[llvm-dev] Register Allocation Graph Coloring algorithm and Others
Leslie Zhai via llvm-dev
llvm-dev at lists.llvm.org
Thu Dec 21 08:25:53 PST 2017
Hi Bruce,
Thanks for your sharing!
I am porting GlobalISel to RISCV target[1], the highest priority in the
TODO list[2], welcome to contribute to lowRISC, if fixed all the issues,
then I could try to implement RegAllocGraphColoring in HEA and write
great Machine Schedulers.
[1] https://github.com/lowRISC/riscv-llvm/issues/19
[2] https://github.com/lowRISC/riscv-llvm/issues
在 2017年12月21日 19:09, Bruce Hoult 写道:
> 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 <mailto: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>
> <mailto: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
> <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/
> <https://reviews.llvm.org/p/xiangzhai/>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
--
Regards,
Leslie Zhai - https://reviews.llvm.org/p/xiangzhai/
More information about the llvm-dev
mailing list