LLVM 17.0.0git
LoopDeletion.cpp
Go to the documentation of this file.
1//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Dead Loop Deletion Pass. This pass is responsible
10// for eliminating loops with non-infinite computable trip counts that have no
11// side effects or volatile instructions, and do not contribute to the
12// computation of the function's return value.
13//
14//===----------------------------------------------------------------------===//
15
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/CFG.h"
26#include "llvm/IR/Dominators.h"
27
33
34using namespace llvm;
35
36#define DEBUG_TYPE "loop-delete"
37
38STATISTIC(NumDeleted, "Number of loops deleted");
39STATISTIC(NumBackedgesBroken,
40 "Number of loops for which we managed to break the backedge");
41
43 "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true),
44 cl::desc("Break backedge through symbolic execution of 1st iteration "
45 "attempting to prove that the backedge is never taken"));
46
50 Deleted,
51};
52
59}
60
61/// Determines if a loop is dead.
62///
63/// This assumes that we've already checked for unique exit and exiting blocks,
64/// and that the code is in LCSSA form.
65static bool isLoopDead(Loop *L, ScalarEvolution &SE,
66 SmallVectorImpl<BasicBlock *> &ExitingBlocks,
67 BasicBlock *ExitBlock, bool &Changed,
68 BasicBlock *Preheader, LoopInfo &LI) {
69 // Make sure that all PHI entries coming from the loop are loop invariant.
70 // Because the code is in LCSSA form, any values used outside of the loop
71 // must pass through a PHI in the exit block, meaning that this check is
72 // sufficient to guarantee that no loop-variant values are used outside
73 // of the loop.
74 bool AllEntriesInvariant = true;
75 bool AllOutgoingValuesSame = true;
76 if (ExitBlock) {
77 for (PHINode &P : ExitBlock->phis()) {
78 Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
79
80 // Make sure all exiting blocks produce the same incoming value for the
81 // block. If there are different incoming values for different exiting
82 // blocks, then it is impossible to statically determine which value
83 // should be used.
84 AllOutgoingValuesSame =
85 all_of(ArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
86 return incoming == P.getIncomingValueForBlock(BB);
87 });
88
89 if (!AllOutgoingValuesSame)
90 break;
91
92 if (Instruction *I = dyn_cast<Instruction>(incoming)) {
93 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator(),
94 /*MSSAU=*/nullptr, &SE)) {
95 AllEntriesInvariant = false;
96 break;
97 }
98 }
99 }
100 }
101
102 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
103 return false;
104
105 // Make sure that no instructions in the block have potential side-effects.
106 // This includes instructions that could write to memory, and loads that are
107 // marked volatile.
108 for (const auto &I : L->blocks())
109 if (any_of(*I, [](Instruction &I) {
110 return I.mayHaveSideEffects() && !I.isDroppable();
111 }))
112 return false;
113
114 // The loop or any of its sub-loops looping infinitely is legal. The loop can
115 // only be considered dead if either
116 // a. the function is mustprogress.
117 // b. all (sub-)loops are mustprogress or have a known trip-count.
118 if (L->getHeader()->getParent()->mustProgress())
119 return true;
120
121 LoopBlocksRPO RPOT(L);
122 RPOT.perform(&LI);
123 // If the loop contains an irreducible cycle, it may loop infinitely.
124 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
125 return false;
126
127 SmallVector<Loop *, 8> WorkList;
128 WorkList.push_back(L);
129 while (!WorkList.empty()) {
130 Loop *Current = WorkList.pop_back_val();
131 if (hasMustProgress(Current))
132 continue;
133
134 const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
135 if (isa<SCEVCouldNotCompute>(S)) {
137 dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
138 "not required to make progress.\n");
139 return false;
140 }
141 WorkList.append(Current->begin(), Current->end());
142 }
143 return true;
144}
145
146/// This function returns true if there is no viable path from the
147/// entry block to the header of \p L. Right now, it only does
148/// a local search to save compile time.
149static bool isLoopNeverExecuted(Loop *L) {
150 using namespace PatternMatch;
151
152 auto *Preheader = L->getLoopPreheader();
153 // TODO: We can relax this constraint, since we just need a loop
154 // predecessor.
155 assert(Preheader && "Needs preheader!");
156
157 if (Preheader->isEntryBlock())
158 return false;
159 // All predecessors of the preheader should have a constant conditional
160 // branch, with the loop's preheader as not-taken.
161 for (auto *Pred: predecessors(Preheader)) {
162 BasicBlock *Taken, *NotTaken;
164 if (!match(Pred->getTerminator(),
165 m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
166 return false;
167 if (!Cond->getZExtValue())
168 std::swap(Taken, NotTaken);
169 if (Taken == Preheader)
170 return false;
171 }
172 assert(!pred_empty(Preheader) &&
173 "Preheader should have predecessors at this point!");
174 // All the predecessors have the loop preheader as not-taken target.
175 return true;
176}
177
178static Value *
180 const SimplifyQuery &SQ) {
181 // Quick hack: do not flood cache with non-instruction values.
182 if (!isa<Instruction>(V))
183 return V;
184 // Do we already know cached result?
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)) {
190 Value *LHS =
191 getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
192 Value *RHS =
193 getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
194 FirstIterV = simplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
195 } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
196 Value *LHS =
197 getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
198 Value *RHS =
199 getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
200 FirstIterV = simplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
201 } else if (auto *Select = dyn_cast<SelectInst>(V)) {
202 Value *Cond =
203 getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
204 if (auto *C = dyn_cast<ConstantInt>(Cond)) {
205 auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
206 : Select->getFalseValue();
207 FirstIterV = getValueOnFirstIteration(Selected, FirstIterValue, SQ);
208 }
209 }
210 if (!FirstIterV)
211 FirstIterV = V;
212 FirstIterValue[V] = FirstIterV;
213 return FirstIterV;
214}
215
216// Try to prove that one of conditions that dominates the latch must exit on 1st
217// iteration.
219 LoopInfo &LI) {
220 // Disabled by option.
222 return false;
223
224 BasicBlock *Predecessor = L->getLoopPredecessor();
225 BasicBlock *Latch = L->getLoopLatch();
226
227 if (!Predecessor || !Latch)
228 return false;
229
230 LoopBlocksRPO RPOT(L);
231 RPOT.perform(&LI);
232
233 // For the optimization to be correct, we need RPOT to have a property that
234 // each block is processed after all its predecessors, which may only be
235 // violated for headers of the current loop and all nested loops. Irreducible
236 // CFG provides multiple ways to break this assumption, so we do not want to
237 // deal with it.
238 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
239 return false;
240
241 BasicBlock *Header = L->getHeader();
242 // Blocks that are reachable on the 1st iteration.
244 // Edges that are reachable on the 1st iteration.
245 DenseSet<BasicBlockEdge> LiveEdges;
246 LiveBlocks.insert(Header);
247
249 auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
250 assert(LiveBlocks.count(From) && "Must be live!");
251 assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
252 "Only canonical backedges are allowed. Irreducible CFG?");
253 assert((LiveBlocks.count(To) || !Visited.count(To)) &&
254 "We already discarded this block as dead!");
255 LiveBlocks.insert(To);
256 LiveEdges.insert({ From, To });
257 };
258
259 auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
260 for (auto *Succ : successors(BB))
261 MarkLiveEdge(BB, Succ);
262 };
263
264 // Check if there is only one value coming from all live predecessor blocks.
265 // Note that because we iterate in RPOT, we have already visited all its
266 // (non-latch) predecessors.
267 auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
268 BasicBlock *BB = PN.getParent();
269 bool HasLivePreds = false;
270 (void)HasLivePreds;
271 if (BB == Header)
272 return PN.getIncomingValueForBlock(Predecessor);
273 Value *OnlyInput = nullptr;
274 for (auto *Pred : predecessors(BB))
275 if (LiveEdges.count({ Pred, BB })) {
276 HasLivePreds = true;
277 Value *Incoming = PN.getIncomingValueForBlock(Pred);
278 // Skip undefs. If they are present, we can assume they are equal to
279 // the non-undef input.
280 if (isa<UndefValue>(Incoming))
281 continue;
282 // Two inputs.
283 if (OnlyInput && OnlyInput != Incoming)
284 return nullptr;
285 OnlyInput = Incoming;
286 }
287
288 assert(HasLivePreds && "No live predecessors?");
289 // If all incoming live value were undefs, return undef.
290 return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
291 };
292 DenseMap<Value *, Value *> FirstIterValue;
293
294 // Use the following algorithm to prove we never take the latch on the 1st
295 // iteration:
296 // 1. Traverse in topological order, so that whenever we visit a block, all
297 // its predecessors are already visited.
298 // 2. If we can prove that the block may have only 1 predecessor on the 1st
299 // iteration, map all its phis onto input from this predecessor.
300 // 3a. If we can prove which successor of out block is taken on the 1st
301 // iteration, mark this successor live.
302 // 3b. If we cannot prove it, conservatively assume that all successors are
303 // live.
304 auto &DL = Header->getModule()->getDataLayout();
305 const SimplifyQuery SQ(DL);
306 for (auto *BB : RPOT) {
307 Visited.insert(BB);
308
309 // This block is not reachable on the 1st iterations.
310 if (!LiveBlocks.count(BB))
311 continue;
312
313 // Skip inner loops.
314 if (LI.getLoopFor(BB) != L) {
315 MarkAllSuccessorsLive(BB);
316 continue;
317 }
318
319 // If Phi has only one input from all live input blocks, use it.
320 for (auto &PN : BB->phis()) {
321 if (!PN.getType()->isIntegerTy())
322 continue;
323 auto *Incoming = GetSoleInputOnFirstIteration(PN);
324 if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
325 Value *FirstIterV =
326 getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
327 FirstIterValue[&PN] = FirstIterV;
328 }
329 }
330
331 using namespace PatternMatch;
332 Value *Cond;
333 BasicBlock *IfTrue, *IfFalse;
334 auto *Term = BB->getTerminator();
335 if (match(Term, m_Br(m_Value(Cond),
336 m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
337 auto *ICmp = dyn_cast<ICmpInst>(Cond);
338 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
339 MarkAllSuccessorsLive(BB);
340 continue;
341 }
342
343 // Can we prove constant true or false for this condition?
344 auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
345 if (KnownCondition == ICmp) {
346 // Failed to simplify.
347 MarkAllSuccessorsLive(BB);
348 continue;
349 }
350 if (isa<UndefValue>(KnownCondition)) {
351 // TODO: According to langref, branching by undef is undefined behavior.
352 // It means that, theoretically, we should be able to just continue
353 // without marking any successors as live. However, we are not certain
354 // how correct our compiler is at handling such cases. So we are being
355 // very conservative here.
356 //
357 // If there is a non-loop successor, always assume this branch leaves the
358 // loop. Otherwise, arbitrarily take IfTrue.
359 //
360 // Once we are certain that branching by undef is handled correctly by
361 // other transforms, we should not mark any successors live here.
362 if (L->contains(IfTrue) && L->contains(IfFalse))
363 MarkLiveEdge(BB, IfTrue);
364 continue;
365 }
366 auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
367 if (!ConstCondition) {
368 // Non-constant condition, cannot analyze any further.
369 MarkAllSuccessorsLive(BB);
370 continue;
371 }
372 if (ConstCondition->isAllOnesValue())
373 MarkLiveEdge(BB, IfTrue);
374 else
375 MarkLiveEdge(BB, IfFalse);
376 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
377 auto *SwitchValue = SI->getCondition();
378 auto *SwitchValueOnFirstIter =
379 getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
380 auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
381 if (!ConstSwitchValue) {
382 MarkAllSuccessorsLive(BB);
383 continue;
384 }
385 auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
386 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
387 } else {
388 MarkAllSuccessorsLive(BB);
389 continue;
390 }
391 }
392
393 // We can break the latch if it wasn't live.
394 return !LiveEdges.count({ Latch, Header });
395}
396
397/// If we can prove the backedge is untaken, remove it. This destroys the
398/// loop, but leaves the (now trivially loop invariant) control flow and
399/// side effects (if any) in place.
402 LoopInfo &LI, MemorySSA *MSSA,
404 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
405
406 if (!L->getLoopLatch())
408
409 auto *BTCMax = SE.getConstantMaxBackedgeTakenCount(L);
410 if (!BTCMax->isZero()) {
411 auto *BTC = SE.getBackedgeTakenCount(L);
412 if (!BTC->isZero()) {
413 if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC))
415 if (!canProveExitOnFirstIteration(L, DT, LI))
417 }
418 }
419 ++NumBackedgesBroken;
420 breakLoopBackedge(L, DT, SE, LI, MSSA);
422}
423
424/// Remove a loop if it is dead.
425///
426/// A loop is considered dead either if it does not impact the observable
427/// behavior of the program other than finite running time, or if it is
428/// required to make progress by an attribute such as 'mustprogress' or
429/// 'llvm.loop.mustprogress' and does not make any. This may remove
430/// infinite loops that have been required to make progress.
431///
432/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
433/// order to make various safety checks work.
434///
435/// \returns true if any changes were made. This may mutate the loop even if it
436/// is unable to delete it due to hoisting trivially loop invariant
437/// instructions out of the loop.
439 ScalarEvolution &SE, LoopInfo &LI,
440 MemorySSA *MSSA,
442 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
443
444 // We can only remove the loop if there is a preheader that we can branch from
445 // after removing it. Also, if LoopSimplify form is not available, stay out
446 // of trouble.
447 BasicBlock *Preheader = L->getLoopPreheader();
448 if (!Preheader || !L->hasDedicatedExits()) {
450 dbgs()
451 << "Deletion requires Loop with preheader and dedicated exits.\n");
453 }
454
455 BasicBlock *ExitBlock = L->getUniqueExitBlock();
456
457 if (ExitBlock && isLoopNeverExecuted(L)) {
458 LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!\n");
459 // We need to forget the loop before setting the incoming values of the exit
460 // phis to poison, so we properly invalidate the SCEV expressions for those
461 // phis.
462 SE.forgetLoop(L);
463 // Set incoming value to poison for phi nodes in the exit block.
464 for (PHINode &P : ExitBlock->phis()) {
465 std::fill(P.incoming_values().begin(), P.incoming_values().end(),
466 PoisonValue::get(P.getType()));
467 }
468 ORE.emit([&]() {
469 return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
470 L->getHeader())
471 << "Loop deleted because it never executes";
472 });
473 deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
474 ++NumDeleted;
476 }
477
478 // The remaining checks below are for a loop being dead because all statements
479 // in the loop are invariant.
480 SmallVector<BasicBlock *, 4> ExitingBlocks;
481 L->getExitingBlocks(ExitingBlocks);
482
483 // We require that the loop has at most one exit block. Otherwise, we'd be in
484 // the situation of needing to be able to solve statically which exit block
485 // will be branched to, or trying to preserve the branching logic in a loop
486 // invariant manner.
487 if (!ExitBlock && !L->hasNoExitBlocks()) {
488 LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
490 }
491 // Finally, we have to check that the loop really is dead.
492 bool Changed = false;
493 if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
494 LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
495 return Changed ? LoopDeletionResult::Modified
497 }
498
499 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!\n");
500 ORE.emit([&]() {
501 return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
502 L->getHeader())
503 << "Loop deleted because it is invariant";
504 });
505 deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
506 ++NumDeleted;
507
509}
510
513 LPMUpdater &Updater) {
514
515 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
516 LLVM_DEBUG(L.dump());
517 std::string LoopName = std::string(L.getName());
518 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
519 // pass. Function analyses need to be preserved across loop transformations
520 // but ORE cannot be preserved (see comment before the pass definition).
521 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
522 auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
523
524 // If we can prove the backedge isn't taken, just break it and be done. This
525 // leaves the loop structure in place which means it can handle dispatching
526 // to the right exit based on whatever loop invariant structure remains.
527 if (Result != LoopDeletionResult::Deleted)
528 Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
529 AR.MSSA, ORE));
530
531 if (Result == LoopDeletionResult::Unmodified)
532 return PreservedAnalyses::all();
533
534 if (Result == LoopDeletionResult::Deleted)
535 Updater.markLoopAsDeleted(L, LoopName);
536
538 if (AR.MSSA)
539 PA.preserve<MemorySSAAnalysis>();
540 return PA;
541}
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")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
LoopDeletionResult
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"))
#define DEBUG_TYPE
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.
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define P(N)
@ SI
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)
Definition: Statistic.h:167
Value * RHS
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:381
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
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...
Definition: BasicBlock.h:127
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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.
iterator end() const
Definition: LoopInfo.h:172
iterator begin() const
Definition: LoopInfo.h:171
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
The optimization diagnostic interface.
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for applied optimization remarks.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
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.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Multiway switch.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
LLVM Value Representation.
Definition: Value.h:74
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
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.
Definition: PatternMatch.h:76
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:168
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
auto successors(const MachineBasicBlock *BB)
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Definition: LoopInfo.cpp:1114
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1826
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:482
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:699
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)
Definition: CFG.h:118
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...