michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- michael@0: * vim: set ts=8 sts=4 et sw=4 tw=99: michael@0: * This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: #ifndef jit_RegisterAllocator_h michael@0: #define jit_RegisterAllocator_h michael@0: michael@0: #include "mozilla/Attributes.h" michael@0: #include "mozilla/MathAlgorithms.h" michael@0: michael@0: #include "jit/LIR.h" michael@0: #include "jit/MIRGenerator.h" michael@0: #include "jit/MIRGraph.h" michael@0: michael@0: // Generic structures and functions for use by register allocators. michael@0: michael@0: namespace js { michael@0: namespace jit { michael@0: michael@0: class LIRGenerator; michael@0: michael@0: // Structure for running a liveness analysis on a finished register allocation. michael@0: // This analysis can be used for two purposes: michael@0: // michael@0: // - Check the integrity of the allocation, i.e. that the reads and writes of michael@0: // physical values preserve the semantics of the original virtual registers. michael@0: // michael@0: // - Populate safepoints with live registers, GC thing and value data, to michael@0: // streamline the process of prototyping new allocators. michael@0: struct AllocationIntegrityState michael@0: { michael@0: explicit AllocationIntegrityState(const LIRGraph &graph) michael@0: : graph(graph) michael@0: {} michael@0: michael@0: // Record all virtual registers in the graph. This must be called before michael@0: // register allocation, to pick up the original LUses. michael@0: bool record(); michael@0: michael@0: // Perform the liveness analysis on the graph, and assert on an invalid michael@0: // allocation. This must be called after register allocation, to pick up michael@0: // all assigned physical values. If populateSafepoints is specified, michael@0: // safepoints will be filled in with liveness information. michael@0: bool check(bool populateSafepoints); michael@0: michael@0: private: michael@0: michael@0: const LIRGraph &graph; michael@0: michael@0: // For all instructions and phis in the graph, keep track of the virtual michael@0: // registers for all inputs and outputs of the nodes. These are overwritten michael@0: // in place during register allocation. This information is kept on the michael@0: // side rather than in the instructions and phis themselves to avoid michael@0: // debug-builds-only bloat in the size of the involved structures. michael@0: michael@0: struct InstructionInfo { michael@0: Vector inputs; michael@0: Vector temps; michael@0: Vector outputs; michael@0: michael@0: InstructionInfo() michael@0: { } michael@0: michael@0: InstructionInfo(const InstructionInfo &o) michael@0: { michael@0: inputs.appendAll(o.inputs); michael@0: temps.appendAll(o.temps); michael@0: outputs.appendAll(o.outputs); michael@0: } michael@0: }; michael@0: Vector instructions; michael@0: michael@0: struct BlockInfo { michael@0: Vector phis; michael@0: BlockInfo() {} michael@0: BlockInfo(const BlockInfo &o) { michael@0: phis.appendAll(o.phis); michael@0: } michael@0: }; michael@0: Vector blocks; michael@0: michael@0: Vector virtualRegisters; michael@0: michael@0: // Describes a correspondence that should hold at the end of a block. michael@0: // The value which was written to vreg in the original LIR should be michael@0: // physically stored in alloc after the register allocation. michael@0: struct IntegrityItem michael@0: { michael@0: LBlock *block; michael@0: uint32_t vreg; michael@0: LAllocation alloc; michael@0: michael@0: // Order of insertion into seen, for sorting. michael@0: uint32_t index; michael@0: michael@0: typedef IntegrityItem Lookup; michael@0: static HashNumber hash(const IntegrityItem &item) { michael@0: HashNumber hash = item.alloc.hash(); michael@0: hash = mozilla::RotateLeft(hash, 4) ^ item.vreg; michael@0: hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id()); michael@0: return hash; michael@0: } michael@0: static bool match(const IntegrityItem &one, const IntegrityItem &two) { michael@0: return one.block == two.block michael@0: && one.vreg == two.vreg michael@0: && one.alloc == two.alloc; michael@0: } michael@0: }; michael@0: michael@0: // Items still to be processed. michael@0: Vector worklist; michael@0: michael@0: // Set of all items that have already been processed. michael@0: typedef HashSet IntegrityItemSet; michael@0: IntegrityItemSet seen; michael@0: michael@0: bool checkIntegrity(LBlock *block, LInstruction *ins, uint32_t vreg, LAllocation alloc, michael@0: bool populateSafepoints); michael@0: bool checkSafepointAllocation(LInstruction *ins, uint32_t vreg, LAllocation alloc, michael@0: bool populateSafepoints); michael@0: bool addPredecessor(LBlock *block, uint32_t vreg, LAllocation alloc); michael@0: michael@0: void dump(); michael@0: }; michael@0: michael@0: // Represents with better-than-instruction precision a position in the michael@0: // instruction stream. michael@0: // michael@0: // An issue comes up when performing register allocation as to how to represent michael@0: // information such as "this register is only needed for the input of michael@0: // this instruction, it can be clobbered in the output". Just having ranges michael@0: // of instruction IDs is insufficiently expressive to denote all possibilities. michael@0: // This class solves this issue by associating an extra bit with the instruction michael@0: // ID which indicates whether the position is the input half or output half of michael@0: // an instruction. michael@0: class CodePosition michael@0: { michael@0: private: michael@0: MOZ_CONSTEXPR CodePosition(const uint32_t &bits) michael@0: : bits_(bits) michael@0: { } michael@0: michael@0: static const unsigned int INSTRUCTION_SHIFT = 1; michael@0: static const unsigned int SUBPOSITION_MASK = 1; michael@0: uint32_t bits_; michael@0: michael@0: public: michael@0: static const CodePosition MAX; michael@0: static const CodePosition MIN; michael@0: michael@0: // This is the half of the instruction this code position represents, as michael@0: // described in the huge comment above. michael@0: enum SubPosition { michael@0: INPUT, michael@0: OUTPUT michael@0: }; michael@0: michael@0: MOZ_CONSTEXPR CodePosition() : bits_(0) michael@0: { } michael@0: michael@0: CodePosition(uint32_t instruction, SubPosition where) { michael@0: JS_ASSERT(instruction < 0x80000000u); michael@0: JS_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where); michael@0: bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where; michael@0: } michael@0: michael@0: uint32_t ins() const { michael@0: return bits_ >> INSTRUCTION_SHIFT; michael@0: } michael@0: michael@0: uint32_t pos() const { michael@0: return bits_; michael@0: } michael@0: michael@0: SubPosition subpos() const { michael@0: return (SubPosition)(bits_ & SUBPOSITION_MASK); michael@0: } michael@0: michael@0: bool operator <(const CodePosition &other) const { michael@0: return bits_ < other.bits_; michael@0: } michael@0: michael@0: bool operator <=(const CodePosition &other) const { michael@0: return bits_ <= other.bits_; michael@0: } michael@0: michael@0: bool operator !=(const CodePosition &other) const { michael@0: return bits_ != other.bits_; michael@0: } michael@0: michael@0: bool operator ==(const CodePosition &other) const { michael@0: return bits_ == other.bits_; michael@0: } michael@0: michael@0: bool operator >(const CodePosition &other) const { michael@0: return bits_ > other.bits_; michael@0: } michael@0: michael@0: bool operator >=(const CodePosition &other) const { michael@0: return bits_ >= other.bits_; michael@0: } michael@0: michael@0: CodePosition previous() const { michael@0: JS_ASSERT(*this != MIN); michael@0: return CodePosition(bits_ - 1); michael@0: } michael@0: CodePosition next() const { michael@0: JS_ASSERT(*this != MAX); michael@0: return CodePosition(bits_ + 1); michael@0: } michael@0: }; michael@0: michael@0: // Structure to track moves inserted before or after an instruction. michael@0: class InstructionData michael@0: { michael@0: LInstruction *ins_; michael@0: LBlock *block_; michael@0: LMoveGroup *inputMoves_; michael@0: LMoveGroup *movesAfter_; michael@0: michael@0: public: michael@0: void init(LInstruction *ins, LBlock *block) { michael@0: JS_ASSERT(!ins_); michael@0: JS_ASSERT(!block_); michael@0: ins_ = ins; michael@0: block_ = block; michael@0: } michael@0: LInstruction *ins() const { michael@0: return ins_; michael@0: } michael@0: LBlock *block() const { michael@0: return block_; michael@0: } michael@0: void setInputMoves(LMoveGroup *moves) { michael@0: inputMoves_ = moves; michael@0: } michael@0: LMoveGroup *inputMoves() const { michael@0: return inputMoves_; michael@0: } michael@0: void setMovesAfter(LMoveGroup *moves) { michael@0: movesAfter_ = moves; michael@0: } michael@0: LMoveGroup *movesAfter() const { michael@0: return movesAfter_; michael@0: } michael@0: }; michael@0: michael@0: // Structure to track all moves inserted next to instructions in a graph. michael@0: class InstructionDataMap michael@0: { michael@0: InstructionData *insData_; michael@0: uint32_t numIns_; michael@0: michael@0: public: michael@0: InstructionDataMap() michael@0: : insData_(nullptr), michael@0: numIns_(0) michael@0: { } michael@0: michael@0: bool init(MIRGenerator *gen, uint32_t numInstructions) { michael@0: insData_ = gen->allocate(numInstructions); michael@0: numIns_ = numInstructions; michael@0: if (!insData_) michael@0: return false; michael@0: memset(insData_, 0, sizeof(InstructionData) * numInstructions); michael@0: return true; michael@0: } michael@0: michael@0: InstructionData &operator[](const CodePosition &pos) { michael@0: JS_ASSERT(pos.ins() < numIns_); michael@0: return insData_[pos.ins()]; michael@0: } michael@0: InstructionData &operator[](LInstruction *ins) { michael@0: JS_ASSERT(ins->id() < numIns_); michael@0: return insData_[ins->id()]; michael@0: } michael@0: InstructionData &operator[](uint32_t ins) { michael@0: JS_ASSERT(ins < numIns_); michael@0: return insData_[ins]; michael@0: } michael@0: }; michael@0: michael@0: // Common superclass for register allocators. michael@0: class RegisterAllocator michael@0: { michael@0: void operator=(const RegisterAllocator &) MOZ_DELETE; michael@0: RegisterAllocator(const RegisterAllocator &) MOZ_DELETE; michael@0: michael@0: protected: michael@0: // Context michael@0: MIRGenerator *mir; michael@0: LIRGenerator *lir; michael@0: LIRGraph &graph; michael@0: michael@0: // Pool of all registers that should be considered allocateable michael@0: RegisterSet allRegisters_; michael@0: michael@0: // Computed data michael@0: InstructionDataMap insData; michael@0: michael@0: RegisterAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph) michael@0: : mir(mir), michael@0: lir(lir), michael@0: graph(graph), michael@0: allRegisters_(RegisterSet::All()) michael@0: { michael@0: if (FramePointer != InvalidReg && mir->instrumentedProfiling()) michael@0: allRegisters_.take(AnyRegister(FramePointer)); michael@0: #if defined(JS_CODEGEN_X64) michael@0: if (mir->compilingAsmJS()) michael@0: allRegisters_.take(AnyRegister(HeapReg)); michael@0: #elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS) michael@0: if (mir->compilingAsmJS()) { michael@0: allRegisters_.take(AnyRegister(HeapReg)); michael@0: allRegisters_.take(AnyRegister(GlobalReg)); michael@0: allRegisters_.take(AnyRegister(NANReg)); michael@0: } michael@0: #endif michael@0: } michael@0: michael@0: bool init(); michael@0: michael@0: TempAllocator &alloc() const { michael@0: return mir->alloc(); michael@0: } michael@0: michael@0: static CodePosition outputOf(uint32_t pos) { michael@0: return CodePosition(pos, CodePosition::OUTPUT); michael@0: } michael@0: static CodePosition outputOf(const LInstruction *ins) { michael@0: return CodePosition(ins->id(), CodePosition::OUTPUT); michael@0: } michael@0: static CodePosition inputOf(uint32_t pos) { michael@0: return CodePosition(pos, CodePosition::INPUT); michael@0: } michael@0: static CodePosition inputOf(const LInstruction *ins) { michael@0: // Phi nodes "use" their inputs before the beginning of the block. michael@0: JS_ASSERT(!ins->isPhi()); michael@0: return CodePosition(ins->id(), CodePosition::INPUT); michael@0: } michael@0: michael@0: LMoveGroup *getInputMoveGroup(uint32_t ins); michael@0: LMoveGroup *getMoveGroupAfter(uint32_t ins); michael@0: michael@0: LMoveGroup *getInputMoveGroup(CodePosition pos) { michael@0: return getInputMoveGroup(pos.ins()); michael@0: } michael@0: LMoveGroup *getMoveGroupAfter(CodePosition pos) { michael@0: return getMoveGroupAfter(pos.ins()); michael@0: } michael@0: michael@0: CodePosition minimalDefEnd(LInstruction *ins) { michael@0: // Compute the shortest interval that captures vregs defined by ins. michael@0: // Watch for instructions that are followed by an OSI point and/or Nop. michael@0: // If moves are introduced between the instruction and the OSI point then michael@0: // safepoint information for the instruction may be incorrect. michael@0: while (true) { michael@0: LInstruction *next = insData[outputOf(ins).next()].ins(); michael@0: if (!next->isNop() && !next->isOsiPoint()) michael@0: break; michael@0: ins = next; michael@0: } michael@0: michael@0: return outputOf(ins); michael@0: } michael@0: }; michael@0: michael@0: static inline AnyRegister michael@0: GetFixedRegister(const LDefinition *def, const LUse *use) michael@0: { michael@0: return def->isFloatReg() michael@0: ? AnyRegister(FloatRegister::FromCode(use->registerCode())) michael@0: : AnyRegister(Register::FromCode(use->registerCode())); michael@0: } michael@0: michael@0: } // namespace jit michael@0: } // namespace js michael@0: michael@0: #endif /* jit_RegisterAllocator_h */