LICM.cpp File Reference

#include "llvm/Transforms/Scalar/LICM.h"
#include "ScalarOptions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PriorityWorklist.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/MemoryLocation.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/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/InitializePasses.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>

Go to the source code of this file.

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

Macros
#define	DEBUG_TYPE   "licm"

Typedefs
using	PointersAndHasReadsOutsideSet

Functions
	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 bool	hoistInsertPastInsert (InsertElementInst *Ins, Loop *CurLoop, DominatorTree *DT, BasicBlock *HoistDest, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
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, DominatorTree *DT, ICFLoopSafetyInfo *SafetyInfo, const SmallPtrSetImpl< const MDNode * > &LoopLocalAliasScopes, Loop *L)
	INITIALIZE_PASS_BEGIN (LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, false) INITIALIZE_PASS_END(LegacyLICMPass
static std::optional< uint64_t >	getConstantInsertionIndex (InsertElementInst *Ins)
static bool	isLoadInvariantInLoop (LoadInst *LI, DominatorTree *DT, Loop *CurLoop)
static bool	isHoistableAndSinkableInst (Instruction &I)
	Return true if-and-only-if we know how to (mechanically) both hoist and sink a given instruction out of a loop.
static bool	isOnlyMemoryAccess (const Instruction *I, const Loop *L, const MemorySSAUpdater &MSSAU)
	Return true if I is the only Instruction with a MemoryAccess in L.
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	isPotentiallyPromotable (const Instruction *I, const Loop *L)
	Returns whether I is a memory access that may be a candidate for promotion out of the loop L.
static bool	hasAnyMDOperandsFrom (const MDNode *N, const SmallPtrSetImpl< const MDNode * > &Operands)
	Returns whether N has any operand from the set Operands.
static SmallPtrSet< const StoreInst *, 8 >	collectStoresWithInvariantAATags (MemorySSA *MSSA, DominatorTree *DT, const SmallPtrSetImpl< const MDNode * > &LoopLocalAliasScopes, Loop *L)
	Returns the potentially promotable stores with AA tags that are valid along all non-unwinding execution paths of the loop L, which allows for the AA tags to be used when deciding promotions.
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.
static bool	hoistSubAddAssociation (Instruction &I, Loop &L, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU, AssumptionCache *AC, DominatorTree *DT)
	Reassociate add/sub expressions of the form:

Variables
	licm
Loop Invariant Code	Motion
Loop Invariant Code	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "licm"

Definition at line 96 of file LICM.cpp.

Typedef Documentation

PointersAndHasReadsOutsideSet

using PointersAndHasReadsOutsideSet

Initial value:

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

Definition at line 176 of file LICM.cpp.

Function Documentation

canSplitPredecessors()

bool canSplitPredecessors ( PHINode * PN, LoopSafetyInfo * SafetyInfo )

static

Definition at line 1247 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 1133 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, DominatorTree * DT, ICFLoopSafetyInfo * SafetyInfo, const SmallPtrSetImpl< const MDNode * > & LoopLocalAliasScopes, Loop * L )

static

Definition at line 2075 of file LICM.cpp.

