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