Unbreak the build.
[oota-llvm.git] / 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(); }