Basic Register Allocation Algorithm Documentation

Code Generation Common Infrastructure
1

Hello LLVM Community,

It’s been a while since I started to look for any piece of text documenting the algorithm on which the Basic Register Allocator (BRA) relies on.

During my research, I stumbled on [1], a report concerning the application of “Secon-Chanche Binpacking in SSA context” [2] within the LLVM ecosystem. The description seems to match (to some degree) what I’ve been able to understand from the BRA’s code.

Still, I unable to find documents reporting whether the BRA bases on [1]'s implementation. Furthermore, the current BRA implementation uses a different priority cost (spill weight, instead of liveness starting point).

So, I have the two following questions:

  1. Is there any public document specific to the BRA? (pseudo-code, rationale, …).
  2. Does BRA base on [1]?
  3. Is it BRA based on “Secon-Chanche Binpacking in SSA context” [2], but with a different priority cost?

Thank you in advance,
DoktorC

---- REFERENCES

[1] Evlogimenos A. (2004). Improvements to Linear Scan Register Allocation.

[2] Mössenböck, H., & Pfeiffer, M. (2002). Linear Scan Register Allocation in the Context of SSA Form and Register Constraints. International Conference on Compiler Construction .

2

Are you talking about llvm/lib/CodeGen/RegAllocBasic.cpp? Like RegAllocGreedy, I don’t think that really is explained in papers, your best bet are probably reading the source and looking for the presentations at the developer meetings.

RegAllocBasic.cpp I think was meant as a form of basic, as-simple-as-possible implementation of the new (at the time) register allocation APIs. The idea was that you can build more advanced allocators on top of it.

In practice RegAllocBasic is not used AFAIK. It’s not as fast as RegAllocFast and RegAllocGreedy has more features / produces better code. So RegAllocBasic mostly lives on as the base class for RegAllocGreedy and as sort of an example if someone wanted to start a new allocator based on the infrastructure…

3

Hello MatzeB,

Yes, that one.

That is a bit of a shame :frowning: I find presentations useful to have an holistic overview of the algorithm (or a specific part of it), but it happens to be in need of a more systematic discussion about it.

Indeed, from the current description of RegAllocGreedy and from Intel’s presentation (2018), it resembles a beefed version of the BRA.

I wonder if it would be worth to extend the built-in register allocators description in the LLVM docs…

Kind regards