diff -r 000000000000 -r 6474c204b198 js/src/jit/RegisterAllocator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/RegisterAllocator.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,381 @@ +/* -*- 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(const LIRGraph &graph) + : graph(graph) + {} + + // Record all virtual registers in the graph. This must be called before + // register allocation, to pick up the original LUses. + 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. + bool check(bool populateSafepoints); + + private: + + const 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 inputs; + Vector temps; + Vector outputs; + + InstructionInfo() + { } + + InstructionInfo(const InstructionInfo &o) + { + inputs.appendAll(o.inputs); + temps.appendAll(o.temps); + outputs.appendAll(o.outputs); + } + }; + Vector instructions; + + struct BlockInfo { + Vector phis; + BlockInfo() {} + BlockInfo(const BlockInfo &o) { + phis.appendAll(o.phis); + } + }; + Vector blocks; + + Vector 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 worklist; + + // Set of all items that have already been processed. + typedef HashSet IntegrityItemSet; + IntegrityItemSet seen; + + bool checkIntegrity(LBlock *block, LInstruction *ins, uint32_t vreg, LAllocation alloc, + bool populateSafepoints); + bool checkSafepointAllocation(LInstruction *ins, uint32_t vreg, LAllocation alloc, + bool populateSafepoints); + 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: + MOZ_CONSTEXPR CodePosition(const 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 + }; + + MOZ_CONSTEXPR CodePosition() : bits_(0) + { } + + CodePosition(uint32_t instruction, SubPosition where) { + JS_ASSERT(instruction < 0x80000000u); + JS_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 pos() const { + return bits_; + } + + SubPosition subpos() const { + return (SubPosition)(bits_ & SUBPOSITION_MASK); + } + + bool operator <(const CodePosition &other) const { + return bits_ < other.bits_; + } + + bool operator <=(const CodePosition &other) const { + return bits_ <= other.bits_; + } + + bool operator !=(const CodePosition &other) const { + return bits_ != other.bits_; + } + + bool operator ==(const CodePosition &other) const { + return bits_ == other.bits_; + } + + bool operator >(const CodePosition &other) const { + return bits_ > other.bits_; + } + + bool operator >=(const CodePosition &other) const { + return bits_ >= other.bits_; + } + + CodePosition previous() const { + JS_ASSERT(*this != MIN); + return CodePosition(bits_ - 1); + } + CodePosition next() const { + JS_ASSERT(*this != MAX); + return CodePosition(bits_ + 1); + } +}; + +// Structure to track moves inserted before or after an instruction. +class InstructionData +{ + LInstruction *ins_; + LBlock *block_; + LMoveGroup *inputMoves_; + LMoveGroup *movesAfter_; + + public: + void init(LInstruction *ins, LBlock *block) { + JS_ASSERT(!ins_); + JS_ASSERT(!block_); + ins_ = ins; + block_ = block; + } + LInstruction *ins() const { + return ins_; + } + LBlock *block() const { + return block_; + } + void setInputMoves(LMoveGroup *moves) { + inputMoves_ = moves; + } + LMoveGroup *inputMoves() const { + return inputMoves_; + } + void setMovesAfter(LMoveGroup *moves) { + movesAfter_ = moves; + } + LMoveGroup *movesAfter() const { + return movesAfter_; + } +}; + +// Structure to track all moves inserted next to instructions in a graph. +class InstructionDataMap +{ + InstructionData *insData_; + uint32_t numIns_; + + public: + InstructionDataMap() + : insData_(nullptr), + numIns_(0) + { } + + bool init(MIRGenerator *gen, uint32_t numInstructions) { + insData_ = gen->allocate(numInstructions); + numIns_ = numInstructions; + if (!insData_) + return false; + memset(insData_, 0, sizeof(InstructionData) * numInstructions); + return true; + } + + InstructionData &operator[](const CodePosition &pos) { + JS_ASSERT(pos.ins() < numIns_); + return insData_[pos.ins()]; + } + InstructionData &operator[](LInstruction *ins) { + JS_ASSERT(ins->id() < numIns_); + return insData_[ins->id()]; + } + InstructionData &operator[](uint32_t ins) { + JS_ASSERT(ins < numIns_); + return insData_[ins]; + } +}; + +// Common superclass for register allocators. +class RegisterAllocator +{ + void operator=(const RegisterAllocator &) MOZ_DELETE; + RegisterAllocator(const RegisterAllocator &) MOZ_DELETE; + + protected: + // Context + MIRGenerator *mir; + LIRGenerator *lir; + LIRGraph &graph; + + // Pool of all registers that should be considered allocateable + RegisterSet allRegisters_; + + // Computed data + InstructionDataMap insData; + + RegisterAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph) + : mir(mir), + lir(lir), + graph(graph), + allRegisters_(RegisterSet::All()) + { + if (FramePointer != InvalidReg && mir->instrumentedProfiling()) + allRegisters_.take(AnyRegister(FramePointer)); +#if defined(JS_CODEGEN_X64) + if (mir->compilingAsmJS()) + allRegisters_.take(AnyRegister(HeapReg)); +#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS) + if (mir->compilingAsmJS()) { + allRegisters_.take(AnyRegister(HeapReg)); + allRegisters_.take(AnyRegister(GlobalReg)); + allRegisters_.take(AnyRegister(NANReg)); + } +#endif + } + + bool init(); + + TempAllocator &alloc() const { + return mir->alloc(); + } + + static CodePosition outputOf(uint32_t pos) { + return CodePosition(pos, CodePosition::OUTPUT); + } + static CodePosition outputOf(const LInstruction *ins) { + return CodePosition(ins->id(), CodePosition::OUTPUT); + } + static CodePosition inputOf(uint32_t pos) { + return CodePosition(pos, CodePosition::INPUT); + } + static CodePosition inputOf(const LInstruction *ins) { + // Phi nodes "use" their inputs before the beginning of the block. + JS_ASSERT(!ins->isPhi()); + return CodePosition(ins->id(), CodePosition::INPUT); + } + + LMoveGroup *getInputMoveGroup(uint32_t ins); + LMoveGroup *getMoveGroupAfter(uint32_t ins); + + LMoveGroup *getInputMoveGroup(CodePosition pos) { + return getInputMoveGroup(pos.ins()); + } + LMoveGroup *getMoveGroupAfter(CodePosition pos) { + return getMoveGroupAfter(pos.ins()); + } + + CodePosition minimalDefEnd(LInstruction *ins) { + // Compute the shortest interval that captures vregs defined by ins. + // Watch for instructions that are followed by an OSI point and/or Nop. + // If moves are introduced between the instruction and the OSI point then + // safepoint information for the instruction may be incorrect. + while (true) { + LInstruction *next = insData[outputOf(ins).next()].ins(); + if (!next->isNop() && !next->isOsiPoint()) + break; + ins = next; + } + + return outputOf(ins); + } +}; + +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 */