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?