Register allocation in Subzero ============================== Introduction ------------ `Subzero `_ is a fast code generator that translates architecture-independent `PNaCl bitcode `_ into architecture-specific machine code. PNaCl bitcode is LLVM bitcode that has been simplified (e.g. weird-width primitive types like 57-bit integers are not allowed) and has had architecture-independent optimizations already applied. Subzero aims to generate high-quality code as fast as practical, and as such Subzero needs to make tradeoffs between compilation speed and output code quality. In Subzero, we have found register allocation to be one of the most important optimizations toward achieving the best code quality, which is in tension with register allocation's reputation for being complex and expensive. Linear-scan register allocation is a modern favorite for getting fairly good register allocation at relatively low cost. Subzero uses linear-scan for its core register allocator, with a few internal modifications to improve its effectiveness (specifically: register preference, register overlap, and register aliases). Subzero also does a few high-level things on top of its core register allocator to improve overall effectiveness (specifically: repeat until convergence, delayed phi lowering, and local live range splitting). What we describe here are techniques that have worked well for Subzero, in the context of its particular intermediate representation (IR) and compilation strategy. Some of these techniques may not be applicable to another compiler, depending on its particular IR and compilation strategy. Some key concepts in Subzero are the following: - Subzero's ``Variable`` operand is an operand that resides either on the stack or in a physical register. A Variable can be tagged as *must-have-register* or *must-not-have-register*, but its default is *may-have-register*. All uses of the Variable map to the same physical register or stack location. - Basic lowering is done before register allocation. Lowering is the process of translating PNaCl bitcode instructions into native instructions. Sometimes a native instruction, like the x86 ``add`` instruction, allows one of its Variable operands to be either in a physical register or on the stack, in which case the lowering is relatively simple. But if the lowered instruction requires the operand to be in a physical register, we generate code that copies the Variable into a *must-have-register* temporary, and then use that temporary in the lowered instruction. - Instructions within a basic block appear in a linearized order (as opposed to something like a directed acyclic graph of dependency edges). - An instruction has 0 or 1 *dest* Variables and an arbitrary (but usually small) number of *source* Variables. Assuming SSA form, the instruction begins the live range of the dest Variable, and may end the live range of one or more of the source Variables. Executive summary ----------------- - Liveness analysis and live range construction are prerequisites for register allocation. Without careful attention, they can be potentially very expensive, especially when the number of variables and basic blocks gets very large. Subzero uses some clever data structures to take advantage of the sparsity of the data, resulting in stable performance as function size scales up. This means that the proportion of compilation time spent on liveness analysis stays roughly the same. - The core of Subzero's register allocator is taken from `Mössenböck and Pfeiffer's paper `_ on linear-scan register allocation. - We enhance the core algorithm with a good automatic preference mechanism when more than one register is available, to try to minimize register shuffling. - We also enhance it to allow overlapping live ranges to share the same register, when one variable is recognized as a read-only copy of the other. - We deal with register aliasing in a clean and general fashion. Register aliasing is when e.g. 16-bit architectural registers share some bits with their 32-bit counterparts, or 64-bit registers are actually pairs of 32-bit registers. - We improve register allocation by rerunning the algorithm on likely candidates that didn't get registers during the previous iteration, without imposing much additional cost. - The main register allocation is done before phi lowering, because phi lowering imposes early and unnecessary ordering constraints on the resulting assigments, which create spurious interferences in live ranges. - Within each basic block, we aggressively split each variable's live range at every use, so that portions of the live range can get registers even if the whole live range can't. Doing this separately for each basic block avoids merge complications, and keeps liveness analysis and register allocation fast by fitting well into the sparsity optimizations of their data structures. Liveness analysis ----------------- With respect to register allocation, the main purpose of liveness analysis is to calculate the live range of each variable. The live range is represented as a set of instruction number ranges. Instruction numbers within a basic block must be monotonically increasing, and the instruction ranges of two different basic blocks must not overlap. Basic liveness ^^^^^^^^^^^^^^ Liveness analysis is a straightforward dataflow algorithm. For each basic block, we keep track of the live-in and live-out set, i.e. the set of variables that are live coming into or going out of the basic block. Processing of a basic block starts by initializing a temporary set as the union of the live-in sets of the basic block's successor blocks. (This basic block's live-out set is captured as the initial value of the temporary set.) Then each instruction of the basic block is processed in reverse order. All the source variables of the instruction are marked as live, by adding them to the temporary set, and the dest variable of the instruction (if any) is marked as not-live, by removing it from the temporary set. When we finish processing all of the block's instructions, we add/union the temporary set into the basic block's live-in set. If this changes the basic block's live-in set, then we mark all of this basic block's predecessor blocks to be reprocessed. Then we repeat for other basic blocks until convergence, i.e. no more basic blocks are marked to be reprocessed. If basic blocks are processed in reverse topological order, then the number of times each basic block need to be reprocessed is generally its loop nest depth. The result of this pass is the live-in and live-out set for each basic block. With so many set operations, choice of data structure is crucial for performance. We tried a few options, and found that a simple dense bit vector works best. This keeps the per-instruction cost very low. However, we found that when the function gets very large, merging and copying bit vectors at basic block boundaries dominates the cost. This is due to the number of variables (hence the bit vector size) and the number of basic blocks getting large. A simple enhancement brought this under control in Subzero. It turns out that the vast majority of variables are referenced, and therefore live, only in a single basic block. This is largely due to the SSA form of PNaCl bitcode. To take advantage of this, we partition variables by single-block versus multi-block liveness. Multi-block variables get lower-numbered bit vector indexes, and single-block variables get higher-number indexes. Single-block bit vector indexes are reused across different basic blocks. As such, the size of live-in and live-out bit vectors is limited to the number of multi-block variables, and the temporary set's size can be limited to that plus the largest number of single-block variables across all basic blocks. For the purpose of live range construction, we also need to track definitions (LiveBegin) and last-uses (LiveEnd) of variables used within instructions of the basic block. These are easy to detect while processing the instructions; data structure choices are described below. Live range construction ^^^^^^^^^^^^^^^^^^^^^^^ After the live-in and live-out sets are calculated, we construct each variable's live range (as an ordered list of instruction ranges, described above). We do this by considering the live-in and live-out sets, combined with LiveBegin and LiveEnd information. This is done separately for each basic block. As before, we need to take advantage of sparsity of variable uses across basic blocks, to avoid overly copying/merging data structures. The following is what worked well for Subzero (after trying several other options). The basic liveness pass, described above, keeps track of when a variable's live range begins or ends within the block. LiveBegin and LiveEnd are unordered vectors where each element is a pair of the variable and the instruction number, representing that the particular variable's live range begins or ends at the particular instruction. When the liveness pass finds a variable whose live range begins or ends, it appends and entry to LiveBegin or LiveEnd. During live range construction, the LiveBegin and LiveEnd vectors are sorted by variable number. Then we iterate across both vectors in parallel. If a variable appears in both LiveBegin and LiveEnd, then its live range is entirely within this block. If it appears in only LiveBegin, then its live range starts here and extends through the end of the block. If it appears in only LiveEnd, then its live range starts at the beginning of the block and ends here. (Note that this only covers the live range within this block, and this process is repeated across all blocks.) It is also possible that a variable is live within this block but its live range does not begin or end in this block. These variables are identified simply by taking the intersection of the live-in and live-out sets. As a result of these data structures, performance of liveness analysis and live range construction tend to be stable across small, medium, and large functions, as measured by a fairly consistent proportion of total compilation time spent on the liveness passes. Linear-scan register allocation ------------------------------- The basis of Subzero's register allocator is the allocator described by Hanspeter Mössenböck and Michael Pfeiffer in `Linear Scan Register Allocation in the Context of SSA Form and Register Constraints `_. It allows live ranges to be a union of intervals rather than a single conservative interval, and it allows pre-coloring of variables with specific physical registers. The paper suggests an approach of aggressively coalescing variables across Phi instructions (i.e., trying to force Phi source and dest variables to have the same register assignment), but we omit that in favor of the more natural preference mechanism described below. We found the paper quite remarkable in that a straightforward implementation of its pseudo-code led to an entirely correct register allocator. The only thing we found in the specification that was even close to a mistake is that it was too aggressive in evicting inactive ranges in the "else" clause of the AssignMemLoc routine. An inactive range only needs to be evicted if it actually overlaps the current range being considered, whereas the paper evicts it unconditionally. (Search for "original paper" in Subzero's register allocator source code.) Register preference ------------------- The linear-scan algorithm from the paper talks about choosing an available register, but isn't specific on how to choose among several available registers. The simplest approach is to just choose the first available register, e.g. the lowest-numbered register. Often a better choice is possible. Specifically, if variable ``V`` is assigned in an instruction ``V=f(S1,S2,...)`` with source variables ``S1,S2,...``, and that instruction ends the live range of one of those source variables ``Sn``, and ``Sn`` was assigned a register, then ``Sn``'s register is usually a good choice for ``V``. This is especially true when the instruction is a simple assignment, because an assignment where the dest and source variables end up with the same register can be trivially elided, reducing the amount of register-shuffling code. This requires being able to find and inspect a variable's defining instruction, which is not an assumption in the original paper but is easily tracked in practice. Register overlap ---------------- Because Subzero does register allocation after basic lowering, the lowering has to be prepared for the possibility of any given program variable not getting a physical register. It does this by introducing *must-have-register* temporary variables, and copies the program variable into the temporary to ensure that register requirements in the target instruction are met. In many cases, the program variable and temporary variable have overlapping live ranges, and would be forced to have different registers even if the temporary variable is effectively a read-only copy of the program variable. We recognize this when the program variable has no definitions within the temporary variable's live range, and the temporary variable has no definitions within the program variable's live range with the exception of the copy assignment. This analysis is done as part of register preference detection. The main impact on the linear-scan implementation is that instead of setting/resetting a boolean flag to indicate whether a register is free or in use, we increment/decrement a number-of-uses counter. Register aliases ---------------- Sometimes registers of different register classes partially overlap. For example, in x86, registers ``al`` and ``ah`` alias ``ax`` (though they don't alias each other), and all three alias ``eax`` and ``rax``. And in ARM, registers ``s0`` and ``s1`` (which are single-precision floating-point registers) alias ``d0`` (double-precision floating-point), and registers ``d0`` and ``d1`` alias ``q0`` (128-bit vector register). The linear-scan paper doesn't address this issue; it assumes that all registers are independent. A simple solution is to essentially avoid aliasing by disallowing a subset of the registers, but there is obviously a reduction in code quality when e.g. half of the registers are taken away. Subzero handles this more elegantly. For each register, we keep a bitmask indicating which registers alias/conflict with it. For example, in x86, ``ah``'s alias set is ``ah``, ``ax``, ``eax``, and ``rax`` (but not ``al``), and in ARM, ``s1``'s alias set is ``s1``, ``d0``, and ``q0``. Whenever we want to mark a register as being used or released, we do the same for all of its aliases. Before implementing this, we were a bit apprehensive about the compile-time performance impact. Instead of setting one bit in a bit vector or decrementing one counter, this generally needs to be done in a loop that iterates over all aliases. Fortunately, this seemed to make very little difference in performance, as the bulk of the cost ends up being in live range overlap computations, which are not affected by register aliasing. Repeat until convergence ------------------------ Sometimes the linear-scan algorithm makes a register assignment only to later revoke it in favor of a higher-priority variable, but it turns out that a different initial register choice would not have been revoked. For relatively low compile-time cost, we can give those variables another chance. During register allocation, we keep track of the revoked variables and then do another round of register allocation targeted only to that set. We repeat until no new register assignments are made, which is usually just a handful of successively cheaper iterations. Another approach would be to repeat register allocation for *all* variables that haven't had a register assigned (rather than variables that got a register that was subsequently revoked), but our experience is that this greatly increases compile-time cost, with little or no code quality gain. Delayed Phi lowering -------------------- The linear-scan algorithm works for phi instructions as well as regular instructions, but it is tempting to lower phi instructions into non-SSA assignments before register allocation, so that register allocation need only happen once. Unfortunately, simple phi lowering imposes an arbitrary ordering on the resulting assignments that can cause artificial overlap/interference between lowered assignments, and can lead to worse register allocation decisions. As a simple example, consider these two phi instructions which are semantically unordered:: A = phi(B) // B's live range ends here C = phi(D) // D's live range ends here A straightforward lowering might yield:: A = B // end of B's live range C = D // end of D's live range The potential problem here is that A and D's live ranges overlap, and so they are prevented from having the same register. Swapping the order of lowered assignments fixes that (but then B and C would overlap), but we can't really know which is better until after register allocation. Subzero deals with this by doing the main register allocation before phi lowering, followed by phi lowering, and finally a special register allocation pass limited to the new lowered assignments. Phi lowering considers the phi operands separately for each predecessor edge, and starts by finding a topological sort of the Phi instructions, such that assignments can be executed in that order without violating dependencies on registers or stack locations. If a topological sort is not possible due to a cycle, the cycle is broken by introducing a temporary, e.g. ``A=B;B=C;C=A`` can become ``T=A;A=B;B=C;C=T``. The topological order is tuned to favor freeing up registers early to reduce register pressure. It then lowers the linearized assignments into machine instructions (which may require extra physical registers e.g. to copy from one stack location to another), and finally runs the register allocator limited to those instructions. In rare cases, the register allocator may fail on some *must-have-register* variable, because register pressure is too high to satisfy requirements arising from cycle-breaking temporaries and registers required for stack-to-stack copies. In this case, we have to find a register with no active uses within the variable's live range, and actively spill/restore that register around the live range. This makes the code quality suffer and may be slow to implement depending on compiler data structures, but in practice we find the situation to be vanishingly rare and so not really worth optimizing. Local live range splitting -------------------------- The basic linear-scan algorithm has an "all-or-nothing" policy: a variable gets a register for its entire live range, or not at all. This is unfortunate when a variable has many uses close together, but ultimately a large enough live range to prevent register assignment. Another bad example is on x86 where all vector and floating-point registers (the ``xmm`` registers) are killed by call instructions, per the x86 call ABI, so such variables are completely prevented from having a register when their live ranges contain a call instruction. The general solution here is some policy for splitting live ranges. A variable can be split into multiple copies and each can be register-allocated separately. The complication comes in finding a sane policy for where and when to split variables such that complexity doesn't explode, and how to join the different values at merge points. Subzero implements aggressive block-local splitting of variables. Each basic block is handled separately and independently. Within the block, we maintain a table ``T`` that maps each variable ``V`` to its split version ``T[V]``, with every variable ``V``'s initial state set (implicitly) as ``T[V]=V``. For each instruction in the block, and for each *may-have-register* variable ``V`` in the instruction, we do the following: - Replace all uses of ``V`` in the instruction with ``T[V]``. - Create a new split variable ``V'``. - Add a new assignment ``V'=T[V]``, placing it adjacent to (either immediately before or immediately after) the current instruction. - Update ``T[V]`` to be ``V'``. This leads to a chain of copies of ``V`` through the block, linked by assignment instructions. The live ranges of these copies are usually much smaller, and more likely to get registers. In fact, because of the preference mechanism described above, they are likely to get the same register whenever possible. One obvious question comes up: won't this proliferation of new variables cause an explosion in the running time of liveness analysis and register allocation? As it turns out, not really. First, for register allocation, the cost tends to be dominated by live range overlap computations, whose cost is roughly proportional to the size of the live range. All the new variable copies' live ranges sum up to the original variable's live range, so the cost isn't vastly greater. Second, for liveness analysis, the cost is dominated by merging bit vectors corresponding to the set of variables that have multi-block liveness. All the new copies are guaranteed to be single-block, so the main additional cost is that of processing the new assignments. There's one other key issue here. The original variable and all of its copies need to be "linked", in the sense that all of these variables that get a stack slot (because they didn't get a register) are guaranteed to have the same stack slot. This way, we can avoid generating any code related to ``V'=V`` when neither gets a register. In addition, we can elide instructions that write a value to a stack slot that is linked to another stack slot, because that is guaranteed to be just rewriting the same value to the stack.