LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

IPModRef.cpp

Go to the documentation of this file.
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