//===----------------------------------------------------------------------===//
//
// 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
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
BlockT *getHeader() const { return Blocks.front(); }
LoopT *getParentLoop() const { return ParentLoop; }
- /// contains - Return true if the specified basic block is in this loop
+ /// contains - Return true if the specified loop is contained within in
+ /// this loop.
+ ///
+ bool contains(const LoopT *L) const {
+ if (L == this) return true;
+ if (L == 0) return false;
+ return contains(L->getParentLoop());
+ }
+
+ /// contains - Return true if the specified basic block is in this loop.
///
bool contains(const BlockT *BB) const {
return std::find(block_begin(), block_end(), BB) != block_end();
}
+ /// contains - Return true if the specified instruction is in this loop.
+ ///
+ template<class InstT>
+ bool contains(const InstT *Inst) const {
+ return contains(Inst->getParent());
+ }
+
/// iterator/begin/end - Return the loops contained entirely within this loop.
///
const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
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;
}
void verifyLoop() const {
#ifndef NDEBUG
assert(!Blocks.empty() && "Loop header is missing");
- assert(getHeader() && "Loop header is missing");
// Sort the blocks vector so that we can use binary search to do quick
// lookups.
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";
}
void dump() const {
- print(errs());
+ print(dbgs());
}
protected:
/// 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;
void removeBlock(BasicBlock *BB) {
LI.removeBlock(BB);
}
-
- static bool isNotAlreadyContainedIn(const Loop *SubLoop,
- const Loop *ParentLoop) {
- return
- LoopInfoBase<BasicBlock, Loop>::isNotAlreadyContainedIn(SubLoop,
- ParentLoop);
- }
};