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.

Figure 11: A control flow graph.

• 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.

Figure 12: A control flow graph.

Obviously, one would like to move out the first two lines of the basic block B₂. This will be achieved using Invariant Code Motion to be described now.