Differential D40146 Diff 125992 llvm/lib/Transforms/Scalar/JumpThreading.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Scalar/JumpThreading.cpp

Show All 31 Lines
#include "llvm/Analysis/TargetLibraryInfo.h"		#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"		#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"		#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"		#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"		#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"		#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"		#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"		#include "llvm/IR/DataLayout.h"
		#include "llvm/IR/DeferredDominance.h"
#include "llvm/IR/Dominators.h"		#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"		#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"		#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"		#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"		#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"		#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"		#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"		#include "llvm/IR/LLVMContext.h"
▲ Show 20 Lines • Show All 78 Lines • ▼ Show 20 Lines	public:

JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {		JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
initializeJumpThreadingPass(*PassRegistry::getPassRegistry());		initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
}		}

bool runOnFunction(Function &F) override;		bool runOnFunction(Function &F) override;

void getAnalysisUsage(AnalysisUsage &AU) const override {		void getAnalysisUsage(AnalysisUsage &AU) const override {
if (PrintLVIAfterJumpThreading)
AU.addRequired<DominatorTreeWrapperPass>();		AU.addRequired<DominatorTreeWrapperPass>();
		AU.addPreserved<DominatorTreeWrapperPass>();
AU.addRequired<AAResultsWrapperPass>();		AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<LazyValueInfoWrapperPass>();		AU.addRequired<LazyValueInfoWrapperPass>();
		AU.addPreserved<LazyValueInfoWrapperPass>();
AU.addPreserved<GlobalsAAWrapperPass>();		AU.addPreserved<GlobalsAAWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();		AU.addRequired<TargetLibraryInfoWrapperPass>();
}		}

void releaseMemory() override { Impl.releaseMemory(); }		void releaseMemory() override { Impl.releaseMemory(); }
};		};

} // end anonymous namespace		} // end anonymous namespace

char JumpThreading::ID = 0;		char JumpThreading::ID = 0;

INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",		INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
"Jump Threading", false, false)		"Jump Threading", false, false)
		INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)		INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)		INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(JumpThreading, "jump-threading",		INITIALIZE_PASS_END(JumpThreading, "jump-threading",
"Jump Threading", false, false)		"Jump Threading", false, false)

// Public interface to the Jump Threading pass		// Public interface to the Jump Threading pass
FunctionPass *llvm::createJumpThreadingPass(int Threshold) {		FunctionPass *llvm::createJumpThreadingPass(int Threshold) {
▲ Show 20 Lines • Show All 114 Lines • ▼ Show 20 Lines	static void updatePredecessorProfileMetadata(PHINode PN, BasicBlock BB) {
}		}
}		}

/// runOnFunction - Toplevel algorithm.		/// runOnFunction - Toplevel algorithm.
bool JumpThreading::runOnFunction(Function &F) {		bool JumpThreading::runOnFunction(Function &F) {
if (skipFunction(F))		if (skipFunction(F))
return false;		return false;
auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();		auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
		// Get DT analysis before LVI. When LVI is initialized it conditionally adds
		// DT if it's available.
		auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();		auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();		auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
		DeferredDominance *DDT = new DeferredDominance(DT);
		kuharUnsubmitted Done Reply Inline Actions One remark: why new here instead of just putting it on the stack? If you need to pass the ownership around, who deallocates it? kuhar: One remark: why new here instead of just putting it on the stack? If you need to pass the…
		brzyckiAuthorUnsubmitted Done Reply Inline Actions Ah, I forgot I had that. This is stale code from an older attempt at working the class into JumpThreading. I'll fix it in the next diff. Thanks for catching this. brzycki: Ah, I forgot I had that. This is stale code from an older attempt at working the class into…
		kuharUnsubmitted Done Reply Inline Actions Nit: `DeferredDominance DDT = DeferredDominance(DT)` can be just `DeferredDominance DDT(DT);` kuhar: Nit: `DeferredDominance DDT = DeferredDominance(DT)` can be just `DeferredDominance DDT(DT);`
std::unique_ptr<BlockFrequencyInfo> BFI;		std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;		std::unique_ptr<BranchProbabilityInfo> BPI;
bool HasProfileData = F.getEntryCount().hasValue();		bool HasProfileData = F.getEntryCount().hasValue();
if (HasProfileData) {		if (HasProfileData) {
LoopInfo LI{DominatorTree(F)};		LoopInfo LI{DominatorTree(F)};
BPI.reset(new BranchProbabilityInfo(F, LI, TLI));		BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));		BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
}		}

bool Changed = Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI),		bool Changed = Impl.runImpl(F, TLI, LVI, AA, DDT, HasProfileData,
std::move(BPI));		std::move(BFI), std::move(BPI));
if (PrintLVIAfterJumpThreading) {		if (PrintLVIAfterJumpThreading) {
dbgs() << "LVI for function '" << F.getName() << "':\n";		dbgs() << "LVI for function '" << F.getName() << "':\n";
LVI->printLVI(F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),		LVI->printLVI(F, *DT, dbgs());
dbgs());
}		}
return Changed;		return Changed;
}		}

