Deleted Added
sdiff udiff text old ( 256281 ) new ( 263508 )
full compact
LoopInfoImpl.h (256281) LoopInfoImpl.h (263508)
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//===----------------------------------------------------------------------===//

--- 17 unchanged lines hidden (view full) ---

26
27/// getExitingBlocks - Return all blocks inside the loop that have successors
28/// outside of the loop. These are the blocks _inside of the current loop_
29/// which branch out. The returned list is always unique.
30///
31template<class BlockT, class LoopT>
32void LoopBase<BlockT, LoopT>::
33getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
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//===----------------------------------------------------------------------===//

--- 17 unchanged lines hidden (view full) ---

26
27/// getExitingBlocks - Return all blocks inside the loop that have successors
28/// outside of the loop. These are the blocks _inside of the current loop_
29/// which branch out. The returned list is always unique.
30///
31template<class BlockT, class LoopT>
32void LoopBase<BlockT, LoopT>::
33getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
34 // Sort the blocks vector so that we can use binary search to do quick
35 // lookups.
36 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
37 std::sort(LoopBBs.begin(), LoopBBs.end());
38
39 typedef GraphTraits<BlockT*> BlockTraits;
40 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
41 for (typename BlockTraits::ChildIteratorType I =
42 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
43 I != E; ++I)
34 typedef GraphTraits<BlockT*> BlockTraits;
35 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
36 for (typename BlockTraits::ChildIteratorType I =
37 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
38 I != E; ++I)
44 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
39 if (!contains(*I)) {
45 // Not in current loop? It must be an exit block.
46 ExitingBlocks.push_back(*BI);
47 break;
48 }
49}
50
51/// getExitingBlock - If getExitingBlocks would return exactly one block,
52/// return that block. Otherwise return null.

--- 7 unchanged lines hidden (view full) ---

60}
61
62/// getExitBlocks - Return all of the successor blocks of this loop. These
63/// are the blocks _outside of the current loop_ which are branched to.
64///
65template<class BlockT, class LoopT>
66void LoopBase<BlockT, LoopT>::
67getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
40 // Not in current loop? It must be an exit block.
41 ExitingBlocks.push_back(*BI);
42 break;
43 }
44}
45
46/// getExitingBlock - If getExitingBlocks would return exactly one block,
47/// return that block. Otherwise return null.

--- 7 unchanged lines hidden (view full) ---

55}
56
57/// getExitBlocks - Return all of the successor blocks of this loop. These
58/// are the blocks _outside of the current loop_ which are branched to.
59///
60template<class BlockT, class LoopT>
61void LoopBase<BlockT, LoopT>::
62getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
68 // Sort the blocks vector so that we can use binary search to do quick
69 // lookups.
70 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
71 std::sort(LoopBBs.begin(), LoopBBs.end());
72
73 typedef GraphTraits<BlockT*> BlockTraits;
74 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
75 for (typename BlockTraits::ChildIteratorType I =
76 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
77 I != E; ++I)
63 typedef GraphTraits<BlockT*> BlockTraits;
64 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
65 for (typename BlockTraits::ChildIteratorType I =
66 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
67 I != E; ++I)
78 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
68 if (!contains(*I))
79 // Not in current loop? It must be an exit block.
80 ExitBlocks.push_back(*I);
81}
82
83/// getExitBlock - If getExitBlocks would return exactly one block,
84/// return that block. Otherwise return null.
85template<class BlockT, class LoopT>
86BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
87 SmallVector<BlockT*, 8> ExitBlocks;
88 getExitBlocks(ExitBlocks);
89 if (ExitBlocks.size() == 1)
90 return ExitBlocks[0];
91 return 0;
92}
93
94/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
95template<class BlockT, class LoopT>
96void LoopBase<BlockT, LoopT>::
97getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
69 // Not in current loop? It must be an exit block.
70 ExitBlocks.push_back(*I);
71}
72
73/// getExitBlock - If getExitBlocks would return exactly one block,
74/// return that block. Otherwise return null.
75template<class BlockT, class LoopT>
76BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
77 SmallVector<BlockT*, 8> ExitBlocks;
78 getExitBlocks(ExitBlocks);
79 if (ExitBlocks.size() == 1)
80 return ExitBlocks[0];
81 return 0;
82}
83
84/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
85template<class BlockT, class LoopT>
86void LoopBase<BlockT, LoopT>::
87getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
98 // Sort the blocks vector so that we can use binary search to do quick
99 // lookups.
100 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
101 array_pod_sort(LoopBBs.begin(), LoopBBs.end());
102
103 typedef GraphTraits<BlockT*> BlockTraits;
104 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
105 for (typename BlockTraits::ChildIteratorType I =
106 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
107 I != E; ++I)
88 typedef GraphTraits<BlockT*> BlockTraits;
89 for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
90 for (typename BlockTraits::ChildIteratorType I =
91 BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
92 I != E; ++I)
108 if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
93 if (!contains(*I))
109 // Not in current loop? It must be an exit block.
110 ExitEdges.push_back(Edge(*BI, *I));
111}
112
113/// getLoopPreheader - If there is a preheader for this loop, return it. A
114/// loop has a preheader if there is only one edge to the header of the loop
115/// from outside of the loop. If this is the case, the block branching to the
116/// header of the loop is the preheader node.

