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/BranchPruning.h"
#include <utility> // for ::std::pair
#include "jit/IonAnalysis.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"
using namespace js;
using namespace js::jit;
// 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.
[[nodiscard]] static bool DepthFirstSearchUse(const 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;
}
[[nodiscard]] static bool FlagPhiInputsAsImplicitlyUsed(
const 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.
[[nodiscard]] static bool FlagOperandsAsImplicitlyUsedAfter(
const 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;
}
[[nodiscard]] static bool FlagEntryResumePointOperands(const 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;
}
[[nodiscard]] static bool FlagAllOperandsAsImplicitlyUsed(
const 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(const 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.
if (!FlagAllOperandsAsImplicitlyUsed(mir, block)) {
return false;
}
} else if (block->alwaysBails()) {
// If we are only trimming instructions after a bail, only mark operands
// of removed instructions.
MInstructionIterator firstRemoved = FindFirstInstructionAfterBail(block);
if (!FlagOperandsAsImplicitlyUsedAfter(mir, block, firstRemoved)) {
return false;
}
}
}
// 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;
}
// Remove all blocks not marked with isMarked(). Unmark all remaining blocks.
// Alias analysis dependencies may be invalid after calling this function.
bool jit::RemoveUnmarkedBlocks(const MIRGenerator* mir, MIRGraph& graph,
uint32_t numMarkedBlocks) {
if (numMarkedBlocks == graph.numBlocks()) {
// If all blocks are marked, no blocks need removal. Just clear the
// marks. We'll still need to update the dominator tree below though,
// since we may have removed edges even if we didn't remove any blocks.
graph.unmarkBlocks();
} else {
// As we are going to remove edges and basic blocks, we have to mark
// instructions which would be needed by baseline if we were to
// bailout.
for (PostorderIterator it(graph.poBegin()); it != graph.poEnd();) {
MBasicBlock* block = *it++;
if (block->isMarked()) {
continue;
}
if (!FlagAllOperandsAsImplicitlyUsed(mir, block)) {
return false;
}
}
// Find unmarked blocks and remove them.
for (ReversePostorderIterator iter(graph.rpoBegin());
iter != graph.rpoEnd();) {
MBasicBlock* block = *iter++;
if (block->isMarked()) {
block->unmark();
continue;
}
// The block is unreachable. Clear out the loop header flag, as
// we're doing the sweep of a mark-and-sweep here, so we no longer
// need to worry about whether an unmarked block is a loop or not.
if (block->isLoopHeader()) {
block->clearLoopHeader();
}
for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) {
block->getSuccessor(i)->removePredecessor(block);
}
graph.removeBlock(block);
}
}
// Renumber the blocks and update the dominator tree.
return AccountForCFGChanges(mir, graph, /*updateAliasAnalysis=*/false);
}