]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This is the generic implementation of LoopInfo used for both Loops and | |
11 | // MachineLoops. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
970d7e83 LB |
15 | #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H |
16 | #define LLVM_ANALYSIS_LOOPINFOIMPL_H | |
223e47cc | 17 | |
1a4d82fc | 18 | #include "llvm/ADT/DepthFirstIterator.h" |
223e47cc | 19 | #include "llvm/ADT/PostOrderIterator.h" |
970d7e83 LB |
20 | #include "llvm/ADT/STLExtras.h" |
21 | #include "llvm/Analysis/LoopInfo.h" | |
1a4d82fc | 22 | #include "llvm/IR/Dominators.h" |
223e47cc LB |
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> | |
34 | void LoopBase<BlockT, LoopT>:: | |
35 | getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { | |
223e47cc LB |
36 | typedef GraphTraits<BlockT*> BlockTraits; |
37 | for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) | |
38 | for (typename BlockTraits::ChildIteratorType I = | |
39 | BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); | |
40 | I != E; ++I) | |
1a4d82fc | 41 | if (!contains(*I)) { |
223e47cc LB |
42 | // Not in current loop? It must be an exit block. |
43 | ExitingBlocks.push_back(*BI); | |
44 | break; | |
45 | } | |
46 | } | |
47 | ||
48 | /// getExitingBlock - If getExitingBlocks would return exactly one block, | |
49 | /// return that block. Otherwise return null. | |
50 | template<class BlockT, class LoopT> | |
51 | BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { | |
52 | SmallVector<BlockT*, 8> ExitingBlocks; | |
53 | getExitingBlocks(ExitingBlocks); | |
54 | if (ExitingBlocks.size() == 1) | |
55 | return ExitingBlocks[0]; | |
1a4d82fc | 56 | return nullptr; |
223e47cc LB |
57 | } |
58 | ||
59 | /// getExitBlocks - Return all of the successor blocks of this loop. These | |
60 | /// are the blocks _outside of the current loop_ which are branched to. | |
61 | /// | |
62 | template<class BlockT, class LoopT> | |
63 | void LoopBase<BlockT, LoopT>:: | |
64 | getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { | |
223e47cc LB |
65 | typedef GraphTraits<BlockT*> BlockTraits; |
66 | for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) | |
67 | for (typename BlockTraits::ChildIteratorType I = | |
68 | BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); | |
69 | I != E; ++I) | |
1a4d82fc | 70 | if (!contains(*I)) |
223e47cc LB |
71 | // Not in current loop? It must be an exit block. |
72 | ExitBlocks.push_back(*I); | |
73 | } | |
74 | ||
75 | /// getExitBlock - If getExitBlocks would return exactly one block, | |
76 | /// return that block. Otherwise return null. | |
77 | template<class BlockT, class LoopT> | |
78 | BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { | |
79 | SmallVector<BlockT*, 8> ExitBlocks; | |
80 | getExitBlocks(ExitBlocks); | |
81 | if (ExitBlocks.size() == 1) | |
82 | return ExitBlocks[0]; | |
1a4d82fc | 83 | return nullptr; |
223e47cc LB |
84 | } |
85 | ||
86 | /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). | |
87 | template<class BlockT, class LoopT> | |
88 | void LoopBase<BlockT, LoopT>:: | |
89 | getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { | |
223e47cc LB |
90 | typedef GraphTraits<BlockT*> BlockTraits; |
91 | for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) | |
92 | for (typename BlockTraits::ChildIteratorType I = | |
93 | BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); | |
94 | I != E; ++I) | |
1a4d82fc | 95 | if (!contains(*I)) |
223e47cc LB |
96 | // Not in current loop? It must be an exit block. |
97 | ExitEdges.push_back(Edge(*BI, *I)); | |
98 | } | |
99 | ||
100 | /// getLoopPreheader - If there is a preheader for this loop, return it. A | |
101 | /// loop has a preheader if there is only one edge to the header of the loop | |
102 | /// from outside of the loop. If this is the case, the block branching to the | |
103 | /// header of the loop is the preheader node. | |
104 | /// | |
105 | /// This method returns null if there is no preheader for the loop. | |
106 | /// | |
107 | template<class BlockT, class LoopT> | |
108 | BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { | |
109 | // Keep track of nodes outside the loop branching to the header... | |
110 | BlockT *Out = getLoopPredecessor(); | |
1a4d82fc | 111 | if (!Out) return nullptr; |
223e47cc LB |
112 | |
113 | // Make sure there is only one exit out of the preheader. | |
114 | typedef GraphTraits<BlockT*> BlockTraits; | |
115 | typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); | |
116 | ++SI; | |
117 | if (SI != BlockTraits::child_end(Out)) | |
1a4d82fc | 118 | return nullptr; // Multiple exits from the block, must not be a preheader. |
223e47cc LB |
119 | |
120 | // The predecessor has exactly one successor, so it is a preheader. | |
121 | return Out; | |
122 | } | |
123 | ||
124 | /// getLoopPredecessor - If the given loop's header has exactly one unique | |
125 | /// predecessor outside the loop, return it. Otherwise return null. | |
126 | /// This is less strict that the loop "preheader" concept, which requires | |
127 | /// the predecessor to have exactly one successor. | |
128 | /// | |
129 | template<class BlockT, class LoopT> | |
130 | BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { | |
131 | // Keep track of nodes outside the loop branching to the header... | |
1a4d82fc | 132 | BlockT *Out = nullptr; |
223e47cc LB |
133 | |
134 | // Loop over the predecessors of the header node... | |
135 | BlockT *Header = getHeader(); | |
136 | typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; | |
137 | for (typename InvBlockTraits::ChildIteratorType PI = | |
138 | InvBlockTraits::child_begin(Header), | |
139 | PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { | |
140 | typename InvBlockTraits::NodeType *N = *PI; | |
141 | if (!contains(N)) { // If the block is not in the loop... | |
142 | if (Out && Out != N) | |
1a4d82fc | 143 | return nullptr; // Multiple predecessors outside the loop |
223e47cc LB |
144 | Out = N; |
145 | } | |
146 | } | |
147 | ||
148 | // Make sure there is only one exit out of the preheader. | |
149 | assert(Out && "Header of loop has no predecessors from outside loop?"); | |
150 | return Out; | |
151 | } | |
152 | ||
153 | /// getLoopLatch - If there is a single latch block for this loop, return it. | |
154 | /// A latch block is a block that contains a branch back to the header. | |
155 | template<class BlockT, class LoopT> | |
156 | BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { | |
157 | BlockT *Header = getHeader(); | |
158 | typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; | |
159 | typename InvBlockTraits::ChildIteratorType PI = | |
160 | InvBlockTraits::child_begin(Header); | |
161 | typename InvBlockTraits::ChildIteratorType PE = | |
162 | InvBlockTraits::child_end(Header); | |
1a4d82fc | 163 | BlockT *Latch = nullptr; |
223e47cc LB |
164 | for (; PI != PE; ++PI) { |
165 | typename InvBlockTraits::NodeType *N = *PI; | |
166 | if (contains(N)) { | |
1a4d82fc | 167 | if (Latch) return nullptr; |
223e47cc LB |
168 | Latch = N; |
169 | } | |
170 | } | |
171 | ||
172 | return Latch; | |
173 | } | |
174 | ||
175 | //===----------------------------------------------------------------------===// | |
176 | // APIs for updating loop information after changing the CFG | |
177 | // | |
178 | ||
179 | /// addBasicBlockToLoop - This method is used by other analyses to update loop | |
180 | /// information. NewBB is set to be a new member of the current loop. | |
181 | /// Because of this, it is added as a member of all parent loops, and is added | |
182 | /// to the specified LoopInfo object as being in the current basic block. It | |
183 | /// is not valid to replace the loop header with this method. | |
184 | /// | |
185 | template<class BlockT, class LoopT> | |
186 | void LoopBase<BlockT, LoopT>:: | |
187 | addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { | |
188 | assert((Blocks.empty() || LIB[getHeader()] == this) && | |
189 | "Incorrect LI specified for this loop!"); | |
190 | assert(NewBB && "Cannot add a null basic block to the loop!"); | |
1a4d82fc | 191 | assert(!LIB[NewBB] && "BasicBlock already in the loop!"); |
223e47cc LB |
192 | |
193 | LoopT *L = static_cast<LoopT *>(this); | |
194 | ||
195 | // Add the loop mapping to the LoopInfo object... | |
196 | LIB.BBMap[NewBB] = L; | |
197 | ||
198 | // Add the basic block to this loop and all parent loops... | |
199 | while (L) { | |
1a4d82fc | 200 | L->addBlockEntry(NewBB); |
223e47cc LB |
201 | L = L->getParentLoop(); |
202 | } | |
203 | } | |
204 | ||
205 | /// replaceChildLoopWith - This is used when splitting loops up. It replaces | |
206 | /// the OldChild entry in our children list with NewChild, and updates the | |
207 | /// parent pointer of OldChild to be null and the NewChild to be this loop. | |
208 | /// This updates the loop depth of the new child. | |
209 | template<class BlockT, class LoopT> | |
210 | void LoopBase<BlockT, LoopT>:: | |
211 | replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) { | |
212 | assert(OldChild->ParentLoop == this && "This loop is already broken!"); | |
1a4d82fc | 213 | assert(!NewChild->ParentLoop && "NewChild already has a parent!"); |
223e47cc LB |
214 | typename std::vector<LoopT *>::iterator I = |
215 | std::find(SubLoops.begin(), SubLoops.end(), OldChild); | |
216 | assert(I != SubLoops.end() && "OldChild not in loop!"); | |
217 | *I = NewChild; | |
1a4d82fc | 218 | OldChild->ParentLoop = nullptr; |
223e47cc LB |
219 | NewChild->ParentLoop = static_cast<LoopT *>(this); |
220 | } | |
221 | ||
222 | /// verifyLoop - Verify loop structure | |
223 | template<class BlockT, class LoopT> | |
224 | void LoopBase<BlockT, LoopT>::verifyLoop() const { | |
225 | #ifndef NDEBUG | |
226 | assert(!Blocks.empty() && "Loop header is missing"); | |
227 | ||
228 | // Setup for using a depth-first iterator to visit every block in the loop. | |
229 | SmallVector<BlockT*, 8> ExitBBs; | |
230 | getExitBlocks(ExitBBs); | |
231 | llvm::SmallPtrSet<BlockT*, 8> VisitSet; | |
232 | VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); | |
233 | df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> > | |
234 | BI = df_ext_begin(getHeader(), VisitSet), | |
235 | BE = df_ext_end(getHeader(), VisitSet); | |
236 | ||
237 | // Keep track of the number of BBs visited. | |
238 | unsigned NumVisited = 0; | |
239 | ||
223e47cc LB |
240 | // Check the individual blocks. |
241 | for ( ; BI != BE; ++BI) { | |
242 | BlockT *BB = *BI; | |
243 | bool HasInsideLoopSuccs = false; | |
244 | bool HasInsideLoopPreds = false; | |
245 | SmallVector<BlockT *, 2> OutsideLoopPreds; | |
246 | ||
247 | typedef GraphTraits<BlockT*> BlockTraits; | |
248 | for (typename BlockTraits::ChildIteratorType SI = | |
249 | BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB); | |
250 | SI != SE; ++SI) | |
1a4d82fc | 251 | if (contains(*SI)) { |
223e47cc LB |
252 | HasInsideLoopSuccs = true; |
253 | break; | |
254 | } | |
255 | typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; | |
256 | for (typename InvBlockTraits::ChildIteratorType PI = | |
257 | InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); | |
258 | PI != PE; ++PI) { | |
259 | BlockT *N = *PI; | |
1a4d82fc | 260 | if (contains(N)) |
223e47cc LB |
261 | HasInsideLoopPreds = true; |
262 | else | |
263 | OutsideLoopPreds.push_back(N); | |
264 | } | |
265 | ||
266 | if (BB == getHeader()) { | |
267 | assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); | |
268 | } else if (!OutsideLoopPreds.empty()) { | |
269 | // A non-header loop shouldn't be reachable from outside the loop, | |
270 | // though it is permitted if the predecessor is not itself actually | |
271 | // reachable. | |
272 | BlockT *EntryBB = BB->getParent()->begin(); | |
1a4d82fc JJ |
273 | for (BlockT *CB : depth_first(EntryBB)) |
274 | for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) | |
275 | assert(CB != OutsideLoopPreds[i] && | |
276 | "Loop has multiple entry points!"); | |
223e47cc LB |
277 | } |
278 | assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!"); | |
279 | assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!"); | |
280 | assert(BB != getHeader()->getParent()->begin() && | |
281 | "Loop contains function entry block!"); | |
282 | ||
283 | NumVisited++; | |
284 | } | |
285 | ||
286 | assert(NumVisited == getNumBlocks() && "Unreachable block in loop"); | |
287 | ||
288 | // Check the subloops. | |
289 | for (iterator I = begin(), E = end(); I != E; ++I) | |
290 | // Each block in each subloop should be contained within this loop. | |
291 | for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); | |
292 | BI != BE; ++BI) { | |
1a4d82fc | 293 | assert(contains(*BI) && |
223e47cc LB |
294 | "Loop does not contain all the blocks of a subloop!"); |
295 | } | |
296 | ||
297 | // Check the parent loop pointer. | |
298 | if (ParentLoop) { | |
299 | assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) != | |
300 | ParentLoop->end() && | |
301 | "Loop is not a subloop of its parent!"); | |
302 | } | |
303 | #endif | |
304 | } | |
305 | ||
306 | /// verifyLoop - Verify loop structure of this loop and all nested loops. | |
307 | template<class BlockT, class LoopT> | |
308 | void LoopBase<BlockT, LoopT>::verifyLoopNest( | |
309 | DenseSet<const LoopT*> *Loops) const { | |
310 | Loops->insert(static_cast<const LoopT *>(this)); | |
311 | // Verify this loop. | |
312 | verifyLoop(); | |
313 | // Verify the subloops. | |
314 | for (iterator I = begin(), E = end(); I != E; ++I) | |
315 | (*I)->verifyLoopNest(Loops); | |
316 | } | |
317 | ||
318 | template<class BlockT, class LoopT> | |
319 | void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const { | |
320 | OS.indent(Depth*2) << "Loop at depth " << getLoopDepth() | |
321 | << " containing: "; | |
322 | ||
323 | for (unsigned i = 0; i < getBlocks().size(); ++i) { | |
324 | if (i) OS << ","; | |
325 | BlockT *BB = getBlocks()[i]; | |
1a4d82fc | 326 | BB->printAsOperand(OS, false); |
223e47cc LB |
327 | if (BB == getHeader()) OS << "<header>"; |
328 | if (BB == getLoopLatch()) OS << "<latch>"; | |
329 | if (isLoopExiting(BB)) OS << "<exiting>"; | |
330 | } | |
331 | OS << "\n"; | |
332 | ||
333 | for (iterator I = begin(), E = end(); I != E; ++I) | |
334 | (*I)->print(OS, Depth+2); | |
335 | } | |
336 | ||
337 | //===----------------------------------------------------------------------===// | |
338 | /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the | |
339 | /// result does / not depend on use list (block predecessor) order. | |
340 | /// | |
341 | ||
342 | /// Discover a subloop with the specified backedges such that: All blocks within | |
343 | /// this loop are mapped to this loop or a subloop. And all subloops within this | |
344 | /// loop have their parent loop set to this loop or a subloop. | |
345 | template<class BlockT, class LoopT> | |
346 | static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges, | |
347 | LoopInfoBase<BlockT, LoopT> *LI, | |
348 | DominatorTreeBase<BlockT> &DomTree) { | |
349 | typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; | |
350 | ||
351 | unsigned NumBlocks = 0; | |
352 | unsigned NumSubloops = 0; | |
353 | ||
354 | // Perform a backward CFG traversal using a worklist. | |
355 | std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); | |
356 | while (!ReverseCFGWorklist.empty()) { | |
357 | BlockT *PredBB = ReverseCFGWorklist.back(); | |
358 | ReverseCFGWorklist.pop_back(); | |
359 | ||
360 | LoopT *Subloop = LI->getLoopFor(PredBB); | |
361 | if (!Subloop) { | |
362 | if (!DomTree.isReachableFromEntry(PredBB)) | |
363 | continue; | |
364 | ||
365 | // This is an undiscovered block. Map it to the current loop. | |
366 | LI->changeLoopFor(PredBB, L); | |
367 | ++NumBlocks; | |
368 | if (PredBB == L->getHeader()) | |
369 | continue; | |
370 | // Push all block predecessors on the worklist. | |
371 | ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), | |
372 | InvBlockTraits::child_begin(PredBB), | |
373 | InvBlockTraits::child_end(PredBB)); | |
374 | } | |
375 | else { | |
376 | // This is a discovered block. Find its outermost discovered loop. | |
377 | while (LoopT *Parent = Subloop->getParentLoop()) | |
378 | Subloop = Parent; | |
379 | ||
380 | // If it is already discovered to be a subloop of this loop, continue. | |
381 | if (Subloop == L) | |
382 | continue; | |
383 | ||
384 | // Discover a subloop of this loop. | |
385 | Subloop->setParentLoop(L); | |
386 | ++NumSubloops; | |
387 | NumBlocks += Subloop->getBlocks().capacity(); | |
388 | PredBB = Subloop->getHeader(); | |
389 | // Continue traversal along predecessors that are not loop-back edges from | |
390 | // within this subloop tree itself. Note that a predecessor may directly | |
391 | // reach another subloop that is not yet discovered to be a subloop of | |
392 | // this loop, which we must traverse. | |
393 | for (typename InvBlockTraits::ChildIteratorType PI = | |
394 | InvBlockTraits::child_begin(PredBB), | |
395 | PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) { | |
396 | if (LI->getLoopFor(*PI) != Subloop) | |
397 | ReverseCFGWorklist.push_back(*PI); | |
398 | } | |
399 | } | |
400 | } | |
401 | L->getSubLoopsVector().reserve(NumSubloops); | |
1a4d82fc | 402 | L->reserveBlocks(NumBlocks); |
223e47cc LB |
403 | } |
404 | ||
405 | namespace { | |
406 | /// Populate all loop data in a stable order during a single forward DFS. | |
407 | template<class BlockT, class LoopT> | |
408 | class PopulateLoopsDFS { | |
409 | typedef GraphTraits<BlockT*> BlockTraits; | |
410 | typedef typename BlockTraits::ChildIteratorType SuccIterTy; | |
411 | ||
412 | LoopInfoBase<BlockT, LoopT> *LI; | |
413 | DenseSet<const BlockT *> VisitedBlocks; | |
414 | std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack; | |
415 | ||
416 | public: | |
417 | PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li): | |
418 | LI(li) {} | |
419 | ||
420 | void traverse(BlockT *EntryBlock); | |
421 | ||
422 | protected: | |
423 | void insertIntoLoop(BlockT *Block); | |
424 | ||
425 | BlockT *dfsSource() { return DFSStack.back().first; } | |
426 | SuccIterTy &dfsSucc() { return DFSStack.back().second; } | |
427 | SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); } | |
428 | ||
429 | void pushBlock(BlockT *Block) { | |
430 | DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block))); | |
431 | } | |
432 | }; | |
433 | } // anonymous | |
434 | ||
435 | /// Top-level driver for the forward DFS within the loop. | |
436 | template<class BlockT, class LoopT> | |
437 | void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { | |
438 | pushBlock(EntryBlock); | |
439 | VisitedBlocks.insert(EntryBlock); | |
440 | while (!DFSStack.empty()) { | |
441 | // Traverse the leftmost path as far as possible. | |
442 | while (dfsSucc() != dfsSuccEnd()) { | |
443 | BlockT *BB = *dfsSucc(); | |
444 | ++dfsSucc(); | |
445 | if (!VisitedBlocks.insert(BB).second) | |
446 | continue; | |
447 | ||
448 | // Push the next DFS successor onto the stack. | |
449 | pushBlock(BB); | |
450 | } | |
451 | // Visit the top of the stack in postorder and backtrack. | |
452 | insertIntoLoop(dfsSource()); | |
453 | DFSStack.pop_back(); | |
454 | } | |
455 | } | |
456 | ||
457 | /// Add a single Block to its ancestor loops in PostOrder. If the block is a | |
458 | /// subloop header, add the subloop to its parent in PostOrder, then reverse the | |
459 | /// Block and Subloop vectors of the now complete subloop to achieve RPO. | |
460 | template<class BlockT, class LoopT> | |
461 | void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { | |
462 | LoopT *Subloop = LI->getLoopFor(Block); | |
463 | if (Subloop && Block == Subloop->getHeader()) { | |
464 | // We reach this point once per subloop after processing all the blocks in | |
465 | // the subloop. | |
466 | if (Subloop->getParentLoop()) | |
467 | Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); | |
468 | else | |
469 | LI->addTopLevelLoop(Subloop); | |
470 | ||
471 | // For convenience, Blocks and Subloops are inserted in postorder. Reverse | |
472 | // the lists, except for the loop header, which is always at the beginning. | |
1a4d82fc | 473 | Subloop->reverseBlock(1); |
223e47cc LB |
474 | std::reverse(Subloop->getSubLoopsVector().begin(), |
475 | Subloop->getSubLoopsVector().end()); | |
476 | ||
477 | Subloop = Subloop->getParentLoop(); | |
478 | } | |
479 | for (; Subloop; Subloop = Subloop->getParentLoop()) | |
1a4d82fc | 480 | Subloop->addBlockEntry(Block); |
223e47cc LB |
481 | } |
482 | ||
483 | /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal | |
484 | /// interleaved with backward CFG traversals within each subloop | |
485 | /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so | |
486 | /// this part of the algorithm is linear in the number of CFG edges. Subloop and | |
487 | /// Block vectors are then populated during a single forward CFG traversal | |
488 | /// (PopulateLoopDFS). | |
489 | /// | |
490 | /// During the two CFG traversals each block is seen three times: | |
491 | /// 1) Discovered and mapped by a reverse CFG traversal. | |
492 | /// 2) Visited during a forward DFS CFG traversal. | |
493 | /// 3) Reverse-inserted in the loop in postorder following forward DFS. | |
494 | /// | |
495 | /// The Block vectors are inclusive, so step 3 requires loop-depth number of | |
496 | /// insertions per block. | |
497 | template<class BlockT, class LoopT> | |
498 | void LoopInfoBase<BlockT, LoopT>:: | |
499 | Analyze(DominatorTreeBase<BlockT> &DomTree) { | |
500 | ||
501 | // Postorder traversal of the dominator tree. | |
502 | DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode(); | |
503 | for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot), | |
504 | DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { | |
505 | ||
506 | BlockT *Header = DomIter->getBlock(); | |
507 | SmallVector<BlockT *, 4> Backedges; | |
508 | ||
509 | // Check each predecessor of the potential loop header. | |
510 | typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; | |
511 | for (typename InvBlockTraits::ChildIteratorType PI = | |
512 | InvBlockTraits::child_begin(Header), | |
513 | PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { | |
514 | ||
515 | BlockT *Backedge = *PI; | |
516 | ||
517 | // If Header dominates predBB, this is a new loop. Collect the backedges. | |
518 | if (DomTree.dominates(Header, Backedge) | |
519 | && DomTree.isReachableFromEntry(Backedge)) { | |
520 | Backedges.push_back(Backedge); | |
521 | } | |
522 | } | |
523 | // Perform a backward CFG traversal to discover and map blocks in this loop. | |
524 | if (!Backedges.empty()) { | |
525 | LoopT *L = new LoopT(Header); | |
526 | discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree); | |
527 | } | |
528 | } | |
529 | // Perform a single forward CFG traversal to populate block and subloop | |
530 | // vectors for all loops. | |
531 | PopulateLoopsDFS<BlockT, LoopT> DFS(this); | |
532 | DFS.traverse(DomRoot->getBlock()); | |
533 | } | |
534 | ||
535 | // Debugging | |
536 | template<class BlockT, class LoopT> | |
537 | void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { | |
538 | for (unsigned i = 0; i < TopLevelLoops.size(); ++i) | |
539 | TopLevelLoops[i]->print(OS); | |
540 | #if 0 | |
541 | for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), | |
542 | E = BBMap.end(); I != E; ++I) | |
543 | OS << "BB '" << I->first->getName() << "' level = " | |
544 | << I->second->getLoopDepth() << "\n"; | |
545 | #endif | |
546 | } | |
547 | ||
548 | } // End llvm namespace | |
549 | ||
550 | #endif |