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