#include "llvm/Transforms/Scalar/LICM.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <algorithm>
#include <utility>

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE "licm"

Typedefs
using	PointersAndHasReadsOutsideSet

Functions
	STATISTIC (NumCreatedBlocks, "Number of blocks created")
	STATISTIC (NumClonedBranches, "Number of branches cloned")
	STATISTIC (NumSunk, "Number of instructions sunk out of loop")
	STATISTIC (NumHoisted, "Number of instructions hoisted out of loop")
	STATISTIC (NumMovedLoads, "Number of load insts hoisted or sunk")
	STATISTIC (NumMovedCalls, "Number of call insts hoisted or sunk")
	STATISTIC (NumPromotionCandidates, "Number of promotion candidates")
	STATISTIC (NumLoadPromoted, "Number of load-only promotions")
	STATISTIC (NumLoadStorePromoted, "Number of load and store promotions")
	STATISTIC (NumMinMaxHoisted, "Number of min/max expressions hoisted out of the loop")
	STATISTIC (NumGEPsHoisted, "Number of geps reassociated and hoisted out of the loop")
	STATISTIC (NumAddSubHoisted, "Number of add/subtract expressions reassociated " "and hoisted out of the loop")
	STATISTIC (NumFPAssociationsHoisted, "Number of invariant FP expressions " "reassociated and hoisted out of the loop")
	STATISTIC (NumIntAssociationsHoisted, "Number of invariant int expressions " "reassociated and hoisted out of the loop")
	STATISTIC (NumBOAssociationsHoisted, "Number of invariant BinaryOp expressions " "reassociated and hoisted out of the loop")
static bool	inSubLoop (BasicBlock BB, Loop CurLoop, LoopInfo *LI)
	Little predicate that returns true if the specified basic block is in a subloop of the current one, not the current one itself.
static bool	isNotUsedOrFoldableInLoop (const Instruction &I, const Loop CurLoop, const LoopSafetyInfo SafetyInfo, TargetTransformInfo *TTI, bool &FoldableInLoop, bool LoopNestMode)
	Return true if the only users of this instruction are outside of the loop.
static void	hoist (Instruction &I, const DominatorTree DT, const Loop CurLoop, BasicBlock Dest, ICFLoopSafetyInfo SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution SE, OptimizationRemarkEmitter ORE)
	When an instruction is found to only use loop invariant operands that is safe to hoist, this instruction is called to do the dirty work.
static bool	sink (Instruction &I, LoopInfo LI, DominatorTree DT, const Loop CurLoop, ICFLoopSafetyInfo SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)
	When an instruction is found to only be used outside of the loop, this function moves it to the exit blocks and patches up SSA form as needed.
static bool	isSafeToExecuteUnconditionally (Instruction &Inst, const DominatorTree DT, const TargetLibraryInfo TLI, const Loop CurLoop, const LoopSafetyInfo SafetyInfo, OptimizationRemarkEmitter ORE, const Instruction CtxI, AssumptionCache *AC, bool AllowSpeculation)
	Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known not to trap when moved to the preheader.
