Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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
#ifndef jit_RegisterAllocator_h
#define jit_RegisterAllocator_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;
#ifdef DEBUG
// 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.
[[nodiscard]] 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.
[[nodiscard]] bool check();
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() = default;
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() = default;
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;
using Lookup = IntegrityItem;
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;
[[nodiscard]] bool checkIntegrity(LBlock* block, LInstruction* ins,
uint32_t vreg, LAllocation alloc);
void checkSafepointAllocation(LInstruction* ins, uint32_t vreg,
LAllocation alloc);
[[nodiscard]] bool addPredecessor(LBlock* block, uint32_t vreg,
LAllocation alloc);
void dump();
};
#endif // DEBUG
// 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() {}
[[nodiscard]] 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()) {
MOZ_ASSERT(!allRegisters_.has(FramePointer));
if (mir->compilingWasm()) {
takeWasmRegisters(allRegisters_);
}
}
[[nodiscard]] 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);
// Atomic group helper. See comments in BacktrackingAllocator.cpp.
CodePosition minimalDefEnd(LNode* ins) const;
void dumpInstructions(const char* who);
public:
template <typename TakeableSet>
static void takeWasmRegisters(TakeableSet& regs) {
#if defined(JS_CODEGEN_X64) || defined(JS_CODEGEN_ARM) || \
defined(JS_CODEGEN_ARM64) || defined(JS_CODEGEN_MIPS32) || \
defined(JS_CODEGEN_MIPS64) || defined(JS_CODEGEN_LOONG64) || \
defined(JS_CODEGEN_RISCV64)
regs.take(HeapReg);
#endif
MOZ_ASSERT(!regs.has(FramePointer));
}
};
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 */