PreservedAnalyses JumpThreadingPass::run(Function &F,		PreservedAnalyses JumpThreadingPass::run(Function &F,
FunctionAnalysisManager &AM) {		FunctionAnalysisManager &AM) {
auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);		auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
		// Get DT analysis before LVI. When LVI is initialized it conditionally adds
		// DT if it's available.
		auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
auto &LVI = AM.getResult<LazyValueAnalysis>(F);		auto &LVI = AM.getResult<LazyValueAnalysis>(F);
auto &AA = AM.getResult<AAManager>(F);		auto &AA = AM.getResult<AAManager>(F);
		DeferredDominance *DDT = new DeferredDominance(&DT);

std::unique_ptr<BlockFrequencyInfo> BFI;		std::unique_ptr<BlockFrequencyInfo> BFI;
std::unique_ptr<BranchProbabilityInfo> BPI;		std::unique_ptr<BranchProbabilityInfo> BPI;
bool HasProfileData = F.getEntryCount().hasValue();		bool HasProfileData = F.getEntryCount().hasValue();
if (HasProfileData) {		if (HasProfileData) {
LoopInfo LI{DominatorTree(F)};		LoopInfo LI{DominatorTree(F)};
BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));		BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));		BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
}		}

bool Changed = runImpl(F, &TLI, &LVI, &AA, HasProfileData, std::move(BFI),		bool Changed = runImpl(F, &TLI, &LVI, &AA, DDT, HasProfileData,
std::move(BPI));		std::move(BFI), std::move(BPI));

if (!Changed)		if (!Changed)
return PreservedAnalyses::all();		return PreservedAnalyses::all();
PreservedAnalyses PA;		PreservedAnalyses PA;
PA.preserve<GlobalsAA>();		PA.preserve<GlobalsAA>();
		PA.preserve<DominatorTreeAnalysis>();
		PA.preserve<LazyValueAnalysis>();
return PA;		return PA;
}		}

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,		bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
LazyValueInfo LVI_, AliasAnalysis AA_,		LazyValueInfo LVI_, AliasAnalysis AA_,
bool HasProfileData_,		DeferredDominance *DDT_, bool HasProfileData_,
std::unique_ptr<BlockFrequencyInfo> BFI_,		std::unique_ptr<BlockFrequencyInfo> BFI_,
std::unique_ptr<BranchProbabilityInfo> BPI_) {		std::unique_ptr<BranchProbabilityInfo> BPI_) {
DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");		DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
TLI = TLI_;		TLI = TLI_;
LVI = LVI_;		LVI = LVI_;
AA = AA_;		AA = AA_;
		DDT = DDT_;
BFI.reset();		BFI.reset();
BPI.reset();		BPI.reset();
// When profile data is available, we need to update edge weights after		// When profile data is available, we need to update edge weights after
// successful jump threading, which requires both BPI and BFI being available.		// successful jump threading, which requires both BPI and BFI being available.
HasProfileData = HasProfileData_;		HasProfileData = HasProfileData_;
auto *GuardDecl = F.getParent()->getFunction(		auto *GuardDecl = F.getParent()->getFunction(
Intrinsic::getName(Intrinsic::experimental_guard));		Intrinsic::getName(Intrinsic::experimental_guard));
HasGuards = GuardDecl && !GuardDecl->use_empty();		HasGuards = GuardDecl && !GuardDecl->use_empty();
if (HasProfileData) {		if (HasProfileData) {
BPI = std::move(BPI_);		BPI = std::move(BPI_);
BFI = std::move(BFI_);		BFI = std::move(BFI_);
}		}

// Remove unreachable blocks from function as they may result in infinite		// Remove unreachable blocks from function as they may result in infinite
// loop. We do threading if we found something profitable. Jump threading a		// loop. We do threading if we found something profitable. Jump threading a
// branch can create other opportunities. If these opportunities form a cycle		// branch can create other opportunities. If these opportunities form a cycle
// i.e. if any jump threading is undoing previous threading in the path, then		// i.e. if any jump threading is undoing previous threading in the path, then
// we will loop forever. We take care of this issue by not jump threading for		// we will loop forever. We take care of this issue by not jump threading for
// back edges. This works for normal cases but not for unreachable blocks as		// back edges. This works for normal cases but not for unreachable blocks as
// they may have cycle with no back edge.		// they may have cycle with no back edge.
bool EverChanged = false;		bool EverChanged = false;
EverChanged \|= removeUnreachableBlocks(F, LVI);		EverChanged \|= removeUnreachableBlocks(F, LVI, DDT);

FindLoopHeaders(F);		FindLoopHeaders(F);

bool Changed;		bool Changed;
do {		do {
Changed = false;		Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E;) {		for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
BasicBlock BB = &I;		BasicBlock BB = &I;
// Thread all of the branches we can over this block.		// Thread all of the branches we can over this block.
while (ProcessBlock(BB))		while (ProcessBlock(BB))
Changed = true;		Changed = true;

++I;		++I;

		// Don't thread branches over a block that's slated for deletion.
		if (DDT->pendingDeletedBB(BB))
		continue;

// If the block is trivially dead, zap it. This eliminates the successor		// If the block is trivially dead, zap it. This eliminates the successor
// edges which simplifies the CFG.		// edges which simplifies the CFG.
if (pred_empty(BB) &&		if (pred_empty(BB) &&
BB != &BB->getParent()->getEntryBlock()) {		BB != &BB->getParent()->getEntryBlock()) {
DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()		DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n');		<< "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB);		LoopHeaders.erase(BB);
LVI->eraseBlock(BB);		LVI->eraseBlock(BB);
DeleteDeadBlock(BB);		DeleteDeadBlock(BB, DDT);
Changed = true;		Changed = true;
continue;		continue;
}		}

BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());		BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());

// Can't thread an unconditional jump, but if the block is "almost		// Can't thread an unconditional jump, but if the block is "almost
// empty", we can replace uses of it with uses of the successor and make		// empty", we can replace uses of it with uses of the successor and make
// this dead.		// this dead.
// We should not eliminate the loop header or latch either, because		// We should not eliminate the loop header or latch either, because
// eliminating a loop header or latch might later prevent LoopSimplify		// eliminating a loop header or latch might later prevent LoopSimplify
// from transforming nested loops into simplified form. We will rely on		// from transforming nested loops into simplified form. We will rely on
// later passes in backend to clean up empty blocks.		// later passes in backend to clean up empty blocks.
if (BI && BI->isUnconditional() &&		if (BI && BI->isUnconditional() &&
BB != &BB->getParent()->getEntryBlock() &&		BB != &BB->getParent()->getEntryBlock() &&
// If the terminator is the only non-phi instruction, try to nuke it.		// If the terminator is the only non-phi instruction, try to nuke it.
BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&		BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&
!LoopHeaders.count(BI->getSuccessor(0))) {		!LoopHeaders.count(BI->getSuccessor(0))) {
// FIXME: It is always conservatively correct to drop the info		// FIXME: It is always conservatively correct to drop the info
// for a block even if it doesn't get erased. This isn't totally		// for a block even if it doesn't get erased. This isn't totally
// awesome, but it allows us to use AssertingVH to prevent nasty		// awesome, but it allows us to use AssertingVH to prevent nasty
// dangling pointer issues within LazyValueInfo.		// dangling pointer issues within LazyValueInfo.
LVI->eraseBlock(BB);		LVI->eraseBlock(BB);
if (TryToSimplifyUncondBranchFromEmptyBlock(BB))		if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DDT))
Changed = true;		Changed = true;
}		}
}		}
EverChanged \|= Changed;		EverChanged \|= Changed;
} while (Changed);		} while (Changed);

