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