source: clamav/trunk/libclamav/c++/llvm/lib/Analysis/ProfileInfo.cpp@ 319

Last change on this file since 319 was 319, checked in by Yuri Dario, 14 years ago

clamav: update trunk to 0.97.
File size: 32.8 KB
Line 
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 const_pred_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 const BasicBlock *P = *PI;
83 if (ProcessedPreds.insert(P).second) {
84 double w = getEdgeWeight(getEdge(P, BB));
85 if (w == MissingValue) {
86 Count = MissingValue;
87 break;
88 }
89 Count += w;
90 }
91 }
92 }
93
94 // If the predecessors did not suffice to get block weight, try successors.
95 if (Count == MissingValue) {
96
97 succ_const_iterator SI = succ_begin(BB), SE = succ_end(BB);
98
99 // Are there zero successors of this block?
100 if (SI == SE) {
101 Edge e = getEdge(BB,0);
102 Count = getEdgeWeight(e);
103 } else {
104 std::set<const BasicBlock*> ProcessedSuccs;
105 Count = 0;
106 for (; SI != SE; ++SI)
107 if (ProcessedSuccs.insert(*SI).second) {
108 double w = getEdgeWeight(getEdge(BB, *SI));
109 if (w == MissingValue) {
110 Count = MissingValue;
111 break;
112 }
113 Count += w;
114 }
115 }
116 }
117
118 if (Count != MissingValue) BlockInformation[BB->getParent()][BB] = Count;
119 return Count;
120}
121
122template<>
123double ProfileInfoT<MachineFunction, MachineBasicBlock>::
124 getExecutionCount(const MachineBasicBlock *MBB) {
125 std::map<const MachineFunction*, BlockCounts>::iterator J =
126 BlockInformation.find(MBB->getParent());
127 if (J != BlockInformation.end()) {
128 BlockCounts::iterator I = J->second.find(MBB);
129 if (I != J->second.end())
130 return I->second;
131 }
132
133 return MissingValue;
134}
135
136template<>
137double ProfileInfoT<Function,BasicBlock>::getExecutionCount(const Function *F) {
138 std::map<const Function*, double>::iterator J =
139 FunctionInformation.find(F);
140 if (J != FunctionInformation.end())
141 return J->second;
142
143 // isDeclaration() is checked here and not at start of function to allow
144 // functions without a body still to have a execution count.
145 if (F->isDeclaration()) return MissingValue;
146
147 double Count = getExecutionCount(&F->getEntryBlock());
148 if (Count != MissingValue) FunctionInformation[F] = Count;
149 return Count;
150}
151
152template<>
153double ProfileInfoT<MachineFunction, MachineBasicBlock>::
154 getExecutionCount(const MachineFunction *MF) {
155 std::map<const MachineFunction*, double>::iterator J =
156 FunctionInformation.find(MF);
157 if (J != FunctionInformation.end())
158 return J->second;
159
160 double Count = getExecutionCount(&MF->front());
161 if (Count != MissingValue) FunctionInformation[MF] = Count;
162 return Count;
163}
164
165template<>
166void ProfileInfoT<Function,BasicBlock>::
167 setExecutionCount(const BasicBlock *BB, double w) {
168 DEBUG(dbgs() << "Creating Block " << BB->getName()
169 << " (weight: " << format("%.20g",w) << ")\n");
170 BlockInformation[BB->getParent()][BB] = w;
171}
172
173template<>
174void ProfileInfoT<MachineFunction, MachineBasicBlock>::
175 setExecutionCount(const MachineBasicBlock *MBB, double w) {
176 DEBUG(dbgs() << "Creating Block " << MBB->getBasicBlock()->getName()
177 << " (weight: " << format("%.20g",w) << ")\n");
178 BlockInformation[MBB->getParent()][MBB] = w;
179}
180
181template<>
182void ProfileInfoT<Function,BasicBlock>::addEdgeWeight(Edge e, double w) {
183 double oldw = getEdgeWeight(e);
184 assert (oldw != MissingValue && "Adding weight to Edge with no previous weight");
185 DEBUG(dbgs() << "Adding to Edge " << e
186 << " (new weight: " << format("%.20g",oldw + w) << ")\n");
187 EdgeInformation[getFunction(e)][e] = oldw + w;
188}
189
190template<>
191void ProfileInfoT<Function,BasicBlock>::
192 addExecutionCount(const BasicBlock *BB, double w) {
193 double oldw = getExecutionCount(BB);
194 assert (oldw != MissingValue && "Adding weight to Block with no previous weight");
195 DEBUG(dbgs() << "Adding to Block " << BB->getName()
196 << " (new weight: " << format("%.20g",oldw + w) << ")\n");
197 BlockInformation[BB->getParent()][BB] = oldw + w;
198}
199
200template<>
201void ProfileInfoT<Function,BasicBlock>::removeBlock(const BasicBlock *BB) {
202 std::map<const Function*, BlockCounts>::iterator J =
203 BlockInformation.find(BB->getParent());
204 if (J == BlockInformation.end()) return;
205
206 DEBUG(dbgs() << "Deleting " << BB->getName() << "\n");
207 J->second.erase(BB);
208}
209
210template<>
211void ProfileInfoT<Function,BasicBlock>::removeEdge(Edge e) {
212 std::map<const Function*, EdgeWeights>::iterator J =
213 EdgeInformation.find(getFunction(e));
214 if (J == EdgeInformation.end()) return;
215
216 DEBUG(dbgs() << "Deleting" << e << "\n");
217 J->second.erase(e);
218}
219
220template<>
221void ProfileInfoT<Function,BasicBlock>::
222 replaceEdge(const Edge &oldedge, const Edge &newedge) {
223 double w;
224 if ((w = getEdgeWeight(newedge)) == MissingValue) {
225 w = getEdgeWeight(oldedge);
226 DEBUG(dbgs() << "Replacing " << oldedge << " with " << newedge << "\n");
227 } else {
228 w += getEdgeWeight(oldedge);
229 DEBUG(dbgs() << "Adding " << oldedge << " to " << newedge << "\n");
230 }
231 setEdgeWeight(newedge,w);
232 removeEdge(oldedge);
233}
234
235template<>
236const BasicBlock *ProfileInfoT<Function,BasicBlock>::
237 GetPath(const BasicBlock *Src, const BasicBlock *Dest,
238 Path &P, unsigned Mode) {
239 const BasicBlock *BB = 0;
240 bool hasFoundPath = false;
241
242 std::queue<const BasicBlock *> BFS;
243 BFS.push(Src);
244
245 while(BFS.size() && !hasFoundPath) {
246 BB = BFS.front();
247 BFS.pop();
248
249 succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
250 if (Succ == End) {
251 P[0] = BB;
252 if (Mode & GetPathToExit) {
253 hasFoundPath = true;
254 BB = 0;
255 }
256 }
257 for(;Succ != End; ++Succ) {
258 if (P.find(*Succ) != P.end()) continue;
259 Edge e = getEdge(BB,*Succ);
260 if ((Mode & GetPathWithNewEdges) && (getEdgeWeight(e) != MissingValue)) continue;
261 P[*Succ] = BB;
262 BFS.push(*Succ);
263 if ((Mode & GetPathToDest) && *Succ == Dest) {
264 hasFoundPath = true;
265 BB = *Succ;
266 break;
267 }
268 if ((Mode & GetPathToValue) && (getExecutionCount(*Succ) != MissingValue)) {
269 hasFoundPath = true;
270 BB = *Succ;
271 break;
272 }
273 }
274 }
275
276 return BB;
277}
278
279template<>
280void ProfileInfoT<Function,BasicBlock>::
281 divertFlow(const Edge &oldedge, const Edge &newedge) {
282 DEBUG(dbgs() << "Diverting " << oldedge << " via " << newedge );
283
284 // First check if the old edge was taken, if not, just delete it...
285 if (getEdgeWeight(oldedge) == 0) {
286 removeEdge(oldedge);
287 return;
288 }
289
290 Path P;
291 P[newedge.first] = 0;
292 P[newedge.second] = newedge.first;
293 const BasicBlock *BB = GetPath(newedge.second,oldedge.second,P,GetPathToExit | GetPathToDest);
294
295 double w = getEdgeWeight (oldedge);
296 DEBUG(dbgs() << ", Weight: " << format("%.20g",w) << "\n");
297 do {
298 const BasicBlock *Parent = P.find(BB)->second;
299 Edge e = getEdge(Parent,BB);
300 double oldw = getEdgeWeight(e);
301 double oldc = getExecutionCount(e.first);
302 setEdgeWeight(e, w+oldw);
303 if (Parent != oldedge.first) {
304 setExecutionCount(e.first, w+oldc);
305 }
306 BB = Parent;
307 } while (BB != newedge.first);
308 removeEdge(oldedge);
309}
310
311/// Replaces all occurences of RmBB in the ProfilingInfo with DestBB.
312/// This checks all edges of the function the blocks reside in and replaces the
313/// occurences of RmBB with DestBB.
314template<>
315void ProfileInfoT<Function,BasicBlock>::
316 replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB) {
317 DEBUG(dbgs() << "Replacing " << RmBB->getName()
318 << " with " << DestBB->getName() << "\n");
319 const Function *F = DestBB->getParent();
320 std::map<const Function*, EdgeWeights>::iterator J =
321 EdgeInformation.find(F);
322 if (J == EdgeInformation.end()) return;
323
324 Edge e, newedge;
325 bool erasededge = false;
326 EdgeWeights::iterator I = J->second.begin(), E = J->second.end();
327 while(I != E) {
328 e = (I++)->first;
329 bool foundedge = false; bool eraseedge = false;
330 if (e.first == RmBB) {
331 if (e.second == DestBB) {
332 eraseedge = true;
333 } else {
334 newedge = getEdge(DestBB, e.second);
335 foundedge = true;
336 }
337 }
338 if (e.second == RmBB) {
339 if (e.first == DestBB) {
340 eraseedge = true;
341 } else {
342 newedge = getEdge(e.first, DestBB);
343 foundedge = true;
344 }
345 }
346 if (foundedge) {
347 replaceEdge(e, newedge);
348 }
349 if (eraseedge) {
350 if (erasededge) {
351 Edge newedge = getEdge(DestBB, DestBB);
352 replaceEdge(e, newedge);
353 } else {
354 removeEdge(e);
355 erasededge = true;
356 }
357 }
358 }
359}
360
361/// Splits an edge in the ProfileInfo and redirects flow over NewBB.
362/// Since its possible that there is more than one edge in the CFG from FristBB
363/// to SecondBB its necessary to redirect the flow proporionally.
364template<>
365void ProfileInfoT<Function,BasicBlock>::splitEdge(const BasicBlock *FirstBB,
366 const BasicBlock *SecondBB,
367 const BasicBlock *NewBB,
368 bool MergeIdenticalEdges) {
369 const Function *F = FirstBB->getParent();
370 std::map<const Function*, EdgeWeights>::iterator J =
371 EdgeInformation.find(F);
372 if (J == EdgeInformation.end()) return;
373
374 // Generate edges and read current weight.
375 Edge e = getEdge(FirstBB, SecondBB);
376 Edge n1 = getEdge(FirstBB, NewBB);
377 Edge n2 = getEdge(NewBB, SecondBB);
378 EdgeWeights &ECs = J->second;
379 double w = ECs[e];
380
381 int succ_count = 0;
382 if (!MergeIdenticalEdges) {
383 // First count the edges from FristBB to SecondBB, if there is more than
384 // one, only slice out a proporional part for NewBB.
385 for(succ_const_iterator BBI = succ_begin(FirstBB), BBE = succ_end(FirstBB);
386 BBI != BBE; ++BBI) {
387 if (*BBI == SecondBB) succ_count++;
388 }
389 // When the NewBB is completely new, increment the count by one so that
390 // the counts are properly distributed.
391 if (getExecutionCount(NewBB) == ProfileInfo::MissingValue) succ_count++;
392 } else {
393 // When the edges are merged anyway, then redirect all flow.
394 succ_count = 1;
395 }
396
397 // We know now how many edges there are from FirstBB to SecondBB, reroute a
398 // proportional part of the edge weight over NewBB.
399 double neww = floor(w / succ_count);
400 ECs[n1] += neww;
401 ECs[n2] += neww;
402 BlockInformation[F][NewBB] += neww;
403 if (succ_count == 1) {
404 ECs.erase(e);
405 } else {
406 ECs[e] -= neww;
407 }
408}
409
410template<>
411void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *Old,
412 const BasicBlock* New) {
413 const Function *F = Old->getParent();
414 std::map<const Function*, EdgeWeights>::iterator J =
415 EdgeInformation.find(F);
416 if (J == EdgeInformation.end()) return;
417
418 DEBUG(dbgs() << "Splitting " << Old->getName() << " to " << New->getName() << "\n");
419
420 std::set<Edge> Edges;
421 for (EdgeWeights::iterator ewi = J->second.begin(), ewe = J->second.end();
422 ewi != ewe; ++ewi) {
423 Edge old = ewi->first;
424 if (old.first == Old) {
425 Edges.insert(old);
426 }
427 }
428 for (std::set<Edge>::iterator EI = Edges.begin(), EE = Edges.end();
429 EI != EE; ++EI) {
430 Edge newedge = getEdge(New, EI->second);
431 replaceEdge(*EI, newedge);
432 }
433
434 double w = getExecutionCount(Old);
435 setEdgeWeight(getEdge(Old, New), w);
436 setExecutionCount(New, w);
437}
438
439template<>
440void ProfileInfoT<Function,BasicBlock>::splitBlock(const BasicBlock *BB,
441 const BasicBlock* NewBB,
442 BasicBlock *const *Preds,
443 unsigned NumPreds) {
444 const Function *F = BB->getParent();
445 std::map<const Function*, EdgeWeights>::iterator J =
446 EdgeInformation.find(F);
447 if (J == EdgeInformation.end()) return;
448
449 DEBUG(dbgs() << "Splitting " << NumPreds << " Edges from " << BB->getName()
450 << " to " << NewBB->getName() << "\n");
451
452 // Collect weight that was redirected over NewBB.
453 double newweight = 0;
454
455 std::set<const BasicBlock *> ProcessedPreds;
456 // For all requestes Predecessors.
457 for (unsigned pred = 0; pred < NumPreds; ++pred) {
458 const BasicBlock * Pred = Preds[pred];
459 if (ProcessedPreds.insert(Pred).second) {
460 // Create edges and read old weight.
461 Edge oldedge = getEdge(Pred, BB);
462 Edge newedge = getEdge(Pred, NewBB);
463
464 // Remember how much weight was redirected.
465 newweight += getEdgeWeight(oldedge);
466
467 replaceEdge(oldedge,newedge);
468 }
469 }
470
471 Edge newedge = getEdge(NewBB,BB);
472 setEdgeWeight(newedge, newweight);
473 setExecutionCount(NewBB, newweight);
474}
475
476template<>
477void ProfileInfoT<Function,BasicBlock>::transfer(const Function *Old,
478 const Function *New) {
479 DEBUG(dbgs() << "Replacing Function " << Old->getName() << " with "
480 << New->getName() << "\n");
481 std::map<const Function*, EdgeWeights>::iterator J =
482 EdgeInformation.find(Old);
483 if(J != EdgeInformation.end()) {
484 EdgeInformation[New] = J->second;
485 }
486 EdgeInformation.erase(Old);
487 BlockInformation.erase(Old);
488 FunctionInformation.erase(Old);
489}
490
491static double readEdgeOrRemember(ProfileInfo::Edge edge, double w,
492 ProfileInfo::Edge &tocalc, unsigned &uncalc) {
493 if (w == ProfileInfo::MissingValue) {
494 tocalc = edge;
495 uncalc++;
496 return 0;
497 } else {
498 return w;
499 }
500}
501
502template<>
503bool ProfileInfoT<Function,BasicBlock>::
504 CalculateMissingEdge(const BasicBlock *BB, Edge &removed,
505 bool assumeEmptySelf) {
506 Edge edgetocalc;
507 unsigned uncalculated = 0;
508
509 // collect weights of all incoming and outgoing edges, rememer edges that
510 // have no value
511 double incount = 0;
512 SmallSet<const BasicBlock*,8> pred_visited;
513 const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
514 if (bbi==bbe) {
515 Edge e = getEdge(0,BB);
516 incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
517 }
518 for (;bbi != bbe; ++bbi) {
519 if (pred_visited.insert(*bbi)) {
520 Edge e = getEdge(*bbi,BB);
521 incount += readEdgeOrRemember(e, getEdgeWeight(e) ,edgetocalc,uncalculated);
522 }
523 }
524
525 double outcount = 0;
526 SmallSet<const BasicBlock*,8> succ_visited;
527 succ_const_iterator sbbi = succ_begin(BB), sbbe = succ_end(BB);
528 if (sbbi==sbbe) {
529 Edge e = getEdge(BB,0);
530 if (getEdgeWeight(e) == MissingValue) {
531 double w = getExecutionCount(BB);
532 if (w != MissingValue) {
533 setEdgeWeight(e,w);
534 removed = e;
535 }
536 }
537 outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
538 }
539 for (;sbbi != sbbe; ++sbbi) {
540 if (succ_visited.insert(*sbbi)) {
541 Edge e = getEdge(BB,*sbbi);
542 outcount += readEdgeOrRemember(e, getEdgeWeight(e), edgetocalc, uncalculated);
543 }
544 }
545
546 // if exactly one edge weight was missing, calculate it and remove it from
547 // spanning tree
548 if (uncalculated == 0 ) {
549 return true;
550 } else
551 if (uncalculated == 1) {
552 if (incount < outcount) {
553 EdgeInformation[BB->getParent()][edgetocalc] = outcount-incount;
554 } else {
555 EdgeInformation[BB->getParent()][edgetocalc] = incount-outcount;
556 }
557 DEBUG(dbgs() << "--Calc Edge Counter for " << edgetocalc << ": "
558 << format("%.20g", getEdgeWeight(edgetocalc)) << "\n");
559 removed = edgetocalc;
560 return true;
561 } else
562 if (uncalculated == 2 && assumeEmptySelf && edgetocalc.first == edgetocalc.second && incount == outcount) {
563 setEdgeWeight(edgetocalc, incount * 10);
564 removed = edgetocalc;
565 return true;
566 } else {
567 return false;
568 }
569}
570
571static void readEdge(ProfileInfo *PI, ProfileInfo::Edge e, double &calcw, std::set<ProfileInfo::Edge> &misscount) {
572 double w = PI->getEdgeWeight(e);
573 if (w != ProfileInfo::MissingValue) {
574 calcw += w;
575 } else {
576 misscount.insert(e);
577 }
578}
579
580template<>
581bool ProfileInfoT<Function,BasicBlock>::EstimateMissingEdges(const BasicBlock *BB) {
582 double inWeight = 0;
583 std::set<Edge> inMissing;
584 std::set<const BasicBlock*> ProcessedPreds;
585 const_pred_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 for ( ; sbbi != sbbe; ++sbbi ) {
602 if (ProcessedSuccs.insert(*sbbi).second) {
603 readEdge(this,getEdge(BB,*sbbi),outWeight,outMissing);
604 }
605 }
606
607 double share;
608 std::set<Edge>::iterator ei,ee;
609 if (inMissing.size() == 0 && outMissing.size() > 0) {
610 ei = outMissing.begin();
611 ee = outMissing.end();
612 share = inWeight/outMissing.size();
613 setExecutionCount(BB,inWeight);
614 } else
615 if (inMissing.size() > 0 && outMissing.size() == 0 && outWeight == 0) {
616 ei = inMissing.begin();
617 ee = inMissing.end();
618 share = 0;
619 setExecutionCount(BB,0);
620 } else
621 if (inMissing.size() == 0 && outMissing.size() == 0) {
622 setExecutionCount(BB,outWeight);
623 return true;
624 } else {
625 return false;
626 }
627 for ( ; ei != ee; ++ei ) {
628 setEdgeWeight(*ei,share);
629 }
630 return true;
631}
632
633template<>
634void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
635// if (getExecutionCount(&(F->getEntryBlock())) == 0) {
636// for (Function::const_iterator FI = F->begin(), FE = F->end();
637// FI != FE; ++FI) {
638// const BasicBlock* BB = &(*FI);
639// {
640// const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
641// if (NBB == End) {
642// setEdgeWeight(getEdge(0,BB),0);
643// }
644// for(;NBB != End; ++NBB) {
645// setEdgeWeight(getEdge(*NBB,BB),0);
646// }
647// }
648// {
649// succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
650// if (NBB == End) {
651// setEdgeWeight(getEdge(0,BB),0);
652// }
653// for(;NBB != End; ++NBB) {
654// setEdgeWeight(getEdge(*NBB,BB),0);
655// }
656// }
657// }
658// return;
659// }
660 // The set of BasicBlocks that are still unvisited.
661 std::set<const BasicBlock*> Unvisited;
662
663 // The set of return edges (Edges with no successors).
664 std::set<Edge> ReturnEdges;
665 double ReturnWeight = 0;
666
667 // First iterate over the whole function and collect:
668 // 1) The blocks in this function in the Unvisited set.
669 // 2) The return edges in the ReturnEdges set.
670 // 3) The flow that is leaving the function already via return edges.
671
672 // Data structure for searching the function.
673 std::queue<const BasicBlock *> BFS;
674 const BasicBlock *BB = &(F->getEntryBlock());
675 BFS.push(BB);
676 Unvisited.insert(BB);
677
678 while (BFS.size()) {
679 BB = BFS.front(); BFS.pop();
680 succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
681 if (NBB == End) {
682 Edge e = getEdge(BB,0);
683 double w = getEdgeWeight(e);
684 if (w == MissingValue) {
685 // If the return edge has no value, try to read value from block.
686 double bw = getExecutionCount(BB);
687 if (bw != MissingValue) {
688 setEdgeWeight(e,bw);
689 ReturnWeight += bw;
690 } else {
691 // If both return edge and block provide no value, collect edge.
692 ReturnEdges.insert(e);
693 }
694 } else {
695 // If the return edge has a proper value, collect it.
696 ReturnWeight += w;
697 }
698 }
699 for (;NBB != End; ++NBB) {
700 if (Unvisited.insert(*NBB).second) {
701 BFS.push(*NBB);
702 }
703 }
704 }
705
706 while (Unvisited.size() > 0) {
707 unsigned oldUnvisitedCount = Unvisited.size();
708 bool FoundPath = false;
709
710 // If there is only one edge left, calculate it.
711 if (ReturnEdges.size() == 1) {
712 ReturnWeight = getExecutionCount(&(F->getEntryBlock())) - ReturnWeight;
713
714 Edge e = *ReturnEdges.begin();
715 setEdgeWeight(e,ReturnWeight);
716 setExecutionCount(e.first,ReturnWeight);
717
718 Unvisited.erase(e.first);
719 ReturnEdges.erase(e);
720 continue;
721 }
722
723 // Calculate all blocks where only one edge is missing, this may also
724 // resolve furhter return edges.
725 std::set<const BasicBlock *>::iterator FI = Unvisited.begin(), FE = Unvisited.end();
726 while(FI != FE) {
727 const BasicBlock *BB = *FI; ++FI;
728 Edge e;
729 if(CalculateMissingEdge(BB,e,true)) {
730 if (BlockInformation[F].find(BB) == BlockInformation[F].end()) {
731 setExecutionCount(BB,getExecutionCount(BB));
732 }
733 Unvisited.erase(BB);
734 if (e.first != 0 && e.second == 0) {
735 ReturnEdges.erase(e);
736 ReturnWeight += getEdgeWeight(e);
737 }
738 }
739 }
740 if (oldUnvisitedCount > Unvisited.size()) continue;
741
742 // Estimate edge weights by dividing the flow proportionally.
743 FI = Unvisited.begin(), FE = Unvisited.end();
744 while(FI != FE) {
745 const BasicBlock *BB = *FI; ++FI;
746 const BasicBlock *Dest = 0;
747 bool AllEdgesHaveSameReturn = true;
748 // Check each Successor, these must all end up in the same or an empty
749 // return block otherwise its dangerous to do an estimation on them.
750 for (succ_const_iterator Succ = succ_begin(BB), End = succ_end(BB);
751 Succ != End; ++Succ) {
752 Path P;
753 GetPath(*Succ, 0, P, GetPathToExit);
754 if (Dest && Dest != P[0]) {
755 AllEdgesHaveSameReturn = false;
756 }
757 Dest = P[0];
758 }
759 if (AllEdgesHaveSameReturn) {
760 if(EstimateMissingEdges(BB)) {
761 Unvisited.erase(BB);
762 break;
763 }
764 }
765 }
766 if (oldUnvisitedCount > Unvisited.size()) continue;
767
768 // Check if there is a path to an block that has a known value and redirect
769 // flow accordingly.
770 FI = Unvisited.begin(), FE = Unvisited.end();
771 while(FI != FE && !FoundPath) {
772 // Fetch path.
773 const BasicBlock *BB = *FI; ++FI;
774 Path P;
775 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToValue);
776
777 // Calculate incoming flow.
778 double iw = 0; unsigned inmissing = 0; unsigned incount = 0; unsigned invalid = 0;
779 std::set<const BasicBlock *> Processed;
780 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
781 NBB != End; ++NBB) {
782 if (Processed.insert(*NBB).second) {
783 Edge e = getEdge(*NBB, BB);
784 double ew = getEdgeWeight(e);
785 if (ew != MissingValue) {
786 iw += ew;
787 invalid++;
788 } else {
789 // If the path contains the successor, this means its a backedge,
790 // do not count as missing.
791 if (P.find(*NBB) == P.end())
792 inmissing++;
793 }
794 incount++;
795 }
796 }
797 if (inmissing == incount) continue;
798 if (invalid == 0) continue;
799
800 // Subtract (already) outgoing flow.
801 Processed.clear();
802 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
803 NBB != End; ++NBB) {
804 if (Processed.insert(*NBB).second) {
805 Edge e = getEdge(BB, *NBB);
806 double ew = getEdgeWeight(e);
807 if (ew != MissingValue) {
808 iw -= ew;
809 }
810 }
811 }
812 if (iw < 0) continue;
813
814 // Check the recieving end of the path if it can handle the flow.
815 double ow = getExecutionCount(Dest);
816 Processed.clear();
817 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
818 NBB != End; ++NBB) {
819 if (Processed.insert(*NBB).second) {
820 Edge e = getEdge(BB, *NBB);
821 double ew = getEdgeWeight(e);
822 if (ew != MissingValue) {
823 ow -= ew;
824 }
825 }
826 }
827 if (ow < 0) continue;
828
829 // Determine how much flow shall be used.
830 double ew = getEdgeWeight(getEdge(P[Dest],Dest));
831 if (ew != MissingValue) {
832 ew = ew<ow?ew:ow;
833 ew = ew<iw?ew:iw;
834 } else {
835 if (inmissing == 0)
836 ew = iw;
837 }
838
839 // Create flow.
840 if (ew != MissingValue) {
841 do {
842 Edge e = getEdge(P[Dest],Dest);
843 if (getEdgeWeight(e) == MissingValue) {
844 setEdgeWeight(e,ew);
845 FoundPath = true;
846 }
847 Dest = P[Dest];
848 } while (Dest != BB);
849 }
850 }
851 if (FoundPath) continue;
852
853 // Calculate a block with self loop.
854 FI = Unvisited.begin(), FE = Unvisited.end();
855 while(FI != FE && !FoundPath) {
856 const BasicBlock *BB = *FI; ++FI;
857 bool SelfEdgeFound = false;
858 for (succ_const_iterator NBB = succ_begin(BB), End = succ_end(BB);
859 NBB != End; ++NBB) {
860 if (*NBB == BB) {
861 SelfEdgeFound = true;
862 break;
863 }
864 }
865 if (SelfEdgeFound) {
866 Edge e = getEdge(BB,BB);
867 if (getEdgeWeight(e) == MissingValue) {
868 double iw = 0;
869 std::set<const BasicBlock *> Processed;
870 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
871 NBB != End; ++NBB) {
872 if (Processed.insert(*NBB).second) {
873 Edge e = getEdge(*NBB, BB);
874 double ew = getEdgeWeight(e);
875 if (ew != MissingValue) {
876 iw += ew;
877 }
878 }
879 }
880 setEdgeWeight(e,iw * 10);
881 FoundPath = true;
882 }
883 }
884 }
885 if (FoundPath) continue;
886
887 // Determine backedges, set them to zero.
888 FI = Unvisited.begin(), FE = Unvisited.end();
889 while(FI != FE && !FoundPath) {
890 const BasicBlock *BB = *FI; ++FI;
891 const BasicBlock *Dest;
892 Path P;
893 bool BackEdgeFound = false;
894 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
895 NBB != End; ++NBB) {
896 Dest = GetPath(BB, *NBB, P, GetPathToDest | GetPathWithNewEdges);
897 if (Dest == *NBB) {
898 BackEdgeFound = true;
899 break;
900 }
901 }
902 if (BackEdgeFound) {
903 Edge e = getEdge(Dest,BB);
904 double w = getEdgeWeight(e);
905 if (w == MissingValue) {
906 setEdgeWeight(e,0);
907 FoundPath = true;
908 }
909 do {
910 Edge e = getEdge(P[Dest], Dest);
911 double w = getEdgeWeight(e);
912 if (w == MissingValue) {
913 setEdgeWeight(e,0);
914 FoundPath = true;
915 }
916 Dest = P[Dest];
917 } while (Dest != BB);
918 }
919 }
920 if (FoundPath) continue;
921
922 // Channel flow to return block.
923 FI = Unvisited.begin(), FE = Unvisited.end();
924 while(FI != FE && !FoundPath) {
925 const BasicBlock *BB = *FI; ++FI;
926
927 Path P;
928 const BasicBlock *Dest = GetPath(BB, 0, P, GetPathToExit | GetPathWithNewEdges);
929 Dest = P[0];
930 if (!Dest) continue;
931
932 if (getEdgeWeight(getEdge(Dest,0)) == MissingValue) {
933 // Calculate incoming flow.
934 double iw = 0;
935 std::set<const BasicBlock *> Processed;
936 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
937 NBB != End; ++NBB) {
938 if (Processed.insert(*NBB).second) {
939 Edge e = getEdge(*NBB, BB);
940 double ew = getEdgeWeight(e);
941 if (ew != MissingValue) {
942 iw += ew;
943 }
944 }
945 }
946 do {
947 Edge e = getEdge(P[Dest], Dest);
948 double w = getEdgeWeight(e);
949 if (w == MissingValue) {
950 setEdgeWeight(e,iw);
951 FoundPath = true;
952 } else {
953 assert(0 && "Edge should not have value already!");
954 }
955 Dest = P[Dest];
956 } while (Dest != BB);
957 }
958 }
959 if (FoundPath) continue;
960
961 // Speculatively set edges to zero.
962 FI = Unvisited.begin(), FE = Unvisited.end();
963 while(FI != FE && !FoundPath) {
964 const BasicBlock *BB = *FI; ++FI;
965
966 for (const_pred_iterator NBB = pred_begin(BB), End = pred_end(BB);
967 NBB != End; ++NBB) {
968 Edge e = getEdge(*NBB,BB);
969 double w = getEdgeWeight(e);
970 if (w == MissingValue) {
971 setEdgeWeight(e,0);
972 FoundPath = true;
973 break;
974 }
975 }
976 }
977 if (FoundPath) continue;
978
979 errs() << "{";
980 FI = Unvisited.begin(), FE = Unvisited.end();
981 while(FI != FE) {
982 const BasicBlock *BB = *FI; ++FI;
983 dbgs() << BB->getName();
984 if (FI != FE)
985 dbgs() << ",";
986 }
987 errs() << "}";
988
989 errs() << "ASSERT: could not repair function";
990 assert(0 && "could not repair function");
991 }
992
993 EdgeWeights J = EdgeInformation[F];
994 for (EdgeWeights::iterator EI = J.begin(), EE = J.end(); EI != EE; ++EI) {
995 Edge e = EI->first;
996
997 bool SuccFound = false;
998 if (e.first != 0) {
999 succ_const_iterator NBB = succ_begin(e.first), End = succ_end(e.first);
1000 if (NBB == End) {
1001 if (0 == e.second) {
1002 SuccFound = true;
1003 }
1004 }
1005 for (;NBB != End; ++NBB) {
1006 if (*NBB == e.second) {
1007 SuccFound = true;
1008 break;
1009 }
1010 }
1011 if (!SuccFound) {
1012 removeEdge(e);
1013 }
1014 }
1015 }
1016}
1017
1018raw_ostream& operator<<(raw_ostream &O, const Function *F) {
1019 return O << F->getName();
1020}
1021
1022raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
1023 return O << MF->getFunction()->getName() << "(MF)";
1024}
1025
1026raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
1027 return O << BB->getName();
1028}
1029
1030raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
1031 return O << MBB->getBasicBlock()->getName() << "(MB)";
1032}
1033
1034raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
1035 O << "(";
1036
1037 if (E.first)
1038 O << E.first;
1039 else
1040 O << "0";
1041
1042 O << ",";
1043
1044 if (E.second)
1045 O << E.second;
1046 else
1047 O << "0";
1048
1049 return O << ")";
1050}
1051
1052raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
1053 O << "(";
1054
1055 if (E.first)
1056 O << E.first;
1057 else
1058 O << "0";
1059
1060 O << ",";
1061
1062 if (E.second)
1063 O << E.second;
1064 else
1065 O << "0";
1066
1067 return O << ")";
1068}
1069
1070} // namespace llvm
1071
1072//===----------------------------------------------------------------------===//
1073// NoProfile ProfileInfo implementation
1074//
1075
1076namespace {
1077 struct NoProfileInfo : public ImmutablePass, public ProfileInfo {
1078 static char ID; // Class identification, replacement for typeinfo
1079 NoProfileInfo() : ImmutablePass(ID) {}
1080
1081 /// getAdjustedAnalysisPointer - This method is used when a pass implements
1082 /// an analysis interface through multiple inheritance. If needed, it
1083 /// should override this to adjust the this pointer as needed for the
1084 /// specified pass info.
1085 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) {
1086 if (PI == &ProfileInfo::ID)
1087 return (ProfileInfo*)this;
1088 return this;
1089 }
1090
1091 virtual const char *getPassName() const {
1092 return "NoProfileInfo";
1093 }
1094 };
1095} // End of anonymous namespace
1096
1097char NoProfileInfo::ID = 0;
1098// Register this pass...
1099INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile",
1100 "No Profile Information", false, true, true);
1101
1102ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); }
Note: See TracBrowser for help on using the repository browser.