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