Home | History | Annotate | Download | only in Analysis 
      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 #define DEBUG_TYPE "profile-info"
     15 #include "llvm/Analysis/ProfileInfo.h"
     16 #include "llvm/ADT/SmallSet.h"
     17 #include "llvm/Analysis/Passes.h"
     18 #include "llvm/CodeGen/MachineBasicBlock.h"
     19 #include "llvm/CodeGen/MachineFunction.h"
     20 #include "llvm/Pass.h"
     21 #include "llvm/Support/CFG.h"
     22 #include <limits>
     23 #include <queue>
     24 #include <set>
     25 using namespace llvm;
     26 
     27 namespace llvm {
     28   template<> char ProfileInfoT<Function,BasicBlock>::ID = 0;
     29 }
     30 
     31 // Register the ProfileInfo interface, providing a nice name to refer to.
     32 INITIALIZE_ANALYSIS_GROUP(ProfileInfo, "Profile Information", NoProfileInfo)
     33 
     34 namespace llvm {
     35 
     36 template <>
     37 ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {}
     38 template <>
     39 ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {}
     40 
     41 template <>
     42 ProfileInfoT<Function, BasicBlock>::ProfileInfoT() {
     43   MachineProfile = 0;
     44 }
     45 template <>
     46 ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() {
     47   if (MachineProfile) delete MachineProfile;
     48 }
     49 
     50 template<>
     51 char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0;
     52 
     53 template<>
     54 const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1;
     55 
     56 template<> const
     57 double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1;
     58 
     59 template<> double
     60 ProfileInfoT<Function,BasicBlock>::getExecutionCount(const BasicBlock *BB) {
     61   std::map<const Function*, BlockCounts>::iterator J =
     62     BlockInformation.find(BB->getParent());
     63   if (J != BlockInformation.end()) {
     64     BlockCounts::iterator I = J->second.find(BB);
     65     if (I != J->second.end())
     66       return I->second;
     67   }
     68 
     69   double Count = MissingValue;
     70 
     71   const_pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
     72 
     73   // Are there zero predecessors of this block?
     74   if (PI == PE) {
     75     Edge e = getEdge(0, BB);
     76     Count = getEdgeWeight(e);
     77   } else {
     78     // Otherwise, if there are predecessors, the execution count of this block is
     79     // the sum of the edge frequencies from the incoming edges.
     80     std::set<const BasicBlock*> ProcessedPreds;
     81     Count = 0;
     82     for (; PI != PE; ++PI) {
     83       const BasicBlock *P = *PI;
     84       if (ProcessedPreds.insert(P).second) {
     85         double w = getEdgeWeight(getEdge(P, BB));
     86         if (w == MissingValue) {
     87           Count = MissingValue;
     88           break;
     89         }
     90         Count += w;
     91       }
     92     }
     93   }
     94 
     95   // If the predecessors did not suffice to get block weight, try successors.
     96   if (Count == MissingValue) {
     97 
     98     succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
     99 
    100     // Are there zero successors of this block?
    101     if (SI == SE) {
    102       Edge e = getEdge(BB,0);
    103       Count = getEdgeWeight(e);
    104     } else {
    105       std::set<const BasicBlock*> ProcessedSuccs;
    106       Count = 0;
    107       for (; SI != SE; ++SI)
    108         if (ProcessedSuccs.insert(*SI).second) {
    109           double w = getEdgeWeight(getEdge(BB, *SI));
    110           if (w == MissingValue) {
    111             Count = MissingValue;
    112             break;
    113           }
    114           Count += w;
    115         }
    116     }
    117   }
    118 
    119   if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
    120   return Count;
    121 }
    122 
    123 template<>
    124 double ProfileInfoT<MachineFunction, MachineBasicBlock>::
    125         getExecutionCount(const MachineBasicBlock *MBB) {
    126   std::map<const MachineFunction*, BlockCounts>::iterator J =
    127     BlockInformation.find(MBB->getParent());
    128   if (J != BlockInformation.end()) {
    129     BlockCounts::iterator I = J->second.find(MBB);
    130     if (I != J->second.end())
    131       return I->second;
    132   }
    133 
    134   return MissingValue;
    135 }
    136 
    137 template<>
    138 double ProfileInfoT<Function,BasicBlock>::getExecutionCount(const Function *F) {
    139   std::map<const Function*, double>::iterator J =
    140     FunctionInformation.find(F);
    141   if (J != FunctionInformation.end())
    142     return J->second;
    143 
    144   // isDeclaration() is checked here and not at start of function to allow
    145   // functions without a body still to have a execution count.
    146   if (F->isDeclaration()) return MissingValue;
    147 
    148   double Count = getExecutionCount(&F->getEntryBlock());
    149   if (Count != MissingValue) FunctionInformation[F] = Count;
    150   return Count;
    151 }
    152 
    153 template<>
    154 double ProfileInfoT<MachineFunction, MachineBasicBlock>::
    155         getExecutionCount(const MachineFunction *MF) {
    156   std::map<const MachineFunction*, double>::iterator J =
    157     FunctionInformation.find(MF);
    158   if (J != FunctionInformation.end())
    159     return J->second;
    160 
    161   double Count = getExecutionCount(&MF->front());
    162   if (Count != MissingValue) FunctionInformation[MF] = Count;
    163   return Count;
    164 }
    165 
    166 template<>
    167 void ProfileInfoT<Function,BasicBlock>::
    168         setExecutionCount(const BasicBlock *BB, double w) {
    169   DEBUG(dbgs() << "Creating Block " << BB->getName()
    170                << " (weight: " << format("%.20g",w) << ")\n");
    171   BlockInformation[BB->getParent()][BB] = w;
    172 }
    173 
    174 template<>
    175 void ProfileInfoT<MachineFunction, MachineBasicBlock>::
    176         setExecutionCount(const MachineBasicBlock *MBB, double w) {
    177   DEBUG(dbgs() << "Creating Block " << MBB->getBasicBlock()->getName()
    178                << " (weight: " << format("%.20g",w) << ")\n");
    179   BlockInformation[MBB->getParent()][MBB] = w;
    180 }
    181 
    182 template<>
    183 void ProfileInfoT<Function,BasicBlock>::addEdgeWeight(Edge e, double w) {
    184   double oldw = getEdgeWeight(e);
    185   assert (oldw != MissingValue && "Adding weight to Edge with no previous weight");
    186   DEBUG(dbgs() << "Adding to Edge " << e
    187                << " (new weight: " << format("%.20g",oldw + w) << ")\n");
    188   EdgeInformation[getFunction(e)][e] = oldw + w;
    189 }
    190 
    191 template<>
    192 void ProfileInfoT<Function,BasicBlock>::
    193         addExecutionCount(const BasicBlock *BB, double w) {
    194   double oldw = getExecutionCount(BB);
    195   assert (oldw != MissingValue && "Adding weight to Block with no previous weight");
    196   DEBUG(dbgs() << "Adding to Block " << BB->getName()
    197                << " (new weight: " << format("%.20g",oldw + w) << ")\n");
    198   BlockInformation[BB->getParent()][BB] = oldw + w;
    199 }
    200 
    201 template<>
    202 void ProfileInfoT<Function,BasicBlock>::removeBlock(const BasicBlock *BB) {
    203   std::map<const Function*, BlockCounts>::iterator J =
    204     BlockInformation.find(BB->getParent());
    205   if (J == BlockInformation.end()) return;
    206 
    207   DEBUG(dbgs() << "Deleting " << BB->getName() << "\n");
    208   J->second.erase(BB);
    209 }
    210 
    211 template<>
    212 void ProfileInfoT<Function,BasicBlock>::removeEdge(Edge e) {
    213   std::map<const Function*, EdgeWeights>::iterator J =
    214     EdgeInformation.find(getFunction(e));
    215   if (J == EdgeInformation.end()) return;
    216 
    217   DEBUG(dbgs() << "Deleting" << e << "\n");
    218   J->second.erase(e);
    219 }
    220 
    221 template<>
    222 void ProfileInfoT<Function,BasicBlock>::
    223         replaceEdge(const Edge &oldedge, const Edge &newedge) {
    224   double w;
    225   if ((w = getEdgeWeight(newedge)) == MissingValue) {
    226     w = getEdgeWeight(oldedge);
    227     DEBUG(dbgs() << "Replacing " << oldedge << " with " << newedge  << "\n");
    228   } else {
    229     w += getEdgeWeight(oldedge);
    230     DEBUG(dbgs() << "Adding " << oldedge << " to " << newedge  << "\n");
    231   }
    232   setEdgeWeight(newedge,w);
    233   removeEdge(oldedge);
    234 }
    235 
    236 template<>
    237 const BasicBlock *ProfileInfoT<Function,BasicBlock>::
    238         GetPath(const BasicBlock *Src, const BasicBlock *Dest,
    239                 Path &P, unsigned Mode) {
    240   const BasicBlock *BB = 0;
    241   bool hasFoundPath = false;
    242 
    243   std::queue<const BasicBlock *> BFS;
    244   BFS.push(Src);
    245 
    246   while(BFS.size() && !hasFoundPath) {
    247     BB = BFS.front();
    248     BFS.pop();
    249 
    250     succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
    251     if (Succ == End) {
    252       P[(const BasicBlock*)0] = BB;
    253       if (Mode & GetPathToExit) {
    254         hasFoundPath = true;
    255         BB = 0;
    256       }
    257     }
    258     for(;Succ != End; ++Succ) {
    259       if (P.find(*Succ) != P.end()) continue;
    260       Edge e = getEdge(BB,*Succ);
    261       if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue;
    262       P[*Succ] = BB;
    263       BFS.push(*Succ);
    264       if ((Mode & GetPathToDest) && *Succ == Dest) {
    265         hasFoundPath = true;
    266         BB = *Succ;
    267         break;
    268       }
    269       if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) {
    270         hasFoundPath = true;
    271         BB = *Succ;
    272         break;
    273       }
    274     }
    275   }
    276 
    277   return BB;
    278 }
    279 
    280 template<>
    281 void ProfileInfoT<Function,BasicBlock>::
    282         divertFlow(const Edge &oldedge, const Edge &newedge) {
    283   DEBUG(dbgs() << "Diverting " << oldedge << " via " << newedge );
    284 
    285   // First check if the old edge was taken, if not, just delete it...
    286   if (getEdgeWeight(oldedge) == 0) {
    287     removeEdge(oldedge);
    288     return;
    289   }
    290 
    291   Path P;
    292   P[newedge.first] = 0;
    293   P[newedge.second] = newedge.first;
    294   const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest);
    295 
    296   double w = getEdgeWeight (oldedge);
    297   DEBUG(dbgs() << ", Weight: " << format("%.20g",w) << "\n");
    298   do {
    299     const BasicBlock *Parent = P.find(BB)->second;
    300     Edge e = getEdge(Parent,BB);
    301     double oldw = getEdgeWeight(e);
    302     double oldc = getExecutionCount(e.first);
    303     setEdgeWeight(e, w+oldw);
    304     if (Parent != oldedge.first) {
    305       setExecutionCount(e.first, w+oldc);
    306     }
    307     BB = Parent;
    308   } while (BB != newedge.first);
    309   removeEdge(oldedge);
    310 }
    311 
    312 /// Replaces all occurrences of RmBB in the ProfilingInfo with DestBB.
    313 /// This checks all edges of the function the blocks reside in and replaces the
    314 /// occurrences of RmBB with DestBB.
    315 template<>
    316 void ProfileInfoT<Function,BasicBlock>::
    317         replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) {
    318   DEBUG(dbgs() << "Replacing " << RmBB->getName()
    319                << " with " << DestBB->getName() << "\n");
    320   const Function *F = DestBB->getParent();
    321   std::map<const Function*, EdgeWeights>::iterator J =
    322     EdgeInformation.find(F);
    323   if (J == EdgeInformation.end()) return;
    324 
    325   Edge e, newedge;
    326   bool erasededge = false;
    327   EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
    328   while(I != E) {
    329     e = (I++)->first;
    330     bool foundedge = false; bool eraseedge = false;
    331     if (e.first == RmBB) {
    332       if (e.second == DestBB) {
    333         eraseedge = true;
    334       } else {
    335         newedge = getEdge(DestBB, e.second);
    336         foundedge = true;
    337       }
    338     }
    339     if (e.second == RmBB) {
    340       if (e.first == DestBB) {
    341         eraseedge = true;
    342       } else {
    343         newedge = getEdge(e.first, DestBB);
    344         foundedge = true;
    345       }
    346     }
    347     if (foundedge) {
    348       replaceEdge(e, newedge);
    349     }
    350     if (eraseedge) {
    351       if (erasededge) {
    352         Edge newedge = getEdge(DestBB, DestBB);
    353         replaceEdge(e, newedge);
    354       } else {
    355         removeEdge(e);
    356         erasededge = true;
    357       }
    358     }
    359   }
    360 }
    361 
    362 /// Splits an edge in the ProfileInfo and redirects flow over NewBB.
    363 /// Since its possible that there is more than one edge in the CFG from FristBB
    364 /// to SecondBB its necessary to redirect the flow proporionally.
    365 template<>
    366 void ProfileInfoT<Function,BasicBlock>::splitEdge(const BasicBlock *FirstBB,
    367                                                   const BasicBlock *SecondBB,
    368                                                   const BasicBlock *NewBB,
    369                                                   bool MergeIdenticalEdges) {
    370   const Function *F = FirstBB->getParent();
    371   std::map<const Function*, EdgeWeights>::iterator J =
    372     EdgeInformation.find(F);
    373   if (J == EdgeInformation.end()) return;
    374 
    375   // Generate edges and read current weight.
    376   Edge e  = getEdge(FirstBB, SecondBB);
    377   Edge n1 = getEdge(FirstBB, NewBB);
    378   Edge n2 = getEdge(NewBB, SecondBB);
    379   EdgeWeights &ECs = J->second;
    380   double w = ECs[e];
    381 
    382   int succ_count = 0;
    383   if (!MergeIdenticalEdges) {
    384     // First count the edges from FristBB to SecondBB, if there is more than
    385     // one, only slice out a proporional part for NewBB.
    386     for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB);
    387         BBI != BBE; ++BBI) {
    388       if (*BBI == SecondBB) succ_count++;
    389     }
    390     // When the NewBB is completely new, increment the count by one so that
    391     // the counts are properly distributed.
    392     if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++;
    393   } else {
    394     // When the edges are merged anyway, then redirect all flow.
    395     succ_count = 1;
    396   }
    397 
    398   // We know now how many edges there are from FirstBB to SecondBB, reroute a
    399   // proportional part of the edge weight over NewBB.
    400   double neww = floor(w / succ_count);
    401   ECs[n1] += neww;
    402   ECs[n2] += neww;
    403   BlockInformation[F][NewBB] += neww;
    404   if (succ_count == 1) {
    405     ECs.erase(e);
    406   } else {
    407     ECs[e] -= neww;
    408   }
    409 }
    410 
    411 template<>
    412 void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *Old,
    413                                                    const BasicBlock* New) {
    414   const Function *F = Old->getParent();
    415   std::map<const Function*, EdgeWeights>::iterator J =
    416     EdgeInformation.find(F);
    417   if (J == EdgeInformation.end()) return;
    418 
    419   DEBUG(dbgs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n");
    420 
    421   std::set<Edge> Edges;
    422   for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end();
    423        ewi != ewe; ++ewi) {
    424     Edge old = ewi->first;
    425     if (old.first == Old) {
    426       Edges.insert(old);
    427     }
    428   }
    429   for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end();
    430        EI != EE; ++EI) {
    431     Edge newedge = getEdge(New, EI->second);
    432     replaceEdge(*EI, newedge);
    433   }
    434 
    435   double w = getExecutionCount(Old);
    436   setEdgeWeight(getEdge(Old, New), w);
    437   setExecutionCount(New, w);
    438 }
    439 
    440 template<>
    441 void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *BB,
    442                                                    const BasicBlock* NewBB,
    443                                                    BasicBlock *const *Preds,
    444                                                    unsigned NumPreds) {
    445   const Function *F = BB->getParent();
    446   std::map<const Function*, EdgeWeights>::iterator J =
    447     EdgeInformation.find(F);
    448   if (J == EdgeInformation.end()) return;
    449 
    450   DEBUG(dbgs() << "Splitting " << NumPreds << " Edges from " << BB->getName()
    451                << " to " << NewBB->getName() << "\n");
    452 
    453   // Collect weight that was redirected over NewBB.
    454   double newweight = 0;
    455 
    456   std::set<const BasicBlock *> ProcessedPreds;
    457   // For all requestes Predecessors.
    458   for (unsigned pred = 0; pred < NumPreds; ++pred) {
    459     const BasicBlock * Pred = Preds[pred];
    460     if (ProcessedPreds.insert(Pred).second) {
    461       // Create edges and read old weight.
    462       Edge oldedge = getEdge(Pred, BB);
    463       Edge newedge = getEdge(Pred, NewBB);
    464 
    465       // Remember how much weight was redirected.
    466       newweight += getEdgeWeight(oldedge);
    467 
    468       replaceEdge(oldedge,newedge);
    469     }
    470   }
    471 
    472   Edge newedge = getEdge(NewBB,BB);
    473   setEdgeWeight(newedge, newweight);
    474   setExecutionCount(NewBB, newweight);
    475 }
    476 
    477 template<>
    478 void ProfileInfoT<Function,BasicBlock>::transfer(const Function *Old,
    479                                                  const Function *New) {
    480   DEBUG(dbgs() << "Replacing Function " << Old->getName() << " with "
    481                << New->getName() << "\n");
    482   std::map<const Function*, EdgeWeights>::iterator J =
    483     EdgeInformation.find(Old);
    484   if(J != EdgeInformation.end()) {
    485     EdgeInformation[New] = J->second;
    486   }
    487   EdgeInformation.erase(Old);
    488   BlockInformation.erase(Old);
    489   FunctionInformation.erase(Old);
    490 }
    491 
    492 static double readEdgeOrRemember(ProfileInfo::Edge edge, double w,
    493                                  ProfileInfo::Edge &tocalc, unsigned &uncalc) {
    494   if (w == ProfileInfo::MissingValue) {
    495     tocalc = edge;
    496     uncalc++;
    497     return 0;
    498   } else {
    499     return w;
    500   }
    501 }
    502 
    503 template<>
    504 bool ProfileInfoT<Function,BasicBlock>::
    505         CalculateMissingEdge(const BasicBlock *BB, Edge &removed,
    506                              bool assumeEmptySelf) {
    507   Edge edgetocalc;
    508   unsigned uncalculated = 0;
    509 
    510   // collect weights of all incoming and outgoing edges, rememer edges that
    511   // have no value
    512   double incount = 0;
    513   SmallSet<const BasicBlock*,8> pred_visited;
    514   const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
    515   if (bbi==bbe) {
    516     Edge e = getEdge(0,BB);
    517     incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
    518   }
    519   for (;bbi != bbe; ++bbi) {
    520     if (pred_visited.insert(*bbi)) {
    521       Edge e = getEdge(*bbi,BB);
    522       incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
    523     }
    524   }
    525 
    526   double outcount = 0;
    527   SmallSet<const BasicBlock*,8> succ_visited;
    528   succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
    529   if (sbbi==sbbe) {
    530     Edge e = getEdge(BB,0);
    531     if (getEdgeWeight(e) == MissingValue) {
    532       double w = getExecutionCount(BB);
    533       if (w != MissingValue) {
    534         setEdgeWeight(e,w);
    535         removed = e;
    536       }
    537     }
    538     outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
    539   }
    540   for (;sbbi != sbbe; ++sbbi) {
    541     if (succ_visited.insert(*sbbi)) {
    542       Edge e = getEdge(BB,*sbbi);
    543       outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
    544     }
    545   }
    546 
    547   // if exactly one edge weight was missing, calculate it and remove it from
    548   // spanning tree
    549   if (uncalculated == 0 ) {
    550     return true;
    551   } else
    552   if (uncalculated == 1) {
    553     if (incount < outcount) {
    554       EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
    555     } else {
    556       EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
    557     }
    558     DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": "
    559                  << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
    560     removed = edgetocalc;
    561     return true;
    562   } else
    563   if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
    564     setEdgeWeight(edgetocalc, incount * 10);
    565     removed = edgetocalc;
    566     return true;
    567   } else {
    568     return false;
    569   }
    570 }
    571 
    572 static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) {
    573   double w = PI->getEdgeWeight(e);
    574   if (w != ProfileInfo::MissingValue) {
    575     calcw += w;
    576   } else {
    577     misscount.insert(e);
    578   }
    579 }
    580 
    581 template<>
    582 bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) {
    583   double inWeight = 0;
    584   std::set<Edge> inMissing;
    585   std::set<const BasicBlock*> ProcessedPreds;
    586   const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
    587   if (bbi == bbe) {
    588     readEdge(this,getEdge(0,BB),inWeight,inMissing);
    589   }
    590   for( ; bbi != bbe; ++bbi ) {
    591     if (ProcessedPreds.insert(*bbi).second) {
    592       readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
    593     }
    594   }
    595 
    596   double outWeight = 0;
    597   std::set<Edge> outMissing;
    598   std::set<const BasicBlock*> ProcessedSuccs;
    599   succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
    600   if (sbbi == sbbe)
    601     readEdge(this,getEdge(BB,0),outWeight,outMissing);
    602   for ( ; sbbi != sbbe; ++sbbi ) {
    603     if (ProcessedSuccs.insert(*sbbi).second) {
    604       readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
    605     }
    606   }
    607 
    608   double share;
    609   std::set<Edge>::iterator ei,ee;
    610   if (inMissing.size() == 0 && outMissing.size() > 0) {
    611     ei = outMissing.begin();
    612     ee = outMissing.end();
    613     share = inWeight/outMissing.size();
    614     setExecutionCount(BB,inWeight);
    615   } else
    616   if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
    617     ei = inMissing.begin();
    618     ee = inMissing.end();
    619     share = 0;
    620     setExecutionCount(BB,0);
    621   } else
    622   if (inMissing.size() == 0 && outMissing.size() == 0) {
    623     setExecutionCount(BB,outWeight);
    624     return true;
    625   } else {
    626     return false;
    627   }
    628   for ( ; ei != ee; ++ei ) {
    629     setEdgeWeight(*ei,share);
    630   }
    631   return true;
    632 }
    633 
    634 template<>
    635 void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
    636 //  if (getExecutionCount(&(F->getEntryBlock())) == 0) {
    637 //    for (Function::const_iterator FI = F->begin(), FE = F->end();
    638 //         FI != FE; ++FI) {
    639 //      const BasicBlock* BB = &(*FI);
    640 //      {
    641 //        const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    642 //        if (NBB == End) {
    643 //          setEdgeWeight(getEdge(0,BB),0);
    644 //        }
    645 //        for(;NBB != End; ++NBB) {
    646 //          setEdgeWeight(getEdge(*NBB,BB),0);
    647 //        }
    648 //      }
    649 //      {
    650 //        succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    651 //        if (NBB == End) {
    652 //          setEdgeWeight(getEdge(0,BB),0);
    653 //        }
    654 //        for(;NBB != End; ++NBB) {
    655 //          setEdgeWeight(getEdge(*NBB,BB),0);
    656 //        }
    657 //      }
    658 //    }
    659 //    return;
    660 //  }
    661   // The set of BasicBlocks that are still unvisited.
    662   std::set<const BasicBlock*> Unvisited;
    663 
    664   // The set of return edges (Edges with no successors).
    665   std::set<Edge> ReturnEdges;
    666   double ReturnWeight = 0;
    667 
    668   // First iterate over the whole function and collect:
    669   // 1) The blocks in this function in the Unvisited set.
    670   // 2) The return edges in the ReturnEdges set.
    671   // 3) The flow that is leaving the function already via return edges.
    672 
    673   // Data structure for searching the function.
    674   std::queue<const BasicBlock *> BFS;
    675   const BasicBlock *BB = &(F->getEntryBlock());
    676   BFS.push(BB);
    677   Unvisited.insert(BB);
    678 
    679   while (BFS.size()) {
    680     BB = BFS.front(); BFS.pop();
    681     succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    682     if (NBB == End) {
    683       Edge e = getEdge(BB,0);
    684       double w = getEdgeWeight(e);
    685       if (w == MissingValue) {
    686         // If the return edge has no value, try to read value from block.
    687         double bw = getExecutionCount(BB);
    688         if (bw != MissingValue) {
    689           setEdgeWeight(e,bw);
    690           ReturnWeight += bw;
    691         } else {
    692           // If both return edge and block provide no value, collect edge.
    693           ReturnEdges.insert(e);
    694         }
    695       } else {
    696         // If the return edge has a proper value, collect it.
    697         ReturnWeight += w;
    698       }
    699     }
    700     for (;NBB != End; ++NBB) {
    701       if (Unvisited.insert(*NBB).second) {
    702         BFS.push(*NBB);
    703       }
    704     }
    705   }
    706 
    707   while (Unvisited.size() > 0) {
    708     unsigned oldUnvisitedCount = Unvisited.size();
    709     bool FoundPath = false;
    710 
    711     // If there is only one edge left, calculate it.
    712     if (ReturnEdges.size() == 1) {
    713       ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
    714 
    715       Edge e = *ReturnEdges.begin();
    716       setEdgeWeight(e,ReturnWeight);
    717       setExecutionCount(e.first,ReturnWeight);
    718 
    719       Unvisited.erase(e.first);
    720       ReturnEdges.erase(e);
    721       continue;
    722     }
    723 
    724     // Calculate all blocks where only one edge is missing, this may also
    725     // resolve furhter return edges.
    726     std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
    727     while(FI != FE) {
    728       const BasicBlock *BB = *FI; ++FI;
    729       Edge e;
    730       if(CalculateMissingEdge(BB,e,true)) {
    731         if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
    732           setExecutionCount(BB,getExecutionCount(BB));
    733         }
    734         Unvisited.erase(BB);
    735         if (e.first != 0 && e.second == 0) {
    736           ReturnEdges.erase(e);
    737           ReturnWeight += getEdgeWeight(e);
    738         }
    739       }
    740     }
    741     if (oldUnvisitedCount > Unvisited.size()) continue;
    742 
    743     // Estimate edge weights by dividing the flow proportionally.
    744     FI = Unvisited.begin(), FE = Unvisited.end();
    745     while(FI != FE) {
    746       const BasicBlock *BB = *FI; ++FI;
    747       const BasicBlock *Dest = 0;
    748       bool AllEdgesHaveSameReturn = true;
    749       // Check each Successor, these must all end up in the same or an empty
    750       // return block otherwise its dangerous to do an estimation on them.
    751       for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
    752            Succ != End; ++Succ) {
    753         Path P;
    754         GetPath(*Succ, 0, P, GetPathToExit);
    755         if (Dest && Dest != P[(const BasicBlock*)0]) {
    756           AllEdgesHaveSameReturn = false;
    757         }
    758         Dest = P[(const BasicBlock*)0];
    759       }
    760       if (AllEdgesHaveSameReturn) {
    761         if(EstimateMissingEdges(BB)) {
    762           Unvisited.erase(BB);
    763           break;
    764         }
    765       }
    766     }
    767     if (oldUnvisitedCount > Unvisited.size()) continue;
    768 
    769     // Check if there is a path to an block that has a known value and redirect
    770     // flow accordingly.
    771     FI = Unvisited.begin(), FE = Unvisited.end();
    772     while(FI != FE && !FoundPath) {
    773       // Fetch path.
    774       const BasicBlock *BB = *FI; ++FI;
    775       Path P;
    776       const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
    777 
    778       // Calculate incoming flow.
    779       double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
    780       std::set<const BasicBlock *> Processed;
    781       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    782            NBB != End; ++NBB) {
    783         if (Processed.insert(*NBB).second) {
    784           Edge e = getEdge(*NBB, BB);
    785           double ew = getEdgeWeight(e);
    786           if (ew != MissingValue) {
    787             iw += ew;
    788             invalid++;
    789           } else {
    790             // If the path contains the successor, this means its a backedge,
    791             // do not count as missing.
    792             if (P.find(*NBB) == P.end())
    793               inmissing++;
    794           }
    795           incount++;
    796         }
    797       }
    798       if (inmissing == incount) continue;
    799       if (invalid == 0) continue;
    800 
    801       // Subtract (already) outgoing flow.
    802       Processed.clear();
    803       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    804            NBB != End; ++NBB) {
    805         if (Processed.insert(*NBB).second) {
    806           Edge e = getEdge(BB, *NBB);
    807           double ew = getEdgeWeight(e);
    808           if (ew != MissingValue) {
    809             iw -= ew;
    810           }
    811         }
    812       }
    813       if (iw < 0) continue;
    814 
    815       // Check the receiving end of the path if it can handle the flow.
    816       double ow = getExecutionCount(Dest);
    817       Processed.clear();
    818       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    819            NBB != End; ++NBB) {
    820         if (Processed.insert(*NBB).second) {
    821           Edge e = getEdge(BB, *NBB);
    822           double ew = getEdgeWeight(e);
    823           if (ew != MissingValue) {
    824             ow -= ew;
    825           }
    826         }
    827       }
    828       if (ow < 0) continue;
    829 
    830       // Determine how much flow shall be used.
    831       double ew = getEdgeWeight(getEdge(P[Dest],Dest));
    832       if (ew != MissingValue) {
    833         ew = ew<ow?ew:ow;
    834         ew = ew<iw?ew:iw;
    835       } else {
    836         if (inmissing == 0)
    837           ew = iw;
    838       }
    839 
    840       // Create flow.
    841       if (ew != MissingValue) {
    842         do {
    843           Edge e = getEdge(P[Dest],Dest);
    844           if (getEdgeWeight(e) == MissingValue) {
    845             setEdgeWeight(e,ew);
    846             FoundPath = true;
    847           }
    848           Dest = P[Dest];
    849         } while (Dest != BB);
    850       }
    851     }
    852     if (FoundPath) continue;
    853 
    854     // Calculate a block with self loop.
    855     FI = Unvisited.begin(), FE = Unvisited.end();
    856     while(FI != FE && !FoundPath) {
    857       const BasicBlock *BB = *FI; ++FI;
    858       bool SelfEdgeFound = false;
    859       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
    860            NBB != End; ++NBB) {
    861         if (*NBB == BB) {
    862           SelfEdgeFound = true;
    863           break;
    864         }
    865       }
    866       if (SelfEdgeFound) {
    867         Edge e = getEdge(BB,BB);
    868         if (getEdgeWeight(e) == MissingValue) {
    869           double iw = 0;
    870           std::set<const BasicBlock *> Processed;
    871           for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    872                NBB != End; ++NBB) {
    873             if (Processed.insert(*NBB).second) {
    874               Edge e = getEdge(*NBB, BB);
    875               double ew = getEdgeWeight(e);
    876               if (ew != MissingValue) {
    877                 iw += ew;
    878               }
    879             }
    880           }
    881           setEdgeWeight(e,iw * 10);
    882           FoundPath = true;
    883         }
    884       }
    885     }
    886     if (FoundPath) continue;
    887 
    888     // Determine backedges, set them to zero.
    889     FI = Unvisited.begin(), FE = Unvisited.end();
    890     while(FI != FE && !FoundPath) {
    891       const BasicBlock *BB = *FI; ++FI;
    892       const BasicBlock *Dest = 0;
    893       Path P;
    894       bool BackEdgeFound = false;
    895       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    896            NBB != End; ++NBB) {
    897         Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
    898         if (Dest == *NBB) {
    899           BackEdgeFound = true;
    900           break;
    901         }
    902       }
    903       if (BackEdgeFound) {
    904         Edge e = getEdge(Dest,BB);
    905         double w = getEdgeWeight(e);
    906         if (w == MissingValue) {
    907           setEdgeWeight(e,0);
    908           FoundPath = true;
    909         }
    910         do {
    911           Edge e = getEdge(P[Dest], Dest);
    912           double w = getEdgeWeight(e);
    913           if (w == MissingValue) {
    914             setEdgeWeight(e,0);
    915             FoundPath = true;
    916           }
    917           Dest = P[Dest];
    918         } while (Dest != BB);
    919       }
    920     }
    921     if (FoundPath) continue;
    922 
    923     // Channel flow to return block.
    924     FI = Unvisited.begin(), FE = Unvisited.end();
    925     while(FI != FE && !FoundPath) {
    926       const BasicBlock *BB = *FI; ++FI;
    927 
    928       Path P;
    929       const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
    930       Dest = P[(const BasicBlock*)0];
    931       if (!Dest) continue;
    932 
    933       if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
    934         // Calculate incoming flow.
    935         double iw = 0;
    936         std::set<const BasicBlock *> Processed;
    937         for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    938              NBB != End; ++NBB) {
    939           if (Processed.insert(*NBB).second) {
    940             Edge e = getEdge(*NBB, BB);
    941             double ew = getEdgeWeight(e);
    942             if (ew != MissingValue) {
    943               iw += ew;
    944             }
    945           }
    946         }
    947         do {
    948           Edge e = getEdge(P[Dest], Dest);
    949           double w = getEdgeWeight(e);
    950           if (w == MissingValue) {
    951             setEdgeWeight(e,iw);
    952             FoundPath = true;
    953           } else {
    954             assert(0 && "Edge should not have value already!");
    955           }
    956           Dest = P[Dest];
    957         } while (Dest != BB);
    958       }
    959     }
    960     if (FoundPath) continue;
    961 
    962     // Speculatively set edges to zero.
    963     FI = Unvisited.begin(), FE = Unvisited.end();
    964     while(FI != FE && !FoundPath) {
    965       const BasicBlock *BB = *FI; ++FI;
    966 
    967       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
    968            NBB != End; ++NBB) {
    969         Edge e = getEdge(*NBB,BB);
    970         double w = getEdgeWeight(e);
    971         if (w == MissingValue) {
    972           setEdgeWeight(e,0);
    973           FoundPath = true;
    974           break;
    975         }
    976       }
    977     }
    978     if (FoundPath) continue;
    979 
    980     errs() << "{";
    981     FI = Unvisited.begin(), FE = Unvisited.end();
    982     while(FI != FE) {
    983       const BasicBlock *BB = *FI; ++FI;
    984       dbgs() << BB->getName();
    985       if (FI != FE)
    986         dbgs() << ",";
    987     }
    988     errs() << "}";
    989 
    990     errs() << "ASSERT: could not repair function";
    991     assert(0 && "could not repair function");
    992   }
    993 
    994   EdgeWeights J = EdgeInformation[F];
    995   for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
    996     Edge e = EI->first;
    997 
    998     bool SuccFound = false;
    999     if (e.first != 0) {
   1000       succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
   1001       if (NBB == End) {
   1002         if (0 == e.second) {
   1003           SuccFound = true;
   1004         }
   1005       }
   1006       for (;NBB != End; ++NBB) {
   1007         if (*NBB == e.second) {
   1008           SuccFound = true;
   1009           break;
   1010         }
   1011       }
   1012       if (!SuccFound) {
   1013         removeEdge(e);
   1014       }
   1015     }
   1016   }
   1017 }
   1018 
   1019 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
   1020   return O << MF->getFunction()->getName() << "(MF)";
   1021 }
   1022 
   1023 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
   1024   return O << MBB->getBasicBlock()->getName() << "(MB)";
   1025 }
   1026 
   1027 raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
   1028   O << "(";
   1029 
   1030   if (E.first)
   1031     O << E.first;
   1032   else
   1033     O << "0";
   1034 
   1035   O << ",";
   1036 
   1037   if (E.second)
   1038     O << E.second;
   1039   else
   1040     O << "0";
   1041 
   1042   return O << ")";
   1043 }
   1044 
   1045 } // namespace llvm
   1046 
   1047 //===----------------------------------------------------------------------===//
   1048 //  NoProfile ProfileInfo implementation
   1049 //
   1050 
   1051 namespace {
   1052   struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
   1053     static char ID; // Class identification, replacement for typeinfo
   1054     NoProfileInfo() : ImmutablePass(ID) {
   1055       initializeNoProfileInfoPass(*PassRegistry::getPassRegistry());
   1056     }
   1057 
   1058     /// getAdjustedAnalysisPointer - This method is used when a pass implements
   1059     /// an analysis interface through multiple inheritance.  If needed, it
   1060     /// should override this to adjust the this pointer as needed for the
   1061     /// specified pass info.
   1062     virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
   1063       if (PI == &ProfileInfo::ID)
   1064         return (ProfileInfo*)this;
   1065       return this;
   1066     }
   1067 
   1068     virtual const char *getPassName() const {
   1069       return "NoProfileInfo";
   1070     }
   1071   };
   1072 }  // End of anonymous namespace
   1073 
   1074 char NoProfileInfo::ID = 0;
   1075 // Register this pass...
   1076 INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile",
   1077                    "No Profile Information", false, true, true)
   1078 
   1079 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }
   1080