LLVM
15.0.0git
|
#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"
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 |
#define DEBUG_TYPE "loop-delete" |
Definition at line 36 of file LoopDeletion.cpp.
|
strong |
Enumerator | |
---|---|
Unmodified | |
Modified | |
Deleted |
Definition at line 47 of file LoopDeletion.cpp.
|
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().
|
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().
|
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.
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().
|
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 | ( | LoopDeletionLegacyPass | , |
"loop-deletion" | , | ||
"Delete dead loops" | , | ||
false | , | ||
false | |||
) |
|
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().
|
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().
|
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().
loop deletion |
Definition at line 566 of file LoopDeletion.cpp.
|
static |
Referenced by canProveExitOnFirstIteration().
loop Delete dead false |
Definition at line 567 of file LoopDeletion.cpp.
loop Delete dead loops |
Definition at line 567 of file LoopDeletion.cpp.