Class 32: Liveness Analysis

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)
  until no changes are made
  

• 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;