LLVM  10.0.0svn
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 
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/Dominators.h"
23 
24 namespace llvm {
25 
26 //===----------------------------------------------------------------------===//
27 // APIs for simple analysis of the loop. See header notes.
28 
29 /// getExitingBlocks - Return all blocks inside the loop that have successors
30 /// outside of the loop. These are the blocks _inside of the current loop_
31 /// which branch out. The returned list is always unique.
32 ///
33 template <class BlockT, class LoopT>
35  SmallVectorImpl<BlockT *> &ExitingBlocks) const {
36  assert(!isInvalid() && "Loop not in a valid state!");
37  for (const auto BB : blocks())
38  for (const auto &Succ : children<BlockT *>(BB))
39  if (!contains(Succ)) {
40  // Not in current loop? It must be an exit block.
41  ExitingBlocks.push_back(BB);
42  break;
43  }
44 }
45 
46 /// getExitingBlock - If getExitingBlocks would return exactly one block,
47 /// return that block. Otherwise return null.
48 template <class BlockT, class LoopT>
50  assert(!isInvalid() && "Loop not in a valid state!");
51  SmallVector<BlockT *, 8> ExitingBlocks;
52  getExitingBlocks(ExitingBlocks);
53  if (ExitingBlocks.size() == 1)
54  return ExitingBlocks[0];
55  return nullptr;
56 }
57 
58 /// getExitBlocks - Return all of the successor blocks of this loop. These
59 /// are the blocks _outside of the current loop_ which are branched to.
60 ///
61 template <class BlockT, class LoopT>
63  SmallVectorImpl<BlockT *> &ExitBlocks) const {
64  assert(!isInvalid() && "Loop not in a valid state!");
65  for (const auto BB : blocks())
66  for (const auto &Succ : children<BlockT *>(BB))
67  if (!contains(Succ))
68  // Not in current loop? It must be an exit block.
69  ExitBlocks.push_back(Succ);
70 }
71 
72 /// getExitBlock - If getExitBlocks would return exactly one block,
73 /// return that block. Otherwise return null.
74 template <class BlockT, class LoopT>
76  assert(!isInvalid() && "Loop not in a valid state!");
77  SmallVector<BlockT *, 8> ExitBlocks;
78  getExitBlocks(ExitBlocks);
79  if (ExitBlocks.size() == 1)
80  return ExitBlocks[0];
81  return nullptr;
82 }
83 
84 template <class BlockT, class LoopT>
86  // Each predecessor of each exit block of a normal loop is contained
87  // within the loop.
88  SmallVector<BlockT *, 4> ExitBlocks;
89  getExitBlocks(ExitBlocks);
90  for (BlockT *EB : ExitBlocks)
91  for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
92  if (!contains(Predecessor))
93  return false;
94  // All the requirements are met.
95  return true;
96 }
97 
98 // Helper function to get unique loop exits. Pred is a predicate pointing to
99 // BasicBlocks in a loop which should be considered to find loop exits.
100 template <class BlockT, class LoopT, typename PredicateT>
101 void getUniqueExitBlocksHelper(const LoopT *L,
102  SmallVectorImpl<BlockT *> &ExitBlocks,
103  PredicateT Pred) {
104  assert(!L->isInvalid() && "Loop not in a valid state!");
106  auto Filtered = make_filter_range(L->blocks(), Pred);
107  for (BlockT *BB : Filtered)
108  for (BlockT *Successor : children<BlockT *>(BB))
109  if (!L->contains(Successor))
110  if (Visited.insert(Successor).second)
111  ExitBlocks.push_back(Successor);
112 }
113 
114 template <class BlockT, class LoopT>
116  SmallVectorImpl<BlockT *> &ExitBlocks) const {
117  getUniqueExitBlocksHelper(this, ExitBlocks,
118  [](const BlockT *BB) { return true; });
119 }
120 
121 template <class BlockT, class LoopT>
123  SmallVectorImpl<BlockT *> &ExitBlocks) const {
124  const BlockT *Latch = getLoopLatch();
125  assert(Latch && "Latch block must exists");
126  getUniqueExitBlocksHelper(this, ExitBlocks,
127  [Latch](const BlockT *BB) { return BB != Latch; });
128 }
129 
130 template <class BlockT, class LoopT>
132  SmallVector<BlockT *, 8> UniqueExitBlocks;
133  getUniqueExitBlocks(UniqueExitBlocks);
134  if (UniqueExitBlocks.size() == 1)
135  return UniqueExitBlocks[0];
136  return nullptr;
137 }
138 
139 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
140 template <class BlockT, class LoopT>
142  SmallVectorImpl<Edge> &ExitEdges) const {
143  assert(!isInvalid() && "Loop not in a valid state!");
144  for (const auto BB : blocks())
145  for (const auto &Succ : children<BlockT *>(BB))
146  if (!contains(Succ))
147  // Not in current loop? It must be an exit block.
148  ExitEdges.emplace_back(BB, Succ);
149 }
150 
151 /// getLoopPreheader - If there is a preheader for this loop, return it. A
152 /// loop has a preheader if there is only one edge to the header of the loop
153 /// from outside of the loop and it is legal to hoist instructions into the
154 /// predecessor. If this is the case, the block branching to the header of the
155 /// loop is the preheader node.
156 ///
157 /// This method returns null if there is no preheader for the loop.
158 ///
159 template <class BlockT, class LoopT>
161  assert(!isInvalid() && "Loop not in a valid state!");
162  // Keep track of nodes outside the loop branching to the header...
163  BlockT *Out = getLoopPredecessor();
164  if (!Out)
165  return nullptr;
166 
167  // Make sure we are allowed to hoist instructions into the predecessor.
168  if (!Out->isLegalToHoistInto())
169  return nullptr;
170 
171  // Make sure there is only one exit out of the preheader.
172  typedef GraphTraits<BlockT *> BlockTraits;
173  typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
174  ++SI;
175  if (SI != BlockTraits::child_end(Out))
176  return nullptr; // Multiple exits from the block, must not be a preheader.
177 
178  // The predecessor has exactly one successor, so it is a preheader.
179  return Out;
180 }
181 
182 /// getLoopPredecessor - If the given loop's header has exactly one unique
183 /// predecessor outside the loop, return it. Otherwise return null.
184 /// This is less strict that the loop "preheader" concept, which requires
185 /// the predecessor to have exactly one successor.
186 ///
187 template <class BlockT, class LoopT>
189  assert(!isInvalid() && "Loop not in a valid state!");
190  // Keep track of nodes outside the loop branching to the header...
191  BlockT *Out = nullptr;
192 
193  // Loop over the predecessors of the header node...
194  BlockT *Header = getHeader();
195  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
196  if (!contains(Pred)) { // If the block is not in the loop...
197  if (Out && Out != Pred)
198  return nullptr; // Multiple predecessors outside the loop
199  Out = Pred;
200  }
201  }
202 
203  // Make sure there is only one exit out of the preheader.
204  assert(Out && "Header of loop has no predecessors from outside loop?");
205  return Out;
206 }
207 
208 /// getLoopLatch - If there is a single latch block for this loop, return it.
209 /// A latch block is a block that contains a branch back to the header.
210 template <class BlockT, class LoopT>
212  assert(!isInvalid() && "Loop not in a valid state!");
213  BlockT *Header = getHeader();
214  BlockT *Latch = nullptr;
215  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
216  if (contains(Pred)) {
217  if (Latch)
218  return nullptr;
219  Latch = Pred;
220  }
221  }
222 
223  return Latch;
224 }
225 
226 //===----------------------------------------------------------------------===//
227 // APIs for updating loop information after changing the CFG
228 //
229 
230 /// addBasicBlockToLoop - This method is used by other analyses to update loop
231 /// information. NewBB is set to be a new member of the current loop.
232 /// Because of this, it is added as a member of all parent loops, and is added
233 /// to the specified LoopInfo object as being in the current basic block. It
234 /// is not valid to replace the loop header with this method.
235 ///
236 template <class BlockT, class LoopT>
238  BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
239  assert(!isInvalid() && "Loop not in a valid state!");
240 #ifndef NDEBUG
241  if (!Blocks.empty()) {
242  auto SameHeader = LIB[getHeader()];
243  assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
244  "Incorrect LI specified for this loop!");
245  }
246 #endif
247  assert(NewBB && "Cannot add a null basic block to the loop!");
248  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
249 
250  LoopT *L = static_cast<LoopT *>(this);
251 
252  // Add the loop mapping to the LoopInfo object...
253  LIB.BBMap[NewBB] = L;
254 
255  // Add the basic block to this loop and all parent loops...
256  while (L) {
257  L->addBlockEntry(NewBB);
258  L = L->getParentLoop();
259  }
260 }
261 
262 /// replaceChildLoopWith - This is used when splitting loops up. It replaces
263 /// the OldChild entry in our children list with NewChild, and updates the
264 /// parent pointer of OldChild to be null and the NewChild to be this loop.
265 /// This updates the loop depth of the new child.
266 template <class BlockT, class LoopT>
268  LoopT *NewChild) {
269  assert(!isInvalid() && "Loop not in a valid state!");
270  assert(OldChild->ParentLoop == this && "This loop is already broken!");
271  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
272  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
273  assert(I != SubLoops.end() && "OldChild not in loop!");
274  *I = NewChild;
275  OldChild->ParentLoop = nullptr;
276  NewChild->ParentLoop = static_cast<LoopT *>(this);
277 }
278 
279 /// verifyLoop - Verify loop structure
280 template <class BlockT, class LoopT>
282  assert(!isInvalid() && "Loop not in a valid state!");
283 #ifndef NDEBUG
284  assert(!Blocks.empty() && "Loop header is missing");
285 
286  // Setup for using a depth-first iterator to visit every block in the loop.
287  SmallVector<BlockT *, 8> ExitBBs;
288  getExitBlocks(ExitBBs);
290  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
292  BI = df_ext_begin(getHeader(), VisitSet),
293  BE = df_ext_end(getHeader(), VisitSet);
294 
295  // Keep track of the BBs visited.
296  SmallPtrSet<BlockT *, 8> VisitedBBs;
297 
298  // Check the individual blocks.
299  for (; BI != BE; ++BI) {
300  BlockT *BB = *BI;
301 
304  [&](BlockT *B) { return contains(B); }) &&
305  "Loop block has no in-loop successors!");
306 
308  GraphTraits<Inverse<BlockT *>>::child_end(BB),
309  [&](BlockT *B) { return contains(B); }) &&
310  "Loop block has no in-loop predecessors!");
311 
312  SmallVector<BlockT *, 2> OutsideLoopPreds;
313  std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
314  GraphTraits<Inverse<BlockT *>>::child_end(BB),
315  [&](BlockT *B) {
316  if (!contains(B))
317  OutsideLoopPreds.push_back(B);
318  });
319 
320  if (BB == getHeader()) {
321  assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
322  } else if (!OutsideLoopPreds.empty()) {
323  // A non-header loop shouldn't be reachable from outside the loop,
324  // though it is permitted if the predecessor is not itself actually
325  // reachable.
326  BlockT *EntryBB = &BB->getParent()->front();
327  for (BlockT *CB : depth_first(EntryBB))
328  for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
329  assert(CB != OutsideLoopPreds[i] &&
330  "Loop has multiple entry points!");
331  }
332  assert(BB != &getHeader()->getParent()->front() &&
333  "Loop contains function entry block!");
334 
335  VisitedBBs.insert(BB);
336  }
337 
338  if (VisitedBBs.size() != getNumBlocks()) {
339  dbgs() << "The following blocks are unreachable in the loop: ";
340  for (auto BB : Blocks) {
341  if (!VisitedBBs.count(BB)) {
342  dbgs() << *BB << "\n";
343  }
344  }
345  assert(false && "Unreachable block in loop");
346  }
347 
348  // Check the subloops.
349  for (iterator I = begin(), E = end(); I != E; ++I)
350  // Each block in each subloop should be contained within this loop.
351  for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
352  BI != BE; ++BI) {
353  assert(contains(*BI) &&
354  "Loop does not contain all the blocks of a subloop!");
355  }
356 
357  // Check the parent loop pointer.
358  if (ParentLoop) {
359  assert(is_contained(*ParentLoop, this) &&
360  "Loop is not a subloop of its parent!");
361  }
362 #endif
363 }
364 
365 /// verifyLoop - Verify loop structure of this loop and all nested loops.
366 template <class BlockT, class LoopT>
369  assert(!isInvalid() && "Loop not in a valid state!");
370  Loops->insert(static_cast<const LoopT *>(this));
371  // Verify this loop.
372  verifyLoop();
373  // Verify the subloops.
374  for (iterator I = begin(), E = end(); I != E; ++I)
375  (*I)->verifyLoopNest(Loops);
376 }
377 
378 template <class BlockT, class LoopT>
380  bool Verbose) const {
381  OS.indent(Depth * 2);
382  if (static_cast<const LoopT *>(this)->isAnnotatedParallel())
383  OS << "Parallel ";
384  OS << "Loop at depth " << getLoopDepth() << " containing: ";
385 
386  BlockT *H = getHeader();
387  for (unsigned i = 0; i < getBlocks().size(); ++i) {
388  BlockT *BB = getBlocks()[i];
389  if (!Verbose) {
390  if (i)
391  OS << ",";
392  BB->printAsOperand(OS, false);
393  } else
394  OS << "\n";
395 
396  if (BB == H)
397  OS << "<header>";
398  if (isLoopLatch(BB))
399  OS << "<latch>";
400  if (isLoopExiting(BB))
401  OS << "<exiting>";
402  if (Verbose)
403  BB->print(OS);
404  }
405  OS << "\n";
406 
407  for (iterator I = begin(), E = end(); I != E; ++I)
408  (*I)->print(OS, Depth + 2);
409 }
410 
411 //===----------------------------------------------------------------------===//
412 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
413 /// result does / not depend on use list (block predecessor) order.
414 ///
415 
416 /// Discover a subloop with the specified backedges such that: All blocks within
417 /// this loop are mapped to this loop or a subloop. And all subloops within this
418 /// loop have their parent loop set to this loop or a subloop.
419 template <class BlockT, class LoopT>
420 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
422  const DomTreeBase<BlockT> &DomTree) {
423  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
424 
425  unsigned NumBlocks = 0;
426  unsigned NumSubloops = 0;
427 
428  // Perform a backward CFG traversal using a worklist.
429  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
430  while (!ReverseCFGWorklist.empty()) {
431  BlockT *PredBB = ReverseCFGWorklist.back();
432  ReverseCFGWorklist.pop_back();
433 
434  LoopT *Subloop = LI->getLoopFor(PredBB);
435  if (!Subloop) {
436  if (!DomTree.isReachableFromEntry(PredBB))
437  continue;
438 
439  // This is an undiscovered block. Map it to the current loop.
440  LI->changeLoopFor(PredBB, L);
441  ++NumBlocks;
442  if (PredBB == L->getHeader())
443  continue;
444  // Push all block predecessors on the worklist.
445  ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
446  InvBlockTraits::child_begin(PredBB),
447  InvBlockTraits::child_end(PredBB));
448  } else {
449  // This is a discovered block. Find its outermost discovered loop.
450  while (LoopT *Parent = Subloop->getParentLoop())
451  Subloop = Parent;
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->getParentLoop())
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>
570  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
571  // The outer-most loop actually goes into the result in the same relative
572  // order as we walk it. But LoopInfo stores the top level loops in reverse
573  // program order so for here we reverse it to get forward program order.
574  // FIXME: If we change the order of LoopInfo we will want to remove the
575  // reverse here.
576  for (LoopT *RootL : reverse(*this)) {
577  auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
578  PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
579  PreOrderLoopsInRootL.end());
580  }
581 
582  return PreOrderLoops;
583 }
584 
585 template <class BlockT, class LoopT>
588  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
589  // The outer-most loop actually goes into the result in the same relative
590  // order as we walk it. LoopInfo stores the top level loops in reverse
591  // program order so we walk in order here.
592  // FIXME: If we change the order of LoopInfo we will want to add a reverse
593  // here.
594  for (LoopT *RootL : *this) {
595  assert(PreOrderWorklist.empty() &&
596  "Must start with an empty preorder walk worklist.");
597  PreOrderWorklist.push_back(RootL);
598  do {
599  LoopT *L = PreOrderWorklist.pop_back_val();
600  // Sub-loops are stored in forward program order, but will process the
601  // worklist backwards so we can just append them in order.
602  PreOrderWorklist.append(L->begin(), L->end());
603  PreOrderLoops.push_back(L);
604  } while (!PreOrderWorklist.empty());
605  }
606 
607  return PreOrderLoops;
608 }
609 
610 // Debugging
611 template <class BlockT, class LoopT>
613  for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
614  TopLevelLoops[i]->print(OS);
615 #if 0
617  E = BBMap.end(); I != E; ++I)
618  OS << "BB '" << I->first->getName() << "' level = "
619  << I->second->getLoopDepth() << "\n";
620 #endif
621 }
622 
623 template <typename T>
624 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
625  llvm::sort(BB1);
626  llvm::sort(BB2);
627  return BB1 == BB2;
628 }
629 
630 template <class BlockT, class LoopT>
632  const LoopInfoBase<BlockT, LoopT> &LI,
633  const LoopT &L) {
634  LoopHeaders[L.getHeader()] = &L;
635  for (LoopT *SL : L)
636  addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
637 }
638 
639 #ifndef NDEBUG
640 template <class BlockT, class LoopT>
641 static void compareLoops(const LoopT *L, const LoopT *OtherL,
642  DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
643  BlockT *H = L->getHeader();
644  BlockT *OtherH = OtherL->getHeader();
645  assert(H == OtherH &&
646  "Mismatched headers even though found in the same map entry!");
647 
648  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
649  "Mismatched loop depth!");
650  const LoopT *ParentL = L, *OtherParentL = OtherL;
651  do {
652  assert(ParentL->getHeader() == OtherParentL->getHeader() &&
653  "Mismatched parent loop headers!");
654  ParentL = ParentL->getParentLoop();
655  OtherParentL = OtherParentL->getParentLoop();
656  } while (ParentL);
657 
658  for (const LoopT *SubL : *L) {
659  BlockT *SubH = SubL->getHeader();
660  const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
661  assert(OtherSubL && "Inner loop is missing in computed loop info!");
662  OtherLoopHeaders.erase(SubH);
663  compareLoops(SubL, OtherSubL, OtherLoopHeaders);
664  }
665 
666  std::vector<BlockT *> BBs = L->getBlocks();
667  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
668  assert(compareVectors(BBs, OtherBBs) &&
669  "Mismatched basic blocks in the loops!");
670 
671  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
672  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = L->getBlocksSet();
673  assert(BlocksSet.size() == OtherBlocksSet.size() &&
674  std::all_of(BlocksSet.begin(), BlocksSet.end(),
675  [&OtherBlocksSet](const BlockT *BB) {
676  return OtherBlocksSet.count(BB);
677  }) &&
678  "Mismatched basic blocks in BlocksSets!");
679 }
680 #endif
681 
682 template <class BlockT, class LoopT>
684  const DomTreeBase<BlockT> &DomTree) const {
686  for (iterator I = begin(), E = end(); I != E; ++I) {
687  assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
688  (*I)->verifyLoopNest(&Loops);
689  }
690 
691 // Verify that blocks are mapped to valid loops.
692 #ifndef NDEBUG
693  for (auto &Entry : BBMap) {
694  const BlockT *BB = Entry.first;
695  LoopT *L = Entry.second;
696  assert(Loops.count(L) && "orphaned loop");
697  assert(L->contains(BB) && "orphaned block");
698  for (LoopT *ChildLoop : *L)
699  assert(!ChildLoop->contains(BB) &&
700  "BBMap should point to the innermost loop containing BB");
701  }
702 
703  // Recompute LoopInfo to verify loops structure.
705  OtherLI.analyze(DomTree);
706 
707  // Build a map we can use to move from our LI to the computed one. This
708  // allows us to ignore the particular order in any layer of the loop forest
709  // while still comparing the structure.
710  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
711  for (LoopT *L : OtherLI)
712  addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
713 
714  // Walk the top level loops and ensure there is a corresponding top-level
715  // loop in the computed version and then recursively compare those loop
716  // nests.
717  for (LoopT *L : *this) {
718  BlockT *Header = L->getHeader();
719  const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
720  assert(OtherL && "Top level loop is missing in computed loop info!");
721  // Now that we've matched this loop, erase its header from the map.
722  OtherLoopHeaders.erase(Header);
723  // And recursively compare these loops.
724  compareLoops(L, OtherL, OtherLoopHeaders);
725  }
726 
727  // Any remaining entries in the map are loops which were found when computing
728  // a fresh LoopInfo but not present in the current one.
729  if (!OtherLoopHeaders.empty()) {
730  for (const auto &HeaderAndLoop : OtherLoopHeaders)
731  dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
732  llvm_unreachable("Found new loops when recomputing LoopInfo!");
733  }
734 #endif
735 }
736 
737 } // End llvm namespace
738 
739 #endif
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:211
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static void compareLoops(const LoopT *L, const LoopT *OtherL, DenseMap< BlockT *, const LoopT *> &OtherLoopHeaders)
Definition: LoopInfoImpl.h:641
iterator begin() const
Definition: ArrayRef.h:136
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
Definition: LoopInfoImpl.h:624
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:85
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
void push_back(const T &Elt)
Definition: SmallVector.h:211
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
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:420
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
This is used when splitting loops up.
Definition: LoopInfoImpl.h:267
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
Definition: LoopInfoImpl.h:503
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:1165
return AArch64::GPR64RegClass contains(Reg)
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:683
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:379
Hexagon Hardware Loops
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:928
std::vector< Loop *>::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:900
void addInnerLoopsToHeadersMap(DenseMap< BlockT *, const LoopT *> &LoopHeaders, const LoopInfoBase< BlockT, LoopT > &LI, const LoopT &L)
Definition: LoopInfoImpl.h:631
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:144
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:237
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
Definition: LoopInfoImpl.h:494
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Core dominator tree base class.
Definition: LoopInfo.h:66
NodeT * getBlock() const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
PopulateLoopsDFS(LoopInfoBase< BlockT, LoopT > *li)
Definition: LoopInfoImpl.h:484
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define H(x, y, z)
Definition: MD5.cpp:57
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:370
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:540
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
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:1172
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
iterator_range< po_iterator< T > > post_order(const T &G)
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:75
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:131
size_t size() const
Definition: SmallVector.h:52
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
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:122
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
Definition: LoopInfoImpl.h:141
size_type size() const
Definition: SmallPtrSet.h:92
BlockT * getLoopPredecessor() const
If the given loop&#39;s header has exactly one unique predecessor outside the loop, return it...
Definition: LoopInfoImpl.h:188
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void print(raw_ostream &OS) const
Definition: LoopInfoImpl.h:612
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
iterator end() const
Definition: ArrayRef.h:137
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
std::pair< iterator, bool > insert(NodeRef N)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
void getUniqueExitBlocksHelper(const LoopT *L, SmallVectorImpl< BlockT *> &ExitBlocks, PredicateT Pred)
Definition: LoopInfoImpl.h:101
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
void verifyLoopNest(DenseSet< const LoopT *> *Loops) const
Verify loop structure of this loop and all nested loops.
Definition: LoopInfoImpl.h:367
iterator begin() const
Definition: SmallPtrSet.h:396
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...
Definition: LoopInfoImpl.h:587
#define I(x, y, z)
Definition: MD5.cpp:58
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:960
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
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:422
iterator end() const
Definition: SmallPtrSet.h:401
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:185
SmallVector< LoopT *, 4 > getLoopsInPreorder()
Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...
Definition: LoopInfoImpl.h:569
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:281
void getUniqueExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all unique successor blocks of this loop.
Definition: LoopInfoImpl.h:115
UnaryPredicate for_each(R &&Range, UnaryPredicate P)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1158
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
Populate all loop data in a stable order during a single forward DFS.
Definition: LoopInfoImpl.h:477
This class builds and contains all of the top-level loop structures in the specified function...
Definition: LoopInfo.h:67
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:1224