Register allocation is the most important optimization, since it allows fast hardware registers to be used in place of relatively slow memory. The optimization replaces temporaries (abstract registers) with real registers from the instruction set architecture, so that they do not have to be placed on the stack. The key to successful register allocation is to share the real registers across multiple temporaries.
A temporary variable is live at a point in the program if its value may be needed. For example, in the following Xi code, the comments on the right show the live variables after each statement.
{
// live: a, e
b:int = a + 2; // live: b, e
c:int = b*b; // live: c, e
d:int = c+e; // live: d
return d; // live: ∅
}
Since there are only two live variables at any point in the program, this code could be implemented with only two registers. In particular, the variables a, b, c, and d are never live at the same time, so they could all be stored in the same register, with the variable e occupying a second register. For example, the following x86 code would be a possible translation:
add rax, 2 // b = a + 2 imul rax, rax // c = b * b add rax, rcx // d = c + e ret // return d
Live variable analysis is the job of computing these live sets, for use in register allocation or other optimizations. Live sets are computed for each program point, meaning between statements or, equivalently on edges in the control-flow graph.
Perhaps surprisingly, we cannot precisely compute live variables. To see why, consider the following code:
x: int = y; // is x live here? f(); return x;
It might seem obvious that x is live at the program point following the
first statement, but suppose that the function call f() never
returns. In that case the value of x is not needed. In other words,
x is live if f() halts. Since the halting problem
is undecidable, so is the live variable problem, at least if we want precise
results.
In fact, all interesting facts about programs (by a reasonable definition of “interesting”) are undecidable for similar reasons. Therefore, when we do program analysis, we are always approximating facts about programs. The key is that the approximation must be conservative so that optimizations do not break the program. In the case of live variable analysis, being conservative means that the analysis overestimates the set of live variables.
Dataflow analysis is a technique for computing information, such as live variables, about a program expressed as a control-flow graph (CFG). The information is computed for each edge in the control-flow graph: that is, at each program point. For live variable analysis, we want liveness to be computed with fine granularity, so the nodes in the CFG are individual statements. For register allocation, the statements in question are instructions.
Although live variable analysis for register allocation is done on abstract assembly. most of the analyses we will explore will be done on IR. Therefore, we introduce a common language for expressing CFGs.
| CFG node | IR equivalent | Possible abstract assembly | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| x ← e | \(\textit{MOVE}(x, e) \) | mov x, eadd x, ...
| |||||||||
| [e1] ← e2 | \(\textit{MOVE}(\textit{MEM}(e_1), e_2)\) | mov [e1], e2
|
The CFG language includes variables, which at the IR level correspond to temporaries, and at the abstract assembly level correspond to abstract registers.
Expressions e in the CFG language denote pure expression built from variables, constants, binary operators \(OP\), and memory references:
\begin{align*} e ::= k \mid x \mid e_1~OP~e_2 \mid [ e_1 ] \end{align*}To describe live variable analysis succinctly, it is handy to define two properties of CFG nodes. For a node n, we use the notation use[n] to denote the set of variables that are used (that is, read) at node n. The notation def[n] denotes the set of variables that are modified (written) at node n. For an expression e, we denote the set of variables appearing in the expression as vars[e].
For example:
Given these definitions, we can summarize the action of use and def in table form.
| Node n | use[n] | def[n] |
|---|---|---|
| x←e | vars[e] | {x} |
| [e1]←e2 | vars[e1] ∪ vars[e2] | ∅ |
| if e | vars[e] | ∅ |
| start | ∅ | ∅ |
| return e | vars[e] | ∅ |
A variable is live on edge e if there exists some path through the CFG from the edge to a node where the variable is used, and no node on the path modified the value of the variable.
This definition leads naturally to an algorithm for computing liveness:
Backtracing algorithm
To compute the nodes where a variable is live, traverse all simple paths in the CFG that start from a use of the variable and that do not include a def.
This algorithm is clearly correct but unfortunately requires traversing an exponential number of paths. So we would like a more efficient algorithm that computes the same result.
The key idea of dataflow analysis is to set up local equations at each CFG node such that solving the the equations computes the desired information for each program point. In general, for a node n, we write in[n] to represent facts that are true on all in-edges to the node, and out[n] to represent facts true on all out-edges. For live variable analysis, in[n] is the set of variables live on entry to a node (we say that such variables are live-in) and out[n] is the set of variable live on exit (that is, live-out).
Consider a CFG node containing the single statement (a ← b + c). A variable is live-out from this node if it is live-in on any successor node. In other words, we can compute out[n] by taking a union: \[ out[n] = \bigcup_{n'≻n} in[n'] \]
The variables b and c are clearly live-in to this node since the node uses them. However, variables that are live-out from the node must also be live-in to this node too — except for the variable a, since any previous value of a is overwritten by this node.
\[ in[n] = \{b, c\} ∪ (out[n] - \{a\}) \]We can extend this reasoning to nodes more generally. For any node, the above equation for \(out[n]\) holds; the equation for \(in[n]\) uses \(use[n]\) and \(def[n]\): \[ in[n] = use[n] ∪ (out[n] - \mathit{def}\,[n]) \]
We now have a system of equations relating \(in[n]\) and \(out[n]\) for the various nodes \(n\). It turns out that we can solve these equations straightforwardly by iteratively updating them until all equations are solved.
Notice that when an equation is satisfied, performing the assignment has no effect. Therefore, when the algorithm terminates, all equations are satisfied. How do we know that the algorithm terminates? Consider how the sets \(in[n]\) and \(out[n]\) change as the algorithm runs. These sets are initially empty, so they can only change in the first iteration by having new elements added to them. But increasing these sets can only cause the right-hand side of the equations to increase, so on the second iteration, the sets can only change by adding new elements. Inductively, on each iteration, if any of the sets change, it is because they acquired new elements. Given that the program contains \(|V|\) variables, the sets \(in[n]\) can change at most \(|V|\) times. For the algorithm not to terminate, at least one node must have its value \(in[n]\) change. Assuming there are \(|N|\) nodes, this implies that the loop can run at most \(|N|\cdot |V|\) times, so the algorithm terminates in polynomial time with a solution to the dataflow equations.
Click the play button to see the steps of finding live variables for the CFG shown. Notice that the algorithm works no matter what order we choose nodes in, but for this example the nodes are chosen in an order that propagates information through the CFG fairly rapidly. Still, two iterations are required to arrive at a solution.