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> 25 using namespace llvm; 26 27 namespace llvm { 28 template<> char ProfileInfoT<Function,BasicBlock>::ID = 0; 29 } 30 31 // Register the ProfileInfo interface, providing a nice name to refer to. 32 INITIALIZE_ANALYSIS_GROUP(ProfileInfo, "Profile Information", NoProfileInfo) 33 34 namespace llvm { 35 36 template <> 37 ProfileInfoT<MachineFunction, MachineBasicBlock>::ProfileInfoT() {} 38 template <> 39 ProfileInfoT<MachineFunction, MachineBasicBlock>::~ProfileInfoT() {} 40 41 template <> 42 ProfileInfoT<Function, BasicBlock>::ProfileInfoT() { 43 MachineProfile = 0; 44 } 45 template <> 46 ProfileInfoT<Function, BasicBlock>::~ProfileInfoT() { 47 if (MachineProfile) delete MachineProfile; 48 } 49 50 template<> 51 char ProfileInfoT<MachineFunction, MachineBasicBlock>::ID = 0; 52 53 template<> 54 const double ProfileInfoT<Function,BasicBlock>::MissingValue = -1; 55 56 template<> const 57 double ProfileInfoT<MachineFunction, MachineBasicBlock>::MissingValue = -1; 58 59 template<> double 60 ProfileInfoT<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 123 template<> 124 double 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 137 template<> 138 double 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 153 template<> 154 double 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 166 template<> 167 void 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 174 template<> 175 void 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 182 template<> 183 void 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 191 template<> 192 void 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 201 template<> 202 void 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 211 template<> 212 void 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 221 template<> 222 void 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 236 template<> 237 const 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 280 template<> 281 void 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. 315 template<> 316 void 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. 365 template<> 366 void 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 411 template<> 412 void 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 440 template<> 441 void 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 477 template<> 478 void 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 492 static 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 503 template<> 504 bool 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 572 static 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 581 template<> 582 bool 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 634 template<> 635 void 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 1019 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) { 1020 return O << MF->getFunction()->getName() << "(MF)"; 1021 } 1022 1023 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) { 1024 return O << MBB->getBasicBlock()->getName() << "(MB)"; 1025 } 1026 1027 raw_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 1051 namespace { 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 1074 char NoProfileInfo::ID = 0; 1075 // Register this pass... 1076 INITIALIZE_AG_PASS(NoProfileInfo, ProfileInfo, "no-profile", 1077 "No Profile Information", false, true, true) 1078 1079 ImmutablePass *llvm::createNoProfileInfoPass() { return new NoProfileInfo(); } 1080