LoopDeletion.cpp File Reference

#include "llvm/Transforms/Scalar/LoopDeletion.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PatternMatch.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")
static bool	isLoopDead (Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock *> &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader)
	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 LoopDeletionResult	deleteLoopIfDead (Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI)
	Remove a loop if it is dead. More...
	INITIALIZE_PASS_BEGIN (LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass

Variables
loop	deletion
loop Delete dead	loops
loop Delete dead	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-delete"

Definition at line 29 of file LoopDeletion.cpp.

Enumeration Type Documentation

LoopDeletionResult

enum LoopDeletionResult

strong

Enumerator
Unmodified
Modified
Deleted

Definition at line 33 of file LoopDeletion.cpp.

Function Documentation

deleteLoopIfDead()

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

static

Remove a loop if it is dead.

A loop is considered dead if it does not impact the observable behavior of the program other than finite running time. This never removes a loop that might be infinite (unless it is never executed), as doing so could change the halting/non-halting nature of a program.

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

References assert(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::dbgs(), Deleted, llvm::deleteDeadLoop(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::UndefValue::get(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ScalarEvolution::getMaxBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getUniqueExitBlock(), llvm::LoopBase< BlockT, LoopT >::hasDedicatedExits(), llvm::Loop::isLCSSAForm(), isLoopDead(), isLoopNeverExecuted(), LLVM_DEBUG, Modified, P, llvm::BasicBlock::phis(), and llvm::Unmodified.

Referenced by llvm::createLoopDeletionPass(), and llvm::LoopDeletionPass::run().

INITIALIZE_PASS_BEGIN()

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

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

isLoopDead()

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

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

References llvm::all_of(), llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::blocks(), llvm::ScalarEvolution::forgetLoopDispositions(), llvm::BasicBlock::getTerminator(), I, llvm::makeArrayRef(), llvm::Loop::makeLoopInvariant(), llvm::Instruction::mayHaveSideEffects(), P, and llvm::BasicBlock::phis().

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

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

Referenced by deleteLoopIfDead().

STATISTIC()

STATISTIC	(	NumDeleted	,
		"Number of loops deleted"
	)

Variable Documentation

deletion

loop deletion

Definition at line 247 of file LoopDeletion.cpp.

false

loop Delete dead false

Definition at line 247 of file LoopDeletion.cpp.

loops

loop Delete dead loops

Definition at line 247 of file LoopDeletion.cpp.