next up previous
Next: Global Live Variable Analysis Up: Compiler Theory: Code Optimization Previous: Data-flow analysis: copy propagation.

Data-flow analysis: available expressions.

IN PERFORMING COMMON SUBEXPRESSION ELIMINATION we wish tofind in the program two expressions that will always yield the same value, such that one can be replaced by the other.


AN EXPRESSION B OP C IS AVAILABLE at a point p of the program if

This means that at point p we can replace b op c by the result of its last evaluation.


DATA-FLOW EQUATIONS.


DATA-FLOW EQUATIONS. For every basic block B the data-flow sets inE(B) and outE(B) satisfy the following equations

inE(B) = $\displaystyle \bigcap_{{{\ B' \ \in \ {\mbox{\sf pred}}(B)}}}^{{}}$ outE(B'),
outE(B) = genE(B$\displaystyle \bigcup$ $\displaystyle \left(\vphantom{ in_E(B) \setminus kill_E(B) }\right.$inE(B) $\displaystyle \setminus$ killE(B)$\displaystyle \left.\vphantom{ in_E(B) \setminus kill_E(B) }\right)$.
(10)


COMPUTING THE DATA-FLOW SETS. We assume that

The iterative algorithm for determining available expressions is now basically the same as for copy statements.
  1. For the first basic block B1 we define

    inE(B1) = $\displaystyle \emptyset$  and  outE(B1) = genE(B1). (11)

  2. For each basic block B $ \neq$ B1 we define

    outE(B) = E $\displaystyle \setminus$ killE(B) (12)

  3. We update the data-flow sets inE(B) and outE(B) (for every basic block B $ \neq$ B1) with the data-flow equations until there are no more changes in these sets.


next up previous
Next: Global Live Variable Analysis Up: Compiler Theory: Code Optimization Previous: Data-flow analysis: copy propagation.
Marc Moreno Maza
2004-12-02