In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (local register allocation), over a whole function/procedure (global register allocation), or across function boundaries traversed via call-graph (interprocedural register allocation). When done per function/procedure the calling convention may require insertion of save/restore around each call-site.
Context
Principle
+ Different number of general-purpose registers in the most common architectures Architecture 32 bit 64 bit ARM 15 31 Intel x86 8 16 MIPS 32 32 POWER/PowerPC 32 32 RISC-V 15/31 15/31 SPARC 31 31
In many programming languages, the programmer may use any number of variables. The computer can quickly read and write registers in the CPU, so the computer program runs faster when more variables can be in the CPU's registers. Also, sometimes code accessing registers is more compact, so the code is smaller, and can be fetched faster if it uses registers rather than memory. However, the number of registers is limited. Therefore, when the compiler is translating code to machine-language, it must decide how to allocate variables to the limited number of registers in the CPU.
Not all variables are in use (or "live") at the same time, so, over the lifetime of a program, a given register may be used to hold different variables. However, two variables in use at the same time cannot be assigned to the same register without corrupting one of the variables. If there are not enough registers to hold all the variables, some variables may be moved to and from RAM. This process is called "spilling" the registers. Over the lifetime of a program, a variable can be both spilled and stored in registers: this variable is then considered as "split". Accessing RAM is significantly slower than accessing registers and so a compiled program runs slower. Therefore, an optimizing compiler aims to assign as many variables to registers as possible. A high "Register pressure" is a technical term that means that more spills and reloads are needed; it is defined by Braun et al. as "the number of simultaneously live variables at an instruction".
In addition, some computer designs cache frequently-accessed registers. So, programs can be further optimized by assigning the same register to a source and destination of a move instruction whenever possible. This is especially important if the compiler is using an intermediate representation such as static single-assignment form (SSA). In particular, when SSA is not fully optimized it can artificially generate additional move instructions.
Components of register allocation Register allocation consists therefore of choosing where to store the variables at runtime, i.e. inside or outside registers. If the variable is to be stored in registers, then the allocator needs to determine in which register(s) this variable will be stored. Eventually, another challenge is to determine the duration for which a variable should stay at the same location.
A register allocator, disregarding the chosen allocation strategy, can rely on a set of core actions to address these challenges. These actions can be gathered in several different categories: Move insertion This action consists of increasing the number of move instructions between registers, i.e. make a variable live in different registers during its lifetime, instead of one. This occurs in the split live range approach. Spilling This action consists of storing a variable into memory (primary storage like RAM) instead of registers. Assignment This action consists of assigning a register to a variable. Coalescing This action consists of limiting the number of moves between registers, thus limiting the total number of instructions. For instance, by identifying a variable live across different methods, and storing it into one register during its whole lifetime. Many register allocation approaches optimize for one or more specific categories of actions.
Common problems raised in register allocation Register allocation raises several problems that can be tackled (or avoided) by different register allocation approaches. Three of the most common problems are identified as follows:
Aliasing In some architectures, assigning a value to one register can affect the value of another: this is called aliasing. For example, the x86 architecture has four general purpose 32-bit registers that can also be used as 16-bit or 8-bit registers. In this case, assigning a 32-bit value to the eax register will affect the value of the al register.
Pre-coloring This problem is an act to force some variables to be assigned to particular registers. For example, in PowerPC calling conventions, parameters are commonly passed in R3-R10 and the return value is passed in R3.
NP-Problem Chaitin et al. showed that optimal register allocation is an NP-complete problem. This NP-completeness is entirely dependent upon exactly how the problem is structured. It has been shown that for programs in SSA form, the graph coloring portion of the register allocation problem can be solved in linear time. What causes the general graph coloring problem to be NP-complete and what causes the some versions of the register allocation problem to be NP-complete are distinct.
Register allocation techniques Register allocation can happen over a basic block of code: it is said to be "local", and was first mentioned by Horwitz et al. As basic blocks do not contain branches, the allocation process is thought to be fast, because the management of control-flow graph merge points in register allocation reveals itself a time-consuming operation. However, this approach is thought not to produce as optimized code as the "global" approach, which operates over the whole compilation unit (a method or procedure for instance).
Graph-coloring allocation
Graph-coloring allocation is the predominant approach to solve register allocation. It was first proposed by Chaitin et al. In this approach, nodes in the graph represent live ranges (variables, temporaries, virtual/symbolic registers) that are candidates for register allocation. Edges connect live ranges that interfere, i.e., live ranges that are simultaneously live at at least one program point. Register allocation then reduces to the graph coloring problem in which colors (registers) are assigned to the nodes such that two nodes connected by an edge do not receive the same color.
Using liveness analysis, an interference graph can be built. The interference graph, which is an Interval graph where the nodes are the program's variables, is used to model which variables cannot be allocated to the same register.
Principle The main phases in a Chaitin-style graph-coloring register allocator are:
Renumber: discover live range information in the source program. Build: build the interference graph. Coalesce: merge the live ranges of non-interfering variables related by copy instructions. Spill cost: compute the spill cost of each variable. This assesses the impact of mapping a variable to memory on the speed of the final program. Simplify: construct an ordering of the nodes in the inferences graph Spill Code: insert spill instructions, i.e. loads and stores to commute values between registers and memory. Select: assign a register to each variable.
Drawbacks and further improvements The graph-coloring allocation has three major drawbacks. First, it relies on graph-coloring, which is an NP-complete problem, to decide which variables are spilled. Although finding a minimal coloring for general graphs is indeed an NP-complete problem, minimal coloring of Interval graphs (including interference graphs) can be done in linear time (see Linear scan below); Therefore, this technique does not full utilize the problem's assumptions. Second, unless live-range splitting is used, evicted variables are spilled everywhere: store instructions are inserted as early as possible, i.e., just after variable definitions; load instructions are respectively inserted late, just before variable use. Third, a variable that is not spilled is kept in the same register throughout its whole lifetime.
On the other hand, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Then, multiple register names may be aliases for a single hardware register. Finally, graph coloring is an aggressive technique for allocating registers, but is computationally expensive due to its use of the interference graph, which can have a worst-case size that is quadratic in the number of live ranges. The traditional formulation of graph-coloring register allocation implicitly assumes a single bank of non-overlapping general-purpose registers and does not handle irregular architectural features like overlapping registers pairs, special purpose registers and multiple register banks.
One later improvement of Chaitin-style graph-coloring approach was found by Briggs et al.: it is called conservative coalescing. This improvement adds a criterion to decide when two live ranges can be merged. Mainly, in addition to the non-interfering requirements, two variables can only be coalesced if their merging will not cause further spilling. Briggs et al. introduces a second improvement to Chaitin's works which is biased coloring. Biased coloring tries to assign the same color in the graph-coloring to live range that are copy related.
Linear scan
Linear scan is another global register allocation approach. It was first proposed by Poletto et al. in 1999. In this approach, the code is not turned into a graph. Instead, all the variables are linearly scanned to determine their live range, represented as an interval. Once the live ranges of all variables have been figured out, the intervals are traversed chronologically. Although this traversal could help identifying variables whose live ranges interfere, no interference graph is being built and the variables are allocated in a greedy way.
The motivation for this approach is speed; not in terms of execution time of the generated code, but in terms of time spent in code generation. Typically, the standard graph coloring approaches produce quality code, but have a significant overhead, the used graph coloring algorithm having a quadratic cost. Owing to this feature, linear scan is the approach currently used in several JIT compilers, like the Hotspot client compiler, V8, Jikes RVM, and the Android Runtime (ART). The Hotspot server compiler uses graph coloring for its superior code.
Pseudocode
This describes the algorithm as first proposed by Poletto et al., where: R is the number of available registers. active is the list, sorted in order of increasing end point, of live intervals overlapping the current point and placed in registers.
LinearScanRegisterAllocation active ← {} for each live interval i, in order of increasing start point do ExpireOldIntervals(i) if length(active) = R then SpillAtInterval(i) else register[i] ← a register removed from pool of free registers add i to active, sorted by increasing end point
ExpireOldIntervals(i) for each interval j in active, in order of increasing end point do if endpoint[j] ≥ startpoint[i] then return remove j from active add register[j] to pool of free registers
SpillAtInterval(i) spill ← last interval in active if endpoint[spill] > endpoint[i] then register[i] ← register[spill] location[spill] ← new stack location remove spill from active add i to active, sorted by increasing end point else location[i] ← new stack location
Drawbacks and further improvements