//===- 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/Support/Streams.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include <algorithm>
+#include <ostream>
using namespace llvm;
-static RegisterAnalysis<LoopInfo>
+char LoopInfo::ID = 0;
+static RegisterPass<LoopInfo>
X("loops", "Natural Loop Construction", true);
//===----------------------------------------------------------------------===//
// 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 {
return NumBackEdges;
}
+/// isLoopInvariant - Return true if the specified value is loop invariant
+///
+bool Loop::isLoopInvariant(Value *V) const {
+ if (Instruction *I = dyn_cast<Instruction>(V))
+ return !contains(I->getParent());
+ return true; // All non-instructions are loop invariant
+}
+
void Loop::print(std::ostream &OS, unsigned Depth) const {
OS << std::string(Depth*2, ' ') << "Loop Containing: ";
(*I)->print(OS, Depth+2);
}
+/// verifyLoop - Verify loop structure
+void Loop::verifyLoop() const {
+#ifndef NDEBUG
+ assert (getHeader() && "Loop header is missing");
+ assert (getLoopPreheader() && "Loop preheader is missing");
+ assert (getLoopLatch() && "Loop latch is missing");
+ for (std::vector<Loop*>::const_iterator I = SubLoops.begin(), E = SubLoops.end();
+ I != E; ++I)
+ (*I)->verifyLoop();
+#endif
+}
+
void Loop::dump() const {
- print(std::cerr);
+ print(cerr);
}
//===----------------------------------------------------------------------===//
// LoopInfo implementation
//
-void LoopInfo::stub() {}
-
bool LoopInfo::runOnFunction(Function &) {
releaseMemory();
- Calculate(getAnalysis<DominatorSet>()); // Update
+ Calculate(getAnalysis<DominatorTree>()); // Update
return false;
}
TopLevelLoops.clear();
}
-
-void LoopInfo::Calculate(const DominatorSet &DS) {
- BasicBlock *RootNode = DS.getRoot();
+void LoopInfo::Calculate(DominatorTree &DT) {
+ BasicBlock *RootNode = DT.getRootNode()->getBlock();
for (df_iterator<BasicBlock*> NI = df_begin(RootNode),
- NE = df_end(RootNode); NI != NE; ++NI)
- if (Loop *L = ConsiderForLoop(*NI, DS))
+ NE = df_end(RootNode); NI != NE; ++NI)
+ if (Loop *L = ConsiderForLoop(*NI, DT))
TopLevelLoops.push_back(L);
-
- for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
- TopLevelLoops[i]->setLoopDepth(1);
}
void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<DominatorSet>();
+ AU.addRequired<DominatorTree>();
}
-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
for (std::map<BasicBlock*, Loop*>::const_iterator I = BBMap.begin(),
E = BBMap.end(); I != E; ++I)
OS << "BB '" << I->first->getName() << "' level = "
- << I->second->LoopDepth << "\n";
+ << I->second->getLoopDepth() << "\n";
#endif
}
return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
}
-Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS) {
+Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, DominatorTree &DT) {
if (BBMap.find(BB) != BBMap.end()) return 0; // Haven't processed this node?
std::vector<BasicBlock *> TodoStack;
// Scan the predecessors of BB, checking to see if BB dominates any of
// them. This identifies backedges which target this node...
for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I)
- if (DS.dominates(BB, *I)) // If BB dominates it's predecessor...
+ if (DT.dominates(BB, *I)) // If BB dominates it's predecessor...
TodoStack.push_back(*I);
if (TodoStack.empty()) return 0; // No backedges to this block...
TodoStack.pop_back();
if (!L->contains(X) && // As of yet unprocessed??
- DS.dominates(EntryBlock, X)) { // X is reachable from entry block?
+ DT.dominates(EntryBlock, X)) { // X is reachable from entry block?
// Check to see if this block already belongs to a loop. If this occurs
// then we have a case where a loop that is supposed to be a child of the
// current loop was processed before the current loop. When this occurs,
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)
- if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
+ E = L->Blocks.end(); I != E; ++I)
+ if (Loop *NewLoop = ConsiderForLoop(*I, DT)) {
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);
}
}
// APIs for simple analysis of the loop.
//
+/// getExitingBlocks - Return all blocks inside the loop that have successors
+/// outside of the loop. These are the blocks _inside of the current loop_
+/// which branch out. The returned list is always unique.
+///
+void Loop::getExitingBlocks(std::vector<BasicBlock*> &ExitingBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ std::vector<BasicBlock*> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ for (std::vector<BasicBlock*>::const_iterator BI = Blocks.begin(),
+ BE = Blocks.end(); BI != BE; ++BI)
+ for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
+ // Not in current loop? It must be an exit block.
+ ExitingBlocks.push_back(*BI);
+ break;
+ }
+}
+
/// getExitBlocks - Return all of the successor blocks of this loop. These
/// are the blocks _outside of the current loop_ which are branched to.
///
void Loop::getExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ std::vector<BasicBlock*> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
for (std::vector<BasicBlock*>::const_iterator BI = Blocks.begin(),
- BE = Blocks.end(); BI != BE; ++BI)
+ BE = Blocks.end(); BI != BE; ++BI)
for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I)
- if (!contains(*I)) // Not in current loop?
- ExitBlocks.push_back(*I); // It must be an exit block...
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // Not in current loop? It must be an exit block.
+ ExitBlocks.push_back(*I);
+}
+
+/// getUniqueExitBlocks - Return all unique successor blocks of this loop. These
+/// are the blocks _outside of the current loop_ which are branched to. This
+/// assumes that loop is in canonical form.
+//
+void Loop::getUniqueExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ std::vector<BasicBlock*> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ std::vector<BasicBlock*> switchExitBlocks;
+
+ for (std::vector<BasicBlock*>::const_iterator BI = Blocks.begin(),
+ BE = Blocks.end(); BI != BE; ++BI) {
+
+ BasicBlock *current = *BI;
+ switchExitBlocks.clear();
+
+ for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) {
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // If block is inside the loop then it is not a exit block.
+ continue;
+
+ pred_iterator PI = pred_begin(*I);
+ BasicBlock *firstPred = *PI;
+
+ // If current basic block is this exit block's first predecessor
+ // then only insert exit block in to the output ExitBlocks vector.
+ // This ensures that same exit block is not inserted twice into
+ // ExitBlocks vector.
+ if (current != firstPred)
+ continue;
+
+ // If a terminator has more then two successors, for example SwitchInst,
+ // then it is possible that there are multiple edges from current block
+ // to one exit block.
+ if (current->getTerminator()->getNumSuccessors() <= 2) {
+ ExitBlocks.push_back(*I);
+ continue;
+ }
+
+ // In case of multiple edges from current block to exit block, collect
+ // only one edge in ExitBlocks. Use switchExitBlocks to keep track of
+ // duplicate edges.
+ if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I)
+ == switchExitBlocks.end()) {
+ switchExitBlocks.push_back(*I);
+ ExitBlocks.push_back(*I);
+ }
+ }
+ }
}
return 0; // Multiple predecessors outside the loop
Out = *PI;
}
-
- // Make sure there is only one exit out of the preheader...
+
+ // Make sure there is only one exit out of the preheader.
+ assert(Out && "Header of loop has no predecessors from outside loop?");
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;
}
/// returns null.
///
Value *Loop::getTripCount() const {
- // Canonical loops will end with a 'setne I, V', where I is the incremented
+ // Canonical loops will end with a 'cmp ne I, V', where I is the incremented
// canonical induction variable and V is the trip count of the loop.
Instruction *Inc = getCanonicalInductionVariableIncrement();
if (Inc == 0) return 0;
PHINode *IV = cast<PHINode>(Inc->getOperand(0));
-
+
BasicBlock *BackedgeBlock =
IV->getIncomingBlock(contains(IV->getIncomingBlock(1)));
if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator()))
- if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition()))
- if (SCI->getOperand(0) == Inc)
- if (BI->getSuccessor(0) == getHeader()) {
- if (SCI->getOpcode() == Instruction::SetNE)
- return SCI->getOperand(1);
- } else if (SCI->getOpcode() == Instruction::SetEQ) {
- return SCI->getOperand(1);
- }
-
+ 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;
}
+/// isLCSSAForm - Return true if the Loop is in LCSSA form
+bool Loop::isLCSSAForm() const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallPtrSet<BasicBlock*, 16> LoopBBs(block_begin(), block_end());
+
+ for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) {
+ BasicBlock *BB = *BI;
+ for (BasicBlock::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) {
+ BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
+ if (PHINode *P = dyn_cast<PHINode>(*UI)) {
+ unsigned OperandNo = UI.getOperandNo();
+ UserBB = P->getIncomingBlock(OperandNo/2);
+ }
+
+ // Check the current block, as a fast-path. Most values are used in the
+ // same block they are defined in.
+ if (UserBB != BB && !LoopBBs.count(UserBB))
+ return false;
+ }
+ }
+
+ return true;
+}
//===-------------------------------------------------------------------===//
// APIs for updating loop information after changing the CFG
*I = NewChild;
OldChild->ParentLoop = 0;
NewChild->ParentLoop = this;
-
- // Update the loop depth of the new child.
- NewChild->setLoopDepth(LoopDepth+1);
}
/// addChildLoop - Add the specified loop to be a child of this loop.
assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
NewChild->ParentLoop = this;
SubLoops.push_back(NewChild);
-
- // Update the loop depth of the new child.
- NewChild->setLoopDepth(LoopDepth+1);
}
template<typename T>
void Loop::removeBlockFromLoop(BasicBlock *BB) {
RemoveFromVector(Blocks, BB);
}
+
+// Ensure this file gets linked when LoopInfo.h is used.
+DEFINING_FILE_FOR(LoopInfo)
projects / oota-llvm.git / blobdiff