[llvm-dev] Register Allocation Graph Coloring algorithm and Others

[Leslie Zhai via llvm-dev]

Hi Jakob,

Thanks for your kind response!

My usecase is for AVR and RISCV targets, and I just want to learn and 
practice HEA in RA, thanks for your sharing.


在 2017年12月21日 01:25, Jakob Stoklund Olesen 写道:
>
>> On Dec 18, 2017, at 19:03, Leslie Zhai <lesliezhai at llvm.org.cn 
>> <mailto:lesliezhai at 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
>

-- 
Regards,
Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/