1 //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===// 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 basic block placement transformations using the CFG 11 // structure and branch probability estimates. 12 // 13 // The pass strives to preserve the structure of the CFG (that is, retain 14 // a topological ordering of basic blocks) in the absence of a *strong* signal 15 // to the contrary from probabilities. However, within the CFG structure, it 16 // attempts to choose an ordering which favors placing more likely sequences of 17 // blocks adjacent to each other. 18 // 19 // The algorithm works from the inner-most loop within a function outward, and 20 // at each stage walks through the basic blocks, trying to coalesce them into 21 // sequential chains where allowed by the CFG (or demanded by heavy 22 // probabilities). Finally, it walks the blocks in topological order, and the 23 // first time it reaches a chain of basic blocks, it schedules them in the 24 // function in-order. 25 // 26 //===----------------------------------------------------------------------===// 27 28 #define DEBUG_TYPE "block-placement2" 29 #include "llvm/CodeGen/Passes.h" 30 #include "llvm/ADT/DenseMap.h" 31 #include "llvm/ADT/SmallPtrSet.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/Statistic.h" 34 #include "llvm/CodeGen/MachineBasicBlock.h" 35 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 36 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 37 #include "llvm/CodeGen/MachineFunction.h" 38 #include "llvm/CodeGen/MachineFunctionPass.h" 39 #include "llvm/CodeGen/MachineLoopInfo.h" 40 #include "llvm/CodeGen/MachineModuleInfo.h" 41 #include "llvm/Support/Allocator.h" 42 #include "llvm/Support/Debug.h" 43 #include "llvm/Target/TargetInstrInfo.h" 44 #include "llvm/Target/TargetLowering.h" 45 #include <algorithm> 46 using namespace llvm; 47 48 STATISTIC(NumCondBranches, "Number of conditional branches"); 49 STATISTIC(NumUncondBranches, "Number of uncondittional branches"); 50 STATISTIC(CondBranchTakenFreq, 51 "Potential frequency of taking conditional branches"); 52 STATISTIC(UncondBranchTakenFreq, 53 "Potential frequency of taking unconditional branches"); 54 55 namespace { 56 class BlockChain; 57 /// \brief Type for our function-wide basic block -> block chain mapping. 58 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 59 } 60 61 namespace { 62 /// \brief A chain of blocks which will be laid out contiguously. 63 /// 64 /// This is the datastructure representing a chain of consecutive blocks that 65 /// are profitable to layout together in order to maximize fallthrough 66 /// probabilities and code locality. We also can use a block chain to represent 67 /// a sequence of basic blocks which have some external (correctness) 68 /// requirement for sequential layout. 69 /// 70 /// Chains can be built around a single basic block and can be merged to grow 71 /// them. They participate in a block-to-chain mapping, which is updated 72 /// automatically as chains are merged together. 73 class BlockChain { 74 /// \brief The sequence of blocks belonging to this chain. 75 /// 76 /// This is the sequence of blocks for a particular chain. These will be laid 77 /// out in-order within the function. 78 SmallVector<MachineBasicBlock *, 4> Blocks; 79 80 /// \brief A handle to the function-wide basic block to block chain mapping. 81 /// 82 /// This is retained in each block chain to simplify the computation of child 83 /// block chains for SCC-formation and iteration. We store the edges to child 84 /// basic blocks, and map them back to their associated chains using this 85 /// structure. 86 BlockToChainMapType &BlockToChain; 87 88 public: 89 /// \brief Construct a new BlockChain. 90 /// 91 /// This builds a new block chain representing a single basic block in the 92 /// function. It also registers itself as the chain that block participates 93 /// in with the BlockToChain mapping. 94 BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) 95 : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { 96 assert(BB && "Cannot create a chain with a null basic block"); 97 BlockToChain[BB] = this; 98 } 99 100 /// \brief Iterator over blocks within the chain. 101 typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator; 102 103 /// \brief Beginning of blocks within the chain. 104 iterator begin() { return Blocks.begin(); } 105 106 /// \brief End of blocks within the chain. 107 iterator end() { return Blocks.end(); } 108 109 /// \brief Merge a block chain into this one. 110 /// 111 /// This routine merges a block chain into this one. It takes care of forming 112 /// a contiguous sequence of basic blocks, updating the edge list, and 113 /// updating the block -> chain mapping. It does not free or tear down the 114 /// old chain, but the old chain's block list is no longer valid. 115 void merge(MachineBasicBlock *BB, BlockChain *Chain) { 116 assert(BB); 117 assert(!Blocks.empty()); 118 119 // Fast path in case we don't have a chain already. 120 if (!Chain) { 121 assert(!BlockToChain[BB]); 122 Blocks.push_back(BB); 123 BlockToChain[BB] = this; 124 return; 125 } 126 127 assert(BB == *Chain->begin()); 128 assert(Chain->begin() != Chain->end()); 129 130 // Update the incoming blocks to point to this chain, and add them to the 131 // chain structure. 132 for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); 133 BI != BE; ++BI) { 134 Blocks.push_back(*BI); 135 assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain"); 136 BlockToChain[*BI] = this; 137 } 138 } 139 140 #ifndef NDEBUG 141 /// \brief Dump the blocks in this chain. 142 void dump() LLVM_ATTRIBUTE_USED { 143 for (iterator I = begin(), E = end(); I != E; ++I) 144 (*I)->dump(); 145 } 146 #endif // NDEBUG 147 148 /// \brief Count of predecessors within the loop currently being processed. 149 /// 150 /// This count is updated at each loop we process to represent the number of 151 /// in-loop predecessors of this chain. 152 unsigned LoopPredecessors; 153 }; 154 } 155 156 namespace { 157 class MachineBlockPlacement : public MachineFunctionPass { 158 /// \brief A typedef for a block filter set. 159 typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet; 160 161 /// \brief A handle to the branch probability pass. 162 const MachineBranchProbabilityInfo *MBPI; 163 164 /// \brief A handle to the function-wide block frequency pass. 165 const MachineBlockFrequencyInfo *MBFI; 166 167 /// \brief A handle to the loop info. 168 const MachineLoopInfo *MLI; 169 170 /// \brief A handle to the target's instruction info. 171 const TargetInstrInfo *TII; 172 173 /// \brief A handle to the target's lowering info. 174 const TargetLoweringBase *TLI; 175 176 /// \brief Allocator and owner of BlockChain structures. 177 /// 178 /// We build BlockChains lazily while processing the loop structure of 179 /// a function. To reduce malloc traffic, we allocate them using this 180 /// slab-like allocator, and destroy them after the pass completes. An 181 /// important guarantee is that this allocator produces stable pointers to 182 /// the chains. 183 SpecificBumpPtrAllocator<BlockChain> ChainAllocator; 184 185 /// \brief Function wide BasicBlock to BlockChain mapping. 186 /// 187 /// This mapping allows efficiently moving from any given basic block to the 188 /// BlockChain it participates in, if any. We use it to, among other things, 189 /// allow implicitly defining edges between chains as the existing edges 190 /// between basic blocks. 191 DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain; 192 193 void markChainSuccessors(BlockChain &Chain, 194 MachineBasicBlock *LoopHeaderBB, 195 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 196 const BlockFilterSet *BlockFilter = 0); 197 MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, 198 BlockChain &Chain, 199 const BlockFilterSet *BlockFilter); 200 MachineBasicBlock *selectBestCandidateBlock( 201 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 202 const BlockFilterSet *BlockFilter); 203 MachineBasicBlock *getFirstUnplacedBlock( 204 MachineFunction &F, 205 const BlockChain &PlacedChain, 206 MachineFunction::iterator &PrevUnplacedBlockIt, 207 const BlockFilterSet *BlockFilter); 208 void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 209 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 210 const BlockFilterSet *BlockFilter = 0); 211 MachineBasicBlock *findBestLoopTop(MachineLoop &L, 212 const BlockFilterSet &LoopBlockSet); 213 MachineBasicBlock *findBestLoopExit(MachineFunction &F, 214 MachineLoop &L, 215 const BlockFilterSet &LoopBlockSet); 216 void buildLoopChains(MachineFunction &F, MachineLoop &L); 217 void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, 218 const BlockFilterSet &LoopBlockSet); 219 void buildCFGChains(MachineFunction &F); 220 221 public: 222 static char ID; // Pass identification, replacement for typeid 223 MachineBlockPlacement() : MachineFunctionPass(ID) { 224 initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); 225 } 226 227 bool runOnMachineFunction(MachineFunction &F); 228 229 void getAnalysisUsage(AnalysisUsage &AU) const { 230 AU.addRequired<MachineBranchProbabilityInfo>(); 231 AU.addRequired<MachineBlockFrequencyInfo>(); 232 AU.addRequired<MachineLoopInfo>(); 233 MachineFunctionPass::getAnalysisUsage(AU); 234 } 235 }; 236 } 237 238 char MachineBlockPlacement::ID = 0; 239 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; 240 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 241 "Branch Probability Basic Block Placement", false, false) 242 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 243 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 244 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 245 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 246 "Branch Probability Basic Block Placement", false, false) 247 248 #ifndef NDEBUG 249 /// \brief Helper to print the name of a MBB. 250 /// 251 /// Only used by debug logging. 252 static std::string getBlockName(MachineBasicBlock *BB) { 253 std::string Result; 254 raw_string_ostream OS(Result); 255 OS << "BB#" << BB->getNumber() 256 << " (derived from LLVM BB '" << BB->getName() << "')"; 257 OS.flush(); 258 return Result; 259 } 260 261 /// \brief Helper to print the number of a MBB. 262 /// 263 /// Only used by debug logging. 264 static std::string getBlockNum(MachineBasicBlock *BB) { 265 std::string Result; 266 raw_string_ostream OS(Result); 267 OS << "BB#" << BB->getNumber(); 268 OS.flush(); 269 return Result; 270 } 271 #endif 272 273 /// \brief Mark a chain's successors as having one fewer preds. 274 /// 275 /// When a chain is being merged into the "placed" chain, this routine will 276 /// quickly walk the successors of each block in the chain and mark them as 277 /// having one fewer active predecessor. It also adds any successors of this 278 /// chain which reach the zero-predecessor state to the worklist passed in. 279 void MachineBlockPlacement::markChainSuccessors( 280 BlockChain &Chain, 281 MachineBasicBlock *LoopHeaderBB, 282 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 283 const BlockFilterSet *BlockFilter) { 284 // Walk all the blocks in this chain, marking their successors as having 285 // a predecessor placed. 286 for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); 287 CBI != CBE; ++CBI) { 288 // Add any successors for which this is the only un-placed in-loop 289 // predecessor to the worklist as a viable candidate for CFG-neutral 290 // placement. No subsequent placement of this block will violate the CFG 291 // shape, so we get to use heuristics to choose a favorable placement. 292 for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), 293 SE = (*CBI)->succ_end(); 294 SI != SE; ++SI) { 295 if (BlockFilter && !BlockFilter->count(*SI)) 296 continue; 297 BlockChain &SuccChain = *BlockToChain[*SI]; 298 // Disregard edges within a fixed chain, or edges to the loop header. 299 if (&Chain == &SuccChain || *SI == LoopHeaderBB) 300 continue; 301 302 // This is a cross-chain edge that is within the loop, so decrement the 303 // loop predecessor count of the destination chain. 304 if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) 305 BlockWorkList.push_back(*SuccChain.begin()); 306 } 307 } 308 } 309 310 /// \brief Select the best successor for a block. 311 /// 312 /// This looks across all successors of a particular block and attempts to 313 /// select the "best" one to be the layout successor. It only considers direct 314 /// successors which also pass the block filter. It will attempt to avoid 315 /// breaking CFG structure, but cave and break such structures in the case of 316 /// very hot successor edges. 317 /// 318 /// \returns The best successor block found, or null if none are viable. 319 MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 320 MachineBasicBlock *BB, BlockChain &Chain, 321 const BlockFilterSet *BlockFilter) { 322 const BranchProbability HotProb(4, 5); // 80% 323 324 MachineBasicBlock *BestSucc = 0; 325 // FIXME: Due to the performance of the probability and weight routines in 326 // the MBPI analysis, we manually compute probabilities using the edge 327 // weights. This is suboptimal as it means that the somewhat subtle 328 // definition of edge weight semantics is encoded here as well. We should 329 // improve the MBPI interface to efficiently support query patterns such as 330 // this. 331 uint32_t BestWeight = 0; 332 uint32_t WeightScale = 0; 333 uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); 334 DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 335 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 336 SE = BB->succ_end(); 337 SI != SE; ++SI) { 338 if (BlockFilter && !BlockFilter->count(*SI)) 339 continue; 340 BlockChain &SuccChain = *BlockToChain[*SI]; 341 if (&SuccChain == &Chain) { 342 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); 343 continue; 344 } 345 if (*SI != *SuccChain.begin()) { 346 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n"); 347 continue; 348 } 349 350 uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI); 351 BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 352 353 // Only consider successors which are either "hot", or wouldn't violate 354 // any CFG constraints. 355 if (SuccChain.LoopPredecessors != 0) { 356 if (SuccProb < HotProb) { 357 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); 358 continue; 359 } 360 361 // Make sure that a hot successor doesn't have a globally more important 362 // predecessor. 363 BlockFrequency CandidateEdgeFreq 364 = MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl(); 365 bool BadCFGConflict = false; 366 for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(), 367 PE = (*SI)->pred_end(); 368 PI != PE; ++PI) { 369 if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) || 370 BlockToChain[*PI] == &Chain) 371 continue; 372 BlockFrequency PredEdgeFreq 373 = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI); 374 if (PredEdgeFreq >= CandidateEdgeFreq) { 375 BadCFGConflict = true; 376 break; 377 } 378 } 379 if (BadCFGConflict) { 380 DEBUG(dbgs() << " " << getBlockName(*SI) 381 << " -> non-cold CFG conflict\n"); 382 continue; 383 } 384 } 385 386 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 387 << " (prob)" 388 << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") 389 << "\n"); 390 if (BestSucc && BestWeight >= SuccWeight) 391 continue; 392 BestSucc = *SI; 393 BestWeight = SuccWeight; 394 } 395 return BestSucc; 396 } 397 398 namespace { 399 /// \brief Predicate struct to detect blocks already placed. 400 class IsBlockPlaced { 401 const BlockChain &PlacedChain; 402 const BlockToChainMapType &BlockToChain; 403 404 public: 405 IsBlockPlaced(const BlockChain &PlacedChain, 406 const BlockToChainMapType &BlockToChain) 407 : PlacedChain(PlacedChain), BlockToChain(BlockToChain) {} 408 409 bool operator()(MachineBasicBlock *BB) const { 410 return BlockToChain.lookup(BB) == &PlacedChain; 411 } 412 }; 413 } 414 415 /// \brief Select the best block from a worklist. 416 /// 417 /// This looks through the provided worklist as a list of candidate basic 418 /// blocks and select the most profitable one to place. The definition of 419 /// profitable only really makes sense in the context of a loop. This returns 420 /// the most frequently visited block in the worklist, which in the case of 421 /// a loop, is the one most desirable to be physically close to the rest of the 422 /// loop body in order to improve icache behavior. 423 /// 424 /// \returns The best block found, or null if none are viable. 425 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( 426 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 427 const BlockFilterSet *BlockFilter) { 428 // Once we need to walk the worklist looking for a candidate, cleanup the 429 // worklist of already placed entries. 430 // FIXME: If this shows up on profiles, it could be folded (at the cost of 431 // some code complexity) into the loop below. 432 WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(), 433 IsBlockPlaced(Chain, BlockToChain)), 434 WorkList.end()); 435 436 MachineBasicBlock *BestBlock = 0; 437 BlockFrequency BestFreq; 438 for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = WorkList.begin(), 439 WBE = WorkList.end(); 440 WBI != WBE; ++WBI) { 441 BlockChain &SuccChain = *BlockToChain[*WBI]; 442 if (&SuccChain == &Chain) { 443 DEBUG(dbgs() << " " << getBlockName(*WBI) 444 << " -> Already merged!\n"); 445 continue; 446 } 447 assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); 448 449 BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); 450 DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq 451 << " (freq)\n"); 452 if (BestBlock && BestFreq >= CandidateFreq) 453 continue; 454 BestBlock = *WBI; 455 BestFreq = CandidateFreq; 456 } 457 return BestBlock; 458 } 459 460 /// \brief Retrieve the first unplaced basic block. 461 /// 462 /// This routine is called when we are unable to use the CFG to walk through 463 /// all of the basic blocks and form a chain due to unnatural loops in the CFG. 464 /// We walk through the function's blocks in order, starting from the 465 /// LastUnplacedBlockIt. We update this iterator on each call to avoid 466 /// re-scanning the entire sequence on repeated calls to this routine. 467 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( 468 MachineFunction &F, const BlockChain &PlacedChain, 469 MachineFunction::iterator &PrevUnplacedBlockIt, 470 const BlockFilterSet *BlockFilter) { 471 for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E; 472 ++I) { 473 if (BlockFilter && !BlockFilter->count(I)) 474 continue; 475 if (BlockToChain[I] != &PlacedChain) { 476 PrevUnplacedBlockIt = I; 477 // Now select the head of the chain to which the unplaced block belongs 478 // as the block to place. This will force the entire chain to be placed, 479 // and satisfies the requirements of merging chains. 480 return *BlockToChain[I]->begin(); 481 } 482 } 483 return 0; 484 } 485 486 void MachineBlockPlacement::buildChain( 487 MachineBasicBlock *BB, 488 BlockChain &Chain, 489 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 490 const BlockFilterSet *BlockFilter) { 491 assert(BB); 492 assert(BlockToChain[BB] == &Chain); 493 MachineFunction &F = *BB->getParent(); 494 MachineFunction::iterator PrevUnplacedBlockIt = F.begin(); 495 496 MachineBasicBlock *LoopHeaderBB = BB; 497 markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); 498 BB = *llvm::prior(Chain.end()); 499 for (;;) { 500 assert(BB); 501 assert(BlockToChain[BB] == &Chain); 502 assert(*llvm::prior(Chain.end()) == BB); 503 504 // Look for the best viable successor if there is one to place immediately 505 // after this block. 506 MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); 507 508 // If an immediate successor isn't available, look for the best viable 509 // block among those we've identified as not violating the loop's CFG at 510 // this point. This won't be a fallthrough, but it will increase locality. 511 if (!BestSucc) 512 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); 513 514 if (!BestSucc) { 515 BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, 516 BlockFilter); 517 if (!BestSucc) 518 break; 519 520 DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " 521 "layout successor until the CFG reduces\n"); 522 } 523 524 // Place this block, updating the datastructures to reflect its placement. 525 BlockChain &SuccChain = *BlockToChain[BestSucc]; 526 // Zero out LoopPredecessors for the successor we're about to merge in case 527 // we selected a successor that didn't fit naturally into the CFG. 528 SuccChain.LoopPredecessors = 0; 529 DEBUG(dbgs() << "Merging from " << getBlockNum(BB) 530 << " to " << getBlockNum(BestSucc) << "\n"); 531 markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); 532 Chain.merge(BestSucc, &SuccChain); 533 BB = *llvm::prior(Chain.end()); 534 } 535 536 DEBUG(dbgs() << "Finished forming chain for header block " 537 << getBlockNum(*Chain.begin()) << "\n"); 538 } 539 540 /// \brief Find the best loop top block for layout. 541 /// 542 /// Look for a block which is strictly better than the loop header for laying 543 /// out at the top of the loop. This looks for one and only one pattern: 544 /// a latch block with no conditional exit. This block will cause a conditional 545 /// jump around it or will be the bottom of the loop if we lay it out in place, 546 /// but if it it doesn't end up at the bottom of the loop for any reason, 547 /// rotation alone won't fix it. Because such a block will always result in an 548 /// unconditional jump (for the backedge) rotating it in front of the loop 549 /// header is always profitable. 550 MachineBasicBlock * 551 MachineBlockPlacement::findBestLoopTop(MachineLoop &L, 552 const BlockFilterSet &LoopBlockSet) { 553 // Check that the header hasn't been fused with a preheader block due to 554 // crazy branches. If it has, we need to start with the header at the top to 555 // prevent pulling the preheader into the loop body. 556 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 557 if (!LoopBlockSet.count(*HeaderChain.begin())) 558 return L.getHeader(); 559 560 DEBUG(dbgs() << "Finding best loop top for: " 561 << getBlockName(L.getHeader()) << "\n"); 562 563 BlockFrequency BestPredFreq; 564 MachineBasicBlock *BestPred = 0; 565 for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(), 566 PE = L.getHeader()->pred_end(); 567 PI != PE; ++PI) { 568 MachineBasicBlock *Pred = *PI; 569 if (!LoopBlockSet.count(Pred)) 570 continue; 571 DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", " 572 << Pred->succ_size() << " successors, " 573 << MBFI->getBlockFreq(Pred) << " freq\n"); 574 if (Pred->succ_size() > 1) 575 continue; 576 577 BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); 578 if (!BestPred || PredFreq > BestPredFreq || 579 (!(PredFreq < BestPredFreq) && 580 Pred->isLayoutSuccessor(L.getHeader()))) { 581 BestPred = Pred; 582 BestPredFreq = PredFreq; 583 } 584 } 585 586 // If no direct predecessor is fine, just use the loop header. 587 if (!BestPred) 588 return L.getHeader(); 589 590 // Walk backwards through any straight line of predecessors. 591 while (BestPred->pred_size() == 1 && 592 (*BestPred->pred_begin())->succ_size() == 1 && 593 *BestPred->pred_begin() != L.getHeader()) 594 BestPred = *BestPred->pred_begin(); 595 596 DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); 597 return BestPred; 598 } 599 600 601 /// \brief Find the best loop exiting block for layout. 602 /// 603 /// This routine implements the logic to analyze the loop looking for the best 604 /// block to layout at the top of the loop. Typically this is done to maximize 605 /// fallthrough opportunities. 606 MachineBasicBlock * 607 MachineBlockPlacement::findBestLoopExit(MachineFunction &F, 608 MachineLoop &L, 609 const BlockFilterSet &LoopBlockSet) { 610 // We don't want to layout the loop linearly in all cases. If the loop header 611 // is just a normal basic block in the loop, we want to look for what block 612 // within the loop is the best one to layout at the top. However, if the loop 613 // header has be pre-merged into a chain due to predecessors not having 614 // analyzable branches, *and* the predecessor it is merged with is *not* part 615 // of the loop, rotating the header into the middle of the loop will create 616 // a non-contiguous range of blocks which is Very Bad. So start with the 617 // header and only rotate if safe. 618 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 619 if (!LoopBlockSet.count(*HeaderChain.begin())) 620 return 0; 621 622 BlockFrequency BestExitEdgeFreq; 623 unsigned BestExitLoopDepth = 0; 624 MachineBasicBlock *ExitingBB = 0; 625 // If there are exits to outer loops, loop rotation can severely limit 626 // fallthrough opportunites unless it selects such an exit. Keep a set of 627 // blocks where rotating to exit with that block will reach an outer loop. 628 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; 629 630 DEBUG(dbgs() << "Finding best loop exit for: " 631 << getBlockName(L.getHeader()) << "\n"); 632 for (MachineLoop::block_iterator I = L.block_begin(), 633 E = L.block_end(); 634 I != E; ++I) { 635 BlockChain &Chain = *BlockToChain[*I]; 636 // Ensure that this block is at the end of a chain; otherwise it could be 637 // mid-way through an inner loop or a successor of an analyzable branch. 638 if (*I != *llvm::prior(Chain.end())) 639 continue; 640 641 // Now walk the successors. We need to establish whether this has a viable 642 // exiting successor and whether it has a viable non-exiting successor. 643 // We store the old exiting state and restore it if a viable looping 644 // successor isn't found. 645 MachineBasicBlock *OldExitingBB = ExitingBB; 646 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; 647 bool HasLoopingSucc = false; 648 // FIXME: Due to the performance of the probability and weight routines in 649 // the MBPI analysis, we use the internal weights and manually compute the 650 // probabilities to avoid quadratic behavior. 651 uint32_t WeightScale = 0; 652 uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); 653 for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), 654 SE = (*I)->succ_end(); 655 SI != SE; ++SI) { 656 if ((*SI)->isLandingPad()) 657 continue; 658 if (*SI == *I) 659 continue; 660 BlockChain &SuccChain = *BlockToChain[*SI]; 661 // Don't split chains, either this chain or the successor's chain. 662 if (&Chain == &SuccChain) { 663 DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 664 << getBlockName(*SI) << " (chain conflict)\n"); 665 continue; 666 } 667 668 uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); 669 if (LoopBlockSet.count(*SI)) { 670 DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " 671 << getBlockName(*SI) << " (" << SuccWeight << ")\n"); 672 HasLoopingSucc = true; 673 continue; 674 } 675 676 unsigned SuccLoopDepth = 0; 677 if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) { 678 SuccLoopDepth = ExitLoop->getLoopDepth(); 679 if (ExitLoop->contains(&L)) 680 BlocksExitingToOuterLoop.insert(*I); 681 } 682 683 BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 684 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; 685 DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 686 << getBlockName(*SI) << " [L:" << SuccLoopDepth 687 << "] (" << ExitEdgeFreq << ")\n"); 688 // Note that we slightly bias this toward an existing layout successor to 689 // retain incoming order in the absence of better information. 690 // FIXME: Should we bias this more strongly? It's pretty weak. 691 if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || 692 ExitEdgeFreq > BestExitEdgeFreq || 693 ((*I)->isLayoutSuccessor(*SI) && 694 !(ExitEdgeFreq < BestExitEdgeFreq))) { 695 BestExitEdgeFreq = ExitEdgeFreq; 696 ExitingBB = *I; 697 } 698 } 699 700 // Restore the old exiting state, no viable looping successor was found. 701 if (!HasLoopingSucc) { 702 ExitingBB = OldExitingBB; 703 BestExitEdgeFreq = OldBestExitEdgeFreq; 704 continue; 705 } 706 } 707 // Without a candidate exiting block or with only a single block in the 708 // loop, just use the loop header to layout the loop. 709 if (!ExitingBB || L.getNumBlocks() == 1) 710 return 0; 711 712 // Also, if we have exit blocks which lead to outer loops but didn't select 713 // one of them as the exiting block we are rotating toward, disable loop 714 // rotation altogether. 715 if (!BlocksExitingToOuterLoop.empty() && 716 !BlocksExitingToOuterLoop.count(ExitingBB)) 717 return 0; 718 719 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 720 return ExitingBB; 721 } 722 723 /// \brief Attempt to rotate an exiting block to the bottom of the loop. 724 /// 725 /// Once we have built a chain, try to rotate it to line up the hot exit block 726 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary 727 /// branches. For example, if the loop has fallthrough into its header and out 728 /// of its bottom already, don't rotate it. 729 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, 730 MachineBasicBlock *ExitingBB, 731 const BlockFilterSet &LoopBlockSet) { 732 if (!ExitingBB) 733 return; 734 735 MachineBasicBlock *Top = *LoopChain.begin(); 736 bool ViableTopFallthrough = false; 737 for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), 738 PE = Top->pred_end(); 739 PI != PE; ++PI) { 740 BlockChain *PredChain = BlockToChain[*PI]; 741 if (!LoopBlockSet.count(*PI) && 742 (!PredChain || *PI == *llvm::prior(PredChain->end()))) { 743 ViableTopFallthrough = true; 744 break; 745 } 746 } 747 748 // If the header has viable fallthrough, check whether the current loop 749 // bottom is a viable exiting block. If so, bail out as rotating will 750 // introduce an unnecessary branch. 751 if (ViableTopFallthrough) { 752 MachineBasicBlock *Bottom = *llvm::prior(LoopChain.end()); 753 for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), 754 SE = Bottom->succ_end(); 755 SI != SE; ++SI) { 756 BlockChain *SuccChain = BlockToChain[*SI]; 757 if (!LoopBlockSet.count(*SI) && 758 (!SuccChain || *SI == *SuccChain->begin())) 759 return; 760 } 761 } 762 763 BlockChain::iterator ExitIt = std::find(LoopChain.begin(), LoopChain.end(), 764 ExitingBB); 765 if (ExitIt == LoopChain.end()) 766 return; 767 768 std::rotate(LoopChain.begin(), llvm::next(ExitIt), LoopChain.end()); 769 } 770 771 /// \brief Forms basic block chains from the natural loop structures. 772 /// 773 /// These chains are designed to preserve the existing *structure* of the code 774 /// as much as possible. We can then stitch the chains together in a way which 775 /// both preserves the topological structure and minimizes taken conditional 776 /// branches. 777 void MachineBlockPlacement::buildLoopChains(MachineFunction &F, 778 MachineLoop &L) { 779 // First recurse through any nested loops, building chains for those inner 780 // loops. 781 for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 782 buildLoopChains(F, **LI); 783 784 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 785 BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 786 787 // First check to see if there is an obviously preferable top block for the 788 // loop. This will default to the header, but may end up as one of the 789 // predecessors to the header if there is one which will result in strictly 790 // fewer branches in the loop body. 791 MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); 792 793 // If we selected just the header for the loop top, look for a potentially 794 // profitable exit block in the event that rotating the loop can eliminate 795 // branches by placing an exit edge at the bottom. 796 MachineBasicBlock *ExitingBB = 0; 797 if (LoopTop == L.getHeader()) 798 ExitingBB = findBestLoopExit(F, L, LoopBlockSet); 799 800 BlockChain &LoopChain = *BlockToChain[LoopTop]; 801 802 // FIXME: This is a really lame way of walking the chains in the loop: we 803 // walk the blocks, and use a set to prevent visiting a particular chain 804 // twice. 805 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 806 assert(LoopChain.LoopPredecessors == 0); 807 UpdatedPreds.insert(&LoopChain); 808 for (MachineLoop::block_iterator BI = L.block_begin(), 809 BE = L.block_end(); 810 BI != BE; ++BI) { 811 BlockChain &Chain = *BlockToChain[*BI]; 812 if (!UpdatedPreds.insert(&Chain)) 813 continue; 814 815 assert(Chain.LoopPredecessors == 0); 816 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 817 BCI != BCE; ++BCI) { 818 assert(BlockToChain[*BCI] == &Chain); 819 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 820 PE = (*BCI)->pred_end(); 821 PI != PE; ++PI) { 822 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 823 continue; 824 ++Chain.LoopPredecessors; 825 } 826 } 827 828 if (Chain.LoopPredecessors == 0) 829 BlockWorkList.push_back(*Chain.begin()); 830 } 831 832 buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); 833 rotateLoop(LoopChain, ExitingBB, LoopBlockSet); 834 835 DEBUG({ 836 // Crash at the end so we get all of the debugging output first. 837 bool BadLoop = false; 838 if (LoopChain.LoopPredecessors) { 839 BadLoop = true; 840 dbgs() << "Loop chain contains a block without its preds placed!\n" 841 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 842 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 843 } 844 for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 845 BCI != BCE; ++BCI) { 846 dbgs() << " ... " << getBlockName(*BCI) << "\n"; 847 if (!LoopBlockSet.erase(*BCI)) { 848 // We don't mark the loop as bad here because there are real situations 849 // where this can occur. For example, with an unanalyzable fallthrough 850 // from a loop block to a non-loop block or vice versa. 851 dbgs() << "Loop chain contains a block not contained by the loop!\n" 852 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 853 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 854 << " Bad block: " << getBlockName(*BCI) << "\n"; 855 } 856 } 857 858 if (!LoopBlockSet.empty()) { 859 BadLoop = true; 860 for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), 861 LBE = LoopBlockSet.end(); 862 LBI != LBE; ++LBI) 863 dbgs() << "Loop contains blocks never placed into a chain!\n" 864 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 865 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 866 << " Bad block: " << getBlockName(*LBI) << "\n"; 867 } 868 assert(!BadLoop && "Detected problems with the placement of this loop."); 869 }); 870 } 871 872 void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 873 // Ensure that every BB in the function has an associated chain to simplify 874 // the assumptions of the remaining algorithm. 875 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 876 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 877 MachineBasicBlock *BB = FI; 878 BlockChain *Chain 879 = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 880 // Also, merge any blocks which we cannot reason about and must preserve 881 // the exact fallthrough behavior for. 882 for (;;) { 883 Cond.clear(); 884 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 885 if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 886 break; 887 888 MachineFunction::iterator NextFI(llvm::next(FI)); 889 MachineBasicBlock *NextBB = NextFI; 890 // Ensure that the layout successor is a viable block, as we know that 891 // fallthrough is a possibility. 892 assert(NextFI != FE && "Can't fallthrough past the last block."); 893 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 894 << getBlockName(BB) << " -> " << getBlockName(NextBB) 895 << "\n"); 896 Chain->merge(NextBB, 0); 897 FI = NextFI; 898 BB = NextBB; 899 } 900 } 901 902 // Build any loop-based chains. 903 for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 904 ++LI) 905 buildLoopChains(F, **LI); 906 907 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 908 909 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 910 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 911 MachineBasicBlock *BB = &*FI; 912 BlockChain &Chain = *BlockToChain[BB]; 913 if (!UpdatedPreds.insert(&Chain)) 914 continue; 915 916 assert(Chain.LoopPredecessors == 0); 917 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 918 BCI != BCE; ++BCI) { 919 assert(BlockToChain[*BCI] == &Chain); 920 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 921 PE = (*BCI)->pred_end(); 922 PI != PE; ++PI) { 923 if (BlockToChain[*PI] == &Chain) 924 continue; 925 ++Chain.LoopPredecessors; 926 } 927 } 928 929 if (Chain.LoopPredecessors == 0) 930 BlockWorkList.push_back(*Chain.begin()); 931 } 932 933 BlockChain &FunctionChain = *BlockToChain[&F.front()]; 934 buildChain(&F.front(), FunctionChain, BlockWorkList); 935 936 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 937 DEBUG({ 938 // Crash at the end so we get all of the debugging output first. 939 bool BadFunc = false; 940 FunctionBlockSetType FunctionBlockSet; 941 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 942 FunctionBlockSet.insert(FI); 943 944 for (BlockChain::iterator BCI = FunctionChain.begin(), 945 BCE = FunctionChain.end(); 946 BCI != BCE; ++BCI) 947 if (!FunctionBlockSet.erase(*BCI)) { 948 BadFunc = true; 949 dbgs() << "Function chain contains a block not in the function!\n" 950 << " Bad block: " << getBlockName(*BCI) << "\n"; 951 } 952 953 if (!FunctionBlockSet.empty()) { 954 BadFunc = true; 955 for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), 956 FBE = FunctionBlockSet.end(); 957 FBI != FBE; ++FBI) 958 dbgs() << "Function contains blocks never placed into a chain!\n" 959 << " Bad block: " << getBlockName(*FBI) << "\n"; 960 } 961 assert(!BadFunc && "Detected problems with the block placement."); 962 }); 963 964 // Splice the blocks into place. 965 MachineFunction::iterator InsertPos = F.begin(); 966 for (BlockChain::iterator BI = FunctionChain.begin(), 967 BE = FunctionChain.end(); 968 BI != BE; ++BI) { 969 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 970 : " ... ") 971 << getBlockName(*BI) << "\n"); 972 if (InsertPos != MachineFunction::iterator(*BI)) 973 F.splice(InsertPos, *BI); 974 else 975 ++InsertPos; 976 977 // Update the terminator of the previous block. 978 if (BI == FunctionChain.begin()) 979 continue; 980 MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 981 982 // FIXME: It would be awesome of updateTerminator would just return rather 983 // than assert when the branch cannot be analyzed in order to remove this 984 // boiler plate. 985 Cond.clear(); 986 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 987 if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { 988 // If PrevBB has a two-way branch, try to re-order the branches 989 // such that we branch to the successor with higher weight first. 990 if (TBB && !Cond.empty() && FBB && 991 MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && 992 !TII->ReverseBranchCondition(Cond)) { 993 DEBUG(dbgs() << "Reverse order of the two branches: " 994 << getBlockName(PrevBB) << "\n"); 995 DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) 996 << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); 997 DebugLoc dl; // FIXME: this is nowhere 998 TII->RemoveBranch(*PrevBB); 999 TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); 1000 } 1001 PrevBB->updateTerminator(); 1002 } 1003 } 1004 1005 // Fixup the last block. 1006 Cond.clear(); 1007 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 1008 if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 1009 F.back().updateTerminator(); 1010 1011 // Walk through the backedges of the function now that we have fully laid out 1012 // the basic blocks and align the destination of each backedge. We don't rely 1013 // exclusively on the loop info here so that we can align backedges in 1014 // unnatural CFGs and backedges that were introduced purely because of the 1015 // loop rotations done during this layout pass. 1016 if (F.getFunction()->getAttributes(). 1017 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize)) 1018 return; 1019 unsigned Align = TLI->getPrefLoopAlignment(); 1020 if (!Align) 1021 return; // Don't care about loop alignment. 1022 if (FunctionChain.begin() == FunctionChain.end()) 1023 return; // Empty chain. 1024 1025 const BranchProbability ColdProb(1, 5); // 20% 1026 BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); 1027 BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; 1028 for (BlockChain::iterator BI = llvm::next(FunctionChain.begin()), 1029 BE = FunctionChain.end(); 1030 BI != BE; ++BI) { 1031 // Don't align non-looping basic blocks. These are unlikely to execute 1032 // enough times to matter in practice. Note that we'll still handle 1033 // unnatural CFGs inside of a natural outer loop (the common case) and 1034 // rotated loops. 1035 MachineLoop *L = MLI->getLoopFor(*BI); 1036 if (!L) 1037 continue; 1038 1039 // If the block is cold relative to the function entry don't waste space 1040 // aligning it. 1041 BlockFrequency Freq = MBFI->getBlockFreq(*BI); 1042 if (Freq < WeightedEntryFreq) 1043 continue; 1044 1045 // If the block is cold relative to its loop header, don't align it 1046 // regardless of what edges into the block exist. 1047 MachineBasicBlock *LoopHeader = L->getHeader(); 1048 BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); 1049 if (Freq < (LoopHeaderFreq * ColdProb)) 1050 continue; 1051 1052 // Check for the existence of a non-layout predecessor which would benefit 1053 // from aligning this block. 1054 MachineBasicBlock *LayoutPred = *llvm::prior(BI); 1055 1056 // Force alignment if all the predecessors are jumps. We already checked 1057 // that the block isn't cold above. 1058 if (!LayoutPred->isSuccessor(*BI)) { 1059 (*BI)->setAlignment(Align); 1060 continue; 1061 } 1062 1063 // Align this block if the layout predecessor's edge into this block is 1064 // cold relative to the block. When this is true, othe predecessors make up 1065 // all of the hot entries into the block and thus alignment is likely to be 1066 // important. 1067 BranchProbability LayoutProb = MBPI->getEdgeProbability(LayoutPred, *BI); 1068 BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; 1069 if (LayoutEdgeFreq <= (Freq * ColdProb)) 1070 (*BI)->setAlignment(Align); 1071 } 1072 } 1073 1074 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 1075 // Check for single-block functions and skip them. 1076 if (llvm::next(F.begin()) == F.end()) 1077 return false; 1078 1079 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1080 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 1081 MLI = &getAnalysis<MachineLoopInfo>(); 1082 TII = F.getTarget().getInstrInfo(); 1083 TLI = F.getTarget().getTargetLowering(); 1084 assert(BlockToChain.empty()); 1085 1086 buildCFGChains(F); 1087 1088 BlockToChain.clear(); 1089 ChainAllocator.DestroyAll(); 1090 1091 // We always return true as we have no way to track whether the final order 1092 // differs from the original order. 1093 return true; 1094 } 1095 1096 namespace { 1097 /// \brief A pass to compute block placement statistics. 1098 /// 1099 /// A separate pass to compute interesting statistics for evaluating block 1100 /// placement. This is separate from the actual placement pass so that they can 1101 /// be computed in the absence of any placement transformations or when using 1102 /// alternative placement strategies. 1103 class MachineBlockPlacementStats : public MachineFunctionPass { 1104 /// \brief A handle to the branch probability pass. 1105 const MachineBranchProbabilityInfo *MBPI; 1106 1107 /// \brief A handle to the function-wide block frequency pass. 1108 const MachineBlockFrequencyInfo *MBFI; 1109 1110 public: 1111 static char ID; // Pass identification, replacement for typeid 1112 MachineBlockPlacementStats() : MachineFunctionPass(ID) { 1113 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 1114 } 1115 1116 bool runOnMachineFunction(MachineFunction &F); 1117 1118 void getAnalysisUsage(AnalysisUsage &AU) const { 1119 AU.addRequired<MachineBranchProbabilityInfo>(); 1120 AU.addRequired<MachineBlockFrequencyInfo>(); 1121 AU.setPreservesAll(); 1122 MachineFunctionPass::getAnalysisUsage(AU); 1123 } 1124 }; 1125 } 1126 1127 char MachineBlockPlacementStats::ID = 0; 1128 char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 1129 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 1130 "Basic Block Placement Stats", false, false) 1131 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 1132 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 1133 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 1134 "Basic Block Placement Stats", false, false) 1135 1136 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 1137 // Check for single-block functions and skip them. 1138 if (llvm::next(F.begin()) == F.end()) 1139 return false; 1140 1141 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1142 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 1143 1144 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 1145 BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 1146 Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 1147 : NumUncondBranches; 1148 Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 1149 : UncondBranchTakenFreq; 1150 for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 1151 SE = I->succ_end(); 1152 SI != SE; ++SI) { 1153 // Skip if this successor is a fallthrough. 1154 if (I->isLayoutSuccessor(*SI)) 1155 continue; 1156 1157 BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 1158 ++NumBranches; 1159 BranchTakenFreq += EdgeFreq.getFrequency(); 1160 } 1161 } 1162 1163 return false; 1164 } 1165 1166