Global constant propagation

Recall: To replace a use of x by a constant k, we must know: On every path to the use of x, the last assignment to x is x := k. Let's call this condition AA.

Global constant propagation can be performed at any point where AA holds.

Let's first consider the case of computing AA for a single variable X at all program points. One can potentially repeat this procedure for each variable (inefficient but okay; improvements possible by doing all at once -- later).

To make the problem precise, we associate one of the following values with X at every program point:

value	interpretation
\top	This statement never executes (or we have not executed it so far). This statement is unreachable (so far).
K	Whenever this program point is reached, X evaluates to constant K
\bot	X may not a constant, we are not sure if it is a constant.

\bot is our safe situation and has no information whatsoever; we can always say that X is not a constant (means that we do not know if it is a constant or not). \top has the most amount of information. It says that this program point is unreachable, whereas K says that if it is reached, then X evaluates to constant K (the former implies the latter). Thus the values at the lower end of the table are "safer" values, whereas the values at the higher end are "more precise" values. An analysis should aimfor the "most precise" values while being correct; however designing an analysis that is most precise is an undecidable problem in general, and we usually do the best possible with a reasonable amount of effort.

BB1:
               === X = \bot (at this program point)
X := 3
               === X = 3
B > 0 then goto BB2
         else goto BB3
              === X = 3 on both branches

BB2:
             ==== X = 3
Y := Z + W
             ==== X = 3
X := 4
             ==== X = 4

BB3:
             ==== X = 3
Y := 0
             ==== X = 3

BB4:
             ==== X = \bot
X := 2 * X

Given global constant information, it is easy to perform the optimization

• Simply inspect the x = ? associated with a statement using x
• If x is a constant at that point, replace all uses of x with that constant.
• But how do we compute x = ? at each program point.

The analysis of a compicated program can be expressed as a combination of simple rules relating the change in information between adjacent statements.

The idea is to "push" or "transfer" information from one statement to the next. Initialize all the values in the program above to \top (unreachable so far), except the entry value. Run the analysis.

For each statement s, we compute information about the value of x immediately before and after s

• Define a function C that stands for "constant information".
• C(x,s,in) = value of x before s.
• C(x,s,out) = value of x after s. For a statement that has two exits, e.g., a conditional branch, have two values C(x,s,out1) and C(x,s,out2).

Define a transfer function that transfers information across a statement/instruction. This transfer function is derived from the execution semantics of that statement, except that it is different, e.g., to accommodate extra \top and \bot values. There are also other differences as we will see later. Discuss the transfer functions of X:=K, Y:= ..., and if B goto L.

The analysis is designed so that the order in which the branches are taken becomes inconsequential.

Change the program to remove the X:=4 statement, and run the analysis again. The stopping criteria is when the values stop changing, which is als called a fixed point. One can potentially do better for this example program, to avoid having to check the fixed point, e.g., by carefully ordering the execution of the analysis; but in general, for programs with loops or arbitrary cycles, checking a fixed point remains the most general solution.

Change the program to add a loop from BB3 to itself, replacing X:=4 with X:=X+1. Notice that the loop reaches a fixed point after two iterations. In general, the analysis is designed such that the fixed point is reached after a finite number of steps/iterations.

When we update the value at a program point, that already has a value, and has multiple predecessors, it may be tempting to consider the previous value at that analysis to determine the new value. We do not that in our formulation, instead, we always look at the current values only of all the predecessor program points. So for example when we transfer a value to a program point with multiple predecessors, we again look at all its predecessors' current values to determine the new value at that program point.

This function that determines the value of a program point based on the value of the predecessor points is called the meet operator. The meet operator is only a property of the values being computed, and has nothing to do with the program's instructions. Further, a meet operator only makes sense for multiple predecessors; for a single predecessor, we simply copy the value.

Let's discuss the meet operator for our constant-information analysis. In the following rules, let statement s have immediate predecessor statements p1, ..., pn.

         |
         |
         v
 ---> s <---

1. if C(pi, x, out) = \bot for any i, then C(s, x, in) = \bot. For all we know, the execution may come down that predecessor, and so in that case we can make no prediction about the value of x.
2. if C(pi, x, out) = c and C(pi, x, out) = d and c <> d, then C(s, x, in) = \bot. We saw this in the example that we did by hand.
3. If C(pi, x, out) = c or \top for all i, then C(s, x, in) = c. If we come along a path where x=c, this is trivial to see. For a path with \top, it means that this never executes and so it can be ignored.
4. If C(pi, x, out) = \top for all i, then C(s, x, in) = \top. Every predecessor is unreachable, and so x itself is unreachable.

Rules 1-4 relate the out of one statement to the in of the next statement. Now we need rules relating the in of a statement to the out of the same statement. These rules form the meet operator.

Our next set of rules will relate the values at the in of a statement to its out.

1. If C(s,x,in)=\top then C(s,x,out)=\top, for all s. Let's call this rule 5.
2. C(x:=k, x, out) = k if k is a constant. This rule (rule 6) has lower priority than the previous rule (rule 5). i.e., this rule applies only if C(x:=k, x, in) = k2 or \bot.
3. C(x:=f(...), x, out) = \bot if the value of x cannot be determined to be a constant after this statement.
4. C(y:=..., x, out) = C(y:=..., x, in) if x<>y

