lib/Analysis/ProfileInfoLoaderPass.cpp

   1 //===- ProfileInfoLoaderPass.cpp - LLVM Pass to load profile info ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a concrete implementation of profiling information that
  11 // loads the information from a profile dump file.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 #define DEBUG_TYPE "profile-loader"
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/InstrTypes.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/Analysis/Passes.h"
  20 #include "llvm/Analysis/ProfileInfo.h"
  21 #include "llvm/Analysis/ProfileInfoLoader.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/CFG.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/Support/Format.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/ADT/SmallSet.h"
  29 #include <set>
  30 using namespace llvm;
  31
  32 STATISTIC(NumEdgesRead, "The # of edges read.");
  33
  34 static cl::opt<std::string>
  35 ProfileInfoFilename("profile-info-file", cl::init("llvmprof.out"),
  36                     cl::value_desc("filename"),
  37                     cl::desc("Profile file loaded by -profile-loader"));
  38
  39 namespace {
  40   class LoaderPass : public ModulePass, public ProfileInfo {
  41     std::string Filename;
  42     std::set<Edge> SpanningTree;
  43     std::set<const BasicBlock*> BBisUnvisited;
  44     unsigned ReadCount;
  45   public:
  46     static char ID; // Class identification, replacement for typeinfo
  47     explicit LoaderPass(const std::string &filename = "")
  48       : ModulePass(&ID), Filename(filename) {
  49       if (filename.empty()) Filename = ProfileInfoFilename;
  50     }
  51
  52     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  53       AU.setPreservesAll();
  54     }
  55
  56     virtual const char *getPassName() const {
  57       return "Profiling information loader";
  58     }
  59
  60     // recurseBasicBlock() - Calculates the edge weights for as much basic
  61     // blocks as possbile.
  62     virtual void recurseBasicBlock(const BasicBlock *BB);
  63     virtual void readEdgeOrRemember(Edge, Edge&, unsigned &, unsigned &);
  64     virtual void readEdge(ProfileInfo::Edge, std::vector<unsigned>&);
  65
  66     /// run - Load the profile information from the specified file.
  67     virtual bool runOnModule(Module &M);
  68   };
  69 }  // End of anonymous namespace
  70
  71 char LoaderPass::ID = 0;
  72 static RegisterPass<LoaderPass>
  73 X("profile-loader", "Load profile information from llvmprof.out", false, true);
  74
  75 static RegisterAnalysisGroup<ProfileInfo> Y(X);
  76
  77 ModulePass *llvm::createProfileLoaderPass() { return new LoaderPass(); }
  78
  79 /// createProfileLoaderPass - This function returns a Pass that loads the
  80 /// profiling information for the module from the specified filename, making it
  81 /// available to the optimizers.
  82 Pass *llvm::createProfileLoaderPass(const std::string &Filename) {
  83   return new LoaderPass(Filename);
  84 }
  85
  86 void LoaderPass::readEdgeOrRemember(Edge edge, Edge &tocalc,
  87                                     unsigned &uncalc, unsigned &count) {
  88   double w;
  89   if ((w = getEdgeWeight(edge)) == MissingValue) {
  90     tocalc = edge;
  91     uncalc++;
  92   } else {
  93     count+=w;
  94   }
  95 }
  96
  97 // recurseBasicBlock - Visits all neighbours of a block and then tries to
  98 // calculate the missing edge values.
  99 void LoaderPass::recurseBasicBlock(const BasicBlock *BB) {
 100
 101   // break recursion if already visited
 102   if (BBisUnvisited.find(BB) == BBisUnvisited.end()) return;
 103   BBisUnvisited.erase(BB);
 104   if (!BB) return;
 105
 106   for (succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 107        bbi != bbe; ++bbi) {
 108     recurseBasicBlock(*bbi);
 109   }
 110   for (pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 111        bbi != bbe; ++bbi) {
 112     recurseBasicBlock(*bbi);
 113   }
 114
 115   Edge edgetocalc;
 116   unsigned uncalculated = 0;
 117
 118   // collect weights of all incoming and outgoing edges, rememer edges that
 119   // have no value
 120   unsigned incount = 0;
 121   SmallSet<const BasicBlock*,8> pred_visited;
 122   pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 123   if (bbi==bbe) {
 124     readEdgeOrRemember(getEdge(0, BB),edgetocalc,uncalculated,incount);
 125   }
 126   for (;bbi != bbe; ++bbi) {
 127     if (pred_visited.insert(*bbi)) {
 128       readEdgeOrRemember(getEdge(*bbi, BB),edgetocalc,uncalculated,incount);
 129     }
 130   }
 131
 132   unsigned outcount = 0;
 133   SmallSet<const BasicBlock*,8> succ_visited;
 134   succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
 135   if (sbbi==sbbe) {
 136     readEdgeOrRemember(getEdge(BB, 0),edgetocalc,uncalculated,outcount);
 137   }
 138   for (;sbbi != sbbe; ++sbbi) {
 139     if (succ_visited.insert(*sbbi)) {
 140       readEdgeOrRemember(getEdge(BB, *sbbi),edgetocalc,uncalculated,outcount);
 141     }
 142   }
 143
 144   // if exactly one edge weight was missing, calculate it and remove it from
 145   // spanning tree
 146   if (uncalculated == 1) {
 147     if (incount < outcount) {
 148       EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
 149     } else {
 150       EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
 151     }
 152     DEBUG(errs() << "--Calc Edge Counter for " << edgetocalc << ": "
 153                  << format("%g", getEdgeWeight(edgetocalc)) << "\n");
 154     SpanningTree.erase(edgetocalc);
 155   }
 156 }
 157
 158 void LoaderPass::readEdge(ProfileInfo::Edge e,
 159                           std::vector<unsigned> &ECs) {
 160   if (ReadCount < ECs.size()) {
 161     double weight = ECs[ReadCount++];
 162     if (weight != ProfileInfoLoader::Uncounted) {
 163       // Here the data realm changes from the unsigned of the file to the
 164       // double of the ProfileInfo. This conversion is save because we know
 165       // that everything thats representable in unsinged is also representable
 166       // in double.
 167       EdgeInformation[getFunction(e)][e] += (double)weight;
 168
 169       DEBUG(errs() << "--Read Edge Counter for " << e
 170                    << " (# "<< (ReadCount-1) << "): "
 171                    << (unsigned)getEdgeWeight(e) << "\n");
 172     } else {
 173       // This happens only if reading optimal profiling information, not when
 174       // reading regular profiling information.
 175       SpanningTree.insert(e);
 176     }
 177   }
 178 }
 179
 180 bool LoaderPass::runOnModule(Module &M) {
 181   ProfileInfoLoader PIL("profile-loader", Filename, M);
 182
 183   EdgeInformation.clear();
 184   std::vector<unsigned> Counters = PIL.getRawEdgeCounts();
 185   if (Counters.size() > 0) {
 186     ReadCount = 0;
 187     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 188       if (F->isDeclaration()) continue;
 189       DEBUG(errs()<<"Working on "<<F->getNameStr()<<"\n");
 190       readEdge(getEdge(0,&F->getEntryBlock()), Counters);
 191       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 192         TerminatorInst *TI = BB->getTerminator();
 193         for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
 194           readEdge(getEdge(BB,TI->getSuccessor(s)), Counters);
 195         }
 196       }
 197     }
 198     if (ReadCount != Counters.size()) {
 199       errs() << "WARNING: profile information is inconsistent with "
 200              << "the current program!\n";
 201     }
 202     NumEdgesRead = ReadCount;
 203   }
 204
 205   Counters = PIL.getRawOptimalEdgeCounts();
 206   if (Counters.size() > 0) {
 207     ReadCount = 0;
 208     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 209       if (F->isDeclaration()) continue;
 210       DEBUG(errs()<<"Working on "<<F->getNameStr()<<"\n");
 211       readEdge(getEdge(0,&F->getEntryBlock()), Counters);
 212       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 213         TerminatorInst *TI = BB->getTerminator();
 214         if (TI->getNumSuccessors() == 0) {
 215           readEdge(getEdge(BB,0), Counters);
 216         }
 217         for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
 218           readEdge(getEdge(BB,TI->getSuccessor(s)), Counters);
 219         }
 220       }
 221       while (SpanningTree.size() > 0) {
 222 #if 0
 223         unsigned size = SpanningTree.size();
 224 #endif
 225         BBisUnvisited.clear();
 226         for (std::set<Edge>::iterator ei = SpanningTree.begin(),
 227              ee = SpanningTree.end(); ei != ee; ++ei) {
 228           BBisUnvisited.insert(ei->first);
 229           BBisUnvisited.insert(ei->second);
 230         }
 231         while (BBisUnvisited.size() > 0) {
 232           recurseBasicBlock(*BBisUnvisited.begin());
 233         }
 234 #if 0
 235         if (SpanningTree.size() == size) {
 236           DEBUG(errs()<<"{");
 237           for (std::set<Edge>::iterator ei = SpanningTree.begin(),
 238                ee = SpanningTree.end(); ei != ee; ++ei) {
 239             DEBUG(errs()<<"("<<(ei->first?ei->first->getName():"0")<<","
 240                         <<(ei->second?ei->second->getName():"0")<<"),");
 241           }
 242           assert(0 && "No edge calculated!");
 243         }
 244 #endif
 245       }
 246     }
 247     if (ReadCount != Counters.size()) {
 248       errs() << "WARNING: profile information is inconsistent with "
 249              << "the current program!\n";
 250     }
 251     NumEdgesRead = ReadCount;
 252   }
 253
 254   BlockInformation.clear();
 255   Counters = PIL.getRawBlockCounts();
 256   if (Counters.size() > 0) {
 257     ReadCount = 0;
 258     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 259       if (F->isDeclaration()) continue;
 260       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 261         if (ReadCount < Counters.size())
 262           // Here the data realm changes from the unsigned of the file to the
 263           // double of the ProfileInfo. This conversion is save because we know
 264           // that everything thats representable in unsinged is also
 265           // representable in double.
 266           BlockInformation[F][BB] = (double)Counters[ReadCount++];
 267     }
 268     if (ReadCount != Counters.size()) {
 269       errs() << "WARNING: profile information is inconsistent with "
 270              << "the current program!\n";
 271     }
 272   }
 273
 274   FunctionInformation.clear();
 275   Counters = PIL.getRawFunctionCounts();
 276   if (Counters.size() > 0) {
 277     ReadCount = 0;
 278     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 279       if (F->isDeclaration()) continue;
 280       if (ReadCount < Counters.size())
 281         // Here the data realm changes from the unsigned of the file to the
 282         // double of the ProfileInfo. This conversion is save because we know
 283         // that everything thats representable in unsinged is also
 284         // representable in double.
 285         FunctionInformation[F] = (double)Counters[ReadCount++];
 286     }
 287     if (ReadCount != Counters.size()) {
 288       errs() << "WARNING: profile information is inconsistent with "
 289              << "the current program!\n";
 290     }
 291   }
 292
 293   return false;
 294 }