15 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
16 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
31 template<
class BlockT,
class LoopT>
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);
48 template<
class BlockT,
class LoopT>
51 getExitingBlocks(ExitingBlocks);
52 if (ExitingBlocks.
size() == 1)
53 return ExitingBlocks[0];
60 template<
class BlockT,
class LoopT>
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);
75 template<
class BlockT,
class LoopT>
78 getExitBlocks(ExitBlocks);
79 if (ExitBlocks.
size() == 1)
85 template<
class BlockT,
class LoopT>
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);
105 template<
class BlockT,
class LoopT>
108 BlockT *Out = getLoopPredecessor();
113 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
115 if (SI != BlockTraits::child_end(Out))
127 template<
class BlockT,
class LoopT>
133 BlockT *Header = getHeader();
135 for (
typename InvBlockTraits::ChildIteratorType PI =
136 InvBlockTraits::child_begin(Header),
137 PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
147 assert(Out &&
"Header of loop has no predecessors from outside loop?");
153 template<
class BlockT,
class LoopT>
155 BlockT *Header = getHeader();
157 typename InvBlockTraits::ChildIteratorType PI =
158 InvBlockTraits::child_begin(Header);
159 typename InvBlockTraits::ChildIteratorType PE =
160 InvBlockTraits::child_end(Header);
162 for (; PI != PE; ++PI) {
183 template<
class BlockT,
class LoopT>
186 assert((Blocks.empty() || LIB[getHeader()] ==
this) &&
187 "Incorrect LI specified for this loop!");
188 assert(NewBB &&
"Cannot add a null basic block to the loop!");
189 assert(LIB[NewBB] == 0 &&
"BasicBlock already in the loop!");
191 LoopT *L =
static_cast<LoopT *
>(
this);
194 LIB.BBMap[NewBB] = L;
198 L->addBlockEntry(NewBB);
199 L = L->getParentLoop();
207 template<
class BlockT,
class LoopT>
210 assert(OldChild->ParentLoop ==
this &&
"This loop is already broken!");
211 assert(NewChild->ParentLoop == 0 &&
"NewChild already has a parent!");
212 typename std::vector<LoopT *>::iterator
I =
213 std::find(SubLoops.begin(), SubLoops.end(), OldChild);
214 assert(I != SubLoops.end() &&
"OldChild not in loop!");
216 OldChild->ParentLoop = 0;
217 NewChild->ParentLoop =
static_cast<LoopT *
>(
this);
221 template<
class BlockT,
class LoopT>
224 assert(!Blocks.empty() &&
"Loop header is missing");
228 getExitBlocks(ExitBBs);
230 VisitSet.
insert(ExitBBs.begin(), ExitBBs.end());
236 unsigned NumVisited = 0;
239 for ( ; BI != BE; ++BI) {
241 bool HasInsideLoopSuccs =
false;
242 bool HasInsideLoopPreds =
false;
246 for (
typename BlockTraits::ChildIteratorType SI =
247 BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
250 HasInsideLoopSuccs =
true;
254 for (
typename InvBlockTraits::ChildIteratorType PI =
255 InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
259 HasInsideLoopPreds =
true;
264 if (BB == getHeader()) {
265 assert(!OutsideLoopPreds.
empty() &&
"Loop is unreachable!");
266 }
else if (!OutsideLoopPreds.
empty()) {
270 BlockT *EntryBB = BB->getParent()->begin();
273 for (
unsigned i = 0, e = OutsideLoopPreds.
size(); i != e; ++i)
274 assert(*NI != OutsideLoopPreds[i] &&
275 "Loop has multiple entry points!");
277 assert(HasInsideLoopPreds &&
"Loop block has no in-loop predecessors!");
278 assert(HasInsideLoopSuccs &&
"Loop block has no in-loop successors!");
280 "Loop contains function entry block!");
285 assert(NumVisited == getNumBlocks() &&
"Unreachable block in loop");
290 for (
block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
292 assert(contains(*BI) &&
293 "Loop does not contain all the blocks of a subloop!");
298 assert(std::find(ParentLoop->begin(), ParentLoop->end(),
this) !=
300 "Loop is not a subloop of its parent!");
306 template<
class BlockT,
class LoopT>
309 Loops->
insert(static_cast<const LoopT *>(
this));
314 (*I)->verifyLoopNest(Loops);
317 template<
class BlockT,
class LoopT>
319 OS.
indent(Depth*2) <<
"Loop at depth " << getLoopDepth()
322 for (
unsigned i = 0; i < getBlocks().size(); ++i) {
324 BlockT *BB = getBlocks()[i];
326 if (BB == getHeader()) OS <<
"<header>";
327 if (BB == getLoopLatch()) OS <<
"<latch>";
328 if (isLoopExiting(BB)) OS <<
"<exiting>";
333 (*I)->print(OS, Depth+2);
344 template<
class BlockT,
class LoopT>
350 unsigned NumBlocks = 0;
351 unsigned NumSubloops = 0;
354 std::vector<BlockT *> ReverseCFGWorklist(Backedges.
begin(), Backedges.
end());
355 while (!ReverseCFGWorklist.empty()) {
356 BlockT *PredBB = ReverseCFGWorklist.back();
357 ReverseCFGWorklist.pop_back();
367 if (PredBB == L->getHeader())
370 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
371 InvBlockTraits::child_begin(PredBB),
372 InvBlockTraits::child_end(PredBB));
376 while (LoopT *Parent = Subloop->getParentLoop())
384 Subloop->setParentLoop(L);
386 NumBlocks += Subloop->getBlocks().capacity();
387 PredBB = Subloop->getHeader();
392 for (
typename InvBlockTraits::ChildIteratorType PI =
393 InvBlockTraits::child_begin(PredBB),
394 PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
396 ReverseCFGWorklist.push_back(*PI);
400 L->getSubLoopsVector().reserve(NumSubloops);
401 L->reserveBlocks(NumBlocks);
406 template<
class BlockT,
class LoopT>
407 class PopulateLoopsDFS {
408 typedef GraphTraits<BlockT*> BlockTraits;
409 typedef typename BlockTraits::ChildIteratorType SuccIterTy;
411 LoopInfoBase<BlockT, LoopT> *
LI;
413 std::vector<std::pair<BlockT*, SuccIterTy> >
DFSStack;
416 PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li):
419 void traverse(BlockT *EntryBlock);
422 void insertIntoLoop(BlockT *Block);
424 BlockT *dfsSource() {
return DFSStack.back().first; }
425 SuccIterTy &dfsSucc() {
return DFSStack.back().second; }
426 SuccIterTy dfsSuccEnd() {
return BlockTraits::child_end(dfsSource()); }
428 void pushBlock(BlockT *Block) {
429 DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block)));
435 template<
class BlockT,
class LoopT>
436 void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
437 pushBlock(EntryBlock);
441 while (dfsSucc() != dfsSuccEnd()) {
442 BlockT *BB = *dfsSucc();
451 insertIntoLoop(dfsSource());
459 template<
class BlockT,
class LoopT>
460 void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
461 LoopT *Subloop =
LI->getLoopFor(Block);
462 if (Subloop && Block == Subloop->getHeader()) {
465 if (Subloop->getParentLoop())
466 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
468 LI->addTopLevelLoop(Subloop);
472 Subloop->reverseBlock(1);
473 std::reverse(Subloop->getSubLoopsVector().begin(),
474 Subloop->getSubLoopsVector().end());
476 Subloop = Subloop->getParentLoop();
478 for (; Subloop; Subloop = Subloop->getParentLoop())
479 Subloop->addBlockEntry(Block);
496 template<
class BlockT,
class LoopT>
503 DomEnd =
po_end(DomRoot); DomIter != DomEnd; ++DomIter) {
505 BlockT *Header = DomIter->getBlock();
510 for (
typename InvBlockTraits::ChildIteratorType PI =
511 InvBlockTraits::child_begin(Header),
512 PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
514 BlockT *Backedge = *PI;
523 if (!Backedges.
empty()) {
524 LoopT *L =
new LoopT(Header);
530 PopulateLoopsDFS<BlockT, LoopT> DFS(
this);
535 template<
class BlockT,
class LoopT>
537 for (
unsigned i = 0; i < TopLevelLoops.size(); ++i)
538 TopLevelLoops[i]->print(OS);
541 E = BBMap.end();
I != E; ++
I)
542 OS <<
"BB '" <<
I->first->getName() <<
"' level = "
543 <<
I->second->getLoopDepth() <<
"\n";
void push_back(const T &Elt)
const_iterator end(StringRef path)
Get end iterator over path.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
DenseSet< const BlockT * > VisitedBlocks
void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)
const_iterator begin(StringRef path)
Get begin iterator over path.
void changeLoopFor(BlockT *BB, LoopT *L)
void print(raw_ostream &OS) const
DomTreeNodeBase< NodeT > * getRootNode()
LoopT * getLoopFor(const BlockT *BB) const
BlockT * getExitBlock() const
LoopInfoBase< BlockT, LoopT > * LI
BlockT * getLoopLatch() const
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
getExitEdges - Return all pairs of (inside_block,outside_block).
void WriteAsOperand(raw_ostream &, const Value *, bool PrintTy=true, const Module *Context=0)
void print(raw_ostream &OS, unsigned Depth=0) const
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
po_iterator< T > po_begin(T G)
std::vector< std::pair< BlockT *, SuccIterTy > > DFSStack
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
void verifyLoop() const
verifyLoop - Verify loop structure
BlockT * getLoopPreheader() const
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
df_iterator< T > df_end(const T &G)
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
BlockT * getExitingBlock() const
std::pair< const BlockT *, const BlockT * > Edge
Edge type.
std::pair< iterator, bool > insert(const ValueT &V)
df_iterator< T > df_begin(const T &G)
std::vector< BlockT * >::const_iterator block_iterator
void verifyLoopNest(DenseSet< const LoopT * > *Loops) const
verifyLoop - Verify loop structure of this loop and all nested loops.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B)
po_iterator< T > po_end(T G)
static void discoverAndMapSubloop(LoopT *L, ArrayRef< BlockT * > Backedges, LoopInfoBase< BlockT, LoopT > *LI, DominatorTreeBase< BlockT > &DomTree)
void Analyze(DominatorTreeBase< BlockT > &DomTree)
Create the loop forest using a stable algorithm.
BlockT * getLoopPredecessor() const
bool isReachableFromEntry(const NodeT *A) const
static const Function * getParent(const Value *V)
std::vector< LoopT * >::const_iterator iterator