LLVM API Documentation

DataStructureStats.cpp

Go to the documentation of this file.
00001 //===- DataStructureStats.cpp - Various statistics for DS Graphs ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines a little pass that prints out statistics for DS Graphs.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Analysis/DataStructure/DataStructure.h"
00015 #include "llvm/Analysis/DataStructure/DSGraph.h"
00016 #include "llvm/Function.h"
00017 #include "llvm/Instructions.h"
00018 #include "llvm/Pass.h"
00019 #include "llvm/Support/InstVisitor.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include <iostream>
00022 using namespace llvm;
00023 
00024 namespace {
00025   Statistic<> TotalNumCallees("totalcallees",
00026                 "Total number of callee functions at all indirect call sites");
00027   Statistic<> NumIndirectCalls("numindirect",
00028                 "Total number of indirect call sites in the program");
00029   Statistic<> NumPoolNodes("numpools",
00030                   "Number of allocation nodes that could be pool allocated");
00031 
00032   // Typed/Untyped memory accesses: If DSA can infer that the types the loads
00033   // and stores are accessing are correct (ie, the node has not been collapsed),
00034   // increment the appropriate counter.
00035   Statistic<> NumTypedMemAccesses("numtypedmemaccesses",
00036                                 "Number of loads/stores which are fully typed");
00037   Statistic<> NumUntypedMemAccesses("numuntypedmemaccesses",
00038                                 "Number of loads/stores which are untyped");
00039 
00040   class DSGraphStats : public FunctionPass, public InstVisitor<DSGraphStats> {
00041     void countCallees(const Function &F);
00042     const DSGraph *TDGraph;
00043 
00044     DSNode *getNodeForValue(Value *V);
00045     bool isNodeForValueCollapsed(Value *V);
00046   public:
00047     /// Driver functions to compute the Load/Store Dep. Graph per function.
00048     bool runOnFunction(Function& F);
00049 
00050     /// getAnalysisUsage - This modify nothing, and uses the Top-Down Graph.
00051     void getAnalysisUsage(AnalysisUsage &AU) const {
00052       AU.setPreservesAll();
00053       AU.addRequired<TDDataStructures>();
00054     }
00055 
00056     void visitLoad(LoadInst &LI);
00057     void visitStore(StoreInst &SI);
00058 
00059     /// Debugging support methods
00060     void print(std::ostream &O, const Module* = 0) const { }
00061   };
00062 
00063   static RegisterAnalysis<DSGraphStats> Z("dsstats", "DS Graph Statistics");
00064 }
00065 
00066 FunctionPass *llvm::createDataStructureStatsPass() { 
00067   return new DSGraphStats();
00068 }
00069 
00070 
00071 static bool isIndirectCallee(Value *V) {
00072   if (isa<Function>(V)) return false;
00073 
00074   if (CastInst *CI = dyn_cast<CastInst>(V))
00075     return isIndirectCallee(CI->getOperand(0));
00076   return true;
00077 }
00078 
00079 
00080 void DSGraphStats::countCallees(const Function& F) {
00081   unsigned numIndirectCalls = 0, totalNumCallees = 0;
00082 
00083   for (DSGraph::fc_iterator I = TDGraph->fc_begin(), E = TDGraph->fc_end();
00084        I != E; ++I)
00085     if (isIndirectCallee(I->getCallSite().getCalledValue())) {
00086       // This is an indirect function call
00087       std::vector<Function*> Callees;
00088       I->getCalleeNode()->addFullFunctionList(Callees);
00089 
00090       if (Callees.size() > 0) {
00091         totalNumCallees  += Callees.size();
00092         ++numIndirectCalls;
00093       } else
00094         std::cerr << "WARNING: No callee in Function '" << F.getName()
00095                   << "' at call: \n"
00096                   << *I->getCallSite().getInstruction();
00097     }
00098 
00099   TotalNumCallees  += totalNumCallees;
00100   NumIndirectCalls += numIndirectCalls;
00101 
00102   if (numIndirectCalls)
00103     std::cout << "  In function " << F.getName() << ":  "
00104               << (totalNumCallees / (double) numIndirectCalls)
00105               << " average callees per indirect call\n";
00106 }
00107 
00108 DSNode *DSGraphStats::getNodeForValue(Value *V) {
00109   const DSGraph *G = TDGraph;
00110   if (isa<Constant>(V))
00111     G = TDGraph->getGlobalsGraph();
00112 
00113   const DSGraph::ScalarMapTy &ScalarMap = G->getScalarMap();
00114   DSGraph::ScalarMapTy::const_iterator I = ScalarMap.find(V);
00115   if (I != ScalarMap.end())
00116     return I->second.getNode();
00117   return 0;
00118 }
00119 
00120 bool DSGraphStats::isNodeForValueCollapsed(Value *V) {
00121   if (DSNode *N = getNodeForValue(V))
00122     return N->isNodeCompletelyFolded() || N->isIncomplete();
00123   return false;
00124 }
00125 
00126 void DSGraphStats::visitLoad(LoadInst &LI) {
00127   if (isNodeForValueCollapsed(LI.getOperand(0))) {
00128     NumUntypedMemAccesses++;
00129   } else {
00130     NumTypedMemAccesses++;
00131   }
00132 }
00133 
00134 void DSGraphStats::visitStore(StoreInst &SI) {
00135   if (isNodeForValueCollapsed(SI.getOperand(1))) {
00136     NumUntypedMemAccesses++;
00137   } else {
00138     NumTypedMemAccesses++;
00139   }
00140 }
00141 
00142 
00143 
00144 bool DSGraphStats::runOnFunction(Function& F) {
00145   TDGraph = &getAnalysis<TDDataStructures>().getDSGraph(F);
00146   countCallees(F);
00147   visit(F);
00148   return true;
00149 }