1 files changed, 107 insertions, 0 deletions
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
new file mode 100644
index 0000000000..3a20226520
--- /dev/null
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -0,0 +1,107 @@
+//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator --------*- C++ -*--=//
+//
+// 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 the
+// loops identified may actually be several natural loops that share the same
+// header node... not just a single natural loop.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_INFO_H
+#define LLVM_ANALYSIS_LOOP_INFO_H
+
+#include <vector>
+#include <map>
+#include <set>
+class BasicBlock;
+
+namespace cfg {
+  class DominatorSet;
+  class LoopInfo;
+
+//===----------------------------------------------------------------------===//
+// Loop class - Instances of this class are used to represent loops that are 
+// detected in the flow graph 
+//
+class Loop {
+  Loop *ParentLoop;
+  vector<const BasicBlock *> Blocks; // First entry is the header node
+  vector<Loop*> SubLoops;            // Loops contained entirely within this one
+  unsigned LoopDepth;                // Nesting depth of this loop
+
+  Loop(const Loop &);                  // DO NOT IMPLEMENT
+  const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
+public:
+
+  inline unsigned getLoopDepth() const { return LoopDepth; }
+  inline const BasicBlock *getHeader() const { return Blocks.front(); }
+
+  // contains - Return true of the specified basic block is in this loop
+  bool contains(const BasicBlock *BB) const;
+
+  // getSubLoops - Return the loops contained entirely within this loop
+  inline const vector<Loop*> &getSubLoops() const { return SubLoops; }
+  inline const vector<const BasicBlock*> &getBlocks() const { return Blocks; }
+
+private:
+  friend class LoopInfo;
+  inline Loop(const BasicBlock *BB) { Blocks.push_back(BB); LoopDepth = 0; }
+  
+  void setLoopDepth(unsigned Level) {
+    LoopDepth = Level;
+    for (unsigned i = 0; i < SubLoops.size(); ++i)
+      SubLoops[i]->setLoopDepth(Level+1);
+  }
+};
+
+
+
+//===----------------------------------------------------------------------===//
+// LoopInfo - This class builds and contains all of the top level loop
+// structures in the specified method.
+//
+class LoopInfo {
+  // BBMap - Mapping of basic blocks to the inner most loop they occur in
+  map<const BasicBlock *, Loop*> BBMap;
+  vector<Loop*> TopLevelLoops;
+public:
+  // LoopInfo ctor - Calculate the natural loop information for a CFG
+  LoopInfo(const DominatorSet &DS);
+
+  const vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; }
+
+  // getLoopFor - Return the inner most loop that BB lives in.  If a basic block
+  // is in no loop (for example the entry node), null is returned.
+  //
+  const Loop *getLoopFor(const BasicBlock *BB) const {
+    map<const BasicBlock *, Loop*>::const_iterator I = BBMap.find(BB);
+    return I != BBMap.end() ? I->second : 0;
+  }
+  inline const Loop *operator[](const BasicBlock *BB) const {
+    return getLoopFor(BB);
+  }
+
+  // getLoopDepth - Return the loop nesting level of the specified block...
+  unsigned getLoopDepth(const BasicBlock *BB) const {
+    const Loop *L = getLoopFor(BB);
+    return L ? L->getLoopDepth() : 0;
+  }
+
+#if 0
+  // isLoopHeader - True if the block is a loop header node
+  bool isLoopHeader(const BasicBlock *BB) const {
+    return getLoopFor(BB)->getHeader() == BB;
+  }
+  // isLoopEnd - True if block jumps to loop entry
+  bool isLoopEnd(const BasicBlock *BB) const;
+  // isLoopExit - True if block is the loop exit
+  bool isLoopExit(const BasicBlock *BB) const;
+#endif
+
+private:
+  Loop *ConsiderForLoop(const BasicBlock *BB, const DominatorSet &DS);
+};
+
+}  // End namespace cfg
+
+#endif