
<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Dec 18, 2017, at 19:03, Leslie Zhai <<a href="mailto:lesliezhai@llvm.org.cn" class="">lesliezhai@llvm.org.cn</a>> wrote:</div></blockquote><div><br class=""></div></div>Hi Leslie,<div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">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. <a href="http://doi.org/10.1007/978-3-540-24644-2_24" class="">http://doi.org/10.1007/978-3-540-24644-2_24</a></div><div class=""><br class=""></div><div class="">Braun, M., & Hack, S. (2009). Register spilling and live-range splitting for SSA-form programs. International Conference on Compiler Construction.</div></blockquote><div class=""><br class=""></div><div class="">When you look at register allocation that way, the graph coloring aspect almost disappears. The optimum approach is probably somewhere in the middle.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">Pereira, F. Q., & Palsberg, J. (2008). Register allocation by puzzle solving.</div></blockquote><div class=""><br class=""></div><div class="">Regards,</div><div class="">/jakob</div><div class=""><br class=""></div></body></html>