Add m-esr52 at 52.6.0

1 files changed, 816 insertions, 0 deletions

diff --git a/js/src/jit/BacktrackingAllocator.h b/js/src/jit/BacktrackingAllocator.h
new file mode 100644
index 000000000..6d14ffacd
--- /dev/null
+++ b/js/src/jit/BacktrackingAllocator.h
@@ -0,0 +1,816 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * 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/. */
+
+#ifndef jit_BacktrackingAllocator_h
+#define jit_BacktrackingAllocator_h
+
+#include "mozilla/Array.h"
+
+#include "ds/PriorityQueue.h"
+#include "ds/SplayTree.h"
+#include "jit/RegisterAllocator.h"
+#include "jit/StackSlotAllocator.h"
+
+// Backtracking priority queue based register allocator based on that described
+// in the following blog post:
+//
+// http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
+
+namespace js {
+namespace jit {
+
+class Requirement
+{
+  public:
+    enum Kind {
+        NONE,
+        REGISTER,
+        FIXED,
+        MUST_REUSE_INPUT
+    };
+
+    Requirement()
+      : kind_(NONE)
+    { }
+
+    explicit Requirement(Kind kind)
+      : kind_(kind)
+    {
+        // These have dedicated constructors.
+        MOZ_ASSERT(kind != FIXED && kind != MUST_REUSE_INPUT);
+    }
+
+    Requirement(Kind kind, CodePosition at)
+      : kind_(kind),
+        position_(at)
+    {
+        // These have dedicated constructors.
+        MOZ_ASSERT(kind != FIXED && kind != MUST_REUSE_INPUT);
+    }
+
+    explicit Requirement(LAllocation fixed)
+      : kind_(FIXED),
+        allocation_(fixed)
+    {
+        MOZ_ASSERT(!fixed.isBogus() && !fixed.isUse());
+    }
+
+    // Only useful as a hint, encodes where the fixed requirement is used to
+    // avoid allocating a fixed register too early.
+    Requirement(LAllocation fixed, CodePosition at)
+      : kind_(FIXED),
+        allocation_(fixed),
+        position_(at)
+    {
+        MOZ_ASSERT(!fixed.isBogus() && !fixed.isUse());
+    }
+
+    Requirement(uint32_t vreg, CodePosition at)
+      : kind_(MUST_REUSE_INPUT),
+        allocation_(LUse(vreg, LUse::ANY)),
+        position_(at)
+    { }
+
+    Kind kind() const {
+        return kind_;
+    }
+
+    LAllocation allocation() const {
+        MOZ_ASSERT(!allocation_.isBogus() && !allocation_.isUse());
+        return allocation_;
+    }
+
+    uint32_t virtualRegister() const {
+        MOZ_ASSERT(allocation_.isUse());
+        MOZ_ASSERT(kind() == MUST_REUSE_INPUT);
+        return allocation_.toUse()->virtualRegister();
+    }
+
+    CodePosition pos() const {
+        return position_;
+    }
+
+    int priority() const;
+
+    MOZ_MUST_USE bool merge(const Requirement& newRequirement) {
+        // Merge newRequirement with any existing requirement, returning false
+        // if the new and old requirements conflict.
+        MOZ_ASSERT(newRequirement.kind() != Requirement::MUST_REUSE_INPUT);
+
+        if (newRequirement.kind() == Requirement::FIXED) {
+            if (kind() == Requirement::FIXED)
+                return newRequirement.allocation() == allocation();
+            *this = newRequirement;
+            return true;
+        }
+
+        MOZ_ASSERT(newRequirement.kind() == Requirement::REGISTER);
+        if (kind() == Requirement::FIXED)
+            return allocation().isRegister();
+
+        *this = newRequirement;
+        return true;
+    }
+
+    void dump() const;
+
+  private:
+    Kind kind_;
+    LAllocation allocation_;
+    CodePosition position_;
+};
+
+struct UsePosition : public TempObject,
+                     public InlineForwardListNode<UsePosition>
+{
+  private:
+    // Packed LUse* with a copy of the LUse::Policy value, in order to avoid
+    // making cache misses while reaching out to the policy value.
+    uintptr_t use_;
+
+    void setUse(LUse* use) {
+        // Assert that we can safely pack the LUse policy in the last 2 bits of
+        // the LUse pointer.
+        static_assert((LUse::ANY | LUse::REGISTER | LUse::FIXED | LUse::KEEPALIVE) <= 0x3,
+                      "Cannot pack the LUse::Policy value on 32 bits architectures.");
+
+        // RECOVERED_INPUT is used by snapshots and ignored when building the
+        // liveness information. Thus we can safely assume that no such value
+        // would be seen.
+        MOZ_ASSERT(use->policy() != LUse::RECOVERED_INPUT);
+        use_ = uintptr_t(use) | (use->policy() & 0x3);
+    }
+
+  public:
+    CodePosition pos;
+
+    LUse* use() const {
+        return reinterpret_cast<LUse*>(use_ & ~0x3);
+    }
+
+    LUse::Policy usePolicy() const {
+        LUse::Policy policy = LUse::Policy(use_ & 0x3);
+        MOZ_ASSERT(use()->policy() == policy);
+        return policy;
+    }
+
+    UsePosition(LUse* use, CodePosition pos) :
+        pos(pos)
+    {
+        // Verify that the usedAtStart() flag is consistent with the
+        // subposition. For now ignore fixed registers, because they
+        // are handled specially around calls.
+        MOZ_ASSERT_IF(!use->isFixedRegister(),
+                      pos.subpos() == (use->usedAtStart()
+                                       ? CodePosition::INPUT
+                                       : CodePosition::OUTPUT));
+        setUse(use);
+    }
+};
+
+typedef InlineForwardListIterator<UsePosition> UsePositionIterator;
+
+// Backtracking allocator data structures overview.
+//
+// LiveRange: A continuous range of positions where a virtual register is live.
+// LiveBundle: A set of LiveRanges which do not overlap.
+// VirtualRegister: A set of all LiveRanges used for some LDefinition.
+//
+// The allocator first performs a liveness ananlysis on the LIR graph which
+// constructs LiveRanges for each VirtualRegister, determining where the
+// registers are live.
+//
+// The ranges are then bundled together according to heuristics, and placed on
+// the allocation queue.
+//
+// As bundles are removed from the allocation queue, we attempt to find a
+// physical register or stack slot allocation for all ranges in the removed
+// bundle, possibly evicting already-allocated bundles. See processBundle()
+// for details.
+//
+// If we are not able to allocate a bundle, it is split according to heuristics
+// into two or more smaller bundles which cover all the ranges of the original.
+// These smaller bundles are then allocated independently.
+
+class LiveBundle;
+
+class LiveRange : public TempObject
+{
+  public:
+    // Linked lists are used to keep track of the ranges in each LiveBundle and
+    // VirtualRegister. Since a LiveRange may be in two lists simultaneously, use
+    // these auxiliary classes to keep things straight.
+    class BundleLink : public InlineForwardListNode<BundleLink> {};
+    class RegisterLink : public InlineForwardListNode<RegisterLink> {};
+
+    typedef InlineForwardListIterator<BundleLink> BundleLinkIterator;
+    typedef InlineForwardListIterator<RegisterLink> RegisterLinkIterator;
+
+    // Links in the lists in LiveBundle and VirtualRegister.
+    BundleLink bundleLink;
+    RegisterLink registerLink;
+
+    static LiveRange* get(BundleLink* link) {
+        return reinterpret_cast<LiveRange*>(reinterpret_cast<uint8_t*>(link) -
+                                            offsetof(LiveRange, bundleLink));
+    }
+    static LiveRange* get(RegisterLink* link) {
+        return reinterpret_cast<LiveRange*>(reinterpret_cast<uint8_t*>(link) -
+                                            offsetof(LiveRange, registerLink));
+    }
+
+    struct Range
+    {
+        // The beginning of this range, inclusive.
+        CodePosition from;
+
+        // The end of this range, exclusive.
+        CodePosition to;
+
+        Range() {}
+
+        Range(CodePosition from, CodePosition to)
+          : from(from), to(to)
+        {
+            MOZ_ASSERT(!empty());
+        }
+
+        bool empty() {
+            MOZ_ASSERT(from <= to);
+            return from == to;
+        }
+    };
+
+  private:
+    // The virtual register this range is for, or zero if this does not have a
+    // virtual register (for example, it is in the callRanges bundle).
+    uint32_t vreg_;
+
+    // The bundle containing this range, null if liveness information is being
+    // constructed and we haven't started allocating bundles yet.
+    LiveBundle* bundle_;
+
+    // The code positions in this range.
+    Range range_;
+
+    // All uses of the virtual register in this range, ordered by location.
+    InlineForwardList<UsePosition> uses_;
+
+    // Whether this range contains the virtual register's definition.
+    bool hasDefinition_;
+
+    LiveRange(uint32_t vreg, Range range)
+      : vreg_(vreg), bundle_(nullptr), range_(range), hasDefinition_(false)
+    {
+        MOZ_ASSERT(!range.empty());
+    }
+
+  public:
+    static LiveRange* FallibleNew(TempAllocator& alloc, uint32_t vreg,
+                                  CodePosition from, CodePosition to)
+    {
+        return new(alloc.fallible()) LiveRange(vreg, Range(from, to));
+    }
+
+    uint32_t vreg() const {
+        MOZ_ASSERT(hasVreg());
+        return vreg_;
+    }
+    bool hasVreg() const {
+        return vreg_ != 0;
+    }
+
+    LiveBundle* bundle() const {
+        return bundle_;
+    }
+
+    CodePosition from() const {
+        return range_.from;
+    }
+    CodePosition to() const {
+        return range_.to;
+    }
+    bool covers(CodePosition pos) const {
+        return pos >= from() && pos < to();
+    }
+
+    // Whether this range wholly contains other.
+    bool contains(LiveRange* other) const;
+
+    // Intersect this range with other, returning the subranges of this
+    // that are before, inside, or after other.
+    void intersect(LiveRange* other, Range* pre, Range* inside, Range* post) const;
+
+    // Whether this range has any intersection with other.
+    bool intersects(LiveRange* other) const;
+
+    UsePositionIterator usesBegin() const {
+        return uses_.begin();
+    }
+    UsePosition* lastUse() const {
+        return uses_.back();
+    }
+    bool hasUses() const {
+        return !!usesBegin();
+    }
+    UsePosition* popUse() {
+        return uses_.popFront();
+    }
+
+    bool hasDefinition() const {
+        return hasDefinition_;
+    }
+
+    void setFrom(CodePosition from) {
+        range_.from = from;
+        MOZ_ASSERT(!range_.empty());
+    }
+    void setTo(CodePosition to) {
+        range_.to = to;
+        MOZ_ASSERT(!range_.empty());
+    }
+
+    void setBundle(LiveBundle* bundle) {
+        bundle_ = bundle;
+    }
+
+    void addUse(UsePosition* use);
+    void distributeUses(LiveRange* other);
+
+    void setHasDefinition() {
+        MOZ_ASSERT(!hasDefinition_);
+        hasDefinition_ = true;
+    }
+
+#ifdef JS_JITSPEW
+    // Return a string describing this range.
+    UniqueChars toString() const;
+#endif
+
+    // Comparator for use in range splay trees.
+    static int compare(LiveRange* v0, LiveRange* v1) {
+        // LiveRange includes 'from' but excludes 'to'.
+        if (v0->to() <= v1->from())
+            return -1;
+        if (v0->from() >= v1->to())
+            return 1;
+        return 0;
+    }
+};
+
+// Tracks information about bundles that should all be spilled to the same
+// physical location. At the beginning of allocation, each bundle has its own
+// spill set. As bundles are split, the new smaller bundles continue to use the
+// same spill set.
+class SpillSet : public TempObject
+{
+    // All bundles with this spill set which have been spilled. All bundles in
+    // this list will be given the same physical slot.
+    Vector<LiveBundle*, 1, JitAllocPolicy> list_;
+
+    explicit SpillSet(TempAllocator& alloc)
+      : list_(alloc)
+    { }
+
+  public:
+    static SpillSet* New(TempAllocator& alloc) {
+        return new(alloc) SpillSet(alloc);
+    }
+
+    MOZ_MUST_USE bool addSpilledBundle(LiveBundle* bundle) {
+        return list_.append(bundle);
+    }
+    size_t numSpilledBundles() const {
+        return list_.length();
+    }
+    LiveBundle* spilledBundle(size_t i) const {
+        return list_[i];
+    }
+
+    void setAllocation(LAllocation alloc);
+};
+
+// A set of live ranges which are all pairwise disjoint. The register allocator
+// attempts to find allocations for an entire bundle, and if it fails the
+// bundle will be broken into smaller ones which are allocated independently.
+class LiveBundle : public TempObject
+{
+    // Set to use if this bundle or one it is split into is spilled.
+    SpillSet* spill_;
+
+    // All the ranges in this set, ordered by location.
+    InlineForwardList<LiveRange::BundleLink> ranges_;
+
+    // Allocation to use for ranges in this set, bogus if unallocated or spilled
+    // and not yet given a physical stack slot.
+    LAllocation alloc_;
+
+    // Bundle which entirely contains this one and has no register uses. This
+    // may or may not be spilled by the allocator, but it can be spilled and
+    // will not be split.
+    LiveBundle* spillParent_;
+
+    LiveBundle(SpillSet* spill, LiveBundle* spillParent)
+      : spill_(spill), spillParent_(spillParent)
+    { }
+
+  public:
+    static LiveBundle* FallibleNew(TempAllocator& alloc, SpillSet* spill, LiveBundle* spillParent)
+    {
+        return new(alloc.fallible()) LiveBundle(spill, spillParent);
+    }
+
+    SpillSet* spillSet() const {
+        return spill_;
+    }
+    void setSpillSet(SpillSet* spill) {
+        spill_ = spill;
+    }
+
+    LiveRange::BundleLinkIterator rangesBegin() const {
+        return ranges_.begin();
+    }
+    bool hasRanges() const {
+        return !!rangesBegin();
+    }
+    LiveRange* firstRange() const {
+        return LiveRange::get(*rangesBegin());
+    }
+    LiveRange* lastRange() const {
+        return LiveRange::get(ranges_.back());
+    }
+    LiveRange* rangeFor(CodePosition pos) const;
+    void removeRange(LiveRange* range);
+    void removeRangeAndIncrementIterator(LiveRange::BundleLinkIterator& iter) {
+        ranges_.removeAndIncrement(iter);
+    }
+    void addRange(LiveRange* range);
+    MOZ_MUST_USE bool addRange(TempAllocator& alloc, uint32_t vreg,
+                               CodePosition from, CodePosition to);
+    MOZ_MUST_USE bool addRangeAndDistributeUses(TempAllocator& alloc, LiveRange* oldRange,
+                                                CodePosition from, CodePosition to);
+    LiveRange* popFirstRange();
+#ifdef DEBUG
+    size_t numRanges() const;
+#endif
+
+    LAllocation allocation() const {
+        return alloc_;
+    }
+    void setAllocation(LAllocation alloc) {
+        alloc_ = alloc;
+    }
+
+    LiveBundle* spillParent() const {
+        return spillParent_;
+    }
+
+#ifdef JS_JITSPEW
+    // Return a string describing this bundle.
+    UniqueChars toString() const;
+#endif
+};
+
+// Information about the allocation for a virtual register.
+class VirtualRegister
+{
+    // Instruction which defines this register.
+    LNode* ins_;
+
+    // Definition in the instruction for this register.
+    LDefinition* def_;
+
+    // All live ranges for this register. These may overlap each other, and are
+    // ordered by their start position.
+    InlineForwardList<LiveRange::RegisterLink> ranges_;
+
+    // Whether def_ is a temp or an output.
+    bool isTemp_;
+
+    // Whether this vreg is an input for some phi. This use is not reflected in
+    // any range on the vreg.
+    bool usedByPhi_;
+
+    // If this register's definition is MUST_REUSE_INPUT, whether a copy must
+    // be introduced before the definition that relaxes the policy.
+    bool mustCopyInput_;
+
+    void operator=(const VirtualRegister&) = delete;
+    VirtualRegister(const VirtualRegister&) = delete;
+
+  public:
+    explicit VirtualRegister()
+    {
+        // Note: This class is zeroed before it is constructed.
+    }
+
+    void init(LNode* ins, LDefinition* def, bool isTemp) {
+        MOZ_ASSERT(!ins_);
+        ins_ = ins;
+        def_ = def;
+        isTemp_ = isTemp;
+    }
+
+    LNode* ins() const {
+        return ins_;
+    }
+    LDefinition* def() const {
+        return def_;
+    }
+    LDefinition::Type type() const {
+        return def()->type();
+    }
+    uint32_t vreg() const {
+        return def()->virtualRegister();
+    }
+    bool isCompatible(const AnyRegister& r) const {
+        return def_->isCompatibleReg(r);
+    }
+    bool isCompatible(const VirtualRegister& vr) const {
+        return def_->isCompatibleDef(*vr.def_);
+    }
+    bool isTemp() const {
+        return isTemp_;
+    }
+
+    void setUsedByPhi() {
+        usedByPhi_ = true;
+    }
+    bool usedByPhi() {
+        return usedByPhi_;
+    }
+
+    void setMustCopyInput() {
+        mustCopyInput_ = true;
+    }
+    bool mustCopyInput() {
+        return mustCopyInput_;
+    }
+
+    LiveRange::RegisterLinkIterator rangesBegin() const {
+        return ranges_.begin();
+    }
+    LiveRange::RegisterLinkIterator rangesBegin(LiveRange* range) const {
+        return ranges_.begin(&range->registerLink);
+    }
+    bool hasRanges() const {
+        return !!rangesBegin();
+    }
+    LiveRange* firstRange() const {
+        return LiveRange::get(*rangesBegin());
+    }
+    LiveRange* lastRange() const {
+        return LiveRange::get(ranges_.back());
+    }
+    LiveRange* rangeFor(CodePosition pos, bool preferRegister = false) const;
+    void removeRange(LiveRange* range);
+    void addRange(LiveRange* range);
+
+    void removeRangeAndIncrement(LiveRange::RegisterLinkIterator& iter) {
+        ranges_.removeAndIncrement(iter);
+    }
+
+    LiveBundle* firstBundle() const {
+        return firstRange()->bundle();
+    }
+
+    MOZ_MUST_USE bool addInitialRange(TempAllocator& alloc, CodePosition from, CodePosition to);
+    void addInitialUse(UsePosition* use);
+    void setInitialDefinition(CodePosition from);
+};
+
+// A sequence of code positions, for tellings BacktrackingAllocator::splitAt
+// where to split.
+typedef js::Vector<CodePosition, 4, SystemAllocPolicy> SplitPositionVector;
+
+class BacktrackingAllocator : protected RegisterAllocator
+{
+    friend class C1Spewer;
+    friend class JSONSpewer;
+
+    // This flag is set when testing new allocator modifications.
+    bool testbed;
+
+    BitSet* liveIn;
+    FixedList<VirtualRegister> vregs;
+
+    // Allocation state.
+    StackSlotAllocator stackSlotAllocator;
+
+    // Priority queue element: a bundle and the associated priority.
+    struct QueueItem
+    {
+        LiveBundle* bundle;
+
+        QueueItem(LiveBundle* bundle, size_t priority)
+          : bundle(bundle), priority_(priority)
+        {}
+
+        static size_t priority(const QueueItem& v) {
+            return v.priority_;
+        }
+
+      private:
+        size_t priority_;
+    };
+
+    PriorityQueue<QueueItem, QueueItem, 0, SystemAllocPolicy> allocationQueue;
+
+    typedef SplayTree<LiveRange*, LiveRange> LiveRangeSet;
+
+    // Each physical register is associated with the set of ranges over which
+    // that register is currently allocated.
+    struct PhysicalRegister {
+        bool allocatable;
+        AnyRegister reg;
+        LiveRangeSet allocations;
+
+        PhysicalRegister() : allocatable(false) {}
+    };
+    mozilla::Array<PhysicalRegister, AnyRegister::Total> registers;
+
+    // Ranges of code which are considered to be hot, for which good allocation
+    // should be prioritized.
+    LiveRangeSet hotcode;
+
+    struct CallRange : public TempObject, public InlineListNode<CallRange> {
+        LiveRange::Range range;
+
+        CallRange(CodePosition from, CodePosition to)
+          : range(from, to)
+        {}
+
+        // Comparator for use in splay tree.
+        static int compare(CallRange* v0, CallRange* v1) {
+            if (v0->range.to <= v1->range.from)
+                return -1;
+            if (v0->range.from >= v1->range.to)
+                return 1;
+            return 0;
+        }
+    };
+
+    // Ranges where all registers must be spilled due to call instructions.
+    typedef InlineList<CallRange> CallRangeList;
+    CallRangeList callRangesList;
+    SplayTree<CallRange*, CallRange> callRanges;
+
+    // Information about an allocated stack slot.
+    struct SpillSlot : public TempObject, public InlineForwardListNode<SpillSlot> {
+        LStackSlot alloc;
+        LiveRangeSet allocated;
+
+        SpillSlot(uint32_t slot, LifoAlloc* alloc)
+          : alloc(slot), allocated(alloc)
+        {}
+    };
+    typedef InlineForwardList<SpillSlot> SpillSlotList;
+
+    // All allocated slots of each width.
+    SpillSlotList normalSlots, doubleSlots, quadSlots;
+
+  public:
+    BacktrackingAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph, bool testbed)
+      : RegisterAllocator(mir, lir, graph),
+        testbed(testbed),
+        liveIn(nullptr),
+        callRanges(nullptr)
+    { }
+
+    MOZ_MUST_USE bool go();
+
+  private:
+
+    typedef Vector<LiveRange*, 4, SystemAllocPolicy> LiveRangeVector;
+    typedef Vector<LiveBundle*, 4, SystemAllocPolicy> LiveBundleVector;
+
+    // Liveness methods.
+    MOZ_MUST_USE bool init();
+    MOZ_MUST_USE bool buildLivenessInfo();
+
+    MOZ_MUST_USE bool addInitialFixedRange(AnyRegister reg, CodePosition from, CodePosition to);
+
+    VirtualRegister& vreg(const LDefinition* def) {
+        return vregs[def->virtualRegister()];
+    }
+    VirtualRegister& vreg(const LAllocation* alloc) {
+        MOZ_ASSERT(alloc->isUse());
+        return vregs[alloc->toUse()->virtualRegister()];
+    }
+
+    // Allocation methods.
+    MOZ_MUST_USE bool tryMergeBundles(LiveBundle* bundle0, LiveBundle* bundle1);
+    MOZ_MUST_USE bool tryMergeReusedRegister(VirtualRegister& def, VirtualRegister& input);
+    MOZ_MUST_USE bool mergeAndQueueRegisters();
+    MOZ_MUST_USE bool tryAllocateFixed(LiveBundle* bundle, Requirement requirement,
+                                       bool* success, bool* pfixed, LiveBundleVector& conflicting);
+    MOZ_MUST_USE bool tryAllocateNonFixed(LiveBundle* bundle, Requirement requirement,
+                                          Requirement hint, bool* success, bool* pfixed,
+                                          LiveBundleVector& conflicting);
+    MOZ_MUST_USE bool processBundle(MIRGenerator* mir, LiveBundle* bundle);
+    MOZ_MUST_USE bool computeRequirement(LiveBundle* bundle, Requirement *prequirement,
+                                         Requirement *phint);
+    MOZ_MUST_USE bool tryAllocateRegister(PhysicalRegister& r, LiveBundle* bundle, bool* success,
+                                          bool* pfixed, LiveBundleVector& conflicting);
+    MOZ_MUST_USE bool evictBundle(LiveBundle* bundle);
+    MOZ_MUST_USE bool splitAndRequeueBundles(LiveBundle* bundle,
+                                             const LiveBundleVector& newBundles);
+    MOZ_MUST_USE bool spill(LiveBundle* bundle);
+
+    bool isReusedInput(LUse* use, LNode* ins, bool considerCopy);
+    bool isRegisterUse(UsePosition* use, LNode* ins, bool considerCopy = false);
+    bool isRegisterDefinition(LiveRange* range);
+    MOZ_MUST_USE bool pickStackSlot(SpillSet* spill);
+    MOZ_MUST_USE bool insertAllRanges(LiveRangeSet& set, LiveBundle* bundle);
+
+    // Reification methods.
+    MOZ_MUST_USE bool pickStackSlots();
+    MOZ_MUST_USE bool resolveControlFlow();
+    MOZ_MUST_USE bool reifyAllocations();
+    MOZ_MUST_USE bool populateSafepoints();
+    MOZ_MUST_USE bool annotateMoveGroups();
+    MOZ_MUST_USE bool deadRange(LiveRange* range);
+    size_t findFirstNonCallSafepoint(CodePosition from);
+    size_t findFirstSafepoint(CodePosition pos, size_t startFrom);
+    void addLiveRegistersForRange(VirtualRegister& reg, LiveRange* range);
+
+    MOZ_MUST_USE bool addMove(LMoveGroup* moves, LiveRange* from, LiveRange* to,
+                              LDefinition::Type type) {
+        LAllocation fromAlloc = from->bundle()->allocation();
+        LAllocation toAlloc = to->bundle()->allocation();
+        MOZ_ASSERT(fromAlloc != toAlloc);
+        return moves->add(fromAlloc, toAlloc, type);
+    }
+
+    MOZ_MUST_USE bool moveInput(LInstruction* ins, LiveRange* from, LiveRange* to,
+                                LDefinition::Type type) {
+        if (from->bundle()->allocation() == to->bundle()->allocation())
+            return true;
+        LMoveGroup* moves = getInputMoveGroup(ins);
+        return addMove(moves, from, to, type);
+    }
+
+    MOZ_MUST_USE bool moveAfter(LInstruction* ins, LiveRange* from, LiveRange* to,
+                                LDefinition::Type type) {
+        if (from->bundle()->allocation() == to->bundle()->allocation())
+            return true;
+        LMoveGroup* moves = getMoveGroupAfter(ins);
+        return addMove(moves, from, to, type);
+    }
+
+    MOZ_MUST_USE bool moveAtExit(LBlock* block, LiveRange* from, LiveRange* to,
+                                 LDefinition::Type type) {
+        if (from->bundle()->allocation() == to->bundle()->allocation())
+            return true;
+        LMoveGroup* moves = block->getExitMoveGroup(alloc());
+        return addMove(moves, from, to, type);
+    }
+
+    MOZ_MUST_USE bool moveAtEntry(LBlock* block, LiveRange* from, LiveRange* to,
+                                  LDefinition::Type type) {
+        if (from->bundle()->allocation() == to->bundle()->allocation())
+            return true;
+        LMoveGroup* moves = block->getEntryMoveGroup(alloc());
+        return addMove(moves, from, to, type);
+    }
+
+    // Debugging methods.
+    void dumpAllocations();
+
+    struct PrintLiveRange;
+
+    bool minimalDef(LiveRange* range, LNode* ins);
+    bool minimalUse(LiveRange* range, UsePosition* use);
+    bool minimalBundle(LiveBundle* bundle, bool* pfixed = nullptr);
+
+    // Heuristic methods.
+
+    size_t computePriority(LiveBundle* bundle);
+    size_t computeSpillWeight(LiveBundle* bundle);
+
+    size_t maximumSpillWeight(const LiveBundleVector& bundles);
+
+    MOZ_MUST_USE bool chooseBundleSplit(LiveBundle* bundle, bool fixed, LiveBundle* conflict);
+
+    MOZ_MUST_USE bool splitAt(LiveBundle* bundle, const SplitPositionVector& splitPositions);
+    MOZ_MUST_USE bool trySplitAcrossHotcode(LiveBundle* bundle, bool* success);
+    MOZ_MUST_USE bool trySplitAfterLastRegisterUse(LiveBundle* bundle, LiveBundle* conflict,
+                                                   bool* success);
+    MOZ_MUST_USE bool trySplitBeforeFirstRegisterUse(LiveBundle* bundle, LiveBundle* conflict,
+                                                     bool* success);
+    MOZ_MUST_USE bool splitAcrossCalls(LiveBundle* bundle);
+
+    bool compilingWasm() {
+        return mir->info().compilingWasm();
+    }
+
+    void dumpVregs();
+};
+
+} // namespace jit
+} // namespace js
+
+#endif /* jit_BacktrackingAllocator_h */