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>
38 using namespace llvm;
39
40 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
41 template class llvm::LoopBase<BasicBlock, Loop>;
42 template class llvm::LoopInfoBase<BasicBlock, Loop>;
43
44 // Always verify loopinfo if expensive checking is enabled.
45 #ifdef EXPENSIVE_CHECKS
46 bool llvm::VerifyLoopInfo = true;
47 #else
48 bool llvm::VerifyLoopInfo = false;
49 #endif
50 static 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
isLoopInvariant(const Value * V) const58 bool 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
hasLoopInvariantOperands(const Instruction * I) const64 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
65 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
66 }
67
makeLoopInvariant(Value * V,bool & Changed,Instruction * InsertPt) const68 bool 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
makeLoopInvariant(Instruction * I,bool & Changed,Instruction * InsertPt) const75 bool 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
getCanonicalInductionVariable() const113 PHINode *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!");
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'
isBlockInLCSSAForm(const Loop & L,const BasicBlock & BB,DominatorTree & DT)150 static 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
isLCSSAForm(DominatorTree & DT) const177 bool 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
isRecursivelyLCSSAForm(DominatorTree & DT,const LoopInfo & LI) const184 bool 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
isLoopSimplifyForm() const193 bool 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.
isSafeToClone() const200 bool 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
getLoopID() const215 MDNode *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
setLoopID(MDNode * LoopID) const239 void Loop::setLoopID(MDNode *LoopID) const {
240 assert((!LoopID || LoopID->getNumOperands() > 0) &&
241 "Loop ID needs at least one operand");
242 assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
243 "Loop ID should refer to itself");
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
setLoopAlreadyUnrolled()257 void 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
isAnnotatedParallel() const290 bool 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) &&
304 "List item must be an access group");
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");
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) &&
329 "List item must be an access group");
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
getStartLoc() const365 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
366
getLocRange() const367 Loop::LocRange Loop::getLocRange() const {
368 // If we have a debug location in the loop ID, then use it.
369 if (MDNode *LoopID = getLoopID()) {
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())
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())
395 return LocRange(HeadBB->getTerminator()->getDebugLoc());
396
397 return LocRange();
398 }
399
400 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const401 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
402
dumpVerbose() const403 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
404 print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
405 }
406 #endif
407
408 //===----------------------------------------------------------------------===//
409 // UnloopUpdater implementation
410 //
411
412 namespace {
413 /// Find the new parent loop for all blocks within the "unloop" whose last
414 /// backedges has just been removed.
415 class 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
431 public:
UnloopUpdater(Loop * UL,LoopInfo * LInfo)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
441 protected:
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".
updateBlockParents()448 void 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))) &&
461 "uninitialized successor");
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");
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");
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)) &&
487 "uninitialized successor");
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.
removeBlocksFromAncestors()496 void 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");
512 OldParent->removeBlockFromLoop(*BI);
513 }
514 }
515 }
516
517 /// Update the parent loop for all subloops directly nested within unloop.
updateSubloopParents()518 void 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");
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.
getNearestLoop(BasicBlock * BB,Loop * BBLoop)536 Loop *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");
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");
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");
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");
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
LoopInfo(const DomTreeBase<BasicBlock> & DomTree)600 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
601
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)602 bool 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
erase(Loop * Unloop)611 void LoopInfo::erase(Loop *Unloop) {
612 assert(!Unloop->isInvalid() && "Loop has already been erased!");
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");
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");
663 if (*I == Unloop) {
664 ParentLoop->removeChildLoop(I);
665 break;
666 }
667 }
668 }
669
670 AnalysisKey LoopAnalysis::Key;
671
run(Function & F,FunctionAnalysisManager & AM)672 LoopInfo 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
run(Function & F,FunctionAnalysisManager & AM)684 PreservedAnalyses LoopPrinterPass::run(Function &F,
685 FunctionAnalysisManager &AM) {
686 AM.getResult<LoopAnalysis>(F).print(OS);
687 return PreservedAnalyses::all();
688 }
689
printLoop(Loop & L,raw_ostream & OS,const std::string & Banner)690 void 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
findOptionMDForLoopID(MDNode * LoopID,StringRef Name)730 MDNode *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");
737 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
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
findOptionMDForLoop(const Loop * TheLoop,StringRef Name)756 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
757 return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
758 }
759
isValidAsAccessGroup(MDNode * Node)760 bool llvm::isValidAsAccessGroup(MDNode *Node) {
761 return Node->getNumOperands() == 0 && Node->isDistinct();
762 }
763
764 //===----------------------------------------------------------------------===//
765 // LoopInfo implementation
766 //
767
768 char LoopInfoWrapperPass::ID = 0;
769 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
770 true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)771 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
772 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
773 true, true)
774
775 bool LoopInfoWrapperPass::runOnFunction(Function &) {
776 releaseMemory();
777 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
778 return false;
779 }
780
verifyAnalysis() const781 void 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
getAnalysisUsage(AnalysisUsage & AU) const793 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
794 AU.setPreservesAll();
795 AU.addRequired<DominatorTreeWrapperPass>();
796 }
797
print(raw_ostream & OS,const Module *) const798 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
799 LI.print(OS);
800 }
801
run(Function & F,FunctionAnalysisManager & AM)802 PreservedAnalyses 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.
perform(LoopInfo * LI)817 void 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 }
824