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  return Out;
204 }
205 
206 /// getLoopLatch - If there is a single latch block for this loop, return it.
207 /// A latch block is a block that contains a branch back to the header.
208 template <class BlockT, class LoopT>
210  assert(!isInvalid() && "Loop not in a valid state!");
211  BlockT *Header = getHeader();
212  BlockT *Latch = nullptr;
213  for (const auto Pred : children<Inverse<BlockT *>>(Header)) {
214  if (contains(Pred)) {
215  if (Latch)
216  return nullptr;
217  Latch = Pred;
218  }
219  }
220 
221  return Latch;
222 }
223 
224 //===----------------------------------------------------------------------===//
225 // APIs for updating loop information after changing the CFG
226 //
227 
228 /// addBasicBlockToLoop - This method is used by other analyses to update loop
229 /// information. NewBB is set to be a new member of the current loop.
230 /// Because of this, it is added as a member of all parent loops, and is added
231 /// to the specified LoopInfo object as being in the current basic block. It
232 /// is not valid to replace the loop header with this method.
233 ///
234 template <class BlockT, class LoopT>
236  BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
237  assert(!isInvalid() && "Loop not in a valid state!");
238 #ifndef NDEBUG
239  if (!Blocks.empty()) {
240  auto SameHeader = LIB[getHeader()];
241  assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() &&
242  "Incorrect LI specified for this loop!");
243  }
244 #endif
245  assert(NewBB && "Cannot add a null basic block to the loop!");
246  assert(!LIB[NewBB] && "BasicBlock already in the loop!");
247 
248  LoopT *L = static_cast<LoopT *>(this);
249 
250  // Add the loop mapping to the LoopInfo object...
251  LIB.BBMap[NewBB] = L;
252 
253  // Add the basic block to this loop and all parent loops...
254  while (L) {
255  L->addBlockEntry(NewBB);
256  L = L->getParentLoop();
257  }
258 }
259 
260 /// replaceChildLoopWith - This is used when splitting loops up. It replaces
261 /// the OldChild entry in our children list with NewChild, and updates the
262 /// parent pointer of OldChild to be null and the NewChild to be this loop.
263 /// This updates the loop depth of the new child.
264 template <class BlockT, class LoopT>
266  LoopT *NewChild) {
267  assert(!isInvalid() && "Loop not in a valid state!");
268  assert(OldChild->ParentLoop == this && "This loop is already broken!");
269  assert(!NewChild->ParentLoop && "NewChild already has a parent!");
270  typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild);
271  assert(I != SubLoops.end() && "OldChild not in loop!");
272  *I = NewChild;
273  OldChild->ParentLoop = nullptr;
274  NewChild->ParentLoop = static_cast<LoopT *>(this);
275 }
276 
277 /// verifyLoop - Verify loop structure
278 template <class BlockT, class LoopT>
280  assert(!isInvalid() && "Loop not in a valid state!");
281 #ifndef NDEBUG
282  assert(!Blocks.empty() && "Loop header is missing");
283 
284  // Setup for using a depth-first iterator to visit every block in the loop.
285  SmallVector<BlockT *, 8> ExitBBs;
286  getExitBlocks(ExitBBs);
288  VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
290  BI = df_ext_begin(getHeader(), VisitSet),
291  BE = df_ext_end(getHeader(), VisitSet);
292 
293  // Keep track of the BBs visited.
294  SmallPtrSet<BlockT *, 8> VisitedBBs;
295 
296  // Check the individual blocks.
297  for (; BI != BE; ++BI) {
298  BlockT *BB = *BI;
299 
302  [&](BlockT *B) { return contains(B); }) &&
303  "Loop block has no in-loop successors!");
304 
306  GraphTraits<Inverse<BlockT *>>::child_end(BB),
307  [&](BlockT *B) { return contains(B); }) &&
308  "Loop block has no in-loop predecessors!");
309 
310  SmallVector<BlockT *, 2> OutsideLoopPreds;
311  std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
312  GraphTraits<Inverse<BlockT *>>::child_end(BB),
313  [&](BlockT *B) {
314  if (!contains(B))
315  OutsideLoopPreds.push_back(B);
316  });
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 Verbose) 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  OS << "\n";
404 
405  for (iterator I = begin(), E = end(); I != E; ++I)
406  (*I)->print(OS, Depth + 2);
407 }
408 
409 //===----------------------------------------------------------------------===//
410 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
411 /// result does / not depend on use list (block predecessor) order.
412 ///
413 
414 /// Discover a subloop with the specified backedges such that: All blocks within
415 /// this loop are mapped to this loop or a subloop. And all subloops within this
416 /// loop have their parent loop set to this loop or a subloop.
417 template <class BlockT, class LoopT>
418 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
420  const DomTreeBase<BlockT> &DomTree) {
421  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
422 
423  unsigned NumBlocks = 0;
424  unsigned NumSubloops = 0;
425 
426  // Perform a backward CFG traversal using a worklist.
427  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
428  while (!ReverseCFGWorklist.empty()) {
429  BlockT *PredBB = ReverseCFGWorklist.back();
430  ReverseCFGWorklist.pop_back();
431 
432  LoopT *Subloop = LI->getLoopFor(PredBB);
433  if (!Subloop) {
434  if (!DomTree.isReachableFromEntry(PredBB))
435  continue;
436 
437  // This is an undiscovered block. Map it to the current loop.
438  LI->changeLoopFor(PredBB, L);
439  ++NumBlocks;
440  if (PredBB == L->getHeader())
441  continue;
442  // Push all block predecessors on the worklist.
443  ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
444  InvBlockTraits::child_begin(PredBB),
445  InvBlockTraits::child_end(PredBB));
446  } else {
447  // This is a discovered block. Find its outermost discovered loop.
448  while (LoopT *Parent = Subloop->getParentLoop())
449  Subloop = Parent;
450 
451  // If it is already discovered to be a subloop of this loop, continue.
452  if (Subloop == L)
453  continue;
454 
455  // Discover a subloop of this loop.
456  Subloop->setParentLoop(L);
457  ++NumSubloops;
458  NumBlocks += Subloop->getBlocksVector().capacity();
459  PredBB = Subloop->getHeader();
460  // Continue traversal along predecessors that are not loop-back edges from
461  // within this subloop tree itself. Note that a predecessor may directly
462  // reach another subloop that is not yet discovered to be a subloop of
463  // this loop, which we must traverse.
464  for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
465  if (LI->getLoopFor(Pred) != Subloop)
466  ReverseCFGWorklist.push_back(Pred);
467  }
468  }
469  }
470  L->getSubLoopsVector().reserve(NumSubloops);
471  L->reserveBlocks(NumBlocks);
472 }
473 
474 /// Populate all loop data in a stable order during a single forward DFS.
475 template <class BlockT, class LoopT> class PopulateLoopsDFS {
477  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
478 
480 
481 public:
483 
484  void traverse(BlockT *EntryBlock);
485 
486 protected:
487  void insertIntoLoop(BlockT *Block);
488 };
489 
490 /// Top-level driver for the forward DFS within the loop.
491 template <class BlockT, class LoopT>
493  for (BlockT *BB : post_order(EntryBlock))
494  insertIntoLoop(BB);
495 }
496 
497 /// Add a single Block to its ancestor loops in PostOrder. If the block is a
498 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
499 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
500 template <class BlockT, class LoopT>
502  LoopT *Subloop = LI->getLoopFor(Block);
503  if (Subloop && Block == Subloop->getHeader()) {
504  // We reach this point once per subloop after processing all the blocks in
505  // the subloop.
506  if (Subloop->getParentLoop())
507  Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
508  else
509  LI->addTopLevelLoop(Subloop);
510 
511  // For convenience, Blocks and Subloops are inserted in postorder. Reverse
512  // the lists, except for the loop header, which is always at the beginning.
513  Subloop->reverseBlock(1);
514  std::reverse(Subloop->getSubLoopsVector().begin(),
515  Subloop->getSubLoopsVector().end());
516 
517  Subloop = Subloop->getParentLoop();
518  }
519  for (; Subloop; Subloop = Subloop->getParentLoop())
520  Subloop->addBlockEntry(Block);
521 }
522 
523 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
524 /// interleaved with backward CFG traversals within each subloop
525 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
526 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
527 /// Block vectors are then populated during a single forward CFG traversal
528 /// (PopulateLoopDFS).
529 ///
530 /// During the two CFG traversals each block is seen three times:
531 /// 1) Discovered and mapped by a reverse CFG traversal.
532 /// 2) Visited during a forward DFS CFG traversal.
533 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
534 ///
535 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
536 /// insertions per block.
537 template <class BlockT, class LoopT>
539  // Postorder traversal of the dominator tree.
540  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
541  for (auto DomNode : post_order(DomRoot)) {
542 
543  BlockT *Header = DomNode->getBlock();
544  SmallVector<BlockT *, 4> Backedges;
545 
546  // Check each predecessor of the potential loop header.
547  for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
548  // If Header dominates predBB, this is a new loop. Collect the backedges.
549  if (DomTree.dominates(Header, Backedge) &&
550  DomTree.isReachableFromEntry(Backedge)) {
551  Backedges.push_back(Backedge);
552  }
553  }
554  // Perform a backward CFG traversal to discover and map blocks in this loop.
555  if (!Backedges.empty()) {
556  LoopT *L = AllocateLoop(Header);
557  discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
558  }
559  }
560  // Perform a single forward CFG traversal to populate block and subloop
561  // vectors for all loops.
563  DFS.traverse(DomRoot->getBlock());
564 }
565 
566 template <class BlockT, class LoopT>
568  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
569  // The outer-most loop actually goes into the result in the same relative
570  // order as we walk it. But LoopInfo stores the top level loops in reverse
571  // program order so for here we reverse it to get forward program order.
572  // FIXME: If we change the order of LoopInfo we will want to remove the
573  // reverse here.
574  for (LoopT *RootL : reverse(*this)) {
575  auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder();
576  PreOrderLoops.append(PreOrderLoopsInRootL.begin(),
577  PreOrderLoopsInRootL.end());
578  }
579 
580  return PreOrderLoops;
581 }
582 
583 template <class BlockT, class LoopT>
586  SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist;
587  // The outer-most loop actually goes into the result in the same relative
588  // order as we walk it. LoopInfo stores the top level loops in reverse
589  // program order so we walk in order here.
590  // FIXME: If we change the order of LoopInfo we will want to add a reverse
591  // here.
592  for (LoopT *RootL : *this) {
593  assert(PreOrderWorklist.empty() &&
594  "Must start with an empty preorder walk worklist.");
595  PreOrderWorklist.push_back(RootL);
596  do {
597  LoopT *L = PreOrderWorklist.pop_back_val();
598  // Sub-loops are stored in forward program order, but will process the
599  // worklist backwards so we can just append them in order.
600  PreOrderWorklist.append(L->begin(), L->end());
601  PreOrderLoops.push_back(L);
602  } while (!PreOrderWorklist.empty());
603  }
604 
605  return PreOrderLoops;
606 }
607 
608 // Debugging
609 template <class BlockT, class LoopT>
611  for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
612  TopLevelLoops[i]->print(OS);
613 #if 0
615  E = BBMap.end(); I != E; ++I)
616  OS << "BB '" << I->first->getName() << "' level = "
617  << I->second->getLoopDepth() << "\n";
618 #endif
619 }
620 
621 template <typename T>
622 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
623  llvm::sort(BB1);
624  llvm::sort(BB2);
625  return BB1 == BB2;
626 }
627 
628 template <class BlockT, class LoopT>
630  const LoopInfoBase<BlockT, LoopT> &LI,
631  const LoopT &L) {
632  LoopHeaders[L.getHeader()] = &L;
633  for (LoopT *SL : L)
634  addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL);
635 }
636 
637 #ifndef NDEBUG
638 template <class BlockT, class LoopT>
639 static void compareLoops(const LoopT *L, const LoopT *OtherL,
640  DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) {
641  BlockT *H = L->getHeader();
642  BlockT *OtherH = OtherL->getHeader();
643  assert(H == OtherH &&
644  "Mismatched headers even though found in the same map entry!");
645 
646  assert(L->getLoopDepth() == OtherL->getLoopDepth() &&
647  "Mismatched loop depth!");
648  const LoopT *ParentL = L, *OtherParentL = OtherL;
649  do {
650  assert(ParentL->getHeader() == OtherParentL->getHeader() &&
651  "Mismatched parent loop headers!");
652  ParentL = ParentL->getParentLoop();
653  OtherParentL = OtherParentL->getParentLoop();
654  } while (ParentL);
655 
656  for (const LoopT *SubL : *L) {
657  BlockT *SubH = SubL->getHeader();
658  const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH);
659  assert(OtherSubL && "Inner loop is missing in computed loop info!");
660  OtherLoopHeaders.erase(SubH);
661  compareLoops(SubL, OtherSubL, OtherLoopHeaders);
662  }
663 
664  std::vector<BlockT *> BBs = L->getBlocks();
665  std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
666  assert(compareVectors(BBs, OtherBBs) &&
667  "Mismatched basic blocks in the loops!");
668 
669  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
670  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = L->getBlocksSet();
671  assert(BlocksSet.size() == OtherBlocksSet.size() &&
672  std::all_of(BlocksSet.begin(), BlocksSet.end(),
673  [&OtherBlocksSet](const BlockT *BB) {
674  return OtherBlocksSet.count(BB);
675  }) &&
676  "Mismatched basic blocks in BlocksSets!");
677 }
678 #endif
679 
680 template <class BlockT, class LoopT>
682  const DomTreeBase<BlockT> &DomTree) const {
684  for (iterator I = begin(), E = end(); I != E; ++I) {
685  assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
686  (*I)->verifyLoopNest(&Loops);
687  }
688 
689 // Verify that blocks are mapped to valid loops.
690 #ifndef NDEBUG
691  for (auto &Entry : BBMap) {
692  const BlockT *BB = Entry.first;
693  LoopT *L = Entry.second;
694  assert(Loops.count(L) && "orphaned loop");
695  assert(L->contains(BB) && "orphaned block");
696  for (LoopT *ChildLoop : *L)
697  assert(!ChildLoop->contains(BB) &&
698  "BBMap should point to the innermost loop containing BB");
699  }
700 
701  // Recompute LoopInfo to verify loops structure.
703  OtherLI.analyze(DomTree);
704 
705  // Build a map we can use to move from our LI to the computed one. This
706  // allows us to ignore the particular order in any layer of the loop forest
707  // while still comparing the structure.
708  DenseMap<BlockT *, const LoopT *> OtherLoopHeaders;
709  for (LoopT *L : OtherLI)
710  addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L);
711 
712  // Walk the top level loops and ensure there is a corresponding top-level
713  // loop in the computed version and then recursively compare those loop
714  // nests.
715  for (LoopT *L : *this) {
716  BlockT *Header = L->getHeader();
717  const LoopT *OtherL = OtherLoopHeaders.lookup(Header);
718  assert(OtherL && "Top level loop is missing in computed loop info!");
719  // Now that we've matched this loop, erase its header from the map.
720  OtherLoopHeaders.erase(Header);
721  // And recursively compare these loops.
722  compareLoops(L, OtherL, OtherLoopHeaders);
723  }
724 
725  // Any remaining entries in the map are loops which were found when computing
726  // a fresh LoopInfo but not present in the current one.
727  if (!OtherLoopHeaders.empty()) {
728  for (const auto &HeaderAndLoop : OtherLoopHeaders)
729  dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n";
730  llvm_unreachable("Found new loops when recomputing LoopInfo!");
731  }
732 #endif
733 }
734 
735 } // End llvm namespace
736 
737 #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:209
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:639
iterator begin() const
Definition: ArrayRef.h:136
bool compareVectors(std::vector< T > &BB1, std::vector< T > &BB2)
Definition: LoopInfoImpl.h:622
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:418
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:265
void insertIntoLoop(BlockT *Block)
Add a single Block to its ancestor loops in PostOrder.
Definition: LoopInfoImpl.h:501
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:681
void print(raw_ostream &OS, unsigned Depth=0, bool Verbose=false) const
Print loop with all the BBs inside it.
Definition: LoopInfoImpl.h:377
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:629
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:235
void traverse(BlockT *EntryBlock)
Top-level driver for the forward DFS within the loop.
Definition: LoopInfoImpl.h:492
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:482
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:538
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:610
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:365
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:585
#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:567
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:279
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:475
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