References llvm::AliasSetTracker::add(), llvm::AliasSetTracker::addWithoutAATags(), collectStoresWithInvariantAATags(), 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::ICFLoopSafetyInfo::isGuaranteedToExecute(), llvm::isModSet(), isPotentiallyPromotable(), llvm::isRefSet(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::setInt().

collectStoresWithInvariantAATags()

SmallPtrSet< const StoreInst *, 8 > collectStoresWithInvariantAATags ( MemorySSA * MSSA, DominatorTree * DT, const SmallPtrSetImpl< const MDNode * > & LoopLocalAliasScopes, Loop * L )

static

Returns the potentially promotable stores with AA tags that are valid along all non-unwinding execution paths of the loop L, which allows for the AA tags to be used when deciding promotions.

Definition at line 2034 of file LICM.cpp.

References llvm::all_of(), llvm::any_of(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), foreachMemoryAccess(), llvm::MemoryLocation::get(), hasAnyMDOperandsFrom(), I, llvm::SmallPtrSetImpl< PtrType >::insert_range(), and isPotentiallyPromotable().

Referenced by collectPromotionCandidates().

eraseInstruction()

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

static

Definition at line 1210 of file LICM.cpp.

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

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

foreachMemoryAccess()

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

static

Definition at line 1995 of file LICM.cpp.

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

Referenced by collectPromotionCandidates(), and collectStoresWithInvariantAATags().

getClobberingMemoryAccess()

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

static

Definition at line 902 of file LICM.cpp.

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

Referenced by noConflictingReadWrites(), and pointerInvalidatedByLoop().

getConstantInsertionIndex()

std::optional< uint64_t > getConstantInsertionIndex ( InsertElementInst * Ins )

static

Definition at line 743 of file LICM.cpp.

References llvm::cast(), llvm::dyn_cast(), llvm::User::getOperand(), and llvm::InsertElementInst::getType().

Referenced by hoistInsertPastInsert().

hasAnyMDOperandsFrom()

bool hasAnyMDOperandsFrom ( const MDNode * N, const SmallPtrSetImpl< const MDNode * > & Operands )

static

Returns whether N has any operand from the set Operands.

Definition at line 2024 of file LICM.cpp.

References llvm::any_of(), N, and Operands.

Referenced by collectStoresWithInvariantAATags().

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 1444 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 hoistInsertPastInsert(), and 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 2399 of file LICM.cpp.

References assert(), llvm::cast(), llvm::computeOverflowForSignedSub(), llvm::computeOverflowForUnsignedSub(), DL, llvm::Instruction::dropPoisonGeneratingFlags(), eraseInstruction(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::isSigned(), llvm::PatternMatch::m_NSWAddLike(), llvm::PatternMatch::m_NUWAddLike(), 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 2542 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 2857 of file LICM.cpp.

References hoistAddSub(), hoistBOAssociation(), hoistGEP(), hoistMinMax(), hoistMulAddAssociation(), hoistSubAddAssociation(), 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.

1. "(LV op C1) op C2" ==> "LV op (C1 op C2)"
2. "(C1 op LV) op C2" ==> "LV op (C1 op C2)"
3. "C2 op (C1 op LV)" ==> "LV op (C1 op C2)"
4. "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 2691 of file LICM.cpp.

References llvm::OverflowTracking::AllKnownNonNegative, assert(), llvm::computeOverflowForSignedAdd(), llvm::BinaryOperator::Create(), llvm::dyn_cast(), eraseInstruction(), llvm::DebugLoc::getDropped(), llvm::Value::getName(), llvm::BasicBlock::getTerminator(), I, llvm::NeverOverflows, 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 2341 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().

hoistInsertPastInsert()

bool hoistInsertPastInsert ( InsertElementInst * Ins, Loop * CurLoop, DominatorTree * DT, BasicBlock * HoistDest, ICFLoopSafetyInfo * SafetyInfo, MemorySSAUpdater & MSSAU, ScalarEvolution * SE, OptimizationRemarkEmitter * ORE )

static

Definition at line 758 of file LICM.cpp.

References llvm::dyn_cast(), getConstantInsertionIndex(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::User::getOperand(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), hoist(), llvm::Loop::isLoopInvariant(), llvm::Instruction::moveBefore(), llvm::Value::replaceAllUsesWith(), and llvm::User::setOperand().

Referenced by llvm::hoistRegion().

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 2260 of file LICM.cpp.

References assert(), 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 occurred.

Definition at line 2587 of file LICM.cpp.

References llvm::Add, assert(), llvm::cast(), llvm::BinaryOperator::Create(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), eraseInstruction(), llvm::DebugLoc::getDropped(), llvm::User::getOperand(), llvm::User::getOperandUse(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUse(), I, llvm::isa(), isReassociableOp(), LHS, Mul, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceAllUsesWith(), 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 2460 of file LICM.cpp.

References assert(), llvm::cast(), llvm::computeOverflowForSignedAdd(), llvm::computeOverflowForSignedSub(), llvm::computeOverflowForUnsignedAdd(), llvm::computeOverflowForUnsignedSub(), DL, llvm::Instruction::dropPoisonGeneratingFlags(), 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().

hoistSubAddAssociation()

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

static

Reassociate add/sub expressions of the form:

1. "(LV + C1) - C2" ==> "LV + (C1 - C2)"
2. "(LV - C1) - C2" ==> "LV - (C1 + C2)"
3. "(LV - C1) + C2" ==> "LV + (C2 - C1)"

where LV is a loop variant, and C1 and C2 are loop invariants. Sub is not associative, but these algebraic identities allow hoisting invariant computations out of the loop.

Definition at line 2780 of file LICM.cpp.

References assert(), llvm::BinaryOperator::Create(), eraseInstruction(), llvm::DebugLoc::getDropped(), llvm::BasicBlock::getTerminator(), I, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_Instruction(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::salvageDebugInfo(), and std::swap().

Referenced by hoistArithmetics().

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 2912 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 1060 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().

isHoistableAndSinkableInst()

bool isHoistableAndSinkableInst ( Instruction & I )

static

Return true if-and-only-if we know how to (mechanically) both hoist and sink a given instruction out of a loop.

Does not address legality concerns such as aliasing or speculation safety.

Definition at line 874 of file LICM.cpp.

References I, and llvm::isa().

Referenced by llvm::canSinkOrHoistInst().

isLoadInvariantInLoop()

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

static

Definition at line 817 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(), llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), uint64_t, and llvm::Value::users().

Referenced by llvm::canHoistLoad().

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 1090 of file LICM.cpp.

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

Referenced by llvm::sinkRegion().

isOnlyMemoryAccess()

bool isOnlyMemoryAccess ( const Instruction * I, const Loop * L, const MemorySSAUpdater & MSSAU )

static

Return true if I is the only Instruction with a MemoryAccess in L.

Definition at line 886 of file LICM.cpp.

References llvm::cast(), llvm::MemorySSA::getBlockAccesses(), llvm::MemorySSAUpdater::getMemorySSA(), I, and llvm::isa().

Referenced by llvm::canSinkOrHoistInst().

isPotentiallyPromotable()

bool isPotentiallyPromotable ( const Instruction * I, const Loop * L )

static

Returns whether I is a memory access that may be a candidate for promotion out of the loop L.

Definition at line 2006 of file LICM.cpp.

References llvm::dyn_cast(), I, llvm::isa(), and llvm::isStrongerThanMonotonic().

Referenced by collectPromotionCandidates(), and collectStoresWithInvariantAATags().

isReassociableOp()

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

static

Definition at line 2572 of file LICM.cpp.

References I.

Referenced by FindSingleUseMultiplyFactors(), hoistMulAddAssociation(), isFMulAddCandidate(), 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 1491 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 1051 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 1217 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().

noConflictingReadWrites()

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

static

Definition at line 2157 of file LICM.cpp.

References Accesses, assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::MemorySSA::dominates(), llvm::dyn_cast(), llvm::MemorySSA::getBlockAccesses(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), getClobberingMemoryAccess(), llvm::MemorySSA::getMemoryAccess(), llvm::BatchAAResults::getModRefInfo(), I, llvm::isa(), llvm::MemorySSA::isLiveOnEntryDef(), and llvm::isNoModRef().

Referenced by llvm::canSinkOrHoistInst().

pointerInvalidatedByBlock()

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

static

Definition at line 2248 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 2197 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::canHoistLoad(), and 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 1337 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 1232 of file LICM.cpp.

References assert(), cloneInstructionInExitBlock(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, isTriviallyReplaceablePHI(), and llvm::DenseMapBase< StorageT, 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 1265 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/13]

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

STATISTIC() [2/13]

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

STATISTIC() [3/13]

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

STATISTIC() [4/13]

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

STATISTIC() [5/13]

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

STATISTIC() [6/13]

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

STATISTIC() [7/13]

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

STATISTIC() [8/13]

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

STATISTIC() [9/13]

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

STATISTIC() [10/13]

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

STATISTIC() [11/13]

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

STATISTIC() [12/13]

STATISTIC	(	NumPromotionCandidates	,
		"Number of promotion candidates"	)

STATISTIC() [13/13]

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

Variable Documentation

false

Loop Invariant Code false

Definition at line 342 of file LICM.cpp.

licm

licm

Definition at line 342 of file LICM.cpp.

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

Motion

Loop Invariant Code Motion

Definition at line 342 of file LICM.cpp.