X := 3
Y := W+X
Z := 2 * X
X := Y + V

Two observations:

• For rule 6, if C(x:=k, x, in) is \top, then we prefer the out value to be \top (over k). This is because \top has more information than k For example, meet of \top with k2 results in k2, whereas a meet of k with k2 results in \bot.
• For rule 7, the characterisation of x:=f(...) can improve the precision of the analysis (thus increasing optimization opportunity):
  • For example, we can make this more precise by saying that if f is a function of x, and the in value of x is a constant k, then the out value is f(k), e.g., we did this for X := 2*X in the example program above.
  • We can make this more precise if we do the constant information analysis for all variables at once, in which case we will track the same values (\top,k,\bot) for each variable --- we can improve this slightly by tracking \top only once, instead of per variable. This makes the analysis more precise, e.g., if the statement is z := f(x,y), and we know that the in value maps both x and y to constants (say k1 and k2), then the out value should map z to f(k1,k2).
  • This can be made arbitrarily more precise, e.g., have a transfer function for if x==3 goto L create a constant value for x at the incoming edge of L. In general, only syntactic determinations are made. As we said earlier, solving this problem with full precision is undecidable.

Algorithm

• For every entry s to the program, set C(s,x,in) = \bot
• For every other statement (non-entry), set C(s,x,in)=C(s,x,out)=\top.
• Repeat until all points satisfy rules 1-8:
  • Pick s not satisfying 1-8 and update using the appropriate rule.

Let's run the algorithm on this example:

BB1:
               === X = \bot (at this program point)
X := 3
               === X = \top
B > 0 then goto BB2
         else goto BB3
              === X = \top

BB2:
             ==== X = \top
Y := Z + W
             ==== X = \top
X := 4
             ==== X = \top

BB3:
             ==== X = \top
Y := 0
             ==== X = \top

BB4:
             ==== X = \bot
A := 2 * X

Some guarantees: the fixed-point solution will satisfy the equations at each program point.

Some un-answered questions: what is the guarantee that this analysis will converge? What is the guarantee that this algorithm will result in the best possible solution for this system of solutions?

Notice that the execution of a dataflow analysis proceeds very similar to program execution, e.g., we take loop edges multiple times, etc. The primary difference is that unlike regular execution where the value of a variable can change from a constant k1 to another constant k2 (e.g., due to x := x 1), in a dataflow analysis, the value can only move down, e.g., from k1 to \bottom.

Analysis of loops

BB1:
X := 3
B > 0 then goto BB2
         else goto BB3

BB2:
Y := Z + W
X := 4

BB3:
Y := 0

BB4:
A := 2 * X

Now, when we are computing C(BB3,x,in), we need to know the value of C(BB4,x,out) and in turn C(BB4, x, in) and so on... And we are in a loop (we get back to C(BB3,x,in)).

• Consider the statement Y:=0
• To compute whether X is constant at this point, we need to know whether X is constant at the two predecessors
  • X:=3
  • A:=2*X
• But info for A:=2*X depends on its predecessors including Y:=0!

Because of cycles, all points must have values at all times.

Intuitively, assigning some initial value allows the analysis to break cycles.

The initial value \top means "So far as we know, control never reaches this point". The initial value is not what is expected at the end but allows us to get going (by breaking the cycle).

Analyzing the example: if we run the algorithm assuming that C(BB4,x,out) is \top, then we will be able to reach a fixed-point solution.

Orderings

We can simplify the presentation of the analysis by ordering the (abstract) values.

\bot < c < \top

      \top
  /   / | \  \
... -1  0  1 ...
  \   \ | /  /
      \bot

With orderings defined:

• \top is the greatest value, \bot is the least.
  • All constants are in between and incomparable.
• Let glb be the greatest-lower bound in this ordering:
  • glb(\top, 1) = 1
  • glb(\bot, \top) = \bot
  • glb(\bot, 1) = \bot
  • glb(1, 2) = \bot
• Rules 1-4 can be written using glb:
  • C(s,x,in) = glb{C(p,x,out) | p is a predecessor of s}.

Simply saying "repeat until nothing changes" doesn't guarantee that eventually nothing changes (it could oscillate forever for example). The use of glb explains why the algorithm terminates:

• Values start as \top can only decrease.
• \top can change to a constant, and a constant to \bot.
• Thus, C(s,x,_) (for every statement, for every variable) can change at most twice.

It can be proven using coinduction that the value at a program point can only decrease. Pick an arbitrary program point; assuming this property of non-increasing values holds for all other program points, we show that it holds for the picked program point. The idea is that both the meet operator and the transfer function map lower input values to lower output values.

Also, we maintain the invariant that the value at any intermediate point of the algorithm is always greater than the best solution value. This is because we initialize all values to \top. Also, we relax minimally --- assuming this invariant is true for the predecessors, it is guaranteed to be true for the successor.

Thus the constant propagation algorithm is linear in program size. Number of steps per variable = Number of C(...) values computed * 2 = Number of program statements * 4 (two C values per program statement, in and out).

