MachineBlockPlacement.cpp revision 6313d941d29d77f62662c4bd13f12314e6b4b86e
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#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 *findBestLoopTop(MachineFunction &F, 215 MachineLoop &L, 216 const BlockFilterSet &LoopBlockSet); 217 void buildLoopChains(MachineFunction &F, MachineLoop &L); 218 void buildCFGChains(MachineFunction &F); 219 void AlignLoops(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 effeciently 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 assert(!BlockFilter || BlockFilter->count(*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::findBestLoopTop(MachineFunction &F, 549 MachineLoop &L, 550 const BlockFilterSet &LoopBlockSet) { 551 BlockFrequency BestExitEdgeFreq; 552 MachineBasicBlock *ExitingBB = 0; 553 MachineBasicBlock *LoopingBB = 0; 554 // If there are exits to outer loops, loop rotation can severely limit 555 // fallthrough opportunites unless it selects such an exit. Keep a set of 556 // blocks where rotating to exit with that block will reach an outer loop. 557 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; 558 559 DEBUG(dbgs() << "Finding best loop exit for: " 560 << getBlockName(L.getHeader()) << "\n"); 561 for (MachineLoop::block_iterator I = L.block_begin(), 562 E = L.block_end(); 563 I != E; ++I) { 564 BlockChain &Chain = *BlockToChain[*I]; 565 // Ensure that this block is at the end of a chain; otherwise it could be 566 // mid-way through an inner loop or a successor of an analyzable branch. 567 if (*I != *llvm::prior(Chain.end())) 568 continue; 569 570 // Now walk the successors. We need to establish whether this has a viable 571 // exiting successor and whether it has a viable non-exiting successor. 572 // We store the old exiting state and restore it if a viable looping 573 // successor isn't found. 574 MachineBasicBlock *OldExitingBB = ExitingBB; 575 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; 576 // We also compute and store the best looping successor for use in layout. 577 MachineBasicBlock *BestLoopSucc = 0; 578 // FIXME: Due to the performance of the probability and weight routines in 579 // the MBPI analysis, we use the internal weights. This is only valid 580 // because it is purely a ranking function, we don't care about anything 581 // but the relative values. 582 uint32_t BestLoopSuccWeight = 0; 583 // FIXME: We also manually compute the probabilities to avoid quadratic 584 // behavior. 585 uint32_t WeightScale = 0; 586 uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); 587 for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), 588 SE = (*I)->succ_end(); 589 SI != SE; ++SI) { 590 if ((*SI)->isLandingPad()) 591 continue; 592 if (*SI == *I) 593 continue; 594 BlockChain &SuccChain = *BlockToChain[*SI]; 595 // Don't split chains, either this chain or the successor's chain. 596 if (&Chain == &SuccChain || *SI != *SuccChain.begin()) { 597 DEBUG(dbgs() << " " << (LoopBlockSet.count(*SI) ? "looping: " 598 : "exiting: ") 599 << getBlockName(*I) << " -> " 600 << getBlockName(*SI) << " (chain conflict)\n"); 601 continue; 602 } 603 604 uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); 605 if (LoopBlockSet.count(*SI)) { 606 DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " 607 << getBlockName(*SI) << " (" << SuccWeight << ")\n"); 608 if (BestLoopSucc && BestLoopSuccWeight >= SuccWeight) 609 continue; 610 611 BestLoopSucc = *SI; 612 BestLoopSuccWeight = SuccWeight; 613 continue; 614 } 615 616 BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 617 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; 618 DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 619 << getBlockName(*SI) << " (" << ExitEdgeFreq << ")\n"); 620 // Note that we slightly bias this toward an existing layout successor to 621 // retain incoming order in the absence of better information. 622 // FIXME: Should we bias this more strongly? It's pretty weak. 623 if (!ExitingBB || ExitEdgeFreq > BestExitEdgeFreq || 624 ((*I)->isLayoutSuccessor(*SI) && 625 !(ExitEdgeFreq < BestExitEdgeFreq))) { 626 BestExitEdgeFreq = ExitEdgeFreq; 627 ExitingBB = *I; 628 } 629 630 if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) 631 if (ExitLoop->contains(&L)) 632 BlocksExitingToOuterLoop.insert(*I); 633 } 634 635 // Restore the old exiting state, no viable looping successor was found. 636 if (!BestLoopSucc) { 637 ExitingBB = OldExitingBB; 638 BestExitEdgeFreq = OldBestExitEdgeFreq; 639 continue; 640 } 641 642 // If this was best exiting block thus far, also record the looping block. 643 if (ExitingBB == *I) 644 LoopingBB = BestLoopSucc; 645 } 646 // Without a candidate exitting block or with only a single block in the 647 // loop, just use the loop header to layout the loop. 648 if (!ExitingBB || L.getNumBlocks() == 1) 649 return L.getHeader(); 650 651 // Also, if we have exit blocks which lead to outer loops but didn't select 652 // one of them as the exiting block we are rotating toward, disable loop 653 // rotation altogether. 654 if (!BlocksExitingToOuterLoop.empty() && 655 !BlocksExitingToOuterLoop.count(ExitingBB)) 656 return L.getHeader(); 657 658 assert(LoopingBB && "All successors of a loop block are exit blocks!"); 659 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 660 DEBUG(dbgs() << " Best top block: " << getBlockName(LoopingBB) << "\n"); 661 return LoopingBB; 662} 663 664/// \brief Forms basic block chains from the natural loop structures. 665/// 666/// These chains are designed to preserve the existing *structure* of the code 667/// as much as possible. We can then stitch the chains together in a way which 668/// both preserves the topological structure and minimizes taken conditional 669/// branches. 670void MachineBlockPlacement::buildLoopChains(MachineFunction &F, 671 MachineLoop &L) { 672 // First recurse through any nested loops, building chains for those inner 673 // loops. 674 for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 675 buildLoopChains(F, **LI); 676 677 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 678 BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 679 680 MachineBasicBlock *LayoutTop = findBestLoopTop(F, L, LoopBlockSet); 681 BlockChain &LoopChain = *BlockToChain[LayoutTop]; 682 683 // FIXME: This is a really lame way of walking the chains in the loop: we 684 // walk the blocks, and use a set to prevent visiting a particular chain 685 // twice. 686 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 687 assert(LoopChain.LoopPredecessors == 0); 688 UpdatedPreds.insert(&LoopChain); 689 for (MachineLoop::block_iterator BI = L.block_begin(), 690 BE = L.block_end(); 691 BI != BE; ++BI) { 692 BlockChain &Chain = *BlockToChain[*BI]; 693 if (!UpdatedPreds.insert(&Chain)) 694 continue; 695 696 assert(Chain.LoopPredecessors == 0); 697 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 698 BCI != BCE; ++BCI) { 699 assert(BlockToChain[*BCI] == &Chain); 700 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 701 PE = (*BCI)->pred_end(); 702 PI != PE; ++PI) { 703 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 704 continue; 705 ++Chain.LoopPredecessors; 706 } 707 } 708 709 if (Chain.LoopPredecessors == 0) 710 BlockWorkList.push_back(*Chain.begin()); 711 } 712 713 buildChain(LayoutTop, LoopChain, BlockWorkList, &LoopBlockSet); 714 715 DEBUG({ 716 // Crash at the end so we get all of the debugging output first. 717 bool BadLoop = false; 718 if (LoopChain.LoopPredecessors) { 719 BadLoop = true; 720 dbgs() << "Loop chain contains a block without its preds placed!\n" 721 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 722 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 723 } 724 for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 725 BCI != BCE; ++BCI) 726 if (!LoopBlockSet.erase(*BCI)) { 727 // We don't mark the loop as bad here because there are real situations 728 // where this can occur. For example, with an unanalyzable fallthrough 729 // from a loop block to a non-loop block or vice versa. 730 dbgs() << "Loop chain contains a block not contained by the loop!\n" 731 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 732 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 733 << " Bad block: " << getBlockName(*BCI) << "\n"; 734 } 735 736 if (!LoopBlockSet.empty()) { 737 BadLoop = true; 738 for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), 739 LBE = LoopBlockSet.end(); 740 LBI != LBE; ++LBI) 741 dbgs() << "Loop contains blocks never placed into a chain!\n" 742 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 743 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 744 << " Bad block: " << getBlockName(*LBI) << "\n"; 745 } 746 assert(!BadLoop && "Detected problems with the placement of this loop."); 747 }); 748} 749 750void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 751 // Ensure that every BB in the function has an associated chain to simplify 752 // the assumptions of the remaining algorithm. 753 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 754 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 755 MachineBasicBlock *BB = FI; 756 BlockChain *Chain 757 = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 758 // Also, merge any blocks which we cannot reason about and must preserve 759 // the exact fallthrough behavior for. 760 for (;;) { 761 Cond.clear(); 762 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 763 if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 764 break; 765 766 MachineFunction::iterator NextFI(llvm::next(FI)); 767 MachineBasicBlock *NextBB = NextFI; 768 // Ensure that the layout successor is a viable block, as we know that 769 // fallthrough is a possibility. 770 assert(NextFI != FE && "Can't fallthrough past the last block."); 771 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 772 << getBlockName(BB) << " -> " << getBlockName(NextBB) 773 << "\n"); 774 Chain->merge(NextBB, 0); 775 FI = NextFI; 776 BB = NextBB; 777 } 778 } 779 780 // Build any loop-based chains. 781 for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 782 ++LI) 783 buildLoopChains(F, **LI); 784 785 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 786 787 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 788 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 789 MachineBasicBlock *BB = &*FI; 790 BlockChain &Chain = *BlockToChain[BB]; 791 if (!UpdatedPreds.insert(&Chain)) 792 continue; 793 794 assert(Chain.LoopPredecessors == 0); 795 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 796 BCI != BCE; ++BCI) { 797 assert(BlockToChain[*BCI] == &Chain); 798 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 799 PE = (*BCI)->pred_end(); 800 PI != PE; ++PI) { 801 if (BlockToChain[*PI] == &Chain) 802 continue; 803 ++Chain.LoopPredecessors; 804 } 805 } 806 807 if (Chain.LoopPredecessors == 0) 808 BlockWorkList.push_back(*Chain.begin()); 809 } 810 811 BlockChain &FunctionChain = *BlockToChain[&F.front()]; 812 buildChain(&F.front(), FunctionChain, BlockWorkList); 813 814 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 815 DEBUG({ 816 // Crash at the end so we get all of the debugging output first. 817 bool BadFunc = false; 818 FunctionBlockSetType FunctionBlockSet; 819 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 820 FunctionBlockSet.insert(FI); 821 822 for (BlockChain::iterator BCI = FunctionChain.begin(), 823 BCE = FunctionChain.end(); 824 BCI != BCE; ++BCI) 825 if (!FunctionBlockSet.erase(*BCI)) { 826 BadFunc = true; 827 dbgs() << "Function chain contains a block not in the function!\n" 828 << " Bad block: " << getBlockName(*BCI) << "\n"; 829 } 830 831 if (!FunctionBlockSet.empty()) { 832 BadFunc = true; 833 for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), 834 FBE = FunctionBlockSet.end(); 835 FBI != FBE; ++FBI) 836 dbgs() << "Function contains blocks never placed into a chain!\n" 837 << " Bad block: " << getBlockName(*FBI) << "\n"; 838 } 839 assert(!BadFunc && "Detected problems with the block placement."); 840 }); 841 842 // Splice the blocks into place. 843 MachineFunction::iterator InsertPos = F.begin(); 844 for (BlockChain::iterator BI = FunctionChain.begin(), 845 BE = FunctionChain.end(); 846 BI != BE; ++BI) { 847 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 848 : " ... ") 849 << getBlockName(*BI) << "\n"); 850 if (InsertPos != MachineFunction::iterator(*BI)) 851 F.splice(InsertPos, *BI); 852 else 853 ++InsertPos; 854 855 // Update the terminator of the previous block. 856 if (BI == FunctionChain.begin()) 857 continue; 858 MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 859 860 // FIXME: It would be awesome of updateTerminator would just return rather 861 // than assert when the branch cannot be analyzed in order to remove this 862 // boiler plate. 863 Cond.clear(); 864 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 865 if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) 866 PrevBB->updateTerminator(); 867 } 868 869 // Fixup the last block. 870 Cond.clear(); 871 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 872 if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 873 F.back().updateTerminator(); 874} 875 876/// \brief Recursive helper to align a loop and any nested loops. 877static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) { 878 // Recurse through nested loops. 879 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 880 AlignLoop(F, *I, Align); 881 882 L->getTopBlock()->setAlignment(Align); 883} 884 885/// \brief Align loop headers to target preferred alignments. 886void MachineBlockPlacement::AlignLoops(MachineFunction &F) { 887 if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 888 return; 889 890 unsigned Align = TLI->getPrefLoopAlignment(); 891 if (!Align) 892 return; // Don't care about loop alignment. 893 894 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) 895 AlignLoop(F, *I, Align); 896} 897 898bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 899 // Check for single-block functions and skip them. 900 if (llvm::next(F.begin()) == F.end()) 901 return false; 902 903 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 904 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 905 MLI = &getAnalysis<MachineLoopInfo>(); 906 TII = F.getTarget().getInstrInfo(); 907 TLI = F.getTarget().getTargetLowering(); 908 assert(BlockToChain.empty()); 909 910 buildCFGChains(F); 911 AlignLoops(F); 912 913 BlockToChain.clear(); 914 ChainAllocator.DestroyAll(); 915 916 // We always return true as we have no way to track whether the final order 917 // differs from the original order. 918 return true; 919} 920 921namespace { 922/// \brief A pass to compute block placement statistics. 923/// 924/// A separate pass to compute interesting statistics for evaluating block 925/// placement. This is separate from the actual placement pass so that they can 926/// be computed in the absense of any placement transformations or when using 927/// alternative placement strategies. 928class MachineBlockPlacementStats : public MachineFunctionPass { 929 /// \brief A handle to the branch probability pass. 930 const MachineBranchProbabilityInfo *MBPI; 931 932 /// \brief A handle to the function-wide block frequency pass. 933 const MachineBlockFrequencyInfo *MBFI; 934 935public: 936 static char ID; // Pass identification, replacement for typeid 937 MachineBlockPlacementStats() : MachineFunctionPass(ID) { 938 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 939 } 940 941 bool runOnMachineFunction(MachineFunction &F); 942 943 void getAnalysisUsage(AnalysisUsage &AU) const { 944 AU.addRequired<MachineBranchProbabilityInfo>(); 945 AU.addRequired<MachineBlockFrequencyInfo>(); 946 AU.setPreservesAll(); 947 MachineFunctionPass::getAnalysisUsage(AU); 948 } 949}; 950} 951 952char MachineBlockPlacementStats::ID = 0; 953char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 954INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 955 "Basic Block Placement Stats", false, false) 956INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 957INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 958INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 959 "Basic Block Placement Stats", false, false) 960 961bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 962 // Check for single-block functions and skip them. 963 if (llvm::next(F.begin()) == F.end()) 964 return false; 965 966 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 967 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 968 969 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 970 BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 971 Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 972 : NumUncondBranches; 973 Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 974 : UncondBranchTakenFreq; 975 for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 976 SE = I->succ_end(); 977 SI != SE; ++SI) { 978 // Skip if this successor is a fallthrough. 979 if (I->isLayoutSuccessor(*SI)) 980 continue; 981 982 BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 983 ++NumBranches; 984 BranchTakenFreq += EdgeFreq.getFrequency(); 985 } 986 } 987 988 return false; 989} 990 991