mirror of
https://github.com/classilla/tenfourfox.git
synced 2024-06-02 08:41:34 +00:00
375 lines
12 KiB
C++
375 lines
12 KiB
C++
/* -*- 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(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:
|
|
|
|
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()
|
|
{ }
|
|
|
|
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() {}
|
|
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;
|
|
|
|
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
|
|
{
|
|
private:
|
|
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_;
|
|
|
|
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) {
|
|
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()
|
|
: 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;
|
|
|
|
protected:
|
|
// 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),
|
|
lir(lir),
|
|
graph(graph),
|
|
allRegisters_(RegisterSet::All())
|
|
{
|
|
if (mir->compilingAsmJS()) {
|
|
#if defined(JS_CODEGEN_X64)
|
|
allRegisters_.take(AnyRegister(HeapReg));
|
|
#elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64)
|
|
allRegisters_.take(AnyRegister(HeapReg));
|
|
allRegisters_.take(AnyRegister(GlobalReg));
|
|
#elif defined(JS_CODEGEN_ARM64)
|
|
allRegisters_.take(AnyRegister(HeapReg));
|
|
allRegisters_.take(AnyRegister(HeapLenReg));
|
|
allRegisters_.take(AnyRegister(GlobalReg));
|
|
#endif
|
|
} else {
|
|
if (FramePointer != InvalidReg && mir->instrumentedProfiling())
|
|
allRegisters_.take(AnyRegister(FramePointer));
|
|
}
|
|
}
|
|
|
|
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())
|
|
break;
|
|
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 */
|