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/ScopeExit.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/Analysis/IVDescriptors.h"
20 #include "llvm/Analysis/LoopIterator.h"
21 #include "llvm/Analysis/LoopNestAnalysis.h"
22 #include "llvm/Analysis/MemorySSA.h"
23 #include "llvm/Analysis/MemorySSAUpdater.h"
24 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Config/llvm-config.h"
27 #include "llvm/IR/CFG.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DebugLoc.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/Metadata.h"
34 #include "llvm/IR/PassManager.h"
35 #include "llvm/IR/PrintPasses.h"
36 #include "llvm/InitializePasses.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/GenericLoopInfoImpl.h"
39 #include "llvm/Support/raw_ostream.h"
40 using namespace llvm;
41
42 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
43 template class llvm::LoopBase<BasicBlock, Loop>;
44 template class llvm::LoopInfoBase<BasicBlock, Loop>;
45
46 // Always verify loopinfo if expensive checking is enabled.
47 #ifdef EXPENSIVE_CHECKS
48 bool llvm::VerifyLoopInfo = true;
49 #else
50 bool llvm::VerifyLoopInfo = false;
51 #endif
52 static cl::opt<bool, true>
53 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
54 cl::Hidden, cl::desc("Verify loop info (time consuming)"));
55
56 //===----------------------------------------------------------------------===//
57 // Loop implementation
58 //
59
isLoopInvariant(const Value * V) const60 bool Loop::isLoopInvariant(const Value *V) const {
61 if (const Instruction *I = dyn_cast<Instruction>(V))
62 return !contains(I);
63 return true; // All non-instructions are loop invariant
64 }
65
hasLoopInvariantOperands(const Instruction * I) const66 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
67 return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
68 }
69
makeLoopInvariant(Value * V,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU,ScalarEvolution * SE) const70 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
71 MemorySSAUpdater *MSSAU,
72 ScalarEvolution *SE) const {
73 if (Instruction *I = dyn_cast<Instruction>(V))
74 return makeLoopInvariant(I, Changed, InsertPt, MSSAU, SE);
75 return true; // All non-instructions are loop-invariant.
76 }
77
makeLoopInvariant(Instruction * I,bool & Changed,Instruction * InsertPt,MemorySSAUpdater * MSSAU,ScalarEvolution * SE) const78 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
79 Instruction *InsertPt, MemorySSAUpdater *MSSAU,
80 ScalarEvolution *SE) const {
81 // Test if the value is already loop-invariant.
82 if (isLoopInvariant(I))
83 return true;
84 if (!isSafeToSpeculativelyExecute(I))
85 return false;
86 if (I->mayReadFromMemory())
87 return false;
88 // EH block instructions are immobile.
89 if (I->isEHPad())
90 return false;
91 // Determine the insertion point, unless one was given.
92 if (!InsertPt) {
93 BasicBlock *Preheader = getLoopPreheader();
94 // Without a preheader, hoisting is not feasible.
95 if (!Preheader)
96 return false;
97 InsertPt = Preheader->getTerminator();
98 }
99 // Don't hoist instructions with loop-variant operands.
100 for (Value *Operand : I->operands())
101 if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU, SE))
102 return false;
103
104 // Hoist.
105 I->moveBefore(InsertPt);
106 if (MSSAU)
107 if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
108 MSSAU->moveToPlace(MUD, InsertPt->getParent(),
109 MemorySSA::BeforeTerminator);
110
111 // There is possibility of hoisting this instruction above some arbitrary
112 // condition. Any metadata defined on it can be control dependent on this
113 // condition. Conservatively strip it here so that we don't give any wrong
114 // information to the optimizer.
115 I->dropUnknownNonDebugMetadata();
116
117 if (SE)
118 SE->forgetBlockAndLoopDispositions(I);
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() const174 ICmpInst *Loop::getLatchCmpInst() const {
175 if (BasicBlock *Latch = 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 = L.getLatchCmpInst();
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
201 std::optional<Loop::LoopBounds>
getBounds(const Loop & L,PHINode & IndVar,ScalarEvolution & SE)202 Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar,
203 ScalarEvolution &SE) {
204 InductionDescriptor IndDesc;
205 if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))
206 return std::nullopt;
207
208 Value *InitialIVValue = IndDesc.getStartValue();
209 Instruction *StepInst = IndDesc.getInductionBinOp();
210 if (!InitialIVValue || !StepInst)
211 return std::nullopt;
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 std::nullopt;
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 std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
288 if (PHINode *IndVar = getInductionVariable(SE))
289 return LoopBounds::getBounds(*this, *IndVar, SE);
290
291 return std::nullopt;
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();
301 if (!CmpInst)
302 return nullptr;
303
304 Value *LatchCmpOp0 = CmpInst->getOperand(0);
305 Value *LatchCmpOp1 = 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 BasicBlock *Latch = getLoopLatch();
313 Value *StepInst = IndVar.getIncomingValueForBlock(Latch);
314
315 // case 1:
316 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
317 // StepInst = IndVar + step
318 // cmp = StepInst < FinalValue
319 if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
320 return &IndVar;
321
322 // case 2:
323 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
324 // StepInst = IndVar + step
325 // cmp = IndVar < FinalValue
326 if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
327 return &IndVar;
328 }
329
330 return nullptr;
331 }
332
getInductionDescriptor(ScalarEvolution & SE,InductionDescriptor & IndDesc) const333 bool Loop::getInductionDescriptor(ScalarEvolution &SE,
334 InductionDescriptor &IndDesc) const {
335 if (PHINode *IndVar = getInductionVariable(SE))
336 return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
337
338 return false;
339 }
340
isAuxiliaryInductionVariable(PHINode & AuxIndVar,ScalarEvolution & SE) const341 bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
342 ScalarEvolution &SE) const {
343 // Located in the loop header
344 BasicBlock *Header = getHeader();
345 if (AuxIndVar.getParent() != Header)
346 return false;
347
348 // No uses outside of the loop
349 for (User *U : AuxIndVar.users())
350 if (const Instruction *I = dyn_cast<Instruction>(U))
351 if (!contains(I))
352 return false;
353
354 InductionDescriptor IndDesc;
355 if (!InductionDescriptor::isInductionPHI(&AuxIndVar, this, &SE, IndDesc))
356 return false;
357
358 // The step instruction opcode should be add or sub.
359 if (IndDesc.getInductionOpcode() != Instruction::Add &&
360 IndDesc.getInductionOpcode() != Instruction::Sub)
361 return false;
362
363 // Incremented by a loop invariant step for each loop iteration
364 return SE.isLoopInvariant(IndDesc.getStep(), this);
365 }
366
getLoopGuardBranch() const367 BranchInst *Loop::getLoopGuardBranch() const {
368 if (!isLoopSimplifyForm())
369 return nullptr;
370
371 BasicBlock *Preheader = getLoopPreheader();
372 assert(Preheader && getLoopLatch() &&
373 "Expecting a loop with valid preheader and latch");
374
375 // Loop should be in rotate form.
376 if (!isRotatedForm())
377 return nullptr;
378
379 // Disallow loops with more than one unique exit block, as we do not verify
380 // that GuardOtherSucc post dominates all exit blocks.
381 BasicBlock *ExitFromLatch = getUniqueExitBlock();
382 if (!ExitFromLatch)
383 return nullptr;
384
385 BasicBlock *GuardBB = Preheader->getUniquePredecessor();
386 if (!GuardBB)
387 return nullptr;
388
389 assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
390
391 BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());
392 if (!GuardBI || GuardBI->isUnconditional())
393 return nullptr;
394
395 BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)
396 ? GuardBI->getSuccessor(1)
397 : GuardBI->getSuccessor(0);
398
399 // Check if ExitFromLatch (or any BasicBlock which is an empty unique
400 // successor of ExitFromLatch) is equal to GuardOtherSucc. If
401 // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
402 // loop is GuardBI (return GuardBI), otherwise return nullptr.
403 if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,
404 /*CheckUniquePred=*/true) ==
405 GuardOtherSucc)
406 return GuardBI;
407 else
408 return nullptr;
409 }
410
isCanonical(ScalarEvolution & SE) const411 bool Loop::isCanonical(ScalarEvolution &SE) const {
412 InductionDescriptor IndDesc;
413 if (!getInductionDescriptor(SE, IndDesc))
414 return false;
415
416 ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());
417 if (!Init || !Init->isZero())
418 return false;
419
420 if (IndDesc.getInductionOpcode() != Instruction::Add)
421 return false;
422
423 ConstantInt *Step = IndDesc.getConstIntStepValue();
424 if (!Step || !Step->isOne())
425 return false;
426
427 return true;
428 }
429
430 // Check that 'BB' doesn't have any uses outside of the 'L'
isBlockInLCSSAForm(const Loop & L,const BasicBlock & BB,const DominatorTree & DT,bool IgnoreTokens)431 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
432 const DominatorTree &DT, bool IgnoreTokens) {
433 for (const Instruction &I : BB) {
434 // Tokens can't be used in PHI nodes and live-out tokens prevent loop
435 // optimizations, so for the purposes of considered LCSSA form, we
436 // can ignore them.
437 if (IgnoreTokens && I.getType()->isTokenTy())
438 continue;
439
440 for (const Use &U : I.uses()) {
441 const Instruction *UI = cast<Instruction>(U.getUser());
442 const BasicBlock *UserBB = UI->getParent();
443
444 // For practical purposes, we consider that the use in a PHI
445 // occurs in the respective predecessor block. For more info,
446 // see the `phi` doc in LangRef and the LCSSA doc.
447 if (const PHINode *P = dyn_cast<PHINode>(UI))
448 UserBB = P->getIncomingBlock(U);
449
450 // Check the current block, as a fast-path, before checking whether
451 // the use is anywhere in the loop. Most values are used in the same
452 // block they are defined in. Also, blocks not reachable from the
453 // entry are special; uses in them don't need to go through PHIs.
454 if (UserBB != &BB && !L.contains(UserBB) &&
455 DT.isReachableFromEntry(UserBB))
456 return false;
457 }
458 }
459 return true;
460 }
461
isLCSSAForm(const DominatorTree & DT,bool IgnoreTokens) const462 bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const {
463 // For each block we check that it doesn't have any uses outside of this loop.
464 return all_of(this->blocks(), [&](const BasicBlock *BB) {
465 return isBlockInLCSSAForm(*this, *BB, DT, IgnoreTokens);
466 });
467 }
468
isRecursivelyLCSSAForm(const DominatorTree & DT,const LoopInfo & LI,bool IgnoreTokens) const469 bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI,
470 bool IgnoreTokens) const {
471 // For each block we check that it doesn't have any uses outside of its
472 // innermost loop. This process will transitively guarantee that the current
473 // loop and all of the nested loops are in LCSSA form.
474 return all_of(this->blocks(), [&](const BasicBlock *BB) {
475 return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT, IgnoreTokens);
476 });
477 }
478
isLoopSimplifyForm() const479 bool Loop::isLoopSimplifyForm() const {
480 // Normal-form loops have a preheader, a single backedge, and all of their
481 // exits have all their predecessors inside the loop.
482 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
483 }
484
485 // Routines that reform the loop CFG and split edges often fail on indirectbr.
isSafeToClone() const486 bool Loop::isSafeToClone() const {
487 // Return false if any loop blocks contain indirectbrs, or there are any calls
488 // to noduplicate functions.
489 for (BasicBlock *BB : this->blocks()) {
490 if (isa<IndirectBrInst>(BB->getTerminator()))
491 return false;
492
493 for (Instruction &I : *BB)
494 if (auto *CB = dyn_cast<CallBase>(&I))
495 if (CB->cannotDuplicate())
496 return false;
497 }
498 return true;
499 }
500
getLoopID() const501 MDNode *Loop::getLoopID() const {
502 MDNode *LoopID = nullptr;
503
504 // Go through the latch blocks and check the terminator for the metadata.
505 SmallVector<BasicBlock *, 4> LatchesBlocks;
506 getLoopLatches(LatchesBlocks);
507 for (BasicBlock *BB : LatchesBlocks) {
508 Instruction *TI = BB->getTerminator();
509 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
510
511 if (!MD)
512 return nullptr;
513
514 if (!LoopID)
515 LoopID = MD;
516 else if (MD != LoopID)
517 return nullptr;
518 }
519 if (!LoopID || LoopID->getNumOperands() == 0 ||
520 LoopID->getOperand(0) != LoopID)
521 return nullptr;
522 return LoopID;
523 }
524
setLoopID(MDNode * LoopID) const525 void Loop::setLoopID(MDNode *LoopID) const {
526 assert((!LoopID || LoopID->getNumOperands() > 0) &&
527 "Loop ID needs at least one operand");
528 assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
529 "Loop ID should refer to itself");
530
531 SmallVector<BasicBlock *, 4> LoopLatches;
532 getLoopLatches(LoopLatches);
533 for (BasicBlock *BB : LoopLatches)
534 BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
535 }
536
setLoopAlreadyUnrolled()537 void Loop::setLoopAlreadyUnrolled() {
538 LLVMContext &Context = getHeader()->getContext();
539
540 MDNode *DisableUnrollMD =
541 MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
542 MDNode *LoopID = getLoopID();
543 MDNode *NewLoopID = makePostTransformationMetadata(
544 Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
545 setLoopID(NewLoopID);
546 }
547
setLoopMustProgress()548 void Loop::setLoopMustProgress() {
549 LLVMContext &Context = getHeader()->getContext();
550
551 MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
552
553 if (MustProgress)
554 return;
555
556 MDNode *MustProgressMD =
557 MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
558 MDNode *LoopID = getLoopID();
559 MDNode *NewLoopID =
560 makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
561 setLoopID(NewLoopID);
562 }
563
isAnnotatedParallel() const564 bool Loop::isAnnotatedParallel() const {
565 MDNode *DesiredLoopIdMetadata = getLoopID();
566
567 if (!DesiredLoopIdMetadata)
568 return false;
569
570 MDNode *ParallelAccesses =
571 findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
572 SmallPtrSet<MDNode *, 4>
573 ParallelAccessGroups; // For scalable 'contains' check.
574 if (ParallelAccesses) {
575 for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
576 MDNode *AccGroup = cast<MDNode>(MD.get());
577 assert(isValidAsAccessGroup(AccGroup) &&
578 "List item must be an access group");
579 ParallelAccessGroups.insert(AccGroup);
580 }
581 }
582
583 // The loop branch contains the parallel loop metadata. In order to ensure
584 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
585 // dependencies (thus converted the loop back to a sequential loop), check
586 // that all the memory instructions in the loop belong to an access group that
587 // is parallel to this loop.
588 for (BasicBlock *BB : this->blocks()) {
589 for (Instruction &I : *BB) {
590 if (!I.mayReadOrWriteMemory())
591 continue;
592
593 if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
594 auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
595 if (AG->getNumOperands() == 0) {
596 assert(isValidAsAccessGroup(AG) && "Item must be an access group");
597 return ParallelAccessGroups.count(AG);
598 }
599
600 for (const MDOperand &AccessListItem : AG->operands()) {
601 MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
602 assert(isValidAsAccessGroup(AccGroup) &&
603 "List item must be an access group");
604 if (ParallelAccessGroups.count(AccGroup))
605 return true;
606 }
607 return false;
608 };
609
610 if (ContainsAccessGroup(AccessGroup))
611 continue;
612 }
613
614 // The memory instruction can refer to the loop identifier metadata
615 // directly or indirectly through another list metadata (in case of
616 // nested parallel loops). The loop identifier metadata refers to
617 // itself so we can check both cases with the same routine.
618 MDNode *LoopIdMD =
619 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
620
621 if (!LoopIdMD)
622 return false;
623
624 if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
625 return false;
626 }
627 }
628 return true;
629 }
630
getStartLoc() const631 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
632
getLocRange() const633 Loop::LocRange Loop::getLocRange() const {
634 // If we have a debug location in the loop ID, then use it.
635 if (MDNode *LoopID = getLoopID()) {
636 DebugLoc Start;
637 // We use the first DebugLoc in the header as the start location of the loop
638 // and if there is a second DebugLoc in the header we use it as end location
639 // of the loop.
640 for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
641 if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
642 if (!Start)
643 Start = DebugLoc(L);
644 else
645 return LocRange(Start, DebugLoc(L));
646 }
647 }
648
649 if (Start)
650 return LocRange(Start);
651 }
652
653 // Try the pre-header first.
654 if (BasicBlock *PHeadBB = getLoopPreheader())
655 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
656 return LocRange(DL);
657
658 // If we have no pre-header or there are no instructions with debug
659 // info in it, try the header.
660 if (BasicBlock *HeadBB = getHeader())
661 return LocRange(HeadBB->getTerminator()->getDebugLoc());
662
663 return LocRange();
664 }
665
666 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const667 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
668
dumpVerbose() const669 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
670 print(dbgs(), /*Verbose=*/true);
671 }
672 #endif
673
674 //===----------------------------------------------------------------------===//
675 // UnloopUpdater implementation
676 //
677
678 namespace {
679 /// Find the new parent loop for all blocks within the "unloop" whose last
680 /// backedges has just been removed.
681 class UnloopUpdater {
682 Loop &Unloop;
683 LoopInfo *LI;
684
685 LoopBlocksDFS DFS;
686
687 // Map unloop's immediate subloops to their nearest reachable parents. Nested
688 // loops within these subloops will not change parents. However, an immediate
689 // subloop's new parent will be the nearest loop reachable from either its own
690 // exits *or* any of its nested loop's exits.
691 DenseMap<Loop *, Loop *> SubloopParents;
692
693 // Flag the presence of an irreducible backedge whose destination is a block
694 // directly contained by the original unloop.
695 bool FoundIB = false;
696
697 public:
UnloopUpdater(Loop * UL,LoopInfo * LInfo)698 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {}
699
700 void updateBlockParents();
701
702 void removeBlocksFromAncestors();
703
704 void updateSubloopParents();
705
706 protected:
707 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
708 };
709 } // end anonymous namespace
710
711 /// Update the parent loop for all blocks that are directly contained within the
712 /// original "unloop".
updateBlockParents()713 void UnloopUpdater::updateBlockParents() {
714 if (Unloop.getNumBlocks()) {
715 // Perform a post order CFG traversal of all blocks within this loop,
716 // propagating the nearest loop from successors to predecessors.
717 LoopBlocksTraversal Traversal(DFS, LI);
718 for (BasicBlock *POI : Traversal) {
719
720 Loop *L = LI->getLoopFor(POI);
721 Loop *NL = getNearestLoop(POI, L);
722
723 if (NL != L) {
724 // For reducible loops, NL is now an ancestor of Unloop.
725 assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
726 "uninitialized successor");
727 LI->changeLoopFor(POI, NL);
728 } else {
729 // Or the current block is part of a subloop, in which case its parent
730 // is unchanged.
731 assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
732 }
733 }
734 }
735 // Each irreducible loop within the unloop induces a round of iteration using
736 // the DFS result cached by Traversal.
737 bool Changed = FoundIB;
738 for (unsigned NIters = 0; Changed; ++NIters) {
739 assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
740 (void)NIters;
741
742 // Iterate over the postorder list of blocks, propagating the nearest loop
743 // from successors to predecessors as before.
744 Changed = false;
745 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
746 POE = DFS.endPostorder();
747 POI != POE; ++POI) {
748
749 Loop *L = LI->getLoopFor(*POI);
750 Loop *NL = getNearestLoop(*POI, L);
751 if (NL != L) {
752 assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
753 "uninitialized successor");
754 LI->changeLoopFor(*POI, NL);
755 Changed = true;
756 }
757 }
758 }
759 }
760
761 /// Remove unloop's blocks from all ancestors below their new parents.
removeBlocksFromAncestors()762 void UnloopUpdater::removeBlocksFromAncestors() {
763 // Remove all unloop's blocks (including those in nested subloops) from
764 // ancestors below the new parent loop.
765 for (BasicBlock *BB : Unloop.blocks()) {
766 Loop *OuterParent = LI->getLoopFor(BB);
767 if (Unloop.contains(OuterParent)) {
768 while (OuterParent->getParentLoop() != &Unloop)
769 OuterParent = OuterParent->getParentLoop();
770 OuterParent = SubloopParents[OuterParent];
771 }
772 // Remove blocks from former Ancestors except Unloop itself which will be
773 // deleted.
774 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
775 OldParent = OldParent->getParentLoop()) {
776 assert(OldParent && "new loop is not an ancestor of the original");
777 OldParent->removeBlockFromLoop(BB);
778 }
779 }
780 }
781
782 /// Update the parent loop for all subloops directly nested within unloop.
updateSubloopParents()783 void UnloopUpdater::updateSubloopParents() {
784 while (!Unloop.isInnermost()) {
785 Loop *Subloop = *std::prev(Unloop.end());
786 Unloop.removeChildLoop(std::prev(Unloop.end()));
787
788 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
789 if (Loop *Parent = SubloopParents[Subloop])
790 Parent->addChildLoop(Subloop);
791 else
792 LI->addTopLevelLoop(Subloop);
793 }
794 }
795
796 /// Return the nearest parent loop among this block's successors. If a successor
797 /// is a subloop header, consider its parent to be the nearest parent of the
798 /// subloop's exits.
799 ///
800 /// For subloop blocks, simply update SubloopParents and return NULL.
getNearestLoop(BasicBlock * BB,Loop * BBLoop)801 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
802
803 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
804 // is considered uninitialized.
805 Loop *NearLoop = BBLoop;
806
807 Loop *Subloop = nullptr;
808 if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
809 Subloop = NearLoop;
810 // Find the subloop ancestor that is directly contained within Unloop.
811 while (Subloop->getParentLoop() != &Unloop) {
812 Subloop = Subloop->getParentLoop();
813 assert(Subloop && "subloop is not an ancestor of the original loop");
814 }
815 // Get the current nearest parent of the Subloop exits, initially Unloop.
816 NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
817 }
818
819 succ_iterator I = succ_begin(BB), E = succ_end(BB);
820 if (I == E) {
821 assert(!Subloop && "subloop blocks must have a successor");
822 NearLoop = nullptr; // unloop blocks may now exit the function.
823 }
824 for (; I != E; ++I) {
825 if (*I == BB)
826 continue; // self loops are uninteresting
827
828 Loop *L = LI->getLoopFor(*I);
829 if (L == &Unloop) {
830 // This successor has not been processed. This path must lead to an
831 // irreducible backedge.
832 assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
833 FoundIB = true;
834 }
835 if (L != &Unloop && Unloop.contains(L)) {
836 // Successor is in a subloop.
837 if (Subloop)
838 continue; // Branching within subloops. Ignore it.
839
840 // BB branches from the original into a subloop header.
841 assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
842
843 // Get the current nearest parent of the Subloop's exits.
844 L = SubloopParents[L];
845 // L could be Unloop if the only exit was an irreducible backedge.
846 }
847 if (L == &Unloop) {
848 continue;
849 }
850 // Handle critical edges from Unloop into a sibling loop.
851 if (L && !L->contains(&Unloop)) {
852 L = L->getParentLoop();
853 }
854 // Remember the nearest parent loop among successors or subloop exits.
855 if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
856 NearLoop = L;
857 }
858 if (Subloop) {
859 SubloopParents[Subloop] = NearLoop;
860 return BBLoop;
861 }
862 return NearLoop;
863 }
864
LoopInfo(const DomTreeBase<BasicBlock> & DomTree)865 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
866
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator &)867 bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
868 FunctionAnalysisManager::Invalidator &) {
869 // Check whether the analysis, all analyses on functions, or the function's
870 // CFG have been preserved.
871 auto PAC = PA.getChecker<LoopAnalysis>();
872 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
873 PAC.preservedSet<CFGAnalyses>());
874 }
875
erase(Loop * Unloop)876 void LoopInfo::erase(Loop *Unloop) {
877 assert(!Unloop->isInvalid() && "Loop has already been erased!");
878
879 auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
880
881 // First handle the special case of no parent loop to simplify the algorithm.
882 if (Unloop->isOutermost()) {
883 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
884 for (BasicBlock *BB : Unloop->blocks()) {
885 // Don't reparent blocks in subloops.
886 if (getLoopFor(BB) != Unloop)
887 continue;
888
889 // Blocks no longer have a parent but are still referenced by Unloop until
890 // the Unloop object is deleted.
891 changeLoopFor(BB, nullptr);
892 }
893
894 // Remove the loop from the top-level LoopInfo object.
895 for (iterator I = begin();; ++I) {
896 assert(I != end() && "Couldn't find loop");
897 if (*I == Unloop) {
898 removeLoop(I);
899 break;
900 }
901 }
902
903 // Move all of the subloops to the top-level.
904 while (!Unloop->isInnermost())
905 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
906
907 return;
908 }
909
910 // Update the parent loop for all blocks within the loop. Blocks within
911 // subloops will not change parents.
912 UnloopUpdater Updater(Unloop, this);
913 Updater.updateBlockParents();
914
915 // Remove blocks from former ancestor loops.
916 Updater.removeBlocksFromAncestors();
917
918 // Add direct subloops as children in their new parent loop.
919 Updater.updateSubloopParents();
920
921 // Remove unloop from its parent loop.
922 Loop *ParentLoop = Unloop->getParentLoop();
923 for (Loop::iterator I = ParentLoop->begin();; ++I) {
924 assert(I != ParentLoop->end() && "Couldn't find loop");
925 if (*I == Unloop) {
926 ParentLoop->removeChildLoop(I);
927 break;
928 }
929 }
930 }
931
wouldBeOutOfLoopUseRequiringLCSSA(const Value * V,const BasicBlock * ExitBB) const932 bool LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(
933 const Value *V, const BasicBlock *ExitBB) const {
934 if (V->getType()->isTokenTy())
935 // We can't form PHIs of token type, so the definition of LCSSA excludes
936 // values of that type.
937 return false;
938
939 const Instruction *I = dyn_cast<Instruction>(V);
940 if (!I)
941 return false;
942 const Loop *L = getLoopFor(I->getParent());
943 if (!L)
944 return false;
945 if (L->contains(ExitBB))
946 // Could be an exit bb of a subloop and contained in defining loop
947 return false;
948
949 // We found a (new) out-of-loop use location, for a value defined in-loop.
950 // (Note that because of LCSSA, we don't have to account for values defined
951 // in sibling loops. Such values will have LCSSA phis of their own in the
952 // common parent loop.)
953 return true;
954 }
955
956 AnalysisKey LoopAnalysis::Key;
957
run(Function & F,FunctionAnalysisManager & AM)958 LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
959 // FIXME: Currently we create a LoopInfo from scratch for every function.
960 // This may prove to be too wasteful due to deallocating and re-allocating
961 // memory each time for the underlying map and vector datastructures. At some
962 // point it may prove worthwhile to use a freelist and recycle LoopInfo
963 // objects. I don't want to add that kind of complexity until the scope of
964 // the problem is better understood.
965 LoopInfo LI;
966 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
967 return LI;
968 }
969
run(Function & F,FunctionAnalysisManager & AM)970 PreservedAnalyses LoopPrinterPass::run(Function &F,
971 FunctionAnalysisManager &AM) {
972 auto &LI = AM.getResult<LoopAnalysis>(F);
973 OS << "Loop info for function '" << F.getName() << "':\n";
974 LI.print(OS);
975 return PreservedAnalyses::all();
976 }
977
printLoop(Loop & L,raw_ostream & OS,const std::string & Banner)978 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
979
980 if (forcePrintModuleIR()) {
981 // handling -print-module-scope
982 OS << Banner << " (loop: ";
983 L.getHeader()->printAsOperand(OS, false);
984 OS << ")\n";
985
986 // printing whole module
987 OS << *L.getHeader()->getModule();
988 return;
989 }
990
991 OS << Banner;
992
993 auto *PreHeader = L.getLoopPreheader();
994 if (PreHeader) {
995 OS << "\n; Preheader:";
996 PreHeader->print(OS);
997 OS << "\n; Loop:";
998 }
999
1000 for (auto *Block : L.blocks())
1001 if (Block)
1002 Block->print(OS);
1003 else
1004 OS << "Printing <null> block";
1005
1006 SmallVector<BasicBlock *, 8> ExitBlocks;
1007 L.getExitBlocks(ExitBlocks);
1008 if (!ExitBlocks.empty()) {
1009 OS << "\n; Exit blocks";
1010 for (auto *Block : ExitBlocks)
1011 if (Block)
1012 Block->print(OS);
1013 else
1014 OS << "Printing <null> block";
1015 }
1016 }
1017
findOptionMDForLoopID(MDNode * LoopID,StringRef Name)1018 MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
1019 // No loop metadata node, no loop properties.
1020 if (!LoopID)
1021 return nullptr;
1022
1023 // First operand should refer to the metadata node itself, for legacy reasons.
1024 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1025 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1026
1027 // Iterate over the metdata node operands and look for MDString metadata.
1028 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1029 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1030 if (!MD || MD->getNumOperands() < 1)
1031 continue;
1032 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1033 if (!S)
1034 continue;
1035 // Return the operand node if MDString holds expected metadata.
1036 if (Name.equals(S->getString()))
1037 return MD;
1038 }
1039
1040 // Loop property not found.
1041 return nullptr;
1042 }
1043
findOptionMDForLoop(const Loop * TheLoop,StringRef Name)1044 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
1045 return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1046 }
1047
1048 /// Find string metadata for loop
1049 ///
1050 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1051 /// operand or null otherwise. If the string metadata is not found return
1052 /// Optional's not-a-value.
1053 std::optional<const MDOperand *>
findStringMetadataForLoop(const Loop * TheLoop,StringRef Name)1054 llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) {
1055 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1056 if (!MD)
1057 return std::nullopt;
1058 switch (MD->getNumOperands()) {
1059 case 1:
1060 return nullptr;
1061 case 2:
1062 return &MD->getOperand(1);
1063 default:
1064 llvm_unreachable("loop metadata has 0 or 1 operand");
1065 }
1066 }
1067
getOptionalBoolLoopAttribute(const Loop * TheLoop,StringRef Name)1068 std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop,
1069 StringRef Name) {
1070 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1071 if (!MD)
1072 return std::nullopt;
1073 switch (MD->getNumOperands()) {
1074 case 1:
1075 // When the value is absent it is interpreted as 'attribute set'.
1076 return true;
1077 case 2:
1078 if (ConstantInt *IntMD =
1079 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
1080 return IntMD->getZExtValue();
1081 return true;
1082 }
1083 llvm_unreachable("unexpected number of options");
1084 }
1085
getBooleanLoopAttribute(const Loop * TheLoop,StringRef Name)1086 bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
1087 return getOptionalBoolLoopAttribute(TheLoop, Name).value_or(false);
1088 }
1089
getOptionalIntLoopAttribute(const Loop * TheLoop,StringRef Name)1090 std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
1091 StringRef Name) {
1092 const MDOperand *AttrMD =
1093 findStringMetadataForLoop(TheLoop, Name).value_or(nullptr);
1094 if (!AttrMD)
1095 return std::nullopt;
1096
1097 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
1098 if (!IntMD)
1099 return std::nullopt;
1100
1101 return IntMD->getSExtValue();
1102 }
1103
getIntLoopAttribute(const Loop * TheLoop,StringRef Name,int Default)1104 int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name,
1105 int Default) {
1106 return getOptionalIntLoopAttribute(TheLoop, Name).value_or(Default);
1107 }
1108
isFinite(const Loop * L)1109 bool llvm::isFinite(const Loop *L) {
1110 return L->getHeader()->getParent()->willReturn();
1111 }
1112
1113 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1114
hasMustProgress(const Loop * L)1115 bool llvm::hasMustProgress(const Loop *L) {
1116 return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
1117 }
1118
isMustProgress(const Loop * L)1119 bool llvm::isMustProgress(const Loop *L) {
1120 return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1121 }
1122
isValidAsAccessGroup(MDNode * Node)1123 bool llvm::isValidAsAccessGroup(MDNode *Node) {
1124 return Node->getNumOperands() == 0 && Node->isDistinct();
1125 }
1126
makePostTransformationMetadata(LLVMContext & Context,MDNode * OrigLoopID,ArrayRef<StringRef> RemovePrefixes,ArrayRef<MDNode * > AddAttrs)1127 MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
1128 MDNode *OrigLoopID,
1129 ArrayRef<StringRef> RemovePrefixes,
1130 ArrayRef<MDNode *> AddAttrs) {
1131 // First remove any existing loop metadata related to this transformation.
1132 SmallVector<Metadata *, 4> MDs;
1133
1134 // Reserve first location for self reference to the LoopID metadata node.
1135 MDs.push_back(nullptr);
1136
1137 // Remove metadata for the transformation that has been applied or that became
1138 // outdated.
1139 if (OrigLoopID) {
1140 for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1141 bool IsVectorMetadata = false;
1142 Metadata *Op = OrigLoopID->getOperand(i);
1143 if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1144 const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1145 if (S)
1146 IsVectorMetadata =
1147 llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1148 return S->getString().starts_with(Prefix);
1149 });
1150 }
1151 if (!IsVectorMetadata)
1152 MDs.push_back(Op);
1153 }
1154 }
1155
1156 // Add metadata to avoid reapplying a transformation, such as
1157 // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1158 MDs.append(AddAttrs.begin(), AddAttrs.end());
1159
1160 MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1161 // Replace the temporary node with a self-reference.
1162 NewLoopID->replaceOperandWith(0, NewLoopID);
1163 return NewLoopID;
1164 }
1165
1166 //===----------------------------------------------------------------------===//
1167 // LoopInfo implementation
1168 //
1169
LoopInfoWrapperPass()1170 LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) {
1171 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1172 }
1173
1174 char LoopInfoWrapperPass::ID = 0;
1175 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1176 true, true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)1177 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1178 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1179 true, true)
1180
1181 bool LoopInfoWrapperPass::runOnFunction(Function &) {
1182 releaseMemory();
1183 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1184 return false;
1185 }
1186
verifyAnalysis() const1187 void LoopInfoWrapperPass::verifyAnalysis() const {
1188 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1189 // function each time verifyAnalysis is called is very expensive. The
1190 // -verify-loop-info option can enable this. In order to perform some
1191 // checking by default, LoopPass has been taught to call verifyLoop manually
1192 // during loop pass sequences.
1193 if (VerifyLoopInfo) {
1194 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1195 LI.verify(DT);
1196 }
1197 }
1198
getAnalysisUsage(AnalysisUsage & AU) const1199 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1200 AU.setPreservesAll();
1201 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1202 }
1203
print(raw_ostream & OS,const Module *) const1204 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
1205 LI.print(OS);
1206 }
1207
run(Function & F,FunctionAnalysisManager & AM)1208 PreservedAnalyses LoopVerifierPass::run(Function &F,
1209 FunctionAnalysisManager &AM) {
1210 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1211 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1212 LI.verify(DT);
1213 return PreservedAnalyses::all();
1214 }
1215
1216 //===----------------------------------------------------------------------===//
1217 // LoopBlocksDFS implementation
1218 //
1219
1220 /// Traverse the loop blocks and store the DFS result.
1221 /// Useful for clients that just want the final DFS result and don't need to
1222 /// visit blocks during the initial traversal.
perform(const LoopInfo * LI)1223 void LoopBlocksDFS::perform(const LoopInfo *LI) {
1224 LoopBlocksTraversal Traversal(*this, LI);
1225 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1226 POE = Traversal.end();
1227 POI != POE; ++POI)
1228 ;
1229 }
1230