36#define DEBUG_TYPE "loop-delete"
40 "Number of loops for which we managed to break the backedge");
44 cl::desc(
"Break backedge through symbolic execution of 1st iteration "
45 "attempting to prove that the backedge is never taken"));
74 bool AllEntriesInvariant =
true;
75 bool AllOutgoingValuesSame =
true;
78 Value *incoming =
P.getIncomingValueForBlock(ExitingBlocks[0]);
84 AllOutgoingValuesSame =
86 return incoming ==
P.getIncomingValueForBlock(BB);
89 if (!AllOutgoingValuesSame)
95 AllEntriesInvariant =
false;
102 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
108 for (
const auto &
I : L->blocks())
110 return I.mayHaveSideEffects() && !
I.isDroppable();
118 if (L->getHeader()->getParent()->mustProgress())
124 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
129 while (!WorkList.
empty()) {
135 if (isa<SCEVCouldNotCompute>(S)) {
137 dbgs() <<
"Could not compute SCEV MaxBackedgeTakenCount and was "
138 "not required to make progress.\n");
150 using namespace PatternMatch;
152 auto *Preheader = L->getLoopPreheader();
155 assert(Preheader &&
"Needs preheader!");
157 if (Preheader->isEntryBlock())
164 if (!
match(Pred->getTerminator(),
167 if (!
Cond->getZExtValue())
169 if (Taken == Preheader)
173 "Preheader should have predecessors at this point!");
182 if (!isa<Instruction>(V))
185 auto Existing = FirstIterValue.
find(V);
186 if (Existing != FirstIterValue.
end())
187 return Existing->second;
188 Value *FirstIterV =
nullptr;
189 if (
auto *BO = dyn_cast<BinaryOperator>(V)) {
195 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(V)) {
201 }
else if (
auto *
Select = dyn_cast<SelectInst>(V)) {
204 if (
auto *
C = dyn_cast<ConstantInt>(
Cond)) {
205 auto *Selected =
C->isAllOnesValue() ?
Select->getTrueValue()
206 :
Select->getFalseValue();
212 FirstIterValue[V] = FirstIterV;
224 BasicBlock *Predecessor = L->getLoopPredecessor();
227 if (!Predecessor || !Latch)
238 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
246 LiveBlocks.
insert(Header);
252 "Only canonical backedges are allowed. Irreducible CFG?");
254 "We already discarded this block as dead!");
259 auto MarkAllSuccessorsLive = [&](
BasicBlock *BB) {
261 MarkLiveEdge(BB, Succ);
267 auto GetSoleInputOnFirstIteration = [&](
PHINode & PN)->
Value * {
269 bool HasLivePreds =
false;
272 return PN.getIncomingValueForBlock(Predecessor);
273 Value *OnlyInput =
nullptr;
275 if (LiveEdges.
count({ Pred, BB })) {
277 Value *Incoming = PN.getIncomingValueForBlock(Pred);
280 if (isa<UndefValue>(Incoming))
283 if (OnlyInput && OnlyInput != Incoming)
285 OnlyInput = Incoming;
288 assert(HasLivePreds &&
"No live predecessors?");
304 auto &
DL = Header->getModule()->getDataLayout();
306 for (
auto *BB : RPOT) {
310 if (!LiveBlocks.count(BB))
314 if (LI.getLoopFor(BB) != L) {
315 MarkAllSuccessorsLive(BB);
320 for (
auto &PN : BB->phis()) {
321 if (!PN.getType()->isIntegerTy())
323 auto *Incoming = GetSoleInputOnFirstIteration(PN);
324 if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
327 FirstIterValue[&PN] = FirstIterV;
331 using namespace PatternMatch;
334 auto *
Term = BB->getTerminator();
337 auto *ICmp = dyn_cast<ICmpInst>(
Cond);
338 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
339 MarkAllSuccessorsLive(BB);
345 if (KnownCondition == ICmp) {
347 MarkAllSuccessorsLive(BB);
350 if (isa<UndefValue>(KnownCondition)) {
362 if (
L->contains(IfTrue) &&
L->contains(IfFalse))
363 MarkLiveEdge(BB, IfTrue);
366 auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
367 if (!ConstCondition) {
369 MarkAllSuccessorsLive(BB);
372 if (ConstCondition->isAllOnesValue())
373 MarkLiveEdge(BB, IfTrue);
375 MarkLiveEdge(BB, IfFalse);
376 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
377 auto *SwitchValue =
SI->getCondition();
378 auto *SwitchValueOnFirstIter =
380 auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
381 if (!ConstSwitchValue) {
382 MarkAllSuccessorsLive(BB);
385 auto CaseIterator =
SI->findCaseValue(ConstSwitchValue);
386 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
388 MarkAllSuccessorsLive(BB);
394 return !LiveEdges.count({ Latch, Header });
404 assert(L->isLCSSAForm(DT) &&
"Expected LCSSA!");
406 if (!L->getLoopLatch())
410 if (!BTCMax->isZero()) {
412 if (!BTC->isZero()) {
419 ++NumBackedgesBroken;
442 assert(L->isLCSSAForm(DT) &&
"Expected LCSSA!");
447 BasicBlock *Preheader = L->getLoopPreheader();
448 if (!Preheader || !L->hasDedicatedExits()) {
451 <<
"Deletion requires Loop with preheader and dedicated exits.\n");
455 BasicBlock *ExitBlock = L->getUniqueExitBlock();
458 LLVM_DEBUG(
dbgs() <<
"Loop is proven to never execute, delete it!\n");
465 std::fill(
P.incoming_values().begin(),
P.incoming_values().end(),
471 <<
"Loop deleted because it never executes";
481 L->getExitingBlocks(ExitingBlocks);
487 if (!ExitBlock && !L->hasNoExitBlocks()) {
488 LLVM_DEBUG(
dbgs() <<
"Deletion requires at most one exit block.\n");
492 bool Changed =
false;
493 if (!
isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
503 <<
"Loop deleted because it is invariant";
517 std::string LoopName = std::string(L.getName());
527 if (Result != LoopDeletionResult::Deleted)
531 if (Result == LoopDeletionResult::Unmodified)
534 if (Result == LoopDeletionResult::Deleted)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
SmallVector< MachineOperand, 4 > Cond
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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 Value * getValueOnFirstIteration(Value *V, DenseMap< Value *, Value * > &FirstIterValue, const SimplifyQuery &SQ)
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
Remove a loop if it is dead.
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
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 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 bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, LoopInfo &LI)
static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock * > &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader, LoopInfo &LI)
Determines if a loop is dead.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This is the shared class of boolean and integer constants.
iterator find(const_arg_type_t< KeyT > Val)
Implements a dense probed hash-table based set.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool isLoopHeader(const BlockT *BB) const
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
Encapsulates MemorySSA, including all data associated with memory accesses.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
LLVM Value Representation.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto successors(const MachineBasicBlock *BB)
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Value * simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto predecessors(const MachineBasicBlock *BB)
bool pred_empty(const BasicBlock *BB)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...