On Dec 18, 2017, at 19:03, Leslie Zhai <lesliezhai@llvm.org.cn
<mailto:lesliezhai@llvm.org.cn>> wrote:
Hi Leslie,
As others have pointed out, the notion that register allocation is
isomorphic to graph coloring is poppycock. There are other important
aspects, in particular the placement of spill/fill/copy instructions.
The importance of graph coloring relative to spill code placement
depends on how many registers you have available. If you are
generating code for 32-bit x86 which has only 6-7 general purpose
registers, you will have so much spill code and short live ranges that
graph coloring doesn’t matter much at all. On the other hand, if you
have 32 registers like Chaitin did, you have much less spilling in
typical code, and the graph coloring aspect becomes important.
Early compilers would keep each local variable in a stack slot, and
the register allocation optimization would literally allocate a whole
local variable to a register. The C “register” keyword makes sense in
that context. Later improvements like copy coalescing and live range
splitting meant that multiple local variables could use the same
register and a variable could live in different places at different
times. It is sometimes useful to take this development to its logical
extreme and look at register allocation as a caching problem: The
register allocator’s job is to make sure that values are available to
the instructions the need them, using the registers as a cache to get
the values there in the most efficient way possible.
Guo, J., Garzarán, M. J., & Padua, D. (2004). The Power of
Belady’s Algorithm in Register Allocation for Long Basic Blocks.
In Languages and Compilers for Parallel Computing (Vol. 2958, pp.
374–389). Berlin, Heidelberg: Springer Berlin Heidelberg.
http://doi.org/10.1007/978-3-540-24644-2_24
Braun, M., & Hack, S. (2009). Register spilling and live-range
splitting for SSA-form programs. International Conference on
Compiler Construction.
When you look at register allocation that way, the graph coloring
aspect almost disappears. The optimum approach is probably somewhere
in the middle.
A third important aspect is register constraints on individual
instructions. Sometimes you almost need a little constraint solver
just to figure out a valid register assignment for a single
instruction. Preston Briggs dealt with this in his thesis, but it
hasn’t gotten as much attention as graph coloring since.
Pereira, F. Q., & Palsberg, J. (2008). Register allocation by
puzzle solving.
Regards,
/jakob