Differential D40146 Diff 126034 llvm/lib/Transforms/Utils/Local.cpp

Changeset View

Standalone View

llvm/lib/Transforms/Utils/Local.cpp

Show First 20 Lines • Show All 94 Lines • ▼ Show 20 Lines
/// ConstantFoldTerminator - If a terminator instruction is predicated on a		/// ConstantFoldTerminator - If a terminator instruction is predicated on a
/// constant value, convert it into an unconditional branch to the constant		/// constant value, convert it into an unconditional branch to the constant
/// destination. This is a nontrivial operation because the successors of this		/// destination. This is a nontrivial operation because the successors of this
/// basic block must have their PHI nodes updated.		/// basic block must have their PHI nodes updated.
/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch		/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
/// conditions and indirectbr addresses this might make dead if		/// conditions and indirectbr addresses this might make dead if
/// DeleteDeadConditions is true.		/// DeleteDeadConditions is true.
bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,		bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
const TargetLibraryInfo *TLI) {		const TargetLibraryInfo *TLI,
		DeferredDominance *DDT) {
TerminatorInst *T = BB->getTerminator();		TerminatorInst *T = BB->getTerminator();
IRBuilder<> Builder(T);		IRBuilder<> Builder(T);

// Branch - See if we are conditional jumping on constant		// Branch - See if we are conditional jumping on constant
if (BranchInst *BI = dyn_cast<BranchInst>(T)) {		if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
if (BI->isUnconditional()) return false; // Can't optimize uncond branch		if (BI->isUnconditional()) return false; // Can't optimize uncond branch
BasicBlock *Dest1 = BI->getSuccessor(0);		BasicBlock *Dest1 = BI->getSuccessor(0);
BasicBlock *Dest2 = BI->getSuccessor(1);		BasicBlock *Dest2 = BI->getSuccessor(1);
Show All 10 Lines	if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {

// Let the basic block know that we are letting go of it. Based on this,		// Let the basic block know that we are letting go of it. Based on this,
// it will adjust it's PHI nodes.		// it will adjust it's PHI nodes.
OldDest->removePredecessor(BB);		OldDest->removePredecessor(BB);

// Replace the conditional branch with an unconditional one.		// Replace the conditional branch with an unconditional one.
Builder.CreateBr(Destination);		Builder.CreateBr(Destination);
BI->eraseFromParent();		BI->eraseFromParent();
		if (DDT)
		DDT->deleteEdge(BB, OldDest);
return true;		return true;
}		}

if (Dest2 == Dest1) { // Conditional branch to same location?		if (Dest2 == Dest1) { // Conditional branch to same location?
// This branch matches something like this:		// This branch matches something like this:
// br bool %cond, label %Dest, label %Dest		// br bool %cond, label %Dest, label %Dest
// and changes it into: br label %Dest		// and changes it into: br label %Dest

▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines	for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
// Remove weight for this case.		// Remove weight for this case.
std::swap(Weights[idx+1], Weights.back());		std::swap(Weights[idx+1], Weights.back());
Weights.pop_back();		Weights.pop_back();
SI->setMetadata(LLVMContext::MD_prof,		SI->setMetadata(LLVMContext::MD_prof,
MDBuilder(BB->getContext()).		MDBuilder(BB->getContext()).
createBranchWeights(Weights));		createBranchWeights(Weights));
}		}
// Remove this entry.		// Remove this entry.
DefaultDest->removePredecessor(SI->getParent());		BasicBlock *ParentBB = SI->getParent();
		DefaultDest->removePredecessor(ParentBB);
i = SI->removeCase(i);		i = SI->removeCase(i);
e = SI->case_end();		e = SI->case_end();
		if (DDT)
		DDT->deleteEdge(ParentBB, DefaultDest);
continue;		continue;
}		}

// Otherwise, check to see if the switch only branches to one destination.		// Otherwise, check to see if the switch only branches to one destination.
// We do this by reseting "TheOnlyDest" to null when we find two non-equal		// We do this by reseting "TheOnlyDest" to null when we find two non-equal
// destinations.		// destinations.
if (i->getCaseSuccessor() != TheOnlyDest)		if (i->getCaseSuccessor() != TheOnlyDest)
TheOnlyDest = nullptr;		TheOnlyDest = nullptr;
Show All 9 Lines	if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
}		}

// If we found a single destination that we can fold the switch into, do so		// If we found a single destination that we can fold the switch into, do so
// now.		// now.
if (TheOnlyDest) {		if (TheOnlyDest) {
// Insert the new branch.		// Insert the new branch.
Builder.CreateBr(TheOnlyDest);		Builder.CreateBr(TheOnlyDest);
BasicBlock *BB = SI->getParent();		BasicBlock *BB = SI->getParent();
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT)
		Updates.reserve(SI->getNumSuccessors() - 1);

// Remove entries from PHI nodes which we no longer branch to...		// Remove entries from PHI nodes which we no longer branch to...
for (BasicBlock *Succ : SI->successors()) {		for (BasicBlock *Succ : SI->successors()) {
// Found case matching a constant operand?		// Found case matching a constant operand?
if (Succ == TheOnlyDest)		if (Succ == TheOnlyDest) {
TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest		TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
else		} else {
Succ->removePredecessor(BB);		Succ->removePredecessor(BB);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, BB, Succ});
		}
}		}

