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