lib/Analysis/DataStructure/IPModRef.cpp

   1 //===- IPModRef.cpp - Compute IP Mod/Ref information ------------*- C++ -*-===//
   2 //
   3 // See high-level comments in include/llvm/Analysis/IPModRef.h
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/IPModRef.h"
   8 #include "llvm/Analysis/DataStructure.h"
   9 #include "llvm/Analysis/DSGraph.h"
  10 #include "llvm/Module.h"
  11 #include "llvm/Function.h"
  12 #include "llvm/iMemory.h"
  13 #include "llvm/iOther.h"
  14 #include "Support/Statistic.h"
  15 #include "Support/STLExtras.h"
  16 #include "Support/StringExtras.h"
  17 #include <vector>
  18
  19 //----------------------------------------------------------------------------
  20 // Private constants and data
  21 //----------------------------------------------------------------------------
  22
  23 static RegisterAnalysis<IPModRef>
  24 Z("ipmodref", "Interprocedural mod/ref analysis");
  25
  26
  27 //----------------------------------------------------------------------------
  28 // class ModRefInfo
  29 //----------------------------------------------------------------------------
  30
  31 void ModRefInfo::print(std::ostream &O,
  32                        const std::string& sprefix) const
  33 {
  34   O << sprefix << "Modified   nodes = " << modNodeSet;
  35   O << sprefix << "Referenced nodes = " << refNodeSet;
  36 }
  37
  38 void ModRefInfo::dump() const
  39 {
  40   print(std::cerr);
  41 }
  42
  43 //----------------------------------------------------------------------------
  44 // class FunctionModRefInfo
  45 //----------------------------------------------------------------------------
  46
  47
  48 // This constructor computes a node numbering for the TD graph.
  49 //
  50 FunctionModRefInfo::FunctionModRefInfo(const Function& func,
  51                                        IPModRef& ipmro,
  52                                        DSGraph* tdgClone)
  53   : F(func), IPModRefObj(ipmro),
  54     funcTDGraph(tdgClone),
  55     funcModRefInfo(tdgClone->getGraphSize())
  56 {
  57   for (unsigned i=0, N = funcTDGraph->getGraphSize(); i < N; ++i)
  58     NodeIds[funcTDGraph->getNodes()[i]] = i;
  59 }
  60
  61
  62 FunctionModRefInfo::~FunctionModRefInfo()
  63 {
  64   for(std::map<const CallInst*, ModRefInfo*>::iterator
  65         I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I)
  66     delete(I->second);
  67
  68   // Empty map just to make problems easier to track down
  69   callSiteModRefInfo.clear();
  70
  71   delete funcTDGraph;
  72 }
  73
  74 unsigned FunctionModRefInfo::getNodeId(const Value* value) const {
  75   return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value))
  76                    .getNode());
  77 }
  78
  79
  80
  81 // Compute Mod/Ref bit vectors for the entire function.
  82 // These are simply copies of the Read/Write flags from the nodes of
  83 // the top-down DS graph.
  84 //
  85 void FunctionModRefInfo::computeModRef(const Function &func)
  86 {
  87   // Mark all nodes in the graph that are marked MOD as being mod
  88   // and all those marked REF as being ref.
  89   for (unsigned i = 0, N = funcTDGraph->getGraphSize(); i < N; ++i)
  90     {
  91       if (funcTDGraph->getNodes()[i]->isModified())
  92         funcModRefInfo.setNodeIsMod(i);
  93       if (funcTDGraph->getNodes()[i]->isRead())
  94         funcModRefInfo.setNodeIsRef(i);
  95     }
  96
  97   // Compute the Mod/Ref info for all call sites within the function.
  98   // The call sites are recorded in the TD graph.
  99   const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls();
 100   for (unsigned i = 0, N = callSites.size(); i < N; ++i)
 101     computeModRef(callSites[i].getCallInst());
 102 }
 103
 104
 105 // ResolveCallSiteModRefInfo - This method performs the following actions:
 106 //
 107 //  1. It clones the top-down graph for the current function
 108 //  2. It clears all of the mod/ref bits in the cloned graph
 109 //  3. It then merges the bottom-up graph(s) for the specified call-site into
 110 //     the clone (bringing new mod/ref bits).
 111 //  4. It returns the clone, and a mapping of nodes from the original TDGraph to
 112 //     the cloned graph with Mod/Ref info for the callsite.
 113 //
 114 // NOTE: Because this clones a dsgraph and returns it, the caller is responsible
 115 //       for deleting the returned graph!
 116 // NOTE: This method may return a null pointer if it is unable to determine the
 117 //       requested information (because the call site calls an external
 118 //       function or we cannot determine the complete set of functions invoked).
 119 //
 120 DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI,
 121                                hash_map<const DSNode*, DSNodeHandle> &NodeMap)
 122 {
 123   // Step #0: Quick check if we are going to fail anyway: avoid
 124   // all the graph cloning and map copying in steps #1 and #2.
 125   //
 126   if (const Function *F = CI.getCalledFunction())
 127     {
 128       if (F->isExternal())
 129         return 0;   // We cannot compute Mod/Ref info for this callsite...
 130     }
 131   else
 132     {
 133       // Eventually, should check here if any callee is external.
 134       // For now we are not handling this case anyway.
 135       std::cerr << "IP Mod/Ref indirect call not implemented yet: "
 136               << "Being conservative\n";
 137       return 0;   // We cannot compute Mod/Ref info for this callsite...
 138     }
 139
 140   // Step #1: Clone the top-down graph...
 141   DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap);
 142
 143   // Step #2: Clear Mod/Ref information...
 144   Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read));
 145
 146   // Step #3: clone the bottom up graphs for the callees into the caller graph
 147   if (const Function *F = CI.getCalledFunction())
 148     {
 149       assert(!F->isExternal());
 150
 151       // Build up a DSCallSite for our invocation point here...
 152
 153       // If the call returns a value, make sure to merge the nodes...
 154       DSNodeHandle RetVal;
 155       if (DS::isPointerType(CI.getType()))
 156         RetVal = Result->getNodeForValue(&CI);
 157
 158       // Populate the arguments list...
 159       std::vector<DSNodeHandle> Args;
 160       for (unsigned i = 1, e = CI.getNumOperands(); i != e; ++i)
 161         if (DS::isPointerType(CI.getOperand(i)->getType()))
 162           Args.push_back(Result->getNodeForValue(CI.getOperand(i)));
 163
 164       // Build the call site...
 165       DSCallSite CS(CI, RetVal, 0, Args);
 166
 167       // Perform the merging now of the graph for the callee, which will
 168       // come with mod/ref bits set...
 169       Result->mergeInGraph(CS, IPModRefObj.getBUDSGraph(*F),
 170                            DSGraph::StripAllocaBit
 171                            | DSGraph::DontCloneCallNodes
 172                            | DSGraph::DontCloneAuxCallNodes);
 173     }
 174   else
 175     assert(0 && "See error message");
 176
 177   // Remove dead nodes aggressively to match the caller's original graph.
 178   Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 179
 180   // Step #4: Return the clone + the mapping (by ref)
 181   return Result;
 182 }
 183
 184 // Compute Mod/Ref bit vectors for a single call site.
 185 // These are copies of the Read/Write flags from the nodes of
 186 // the graph produced by clearing all flags in teh caller's TD graph
 187 // and then inlining the callee's BU graph into the caller's TD graph.
 188 //
 189 void
 190 FunctionModRefInfo::computeModRef(const CallInst& callInst)
 191 {
 192   // Allocate the mod/ref info for the call site.  Bits automatically cleared.
 193   ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize());
 194   callSiteModRefInfo[&callInst] = callModRefInfo;
 195
 196   // Get a copy of the graph for the callee with the callee inlined
 197   hash_map<const DSNode*, DSNodeHandle> NodeMap;
 198   DSGraph* csgp = ResolveCallSiteModRefInfo(const_cast<CallInst&>(callInst),
 199                                             NodeMap);
 200   if (!csgp)
 201     { // Callee's side effects are unknown: mark all nodes Mod and Ref.
 202       // Eventually this should only mark nodes visible to the callee, i.e.,
 203       // exclude stack variables not reachable from any outgoing argument
 204       // or any global.
 205       callModRefInfo->getModSet().set();
 206       callModRefInfo->getRefSet().set();
 207       return;
 208     }
 209
 210   // For all nodes in the graph, extract the mod/ref information
 211   const std::vector<DSNode*>& csgNodes = csgp->getNodes();
 212   const std::vector<DSNode*>& origNodes = funcTDGraph->getNodes();
 213   assert(csgNodes.size() == origNodes.size());
 214   for (unsigned i=0, N = origNodes.size(); i < N; ++i)
 215     {
 216       DSNode* csgNode = NodeMap[origNodes[i]].getNode();
 217       assert(csgNode && "Inlined and original graphs do not correspond!");
 218       if (csgNode->isModified())
 219         callModRefInfo->setNodeIsMod(getNodeId(origNodes[i]));
 220       if (csgNode->isRead())
 221         callModRefInfo->setNodeIsRef(getNodeId(origNodes[i]));
 222     }
 223
 224   // Drop nodemap before we delete the graph...
 225   NodeMap.clear();
 226   delete csgp;
 227 }
 228
 229
 230 class DSGraphPrintHelper {
 231   const DSGraph& tdGraph;
 232   std::vector<std::vector<const Value*> > knownValues; // identifiable objects
 233
 234 public:
 235   /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo)
 236     : tdGraph(fmrInfo.getFuncGraph())
 237   {
 238     knownValues.resize(tdGraph.getGraphSize());
 239
 240     // For every identifiable value, save Value pointer in knownValues[i]
 241     for (hash_map<Value*, DSNodeHandle>::const_iterator
 242            I = tdGraph.getScalarMap().begin(),
 243            E = tdGraph.getScalarMap().end(); I != E; ++I)
 244       if (isa<GlobalValue>(I->first) ||
 245           isa<Argument>(I->first) ||
 246           isa<LoadInst>(I->first) ||
 247           isa<AllocaInst>(I->first) ||
 248           isa<MallocInst>(I->first))
 249         {
 250           unsigned nodeId = fmrInfo.getNodeId(I->second.getNode());
 251           knownValues[nodeId].push_back(I->first);
 252         }
 253   }
 254
 255   void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const
 256   {
 257     assert(bv.size() == knownValues.size());
 258
 259     if (bv.none())
 260       { // No bits are set: just say so and return
 261         O << "\tNONE.\n";
 262         return;
 263       }
 264
 265     if (bv.all())
 266       { // All bits are set: just say so and return
 267         O << "\tALL GRAPH NODES.\n";
 268         return;
 269       }
 270
 271     for (unsigned i=0, N=bv.size(); i < N; ++i)
 272       if (bv.test(i))
 273         {
 274           O << "\tNode# " << i << " : ";
 275           if (! knownValues[i].empty())
 276             for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++)
 277               {
 278                 const Value* V = knownValues[i][j];
 279
 280                 if      (isa<GlobalValue>(V))  O << "(Global) ";
 281                 else if (isa<Argument>(V))     O << "(Target of FormalParm) ";
 282                 else if (isa<LoadInst>(V))     O << "(Target of LoadInst  ) ";
 283                 else if (isa<AllocaInst>(V))   O << "(Target of AllocaInst) ";
 284                 else if (isa<MallocInst>(V))   O << "(Target of MallocInst) ";
 285
 286                 if (V->hasName())             O << V->getName();
 287                 else if (isa<Instruction>(V)) O << *V;
 288                 else                          O << "(Value*) 0x" << (void*) V;
 289
 290                 O << std::string((j < NV-1)? "; " : "\n");
 291               }
 292           else
 293             tdGraph.getNodes()[i]->print(O, /*graph*/ NULL);
 294         }
 295   }
 296 };
 297
 298
 299 // Print the results of the pass.
 300 // Currently this just prints bit-vectors and is not very readable.
 301 //
 302 void FunctionModRefInfo::print(std::ostream &O) const
 303 {
 304   DSGraphPrintHelper DPH(*this);
 305
 306   O << "========== Mod/ref information for function "
 307     << F.getName() << "========== \n\n";
 308
 309   // First: Print Globals and Locals modified anywhere in the function.
 310   //
 311   O << "  -----Mod/Ref in the body of function " << F.getName()<< ":\n";
 312
 313   O << "    --Objects modified in the function body:\n";
 314   DPH.printValuesInBitVec(O, funcModRefInfo.getModSet());
 315
 316   O << "    --Objects referenced in the function body:\n";
 317   DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet());
 318
 319   O << "    --Mod and Ref vectors for the nodes listed above:\n";
 320   funcModRefInfo.print(O, "\t");
 321
 322   O << "\n";
 323
 324   // Second: Print Globals and Locals modified at each call site in function
 325   //
 326   for (std::map<const CallInst*, ModRefInfo*>::const_iterator
 327          CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end();
 328        CI != CE; ++CI)
 329     {
 330       O << "  ----Mod/Ref information for call site\n" << CI->first;
 331
 332       O << "    --Objects modified at call site:\n";
 333       DPH.printValuesInBitVec(O, CI->second->getModSet());
 334
 335       O << "    --Objects referenced at call site:\n";
 336       DPH.printValuesInBitVec(O, CI->second->getRefSet());
 337
 338       O << "    --Mod and Ref vectors for the nodes listed above:\n";
 339       CI->second->print(O, "\t");
 340
 341       O << "\n";
 342     }
 343
 344   O << "\n";
 345 }
 346
 347 void FunctionModRefInfo::dump() const
 348 {
 349   print(std::cerr);
 350 }
 351
 352
 353 //----------------------------------------------------------------------------
 354 // class IPModRef: An interprocedural pass that computes IP Mod/Ref info.
 355 //----------------------------------------------------------------------------
 356
 357 // Free the FunctionModRefInfo objects cached in funcToModRefInfoMap.
 358 //
 359 void IPModRef::releaseMemory()
 360 {
 361   for(std::map<const Function*, FunctionModRefInfo*>::iterator
 362         I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I)
 363     delete(I->second);
 364
 365   // Clear map so memory is not re-released if we are called again
 366   funcToModRefInfoMap.clear();
 367 }
 368
 369 // Run the "interprocedural" pass on each function.  This needs to do
 370 // NO real interprocedural work because all that has been done the
 371 // data structure analysis.
 372 //
 373 bool IPModRef::run(Module &theModule)
 374 {
 375   M = &theModule;
 376
 377   for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI)
 378     if (! FI->isExternal())
 379       getFuncInfo(*FI, /*computeIfMissing*/ true);
 380   return true;
 381 }
 382
 383
 384 FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func,
 385                                           bool computeIfMissing)
 386 {
 387   FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func];
 388   assert (funcInfo != NULL || computeIfMissing);
 389   if (funcInfo == NULL)
 390     { // Create a new FunctionModRefInfo object.
 391       // Clone the top-down graph and remove any dead nodes first, because
 392       // otherwise original and merged graphs will not match.
 393       // The memory for this graph clone will be freed by FunctionModRefInfo.
 394       DSGraph* funcTDGraph =
 395         new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func));
 396       funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 397
 398       funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert
 399       funcInfo->computeModRef(func);  // computes the mod/ref info
 400     }
 401   return *funcInfo;
 402 }
 403
 404 /// getBUDSGraph - This method returns the BU data structure graph for F through
 405 /// the use of the BUDataStructures object.
 406 ///
 407 const DSGraph &IPModRef::getBUDSGraph(const Function &F) {
 408   return getAnalysis<BUDataStructures>().getDSGraph(F);
 409 }
 410
 411
 412 // getAnalysisUsage - This pass requires top-down data structure graphs.
 413 // It modifies nothing.
 414 //
 415 void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const {
 416   AU.setPreservesAll();
 417   AU.addRequired<LocalDataStructures>();
 418   AU.addRequired<BUDataStructures>();
 419   AU.addRequired<TDDataStructures>();
 420 }
 421
 422
 423 void IPModRef::print(std::ostream &O) const
 424 {
 425   O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n";
 426
 427   for (std::map<const Function*, FunctionModRefInfo*>::const_iterator
 428          mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end();
 429        mapI != mapE; ++mapI)
 430     mapI->second->print(O);
 431
 432   O << "\n";
 433 }
 434
 435
 436 void IPModRef::dump() const
 437 {
 438   print(std::cerr);
 439 }