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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} .
kill: expression is killed at $p$ if one of its argument variables is defined at $p$ .; suppose $e:=a+b$ . Executing $a:=\ldots$ 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\gets e$ , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} has already been computed and has name Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , we can replace the evaluation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} with a reference to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .

Requires global expression naming scheme.

Available Expressions

AVAIL(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} ) is set of expressions available on entry to $b$ .
KILL(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} ) is set of expressions that are killed in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} .
GEN(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} ) is set of expressions defined in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} and not subsequently killed in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} .

The Data Flow Equation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{AVAIL}(b) = \bigcap_{x \in \mbox{predecessors of}\ b} \left( \mathrm{GEN}(x) \cup \left( \mathrm{AVAIL}(x) \setminus \mathrm{KILL}(x) \right) \right)}

Algorithm

Build control flow graph
Initial (local) data gathering
propagate information around the graph
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