CSC362 2004S, Class 40: Register Allocation
Admin:
* Optimization tomorrow, Evaluation at Dairy Barn on Friday
* Meet here at 1:00 p.m. or at Dairy Barn at 1:15
* Send your *reasonable* ice cream request to Ananta by Thursday 9p.m.
* Books
* Please attend tomorrow and Friday
* Notes on upcoming finals (Monday and Thursday)
* You are now second on my grading list
* Questions on the project
* How do you deal with signed values?
Parse tree:
SYM[-]
* Strategy one
* Generate code and a location for the subexpression
* Allocate a new location
* Add the line SUB 0 subexp.loc loc
* Strategy two
* Determine the constant value associated with
* Return new IConstant(-subexp.ivalue); return new FContant(-subexp.fvalue)
Overview
* Goals
* Spilling
* Detour: NP Completeness
* A Heuristic for graph coloring
* Coalescing
* A revised heuristic
Register allocation: Given a large number of temporaries and a smaller number
of registers, assign each temporary to a register such that no two temporaries
who are simulatenously alive use the same register.
* Why?
* Uses less space.
* Matches real computers
Graph coloring: Given an undirected graph, assign a color to each node such that
no two neighboring nodes have the same color.
* Nodes: Temporaries
* Colors: Registers
* Edges: Simultaneous/overlapping lifetimes
Are there other criteria you might use in register allocation (more than
just "fit them all in the available registers")?
* If there is a choice between register or memory, the more-frequently-used temporaries should be put in registers. (perhaps: Consider twenty non-intersecting temporaries vs. one temporary used eight times)
* If you have a MOVE ti tj statement, try to get ti and tj into the same register. -> Permits us to eliminate the move statement. <- Very useful.
Minimal-color Graph coloring is NP complete! That means:
* Informally: No known fast correct solution; Unlikely to be a fast solution.
* Formally: A problem is in NP if a solution can be verified in polynomial time. (O(some polynomial in the size of the problem))
* A problem is NP-complete if any NP problem can be converted to that problem in polynomial time and any solution to that problem can be converted back to a solution to the original problem in polynomial time: Infomally: As hard or harder than any other NP problem.
What do we do when we *have* to solve an NP-complete problem?
* Approximation: Accept "really good" but not "best" solution.
* Accept an algorithm that usually, but not always, works.
* Accept an algorithm that usually, but not always, takes polynomial time
Some graphs are not even K-colorable. The complete graph of six nodes is not five-colorable
* The solution to non-K-colorability requires us to return to the earlier problem of register allocation
* Pick some temporary. After it is assigned, add MOVE tmp some-place-on-stack; Before it is used, add MOVE some-place-on-stack tmp
* Still has to be assigned to a register, still has a node in the graph
* Can change the lifetime of the variable, which should drop edges
* This process is called "spilling"
Goal: Approximate K-coloring
Input: A graph, g, a number of colors, K
Outcome: a K-coloring, much of the time
an error and a recommend node to spill
Associated stuff: A stack
// Preparation
while g is not empty
// Remove the nodes which can "easily" be colored
while g contains a node with < K neighbors
remove that node and push it on the stack
// At this point, all the nodes have K or more neighbors/edges
pick some node with K or more edges, remove it, mark it as "spillable", and push it on the stack
end while
// Coloring
while the stack is nonempty
pop the top element of the stack.
If it is not marked, color it.
if it is marked, try to color it.
Success -> Keep going
Failure -> Stop, report "not K colorable", and spill this node
Can we four-color the following graph?
(A,B), (A,F), (A,G), (B,C), (B,D), (B,E), (B,K), (B,M),
(C,M), (D,J), (D,K), (D,M), (E,F), (E,J), (E,M), (F,J),
(F,M), (G,H), (G,I), (G,J), (G,K), (H,I), (H,J), (J,K),
(J,L), (L,M)