Next: Global Live Variable Analysis
Up: Compiler Theory: Code Optimization
Previous: Dataflow analysis: copy propagation.
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.
DATAFLOW 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.
 Initially, we set
gen_{E}(B) = .
 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 .
The set kill_{E}(B) of the expressions killed by a basic block B can be computed
(or defined) as follows.
 Initially, we set
kill_{E}(B) = .
 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).
DATAFLOW EQUATIONS. For every basic block B the dataflow sets in_{E}(B) and out_{E}(B) satisfy
the following equations
in_{E}(B) 
= 
out_{E}(B'), 
out_{E}(B) 
= 
gen_{E}(B) in_{E}(B) kill_{E}(B). 

(10) 
COMPUTING THE DATAFLOW SETS. We assume that
 the set E of all expressions in the entire program has been computed,
 the dataflow 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.
 For the first basic block B_{1} we define
in_{E}(B_{1}) = and out_{E}(B_{1}) = gen_{E}(B_{1}). 
(11) 
 For each basic block
B B_{1} we define
out_{E}(B) = E kill_{E}(B) 
(12) 
 We update the dataflow sets in_{E}(B) and out_{E}(B) (for every basic block
B B_{1}) with the dataflow equations until there are no more changes
in these sets.
Next: Global Live Variable Analysis
Up: Compiler Theory: Code Optimization
Previous: Dataflow analysis: copy propagation.
Marc Moreno Maza
20041202