Today in CS362: Register Allocation

Admin
* Reminder: It's not a sign of weakness to ask for help
* Parsers?
* Project, Phase 4 (Translation), Ready
  + New groups vs. the Mythical Man Month
* Eboards inhibit Sam's performance predelictions! Problematic?
* Question: What is NP completeness?  (Do I need to describe it?)
* Evote: Should I keep or remove the public presentations
  + A chance to visit more topics
  + An experience you should have in your career
  + But more time in an already crowded semester

Overview
* The problem: Convert arbitrarily many temporaries into fixed
  number of registers.
  + Key concept: Interference graph
* A Basic Algorithm
  + Potential detour: NP completeness
  + Graph coloring
  + Example
* Optimizing while coloring: Coalescing
* A Revised Algorithm

What makes it hard to convert temporaries to registers?
* Temporaries are live at the same time, and therefore
  can't be put into the same register.
* Observation: We can represent the "temps a and b need
  different registers" by making a and b nodes and putting
  an edge between them in a graph
  + We now have a graph in which we'd like to assign a
    value (register) to each node in such a way that no two
    neighboring nodes have the same value.  (Our values 
    must be taken from the set 1 .. k, where there a k
    registers.) : K colorability
* If the graph is K-colorable, we're done
  + Problem one: How do you K-color?
  + Problem two: What do you do if you can't K-color?
* If you can't K-color, you pick a temporary to "spill",
  which requires rewriting the program to store the temporary
  after it is assigned to and load the temporary before it
  is used.
  + Anything with more than k edges is a candidate for
    spilling

On to the problem of K-coloring
* K coloring is NP complete
  + NP: "Nondeterministic Polynomial"
    - You can nondeterministically pick a potential
      solution in polynomial time : O(some polynomail)
    - You can verify whether or not the solution is
      correct in polynomial time
  + Complete: If you can convert another NP-complete problem 
    to this problem  and then convert a solution to this problem
    to a solution to taht problem.
  + What do you do about NP-complete problems in practice,
    given that no one likes expoential algorithms?  Come up
    with a "heuristic" that isn't always right.

Approximate k coloring: K color some K-colorable graphs ,
but not all of 'em.

Key observation: Nodes with degree less than k are easy to
color.  No matter what colors your neighbors have, you can
choose a color for this node.

while nodes remain in graph
  while node n of degree < k remain,
    remove n
    push n onto "nodes to color later"
  end while
  pick some node n of degree >= k
  remove n
  mark n as "potential problem"
  push n onto "nodes to color later"
end while
while nodes remain in stack
  pop a node, n
  if n is not a potential problem, color it some
    color compatible with already-colored neighbors
  if n is a potential problem, two possibilities
    good luck: it's still colorable, so color it
    bad luck: it's not colorable: rewrite the
     program to spill this temporary

Observation:
  Certain kinds of optimization can be done during
  register coloring:
    if you have MOVE ta tb
    try to give ta and tb the same color/register
    then you can eliminate the instruction (yay!)

How do we change our algorithm?