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/MachineBasicBlock.h" 30#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 31#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 32#include "llvm/CodeGen/MachineFunction.h" 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/CodeGen/MachineLoopInfo.h" 35#include "llvm/CodeGen/MachineModuleInfo.h" 36#include "llvm/CodeGen/Passes.h" 37#include "llvm/Support/Allocator.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/ADT/DenseMap.h" 40#include "llvm/ADT/SmallPtrSet.h" 41#include "llvm/ADT/SmallVector.h" 42#include "llvm/ADT/Statistic.h" 43#include "llvm/Target/TargetInstrInfo.h" 44#include "llvm/Target/TargetLowering.h" 45#include <algorithm> 46using namespace llvm; 47 48STATISTIC(NumCondBranches, "Number of conditional branches"); 49STATISTIC(NumUncondBranches, "Number of uncondittional branches"); 50STATISTIC(CondBranchTakenFreq, 51 "Potential frequency of taking conditional branches"); 52STATISTIC(UncondBranchTakenFreq, 53 "Potential frequency of taking unconditional branches"); 54 55namespace { 56class BlockChain; 57/// \brief Type for our function-wide basic block -> block chain mapping. 58typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 59} 60 61namespace { 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. 73class 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 88public: 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 156namespace { 157class 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 TargetLowering *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 221public: 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 238char MachineBlockPlacement::ID = 0; 239char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; 240INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 241 "Branch Probability Basic Block Placement", false, false) 242INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 243INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 244INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 245INITIALIZE_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. 252static 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. 264static 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. 279void 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. 319MachineBasicBlock *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 398namespace { 399/// \brief Predicate struct to detect blocks already placed. 400class IsBlockPlaced { 401 const BlockChain &PlacedChain; 402 const BlockToChainMapType &BlockToChain; 403 404public: 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. 425MachineBasicBlock *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. 467MachineBasicBlock *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 486void 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 MachineBasicBlock *BestSucc = 0; 504 505 // Look for the best viable successor if there is one to place immediately 506 // after this block. 507 BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); 508 509 // If an immediate successor isn't available, look for the best viable 510 // block among those we've identified as not violating the loop's CFG at 511 // this point. This won't be a fallthrough, but it will increase locality. 512 if (!BestSucc) 513 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); 514 515 if (!BestSucc) { 516 BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, 517 BlockFilter); 518 if (!BestSucc) 519 break; 520 521 DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " 522 "layout successor until the CFG reduces\n"); 523 } 524 525 // Place this block, updating the datastructures to reflect its placement. 526 BlockChain &SuccChain = *BlockToChain[BestSucc]; 527 // Zero out LoopPredecessors for the successor we're about to merge in case 528 // we selected a successor that didn't fit naturally into the CFG. 529 SuccChain.LoopPredecessors = 0; 530 DEBUG(dbgs() << "Merging from " << getBlockNum(BB) 531 << " to " << getBlockNum(BestSucc) << "\n"); 532 markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); 533 Chain.merge(BestSucc, &SuccChain); 534 BB = *llvm::prior(Chain.end()); 535 } 536 537 DEBUG(dbgs() << "Finished forming chain for header block " 538 << getBlockNum(*Chain.begin()) << "\n"); 539} 540 541/// \brief Find the best loop top block for layout. 542/// 543/// Look for a block which is strictly better than the loop header for laying 544/// out at the top of the loop. This looks for one and only one pattern: 545/// a latch block with no conditional exit. This block will cause a conditional 546/// jump around it or will be the bottom of the loop if we lay it out in place, 547/// but if it it doesn't end up at the bottom of the loop for any reason, 548/// rotation alone won't fix it. Because such a block will always result in an 549/// unconditional jump (for the backedge) rotating it in front of the loop 550/// header is always profitable. 551MachineBasicBlock * 552MachineBlockPlacement::findBestLoopTop(MachineLoop &L, 553 const BlockFilterSet &LoopBlockSet) { 554 // Check that the header hasn't been fused with a preheader block due to 555 // crazy branches. If it has, we need to start with the header at the top to 556 // prevent pulling the preheader into the loop body. 557 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 558 if (!LoopBlockSet.count(*HeaderChain.begin())) 559 return L.getHeader(); 560 561 DEBUG(dbgs() << "Finding best loop top for: " 562 << getBlockName(L.getHeader()) << "\n"); 563 564 BlockFrequency BestPredFreq; 565 MachineBasicBlock *BestPred = 0; 566 for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(), 567 PE = L.getHeader()->pred_end(); 568 PI != PE; ++PI) { 569 MachineBasicBlock *Pred = *PI; 570 if (!LoopBlockSet.count(Pred)) 571 continue; 572 DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", " 573 << Pred->succ_size() << " successors, " 574 << MBFI->getBlockFreq(Pred) << " freq\n"); 575 if (Pred->succ_size() > 1) 576 continue; 577 578 BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); 579 if (!BestPred || PredFreq > BestPredFreq || 580 (!(PredFreq < BestPredFreq) && 581 Pred->isLayoutSuccessor(L.getHeader()))) { 582 BestPred = Pred; 583 BestPredFreq = PredFreq; 584 } 585 } 586 587 // If no direct predecessor is fine, just use the loop header. 588 if (!BestPred) 589 return L.getHeader(); 590 591 // Walk backwards through any straight line of predecessors. 592 while (BestPred->pred_size() == 1 && 593 (*BestPred->pred_begin())->succ_size() == 1 && 594 *BestPred->pred_begin() != L.getHeader()) 595 BestPred = *BestPred->pred_begin(); 596 597 DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); 598 return BestPred; 599} 600 601 602/// \brief Find the best loop exiting block for layout. 603/// 604/// This routine implements the logic to analyze the loop looking for the best 605/// block to layout at the top of the loop. Typically this is done to maximize 606/// fallthrough opportunities. 607MachineBasicBlock * 608MachineBlockPlacement::findBestLoopExit(MachineFunction &F, 609 MachineLoop &L, 610 const BlockFilterSet &LoopBlockSet) { 611 // We don't want to layout the loop linearly in all cases. If the loop header 612 // is just a normal basic block in the loop, we want to look for what block 613 // within the loop is the best one to layout at the top. However, if the loop 614 // header has be pre-merged into a chain due to predecessors not having 615 // analyzable branches, *and* the predecessor it is merged with is *not* part 616 // of the loop, rotating the header into the middle of the loop will create 617 // a non-contiguous range of blocks which is Very Bad. So start with the 618 // header and only rotate if safe. 619 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 620 if (!LoopBlockSet.count(*HeaderChain.begin())) 621 return 0; 622 623 BlockFrequency BestExitEdgeFreq; 624 unsigned BestExitLoopDepth = 0; 625 MachineBasicBlock *ExitingBB = 0; 626 // If there are exits to outer loops, loop rotation can severely limit 627 // fallthrough opportunites unless it selects such an exit. Keep a set of 628 // blocks where rotating to exit with that block will reach an outer loop. 629 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; 630 631 DEBUG(dbgs() << "Finding best loop exit for: " 632 << getBlockName(L.getHeader()) << "\n"); 633 for (MachineLoop::block_iterator I = L.block_begin(), 634 E = L.block_end(); 635 I != E; ++I) { 636 BlockChain &Chain = *BlockToChain[*I]; 637 // Ensure that this block is at the end of a chain; otherwise it could be 638 // mid-way through an inner loop or a successor of an analyzable branch. 639 if (*I != *llvm::prior(Chain.end())) 640 continue; 641 642 // Now walk the successors. We need to establish whether this has a viable 643 // exiting successor and whether it has a viable non-exiting successor. 644 // We store the old exiting state and restore it if a viable looping 645 // successor isn't found. 646 MachineBasicBlock *OldExitingBB = ExitingBB; 647 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; 648 bool HasLoopingSucc = false; 649 // FIXME: Due to the performance of the probability and weight routines in 650 // the MBPI analysis, we use the internal weights and manually compute the 651 // probabilities to avoid quadratic behavior. 652 uint32_t WeightScale = 0; 653 uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); 654 for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), 655 SE = (*I)->succ_end(); 656 SI != SE; ++SI) { 657 if ((*SI)->isLandingPad()) 658 continue; 659 if (*SI == *I) 660 continue; 661 BlockChain &SuccChain = *BlockToChain[*SI]; 662 // Don't split chains, either this chain or the successor's chain. 663 if (&Chain == &SuccChain) { 664 DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 665 << getBlockName(*SI) << " (chain conflict)\n"); 666 continue; 667 } 668 669 uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); 670 if (LoopBlockSet.count(*SI)) { 671 DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " 672 << getBlockName(*SI) << " (" << SuccWeight << ")\n"); 673 HasLoopingSucc = true; 674 continue; 675 } 676 677 unsigned SuccLoopDepth = 0; 678 if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) { 679 SuccLoopDepth = ExitLoop->getLoopDepth(); 680 if (ExitLoop->contains(&L)) 681 BlocksExitingToOuterLoop.insert(*I); 682 } 683 684 BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 685 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; 686 DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 687 << getBlockName(*SI) << " [L:" << SuccLoopDepth 688 << "] (" << ExitEdgeFreq << ")\n"); 689 // Note that we slightly bias this toward an existing layout successor to 690 // retain incoming order in the absence of better information. 691 // FIXME: Should we bias this more strongly? It's pretty weak. 692 if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || 693 ExitEdgeFreq > BestExitEdgeFreq || 694 ((*I)->isLayoutSuccessor(*SI) && 695 !(ExitEdgeFreq < BestExitEdgeFreq))) { 696 BestExitEdgeFreq = ExitEdgeFreq; 697 ExitingBB = *I; 698 } 699 } 700 701 // Restore the old exiting state, no viable looping successor was found. 702 if (!HasLoopingSucc) { 703 ExitingBB = OldExitingBB; 704 BestExitEdgeFreq = OldBestExitEdgeFreq; 705 continue; 706 } 707 } 708 // Without a candidate exiting block or with only a single block in the 709 // loop, just use the loop header to layout the loop. 710 if (!ExitingBB || L.getNumBlocks() == 1) 711 return 0; 712 713 // Also, if we have exit blocks which lead to outer loops but didn't select 714 // one of them as the exiting block we are rotating toward, disable loop 715 // rotation altogether. 716 if (!BlocksExitingToOuterLoop.empty() && 717 !BlocksExitingToOuterLoop.count(ExitingBB)) 718 return 0; 719 720 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 721 return ExitingBB; 722} 723 724/// \brief Attempt to rotate an exiting block to the bottom of the loop. 725/// 726/// Once we have built a chain, try to rotate it to line up the hot exit block 727/// with fallthrough out of the loop if doing so doesn't introduce unnecessary 728/// branches. For example, if the loop has fallthrough into its header and out 729/// of its bottom already, don't rotate it. 730void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, 731 MachineBasicBlock *ExitingBB, 732 const BlockFilterSet &LoopBlockSet) { 733 if (!ExitingBB) 734 return; 735 736 MachineBasicBlock *Top = *LoopChain.begin(); 737 bool ViableTopFallthrough = false; 738 for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), 739 PE = Top->pred_end(); 740 PI != PE; ++PI) { 741 BlockChain *PredChain = BlockToChain[*PI]; 742 if (!LoopBlockSet.count(*PI) && 743 (!PredChain || *PI == *llvm::prior(PredChain->end()))) { 744 ViableTopFallthrough = true; 745 break; 746 } 747 } 748 749 // If the header has viable fallthrough, check whether the current loop 750 // bottom is a viable exiting block. If so, bail out as rotating will 751 // introduce an unnecessary branch. 752 if (ViableTopFallthrough) { 753 MachineBasicBlock *Bottom = *llvm::prior(LoopChain.end()); 754 for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), 755 SE = Bottom->succ_end(); 756 SI != SE; ++SI) { 757 BlockChain *SuccChain = BlockToChain[*SI]; 758 if (!LoopBlockSet.count(*SI) && 759 (!SuccChain || *SI == *SuccChain->begin())) 760 return; 761 } 762 } 763 764 BlockChain::iterator ExitIt = std::find(LoopChain.begin(), LoopChain.end(), 765 ExitingBB); 766 if (ExitIt == LoopChain.end()) 767 return; 768 769 std::rotate(LoopChain.begin(), llvm::next(ExitIt), LoopChain.end()); 770} 771 772/// \brief Forms basic block chains from the natural loop structures. 773/// 774/// These chains are designed to preserve the existing *structure* of the code 775/// as much as possible. We can then stitch the chains together in a way which 776/// both preserves the topological structure and minimizes taken conditional 777/// branches. 778void MachineBlockPlacement::buildLoopChains(MachineFunction &F, 779 MachineLoop &L) { 780 // First recurse through any nested loops, building chains for those inner 781 // loops. 782 for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 783 buildLoopChains(F, **LI); 784 785 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 786 BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 787 788 // First check to see if there is an obviously preferable top block for the 789 // loop. This will default to the header, but may end up as one of the 790 // predecessors to the header if there is one which will result in strictly 791 // fewer branches in the loop body. 792 MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); 793 794 // If we selected just the header for the loop top, look for a potentially 795 // profitable exit block in the event that rotating the loop can eliminate 796 // branches by placing an exit edge at the bottom. 797 MachineBasicBlock *ExitingBB = 0; 798 if (LoopTop == L.getHeader()) 799 ExitingBB = findBestLoopExit(F, L, LoopBlockSet); 800 801 BlockChain &LoopChain = *BlockToChain[LoopTop]; 802 803 // FIXME: This is a really lame way of walking the chains in the loop: we 804 // walk the blocks, and use a set to prevent visiting a particular chain 805 // twice. 806 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 807 assert(LoopChain.LoopPredecessors == 0); 808 UpdatedPreds.insert(&LoopChain); 809 for (MachineLoop::block_iterator BI = L.block_begin(), 810 BE = L.block_end(); 811 BI != BE; ++BI) { 812 BlockChain &Chain = *BlockToChain[*BI]; 813 if (!UpdatedPreds.insert(&Chain)) 814 continue; 815 816 assert(Chain.LoopPredecessors == 0); 817 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 818 BCI != BCE; ++BCI) { 819 assert(BlockToChain[*BCI] == &Chain); 820 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 821 PE = (*BCI)->pred_end(); 822 PI != PE; ++PI) { 823 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 824 continue; 825 ++Chain.LoopPredecessors; 826 } 827 } 828 829 if (Chain.LoopPredecessors == 0) 830 BlockWorkList.push_back(*Chain.begin()); 831 } 832 833 buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); 834 rotateLoop(LoopChain, ExitingBB, LoopBlockSet); 835 836 DEBUG({ 837 // Crash at the end so we get all of the debugging output first. 838 bool BadLoop = false; 839 if (LoopChain.LoopPredecessors) { 840 BadLoop = true; 841 dbgs() << "Loop chain contains a block without its preds placed!\n" 842 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 843 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 844 } 845 for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 846 BCI != BCE; ++BCI) { 847 dbgs() << " ... " << getBlockName(*BCI) << "\n"; 848 if (!LoopBlockSet.erase(*BCI)) { 849 // We don't mark the loop as bad here because there are real situations 850 // where this can occur. For example, with an unanalyzable fallthrough 851 // from a loop block to a non-loop block or vice versa. 852 dbgs() << "Loop chain contains a block not contained by the loop!\n" 853 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 854 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 855 << " Bad block: " << getBlockName(*BCI) << "\n"; 856 } 857 } 858 859 if (!LoopBlockSet.empty()) { 860 BadLoop = true; 861 for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), 862 LBE = LoopBlockSet.end(); 863 LBI != LBE; ++LBI) 864 dbgs() << "Loop contains blocks never placed into a chain!\n" 865 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 866 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 867 << " Bad block: " << getBlockName(*LBI) << "\n"; 868 } 869 assert(!BadLoop && "Detected problems with the placement of this loop."); 870 }); 871} 872 873void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 874 // Ensure that every BB in the function has an associated chain to simplify 875 // the assumptions of the remaining algorithm. 876 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 877 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 878 MachineBasicBlock *BB = FI; 879 BlockChain *Chain 880 = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 881 // Also, merge any blocks which we cannot reason about and must preserve 882 // the exact fallthrough behavior for. 883 for (;;) { 884 Cond.clear(); 885 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 886 if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 887 break; 888 889 MachineFunction::iterator NextFI(llvm::next(FI)); 890 MachineBasicBlock *NextBB = NextFI; 891 // Ensure that the layout successor is a viable block, as we know that 892 // fallthrough is a possibility. 893 assert(NextFI != FE && "Can't fallthrough past the last block."); 894 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 895 << getBlockName(BB) << " -> " << getBlockName(NextBB) 896 << "\n"); 897 Chain->merge(NextBB, 0); 898 FI = NextFI; 899 BB = NextBB; 900 } 901 } 902 903 // Build any loop-based chains. 904 for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 905 ++LI) 906 buildLoopChains(F, **LI); 907 908 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 909 910 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 911 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 912 MachineBasicBlock *BB = &*FI; 913 BlockChain &Chain = *BlockToChain[BB]; 914 if (!UpdatedPreds.insert(&Chain)) 915 continue; 916 917 assert(Chain.LoopPredecessors == 0); 918 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 919 BCI != BCE; ++BCI) { 920 assert(BlockToChain[*BCI] == &Chain); 921 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 922 PE = (*BCI)->pred_end(); 923 PI != PE; ++PI) { 924 if (BlockToChain[*PI] == &Chain) 925 continue; 926 ++Chain.LoopPredecessors; 927 } 928 } 929 930 if (Chain.LoopPredecessors == 0) 931 BlockWorkList.push_back(*Chain.begin()); 932 } 933 934 BlockChain &FunctionChain = *BlockToChain[&F.front()]; 935 buildChain(&F.front(), FunctionChain, BlockWorkList); 936 937 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 938 DEBUG({ 939 // Crash at the end so we get all of the debugging output first. 940 bool BadFunc = false; 941 FunctionBlockSetType FunctionBlockSet; 942 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 943 FunctionBlockSet.insert(FI); 944 945 for (BlockChain::iterator BCI = FunctionChain.begin(), 946 BCE = FunctionChain.end(); 947 BCI != BCE; ++BCI) 948 if (!FunctionBlockSet.erase(*BCI)) { 949 BadFunc = true; 950 dbgs() << "Function chain contains a block not in the function!\n" 951 << " Bad block: " << getBlockName(*BCI) << "\n"; 952 } 953 954 if (!FunctionBlockSet.empty()) { 955 BadFunc = true; 956 for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), 957 FBE = FunctionBlockSet.end(); 958 FBI != FBE; ++FBI) 959 dbgs() << "Function contains blocks never placed into a chain!\n" 960 << " Bad block: " << getBlockName(*FBI) << "\n"; 961 } 962 assert(!BadFunc && "Detected problems with the block placement."); 963 }); 964 965 // Splice the blocks into place. 966 MachineFunction::iterator InsertPos = F.begin(); 967 for (BlockChain::iterator BI = FunctionChain.begin(), 968 BE = FunctionChain.end(); 969 BI != BE; ++BI) { 970 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 971 : " ... ") 972 << getBlockName(*BI) << "\n"); 973 if (InsertPos != MachineFunction::iterator(*BI)) 974 F.splice(InsertPos, *BI); 975 else 976 ++InsertPos; 977 978 // Update the terminator of the previous block. 979 if (BI == FunctionChain.begin()) 980 continue; 981 MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 982 983 // FIXME: It would be awesome of updateTerminator would just return rather 984 // than assert when the branch cannot be analyzed in order to remove this 985 // boiler plate. 986 Cond.clear(); 987 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 988 if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { 989 // If PrevBB has a two-way branch, try to re-order the branches 990 // such that we branch to the successor with higher weight first. 991 if (TBB && !Cond.empty() && FBB && 992 MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && 993 !TII->ReverseBranchCondition(Cond)) { 994 DEBUG(dbgs() << "Reverse order of the two branches: " 995 << getBlockName(PrevBB) << "\n"); 996 DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) 997 << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); 998 DebugLoc dl; // FIXME: this is nowhere 999 TII->RemoveBranch(*PrevBB); 1000 TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); 1001 } 1002 PrevBB->updateTerminator(); 1003 } 1004 } 1005 1006 // Fixup the last block. 1007 Cond.clear(); 1008 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 1009 if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 1010 F.back().updateTerminator(); 1011 1012 // Walk through the backedges of the function now that we have fully laid out 1013 // the basic blocks and align the destination of each backedge. We don't rely 1014 // exclusively on the loop info here so that we can align backedges in 1015 // unnatural CFGs and backedges that were introduced purely because of the 1016 // loop rotations done during this layout pass. 1017 if (F.getFunction()->hasFnAttr(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 1074bool 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 1096namespace { 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. 1103class 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 1110public: 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 1127char MachineBlockPlacementStats::ID = 0; 1128char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 1129INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 1130 "Basic Block Placement Stats", false, false) 1131INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 1132INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 1133INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 1134 "Basic Block Placement Stats", false, false) 1135 1136bool 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