Add capability to build a derived interval graph

[oota-llvm.git] / include / llvm / Analysis / Interval.h

diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h
index a17e655c9e4853652bacdd2d47f85216988367df..3c22f6dc7caf5daa29b3a72b55579b772687f770 100644 (file)
--- a/include/llvm/Analysis/Interval.h
+++ b/include/llvm/Analysis/Interval.h
@@ -1,7 +1,11 @@
 //===- llvm/Analysis/Intervals.h - Interval partition Calculation-*- C++ -*--=//
 //
 // This file contains the declaration of the cfg::IntervalPartition class, which
-// calculates and represent the interval partition of a method.
+// calculates and represents the interval partition of a method, or a
+// preexisting interval partition.
+//
+// In this way, the interval partition may be used to reduce a flow graph down
+// to its degenerate single node interval partition (unless it is irreducible).
 //
 //===----------------------------------------------------------------------===//
 
@@ -64,6 +68,28 @@ private:           // Only accessable by IntervalPartition class
 };
 
 
+// succ_begin/succ_end - define global functions so that Intervals may be used
+// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
+//
+inline Interval::succ_iterator succ_begin(Interval *I) { 
+  return I->Successors.begin();
+}
+inline Interval::succ_iterator succ_end(Interval *I) { 
+  return I->Successors.end();
+}
+
+// pred_begin/pred_end - define global functions so that Intervals may be used
+// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
+//
+inline Interval::pred_iterator pred_begin(Interval *I) { 
+  return I->Predecessors.begin();
+}
+inline Interval::pred_iterator pred_end(Interval *I) { 
+  return I->Predecessors.end();
+}
+
+
+
 // IntervalPartition - This class builds and holds an "interval partition" for
 // a method.  This partition divides the control flow graph into a set of
 // maximal intervals, as defined with the properties above.  Intuitively, a
@@ -85,6 +111,12 @@ public:
   // IntervalPartition ctor - Build the partition for the specified method
   IntervalPartition(Method *M);
 
+  // IntervalPartition ctor - Build a reduced interval partition from an
+  // existing interval graph.  This takes an additional boolean parameter to
+  // distinguish it from a copy constructor.  Always pass in false for now.
+  //
+  IntervalPartition(IntervalPartition &I, bool);
+
   // getRootInterval() - Return the root interval that contains the starting
   // block of the method
   inline Interval *getRootInterval() { return RootInterval; }
@@ -102,9 +134,45 @@ public:
   inline iterator end()   { return IntervalList.end(); }
 
 private:
-  void ProcessInterval(BasicBlock *Header);
-  void ProcessBasicBlock(Interval *I, BasicBlock *BB);
-  void UpdateSuccessors(Interval *Int);
+  // ProcessInterval - This method is used during the construction of the 
+  // interval graph.  It walks through the source graph, recursively creating
+  // an interval per invokation until the entire graph is covered.  This uses
+  // the ProcessNode method to add all of the nodes to the interval.
+  //
+  // This method is templated because it may operate on two different source
+  // graphs: a basic block graph, or a preexisting interval graph.
+  //
+  template<class NodeTy, class OrigContainer>
+  void ProcessInterval(NodeTy *Node, OrigContainer *OC);
+
+  // ProcessNode - This method is called by ProcessInterval to add nodes to the
+  // interval being constructed, and it is also called recursively as it walks
+  // the source graph.  A node is added to the current interval only if all of
+  // its predecessors are already in the graph.  This also takes care of keeping
+  // the successor set of an interval up to date.
+  //
+  // This method is templated because it may operate on two different source
+  // graphs: a basic block graph, or a preexisting interval graph.
+  //
+  template<class NodeTy, class OrigContainer>
+  void ProcessNode(Interval *Int, NodeTy *Node, OrigContainer *OC);
+
+  // addNodeToInterval - This method exists to assist the generic ProcessNode
+  // with the task of adding a node to the new interval, depending on the 
+  // type of the source node.  In the case of a CFG source graph (BasicBlock 
+  // case), the BasicBlock itself is added to the interval.  In the case of
+  // an IntervalPartition source graph (Interval case), all of the member
+  // BasicBlocks are added to the interval.
+  //
+  inline void addNodeToInterval(Interval *Int, Interval *I);
+  inline void addNodeToInterval(Interval *Int, BasicBlock *BB);
+
+  // updatePredecessors - Interval generation only sets the successor fields of
+  // the interval data structures.  After interval generation is complete,
+  // run through all of the intervals and propogate successor info as
+  // predecessor info.
+  //
+  void updatePredecessors(Interval *Int);
 };
 
 }    // End namespace cfg