1 //===- ProfileInfo.cpp - Profile Info Interface ---------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the abstract ProfileInfo interface, and the default
11 // "no profile" implementation.
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"
27 // Register the ProfileInfo interface, providing a nice name to refer to.
28 static RegisterAnalysisGroup<ProfileInfo> Z("Profile Information");
33 ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {}
35 ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {}
38 ProfileInfoT<Function, BasicBlock>::ProfileInfoT() {
42 ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() {
43 if (MachineProfile) delete MachineProfile;
47 char ProfileInfo::ID = 0;
50 char MachineProfileInfo::ID = 0;
53 const double ProfileInfo::MissingValue = -1;
56 const double MachineProfileInfo::MissingValue = -1;
59 double ProfileInfo::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())
68 double Count = MissingValue;
70 pred_const_iterator PI = pred_begin(BB), PE = pred_end(BB);
72 // Are there zero predecessors of this block?
74 Edge e = getEdge(0,BB);
75 Count = getEdgeWeight(e);
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;
81 for (; PI != PE; ++PI)
82 if (ProcessedPreds.insert(*PI).second) {
83 double w = getEdgeWeight(getEdge(*PI, BB));
84 if (w == MissingValue) {
92 // If the predecessors did not suffice to get block weight, try successors.
93 if (Count == MissingValue) {
95 succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
97 // Are there zero successors of this block?
99 Edge e = getEdge(BB,0);
100 Count = getEdgeWeight(e);
102 std::set<const BasicBlock*> ProcessedSuccs;
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;
116 if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
121 double MachineProfileInfo::getExecutionCount(const MachineBasicBlock *MBB) {
122 std::map<const MachineFunction*, BlockCounts>::iterator J =
123 BlockInformation.find(MBB->getParent());
124 if (J != BlockInformation.end()) {
125 BlockCounts::iterator I = J->second.find(MBB);
126 if (I != J->second.end())
134 double ProfileInfo::getExecutionCount(const Function *F) {
135 std::map<const Function*, double>::iterator J =
136 FunctionInformation.find(F);
137 if (J != FunctionInformation.end())
140 // isDeclaration() is checked here and not at start of function to allow
141 // functions without a body still to have a execution count.
142 if (F->isDeclaration()) return MissingValue;
144 double Count = getExecutionCount(&F->getEntryBlock());
145 if (Count != MissingValue) FunctionInformation[F] = Count;
150 double MachineProfileInfo::getExecutionCount(const MachineFunction *MF) {
151 std::map<const MachineFunction*, double>::iterator J =
152 FunctionInformation.find(MF);
153 if (J != FunctionInformation.end())
156 double Count = getExecutionCount(&MF->front());
157 if (Count != MissingValue) FunctionInformation[MF] = Count;
162 void ProfileInfo::setExecutionCount(const BasicBlock *BB, double w) {
163 DEBUG(errs() << "Creating Block " << BB->getName()
164 << " (weight: " << format("%.20g",w) << ")\n");
165 BlockInformation[BB->getParent()][BB] = w;
169 void MachineProfileInfo::setExecutionCount(const MachineBasicBlock *MBB, double w) {
170 DEBUG(errs() << "Creating Block " << MBB->getBasicBlock()->getName()
171 << " (weight: " << format("%.20g",w) << ")\n");
172 BlockInformation[MBB->getParent()][MBB] = w;
176 void ProfileInfo::addEdgeWeight(Edge e, double w) {
177 double oldw = getEdgeWeight(e);
178 assert (oldw != MissingValue && "Adding weight to Edge with no previous weight");
179 DEBUG(errs() << "Adding to Edge " << e
180 << " (new weight: " << format("%.20g",oldw + w) << ")\n");
181 EdgeInformation[getFunction(e)][e] = oldw + w;
185 void ProfileInfo::addExecutionCount(const BasicBlock *BB, double w) {
186 double oldw = getExecutionCount(BB);
187 assert (oldw != MissingValue && "Adding weight to Block with no previous weight");
188 DEBUG(errs() << "Adding to Block " << BB->getName()
189 << " (new weight: " << format("%.20g",oldw + w) << ")\n");
190 BlockInformation[BB->getParent()][BB] = oldw + w;
194 void ProfileInfo::removeBlock(const BasicBlock *BB) {
195 std::map<const Function*, BlockCounts>::iterator J =
196 BlockInformation.find(BB->getParent());
197 if (J == BlockInformation.end()) return;
199 DEBUG(errs() << "Deleting " << BB->getName() << "\n");
204 void ProfileInfo::removeEdge(Edge e) {
205 std::map<const Function*, EdgeWeights>::iterator J =
206 EdgeInformation.find(getFunction(e));
207 if (J == EdgeInformation.end()) return;
209 DEBUG(errs() << "Deleting" << e << "\n");
214 void ProfileInfo::replaceEdge(const Edge &oldedge, const Edge &newedge) {
216 if ((w = getEdgeWeight(newedge)) == MissingValue) {
217 w = getEdgeWeight(oldedge);
218 DEBUG(errs() << "Replacing " << oldedge << " with " << newedge << "\n");
220 w += getEdgeWeight(oldedge);
221 DEBUG(errs() << "Adding " << oldedge << " to " << newedge << "\n");
223 setEdgeWeight(newedge,w);
228 const BasicBlock *ProfileInfo::GetPath(const BasicBlock *Src, const BasicBlock *Dest,
229 Path &P, unsigned Mode) {
230 const BasicBlock *BB = 0;
231 bool hasFoundPath = false;
233 std::queue<const BasicBlock *> BFS;
236 while(BFS.size() && !hasFoundPath) {
240 succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
243 if (Mode & GetPathToExit) {
248 for(;Succ != End; ++Succ) {
249 if (P.find(*Succ) != P.end()) continue;
250 Edge e = getEdge(BB,*Succ);
251 if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue;
254 if ((Mode & GetPathToDest) && *Succ == Dest) {
259 if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) {
271 void ProfileInfo::divertFlow(const Edge &oldedge, const Edge &newedge) {
272 DEBUG(errs() << "Diverting " << oldedge << " via " << newedge );
274 // First check if the old edge was taken, if not, just delete it...
275 if (getEdgeWeight(oldedge) == 0) {
281 P[newedge.first] = 0;
282 P[newedge.second] = newedge.first;
283 const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest);
285 double w = getEdgeWeight (oldedge);
286 DEBUG(errs() << ", Weight: " << format("%.20g",w) << "\n");
288 const BasicBlock *Parent = P.find(BB)->second;
289 Edge e = getEdge(Parent,BB);
290 double oldw = getEdgeWeight(e);
291 double oldc = getExecutionCount(e.first);
292 setEdgeWeight(e, w+oldw);
293 if (Parent != oldedge.first) {
294 setExecutionCount(e.first, w+oldc);
297 } while (BB != newedge.first);
301 /// Replaces all occurences of RmBB in the ProfilingInfo with DestBB.
302 /// This checks all edges of the function the blocks reside in and replaces the
303 /// occurences of RmBB with DestBB.
305 void ProfileInfo::replaceAllUses(const BasicBlock *RmBB,
306 const BasicBlock *DestBB) {
307 DEBUG(errs() << "Replacing " << RmBB->getName()
308 << " with " << DestBB->getName() << "\n");
309 const Function *F = DestBB->getParent();
310 std::map<const Function*, EdgeWeights>::iterator J =
311 EdgeInformation.find(F);
312 if (J == EdgeInformation.end()) return;
315 bool erasededge = false;
316 EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
319 bool foundedge = false; bool eraseedge = false;
320 if (e.first == RmBB) {
321 if (e.second == DestBB) {
324 newedge = getEdge(DestBB, e.second);
328 if (e.second == RmBB) {
329 if (e.first == DestBB) {
332 newedge = getEdge(e.first, DestBB);
337 replaceEdge(e, newedge);
341 Edge newedge = getEdge(DestBB, DestBB);
342 replaceEdge(e, newedge);
351 /// Splits an edge in the ProfileInfo and redirects flow over NewBB.
352 /// Since its possible that there is more than one edge in the CFG from FristBB
353 /// to SecondBB its necessary to redirect the flow proporionally.
355 void ProfileInfo::splitEdge(const BasicBlock *FirstBB,
356 const BasicBlock *SecondBB,
357 const BasicBlock *NewBB,
358 bool MergeIdenticalEdges) {
359 const Function *F = FirstBB->getParent();
360 std::map<const Function*, EdgeWeights>::iterator J =
361 EdgeInformation.find(F);
362 if (J == EdgeInformation.end()) return;
364 // Generate edges and read current weight.
365 Edge e = getEdge(FirstBB, SecondBB);
366 Edge n1 = getEdge(FirstBB, NewBB);
367 Edge n2 = getEdge(NewBB, SecondBB);
368 EdgeWeights &ECs = J->second;
372 if (!MergeIdenticalEdges) {
373 // First count the edges from FristBB to SecondBB, if there is more than
374 // one, only slice out a proporional part for NewBB.
375 for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB);
377 if (*BBI == SecondBB) succ_count++;
379 // When the NewBB is completely new, increment the count by one so that
380 // the counts are properly distributed.
381 if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++;
383 // When the edges are merged anyway, then redirect all flow.
387 // We know now how many edges there are from FirstBB to SecondBB, reroute a
388 // proportional part of the edge weight over NewBB.
389 double neww = floor(w / succ_count);
392 BlockInformation[F][NewBB] += neww;
393 if (succ_count == 1) {
401 void ProfileInfo::splitBlock(const BasicBlock *Old, const BasicBlock* New) {
402 const Function *F = Old->getParent();
403 std::map<const Function*, EdgeWeights>::iterator J =
404 EdgeInformation.find(F);
405 if (J == EdgeInformation.end()) return;
407 DEBUG(errs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n");
409 std::set<Edge> Edges;
410 for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end();
412 Edge old = ewi->first;
413 if (old.first == Old) {
417 for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end();
419 Edge newedge = getEdge(New, EI->second);
420 replaceEdge(*EI, newedge);
423 double w = getExecutionCount(Old);
424 setEdgeWeight(getEdge(Old, New), w);
425 setExecutionCount(New, w);
429 void ProfileInfo::splitBlock(const BasicBlock *BB, const BasicBlock* NewBB,
430 BasicBlock *const *Preds, unsigned NumPreds) {
431 const Function *F = BB->getParent();
432 std::map<const Function*, EdgeWeights>::iterator J =
433 EdgeInformation.find(F);
434 if (J == EdgeInformation.end()) return;
436 DEBUG(errs() << "Splitting " << NumPreds << " Edges from " << BB->getName()
437 << " to " << NewBB->getName() << "\n");
439 // Collect weight that was redirected over NewBB.
440 double newweight = 0;
442 std::set<const BasicBlock *> ProcessedPreds;
443 // For all requestes Predecessors.
444 for (unsigned pred = 0; pred < NumPreds; ++pred) {
445 const BasicBlock * Pred = Preds[pred];
446 if (ProcessedPreds.insert(Pred).second) {
447 // Create edges and read old weight.
448 Edge oldedge = getEdge(Pred, BB);
449 Edge newedge = getEdge(Pred, NewBB);
451 // Remember how much weight was redirected.
452 newweight += getEdgeWeight(oldedge);
454 replaceEdge(oldedge,newedge);
458 Edge newedge = getEdge(NewBB,BB);
459 setEdgeWeight(newedge, newweight);
460 setExecutionCount(NewBB, newweight);
464 void ProfileInfo::transfer(const Function *Old, const Function *New) {
465 DEBUG(errs() << "Replacing Function " << Old->getName() << " with "
466 << New->getName() << "\n");
467 std::map<const Function*, EdgeWeights>::iterator J =
468 EdgeInformation.find(Old);
469 if(J != EdgeInformation.end()) {
470 EdgeInformation[New] = J->second;
472 EdgeInformation.erase(Old);
473 BlockInformation.erase(Old);
474 FunctionInformation.erase(Old);
477 static double readEdgeOrRemember(ProfileInfo::Edge edge, double w, ProfileInfo::Edge &tocalc,
479 if (w == ProfileInfo::MissingValue) {
489 bool ProfileInfo::CalculateMissingEdge(const BasicBlock *BB, Edge &removed, bool assumeEmptySelf) {
491 unsigned uncalculated = 0;
493 // collect weights of all incoming and outgoing edges, rememer edges that
496 SmallSet<const BasicBlock*,8> pred_visited;
497 pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
499 Edge e = getEdge(0,BB);
500 incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
502 for (;bbi != bbe; ++bbi) {
503 if (pred_visited.insert(*bbi)) {
504 Edge e = getEdge(*bbi,BB);
505 incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
510 SmallSet<const BasicBlock*,8> succ_visited;
511 succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
513 Edge e = getEdge(BB,0);
514 if (getEdgeWeight(e) == MissingValue) {
515 double w = getExecutionCount(BB);
516 if (w != MissingValue) {
521 outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
523 for (;sbbi != sbbe; ++sbbi) {
524 if (succ_visited.insert(*sbbi)) {
525 Edge e = getEdge(BB,*sbbi);
526 outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
530 // if exactly one edge weight was missing, calculate it and remove it from
532 if (uncalculated == 0 ) {
535 if (uncalculated == 1) {
536 if (incount < outcount) {
537 EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
539 EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
541 DEBUG(errs() << "--Calc Edge Counter for " << edgetocalc << ": "
542 << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
543 removed = edgetocalc;
546 if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
547 setEdgeWeight(edgetocalc, incount * 10);
548 removed = edgetocalc;
555 static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) {
556 double w = PI->getEdgeWeight(e);
557 if (w != ProfileInfo::MissingValue) {
565 bool ProfileInfo::EstimateMissingEdges(const BasicBlock *BB) {
566 bool hasNoSuccessors = false;
569 std::set<Edge> inMissing;
570 std::set<const BasicBlock*> ProcessedPreds;
571 pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
573 readEdge(this,getEdge(0,BB),inWeight,inMissing);
575 for( ; bbi != bbe; ++bbi ) {
576 if (ProcessedPreds.insert(*bbi).second) {
577 readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
581 double outWeight = 0;
582 std::set<Edge> outMissing;
583 std::set<const BasicBlock*> ProcessedSuccs;
584 succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
586 readEdge(this,getEdge(BB,0),outWeight,outMissing);
587 hasNoSuccessors = true;
589 for ( ; sbbi != sbbe; ++sbbi ) {
590 if (ProcessedSuccs.insert(*sbbi).second) {
591 readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
596 std::set<Edge>::iterator ei,ee;
597 if (inMissing.size() == 0 && outMissing.size() > 0) {
598 ei = outMissing.begin();
599 ee = outMissing.end();
600 share = inWeight/outMissing.size();
601 setExecutionCount(BB,inWeight);
603 if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
604 ei = inMissing.begin();
605 ee = inMissing.end();
607 setExecutionCount(BB,0);
609 if (inMissing.size() == 0 && outMissing.size() == 0) {
610 setExecutionCount(BB,outWeight);
615 for ( ; ei != ee; ++ei ) {
616 setEdgeWeight(*ei,share);
622 void ProfileInfo::repair(const Function *F) {
623 // if (getExecutionCount(&(F->getEntryBlock())) == 0) {
624 // for (Function::const_iterator FI = F->begin(), FE = F->end();
626 // const BasicBlock* BB = &(*FI);
628 // pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
630 // setEdgeWeight(getEdge(0,BB),0);
632 // for(;NBB != End; ++NBB) {
633 // setEdgeWeight(getEdge(*NBB,BB),0);
637 // succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
639 // setEdgeWeight(getEdge(0,BB),0);
641 // for(;NBB != End; ++NBB) {
642 // setEdgeWeight(getEdge(*NBB,BB),0);
648 // The set of BasicBlocks that are still unvisited.
649 std::set<const BasicBlock*> Unvisited;
651 // The set of return edges (Edges with no successors).
652 std::set<Edge> ReturnEdges;
653 double ReturnWeight = 0;
655 // First iterate over the whole function and collect:
656 // 1) The blocks in this function in the Unvisited set.
657 // 2) The return edges in the ReturnEdges set.
658 // 3) The flow that is leaving the function already via return edges.
660 // Data structure for searching the function.
661 std::queue<const BasicBlock *> BFS;
662 const BasicBlock *BB = &(F->getEntryBlock());
664 Unvisited.insert(BB);
667 BB = BFS.front(); BFS.pop();
668 succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
670 Edge e = getEdge(BB,0);
671 double w = getEdgeWeight(e);
672 if (w == MissingValue) {
673 // If the return edge has no value, try to read value from block.
674 double bw = getExecutionCount(BB);
675 if (bw != MissingValue) {
679 // If both return edge and block provide no value, collect edge.
680 ReturnEdges.insert(e);
683 // If the return edge has a proper value, collect it.
687 for (;NBB != End; ++NBB) {
688 if (Unvisited.insert(*NBB).second) {
694 while (Unvisited.size() > 0) {
695 unsigned oldUnvisitedCount = Unvisited.size();
696 bool FoundPath = false;
698 // If there is only one edge left, calculate it.
699 if (ReturnEdges.size() == 1) {
700 ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
702 Edge e = *ReturnEdges.begin();
703 setEdgeWeight(e,ReturnWeight);
704 setExecutionCount(e.first,ReturnWeight);
706 Unvisited.erase(e.first);
707 ReturnEdges.erase(e);
711 // Calculate all blocks where only one edge is missing, this may also
712 // resolve furhter return edges.
713 std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
715 const BasicBlock *BB = *FI; ++FI;
717 if(CalculateMissingEdge(BB,e,true)) {
718 if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
719 setExecutionCount(BB,getExecutionCount(BB));
722 if (e.first != 0 && e.second == 0) {
723 ReturnEdges.erase(e);
724 ReturnWeight += getEdgeWeight(e);
728 if (oldUnvisitedCount > Unvisited.size()) continue;
730 // Estimate edge weights by dividing the flow proportionally.
731 FI = Unvisited.begin(), FE = Unvisited.end();
733 const BasicBlock *BB = *FI; ++FI;
734 const BasicBlock *Dest = 0;
735 bool AllEdgesHaveSameReturn = true;
736 // Check each Successor, these must all end up in the same or an empty
737 // return block otherwise its dangerous to do an estimation on them.
738 for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
739 Succ != End; ++Succ) {
741 GetPath(*Succ, 0, P, GetPathToExit);
742 if (Dest && Dest != P[0]) {
743 AllEdgesHaveSameReturn = false;
747 if (AllEdgesHaveSameReturn) {
748 if(EstimateMissingEdges(BB)) {
754 if (oldUnvisitedCount > Unvisited.size()) continue;
756 // Check if there is a path to an block that has a known value and redirect
758 FI = Unvisited.begin(), FE = Unvisited.end();
759 while(FI != FE && !FoundPath) {
761 const BasicBlock *BB = *FI; ++FI;
763 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
765 // Calculate incoming flow.
766 double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
767 std::set<const BasicBlock *> Processed;
768 for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
770 if (Processed.insert(*NBB).second) {
771 Edge e = getEdge(*NBB, BB);
772 double ew = getEdgeWeight(e);
773 if (ew != MissingValue) {
777 // If the path contains the successor, this means its a backedge,
778 // do not count as missing.
779 if (P.find(*NBB) == P.end())
785 if (inmissing == incount) continue;
786 if (invalid == 0) continue;
788 // Subtract (already) outgoing flow.
790 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
792 if (Processed.insert(*NBB).second) {
793 Edge e = getEdge(BB, *NBB);
794 double ew = getEdgeWeight(e);
795 if (ew != MissingValue) {
800 if (iw < 0) continue;
802 // Check the recieving end of the path if it can handle the flow.
803 double ow = getExecutionCount(Dest);
805 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
807 if (Processed.insert(*NBB).second) {
808 Edge e = getEdge(BB, *NBB);
809 double ew = getEdgeWeight(e);
810 if (ew != MissingValue) {
815 if (ow < 0) continue;
817 // Determine how much flow shall be used.
818 double ew = getEdgeWeight(getEdge(P[Dest],Dest));
819 if (ew != MissingValue) {
828 if (ew != MissingValue) {
830 Edge e = getEdge(P[Dest],Dest);
831 if (getEdgeWeight(e) == MissingValue) {
836 } while (Dest != BB);
839 if (FoundPath) continue;
841 // Calculate a block with self loop.
842 FI = Unvisited.begin(), FE = Unvisited.end();
843 while(FI != FE && !FoundPath) {
844 const BasicBlock *BB = *FI; ++FI;
845 bool SelfEdgeFound = false;
846 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
849 SelfEdgeFound = true;
854 Edge e = getEdge(BB,BB);
855 if (getEdgeWeight(e) == MissingValue) {
857 std::set<const BasicBlock *> Processed;
858 for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
860 if (Processed.insert(*NBB).second) {
861 Edge e = getEdge(*NBB, BB);
862 double ew = getEdgeWeight(e);
863 if (ew != MissingValue) {
868 setEdgeWeight(e,iw * 10);
873 if (FoundPath) continue;
875 // Determine backedges, set them to zero.
876 FI = Unvisited.begin(), FE = Unvisited.end();
877 while(FI != FE && !FoundPath) {
878 const BasicBlock *BB = *FI; ++FI;
879 const BasicBlock *Dest;
881 bool BackEdgeFound = false;
882 for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
884 Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
886 BackEdgeFound = true;
891 Edge e = getEdge(Dest,BB);
892 double w = getEdgeWeight(e);
893 if (w == MissingValue) {
898 Edge e = getEdge(P[Dest], Dest);
899 double w = getEdgeWeight(e);
900 if (w == MissingValue) {
905 } while (Dest != BB);
908 if (FoundPath) continue;
910 // Channel flow to return block.
911 FI = Unvisited.begin(), FE = Unvisited.end();
912 while(FI != FE && !FoundPath) {
913 const BasicBlock *BB = *FI; ++FI;
916 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
920 if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
921 // Calculate incoming flow.
923 std::set<const BasicBlock *> Processed;
924 for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
926 if (Processed.insert(*NBB).second) {
927 Edge e = getEdge(*NBB, BB);
928 double ew = getEdgeWeight(e);
929 if (ew != MissingValue) {
935 Edge e = getEdge(P[Dest], Dest);
936 double w = getEdgeWeight(e);
937 if (w == MissingValue) {
941 assert(0 && "Edge should not have value already!");
944 } while (Dest != BB);
947 if (FoundPath) continue;
949 // Speculatively set edges to zero.
950 FI = Unvisited.begin(), FE = Unvisited.end();
951 while(FI != FE && !FoundPath) {
952 const BasicBlock *BB = *FI; ++FI;
954 for (pred_const_iterator NBB = pred_begin(BB), End = pred_end(BB);
956 Edge e = getEdge(*NBB,BB);
957 double w = getEdgeWeight(e);
958 if (w == MissingValue) {
965 if (FoundPath) continue;
968 FI = Unvisited.begin(), FE = Unvisited.end();
970 const BasicBlock *BB = *FI; ++FI;
971 errs() << BB->getName();
977 errs() << "ASSERT: could not repair function";
978 assert(0 && "could not repair function");
981 EdgeWeights J = EdgeInformation[F];
982 for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
985 bool SuccFound = false;
987 succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
993 for (;NBB != End; ++NBB) {
994 if (*NBB == e.second) {
1006 raw_ostream& operator<<(raw_ostream &O, const Function *F) {
1007 return O << F->getName();
1010 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1011 return O << MF->getFunction()->getName() << "(MF)";
1014 raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
1015 return O << BB->getName();
1018 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1019 return O << MBB->getBasicBlock()->getName() << "(MB)";
1022 raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
1040 raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1060 //===----------------------------------------------------------------------===//
1061 // NoProfile ProfileInfo implementation
1065 struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1066 static char ID; // Class identification, replacement for typeinfo
1067 NoProfileInfo() : ImmutablePass(&ID) {}
1069 } // End of anonymous namespace
1071 char NoProfileInfo::ID = 0;
1072 // Register this pass...
1073 static RegisterPass<NoProfileInfo>
1074 X("no-profile", "No Profile Information", false, true);
1076 // Declare that we implement the ProfileInfo interface
1077 static RegisterAnalysisGroup<ProfileInfo, true> Y(X);
1079 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }