#ifndef LLVM_ANALYSIS_LOOP_INFO_H
#define LLVM_ANALYSIS_LOOP_INFO_H
#include "llvm/Pass.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <map>
namespace llvm {
template<typename T>
static void RemoveFromVector(std::vector<T*> &V, T *N) {
typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
assert(I != V.end() && "N is not in this list!");
V.erase(I);
}
class DominatorTree;
class LoopInfo;
class Loop;
class PHINode;
template<class N, class M> class LoopInfoBase;
template<class N, class M> class LoopBase;
template<class BlockT, class LoopT>
class LoopBase {
LoopT *ParentLoop;
std::vector<LoopT *> SubLoops;
std::vector<BlockT*> Blocks;
LoopBase(const LoopBase<BlockT, LoopT> &);
const LoopBase<BlockT, LoopT>&operator=(const LoopBase<BlockT, LoopT> &);
public:
LoopBase() : ParentLoop(0) {}
~LoopBase() {
for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
delete SubLoops[i];
}
unsigned getLoopDepth() const {
unsigned D = 1;
for (const LoopT *CurLoop = ParentLoop; CurLoop;
CurLoop = CurLoop->ParentLoop)
++D;
return D;
}
BlockT *getHeader() const { return Blocks.front(); }
LoopT *getParentLoop() const { return ParentLoop; }
bool contains(const LoopT *L) const {
if (L == this) return true;
if (L == 0) return false;
return contains(L->getParentLoop());
}
bool contains(const BlockT *BB) const {
return std::find(block_begin(), block_end(), BB) != block_end();
}
template<class InstT>
bool contains(const InstT *Inst) const {
return contains(Inst->getParent());
}
const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
typedef typename std::vector<LoopT *>::const_iterator iterator;
iterator begin() const { return SubLoops.begin(); }
iterator end() const { return SubLoops.end(); }
bool empty() const { return SubLoops.empty(); }
const std::vector<BlockT*> &getBlocks() const { return Blocks; }
typedef typename std::vector<BlockT*>::const_iterator block_iterator;
block_iterator block_begin() const { return Blocks.begin(); }
block_iterator block_end() const { return Blocks.end(); }
bool isLoopExiting(const BlockT *BB) const {
typedef GraphTraits<BlockT*> BlockTraits;
for (typename BlockTraits::ChildIteratorType SI =
BlockTraits::child_begin(const_cast<BlockT*>(BB)),
SE = BlockTraits::child_end(const_cast<BlockT*>(BB)); SI != SE; ++SI) {
if (!contains(*SI))
return true;
}
return false;
}
unsigned getNumBackEdges() const {
unsigned NumBackEdges = 0;
BlockT *H = getHeader();
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
for (typename InvBlockTraits::ChildIteratorType I =
InvBlockTraits::child_begin(const_cast<BlockT*>(H)),
E = InvBlockTraits::child_end(const_cast<BlockT*>(H)); I != E; ++I)
if (contains(*I))
++NumBackEdges;
return NumBackEdges;
}
void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
std::sort(LoopBBs.begin(), LoopBBs.end());
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
ExitingBlocks.push_back(*BI);
break;
}
}
BlockT *getExitingBlock() const {
SmallVector<BlockT*, 8> ExitingBlocks;
getExitingBlocks(ExitingBlocks);
if (ExitingBlocks.size() == 1)
return ExitingBlocks[0];
return 0;
}
void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
std::sort(LoopBBs.begin(), LoopBBs.end());
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
ExitBlocks.push_back(*I);
}
BlockT *getExitBlock() const {
SmallVector<BlockT*, 8> ExitBlocks;
getExitBlocks(ExitBlocks);
if (ExitBlocks.size() == 1)
return ExitBlocks[0];
return 0;
}
typedef std::pair<BlockT*, BlockT*> Edge;
template <typename EdgeT>
void getExitEdges(SmallVectorImpl<EdgeT> &ExitEdges) const {
SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
array_pod_sort(LoopBBs.begin(), LoopBBs.end());
typedef GraphTraits<BlockT*> BlockTraits;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
for (typename BlockTraits::ChildIteratorType I =
BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
I != E; ++I)
if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
ExitEdges.push_back(EdgeT(*BI, *I));
}
BlockT *getLoopPreheader() const {
BlockT *Out = getLoopPredecessor();
if (!Out) return 0;
typedef GraphTraits<BlockT*> BlockTraits;
typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
++SI;
if (SI != BlockTraits::child_end(Out))
return 0;
return Out;
}
BlockT *getLoopPredecessor() const {
BlockT *Out = 0;
BlockT *Header = getHeader();
typedef GraphTraits<BlockT*> BlockTraits;
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
for (typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(Header),
PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
typename InvBlockTraits::NodeType *N = *PI;
if (!contains(N)) { if (Out && Out != N)
return 0; Out = N;
}
}
assert(Out && "Header of loop has no predecessors from outside loop?");
return Out;
}
BlockT *getLoopLatch() const {
BlockT *Header = getHeader();
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(Header);
typename InvBlockTraits::ChildIteratorType PE =
InvBlockTraits::child_end(Header);
BlockT *Latch = 0;
for (; PI != PE; ++PI) {
typename InvBlockTraits::NodeType *N = *PI;
if (contains(N)) {
if (Latch) return 0;
Latch = N;
}
}
return Latch;
}
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI);
void replaceChildLoopWith(LoopT *OldChild,
LoopT *NewChild) {
assert(OldChild->ParentLoop == this && "This loop is already broken!");
assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
typename std::vector<LoopT *>::iterator I =
std::find(SubLoops.begin(), SubLoops.end(), OldChild);
assert(I != SubLoops.end() && "OldChild not in loop!");
*I = NewChild;
OldChild->ParentLoop = 0;
NewChild->ParentLoop = static_cast<LoopT *>(this);
}
void addChildLoop(LoopT *NewChild) {
assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
NewChild->ParentLoop = static_cast<LoopT *>(this);
SubLoops.push_back(NewChild);
}
LoopT *removeChildLoop(iterator I) {
assert(I != SubLoops.end() && "Cannot remove end iterator!");
LoopT *Child = *I;
assert(Child->ParentLoop == this && "Child is not a child of this loop!");
SubLoops.erase(SubLoops.begin()+(I-begin()));
Child->ParentLoop = 0;
return Child;
}
void addBlockEntry(BlockT *BB) {
Blocks.push_back(BB);
}
void moveToHeader(BlockT *BB) {
if (Blocks[0] == BB) return;
for (unsigned i = 0; ; ++i) {
assert(i != Blocks.size() && "Loop does not contain BB!");
if (Blocks[i] == BB) {
Blocks[i] = Blocks[0];
Blocks[0] = BB;
return;
}
}
}
void removeBlockFromLoop(BlockT *BB) {
RemoveFromVector(Blocks, BB);
}
void verifyLoop() const {
#ifndef NDEBUG
assert(!Blocks.empty() && "Loop header is missing");
SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
std::sort(LoopBBs.begin(), LoopBBs.end());
for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
BlockT *BB = *I;
bool HasInsideLoopSuccs = false;
bool HasInsideLoopPreds = false;
SmallVector<BlockT *, 2> OutsideLoopPreds;
typedef GraphTraits<BlockT*> BlockTraits;
for (typename BlockTraits::ChildIteratorType SI =
BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
SI != SE; ++SI)
if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
HasInsideLoopSuccs = true;
break;
}
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
for (typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
PI != PE; ++PI) {
typename InvBlockTraits::NodeType *N = *PI;
if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
HasInsideLoopPreds = true;
else
OutsideLoopPreds.push_back(N);
}
if (BB == getHeader()) {
assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
} else if (!OutsideLoopPreds.empty()) {
BlockT *EntryBB = BB->getParent()->begin();
for (df_iterator<BlockT *> NI = df_begin(EntryBB),
NE = df_end(EntryBB); NI != NE; ++NI)
for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
assert(*NI != OutsideLoopPreds[i] &&
"Loop has multiple entry points!");
}
assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
assert(BB != getHeader()->getParent()->begin() &&
"Loop contains function entry block!");
}
for (iterator I = begin(), E = end(); I != E; ++I)
for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
BI != BE; ++BI) {
assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
"Loop does not contain all the blocks of a subloop!");
}
if (ParentLoop) {
assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
ParentLoop->end() &&
"Loop is not a subloop of its parent!");
}
#endif
}
void verifyLoopNest() const {
verifyLoop();
for (iterator I = begin(), E = end(); I != E; ++I)
(*I)->verifyLoopNest();
}
void print(raw_ostream &OS, unsigned Depth = 0) const {
OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()
<< " containing: ";
for (unsigned i = 0; i < getBlocks().size(); ++i) {
if (i) OS << ",";
BlockT *BB = getBlocks()[i];
WriteAsOperand(OS, BB, false);
if (BB == getHeader()) OS << "<header>";
if (BB == getLoopLatch()) OS << "<latch>";
if (isLoopExiting(BB)) OS << "<exiting>";
}
OS << "\n";
for (iterator I = begin(), E = end(); I != E; ++I)
(*I)->print(OS, Depth+2);
}
protected:
friend class LoopInfoBase<BlockT, LoopT>;
explicit LoopBase(BlockT *BB) : ParentLoop(0) {
Blocks.push_back(BB);
}
};
template<class BlockT, class LoopT>
raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
Loop.print(OS);
return OS;
}
class Loop : public LoopBase<BasicBlock, Loop> {
public:
Loop() {}
bool isLoopInvariant(Value *V) const;
bool hasLoopInvariantOperands(Instruction *I) const;
bool makeLoopInvariant(Value *V, bool &Changed,
Instruction *InsertPt = 0) const;
bool makeLoopInvariant(Instruction *I, bool &Changed,
Instruction *InsertPt = 0) const;
PHINode *getCanonicalInductionVariable() const;
Value *getTripCount() const;
unsigned getSmallConstantTripCount() const;
unsigned getSmallConstantTripMultiple() const;
bool isLCSSAForm(DominatorTree &DT) const;
bool isLoopSimplifyForm() const;
bool hasDedicatedExits() const;
void getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const;
BasicBlock *getUniqueExitBlock() const;
void dump() const;
private:
friend class LoopInfoBase<BasicBlock, Loop>;
explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
};
template<class BlockT, class LoopT>
class LoopInfoBase {
DenseMap<BlockT *, LoopT *> BBMap;
std::vector<LoopT *> TopLevelLoops;
friend class LoopBase<BlockT, LoopT>;
void operator=(const LoopInfoBase &); LoopInfoBase(const LoopInfo &); public:
LoopInfoBase() { }
~LoopInfoBase() { releaseMemory(); }
void releaseMemory() {
for (typename std::vector<LoopT *>::iterator I =
TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I)
delete *I;
BBMap.clear(); TopLevelLoops.clear();
}
typedef typename std::vector<LoopT *>::const_iterator iterator;
iterator begin() const { return TopLevelLoops.begin(); }
iterator end() const { return TopLevelLoops.end(); }
bool empty() const { return TopLevelLoops.empty(); }
LoopT *getLoopFor(const BlockT *BB) const {
typename DenseMap<BlockT *, LoopT *>::const_iterator I=
BBMap.find(const_cast<BlockT*>(BB));
return I != BBMap.end() ? I->second : 0;
}
const LoopT *operator[](const BlockT *BB) const {
return getLoopFor(BB);
}
unsigned getLoopDepth(const BlockT *BB) const {
const LoopT *L = getLoopFor(BB);
return L ? L->getLoopDepth() : 0;
}
bool isLoopHeader(BlockT *BB) const {
const LoopT *L = getLoopFor(BB);
return L && L->getHeader() == BB;
}
LoopT *removeLoop(iterator I) {
assert(I != end() && "Cannot remove end iterator!");
LoopT *L = *I;
assert(L->getParentLoop() == 0 && "Not a top-level loop!");
TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
return L;
}
void changeLoopFor(BlockT *BB, LoopT *L) {
LoopT *&OldLoop = BBMap[BB];
assert(OldLoop && "Block not in a loop yet!");
OldLoop = L;
}
void changeTopLevelLoop(LoopT *OldLoop,
LoopT *NewLoop) {
typename std::vector<LoopT *>::iterator I =
std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop);
assert(I != TopLevelLoops.end() && "Old loop not at top level!");
*I = NewLoop;
assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
"Loops already embedded into a subloop!");
}
void addTopLevelLoop(LoopT *New) {
assert(New->getParentLoop() == 0 && "Loop already in subloop!");
TopLevelLoops.push_back(New);
}
void removeBlock(BlockT *BB) {
typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB);
if (I != BBMap.end()) {
for (LoopT *L = I->second; L; L = L->getParentLoop())
L->removeBlockFromLoop(BB);
BBMap.erase(I);
}
}
static bool isNotAlreadyContainedIn(const LoopT *SubLoop,
const LoopT *ParentLoop) {
if (SubLoop == 0) return true;
if (SubLoop == ParentLoop) return false;
return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
}
void Calculate(DominatorTreeBase<BlockT> &DT) {
BlockT *RootNode = DT.getRootNode()->getBlock();
for (df_iterator<BlockT*> NI = df_begin(RootNode),
NE = df_end(RootNode); NI != NE; ++NI)
if (LoopT *L = ConsiderForLoop(*NI, DT))
TopLevelLoops.push_back(L);
}
LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
if (BBMap.find(BB) != BBMap.end()) return 0;
std::vector<BlockT *> TodoStack;
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
for (typename InvBlockTraits::ChildIteratorType I =
InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
I != E; ++I) {
typename InvBlockTraits::NodeType *N = *I;
if (DT.dominates(BB, N)) TodoStack.push_back(N);
}
if (TodoStack.empty()) return 0;
LoopT *L = new LoopT(BB);
BBMap[BB] = L;
BlockT *EntryBlock = BB->getParent()->begin();
while (!TodoStack.empty()) { BlockT *X = TodoStack.back();
TodoStack.pop_back();
if (!L->contains(X) && DT.dominates(EntryBlock, X)) { if (LoopT *SubLoop =
const_cast<LoopT *>(getLoopFor(X)))
if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
LoopT *SLP = SubLoop->ParentLoop; typename std::vector<LoopT *>::iterator I =
std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
SLP->SubLoops.erase(I);
SubLoop->ParentLoop = L;
L->SubLoops.push_back(SubLoop);
}
L->Blocks.push_back(X);
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
InvBlockTraits::child_end(X));
}
}
for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
E = L->Blocks.end(); I != E; ++I)
if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {
L->SubLoops.push_back(NewLoop);
NewLoop->ParentLoop = L;
}
for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
E = L->Blocks.end(); I != E; ++I)
BBMap.insert(std::make_pair(*I, L));
{
std::map<BlockT *, LoopT *> ContainingLoops;
for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
LoopT *Child = L->SubLoops[i];
assert(Child->getParentLoop() == L && "Not proper child loop?");
if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
MoveSiblingLoopInto(Child, ContainingLoop);
--i; } else {
for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
if (BlockLoop == 0) { BlockLoop = Child;
} else if (BlockLoop != Child) {
LoopT *SubLoop = BlockLoop;
for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)
ContainingLoops[SubLoop->Blocks[j]] = Child;
MoveSiblingLoopInto(SubLoop, Child);
--i; }
}
}
}
}
return L;
}
void MoveSiblingLoopInto(LoopT *NewChild,
LoopT *NewParent) {
LoopT *OldParent = NewChild->getParentLoop();
assert(OldParent && OldParent == NewParent->getParentLoop() &&
NewChild != NewParent && "Not sibling loops!");
typename std::vector<LoopT *>::iterator I =
std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
NewChild);
assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
OldParent->SubLoops.erase(I); NewChild->ParentLoop = 0;
InsertLoopInto(NewChild, NewParent);
}
void InsertLoopInto(LoopT *L, LoopT *Parent) {
BlockT *LHeader = L->getHeader();
assert(Parent->contains(LHeader) &&
"This loop should not be inserted here!");
for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
i != e; ++i)
if (Parent->SubLoops[i]->contains(LHeader)) {
InsertLoopInto(L, Parent->SubLoops[i]);
return;
}
Parent->SubLoops.push_back(L);
L->ParentLoop = Parent;
}
void print(raw_ostream &OS) const {
for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
TopLevelLoops[i]->print(OS);
#if 0
for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
E = BBMap.end(); I != E; ++I)
OS << "BB '" << I->first->getName() << "' level = "
<< I->second->getLoopDepth() << "\n";
#endif
}
};
class LoopInfo : public FunctionPass {
LoopInfoBase<BasicBlock, Loop> LI;
friend class LoopBase<BasicBlock, Loop>;
void operator=(const LoopInfo &); LoopInfo(const LoopInfo &); public:
static char ID;
LoopInfo() : FunctionPass(ID) {
initializeLoopInfoPass(*PassRegistry::getPassRegistry());
}
LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; }
typedef LoopInfoBase<BasicBlock, Loop>::iterator iterator;
inline iterator begin() const { return LI.begin(); }
inline iterator end() const { return LI.end(); }
bool empty() const { return LI.empty(); }
inline Loop *getLoopFor(const BasicBlock *BB) const {
return LI.getLoopFor(BB);
}
inline const Loop *operator[](const BasicBlock *BB) const {
return LI.getLoopFor(BB);
}
inline unsigned getLoopDepth(const BasicBlock *BB) const {
return LI.getLoopDepth(BB);
}
inline bool isLoopHeader(BasicBlock *BB) const {
return LI.isLoopHeader(BB);
}
virtual bool runOnFunction(Function &F);
virtual void verifyAnalysis() const;
virtual void releaseMemory() { LI.releaseMemory(); }
virtual void print(raw_ostream &O, const Module* M = 0) const;
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); }
inline void changeLoopFor(BasicBlock *BB, Loop *L) {
LI.changeLoopFor(BB, L);
}
inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
LI.changeTopLevelLoop(OldLoop, NewLoop);
}
inline void addTopLevelLoop(Loop *New) {
LI.addTopLevelLoop(New);
}
void removeBlock(BasicBlock *BB) {
LI.removeBlock(BB);
}
bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
Instruction *I = dyn_cast<Instruction>(To);
if (!I) return true;
if (I->getParent() == From->getParent())
return true;
Loop *ToLoop = getLoopFor(I->getParent());
if (!ToLoop) return true;
return ToLoop->contains(getLoopFor(From->getParent()));
}
};
template <> struct GraphTraits<const Loop*> {
typedef const Loop NodeType;
typedef LoopInfo::iterator ChildIteratorType;
static NodeType *getEntryNode(const Loop *L) { return L; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
template <> struct GraphTraits<Loop*> {
typedef Loop NodeType;
typedef LoopInfo::iterator ChildIteratorType;
static NodeType *getEntryNode(Loop *L) { return L; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
template<class BlockT, class LoopT>
void
LoopBase<BlockT, LoopT>::addBasicBlockToLoop(BlockT *NewBB,
LoopInfoBase<BlockT, LoopT> &LIB) {
assert((Blocks.empty() || LIB[getHeader()] == this) &&
"Incorrect LI specified for this loop!");
assert(NewBB && "Cannot add a null basic block to the loop!");
assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
LoopT *L = static_cast<LoopT *>(this);
LIB.BBMap[NewBB] = L;
while (L) {
L->Blocks.push_back(NewBB);
L = L->getParentLoop();
}
}
}
#endif