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