lib/Analysis/ProfileInfo.cpp

   1 //===- ProfileInfo.cpp - Profile Info Interface ---------------------------===//
   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 the abstract ProfileInfo interface, and the default
  11 // "no profile" implementation.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/Passes.h"
  16 #include "llvm/Analysis/ProfileInfo.h"
  17 #include "llvm/Pass.h"
  18 #include "llvm/Support/CFG.h"
  19 #include "llvm/Support/Compiler.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/Support/Format.h"
  23 #include <set>
  24 using namespace llvm;
  25
  26 // Register the ProfileInfo interface, providing a nice name to refer to.
  27 static RegisterAnalysisGroup<ProfileInfo> Z("Profile Information");
  28 char ProfileInfo::ID = 0;
  29
  30 ProfileInfo::~ProfileInfo() {}
  31
  32 const double ProfileInfo::MissingValue = -1;
  33
  34 double ProfileInfo::getExecutionCount(const BasicBlock *BB) {
  35   std::map<const Function*, BlockCounts>::iterator J =
  36     BlockInformation.find(BB->getParent());
  37   if (J != BlockInformation.end()) {
  38     BlockCounts::iterator I = J->second.find(BB);
  39     if (I != J->second.end())
  40       return I->second;
  41   }
  42
  43   pred_const_iterator PI = pred_begin(BB), PE = pred_end(BB);
  44
  45   // Are there zero predecessors of this block?
  46   if (PI == PE) {
  47     // If this is the entry block, look for the Null -> Entry edge.
  48     if (BB == &BB->getParent()->getEntryBlock())
  49       return getEdgeWeight(getEdge(0, BB));
  50     else
  51       return 0;   // Otherwise, this is a dead block.
  52   }
  53
  54   // Otherwise, if there are predecessors, the execution count of this block is
  55   // the sum of the edge frequencies from the incoming edges.
  56   std::set<const BasicBlock*> ProcessedPreds;
  57   double Count = 0;
  58   for (; PI != PE; ++PI)
  59     if (ProcessedPreds.insert(*PI).second) {
  60       double w = getEdgeWeight(getEdge(*PI, BB));
  61       if (w == MissingValue) {
  62         Count = MissingValue;
  63         break;
  64       }
  65       Count += w;
  66     }
  67
  68   if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
  69   return Count;
  70 }
  71
  72 double ProfileInfo::getExecutionCount(const Function *F) {
  73   std::map<const Function*, double>::iterator J =
  74     FunctionInformation.find(F);
  75   if (J != FunctionInformation.end())
  76     return J->second;
  77
  78   // isDeclaration() is checked here and not at start of function to allow
  79   // functions without a body still to have a execution count.
  80   if (F->isDeclaration()) return MissingValue;
  81
  82   double Count = getExecutionCount(&F->getEntryBlock());
  83   if (Count != MissingValue) FunctionInformation[F] = Count;
  84   return Count;
  85 }
  86
  87 /// Replaces all occurences of RmBB in the ProfilingInfo with DestBB.
  88 /// This checks all edges of the function the blocks reside in and replaces the
  89 /// occurences of RmBB with DestBB.
  90 void ProfileInfo::replaceAllUses(const BasicBlock *RmBB,
  91                                  const BasicBlock *DestBB) {
  92   DEBUG(errs() << "Replacing " << RmBB->getNameStr()
  93                << " with " << DestBB->getNameStr() << "\n");
  94   const Function *F = DestBB->getParent();
  95   std::map<const Function*, EdgeWeights>::iterator J =
  96     EdgeInformation.find(F);
  97   if (J == EdgeInformation.end()) return;
  98
  99   for (EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
 100        I != E; ++I) {
 101     Edge e = I->first;
 102     Edge newedge; bool foundedge = false;
 103     if (e.first == RmBB) {
 104       newedge = getEdge(DestBB, e.second);
 105       foundedge = true;
 106     }
 107     if (e.second == RmBB) {
 108       newedge = getEdge(e.first, DestBB);
 109       foundedge = true;
 110     }
 111     if (foundedge) {
 112       double w = getEdgeWeight(e);
 113       EdgeInformation[F][newedge] = w;
 114       DEBUG(errs() << "Replacing " << e << " with " << newedge  << "\n");
 115       J->second.erase(e);
 116     }
 117   }
 118 }
 119
 120 /// Splits an edge in the ProfileInfo and redirects flow over NewBB.
 121 /// Since its possible that there is more than one edge in the CFG from FristBB
 122 /// to SecondBB its necessary to redirect the flow proporionally.
 123 void ProfileInfo::splitEdge(const BasicBlock *FirstBB,
 124                             const BasicBlock *SecondBB,
 125                             const BasicBlock *NewBB,
 126                             bool MergeIdenticalEdges) {
 127   const Function *F = FirstBB->getParent();
 128   std::map<const Function*, EdgeWeights>::iterator J =
 129     EdgeInformation.find(F);
 130   if (J == EdgeInformation.end()) return;
 131
 132   // Generate edges and read current weight.
 133   Edge e  = getEdge(FirstBB, SecondBB);
 134   Edge n1 = getEdge(FirstBB, NewBB);
 135   Edge n2 = getEdge(NewBB, SecondBB);
 136   EdgeWeights &ECs = J->second;
 137   double w = ECs[e];
 138
 139   int succ_count = 0;
 140   if (!MergeIdenticalEdges) {
 141     // First count the edges from FristBB to SecondBB, if there is more than
 142     // one, only slice out a proporional part for NewBB.
 143     for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB);
 144         BBI != BBE; ++BBI) {
 145       if (*BBI == SecondBB) succ_count++;
 146     }
 147     // When the NewBB is completely new, increment the count by one so that
 148     // the counts are properly distributed.
 149     if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++;
 150   } else {
 151     // When the edges are merged anyway, then redirect all flow.
 152     succ_count = 1;
 153   }
 154
 155   // We know now how many edges there are from FirstBB to SecondBB, reroute a
 156   // proportional part of the edge weight over NewBB.
 157   double neww = w / succ_count;
 158   ECs[n1] += neww;
 159   ECs[n2] += neww;
 160   BlockInformation[F][NewBB] += neww;
 161   if (succ_count == 1) {
 162     ECs.erase(e);
 163   } else {
 164     ECs[e] -= neww;
 165   }
 166 }
 167
 168 raw_ostream& llvm::operator<<(raw_ostream &O, ProfileInfo::Edge E) {
 169   O << "(";
 170   O << (E.first ? E.first->getNameStr() : "0");
 171   O << ",";
 172   O << (E.second ? E.second->getNameStr() : "0");
 173   return O << ")";
 174 }
 175
 176 //===----------------------------------------------------------------------===//
 177 //  NoProfile ProfileInfo implementation
 178 //
 179
 180 namespace {
 181   struct VISIBILITY_HIDDEN NoProfileInfo
 182     : public ImmutablePass, public ProfileInfo {
 183     static char ID; // Class identification, replacement for typeinfo
 184     NoProfileInfo() : ImmutablePass(&ID) {}
 185   };
 186 }  // End of anonymous namespace
 187
 188 char NoProfileInfo::ID = 0;
 189 // Register this pass...
 190 static RegisterPass<NoProfileInfo>
 191 X("no-profile", "No Profile Information", false, true);
 192
 193 // Declare that we implement the ProfileInfo interface
 194 static RegisterAnalysisGroup<ProfileInfo, true> Y(X);
 195
 196 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }