The Register Allocation problem consists in mapping a program Pv, that can use an unbounded number of virtual registers, to a program Pp that contains a finite, and possibly small number of physical registers. Each target architecture has a different number of physical registers. If the number of physical registers is not enough to accommodate all the virtual registers, some of them will have to be mapped into memory. These virtuals are called spilled virtuals.

In LLVM, physical registers are denoted by integer numbers that normally range from 1 to 1023. To see how this numbering is defined for a particular architecture, you can read the GenRegisterNames.inc file for that architecture. For instance, by inspecting lib/Target/X86/X86GenRegisterNames.inc we see that the 32-bit register EAX is denoted by 15, and the MMX register MM0 is mapped to 48.

Some architectures contain registers that share the same physical location. A notable example is the X86 platform. For instance, in the X86 architecture, the registers EAX, AX and AL share the first eight bits. These physical registers are marked as aliased in LLVM. Given a particular architecture, you can check which registers are aliased by inspecting its RegisterInfo.td file. Moreover, the method MRegisterInfo::getAliasSet(p_reg) returns an array containing all the physical registers aliased to the register p_reg.

Physical registers, in LLVM, are grouped in Register Classes. Elements in the same register class are functionally equivalent, and can be interchangeably used. Each virtual register can only be mapped to physical registers of a particular class. For instance, in the X86 architecture, some virtuals can only be allocated to 8 bit registers. A register class is described by TargetRegisterClass objects. To discover if a virtual register is compatible with a given physical, this code can be used:

  bool RegMapping_Fer::compatible_class(
      MachineFunction & mf,
      unsigned v_reg,
      unsigned p_reg
  ) {
      assert(MRegisterInfo::isPhysicalRegister(p_reg) &&
                                   "Target register must be physical");
      const TargetRegisterClass *trc =
                                 mf.getSSARegMap()->getRegClass(v_reg);
      return trc->contains(p_reg);
  }

Sometimes, mostly for debugging purposes, it is useful to change the number of physical registers available in the target architecture. This must be done statically, inside the TargetRegsterInfo.td file. Just grep for RegisterClass, the last parameter of which is a list of registers. Just commenting some out is one simple way to avoid them being used. More polite is to explicitly exclude some registers from the allocation order. See the definition of the GR register class in IA64RegisterInfo.td for an example of this (there, numReservedRegs registers are hidden.)

Virtual registers are also denoted by integer numbers. Contrary to physical registers, different virtual registers never share the same number. The smallest virtual register is normally assigned the number 1024. This may change, so, in order to know which is the first virtual register, you may access MRegisterInfo::FirstVirtualRegister. Any register whose number is greater than or equal to MRegisterInfo::FirstVirtualRegister is considered a virtual register. Whereas physical registers are statically defined in a TargetRegisterInfo.td file, and cannot be created by the application developer, that is not the case with virtual registers. In order to create new virtual registers, use the method SSARegMap::createVirtualRegister(). This method will return a virtual register with the highest code.

Before register allocation, the operands of an instruction are mostly virtual registers, although physical registers may also be used. In order to check if a given machine operand is a register, use the boolean function MachineOperand::isRegister(). To obtain the integer code of a register, use MachineOperand::getReg(). An instruction may define a register, or may use a register. For instance, ADD reg:1026 := reg:1025 reg:1024 defines the registers 1024, and uses registers 1025 and 1026. Given a register operand, the method MachineOperand::isUse() informs if that register is being used by the instruction. The method MachineOperand::isDef() informs if that registers is being defined.

We will call physical registers present in the LLVM bytecode before register allocation pre-colored registers. Pre-colored registers are used in many different situations, for instance, to pass parameters of functions calls, and to store results of particular instructions. There are two types of pre-colored registers: the ones implicitly defined, and those explicitly defined. Explicitly defined registers are normal operands, and can be accessed with MachineInstr::getOperand(int)::getReg(). In order to check which registers are implicitly defined by an instruction, use the TargetInstrInfo::get(opcode)::ImplicitDefs, where opcode is the opcode of the target instruction. One important difference between explicit and implicit physical registers is that the latter are defined statically for each instruction, whereas the former may vary depending on the program being compiled. For example, an instruction that represents a function call will always implicitly define or use the same set of physical registers. To read the registers implicitly used by an instruction, use TargetInstrInfo::get(opcode)::ImplicitUses. Pre-colored registers impose constraints on any register allocation algorithm. The register allocator must make sure that none of them is been overwritten by the values of virtual registers while still alive.

