include/llvm/Analysis/Interval.h

   1 //===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===//
   2 //
   3 // This file contains the declaration of the Interval class, which
   4 // represents a set of CFG nodes and is a portion of an interval partition.
   5 //
   6 // Intervals have some interesting and useful properties, including the
   7 // following:
   8 //    1. The header node of an interval dominates all of the elements of the
   9 //       interval
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_INTERVAL_H
  14 #define LLVM_INTERVAL_H
  15
  16 #include "Support/GraphTraits.h"
  17 #include <vector>
  18 #include <iosfwd>
  19
  20 class BasicBlock;
  21
  22 //===----------------------------------------------------------------------===//
  23 //
  24 // Interval Class - An Interval is a set of nodes defined such that every node
  25 // in the interval has all of its predecessors in the interval (except for the
  26 // header)
  27 //
  28 class Interval {
  29   // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
  30   // interval.  Also, any loops in this interval must go through the HeaderNode.
  31   //
  32   BasicBlock *HeaderNode;
  33 public:
  34   typedef std::vector<BasicBlock*>::iterator succ_iterator;
  35   typedef std::vector<BasicBlock*>::iterator pred_iterator;
  36   typedef std::vector<BasicBlock*>::iterator node_iterator;
  37
  38   inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  39     Nodes.push_back(Header);
  40   }
  41
  42   inline Interval(const Interval &I) // copy ctor
  43     : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {}
  44
  45   inline BasicBlock *getHeaderNode() const { return HeaderNode; }
  46
  47   // Nodes - The basic blocks in this interval.
  48   //
  49   std::vector<BasicBlock*> Nodes;
  50
  51   // Successors - List of BasicBlocks that are reachable directly from nodes in
  52   // this interval, but are not in the interval themselves.
  53   // These nodes necessarily must be header nodes for other intervals.
  54   //
  55   std::vector<BasicBlock*> Successors;
  56
  57   // Predecessors - List of BasicBlocks that have this Interval's header block
  58   // as one of their successors.
  59   //
  60   std::vector<BasicBlock*> Predecessors;
  61
  62   // contains - Find out if a basic block is in this interval
  63   inline bool contains(BasicBlock *BB) const {
  64     for (unsigned i = 0; i < Nodes.size(); ++i)
  65       if (Nodes[i] == BB) return true;
  66     return false;
  67     // I don't want the dependency on <algorithm>
  68     //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
  69   }
  70
  71   // isSuccessor - find out if a basic block is a successor of this Interval
  72   inline bool isSuccessor(BasicBlock *BB) const {
  73     for (unsigned i = 0; i < Successors.size(); ++i)
  74       if (Successors[i] == BB) return true;
  75     return false;
  76     // I don't want the dependency on <algorithm>
  77     //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
  78   }
  79
  80   // Equality operator.  It is only valid to compare two intervals from the same
  81   // partition, because of this, all we have to check is the header node for
  82   // equality.
  83   //
  84   inline bool operator==(const Interval &I) const {
  85     return HeaderNode == I.HeaderNode;
  86   }
  87
  88   // isLoop - Find out if there is a back edge in this interval...
  89   bool isLoop() const;
  90
  91   // print - Show contents in human readable format...
  92   void print(std::ostream &O) const;
  93 };
  94
  95 // succ_begin/succ_end - define methods so that Intervals may be used
  96 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  97 //
  98 inline Interval::succ_iterator succ_begin(Interval *I) {
  99   return I->Successors.begin();
 100 }
 101 inline Interval::succ_iterator succ_end(Interval *I)   {
 102   return I->Successors.end();
 103 }
 104
 105 // pred_begin/pred_end - define methods so that Intervals may be used
 106 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
 107 //
 108 inline Interval::pred_iterator pred_begin(Interval *I) {
 109   return I->Predecessors.begin();
 110 }
 111 inline Interval::pred_iterator pred_end(Interval *I)   {
 112   return I->Predecessors.end();
 113 }
 114
 115 template <> struct GraphTraits<Interval*> {
 116   typedef Interval NodeType;
 117   typedef Interval::succ_iterator ChildIteratorType;
 118
 119   static NodeType *getEntryNode(Interval *I) { return I; }
 120
 121   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 122   static inline ChildIteratorType child_begin(NodeType *N) {
 123     return succ_begin(N);
 124   }
 125   static inline ChildIteratorType child_end(NodeType *N) {
 126     return succ_end(N);
 127   }
 128 };
 129
 130 template <> struct GraphTraits<Inverse<Interval*> > {
 131   typedef Interval NodeType;
 132   typedef Interval::pred_iterator ChildIteratorType;
 133   static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; }
 134   static inline ChildIteratorType child_begin(NodeType *N) {
 135     return pred_begin(N);
 136   }
 137   static inline ChildIteratorType child_end(NodeType *N) {
 138     return pred_end(N);
 139   }
 140 };
 141
 142 #endif