How does LLVM allocate "irregular"-size virtual registers to physical registers?

user_2524999 0
Viewed 29

I'm just getting started with learning LLVM and have a question about the register allocation process.

What I understand so far:

  • Registers defined in LLVM are considered "virtual" registers, and may or may not exceed the number of physical registers a machine has
  • When LLVM assembly is compiled for a specific machine architecture, a register allocation process determines which of the virtual registers can be mapped to physical registers, and which may need to be loaded and unloaded on the stack, instead (ideally this allocation process is optimizing for performance by minimizing memory access)

For the purpose of this question, let's assume that a "regular"-sized virtual register is one that is the same size as a physical register, and than an "irregular"-sized virtual register is one that is either smaller or larger than a physical register. How does LLVM allocate these "irregular"-sized virtual registers?

More specifically:

  • If I have multiple irregular-sized virtual registers that are smaller than the physical registers, can LLVM allocate them to the same physical register? For example, if a machine had 64-bit registers, but I had 3 i8 virtual registers, could they all be used in the same physical register? The images in this blog post seem to suggest they can, but I'm not sure I'm interpreting that post correctly. Are there any performance or capability limitations if virtual registers did share a single physical register?
  • If I have an irregular-sized virtual register that's larger than the physical registers, can LLVM split them across multiple physical registers, or would it be forced to use the stack? For example, if a machine had 64 bit registers, but I had an i72 virtual register, could that just be split across two physical registers? Are there any performance or capability limitations from this?
  • Assuming the answers to the above two questions are "yes", can a smaller virtual register share a physical register with the "overflow" portion of a larger virtual register?
llvm
1 Answers

There is a dedicated process within backend that is called "legalization". Basically the types / operations that are not legal for a given target are turned into ones that are supported by a target natively.

There are multiple approaches to legalizations:

  • Implementing operation in terms of others (sometimes even doing a library function call)
  • Promoting the type to the larger one
  • Splitting the type into smaller pieces

Or the target could chose to lower a particular operation in some custom way.

Note that "register allocation" is not "assigning physical registers to LLVM IR values" (it's better to think about values not registers here as the value is assigned once, you cannot redefine it in LLVM IR). Instead, the register allocation process operates on already legalized values. So it already has in the input the set of properly-sized values along with their live ranges.

user_1649250
Related