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