LLVM API Documentation
00001 //===- PgmDependenceGraph.h - Enumerate the PDG 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 // The Program Dependence Graph (PDG) for a single function represents all 00011 // data and control dependences for the function. This file provides an 00012 // iterator to enumerate all these dependences. In particular, it enumerates: 00013 // 00014 // -- Data dependences on memory locations, computed using the 00015 // MemoryDepAnalysis pass; 00016 // -- Data dependences on SSA registers, directly from Def-Use edges of Values; 00017 // -- Control dependences, computed using postdominance frontiers 00018 // (NOT YET IMPLEMENTED). 00019 // 00020 // Note that this file does not create an explicit dependence graph -- 00021 // it only provides an iterator to traverse the PDG conceptually. 00022 // The MemoryDepAnalysis does build an explicit graph, which is used internally 00023 // here. That graph could be augmented with the other dependences above if 00024 // desired, but for most uses there will be little need to do that. 00025 // 00026 // Key Classes: 00027 // 00028 // enum PDGIteratorFlags -- Specify which dependences to enumerate. 00029 // 00030 // class PDGIterator -- The PDG iterator. This is essentially like a 00031 // pointer to class Dependence, but doesn't explicitly 00032 // construct a Dependence object for each dependence. 00033 // 00034 // class PgmDependenceGraph -- Interface to obtain PDGIterators for each 00035 // instruction. 00036 // 00037 //===----------------------------------------------------------------------===// 00038 00039 #ifndef LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H 00040 #define LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H 00041 00042 #include "MemoryDepAnalysis.h" 00043 /* #include "llvm/Analysis/PostDominators.h" -- see below */ 00044 #include "llvm/Instruction.h" 00045 #include "llvm/Pass.h" 00046 #include "llvm/ADT/iterator" 00047 00048 namespace llvm { 00049 00050 class DSGraph; 00051 class DependenceGraph; 00052 class PgmDependenceGraph; 00053 00054 //--------------------------------------------------------------------------- 00055 /// enum PDGIteratorFlags - specify which dependences incident on a statement 00056 /// are to be enumerated: Memory deps, SSA deps, Control deps, or any 00057 /// combination thereof. 00058 /// 00059 enum PDGIteratorFlags { 00060 MemoryDeps = 0x1, // load/store/call deps 00061 SSADeps = 0x2, // SSA deps (true) 00062 ControlDeps = /* 0x4*/ 0x0, // control dependences 00063 AllDataDeps = MemoryDeps | SSADeps, // shorthand for data deps 00064 AllDeps = MemoryDeps | SSADeps | ControlDeps // shorthand for all three 00065 }; 00066 00067 //--------------------------------------------------------------------------- 00068 /// struct DepIterState - an internal implementation detail. 00069 /// It are exposed here only to give inlinable access to field dep, 00070 /// which is the representation for the current dependence pointed to by 00071 /// a PgmDependenceGraph::iterator. 00072 /// 00073 class DepIterState { 00074 private: 00075 typedef char IterStateFlags; 00076 static const IterStateFlags NoFlag, MemDone, SSADone, AllDone, FirstTimeFlag; 00077 00078 public: 00079 DepGraphNode* depNode; // the node being enumerated 00080 DependenceGraph::iterator memDepIter; // pointer to current memory dep 00081 Instruction::op_iterator ssaInEdgeIter; // pointer to current SSA in-dep 00082 Value::use_iterator ssaOutEdgeIter; // pointer to current SSA out-dep 00083 DependenceGraph* memDepGraph; // the core dependence graph 00084 Dependence dep; // the "current" dependence 00085 PDGIteratorFlags depFlags:8; // which deps are we enumerating? 00086 IterStateFlags iterFlags:8; // marking where the iter stands 00087 00088 DepIterState(DependenceGraph* _memDepGraph, 00089 Instruction& I, 00090 bool incomingDeps, 00091 PDGIteratorFlags whichDeps); 00092 00093 bool operator==(const DepIterState& S) { 00094 assert(memDepGraph == S.memDepGraph && 00095 "Incompatible iterators! This is a probable sign of something BAD."); 00096 return (iterFlags == S.iterFlags && 00097 dep == S.dep && depFlags == S.depFlags && depNode == S.depNode && 00098 memDepIter == S.memDepIter && ssaInEdgeIter == S.ssaInEdgeIter && 00099 ssaOutEdgeIter == S.ssaOutEdgeIter); 00100 } 00101 00102 // Is the iteration completely done? 00103 // 00104 bool done() const { return iterFlags & AllDone; } 00105 00106 /// Next - Bump this iterator logically by 1 (to next dependence) and reset 00107 /// the dep field to represent the new dependence if there is one. 00108 /// Set done = true otherwise. 00109 /// 00110 void Next(); 00111 00112 /// SetFirstMemoryDep - Find the first memory dependence for the current Mem 00113 /// In/Out iterators. Sets dep to that dependence and returns true if one is 00114 /// found. Returns false and leaves dep unchanged otherwise. 00115 /// 00116 bool SetFirstMemoryDep(); 00117 00118 /// SetFirstSSADep - Find the next valid data dependence for the current SSA 00119 /// In/Out iterators. A valid data dependence is one that is to/from an 00120 /// Instruction. E.g., an SSA edge from a formal parameter is not a valid 00121 /// dependence. Sets dep to that dependence and returns true if a valid one is 00122 /// found. Returns false and leaves dep unchanged otherwise. 00123 /// 00124 bool SetFirstSSADep(); 00125 }; 00126 00127 00128 //--------------------------------------------------------------------------- 00129 /// PDGIterator Class - represents a pointer to a single dependence in the 00130 /// program dependence graph. It is essentially like a pointer to an object of 00131 /// class Dependence but it is much more efficient to retrieve information about 00132 /// the dependence directly rather than constructing the equivalent Dependence 00133 /// object (since that object is normally not constructed for SSA def-use 00134 /// dependences). 00135 /// 00136 class PDGIterator: public forward_iterator<Dependence, ptrdiff_t> { 00137 DepIterState* istate; 00138 00139 #if 0 00140 /*copy*/ PDGIterator (const PDGIterator& I); // do not implement! 00141 PDGIterator& operator= (const PDGIterator& I); // do not implement! 00142 00143 /*copy*/ PDGIterator (PDGIterator& I) : istate(I.istate) { 00144 I.istate = NULL; // ensure this is not deleted twice. 00145 } 00146 #endif 00147 00148 friend class PgmDependenceGraph; 00149 00150 public: 00151 typedef PDGIterator _Self; 00152 00153 PDGIterator(DepIterState* _istate) : istate(_istate) {} 00154 ~PDGIterator() { delete istate; } 00155 00156 PDGIterator(const PDGIterator& I) :istate(new DepIterState(*I.istate)) {} 00157 00158 PDGIterator& operator=(const PDGIterator& I) { 00159 if (istate) delete istate; 00160 istate = new DepIterState(*I.istate); 00161 return *this; 00162 } 00163 00164 /// fini - check if the iteration is complete 00165 /// 00166 bool fini() const { return !istate || istate->done(); } 00167 00168 // Retrieve the underlying Dependence. Returns NULL if fini(). 00169 // 00170 Dependence* operator*() const { return fini() ? NULL : &istate->dep; } 00171 Dependence* operator->() const { assert(!fini()); return &istate->dep; } 00172 00173 // Increment the iterator 00174 // 00175 _Self& operator++() { if (!fini()) istate->Next(); return *this;} 00176 _Self& operator++(int); // do not implement! 00177 00178 // Equality comparison: a "null" state should compare equal to done 00179 // This is efficient for comparing with "end" or with itself, but could 00180 // be quite inefficient for other cases. 00181 // 00182 bool operator==(const PDGIterator& I) const { 00183 if (I.istate == NULL) // most common case: iter == end() 00184 return (istate == NULL || istate->done()); 00185 if (istate == NULL) 00186 return (I.istate == NULL || I.istate->done()); 00187 return (*istate == *I.istate); 00188 } 00189 bool operator!=(const PDGIterator& I) const { 00190 return ! (*this == I); 00191 } 00192 }; 00193 00194 00195 ///--------------------------------------------------------------------------- 00196 /// class PgmDependenceGraph: 00197 /// 00198 /// This pass enumerates dependences incident on each instruction in a function. 00199 /// It can be made a FunctionPass once a Pass (such as Parallelize) is 00200 /// allowed to use a FunctionPass such as this one. 00201 ///--------------------------------------------------------------------------- 00202 00203 class PgmDependenceGraph: public ModulePass { 00204 00205 /// Information about the function being analyzed. 00206 /// 00207 DependenceGraph* memDepGraph; 00208 00209 // print helper function. 00210 void printOutgoingSSADeps(Instruction& I, std::ostream &O); 00211 00212 /// MakeIterator - creates and initializes an iterator as specified. 00213 /// 00214 PDGIterator MakeIterator(Instruction& I, 00215 bool incomingDeps, 00216 PDGIteratorFlags whichDeps); 00217 00218 /// MakeIterator - creates a null iterator representing end-of-iteration. 00219 /// 00220 PDGIterator MakeIterator() { return PDGIterator(NULL); } 00221 00222 friend class PDGIterator; 00223 friend class DepIterState; 00224 00225 public: 00226 typedef PDGIterator iterator; 00227 /* typedef PDGIterator<const Dependence> const iterator; */ 00228 00229 public: 00230 PgmDependenceGraph() : memDepGraph(NULL) {} 00231 ~PgmDependenceGraph() {} 00232 00233 /// Iterators to enumerate the program dependence graph for a function. 00234 /// Note that this does not provide "end" iterators to check for completion. 00235 /// Instead, just use iterator::fini() or iterator::operator*() == NULL 00236 /// 00237 iterator inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) { 00238 return MakeIterator(I, /*inDeps*/ true, whichDeps); 00239 } 00240 iterator inDepEnd (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) { 00241 return MakeIterator(); 00242 } 00243 iterator outDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) { 00244 return MakeIterator(I, /*inDeps*/ false, whichDeps); 00245 } 00246 iterator outDepEnd (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) { 00247 return MakeIterator(); 00248 } 00249 00250 //------------------------------------------------------------------------ 00251 /// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS --- 00252 /// These functions will go away once this class becomes a FunctionPass. 00253 00254 /// Driver function to compute dependence graphs for every function. 00255 /// 00256 bool runOnModule(Module& M) { return true; } 00257 00258 /// getGraph() -- Retrieve the pgm dependence graph for a function. 00259 /// This is temporary and will go away once this is a FunctionPass. 00260 /// At that point, this class itself will be the PgmDependenceGraph you want. 00261 /// 00262 PgmDependenceGraph& getGraph(Function& F) { 00263 Visiting(F); 00264 return *this; 00265 } 00266 00267 private: 00268 void Visiting(Function& F) { 00269 memDepGraph = &getAnalysis<MemoryDepAnalysis>().getGraph(F); 00270 } 00271 public: 00272 ///----END TEMPORARY FUNCTIONS--------------------------------------------- 00273 00274 00275 /// This initializes the program dependence graph iterator for a function. 00276 /// 00277 bool runOnFunction(Function& func) { 00278 Visiting(func); 00279 return true; 00280 } 00281 00282 /// getAnalysisUsage - This does not modify anything. 00283 /// It uses the Memory Dependence Analysis pass. 00284 /// It needs to use the PostDominanceFrontier pass, but cannot because 00285 /// that is a FunctionPass. This means control dependence are not emumerated. 00286 /// 00287 void getAnalysisUsage(AnalysisUsage &AU) const { 00288 AU.setPreservesAll(); 00289 AU.addRequired<MemoryDepAnalysis>(); 00290 /* AU.addRequired<PostDominanceFrontier>(); */ 00291 } 00292 00293 /// Debugging support methods 00294 /// 00295 void print(std::ostream &O) const; 00296 void dump() const; 00297 }; 00298 00299 } // End llvm namespace 00300 00301 #endif