LLVM: lib/Transforms/Scalar/LoopFlatten.cpp File Reference (original) (raw)

Go to the source code of this file.

Macros
#define	DEBUG_TYPE "loop-flatten"

Functions
	STATISTIC (NumFlattened, "Number of loops flattened")
static bool	setLoopComponents (Value &TC, Value &TripCount, BinaryOperator &Increment, SmallPtrSetImpl< Instruction > &IterationInstructions)
static bool	verifyTripCount (Value RHS, Loop L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode &InductionPHI, Value &TripCount, BinaryOperator &Increment, BranchInst &BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool	findLoopComponents (Loop L, SmallPtrSetImpl< Instruction > &IterationInstructions, PHINode &InductionPHI, Value &TripCount, BinaryOperator &Increment, BranchInst &BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool	checkPHIs (FlattenInfo &FI, const TargetTransformInfo *TTI)
static bool	checkOuterLoopInsts (FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
static bool	checkIVUsers (FlattenInfo &FI)
static OverflowResult	checkOverflow (FlattenInfo &FI, DominatorTree DT, AssumptionCache AC)
static bool	CanFlattenLoopPair (FlattenInfo &FI, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, AssumptionCache AC, const TargetTransformInfo *TTI)
static bool	DoFlattenLoopPair (FlattenInfo &FI, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, AssumptionCache AC, const TargetTransformInfo TTI, LPMUpdater U, MemorySSAUpdater *MSSAU)
static bool	CanWidenIV (FlattenInfo &FI, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, AssumptionCache AC, const TargetTransformInfo *TTI)
static bool	FlattenLoopPair (FlattenInfo &FI, DominatorTree DT, LoopInfo LI, ScalarEvolution SE, AssumptionCache AC, const TargetTransformInfo TTI, LPMUpdater U, MemorySSAUpdater *MSSAU, const LoopAccessInfo &LAI)

Variables
static cl::opt< unsigned >	RepeatedInstructionThreshold ("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))
static cl::opt< bool >	AssumeNoOverflow ("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))
static cl::opt< bool >	WidenIV ("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
static cl::opt< bool >	VersionLoops ("loop-flatten-version-loops", cl::Hidden, cl::init(true), cl::desc("Version loops if flattened loop could overflow"))

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-flatten"

◆ CanFlattenLoopPair()

◆ CanWidenIV()

Definition at line 838 of file LoopFlatten.cpp.

References assert(), CanFlattenLoopPair(), llvm::createWideIV(), llvm::dbgs(), Deleted, DL, llvm::Value::dump(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), LLVM_DEBUG, llvm::WideIVInfo::NarrowIV, llvm::RecursivelyDeleteDeadPHINode(), and Rewriter.

Referenced by FlattenLoopPair().

◆ checkIVUsers()

bool checkIVUsers ( FlattenInfo & FI)	static

◆ checkOuterLoopInsts()

Definition at line 553 of file LoopFlatten.cpp.

References B(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BranchInst::getSuccessor(), I, llvm::isa(), llvm::isSafeToSpeculativelyExecute(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), RepeatedInstructionThreshold, and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by CanFlattenLoopPair().

◆ checkOverflow()

Definition at line 644 of file LoopFlatten.cpp.

References AssumeNoOverflow, llvm::cast(), llvm::computeOverflowForUnsignedMul(), llvm::dbgs(), DL, llvm::dyn_cast(), F, GEP, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::isa(), llvm::isGuaranteedToExecuteForEveryIteration(), LLVM_DEBUG, llvm::MayOverflow, llvm::NeverOverflows, and llvm::Value::users().

Referenced by FlattenLoopPair().

◆ checkPHIs()

Definition at line 468 of file LoopFlatten.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::PHINode::hasConstantValue(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, and llvm::BasicBlock::phis().

Referenced by CanFlattenLoopPair().

◆ DoFlattenLoopPair()

Definition at line 747 of file LoopFlatten.cpp.

References llvm::sampleprof::Base, llvm::cast(), llvm::BranchInst::Create(), llvm::dbgs(), DEBUG_TYPE, llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::DominatorTree::dominates(), llvm::Value::dump(), llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::LoopInfo::erase(), F, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::ScalarEvolution::forgetLoop(), GEP, llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Loop::getName(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), LLVM_DEBUG, PHI, llvm::Remark, llvm::MemorySSAUpdater::removeEdge(), llvm::PHINode::removeIncomingValue(), llvm::Value::replaceAllUsesWith(), and llvm::Instruction::setDebugLoc().

Referenced by FlattenLoopPair().

◆ findLoopComponents()

Definition at line 388 of file LoopFlatten.cpp.

References llvm::cast(), llvm::dbgs(), llvm::Value::dump(), llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULT, llvm::Increment, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, RHS, and verifyTripCount().

Referenced by CanFlattenLoopPair().

◆ FlattenLoopPair()

Definition at line 904 of file LoopFlatten.cpp.

References llvm::AlwaysOverflowsHigh, llvm::AlwaysOverflowsLow, assert(), Call, CanFlattenLoopPair(), CanWidenIV(), llvm::cast(), checkOverflow(), llvm::dbgs(), DL, DoFlattenLoopPair(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Type::getScalarSizeInBits(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::BranchInst::isConditional(), LLVM_DEBUG, llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), llvm::MayOverflow, llvm::BranchInst::setCondition(), llvm::LoopVersioning::versionLoop(), and VersionLoops.

Referenced by llvm::LoopFlattenPass::run().

◆ setLoopComponents()

◆ STATISTIC()

STATISTIC	(	NumFlattened	,
"Number of loops flattened"	)

◆ verifyTripCount()

Definition at line 321 of file LoopFlatten.cpp.

References llvm::dbgs(), llvm::dyn_cast(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::Value::getContext(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEV::getType(), llvm::ConstantInt::getValue(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm::Increment, llvm::isa(), LLVM_DEBUG, RHS, and setLoopComponents().

Referenced by findLoopComponents().

◆ AssumeNoOverflow

cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow")) ( "loop-flatten-assume-no-overflow" , cl::Hidden , cl::init(false) , cl::desc("Assume that the product of the two iteration " "trip counts will never overflow") )	static

◆ RepeatedInstructionThreshold

cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening")) ( "loop-flatten-cost-threshold" , cl::Hidden , cl::init(2) , cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening") )	static

◆ VersionLoops

cl::opt< bool > VersionLoops("loop-flatten-version-loops", cl::Hidden, cl::init(true), cl::desc("Version loops if flattened loop could overflow")) ( "loop-flatten-version-loops" , cl::Hidden , cl::init(true) , cl::desc("Version loops if flattened loop could overflow") )	static

◆ WidenIV

WidenIV::WidenIV ( "loop-flatten-widen-iv" , cl::Hidden , cl::init(true) , cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening") )	static