//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfo class that is used to identify natural loops
#include "llvm/Analysis/Dominators.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
-#include "Support/DepthFirstIterator.h"
+#include "llvm/ADT/DepthFirstIterator.h"
#include <algorithm>
+#include <iostream>
using namespace llvm;
static RegisterAnalysis<LoopInfo>
// Loop implementation
//
bool Loop::contains(const BasicBlock *BB) const {
- return find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
+ return std::find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
}
bool Loop::isLoopExit(const BasicBlock *BB) const {
BasicBlock *RootNode = DS.getRoot();
for (df_iterator<BasicBlock*> NI = df_begin(RootNode),
- NE = df_end(RootNode); NI != NE; ++NI)
+ NE = df_end(RootNode); NI != NE; ++NI)
if (Loop *L = ConsiderForLoop(*NI, DS))
TopLevelLoops.push_back(L);
}
AU.addRequired<DominatorSet>();
}
-void LoopInfo::print(std::ostream &OS) const {
+void LoopInfo::print(std::ostream &OS, const Module* ) const {
for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
TopLevelLoops[i]->print(OS);
#if 0
std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
assert(I != SLP->SubLoops.end() && "SubLoop not a child of parent?");
SLP->SubLoops.erase(I); // Remove from parent...
-
+
// Add the subloop to THIS loop...
SubLoop->ParentLoop = L;
L->SubLoops.push_back(SubLoop);
// Normal case, add the block to our loop...
L->Blocks.push_back(X);
-
+
// Add all of the predecessors of X to the end of the work stack...
TodoStack.insert(TodoStack.end(), pred_begin(X), pred_end(X));
}
// If there are any loops nested within this loop, create them now!
for (std::vector<BasicBlock*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
+ E = L->Blocks.end(); I != E; ++I)
if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
L->SubLoops.push_back(NewLoop);
NewLoop->ParentLoop = L;
// loop can be found for them.
//
for (std::vector<BasicBlock*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I) {
+ E = L->Blocks.end(); I != E; ++I) {
std::map<BasicBlock*, Loop*>::iterator BBMI = BBMap.lower_bound(*I);
if (BBMI == BBMap.end() || BBMI->first != *I) // Not in map yet...
BBMap.insert(BBMI, std::make_pair(*I, L)); // Must be at this level
--i; // We just shrunk the SubLoops list.
}
}
- }
+ }
}
}
assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
OldParent->SubLoops.erase(I); // Remove from parent's subloops list
NewChild->ParentLoop = 0;
-
- InsertLoopInto(NewChild, NewParent);
+
+ InsertLoopInto(NewChild, NewParent);
}
/// InsertLoopInto - This inserts loop L into the specified parent loop. If the
void LoopInfo::InsertLoopInto(Loop *L, Loop *Parent) {
BasicBlock *LHeader = L->getHeader();
assert(Parent->contains(LHeader) && "This loop should not be inserted here!");
-
+
// Check to see if it belongs in a child loop...
for (unsigned i = 0, e = Parent->SubLoops.size(); i != e; ++i)
if (Parent->SubLoops[i]->contains(LHeader)) {
InsertLoopInto(L, Parent->SubLoops[i]);
return;
- }
+ }
// If not, insert it here!
Parent->SubLoops.push_back(L);
if (I != BBMap.end()) {
for (Loop *L = I->second; L; L = L->getParentLoop())
L->removeBlockFromLoop(BB);
-
+
BBMap.erase(I);
}
}
return 0; // Multiple predecessors outside the loop
Out = *PI;
}
-
+
// Make sure there is only one exit out of the preheader...
succ_iterator SI = succ_begin(Out);
++SI;
if (SI != succ_end(Out))
return 0; // Multiple exits from the block, must not be a preheader.
-
// If there is exactly one preheader, return it. If there was zero, then Out
// is still null.
return Out;
}
+/// getLoopLatch - If there is a latch block for this loop, return it. A
+/// latch block is the canonical backedge for a loop. A loop header in normal
+/// form has two edges into it: one from a preheader and one from a latch
+/// block.
+BasicBlock *Loop::getLoopLatch() const {
+ BasicBlock *Header = getHeader();
+ pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
+ if (PI == PE) return 0; // no preds?
+
+ BasicBlock *Latch = 0;
+ if (contains(*PI))
+ Latch = *PI;
+ ++PI;
+ if (PI == PE) return 0; // only one pred?
+
+ if (contains(*PI)) {
+ if (Latch) return 0; // multiple backedges
+ Latch = *PI;
+ }
+ ++PI;
+ if (PI != PE) return 0; // more than two preds
+
+ return Latch;
+}
+
/// getCanonicalInductionVariable - Check to see if the loop has a canonical
/// induction variable: an integer recurrence that starts at 0 and increments by
/// one each time through the loop. If so, return the phi node that corresponds
return 0;
// Loop over all of the PHI nodes, looking for a canonical indvar.
- for (BasicBlock::iterator I = H->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
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;
}
Instruction *Inc = getCanonicalInductionVariableIncrement();
if (Inc == 0) return 0;
PHINode *IV = cast<PHINode>(Inc->getOperand(0));
-
+
BasicBlock *BackedgeBlock =
IV->getIncomingBlock(contains(IV->getIncomingBlock(1)));
} else if (SCI->getOpcode() == Instruction::SetEQ) {
return SCI->getOperand(1);
}
-
+
return 0;
}
projects / oota-llvm.git / blobdiff