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?