3 ms·
For the curious, reload was written by Richard Kenner, who, while a wonderful guy, was not generally familiar with modern compiler architecture (graph coloring
by DannyBee 12y ago
For the curious, reload was written by Richard Kenner, who, while a wonderful guy, was not generally familiar with modern compiler architecture (graph coloring register allocation goes back to 1982, reload was started in the late 80's).
It essentially took the place of spill placement/code/legalization. Over the years, it grew rematerialization, instruction combination, copy coalescing, stack slot sharing and all sorts of other interesting scope creep.
While i believe it has finally been replaced by LRA for some targets, there were many people who spent years of their life trying to replace reload with separate, smaller pieces of architecture. No one has yet completely succeeded.
It is essentially an interesting object lesson in what happens when you just incrementally improve architecture to achieve performance goals without a stop-loss point for requiring new design.
- probably_wrong 12y agoAs 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.