diff options
Diffstat (limited to 'js/src/jit/BacktrackingAllocator.cpp')
| -rw-r--r-- | js/src/jit/BacktrackingAllocator.cpp | 4676 |
1 files changed, 4676 insertions, 0 deletions
diff --git a/js/src/jit/BacktrackingAllocator.cpp b/js/src/jit/BacktrackingAllocator.cpp new file mode 100644 index 0000000000..d93431795a --- /dev/null +++ b/js/src/jit/BacktrackingAllocator.cpp @@ -0,0 +1,4676 @@ +/* -*- 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. +// +// At https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17 +// (https://bugzilla.mozilla.org/attachment.cgi?id=9288467) is a document +// 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 linked lists, chained through +// fields registerLink and bundleLink. +// +// A VirtualRegister (described in detail below) has a list of LiveRanges that +// it "owns". These are chained through LiveRange::registerLink. +// +// A LiveBundle (also described below) also has a list LiveRanges that it +// "owns", chained through LiveRange::bundleLink. +// +// 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. This is a linked list beginning +// at VirtualRegister::ranges_, and which, as described above, is chained +// through LiveRange::registerLink. The set of LiveRanges must logically form +// a tree, rooted at the LiveRange which defines the value. +// +// For adminstrative convenience, the linked list must contain the LiveRanges +// in order of increasing start point. +// +// 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_ and chained through LiveRange::bundleLink. +// +// 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 debugId_ 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. +// +// When compiled with JS_JITSPEW, LiveBundle has a 32-bit `debugId_` field. +// This is used only for debug printing, and makes it easier to see +// parent-child relationships induced by the `spillParent_` pointers. +// +// 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) | +// | (vreg) +// `--v->--. | ,-->--v-->-------------->--v-->--. ,--NULL +// \ | / \ / +// LiveRange LiveRange LiveRange +// / | \ / \. +// ,--b->--' / `-->--b-->--' `--NULL +// | (bundle) +// ^ / +// | v +// (ranges) / +// | / +// LiveBundle --s-->- LiveBundle +// | \ / | +// | \ / | +// (spill) ^ ^ (spill) +// | \ / | +// v \ / ^ +// | (list) | +// \ | / +// `--->---> SpillSet <--' +// +// --b-- LiveRange::bundleLink: links in the list of LiveRanges that belong to +// a LiveBundle +// +// --v-- LiveRange::registerLink: links in the list 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 two different +// linked lists, the --b-- list and the --v-- list. +// +// * VirtualRegister has a pointer `ranges` that points to the start of its +// --v-- list of 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 <algorithm> + +#include "jit/BitSet.h" +#include "jit/CompileInfo.h" +#include "js/Printf.h" + +using namespace js; +using namespace js::jit; + +using mozilla::DebugOnly; + +// 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::BundleLink* a, + LiveRange::BundleLink* b) { + LiveRange* rangea = LiveRange::get(a); + LiveRange* rangeb = LiveRange::get(b); + MOZ_ASSERT(!rangea->intersects(rangeb)); + return rangea->from() < rangeb->from(); +} + +static inline bool SortBefore(LiveRange::RegisterLink* a, + LiveRange::RegisterLink* b) { + return LiveRange::get(a)->from() <= LiveRange::get(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 (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) { + count++; + } + return count; +} +#endif + +LiveRange* LiveBundle::rangeFor(CodePosition pos) const { + for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) { + LiveRange* range = LiveRange::get(*iter); + if (range->covers(pos)) { + return range; + } + } + return nullptr; +} + +void LiveBundle::addRange(LiveRange* range) { + MOZ_ASSERT(!range->bundle()); + range->setBundle(this); + InsertSortedList(ranges_, &range->bundleLink); +} + +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() { + LiveRange::BundleLinkIterator iter = rangesBegin(); + if (!iter) { + return nullptr; + } + + LiveRange* range = LiveRange::get(*iter); + ranges_.removeAt(iter); + + range->setBundle(nullptr); + return range; +} + +void LiveBundle::removeRange(LiveRange* range) { + for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) { + LiveRange* existing = LiveRange::get(*iter); + if (existing == range) { + ranges_.removeAt(iter); + return; + } + } + MOZ_CRASH(); +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Misc helpers: methods for class VirtualRegister // +// // +/////////////////////////////////////////////////////////////////////////////// + +bool VirtualRegister::addInitialRange(TempAllocator& alloc, CodePosition from, + CodePosition to, size_t* numRanges) { + MOZ_ASSERT(from < to); + + // Mark [from,to) as a live range for this register during the initial + // liveness analysis, coalescing with any existing overlapping ranges. + + // On some pathological graphs there might be a huge number of different + // live ranges. Allow non-overlapping live range to be merged if the + // number of ranges exceeds the cap below. + static const size_t CoalesceLimit = 100000; + + LiveRange* prev = nullptr; + LiveRange* merged = nullptr; + for (LiveRange::RegisterLinkIterator iter(rangesBegin()); iter;) { + LiveRange* existing = LiveRange::get(*iter); + + if (from > existing->to() && *numRanges < CoalesceLimit) { + // The new range should go after this one. + prev = existing; + iter++; + continue; + } + + if (to.next() < existing->from()) { + // The new range should go before this one. + 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. + iter++; + continue; + } + + // 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()); + + ranges_.removeAndIncrement(iter); + } + + if (!merged) { + // The new range does not overlap any existing range for the vreg. + LiveRange* range = LiveRange::FallibleNew(alloc, this, from, to); + if (!range) { + return false; + } + + if (prev) { + ranges_.insertAfter(&prev->registerLink, &range->registerLink); + } else { + ranges_.pushFront(&range->registerLink); + } + + (*numRanges)++; + } + + return true; +} + +void VirtualRegister::addInitialUse(UsePosition* use) { + LiveRange::get(*rangesBegin())->addUse(use); +} + +void VirtualRegister::setInitialDefinition(CodePosition from) { + LiveRange* first = LiveRange::get(*rangesBegin()); + MOZ_ASSERT(from >= first->from()); + first->setFrom(from); + first->setHasDefinition(); +} + +LiveRange* VirtualRegister::rangeFor(CodePosition pos, + bool preferRegister /* = false */) const { + LiveRange* found = nullptr; + for (LiveRange::RegisterLinkIterator iter = rangesBegin(); iter; iter++) { + LiveRange* range = LiveRange::get(*iter); + if (range->covers(pos)) { + if (!preferRegister || range->bundle()->allocation().isRegister()) { + return range; + } + if (!found) { + found = range; + } + } + } + return found; +} + +void VirtualRegister::addRange(LiveRange* range) { + InsertSortedList(ranges_, &range->registerLink); +} + +void VirtualRegister::removeRange(LiveRange* range) { + for (LiveRange::RegisterLinkIterator iter = rangesBegin(); iter; iter++) { + LiveRange* existing = LiveRange::get(*iter); + if (existing == range) { + ranges_.removeAt(iter); + return; + } + } + MOZ_CRASH(); +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// 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 (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*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) { + LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); + LiveRange* range = LiveRange::get(*iter); + + if (!range->hasVreg()) { + *pfixed = true; + return true; + } + + // If a bundle contains multiple ranges, splitAtAllRegisterUses will split + // each range into a separate bundle. + if (++iter) { + return false; + } + + if (range->hasDefinition()) { + VirtualRegister& reg = range->vreg(); + if (pfixed) { + *pfixed = reg.def()->policy() == LDefinition::FIXED && + reg.def()->output()->isRegister(); + } + return minimalDef(range, reg.ins()); + } + + bool fixed = false, minimal = false, multiple = false; + + for (UsePositionIterator iter = range->usesBegin(); iter; iter++) { + if (iter != range->usesBegin()) { + multiple = true; + } + + switch (iter->usePolicy()) { + case LUse::FIXED: + if (fixed) { + return false; + } + fixed = true; + if (minimalUse(range, *iter)) { + minimal = true; + } + break; + + case LUse::REGISTER: + if (minimalUse(range, *iter)) { + minimal = true; + } + break; + + default: + break; + } + } + + // If a range contains a fixed use and at least one other use, + // splitAtAllRegisterUses will split each use into a different bundle. + if (multiple && fixed) { + minimal = false; + } + + if (pfixed) { + *pfixed = fixed; + } + return minimal; +} + +size_t BacktrackingAllocator::computeSpillWeight(LiveBundle* bundle) { + // Minimal bundles have an extremely high spill weight, to ensure they + // can evict any other bundles and be allocated to a register. + bool fixed; + if (minimalBundle(bundle, &fixed)) { + return fixed ? 2000000 : 1000000; + } + + size_t usesTotal = 0; + fixed = false; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + if (range->hasDefinition()) { + VirtualRegister& reg = range->vreg(); + if (reg.def()->policy() == LDefinition::FIXED && + reg.def()->output()->isRegister()) { + usesTotal += 2000; + fixed = true; + } else if (!reg.ins()->isPhi()) { + usesTotal += 2000; + } + } + + usesTotal += range->usesSpillWeight(); + if (range->numFixedUses() > 0) { + fixed = true; + } + } + + // Bundles with fixed uses are given a higher spill weight, since they must + // be allocated to a specific register. + if (testbed && fixed) { + usesTotal *= 2; + } + + // Compute spill weight as a use density, lowering the weight for long + // lived bundles with relatively few uses. + size_t lifetimeTotal = computePriority(bundle); + return lifetimeTotal ? usesTotal / lifetimeTotal : 0; +} + +size_t BacktrackingAllocator::maximumSpillWeight( + const LiveBundleVector& bundles) { + size_t maxWeight = 0; + for (size_t i = 0; i < bundles.length(); i++) { + maxWeight = std::max(maxWeight, computeSpillWeight(bundles[i])); + } + return maxWeight; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Initialization of the allocator // +// // +/////////////////////////////////////////////////////////////////////////////// + +// This function pre-allocates and initializes as much global state as possible +// to avoid littering the algorithms with memory management cruft. +bool BacktrackingAllocator::init() { + if (!RegisterAllocator::init()) { + return false; + } + + liveIn = mir->allocate<BitSet>(graph.numBlockIds()); + if (!liveIn) { + return false; + } + + size_t numVregs = graph.numVirtualRegisters(); + if (!vregs.init(mir->alloc(), numVregs)) { + return false; + } + for (uint32_t i = 0; i < numVregs; i++) { + new (&vregs[i]) VirtualRegister(); + } + + // Build virtual register objects. + for (size_t i = 0; i < graph.numBlocks(); i++) { + if (mir->shouldCancel("Create data structures (main loop)")) { + return false; + } + + LBlock* block = graph.getBlock(i); + for (LInstructionIterator ins = block->begin(); ins != block->end(); + ins++) { + if (mir->shouldCancel("Create data structures (inner loop 1)")) { + return false; + } + + for (size_t j = 0; j < ins->numDefs(); j++) { + LDefinition* def = ins->getDef(j); + if (def->isBogusTemp()) { + continue; + } + vreg(def).init(*ins, def, /* isTemp = */ false); + } + + for (size_t j = 0; j < ins->numTemps(); j++) { + LDefinition* def = ins->getTemp(j); + if (def->isBogusTemp()) { + continue; + } + vreg(def).init(*ins, def, /* isTemp = */ true); + } + } + for (size_t j = 0; j < block->numPhis(); j++) { + LPhi* phi = block->getPhi(j); + LDefinition* def = phi->getDef(0); + vreg(def).init(phi, def, /* isTemp = */ false); + } + } + + LiveRegisterSet remainingRegisters(allRegisters_.asLiveSet()); + while (!remainingRegisters.emptyGeneral()) { + AnyRegister reg = AnyRegister(remainingRegisters.takeAnyGeneral()); + registers[reg.code()].allocatable = true; + } + while (!remainingRegisters.emptyFloat()) { + AnyRegister reg = + AnyRegister(remainingRegisters.takeAnyFloat<RegTypeName::Any>()); + registers[reg.code()].allocatable = true; + } + + LifoAlloc* lifoAlloc = mir->alloc().lifoAlloc(); + for (size_t i = 0; i < AnyRegister::Total; i++) { + registers[i].reg = AnyRegister::FromCode(i); + registers[i].allocations.setAllocator(lifoAlloc); + } + + hotcode.setAllocator(lifoAlloc); + callRanges.setAllocator(lifoAlloc); + + // Partition the graph into hot and cold sections, for helping to make + // splitting decisions. Since we don't have any profiling data this is a + // crapshoot, so just mark the bodies of inner loops as hot and everything + // else as cold. + + LBlock* backedge = nullptr; + for (size_t i = 0; i < graph.numBlocks(); i++) { + LBlock* block = graph.getBlock(i); + + // If we see a loop header, mark the backedge so we know when we have + // hit the end of the loop. Don't process the loop immediately, so that + // if there is an inner loop we will ignore the outer backedge. + if (block->mir()->isLoopHeader()) { + backedge = block->mir()->backedge()->lir(); + } + + if (block == backedge) { + LBlock* header = block->mir()->loopHeaderOfBackedge()->lir(); + LiveRange* range = LiveRange::FallibleNew( + alloc(), nullptr, entryOf(header), exitOf(block).next()); + if (!range || !hotcode.insert(range)) { + return false; + } + } + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Liveness analysis // +// // +/////////////////////////////////////////////////////////////////////////////// + +// Helper for ::buildLivenessInfo +bool BacktrackingAllocator::addInitialFixedRange(AnyRegister reg, + CodePosition from, + CodePosition to) { + LiveRange* range = LiveRange::FallibleNew(alloc(), nullptr, from, to); + if (!range) { + return false; + } + LiveRangePlus rangePlus(range); + return registers[reg.code()].allocations.insert(rangePlus); +} + +// Helper for ::buildLivenessInfo +#ifdef DEBUG +// Returns true iff ins has a def/temp reusing the input allocation. +static bool IsInputReused(LInstruction* ins, LUse* use) { + for (size_t i = 0; i < ins->numDefs(); i++) { + if (ins->getDef(i)->policy() == LDefinition::MUST_REUSE_INPUT && + ins->getOperand(ins->getDef(i)->getReusedInput())->toUse() == use) { + return true; + } + } + + for (size_t i = 0; i < ins->numTemps(); i++) { + if (ins->getTemp(i)->policy() == LDefinition::MUST_REUSE_INPUT && + ins->getOperand(ins->getTemp(i)->getReusedInput())->toUse() == use) { + return true; + } + } + + return false; +} +#endif + +/* + * This function builds up liveness ranges for all virtual registers + * defined in the function. + * + * The algorithm is based on the one published in: + * + * Wimmer, Christian, and Michael Franz. "Linear Scan Register Allocation on + * SSA Form." Proceedings of the International Symposium on Code Generation + * and Optimization. Toronto, Ontario, Canada, ACM. 2010. 170-79. PDF. + * + * The algorithm operates on blocks ordered such that dominators of a block + * are before the block itself, and such that all blocks of a loop are + * contiguous. It proceeds backwards over the instructions in this order, + * marking registers live at their uses, ending their live ranges at + * definitions, and recording which registers are live at the top of every + * block. To deal with loop backedges, registers live at the beginning of + * a loop gain a range covering the entire loop. + */ +bool BacktrackingAllocator::buildLivenessInfo() { + JitSpew(JitSpew_RegAlloc, "Beginning liveness analysis"); + + Vector<MBasicBlock*, 1, SystemAllocPolicy> loopWorkList; + BitSet loopDone(graph.numBlockIds()); + if (!loopDone.init(alloc())) { + return false; + } + + size_t numRanges = 0; + + for (size_t i = graph.numBlocks(); i > 0; i--) { + if (mir->shouldCancel("Build Liveness Info (main loop)")) { + return false; + } + + LBlock* block = graph.getBlock(i - 1); + MBasicBlock* mblock = block->mir(); + + BitSet& live = liveIn[mblock->id()]; + new (&live) BitSet(graph.numVirtualRegisters()); + if (!live.init(alloc())) { + return false; + } + + // Propagate liveIn from our successors to us. + for (size_t i = 0; i < mblock->lastIns()->numSuccessors(); i++) { + MBasicBlock* successor = mblock->lastIns()->getSuccessor(i); + // Skip backedges, as we fix them up at the loop header. + if (mblock->id() < successor->id()) { + live.insertAll(liveIn[successor->id()]); + } + } + + // Add successor phis. + if (mblock->successorWithPhis()) { + LBlock* phiSuccessor = mblock->successorWithPhis()->lir(); + for (unsigned int j = 0; j < phiSuccessor->numPhis(); j++) { + LPhi* phi = phiSuccessor->getPhi(j); + LAllocation* use = phi->getOperand(mblock->positionInPhiSuccessor()); + uint32_t reg = use->toUse()->virtualRegister(); + live.insert(reg); + vreg(use).setUsedByPhi(); + } + } + + // Registers are assumed alive for the entire block, a define shortens + // the range to the point of definition. + for (BitSet::Iterator liveRegId(live); liveRegId; ++liveRegId) { + if (!vregs[*liveRegId].addInitialRange(alloc(), entryOf(block), + exitOf(block).next(), &numRanges)) + return false; + } + + // Shorten the front end of ranges for live variables to their point of + // definition, if found. + for (LInstructionReverseIterator ins = block->rbegin(); + ins != block->rend(); ins++) { + // Calls may clobber registers, so force a spill and reload around the + // callsite. + if (ins->isCall()) { + for (AnyRegisterIterator iter(allRegisters_.asLiveSet()); iter.more(); + ++iter) { + bool found = false; + for (size_t i = 0; i < ins->numDefs(); i++) { + if (ins->getDef(i)->isFixed() && + ins->getDef(i)->output()->aliases(LAllocation(*iter))) { + found = true; + break; + } + } + // If this register doesn't have an explicit def above, mark + // it as clobbered by the call unless it is actually + // call-preserved. + if (!found && !ins->isCallPreserved(*iter)) { + if (!addInitialFixedRange(*iter, outputOf(*ins), + outputOf(*ins).next())) { + return false; + } + } + } + + CallRange* callRange = new (alloc().fallible()) + CallRange(outputOf(*ins), outputOf(*ins).next()); + if (!callRange) { + return false; + } + + callRangesList.pushFront(callRange); + if (!callRanges.insert(callRange)) { + return false; + } + } + + for (size_t i = 0; i < ins->numDefs(); i++) { + LDefinition* def = ins->getDef(i); + if (def->isBogusTemp()) { + continue; + } + + CodePosition from = outputOf(*ins); + + if (def->policy() == LDefinition::MUST_REUSE_INPUT) { + // MUST_REUSE_INPUT is implemented by allocating an output + // register and moving the input to it. Register hints are + // used to avoid unnecessary moves. We give the input an + // LUse::ANY policy to avoid allocating a register for the + // input. + LUse* inputUse = ins->getOperand(def->getReusedInput())->toUse(); + MOZ_ASSERT(inputUse->policy() == LUse::REGISTER); + MOZ_ASSERT(inputUse->usedAtStart()); + *inputUse = LUse(inputUse->virtualRegister(), LUse::ANY, + /* usedAtStart = */ true); + } + + if (!vreg(def).addInitialRange(alloc(), from, from.next(), + &numRanges)) { + return false; + } + vreg(def).setInitialDefinition(from); + live.remove(def->virtualRegister()); + } + + for (size_t i = 0; i < ins->numTemps(); i++) { + LDefinition* temp = ins->getTemp(i); + if (temp->isBogusTemp()) { + continue; + } + + // Normally temps are considered to cover both the input + // and output of the associated instruction. In some cases + // though we want to use a fixed register as both an input + // and clobbered register in the instruction, so watch for + // this and shorten the temp to cover only the output. + CodePosition from = inputOf(*ins); + if (temp->policy() == LDefinition::FIXED) { + AnyRegister reg = temp->output()->toRegister(); + for (LInstruction::InputIterator alloc(**ins); alloc.more(); + alloc.next()) { + if (alloc->isUse()) { + LUse* use = alloc->toUse(); + if (use->isFixedRegister()) { + if (GetFixedRegister(vreg(use).def(), use) == reg) { + from = outputOf(*ins); + } + } + } + } + } + + // * For non-call instructions, temps cover both the input and output, + // so temps never alias uses (even at-start uses) or defs. + // * For call instructions, temps only cover the input (the output is + // used for the force-spill ranges added above). This means temps + // still don't alias uses but they can alias the (fixed) defs. For now + // we conservatively require temps to have a fixed register for call + // instructions to prevent a footgun. + MOZ_ASSERT_IF(ins->isCall(), temp->policy() == LDefinition::FIXED); + CodePosition to = + ins->isCall() ? outputOf(*ins) : outputOf(*ins).next(); + + if (!vreg(temp).addInitialRange(alloc(), from, to, &numRanges)) { + return false; + } + vreg(temp).setInitialDefinition(from); + } + + DebugOnly<bool> hasUseRegister = false; + DebugOnly<bool> hasUseRegisterAtStart = false; + + for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); + inputAlloc.next()) { + if (inputAlloc->isUse()) { + LUse* use = inputAlloc->toUse(); + + // Call uses should always be at-start, since calls use all + // registers. + MOZ_ASSERT_IF(ins->isCall() && !inputAlloc.isSnapshotInput(), + use->usedAtStart()); + +#ifdef DEBUG + // If there are both useRegisterAtStart(x) and useRegister(y) + // uses, we may assign the same register to both operands + // (bug 772830). Don't allow this for now. + if (use->policy() == LUse::REGISTER) { + if (use->usedAtStart()) { + if (!IsInputReused(*ins, use)) { + hasUseRegisterAtStart = true; + } + } else { + hasUseRegister = true; + } + } + MOZ_ASSERT(!(hasUseRegister && hasUseRegisterAtStart)); +#endif + + // Don't treat RECOVERED_INPUT uses as keeping the vreg alive. + if (use->policy() == LUse::RECOVERED_INPUT) { + continue; + } + + CodePosition to = use->usedAtStart() ? inputOf(*ins) : outputOf(*ins); + if (use->isFixedRegister()) { + LAllocation reg(AnyRegister::FromCode(use->registerCode())); + for (size_t i = 0; i < ins->numDefs(); i++) { + LDefinition* def = ins->getDef(i); + if (def->policy() == LDefinition::FIXED && + *def->output() == reg) { + to = inputOf(*ins); + } + } + } + + if (!vreg(use).addInitialRange(alloc(), entryOf(block), to.next(), + &numRanges)) { + return false; + } + UsePosition* usePosition = + new (alloc().fallible()) UsePosition(use, to); + if (!usePosition) { + return false; + } + vreg(use).addInitialUse(usePosition); + live.insert(use->virtualRegister()); + } + } + } + + // Phis have simultaneous assignment semantics at block begin, so at + // the beginning of the block we can be sure that liveIn does not + // contain any phi outputs. + for (unsigned int i = 0; i < block->numPhis(); i++) { + LDefinition* def = block->getPhi(i)->getDef(0); + if (live.contains(def->virtualRegister())) { + live.remove(def->virtualRegister()); + } else { + // This is a dead phi, so add a dummy range over all phis. This + // can go away if we have an earlier dead code elimination pass. + CodePosition entryPos = entryOf(block); + if (!vreg(def).addInitialRange(alloc(), entryPos, entryPos.next(), + &numRanges)) { + return false; + } + } + } + + if (mblock->isLoopHeader()) { + // A divergence from the published algorithm is required here, as + // our block order does not guarantee that blocks of a loop are + // contiguous. As a result, a single live range spanning the + // loop is not possible. Additionally, we require liveIn in a later + // pass for resolution, so that must also be fixed up here. + MBasicBlock* loopBlock = mblock->backedge(); + while (true) { + // Blocks must already have been visited to have a liveIn set. + MOZ_ASSERT(loopBlock->id() >= mblock->id()); + + // Add a range for this entire loop block + CodePosition from = entryOf(loopBlock->lir()); + CodePosition to = exitOf(loopBlock->lir()).next(); + + for (BitSet::Iterator liveRegId(live); liveRegId; ++liveRegId) { + if (!vregs[*liveRegId].addInitialRange(alloc(), from, to, + &numRanges)) { + return false; + } + } + + // Fix up the liveIn set. + liveIn[loopBlock->id()].insertAll(live); + + // Make sure we don't visit this node again + loopDone.insert(loopBlock->id()); + + // If this is the loop header, any predecessors are either the + // backedge or out of the loop, so skip any predecessors of + // this block + if (loopBlock != mblock) { + for (size_t i = 0; i < loopBlock->numPredecessors(); i++) { + MBasicBlock* pred = loopBlock->getPredecessor(i); + if (loopDone.contains(pred->id())) { + continue; + } + if (!loopWorkList.append(pred)) { + return false; + } + } + } + + // Terminate loop if out of work. + if (loopWorkList.empty()) { + break; + } + + // Grab the next block off the work list, skipping any OSR block. + MBasicBlock* osrBlock = graph.mir().osrBlock(); + while (!loopWorkList.empty()) { + loopBlock = loopWorkList.popCopy(); + if (loopBlock != osrBlock) { + break; + } + } + + // If end is reached without finding a non-OSR block, then no more work + // items were found. + if (loopBlock == osrBlock) { + MOZ_ASSERT(loopWorkList.empty()); + break; + } + } + + // Clear the done set for other loops + loopDone.clear(); + } + + MOZ_ASSERT_IF(!mblock->numPredecessors(), live.empty()); + } + + JitSpew(JitSpew_RegAlloc, "Completed liveness analysis"); + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Merging and queueing of LiveRange groups // +// // +/////////////////////////////////////////////////////////////////////////////// + +// Helper for ::tryMergeBundles +static bool IsArgumentSlotDefinition(LDefinition* def) { + return def->policy() == LDefinition::FIXED && def->output()->isArgument(); +} + +// Helper for ::tryMergeBundles +static bool IsThisSlotDefinition(LDefinition* def) { + return IsArgumentSlotDefinition(def) && + def->output()->toArgument()->index() < + THIS_FRAME_ARGSLOT + sizeof(Value); +} + +// Helper for ::tryMergeBundles +static bool HasStackPolicy(LDefinition* def) { + return def->policy() == LDefinition::STACK; +} + +// Helper for ::tryMergeBundles +static bool CanMergeTypesInBundle(LDefinition::Type a, LDefinition::Type b) { + // Fast path for the common case. + if (a == b) { + return true; + } + + // Only merge if the sizes match, so that we don't get confused about the + // width of spill slots. + return StackSlotAllocator::width(a) == StackSlotAllocator::width(b); +} + +// Helper for ::tryMergeReusedRegister +bool BacktrackingAllocator::tryMergeBundles(LiveBundle* bundle0, + LiveBundle* bundle1) { + // See if bundle0 and bundle1 can be merged together. + if (bundle0 == bundle1) { + return true; + } + + // Get a representative virtual register from each bundle. + VirtualRegister& reg0 = bundle0->firstRange()->vreg(); + VirtualRegister& reg1 = bundle1->firstRange()->vreg(); + + MOZ_ASSERT(CanMergeTypesInBundle(reg0.type(), reg1.type())); + MOZ_ASSERT(reg0.isCompatible(reg1)); + + // Registers which might spill to the frame's |this| slot can only be + // grouped with other such registers. The frame's |this| slot must always + // hold the |this| value, as required by JitFrame tracing and by the Ion + // constructor calling convention. + if (IsThisSlotDefinition(reg0.def()) || IsThisSlotDefinition(reg1.def())) { + if (*reg0.def()->output() != *reg1.def()->output()) { + return true; + } + } + + // Registers which might spill to the frame's argument slots can only be + // grouped with other such registers if the frame might access those + // arguments through a lazy arguments object or rest parameter. + if (IsArgumentSlotDefinition(reg0.def()) || + IsArgumentSlotDefinition(reg1.def())) { + if (graph.mir().entryBlock()->info().mayReadFrameArgsDirectly()) { + if (*reg0.def()->output() != *reg1.def()->output()) { + return true; + } + } + } + + // When we make a call to a WebAssembly function that returns multiple + // results, some of those results can go on the stack. The callee is passed a + // pointer to this stack area, which is represented as having policy + // LDefinition::STACK (with type LDefinition::STACKRESULTS). Individual + // results alias parts of the stack area with a value-appropriate type, but + // policy LDefinition::STACK. This aliasing between allocations makes it + // unsound to merge anything with a LDefinition::STACK policy. + if (HasStackPolicy(reg0.def()) || HasStackPolicy(reg1.def())) { + return true; + } + + // Limit the number of times we compare ranges if there are many ranges in + // one of the bundles, to avoid quadratic behavior. + static const size_t MAX_RANGES = 200; + + // Make sure that ranges in the bundles do not overlap. + LiveRange::BundleLinkIterator iter0 = bundle0->rangesBegin(), + iter1 = bundle1->rangesBegin(); + size_t count = 0; + while (iter0 && iter1) { + if (++count >= MAX_RANGES) { + return true; + } + + LiveRange* range0 = LiveRange::get(*iter0); + LiveRange* range1 = LiveRange::get(*iter1); + + if (range0->from() >= range1->to()) { + iter1++; + } else if (range1->from() >= range0->to()) { + iter0++; + } else { + return true; + } + } + + // Move all ranges from bundle1 into bundle0. + while (LiveRange* range = bundle1->popFirstRange()) { + bundle0->addRange(range); + } + + return true; +} + +// Helper for ::mergeAndQueueRegisters +void BacktrackingAllocator::allocateStackDefinition(VirtualRegister& reg) { + LInstruction* ins = reg.ins()->toInstruction(); + if (reg.def()->type() == LDefinition::STACKRESULTS) { + LStackArea alloc(ins->toInstruction()); + stackSlotAllocator.allocateStackArea(&alloc); + reg.def()->setOutput(alloc); + } else { + // Because the definitions are visited in order, the area has been allocated + // before we reach this result, so we know the operand is an LStackArea. + const LUse* use = ins->getOperand(0)->toUse(); + VirtualRegister& area = vregs[use->virtualRegister()]; + const LStackArea* areaAlloc = area.def()->output()->toStackArea(); + reg.def()->setOutput(areaAlloc->resultAlloc(ins, reg.def())); + } +} + +// Helper for ::mergeAndQueueRegisters +bool BacktrackingAllocator::tryMergeReusedRegister(VirtualRegister& def, + VirtualRegister& input) { + // def is a vreg which reuses input for its output physical register. Try + // to merge ranges for def with those of input if possible, as avoiding + // copies before def's instruction is crucial for generated code quality + // (MUST_REUSE_INPUT is used for all arithmetic on x86/x64). + + if (def.rangeFor(inputOf(def.ins()))) { + MOZ_ASSERT(def.isTemp()); + def.setMustCopyInput(); + return true; + } + + if (!CanMergeTypesInBundle(def.type(), input.type())) { + def.setMustCopyInput(); + return true; + } + + LiveRange* inputRange = input.rangeFor(outputOf(def.ins())); + if (!inputRange) { + // The input is not live after the instruction, either in a safepoint + // for the instruction or in subsequent code. The input and output + // can thus be in the same group. + return tryMergeBundles(def.firstBundle(), input.firstBundle()); + } + + // Avoid merging in very large live ranges as merging has non-linear + // complexity. The cutoff value is hard to gauge. 1M was chosen because it + // is "large" and yet usefully caps compile time on AutoCad-for-the-web to + // something reasonable on a 2017-era desktop system. + const uint32_t RANGE_SIZE_CUTOFF = 1000000; + if (inputRange->to() - inputRange->from() > RANGE_SIZE_CUTOFF) { + def.setMustCopyInput(); + return true; + } + + // The input is live afterwards, either in future instructions or in a + // safepoint for the reusing instruction. This is impossible to satisfy + // without copying the input. + // + // It may or may not be better to split the input into two bundles at the + // point of the definition, which may permit merging. One case where it is + // definitely better to split is if the input never has any register uses + // after the instruction. Handle this splitting eagerly. + + LBlock* block = def.ins()->block(); + + // The input's lifetime must end within the same block as the definition, + // otherwise it could live on in phis elsewhere. + if (inputRange != input.lastRange() || inputRange->to() > exitOf(block)) { + def.setMustCopyInput(); + return true; + } + + // If we already split the input for some other register, don't make a + // third bundle. + if (inputRange->bundle() != input.firstRange()->bundle()) { + def.setMustCopyInput(); + return true; + } + + // If the input will start out in memory then adding a separate bundle for + // memory uses after the def won't help. + if (input.def()->isFixed() && !input.def()->output()->isRegister()) { + def.setMustCopyInput(); + return true; + } + + // The input cannot have register or reused uses after the definition. + for (UsePositionIterator iter = inputRange->usesBegin(); iter; iter++) { + if (iter->pos <= inputOf(def.ins())) { + continue; + } + + LUse* use = iter->use(); + if (FindReusingDefOrTemp(insData[iter->pos], use)) { + def.setMustCopyInput(); + return true; + } + if (iter->usePolicy() != LUse::ANY && + iter->usePolicy() != LUse::KEEPALIVE) { + def.setMustCopyInput(); + return true; + } + } + + LiveRange* preRange = LiveRange::FallibleNew( + alloc(), &input, inputRange->from(), outputOf(def.ins())); + if (!preRange) { + return false; + } + + // The new range starts at reg's input position, which means it overlaps + // with the old range at one position. This is what we want, because we + // need to copy the input before the instruction. + LiveRange* postRange = LiveRange::FallibleNew( + alloc(), &input, inputOf(def.ins()), inputRange->to()); + if (!postRange) { + return false; + } + + inputRange->tryToMoveDefAndUsesInto(preRange); + inputRange->tryToMoveDefAndUsesInto(postRange); + MOZ_ASSERT(!inputRange->hasUses()); + + JitSpewIfEnabled(JitSpew_RegAlloc, + " splitting reused input at %u to try to help grouping", + inputOf(def.ins()).bits()); + + LiveBundle* firstBundle = inputRange->bundle(); + input.removeRange(inputRange); + input.addRange(preRange); + input.addRange(postRange); + + firstBundle->removeRange(inputRange); + firstBundle->addRange(preRange); + + // The new range goes in a separate bundle, where it will be spilled during + // allocation. + LiveBundle* secondBundle = LiveBundle::FallibleNew(alloc(), nullptr, nullptr); + if (!secondBundle) { + return false; + } + secondBundle->addRange(postRange); + + return tryMergeBundles(def.firstBundle(), input.firstBundle()); +} + +bool BacktrackingAllocator::mergeAndQueueRegisters() { + MOZ_ASSERT(!vregs[0u].hasRanges()); + + // Create a bundle for each register containing all its ranges. + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + if (!reg.hasRanges()) { + continue; + } + + LiveBundle* bundle = LiveBundle::FallibleNew(alloc(), nullptr, nullptr); + if (!bundle) { + return false; + } + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + bundle->addRange(range); + } + } + + // If there is an OSR block, merge parameters in that block with the + // corresponding parameters in the initial block. + if (MBasicBlock* osr = graph.mir().osrBlock()) { + size_t original = 1; + for (LInstructionIterator iter = osr->lir()->begin(); + iter != osr->lir()->end(); iter++) { + if (iter->isParameter()) { + for (size_t i = 0; i < iter->numDefs(); i++) { + DebugOnly<bool> found = false; + VirtualRegister& paramVreg = vreg(iter->getDef(i)); + for (; original < paramVreg.vreg(); original++) { + VirtualRegister& originalVreg = vregs[original]; + if (*originalVreg.def()->output() == *iter->getDef(i)->output()) { + MOZ_ASSERT(originalVreg.ins()->isParameter()); + if (!tryMergeBundles(originalVreg.firstBundle(), + paramVreg.firstBundle())) { + return false; + } + found = true; + break; + } + } + MOZ_ASSERT(found); + } + } + } + } + + // Try to merge registers with their reused inputs. + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + if (!reg.hasRanges()) { + continue; + } + + if (reg.def()->policy() == LDefinition::MUST_REUSE_INPUT) { + LUse* use = reg.ins() + ->toInstruction() + ->getOperand(reg.def()->getReusedInput()) + ->toUse(); + if (!tryMergeReusedRegister(reg, vreg(use))) { + return false; + } + } + } + + // Try to merge phis with their inputs. + for (size_t i = 0; i < graph.numBlocks(); i++) { + LBlock* block = graph.getBlock(i); + for (size_t j = 0; j < block->numPhis(); j++) { + LPhi* phi = block->getPhi(j); + VirtualRegister& outputVreg = vreg(phi->getDef(0)); + for (size_t k = 0, kend = phi->numOperands(); k < kend; k++) { + VirtualRegister& inputVreg = vreg(phi->getOperand(k)->toUse()); + if (!tryMergeBundles(inputVreg.firstBundle(), + outputVreg.firstBundle())) { + return false; + } + } + } + } + + // Add all bundles to the allocation queue, and create spill sets for them. + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + + // Eagerly allocate stack result areas and their component stack results. + if (reg.def() && reg.def()->policy() == LDefinition::STACK) { + allocateStackDefinition(reg); + } + + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveBundle* bundle = range->bundle(); + if (range == bundle->firstRange()) { + if (!alloc().ensureBallast()) { + return false; + } + + SpillSet* spill = SpillSet::New(alloc()); + if (!spill) { + return false; + } + bundle->setSpillSet(spill); + + size_t priority = computePriority(bundle); + if (!allocationQueue.insert(QueueItem(bundle, priority))) { + return false; + } + } + } + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Code for the splitting/spilling subsystem begins here. // +// // +// The code that follows is structured in the following sequence: // +// // +// (1) Routines that are helpers for ::splitAt. // +// (2) ::splitAt itself, which implements splitting decisions. // +// (3) heuristic routines (eg ::splitAcrossCalls), which decide where // +// splits should be made. They then call ::splitAt to perform the // +// chosen split. // +// (4) The top level driver, ::chooseBundleSplit. // +// // +// There are further comments on ::splitAt and ::chooseBundleSplit below. // +// // +/////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////// +// // +// Implementation of splitting decisions, but not the making of those // +// decisions: various helper functions // +// // +/////////////////////////////////////////////////////////////////////////////// + +bool BacktrackingAllocator::updateVirtualRegisterListsThenRequeueBundles( + LiveBundle* bundle, const LiveBundleVector& newBundles) { +#ifdef DEBUG + if (newBundles.length() == 1) { + LiveBundle* newBundle = newBundles[0]; + if (newBundle->numRanges() == bundle->numRanges() && + computePriority(newBundle) == computePriority(bundle)) { + bool different = false; + LiveRange::BundleLinkIterator oldRanges = bundle->rangesBegin(); + LiveRange::BundleLinkIterator newRanges = newBundle->rangesBegin(); + while (oldRanges) { + LiveRange* oldRange = LiveRange::get(*oldRanges); + LiveRange* newRange = LiveRange::get(*newRanges); + if (oldRange->from() != newRange->from() || + oldRange->to() != newRange->to()) { + different = true; + break; + } + oldRanges++; + newRanges++; + } + + // This is likely to trigger an infinite loop in register allocation. This + // can be the result of invalid register constraints, making regalloc + // impossible; consider relaxing those. + MOZ_ASSERT(different, + "Split results in the same bundle with the same priority"); + } + } +#endif + + if (JitSpewEnabled(JitSpew_RegAlloc)) { + JitSpew(JitSpew_RegAlloc, " .. into:"); + for (size_t i = 0; i < newBundles.length(); i++) { + JitSpew(JitSpew_RegAlloc, " %s", newBundles[i]->toString().get()); + } + } + + // Remove all ranges in the old bundle from their register's list. + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + range->vreg().removeRange(range); + } + + // Add all ranges in the new bundles to their register's list. + for (size_t i = 0; i < newBundles.length(); i++) { + LiveBundle* newBundle = newBundles[i]; + for (LiveRange::BundleLinkIterator iter = newBundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + range->vreg().addRange(range); + } + } + + // Queue the new bundles for register assignment. + for (size_t i = 0; i < newBundles.length(); i++) { + LiveBundle* newBundle = newBundles[i]; + size_t priority = computePriority(newBundle); + if (!allocationQueue.insert(QueueItem(newBundle, priority))) { + return false; + } + } + + return true; +} + +// Helper for ::splitAt +// When splitting a bundle according to a list of split positions, return +// whether a use or range at |pos| should use a different bundle than the last +// position this was called for. +static bool UseNewBundle(const SplitPositionVector& splitPositions, + CodePosition pos, size_t* activeSplitPosition) { + if (splitPositions.empty()) { + // When the split positions are empty we are splitting at all uses. + return true; + } + + if (*activeSplitPosition == splitPositions.length()) { + // We've advanced past all split positions. + return false; + } + + if (splitPositions[*activeSplitPosition] > pos) { + // We haven't gotten to the next split position yet. + return false; + } + + // We've advanced past the next split position, find the next one which we + // should split at. + while (*activeSplitPosition < splitPositions.length() && + splitPositions[*activeSplitPosition] <= pos) { + (*activeSplitPosition)++; + } + return true; +} + +// Helper for ::splitAt +static bool HasPrecedingRangeSharingVreg(LiveBundle* bundle, LiveRange* range) { + MOZ_ASSERT(range->bundle() == bundle); + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* prevRange = LiveRange::get(*iter); + if (prevRange == range) { + return false; + } + if (&prevRange->vreg() == &range->vreg()) { + return true; + } + } + + MOZ_CRASH(); +} + +// Helper for ::splitAt +static bool HasFollowingRangeSharingVreg(LiveBundle* bundle, LiveRange* range) { + MOZ_ASSERT(range->bundle() == bundle); + + bool foundRange = false; + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* prevRange = LiveRange::get(*iter); + if (foundRange && &prevRange->vreg() == &range->vreg()) { + return true; + } + if (prevRange == range) { + foundRange = true; + } + } + + MOZ_ASSERT(foundRange); + return false; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Implementation of splitting decisions, but not the making of those // +// decisions: // +// ::splitAt // +// // +/////////////////////////////////////////////////////////////////////////////// + +// ::splitAt +// --------- +// It would be nice to be able to interpret ::splitAt as simply performing +// whatever split the heuristic routines decide on. Unfortunately it +// tries to "improve" on the initial locations, which as +// https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17 shows, often +// leads to excessive spilling. So there is no clean distinction between +// policy (where to split, computed by the heuristic routines) and +// implementation (done by ::splitAt). +// +// ::splitAt -- creation of spill parent bundles +// --------------------------------------------- +// To understand what ::splitAt does, we must refer back to Section 1's +// description of LiveBundle::spillParent_. +// +// Initially (as created by Phase 1), all bundles have `spillParent_` being +// NULL. If ::splitAt is asked to split such a bundle, it will first create a +// "spill bundle" or "spill parent" bundle. This is a copy of the original, +// with two changes: +// +// * all register uses have been removed, so that only stack-compatible uses +// remain. +// +// * for all LiveRanges in the bundle that define a register, the start point +// of the range is moved one CodePosition forwards, thusly: +// +// from = minimalDefEnd(insData[from]).next(); +// +// The reason for the latter relates to the idea described in Section 1, that +// all LiveRanges for any given VirtualRegister must form a tree rooted at the +// defining LiveRange. If the spill-bundle definition range start points are +// the same as those in the original bundle, then we will end up with two roots +// for the tree, and it is then unclear which one should supply "the value". +// +// Putting the spill-bundle start point one CodePosition further along causes +// the range containing the register def (after splitting) to still be the +// defining point. ::createMoveGroupsFromLiveRangeTransitions will observe the +// equivalent spill-bundle range starting one point later and add a MoveGroup +// to move the value into it. Since the spill bundle is intended to be stack +// resident, the effect is to force creation of the MoveGroup that will +// actually spill this value onto the stack. +// +// If the bundle provided to ::splitAt already has a spill parent, then +// ::splitAt doesn't create a new spill parent. This situation will happen +// when the bundle to be split was itself created by splitting. The effect is +// that *all* bundles created from an "original bundle" share the same spill +// parent, and hence they will share the same spill slot, which guarantees that +// all the spilled fragments of a VirtualRegister share the same spill slot, +// which means we'll never have to move a VirtualRegister between different +// spill slots during its lifetime. +// +// ::splitAt -- creation of other bundles +// -------------------------------------- +// With the spill parent bundle question out of the way, ::splitAt then goes on +// to create the remaining new bundles, using near-incomprehensible logic +// steered by `UseNewBundle`. +// +// This supposedly splits the bundle at the positions given by the +// `SplitPositionVector` parameter to ::splitAt, putting them in a temporary +// vector `newBundles`. Whether it really splits at the requested positions or +// not is hard to say; more important is what happens next. +// +// ::splitAt -- "improvement" ("filtering") of the split bundles +// ------------------------------------------------------------- +// ::splitAt now tries to reduce the length of the LiveRanges that make up the +// new bundles (not including the "spill parent"). I assume this is to remove +// sections of the bundles that carry no useful value (eg, extending after the +// last using a range), thereby removing the demand for registers in those +// parts. This does however mean that ::splitAt is no longer really splitting +// where the heuristic routines wanted, and that can lead to a big increase in +// spilling in loops, as +// https://bugzilla.mozilla.org/show_bug.cgi?id=1758274#c17 describes. +// +// ::splitAt -- meaning of the incoming `SplitPositionVector` +// ---------------------------------------------------------- +// ::splitAt has one last mystery which is important to document. The split +// positions are specified as CodePositions, but this leads to ambiguity +// because, in a sequence of N (LIR) instructions, there are 2N valid +// CodePositions. For example: +// +// 6-7 WasmLoadTls [def v2<o>] [use v1:R] +// 8-9 WasmNullConstant [def v3<o>] +// +// Consider splitting the range for `v2`, which starts at CodePosition 7. +// What's the difference between saying "split it at 7" and "split it at 8" ? +// Not much really, since in both cases what we intend is for the range to be +// split in between the two instructions. +// +// Hence I believe the semantics is: +// +// * splitting at an even numbered CodePosition (eg, 8), which is an input-side +// position, means "split before the instruction containing this position". +// +// * splitting at an odd numbered CodePositin (eg, 7), which is an output-side +// position, means "split after the instruction containing this position". +// +// Hence in the example, we could specify either 7 or 8 to mean the same +// placement of the split. Well, almost true, but actually: +// +// (SPEC) specifying 8 means +// +// "split between these two insns, and any resulting MoveGroup goes in the +// list to be emitted before the start of the second insn" +// +// (SPEC) specifying 7 means +// +// "split between these two insns, and any resulting MoveGroup goes in the +// list to be emitted after the end of the first insn" +// +// In most cases we don't care on which "side of the valley" the MoveGroup ends +// up, in which case we can use either convention. +// +// (SPEC) I believe these semantics are implied by the logic in +// ::createMoveGroupsFromLiveRangeTransitions. They are certainly not +// documented anywhere in the code. + +bool BacktrackingAllocator::splitAt(LiveBundle* bundle, + const SplitPositionVector& splitPositions) { + // Split the bundle at the given split points. Register uses which have no + // intervening split points are consolidated into the same bundle. If the + // list of split points is empty, then all register uses are placed in + // minimal bundles. + + // splitPositions should be sorted. + for (size_t i = 1; i < splitPositions.length(); ++i) { + MOZ_ASSERT(splitPositions[i - 1] < splitPositions[i]); + } + + // We don't need to create a new spill bundle if there already is one. + bool spillBundleIsNew = false; + LiveBundle* spillBundle = bundle->spillParent(); + if (!spillBundle) { + spillBundle = LiveBundle::FallibleNew(alloc(), bundle->spillSet(), nullptr); + if (!spillBundle) { + return false; + } + spillBundleIsNew = true; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + CodePosition from = range->from(); + if (isRegisterDefinition(range)) { + from = minimalDefEnd(insData[from]).next(); + } + + if (from < range->to()) { + if (!spillBundle->addRange(alloc(), &range->vreg(), from, + range->to())) { + return false; + } + + if (range->hasDefinition() && !isRegisterDefinition(range)) { + spillBundle->lastRange()->setHasDefinition(); + } + } + } + } + + LiveBundleVector newBundles; + + // The bundle which ranges are currently being added to. + LiveBundle* activeBundle = + LiveBundle::FallibleNew(alloc(), bundle->spillSet(), spillBundle); + if (!activeBundle || !newBundles.append(activeBundle)) { + return false; + } + + // State for use by UseNewBundle. + size_t activeSplitPosition = 0; + + // Make new bundles according to the split positions, and distribute ranges + // and uses to them. + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + if (UseNewBundle(splitPositions, range->from(), &activeSplitPosition)) { + activeBundle = + LiveBundle::FallibleNew(alloc(), bundle->spillSet(), spillBundle); + if (!activeBundle || !newBundles.append(activeBundle)) { + return false; + } + } + + LiveRange* activeRange = LiveRange::FallibleNew(alloc(), &range->vreg(), + range->from(), range->to()); + if (!activeRange) { + return false; + } + activeBundle->addRange(activeRange); + + if (isRegisterDefinition(range)) { + activeRange->setHasDefinition(); + } + + while (range->hasUses()) { + UsePosition* use = range->popUse(); + LNode* ins = insData[use->pos]; + + // Any uses of a register that appear before its definition has + // finished must be associated with the range for that definition. + if (isRegisterDefinition(range) && + use->pos <= minimalDefEnd(insData[range->from()])) { + activeRange->addUse(use); + } else if (isRegisterUse(use, ins)) { + // Place this register use into a different bundle from the + // last one if there are any split points between the two uses. + // UseNewBundle always returns true if we are splitting at all + // register uses, but we can still reuse the last range and + // bundle if they have uses at the same position, except when + // either use is fixed (the two uses might require incompatible + // registers.) + if (UseNewBundle(splitPositions, use->pos, &activeSplitPosition) && + (!activeRange->hasUses() || + activeRange->usesBegin()->pos != use->pos || + activeRange->usesBegin()->usePolicy() == LUse::FIXED || + use->usePolicy() == LUse::FIXED)) { + activeBundle = + LiveBundle::FallibleNew(alloc(), bundle->spillSet(), spillBundle); + if (!activeBundle || !newBundles.append(activeBundle)) { + return false; + } + activeRange = LiveRange::FallibleNew(alloc(), &range->vreg(), + range->from(), range->to()); + if (!activeRange) { + return false; + } + activeBundle->addRange(activeRange); + } + + activeRange->addUse(use); + } else { + MOZ_ASSERT(spillBundleIsNew); + spillBundle->rangeFor(use->pos)->addUse(use); + } + } + } + + LiveBundleVector filteredBundles; + + // Trim the ends of ranges in each new bundle when there are no other + // earlier or later ranges in the same bundle with the same vreg. + for (size_t i = 0; i < newBundles.length(); i++) { + LiveBundle* bundle = newBundles[i]; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter;) { + LiveRange* range = LiveRange::get(*iter); + + if (!range->hasDefinition()) { + if (!HasPrecedingRangeSharingVreg(bundle, range)) { + if (range->hasUses()) { + UsePosition* use = *range->usesBegin(); + range->setFrom(inputOf(insData[use->pos])); + } else { + bundle->removeRangeAndIncrementIterator(iter); + continue; + } + } + } + + if (!HasFollowingRangeSharingVreg(bundle, range)) { + if (range->hasUses()) { + UsePosition* use = range->lastUse(); + range->setTo(use->pos.next()); + } else if (range->hasDefinition()) { + range->setTo(minimalDefEnd(insData[range->from()]).next()); + } else { + bundle->removeRangeAndIncrementIterator(iter); + continue; + } + } + + iter++; + } + + if (bundle->hasRanges() && !filteredBundles.append(bundle)) { + return false; + } + } + + if (spillBundleIsNew && !filteredBundles.append(spillBundle)) { + return false; + } + + return updateVirtualRegisterListsThenRequeueBundles(bundle, filteredBundles); +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Creation of splitting decisions, but not their implementation: // +// ::splitAcrossCalls // +// ::trySplitAcrossHotcode // +// ::trySplitAfterLastRegisterUse // +// ::trySplitBeforeFirstRegisterUse // +// // +/////////////////////////////////////////////////////////////////////////////// + +bool BacktrackingAllocator::splitAcrossCalls(LiveBundle* bundle) { + // Split the bundle to separate register uses and non-register uses and + // allow the vreg to be spilled across its range. + + // Find the locations of all calls in the bundle's range. + SplitPositionVector callPositions; + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + CallRange searchRange(range->from(), range->to()); + CallRange* callRange; + if (!callRanges.contains(&searchRange, &callRange)) { + // There are no calls inside this range. + continue; + } + MOZ_ASSERT(range->covers(callRange->range.from)); + + // The search above returns an arbitrary call within the range. Walk + // backwards to find the first call in the range. + for (CallRangeList::reverse_iterator riter = + callRangesList.rbegin(callRange); + riter != callRangesList.rend(); ++riter) { + CodePosition pos = riter->range.from; + if (range->covers(pos)) { + callRange = *riter; + } else { + break; + } + } + + // Add all call positions within the range, by walking forwards. + for (CallRangeList::iterator iter = callRangesList.begin(callRange); + iter != callRangesList.end(); ++iter) { + CodePosition pos = iter->range.from; + if (!range->covers(pos)) { + break; + } + + // Calls at the beginning of the range are ignored; there is no splitting + // to do. + if (range->covers(pos.previous())) { + MOZ_ASSERT_IF(callPositions.length(), pos > callPositions.back()); + if (!callPositions.append(pos)) { + return false; + } + } + } + } + MOZ_ASSERT(callPositions.length()); + +#ifdef JS_JITSPEW + JitSpewStart(JitSpew_RegAlloc, " .. split across calls at "); + for (size_t i = 0; i < callPositions.length(); ++i) { + JitSpewCont(JitSpew_RegAlloc, "%s%u", i != 0 ? ", " : "", + callPositions[i].bits()); + } + JitSpewFin(JitSpew_RegAlloc); +#endif + + return splitAt(bundle, callPositions); +} + +bool BacktrackingAllocator::trySplitAcrossHotcode(LiveBundle* bundle, + bool* success) { + // If this bundle has portions that are hot and portions that are cold, + // split it at the boundaries between hot and cold code. + + LiveRange* hotRange = nullptr; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (hotcode.contains(range, &hotRange)) { + break; + } + } + + // Don't split if there is no hot code in the bundle. + if (!hotRange) { + JitSpew(JitSpew_RegAlloc, " .. bundle does not contain hot code"); + return true; + } + + // Don't split if there is no cold code in the bundle. + bool coldCode = false; + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (!hotRange->contains(range)) { + coldCode = true; + break; + } + } + if (!coldCode) { + JitSpew(JitSpew_RegAlloc, " .. bundle does not contain cold code"); + return true; + } + + JitSpewIfEnabled(JitSpew_RegAlloc, " .. split across hot range %s", + hotRange->toString().get()); + + // Tweak the splitting method when compiling wasm code to look at actual + // uses within the hot/cold code. This heuristic is in place as the below + // mechanism regresses several asm.js tests. Hopefully this will be fixed + // soon and this special case removed. See bug 948838. + if (compilingWasm()) { + SplitPositionVector splitPositions; + if (!splitPositions.append(hotRange->from()) || + !splitPositions.append(hotRange->to())) { + return false; + } + *success = true; + return splitAt(bundle, splitPositions); + } + + LiveBundle* hotBundle = LiveBundle::FallibleNew(alloc(), bundle->spillSet(), + bundle->spillParent()); + if (!hotBundle) { + return false; + } + LiveBundle* preBundle = nullptr; + LiveBundle* postBundle = nullptr; + LiveBundle* coldBundle = nullptr; + + if (testbed) { + coldBundle = LiveBundle::FallibleNew(alloc(), bundle->spillSet(), + bundle->spillParent()); + if (!coldBundle) { + return false; + } + } + + // Accumulate the ranges of hot and cold code in the bundle. Note that + // we are only comparing with the single hot range found, so the cold code + // may contain separate hot ranges. + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveRange::Range hot, coldPre, coldPost; + range->intersect(hotRange, &coldPre, &hot, &coldPost); + + if (!hot.empty()) { + if (!hotBundle->addRangeAndDistributeUses(alloc(), range, hot.from, + hot.to)) { + return false; + } + } + + if (!coldPre.empty()) { + if (testbed) { + if (!coldBundle->addRangeAndDistributeUses(alloc(), range, coldPre.from, + coldPre.to)) { + return false; + } + } else { + if (!preBundle) { + preBundle = LiveBundle::FallibleNew(alloc(), bundle->spillSet(), + bundle->spillParent()); + if (!preBundle) { + return false; + } + } + if (!preBundle->addRangeAndDistributeUses(alloc(), range, coldPre.from, + coldPre.to)) { + return false; + } + } + } + + if (!coldPost.empty()) { + if (testbed) { + if (!coldBundle->addRangeAndDistributeUses( + alloc(), range, coldPost.from, coldPost.to)) { + return false; + } + } else { + if (!postBundle) { + postBundle = LiveBundle::FallibleNew(alloc(), bundle->spillSet(), + bundle->spillParent()); + if (!postBundle) { + return false; + } + } + if (!postBundle->addRangeAndDistributeUses( + alloc(), range, coldPost.from, coldPost.to)) { + return false; + } + } + } + } + + MOZ_ASSERT(hotBundle->numRanges() != 0); + + LiveBundleVector newBundles; + if (!newBundles.append(hotBundle)) { + return false; + } + + if (testbed) { + MOZ_ASSERT(coldBundle->numRanges() != 0); + if (!newBundles.append(coldBundle)) { + return false; + } + } else { + MOZ_ASSERT(preBundle || postBundle); + if (preBundle && !newBundles.append(preBundle)) { + return false; + } + if (postBundle && !newBundles.append(postBundle)) { + return false; + } + } + + *success = true; + return updateVirtualRegisterListsThenRequeueBundles(bundle, newBundles); +} + +bool BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveBundle* bundle, + LiveBundle* conflict, + bool* success) { + // If this bundle's later uses do not require it to be in a register, + // split it after the last use which does require a register. If conflict + // is specified, only consider register uses before the conflict starts. + + CodePosition lastRegisterFrom, lastRegisterTo, lastUse; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + // If the range defines a register, consider that a register use for + // our purposes here. + if (isRegisterDefinition(range)) { + CodePosition spillStart = minimalDefEnd(insData[range->from()]).next(); + if (!conflict || spillStart < conflict->firstRange()->from()) { + lastUse = lastRegisterFrom = range->from(); + lastRegisterTo = spillStart; + } + } + + for (UsePositionIterator iter(range->usesBegin()); iter; iter++) { + LNode* ins = insData[iter->pos]; + + // Uses in the bundle should be sorted. + MOZ_ASSERT(iter->pos >= lastUse); + lastUse = inputOf(ins); + + if (!conflict || outputOf(ins) < conflict->firstRange()->from()) { + if (isRegisterUse(*iter, ins, /* considerCopy = */ true)) { + lastRegisterFrom = inputOf(ins); + lastRegisterTo = iter->pos.next(); + } + } + } + } + + // Can't trim non-register uses off the end by splitting. + if (!lastRegisterFrom.bits()) { + JitSpew(JitSpew_RegAlloc, " .. bundle has no register uses"); + return true; + } + if (lastUse < lastRegisterTo) { + JitSpew(JitSpew_RegAlloc, " .. bundle's last use is a register use"); + return true; + } + + JitSpewIfEnabled(JitSpew_RegAlloc, " .. split after last register use at %u", + lastRegisterTo.bits()); + + SplitPositionVector splitPositions; + if (!splitPositions.append(lastRegisterTo)) { + return false; + } + *success = true; + return splitAt(bundle, splitPositions); +} + +bool BacktrackingAllocator::trySplitBeforeFirstRegisterUse(LiveBundle* bundle, + LiveBundle* conflict, + bool* success) { + // If this bundle's earlier uses do not require it to be in a register, + // split it before the first use which does require a register. If conflict + // is specified, only consider register uses after the conflict ends. + + if (isRegisterDefinition(bundle->firstRange())) { + JitSpew(JitSpew_RegAlloc, " .. bundle is defined by a register"); + return true; + } + if (!bundle->firstRange()->hasDefinition()) { + JitSpew(JitSpew_RegAlloc, " .. bundle does not have definition"); + return true; + } + + CodePosition firstRegisterFrom; + + CodePosition conflictEnd; + if (conflict) { + for (LiveRange::BundleLinkIterator iter = conflict->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (range->to() > conflictEnd) { + conflictEnd = range->to(); + } + } + } + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + if (!conflict || range->from() > conflictEnd) { + if (range->hasDefinition() && isRegisterDefinition(range)) { + firstRegisterFrom = range->from(); + break; + } + } + + for (UsePositionIterator iter(range->usesBegin()); iter; iter++) { + LNode* ins = insData[iter->pos]; + + if (!conflict || outputOf(ins) >= conflictEnd) { + if (isRegisterUse(*iter, ins, /* considerCopy = */ true)) { + firstRegisterFrom = inputOf(ins); + break; + } + } + } + if (firstRegisterFrom.bits()) { + break; + } + } + + if (!firstRegisterFrom.bits()) { + // Can't trim non-register uses off the beginning by splitting. + JitSpew(JitSpew_RegAlloc, " bundle has no register uses"); + return true; + } + + JitSpewIfEnabled(JitSpew_RegAlloc, + " .. split before first register use at %u", + firstRegisterFrom.bits()); + + SplitPositionVector splitPositions; + if (!splitPositions.append(firstRegisterFrom)) { + return false; + } + *success = true; + return splitAt(bundle, splitPositions); +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// The top level driver for the splitting machinery // +// // +/////////////////////////////////////////////////////////////////////////////// + +// ::chooseBundleSplit +// ------------------- +// If the first allocation loop (in ::go) can't allocate a bundle, it hands it +// off to ::chooseBundleSplit, which is the "entry point" of the bundle-split +// machinery. This tries four heuristics in turn, to see if any can split the +// bundle: +// +// * ::trySplitAcrossHotcode +// * ::splitAcrossCalls (in some cases) +// * ::trySplitBeforeFirstRegisterUse +// * ::trySplitAfterLastRegisterUse +// +// These routines have similar structure: they try to decide on one or more +// CodePositions at which to split the bundle, using whatever heuristics they +// have to hand. If suitable CodePosition(s) are found, they are put into a +// `SplitPositionVector`, and the bundle and the vector are handed off to +// ::splitAt, which performs the split (at least in theory) at the chosen +// positions. It also arranges for the new bundles to be added to +// ::allocationQueue. +// +// ::trySplitAcrossHotcode has a special case for JS -- it modifies the +// bundle(s) itself, rather than using ::splitAt. +// +// If none of the heuristic routines apply, then ::splitAt is called with an +// empty vector of split points. This is interpreted to mean "split at all +// register uses". When combined with how ::splitAt works, the effect is to +// spill the bundle. + +bool BacktrackingAllocator::chooseBundleSplit(LiveBundle* bundle, bool fixed, + LiveBundle* conflict) { + bool success = false; + + JitSpewIfEnabled(JitSpew_RegAlloc, " Splitting %s ..", + bundle->toString().get()); + + if (!trySplitAcrossHotcode(bundle, &success)) { + return false; + } + if (success) { + return true; + } + + if (fixed) { + return splitAcrossCalls(bundle); + } + + if (!trySplitBeforeFirstRegisterUse(bundle, conflict, &success)) { + return false; + } + if (success) { + return true; + } + + if (!trySplitAfterLastRegisterUse(bundle, conflict, &success)) { + return false; + } + if (success) { + return true; + } + + // Split at all register uses. + SplitPositionVector emptyPositions; + return splitAt(bundle, emptyPositions); +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Bundle allocation // +// // +/////////////////////////////////////////////////////////////////////////////// + +static const size_t MAX_ATTEMPTS = 2; + +bool BacktrackingAllocator::computeRequirement(LiveBundle* bundle, + Requirement* requirement, + Requirement* hint) { + // Set any requirement or hint on bundle according to its definition and + // uses. Return false if there are conflicting requirements which will + // require the bundle to be split. + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + VirtualRegister& reg = range->vreg(); + + if (range->hasDefinition()) { + // Deal with any definition constraints/hints. + LDefinition::Policy policy = reg.def()->policy(); + if (policy == LDefinition::FIXED || policy == LDefinition::STACK) { + // Fixed and stack policies get a FIXED requirement. (In the stack + // case, the allocation should have been performed already by + // mergeAndQueueRegisters.) + JitSpewIfEnabled(JitSpew_RegAlloc, + " Requirement %s, fixed by definition", + reg.def()->output()->toString().get()); + if (!requirement->merge(Requirement(*reg.def()->output()))) { + return false; + } + } else if (reg.ins()->isPhi()) { + // Phis don't have any requirements, but they should prefer their + // input allocations. This is captured by the group hints above. + } else { + // Non-phis get a REGISTER requirement. + if (!requirement->merge(Requirement(Requirement::REGISTER))) { + return false; + } + } + } + + // Search uses for requirements. + for (UsePositionIterator iter = range->usesBegin(); iter; iter++) { + LUse::Policy policy = iter->usePolicy(); + if (policy == LUse::FIXED) { + AnyRegister required = GetFixedRegister(reg.def(), iter->use()); + + JitSpewIfEnabled(JitSpew_RegAlloc, " Requirement %s, due to use at %u", + required.name(), iter->pos.bits()); + + // If there are multiple fixed registers which the bundle is + // required to use, fail. The bundle will need to be split before + // it can be allocated. + if (!requirement->merge(Requirement(LAllocation(required)))) { + return false; + } + } else if (policy == LUse::REGISTER) { + if (!requirement->merge(Requirement(Requirement::REGISTER))) { + return false; + } + } else if (policy == LUse::ANY) { + // ANY differs from KEEPALIVE by actively preferring a register. + if (!hint->merge(Requirement(Requirement::REGISTER))) { + return false; + } + } + + // The only case of STACK use policies is individual stack results using + // their containing stack result area, which is given a fixed allocation + // above. + MOZ_ASSERT_IF(policy == LUse::STACK, + requirement->kind() == Requirement::FIXED); + MOZ_ASSERT_IF(policy == LUse::STACK, + requirement->allocation().isStackArea()); + } + } + + return true; +} + +bool BacktrackingAllocator::tryAllocateRegister(PhysicalRegister& r, + LiveBundle* bundle, + bool* success, bool* pfixed, + LiveBundleVector& conflicting) { + *success = false; + + if (!r.allocatable) { + return true; + } + + LiveBundleVector aliasedConflicting; + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveRangePlus rangePlus(range); + + // All ranges in the bundle must be compatible with the physical register. + MOZ_ASSERT(range->vreg().isCompatible(r.reg)); + + for (size_t a = 0; a < r.reg.numAliased(); a++) { + PhysicalRegister& rAlias = registers[r.reg.aliased(a).code()]; + LiveRangePlus existingPlus; + if (!rAlias.allocations.contains(rangePlus, &existingPlus)) { + continue; + } + const LiveRange* existing = existingPlus.liveRange(); + if (existing->hasVreg()) { + MOZ_ASSERT(existing->bundle()->allocation().toRegister() == rAlias.reg); + bool duplicate = false; + for (size_t i = 0; i < aliasedConflicting.length(); i++) { + if (aliasedConflicting[i] == existing->bundle()) { + duplicate = true; + break; + } + } + if (!duplicate && !aliasedConflicting.append(existing->bundle())) { + return false; + } + } else { + JitSpewIfEnabled(JitSpew_RegAlloc, " %s collides with fixed use %s", + rAlias.reg.name(), existing->toString().get()); + *pfixed = true; + return true; + } + } + } + + if (!aliasedConflicting.empty()) { + // One or more aliased registers is allocated to another bundle + // overlapping this one. Keep track of the conflicting set, and in the + // case of multiple conflicting sets keep track of the set with the + // lowest maximum spill weight. + + // The #ifdef guards against "unused variable 'existing'" bustage. +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_RegAlloc)) { + if (aliasedConflicting.length() == 1) { + LiveBundle* existing = aliasedConflicting[0]; + JitSpew(JitSpew_RegAlloc, " %s collides with %s [weight %zu]", + r.reg.name(), existing->toString().get(), + computeSpillWeight(existing)); + } else { + JitSpew(JitSpew_RegAlloc, " %s collides with the following", + r.reg.name()); + for (size_t i = 0; i < aliasedConflicting.length(); i++) { + LiveBundle* existing = aliasedConflicting[i]; + JitSpew(JitSpew_RegAlloc, " %s [weight %zu]", + existing->toString().get(), computeSpillWeight(existing)); + } + } + } +#endif + + if (conflicting.empty()) { + conflicting = std::move(aliasedConflicting); + } else { + if (maximumSpillWeight(aliasedConflicting) < + maximumSpillWeight(conflicting)) { + conflicting = std::move(aliasedConflicting); + } + } + return true; + } + + JitSpewIfEnabled(JitSpew_RegAlloc, " allocated to %s", r.reg.name()); + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (!alloc().ensureBallast()) { + return false; + } + LiveRangePlus rangePlus(range); + if (!r.allocations.insert(rangePlus)) { + return false; + } + } + + bundle->setAllocation(LAllocation(r.reg)); + *success = true; + return true; +} + +bool BacktrackingAllocator::tryAllocateAnyRegister( + LiveBundle* bundle, bool* success, bool* pfixed, + LiveBundleVector& conflicting) { + // Search for any available register which the bundle can be allocated to. + + LDefinition::Type type = bundle->firstRange()->vreg().type(); + + if (LDefinition::isFloatReg(type)) { + for (size_t i = AnyRegister::FirstFloatReg; i < AnyRegister::Total; i++) { + if (!LDefinition::isFloatRegCompatible(type, registers[i].reg.fpu())) { + continue; + } + if (!tryAllocateRegister(registers[i], bundle, success, pfixed, + conflicting)) { + return false; + } + if (*success) { + break; + } + } + return true; + } + + for (size_t i = 0; i < AnyRegister::FirstFloatReg; i++) { + if (!tryAllocateRegister(registers[i], bundle, success, pfixed, + conflicting)) { + return false; + } + if (*success) { + break; + } + } + return true; +} + +bool BacktrackingAllocator::evictBundle(LiveBundle* bundle) { + JitSpewIfEnabled(JitSpew_RegAlloc, + " Evicting %s [priority %zu] [weight %zu]", + bundle->toString().get(), computePriority(bundle), + computeSpillWeight(bundle)); + + AnyRegister reg(bundle->allocation().toRegister()); + PhysicalRegister& physical = registers[reg.code()]; + MOZ_ASSERT(physical.reg == reg && physical.allocatable); + + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveRangePlus rangePlus(range); + physical.allocations.remove(rangePlus); + } + + bundle->setAllocation(LAllocation()); + + size_t priority = computePriority(bundle); + return allocationQueue.insert(QueueItem(bundle, priority)); +} + +bool BacktrackingAllocator::tryAllocateFixed(LiveBundle* bundle, + Requirement requirement, + bool* success, bool* pfixed, + LiveBundleVector& conflicting) { + // Spill bundles which are required to be in a certain stack slot. + if (!requirement.allocation().isRegister()) { + JitSpew(JitSpew_RegAlloc, " stack allocation requirement"); + bundle->setAllocation(requirement.allocation()); + *success = true; + return true; + } + + AnyRegister reg = requirement.allocation().toRegister(); + return tryAllocateRegister(registers[reg.code()], bundle, success, pfixed, + conflicting); +} + +bool BacktrackingAllocator::tryAllocateNonFixed(LiveBundle* bundle, + Requirement requirement, + Requirement hint, bool* success, + bool* pfixed, + LiveBundleVector& conflicting) { + // If we want, but do not require a bundle to be in a specific register, + // only look at that register for allocating and evict or spill if it is + // not available. Picking a separate register may be even worse than + // spilling, as it will still necessitate moves and will tie up more + // registers than if we spilled. + if (hint.kind() == Requirement::FIXED) { + AnyRegister reg = hint.allocation().toRegister(); + if (!tryAllocateRegister(registers[reg.code()], bundle, success, pfixed, + conflicting)) { + return false; + } + if (*success) { + return true; + } + } + + // Spill bundles which have no hint or register requirement. + if (requirement.kind() == Requirement::NONE && + hint.kind() != Requirement::REGISTER) { + JitSpew(JitSpew_RegAlloc, + " postponed spill (no hint or register requirement)"); + if (!spilledBundles.append(bundle)) { + return false; + } + *success = true; + return true; + } + + if (conflicting.empty() || minimalBundle(bundle)) { + if (!tryAllocateAnyRegister(bundle, success, pfixed, conflicting)) { + return false; + } + if (*success) { + return true; + } + } + + // Spill bundles which have no register requirement if they didn't get + // allocated. + if (requirement.kind() == Requirement::NONE) { + JitSpew(JitSpew_RegAlloc, " postponed spill (no register requirement)"); + if (!spilledBundles.append(bundle)) { + return false; + } + *success = true; + return true; + } + + // We failed to allocate this bundle. + MOZ_ASSERT(!*success); + return true; +} + +bool BacktrackingAllocator::processBundle(MIRGenerator* mir, + LiveBundle* bundle) { + JitSpewIfEnabled(JitSpew_RegAlloc, + "Allocating %s [priority %zu] [weight %zu]", + bundle->toString().get(), computePriority(bundle), + computeSpillWeight(bundle)); + + // A bundle can be processed by doing any of the following: + // + // - Assigning the bundle a register. The bundle cannot overlap any other + // bundle allocated for that physical register. + // + // - Spilling the bundle, provided it has no register uses. + // + // - Splitting the bundle into two or more bundles which cover the original + // one. The new bundles are placed back onto the priority queue for later + // processing. + // + // - Evicting one or more existing allocated bundles, and then doing one + // of the above operations. Evicted bundles are placed back on the + // priority queue. Any evicted bundles must have a lower spill weight + // than the bundle being processed. + // + // As long as this structure is followed, termination is guaranteed. + // In general, we want to minimize the amount of bundle splitting (which + // generally necessitates spills), so allocate longer lived, lower weight + // bundles first and evict and split them later if they prevent allocation + // for higher weight bundles. + + Requirement requirement, hint; + bool canAllocate = computeRequirement(bundle, &requirement, &hint); + + bool fixed; + LiveBundleVector conflicting; + for (size_t attempt = 0;; attempt++) { + if (mir->shouldCancel("Backtracking Allocation (processBundle loop)")) { + return false; + } + + if (canAllocate) { + bool success = false; + fixed = false; + conflicting.clear(); + + // Ok, let's try allocating for this bundle. + if (requirement.kind() == Requirement::FIXED) { + if (!tryAllocateFixed(bundle, requirement, &success, &fixed, + conflicting)) { + return false; + } + } else { + if (!tryAllocateNonFixed(bundle, requirement, hint, &success, &fixed, + conflicting)) { + return false; + } + } + + // If that worked, we're done! + if (success) { + return true; + } + + // If that didn't work, but we have one or more non-fixed bundles + // known to be conflicting, maybe we can evict them and try again. + if ((attempt < MAX_ATTEMPTS || minimalBundle(bundle)) && !fixed && + !conflicting.empty() && + maximumSpillWeight(conflicting) < computeSpillWeight(bundle)) { + for (size_t i = 0; i < conflicting.length(); i++) { + if (!evictBundle(conflicting[i])) { + return false; + } + } + continue; + } + } + + // A minimal bundle cannot be split any further. If we try to split it + // it at this point we will just end up with the same bundle and will + // enter an infinite loop. Weights and the initial live ranges must + // be constructed so that any minimal bundle is allocatable. + MOZ_ASSERT(!minimalBundle(bundle)); + + LiveBundle* conflict = conflicting.empty() ? nullptr : conflicting[0]; + return chooseBundleSplit(bundle, canAllocate && fixed, conflict); + } +} + +// Helper for ::tryAllocatingRegistersForSpillBundles +bool BacktrackingAllocator::spill(LiveBundle* bundle) { + JitSpew(JitSpew_RegAlloc, " Spilling bundle"); + MOZ_ASSERT(bundle->allocation().isBogus()); + + if (LiveBundle* spillParent = bundle->spillParent()) { + JitSpew(JitSpew_RegAlloc, " Using existing spill bundle"); + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveRange* parentRange = spillParent->rangeFor(range->from()); + MOZ_ASSERT(parentRange->contains(range)); + MOZ_ASSERT(&range->vreg() == &parentRange->vreg()); + range->tryToMoveDefAndUsesInto(parentRange); + MOZ_ASSERT(!range->hasUses()); + range->vreg().removeRange(range); + } + return true; + } + + return bundle->spillSet()->addSpilledBundle(bundle); +} + +bool BacktrackingAllocator::tryAllocatingRegistersForSpillBundles() { + for (auto it = spilledBundles.begin(); it != spilledBundles.end(); it++) { + LiveBundle* bundle = *it; + LiveBundleVector conflicting; + bool fixed = false; + bool success = false; + + if (mir->shouldCancel("Backtracking Try Allocating Spilled Bundles")) { + return false; + } + + JitSpewIfEnabled(JitSpew_RegAlloc, "Spill or allocate %s", + bundle->toString().get()); + + if (!tryAllocateAnyRegister(bundle, &success, &fixed, conflicting)) { + return false; + } + + // If the bundle still has no register, spill the bundle. + if (!success && !spill(bundle)) { + return false; + } + } + + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Rewriting of the LIR after bundle processing is done: // +// ::pickStackSlots // +// ::createMoveGroupsFromLiveRangeTransitions // +// ::installAllocationsInLIR // +// ::populateSafepoints // +// ::annotateMoveGroups // +// // +/////////////////////////////////////////////////////////////////////////////// + +// Helper for ::pickStackSlot +bool BacktrackingAllocator::insertAllRanges(LiveRangePlusSet& set, + LiveBundle* bundle) { + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (!alloc().ensureBallast()) { + return false; + } + LiveRangePlus rangePlus(range); + if (!set.insert(rangePlus)) { + return false; + } + } + return true; +} + +// Helper for ::pickStackSlots +bool BacktrackingAllocator::pickStackSlot(SpillSet* spillSet) { + // Look through all ranges that have been spilled in this set for a + // register definition which is fixed to a stack or argument slot. If we + // find one, use it for all bundles that have been spilled. tryMergeBundles + // makes sure this reuse is possible when an initial bundle contains ranges + // from multiple virtual registers. + for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) { + LiveBundle* bundle = spillSet->spilledBundle(i); + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + if (range->hasDefinition()) { + LDefinition* def = range->vreg().def(); + if (def->policy() == LDefinition::FIXED) { + MOZ_ASSERT(!def->output()->isRegister()); + MOZ_ASSERT(!def->output()->isStackSlot()); + spillSet->setAllocation(*def->output()); + return true; + } + } + } + } + + LDefinition::Type type = + spillSet->spilledBundle(0)->firstRange()->vreg().type(); + + SpillSlotList* slotList; + switch (StackSlotAllocator::width(type)) { + case 4: + slotList = &normalSlots; + break; + case 8: + slotList = &doubleSlots; + break; + case 16: + slotList = &quadSlots; + break; + default: + MOZ_CRASH("Bad width"); + } + + // Maximum number of existing spill slots we will look at before giving up + // and allocating a new slot. + static const size_t MAX_SEARCH_COUNT = 10; + + size_t searches = 0; + SpillSlot* stop = nullptr; + while (!slotList->empty()) { + SpillSlot* spillSlot = *slotList->begin(); + if (!stop) { + stop = spillSlot; + } else if (stop == spillSlot) { + // We looked through every slot in the list. + break; + } + + bool success = true; + for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) { + LiveBundle* bundle = spillSet->spilledBundle(i); + for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveRangePlus rangePlus(range); + LiveRangePlus existingPlus; + if (spillSlot->allocated.contains(rangePlus, &existingPlus)) { + success = false; + break; + } + } + if (!success) { + break; + } + } + if (success) { + // We can reuse this physical stack slot for the new bundles. + // Update the allocated ranges for the slot. + for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) { + LiveBundle* bundle = spillSet->spilledBundle(i); + if (!insertAllRanges(spillSlot->allocated, bundle)) { + return false; + } + } + spillSet->setAllocation(spillSlot->alloc); + return true; + } + + // On a miss, move the spill to the end of the list. This will cause us + // to make fewer attempts to allocate from slots with a large and + // highly contended range. + slotList->popFront(); + slotList->pushBack(spillSlot); + + if (++searches == MAX_SEARCH_COUNT) { + break; + } + } + + // We need a new physical stack slot. + uint32_t stackSlot = stackSlotAllocator.allocateSlot(type); + + SpillSlot* spillSlot = + new (alloc().fallible()) SpillSlot(stackSlot, alloc().lifoAlloc()); + if (!spillSlot) { + return false; + } + + for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) { + LiveBundle* bundle = spillSet->spilledBundle(i); + if (!insertAllRanges(spillSlot->allocated, bundle)) { + return false; + } + } + + spillSet->setAllocation(spillSlot->alloc); + + slotList->pushFront(spillSlot); + return true; +} + +bool BacktrackingAllocator::pickStackSlots() { + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + + if (mir->shouldCancel("Backtracking Pick Stack Slots")) { + return false; + } + + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + LiveBundle* bundle = range->bundle(); + + if (bundle->allocation().isBogus()) { + if (!pickStackSlot(bundle->spillSet())) { + return false; + } + MOZ_ASSERT(!bundle->allocation().isBogus()); + } + } + } + + return true; +} + +// Helper for ::createMoveGroupsFromLiveRangeTransitions +bool BacktrackingAllocator::moveAtEdge(LBlock* predecessor, LBlock* successor, + LiveRange* from, LiveRange* to, + LDefinition::Type type) { + if (successor->mir()->numPredecessors() > 1) { + MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1); + return moveAtExit(predecessor, from, to, type); + } + + return moveAtEntry(successor, from, to, type); +} + +// Helper for ::createMoveGroupsFromLiveRangeTransitions +bool BacktrackingAllocator::deadRange(LiveRange* range) { + // Check for direct uses of this range. + if (range->hasUses() || range->hasDefinition()) { + return false; + } + + CodePosition start = range->from(); + LNode* ins = insData[start]; + if (start == entryOf(ins->block())) { + return false; + } + + VirtualRegister& reg = range->vreg(); + + // Check if there are later ranges for this vreg. + LiveRange::RegisterLinkIterator iter = reg.rangesBegin(range); + for (iter++; iter; iter++) { + LiveRange* laterRange = LiveRange::get(*iter); + if (laterRange->from() > range->from()) { + return false; + } + } + + // Check if this range ends at a loop backedge. + LNode* last = insData[range->to().previous()]; + if (last->isGoto() && + last->toGoto()->target()->id() < last->block()->mir()->id()) { + return false; + } + + // Check if there are phis which this vreg flows to. + if (reg.usedByPhi()) { + return false; + } + + return true; +} + +bool BacktrackingAllocator::createMoveGroupsFromLiveRangeTransitions() { + // Add moves to handle changing assignments for vregs over their lifetime. + JitSpew(JitSpew_RegAlloc, "ResolveControlFlow: begin"); + + JitSpew(JitSpew_RegAlloc, + " ResolveControlFlow: adding MoveGroups within blocks"); + + // Look for places where a register's assignment changes in the middle of a + // basic block. + MOZ_ASSERT(!vregs[0u].hasRanges()); + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + + if (mir->shouldCancel( + "Backtracking Resolve Control Flow (vreg outer loop)")) { + return false; + } + + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter;) { + LiveRange* range = LiveRange::get(*iter); + + if (mir->shouldCancel( + "Backtracking Resolve Control Flow (vreg inner loop)")) { + return false; + } + + // Remove ranges which will never be used. + if (deadRange(range)) { + reg.removeRangeAndIncrement(iter); + continue; + } + + // The range which defines the register does not have a predecessor + // to add moves from. + if (range->hasDefinition()) { + iter++; + continue; + } + + // Ignore ranges that start at block boundaries. We will handle + // these in the next phase. + CodePosition start = range->from(); + LNode* ins = insData[start]; + if (start == entryOf(ins->block())) { + iter++; + continue; + } + + // If we already saw a range which covers the start of this range + // and has the same allocation, we don't need an explicit move at + // the start of this range. + bool skip = false; + for (LiveRange::RegisterLinkIterator prevIter = reg.rangesBegin(); + prevIter != iter; prevIter++) { + LiveRange* prevRange = LiveRange::get(*prevIter); + if (prevRange->covers(start) && prevRange->bundle()->allocation() == + range->bundle()->allocation()) { + skip = true; + break; + } + } + if (skip) { + iter++; + continue; + } + + if (!alloc().ensureBallast()) { + return false; + } + + LiveRange* predecessorRange = + reg.rangeFor(start.previous(), /* preferRegister = */ true); + if (start.subpos() == CodePosition::INPUT) { + JitSpewIfEnabled(JitSpew_RegAlloc, " moveInput (%s) <- (%s)", + range->toString().get(), + predecessorRange->toString().get()); + if (!moveInput(ins->toInstruction(), predecessorRange, range, + reg.type())) { + return false; + } + } else { + JitSpew(JitSpew_RegAlloc, " (moveAfter)"); + if (!moveAfter(ins->toInstruction(), predecessorRange, range, + reg.type())) { + return false; + } + } + + iter++; + } + } + + JitSpew(JitSpew_RegAlloc, + " ResolveControlFlow: adding MoveGroups for phi nodes"); + + for (size_t i = 0; i < graph.numBlocks(); i++) { + if (mir->shouldCancel("Backtracking Resolve Control Flow (block loop)")) { + return false; + } + + LBlock* successor = graph.getBlock(i); + MBasicBlock* mSuccessor = successor->mir(); + if (mSuccessor->numPredecessors() < 1) { + continue; + } + + // Resolve phis to moves. + for (size_t j = 0; j < successor->numPhis(); j++) { + LPhi* phi = successor->getPhi(j); + MOZ_ASSERT(phi->numDefs() == 1); + LDefinition* def = phi->getDef(0); + VirtualRegister& reg = vreg(def); + LiveRange* to = reg.rangeFor(entryOf(successor)); + MOZ_ASSERT(to); + + for (size_t k = 0; k < mSuccessor->numPredecessors(); k++) { + LBlock* predecessor = mSuccessor->getPredecessor(k)->lir(); + MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1); + + LAllocation* input = phi->getOperand(k); + LiveRange* from = vreg(input).rangeFor(exitOf(predecessor), + /* preferRegister = */ true); + MOZ_ASSERT(from); + + if (!alloc().ensureBallast()) { + return false; + } + + // Note: we have to use moveAtEdge both here and below (for edge + // resolution) to avoid conflicting moves. See bug 1493900. + JitSpew(JitSpew_RegAlloc, " (moveAtEdge#1)"); + if (!moveAtEdge(predecessor, successor, from, to, def->type())) { + return false; + } + } + } + } + + JitSpew(JitSpew_RegAlloc, + " ResolveControlFlow: adding MoveGroups to fix conflicted edges"); + + // Add moves to resolve graph edges with different allocations at their + // source and target. + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* targetRange = LiveRange::get(*iter); + + size_t firstBlockId = insData[targetRange->from()]->block()->mir()->id(); + if (!targetRange->covers(entryOf(graph.getBlock(firstBlockId)))) { + firstBlockId++; + } + for (size_t id = firstBlockId; id < graph.numBlocks(); id++) { + LBlock* successor = graph.getBlock(id); + if (!targetRange->covers(entryOf(successor))) { + break; + } + + BitSet& live = liveIn[id]; + if (!live.contains(i)) { + continue; + } + + for (size_t j = 0; j < successor->mir()->numPredecessors(); j++) { + LBlock* predecessor = successor->mir()->getPredecessor(j)->lir(); + if (targetRange->covers(exitOf(predecessor))) { + continue; + } + + if (!alloc().ensureBallast()) { + return false; + } + JitSpew(JitSpew_RegAlloc, " (moveAtEdge#2)"); + LiveRange* from = reg.rangeFor(exitOf(predecessor), true); + if (!moveAtEdge(predecessor, successor, from, targetRange, + reg.type())) { + return false; + } + } + } + } + } + + JitSpew(JitSpew_RegAlloc, "ResolveControlFlow: end"); + return true; +} + +// Helper for ::addLiveRegistersForRange +size_t BacktrackingAllocator::findFirstNonCallSafepoint(CodePosition from) { + size_t i = 0; + for (; i < graph.numNonCallSafepoints(); i++) { + const LInstruction* ins = graph.getNonCallSafepoint(i); + if (from <= inputOf(ins)) { + break; + } + } + return i; +} + +// Helper for ::installAllocationsInLIR +void BacktrackingAllocator::addLiveRegistersForRange(VirtualRegister& reg, + LiveRange* range) { + // Fill in the live register sets for all non-call safepoints. + LAllocation a = range->bundle()->allocation(); + if (!a.isRegister()) { + return; + } + + // Don't add output registers to the safepoint. + CodePosition start = range->from(); + if (range->hasDefinition() && !reg.isTemp()) { +#ifdef CHECK_OSIPOINT_REGISTERS + // We don't add the output register to the safepoint, + // but it still might get added as one of the inputs. + // So eagerly add this reg to the safepoint clobbered registers. + if (reg.ins()->isInstruction()) { + if (LSafepoint* safepoint = reg.ins()->toInstruction()->safepoint()) { + safepoint->addClobberedRegister(a.toRegister()); + } + } +#endif + start = start.next(); + } + + size_t i = findFirstNonCallSafepoint(start); + for (; i < graph.numNonCallSafepoints(); i++) { + LInstruction* ins = graph.getNonCallSafepoint(i); + CodePosition pos = inputOf(ins); + + // Safepoints are sorted, so we can shortcut out of this loop + // if we go out of range. + if (range->to() <= pos) { + break; + } + + MOZ_ASSERT(range->covers(pos)); + + LSafepoint* safepoint = ins->safepoint(); + safepoint->addLiveRegister(a.toRegister()); + +#ifdef CHECK_OSIPOINT_REGISTERS + if (reg.isTemp()) { + safepoint->addClobberedRegister(a.toRegister()); + } +#endif + } +} + +// Helper for ::installAllocationsInLIR +static inline size_t NumReusingDefs(LInstruction* ins) { + size_t num = 0; + for (size_t i = 0; i < ins->numDefs(); i++) { + LDefinition* def = ins->getDef(i); + if (def->policy() == LDefinition::MUST_REUSE_INPUT) { + num++; + } + } + return num; +} + +bool BacktrackingAllocator::installAllocationsInLIR() { + JitSpew(JitSpew_RegAlloc, "Installing Allocations"); + + MOZ_ASSERT(!vregs[0u].hasRanges()); + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + + if (mir->shouldCancel("Backtracking Install Allocations (main loop)")) { + return false; + } + + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + if (range->hasDefinition()) { + reg.def()->setOutput(range->bundle()->allocation()); + if (reg.ins()->recoversInput()) { + LSnapshot* snapshot = reg.ins()->toInstruction()->snapshot(); + for (size_t i = 0; i < snapshot->numEntries(); i++) { + LAllocation* entry = snapshot->getEntry(i); + if (entry->isUse() && + entry->toUse()->policy() == LUse::RECOVERED_INPUT) { + *entry = *reg.def()->output(); + } + } + } + } + + for (UsePositionIterator iter(range->usesBegin()); iter; iter++) { + LAllocation* alloc = iter->use(); + *alloc = range->bundle()->allocation(); + + // For any uses which feed into MUST_REUSE_INPUT definitions, + // add copies if the use and def have different allocations. + LNode* ins = insData[iter->pos]; + if (LDefinition* def = FindReusingDefOrTemp(ins, alloc)) { + LiveRange* outputRange = vreg(def).rangeFor(outputOf(ins)); + LAllocation res = outputRange->bundle()->allocation(); + LAllocation sourceAlloc = range->bundle()->allocation(); + + if (res != *alloc) { + if (!this->alloc().ensureBallast()) { + return false; + } + if (NumReusingDefs(ins->toInstruction()) <= 1) { + LMoveGroup* group = getInputMoveGroup(ins->toInstruction()); + if (!group->addAfter(sourceAlloc, res, reg.type())) { + return false; + } + } else { + LMoveGroup* group = getFixReuseMoveGroup(ins->toInstruction()); + if (!group->add(sourceAlloc, res, reg.type())) { + return false; + } + } + *alloc = res; + } + } + } + + addLiveRegistersForRange(reg, range); + } + } + + graph.setLocalSlotsSize(stackSlotAllocator.stackHeight()); + return true; +} + +// Helper for ::populateSafepoints +size_t BacktrackingAllocator::findFirstSafepoint(CodePosition pos, + size_t startFrom) { + size_t i = startFrom; + for (; i < graph.numSafepoints(); i++) { + LInstruction* ins = graph.getSafepoint(i); + if (pos <= inputOf(ins)) { + break; + } + } + return i; +} + +// Helper for ::populateSafepoints +static inline bool IsNunbox(VirtualRegister& reg) { +#ifdef JS_NUNBOX32 + return reg.type() == LDefinition::TYPE || reg.type() == LDefinition::PAYLOAD; +#else + return false; +#endif +} + +// Helper for ::populateSafepoints +static inline bool IsSlotsOrElements(VirtualRegister& reg) { + return reg.type() == LDefinition::SLOTS; +} + +// Helper for ::populateSafepoints +static inline bool IsTraceable(VirtualRegister& reg) { + if (reg.type() == LDefinition::OBJECT) { + return true; + } +#ifdef JS_PUNBOX64 + if (reg.type() == LDefinition::BOX) { + return true; + } +#endif + if (reg.type() == LDefinition::STACKRESULTS) { + MOZ_ASSERT(reg.def()); + const LStackArea* alloc = reg.def()->output()->toStackArea(); + for (auto iter = alloc->results(); iter; iter.next()) { + if (iter.isGcPointer()) { + return true; + } + } + } + return false; +} + +bool BacktrackingAllocator::populateSafepoints() { + JitSpew(JitSpew_RegAlloc, "Populating Safepoints"); + + size_t firstSafepoint = 0; + + MOZ_ASSERT(!vregs[0u].def()); + for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + + if (!reg.def() || + (!IsTraceable(reg) && !IsSlotsOrElements(reg) && !IsNunbox(reg))) { + continue; + } + + firstSafepoint = findFirstSafepoint(inputOf(reg.ins()), firstSafepoint); + if (firstSafepoint >= graph.numSafepoints()) { + break; + } + + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + LiveRange* range = LiveRange::get(*iter); + + for (size_t j = firstSafepoint; j < graph.numSafepoints(); j++) { + LInstruction* ins = graph.getSafepoint(j); + + if (!range->covers(inputOf(ins))) { + if (inputOf(ins) >= range->to()) { + break; + } + continue; + } + + // Include temps but not instruction outputs. Also make sure + // MUST_REUSE_INPUT is not used with gcthings or nunboxes, or + // we would have to add the input reg to this safepoint. + if (ins == reg.ins() && !reg.isTemp()) { + DebugOnly<LDefinition*> def = reg.def(); + MOZ_ASSERT_IF(def->policy() == LDefinition::MUST_REUSE_INPUT, + def->type() == LDefinition::GENERAL || + def->type() == LDefinition::INT32 || + def->type() == LDefinition::FLOAT32 || + def->type() == LDefinition::DOUBLE || + def->type() == LDefinition::SIMD128); + continue; + } + + LSafepoint* safepoint = ins->safepoint(); + + LAllocation a = range->bundle()->allocation(); + if (a.isGeneralReg() && ins->isCall()) { + continue; + } + + switch (reg.type()) { + case LDefinition::OBJECT: + if (!safepoint->addGcPointer(a)) { + return false; + } + break; + case LDefinition::SLOTS: + if (!safepoint->addSlotsOrElementsPointer(a)) { + return false; + } + break; + case LDefinition::STACKRESULTS: { + MOZ_ASSERT(a.isStackArea()); + for (auto iter = a.toStackArea()->results(); iter; iter.next()) { + if (iter.isGcPointer()) { + if (!safepoint->addGcPointer(iter.alloc())) { + return false; + } + } + } + break; + } +#ifdef JS_NUNBOX32 + case LDefinition::TYPE: + if (!safepoint->addNunboxType(i, a)) { + return false; + } + break; + case LDefinition::PAYLOAD: + if (!safepoint->addNunboxPayload(i, a)) { + return false; + } + break; +#else + case LDefinition::BOX: + if (!safepoint->addBoxedValue(a)) { + return false; + } + break; +#endif + default: + MOZ_CRASH("Bad register type"); + } + } + } + } + + return true; +} + +bool BacktrackingAllocator::annotateMoveGroups() { + // Annotate move groups in the LIR graph with any register that is not + // allocated at that point and can be used as a scratch register. This is + // only required for x86, as other platforms always have scratch registers + // available for use. +#ifdef JS_CODEGEN_X86 + LiveRange* range = LiveRange::FallibleNew(alloc(), nullptr, CodePosition(), + CodePosition().next()); + if (!range) { + return false; + } + + for (size_t i = 0; i < graph.numBlocks(); i++) { + if (mir->shouldCancel("Backtracking Annotate Move Groups")) { + return false; + } + + LBlock* block = graph.getBlock(i); + LInstruction* last = nullptr; + for (LInstructionIterator iter = block->begin(); iter != block->end(); + ++iter) { + if (iter->isMoveGroup()) { + CodePosition from = last ? outputOf(last) : entryOf(block); + range->setTo(from.next()); + range->setFrom(from); + + for (size_t i = 0; i < AnyRegister::Total; i++) { + PhysicalRegister& reg = registers[i]; + if (reg.reg.isFloat() || !reg.allocatable) { + continue; + } + + // This register is unavailable for use if (a) it is in use + // by some live range immediately before the move group, + // or (b) it is an operand in one of the group's moves. The + // latter case handles live ranges which end immediately + // before the move group or start immediately after. + // For (b) we need to consider move groups immediately + // preceding or following this one. + + if (iter->toMoveGroup()->uses(reg.reg.gpr())) { + continue; + } + bool found = false; + LInstructionIterator niter(iter); + for (niter++; niter != block->end(); niter++) { + if (niter->isMoveGroup()) { + if (niter->toMoveGroup()->uses(reg.reg.gpr())) { + found = true; + break; + } + } else { + break; + } + } + if (iter != block->begin()) { + LInstructionIterator riter(iter); + do { + riter--; + if (riter->isMoveGroup()) { + if (riter->toMoveGroup()->uses(reg.reg.gpr())) { + found = true; + break; + } + } else { + break; + } + } while (riter != block->begin()); + } + + if (found) { + continue; + } + LiveRangePlus existingPlus; + LiveRangePlus rangePlus(range); + if (reg.allocations.contains(rangePlus, &existingPlus)) { + continue; + } + + iter->toMoveGroup()->setScratchRegister(reg.reg.gpr()); + break; + } + } else { + last = *iter; + } + } + } +#endif + + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +// Debug-printing support // +// // +/////////////////////////////////////////////////////////////////////////////// + +#ifdef JS_JITSPEW + +UniqueChars LiveRange::toString() const { + AutoEnterOOMUnsafeRegion oomUnsafe; + + UniqueChars buf = JS_smprintf("v%u %u-%u", hasVreg() ? vreg().vreg() : 0, + from().bits(), to().bits() - 1); + + if (buf && bundle() && !bundle()->allocation().isBogus()) { + buf = JS_sprintf_append(std::move(buf), " %s", + bundle()->allocation().toString().get()); + } + + buf = JS_sprintf_append(std::move(buf), " {"); + + if (buf && hasDefinition()) { + buf = JS_sprintf_append(std::move(buf), " %u_def", from().bits()); + if (hasVreg()) { + // If the definition has a fixed requirement, print it too. + const LDefinition* def = vreg().def(); + LDefinition::Policy policy = def->policy(); + if (policy == LDefinition::FIXED || policy == LDefinition::STACK) { + if (buf) { + buf = JS_sprintf_append(std::move(buf), ":F:%s", + def->output()->toString().get()); + } + } + } + } + + for (UsePositionIterator iter = usesBegin(); buf && iter; iter++) { + buf = JS_sprintf_append(std::move(buf), " %u_%s", iter->pos.bits(), + iter->use()->toString().get()); + } + + buf = JS_sprintf_append(std::move(buf), " }"); + + if (!buf) { + oomUnsafe.crash("LiveRange::toString()"); + } + + return buf; +} + +UniqueChars LiveBundle::toString() const { + AutoEnterOOMUnsafeRegion oomUnsafe; + + UniqueChars buf = JS_smprintf("LB%u(", debugId()); + + if (buf) { + if (spillParent()) { + buf = JS_sprintf_append(std::move(buf), "parent=LB%u", + spillParent()->debugId()); + } else { + buf = JS_sprintf_append(std::move(buf), "parent=none"); + } + } + + for (LiveRange::BundleLinkIterator iter = rangesBegin(); buf && iter; + iter++) { + if (buf) { + buf = JS_sprintf_append(std::move(buf), "%s %s", + (iter == rangesBegin()) ? "" : " ##", + LiveRange::get(*iter)->toString().get()); + } + } + + if (buf) { + buf = JS_sprintf_append(std::move(buf), ")"); + } + + if (!buf) { + oomUnsafe.crash("LiveBundle::toString()"); + } + + return buf; +} + +void BacktrackingAllocator::dumpLiveRangesByVReg(const char* who) { + MOZ_ASSERT(!vregs[0u].hasRanges()); + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Live ranges by virtual register (%s):", who); + + for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) { + JitSpewHeader(JitSpew_RegAlloc); + JitSpewCont(JitSpew_RegAlloc, " "); + VirtualRegister& reg = vregs[i]; + for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; + iter++) { + if (iter != reg.rangesBegin()) { + JitSpewCont(JitSpew_RegAlloc, " ## "); + } + JitSpewCont(JitSpew_RegAlloc, "%s", + LiveRange::get(*iter)->toString().get()); + } + JitSpewCont(JitSpew_RegAlloc, "\n"); + } +} + +void BacktrackingAllocator::dumpLiveRangesByBundle(const char* who) { + MOZ_ASSERT(!vregs[0u].hasRanges()); + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Live ranges by bundle (%s):", who); + + for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) { + VirtualRegister& reg = vregs[i]; + for (LiveRange::RegisterLinkIterator baseIter = reg.rangesBegin(); baseIter; + baseIter++) { + LiveRange* range = LiveRange::get(*baseIter); + LiveBundle* bundle = range->bundle(); + if (range == bundle->firstRange()) { + JitSpew(JitSpew_RegAlloc, " %s", bundle->toString().get()); + } + } + } +} + +void BacktrackingAllocator::dumpAllocations() { + JitSpew(JitSpew_RegAlloc, "Allocations:"); + + dumpLiveRangesByBundle("in dumpAllocations()"); + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Allocations by physical register:"); + + for (size_t i = 0; i < AnyRegister::Total; i++) { + if (registers[i].allocatable && !registers[i].allocations.empty()) { + JitSpewHeader(JitSpew_RegAlloc); + JitSpewCont(JitSpew_RegAlloc, " %s:", AnyRegister::FromCode(i).name()); + bool first = true; + LiveRangePlusSet::Iter lrpIter(®isters[i].allocations); + while (lrpIter.hasMore()) { + LiveRange* range = lrpIter.next().liveRange(); + if (first) { + first = false; + } else { + fprintf(stderr, " /"); + } + fprintf(stderr, " %s", range->toString().get()); + } + JitSpewCont(JitSpew_RegAlloc, "\n"); + } + } + + JitSpewCont(JitSpew_RegAlloc, "\n"); +} + +#endif // JS_JITSPEW + +/////////////////////////////////////////////////////////////////////////////// +// // +// Top level of the register allocation machinery // +// // +/////////////////////////////////////////////////////////////////////////////// + +bool BacktrackingAllocator::go() { + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Beginning register allocation"); + + JitSpewCont(JitSpew_RegAlloc, "\n"); + if (JitSpewEnabled(JitSpew_RegAlloc)) { + dumpInstructions("(Pre-allocation LIR)"); + } + + if (!init()) { + return false; + } + + if (!buildLivenessInfo()) { + return false; + } + +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_RegAlloc)) { + dumpLiveRangesByVReg("after liveness analysis"); + } +#endif + + if (!allocationQueue.reserve(graph.numVirtualRegisters() * 3 / 2)) { + return false; + } + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Beginning grouping and queueing registers"); + if (!mergeAndQueueRegisters()) { + return false; + } + JitSpew(JitSpew_RegAlloc, "Completed grouping and queueing registers"); + +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_RegAlloc)) { + dumpLiveRangesByBundle("after grouping/queueing regs"); + } +#endif + + // There now follow two allocation loops, which are really the heart of the + // allocator. First, the "main" allocation loop. This does almost all of + // the allocation work, by repeatedly pulling bundles out of + // ::allocationQueue and calling ::processBundle on it, until there are no + // bundles left in the queue. Note that ::processBundle can add new smaller + // bundles to the queue if it needs to split or spill a bundle. + // + // For each bundle in turn pulled out of ::allocationQueue, ::processBundle: + // + // * calls ::computeRequirement to discover the overall constraint for the + // bundle. + // + // * tries to find a register for it, by calling either ::tryAllocateFixed or + // ::tryAllocateNonFixed. + // + // * if that fails, but ::tryAllocateFixed / ::tryAllocateNonFixed indicate + // that there is some other bundle with lower spill weight that can be + // evicted, then that bundle is evicted (hence, put back into + // ::allocationQueue), and we try again. + // + // * at most MAX_ATTEMPTS may be made. + // + // * If that still fails to find a register, then the bundle is handed off to + // ::chooseBundleSplit. That will choose to either split the bundle, + // yielding multiple pieces which are put back into ::allocationQueue, or + // it will spill the bundle. Note that the same mechanism applies to both; + // there's no clear boundary between splitting and spilling, because + // spilling can be interpreted as an extreme form of splitting. + // + // ::processBundle and its callees contains much gnarly and logic which isn't + // easy to understand, particularly in the area of how eviction candidates + // are chosen. But it works well enough, and tinkering doesn't seem to + // improve the resulting allocations. More important is the splitting logic, + // because that controls where spill/reload instructions are placed. + // + // Eventually ::allocationQueue becomes empty, and each LiveBundle has either + // been allocated a register or is marked for spilling. In the latter case + // it will have been added to ::spilledBundles. + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Beginning main allocation loop"); + JitSpewCont(JitSpew_RegAlloc, "\n"); + + // Allocate, spill and split bundles until finished. + while (!allocationQueue.empty()) { + if (mir->shouldCancel("Backtracking Allocation")) { + return false; + } + + QueueItem item = allocationQueue.removeHighest(); + if (!processBundle(mir, item.bundle)) { + return false; + } + } + + // And here's the second allocation loop (hidden inside + // ::tryAllocatingRegistersForSpillBundles). It makes one last attempt to + // find a register for each spill bundle. There's no attempt to free up + // registers by eviction. In at least 99% of cases this attempt fails, in + // which case the bundle is handed off to ::spill. The lucky remaining 1% + // get a register. Unfortunately this scheme interacts badly with the + // splitting strategy, leading to excessive register-to-register copying in + // some very simple cases. See bug 1752520. + // + // A modest but probably worthwhile amount of allocation time can be saved by + // making ::tryAllocatingRegistersForSpillBundles use specialised versions of + // ::tryAllocateAnyRegister and its callees, that don't bother to create sets + // of conflicting bundles. Creating those sets is expensive and, here, + // pointless, since we're not going to do any eviction based on them. This + // refinement is implemented in the un-landed patch at bug 1758274 comment + // 15. + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, + "Main allocation loop complete; " + "beginning spill-bundle allocation loop"); + JitSpewCont(JitSpew_RegAlloc, "\n"); + + if (!tryAllocatingRegistersForSpillBundles()) { + return false; + } + + JitSpewCont(JitSpew_RegAlloc, "\n"); + JitSpew(JitSpew_RegAlloc, "Spill-bundle allocation loop complete"); + JitSpewCont(JitSpew_RegAlloc, "\n"); + + if (!pickStackSlots()) { + return false; + } + +#ifdef JS_JITSPEW + if (JitSpewEnabled(JitSpew_RegAlloc)) { + dumpAllocations(); + } +#endif + + if (!createMoveGroupsFromLiveRangeTransitions()) { + return false; + } + + if (!installAllocationsInLIR()) { + return false; + } + + if (!populateSafepoints()) { + return false; + } + + if (!annotateMoveGroups()) { + return false; + } + + JitSpewCont(JitSpew_RegAlloc, "\n"); + if (JitSpewEnabled(JitSpew_RegAlloc)) { + dumpInstructions("(Post-allocation LIR)"); + } + + JitSpew(JitSpew_RegAlloc, "Finished register allocation"); + + return true; +} + +/////////////////////////////////////////////////////////////////////////////// +// // +/////////////////////////////////////////////////////////////////////////////// |