summaryrefslogtreecommitdiffstats
path: root/js/src/jit/RegisterAllocator.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/RegisterAllocator.h')
-rw-r--r--js/src/jit/RegisterAllocator.h314
1 files changed, 314 insertions, 0 deletions
diff --git a/js/src/jit/RegisterAllocator.h b/js/src/jit/RegisterAllocator.h
new file mode 100644
index 0000000000..845ef91ce9
--- /dev/null
+++ b/js/src/jit/RegisterAllocator.h
@@ -0,0 +1,314 @@
+/* -*- 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/. */
+
+#ifndef jit_RegisterAllocator_h
+#define jit_RegisterAllocator_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;
+
+#ifdef DEBUG
+// 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.
+ [[nodiscard]] 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.
+ [[nodiscard]] bool check();
+
+ 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() = default;
+
+ 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() = default;
+ 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;
+
+ using Lookup = IntegrityItem;
+ 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;
+
+ [[nodiscard]] bool checkIntegrity(LBlock* block, LInstruction* ins,
+ uint32_t vreg, LAllocation alloc);
+ void checkSafepointAllocation(LInstruction* ins, uint32_t vreg,
+ LAllocation alloc);
+ [[nodiscard]] bool addPredecessor(LBlock* block, uint32_t vreg,
+ LAllocation alloc);
+
+ void dump();
+};
+#endif // DEBUG
+
+// 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_() {}
+
+ [[nodiscard]] 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()) {
+ MOZ_ASSERT(!allRegisters_.has(FramePointer));
+ if (mir->compilingWasm()) {
+ takeWasmRegisters(allRegisters_);
+ }
+ }
+
+ [[nodiscard]] 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);
+
+ // Atomic group helper. See comments in BacktrackingAllocator.cpp.
+ CodePosition minimalDefEnd(LNode* ins) const;
+
+ void dumpInstructions(const char* who);
+
+ public:
+ template <typename TakeableSet>
+ static void takeWasmRegisters(TakeableSet& regs) {
+#if defined(JS_CODEGEN_X64) || defined(JS_CODEGEN_ARM) || \
+ defined(JS_CODEGEN_ARM64) || defined(JS_CODEGEN_MIPS32) || \
+ defined(JS_CODEGEN_MIPS64) || defined(JS_CODEGEN_LOONG64) || \
+ defined(JS_CODEGEN_RISCV64)
+ regs.take(HeapReg);
+#endif
+ MOZ_ASSERT(!regs.has(FramePointer));
+ }
+};
+
+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 */