LoopDeletion.cpp File Reference (original) (raw)

Go to the source code of this file.

Functions
	STATISTIC (NumDeleted, "Number of loops deleted")

	STATISTIC (NumBackedgesBroken, "Number of loops for which we managed to break the backedge")

static LoopDeletionResult	merge (LoopDeletionResult A, LoopDeletionResult B)

static bool	isLoopDead (Loop L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock > &ExitingBlocks, BasicBlock ExitBlock, bool &Changed, BasicBlock Preheader, LoopInfo &LI)
	Determines if a loop is dead.

static bool	isLoopNeverExecuted (Loop *L)
	This function returns true if there is no viable path from the entry block to the header of L.

static Value *	getValueOnFirstIteration (Value V, DenseMap< Value , Value * > &FirstIterValue, const SimplifyQuery &SQ)

static bool	canProveExitOnFirstIteration (Loop *L, DominatorTree &DT, LoopInfo &LI)

static LoopDeletionResult	breakBackedgeIfNotTaken (Loop L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA MSSA, OptimizationRemarkEmitter &ORE)
	If we can prove the backedge is untaken, remove it.

static LoopDeletionResult	deleteLoopIfDead (Loop L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA MSSA, OptimizationRemarkEmitter &ORE)
	Remove a loop if it is dead.

◆ DEBUG_TYPE

#define DEBUG_TYPE "loop-delete"

◆ LoopDeletionResult

◆ breakBackedgeIfNotTaken()

If we can prove the backedge is untaken, remove it.

This destroys the loop, but leaves the (now trivially loop invariant) control flow and side effects (if any) in place.

Definition at line 399 of file LoopDeletion.cpp.

References assert(), llvm::breakLoopBackedge(), canProveExitOnFirstIteration(), Deleted, llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::ScalarEvolution::isKnownNonZero(), llvm::SCEV::isZero(), and Unmodified.

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

◆ canProveExitOnFirstIteration()

Definition at line 216 of file LoopDeletion.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), EnableSymbolicExecution, From, llvm::PoisonValue::get(), llvm::BasicBlock::getParent(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::LoopBlocksRPO::perform(), llvm::predecessors(), and llvm::successors().

Referenced by breakBackedgeIfNotTaken().

◆ deleteLoopIfDead()

Remove a loop if it is dead.

A loop is considered dead either if it does not impact the observable behavior of the program other than finite running time, or if it is required to make progress by an attribute such as 'mustprogress' or 'llvm.loop.mustprogress' and does not make any. This may remove infinite loops that have been required to make progress.

This entire process relies pretty heavily on LoopSimplify form and LCSSA in order to make various safety checks work.

Returns

true if any changes were made. This may mutate the loop even if it is unable to delete it due to hoisting trivially loop invariant instructions out of the loop.

Definition at line 436 of file LoopDeletion.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, Deleted, llvm::deleteDeadLoop(), llvm::OptimizationRemarkEmitter::emit(), llvm::ScalarEvolution::forgetLoop(), llvm::PoisonValue::get(), llvm::BasicBlock::isEHPad(), isLoopDead(), isLoopNeverExecuted(), LLVM_DEBUG, Modified, P, llvm::BasicBlock::phis(), and Unmodified.

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

◆ getValueOnFirstIteration()

Definition at line 177 of file LoopDeletion.cpp.

References llvm::CallingConv::C, Cond, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), getValueOnFirstIteration(), LHS, RHS, Select, llvm::simplifyBinOp(), and llvm::simplifyICmpInst().

Referenced by getValueOnFirstIteration().

◆ isLoopDead()

Determines if a loop is dead.

This assumes that we've already checked for unique exit and exiting blocks, and that the code is in LCSSA form.

Definition at line 63 of file LoopDeletion.cpp.

References llvm::all_of(), llvm::any_of(), llvm::SmallVectorImpl< T >::append(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::dbgs(), llvm::SmallVectorBase< Size_T >::empty(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::BasicBlock::getTerminator(), llvm::hasMustProgress(), I, LLVM_DEBUG, P, llvm::LoopBlocksRPO::perform(), llvm::BasicBlock::phis(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by deleteLoopIfDead().

◆ isLoopNeverExecuted()

static bool isLoopNeverExecuted ( Loop * L)	static

◆ merge()

◆ STATISTIC() [1/2]

STATISTIC	(	NumBackedgesBroken	,
"Number of loops for which we managed to break the backedge"
)

◆ STATISTIC() [2/2]

STATISTIC	(	NumDeleted	,
"Number of loops deleted"
)

◆ EnableSymbolicExecution

cl::opt< bool > EnableSymbolicExecution("loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), cl::desc("Break backedge through symbolic execution of 1st iteration " "attempting to prove that the backedge is never taken")) ( "loop-deletion-enable-symbolic-execution" , cl::Hidden , cl::init(true) , cl::desc("Break backedge through symbolic execution of 1st iteration " "attempting to prove that the backedge is never taken") )

static