Register allocation is the task of assigning physical registers to virtual registers. Virtual registers can be infinite, but the physical registers for a machine are limited. So, register allocation is aimed at maximizing the number of physical registers getting assigned to virtual registers. In this recipe, we will see how registers are represented in LLVM, how can we tinker with the register information, the steps taking place, and built-in register allocators.
- To see how registers are represented in LLVM, open the
build-folder/lib/Target/X86/X86GenRegisterInfo.incfile and check out the first few lines, which show that registers are represented as integers:namespace X86 { enum { NoRegister, AH = 1, AL = 2, AX = 3, BH = 4, BL = 5, BP = 6, BPL = 7, BX = 8, CH = 9, … - For architectures that have registers that share the same physical location, check out the
RegisterInfo.tdfile of that architecture for alias information. Let's check out thelib/Target/X86/X86RegisterInfo.tdfile. By looking at the following code snippet, we see how theEAX,AX, andALregisters are aliased (we only specify the smallest register alias):def AL : X86Reg<"al", 0>; def DL : X86Reg<"dl", 2>; def CL : X86Reg<"cl", 1>; def BL : X86Reg<"bl", 3>; def AH : X86Reg<"ah", 4>; def DH : X86Reg<"dh", 6>; def CH : X86Reg<"ch", 5>; def BH : X86Reg<"bh", 7>; def AX : X86Reg<"ax", 0, [AL,AH]>; def DX : X86Reg<"dx", 2, [DL,DH]>; def CX : X86Reg<"cx", 1, [CL,CH]>; def BX : X86Reg<"bx", 3, [BL,BH]>; // 32-bit registers let SubRegIndices = [sub_16bit] in { def EAX : X86Reg<"eax", 0, [AX]>, DwarfRegNum<[-2, 0, 0]>; def EDX : X86Reg<"edx", 2, [DX]>, DwarfRegNum<[-2, 2, 2]>; def ECX : X86Reg<"ecx", 1, [CX]>, DwarfRegNum<[-2, 1, 1]>; def EBX : X86Reg<"ebx", 3, [BX]>, DwarfRegNum<[-2, 3, 3]>; def ESI : X86Reg<"esi", 6, [SI]>, DwarfRegNum<[-2, 6, 6]>; def EDI : X86Reg<"edi", 7, [DI]>, DwarfRegNum<[-2, 7, 7]>; def EBP : X86Reg<"ebp", 5, [BP]>, DwarfRegNum<[-2, 4, 5]>; def ESP : X86Reg<"esp", 4, [SP]>, DwarfRegNum<[-2, 5, 4]>; def EIP : X86Reg<"eip", 0, [IP]>, DwarfRegNum<[-2, 8, 8]>; … - To change the number of physical registers available, go to the
TargetRegisterInfo.tdfile and manually comment out some of the registers, which are the last parameters of theRegisterClass. Open theX86RegisterInfo.cppfile and remove the registersAH,CH, andDH:def GR8 : RegisterClass<"X86", [i8], 8, (add AL, CL, DL, AH, CH, DH, BL, BH, SIL, DIL, BPL, SPL, R8B, R9B, R10B, R11B, R14B, R15B, R12B, R13B)> { - When you build LLVM, the
.incfile in the first step will have been changed and will not contain theAH,CH, and DH registers. - Use the test case from the previous recipe, Analyzing live intervals, in which we performed live interval analysis, and run the register allocation techniques provided by LLVM, namely
fast,basic,greedy, andpbqp. Let's run two of them here and compare the results:$ llc –regalloc=basic interval.ll –o intervalregbasic.sNext, create the
intervalregbasic.sfile as shown:$ cat intervalregbasic.s .text .file "interval.ll" .globl donothing .align 16, 0x90 .type donothing,@function donothing: # @donothing # BB#0: movl %edi, -4(%rsp) retq .Lfunc_end0: .size donothing, .Lfunc_end0-donothing .globl func .align 16, 0x90 .type func,@function func: # @func # BB#0: subq $24, %rsp movl %edi, 20(%rsp) movl $5, 16(%rsp) movl $5, %edi callq donothing movl 16(%rsp), %edi movl %edi, 12(%rsp) callq donothing movl $9, 16(%rsp) cmpl $4, 20(%rsp) jg .LBB1_2 # BB#1: movl $3, 8(%rsp) movl $3, %edi callq donothing movl 8(%rsp), %edi movl %edi, 4(%rsp) jmp .LBB1_3 .LBB1_2: movl 16(%rsp), %edi movl %edi, (%rsp) .LBB1_3: callq donothing movl 12(%rsp), %eax addq $24, %rsp retq .Lfunc_end1: .size func, .Lfunc_end1-func
Next, run the following command to compare the two files:
$ llc –regalloc=pbqp interval.ll –o intervalregpbqp.sCreate the
intervalregbqp.sfile:$cat intervalregpbqp.s .text .file "interval.ll" .globl donothing .align 16, 0x90 .type donothing,@function donothing: # @donothing # BB#0: movl %edi, %eax movl %eax, -4(%rsp) retq .Lfunc_end0: .size donothing, .Lfunc_end0-donothing .globl func .align 16, 0x90 .type func,@function func: # @func # BB#0: subq $24, %rsp movl %edi, %eax movl %eax, 20(%rsp) movl $5, 16(%rsp) movl $5, %edi callq donothing movl 16(%rsp), %eax movl %eax, 12(%rsp) movl %eax, %edi callq donothing movl $9, 16(%rsp) cmpl $4, 20(%rsp) jg .LBB1_2 # BB#1: movl $3, 8(%rsp) movl $3, %edi callq donothing movl 8(%rsp), %eax movl %eax, 4(%rsp) jmp .LBB1_3 .LBB1_2: movl 16(%rsp), %eax movl %eax, (%rsp) .LBB1_3: movl %eax, %edi callq donothing movl 12(%rsp), %eax addq $24, %rsp retq .Lfunc_end1: .size func, .Lfunc_end1-func
- Now, use a
difftool and compare the two assemblies side by side.
The mapping of virtual registers on physical registers can be done in two ways:
- Direct Mapping: By making use of the
TargetRegisterInfoandMachineOperandclasses. This depends on the developer, who needs to provide the location where load and store instructions should be inserted in order to get and store values in the memory. - Indirect Mapping: This depends on the
VirtRegMapclass to insert loads and stores, and to get and set values from the memory. Use theVirtRegMap::assignVirt2Phys(vreg, preg)function to map a virtual register on a physical one.
Another important role that the register allocator plays is in SSA form deconstruction. As traditional instruction sets do not support the phi instruction, we must replace it with other instructions to generate the machine code. The traditional way was to replace the phi instruction with the copy instruction.
After this stage, we do the actual mapping on the physical registers. We have four implementations of register allocation in LLVM, which have their algorithms for mapping the virtual registers on the physical registers. It is not possible to cover in detail any of those algorithms here. If you want to try and understand them, refer to the next section.