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  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 
334  InductionDescriptor &IndDesc) const {
335  if (PHINode *IndVar = getInductionVariable(SE))
336  return InductionDescriptor::isInductionPHI(IndVar, this, &SE, IndDesc);
337 
338  return false;
339 }
340 
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 
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 
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'
431 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
432  const DominatorTree &DT) {
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 (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 
462 bool Loop::isLCSSAForm(const DominatorTree &DT) 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);
466  });
467 }
468 
470  const LoopInfo &LI) 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);
476  });
477 }
478 
480  // Normal-form loops have a preheader, a single backedge, and all of their
481  // exits have all their predecessors inside the loop.
483 }
484 
485 // Routines that reform the loop CFG and split edges often fail on indirectbr.
486 bool Loop::isSafeToClone() const {
487  // Return false if any loop blocks contain indirectbrs, or there are any calls
488  // to noduplicate functions.
489  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
490  // operand list to reflect the newly cloned labels.
491  for (BasicBlock *BB : this->blocks()) {
492  if (isa<IndirectBrInst>(BB->getTerminator()) ||
493  isa<CallBrInst>(BB->getTerminator()))
494  return false;
495 
496  for (Instruction &I : *BB)
497  if (auto *CB = dyn_cast<CallBase>(&I))
498  if (CB->cannotDuplicate())
499  return false;
500  }
501  return true;
502 }
503 
505  MDNode *LoopID = nullptr;
506 
507  // Go through the latch blocks and check the terminator for the metadata.
508  SmallVector<BasicBlock *, 4> LatchesBlocks;
509  getLoopLatches(LatchesBlocks);
510  for (BasicBlock *BB : LatchesBlocks) {
511  Instruction *TI = BB->getTerminator();
512  MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
513 
514  if (!MD)
515  return nullptr;
516 
517  if (!LoopID)
518  LoopID = MD;
519  else if (MD != LoopID)
520  return nullptr;
521  }
522  if (!LoopID || LoopID->getNumOperands() == 0 ||
523  LoopID->getOperand(0) != LoopID)
524  return nullptr;
525  return LoopID;
526 }
527 
528 void Loop::setLoopID(MDNode *LoopID) const {
529  assert((!LoopID || LoopID->getNumOperands() > 0) &&
530  "Loop ID needs at least one operand");
531  assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
532  "Loop ID should refer to itself");
533 
534  SmallVector<BasicBlock *, 4> LoopLatches;
535  getLoopLatches(LoopLatches);
536  for (BasicBlock *BB : LoopLatches)
537  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
538 }
539 
542 
543  MDNode *DisableUnrollMD =
544  MDNode::get(Context, MDString::get(Context, "llvm.loop.unroll.disable"));
545  MDNode *LoopID = getLoopID();
547  Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});
548  setLoopID(NewLoopID);
549 }
550 
553 
554  MDNode *MustProgress = findOptionMDForLoop(this, "llvm.loop.mustprogress");
555 
556  if (MustProgress)
557  return;
558 
559  MDNode *MustProgressMD =
560  MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
561  MDNode *LoopID = getLoopID();
562  MDNode *NewLoopID =
563  makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
564  setLoopID(NewLoopID);
565 }
566 
568  MDNode *DesiredLoopIdMetadata = getLoopID();
569 
570  if (!DesiredLoopIdMetadata)
571  return false;
572 
573  MDNode *ParallelAccesses =
574  findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
576  ParallelAccessGroups; // For scalable 'contains' check.
577  if (ParallelAccesses) {
578  for (const MDOperand &MD : drop_begin(ParallelAccesses->operands())) {
579  MDNode *AccGroup = cast<MDNode>(MD.get());
580  assert(isValidAsAccessGroup(AccGroup) &&
581  "List item must be an access group");
582  ParallelAccessGroups.insert(AccGroup);
583  }
584  }
585 
586  // The loop branch contains the parallel loop metadata. In order to ensure
587  // that any parallel-loop-unaware optimization pass hasn't added loop-carried
588  // dependencies (thus converted the loop back to a sequential loop), check
589  // that all the memory instructions in the loop belong to an access group that
590  // is parallel to this loop.
591  for (BasicBlock *BB : this->blocks()) {
592  for (Instruction &I : *BB) {
593  if (!I.mayReadOrWriteMemory())
594  continue;
595 
596  if (MDNode *AccessGroup = I.getMetadata(LLVMContext::MD_access_group)) {
597  auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
598  if (AG->getNumOperands() == 0) {
599  assert(isValidAsAccessGroup(AG) && "Item must be an access group");
600  return ParallelAccessGroups.count(AG);
601  }
602 
603  for (const MDOperand &AccessListItem : AG->operands()) {
604  MDNode *AccGroup = cast<MDNode>(AccessListItem.get());
605  assert(isValidAsAccessGroup(AccGroup) &&
606  "List item must be an access group");
607  if (ParallelAccessGroups.count(AccGroup))
608  return true;
609  }
610  return false;
611  };
612 
613  if (ContainsAccessGroup(AccessGroup))
614  continue;
615  }
616 
617  // The memory instruction can refer to the loop identifier metadata
618  // directly or indirectly through another list metadata (in case of
619  // nested parallel loops). The loop identifier metadata refers to
620  // itself so we can check both cases with the same routine.
621  MDNode *LoopIdMD =
622  I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
623 
624  if (!LoopIdMD)
625  return false;
626 
627  if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))
628  return false;
629  }
630  }
631  return true;
632 }
633 
635 
637  // If we have a debug location in the loop ID, then use it.
638  if (MDNode *LoopID = getLoopID()) {
639  DebugLoc Start;
640  // We use the first DebugLoc in the header as the start location of the loop
641  // and if there is a second DebugLoc in the header we use it as end location
642  // of the loop.
643  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
644  if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
645  if (!Start)
646  Start = DebugLoc(L);
647  else
648  return LocRange(Start, DebugLoc(L));
649  }
650  }
651 
652  if (Start)
653  return LocRange(Start);
654  }
655 
656  // Try the pre-header first.
657  if (BasicBlock *PHeadBB = getLoopPreheader())
658  if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
659  return LocRange(DL);
660 
661  // If we have no pre-header or there are no instructions with debug
662  // info in it, try the header.
663  if (BasicBlock *HeadBB = getHeader())
664  return LocRange(HeadBB->getTerminator()->getDebugLoc());
665 
666  return LocRange();
667 }
668 
669 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
670 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
671 
673  print(dbgs(), /*Verbose=*/true);
674 }
675 #endif
676 
677 //===----------------------------------------------------------------------===//
678 // UnloopUpdater implementation
679 //
680 
681 namespace {
682 /// Find the new parent loop for all blocks within the "unloop" whose last
683 /// backedges has just been removed.
684 class UnloopUpdater {
685  Loop &Unloop;
686  LoopInfo *LI;
687 
688  LoopBlocksDFS DFS;
689 
690  // Map unloop's immediate subloops to their nearest reachable parents. Nested
691  // loops within these subloops will not change parents. However, an immediate
692  // subloop's new parent will be the nearest loop reachable from either its own
693  // exits *or* any of its nested loop's exits.
694  DenseMap<Loop *, Loop *> SubloopParents;
695 
696  // Flag the presence of an irreducible backedge whose destination is a block
697  // directly contained by the original unloop.
698  bool FoundIB;
699 
700 public:
701  UnloopUpdater(Loop *UL, LoopInfo *LInfo)
702  : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
703 
704  void updateBlockParents();
705 
706  void removeBlocksFromAncestors();
707 
708  void updateSubloopParents();
709 
710 protected:
711  Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
712 };
713 } // end anonymous namespace
714 
715 /// Update the parent loop for all blocks that are directly contained within the
716 /// original "unloop".
717 void UnloopUpdater::updateBlockParents() {
718  if (Unloop.getNumBlocks()) {
719  // Perform a post order CFG traversal of all blocks within this loop,
720  // propagating the nearest loop from successors to predecessors.
721  LoopBlocksTraversal Traversal(DFS, LI);
722  for (BasicBlock *POI : Traversal) {
723 
724  Loop *L = LI->getLoopFor(POI);
725  Loop *NL = getNearestLoop(POI, L);
726 
727  if (NL != L) {
728  // For reducible loops, NL is now an ancestor of Unloop.
729  assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
730  "uninitialized successor");
731  LI->changeLoopFor(POI, NL);
732  } else {
733  // Or the current block is part of a subloop, in which case its parent
734  // is unchanged.
735  assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
736  }
737  }
738  }
739  // Each irreducible loop within the unloop induces a round of iteration using
740  // the DFS result cached by Traversal.
741  bool Changed = FoundIB;
742  for (unsigned NIters = 0; Changed; ++NIters) {
743  assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
744 
745  // Iterate over the postorder list of blocks, propagating the nearest loop
746  // from successors to predecessors as before.
747  Changed = false;
748  for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
749  POE = DFS.endPostorder();
750  POI != POE; ++POI) {
751 
752  Loop *L = LI->getLoopFor(*POI);
753  Loop *NL = getNearestLoop(*POI, L);
754  if (NL != L) {
755  assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
756  "uninitialized successor");
757  LI->changeLoopFor(*POI, NL);
758  Changed = true;
759  }
760  }
761  }
762 }
763 
764 /// Remove unloop's blocks from all ancestors below their new parents.
765 void UnloopUpdater::removeBlocksFromAncestors() {
766  // Remove all unloop's blocks (including those in nested subloops) from
767  // ancestors below the new parent loop.
768  for (BasicBlock *BB : Unloop.blocks()) {
769  Loop *OuterParent = LI->getLoopFor(BB);
770  if (Unloop.contains(OuterParent)) {
771  while (OuterParent->getParentLoop() != &Unloop)
772  OuterParent = OuterParent->getParentLoop();
773  OuterParent = SubloopParents[OuterParent];
774  }
775  // Remove blocks from former Ancestors except Unloop itself which will be
776  // deleted.
777  for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
778  OldParent = OldParent->getParentLoop()) {
779  assert(OldParent && "new loop is not an ancestor of the original");
780  OldParent->removeBlockFromLoop(BB);
781  }
782  }
783 }
784 
785 /// Update the parent loop for all subloops directly nested within unloop.
786 void UnloopUpdater::updateSubloopParents() {
787  while (!Unloop.isInnermost()) {
788  Loop *Subloop = *std::prev(Unloop.end());
789  Unloop.removeChildLoop(std::prev(Unloop.end()));
790 
791  assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
792  if (Loop *Parent = SubloopParents[Subloop])
793  Parent->addChildLoop(Subloop);
794  else
795  LI->addTopLevelLoop(Subloop);
796  }
797 }
798 
799 /// Return the nearest parent loop among this block's successors. If a successor
800 /// is a subloop header, consider its parent to be the nearest parent of the
801 /// subloop's exits.
802 ///
803 /// For subloop blocks, simply update SubloopParents and return NULL.
804 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
805 
806  // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
807  // is considered uninitialized.
808  Loop *NearLoop = BBLoop;
809 
810  Loop *Subloop = nullptr;
811  if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
812  Subloop = NearLoop;
813  // Find the subloop ancestor that is directly contained within Unloop.
814  while (Subloop->getParentLoop() != &Unloop) {
815  Subloop = Subloop->getParentLoop();
816  assert(Subloop && "subloop is not an ancestor of the original loop");
817  }
818  // Get the current nearest parent of the Subloop exits, initially Unloop.
819  NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
820  }
821 
823  if (I == E) {
824  assert(!Subloop && "subloop blocks must have a successor");
825  NearLoop = nullptr; // unloop blocks may now exit the function.
826  }
827  for (; I != E; ++I) {
828  if (*I == BB)
829  continue; // self loops are uninteresting
830 
831  Loop *L = LI->getLoopFor(*I);
832  if (L == &Unloop) {
833  // This successor has not been processed. This path must lead to an
834  // irreducible backedge.
835  assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
836  FoundIB = true;
837  }
838  if (L != &Unloop && Unloop.contains(L)) {
839  // Successor is in a subloop.
840  if (Subloop)
841  continue; // Branching within subloops. Ignore it.
842 
843  // BB branches from the original into a subloop header.
844  assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
845 
846  // Get the current nearest parent of the Subloop's exits.
847  L = SubloopParents[L];
848  // L could be Unloop if the only exit was an irreducible backedge.
849  }
850  if (L == &Unloop) {
851  continue;
852  }
853  // Handle critical edges from Unloop into a sibling loop.
854  if (L && !L->contains(&Unloop)) {
855  L = L->getParentLoop();
856  }
857  // Remember the nearest parent loop among successors or subloop exits.
858  if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
859  NearLoop = L;
860  }
861  if (Subloop) {
862  SubloopParents[Subloop] = NearLoop;
863  return BBLoop;
864  }
865  return NearLoop;
866 }
867 
868 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
869 
872  // Check whether the analysis, all analyses on functions, or the function's
873  // CFG have been preserved.
874  auto PAC = PA.getChecker<LoopAnalysis>();
875  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
876  PAC.preservedSet<CFGAnalyses>());
877 }
878 
879 void LoopInfo::erase(Loop *Unloop) {
880  assert(!Unloop->isInvalid() && "Loop has already been erased!");
881 
882  auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
883 
884  // First handle the special case of no parent loop to simplify the algorithm.
885  if (Unloop->isOutermost()) {
886  // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
887  for (BasicBlock *BB : Unloop->blocks()) {
888  // Don't reparent blocks in subloops.
889  if (getLoopFor(BB) != Unloop)
890  continue;
891 
892  // Blocks no longer have a parent but are still referenced by Unloop until
893  // the Unloop object is deleted.
894  changeLoopFor(BB, nullptr);
895  }
896 
897  // Remove the loop from the top-level LoopInfo object.
898  for (iterator I = begin();; ++I) {
899  assert(I != end() && "Couldn't find loop");
900  if (*I == Unloop) {
901  removeLoop(I);
902  break;
903  }
904  }
905 
906  // Move all of the subloops to the top-level.
907  while (!Unloop->isInnermost())
908  addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
909 
910  return;
911  }
912 
913  // Update the parent loop for all blocks within the loop. Blocks within
914  // subloops will not change parents.
915  UnloopUpdater Updater(Unloop, this);
916  Updater.updateBlockParents();
917 
918  // Remove blocks from former ancestor loops.
919  Updater.removeBlocksFromAncestors();
920 
921  // Add direct subloops as children in their new parent loop.
922  Updater.updateSubloopParents();
923 
924  // Remove unloop from its parent loop.
925  Loop *ParentLoop = Unloop->getParentLoop();
926  for (Loop::iterator I = ParentLoop->begin();; ++I) {
927  assert(I != ParentLoop->end() && "Couldn't find loop");
928  if (*I == Unloop) {
929  ParentLoop->removeChildLoop(I);
930  break;
931  }
932  }
933 }
934 
935 bool
937  const BasicBlock *ExitBB) const {
938  if (V->getType()->isTokenTy())
939  // We can't form PHIs of token type, so the definition of LCSSA excludes
940  // values of that type.
941  return false;
942 
943  const Instruction *I = dyn_cast<Instruction>(V);
944  if (!I)
945  return false;
946  const Loop *L = getLoopFor(I->getParent());
947  if (!L)
948  return false;
949  if (L->contains(ExitBB))
950  // Could be an exit bb of a subloop and contained in defining loop
951  return false;
952 
953  // We found a (new) out-of-loop use location, for a value defined in-loop.
954  // (Note that because of LCSSA, we don't have to account for values defined
955  // in sibling loops. Such values will have LCSSA phis of their own in the
956  // common parent loop.)
957  return true;
958 }
959 
960 AnalysisKey LoopAnalysis::Key;
961 
963  // FIXME: Currently we create a LoopInfo from scratch for every function.
964  // This may prove to be too wasteful due to deallocating and re-allocating
965  // memory each time for the underlying map and vector datastructures. At some
966  // point it may prove worthwhile to use a freelist and recycle LoopInfo
967  // objects. I don't want to add that kind of complexity until the scope of
968  // the problem is better understood.
969  LoopInfo LI;
971  return LI;
972 }
973 
976  AM.getResult<LoopAnalysis>(F).print(OS);
977  return PreservedAnalyses::all();
978 }
979 
980 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
981 
982  if (forcePrintModuleIR()) {
983  // handling -print-module-scope
984  OS << Banner << " (loop: ";
985  L.getHeader()->printAsOperand(OS, false);
986  OS << ")\n";
987 
988  // printing whole module
989  OS << *L.getHeader()->getModule();
990  return;
991  }
992 
993  OS << Banner;
994 
995  auto *PreHeader = L.getLoopPreheader();
996  if (PreHeader) {
997  OS << "\n; Preheader:";
998  PreHeader->print(OS);
999  OS << "\n; Loop:";
1000  }
1001 
1002  for (auto *Block : L.blocks())
1003  if (Block)
1004  Block->print(OS);
1005  else
1006  OS << "Printing <null> block";
1007 
1008  SmallVector<BasicBlock *, 8> ExitBlocks;
1009  L.getExitBlocks(ExitBlocks);
1010  if (!ExitBlocks.empty()) {
1011  OS << "\n; Exit blocks";
1012  for (auto *Block : ExitBlocks)
1013  if (Block)
1014  Block->print(OS);
1015  else
1016  OS << "Printing <null> block";
1017  }
1018 }
1019 
1021  // No loop metadata node, no loop properties.
1022  if (!LoopID)
1023  return nullptr;
1024 
1025  // First operand should refer to the metadata node itself, for legacy reasons.
1026  assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1027  assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1028 
1029  // Iterate over the metdata node operands and look for MDString metadata.
1030  for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
1031  MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
1032  if (!MD || MD->getNumOperands() < 1)
1033  continue;
1034  MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1035  if (!S)
1036  continue;
1037  // Return the operand node if MDString holds expected metadata.
1038  if (Name.equals(S->getString()))
1039  return MD;
1040  }
1041 
1042  // Loop property not found.
1043  return nullptr;
1044 }
1045 
1047  return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
1048 }
1049 
1050 /// Find string metadata for loop
1051 ///
1052 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1053 /// operand or null otherwise. If the string metadata is not found return
1054 /// Optional's not-a-value.
1056  StringRef Name) {
1057  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1058  if (!MD)
1059  return None;
1060  switch (MD->getNumOperands()) {
1061  case 1:
1062  return nullptr;
1063  case 2:
1064  return &MD->getOperand(1);
1065  default:
1066  llvm_unreachable("loop metadata has 0 or 1 operand");
1067  }
1068 }
1069 
1071  StringRef Name) {
1072  MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1073  if (!MD)
1074  return None;
1075  switch (MD->getNumOperands()) {
1076  case 1:
1077  // When the value is absent it is interpreted as 'attribute set'.
1078  return true;
1079  case 2:
1080  if (ConstantInt *IntMD =
1081  mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
1082  return IntMD->getZExtValue();
1083  return true;
1084  }
1085  llvm_unreachable("unexpected number of options");
1086 }
1087 
1089  return getOptionalBoolLoopAttribute(TheLoop, Name).getValueOr(false);
1090 }
1091 
1093  StringRef Name) {
1094  const MDOperand *AttrMD =
1095  findStringMetadataForLoop(TheLoop, Name).getValueOr(nullptr);
1096  if (!AttrMD)
1097  return None;
1098 
1099  ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
1100  if (!IntMD)
1101  return None;
1102 
1103  return IntMD->getSExtValue();
1104 }
1105 
1107  int Default) {
1108  return getOptionalIntLoopAttribute(TheLoop, Name).getValueOr(Default);
1109 }
1110 
1111 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1112 
1113 bool llvm::hasMustProgress(const Loop *L) {
1115 }
1116 
1117 bool llvm::isMustProgress(const Loop *L) {
1118  return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1119 }
1120 
1122  return Node->getNumOperands() == 0 && Node->isDistinct();
1123 }
1124 
1126  MDNode *OrigLoopID,
1127  ArrayRef<StringRef> RemovePrefixes,
1128  ArrayRef<MDNode *> AddAttrs) {
1129  // First remove any existing loop metadata related to this transformation.
1131 
1132  // Reserve first location for self reference to the LoopID metadata node.
1133  MDs.push_back(nullptr);
1134 
1135  // Remove metadata for the transformation that has been applied or that became
1136  // outdated.
1137  if (OrigLoopID) {
1138  for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
1139  bool IsVectorMetadata = false;
1140  Metadata *Op = OrigLoopID->getOperand(i);
1141  if (MDNode *MD = dyn_cast<MDNode>(Op)) {
1142  const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
1143  if (S)
1144  IsVectorMetadata =
1145  llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
1146  return S->getString().startswith(Prefix);
1147  });
1148  }
1149  if (!IsVectorMetadata)
1150  MDs.push_back(Op);
1151  }
1152  }
1153 
1154  // Add metadata to avoid reapplying a transformation, such as
1155  // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1156  MDs.append(AddAttrs.begin(), AddAttrs.end());
1157 
1158  MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1159  // Replace the temporary node with a self-reference.
1160  NewLoopID->replaceOperandWith(0, NewLoopID);
1161  return NewLoopID;
1162 }
1163 
1164 //===----------------------------------------------------------------------===//
1165 // LoopInfo implementation
1166 //
1167 
1170 }
1171 
1172 char LoopInfoWrapperPass::ID = 0;
1173 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1174  true, true)
1178 
1180  releaseMemory();
1181  LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1182  return false;
1183 }
1184 
1186  // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1187  // function each time verifyAnalysis is called is very expensive. The
1188  // -verify-loop-info option can enable this. In order to perform some
1189  // checking by default, LoopPass has been taught to call verifyLoop manually
1190  // during loop pass sequences.
1191  if (VerifyLoopInfo) {
1192  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1193  LI.verify(DT);
1194  }
1195 }
1196 
1198  AU.setPreservesAll();
1200 }
1201 
1203  LI.print(OS);
1204 }
1205 
1208  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
1209  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1210  LI.verify(DT);
1211  return PreservedAnalyses::all();
1212 }
1213 
1214 //===----------------------------------------------------------------------===//
1215 // LoopBlocksDFS implementation
1216 //
1217 
1218 /// Traverse the loop blocks and store the DFS result.
1219 /// Useful for clients that just want the final DFS result and don't need to
1220 /// visit blocks during the initial traversal.
1222  LoopBlocksTraversal Traversal(*this, LI);
1223  for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1224  POE = Traversal.end();
1225  POI != POE; ++POI)
1226  ;
1227 }
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:851
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:506
llvm
This is an optimization pass for GlobalISel generic memory operations.
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:1206
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:742
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:721
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:4632
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:783
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:62
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:457
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:870
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:690
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:634
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:460
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:367
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:743
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:835
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:621
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:356
llvm::Loop::dumpVerbose
void dumpVerbose() const
Definition: LoopInfo.cpp:672
llvm::CmpInst::getFlippedStrictnessPredicate
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Definition: InstrTypes.h:917
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:1106
Information
Natural Loop Information
Definition: LoopInfo.cpp:1176
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:748
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:314
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:411
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:1020
loops
loops
Definition: LoopInfo.cpp:1176
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:1197
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1233
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1135
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1143
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:1125
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:1600
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:333
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:297
llvm::Loop::setLoopAlreadyUnrolled
void setLoopAlreadyUnrolled()
Add llvm.loop.unroll.disable to this loop's loop id metadata.
Definition: LoopInfo.cpp:540
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:1092
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:1168
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:567
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:1070
false
Definition: StackSlotColoring.cpp:142
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1199
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:2833
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:187
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:980
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:1111
llvm::isMustProgress
bool isMustProgress(const Loop *L)
Return true if this loop can be assumed to make progress.
Definition: LoopInfo.cpp:1117
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:148
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
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:636
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:3164
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4110
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1137
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:311
llvm::findStringMetadataForLoop
Optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)
Find string metadata for loop.
Definition: LoopInfo.cpp:1055
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:479
llvm::Optional::getValueOr
constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION
Definition: Optional.h:297
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1185
isBlockInLCSSAForm
static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, const DominatorTree &DT)
Definition: LoopInfo.cpp:431
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:1665
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1221
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:1137
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:754
LoopNestAnalysis.h
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:879
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:906
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:1202
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:4652
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3161
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:750
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:1607
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
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:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:313
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:276
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:1185
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:1046
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:1241
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:152
llvm::Init
Definition: Record.h:275
llvm::LoopAnalysis::run
LoopInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:962
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:12762
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:36
true
Natural Loop true
Definition: LoopInfo.cpp:1177
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:1345
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:1121
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:528
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
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:325
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:341
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:151
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:504
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:469
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:670
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:616
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:551
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:1113
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:1088
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:486
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:811
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:2648
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:412
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3083
raw_ostream.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MDOperand::get
Metadata * get() const
Definition: Metadata.h:764
Debug.h
llvm::LoopPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopInfo.cpp:974
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3162
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:753
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3176
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:936
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:38