One of the constraints placed on code motion is not to move a computation
to a path where it would not have been executed in the original program.
To check this constraint, the compiler might compute a predicate
`d-safe(p,v)`, which is true if a computation of `v` at
program point `p` does not introduce a new value on a terminating
path starting at `p`.

- Characterization of a data flow problem by a function of a program point and a value
- This particular analysis only makes sense if global value numbering has been done previously
- The need to compute that function for each value at each program point
- When the function result is Boolean, we can often compute it in parallel for a number of values by using a bit vector.

- If
`v`is used at program point`p`then`d-safe(p,v)`is true - If
`p`does not compute any operand of`v`, and`d-safe(p',v)`is true for all of the successors`p'`of`p`then`d-safe(p,v)`is true

used(p,v): v appears in the tuple at p through(p,v): no operand of v appears before := in the tuple at pUsing these predicates, our inferred conditions can be described by:

d-safe(p,v) = used(p,v) or through(p,v) and for all successors p' of p, d-safe(p',v)Let's try computing

- Working through from the back
`d-safe(17,v)`must be false, because a computation of`v`in 17 introduces a new value on the path Entry, 1, 3, 4, 6, 17, Exit- Therefore
`d-safe(exit,v)`must be assumed to be false `d-safe(11,v)`and`d-safe(12,v)`are both clearly true, but the formal description above would also allow them both to be false- A
*fixedpoint*of a computation is a set of values such that if you compute all of the functions using them the answers don't change - The computation of
`d-safe(p,v)`for this graph, using the given definition, has two fixedpoints - In this case, we get the one we want by assuming
`d-safe(p,v) = true`for all`p = 1,...,17`initially - Any value can only change once, so the computation must reach a fixedpoint

- Put all
`p`onto a work list, and set all values of`d-safe(p,v)`to ``true'' - Take an element off of the work list and compute its value
- If the new value differs from the old, put all
`p`depending on this value onto the work list if they are not there already - If the work list is not empty, go to step 2

- This algorithm is linear in the number of values:
- A value can change at most once
- A value can be put back on the list at most once (when
*some*successor becomes false)

- Those values dependent on a value are simply its predecessors in the graph
- Note that in practice we combine the first computation with putting the value on the work list
- A quadratic algorithm simply scans all
`p`repeatedly, stopping when none changes - The quadratic algorithm
*could*be approximately linear in practice, if a good order happened to be chosen

Recall that the earliest placement of a computation minimized the code
size.
To determine this placement, the compiler might compute a predicate
`earliest(p,v)`, which is true at all nodes reached from the start
node via paths along which there is no point `p'` for which
`d-safe(p',v)` is true.
The earliest placement would then be at a point for which both
`d-safe(p',v)` and `earliest(p,v)` were true.

- The
*first*d-safe node reachable from the start node by a path containing no d-safe node will have`earliest(p,v)`true - It's tempting to think that the earliest point is one that is d-safe
and has no d-safe predecessors, but here's a counterexample:
Node 3 is d-safe and 2 isn't, but 1 is the earliest node at which

`v`can be computed. There is no need to re-compute the value in 3, which is dominated by 1.

earliest(p,v) = there exists a predecessor p' of p such that (not d-safe(p',v) and earliest(p',v))We can compute this predicate by using the same algorithm as before, but

- Setting all values to false initially
- Assuming that
`earliest(entry,v) = true`

- Do the computation for the sample graph, showing that the predicate is true for nodes 1, 2, 3, 4, 5, 6 and 17
- The function and initial value have changed, but the algorithm remains the same
- Those values dependent on a value are simply its successors in the graph

A computation can be delayed to a node without execution-time cost so long as none of the predecessors of that node uses the value computed. In terms of predicates:

delay(p,v) = (d-safe(p,v) and earliest(p,v)) or for all predecessors, p', of p (not used(p',v) and delay(p',v))We can compute this predicate by using our general-purpose algorithm, but

- Setting all values to true initially
- Assuming that
`delay(entry,v) = false`

- Do the computation for the sample graph, showing that the predicate is true for nodes 2, 5, 7, 8, 11, 12, 14 and 15
- Those values dependent on a value are simply its successors in the graph

latest(p,v) = delay(p,v) and for some successor, p', of p) (used(p,v) or not delay(p',v)

