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