This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multiple successors. More...

#include "llvm/Transforms/Scalar/JumpThreading.h"

Inheritance diagram for llvm::JumpThreadingPass:

[legend]

Public Member Functions
LLVM_ABI	JumpThreadingPass (int T=-1)

LLVM_ABI bool	runImpl (Function &F, FunctionAnalysisManager FAM, TargetLibraryInfo TLI, TargetTransformInfo TTI, LazyValueInfo LVI, AAResults AA, std::unique_ptr< DomTreeUpdater > DTU, BlockFrequencyInfo BFI, BranchProbabilityInfo *BPI)

LLVM_ABI PreservedAnalyses	run (Function &F, FunctionAnalysisManager &AM)

DomTreeUpdater *	getDomTreeUpdater () const

LLVM_ABI void	findLoopHeaders (Function &F)
	findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops.

LLVM_ABI bool	processBlock (BasicBlock *BB)
	processBlock - If there are any predecessors whose control can be threaded through to a successor, transform them now.

LLVM_ABI bool	maybeMergeBasicBlockIntoOnlyPred (BasicBlock *BB)
	Merge basic block BB into its sole predecessor if possible.

LLVM_ABI void	updateSSA (BasicBlock BB, BasicBlock NewBB, ValueToValueMapTy &ValueMapping)
	Update the SSA form.

LLVM_ABI void	cloneInstructions (ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock NewBB, BasicBlock PredBB)
	Clone instructions in range [BI, BE) to NewBB.

LLVM_ABI bool	tryThreadEdge (BasicBlock BB, const SmallVectorImpl< BasicBlock > &PredBBs, BasicBlock *SuccBB)
	tryThreadEdge - Thread an edge if it's safe and profitable to do so.

LLVM_ABI void	threadEdge (BasicBlock BB, const SmallVectorImpl< BasicBlock > &PredBBs, BasicBlock *SuccBB)
	threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB across BB.

LLVM_ABI bool	duplicateCondBranchOnPHIIntoPred (BasicBlock BB, const SmallVectorImpl< BasicBlock > &PredBBs)
	duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1 PHI node and a conditional branch on that PHI.

LLVM_ABI bool	computeValueKnownInPredecessorsImpl (Value V, BasicBlock BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value , 4 > &RecursionSet, Instruction CxtI=nullptr)
	computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the value is a known ConstantInt/BlockAddress or undef in any of our predecessors.

bool	computeValueKnownInPredecessors (Value V, BasicBlock BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)

LLVM_ABI Constant *	evaluateOnPredecessorEdge (BasicBlock BB, BasicBlock PredPredBB, Value *cond, const DataLayout &DL)

LLVM_ABI bool	maybethreadThroughTwoBasicBlocks (BasicBlock BB, Value Cond)
	Attempt to thread through two successive basic blocks.

LLVM_ABI void	threadThroughTwoBasicBlocks (BasicBlock PredPredBB, BasicBlock PredBB, BasicBlock BB, BasicBlock SuccBB)

LLVM_ABI bool	processThreadableEdges (Value Cond, BasicBlock BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)

LLVM_ABI bool	processBranchOnPHI (PHINode *PN)
	processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PHI) in the current block.

LLVM_ABI bool	processBranchOnXOR (BinaryOperator *BO)
	processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the current block.

LLVM_ABI bool	processImpliedCondition (BasicBlock *BB)

LLVM_ABI bool	simplifyPartiallyRedundantLoad (LoadInst *LI)
	simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction, eliminate it by replacing it with a PHI node.

LLVM_ABI void	unfoldSelectInstr (BasicBlock Pred, BasicBlock BB, SelectInst SI, PHINode SIUse, unsigned Idx)

LLVM_ABI bool	tryToUnfoldSelect (CmpInst CondCmp, BasicBlock BB)
	tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2

LLVM_ABI bool	tryToUnfoldSelect (SwitchInst SI, BasicBlock BB)

LLVM_ABI bool	tryToUnfoldSelectInCurrBB (BasicBlock *BB)
	tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = phi [false, bb1], [true, bb2], [false, bb3], [true, bb4], ... s = select p, trueval, falseval

LLVM_ABI bool	processGuards (BasicBlock *BB)
	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 guard is always true.

