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