#ifndef LLVM_ANALYSIS_LOOP_INFO_H
#define LLVM_ANALYSIS_LOOP_INFO_H
#include "llvm/Pass.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Streams.h"
#include <algorithm>
#include <ostream>
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;
template<class N> class LoopInfoBase;
template<class N> class LoopBase;
typedef LoopBase<BasicBlock> Loop;
template<class BlockT>
class LoopBase {
LoopBase<BlockT> *ParentLoop;
std::vector<LoopBase<BlockT>*> SubLoops;
std::vector<BlockT*> Blocks;
LoopBase(const LoopBase<BlockT> &); const LoopBase<BlockT>&operator=(const LoopBase<BlockT> &);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 LoopBase<BlockT> *CurLoop = ParentLoop; CurLoop;
CurLoop = CurLoop->ParentLoop)
++D;
return D;
}
BlockT *getHeader() const { return Blocks.front(); }
LoopBase<BlockT> *getParentLoop() const { return ParentLoop; }
bool contains(const BlockT *BB) const {
return std::find(block_begin(), block_end(), BB) != block_end();
}
const std::vector<LoopBase<BlockT>*> &getSubLoops() const { return SubLoops; }
typedef typename std::vector<LoopBase<BlockT>*>::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 isLoopExit(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;
}
inline bool isLoopInvariant(Value *V) const {
if (Instruction *I = dyn_cast<Instruction>(V))
return !contains(I->getParent());
return true; }
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);
}
void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
std::sort(LoopBBs.begin(), LoopBBs.end());
std::vector<BlockT*> switchExitBlocks;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) {
BlockT *current = *BI;
switchExitBlocks.clear();
typedef GraphTraits<BlockT*> BlockTraits;
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
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))
continue;
typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(*I);
BlockT *firstPred = *PI;
if (current != firstPred)
continue;
if (std::distance(BlockTraits::child_begin(current),
BlockTraits::child_end(current)) <= 2) {
ExitBlocks.push_back(*I);
continue;
}
if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I)
== switchExitBlocks.end()) {
switchExitBlocks.push_back(*I);
ExitBlocks.push_back(*I);
}
}
}
}
BlockT *getLoopPreheader() 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)
if (!contains(*PI)) { if (Out && Out != *PI)
return 0; Out = *PI;
}
assert(Out && "Header of loop has no predecessors from outside loop?");
typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
++SI;
if (SI != BlockTraits::child_end(Out))
return 0;
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);
if (PI == PE) return 0;
BlockT *Latch = 0;
if (contains(*PI))
Latch = *PI;
++PI;
if (PI == PE) return 0;
if (contains(*PI)) {
if (Latch) return 0; Latch = *PI;
}
++PI;
if (PI != PE) return 0;
return Latch;
}
inline PHINode *getCanonicalInductionVariable() const {
BlockT *H = getHeader();
BlockT *Incoming = 0, *Backedge = 0;
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
typename InvBlockTraits::ChildIteratorType PI =
InvBlockTraits::child_begin(H);
assert(PI != InvBlockTraits::child_end(H) &&
"Loop must have at least one backedge!");
Backedge = *PI++;
if (PI == InvBlockTraits::child_end(H)) return 0; Incoming = *PI++;
if (PI != InvBlockTraits::child_end(H)) return 0;
if (contains(Incoming)) {
if (contains(Backedge))
return 0;
std::swap(Incoming, Backedge);
} else if (!contains(Backedge))
return 0;
for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
if (ConstantInt *CI =
dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
if (CI->isNullValue())
if (Instruction *Inc =
dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
if (Inc->getOpcode() == Instruction::Add &&
Inc->getOperand(0) == PN)
if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
if (CI->equalsInt(1))
return PN;
}
return 0;
}
inline Instruction *getCanonicalInductionVariableIncrement() const {
if (PHINode *PN = getCanonicalInductionVariable()) {
bool P1InLoop = contains(PN->getIncomingBlock(1));
return cast<Instruction>(PN->getIncomingValue(P1InLoop));
}
return 0;
}
inline Value *getTripCount() const {
Instruction *Inc = getCanonicalInductionVariableIncrement();
if (Inc == 0) return 0;
PHINode *IV = cast<PHINode>(Inc->getOperand(0));
BlockT *BackedgeBlock =
IV->getIncomingBlock(contains(IV->getIncomingBlock(1)));
if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator()))
if (BI->isConditional()) {
if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) {
if (ICI->getOperand(0) == Inc) {
if (BI->getSuccessor(0) == getHeader()) {
if (ICI->getPredicate() == ICmpInst::ICMP_NE)
return ICI->getOperand(1);
} else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) {
return ICI->getOperand(1);
}
}
}
}
return 0;
}
inline unsigned getSmallConstantTripCount() const {
Value* TripCount = this->getTripCount();
if (TripCount) {
if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) {
if (TripCountC->getValue().getActiveBits() <= 32) {
return (unsigned)TripCountC->getZExtValue();
}
}
}
return 0;
}
inline unsigned getSmallConstantTripMultiple() const {
Value* TripCount = this->getTripCount();
ConstantInt *Result = NULL;
if (TripCount) {
Result = dyn_cast<ConstantInt>(TripCount);
if (!Result)
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) {
switch (BO->getOpcode()) {
case BinaryOperator::Mul:
Result = dyn_cast<ConstantInt>(BO->getOperand(1));
break;
default:
break;
}
}
}
if (Result && Result->getValue().getActiveBits() <= 32) {
return (unsigned)Result->getZExtValue();
} else {
return 1;
}
}
inline bool isLCSSAForm() const {
SmallPtrSet<BlockT*, 16> LoopBBs(block_begin(), block_end());
for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) {
BlockT *BB = *BI;
for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E;++I)
for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
++UI) {
BlockT *UserBB = cast<Instruction>(*UI)->getParent();
if (PHINode *P = dyn_cast<PHINode>(*UI)) {
UserBB = P->getIncomingBlock(UI);
}
if (UserBB != BB && !LoopBBs.count(UserBB))
return false;
}
}
return true;
}
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT> &LI);
void replaceChildLoopWith(LoopBase<BlockT> *OldChild,
LoopBase<BlockT> *NewChild) {
assert(OldChild->ParentLoop == this && "This loop is already broken!");
assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
typename std::vector<LoopBase<BlockT>*>::iterator I =
std::find(SubLoops.begin(), SubLoops.end(), OldChild);
assert(I != SubLoops.end() && "OldChild not in loop!");
*I = NewChild;
OldChild->ParentLoop = 0;
NewChild->ParentLoop = this;
}
void addChildLoop(LoopBase<BlockT> *NewChild) {
assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
NewChild->ParentLoop = this;
SubLoops.push_back(NewChild);
}
LoopBase<BlockT> *removeChildLoop(iterator I) {
assert(I != SubLoops.end() && "Cannot remove end iterator!");
LoopBase<BlockT> *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 (getHeader() && "Loop header is missing");
assert (getLoopPreheader() && "Loop preheader is missing");
assert (getLoopLatch() && "Loop latch is missing");
for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
(*I)->verifyLoop();
#endif
}
void print(std::ostream &OS, unsigned Depth = 0) const {
OS << std::string(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 (isLoopExit(BB)) OS << "<exit>";
}
OS << "\n";
for (iterator I = begin(), E = end(); I != E; ++I)
(*I)->print(OS, Depth+2);
}
void print(std::ostream *O, unsigned Depth = 0) const {
if (O) print(*O, Depth);
}
void dump() const {
print(cerr);
}
private:
friend class LoopInfoBase<BlockT>;
explicit LoopBase(BlockT *BB) : ParentLoop(0) {
Blocks.push_back(BB);
}
};
template<class BlockT>
class LoopInfoBase {
std::map<BlockT*, LoopBase<BlockT>*> BBMap;
std::vector<LoopBase<BlockT>*> TopLevelLoops;
friend class LoopBase<BlockT>;
public:
LoopInfoBase() { }
~LoopInfoBase() { releaseMemory(); }
void releaseMemory() {
for (typename std::vector<LoopBase<BlockT>* >::iterator I =
TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I)
delete *I;
BBMap.clear(); TopLevelLoops.clear();
}
typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator;
iterator begin() const { return TopLevelLoops.begin(); }
iterator end() const { return TopLevelLoops.end(); }
bool empty() const { return TopLevelLoops.empty(); }
LoopBase<BlockT> *getLoopFor(const BlockT *BB) const {
typename std::map<BlockT *, LoopBase<BlockT>*>::const_iterator I=
BBMap.find(const_cast<BlockT*>(BB));
return I != BBMap.end() ? I->second : 0;
}
const LoopBase<BlockT> *operator[](const BlockT *BB) const {
return getLoopFor(BB);
}
unsigned getLoopDepth(const BlockT *BB) const {
const LoopBase<BlockT> *L = getLoopFor(BB);
return L ? L->getLoopDepth() : 0;
}
bool isLoopHeader(BlockT *BB) const {
const LoopBase<BlockT> *L = getLoopFor(BB);
return L && L->getHeader() == BB;
}
LoopBase<BlockT> *removeLoop(iterator I) {
assert(I != end() && "Cannot remove end iterator!");
LoopBase<BlockT> *L = *I;
assert(L->getParentLoop() == 0 && "Not a top-level loop!");
TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
return L;
}
void changeLoopFor(BlockT *BB, LoopBase<BlockT> *L) {
LoopBase<BlockT> *&OldLoop = BBMap[BB];
assert(OldLoop && "Block not in a loop yet!");
OldLoop = L;
}
void changeTopLevelLoop(LoopBase<BlockT> *OldLoop,
LoopBase<BlockT> *NewLoop) {
typename std::vector<LoopBase<BlockT>*>::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(LoopBase<BlockT> *New) {
assert(New->getParentLoop() == 0 && "Loop already in subloop!");
TopLevelLoops.push_back(New);
}
void removeBlock(BlockT *BB) {
typename std::map<BlockT *, LoopBase<BlockT>*>::iterator I = BBMap.find(BB);
if (I != BBMap.end()) {
for (LoopBase<BlockT> *L = I->second; L; L = L->getParentLoop())
L->removeBlockFromLoop(BB);
BBMap.erase(I);
}
}
static bool isNotAlreadyContainedIn(const LoopBase<BlockT> *SubLoop,
const LoopBase<BlockT> *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 (LoopBase<BlockT> *L = ConsiderForLoop(*NI, DT))
TopLevelLoops.push_back(L);
}
LoopBase<BlockT> *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)
if (DT.dominates(BB, *I)) TodoStack.push_back(*I);
if (TodoStack.empty()) return 0;
LoopBase<BlockT> *L = new LoopBase<BlockT>(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 (LoopBase<BlockT> *SubLoop =
const_cast<LoopBase<BlockT>*>(getLoopFor(X)))
if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
LoopBase<BlockT> *SLP = SubLoop->ParentLoop; typename std::vector<LoopBase<BlockT>*>::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 (LoopBase<BlockT> *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) {
typename std::map<BlockT*, LoopBase<BlockT>*>::iterator BBMI =
BBMap.find(*I);
if (BBMI == BBMap.end()) BBMap.insert(BBMI, std::make_pair(*I, L)); }
{
std::map<BlockT*, LoopBase<BlockT>*> ContainingLoops;
for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
LoopBase<BlockT> *Child = L->SubLoops[i];
assert(Child->getParentLoop() == L && "Not proper child loop?");
if (LoopBase<BlockT> *ContainingLoop =
ContainingLoops[Child->getHeader()]) {
MoveSiblingLoopInto(Child, ContainingLoop);
--i; } else {
for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
LoopBase<BlockT> *&BlockLoop = ContainingLoops[Child->Blocks[b]];
if (BlockLoop == 0) { BlockLoop = Child;
} else if (BlockLoop != Child) {
LoopBase<BlockT> *SubLoop = BlockLoop;
for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j)
ContainingLoops[SubLoop->Blocks[j]] = Child;
MoveSiblingLoopInto(SubLoop, Child);
--i; }
}
}
}
}
return L;
}
void MoveSiblingLoopInto(LoopBase<BlockT> *NewChild,
LoopBase<BlockT> *NewParent) {
LoopBase<BlockT> *OldParent = NewChild->getParentLoop();
assert(OldParent && OldParent == NewParent->getParentLoop() &&
NewChild != NewParent && "Not sibling loops!");
typename std::vector<LoopBase<BlockT>*>::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(LoopBase<BlockT> *L, LoopBase<BlockT> *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(std::ostream &OS, const Module* ) const {
for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
TopLevelLoops[i]->print(OS);
#if 0
for (std::map<BasicBlock*, Loop*>::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>* LI;
friend class LoopBase<BasicBlock>;
public:
static char ID;
LoopInfo() : FunctionPass(&ID) {
LI = new LoopInfoBase<BasicBlock>();
}
~LoopInfo() { delete LI; }
LoopInfoBase<BasicBlock>& getBase() { return *LI; }
typedef std::vector<Loop*>::const_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 releaseMemory() { LI->releaseMemory(); }
virtual void print(std::ostream &O, const Module* M = 0) const {
if (O) LI->print(O, M);
}
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);
}
};
template <> struct GraphTraits<const Loop*> {
typedef const Loop NodeType;
typedef std::vector<Loop*>::const_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 std::vector<Loop*>::const_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>
void LoopBase<BlockT>::addBasicBlockToLoop(BlockT *NewBB,
LoopInfoBase<BlockT> &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!");
LIB.BBMap[NewBB] = this;
LoopBase<BlockT> *L = this;
while (L) {
L->Blocks.push_back(NewBB);
L = L->getParentLoop();
}
}
}
#endif