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
#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/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;
}
// 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;
}
}
auto iter = testBlock->rbegin();
if (!iter->isTest()) {
return false;
}
MTest* test = iter->toTest();
// Unwrap boolean conversion performed through the '!!' idiom.
MInstruction* testOrNot = test;
bool hasOddNumberOfNots = false;
while (++iter != testBlock->rend()) {
if (iter->isNot()) {
// The MNot must only be used by |testOrNot|.
auto* notIns = iter->toNot();
if (testOrNot->getOperand(0) != notIns) {
return false;
}
if (!notIns->hasOneUse()) {
return false;
}
testOrNot = notIns;
hasOddNumberOfNots = !hasOddNumberOfNots;
} else {
// Fail if there are any other instructions than MNot.
return false;
}
}
// There's an odd number of MNot, so this can't be the '!!' idiom.
if (hasOddNumberOfNots) {
return false;
}
MOZ_ASSERT(testOrNot->isTest() || testOrNot->isNot());
MDefinition* testInput = testOrNot->getOperand(0);
if (!testInput->isPhi()) {
return false;
}
MPhi* phi = testInput->toPhi();
if (phi->block() != phiBlock) {
return false;
}
for (MUseIterator iter = phi->usesBegin(); iter != phi->usesEnd(); ++iter) {
MUse* use = *iter;
if (use->consumer() == testOrNot) {
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;
}
// Determine if value is directly or indirectly the test input.
static bool IsTestInputMaybeToBool(MTest* test, MDefinition* value) {
auto* input = test->input();
bool hasEvenNumberOfNots = true;
while (true) {
// Only accept if there's an even number of MNot.
if (input == value && hasEvenNumberOfNots) {
return true;
}
// Unwrap boolean conversion performed through the '!!' idiom.
if (input->isNot()) {
input = input->toNot()->input();
hasEvenNumberOfNots = !hasEvenNumberOfNots;
continue;
}
return false;
}
}
// 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;
}
/*
* Look for a diamond pattern:
*
* initialBlock
* / \
* trueBranch falseBranch
* \ /
* phiBlock
* |
* testBlock
*/
static bool IsDiamondPattern(MBasicBlock* initialBlock) {
MInstruction* ins = initialBlock->lastIns();
if (!ins->isTest()) {
return false;
}
MTest* initialTest = ins->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
if (trueBranch->numPredecessors() != 1 || trueBranch->numSuccessors() != 1) {
return false;
}
MBasicBlock* falseBranch = initialTest->ifFalse();
if (falseBranch->numPredecessors() != 1 ||
falseBranch->numSuccessors() != 1) {
return false;
}
MBasicBlock* phiBlock = trueBranch->getSuccessor(0);
if (phiBlock != falseBranch->getSuccessor(0)) {
return false;
}
if (phiBlock->numPredecessors() != 2) {
return false;
}
return true;
}
static bool MaybeFoldDiamondConditionBlock(MIRGraph& graph,
MBasicBlock* initialBlock) {
MOZ_ASSERT(IsDiamondPattern(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.
/*
* 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.
*/
MTest* initialTest = initialBlock->lastIns()->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
MBasicBlock* falseBranch = initialTest->ifFalse();
if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() ||
falseBranch->isLoopBackedge()) {
return true;
}
MBasicBlock* phiBlock = trueBranch->getSuccessor(0);
MBasicBlock* testBlock = phiBlock;
if (testBlock->numSuccessors() == 1) {
if (testBlock->isLoopBackedge()) {
return true;
}
testBlock = testBlock->getSuccessor(0);
if (testBlock->numPredecessors() != 1) {
return true;
}
}
MPhi* phi;
MTest* finalTest;
if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
return true;
}
MOZ_ASSERT(phi->numOperands() == 2);
// Make sure the test block does not have any outgoing loop backedges.
if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
return false;
}
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());
// Change the end of the block to a test that jumps directly to successors of
// testBlock, rather than to testBlock itself.
if (IsTestInputMaybeToBool(initialTest, 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;
}
}
if (IsTestInputMaybeToBool(initialTest, 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;
}
}
// 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;
}
/*
* Look for a triangle pattern:
*
* initialBlock
* / \
* trueBranch |
* \ /
* phiBlock+falseBranch
* |
* testBlock
*
* Or:
*
* initialBlock
* / \
* | falseBranch
* \ /
* phiBlock+trueBranch
* |
* testBlock
*/
static bool IsTrianglePattern(MBasicBlock* initialBlock) {
MInstruction* ins = initialBlock->lastIns();
if (!ins->isTest()) {
return false;
}
MTest* initialTest = ins->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
MBasicBlock* falseBranch = initialTest->ifFalse();
if (trueBranch->numSuccessors() == 1 &&
trueBranch->getSuccessor(0) == falseBranch) {
if (trueBranch->numPredecessors() != 1) {
return false;
}
if (falseBranch->numPredecessors() != 2) {
return false;
}
return true;
}
if (falseBranch->numSuccessors() == 1 &&
falseBranch->getSuccessor(0) == trueBranch) {
if (trueBranch->numPredecessors() != 2) {
return false;
}
if (falseBranch->numPredecessors() != 1) {
return false;
}
return true;
}
return false;
}
static bool MaybeFoldTriangleConditionBlock(MIRGraph& graph,
MBasicBlock* initialBlock) {
MOZ_ASSERT(IsTrianglePattern(initialBlock));
// Optimize the MIR graph to improve the code generated for boolean
// operations. A test like 'if (a && b)' normally requires three blocks, with
// a phi for the intermediate value. This can be improved to use no phi value.
/*
* Look for a triangle pattern:
*
* initialBlock
* / \
* trueBranch |
* \ /
* phiBlock+falseBranch
* |
* testBlock
*
* Or:
*
* initialBlock
* / \
* | falseBranch
* \ /
* phiBlock+trueBranch
* |
* 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.
*/
MTest* initialTest = initialBlock->lastIns()->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
MBasicBlock* falseBranch = initialTest->ifFalse();
if (initialBlock->isLoopBackedge() || trueBranch->isLoopBackedge() ||
falseBranch->isLoopBackedge()) {
return true;
}
MBasicBlock* phiBlock;
if (trueBranch->numSuccessors() == 1 &&
trueBranch->getSuccessor(0) == falseBranch) {
phiBlock = falseBranch;
} else {
MOZ_ASSERT(falseBranch->getSuccessor(0) == trueBranch);
phiBlock = trueBranch;
}
MBasicBlock* testBlock = phiBlock;
if (testBlock->numSuccessors() == 1) {
MOZ_ASSERT(!testBlock->isLoopBackedge());
testBlock = testBlock->getSuccessor(0);
if (testBlock->numPredecessors() != 1) {
return true;
}
}
MPhi* phi;
MTest* finalTest;
if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
return true;
}
MOZ_ASSERT(phi->numOperands() == 2);
// If the phi-operand doesn't match the initial input, we can't fold the test.
auto* phiInputForInitialBlock =
phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
if (!IsTestInputMaybeToBool(initialTest, phiInputForInitialBlock)) {
return true;
}
// Make sure the test block does not have any outgoing loop backedges.
if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
return false;
}
MDefinition* trueResult;
MDefinition* falseResult;
if (phiBlock == trueBranch) {
trueResult = phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
falseResult = phi->getOperand(phiBlock->indexForPredecessor(falseBranch));
} else {
trueResult = phi->getOperand(phiBlock->indexForPredecessor(trueBranch));
falseResult = phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
}
// OK, we found the desired pattern, now transform the graph.
// Remove the phi from phiBlock.
phiBlock->discardPhi(*phiBlock->phisBegin());
// Change the end of the block to a test that jumps directly to successors of
// testBlock, rather than to testBlock itself.
if (phiBlock == trueBranch) {
if (!UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
finalTest->ifTrue(), initialTest->ifFalse(),
testBlock)) {
return false;
}
} else if (IsTestInputMaybeToBool(initialTest, 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;
}
}
if (phiBlock == falseBranch) {
if (!UpdateTestSuccessors(graph.alloc(), initialBlock, initialTest->input(),
initialTest->ifTrue(), finalTest->ifFalse(),
testBlock)) {
return false;
}
} else if (IsTestInputMaybeToBool(initialTest, 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;
}
}
// 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;
}
static bool MaybeFoldConditionBlock(MIRGraph& graph,
MBasicBlock* initialBlock) {
if (IsDiamondPattern(initialBlock)) {
return MaybeFoldDiamondConditionBlock(graph, initialBlock);
}
if (IsTrianglePattern(initialBlock)) {
return MaybeFoldTriangleConditionBlock(graph, initialBlock);
}
return true;
}
static bool MaybeFoldTestBlock(MIRGraph& graph, MBasicBlock* initialBlock) {
// Handle test expressions on more than two inputs. For example
// |if ((x > 10) && (y > 20) && (z > 30)) { ... }|, which results in the below
// pattern.
//
// Look for the pattern:
// ┌─────────────────┐
// 1 │ 1 compare │
// ┌─────┤ 2 test compare1 │
// │ └──────┬──────────┘
// │ │0
// ┌───────▼─────────┐ │
// │ 3 compare │ │
// │ 4 test compare3 │ └──────────┐
// └──┬──────────┬───┘ │
// 1│ │0 │
// ┌──────────▼──────┐ │ │
// │ 5 compare │ └─────────┐ │
// │ 6 goto │ │ │
// └───────┬─────────┘ │ │
// │ │ │
// │ ┌──────────────────▼───────▼───────┐
// └───►│ 9 phi compare1 compare3 compare5 │
// │10 goto │
// └────────────────┬─────────────────┘
// │
// ┌────────▼────────┐
// │11 test phi9 │
// └─────┬─────┬─────┘
// 1│ │0
// ┌────────────┐ │ │ ┌─────────────┐
// │ TrueBranch │◄────┘ └─────►│ FalseBranch │
// └────────────┘ └─────────────┘
//
// And transform it to:
//
// ┌─────────────────┐
// 1 │ 1 compare │
// ┌───┤ 2 test compare1 │
// │ └──────────┬──────┘
// │ │0
// ┌───────▼─────────┐ │
// │ 3 compare │ │
// │ 4 test compare3 │ │
// └──┬─────────┬────┘ │
// 1│ │0 │
// ┌──────────▼──────┐ │ │
// │ 5 compare │ └──────┐ │
// │ 6 test compare5 │ │ │
// └────┬────────┬───┘ │ │
// 1│ │0 │ │
// ┌─────▼──────┐ │ ┌───▼──▼──────┐
// │ TrueBranch │ └─────────► FalseBranch │
// └────────────┘ └─────────────┘
auto* ins = initialBlock->lastIns();
if (!ins->isTest()) {
return true;
}
auto* initialTest = ins->toTest();
MBasicBlock* trueBranch = initialTest->ifTrue();
MBasicBlock* falseBranch = initialTest->ifFalse();
// MaybeFoldConditionBlock handles the case for two operands.
MBasicBlock* phiBlock;
if (trueBranch->numPredecessors() > 2) {
phiBlock = trueBranch;
} else if (falseBranch->numPredecessors() > 2) {
phiBlock = falseBranch;
} else {
return true;
}
MBasicBlock* testBlock = phiBlock;
if (testBlock->numSuccessors() == 1) {
if (testBlock->isLoopBackedge()) {
return true;
}
testBlock = testBlock->getSuccessor(0);
if (testBlock->numPredecessors() != 1) {
return true;
}
}
MOZ_ASSERT(!phiBlock->isLoopBackedge());
MPhi* phi = nullptr;
MTest* finalTest = nullptr;
if (!BlockIsSingleTest(phiBlock, testBlock, &phi, &finalTest)) {
return true;
}
MOZ_ASSERT(phiBlock->numPredecessors() == phi->numOperands());
// If the phi-operand doesn't match the initial input, we can't fold the test.
auto* phiInputForInitialBlock =
phi->getOperand(phiBlock->indexForPredecessor(initialBlock));
if (!IsTestInputMaybeToBool(initialTest, phiInputForInitialBlock)) {
return true;
}
MBasicBlock* newTestBlock = nullptr;
MDefinition* newTestInput = nullptr;
// The block of each phi operand must either end with a test instruction on
// that phi operand or it's the sole block which ends with a goto instruction.
for (size_t i = 0; i < phiBlock->numPredecessors(); i++) {
auto* pred = phiBlock->getPredecessor(i);
auto* operand = phi->getOperand(i);
// Each predecessor must end with either a test or goto instruction.
auto* lastIns = pred->lastIns();
if (lastIns->isGoto() && !newTestBlock) {
newTestBlock = pred;
newTestInput = operand;
} else if (lastIns->isTest()) {
if (!IsTestInputMaybeToBool(lastIns->toTest(), operand)) {
return true;
}
} else {
return true;
}
MOZ_ASSERT(!pred->isLoopBackedge());
}
// Ensure we found the single goto block.
if (!newTestBlock) {
return true;
}
// Make sure the test block does not have any outgoing loop backedges.
if (!SplitCriticalEdgesForBlock(graph, testBlock)) {
return false;
}
// OK, we found the desired pattern, now transform the graph.
// Remove the phi from phiBlock.
phiBlock->discardPhi(*phiBlock->phisBegin());
// Create the new test instruction.
if (!UpdateTestSuccessors(graph.alloc(), newTestBlock, newTestInput,
finalTest->ifTrue(), finalTest->ifFalse(),
testBlock)) {
return false;
}
// Update all test instructions to point to the final target.
while (phiBlock->numPredecessors()) {
mozilla::DebugOnly<size_t> oldNumPred = phiBlock->numPredecessors();
auto* pred = phiBlock->getPredecessor(0);
auto* test = pred->lastIns()->toTest();
if (test->ifTrue() == phiBlock) {
if (!UpdateTestSuccessors(graph.alloc(), pred, test->input(),
finalTest->ifTrue(), test->ifFalse(),
testBlock)) {
return false;
}
} else {
MOZ_ASSERT(test->ifFalse() == phiBlock);
if (!UpdateTestSuccessors(graph.alloc(), pred, test->input(),
test->ifTrue(), finalTest->ifFalse(),
testBlock)) {
return false;
}
}
// Ensure we've made progress.
MOZ_ASSERT(phiBlock->numPredecessors() + 1 == oldNumPred);
}
// 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 (PostorderIterator block(graph.poBegin()); block != graph.poEnd();
block++) {
if (!MaybeFoldConditionBlock(graph, *block)) {
return false;
}
if (!MaybeFoldTestBlock(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() != ResumeMode::ResumeAt) {
return;
}
jsbytecode* pc = rp->pc();
if (JSOp(*pc) == JSOp::JumpTarget) {
pc += JSOpLength_JumpTarget;
}
if (JSOp(*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 pass only replaces resume points which are
// trivially dead.
//
// 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::EliminateTriviallyDeadResumePointOperands(MIRGenerator* mir,
MIRGraph& graph) {
for (auto* block : graph) {
if (MResumePoint* rp = block->entryResumePoint()) {
if (!graph.alloc().ensureBallast()) {
return false;
}
::EliminateTriviallyDeadResumePointOperands(graph, rp);
}
}
return true;
}
// 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->