Copyright © 2004
Robert W. Hasker

Chapters 11 and 12

Ch. 11

• Register Allocation
• an application of graph coloring
  • graph coloring: assign colors to all nodes such that no two adjacent nodes have the same color but we use a minimum number of colors
  • classic application: color states/countries on a map
    • 4-color theorem: if can draw graph on paper without crossing lines, need at most 4 colors
  • application to register allocation: colors = register names
    • if need more colors than registers, need to spill registers into memory
• issue: graph coloring is "NP Complete"
  • all known (perfect) algorithms are exponential: try all colorings with 2, 3, ... N (where N is the number of nodes in the graph) until find one which works
    • each trial: consider all N^k possible colorings for k colors
  • furthermore, can reduce this problem (in polynomial time) to a large set of other problems which seem to require exponential time
    • a polynomial-time solution to any one of the problems would lead to polynomial-time solutions to all of them
    • no one can yet prove polynomial-time solutions do not exist
    • people have tried to find polynomial-time solutions to these problems but have failed
  • consequence: "perfect" register allocation is not practical
    • given 20 variables and 10 registers, may need to examine 10²⁰ combinations
    • at 10¹² combinations per second, need 10⁸ seconds or 3+ years to evaluate all!

Practical Register Allocation

• linear-time approximation algorithm giving good results
• phases:
  1. Build: construct interference graph
  2. Simplify: color graph using heuristic
     • Let K be the number of registers; goal is to find a coloring that uses no more than K distinct colors/registers
     • Observation: if node m in G has fewer than K neighbors (where K is the number of registers) and G' = G - {m} can be K - 1 colored, then can color G
     • Algorithm: find a node with fewer than K neighbors, push that node on a stack, remove it, then recursively look for a node with fewer than K neighbors. Stop when all nodes removed or no node has fewer than K neighbors.
  3. Spill: if all nodes have too many neighbors (so we may need to spill some node to memory), pick one and mark it to be spilled and push that node on the stack. Then go back to Simplify.
  4. Select: When graph is empty, we rebuild the graph by picking the topmost node from the stack, allocating it to a register. When we reach a node which was marked for spill, we determine if there is a possible allocation after all - that is, its neighbors already use all registers. If it can be allocated, we do so and simply continue. Of not, we go on to identify other variables that also need to be spilled. This step terminates with either all variables allocated as a register or some variables must be spilled.
     • Start Over: If some variables must be spilled, rewrite the program to fetch the variables from memory just before using them and go back to Build.
  5. the rewrite results in different live ranges, hence a different interference graph
  6. in practice: one or two iterations is almost always is sufficient