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