Add m-esr52 at 52.6.0

1 files changed, 375 insertions, 0 deletions

diff --git a/js/src/jit/RegisterAllocator.h b/js/src/jit/RegisterAllocator.h
new file mode 100644
index 000000000..4ff16d523
--- /dev/null
+++ b/js/src/jit/RegisterAllocator.h
@@ -0,0 +1,375 @@
+/* -*- 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_RegisterAllocator_h
+#define jit_RegisterAllocator_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include "jit/LIR.h"
+#include "jit/MIRGenerator.h"
+#include "jit/MIRGraph.h"
+
+// Generic structures and functions for use by register allocators.
+
+namespace js {
+namespace jit {
+
+class LIRGenerator;
+
+// Structure for running a liveness analysis on a finished register allocation.
+// This analysis can be used for two purposes:
+//
+// - Check the integrity of the allocation, i.e. that the reads and writes of
+//   physical values preserve the semantics of the original virtual registers.
+//
+// - Populate safepoints with live registers, GC thing and value data, to
+//   streamline the process of prototyping new allocators.
+struct AllocationIntegrityState
+{
+    explicit AllocationIntegrityState(LIRGraph& graph)
+      : graph(graph)
+    {}
+
+    // Record all virtual registers in the graph. This must be called before
+    // register allocation, to pick up the original LUses.
+    MOZ_MUST_USE bool record();
+
+    // Perform the liveness analysis on the graph, and assert on an invalid
+    // allocation. This must be called after register allocation, to pick up
+    // all assigned physical values. If populateSafepoints is specified,
+    // safepoints will be filled in with liveness information.
+    MOZ_MUST_USE bool check(bool populateSafepoints);
+
+  private:
+
+    LIRGraph& graph;
+
+    // For all instructions and phis in the graph, keep track of the virtual
+    // registers for all inputs and outputs of the nodes. These are overwritten
+    // in place during register allocation. This information is kept on the
+    // side rather than in the instructions and phis themselves to avoid
+    // debug-builds-only bloat in the size of the involved structures.
+
+    struct InstructionInfo {
+        Vector<LAllocation, 2, SystemAllocPolicy> inputs;
+        Vector<LDefinition, 0, SystemAllocPolicy> temps;
+        Vector<LDefinition, 1, SystemAllocPolicy> outputs;
+
+        InstructionInfo()
+        { }
+
+        InstructionInfo(const InstructionInfo& o)
+        {
+            AutoEnterOOMUnsafeRegion oomUnsafe;
+            if (!inputs.appendAll(o.inputs) ||
+                !temps.appendAll(o.temps) ||
+                !outputs.appendAll(o.outputs))
+            {
+                oomUnsafe.crash("InstructionInfo::InstructionInfo");
+            }
+        }
+    };
+    Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
+
+    struct BlockInfo {
+        Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
+        BlockInfo() {}
+        BlockInfo(const BlockInfo& o) {
+            AutoEnterOOMUnsafeRegion oomUnsafe;
+            if (!phis.appendAll(o.phis))
+                oomUnsafe.crash("BlockInfo::BlockInfo");
+        }
+    };
+    Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
+
+    Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
+
+    // Describes a correspondence that should hold at the end of a block.
+    // The value which was written to vreg in the original LIR should be
+    // physically stored in alloc after the register allocation.
+    struct IntegrityItem
+    {
+        LBlock* block;
+        uint32_t vreg;
+        LAllocation alloc;
+
+        // Order of insertion into seen, for sorting.
+        uint32_t index;
+
+        typedef IntegrityItem Lookup;
+        static HashNumber hash(const IntegrityItem& item) {
+            HashNumber hash = item.alloc.hash();
+            hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
+            hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
+            return hash;
+        }
+        static bool match(const IntegrityItem& one, const IntegrityItem& two) {
+            return one.block == two.block
+                && one.vreg == two.vreg
+                && one.alloc == two.alloc;
+        }
+    };
+
+    // Items still to be processed.
+    Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
+
+    // Set of all items that have already been processed.
+    typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
+    IntegrityItemSet seen;
+
+    MOZ_MUST_USE bool checkIntegrity(LBlock* block, LInstruction* ins, uint32_t vreg,
+                                     LAllocation alloc, bool populateSafepoints);
+    MOZ_MUST_USE bool checkSafepointAllocation(LInstruction* ins, uint32_t vreg, LAllocation alloc,
+                                               bool populateSafepoints);
+    MOZ_MUST_USE bool addPredecessor(LBlock* block, uint32_t vreg, LAllocation alloc);
+
+    void dump();
+};
+
+// Represents with better-than-instruction precision a position in the
+// instruction stream.
+//
+// An issue comes up when performing register allocation as to how to represent
+// information such as "this register is only needed for the input of
+// this instruction, it can be clobbered in the output". Just having ranges
+// of instruction IDs is insufficiently expressive to denote all possibilities.
+// This class solves this issue by associating an extra bit with the instruction
+// ID which indicates whether the position is the input half or output half of
+// an instruction.
+class CodePosition
+{
+  private:
+    constexpr explicit CodePosition(uint32_t bits)
+      : bits_(bits)
+    { }
+
+    static const unsigned int INSTRUCTION_SHIFT = 1;
+    static const unsigned int SUBPOSITION_MASK = 1;
+    uint32_t bits_;
+
+  public:
+    static const CodePosition MAX;
+    static const CodePosition MIN;
+
+    // This is the half of the instruction this code position represents, as
+    // described in the huge comment above.
+    enum SubPosition {
+        INPUT,
+        OUTPUT
+    };
+
+    constexpr CodePosition() : bits_(0)
+    { }
+
+    CodePosition(uint32_t instruction, SubPosition where) {
+        MOZ_ASSERT(instruction < 0x80000000u);
+        MOZ_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
+        bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
+    }
+
+    uint32_t ins() const {
+        return bits_ >> INSTRUCTION_SHIFT;
+    }
+
+    uint32_t bits() const {
+        return bits_;
+    }
+
+    SubPosition subpos() const {
+        return (SubPosition)(bits_ & SUBPOSITION_MASK);
+    }
+
+    bool operator <(CodePosition other) const {
+        return bits_ < other.bits_;
+    }
+
+    bool operator <=(CodePosition other) const {
+        return bits_ <= other.bits_;
+    }
+
+    bool operator !=(CodePosition other) const {
+        return bits_ != other.bits_;
+    }
+
+    bool operator ==(CodePosition other) const {
+        return bits_ == other.bits_;
+    }
+
+    bool operator >(CodePosition other) const {
+        return bits_ > other.bits_;
+    }
+
+    bool operator >=(CodePosition other) const {
+        return bits_ >= other.bits_;
+    }
+
+    uint32_t operator -(CodePosition other) const {
+        MOZ_ASSERT(bits_ >= other.bits_);
+        return bits_ - other.bits_;
+    }
+
+    CodePosition previous() const {
+        MOZ_ASSERT(*this != MIN);
+        return CodePosition(bits_ - 1);
+    }
+    CodePosition next() const {
+        MOZ_ASSERT(*this != MAX);
+        return CodePosition(bits_ + 1);
+    }
+};
+
+// Structure to track all moves inserted next to instructions in a graph.
+class InstructionDataMap
+{
+    FixedList<LNode*> insData_;
+
+  public:
+    InstructionDataMap()
+      : insData_()
+    { }
+
+    MOZ_MUST_USE bool init(MIRGenerator* gen, uint32_t numInstructions) {
+        if (!insData_.init(gen->alloc(), numInstructions))
+            return false;
+        memset(&insData_[0], 0, sizeof(LNode*) * numInstructions);
+        return true;
+    }
+
+    LNode*& operator[](CodePosition pos) {
+        return operator[](pos.ins());
+    }
+    LNode* const& operator[](CodePosition pos) const {
+        return operator[](pos.ins());
+    }
+    LNode*& operator[](uint32_t ins) {
+        return insData_[ins];
+    }
+    LNode* const& operator[](uint32_t ins) const {
+        return insData_[ins];
+    }
+};
+
+// Common superclass for register allocators.
+class RegisterAllocator
+{
+    void operator=(const RegisterAllocator&) = delete;
+    RegisterAllocator(const RegisterAllocator&) = delete;
+
+  protected:
+    // Context
+    MIRGenerator* mir;
+    LIRGenerator* lir;
+    LIRGraph& graph;
+
+    // Pool of all registers that should be considered allocateable
+    AllocatableRegisterSet allRegisters_;
+
+    // Computed data
+    InstructionDataMap insData;
+    Vector<CodePosition, 12, SystemAllocPolicy> entryPositions;
+    Vector<CodePosition, 12, SystemAllocPolicy> exitPositions;
+
+    RegisterAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
+      : mir(mir),
+        lir(lir),
+        graph(graph),
+        allRegisters_(RegisterSet::All())
+    {
+        if (mir->compilingWasm()) {
+#if defined(JS_CODEGEN_X64)
+            allRegisters_.take(AnyRegister(HeapReg));
+#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64)
+            allRegisters_.take(AnyRegister(HeapReg));
+            allRegisters_.take(AnyRegister(GlobalReg));
+#elif defined(JS_CODEGEN_ARM64)
+            allRegisters_.take(AnyRegister(HeapReg));
+            allRegisters_.take(AnyRegister(HeapLenReg));
+            allRegisters_.take(AnyRegister(GlobalReg));
+#endif
+        } else {
+            if (FramePointer != InvalidReg && mir->instrumentedProfiling())
+                allRegisters_.take(AnyRegister(FramePointer));
+        }
+    }
+
+    MOZ_MUST_USE bool init();
+
+    TempAllocator& alloc() const {
+        return mir->alloc();
+    }
+
+    CodePosition outputOf(const LNode* ins) const {
+        return ins->isPhi()
+               ? outputOf(ins->toPhi())
+               : outputOf(ins->toInstruction());
+    }
+    CodePosition outputOf(const LPhi* ins) const {
+        // All phis in a block write their outputs after all of them have
+        // read their inputs. Consequently, it doesn't make sense to talk
+        // about code positions in the middle of a series of phis.
+        LBlock* block = ins->block();
+        return CodePosition(block->getPhi(block->numPhis() - 1)->id(), CodePosition::OUTPUT);
+    }
+    CodePosition outputOf(const LInstruction* ins) const {
+        return CodePosition(ins->id(), CodePosition::OUTPUT);
+    }
+    CodePosition inputOf(const LNode* ins) const {
+        return ins->isPhi()
+               ? inputOf(ins->toPhi())
+               : inputOf(ins->toInstruction());
+    }
+    CodePosition inputOf(const LPhi* ins) const {
+        // All phis in a block read their inputs before any of them write their
+        // outputs. Consequently, it doesn't make sense to talk about code
+        // positions in the middle of a series of phis.
+        return CodePosition(ins->block()->getPhi(0)->id(), CodePosition::INPUT);
+    }
+    CodePosition inputOf(const LInstruction* ins) const {
+        return CodePosition(ins->id(), CodePosition::INPUT);
+    }
+    CodePosition entryOf(const LBlock* block) {
+        return entryPositions[block->mir()->id()];
+    }
+    CodePosition exitOf(const LBlock* block) {
+        return exitPositions[block->mir()->id()];
+    }
+
+    LMoveGroup* getInputMoveGroup(LInstruction* ins);
+    LMoveGroup* getFixReuseMoveGroup(LInstruction* ins);
+    LMoveGroup* getMoveGroupAfter(LInstruction* ins);
+
+    CodePosition minimalDefEnd(LNode* ins) {
+        // 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);
+    }
+
+    void dumpInstructions();
+};
+
+static inline AnyRegister
+GetFixedRegister(const LDefinition* def, const LUse* use)
+{
+    return def->isFloatReg()
+           ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
+           : AnyRegister(Register::FromCode(use->registerCode()));
+}
+
+} // namespace jit
+} // namespace js
+
+#endif /* jit_RegisterAllocator_h */