diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /js/src/jit/RegisterAllocator.h | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'js/src/jit/RegisterAllocator.h')
-rw-r--r-- | js/src/jit/RegisterAllocator.h | 314 |
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..805bc7e77d --- /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() {} + + [[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 */ |