blob: f625f55d72192d60cabf106d37e0c8b5e4afd53c [file] [log] [blame]
/* -*- 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 */
#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.
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);
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(const InstructionInfo& o)
AutoEnterOOMUnsafeRegion oomUnsafe;
if (!inputs.appendAll(o.inputs) ||
!temps.appendAll(o.temps) ||
Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
struct BlockInfo {
Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
BlockInfo() {}
BlockInfo(const BlockInfo& o) {
AutoEnterOOMUnsafeRegion oomUnsafe;
if (!phis.appendAll(o.phis))
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;
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
MOZ_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_;
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 {
MOZ_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_;
: insData_()
{ }
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;
// Context
MIRGenerator* mir;
LIRGenerator* lir;
LIRGraph& graph;
// Pool of all registers that should be considered allocateable
AllocatableRegisterSet allRegisters_;
// Computed data
InstructionDataMap insData;
RegisterAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
: mir(mir),
if (mir->compilingAsmJS()) {
#if defined(JS_CODEGEN_X64)
#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64)
#elif defined(JS_CODEGEN_ARM64)
} else {
if (FramePointer != InvalidReg && mir->instrumentedProfiling())
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 block->numPhis() != 0
? CodePosition(block->getPhi(0)->id(), CodePosition::INPUT)
: inputOf(block->firstInstructionWithId());
CodePosition exitOf(const LBlock* block) {
return outputOf(block->lastInstructionWithId());
LMoveGroup* getInputMoveGroup(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())
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 */