LLVM API Documentation
00001 //===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains the declaration of the Interval class, which 00011 // represents a set of CFG nodes and is a portion of an interval partition. 00012 // 00013 // Intervals have some interesting and useful properties, including the 00014 // following: 00015 // 1. The header node of an interval dominates all of the elements of the 00016 // interval 00017 // 00018 //===----------------------------------------------------------------------===// 00019 00020 #ifndef LLVM_INTERVAL_H 00021 #define LLVM_INTERVAL_H 00022 00023 #include "llvm/ADT/GraphTraits.h" 00024 #include <vector> 00025 #include <iosfwd> 00026 00027 namespace llvm { 00028 00029 class BasicBlock; 00030 00031 //===----------------------------------------------------------------------===// 00032 // 00033 // Interval Class - An Interval is a set of nodes defined such that every node 00034 // in the interval has all of its predecessors in the interval (except for the 00035 // header) 00036 // 00037 class Interval { 00038 // HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this 00039 // interval. Also, any loops in this interval must go through the HeaderNode. 00040 // 00041 BasicBlock *HeaderNode; 00042 public: 00043 typedef std::vector<BasicBlock*>::iterator succ_iterator; 00044 typedef std::vector<BasicBlock*>::iterator pred_iterator; 00045 typedef std::vector<BasicBlock*>::iterator node_iterator; 00046 00047 inline Interval(BasicBlock *Header) : HeaderNode(Header) { 00048 Nodes.push_back(Header); 00049 } 00050 00051 inline Interval(const Interval &I) // copy ctor 00052 : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {} 00053 00054 inline BasicBlock *getHeaderNode() const { return HeaderNode; } 00055 00056 // Nodes - The basic blocks in this interval. 00057 // 00058 std::vector<BasicBlock*> Nodes; 00059 00060 // Successors - List of BasicBlocks that are reachable directly from nodes in 00061 // this interval, but are not in the interval themselves. 00062 // These nodes necessarily must be header nodes for other intervals. 00063 // 00064 std::vector<BasicBlock*> Successors; 00065 00066 // Predecessors - List of BasicBlocks that have this Interval's header block 00067 // as one of their successors. 00068 // 00069 std::vector<BasicBlock*> Predecessors; 00070 00071 // contains - Find out if a basic block is in this interval 00072 inline bool contains(BasicBlock *BB) const { 00073 for (unsigned i = 0; i < Nodes.size(); ++i) 00074 if (Nodes[i] == BB) return true; 00075 return false; 00076 // I don't want the dependency on <algorithm> 00077 //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end(); 00078 } 00079 00080 // isSuccessor - find out if a basic block is a successor of this Interval 00081 inline bool isSuccessor(BasicBlock *BB) const { 00082 for (unsigned i = 0; i < Successors.size(); ++i) 00083 if (Successors[i] == BB) return true; 00084 return false; 00085 // I don't want the dependency on <algorithm> 00086 //return find(Successors.begin(), Successors.end(), BB) != Successors.end(); 00087 } 00088 00089 // Equality operator. It is only valid to compare two intervals from the same 00090 // partition, because of this, all we have to check is the header node for 00091 // equality. 00092 // 00093 inline bool operator==(const Interval &I) const { 00094 return HeaderNode == I.HeaderNode; 00095 } 00096 00097 // isLoop - Find out if there is a back edge in this interval... 00098 bool isLoop() const; 00099 00100 // print - Show contents in human readable format... 00101 void print(std::ostream &O) const; 00102 }; 00103 00104 // succ_begin/succ_end - define methods so that Intervals may be used 00105 // just like BasicBlocks can with the succ_* functions, and *::succ_iterator. 00106 // 00107 inline Interval::succ_iterator succ_begin(Interval *I) { 00108 return I->Successors.begin(); 00109 } 00110 inline Interval::succ_iterator succ_end(Interval *I) { 00111 return I->Successors.end(); 00112 } 00113 00114 // pred_begin/pred_end - define methods so that Intervals may be used 00115 // just like BasicBlocks can with the pred_* functions, and *::pred_iterator. 00116 // 00117 inline Interval::pred_iterator pred_begin(Interval *I) { 00118 return I->Predecessors.begin(); 00119 } 00120 inline Interval::pred_iterator pred_end(Interval *I) { 00121 return I->Predecessors.end(); 00122 } 00123 00124 template <> struct GraphTraits<Interval*> { 00125 typedef Interval NodeType; 00126 typedef Interval::succ_iterator ChildIteratorType; 00127 00128 static NodeType *getEntryNode(Interval *I) { return I; } 00129 00130 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00131 static inline ChildIteratorType child_begin(NodeType *N) { 00132 return succ_begin(N); 00133 } 00134 static inline ChildIteratorType child_end(NodeType *N) { 00135 return succ_end(N); 00136 } 00137 }; 00138 00139 template <> struct GraphTraits<Inverse<Interval*> > { 00140 typedef Interval NodeType; 00141 typedef Interval::pred_iterator ChildIteratorType; 00142 static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; } 00143 static inline ChildIteratorType child_begin(NodeType *N) { 00144 return pred_begin(N); 00145 } 00146 static inline ChildIteratorType child_end(NodeType *N) { 00147 return pred_end(N); 00148 } 00149 }; 00150 00151 } // End llvm namespace 00152 00153 #endif