uebung12-notizen
Table of Contents
1 Übung 12 - 22. Juli
1.1 Basic algorithm
- build CFG
- compute gen and kill sets
- compute IN and OUT sets
- compute alive variables
1.2 Liveness Analysis
Global variables: g1,g2,3…
| A | live |
|---|---|
| x1 = x1 + 1 | x1,x2 |
| x2 = x2 + x1 | x2 |
| x3 = x2 + x2 | x3 |
| g1 = x3 + 2 | g1 |
| end | g1 |
1.3 Gen and Kill
| A | gen | kill |
|---|---|---|
| x1 = x1 + 1 | x1 | x1 |
| x2 = x2 + x1 | x2 | x2 |
| x3 = x2 + x2 | x3 | |
| g1 = x3 + 2 | g1 | |
| Total: | x1,x2 | x1,x2,x3,g1 |
1.4 In and Out
A -> B,C B -> A C -> C,E
| gen | kill | |
|---|---|---|
| A | x1,x2,x3 | x2,x3 |
| B | x2,x3 | x1 |
| C | x2,x4 | x3 |
| E | x3 | g1 |
in(B) = gen(B) U (out(B) \ kill(B)) out(B) = U in(succ(B))
| succ | in | out | |
|---|---|---|---|
| A | B,C | x1,x2,x3,x4 | x2,x3,x4 |
| B | A | x2,x3,x4 | x1,x2,x3,x4 |
| C | C,E | x2,x4 | x2,x3,x4 |
| E | - | x3 | g1 |
1.5 Dead-Code Elimination
| live variables | dead variables | |
|---|---|---|
| in | x2,x3 | x1, x4,x5 |
| x1 = x2 + x3 | x1,x2 | x3,x4,x5 |
| x4 = x1 + x2 | x1,x2 | x3,x4,x5 |
| x2 = x1 + x2 | x2 | x1, x3,x4,x5 |
| x5 = x2 + x2 | x2 x5 | x1, x3,x4 |
| out | x2, x5 | x1, x3,x4 |
Date: 2011-07-22 15:47:06 CEST
HTML generated by org-mode 6.21b in emacs 23
