Aalborg den 05.05.2003

Liveness Analysis vejledende løsninger

Opgave 10.1

A

Vi har fundet basic block i opgave 8.6 fra sidste gang. Vi forbinder disse basic blocks og får en control flow graph (CFG) som vist nedenfor.

B

Hvis basic blocken for linje 1 og 2 er state 1 og basic blokken for linje 15 er state 8 så finder vi use, def og succ.

State Use Def Succ
0 empty m, v 1
1 n,v empty 2, 8
2 v r,s 3
3 r,v empty 4, 5
4 v v 1
5 r,s,x,m s,x 6, 7
6 s m 7
7 r r 3
8 m empty empty

Vi finder herefter live- in og live-out vha. algoritme 10.4 på side 206 i bogen.

State Live-in Live-out
0 x, n m, n, v, x
1 m, n, v, x m, n, v, x
2 m, n, v, x m, n, r, s, v, x
3 m, n, r, s, v, x  m, n, r, s, v, x
4 n, m, v, x m, n, v, x
5 m, n, r, s, v, x m, n, r, s, v, x
6 n, r, s, v, x m, n, r, s, v, x
7 m, n, r, s, v, x m, n, r, s, v, x
8 m empty

C

Inference graf udtrykt som en matrix.

m n r s v x
m   X X X X X
n X       X X
r X X   X X X
s X X X   X X
v X X       X
x X X X X X  

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