Class 32: Liveness Analysis

Back to Translating Procedure Calls. On to Register Allocation.

Held Monday, November 18, 2002

Summary

Today we consider techniques for determining how long a variable remains useful in a program. Such knowledge can help us generate more efficient code.

Notes

• Barring unforeseen circmstances, we will have lab tomorrow.
• Of course, given that my laptop crashed over the weekend, unforeseen circumstances are a possibility.
• Please try to get your parsers to me on Wednesday so that I may take them on my trip for grading.
• I'm teaching algorithms today and Wednesday, and won't be in my office during those times.
• Warning: I may have to refer to my notes today.

Overview

• Context: Why consider liveness
• The basics of liveness analysis
• Some theoretical issues
• Some practical issues
• Some examples

Context

• We now know how to generate something fairly close to assembly code
• We use an infinite number of temporaries.
• We generalize or approximate many instructions.
• Where might we go from here?
• We need to go from a large number of temporaries to a smaller number of temporaries (or even registers).
• We might want to improve memory usage.
• We might want to improve the code.
• In going to a smaller number of temporaries, we may need to temporarily store some values on the stack and load them into registers later.
• We can ground some of these choices by understanding when and how long registers are needed.
• Generalizing, we need to understand how long variables remain active in a program.
• Today, we'll look at liveness analysis: how one figures out how long a variable or termporary is needed within a program.
• We'll continue later this week with register allocation.

Liveness Analysis

• We can save space in memory and registers if we can determine when two variables (or termporaries) are not used at the same time.
• If both variables are stored in registers, we only need one register for the two.
• If both variables are stored in memory, we only need one memory location for the two.
• If one variable is stored in memory and the other in a register, we can safely use the memory location to store the register when it needs to be swapped out.
• To do this type of analysis, we need to define attributes of used, needed, defined, and live for variables.
• The key attribute we care about is Do we need to remember the value assigned to this variable (temporary) for later statements?
• It turns out that it is theoretically impossible to answer that question for an arbitrary program.
• Can you explain why? (It relates to the halting problem.)
• We will instead say Is it possible, in some path through the program, that the current value assigned to this variable will be used in a later statement?
• A variable that has this property is live.
• Note that liveness analysis can also be used for other compiler optimizations.
• If we know that no variables are used after a recursive function call, we may be more able to do tail recursion removal.
• If we know that a variable is used/needed before it is defined, then we can report an error (as Java does).
• If we know that a variable is never used after it is defined, then we can discard the statement that defines it.
• Note that we can apply this analysis to assembly code, high-level code, or even blocks of code. All that we need is the ability to talk about the variables that are used and defined within each statement.

A Theory of Liveness

• We'll look at liveness in terms of relationships between statements.
• We'll work in terms of sets:
• `in`: the variables needed/live just before the statement;
• `out`: the variables needed/live after the statement;
• `use`: the variables used within the statement;
• `def`: the variables defined by the statement;
• `succ`: the successors of a statement; and
• `pred`: the predecessors of a statement.
• We note that a variable is needed by a statement if it is used by that statement.
• `use(x)` is a subset of `in(x)`
• We note that a variable is needed after a statement if it is needed in any subsequent statements.
• `out(x)` is a superset of `in(y)` for each `y` that can follow `x`.
• We note that a variable is needed at the beginning of a statement if it is used after the statement and not defined in the statement.
• `in(x)` is a superset of `out(x)-def(x)`.
• There are no other times that variables are needed.
• Putting it together
```in(x) = use(x) union (out(x)-def(x))
out(x) = Union(in(y) s.t. y in succ(x))
```
• In the abstract, we want to solve these mutually recursive equations.
• It turns out that there are many possible solutions. Consider the program
```s0: a := 0
s1: a := b + c
s2: b := a
s3: end
```
• Then
```use(s0) = { }
use(s1) = { b, c }
use(s2) = { a }
use(s3) = { }
def(s0) = { a }
def(s1) = { a }
def(s2) = { b }
def(s3) = { }
succ(s0) = { s1 }
succ(s1) = { s2 }
succ(s2) = { s3 }
succ(s3) = { }
```
• What definitions of `in` and `out` satisfy the equations given earlier?
• Many
• Here's a solution that uses a few new variables. It may look a little odd, but you'll see that it satisifies the equations.
```in(s0) = { q,b,c }
out(s0) = { q,b,c }
in(s1) = { q,b,c }
out(s1) = { q,a,b,c }
in(s2) = { q,a,c }
out(s2) = { q,a,b,c }
in(s3) = { q,a,b,c }
```
• Here's a more compact solution
```in(s0) = { b,c }
out(s0) = { b,c }
in(s1) = { b,c }
out(s1) = { a }
in(s2) = { a }
out(s2) = { }
in(s3) = { }
```
• Given the possibility of multiple (in fact, infinite) solutions to the equations, how do we choose one?
• We choose the smallest one. This is typically called the least fixed point of the equations.
• We use an algorithm that builds the smallest one.

Practice

• What algorithm might we use to compute `in` and `out`?
• It turns out that a relatively straightforward one will work. In this algorithm, we work from back to front.
```compute used and def for each statement
// the prior step may be done during translation
foreach statement, s
in(s) = used(s)
repeat
foreach statement s
in(s) = in(s) + (out(s)-def(s))
foreach predecessor, p, of s
out(p) = out(p) + in(s)
```
• We'll run this algorithm on some sample code
• A simple For loop.
```for i := 1 to 10 do
begin
writeln(i);
end;
```
• A less-simple While loop
```y := 1;
while (x <= 10) do
begin
x := x + 1;
y := x;
end
writeln(y);
```
• A similer Repeat loop
```y := 1;
repeat
x := x + 1;
y := x;
until (x > 10);
writeln(y);
```
• Here's a hard question: What should we do about function and procedure calls? That is, what's `used` for those calls?
• Are all parameters used?
• Can other variables also be used?
• Consider
```begin
x := 10;
y := 5;
proc(y);
end.
```
• Are there cases in which `y` is not needed?
• Are there cases in which `x` is needed?
• More examples
• A procedure body
```procedure foo(x: integer);
begin
x := x + 1;
writeln(x);
x := x - 1;
end;
```
• A similar procedure body.
```procedure bar(var x: integer);
begin
x := x + 1;
writeln(x);
x := x - 1;
end;
```

History

Thursday, 29 August 2002 [Samuel A. Rebelsky]

• First version, based somewhat on outlines from CS362 2001S.

Monday, 18 November 2002 [Samuel A. Rebelsky]

• Updated slightly.

Back to Translating Procedure Calls. On to Register Allocation.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Dec 6 10:38:33 2002.
The source to the document was last modified on Mon Nov 18 10:38:24 2002.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2002F/Outlines/outline.32.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Glimmer Labs: The Grinnell Laboratory for Interactive Multimedia Experimentation & Research
glimmer@grinnell.edu