Interval.h revision 75517097e71f79b0a6daaa02a8c0a038436863d4
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 BasicBlock *getHeaderNode() const { return HeaderNode; } 43 44 // Nodes - The basic blocks in this interval. 45 // 46 vector<BasicBlock*> Nodes; 47 48 // Successors - List of BasicBlocks that are reachable directly from nodes in 49 // this interval, but are not in the interval themselves. 50 // These nodes neccesarily must be header nodes for other intervals. 51 // 52 vector<BasicBlock*> Successors; 53 54 // Predecessors - List of BasicBlocks that have this Interval's header block 55 // as one of their successors. 56 // 57 vector<BasicBlock*> Predecessors; 58 59 // contains - Find out if a basic block is in this interval 60 inline bool contains(BasicBlock *BB) const { 61 for (unsigned i = 0; i < Nodes.size(); ++i) 62 if (Nodes[i] == BB) return true; 63 return false; 64 // I don't want the dependency on <algorithm> 65 //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); 66 } 67 68 // isSuccessor - find out if a basic block is a successor of this Interval 69 inline bool isSuccessor(BasicBlock *BB) const { 70 for (unsigned i = 0; i < Successors.size(); ++i) 71 if (Successors[i] == BB) return true; 72 return false; 73 // I don't want the dependency on <algorithm> 74 //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); 75 } 76 77 // isLoop - Find out if there is a back edge in this interval... 78 bool isLoop() const; 79}; 80 81 82// succ_begin/succ_end - define global functions so that Intervals may be used 83// just like BasicBlocks can with the succ_* functions, and *::succ_iterator. 84// 85inline Interval::succ_iterator succ_begin(Interval *I) { 86 return I->Successors.begin(); 87} 88inline Interval::succ_iterator succ_end(Interval *I) { 89 return I->Successors.end(); 90} 91 92// pred_begin/pred_end - define global functions so that Intervals may be used 93// just like BasicBlocks can with the pred_* functions, and *::pred_iterator. 94// 95inline Interval::pred_iterator pred_begin(Interval *I) { 96 return I->Predecessors.begin(); 97} 98inline Interval::pred_iterator pred_end(Interval *I) { 99 return I->Predecessors.end(); 100} 101 102} // End namespace cfg 103 104#endif 105