1 //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This is the generic implementation of LoopInfo used for both Loops and
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
15 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
17 #include "llvm/ADT/DepthFirstIterator.h"
18 #include "llvm/ADT/PostOrderIterator.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/IR/Dominators.h"
26 //===----------------------------------------------------------------------===//
27 // APIs for simple analysis of the loop. See header notes.
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.
33 template <class BlockT
, class LoopT
>
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 (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
);
46 /// getExitingBlock - If getExitingBlocks would return exactly one block,
47 /// return that block. Otherwise return null.
48 template <class BlockT
, class LoopT
>
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];
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.
61 template <class BlockT
, class LoopT
>
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 (const auto &Succ
: children
<BlockT
*>(BB
))
68 // Not in current loop? It must be an exit block.
69 ExitBlocks
.push_back(Succ
);
72 /// getExitBlock - If getExitBlocks would return exactly one block,
73 /// return that block. Otherwise return null.
74 template <class BlockT
, class LoopT
>
75 BlockT
*LoopBase
<BlockT
, LoopT
>::getExitBlock() const {
76 assert(!isInvalid() && "Loop not in a valid state!");
77 SmallVector
<BlockT
*, 8> ExitBlocks
;
78 getExitBlocks(ExitBlocks
);
79 if (ExitBlocks
.size() == 1)
84 template <class BlockT
, class LoopT
>
85 bool LoopBase
<BlockT
, LoopT
>::hasDedicatedExits() const {
86 // Each predecessor of each exit block of a normal loop is contained
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
))
94 // All the requirements are met.
98 // Helper function to get unique loop exits. Pred is a predicate pointing to
99 // BasicBlocks in a loop which should be considered to find loop exits.
100 template <class BlockT
, class LoopT
, typename PredicateT
>
101 void getUniqueExitBlocksHelper(const LoopT
*L
,
102 SmallVectorImpl
<BlockT
*> &ExitBlocks
,
104 assert(!L
->isInvalid() && "Loop not in a valid state!");
105 SmallPtrSet
<BlockT
*, 32> Visited
;
106 auto Filtered
= make_filter_range(L
->blocks(), Pred
);
107 for (BlockT
*BB
: Filtered
)
108 for (BlockT
*Successor
: children
<BlockT
*>(BB
))
109 if (!L
->contains(Successor
))
110 if (Visited
.insert(Successor
).second
)
111 ExitBlocks
.push_back(Successor
);
114 template <class BlockT
, class LoopT
>
115 void LoopBase
<BlockT
, LoopT
>::getUniqueExitBlocks(
116 SmallVectorImpl
<BlockT
*> &ExitBlocks
) const {
117 getUniqueExitBlocksHelper(this, ExitBlocks
,
118 [](const BlockT
*BB
) { return true; });
121 template <class BlockT
, class LoopT
>
122 void LoopBase
<BlockT
, LoopT
>::getUniqueNonLatchExitBlocks(
123 SmallVectorImpl
<BlockT
*> &ExitBlocks
) const {
124 const BlockT
*Latch
= getLoopLatch();
125 assert(Latch
&& "Latch block must exists");
126 getUniqueExitBlocksHelper(this, ExitBlocks
,
127 [Latch
](const BlockT
*BB
) { return BB
!= Latch
; });
130 template <class BlockT
, class LoopT
>
131 BlockT
*LoopBase
<BlockT
, LoopT
>::getUniqueExitBlock() const {
132 SmallVector
<BlockT
*, 8> UniqueExitBlocks
;
133 getUniqueExitBlocks(UniqueExitBlocks
);
134 if (UniqueExitBlocks
.size() == 1)
135 return UniqueExitBlocks
[0];
139 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
140 template <class BlockT
, class LoopT
>
141 void LoopBase
<BlockT
, LoopT
>::getExitEdges(
142 SmallVectorImpl
<Edge
> &ExitEdges
) const {
143 assert(!isInvalid() && "Loop not in a valid state!");
144 for (const auto BB
: blocks())
145 for (const auto &Succ
: children
<BlockT
*>(BB
))
147 // Not in current loop? It must be an exit block.
148 ExitEdges
.emplace_back(BB
, Succ
);
151 /// getLoopPreheader - If there is a preheader for this loop, return it. A
152 /// loop has a preheader if there is only one edge to the header of the loop
153 /// from outside of the loop and it is legal to hoist instructions into the
154 /// predecessor. If this is the case, the block branching to the header of the
155 /// loop is the preheader node.
157 /// This method returns null if there is no preheader for the loop.
159 template <class BlockT
, class LoopT
>
160 BlockT
*LoopBase
<BlockT
, LoopT
>::getLoopPreheader() const {
161 assert(!isInvalid() && "Loop not in a valid state!");
162 // Keep track of nodes outside the loop branching to the header...
163 BlockT
*Out
= getLoopPredecessor();
167 // Make sure we are allowed to hoist instructions into the predecessor.
168 if (!Out
->isLegalToHoistInto())
171 // Make sure there is only one exit out of the preheader.
172 typedef GraphTraits
<BlockT
*> BlockTraits
;
173 typename
BlockTraits::ChildIteratorType SI
= BlockTraits::child_begin(Out
);
175 if (SI
!= BlockTraits::child_end(Out
))
176 return nullptr; // Multiple exits from the block, must not be a preheader.
178 // The predecessor has exactly one successor, so it is a preheader.
182 /// getLoopPredecessor - If the given loop's header has exactly one unique
183 /// predecessor outside the loop, return it. Otherwise return null.
184 /// This is less strict that the loop "preheader" concept, which requires
185 /// the predecessor to have exactly one successor.
187 template <class BlockT
, class LoopT
>
188 BlockT
*LoopBase
<BlockT
, LoopT
>::getLoopPredecessor() const {
189 assert(!isInvalid() && "Loop not in a valid state!");
190 // Keep track of nodes outside the loop branching to the header...
191 BlockT
*Out
= nullptr;
193 // Loop over the predecessors of the header node...
194 BlockT
*Header
= getHeader();
195 for (const auto Pred
: children
<Inverse
<BlockT
*>>(Header
)) {
196 if (!contains(Pred
)) { // If the block is not in the loop...
197 if (Out
&& Out
!= Pred
)
198 return nullptr; // Multiple predecessors outside the loop
206 /// getLoopLatch - If there is a single latch block for this loop, return it.
207 /// A latch block is a block that contains a branch back to the header.
208 template <class BlockT
, class LoopT
>
209 BlockT
*LoopBase
<BlockT
, LoopT
>::getLoopLatch() const {
210 assert(!isInvalid() && "Loop not in a valid state!");
211 BlockT
*Header
= getHeader();
212 BlockT
*Latch
= nullptr;
213 for (const auto Pred
: children
<Inverse
<BlockT
*>>(Header
)) {
214 if (contains(Pred
)) {
224 //===----------------------------------------------------------------------===//
225 // APIs for updating loop information after changing the CFG
228 /// addBasicBlockToLoop - This method is used by other analyses to update loop
229 /// information. NewBB is set to be a new member of the current loop.
230 /// Because of this, it is added as a member of all parent loops, and is added
231 /// to the specified LoopInfo object as being in the current basic block. It
232 /// is not valid to replace the loop header with this method.
234 template <class BlockT
, class LoopT
>
235 void LoopBase
<BlockT
, LoopT
>::addBasicBlockToLoop(
236 BlockT
*NewBB
, LoopInfoBase
<BlockT
, LoopT
> &LIB
) {
237 assert(!isInvalid() && "Loop not in a valid state!");
239 if (!Blocks
.empty()) {
240 auto SameHeader
= LIB
[getHeader()];
241 assert(contains(SameHeader
) && getHeader() == SameHeader
->getHeader() &&
242 "Incorrect LI specified for this loop!");
245 assert(NewBB
&& "Cannot add a null basic block to the loop!");
246 assert(!LIB
[NewBB
] && "BasicBlock already in the loop!");
248 LoopT
*L
= static_cast<LoopT
*>(this);
250 // Add the loop mapping to the LoopInfo object...
251 LIB
.BBMap
[NewBB
] = L
;
253 // Add the basic block to this loop and all parent loops...
255 L
->addBlockEntry(NewBB
);
256 L
= L
->getParentLoop();
260 /// replaceChildLoopWith - This is used when splitting loops up. It replaces
261 /// the OldChild entry in our children list with NewChild, and updates the
262 /// parent pointer of OldChild to be null and the NewChild to be this loop.
263 /// This updates the loop depth of the new child.
264 template <class BlockT
, class LoopT
>
265 void LoopBase
<BlockT
, LoopT
>::replaceChildLoopWith(LoopT
*OldChild
,
267 assert(!isInvalid() && "Loop not in a valid state!");
268 assert(OldChild
->ParentLoop
== this && "This loop is already broken!");
269 assert(!NewChild
->ParentLoop
&& "NewChild already has a parent!");
270 typename
std::vector
<LoopT
*>::iterator I
= find(SubLoops
, OldChild
);
271 assert(I
!= SubLoops
.end() && "OldChild not in loop!");
273 OldChild
->ParentLoop
= nullptr;
274 NewChild
->ParentLoop
= static_cast<LoopT
*>(this);
277 /// verifyLoop - Verify loop structure
278 template <class BlockT
, class LoopT
>
279 void LoopBase
<BlockT
, LoopT
>::verifyLoop() const {
280 assert(!isInvalid() && "Loop not in a valid state!");
282 assert(!Blocks
.empty() && "Loop header is missing");
284 // Setup for using a depth-first iterator to visit every block in the loop.
285 SmallVector
<BlockT
*, 8> ExitBBs
;
286 getExitBlocks(ExitBBs
);
287 df_iterator_default_set
<BlockT
*> VisitSet
;
288 VisitSet
.insert(ExitBBs
.begin(), ExitBBs
.end());
289 df_ext_iterator
<BlockT
*, df_iterator_default_set
<BlockT
*>>
290 BI
= df_ext_begin(getHeader(), VisitSet
),
291 BE
= df_ext_end(getHeader(), VisitSet
);
293 // Keep track of the BBs visited.
294 SmallPtrSet
<BlockT
*, 8> VisitedBBs
;
296 // Check the individual blocks.
297 for (; BI
!= BE
; ++BI
) {
300 assert(std::any_of(GraphTraits
<BlockT
*>::child_begin(BB
),
301 GraphTraits
<BlockT
*>::child_end(BB
),
302 [&](BlockT
*B
) { return contains(B
); }) &&
303 "Loop block has no in-loop successors!");
305 assert(std::any_of(GraphTraits
<Inverse
<BlockT
*>>::child_begin(BB
),
306 GraphTraits
<Inverse
<BlockT
*>>::child_end(BB
),
307 [&](BlockT
*B
) { return contains(B
); }) &&
308 "Loop block has no in-loop predecessors!");
310 SmallVector
<BlockT
*, 2> OutsideLoopPreds
;
311 std::for_each(GraphTraits
<Inverse
<BlockT
*>>::child_begin(BB
),
312 GraphTraits
<Inverse
<BlockT
*>>::child_end(BB
),
315 OutsideLoopPreds
.push_back(B
);
318 if (BB
== getHeader()) {
319 assert(!OutsideLoopPreds
.empty() && "Loop is unreachable!");
320 } else if (!OutsideLoopPreds
.empty()) {
321 // A non-header loop shouldn't be reachable from outside the loop,
322 // though it is permitted if the predecessor is not itself actually
324 BlockT
*EntryBB
= &BB
->getParent()->front();
325 for (BlockT
*CB
: depth_first(EntryBB
))
326 for (unsigned i
= 0, e
= OutsideLoopPreds
.size(); i
!= e
; ++i
)
327 assert(CB
!= OutsideLoopPreds
[i
] &&
328 "Loop has multiple entry points!");
330 assert(BB
!= &getHeader()->getParent()->front() &&
331 "Loop contains function entry block!");
333 VisitedBBs
.insert(BB
);
336 if (VisitedBBs
.size() != getNumBlocks()) {
337 dbgs() << "The following blocks are unreachable in the loop: ";
338 for (auto BB
: Blocks
) {
339 if (!VisitedBBs
.count(BB
)) {
340 dbgs() << *BB
<< "\n";
343 assert(false && "Unreachable block in loop");
346 // Check the subloops.
347 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
348 // Each block in each subloop should be contained within this loop.
349 for (block_iterator BI
= (*I
)->block_begin(), BE
= (*I
)->block_end();
351 assert(contains(*BI
) &&
352 "Loop does not contain all the blocks of a subloop!");
355 // Check the parent loop pointer.
357 assert(is_contained(*ParentLoop
, this) &&
358 "Loop is not a subloop of its parent!");
363 /// verifyLoop - Verify loop structure of this loop and all nested loops.
364 template <class BlockT
, class LoopT
>
365 void LoopBase
<BlockT
, LoopT
>::verifyLoopNest(
366 DenseSet
<const LoopT
*> *Loops
) const {
367 assert(!isInvalid() && "Loop not in a valid state!");
368 Loops
->insert(static_cast<const LoopT
*>(this));
371 // Verify the subloops.
372 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
373 (*I
)->verifyLoopNest(Loops
);
376 template <class BlockT
, class LoopT
>
377 void LoopBase
<BlockT
, LoopT
>::print(raw_ostream
&OS
, unsigned Depth
,
378 bool Verbose
) const {
379 OS
.indent(Depth
* 2);
380 if (static_cast<const LoopT
*>(this)->isAnnotatedParallel())
382 OS
<< "Loop at depth " << getLoopDepth() << " containing: ";
384 BlockT
*H
= getHeader();
385 for (unsigned i
= 0; i
< getBlocks().size(); ++i
) {
386 BlockT
*BB
= getBlocks()[i
];
390 BB
->printAsOperand(OS
, false);
398 if (isLoopExiting(BB
))
405 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
406 (*I
)->print(OS
, Depth
+ 2);
409 //===----------------------------------------------------------------------===//
410 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
411 /// result does / not depend on use list (block predecessor) order.
414 /// Discover a subloop with the specified backedges such that: All blocks within
415 /// this loop are mapped to this loop or a subloop. And all subloops within this
416 /// loop have their parent loop set to this loop or a subloop.
417 template <class BlockT
, class LoopT
>
418 static void discoverAndMapSubloop(LoopT
*L
, ArrayRef
<BlockT
*> Backedges
,
419 LoopInfoBase
<BlockT
, LoopT
> *LI
,
420 const DomTreeBase
<BlockT
> &DomTree
) {
421 typedef GraphTraits
<Inverse
<BlockT
*>> InvBlockTraits
;
423 unsigned NumBlocks
= 0;
424 unsigned NumSubloops
= 0;
426 // Perform a backward CFG traversal using a worklist.
427 std::vector
<BlockT
*> ReverseCFGWorklist(Backedges
.begin(), Backedges
.end());
428 while (!ReverseCFGWorklist
.empty()) {
429 BlockT
*PredBB
= ReverseCFGWorklist
.back();
430 ReverseCFGWorklist
.pop_back();
432 LoopT
*Subloop
= LI
->getLoopFor(PredBB
);
434 if (!DomTree
.isReachableFromEntry(PredBB
))
437 // This is an undiscovered block. Map it to the current loop.
438 LI
->changeLoopFor(PredBB
, L
);
440 if (PredBB
== L
->getHeader())
442 // Push all block predecessors on the worklist.
443 ReverseCFGWorklist
.insert(ReverseCFGWorklist
.end(),
444 InvBlockTraits::child_begin(PredBB
),
445 InvBlockTraits::child_end(PredBB
));
447 // This is a discovered block. Find its outermost discovered loop.
448 while (LoopT
*Parent
= Subloop
->getParentLoop())
451 // If it is already discovered to be a subloop of this loop, continue.
455 // Discover a subloop of this loop.
456 Subloop
->setParentLoop(L
);
458 NumBlocks
+= Subloop
->getBlocksVector().capacity();
459 PredBB
= Subloop
->getHeader();
460 // Continue traversal along predecessors that are not loop-back edges from
461 // within this subloop tree itself. Note that a predecessor may directly
462 // reach another subloop that is not yet discovered to be a subloop of
463 // this loop, which we must traverse.
464 for (const auto Pred
: children
<Inverse
<BlockT
*>>(PredBB
)) {
465 if (LI
->getLoopFor(Pred
) != Subloop
)
466 ReverseCFGWorklist
.push_back(Pred
);
470 L
->getSubLoopsVector().reserve(NumSubloops
);
471 L
->reserveBlocks(NumBlocks
);
474 /// Populate all loop data in a stable order during a single forward DFS.
475 template <class BlockT
, class LoopT
> class PopulateLoopsDFS
{
476 typedef GraphTraits
<BlockT
*> BlockTraits
;
477 typedef typename
BlockTraits::ChildIteratorType SuccIterTy
;
479 LoopInfoBase
<BlockT
, LoopT
> *LI
;
482 PopulateLoopsDFS(LoopInfoBase
<BlockT
, LoopT
> *li
) : LI(li
) {}
484 void traverse(BlockT
*EntryBlock
);
487 void insertIntoLoop(BlockT
*Block
);
490 /// Top-level driver for the forward DFS within the loop.
491 template <class BlockT
, class LoopT
>
492 void PopulateLoopsDFS
<BlockT
, LoopT
>::traverse(BlockT
*EntryBlock
) {
493 for (BlockT
*BB
: post_order(EntryBlock
))
497 /// Add a single Block to its ancestor loops in PostOrder. If the block is a
498 /// subloop header, add the subloop to its parent in PostOrder, then reverse the
499 /// Block and Subloop vectors of the now complete subloop to achieve RPO.
500 template <class BlockT
, class LoopT
>
501 void PopulateLoopsDFS
<BlockT
, LoopT
>::insertIntoLoop(BlockT
*Block
) {
502 LoopT
*Subloop
= LI
->getLoopFor(Block
);
503 if (Subloop
&& Block
== Subloop
->getHeader()) {
504 // We reach this point once per subloop after processing all the blocks in
506 if (Subloop
->getParentLoop())
507 Subloop
->getParentLoop()->getSubLoopsVector().push_back(Subloop
);
509 LI
->addTopLevelLoop(Subloop
);
511 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
512 // the lists, except for the loop header, which is always at the beginning.
513 Subloop
->reverseBlock(1);
514 std::reverse(Subloop
->getSubLoopsVector().begin(),
515 Subloop
->getSubLoopsVector().end());
517 Subloop
= Subloop
->getParentLoop();
519 for (; Subloop
; Subloop
= Subloop
->getParentLoop())
520 Subloop
->addBlockEntry(Block
);
523 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
524 /// interleaved with backward CFG traversals within each subloop
525 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
526 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
527 /// Block vectors are then populated during a single forward CFG traversal
528 /// (PopulateLoopDFS).
530 /// During the two CFG traversals each block is seen three times:
531 /// 1) Discovered and mapped by a reverse CFG traversal.
532 /// 2) Visited during a forward DFS CFG traversal.
533 /// 3) Reverse-inserted in the loop in postorder following forward DFS.
535 /// The Block vectors are inclusive, so step 3 requires loop-depth number of
536 /// insertions per block.
537 template <class BlockT
, class LoopT
>
538 void LoopInfoBase
<BlockT
, LoopT
>::analyze(const DomTreeBase
<BlockT
> &DomTree
) {
539 // Postorder traversal of the dominator tree.
540 const DomTreeNodeBase
<BlockT
> *DomRoot
= DomTree
.getRootNode();
541 for (auto DomNode
: post_order(DomRoot
)) {
543 BlockT
*Header
= DomNode
->getBlock();
544 SmallVector
<BlockT
*, 4> Backedges
;
546 // Check each predecessor of the potential loop header.
547 for (const auto Backedge
: children
<Inverse
<BlockT
*>>(Header
)) {
548 // If Header dominates predBB, this is a new loop. Collect the backedges.
549 if (DomTree
.dominates(Header
, Backedge
) &&
550 DomTree
.isReachableFromEntry(Backedge
)) {
551 Backedges
.push_back(Backedge
);
554 // Perform a backward CFG traversal to discover and map blocks in this loop.
555 if (!Backedges
.empty()) {
556 LoopT
*L
= AllocateLoop(Header
);
557 discoverAndMapSubloop(L
, ArrayRef
<BlockT
*>(Backedges
), this, DomTree
);
560 // Perform a single forward CFG traversal to populate block and subloop
561 // vectors for all loops.
562 PopulateLoopsDFS
<BlockT
, LoopT
> DFS(this);
563 DFS
.traverse(DomRoot
->getBlock());
566 template <class BlockT
, class LoopT
>
567 SmallVector
<LoopT
*, 4> LoopInfoBase
<BlockT
, LoopT
>::getLoopsInPreorder() {
568 SmallVector
<LoopT
*, 4> PreOrderLoops
, PreOrderWorklist
;
569 // The outer-most loop actually goes into the result in the same relative
570 // order as we walk it. But LoopInfo stores the top level loops in reverse
571 // program order so for here we reverse it to get forward program order.
572 // FIXME: If we change the order of LoopInfo we will want to remove the
574 for (LoopT
*RootL
: reverse(*this)) {
575 auto PreOrderLoopsInRootL
= RootL
->getLoopsInPreorder();
576 PreOrderLoops
.append(PreOrderLoopsInRootL
.begin(),
577 PreOrderLoopsInRootL
.end());
580 return PreOrderLoops
;
583 template <class BlockT
, class LoopT
>
584 SmallVector
<LoopT
*, 4>
585 LoopInfoBase
<BlockT
, LoopT
>::getLoopsInReverseSiblingPreorder() {
586 SmallVector
<LoopT
*, 4> PreOrderLoops
, PreOrderWorklist
;
587 // The outer-most loop actually goes into the result in the same relative
588 // order as we walk it. LoopInfo stores the top level loops in reverse
589 // program order so we walk in order here.
590 // FIXME: If we change the order of LoopInfo we will want to add a reverse
592 for (LoopT
*RootL
: *this) {
593 assert(PreOrderWorklist
.empty() &&
594 "Must start with an empty preorder walk worklist.");
595 PreOrderWorklist
.push_back(RootL
);
597 LoopT
*L
= PreOrderWorklist
.pop_back_val();
598 // Sub-loops are stored in forward program order, but will process the
599 // worklist backwards so we can just append them in order.
600 PreOrderWorklist
.append(L
->begin(), L
->end());
601 PreOrderLoops
.push_back(L
);
602 } while (!PreOrderWorklist
.empty());
605 return PreOrderLoops
;
609 template <class BlockT
, class LoopT
>
610 void LoopInfoBase
<BlockT
, LoopT
>::print(raw_ostream
&OS
) const {
611 for (unsigned i
= 0; i
< TopLevelLoops
.size(); ++i
)
612 TopLevelLoops
[i
]->print(OS
);
614 for (DenseMap
<BasicBlock
*, LoopT
*>::const_iterator I
= BBMap
.begin(),
615 E
= BBMap
.end(); I
!= E
; ++I
)
616 OS
<< "BB '" << I
->first
->getName() << "' level = "
617 << I
->second
->getLoopDepth() << "\n";
621 template <typename T
>
622 bool compareVectors(std::vector
<T
> &BB1
, std::vector
<T
> &BB2
) {
628 template <class BlockT
, class LoopT
>
629 void addInnerLoopsToHeadersMap(DenseMap
<BlockT
*, const LoopT
*> &LoopHeaders
,
630 const LoopInfoBase
<BlockT
, LoopT
> &LI
,
632 LoopHeaders
[L
.getHeader()] = &L
;
634 addInnerLoopsToHeadersMap(LoopHeaders
, LI
, *SL
);
638 template <class BlockT
, class LoopT
>
639 static void compareLoops(const LoopT
*L
, const LoopT
*OtherL
,
640 DenseMap
<BlockT
*, const LoopT
*> &OtherLoopHeaders
) {
641 BlockT
*H
= L
->getHeader();
642 BlockT
*OtherH
= OtherL
->getHeader();
643 assert(H
== OtherH
&&
644 "Mismatched headers even though found in the same map entry!");
646 assert(L
->getLoopDepth() == OtherL
->getLoopDepth() &&
647 "Mismatched loop depth!");
648 const LoopT
*ParentL
= L
, *OtherParentL
= OtherL
;
650 assert(ParentL
->getHeader() == OtherParentL
->getHeader() &&
651 "Mismatched parent loop headers!");
652 ParentL
= ParentL
->getParentLoop();
653 OtherParentL
= OtherParentL
->getParentLoop();
656 for (const LoopT
*SubL
: *L
) {
657 BlockT
*SubH
= SubL
->getHeader();
658 const LoopT
*OtherSubL
= OtherLoopHeaders
.lookup(SubH
);
659 assert(OtherSubL
&& "Inner loop is missing in computed loop info!");
660 OtherLoopHeaders
.erase(SubH
);
661 compareLoops(SubL
, OtherSubL
, OtherLoopHeaders
);
664 std::vector
<BlockT
*> BBs
= L
->getBlocks();
665 std::vector
<BlockT
*> OtherBBs
= OtherL
->getBlocks();
666 assert(compareVectors(BBs
, OtherBBs
) &&
667 "Mismatched basic blocks in the loops!");
669 const SmallPtrSetImpl
<const BlockT
*> &BlocksSet
= L
->getBlocksSet();
670 const SmallPtrSetImpl
<const BlockT
*> &OtherBlocksSet
= L
->getBlocksSet();
671 assert(BlocksSet
.size() == OtherBlocksSet
.size() &&
672 std::all_of(BlocksSet
.begin(), BlocksSet
.end(),
673 [&OtherBlocksSet
](const BlockT
*BB
) {
674 return OtherBlocksSet
.count(BB
);
676 "Mismatched basic blocks in BlocksSets!");
680 template <class BlockT
, class LoopT
>
681 void LoopInfoBase
<BlockT
, LoopT
>::verify(
682 const DomTreeBase
<BlockT
> &DomTree
) const {
683 DenseSet
<const LoopT
*> Loops
;
684 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
685 assert(!(*I
)->getParentLoop() && "Top-level loop has a parent!");
686 (*I
)->verifyLoopNest(&Loops
);
689 // Verify that blocks are mapped to valid loops.
691 for (auto &Entry
: BBMap
) {
692 const BlockT
*BB
= Entry
.first
;
693 LoopT
*L
= Entry
.second
;
694 assert(Loops
.count(L
) && "orphaned loop");
695 assert(L
->contains(BB
) && "orphaned block");
696 for (LoopT
*ChildLoop
: *L
)
697 assert(!ChildLoop
->contains(BB
) &&
698 "BBMap should point to the innermost loop containing BB");
701 // Recompute LoopInfo to verify loops structure.
702 LoopInfoBase
<BlockT
, LoopT
> OtherLI
;
703 OtherLI
.analyze(DomTree
);
705 // Build a map we can use to move from our LI to the computed one. This
706 // allows us to ignore the particular order in any layer of the loop forest
707 // while still comparing the structure.
708 DenseMap
<BlockT
*, const LoopT
*> OtherLoopHeaders
;
709 for (LoopT
*L
: OtherLI
)
710 addInnerLoopsToHeadersMap(OtherLoopHeaders
, OtherLI
, *L
);
712 // Walk the top level loops and ensure there is a corresponding top-level
713 // loop in the computed version and then recursively compare those loop
715 for (LoopT
*L
: *this) {
716 BlockT
*Header
= L
->getHeader();
717 const LoopT
*OtherL
= OtherLoopHeaders
.lookup(Header
);
718 assert(OtherL
&& "Top level loop is missing in computed loop info!");
719 // Now that we've matched this loop, erase its header from the map.
720 OtherLoopHeaders
.erase(Header
);
721 // And recursively compare these loops.
722 compareLoops(L
, OtherL
, OtherLoopHeaders
);
725 // Any remaining entries in the map are loops which were found when computing
726 // a fresh LoopInfo but not present in the current one.
727 if (!OtherLoopHeaders
.empty()) {
728 for (const auto &HeaderAndLoop
: OtherLoopHeaders
)
729 dbgs() << "Found new loop: " << *HeaderAndLoop
.second
<< "\n";
730 llvm_unreachable("Found new loops when recomputing LoopInfo!");
735 } // End llvm namespace