LLVM  14.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 PrintNested, unsigned Depth) 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 
411  if (PrintNested) {
412  OS << "\n";
413 
414  for (iterator I = begin(), E = end(); I != E; ++I)
415  (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2);
416  }
417 }
418 
419 //===----------------------------------------------------------------------===//
420 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
421 /// result does / not depend on use list (block predecessor) order.
422 ///
423 
424 /// Discover a subloop with the specified backedges such that: All blocks within
425 /// this loop are mapped to this loop or a subloop. And all subloops within this
426 /// loop have their parent loop set to this loop or a subloop.
427 template <class BlockT, class LoopT>
428 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
430  const DomTreeBase<BlockT> &DomTree) {
431  typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits;
432 
433  unsigned NumBlocks = 0;
434  unsigned NumSubloops = 0;
435 
436  // Perform a backward CFG traversal using a worklist.
437  std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
438  while (!ReverseCFGWorklist.empty()) {
439  BlockT *PredBB = ReverseCFGWorklist.back();
440  ReverseCFGWorklist.pop_back();
441 
442  LoopT *Subloop = LI->getLoopFor(PredBB);
443  if (!Subloop) {
444  if (!DomTree.isReachableFromEntry(PredBB))
445  continue;
446 
447  // This is an undiscovered block. Map it to the current loop.
448  LI->changeLoopFor(PredBB, L);
449  ++NumBlocks;
450  if (PredBB == L->getHeader())
451  continue;
452  // Push all block predecessors on the worklist.
453  ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
454  InvBlockTraits::child_begin(PredBB),
455  InvBlockTraits::child_end(PredBB));
456  } else {
457  // This is a discovered block. Find its outermost discovered loop.
458  while (LoopT *Parent = Subloop->getParentLoop())
459  Subloop = Parent;
460 
461  // If it is already discovered to be a subloop of this loop, continue.
462  if (Subloop == L)
463  continue;
464 
465  // Discover a subloop of this loop.
466  Subloop->setParentLoop(L);
467  ++NumSubloops;
468  NumBlocks += Subloop->getBlocksVector().capacity();
469  PredBB = Subloop->getHeader();
470  // Continue traversal along predecessors that are not loop-back edges from
471  // within this subloop tree itself. Note that a predecessor may directly
472  // reach another subloop that is not yet discovered to be a subloop of
473  // this loop, which we must traverse.
474  for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) {
475  if (LI->getLoopFor(Pred) != Subloop)
476  ReverseCFGWorklist.push_back(Pred);
477  }
478  }
479  }
480  L->getSubLoopsVector().reserve(NumSubloops);
481  L->reserveBlocks(NumBlocks);
482 }
483 
484 /// Populate all loop data in a stable order during a single forward DFS.
485 template <class BlockT, class LoopT> class PopulateLoopsDFS {
487  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
488 
490 
491 public:
493 
494  void traverse(BlockT *EntryBlock);
495 
496 protected:
497  void insertIntoLoop(BlockT *Block);
498 };
499 
500 /// Top-level driver for the forward DFS within the loop.
501 template <class BlockT, class LoopT>
503  for (BlockT *BB : post_order(EntryBlock))
504  insertIntoLoop(BB);
505 }
506 
507 /// Add a single Block to its ancestor loops in PostOrder. If the block is a
508 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
509 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
510 template <class BlockT, class LoopT>
512  LoopT *Subloop = LI->getLoopFor(Block);
513  if (Subloop && Block == Subloop->getHeader()) {
514  // We reach this point once per subloop after processing all the blocks in
515  // the subloop.
516  if (!Subloop->isOutermost())
517  Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
518  else
519  LI->addTopLevelLoop(Subloop);
520 
521  // For convenience, Blocks and Subloops are inserted in postorder. Reverse
522  // the lists, except for the loop header, which is always at the beginning.
523  Subloop->reverseBlock(1);
524  std::reverse(Subloop->getSubLoopsVector().begin(),
525  Subloop->getSubLoopsVector().end());
526 
527  Subloop = Subloop->getParentLoop();
528  }
529  for (; Subloop; Subloop = Subloop->getParentLoop())
530  Subloop->addBlockEntry(Block);
531 }
532 
533 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
534 /// interleaved with backward CFG traversals within each subloop
535 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
536 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
537 /// Block vectors are then populated during a single forward CFG traversal
538 /// (PopulateLoopDFS).
539 ///
540 /// During the two CFG traversals each block is seen three times:
541 /// 1) Discovered and mapped by a reverse CFG traversal.
542 /// 2) Visited during a forward DFS CFG traversal.
543 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
544 ///
545 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
546 /// insertions per block.
547 template <class BlockT, class LoopT>
549  // Postorder traversal of the dominator tree.
550  const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode();
551  for (auto DomNode : post_order(DomRoot)) {
552 
553  BlockT *Header = DomNode->getBlock();
554  SmallVector<BlockT *, 4> Backedges;
555 
556  // Check each predecessor of the potential loop header.
557  for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
558  // If Header dominates predBB, this is a new loop. Collect the backedges.
559  if (DomTree.dominates(Header, Backedge) &&
560  DomTree.isReachableFromEntry(Backedge)) {
561  Backedges.push_back(Backedge);
562  }
563  }
564  // Perform a backward CFG traversal to discover and map blocks in this loop.
565  if (!Backedges.empty()) {
566  LoopT *L = AllocateLoop(Header);
567  discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree);
568  }
569  }
570  // Perform a single forward CFG traversal to populate block and subloop
571  // vectors for all loops.
573  DFS.traverse(DomRoot->getBlock());
574 }
575 
576 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
---------------------— PointerInfo ------------------------------------—
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: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: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:428
llvm::PopulateLoopsDFS
Populate all loop data in a stable order during a single forward DFS.
Definition: LoopInfoImpl.h:485
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1005
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:302
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
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:492
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:163
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:577
llvm::LoopInfoBase::analyze
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
Definition: LoopInfoImpl.h:548
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
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:53
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:632
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:502
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:1540
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:1567
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:57
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:967
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:1612
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())
SI
StandardInstrumentations SI(Debug, VerifyEach)
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::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:1554
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:776
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:486
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: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:153
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:1488
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:595
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:939
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:384
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:511
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:154
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