LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <vector>
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 { }
00061   };
00062 
00063   static RegisterAnalysis<DSGraphStats> Z("dsstats", "DS Graph Statistics");
00064 }
00065 
00066 static bool isIndirectCallee(Value *V) {
00067   if (isa<Function>(V)) return false;
00068 
00069   if (CastInst *CI = dyn_cast<CastInst>(V))
00070     return isIndirectCallee(CI->getOperand(0));
00071   return true;
00072 }
00073 
00074 
00075 void DSGraphStats::countCallees(const Function& F) {
00076   unsigned numIndirectCalls = 0, totalNumCallees = 0;
00077 
00078   const std::vector<DSCallSite> &callSites = TDGraph->getFunctionCalls();
00079   for (unsigned i = 0, N = callSites.size(); i != N; ++i)
00080     if (isIndirectCallee(callSites[i].getCallSite().getCalledValue())) {
00081       // This is an indirect function call
00082       const std::vector<GlobalValue*> &Callees =
00083         callSites[i].getCalleeNode()->getGlobals();
00084       if (Callees.size() > 0) {
00085         totalNumCallees  += Callees.size();
00086         ++numIndirectCalls;
00087       } else
00088         std::cerr << "WARNING: No callee in Function '" << F.getName()
00089                   << "' at call: \n"
00090                   << *callSites[i].getCallSite().getInstruction();
00091     }
00092   
00093   TotalNumCallees  += totalNumCallees;
00094   NumIndirectCalls += numIndirectCalls;
00095   
00096   if (numIndirectCalls)
00097     std::cout << "  In function " << F.getName() << ":  "
00098               << (totalNumCallees / (double) numIndirectCalls)
00099               << " average callees per indirect call\n";
00100 }
00101 
00102 DSNode *DSGraphStats::getNodeForValue(Value *V) {
00103   const DSGraph *G = TDGraph;
00104   if (isa<Constant>(V))
00105     G = TDGraph->getGlobalsGraph();
00106 
00107   const DSGraph::ScalarMapTy &ScalarMap = G->getScalarMap();
00108   DSGraph::ScalarMapTy::const_iterator I = ScalarMap.find(V);
00109   if (I != ScalarMap.end())
00110     return I->second.getNode();
00111   return 0;
00112 }
00113 
00114 bool DSGraphStats::isNodeForValueCollapsed(Value *V) {
00115   if (DSNode *N = getNodeForValue(V))
00116     return N->isNodeCompletelyFolded() || N->isIncomplete();
00117   return false;
00118 }
00119 
00120 void DSGraphStats::visitLoad(LoadInst &LI) {
00121   if (isNodeForValueCollapsed(LI.getOperand(0))) {
00122     NumUntypedMemAccesses++;
00123   } else {
00124     NumTypedMemAccesses++;
00125   }
00126 }
00127 
00128 void DSGraphStats::visitStore(StoreInst &SI) {
00129   if (isNodeForValueCollapsed(SI.getOperand(1))) {
00130     NumUntypedMemAccesses++;
00131   } else {
00132     NumTypedMemAccesses++;
00133   }
00134 }
00135 
00136 
00137 
00138 bool DSGraphStats::runOnFunction(Function& F) {
00139   TDGraph = &getAnalysis<TDDataStructures>().getDSGraph(F);
00140   countCallees(F);
00141   visit(F);
00142   return true;
00143 }