LLVM  15.0.0git
LoopInfoImpl.h
Go to the documentation of this file.
1 //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===//
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 is the generic implementation of LoopInfo used for both Loops and
10 // MachineLoops.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
16 
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetOperations.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/Dominators.h"
22 
23 namespace llvm {
24 
25 //===----------------------------------------------------------------------===//
26 // APIs for simple analysis of the loop. See header notes.
27 
28 /// getExitingBlocks - Return all blocks inside the loop that have successors
29 /// outside of the loop. These are the blocks _inside of the current loop_
30 /// which branch out. The returned list is always unique.
31 ///
32 template <class BlockT, class LoopT>
34  SmallVectorImpl<BlockT *> &ExitingBlocks) const {
35  assert(!isInvalid() && "Loop not in a valid state!");
36  for (const auto BB : blocks())
37  for (auto *Succ : children<BlockT *>(BB))
38  if (!contains(Succ)) {
39  // Not in current loop? It must be an exit block.
40  ExitingBlocks.push_back(BB);
41  break;
42  }
43 }
44 
45 /// getExitingBlock - If getExitingBlocks would return exactly one block,
46 /// return that block. Otherwise return null.
47 template <class BlockT, class LoopT>
49  assert(!isInvalid() && "Loop not in a valid state!");
50  SmallVector<BlockT *, 8> ExitingBlocks;
51  getExitingBlocks(ExitingBlocks);
52  if (ExitingBlocks.size() == 1)
53  return ExitingBlocks[0];
54  return nullptr;
55 }
56 
57 /// getExitBlocks - Return all of the successor blocks of this loop. These
58 /// are the blocks _outside of the current loop_ which are branched to.
59 ///
60 template <class BlockT, class LoopT>
62  SmallVectorImpl<BlockT *> &ExitBlocks) const {
63  assert(!isInvalid() && "Loop not in a valid state!");
64  for (const auto BB : blocks())
65  for (auto *Succ : children<BlockT *>(BB))
66  if (!contains(Succ))
67  // Not in current loop? It must be an exit block.
68  ExitBlocks.push_back(Succ);
69 }
70 
71 template <class BlockT, class LoopT>
73  SmallVector<BlockT *, 8> ExitBlocks;
74  getExitBlocks(ExitBlocks);
75  return ExitBlocks.empty();
76 }
77 
78 /// getExitBlock - If getExitBlocks would return exactly one block,
79 /// return that block. Otherwise return null.
80 template <class BlockT, class LoopT>
82  assert(!isInvalid() && "Loop not in a valid state!");
83  SmallVector<BlockT *, 8> ExitBlocks;
84  getExitBlocks(ExitBlocks);
85  if (ExitBlocks.size() == 1)
86  return ExitBlocks[0];
87  return nullptr;
88 }
89 
90 template <class BlockT, class LoopT>
92  // Each predecessor of each exit block of a normal loop is contained
93  // within the loop.
94  SmallVector<BlockT *, 4> UniqueExitBlocks;
95  getUniqueExitBlocks(UniqueExitBlocks);
96  for (BlockT *EB : UniqueExitBlocks)
97  for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
98  if (!contains(Predecessor))
99  return false;
100  // All the requirements are met.
101  return true;
102 }
103 
104 // Helper function to get unique loop exits. Pred is a predicate pointing to
105 // BasicBlocks in a loop which should be considered to find loop exits.
106 template <class BlockT, class LoopT, typename PredicateT>
107 void getUniqueExitBlocksHelper(const LoopT *L,
108  SmallVectorImpl<BlockT *> &ExitBlocks,
109  PredicateT Pred) {
110  assert(!L->isInvalid() && "Loop not in a valid state!");
112  auto Filtered = make_filter_range(L->blocks(), Pred);
113  for (BlockT *BB : Filtered)
114  for (BlockT *Successor : children<BlockT *>(BB))
115  if (!L->contains(Successor))
116  if (Visited.insert(Successor).second)
117  ExitBlocks.push_back(Successor);
118 }
119 
120 template <class BlockT, class LoopT>
122  SmallVectorImpl<BlockT *> &ExitBlocks) const {
123  getUniqueExitBlocksHelper(this, ExitBlocks,
124  [](const BlockT *BB) { return true; });
125 }
126 
127 template <class BlockT, class LoopT>
129  SmallVectorImpl<BlockT *> &ExitBlocks) const {
130  const BlockT *Latch = getLoopLatch();
131  assert(Latch && "Latch block must exists");
132  getUniqueExitBlocksHelper(this, ExitBlocks,
133  [Latch](const BlockT *BB) { return BB != Latch; });
134 }
135 
136 template <class BlockT, class LoopT>
138  SmallVector<BlockT *, 8> UniqueExitBlocks;
139  getUniqueExitBlocks(UniqueExitBlocks);
140  if (UniqueExitBlocks.size() == 1)
141  return UniqueExitBlocks[0];
142  return nullptr;
143 }
144 
145 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
146 template <class BlockT, class LoopT>
148  SmallVectorImpl<Edge> &ExitEdges) const {
149  assert(!isInvalid() && "Loop not in a valid state!");
150  for (const auto BB : blocks())
151  for (auto *Succ : children<BlockT *>(BB))
152  if (!contains(Succ))
153  // Not in current loop? It must be an exit block.
154  ExitEdges.emplace_back(BB, Succ);
155 }
156 
157 /// getLoopPreheader - If there is a preheader for this loop, return it. A
158 /// loop has a preheader if there is only one edge to the header of the loop
159 /// from outside of the loop and it is legal to hoist instructions into the
160 /// predecessor. If this is the case, the block branching to the header of the
161 /// loop is the preheader node.
162 ///
163 /// This method returns null if there is no preheader for the loop.
164 ///
165 template <class BlockT, class LoopT>
167  assert(!isInvalid() && "Loop not in a valid state!");
168  // Keep track of nodes outside the loop branching to the header...
169  BlockT *Out = getLoopPredecessor();
170  if (!Out)
171  return nullptr;
172 
173  // Make sure we are allowed to hoist instructions into the predecessor.
174  if (!Out->isLegalToHoistInto())
175  return nullptr;
176 
177  // Make sure there is only one exit out of the preheader.
178  typedef GraphTraits<BlockT *> BlockTraits;
179  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
180  ++SI;
181  if (SI != BlockTraits::child_end(Out))
182  return nullptr; // Multiple exits from the block, must not be a preheader.
183 
184  // The predecessor has exactly one successor, so it is a preheader.
185  return Out;
186 }
187 
188 /// getLoopPredecessor - If the given loop's header has exactly one unique
189 /// predecessor outside the loop, return it. Otherwise return null.
190 /// This is less strict that the loop "preheader" concept, which requires
191 /// the predecessor to have exactly one successor.
192 ///
193 template <class BlockT, class LoopT>
195  assert(!isInvalid() && "Loop not in a valid state!");
196  // Keep track of nodes outside the loop branching to the header...
197  BlockT *Out = nullptr;
198 
199  // Loop over the predecessors of the header node...
200  BlockT *Header = getHeader();
201  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
202  if (!contains(Pred)) { // If the block is not in the loop...
203  if (Out && Out != Pred)
204  return nullptr; // Multiple predecessors outside the loop
205  Out = Pred;
206  }
207  }
208 
209  return Out;
210 }
211 
212 /// getLoopLatch - If there is a single latch block for this loop, return it.
213 /// A latch block is a block that contains a branch back to the header.
214 template <class BlockT, class LoopT>
216  assert(!isInvalid() && "Loop not in a valid state!");
217  BlockT *Header = getHeader();
218  BlockT *Latch = nullptr;
219  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
220  if (contains(Pred)) {
221  if (Latch)
222  return nullptr;
223  Latch = Pred;
224  }
225  }
226 
227  return Latch;
228 }
229 
230 //===----------------------------------------------------------------------===//
231 // APIs for updating loop information after changing the CFG
232 //
233 
234 /// addBasicBlockToLoop - This method is used by other analyses to update loop
235 /// information. NewBB is set to be a new member of the current loop.
236 /// Because of this, it is added as a member of all parent loops, and is added
237 /// to the specified LoopInfo object as being in the current basic block. It
238 /// is not valid to replace the loop header with this method.
239 ///
240 template <class BlockT, class LoopT>
242  BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
243  assert(!isInvalid() && "Loop not in a valid state!");
244 #ifndef NDEBUG
245  if (!Blocks.empty()) {
246  auto SameHeader = LIB[getHeader()];
247  assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
248  "Incorrect LI specified for this loop!");
249  }
250 #endif
251  assert(NewBB && "Cannot add a null basic block to the loop!");
252  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
253 
254  LoopT *L = static_cast<LoopT *>(this);
255 
256  // Add the loop mapping to the LoopInfo object...
257  LIB.BBMap[NewBB] = L;
258 
259  // Add the basic block to this loop and all parent loops...
260  while (L) {
261  L->addBlockEntry(NewBB);
262  L = L->getParentLoop();
263  }
264 }
265 
266 /// replaceChildLoopWith - This is used when splitting loops up. It replaces
267 /// the OldChild entry in our children list with NewChild, and updates the
268 /// parent pointer of OldChild to be null and the NewChild to be this loop.
269 /// This updates the loop depth of the new child.
270 template <class BlockT, class LoopT>
272  LoopT *NewChild) {
273  assert(!isInvalid() && "Loop not in a valid state!");
274  assert(OldChild->ParentLoop == this && "This loop is already broken!");
275  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
276  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
277  assert(I != SubLoops.end() && "OldChild not in loop!");
278  *I = NewChild;
279  OldChild->ParentLoop = nullptr;
280  NewChild->ParentLoop = static_cast<LoopT *>(this);
281 }
282 
283 /// verifyLoop - Verify loop structure
284 template <class BlockT, class LoopT>
286  assert(!isInvalid() && "Loop not in a valid state!");
287 #ifndef NDEBUG
288  assert(!Blocks.empty() && "Loop header is missing");
289 
290  // Setup for using a depth-first iterator to visit every block in the loop.
291  SmallVector<BlockT *, 8> ExitBBs;
292  getExitBlocks(ExitBBs);
294  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
296  BI = df_ext_begin(getHeader(), VisitSet),
297  BE = df_ext_end(getHeader(), VisitSet);
298 
299  // Keep track of the BBs visited.
300  SmallPtrSet<BlockT *, 8> VisitedBBs;
301 
302  // Check the individual blocks.
303  for (; BI != BE; ++BI) {
304  BlockT *BB = *BI;
305 
308  [&](BlockT *B) { return contains(B); }) &&
309  "Loop block has no in-loop successors!");
310 
312  GraphTraits<Inverse<BlockT *>>::child_end(BB),
313  [&](BlockT *B) { return contains(B); }) &&
314  "Loop block has no in-loop predecessors!");
315 
316  SmallVector<BlockT *, 2> OutsideLoopPreds;
317  for (BlockT *B :
319  GraphTraits<Inverse<BlockT *>>::child_end(BB)))
320  if (!contains(B))
321  OutsideLoopPreds.push_back(B);
322 
323  if (BB == getHeader()) {
324  assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
325  } else if (!OutsideLoopPreds.empty()) {
326  // A non-header loop shouldn't be reachable from outside the loop,
327  // though it is permitted if the predecessor is not itself actually
328  // reachable.
329  BlockT *EntryBB = &BB->getParent()->front();
330  for (BlockT *CB : depth_first(EntryBB))
331  for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
332  assert(CB != OutsideLoopPreds[i] &&
333  "Loop has multiple entry points!");
334  }
335  assert(BB != &getHeader()->getParent()->front() &&
336  "Loop contains function entry block!");
337 
338  VisitedBBs.insert(BB);
339  }
340 
341  if (VisitedBBs.size() != getNumBlocks()) {
342  dbgs() << "The following blocks are unreachable in the loop: ";
343  for (auto BB : Blocks) {
344  if (!VisitedBBs.count(BB)) {
345  dbgs() << *BB << "\n";
346  }
347  }
348  assert(false && "Unreachable block in loop");
349  }
350 
351  // Check the subloops.
352  for (iterator I = begin(), E = end(); I != E; ++I)
353  // Each block in each subloop should be contained within this loop.
354  for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
355  BI != BE; ++BI) {
356  assert(contains(*BI) &&
357  "Loop does not contain all the blocks of a subloop!");
358  }
359 
360  // Check the parent loop pointer.
361  if (ParentLoop) {
362  assert(is_contained(*ParentLoop, this) &&
363  "Loop is not a subloop of its parent!");
364  }
365 #endif
366 }
367 
368 /// verifyLoop - Verify loop structure of this loop and all nested loops.
369 template <class BlockT, class LoopT>
372  assert(!isInvalid() && "Loop not in a valid state!");
373  Loops->insert(static_cast<const LoopT *>(this));
374  // Verify this loop.
375  verifyLoop();
376  // Verify the subloops.
377  for (iterator I = begin(), E = end(); I != E; ++I)
378  (*I)->verifyLoopNest(Loops);
379 }
380 
381 template <class BlockT, class LoopT>
383  bool PrintNested, unsigned Depth) const {
384  OS.indent(Depth * 2);
385  if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
386  OS << "Parallel ";
387  OS << "Loop at depth " << getLoopDepth() << " containing: ";
388 
389  BlockT *H = getHeader();
390  for (unsigned i = 0; i < getBlocks().size(); ++i) {
391  BlockT *BB = getBlocks()[i];
392  if (!Verbose) {
393  if (i)
394  OS << ",";
395  BB->printAsOperand(OS, false);
396  } else
397  OS << "\n";
398 
399  if (BB == H)
400  OS << "<header>";
401  if (isLoopLatch(BB))
402  OS << "<latch>";
403  if (isLoopExiting(BB))
404  OS << "<exiting>";
405  if (Verbose)
406  BB->print(OS);
407  }
408 
409  if (PrintNested) {
410  OS << "\n";
411 
412  for (iterator I = begin(), E = end(); I != E; ++I)
413  (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
414  }
415 }
416 
417 //===----------------------------------------------------------------------===//
418 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
419 /// result does / not depend on use list (block predecessor) order.
420 ///
421 
422 /// Discover a subloop with the specified backedges such that: All blocks within
423 /// this loop are mapped to this loop or a subloop. And all subloops within this
424 /// loop have their parent loop set to this loop or a subloop.
425 template <class BlockT, class LoopT>
426 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
428  const DomTreeBase<BlockT> &DomTree) {
429  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
430 
431  unsigned NumBlocks = 0;
432  unsigned NumSubloops = 0;
433 
434  // Perform a backward CFG traversal using a worklist.
435  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
436  while (!ReverseCFGWorklist.empty()) {
437  BlockT *PredBB = ReverseCFGWorklist.back();
438  ReverseCFGWorklist.pop_back();
439 
440  LoopT *Subloop = LI->getLoopFor(PredBB);
441  if (!Subloop) {
442  if (!DomTree.isReachableFromEntry(PredBB))
443  continue;
444 
445  // This is an undiscovered block. Map it to the current loop.
446  LI->changeLoopFor(PredBB, L);
447  ++NumBlocks;
448  if (PredBB == L->getHeader())
449  continue;
450  // Push all block predecessors on the worklist.
451  ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
452  InvBlockTraits::child_begin(PredBB),
453  InvBlockTraits::child_end(PredBB));
454  } else {
455  // This is a discovered block. Find its outermost discovered loop.
456  Subloop = Subloop->getOutermostLoop();
457 
458  // If it is already discovered to be a subloop of this loop, continue.
459  if (Subloop == L)
460  continue;
461 
462  // Discover a subloop of this loop.
463  Subloop->setParentLoop(L);
464  ++NumSubloops;
465  NumBlocks += Subloop->getBlocksVector().capacity();
466  PredBB = Subloop->getHeader();
467  // Continue traversal along predecessors that are not loop-back edges from
468  // within this subloop tree itself. Note that a predecessor may directly
469  // reach another subloop that is not yet discovered to be a subloop of
470  // this loop, which we must traverse.
471  for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
472  if (LI->getLoopFor(Pred) != Subloop)
473  ReverseCFGWorklist.push_back(Pred);
474  }
475  }
476  }
477  L->getSubLoopsVector().reserve(NumSubloops);
478  L->reserveBlocks(NumBlocks);
479 }
480 
481 /// Populate all loop data in a stable order during a single forward DFS.
482 template <class BlockT, class LoopT> class PopulateLoopsDFS {
484  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
485 
487 
488 public:
490 
491  void traverse(BlockT *EntryBlock);
492 
493 protected:
494  void insertIntoLoop(BlockT *Block);
495 };
496 
497 /// Top-level driver for the forward DFS within the loop.
498 template <class BlockT, class LoopT>
500  for (BlockT *BB : post_order(EntryBlock))
501  insertIntoLoop(BB);
502 }
503 
504 /// Add a single Block to its ancestor loops in PostOrder. If the block is a
505 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
506 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
507 template <class BlockT, class LoopT>
509  LoopT *Subloop = LI->getLoopFor(Block);
510  if (Subloop && Block == Subloop->getHeader()) {
511  // We reach this point once per subloop after processing all the blocks in
512  // the subloop.
513  if (!Subloop->isOutermost())
514  Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
515  else
516  LI->addTopLevelLoop(Subloop);
517 
518  // For convenience, Blocks and Subloops are inserted in postorder. Reverse
519  // the lists, except for the loop header, which is always at the beginning.
520  Subloop->reverseBlock(1);
521  std::reverse(Subloop->getSubLoopsVector().begin(),
522  Subloop->getSubLoopsVector().end());
523 
524  Subloop = Subloop->getParentLoop();
525  }
526  for (; Subloop; Subloop = Subloop->getParentLoop())
527  Subloop->addBlockEntry(Block);
528 }
529 
530 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
531 /// interleaved with backward CFG traversals within each subloop
532 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
533 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
534 /// Block vectors are then populated during a single forward CFG traversal
535 /// (PopulateLoopDFS).
536 ///
537 /// During the two CFG traversals each block is seen three times:
538 /// 1) Discovered and mapped by a reverse CFG traversal.
539 /// 2) Visited during a forward DFS CFG traversal.
540 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
541 ///
542 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
543 /// insertions per block.
544 template <class BlockT, class LoopT>
546  // Postorder traversal of the dominator tree.
547  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
548  for (auto DomNode : post_order(DomRoot)) {
549 
550  BlockT *Header = DomNode->getBlock();
551  SmallVector<BlockT *, 4> Backedges;
552 
553  // Check each predecessor of the potential loop header.
554  for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
555  // If Header dominates predBB, this is a new loop. Collect the backedges.
556  if (DomTree.dominates(Header, Backedge) &&
557  DomTree.isReachableFromEntry(Backedge)) {
558  Backedges.push_back(Backedge);
559  }
560  }
561  // Perform a backward CFG traversal to discover and map blocks in this loop.
562  if (!Backedges.empty()) {
563  LoopT *L = AllocateLoop(Header);
564  discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
565  }
566  }
567  // Perform a single forward CFG traversal to populate block and subloop
568  // vectors for all loops.
570  DFS.traverse(DomRoot->getBlock());
571 }
572 
573 template <class BlockT, class LoopT>
576  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
577  // The outer-most loop actually goes into the result in the same relative
578  // order as we walk it. But LoopInfo stores the top level loops in reverse
579  // program order so for here we reverse it to get forward program order.
580  // FIXME: If we change the order of LoopInfo we will want to remove the
581  // reverse here.
582  for (LoopT *RootL : reverse(*this)) {
583  auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
584  PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
585  PreOrderLoopsInRootL.end());
586  }
587 
588  return PreOrderLoops;
589 }
590 
591 template <class BlockT, class LoopT>
594  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
595  // The outer-most loop actually goes into the result in the same relative
596  // order as we walk it. LoopInfo stores the top level loops in reverse
597  // program order so we walk in order here.
598  // FIXME: If we change the order of LoopInfo we will want to add a reverse
599  // here.
600  for (LoopT *RootL : *this) {
601  assert(PreOrderWorklist.empty() &&
602  "Must start with an empty preorder walk worklist.");
603  PreOrderWorklist.push_back(RootL);
604  do {
605  LoopT *L = PreOrderWorklist.pop_back_val();
606  // Sub-loops are stored in forward program order, but will process the
607  // worklist backwards so we can just append them in order.
608  PreOrderWorklist.append(L->begin(), L->end());
609  PreOrderLoops.push_back(L);
610  } while (!PreOrderWorklist.empty());
611  }
612 
613  return PreOrderLoops;
614 }
615 
616 // Debugging
617 template <class BlockT, class LoopT>
619  for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
620  TopLevelLoops[i]->print(OS);
621 #if 0
623  E = BBMap.end(); I != E; ++I)
624  OS << "BB '" << I->first->getName() << "' level = "
625  << I->second->getLoopDepth() << "\n";
626 #endif
627 }
628 
629 template <typename T>
630 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
631  llvm::sort(BB1);
632  llvm::sort(BB2);
633  return BB1 == BB2;
634 }
635 
636 template <class BlockT, class LoopT>
638  const LoopInfoBase<BlockT, LoopT> &LI,
639  const LoopT &L) {
640  LoopHeaders[L.getHeader()] = &L;
641  for (LoopT *SL : L)
642  addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
643 }
644 
645 #ifndef NDEBUG
646 template <class BlockT, class LoopT>
647 static void compareLoops(const LoopT *L, const LoopT *OtherL,
648  DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
649  BlockT *H = L->getHeader();
650  BlockT *OtherH = OtherL->getHeader();
651  assert(H == OtherH &&
652  "Mismatched headers even though found in the same map entry!");
653 
654  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
655  "Mismatched loop depth!");
656  const LoopT *ParentL = L, *OtherParentL = OtherL;
657  do {
658  assert(ParentL->getHeader() == OtherParentL->getHeader() &&
659  "Mismatched parent loop headers!");
660  ParentL = ParentL->getParentLoop();
661  OtherParentL = OtherParentL->getParentLoop();
662  } while (ParentL);
663 
664  for (const LoopT *SubL : *L) {
665  BlockT *SubH = SubL->getHeader();
666  const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
667  assert(OtherSubL && "Inner loop is missing in computed loop info!");
668  OtherLoopHeaders.erase(SubH);
669  compareLoops(SubL, OtherSubL, OtherLoopHeaders);
670  }
671 
672  std::vector<BlockT *> BBs = L->getBlocks();
673  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
674  assert(compareVectors(BBs, OtherBBs) &&
675  "Mismatched basic blocks in the loops!");
676 
677  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
678  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
679  OtherL->getBlocksSet();
680  assert(BlocksSet.size() == OtherBlocksSet.size() &&
681  llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
682  "Mismatched basic blocks in BlocksSets!");
683 }
684 #endif
685 
686 template <class BlockT, class LoopT>
688  const DomTreeBase<BlockT> &DomTree) const {
690  for (iterator I = begin(), E = end(); I != E; ++I) {
691  assert((*I)->isOutermost() && "Top-level loop has a parent!");
692  (*I)->verifyLoopNest(&Loops);
693  }
694 
695 // Verify that blocks are mapped to valid loops.
696 #ifndef NDEBUG
697  for (auto &Entry : BBMap) {
698  const BlockT *BB = Entry.first;
699  LoopT *L = Entry.second;
700  assert(Loops.count(L) && "orphaned loop");
701  assert(L->contains(BB) && "orphaned block");
702  for (LoopT *ChildLoop : *L)
703  assert(!ChildLoop->contains(BB) &&
704  "BBMap should point to the innermost loop containing BB");
705  }
706 
707  // Recompute LoopInfo to verify loops structure.
709  OtherLI.analyze(DomTree);
710 
711  // Build a map we can use to move from our LI to the computed one. This
712  // allows us to ignore the particular order in any layer of the loop forest
713  // while still comparing the structure.
714  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
715  for (LoopT *L : OtherLI)
716  addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
717 
718  // Walk the top level loops and ensure there is a corresponding top-level
719  // loop in the computed version and then recursively compare those loop
720  // nests.
721  for (LoopT *L : *this) {
722  BlockT *Header = L->getHeader();
723  const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
724  assert(OtherL && "Top level loop is missing in computed loop info!");
725  // Now that we've matched this loop, erase its header from the map.
726  OtherLoopHeaders.erase(Header);
727  // And recursively compare these loops.
728  compareLoops(L, OtherL, OtherLoopHeaders);
729  }
730 
731  // Any remaining entries in the map are loops which were found when computing
732  // a fresh LoopInfo but not present in the current one.
733  if (!OtherLoopHeaders.empty()) {
734  for (const auto &HeaderAndLoop : OtherLoopHeaders)
735  dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
736  llvm_unreachable("Found new loops when recomputing LoopInfo!");
737  }
738 #endif
739 }
740 
741 } // End llvm namespace
742 
743 #endif
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:137
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DominatorTreeBase::isReachableFromEntry
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
Definition: GenericDomTree.h:405
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:61
llvm::set_is_subset
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
Definition: SetOperations.h:72
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:81
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
SetOperations.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:199
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::InlinerFunctionImportStatsOpts::Verbose
@ Verbose
contains
return AArch64::GPR64RegClass contains(Reg)
llvm::SmallVector< BlockT *, 8 >
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:687
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:194
llvm::discoverAndMapSubloop
static void discoverAndMapSubloop(LoopT *L, ArrayRef< BlockT * > Backedges, LoopInfoBase< BlockT, LoopT > *LI, const DomTreeBase< BlockT > &DomTree)
Stable LoopInfo Analysis - Build a loop tree using stable iterators so the result does / not depend o...
Definition: LoopInfoImpl.h:426
llvm::PopulateLoopsDFS
Populate all loop data in a stable order during a single forward DFS.
Definition: LoopInfoImpl.h:482
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1024
llvm::LoopInfoBase::print
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:618
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::LoopBase::getExitEdges
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:147
llvm::PopulateLoopsDFS::PopulateLoopsDFS
PopulateLoopsDFS(LoopInfoBase< BlockT, LoopT > *li)
Definition: LoopInfoImpl.h:489
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::df_ext_begin
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:242
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:545
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
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:667
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::LoopBase::verifyLoop
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:285
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:33
llvm::compareVectors
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
Definition: LoopInfoImpl.h:630
llvm::LoopBase::verifyLoopNest
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
Definition: LoopInfoImpl.h:370
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
PredicateT
LoopInfo.h
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::LoopBase< BasicBlock, Loop >::block_iterator
ArrayRef< BasicBlock * >::const_iterator block_iterator
Definition: LoopInfo.h:191
llvm::PopulateLoopsDFS::traverse
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
Definition: LoopInfoImpl.h:499
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1637
llvm::LoopBase::getUniqueExitBlocks
void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:121
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
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:1682
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:91
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
llvm::df_iterator_default_set::insert
std::pair< iterator, bool > insert(NodeRef N)
Definition: DepthFirstIterator.h:74
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:383
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:70
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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:1624
llvm::getUniqueExitBlocksHelper
void getUniqueExitBlocksHelper(const LoopT *L, SmallVectorImpl< BlockT * > &ExitBlocks, PredicateT Pred)
Definition: LoopInfoImpl.h:107
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:868
llvm::LoopBase::replaceChildLoopWith
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:271
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::DominatorTreeBase::dominates
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Definition: GenericDomTree.h:416
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:534
llvm::LoopBase::getUniqueNonLatchExitBlocks
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
Definition: LoopInfoImpl.h:128
llvm::df_ext_end
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:247
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:98
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::LoopInfoBase::getLoopsInPreorder
SmallVector< LoopT *, 4 > getLoopsInPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:575
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::addInnerLoopsToHeadersMap
void addInnerLoopsToHeadersMap(DenseMap< BlockT *, const LoopT * > &LoopHeaders, const LoopInfoBase< BlockT, LoopT > &LI, const LoopT &L)
Definition: LoopInfoImpl.h:637
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::compareLoops
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT * > &OtherLoopHeaders)
Definition: LoopInfoImpl.h:647
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:152
llvm::LoopInfoBase
This class builds and contains all of the top-level loop structures in the specified function.
Definition: LoopInfo.h:66
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:189
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
llvm::Inverse
Definition: GraphTraits.h:97
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:72
PostOrderIterator.h
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:241
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:496
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:167
Dominators.h
llvm::df_ext_iterator
Definition: DepthFirstIterator.h:236
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:958
llvm::SmallVectorImpl< BlockT * >
llvm::SmallPtrSetImpl< const BlockT * >
llvm::LoopBase::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:382
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::GraphTraits
Definition: GraphTraits.h:37
llvm::PopulateLoopsDFS::insertIntoLoop
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
Definition: LoopInfoImpl.h:508
llvm::LoopInfoBase::getLoopsInReverseSiblingPreorder
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder() const
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
Definition: LoopInfoImpl.h:593
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
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:365