Liveness analysis

BB1:
X := 3
B > 0 then goto BB2
         else goto BB3

BB2:
Y := Z + W

BB3:
Y := 0

BB4:
A := 2 * 3

Defining what is used (live) and what is not used (dead).

X := 3
X := 4
Y := X

• The first value of x is dead (never used).
• The second value of x is live (may be used).
• Liveness is an important concept.

A variable x is live at statement s if

• There exists a statement s' that uses x.
• There is a path from s to s'.
• That path has no intervening assignment to x.

A statement x:=... is dead code if x is dead after the assignment. Dead statements can be eliminated from the program. But we need liveness information first . . .

We can express liveness in terms of information transferred between adjacent statements, just as in constant propagation.

Liveness is simpler than constant propagation, since it is a boolean property (true or false).

Here the set of values is False (definitely not live) and True (may be live). False > True. The glb function is the boolean-OR function in this set of values. Notice that we did not need separate \top and \bottom values, because there already exists a value that is greater or equal than all other values (False) and there already exists a value that is smaller or equal than all other values (True), so we do not need to introduce extra values.

 <------ p ------->
         |
         |
         v

Rule 2: s: ... := f(x). L(s,x,in) = true if s refers to x on the RHS.

Rule 3: s: x := e where e does not refer to x. L(x:=e,x,in)=false if e does not refer to x. x is dead before an assignment to x because the current value of x at that point will not be used in the future.

Rule 4: L(s,x,in) = L(s,x,out) if s does not refer to x.

Algorithm

1. Let all L(...) = false initially.
2. Repeat until all statements s satisfy rules 1-4
   • Pick s where one of 1-4 does not hold and update using the appropriate rule.

Example:

    ==== L(x) = false
x := 0
    ==== L(x) = false
while (x!= 10) {
		==== L(x) = false -> true (step 1)
  x = x + 1;
    ==== L(x) = false
}
    ==== L(x) = false
return;
    ==== L(x) = false

    ==== L(x) = false
x := 0
		==== L(x) = false -> true (step 3)
while (x!= 10) {
		==== L(x) = false -> true (step 1)
  x = x + 1;
    ==== L(x) = false -> true (step 2)
}
    ==== L(x) = false
return;
    ==== L(x) = false

• A value can change from false to true, but not the other way round. So we use the ordering false > true
• Each value can change only once, so termination is guaranteed.
• Once the analysis is computed, it is simple to eliminate dead code.

Notice that information flowed in the forward direction (in the direction of the program execution) for constant propagation but flowed in the reverse direction (against the direction of the program execution) for liveness analysis. The former types of analyses are called forward dataflow analyses. The latter types of analyses are called backward dataflow analyses.

How to decide the direction? If the value being computed depends on what may happen in the future (e.g., can the value get used in the future), then we need a backward analysis; if the value being computed depends on what may have happened in the past (e.g., was the register definitely assigned to a constant value in the past), then we need a forward analysis.

Some other analyses that can be modeled as dataflow analyses

• Common-subexpression elimination: maintain a set of available expressions of the form x = op(y,z) at each statement. If we see another expression of the type u = op(y,z), replace by u=x. Available expressions is a forward data-flow analysis. A value is available at a program location only if it is available at all the predecessor program locations, i.e., the available expressions at a statement is the intersection of the available expressions at the predecessors. In other words, the meet operator is intersection. Works best with single-assignment form because can maintain a larger set of available expressions.
• Copy-propagation: an analysis similar to available-expressions, except only for expressions that are of the form x=y. The main difference is in the transformation (substituting variable names vs. substituting expressions by variable names).

Available expressions : single expression/register at a time

Direction: Forward

Set of values: Available/TRUE (y+z is available in x) or NotAvailable/FALSE (y+z is not available in x).

Ordering: FALSE is less than TRUE

• Thus, meet is logical AND

Transfer functions: For x := y+z, the out value is TRUE; for x:=f(...), or y:=g(..), or z:=h(..), the out value is FALSE; for all other instructions, the out value is the same as in value.

Initialization: initialize the value at entry to FALSE. initialize all other values (optimistically) to TRUE.

Copy propagation: single register at a time

At every program point, compute whether register x definitely contains a copy of another register.

Direction: forward

Set of values: \top (not yet reached), registers r1, r2, ..., rN, \bottom.

Ordering: \top < r1,r2,r3,...,rN < \bottom

Transfer functions: For x := w, out is w; for w := ... and in=w, out is \bottom; for x := f(...), out is \bottom, for all other statements, out is the same as in.

Initialization: \bottom at entry, \top at all other program points.

Available expressions: single register at a time

At every program point, compute whether register x definitely contains an expression.

Direction: forward

Set of values: \top (not yet reached), expressions e1, e2, ..., eN, \bottom.

Ordering: \top < e1,e2,e3,...,rN < \bottom (there could be an infinite number of expressions, and that's ok)

Transfer functions: For x := f(...), out is f(...); for w := ... and in contains w, out is \bottom, for all other statements, out is the same as in.

Initialization: \bottom at entry, \top at all other program points.