Interval.h revision 4dd88f6fbf6dc44ceba03b34aeab458536789b98
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 18class BasicBlock; 19 20namespace 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// 28class 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; 33public: 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 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 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 vector<BasicBlock*> Successors; 56 57 // Predecessors - List of BasicBlocks that have this Interval's header block 58 // as one of their successors. 59 // 60 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 93// succ_begin/succ_end - define global functions so that Intervals may be used 94// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. 95// 96inline Interval::succ_iterator succ_begin(Interval *I) { 97 return I->Successors.begin(); 98} 99inline Interval::succ_iterator succ_end(Interval *I) { 100 return I->Successors.end(); 101} 102 103// pred_begin/pred_end - define global functions so that Intervals may be used 104// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. 105// 106inline Interval::pred_iterator pred_begin(Interval *I) { 107 return I->Predecessors.begin(); 108} 109inline Interval::pred_iterator pred_end(Interval *I) { 110 return I->Predecessors.end(); 111} 112 113} // End namespace cfg 114 115#endif 116