ProfileInfo.cpp revision e6717d7ba653d2bafb7ce8f1750ee58513fbabad 
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>
25using namespace llvm;
26
27// Register the ProfileInfo interface, providing a nice name to refer to.
28static RegisterAnalysisGroup<ProfileInfo> Z("Profile Information");
29
30namespace llvm {
31
32template <>
33ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {}
34template <>
35ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {}
36
37template <>
38ProfileInfoT<Function, BasicBlock>::ProfileInfoT() {
39  MachineProfile = 0;
40}
41template <>
42ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() {
43  if (MachineProfile) delete MachineProfile;
44}
45
46template<>
47char ProfileInfoT<Function,BasicBlock>::ID = 0;
48
49template<>
50char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0;
51
52template<>
53const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1;
54
55template<> const
56double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1;
57
58template<> double
59ProfileInfoT<Function,BasicBlock>::getExecutionCount(const BasicBlock *BB) {
60  std::map<const Function*, BlockCounts>::iterator J =
61    BlockInformation.find(BB->getParent());
62  if (J != BlockInformation.end()) {
63    BlockCounts::iterator I = J->second.find(BB);
64    if (I != J->second.end())
65      return I->second;
66  }
67
68  double Count = MissingValue;
69
70  pred_const_iterator PI = pred_begin(BB), PE = pred_end(BB);
71
72  // Are there zero predecessors of this block?
73  if (PI == PE) {
74    Edge e = getEdge(0,BB);
75    Count = getEdgeWeight(e);
76  } else {
77    // Otherwise, if there are predecessors, the execution count of this block is
78    // the sum of the edge frequencies from the incoming edges.
79    std::set<const BasicBlock*> ProcessedPreds;
80    Count = 0;
81    for (; PI != PE; ++PI)
82      if (ProcessedPreds.insert(*PI).second) {
83        double w = getEdgeWeight(getEdge(*PI, BB));
84        if (w == MissingValue) {
85          Count = MissingValue;
86          break;
87        }
88        Count += w;
89      }
90  }
91
92  // If the predecessors did not suffice to get block weight, try successors.
93  if (Count == MissingValue) {
94
95    succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
96
97    // Are there zero successors of this block?
98    if (SI == SE) {
99      Edge e = getEdge(BB,0);
100      Count = getEdgeWeight(e);
101    } else {
102      std::set<const BasicBlock*> ProcessedSuccs;
103      Count = 0;
104      for (; SI != SE; ++SI)
105        if (ProcessedSuccs.insert(*SI).second) {
106          double w = getEdgeWeight(getEdge(BB, *SI));
107          if (w == MissingValue) {
108            Count = MissingValue;
109            break;
110          }
111          Count += w;
112        }
113    }
114  }
115
116  if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
117  return Count;
118}
119
120template<>
121double 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
134template<>
135double 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
150template<>
151double 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
163template<>
164void 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
171template<>
172void 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
179template<>
180void 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
188template<>
189void 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
198template<>
199void 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
208template<>
209void 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
218template<>
219void 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
233template<>
234const 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
277template<>
278void 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.
312template<>
313void 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.
362template<>
363void 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
408template<>
409void 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
437template<>
438void 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
474template<>
475void 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
489static 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
500template<>
501bool ProfileInfoT<Function,BasicBlock>::
502        CalculateMissingEdge(const BasicBlock *BB, Edge &removed,
503                             bool assumeEmptySelf) {
504  Edge edgetocalc;
505  unsigned uncalculated = 0;
506
507  // collect weights of all incoming and outgoing edges, rememer edges that
508  // have no value
509  double incount = 0;
510  SmallSet<const BasicBlock*,8> pred_visited;
511  pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
512  if (bbi==bbe) {
513    Edge e = getEdge(0,BB);
514    incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
515  }
516  for (;bbi != bbe; ++bbi) {
517    if (pred_visited.insert(*bbi)) {
518      Edge e = getEdge(*bbi,BB);
519      incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
520    }
521  }
522
523  double outcount = 0;
524  SmallSet<const BasicBlock*,8> succ_visited;
525  succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
526  if (sbbi==sbbe) {
527    Edge e = getEdge(BB,0);
528    if (getEdgeWeight(e) == MissingValue) {
529      double w = getExecutionCount(BB);
530      if (w != MissingValue) {
531        setEdgeWeight(e,w);
532        removed = e;
533      }
534    }
535    outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
536  }
537  for (;sbbi != sbbe; ++sbbi) {
538    if (succ_visited.insert(*sbbi)) {
539      Edge e = getEdge(BB,*sbbi);
540      outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
541    }
542  }
543
544  // if exactly one edge weight was missing, calculate it and remove it from
545  // spanning tree
546  if (uncalculated == 0 ) {
547    return true;
548  } else
549  if (uncalculated == 1) {
550    if (incount < outcount) {
551      EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
552    } else {
553      EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
554    }
555    DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": "
556                 << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
557    removed = edgetocalc;
558    return true;
559  } else
560  if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
561    setEdgeWeight(edgetocalc, incount * 10);
562    removed = edgetocalc;
563    return true;
564  } else {
565    return false;
566  }
567}
568
569static 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
578template<>
579bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) {
580  bool hasNoSuccessors = false;
581
582  double inWeight = 0;
583  std::set<Edge> inMissing;
584  std::set<const BasicBlock*> ProcessedPreds;
585  pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
586  if (bbi == bbe) {
587    readEdge(this,getEdge(0,BB),inWeight,inMissing);
588  }
589  for( ; bbi != bbe; ++bbi ) {
590    if (ProcessedPreds.insert(*bbi).second) {
591      readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
592    }
593  }
594
595  double outWeight = 0;
596  std::set<Edge> outMissing;
597  std::set<const BasicBlock*> ProcessedSuccs;
598  succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
599  if (sbbi == sbbe) {
600    readEdge(this,getEdge(BB,0),outWeight,outMissing);
601    hasNoSuccessors = true;
602  }
603  for ( ; sbbi != sbbe; ++sbbi ) {
604    if (ProcessedSuccs.insert(*sbbi).second) {
605      readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
606    }
607  }
608
609  double share;
610  std::set<Edge>::iterator ei,ee;
611  if (inMissing.size() == 0 && outMissing.size() > 0) {
612    ei = outMissing.begin();
613    ee = outMissing.end();
614    share = inWeight/outMissing.size();
615    setExecutionCount(BB,inWeight);
616  } else
617  if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
618    ei = inMissing.begin();
619    ee = inMissing.end();
620    share = 0;
621    setExecutionCount(BB,0);
622  } else
623  if (inMissing.size() == 0 && outMissing.size() == 0) {
624    setExecutionCount(BB,outWeight);
625    return true;
626  } else {
627    return false;
628  }
629  for ( ; ei != ee; ++ei ) {
630    setEdgeWeight(*ei,share);
631  }
632  return true;
633}
634
635template<>
636void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
637//  if (getExecutionCount(&(F->getEntryBlock())) == 0) {
638//    for (Function::const_iterator FI = F->begin(), FE = F->end();
639//         FI != FE; ++FI) {
640//      const BasicBlock* BB = &(*FI);
641//      {
642//        pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
643//        if (NBB == End) {
644//          setEdgeWeight(getEdge(0,BB),0);
645//        }
646//        for(;NBB != End; ++NBB) {
647//          setEdgeWeight(getEdge(*NBB,BB),0);
648//        }
649//      }
650//      {
651//        succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
652//        if (NBB == End) {
653//          setEdgeWeight(getEdge(0,BB),0);
654//        }
655//        for(;NBB != End; ++NBB) {
656//          setEdgeWeight(getEdge(*NBB,BB),0);
657//        }
658//      }
659//    }
660//    return;
661//  }
662  // The set of BasicBlocks that are still unvisited.
663  std::set<const BasicBlock*> Unvisited;
664
665  // The set of return edges (Edges with no successors).
666  std::set<Edge> ReturnEdges;
667  double ReturnWeight = 0;
668
669  // First iterate over the whole function and collect:
670  // 1) The blocks in this function in the Unvisited set.
671  // 2) The return edges in the ReturnEdges set.
672  // 3) The flow that is leaving the function already via return edges.
673
674  // Data structure for searching the function.
675  std::queue<const BasicBlock *> BFS;
676  const BasicBlock *BB = &(F->getEntryBlock());
677  BFS.push(BB);
678  Unvisited.insert(BB);
679
680  while (BFS.size()) {
681    BB = BFS.front(); BFS.pop();
682    succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
683    if (NBB == End) {
684      Edge e = getEdge(BB,0);
685      double w = getEdgeWeight(e);
686      if (w == MissingValue) {
687        // If the return edge has no value, try to read value from block.
688        double bw = getExecutionCount(BB);
689        if (bw != MissingValue) {
690          setEdgeWeight(e,bw);
691          ReturnWeight += bw;
692        } else {
693          // If both return edge and block provide no value, collect edge.
694          ReturnEdges.insert(e);
695        }
696      } else {
697        // If the return edge has a proper value, collect it.
698        ReturnWeight += w;
699      }
700    }
701    for (;NBB != End; ++NBB) {
702      if (Unvisited.insert(*NBB).second) {
703        BFS.push(*NBB);
704      }
705    }
706  }
707
708  while (Unvisited.size() > 0) {
709    unsigned oldUnvisitedCount = Unvisited.size();
710    bool FoundPath = false;
711
712    // If there is only one edge left, calculate it.
713    if (ReturnEdges.size() == 1) {
714      ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
715
716      Edge e = *ReturnEdges.begin();
717      setEdgeWeight(e,ReturnWeight);
718      setExecutionCount(e.first,ReturnWeight);
719
720      Unvisited.erase(e.first);
721      ReturnEdges.erase(e);
722      continue;
723    }
724
725    // Calculate all blocks where only one edge is missing, this may also
726    // resolve furhter return edges.
727    std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
728    while(FI != FE) {
729      const BasicBlock *BB = *FI; ++FI;
730      Edge e;
731      if(CalculateMissingEdge(BB,e,true)) {
732        if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
733          setExecutionCount(BB,getExecutionCount(BB));
734        }
735        Unvisited.erase(BB);
736        if (e.first != 0 && e.second == 0) {
737          ReturnEdges.erase(e);
738          ReturnWeight += getEdgeWeight(e);
739        }
740      }
741    }
742    if (oldUnvisitedCount > Unvisited.size()) continue;
743
744    // Estimate edge weights by dividing the flow proportionally.
745    FI = Unvisited.begin(), FE = Unvisited.end();
746    while(FI != FE) {
747      const BasicBlock *BB = *FI; ++FI;
748      const BasicBlock *Dest = 0;
749      bool AllEdgesHaveSameReturn = true;
750      // Check each Successor, these must all end up in the same or an empty
751      // return block otherwise its dangerous to do an estimation on them.
752      for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
753           Succ != End; ++Succ) {
754        Path P;
755        GetPath(*Succ, 0, P, GetPathToExit);
756        if (Dest && Dest != P[0]) {
757          AllEdgesHaveSameReturn = false;
758        }
759        Dest = P[0];
760      }
761      if (AllEdgesHaveSameReturn) {
762        if(EstimateMissingEdges(BB)) {
763          Unvisited.erase(BB);
764          break;
765        }
766      }
767    }
768    if (oldUnvisitedCount > Unvisited.size()) continue;
769
770    // Check if there is a path to an block that has a known value and redirect
771    // flow accordingly.
772    FI = Unvisited.begin(), FE = Unvisited.end();
773    while(FI != FE && !FoundPath) {
774      // Fetch path.
775      const BasicBlock *BB = *FI; ++FI;
776      Path P;
777      const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
778
779      // Calculate incoming flow.
780      double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
781      std::set<const BasicBlock *> Processed;
782      for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
783           NBB != End; ++NBB) {
784        if (Processed.insert(*NBB).second) {
785          Edge e = getEdge(*NBB, BB);
786          double ew = getEdgeWeight(e);
787          if (ew != MissingValue) {
788            iw += ew;
789            invalid++;
790          } else {
791            // If the path contains the successor, this means its a backedge,
792            // do not count as missing.
793            if (P.find(*NBB) == P.end())
794              inmissing++;
795          }
796          incount++;
797        }
798      }
799      if (inmissing == incount) continue;
800      if (invalid == 0) continue;
801
802      // Subtract (already) outgoing flow.
803      Processed.clear();
804      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
805           NBB != End; ++NBB) {
806        if (Processed.insert(*NBB).second) {
807          Edge e = getEdge(BB, *NBB);
808          double ew = getEdgeWeight(e);
809          if (ew != MissingValue) {
810            iw -= ew;
811          }
812        }
813      }
814      if (iw < 0) continue;
815
816      // Check the recieving end of the path if it can handle the flow.
817      double ow = getExecutionCount(Dest);
818      Processed.clear();
819      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
820           NBB != End; ++NBB) {
821        if (Processed.insert(*NBB).second) {
822          Edge e = getEdge(BB, *NBB);
823          double ew = getEdgeWeight(e);
824          if (ew != MissingValue) {
825            ow -= ew;
826          }
827        }
828      }
829      if (ow < 0) continue;
830
831      // Determine how much flow shall be used.
832      double ew = getEdgeWeight(getEdge(P[Dest],Dest));
833      if (ew != MissingValue) {
834        ew = ew<ow?ew:ow;
835        ew = ew<iw?ew:iw;
836      } else {
837        if (inmissing == 0)
838          ew = iw;
839      }
840
841      // Create flow.
842      if (ew != MissingValue) {
843        do {
844          Edge e = getEdge(P[Dest],Dest);
845          if (getEdgeWeight(e) == MissingValue) {
846            setEdgeWeight(e,ew);
847            FoundPath = true;
848          }
849          Dest = P[Dest];
850        } while (Dest != BB);
851      }
852    }
853    if (FoundPath) continue;
854
855    // Calculate a block with self loop.
856    FI = Unvisited.begin(), FE = Unvisited.end();
857    while(FI != FE && !FoundPath) {
858      const BasicBlock *BB = *FI; ++FI;
859      bool SelfEdgeFound = false;
860      for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
861           NBB != End; ++NBB) {
862        if (*NBB == BB) {
863          SelfEdgeFound = true;
864          break;
865        }
866      }
867      if (SelfEdgeFound) {
868        Edge e = getEdge(BB,BB);
869        if (getEdgeWeight(e) == MissingValue) {
870          double iw = 0;
871          std::set<const BasicBlock *> Processed;
872          for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
873               NBB != End; ++NBB) {
874            if (Processed.insert(*NBB).second) {
875              Edge e = getEdge(*NBB, BB);
876              double ew = getEdgeWeight(e);
877              if (ew != MissingValue) {
878                iw += ew;
879              }
880            }
881          }
882          setEdgeWeight(e,iw * 10);
883          FoundPath = true;
884        }
885      }
886    }
887    if (FoundPath) continue;
888
889    // Determine backedges, set them to zero.
890    FI = Unvisited.begin(), FE = Unvisited.end();
891    while(FI != FE && !FoundPath) {
892      const BasicBlock *BB = *FI; ++FI;
893      const BasicBlock *Dest;
894      Path P;
895      bool BackEdgeFound = false;
896      for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
897           NBB != End; ++NBB) {
898        Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
899        if (Dest == *NBB) {
900          BackEdgeFound = true;
901          break;
902        }
903      }
904      if (BackEdgeFound) {
905        Edge e = getEdge(Dest,BB);
906        double w = getEdgeWeight(e);
907        if (w == MissingValue) {
908          setEdgeWeight(e,0);
909          FoundPath = true;
910        }
911        do {
912          Edge e = getEdge(P[Dest], Dest);
913          double w = getEdgeWeight(e);
914          if (w == MissingValue) {
915            setEdgeWeight(e,0);
916            FoundPath = true;
917          }
918          Dest = P[Dest];
919        } while (Dest != BB);
920      }
921    }
922    if (FoundPath) continue;
923
924    // Channel flow to return block.
925    FI = Unvisited.begin(), FE = Unvisited.end();
926    while(FI != FE && !FoundPath) {
927      const BasicBlock *BB = *FI; ++FI;
928
929      Path P;
930      const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
931      Dest = P[0];
932      if (!Dest) continue;
933
934      if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
935        // Calculate incoming flow.
936        double iw = 0;
937        std::set<const BasicBlock *> Processed;
938        for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
939             NBB != End; ++NBB) {
940          if (Processed.insert(*NBB).second) {
941            Edge e = getEdge(*NBB, BB);
942            double ew = getEdgeWeight(e);
943            if (ew != MissingValue) {
944              iw += ew;
945            }
946          }
947        }
948        do {
949          Edge e = getEdge(P[Dest], Dest);
950          double w = getEdgeWeight(e);
951          if (w == MissingValue) {
952            setEdgeWeight(e,iw);
953            FoundPath = true;
954          } else {
955            assert(0 && "Edge should not have value already!");
956          }
957          Dest = P[Dest];
958        } while (Dest != BB);
959      }
960    }
961    if (FoundPath) continue;
962
963    // Speculatively set edges to zero.
964    FI = Unvisited.begin(), FE = Unvisited.end();
965    while(FI != FE && !FoundPath) {
966      const BasicBlock *BB = *FI; ++FI;
967
968      for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
969           NBB != End; ++NBB) {
970        Edge e = getEdge(*NBB,BB);
971        double w = getEdgeWeight(e);
972        if (w == MissingValue) {
973          setEdgeWeight(e,0);
974          FoundPath = true;
975          break;
976        }
977      }
978    }
979    if (FoundPath) continue;
980
981    errs() << "{";
982    FI = Unvisited.begin(), FE = Unvisited.end();
983    while(FI != FE) {
984      const BasicBlock *BB = *FI; ++FI;
985      dbgs() << BB->getName();
986      if (FI != FE)
987        dbgs() << ",";
988    }
989    errs() << "}";
990
991    errs() << "ASSERT: could not repair function";
992    assert(0 && "could not repair function");
993  }
994
995  EdgeWeights J = EdgeInformation[F];
996  for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
997    Edge e = EI->first;
998
999    bool SuccFound = false;
1000    if (e.first != 0) {
1001      succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
1002      if (NBB == End) {
1003        if (0 == e.second) {
1004          SuccFound = true;
1005        }
1006      }
1007      for (;NBB != End; ++NBB) {
1008        if (*NBB == e.second) {
1009          SuccFound = true;
1010          break;
1011        }
1012      }
1013      if (!SuccFound) {
1014        removeEdge(e);
1015      }
1016    }
1017  }
1018}
1019
1020raw_ostream& operator<<(raw_ostream &O, const Function *F) {
1021  return O << F->getName();
1022}
1023
1024raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1025  return O << MF->getFunction()->getName() << "(MF)";
1026}
1027
1028raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
1029  return O << BB->getName();
1030}
1031
1032raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1033  return O << MBB->getBasicBlock()->getName() << "(MB)";
1034}
1035
1036raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
1037  O << "(";
1038
1039  if (E.first)
1040    O << E.first;
1041  else
1042    O << "0";
1043
1044  O << ",";
1045
1046  if (E.second)
1047    O << E.second;
1048  else
1049    O << "0";
1050
1051  return O << ")";
1052}
1053
1054raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1055  O << "(";
1056
1057  if (E.first)
1058    O << E.first;
1059  else
1060    O << "0";
1061
1062  O << ",";
1063
1064  if (E.second)
1065    O << E.second;
1066  else
1067    O << "0";
1068
1069  return O << ")";
1070}
1071
1072} // namespace llvm
1073
1074//===----------------------------------------------------------------------===//
1075//  NoProfile ProfileInfo implementation
1076//
1077
1078namespace {
1079  struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1080    static char ID; // Class identification, replacement for typeinfo
1081    NoProfileInfo() : ImmutablePass(&ID) {}
1082  };
1083}  // End of anonymous namespace
1084
1085char NoProfileInfo::ID = 0;
1086// Register this pass...
1087static RegisterPass<NoProfileInfo>
1088X("no-profile", "No Profile Information", false, true);
1089
1090// Declare that we implement the ProfileInfo interface
1091static RegisterAnalysisGroup<ProfileInfo, true> Y(X);
1092
1093ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }
1094