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
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/PostOrderIterator.h"
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>
getExitingBlocks(SmallVectorImpl<BlockT * > & ExitingBlocks)34 void LoopBase<BlockT, LoopT>::getExitingBlocks(
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>
getExitingBlock()49 BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
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>
getExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)62 void LoopBase<BlockT, LoopT>::getExitBlocks(
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>
hasNoExitBlocks()73 bool LoopBase<BlockT, LoopT>::hasNoExitBlocks() const {
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>
getExitBlock()82 BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
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>
hasDedicatedExits()92 bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
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>
getUniqueExitBlocksHelper(const LoopT * L,SmallVectorImpl<BlockT * > & ExitBlocks,PredicateT Pred)108 void getUniqueExitBlocksHelper(const LoopT *L,
109 SmallVectorImpl<BlockT *> &ExitBlocks,
110 PredicateT Pred) {
111 assert(!L->isInvalid() && "Loop not in a valid state!");
112 SmallPtrSet<BlockT *, 32> Visited;
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>
getUniqueExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)122 void LoopBase<BlockT, LoopT>::getUniqueExitBlocks(
123 SmallVectorImpl<BlockT *> &ExitBlocks) const {
124 getUniqueExitBlocksHelper(this, ExitBlocks,
125 [](const BlockT *BB) { return true; });
126 }
127
128 template <class BlockT, class LoopT>
getUniqueNonLatchExitBlocks(SmallVectorImpl<BlockT * > & ExitBlocks)129 void LoopBase<BlockT, LoopT>::getUniqueNonLatchExitBlocks(
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>
getUniqueExitBlock()138 BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const {
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>
getExitEdges(SmallVectorImpl<Edge> & ExitEdges)148 void LoopBase<BlockT, LoopT>::getExitEdges(
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>
getLoopPreheader()167 BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
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>
getLoopPredecessor()195 BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
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>
getLoopLatch()216 BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
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>
addBasicBlockToLoop(BlockT * NewBB,LoopInfoBase<BlockT,LoopT> & LIB)242 void LoopBase<BlockT, LoopT>::addBasicBlockToLoop(
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>
replaceChildLoopWith(LoopT * OldChild,LoopT * NewChild)272 void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild,
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>
verifyLoop()286 void LoopBase<BlockT, LoopT>::verifyLoop() const {
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);
294 df_iterator_default_set<BlockT *> VisitSet;
295 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
296 df_ext_iterator<BlockT *, df_iterator_default_set<BlockT *>>
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
307 assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB),
308 GraphTraits<BlockT *>::child_end(BB),
309 [&](BlockT *B) { return contains(B); }) &&
310 "Loop block has no in-loop successors!");
311
312 assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
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;
318 std::for_each(GraphTraits<Inverse<BlockT *>>::child_begin(BB),
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>
verifyLoopNest(DenseSet<const LoopT * > * Loops)372 void LoopBase<BlockT, LoopT>::verifyLoopNest(
373 DenseSet<const LoopT *> *Loops) const {
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>
print(raw_ostream & OS,bool Verbose,bool PrintNested,unsigned Depth)384 void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, bool Verbose,
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>
discoverAndMapSubloop(LoopT * L,ArrayRef<BlockT * > Backedges,LoopInfoBase<BlockT,LoopT> * LI,const DomTreeBase<BlockT> & DomTree)428 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges,
429 LoopInfoBase<BlockT, LoopT> *LI,
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 {
486 typedef GraphTraits<BlockT *> BlockTraits;
487 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
488
489 LoopInfoBase<BlockT, LoopT> *LI;
490
491 public:
PopulateLoopsDFS(LoopInfoBase<BlockT,LoopT> * li)492 PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {}
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>
traverse(BlockT * EntryBlock)502 void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
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>
insertIntoLoop(BlockT * Block)511 void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
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>
analyze(const DomTreeBase<BlockT> & DomTree)548 void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) {
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.
572 PopulateLoopsDFS<BlockT, LoopT> DFS(this);
573 DFS.traverse(DomRoot->getBlock());
574 }
575
576 template <class BlockT, class LoopT>
getLoopsInPreorder()577 SmallVector<LoopT *, 4> LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() {
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>
594 SmallVector<LoopT *, 4>
getLoopsInReverseSiblingPreorder()595 LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() {
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>
print(raw_ostream & OS)620 void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
621 for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
622 TopLevelLoops[i]->print(OS);
623 #if 0
624 for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
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>
compareVectors(std::vector<T> & BB1,std::vector<T> & BB2)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>
addInnerLoopsToHeadersMap(DenseMap<BlockT *,const LoopT * > & LoopHeaders,const LoopInfoBase<BlockT,LoopT> & LI,const LoopT & L)639 void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
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>
compareLoops(const LoopT * L,const LoopT * OtherL,DenseMap<BlockT *,const LoopT * > & OtherLoopHeaders)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>
verify(const DomTreeBase<BlockT> & DomTree)689 void LoopInfoBase<BlockT, LoopT>::verify(
690 const DomTreeBase<BlockT> &DomTree) const {
691 DenseSet<const LoopT *> Loops;
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.
710 LoopInfoBase<BlockT, LoopT> OtherLI;
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
746