LLVM API Documentation
00001 //===- IPModRef.cpp - Compute IP Mod/Ref information ------------*- 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 // See high-level comments in IPModRef.h 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "IPModRef.h" 00015 #include "llvm/Analysis/DataStructure/DataStructure.h" 00016 #include "llvm/Analysis/DataStructure/DSGraph.h" 00017 #include "llvm/Module.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/ADT/Statistic.h" 00020 #include "llvm/ADT/STLExtras.h" 00021 #include "llvm/ADT/StringExtras.h" 00022 #include <vector> 00023 00024 namespace llvm { 00025 00026 //---------------------------------------------------------------------------- 00027 // Private constants and data 00028 //---------------------------------------------------------------------------- 00029 00030 static RegisterAnalysis<IPModRef> 00031 Z("ipmodref", "Interprocedural mod/ref analysis"); 00032 00033 00034 //---------------------------------------------------------------------------- 00035 // class ModRefInfo 00036 //---------------------------------------------------------------------------- 00037 00038 void ModRefInfo::print(std::ostream &O, 00039 const std::string& sprefix) const 00040 { 00041 O << sprefix << "Modified nodes = " << modNodeSet; 00042 O << sprefix << "Referenced nodes = " << refNodeSet; 00043 } 00044 00045 void ModRefInfo::dump() const 00046 { 00047 print(std::cerr); 00048 } 00049 00050 //---------------------------------------------------------------------------- 00051 // class FunctionModRefInfo 00052 //---------------------------------------------------------------------------- 00053 00054 00055 // This constructor computes a node numbering for the TD graph. 00056 // 00057 FunctionModRefInfo::FunctionModRefInfo(const Function& func, 00058 IPModRef& ipmro, 00059 DSGraph* tdgClone) 00060 : F(func), IPModRefObj(ipmro), 00061 funcTDGraph(tdgClone), 00062 funcModRefInfo(tdgClone->getGraphSize()) 00063 { 00064 unsigned i = 0; 00065 for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), 00066 E = funcTDGraph->node_end(); NI != E; ++NI) 00067 NodeIds[*NI] = i++; 00068 } 00069 00070 00071 FunctionModRefInfo::~FunctionModRefInfo() 00072 { 00073 for(std::map<const Instruction*, ModRefInfo*>::iterator 00074 I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I) 00075 delete(I->second); 00076 00077 // Empty map just to make problems easier to track down 00078 callSiteModRefInfo.clear(); 00079 00080 delete funcTDGraph; 00081 } 00082 00083 unsigned FunctionModRefInfo::getNodeId(const Value* value) const { 00084 return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value)) 00085 .getNode()); 00086 } 00087 00088 00089 00090 // Compute Mod/Ref bit vectors for the entire function. 00091 // These are simply copies of the Read/Write flags from the nodes of 00092 // the top-down DS graph. 00093 // 00094 void FunctionModRefInfo::computeModRef(const Function &func) 00095 { 00096 // Mark all nodes in the graph that are marked MOD as being mod 00097 // and all those marked REF as being ref. 00098 unsigned i = 0; 00099 for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), 00100 E = funcTDGraph->node_end(); NI != E; ++NI, ++i) { 00101 if ((*NI)->isModified()) funcModRefInfo.setNodeIsMod(i); 00102 if ((*NI)->isRead()) funcModRefInfo.setNodeIsRef(i); 00103 } 00104 00105 // Compute the Mod/Ref info for all call sites within the function. 00106 // The call sites are recorded in the TD graph. 00107 const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls(); 00108 for (unsigned i = 0, N = callSites.size(); i < N; ++i) 00109 computeModRef(callSites[i].getCallSite()); 00110 } 00111 00112 00113 // ResolveCallSiteModRefInfo - This method performs the following actions: 00114 // 00115 // 1. It clones the top-down graph for the current function 00116 // 2. It clears all of the mod/ref bits in the cloned graph 00117 // 3. It then merges the bottom-up graph(s) for the specified call-site into 00118 // the clone (bringing new mod/ref bits). 00119 // 4. It returns the clone, and a mapping of nodes from the original TDGraph to 00120 // the cloned graph with Mod/Ref info for the callsite. 00121 // 00122 // NOTE: Because this clones a dsgraph and returns it, the caller is responsible 00123 // for deleting the returned graph! 00124 // NOTE: This method may return a null pointer if it is unable to determine the 00125 // requested information (because the call site calls an external 00126 // function or we cannot determine the complete set of functions invoked). 00127 // 00128 DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallSite CS, 00129 hash_map<const DSNode*, DSNodeHandle> &NodeMap) 00130 { 00131 // Step #0: Quick check if we are going to fail anyway: avoid 00132 // all the graph cloning and map copying in steps #1 and #2. 00133 // 00134 if (const Function *F = CS.getCalledFunction()) { 00135 if (F->isExternal()) 00136 return 0; // We cannot compute Mod/Ref info for this callsite... 00137 } else { 00138 // Eventually, should check here if any callee is external. 00139 // For now we are not handling this case anyway. 00140 std::cerr << "IP Mod/Ref indirect call not implemented yet: " 00141 << "Being conservative\n"; 00142 return 0; // We cannot compute Mod/Ref info for this callsite... 00143 } 00144 00145 // Step #1: Clone the top-down graph... 00146 DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap); 00147 00148 // Step #2: Clear Mod/Ref information... 00149 Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read)); 00150 00151 // Step #3: clone the bottom up graphs for the callees into the caller graph 00152 if (Function *F = CS.getCalledFunction()) 00153 { 00154 assert(!F->isExternal()); 00155 00156 // Build up a DSCallSite for our invocation point here... 00157 00158 // If the call returns a value, make sure to merge the nodes... 00159 DSNodeHandle RetVal; 00160 if (DS::isPointerType(CS.getInstruction()->getType())) 00161 RetVal = Result->getNodeForValue(CS.getInstruction()); 00162 00163 // Populate the arguments list... 00164 std::vector<DSNodeHandle> Args; 00165 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 00166 I != E; ++I) 00167 if (DS::isPointerType((*I)->getType())) 00168 Args.push_back(Result->getNodeForValue(*I)); 00169 00170 // Build the call site... 00171 DSCallSite NCS(CS, RetVal, F, Args); 00172 00173 // Perform the merging now of the graph for the callee, which will 00174 // come with mod/ref bits set... 00175 Result->mergeInGraph(NCS, *F, IPModRefObj.getBUDSGraph(*F), 00176 DSGraph::StripAllocaBit 00177 | DSGraph::DontCloneCallNodes 00178 | DSGraph::DontCloneAuxCallNodes); 00179 } 00180 else 00181 assert(0 && "See error message"); 00182 00183 // Remove dead nodes aggressively to match the caller's original graph. 00184 Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00185 00186 // Step #4: Return the clone + the mapping (by ref) 00187 return Result; 00188 } 00189 00190 // Compute Mod/Ref bit vectors for a single call site. 00191 // These are copies of the Read/Write flags from the nodes of 00192 // the graph produced by clearing all flags in the caller's TD graph 00193 // and then inlining the callee's BU graph into the caller's TD graph. 00194 // 00195 void 00196 FunctionModRefInfo::computeModRef(CallSite CS) 00197 { 00198 // Allocate the mod/ref info for the call site. Bits automatically cleared. 00199 ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize()); 00200 callSiteModRefInfo[CS.getInstruction()] = callModRefInfo; 00201 00202 // Get a copy of the graph for the callee with the callee inlined 00203 hash_map<const DSNode*, DSNodeHandle> NodeMap; 00204 DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap); 00205 if (!csgp) 00206 { // Callee's side effects are unknown: mark all nodes Mod and Ref. 00207 // Eventually this should only mark nodes visible to the callee, i.e., 00208 // exclude stack variables not reachable from any outgoing argument 00209 // or any global. 00210 callModRefInfo->getModSet().set(); 00211 callModRefInfo->getRefSet().set(); 00212 return; 00213 } 00214 00215 // For all nodes in the graph, extract the mod/ref information 00216 for (DSGraph::node_iterator NI = funcTDGraph->node_begin(), 00217 E = funcTDGraph->node_end(); NI != E; ++NI) { 00218 DSNode* csgNode = NodeMap[*NI].getNode(); 00219 assert(csgNode && "Inlined and original graphs do not correspond!"); 00220 if (csgNode->isModified()) 00221 callModRefInfo->setNodeIsMod(getNodeId(*NI)); 00222 if (csgNode->isRead()) 00223 callModRefInfo->setNodeIsRef(getNodeId(*NI)); 00224 } 00225 00226 // Drop nodemap before we delete the graph... 00227 NodeMap.clear(); 00228 delete csgp; 00229 } 00230 00231 00232 class DSGraphPrintHelper { 00233 const DSGraph& tdGraph; 00234 std::vector<std::vector<const Value*> > knownValues; // identifiable objects 00235 00236 public: 00237 /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo) 00238 : tdGraph(fmrInfo.getFuncGraph()) 00239 { 00240 knownValues.resize(tdGraph.getGraphSize()); 00241 00242 // For every identifiable value, save Value pointer in knownValues[i] 00243 for (hash_map<Value*, DSNodeHandle>::const_iterator 00244 I = tdGraph.getScalarMap().begin(), 00245 E = tdGraph.getScalarMap().end(); I != E; ++I) 00246 if (isa<GlobalValue>(I->first) || 00247 isa<Argument>(I->first) || 00248 isa<LoadInst>(I->first) || 00249 isa<AllocaInst>(I->first) || 00250 isa<MallocInst>(I->first)) 00251 { 00252 unsigned nodeId = fmrInfo.getNodeId(I->second.getNode()); 00253 knownValues[nodeId].push_back(I->first); 00254 } 00255 } 00256 00257 void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const 00258 { 00259 assert(bv.size() == knownValues.size()); 00260 00261 if (bv.none()) 00262 { // No bits are set: just say so and return 00263 O << "\tNONE.\n"; 00264 return; 00265 } 00266 00267 if (bv.all()) 00268 { // All bits are set: just say so and return 00269 O << "\tALL GRAPH NODES.\n"; 00270 return; 00271 } 00272 00273 for (unsigned i=0, N=bv.size(); i < N; ++i) 00274 if (bv.test(i)) 00275 { 00276 O << "\tNode# " << i << " : "; 00277 if (! knownValues[i].empty()) 00278 for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++) 00279 { 00280 const Value* V = knownValues[i][j]; 00281 00282 if (isa<GlobalValue>(V)) O << "(Global) "; 00283 else if (isa<Argument>(V)) O << "(Target of FormalParm) "; 00284 else if (isa<LoadInst>(V)) O << "(Target of LoadInst ) "; 00285 else if (isa<AllocaInst>(V)) O << "(Target of AllocaInst) "; 00286 else if (isa<MallocInst>(V)) O << "(Target of MallocInst) "; 00287 00288 if (V->hasName()) O << V->getName(); 00289 else if (isa<Instruction>(V)) O << *V; 00290 else O << "(Value*) 0x" << (void*) V; 00291 00292 O << std::string((j < NV-1)? "; " : "\n"); 00293 } 00294 #if 0 00295 else 00296 tdGraph.getNodes()[i]->print(O, /*graph*/ NULL); 00297 #endif 00298 } 00299 } 00300 }; 00301 00302 00303 // Print the results of the pass. 00304 // Currently this just prints bit-vectors and is not very readable. 00305 // 00306 void FunctionModRefInfo::print(std::ostream &O) const 00307 { 00308 DSGraphPrintHelper DPH(*this); 00309 00310 O << "========== Mod/ref information for function " 00311 << F.getName() << "========== \n\n"; 00312 00313 // First: Print Globals and Locals modified anywhere in the function. 00314 // 00315 O << " -----Mod/Ref in the body of function " << F.getName()<< ":\n"; 00316 00317 O << " --Objects modified in the function body:\n"; 00318 DPH.printValuesInBitVec(O, funcModRefInfo.getModSet()); 00319 00320 O << " --Objects referenced in the function body:\n"; 00321 DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet()); 00322 00323 O << " --Mod and Ref vectors for the nodes listed above:\n"; 00324 funcModRefInfo.print(O, "\t"); 00325 00326 O << "\n"; 00327 00328 // Second: Print Globals and Locals modified at each call site in function 00329 // 00330 for (std::map<const Instruction *, ModRefInfo*>::const_iterator 00331 CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end(); 00332 CI != CE; ++CI) 00333 { 00334 O << " ----Mod/Ref information for call site\n" << *CI->first; 00335 00336 O << " --Objects modified at call site:\n"; 00337 DPH.printValuesInBitVec(O, CI->second->getModSet()); 00338 00339 O << " --Objects referenced at call site:\n"; 00340 DPH.printValuesInBitVec(O, CI->second->getRefSet()); 00341 00342 O << " --Mod and Ref vectors for the nodes listed above:\n"; 00343 CI->second->print(O, "\t"); 00344 00345 O << "\n"; 00346 } 00347 00348 O << "\n"; 00349 } 00350 00351 void FunctionModRefInfo::dump() const 00352 { 00353 print(std::cerr); 00354 } 00355 00356 00357 //---------------------------------------------------------------------------- 00358 // class IPModRef: An interprocedural pass that computes IP Mod/Ref info. 00359 //---------------------------------------------------------------------------- 00360 00361 // Free the FunctionModRefInfo objects cached in funcToModRefInfoMap. 00362 // 00363 void IPModRef::releaseMemory() 00364 { 00365 for(std::map<const Function*, FunctionModRefInfo*>::iterator 00366 I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I) 00367 delete(I->second); 00368 00369 // Clear map so memory is not re-released if we are called again 00370 funcToModRefInfoMap.clear(); 00371 } 00372 00373 // Run the "interprocedural" pass on each function. This needs to do 00374 // NO real interprocedural work because all that has been done the 00375 // data structure analysis. 00376 // 00377 bool IPModRef::runOnModule(Module &theModule) 00378 { 00379 M = &theModule; 00380 00381 for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI) 00382 if (! FI->isExternal()) 00383 getFuncInfo(*FI, /*computeIfMissing*/ true); 00384 return true; 00385 } 00386 00387 00388 FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func, 00389 bool computeIfMissing) 00390 { 00391 FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func]; 00392 assert (funcInfo != NULL || computeIfMissing); 00393 if (funcInfo == NULL) 00394 { // Create a new FunctionModRefInfo object. 00395 // Clone the top-down graph and remove any dead nodes first, because 00396 // otherwise original and merged graphs will not match. 00397 // The memory for this graph clone will be freed by FunctionModRefInfo. 00398 DSGraph* funcTDGraph = 00399 new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func)); 00400 funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00401 00402 funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert 00403 funcInfo->computeModRef(func); // computes the mod/ref info 00404 } 00405 return *funcInfo; 00406 } 00407 00408 /// getBUDSGraph - This method returns the BU data structure graph for F through 00409 /// the use of the BUDataStructures object. 00410 /// 00411 const DSGraph &IPModRef::getBUDSGraph(const Function &F) { 00412 return getAnalysis<BUDataStructures>().getDSGraph(F); 00413 } 00414 00415 00416 // getAnalysisUsage - This pass requires top-down data structure graphs. 00417 // It modifies nothing. 00418 // 00419 void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const { 00420 AU.setPreservesAll(); 00421 AU.addRequired<LocalDataStructures>(); 00422 AU.addRequired<BUDataStructures>(); 00423 AU.addRequired<TDDataStructures>(); 00424 } 00425 00426 00427 void IPModRef::print(std::ostream &O) const 00428 { 00429 O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n"; 00430 00431 for (std::map<const Function*, FunctionModRefInfo*>::const_iterator 00432 mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end(); 00433 mapI != mapE; ++mapI) 00434 mapI->second->print(O); 00435 00436 O << "\n"; 00437 } 00438 00439 00440 void IPModRef::dump() const 00441 { 00442 print(std::cerr); 00443 } 00444 00445 } // End llvm namespace