Register Allocation in the LLVM Backend

Introduction

Post instruction selection in LLVM, all instructions operate on virtual registers. The number of virtual registers used is unbounded and often greater than the actual number of registers present on the target machine. Register allocation maps this unbounded set of virtual registers to the finite set of registers present on the target hardware. Ideally, every required value would be present in a register for immediate use. However, the number of registers is finite and the number of values in a program is much higher. A good register allocation algorithm hence tries to keep values that are used frequently in registers. Every value that does not get a register has to be loaded from memory each time it is needed, which costs much more than a register read.

There are two fundamental terms to cover first:

Live range of a variable: The live range of a variable is the range of program points over which its value may still be read. If two variables have no overlap between their live ranges, the register allocator is free to assign to them the same physical register. If their live ranges do overlap, then they cannot.

Spilling: If there are more variables live at the same time than the number of physical registers available, one or more variables have to be spilled to memory. The value is stored to a stack slot and loaded back only at the points where it is actually required, which frees the register everywhere in between. The original live range of the value is replaced by several short ranges, one around each use. This, however, incurs extra latency due to the store and load operations.

LLVM provides four register allocation implementations that can be selected with the -regalloc= flag on llc, or with -mllvm -regalloc= when going through clang.

flag implementation when it runs
fast RegAllocFast default at -O0
basic RABasic never by default, a reference implementation
greedy RAGreedy default at -O1 and above
pbqp RegAllocPBQP never by default, opt-in

This post goes through each algorithm one by one.

Fast

The fast algorithm is by design an extremely simple register allocator.

It works by walking the instructions of a block backwards and handing out a register the first time it encounters a use of a value. Because the walk runs backwards, that first sighting is the last use in program order, which is exactly the point where the value has to be in a register. Any further uses met later in the walk find the value already resident and reuse the same assignment.

If it encounters a use of a value and finds no free registers to allocate it to, it must evict one. The evicted value still has a use further down the block, so a load is placed immediately below the current instruction to bring it back into its register there. When the walk reaches the definition of the evicted value, it inserts a store instruction there.

The choice of which value to evict is a simple ordering. The allocator walks the allocation order for the register class and takes the first free register it finds. If nothing is free, it takes the cheapest register to steal, in this order.

  • A register whose occupant already has a stack slot, or leaves the block anyway. Evicting it costs no new spill.
  • Failing that, a register whose occupant would need a fresh spill.

A register that is pre-assigned, meaning it was fixed before register allocation ever ran, cannot be taken at all.

For every def that it encounters, it frees up the particular register associated with that value. Since the value is defined at this point, it will not be needed further up in the program. Before releasing the register it may have to emit a store though. If the value is used in some other block, or if it was evicted, then the value has to be written out to its stack slot.

Once the walk reaches the top of a block, whatever is still holding a register could not have been defined anywhere inside that block, so it must have arrived from a predecessor. A load is inserted at the top of the block for each of these. Nothing has to be computed here. The backward walk has already worked out exactly which values they are.

Since the algorithm allocates registers for each block separately, a value that crosses a block boundary cannot travel in a register at all. Any value with a use in another block is written out to its stack slot as soon as it is computed, and loaded back at the top of every block that uses it.

1
2
3
4
5
6
7
8
9
define i32 @f(i32 %a, i32 %b, i32 %c) {
entry:
  %s = add i32 %a, %b
  %t = mul i32 %s, %c
  br label %next
next:
  %u = add i32 %s, %t
  ret i32 %u
}
1
2
3
4
5
6
7
8
9
10
11
12
f:
# %bb.0:                                # %entry
	movl	%edi, %eax
	addl	%esi, %eax
	movl	%eax, -8(%rsp)                  # 4-byte Spill
	imull	%edx, %eax
	movl	%eax, -4(%rsp)                  # 4-byte Spill
# %bb.1:                                # %next
	movl	-4(%rsp), %ecx                  # 4-byte Reload
	movl	-8(%rsp), %eax                  # 4-byte Reload
	addl	%ecx, %eax
	retq

