1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the LoopInfo class that is used to identify natural loops
10 // and determine the loop depth of various nodes of the CFG.  Note that the
11 // loops identified may actually be several natural loops that share the same
12 // header node... not just a single natural loop.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/ScopeExit.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/Analysis/IVDescriptors.h"
21 #include "llvm/Analysis/LoopInfoImpl.h"
22 #include "llvm/Analysis/LoopIterator.h"
23 #include "llvm/Analysis/LoopNestAnalysis.h"
24 #include "llvm/Analysis/MemorySSA.h"
25 #include "llvm/Analysis/MemorySSAUpdater.h"
26 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/Config/llvm-config.h"
29 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/DebugLoc.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/IRPrintingPasses.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/LLVMContext.h"
36 #include "llvm/IR/Metadata.h"
37 #include "llvm/IR/PassManager.h"
38 #include "llvm/IR/PrintPasses.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include <algorithm>
44 using namespace llvm;
45 
46 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
47 template class llvm::LoopBase<BasicBlock, Loop>;
48 template class llvm::LoopInfoBase<BasicBlock, Loop>;
49 
50 // Always verify loopinfo if expensive checking is enabled.
51 #ifdef EXPENSIVE_CHECKS
52 bool llvm::VerifyLoopInfo = true;
53 #else
54 bool llvm::VerifyLoopInfo = false;
55 #endif
56 static cl::opt<bool, true>
57     VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
58                     cl::Hidden, cl::desc("Verify loop info (time consuming)"));
59 
60 //===----------------------------------------------------------------------===//
61 // Loop implementation
62 //
63 
isLoopInvariant(const Value * V) const64 bool Loop::isLoopInvariant(const Value *V) const {
65   if (const Instruction *I = dyn_cast<Instruction>(V))
66     return !contains(I);
67   return true; // All non-instructions are loop invariant
68 }
69 
hasLoopInvariantOperands(const Instruction * I) const70 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
71   return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
72 }
73 
makeLoopInvariant(Value * V,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU) const74 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
75                              MemorySSAUpdater *MSSAU) const {
76   if (Instruction *I = dyn_cast<Instruction>(V))
77     return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
78   return true; // All non-instructions are loop-invariant.
79 }
80 
makeLoopInvariant(Instruction * I,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU) const81 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
82                              Instruction *InsertPt,
83                              MemorySSAUpdater *MSSAU) const {
84   // Test if the value is already loop-invariant.
85   if (isLoopInvariant(I))
86     return true;
87   if (!isSafeToSpeculativelyExecute(I))
88     return false;
89   if (I->mayReadFromMemory())
90     return false;
91   // EH block instructions are immobile.
92   if (I->isEHPad())
93     return false;
94   // Determine the insertion point, unless one was given.
95   if (!InsertPt) {
96     BasicBlock *Preheader = getLoopPreheader();
97     // Without a preheader, hoisting is not feasible.
98     if (!Preheader)
99       return false;
100     InsertPt = Preheader->getTerminator();
101   }
102   // Don't hoist instructions with loop-variant operands.
103   for (Value *Operand : I->operands())
104     if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
105       return false;
106 
107   // Hoist.
108   I->moveBefore(InsertPt);
109   if (MSSAU)
110     if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
111       MSSAU->moveToPlace(MUD, InsertPt->getParent(),
112                          MemorySSA::BeforeTerminator);
113 
114   // There is possibility of hoisting this instruction above some arbitrary
115   // condition. Any metadata defined on it can be control dependent on this
116   // condition. Conservatively strip it here so that we don't give any wrong
117   // information to the optimizer.
118   I->dropUnknownNonDebugMetadata();
119 
120   Changed = true;
121   return true;
122 }
123 
getIncomingAndBackEdge(BasicBlock * & Incoming,BasicBlock * & Backedge) const124 bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
125                                   BasicBlock *&Backedge) const {
126   BasicBlock *H = getHeader();
127 
128   Incoming = nullptr;
129   Backedge = nullptr;
130   pred_iterator PI = pred_begin(H);
131   assert(PI != pred_end(H) && "Loop must have at least one backedge!");
132   Backedge = *PI++;
133   if (PI == pred_end(H))
134     return false; // dead loop
135   Incoming = *PI++;
136   if (PI != pred_end(H))
137     return false; // multiple backedges?
138 
139   if (contains(Incoming)) {
140     if (contains(Backedge))
141       return false;
142     std::swap(Incoming, Backedge);
143   } else if (!contains(Backedge))
144     return false;
145 
146   assert(Incoming && Backedge && "expected non-null incoming and backedges");
147   return true;
148 }
149 
getCanonicalInductionVariable() const150 PHINode *Loop::getCanonicalInductionVariable() const {
151   BasicBlock *H = getHeader();
152 
153   BasicBlock *Incoming = nullptr, *Backedge = nullptr;
154   if (!getIncomingAndBackEdge(Incoming, Backedge))
155     return nullptr;
156 
157   // Loop over all of the PHI nodes, looking for a canonical indvar.
158   for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
159     PHINode *PN = cast<PHINode>(I);
160     if (ConstantInt *CI =
161             dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
162       if (CI->isZero())
163         if (Instruction *Inc =
164                 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
165           if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
166             if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
167               if (CI->isOne())
168                 return PN;
169   }
170   return nullptr;
171 }
172 
173 /// Get the latch condition instruction.
getLatchCmpInst(const Loop & L)174 static ICmpInst *getLatchCmpInst(const Loop &L) {
175   if (BasicBlock *Latch = L.getLoopLatch())
176     if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))
177       if (BI->isConditional())
178         return dyn_cast<ICmpInst>(BI->getCondition());
179 
180   return nullptr;
181 }
182 
183 /// Return the final value of the loop induction variable if found.
findFinalIVValue(const Loop & L,const PHINode & IndVar,const Instruction & StepInst)184 static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
185                                const Instruction &StepInst) {
186   ICmpInst *LatchCmpInst = getLatchCmpInst(L);
187   if (!LatchCmpInst)
188     return nullptr;
189 
190   Value *Op0 = LatchCmpInst->getOperand(0);
191   Value *Op1 = LatchCmpInst->getOperand(1);
192   if (Op0 == &IndVar || Op0 == &StepInst)
193     return Op1;
194 
195   if (Op1 == &IndVar || Op1 == &StepInst)
196     return Op0;
197 
198   return nullptr;
199 }
200 
getBounds(const Loop & L,PHINode & IndVar,ScalarEvolution & SE)201 Optional<Loop::LoopBounds> Loop::LoopBounds::getBounds(const Loop &L,
202                                                        PHINode &IndVar,
203                                                        ScalarEvolution &SE) {
204   InductionDescriptor IndDesc;
205   if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
206     return None;
207 
208   Value *InitialIVValue = IndDesc.getStartValue();
209   Instruction *StepInst = IndDesc.getInductionBinOp();
210   if (!InitialIVValue || !StepInst)
211     return None;
212 
213   const SCEV *Step = IndDesc.getStep();
214   Value *StepInstOp1 = StepInst->getOperand(1);
215   Value *StepInstOp0 = StepInst->getOperand(0);
216   Value *StepValue = nullptr;
217   if (SE.getSCEV(StepInstOp1) == Step)
218     StepValue = StepInstOp1;
219   else if (SE.getSCEV(StepInstOp0) == Step)
220     StepValue = StepInstOp0;
221 
222   Value *FinalIVValue = findFinalIVValue(L, IndVar, *StepInst);
223   if (!FinalIVValue)
224     return None;
225 
226   return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
227                     SE);
228 }
229 
230 using Direction = Loop::LoopBounds::Direction;
231 
getCanonicalPredicate() const232 ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
233   BasicBlock *Latch = L.getLoopLatch();
234   assert(Latch && "Expecting valid latch");
235 
236   BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());
237   assert(BI && BI->isConditional() && "Expecting conditional latch branch");
238 
239   ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());
240   assert(LatchCmpInst &&
241          "Expecting the latch compare instruction to be a CmpInst");
242 
243   // Need to inverse the predicate when first successor is not the loop
244   // header
245   ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())
246                                  ? LatchCmpInst->getPredicate()
247                                  : LatchCmpInst->getInversePredicate();
248 
249   if (LatchCmpInst->getOperand(0) == &getFinalIVValue())
250     Pred = ICmpInst::getSwappedPredicate(Pred);
251 
252   // Need to flip strictness of the predicate when the latch compare instruction
253   // is not using StepInst
254   if (LatchCmpInst->getOperand(0) == &getStepInst() ||
255       LatchCmpInst->getOperand(1) == &getStepInst())
256     return Pred;
257 
258   // Cannot flip strictness of NE and EQ
259   if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
260     return ICmpInst::getFlippedStrictnessPredicate(Pred);
261 
262   Direction D = getDirection();
263   if (D == Direction::Increasing)
264     return ICmpInst::ICMP_SLT;
265 
266   if (D == Direction::Decreasing)
267     return ICmpInst::ICMP_SGT;
268 
269   // If cannot determine the direction, then unable to find the canonical
270   // predicate
271   return ICmpInst::BAD_ICMP_PREDICATE;
272 }
273 
getDirection() const274 Direction Loop::LoopBounds::getDirection() const {
275   if (const SCEVAddRecExpr *StepAddRecExpr =
276           dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))
277     if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
278       if (SE.isKnownPositive(StepRecur))
279         return Direction::Increasing;
280       if (SE.isKnownNegative(StepRecur))
281         return Direction::Decreasing;
282     }
283 
284   return Direction::Unknown;
285 }
286 
getBounds(ScalarEvolution & SE) const287 Optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
288   if (PHINode *IndVar = getInductionVariable(SE))
289     return LoopBounds::getBounds(*this, *IndVar, SE);
290 
291   return None;
292 }
293 
getInductionVariable(ScalarEvolution & SE) const294 PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
295   if (!isLoopSimplifyForm())
296     return nullptr;
297 
298   BasicBlock *Header = getHeader();
299   assert(Header && "Expected a valid loop header");
300   ICmpInst *CmpInst = getLatchCmpInst(*this);
301   if (!CmpInst)
302     return nullptr;
303 
304   Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
305   Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
306 
307   for (PHINode &IndVar : Header->phis()) {
308     InductionDescriptor IndDesc;
309     if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
310       continue;
311 
312     Instruction *StepInst = IndDesc.getInductionBinOp();
313 
314     // case 1:
315     // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
316     // StepInst = IndVar + step
317     // cmp = StepInst < FinalValue
318     if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
319       return &IndVar;
320 
321     // case 2:
322     // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
323     // StepInst = IndVar + step
324     // cmp = IndVar < FinalValue
325     if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
326       return &IndVar;
327   }
328 
329   return nullptr;
330 }
331 
getInductionDescriptor(ScalarEvolution & SE,InductionDescriptor & IndDesc) const332 bool Loop::getInductionDescriptor(ScalarEvolution &SE,
333                                   InductionDescriptor &IndDesc) const {
334   if (PHINode *IndVar = getInductionVariable(SE))
335     return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
336 
337   return false;
338 }
339 
isAuxiliaryInductionVariable(PHINode & AuxIndVar,ScalarEvolution & SE) const340 bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
341                                         ScalarEvolution &SE) const {
342   // Located in the loop header
343   BasicBlock *Header = getHeader();
344   if (AuxIndVar.getParent() != Header)
345     return false;
346 
347   // No uses outside of the loop
348   for (User *U : AuxIndVar.users())
349     if (const Instruction *I = dyn_cast<Instruction>(U))
350       if (!contains(I))
351         return false;
352 
353   InductionDescriptor IndDesc;
354   if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
355     return false;
356 
357   // The step instruction opcode should be add or sub.
358   if (IndDesc.getInductionOpcode() != Instruction::Add &&
359       IndDesc.getInductionOpcode() != Instruction::Sub)
360     return false;
361 
362   // Incremented by a loop invariant step for each loop iteration
363   return SE.isLoopInvariant(IndDesc.getStep(), this);
364 }
365 
getLoopGuardBranch() const366 BranchInst *Loop::getLoopGuardBranch() const {
367   if (!isLoopSimplifyForm())
368     return nullptr;
369 
370   BasicBlock *Preheader = getLoopPreheader();
371   assert(Preheader && getLoopLatch() &&
372          "Expecting a loop with valid preheader and latch");
373 
374   // Loop should be in rotate form.
375   if (!isRotatedForm())
376     return nullptr;
377 
378   // Disallow loops with more than one unique exit block, as we do not verify
379   // that GuardOtherSucc post dominates all exit blocks.
380   BasicBlock *ExitFromLatch = getUniqueExitBlock();
381   if (!ExitFromLatch)
382     return nullptr;
383 
384   BasicBlock *GuardBB = Preheader->getUniquePredecessor();
385   if (!GuardBB)
386     return nullptr;
387 
388   assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
389 
390   BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
391   if (!GuardBI || GuardBI->isUnconditional())
392     return nullptr;
393 
394   BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
395                                    ? GuardBI->getSuccessor(1)
396                                    : GuardBI->getSuccessor(0);
397 
398   // Check if ExitFromLatch (or any BasicBlock which is an empty unique
399   // successor of ExitFromLatch) is equal to GuardOtherSucc. If
400   // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
401   // loop is GuardBI (return GuardBI), otherwise return nullptr.
402   if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,
403                                      /*CheckUniquePred=*/true) ==
404       GuardOtherSucc)
405     return GuardBI;
406   else
407     return nullptr;
408 }
409 
isCanonical(ScalarEvolution & SE) const410 bool Loop::isCanonical(ScalarEvolution &SE) const {
411   InductionDescriptor IndDesc;
412   if (!getInductionDescriptor(SE, IndDesc))
413     return false;
414 
415   ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
416   if (!Init || !Init->isZero())
417     return false;
418 
419   if (IndDesc.getInductionOpcode() != Instruction::Add)
420     return false;
421 
422   ConstantInt *Step = IndDesc.getConstIntStepValue();
423   if (!Step || !Step->isOne())
424     return false;
425 
426   return true;
427 }
428 
429 // Check that 'BB' doesn't have any uses outside of the 'L'
isBlockInLCSSAForm(const Loop & L,const BasicBlock & BB,const DominatorTree & DT)430 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
431                                const DominatorTree &DT) {
432   for (const Instruction &I : BB) {
433     // Tokens can't be used in PHI nodes and live-out tokens prevent loop
434     // optimizations, so for the purposes of considered LCSSA form, we
435     // can ignore them.
436     if (I.getType()->isTokenTy())
437       continue;
438 
439     for (const Use &U : I.uses()) {
440       const Instruction *UI = cast<Instruction>(U.getUser());
441       const BasicBlock *UserBB = UI->getParent();
442 
443       // For practical purposes, we consider that the use in a PHI
444       // occurs in the respective predecessor block. For more info,
445       // see the `phi` doc in LangRef and the LCSSA doc.
446       if (const PHINode *P = dyn_cast<PHINode>(UI))
447         UserBB = P->getIncomingBlock(U);
448 
449       // Check the current block, as a fast-path, before checking whether
450       // the use is anywhere in the loop.  Most values are used in the same
451       // block they are defined in.  Also, blocks not reachable from the
452       // entry are special; uses in them don't need to go through PHIs.
453       if (UserBB != &BB && !L.contains(UserBB) &&
454           DT.isReachableFromEntry(UserBB))
455         return false;
456     }
457   }
458   return true;
459 }
460 
isLCSSAForm(const DominatorTree & DT) const461 bool Loop::isLCSSAForm(const DominatorTree &DT) const {
462   // For each block we check that it doesn't have any uses outside of this loop.
463   return all_of(this->blocks(), [&](const BasicBlock *BB) {
464     return isBlockInLCSSAForm(*this, *BB, DT);
465   });
466 }
467 
isRecursivelyLCSSAForm(const DominatorTree & DT,const LoopInfo & LI) const468 bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT,
469                                   const LoopInfo &LI) const {
470   // For each block we check that it doesn't have any uses outside of its
471   // innermost loop. This process will transitively guarantee that the current
472   // loop and all of the nested loops are in LCSSA form.
473   return all_of(this->blocks(), [&](const BasicBlock *BB) {
474     return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
475   });
476 }
477 
isLoopSimplifyForm() const478 bool Loop::isLoopSimplifyForm() const {
479   // Normal-form loops have a preheader, a single backedge, and all of their
480   // exits have all their predecessors inside the loop.
481   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
482 }
483 
484 // Routines that reform the loop CFG and split edges often fail on indirectbr.
isSafeToClone() const485 bool Loop::isSafeToClone() const {
486   // Return false if any loop blocks contain indirectbrs, or there are any calls
487   // to noduplicate functions.
488   // FIXME: it should be ok to clone CallBrInst's if we correctly update the
489   // operand list to reflect the newly cloned labels.
490   for (BasicBlock *BB : this->blocks()) {
491     if (isa<IndirectBrInst>(BB->getTerminator()) ||
492         isa<CallBrInst>(BB->getTerminator()))
493       return false;
494 
495     for (Instruction &I : *BB)
496       if (auto *CB = dyn_cast<CallBase>(&I))
497         if (CB->cannotDuplicate())
498           return false;
499   }
500   return true;
501 }
502 
getLoopID() const503 MDNode *Loop::getLoopID() const {
504   MDNode *LoopID = nullptr;
505 
506   // Go through the latch blocks and check the terminator for the metadata.
507   SmallVector<BasicBlock *, 4> LatchesBlocks;
508   getLoopLatches(LatchesBlocks);
509   for (BasicBlock *BB : LatchesBlocks) {
510     Instruction *TI = BB->getTerminator();
511     MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
512 
513     if (!MD)
514       return nullptr;
515 
516     if (!LoopID)
517       LoopID = MD;
518     else if (MD != LoopID)
519       return nullptr;
520   }
521   if (!LoopID || LoopID->getNumOperands() == 0 ||
522       LoopID->getOperand(0) != LoopID)
523     return nullptr;
524   return LoopID;
525 }
526 
setLoopID(MDNode * LoopID) const527 void Loop::setLoopID(MDNode *LoopID) const {
528   assert((!LoopID || LoopID->getNumOperands() > 0) &&
529          "Loop ID needs at least one operand");
530   assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
531          "Loop ID should refer to itself");
532 
533   SmallVector<BasicBlock *, 4> LoopLatches;
534   getLoopLatches(LoopLatches);
535   for (BasicBlock *BB : LoopLatches)
536     BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
537 }
538 
setLoopAlreadyUnrolled()539 void Loop::setLoopAlreadyUnrolled() {
540   LLVMContext &Context = getHeader()->getContext();
541 
542   MDNode *DisableUnrollMD =
543       MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
544   MDNode *LoopID = getLoopID();
545   MDNode *NewLoopID = makePostTransformationMetadata(
546       Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
547   setLoopID(NewLoopID);
548 }
549 
setLoopMustProgress()550 void Loop::setLoopMustProgress() {
551   LLVMContext &Context = getHeader()->getContext();
552 
553   MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
554 
555   if (MustProgress)
556     return;
557 
558   MDNode *MustProgressMD =
559       MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
560   MDNode *LoopID = getLoopID();
561   MDNode *NewLoopID =
562       makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
563   setLoopID(NewLoopID);
564 }
565 
isAnnotatedParallel() const566 bool Loop::isAnnotatedParallel() const {
567   MDNode *DesiredLoopIdMetadata = getLoopID();
568 
569   if (!DesiredLoopIdMetadata)
570     return false;
571 
572   MDNode *ParallelAccesses =
573       findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
574   SmallPtrSet<MDNode *, 4>
575       ParallelAccessGroups; // For scalable 'contains' check.
576   if (ParallelAccesses) {
577     for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
578       MDNode *AccGroup = cast<MDNode>(MD.get());
579       assert(isValidAsAccessGroup(AccGroup) &&
580              "List item must be an access group");
581       ParallelAccessGroups.insert(AccGroup);
582     }
583   }
584 
585   // The loop branch contains the parallel loop metadata. In order to ensure
586   // that any parallel-loop-unaware optimization pass hasn't added loop-carried
587   // dependencies (thus converted the loop back to a sequential loop), check
588   // that all the memory instructions in the loop belong to an access group that
589   // is parallel to this loop.
590   for (BasicBlock *BB : this->blocks()) {
591     for (Instruction &I : *BB) {
592       if (!I.mayReadOrWriteMemory())
593         continue;
594 
595       if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
596         auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
597           if (AG->getNumOperands() == 0) {
598             assert(isValidAsAccessGroup(AG) && "Item must be an access group");
599             return ParallelAccessGroups.count(AG);
600           }
601 
602           for (const MDOperand &AccessListItem : AG->operands()) {
603             MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
604             assert(isValidAsAccessGroup(AccGroup) &&
605                    "List item must be an access group");
606             if (ParallelAccessGroups.count(AccGroup))
607               return true;
608           }
609           return false;
610         };
611 
612         if (ContainsAccessGroup(AccessGroup))
613           continue;
614       }
615 
616       // The memory instruction can refer to the loop identifier metadata
617       // directly or indirectly through another list metadata (in case of
618       // nested parallel loops). The loop identifier metadata refers to
619       // itself so we can check both cases with the same routine.
620       MDNode *LoopIdMD =
621           I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
622 
623       if (!LoopIdMD)
624         return false;
625 
626       if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
627         return false;
628     }
629   }
630   return true;
631 }
632 
getStartLoc() const633 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
634 
getLocRange() const635 Loop::LocRange Loop::getLocRange() const {
636   // If we have a debug location in the loop ID, then use it.
637   if (MDNode *LoopID = getLoopID()) {
638     DebugLoc Start;
639     // We use the first DebugLoc in the header as the start location of the loop
640     // and if there is a second DebugLoc in the header we use it as end location
641     // of the loop.
642     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
643       if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
644         if (!Start)
645           Start = DebugLoc(L);
646         else
647           return LocRange(Start, DebugLoc(L));
648       }
649     }
650 
651     if (Start)
652       return LocRange(Start);
653   }
654 
655   // Try the pre-header first.
656   if (BasicBlock *PHeadBB = getLoopPreheader())
657     if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
658       return LocRange(DL);
659 
660   // If we have no pre-header or there are no instructions with debug
661   // info in it, try the header.
662   if (BasicBlock *HeadBB = getHeader())
663     return LocRange(HeadBB->getTerminator()->getDebugLoc());
664 
665   return LocRange();
666 }
667 
668 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const669 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
670 
dumpVerbose() const671 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
672   print(dbgs(), /*Verbose=*/true);
673 }
674 #endif
675 
676 //===----------------------------------------------------------------------===//
677 // UnloopUpdater implementation
678 //
679 
680 namespace {
681 /// Find the new parent loop for all blocks within the "unloop" whose last
682 /// backedges has just been removed.
683 class UnloopUpdater {
684   Loop &Unloop;
685   LoopInfo *LI;
686 
687   LoopBlocksDFS DFS;
688 
689   // Map unloop's immediate subloops to their nearest reachable parents. Nested
690   // loops within these subloops will not change parents. However, an immediate
691   // subloop's new parent will be the nearest loop reachable from either its own
692   // exits *or* any of its nested loop's exits.
693   DenseMap<Loop *, Loop *> SubloopParents;
694 
695   // Flag the presence of an irreducible backedge whose destination is a block
696   // directly contained by the original unloop.
697   bool FoundIB;
698 
699 public:
UnloopUpdater(Loop * UL,LoopInfo * LInfo)700   UnloopUpdater(Loop *UL, LoopInfo *LInfo)
701       : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
702 
703   void updateBlockParents();
704 
705   void removeBlocksFromAncestors();
706 
707   void updateSubloopParents();
708 
709 protected:
710   Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
711 };
712 } // end anonymous namespace
713 
714 /// Update the parent loop for all blocks that are directly contained within the
715 /// original "unloop".
updateBlockParents()716 void UnloopUpdater::updateBlockParents() {
717   if (Unloop.getNumBlocks()) {
718     // Perform a post order CFG traversal of all blocks within this loop,
719     // propagating the nearest loop from successors to predecessors.
720     LoopBlocksTraversal Traversal(DFS, LI);
721     for (BasicBlock *POI : Traversal) {
722 
723       Loop *L = LI->getLoopFor(POI);
724       Loop *NL = getNearestLoop(POI, L);
725 
726       if (NL != L) {
727         // For reducible loops, NL is now an ancestor of Unloop.
728         assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
729                "uninitialized successor");
730         LI->changeLoopFor(POI, NL);
731       } else {
732         // Or the current block is part of a subloop, in which case its parent
733         // is unchanged.
734         assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
735       }
736     }
737   }
738   // Each irreducible loop within the unloop induces a round of iteration using
739   // the DFS result cached by Traversal.
740   bool Changed = FoundIB;
741   for (unsigned NIters = 0; Changed; ++NIters) {
742     assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
743 
744     // Iterate over the postorder list of blocks, propagating the nearest loop
745     // from successors to predecessors as before.
746     Changed = false;
747     for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
748                                    POE = DFS.endPostorder();
749          POI != POE; ++POI) {
750 
751       Loop *L = LI->getLoopFor(*POI);
752       Loop *NL = getNearestLoop(*POI, L);
753       if (NL != L) {
754         assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
755                "uninitialized successor");
756         LI->changeLoopFor(*POI, NL);
757         Changed = true;
758       }
759     }
760   }
761 }
762 
763 /// Remove unloop's blocks from all ancestors below their new parents.
removeBlocksFromAncestors()764 void UnloopUpdater::removeBlocksFromAncestors() {
765   // Remove all unloop's blocks (including those in nested subloops) from
766   // ancestors below the new parent loop.
767   for (BasicBlock *BB : Unloop.blocks()) {
768     Loop *OuterParent = LI->getLoopFor(BB);
769     if (Unloop.contains(OuterParent)) {
770       while (OuterParent->getParentLoop() != &Unloop)
771         OuterParent = OuterParent->getParentLoop();
772       OuterParent = SubloopParents[OuterParent];
773     }
774     // Remove blocks from former Ancestors except Unloop itself which will be
775     // deleted.
776     for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
777          OldParent = OldParent->getParentLoop()) {
778       assert(OldParent && "new loop is not an ancestor of the original");
779       OldParent->removeBlockFromLoop(BB);
780     }
781   }
782 }
783 
784 /// Update the parent loop for all subloops directly nested within unloop.
updateSubloopParents()785 void UnloopUpdater::updateSubloopParents() {
786   while (!Unloop.isInnermost()) {
787     Loop *Subloop = *std::prev(Unloop.end());
788     Unloop.removeChildLoop(std::prev(Unloop.end()));
789 
790     assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
791     if (Loop *Parent = SubloopParents[Subloop])
792       Parent->addChildLoop(Subloop);
793     else
794       LI->addTopLevelLoop(Subloop);
795   }
796 }
797 
798 /// Return the nearest parent loop among this block's successors. If a successor
799 /// is a subloop header, consider its parent to be the nearest parent of the
800 /// subloop's exits.
801 ///
802 /// For subloop blocks, simply update SubloopParents and return NULL.
getNearestLoop(BasicBlock * BB,Loop * BBLoop)803 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
804 
805   // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
806   // is considered uninitialized.
807   Loop *NearLoop = BBLoop;
808 
809   Loop *Subloop = nullptr;
810   if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
811     Subloop = NearLoop;
812     // Find the subloop ancestor that is directly contained within Unloop.
813     while (Subloop->getParentLoop() != &Unloop) {
814       Subloop = Subloop->getParentLoop();
815       assert(Subloop && "subloop is not an ancestor of the original loop");
816     }
817     // Get the current nearest parent of the Subloop exits, initially Unloop.
818     NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
819   }
820 
821   succ_iterator I = succ_begin(BB), E = succ_end(BB);
822   if (I == E) {
823     assert(!Subloop && "subloop blocks must have a successor");
824     NearLoop = nullptr; // unloop blocks may now exit the function.
825   }
826   for (; I != E; ++I) {
827     if (*I == BB)
828       continue; // self loops are uninteresting
829 
830     Loop *L = LI->getLoopFor(*I);
831     if (L == &Unloop) {
832       // This successor has not been processed. This path must lead to an
833       // irreducible backedge.
834       assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
835       FoundIB = true;
836     }
837     if (L != &Unloop && Unloop.contains(L)) {
838       // Successor is in a subloop.
839       if (Subloop)
840         continue; // Branching within subloops. Ignore it.
841 
842       // BB branches from the original into a subloop header.
843       assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
844 
845       // Get the current nearest parent of the Subloop's exits.
846       L = SubloopParents[L];
847       // L could be Unloop if the only exit was an irreducible backedge.
848     }
849     if (L == &Unloop) {
850       continue;
851     }
852     // Handle critical edges from Unloop into a sibling loop.
853     if (L && !L->contains(&Unloop)) {
854       L = L->getParentLoop();
855     }
856     // Remember the nearest parent loop among successors or subloop exits.
857     if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
858       NearLoop = L;
859   }
860   if (Subloop) {
861     SubloopParents[Subloop] = NearLoop;
862     return BBLoop;
863   }
864   return NearLoop;
865 }
866 
LoopInfo(const DomTreeBase<BasicBlock> & DomTree)867 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
868 
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)869 bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
870                           FunctionAnalysisManager::Invalidator &) {
871   // Check whether the analysis, all analyses on functions, or the function's
872   // CFG have been preserved.
873   auto PAC = PA.getChecker<LoopAnalysis>();
874   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
875            PAC.preservedSet<CFGAnalyses>());
876 }
877 
erase(Loop * Unloop)878 void LoopInfo::erase(Loop *Unloop) {
879   assert(!Unloop->isInvalid() && "Loop has already been erased!");
880 
881   auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
882 
883   // First handle the special case of no parent loop to simplify the algorithm.
884   if (Unloop->isOutermost()) {
885     // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
886     for (BasicBlock *BB : Unloop->blocks()) {
887       // Don't reparent blocks in subloops.
888       if (getLoopFor(BB) != Unloop)
889         continue;
890 
891       // Blocks no longer have a parent but are still referenced by Unloop until
892       // the Unloop object is deleted.
893       changeLoopFor(BB, nullptr);
894     }
895 
896     // Remove the loop from the top-level LoopInfo object.
897     for (iterator I = begin();; ++I) {
898       assert(I != end() && "Couldn't find loop");
899       if (*I == Unloop) {
900         removeLoop(I);
901         break;
902       }
903     }
904 
905     // Move all of the subloops to the top-level.
906     while (!Unloop->isInnermost())
907       addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
908 
909     return;
910   }
911 
912   // Update the parent loop for all blocks within the loop. Blocks within
913   // subloops will not change parents.
914   UnloopUpdater Updater(Unloop, this);
915   Updater.updateBlockParents();
916 
917   // Remove blocks from former ancestor loops.
918   Updater.removeBlocksFromAncestors();
919 
920   // Add direct subloops as children in their new parent loop.
921   Updater.updateSubloopParents();
922 
923   // Remove unloop from its parent loop.
924   Loop *ParentLoop = Unloop->getParentLoop();
925   for (Loop::iterator I = ParentLoop->begin();; ++I) {
926     assert(I != ParentLoop->end() && "Couldn't find loop");
927     if (*I == Unloop) {
928       ParentLoop->removeChildLoop(I);
929       break;
930     }
931   }
932 }
933 
934 bool
wouldBeOutOfLoopUseRequiringLCSSA(const Value * V,const BasicBlock * ExitBB) const935 LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,
936                                             const BasicBlock *ExitBB) const {
937   if (V->getType()->isTokenTy())
938     // We can't form PHIs of token type, so the definition of LCSSA excludes
939     // values of that type.
940     return false;
941 
942   const Instruction *I = dyn_cast<Instruction>(V);
943   if (!I)
944     return false;
945   const Loop *L = getLoopFor(I->getParent());
946   if (!L)
947     return false;
948   if (L->contains(ExitBB))
949     // Could be an exit bb of a subloop and contained in defining loop
950     return false;
951 
952   // We found a (new) out-of-loop use location, for a value defined in-loop.
953   // (Note that because of LCSSA, we don't have to account for values defined
954   // in sibling loops.  Such values will have LCSSA phis of their own in the
955   // common parent loop.)
956   return true;
957 }
958 
959 AnalysisKey LoopAnalysis::Key;
960 
run(Function & F,FunctionAnalysisManager & AM)961 LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
962   // FIXME: Currently we create a LoopInfo from scratch for every function.
963   // This may prove to be too wasteful due to deallocating and re-allocating
964   // memory each time for the underlying map and vector datastructures. At some
965   // point it may prove worthwhile to use a freelist and recycle LoopInfo
966   // objects. I don't want to add that kind of complexity until the scope of
967   // the problem is better understood.
968   LoopInfo LI;
969   LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
970   return LI;
971 }
972 
run(Function & F,FunctionAnalysisManager & AM)973 PreservedAnalyses LoopPrinterPass::run(Function &F,
974                                        FunctionAnalysisManager &AM) {
975   AM.getResult<LoopAnalysis>(F).print(OS);
976   return PreservedAnalyses::all();
977 }
978 
printLoop(Loop & L,raw_ostream & OS,const std::string & Banner)979 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
980 
981   if (forcePrintModuleIR()) {
982     // handling -print-module-scope
983     OS << Banner << " (loop: ";
984     L.getHeader()->printAsOperand(OS, false);
985     OS << ")\n";
986 
987     // printing whole module
988     OS << *L.getHeader()->getModule();
989     return;
990   }
991 
992   OS << Banner;
993 
994   auto *PreHeader = L.getLoopPreheader();
995   if (PreHeader) {
996     OS << "\n; Preheader:";
997     PreHeader->print(OS);
998     OS << "\n; Loop:";
999   }
1000 
1001   for (auto *Block : L.blocks())
1002     if (Block)
1003       Block->print(OS);
1004     else
1005       OS << "Printing <null> block";
1006 
1007   SmallVector<BasicBlock *, 8> ExitBlocks;
1008   L.getExitBlocks(ExitBlocks);
1009   if (!ExitBlocks.empty()) {
1010     OS << "\n; Exit blocks";
1011     for (auto *Block : ExitBlocks)
1012       if (Block)
1013         Block->print(OS);
1014       else
1015         OS << "Printing <null> block";
1016   }
1017 }
1018 
findOptionMDForLoopID(MDNode * LoopID,StringRef Name)1019 MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
1020   // No loop metadata node, no loop properties.
1021   if (!LoopID)
1022     return nullptr;
1023 
1024   // First operand should refer to the metadata node itself, for legacy reasons.
1025   assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1026   assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1027 
1028   // Iterate over the metdata node operands and look for MDString metadata.
1029   for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1030     MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1031     if (!MD || MD->getNumOperands() < 1)
1032       continue;
1033     MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1034     if (!S)
1035       continue;
1036     // Return the operand node if MDString holds expected metadata.
1037     if (Name.equals(S->getString()))
1038       return MD;
1039   }
1040 
1041   // Loop property not found.
1042   return nullptr;
1043 }
1044 
findOptionMDForLoop(const Loop * TheLoop,StringRef Name)1045 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
1046   return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1047 }
1048 
isValidAsAccessGroup(MDNode * Node)1049 bool llvm::isValidAsAccessGroup(MDNode *Node) {
1050   return Node->getNumOperands() == 0 && Node->isDistinct();
1051 }
1052 
makePostTransformationMetadata(LLVMContext & Context,MDNode * OrigLoopID,ArrayRef<StringRef> RemovePrefixes,ArrayRef<MDNode * > AddAttrs)1053 MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
1054                                              MDNode *OrigLoopID,
1055                                              ArrayRef<StringRef> RemovePrefixes,
1056                                              ArrayRef<MDNode *> AddAttrs) {
1057   // First remove any existing loop metadata related to this transformation.
1058   SmallVector<Metadata *, 4> MDs;
1059 
1060   // Reserve first location for self reference to the LoopID metadata node.
1061   MDs.push_back(nullptr);
1062 
1063   // Remove metadata for the transformation that has been applied or that became
1064   // outdated.
1065   if (OrigLoopID) {
1066     for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1067       bool IsVectorMetadata = false;
1068       Metadata *Op = OrigLoopID->getOperand(i);
1069       if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1070         const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1071         if (S)
1072           IsVectorMetadata =
1073               llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1074                 return S->getString().startswith(Prefix);
1075               });
1076       }
1077       if (!IsVectorMetadata)
1078         MDs.push_back(Op);
1079     }
1080   }
1081 
1082   // Add metadata to avoid reapplying a transformation, such as
1083   // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1084   MDs.append(AddAttrs.begin(), AddAttrs.end());
1085 
1086   MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1087   // Replace the temporary node with a self-reference.
1088   NewLoopID->replaceOperandWith(0, NewLoopID);
1089   return NewLoopID;
1090 }
1091 
1092 //===----------------------------------------------------------------------===//
1093 // LoopInfo implementation
1094 //
1095 
LoopInfoWrapperPass()1096 LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) {
1097   initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1098 }
1099 
1100 char LoopInfoWrapperPass::ID = 0;
1101 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1102                       true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)1103 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1104 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1105                     true, true)
1106 
1107 bool LoopInfoWrapperPass::runOnFunction(Function &) {
1108   releaseMemory();
1109   LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1110   return false;
1111 }
1112 
verifyAnalysis() const1113 void LoopInfoWrapperPass::verifyAnalysis() const {
1114   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1115   // function each time verifyAnalysis is called is very expensive. The
1116   // -verify-loop-info option can enable this. In order to perform some
1117   // checking by default, LoopPass has been taught to call verifyLoop manually
1118   // during loop pass sequences.
1119   if (VerifyLoopInfo) {
1120     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1121     LI.verify(DT);
1122   }
1123 }
1124 
getAnalysisUsage(AnalysisUsage & AU) const1125 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1126   AU.setPreservesAll();
1127   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1128 }
1129 
print(raw_ostream & OS,const Module *) const1130 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
1131   LI.print(OS);
1132 }
1133 
run(Function & F,FunctionAnalysisManager & AM)1134 PreservedAnalyses LoopVerifierPass::run(Function &F,
1135                                         FunctionAnalysisManager &AM) {
1136   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1137   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1138   LI.verify(DT);
1139   return PreservedAnalyses::all();
1140 }
1141 
1142 //===----------------------------------------------------------------------===//
1143 // LoopBlocksDFS implementation
1144 //
1145 
1146 /// Traverse the loop blocks and store the DFS result.
1147 /// Useful for clients that just want the final DFS result and don't need to
1148 /// visit blocks during the initial traversal.
perform(LoopInfo * LI)1149 void LoopBlocksDFS::perform(LoopInfo *LI) {
1150   LoopBlocksTraversal Traversal(*this, LI);
1151   for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1152                                         POE = Traversal.end();
1153        POI != POE; ++POI)
1154     ;
1155 }
1156