Previous Next |
10.1 Perform flow analysis on the program of Exercise 8.6:
Draw the control-flow graph.
Hint: We know the algorithm refuses to terminate until it has a fixed point. The questions are whether (a) it must eventually terminate, and (b) the fixed point it computes is smaller than all other fixed points. For (a) show that the sets can only get bigger. For (b) show by induction that at any time the in and out sets are subsets of those in any possible fixed point. This is clearly true initially, when in and out are both empty; show that each step of the algorithm preserves the invariant.
Within a basic block (actually, in any sequence of instructions not separated by a trap-barrier instruction), no two instructions should write to the same destination register.
r_{1} + r_{5} → r_{4} |
r_{1} + r_{5} → r_{4} |
r_{1} + r_{5} → r_{3} |
r_{1} + r_{5} → r_{4} |
r_{3} × r_{2} → r_{4} |
r_{4} × r_{2} → r_{1} |
r_{4} × r_{2} → r_{4} |
r_{4} × r_{2} → r_{6} |
violates rule 1. |
violates rule 2. |
violates rule 2. |
OK |
Show how to express these restrictions in the register interference graph.
JaVa | Previous Next |