LLVM API Documentation
00001 //===- DependenceGraph.h - Dependence graph for a function ------*- 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 provides an explicit representation for the dependence graph 00011 // of a function, with one node per instruction and one edge per dependence. 00012 // Dependences include both data and control dependences. 00013 // 00014 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and 00015 // outgoing dependence edges. 00016 // 00017 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point 00018 // of the dependence. This saves space and is important because dep. graphs 00019 // can grow quickly. It works just fine because the standard idiom is to 00020 // start with a known node and enumerate the dependences to or from that node. 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H 00025 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H 00026 00027 #include "llvm/ADT/hash_map" 00028 #include <cassert> 00029 #include <iosfwd> 00030 #include <utility> 00031 #include <vector> 00032 00033 namespace llvm { 00034 00035 class Instruction; 00036 class Function; 00037 class Dependence; 00038 class DepGraphNode; 00039 class DependenceGraph; 00040 00041 //---------------------------------------------------------------------------- 00042 /// enum DependenceType - The standard data dependence types 00043 /// 00044 enum DependenceType { 00045 NoDependence = 0x0, 00046 TrueDependence = 0x1, 00047 AntiDependence = 0x2, 00048 OutputDependence = 0x4, 00049 ControlDependence = 0x8, // from a terminator to some other instr. 00050 IncomingFlag = 0x10 // is this an incoming or outgoing dep? 00051 }; 00052 00053 //---------------------------------------------------------------------------- 00054 /// Dependence Class - A representation of a simple (non-loop-related) 00055 /// dependence. 00056 /// 00057 class Dependence { 00058 DepGraphNode* toOrFromNode; 00059 unsigned char depType; 00060 00061 public: 00062 Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming) 00063 : toOrFromNode(toOrFromN), 00064 depType(type | (isIncoming? IncomingFlag : 0x0)) { } 00065 00066 Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode), 00067 depType(D.depType) { } 00068 00069 bool operator==(const Dependence& D) const { 00070 return toOrFromNode == D.toOrFromNode && depType == D.depType; 00071 } 00072 00073 /// Get information about the type of dependence. 00074 /// 00075 unsigned getDepType() const { 00076 return depType; 00077 } 00078 00079 /// Get source or sink depending on what type of node this is! 00080 /// 00081 DepGraphNode* getSrc() { 00082 assert(depType & IncomingFlag); return toOrFromNode; 00083 } 00084 const DepGraphNode* getSrc() const { 00085 assert(depType & IncomingFlag); return toOrFromNode; 00086 } 00087 00088 DepGraphNode* getSink() { 00089 assert(! (depType & IncomingFlag)); return toOrFromNode; 00090 } 00091 const DepGraphNode* getSink() const { 00092 assert(! (depType & IncomingFlag)); return toOrFromNode; 00093 } 00094 00095 /// Debugging support methods 00096 /// 00097 void print(std::ostream &O) const; 00098 00099 // Default constructor: Do not use directly except for graph builder code 00100 // 00101 Dependence() : toOrFromNode(NULL), depType(NoDependence) { } 00102 }; 00103 00104 #ifdef SUPPORTING_LOOP_DEPENDENCES 00105 struct LoopDependence: public Dependence { 00106 DependenceDirection dir; 00107 int distance; 00108 short level; 00109 LoopInfo* enclosingLoop; 00110 }; 00111 #endif 00112 00113 00114 //---------------------------------------------------------------------------- 00115 /// DepGraphNode Class - A representation of a single node in a dependence 00116 /// graph, corresponding to a single instruction. 00117 /// 00118 class DepGraphNode { 00119 Instruction* instr; 00120 std::vector<Dependence> inDeps; 00121 std::vector<Dependence> outDeps; 00122 friend class DependenceGraph; 00123 00124 typedef std::vector<Dependence>:: iterator iterator; 00125 typedef std::vector<Dependence>::const_iterator const_iterator; 00126 00127 iterator inDepBegin() { return inDeps.begin(); } 00128 const_iterator inDepBegin() const { return inDeps.begin(); } 00129 iterator inDepEnd() { return inDeps.end(); } 00130 const_iterator inDepEnd() const { return inDeps.end(); } 00131 00132 iterator outDepBegin() { return outDeps.begin(); } 00133 const_iterator outDepBegin() const { return outDeps.begin(); } 00134 iterator outDepEnd() { return outDeps.end(); } 00135 const_iterator outDepEnd() const { return outDeps.end(); } 00136 00137 public: 00138 DepGraphNode(Instruction& I) : instr(&I) { } 00139 00140 Instruction& getInstr() { return *instr; } 00141 const Instruction& getInstr() const { return *instr; } 00142 00143 /// Debugging support methods 00144 /// 00145 void print(std::ostream &O) const; 00146 }; 00147 00148 00149 //---------------------------------------------------------------------------- 00150 /// DependenceGraph Class - A representation of a dependence graph for a 00151 /// procedure. The primary query operation here is to look up a DepGraphNode for 00152 /// a particular instruction, and then use the in/out dependence iterators 00153 /// for the node. 00154 /// 00155 class DependenceGraph { 00156 DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT 00157 void operator=(const DependenceGraph&); // DO NOT IMPLEMENT 00158 00159 typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType; 00160 typedef DepNodeMapType:: iterator map_iterator; 00161 typedef DepNodeMapType::const_iterator const_map_iterator; 00162 00163 DepNodeMapType depNodeMap; 00164 00165 inline DepGraphNode* getNodeInternal(Instruction& inst, 00166 bool createIfMissing = false) { 00167 map_iterator I = depNodeMap.find(&inst); 00168 if (I == depNodeMap.end()) 00169 return (!createIfMissing)? NULL : 00170 depNodeMap.insert( 00171 std::make_pair(&inst, new DepGraphNode(inst))).first->second; 00172 else 00173 return I->second; 00174 } 00175 00176 public: 00177 typedef std::vector<Dependence>:: iterator iterator; 00178 typedef std::vector<Dependence>::const_iterator const_iterator; 00179 00180 public: 00181 DependenceGraph() { } 00182 ~DependenceGraph(); 00183 00184 /// Get the graph node for an instruction. There will be one if and 00185 /// only if there are any dependences incident on this instruction. 00186 /// If there is none, these methods will return NULL. 00187 /// 00188 DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) { 00189 return getNodeInternal(inst, createIfMissing); 00190 } 00191 const DepGraphNode* getNode(const Instruction& inst) const { 00192 return const_cast<DependenceGraph*>(this) 00193 ->getNodeInternal(const_cast<Instruction&>(inst)); 00194 } 00195 00196 iterator inDepBegin(DepGraphNode& T) { 00197 return T.inDeps.begin(); 00198 } 00199 const_iterator inDepBegin (const DepGraphNode& T) const { 00200 return T.inDeps.begin(); 00201 } 00202 00203 iterator inDepEnd(DepGraphNode& T) { 00204 return T.inDeps.end(); 00205 } 00206 const_iterator inDepEnd(const DepGraphNode& T) const { 00207 return T.inDeps.end(); 00208 } 00209 00210 iterator outDepBegin(DepGraphNode& F) { 00211 return F.outDeps.begin(); 00212 } 00213 const_iterator outDepBegin(const DepGraphNode& F) const { 00214 return F.outDeps.begin(); 00215 } 00216 00217 iterator outDepEnd(DepGraphNode& F) { 00218 return F.outDeps.end(); 00219 } 00220 const_iterator outDepEnd(const DepGraphNode& F) const { 00221 return F.outDeps.end(); 00222 } 00223 00224 /// Debugging support methods 00225 /// 00226 void print(const Function& func, std::ostream &O) const; 00227 00228 public: 00229 /// AddSimpleDependence - adding and modifying the dependence graph. 00230 /// These should to be used only by dependence analysis implementations. 00231 /// 00232 void AddSimpleDependence(Instruction& fromI, Instruction& toI, 00233 DependenceType depType) { 00234 DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true); 00235 DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true); 00236 fromNode->outDeps.push_back(Dependence(toNode, depType, false)); 00237 toNode-> inDeps. push_back(Dependence(fromNode, depType, true)); 00238 } 00239 00240 #ifdef SUPPORTING_LOOP_DEPENDENCES 00241 // This interface is a placeholder to show what information is needed. 00242 // It will probably change when it starts being used. 00243 void AddLoopDependence(Instruction& fromI, 00244 Instruction& toI, 00245 DependenceType depType, 00246 DependenceDirection dir, 00247 int distance, 00248 short level, 00249 LoopInfo* enclosingLoop); 00250 #endif // SUPPORTING_LOOP_DEPENDENCES 00251 }; 00252 00253 } // End llvm namespace 00254 00255 #endif