LoopHeaders.clear();		LoopHeaders.clear();
		DDT->flush();
return EverChanged;		return EverChanged;
}		}

// Replace uses of Cond with ToVal when safe to do so. If all uses are		// Replace uses of Cond with ToVal when safe to do so. If all uses are
// replaced, we can remove Cond. We cannot blindly replace all uses of Cond		// replaced, we can remove Cond. We cannot blindly replace all uses of Cond
// because we may incorrectly replace uses when guards/assumes are uses of		// because we may incorrectly replace uses when guards/assumes are uses of
// of `Cond` and we used the guards/assume to reason about the `Cond` value		// of `Cond` and we used the guards/assume to reason about the `Cond` value
// at the end of block. RAUW unconditionally replaces all uses		// at the end of block. RAUW unconditionally replaces all uses
▲ Show 20 Lines • Show All 507 Lines • ▼ Show 20 Lines	static bool hasAddressTakenAndUsed(BasicBlock *BB) {
return !BA->use_empty();		return !BA->use_empty();
}		}

/// ProcessBlock - If there are any predecessors whose control can be threaded		/// ProcessBlock - If there are any predecessors whose control can be threaded
/// through to a successor, transform them now.		/// through to a successor, transform them now.
bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {		bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
// If the block is trivially dead, just return and let the caller nuke it.		// If the block is trivially dead, just return and let the caller nuke it.
// This simplifies other transformations.		// This simplifies other transformations.
if (pred_empty(BB) &&		if (DDT->pendingDeletedBB(BB) \|\|
BB != &BB->getParent()->getEntryBlock())		(pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
return false;		return false;

// If this block has a single predecessor, and if that pred has a single		// If this block has a single predecessor, and if that pred has a single
// successor, merge the blocks. This encourages recursive jump threading		// successor, merge the blocks. This encourages recursive jump threading
// because now the condition in this block can be threaded through		// because now the condition in this block can be threaded through
// predecessors of our predecessor block.		// predecessors of our predecessor block.
if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {		if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
const TerminatorInst *TI = SinglePred->getTerminator();		const TerminatorInst *TI = SinglePred->getTerminator();
if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&		if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
SinglePred != BB && !hasAddressTakenAndUsed(BB)) {		SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
// If SinglePred was a loop header, BB becomes one.		// If SinglePred was a loop header, BB becomes one.
if (LoopHeaders.erase(SinglePred))		if (LoopHeaders.erase(SinglePred))
LoopHeaders.insert(BB);		LoopHeaders.insert(BB);

LVI->eraseBlock(SinglePred);		LVI->eraseBlock(SinglePred);
MergeBasicBlockIntoOnlyPred(BB);		MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT);

// Now that BB is merged into SinglePred (i.e. SinglePred Code followed by		// Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
// BB code within one basic block `BB`), we need to invalidate the LVI		// BB code within one basic block `BB`), we need to invalidate the LVI
// information associated with BB, because the LVI information need not be		// information associated with BB, because the LVI information need not be
// true for all of BB after the merge. For example,		// true for all of BB after the merge. For example,
// Before the merge, LVI info and code is as follows:		// Before the merge, LVI info and code is as follows:
// SinglePred: <LVI info1 for %p val>		// SinglePred: <LVI info1 for %p val>
// %y = use of %p		// %y = use of %p
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines	if (SimpleVal) {
Condition = SimpleVal;		Condition = SimpleVal;
}		}
}		}

