Chapter 10
LIVENESS ANALYSIS

OVERVIEW

Have not yet targeted an architecture.

Have generated TEMP as needed.

Goal is to determine fewest TEMPs necessary by eliminating and reusing where possible.

live - a variable that holds a value that may be needed in the future.

Discovering live variables is liveness analysis

Control-flow graph used in analysis, such graphs consist of nodes and directed edges

nodes - statements of program

edges - if statement x can be followed by statement y there is an edge from x to y.

Example

Graph 10-1 nodes and edges

A variable is live if current value used in future.
Analyze from future to the past

Nodes	Edges
1,2,3,4,5,6	1®2 2®3 3®4 4®5 5®2, 5®6

used at 4, b live on 3®4.
used at 3, b live on 2®3
defined at 2
dead on 1®2, 5®2

live 1®2
live 4®5®2
dead 2®3®4

live at 1, block entry
defined at 3
live throughout

1®2

4®5

5®2

2®3

3®4

1®2

2®3

3®4

4®5

5®2

5®6

Analysis result: a and b liveness do not intersect, can use 1 register

10.1 SOLUTION OF DATAFLOW EQUATIONS

Flow-graph terminology

out-edges - lead from node to successor node, 5®2 and 5®6 are out-edges of 5

in-edge - come from a predecessor node, 5®2 is an in-edge of 2

succ[n] - set of all successors of n, succ[5] = {2,6}

pred[n] - set of all predecessors of n, pred[2] = {1,5}

use(n) - set of all variables used (right-side) at a node, use(3) = {b,c}

use(v) - set of graph nodes that use a variable, use(b)={3,4}

def(n) - set of variables defined by a graph node, def(4) = {a}

def(v) - set of graph nodes that define a variable, def(a) = {1,4}

liveness - variable live on edge if directed path from edge to a use that does not go through any def; b live on 2®3 and 3®4

live-in - at a node if live on any in-edges

live-out - at a node if live on any out-edges

Exercise

What is succ[3]? pred[3]?

Variables in: use(3)? def(3)?

Nodes in: use(b)? def(b)?

What variables are live-in and live-out at nodes 1, 2, 5?

a
1®2

4®5

5®2

b

2®3

3®4

c
1®2

2®3

3®4

4®5

5®2

5®6

CALCULATION OF LIVENESS

Liveness, live-in and live-out, calculated from use, def and succ

Variable is:

live-in at node n if variable in use[n]
use[2]={a}, a is live-in at 2
use[3]={c,b} c and b are live-in at 3
live-out at all nodes m in pred[n] if variable live-in at n
pred[2]={1,5}, a is live-out at 1 and 5
pred[3]={2}, c is live-out at 2 since live-in at 3
live-in at node n if variable live-out at n and not in def[n].
def[2] = {b}, c live-out at 2 so live-in at 2
def[1] = {a}, c is live-out at node 1 by rule 2., c is live-in at node 1 by rule 3.

Example

s0: a := 0
s1: a := b + c
s2: b := a + b
s3: end use(s0) = { }
use(s1) = { b, c }
use(s2) = { a, b }
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?
Here's one solution by inspection:

in(s0) = { b,c }
in(s1) = { b,c }
in(s2) = { a,b }
in(s3) = { } out(s0) = { b,c }
out(s1) = { a,b }
out(s2) = { }

Here's another solution that uses a few new variables. It looks odd, but it satisfies the equations.

in(s0) = { q,b,c }
in(s1) = { q,b,c }
in(s2) = { q,a,c }
in(s3) = { q,a,b,c } out(s0) = { q,b,c }
out(s1) = { q,a,b,c }
out(s2) = { q,a,b,c }

Exercise - Why is the first solution preferable?

Exercise - Give use[n], def[n] and succ[n] for each node n.

ALGORITHM 10.4

Iterative form of 10.3 that calculates in (live-in) and out (live-out) of each variable at each node, stopping iteration when converges to solution of no change to in or out.

TABLE 10.5 column 1 in and out are used in column 2, etc. terminating when no change. Result of incrementing n

Incrementing n results in the calculation flow following edge 1®2®3

But in[4] is computed from out[4] and out[3] is computed from in[4]

The in and out sets should be computed in order of out[4]®in[4]®out[3]®in[3]

TABLE 10.6 reverses the order to fit the flow of liveness backward along control-flow arrows.

succ[1]={2}
succ[2]={3}
succ[3]={4}
succ[4]={5}
succ[5]={2,6}
succ[6]={}

Exercise - Using use, def and succ calculate the first complete repetition for TABLE 10.5 from ALGORITHM 10.4; the results should agree with 1st column.

Exercise

Why are we interested in live-out variables at each node?

Examine the last column in TABLE 10.5 and 10.6:

Are they the same?

What is the implication of the in and out columns?

Basic blocks - Recall that basic blocks have no internal labels or jumps. Nodes can be merged to produce a graph with fewer nodes.

One variable at a time - ALGORITHM 10.4 calculates liveness for all variables in parallel. Liveness of individual variables can be calculated by:

start at each use node in flow-graph for variable

trace back via predecessor edges (using depth-first search) noting liveness of variable

stop when def of node contains variable

Exercise - Sketch the above steps to determine the liveness of b.

REPRESENTATION OF SETS

Dataflow equations (in, out, etc.) require set representation.

Sorted lists of variables - 6 lists for each set. Union done by merging lists and eliminating duplicates.

arrays of bits - requires 6 3-bit entry for each in, out, def, use set. pred and succ (assuming can branch to any other node) require 6 6-bit entry). Union done by bitwise OR.

HashSet class in Java is a convenient solution.

Exercise

How many bits in general to represent def for n nodes and v variables?

Give a bit representation of def, use and succ for n=1, 2, 3.

Bitwise OR implements set union. For n=1, 2, 3 compute the first iteration of ALGORITHM 10.4 using bit representation.

TIME COMPLEXITY

For N nodes and N variables

Each for iterates for N nodes.

Each union is O(N) for N variables; consider merging two lists of length N

for is then O(N²)

Each repeat iteration must add something to in or out sets. Each of N in and out sets could have at most N variables each, if only one in or out variable changes per repeat then 2N² the maximum or O(N²).

Worst case is then O(N⁴).

Ordering usually reduces repeat to 2 or 3 so algorithm runs in O(N²)

LEAST FIXED POINTS

Solutions to EQUATION 10.3 are conservative, may include live-out variables that are not used

Including extra variables in solution may prevent reallocating registers but will compute the right answer.

TABLE 10.7 illustrates 3 possible solutions to EQUATION 10.3

X - is least solution

Y - includes variable d not used in program fragment but satisfies EQUATION 10.3

Z - fails to satisfy EQUATION 10.3; indicates b and c are never live at same time.

ALGORITHM 10.4 computes the least fixed point

Exercise - Which registers are never live at the same time in solution X above?

STATIC VS. DYNAMIC LIVENESS

GRAPH 10.8

b*b positive

c ³ b always true

node 4 never reached

a not used after node 2

a not live-out of node 2

EQUATIONS 10.3 say a live-in at node 4 and therefore live-out at nodes 2 and 3

In general can not determine control flow in all cases

Theorem

For program P and input X, no program H(P, X) that halts itself can return true if P(X) halts and false if P(X) fails to halt (infinite-loop).

Proof

Suppose H exists. Construct:

F(Y) = if H(Y,Y) then while true; else true;

If F(F) halts then H(F,F) is true and F(F) does not halt: while true. Otherwise, if F(F) does not halt H(F,F) is false so returns true but F(F) does not halt, so never returns true. By contradiction, H cannot exist.

Corollary

H'(X,L) for program X and label L in X, cannot determine if L is ever reached on execution of X.

Proof

From H' construct H. For program to test for halting, let L be end of program and replace halts with goto L.

INTERFERENCE GRAPHS

Interference - condition that prevents allocation of two variables to same register (e.g. live-out of same node)

Most common interference - overlapping live ranges; when live at same node, require different registers

Other - when instruction must address a specific register. Example: Push/Pop only addresses eSp.

Figure below shows ac and bc interfere.

Special treatment of MOVE instructions

Any non-MOVE instruction that defines a, where live-out variables are b₁,..., b_j, add interference edges (a, b₁), ..., (a, b_j)

At MOVE a¬c where variables b₁,..., b_j are live-out, add interference edges (a, b₁), ..., (a, b_j) for any b_i that is not the same as c.
MOVE a¬c deserves special treatment because a and c have the same value and should be the same register. Consider:

a¬3            ; a live
c¬4            ; c live
:
x¬ ...c...
:
y¬ ...a...     ; a and c interfere c¬4            ; c live
a¬c            ; a live
:
x¬ ...c...
:
y¬ ...a...     ; a and do not interfere c¬4            ; c live
a¬c            ; a live
:
x¬ ...c...
:
y¬ ...a...
:
c¬ x+y

On the left, adding an interference edge (a,c) is correct because a and c need separate registers.

In middle, adding an interference edge (a,c) is wrong because a and c do not need separate registers.

Exercise - Is an interference edge needed for the right example?

Interference graph computation

for each node in the flow graph
for each def temporary at that node
     for each live out temporary at that node
         addEdge(def, out);
         addEdge(out, def);

10.2 LIVENESS IN THE MiniJava COMPILER

Two parts:

Construct the control-flow graph from a given instruction list. Each instruction maintains a list of destination registers (defined) and source registers (used).
For example, in the MiniJava®IR®Mips instruction®control-flow graph translation:

MiniJava

IR

Mips InstrList
x=t14, y=t15, max=t16

Control-flow

max = x;
if ( y > x )

   max = y;

MOVE(MAX, X)

CJUMP(CJUMP.GT, Y, X,T,F)

LABEL(F)

MOVE(MAX, Y)

LABEL(T)

MOVE[ move `d0 `s0][t16][t14]

OPER[ bgt `s0 `s1 T][][t15 t14 ][TF]

LABEL[F:][F]

MOVE[ move `d0 `s0][t16][t15]

LABEL[T:][T]

1: t16 <= t14 ; goto 2
2: <- t14 t15 ; goto 3 5
3: <-             ; goto 4
4: t16 <= t15 ; goto 5
5: <-             ; goto

1: t16 <= t14 implies use[1] = {t14}, def[1]={t16}

Control-flow graph construction

Each instruction is a node in the control-flow graph.

A directed-edge is added from non-branching node to the next instruction node.

A directed-edge is added from a branching node to each possible target instruction.

The graphical control-flow graph and AssemFlowGraph.java is then:

Instruction list from Munch

MOVE[ move `d0 `s0][t16][t14]
OPER[ bgt `s0 `s1 T][][t14 t15 ][TF]
LABEL[F:][F]
MOVE[ move `d0 `s0][t16][t15]
LABEL[T:][T]

Flow graph from AssemFlowGraph

package AssemFlowGraph;
import java.util.Iterator;

public class AssemFlowGraph extends FlowGraph {
java.util.Dictionary ht;

public Temp.Temp[] def(Graph.Node node) {
    return instr(node).def();
}
public Temp.Temp[] use(Graph.Node node) {
    return instr(node).use();
}
public boolean isMove(Graph.Node node) {
    return instr(node) instanceof Assem.MOVE;
}
public Assem.Instr instr( Graph.Node n ) {
    return (Assem.Instr)ht.get(n);
}

public AssemFlowGraph(Assem.InstrList instrs) {
    ht=new java.util.Hashtable();
    java.util.Dictionary l2n=new java.util.Hashtable();

    // Relate instructions to nodes in AssemFlowGraph
    for (Assem.InstrList p=instrs; p!=null; p=p.tail) {
      Graph.Node n=new Graph.Node(this);
      ht.put(n, p.head);
      if (p.head instanceof Assem.LABEL)
            l2n.put(((Assem.LABEL)p.head).label, n);
    }
    // Add edges from each branch instruction node to target node(s)
    for (Graph.NodeList p=nodes(); p!=null; p=p.tail) {
      Graph.Node n=p.head;
      Assem.Targets jumps = (Assem.Targets) instr(n).jumps();
      if (jumps==null && p.tail!=null) {
            addEdge(n, p.tail.head);    // Fall through with edge
      }                                           // to next instruction
      else if (jumps!=null) {             // Jumps - Edge to target label node
            Iterator l = jumps.labels.iterator();
            while( l.hasNext())
            addEdge(n, (Graph.Node)l2n.get(l.next()));
      }
    }
}
}

Control-flow information of def, use and succ are used as input to perform liveness analysis. The implementation follows the texts iterative Algorithm 10.4 using input derived from munching IR into Mips code. The output consists of:

Assem of Mips code

Registers of each instruction, def and use

Live in and out until iteration is unchanged

Liveness interval indicating instructions where register is live

Interference graph indicating register interference; the interference table is not generated.

Note that in the following examples, the final operation is essentially MOVE(c, c); added to have c live out at the end of liveness analysis. The interval of t33 is [2,2] indicating that it could be eliminated and a little more analysis shows that it could be replaced by t3.

t1=0
t2=t1
t3=t3+t2
t3=t3

IR
MOVE(t1,CONST(0))
MOVE(t2,t1)
MOVE(t3,
BINOP(+,t3,t2))
MOVE(t3,t3)

Interference graph
t1: t3 t1
t3: t3 t2 t1
t2: t2 t3
t33: t33

Mips
MOVE[   move `d0 `s0][t1][t0]
MOVE[   move `d0 `s0][t2][t1]
OPER[add `d0 `s0 `s1][t33 ][t3 t2 ][]
MOVE[   move `d0 `s0][t3][t33]
MOVE[   move `d0 `s0][t3][t3]

Register use
0: t1 <= t0 ; goto 1
1: t2 <= t1 ; goto 2
2: t33 <- t3 t2 ; goto 3
3: t3 <= t33 ; goto 4
4: t3 <= t3 ; goto

                                Interference
Liveness interval         t1 t2 t3 t33
t1 [0,0]                 t1          x
t2 [1,1]                 t2          x
t3 [0,3]                 t3   x x
t33 [2,2]               t33

use
0:{ t0 }
1:{ t1 }
2:{ t2 t3 }
3:{ t33 }
4:{ t3 }

def
0:{ t1 }
  1:{ t2 }
  2:{ t33 }
  3:{ t3 }
  4:{ t3 }

in
0:{ t0 }
1:{ t1 }
2:{ t2 t3 }
3:{ t33 }
4:{ t3 }

out
0:{ t1 }
1:{ t2 t3 }
2:{ t33 }
3:{ t3 }
4:{ }

in
0:{ t0 }
1:{ t1 t3 }
2:{ t2 t3 }
3:{ t33 }
4:{ t3 }

out
0:{ t1 t3 }
1:{ t2 t3 }
2:{ t33 }
3:{ t3 }
4:{ }

Same as above but Labels and Jumps have been added to show effect on liveness interval. The interval of t33 is [3,3] indicating that it could be eliminated and a little more analysis shows that it could be replaced by t3.

t1=0
t2=t1
F:
t3=t3+t2
goto F:
t3=t3

IR
MOVE(t1,CONST(0))
MOVE(t2,t1)
LABEL(F)
MOVE(t3,
BINOP(+,t3,t2))
JUMP(F)
MOVE(t3,t3)

Interference graph
t1: t3 t1
t3: t3 t2 t1
t2: t33 t3 t2
t33: t33 t2

Mips
MOVE[   move `d0 `s0][t1][t0]
MOVE[   move `d0 `s0][t2][t1]
LABEL[F:][F]
OPER[add `d0 `s0 `s1][t33 ][t3 t2 ][]
MOVE[   move `d0 `s0][t3][t33]
OPER[   b F][][][F]
MOVE[   move `d0 `s0][t3][t3]

Register use
0: t1 <= t0 ; goto 1
1: t2 <= t1 ; goto 2
2: <- ; goto 3
3: t33 <- t3 t2 ; goto 4
4: t3 <= t33 ; goto 5
5: <- ; goto 2
6: t3 <= t3 ; goto
                                Interference
Liveness interval         t1 t2 t3 t33
t1   [0,0]              t1           x
t2   [1,5]              t2           x     x
t3   [0,5]              t3   x   x
t33 [3,3]              t33      x

