Computing Available Expressions

Use of Available Expressions

Available expressions eliminate recomputations. For example, suppose In(B) contains an expression A op B as does B₄ (BB * 12) in Example 7, that is, A op B is available at the beginning of the block as is BB * 12 at the beginning of block B₄. Suppose, further, that A op B is used in B (before A or B is redefined). Then we can avoid recomputing A op B in the following way:

1. Find all definitions that reach B and have A op B on the right-hand side.

2. Create a new variable T to hold the value of A op B.

3. Replace each definition Z := A op B from (1) by

T := A op B

Z := T

4. Replace all uses Q := A op B by Q := T.

Example 8 shows this for the program of Example 7 and for the expressions BB * 12 and A + BB * 12.