Bug Summary

File:include/llvm/Analysis/LoopInfo.h
Warning:line 474, column 57
Moved-from object 'Start' is moved

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopInfo.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn350071/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn350071=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-27-042839-1215-1 -x c++ /build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp

1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the LoopInfo class that is used to identify natural loops
11// and determine the loop depth of various nodes of the CFG. Note that the
12// loops identified may actually be several natural loops that share the same
13// header node... not just a single natural loop.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/ADT/DepthFirstIterator.h"
19#include "llvm/ADT/ScopeExit.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/Analysis/LoopInfoImpl.h"
22#include "llvm/Analysis/LoopIterator.h"
23#include "llvm/Analysis/ValueTracking.h"
24#include "llvm/Config/llvm-config.h"
25#include "llvm/IR/CFG.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DebugLoc.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/IRPrintingPasses.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/LLVMContext.h"
32#include "llvm/IR/Metadata.h"
33#include "llvm/IR/PassManager.h"
34#include "llvm/Support/CommandLine.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/raw_ostream.h"
37#include <algorithm>
38using namespace llvm;
39
40// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
41template class llvm::LoopBase<BasicBlock, Loop>;
42template class llvm::LoopInfoBase<BasicBlock, Loop>;
43
44// Always verify loopinfo if expensive checking is enabled.
45#ifdef EXPENSIVE_CHECKS
46bool llvm::VerifyLoopInfo = true;
47#else
48bool llvm::VerifyLoopInfo = false;
49#endif
50static cl::opt<bool, true>
51 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
52 cl::Hidden, cl::desc("Verify loop info (time consuming)"));
53
54//===----------------------------------------------------------------------===//
55// Loop implementation
56//
57
58bool Loop::isLoopInvariant(const Value *V) const {
59 if (const Instruction *I = dyn_cast<Instruction>(V))
60 return !contains(I);
61 return true; // All non-instructions are loop invariant
62}
63
64bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
65 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
66}
67
68bool Loop::makeLoopInvariant(Value *V, bool &Changed,
69 Instruction *InsertPt) const {
70 if (Instruction *I = dyn_cast<Instruction>(V))
71 return makeLoopInvariant(I, Changed, InsertPt);
72 return true; // All non-instructions are loop-invariant.
73}
74
75bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
76 Instruction *InsertPt) const {
77 // Test if the value is already loop-invariant.
78 if (isLoopInvariant(I))
79 return true;
80 if (!isSafeToSpeculativelyExecute(I))
81 return false;
82 if (I->mayReadFromMemory())
83 return false;
84 // EH block instructions are immobile.
85 if (I->isEHPad())
86 return false;
87 // Determine the insertion point, unless one was given.
88 if (!InsertPt) {
89 BasicBlock *Preheader = getLoopPreheader();
90 // Without a preheader, hoisting is not feasible.
91 if (!Preheader)
92 return false;
93 InsertPt = Preheader->getTerminator();
94 }
95 // Don't hoist instructions with loop-variant operands.
96 for (Value *Operand : I->operands())
97 if (!makeLoopInvariant(Operand, Changed, InsertPt))
98 return false;
99
100 // Hoist.
101 I->moveBefore(InsertPt);
102
103 // There is possibility of hoisting this instruction above some arbitrary
104 // condition. Any metadata defined on it can be control dependent on this
105 // condition. Conservatively strip it here so that we don't give any wrong
106 // information to the optimizer.
107 I->dropUnknownNonDebugMetadata();
108
109 Changed = true;
110 return true;
111}
112
113PHINode *Loop::getCanonicalInductionVariable() const {
114 BasicBlock *H = getHeader();
115
116 BasicBlock *Incoming = nullptr, *Backedge = nullptr;
117 pred_iterator PI = pred_begin(H);
118 assert(PI != pred_end(H) && "Loop must have at least one backedge!")((PI != pred_end(H) && "Loop must have at least one backedge!"
) ? static_cast<void> (0) : __assert_fail ("PI != pred_end(H) && \"Loop must have at least one backedge!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 118, __PRETTY_FUNCTION__))
;
119 Backedge = *PI++;
120 if (PI == pred_end(H))
121 return nullptr; // dead loop
122 Incoming = *PI++;
123 if (PI != pred_end(H))
124 return nullptr; // multiple backedges?
125
126 if (contains(Incoming)) {
127 if (contains(Backedge))
128 return nullptr;
129 std::swap(Incoming, Backedge);
130 } else if (!contains(Backedge))
131 return nullptr;
132
133 // Loop over all of the PHI nodes, looking for a canonical indvar.
134 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
135 PHINode *PN = cast<PHINode>(I);
136 if (ConstantInt *CI =
137 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
138 if (CI->isZero())
139 if (Instruction *Inc =
140 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
141 if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
142 if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
143 if (CI->isOne())
144 return PN;
145 }
146 return nullptr;
147}
148
149// Check that 'BB' doesn't have any uses outside of the 'L'
150static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
151 DominatorTree &DT) {
152 for (const Instruction &I : BB) {
153 // Tokens can't be used in PHI nodes and live-out tokens prevent loop
154 // optimizations, so for the purposes of considered LCSSA form, we
155 // can ignore them.
156 if (I.getType()->isTokenTy())
157 continue;
158
159 for (const Use &U : I.uses()) {
160 const Instruction *UI = cast<Instruction>(U.getUser());
161 const BasicBlock *UserBB = UI->getParent();
162 if (const PHINode *P = dyn_cast<PHINode>(UI))
163 UserBB = P->getIncomingBlock(U);
164
165 // Check the current block, as a fast-path, before checking whether
166 // the use is anywhere in the loop. Most values are used in the same
167 // block they are defined in. Also, blocks not reachable from the
168 // entry are special; uses in them don't need to go through PHIs.
169 if (UserBB != &BB && !L.contains(UserBB) &&
170 DT.isReachableFromEntry(UserBB))
171 return false;
172 }
173 }
174 return true;
175}
176
177bool Loop::isLCSSAForm(DominatorTree &DT) const {
178 // For each block we check that it doesn't have any uses outside of this loop.
179 return all_of(this->blocks(), [&](const BasicBlock *BB) {
180 return isBlockInLCSSAForm(*this, *BB, DT);
181 });
182}
183
184bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
185 // For each block we check that it doesn't have any uses outside of its
186 // innermost loop. This process will transitively guarantee that the current
187 // loop and all of the nested loops are in LCSSA form.
188 return all_of(this->blocks(), [&](const BasicBlock *BB) {
189 return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
190 });
191}
192
193bool Loop::isLoopSimplifyForm() const {
194 // Normal-form loops have a preheader, a single backedge, and all of their
195 // exits have all their predecessors inside the loop.
196 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
197}
198
199// Routines that reform the loop CFG and split edges often fail on indirectbr.
200bool Loop::isSafeToClone() const {
201 // Return false if any loop blocks contain indirectbrs, or there are any calls
202 // to noduplicate functions.
203 for (BasicBlock *BB : this->blocks()) {
204 if (isa<IndirectBrInst>(BB->getTerminator()))
205 return false;
206
207 for (Instruction &I : *BB)
208 if (auto CS = CallSite(&I))
209 if (CS.cannotDuplicate())
210 return false;
211 }
212 return true;
213}
214
215MDNode *Loop::getLoopID() const {
216 MDNode *LoopID = nullptr;
217
218 // Go through the latch blocks and check the terminator for the metadata.
219 SmallVector<BasicBlock *, 4> LatchesBlocks;
220 getLoopLatches(LatchesBlocks);
221 for (BasicBlock *BB : LatchesBlocks) {
222 Instruction *TI = BB->getTerminator();
223 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
224
225 if (!MD)
226 return nullptr;
227
228 if (!LoopID)
229 LoopID = MD;
230 else if (MD != LoopID)
231 return nullptr;
232 }
233 if (!LoopID || LoopID->getNumOperands() == 0 ||
234 LoopID->getOperand(0) != LoopID)
235 return nullptr;
236 return LoopID;
237}
238
239void Loop::setLoopID(MDNode *LoopID) const {
240 assert((!LoopID || LoopID->getNumOperands() > 0) &&(((!LoopID || LoopID->getNumOperands() > 0) && "Loop ID needs at least one operand"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getNumOperands() > 0) && \"Loop ID needs at least one operand\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 241, __PRETTY_FUNCTION__))
241 "Loop ID needs at least one operand")(((!LoopID || LoopID->getNumOperands() > 0) && "Loop ID needs at least one operand"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getNumOperands() > 0) && \"Loop ID needs at least one operand\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 241, __PRETTY_FUNCTION__))
;
242 assert((!LoopID || LoopID->getOperand(0) == LoopID) &&(((!LoopID || LoopID->getOperand(0) == LoopID) && "Loop ID should refer to itself"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getOperand(0) == LoopID) && \"Loop ID should refer to itself\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 243, __PRETTY_FUNCTION__))
243 "Loop ID should refer to itself")(((!LoopID || LoopID->getOperand(0) == LoopID) && "Loop ID should refer to itself"
) ? static_cast<void> (0) : __assert_fail ("(!LoopID || LoopID->getOperand(0) == LoopID) && \"Loop ID should refer to itself\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 243, __PRETTY_FUNCTION__))
;
244
245 BasicBlock *H = getHeader();
246 for (BasicBlock *BB : this->blocks()) {
247 Instruction *TI = BB->getTerminator();
248 for (BasicBlock *Successor : successors(TI)) {
249 if (Successor == H) {
250 TI->setMetadata(LLVMContext::MD_loop, LoopID);
251 break;
252 }
253 }
254 }
255}
256
257void Loop::setLoopAlreadyUnrolled() {
258 MDNode *LoopID = getLoopID();
259 // First remove any existing loop unrolling metadata.
260 SmallVector<Metadata *, 4> MDs;
261 // Reserve first location for self reference to the LoopID metadata node.
262 MDs.push_back(nullptr);
263
264 if (LoopID) {
265 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
266 bool IsUnrollMetadata = false;
267 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
268 if (MD) {
269 const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
270 IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
271 }
272 if (!IsUnrollMetadata)
273 MDs.push_back(LoopID->getOperand(i));
274 }
275 }
276
277 // Add unroll(disable) metadata to disable future unrolling.
278 LLVMContext &Context = getHeader()->getContext();
279 SmallVector<Metadata *, 1> DisableOperands;
280 DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
281 MDNode *DisableNode = MDNode::get(Context, DisableOperands);
282 MDs.push_back(DisableNode);
283
284 MDNode *NewLoopID = MDNode::get(Context, MDs);
285 // Set operand 0 to refer to the loop id itself.
286 NewLoopID->replaceOperandWith(0, NewLoopID);
287 setLoopID(NewLoopID);
288}
289
290bool Loop::isAnnotatedParallel() const {
291 MDNode *DesiredLoopIdMetadata = getLoopID();
292
293 if (!DesiredLoopIdMetadata)
294 return false;
295
296 MDNode *ParallelAccesses =
297 findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
298 SmallPtrSet<MDNode *, 4>
299 ParallelAccessGroups; // For scalable 'contains' check.
300 if (ParallelAccesses) {
301 for (const MDOperand &MD : drop_begin(ParallelAccesses->operands(), 1)) {
302 MDNode *AccGroup = cast<MDNode>(MD.get());
303 assert(isValidAsAccessGroup(AccGroup) &&((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 304, __PRETTY_FUNCTION__))
304 "List item must be an access group")((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 304, __PRETTY_FUNCTION__))
;
305 ParallelAccessGroups.insert(AccGroup);
306 }
307 }
308
309 // The loop branch contains the parallel loop metadata. In order to ensure
310 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
311 // dependencies (thus converted the loop back to a sequential loop), check
312 // that all the memory instructions in the loop belong to an access group that
313 // is parallel to this loop.
314 for (BasicBlock *BB : this->blocks()) {
315 for (Instruction &I : *BB) {
316 if (!I.mayReadOrWriteMemory())
317 continue;
318
319 if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
320 auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
321 if (AG->getNumOperands() == 0) {
322 assert(isValidAsAccessGroup(AG) && "Item must be an access group")((isValidAsAccessGroup(AG) && "Item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AG) && \"Item must be an access group\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 322, __PRETTY_FUNCTION__))
;
323 return ParallelAccessGroups.count(AG);
324 }
325
326 for (const MDOperand &AccessListItem : AG->operands()) {
327 MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
328 assert(isValidAsAccessGroup(AccGroup) &&((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 329, __PRETTY_FUNCTION__))
329 "List item must be an access group")((isValidAsAccessGroup(AccGroup) && "List item must be an access group"
) ? static_cast<void> (0) : __assert_fail ("isValidAsAccessGroup(AccGroup) && \"List item must be an access group\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 329, __PRETTY_FUNCTION__))
;
330 if (ParallelAccessGroups.count(AccGroup))
331 return true;
332 }
333 return false;
334 };
335
336 if (ContainsAccessGroup(AccessGroup))
337 continue;
338 }
339
340 // The memory instruction can refer to the loop identifier metadata
341 // directly or indirectly through another list metadata (in case of
342 // nested parallel loops). The loop identifier metadata refers to
343 // itself so we can check both cases with the same routine.
344 MDNode *LoopIdMD =
345 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
346
347 if (!LoopIdMD)
348 return false;
349
350 bool LoopIdMDFound = false;
351 for (const MDOperand &MDOp : LoopIdMD->operands()) {
352 if (MDOp == DesiredLoopIdMetadata) {
353 LoopIdMDFound = true;
354 break;
355 }
356 }
357
358 if (!LoopIdMDFound)
359 return false;
360 }
361 }
362 return true;
363}
364
365DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
1
Calling 'Loop::getLocRange'
366
367Loop::LocRange Loop::getLocRange() const {
368 // If we have a debug location in the loop ID, then use it.
369 if (MDNode *LoopID = getLoopID()) {
2
Assuming 'LoopID' is null
3
Taking false branch
370 DebugLoc Start;
371 // We use the first DebugLoc in the header as the start location of the loop
372 // and if there is a second DebugLoc in the header we use it as end location
373 // of the loop.
374 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
375 if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
376 if (!Start)
377 Start = DebugLoc(L);
378 else
379 return LocRange(Start, DebugLoc(L));
380 }
381 }
382
383 if (Start)
384 return LocRange(Start);
385 }
386
387 // Try the pre-header first.
388 if (BasicBlock *PHeadBB = getLoopPreheader())
4
Assuming 'PHeadBB' is null
5
Taking false branch
389 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
390 return LocRange(DL);
391
392 // If we have no pre-header or there are no instructions with debug
393 // info in it, try the header.
394 if (BasicBlock *HeadBB = getHeader())
6
Assuming 'HeadBB' is non-null
7
Taking true branch
395 return LocRange(HeadBB->getTerminator()->getDebugLoc());
8
Calling constructor for 'LocRange'
396
397 return LocRange();
398}
399
400#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
401LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dump() const { print(dbgs()); }
402
403LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Loop::dumpVerbose() const {
404 print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
405}
406#endif
407
408//===----------------------------------------------------------------------===//
409// UnloopUpdater implementation
410//
411
412namespace {
413/// Find the new parent loop for all blocks within the "unloop" whose last
414/// backedges has just been removed.
415class UnloopUpdater {
416 Loop &Unloop;
417 LoopInfo *LI;
418
419 LoopBlocksDFS DFS;
420
421 // Map unloop's immediate subloops to their nearest reachable parents. Nested
422 // loops within these subloops will not change parents. However, an immediate
423 // subloop's new parent will be the nearest loop reachable from either its own
424 // exits *or* any of its nested loop's exits.
425 DenseMap<Loop *, Loop *> SubloopParents;
426
427 // Flag the presence of an irreducible backedge whose destination is a block
428 // directly contained by the original unloop.
429 bool FoundIB;
430
431public:
432 UnloopUpdater(Loop *UL, LoopInfo *LInfo)
433 : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
434
435 void updateBlockParents();
436
437 void removeBlocksFromAncestors();
438
439 void updateSubloopParents();
440
441protected:
442 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
443};
444} // end anonymous namespace
445
446/// Update the parent loop for all blocks that are directly contained within the
447/// original "unloop".
448void UnloopUpdater::updateBlockParents() {
449 if (Unloop.getNumBlocks()) {
450 // Perform a post order CFG traversal of all blocks within this loop,
451 // propagating the nearest loop from successors to predecessors.
452 LoopBlocksTraversal Traversal(DFS, LI);
453 for (BasicBlock *POI : Traversal) {
454
455 Loop *L = LI->getLoopFor(POI);
456 Loop *NL = getNearestLoop(POI, L);
457
458 if (NL != L) {
459 // For reducible loops, NL is now an ancestor of Unloop.
460 assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&(((NL != &Unloop && (!NL || NL->contains(&
Unloop))) && "uninitialized successor") ? static_cast
<void> (0) : __assert_fail ("(NL != &Unloop && (!NL || NL->contains(&Unloop))) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 461, __PRETTY_FUNCTION__))
461 "uninitialized successor")(((NL != &Unloop && (!NL || NL->contains(&
Unloop))) && "uninitialized successor") ? static_cast
<void> (0) : __assert_fail ("(NL != &Unloop && (!NL || NL->contains(&Unloop))) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 461, __PRETTY_FUNCTION__))
;
462 LI->changeLoopFor(POI, NL);
463 } else {
464 // Or the current block is part of a subloop, in which case its parent
465 // is unchanged.
466 assert((FoundIB || Unloop.contains(L)) && "uninitialized successor")(((FoundIB || Unloop.contains(L)) && "uninitialized successor"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || Unloop.contains(L)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 466, __PRETTY_FUNCTION__))
;
467 }
468 }
469 }
470 // Each irreducible loop within the unloop induces a round of iteration using
471 // the DFS result cached by Traversal.
472 bool Changed = FoundIB;
473 for (unsigned NIters = 0; Changed; ++NIters) {
474 assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm")((NIters < Unloop.getNumBlocks() && "runaway iterative algorithm"
) ? static_cast<void> (0) : __assert_fail ("NIters < Unloop.getNumBlocks() && \"runaway iterative algorithm\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 474, __PRETTY_FUNCTION__))
;
475
476 // Iterate over the postorder list of blocks, propagating the nearest loop
477 // from successors to predecessors as before.
478 Changed = false;
479 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
480 POE = DFS.endPostorder();
481 POI != POE; ++POI) {
482
483 Loop *L = LI->getLoopFor(*POI);
484 Loop *NL = getNearestLoop(*POI, L);
485 if (NL != L) {
486 assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&((NL != &Unloop && (!NL || NL->contains(&Unloop
)) && "uninitialized successor") ? static_cast<void
> (0) : __assert_fail ("NL != &Unloop && (!NL || NL->contains(&Unloop)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 487, __PRETTY_FUNCTION__))
487 "uninitialized successor")((NL != &Unloop && (!NL || NL->contains(&Unloop
)) && "uninitialized successor") ? static_cast<void
> (0) : __assert_fail ("NL != &Unloop && (!NL || NL->contains(&Unloop)) && \"uninitialized successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 487, __PRETTY_FUNCTION__))
;
488 LI->changeLoopFor(*POI, NL);
489 Changed = true;
490 }
491 }
492 }
493}
494
495/// Remove unloop's blocks from all ancestors below their new parents.
496void UnloopUpdater::removeBlocksFromAncestors() {
497 // Remove all unloop's blocks (including those in nested subloops) from
498 // ancestors below the new parent loop.
499 for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
500 BI != BE; ++BI) {
501 Loop *OuterParent = LI->getLoopFor(*BI);
502 if (Unloop.contains(OuterParent)) {
503 while (OuterParent->getParentLoop() != &Unloop)
504 OuterParent = OuterParent->getParentLoop();
505 OuterParent = SubloopParents[OuterParent];
506 }
507 // Remove blocks from former Ancestors except Unloop itself which will be
508 // deleted.
509 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
510 OldParent = OldParent->getParentLoop()) {
511 assert(OldParent && "new loop is not an ancestor of the original")((OldParent && "new loop is not an ancestor of the original"
) ? static_cast<void> (0) : __assert_fail ("OldParent && \"new loop is not an ancestor of the original\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 511, __PRETTY_FUNCTION__))
;
512 OldParent->removeBlockFromLoop(*BI);
513 }
514 }
515}
516
517/// Update the parent loop for all subloops directly nested within unloop.
518void UnloopUpdater::updateSubloopParents() {
519 while (!Unloop.empty()) {
520 Loop *Subloop = *std::prev(Unloop.end());
521 Unloop.removeChildLoop(std::prev(Unloop.end()));
522
523 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop")((SubloopParents.count(Subloop) && "DFS failed to visit subloop"
) ? static_cast<void> (0) : __assert_fail ("SubloopParents.count(Subloop) && \"DFS failed to visit subloop\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 523, __PRETTY_FUNCTION__))
;
524 if (Loop *Parent = SubloopParents[Subloop])
525 Parent->addChildLoop(Subloop);
526 else
527 LI->addTopLevelLoop(Subloop);
528 }
529}
530
531/// Return the nearest parent loop among this block's successors. If a successor
532/// is a subloop header, consider its parent to be the nearest parent of the
533/// subloop's exits.
534///
535/// For subloop blocks, simply update SubloopParents and return NULL.
536Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
537
538 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
539 // is considered uninitialized.
540 Loop *NearLoop = BBLoop;
541
542 Loop *Subloop = nullptr;
543 if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
544 Subloop = NearLoop;
545 // Find the subloop ancestor that is directly contained within Unloop.
546 while (Subloop->getParentLoop() != &Unloop) {
547 Subloop = Subloop->getParentLoop();
548 assert(Subloop && "subloop is not an ancestor of the original loop")((Subloop && "subloop is not an ancestor of the original loop"
) ? static_cast<void> (0) : __assert_fail ("Subloop && \"subloop is not an ancestor of the original loop\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 548, __PRETTY_FUNCTION__))
;
549 }
550 // Get the current nearest parent of the Subloop exits, initially Unloop.
551 NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
552 }
553
554 succ_iterator I = succ_begin(BB), E = succ_end(BB);
555 if (I == E) {
556 assert(!Subloop && "subloop blocks must have a successor")((!Subloop && "subloop blocks must have a successor")
? static_cast<void> (0) : __assert_fail ("!Subloop && \"subloop blocks must have a successor\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 556, __PRETTY_FUNCTION__))
;
557 NearLoop = nullptr; // unloop blocks may now exit the function.
558 }
559 for (; I != E; ++I) {
560 if (*I == BB)
561 continue; // self loops are uninteresting
562
563 Loop *L = LI->getLoopFor(*I);
564 if (L == &Unloop) {
565 // This successor has not been processed. This path must lead to an
566 // irreducible backedge.
567 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB")(((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB"
) ? static_cast<void> (0) : __assert_fail ("(FoundIB || !DFS.hasPostorder(*I)) && \"should have seen IB\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 567, __PRETTY_FUNCTION__))
;
568 FoundIB = true;
569 }
570 if (L != &Unloop && Unloop.contains(L)) {
571 // Successor is in a subloop.
572 if (Subloop)
573 continue; // Branching within subloops. Ignore it.
574
575 // BB branches from the original into a subloop header.
576 assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops")((L->getParentLoop() == &Unloop && "cannot skip into nested loops"
) ? static_cast<void> (0) : __assert_fail ("L->getParentLoop() == &Unloop && \"cannot skip into nested loops\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 576, __PRETTY_FUNCTION__))
;
577
578 // Get the current nearest parent of the Subloop's exits.
579 L = SubloopParents[L];
580 // L could be Unloop if the only exit was an irreducible backedge.
581 }
582 if (L == &Unloop) {
583 continue;
584 }
585 // Handle critical edges from Unloop into a sibling loop.
586 if (L && !L->contains(&Unloop)) {
587 L = L->getParentLoop();
588 }
589 // Remember the nearest parent loop among successors or subloop exits.
590 if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
591 NearLoop = L;
592 }
593 if (Subloop) {
594 SubloopParents[Subloop] = NearLoop;
595 return BBLoop;
596 }
597 return NearLoop;
598}
599
600LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
601
602bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
603 FunctionAnalysisManager::Invalidator &) {
604 // Check whether the analysis, all analyses on functions, or the function's
605 // CFG have been preserved.
606 auto PAC = PA.getChecker<LoopAnalysis>();
607 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
608 PAC.preservedSet<CFGAnalyses>());
609}
610
611void LoopInfo::erase(Loop *Unloop) {
612 assert(!Unloop->isInvalid() && "Loop has already been erased!")((!Unloop->isInvalid() && "Loop has already been erased!"
) ? static_cast<void> (0) : __assert_fail ("!Unloop->isInvalid() && \"Loop has already been erased!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 612, __PRETTY_FUNCTION__))
;
613
614 auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
615
616 // First handle the special case of no parent loop to simplify the algorithm.
617 if (!Unloop->getParentLoop()) {
618 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
619 for (Loop::block_iterator I = Unloop->block_begin(),
620 E = Unloop->block_end();
621 I != E; ++I) {
622
623 // Don't reparent blocks in subloops.
624 if (getLoopFor(*I) != Unloop)
625 continue;
626
627 // Blocks no longer have a parent but are still referenced by Unloop until
628 // the Unloop object is deleted.
629 changeLoopFor(*I, nullptr);
630 }
631
632 // Remove the loop from the top-level LoopInfo object.
633 for (iterator I = begin();; ++I) {
634 assert(I != end() && "Couldn't find loop")((I != end() && "Couldn't find loop") ? static_cast<
void> (0) : __assert_fail ("I != end() && \"Couldn't find loop\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 634, __PRETTY_FUNCTION__))
;
635 if (*I == Unloop) {
636 removeLoop(I);
637 break;
638 }
639 }
640
641 // Move all of the subloops to the top-level.
642 while (!Unloop->empty())
643 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
644
645 return;
646 }
647
648 // Update the parent loop for all blocks within the loop. Blocks within
649 // subloops will not change parents.
650 UnloopUpdater Updater(Unloop, this);
651 Updater.updateBlockParents();
652
653 // Remove blocks from former ancestor loops.
654 Updater.removeBlocksFromAncestors();
655
656 // Add direct subloops as children in their new parent loop.
657 Updater.updateSubloopParents();
658
659 // Remove unloop from its parent loop.
660 Loop *ParentLoop = Unloop->getParentLoop();
661 for (Loop::iterator I = ParentLoop->begin();; ++I) {
662 assert(I != ParentLoop->end() && "Couldn't find loop")((I != ParentLoop->end() && "Couldn't find loop") ?
static_cast<void> (0) : __assert_fail ("I != ParentLoop->end() && \"Couldn't find loop\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 662, __PRETTY_FUNCTION__))
;
663 if (*I == Unloop) {
664 ParentLoop->removeChildLoop(I);
665 break;
666 }
667 }
668}
669
670AnalysisKey LoopAnalysis::Key;
671
672LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
673 // FIXME: Currently we create a LoopInfo from scratch for every function.
674 // This may prove to be too wasteful due to deallocating and re-allocating
675 // memory each time for the underlying map and vector datastructures. At some
676 // point it may prove worthwhile to use a freelist and recycle LoopInfo
677 // objects. I don't want to add that kind of complexity until the scope of
678 // the problem is better understood.
679 LoopInfo LI;
680 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
681 return LI;
682}
683
684PreservedAnalyses LoopPrinterPass::run(Function &F,
685 FunctionAnalysisManager &AM) {
686 AM.getResult<LoopAnalysis>(F).print(OS);
687 return PreservedAnalyses::all();
688}
689
690void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
691
692 if (forcePrintModuleIR()) {
693 // handling -print-module-scope
694 OS << Banner << " (loop: ";
695 L.getHeader()->printAsOperand(OS, false);
696 OS << ")\n";
697
698 // printing whole module
699 OS << *L.getHeader()->getModule();
700 return;
701 }
702
703 OS << Banner;
704
705 auto *PreHeader = L.getLoopPreheader();
706 if (PreHeader) {
707 OS << "\n; Preheader:";
708 PreHeader->print(OS);
709 OS << "\n; Loop:";
710 }
711
712 for (auto *Block : L.blocks())
713 if (Block)
714 Block->print(OS);
715 else
716 OS << "Printing <null> block";
717
718 SmallVector<BasicBlock *, 8> ExitBlocks;
719 L.getExitBlocks(ExitBlocks);
720 if (!ExitBlocks.empty()) {
721 OS << "\n; Exit blocks";
722 for (auto *Block : ExitBlocks)
723 if (Block)
724 Block->print(OS);
725 else
726 OS << "Printing <null> block";
727 }
728}
729
730MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
731 // No loop metadata node, no loop properties.
732 if (!LoopID)
733 return nullptr;
734
735 // First operand should refer to the metadata node itself, for legacy reasons.
736 assert(LoopID->getNumOperands() > 0 && "requires at least one operand")((LoopID->getNumOperands() > 0 && "requires at least one operand"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getNumOperands() > 0 && \"requires at least one operand\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 736, __PRETTY_FUNCTION__))
;
737 assert(LoopID->getOperand(0) == LoopID && "invalid loop id")((LoopID->getOperand(0) == LoopID && "invalid loop id"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getOperand(0) == LoopID && \"invalid loop id\""
, "/build/llvm-toolchain-snapshot-8~svn350071/lib/Analysis/LoopInfo.cpp"
, 737, __PRETTY_FUNCTION__))
;
738
739 // Iterate over the metdata node operands and look for MDString metadata.
740 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
741 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
742 if (!MD || MD->getNumOperands() < 1)
743 continue;
744 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
745 if (!S)
746 continue;
747 // Return the operand node if MDString holds expected metadata.
748 if (Name.equals(S->getString()))
749 return MD;
750 }
751
752 // Loop property not found.
753 return nullptr;
754}
755
756MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
757 return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
758}
759
760bool llvm::isValidAsAccessGroup(MDNode *Node) {
761 return Node->getNumOperands() == 0 && Node->isDistinct();
762}
763
764//===----------------------------------------------------------------------===//
765// LoopInfo implementation
766//
767
768char LoopInfoWrapperPass::ID = 0;
769INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
770 true, true)static void *initializeLoopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
771INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
772INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
}
773 true, true)PassInfo *PI = new PassInfo( "Natural Loop Information", "loops"
, &LoopInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopInfoWrapperPass>), true, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopInfoWrapperPassPassFlag
; void llvm::initializeLoopInfoWrapperPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeLoopInfoWrapperPassPassFlag
, initializeLoopInfoWrapperPassPassOnce, std::ref(Registry));
}
774
775bool LoopInfoWrapperPass::runOnFunction(Function &) {
776 releaseMemory();
777 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
778 return false;
779}
780
781void LoopInfoWrapperPass::verifyAnalysis() const {
782 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
783 // function each time verifyAnalysis is called is very expensive. The
784 // -verify-loop-info option can enable this. In order to perform some
785 // checking by default, LoopPass has been taught to call verifyLoop manually
786 // during loop pass sequences.
787 if (VerifyLoopInfo) {
788 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
789 LI.verify(DT);
790 }
791}
792
793void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
794 AU.setPreservesAll();
795 AU.addRequired<DominatorTreeWrapperPass>();
796}
797
798void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
799 LI.print(OS);
800}
801
802PreservedAnalyses LoopVerifierPass::run(Function &F,
803 FunctionAnalysisManager &AM) {
804 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
805 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
806 LI.verify(DT);
807 return PreservedAnalyses::all();
808}
809
810//===----------------------------------------------------------------------===//
811// LoopBlocksDFS implementation
812//
813
814/// Traverse the loop blocks and store the DFS result.
815/// Useful for clients that just want the final DFS result and don't need to
816/// visit blocks during the initial traversal.
817void LoopBlocksDFS::perform(LoopInfo *LI) {
818 LoopBlocksTraversal Traversal(*this, LI);
819 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
820 POE = Traversal.end();
821 POI != POE; ++POI)
822 ;
823}

/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h

1//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the LoopInfo class that is used to identify natural loops
11// and determine the loop depth of various nodes of the CFG. A natural loop
12// has exactly one entry-point, which is called the header. Note that natural
13// loops may actually be several loops that share the same header node.
14//
15// This analysis calculates the nesting structure of loops in a function. For
16// each natural loop identified, this analysis identifies natural loops
17// contained entirely within the loop and the basic blocks the make up the loop.
18//
19// It can calculate on the fly various bits of information, for example:
20//
21// * whether there is a preheader for the loop
22// * the number of back edges to the header
23// * whether or not a particular block branches out of the loop
24// * the successor blocks of the loop
25// * the loop depth
26// * etc...
27//
28// Note that this analysis specifically identifies *Loops* not cycles or SCCs
29// in the CFG. There can be strongly connected components in the CFG which
30// this analysis will not recognize and that will not be represented by a Loop
31// instance. In particular, a Loop might be inside such a non-loop SCC, or a
32// non-loop SCC might contain a sub-SCC which is a Loop.
33//
34//===----------------------------------------------------------------------===//
35
36#ifndef LLVM_ANALYSIS_LOOPINFO_H
37#define LLVM_ANALYSIS_LOOPINFO_H
38
39#include "llvm/ADT/DenseMap.h"
40#include "llvm/ADT/DenseSet.h"
41#include "llvm/ADT/GraphTraits.h"
42#include "llvm/ADT/SmallPtrSet.h"
43#include "llvm/ADT/SmallVector.h"
44#include "llvm/IR/CFG.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/PassManager.h"
48#include "llvm/Pass.h"
49#include "llvm/Support/Allocator.h"
50#include <algorithm>
51#include <utility>
52
53namespace llvm {
54
55class DominatorTree;
56class LoopInfo;
57class Loop;
58class MDNode;
59class PHINode;
60class raw_ostream;
61template <class N, bool IsPostDom> class DominatorTreeBase;
62template <class N, class M> class LoopInfoBase;
63template <class N, class M> class LoopBase;
64
65//===----------------------------------------------------------------------===//
66/// Instances of this class are used to represent loops that are detected in the
67/// flow graph.
68///
69template <class BlockT, class LoopT> class LoopBase {
70 LoopT *ParentLoop;
71 // Loops contained entirely within this one.
72 std::vector<LoopT *> SubLoops;
73
74 // The list of blocks in this loop. First entry is the header node.
75 std::vector<BlockT *> Blocks;
76
77 SmallPtrSet<const BlockT *, 8> DenseBlockSet;
78
79#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
80 /// Indicator that this loop is no longer a valid loop.
81 bool IsInvalid = false;
82#endif
83
84 LoopBase(const LoopBase<BlockT, LoopT> &) = delete;
85 const LoopBase<BlockT, LoopT> &
86 operator=(const LoopBase<BlockT, LoopT> &) = delete;
87
88public:
89 /// Return the nesting level of this loop. An outer-most loop has depth 1,
90 /// for consistency with loop depth values used for basic blocks, where depth
91 /// 0 is used for blocks not inside any loops.
92 unsigned getLoopDepth() const {
93 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 93, __PRETTY_FUNCTION__))
;
94 unsigned D = 1;
95 for (const LoopT *CurLoop = ParentLoop; CurLoop;
96 CurLoop = CurLoop->ParentLoop)
97 ++D;
98 return D;
99 }
100 BlockT *getHeader() const { return getBlocks().front(); }
101 LoopT *getParentLoop() const { return ParentLoop; }
102
103 /// This is a raw interface for bypassing addChildLoop.
104 void setParentLoop(LoopT *L) {
105 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 105, __PRETTY_FUNCTION__))
;
106 ParentLoop = L;
107 }
108
109 /// Return true if the specified loop is contained within in this loop.
110 bool contains(const LoopT *L) const {
111 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 111, __PRETTY_FUNCTION__))
;
112 if (L == this)
113 return true;
114 if (!L)
115 return false;
116 return contains(L->getParentLoop());
117 }
118
119 /// Return true if the specified basic block is in this loop.
120 bool contains(const BlockT *BB) const {
121 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 121, __PRETTY_FUNCTION__))
;
122 return DenseBlockSet.count(BB);
123 }
124
125 /// Return true if the specified instruction is in this loop.
126 template <class InstT> bool contains(const InstT *Inst) const {
127 return contains(Inst->getParent());
128 }
129
130 /// Return the loops contained entirely within this loop.
131 const std::vector<LoopT *> &getSubLoops() const {
132 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 132, __PRETTY_FUNCTION__))
;
133 return SubLoops;
134 }
135 std::vector<LoopT *> &getSubLoopsVector() {
136 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 136, __PRETTY_FUNCTION__))
;
137 return SubLoops;
138 }
139 typedef typename std::vector<LoopT *>::const_iterator iterator;
140 typedef
141 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
142 iterator begin() const { return getSubLoops().begin(); }
143 iterator end() const { return getSubLoops().end(); }
144 reverse_iterator rbegin() const { return getSubLoops().rbegin(); }
145 reverse_iterator rend() const { return getSubLoops().rend(); }
146 bool empty() const { return getSubLoops().empty(); }
147
148 /// Get a list of the basic blocks which make up this loop.
149 ArrayRef<BlockT *> getBlocks() const {
150 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 150, __PRETTY_FUNCTION__))
;
151 return Blocks;
152 }
153 typedef typename ArrayRef<BlockT *>::const_iterator block_iterator;
154 block_iterator block_begin() const { return getBlocks().begin(); }
155 block_iterator block_end() const { return getBlocks().end(); }
156 inline iterator_range<block_iterator> blocks() const {
157 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 157, __PRETTY_FUNCTION__))
;
158 return make_range(block_begin(), block_end());
159 }
160
161 /// Get the number of blocks in this loop in constant time.
162 /// Invalidate the loop, indicating that it is no longer a loop.
163 unsigned getNumBlocks() const {
164 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 164, __PRETTY_FUNCTION__))
;
165 return Blocks.size();
166 }
167
168 /// Return a direct, mutable handle to the blocks vector so that we can
169 /// mutate it efficiently with techniques like `std::remove`.
170 std::vector<BlockT *> &getBlocksVector() {
171 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 171, __PRETTY_FUNCTION__))
;
172 return Blocks;
173 }
174 /// Return a direct, mutable handle to the blocks set so that we can
175 /// mutate it efficiently.
176 SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
177 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 177, __PRETTY_FUNCTION__))
;
178 return DenseBlockSet;
179 }
180
181 /// Return a direct, immutable handle to the blocks set.
182 const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
183 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 183, __PRETTY_FUNCTION__))
;
184 return DenseBlockSet;
185 }
186
187 /// Return true if this loop is no longer valid. The only valid use of this
188 /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
189 /// true by the destructor. In other words, if this accessor returns true,
190 /// the caller has already triggered UB by calling this accessor; and so it
191 /// can only be called in a context where a return value of true indicates a
192 /// programmer error.
193 bool isInvalid() const {
194#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
195 return IsInvalid;
196#else
197 return false;
198#endif
199 }
200
201 /// True if terminator in the block can branch to another block that is
202 /// outside of the current loop.
203 bool isLoopExiting(const BlockT *BB) const {
204 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 204, __PRETTY_FUNCTION__))
;
205 for (const auto &Succ : children<const BlockT *>(BB)) {
206 if (!contains(Succ))
207 return true;
208 }
209 return false;
210 }
211
212 /// Returns true if \p BB is a loop-latch.
213 /// A latch block is a block that contains a branch back to the header.
214 /// This function is useful when there are multiple latches in a loop
215 /// because \fn getLoopLatch will return nullptr in that case.
216 bool isLoopLatch(const BlockT *BB) const {
217 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 217, __PRETTY_FUNCTION__))
;
218 assert(contains(BB) && "block does not belong to the loop")((contains(BB) && "block does not belong to the loop"
) ? static_cast<void> (0) : __assert_fail ("contains(BB) && \"block does not belong to the loop\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 218, __PRETTY_FUNCTION__))
;
219
220 BlockT *Header = getHeader();
221 auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header);
222 auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header);
223 return std::find(PredBegin, PredEnd, BB) != PredEnd;
224 }
225
226 /// Calculate the number of back edges to the loop header.
227 unsigned getNumBackEdges() const {
228 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 228, __PRETTY_FUNCTION__))
;
229 unsigned NumBackEdges = 0;
230 BlockT *H = getHeader();
231
232 for (const auto Pred : children<Inverse<BlockT *>>(H))
233 if (contains(Pred))
234 ++NumBackEdges;
235
236 return NumBackEdges;
237 }
238
239 //===--------------------------------------------------------------------===//
240 // APIs for simple analysis of the loop.
241 //
242 // Note that all of these methods can fail on general loops (ie, there may not
243 // be a preheader, etc). For best success, the loop simplification and
244 // induction variable canonicalization pass should be used to normalize loops
245 // for easy analysis. These methods assume canonical loops.
246
247 /// Return all blocks inside the loop that have successors outside of the
248 /// loop. These are the blocks _inside of the current loop_ which branch out.
249 /// The returned list is always unique.
250 void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
251
252 /// If getExitingBlocks would return exactly one block, return that block.
253 /// Otherwise return null.
254 BlockT *getExitingBlock() const;
255
256 /// Return all of the successor blocks of this loop. These are the blocks
257 /// _outside of the current loop_ which are branched to.
258 void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
259
260 /// If getExitBlocks would return exactly one block, return that block.
261 /// Otherwise return null.
262 BlockT *getExitBlock() const;
263
264 /// Return true if no exit block for the loop has a predecessor that is
265 /// outside the loop.
266 bool hasDedicatedExits() const;
267
268 /// Return all unique successor blocks of this loop.
269 /// These are the blocks _outside of the current loop_ which are branched to.
270 /// This assumes that loop exits are in canonical form, i.e. all exits are
271 /// dedicated exits.
272 void getUniqueExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const;
273
274 /// If getUniqueExitBlocks would return exactly one block, return that block.
275 /// Otherwise return null.
276 BlockT *getUniqueExitBlock() const;
277
278 /// Edge type.
279 typedef std::pair<const BlockT *, const BlockT *> Edge;
280
281 /// Return all pairs of (_inside_block_,_outside_block_).
282 void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
283
284 /// If there is a preheader for this loop, return it. A loop has a preheader
285 /// if there is only one edge to the header of the loop from outside of the
286 /// loop. If this is the case, the block branching to the header of the loop
287 /// is the preheader node.
288 ///
289 /// This method returns null if there is no preheader for the loop.
290 BlockT *getLoopPreheader() const;
291
292 /// If the given loop's header has exactly one unique predecessor outside the
293 /// loop, return it. Otherwise return null.
294 /// This is less strict that the loop "preheader" concept, which requires
295 /// the predecessor to have exactly one successor.
296 BlockT *getLoopPredecessor() const;
297
298 /// If there is a single latch block for this loop, return it.
299 /// A latch block is a block that contains a branch back to the header.
300 BlockT *getLoopLatch() const;
301
302 /// Return all loop latch blocks of this loop. A latch block is a block that
303 /// contains a branch back to the header.
304 void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const {
305 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 305, __PRETTY_FUNCTION__))
;
306 BlockT *H = getHeader();
307 for (const auto Pred : children<Inverse<BlockT *>>(H))
308 if (contains(Pred))
309 LoopLatches.push_back(Pred);
310 }
311
312 //===--------------------------------------------------------------------===//
313 // APIs for updating loop information after changing the CFG
314 //
315
316 /// This method is used by other analyses to update loop information.
317 /// NewBB is set to be a new member of the current loop.
318 /// Because of this, it is added as a member of all parent loops, and is added
319 /// to the specified LoopInfo object as being in the current basic block. It
320 /// is not valid to replace the loop header with this method.
321 void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
322
323 /// This is used when splitting loops up. It replaces the OldChild entry in
324 /// our children list with NewChild, and updates the parent pointer of
325 /// OldChild to be null and the NewChild to be this loop.
326 /// This updates the loop depth of the new child.
327 void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
328
329 /// Add the specified loop to be a child of this loop.
330 /// This updates the loop depth of the new child.
331 void addChildLoop(LoopT *NewChild) {
332 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 332, __PRETTY_FUNCTION__))
;
333 assert(!NewChild->ParentLoop && "NewChild already has a parent!")((!NewChild->ParentLoop && "NewChild already has a parent!"
) ? static_cast<void> (0) : __assert_fail ("!NewChild->ParentLoop && \"NewChild already has a parent!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 333, __PRETTY_FUNCTION__))
;
334 NewChild->ParentLoop = static_cast<LoopT *>(this);
335 SubLoops.push_back(NewChild);
336 }
337
338 /// This removes the specified child from being a subloop of this loop. The
339 /// loop is not deleted, as it will presumably be inserted into another loop.
340 LoopT *removeChildLoop(iterator I) {
341 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 341, __PRETTY_FUNCTION__))
;
342 assert(I != SubLoops.end() && "Cannot remove end iterator!")((I != SubLoops.end() && "Cannot remove end iterator!"
) ? static_cast<void> (0) : __assert_fail ("I != SubLoops.end() && \"Cannot remove end iterator!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 342, __PRETTY_FUNCTION__))
;
343 LoopT *Child = *I;
344 assert(Child->ParentLoop == this && "Child is not a child of this loop!")((Child->ParentLoop == this && "Child is not a child of this loop!"
) ? static_cast<void> (0) : __assert_fail ("Child->ParentLoop == this && \"Child is not a child of this loop!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 344, __PRETTY_FUNCTION__))
;
345 SubLoops.erase(SubLoops.begin() + (I - begin()));
346 Child->ParentLoop = nullptr;
347 return Child;
348 }
349
350 /// This removes the specified child from being a subloop of this loop. The
351 /// loop is not deleted, as it will presumably be inserted into another loop.
352 LoopT *removeChildLoop(LoopT *Child) {
353 return removeChildLoop(llvm::find(*this, Child));
354 }
355
356 /// This adds a basic block directly to the basic block list.
357 /// This should only be used by transformations that create new loops. Other
358 /// transformations should use addBasicBlockToLoop.
359 void addBlockEntry(BlockT *BB) {
360 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 360, __PRETTY_FUNCTION__))
;
361 Blocks.push_back(BB);
362 DenseBlockSet.insert(BB);
363 }
364
365 /// interface to reverse Blocks[from, end of loop] in this loop
366 void reverseBlock(unsigned from) {
367 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 367, __PRETTY_FUNCTION__))
;
368 std::reverse(Blocks.begin() + from, Blocks.end());
369 }
370
371 /// interface to do reserve() for Blocks
372 void reserveBlocks(unsigned size) {
373 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 373, __PRETTY_FUNCTION__))
;
374 Blocks.reserve(size);
375 }
376
377 /// This method is used to move BB (which must be part of this loop) to be the
378 /// loop header of the loop (the block that dominates all others).
379 void moveToHeader(BlockT *BB) {
380 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 380, __PRETTY_FUNCTION__))
;
381 if (Blocks[0] == BB)
382 return;
383 for (unsigned i = 0;; ++i) {
384 assert(i != Blocks.size() && "Loop does not contain BB!")((i != Blocks.size() && "Loop does not contain BB!") ?
static_cast<void> (0) : __assert_fail ("i != Blocks.size() && \"Loop does not contain BB!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 384, __PRETTY_FUNCTION__))
;
385 if (Blocks[i] == BB) {
386 Blocks[i] = Blocks[0];
387 Blocks[0] = BB;
388 return;
389 }
390 }
391 }
392
393 /// This removes the specified basic block from the current loop, updating the
394 /// Blocks as appropriate. This does not update the mapping in the LoopInfo
395 /// class.
396 void removeBlockFromLoop(BlockT *BB) {
397 assert(!isInvalid() && "Loop not in a valid state!")((!isInvalid() && "Loop not in a valid state!") ? static_cast
<void> (0) : __assert_fail ("!isInvalid() && \"Loop not in a valid state!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 397, __PRETTY_FUNCTION__))
;
398 auto I = find(Blocks, BB);
399 assert(I != Blocks.end() && "N is not in this list!")((I != Blocks.end() && "N is not in this list!") ? static_cast
<void> (0) : __assert_fail ("I != Blocks.end() && \"N is not in this list!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 399, __PRETTY_FUNCTION__))
;
400 Blocks.erase(I);
401
402 DenseBlockSet.erase(BB);
403 }
404
405 /// Verify loop structure
406 void verifyLoop() const;
407
408 /// Verify loop structure of this loop and all nested loops.
409 void verifyLoopNest(DenseSet<const LoopT *> *Loops) const;
410
411 /// Returns true if the loop is annotated parallel.
412 ///
413 /// Derived classes can override this method using static template
414 /// polymorphism.
415 bool isAnnotatedParallel() const { return false; }
416
417 /// Print loop with all the BBs inside it.
418 void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const;
419
420protected:
421 friend class LoopInfoBase<BlockT, LoopT>;
422
423 /// This creates an empty loop.
424 LoopBase() : ParentLoop(nullptr) {}
425
426 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {
427 Blocks.push_back(BB);
428 DenseBlockSet.insert(BB);
429 }
430
431 // Since loop passes like SCEV are allowed to key analysis results off of
432 // `Loop` pointers, we cannot re-use pointers within a loop pass manager.
433 // This means loop passes should not be `delete` ing `Loop` objects directly
434 // (and risk a later `Loop` allocation re-using the address of a previous one)
435 // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop`
436 // pointer till the end of the lifetime of the `LoopInfo` object.
437 //
438 // To make it easier to follow this rule, we mark the destructor as
439 // non-public.
440 ~LoopBase() {
441 for (auto *SubLoop : SubLoops)
442 SubLoop->~LoopT();
443
444#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
445 IsInvalid = true;
446#endif
447 SubLoops.clear();
448 Blocks.clear();
449 DenseBlockSet.clear();
450 ParentLoop = nullptr;
451 }
452};
453
454template <class BlockT, class LoopT>
455raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
456 Loop.print(OS);
457 return OS;
458}
459
460// Implementation in LoopInfoImpl.h
461extern template class LoopBase<BasicBlock, Loop>;
462
463/// Represents a single loop in the control flow graph. Note that not all SCCs
464/// in the CFG are necessarily loops.
465class Loop : public LoopBase<BasicBlock, Loop> {
466public:
467 /// A range representing the start and end location of a loop.
468 class LocRange {
469 DebugLoc Start;
470 DebugLoc End;
471
472 public:
473 LocRange() {}
474 LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {}
9
Object 'Start' is moved
10
Moved-from object 'Start' is moved
475 LocRange(DebugLoc Start, DebugLoc End)
476 : Start(std::move(Start)), End(std::move(End)) {}
477
478 const DebugLoc &getStart() const { return Start; }
479 const DebugLoc &getEnd() const { return End; }
480
481 /// Check for null.
482 ///
483 explicit operator bool() const { return Start && End; }
484 };
485
486 /// Return true if the specified value is loop invariant.
487 bool isLoopInvariant(const Value *V) const;
488
489 /// Return true if all the operands of the specified instruction are loop
490 /// invariant.
491 bool hasLoopInvariantOperands(const Instruction *I) const;
492
493 /// If the given value is an instruction inside of the loop and it can be
494 /// hoisted, do so to make it trivially loop-invariant.
495 /// Return true if the value after any hoisting is loop invariant. This
496 /// function can be used as a slightly more aggressive replacement for
497 /// isLoopInvariant.
498 ///
499 /// If InsertPt is specified, it is the point to hoist instructions to.
500 /// If null, the terminator of the loop preheader is used.
501 bool makeLoopInvariant(Value *V, bool &Changed,
502 Instruction *InsertPt = nullptr) const;
503
504 /// If the given instruction is inside of the loop and it can be hoisted, do
505 /// so to make it trivially loop-invariant.
506 /// Return true if the instruction after any hoisting is loop invariant. This
507 /// function can be used as a slightly more aggressive replacement for
508 /// isLoopInvariant.
509 ///
510 /// If InsertPt is specified, it is the point to hoist instructions to.
511 /// If null, the terminator of the loop preheader is used.
512 ///
513 bool makeLoopInvariant(Instruction *I, bool &Changed,
514 Instruction *InsertPt = nullptr) const;
515
516 /// Check to see if the loop has a canonical induction variable: an integer
517 /// recurrence that starts at 0 and increments by one each time through the
518 /// loop. If so, return the phi node that corresponds to it.
519 ///
520 /// The IndVarSimplify pass transforms loops to have a canonical induction
521 /// variable.
522 ///
523 PHINode *getCanonicalInductionVariable() const;
524
525 /// Return true if the Loop is in LCSSA form.
526 bool isLCSSAForm(DominatorTree &DT) const;
527
528 /// Return true if this Loop and all inner subloops are in LCSSA form.
529 bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
530
531 /// Return true if the Loop is in the form that the LoopSimplify form
532 /// transforms loops to, which is sometimes called normal form.
533 bool isLoopSimplifyForm() const;
534
535 /// Return true if the loop body is safe to clone in practice.
536 bool isSafeToClone() const;
537
538 /// Returns true if the loop is annotated parallel.
539 ///
540 /// A parallel loop can be assumed to not contain any dependencies between
541 /// iterations by the compiler. That is, any loop-carried dependency checking
542 /// can be skipped completely when parallelizing the loop on the target
543 /// machine. Thus, if the parallel loop information originates from the
544 /// programmer, e.g. via the OpenMP parallel for pragma, it is the
545 /// programmer's responsibility to ensure there are no loop-carried
546 /// dependencies. The final execution order of the instructions across
547 /// iterations is not guaranteed, thus, the end result might or might not
548 /// implement actual concurrent execution of instructions across multiple
549 /// iterations.
550 bool isAnnotatedParallel() const;
551
552 /// Return the llvm.loop loop id metadata node for this loop if it is present.
553 ///
554 /// If this loop contains the same llvm.loop metadata on each branch to the
555 /// header then the node is returned. If any latch instruction does not
556 /// contain llvm.loop or if multiple latches contain different nodes then
557 /// 0 is returned.
558 MDNode *getLoopID() const;
559 /// Set the llvm.loop loop id metadata for this loop.
560 ///
561 /// The LoopID metadata node will be added to each terminator instruction in
562 /// the loop that branches to the loop header.
563 ///
564 /// The LoopID metadata node should have one or more operands and the first
565 /// operand should be the node itself.
566 void setLoopID(MDNode *LoopID) const;
567
568 /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
569 ///
570 /// Remove existing unroll metadata and add unroll disable metadata to
571 /// indicate the loop has already been unrolled. This prevents a loop
572 /// from being unrolled more than is directed by a pragma if the loop
573 /// unrolling pass is run more than once (which it generally is).
574 void setLoopAlreadyUnrolled();
575
576 void dump() const;
577 void dumpVerbose() const;
578
579 /// Return the debug location of the start of this loop.
580 /// This looks for a BB terminating instruction with a known debug
581 /// location by looking at the preheader and header blocks. If it
582 /// cannot find a terminating instruction with location information,
583 /// it returns an unknown location.
584 DebugLoc getStartLoc() const;
585
586 /// Return the source code span of the loop.
587 LocRange getLocRange() const;
588
589 StringRef getName() const {
590 if (BasicBlock *Header = getHeader())
591 if (Header->hasName())
592 return Header->getName();
593 return "<unnamed loop>";
594 }
595
596private:
597 Loop() = default;
598
599 friend class LoopInfoBase<BasicBlock, Loop>;
600 friend class LoopBase<BasicBlock, Loop>;
601 explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
602 ~Loop() = default;
603};
604
605//===----------------------------------------------------------------------===//
606/// This class builds and contains all of the top-level loop
607/// structures in the specified function.
608///
609
610template <class BlockT, class LoopT> class LoopInfoBase {
611 // BBMap - Mapping of basic blocks to the inner most loop they occur in
612 DenseMap<const BlockT *, LoopT *> BBMap;
613 std::vector<LoopT *> TopLevelLoops;
614 BumpPtrAllocator LoopAllocator;
615
616 friend class LoopBase<BlockT, LoopT>;
617 friend class LoopInfo;
618
619 void operator=(const LoopInfoBase &) = delete;
620 LoopInfoBase(const LoopInfoBase &) = delete;
621
622public:
623 LoopInfoBase() {}
624 ~LoopInfoBase() { releaseMemory(); }
625
626 LoopInfoBase(LoopInfoBase &&Arg)
627 : BBMap(std::move(Arg.BBMap)),
628 TopLevelLoops(std::move(Arg.TopLevelLoops)),
629 LoopAllocator(std::move(Arg.LoopAllocator)) {
630 // We have to clear the arguments top level loops as we've taken ownership.
631 Arg.TopLevelLoops.clear();
632 }
633 LoopInfoBase &operator=(LoopInfoBase &&RHS) {
634 BBMap = std::move(RHS.BBMap);
635
636 for (auto *L : TopLevelLoops)
637 L->~LoopT();
638
639 TopLevelLoops = std::move(RHS.TopLevelLoops);
640 LoopAllocator = std::move(RHS.LoopAllocator);
641 RHS.TopLevelLoops.clear();
642 return *this;
643 }
644
645 void releaseMemory() {
646 BBMap.clear();
647
648 for (auto *L : TopLevelLoops)
649 L->~LoopT();
650 TopLevelLoops.clear();
651 LoopAllocator.Reset();
652 }
653
654 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) {
655 LoopT *Storage = LoopAllocator.Allocate<LoopT>();
656 return new (Storage) LoopT(std::forward<ArgsTy>(Args)...);
657 }
658
659 /// iterator/begin/end - The interface to the top-level loops in the current
660 /// function.
661 ///
662 typedef typename std::vector<LoopT *>::const_iterator iterator;
663 typedef
664 typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator;
665 iterator begin() const { return TopLevelLoops.begin(); }
666 iterator end() const { return TopLevelLoops.end(); }
667 reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
668 reverse_iterator rend() const { return TopLevelLoops.rend(); }
669 bool empty() const { return TopLevelLoops.empty(); }
670
671 /// Return all of the loops in the function in preorder across the loop
672 /// nests, with siblings in forward program order.
673 ///
674 /// Note that because loops form a forest of trees, preorder is equivalent to
675 /// reverse postorder.
676 SmallVector<LoopT *, 4> getLoopsInPreorder();
677
678 /// Return all of the loops in the function in preorder across the loop
679 /// nests, with siblings in *reverse* program order.
680 ///
681 /// Note that because loops form a forest of trees, preorder is equivalent to
682 /// reverse postorder.
683 ///
684 /// Also note that this is *not* a reverse preorder. Only the siblings are in
685 /// reverse program order.
686 SmallVector<LoopT *, 4> getLoopsInReverseSiblingPreorder();
687
688 /// Return the inner most loop that BB lives in. If a basic block is in no
689 /// loop (for example the entry node), null is returned.
690 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }
691
692 /// Same as getLoopFor.
693 const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); }
694
695 /// Return the loop nesting level of the specified block. A depth of 0 means
696 /// the block is not inside any loop.
697 unsigned getLoopDepth(const BlockT *BB) const {
698 const LoopT *L = getLoopFor(BB);
699 return L ? L->getLoopDepth() : 0;
700 }
701
702 // True if the block is a loop header node
703 bool isLoopHeader(const BlockT *BB) const {
704 const LoopT *L = getLoopFor(BB);
705 return L && L->getHeader() == BB;
706 }
707
708 /// This removes the specified top-level loop from this loop info object.
709 /// The loop is not deleted, as it will presumably be inserted into
710 /// another loop.
711 LoopT *removeLoop(iterator I) {
712 assert(I != end() && "Cannot remove end iterator!")((I != end() && "Cannot remove end iterator!") ? static_cast
<void> (0) : __assert_fail ("I != end() && \"Cannot remove end iterator!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 712, __PRETTY_FUNCTION__))
;
713 LoopT *L = *I;
714 assert(!L->getParentLoop() && "Not a top-level loop!")((!L->getParentLoop() && "Not a top-level loop!") ?
static_cast<void> (0) : __assert_fail ("!L->getParentLoop() && \"Not a top-level loop!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 714, __PRETTY_FUNCTION__))
;
715 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));
716 return L;
717 }
718
719 /// Change the top-level loop that contains BB to the specified loop.
720 /// This should be used by transformations that restructure the loop hierarchy
721 /// tree.
722 void changeLoopFor(BlockT *BB, LoopT *L) {
723 if (!L) {
724 BBMap.erase(BB);
725 return;
726 }
727 BBMap[BB] = L;
728 }
729
730 /// Replace the specified loop in the top-level loops list with the indicated
731 /// loop.
732 void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) {
733 auto I = find(TopLevelLoops, OldLoop);
734 assert(I != TopLevelLoops.end() && "Old loop not at top level!")((I != TopLevelLoops.end() && "Old loop not at top level!"
) ? static_cast<void> (0) : __assert_fail ("I != TopLevelLoops.end() && \"Old loop not at top level!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 734, __PRETTY_FUNCTION__))
;
735 *I = NewLoop;
736 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&((!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
"Loops already embedded into a subloop!") ? static_cast<void
> (0) : __assert_fail ("!NewLoop->ParentLoop && !OldLoop->ParentLoop && \"Loops already embedded into a subloop!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 737, __PRETTY_FUNCTION__))
737 "Loops already embedded into a subloop!")((!NewLoop->ParentLoop && !OldLoop->ParentLoop &&
"Loops already embedded into a subloop!") ? static_cast<void
> (0) : __assert_fail ("!NewLoop->ParentLoop && !OldLoop->ParentLoop && \"Loops already embedded into a subloop!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 737, __PRETTY_FUNCTION__))
;
738 }
739
740 /// This adds the specified loop to the collection of top-level loops.
741 void addTopLevelLoop(LoopT *New) {
742 assert(!New->getParentLoop() && "Loop already in subloop!")((!New->getParentLoop() && "Loop already in subloop!"
) ? static_cast<void> (0) : __assert_fail ("!New->getParentLoop() && \"Loop already in subloop!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 742, __PRETTY_FUNCTION__))
;
743 TopLevelLoops.push_back(New);
744 }
745
746 /// This method completely removes BB from all data structures,
747 /// including all of the Loop objects it is nested in and our mapping from
748 /// BasicBlocks to loops.
749 void removeBlock(BlockT *BB) {
750 auto I = BBMap.find(BB);
751 if (I != BBMap.end()) {
752 for (LoopT *L = I->second; L; L = L->getParentLoop())
753 L->removeBlockFromLoop(BB);
754
755 BBMap.erase(I);
756 }
757 }
758
759 // Internals
760
761 static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
762 const LoopT *ParentLoop) {
763 if (!SubLoop)
764 return true;
765 if (SubLoop == ParentLoop)
766 return false;
767 return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
768 }
769
770 /// Create the loop forest using a stable algorithm.
771 void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
772
773 // Debugging
774 void print(raw_ostream &OS) const;
775
776 void verify(const DominatorTreeBase<BlockT, false> &DomTree) const;
777
778 /// Destroy a loop that has been removed from the `LoopInfo` nest.
779 ///
780 /// This runs the destructor of the loop object making it invalid to
781 /// reference afterward. The memory is retained so that the *pointer* to the
782 /// loop remains valid.
783 ///
784 /// The caller is responsible for removing this loop from the loop nest and
785 /// otherwise disconnecting it from the broader `LoopInfo` data structures.
786 /// Callers that don't naturally handle this themselves should probably call
787 /// `erase' instead.
788 void destroy(LoopT *L) {
789 L->~LoopT();
790
791 // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons
792 // \c L, but the pointer remains valid for non-dereferencing uses.
793 LoopAllocator.Deallocate(L);
794 }
795};
796
797// Implementation in LoopInfoImpl.h
798extern template class LoopInfoBase<BasicBlock, Loop>;
799
800class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
801 typedef LoopInfoBase<BasicBlock, Loop> BaseT;
802
803 friend class LoopBase<BasicBlock, Loop>;
804
805 void operator=(const LoopInfo &) = delete;
806 LoopInfo(const LoopInfo &) = delete;
807
808public:
809 LoopInfo() {}
810 explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree);
811
812 LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
813 LoopInfo &operator=(LoopInfo &&RHS) {
814 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
815 return *this;
816 }
817
818 /// Handle invalidation explicitly.
819 bool invalidate(Function &F, const PreservedAnalyses &PA,
820 FunctionAnalysisManager::Invalidator &);
821
822 // Most of the public interface is provided via LoopInfoBase.
823
824 /// Update LoopInfo after removing the last backedge from a loop. This updates
825 /// the loop forest and parent loops for each block so that \c L is no longer
826 /// referenced, but does not actually delete \c L immediately. The pointer
827 /// will remain valid until this LoopInfo's memory is released.
828 void erase(Loop *L);
829
830 /// Returns true if replacing From with To everywhere is guaranteed to
831 /// preserve LCSSA form.
832 bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
833 // Preserving LCSSA form is only problematic if the replacing value is an
834 // instruction.
835 Instruction *I = dyn_cast<Instruction>(To);
836 if (!I)
837 return true;
838 // If both instructions are defined in the same basic block then replacement
839 // cannot break LCSSA form.
840 if (I->getParent() == From->getParent())
841 return true;
842 // If the instruction is not defined in a loop then it can safely replace
843 // anything.
844 Loop *ToLoop = getLoopFor(I->getParent());
845 if (!ToLoop)
846 return true;
847 // If the replacing instruction is defined in the same loop as the original
848 // instruction, or in a loop that contains it as an inner loop, then using
849 // it as a replacement will not break LCSSA form.
850 return ToLoop->contains(getLoopFor(From->getParent()));
851 }
852
853 /// Checks if moving a specific instruction can break LCSSA in any loop.
854 ///
855 /// Return true if moving \p Inst to before \p NewLoc will break LCSSA,
856 /// assuming that the function containing \p Inst and \p NewLoc is currently
857 /// in LCSSA form.
858 bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
859 assert(Inst->getFunction() == NewLoc->getFunction() &&((Inst->getFunction() == NewLoc->getFunction() &&
"Can't reason about IPO!") ? static_cast<void> (0) : __assert_fail
("Inst->getFunction() == NewLoc->getFunction() && \"Can't reason about IPO!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 860, __PRETTY_FUNCTION__))
860 "Can't reason about IPO!")((Inst->getFunction() == NewLoc->getFunction() &&
"Can't reason about IPO!") ? static_cast<void> (0) : __assert_fail
("Inst->getFunction() == NewLoc->getFunction() && \"Can't reason about IPO!\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/Analysis/LoopInfo.h"
, 860, __PRETTY_FUNCTION__))
;
861
862 auto *OldBB = Inst->getParent();
863 auto *NewBB = NewLoc->getParent();
864
865 // Movement within the same loop does not break LCSSA (the equality check is
866 // to avoid doing a hashtable lookup in case of intra-block movement).
867 if (OldBB == NewBB)
868 return true;
869
870 auto *OldLoop = getLoopFor(OldBB);
871 auto *NewLoop = getLoopFor(NewBB);
872
873 if (OldLoop == NewLoop)
874 return true;
875
876 // Check if Outer contains Inner; with the null loop counting as the
877 // "outermost" loop.
878 auto Contains = [](const Loop *Outer, const Loop *Inner) {
879 return !Outer || Outer->contains(Inner);
880 };
881
882 // To check that the movement of Inst to before NewLoc does not break LCSSA,
883 // we need to check two sets of uses for possible LCSSA violations at
884 // NewLoc: the users of NewInst, and the operands of NewInst.
885
886 // If we know we're hoisting Inst out of an inner loop to an outer loop,
887 // then the uses *of* Inst don't need to be checked.
888
889 if (!Contains(NewLoop, OldLoop)) {
890 for (Use &U : Inst->uses()) {
891 auto *UI = cast<Instruction>(U.getUser());
892 auto *UBB = isa<PHINode>(UI) ? cast<PHINode>(UI)->getIncomingBlock(U)
893 : UI->getParent();
894 if (UBB != NewBB && getLoopFor(UBB) != NewLoop)
895 return false;
896 }
897 }
898
899 // If we know we're sinking Inst from an outer loop into an inner loop, then
900 // the *operands* of Inst don't need to be checked.
901
902 if (!Contains(OldLoop, NewLoop)) {
903 // See below on why we can't handle phi nodes here.
904 if (isa<PHINode>(Inst))
905 return false;
906
907 for (Use &U : Inst->operands()) {
908 auto *DefI = dyn_cast<Instruction>(U.get());
909 if (!DefI)
910 return false;
911
912 // This would need adjustment if we allow Inst to be a phi node -- the
913 // new use block won't simply be NewBB.
914
915 auto *DefBlock = DefI->getParent();
916 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)
917 return false;
918 }
919 }
920
921 return true;
922 }
923};
924
925// Allow clients to walk the list of nested loops...
926template <> struct GraphTraits<const Loop *> {
927 typedef const Loop *NodeRef;
928 typedef LoopInfo::iterator ChildIteratorType;
929
930 static NodeRef getEntryNode(const Loop *L) { return L; }
931 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
932 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
933};
934
935template <> struct GraphTraits<Loop *> {
936 typedef Loop *NodeRef;
937 typedef LoopInfo::iterator ChildIteratorType;
938
939 static NodeRef getEntryNode(Loop *L) { return L; }
940 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
941 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
942};
943
944/// Analysis pass that exposes the \c LoopInfo for a function.
945class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
946 friend AnalysisInfoMixin<LoopAnalysis>;
947 static AnalysisKey Key;
948
949public:
950 typedef LoopInfo Result;
951
952 LoopInfo run(Function &F, FunctionAnalysisManager &AM);
953};
954
955/// Printer pass for the \c LoopAnalysis results.
956class LoopPrinterPass : public PassInfoMixin<LoopPrinterPass> {
957 raw_ostream &OS;
958
959public:
960 explicit LoopPrinterPass(raw_ostream &OS) : OS(OS) {}
961 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
962};
963
964/// Verifier pass for the \c LoopAnalysis results.
965struct LoopVerifierPass : public PassInfoMixin<LoopVerifierPass> {
966 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
967};
968
969/// The legacy pass manager's analysis pass to compute loop information.
970class LoopInfoWrapperPass : public FunctionPass {
971 LoopInfo LI;
972
973public:
974 static char ID; // Pass identification, replacement for typeid
975
976 LoopInfoWrapperPass() : FunctionPass(ID) {
977 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
978 }
979
980 LoopInfo &getLoopInfo() { return LI; }
981 const LoopInfo &getLoopInfo() const { return LI; }
982
983 /// Calculate the natural loop information for a given function.
984 bool runOnFunction(Function &F) override;
985
986 void verifyAnalysis() const override;
987
988 void releaseMemory() override { LI.releaseMemory(); }
989
990 void print(raw_ostream &O, const Module *M = nullptr) const override;
991
992 void getAnalysisUsage(AnalysisUsage &AU) const override;
993};
994
995/// Function to print a loop's contents as LLVM's text IR assembly.
996void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");
997
998/// Find and return the loop attribute node for the attribute @p Name in
999/// @p LoopID. Return nullptr if there is no such attribute.
1000MDNode *findOptionMDForLoopID(MDNode *LoopID, StringRef Name);
1001
1002/// Find string metadata for a loop.
1003///
1004/// Returns the MDNode where the first operand is the metadata's name. The
1005/// following operands are the metadata's values. If no metadata with @p Name is
1006/// found, return nullptr.
1007MDNode *findOptionMDForLoop(const Loop *TheLoop, StringRef Name);
1008
1009/// Return whether an MDNode might represent an access group.
1010///
1011/// Access group metadata nodes have to be distinct and empty. Being
1012/// always-empty ensures that it never needs to be changed (which -- because
1013/// MDNodes are designed immutable -- would require creating a new MDNode). Note
1014/// that this is not a sufficient condition: not every distinct and empty NDNode
1015/// is representing an access group.
1016bool isValidAsAccessGroup(MDNode *AccGroup);
1017
1018} // End llvm namespace
1019
1020#endif