// If the terminator is branching on an undef, we can pick any of the		// If the terminator is branching on an undef, we can pick any of the
// successors to branch to. Let GetBestDestForJumpOnUndef decide.		// successors to branch to. Let GetBestDestForJumpOnUndef decide.
if (isa<UndefValue>(Condition)) {		if (isa<UndefValue>(Condition)) {
unsigned BestSucc = GetBestDestForJumpOnUndef(BB);		unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
		std::vector<DominatorTree::UpdateType> Updates;

// Fold the branch/switch.		// Fold the branch/switch.
TerminatorInst *BBTerm = BB->getTerminator();		TerminatorInst *BBTerm = BB->getTerminator();
for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {		for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
if (i == BestSucc) continue;		if (i == BestSucc) continue;
BBTerm->getSuccessor(i)->removePredecessor(BB, true);		BasicBlock *Succ = BBTerm->getSuccessor(i);
		Succ->removePredecessor(BB, true);
		Updates.push_back({DominatorTree::Delete, BB, Succ});
}		}

DEBUG(dbgs() << " In block '" << BB->getName()		DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding undef terminator: " << *BBTerm << '\n');		<< "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);		BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent();		BBTerm->eraseFromParent();
		DDT->applyUpdates(Updates);
return true;		return true;
}		}

// If the terminator of this block is branching on a constant, simplify the		// If the terminator of this block is branching on a constant, simplify the
// terminator to an unconditional branch. This can occur due to threading in		// terminator to an unconditional branch. This can occur due to threading in
// other blocks.		// other blocks.
if (getKnownConstant(Condition, Preference)) {		if (getKnownConstant(Condition, Preference)) {
DEBUG(dbgs() << " In block '" << BB->getName()		DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding terminator: " << *BB->getTerminator() << '\n');		<< "' folding terminator: " << *BB->getTerminator() << '\n');
++NumFolds;		++NumFolds;
ConstantFoldTerminator(BB, true);		ConstantFoldTerminator(BB, true, nullptr, DDT);
return true;		return true;
}		}

Instruction *CondInst = dyn_cast<Instruction>(Condition);		Instruction *CondInst = dyn_cast<Instruction>(Condition);

// All the rest of our checks depend on the condition being an instruction.		// All the rest of our checks depend on the condition being an instruction.
if (!CondInst) {		if (!CondInst) {
// FIXME: Unify this with code below.		// FIXME: Unify this with code below.
Show All 16 Lines	if (CondBr && CondConst) {
assert(CondBr->isConditional() && "Threading on unconditional terminator");		assert(CondBr->isConditional() && "Threading on unconditional terminator");

LazyValueInfo::Tristate Ret =		LazyValueInfo::Tristate Ret =
LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),		LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
CondConst, CondBr);		CondConst, CondBr);
if (Ret != LazyValueInfo::Unknown) {		if (Ret != LazyValueInfo::Unknown) {
unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;		unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;		unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);		BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
		ToRemoveSucc->removePredecessor(BB, true);
BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);		BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
CondBr->eraseFromParent();		CondBr->eraseFromParent();
if (CondCmp->use_empty())		if (CondCmp->use_empty())
CondCmp->eraseFromParent();		CondCmp->eraseFromParent();
// We can safely replace some uses of the CondInst if it has		// We can safely replace some uses of the CondInst if it has
// exactly one value as returned by LVI. RAUW is incorrect in the		// exactly one value as returned by LVI. RAUW is incorrect in the
// presence of guards and assumes, that have the `Cond` as the use. This		// presence of guards and assumes, that have the `Cond` as the use. This
// is because we use the guards/assume to reason about the `Cond` value		// is because we use the guards/assume to reason about the `Cond` value
// at the end of block, but RAUW unconditionally replaces all uses		// at the end of block, but RAUW unconditionally replaces all uses
// including the guards/assumes themselves and the uses before the		// including the guards/assumes themselves and the uses before the
// guard/assume.		// guard/assume.
else if (CondCmp->getParent() == BB) {		else if (CondCmp->getParent() == BB) {
auto *CI = Ret == LazyValueInfo::True ?		auto *CI = Ret == LazyValueInfo::True ?
ConstantInt::getTrue(CondCmp->getType()) :		ConstantInt::getTrue(CondCmp->getType()) :
ConstantInt::getFalse(CondCmp->getType());		ConstantInt::getFalse(CondCmp->getType());
ReplaceFoldableUses(CondCmp, CI);		ReplaceFoldableUses(CondCmp, CI);
}		}
		DDT->deleteEdge(BB, ToRemoveSucc);
return true;		return true;
}		}

