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