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       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   const_pred_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   double inWeight = 0;
 581   std::set<Edge> inMissing;
 582   std::set<const BasicBlock*> ProcessedPreds;
 583   const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 584   if (bbi == bbe) {
 585     readEdge(this,getEdge(0,BB),inWeight,inMissing);
 586   }
 587   for( ; bbi != bbe; ++bbi ) {
 588     if (ProcessedPreds.insert(*bbi).second) {
 589       readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
 590     }
 591   }
 592
 593   double outWeight = 0;
 594   std::set<Edge> outMissing;
 595   std::set<const BasicBlock*> ProcessedSuccs;
 596   succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
 597   if (sbbi == sbbe)
 598     readEdge(this,getEdge(BB,0),outWeight,outMissing);
 599   for ( ; sbbi != sbbe; ++sbbi ) {
 600     if (ProcessedSuccs.insert(*sbbi).second) {
 601       readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
 602     }
 603   }
 604
 605   double share;
 606   std::set<Edge>::iterator ei,ee;
 607   if (inMissing.size() == 0 && outMissing.size() > 0) {
 608     ei = outMissing.begin();
 609     ee = outMissing.end();
 610     share = inWeight/outMissing.size();
 611     setExecutionCount(BB,inWeight);
 612   } else
 613   if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
 614     ei = inMissing.begin();
 615     ee = inMissing.end();
 616     share = 0;
 617     setExecutionCount(BB,0);
 618   } else
 619   if (inMissing.size() == 0 && outMissing.size() == 0) {
 620     setExecutionCount(BB,outWeight);
 621     return true;
 622   } else {
 623     return false;
 624   }
 625   for ( ; ei != ee; ++ei ) {
 626     setEdgeWeight(*ei,share);
 627   }
 628   return true;
 629 }
 630
 631 template<>
 632 void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
 633 //  if (getExecutionCount(&(F->getEntryBlock())) == 0) {
 634 //    for (Function::const_iterator FI = F->begin(), FE = F->end();
 635 //         FI != FE; ++FI) {
 636 //      const BasicBlock* BB = &(*FI);
 637 //      {
 638 //        const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 639 //        if (NBB == End) {
 640 //          setEdgeWeight(getEdge(0,BB),0);
 641 //        }
 642 //        for(;NBB != End; ++NBB) {
 643 //          setEdgeWeight(getEdge(*NBB,BB),0);
 644 //        }
 645 //      }
 646 //      {
 647 //        succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
 648 //        if (NBB == End) {
 649 //          setEdgeWeight(getEdge(0,BB),0);
 650 //        }
 651 //        for(;NBB != End; ++NBB) {
 652 //          setEdgeWeight(getEdge(*NBB,BB),0);
 653 //        }
 654 //      }
 655 //    }
 656 //    return;
 657 //  }
 658   // The set of BasicBlocks that are still unvisited.
 659   std::set<const BasicBlock*> Unvisited;
 660
 661   // The set of return edges (Edges with no successors).
 662   std::set<Edge> ReturnEdges;
 663   double ReturnWeight = 0;
 664
 665   // First iterate over the whole function and collect:
 666   // 1) The blocks in this function in the Unvisited set.
 667   // 2) The return edges in the ReturnEdges set.
 668   // 3) The flow that is leaving the function already via return edges.
 669
 670   // Data structure for searching the function.
 671   std::queue<const BasicBlock *> BFS;
 672   const BasicBlock *BB = &(F->getEntryBlock());
 673   BFS.push(BB);
 674   Unvisited.insert(BB);
 675
 676   while (BFS.size()) {
 677     BB = BFS.front(); BFS.pop();
 678     succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
 679     if (NBB == End) {
 680       Edge e = getEdge(BB,0);
 681       double w = getEdgeWeight(e);
 682       if (w == MissingValue) {
 683         // If the return edge has no value, try to read value from block.
 684         double bw = getExecutionCount(BB);
 685         if (bw != MissingValue) {
 686           setEdgeWeight(e,bw);
 687           ReturnWeight += bw;
 688         } else {
 689           // If both return edge and block provide no value, collect edge.
 690           ReturnEdges.insert(e);
 691         }
 692       } else {
 693         // If the return edge has a proper value, collect it.
 694         ReturnWeight += w;
 695       }
 696     }
 697     for (;NBB != End; ++NBB) {
 698       if (Unvisited.insert(*NBB).second) {
 699         BFS.push(*NBB);
 700       }
 701     }
 702   }
 703
 704   while (Unvisited.size() > 0) {
 705     unsigned oldUnvisitedCount = Unvisited.size();
 706     bool FoundPath = false;
 707
 708     // If there is only one edge left, calculate it.
 709     if (ReturnEdges.size() == 1) {
 710       ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
 711
 712       Edge e = *ReturnEdges.begin();
 713       setEdgeWeight(e,ReturnWeight);
 714       setExecutionCount(e.first,ReturnWeight);
 715
 716       Unvisited.erase(e.first);
 717       ReturnEdges.erase(e);
 718       continue;
 719     }
 720
 721     // Calculate all blocks where only one edge is missing, this may also
 722     // resolve furhter return edges.
 723     std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
 724     while(FI != FE) {
 725       const BasicBlock *BB = *FI; ++FI;
 726       Edge e;
 727       if(CalculateMissingEdge(BB,e,true)) {
 728         if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
 729           setExecutionCount(BB,getExecutionCount(BB));
 730         }
 731         Unvisited.erase(BB);
 732         if (e.first != 0 && e.second == 0) {
 733           ReturnEdges.erase(e);
 734           ReturnWeight += getEdgeWeight(e);
 735         }
 736       }
 737     }
 738     if (oldUnvisitedCount > Unvisited.size()) continue;
 739
 740     // Estimate edge weights by dividing the flow proportionally.
 741     FI = Unvisited.begin(), FE = Unvisited.end();
 742     while(FI != FE) {
 743       const BasicBlock *BB = *FI; ++FI;
 744       const BasicBlock *Dest = 0;
 745       bool AllEdgesHaveSameReturn = true;
 746       // Check each Successor, these must all end up in the same or an empty
 747       // return block otherwise its dangerous to do an estimation on them.
 748       for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
 749            Succ != End; ++Succ) {
 750         Path P;
 751         GetPath(*Succ, 0, P, GetPathToExit);
 752         if (Dest && Dest != P[0]) {
 753           AllEdgesHaveSameReturn = false;
 754         }
 755         Dest = P[0];
 756       }
 757       if (AllEdgesHaveSameReturn) {
 758         if(EstimateMissingEdges(BB)) {
 759           Unvisited.erase(BB);
 760           break;
 761         }
 762       }
 763     }
 764     if (oldUnvisitedCount > Unvisited.size()) continue;
 765
 766     // Check if there is a path to an block that has a known value and redirect
 767     // flow accordingly.
 768     FI = Unvisited.begin(), FE = Unvisited.end();
 769     while(FI != FE && !FoundPath) {
 770       // Fetch path.
 771       const BasicBlock *BB = *FI; ++FI;
 772       Path P;
 773       const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
 774
 775       // Calculate incoming flow.
 776       double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
 777       std::set<const BasicBlock *> Processed;
 778       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 779            NBB != End; ++NBB) {
 780         if (Processed.insert(*NBB).second) {
 781           Edge e = getEdge(*NBB, BB);
 782           double ew = getEdgeWeight(e);
 783           if (ew != MissingValue) {
 784             iw += ew;
 785             invalid++;
 786           } else {
 787             // If the path contains the successor, this means its a backedge,
 788             // do not count as missing.
 789             if (P.find(*NBB) == P.end())
 790               inmissing++;
 791           }
 792           incount++;
 793         }
 794       }
 795       if (inmissing == incount) continue;
 796       if (invalid == 0) continue;
 797
 798       // Subtract (already) outgoing flow.
 799       Processed.clear();
 800       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
 801            NBB != End; ++NBB) {
 802         if (Processed.insert(*NBB).second) {
 803           Edge e = getEdge(BB, *NBB);
 804           double ew = getEdgeWeight(e);
 805           if (ew != MissingValue) {
 806             iw -= ew;
 807           }
 808         }
 809       }
 810       if (iw < 0) continue;
 811
 812       // Check the recieving end of the path if it can handle the flow.
 813       double ow = getExecutionCount(Dest);
 814       Processed.clear();
 815       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
 816            NBB != End; ++NBB) {
 817         if (Processed.insert(*NBB).second) {
 818           Edge e = getEdge(BB, *NBB);
 819           double ew = getEdgeWeight(e);
 820           if (ew != MissingValue) {
 821             ow -= ew;
 822           }
 823         }
 824       }
 825       if (ow < 0) continue;
 826
 827       // Determine how much flow shall be used.
 828       double ew = getEdgeWeight(getEdge(P[Dest],Dest));
 829       if (ew != MissingValue) {
 830         ew = ew<ow?ew:ow;
 831         ew = ew<iw?ew:iw;
 832       } else {
 833         if (inmissing == 0)
 834           ew = iw;
 835       }
 836
 837       // Create flow.
 838       if (ew != MissingValue) {
 839         do {
 840           Edge e = getEdge(P[Dest],Dest);
 841           if (getEdgeWeight(e) == MissingValue) {
 842             setEdgeWeight(e,ew);
 843             FoundPath = true;
 844           }
 845           Dest = P[Dest];
 846         } while (Dest != BB);
 847       }
 848     }
 849     if (FoundPath) continue;
 850
 851     // Calculate a block with self loop.
 852     FI = Unvisited.begin(), FE = Unvisited.end();
 853     while(FI != FE && !FoundPath) {
 854       const BasicBlock *BB = *FI; ++FI;
 855       bool SelfEdgeFound = false;
 856       for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
 857            NBB != End; ++NBB) {
 858         if (*NBB == BB) {
 859           SelfEdgeFound = true;
 860           break;
 861         }
 862       }
 863       if (SelfEdgeFound) {
 864         Edge e = getEdge(BB,BB);
 865         if (getEdgeWeight(e) == MissingValue) {
 866           double iw = 0;
 867           std::set<const BasicBlock *> Processed;
 868           for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 869                NBB != End; ++NBB) {
 870             if (Processed.insert(*NBB).second) {
 871               Edge e = getEdge(*NBB, BB);
 872               double ew = getEdgeWeight(e);
 873               if (ew != MissingValue) {
 874                 iw += ew;
 875               }
 876             }
 877           }
 878           setEdgeWeight(e,iw * 10);
 879           FoundPath = true;
 880         }
 881       }
 882     }
 883     if (FoundPath) continue;
 884
 885     // Determine backedges, set them to zero.
 886     FI = Unvisited.begin(), FE = Unvisited.end();
 887     while(FI != FE && !FoundPath) {
 888       const BasicBlock *BB = *FI; ++FI;
 889       const BasicBlock *Dest;
 890       Path P;
 891       bool BackEdgeFound = false;
 892       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 893            NBB != End; ++NBB) {
 894         Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
 895         if (Dest == *NBB) {
 896           BackEdgeFound = true;
 897           break;
 898         }
 899       }
 900       if (BackEdgeFound) {
 901         Edge e = getEdge(Dest,BB);
 902         double w = getEdgeWeight(e);
 903         if (w == MissingValue) {
 904           setEdgeWeight(e,0);
 905           FoundPath = true;
 906         }
 907         do {
 908           Edge e = getEdge(P[Dest], Dest);
 909           double w = getEdgeWeight(e);
 910           if (w == MissingValue) {
 911             setEdgeWeight(e,0);
 912             FoundPath = true;
 913           }
 914           Dest = P[Dest];
 915         } while (Dest != BB);
 916       }
 917     }
 918     if (FoundPath) continue;
 919
 920     // Channel flow to return block.
 921     FI = Unvisited.begin(), FE = Unvisited.end();
 922     while(FI != FE && !FoundPath) {
 923       const BasicBlock *BB = *FI; ++FI;
 924
 925       Path P;
 926       const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
 927       Dest = P[0];
 928       if (!Dest) continue;
 929
 930       if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
 931         // Calculate incoming flow.
 932         double iw = 0;
 933         std::set<const BasicBlock *> Processed;
 934         for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 935              NBB != End; ++NBB) {
 936           if (Processed.insert(*NBB).second) {
 937             Edge e = getEdge(*NBB, BB);
 938             double ew = getEdgeWeight(e);
 939             if (ew != MissingValue) {
 940               iw += ew;
 941             }
 942           }
 943         }
 944         do {
 945           Edge e = getEdge(P[Dest], Dest);
 946           double w = getEdgeWeight(e);
 947           if (w == MissingValue) {
 948             setEdgeWeight(e,iw);
 949             FoundPath = true;
 950           } else {
 951             assert(0 && "Edge should not have value already!");
 952           }
 953           Dest = P[Dest];
 954         } while (Dest != BB);
 955       }
 956     }
 957     if (FoundPath) continue;
 958
 959     // Speculatively set edges to zero.
 960     FI = Unvisited.begin(), FE = Unvisited.end();
 961     while(FI != FE && !FoundPath) {
 962       const BasicBlock *BB = *FI; ++FI;
 963
 964       for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
 965            NBB != End; ++NBB) {
 966         Edge e = getEdge(*NBB,BB);
 967         double w = getEdgeWeight(e);
 968         if (w == MissingValue) {
 969           setEdgeWeight(e,0);
 970           FoundPath = true;
 971           break;
 972         }
 973       }
 974     }
 975     if (FoundPath) continue;
 976
 977     errs() << "{";
 978     FI = Unvisited.begin(), FE = Unvisited.end();
 979     while(FI != FE) {
 980       const BasicBlock *BB = *FI; ++FI;
 981       dbgs() << BB->getName();
 982       if (FI != FE)
 983         dbgs() << ",";
 984     }
 985     errs() << "}";
 986
 987     errs() << "ASSERT: could not repair function";
 988     assert(0 && "could not repair function");
 989   }
 990
 991   EdgeWeights J = EdgeInformation[F];
 992   for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
 993     Edge e = EI->first;
 994
 995     bool SuccFound = false;
 996     if (e.first != 0) {
 997       succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
 998       if (NBB == End) {
 999         if (0 == e.second) {
1000           SuccFound = true;
1001         }
1002       }
1003       for (;NBB != End; ++NBB) {
1004         if (*NBB == e.second) {
1005           SuccFound = true;
1006           break;
1007         }
1008       }
1009       if (!SuccFound) {
1010         removeEdge(e);
1011       }
1012     }
1013   }
1014 }
1015
1016 raw_ostream& operator<<(raw_ostream &O, const Function *F) {
1017   return O << F->getName();
1018 }
1019
1020 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1021   return O << MF->getFunction()->getName() << "(MF)";
1022 }
1023
1024 raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
1025   return O << BB->getName();
1026 }
1027
1028 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1029   return O << MBB->getBasicBlock()->getName() << "(MB)";
1030 }
1031
1032 raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
1033   O << "(";
1034
1035   if (E.first)
1036     O << E.first;
1037   else
1038     O << "0";
1039
1040   O << ",";
1041
1042   if (E.second)
1043     O << E.second;
1044   else
1045     O << "0";
1046
1047   return O << ")";
1048 }
1049
1050 raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1051   O << "(";
1052
1053   if (E.first)
1054     O << E.first;
1055   else
1056     O << "0";
1057
1058   O << ",";
1059
1060   if (E.second)
1061     O << E.second;
1062   else
1063     O << "0";
1064
1065   return O << ")";
1066 }
1067
1068 } // namespace llvm
1069
1070 //===----------------------------------------------------------------------===//
1071 //  NoProfile ProfileInfo implementation
1072 //
1073
1074 namespace {
1075   struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1076     static char ID; // Class identification, replacement for typeinfo
1077     NoProfileInfo() : ImmutablePass(&ID) {}
1078
1079     /// getAdjustedAnalysisPointer - This method is used when a pass implements
1080     /// an analysis interface through multiple inheritance.  If needed, it
1081     /// should override this to adjust the this pointer as needed for the
1082     /// specified pass info.
1083     virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
1084       if (PI->isPassID(&ProfileInfo::ID))
1085         return (ProfileInfo*)this;
1086       return this;
1087     }
1088
1089     virtual const char *getPassName() const {
1090       return "NoProfileInfo";
1091     }
1092   };
1093 }  // End of anonymous namespace
1094
1095 char NoProfileInfo::ID = 0;
1096 // Register this pass...
1097 static RegisterPass<NoProfileInfo>
1098 X("no-profile", "No Profile Information", false, true);
1099
1100 // Declare that we implement the ProfileInfo interface
1101 static RegisterAnalysisGroup<ProfileInfo, true> Y(X);
1102
1103 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }