//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
-//
+//
// 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
#define LLVM_ANALYSIS_LOOP_INFO_H
#include "llvm/Pass.h"
-#include "Support/GraphTraits.h"
+#include "llvm/ADT/GraphTraits.h"
namespace llvm {
-class DominatorSet;
+class ETForest;
class LoopInfo;
class PHINode;
class Instruction;
//===----------------------------------------------------------------------===//
-/// Loop class - Instances of this class are used to represent loops that are
-/// detected in the flow graph
+/// Loop class - Instances of this class are used to represent loops that are
+/// detected in the flow graph
///
class Loop {
Loop *ParentLoop;
/// iterator/begin/end - Return the loops contained entirely within this loop.
///
+ const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
typedef std::vector<Loop*>::const_iterator iterator;
iterator begin() const { return SubLoops.begin(); }
iterator end() const { return SubLoops.end(); }
// induction variable canonicalization pass should be used to normalize loops
// for easy analysis. These methods assume canonical loops.
+ /// 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 getExitingBlocks(std::vector<BasicBlock*> &Blocks) const;
+
/// getExitBlocks - Return all of the successor blocks of this loop. These
/// are the blocks _outside of the current loop_ which are branched to.
///
void getExitBlocks(std::vector<BasicBlock*> &Blocks) 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.
+ ///
+ void getUniqueExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const;
+
/// getLoopPreheader - If there is a preheader for this loop, return it. A
/// loop has a preheader if there is only one edge to the header of the loop
/// from outside of the loop. If this is the case, the block branching to the
///
BasicBlock *getLoopPreheader() const;
+ /// 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 *getLoopLatch() const;
+
/// 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
/// this returns null.
///
Value *getTripCount() const;
+
+ /// isLCSSAForm - Return true if the Loop is in LCSSA form
+ bool isLCSSAForm() const;
//===--------------------------------------------------------------------===//
// APIs for updating loop information after changing the CFG
Blocks.push_back(BB);
}
+ /// moveToHeader - This method is used to move BB (which must be part of this
+ /// loop) to be the loop header of the loop (the block that dominates all
+ /// others).
+ void moveToHeader(BasicBlock *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;
+ }
+ }
+ }
+
/// removeBlockFromLoop - This removes the specified basic block from the
/// current loop, updating the Blocks as appropriate. This does not update
/// the mapping in the LoopInfo class.
void removeBlockFromLoop(BasicBlock *BB);
+ void print(OStream &O, unsigned Depth = 0) const {
+ if (O.stream()) print(*O.stream(), Depth);
+ }
void print(std::ostream &O, unsigned Depth = 0) const;
void dump() const;
private:
/// block is in no loop (for example the entry node), null is returned.
///
Loop *getLoopFor(const BasicBlock *BB) const {
- std::map<BasicBlock *, Loop*>::const_iterator I=BBMap.find((BasicBlock*)BB);
+ std::map<BasicBlock *, Loop*>::const_iterator I=
+ BBMap.find(const_cast<BasicBlock*>(BB));
return I != BBMap.end() ? I->second : 0;
}
// isLoopHeader - True if the block is a loop header node
bool isLoopHeader(BasicBlock *BB) const {
- return getLoopFor(BB)->getHeader() == BB;
+ const Loop *L = getLoopFor(BB);
+ return L && L->getHeader() == BB;
}
/// runOnFunction - Calculate the natural loop information.
virtual bool runOnFunction(Function &F);
virtual void releaseMemory();
- void print(std::ostream &O) const;
+ void print(OStream &O, const Module* = 0) const {
+ if (O.stream()) print(*O.stream());
+ }
+ void print(std::ostream &O, const Module* = 0) const;
- /// getAnalysisUsage - Requires dominator sets
- ///
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- /// addBlockMapping - Add the specified basic block to the mapping from blocks
- /// to loops.
- void addBlockMapping(BasicBlock *BB, Loop *L) {
- assert(!BBMap.count(BB) && "Block already in mapping!");
- assert(L != 0 && "Cannot map to null loop!");
- BBMap[BB] = L;
- }
-
/// removeLoop - This removes the specified top-level loop from this loop info
/// object. The loop is not deleted, as it will presumably be inserted into
/// another loop.
/// BasicBlocks to loops.
void removeBlock(BasicBlock *BB);
- static void stub(); // Noop
private:
- void Calculate(const DominatorSet &DS);
- Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS);
+ void Calculate(ETForest &EF);
+ Loop *ConsiderForLoop(BasicBlock *BB, ETForest &EF);
void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
void InsertLoopInto(Loop *L, Loop *Parent);
};
-// Make sure that any clients of this file link in LoopInfo.cpp
-static IncludeFile
-LOOP_INFO_INCLUDE_FILE((void*)&LoopInfo::stub);
-
// Allow clients to walk the list of nested loops...
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) {
+ static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
- static inline ChildIteratorType child_end(NodeType *N) {
+ static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
typedef std::vector<Loop*>::const_iterator ChildIteratorType;
static NodeType *getEntryNode(Loop *L) { return L; }
- static inline ChildIteratorType child_begin(NodeType *N) {
+ static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
- static inline ChildIteratorType child_end(NodeType *N) {
+ static inline ChildIteratorType child_end(NodeType *N) {
return N->end();
}
};
} // End llvm namespace
+// Make sure that any clients of this file link in LoopInfo.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo)
+
#endif
projects / oota-llvm.git / blobdiff