// Delete the old switch.		// Delete the old switch.
Value *Cond = SI->getCondition();		Value *Cond = SI->getCondition();
SI->eraseFromParent();		SI->eraseFromParent();
if (DeleteDeadConditions)		if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);		RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
		if (DDT)
		DDT->applyUpdates(Updates);
return true;		return true;
}		}

if (SI->getNumCases() == 1) {		if (SI->getNumCases() == 1) {
// Otherwise, we can fold this switch into a conditional branch		// Otherwise, we can fold this switch into a conditional branch
// instruction if it has only one non-default destination.		// instruction if it has only one non-default destination.
auto FirstCase = *SI->case_begin();		auto FirstCase = *SI->case_begin();
Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),		Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
Show All 29 Lines	if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
return false;		return false;
}		}

if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {		if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
// indirectbr blockaddress(@F, @BB) -> br label @BB		// indirectbr blockaddress(@F, @BB) -> br label @BB
if (BlockAddress *BA =		if (BlockAddress *BA =
dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {		dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
BasicBlock *TheOnlyDest = BA->getBasicBlock();		BasicBlock *TheOnlyDest = BA->getBasicBlock();
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT)
		Updates.reserve(IBI->getNumDestinations() - 1);

// Insert the new branch.		// Insert the new branch.
Builder.CreateBr(TheOnlyDest);		Builder.CreateBr(TheOnlyDest);

for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {		for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
if (IBI->getDestination(i) == TheOnlyDest)		if (IBI->getDestination(i) == TheOnlyDest) {
TheOnlyDest = nullptr;		TheOnlyDest = nullptr;
else		} else {
IBI->getDestination(i)->removePredecessor(IBI->getParent());		BasicBlock *ParentBB = IBI->getParent();
		BasicBlock *DestBB = IBI->getDestination(i);
		DestBB->removePredecessor(ParentBB);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
		}
}		}
Value *Address = IBI->getAddress();		Value *Address = IBI->getAddress();
IBI->eraseFromParent();		IBI->eraseFromParent();
if (DeleteDeadConditions)		if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);		RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);

// If we didn't find our destination in the IBI successor list, then we		// If we didn't find our destination in the IBI successor list, then we
// have undefined behavior. Replace the unconditional branch with an		// have undefined behavior. Replace the unconditional branch with an
// 'unreachable' instruction.		// 'unreachable' instruction.
if (TheOnlyDest) {		if (TheOnlyDest) {
BB->getTerminator()->eraseFromParent();		BB->getTerminator()->eraseFromParent();
new UnreachableInst(BB->getContext(), BB);		new UnreachableInst(BB->getContext(), BB);
}		}

		if (DDT)
		DDT->applyUpdates(Updates);
return true;		return true;
}		}
}		}

return false;		return false;
}		}

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
▲ Show 20 Lines • Show All 260 Lines • ▼ Show 20 Lines
///		///
/// Unlike the removePredecessor method, this attempts to simplify uses of PHI		/// Unlike the removePredecessor method, this attempts to simplify uses of PHI
/// nodes that collapse into identity values. For example, if we have:		/// nodes that collapse into identity values. For example, if we have:
/// x = phi(1, 0, 0, 0)		/// x = phi(1, 0, 0, 0)
/// y = and x, z		/// y = and x, z
///		///
/// .. and delete the predecessor corresponding to the '1', this will attempt to		/// .. and delete the predecessor corresponding to the '1', this will attempt to
/// recursively fold the and to 0.		/// recursively fold the and to 0.
void llvm::RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred) {		void llvm::RemovePredecessorAndSimplify(BasicBlock BB, BasicBlock Pred,
		DeferredDominance *DDT) {
// This only adjusts blocks with PHI nodes.		// This only adjusts blocks with PHI nodes.
if (!isa<PHINode>(BB->begin()))		if (!isa<PHINode>(BB->begin()))
return;		return;

// Remove the entries for Pred from the PHI nodes in BB, but do not simplify		// Remove the entries for Pred from the PHI nodes in BB, but do not simplify
// them down. This will leave us with single entry phi nodes and other phis		// them down. This will leave us with single entry phi nodes and other phis
// that can be removed.		// that can be removed.
BB->removePredecessor(Pred, true);		BB->removePredecessor(Pred, true);

WeakTrackingVH PhiIt = &BB->front();		WeakTrackingVH PhiIt = &BB->front();
while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {		while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));		PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
Value *OldPhiIt = PhiIt;		Value *OldPhiIt = PhiIt;

if (!recursivelySimplifyInstruction(PN))		if (!recursivelySimplifyInstruction(PN))
continue;		continue;

// If recursive simplification ended up deleting the next PHI node we would		// If recursive simplification ended up deleting the next PHI node we would
// iterate to, then our iterator is invalid, restart scanning from the top		// iterate to, then our iterator is invalid, restart scanning from the top
// of the block.		// of the block.
if (PhiIt != OldPhiIt) PhiIt = &BB->front();		if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}		}
		if (DDT)
		DDT->deleteEdge(Pred, BB);
}		}

