Support for llvm_ostreams.
[oota-llvm.git] / include / llvm / Analysis / LoopInfo.h
index 402897c1fd9f64504aa6a248daf63c6db272c9ec..2e6d2471fcb947830333a50786bcea653fac22ec 100644 (file)
@@ -1,10 +1,10 @@
 //===- 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
 
 namespace llvm {
 
-struct 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;
@@ -74,6 +74,7 @@ public:
 
   /// 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(); }
@@ -106,11 +107,23 @@ public:
   // 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
@@ -120,6 +133,12 @@ public:
   ///
   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
@@ -139,6 +158,9 @@ public:
   /// 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
@@ -195,6 +217,9 @@ public:
   /// the mapping in the LoopInfo class.
   void removeBlockFromLoop(BasicBlock *BB);
 
+  void print(llvm_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:
@@ -229,7 +254,8 @@ public:
   /// 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;
   }
 
@@ -248,7 +274,8 @@ public:
 
   // 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.
@@ -256,10 +283,11 @@ public:
   virtual bool runOnFunction(Function &F);
 
   virtual void releaseMemory();
+  void print(llvm_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;
 
   /// removeLoop - This removes the specified top-level loop from this loop info
@@ -288,29 +316,24 @@ public:
   /// 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();
   }
 };
@@ -320,14 +343,17 @@ template <> struct GraphTraits<Loop*> {
   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