--- 88 unchanged lines hidden (view full) ---

205
206 LoopT *L = static_cast<LoopT *>(this);
207
208 // Add the loop mapping to the LoopInfo object...
209 LIB.BBMap[NewBB] = L;
210
211 // Add the basic block to this loop and all parent loops...
212 while (L) {
94 // Not in current loop? It must be an exit block.
95 ExitEdges.push_back(Edge(*BI, *I));
96}
97
98/// getLoopPreheader - If there is a preheader for this loop, return it. A
99/// loop has a preheader if there is only one edge to the header of the loop
100/// from outside of the loop. If this is the case, the block branching to the
101/// header of the loop is the preheader node.

--- 88 unchanged lines hidden (view full) ---

190
191 LoopT *L = static_cast<LoopT *>(this);
192
193 // Add the loop mapping to the LoopInfo object...
194 LIB.BBMap[NewBB] = L;
195
196 // Add the basic block to this loop and all parent loops...
197 while (L) {
213 L->Blocks.push_back(NewBB);
198 L->addBlockEntry(NewBB);
214 L = L->getParentLoop();
215 }
216}
217
218/// replaceChildLoopWith - This is used when splitting loops up. It replaces
219/// the OldChild entry in our children list with NewChild, and updates the
220/// parent pointer of OldChild to be null and the NewChild to be this loop.
221/// This updates the loop depth of the new child.

--- 23 unchanged lines hidden (view full) ---

245 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
246 df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
247 BI = df_ext_begin(getHeader(), VisitSet),
248 BE = df_ext_end(getHeader(), VisitSet);
249
250 // Keep track of the number of BBs visited.
251 unsigned NumVisited = 0;
252
199 L = L->getParentLoop();
200 }
201}
202
203/// replaceChildLoopWith - This is used when splitting loops up. It replaces
204/// the OldChild entry in our children list with NewChild, and updates the
205/// parent pointer of OldChild to be null and the NewChild to be this loop.
206/// This updates the loop depth of the new child.

--- 23 unchanged lines hidden (view full) ---

230 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
231 df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
232 BI = df_ext_begin(getHeader(), VisitSet),
233 BE = df_ext_end(getHeader(), VisitSet);
234
235 // Keep track of the number of BBs visited.
236 unsigned NumVisited = 0;
237
253 // Sort the blocks vector so that we can use binary search to do quick
254 // lookups.
255 SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
256 std::sort(LoopBBs.begin(), LoopBBs.end());
257
258 // Check the individual blocks.
259 for ( ; BI != BE; ++BI) {
260 BlockT *BB = *BI;
261 bool HasInsideLoopSuccs = false;
262 bool HasInsideLoopPreds = false;
263 SmallVector<BlockT *, 2> OutsideLoopPreds;
264
265 typedef GraphTraits<BlockT*> BlockTraits;
266 for (typename BlockTraits::ChildIteratorType SI =
267 BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
268 SI != SE; ++SI)
238 // Check the individual blocks.
239 for ( ; BI != BE; ++BI) {
240 BlockT *BB = *BI;
241 bool HasInsideLoopSuccs = false;
242 bool HasInsideLoopPreds = false;
243 SmallVector<BlockT *, 2> OutsideLoopPreds;
244
245 typedef GraphTraits<BlockT*> BlockTraits;
246 for (typename BlockTraits::ChildIteratorType SI =
247 BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
248 SI != SE; ++SI)
269 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
249 if (contains(*SI)) {
270 HasInsideLoopSuccs = true;
271 break;
272 }
273 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
274 for (typename InvBlockTraits::ChildIteratorType PI =
275 InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
276 PI != PE; ++PI) {
277 BlockT *N = *PI;
250 HasInsideLoopSuccs = true;
251 break;
252 }
253 typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
254 for (typename InvBlockTraits::ChildIteratorType PI =
255 InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
256 PI != PE; ++PI) {
257 BlockT *N = *PI;
278 if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
258 if (contains(N))
279 HasInsideLoopPreds = true;
280 else
281 OutsideLoopPreds.push_back(N);
282 }
283
284 if (BB == getHeader()) {
285 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
286 } else if (!OutsideLoopPreds.empty()) {

--- 17 unchanged lines hidden (view full) ---

304
305 assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
306
307 // Check the subloops.
308 for (iterator I = begin(), E = end(); I != E; ++I)
309 // Each block in each subloop should be contained within this loop.
310 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
311 BI != BE; ++BI) {
259 HasInsideLoopPreds = true;
260 else
261 OutsideLoopPreds.push_back(N);
262 }
263
264 if (BB == getHeader()) {
265 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
266 } else if (!OutsideLoopPreds.empty()) {

--- 17 unchanged lines hidden (view full) ---

284
285 assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
286
287 // Check the subloops.
288 for (iterator I = begin(), E = end(); I != E; ++I)
289 // Each block in each subloop should be contained within this loop.
290 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
291 BI != BE; ++BI) {
312 assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
292 assert(contains(*BI) &&
313 "Loop does not contain all the blocks of a subloop!");
314 }
315
316 // Check the parent loop pointer.
317 if (ParentLoop) {
318 assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
319 ParentLoop->end() &&
320 "Loop is not a subloop of its parent!");

--- 92 unchanged lines hidden (view full) ---

413 InvBlockTraits::child_begin(PredBB),
414 PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
415 if (LI->getLoopFor(*PI) != Subloop)
416 ReverseCFGWorklist.push_back(*PI);
417 }
418 }
419 }
420 L->getSubLoopsVector().reserve(NumSubloops);
293 "Loop does not contain all the blocks of a subloop!");
294 }
295
296 // Check the parent loop pointer.
297 if (ParentLoop) {
298 assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
299 ParentLoop->end() &&
300 "Loop is not a subloop of its parent!");

