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