- We don't need the general-purpose algorithm here because
`latest(p,v)`is not defined in terms of itself - Do the computation for the sample graph, showing that the predicate is true for nodes 2, 7, 14 and 15

- Successors of a node (e.g.
`d-safe`) - Predecessors of a node (e.g.
`earliest`,`delay`) - Universal quantifiers (e.g.
`d-safe`,`delay`) - Existential quantifiers (e.g.
`earliest`)

- We use models for many compiler construction tasks (e.g. parsing, name analysis, tree transformation)
- A model allows us to understand new problems in terms of old ones
- A model allows us to prove things like termination once
- There is the possibility of providing a tool that will generate processors to solve problems fitting the model

- A set of inferences we make about the program, described as a complete
semilattice
`L = (A, top, bottom, meet)`with height`d`, where:`A`is an arbitrary set of inferences`top`and`bottom`are distinguished elements of`A``meet`is an operator such that for any`a`,`b`and`c`in`A`,a meet a = a a meet b = b meet a a meet (b meet c) = (a meet b) meet c a meet top = a a meet bottom = bottom

`d`is the length of the longest chain in`A`

- A set,
`F`, of k-ary monotone functions from lattice elements to lattice elements containing the identity function and closed under pointwise meet - A mapping from operators of the program to elements of
`F`

See A unified approach to path problems, Journal of the ACM 28 (July, 1981) 577-593, for an explanation of the theory behind this class of problems.

- The operator
`<=`is defined on the*lattice*; it isn't the normal integer operator `d`must be bounded by a constant (usually small -- 2 or 3)- The arity of the functions is also usually no more than 3
- Our general algorithm is applied by first setting all of the values to
`top`

- The inferences we make about the program are
`Safe`and`Unsafe`;`Safe`is the top element of the lattice and`Unsafe`is the bottom element. - The longest chain in the set of inferences is 1, so
`d = 1` - The
`meet`operation is defined by the following table:meet `Safe``Unsafe``Safe``Safe``Unsafe``Unsafe``Unsafe``Unsafe`It's easy to see by complete enumeration that this operation satisfies all of the conditions on

`meet`. - The set
`F`contains three functions, two 0-ary (constant) and one 1-ary:`f`_{0}= Safe`f`_{1}= Unsafe`f`_{2}(a) = a

- The mapping from a program point
`p`to an element of`F`is:used(p,v) ? f

_{0}: through(p,v) ? f_{2}: f_{1}

- A function is monotone if the table describing its operation can be written so that the the values in every row are monotone decreasing from left to right and the values in every column are monotone decreasing from top to bottom
`meet`is applied to the successors of a node if there is more than one`f`is applied to the result of the meet (a single value summarizing the successors)_{2}(a)- Show how the computation works for the sample graph:
- Nodes 2, 9, 14, 15 and 16 get
`f`_{0} - Node 1 gets
`f`_{1} - All other nodes get
`f`_{2}

- Nodes 2, 9, 14, 15 and 16 get

- Determine a predicate,
`B`, that defines continuation (i.e. the iteration stops if`B`is false) - Determine an integer value,
`t`, such that`B`implies implies`t>0`and`t`is decreased by each iteration

Example:

while (fread(...) != EOF) {...} B: We haven't gotten to the end of the file t: Number of characters remaining in the file

- Show that
`B`and`t`meet the requirements - Note that
`t`need not be*computable*by the program

B: The work list is empty t: (sum of argument levels)*(total number of values) + (size of work list)``Argument level'' is the index of the row or column of the function's table, with the origin at the lower right corner.

`t>0`if the work list isn't empty- If a value doesn't change when it's computed, that value is taken off
the work list, so
`t`decreases - If a value
*does*change when it's computed, an arbitrary number of computations may be put onto the work list but the total size of the work list never exceeds the total number of values - If a value changes, it must lower the level of some argument, so
`t`decreases

- Constancy undetermined
- A particular constant value
- Not a constant

- Global constant propagation depends on the SSA representation, but
*not*on global value numbering; in fact, it should be done earlier, to eliminate computations - All values are initially undetermined as to constancy
- Values of external variables are always ``not a constant''
- Need functions to evaluate at least
*some*operations - Result of any operation with at least one ``not a constant'' operand is ``not a constant''
- At a phi function, all operands must be the same value for the result to be constant

