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 ProfileInfoT<Function,BasicBlock>::ID = 0;
50 char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0;
53 const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1;
56 double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1;
59 ProfileInfoT<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())
68 double Count = MissingValue;
70 const_pred_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 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())
135 double ProfileInfoT<Function,BasicBlock>::getExecutionCount(const Function *F) {
136 std::map<const Function*, double>::iterator J =
137 FunctionInformation.find(F);
138 if (J != FunctionInformation.end())
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;
145 double Count = getExecutionCount(&F->getEntryBlock());
146 if (Count != MissingValue) FunctionInformation[F] = Count;
151 double 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())
158 double Count = getExecutionCount(&MF->front());
159 if (Count != MissingValue) FunctionInformation[MF] = Count;
164 void 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;
172 void 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;
180 void 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;
189 void 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;
199 void 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;
204 DEBUG(dbgs() << "Deleting " << BB->getName() << "\n");
209 void 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;
214 DEBUG(dbgs() << "Deleting" << e << "\n");
219 void ProfileInfoT<Function,BasicBlock>::
220 replaceEdge(const Edge &oldedge, const Edge &newedge) {
222 if ((w = getEdgeWeight(newedge)) == MissingValue) {
223 w = getEdgeWeight(oldedge);
224 DEBUG(dbgs() << "Replacing " << oldedge << " with " << newedge << "\n");
226 w += getEdgeWeight(oldedge);
227 DEBUG(dbgs() << "Adding " << oldedge << " to " << newedge << "\n");
229 setEdgeWeight(newedge,w);
234 const 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;
240 std::queue<const BasicBlock *> BFS;
243 while(BFS.size() && !hasFoundPath) {
247 succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
250 if (Mode & GetPathToExit) {
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;
261 if ((Mode & GetPathToDest) && *Succ == Dest) {
266 if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) {
278 void ProfileInfoT<Function,BasicBlock>::
279 divertFlow(const Edge &oldedge, const Edge &newedge) {
280 DEBUG(dbgs() << "Diverting " << oldedge << " via " << newedge );
282 // First check if the old edge was taken, if not, just delete it...
283 if (getEdgeWeight(oldedge) == 0) {
289 P[newedge.first] = 0;
290 P[newedge.second] = newedge.first;
291 const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest);
293 double w = getEdgeWeight (oldedge);
294 DEBUG(dbgs() << ", Weight: " << format("%.20g",w) << "\n");
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);
305 } while (BB != newedge.first);
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.
313 void 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;
323 bool erasededge = false;
324 EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
327 bool foundedge = false; bool eraseedge = false;
328 if (e.first == RmBB) {
329 if (e.second == DestBB) {
332 newedge = getEdge(DestBB, e.second);
336 if (e.second == RmBB) {
337 if (e.first == DestBB) {
340 newedge = getEdge(e.first, DestBB);
345 replaceEdge(e, newedge);
349 Edge newedge = getEdge(DestBB, DestBB);
350 replaceEdge(e, newedge);
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.
363 void 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;
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;
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);
385 if (*BBI == SecondBB) succ_count++;
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++;
391 // When the edges are merged anyway, then redirect all flow.
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);
400 BlockInformation[F][NewBB] += neww;
401 if (succ_count == 1) {
409 void 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;
416 DEBUG(dbgs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n");
418 std::set<Edge> Edges;
419 for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end();
421 Edge old = ewi->first;
422 if (old.first == Old) {
426 for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end();
428 Edge newedge = getEdge(New, EI->second);
429 replaceEdge(*EI, newedge);
432 double w = getExecutionCount(Old);
433 setEdgeWeight(getEdge(Old, New), w);
434 setExecutionCount(New, w);
438 void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *BB,
439 const BasicBlock* NewBB,
440 BasicBlock *const *Preds,
442 const Function *F = BB->getParent();
443 std::map<const Function*, EdgeWeights>::iterator J =
444 EdgeInformation.find(F);
445 if (J == EdgeInformation.end()) return;
447 DEBUG(dbgs() << "Splitting " << NumPreds << " Edges from " << BB->getName()
448 << " to " << NewBB->getName() << "\n");
450 // Collect weight that was redirected over NewBB.
451 double newweight = 0;
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);
462 // Remember how much weight was redirected.
463 newweight += getEdgeWeight(oldedge);
465 replaceEdge(oldedge,newedge);
469 Edge newedge = getEdge(NewBB,BB);
470 setEdgeWeight(newedge, newweight);
471 setExecutionCount(NewBB, newweight);
475 void 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;
484 EdgeInformation.erase(Old);
485 BlockInformation.erase(Old);
486 FunctionInformation.erase(Old);
489 static double readEdgeOrRemember(ProfileInfo::Edge edge, double w,
490 ProfileInfo::Edge &tocalc, unsigned &uncalc) {
491 if (w == ProfileInfo::MissingValue) {
501 bool ProfileInfoT<Function,BasicBlock>::
502 CalculateMissingEdge(const BasicBlock *BB, Edge &removed,
503 bool assumeEmptySelf) {
505 unsigned uncalculated = 0;
507 // collect weights of all incoming and outgoing edges, rememer edges that
510 SmallSet<const BasicBlock*,8> pred_visited;
511 const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
513 Edge e = getEdge(0,BB);
514 incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
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);
524 SmallSet<const BasicBlock*,8> succ_visited;
525 succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
527 Edge e = getEdge(BB,0);
528 if (getEdgeWeight(e) == MissingValue) {
529 double w = getExecutionCount(BB);
530 if (w != MissingValue) {
535 outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
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);
544 // if exactly one edge weight was missing, calculate it and remove it from
546 if (uncalculated == 0 ) {
549 if (uncalculated == 1) {
550 if (incount < outcount) {
551 EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
553 EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
555 DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": "
556 << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
557 removed = edgetocalc;
560 if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
561 setEdgeWeight(edgetocalc, incount * 10);
562 removed = edgetocalc;
569 static 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) {
579 bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) {
580 bool hasNoSuccessors = false;
583 std::set<Edge> inMissing;
584 std::set<const BasicBlock*> ProcessedPreds;
585 const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
587 readEdge(this,getEdge(0,BB),inWeight,inMissing);
589 for( ; bbi != bbe; ++bbi ) {
590 if (ProcessedPreds.insert(*bbi).second) {
591 readEdge(this,getEdge(*bbi,BB),inWeight,inMissing);
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);
600 readEdge(this,getEdge(BB,0),outWeight,outMissing);
601 hasNoSuccessors = true;
603 for ( ; sbbi != sbbe; ++sbbi ) {
604 if (ProcessedSuccs.insert(*sbbi).second) {
605 readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
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);
617 if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
618 ei = inMissing.begin();
619 ee = inMissing.end();
621 setExecutionCount(BB,0);
623 if (inMissing.size() == 0 && outMissing.size() == 0) {
624 setExecutionCount(BB,outWeight);
629 for ( ; ei != ee; ++ei ) {
630 setEdgeWeight(*ei,share);
636 void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
637 // if (getExecutionCount(&(F->getEntryBlock())) == 0) {
638 // for (Function::const_iterator FI = F->begin(), FE = F->end();
640 // const BasicBlock* BB = &(*FI);
642 // const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
644 // setEdgeWeight(getEdge(0,BB),0);
646 // for(;NBB != End; ++NBB) {
647 // setEdgeWeight(getEdge(*NBB,BB),0);
651 // succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
653 // setEdgeWeight(getEdge(0,BB),0);
655 // for(;NBB != End; ++NBB) {
656 // setEdgeWeight(getEdge(*NBB,BB),0);
662 // The set of BasicBlocks that are still unvisited.
663 std::set<const BasicBlock*> Unvisited;
665 // The set of return edges (Edges with no successors).
666 std::set<Edge> ReturnEdges;
667 double ReturnWeight = 0;
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.
674 // Data structure for searching the function.
675 std::queue<const BasicBlock *> BFS;
676 const BasicBlock *BB = &(F->getEntryBlock());
678 Unvisited.insert(BB);
681 BB = BFS.front(); BFS.pop();
682 succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
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) {
693 // If both return edge and block provide no value, collect edge.
694 ReturnEdges.insert(e);
697 // If the return edge has a proper value, collect it.
701 for (;NBB != End; ++NBB) {
702 if (Unvisited.insert(*NBB).second) {
708 while (Unvisited.size() > 0) {
709 unsigned oldUnvisitedCount = Unvisited.size();
710 bool FoundPath = false;
712 // If there is only one edge left, calculate it.
713 if (ReturnEdges.size() == 1) {
714 ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
716 Edge e = *ReturnEdges.begin();
717 setEdgeWeight(e,ReturnWeight);
718 setExecutionCount(e.first,ReturnWeight);
720 Unvisited.erase(e.first);
721 ReturnEdges.erase(e);
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();
729 const BasicBlock *BB = *FI; ++FI;
731 if(CalculateMissingEdge(BB,e,true)) {
732 if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
733 setExecutionCount(BB,getExecutionCount(BB));
736 if (e.first != 0 && e.second == 0) {
737 ReturnEdges.erase(e);
738 ReturnWeight += getEdgeWeight(e);
742 if (oldUnvisitedCount > Unvisited.size()) continue;
744 // Estimate edge weights by dividing the flow proportionally.
745 FI = Unvisited.begin(), FE = Unvisited.end();
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) {
755 GetPath(*Succ, 0, P, GetPathToExit);
756 if (Dest && Dest != P[0]) {
757 AllEdgesHaveSameReturn = false;
761 if (AllEdgesHaveSameReturn) {
762 if(EstimateMissingEdges(BB)) {
768 if (oldUnvisitedCount > Unvisited.size()) continue;
770 // Check if there is a path to an block that has a known value and redirect
772 FI = Unvisited.begin(), FE = Unvisited.end();
773 while(FI != FE && !FoundPath) {
775 const BasicBlock *BB = *FI; ++FI;
777 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
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 (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
784 if (Processed.insert(*NBB).second) {
785 Edge e = getEdge(*NBB, BB);
786 double ew = getEdgeWeight(e);
787 if (ew != MissingValue) {
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())
799 if (inmissing == incount) continue;
800 if (invalid == 0) continue;
802 // Subtract (already) outgoing flow.
804 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
806 if (Processed.insert(*NBB).second) {
807 Edge e = getEdge(BB, *NBB);
808 double ew = getEdgeWeight(e);
809 if (ew != MissingValue) {
814 if (iw < 0) continue;
816 // Check the recieving end of the path if it can handle the flow.
817 double ow = getExecutionCount(Dest);
819 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
821 if (Processed.insert(*NBB).second) {
822 Edge e = getEdge(BB, *NBB);
823 double ew = getEdgeWeight(e);
824 if (ew != MissingValue) {
829 if (ow < 0) continue;
831 // Determine how much flow shall be used.
832 double ew = getEdgeWeight(getEdge(P[Dest],Dest));
833 if (ew != MissingValue) {
842 if (ew != MissingValue) {
844 Edge e = getEdge(P[Dest],Dest);
845 if (getEdgeWeight(e) == MissingValue) {
850 } while (Dest != BB);
853 if (FoundPath) continue;
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);
863 SelfEdgeFound = true;
868 Edge e = getEdge(BB,BB);
869 if (getEdgeWeight(e) == MissingValue) {
871 std::set<const BasicBlock *> Processed;
872 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
874 if (Processed.insert(*NBB).second) {
875 Edge e = getEdge(*NBB, BB);
876 double ew = getEdgeWeight(e);
877 if (ew != MissingValue) {
882 setEdgeWeight(e,iw * 10);
887 if (FoundPath) continue;
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;
895 bool BackEdgeFound = false;
896 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
898 Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
900 BackEdgeFound = true;
905 Edge e = getEdge(Dest,BB);
906 double w = getEdgeWeight(e);
907 if (w == MissingValue) {
912 Edge e = getEdge(P[Dest], Dest);
913 double w = getEdgeWeight(e);
914 if (w == MissingValue) {
919 } while (Dest != BB);
922 if (FoundPath) continue;
924 // Channel flow to return block.
925 FI = Unvisited.begin(), FE = Unvisited.end();
926 while(FI != FE && !FoundPath) {
927 const BasicBlock *BB = *FI; ++FI;
930 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
934 if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
935 // Calculate incoming flow.
937 std::set<const BasicBlock *> Processed;
938 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
940 if (Processed.insert(*NBB).second) {
941 Edge e = getEdge(*NBB, BB);
942 double ew = getEdgeWeight(e);
943 if (ew != MissingValue) {
949 Edge e = getEdge(P[Dest], Dest);
950 double w = getEdgeWeight(e);
951 if (w == MissingValue) {
955 assert(0 && "Edge should not have value already!");
958 } while (Dest != BB);
961 if (FoundPath) continue;
963 // Speculatively set edges to zero.
964 FI = Unvisited.begin(), FE = Unvisited.end();
965 while(FI != FE && !FoundPath) {
966 const BasicBlock *BB = *FI; ++FI;
968 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
970 Edge e = getEdge(*NBB,BB);
971 double w = getEdgeWeight(e);
972 if (w == MissingValue) {
979 if (FoundPath) continue;
982 FI = Unvisited.begin(), FE = Unvisited.end();
984 const BasicBlock *BB = *FI; ++FI;
985 dbgs() << BB->getName();
991 errs() << "ASSERT: could not repair function";
992 assert(0 && "could not repair function");
995 EdgeWeights J = EdgeInformation[F];
996 for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
999 bool SuccFound = false;
1001 succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
1003 if (0 == e.second) {
1007 for (;NBB != End; ++NBB) {
1008 if (*NBB == e.second) {
1020 raw_ostream& operator<<(raw_ostream &O, const Function *F) {
1021 return O << F->getName();
1024 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1025 return O << MF->getFunction()->getName() << "(MF)";
1028 raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
1029 return O << BB->getName();
1032 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1033 return O << MBB->getBasicBlock()->getName() << "(MB)";
1036 raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
1054 raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1074 //===----------------------------------------------------------------------===//
1075 // NoProfile ProfileInfo implementation
1079 struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1080 static char ID; // Class identification, replacement for typeinfo
1081 NoProfileInfo() : ImmutablePass(&ID) {}
1083 /// getAdjustedAnalysisPointer - This method is used when a pass implements
1084 /// an analysis interface through multiple inheritance. If needed, it
1085 /// should override this to adjust the this pointer as needed for the
1086 /// specified pass info.
1087 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
1088 if (PI->isPassID(&ProfileInfo::ID))
1089 return (ProfileInfo*)this;
1093 virtual const char *getPassName() const {
1094 return "NoProfileInfo";
1097 } // End of anonymous namespace
1099 char NoProfileInfo::ID = 0;
1100 // Register this pass...
1101 static RegisterPass<NoProfileInfo>
1102 X("no-profile", "No Profile Information", false, true);
1104 // Declare that we implement the ProfileInfo interface
1105 static RegisterAnalysisGroup<ProfileInfo, true> Y(X);
1107 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }