//===----------------------------------------------------------------------===//
//
// This file defines the LoopInfo class that is used to identify natural loops
-// and determine the loop depth of various nodes of the CFG. Note that natural
+// and determine the loop depth of various nodes of the CFG. A natural loop
+// has exactly one entry-point, which is called the header. Note that natural
// loops may actually be several loops that share the same header node.
//
// This analysis calculates the nesting structure of loops in a function. For
block_iterator block_begin() const { return Blocks.begin(); }
block_iterator block_end() const { return Blocks.end(); }
- /// isLoopExit - True if terminator in the block can branch to another block
- /// that is outside of the current loop.
+ /// isLoopExiting - True if terminator in the block can branch to another
+ /// block that is outside of the current loop.
///
- bool isLoopExit(const BlockT *BB) const {
+ bool isLoopExiting(const BlockT *BB) const {
typedef GraphTraits<BlockT*> BlockTraits;
for (typename BlockTraits::ChildIteratorType SI =
BlockTraits::child_begin(const_cast<BlockT*>(BB)),
/// getLoopLatch - If there is a single latch block for this loop, return it.
/// A latch block is a block that contains a branch back to the header.
- /// A loop header in normal form has two edges into it: one from a preheader
- /// and one from a latch block.
BlockT *getLoopLatch() const {
BlockT *Header = getHeader();
typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
InvBlockTraits::child_begin(Header);
typename InvBlockTraits::ChildIteratorType PE =
InvBlockTraits::child_end(Header);
- if (PI == PE) return 0; // no preds?
-
BlockT *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
+ for (; PI != PE; ++PI)
+ if (contains(*PI)) {
+ if (Latch) return 0;
+ Latch = *PI;
+ }
return Latch;
}
/// verifyLoop - Verify loop structure
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();
+ assert(!Blocks.empty() && "Loop header is missing");
+
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ // Check the individual blocks.
+ 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) {
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *PI))
+ HasInsideLoopPreds = true;
+ else
+ OutsideLoopPreds.push_back(*PI);
+ }
+
+ if (BB == getHeader()) {
+ assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
+ } else if (!OutsideLoopPreds.empty()) {
+ // A non-header loop shouldn't be reachable from outside the loop,
+ // though it is permitted if the predecessor is not itself actually
+ // reachable.
+ 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!");
+ }
+
+ // Check the subloops.
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ // Each block in each subloop should be contained within this loop.
+ 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!");
+ }
+
+ // Check the parent loop pointer.
+ if (ParentLoop) {
+ assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
+ ParentLoop->end() &&
+ "Loop is not a subloop of its parent!");
+ }
#endif
}
+ /// verifyLoop - Verify loop structure of this loop and all nested loops.
+ void verifyLoopNest() const {
+ // Verify this loop.
+ verifyLoop();
+ // Verify the subloops.
+ 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: ";
WriteAsOperand(OS, BB, false);
if (BB == getHeader()) OS << "<header>";
if (BB == getLoopLatch()) OS << "<latch>";
- if (isLoopExit(BB)) OS << "<exit>";
+ if (isLoopExiting(BB)) OS << "<exiting>";
}
OS << "\n";
/// normal form.
bool isLoopSimplifyForm() const;
+ /// hasDedicatedExits - Return true if no exit block for the loop
+ /// has a predecessor that is outside the loop.
+ bool hasDedicatedExits() const;
+
/// 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.
+ /// This assumes that loop exits are in canonical form.
///
void getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const;
for (typename InvBlockTraits::ChildIteratorType I =
InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
I != E; ++I)
- if (DT.dominates(BB, *I)) // If BB dominates it's predecessor...
+ if (DT.dominates(BB, *I)) // If BB dominates its predecessor...
TodoStack.push_back(*I);
if (TodoStack.empty()) return 0; // No backedges to this block...
if (LoopT *SubLoop =
const_cast<LoopT *>(getLoopFor(X)))
if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
- // Remove the subloop from it's current parent...
+ // Remove the subloop from its current parent...
assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent
typename std::vector<LoopT *>::iterator I =
///
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;
void removeBlock(BasicBlock *BB) {
LI.removeBlock(BB);
}
-
- static bool isNotAlreadyContainedIn(const Loop *SubLoop,
- const Loop *ParentLoop) {
- return
- LoopInfoBase<BasicBlock, Loop>::isNotAlreadyContainedIn(SubLoop,
- ParentLoop);
- }
};
projects / oota-llvm.git / blobdiff