// We did not manage to simplify this branch, try to see whether		// We did not manage to simplify this branch, try to see whether
// CondCmp depends on a known phi-select pattern.		// CondCmp depends on a known phi-select pattern.
if (TryToUnfoldSelect(CondCmp, BB))		if (TryToUnfoldSelect(CondCmp, BB))
return true;		return true;
}		}
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines	if (!PBI \|\| !PBI->isConditional())
return false;		return false;
if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)		if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
return false;		return false;

bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;		bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
Optional<bool> Implication =		Optional<bool> Implication =
isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);		isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
if (Implication) {		if (Implication) {
BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);		BasicBlock KeepSucc = BI->getSuccessor(Implication ? 0 : 1);
BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);		BasicBlock RemoveSucc = BI->getSuccessor(Implication ? 1 : 0);
		RemoveSucc->removePredecessor(BB);
		BranchInst::Create(KeepSucc, BI);
BI->eraseFromParent();		BI->eraseFromParent();
		DDT->deleteEdge(BB, RemoveSucc);
return true;		return true;
}		}
CurrentBB = CurrentPred;		CurrentBB = CurrentPred;
CurrentPred = CurrentBB->getSinglePredecessor();		CurrentPred = CurrentBB->getSinglePredecessor();
}		}

return false;		return false;
}		}
▲ Show 20 Lines • Show All 376 Lines • ▼ Show 20 Lines	bool JumpThreadingPass::ProcessThreadableEdges(Value Cond, BasicBlock BB,

// If all the predecessors go to a single known successor, we want to fold,		// If all the predecessors go to a single known successor, we want to fold,
// not thread. By doing so, we do not need to duplicate the current block and		// not thread. By doing so, we do not need to duplicate the current block and
// also miss potential opportunities in case we dont/cant duplicate.		// also miss potential opportunities in case we dont/cant duplicate.
if (OnlyDest && OnlyDest != MultipleDestSentinel) {		if (OnlyDest && OnlyDest != MultipleDestSentinel) {
if (PredWithKnownDest ==		if (PredWithKnownDest ==
(size_t)std::distance(pred_begin(BB), pred_end(BB))) {		(size_t)std::distance(pred_begin(BB), pred_end(BB))) {
bool SeenFirstBranchToOnlyDest = false;		bool SeenFirstBranchToOnlyDest = false;
		std::vector <DominatorTree::UpdateType> Updates;
for (BasicBlock *SuccBB : successors(BB)) {		for (BasicBlock *SuccBB : successors(BB)) {
if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest)		if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.		SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
else		} else {
SuccBB->removePredecessor(BB, true); // This is unreachable successor.		SuccBB->removePredecessor(BB, true); // This is unreachable successor.
		Updates.push_back({DominatorTree::Delete, BB, SuccBB});
		}
}		}

// Finally update the terminator.		// Finally update the terminator.
TerminatorInst *Term = BB->getTerminator();		TerminatorInst *Term = BB->getTerminator();
BranchInst::Create(OnlyDest, Term);		BranchInst::Create(OnlyDest, Term);
Term->eraseFromParent();		Term->eraseFromParent();
		DDT->applyUpdates(Updates);

// If the condition is now dead due to the removal of the old terminator,		// If the condition is now dead due to the removal of the old terminator,
// erase it.		// erase it.
if (auto *CondInst = dyn_cast<Instruction>(Cond)) {		if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())		if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
CondInst->eraseFromParent();		CondInst->eraseFromParent();
// We can safely replace some uses of the CondInst if it has		// We can safely replace some uses of the CondInst if it has
// exactly one value as returned by LVI. RAUW is incorrect in the		// exactly one value as returned by LVI. RAUW is incorrect in the
▲ Show 20 Lines • Show All 347 Lines • ▼ Show 20 Lines	bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
// us to simplify any PHI nodes in BB.		// us to simplify any PHI nodes in BB.
TerminatorInst *PredTerm = PredBB->getTerminator();		TerminatorInst *PredTerm = PredBB->getTerminator();
for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)		for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
if (PredTerm->getSuccessor(i) == BB) {		if (PredTerm->getSuccessor(i) == BB) {
BB->removePredecessor(PredBB, true);		BB->removePredecessor(PredBB, true);
PredTerm->setSuccessor(i, NewBB);		PredTerm->setSuccessor(i, NewBB);
}		}

		DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
		{DominatorTree::Insert, PredBB, NewBB},
		{DominatorTree::Delete, PredBB, BB}});