LLVM_ABI bool	threadGuard (BasicBlock BB, IntrinsicInst Guard, BranchInst *BI)
	Try to propagate the guard from BB which is the lower block of a diamond to one of its branches, in case if diamond's condition implies guard's condition.

Public Member Functions inherited from llvm::PassInfoMixin< JumpThreadingPass >
void	printPipeline (raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Additional Inherited Members
Static Public Member Functions inherited from llvm::PassInfoMixin< JumpThreadingPass >
static StringRef	name ()
	Gets the name of the pass we are mixed into.

Detailed Description

This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multiple successors.

If one or more of the predecessors of the block can be proven to always jump to one of the successors, we forward the edge from the predecessor to the successor by duplicating the contents of this block.

An example of when this can occur is code like this:

if () { ... X = 4; } if (X < 3) {

In this case, the unconditional branch at the end of the first if can be revectored to the false side of the second if.

Definition at line 80 of file JumpThreading.h.

Constructor & Destructor Documentation

◆ JumpThreadingPass()

JumpThreadingPass::JumpThreadingPass ( int T = -1 )

Definition at line 109 of file JumpThreading.cpp.

References BBDuplicateThreshold.

Member Function Documentation

◆ cloneInstructions()

void JumpThreadingPass::cloneInstructions	(	ValueToValueMapTy &	ValueMapping,
		BasicBlock::iterator	BI,
		BasicBlock::iterator	BE,
		BasicBlock *	NewBB,
		BasicBlock *	PredBB
	)

Clone instructions in range [BI, BE) to NewBB.

For PHI nodes, we only clone arguments that come from PredBB. Return the map from the variables in the source basic block to the variables in the newly created basic block.

Definition at line 2020 of file JumpThreading.cpp.

References llvm::adaptNoAliasScopes(), llvm::PHINode::addIncoming(), llvm::Instruction::cloneDebugInfoFrom(), llvm::DbgMarker::cloneDebugInfoFrom(), llvm::cloneNoAliasScopes(), Context, llvm::PHINode::Create(), llvm::BasicBlock::createMarker(), DL, llvm::BasicBlock::end(), llvm::ValueMap< KeyT, ValueT, Config >::end(), llvm::filterDbgVars(), llvm::ValueMap< KeyT, ValueT, Config >::find(), From, llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getMarker(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::Value::getType(), I, llvm::identifyNoAliasScopesToClone(), llvm::SmallSet< T, N, C >::insert(), and llvm::mapAtomInstance().

Referenced by threadEdge(), and threadThroughTwoBasicBlocks().

◆ computeValueKnownInPredecessors()

bool llvm::JumpThreadingPass::computeValueKnownInPredecessors	(	Value *	V,
		BasicBlock *	BB,
		jumpthreading::PredValueInfo &	Result,
		jumpthreading::ConstantPreference	Preference,
		Instruction *	CxtI = `nullptr`
	)

inline

Definition at line 141 of file JumpThreading.h.

References computeValueKnownInPredecessorsImpl().

Referenced by processBranchOnXOR(), and processThreadableEdges().

◆ computeValueKnownInPredecessorsImpl()

bool JumpThreadingPass::computeValueKnownInPredecessorsImpl	(	Value *	V,
		BasicBlock *	BB,
		jumpthreading::PredValueInfo &	Result,
		jumpthreading::ConstantPreference	Preference,
		SmallPtrSet< Value *, 4 > &	RecursionSet,
		Instruction *	CxtI = `nullptr`
	)

computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the value is a known ConstantInt/BlockAddress or undef in any of our predecessors.

If so, return the known list of value and pred BB in the result vector.

This returns true if there were any known values.

If I is a PHI node, then we know the incoming values for any constants.

Definition at line 556 of file JumpThreading.cpp.

Referenced by computeValueKnownInPredecessors(), and computeValueKnownInPredecessorsImpl().

◆ duplicateCondBranchOnPHIIntoPred()

bool JumpThreadingPass::duplicateCondBranchOnPHIIntoPred	(	BasicBlock *	BB,
		const SmallVectorImpl< BasicBlock * > &	PredBBs
	)

duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1 PHI node and a conditional branch on that PHI.

If we can duplicate the contents of BB up into PredBB do so now, this improves the odds that the branch will be on an analyzable instruction like a compare.

Definition at line 2611 of file JumpThreading.cpp.

References addPHINodeEntriesForMappedBlock(), assert(), llvm::BasicBlock::begin(), llvm::Instruction::cloneDebugInfoFrom(), llvm::BranchProbabilityInfo::copyEdgeProbabilities(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, DL, llvm::SmallVectorBase< Size_T >::empty(), llvm::BasicBlock::end(), llvm::ValueMap< KeyT, ValueT, Config >::end(), llvm::Instruction::eraseFromParent(), llvm::ValueMap< KeyT, ValueT, Config >::find(), llvm::BasicBlock::getDataLayout(), llvm::PHINode::getIncomingValueForBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), getJumpThreadDuplicationCost(), llvm::Value::getName(), llvm::ilist_node_impl< OptionsT >::getReverseIterator(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::BranchInst::isUnconditional(), IV, LLVM_DEBUG, llvm::mapAtomInstance(), llvm::remapDebugVariable(), remapSourceAtoms(), llvm::BasicBlock::removePredecessor(), llvm::simplifyInstruction(), llvm::SmallVectorBase< Size_T >::size(), llvm::SplitEdge(), and updateSSA().

Referenced by processBranchOnPHI(), and processBranchOnXOR().

◆ evaluateOnPredecessorEdge()

Constant * JumpThreadingPass::evaluateOnPredecessorEdge	(	BasicBlock *	BB,
		BasicBlock *	PredPredBB,
		Value *	cond,
		const DataLayout &	DL
	)

Definition at line 1494 of file JumpThreading.cpp.

References DL, and evaluateOnPredecessorEdge().

Referenced by evaluateOnPredecessorEdge(), and maybethreadThroughTwoBasicBlocks().

◆ findLoopHeaders()

void JumpThreadingPass::findLoopHeaders ( Function & F )

findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops.

Doing this breaks up the loop nesting hierarchy and pessimizes later transformations. To prevent this from happening, we first have to find the loop headers. Here we approximate this by finding targets of backedges in the CFG.

Note that there definitely are cases when we want to allow threading of edges across a loop header. For example, threading a jump from outside the loop (the preheader) to an exit block of the loop is definitely profitable. It is also almost always profitable to thread backedges from within the loop to exit blocks, and is often profitable to thread backedges to other blocks within the loop (forming a nested loop). This simple analysis is not rich enough to track all of these properties and keep it up-to-date as the CFG mutates, so we don't allow any of these transformations.

Definition at line 525 of file JumpThreading.cpp.

References F, llvm::FindFunctionBackedges(), and llvm::make_second_range().

Referenced by runImpl().

◆ getDomTreeUpdater()

DomTreeUpdater * llvm::JumpThreadingPass::getDomTreeUpdater ( ) const

inline

Definition at line 117 of file JumpThreading.h.

Referenced by run().

◆ maybeMergeBasicBlockIntoOnlyPred()

bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred ( BasicBlock * BB )

Merge basic block BB into its sole predecessor if possible.

Definition at line 1899 of file JumpThreading.cpp.

References llvm::LazyValueInfo::eraseBlock(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), hasAddressTakenAndUsed(), llvm::isGuaranteedToTransferExecutionToSuccessor(), llvm::Instruction::isSpecialTerminator(), and llvm::MergeBasicBlockIntoOnlyPred().

Referenced by processBlock().

◆ maybethreadThroughTwoBasicBlocks()

bool JumpThreadingPass::maybethreadThroughTwoBasicBlocks	(	BasicBlock *	BB,
		Value *	Cond
	)

Attempt to thread through two successive basic blocks.

Definition at line 2110 of file JumpThreading.cpp.

References Cond, llvm::dbgs(), DL, evaluateOnPredecessorEdge(), llvm::BasicBlock::getDataLayout(), getJumpThreadDuplicationCost(), llvm::Value::getName(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::is_contained(), llvm::BasicBlock::isEHPad(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, P, llvm::predecessors(), llvm::successors(), and threadThroughTwoBasicBlocks().

Referenced by processThreadableEdges().

◆ processBlock()

bool JumpThreadingPass::processBlock ( BasicBlock * BB )

processBlock - If there are any predecessors whose control can be threaded through to a successor, transform them now.

Definition at line 946 of file JumpThreading.cpp.

References llvm::ConstantFoldInstruction(), llvm::ConstantFoldTerminator(), llvm::BranchInst::Create(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::BranchProbabilityInfo::eraseBlock(), llvm::Instruction::eraseFromParent(), getBestDestForJumpOnUndef(), llvm::BasicBlock::getDataLayout(), llvm::Instruction::getDebugLoc(), llvm::Function::getEntryBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), getKnownConstant(), llvm::Value::getName(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getOpcode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getParent(), llvm::LazyValueInfo::getPredicateAt(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::isInstructionTriviallyDead(), LLVM_DEBUG, maybeMergeBasicBlockIntoOnlyPred(), llvm::pred_empty(), processBranchOnPHI(), processBranchOnXOR(), processGuards(), processImpliedCondition(), processThreadableEdges(), llvm::BasicBlock::removePredecessor(), replaceFoldableUses(), llvm::Instruction::setDebugLoc(), simplifyPartiallyRedundantLoad(), tryToUnfoldSelect(), tryToUnfoldSelectInCurrBB(), updatePredecessorProfileMetadata(), llvm::jumpthreading::WantBlockAddress, and llvm::jumpthreading::WantInteger.

Referenced by runImpl().

◆ processBranchOnPHI()

bool JumpThreadingPass::processBranchOnPHI ( PHINode * PN )

processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PHI) in the current block.

See if there are any simplifications we can do based on inputs to the phi node.

Definition at line 1732 of file JumpThreading.cpp.

References duplicateCondBranchOnPHIIntoPred(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), and llvm::SmallVectorImpl< T >::resize().

Referenced by processBlock().

◆ processBranchOnXOR()

bool JumpThreadingPass::processBranchOnXOR ( BinaryOperator * BO )

processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the current block.

See if there are any simplifications we can do based on inputs to the xor.

Definition at line 1764 of file JumpThreading.cpp.

References llvm::any_of(), assert(), computeValueKnownInPredecessors(), duplicateCondBranchOnPHIIntoPred(), llvm::SmallVectorBase< Size_T >::empty(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::front(), llvm::UndefValue::get(), llvm::BasicBlock::getContext(), llvm::ConstantInt::getFalse(), llvm::User::getOperand(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::BasicBlock::isEHPad(), llvm::ConstantInt::isZero(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::User::setOperand(), llvm::SmallVectorBase< Size_T >::size(), and llvm::jumpthreading::WantInteger.

Referenced by processBlock().

◆ processGuards()

bool JumpThreadingPass::processGuards ( BasicBlock * BB )

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 guard is always true.

Currently we only process the simplest case that looks like:

Start: cond = ... br i1 cond, label T1, label F1 T1: br label Merge F1: br label Merge Merge: condGuard = ... call void(i1, ...) @llvm.experimental.guard( i1 condGuard )[ "deopt"() ]

And cond either implies condGuard or !condGuard. In this case all the instructions before the guard can be duplicated in both branches, and the guard is then threaded to one of them.

Definition at line 3021 of file JumpThreading.cpp.

References llvm::BasicBlock::getSinglePredecessor(), I, llvm::isGuard(), llvm::pred_begin(), llvm::pred_end(), and threadGuard().

Referenced by processBlock().

◆ processImpliedCondition()

bool JumpThreadingPass::processImpliedCondition ( BasicBlock * BB )

Definition at line 1143 of file JumpThreading.cpp.

References Cond, llvm::BranchInst::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, DL, llvm::BranchProbabilityInfo::eraseBlock(), llvm::BasicBlock::getDataLayout(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), ImplicationSearchThreshold, llvm::isImpliedCondition(), llvm::BasicBlock::removePredecessor(), and llvm::Instruction::setDebugLoc().

Referenced by processBlock().

◆ processThreadableEdges()

bool JumpThreadingPass::processThreadableEdges	(	Value *	Cond,
		BasicBlock *	BB,
		jumpthreading::ConstantPreference	Preference,
		Instruction *	CxtI = `nullptr`
	)

◆ run()

PreservedAnalyses JumpThreadingPass::run	(	Function &	F,
		FunctionAnalysisManager &	AM
	)

Definition at line 237 of file JumpThreading.cpp.

References llvm::PreservedAnalyses::all(), assert(), F, llvm::DominatorTreeBase< NodeT, IsPostDom >::Fast, llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::flush(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Full, getDomTreeUpdater(), llvm::AnalysisManager< IRUnitT, ExtraArgTs >::getResult(), llvm::TargetTransformInfo::hasBranchDivergence(), runImpl(), and verify.

◆ runImpl()

bool JumpThreadingPass::runImpl	(	Function &	F,
		FunctionAnalysisManager *	FAM,
		TargetLibraryInfo *	TLI,
		TargetTransformInfo *	TTI,
		LazyValueInfo *	LVI,
		AAResults *	AA,
		std::unique_ptr< DomTreeUpdater >	DTU,
		BlockFrequencyInfo *	BFI,
		BranchProbabilityInfo *	BPI
	)

◆ simplifyPartiallyRedundantLoad()

bool JumpThreadingPass::simplifyPartiallyRedundantLoad ( LoadInst * LoadI )

simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction, eliminate it by replacing it with a PHI node.

This is an important optimization that encourages jump threading, and needs to be run interlaced with other jump threading tasks.

Definition at line 1220 of file JumpThreading.cpp.

Referenced by processBlock().

◆ threadEdge()

void JumpThreadingPass::threadEdge	(	BasicBlock *	BB,
		const SmallVectorImpl< BasicBlock * > &	PredBBs,
		BasicBlock *	SuccBB
	)

threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB across BB.

Transform the IR to reflect this change.

Definition at line 2366 of file JumpThreading.cpp.

References addPHINodeEntriesForMappedBlock(), assert(), llvm::BasicBlock::begin(), cloneInstructions(), llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::BasicBlock::end(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::BranchProbabilityInfo::getEdgeProbability(), llvm::Value::getName(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, LLVM_DEBUG, llvm::BasicBlock::moveAfter(), remapSourceAtoms(), llvm::BasicBlock::removePredecessor(), llvm::BlockFrequencyInfo::setBlockFreq(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setSuccessor(), llvm::SimplifyInstructionsInBlock(), llvm::SmallVectorBase< Size_T >::size(), llvm::LazyValueInfo::threadEdge(), and updateSSA().

Referenced by threadThroughTwoBasicBlocks(), and tryThreadEdge().

◆ threadGuard()

bool JumpThreadingPass::threadGuard	(	BasicBlock *	BB,
		IntrinsicInst *	Guard,
		BranchInst *	BI
	)

Try to propagate the guard from BB which is the lower block of a diamond to one of its branches, in case if diamond's condition implies guard's condition.

Definition at line 3055 of file JumpThreading.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), llvm::dbgs(), DL, llvm::DuplicateInstructionsInSplitBetween(), llvm::BasicBlock::end(), llvm::CallBase::getArgOperand(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getDataLayout(), llvm::BasicBlock::getFirstInsertionPt(), getJumpThreadDuplicationCost(), llvm::Value::getName(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::BranchInst::getNumSuccessors(), llvm::BranchInst::getSuccessor(), llvm::Instruction::insertBefore(), llvm::BranchInst::isConditional(), llvm::isImpliedCondition(), LLVM_DEBUG, llvm::reverse(), llvm::Instruction::setDebugLoc(), and ToRemove.

Referenced by processGuards().

◆ threadThroughTwoBasicBlocks()

void JumpThreadingPass::threadThroughTwoBasicBlocks	(	BasicBlock *	PredPredBB,
		BasicBlock *	PredBB,
		BasicBlock *	BB,
		BasicBlock *	SuccBB
	)

Definition at line 2251 of file JumpThreading.cpp.

Referenced by maybethreadThroughTwoBasicBlocks().

◆ tryThreadEdge()

bool JumpThreadingPass::tryThreadEdge	(	BasicBlock *	BB,
		const SmallVectorImpl< BasicBlock * > &	PredBBs,
		BasicBlock *	SuccBB
	)

tryThreadEdge - Thread an edge if it's safe and profitable to do so.

Definition at line 2327 of file JumpThreading.cpp.

References llvm::dbgs(), getJumpThreadDuplicationCost(), llvm::Value::getName(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, and threadEdge().

Referenced by processThreadableEdges().

◆ tryToUnfoldSelect() [1/2]

bool JumpThreadingPass::tryToUnfoldSelect	(	CmpInst *	CondCmp,
		BasicBlock *	BB
	)

tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2

bb2: p = phi [a, bb1] ... c = icmp p br i1 c

And expand the select into a branch structure if one of its arms allows c to be folded. This later enables threading from bb1 over bb2.

Definition at line 2857 of file JumpThreading.cpp.

References llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::User::getOperand(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::CmpInst::getPredicate(), llvm::LazyValueInfo::getPredicateOnEdge(), llvm::BasicBlock::getTerminator(), I, llvm::BranchInst::isConditional(), llvm::BranchInst::isUnconditional(), and unfoldSelectInstr().

Referenced by processBlock().

◆ tryToUnfoldSelect() [2/2]

bool JumpThreadingPass::tryToUnfoldSelect	(	SwitchInst *	SI,
		BasicBlock *	BB
	)

Definition at line 2819 of file JumpThreading.cpp.

References llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUse(), I, llvm::BranchInst::isUnconditional(), and unfoldSelectInstr().

◆ tryToUnfoldSelectInCurrBB()

bool JumpThreadingPass::tryToUnfoldSelectInCurrBB ( BasicBlock * BB )

tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = phi [false, bb1], [true, bb2], [false, bb3], [true, bb4], ... s = select p, trueval, falseval

or

bb: p = phi [0, bb1], [1, bb2], [0, bb3], [1, bb4], ... c = cmp p, 0 s = select c, trueval, falseval

And expand the select into a branch structure. This later enables jump-threading over bb in this pass.

Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold select if the associated PHI has at least one constant. If the unfolded select is not jump-threaded, it will be folded again in the later optimizations.

Definition at line 2916 of file JumpThreading.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), llvm::BasicBlock::begin(), Cond, llvm::PHINode::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::getBranchWeightMDNode(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::DebugLoc::getTemporary(), llvm::BasicBlock::getTerminator(), llvm::Function::hasFnAttribute(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::isGuaranteedNotToBeUndefOrPoison(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::match(), llvm::Instruction::setDebugLoc(), llvm::SplitBlockAndInsertIfThen(), and llvm::successors().

Referenced by processBlock().

◆ unfoldSelectInstr()

void JumpThreadingPass::unfoldSelectInstr	(	BasicBlock *	Pred,
		BasicBlock *	BB,
		SelectInst *	SI,
		PHINode *	SIUse,
		unsigned	Idx
	)

◆ updateSSA()

void JumpThreadingPass::updateSSA	(	BasicBlock *	BB,
		BasicBlock *	NewBB,
		ValueToValueMapTy &	ValueMapping
	)

Update the SSA form.

NewBB contains instructions that are copied from BB. ValueMapping maps old values in BB to new ones in NewBB.

Definition at line 1955 of file JumpThreading.cpp.

References llvm::SSAUpdater::AddAvailableValue(), llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), llvm::SmallVectorBase< Size_T >::empty(), llvm::erase_if(), llvm::findDbgValues(), llvm::DbgRecord::getParent(), I, llvm::SSAUpdater::Initialize(), LLVM_DEBUG, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SSAUpdater::RewriteUse(), and llvm::SSAUpdater::UpdateDebugValues().

Referenced by duplicateCondBranchOnPHIIntoPred(), threadEdge(), and threadThroughTwoBasicBlocks().

The documentation for this class was generated from the following files:

include/llvm/Transforms/Scalar/JumpThreading.h
lib/Transforms/Scalar/JumpThreading.cpp

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ JumpThreadingPass()

Member Function Documentation

◆ cloneInstructions()

◆ computeValueKnownInPredecessors()

◆ computeValueKnownInPredecessorsImpl()

◆ duplicateCondBranchOnPHIIntoPred()

◆ evaluateOnPredecessorEdge()

◆ findLoopHeaders()

◆ getDomTreeUpdater()

◆ maybeMergeBasicBlockIntoOnlyPred()

◆ maybethreadThroughTwoBasicBlocks()

◆ processBlock()

◆ processBranchOnPHI()

◆ processBranchOnXOR()

◆ processGuards()

◆ processImpliedCondition()

◆ processThreadableEdges()

◆ run()

◆ runImpl()

◆ simplifyPartiallyRedundantLoad()

◆ threadEdge()

◆ threadGuard()

◆ threadThroughTwoBasicBlocks()

◆ tryThreadEdge()

◆ tryToUnfoldSelect() [1/2]

◆ tryToUnfoldSelect() [2/2]

◆ tryToUnfoldSelectInCurrBB()

◆ unfoldSelectInstr()

◆ updateSSA()