LLVM API Documentation
00001 //===- PgmDependenceGraph.cpp - Enumerate 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 //===----------------------------------------------------------------------===// 00027 00028 #include "PgmDependenceGraph.h" 00029 #include "llvm/Analysis/PostDominators.h" 00030 #include "llvm/Function.h" 00031 #include <iostream> 00032 00033 namespace llvm { 00034 00035 //---------------------------------------------------------------------------- 00036 // class DepIterState 00037 //---------------------------------------------------------------------------- 00038 00039 const DepIterState::IterStateFlags DepIterState::NoFlag = 0x0; 00040 const DepIterState::IterStateFlags DepIterState::MemDone = 0x1; 00041 const DepIterState::IterStateFlags DepIterState::SSADone = 0x2; 00042 const DepIterState::IterStateFlags DepIterState::AllDone = 0x4; 00043 const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8; 00044 00045 // Find the first memory dependence for the current Mem In/Out iterators. 00046 // Find the first memory dependence for the current Mem In/Out iterators. 00047 // Sets dep to that dependence and returns true if one is found. 00048 // 00049 bool DepIterState::SetFirstMemoryDep() 00050 { 00051 if (! (depFlags & MemoryDeps)) 00052 return false; 00053 00054 bool doIncomingDeps = dep.getDepType() & IncomingFlag; 00055 00056 if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) || 00057 (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode))) 00058 { 00059 iterFlags |= MemDone; 00060 return false; 00061 } 00062 00063 dep = *memDepIter; // simple copy from dependence in memory DepGraph 00064 00065 return true; 00066 } 00067 00068 00069 // Find the first valid data dependence for the current SSA In/Out iterators. 00070 // A valid data dependence is one that is to/from an Instruction. 00071 // E.g., an SSA edge from a formal parameter is not a valid dependence. 00072 // Sets dep to that dependence and returns true if a valid one is found. 00073 // Returns false and leaves dep unchanged otherwise. 00074 // 00075 bool DepIterState::SetFirstSSADep() 00076 { 00077 if (! (depFlags & SSADeps)) 00078 return false; 00079 00080 bool doIncomingDeps = dep.getDepType() & IncomingFlag; 00081 Instruction* firstTarget = NULL; 00082 00083 // Increment the In or Out iterator till it runs out or we find a valid dep 00084 if (doIncomingDeps) 00085 for (Instruction::op_iterator E = depNode->getInstr().op_end(); 00086 ssaInEdgeIter != E && 00087 (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter))== NULL; ) 00088 ++ssaInEdgeIter; 00089 else 00090 for (Value::use_iterator E = depNode->getInstr().use_end(); 00091 ssaOutEdgeIter != E && 00092 (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; ) 00093 ++ssaOutEdgeIter; 00094 00095 // If the iterator ran out before we found a valid dep, there isn't one. 00096 if (!firstTarget) 00097 { 00098 iterFlags |= SSADone; 00099 return false; 00100 } 00101 00102 // Create a simple dependence object to represent this SSA dependence. 00103 dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true), 00104 TrueDependence, doIncomingDeps); 00105 00106 return true; 00107 } 00108 00109 00110 DepIterState::DepIterState(DependenceGraph* _memDepGraph, 00111 Instruction& I, 00112 bool incomingDeps, 00113 PDGIteratorFlags whichDeps) 00114 : memDepGraph(_memDepGraph), 00115 depFlags(whichDeps), 00116 iterFlags(NoFlag) 00117 { 00118 depNode = memDepGraph->getNode(I, /*create*/ true); 00119 00120 if (incomingDeps) 00121 { 00122 if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode); 00123 if (whichDeps & SSADeps) ssaInEdgeIter = I.op_begin(); 00124 /* Initialize control dependence iterator here. */ 00125 } 00126 else 00127 { 00128 if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode); 00129 if (whichDeps & SSADeps) ssaOutEdgeIter = I.use_begin(); 00130 /* Initialize control dependence iterator here. */ 00131 } 00132 00133 // Set the dependence to the first of a memory dep or an SSA dep 00134 // and set the done flag if either is found. Otherwise, set the 00135 // init flag to indicate that the iterators have just been initialized. 00136 // 00137 if (!SetFirstMemoryDep() && !SetFirstSSADep()) 00138 iterFlags |= AllDone; 00139 else 00140 iterFlags |= FirstTimeFlag; 00141 } 00142 00143 00144 // Helper function for ++ operator that bumps iterator by 1 (to next 00145 // dependence) and resets the dep field to represent the new dependence. 00146 // 00147 void DepIterState::Next() 00148 { 00149 // firstMemDone and firstSsaDone are used to indicate when the memory or 00150 // SSA iterators just ran out, or when this is the very first increment. 00151 // In either case, the next iterator (if any) should not be incremented. 00152 // 00153 bool firstMemDone = iterFlags & FirstTimeFlag; 00154 bool firstSsaDone = iterFlags & FirstTimeFlag; 00155 bool doIncomingDeps = dep.getDepType() & IncomingFlag; 00156 00157 if (depFlags & MemoryDeps && ! (iterFlags & MemDone)) 00158 { 00159 iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag 00160 ++memDepIter; 00161 if (SetFirstMemoryDep()) 00162 return; 00163 firstMemDone = true; // flags that we _just_ rolled over 00164 } 00165 00166 if (depFlags & SSADeps && ! (iterFlags & SSADone)) 00167 { 00168 // Don't increment the SSA iterator if we either just rolled over from 00169 // the memory dep iterator, or if the SSA iterator is already done. 00170 iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag 00171 if (! firstMemDone) 00172 if (doIncomingDeps) ++ssaInEdgeIter; 00173 else ++ssaOutEdgeIter; 00174 if (SetFirstSSADep()) 00175 return; 00176 firstSsaDone = true; // flags if we just rolled over 00177 } 00178 00179 if (depFlags & ControlDeps != 0) 00180 { 00181 assert(0 && "Cannot handle control deps"); 00182 // iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag 00183 } 00184 00185 // This iterator is now complete. 00186 iterFlags |= AllDone; 00187 } 00188 00189 00190 //---------------------------------------------------------------------------- 00191 // class PgmDependenceGraph 00192 //---------------------------------------------------------------------------- 00193 00194 00195 // MakeIterator -- Create and initialize an iterator as specified. 00196 // 00197 PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I, 00198 bool incomingDeps, 00199 PDGIteratorFlags whichDeps) 00200 { 00201 assert(memDepGraph && "Function not initialized!"); 00202 return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps)); 00203 } 00204 00205 00206 void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I, 00207 std::ostream &O) 00208 { 00209 iterator SI = this->outDepBegin(I, SSADeps); 00210 iterator SE = this->outDepEnd(I, SSADeps); 00211 if (SI == SE) 00212 return; 00213 00214 O << "\n Outgoing SSA dependences:\n"; 00215 for ( ; SI != SE; ++SI) 00216 { 00217 O << "\t"; 00218 SI->print(O); 00219 O << " to instruction:"; 00220 O << SI->getSink()->getInstr(); 00221 } 00222 } 00223 00224 00225 void PgmDependenceGraph::print(std::ostream &O) const 00226 { 00227 MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>(); 00228 00229 // TEMPORARY LOOP 00230 for (hash_map<Function*, DependenceGraph*>::iterator 00231 I = graphSet.funcMap.begin(), E = graphSet.funcMap.end(); 00232 I != E; ++I) 00233 { 00234 Function* func = I->first; 00235 DependenceGraph* depGraph = I->second; 00236 const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func); 00237 00238 O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n"; 00239 for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB) 00240 for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II) 00241 { 00242 DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true); 00243 dgNode->print(O); 00244 const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O); 00245 } 00246 } // END TEMPORARY LOOP 00247 } 00248 00249 00250 void PgmDependenceGraph::dump() const 00251 { 00252 this->print(std::cerr); 00253 } 00254 00255 static RegisterAnalysis<PgmDependenceGraph> 00256 Z("pgmdep", "Enumerate Program Dependence Graph (data and control)"); 00257 00258 } // End llvm namespace