--- 92 unchanged lines hidden (view full) ---

393 InvBlockTraits::child_begin(PredBB),
394 PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
395 if (LI->getLoopFor(*PI) != Subloop)
396 ReverseCFGWorklist.push_back(*PI);
397 }
398 }
399 }
400 L->getSubLoopsVector().reserve(NumSubloops);
421 L->getBlocksVector().reserve(NumBlocks);
401 L->reserveBlocks(NumBlocks);
422}
423
424namespace {
425/// Populate all loop data in a stable order during a single forward DFS.
426template<class BlockT, class LoopT>
427class PopulateLoopsDFS {
428 typedef GraphTraits<BlockT*> BlockTraits;
429 typedef typename BlockTraits::ChildIteratorType SuccIterTy;

--- 54 unchanged lines hidden (view full) ---

484 // the subloop.
485 if (Subloop->getParentLoop())
486 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
487 else
488 LI->addTopLevelLoop(Subloop);
489
490 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
491 // the lists, except for the loop header, which is always at the beginning.
402}
403
404namespace {
405/// Populate all loop data in a stable order during a single forward DFS.
406template<class BlockT, class LoopT>
407class PopulateLoopsDFS {
408 typedef GraphTraits<BlockT*> BlockTraits;
409 typedef typename BlockTraits::ChildIteratorType SuccIterTy;

--- 54 unchanged lines hidden (view full) ---

464 // the subloop.
465 if (Subloop->getParentLoop())
466 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
467 else
468 LI->addTopLevelLoop(Subloop);
469
470 // For convenience, Blocks and Subloops are inserted in postorder. Reverse
471 // the lists, except for the loop header, which is always at the beginning.
492 std::reverse(Subloop->getBlocksVector().begin()+1,
493 Subloop->getBlocksVector().end());
472 Subloop->reverseBlock(1);
494 std::reverse(Subloop->getSubLoopsVector().begin(),
495 Subloop->getSubLoopsVector().end());
496
497 Subloop = Subloop->getParentLoop();
498 }
499 for (; Subloop; Subloop = Subloop->getParentLoop())
473 std::reverse(Subloop->getSubLoopsVector().begin(),
474 Subloop->getSubLoopsVector().end());
475
476 Subloop = Subloop->getParentLoop();
477 }
478 for (; Subloop; Subloop = Subloop->getParentLoop())
500 Subloop->getBlocksVector().push_back(Block);
479 Subloop->addBlockEntry(Block);
501}
502
503/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
504/// interleaved with backward CFG traversals within each subloop
505/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
506/// this part of the algorithm is linear in the number of CFG edges. Subloop and
507/// Block vectors are then populated during a single forward CFG traversal
508/// (PopulateLoopDFS).

--- 62 unchanged lines hidden --- 		480}
481
482/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
483/// interleaved with backward CFG traversals within each subloop
484/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
485/// this part of the algorithm is linear in the number of CFG edges. Subloop and
486/// Block vectors are then populated during a single forward CFG traversal
487/// (PopulateLoopDFS).

--- 62 unchanged lines hidden ---