Next: Invariant Code Motion Up: Compiler Theory: Code Optimization Previous: Global Copy Propagation and Dead

# Global Recycling of Available Expressions

KEY IDEA.

• We look for statements a:=b op c where
• b op c is in the list of available expressions at the start of the block where a:=b op c appears, and
• b,c have not been defined earlier in the block.
• We look for an earlier evaluation of a statement d:=b op c
• However, we cannot just use the value of d because the available expression may actually have come along a completely different route.
• This problem can be solved by storing the value of each occurrence of the available expression (in different parts of the program) into the same temporary variable t and then use the value of the temporary.

• This process generates new copy statements, but these can usually be eliminated using further copy propagation and deadcode elimination.

ALGORITHM.

1. Find all statements S: a := b op c occurring in a basic block B such that
• b op c is available at Entry(B), and
• B contains no earlier definition for b or c.
2. For each statement S found in the previous step,
1. allocate a temporary variable t, and
2. from block B search backwards along all possible paths the previous statement d := b op c, and immediately after it insert the statement t := d.
3. Replace the statement S by a := t.

EXERCISE. Apply the previous algorithm to Figure 11.

• The statement t4 := a-b is found in stage (i) of the algorithm.
• Searching backwards, the unique previous evaluation in statment 4.
• So, after Statement 4, we insert t5 := t1 and statement 12 is replaced by t4 := t5.
• After new copy propagation and dead code elimination, line 12 is eliminated.
After applying these transformations, we obtain the control flow graph of Figure 12.
Obviously, one would like to move out the first two lines of the basic block B2. This will be achieved using Invariant Code Motion to be described now.

Next: Invariant Code Motion Up: Compiler Theory: Code Optimization Previous: Global Copy Propagation and Dead
Marc Moreno Maza
2004-12-02