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