lib/Analysis/DataStructure/DataStructureStats.cpp

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