[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to Liveness Analysis. On to Code Improvement (1).
Held: Wednesday, 5 May 2004
Summary: Today we consider how to assign registers to temporaries.
Related Pages:
Notes:
Overview:
MOVE
in the same register, so that the MOVE
can be
eliminated.
MOVE
instructions. In these cases, the values in the registers may need
to spill to memory (requiring a change in the program so that
we write them to the stack whenever we change them and read
them from the stack whenever we need them).
t10
is assigned a value
in the first statement and that value is not used again until the
hundredth statement. t10
is live for all 100 statements.
allocateRegisters(program p, regcount k) { compute g, an interference graph for the program while g cannot be colored with k colors remove a node from g, spilling it to memory rewrite the program and recompute g end while color g with k colors replace each color by a register end allocateRegisters
very difficultor
exponential time
repeatedly guess a solution and test whether it is correct
guess and test.
try all permutations until you find a sorted one.
Here's a graph (a list of edges) to try the algorithm on. We'll try to four-color it. Note that this is a modified version of a graph that I took from Appel's book (a book we no longer use for reasons that the first set of CS362 students will be happy to tell you).
(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)
(I haven't given the underlying program. I don't think we'll need to rewrite the program, but it may depend on choices we make.)
MOVE
when it
is safeto do so.
function allocReg(program p, regcount k) build the interference graph for p build the list of move-pairs create an empty stack while p is nonempty repeat simplify: remove nodes of arity < k not in move pairs, pushing them on the stack coalesce: join nodes in any move pairs if safe to do so if (we neither simplified nor coalesced) freeze: pick some move-pair node with arity < k, and remove all move-pairs with that node until no changes can be made if there are nodes of arity >= k spill: remove some node of arity >= k, pushing it on the stack end if end while select: while there are nodes on the stack if some color can be assigned to the top node on the stack then assign that color otherwise, note that the top node must be spilled recover: if some node was marked as spilled during the select phase, then update the program to do the spilling and call allocReg again. end allocReg
Back to Liveness Analysis. On to Code Improvement (1).
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Thu May 6 08:49:51 2004.
The source to the document was last modified on Tue Jan 20 23:06:47 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.40.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby