Source code

Revision control

Copy as Markdown

Other Tools

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
///////////////////////////////////////////////////////////////////////////////
// //
// Documentation. Code starts about 670 lines down from here. //
// //
///////////////////////////////////////////////////////////////////////////////
// [SMDOC] An overview of Ion's register allocator
//
// The intent of this documentation is to give maintainers a map with which to
// navigate the allocator. As further understanding is obtained, it should be
// added to this overview.
//
// Where possible, invariants are stated and are marked "(INVAR)". Many
// details are omitted because their workings are currently unknown. In
// particular, this overview doesn't explain how Intel-style "modify" (tied)
// operands are handled. Facts or invariants that are speculative -- believed
// to be true, but not verified at the time of writing -- are marked "(SPEC)".
//
// The various concepts are interdependent, so a single forwards reading of the
// following won't make much sense. Many concepts are explained only after
// they are mentioned.
//
// Where possible examples are shown. Without those the description is
// excessively abstract.
//
// Names of the form ::name mean BacktrackingAllocator::name.
//
// The description falls into two sections:
//
// * Section 1: A tour of the data structures
// * Section 2: The core allocation loop, and bundle splitting
//
// The allocator sometimes produces poor allocations, with excessive spilling
// and register-to-register moves (bugs 1752520, bug 1714280 bug 1746596).
// Work in bug 1752582 shows we can get better quality allocations from this
// framework without having to make any large (conceptual) changes, by having
// better splitting heuristics.
//
// written at the same time as these comments. It describes some improvements
// we could make to our splitting heuristics, particularly in the presence of
// loops and calls, and shows why the current implementation sometimes produces
// excessive spilling. It builds on the commentary in this SMDOC.
//
//
// Top level pipeline
// ~~~~~~~~~~~~~~~~~~
// There are three major phases in allocation. They run sequentially, at a
// per-function granularity.
//
// (1) Liveness analysis and bundle formation
// (2) Bundle allocation and last-chance allocation
// (3) Rewriting the function to create MoveGroups and to "install"
// the allocation
//
// The input language (LIR) is in SSA form, and phases (1) and (3) depend on
// that SSAness. Without it the allocator wouldn't work.
//
// The top level function is ::go. The phases are divided into functions as
// follows:
//
// (1) ::buildLivenessInfo, ::mergeAndQueueRegisters
// (2) ::processBundle, ::tryAllocatingRegistersForSpillBundles,
// ::pickStackSlots
// (3) ::createMoveGroupsFromLiveRangeTransitions, ::installAllocationsInLIR,
// ::populateSafepoints, ::annotateMoveGroups
//
// The code in this file is structured as much as possible in the same sequence
// as flow through the pipeline. Hence, top level function ::go is right at
// the end. Where a function depends on helper function(s), the helpers appear
// first.
//
//
// ========================================================================
// ==== ====
// ==== Section 1: A tour of the data structures ====
// ==== ====
// ========================================================================
//
// Here are the key data structures necessary for understanding what follows.
//
// Some basic data structures
// ~~~~~~~~~~~~~~~~~~~~~~~~~~
//
// CodePosition
// ------------
// A CodePosition is an unsigned 32-bit int that indicates an instruction index
// in the incoming LIR. Each LIR actually has two code positions, one to
// denote the "input" point (where, one might imagine, the operands are read,
// at least useAtStart ones) and the "output" point, where operands are
// written. Eg:
//
// Block 0 [successor 2] [successor 1]
// 2-3 WasmParameter [def v1<g>:r14]
// 4-5 WasmCall [use v1:F:r14]
// 6-7 WasmLoadTls [def v2<o>] [use v1:R]
// 8-9 WasmNullConstant [def v3<o>]
// 10-11 Compare [def v4<i>] [use v2:R] [use v3:A]
// 12-13 TestIAndBranch [use v4:R]
//
// So for example the WasmLoadTls insn has its input CodePosition as 6 and
// output point as 7. Input points are even numbered, output points are odd
// numbered. CodePositions 0 and 1 never appear, because LIR instruction IDs
// start at 1. Indeed, CodePosition 0 is assumed to be invalid and hence is
// used as a marker for "unusual conditions" in various places.
//
// Phi nodes exist in the instruction stream too. They always appear at the
// start of blocks (of course) (SPEC), but their start and end points are
// printed for the group as a whole. This is to emphasise that they are really
// parallel assignments and that printing them sequentially would misleadingly
// imply that they are executed sequentially. Example:
//
// Block 6 [successor 7] [successor 8]
// 56-59 Phi [def v19<o>] [use v2:A] [use v5:A] [use v13:A]
// 56-59 Phi [def v20<o>] [use v7:A] [use v14:A] [use v12:A]
// 60-61 WasmLoadSlot [def v21<o>] [use v1:R]
// 62-63 Compare [def v22<i>] [use v20:R] [use v21:A]
// 64-65 TestIAndBranch [use v22:R]
//
// See that both Phis are printed with limits 56-59, even though they are
// stored in the LIR array like regular LIRs and so have code points 56-57 and
// 58-59 in reality.
//
// The process of allocation adds MoveGroup LIRs to the function. Each
// incoming LIR has its own private list of MoveGroups (actually, 3 lists; two
// for moves that conceptually take place before the instruction, and one for
// moves after it). Hence the CodePositions for LIRs (the "62-63", etc, above)
// do not change as a result of allocation.
//
// Virtual registers (vregs) in LIR
// --------------------------------
// The MIR from which the LIR is derived, is standard SSA. That SSAness is
// carried through into the LIR (SPEC). In the examples here, LIR SSA names
// (virtual registers, a.k.a. vregs) are printed as "v<number>". v0 never
// appears and is presumed to be a special value, perhaps "invalid" (SPEC).
//
// The allocator core has a type VirtualRegister, but this is private to the
// allocator and not part of the LIR. It carries far more information than
// merely the name of the vreg. The allocator creates one VirtualRegister
// structure for each vreg in the LIR.
//
// LDefinition and LUse
// --------------------
// These are part of the incoming LIR. Each LIR instruction defines zero or
// more values, and contains one LDefinition for each defined value (SPEC).
// Each instruction has zero or more input operands, each of which has its own
// LUse (SPEC).
//
// Both LDefinition and LUse hold both a virtual register name and, in general,
// a real (physical) register identity. The incoming LIR has the real register
// fields unset, except in places where the incoming LIR has fixed register
// constraints (SPEC). Phase 3 of allocation will visit all of the
// LDefinitions and LUses so as to write into the real register fields the
// decisions made by the allocator. For LUses, this is done by overwriting the
// complete LUse with a different LAllocation, for example LStackSlot. That's
// possible because LUse is a child class of LAllocation.
//
// This action of reading and then later updating LDefinition/LUses is the core
// of the allocator's interface to the outside world.
//
// To make visiting of LDefinitions/LUses possible, the allocator doesn't work
// with LDefinition and LUse directly. Rather it has pointers to them
// (VirtualRegister::def_, UsePosition::use_). Hence Phase 3 can modify the
// LIR in-place.
//
// (INVARs, all SPEC):
//
// - The collective VirtualRegister::def_ values should be unique, and there
// should be a 1:1 mapping between the VirtualRegister::def_ values and the
// LDefinitions in the LIR. (So that the LIR LDefinition has exactly one
// VirtualRegister::def_ to track it). But only for the valid LDefinitions.
// If isBogusTemp() is true, the definition is invalid and doesn't have a
// vreg.
//
// - The same for uses: there must be a 1:1 correspondence between the
// CodePosition::use_ values and the LIR LUses.
//
// - The allocation process must preserve these 1:1 mappings. That implies
// (weaker) that the number of VirtualRegisters and of UsePositions must
// remain constant through allocation. (Eg: losing them would mean that some
// LIR def or use would necessarily not get annotated with its final
// allocation decision. Duplicating them would lead to the possibility of
// conflicting allocation decisions.)
//
// Other comments regarding LIR
// ----------------------------
// The incoming LIR is structured into basic blocks and a CFG, as one would
// expect. These (insns, block boundaries, block edges etc) are available
// through the BacktrackingAllocator object. They are important for Phases 1
// and 3 but not for Phase 2.
//
// Phase 3 "rewrites" the input LIR so as to "install" the final allocation.
// It has to insert MoveGroup instructions, but that isn't done by pushing them
// into the instruction array. Rather, each LIR has 3 auxiliary sets of
// MoveGroups (SPEC): two that "happen" conceptually before the LIR, and one
// that happens after it. The rewriter inserts MoveGroups into one of these 3
// sets, and later code generation phases presumably insert the sets (suitably
// translated) into the final machine code (SPEC).
//
//
// Key data structures: LiveRange, VirtualRegister and LiveBundle
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
// These three have central roles in allocation. Of them, LiveRange is the
// most central. VirtualRegister is conceptually important throughout, but
// appears less frequently in the allocator code. LiveBundle is important only
// in Phase 2 (where it is central) and at the end of Phase 1, but plays no
// role in Phase 3.
//
// It's important to understand that LiveRange and VirtualRegister correspond
// to concepts visible in the incoming LIR, which is in SSA form. LiveBundle
// by comparison is related to neither the structure of LIR nor its SSA
// properties. Instead, LiveBundle is an essentially adminstrative structure
// used to accelerate allocation and to implement a crude form of
// move-coalescing.
//
// VirtualRegisters and LiveRanges are (almost) static throughout the process,
// because they reflect aspects of the incoming LIR, which does not change.
// LiveBundles by contrast come and go; they are created, but may be split up
// into new bundles, and old ones abandoned.
//
// Each LiveRange is a member of two different lists.
//
// A VirtualRegister (described in detail below) has a vector of LiveRanges that
// it "owns".
//
// A LiveBundle (also described below) has a linked list of LiveRanges that it
// "owns".
//
// Hence each LiveRange is "owned" by one VirtualRegister and one LiveBundle.
// LiveRanges may have their owning LiveBundle changed as a result of
// splitting. By contrast a LiveRange stays with its "owning" VirtualRegister
// for ever.
//
// A few LiveRanges have no VirtualRegister. This is used to implement
// register spilling for calls. Each physical register that's not preserved
// across a call has a small range that covers the call. It is
// ::buildLivenessInfo that adds these small ranges.
//
// Iterating over every VirtualRegister in the system is a common operation and
// is straightforward because (somewhat redundantly?) the LIRGraph knows the
// number of vregs, and more importantly because BacktrackingAllocator::vregs
// is a vector of all VirtualRegisters. By contrast iterating over every
// LiveBundle in the system is more complex because there is no top-level
// registry of them. It is still possible though. See ::dumpLiveRangesByVReg
// and ::dumpLiveRangesByBundle for example code.
//
// LiveRange
// ---------
// Fundamentally, a LiveRange (often written just "range") is a request for
// storage of a LIR vreg for some contiguous sequence of LIRs. A LiveRange
// generally covers only a fraction of a vreg's overall lifetime, so multiple
// LiveRanges are generally needed to cover the whole lifetime.
//
// A LiveRange contains (amongst other things):
//
// * the vreg for which it is for, as a VirtualRegister*
//
// * the range of CodePositions for which it is for, as a LiveRange::Range
//
// * auxiliary information:
//
// - a boolean that indicates whether this LiveRange defines a value for the
// vreg. If so, that definition is regarded as taking place at the first
// CodePoint of the range.
//
// - a linked list of uses of the vreg within this range. Each use is a pair
// of a CodePosition and an LUse*. (INVAR): the uses are maintained in
// increasing order of CodePosition. Multiple uses at the same
// CodePosition are permitted, since that is necessary to represent an LIR
// that uses the same vreg in more than one of its operand slots.
//
// Some important facts about LiveRanges are best illustrated with examples:
//
// v25 75-82 { 75_def:R 78_v25:A 82_v25:A }
//
// This LiveRange is for vreg v25. The value is defined at CodePosition 75,
// with the LIR requiring that it be in a register. It is used twice at
// positions 78 and 82, both with no constraints (A meaning "any"). The range
// runs from position 75 to 82 inclusive. Note however that LiveRange::Range
// uses non-inclusive range ends; hence its .to field would be 83, not 82.
//
// v26 84-85 { 85_v26:R }
//
// This LiveRange is for vreg v26. Here, there's only a single use of it at
// position 85. Presumably it is defined in some other LiveRange.
//
// v19 74-79 { }
//
// This LiveRange is for vreg v19. There is no def and no uses, so at first
// glance this seems redundant. But it isn't: it still expresses a request for
// storage for v19 across 74-79, because Phase 1 regards v19 as being live in
// this range (meaning: having a value that, if changed in this range, would
// cause the program to fail).
//
// Other points:
//
// * (INVAR) Each vreg/VirtualRegister has at least one LiveRange.
//
// * (INVAR) Exactly one LiveRange of a vreg gives a definition for the value.
// All other LiveRanges must consist only of uses (including zero uses, for a
// "flow-though" range as mentioned above). This requirement follows from
// the fact that LIR is in SSA form.
//
// * It follows from this, that the LiveRanges for a VirtualRegister must form
// a tree, where the parent-child relationship is "control flows directly
// from a parent LiveRange (anywhere in the LiveRange) to a child LiveRange
// (start)". The entire tree carries only one value. This is a use of
// SSAness in the allocator which is fundamental: without SSA input, this
// design would not work.
//
// The root node (LiveRange) in the tree must be one that defines the value,
// and all other nodes must only use or be flow-throughs for the value. It's
// OK for LiveRanges in the tree to overlap, providing that there is a unique
// root node -- otherwise it would be unclear which LiveRange provides the
// value.
//
// The function ::createMoveGroupsFromLiveRangeTransitions runs after all
// LiveBundles have been allocated. It visits each VirtualRegister tree in
// turn. For every parent->child edge in a tree, it creates a MoveGroup that
// copies the value from the parent into the child -- this is how the
// allocator decides where to put MoveGroups. There are various other
// details not described here.
//
// * It's important to understand that a LiveRange carries no meaning about
// control flow beyond that implied by the SSA (hence, dominance)
// relationship between a def and its uses. In particular, there's no
// implication that execution "flowing into" the start of the range implies
// that it will "flow out" of the end. Or that any particular use will or
// will not be executed.
//
// * (very SPEC) Indeed, even if a range has a def, there's no implication that
// a use later in the range will have been immediately preceded by execution
// of the def. It could be that the def is executed, flow jumps somewhere
// else, and later jumps back into the middle of the range, where there are
// then some uses.
//
// * Uses of a vreg by a phi node are not mentioned in the use list of a
// LiveRange. The reasons for this are unknown, but it is speculated that
// this is because we don't need to know about phi uses where we use the list
// of positions. See comments on VirtualRegister::usedByPhi_.
//
// * Similarly, a definition of a vreg by a phi node is not regarded as being a
// definition point (why not?), at least as the view of
// LiveRange::hasDefinition_.
//
// * LiveRanges that nevertheless include a phi-defined value have their first
// point set to the first of the block of phis, even if the var isn't defined
// by that specific phi. Eg:
//
// Block 6 [successor 7] [successor 8]
// 56-59 Phi [def v19<o>] [use v2:A] [use v5:A] [use v13:A]
// 56-59 Phi [def v20<o>] [use v7:A] [use v14:A] [use v12:A]
// 60-61 WasmLoadSlot [def v21<o>] [use v1:R]
// 62-63 Compare [def v22<i>] [use v20:R] [use v21:A]
//
// The relevant live range for v20 is
//
// v20 56-65 { 63_v20:R }
//
// Observe that it starts at 56, not 58.
//
// VirtualRegister
// ---------------
// Each VirtualRegister is associated with an SSA value created by the LIR.
// Fundamentally it is a container to hold all of the LiveRanges that together
// indicate where the value must be kept live. The live ranges are stored in a
// vector, VirtualRegister::ranges_. The set of LiveRanges must logically form
// a tree, rooted at the LiveRange which defines the value.
//
// The live ranges are sorted in order of decreasing start point by construction
// after buildLivenessInfo until the main register allocation loops. At that
// point they can become unsorted and this is important for performance because
// it allows the core allocation code to add/remove ranges more efficiently.
// After all bundles are allocated, sortVirtualRegisterRanges is called to
// ensure the ranges are sorted again.
//
// There are various auxiliary fields, most importantly the LIR node and the
// associated LDefinition that define the value.
//
// It is OK, and quite common, for LiveRanges of a VirtualRegister to overlap.
// The effect will be that, in an overlapped area, there are two storage
// locations holding the value. This is OK -- although wasteful of storage
// resources -- because the SSAness means the value must be the same in both
// locations. Hence there's no questions like "which LiveRange holds the most
// up-to-date value?", since it's all just one value anyway.
//
// Note by contrast, it is *not* OK for the LiveRanges of a LiveBundle to
// overlap.
//
// LiveBundle
// ----------
// Similar to VirtualRegister, a LiveBundle is also, fundamentally, a container
// for a set of LiveRanges. The set is stored as a linked list, rooted at
// LiveBundle::ranges_.
//
// However, the similarity ends there:
//
// * The LiveRanges in a LiveBundle absolutely must not overlap. They must
// indicate disjoint sets of CodePositions, and must be stored in the list in
// order of increasing CodePosition. Because of the no-overlap requirement,
// these ranges form a total ordering regardless of whether one uses the
// LiveRange::Range::from_ or ::to_ fields for comparison.
//
// * The LiveRanges in a LiveBundle can otherwise be entirely arbitrary and
// unrelated. They can be from different VirtualRegisters and can have no
// particular mutual significance w.r.t. the SSAness or structure of the
// input LIR.
//
// LiveBundles are the fundamental unit of allocation. The allocator attempts
// to find a single storage location that will work for all LiveRanges in the
// bundle. That's why the ranges must not overlap. If no such location can be
// found, the allocator may decide to split the bundle into multiple smaller
// bundles. Each of those may be allocated independently.
//
// The other really important field is LiveBundle::alloc_, indicating the
// chosen storage location.
//
// Here's an example, for a LiveBundle before it has been allocated:
//
// LB2(parent=none v3 8-21 { 16_v3:A } ## v3 24-25 { 25_v3:F:xmm0 })
//
// LB merely indicates "LiveBundle", and the 2 is the id_ value (see
// below). This bundle has two LiveRanges
//
// v3 8-21 { 16_v3:A }
// v3 24-25 { 25_v3:F:xmm0 }
//
// both of which (coincidentally) are for the same VirtualRegister, v3.The
// second LiveRange has a fixed use in `xmm0`, whilst the first one doesn't
// care (A meaning "any location") so the allocator *could* choose `xmm0` for
// the bundle as a whole.
//
// One might ask: why bother with LiveBundle at all? After all, it would be
// possible to get correct allocations by allocating each LiveRange
// individually, then leaving ::createMoveGroupsFromLiveRangeTransitions to add
// MoveGroups to join up LiveRanges that form each SSA value tree (that is,
// LiveRanges belonging to each VirtualRegister).
//
// There are two reasons:
//
// (1) By putting multiple LiveRanges into each LiveBundle, we can end up with
// many fewer LiveBundles than LiveRanges. Since the cost of allocating a
// LiveBundle is substantially less than the cost of allocating each of its
// LiveRanges individually, the allocator will run faster.
//
// (2) It provides a crude form of move-coalescing. There are situations where
// it would be beneficial, although not mandatory, to have two LiveRanges
// assigned to the same storage unit. Most importantly: (a) LiveRanges
// that form all of the inputs, and the output, of a phi node. (b)
// LiveRanges for the output and first-operand values in the case where we
// are targetting Intel-style instructions.
//
// In such cases, if the bundle can be allocated as-is, then no extra moves
// are necessary. If not (and the bundle is split), then
// ::createMoveGroupsFromLiveRangeTransitions will later fix things up by
// inserting MoveGroups in the right places.
//
// Merging of LiveRanges into LiveBundles is done in Phase 1, by
// ::mergeAndQueueRegisters, after liveness analysis (which generates only
// LiveRanges).
//
// For the bundle mentioned above, viz
//
// LB2(parent=none v3 8-21 { 16_v3:A } ## v3 24-25 { 25_v3:F:xmm0 })
//
// the allocator did not in the end choose to allocate it to `xmm0`. Instead
// it was split into two bundles, LB6 (a "spill parent", or root node in the
// trees described above), and LB9, a leaf node, that points to its parent LB6:
//
// LB6(parent=none v3 8-21 %xmm1.s { 16_v3:A } ## v3 24-25 %xmm1.s { })
// LB9(parent=LB6 v3 24-25 %xmm0.s { 25_v3:F:rax })
//
// Note that both bundles now have an allocation, and that is printed,
// redundantly, for each LiveRange in the bundle -- hence the repeated
// `%xmm1.s` in the lines above. Since all LiveRanges in a LiveBundle must be
// allocated to the same storage location, we never expect to see output like
// this
//
// LB6(parent=none v3 8-21 %xmm1.s { 16_v3:A } ## v3 24-25 %xmm2.s { })
//
// and that is in any case impossible, since a LiveRange doesn't have an
// LAllocation field. Instead it has a pointer to its LiveBundle, and the
// LAllocation lives in the LiveBundle.
//
// For the resulting allocation (LB6 and LB9), all the LiveRanges are use-only
// or flow-through. There are no definitions. But they are all for the same
// VirtualReg, v3, so they all have the same value. An important question is
// where they "get their value from". The answer is that
// ::createMoveGroupsFromLiveRangeTransitions will have to insert suitable
// MoveGroups so that each LiveRange for v3 can "acquire" the value from a
// previously-executed LiveRange, except for the range that defines it. The
// defining LiveRange is not visible here; either it is in some other
// LiveBundle, not shown, or (more likely) the value is defined by a phi-node,
// in which case, as mentioned previously, it is not shown as having an
// explicit definition in any LiveRange.
//
// LiveBundles also have a `SpillSet* spill_` field (see below) and a
// `LiveBundle* spillParent_`. The latter is used to ensure that all bundles
// originating from an "original" bundle share the same spill slot. The
// `spillParent_` pointers can be thought of creating a 1-level tree, where
// each node points at its parent. Since the tree can be only 1-level, the
// following invariant (INVAR) must be maintained:
//
// * if a LiveBundle has a non-null spillParent_ field, then it is a leaf node,
// and no other LiveBundle can point at this one.
//
// * else (it has a null spillParent_ field) it is a root node, and so other
// LiveBundles may point at it.
//
// LiveBundle has a 32-bit `id_` field. This is used for debug printing, and
// makes it easier to see parent-child relationships induced by the
// `spillParent_` pointers. It's also used for sorting live ranges in
// VirtualRegister::sortRanges.
//
// The "life cycle" of LiveBundles is described in Section 2 below.
//
//
// Secondary data structures: SpillSet, Requirement
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
// SpillSet
// --------
// A SpillSet is a container for a set of LiveBundles that have been spilled,
// all of which are assigned the same spill slot. The set is represented as a
// vector of points to LiveBundles. SpillSet also contains the identity of the
// spill slot (its LAllocation).
//
// A LiveBundle, if it is to be spilled, has a pointer to the relevant
// SpillSet, and the SpillSet in turn has a pointer back to the LiveBundle in
// its vector thereof. So LiveBundles (that are to be spilled) and SpillSets
// point at each other.
//
// (SPEC) LiveBundles that are not to be spilled (or for which the decision has
// yet to be made, have their SpillSet pointers as null. (/SPEC)
//
// Requirement
// -----------
// Requirements are used transiently during the main allocation loop. It
// summarises the set of constraints on storage location (must be any register,
// must be this specific register, must be stack, etc) for a LiveBundle. This
// is so that the main allocation loop knows what kind of storage location it
// must choose in order to satisfy all of the defs and uses within the bundle.
//
// What Requirement provides is (a) a partially ordered set of locations, and
// (b) a constraint-merging method `merge`.
//
// Requirement needs a rewrite (and, in fact, that has already happened in
// un-landed code in bug 1758274) for the following reasons:
//
// * it's potentially buggy (bug 1761654), although that doesn't currently
// affect us, for reasons which are unclear.
//
// * the partially ordered set has a top point, meaning "no constraint", but it
// doesn't have a corresponding bottom point, meaning "impossible
// constraints". (So it's a partially ordered set, but not a lattice). This
// leads to awkward coding in some places, which would be simplified if there
// were an explicit way to indicate "impossible constraint".
//
//
// Some ASCII art
// ~~~~~~~~~~~~~~
//
// Here's some not-very-good ASCII art that tries to summarise the data
// structures that persist for the entire allocation of a function:
//
// BacktrackingAllocator
// |
// (vregs)
// |
// v
// |
// VirtualRegister -->--(ins)--> LNode
// | | `->--(def)--> LDefinition
// v ^
// | |
// (ranges vector) |
// | |
// | (vreg)
// `--v->--. |
// \ |
// LiveRange -->--b-->-- LiveRange -->--b-->-- NULL
// / |
// ,--b->--' /
// | (bundle)
// ^ /
// | v
// (ranges) /
// | /
// LiveBundle --s-->- LiveBundle
// | \ / |
// | \ / |
// (spill) ^ ^ (spill)
// | \ / |
// v \ / ^
// | (list) |
// \ | /
// `--->---> SpillSet <--'
//
// --b-- LiveRange::next_: links in the list of LiveRanges that belong to
// a LiveBundle
//
// --v-- VirtualRegister::ranges_: vector of LiveRanges that belong to a
// VirtualRegister
//
// --s-- LiveBundle::spillParent: a possible link to my "spill parent bundle"
//
//
// * LiveRange is in the center. Each LiveRange is a member of a linked list,
// the --b-- list, and is also stored in VirtualRegister's `ranges` vector.
//
// * VirtualRegister has a `ranges` vector that contains its LiveRanges.
//
// * LiveBundle has a pointer `ranges` that points to the start of its --b--
// list of LiveRanges.
//
// * LiveRange points back at both its owning VirtualRegister (`vreg`) and its
// owning LiveBundle (`bundle`).
//
// * LiveBundle has a pointer --s-- `spillParent`, which may be null, to its
// conceptual "spill parent bundle", as discussed in detail above.
//
// * LiveBundle has a pointer `spill` to its SpillSet.
//
// * SpillSet has a vector `list` of pointers back to the LiveBundles that
// point at it.
//
// * VirtualRegister has pointers `ins` to the LNode that defines the value and
// `def` to the LDefinition within that LNode.
//
// * BacktrackingAllocator has a vector `vregs` of pointers to all the
// VirtualRegisters for the function. There is no equivalent top-level table
// of all the LiveBundles for the function.
//
// Note that none of these pointers are "owning" in the C++-storage-management
// sense. Rather, everything is stored in single arena which is freed when
// compilation of the function is complete. For this reason,
// BacktrackingAllocator.{h,cpp} is almost completely free of the usual C++
// storage-management artefacts one would normally expect to see.
//
//
// ========================================================================
// ==== ====
// ==== Section 2: The core allocation loop, and bundle splitting ====
// ==== ====
// ========================================================================
//
// Phase 1 of the allocator (described at the start of this SMDOC) computes
// live ranges, merges them into bundles, and places the bundles in a priority
// queue ::allocationQueue, ordered by what ::computePriority computes.
//
//
// The allocation loops
// ~~~~~~~~~~~~~~~~~~~~
// The core of the allocation machinery consists of two loops followed by a
// call to ::pickStackSlots. The latter is uninteresting. The two loops live
// in ::go and are documented in detail there.
//
//
// Bundle splitting
// ~~~~~~~~~~~~~~~~
// If the first of the two abovementioned loops cannot find a register for a
// bundle, either directly or as a result of evicting conflicting bundles, then
// it will have to either split or spill the bundle. The entry point to the
// split/spill subsystem is ::chooseBundleSplit. See comments there.
///////////////////////////////////////////////////////////////////////////////
// //
// End of documentation //
// //
///////////////////////////////////////////////////////////////////////////////
#include "jit/BacktrackingAllocator.h"
#include "mozilla/BinarySearch.h"
#include "mozilla/Maybe.h"
#include <algorithm>
#include "jit/BitSet.h"
#include "jit/CompileInfo.h"
#include "js/Printf.h"
using namespace js;
using namespace js::jit;
using mozilla::DebugOnly;
using mozilla::Maybe;
// This is a big, complex file. Code is grouped into various sections, each
// preceded by a box comment. Sections not marked as "Misc helpers" are
// pretty much the top level flow, and are presented roughly in the same order
// in which the allocation pipeline operates. BacktrackingAllocator::go,
// right at the end of the file, is a good starting point.
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: linked-list management //
// //
///////////////////////////////////////////////////////////////////////////////
static inline bool SortBefore(UsePosition* a, UsePosition* b) {
return a->pos <= b->pos;
}
static inline bool SortBefore(LiveRange* a, LiveRange* b) {
MOZ_ASSERT(!a->intersects(b));
return a->from() < b->from();
}
template <typename T>
static inline void InsertSortedList(InlineForwardList<T>& list, T* value) {
if (list.empty()) {
list.pushFront(value);
return;
}
if (SortBefore(list.back(), value)) {
list.pushBack(value);
return;
}
T* prev = nullptr;
for (InlineForwardListIterator<T> iter = list.begin(); iter; iter++) {
if (SortBefore(value, *iter)) {
break;
}
prev = *iter;
}
if (prev) {
list.insertAfter(prev, value);
} else {
list.pushFront(value);
}
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: methods for class SpillSet //
// //
///////////////////////////////////////////////////////////////////////////////
void SpillSet::setAllocation(LAllocation alloc) {
for (size_t i = 0; i < numSpilledBundles(); i++) {
spilledBundle(i)->setAllocation(alloc);
}
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: methods for class LiveRange //
// //
///////////////////////////////////////////////////////////////////////////////
static size_t SpillWeightFromUsePolicy(LUse::Policy policy) {
switch (policy) {
case LUse::ANY:
return 1000;
case LUse::REGISTER:
case LUse::FIXED:
return 2000;
default:
return 0;
}
}
inline void LiveRange::noteAddedUse(UsePosition* use) {
LUse::Policy policy = use->usePolicy();
usesSpillWeight_ += SpillWeightFromUsePolicy(policy);
if (policy == LUse::FIXED) {
++numFixedUses_;
}
}
inline void LiveRange::noteRemovedUse(UsePosition* use) {
LUse::Policy policy = use->usePolicy();
usesSpillWeight_ -= SpillWeightFromUsePolicy(policy);
if (policy == LUse::FIXED) {
--numFixedUses_;
}
MOZ_ASSERT_IF(!hasUses(), !usesSpillWeight_ && !numFixedUses_);
}
void LiveRange::addUse(UsePosition* use) {
MOZ_ASSERT(covers(use->pos));
InsertSortedList(uses_, use);
noteAddedUse(use);
}
UsePosition* LiveRange::popUse() {
UsePosition* ret = uses_.popFront();
noteRemovedUse(ret);
return ret;
}
void LiveRange::tryToMoveDefAndUsesInto(LiveRange* other) {
MOZ_ASSERT(&other->vreg() == &vreg());
MOZ_ASSERT(this != other);
// Move over all uses which fit in |other|'s boundaries.
for (UsePositionIterator iter = usesBegin(); iter;) {
UsePosition* use = *iter;
if (other->covers(use->pos)) {
uses_.removeAndIncrement(iter);
noteRemovedUse(use);
other->addUse(use);
} else {
iter++;
}
}
// Distribute the definition to |other| as well, if possible.
if (hasDefinition() && from() == other->from()) {
other->setHasDefinition();
}
}
bool LiveRange::contains(LiveRange* other) const {
return from() <= other->from() && to() >= other->to();
}
void LiveRange::intersect(LiveRange* other, Range* pre, Range* inside,
Range* post) const {
MOZ_ASSERT(pre->empty() && inside->empty() && post->empty());
CodePosition innerFrom = from();
if (from() < other->from()) {
if (to() < other->from()) {
*pre = range_;
return;
}
*pre = Range(from(), other->from());
innerFrom = other->from();
}
CodePosition innerTo = to();
if (to() > other->to()) {
if (from() >= other->to()) {
*post = range_;
return;
}
*post = Range(other->to(), to());
innerTo = other->to();
}
if (innerFrom != innerTo) {
*inside = Range(innerFrom, innerTo);
}
}
bool LiveRange::intersects(LiveRange* other) const {
Range pre, inside, post;
intersect(other, &pre, &inside, &post);
return !inside.empty();
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: methods for class LiveBundle //
// //
///////////////////////////////////////////////////////////////////////////////
#ifdef DEBUG
size_t LiveBundle::numRanges() const {
size_t count = 0;
for (RangeIterator iter = rangesBegin(); iter; iter++) {
count++;
}
return count;
}
#endif
LiveRange* LiveBundle::rangeFor(CodePosition pos) const {
for (RangeIterator iter = rangesBegin(); iter; iter++) {
LiveRange* range = *iter;
if (range->covers(pos)) {
return range;
}
}
return nullptr;
}
void LiveBundle::addRange(LiveRange* range) {
MOZ_ASSERT(!range->bundle());
MOZ_ASSERT(range->hasVreg());
range->setBundle(this);
InsertSortedList(ranges_, range);
}
bool LiveBundle::addRange(TempAllocator& alloc, VirtualRegister* vreg,
CodePosition from, CodePosition to) {
LiveRange* range = LiveRange::FallibleNew(alloc, vreg, from, to);
if (!range) {
return false;
}
addRange(range);
return true;
}
bool LiveBundle::addRangeAndDistributeUses(TempAllocator& alloc,
LiveRange* oldRange,
CodePosition from, CodePosition to) {
LiveRange* range = LiveRange::FallibleNew(alloc, &oldRange->vreg(), from, to);
if (!range) {
return false;
}
addRange(range);
oldRange->tryToMoveDefAndUsesInto(range);
return true;
}
LiveRange* LiveBundle::popFirstRange() {
RangeIterator iter = rangesBegin();
if (!iter) {
return nullptr;
}
LiveRange* range = *iter;
ranges_.removeAt(iter);
range->setBundle(nullptr);
return range;
}
void LiveBundle::removeRange(LiveRange* range) {
for (RangeIterator iter = rangesBegin(); iter; iter++) {
LiveRange* existing = *iter;
if (existing == range) {
ranges_.removeAt(iter);
return;
}
}
MOZ_CRASH();
}
void LiveBundle::removeAllRangesFromVirtualRegisters() {
VirtualRegister* prevVreg = nullptr;
for (RangeIterator iter = rangesBegin(); iter; iter++) {
LiveRange* range = *iter;
MOZ_ASSERT(!range->hasUses());
if (&range->vreg() != prevVreg) {
// As an optimization, remove all ranges owned by this bundle from the
// register's list, instead of a single range at a time.
range->vreg().removeRangesForBundle(this);
prevVreg = &range->vreg();
}
}
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: methods for class VirtualRegister //
// //
///////////////////////////////////////////////////////////////////////////////
bool VirtualRegister::addInitialRange(TempAllocator& alloc, CodePosition from,
CodePosition to) {
MOZ_ASSERT(rangesSorted_, "ranges stay sorted during live range building");
MOZ_ASSERT(from < to);
MOZ_ASSERT_IF(hasRanges(), from < ranges_.back()->to());
// Mark [from,to) as a live range for this register during the initial
// liveness analysis, coalescing with any existing overlapping ranges.
LiveRange* merged = nullptr;
for (RangeIterator iter(*this); iter; iter++) {
LiveRange* existing = *iter;
MOZ_ASSERT(from < existing->to());
if (to < existing->from()) {
// All other ranges start after |to| so can't overlap.
break;
}
if (!merged) {
// This is the first old range we've found that overlaps the new
// range. Extend this one to cover its union with the new range.
merged = existing;
if (from < existing->from()) {
existing->setFrom(from);
}
if (to > existing->to()) {
existing->setTo(to);
}
// Continue searching to see if any other old ranges can be
// coalesced with the new merged range.
} else {
// Coalesce this range into the previous range we merged into.
MOZ_ASSERT(existing->from() >= merged->from());
if (existing->to() > merged->to()) {
merged->setTo(existing->to());
}
MOZ_ASSERT(!existing->hasDefinition());
existing->tryToMoveDefAndUsesInto(merged);
MOZ_ASSERT(!existing->hasUses());
}
removeFirstRange(iter);
}
if (merged) {
// Re-append the merged range.
if (!ranges_.append(merged)) {
return false;
}
} else {
// The new range does not overlap any existing range for the vreg.
MOZ_ASSERT_IF(hasRanges(), to < ranges_.back()->from());
LiveRange* range = LiveRange::FallibleNew(alloc, this, from, to);
if (!range) {
return false;
}
if (!ranges_.append(range)) {
return false;
}
}
MOZ_ASSERT(rangesSorted_, "ranges are still sorted");
#ifdef DEBUG
// Check the last few ranges don't overlap and are in the correct order.
size_t len = ranges_.length();
static constexpr size_t MaxIterations = 4;
size_t start = len > MaxIterations ? (len - MaxIterations) : 1;
for (size_t i = start; i < len; i++) {
LiveRange* range = ranges_[i];
LiveRange* prev = ranges_[i - 1];
MOZ_ASSERT(range->from() < range->to());
MOZ_ASSERT(range->to() < prev->from());
}
#endif
return true;
}
void VirtualRegister::addInitialUse(UsePosition* use) {
MOZ_ASSERT(rangesSorted_, "ranges stay sorted during live range building");
ranges_.back()->addUse(use);
}
void VirtualRegister::setInitialDefinition(CodePosition from) {
MOZ_ASSERT(rangesSorted_, "ranges stay sorted during live range building");
LiveRange* first = ranges_.back();
MOZ_ASSERT(from >= first->from());
first->setFrom(from);
first->setHasDefinition();
}
LiveRange* VirtualRegister::rangeFor(CodePosition pos,
bool preferRegister /* = false */) const {
assertRangesSorted();
size_t len = ranges_.length();
// Because the ranges are sorted in order of descending start position, we use
// binary search to find the first range where |range->from <= pos|. All
// ranges before that definitely don't cover |pos|.
auto compare = [pos](LiveRange* other) {
if (pos < other->from()) {
return 1;
}
if (pos > other->from()) {
return -1;
}
return 0;
};
size_t index;
mozilla::BinarySearchIf(ranges_, 0, len, compare, &index);
if (index == len) {
// None of the ranges overlap.
MOZ_ASSERT(ranges_.back()->from() > pos);
return nullptr;
}
// There can be multiple ranges with |range->from == pos|. We want to start at
// the first one.
while (index > 0 && ranges_[index - 1]->from() == pos) {
index--;
}
// Verify the above code is correct:
// * The range at |index| starts before or at |pos| and needs to be searched.
// * All ranges before |index| start after |pos| and can be ignored.
MOZ_ASSERT(ranges_[index]->from() <= pos);
MOZ_ASSERT_IF(index > 0, ranges_[index - 1]->from() > pos);
LiveRange* found = nullptr;
do {
LiveRange* range = ranges_[index];
if (range->covers(pos)) {
if (!preferRegister || range->bundle()->allocation().isRegister()) {
return range;
}
if (!found) {
found = range;
}
}
index++;
} while (index < len);
return found;
}
void VirtualRegister::sortRanges() {
if (rangesSorted_) {
assertRangesSorted();
return;
}
// Sort ranges by start position in descending order.
//
// It would be correct to only compare the start position, but std::sort is
// not a stable sort and we don't want the order of ranges with the same start
// position to depend on the sort implementation. Use the end position and the
// bundle's id to ensure ranges are always sorted the same way.
auto compareRanges = [](LiveRange* a, LiveRange* b) -> bool {
if (a->from() != b->from()) {
return a->from() > b->from();
}
if (a->to() != b->to()) {
return a->to() > b->to();
}
// Overlapping live ranges must belong to different bundles.
MOZ_ASSERT_IF(a != b, a->bundle()->id() != b->bundle()->id());
return a->bundle()->id() > b->bundle()->id();
};
std::sort(ranges_.begin(), ranges_.end(), compareRanges);
rangesSorted_ = true;
}
#ifdef DEBUG
void VirtualRegister::assertRangesSorted() const {
MOZ_ASSERT(rangesSorted_);
// Assert the last N ranges in the vector are sorted correctly. We don't check
// the whole vector to not slow down debug builds too much.
size_t len = ranges_.length();
static constexpr size_t MaxIterations = 4;
size_t start = len > MaxIterations ? (len - MaxIterations) : 1;
for (size_t i = start; i < len; i++) {
LiveRange* prev = ranges_[i - 1];
LiveRange* range = ranges_[i];
MOZ_ASSERT(range->from() <= prev->from());
// If two ranges have the same |from| position, neither must be defining.
// This ensures the defining range, if any, always comes first after
// sorting.
MOZ_ASSERT_IF(range->from() == prev->from(),
!range->hasDefinition() && !prev->hasDefinition());
}
}
#endif
bool VirtualRegister::addRange(LiveRange* range) {
bool sorted = ranges_.empty() ||
(rangesSorted_ && ranges_.back()->from() >= range->from());
if (!ranges_.append(range)) {
return false;
}
rangesSorted_ = sorted;
return true;
}
void VirtualRegister::removeFirstRange(RangeIterator& iter) {
MOZ_ASSERT(iter.index() == ranges_.length() - 1);
ranges_.popBack();
}
void VirtualRegister::removeRangesForBundle(LiveBundle* bundle) {
auto bundleMatches = [bundle](LiveRange* range) {
return range->bundle() == bundle;
};
ranges_.eraseIf(bundleMatches);
}
template <typename Pred>
void VirtualRegister::removeRangesIf(Pred&& pred) {
assertRangesSorted();
ranges_.eraseIf([&](LiveRange* range) { return pred(ranges_, range); });
}
// Helper for ::tryMergeReusedRegister.
bool VirtualRegister::replaceLastRangeLinear(LiveRange* old, LiveRange* newPre,
LiveRange* newPost) {
assertRangesSorted();
// |old| is currently the first range in the Vector (the range with the
// highest start position). This range is being replaced with two new ranges,
// |newPre| and |newPost|. The relative order of these ranges by start
// position is:
//
// old <= newPre <= newPost
//
// To keep the vector sorted by descending start position, |newPost| must
// become the new last range and |newPre| must be inserted after it.
MOZ_ASSERT(ranges_[0] == old);
MOZ_ASSERT(old->from() <= newPre->from());
MOZ_ASSERT(newPre->from() <= newPost->from());
ranges_[0] = newPost;
if (!ranges_.insert(ranges_.begin() + 1, newPre)) {
return false;
}
assertRangesSorted();
return true;
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: queries about uses //
// //
///////////////////////////////////////////////////////////////////////////////
static inline LDefinition* FindReusingDefOrTemp(LNode* node,
LAllocation* alloc) {
if (node->isPhi()) {
MOZ_ASSERT(node->toPhi()->numDefs() == 1);
MOZ_ASSERT(node->toPhi()->getDef(0)->policy() !=
LDefinition::MUST_REUSE_INPUT);
return nullptr;
}
LInstruction* ins = node->toInstruction();
for (size_t i = 0; i < ins->numDefs(); i++) {
LDefinition* def = ins->getDef(i);
if (def->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(def->getReusedInput()) == alloc) {
return def;
}
}
for (size_t i = 0; i < ins->numTemps(); i++) {
LDefinition* def = ins->getTemp(i);
if (def->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(def->getReusedInput()) == alloc) {
return def;
}
}
return nullptr;
}
bool BacktrackingAllocator::isReusedInput(LUse* use, LNode* ins,
bool considerCopy) {
if (LDefinition* def = FindReusingDefOrTemp(ins, use)) {
return considerCopy || !vregs[def->virtualRegister()].mustCopyInput();
}
return false;
}
bool BacktrackingAllocator::isRegisterUse(UsePosition* use, LNode* ins,
bool considerCopy) {
switch (use->usePolicy()) {
case LUse::ANY:
return isReusedInput(use->use(), ins, considerCopy);
case LUse::REGISTER:
case LUse::FIXED:
return true;
default:
return false;
}
}
bool BacktrackingAllocator::isRegisterDefinition(LiveRange* range) {
if (!range->hasDefinition()) {
return false;
}
VirtualRegister& reg = range->vreg();
if (reg.ins()->isPhi()) {
return false;
}
if (reg.def()->policy() == LDefinition::FIXED &&
!reg.def()->output()->isRegister()) {
return false;
}
return true;
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: atomic LIR groups //
// //
///////////////////////////////////////////////////////////////////////////////
// The following groupings contain implicit (invisible to ::buildLivenessInfo)
// value flows, and therefore no split points may be requested inside them.
// This is an otherwise unstated part of the contract between LIR generation
// and the allocator.
//
// (1) (any insn) ; OsiPoint
//
// [Further group definitions and supporting code to come, pending rework
// of the wasm atomic-group situation.]
CodePosition RegisterAllocator::minimalDefEnd(LNode* ins) const {
// Compute the shortest interval that captures vregs defined by ins.
// Watch for instructions that are followed by an OSI point.
// If moves are introduced between the instruction and the OSI point then
// safepoint information for the instruction may be incorrect.
while (true) {
LNode* next = insData[ins->id() + 1];
if (!next->isOsiPoint()) {
break;
}
ins = next;
}
return outputOf(ins);
}
///////////////////////////////////////////////////////////////////////////////
// //
// Misc helpers: computation of bundle priorities and spill weights //
// //
///////////////////////////////////////////////////////////////////////////////
size_t BacktrackingAllocator::computePriority(LiveBundle* bundle) {
// The priority of a bundle is its total length, so that longer lived
// bundles will be processed before shorter ones (even if the longer ones
// have a low spill weight). See processBundle().
size_t lifetimeTotal = 0;
for (LiveBundle::RangeIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = *iter;
lifetimeTotal += range->to() - range->from();
}
return lifetimeTotal;
}
bool BacktrackingAllocator::minimalDef(LiveRange* range, LNode* ins) {
// Whether this is a minimal range capturing a definition at ins.
return (range->to() <= minimalDefEnd(ins).next()) &&
((!ins->isPhi() && range->from() == inputOf(ins)) ||
range->from() == outputOf(ins));
}
bool BacktrackingAllocator::minimalUse(LiveRange* range, UsePosition* use) {
// Whether this is a minimal range capturing |use|.
LNode* ins = insData[use->pos];
return (range->from() == inputOf(ins)) &&
(range->to() ==
(use->use()->usedAtStart() ? outputOf(ins) : outputOf(ins).next()));
}
bool BacktrackingAllocator::minimalBundle(LiveBundle* bundle, bool* pfixed) {
LiveBundle::RangeIterator iter = bundle->rangesBegin();
LiveRange* range = *iter;
MOZ_ASSERT(range->hasVreg(), "Call ranges are not added to LiveBundles");
// If a bundle contains multiple ranges, splitAtAllRegisterUses will split
// each range into a separate bundle.
if (++iter) {
return false;
}