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