LLVM  14.0.0git
LoopInfo.cpp
Go to the documentation of this file.
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"
18 #include "llvm/ADT/ScopeExit.h"
19 #include "llvm/ADT/SmallPtrSet.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"
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"
41 #include "llvm/Support/Debug.h"
43 #include <algorithm>
44 using namespace llvm;
45 
46 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
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
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 
64 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 
71  return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
72 }
73 
74 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 
81 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;
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(),
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 
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 
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.
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.
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 
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 
231 
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)
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
272 }
273 
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 
288  if (PHINode *IndVar = getInductionVariable(SE))
289  return LoopBounds::getBounds(*this, *IndVar, SE);
290 
291  return None;
292 }
293 
295  if (!isLoopSimplifyForm())
296  return nullptr;
297 
298  BasicBlock *Header = getHeader();
299  assert(Header && "Expected a valid loop header");
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 
333  InductionDescriptor &IndDesc) const {
334  if (PHINode *IndVar = getInductionVariable(SE))
335  return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
336 
337  return false;
338 }
339 
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 
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 
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'
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 
461 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 
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 
479  // Normal-form loops have a preheader, a single backedge, and all of their
480  // exits have all their predecessors inside the loop.
482 }
483 
484 // Routines that reform the loop CFG and split edges often fail on indirectbr.
485 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 
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 
527 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 
541 
542  MDNode *DisableUnrollMD =
543  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
544  MDNode *LoopID = getLoopID();
546  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
547  setLoopID(NewLoopID);
548 }
549 
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 
567  MDNode *DesiredLoopIdMetadata = getLoopID();
568 
569  if (!DesiredLoopIdMetadata)
570  return false;
571 
572  MDNode *ParallelAccesses =
573  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
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 
634 
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)
669 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
670 
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:
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".
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.
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.
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.
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 
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 
867 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
868 
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 
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
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 
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;
970  return LI;
971 }
972 
975  AM.getResult<LoopAnalysis>(F).print(OS);
976  return PreservedAnalyses::all();
977 }
978 
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 
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 
1046  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1047 }
1048 
1049 /// Find string metadata for loop
1050 ///
1051 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1052 /// operand or null otherwise. If the string metadata is not found return
1053 /// Optional's not-a-value.
1055  StringRef Name) {
1056  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1057  if (!MD)
1058  return None;
1059  switch (MD->getNumOperands()) {
1060  case 1:
1061  return nullptr;
1062  case 2:
1063  return &MD->getOperand(1);
1064  default:
1065  llvm_unreachable("loop metadata has 0 or 1 operand");
1066  }
1067 }
1068 
1070  StringRef Name) {
1071  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1072  if (!MD)
1073  return None;
1074  switch (MD->getNumOperands()) {
1075  case 1:
1076  // When the value is absent it is interpreted as 'attribute set'.
1077  return true;
1078  case 2:
1079  if (ConstantInt *IntMD =
1080  mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
1081  return IntMD->getZExtValue();
1082  return true;
1083  }
1084  llvm_unreachable("unexpected number of options");
1085 }
1086 
1088  return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
1089 }
1090 
1092  StringRef Name) {
1093  const MDOperand *AttrMD =
1094  findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
1095  if (!AttrMD)
1096  return None;
1097 
1098  ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
1099  if (!IntMD)
1100  return None;
1101 
1102  return IntMD->getSExtValue();
1103 }
1104 
1106  int Default) {
1107  return getOptionalIntLoopAttribute(TheLoop, Name).getValueOr(Default);
1108 }
1109 
1110 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1111 
1112 bool llvm::hasMustProgress(const Loop *L) {
1114 }
1115 
1116 bool llvm::isMustProgress(const Loop *L) {
1117  return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1118 }
1119 
1121  return Node->getNumOperands() == 0 && Node->isDistinct();
1122 }
1123 
1125  MDNode *OrigLoopID,
1126  ArrayRef<StringRef> RemovePrefixes,
1127  ArrayRef<MDNode *> AddAttrs) {
1128  // First remove any existing loop metadata related to this transformation.
1130 
1131  // Reserve first location for self reference to the LoopID metadata node.
1132  MDs.push_back(nullptr);
1133 
1134  // Remove metadata for the transformation that has been applied or that became
1135  // outdated.
1136  if (OrigLoopID) {
1137  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1138  bool IsVectorMetadata = false;
1139  Metadata *Op = OrigLoopID->getOperand(i);
1140  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1141  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1142  if (S)
1143  IsVectorMetadata =
1144  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1145  return S->getString().startswith(Prefix);
1146  });
1147  }
1148  if (!IsVectorMetadata)
1149  MDs.push_back(Op);
1150  }
1151  }
1152 
1153  // Add metadata to avoid reapplying a transformation, such as
1154  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1155  MDs.append(AddAttrs.begin(), AddAttrs.end());
1156 
1157  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1158  // Replace the temporary node with a self-reference.
1159  NewLoopID->replaceOperandWith(0, NewLoopID);
1160  return NewLoopID;
1161 }
1162 
1163 //===----------------------------------------------------------------------===//
1164 // LoopInfo implementation
1165 //
1166 
1169 }
1170 
1171 char LoopInfoWrapperPass::ID = 0;
1172 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1173  true, true)
1177 
1179  releaseMemory();
1180  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1181  return false;
1182 }
1183 
1185  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1186  // function each time verifyAnalysis is called is very expensive. The
1187  // -verify-loop-info option can enable this. In order to perform some
1188  // checking by default, LoopPass has been taught to call verifyLoop manually
1189  // during loop pass sequences.
1190  if (VerifyLoopInfo) {
1191  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1192  LI.verify(DT);
1193  }
1194 }
1195 
1197  AU.setPreservesAll();
1199 }
1200 
1202  LI.print(OS);
1203 }
1204 
1207  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1208  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1209  LI.verify(DT);
1210  return PreservedAnalyses::all();
1211 }
1212 
1213 //===----------------------------------------------------------------------===//
1214 // LoopBlocksDFS implementation
1215 //
1216 
1217 /// Traverse the loop blocks and store the DFS result.
1218 /// Useful for clients that just want the final DFS result and don't need to
1219 /// visit blocks during the initial traversal.
1221  LoopBlocksTraversal Traversal(*this, LI);
1222  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1223  POE = Traversal.end();
1224  POI != POE; ++POI)
1225  ;
1226 }
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::initializeLoopInfoWrapperPassPass
void initializeLoopInfoWrapperPassPass(PassRegistry &)
llvm::LoopBlocksTraversal
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:836
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:491
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::Loop::getLatchCmpInst
ICmpInst * getLatchCmpInst() const
Get the latch condition instruction.
Definition: LoopInfo.cpp:174
llvm::LoopVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:1205
llvm::LoopBase< BasicBlock, Loop >::getUniqueExitBlock
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:138
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4589
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:164
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:459
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::LoopBase< BasicBlock, Loop >::contains
bool contains(const Loop *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::LoopInfo::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: LoopInfo.cpp:869
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:689
LoopInfoImpl.h
llvm::LoopBase< BasicBlock, Loop >
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:633
llvm::VerifyLoopInfo
bool VerifyLoopInfo
Enable verification of loop info.
Definition: LoopInfo.cpp:54
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:366
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::LoopInfoBase::print
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:620
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::InductionDescriptor::getInductionOpcode
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Definition: IVDescriptors.h:328
llvm::Loop::dumpVerbose
void dumpVerbose() const
Definition: LoopInfo.cpp:671
llvm::CmpInst::getFlippedStrictnessPredicate
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:902
llvm::getIntLoopAttribute
int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1105
Information
Natural Loop Information
Definition: LoopInfo.cpp:1175
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
startswith
static bool startswith(StringRef Magic, const char(&S)[N])
Definition: Magic.cpp:30
NL
#define NL
Definition: DetailedRecordsBackend.cpp:30
llvm::InductionDescriptor::getInductionBinOp
BinaryOperator * getInductionBinOp() const
Definition: IVDescriptors.h:286
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1268
findFinalIVValue
static Value * findFinalIVValue(const Loop &L, const PHINode &IndVar, const Instruction &StepInst)
Return the final value of the loop induction variable if found.
Definition: LoopInfo.cpp:184
llvm::LoopInfo::LoopInfo
LoopInfo()
Definition: LoopInfo.h:1092
llvm::Loop::isCanonical
bool isCanonical(ScalarEvolution &SE) const
Return true if the loop induction variable starts at zero and increments by one each time through the...
Definition: LoopInfo.cpp:410
llvm::Optional
Definition: APInt.h:33
llvm::LoopBase< BasicBlock, Loop >::begin
iterator begin() const
Definition: LoopInfo.h:154
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::LoopBlocksTraversal::end
POTIterator end()
Definition: LoopIterator.h:221
llvm::findOptionMDForLoopID
MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)
Find and return the loop attribute node for the attribute Name in LoopID.
Definition: LoopInfo.cpp:1019
loops
loops
Definition: LoopInfo.cpp:1175
DepthFirstIterator.h
llvm::LoopInfoWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: LoopInfo.cpp:1196
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1203
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1105
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1113
llvm::Loop::LoopBounds::getBounds
static Optional< Loop::LoopBounds > getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE)
Return the LoopBounds object if.
Definition: LoopInfo.cpp:201
llvm::makePostTransformationMetadata
llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)
Create a new LoopID after the loop has been transformed.
Definition: LoopInfo.cpp:1124
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_END(LoopInfoWrapperPass
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1547
llvm::LoopBase< BasicBlock, Loop >::getLoopLatches
void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:334
llvm::Loop::getInductionDescriptor
bool getInductionDescriptor(ScalarEvolution &SE, InductionDescriptor &IndDesc) const
Get the loop induction descriptor for the loop induction variable.
Definition: LoopInfo.cpp:332
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:269
llvm::Loop::setLoopAlreadyUnrolled
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:539
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:548
llvm::getOptionalIntLoopAttribute
llvm::Optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
Definition: LoopInfo.cpp:1091
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LoopInfoWrapperPass::LoopInfoWrapperPass
LoopInfoWrapperPass()
Definition: LoopInfo.cpp:1167
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::User
Definition: User.h:44
llvm::Loop::isAnnotatedParallel
bool isAnnotatedParallel() const
Returns true if the loop is annotated parallel.
Definition: LoopInfo.cpp:566
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase< BasicBlock, Loop >::end
iterator end() const
Definition: LoopInfo.h:155
llvm::LoopBase< BasicBlock, Loop >::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::getOptionalBoolLoopAttribute
Optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)
Definition: LoopInfo.cpp:1069
false
Definition: StackSlotColoring.cpp:142
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1205
llvm::LoopBlocksTraversal::begin
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2810
llvm::make_scope_exit
LLVM_NODISCARD detail::scope_exit< typename std::decay< Callable >::type > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:58
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:198
llvm::printLoop
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
Definition: LoopInfo.cpp:979
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
IRPrintingPasses.h
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
LLVMLoopMustProgress
static const char * LLVMLoopMustProgress
Definition: LoopInfo.cpp:1110
llvm::isMustProgress
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1116
DebugLoc.h
SmallPtrSet.h
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:144
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:672
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
IVDescriptors.h
PrintPasses.h
llvm::None
const NoneType None
Definition: None.h:23
LoopIterator.h
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:701
llvm::Loop::getLocRange
LocRange getLocRange() const
Return the source code span of the loop.
Definition: LoopInfo.cpp:635
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3141
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1107
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:283
llvm::findStringMetadataForLoop
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopInfo.cpp:1054
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:478
llvm::Optional::getValueOr
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:297
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
isBlockInLCSSAForm
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, const DominatorTree &DT)
Definition: LoopInfo.cpp:430
llvm::pdb::Unknown
@ Unknown
Definition: PDBTypes.h:395
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:244
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopNest::skipEmptyBlockUntil
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
Definition: LoopNestAnalysis.cpp:289
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::Loop::getIncomingAndBackEdge
bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const
Obtain the unique incoming and back edge.
Definition: LoopInfo.cpp:124
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:722
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::Loop::LoopBounds::getDirection
Direction getDirection() const
Get the direction of the loop.
Definition: LoopInfo.cpp:274
llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader
BasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1612
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1220
llvm::MDString::get
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:473
llvm::LoopBase< BasicBlock, Loop >::getLoopLatch
BasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::Loop::LocRange
A range representing the start and end location of a loop.
Definition: LoopInfo.h:533
llvm::LoopBase< BasicBlock, Loop >::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:92
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1024
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::po_iterator
Definition: PostOrderIterator.h:95
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:753
LoopNestAnalysis.h
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:878
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:901
llvm::LoopInfoWrapperPass::print
void print(raw_ostream &O, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: LoopInfo.cpp:1201
llvm::LoopBlocksDFS::POIterator
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::Value::printAsOperand
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4675
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3138
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::LoopBase::removeChildLoop
LoopT * removeChildLoop(iterator I)
This removes the specified child from being a subloop of this loop.
Definition: LoopInfo.h:404
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1554
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Loop::makeLoopInvariant
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
Definition: LoopInfo.cpp:74
llvm::Loop::getCanonicalInductionVariable
PHINode * getCanonicalInductionVariable() const
Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...
Definition: LoopInfo.cpp:150
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::InductionDescriptor::getStep
const SCEV * getStep() const
Definition: IVDescriptors.h:285
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:168
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
llvm::LoopInfoWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: LoopInfo.cpp:1184
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::findOptionMDForLoop
MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for a loop.
Definition: LoopInfo.cpp:1045
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::Loop::hasLoopInvariantOperands
bool hasLoopInvariantOperands(const Instruction *I) const
Return true if all the operands of the specified instruction are loop invariant.
Definition: LoopInfo.cpp:70
llvm::PredIterator
Definition: CFG.h:43
llvm::MDNode::getDistinct
static MDTuple * getDistinct(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1211
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::Init
Definition: Record.h:271
llvm::LoopAnalysis::run
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:961
llvm::Loop::getBounds
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
Definition: LoopInfo.cpp:287
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12612
llvm::Loop::LocRange::getStart
const DebugLoc & getStart() const
Definition: LoopInfo.h:543
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
true
Natural Loop true
Definition: LoopInfo.cpp:1176
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::InductionDescriptor::isInductionPHI
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
Definition: IVDescriptors.cpp:1232
llvm::Loop::LoopBounds
Below are some utilities to get the loop guard, loop bounds and induction variable,...
Definition: LoopInfo.h:638
llvm::isValidAsAccessGroup
bool isValidAsAccessGroup(MDNode *AccGroup)
Return whether an MDNode might represent an access group.
Definition: LoopInfo.cpp:1120
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::Loop::setLoopID
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:527
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:461
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Loop::isAuxiliaryInductionVariable
bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const
Return true if the given PHINode AuxIndVar is.
Definition: LoopInfo.cpp:340
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:153
llvm::LoopInfoBase< BasicBlock, Loop >
llvm::Loop::LoopBounds::getCanonicalPredicate
ICmpInst::Predicate getCanonicalPredicate() const
Return the canonical predicate for the latch compare instruction, if able to be calcuated.
Definition: LoopInfo.cpp:232
llvm::LoopBase::isInvalid
bool isInvalid() const
Return true if this loop is no longer valid.
Definition: LoopInfo.h:215
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::Loop::getLoopID
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:503
llvm::MemorySSA::BeforeTerminator
@ BeforeTerminator
Definition: MemorySSA.h:793
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::LoopBase< BasicBlock, Loop >::getHeader
BasicBlock * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::Loop::isRecursivelyLCSSAForm
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:468
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:669
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:626
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::Loop::setLoopMustProgress
void setLoopMustProgress()
Add llvm.loop.mustprogress to this loop's loop id metadata.
Definition: LoopInfo.cpp:550
llvm::MDNode::replaceOperandWith
void replaceOperandWith(unsigned I, Metadata *New)
Replace a specific operand.
Definition: Metadata.cpp:877
ScalarEvolutionExpressions.h
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
MemorySSA.h
Instructions.h
llvm::hasMustProgress
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Definition: LoopInfo.cpp:1112
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:151
Dominators.h
llvm::getBooleanLoopAttribute
bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)
Returns true if Name is applied to TheLoop and enabled.
Definition: LoopInfo.cpp:1087
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::Loop::isSafeToClone
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:485
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
VerifyLoopInfoX
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::Hidden, cl::desc("Verify loop info (time consuming)"))
llvm::PHINode
Definition: Instructions.h:2625
llvm::LoopInfoBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:939
ScopeExit.h
llvm::forcePrintModuleIR
bool forcePrintModuleIR()
Definition: PrintPasses.cpp:81
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::ConstantInt::isOne
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:200
llvm::LoopBase< BasicBlock, Loop >::print
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:384
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Loop::getInductionVariable
PHINode * getInductionVariable(ScalarEvolution &SE) const
Return the loop induction variable if found, else return nullptr.
Definition: LoopInfo.cpp:294
LLVMContext.h
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:788
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:414
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3060
raw_ostream.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::MDOperand::get
Metadata * get() const
Definition: Metadata.h:759
Debug.h
llvm::LoopPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:973
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:154
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3139
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:748
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3153
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA
bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const
Definition: LoopInfo.cpp:935
llvm::LoopInfoWrapperPass::ID
static char ID
Definition: LoopInfo.h:1272
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37