LoopDeletion.cpp File Reference

#include "llvm/Transforms/Scalar/LoopDeletion.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/LoopUtils.h"

Include dependency graph for LoopDeletion.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-delete"

Enumerations
enum	LoopDeletionResult { LoopDeletionResult::Unmodified, LoopDeletionResult::Modified, LoopDeletionResult::Deleted }

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. More...
static bool	isLoopNeverExecuted (Loop *L)
	This function returns true if there is no viable path from the entry block to the header of L. More...
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. More...
static LoopDeletionResult	deleteLoopIfDead (Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
	Remove a loop if it is dead. More...
	INITIALIZE_PASS_BEGIN (LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass

Variables
static 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
loop Delete dead	loops
loop Delete dead	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-delete"

Definition at line 36 of file LoopDeletion.cpp.

Enumeration Type Documentation

LoopDeletionResult

enum LoopDeletionResult

strong

Enumerator
Unmodified
Modified
Deleted

Definition at line 47 of file LoopDeletion.cpp.

Function Documentation

breakBackedgeIfNotTaken()

static LoopDeletionResult breakBackedgeIfNotTaken ( Loop *  L, DominatorTree &  DT, ScalarEvolution &  SE, LoopInfo &  LI, MemorySSA *  MSSA, OptimizationRemarkEmitter &  ORE  )

static

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 402 of file LoopDeletion.cpp.

References assert(), llvm::breakLoopBackedge(), canProveExitOnFirstIteration(), Deleted, llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ScalarEvolution::isKnownNonZero(), llvm::Loop::isLCSSAForm(), and Unmodified.

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

canProveExitOnFirstIteration()

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

static

Definition at line 219 of file LoopDeletion.cpp.

References assert(), BB, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), EnableSymbolicExecution, From, llvm::UndefValue::get(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::LoopBlocksRPO::perform(), llvm::predecessors(), and llvm::successors().

Referenced by breakBackedgeIfNotTaken().

deleteLoopIfDead()

static LoopDeletionResult deleteLoopIfDead ( Loop *  L, DominatorTree &  DT, ScalarEvolution &  SE, LoopInfo &  LI, MemorySSA *  MSSA, OptimizationRemarkEmitter &  ORE  )

static

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 439 of file LoopDeletion.cpp.

References assert(), llvm::dbgs(), DEBUG_TYPE, Deleted, llvm::deleteDeadLoop(), llvm::OptimizationRemarkEmitter::emit(), llvm::ScalarEvolution::forgetLoop(), llvm::PoisonValue::get(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Loop::getStartLoc(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::LoopBase< BlockT, LoopT >::hasDedicatedExits(), llvm::LoopBase< BlockT, LoopT >::hasNoExitBlocks(), llvm::Loop::isLCSSAForm(), isLoopDead(), isLoopNeverExecuted(), LLVM_DEBUG, Modified, P, llvm::BasicBlock::phis(), and Unmodified.

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

getValueOnFirstIteration()

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

static

Definition at line 180 of file LoopDeletion.cpp.

References Cond, llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), LHS, RHS, llvm::MCID::Select, llvm::simplifyBinOp(), and llvm::simplifyICmpInst().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	LoopDeletionLegacyPass	,
		"loop-deletion"	,
		"Delete dead loops"	,
		false	,
		false
	)

isLoopDead()

static bool isLoopDead ( Loop *  L, ScalarEvolution &  SE, SmallVectorImpl< BasicBlock * > &  ExitingBlocks, BasicBlock *  ExitBlock, bool &  Changed, BasicBlock *  Preheader, LoopInfo &  LI  )

static

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 65 of file LoopDeletion.cpp.

References llvm::all_of(), llvm::any_of(), llvm::SmallVectorImpl< T >::append(), BB, llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::ScalarEvolution::forgetLoopDispositions(), llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::hasMustProgress(), llvm::LoopBase< BlockT, LoopT >::hasNoExitBlocks(), I, LLVM_DEBUG, llvm::makeArrayRef(), llvm::Loop::makeLoopInvariant(), llvm::Function::mustProgress(), P, llvm::LoopBlocksRPO::perform(), llvm::BasicBlock::phis(), llvm::SmallVectorImpl< T >::pop_back_val(), and S.

Referenced by deleteLoopIfDead().

isLoopNeverExecuted()

static bool isLoopNeverExecuted ( Loop *  L )

static

This function returns true if there is no viable path from the entry block to the header of L.

Right now, it only does a local search to save compile time.

Definition at line 150 of file LoopDeletion.cpp.

References assert(), Cond, llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::match(), llvm::pred_empty(), llvm::predecessors(), and std::swap().

Referenced by deleteLoopIfDead().

merge()

static LoopDeletionResult merge ( LoopDeletionResult  A, LoopDeletionResult  B  )

static

Definition at line 53 of file LoopDeletion.cpp.

References B, Deleted, Modified, and Unmodified.

Referenced by llvm::CCState::AnalyzeArgumentsSecondPass(), llvm::iplist_impl< simple_ilist< llvm::AliasSet, Options... >, ilist_traits< llvm::AliasSet > >::merge(), and llvm::LoopDeletionPass::run().

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"
	)

Variable Documentation

deletion

loop deletion

Definition at line 566 of file LoopDeletion.cpp.

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"))

static

Referenced by canProveExitOnFirstIteration().

false

loop Delete dead false

Definition at line 567 of file LoopDeletion.cpp.

loops

loop Delete dead loops

Definition at line 567 of file LoopDeletion.cpp.