Aalborg den 05.05.2003

Kodegeneration vejledende løsninger

Opgave 8.1

Vi skal fjerne ESEQ fra venstre siden uden ændre rækkefølgen beregningerne forgår i. Prøve at tegne grafer lignende dem i figur 8.1 og overbevis jer selv om at transformationerne er rigtige.

a) MOVE(TEMP t, ESEQ(s, e)) => SEQ(MOVE(TEMP t), SEQ(s, EXP(e)))

b) MOVE(MEM(ESEQ(s, e1)), e1) => SEQ(s, MOVE(EXP(e1), EXP(e2)))

c) MOVE(MEM(e1), ESEQ(s, e2)) =>SEQ(MOVE(MEM(e1)), SEQ(s, EXP(e2)))

d) EXP(ESEQ(s, e) => SEQ(s, EXP(e))

e) EXP(CALL(ESEQ(s, e), args)) => SEQ(s, EXP(CALL(e, args)))

f) MOVE(TEMP t, CALL (ESEQ(s, e), args)) => SEQ(s, MOVE(TEMP t), CALL(e, args)))

g) EXP(CALL(e1, [e2,ESEQ(s, e3,e4])) => SEQ(MOVE(TEMP t1, e1), SEQ(MOVE(TEMP t2, e2), SEQ(s, EXP(CALL(t1, [t2, e3,e4])))))

Opgave 8.6

Husk for CJUMP hvis betingelsen evaluerer til sandt så hoppes til den label der er angivet. Ellers tages den næste linje i programmet.

m = 0
v = 0
if v >= n goto 15
r = v
s = 0
if r < n goto 9
v = v + 1
goto 3
x = M[r]
s = s + x
if s<= m goto 13
m = s
r = r +1
goto 6
return m
Vi indsætter først en
label i toppen og labels
for alle linjer der er gotos til.
Yderligere laver laves if'er
om til CJUMPs
og rene gotos til JUMPS
label L0
m = 0
v = 0
label L3
CJUMP(v>=n, L15)
r = v
s = 0
label L6
CJUMP (r<n L9)
v = v + 1
JUMP(L3)
label L9
x = M[r]
s = s + x
CJUMP(s<= n, L13)
m = s
label L13
r = r +1
JUMP (L6)
label L15
return n
Vi deler så i basic blocks.
Når vi ser en label stops
blok omgående og nu
begynder. Når vi ser
CJUMP eller JUMP tages
denne med i eksisterende
basic block og en ny startes
label L0
m = 0
v = 0
label L3
CJUMP(v>=n, L15)
r = v
s = 0
label L6
CJUMP (r<n L9)
v = v + 1
JUMP(L3)
label L9
x = M[r]
s = s + x
CJUMP(s<= n, L13)
m = s
label L13
r = r +1
JUMP (L6)
label L15
return n
Vi indsættes ekstra labels og jumps.
label L0
m = 0
v = 0
jump L3
label L3
CJUMP(v>=n, L15)
label L5
r = v
s = 0
JUMP L6
label L6
CJUMP (r<n L9)
label L7
v = v + 1
JUMP(L3)
label L9
x = M[r]
s = s + x
CJUMP(s<= n, L13)
label L12
m = s
JUMP L13
label L13
r = r +1
JUMP (L6)
label L15
return n

Opgave 9.1

A

B

Opgave 9.3


Kristian Torp
torp (at) cs (dot) auc (dot) dk