At most two values are live at any point, and the allocator uses only two registers, eax and ecx, out of fifteen available, so the spills are not due to register pressure. %s and %t are written to the stack as soon as they are computed and reloaded at the top of next, purely because they are defined in one block and used in another.

Basic

Unlike fast, basic operates over the entire function. Instructions are numbered across it, and a live interval records the ranges of those numbers over which a value is live. Basic also has, for every value, an advance estimate of what spilling it would cost, called its spill weight. Both are computed before the allocator itself runs. Values with a lower spill weight are more likely to be spilled first.

In brief, the spill weight of an interval \(L\) is the number of times the value is read or written, weighted by how often those instructions actually run, divided by how much of the function the value stays live over.

\[ w(L) = \frac{\sum_{i} \left( d_i + u_i \right) \cdot \dfrac{f(b_i)}{f(b_{\mathrm{entry}})}}{\mathrm{size}(L) + K} \]

  • \(d_i\) and \(u_i\) record whether instruction \(i\) writes the value and whether it reads it, so an instruction that does both counts twice.
  • \(f(b_i) / f(b_{\mathrm{entry}})\) is how often that instruction's block is expected to run relative to the function entry. So a use inside a loop counts for far more than a use on a path taken once.
  • \(\mathrm{size}(L)\) is how much of the function the interval covers, and \(K\) is a constant, so that for a short interval the weight tracks the number of uses rather than its exact length.

The idea is that if a value is being read constantly over a short span, it should be expensive to spill, whereas a value that is live across a long stretch without being used should be cheaper to spill. This is because spilling a value that is live across a long stretch will reduce register pressure at each point where the value was previously live.

Similarly, a value being used within a loop should be more expensive to spill.

To see the effect of the span alone, consider two values that are identical in every way except how long they stay live. Each is loaded once, incremented once and stored once, all in one block that runs a single time.

1
2
3
4
5
6
7
8
9
%long  = load volatile i32, ptr %p     ; def of long
...                                    ; 8 unrelated load and store pairs
%short = load volatile i32, ptr %p     ; def of short
...                                    ; 3 unrelated load and store pairs
%uS = add i32 %short, 1                ; use of short
store volatile i32 %uS, ptr %p
...                                    ; 3 unrelated load and store pairs
%uL = add i32 %long, 1                 ; use of long
store volatile i32 %uL, ptr %p

Both numerators come to four. The load contributes one, the add is a two-address instruction on x86 so it both reads and writes the value and contributes two, and the store contributes one. However, %short is live over 9 instructions while %long is live over 35.

span weight
%short 9 instructions \(4 / (9 + 25) \approx 0.118\)
%long 35 instructions \(4 / (35 + 25) \approx 0.067\)

%long is more likely to be spilled due to register pressure.

Note that if a value's live range spans no instruction, meaning it is consumed by the instruction immediately after its definition, it is marked unspillable rather than given a weight. There is nowhere to place the reload that is not the definition itself.

Now moving to the algorithm. The algorithm seeds every virtual register's live interval into a max-heap ordered by the spill weight. This ensures the highest spill weight values get allocated first. Then one value is dequeued at a time and a register is allocated to it.

Allocating a single value proceeds as follows.

  • Try to allocate a register in the preferred class of the value. For each register, check if the value's live interval overlaps with the values already occupying that register.
  • If it overlaps nothing, the register is free. It is taken and the value is done.
  • If everything it overlaps with is another virtual register already assigned to that register, the register is not taken yet, but is remembered as a candidate to come back to. Those values could be spilled to make room.
  • If it overlaps something fixed, either the live range of a physical register or the set of registers a call clobbers, the register is skipped and never becomes a candidate. Nothing can be moved out of the way.
  • If the walk found no free register, the remembered candidates are tried in order. A candidate is usable if every virtual register already assigned to it can be spilled and has a spill weight no greater than the value being allocated. If so, all of them are evicted and spilled, and the register goes to the value that displaced them.
  • If no candidate passes that test, the value being allocated is the one that gets spilled.

