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