use
0:{ t0 }
1:{ t1 }
2:{ }
3:{ t2 t3 }
4:{ t33 }
5:{ }
6:{ t3 }

def
0:{ t1 }
1:{ t2 }
2:{ }
3:{ t33 }
4:{ t3 }
5:{ }
6:{ t3 }

in
0:{ t0 }
1:{ t1 }
2:{ }
3:{ t2 t3 }
4:{ t33 }
5:{ }
6:{ t3 }

out
0:{ t1 }
1:{ }
2:{ t2 t3 }
3:{ t33 }
4:{ }
5:{ }
6:{ }

in
0:{ t0 }
1:{ t1 }
2:{ t2 t3 }
3:{ t2 t3 }
4:{ t33 }
5:{ }
6:{ t3 }

out
0:{ t1 }
1:{ t2 t3 }
2:{ t2 t3 }
3:{ t33 }
4:{ }
5:{ }
6:{ }

in
0:{ t0 }
1:{ t1 t3 }
2:{ t2 t3 }
3:{ t2 t3 }
4:{ t33 }
5:{ }
6:{ t3 }

out
0:{ t1 t3 }
1:{ t2 t3 }
2:{ t2 t3 }
3:{ t33 }
4:{ }
5:{ t2 t3 }
6:{ }

in
0:{ t0 t3 }
1:{ t1 t3 }
2:{ t2 t3 }
3:{ t2 t3 }
4:{ t33 }
5:{ t2 t3 }
6:{ t3 }

out
0:{ t1 t3 }
1:{ t2 t3 }
2:{ t2 t3 }
3:{ t33 }
4:{ t2 t3 }
5:{ t2 t3 }
6:{ }

in
0:{ t0 t3 }
1:{ t1 t3 }
2:{ t2 t3 }
3:{ t2 t3 }
4:{ t2 t33 }
5:{ t2 t3 }
6:{ t3 }

out
0:{ t1 t3 }
1:{ t2 t3 }
2:{ t2 t3 }
3:{ t2 t33 }
4:{ t2 t3 }
5:{ t2 t3 }
6:{ }

RESOURCES

Download Chapter 10 software

The software implements the Liveness analysis for the Mips computer and can be used to test your understanding of Chapter 10. The input to the software is IR instructions; the output is munched Mips instructions, the control-flow graph and interference analysis. A test example has been given (test.java) for your enjoyment.

Directions:

Unzip to directory: Chap10

At command prompt, change to Chap10 directory.

Compile by: javac -classpath . RegAlloc\test.java

Execute by: java -cp . RegAlloc.test

The partial program below exercises and displays the results of calculating the interference graph of a given IR instruction list. Any valid IR instruction is munched and added to an Assem.InstrList by statements such as:

MOVE(b,a).accept(cg);

The resulting Assem.InstrList (for Mips) is printed as a string and converted into a flow graph which is also printed. The flow graph is analyzed for liveness, displaying in and out sets during analysis and interference results on completion. Example results are given in the tables above.

package RegAlloc;

import munch.Codegen;

public class test {
    public static void main(String [] args) {
         Assem.InstrList il;
         Codegen cg=new Codegen(new LinkedList().listIterator());

         Label F = new Label("F");
         TEMP a = new TEMP(new Temp(1));
         TEMP b = new TEMP(new Temp(2));
         TEMP c = new TEMP(new Temp(3));

MOVE(a,CONST(0)).accept(cg);
MOVE(b,a).accept(cg);
LABEL(F).accept(cg);
MOVE(c,BINOP(BINOP.PLUS,c,b)).accept(cg);
JUMP(F).accept(cg);
MOVE(c,c).accept(cg);

         il=cg.codegen();
         System.out.println(il.toString());
         new AssemFlowGraph.AssemFlowGraph(il).show(System.out);
         RegAlloc.Liveness la = new RegAlloc.Liveness( new AssemFlowGraph.AssemFlowGraph(il));
         System.out.println("Live Interval\n"+la.toString());
         System.out.println("Interference Graph");
         la.show(System.out);
    }
}

Chapter 10 LIVENESS ANALYSIS

Chapter 10
LIVENESS ANALYSIS