summaryrefslogtreecommitdiffstats
path: root/js/src/jit/RegisterAllocator.h
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /js/src/jit/RegisterAllocator.h
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'js/src/jit/RegisterAllocator.h')
-rw-r--r--js/src/jit/RegisterAllocator.h375
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 */