Interval.h revision 45cfe545ec8177262dabc70580ce05feaa1c3880
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_INTERVAL_H 21#define LLVM_INTERVAL_H 22 23#include "llvm/ADT/GraphTraits.h" 24#include <vector> 25 26namespace llvm { 27 28class BasicBlock; 29class 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/// 37class 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; 42public: 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 Interval(const Interval &I) // copy ctor 52 : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {} 53 54 inline BasicBlock *getHeaderNode() const { return HeaderNode; } 55 56 /// Nodes - The basic blocks in this interval. 57 /// 58 std::vector<BasicBlock*> Nodes; 59 60 /// Successors - List of BasicBlocks that are reachable directly from nodes in 61 /// this interval, but are not in the interval themselves. 62 /// These nodes necessarily must be header nodes for other intervals. 63 /// 64 std::vector<BasicBlock*> Successors; 65 66 /// Predecessors - List of BasicBlocks that have this Interval's header block 67 /// as one of their successors. 68 /// 69 std::vector<BasicBlock*> Predecessors; 70 71 /// contains - Find out if a basic block is in this interval 72 inline bool contains(BasicBlock *BB) const { 73 for (unsigned i = 0; i < Nodes.size(); ++i) 74 if (Nodes[i] == BB) return true; 75 return false; 76 // I don't want the dependency on <algorithm> 77 //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); 78 } 79 80 /// isSuccessor - find out if a basic block is a successor of this Interval 81 inline bool isSuccessor(BasicBlock *BB) const { 82 for (unsigned i = 0; i < Successors.size(); ++i) 83 if (Successors[i] == BB) return true; 84 return false; 85 // I don't want the dependency on <algorithm> 86 //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); 87 } 88 89 /// Equality operator. It is only valid to compare two intervals from the 90 /// same partition, because of this, all we have to check is the header node 91 /// for equality. 92 /// 93 inline bool operator==(const Interval &I) const { 94 return HeaderNode == I.HeaderNode; 95 } 96 97 /// isLoop - Find out if there is a back edge in this interval... 98 bool isLoop() const; 99 100 /// print - Show contents in human readable format... 101 void print(raw_ostream &O) const; 102}; 103 104/// succ_begin/succ_end - define methods so that Intervals may be used 105/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. 106/// 107inline Interval::succ_iterator succ_begin(Interval *I) { 108 return I->Successors.begin(); 109} 110inline Interval::succ_iterator succ_end(Interval *I) { 111 return I->Successors.end(); 112} 113 114/// pred_begin/pred_end - define methods so that Intervals may be used 115/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. 116/// 117inline Interval::pred_iterator pred_begin(Interval *I) { 118 return I->Predecessors.begin(); 119} 120inline Interval::pred_iterator pred_end(Interval *I) { 121 return I->Predecessors.end(); 122} 123 124template <> struct GraphTraits<Interval*> { 125 typedef Interval NodeType; 126 typedef Interval::succ_iterator ChildIteratorType; 127 128 static NodeType *getEntryNode(Interval *I) { return I; } 129 130 /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph 131 static inline ChildIteratorType child_begin(NodeType *N) { 132 return succ_begin(N); 133 } 134 static inline ChildIteratorType child_end(NodeType *N) { 135 return succ_end(N); 136 } 137}; 138 139template <> struct GraphTraits<Inverse<Interval*> > { 140 typedef Interval NodeType; 141 typedef Interval::pred_iterator ChildIteratorType; 142 static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; } 143 static inline ChildIteratorType child_begin(NodeType *N) { 144 return pred_begin(N); 145 } 146 static inline ChildIteratorType child_end(NodeType *N) { 147 return pred_end(N); 148 } 149}; 150 151} // End llvm namespace 152 153#endif 154