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 "llvm/ADT/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 Module* = 0) const { }
  61   };
  62
  63   static RegisterAnalysis<DSGraphStats> Z("dsstats", "DS Graph Statistics");
  64 }
  65
  66 FunctionPass *llvm::createDataStructureStatsPass() {
  67   return new DSGraphStats();
  68 }
  69
  70
  71 static bool isIndirectCallee(Value *V) {
  72   if (isa<Function>(V)) return false;
  73
  74   if (CastInst *CI = dyn_cast<CastInst>(V))
  75     return isIndirectCallee(CI->getOperand(0));
  76   return true;
  77 }
  78
  79
  80 void DSGraphStats::countCallees(const Function& F) {
  81   unsigned numIndirectCalls = 0, totalNumCallees = 0;
  82
  83   for (DSGraph::fc_iterator I = TDGraph->fc_begin(), E = TDGraph->fc_end();
  84        I != E; ++I)
  85     if (isIndirectCallee(I->getCallSite().getCalledValue())) {
  86       // This is an indirect function call
  87       std::vector<Function*> Callees;
  88       I->getCalleeNode()->addFullFunctionList(Callees);
  89
  90       if (Callees.size() > 0) {
  91         totalNumCallees  += Callees.size();
  92         ++numIndirectCalls;
  93       } else
  94         std::cerr << "WARNING: No callee in Function '" << F.getName()
  95                   << "' at call: \n"
  96                   << *I->getCallSite().getInstruction();
  97     }
  98
  99   TotalNumCallees  += totalNumCallees;
 100   NumIndirectCalls += numIndirectCalls;
 101
 102   if (numIndirectCalls)
 103     std::cout << "  In function " << F.getName() << ":  "
 104               << (totalNumCallees / (double) numIndirectCalls)
 105               << " average callees per indirect call\n";
 106 }
 107
 108 DSNode *DSGraphStats::getNodeForValue(Value *V) {
 109   const DSGraph *G = TDGraph;
 110   if (isa<Constant>(V))
 111     G = TDGraph->getGlobalsGraph();
 112
 113   const DSGraph::ScalarMapTy &ScalarMap = G->getScalarMap();
 114   DSGraph::ScalarMapTy::const_iterator I = ScalarMap.find(V);
 115   if (I != ScalarMap.end())
 116     return I->second.getNode();
 117   return 0;
 118 }
 119
 120 bool DSGraphStats::isNodeForValueCollapsed(Value *V) {
 121   if (DSNode *N = getNodeForValue(V))
 122     return N->isNodeCompletelyFolded() || N->isIncomplete();
 123   return false;
 124 }
 125
 126 void DSGraphStats::visitLoad(LoadInst &LI) {
 127   if (isNodeForValueCollapsed(LI.getOperand(0))) {
 128     NumUntypedMemAccesses++;
 129   } else {
 130     NumTypedMemAccesses++;
 131   }
 132 }
 133
 134 void DSGraphStats::visitStore(StoreInst &SI) {
 135   if (isNodeForValueCollapsed(SI.getOperand(1))) {
 136     NumUntypedMemAccesses++;
 137   } else {
 138     NumTypedMemAccesses++;
 139   }
 140 }
 141
 142
 143
 144 bool DSGraphStats::runOnFunction(Function& F) {
 145   TDGraph = &getAnalysis<TDDataStructures>().getDSGraph(F);
 146   countCallees(F);
 147   visit(F);
 148   return true;
 149 }