9 ms·
As someone moderately curious, I hope I'm not the only one when I say: I didn't understand a word after "the late 80's". And that's only because I searched for
by probably_wrong 12y ago
As someone moderately curious, I hope I'm not the only one when I say: I didn't understand a word after "the late 80's". And that's only because I searched for "graph coloring register allocation" first.
- rayiner 12y agoFor simplicity, a compiler manipulates an internal representation in terms of virtual registers. A register allocator assigns physical registers to these virtual ones, under the principle that different virtual registers may be assigned to the same physical one if they are not live (I.e. hold a value that will be used in the future) at the same time. Spill code generation is necessary because at a program point, there may not be enough physical registers for all the live values, and code must be generated to spill some of them to the stack and reload them when needed. Legalization performs code transformations to eliminate target independent operations in the IR that can't be represented on the target. Copy coalescing eliminates the need for copies between virtual registers by assigning both to the same physical register. Rematerialization takes advantage of values that can be recomputed cheaply, and instead of holding them in a register for a long time, recomputes them where needed. What makes this all so complex is that 1) most of these don't have polynomial time algorithms that produce optimal solutions: 2) the individual problems are mostly coupled. E.g. spill code itself uses registers, and so the interference graph (which summaries whether virtual registers are simultaneously live) might need to be recomputed or modified. If you're interested in this sort of thing, Kieth Cooper at Rice has posted the lecture notes for his graduate compilers class online: http://www.cs.rice.edu/~keith/512/Lectures http://www.cs.rice.edu/~keith/512/Lectures. Register allocation is lectures 26-7.