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