MachineBlockPlacement.cpp revision 9fd4e056e433b286f0e6576046ef2242365bfc38
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 *> &Blocks, 210 const BlockFilterSet *BlockFilter = 0); 211 MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, 212 BlockChain &Chain, 213 const BlockFilterSet *BlockFilter); 214 void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 215 SmallVectorImpl<MachineBasicBlock *> &Blocks, 216 const BlockFilterSet *BlockFilter = 0); 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 const char *getPassName() const { return "Block Placement"; } 237}; 238} 239 240char MachineBlockPlacement::ID = 0; 241INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 242 "Branch Probability Basic Block Placement", false, false) 243INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 244INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 245INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 246INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 247 "Branch Probability Basic Block Placement", false, false) 248 249FunctionPass *llvm::createMachineBlockPlacementPass() { 250 return new MachineBlockPlacement(); 251} 252 253#ifndef NDEBUG 254/// \brief Helper to print the name of a MBB. 255/// 256/// Only used by debug logging. 257static std::string getBlockName(MachineBasicBlock *BB) { 258 std::string Result; 259 raw_string_ostream OS(Result); 260 OS << "BB#" << BB->getNumber() 261 << " (derived from LLVM BB '" << BB->getName() << "')"; 262 OS.flush(); 263 return Result; 264} 265 266/// \brief Helper to print the number of a MBB. 267/// 268/// Only used by debug logging. 269static std::string getBlockNum(MachineBasicBlock *BB) { 270 std::string Result; 271 raw_string_ostream OS(Result); 272 OS << "BB#" << BB->getNumber(); 273 OS.flush(); 274 return Result; 275} 276#endif 277 278void MachineBlockPlacement::markChainSuccessors( 279 BlockChain &Chain, 280 MachineBasicBlock *LoopHeaderBB, 281 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 282 const BlockFilterSet *BlockFilter) { 283 // Walk all the blocks in this chain, marking their successors as having 284 // a predecessor placed. 285 for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); 286 CBI != CBE; ++CBI) { 287 // Add any successors for which this is the only un-placed in-loop 288 // predecessor to the worklist as a viable candidate for CFG-neutral 289 // placement. No subsequent placement of this block will violate the CFG 290 // shape, so we get to use heuristics to choose a favorable placement. 291 for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), 292 SE = (*CBI)->succ_end(); 293 SI != SE; ++SI) { 294 if (BlockFilter && !BlockFilter->count(*SI)) 295 continue; 296 BlockChain &SuccChain = *BlockToChain[*SI]; 297 // Disregard edges within a fixed chain, or edges to the loop header. 298 if (&Chain == &SuccChain || *SI == LoopHeaderBB) 299 continue; 300 301 // This is a cross-chain edge that is within the loop, so decrement the 302 // loop predecessor count of the destination chain. 303 if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) 304 BlockWorkList.push_back(*SI); 305 } 306 } 307} 308 309/// \brief Select the best successor for a block. 310/// 311/// This looks across all successors of a particular block and attempts to 312/// select the "best" one to be the layout successor. It only considers direct 313/// successors which also pass the block filter. It will attempt to avoid 314/// breaking CFG structure, but cave and break such structures in the case of 315/// very hot successor edges. 316/// 317/// \returns The best successor block found, or null if none are viable. 318MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 319 MachineBasicBlock *BB, BlockChain &Chain, 320 const BlockFilterSet *BlockFilter) { 321 const BranchProbability HotProb(4, 5); // 80% 322 323 MachineBasicBlock *BestSucc = 0; 324 BranchProbability BestProb = BranchProbability::getZero(); 325 DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 326 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 327 SE = BB->succ_end(); 328 SI != SE; ++SI) { 329 if (BlockFilter && !BlockFilter->count(*SI)) 330 continue; 331 BlockChain &SuccChain = *BlockToChain[*SI]; 332 if (&SuccChain == &Chain) { 333 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); 334 continue; 335 } 336 337 BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI); 338 339 // Only consider successors which are either "hot", or wouldn't violate 340 // any CFG constraints. 341 if (SuccChain.LoopPredecessors != 0 && SuccProb < HotProb) { 342 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); 343 continue; 344 } 345 346 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 347 << " (prob)" 348 << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") 349 << "\n"); 350 if (BestSucc && BestProb >= SuccProb) 351 continue; 352 BestSucc = *SI; 353 BestProb = SuccProb; 354 } 355 return BestSucc; 356} 357 358void MachineBlockPlacement::buildChain( 359 MachineBasicBlock *BB, 360 BlockChain &Chain, 361 SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 362 const BlockFilterSet *BlockFilter) { 363 assert(BB); 364 assert(BlockToChain[BB] == &Chain); 365 assert(*Chain.begin() == BB); 366 MachineBasicBlock *LoopHeaderBB = BB; 367 markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); 368 BB = *llvm::prior(Chain.end()); 369 for (;;) { 370 assert(BB); 371 assert(BlockToChain[BB] == &Chain); 372 assert(*llvm::prior(Chain.end()) == BB); 373 374 // Look for the best viable successor if there is one to place immediately 375 // after this block. 376 MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); 377 378 // If an immediate successor isn't available, look for the best viable 379 // block among those we've identified as not violating the loop's CFG at 380 // this point. This won't be a fallthrough, but it will increase locality. 381 if (!BestSucc) { 382 BlockFrequency BestFreq; 383 for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = BlockWorkList.begin(), 384 WBE = BlockWorkList.end(); 385 WBI != WBE; ++WBI) { 386 if (BlockFilter && !BlockFilter->count(*WBI)) 387 continue; 388 BlockChain &SuccChain = *BlockToChain[*WBI]; 389 if (&SuccChain == &Chain) { 390 DEBUG(dbgs() << " " << getBlockName(*WBI) 391 << " -> Already merged!\n"); 392 continue; 393 } 394 assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); 395 396 BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); 397 DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq 398 << " (freq)\n"); 399 if (BestSucc && BestFreq >= CandidateFreq) 400 continue; 401 BestSucc = *WBI; 402 BestFreq = CandidateFreq; 403 } 404 } 405 if (!BestSucc) { 406 DEBUG(dbgs() << "Finished forming chain for header block " 407 << getBlockNum(*Chain.begin()) << "\n"); 408 return; 409 } 410 411 // Place this block, updating the datastructures to reflect its placement. 412 BlockChain &SuccChain = *BlockToChain[BestSucc]; 413 DEBUG(dbgs() << "Merging from " << getBlockNum(BB) 414 << " to " << getBlockNum(BestSucc) << "\n"); 415 markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); 416 Chain.merge(BestSucc, &SuccChain); 417 BB = *llvm::prior(Chain.end()); 418 } 419} 420 421/// \brief Forms basic block chains from the natural loop structures. 422/// 423/// These chains are designed to preserve the existing *structure* of the code 424/// as much as possible. We can then stitch the chains together in a way which 425/// both preserves the topological structure and minimizes taken conditional 426/// branches. 427void MachineBlockPlacement::buildLoopChains(MachineFunction &F, 428 MachineLoop &L) { 429 // First recurse through any nested loops, building chains for those inner 430 // loops. 431 for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 432 buildLoopChains(F, **LI); 433 434 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 435 BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 436 437 // FIXME: This is a really lame way of walking the chains in the loop: we 438 // walk the blocks, and use a set to prevent visiting a particular chain 439 // twice. 440 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 441 for (MachineLoop::block_iterator BI = L.block_begin(), 442 BE = L.block_end(); 443 BI != BE; ++BI) { 444 BlockChain &Chain = *BlockToChain[*BI]; 445 if (!UpdatedPreds.insert(&Chain) || BI == L.block_begin()) 446 continue; 447 448 assert(Chain.LoopPredecessors == 0); 449 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 450 BCI != BCE; ++BCI) { 451 assert(BlockToChain[*BCI] == &Chain); 452 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 453 PE = (*BCI)->pred_end(); 454 PI != PE; ++PI) { 455 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 456 continue; 457 ++Chain.LoopPredecessors; 458 } 459 } 460 461 if (Chain.LoopPredecessors == 0) 462 BlockWorkList.push_back(*BI); 463 } 464 465 BlockChain &LoopChain = *BlockToChain[L.getHeader()]; 466 buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); 467 468 DEBUG({ 469 if (LoopChain.LoopPredecessors) 470 dbgs() << "Loop chain contains a block without its preds placed!\n" 471 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 472 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 473 for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 474 BCI != BCE; ++BCI) 475 if (!LoopBlockSet.erase(*BCI)) 476 dbgs() << "Loop chain contains a block not contained by the loop!\n" 477 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 478 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 479 << " Bad block: " << getBlockName(*BCI) << "\n"; 480 481 if (!LoopBlockSet.empty()) 482 for (SmallPtrSet<MachineBasicBlock *, 16>::iterator LBI = LoopBlockSet.begin(), LBE = LoopBlockSet.end(); 483 LBI != LBE; ++LBI) 484 dbgs() << "Loop contains blocks never placed into a chain!\n" 485 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 486 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 487 << " Bad block: " << getBlockName(*LBI) << "\n"; 488 }); 489} 490 491void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 492 // Ensure that every BB in the function has an associated chain to simplify 493 // the assumptions of the remaining algorithm. 494 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 495 BlockToChain[&*FI] = 496 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, &*FI); 497 498 // Build any loop-based chains. 499 for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 500 ++LI) 501 buildLoopChains(F, **LI); 502 503 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 504 505 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 506 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 507 MachineBasicBlock *BB = &*FI; 508 BlockChain &Chain = *BlockToChain[BB]; 509 if (!UpdatedPreds.insert(&Chain)) 510 continue; 511 512 assert(Chain.LoopPredecessors == 0); 513 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 514 BCI != BCE; ++BCI) { 515 assert(BlockToChain[*BCI] == &Chain); 516 for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 517 PE = (*BCI)->pred_end(); 518 PI != PE; ++PI) { 519 if (BlockToChain[*PI] == &Chain) 520 continue; 521 ++Chain.LoopPredecessors; 522 } 523 } 524 525 if (Chain.LoopPredecessors == 0) 526 BlockWorkList.push_back(BB); 527 } 528 529 BlockChain &FunctionChain = *BlockToChain[&F.front()]; 530 buildChain(&F.front(), FunctionChain, BlockWorkList); 531 532 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 533 DEBUG({ 534 FunctionBlockSetType FunctionBlockSet; 535 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 536 FunctionBlockSet.insert(FI); 537 538 for (BlockChain::iterator BCI = FunctionChain.begin(), BCE = FunctionChain.end(); 539 BCI != BCE; ++BCI) 540 if (!FunctionBlockSet.erase(*BCI)) 541 dbgs() << "Function chain contains a block not in the function!\n" 542 << " Bad block: " << getBlockName(*BCI) << "\n"; 543 544 if (!FunctionBlockSet.empty()) 545 for (SmallPtrSet<MachineBasicBlock *, 16>::iterator FBI = FunctionBlockSet.begin(), 546 FBE = FunctionBlockSet.end(); FBI != FBE; ++FBI) 547 dbgs() << "Function contains blocks never placed into a chain!\n" 548 << " Bad block: " << getBlockName(*FBI) << "\n"; 549 }); 550 551 // Splice the blocks into place. 552 MachineFunction::iterator InsertPos = F.begin(); 553 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 554 for (BlockChain::iterator BI = FunctionChain.begin(), BE = FunctionChain.end(); 555 BI != BE; ++BI) { 556 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 557 : " ... ") 558 << getBlockName(*BI) << "\n"); 559 if (InsertPos != MachineFunction::iterator(*BI)) 560 F.splice(InsertPos, *BI); 561 else 562 ++InsertPos; 563 564 // Update the terminator of the previous block. 565 if (BI == FunctionChain.begin()) 566 continue; 567 MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 568 569 // FIXME: It would be awesome of updateTerminator would just return rather 570 // than assert when the branch cannot be analyzed in order to remove this 571 // boiler plate. 572 Cond.clear(); 573 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 574 if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) 575 PrevBB->updateTerminator(); 576 } 577 578 // Fixup the last block. 579 Cond.clear(); 580 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 581 if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 582 F.back().updateTerminator(); 583} 584 585/// \brief Recursive helper to align a loop and any nested loops. 586static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) { 587 // Recurse through nested loops. 588 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 589 AlignLoop(F, *I, Align); 590 591 L->getTopBlock()->setAlignment(Align); 592} 593 594/// \brief Align loop headers to target preferred alignments. 595void MachineBlockPlacement::AlignLoops(MachineFunction &F) { 596 if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 597 return; 598 599 unsigned Align = TLI->getPrefLoopAlignment(); 600 if (!Align) 601 return; // Don't care about loop alignment. 602 603 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) 604 AlignLoop(F, *I, Align); 605} 606 607bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 608 // Check for single-block functions and skip them. 609 if (llvm::next(F.begin()) == F.end()) 610 return false; 611 612 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 613 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 614 MLI = &getAnalysis<MachineLoopInfo>(); 615 TII = F.getTarget().getInstrInfo(); 616 TLI = F.getTarget().getTargetLowering(); 617 assert(BlockToChain.empty()); 618 619 buildCFGChains(F); 620 AlignLoops(F); 621 622 BlockToChain.clear(); 623 624 // We always return true as we have no way to track whether the final order 625 // differs from the original order. 626 return true; 627} 628 629namespace { 630/// \brief A pass to compute block placement statistics. 631/// 632/// A separate pass to compute interesting statistics for evaluating block 633/// placement. This is separate from the actual placement pass so that they can 634/// be computed in the absense of any placement transformations or when using 635/// alternative placement strategies. 636class MachineBlockPlacementStats : public MachineFunctionPass { 637 /// \brief A handle to the branch probability pass. 638 const MachineBranchProbabilityInfo *MBPI; 639 640 /// \brief A handle to the function-wide block frequency pass. 641 const MachineBlockFrequencyInfo *MBFI; 642 643public: 644 static char ID; // Pass identification, replacement for typeid 645 MachineBlockPlacementStats() : MachineFunctionPass(ID) { 646 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 647 } 648 649 bool runOnMachineFunction(MachineFunction &F); 650 651 void getAnalysisUsage(AnalysisUsage &AU) const { 652 AU.addRequired<MachineBranchProbabilityInfo>(); 653 AU.addRequired<MachineBlockFrequencyInfo>(); 654 AU.setPreservesAll(); 655 MachineFunctionPass::getAnalysisUsage(AU); 656 } 657 658 const char *getPassName() const { return "Block Placement Stats"; } 659}; 660} 661 662char MachineBlockPlacementStats::ID = 0; 663INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 664 "Basic Block Placement Stats", false, false) 665INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 666INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 667INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 668 "Basic Block Placement Stats", false, false) 669 670FunctionPass *llvm::createMachineBlockPlacementStatsPass() { 671 return new MachineBlockPlacementStats(); 672} 673 674bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 675 // Check for single-block functions and skip them. 676 if (llvm::next(F.begin()) == F.end()) 677 return false; 678 679 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 680 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 681 682 for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 683 BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 684 Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 685 : NumUncondBranches; 686 Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 687 : UncondBranchTakenFreq; 688 for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 689 SE = I->succ_end(); 690 SI != SE; ++SI) { 691 // Skip if this successor is a fallthrough. 692 if (I->isLayoutSuccessor(*SI)) 693 continue; 694 695 BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 696 ++NumBranches; 697 BranchTakenFreq += EdgeFreq.getFrequency(); 698 } 699 } 700 701 return false; 702} 703 704