lib/Analysis/IPA/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 Instruction*, 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].getCallSite());
 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(CallSite CS,
 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 = CS.getCalledFunction()) {
 127     if (F->isExternal())
 128       return 0;   // We cannot compute Mod/Ref info for this callsite...
 129   } else {
 130     // Eventually, should check here if any callee is external.
 131     // For now we are not handling this case anyway.
 132     std::cerr << "IP Mod/Ref indirect call not implemented yet: "
 133               << "Being conservative\n";
 134     return 0;   // We cannot compute Mod/Ref info for this callsite...
 135   }
 136
 137   // Step #1: Clone the top-down graph...
 138   DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap);
 139
 140   // Step #2: Clear Mod/Ref information...
 141   Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read));
 142
 143   // Step #3: clone the bottom up graphs for the callees into the caller graph
 144   if (Function *F = CS.getCalledFunction())
 145     {
 146       assert(!F->isExternal());
 147
 148       // Build up a DSCallSite for our invocation point here...
 149
 150       // If the call returns a value, make sure to merge the nodes...
 151       DSNodeHandle RetVal;
 152       if (DS::isPointerType(CS.getInstruction()->getType()))
 153         RetVal = Result->getNodeForValue(CS.getInstruction());
 154
 155       // Populate the arguments list...
 156       std::vector<DSNodeHandle> Args;
 157       for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
 158            I != E; ++I)
 159         if (DS::isPointerType((*I)->getType()))
 160           Args.push_back(Result->getNodeForValue(*I));
 161
 162       // Build the call site...
 163       DSCallSite CS(CS, RetVal, F, Args);
 164
 165       // Perform the merging now of the graph for the callee, which will
 166       // come with mod/ref bits set...
 167       Result->mergeInGraph(CS, *F, IPModRefObj.getBUDSGraph(*F),
 168                            DSGraph::StripAllocaBit
 169                            | DSGraph::DontCloneCallNodes
 170                            | DSGraph::DontCloneAuxCallNodes);
 171     }
 172   else
 173     assert(0 && "See error message");
 174
 175   // Remove dead nodes aggressively to match the caller's original graph.
 176   Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 177
 178   // Step #4: Return the clone + the mapping (by ref)
 179   return Result;
 180 }
 181
 182 // Compute Mod/Ref bit vectors for a single call site.
 183 // These are copies of the Read/Write flags from the nodes of
 184 // the graph produced by clearing all flags in the caller's TD graph
 185 // and then inlining the callee's BU graph into the caller's TD graph.
 186 //
 187 void
 188 FunctionModRefInfo::computeModRef(CallSite CS)
 189 {
 190   // Allocate the mod/ref info for the call site.  Bits automatically cleared.
 191   ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize());
 192   callSiteModRefInfo[CS.getInstruction()] = callModRefInfo;
 193
 194   // Get a copy of the graph for the callee with the callee inlined
 195   hash_map<const DSNode*, DSNodeHandle> NodeMap;
 196   DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap);
 197   if (!csgp)
 198     { // Callee's side effects are unknown: mark all nodes Mod and Ref.
 199       // Eventually this should only mark nodes visible to the callee, i.e.,
 200       // exclude stack variables not reachable from any outgoing argument
 201       // or any global.
 202       callModRefInfo->getModSet().set();
 203       callModRefInfo->getRefSet().set();
 204       return;
 205     }
 206
 207   // For all nodes in the graph, extract the mod/ref information
 208   const std::vector<DSNode*>& csgNodes = csgp->getNodes();
 209   const std::vector<DSNode*>& origNodes = funcTDGraph->getNodes();
 210   assert(csgNodes.size() == origNodes.size());
 211   for (unsigned i=0, N = origNodes.size(); i < N; ++i)
 212     {
 213       DSNode* csgNode = NodeMap[origNodes[i]].getNode();
 214       assert(csgNode && "Inlined and original graphs do not correspond!");
 215       if (csgNode->isModified())
 216         callModRefInfo->setNodeIsMod(getNodeId(origNodes[i]));
 217       if (csgNode->isRead())
 218         callModRefInfo->setNodeIsRef(getNodeId(origNodes[i]));
 219     }
 220
 221   // Drop nodemap before we delete the graph...
 222   NodeMap.clear();
 223   delete csgp;
 224 }
 225
 226
 227 class DSGraphPrintHelper {
 228   const DSGraph& tdGraph;
 229   std::vector<std::vector<const Value*> > knownValues; // identifiable objects
 230
 231 public:
 232   /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo)
 233     : tdGraph(fmrInfo.getFuncGraph())
 234   {
 235     knownValues.resize(tdGraph.getGraphSize());
 236
 237     // For every identifiable value, save Value pointer in knownValues[i]
 238     for (hash_map<Value*, DSNodeHandle>::const_iterator
 239            I = tdGraph.getScalarMap().begin(),
 240            E = tdGraph.getScalarMap().end(); I != E; ++I)
 241       if (isa<GlobalValue>(I->first) ||
 242           isa<Argument>(I->first) ||
 243           isa<LoadInst>(I->first) ||
 244           isa<AllocaInst>(I->first) ||
 245           isa<MallocInst>(I->first))
 246         {
 247           unsigned nodeId = fmrInfo.getNodeId(I->second.getNode());
 248           knownValues[nodeId].push_back(I->first);
 249         }
 250   }
 251
 252   void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const
 253   {
 254     assert(bv.size() == knownValues.size());
 255
 256     if (bv.none())
 257       { // No bits are set: just say so and return
 258         O << "\tNONE.\n";
 259         return;
 260       }
 261
 262     if (bv.all())
 263       { // All bits are set: just say so and return
 264         O << "\tALL GRAPH NODES.\n";
 265         return;
 266       }
 267
 268     for (unsigned i=0, N=bv.size(); i < N; ++i)
 269       if (bv.test(i))
 270         {
 271           O << "\tNode# " << i << " : ";
 272           if (! knownValues[i].empty())
 273             for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++)
 274               {
 275                 const Value* V = knownValues[i][j];
 276
 277                 if      (isa<GlobalValue>(V))  O << "(Global) ";
 278                 else if (isa<Argument>(V))     O << "(Target of FormalParm) ";
 279                 else if (isa<LoadInst>(V))     O << "(Target of LoadInst  ) ";
 280                 else if (isa<AllocaInst>(V))   O << "(Target of AllocaInst) ";
 281                 else if (isa<MallocInst>(V))   O << "(Target of MallocInst) ";
 282
 283                 if (V->hasName())             O << V->getName();
 284                 else if (isa<Instruction>(V)) O << *V;
 285                 else                          O << "(Value*) 0x" << (void*) V;
 286
 287                 O << std::string((j < NV-1)? "; " : "\n");
 288               }
 289           else
 290             tdGraph.getNodes()[i]->print(O, /*graph*/ NULL);
 291         }
 292   }
 293 };
 294
 295
 296 // Print the results of the pass.
 297 // Currently this just prints bit-vectors and is not very readable.
 298 //
 299 void FunctionModRefInfo::print(std::ostream &O) const
 300 {
 301   DSGraphPrintHelper DPH(*this);
 302
 303   O << "========== Mod/ref information for function "
 304     << F.getName() << "========== \n\n";
 305
 306   // First: Print Globals and Locals modified anywhere in the function.
 307   //
 308   O << "  -----Mod/Ref in the body of function " << F.getName()<< ":\n";
 309
 310   O << "    --Objects modified in the function body:\n";
 311   DPH.printValuesInBitVec(O, funcModRefInfo.getModSet());
 312
 313   O << "    --Objects referenced in the function body:\n";
 314   DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet());
 315
 316   O << "    --Mod and Ref vectors for the nodes listed above:\n";
 317   funcModRefInfo.print(O, "\t");
 318
 319   O << "\n";
 320
 321   // Second: Print Globals and Locals modified at each call site in function
 322   //
 323   for (std::map<const Instruction *, ModRefInfo*>::const_iterator
 324          CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end();
 325        CI != CE; ++CI)
 326     {
 327       O << "  ----Mod/Ref information for call site\n" << CI->first;
 328
 329       O << "    --Objects modified at call site:\n";
 330       DPH.printValuesInBitVec(O, CI->second->getModSet());
 331
 332       O << "    --Objects referenced at call site:\n";
 333       DPH.printValuesInBitVec(O, CI->second->getRefSet());
 334
 335       O << "    --Mod and Ref vectors for the nodes listed above:\n";
 336       CI->second->print(O, "\t");
 337
 338       O << "\n";
 339     }
 340
 341   O << "\n";
 342 }
 343
 344 void FunctionModRefInfo::dump() const
 345 {
 346   print(std::cerr);
 347 }
 348
 349
 350 //----------------------------------------------------------------------------
 351 // class IPModRef: An interprocedural pass that computes IP Mod/Ref info.
 352 //----------------------------------------------------------------------------
 353
 354 // Free the FunctionModRefInfo objects cached in funcToModRefInfoMap.
 355 //
 356 void IPModRef::releaseMemory()
 357 {
 358   for(std::map<const Function*, FunctionModRefInfo*>::iterator
 359         I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I)
 360     delete(I->second);
 361
 362   // Clear map so memory is not re-released if we are called again
 363   funcToModRefInfoMap.clear();
 364 }
 365
 366 // Run the "interprocedural" pass on each function.  This needs to do
 367 // NO real interprocedural work because all that has been done the
 368 // data structure analysis.
 369 //
 370 bool IPModRef::run(Module &theModule)
 371 {
 372   M = &theModule;
 373
 374   for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI)
 375     if (! FI->isExternal())
 376       getFuncInfo(*FI, /*computeIfMissing*/ true);
 377   return true;
 378 }
 379
 380
 381 FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func,
 382                                           bool computeIfMissing)
 383 {
 384   FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func];
 385   assert (funcInfo != NULL || computeIfMissing);
 386   if (funcInfo == NULL)
 387     { // Create a new FunctionModRefInfo object.
 388       // Clone the top-down graph and remove any dead nodes first, because
 389       // otherwise original and merged graphs will not match.
 390       // The memory for this graph clone will be freed by FunctionModRefInfo.
 391       DSGraph* funcTDGraph =
 392         new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func));
 393       funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 394
 395       funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert
 396       funcInfo->computeModRef(func);  // computes the mod/ref info
 397     }
 398   return *funcInfo;
 399 }
 400
 401 /// getBUDSGraph - This method returns the BU data structure graph for F through
 402 /// the use of the BUDataStructures object.
 403 ///
 404 const DSGraph &IPModRef::getBUDSGraph(const Function &F) {
 405   return getAnalysis<BUDataStructures>().getDSGraph(F);
 406 }
 407
 408
 409 // getAnalysisUsage - This pass requires top-down data structure graphs.
 410 // It modifies nothing.
 411 //
 412 void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const {
 413   AU.setPreservesAll();
 414   AU.addRequired<LocalDataStructures>();
 415   AU.addRequired<BUDataStructures>();
 416   AU.addRequired<TDDataStructures>();
 417 }
 418
 419
 420 void IPModRef::print(std::ostream &O) const
 421 {
 422   O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n";
 423
 424   for (std::map<const Function*, FunctionModRefInfo*>::const_iterator
 425          mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end();
 426        mapI != mapE; ++mapI)
 427     mapI->second->print(O);
 428
 429   O << "\n";
 430 }
 431
 432
 433 void IPModRef::dump() const
 434 {
 435   print(std::cerr);
 436 }