// At this point, the IR is fully up to date and consistent. Do a quick scan		// At this point, the IR is fully up to date and consistent. Do a quick scan
// over the new instructions and zap any that are constants or dead. This		// over the new instructions and zap any that are constants or dead. This
// frequently happens because of phi translation.		// frequently happens because of phi translation.
SimplifyInstructionsInBlock(NewBB, TLI);		SimplifyInstructionsInBlock(NewBB, TLI);

// Update the edge weight from BB to SuccBB, which should be less than before.		// Update the edge weight from BB to SuccBB, which should be less than before.
UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);		UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);

// Threaded an edge!		// Threaded an edge!
++NumThreads;		++NumThreads;
return true;		return true;
}		}

/// Create a new basic block that will be the predecessor of BB and successor of		/// Create a new basic block that will be the predecessor of BB and successor of
/// all blocks in Preds. When profile data is available, update the frequency of		/// all blocks in Preds. When profile data is available, update the frequency of
/// this new block.		/// this new block.
BasicBlock JumpThreadingPass::SplitBlockPreds(BasicBlock BB,		BasicBlock JumpThreadingPass::SplitBlockPreds(BasicBlock BB,
ArrayRef<BasicBlock *> Preds,		ArrayRef<BasicBlock *> Preds,
const char *Suffix) {		const char *Suffix) {
		std::vector<DominatorTree::UpdateType> Updates;
		SmallVector<BasicBlock *, 2> NewBBs;

// Collect the frequencies of all predecessors of BB, which will be used to		// Collect the frequencies of all predecessors of BB, which will be used to
// update the edge weight on BB->SuccBB.		// update the edge weight of the result of splitting predecessors.
BlockFrequency PredBBFreq(0);		DenseMap<BasicBlock *, BlockFrequency> FreqMap;
if (HasProfileData)		if (HasProfileData)
for (auto Pred : Preds)		for (auto Pred : Preds)
PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB);		FreqMap.insert(std::make_pair(
		Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));

		// In the case when BB is a LandingPad block we create 2 new predecessors
		// instead of just one.
		if (BB->isLandingPad()) {
		std::string NewName = std::string(Suffix) + ".split-lp";
		SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs);
		} else {
		NewBBs.push_back(SplitBlockPredecessors(BB, Preds, Suffix));
		}

BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix);		for (auto NewBB : NewBBs) {
		BlockFrequency NewBBFreq(0);
		Updates.push_back({DominatorTree::Insert, NewBB, BB});
		for (auto Pred : predecessors(NewBB)) {
		Updates.push_back({DominatorTree::Delete, Pred, BB});
		Updates.push_back({DominatorTree::Insert, Pred, NewBB});
		if (HasProfileData) // Update frequencies between Pred -> NewBB.
		NewBBFreq += FreqMap.lookup(Pred);
		}
		sebpopUnsubmitted Done Reply Inline Actions Please add braces around the else clause. sebpop: Please add braces around the else clause.
		if (HasProfileData) // Apply the summed frequency to NewBB.
		BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
		}

// Set the block frequency of the newly created PredBB, which is the sum of		DDT->applyUpdates(Updates);
// frequencies of Preds.		return NewBBs[0];
if (HasProfileData)
BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency());
return PredBB;
}		}

bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {		bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
const TerminatorInst *TI = BB->getTerminator();		const TerminatorInst *TI = BB->getTerminator();
assert(TI->getNumSuccessors() > 1 && "not a split");		assert(TI->getNumSuccessors() > 1 && "not a split");

MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);		MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
if (!WeightsNode)		if (!WeightsNode)
▲ Show 20 Lines • Show All 127 Lines • ▼ Show 20 Lines	unsigned DuplicationCost =
getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);		getJumpThreadDuplicationCost(BB, BB->getTerminator(), BBDupThreshold);
if (DuplicationCost > BBDupThreshold) {		if (DuplicationCost > BBDupThreshold) {
DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()		DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
<< "' - Cost is too high: " << DuplicationCost << "\n");		<< "' - Cost is too high: " << DuplicationCost << "\n");
return false;		return false;
}		}

// And finally, do it! Start by factoring the predecessors if needed.		// And finally, do it! Start by factoring the predecessors if needed.
		std::vector<DominatorTree::UpdateType> Updates;
BasicBlock *PredBB;		BasicBlock *PredBB;
if (PredBBs.size() == 1)		if (PredBBs.size() == 1)
PredBB = PredBBs[0];		PredBB = PredBBs[0];
else {		else {
DEBUG(dbgs() << " Factoring out " << PredBBs.size()		DEBUG(dbgs() << " Factoring out " << PredBBs.size()
<< " common predecessors.\n");		<< " common predecessors.\n");
PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");		PredBB = SplitBlockPreds(BB, PredBBs, ".thr_comm");
}		}
		Updates.push_back({DominatorTree::Delete, PredBB, BB});