/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its		/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
/// predecessor is known to have one successor (DestBB!). Eliminate the edge		/// predecessor is known to have one successor (DestBB!). Eliminate the edge
/// between them, moving the instructions in the predecessor into DestBB and		/// between them, moving the instructions in the predecessor into DestBB and
/// deleting the predecessor block.		/// deleting the predecessor block.
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock DestBB, DominatorTree DT) {		void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock DestBB, DominatorTree DT,
		DeferredDominance *DDT) {
		assert(!(DT && DDT) && "Cannot call with both DT and DDT.");

// If BB has single-entry PHI nodes, fold them.		// If BB has single-entry PHI nodes, fold them.
while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {		while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
Value *NewVal = PN->getIncomingValue(0);		Value *NewVal = PN->getIncomingValue(0);
// Replace self referencing PHI with undef, it must be dead.		// Replace self referencing PHI with undef, it must be dead.
if (NewVal == PN) NewVal = UndefValue::get(PN->getType());		if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
PN->replaceAllUsesWith(NewVal);		PN->replaceAllUsesWith(NewVal);
PN->eraseFromParent();		PN->eraseFromParent();
}		}

BasicBlock *PredBB = DestBB->getSinglePredecessor();		BasicBlock *PredBB = DestBB->getSinglePredecessor();
assert(PredBB && "Block doesn't have a single predecessor!");		assert(PredBB && "Block doesn't have a single predecessor!");

		bool ReplaceEntryBB = false;
		if (PredBB == &DestBB->getParent()->getEntryBlock())
		ReplaceEntryBB = true;

		// Deferred DT update: Collect all the edges that enter PredBB. These
		// dominator edges will be redirected to DestBB.
		std::vector <DominatorTree::UpdateType> Updates;
		if (DDT && !ReplaceEntryBB) {
		Updates.reserve((2 * std::distance(pred_begin(PredBB), pred_end(PredBB))) +
		1);
		Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
		for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
		Updates.push_back({DominatorTree::Delete, *I, PredBB});
		Updates.push_back({DominatorTree::Insert, *I, DestBB});
		}
		brzyckiAuthorUnsubmitted Done Reply Inline Actions I did not see this fail in the specific case of the Chrome assert(). However, it is entirely possible on this code path for the same issue to occur which is why I added the check. brzycki: I did not see this fail in the specific case of the Chrome assert(). However, it is entirely…
		kuharUnsubmitted Done Reply Inline Actions Looks reasonable. You can use llvm::find here, something like this `if (llvm::find(successors(I), DestBB) == succ_end(I))` kuhar: Looks reasonable. You can use llvm::find here, something like this `if (llvm::find(successors…
		}

// Zap anything that took the address of DestBB. Not doing this will give the		// Zap anything that took the address of DestBB. Not doing this will give the
// address an invalid value.		// address an invalid value.
if (DestBB->hasAddressTaken()) {		if (DestBB->hasAddressTaken()) {
BlockAddress *BA = BlockAddress::get(DestBB);		BlockAddress *BA = BlockAddress::get(DestBB);
Constant *Replacement =		Constant *Replacement =
ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);		ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);
BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,		BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
BA->getType()));		BA->getType()));
BA->destroyConstant();		BA->destroyConstant();
}		}

// Anything that branched to PredBB now branches to DestBB.		// Anything that branched to PredBB now branches to DestBB.
PredBB->replaceAllUsesWith(DestBB);		PredBB->replaceAllUsesWith(DestBB);

// Splice all the instructions from PredBB to DestBB.		// Splice all the instructions from PredBB to DestBB.
PredBB->getTerminator()->eraseFromParent();		PredBB->getTerminator()->eraseFromParent();
DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());		DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());

// If the PredBB is the entry block of the function, move DestBB up to		// If the PredBB is the entry block of the function, move DestBB up to
// become the entry block after we erase PredBB.		// become the entry block after we erase PredBB.
if (PredBB == &DestBB->getParent()->getEntryBlock())		if (ReplaceEntryBB)
DestBB->moveAfter(PredBB);		DestBB->moveAfter(PredBB);

if (DT) {		if (DT) {
// For some irreducible CFG we end up having forward-unreachable blocks		// For some irreducible CFG we end up having forward-unreachable blocks
// so check if getNode returns a valid node before updating the domtree.		// so check if getNode returns a valid node before updating the domtree.
if (DomTreeNode *DTN = DT->getNode(PredBB)) {		if (DomTreeNode *DTN = DT->getNode(PredBB)) {
BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();		BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
DT->changeImmediateDominator(DestBB, PredBBIDom);		DT->changeImmediateDominator(DestBB, PredBBIDom);
DT->eraseNode(PredBB);		DT->eraseNode(PredBB);
}		}
}		}
// Nuke BB.
PredBB->eraseFromParent();		if (DDT) {
		DDT->deleteBB(PredBB); // Deferred deletion of BB.
		if (ReplaceEntryBB)
		// The entry block was removed and there is no external interface for the
		// dominator tree to be notified of this change. In this corner-case we
		// recalculate the entire tree.
		DDT->recalculate(*(DestBB->getParent()));
		else
		DDT->applyUpdates(Updates);
		} else {
		PredBB->eraseFromParent(); // Nuke BB.
		}
}		}

/// CanMergeValues - Return true if we can choose one of these values to use		/// CanMergeValues - Return true if we can choose one of these values to use
/// in place of the other. Note that we will always choose the non-undef		/// in place of the other. Note that we will always choose the non-undef
/// value to keep.		/// value to keep.
static bool CanMergeValues(Value First, Value Second) {		static bool CanMergeValues(Value First, Value Second) {
return First == Second \|\| isa<UndefValue>(First) \|\| isa<UndefValue>(Second);		return First == Second \|\| isa<UndefValue>(First) \|\| isa<UndefValue>(Second);
}		}
▲ Show 20 Lines • Show All 190 Lines • ▼ Show 20 Lines	static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
replaceUndefValuesInPhi(PN, IncomingValues);		replaceUndefValuesInPhi(PN, IncomingValues);
}		}

/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an		/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
/// unconditional branch, and contains no instructions other than PHI nodes,		/// unconditional branch, and contains no instructions other than PHI nodes,
/// potential side-effect free intrinsics and the branch. If possible,		/// potential side-effect free intrinsics and the branch. If possible,
/// eliminate BB by rewriting all the predecessors to branch to the successor		/// eliminate BB by rewriting all the predecessors to branch to the successor
/// block and return true. If we can't transform, return false.		/// block and return true. If we can't transform, return false.
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {		bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
		DeferredDominance *DDT) {
assert(BB != &BB->getParent()->getEntryBlock() &&		assert(BB != &BB->getParent()->getEntryBlock() &&
"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");		"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");

// We can't eliminate infinite loops.		// We can't eliminate infinite loops.
BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);		BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
if (BB == Succ) return false;		if (BB == Succ) return false;

// Check to see if merging these blocks would cause conflicts for any of the		// Check to see if merging these blocks would cause conflicts for any of the
Show All 24 Lines	while (isa<PHINode>(*BBI)) {
}		}
}		}
++BBI;		++BBI;
}		}
}		}

DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);		DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);

		std::vector<DominatorTree::UpdateType> Updates;
		if (DDT) {
		Updates.reserve((2 * std::distance(pred_begin(BB), pred_end(BB))) + 1);
		Updates.push_back({DominatorTree::Delete, BB, Succ});
		// All predecessors of BB will be moved to Succ.
		for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
		Updates.push_back({DominatorTree::Delete, *I, BB});
		Updates.push_back({DominatorTree::Insert, *I, Succ});
		}
		brzyckiAuthorUnsubmitted Done Reply Inline Actions This check is the fix for the assert() discovered by @rnk . The shape of the IR had an existing edge from I to Succ. Inserting was incorrect since the DT already had a pre-existing edge. It caused the balancing of Insertions/Deletions to be incorrect. brzycki:* This check is the fix for the assert() discovered by @rnk . The shape of the IR had an…
		kuharUnsubmitted Done Reply Inline Actions Just like above. kuhar: Just like above.
		}

if (isa<PHINode>(Succ->begin())) {		if (isa<PHINode>(Succ->begin())) {
// If there is more than one pred of succ, and there are PHI nodes in		// If there is more than one pred of succ, and there are PHI nodes in
// the successor, then we need to add incoming edges for the PHI nodes		// the successor, then we need to add incoming edges for the PHI nodes
//		//
const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));		const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));

// Loop over all of the PHI nodes in the successor of BB.		// Loop over all of the PHI nodes in the successor of BB.
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {		for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
Show All 28 Lines	if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {		for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock Pred = PI;		BasicBlock Pred = PI;
Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);		Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
}		}

// Everything that jumped to BB now goes to Succ.		// Everything that jumped to BB now goes to Succ.
BB->replaceAllUsesWith(Succ);		BB->replaceAllUsesWith(Succ);
if (!Succ->hasName()) Succ->takeName(BB);		if (!Succ->hasName()) Succ->takeName(BB);

		if (DDT) {
		DDT->deleteBB(BB); // Deferred deletion of the old basic block.
		DDT->applyUpdates(Updates);
		} else {
BB->eraseFromParent(); // Delete the old basic block.		BB->eraseFromParent(); // Delete the old basic block.
		}
return true;		return true;
}		}

/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI		/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
/// nodes in this block. This doesn't try to be clever about PHI nodes		/// nodes in this block. This doesn't try to be clever about PHI nodes
/// which differ only in the order of the incoming values, but instcombine		/// which differ only in the order of the incoming values, but instcombine
/// orders them so it usually won't matter.		/// orders them so it usually won't matter.
bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {		bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
▲ Show 20 Lines • Show All 483 Lines • ▼ Show 20 Lines	while (EndInst != &BB->front()) {
if (!isa<DbgInfoIntrinsic>(Inst))		if (!isa<DbgInfoIntrinsic>(Inst))
++NumDeadInst;		++NumDeadInst;
Inst->eraseFromParent();		Inst->eraseFromParent();
}		}
return NumDeadInst;		return NumDeadInst;
}		}

unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,		unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
bool PreserveLCSSA) {		bool PreserveLCSSA, DeferredDominance *DDT) {
BasicBlock *BB = I->getParent();		BasicBlock *BB = I->getParent();
		std::vector <DominatorTree::UpdateType> Updates;

// Loop over all of the successors, removing BB's entry from any PHI		// Loop over all of the successors, removing BB's entry from any PHI
// nodes.		// nodes.
for (BasicBlock *Successor : successors(BB))		if (DDT)
		Updates.reserve(BB->getTerminator()->getNumSuccessors());
		for (BasicBlock *Successor : successors(BB)) {
Successor->removePredecessor(BB, PreserveLCSSA);		Successor->removePredecessor(BB, PreserveLCSSA);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, BB, Successor});
		}
// Insert a call to llvm.trap right before this. This turns the undefined		// Insert a call to llvm.trap right before this. This turns the undefined
// behavior into a hard fail instead of falling through into random code.		// behavior into a hard fail instead of falling through into random code.
if (UseLLVMTrap) {		if (UseLLVMTrap) {
Function *TrapFn =		Function *TrapFn =
Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);		Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
CallInst *CallTrap = CallInst::Create(TrapFn, "", I);		CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
CallTrap->setDebugLoc(I->getDebugLoc());		CallTrap->setDebugLoc(I->getDebugLoc());
}		}
new UnreachableInst(I->getContext(), I);		new UnreachableInst(I->getContext(), I);

// All instructions after this are dead.		// All instructions after this are dead.
unsigned NumInstrsRemoved = 0;		unsigned NumInstrsRemoved = 0;
BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();		BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
while (BBI != BBE) {		while (BBI != BBE) {
if (!BBI->use_empty())		if (!BBI->use_empty())
BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));		BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BB->getInstList().erase(BBI++);		BB->getInstList().erase(BBI++);
++NumInstrsRemoved;		++NumInstrsRemoved;
}		}
		if (DDT)
		DDT->applyUpdates(Updates);
return NumInstrsRemoved;		return NumInstrsRemoved;
}		}

/// changeToCall - Convert the specified invoke into a normal call.		/// changeToCall - Convert the specified invoke into a normal call.
static void changeToCall(InvokeInst *II) {		static void changeToCall(InvokeInst II, DeferredDominance DDT = nullptr) {
SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());		SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
SmallVector<OperandBundleDef, 1> OpBundles;		SmallVector<OperandBundleDef, 1> OpBundles;
II->getOperandBundlesAsDefs(OpBundles);		II->getOperandBundlesAsDefs(OpBundles);
CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,		CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
"", II);		"", II);
NewCall->takeName(II);		NewCall->takeName(II);
NewCall->setCallingConv(II->getCallingConv());		NewCall->setCallingConv(II->getCallingConv());
NewCall->setAttributes(II->getAttributes());		NewCall->setAttributes(II->getAttributes());
NewCall->setDebugLoc(II->getDebugLoc());		NewCall->setDebugLoc(II->getDebugLoc());
II->replaceAllUsesWith(NewCall);		II->replaceAllUsesWith(NewCall);

// Follow the call by a branch to the normal destination.		// Follow the call by a branch to the normal destination.
BranchInst::Create(II->getNormalDest(), II);		BasicBlock *NormalDestBB = II->getNormalDest();
		BranchInst::Create(NormalDestBB, II);

// Update PHI nodes in the unwind destination		// Update PHI nodes in the unwind destination
II->getUnwindDest()->removePredecessor(II->getParent());		BasicBlock *BB = II->getParent();
		BasicBlock *UnwindDestBB = II->getUnwindDest();
		UnwindDestBB->removePredecessor(BB);
II->eraseFromParent();		II->eraseFromParent();
		if (DDT)
		DDT->deleteEdge(BB, UnwindDestBB);
}		}

BasicBlock llvm::changeToInvokeAndSplitBasicBlock(CallInst CI,		BasicBlock llvm::changeToInvokeAndSplitBasicBlock(CallInst CI,
BasicBlock *UnwindEdge) {		BasicBlock *UnwindEdge) {
BasicBlock *BB = CI->getParent();		BasicBlock *BB = CI->getParent();

// Convert this function call into an invoke instruction. First, split the		// Convert this function call into an invoke instruction. First, split the
// basic block.		// basic block.
Show All 24 Lines	BasicBlock llvm::changeToInvokeAndSplitBasicBlock(CallInst CI,
CI->replaceAllUsesWith(II);		CI->replaceAllUsesWith(II);

// Delete the original call		// Delete the original call
Split->getInstList().pop_front();		Split->getInstList().pop_front();
return Split;		return Split;
}		}

static bool markAliveBlocks(Function &F,		static bool markAliveBlocks(Function &F,
SmallPtrSetImpl<BasicBlock*> &Reachable) {		SmallPtrSetImpl<BasicBlock*> &Reachable,
		DeferredDominance *DDT = nullptr) {
SmallVector<BasicBlock*, 128> Worklist;		SmallVector<BasicBlock*, 128> Worklist;
BasicBlock *BB = &F.front();		BasicBlock *BB = &F.front();
Worklist.push_back(BB);		Worklist.push_back(BB);
Reachable.insert(BB);		Reachable.insert(BB);
bool Changed = false;		bool Changed = false;
do {		do {
BB = Worklist.pop_back_val();		BB = Worklist.pop_back_val();

// Do a quick scan of the basic block, turning any obviously unreachable		// Do a quick scan of the basic block, turning any obviously unreachable
// instructions into LLVM unreachable insts. The instruction combining pass		// instructions into LLVM unreachable insts. The instruction combining pass
// canonicalizes unreachable insts into stores to null or undef.		// canonicalizes unreachable insts into stores to null or undef.
for (Instruction &I : *BB) {		for (Instruction &I : *BB) {
// Assumptions that are known to be false are equivalent to unreachable.		// Assumptions that are known to be false are equivalent to unreachable.
// Also, if the condition is undefined, then we make the choice most		// Also, if the condition is undefined, then we make the choice most
// beneficial to the optimizer, and choose that to also be unreachable.		// beneficial to the optimizer, and choose that to also be unreachable.
if (auto *II = dyn_cast<IntrinsicInst>(&I)) {		if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
if (II->getIntrinsicID() == Intrinsic::assume) {		if (II->getIntrinsicID() == Intrinsic::assume) {
if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {		if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
// Don't insert a call to llvm.trap right before the unreachable.		// Don't insert a call to llvm.trap right before the unreachable.
changeToUnreachable(II, false);		changeToUnreachable(II, false, false, DDT);
Changed = true;		Changed = true;
break;		break;
}		}
}		}

if (II->getIntrinsicID() == Intrinsic::experimental_guard) {		if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
// A call to the guard intrinsic bails out of the current compilation		// A call to the guard intrinsic bails out of the current compilation
// unit if the predicate passed to it is false. If the predicate is a		// unit if the predicate passed to it is false. If the predicate is a
// constant false, then we know the guard will bail out of the current		// constant false, then we know the guard will bail out of the current
// compile unconditionally, so all code following it is dead.		// compile unconditionally, so all code following it is dead.
//		//
// Note: unlike in llvm.assume, it is not "obviously profitable" for		// Note: unlike in llvm.assume, it is not "obviously profitable" for
// guards to treat `undef` as `false` since a guard on `undef` can		// guards to treat `undef` as `false` since a guard on `undef` can
// still be useful for widening.		// still be useful for widening.
if (match(II->getArgOperand(0), m_Zero()))		if (match(II->getArgOperand(0), m_Zero()))
if (!isa<UnreachableInst>(II->getNextNode())) {		if (!isa<UnreachableInst>(II->getNextNode())) {
changeToUnreachable(II->getNextNode(), /UseLLVMTrap=/ false);		changeToUnreachable(II->getNextNode(), /UseLLVMTrap=/false,
		false, DDT);
Changed = true;		Changed = true;
break;		break;
}		}
}		}
}		}

if (auto *CI = dyn_cast<CallInst>(&I)) {		if (auto *CI = dyn_cast<CallInst>(&I)) {
Value *Callee = CI->getCalledValue();		Value *Callee = CI->getCalledValue();
if (isa<ConstantPointerNull>(Callee) \|\| isa<UndefValue>(Callee)) {		if (isa<ConstantPointerNull>(Callee) \|\| isa<UndefValue>(Callee)) {
changeToUnreachable(CI, /UseLLVMTrap=/false);		changeToUnreachable(CI, /UseLLVMTrap=/false, false, DDT);
Changed = true;		Changed = true;
break;		break;
}		}
if (CI->doesNotReturn()) {		if (CI->doesNotReturn()) {
// If we found a call to a no-return function, insert an unreachable		// If we found a call to a no-return function, insert an unreachable
// instruction after it. Make sure there isn't already one there		// instruction after it. Make sure there isn't already one there
// though.		// though.
if (!isa<UnreachableInst>(CI->getNextNode())) {		if (!isa<UnreachableInst>(CI->getNextNode())) {
// Don't insert a call to llvm.trap right before the unreachable.		// Don't insert a call to llvm.trap right before the unreachable.
changeToUnreachable(CI->getNextNode(), false);		changeToUnreachable(CI->getNextNode(), false, false, DDT);
Changed = true;		Changed = true;
}		}
break;		break;
}		}
}		}

// Store to undef and store to null are undefined and used to signal that		// Store to undef and store to null are undefined and used to signal that
// they should be changed to unreachable by passes that can't modify the		// they should be changed to unreachable by passes that can't modify the
// CFG.		// CFG.
if (auto *SI = dyn_cast<StoreInst>(&I)) {		if (auto *SI = dyn_cast<StoreInst>(&I)) {
// Don't touch volatile stores.		// Don't touch volatile stores.
if (SI->isVolatile()) continue;		if (SI->isVolatile()) continue;

Value *Ptr = SI->getOperand(1);		Value *Ptr = SI->getOperand(1);

if (isa<UndefValue>(Ptr) \|\|		if (isa<UndefValue>(Ptr) \|\|
(isa<ConstantPointerNull>(Ptr) &&		(isa<ConstantPointerNull>(Ptr) &&
SI->getPointerAddressSpace() == 0)) {		SI->getPointerAddressSpace() == 0)) {
changeToUnreachable(SI, true);		changeToUnreachable(SI, true, false, DDT);
Changed = true;		Changed = true;
break;		break;
}		}
}		}
}		}

TerminatorInst *Terminator = BB->getTerminator();		TerminatorInst *Terminator = BB->getTerminator();
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {		if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
// Turn invokes that call 'nounwind' functions into ordinary calls.		// Turn invokes that call 'nounwind' functions into ordinary calls.
Value *Callee = II->getCalledValue();		Value *Callee = II->getCalledValue();
if (isa<ConstantPointerNull>(Callee) \|\| isa<UndefValue>(Callee)) {		if (isa<ConstantPointerNull>(Callee) \|\| isa<UndefValue>(Callee)) {
changeToUnreachable(II, true);		changeToUnreachable(II, true, false, DDT);
Changed = true;		Changed = true;
} else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {		} else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
if (II->use_empty() && II->onlyReadsMemory()) {		if (II->use_empty() && II->onlyReadsMemory()) {
// jump to the normal destination branch.		// jump to the normal destination branch.
BranchInst::Create(II->getNormalDest(), II);		BasicBlock *NormalDestBB = II->getNormalDest();
II->getUnwindDest()->removePredecessor(II->getParent());		BasicBlock *UnwindDestBB = II->getUnwindDest();
		BranchInst::Create(NormalDestBB, II);
		UnwindDestBB->removePredecessor(II->getParent());
II->eraseFromParent();		II->eraseFromParent();
		if (DDT)
		DDT->deleteEdge(BB, UnwindDestBB);
} else		} else
changeToCall(II);		changeToCall(II, DDT);
Changed = true;		Changed = true;
}		}
} else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {		} else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
// Remove catchpads which cannot be reached.		// Remove catchpads which cannot be reached.
struct CatchPadDenseMapInfo {		struct CatchPadDenseMapInfo {
static CatchPadInst *getEmptyKey() {		static CatchPadInst *getEmptyKey() {
return DenseMapInfo<CatchPadInst *>::getEmptyKey();		return DenseMapInfo<CatchPadInst *>::getEmptyKey();
}		}
Show All 29 Lines	if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
CatchSwitch->removeHandler(I);		CatchSwitch->removeHandler(I);
--I;		--I;
--E;		--E;
Changed = true;		Changed = true;
}		}
}		}
}		}

Changed \|= ConstantFoldTerminator(BB, true);		Changed \|= ConstantFoldTerminator(BB, true, nullptr, DDT);
for (BasicBlock *Successor : successors(BB))		for (BasicBlock *Successor : successors(BB))
if (Reachable.insert(Successor).second)		if (Reachable.insert(Successor).second)
Worklist.push_back(Successor);		Worklist.push_back(Successor);
} while (!Worklist.empty());		} while (!Worklist.empty());
return Changed;		return Changed;
}		}

void llvm::removeUnwindEdge(BasicBlock *BB) {		void llvm::removeUnwindEdge(BasicBlock BB, DeferredDominance DDT) {
TerminatorInst *TI = BB->getTerminator();		TerminatorInst *TI = BB->getTerminator();

if (auto *II = dyn_cast<InvokeInst>(TI)) {		if (auto *II = dyn_cast<InvokeInst>(TI)) {
changeToCall(II);		changeToCall(II, DDT);
return;		return;
}		}

TerminatorInst *NewTI;		TerminatorInst *NewTI;
BasicBlock *UnwindDest;		BasicBlock *UnwindDest;

if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {		if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);		NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
Show All 11 Lines	if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
llvm_unreachable("Could not find unwind successor");		llvm_unreachable("Could not find unwind successor");
}		}

NewTI->takeName(TI);		NewTI->takeName(TI);
NewTI->setDebugLoc(TI->getDebugLoc());		NewTI->setDebugLoc(TI->getDebugLoc());
UnwindDest->removePredecessor(BB);		UnwindDest->removePredecessor(BB);
TI->replaceAllUsesWith(NewTI);		TI->replaceAllUsesWith(NewTI);
TI->eraseFromParent();		TI->eraseFromParent();
		if (DDT)
		DDT->deleteEdge(BB, UnwindDest);
}		}

/// removeUnreachableBlocks - Remove blocks that are not reachable, even		/// removeUnreachableBlocks - Remove blocks that are not reachable, even
/// if they are in a dead cycle. Return true if a change was made, false		/// if they are in a dead cycle. Return true if a change was made, false
/// otherwise. If `LVI` is passed, this function preserves LazyValueInfo		/// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
/// after modifying the CFG.		/// after modifying the CFG.
bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {		bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
		DeferredDominance *DDT) {
SmallPtrSet<BasicBlock*, 16> Reachable;		SmallPtrSet<BasicBlock*, 16> Reachable;
bool Changed = markAliveBlocks(F, Reachable);		bool Changed = markAliveBlocks(F, Reachable, DDT);

// If there are unreachable blocks in the CFG...		// If there are unreachable blocks in the CFG...
if (Reachable.size() == F.size())		if (Reachable.size() == F.size())
return Changed;		return Changed;

assert(Reachable.size() < F.size());		assert(Reachable.size() < F.size());
NumRemoved += F.size()-Reachable.size();		NumRemoved += F.size()-Reachable.size();

// Loop over all of the basic blocks that are not reachable, dropping all of		// Loop over all of the basic blocks that are not reachable, dropping all of
// their internal references...		// their internal references. Update DDT and LVI if available.
for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {		std::vector <DominatorTree::UpdateType> Updates;
if (Reachable.count(&*BB))		for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
		auto BB = &I;
		if (Reachable.count(BB))
continue;		continue;
		for (BasicBlock *Successor : successors(BB)) {
for (BasicBlock Successor : successors(&BB))
if (Reachable.count(Successor))		if (Reachable.count(Successor))
Successor->removePredecessor(&*BB);		Successor->removePredecessor(BB);
		if (DDT)
		Updates.push_back({DominatorTree::Delete, BB, Successor});
		}
if (LVI)		if (LVI)
LVI->eraseBlock(&*BB);		LVI->eraseBlock(BB);
BB->dropAllReferences();		BB->dropAllReferences();
}		}

for (Function::iterator I = ++F.begin(); I != F.end();)		for (Function::iterator I = ++F.begin(); I != F.end();) {
if (!Reachable.count(&*I))		auto BB = &I;
I = F.getBasicBlockList().erase(I);		if (Reachable.count(BB)) {
else		++I;
		continue;
		}
		if (DDT) {
		DDT->deleteBB(BB); // deferred deletion of BB.
++I;		++I;
		} else {
		I = F.getBasicBlockList().erase(I);
		}
		}
		sebpopUnsubmitted Done Reply Inline Actions Please move the ++I back in the body of the for loop and remove --I. sebpop: Please move the ++I back in the body of the for loop and remove --I.

		if (DDT)
		DDT->applyUpdates(Updates);
return true;		return true;
}		}

void llvm::combineMetadata(Instruction K, const Instruction J,		void llvm::combineMetadata(Instruction K, const Instruction J,
ArrayRef<unsigned> KnownIDs) {		ArrayRef<unsigned> KnownIDs) {
SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;		SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
K->dropUnknownNonDebugMetadata(KnownIDs);		K->dropUnknownNonDebugMetadata(KnownIDs);
K->getAllMetadataOtherThanDebugLoc(Metadata);		K->getAllMetadataOtherThanDebugLoc(Metadata);
▲ Show 20 Lines • Show All 514 Lines • Show Last 20 Lines