CSCE 434 Lecture 39

« previous | Wednesday, November 27, 2013 | next »

Lecture Slides

Data Flow Analysis

Compile-time analysis of run-time flow of values in the program

• When running a program, instructions come in lexicographic order. When execution splits, only one branch will be taken.
• However, at compile-time We generally don't know which will be taken
• Therefore, we look at both paths "simultaneously"

Data Flow overview:

• Attach sets to nodes and edges of graphs
• Use Lattice to describe relation between values
• Start with initial guess of facts at each node
• Propagate until node sets stabilize at maximal fixed point
• meet over all paths solution (MOP) is desired, but not affordable.

Pointers and arrays are difficult to analyze:

• when writing to array, assume all elements are touched
• when writing to pointers, assume all pointers are modified

Definitions

define

expression is defined at $p$ if value is computed at $p$.

kill

expression is killed at $p$ if one of its argument variables is defined at $p$.

suppose $e:=a+b$. Executing $a:=\dots$ kills $e$.

available

expression $e$ is available at $p$ in a procedure if all paths leading to $p$ contains a prior definition of $e$ that is not killed between its definition and $p$.

Global Common Subexpression Elimination

If at some point for $p\leftarrow e$, $e$ has already been computed and has name $x$, we can replace the evaluation of $e$ with a reference to $x$.

Requires global expression naming scheme.

Available Expressions

• AVAIL($b$) is set of expressions available on entry to $b$.
• KILL($b$) is set of expressions that are killed in $b$.
• GEN($b$) is set of expressions defined in $b$ and not subsequently killed in $b$.

The Data Flow Equation:

$\mathrm{A}\mathrm{V}\mathrm{A}\mathrm{I}\mathrm{L}(b)=\bigcap _{x\in \text{predecessors of}b}(\mathrm{G}\mathrm{E}\mathrm{N}(x)\cup (\mathrm{A}\mathrm{V}\mathrm{A}\mathrm{I}\mathrm{L}(x)\setminus \mathrm{K}\mathrm{I}\mathrm{L}\mathrm{L}(x)))$

Algorithm

1. Build control flow graph
2. Initial (local) data gathering
3. propagate information around the graph
4. post-processing

Worklist Iterative Algorithm

queue<Node> worklist(cfg.nodes);

while(!worklist.empty()) {
    Node n = worklist.dequeue();
    recompute AVAIL(n);
    if (AVAIL(n).changed())
        worklist.enqueue(n.successors);
}

Representation

Facts usually represented on bit vectors

union is bitwise OR, intersection is bitwise AND