When a value is chosen for spilling, a store is placed after the definition and a reload before each remaining use, and the original interval is replaced by one short interval per use, each covering only the gap from its reload to the instruction that reads it. These go back onto the max-heap with freshly computed weights and are allocated in later rounds.

Each of them spans no instruction so they cannot be spilled again.

The problem with the basic algorithm is that values with smaller live intervals are assigned first because their spill weight tends to be higher. This leaves values with larger live intervals with no appropriate slot and hence they are often spilled.

The example below shows this happening. It has six short lived values and one long lived one, compiled for 32 bit x86 with llc -O2 -regalloc=basic -mtriple=i686--. The frame pointer attribute reserves ebp, which leaves exactly six registers available for allocation. Every operation is an opaque asm block, so nothing is reordered or folded away and the intervals are exactly what the listing shows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
define void @f() nounwind "frame-pointer"="all" {
entry:
  %v = call i32 asm sideeffect "", "=r"()      ; long interval, spans everything below

  %a = call i32 asm sideeffect "", "=r"()
  %b = call i32 asm sideeffect "", "=r"()
  %c = call i32 asm sideeffect "", "=r"()
  %d = call i32 asm sideeffect "", "=r"()
  %e = call i32 asm sideeffect "", "=r"()
  call void asm sideeffect "", "r"(i32 %c)
  %f = call i32 asm sideeffect "", "=r"()
  call void asm sideeffect "", "r"(i32 %d)
  call void asm sideeffect "", "r"(i32 %e)
  call void asm sideeffect "", "r"(i32 %b)
  call void asm sideeffect "", "r"(i32 %a)

  call void asm sideeffect "", "r"(i32 %v)     ; only use of %v

  %g = call i32 asm sideeffect "", "=r"()      ; defined and never read
  call void asm sideeffect "", "r"(i32 %f)
  ret void
}
Live ranges of all the values

Every value except %g has exactly one definition and one use, so all of the numerators are equal and the spill weight is decided by the span alone. %v covers the whole function and therefore has the lowest spill weight. This makes %v the last value the allocator tries to allocate. %g is never read, so its interval spans no instruction and it is unspillable, which makes it the first thing the allocator tries to allocate.

Note that at no point are more than six values live at once, and exactly six registers are available, hence it is possible to allocate without spilling any value.

However, that is not what basic produces because it works through the values in this order.

visited assigned
%g 1st, unspillable eax
%c 2nd eax
%d 3rd ecx
%e 4th edx
%b 5th esi
%f 6th edi
%a 7th ebx
%v 8th spilled

Only %g and %c end up sharing, and they share only because %g was already sitting in eax when %c came along and the two do not overlap. Every other short interval is handed a register of its own.

By the time %v is dequeued, all six registers hold something that overlaps it, so none of them is free. %v cannot displace any value either, because it has the lowest spill weight. %v is therefore the value that spills. It picks up a store after its definition and a reload before its single use.

Note that %c and %f never overlap, so one register could have held both of them, and that would have left a register free across the whole of %v. But because basic allocated %g and %c first, they ended up sharing a register, and since %g overlaps with %f, %f needed a new register. The ideal allocation would have been: %c and %f share eax while %g and %v share edi.

assigned
%g edi
%c eax
%d ecx
%e edx
%b esi
%f eax
%a ebx
%v edi

The only difference from what basic produced is that %g and %f swap registers, which leaves edi with room for %v alongside %g. This is one of the problems greedy register allocation solves.

Another problem with basic is that it lacks any means to split the live ranges of a long spanning value. Consider for example an allocation scenario where no suitable register can be found for a value %v spanning program points [a,b). Now suppose two registers are free, one from [a,c) and the other from [c,b). If %v were split into two new values %v1 and %v2 such that %v1 is live from [a,c) and is then copied into %v2, which is live from [c,b), the entire %v could be accommodated without spilling it (a copy is introduced but that is often cheaper than a spill).

