Algorithms for Compiler Design:

Global common subexpressions are expressions that compute the same value but in different basic blocks. To detect such expressions, we need to compute available expressions.

Available Expressions

An expression x op y is available at a point p if every path from the initial node of the flow graph reaching to p evaluates x op y, and if after the last such evaluation and prior to reaching p there are no subsequent assignments to x or y. To eliminate global common subexpressions, we need to compute the set of all the expressions available at the point just before the start of every block. This requires computing the set all the expressions available at a point just after the end of every block. We call these sets IN(b) and OUT(b), respectively. The computation of IN(b) and OUT(b) requires computing the set of all expressions generated by the basic block and the set of all expressions killed by the basic block, respectively:

• A block kills an expression x op y if it assigns to x or y and if does not subsequently recompute as op y.

• A block generates an expression x op y if it evaluates x op y and subsequently does not redefine x or y.

To compute the available expressions, we solve the following equations:

Here, also, we obtain the smallest solution.

The algorithm for computing the smallest IN(b) and OUT(b) is given below, where b1 is the initial block, and U is a "universal" set of all expressions appearing on the right of one or more statements of the program.

1. IN(b1) = φ
   OUT(b1) = GEN(b1);

2. for (i=2; i <= n; i++)

   {
      IN(b) = U
      OUT(b) = U - GEN(b)
   }
   

3. flag = true

4. while (flag) do

   {
   flag = false
   for (i=2; i <= n; i++)
      {
         INnew(bi) = Φ
         for each predecessor p of bi
         INnew(bi) = INnew(bi) ∩ OUT(p)
         if INnew(bi) ≠ IN(bi) then
   
            {
            flag = true
            IN(bi) = INnew(bi)
            OUT(bi) = IN(bi) - KILL(bi) ∪ GEN(bi)
            }
         }
   }
   

After computing IN(b) and OUT(b), eliminating the global common subexpressions is done as follows. For every statement s of the form x = y op z such that y op z is available at the beginning of the block containing s, and neither y nor z is defined prior to the statement x = y op z in that block, do:

1. Find all definitions reaching up to the s statement block that have y op z on the right.

2. Create a new temp.

3. Replace each statement U = y op z found in step 1 by:

   

4. Replace the statement x = y op z in block by x = temp.