uebung12-notizen

uebung12-notizen

1 Übung 12 - 22. Juli

1.1 Basic algorithm

  1. build CFG
  2. compute gen and kill sets
  3. compute IN and OUT sets
  4. compute alive variables

1.2 Liveness Analysis

Global variables: g1,g2,3…

Alive
x1 = x1 + 1x1,x2
x2 = x2 + x1x2
x3 = x2 + x2x3
g1 = x3 + 2g1
endg1

1.3 Gen and Kill

Agenkill
x1 = x1 + 1x1x1
x2 = x2 + x1x2x2
x3 = x2 + x2x3
g1 = x3 + 2g1
Total:x1,x2x1,x2,x3,g1

1.4 In and Out

A -> B,C B -> A C -> C,E

genkill
Ax1,x2,x3x2,x3
Bx2,x3x1
Cx2,x4x3
Ex3g1

in(B) = gen(B) U (out(B) \ kill(B)) out(B) = U in(succ(B))

succinout
AB,Cx1,x2,x3,x4x2,x3,x4
BAx2,x3,x4x1,x2,x3,x4
CC,Ex2,x4x2,x3,x4
E-x3g1

1.5 Dead-Code Elimination

live variablesdead variables
inx2,x3x1, x4,x5
x1 = x2 + x3x1,x2x3,x4,x5
x4 = x1 + x2x1,x2x3,x4,x5
x2 = x1 + x2x2x1, x3,x4,x5
x5 = x2 + x2x2 x5x1, x3,x4
outx2, x5x1, x3,x4

Author: Jan Schäfer <jan@jschaefer-pc>

Date: 2011-07-22 15:47:06 CEST

HTML generated by org-mode 6.21b in emacs 23