blob: 49ab8b662bfd3309a4232ec179387b14816599e4 [file] [log] [blame]
//===--- SimplifyCFG.cpp - Clean up the SIL CFG ---------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "sil-simplify-cfg"
#include "swift/AST/Module.h"
#include "swift/SIL/DebugUtils.h"
#include "swift/SIL/Dominance.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILModule.h"
#include "swift/SIL/SILUndef.h"
#include "swift/SIL/TerminatorUtils.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SILOptimizer/Analysis/ProgramTerminationAnalysis.h"
#include "swift/SILOptimizer/Analysis/SimplifyInstruction.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/BasicBlockOptUtils.h"
#include "swift/SILOptimizer/Utils/CFGOptUtils.h"
#include "swift/SILOptimizer/Utils/CastOptimizer.h"
#include "swift/SILOptimizer/Utils/ConstantFolding.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "swift/SILOptimizer/Utils/SILInliner.h"
#include "swift/SILOptimizer/Utils/SILOptFunctionBuilder.h"
#include "swift/SILOptimizer/Utils/SILSSAUpdater.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
using namespace swift;
STATISTIC(NumBlocksDeleted, "Number of unreachable blocks removed");
STATISTIC(NumBlocksMerged, "Number of blocks merged together");
STATISTIC(NumJumpThreads, "Number of jumps threaded");
STATISTIC(NumTermBlockSimplified, "Number of programterm block simplified");
STATISTIC(NumConstantFolded, "Number of terminators constant folded");
STATISTIC(NumDeadArguments, "Number of unused arguments removed");
STATISTIC(NumSROAArguments, "Number of aggregate argument levels split by "
"SROA");
//===----------------------------------------------------------------------===//
// CFG Simplification
//===----------------------------------------------------------------------===//
/// dominatorBasedSimplify iterates between dominator based simplification of
/// terminator branch condition values and cfg simplification. This is the
/// maximum number of iterations we run. The number is the maximum number of
/// iterations encountered when compiling the stdlib on April 2 2015.
///
static unsigned MaxIterationsOfDominatorBasedSimplify = 10;
namespace {
struct ThreadInfo;
class SimplifyCFG {
SILOptFunctionBuilder FuncBuilder;
SILFunction &Fn;
SILPassManager *PM;
// WorklistList is the actual list that we iterate over (for determinism).
// Slots may be null, which should be ignored.
SmallVector<SILBasicBlock *, 32> WorklistList;
// WorklistMap keeps track of which slot a BB is in, allowing efficient
// containment query, and allows efficient removal.
llvm::SmallDenseMap<SILBasicBlock *, unsigned, 32> WorklistMap;
// Keep track of loop headers - we don't want to jump-thread through them.
SmallPtrSet<SILBasicBlock *, 32> LoopHeaders;
// The cost (~ number of copied instructions) of jump threading per basic
// block. Used to prevent infinite jump threading loops.
llvm::SmallDenseMap<SILBasicBlock *, int, 8> JumpThreadingCost;
// Dominance and post-dominance info for the current function
DominanceInfo *DT = nullptr;
ConstantFolder ConstFolder;
// True if the function has a large amount of blocks. In this case we turn off
// some expensive optimizations.
bool isVeryLargeFunction = false;
void constFoldingCallback(SILInstruction *I) {
// If a terminal instruction gets constant folded (like cond_br), it
// enables further simplify-CFG optimizations.
if (isa<TermInst>(I))
addToWorklist(I->getParent());
}
bool ShouldVerify;
bool EnableJumpThread;
public:
SimplifyCFG(SILFunction &Fn, SILTransform &T, bool Verify,
bool EnableJumpThread)
: FuncBuilder(T), Fn(Fn), PM(T.getPassManager()),
ConstFolder(FuncBuilder, PM->getOptions().AssertConfig,
/* EnableDiagnostics */ false,
[&](SILInstruction *I) { constFoldingCallback(I); }),
ShouldVerify(Verify), EnableJumpThread(EnableJumpThread) {}
bool run();
bool simplifyBlockArgs() {
auto *DA = PM->getAnalysis<DominanceAnalysis>();
DT = DA->get(&Fn);
bool Changed = false;
for (SILBasicBlock &BB : Fn) {
Changed |= simplifyArgs(&BB);
}
DT = nullptr;
return Changed;
}
private:
void clearWorklist() {
WorklistMap.clear();
WorklistList.clear();
}
/// popWorklist - Return the next basic block to look at, or null if the
/// worklist is empty. This handles skipping over null entries in the
/// worklist.
SILBasicBlock *popWorklist() {
while (!WorklistList.empty())
if (auto *BB = WorklistList.pop_back_val()) {
WorklistMap.erase(BB);
return BB;
}
return nullptr;
}
/// addToWorklist - Add the specified block to the work list if it isn't
/// already present.
void addToWorklist(SILBasicBlock *BB) {
unsigned &Entry = WorklistMap[BB];
if (Entry != 0)
return;
WorklistList.push_back(BB);
Entry = WorklistList.size();
}
/// removeFromWorklist - Remove the specified block from the worklist if
/// present.
void removeFromWorklist(SILBasicBlock *BB) {
assert(BB && "Cannot add null pointer to the worklist");
auto It = WorklistMap.find(BB);
if (It == WorklistMap.end())
return;
// If the BB is in the worklist, null out its entry.
if (It->second) {
assert(WorklistList[It->second - 1] == BB && "Consistency error");
WorklistList[It->second - 1] = nullptr;
}
// Remove it from the map as well.
WorklistMap.erase(It);
if (LoopHeaders.count(BB))
LoopHeaders.erase(BB);
}
bool simplifyBlocks();
bool canonicalizeSwitchEnums();
bool simplifyThreadedTerminators();
bool dominatorBasedSimplifications(SILFunction &Fn, DominanceInfo *DT);
bool dominatorBasedSimplify(DominanceAnalysis *DA);
bool threadEdge(const ThreadInfo &ti);
/// Remove the basic block if it has no predecessors. Returns true
/// If the block was removed.
bool removeIfDead(SILBasicBlock *BB);
bool tryJumpThreading(BranchInst *BI);
bool tailDuplicateObjCMethodCallSuccessorBlocks();
bool simplifyAfterDroppingPredecessor(SILBasicBlock *BB);
bool addToWorklistAfterSplittingEdges(SILBasicBlock *BB);
bool simplifyBranchOperands(OperandValueArrayRef Operands);
bool simplifyBranchBlock(BranchInst *BI);
bool simplifyCondBrBlock(CondBranchInst *BI);
bool simplifyCheckedCastBranchBlock(CheckedCastBranchInst *CCBI);
bool simplifyCheckedCastValueBranchBlock(CheckedCastValueBranchInst *CCBI);
bool simplifyCheckedCastAddrBranchBlock(CheckedCastAddrBranchInst *CCABI);
bool simplifyTryApplyBlock(TryApplyInst *TAI);
bool simplifySwitchValueBlock(SwitchValueInst *SVI);
bool simplifyTermWithIdenticalDestBlocks(SILBasicBlock *BB);
bool simplifySwitchEnumUnreachableBlocks(SwitchEnumInst *SEI);
bool simplifySwitchEnumBlock(SwitchEnumInst *SEI);
bool simplifyUnreachableBlock(UnreachableInst *UI);
bool simplifyProgramTerminationBlock(SILBasicBlock *BB);
bool simplifyArgument(SILBasicBlock *BB, unsigned i);
bool simplifyArgs(SILBasicBlock *BB);
void findLoopHeaders();
bool simplifySwitchEnumOnObjcClassOptional(SwitchEnumInst *SEI);
};
} // end anonymous namespace
static SILValue getTerminatorCondition(TermInst *Term) {
if (auto *CondBr = dyn_cast<CondBranchInst>(Term))
return stripExpectIntrinsic(CondBr->getCondition());
if (auto *SEI = dyn_cast<SwitchEnumInst>(Term))
return SEI->getOperand();
return nullptr;
}
/// Is this basic block jump threadable.
static bool isThreadableBlock(SILBasicBlock *BB,
SmallPtrSetImpl<SILBasicBlock *> &LoopHeaders) {
auto TI = BB->getTerminator();
// We know how to handle cond_br and switch_enum.
if (!isa<CondBranchInst>(TI) &&
!isa<SwitchEnumInst>(TI))
return false;
if (LoopHeaders.count(BB))
return false;
unsigned Cost = 0;
for (auto &Inst : *BB) {
if (!Inst.isTriviallyDuplicatable())
return false;
// Don't jumpthread function calls.
if (FullApplySite::isa(&Inst))
return false;
// Only thread 'small blocks'.
if (instructionInlineCost(Inst) != InlineCost::Free)
if (++Cost == 4)
return false;
}
return true;
}
namespace {
/// A description of an edge leading to a conditionally branching (or switching)
/// block and the successor block to thread to.
///
/// Src:
/// br Dest
/// \
/// \ Edge
/// v
/// Dest:
/// ...
/// switch/cond_br
/// / \
/// ... v
/// EnumCase/ThreadedSuccessorIdx
struct ThreadInfo {
SILBasicBlock *Src;
SILBasicBlock *Dest;
EnumElementDecl *EnumCase;
unsigned ThreadedSuccessorIdx;
ThreadInfo(SILBasicBlock *Src, SILBasicBlock *Dest,
unsigned ThreadedBlockSuccessorIdx)
: Src(Src), Dest(Dest), EnumCase(nullptr),
ThreadedSuccessorIdx(ThreadedBlockSuccessorIdx) {}
ThreadInfo(SILBasicBlock *Src, SILBasicBlock *Dest, EnumElementDecl *EnumCase)
: Src(Src), Dest(Dest), EnumCase(EnumCase), ThreadedSuccessorIdx(0) {}
ThreadInfo() = default;
};
} // end anonymous namespace
// FIXME: It would be far more efficient to clone the jump-threaded region using
// a single invocation of the RegionCloner (see ArrayPropertyOpt) instead of a
// BasicBlockCloner. Cloning a single block at a time forces the cloner to
// create four extra blocks that immediately become dead after the conditional
// branch and its clone is converted to an unconditional branch.
bool SimplifyCFG::threadEdge(const ThreadInfo &ti) {
LLVM_DEBUG(llvm::dbgs() << "thread edge from bb" << ti.Src->getDebugID()
<< " to bb" << ti.Dest->getDebugID() << '\n');
auto *SrcTerm = cast<BranchInst>(ti.Src->getTerminator());
BasicBlockCloner Cloner(SrcTerm->getDestBB());
if (!Cloner.canCloneBlock())
return false;
Cloner.cloneBranchTarget(SrcTerm);
// We have copied the threaded block into the edge.
auto *clonedSrc = Cloner.getNewBB();
SmallVector<SILBasicBlock *, 4> clonedSuccessors(
clonedSrc->getSuccessorBlocks().begin(),
clonedSrc->getSuccessorBlocks().end());
SILBasicBlock *ThreadedSuccessorBlock = nullptr;
// Rewrite the cloned branch to eliminate the non-taken path.
if (auto *CondTerm = dyn_cast<CondBranchInst>(clonedSrc->getTerminator())) {
// We know the direction this conditional branch is going to take thread
// it.
assert(clonedSrc->getSuccessors().size() > ti.ThreadedSuccessorIdx
&& "Threaded terminator does not have enough successors");
ThreadedSuccessorBlock =
clonedSrc->getSuccessors()[ti.ThreadedSuccessorIdx].getBB();
auto Args = ti.ThreadedSuccessorIdx == 0 ? CondTerm->getTrueArgs()
: CondTerm->getFalseArgs();
SILBuilderWithScope(CondTerm).createBranch(CondTerm->getLoc(),
ThreadedSuccessorBlock, Args);
CondTerm->eraseFromParent();
} else {
// Get the enum element and the destination block of the block we jump
// thread.
auto *SEI = cast<SwitchEnumInst>(clonedSrc->getTerminator());
ThreadedSuccessorBlock = SEI->getCaseDestination(ti.EnumCase);
// Instantiate the payload if necessary.
SILBuilderWithScope Builder(SEI);
if (!ThreadedSuccessorBlock->args_empty()) {
auto EnumVal = SEI->getOperand();
auto EnumTy = EnumVal->getType();
auto Loc = SEI->getLoc();
auto Ty = EnumTy.getEnumElementType(ti.EnumCase, SEI->getModule(),
Builder.getTypeExpansionContext());
SILValue UED(
Builder.createUncheckedEnumData(Loc, EnumVal, ti.EnumCase, Ty));
assert(UED->getType()
== (*ThreadedSuccessorBlock->args_begin())->getType()
&& "Argument types must match");
Builder.createBranch(SEI->getLoc(), ThreadedSuccessorBlock, {UED});
} else {
Builder.createBranch(SEI->getLoc(), ThreadedSuccessorBlock,
ArrayRef<SILValue>());
}
SEI->eraseFromParent();
}
// If the jump-threading target "Dest" had multiple predecessors, then the
// cloner will have created unconditional branch predecessors, which can
// now be removed or folded after converting the source block "Src" to an
// unconditional branch.
for (auto *succBB : clonedSuccessors) {
removeIfDead(succBB);
}
if (auto *branchInst =
dyn_cast<BranchInst>(ThreadedSuccessorBlock->getTerminator())) {
simplifyBranchBlock(branchInst);
}
Cloner.updateSSAAfterCloning();
return true;
}
/// Give a cond_br or switch_enum instruction and one successor block return
/// true if we can infer the value of the condition/enum along the edge to this
/// successor blocks.
static bool isKnownEdgeValue(TermInst *Term, SILBasicBlock *SuccBB,
EnumElementDecl *&EnumCase) {
assert((isa<CondBranchInst>(Term) || isa<SwitchEnumInst>(Term)) &&
"Expect a cond_br or switch_enum");
if (auto *SEI = dyn_cast<SwitchEnumInst>(Term)) {
if (auto Case = SEI->getUniqueCaseForDestination(SuccBB)) {
EnumCase = Case.get();
return SuccBB->getSinglePredecessorBlock() != nullptr;
}
return false;
}
return SuccBB->getSinglePredecessorBlock() != nullptr;
}
/// Create an enum element by extracting the operand of a switch_enum.
static SILValue createEnumElement(SILBuilder &Builder,
SwitchEnumInst *SEI,
EnumElementDecl *EnumElement) {
auto EnumVal = SEI->getOperand();
// Do we have a payload.
auto EnumTy = EnumVal->getType();
if (EnumElement->hasAssociatedValues()) {
auto Ty = EnumTy.getEnumElementType(EnumElement, SEI->getModule(),
Builder.getTypeExpansionContext());
SILValue UED(Builder.createUncheckedEnumData(SEI->getLoc(), EnumVal,
EnumElement, Ty));
return Builder.createEnum(SEI->getLoc(), UED, EnumElement, EnumTy);
}
return Builder.createEnum(SEI->getLoc(), SILValue(), EnumElement, EnumTy);
}
/// Create a value for the condition of the terminator that flows along the edge
/// with 'EdgeIdx'. Insert it before the 'UserInst'.
static SILValue createValueForEdge(SILInstruction *UserInst,
SILInstruction *DominatingTerminator,
unsigned EdgeIdx) {
SILBuilderWithScope Builder(UserInst);
if (auto *CBI = dyn_cast<CondBranchInst>(DominatingTerminator))
return Builder.createIntegerLiteral(
CBI->getLoc(), CBI->getCondition()->getType(), EdgeIdx == 0 ? -1 : 0);
auto *SEI = cast<SwitchEnumInst>(DominatingTerminator);
auto *DstBlock = SEI->getSuccessors()[EdgeIdx].getBB();
auto Case = SEI->getUniqueCaseForDestination(DstBlock);
assert(Case && "No unique case found for destination block");
return createEnumElement(Builder, SEI, Case.get());
}
/// Perform dominator based value simplifications and jump threading on all users
/// of the operand of 'DominatingBB's terminator.
static bool tryDominatorBasedSimplifications(
SILBasicBlock *DominatingBB, DominanceInfo *DT,
SmallPtrSetImpl<SILBasicBlock *> &LoopHeaders,
SmallVectorImpl<ThreadInfo> &JumpThreadableEdges,
llvm::DenseSet<std::pair<SILBasicBlock *, SILBasicBlock *>>
&ThreadedEdgeSet,
bool TryJumpThreading,
llvm::DenseMap<SILBasicBlock *, bool> &CachedThreadable) {
auto *DominatingTerminator = DominatingBB->getTerminator();
// We handle value propagation from cond_br and switch_enum terminators.
bool IsEnumValue = isa<SwitchEnumInst>(DominatingTerminator);
if (!isa<CondBranchInst>(DominatingTerminator) && !IsEnumValue)
return false;
auto DominatingCondition = getTerminatorCondition(DominatingTerminator);
if (!DominatingCondition)
return false;
if (isa<SILUndef>(DominatingCondition))
return false;
bool Changed = false;
// We will look at all the outgoing edges from the conditional branch to see
// whether any other uses of the condition or uses of the condition along an
// edge are dominated by said outgoing edges. The outgoing edge carries the
// value on which we switch/cond_branch.
auto Succs = DominatingBB->getSuccessors();
for (unsigned Idx = 0; Idx < Succs.size(); ++Idx) {
auto *DominatingSuccBB = Succs[Idx].getBB();
EnumElementDecl *EnumCase = nullptr;
if (!isKnownEdgeValue(DominatingTerminator, DominatingSuccBB, EnumCase))
continue;
// Look for other uses of DominatingCondition that are either:
// * dominated by the DominatingSuccBB
//
// cond_br %dominating_cond / switch_enum
// /
// /
// /
// DominatingSuccBB:
// ...
// use %dominating_cond
//
// * are a conditional branch that has an incoming edge that is
// dominated by DominatingSuccBB.
//
// cond_br %dominating_cond
// /
// /
// /
//
// DominatingSuccBB:
// ...
// br DestBB
//
// \
// \ E -> %dominating_cond = true
// \
// v
// DestBB
// cond_br %dominating_cond
SmallVector<SILInstruction *, 16> UsersToReplace;
for (auto *Op : ignore_expect_uses(DominatingCondition)) {
auto *CondUserInst = Op->getUser();
// Ignore the DominatingTerminator itself.
if (CondUserInst->getParent() == DominatingBB)
continue;
// For enum values we are only interested in switch_enum and select_enum
// users.
if (IsEnumValue && !isa<SwitchEnumInst>(CondUserInst) &&
!isa<SelectEnumInst>(CondUserInst))
continue;
// If the use is dominated we can replace this use by the value
// flowing to DominatingSuccBB.
if (DT->dominates(DominatingSuccBB, CondUserInst->getParent())) {
UsersToReplace.push_back(CondUserInst);
continue;
}
// Jump threading is expensive so we don't always do it.
if (!TryJumpThreading)
continue;
auto *DestBB = CondUserInst->getParent();
// The user must be the terminator we are trying to jump thread.
if (CondUserInst != DestBB->getTerminator())
continue;
// Check whether we have seen this destination block already.
auto CacheEntryIt = CachedThreadable.find(DestBB);
bool IsThreadable = CacheEntryIt != CachedThreadable.end()
? CacheEntryIt->second
: (CachedThreadable[DestBB] =
isThreadableBlock(DestBB, LoopHeaders));
// If the use is a conditional branch/switch then look for an incoming
// edge that is dominated by DominatingSuccBB.
if (IsThreadable) {
auto Preds = DestBB->getPredecessorBlocks();
for (SILBasicBlock *PredBB : Preds) {
if (!isa<BranchInst>(PredBB->getTerminator()))
continue;
if (!DT->dominates(DominatingSuccBB, PredBB))
continue;
// Don't jumpthread the same edge twice.
if (!ThreadedEdgeSet.insert(std::make_pair(PredBB, DestBB)).second)
continue;
if (isa<CondBranchInst>(DestBB->getTerminator()))
JumpThreadableEdges.push_back(ThreadInfo(PredBB, DestBB, Idx));
else
JumpThreadableEdges.push_back(ThreadInfo(PredBB, DestBB, EnumCase));
break;
}
}
}
// Replace dominated user instructions.
for (auto *UserInst : UsersToReplace) {
SILValue EdgeValue;
for (auto &Op : UserInst->getAllOperands()) {
if (stripExpectIntrinsic(Op.get()) == DominatingCondition) {
if (!EdgeValue)
EdgeValue = createValueForEdge(UserInst, DominatingTerminator, Idx);
Op.set(EdgeValue);
Changed = true;
}
}
}
}
return Changed;
}
/// Propagate values of branched upon values along the outgoing edges down the
/// dominator tree.
bool SimplifyCFG::dominatorBasedSimplifications(SILFunction &Fn,
DominanceInfo *DT) {
bool Changed = false;
// Collect jump threadable edges and propagate outgoing edge values of
// conditional branches/switches.
SmallVector<ThreadInfo, 8> JumpThreadableEdges;
llvm::DenseMap<SILBasicBlock *, bool> CachedThreadable;
llvm::DenseSet<std::pair<SILBasicBlock *, SILBasicBlock *>> ThreadedEdgeSet;
for (auto &BB : Fn)
if (DT->getNode(&BB)) // Only handle reachable blocks.
Changed |= tryDominatorBasedSimplifications(
&BB, DT, LoopHeaders, JumpThreadableEdges, ThreadedEdgeSet,
EnableJumpThread, CachedThreadable);
// Nothing to jump thread?
if (JumpThreadableEdges.empty())
return Changed;
for (auto &ThreadInfo : JumpThreadableEdges) {
if (threadEdge(ThreadInfo)) {
Changed = true;
}
}
return Changed;
}
/// Simplify terminators that could have been simplified by threading.
bool SimplifyCFG::simplifyThreadedTerminators() {
bool HaveChangedCFG = false;
for (auto &BB : Fn) {
auto *Term = BB.getTerminator();
// Simplify a switch_enum.
if (auto *SEI = dyn_cast<SwitchEnumInst>(Term)) {
if (auto *EI = dyn_cast<EnumInst>(SEI->getOperand())) {
LLVM_DEBUG(llvm::dbgs() << "simplify threaded " << *SEI);
auto *LiveBlock = SEI->getCaseDestination(EI->getElement());
if (EI->hasOperand() && !LiveBlock->args_empty())
SILBuilderWithScope(SEI)
.createBranch(SEI->getLoc(), LiveBlock, EI->getOperand());
else
SILBuilderWithScope(SEI).createBranch(SEI->getLoc(), LiveBlock);
SEI->eraseFromParent();
if (EI->use_empty())
EI->eraseFromParent();
HaveChangedCFG = true;
}
continue;
} else if (auto *CondBr = dyn_cast<CondBranchInst>(Term)) {
// If the condition is an integer literal, we can constant fold the
// branch.
if (auto *IL = dyn_cast<IntegerLiteralInst>(CondBr->getCondition())) {
LLVM_DEBUG(llvm::dbgs() << "simplify threaded " << *CondBr);
SILBasicBlock *TrueSide = CondBr->getTrueBB();
SILBasicBlock *FalseSide = CondBr->getFalseBB();
auto TrueArgs = CondBr->getTrueArgs();
auto FalseArgs = CondBr->getFalseArgs();
bool isFalse = !IL->getValue();
auto LiveArgs = isFalse ? FalseArgs : TrueArgs;
auto *LiveBlock = isFalse ? FalseSide : TrueSide;
SILBuilderWithScope(CondBr)
.createBranch(CondBr->getLoc(), LiveBlock, LiveArgs);
CondBr->eraseFromParent();
if (IL->use_empty())
IL->eraseFromParent();
HaveChangedCFG = true;
}
}
}
return HaveChangedCFG;
}
// Simplifications that walk the dominator tree to prove redundancy in
// conditional branching.
bool SimplifyCFG::dominatorBasedSimplify(DominanceAnalysis *DA) {
// Get the dominator tree.
DT = DA->get(&Fn);
// Split all critical edges such that we can move code onto edges. This is
// also required for SSA construction in dominatorBasedSimplifications' jump
// threading. It only splits new critical edges it creates by jump threading.
bool Changed =
EnableJumpThread ? splitAllCriticalEdges(Fn, DT, nullptr) : false;
unsigned MaxIter = MaxIterationsOfDominatorBasedSimplify;
SmallVector<SILBasicBlock *, 16> BlocksForWorklist;
bool HasChangedInCurrentIter;
do {
HasChangedInCurrentIter = false;
// Do dominator based simplification of terminator condition. This does not
// and MUST NOT change the CFG without updating the dominator tree to
// reflect such change.
if (tryCheckedCastBrJumpThreading(&Fn, DT, BlocksForWorklist)) {
for (auto BB: BlocksForWorklist)
addToWorklist(BB);
HasChangedInCurrentIter = true;
DT->recalculate(Fn);
}
BlocksForWorklist.clear();
if (ShouldVerify)
DT->verify();
// Simplify the block argument list. This is extremely subtle: simplifyArgs
// will not change the CFG iff the DT is null. Really we should move that
// one optimization out of simplifyArgs ... I am squinting at you
// simplifySwitchEnumToSelectEnum.
// simplifyArgs does use the dominator tree, though.
for (auto &BB : Fn)
HasChangedInCurrentIter |= simplifyArgs(&BB);
if (ShouldVerify)
DT->verify();
// Jump thread.
if (dominatorBasedSimplifications(Fn, DT)) {
DominanceInfo *InvalidDT = DT;
DT = nullptr;
HasChangedInCurrentIter = true;
// Simplify terminators.
simplifyThreadedTerminators();
DT = InvalidDT;
DT->recalculate(Fn);
}
Changed |= HasChangedInCurrentIter;
} while (HasChangedInCurrentIter && --MaxIter);
// Do the simplification that requires both the dom and postdom tree.
for (auto &BB : Fn)
Changed |= simplifyArgs(&BB);
if (ShouldVerify)
DT->verify();
// The functions we used to simplify the CFG put things in the worklist. Clear
// it here.
clearWorklist();
return Changed;
}
// If BB is trivially unreachable, remove it from the worklist, add its
// successors to the worklist, and then remove the block.
bool SimplifyCFG::removeIfDead(SILBasicBlock *BB) {
if (!BB->pred_empty() || BB == &*Fn.begin())
return false;
removeFromWorklist(BB);
// Add successor blocks to the worklist since their predecessor list is about
// to change.
for (auto &S : BB->getSuccessors())
addToWorklist(S);
LLVM_DEBUG(llvm::dbgs() << "remove dead bb" << BB->getDebugID() << '\n');
removeDeadBlock(BB);
++NumBlocksDeleted;
return true;
}
/// This is called when a predecessor of a block is dropped, to simplify the
/// block and add it to the worklist.
bool SimplifyCFG::simplifyAfterDroppingPredecessor(SILBasicBlock *BB) {
// TODO: If BB has only one predecessor and has bb args, fold them away, then
// use instsimplify on all the users of those values - even ones outside that
// block.
// Make sure that DestBB is in the worklist, as well as its remaining
// predecessors, since they may not be able to be simplified.
addToWorklist(BB);
for (auto *P : BB->getPredecessorBlocks())
addToWorklist(P);
return false;
}
/// This is called after \p BB has been cloned during jump-threading
/// (tail-duplication) and the new critical edge on its successor has been
/// split. This is necessary to continue jump-threading through the split
/// critical edge (since we only jump-thread one block at a time).
bool SimplifyCFG::addToWorklistAfterSplittingEdges(SILBasicBlock *BB) {
addToWorklist(BB);
for (auto *succBB : BB->getSuccessorBlocks()) {
addToWorklist(succBB);
}
return false;
}
static NullablePtr<EnumElementDecl>
getEnumCaseRecursive(SILValue Val, SILBasicBlock *UsedInBB, int RecursionDepth,
llvm::SmallPtrSetImpl<SILArgument *> &HandledArgs) {
// Limit the number of recursions. This is an easy way to cope with cycles
// in the SSA graph.
if (RecursionDepth > 3)
return nullptr;
// Handle the obvious case.
if (auto *EI = dyn_cast<EnumInst>(Val))
return EI->getElement();
// Check if the value is dominated by a switch_enum, e.g.
// switch_enum %val, case A: bb1, case B: bb2
// bb1:
// use %val // We know that %val has case A
SILBasicBlock *Pred = UsedInBB->getSinglePredecessorBlock();
int Limit = 3;
// A very simple dominator check: just walk up the single predecessor chain.
// The limit is just there to not run into an infinite loop in case of an
// unreachable CFG cycle.
while (Pred && --Limit > 0) {
if (auto *PredSEI = dyn_cast<SwitchEnumInst>(Pred->getTerminator())) {
if (PredSEI->getOperand() == Val)
return PredSEI->getUniqueCaseForDestination(UsedInBB);
}
UsedInBB = Pred;
Pred = UsedInBB->getSinglePredecessorBlock();
}
// In case of a block argument, recursively check the enum cases of all
// incoming predecessors.
if (auto *Arg = dyn_cast<SILArgument>(Val)) {
HandledArgs.insert(Arg);
llvm::SmallVector<std::pair<SILBasicBlock *, SILValue>, 8> IncomingVals;
if (!Arg->getIncomingPhiValues(IncomingVals))
return nullptr;
EnumElementDecl *CommonCase = nullptr;
for (std::pair<SILBasicBlock *, SILValue> Incoming : IncomingVals) {
SILBasicBlock *IncomingBlock = Incoming.first;
SILValue IncomingVal = Incoming.second;
auto *IncomingArg = dyn_cast<SILArgument>(IncomingVal);
if (IncomingArg && HandledArgs.count(IncomingArg) != 0)
continue;
NullablePtr<EnumElementDecl> IncomingCase =
getEnumCaseRecursive(Incoming.second, IncomingBlock, RecursionDepth + 1,
HandledArgs);
if (!IncomingCase)
return nullptr;
if (IncomingCase.get() != CommonCase) {
if (CommonCase)
return nullptr;
CommonCase = IncomingCase.get();
}
}
return CommonCase;
}
return nullptr;
}
/// Tries to figure out the enum case of an enum value \p Val which is used in
/// block \p UsedInBB.
static NullablePtr<EnumElementDecl> getEnumCase(SILValue Val,
SILBasicBlock *UsedInBB) {
llvm::SmallPtrSet<SILArgument *, 8> HandledArgs;
return getEnumCaseRecursive(Val, UsedInBB, /*RecursionDepth*/ 0, HandledArgs);
}
static int getThreadingCost(SILInstruction *I) {
if (!I->isTriviallyDuplicatable())
return 1000;
// Don't jumpthread function calls.
if (isa<ApplyInst>(I))
return 1000;
// This is a really trivial cost model, which is only intended as a starting
// point.
if (instructionInlineCost(*I) != InlineCost::Free)
return 1;
return 0;
}
static int maxBranchRecursionDepth = 6;
/// couldSimplifyUsers - Check to see if any simplifications are possible if
/// "Val" is substituted for BBArg. If so, return true, if nothing obvious
/// is possible, return false.
static bool couldSimplifyEnumUsers(SILArgument *BBArg, int Budget,
int recursionDepth = 0) {
SILBasicBlock *BB = BBArg->getParent();
int BudgetForBranch = 100;
for (Operand *UI : BBArg->getUses()) {
auto *User = UI->getUser();
if (User->getParent() != BB)
continue;
// We only know we can simplify if the switch_enum user is in the block we
// are trying to jump thread.
// The value must not be define in the same basic block as the switch enum
// user. If this is the case we have a single block switch_enum loop.
if (isa<SwitchEnumInst>(User) || isa<SelectEnumInst>(User))
return true;
// Also allow enum of enum, which usually can be combined to a single
// instruction. This helps to simplify the creation of an enum from an
// integer raw value.
if (isa<EnumInst>(User))
return true;
if (auto *SWI = dyn_cast<SwitchValueInst>(User)) {
if (SWI->getOperand() == BBArg)
return true;
}
if (auto *BI = dyn_cast<BranchInst>(User)) {
if (recursionDepth >= maxBranchRecursionDepth) {
return false;
}
if (BudgetForBranch > Budget) {
BudgetForBranch = Budget;
for (SILInstruction &I : *BB) {
BudgetForBranch -= getThreadingCost(&I);
if (BudgetForBranch < 0)
break;
}
}
if (BudgetForBranch > 0) {
SILBasicBlock *DestBB = BI->getDestBB();
unsigned OpIdx = UI->getOperandNumber();
if (couldSimplifyEnumUsers(DestBB->getArgument(OpIdx), BudgetForBranch,
recursionDepth + 1))
return true;
}
}
}
return false;
}
void SimplifyCFG::findLoopHeaders() {
/// Find back edges in the CFG. This performs a dfs search and identifies
/// back edges as edges going to an ancestor in the dfs search. If a basic
/// block is the target of such a back edge we will identify it as a header.
LoopHeaders.clear();
SmallPtrSet<SILBasicBlock *, 16> Visited;
SmallPtrSet<SILBasicBlock *, 16> InDFSStack;
SmallVector<std::pair<SILBasicBlock *, SILBasicBlock::succ_iterator>, 16>
DFSStack;
auto EntryBB = &Fn.front();
DFSStack.push_back(std::make_pair(EntryBB, EntryBB->succ_begin()));
Visited.insert(EntryBB);
InDFSStack.insert(EntryBB);
while (!DFSStack.empty()) {
auto &D = DFSStack.back();
// No successors.
if (D.second == D.first->succ_end()) {
// Retreat the dfs search.
DFSStack.pop_back();
InDFSStack.erase(D.first);
} else {
// Visit the next successor.
SILBasicBlock *NextSucc = *(D.second);
++D.second;
if (Visited.insert(NextSucc).second) {
InDFSStack.insert(NextSucc);
DFSStack.push_back(std::make_pair(NextSucc, NextSucc->succ_begin()));
} else if (InDFSStack.count(NextSucc)) {
// We have already visited this node and it is in our dfs search. This
// is a back-edge.
LoopHeaders.insert(NextSucc);
}
}
}
}
static bool couldRemoveRelease(SILBasicBlock *SrcBB, SILValue SrcV,
SILBasicBlock *DestBB, SILValue DestV) {
bool IsRetainOfSrc = false;
for (auto *U: SrcV->getUses())
if (U->getUser()->getParent() == SrcBB &&
(isa<StrongRetainInst>(U->getUser()) ||
isa<RetainValueInst>(U->getUser()))) {
IsRetainOfSrc = true;
break;
}
if (!IsRetainOfSrc)
return false;
bool IsReleaseOfDest = false;
for (auto *U: DestV->getUses())
if (U->getUser()->getParent() == DestBB &&
(isa<StrongReleaseInst>(U->getUser()) ||
isa<ReleaseValueInst>(U->getUser()))) {
IsReleaseOfDest = true;
break;
}
return IsReleaseOfDest;
}
/// Returns true if any instruction in \p block may write memory.
static bool blockMayWriteMemory(SILBasicBlock *block) {
for (auto instAndIdx : llvm::enumerate(*block)) {
if (instAndIdx.value().mayWriteToMemory())
return true;
// Only look at the first 20 instructions to avoid compile time problems for
// corner cases of very large blocks without memory writes.
// 20 instructions is more than enough.
if (instAndIdx.index() > 50)
return true;
}
return false;
}
// Returns true if \p block contains an injected an enum case into \p enumAddr
// which is valid at the end of the block.
static bool hasInjectedEnumAtEndOfBlock(SILBasicBlock *block, SILValue enumAddr) {
for (auto instAndIdx : llvm::enumerate(llvm::reverse(*block))) {
SILInstruction &inst = instAndIdx.value();
if (auto *injectInst = dyn_cast<InjectEnumAddrInst>(&inst)) {
return injectInst->getOperand() == enumAddr;
}
if (inst.mayWriteToMemory())
return false;
// Only look at the first 20 instructions to avoid compile time problems for
// corner cases of very large blocks without memory writes.
// 20 instructions is more than enough.
if (instAndIdx.index() > 50)
return false;
}
return false;
}
/// tryJumpThreading - Check to see if it looks profitable to duplicate the
/// destination of an unconditional jump into the bottom of this block.
bool SimplifyCFG::tryJumpThreading(BranchInst *BI) {
auto *DestBB = BI->getDestBB();
auto *SrcBB = BI->getParent();
TermInst *destTerminator = DestBB->getTerminator();
// If the destination block ends with a return, we don't want to duplicate it.
// We want to maintain the canonical form of a single return where possible.
if (destTerminator->isFunctionExiting())
return false;
// Jump threading only makes sense if there is an argument on the branch
// (which is reacted on in the DestBB), or if this goes through a memory
// location (switch_enum_addr is the only adress-instruction which we
// currently handle).
if (BI->getArgs().empty() && !isa<SwitchEnumAddrInst>(destTerminator))
return false;
// We don't have a great cost model at the SIL level, so we don't want to
// blissly duplicate tons of code with a goal of improved performance (we'll
// leave that to LLVM). However, doing limited code duplication can lead to
// major second order simplifications. Here we only do it if there are
// "constant" arguments to the branch or if we know how to fold something
// given the duplication.
int ThreadingBudget = 0;
for (unsigned i = 0, e = BI->getArgs().size(); i != e; ++i) {
// If the value being substituted on is release there is a chance we could
// remove the release after jump threading.
if (couldRemoveRelease(SrcBB, BI->getArg(i), DestBB,
DestBB->getArgument(i))) {
ThreadingBudget = 8;
break;
}
// If the value being substituted is an enum, check to see if there are any
// switches on it.
SILValue Arg = BI->getArg(i);
if (!getEnumCase(Arg, BI->getParent()) &&
!isa<IntegerLiteralInst>(Arg))
continue;
if (couldSimplifyEnumUsers(DestBB->getArgument(i), 8)) {
ThreadingBudget = 8;
break;
}
}
if (ThreadingBudget == 0) {
if (isa<CondBranchInst>(destTerminator)) {
for (auto V : BI->getArgs()) {
if (isa<IntegerLiteralInst>(V) || isa<FloatLiteralInst>(V)) {
ThreadingBudget = 4;
break;
}
}
} else if (auto *SEA = dyn_cast<SwitchEnumAddrInst>(destTerminator)) {
// If the branch-block injects a certain enum case and the destination
// switches on that enum, it's worth jump threading. E.g.
//
// inject_enum_addr %enum : $*Optional<T>, #Optional.some
// ... // no memory writes here
// br DestBB
// DestBB:
// ... // no memory writes here
// switch_enum_addr %enum : $*Optional<T>, case #Optional.some ...
//
SILValue enumAddr = SEA->getOperand();
if (!blockMayWriteMemory(DestBB) &&
hasInjectedEnumAtEndOfBlock(SrcBB, enumAddr)) {
ThreadingBudget = 4;
}
}
}
ThreadingBudget -= JumpThreadingCost[SrcBB];
ThreadingBudget -= JumpThreadingCost[DestBB];
// If we don't have anything that we can simplify, don't do it.
if (ThreadingBudget <= 0)
return false;
// Don't jump thread through a potential header - this can produce irreducible
// control flow. Still, we make an exception for switch_enum.
bool DestIsLoopHeader = (LoopHeaders.count(DestBB) != 0);
if (DestIsLoopHeader) {
if (!isa<SwitchEnumInst>(destTerminator))
return false;
}
// If it looks potentially interesting, decide whether we *can* do the
// operation and whether the block is small enough to be worth duplicating.
int copyCosts = 0;
BasicBlockCloner Cloner(DestBB);
for (auto &inst : *DestBB) {
copyCosts += getThreadingCost(&inst);
if (ThreadingBudget <= copyCosts)
return false;
// If this is an address projection with outside uses, sink it before
// checking for SSA update.
if (!Cloner.canCloneInstruction(&inst))
return false;
}
LLVM_DEBUG(llvm::dbgs() << "jump thread from bb" << SrcBB->getDebugID()
<< " to bb" << DestBB->getDebugID() << '\n');
JumpThreadingCost[DestBB] += copyCosts;
// Duplicate the destination block into this one, rewriting uses of the BBArgs
// to use the branch arguments as we go.
Cloner.cloneBranchTarget(BI);
Cloner.updateSSAAfterCloning();
// Once all the instructions are copied, we can nuke BI itself. We also add
// the threaded and edge block to the worklist now that they (likely) can be
// simplified.
addToWorklist(SrcBB);
// Simplify the cloned block and continue jump-threading through its new
// successors edges.
addToWorklistAfterSplittingEdges(Cloner.getNewBB());
// We may be able to simplify DestBB now that it has one fewer predecessor.
simplifyAfterDroppingPredecessor(DestBB);
// If we jump-thread a switch_enum in the loop header, we have to recalculate
// the loop header info.
if (DestIsLoopHeader)
findLoopHeaders();
++NumJumpThreads;
return true;
}
/// simplifyBranchOperands - Simplify operands of branches, since it can
/// result in exposing opportunities for CFG simplification.
bool SimplifyCFG::simplifyBranchOperands(OperandValueArrayRef Operands) {
bool Simplified = false;
for (auto O = Operands.begin(), E = Operands.end(); O != E; ++O) {
// All of our interesting simplifications are on single-value instructions
// for now.
if (auto *I = dyn_cast<SingleValueInstruction>(*O)) {
SILValue Result = simplifyInstruction(I);
// The Result can be the same instruction I in case it is in an
// unreachable block. In this case it can reference itself as operand.
if (Result && Result != I) {
LLVM_DEBUG(llvm::dbgs() << "simplify branch operand " << *I);
replaceAllSimplifiedUsesAndErase(I, Result);
Simplified = true;
}
}
}
return Simplified;
}
static bool onlyHasTerminatorAndDebugInsts(SILBasicBlock *BB) {
TermInst *Terminator = BB->getTerminator();
SILBasicBlock::iterator Iter = BB->begin();
while (&*Iter != Terminator) {
if (!(&*Iter)->isDebugInstruction())
return false;
++Iter;
}
return true;
}
namespace {
/// Will be valid if the constructor's targetBB has a a single branch and all
/// its block arguments are only used by that branch.
struct TrampolineDest {
SILBasicBlock *destBB = nullptr;
// Source block's branch args after bypassing targetBB.
SmallVector<SILValue, 4> newSourceBranchArgs;
TrampolineDest() {}
TrampolineDest(SILBasicBlock *sourceBB, SILBasicBlock *targetBB);
TrampolineDest(const TrampolineDest &) = delete;
TrampolineDest &operator=(const TrampolineDest &) = delete;
TrampolineDest(TrampolineDest &&) = default;
TrampolineDest &operator=(TrampolineDest &&) = default;
bool operator==(const TrampolineDest &rhs) {
return destBB == rhs.destBB
&& newSourceBranchArgs == rhs.newSourceBranchArgs;
}
bool operator!=(const TrampolineDest &rhs) {
return !(*this == rhs);
}
operator bool() const { return destBB != nullptr; }
};
} // end anonymous namespace
TrampolineDest::TrampolineDest(SILBasicBlock *sourceBB,
SILBasicBlock *targetBB) {
// Ignore blocks with more than one instruction.
if (!onlyHasTerminatorAndDebugInsts(targetBB))
return;
auto *targetBranch = dyn_cast<BranchInst>(targetBB->getTerminator());
if (!targetBranch)
return;
// Disallow infinite loops through targetBB.
llvm::SmallPtrSet<SILBasicBlock *, 8> VisitedBBs;
BranchInst *nextBI = targetBranch;
do {
SILBasicBlock *nextBB = nextBI->getDestBB();
// We don't care about infinite loops after SBB.
if (!VisitedBBs.insert(nextBB).second)
break;
// Only if the infinite loop goes through SBB directly we bail.
if (nextBB == targetBB)
return;
nextBI = dyn_cast<BranchInst>(nextBB->getTerminator());
} while (nextBI);
// Check that all the target block arguments are only used by the branch.
for (SILValue blockArg : targetBB->getArguments()) {
Operand *operand = blockArg->getSingleUse();
if (!operand || operand->getUser() != targetBranch) {
return;
}
}
newSourceBranchArgs.reserve(targetBranch->getArgs().size());
for (SILValue branchArg : targetBranch->getArgs()) {
if (branchArg->getParentBlock() == targetBB) {
auto *phi = dyn_cast<SILPhiArgument>(branchArg);
if (!phi || !phi->isPhiArgument()) {
return;
}
branchArg = phi->getIncomingPhiValue(sourceBB);
}
newSourceBranchArgs.push_back(branchArg);
}
// Setting destBB constructs a valid TrampolineDest.
destBB = targetBranch->getDestBB();
}
#ifndef NDEBUG
/// Is the block reachable from the entry.
static bool isReachable(SILBasicBlock *Block) {
SmallPtrSet<SILBasicBlock *, 16> Visited;
llvm::SmallVector<SILBasicBlock *, 16> Worklist;
SILBasicBlock *EntryBB = &*Block->getParent()->begin();
Worklist.push_back(EntryBB);
Visited.insert(EntryBB);
while (!Worklist.empty()) {
auto *CurBB = Worklist.back();
Worklist.pop_back();
if (CurBB == Block)
return true;
for (auto &Succ : CurBB->getSuccessors())
// Second is true if the insertion took place.
if (Visited.insert(Succ).second)
Worklist.push_back(Succ);
}
return false;
}
#endif
static llvm::cl::opt<bool> SimplifyUnconditionalBranches(
"simplify-cfg-simplify-unconditional-branches", llvm::cl::init(true));
/// Returns true if \p block has less instructions than \p other.
static bool hasLessInstructions(SILBasicBlock *block, SILBasicBlock *other) {
auto blockIter = block->begin();
auto blockEnd = block->end();
auto otherIter = other->begin();
auto otherEnd = other->end();
while (true) {
if (otherIter == otherEnd)
return false;
if (blockIter == blockEnd)
return true;
++blockIter;
++otherIter;
}
}
/// simplifyBranchBlock - Simplify a basic block that ends with an unconditional
/// branch.
///
/// Performs trivial trampoline removal. May be called as a utility to cleanup
/// successors after removing conditional branches or predecessors after
/// deleting unreachable blocks.
bool SimplifyCFG::simplifyBranchBlock(BranchInst *BI) {
// If we are asked to not simplify unconditional branches (for testing
// purposes), exit early.
if (!SimplifyUnconditionalBranches)
return false;
// First simplify instructions generating branch operands since that
// can expose CFG simplifications.
bool Simplified = simplifyBranchOperands(BI->getArgs());
auto *BB = BI->getParent(), *DestBB = BI->getDestBB();
// If this block branches to a block with a single predecessor, then
// merge the DestBB into this BB.
if (BB != DestBB && DestBB->getSinglePredecessorBlock()) {
LLVM_DEBUG(llvm::dbgs() << "merge bb" << BB->getDebugID() << " with bb"
<< DestBB->getDebugID() << '\n');
for (unsigned i = 0, e = BI->getArgs().size(); i != e; ++i) {
if (DestBB->getArgument(i) == BI->getArg(i)) {
// We must be processing an unreachable part of the cfg with a cycle.
// bb1(arg1): // preds: bb3
// br bb2
//
// bb2: // preds: bb1
// br bb3
//
// bb3: // preds: bb2
// br bb1(arg1)
assert(!isReachable(BB) && "Should only occur in unreachable block");
return Simplified;
}
}
// If there are any BB arguments in the destination, replace them with the
// branch operands, since they must dominate the dest block.
for (unsigned i = 0, e = BI->getArgs().size(); i != e; ++i) {
assert(DestBB->getArgument(i) != BI->getArg(i));
SILValue Val = BI->getArg(i);
DestBB->getArgument(i)->replaceAllUsesWith(Val);
if (!isVeryLargeFunction) {
if (auto *I = dyn_cast<SingleValueInstruction>(Val)) {
// Replacing operands may trigger constant folding which then could
// trigger other simplify-CFG optimizations.
ConstFolder.addToWorklist(I);
ConstFolder.processWorkList();
}
}
}
BI->eraseFromParent();
// Move instruction from the smaller block to the larger block.
// The order is essential because if many blocks are merged and this is done
// in the wrong order, we end up with quadratic complexity.
//
SILBasicBlock *remainingBlock = nullptr, *deletedBlock = nullptr;
if (BB != Fn.getEntryBlock() && hasLessInstructions(BB, DestBB)) {
while (!BB->pred_empty()) {
SILBasicBlock *pred = *BB->pred_begin();
replaceBranchTarget(pred->getTerminator(), BB, DestBB, true);
}
DestBB->spliceAtBegin(BB);
DestBB->dropAllArguments();
DestBB->moveArgumentList(BB);
remainingBlock = DestBB;
deletedBlock = BB;
} else {
BB->spliceAtEnd(DestBB);
remainingBlock = BB;
deletedBlock = DestBB;
}
// Revisit this block now that we've changed it.
addToWorklist(remainingBlock);
// This can also expose opportunities in the successors of
// the merged block.
for (auto &Succ : remainingBlock->getSuccessors())
addToWorklist(Succ);
if (LoopHeaders.count(deletedBlock))
LoopHeaders.insert(remainingBlock);
auto Iter = JumpThreadingCost.find(deletedBlock);
if (Iter != JumpThreadingCost.end()) {
int costs = Iter->second;
JumpThreadingCost[remainingBlock] += costs;
}
removeFromWorklist(deletedBlock);
deletedBlock->eraseFromParent();
++NumBlocksMerged;
return true;
}
// If the destination block is a simple trampoline (jump to another block)
// then jump directly.
if (auto trampolineDest = TrampolineDest(BB, DestBB)) {
LLVM_DEBUG(llvm::dbgs()
<< "jump to trampoline from bb" << BB->getDebugID() << " to bb"
<< trampolineDest.destBB->getDebugID() << '\n');
SILBuilderWithScope(BI).createBranch(BI->getLoc(), trampolineDest.destBB,
trampolineDest.newSourceBranchArgs);
// Eliminating the trampoline can expose opportunities to improve the
// new block we branch to.
if (LoopHeaders.count(DestBB))
LoopHeaders.insert(BB);
addToWorklist(trampolineDest.destBB);
BI->eraseFromParent();
removeIfDead(DestBB);
addToWorklist(BB);
return true;
}
return Simplified;
}
/// Returns the original boolean value, looking through possible invert
/// builtins. The parameter \p Inverted is inverted if the returned original
/// value is the inverted value of the passed \p Cond.
/// If \p onlyAcceptSingleUse is true and the operand of an invert builtin has
/// more than one use, an invalid SILValue() is returned.
static SILValue skipInvert(SILValue Cond, bool &Inverted,
bool onlyAcceptSingleUse) {
while (auto *BI = dyn_cast<BuiltinInst>(Cond)) {
if (onlyAcceptSingleUse && !BI->hasOneUse())
return SILValue();
OperandValueArrayRef Args = BI->getArguments();
if (BI->getBuiltinInfo().ID == BuiltinValueKind::Xor) {
// Check if it's a boolean inversion of the condition.
if (auto *IL = dyn_cast<IntegerLiteralInst>(Args[1])) {
if (IL->getValue().isAllOnesValue()) {
Cond = Args[0];
Inverted = !Inverted;
continue;
}
} else if (auto *IL = dyn_cast<IntegerLiteralInst>(Args[0])) {
if (IL->getValue().isAllOnesValue()) {
Cond = Args[1];
Inverted = !Inverted;
continue;
}
}
}
break;
}
return Cond;
}
/// Returns the first cond_fail if it is the first side-effect
/// instruction in this block.
static CondFailInst *getFirstCondFail(SILBasicBlock *BB) {
auto It = BB->begin();
CondFailInst *CondFail = nullptr;
// Skip instructions that don't have side-effects.
while (It != BB->end() && !(CondFail = dyn_cast<CondFailInst>(It))) {
if (It->mayHaveSideEffects())
return nullptr;
++It;
}
return CondFail;
}
/// If the first side-effect instruction in this block is a cond_fail that
/// is guaranteed to fail, it is returned.
/// The \p Cond is the condition from a cond_br in the predecessor block. The
/// cond_fail must only fail if \p BB is entered through this predecessor block.
/// If \p Inverted is true, \p BB is on the false-edge of the cond_br.
static CondFailInst *getUnConditionalFail(SILBasicBlock *BB, SILValue Cond,
bool Inverted) {
CondFailInst *CondFail = getFirstCondFail(BB);
if (!CondFail)
return nullptr;
// The simple case: check if it is a "cond_fail 1".
auto *IL = dyn_cast<IntegerLiteralInst>(CondFail->getOperand());
if (IL && IL->getValue() != 0)
return CondFail;
// Check if the cond_fail has the same condition as the cond_br in the
// predecessor block.
Cond = skipInvert(Cond, Inverted, false);
SILValue CondFailCond = skipInvert(CondFail->getOperand(), Inverted, false);
if (Cond == CondFailCond && !Inverted)
return CondFail;
return nullptr;
}
/// Creates a new cond_fail instruction, optionally with an xor inverted
/// condition.
static void createCondFail(CondFailInst *Orig, SILValue Cond, StringRef Message,
bool inverted, SILBuilder &Builder) {
Builder.createCondFail(Orig->getLoc(), Cond, Message, inverted);
}
/// Inverts the expected value of 'PotentialExpect' (if it is an expect
/// intrinsic) and returns this expected value apply to 'V'.
static SILValue invertExpectAndApplyTo(SILBuilder &Builder,
SILValue PotentialExpect, SILValue V) {
auto *BI = dyn_cast<BuiltinInst>(PotentialExpect);
if (!BI)
return V;
if (BI->getIntrinsicInfo().ID != llvm::Intrinsic::expect)
return V;
auto Args = BI->getArguments();
auto *IL = dyn_cast<IntegerLiteralInst>(Args[1]);
if (!IL)
return V;
SILValue NegatedExpectedValue = Builder.createIntegerLiteral(
IL->getLoc(), Args[1]->getType(), IL->getValue() == 0 ? -1 : 0);
return Builder.createBuiltin(BI->getLoc(), BI->getName(), BI->getType(), {},
{V, NegatedExpectedValue});
}
/// simplifyCondBrBlock - Simplify a basic block that ends with a conditional
/// branch.
bool SimplifyCFG::simplifyCondBrBlock(CondBranchInst *BI) {
// First simplify instructions generating branch operands since that
// can expose CFG simplifications.
simplifyBranchOperands(OperandValueArrayRef(BI->getAllOperands()));
auto *ThisBB = BI->getParent();
SILBasicBlock *TrueSide = BI->getTrueBB();
SILBasicBlock *FalseSide = BI->getFalseBB();
auto TrueArgs = BI->getTrueArgs();
auto FalseArgs = BI->getFalseArgs();
// If the condition is an integer literal, we can constant fold the branch.
if (auto *IL = dyn_cast<IntegerLiteralInst>(BI->getCondition())) {
bool isFalse = !IL->getValue();
auto LiveArgs = isFalse ? FalseArgs : TrueArgs;
auto *LiveBlock = isFalse ? FalseSide : TrueSide;
auto *DeadBlock = !isFalse ? FalseSide : TrueSide;
LLVM_DEBUG(llvm::dbgs() << "replace cond_br with br: " << *BI);
SILBuilderWithScope(BI).createBranch(BI->getLoc(), LiveBlock, LiveArgs);
BI->eraseFromParent();
if (IL->use_empty()) IL->eraseFromParent();
addToWorklist(ThisBB);
simplifyAfterDroppingPredecessor(DeadBlock);
addToWorklist(LiveBlock);
++NumConstantFolded;
return true;
}
// Canonicalize "cond_br (not %cond), BB1, BB2" to "cond_br %cond, BB2, BB1".
// This looks through expect intrinsic calls and applies the ultimate expect
// call inverted to the condition.
if (auto *Xor =
dyn_cast<BuiltinInst>(stripExpectIntrinsic(BI->getCondition()))) {
if (Xor->getBuiltinInfo().ID == BuiltinValueKind::Xor) {
// Check if it's a boolean inversion of the condition.
OperandValueArrayRef Args = Xor->getArguments();
if (auto *IL = dyn_cast<IntegerLiteralInst>(Args[1])) {
if (IL->getValue().isAllOnesValue()) {
LLVM_DEBUG(llvm::dbgs() << "canonicalize cond_br: " << *BI);
auto Cond = Args[0];
SILBuilderWithScope Builder(BI);
Builder.createCondBranch(
BI->getLoc(),
invertExpectAndApplyTo(Builder, BI->getCondition(), Cond),
FalseSide, FalseArgs, TrueSide, TrueArgs, BI->getFalseBBCount(),
BI->getTrueBBCount());
BI->eraseFromParent();
addToWorklist(ThisBB);
return true;
}
}
}
}
// If the destination block is a simple trampoline (jump to another block)
// then jump directly.
auto trueTrampolineDest = TrampolineDest(ThisBB, TrueSide);
if (trueTrampolineDest
&& trueTrampolineDest.destBB->getSinglePredecessorBlock()) {
LLVM_DEBUG(llvm::dbgs()
<< "true-trampoline from bb" << ThisBB->getDebugID() << " to bb"
<< trueTrampolineDest.destBB->getDebugID() << '\n');
SmallVector<SILValue, 4> falseArgsCopy(FalseArgs.begin(), FalseArgs.end());
SILBuilderWithScope(BI).createCondBranch(
BI->getLoc(), BI->getCondition(), trueTrampolineDest.destBB,
trueTrampolineDest.newSourceBranchArgs, FalseSide, falseArgsCopy,
BI->getTrueBBCount(), BI->getFalseBBCount());
BI->eraseFromParent();
if (LoopHeaders.count(TrueSide))
LoopHeaders.insert(ThisBB);
removeIfDead(TrueSide);
addToWorklist(ThisBB);
return true;
}
auto falseTrampolineDest = TrampolineDest(ThisBB, FalseSide);
if (falseTrampolineDest
&& falseTrampolineDest.destBB->getSinglePredecessorBlock()) {
LLVM_DEBUG(llvm::dbgs()
<< "false-trampoline from bb" << ThisBB->getDebugID() << " to bb"
<< falseTrampolineDest.destBB->getDebugID() << '\n');
SmallVector<SILValue, 4> trueArgsCopy(TrueArgs.begin(), TrueArgs.end());
SILBuilderWithScope(BI).createCondBranch(
BI->getLoc(), BI->getCondition(), TrueSide, trueArgsCopy,
falseTrampolineDest.destBB, falseTrampolineDest.newSourceBranchArgs,
BI->getTrueBBCount(), BI->getFalseBBCount());
BI->eraseFromParent();
if (LoopHeaders.count(FalseSide))
LoopHeaders.insert(ThisBB);
removeIfDead(FalseSide);
addToWorklist(ThisBB);
return true;
}
// Simplify cond_br where both sides jump to the same blocks with the same
// args.
auto condBrToBr = [&](ArrayRef<SILValue> branchArgs, SILBasicBlock *newDest) {
LLVM_DEBUG(llvm::dbgs()
<< "replace cond_br with same dests with br: " << *BI);
SILBuilderWithScope(BI).createBranch(BI->getLoc(), newDest, branchArgs);
BI->eraseFromParent();
addToWorklist(ThisBB);
++NumConstantFolded;
};
if (trueTrampolineDest.destBB == FalseSide
&& trueTrampolineDest.newSourceBranchArgs == FalseArgs) {
condBrToBr(trueTrampolineDest.newSourceBranchArgs, FalseSide);
removeIfDead(TrueSide);
return true;
}
if (falseTrampolineDest.destBB == TrueSide) {
condBrToBr(falseTrampolineDest.newSourceBranchArgs, TrueSide);
removeIfDead(FalseSide);
return true;
}
if (trueTrampolineDest && (trueTrampolineDest == falseTrampolineDest)) {
condBrToBr(trueTrampolineDest.newSourceBranchArgs,
trueTrampolineDest.destBB);
removeIfDead(TrueSide);
removeIfDead(FalseSide);
return true;
}
// If we have a (cond (select_enum)) on a two element enum, always have the
// first case as our checked tag. If we have the second, create a new
// select_enum with the first case and swap our operands. This simplifies
// later dominance based processing.
if (auto *SEI = dyn_cast<SelectEnumInst>(BI->getCondition())) {
EnumDecl *E = SEI->getEnumOperand()->getType().getEnumOrBoundGenericEnum();
auto AllElts = E->getAllElements();
auto Iter = AllElts.begin();
EnumElementDecl *FirstElt = *Iter;
// We can't do this optimization on non-exhaustive enums.
bool IsExhaustive =
E->isEffectivelyExhaustive(Fn.getModule().getSwiftModule(),
Fn.getResilienceExpansion());
if (IsExhaustive
&& SEI->getNumCases() >= 1
&& SEI->getCase(0).first != FirstElt) {
++Iter;
if (Iter != AllElts.end() &&
std::next(Iter) == AllElts.end() &&
*Iter == SEI->getCase(0).first) {
EnumElementDecl *SecondElt = *Iter;
SILValue FirstValue;
// SelectEnum must be exhaustive, so the second case must be handled
// either by a case or the default.
if (SEI->getNumCases() >= 2) {
assert(FirstElt == SEI->getCase(1).first
&& "select_enum missing a case?!");
FirstValue = SEI->getCase(1).second;
} else {
FirstValue = SEI->getDefaultResult();
}
std::pair<EnumElementDecl*, SILValue> SwappedCases[2] = {
{FirstElt, SEI->getCase(0).second},
{SecondElt, FirstValue},
};
LLVM_DEBUG(llvm::dbgs() << "canonicalize " << *SEI);
auto *NewSEI = SILBuilderWithScope(SEI)
.createSelectEnum(SEI->getLoc(),
SEI->getEnumOperand(),
SEI->getType(),
SILValue(),
SwappedCases);
// We only change the condition to be NewEITI instead of all uses since
// EITI may have other uses besides this one that need to be updated.
BI->setCondition(NewSEI);
BI->swapSuccessors();
addToWorklist(BI->getParent());
addToWorklist(TrueSide);
addToWorklist(FalseSide);
return true;
}
}
}
// Simplify a condition branch to a block starting with "cond_fail 1".
//
// cond_br %cond, TrueSide, FalseSide
// TrueSide:
// cond_fail 1
//
auto CFCondition = BI->getCondition();
if (auto *TrueCFI = getUnConditionalFail(TrueSide, CFCondition, false)) {
LLVM_DEBUG(llvm::dbgs() << "replace with cond_fail:" << *BI);
SILBuilderWithScope Builder(BI);
createCondFail(TrueCFI, CFCondition, TrueCFI->getMessage(), false, Builder);
SILBuilderWithScope(BI).createBranch(BI->getLoc(), FalseSide, FalseArgs);
BI->eraseFromParent();
addToWorklist(ThisBB);
simplifyAfterDroppingPredecessor(TrueSide);
addToWorklist(FalseSide);
return true;
}
if (auto *FalseCFI = getUnConditionalFail(FalseSide, CFCondition, true)) {
LLVM_DEBUG(llvm::dbgs() << "replace with inverted cond_fail:" << *BI);
SILBuilderWithScope Builder(BI);
createCondFail(FalseCFI, CFCondition, FalseCFI->getMessage(), true, Builder);
SILBuilderWithScope(BI).createBranch(BI->getLoc(), TrueSide, TrueArgs);
BI->eraseFromParent();
addToWorklist(ThisBB);
simplifyAfterDroppingPredecessor(FalseSide);
addToWorklist(TrueSide);
return true;
}
return false;
}
// Does this basic block consist of only an "unreachable" instruction?
static bool isOnlyUnreachable(SILBasicBlock *BB) {
auto *Term = BB->getTerminator();
if (!isa<UnreachableInst>(Term))
return false;
return (&*BB->begin() == BB->getTerminator());
}
/// simplifySwitchEnumUnreachableBlocks - Attempt to replace a
/// switch_enum where all but one block consists of just an
/// "unreachable" with an unchecked_enum_data and branch.
bool SimplifyCFG::simplifySwitchEnumUnreachableBlocks(SwitchEnumInst *SEI) {
auto Count = SEI->getNumCases();
SILBasicBlock *Dest = nullptr;
EnumElementDecl *Element = nullptr;
if (SEI->hasDefault())
if (!isOnlyUnreachable(SEI->getDefaultBB()))
Dest = SEI->getDefaultBB();
for (unsigned i = 0; i < Count; ++i) {
auto EnumCase = SEI->getCase(i);
if (isOnlyUnreachable(EnumCase.second))
continue;
if (Dest)
return false;
assert(!Element && "Did not expect to have an element without a block!");
Element = EnumCase.first;
Dest = EnumCase.second;
}
if (!Dest) {
addToWorklist(SEI->getParent());
SILBuilderWithScope(SEI).createUnreachable(SEI->getLoc());
SEI->eraseFromParent();
return true;
}
if (!Element || !Element->hasAssociatedValues() || Dest->args_empty()) {
assert(Dest->args_empty() && "Unexpected argument at destination!");
SILBuilderWithScope(SEI).createBranch(SEI->getLoc(), Dest);
addToWorklist(SEI->getParent());
addToWorklist(Dest);
SEI->eraseFromParent();
return true;
}
LLVM_DEBUG(llvm::dbgs() << "remove " << *SEI);
auto &Mod = SEI->getModule();
auto OpndTy = SEI->getOperand()->getType();
auto Ty = OpndTy.getEnumElementType(
Element, Mod, TypeExpansionContext(*SEI->getFunction()));
auto *UED = SILBuilderWithScope(SEI)
.createUncheckedEnumData(SEI->getLoc(), SEI->getOperand(), Element, Ty);
assert(Dest->args_size() == 1 && "Expected only one argument!");
SmallVector<SILValue, 1> Args;
Args.push_back(UED);
SILBuilderWithScope(SEI).createBranch(SEI->getLoc(), Dest, Args);
addToWorklist(SEI->getParent());
addToWorklist(Dest);
SEI->eraseFromParent();
return true;
}
/// Checks that the someBB only contains obj_method calls (possibly chained) on
/// the optional value.
///
/// switch_enum %optionalValue, case #Optional.some!enumelt: someBB
///
/// someBB(%optionalPayload):
/// %1 = objc_method %optionalPayload
/// %2 = apply %1(..., %optionalPayload) // self position
/// %3 = unchecked_ref_cast %2
/// %4 = objc_method %3
/// %... = apply %4(..., %3)
/// br mergeBB(%...)
static bool containsOnlyObjMethodCallOnOptional(SILValue optionalValue,
SILBasicBlock *someBB,
SILValue &outBranchArg,
SILValue &outOptionalPayload) {
SILValue optionalPayload;
SmallVector<SILValue, 4> optionalPayloads;
if (someBB->getNumArguments() == 1) {
optionalPayload = someBB->getArgument(0);
optionalPayloads.push_back(optionalPayload);
} else if (someBB->getNumArguments() != 0)
return false;
SmallVector<SILValue, 4> objCApplies;
for (auto &i : *someBB) {
SILInstruction *inst = &i;
if (onlyAffectsRefCount(inst))
continue;
if (inst->isDebugInstruction())
continue;
// An objc_method has no sideffects.
if (isa<ObjCMethodInst>(inst))
continue;
// An uncheckedEnumData has no sideeffects.
if (auto *uncheckedEnumData = dyn_cast<UncheckedEnumDataInst>(inst)) {
if (uncheckedEnumData->getOperand() != optionalValue)
continue;
optionalPayload = uncheckedEnumData;
optionalPayloads.push_back(uncheckedEnumData);
continue;
}
// An unchecked_ref_cast is safe.
if (auto *refCast = dyn_cast<UncheckedRefCastInst>(inst)) {
// An unchecked_ref_cast on a safe objc_method apply behaves like the
// optional (it is null if the optional was null).
if (refCast->getType().getClassOrBoundGenericClass() &&
std::find(objCApplies.begin(), objCApplies.end(),
refCast->getOperand()) != objCApplies.end())
optionalPayloads.push_back(refCast);
continue;
}
// Applies on objc_methods where self is either the optional payload or the
// result of another 'safe' apply are safe.
if (auto *objcMethod = dyn_cast<ApplyInst>(inst)) {
if (!isa<ObjCMethodInst>(objcMethod->getCallee()))
return false;
if (std::find(optionalPayloads.begin(), optionalPayloads.end(),
objcMethod->getSelfArgument()) == optionalPayloads.end())
return false;
objCApplies.push_back(objcMethod);
continue;
}
// The branch should forward one of the objc_method call.
if (auto *br = dyn_cast<BranchInst>(inst)) {
if (br->getNumArgs() == 0 || br->getNumArgs() > 1)
return false;
auto branchArg = br->getArg(0);
if (std::find(objCApplies.begin(), objCApplies.end(), branchArg) ==
objCApplies.end())
return false;
outBranchArg = branchArg;
continue;
}
// Unexpected instruction.
return false;
}
if (!optionalPayload)
return false;
outOptionalPayload = optionalPayload;
return true;
}
/// Check that all that noneBB does is forwarding none.
/// The only other allowed operation are ref count operations.
static bool onlyForwardsNone(SILBasicBlock *noneBB, SILBasicBlock *someBB,
SwitchEnumInst *SEI) {
// It all the basic blocks leading up to the ultimate block we only expect
// reference count instructions.
while (noneBB->getSingleSuccessorBlock() != someBB->getSingleSuccessorBlock()) {
for (auto &i : *noneBB) {
auto *inst = &i;
if (isa<BranchInst>(inst) || onlyAffectsRefCount(inst) ||
inst->isDebugInstruction())
continue;
return false;
}
noneBB = noneBB->getSingleSuccessorBlock();
}
// The ultimate block forwards the Optional<...>.none value.
SILValue optionalNone;
for (auto &i : *noneBB) {
auto *inst = &i;
if (onlyAffectsRefCount(inst) || inst->isDebugInstruction())
continue;
if (auto *none = dyn_cast<EnumInst>(inst)) {
if (none->getElement() !=
SEI->getModule().getASTContext().getOptionalNoneDecl())
return false;
optionalNone = none;
continue;
}
if (auto *noneBranch = dyn_cast<BranchInst>(inst)) {
if (noneBranch->getNumArgs() != 1 ||
(noneBranch->getArg(0) != SEI->getOperand() &&
noneBranch->getArg(0) != optionalNone))
return false;
continue;
}
return false;
}
return true;
}
/// Check whether the \p someBB has only one single successor and that successor
/// post-dominates \p noneBB.
///
/// (maybe otherNoneBB)
/// someBB noneBB /
/// \ | v
/// \ ... more bbs? (A)
/// \ /
/// ulimateBB
///
/// This routine does not support diverging control flow in (A). This means that
/// there must not be any loops or diamonds beginning in that region. We do
/// support side-entrances from blocks not reachable from noneBB in order to
/// ensure that we properly handle other failure cases where the failure case
/// merges into .noneBB before ultimate BB.
///
/// DISCUSSION: We allow this side-entrance pattern to handle iterative
/// conditional checks which all feed the failing case through the .none
/// path. This is a common pattern in swift code. As an example consider a
/// switch statement with multiple pattern binding matching that use the same
/// cleanup code upon failure.
static bool hasSameUltimateSuccessor(SILBasicBlock *noneBB, SILBasicBlock *someBB) {
// Make sure that both our some, none blocks both have single successors that
// are not themselves (which can happen due to single block loops).
auto *someSuccessorBB = someBB->getSingleSuccessorBlock();
if (!someSuccessorBB || someSuccessorBB == someBB)
return false;
auto *noneSuccessorBB = noneBB->getSingleSuccessorBlock();
if (!noneSuccessorBB || noneSuccessorBB == noneBB)
return false;
// If we immediately find a simple diamond, return true. We are done.
if (noneSuccessorBB == someSuccessorBB)
return true;
// Otherwise, lets begin a traversal along the successors of noneSuccessorBB,
// searching for someSuccessorBB, being careful to only allow for blocks to be
// visited once. This enables us to guarantee that there are not any loops or
// any sub-diamonds in the part of the CFG we are traversing. This /does/
// allow for side-entrances to the region from blocks not reachable from
// noneSuccessorBB. See function level comment above.
SILBasicBlock *iter = noneSuccessorBB;
SmallPtrSet<SILBasicBlock *, 8> visitedBlocks;
visitedBlocks.insert(iter);
do {
// First try to grab our single successor if we have only one. If we have no
// successor or more than one successor, bail and do not optimize.
//
// DISCUSSION: Trivially, if we do not have a successor, then we have
// reached either a return/unreachable and this path will never merge with
// the ultimate block. If we have more than one successor, then for our
// condition to pass, we must have that both successors eventually join into
// someSuccessorBB. But this would imply that either someSuccessorBB has
// more than two predecessors and or that we merge the two paths before we
// visit someSuccessorBB.
auto *succBlock = iter->getSingleSuccessorBlock();
if (!succBlock)
return false;
// Then check if our single successor block has been visited already. If so,
// we have some sort of loop or have some sort of merge point that is not
// the final merge point.
//
// NOTE: We do not need to worry about someSuccessorBB being in
// visitedBlocks since before we begin the loop, we check that
// someSuccessorBB != iter and also check that in the do-while condition. So
// we can never have visited someSuccessorBB on any previous iteration
// meaning that the only time we can have succBlock equal to someSuccessorBB
// is on the last iteration before we exit the loop.
if (!visitedBlocks.insert(succBlock).second)
return false;
// Otherwise, set iter to succBlock.
iter = succBlock;
// And then check if this new successor block is someSuccessorBB. If so, we
// break and then return true since we have found our target. Otherwise, we
// need to visit further successors, so go back around the loop.
} while (iter != someSuccessorBB);
return true;
}
/// Simplify switch_enums on class enums that branch to objc_method calls on
/// that optional on the #Optional.some side to always branch to the some side.
///
/// switch_enum %optionalValue, case #Optional.some!enumelt: someBB,
/// case #Optional.none: noneBB
///
/// someBB(%optionalPayload):
/// %1 = objc_method %optionalPayload
/// %2 = apply %1(..., %optionalPayload) // self position
/// br mergeBB(%2)
///
/// noneBB:
/// %4 = enum #Optional.none
/// br mergeBB(%4)
bool SimplifyCFG::simplifySwitchEnumOnObjcClassOptional(SwitchEnumInst *SEI) {
auto optional = SEI->getOperand();
auto optionalPayloadType = optional->getType().getOptionalObjectType();
if (!optionalPayloadType ||
!optionalPayloadType.getClassOrBoundGenericClass())
return false;
if (SEI->getNumCases() != 2)
return false;
auto *noneBB = SEI->getCase(0).second;
auto *someBB = SEI->getCase(1).second;
if (noneBB == someBB)
return false;
auto someDecl = SEI->getModule().getASTContext().getOptionalSomeDecl();
if (SEI->getCaseDestination(someDecl) != someBB)
std::swap(someBB, noneBB);
if (!hasSameUltimateSuccessor(noneBB, someBB))
return false;
if (!onlyForwardsNone(noneBB, someBB, SEI))
return false;
SILValue branchArg;
SILValue optionalPayload;
if (!containsOnlyObjMethodCallOnOptional(optional, someBB, branchArg,
optionalPayload))
return false;
SILBuilderWithScope Builder(SEI);
auto *payloadCast = Builder.createUncheckedRefCast(SEI->getLoc(), optional,
optionalPayloadType);
optionalPayload->replaceAllUsesWith(payloadCast);
auto *switchBB = SEI->getParent();
if (someBB->getNumArguments())
Builder.createBranch(SEI->getLoc(), someBB, SILValue(payloadCast));
else
Builder.createBranch(SEI->getLoc(), someBB);
SEI->eraseFromParent();
addToWorklist(switchBB);
simplifyAfterDroppingPredecessor(noneBB);
addToWorklist(someBB);
++NumConstantFolded;
return true;
}
/// simplifySwitchEnumBlock - Simplify a basic block that ends with a
/// switch_enum instruction that gets its operand from an enum
/// instruction.
bool SimplifyCFG::simplifySwitchEnumBlock(SwitchEnumInst *SEI) {
auto EnumCase = getEnumCase(SEI->getOperand(), SEI->getParent());
if (!EnumCase)
return false;
auto *LiveBlock = SEI->getCaseDestination(EnumCase.get());
auto *ThisBB = SEI->getParent();
bool DroppedLiveBlock = false;
// Copy the successors into a vector, dropping one entry for the liveblock.
SmallVector<SILBasicBlock*, 4> Dests;
for (auto &S : SEI->getSuccessors()) {
if (S == LiveBlock && !DroppedLiveBlock) {
DroppedLiveBlock = true;
continue;
}
Dests.push_back(S);
}
LLVM_DEBUG(llvm::dbgs() << "remove " << *SEI);
auto *EI = dyn_cast<EnumInst>(SEI->getOperand());
SILBuilderWithScope Builder(SEI);
if (!LiveBlock->args_empty()) {
SILValue PayLoad;
if (EI) {
PayLoad = EI->getOperand();
} else {
PayLoad = Builder.createUncheckedEnumData(SEI->getLoc(),
SEI->getOperand(), EnumCase.get());
}
Builder.createBranch(SEI->getLoc(), LiveBlock, PayLoad);
} else {
Builder.createBranch(SEI->getLoc(), LiveBlock);
}
SEI->eraseFromParent();
if (EI && EI->use_empty()) EI->eraseFromParent();
addToWorklist(ThisBB);
for (auto B : Dests)
simplifyAfterDroppingPredecessor(B);
addToWorklist(LiveBlock);
++NumConstantFolded;
return true;
}
/// simplifySwitchValueBlock - Simplify a basic block that ends with a
/// switch_value instruction that gets its operand from an integer
/// literal instruction.
bool SimplifyCFG::simplifySwitchValueBlock(SwitchValueInst *SVI) {
auto *ThisBB = SVI->getParent();
if (auto *ILI = dyn_cast<IntegerLiteralInst>(SVI->getOperand())) {
SILBasicBlock *LiveBlock = nullptr;
auto Value = ILI->getValue();
// Find a case corresponding to this value
int i, e;
for (i = 0, e = SVI->getNumCases(); i < e; ++i) {
auto Pair = SVI->getCase(i);
auto *CaseIL = dyn_cast<IntegerLiteralInst>(Pair.first);
if (!CaseIL)
break;
auto CaseValue = CaseIL->getValue();
if (Value == CaseValue) {
LiveBlock = Pair.second;
break;
}
}
if (i == e && !LiveBlock) {
if (SVI->hasDefault()) {
LiveBlock = SVI->getDefaultBB();
}
}
if (LiveBlock) {
bool DroppedLiveBlock = false;
// Copy the successors into a vector, dropping one entry for the
// liveblock.
SmallVector<SILBasicBlock *, 4> Dests;
for (auto &S : SVI->getSuccessors()) {
if (S == LiveBlock && !DroppedLiveBlock) {
DroppedLiveBlock = true;
continue;
}
Dests.push_back(S);
}
LLVM_DEBUG(llvm::dbgs() << "remove " << *SVI);
SILBuilderWithScope(SVI).createBranch(SVI->getLoc(), LiveBlock);
SVI->eraseFromParent();
if (ILI->use_empty())
ILI->eraseFromParent();
addToWorklist(ThisBB);
for (auto B : Dests)
simplifyAfterDroppingPredecessor(B);
addToWorklist(LiveBlock);
++NumConstantFolded;
return true;
}
}
return simplifyTermWithIdenticalDestBlocks(ThisBB);
}
bool onlyContainsRefcountAndDeallocStackInst(
SILBasicBlock::reverse_iterator I, SILBasicBlock::reverse_iterator End) {
while (I != End) {
auto MaybeDead = I++;
switch (MaybeDead->getKind()) {
// These technically have side effects, but not ones that matter
// in a block that we shouldn't really reach...
case SILInstructionKind::StrongRetainInst:
case SILInstructionKind::StrongReleaseInst:
case SILInstructionKind::RetainValueInst:
case SILInstructionKind::ReleaseValueInst:
case SILInstructionKind::DeallocStackInst:
break;
default:
return false;
}
}
return true;
}
/// simplifyUnreachableBlock - Simplify blocks ending with unreachable by
/// removing instructions that are safe to delete backwards until we
/// hit an instruction we cannot delete.
bool SimplifyCFG::simplifyUnreachableBlock(UnreachableInst *UI) {
bool Changed = false;
auto BB = UI->getParent();
auto I = std::next(BB->rbegin());
auto End = BB->rend();
SmallVector<SILInstruction *, 8> DeadInstrs;
bool canIgnoreRestOfBlock = false;
// Walk backwards deleting instructions that should be safe to delete
// in a block that ends with unreachable.
while (I != End) {
auto MaybeDead = I++;
switch (MaybeDead->getKind()) {
// These technically have side effects, but not ones that matter
// in a block that we shouldn't really reach...
case SILInstructionKind::StrongRetainInst:
case SILInstructionKind::StrongReleaseInst:
case SILInstructionKind::RetainValueInst:
case SILInstructionKind::ReleaseValueInst:
break;
// We can only ignore a dealloc_stack instruction if we can ignore all
// instructions in the block.
case SILInstructionKind::DeallocStackInst: {
if (canIgnoreRestOfBlock ||
onlyContainsRefcountAndDeallocStackInst(MaybeDead, End)) {
canIgnoreRestOfBlock = true;
break;
}
LLVM_FALLTHROUGH;
}
default:
if (MaybeDead->mayHaveSideEffects()) {
if (Changed)
for (auto Dead : DeadInstrs)
Dead->eraseFromParent();
return Changed;
}
}
MaybeDead->replaceAllUsesOfAllResultsWithUndef();
DeadInstrs.push_back(&*MaybeDead);
Changed = true;
}
// If this block was changed and it now consists of only the unreachable,
// make sure we process its predecessors.
if (Changed) {
LLVM_DEBUG(llvm::dbgs() << "remove dead insts in unreachable bb"
<< BB->getDebugID() << '\n');
for (auto Dead : DeadInstrs)
Dead->eraseFromParent();
if (isOnlyUnreachable(BB))
for (auto *P : BB->getPredecessorBlocks())
addToWorklist(P);
}
return Changed;
}
bool SimplifyCFG::simplifyCheckedCastBranchBlock(CheckedCastBranchInst *CCBI) {
auto SuccessBB = CCBI->getSuccessBB();
auto FailureBB = CCBI->getFailureBB();
auto ThisBB = CCBI->getParent();
bool MadeChange = false;
CastOptimizer CastOpt(
FuncBuilder, nullptr /*SILBuilderContext*/,
/* replaceValueUsesAction */
[&MadeChange](SILValue oldValue, SILValue newValue) {
MadeChange = true;
},
/* replaceInstUsesAction */
[&MadeChange](SILInstruction *I, ValueBase *V) { MadeChange = true; },
/* eraseInstAction */
[&MadeChange](SILInstruction *I) {
MadeChange = true;
I->eraseFromParent();
},
/* willSucceedAction */
[&]() {
MadeChange |= removeIfDead(FailureBB);
addToWorklist(ThisBB);
},
/* willFailAction */
[&]() {
MadeChange |= removeIfDead(SuccessBB);
addToWorklist(ThisBB);
});
MadeChange |= bool(CastOpt.simplifyCheckedCastBranchInst(CCBI));
return MadeChange;
}
bool SimplifyCFG::simplifyCheckedCastValueBranchBlock(
CheckedCastValueBranchInst *CCBI) {
auto SuccessBB = CCBI->getSuccessBB();
auto FailureBB = CCBI->getFailureBB();
auto ThisBB = CCBI->getParent();
bool MadeChange = false;
CastOptimizer CastOpt(
FuncBuilder, nullptr /*SILBuilderContext*/,
/* replaceValueUsesAction */
[&MadeChange](SILValue oldValue, SILValue newValue) {
MadeChange = true;
},
/* replaceInstUsesAction */
[&MadeChange](SILInstruction *I, ValueBase *V) { MadeChange = true; },
/* eraseInstAction */
[&MadeChange](SILInstruction *I) {
MadeChange = true;
I->eraseFromParent();
},
/* willSucceedAction */
[&]() {
MadeChange |= removeIfDead(FailureBB);
addToWorklist(ThisBB);
},
/* willFailAction */
[&]() {
MadeChange |= removeIfDead(SuccessBB);
addToWorklist(ThisBB);
});
MadeChange |= bool(CastOpt.simplifyCheckedCastValueBranchInst(CCBI));
return MadeChange;
}
bool
SimplifyCFG::
simplifyCheckedCastAddrBranchBlock(CheckedCastAddrBranchInst *CCABI) {
auto SuccessBB = CCABI->getSuccessBB();
auto FailureBB = CCABI->getFailureBB();
auto ThisBB = CCABI->getParent();
bool MadeChange = false;
CastOptimizer CastOpt(
FuncBuilder, nullptr /*SILBuilderContext*/,
/* replaceValueUsesAction */
[&MadeChange](SILValue, SILValue) { MadeChange = true; },
/* replaceInstUsesAction */
[&MadeChange](SILInstruction *I, ValueBase *V) { MadeChange = true; },
/* eraseInstAction */
[&MadeChange](SILInstruction *I) {
MadeChange = true;
I->eraseFromParent();
},
/* willSucceedAction */
[&]() {
MadeChange |= removeIfDead(FailureBB);
addToWorklist(ThisBB);
},
/* willFailAction */
[&]() {
MadeChange |= removeIfDead(SuccessBB);
addToWorklist(ThisBB);
});
MadeChange |= bool(CastOpt.simplifyCheckedCastAddrBranchInst(CCABI));
return MadeChange;
}
static SILValue getActualCallee(SILValue Callee) {
while (!isa<FunctionRefInst>(Callee)) {
if (auto *CFI = dyn_cast<ConvertFunctionInst>(Callee)) {
Callee = CFI->getConverted();
continue;
}
if (auto *Cvt = dyn_cast<ConvertEscapeToNoEscapeInst>(Callee)) {
Callee = Cvt->getConverted();
continue;
}
if (auto *TTI = dyn_cast<ThinToThickFunctionInst>(Callee)) {
Callee = TTI->getConverted();
continue;
}
break;
}
return Callee;
}
/// Checks if the callee of \p TAI is a convert from a function without
/// error result.
static bool isTryApplyOfConvertFunction(TryApplyInst *TAI,
SILValue &Callee,
SILType &CalleeType) {
auto CalleeOperand = TAI->getCallee();
// Look through a @noescape conversion.
auto *Cvt = dyn_cast<ConvertEscapeToNoEscapeInst>(CalleeOperand);
if (Cvt)
CalleeOperand = Cvt->getConverted();
auto *CFI = dyn_cast<ConvertFunctionInst>(CalleeOperand);
if (!CFI)
return false;
// Check if it is a conversion of a non-throwing function into
// a throwing function. If this is the case, replace by a
// simple apply.
auto OrigFnTy = CFI->getConverted()->getType().getAs<SILFunctionType>();
if (!OrigFnTy || OrigFnTy->hasErrorResult())
return false;
auto TargetFnTy = CFI->getType().getAs<SILFunctionType>();
if (!TargetFnTy || !TargetFnTy->hasErrorResult())
return false;
// Look through the conversions and find the real callee.
Callee = getActualCallee(CFI->getConverted());
CalleeType = Callee->getType();
// If it a call of a throwing callee, bail.
auto CalleeFnTy = CalleeType.getAs<SILFunctionType>();
if (!CalleeFnTy || CalleeFnTy->hasErrorResult())
return false;
return true;
}
/// Checks if the error block of \p TAI has just an unreachable instruction.
/// In this case we know that the callee cannot throw.
static bool isTryApplyWithUnreachableError(TryApplyInst *TAI,
SILValue &Callee,
SILType &CalleeType) {
SILBasicBlock *ErrorBlock = TAI->getErrorBB();
TermInst *Term = ErrorBlock->getTerminator();
if (!isa<UnreachableInst>(Term))
return false;
if (&*ErrorBlock->begin() != Term)
return false;
Callee = TAI->getCallee();
CalleeType = TAI->getSubstCalleeSILType();
return true;
}
bool SimplifyCFG::simplifyTryApplyBlock(TryApplyInst *TAI) {
SILValue Callee;
SILType CalleeType;
// Two reasons for converting a try_apply to an apply.
if (isTryApplyOfConvertFunction(TAI, Callee, CalleeType) ||
isTryApplyWithUnreachableError(TAI, Callee, CalleeType)) {
auto CalleeFnTy = CalleeType.castTo<SILFunctionType>();
SILFunctionConventions calleeConv(CalleeFnTy, TAI->getModule());
auto ResultTy = calleeConv.getSILResultType(
TAI->getFunction()->getTypeExpansionContext());
auto OrigResultTy = TAI->getNormalBB()->getArgument(0)->getType();
SILBuilderWithScope Builder(TAI);
auto TargetFnTy = CalleeFnTy;
if (TargetFnTy->isPolymorphic()) {
TargetFnTy = TargetFnTy->substGenericArgs(
TAI->getModule(), TAI->getSubstitutionMap(),
Builder.getTypeExpansionContext());
}
SILFunctionConventions targetConv(TargetFnTy, TAI->getModule());
auto OrigFnTy = TAI->getCallee()->getType().getAs<SILFunctionType>();
if (OrigFnTy->isPolymorphic()) {
OrigFnTy = OrigFnTy->substGenericArgs(TAI->getModule(),
TAI->getSubstitutionMap(),
Builder.getTypeExpansionContext());
}
SILFunctionConventions origConv(OrigFnTy, TAI->getModule());
auto context = TAI->getFunction()->getTypeExpansionContext();
SmallVector<SILValue, 8> Args;
unsigned numArgs = TAI->getNumArguments();
for (unsigned i = 0; i < numArgs; ++i) {
auto Arg = TAI->getArgument(i);
// Cast argument if required.
std::tie(Arg, std::ignore) = castValueToABICompatibleType(
&Builder, TAI->getLoc(), Arg, origConv.getSILArgumentType(i, context),
targetConv.getSILArgumentType(i, context));
Args.push_back(Arg);
}
assert(calleeConv.getNumSILArguments() == Args.size()
&& "The number of arguments should match");
LLVM_DEBUG(llvm::dbgs() << "replace with apply: " << *TAI);
ApplyInst *NewAI = Builder.createApply(TAI->getLoc(), Callee,
TAI->getSubstitutionMap(),
Args, CalleeFnTy->hasErrorResult());
auto Loc = TAI->getLoc();
auto *NormalBB = TAI->getNormalBB();
SILValue CastedResult;
std::tie(CastedResult, std::ignore) = castValueToABICompatibleType(
&Builder, Loc, NewAI, ResultTy, OrigResultTy);
Builder.createBranch(Loc, NormalBB, { CastedResult });
TAI->eraseFromParent();
return true;
}
return false;
}
// Replace the terminator of BB with a simple branch if all successors go
// to trampoline jumps to the same destination block. The successor blocks
// and the destination blocks may have no arguments.
bool SimplifyCFG::simplifyTermWithIdenticalDestBlocks(SILBasicBlock *BB) {
TrampolineDest commonDest;
for (auto *SuccBlock : BB->getSuccessorBlocks()) {
if (SuccBlock->getNumArguments() != 0)
return false;
auto trampolineDest = TrampolineDest(BB, SuccBlock);
if (!trampolineDest) {
return false;
}
// The branch must have the same destination and same branch arguments.
if (!commonDest) {
commonDest = std::move(trampolineDest);
} else if (trampolineDest != commonDest) {
return false;
}
}
if (!commonDest) {
return false;
}
TermInst *Term = BB->getTerminator();
LLVM_DEBUG(llvm::dbgs() << "replace term with identical dests: " << *Term);
SILBuilderWithScope(Term).createBranch(Term->getLoc(), commonDest.destBB,
commonDest.newSourceBranchArgs);
Term->eraseFromParent();
addToWorklist(BB);
addToWorklist(commonDest.destBB);
return true;
}
/// Checks if the block contains a cond_fail as first side-effect instruction
/// and tries to move it to the predecessors (if beneficial). A sequence
///
/// bb1:
/// br bb3(%c)
/// bb2:
/// %i = integer_literal
/// br bb3(%i) // at least one input argument must be constant
/// bb3(%a) // = BB
/// cond_fail %a // %a must not have other uses
///
/// is replaced with
///
/// bb1:
/// cond_fail %c
/// br bb3(%c)
/// bb2:
/// %i = integer_literal
/// cond_fail %i
/// br bb3(%i)
/// bb3(%a) // %a is dead
///
static bool tryMoveCondFailToPreds(SILBasicBlock *BB) {
CondFailInst *CFI = getFirstCondFail(BB);
if (!CFI)
return false;
// Find the underlying condition value of the cond_fail.
// We only accept single uses. This is not a correctness check, but we only
// want to the optimization if the condition gets dead after moving the
// cond_fail.
bool inverted = false;
SILValue cond = skipInvert(CFI->getOperand(), inverted, true);
if (!cond)
return false;
// Check if the condition is a single-used argument in the current block.
auto *condArg = dyn_cast<SILArgument>(cond);
if (!condArg || !condArg->hasOneUse())
return false;
if (condArg->getParent() != BB)
return false;
// Check if some of the predecessor blocks provide a constant for the
// cond_fail condition. So that the optimization has a positive effect.
bool somePredsAreConst = false;
for (auto *Pred : BB->getPredecessorBlocks()) {
// The cond_fail must post-dominate the predecessor block. We may not
// execute the cond_fail speculatively.
if (!Pred->getSingleSuccessorBlock())
return false;
// If we already found a constant pred, we do not need to check the incoming
// value to see if it is constant. We are already going to perform the
// optimization.
if (somePredsAreConst)
continue;
SILValue incoming = condArg->getIncomingPhiValue(Pred);
somePredsAreConst |= isa<IntegerLiteralInst>(incoming);
}
if (!somePredsAreConst)
return false;
LLVM_DEBUG(llvm::dbgs() << "move to predecessors: " << *CFI);
// Move the cond_fail to the predecessor blocks.
for (auto *Pred : BB->getPredecessorBlocks()) {
SILValue incoming = condArg->getIncomingPhiValue(Pred);
SILBuilderWithScope Builder(Pred->getTerminator());
createCondFail(CFI, incoming, CFI->getMessage(), inverted, Builder);
}
CFI->eraseFromParent();
return true;
}
bool SimplifyCFG::simplifyBlocks() {
bool Changed = false;
// Add all of the blocks to the function.
for (auto &BB : Fn)
addToWorklist(&BB);
// Iteratively simplify while there is still work to do.
while (SILBasicBlock *BB = popWorklist()) {
// If the block is dead, remove it.
if (removeIfDead(BB)) {
Changed = true;
continue;
}
// Otherwise, try to simplify the terminator.
TermInst *TI = BB->getTerminator();
switch (TI->getTermKind()) {
case TermKind::BranchInst:
if (simplifyBranchBlock(cast<BranchInst>(TI))) {
Changed = true;
continue;
}
// If this unconditional branch has BBArgs, check to see if duplicating
// the destination would allow it to be simplified. This is a simple form
// of jump threading.
if (!isVeryLargeFunction && tryJumpThreading(cast<BranchInst>(TI))) {
Changed = true;
continue;
}
break;
case TermKind::CondBranchInst:
Changed |= simplifyCondBrBlock(cast<CondBranchInst>(TI));
break;
case TermKind::SwitchValueInst:
// FIXME: Optimize for known switch values.
Changed |= simplifySwitchValueBlock(cast<SwitchValueInst>(TI));
break;
case TermKind::SwitchEnumInst: {
auto *SEI = cast<SwitchEnumInst>(TI);
if (simplifySwitchEnumBlock(SEI)) {
Changed = true;
} else if (simplifySwitchEnumOnObjcClassOptional(SEI)) {
Changed = true;
} else {
Changed |= simplifySwitchEnumUnreachableBlocks(SEI);
}
Changed |= simplifyTermWithIdenticalDestBlocks(BB);
break;
}
case TermKind::UnreachableInst:
Changed |= simplifyUnreachableBlock(cast<UnreachableInst>(TI));
break;
case TermKind::CheckedCastBranchInst:
Changed |= simplifyCheckedCastBranchBlock(cast<CheckedCastBranchInst>(TI));
break;
case TermKind::CheckedCastValueBranchInst:
Changed |= simplifyCheckedCastValueBranchBlock(
cast<CheckedCastValueBranchInst>(TI));
break;
case TermKind::CheckedCastAddrBranchInst:
Changed |= simplifyCheckedCastAddrBranchBlock(cast<CheckedCastAddrBranchInst>(TI));
break;
case TermKind::TryApplyInst:
Changed |= simplifyTryApplyBlock(cast<TryApplyInst>(TI));
break;
case TermKind::SwitchEnumAddrInst:
Changed |= simplifyTermWithIdenticalDestBlocks(BB);
break;
case TermKind::ThrowInst:
case TermKind::DynamicMethodBranchInst:
case TermKind::ReturnInst:
case TermKind::UnwindInst:
case TermKind::YieldInst:
break;
case TermKind::AwaitAsyncContinuationInst:
// TODO(async): Simplify AwaitAsyncContinuationInst
break;
}
// If the block has a cond_fail, try to move it to the predecessors.
Changed |= tryMoveCondFailToPreds(BB);
// Simplify the block argument list.
Changed |= simplifyArgs(BB);
// Simplify the program termination block.
Changed |= simplifyProgramTerminationBlock(BB);
}
return Changed;
}
/// Canonicalize all switch_enum and switch_enum_addr instructions.
/// If possible, replace the default with the corresponding unique case.
bool SimplifyCFG::canonicalizeSwitchEnums() {
bool Changed = false;
for (auto &BB : Fn) {
TermInst *TI = BB.getTerminator();
SwitchEnumTermInst SWI(TI);
if (!SWI)
continue;
if (!SWI.hasDefault())
continue;
NullablePtr<EnumElementDecl> elementDecl = SWI.getUniqueCaseForDefault();
if (!elementDecl)
continue;
// Construct a new instruction by copying all the case entries.
SmallVector<std::pair<EnumElementDecl*, SILBasicBlock*>, 4> CaseBBs;
for (int idx = 0, numIdcs = SWI.getNumCases(); idx < numIdcs; ++idx) {
CaseBBs.push_back(SWI.getCase(idx));
}
// Add the default-entry of the original instruction as case-entry.
CaseBBs.push_back(std::make_pair(elementDecl.get(), SWI.getDefaultBB()));
if (isa<SwitchEnumInst>(*SWI)) {
SILBuilderWithScope(SWI).createSwitchEnum(SWI->getLoc(), SWI.getOperand(),
nullptr, CaseBBs);
} else {
assert(isa<SwitchEnumAddrInst>(*SWI) &&
"unknown switch_enum instruction");
SILBuilderWithScope(SWI).createSwitchEnumAddr(
SWI->getLoc(), SWI.getOperand(), nullptr, CaseBBs);
}
SWI->eraseFromParent();
Changed = true;
}
return Changed;
}
static SILBasicBlock *isObjCMethodCallBlock(SILBasicBlock &Block) {
auto *Branch = dyn_cast<BranchInst>(Block.getTerminator());
if (!Branch)
return nullptr;
for (auto &Inst : Block) {
// Look for an objc method call.
auto *Apply = dyn_cast<ApplyInst>(&Inst);
if (!Apply)
continue;
auto *Callee = dyn_cast<ObjCMethodInst>(Apply->getCallee());
if (!Callee)
continue;
return Branch->getDestBB();
}
return nullptr;
}
/// We want to duplicate small blocks that contain a least on release and have
/// multiple predecessor.
static bool shouldTailDuplicate(SILBasicBlock &Block) {
unsigned Cost = 0;
bool SawRelease = false;
if (Block.getTerminator()->isFunctionExiting())
return false;
if (Block.getSinglePredecessorBlock())
return false;
for (auto &Inst : Block) {
if (!Inst.isTriviallyDuplicatable())
return false;
if (FullApplySite::isa(&Inst))
return false;
if (isa<ReleaseValueInst>(&Inst) ||
isa<StrongReleaseInst>(&Inst))
SawRelease = true;
if (instructionInlineCost(Inst) != InlineCost::Free)
if (++Cost == 12)
return false;
}
return SawRelease;
}
/// Tail duplicate successor blocks of blocks that perform an objc method call
/// and who contain releases. Cloning such blocks can allow ARC to sink retain
/// releases onto the ObjC path.
bool SimplifyCFG::tailDuplicateObjCMethodCallSuccessorBlocks() {
SmallVector<SILBasicBlock *,