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