diff options
Diffstat (limited to 'js/src/jit/RegisterAllocator.h')
| -rw-r--r-- | js/src/jit/RegisterAllocator.h | 375 |
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 */ |