Copyright © 2004
Robert W. Hasker

Ch. 10

• Issue: how to allocate registers?
  • bounded number of registers: can't allocate one per variable
  • more refined solution requires knowing where variable is "live"
    • that is, the places where a variable holds a value that may be needed in the future
• control-flow graph: [draw graph for following:]

  // program P1
          a = 0                   // node 1
      L1: b = a + 1               // node 2
          c = c + b               // node 3
          a = b * 2               // node 4
          if a < N goto L1        // node 5
          return c                // node 6
  

• liveness of all variables
  • where is b alive?
    • draw on graph
    • live range: {2 -> 3, 3 -> 4}
  • where is a alive?
    • {1 -> 2}, {4 -> 5 -> 2}
    • note where not alive
  • where is c alive?
    • alive on entry: either available as parameter or uninitialized

Dataflow Equations

• how to compute liveness?
• terminology
  • out-edges: edges leading to successor nodes
    • succ[n]: all immediate successors of node n
  • in-edges: edges leading from predecessor nodes
    • pred[n]: all immediate predecessors of node n
  • eg from above graph:
    • pred[2] = {1, 5}
    • succ[5] = {2, 6}
  • defs
    • assignment statement defines a variable
    • def[variable]: set of graph nodes defining variable
    • def[n]: set of variables defined by graph node
  • uses
    • accesses to data
    • use[variable]: set of graph nodes using variable
    • use[n]: set of variables used by node
  • examples
    • def[4], use[4]
  • liveness
    • "a variable is live on an edge if there is a directed path from that edge to a use that does not go through any def"
    • live-in[n]: set of variables live on any in-edge of n
    • live-out[n]: set of variables live on any out-edge of n
• "dataflow equations for liveness analysis"
  • derived from
    • x ∈ use[n] implies x ∈ live-in[n]
    • x ∈ live-in[n] implies x ∈ live-out[m] for all m ∈ pred[n]
    • x ∈ live-out[n] and not x ∈ def[n] implies x ∈ live-in[n]
  • abbreviation: write live-in[n] as in[n], live-out[n] as out[n]
  • equations:
    • in[n] = use[n] ∪ (out[n] - def[n])
    • out[n] = (∪ in[s]) for s in succ[n]
• algorithm: alg 10.4 (p. 206)
  • [apply to above graph: compute use, def for all nodes, then compute live-in (in) and live-out (out) for each node]
• improving the algorithm
  • order nodes properly: given edge 2 -> 3, should compute out[3], then in[3], then out[2], and finally in[2]
    • That is, compute in order of depth-first search.
    • processing nodes in order from 6 to 1 requires just 3 iterations
  • basic blocks: using basic blocks speeds up the algorithm because of fewer nodes
    • increases complexity: now may need liveness analysis within a basic block!
  • computing one variable at a time by tracing backwards from each use
    • can be efficient because most uses span just a few statements
  • representation
    • bit vector: works well for small numbers of variables, not so well for large numbers
• analysis
  • worst-case: O(n⁴)
  • above improvements: typically between O(n) and O(n²)

Refining the Definition

• safety: above definition is conservative: variables may not actually be live even though they are identified as such
  • what are the consequences of this?
  • what would be the consequences of being wrong the other direction?
• Example where equations get it wrong:

          a = b * b       // node 1
          c = a + b       // node 2
          if c >= b       // node 3
             return c     // node 5
          else            
             return a     // node 4
  

  • c >= b is always true, so node 4 never reached
  • question: can we generalize this analysis?
• basic limitation of compiler: halting problem
  • Theorem "There is no program H that takes as input any program P and input X and (without an infinite loop) returns true if P(X) halts and false if P(X) loops forever.
    • why an issue?
      • most programs obvious one way or the other
      • but, there are many difficult cases
      • non-obvious function: Ackermann's function:

                A(0, n) = n + 1
                A(m+1, 0) = A(m, 1)
                A(m+1, n+1) = A(m, A(m+1, n))
        

        • computable, but grows very fast: A(0,0) = 1, A(2, 2) = 7, A(3,2) = 2⁶⁵⁵³⁶-3
      • until recently, another non-obvious function: find an a, b, c, and n over integers such that aⁿ = bⁿ + cⁿ for n > 2
    • Proof of above theorem:
      1. Assume H is such a program (note H has two parameters).
      2. Define F to be

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

      3. Feed F to itself
         • if F(F) halts, then H(F, F) is true and so F falls into the while loop and loops forever
         • if F(F) loops forever, then H(F, F) is false, so F(F) halts and returns false
      4. Contradiction: F(F) halts if it doesn't halt, and doesn't halt if it halts.
      5. Conclusion: there can be no program H that tests whether another program halts (and always halts itself)
  • Corollary: Given program X with label L, there is no program H'(X,L) whether label L is ever reached on any input to X
    • proof: just let L be the end of the program (and change halt commands to jump to L)
  • consequence: cannot predict liveness perfectly
  • could extend compiler to cover special cases, but issue becomes whether extension worth the cost

Interference Graphs

• issue: how to apply liveness definition to register allocation?
  • given: set of temporaries, a, b, c, ... and set of registers r₁, ..., r_k
  • interference: a and b cannot be allocated to same register
  • causes of interference
    • overlapping live regions
    • constraints on registers; eg: must generate a using an instruction that cannot access r₁
  • interference graph
    • node for each temporary, edge between interfering registers
    • eg: interference graph for program P1 (at the start of the notes): live-out sets are 1: {a,c}, 2: {b,c}, 3: {b,c}, 4: {a,c}, 5: {a,c}, 6: {}, thus graph has lines from a to c and b to c (only)
  • move instructions
    • given

              u <- v
              x <- u
              y <- v
      

      u and v have overlapping use/def regions, but in fact they contain the same value
    • special case for not marking interference
    • general rule: if a has the same value as b, don't mark interference between a and b until a and b are modified
  • algorithm for generating interference graph:
    1. if a non-move instruction defines a and has live-out variables b₁, ... b_j, add interference edges (a, b₁), ... (a, b_j)
    2. if a move instruction defines a using c and has live-out variables b₁, ... b_j, add interference edges (a, b₁), ... (a, b_j) for all b_i != c

Review

• liveness, use/def, live-in, live-out
• flow equations
• computing liveness
• limitations of liveness analysis
  • halting problem
• interference graphs