- L = (
`Z`union {Undetermined, Variable}, Undetermined, Variable,`meet`), where`Z`is the set of integers. Here's a picture of the lattice: - The
`meet`operator is applied to the values at a phi function:meet Undetermined c _{0}Variable Undetermined Undetermined c _{0}Variable c _{1}c _{1}(c _{0}==c_{1})?c_{0}:VariableVariable Variable Variable Variable Variable Here are tables for the integer

`+`and`*`operators:+ Undetermined c _{0}Variable Undetermined Undetermined Undetermined Undetermined c _{1}Undetermined c _{0}+c_{1}Variable Variable Undetermined Variable Variable * Undetermined 0 c _{0}Variable Undetermined Undetermined Undetermined Undetermined Undetermined 0 Undetermined 0 0 0 c _{1}Undetermined 0 c _{0}*c_{1}Variable Variable Undetermined 0 Variable Variable ### [Discuss-

- Start out with all of the values
`Undetermined` `0`and`c`are not comparable in the lattice_{i}- The two functions are monotone in each argument because
*if*a value changes, it*must*move from left to right or top to bottom in one of the tables

### ]

## Example of constant propagation

Consider the innermost loop of the nested`for`statements, translated by duplicating the test:Control flow graph Computation After constant propagation 5: V

_{51}:=l_{3}+1 k_{2}:=V_{51}V_{52}:=V_{51}<u_{3}JumpT(5a,V_{52}) JumpF(8,V_{52})5: V

_{51}:=l_{3}+1 k_{2}:=V_{51}Jump(5a)5a: Jump(7)

5a: Jump(7)

7: k

_{3}:=phi(k_{2},k_{4}) V_{1}:=i_{2}V_{2}:=V_{1}*C_{1}... V_{71}:=V_{6}+1 k_{4}:=V_{71}V_{72}:=V_{71}<u_{3}JumpT(7,V_{72}) JumpF(8,V_{72})7: k

_{3}:=phi(k_{2},k_{4}) V_{1}:=i_{2}V_{2}:=V_{1}*C_{1}... V_{71}:=V_{6}+1 k_{4}:=V_{71}V_{72}:=V_{71}<u_{3}JumpT(7,V_{72}) JumpF(8,V_{72})### [Discuss-

- Do the computation of the constants for block 1
- Assuming that the array has at least one element in addition to the
border elements,
`l`_{3}+1<u_{3} - The same thing will occur in the outer loops, effectively turning the
`for`case into the`do-while`case and allowing computations to be moved out of the loop. - Note that this would
*not*have worked if the code generator hadn't duplicated the test -- code generation needs to prepare for optimization

### ]

## Executability

In the example above, we used our intuition to change`JumpT(b,true)`into`Jump(b)`and to eliminate`JumpF(b,true)`. The compiler, of course, must use an inference to make this decision:- L = ({Non-executable, Executable},Non-executable, Executable, meet)
- The
`meet`operator is applied to the executability of multiple predecessors of a program point:meet Non-executable Executable Non-executable Non-executable Executable Executable Executable Executable - The function set
`F`:The

`JumpT`function is applied to the value of the condition and the executability of the last non-jump:JumpT Undetermined 0 c _{i}Variable Non-executable Non-executable Non-executable Non-executable Non-executable Executable Non-executable Non-executable Executable Executable The

`JumpF`function is applied to the value of the condition and the executability of the last non-jump:JumpF Undetermined 0 c _{i}Variable Non-executable Non-executable Non-executable Non-executable Non-executable Executable Non-executable Executable Non-executable Executable `Jump`and`:=`operations use the identity function, applied to the executability of the predecessor.

### [Discuss-

- This is the first example of a data flow analysis problem that uses the results of another data flow analysis problem as an argument
- A basic block may end in a sequence of jumps, one of which is executable if the last tuple before that sequence is executable
- The fact that one jump in a sequence is non-executable does not necessarily mean that subsequent jump in the sequence are non-executable

### ]

waite@isa.informatik.th-darmstadt.de Revision $Revision: 1.3 $ - Start out with all of the values