LLVM API Documentation
00001 //===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- 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 // A common graph class that is based on the SSA graph. It includes 00011 // extra dependencies that are caused by machine resources. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H 00016 #define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H 00017 00018 #include "llvm/Value.h" 00019 #include "llvm/ADT/iterator" 00020 #include <vector> 00021 00022 namespace llvm { 00023 00024 class SchedGraphEdge; 00025 class SchedGraphNode; 00026 00027 /******************** Exported Data Types and Constants ********************/ 00028 00029 typedef int ResourceId; 00030 const ResourceId InvalidRID = -1; 00031 const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs 00032 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs 00033 const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs 00034 00035 00036 //*********************** Public Class Declarations ************************/ 00037 class SchedGraphNodeCommon { 00038 protected: 00039 unsigned ID; 00040 std::vector<SchedGraphEdge*> inEdges; 00041 std::vector<SchedGraphEdge*> outEdges; 00042 int latency; 00043 int origIndexInBB; // original position of instr in BB 00044 00045 public: 00046 typedef std::vector<SchedGraphEdge*>::iterator iterator; 00047 typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator; 00048 typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator; 00049 typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator; 00050 00051 // Accessor methods 00052 unsigned getNodeId() const { return ID; } 00053 int getLatency() const { return latency; } 00054 unsigned getNumInEdges() const { return inEdges.size(); } 00055 unsigned getNumOutEdges() const { return outEdges.size(); } 00056 int getOrigIndexInBB() const { return origIndexInBB; } 00057 00058 // Iterators 00059 iterator beginInEdges() { return inEdges.begin(); } 00060 iterator endInEdges() { return inEdges.end(); } 00061 iterator beginOutEdges() { return outEdges.begin(); } 00062 iterator endOutEdges() { return outEdges.end(); } 00063 00064 const_iterator beginInEdges() const { return inEdges.begin(); } 00065 const_iterator endInEdges() const { return inEdges.end(); } 00066 const_iterator beginOutEdges() const { return outEdges.begin(); } 00067 const_iterator endOutEdges() const { return outEdges.end(); } 00068 00069 void dump(int indent=0) const; 00070 00071 // Debugging support 00072 virtual void print(std::ostream &os) const = 0; 00073 00074 protected: 00075 friend class SchedGraphCommon; 00076 friend class SchedGraphEdge; // give access for adding edges 00077 00078 00079 // disable default constructor and provide a ctor for single-block graphs 00080 SchedGraphNodeCommon(); // DO NOT IMPLEMENT 00081 00082 inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {} 00083 00084 virtual ~SchedGraphNodeCommon(); 00085 00086 //Functions to add and remove edges 00087 inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); } 00088 inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); } 00089 void removeInEdge(const SchedGraphEdge* edge); 00090 void removeOutEdge(const SchedGraphEdge* edge); 00091 00092 }; 00093 00094 // ostream << operator for SchedGraphNode class 00095 inline std::ostream &operator<<(std::ostream &os, 00096 const SchedGraphNodeCommon &node) { 00097 node.print(os); 00098 return os; 00099 } 00100 00101 00102 00103 00104 // 00105 // SchedGraphEdge - Edge class to represent dependencies 00106 // 00107 class SchedGraphEdge { 00108 public: 00109 enum SchedGraphEdgeDepType { 00110 CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource 00111 }; 00112 enum DataDepOrderType { 00113 TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8 00114 }; 00115 00116 protected: 00117 SchedGraphNodeCommon* src; 00118 SchedGraphNodeCommon* sink; 00119 SchedGraphEdgeDepType depType; 00120 unsigned int depOrderType; 00121 int minDelay; // cached latency (assumes fixed target arch) 00122 int iteDiff; 00123 00124 union { 00125 const Value* val; 00126 int machineRegNum; 00127 ResourceId resourceId; 00128 }; 00129 00130 public: 00131 // For all constructors, if minDelay is unspecified, minDelay is 00132 // set to _src->getLatency(). 00133 00134 // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument 00135 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink, 00136 SchedGraphEdgeDepType _depType, unsigned int _depOrderType, 00137 int _minDelay = -1); 00138 00139 // constructor for explicit value dependence (may be true/anti/output) 00140 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink, 00141 const Value* _val, unsigned int _depOrderType, 00142 int _minDelay = -1); 00143 00144 // constructor for machine register dependence 00145 SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink, 00146 unsigned int _regNum, unsigned int _depOrderType, 00147 int _minDelay = -1); 00148 00149 // constructor for any other machine resource dependences. 00150 // DataDepOrderType is always NonDataDep. It it not an argument to 00151 // avoid overloading ambiguity with previous constructor. 00152 SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink, 00153 ResourceId _resourceId, int _minDelay = -1); 00154 00155 ~SchedGraphEdge() {} 00156 00157 SchedGraphNodeCommon* getSrc() const { return src; } 00158 SchedGraphNodeCommon* getSink() const { return sink; } 00159 int getMinDelay() const { return minDelay; } 00160 SchedGraphEdgeDepType getDepType() const { return depType; } 00161 unsigned int getDepOrderType() const { return depOrderType; } 00162 00163 const Value* getValue() const { 00164 assert(depType == ValueDep); return val; 00165 } 00166 00167 int getMachineReg() const { 00168 assert(depType == MachineRegister); return machineRegNum; 00169 } 00170 00171 int getResourceId() const { 00172 assert(depType == MachineResource); return resourceId; 00173 } 00174 00175 void setIteDiff(int _iteDiff) { 00176 iteDiff = _iteDiff; 00177 } 00178 00179 int getIteDiff() { 00180 return iteDiff; 00181 } 00182 00183 public: 00184 // Debugging support 00185 void print(std::ostream &os) const; 00186 void dump(int indent=0) const; 00187 00188 private: 00189 // disable default ctor 00190 SchedGraphEdge(); // DO NOT IMPLEMENT 00191 }; 00192 00193 // ostream << operator for SchedGraphNode class 00194 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) { 00195 edge.print(os); 00196 return os; 00197 } 00198 00199 class SchedGraphCommon { 00200 00201 protected: 00202 SchedGraphNodeCommon* graphRoot; // the root and leaf are not inserted 00203 SchedGraphNodeCommon* graphLeaf; // in the hash_map (see getNumNodes()) 00204 00205 public: 00206 // 00207 // Accessor methods 00208 // 00209 SchedGraphNodeCommon* getRoot() const { return graphRoot; } 00210 SchedGraphNodeCommon* getLeaf() const { return graphLeaf; } 00211 00212 // 00213 // Delete nodes or edges from the graph. 00214 // 00215 void eraseNode(SchedGraphNodeCommon* node); 00216 void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true); 00217 void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true); 00218 void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true); 00219 00220 SchedGraphCommon() {} 00221 ~SchedGraphCommon(); 00222 }; 00223 00224 00225 //********************** Sched Graph Iterators *****************************/ 00226 00227 // Ok to make it a template because it shd get instantiated at most twice: 00228 // for <SchedGraphNode, SchedGraphNode::iterator> and 00229 // for <const SchedGraphNode, SchedGraphNode::const_iterator>. 00230 // 00231 template <class _NodeType, class _EdgeType, class _EdgeIter> 00232 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> { 00233 protected: 00234 _EdgeIter oi; 00235 public: 00236 typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self; 00237 00238 inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {} 00239 00240 inline bool operator==(const _Self& x) const { return oi == x.oi; } 00241 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00242 00243 // operator*() differs for pred or succ iterator 00244 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); } 00245 inline _NodeType* operator->() const { return operator*(); } 00246 00247 inline _EdgeType* getEdge() const { return *(oi); } 00248 00249 inline _Self &operator++() { ++oi; return *this; } // Preincrement 00250 inline _Self operator++(int) { // Postincrement 00251 _Self tmp(*this); ++*this; return tmp; 00252 } 00253 00254 inline _Self &operator--() { --oi; return *this; } // Predecrement 00255 inline _Self operator--(int) { // Postdecrement 00256 _Self tmp = *this; --*this; return tmp; 00257 } 00258 }; 00259 00260 template <class _NodeType, class _EdgeType, class _EdgeIter> 00261 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> { 00262 protected: 00263 _EdgeIter oi; 00264 public: 00265 typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self; 00266 00267 inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {} 00268 00269 inline bool operator==(const _Self& x) const { return oi == x.oi; } 00270 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00271 00272 inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); } 00273 inline _NodeType* operator->() const { return operator*(); } 00274 00275 inline _EdgeType* getEdge() const { return *(oi); } 00276 00277 inline _Self &operator++() { ++oi; return *this; } // Preincrement 00278 inline _Self operator++(int) { // Postincrement 00279 _Self tmp(*this); ++*this; return tmp; 00280 } 00281 00282 inline _Self &operator--() { --oi; return *this; } // Predecrement 00283 inline _Self operator--(int) { // Postdecrement 00284 _Self tmp = *this; --*this; return tmp; 00285 } 00286 }; 00287 } // End llvm namespace 00288 00289 #endif