lib/Analysis/DataStructure/DataStructureStats.cpp

   1 //===- DSGraphStats.cpp - Various statistics for DS Graphs ----------------===//
   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 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Analysis/DataStructure.h"
  13 #include "llvm/Analysis/DSGraph.h"
  14 #include "llvm/Function.h"
  15 #include "llvm/iOther.h"
  16 #include "llvm/iMemory.h"
  17 #include "llvm/Pass.h"
  18 #include "llvm/Support/InstVisitor.h"
  19 #include "Support/Statistic.h"
  20 #include <vector>
  21
  22 namespace {
  23   Statistic<> TotalNumCallees("totalcallees",
  24                 "Total number of callee functions at all indirect call sites");
  25   Statistic<> NumIndirectCalls("numindirect",
  26                 "Total number of indirect call sites in the program");
  27   Statistic<> NumPoolNodes("numpools",
  28                   "Number of allocation nodes that could be pool allocated");
  29
  30   // Typed/Untyped memory accesses: If DSA can infer that the types the loads
  31   // and stores are accessing are correct (ie, the node has not been collapsed),
  32   // increment the appropriate counter.
  33   Statistic<> NumTypedMemAccesses("numtypedmemaccesses",
  34                                 "Number of loads/stores which are fully typed");
  35   Statistic<> NumUntypedMemAccesses("numuntypedmemaccesses",
  36                                 "Number of loads/stores which are untyped");
  37
  38   class DSGraphStats : public FunctionPass, public InstVisitor<DSGraphStats> {
  39     void countCallees(const Function &F);
  40     const DSGraph *TDGraph;
  41
  42     DSNode *getNodeForValue(Value *V);
  43     bool isNodeForValueCollapsed(Value *V);
  44   public:
  45     /// Driver functions to compute the Load/Store Dep. Graph per function.
  46     bool runOnFunction(Function& F);
  47
  48     /// getAnalysisUsage - This modify nothing, and uses the Top-Down Graph.
  49     void getAnalysisUsage(AnalysisUsage &AU) const {
  50       AU.setPreservesAll();
  51       AU.addRequired<TDDataStructures>();
  52     }
  53
  54     void visitLoad(LoadInst &LI);
  55     void visitStore(StoreInst &SI);
  56
  57     /// Debugging support methods
  58     void print(std::ostream &O) const { }
  59   };
  60
  61   static RegisterAnalysis<DSGraphStats> Z("dsstats", "DS Graph Statistics");
  62 }
  63
  64 static bool isIndirectCallee(Value *V) {
  65   if (isa<Function>(V)) return false;
  66
  67   if (CastInst *CI = dyn_cast<CastInst>(V))
  68     return isIndirectCallee(CI->getOperand(0));
  69   return true;
  70 }
  71
  72
  73 void DSGraphStats::countCallees(const Function& F) {
  74   unsigned numIndirectCalls = 0, totalNumCallees = 0;
  75
  76   const std::vector<DSCallSite> &callSites = TDGraph->getFunctionCalls();
  77   for (unsigned i = 0, N = callSites.size(); i != N; ++i)
  78     if (isIndirectCallee(callSites[i].getCallSite().getCalledValue())) {
  79       // This is an indirect function call
  80       const std::vector<GlobalValue*> &Callees =
  81         callSites[i].getCalleeNode()->getGlobals();
  82       if (Callees.size() > 0) {
  83         totalNumCallees  += Callees.size();
  84         ++numIndirectCalls;
  85       } else
  86         std::cerr << "WARNING: No callee in Function '" << F.getName()
  87                   << "' at call: \n"
  88                   << *callSites[i].getCallSite().getInstruction();
  89     }
  90
  91   TotalNumCallees  += totalNumCallees;
  92   NumIndirectCalls += numIndirectCalls;
  93
  94   if (numIndirectCalls)
  95     std::cout << "  In function " << F.getName() << ":  "
  96               << (totalNumCallees / (double) numIndirectCalls)
  97               << " average callees per indirect call\n";
  98 }
  99
 100 DSNode *DSGraphStats::getNodeForValue(Value *V) {
 101   const DSGraph *G = TDGraph;
 102   if (isa<GlobalValue>(V) || isa<Constant>(V))
 103     G = TDGraph->getGlobalsGraph();
 104
 105   const DSGraph::ScalarMapTy &ScalarMap = G->getScalarMap();
 106   DSGraph::ScalarMapTy::const_iterator I = ScalarMap.find(V);
 107   if (I != ScalarMap.end())
 108     return I->second.getNode();
 109   return 0;
 110 }
 111
 112 bool DSGraphStats::isNodeForValueCollapsed(Value *V) {
 113   if (DSNode *N = getNodeForValue(V))
 114     return N->isNodeCompletelyFolded() || N->isIncomplete();
 115   return false;
 116 }
 117
 118 void DSGraphStats::visitLoad(LoadInst &LI) {
 119   if (isNodeForValueCollapsed(LI.getOperand(0))) {
 120     NumUntypedMemAccesses++;
 121   } else {
 122     NumTypedMemAccesses++;
 123   }
 124 }
 125
 126 void DSGraphStats::visitStore(StoreInst &SI) {
 127   if (isNodeForValueCollapsed(SI.getOperand(1))) {
 128     NumUntypedMemAccesses++;
 129   } else {
 130     NumTypedMemAccesses++;
 131   }
 132 }
 133
 134
 135
 136 bool DSGraphStats::runOnFunction(Function& F) {
 137   TDGraph = &getAnalysis<TDDataStructures>().getDSGraph(F);
 138   countCallees(F);
 139   visit(F);
 140   return true;
 141 }