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

- However, we cannot just use the value of
- This process generates new copy statements, but these can usually be eliminated using further copy propagation and deadcode elimination.

__ALGORITHM.__

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

- For each statement
`S`found in the previous step,- allocate a temporary variable
`t`, and - 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`. - Replace the statement
`S`by`a := t`.

- allocate a temporary variable

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

2004-12-02