static bool	noConflictingReadWrites (Instruction I, MemorySSA MSSA, AAResults AA, Loop CurLoop, SinkAndHoistLICMFlags &Flags)
static bool	pointerInvalidatedByLoop (MemorySSA MSSA, MemoryUse MU, Loop *CurLoop, Instruction &I, SinkAndHoistLICMFlags &Flags, bool InvariantGroup)
static bool	pointerInvalidatedByBlock (BasicBlock &BB, MemorySSA &MSSA, MemoryUse &MU)
static bool	hoistArithmetics (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Aggregates various functions for hoisting computations out of loop.
static Instruction *	cloneInstructionInExitBlock (Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo LI, const LoopSafetyInfo SafetyInfo, MemorySSAUpdater &MSSAU)
static void	eraseInstruction (Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
static void	moveInstructionBefore (Instruction &I, BasicBlock::iterator Dest, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE)
static void	foreachMemoryAccess (MemorySSA MSSA, Loop L, function_ref< void(Instruction *)> Fn)
static SmallVector< PointersAndHasReadsOutsideSet, 0 >	collectPromotionCandidates (MemorySSA MSSA, AliasAnalysis AA, Loop *L)
	INITIALIZE_PASS_BEGIN (LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
static bool	isLoadInvariantInLoop (LoadInst LI, DominatorTree DT, Loop *CurLoop)
static MemoryAccess *	getClobberingMemoryAccess (MemorySSA &MSSA, BatchAAResults &BAA, SinkAndHoistLICMFlags &Flags, MemoryUseOrDef *MA)
static bool	isTriviallyReplaceablePHI (const PHINode &PN, const Instruction &I)
	Returns true if a PHINode is a trivially replaceable with an Instruction.
static bool	isFoldableInLoop (const Instruction &I, const Loop CurLoop, const TargetTransformInfo TTI)
	Return true if the instruction is foldable in the loop.
static Instruction *	sinkThroughTriviallyReplaceablePHI (PHINode TPN, Instruction I, LoopInfo LI, SmallDenseMap< BasicBlock , Instruction , 32 > &SunkCopies, const LoopSafetyInfo SafetyInfo, const Loop *CurLoop, MemorySSAUpdater &MSSAU)
static bool	canSplitPredecessors (PHINode PN, LoopSafetyInfo SafetyInfo)
static void	splitPredecessorsOfLoopExit (PHINode PN, DominatorTree DT, LoopInfo LI, const Loop CurLoop, LoopSafetyInfo SafetyInfo, MemorySSAUpdater MSSAU)
static bool	hoistMinMax (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
	Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A < min(INV_1, INV_2)), if INV_1 and INV_2 are both loop invariants and their minimun can be computed outside of loop, and X is not a loop-invariant.
static bool	hoistGEP (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Reassociate gep (gep ptr, idx1), idx2 to gep (gep ptr, idx2), idx1 if this allows hoisting the inner GEP.
static bool	hoistAdd (ICmpInst::Predicate Pred, Value VariantLHS, Value InvariantRHS, ICmpInst &ICmp, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Try to turn things like "LV + C1 < C2" into "LV < C2 - C1".
static bool	hoistSub (ICmpInst::Predicate Pred, Value VariantLHS, Value InvariantRHS, ICmpInst &ICmp, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Try to reassociate and hoist the following two patterns: LV - C1 < C2 --> LV < C1 + C2, C1 - LV < C2 --> LV > C1 - C2.
static bool	hoistAddSub (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Reassociate and hoist add/sub expressions.
static bool	isReassociableOp (Instruction *I, unsigned IntOpcode, unsigned FPOpcode)
static bool	hoistMulAddAssociation (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Try to reassociate expressions like ((A1 * B1) + (A2 * B2) + ...) * C where A1, A2, ... and C are loop invariants into expressions like ((A1 * C * B1) + (A2 * C * B2) + ...) and hoist the (A1 * C), (A2 * C), ... invariant expressions.
static bool	hoistBOAssociation (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache AC, DominatorTree DT)
	Reassociate associative binary expressions of the form.

Variables
static cl::opt< bool >	DisablePromotion ("disable-licm-promotion", cl::Hidden, cl::init(false), cl::desc("Disable memory promotion in LICM pass"))
	Memory promotion is enabled by default.
static cl::opt< bool >	ControlFlowHoisting ("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))
static cl::opt< bool >	SingleThread ("licm-force-thread-model-single", cl::Hidden, cl::init(false), cl::desc("Force thread model single in LICM pass"))
static cl::opt< uint32_t >	MaxNumUsesTraversed ("licm-max-num-uses-traversed", cl::Hidden, cl::init(8), cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)"))
static cl::opt< unsigned >	FPAssociationUpperLimit ("licm-max-num-fp-reassociations", cl::init(5U), cl::Hidden, cl::desc("Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))
static cl::opt< unsigned >	IntAssociationUpperLimit ("licm-max-num-int-reassociations", cl::init(5U), cl::Hidden, cl::desc("Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))
cl::opt< bool >	ProfcheckDisableMetadataFixes
	licm
Loop Invariant Code	Motion
Loop Invariant Code	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "licm"

Definition at line 94 of file LICM.cpp.

Typedef Documentation

◆ PointersAndHasReadsOutsideSet

using PointersAndHasReadsOutsideSet

Initial value:

std::pair<SmallSetVector<Value *, 8>, bool>

Definition at line 218 of file LICM.cpp.

Function Documentation

◆ canSplitPredecessors()

bool canSplitPredecessors	(	PHINode *	PN,
		LoopSafetyInfo *	SafetyInfo )

static

Definition at line 1487 of file LICM.cpp.

References llvm::BasicBlock::canSplitPredecessors(), llvm::LoopSafetyInfo::getBlockColors(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::isa(), and llvm::predecessors().

Referenced by sink().

◆ cloneInstructionInExitBlock()

Instruction * cloneInstructionInExitBlock	(	Instruction &	I,
		BasicBlock &	ExitBlock,
		PHINode &	PN,
		const LoopInfo *	LI,
		const LoopSafetyInfo *	SafetyInfo,
		MemorySSAUpdater &	MSSAU )

static

Definition at line 1373 of file LICM.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), llvm::MemorySSA::Beginning, llvm::cast(), llvm::CallInst::Create(), llvm::PHINode::Create(), llvm::MemorySSAUpdater::createMemoryAccessInBB(), llvm::dyn_cast(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::TinyPtrVector< EltTy >::front(), llvm::LoopSafetyInfo::getBlockColors(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::PHINode::getIncomingBlock(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::OperandBundleUse::getTagID(), I, llvm::Instruction::insertBefore(), llvm::MemorySSAUpdater::insertDef(), llvm::MemorySSAUpdater::insertUse(), llvm::LLVMContext::OB_funclet, llvm::TinyPtrVector< EltTy >::size(), and llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA().

Referenced by sinkThroughTriviallyReplaceablePHI().

◆ collectPromotionCandidates()

SmallVector< PointersAndHasReadsOutsideSet, 0 > collectPromotionCandidates	(	MemorySSA *	MSSA,
		AliasAnalysis *	AA,
		Loop *	L )

static

Definition at line 2239 of file LICM.cpp.

References llvm::AliasSetTracker::add(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dyn_cast(), llvm::erase_if(), foreachMemoryAccess(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getPointer(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::isModSet(), llvm::isRefSet(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::setInt().

◆ eraseInstruction()

void eraseInstruction	(	Instruction &	I,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU )

static

Definition at line 1450 of file LICM.cpp.

References I, llvm::ICFLoopSafetyInfo::removeInstruction(), and llvm::MemorySSAUpdater::removeMemoryAccess().

Referenced by hoistAdd(), hoistBOAssociation(), hoistGEP(), hoistMinMax(), hoistMulAddAssociation(), llvm::hoistRegion(), hoistSub(), llvm::promoteLoopAccessesToScalars(), sink(), and llvm::sinkRegion().

◆ foreachMemoryAccess()

void foreachMemoryAccess	(	MemorySSA *	MSSA,
		Loop *	L,
		function_ref< void(Instruction *)>	Fn )

static

Definition at line 2227 of file LICM.cpp.

References Access, Accesses, llvm::dyn_cast(), and llvm::MemorySSA::getBlockAccesses().

Referenced by collectPromotionCandidates().

◆ getClobberingMemoryAccess()

MemoryAccess * getClobberingMemoryAccess	(	MemorySSA &	MSSA,
		BatchAAResults &	BAA,
		SinkAndHoistLICMFlags &	Flags,
		MemoryUseOrDef *	MA )

static

Definition at line 1152 of file LICM.cpp.

References llvm::MemorySSAWalker::getClobberingMemoryAccess(), llvm::MemoryUseOrDef::getDefiningAccess(), and llvm::MemorySSA::getSkipSelfWalker().

Referenced by noConflictingReadWrites(), and pointerInvalidatedByLoop().

◆ hoist()

void hoist	(	Instruction &	I,
		const DominatorTree *	DT,
		const Loop *	CurLoop,
		BasicBlock *	Dest,
		ICFLoopSafetyInfo *	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		ScalarEvolution *	SE,
		OptimizationRemarkEmitter *	ORE )

static

When an instruction is found to only use loop invariant operands that is safe to hoist, this instruction is called to do the dirty work.

Definition at line 1683 of file LICM.cpp.

References llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getNameOrAsOperand(), llvm::BasicBlock::getTerminator(), I, llvm::isa(), llvm::ICFLoopSafetyInfo::isGuaranteedToExecute(), LLVM_DEBUG, and moveInstructionBefore().

Referenced by llvm::hoistRegion().

◆ hoistAdd()

bool hoistAdd	(	ICmpInst::Predicate	Pred,
		Value *	VariantLHS,
		Value *	InvariantRHS,
		ICmpInst &	ICmp,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Try to turn things like "LV + C1 < C2" into "LV < C2 - C1".

Here C1 and C2 are loop invariants and LV is a loop-variant.

Definition at line 2578 of file LICM.cpp.

References assert(), llvm::cast(), llvm::computeOverflowForSignedSub(), llvm::computeOverflowForUnsignedSub(), DL, eraseInstruction(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::isSigned(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_NUWAdd(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::NeverOverflows, llvm::salvageDebugInfo(), llvm::User::setOperand(), llvm::CmpInst::setPredicate(), and std::swap().

Referenced by hoistAddSub().

◆ hoistAddSub()

bool hoistAddSub	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Reassociate and hoist add/sub expressions.

Definition at line 2715 of file LICM.cpp.

References llvm::cast(), llvm::CmpInst::getSwappedPredicate(), hoistAdd(), hoistSub(), I, LHS, llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), RHS, and std::swap().

Referenced by hoistArithmetics().

◆ hoistArithmetics()

bool hoistArithmetics	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Aggregates various functions for hoisting computations out of loop.

Definition at line 2930 of file LICM.cpp.

References hoistAddSub(), hoistBOAssociation(), hoistGEP(), hoistMinMax(), hoistMulAddAssociation(), and I.

Referenced by llvm::hoistRegion().

◆ hoistBOAssociation()

bool hoistBOAssociation	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Reassociate associative binary expressions of the form.

"(LV op C1) op C2" ==> "LV op (C1 op C2)"
"(C1 op LV) op C2" ==> "LV op (C1 op C2)"
"C2 op (C1 op LV)" ==> "LV op (C1 op C2)"
"C2 op (LV op C1)" ==> "LV op (C1 op C2)"

where op is an associative BinOp, LV is a loop variant, and C1 and C2 are loop invariants that we want to hoist, noting that associativity implies commutativity.

Definition at line 2863 of file LICM.cpp.

References llvm::OverflowTracking::AllKnownNonNegative, assert(), llvm::BinaryOperator::Create(), llvm::dyn_cast(), eraseInstruction(), llvm::DebugLoc::getDropped(), llvm::Value::getName(), llvm::BasicBlock::getTerminator(), I, llvm::salvageDebugInfo(), and std::swap().

Referenced by hoistArithmetics().

◆ hoistGEP()

bool hoistGEP	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Reassociate gep (gep ptr, idx1), idx2 to gep (gep ptr, idx2), idx1 if this allows hoisting the inner GEP.

Definition at line 2520 of file LICM.cpp.

References llvm::all_of(), DL, llvm::dyn_cast(), eraseInstruction(), GEP, llvm::BasicBlock::getTerminator(), I, llvm::isKnownNonNegative(), NonNegative, and llvm::salvageDebugInfo().

Referenced by hoistArithmetics().

◆ hoistMinMax()

bool hoistMinMax	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU )

static

Try to simplify things like (A < INV_1 AND icmp A < INV_2) into (A < min(INV_1, INV_2)), if INV_1 and INV_2 are both loop invariants and their minimun can be computed outside of loop, and X is not a loop-invariant.

Definition at line 2439 of file LICM.cpp.

References assert(), llvm::CallingConv::C, llvm::cast(), eraseInstruction(), llvm::CmpInst::getInversePredicate(), llvm::CmpPredicate::getMatching(), llvm::Value::getName(), llvm::CmpInst::getSwappedPredicate(), llvm::BasicBlock::getTerminator(), I, llvm::isa(), llvm::ICmpInst::isGE(), llvm::ICmpInst::isGT(), llvm::ICmpInst::isLE(), llvm::ICmpInst::isLT(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isSigned(), LHS, llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), P, RHS, llvm::salvageDebugInfo(), std::swap(), and llvm::Value::takeName().

Referenced by hoistArithmetics().

◆ hoistMulAddAssociation()

bool hoistMulAddAssociation	(	Instruction &	I,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Try to reassociate expressions like ((A1 * B1) + (A2 * B2) + ...) * C where A1, A2, ... and C are loop invariants into expressions like ((A1 * C * B1) + (A2 * C * B2) + ...) and hoist the (A1 * C), (A2 * C), ... invariant expressions.

This functions returns true only if any hoisting has actually occured.

Definition at line 2760 of file LICM.cpp.

References llvm::Add, assert(), llvm::cast(), llvm::BinaryOperator::Create(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), eraseInstruction(), FPAssociationUpperLimit, llvm::DebugLoc::getDropped(), llvm::User::getOperand(), llvm::User::getOperandUse(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUse(), I, IntAssociationUpperLimit, llvm::isa(), isReassociableOp(), LHS, Mul, OpIdx, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), RHS, llvm::SmallVectorTemplateCommon< T, typename >::size(), and std::swap().

Referenced by hoistArithmetics().

◆ hoistSub()

bool hoistSub	(	ICmpInst::Predicate	Pred,
		Value *	VariantLHS,
		Value *	InvariantRHS,
		ICmpInst &	ICmp,
		Loop &	L,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		AssumptionCache *	AC,
		DominatorTree *	DT )

static

Try to reassociate and hoist the following two patterns: LV - C1 < C2 --> LV < C1 + C2, C1 - LV < C2 --> LV > C1 - C2.

Definition at line 2636 of file LICM.cpp.

References assert(), llvm::cast(), llvm::computeOverflowForSignedAdd(), llvm::computeOverflowForSignedSub(), llvm::computeOverflowForUnsignedAdd(), llvm::computeOverflowForUnsignedSub(), DL, eraseInstruction(), llvm::CmpInst::getSwappedPredicate(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::isSigned(), llvm::PatternMatch::m_NSWSub(), llvm::PatternMatch::m_NUWSub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::NeverOverflows, llvm::salvageDebugInfo(), llvm::User::setOperand(), llvm::CmpInst::setPredicate(), and std::swap().

Referenced by hoistAddSub().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LegacyLICMPass	,
		"licm"	,
		"Loop Invariant Code Motion"	,
		false	,
		false	)

References INITIALIZE_PASS_DEPENDENCY.

◆ inSubLoop()

bool inSubLoop	(	BasicBlock *	BB,
		Loop *	CurLoop,
		LoopInfo *	LI )

static

Little predicate that returns true if the specified basic block is in a subloop of the current one, not the current one itself.

Definition at line 2979 of file LICM.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), and llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor().

Referenced by llvm::hoistRegion(), and llvm::sinkRegion().

◆ isFoldableInLoop()

bool isFoldableInLoop	(	const Instruction &	I,
		const Loop *	CurLoop,
		const TargetTransformInfo *	TTI )

static

Return true if the instruction is foldable in the loop.

Definition at line 1301 of file LICM.cpp.

References llvm::cast(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), GEP, llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, llvm::isa(), llvm::TargetTransformInfo::TCC_Free, and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by isNotUsedOrFoldableInLoop().

◆ isLoadInvariantInLoop()

bool isLoadInvariantInLoop	(	LoadInst *	LI,
		DominatorTree *	DT,
		Loop *	CurLoop )

static

Definition at line 1065 of file LICM.cpp.

References llvm::cast(), DL, llvm::dyn_cast(), llvm::Instruction::getDataLayout(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoadInst::getPointerOperand(), llvm::ConstantInt::getSExtValue(), llvm::Value::getType(), II, llvm::isa(), llvm::ConstantInt::isNegative(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable(), MaxNumUsesTraversed, llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), and llvm::Value::users().

Referenced by llvm::canSinkOrHoistInst().

◆ isNotUsedOrFoldableInLoop()

bool isNotUsedOrFoldableInLoop	(	const Instruction &	I,
		const Loop *	CurLoop,
		const LoopSafetyInfo *	SafetyInfo,
		TargetTransformInfo *	TTI,
		bool &	FoldableInLoop,
		bool	LoopNestMode )

static

Return true if the only users of this instruction are outside of the loop.

If this is true, we can sink the instruction to the exit blocks of the loop.

We also return true if the instruction could be folded away in lowering. (e.g., a GEP can be folded into a load as an addressing mode in the loop).

Definition at line 1331 of file LICM.cpp.

References llvm::cast(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopSafetyInfo::getBlockColors(), llvm::User::getNumOperands(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUser(), I, llvm::isa(), isFoldableInLoop(), and llvm::Instruction::user_back().

Referenced by llvm::sinkRegion().

◆ isReassociableOp()

bool isReassociableOp	(	Instruction *	I,
		unsigned	IntOpcode,
		unsigned	FPOpcode )

static

Definition at line 2745 of file LICM.cpp.

References I.

Referenced by FindSingleUseMultiplyFactors(), hoistMulAddAssociation(), LinearizeExprTree(), NegateValue(), ShouldBreakUpSubtract(), and shouldConvertOrWithNoCommonBitsToAdd().

◆ isSafeToExecuteUnconditionally()

bool isSafeToExecuteUnconditionally	(	Instruction &	Inst,
		const DominatorTree *	DT,
		const TargetLibraryInfo *	TLI,
		const Loop *	CurLoop,
		const LoopSafetyInfo *	SafetyInfo,
		OptimizationRemarkEmitter *	ORE,
		const Instruction *	CtxI,
		AssumptionCache *	AC,
		bool	AllowSpeculation )

static

Only sink or hoist an instruction if it is not a trapping instruction, or if the instruction is known not to trap when moved to the preheader.

or if it is a trapping instruction and is guaranteed to execute.

Definition at line 1730 of file LICM.cpp.

References DEBUG_TYPE, llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::LoopSafetyInfo::isGuaranteedToExecute(), llvm::Loop::isLoopInvariant(), and llvm::isSafeToSpeculativelyExecute().

Referenced by llvm::hoistRegion(), and llvm::promoteLoopAccessesToScalars().

◆ isTriviallyReplaceablePHI()

bool isTriviallyReplaceablePHI	(	const PHINode &	PN,
		const Instruction &	I )

static

Returns true if a PHINode is a trivially replaceable with an Instruction.

This is true when all incoming values are that instruction. This pattern occurs most often with LCSSA PHI nodes.

Definition at line 1292 of file LICM.cpp.

References I, and llvm::PHINode::incoming_values().

Referenced by sink(), and sinkThroughTriviallyReplaceablePHI().

◆ moveInstructionBefore()

void moveInstructionBefore	(	Instruction &	I,
		BasicBlock::iterator	Dest,
		ICFLoopSafetyInfo &	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		ScalarEvolution *	SE )

static

Definition at line 1457 of file LICM.cpp.

References llvm::MemorySSA::BeforeTerminator, llvm::cast_or_null(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), I, llvm::ICFLoopSafetyInfo::insertInstructionTo(), llvm::MemorySSAUpdater::moveToPlace(), and llvm::ICFLoopSafetyInfo::removeInstruction().

Referenced by hoist(), and llvm::hoistRegion().

◆ noConflictingReadWrites()

bool noConflictingReadWrites	(	Instruction *	I,
		MemorySSA *	MSSA,
		AAResults *	AA,
		Loop *	CurLoop,
		SinkAndHoistLICMFlags &	Flags )

static

◆ pointerInvalidatedByBlock()

bool pointerInvalidatedByBlock	(	BasicBlock &	BB,
		MemorySSA &	MSSA,
		MemoryUse &	MU )

static

Definition at line 2427 of file LICM.cpp.

References Accesses, llvm::dyn_cast(), llvm::MemoryAccess::getBlock(), llvm::MemorySSA::getBlockDefs(), and llvm::MemorySSA::locallyDominates().

Referenced by pointerInvalidatedByLoop().

◆ pointerInvalidatedByLoop()

bool pointerInvalidatedByLoop	(	MemorySSA *	MSSA,
		MemoryUse *	MU,
		Loop *	CurLoop,
		Instruction &	I,
		SinkAndHoistLICMFlags &	Flags,
		bool	InvariantGroup )

static

Definition at line 2376 of file LICM.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::MemorySSA::getAA(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), getClobberingMemoryAccess(), llvm::LoopBase< BlockT, LoopT >::getHeader(), I, llvm::isa(), llvm::MemorySSA::isLiveOnEntryDef(), and pointerInvalidatedByBlock().

Referenced by llvm::canSinkOrHoistInst().

◆ sink()

bool sink	(	Instruction &	I,
		LoopInfo *	LI,
		DominatorTree *	DT,
		const Loop *	CurLoop,
		ICFLoopSafetyInfo *	SafetyInfo,
		MemorySSAUpdater &	MSSAU,
		OptimizationRemarkEmitter *	ORE )

static

When an instruction is found to only be used outside of the loop, this function moves it to the exit blocks and patches up SSA form as needed.

This method is guaranteed to remove the original instruction from its position, and may either delete it or move it to outside of the loop.

Definition at line 1577 of file LICM.cpp.

References assert(), canSplitPredecessors(), llvm::cast(), Changed, llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::SmallPtrSetImplBase::empty(), eraseInstruction(), llvm::from_range, llvm::PoisonValue::get(), llvm::PHINode::getIncomingBlock(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlocks(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::DominatorTree::isReachableFromEntry(), isTriviallyReplaceablePHI(), LLVM_DEBUG, llvm::Value::replaceAllUsesWith(), sinkThroughTriviallyReplaceablePHI(), splitPredecessorsOfLoopExit(), and Users.

Referenced by llvm::GCOVFile::readGCDA(), and llvm::sinkRegion().

◆ sinkThroughTriviallyReplaceablePHI()

Instruction * sinkThroughTriviallyReplaceablePHI	(	PHINode *	TPN,
		Instruction *	I,
		LoopInfo *	LI,
		SmallDenseMap< BasicBlock , Instruction , 32 > &	SunkCopies,
		const LoopSafetyInfo *	SafetyInfo,
		const Loop *	CurLoop,
		MemorySSAUpdater &	MSSAU )

static

Definition at line 1472 of file LICM.cpp.

References assert(), cloneInstructionInExitBlock(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, isTriviallyReplaceablePHI(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by sink().

◆ splitPredecessorsOfLoopExit()

void splitPredecessorsOfLoopExit	(	PHINode *	PN,
		DominatorTree *	DT,
		LoopInfo *	LI,
		const Loop *	CurLoop,
		LoopSafetyInfo *	SafetyInfo,
		MemorySSAUpdater *	MSSAU )

static

Definition at line 1505 of file LICM.cpp.

References assert(), llvm::SetVector< T, Vector, Set, N >::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopSafetyInfo::copyColors(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::from_range, llvm::PHINode::getBasicBlockIndex(), llvm::LoopSafetyInfo::getBlockColors(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlocks(), llvm::pred_begin(), llvm::pred_end(), llvm::SetVector< T, Vector, Set, N >::remove(), and llvm::SplitBlockPredecessors().

Referenced by sink().

◆ STATISTIC() [1/15]

STATISTIC	(	NumAddSubHoisted	,
		"Number of add/subtract expressions reassociated " "and hoisted out of the loop"	)

◆ STATISTIC() [2/15]

STATISTIC	(	NumBOAssociationsHoisted	,
		"Number of invariant BinaryOp expressions " "reassociated and hoisted out of the loop"	)

◆ STATISTIC() [3/15]

STATISTIC	(	NumClonedBranches	,
		"Number of branches cloned"	)

◆ STATISTIC() [4/15]

STATISTIC	(	NumCreatedBlocks	,
		"Number of blocks created"	)

◆ STATISTIC() [5/15]

STATISTIC	(	NumFPAssociationsHoisted	,
		"Number of invariant FP expressions " "reassociated and hoisted out of the loop"	)

◆ STATISTIC() [6/15]

STATISTIC	(	NumGEPsHoisted	,
		"Number of geps reassociated and hoisted out of the loop"	)

◆ STATISTIC() [7/15]

STATISTIC	(	NumHoisted	,
		"Number of instructions hoisted out of loop"	)

◆ STATISTIC() [8/15]

STATISTIC	(	NumIntAssociationsHoisted	,
		"Number of invariant int expressions " "reassociated and hoisted out of the loop"	)

◆ STATISTIC() [9/15]

STATISTIC	(	NumLoadPromoted	,
		"Number of load-only promotions"	)

◆ STATISTIC() [10/15]

STATISTIC	(	NumLoadStorePromoted	,
		"Number of load and store promotions"	)

◆ STATISTIC() [11/15]

STATISTIC	(	NumMinMaxHoisted	,
		"Number of min/max expressions hoisted out of the loop"	)

◆ STATISTIC() [12/15]

STATISTIC	(	NumMovedCalls	,
		"Number of call insts hoisted or sunk"	)

◆ STATISTIC() [13/15]

STATISTIC	(	NumMovedLoads	,
		"Number of load insts hoisted or sunk"	)

◆ STATISTIC() [14/15]

STATISTIC	(	NumPromotionCandidates	,
		"Number of promotion candidates"	)

◆ STATISTIC() [15/15]

STATISTIC	(	NumSunk	,
		"Number of instructions sunk out of loop"	)

Variable Documentation

◆ ControlFlowHoisting

cl::opt< bool > ControlFlowHoisting("licm-control-flow-hoisting", cl::Hidden, cl::init(false), cl::desc("Enable control flow (and PHI) hoisting in LICM"))	(	"licm-control-flow-hoisting"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Enable control flow (and PHI) hoisting in LICM")	)

static

Referenced by llvm::hoistRegion().

◆ DisablePromotion

cl::opt< bool > DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false), cl::desc("Disable memory promotion in LICM pass"))	(	"disable-licm-promotion"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Disable memory promotion in LICM pass")	)

static

Memory promotion is enabled by default.

◆ false

Loop Invariant Code false

Definition at line 381 of file LICM.cpp.

◆ FPAssociationUpperLimit

cl::opt< unsigned > FPAssociationUpperLimit("licm-max-num-fp-reassociations", cl::init(5U), cl::Hidden, cl::desc( "Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))	(	"licm-max-num-fp-reassociations"	,
		cl::init(5U)	,
		cl::Hidden	,
		cl::desc( "Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions.")	)

static

Referenced by hoistMulAddAssociation().

◆ IntAssociationUpperLimit

cl::opt< unsigned > IntAssociationUpperLimit("licm-max-num-int-reassociations", cl::init(5U), cl::Hidden, cl::desc( "Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions."))	(	"licm-max-num-int-reassociations"	,
		cl::init(5U)	,
		cl::Hidden	,
		cl::desc( "Set upper limit for the number of transformations performed " "during a single round of hoisting the reassociated expressions.")	)

static

Referenced by hoistMulAddAssociation().

◆ licm

licm

Definition at line 381 of file LICM.cpp.

Referenced by llvm::VPlanTransforms::optimize().

◆ MaxNumUsesTraversed

cl::opt< uint32_t > MaxNumUsesTraversed("licm-max-num-uses-traversed", cl::Hidden, cl::init(8), cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)"))	(	"licm-max-num-uses-traversed"	,
		cl::Hidden	,
		cl::init(8)	,
		cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)")	)

static

Referenced by isLoadInvariantInLoop().

◆ Motion

Loop Invariant Code Motion

Definition at line 381 of file LICM.cpp.

◆ ProfcheckDisableMetadataFixes

cl::opt<bool> ProfcheckDisableMetadataFixes

extern

◆ SingleThread

cl::opt< bool > SingleThread("licm-force-thread-model-single", cl::Hidden, cl::init(false), cl::desc("Force thread model single in LICM pass"))	(	"licm-force-thread-model-single"	,
		cl::Hidden	,
		cl::init(false)	,
		cl::desc("Force thread model single in LICM pass")	)

static

Referenced by LLVM_ATTRIBUTE_C_DEPRECATED().

Namespaces

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ PointersAndHasReadsOutsideSet

Function Documentation

◆ canSplitPredecessors()

◆ cloneInstructionInExitBlock()

◆ collectPromotionCandidates()

◆ eraseInstruction()

◆ foreachMemoryAccess()

◆ getClobberingMemoryAccess()

◆ hoist()

◆ hoistAdd()

◆ hoistAddSub()

◆ hoistArithmetics()

◆ hoistBOAssociation()

◆ hoistGEP()

◆ hoistMinMax()

◆ hoistMulAddAssociation()

◆ hoistSub()

◆ INITIALIZE_PASS_BEGIN()

◆ inSubLoop()

◆ isFoldableInLoop()

◆ isLoadInvariantInLoop()

◆ isNotUsedOrFoldableInLoop()

◆ isReassociableOp()

◆ isSafeToExecuteUnconditionally()

◆ isTriviallyReplaceablePHI()

◆ moveInstructionBefore()

◆ noConflictingReadWrites()

◆ pointerInvalidatedByBlock()

◆ pointerInvalidatedByLoop()

◆ sink()

◆ sinkThroughTriviallyReplaceablePHI()

◆ splitPredecessorsOfLoopExit()

◆ STATISTIC() [1/15]

◆ STATISTIC() [2/15]

◆ STATISTIC() [3/15]

◆ STATISTIC() [4/15]

◆ STATISTIC() [5/15]

◆ STATISTIC() [6/15]

◆ STATISTIC() [7/15]

◆ STATISTIC() [8/15]

◆ STATISTIC() [9/15]

◆ STATISTIC() [10/15]

◆ STATISTIC() [11/15]

◆ STATISTIC() [12/15]

◆ STATISTIC() [13/15]

◆ STATISTIC() [14/15]

◆ STATISTIC() [15/15]

Variable Documentation

◆ ControlFlowHoisting

◆ DisablePromotion

◆ false

◆ FPAssociationUpperLimit

◆ IntAssociationUpperLimit

◆ licm

◆ MaxNumUsesTraversed

◆ Motion

◆ ProfcheckDisableMetadataFixes

◆ SingleThread