A common framework for expressing algorithms that compute information about a program.
Control Flow Graph
Each statement becomes a node
Edges between nodes represent control flow
Dataflow Analysis
Worklist Algorithm
- Initialize all d to empty set…
- add nodes to worklist…
- while worklist is not empty
- remove a node n
- info_in will be map of sets of incoming information
- info_out will be map of sets of outgoing information computed through F
- for each outgoing edge
if info_out is different from what has been previously calculated, update with info_out and add all destinations of the outgoing edges…- let new_info be superset of previously calculated and info_out
- if new_info is different from what has been previously calculated, update with new_info and add all destinations of the outgoing edges…
Issue: (1) Ordering? Random order will take long due to redundancy, so use reverse depth-first post-order (2) Does this algorithm terminate? May not terminate oscillating in the original algorithm, so make supersets to make guarantees…
May vs Must
Forward vs Backward
Although constraints are not directional, flow functions are
Forward
– the constraints are of the form out = F(in)
Backward
– In some cases, the constraints are of the form in = F(out)
– e.g. live variables
Can formalize backward analysis in two ways
– Option 1: reverse flow graph, and then run forward problem
– Option 2: re-develop the theory, but in the backward direction
Precision
Pretty much any problem in compiler optimization is undecidable.
In order to find solutions for such problem, we approximate! Therefore, we may lose precision.
There are several factors that may cause imprecision:
– Unreacheable code
– Path sensitivity
. Branch correlations: some paths are infeasible
. Path merging: can lead to loss of precision
MOP: meet over all paths
We find all paths that lead to certain program point, do analysis on each path, and merge all information.
MOP is the “best” possible answer given a fixed set of flow functions
However, there are too many paths, so it is not computable.
MOP != dataflow
However, by imposing some restrictions on the flow functions, we could guarantee that dataflow is the same as MOP.
If F(a U b) == F(a) U F(b) (distributivity holds), then dataflow is the same as MOP.
Reaching Definitions
For each program point in the CFG, compute the set of definitions (statements) that may reach that point.
D = 2^A
Top = All, Bottom = Empty (May)
Join = U, Meet = ^
Constant Propagation
D = 2^A
Top = Empty, Bottom = All (MUST)
Join = ^, Meet = U
We could improve the lattice by reducing the infinite height lattice to simpler one
– D = {Top, Bottom} U Z
– Two possibilities
. Option 1: tuple of lattices
. Option 2: map from variables to single lattice
Common Subexpression Elimination
Want to compute when an expression is available in a var
S = {X–>E | X \in Var, E \in Expr}
D = 2^S
Top = Empty, Bottom = All (MUST)
Join = ^, Meet = U
Live Analysis
A variable is live at a program point if it will be used before being redefined
A variable is dead at a program point if it is redefined before being used
D = 2^{Vars}
Top = All, Bottom = Empty (MAY)
Join = U, Meet = ^
