LLVM  14.0.0git
Macros | Enumerations | Functions | Variables
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/GlobalsModRef.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/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")
 
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 ValuegetValueOnFirstIteration (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 45 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 400 of file LoopDeletion.cpp.

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

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

◆ canProveExitOnFirstIteration()

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

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

References assert(), llvm::dbgs(), DEBUG_TYPE, Deleted, llvm::deleteDeadLoop(), llvm::OptimizationRemarkEmitter::emit(), llvm::ScalarEvolution::forgetLoop(), llvm::UndefValue::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

◆ 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

◆ 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 148 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

◆ STATISTIC()

STATISTIC ( NumDeleted  ,
"Number of loops deleted"   
)

Variable Documentation

◆ deletion

loop deletion

Definition at line 568 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

◆ false

loop Delete dead false

Definition at line 569 of file LoopDeletion.cpp.

◆ loops

loop Delete dead loops

Definition at line 569 of file LoopDeletion.cpp.