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

• all routes (= pathes) from the start of the program to that point p must pass through the evaluation of b op c, and
• after the (last) evaluation of b op c there are no redefinitions of b or c.

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

DATA-FLOW EQUATIONS.

• The expression b op c is generated by a statement where this expression is evaluated. Similarly, the expression b op c is killed by a statement that redefines b or c.
• Therefore, we can again think of killing and generating available expressions.
• The set gen_E(B) of the expressions generated by a basic block B can be computed (or defined) as follows.
  1. Initially, we set gen_E(B) = $\emptyset$.
  2. Going through the statements of B in sequence,
     • for a statement a := b op c add b op c to gen_E(B) and
     • remove from gen_E(B) any expression containing a.
• Let E be the set of all the expressions in the entire program $\cal {P}$. The set kill_E(B) of the expressions killed by a basic block B can be computed (or defined) as follows.
  1. Initially, we set kill_E(B) = $\emptyset$.
  2. Going through the statements of B in sequence, for a statement a := b op c add to kill_E(B) any expression in E containing a.
• Precautionary principles:
  • we only add an expression to gen_E(B) if we are sure that it will be evaluated
  • if there is a possibility that the expression is killed, we add it to kill_E(B).
• For a basic block B we define
  • in_E(B) as the set of the expressions available at entry(B),
  • out_E(B) as the set of the expressions available at exit(B).

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

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

(10)

COMPUTING THE DATA-FLOW SETS. We assume that

• the set E of all expressions in the entire program $\cal {P}$ has been computed,
• the data-flow sets kill_E(B) and gen_E(B) have been computed for every basic block B.

The iterative algorithm for determining available expressions is now basically the same as for copy statements.

1. For the first basic block B₁ we define

   $$\emptyset$$ (11)

   
   

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

   $$\setminus$$ (12)

   
   

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