These problems are addressed in greedy.

Greedy

Greedy also maintains a max-heap, but it orders entries by the length of their live interval rather than the spill weight. This means that values with longer live ranges get allocated first, followed by values with shorter live ranges. However, all else being equal, the spill weight of a long lived value is still lower than that of a short lived value. Eviction is decided largely on the basis of spill weight, as in basic, with the difference that greedy also counts the copy hints an eviction would break, and will follow a hint even when that means evicting a heavier value. A copy hint is a physical register that a value would prefer to be given, recorded because some copy in the function is deleted if the value ends up there.

Unlike basic, when a value is evicted to make space for another, it is not spilled. The evicted value is put onto the queue to be allocated again. Its priority remains the same when it is queued again. A value that evicts other values stamps everything it displaces with its own number, and a value may only evict something carrying a lower number. A victim therefore ends up with the same number as the value that displaced it, and can never displace it back.

When the evicted value is dequeued again, it runs through the same steps from the top. A register that was occupied the last time it was considered may since have become free. Failing that, it may evict a value of its own. When both of these fail it is set aside until every other value has been allocated. All the values set aside are then considered for splitting, and after that for spilling.

Splitting: As discussed in the basic section, it is possible to split one value into multiple values with smaller live ranges. Each piece covers part of the original live range but it is treated as an ordinary separate value and put onto the queue and allocated independently of the others. Two pieces of the same original value may therefore end up in different registers.

At the point where one piece ends and the next begins, the value has to be made to appear in the new register. Usually a copy is emitted from the old register into the new one. However, it can sometimes be done by just recomputing the value using the instruction. If after splitting, one or more pieces still cannot be assigned a register, those pieces are either split further or spilled (to the same stack slot).

To decide where to cut, greedy primarily tries region splitting. This applies to values which are live across several blocks. The idea is that a value may not be used in all the blocks it is live in, so it only needs a register in some of them. Region splitting is calculated once for every candidate register, and for a given register \(R\) it proceeds as follows.

  • Every block that the value is live in falls into one of three categories.
    • The block uses the value and has register \(R\) free. The block prefers the value be in \(R\).
    • The block uses the value but \(R\) is occupied around where the value is used. The block prefers the value be on the stack.
    • The block does not use the value, it is merely live across it. The block does not care whether the value is in \(R\) or on the stack.
  • The preference of each block is multiplied by the number of times the block executes.
  • Based on these preferences, a group of blocks is chosen in which the value is kept in \(R\), placed so that the switches between register and stack fall on the least executed edges. If there is a block where \(R\) is occupied at its very boundary, then the value must be on the stack before entering the block. Every other preference is overruled if honouring it would cost more in switches than it saves.
  • This is repeated for every candidate register. The cheapest region wins, but only if it is cheaper than the fallback of giving every block its own piece. Otherwise no region split is made.
  • The live range is then cut at the boundaries of the winning region. The blocks inside it become one new value and everything outside becomes the remainder. The new value is put back on the queue and picks up \(R\) on its next visit, since the region was built so that \(R\) is free throughout it. The remainder is marked so it cannot be split again and is spilled if it finds no register.

This is why a loop that reads the value on every iteration ends up holding it in a register for the whole loop. The reload is placed on the edge into the loop rather than inside it. The region splitting therefore produces two pieces here. Before the loop the value is the remainder, typically on the stack. It is reloaded once on the way into the loop, and inside the loop it is the region piece, held in \(R\).

Region splitting on a small control flow graph

PBQP

