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

[Bruce Hoult via llvm-dev]

So, both AVR and RISC-V are fairly register-rich with usually 32. RV32E
only has 16, but that's still a lot better than i386. If you use a lot of
16 bit integers then AVR also only has effectively 16 registers (or a more
with a mix of 8 and 16 bit variables). 32 bit integers should be rare in
AVR code, but soft float/double variables are common in Arduino code (both
are implemented as 32 bits), so you only have room for 8 of those.

RISC-V doesn't have any hard constraints on something that *must* go in a
certain register, except the usual argument passing/return convention.
There is a an advantage to allocating both the data src/dst register and
the pointer base register for a load or store from x8-x15 (s0-1,a0-5) as
much as possible as this allows the assembler to use a two byte instruction
instead of a four byte instruction.

I haven't look at AVR in detail for a while, but I seem to recall the top
six registers make up three 16 bit pointer registers X,Y,Z. Any of them can
be used for (C language) *p, *--p, *p++, only Y&Z can be used for p->foo,
and only Z can be used for computed jumps (including function link
register) or loading constants from program memory. Also the various
multiply instructions take their 8 bit operands from any registers but
always produce the 16 bit result in r1:r0. Annoying but nowhere near as bad
as i386 as r0 and r1 are not used for anything else. The usual ABI makes r0
a clobber-at-will temp. r1 is supposed to be "always zero", so you need to
CLR it after retrieving (or ignoring) the high bits of a multiply result.

On Thu, Dec 21, 2017 at 3:44 AM, Leslie Zhai via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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/
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171221/5c6414b8/attachment.html>