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/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   unsigned i = 0;
  67   for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
  68          E = funcTDGraph->node_end(); NI != E; ++NI)
  69     NodeIds[*NI] = i++;
  70 }
  71
  72
  73 FunctionModRefInfo::~FunctionModRefInfo()
  74 {
  75   for(std::map<const Instruction*, ModRefInfo*>::iterator
  76         I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I)
  77     delete(I->second);
  78
  79   // Empty map just to make problems easier to track down
  80   callSiteModRefInfo.clear();
  81
  82   delete funcTDGraph;
  83 }
  84
  85 unsigned FunctionModRefInfo::getNodeId(const Value* value) const {
  86   return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value))
  87                    .getNode());
  88 }
  89
  90
  91
  92 // Compute Mod/Ref bit vectors for the entire function.
  93 // These are simply copies of the Read/Write flags from the nodes of
  94 // the top-down DS graph.
  95 //
  96 void FunctionModRefInfo::computeModRef(const Function &func)
  97 {
  98   // Mark all nodes in the graph that are marked MOD as being mod
  99   // and all those marked REF as being ref.
 100   unsigned i = 0;
 101   for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
 102          E = funcTDGraph->node_end(); NI != E; ++NI, ++i) {
 103     if ((*NI)->isModified()) funcModRefInfo.setNodeIsMod(i);
 104     if ((*NI)->isRead())     funcModRefInfo.setNodeIsRef(i);
 105   }
 106
 107   // Compute the Mod/Ref info for all call sites within the function.
 108   // The call sites are recorded in the TD graph.
 109   const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls();
 110   for (unsigned i = 0, N = callSites.size(); i < N; ++i)
 111     computeModRef(callSites[i].getCallSite());
 112 }
 113
 114
 115 // ResolveCallSiteModRefInfo - This method performs the following actions:
 116 //
 117 //  1. It clones the top-down graph for the current function
 118 //  2. It clears all of the mod/ref bits in the cloned graph
 119 //  3. It then merges the bottom-up graph(s) for the specified call-site into
 120 //     the clone (bringing new mod/ref bits).
 121 //  4. It returns the clone, and a mapping of nodes from the original TDGraph to
 122 //     the cloned graph with Mod/Ref info for the callsite.
 123 //
 124 // NOTE: Because this clones a dsgraph and returns it, the caller is responsible
 125 //       for deleting the returned graph!
 126 // NOTE: This method may return a null pointer if it is unable to determine the
 127 //       requested information (because the call site calls an external
 128 //       function or we cannot determine the complete set of functions invoked).
 129 //
 130 DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallSite CS,
 131                                hash_map<const DSNode*, DSNodeHandle> &NodeMap)
 132 {
 133   // Step #0: Quick check if we are going to fail anyway: avoid
 134   // all the graph cloning and map copying in steps #1 and #2.
 135   //
 136   if (const Function *F = CS.getCalledFunction()) {
 137     if (F->isExternal())
 138       return 0;   // We cannot compute Mod/Ref info for this callsite...
 139   } else {
 140     // Eventually, should check here if any callee is external.
 141     // For now we are not handling this case anyway.
 142     std::cerr << "IP Mod/Ref indirect call not implemented yet: "
 143               << "Being conservative\n";
 144     return 0;   // We cannot compute Mod/Ref info for this callsite...
 145   }
 146
 147   // Step #1: Clone the top-down graph...
 148   DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap);
 149
 150   // Step #2: Clear Mod/Ref information...
 151   Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read));
 152
 153   // Step #3: clone the bottom up graphs for the callees into the caller graph
 154   if (Function *F = CS.getCalledFunction())
 155     {
 156       assert(!F->isExternal());
 157
 158       // Build up a DSCallSite for our invocation point here...
 159
 160       // If the call returns a value, make sure to merge the nodes...
 161       DSNodeHandle RetVal;
 162       if (DS::isPointerType(CS.getInstruction()->getType()))
 163         RetVal = Result->getNodeForValue(CS.getInstruction());
 164
 165       // Populate the arguments list...
 166       std::vector<DSNodeHandle> Args;
 167       for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
 168            I != E; ++I)
 169         if (DS::isPointerType((*I)->getType()))
 170           Args.push_back(Result->getNodeForValue(*I));
 171
 172       // Build the call site...
 173       DSCallSite NCS(CS, RetVal, F, Args);
 174
 175       // Perform the merging now of the graph for the callee, which will
 176       // come with mod/ref bits set...
 177       Result->mergeInGraph(NCS, *F, IPModRefObj.getBUDSGraph(*F),
 178                            DSGraph::StripAllocaBit
 179                            | DSGraph::DontCloneCallNodes
 180                            | DSGraph::DontCloneAuxCallNodes);
 181     }
 182   else
 183     assert(0 && "See error message");
 184
 185   // Remove dead nodes aggressively to match the caller's original graph.
 186   Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 187
 188   // Step #4: Return the clone + the mapping (by ref)
 189   return Result;
 190 }
 191
 192 // Compute Mod/Ref bit vectors for a single call site.
 193 // These are copies of the Read/Write flags from the nodes of
 194 // the graph produced by clearing all flags in the caller's TD graph
 195 // and then inlining the callee's BU graph into the caller's TD graph.
 196 //
 197 void
 198 FunctionModRefInfo::computeModRef(CallSite CS)
 199 {
 200   // Allocate the mod/ref info for the call site.  Bits automatically cleared.
 201   ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize());
 202   callSiteModRefInfo[CS.getInstruction()] = callModRefInfo;
 203
 204   // Get a copy of the graph for the callee with the callee inlined
 205   hash_map<const DSNode*, DSNodeHandle> NodeMap;
 206   DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap);
 207   if (!csgp)
 208     { // Callee's side effects are unknown: mark all nodes Mod and Ref.
 209       // Eventually this should only mark nodes visible to the callee, i.e.,
 210       // exclude stack variables not reachable from any outgoing argument
 211       // or any global.
 212       callModRefInfo->getModSet().set();
 213       callModRefInfo->getRefSet().set();
 214       return;
 215     }
 216
 217   // For all nodes in the graph, extract the mod/ref information
 218   for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
 219          E = funcTDGraph->node_end(); NI != E; ++NI) {
 220     DSNode* csgNode = NodeMap[*NI].getNode();
 221     assert(csgNode && "Inlined and original graphs do not correspond!");
 222     if (csgNode->isModified())
 223       callModRefInfo->setNodeIsMod(getNodeId(*NI));
 224     if (csgNode->isRead())
 225       callModRefInfo->setNodeIsRef(getNodeId(*NI));
 226   }
 227
 228   // Drop nodemap before we delete the graph...
 229   NodeMap.clear();
 230   delete csgp;
 231 }
 232
 233
 234 class DSGraphPrintHelper {
 235   const DSGraph& tdGraph;
 236   std::vector<std::vector<const Value*> > knownValues; // identifiable objects
 237
 238 public:
 239   /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo)
 240     : tdGraph(fmrInfo.getFuncGraph())
 241   {
 242     knownValues.resize(tdGraph.getGraphSize());
 243
 244     // For every identifiable value, save Value pointer in knownValues[i]
 245     for (hash_map<Value*, DSNodeHandle>::const_iterator
 246            I = tdGraph.getScalarMap().begin(),
 247            E = tdGraph.getScalarMap().end(); I != E; ++I)
 248       if (isa<GlobalValue>(I->first) ||
 249           isa<Argument>(I->first) ||
 250           isa<LoadInst>(I->first) ||
 251           isa<AllocaInst>(I->first) ||
 252           isa<MallocInst>(I->first))
 253         {
 254           unsigned nodeId = fmrInfo.getNodeId(I->second.getNode());
 255           knownValues[nodeId].push_back(I->first);
 256         }
 257   }
 258
 259   void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const
 260   {
 261     assert(bv.size() == knownValues.size());
 262
 263     if (bv.none())
 264       { // No bits are set: just say so and return
 265         O << "\tNONE.\n";
 266         return;
 267       }
 268
 269     if (bv.all())
 270       { // All bits are set: just say so and return
 271         O << "\tALL GRAPH NODES.\n";
 272         return;
 273       }
 274
 275     for (unsigned i=0, N=bv.size(); i < N; ++i)
 276       if (bv.test(i))
 277         {
 278           O << "\tNode# " << i << " : ";
 279           if (! knownValues[i].empty())
 280             for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++)
 281               {
 282                 const Value* V = knownValues[i][j];
 283
 284                 if      (isa<GlobalValue>(V))  O << "(Global) ";
 285                 else if (isa<Argument>(V))     O << "(Target of FormalParm) ";
 286                 else if (isa<LoadInst>(V))     O << "(Target of LoadInst  ) ";
 287                 else if (isa<AllocaInst>(V))   O << "(Target of AllocaInst) ";
 288                 else if (isa<MallocInst>(V))   O << "(Target of MallocInst) ";
 289
 290                 if (V->hasName())             O << V->getName();
 291                 else if (isa<Instruction>(V)) O << *V;
 292                 else                          O << "(Value*) 0x" << (void*) V;
 293
 294                 O << std::string((j < NV-1)? "; " : "\n");
 295               }
 296 #if 0
 297           else
 298             tdGraph.getNodes()[i]->print(O, /*graph*/ NULL);
 299 #endif
 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