include/llvm/Analysis/Interval.h

   1 //===- llvm/Analysis/Interval.h - Interval Class Declaration -----*- C++ -*--=//
   2 //
   3 // This file contains the declaration of the cfg::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 <vector>
  17
  18 class BasicBlock;
  19
  20 namespace cfg {
  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 vector<BasicBlock*>::iterator succ_iterator;
  35   typedef vector<BasicBlock*>::iterator pred_iterator;
  36   typedef vector<BasicBlock*>::iterator node_iterator;
  37
  38   inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  39     Nodes.push_back(Header);
  40   }
  41
  42   inline BasicBlock *getHeaderNode() const { return HeaderNode; }
  43
  44   // Nodes - The basic blocks in this interval.
  45   //
  46   vector<BasicBlock*> Nodes;
  47
  48   // Successors - List of BasicBlocks that are reachable directly from nodes in
  49   // this interval, but are not in the interval themselves.
  50   // These nodes neccesarily must be header nodes for other intervals.
  51   //
  52   vector<BasicBlock*> Successors;
  53
  54   // Predecessors - List of BasicBlocks that have this Interval's header block
  55   // as one of their successors.
  56   //
  57   vector<BasicBlock*> Predecessors;
  58
  59   // contains - Find out if a basic block is in this interval
  60   inline bool contains(BasicBlock *BB) const {
  61     for (unsigned i = 0; i < Nodes.size(); ++i)
  62       if (Nodes[i] == BB) return true;
  63     return false;
  64     // I don't want the dependency on <algorithm>
  65     //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
  66   }
  67
  68   // isSuccessor - find out if a basic block is a successor of this Interval
  69   inline bool isSuccessor(BasicBlock *BB) const {
  70     for (unsigned i = 0; i < Successors.size(); ++i)
  71       if (Successors[i] == BB) return true;
  72     return false;
  73     // I don't want the dependency on <algorithm>
  74     //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
  75   }
  76
  77   // isLoop - Find out if there is a back edge in this interval...
  78   bool isLoop() const;
  79 };
  80
  81
  82 // succ_begin/succ_end - define global functions so that Intervals may be used
  83 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  84 //
  85 inline Interval::succ_iterator succ_begin(Interval *I) {
  86   return I->Successors.begin();
  87 }
  88 inline Interval::succ_iterator succ_end(Interval *I) {
  89   return I->Successors.end();
  90 }
  91
  92 // pred_begin/pred_end - define global functions so that Intervals may be used
  93 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
  94 //
  95 inline Interval::pred_iterator pred_begin(Interval *I) {
  96   return I->Predecessors.begin();
  97 }
  98 inline Interval::pred_iterator pred_end(Interval *I) {
  99   return I->Predecessors.end();
 100 }
 101
 102 }    // End namespace cfg
 103
 104 #endif