Recall the simple basic-block optimizations
X := 3 Y := Z + W Q := X + Yto
X := 3 Y := Z + W Q := 3 + Yto (if X is not used anywhere else)
Y := Z + W Q := 3 + Y
These optimizations can be extended to an entire control-flow graph (CFG).
BB1: X := 3 B > 0 then goto BB2 else goto BB3 BB2: Y := Z + W BB3: Y := 0 BB4: A := 2 * XHere we can substitute X with 3 in BB4.
BB1: X := 3 B > 0 then goto BB2 else goto BB3 BB2: Y := Z + W X := 4 BB3: Y := 0 BB4: A := 2 * XNow we cannot replace X with 3 in BB4 even though X is only assigned constants.
How do we know if it is OK to globally propagate constants?
To replace a use of
x by a constant
must know: On every path to the use of
x, the last assignment
x := k.
Let's look at the first example. Indeed this condition is satisfied for X:=3 at BB4.
Let's look at the second example. This condition is not satisfied for
X at BB4.
The correctness condition is not trivial to check. "All paths" includes paths around loops and through branches of conditionals.
Checking the condition requires global dataflow analysis, i.e., an analysis of the entire CFG.
In general, global optimization tasks share several traits:
Xat a particular point in program execution.
Xat any point requires knowledge of the entire program.
Xto be true, then want to know either:
Xis definitely true.
Global dataflow analysis is a standard technique for solving problems with these characteristics. Global constant propagation is an example of such a problem.