// Okay, we decided to do this! Clone all the instructions in BB onto the end		// Okay, we decided to do this! Clone all the instructions in BB onto the end
// of PredBB.		// of PredBB.
DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"		DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"
<< PredBB->getName() << "' to eliminate branch on phi. Cost: "		<< PredBB->getName() << "' to eliminate branch on phi. Cost: "
<< DuplicationCost << " block is:" << *BB << "\n");		<< DuplicationCost << " block is:" << *BB << "\n");

// Unless PredBB ends with an unconditional branch, split the edge so that we		// Unless PredBB ends with an unconditional branch, split the edge so that we
// can just clone the bits from BB into the end of the new PredBB.		// can just clone the bits from BB into the end of the new PredBB.
BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());		BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());

if (!OldPredBranch \|\| !OldPredBranch->isUnconditional()) {		if (!OldPredBranch \|\| !OldPredBranch->isUnconditional()) {
PredBB = SplitEdge(PredBB, BB);		BasicBlock *OldPredBB = PredBB;
		PredBB = SplitEdge(OldPredBB, BB);
		Updates.push_back({DominatorTree::Insert, OldPredBB, PredBB});
		Updates.push_back({DominatorTree::Insert, PredBB, BB});
		Updates.push_back({DominatorTree::Delete, OldPredBB, BB});
OldPredBranch = cast<BranchInst>(PredBB->getTerminator());		OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
}		}

// We are going to have to map operands from the original BB block into the		// We are going to have to map operands from the original BB block into the
// PredBB block. Evaluate PHI nodes in BB.		// PredBB block. Evaluate PHI nodes in BB.
DenseMap<Instruction, Value> ValueMapping;		DenseMap<Instruction, Value> ValueMapping;

BasicBlock::iterator BI = BB->begin();		BasicBlock::iterator BI = BB->begin();
Show All 25 Lines	if (Value *IV = SimplifyInstruction(
}		}
} else {		} else {
ValueMapping[&*BI] = New;		ValueMapping[&*BI] = New;
}		}
if (New) {		if (New) {
// Otherwise, insert the new instruction into the block.		// Otherwise, insert the new instruction into the block.
New->setName(BI->getName());		New->setName(BI->getName());
PredBB->getInstList().insert(OldPredBranch->getIterator(), New);		PredBB->getInstList().insert(OldPredBranch->getIterator(), New);
		// Update Dominance from simplified New instruction operands.
		for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
		if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
		Updates.push_back({DominatorTree::Insert, PredBB, SuccBB});
}		}
}		}

// Check to see if the targets of the branch had PHI nodes. If so, we need to		// Check to see if the targets of the branch had PHI nodes. If so, we need to
// add entries to the PHI nodes for branch from PredBB now.		// add entries to the PHI nodes for branch from PredBB now.
BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());		BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,		AddPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
ValueMapping);		ValueMapping);
Show All 39 Lines	bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
}		}

// PredBB no longer jumps to BB, remove entries in the PHI node for the edge		// PredBB no longer jumps to BB, remove entries in the PHI node for the edge
// that we nuked.		// that we nuked.
BB->removePredecessor(PredBB, true);		BB->removePredecessor(PredBB, true);

// Remove the unconditional branch at the end of the PredBB block.		// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();		OldPredBranch->eraseFromParent();
		DDT->applyUpdates(Updates);

++NumDupes;		++NumDupes;
return true;		return true;
}		}

/// TryToUnfoldSelect - Look for blocks of the form		/// TryToUnfoldSelect - Look for blocks of the form
/// bb1:		/// bb1:
/// %a = select		/// %a = select
▲ Show 20 Lines • Show All 56 Lines • ▼ Show 20 Lines	if ((LHSFolds != LazyValueInfo::Unknown \|\|
NewBB->getInstList().insert(NewBB->end(), PredTerm);		NewBB->getInstList().insert(NewBB->end(), PredTerm);
// Create a conditional branch and update PHI nodes.		// Create a conditional branch and update PHI nodes.
BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);		BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
CondLHS->setIncomingValue(I, SI->getFalseValue());		CondLHS->setIncomingValue(I, SI->getFalseValue());
CondLHS->addIncoming(SI->getTrueValue(), NewBB);		CondLHS->addIncoming(SI->getTrueValue(), NewBB);
// The select is now dead.		// The select is now dead.
SI->eraseFromParent();		SI->eraseFromParent();

		DDT->applyUpdates({{DominatorTree::Insert, NewBB, BB},
		{DominatorTree::Insert, Pred, NewBB}});
// Update any other PHI nodes in BB.		// Update any other PHI nodes in BB.
for (BasicBlock::iterator BI = BB->begin();		for (BasicBlock::iterator BI = BB->begin();
PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)		PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
if (Phi != CondLHS)		if (Phi != CondLHS)
Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);		Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
return true;		return true;
}		}
}		}
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines	for (Use &U : PN->uses()) {
}		}
}		}

if (!SI)		if (!SI)
continue;		continue;
// Expand the select.		// Expand the select.
TerminatorInst *Term =		TerminatorInst *Term =
SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);		SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
		BasicBlock *SplitBB = SI->getParent();
		BasicBlock *NewBB = Term->getParent();
PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);		PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
NewPN->addIncoming(SI->getTrueValue(), Term->getParent());		NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
NewPN->addIncoming(SI->getFalseValue(), BB);		NewPN->addIncoming(SI->getFalseValue(), BB);
SI->replaceAllUsesWith(NewPN);		SI->replaceAllUsesWith(NewPN);
SI->eraseFromParent();		SI->eraseFromParent();
		// NewBB and SplitBB are newly created blocks which require insertion.
		std::vector<DominatorTree::UpdateType> Updates;
		kuharUnsubmitted Done Reply Inline Actions I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation kuhar: I think we can reserve (2 * size(successors(SplitBB)) + 3 here to have a single allocation
		brzyckiAuthorUnsubmitted Done Reply Inline Actions I did this and also added others where the size was trivial to calculate. brzycki: I did this and also added others where the size was trivial to calculate.
		Updates.push_back({DominatorTree::Insert, BB, SplitBB});
		Updates.push_back({DominatorTree::Insert, BB, NewBB});
		Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
		// BB's successors were moved to SplitBB, update DDT accordingly.
		for (auto *Succ : successors(SplitBB)) {
		Updates.push_back({DominatorTree::Delete, BB, Succ});
		Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
		}
		DDT->applyUpdates(Updates);
return true;		return true;
}		}
return false;		return false;
}		}

/// Try to propagate a guard from the current BB into one of its predecessors		/// Try to propagate a guard from the current BB into one of its predecessors
/// in case if another branch of execution implies that the condition of this		/// in case if another branch of execution implies that the condition of this
/// guard is always true. Currently we only process the simplest case that		/// guard is always true. Currently we only process the simplest case that
▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines	else {
Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);		Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
if (Impl && *Impl)		if (Impl && *Impl)
FalseDestIsSafe = true;		FalseDestIsSafe = true;
}		}

if (!TrueDestIsSafe && !FalseDestIsSafe)		if (!TrueDestIsSafe && !FalseDestIsSafe)
return false;		return false;

BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;		BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;		BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;

ValueToValueMapTy UnguardedMapping, GuardedMapping;		ValueToValueMapTy UnguardedMapping, GuardedMapping;
Instruction *AfterGuard = Guard->getNextNode();		Instruction *AfterGuard = Guard->getNextNode();
unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);		unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
if (Cost > BBDupThreshold)		if (Cost > BBDupThreshold)
return false;		return false;
// Duplicate all instructions before the guard and the guard itself to the		// Duplicate all instructions before the guard and the guard itself to the
// branch where implication is not proved.		// branch where implication is not proved.
GuardedBlock = DuplicateInstructionsInSplitBetween(		BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween(
BB, GuardedBlock, AfterGuard, GuardedMapping);		BB, PredGuardedBlock, AfterGuard, GuardedMapping);
assert(GuardedBlock && "Could not create the guarded block?");		assert(GuardedBlock && "Could not create the guarded block?");
// Duplicate all instructions before the guard in the unguarded branch.		// Duplicate all instructions before the guard in the unguarded branch.
// Since we have successfully duplicated the guarded block and this block		// Since we have successfully duplicated the guarded block and this block
// has fewer instructions, we expect it to succeed.		// has fewer instructions, we expect it to succeed.
UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,		BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
Guard, UnguardedMapping);		BB, PredUnguardedBlock, Guard, UnguardedMapping);
assert(UnguardedBlock && "Could not create the unguarded block?");		assert(UnguardedBlock && "Could not create the unguarded block?");
DEBUG(dbgs() << "Moved guard " << *Guard << " to block "		DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
<< GuardedBlock->getName() << "\n");		<< GuardedBlock->getName() << "\n");
		// DuplicateInstructionsInSplitBetween inserts a new block "BB.split" between
		// PredBB and BB. We need to perform two inserts and one delete for each of
		// the above calls to update Dominators.
		DDT->applyUpdates(
		{// Guarded block split.
		{DominatorTree::Delete, PredGuardedBlock, BB},
		{DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
		{DominatorTree::Insert, GuardedBlock, BB},
		// Unguarded block split.
		{DominatorTree::Delete, PredUnguardedBlock, BB},
		{DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
		{DominatorTree::Insert, UnguardedBlock, BB}});
// Some instructions before the guard may still have uses. For them, we need		// Some instructions before the guard may still have uses. For them, we need
// to create Phi nodes merging their copies in both guarded and unguarded		// to create Phi nodes merging their copies in both guarded and unguarded
// branches. Those instructions that have no uses can be just removed.		// branches. Those instructions that have no uses can be just removed.
SmallVector<Instruction *, 4> ToRemove;		SmallVector<Instruction *, 4> ToRemove;
for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)		for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
if (!isa<PHINode>(&*BI))		if (!isa<PHINode>(&*BI))
ToRemove.push_back(&*BI);		ToRemove.push_back(&*BI);

Show All 15 Lines