Previous    Next

## EXERCISES

• 10.1 Perform flow analysis on the program of Exercise 8.6:

1. Draw the control-flow graph.

2. Calculate live-in and live-out at each statement.
3. Construct the register interference graph.
• **10.2 Prove that Equations 10.3 have a least fixed point and that Algorithm 10.4 always computes it.

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.

• *10.3 Analyze the asymptotic complexity of the one-variable-at-a-time method of computing dataflow information.
• *10.4 Analyze the worst-case asymptotic complexity of making an interference graph, for a program of size N (with at most N variables and at most N control-flow nodes). Assume the dataflow analysis is already done and that use, def, and live-out information for each node can be queried in constant time. What representation of graph adjacency matrices should be used for efficiency?
• 10.5 The DEC Alpha architecture places the following restrictions on floating-point instructions, for programs that wish to recover from arithmetic exceptions:
1. 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.

2. A source register of an instruction cannot be the same as the destination register of that instruction or any later instruction in the basic block.  r1 + r5 → r4 r1 + r5 → r4 r1 + r5 → r3 r1 + r5 → r4 r3 × r2 → r4 r4 × r2 → r1 r4 × r2 → r4 r4 × r2 → r6 violates rule 1. violates rule 2. violates rule 2. OK

Show how to express these restrictions in the register interference graph.

 JaVa Previous    Next