1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/RegisterAllocator.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,381 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jit_RegisterAllocator_h
1.11 +#define jit_RegisterAllocator_h
1.12 +
1.13 +#include "mozilla/Attributes.h"
1.14 +#include "mozilla/MathAlgorithms.h"
1.15 +
1.16 +#include "jit/LIR.h"
1.17 +#include "jit/MIRGenerator.h"
1.18 +#include "jit/MIRGraph.h"
1.19 +
1.20 +// Generic structures and functions for use by register allocators.
1.21 +
1.22 +namespace js {
1.23 +namespace jit {
1.24 +
1.25 +class LIRGenerator;
1.26 +
1.27 +// Structure for running a liveness analysis on a finished register allocation.
1.28 +// This analysis can be used for two purposes:
1.29 +//
1.30 +// - Check the integrity of the allocation, i.e. that the reads and writes of
1.31 +// physical values preserve the semantics of the original virtual registers.
1.32 +//
1.33 +// - Populate safepoints with live registers, GC thing and value data, to
1.34 +// streamline the process of prototyping new allocators.
1.35 +struct AllocationIntegrityState
1.36 +{
1.37 + explicit AllocationIntegrityState(const LIRGraph &graph)
1.38 + : graph(graph)
1.39 + {}
1.40 +
1.41 + // Record all virtual registers in the graph. This must be called before
1.42 + // register allocation, to pick up the original LUses.
1.43 + bool record();
1.44 +
1.45 + // Perform the liveness analysis on the graph, and assert on an invalid
1.46 + // allocation. This must be called after register allocation, to pick up
1.47 + // all assigned physical values. If populateSafepoints is specified,
1.48 + // safepoints will be filled in with liveness information.
1.49 + bool check(bool populateSafepoints);
1.50 +
1.51 + private:
1.52 +
1.53 + const LIRGraph &graph;
1.54 +
1.55 + // For all instructions and phis in the graph, keep track of the virtual
1.56 + // registers for all inputs and outputs of the nodes. These are overwritten
1.57 + // in place during register allocation. This information is kept on the
1.58 + // side rather than in the instructions and phis themselves to avoid
1.59 + // debug-builds-only bloat in the size of the involved structures.
1.60 +
1.61 + struct InstructionInfo {
1.62 + Vector<LAllocation, 2, SystemAllocPolicy> inputs;
1.63 + Vector<LDefinition, 0, SystemAllocPolicy> temps;
1.64 + Vector<LDefinition, 1, SystemAllocPolicy> outputs;
1.65 +
1.66 + InstructionInfo()
1.67 + { }
1.68 +
1.69 + InstructionInfo(const InstructionInfo &o)
1.70 + {
1.71 + inputs.appendAll(o.inputs);
1.72 + temps.appendAll(o.temps);
1.73 + outputs.appendAll(o.outputs);
1.74 + }
1.75 + };
1.76 + Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
1.77 +
1.78 + struct BlockInfo {
1.79 + Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
1.80 + BlockInfo() {}
1.81 + BlockInfo(const BlockInfo &o) {
1.82 + phis.appendAll(o.phis);
1.83 + }
1.84 + };
1.85 + Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
1.86 +
1.87 + Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
1.88 +
1.89 + // Describes a correspondence that should hold at the end of a block.
1.90 + // The value which was written to vreg in the original LIR should be
1.91 + // physically stored in alloc after the register allocation.
1.92 + struct IntegrityItem
1.93 + {
1.94 + LBlock *block;
1.95 + uint32_t vreg;
1.96 + LAllocation alloc;
1.97 +
1.98 + // Order of insertion into seen, for sorting.
1.99 + uint32_t index;
1.100 +
1.101 + typedef IntegrityItem Lookup;
1.102 + static HashNumber hash(const IntegrityItem &item) {
1.103 + HashNumber hash = item.alloc.hash();
1.104 + hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
1.105 + hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
1.106 + return hash;
1.107 + }
1.108 + static bool match(const IntegrityItem &one, const IntegrityItem &two) {
1.109 + return one.block == two.block
1.110 + && one.vreg == two.vreg
1.111 + && one.alloc == two.alloc;
1.112 + }
1.113 + };
1.114 +
1.115 + // Items still to be processed.
1.116 + Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
1.117 +
1.118 + // Set of all items that have already been processed.
1.119 + typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
1.120 + IntegrityItemSet seen;
1.121 +
1.122 + bool checkIntegrity(LBlock *block, LInstruction *ins, uint32_t vreg, LAllocation alloc,
1.123 + bool populateSafepoints);
1.124 + bool checkSafepointAllocation(LInstruction *ins, uint32_t vreg, LAllocation alloc,
1.125 + bool populateSafepoints);
1.126 + bool addPredecessor(LBlock *block, uint32_t vreg, LAllocation alloc);
1.127 +
1.128 + void dump();
1.129 +};
1.130 +
1.131 +// Represents with better-than-instruction precision a position in the
1.132 +// instruction stream.
1.133 +//
1.134 +// An issue comes up when performing register allocation as to how to represent
1.135 +// information such as "this register is only needed for the input of
1.136 +// this instruction, it can be clobbered in the output". Just having ranges
1.137 +// of instruction IDs is insufficiently expressive to denote all possibilities.
1.138 +// This class solves this issue by associating an extra bit with the instruction
1.139 +// ID which indicates whether the position is the input half or output half of
1.140 +// an instruction.
1.141 +class CodePosition
1.142 +{
1.143 + private:
1.144 + MOZ_CONSTEXPR CodePosition(const uint32_t &bits)
1.145 + : bits_(bits)
1.146 + { }
1.147 +
1.148 + static const unsigned int INSTRUCTION_SHIFT = 1;
1.149 + static const unsigned int SUBPOSITION_MASK = 1;
1.150 + uint32_t bits_;
1.151 +
1.152 + public:
1.153 + static const CodePosition MAX;
1.154 + static const CodePosition MIN;
1.155 +
1.156 + // This is the half of the instruction this code position represents, as
1.157 + // described in the huge comment above.
1.158 + enum SubPosition {
1.159 + INPUT,
1.160 + OUTPUT
1.161 + };
1.162 +
1.163 + MOZ_CONSTEXPR CodePosition() : bits_(0)
1.164 + { }
1.165 +
1.166 + CodePosition(uint32_t instruction, SubPosition where) {
1.167 + JS_ASSERT(instruction < 0x80000000u);
1.168 + JS_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
1.169 + bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
1.170 + }
1.171 +
1.172 + uint32_t ins() const {
1.173 + return bits_ >> INSTRUCTION_SHIFT;
1.174 + }
1.175 +
1.176 + uint32_t pos() const {
1.177 + return bits_;
1.178 + }
1.179 +
1.180 + SubPosition subpos() const {
1.181 + return (SubPosition)(bits_ & SUBPOSITION_MASK);
1.182 + }
1.183 +
1.184 + bool operator <(const CodePosition &other) const {
1.185 + return bits_ < other.bits_;
1.186 + }
1.187 +
1.188 + bool operator <=(const CodePosition &other) const {
1.189 + return bits_ <= other.bits_;
1.190 + }
1.191 +
1.192 + bool operator !=(const CodePosition &other) const {
1.193 + return bits_ != other.bits_;
1.194 + }
1.195 +
1.196 + bool operator ==(const CodePosition &other) const {
1.197 + return bits_ == other.bits_;
1.198 + }
1.199 +
1.200 + bool operator >(const CodePosition &other) const {
1.201 + return bits_ > other.bits_;
1.202 + }
1.203 +
1.204 + bool operator >=(const CodePosition &other) const {
1.205 + return bits_ >= other.bits_;
1.206 + }
1.207 +
1.208 + CodePosition previous() const {
1.209 + JS_ASSERT(*this != MIN);
1.210 + return CodePosition(bits_ - 1);
1.211 + }
1.212 + CodePosition next() const {
1.213 + JS_ASSERT(*this != MAX);
1.214 + return CodePosition(bits_ + 1);
1.215 + }
1.216 +};
1.217 +
1.218 +// Structure to track moves inserted before or after an instruction.
1.219 +class InstructionData
1.220 +{
1.221 + LInstruction *ins_;
1.222 + LBlock *block_;
1.223 + LMoveGroup *inputMoves_;
1.224 + LMoveGroup *movesAfter_;
1.225 +
1.226 + public:
1.227 + void init(LInstruction *ins, LBlock *block) {
1.228 + JS_ASSERT(!ins_);
1.229 + JS_ASSERT(!block_);
1.230 + ins_ = ins;
1.231 + block_ = block;
1.232 + }
1.233 + LInstruction *ins() const {
1.234 + return ins_;
1.235 + }
1.236 + LBlock *block() const {
1.237 + return block_;
1.238 + }
1.239 + void setInputMoves(LMoveGroup *moves) {
1.240 + inputMoves_ = moves;
1.241 + }
1.242 + LMoveGroup *inputMoves() const {
1.243 + return inputMoves_;
1.244 + }
1.245 + void setMovesAfter(LMoveGroup *moves) {
1.246 + movesAfter_ = moves;
1.247 + }
1.248 + LMoveGroup *movesAfter() const {
1.249 + return movesAfter_;
1.250 + }
1.251 +};
1.252 +
1.253 +// Structure to track all moves inserted next to instructions in a graph.
1.254 +class InstructionDataMap
1.255 +{
1.256 + InstructionData *insData_;
1.257 + uint32_t numIns_;
1.258 +
1.259 + public:
1.260 + InstructionDataMap()
1.261 + : insData_(nullptr),
1.262 + numIns_(0)
1.263 + { }
1.264 +
1.265 + bool init(MIRGenerator *gen, uint32_t numInstructions) {
1.266 + insData_ = gen->allocate<InstructionData>(numInstructions);
1.267 + numIns_ = numInstructions;
1.268 + if (!insData_)
1.269 + return false;
1.270 + memset(insData_, 0, sizeof(InstructionData) * numInstructions);
1.271 + return true;
1.272 + }
1.273 +
1.274 + InstructionData &operator[](const CodePosition &pos) {
1.275 + JS_ASSERT(pos.ins() < numIns_);
1.276 + return insData_[pos.ins()];
1.277 + }
1.278 + InstructionData &operator[](LInstruction *ins) {
1.279 + JS_ASSERT(ins->id() < numIns_);
1.280 + return insData_[ins->id()];
1.281 + }
1.282 + InstructionData &operator[](uint32_t ins) {
1.283 + JS_ASSERT(ins < numIns_);
1.284 + return insData_[ins];
1.285 + }
1.286 +};
1.287 +
1.288 +// Common superclass for register allocators.
1.289 +class RegisterAllocator
1.290 +{
1.291 + void operator=(const RegisterAllocator &) MOZ_DELETE;
1.292 + RegisterAllocator(const RegisterAllocator &) MOZ_DELETE;
1.293 +
1.294 + protected:
1.295 + // Context
1.296 + MIRGenerator *mir;
1.297 + LIRGenerator *lir;
1.298 + LIRGraph &graph;
1.299 +
1.300 + // Pool of all registers that should be considered allocateable
1.301 + RegisterSet allRegisters_;
1.302 +
1.303 + // Computed data
1.304 + InstructionDataMap insData;
1.305 +
1.306 + RegisterAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
1.307 + : mir(mir),
1.308 + lir(lir),
1.309 + graph(graph),
1.310 + allRegisters_(RegisterSet::All())
1.311 + {
1.312 + if (FramePointer != InvalidReg && mir->instrumentedProfiling())
1.313 + allRegisters_.take(AnyRegister(FramePointer));
1.314 +#if defined(JS_CODEGEN_X64)
1.315 + if (mir->compilingAsmJS())
1.316 + allRegisters_.take(AnyRegister(HeapReg));
1.317 +#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS)
1.318 + if (mir->compilingAsmJS()) {
1.319 + allRegisters_.take(AnyRegister(HeapReg));
1.320 + allRegisters_.take(AnyRegister(GlobalReg));
1.321 + allRegisters_.take(AnyRegister(NANReg));
1.322 + }
1.323 +#endif
1.324 + }
1.325 +
1.326 + bool init();
1.327 +
1.328 + TempAllocator &alloc() const {
1.329 + return mir->alloc();
1.330 + }
1.331 +
1.332 + static CodePosition outputOf(uint32_t pos) {
1.333 + return CodePosition(pos, CodePosition::OUTPUT);
1.334 + }
1.335 + static CodePosition outputOf(const LInstruction *ins) {
1.336 + return CodePosition(ins->id(), CodePosition::OUTPUT);
1.337 + }
1.338 + static CodePosition inputOf(uint32_t pos) {
1.339 + return CodePosition(pos, CodePosition::INPUT);
1.340 + }
1.341 + static CodePosition inputOf(const LInstruction *ins) {
1.342 + // Phi nodes "use" their inputs before the beginning of the block.
1.343 + JS_ASSERT(!ins->isPhi());
1.344 + return CodePosition(ins->id(), CodePosition::INPUT);
1.345 + }
1.346 +
1.347 + LMoveGroup *getInputMoveGroup(uint32_t ins);
1.348 + LMoveGroup *getMoveGroupAfter(uint32_t ins);
1.349 +
1.350 + LMoveGroup *getInputMoveGroup(CodePosition pos) {
1.351 + return getInputMoveGroup(pos.ins());
1.352 + }
1.353 + LMoveGroup *getMoveGroupAfter(CodePosition pos) {
1.354 + return getMoveGroupAfter(pos.ins());
1.355 + }
1.356 +
1.357 + CodePosition minimalDefEnd(LInstruction *ins) {
1.358 + // Compute the shortest interval that captures vregs defined by ins.
1.359 + // Watch for instructions that are followed by an OSI point and/or Nop.
1.360 + // If moves are introduced between the instruction and the OSI point then
1.361 + // safepoint information for the instruction may be incorrect.
1.362 + while (true) {
1.363 + LInstruction *next = insData[outputOf(ins).next()].ins();
1.364 + if (!next->isNop() && !next->isOsiPoint())
1.365 + break;
1.366 + ins = next;
1.367 + }
1.368 +
1.369 + return outputOf(ins);
1.370 + }
1.371 +};
1.372 +
1.373 +static inline AnyRegister
1.374 +GetFixedRegister(const LDefinition *def, const LUse *use)
1.375 +{
1.376 + return def->isFloatReg()
1.377 + ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
1.378 + : AnyRegister(Register::FromCode(use->registerCode()));
1.379 +}
1.380 +
1.381 +} // namespace jit
1.382 +} // namespace js
1.383 +
1.384 +#endif /* jit_RegisterAllocator_h */
