Source code

Revision control

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/IonAnalysis.h"
#include <algorithm>
#include <utility> // for ::std::pair
#include "jit/AliasAnalysis.h"
#include "jit/CompileInfo.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"
#include "util/CheckedArithmetic.h"
#include "vm/TraceLogging.h"
#include "vm/TraceLoggingTypes.h"
#include "vm/BytecodeUtil-inl.h"
using namespace js;
using namespace js::jit;
using mozilla::DebugOnly;
// Stack used by FlagPhiInputsAsImplicitlyUsed. It stores the Phi instruction
// pointer and the MUseIterator which should be visited next.
using MPhiUseIteratorStack =
Vector<std::pair<MPhi*, MUseIterator>, 16, SystemAllocPolicy>;
// Look for Phi uses with a depth-first search. If any uses are found the stack
// of MPhi instructions is returned in the |worklist| argument.
static bool DepthFirstSearchUse(MIRGenerator* mir,
MPhiUseIteratorStack& worklist, MPhi* phi) {
// Push a Phi and the next use to iterate over in the worklist.
auto push = [&worklist](MPhi* phi, MUseIterator use) -> bool {
phi->setInWorklist();
return worklist.append(std::make_pair(phi, use));
};
#ifdef DEBUG
// Used to assert that when we have no uses, we at least visited all the
// transitive uses.
size_t refUseCount = phi->useCount();
size_t useCount = 0;
#endif
MOZ_ASSERT(worklist.empty());
if (!push(phi, phi->usesBegin())) {
return false;
}
while (!worklist.empty()) {
// Resume iterating over the last phi-use pair added by the next loop.
auto pair = worklist.popCopy();
MPhi* producer = pair.first;
MUseIterator use = pair.second;
MUseIterator end(producer->usesEnd());
producer->setNotInWorklist();
// Keep going down the tree of uses, skipping (continue)
// non-observable/unused cases and Phi which are already listed in the
// worklist. Stop (return) as soon as one use is found.
while (use != end) {
MNode* consumer = (*use)->consumer();
MUseIterator it = use;
use++;
#ifdef DEBUG
useCount++;
#endif
if (mir->shouldCancel("FlagPhiInputsAsImplicitlyUsed inner loop")) {
return false;
}
if (consumer->isResumePoint()) {
MResumePoint* rp = consumer->toResumePoint();
// Observable operands are similar to potential uses.
if (rp->isObservableOperand(*it)) {
return push(producer, use);
}
continue;
}
MDefinition* cdef = consumer->toDefinition();
if (!cdef->isPhi()) {
// The producer is explicitly used by a definition.
return push(producer, use);
}
MPhi* cphi = cdef->toPhi();
if (cphi->getUsageAnalysis() == PhiUsage::Used ||
cphi->isImplicitlyUsed()) {
// The information got cached on the Phi the last time it
// got visited, or when flagging operands of implicitly used
// instructions.
return push(producer, use);
}
if (cphi->isInWorklist() || cphi == producer) {
// We are already iterating over the uses of this Phi instruction which
// are part of a loop, instead of trying to handle loops, conservatively
// mark them as used.
return push(producer, use);
}
if (cphi->getUsageAnalysis() == PhiUsage::Unused) {
// The instruction already got visited and is known to have
// no uses. Skip it.
continue;
}
// We found another Phi instruction, move the use iterator to
// the next use push it to the worklist stack. Then, continue
// with a depth search.
if (!push(producer, use)) {
return false;
}
producer = cphi;
use = producer->usesBegin();
end = producer->usesEnd();
#ifdef DEBUG
refUseCount += producer->useCount();
#endif
}
// When unused, we cannot bubble up this information without iterating
// over the rest of the previous Phi instruction consumers.
MOZ_ASSERT(use == end);
producer->setUsageAnalysis(PhiUsage::Unused);
}
MOZ_ASSERT(useCount == refUseCount);
return true;
}
static bool FlagPhiInputsAsImplicitlyUsed(MIRGenerator* mir, MBasicBlock* block,
MBasicBlock* succ,
MPhiUseIteratorStack& worklist) {
// When removing an edge between 2 blocks, we might remove the ability of
// later phases to figure out that the uses of a Phi should be considered as
// a use of all its inputs. Thus we need to mark the Phi inputs as being
// implicitly used iff the phi has any uses.
//
//
// +--------------------+ +---------------------+
// |12 MFoo 6 | |32 MBar 5 |
// | | | |
// | ... | | ... |
// | | | |
// |25 MGoto Block 4 | |43 MGoto Block 4 |
// +--------------------+ +---------------------+
// | |
// | | |
// | | |
// | +-----X------------------------+
// | Edge |
// | Removed |
// | |
// | +------------v-----------+
// | |50 MPhi 12 32 |
// | | |
// | | ... |
// | | |
// | |70 MReturn 50 |
// | +------------------------+
// |
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// |
// v
//
// ^ +--------------------+ +---------------------+
// /!\ |12 MConst opt-out | |32 MBar 5 |
// '---' | | | |
// | ... | | ... |
// |78 MBail | | |
// |80 MUnreachable | |43 MGoto Block 4 |
// +--------------------+ +---------------------+
// |
// |
// |
// +---------------+
// |
// |
// |
// +------------v-----------+
// |50 MPhi 32 |
// | |
// | ... |
// | |
// |70 MReturn 50 |
// +------------------------+
//
//
// If the inputs of the Phi are not flagged as implicitly used, then
// later compilation phase might optimize them out. The problem is that a
// bailout will use this value and give it back to baseline, which will then
// use the OptimizedOut magic value in a computation.
//
// Unfortunately, we cannot be too conservative about flagging Phi inputs as
// having implicit uses, as this would prevent many optimizations from being
// used. Thus, the following code is in charge of flagging Phi instructions
// as Unused or Used, and setting ImplicitlyUsed accordingly.
size_t predIndex = succ->getPredecessorIndex(block);
MPhiIterator end = succ->phisEnd();
MPhiIterator it = succ->phisBegin();
for (; it != end; it++) {
MPhi* phi = *it;
if (mir->shouldCancel("FlagPhiInputsAsImplicitlyUsed outer loop")) {
return false;
}
// We are looking to mark the Phi inputs which are used across the edge
// between the |block| and its successor |succ|.
MDefinition* def = phi->getOperand(predIndex);
if (def->isImplicitlyUsed()) {
continue;
}
// If the Phi is either Used or Unused, set the ImplicitlyUsed flag
// accordingly.
if (phi->getUsageAnalysis() == PhiUsage::Used || phi->isImplicitlyUsed()) {
def->setImplicitlyUsedUnchecked();
continue;
} else if (phi->getUsageAnalysis() == PhiUsage::Unused) {
continue;
}
// We do not know if the Phi was Used or Unused, iterate over all uses
// with a depth-search of uses. Returns the matching stack in the
// worklist as soon as one use is found.
MOZ_ASSERT(worklist.empty());
if (!DepthFirstSearchUse(mir, worklist, phi)) {
return false;
}
MOZ_ASSERT_IF(worklist.empty(),
phi->getUsageAnalysis() == PhiUsage::Unused);
if (!worklist.empty()) {
// One of the Phis is used, set Used flags on all the Phis which are
// in the use chain.
def->setImplicitlyUsedUnchecked();
do {
auto pair = worklist.popCopy();
MPhi* producer = pair.first;
producer->setUsageAnalysis(PhiUsage::Used);
producer->setNotInWorklist();
} while (!worklist.empty());
}
MOZ_ASSERT(phi->getUsageAnalysis() != PhiUsage::Unknown);
}
return true;
}
static MInstructionIterator FindFirstInstructionAfterBail(MBasicBlock* block) {
MOZ_ASSERT(block->alwaysBails());
for (MInstructionIterator it = block->begin(); it != block->end(); it++) {
MInstruction* ins = *it;
if (ins->isBail()) {
it++;
return it;
}
}
MOZ_CRASH("Expected MBail in alwaysBails block");
}
// Given an iterator pointing to the first removed instruction, mark
// the operands of each removed instruction as having implicit uses.
static bool FlagOperandsAsImplicitlyUsedAfter(
MIRGenerator* mir, MBasicBlock* block, MInstructionIterator firstRemoved) {
MOZ_ASSERT(firstRemoved->block() == block);
const CompileInfo& info = block->info();
// Flag operands of removed instructions as having implicit uses.
MInstructionIterator end = block->end();
for (MInstructionIterator it = firstRemoved; it != end; it++) {
if (mir->shouldCancel("FlagOperandsAsImplicitlyUsedAfter (loop 1)")) {
return false;
}
MInstruction* ins = *it;
for (size_t i = 0, e = ins->numOperands(); i < e; i++) {
ins->getOperand(i)->setImplicitlyUsedUnchecked();
}
// Flag observable resume point operands as having implicit uses.
if (MResumePoint* rp = ins->resumePoint()) {
// Note: no need to iterate over the caller's of the resume point as
// this is the same as the entry resume point.
MOZ_ASSERT(&rp->block()->info() == &info);
for (size_t i = 0, e = rp->numOperands(); i < e; i++) {
if (info.isObservableSlot(i)) {
rp->getOperand(i)->setImplicitlyUsedUnchecked();
}
}
}
}
// Flag Phi inputs of the successors as having implicit uses.
MPhiUseIteratorStack worklist;
for (size_t i = 0, e = block->numSuccessors(); i < e; i++) {
if (mir->shouldCancel("FlagOperandsAsImplicitlyUsedAfter (loop 2)")) {
return false;
}
if (!FlagPhiInputsAsImplicitlyUsed(mir, block, block->getSuccessor(i),
worklist)) {
return false;
}
}
return true;
}
static bool FlagEntryResumePointOperands(MIRGenerator* mir,
MBasicBlock* block) {
// Flag observable operands of the entry resume point as having implicit uses.
MResumePoint* rp = block->entryResumePoint();
while (rp) {
if (mir->shouldCancel("FlagEntryResumePointOperands")) {
return false;
}
const CompileInfo& info = rp->block()->info();
for (size_t i = 0, e = rp->numOperands(); i < e; i++) {
if (info.isObservableSlot(i)) {
rp->getOperand(i)->setImplicitlyUsedUnchecked();
}
}
rp = rp->caller();
}
return true;
}
static bool FlagAllOperandsAsImplicitlyUsed(MIRGenerator* mir,
MBasicBlock* block) {
return FlagEntryResumePointOperands(mir, block) &&
FlagOperandsAsImplicitlyUsedAfter(mir, block, block->begin());
}
// WarpBuilder sets the alwaysBails flag on blocks that contain an
// unconditional bailout. We trim any instructions in those blocks
// after the first unconditional bailout, and remove any blocks that
// are only reachable through bailing blocks.
bool jit::PruneUnusedBranches(MIRGenerator* mir, MIRGraph& graph) {
JitSpew(JitSpew_Prune, "Begin");
// Pruning is guided by unconditional bailouts. Wasm does not have bailouts.
MOZ_ASSERT(!mir->compilingWasm());
Vector<MBasicBlock*, 16, SystemAllocPolicy> worklist;
uint32_t numMarked = 0;
bool needsTrim = false;
auto markReachable = [&](MBasicBlock* block) -> bool {
block->mark();
numMarked++;
if (block->alwaysBails()) {
needsTrim = true;
}
return worklist.append(block);
};
// The entry block is always reachable.
if (!markReachable(graph.entryBlock())) {
return false;
}
// The OSR entry block is always reachable if it exists.
if (graph.osrBlock() && !markReachable(graph.osrBlock())) {
return false;
}
// Iteratively mark all reachable blocks.
while (!worklist.empty()) {
if (mir->shouldCancel("Prune unused branches (marking reachable)")) {
return false;
}
MBasicBlock* block = worklist.popCopy();
JitSpew(JitSpew_Prune, "Visit block %u:", block->id());
JitSpewIndent indent(JitSpew_Prune);
// If this block always bails, then it does not reach its successors.
if (block->alwaysBails()) {
continue;
}
for (size_t i = 0; i < block->numSuccessors(); i++) {
MBasicBlock* succ = block->getSuccessor(i);
if (succ->isMarked()) {
continue;
}
JitSpew(JitSpew_Prune, "Reaches block %u", succ->id());
if (!markReachable(succ)) {
return false;
}
}
}
if (!needsTrim && numMarked == graph.numBlocks()) {
// There is nothing to prune.
graph.unmarkBlocks();
return true;
}
JitSpew(JitSpew_Prune, "Remove unreachable instructions and blocks:");
JitSpewIndent indent(JitSpew_Prune);
// The operands of removed instructions may be needed in baseline
// after bailing out.
for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
if (mir->shouldCancel("Prune unused branches (marking operands)")) {
return false;
}
MBasicBlock* block = *it++;
if (!block->isMarked()) {
// If we are removing the block entirely, mark the operands of every
// instruction as being implicitly used.
FlagAllOperandsAsImplicitlyUsed(mir, block);
} else if (block->alwaysBails()) {
// If we are only trimming instructions after a bail, only mark operands
// of removed instructions.
MInstructionIterator firstRemoved = FindFirstInstructionAfterBail(block);
FlagOperandsAsImplicitlyUsedAfter(mir, block, firstRemoved);
}
}
// Remove the blocks in post-order such that consumers are visited before
// the predecessors, the only exception being the Phi nodes of loop headers.
for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
if (mir->shouldCancel("Prune unused branches (removal loop)")) {
return false;
}
if (!graph.alloc().ensureBallast()) {
return false;
}
MBasicBlock* block = *it++;
if (block->isMarked() && !block->alwaysBails()) {
continue;
}
// As we are going to replace/remove the last instruction, we first have
// to remove this block from the predecessor list of its successors.
size_t numSucc = block->numSuccessors();
for (uint32_t i = 0; i < numSucc; i++) {
MBasicBlock* succ = block->getSuccessor(i);
if (succ->isDead()) {
continue;
}
// Our dominators code expects all loop headers to have two predecessors.
// If we are removing the normal entry to a loop, but can still reach
// the loop header via OSR, we create a fake unreachable predecessor.
if (succ->isLoopHeader() && block != succ->backedge()) {
MOZ_ASSERT(graph.osrBlock());
if (!graph.alloc().ensureBallast()) {
return false;
}
MBasicBlock* fake = MBasicBlock::NewFakeLoopPredecessor(graph, succ);
if (!fake) {
return false;
}
// Mark the block to avoid removing it as unreachable.
fake->mark();
JitSpew(JitSpew_Prune,
"Header %u only reachable by OSR. Add fake predecessor %u",
succ->id(), fake->id());
}
JitSpew(JitSpew_Prune, "Remove block edge %u -> %u.", block->id(),
succ->id());
succ->removePredecessor(block);
}
if (!block->isMarked()) {
// Remove unreachable blocks from the CFG.
JitSpew(JitSpew_Prune, "Remove block %u.", block->id());
graph.removeBlock(block);
} else {
// Remove unreachable instructions after unconditional bailouts.
JitSpew(JitSpew_Prune, "Trim block %u.", block->id());
// Discard all instructions after the first MBail.
MInstructionIterator firstRemoved = FindFirstInstructionAfterBail(block);
block->discardAllInstructionsStartingAt(firstRemoved);
if (block->outerResumePoint()) {
block->clearOuterResumePoint();
}
block->end(MUnreachable::New(graph.alloc()));
}
}
graph.unmarkBlocks();
return true;
}
static bool SplitCriticalEdgesForBlock(MIRGraph& graph, MBasicBlock* block) {
if (block->numSuccessors() < 2) {
return true;
}
for (size_t i = 0; i < block->numSuccessors(); i++) {
MBasicBlock* target = block->getSuccessor(i);
if (target->numPredecessors() < 2) {
continue;
}
// Create a simple new block which contains a goto and which split the
// edge between block and target.
MBasicBlock* split = MBasicBlock::NewSplitEdge(graph, block, i, target);
if (!split) {
return false;
}
}
return true;
}
// A critical edge is an edge which is neither its successor's only predecessor
// nor its predecessor's only successor. Critical edges must be split to
// prevent copy-insertion and code motion from affecting other edges.
bool jit::SplitCriticalEdges(MIRGraph& graph) {
for (MBasicBlockIterator iter(graph.begin()); iter != graph.end(); iter++) {
MBasicBlock* block = *iter;
if (!SplitCriticalEdgesForBlock(graph, block)) {
return false;
}
}
return true;
}
bool jit::IsUint32Type(const MDefinition* def) {
if (def->isBeta()) {
def = def->getOperand(0);
}
if (def->type() != MIRType::Int32) {
return false;
}
return def->isUrsh() && def->getOperand(1)->isConstant() &&
def->getOperand(1)->toConstant()->type() == MIRType::Int32 &&
def->getOperand(1)->toConstant()->toInt32() == 0;
}
// Return whether a block simply computes the specified constant value.
static bool BlockComputesConstant(MBasicBlock* block, MDefinition* value,
bool* constBool) {
// Look for values with no uses. This is used to eliminate constant
// computing blocks in condition statements, and the phi which used to
// consume the constant has already been removed.
if (value->hasUses()) {
return false;
}
if (!value->isConstant() || value->block() != block) {
return false;
}
if (!block->phisEmpty()) {
return false;
}
for (MInstructionIterator iter = block->begin(); iter != block->end();
++iter) {
if (*iter != value || !iter->isGoto()) {
return false;
}
}
return value->toConstant()->valueToBoolean(constBool);
}
// Determine whether phiBlock/testBlock simply compute a phi and perform a
// test on it.
static bool BlockIsSingleTest(MBasicBlock* phiBlock, MBasicBlock* testBlock,
MPhi** pphi, MTest** ptest) {
*pphi = nullptr;
*ptest = nullptr;
if (phiBlock != testBlock) {
MOZ_ASSERT(phiBlock->numSuccessors() == 1 &&
phiBlock->getSuccessor(0) == testBlock);
if (!phiBlock->begin()->isGoto()) {
return false;
}
}
MInstruction* ins = *testBlock->begin();
if (!ins->isTest()) {
return false;
}
MTest* test = ins->toTest();
if (!test->input()->isPhi()) {
return false;
}
MPhi* phi = test->input()->toPhi();
if (phi->block() != phiBlock) {
return false;
}
for (MUseIterator iter = phi->usesBegin(); iter != phi->usesEnd(); ++iter) {
MUse* use = *iter;
if (use->consumer() == test) {
continue;
}
if (use->consumer()->isResumePoint()) {
MBasicBlock* useBlock = use->consumer()->block();
if (useBlock == phiBlock || useBlock == testBlock) {
continue;
}
}
return false;
}
for (MPhiIterator iter = phiBlock->phisBegin(); iter != phiBlock->phisEnd();
++iter) {
if (*iter != phi) {
return false;
}
}
if (phiBlock != testBlock && !testBlock->phisEmpty()) {
return false;
}
*pphi = phi;
*ptest = test;
return true;
}
// Change block so that it ends in a goto to the specific target block.
// existingPred is an existing predecessor of the block.
[[nodiscard]] static bool UpdateGotoSuccessor(TempAllocator& alloc,
MBasicBlock* block,
MBasicBlock* target,
MBasicBlock* existingPred) {
MInstruction* ins = block->lastIns();
MOZ_ASSERT(ins->isGoto());
ins->toGoto()->target()->removePredecessor(block);
block->discardLastIns();
MGoto* newGoto = MGoto::New(alloc, target);
block->end(newGoto);
return target->addPredecessorSameInputsAs(block, existingPred);
}
// Change block so that it ends in a test of the specified value, going to
// either ifTrue or ifFalse. existingPred is an existing predecessor of ifTrue
// or ifFalse with the same values incoming to ifTrue/ifFalse as block.
// existingPred is not required to be a predecessor of ifTrue/ifFalse if block
// already ends in a test going to that block on a true/false result.
[[nodiscard]] static bool UpdateTestSuccessors(
TempAllocator& alloc, MBasicBlock* block, MDefinition* value,
MBasicBlock* ifTrue, MBasicBlock* ifFalse, MBasicBlock* existingPred) {
MInstruction* ins = block->lastIns();
if (ins->isTest()) {
MTest* test = ins->toTest();
MOZ_ASSERT(test->input() == value);
if (ifTrue != test->ifTrue()) {
test->ifTrue()->removePredecessor(block);
if (!ifTrue->addPredecessorSameInputsAs(block, existingPred)) {
return false;
}
MOZ_ASSERT(test->ifTrue() == test->getSuccessor(0));
test->replaceSuccessor(0, ifTrue);
}
if (ifFalse != test->ifFalse()) {
test->ifFalse()->removePredecessor(block);
if (!ifFalse->addPredecessorSameInputsAs(block, existingPred)) {
return false;
}
MOZ_ASSERT(test->ifFalse() == test->getSuccessor(1));
test->replaceSuccessor(1, ifFalse);
}
return true;
}
MOZ_ASSERT(ins->isGoto());
ins->toGoto()->target()->removePredecessor(block);
block->discardLastIns();
MTest* test = MTest::New(alloc, value, ifTrue, ifFalse);
block->end(test);
if (!ifTrue->addPredecessorSameInputsAs(block, existingPred)) {
return false;
}
if (!ifFalse->addPredecessorSameInputsAs(block, existingPred)) {
return false;
}
return true;
}
static bool MaybeFoldConditionBlock(MIRGraph& graph,
MBasicBlock* initialBlock) {
// Optimize the MIR graph to improve the code generated for conditional
// operations. A test like 'if (a ? b : c)' normally requires four blocks,
// with a phi for the intermediate value. This can be improved to use three
// blocks with no phi value, and if either b or c is constant,
// e.g. 'if (a ? b : 0)', then the block associated with that constant
// can be eliminated.
/*
* Look for a diamond pattern:
*
* initialBlock
* / \
* trueBranch falseBranch
* \ /
* phiBlock
* |
* testBlock
*
* Where phiBlock contains a single phi combining values pushed onto the
* stack by trueBranch and falseBranch, and testBlock contains a test on
* that phi. phiBlock and testBlock may be the same block; generated code
* will use different blocks if the (?:) op is in an inlined function.
*/
MInstruction* ins = initialBlock->lastIns();
if (!ins->isTest()) {
return true;
}
MTest* initialTest = ins->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
if (trueBranch->numPredecessors() != 1 || trueBranch->numSuccessors() != 1) {
return true;
}
MBasicBlock* falseBranch = initialTest->ifFalse();
if (falseBranch->numPredecessors() != 1 ||
falseBranch->numSuccessors() != 1) {
return true;
}
MBasicBlock* phiBlock = trueBranch->getSuccessor(0);
if (phiBlock != falseBranch->getSuccessor(0)) {
return true;
}
if (phiBlock->numPredecessors() != 2) {
return true;
}
if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() ||
falseBranch->isLoopBackedge()) {
return true;
}
MBasicBlock* testBlock = phiBlock;
if (testBlock->numSuccessors() == 1) {
if (testBlock->isLoopBackedge()) {
return true;
}
testBlock = testBlock->getSuccessor(0);
if (testBlock->numPredecessors() != 1) {
return true;
}
}
// Make sure the test block does not have any outgoing loop backedges.
if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
return false;
}
MPhi* phi;
MTest* finalTest;
if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
return true;
}
MDefinition* trueResult =
phi->getOperand(phiBlock->indexForPredecessor(trueBranch));
MDefinition* falseResult =
phi->getOperand(phiBlock->indexForPredecessor(falseBranch));
// OK, we found the desired pattern, now transform the graph.
// Remove the phi from phiBlock.
phiBlock->discardPhi(*phiBlock->phisBegin());
// If either trueBranch or falseBranch just computes a constant for the
// test, determine the block that branch will end up jumping to and eliminate
// the branch. Otherwise, change the end of the block to a test that jumps
// directly to successors of testBlock, rather than to testBlock itself.
MBasicBlock* trueTarget = trueBranch;
bool constBool;
if (BlockComputesConstant(trueBranch, trueResult, &constBool)) {
trueTarget = constBool ? finalTest->ifTrue() : finalTest->ifFalse();
phiBlock->removePredecessor(trueBranch);
graph.removeBlock(trueBranch);
} else if (initialTest->input() == trueResult) {
if (!UpdateGotoSuccessor(graph.alloc(), trueBranch, finalTest->ifTrue(),
testBlock)) {
return false;
}
} else {
if (!UpdateTestSuccessors(graph.alloc(), trueBranch, trueResult,
finalTest->ifTrue(), finalTest->ifFalse(),
testBlock)) {
return false;
}
}
MBasicBlock* falseTarget = falseBranch;
if (BlockComputesConstant(falseBranch, falseResult, &constBool)) {
falseTarget = constBool ? finalTest->ifTrue() : finalTest->ifFalse();
phiBlock->removePredecessor(falseBranch);
graph.removeBlock(falseBranch);
} else if (initialTest->input() == falseResult) {
if (!UpdateGotoSuccessor(graph.alloc(), falseBranch, finalTest->ifFalse(),
testBlock)) {
return false;
}
} else {
if (!UpdateTestSuccessors(graph.alloc(), falseBranch, falseResult,
finalTest->ifTrue(), finalTest->ifFalse(),
testBlock)) {
return false;
}
}
// Short circuit the initial test to skip any constant branch eliminated
// above.
if (!UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
trueTarget, falseTarget, testBlock)) {
return false;
}
// Remove phiBlock, if different from testBlock.
if (phiBlock != testBlock) {
testBlock->removePredecessor(phiBlock);
graph.removeBlock(phiBlock);
}
// Remove testBlock itself.
finalTest->ifTrue()->removePredecessor(testBlock);
finalTest->ifFalse()->removePredecessor(testBlock);
graph.removeBlock(testBlock);
return true;
}
bool jit::FoldTests(MIRGraph& graph) {
for (MBasicBlockIterator block(graph.begin()); block != graph.end();
block++) {
if (!MaybeFoldConditionBlock(graph, *block)) {
return false;
}
}
return true;
}
bool jit::FoldEmptyBlocks(MIRGraph& graph) {
for (MBasicBlockIterator iter(graph.begin()); iter != graph.end();) {
MBasicBlock* block = *iter;
iter++;
if (block->numPredecessors() != 1 || block->numSuccessors() != 1) {
continue;
}
if (!block->phisEmpty()) {
continue;
}
if (block->outerResumePoint()) {
continue;
}
if (*block->begin() != *block->rbegin()) {
continue;
}
MBasicBlock* succ = block->getSuccessor(0);
MBasicBlock* pred = block->getPredecessor(0);
if (succ->numPredecessors() != 1) {
continue;
}
size_t pos = pred->getSuccessorIndex(block);
pred->lastIns()->replaceSuccessor(pos, succ);
graph.removeBlock(block);
if (!succ->addPredecessorSameInputsAs(pred, block)) {
return false;
}
succ->removePredecessor(block);
}
return true;
}
static void EliminateTriviallyDeadResumePointOperands(MIRGraph& graph,
MResumePoint* rp) {
// If we will pop the top of the stack immediately after resuming,
// then don't preserve the top value in the resume point.
if (rp->mode() != MResumePoint::ResumeAt || JSOp(*rp->pc()) != JSOp::Pop) {
return;
}
size_t top = rp->stackDepth() - 1;
MOZ_ASSERT(!rp->isObservableOperand(top));
MDefinition* def = rp->getOperand(top);
if (def->isConstant()) {
return;
}
MConstant* constant = rp->block()->optimizedOutConstant(graph.alloc());
rp->replaceOperand(top, constant);
}
// Operands to a resume point which are dead at the point of the resume can be
// replaced with a magic value. This analysis supports limited detection of
// dead operands, pruning those which are defined in the resume point's basic
// block and have no uses outside the block or at points later than the resume
// point.
//
// This is intended to ensure that extra resume points within a basic block
// will not artificially extend the lifetimes of any SSA values. This could
// otherwise occur if the new resume point captured a value which is created
// between the old and new resume point and is dead at the new resume point.
bool jit::EliminateDeadResumePointOperands(MIRGenerator* mir, MIRGraph& graph) {
// If we are compiling try blocks, locals and arguments may be observable
// from catch or finally blocks (which Ion does not compile). For now just
// disable the pass in this case.
if (graph.hasTryBlock()) {
return true;
}
for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
block++) {
if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)")) {
return false;
}
if (MResumePoint* rp = block->entryResumePoint()) {
if (!graph.alloc().ensureBallast()) {
return false;
}
EliminateTriviallyDeadResumePointOperands(graph, rp);
}
// The logic below can get confused on infinite loops.
if (block->isLoopHeader() && block->backedge() == *block) {
continue;
}
for (MInstructionIterator ins = block->begin(); ins != block->end();
ins++) {
if (MResumePoint* rp = ins->resumePoint()) {
if (!graph.alloc().ensureBallast()) {
return false;
}
EliminateTriviallyDeadResumePointOperands(graph, rp);
}
// No benefit to replacing constant operands with other constants.
if (ins->isConstant()) {
continue;
}
// Scanning uses does not give us sufficient information to tell
// where instructions that are involved in box/unbox operations or
// parameter passing might be live. Rewriting uses of these terms
// in resume points may affect the interpreter's behavior. Rather
// than doing a more sophisticated analysis, just ignore these.
if (ins->isUnbox() || ins->isParameter() || ins->isBoxNonStrictThis()) {
continue;
}
// Early intermediate values captured by resume points, such as
// ArrayState and its allocation, may be legitimately dead in Ion code,
// but are still needed if we bail out. They can recover on bailout.
if (ins->isRecoveredOnBailout()) {
MOZ_ASSERT(ins->canRecoverOnBailout());
continue;
}
// If the instruction's behavior has been constant folded into a
// separate instruction, we can't determine precisely where the
// instruction becomes dead and can't eliminate its uses.
if (ins->isImplicitlyUsed()) {
continue;
}
// Check if this instruction's result is only used within the
// current block, and keep track of its last use in a definition
// (not resume point). This requires the instructions in the block
// to be numbered, ensured by running this immediately after alias
// analysis.
uint32_t maxDefinition = 0;
for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd();
uses++) {
MNode* consumer = uses->consumer();
if (consumer->isResumePoint()) {
// If the instruction's is captured by one of the resume point, then
// it might be observed indirectly while the frame is live on the
// stack, so it has to be computed.
MResumePoint* resume = consumer->toResumePoint();
if (resume->isObservableOperand(*uses)) {
maxDefinition = UINT32_MAX;
break;
}
continue;
}
MDefinition* def = consumer->toDefinition();
if (def->block() != *block || def->isBox() || def->isPhi()) {
maxDefinition = UINT32_MAX;
break;
}
maxDefinition = std::max(maxDefinition, def->id());
}
if (maxDefinition == UINT32_MAX) {
continue;
}
// Walk the uses a second time, removing any in resume points after
// the last use in a definition.
for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd();) {
MUse* use = *uses++;
if (use->consumer()->isDefinition()) {
continue;
}
MResumePoint* mrp = use->consumer()->toResumePoint();
if (mrp->block() != *block || !mrp->instruction() ||
mrp->instruction() == *ins ||
mrp->instruction()->id() <= maxDefinition) {
continue;
}
if (!graph.alloc().ensureBallast()) {
return false;
}
// Store an optimized out magic value in place of all dead
// resume point operands. Making any such substitution can in
// general alter the interpreter's behavior, even though the
// code is dead, as the interpreter will still execute opcodes
// whose effects cannot be observed. If the magic value value
// were to flow to, say, a dead property access the
// interpreter could throw an exception; we avoid this problem
// by removing dead operands before removing dead code.
MConstant* constant =
MConstant::New(graph.alloc(), MagicValue(JS_OPTIMIZED_OUT));
block->insertBefore(*(block->begin()), constant);
use->replaceProducer(constant);
}
}
}
return true;
}
// Test whether |def| would be needed if it had no uses.
bool js::jit::DeadIfUnused(const MDefinition* def) {
// Effectful instructions of course cannot be removed.
if (def->isEffectful()) {
return false;
}
// Never eliminate guard instructions.
if (def->isGuard()) {
return false;
}
// Required to be preserved, as the type guard related to this instruction
// is part of the semantics of a transformation.
if (def->isGuardRangeBailouts()) {
return false;
}
// Control instructions have no uses, but also shouldn't be optimized out
if (def->isControlInstruction()) {
return false;
}
// Used when lowering to generate the corresponding snapshots and aggregate
// the list of recover instructions to be repeated.
if (def->isInstruction() && def->toInstruction()->resumePoint()) {
return false;
}
return true;
}
// Similar to DeadIfUnused(), but additionally allows effectful instructions.
bool js::jit::DeadIfUnusedAllowEffectful(const MDefinition* def) {
// Never eliminate guard instructions.
if (def->isGuard()) {
return false;
}
// Required to be preserved, as the type guard related to this instruction
// is part of the semantics of a transformation.
if (def->isGuardRangeBailouts()) {
return false;
}
// Control instructions have no uses, but also shouldn't be optimized out
if (def->isControlInstruction()) {
return false;
}
// Used when lowering to generate the corresponding snapshots and aggregate
// the list of recover instructions to be repeated.
if (def->isInstruction() && def->toInstruction()->resumePoint()) {
// All effectful instructions must have a resume point attached. We're
// allowing effectful instructions here, so we have to ignore any resume
// points if we want to consider effectful instructions as dead.
if (!def->isEffectful()) {
return false;
}
}
return true;
}
// Test whether |def| may be safely discarded, due to being dead or due to being
// located in a basic block which has itself been marked for discarding.
bool js::jit::IsDiscardable(const MDefinition* def) {
return !def->hasUses() && (DeadIfUnused(def) || def->block()->isMarked());
}
// Similar to IsDiscardable(), but additionally allows effectful instructions.
bool js::jit::IsDiscardableAllowEffectful(const MDefinition* def) {
return !def->hasUses() &&
(DeadIfUnusedAllowEffectful(def) || def->block()->isMarked());
}
// Instructions are useless if they are unused and have no side effects.
// This pass eliminates useless instructions.
// The graph itself is unchanged.
bool jit::EliminateDeadCode(MIRGenerator* mir, MIRGraph& graph) {
// Traverse in postorder so that we hit uses before definitions.
// Traverse instruction list backwards for the same reason.
for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
block++) {
if (mir->shouldCancel("Eliminate Dead Code (main loop)")) {
return false;
}
// Remove unused instructions.
for (MInstructionReverseIterator iter = block->rbegin();
iter != block->rend();) {
MInstruction* inst = *iter++;
if (js::jit::IsDiscardable(inst)) {
block->discard(inst);
}
}
}
return true;
}
static inline bool IsPhiObservable(MPhi* phi, Observability observe) {
// If the phi has uses which are not reflected in SSA, then behavior in the
// interpreter may be affected by removing the phi.
if (phi->isImplicitlyUsed()) {
return true;
}
// Check for uses of this phi node outside of other phi nodes.
// Note that, initially, we skip reading resume points, which we
// don't count as actual uses. If the only uses are resume points,
// then the SSA name is never consumed by the program. However,
// after optimizations have been performed, it's possible that the
// actual uses in the program have been (incorrectly) optimized
// away, so we must be more conservative and consider resume
// points as well.
for (MUseIterator iter(phi->usesBegin()); iter != phi->usesEnd(); iter++) {
MNode* consumer = iter->consumer();
if (consumer->isResumePoint()) {
MResumePoint* resume = consumer->toResumePoint();
if (observe == ConservativeObservability) {
return true;
}
if (resume->isObservableOperand(*iter)) {
return true;
}
} else {
MDefinition* def = consumer->toDefinition();
if (!def->isPhi()) {
return true;
}
}
}
return false;
}
// Handles cases like:
// x is phi(a, x) --> a
// x is phi(a, a) --> a
static inline MDefinition* IsPhiRedundant(MPhi* phi) {
MDefinition* first = phi->operandIfRedundant();
if (first == nullptr) {
return nullptr;
}
// Propagate the ImplicitlyUsed flag if |phi| is replaced with another phi.
if (phi->isImplicitlyUsed()) {
first->setImplicitlyUsedUnchecked();
}
return first;
}
bool jit::EliminatePhis(MIRGenerator* mir, MIRGraph& graph,
Observability observe) {
// Eliminates redundant or unobservable phis from the graph. A
// redundant phi is something like b = phi(a, a) or b = phi(a, b),
// both of which can be replaced with a. An unobservable phi is
// one that whose value is never used in the program.
//
// Note that we must be careful not to eliminate phis representing
// values that the interpreter will require later. When the graph
// is first constructed, we can be more aggressive, because there
// is a greater correspondence between the CFG and the bytecode.
// After optimizations such as GVN have been performed, however,
// the bytecode and CFG may not correspond as closely to one
// another. In that case, we must be more conservative. The flag
// |conservativeObservability| is used to indicate that eliminate
// phis is being run after some optimizations have been performed,
// and thus we should use more conservative rules about
// observability. The particular danger is that we can optimize
// away uses of a phi because we think they are not executable,
// but the foundation for that assumption is false TI information
// that will eventually be invalidated. Therefore, if
// |conservativeObservability| is set, we will consider any use
// from a resume point to be observable. Otherwise, we demand a
// use from an actual instruction.
Vector<MPhi*, 16, SystemAllocPolicy> worklist;
// Add all observable phis to a worklist. We use the "in worklist" bit to
// mean "this phi is live".
for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
block++) {
MPhiIterator iter = block->phisBegin();
while (iter != block->phisEnd()) {
MPhi* phi = *iter++;
if (mir->shouldCancel("Eliminate Phis (populate loop)")) {
return false;
}
// Flag all as unused, only observable phis would be marked as used
// when processed by the work list.
phi->setUnused();
// If the phi is redundant, remove it here.
if (MDefinition* redundant = IsPhiRedundant(phi)) {
phi->justReplaceAllUsesWith(redundant);
block->discardPhi(phi);
continue;
}
// Enqueue observable Phis.
if (IsPhiObservable(phi, observe)) {
phi->setInWorklist();
if (!worklist.append(phi)) {
return false;
}
}
}
}
// Iteratively mark all phis reachable from live phis.
while (!worklist.empty()) {
if (mir->shouldCancel("Eliminate Phis (worklist)")) {
return false;
}
MPhi* phi = worklist.popCopy();
MOZ_ASSERT(phi->isUnused());
phi->setNotInWorklist();
// The removal of Phis can produce newly redundant phis.
if (MDefinition* redundant = IsPhiRedundant(phi)) {
// Add to the worklist the used phis which are impacted.
for (MUseDefIterator it(phi); it; it++) {
if (it.def()->isPhi()) {
MPhi* use = it.def()->toPhi();
if (!use->isUnused()) {
use->setUnusedUnchecked();
use->setInWorklist();
if (!worklist.append(use)) {
return false;
}
}
}
}
phi->justReplaceAllUsesWith(redundant);
} else {
// Otherwise flag them as used.
phi->setNotUnused();
}
// The current phi is/was used, so all its operands are used.
for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
MDefinition* in = phi->getOperand(i);
if (!in->isPhi() || !in->isUnused() || in->isInWorklist()) {
continue;
}
in->setInWorklist();
if (!worklist.append(in->toPhi())) {
return false;
}
}
}
// Sweep dead phis.
for (PostorderIterator block = graph.poBegin(); block != graph.poEnd();
block++) {
MPhiIterator iter = block->phisBegin();
while (iter != block->phisEnd()) {
MPhi* phi = *iter++;
if (phi->isUnused()) {
if (!phi->optimizeOutAllUses(graph.alloc())) {
return false;
}
block->discardPhi(phi);
}
}
}
return true;
}
namespace {
// The type analysis algorithm inserts conversions and box/unbox instructions
// to make the IR graph well-typed for future passes.
//
// Phi adjustment: If a phi's inputs are all the same type, the phi is
// specialized to return that type.
//
// Input adjustment: Each input is asked to apply conversion operations to its
// inputs. This may include Box, Unbox, or other instruction-specific type
// conversion operations.
//
class TypeAnalyzer {
MIRGenerator* mir;
MIRGraph& graph;
Vector<MPhi*, 0, SystemAllocPolicy> phiWorklist_;
TempAllocator& alloc() const { return graph.alloc(); }
bool addPhiToWorklist(MPhi* phi) {
if (phi->isInWorklist()) {
return true;
}
if (!phiWorklist_.append(phi)) {
return false;
}
phi->setInWorklist();
return true;
}
MPhi* popPhi() {
MPhi* phi = phiWorklist_.popCopy();
phi->setNotInWorklist();
return phi;
}
[[nodiscard]] bool propagateAllPhiSpecializations();
bool respecialize(MPhi* phi, MIRType type);
bool propagateSpecialization(MPhi* phi);
bool specializePhis();
bool specializeOsrOnlyPhis();
void replaceRedundantPhi(MPhi* phi);
bool adjustPhiInputs(MPhi* phi);
bool adjustInputs(MDefinition* def);
bool insertConversions();
bool checkFloatCoherency();
bool graphContainsFloat32();
bool markPhiConsumers();
bool markPhiProducers();
bool specializeValidFloatOps();
bool tryEmitFloatOperations();
bool shouldSpecializeOsrPhis() const;
MIRType guessPhiType(MPhi* phi) const;
public:
TypeAnalyzer(MIRGenerator* mir, MIRGraph& graph) : mir(mir), graph(graph) {}
bool analyze();
};
} /* anonymous namespace */
bool TypeAnalyzer::shouldSpecializeOsrPhis() const {
// [SMDOC] OSR Phi Type Specialization
//
// Without special handling for OSR phis, we end up with unspecialized phis
// (MIRType::Value) in the loop (pre)header and other blocks, resulting in
// unnecessary boxing and unboxing in the loop body.
//
// To fix this, phi type specialization needs special code to deal with the
// OSR entry block. Recall that OSR results in the following basic block
// structure:
//
// +------------------+ +-----------------+
// | Code before loop | | OSR entry block |
// +------------------+ +-----------------+
// | |
// | |
// | +---------------+ |
// +---------> | OSR preheader | <---------+
// +---------------+
// |
// V
// +---------------+
// | Loop header |<-----+
// +---------------+ |
// | |
// ... |
// | |
// +---------------+ |
// | Loop backedge |------+
// +---------------+
//
// OSR phi specialization happens in three steps:
//
// (1) Specialize phis but ignore MOsrValue phi inputs. In other words,
// pretend the OSR entry block doesn't exist. See guessPhiType.
//
// (2) Once phi specialization is done, look at the types of loop header phis
// and add these types to the corresponding preheader phis. This way, the
// types of the preheader phis are based on the code before the loop and
// the code in the loop body. These are exactly the types we expect for
// the OSR Values. See the last part of TypeAnalyzer::specializePhis.
//
// (3) For type-specialized preheader phis, add guard/unbox instructions to
// the OSR entry block to guard the incoming Value indeed has this type.
// This happens in:
//
// * TypeAnalyzer::adjustPhiInputs: adds a fallible unbox for values that
// can be unboxed.
//
// * TypeAnalyzer::replaceRedundantPhi: adds a type guard for values that
// can't be unboxed (null/undefined/magic Values).
if (!mir->graph().osrBlock()) {
return false;
}
return !mir->outerInfo().hadSpeculativePhiBailout();
}
// Try to specialize this phi based on its non-cyclic inputs.
MIRType TypeAnalyzer::guessPhiType(MPhi* phi) const {
#ifdef DEBUG
// Check that different magic constants aren't flowing together. Ignore
// JS_OPTIMIZED_OUT, since an operand could be legitimately optimized
// away.
MIRType magicType = MIRType::None;
for (size_t i = 0; i < phi->numOperands(); i++) {
MDefinition* in = phi->getOperand(i);
if (in->type() == MIRType::MagicHole ||
in->type() == MIRType::MagicIsConstructing) {
if (magicType == MIRType::None) {
magicType = in->type();
}
MOZ_ASSERT(magicType == in->type());
}
}
#endif
MIRType type = MIRType::None;
bool convertibleToFloat32 = false;
bool hasOSRValueInput = false;
DebugOnly<bool> hasSpecializableInput = false;
for (size_t i = 0, e = phi->numOperands(); i < e; i++) {
MDefinition* in = phi->getOperand(i);
if (in->isPhi()) {
hasSpecializableInput = true;
if (!in->toPhi()->triedToSpecialize()) {
continue;
}
if (in->type() == MIRType::None) {
// The operand is a phi we tried to specialize, but we were
// unable to guess its type. propagateSpecialization will
// propagate the type to this phi when it becomes known.
continue;
}
}
// See shouldSpecializeOsrPhis comment. This is the first step mentioned
// there.
if (shouldSpecializeOsrPhis() && in->isOsrValue()) {
hasOSRValueInput = true;
hasSpecializableInput = true;
continue;
}
if (type == MIRType::None) {
type = in->type();