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