LLVM  16.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());
295 
296  // Keep track of the BBs visited.
297  SmallPtrSet<BlockT *, 8> VisitedBBs;
298 
299  // Check the individual blocks.
300  for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
303  [&](BlockT *B) { return contains(B); }) &&
304  "Loop block has no in-loop successors!");
305 
307  GraphTraits<Inverse<BlockT *>>::child_end(BB),
308  [&](BlockT *B) { return contains(B); }) &&
309  "Loop block has no in-loop predecessors!");
310 
311  SmallVector<BlockT *, 2> OutsideLoopPreds;
312  for (BlockT *B :
314  GraphTraits<Inverse<BlockT *>>::child_end(BB)))
315  if (!contains(B))
316  OutsideLoopPreds.push_back(B);
317 
318  if (BB == getHeader()) {
319  assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
320  } else if (!OutsideLoopPreds.empty()) {
321  // A non-header loop shouldn't be reachable from outside the loop,
322  // though it is permitted if the predecessor is not itself actually
323  // reachable.
324  BlockT *EntryBB = &BB->getParent()->front();
325  for (BlockT *CB : depth_first(EntryBB))
326  for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
327  assert(CB != OutsideLoopPreds[i] &&
328  "Loop has multiple entry points!");
329  }
330  assert(BB != &getHeader()->getParent()->front() &&
331  "Loop contains function entry block!");
332 
333  VisitedBBs.insert(BB);
334  }
335 
336  if (VisitedBBs.size() != getNumBlocks()) {
337  dbgs() << "The following blocks are unreachable in the loop: ";
338  for (auto *BB : Blocks) {
339  if (!VisitedBBs.count(BB)) {
340  dbgs() << *BB << "\n";
341  }
342  }
343  assert(false && "Unreachable block in loop");
344  }
345 
346  // Check the subloops.
347  for (iterator I = begin(), E = end(); I != E; ++I)
348  // Each block in each subloop should be contained within this loop.
349  for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
350  BI != BE; ++BI) {
351  assert(contains(*BI) &&
352  "Loop does not contain all the blocks of a subloop!");
353  }
354 
355  // Check the parent loop pointer.
356  if (ParentLoop) {
357  assert(is_contained(*ParentLoop, this) &&
358  "Loop is not a subloop of its parent!");
359  }
360 #endif
361 }
362 
363 /// verifyLoop - Verify loop structure of this loop and all nested loops.
364 template <class BlockT, class LoopT>
367  assert(!isInvalid() && "Loop not in a valid state!");
368  Loops->insert(static_cast<const LoopT *>(this));
369  // Verify this loop.
370  verifyLoop();
371  // Verify the subloops.
372  for (iterator I = begin(), E = end(); I != E; ++I)
373  (*I)->verifyLoopNest(Loops);
374 }
375 
376 template <class BlockT, class LoopT>
378  bool PrintNested, unsigned Depth) const {
379  OS.indent(Depth * 2);
380  if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
381  OS << "Parallel ";
382  OS << "Loop at depth " << getLoopDepth() << " containing: ";
383 
384  BlockT *H = getHeader();
385  for (unsigned i = 0; i < getBlocks().size(); ++i) {
386  BlockT *BB = getBlocks()[i];
387  if (!Verbose) {
388  if (i)
389  OS << ",";
390  BB->printAsOperand(OS, false);
391  } else
392  OS << "\n";
393 
394  if (BB == H)
395  OS << "<header>";
396  if (isLoopLatch(BB))
397  OS << "<latch>";
398  if (isLoopExiting(BB))
399  OS << "<exiting>";
400  if (Verbose)
401  BB->print(OS);
402  }
403 
404  if (PrintNested) {
405  OS << "\n";
406 
407  for (iterator I = begin(), E = end(); I != E; ++I)
408  (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
409  }
410 }
411 
412 //===----------------------------------------------------------------------===//
413 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
414 /// result does / not depend on use list (block predecessor) order.
415 ///
416 
417 /// Discover a subloop with the specified backedges such that: All blocks within
418 /// this loop are mapped to this loop or a subloop. And all subloops within this
419 /// loop have their parent loop set to this loop or a subloop.
420 template <class BlockT, class LoopT>
421 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
423  const DomTreeBase<BlockT> &DomTree) {
424  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
425 
426  unsigned NumBlocks = 0;
427  unsigned NumSubloops = 0;
428 
429  // Perform a backward CFG traversal using a worklist.
430  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
431  while (!ReverseCFGWorklist.empty()) {
432  BlockT *PredBB = ReverseCFGWorklist.back();
433  ReverseCFGWorklist.pop_back();
434 
435  LoopT *Subloop = LI->getLoopFor(PredBB);
436  if (!Subloop) {
437  if (!DomTree.isReachableFromEntry(PredBB))
438  continue;
439 
440  // This is an undiscovered block. Map it to the current loop.
441  LI->changeLoopFor(PredBB, L);
442  ++NumBlocks;
443  if (PredBB == L->getHeader())
444  continue;
445  // Push all block predecessors on the worklist.
446  ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
447  InvBlockTraits::child_begin(PredBB),
448  InvBlockTraits::child_end(PredBB));
449  } else {
450  // This is a discovered block. Find its outermost discovered loop.
451  Subloop = Subloop->getOutermostLoop();
452 
453  // If it is already discovered to be a subloop of this loop, continue.
454  if (Subloop == L)
455  continue;
456 
457  // Discover a subloop of this loop.
458  Subloop->setParentLoop(L);
459  ++NumSubloops;
460  NumBlocks += Subloop->getBlocksVector().capacity();
461  PredBB = Subloop->getHeader();
462  // Continue traversal along predecessors that are not loop-back edges from
463  // within this subloop tree itself. Note that a predecessor may directly
464  // reach another subloop that is not yet discovered to be a subloop of
465  // this loop, which we must traverse.
466  for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
467  if (LI->getLoopFor(Pred) != Subloop)
468  ReverseCFGWorklist.push_back(Pred);
469  }
470  }
471  }
472  L->getSubLoopsVector().reserve(NumSubloops);
473  L->reserveBlocks(NumBlocks);
474 }
475 
476 /// Populate all loop data in a stable order during a single forward DFS.
477 template <class BlockT, class LoopT> class PopulateLoopsDFS {
479  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
480 
482 
483 public:
485 
486  void traverse(BlockT *EntryBlock);
487 
488 protected:
489  void insertIntoLoop(BlockT *Block);
490 };
491 
492 /// Top-level driver for the forward DFS within the loop.
493 template <class BlockT, class LoopT>
495  for (BlockT *BB : post_order(EntryBlock))
496  insertIntoLoop(BB);
497 }
498 
499 /// Add a single Block to its ancestor loops in PostOrder. If the block is a
500 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
501 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
502 template <class BlockT, class LoopT>
504  LoopT *Subloop = LI->getLoopFor(Block);
505  if (Subloop && Block == Subloop->getHeader()) {
506  // We reach this point once per subloop after processing all the blocks in
507  // the subloop.
508  if (!Subloop->isOutermost())
509  Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
510  else
511  LI->addTopLevelLoop(Subloop);
512 
513  // For convenience, Blocks and Subloops are inserted in postorder. Reverse
514  // the lists, except for the loop header, which is always at the beginning.
515  Subloop->reverseBlock(1);
516  std::reverse(Subloop->getSubLoopsVector().begin(),
517  Subloop->getSubLoopsVector().end());
518 
519  Subloop = Subloop->getParentLoop();
520  }
521  for (; Subloop; Subloop = Subloop->getParentLoop())
522  Subloop->addBlockEntry(Block);
523 }
524 
525 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
526 /// interleaved with backward CFG traversals within each subloop
527 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
528 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
529 /// Block vectors are then populated during a single forward CFG traversal
530 /// (PopulateLoopDFS).
531 ///
532 /// During the two CFG traversals each block is seen three times:
533 /// 1) Discovered and mapped by a reverse CFG traversal.
534 /// 2) Visited during a forward DFS CFG traversal.
535 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
536 ///
537 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
538 /// insertions per block.
539 template <class BlockT, class LoopT>
541  // Postorder traversal of the dominator tree.
542  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
543  for (auto DomNode : post_order(DomRoot)) {
544 
545  BlockT *Header = DomNode->getBlock();
546  SmallVector<BlockT *, 4> Backedges;
547 
548  // Check each predecessor of the potential loop header.
549  for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
550  // If Header dominates predBB, this is a new loop. Collect the backedges.
551  if (DomTree.dominates(Header, Backedge) &&
552  DomTree.isReachableFromEntry(Backedge)) {
553  Backedges.push_back(Backedge);
554  }
555  }
556  // Perform a backward CFG traversal to discover and map blocks in this loop.
557  if (!Backedges.empty()) {
558  LoopT *L = AllocateLoop(Header);
559  discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
560  }
561  }
562  // Perform a single forward CFG traversal to populate block and subloop
563  // vectors for all loops.
565  DFS.traverse(DomRoot->getBlock());
566 }
567 
568 template <class BlockT, class LoopT>
571  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
572  // The outer-most loop actually goes into the result in the same relative
573  // order as we walk it. But LoopInfo stores the top level loops in reverse
574  // program order so for here we reverse it to get forward program order.
575  // FIXME: If we change the order of LoopInfo we will want to remove the
576  // reverse here.
577  for (LoopT *RootL : reverse(*this)) {
578  auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
579  PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
580  PreOrderLoopsInRootL.end());
581  }
582 
583  return PreOrderLoops;
584 }
585 
586 template <class BlockT, class LoopT>
589  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
590  // The outer-most loop actually goes into the result in the same relative
591  // order as we walk it. LoopInfo stores the top level loops in reverse
592  // program order so we walk in order here.
593  // FIXME: If we change the order of LoopInfo we will want to add a reverse
594  // here.
595  for (LoopT *RootL : *this) {
596  assert(PreOrderWorklist.empty() &&
597  "Must start with an empty preorder walk worklist.");
598  PreOrderWorklist.push_back(RootL);
599  do {
600  LoopT *L = PreOrderWorklist.pop_back_val();
601  // Sub-loops are stored in forward program order, but will process the
602  // worklist backwards so we can just append them in order.
603  PreOrderWorklist.append(L->begin(), L->end());
604  PreOrderLoops.push_back(L);
605  } while (!PreOrderWorklist.empty());
606  }
607 
608  return PreOrderLoops;
609 }
610 
611 // Debugging
612 template <class BlockT, class LoopT>
614  for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
615  TopLevelLoops[i]->print(OS);
616 #if 0
618  E = BBMap.end(); I != E; ++I)
619  OS << "BB '" << I->first->getName() << "' level = "
620  << I->second->getLoopDepth() << "\n";
621 #endif
622 }
623 
624 template <typename T>
625 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
626  llvm::sort(BB1);
627  llvm::sort(BB2);
628  return BB1 == BB2;
629 }
630 
631 template <class BlockT, class LoopT>
633  const LoopInfoBase<BlockT, LoopT> &LI,
634  const LoopT &L) {
635  LoopHeaders[L.getHeader()] = &L;
636  for (LoopT *SL : L)
637  addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
638 }
639 
640 #ifndef NDEBUG
641 template <class BlockT, class LoopT>
642 static void compareLoops(const LoopT *L, const LoopT *OtherL,
643  DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
644  BlockT *H = L->getHeader();
645  BlockT *OtherH = OtherL->getHeader();
646  assert(H == OtherH &&
647  "Mismatched headers even though found in the same map entry!");
648 
649  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
650  "Mismatched loop depth!");
651  const LoopT *ParentL = L, *OtherParentL = OtherL;
652  do {
653  assert(ParentL->getHeader() == OtherParentL->getHeader() &&
654  "Mismatched parent loop headers!");
655  ParentL = ParentL->getParentLoop();
656  OtherParentL = OtherParentL->getParentLoop();
657  } while (ParentL);
658 
659  for (const LoopT *SubL : *L) {
660  BlockT *SubH = SubL->getHeader();
661  const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
662  assert(OtherSubL && "Inner loop is missing in computed loop info!");
663  OtherLoopHeaders.erase(SubH);
664  compareLoops(SubL, OtherSubL, OtherLoopHeaders);
665  }
666 
667  std::vector<BlockT *> BBs = L->getBlocks();
668  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
669  assert(compareVectors(BBs, OtherBBs) &&
670  "Mismatched basic blocks in the loops!");
671 
672  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
673  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet =
674  OtherL->getBlocksSet();
675  assert(BlocksSet.size() == OtherBlocksSet.size() &&
676  llvm::set_is_subset(BlocksSet, OtherBlocksSet) &&
677  "Mismatched basic blocks in BlocksSets!");
678 }
679 #endif
680 
681 template <class BlockT, class LoopT>
683  const DomTreeBase<BlockT> &DomTree) const {
685  for (iterator I = begin(), E = end(); I != E; ++I) {
686  assert((*I)->isOutermost() && "Top-level loop has a parent!");
687  (*I)->verifyLoopNest(&Loops);
688  }
689 
690 // Verify that blocks are mapped to valid loops.
691 #ifndef NDEBUG
692  for (auto &Entry : BBMap) {
693  const BlockT *BB = Entry.first;
694  LoopT *L = Entry.second;
695  assert(Loops.count(L) && "orphaned loop");
696  assert(L->contains(BB) && "orphaned block");
697  for (LoopT *ChildLoop : *L)
698  assert(!ChildLoop->contains(BB) &&
699  "BBMap should point to the innermost loop containing BB");
700  }
701 
702  // Recompute LoopInfo to verify loops structure.
704  OtherLI.analyze(DomTree);
705 
706  // Build a map we can use to move from our LI to the computed one. This
707  // allows us to ignore the particular order in any layer of the loop forest
708  // while still comparing the structure.
709  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
710  for (LoopT *L : OtherLI)
711  addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
712 
713  // Walk the top level loops and ensure there is a corresponding top-level
714  // loop in the computed version and then recursively compare those loop
715  // nests.
716  for (LoopT *L : *this) {
717  BlockT *Header = L->getHeader();
718  const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
719  assert(OtherL && "Top level loop is missing in computed loop info!");
720  // Now that we've matched this loop, erase its header from the map.
721  OtherLoopHeaders.erase(Header);
722  // And recursively compare these loops.
723  compareLoops(L, OtherL, OtherLoopHeaders);
724  }
725 
726  // Any remaining entries in the map are loops which were found when computing
727  // a fresh LoopInfo but not present in the current one.
728  if (!OtherLoopHeaders.empty()) {
729  for (const auto &HeaderAndLoop : OtherLoopHeaders)
730  dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
731  llvm_unreachable("Found new loops when recomputing LoopInfo!");
732  }
733 #endif
734 }
735 
736 } // End llvm namespace
737 
738 #endif
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:197
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:682
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:421
llvm::PopulateLoopsDFS
Populate all loop data in a stable order during a single forward DFS.
Definition: LoopInfoImpl.h:477
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1027
llvm::LoopInfoBase::print
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:613
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:302
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::DenseMapIterator
Definition: DenseMap.h:57
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:484
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:540
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")
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:252
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:52
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:625
llvm::LoopBase::verifyLoopNest
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
Verify loop structure of this loop and all nested loops.
Definition: LoopInfoImpl.h:365
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:670
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
PredicateT
LoopInfo.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1538
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:494
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:1610
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:54
llvm::DenseMap
Definition: DenseMap.h:714
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:989
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:1673
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::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
bool empty() const
Definition: DenseMap.h:98
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:1597
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:847
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:512
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::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
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:570
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:632
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:642
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::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:494
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:167
Dominators.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:660
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:961
llvm::SmallVectorImpl< BlockT * >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:365
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:377
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:503
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:588
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:153
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:924
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