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/ProfileInfo.h"
16#include "llvm/ADT/SmallSet.h"
17#include "llvm/Analysis/Passes.h"
18#include "llvm/CodeGen/MachineBasicBlock.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/Pass.h"
21#include "llvm/Support/CFG.h"
22#include <limits>
23#include <queue>
24#include <set>
25using namespace llvm;
26
27namespace llvm {
28  template<> char ProfileInfoT<Function,BasicBlock>::ID = 0;
29}
30
31// Register the ProfileInfo interface, providing a nice name to refer to.
32INITIALIZE_ANALYSIS_GROUP(ProfileInfo, "Profile Information", NoProfileInfo)
33
34namespace llvm {
35
36template <>
37ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {}
38template <>
39ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {}
40
41template <>
42ProfileInfoT<Function, BasicBlock>::ProfileInfoT() {
43  MachineProfile = 0;
44}
45template <>
46ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() {
47  if (MachineProfile) delete MachineProfile;
48}
49
50template<>
51char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0;
52
53template<>
54const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1;
55
56template<> const
57double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1;
58
59template<> double
60ProfileInfoT<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
123template<>
124double 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
137template<>
138double 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
153template<>
154double 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
166template<>
167void 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
174template<>
175void 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
182template<>
183void 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
191template<>
192void 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
201template<>
202void 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
211template<>
212void 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
221template<>
222void 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
236template<>
237const 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[(const BasicBlock*)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
280template<>
281void 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.
315template<>
316void 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.
365template<>
366void 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
411template<>
412void 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
440template<>
441void 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
477template<>
478void 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
492static 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
503template<>
504bool 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
572static 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
581template<>
582bool 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
634template<>
635void 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[(const BasicBlock*)0]) {
756          AllEdgesHaveSameReturn = false;
757        }
758        Dest = P[(const BasicBlock*)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[(const BasicBlock*)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
1019raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1020  return O << MF->getFunction()->getName() << "(MF)";
1021}
1022
1023raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1024  return O << MBB->getBasicBlock()->getName() << "(MB)";
1025}
1026
1027raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1028  O << "(";
1029
1030  if (E.first)
1031    O << E.first;
1032  else
1033    O << "0";
1034
1035  O << ",";
1036
1037  if (E.second)
1038    O << E.second;
1039  else
1040    O << "0";
1041
1042  return O << ")";
1043}
1044
1045} // namespace llvm
1046
1047//===----------------------------------------------------------------------===//
1048//  NoProfile ProfileInfo implementation
1049//
1050
1051namespace {
1052  struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1053    static char ID; // Class identification, replacement for typeinfo
1054    NoProfileInfo() : ImmutablePass(ID) {
1055      initializeNoProfileInfoPass(*PassRegistry::getPassRegistry());
1056    }
1057
1058    /// getAdjustedAnalysisPointer - This method is used when a pass implements
1059    /// an analysis interface through multiple inheritance.  If needed, it
1060    /// should override this to adjust the this pointer as needed for the
1061    /// specified pass info.
1062    virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
1063      if (PI == &ProfileInfo::ID)
1064        return (ProfileInfo*)this;
1065      return this;
1066    }
1067
1068    virtual const char *getPassName() const {
1069      return "NoProfileInfo";
1070    }
1071  };
1072}  // End of anonymous namespace
1073
1074char NoProfileInfo::ID = 0;
1075// Register this pass...
1076INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile",
1077                   "No Profile Information", false, true, true)
1078
1079ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }
1080