There are two ways to map virtual registers to physical registers (or to memory slots). The first one, that we will call direct mapping, is based on the use of methods of the classes MRegisterInfo, and MachineOperand. The second, that we will call indirect mapping relies on the VirtRegMap class in order to insert loads and stores sending (bringing) values to (from) memory.

The direct mapping provides more flexibility to the developer of the register allocator; however, it is more error prone, and demands more implementation work. Basically, the programmer will have to specify where load and store instructions should be inserted in the target function being compiled in order to bring and store values in memory. To assign a physical register to a virtual register present in a given operand, use MachineOperand::setReg(p_reg). To insert a store instruction, use MRegisterInfo::storeRegToStackSlot(...), and to insert a load instruction, use MRegisterInfo::loadRegFromStackSlot.

The indirect mapping shields the application developer from the complexities of inserting load and store instructions. In order to map a virtual register to a physical one, use VirtRegMap::assignVirt2Phys(vreg, preg). In order to point that a certain virtual register should be mapped to memory, use VirtRegMap::assignVirt2StackSlot(vreg). This method will return the stack slot where vreg's value will be located. If necessary to map other virtual register to the same stack slot, use VirtRegMap::assignVirt2StackSlot(vreg, stack_location). One important point to consider, when using the indirect mapping, is that, even if a virtual register is mapped to memory, it still needs to be mapped to a physical register. This physical register is the location where the virtual register is supposed to be found before being stored, or after been reloaded.

If the indirect strategy is used, after all the virtual registers have been mapped to physical registers or stack slots, it is necessary to use a spiller object to place load and store instruction in the code. Every virtual that has been mapped to a stack slot will be stored to memory after been defined, and will be loaded before been used. The implementation of the spiller tries to recycle load/store instructions, avoiding unnecessary instructions. For an example of how to invoke the spiller, see RegAllocLinearScan::runOnMachineFunction.

With very rare exceptions (e.g function calls), the LLVM machine code instructions are three address instructions, that is, each instruction is expected to define at most one register, and to use at most two registers. However, some architectures use two address instructions. In this case, the defined register is also one of the used register. For instance, an instruction such as ADD %EAX, %EBX, in X86 is actually equivalent to %EAX = %EAX + %EBX.

In order to produce correct code, a LLVM based compiler must convert three address instructions that represent two address instructions into true two address instructions. The implementation of LLVM provides the pass TwoAddressInstructionPass with this specific purpose. It must be run before register allocation takes place, and, after its execution, the resulting code may no longer be in SSA form. This happens, for instance, in situations where an instruction such as %a = ADD %b %c is converted to two instructions such as:

  %a = MOVE %b
  %a = ADD %a %b

An important transformation that happens during register allocation is called The SSA Deconstruction Phase. The SSA form simplifies many analyses that are performed on the control flow graph of programs. However, traditional instruction sets do not implement phi-functions. Thus, in order to generate executable code, compilers must replace phi-functions with other instructions that preserve their semantics.

There are many ways in which phi-functions can safely be removed from the target code. The most traditional phi-deconstruction algorithm replaces phi functions with copy instructions. That is the strategy adopted by LLVM. The SSA deconstruction algorithm is implemented in the PHIElimination.cpp file. In order to invoke this pass, the identifier PHIEliminationID must be marked as required in the code of the register allocator.

Instruction folding is an optimization performed during register allocation that allows to remove unnecessary copy instructions. For instance, a sequence of instructions such as:

  %EBX = LOAD %mem_address
  %EAX = COPY %EBX

The LLVM infrastructure provides the application developer with three different register allocators:

• Simple: This is a very simple implementation that does not keep values in registers across instructions. This register allocator immediately spills every value right after it is computed, and it reloads all used operands from memory to temporary registers before each instruction.
• Local: This register allocator is an improvement on the simple implementation. It allocates registers on each basic block at a time, attempting to keep values in registers and reusing registers as appropriate.
• Linear scan: this is the well-know linear scan register allocator. Whereas the simple and local algorithms use a direct mapping implementation technique, the linear scan implementation uses a spiller in order to place load and stores.

The type of register allocator used in llc can be chosen in the command line:

   $ llc -f -regalloc=simple file.bc -o sp.s;
   $ llc -f -regalloc=local file.bc -o lc.s;
   $ llc -f -regalloc=linearscan file.bc -o ln.s;