lib/Analysis/DataStructure/IPModRef.cpp

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