--- /dev/null
+Register allocation in Subzero
+==============================
+
+Introduction
+------------
+
+`Subzero
+<https://chromium.googlesource.com/native_client/pnacl-subzero/+/master/docs/DESIGN.rst>`_
+is a fast code generator that translates architecture-independent `PNaCl bitcode
+<https://developer.chrome.com/native-client/reference/pnacl-bitcode-abi>`_ 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 <ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF>`_ 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
+<ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF>`_. 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.
OSDN Git Service