Unlike the other three, PBQP does not allocate one value at a time. It builds a graph where each virtual register becomes a node. The node has one option for every register it is allowed to take, plus one option for spilling. Each node also has a cost vector with one entry per option. The cost of the spill option is the spill weight of the value, the same weight that basic and greedy use. An edge is added between every two values whose live intervals overlap. Each edge has a cost matrix with one entry for every pair of options the two nodes could take. The entry is infinite if the two registers overlap and zero otherwise. This is how interference is represented. Coalescing is represented the same way with a negative entry. If assigning two values to the same register would allow a copy to be deleted, the entry for that pair is reduced by the frequency of the block containing the copy. The goal is to find the assignment of options to nodes with the lowest total cost.

The algorithm runs in two passes. The first pass removes nodes from the graph one at a time and pushes each onto a stack. The second pass pops the stack and picks an option for each node.

Removing a node \(u\) in the first pass proceeds as follows.

  • If \(u\) has no edges, it is pushed onto the stack. Nothing depends on it.
  • If \(u\) has one neighbour \(v\), its cost is folded into \(v\)'s cost vector before it is removed. For each option \(j\) of \(v\), the cheapest option of \(u\) given \(j\) is added to \(v\)'s cost for \(j\), that is \(c_v[j] \leftarrow c_v[j] + \min_i \left( c_u[i] + C_{uv}[i][j] \right)\).
  • If \(u\) has two neighbours \(v\) and \(w\), its cost is folded into the edge between them, creating that edge if it does not exist. For each pair of options \(j\) of \(v\) and \(k\) of \(w\), the cheapest option of \(u\) given that pair is added to the edge, that is \(C_{vw}[j][k] \leftarrow C_{vw}[j][k] + \min_i \left( c_u[i] + C_{uv}[i][j] + C_{uw}[i][k] \right)\).
  • Note that the two neighbour case can add an edge, so the graph tends to get denser as nodes are removed, and eventually no node of degree two or less is left.
  • If no such node is left, the solver looks for a node that is guaranteed to get a register. A node is guaranteed a register if at least one of its register options stays finite no matter what its neighbours pick. This is checked by counting how many of its options each neighbouring edge can rule out. Such a node is pushed onto the stack and its edges are removed without folding any cost anywhere.
  • If no node is guaranteed a register either, the solver picks the node with the lowest spill cost, breaking ties by lowest degree, and pushes it onto the stack. The node is not spilled at this point. It may still get a register in the second pass.

In the second pass, each node popped from the stack takes its cost vector, adds the row or column of each edge matrix corresponding to the option its neighbour chose, and picks the option with the lowest total. If every register option has infinite cost, the spill option is chosen. If any value is spilled, spill code is inserted, the graph is rebuilt from the new live intervals, and the whole problem is solved again. This repeats until no value is spilled.

PBQP is the only one of the four that is similar to the graph colouring algorithm in Chaitin's original formulation/Briggs' optimistic colouring. The two passes are similar to simplify and select. PBQP is often much slower than the other algorithms because it requires building and rebuilding the graph multiple times.

Conclusion

Out of the four algorithms, greedy is the most commonly used one because it provides a good balance between allocation quality and compilation time. Fast is the quickest of the four algorithms because it operates only at a block level. PBQP can find better solutions for some cases, but in practice its benefits over greedy are limited while its compilation cost is considerably higher.

Register allocation for GPUs has to track one additional constraint, occupancy. On a CPU every thread has the same fixed set of registers. On a GPU, each compute unit has one register file shared by all the waves resident on it, and the number of registers each wave gets is carved out of that pool per kernel. More registers per wave means fewer values have to be spilled and more loads can be kept in flight within a wave. The downside is that fewer waves fit in the pool at once, and hence worse latency hiding. The allocator is therefore given a register budget derived from a target occupancy rather than the whole register file.

References

  1. Jakob Stoklund Olesen, Greedy Register Allocation in LLVM 3.0. https://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
  2. Lang Hames and Bernhard Scholz, Nearly Optimal Register Allocation with PBQP.
  3. Gregory J. Chaitin, Register Allocation & Spilling via Graph Coloring.
  4. Preston Briggs, Keith D. Cooper and Linda Torczon, Improvements to Graph Coloring Register Allocation.