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 <vector>
  17
  18 class BasicBlock;
  19
  20 //===----------------------------------------------------------------------===//
  21 //
  22 // Interval Class - An Interval is a set of nodes defined such that every node
  23 // in the interval has all of its predecessors in the interval (except for the
  24 // header)
  25 //
  26 class Interval {
  27   // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
  28   // interval.  Also, any loops in this interval must go through the HeaderNode.
  29   //
  30   BasicBlock *HeaderNode;
  31 public:
  32   typedef std::vector<BasicBlock*>::iterator succ_iterator;
  33   typedef std::vector<BasicBlock*>::iterator pred_iterator;
  34   typedef std::vector<BasicBlock*>::iterator node_iterator;
  35
  36   inline Interval(BasicBlock *Header) : HeaderNode(Header) {
  37     Nodes.push_back(Header);
  38   }
  39
  40   inline Interval(const Interval &I) // copy ctor
  41     : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {}
  42
  43   inline BasicBlock *getHeaderNode() const { return HeaderNode; }
  44
  45   // Nodes - The basic blocks in this interval.
  46   //
  47   std::vector<BasicBlock*> Nodes;
  48
  49   // Successors - List of BasicBlocks that are reachable directly from nodes in
  50   // this interval, but are not in the interval themselves.
  51   // These nodes neccesarily must be header nodes for other intervals.
  52   //
  53   std::vector<BasicBlock*> Successors;
  54
  55   // Predecessors - List of BasicBlocks that have this Interval's header block
  56   // as one of their successors.
  57   //
  58   std::vector<BasicBlock*> Predecessors;
  59
  60   // contains - Find out if a basic block is in this interval
  61   inline bool contains(BasicBlock *BB) const {
  62     for (unsigned i = 0; i < Nodes.size(); ++i)
  63       if (Nodes[i] == BB) return true;
  64     return false;
  65     // I don't want the dependency on <algorithm>
  66     //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
  67   }
  68
  69   // isSuccessor - find out if a basic block is a successor of this Interval
  70   inline bool isSuccessor(BasicBlock *BB) const {
  71     for (unsigned i = 0; i < Successors.size(); ++i)
  72       if (Successors[i] == BB) return true;
  73     return false;
  74     // I don't want the dependency on <algorithm>
  75     //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
  76   }
  77
  78   // Equality operator.  It is only valid to compare two intervals from the same
  79   // partition, because of this, all we have to check is the header node for
  80   // equality.
  81   //
  82   inline bool operator==(const Interval &I) const {
  83     return HeaderNode == I.HeaderNode;
  84   }
  85
  86   // isLoop - Find out if there is a back edge in this interval...
  87   bool isLoop() const;
  88 };
  89
  90 // succ_begin/succ_end - define methods so that Intervals may be used
  91 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
  92 //
  93 inline Interval::succ_iterator succ_begin(Interval *I) {
  94   return I->Successors.begin();
  95 }
  96 inline Interval::succ_iterator succ_end(Interval *I)   {
  97   return I->Successors.end();
  98 }
  99
 100 // pred_begin/pred_end - define methods so that Intervals may be used
 101 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
 102 //
 103 inline Interval::pred_iterator pred_begin(Interval *I) {
 104   return I->Predecessors.begin();
 105 }
 106 inline Interval::pred_iterator pred_end(Interval *I)   {
 107   return I->Predecessors.end();
 108 }
 109
 110 #endif