Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

870 questions

988 answers

1.4k comments

439 users

0 votes
Guten Tag,

gibt es irgendwo eine Musterlösung zu einer Aufgabe der Form von Aufgabe 5 e) der RoSy-Altklausur SS18? Mich würde insbesondere interessieren, ob die Register mit Variablen (wie im Skript) oder Konstanten identifiziert werden sollen und wie ein Arrayzugriff übersetzt wird, da wir ja die Adresse(n) des Arrays/der Array-Elemente nicht kennen. Wie soll mit Statements  wie z.B. if n<= i goto 11 umgegangen werden? Genau genommen ist das doch gar kein 3-Adress-Code, da die Branch-Bedingung ein Ausdruck und keine Variable ist.

Vielen Dank für alle Beiträge!
in * TF "Emb. Sys. and Rob." by (1.1k points)
edited by

2 Answers

+1 vote
 
Best answer

Yes, the variables in the Cmd program must be mapped to registers, which is done during the register allocation phase in the MiniC compiler. The constants may be held in registers. Or as immediate operands in instructions that operate on them, if there is an immediate operand version of that instruction in the Abacus instruction set and if the constant value can fit into the number of bits reserved for immediate operands in the instruction format. 

With regard to arrays, they are always mapped to the main memory by the MiniC compiler. So an array access (resp. assignment) means that you have to use the load (resp. store) instruction to read from (resp. write to) that array element in the main memory. The offset of an array element should be a variable according to the syntax for Cmd statements. So you have to use the register mapped to this variable (with of course the base address of that array) in the load or store instruction to respectively read or write the array element.
Finally, the if..goto Cmd statements are translated to conditional branch instructions (bez,bnz..) in Abacus.
Often trying out such a small MiniC program in our tools web page https://es.cs.uni-kl.de/tools/teaching/MiniC.html would help:
The MiniC program:
thread t {
    [5]nat a;
    nat e,s,i;
    
    i = 0;
    do {
        e = a[i];
        s = s + e;
        i = i + 1;
    } while (i<5)
}
is compiled to the Cmd program:
0000 : i := 0
0001 : e := a[i]
0002 : s := s + e
0003 : i := i + 1
0004 : _t1 := 5
0005 : _t0 := i < _t1
0006 : if _t0 goto 1
0007 : sync
which is translated to the Abacus program:
mov $2,0            // i := 0
mov $7,0            // e := a[i]
ld $3,$7,$2         // 
addu $1,$1,$3    // s := s + e
addiu $2,$2,1     // i := i + 1
mov $3,5            // _t1 := 5
sltu $3,$2,$3      // _t0 := i < _t1
bnz $3,-6            // if _t0 goto 1
sync                   // sync
for the following register allocation:
_t0 -> $3
_t1 -> $3
e -> $3
i -> $2
s -> $1
This example has almost all the points that you wanted to address. You can see that i := i + 1 is translated to addiu $2,$2,1 where variable i is mapped to register $2 and constant 1 appears as immediate operand. The array access e := a[i] is translated to ld $3,$7,$2 where $7 is the base address of array a (memory location 0) and $2 is the offset (variable i). Finally if _t0 goto 1 is translated to bnz $3,-6 where _t0 is mapped to $3 (branch condition) and -6 is the appropriate branch target distance. 
Though the above translations are what the online MiniC compiler gives you, of course this is not the only possible translation. For example, e := a[i] may also be translated to ldi $3,$2,0 by having the base address of a as an immediate operand. Clearly different translations are possible for the same Cmd program.
By the way, you cannot have a statement like if n<= i goto 11 in the Cmd program. According to the syntax of Cmd statements (see slide 24 / 162), it should be if x goto L, where x is a variable and L the line number. I am not sure why the former appears in the previous exam paper. But I guess that is to simply reduce the number of lines in the given Cmd program so as to make the liveness analysis relatively easier. Also I am not sure why a solution is not given for 5e (may be because different solutions are possible!). 
by (2.5k points)
selected by
+1 vote
Soeben wurde eine Musterlösung für die Aufgabe 5 aus SS18 erstellt und im Internet zur Verfügung gestellt. Die Aufgabe wurde aber an die aktuelle Syntax der CMD-Sprache angepasst.
by (139k points)

Related questions

Imprint | Privacy Policy
...