Dataflow Analysis
The dataflow is a property, which represents information
regarding usefulness of the data items for the purpose of optimization
Dataflow properties include:
Available
expressions
Reaching
definitions
Live
variables
Busy
expressions
Dataflow Properties:
Definition point is a program point containing the
definition
Reference point is a program point, at which a reference is
made to a data item
Evaluation point is a program point where certain evaluation
expression is specified
Figure1
Available
Expressions:
An expression (x + y) is accessible at the program point w,
only if all the paths are reaching to w
The expression (x + y) is accessible, if no definitions of
any expressions operand (here either x or y) follows its last evaluation down
the path. Neither of them gets modified before use
Figure2
Advantages of
available expressions:
Available expressions are mainly used to find common sub
expressions
Use of available
expressions
Figure3
Example: Available expressions
Figure4
Assign a number to each expression
GEN and KILL Sets
GEN Set:
A current basic block or instruction is said to be in the
GEN set if it creates the definition
In any case, the must be in the output
KILL Set:
A current basic block or instruction is said to be in the KILL
set if it redefines a variable in the expression
After that, the expression is becomes invalid
Algorithm for
Available Expression
Assign a number to each expression
Calculate GEN and KILL sets for each instruction
Calculate aggregate GEN and KILL sets for each basic block
Initialize available set at each basic block to be the
entire set
1
a = b + c
GEN
= { b + c }
d = e +
f
2
GEN
= { e + f}
KILL
= {any expr with d}
f = a +
c
3
GEN
= {a + c}
KILL
= {any expr with f}
Figure 5
GEN and KILL Sets:
a = b +
c
1
GEN
= {1}
KILL
={3, 4, 5, 7}
d = e +
f
2
GEN
= {2}
KILL
= {5, 7}
f = a +
c
3
GEN
= {3}
KILL
= {2, 6}
FIGURE6
Aggregate GEN and
KILL Sets:
The propagation of all the GEN and KILL sets from top of the
basic block to the bottom of the basic block is carried out
Figure7
Aggregate GEN Set
The current expression’s GEN set must reside in the OUTGEN
set
The OUTGEN set must contain the expression which is in the
INGEN set and which is not killed
Figure8
Figure9
Aggregate KILL Set:
The current expression’s KILL set should be in the OUTKILL
set
Any set in the INKILL should be in OUTKILL
Figure10
Figure11
Aggregate GEN and
KILL Sets
Figure12
Figure 13
Propagate Available
Expression Set
An expression would be available at the end, if it is
generated in the GEN set should be in the OUT set
Figure 14
Any expression available at the input (in the IN set) and
not killed, should be available at the end
Figure15
Expression is available only if it is available in all input
paths
IN = ∩
OUT
OUT = GEN U (IN – KILL)
FIGURE16
Figure17
Figure18
