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 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 neccesarily 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
  92   // succ_begin/succ_end - define methods so that Intervals may be used
  93   // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  94   //
  95   inline succ_iterator succ_begin() { return Successors.begin(); }
  96   inline succ_iterator succ_end()   { return Successors.end(); }
  97
  98   // pred_begin/pred_end - define methods so that Intervals may be used
  99   // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
 100   //
 101   inline Interval::pred_iterator pred_begin() { return Predecessors.begin(); }
 102   inline Interval::pred_iterator pred_end()   { return Predecessors.end(); }
 103 };
 104
 105 }    // End namespace cfg
 106
 107 #endif