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
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "jit/MIRGraph.h"
#include "jit/CompileInfo.h"
#include "jit/InlineScriptTree.h"
#include "jit/IonOptimizationLevels.h"
#include "jit/JitSpewer.h"
#include "jit/MIR.h"
#include "jit/MIRGenerator.h"
using namespace js;
using namespace js::jit;
MIRGenerator::MIRGenerator(CompileRealm* realm,
const JitCompileOptions& options,
TempAllocator* alloc, MIRGraph* graph,
const CompileInfo* info,
const OptimizationInfo* optimizationInfo)
: realm(realm),
runtime(realm ? realm->runtime() : nullptr),
outerInfo_(info),
optimizationInfo_(optimizationInfo),
alloc_(alloc),
graph_(graph),
offThreadStatus_(Ok()),
cancelBuild_(false),
wasmMaxStackArgBytes_(0),
needsOverrecursedCheck_(false),
needsStaticStackAlignment_(false),
instrumentedProfiling_(false),
instrumentedProfilingIsCached_(false),
stringsCanBeInNursery_(realm ? realm->zone()->canNurseryAllocateStrings()
: false),
bigIntsCanBeInNursery_(realm ? realm->zone()->canNurseryAllocateBigInts()
: false),
minWasmMemory0Length_(0),
options(options),
gs_(alloc) {}
bool MIRGenerator::licmEnabled() const {
return optimizationInfo().licmEnabled() && !disableLICM_ &&
!outerInfo().hadLICMInvalidation();
}
mozilla::GenericErrorResult<AbortReason> MIRGenerator::abort(AbortReason r) {
if (JitSpewEnabled(JitSpew_IonAbort)) {
switch (r) {
case AbortReason::Alloc:
JitSpew(JitSpew_IonAbort, "AbortReason::Alloc");
break;
case AbortReason::Disable:
JitSpew(JitSpew_IonAbort, "AbortReason::Disable");
break;
case AbortReason::Error:
JitSpew(JitSpew_IonAbort, "AbortReason::Error");
break;
case AbortReason::NoAbort:
MOZ_CRASH("Abort with AbortReason::NoAbort");
break;
}
}
return Err(std::move(r));
}
mozilla::GenericErrorResult<AbortReason> MIRGenerator::abortFmt(
AbortReason r, const char* message, va_list ap) {
JitSpewVA(JitSpew_IonAbort, message, ap);
return Err(std::move(r));
}
mozilla::GenericErrorResult<AbortReason> MIRGenerator::abort(
AbortReason r, const char* message, ...) {
va_list ap;
va_start(ap, message);
auto forward = abortFmt(r, message, ap);
va_end(ap);
return forward;
}
void MIRGraph::addBlock(MBasicBlock* block) {
MOZ_ASSERT(block);
block->setId(blockIdGen_++);
blocks_.pushBack(block);
numBlocks_++;
}
void MIRGraph::insertBlockAfter(MBasicBlock* at, MBasicBlock* block) {
block->setId(blockIdGen_++);
blocks_.insertAfter(at, block);
numBlocks_++;
}
void MIRGraph::insertBlockBefore(MBasicBlock* at, MBasicBlock* block) {
block->setId(blockIdGen_++);
blocks_.insertBefore(at, block);
numBlocks_++;
}
void MIRGraph::removeBlock(MBasicBlock* block) {
// Remove a block from the graph. It will also cleanup the block.
if (block == osrBlock_) {
osrBlock_ = nullptr;
}
if (returnAccumulator_) {
size_t i = 0;
while (i < returnAccumulator_->length()) {
if ((*returnAccumulator_)[i] == block) {
returnAccumulator_->erase(returnAccumulator_->begin() + i);
} else {
i++;
}
}
}
block->clear();
block->markAsDead();
if (block->isInList()) {
blocks_.remove(block);
numBlocks_--;
}
}
void MIRGraph::unmarkBlocks() {
for (MBasicBlockIterator i(blocks_.begin()); i != blocks_.end(); i++) {
i->unmark();
}
}
MBasicBlock* MBasicBlock::New(MIRGraph& graph, size_t stackDepth,
const CompileInfo& info, MBasicBlock* maybePred,
BytecodeSite* site, Kind kind) {
MOZ_ASSERT(site->pc() != nullptr);
MBasicBlock* block = new (graph.alloc()) MBasicBlock(graph, info, site, kind);
if (!block->init()) {
return nullptr;
}
if (!block->inherit(graph.alloc(), stackDepth, maybePred, 0)) {
return nullptr;
}
return block;
}
MBasicBlock* MBasicBlock::NewPopN(MIRGraph& graph, const CompileInfo& info,
MBasicBlock* pred, BytecodeSite* site,
Kind kind, uint32_t popped) {
MOZ_ASSERT(site->pc() != nullptr);
MBasicBlock* block = new (graph.alloc()) MBasicBlock(graph, info, site, kind);
if (!block->init()) {
return nullptr;
}
if (!block->inherit(graph.alloc(), pred->stackDepth(), pred, popped)) {
return nullptr;
}
return block;
}
MBasicBlock* MBasicBlock::NewPendingLoopHeader(MIRGraph& graph,
const CompileInfo& info,
MBasicBlock* pred,
BytecodeSite* site) {
MOZ_ASSERT(site->pc() != nullptr);
MBasicBlock* block =
new (graph.alloc()) MBasicBlock(graph, info, site, PENDING_LOOP_HEADER);
if (!block->init()) {
return nullptr;
}
if (!block->inherit(graph.alloc(), pred->stackDepth(), pred, 0)) {
return nullptr;
}
return block;
}
MBasicBlock* MBasicBlock::NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
size_t predEdgeIdx, MBasicBlock* succ) {
MBasicBlock* split = nullptr;
if (!succ->pc()) {
// The predecessor does not have a PC, this is a Wasm compilation.
split = MBasicBlock::New(graph, succ->info(), pred, SPLIT_EDGE);
if (!split) {
return nullptr;
}
// Insert the split edge block in-between.
split->end(MGoto::New(graph.alloc(), succ));
} else {
// The predecessor has a PC, this is a Warp compilation.
MResumePoint* succEntry = succ->entryResumePoint();
BytecodeSite* site =
new (graph.alloc()) BytecodeSite(succ->trackedTree(), succEntry->pc());
split =
new (graph.alloc()) MBasicBlock(graph, succ->info(), site, SPLIT_EDGE);
if (!split->init()) {
return nullptr;
}
// A split edge is used to simplify the graph to avoid having a
// predecessor with multiple successors as well as a successor with
// multiple predecessors. As instructions can be moved in this
// split-edge block, we need to give this block a resume point. To do
// so, we copy the entry resume points of the successor and filter the
// phis to keep inputs from the current edge.
// Propagate the caller resume point from the inherited block.
split->callerResumePoint_ = succ->callerResumePoint();
// Split-edge are created after the interpreter stack emulation. Thus,
// there is no need for creating slots.
split->stackPosition_ = succEntry->stackDepth();
// Create a resume point using our initial stack position.
MResumePoint* splitEntry = new (graph.alloc())
MResumePoint(split, succEntry->pc(), ResumeMode::ResumeAt);
if (!splitEntry->init(graph.alloc())) {
return nullptr;
}
split->entryResumePoint_ = splitEntry;
// Insert the split edge block in-between.
split->end(MGoto::New(graph.alloc(), succ));
// The target entry resume point might have phi operands, keep the
// operands of the phi coming from our edge.
size_t succEdgeIdx = succ->indexForPredecessor(pred);
for (size_t i = 0, e = splitEntry->numOperands(); i < e; i++) {
MDefinition* def = succEntry->getOperand(i);
// This early in the pipeline, we have no recover instructions in
// any entry resume point.
if (def->block() == succ) {
if (def->isPhi()) {
def = def->toPhi()->getOperand(succEdgeIdx);
} else {
// The phi-operand may already have been optimized out.
MOZ_ASSERT(def->isConstant());
MOZ_ASSERT(def->type() == MIRType::MagicOptimizedOut);
def = split->optimizedOutConstant(graph.alloc());
}
}
splitEntry->initOperand(i, def);
}
// This is done in the New variant for wasm, so we cannot keep this
// line below, where the rest of the graph is modified.
if (!split->predecessors_.append(pred)) {
return nullptr;
}
}
split->setLoopDepth(succ->loopDepth());
graph.insertBlockAfter(pred, split);
pred->replaceSuccessor(predEdgeIdx, split);
succ->replacePredecessor(pred, split);
return split;
}
void MBasicBlock::moveToNewBlock(MInstruction* ins, MBasicBlock* dst) {
MOZ_ASSERT(ins->block() == this);
MOZ_ASSERT(!dst->hasLastIns());
instructions_.remove(ins);
ins->setInstructionBlock(dst, dst->trackedSite());
if (MResumePoint* rp = ins->resumePoint()) {
removeResumePoint(rp);
dst->addResumePoint(rp);
rp->setBlock(dst);
}
dst->instructions_.pushBack(ins);
}
void MBasicBlock::moveOuterResumePointTo(MBasicBlock* dest) {
if (MResumePoint* outer = outerResumePoint()) {
removeResumePoint(outer);
outerResumePoint_ = nullptr;
dest->setOuterResumePoint(outer);
dest->addResumePoint(outer);
outer->setBlock(dest);
}
}
bool MBasicBlock::wrapInstructionInFastpath(MInstruction* ins,
MInstruction* fastpath,
MInstruction* condition) {
MOZ_ASSERT(ins->block() == this);
MOZ_ASSERT(!ins->isControlInstruction());
MInstructionIterator rest(begin(ins));
rest++;
MResumePoint* resumeBeforeIns = activeResumePoint(ins);
MResumePoint* resumeAfterIns = activeResumePoint(*rest);
// Create the join block.
MBasicBlock* join = MBasicBlock::NewInternal(graph_, this, resumeAfterIns);
if (!join) {
return false;
}
// Update the successors of the current block.
for (uint32_t i = 0; i < numSuccessors(); i++) {
getSuccessor(i)->replacePredecessor(this, join);
}
if (successorWithPhis()) {
join->setSuccessorWithPhis(successorWithPhis(), positionInPhiSuccessor());
clearSuccessorWithPhis();
}
// Copy all instructions after |ins| into the join block.
while (rest != end()) {
MInstruction* ins = *rest++;
moveToNewBlock(ins, join);
}
MOZ_ASSERT(!hasLastIns());
MOZ_ASSERT(join->hasLastIns());
graph_.insertBlockAfter(this, join);
// Create the fast path block.
MBasicBlock* fastpathBlock =
MBasicBlock::NewInternal(graph_, this, resumeBeforeIns);
if (!fastpathBlock) {
return false;
}
graph_.insertBlockAfter(this, fastpathBlock);
fastpathBlock->add(fastpath);
fastpathBlock->end(MGoto::New(graph_.alloc(), join));
// Create the slowpath block.
MBasicBlock* slowpathBlock =
MBasicBlock::NewInternal(graph_, this, resumeBeforeIns);
if (!slowpathBlock) {
return false;
}
graph_.insertBlockAfter(fastpathBlock, slowpathBlock);
moveToNewBlock(ins, slowpathBlock);
slowpathBlock->end(MGoto::New(graph_.alloc(), join));
// Connect current block to fastpath and slowpath.
add(condition);
end(MTest::New(graph_.alloc(), condition, fastpathBlock, slowpathBlock));
// Update predecessors.
if (!fastpathBlock->addPredecessorWithoutPhis(this) ||
!slowpathBlock->addPredecessorWithoutPhis(this) ||
!join->addPredecessorWithoutPhis(fastpathBlock) ||
!join->addPredecessorWithoutPhis(slowpathBlock)) {
return false;
}
if (ins->hasUses()) {
// Insert phi.
MPhi* phi = MPhi::New(graph_.alloc());
if (!phi->reserveLength(2)) {
return false;
}
phi->addInput(fastpath);
fastpathBlock->setSuccessorWithPhis(join, 0);
phi->addInput(ins);
slowpathBlock->setSuccessorWithPhis(join, 1);
join->addPhi(phi);
for (MUseIterator i(ins->usesBegin()), e(ins->usesEnd()); i != e;) {
MUse* use = *i++;
if (use->consumer() != phi && use->consumer() != ins->resumePoint()) {
use->replaceProducer(phi);
}
}
}
moveOuterResumePointTo(join);
return true;
}
MBasicBlock* MBasicBlock::NewInternal(MIRGraph& graph, MBasicBlock* orig,
MResumePoint* resumePoint) {
jsbytecode* pc = IsResumeAfter(resumePoint->mode())
? GetNextPc(resumePoint->pc())
: resumePoint->pc();
BytecodeSite* site =
new (graph.alloc()) BytecodeSite(orig->trackedTree(), pc);
MBasicBlock* block =
new (graph.alloc()) MBasicBlock(graph, orig->info(), site, INTERNAL);
if (!block->init()) {
return nullptr;
}
// Propagate the caller resume point from the original block.
block->callerResumePoint_ = orig->callerResumePoint();
// Copy the resume point.
block->stackPosition_ = resumePoint->stackDepth();
MResumePoint* entryResumePoint =
new (graph.alloc()) MResumePoint(block, pc, ResumeMode::ResumeAt);
if (!entryResumePoint->init(graph.alloc())) {
return nullptr;
}
for (size_t i = 0; i < resumePoint->stackDepth(); i++) {
entryResumePoint->initOperand(i, resumePoint->getOperand(i));
}
block->entryResumePoint_ = entryResumePoint;
block->setLoopDepth(orig->loopDepth());
return block;
}
MBasicBlock* MBasicBlock::New(MIRGraph& graph, const CompileInfo& info,
MBasicBlock* pred, Kind kind) {
BytecodeSite* site = new (graph.alloc()) BytecodeSite();
MBasicBlock* block = new (graph.alloc()) MBasicBlock(graph, info, site, kind);
if (!block->init()) {
return nullptr;
}
if (pred) {
block->stackPosition_ = pred->stackPosition_;
if (block->kind_ == PENDING_LOOP_HEADER) {
size_t nphis = block->stackPosition_;
size_t nfree = graph.phiFreeListLength();
TempAllocator& alloc = graph.alloc();
MPhi* phis = nullptr;
if (nphis > nfree) {
phis = alloc.allocateArray<MPhi>(nphis - nfree);
if (!phis) {
return nullptr;
}
}
// Note: Phis are inserted in the same order as the slots.
for (size_t i = 0; i < nphis; i++) {
MDefinition* predSlot = pred->getSlot(i);
MOZ_ASSERT(predSlot->type() != MIRType::Value);
MPhi* phi;
if (i < nfree) {
phi = graph.takePhiFromFreeList();
} else {
phi = phis + (i - nfree);
}
new (phi) MPhi(alloc, predSlot->type());
phi->addInlineInput(predSlot);
// Add append Phis in the block.
block->addPhi(phi);
block->setSlot(i, phi);
}
} else {
if (!block->ensureHasSlots(0)) {
return nullptr;
}
block->copySlots(pred);
}
if (!block->predecessors_.append(pred)) {
return nullptr;
}
}
return block;
}
// Create an empty and unreachable block which jumps to |header|. Used
// when the normal entry into a loop is removed (but the loop is still
// reachable due to OSR) to preserve the invariant that every loop
// header has two predecessors, which is needed for building the
// dominator tree. The new block is inserted immediately before the
// header, which preserves the graph ordering (post-order/RPO). These
// blocks will all be removed before lowering.
MBasicBlock* MBasicBlock::NewFakeLoopPredecessor(MIRGraph& graph,
MBasicBlock* header) {
MOZ_ASSERT(graph.osrBlock());
MBasicBlock* backedge = header->backedge();
MBasicBlock* fake = MBasicBlock::New(graph, header->info(), nullptr,
MBasicBlock::FAKE_LOOP_PRED);
if (!fake) {
return nullptr;
}
graph.insertBlockBefore(header, fake);
fake->setUnreachable();
// Create fake defs to use as inputs for any phis in |header|.
for (MPhiIterator iter(header->phisBegin()), end(header->phisEnd());
iter != end; ++iter) {
if (!graph.alloc().ensureBallast()) {
return nullptr;
}
MPhi* phi = *iter;
auto* fakeDef = MUnreachableResult::New(graph.alloc(), phi->type());
fake->add(fakeDef);
if (!phi->addInputSlow(fakeDef)) {
return nullptr;
}
}
fake->end(MGoto::New(graph.alloc(), header));
if (!header->addPredecessorWithoutPhis(fake)) {
return nullptr;
}
// The backedge is always the last predecessor, but we have added a
// new pred. Restore |backedge| as |header|'s loop backedge.
header->clearLoopHeader();
header->setLoopHeader(backedge);
return fake;
}
void MIRGraph::removeFakeLoopPredecessors() {
MOZ_ASSERT(osrBlock());
size_t id = 0;
for (ReversePostorderIterator it = rpoBegin(); it != rpoEnd();) {
MBasicBlock* block = *it++;
if (block->isFakeLoopPred()) {
MOZ_ASSERT(block->unreachable());
MBasicBlock* succ = block->getSingleSuccessor();
succ->removePredecessor(block);
removeBlock(block);
} else {
block->setId(id++);
}
}
#ifdef DEBUG
canBuildDominators_ = false;
#endif
}
MBasicBlock::MBasicBlock(MIRGraph& graph, const CompileInfo& info,
BytecodeSite* site, Kind kind)
: graph_(graph),
info_(info),
predecessors_(graph.alloc()),
stackPosition_(info_.firstStackSlot()),
id_(0),
domIndex_(0),
numDominated_(0),
lir_(nullptr),
callerResumePoint_(nullptr),
entryResumePoint_(nullptr),
outerResumePoint_(nullptr),
successorWithPhis_(nullptr),
positionInPhiSuccessor_(0),
loopDepth_(0),
kind_(kind),
mark_(false),
immediatelyDominated_(graph.alloc()),
immediateDominator_(nullptr),
trackedSite_(site) {
MOZ_ASSERT(trackedSite_, "trackedSite_ is non-nullptr");
}
bool MBasicBlock::init() { return slots_.init(graph_.alloc(), info_.nslots()); }
bool MBasicBlock::increaseSlots(size_t num) {
return slots_.growBy(graph_.alloc(), num);
}
bool MBasicBlock::ensureHasSlots(size_t num) {
size_t depth = stackDepth() + num;
if (depth > nslots()) {
if (!increaseSlots(depth - nslots())) {
return false;
}
}
return true;
}
void MBasicBlock::copySlots(MBasicBlock* from) {
MOZ_ASSERT(stackPosition_ <= from->stackPosition_);
MOZ_ASSERT(stackPosition_ <= nslots());
MDefinition** thisSlots = slots_.begin();
MDefinition** fromSlots = from->slots_.begin();
for (size_t i = 0, e = stackPosition_; i < e; ++i) {
thisSlots[i] = fromSlots[i];
}
}
bool MBasicBlock::inherit(TempAllocator& alloc, size_t stackDepth,
MBasicBlock* maybePred, uint32_t popped) {
MOZ_ASSERT_IF(maybePred, maybePred->stackDepth() == stackDepth);
MOZ_ASSERT(stackDepth >= popped);
stackDepth -= popped;
stackPosition_ = stackDepth;
if (maybePred && kind_ != PENDING_LOOP_HEADER) {
copySlots(maybePred);
}
MOZ_ASSERT(info_.nslots() >= stackPosition_);
MOZ_ASSERT(!entryResumePoint_);
// Propagate the caller resume point from the inherited block.
callerResumePoint_ = maybePred ? maybePred->callerResumePoint() : nullptr;
// Create a resume point using our initial stack state.
entryResumePoint_ =
new (alloc) MResumePoint(this, pc(), ResumeMode::ResumeAt);
if (!entryResumePoint_->init(alloc)) {
return false;
}
if (maybePred) {
if (!predecessors_.append(maybePred)) {
return false;
}
if (kind_ == PENDING_LOOP_HEADER) {
for (size_t i = 0; i < stackDepth; i++) {
MPhi* phi = MPhi::New(alloc.fallible());
if (!phi) {
return false;
}
phi->addInlineInput(maybePred->getSlot(i));
addPhi(phi);
setSlot(i, phi);
entryResumePoint()->initOperand(i, phi);
}
} else {
for (size_t i = 0; i < stackDepth; i++) {
entryResumePoint()->initOperand(i, getSlot(i));
}
}
} else {
/*
* Don't leave the operands uninitialized for the caller, as it may not
* initialize them later on.
*/
for (size_t i = 0; i < stackDepth; i++) {
entryResumePoint()->clearOperand(i);
}
}
return true;
}
void MBasicBlock::inheritSlots(MBasicBlock* parent) {
stackPosition_ = parent->stackPosition_;
copySlots(parent);
}
bool MBasicBlock::initEntrySlots(TempAllocator& alloc) {
// Remove the previous resume point.
discardResumePoint(entryResumePoint_);
// Create a resume point using our initial stack state.
entryResumePoint_ =
MResumePoint::New(alloc, this, pc(), ResumeMode::ResumeAt);
if (!entryResumePoint_) {
return false;
}
return true;
}
MDefinition* MBasicBlock::environmentChain() {
return getSlot(info().environmentChainSlot());
}
MDefinition* MBasicBlock::argumentsObject() {
return getSlot(info().argsObjSlot());
}
void MBasicBlock::setEnvironmentChain(MDefinition* scopeObj) {
setSlot(info().environmentChainSlot(), scopeObj);
}
void MBasicBlock::setArgumentsObject(MDefinition* argsObj) {
setSlot(info().argsObjSlot(), argsObj);
}
void MBasicBlock::pick(int32_t depth) {
// pick takes a value and moves it to the top.
// pick(-2):
// A B C D E
// A B D C E [ swapAt(-2) ]
// A B D E C [ swapAt(-1) ]
for (; depth < 0; depth++) {
swapAt(depth);
}
}
void MBasicBlock::unpick(int32_t depth) {
// unpick takes the value on top of the stack and moves it under the depth-th
// element;
// unpick(-2):
// A B C D E
// A B C E D [ swapAt(-1) ]
// A B E C D [ swapAt(-2) ]
for (int32_t n = -1; n >= depth; n--) {
swapAt(n);
}
}
void MBasicBlock::swapAt(int32_t depth) {
uint32_t lhsDepth = stackPosition_ + depth - 1;
uint32_t rhsDepth = stackPosition_ + depth;
MDefinition* temp = slots_[lhsDepth];
slots_[lhsDepth] = slots_[rhsDepth];
slots_[rhsDepth] = temp;
}
void MBasicBlock::discardLastIns() { discard(lastIns()); }
MConstant* MBasicBlock::optimizedOutConstant(TempAllocator& alloc) {
// If the first instruction is a MConstant(MagicValue(JS_OPTIMIZED_OUT))
// then reuse it.
MInstruction* ins = *begin();
if (ins->type() == MIRType::MagicOptimizedOut) {
return ins->toConstant();
}
MConstant* constant = MConstant::New(alloc, MagicValue(JS_OPTIMIZED_OUT));
insertBefore(ins, constant);
return constant;
}
void MBasicBlock::moveBefore(MInstruction* at, MInstruction* ins) {
// Remove |ins| from the current block.
MOZ_ASSERT(ins->block() == this);
instructions_.remove(ins);
// Insert into new block, which may be distinct.
// Uses and operands are untouched.
ins->setInstructionBlock(at->block(), at->trackedSite());
at->block()->instructions_.insertBefore(at, ins);
}
MInstruction* MBasicBlock::safeInsertTop(MDefinition* ins, IgnoreTop ignore) {
MOZ_ASSERT(graph().osrBlock() != this,
"We are not supposed to add any instruction in OSR blocks.");
// Beta nodes and interrupt checks are required to be located at the
// beginnings of basic blocks, so we must insert new instructions after any
// such instructions.
MInstructionIterator insertIter =
!ins || ins->isPhi() ? begin() : begin(ins->toInstruction());
while (insertIter->isBeta() || insertIter->isInterruptCheck() ||
insertIter->isConstant() || insertIter->isParameter() ||
(!(ignore & IgnoreRecover) && insertIter->isRecoveredOnBailout())) {
insertIter++;
}
return *insertIter;
}
void MBasicBlock::discardResumePoint(
MResumePoint* rp, ReferencesType refType /* = RefType_Default */) {
if (refType & RefType_DiscardOperands) {
rp->releaseUses();
}
rp->setDiscarded();
removeResumePoint(rp);
}
void MBasicBlock::removeResumePoint(MResumePoint* rp) {
#ifdef DEBUG
MResumePointIterator iter = resumePointsBegin();
while (*iter != rp) {
// We should reach it before reaching the end.
MOZ_ASSERT(iter != resumePointsEnd());
iter++;
}
resumePoints_.removeAt(iter);
#endif
}
void MBasicBlock::prepareForDiscard(
MInstruction* ins, ReferencesType refType /* = RefType_Default */) {
// Only remove instructions from the same basic block. This is needed for
// correctly removing the resume point if any.
MOZ_ASSERT(ins->block() == this);
MResumePoint* rp = ins->resumePoint();
if ((refType & RefType_DiscardResumePoint) && rp) {
discardResumePoint(rp, refType);
}
// We need to assert that instructions have no uses after removing the their
// resume points operands as they could be captured by their own resume
// point.
MOZ_ASSERT_IF(refType & RefType_AssertNoUses, !ins->hasUses());
const uint32_t InstructionOperands =
RefType_DiscardOperands | RefType_DiscardInstruction;
if ((refType & InstructionOperands) == InstructionOperands) {
for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
ins->releaseOperand(i);
}
}
ins->setDiscarded();
}
void MBasicBlock::discard(MInstruction* ins) {
prepareForDiscard(ins);
instructions_.remove(ins);
}
void MBasicBlock::discardIgnoreOperands(MInstruction* ins) {
#ifdef DEBUG
for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
MOZ_ASSERT(!ins->hasOperand(i));
}
#endif
prepareForDiscard(ins, RefType_IgnoreOperands);
instructions_.remove(ins);
}
void MBasicBlock::discardAllInstructions() {
MInstructionIterator iter = begin();
discardAllInstructionsStartingAt(iter);
}
void MBasicBlock::discardAllInstructionsStartingAt(MInstructionIterator iter) {
while (iter != end()) {
// Discard operands and resume point operands and flag the instruction
// as discarded. Also we do not assert that we have no uses as blocks
// might be removed in reverse post order.
MInstruction* ins = *iter++;
prepareForDiscard(ins, RefType_DefaultNoAssert);
instructions_.remove(ins);
}
}
void MBasicBlock::discardAllPhis() {
for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
iter->removeAllOperands();
}
for (MBasicBlock** pred = predecessors_.begin(); pred != predecessors_.end();
pred++) {
(*pred)->clearSuccessorWithPhis();
}
phis_.clear();
}
void MBasicBlock::discardAllResumePoints(bool discardEntry) {
if (outerResumePoint_) {
clearOuterResumePoint();
}
if (discardEntry && entryResumePoint_) {
clearEntryResumePoint();
}
#ifdef DEBUG
if (!entryResumePoint()) {
MOZ_ASSERT(resumePointsEmpty());
} else {
MResumePointIterator iter(resumePointsBegin());
MOZ_ASSERT(iter != resumePointsEnd());
iter++;
MOZ_ASSERT(iter == resumePointsEnd());
}
#endif
}
void MBasicBlock::clear() {
discardAllInstructions();
discardAllResumePoints();
discardAllPhis();
}
void MBasicBlock::insertBefore(MInstruction* at, MInstruction* ins) {
MOZ_ASSERT(at->block() == this);
ins->setInstructionBlock(this, at->trackedSite());
graph().allocDefinitionId(ins);
instructions_.insertBefore(at, ins);
}
void MBasicBlock::insertAfter(MInstruction* at, MInstruction* ins) {
MOZ_ASSERT(at->block() == this);
ins->setInstructionBlock(this, at->trackedSite());
graph().allocDefinitionId(ins);
instructions_.insertAfter(at, ins);
}
void MBasicBlock::insertAtEnd(MInstruction* ins) {
if (hasLastIns()) {
insertBefore(lastIns(), ins);
} else {
add(ins);
}
}
void MBasicBlock::addPhi(MPhi* phi) {
phis_.pushBack(phi);
phi->setPhiBlock(this);
graph().allocDefinitionId(phi);
}
void MBasicBlock::discardPhi(MPhi* phi) {
MOZ_ASSERT(!phis_.empty());
phi->removeAllOperands();
phi->setDiscarded();
phis_.remove(phi);
if (phis_.empty()) {
for (MBasicBlock* pred : predecessors_) {
pred->clearSuccessorWithPhis();
}
}
}
MResumePoint* MBasicBlock::activeResumePoint(MInstruction* ins) {
for (MInstructionReverseIterator iter = rbegin(ins); iter != rend(); iter++) {
if (iter->resumePoint() && *iter != ins) {
return iter->resumePoint();
}
}
// If none, take the entry resume point.
return entryResumePoint();
}
void MBasicBlock::flagOperandsOfPrunedBranches(MInstruction* ins) {
MResumePoint* rp = activeResumePoint(ins);
// The only blocks which do not have any entryResumePoint in Ion, are the
// SplitEdge blocks. SplitEdge blocks only have a Goto instruction before
// Range Analysis phase. In adjustInputs, we are manipulating instructions
// which have a TypePolicy. So, as a Goto has no operand and no type
// policy, the entry resume point should exist.
MOZ_ASSERT(rp);
// Flag all operands as being potentially used.
while (rp) {
for (size_t i = 0, end = rp->numOperands(); i < end; i++) {
rp->getOperand(i)->setImplicitlyUsedUnchecked();
}
rp = rp->caller();
}
}
bool MBasicBlock::addPredecessor(TempAllocator& alloc, MBasicBlock* pred) {
return addPredecessorPopN(alloc, pred, 0);
}
bool MBasicBlock::addPredecessorPopN(TempAllocator& alloc, MBasicBlock* pred,
uint32_t popped) {
MOZ_ASSERT(pred);
MOZ_ASSERT(predecessors_.length() > 0);
// Predecessors must be finished, and at the correct stack depth.
MOZ_ASSERT(pred->hasLastIns());
MOZ_ASSERT(pred->stackPosition_ == stackPosition_ + popped);
for (uint32_t i = 0, e = stackPosition_; i < e; ++i) {
MDefinition* mine = getSlot(i);
MDefinition* other = pred->getSlot(i);
if (mine != other) {
MIRType phiType = mine->type();
if (phiType != other->type()) {
phiType = MIRType::Value;
}
// If the current instruction is a phi, and it was created in this
// basic block, then we have already placed this phi and should
// instead append to its operands.
if (mine->isPhi() && mine->block() == this) {
MOZ_ASSERT(predecessors_.length());
MOZ_ASSERT(!mine->hasDefUses(),
"should only change type of newly created phis");
mine->setResultType(phiType);
if (!mine->toPhi()->addInputSlow(other)) {
return false;
}
} else {
// Otherwise, create a new phi node.
MPhi* phi = MPhi::New(alloc.fallible(), phiType);
if (!phi) {
return false;
}
addPhi(phi);
// Prime the phi for each predecessor, so input(x) comes from
// predecessor(x).
if (!phi->reserveLength(predecessors_.length() + 1)) {
return false;
}
for (size_t j = 0, numPreds = predecessors_.length(); j < numPreds;
++j) {
MOZ_ASSERT(predecessors_[j]->getSlot(i) == mine);
phi->addInput(mine);
}
phi->addInput(other);
setSlot(i, phi);
if (entryResumePoint()) {
entryResumePoint()->replaceOperand(i, phi);
}
}
}
}
return predecessors_.append(pred);
}
bool MBasicBlock::addPredecessorSameInputsAs(MBasicBlock* pred,
MBasicBlock* existingPred) {
MOZ_ASSERT(pred);
MOZ_ASSERT(predecessors_.length() > 0);
// Predecessors must be finished, and at the correct stack depth.
MOZ_ASSERT(pred->hasLastIns());
MOZ_ASSERT(!pred->successorWithPhis());
if (!phisEmpty()) {
size_t existingPosition = indexForPredecessor(existingPred);
for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
if (!iter->addInputSlow(iter->getOperand(existingPosition))) {
return false;
}
}
}
if (!predecessors_.append(pred)) {
return false;
}
return true;
}
bool MBasicBlock::addPredecessorWithoutPhis(MBasicBlock* pred) {
// Predecessors must be finished.
MOZ_ASSERT(pred && pred->hasLastIns());
return predecessors_.append(pred);
}
bool MBasicBlock::addImmediatelyDominatedBlock(MBasicBlock* child) {
return immediatelyDominated_.append(child);
}
void MBasicBlock::removeImmediatelyDominatedBlock(MBasicBlock* child) {
for (size_t i = 0;; ++i) {
MOZ_ASSERT(i < immediatelyDominated_.length(),
"Dominated block to remove not present");
if (immediatelyDominated_[i] == child) {
immediatelyDominated_[i] = immediatelyDominated_.back();
immediatelyDominated_.popBack();
return;
}
}
}
bool MBasicBlock::setBackedge(MBasicBlock* pred) {
// Predecessors must be finished, and at the correct stack depth.
MOZ_ASSERT(hasLastIns());
MOZ_ASSERT(pred->hasLastIns());
MOZ_ASSERT(pred->stackDepth() == entryResumePoint()->stackDepth());
// We must be a pending loop header
MOZ_ASSERT(kind_ == PENDING_LOOP_HEADER);
// Add exit definitions to each corresponding phi at the entry.
if (!inheritPhisFromBackedge(pred)) {
return false;
}
// We are now a loop header proper
kind_ = LOOP_HEADER;
return predecessors_.append(pred);
}
bool MBasicBlock::setBackedgeWasm(MBasicBlock* pred, size_t paramCount) {
// Predecessors must be finished, and at the correct stack depth.
MOZ_ASSERT(hasLastIns());
MOZ_ASSERT(pred->hasLastIns());
MOZ_ASSERT(stackDepth() + paramCount == pred->stackDepth());
// We must be a pending loop header
MOZ_ASSERT(kind_ == PENDING_LOOP_HEADER);
// Add exit definitions to each corresponding phi at the entry.
// Note: Phis are inserted in the same order as the slots. (see
// MBasicBlock::New)
size_t slot = 0;
for (MPhiIterator phi = phisBegin(); phi != phisEnd(); phi++, slot++) {
MPhi* entryDef = *phi;
MDefinition* exitDef = pred->getSlot(slot);
// Assert that we already placed phis for each slot.
MOZ_ASSERT(entryDef->block() == this);
// Assert that the phi already has the correct type.
MOZ_ASSERT(entryDef->type() == exitDef->type());
MOZ_ASSERT(entryDef->type() != MIRType::Value);
if (entryDef == exitDef) {
// If the exit def is the same as the entry def, make a redundant
// phi. Since loop headers have exactly two incoming edges, we
// know that that's just the first input.
//
// Note that we eliminate later rather than now, to avoid any
// weirdness around pending continue edges which might still hold
// onto phis.
exitDef = entryDef->getOperand(0);
}
// Phis always have room for 2 operands, so this can't fail.
MOZ_ASSERT(phi->numOperands() == 1);
entryDef->addInlineInput(exitDef);
// Two cases here: phis that correspond to locals, and phis that correspond
// to loop parameters. Only phis for locals go in slots.
if (slot < stackDepth()) {
setSlot(slot, entryDef);
}
}
// We are now a loop header proper
kind_ = LOOP_HEADER;
return predecessors_.append(pred);
}
void MBasicBlock::clearLoopHeader() {
MOZ_ASSERT(isLoopHeader());
kind_ = NORMAL;
}
void MBasicBlock::setLoopHeader(MBasicBlock* newBackedge) {
MOZ_ASSERT(!isLoopHeader());
kind_ = LOOP_HEADER;
size_t numPreds = numPredecessors();
MOZ_ASSERT(numPreds != 0);
size_t lastIndex = numPreds - 1;
size_t oldIndex = 0;
for (;; ++oldIndex) {
MOZ_ASSERT(oldIndex < numPreds);
MBasicBlock* pred = getPredecessor(oldIndex);
if (pred == newBackedge) {
break;
}
}
// Set the loop backedge to be the last element in predecessors_.
std::swap(predecessors_[oldIndex], predecessors_[lastIndex]);
// If we have phis, reorder their operands accordingly.
if (!phisEmpty()) {
getPredecessor(oldIndex)->setSuccessorWithPhis(this, oldIndex);
getPredecessor(lastIndex)->setSuccessorWithPhis(this, lastIndex);
for (MPhiIterator iter(phisBegin()), end(phisEnd()); iter != end; ++iter) {
MPhi* phi = *iter;
MDefinition* last = phi->getOperand(oldIndex);
MDefinition* old = phi->getOperand(lastIndex);
phi->replaceOperand(oldIndex, old);
phi->replaceOperand(lastIndex, last);
}
}
MOZ_ASSERT(newBackedge->loopHeaderOfBackedge() == this);
MOZ_ASSERT(backedge() == newBackedge);
}
size_t MBasicBlock::getSuccessorIndex(MBasicBlock* block) const {
MOZ_ASSERT(lastIns());
for (size_t i = 0; i < numSuccessors(); i++) {
if (getSuccessor(i) == block) {
return i;
}
}
MOZ_CRASH("Invalid successor");
}
size_t MBasicBlock::getPredecessorIndex(MBasicBlock* block) const {
for (size_t i = 0, e = numPredecessors(); i < e; ++i) {
if (getPredecessor(i) == block) {
return i;
}
}
MOZ_CRASH("Invalid predecessor");
}
void MBasicBlock::replaceSuccessor(size_t pos, MBasicBlock* split) {
MOZ_ASSERT(lastIns());
// Note, during split-critical-edges, successors-with-phis is not yet set.
// During PAA, this case is handled before we enter.
MOZ_ASSERT_IF(successorWithPhis_, successorWithPhis_ != getSuccessor(pos));
lastIns()->replaceSuccessor(pos, split);
}
void MBasicBlock::replacePredecessor(MBasicBlock* old, MBasicBlock* split) {
for (size_t i = 0; i < numPredecessors(); i++) {
if (getPredecessor(i) == old) {
predecessors_[i] = split;
#ifdef DEBUG
// The same block should not appear twice in the predecessor list.
for (size_t j = i; j < numPredecessors(); j++) {
MOZ_ASSERT(predecessors_[j] != old);
}
#endif
return;
}
}
MOZ_CRASH("predecessor was not found");
}
void MBasicBlock::clearDominatorInfo() {
setImmediateDominator(nullptr);
immediatelyDominated_.clear();
numDominated_ = 0;
}
void MBasicBlock::removePredecessorWithoutPhiOperands(MBasicBlock* pred,
size_t predIndex) {
// If we're removing the last backedge, this is no longer a loop.
if (isLoopHeader() && hasUniqueBackedge() && backedge() == pred) {
clearLoopHeader();
}
// Adjust phis. Note that this can leave redundant phis behind.
// Don't adjust successorWithPhis() if we haven't constructed this
// information yet.
if (pred->successorWithPhis()) {
MOZ_ASSERT(pred->positionInPhiSuccessor() == predIndex);
pred->clearSuccessorWithPhis();
for (size_t j = predIndex + 1; j < numPredecessors(); j++) {
getPredecessor(j)->setSuccessorWithPhis(this, j - 1);
}
}
// Remove from pred list.
predecessors_.erase(predecessors_.begin() + predIndex);
}
void MBasicBlock::removePredecessor(MBasicBlock* pred) {
size_t predIndex = getPredecessorIndex(pred);
// Remove the phi operands.
for (MPhiIterator iter(phisBegin()), end(phisEnd()); iter != end; ++iter) {
iter->removeOperand(predIndex);
}
// Now we can call the underlying function, which expects that phi
// operands have been removed.
removePredecessorWithoutPhiOperands(pred, predIndex);
}
bool MBasicBlock::inheritPhisFromBackedge(MBasicBlock* backedge) {
// We must be a pending loop header
MOZ_ASSERT(kind_ == PENDING_LOOP_HEADER);
size_t stackDepth = entryResumePoint()->stackDepth();
for (size_t slot = 0; slot < stackDepth; slot++) {
// Get the value stack-slot of the back edge.
MDefinition* exitDef = backedge->getSlot(slot);
// Get the value of the loop header.
MDefinition* loopDef = entryResumePoint()->getOperand(slot);
if (loopDef->block() != this) {
// If we are finishing a pending loop header, then we need to ensure
// that all operands are phis. This is usualy the case, except for
// object/arrays build with generators, in which case we share the
// same allocations across all blocks.
MOZ_ASSERT(loopDef->block()->id() < id());
MOZ_ASSERT(loopDef == exitDef);
continue;
}
// Phis are allocated by NewPendingLoopHeader.
MPhi* entryDef = loopDef->toPhi();
MOZ_ASSERT(entryDef->block() == this);
if (entryDef == exitDef) {
// If the exit def is the same as the entry def, make a redundant
// phi. Since loop headers have exactly two incoming edges, we
// know that that's just the first input.
//
// Note that we eliminate later rather than now, to avoid any
// weirdness around pending continue edges which might still hold
// onto phis.
exitDef = entryDef->getOperand(0);
}
if (!entryDef->addInputSlow(exitDef)) {
return false;
}
}
return true;
}
MTest* MBasicBlock::immediateDominatorBranch(BranchDirection* pdirection) {
*pdirection = FALSE_BRANCH;
if (numPredecessors() != 1) {
return nullptr;
}
MBasicBlock* dom = immediateDominator();
if (dom != getPredecessor(0)) {
return nullptr;
}
// Look for a trailing MTest branching to this block.
MInstruction* ins = dom->lastIns();
if (ins->isTest()) {
MTest* test = ins->toTest();
MOZ_ASSERT(test->ifTrue() == this || test->ifFalse() == this);
if (test->ifTrue() == this && test->ifFalse() == this) {
return nullptr;
}
*pdirection = (test->ifTrue() == this) ? TRUE_BRANCH : FALSE_BRANCH;
return test;
}
return nullptr;
}
void MBasicBlock::dumpStack(GenericPrinter& out) {
#ifdef DEBUG
out.printf(" %-3s %-16s %-6s %-10s\n", "#", "name", "copyOf", "first/next");
out.printf("-------------------------------------------\n");
for (uint32_t i = 0; i < stackPosition_; i++) {
out.printf(" %-3u", i);
out.printf(" %-16p\n", (void*)slots_[i]);
}
#endif
}
void MBasicBlock::dumpStack() {
Fprinter out(stderr);
dumpStack(out);
out.finish();
}
void MIRGraph::dump(GenericPrinter& out) {
#ifdef JS_JITSPEW
for (MBasicBlockIterator iter(begin()); iter != end(); iter++) {
iter->dump(out);
out.printf("\n");
}
#endif
}
void MIRGraph::dump() {
Fprinter out(stderr);
dump(out);
out.finish();
}
void MBasicBlock::dump(GenericPrinter& out) {
#ifdef JS_JITSPEW
out.printf("block%u:%s%s%s\n", id(), isLoopHeader() ? " (loop header)" : "",
unreachable() ? " (unreachable)" : "",
isMarked() ? " (marked)" : "");
if (MResumePoint* resume = entryResumePoint()) {
resume->dump(out);
}
for (MPhiIterator iter(phisBegin()); iter != phisEnd(); iter++) {
iter->dump(out);
}
for (MInstructionIterator iter(begin()); iter != end(); iter++) {
iter->dump(out);
}
#endif
}
void MBasicBlock::dump() {
Fprinter out(stderr);
dump(out);
out.finish();
}