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 absence 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 #include "llvm/CodeGen/Passes.h" 29 #include "llvm/CodeGen/TargetPassConfig.h" 30 #include "BranchFolding.h" 31 #include "llvm/ADT/DenseMap.h" 32 #include "llvm/ADT/SmallPtrSet.h" 33 #include "llvm/ADT/SmallVector.h" 34 #include "llvm/ADT/Statistic.h" 35 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 36 #include "llvm/CodeGen/MachineBasicBlock.h" 37 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 38 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 39 #include "llvm/CodeGen/MachineDominators.h" 40 #include "llvm/CodeGen/MachineFunction.h" 41 #include "llvm/CodeGen/MachineFunctionPass.h" 42 #include "llvm/CodeGen/MachineLoopInfo.h" 43 #include "llvm/CodeGen/MachineModuleInfo.h" 44 #include "llvm/CodeGen/MachinePostDominators.h" 45 #include "llvm/CodeGen/TailDuplicator.h" 46 #include "llvm/Support/Allocator.h" 47 #include "llvm/Support/CommandLine.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include "llvm/Target/TargetInstrInfo.h" 51 #include "llvm/Target/TargetLowering.h" 52 #include "llvm/Target/TargetSubtargetInfo.h" 53 #include <algorithm> 54 #include <functional> 55 #include <utility> 56 using namespace llvm; 57 58 #define DEBUG_TYPE "block-placement" 59 60 STATISTIC(NumCondBranches, "Number of conditional branches"); 61 STATISTIC(NumUncondBranches, "Number of unconditional branches"); 62 STATISTIC(CondBranchTakenFreq, 63 "Potential frequency of taking conditional branches"); 64 STATISTIC(UncondBranchTakenFreq, 65 "Potential frequency of taking unconditional branches"); 66 67 static cl::opt<unsigned> AlignAllBlock("align-all-blocks", 68 cl::desc("Force the alignment of all " 69 "blocks in the function."), 70 cl::init(0), cl::Hidden); 71 72 static cl::opt<unsigned> AlignAllNonFallThruBlocks( 73 "align-all-nofallthru-blocks", 74 cl::desc("Force the alignment of all " 75 "blocks that have no fall-through predecessors (i.e. don't add " 76 "nops that are executed)."), 77 cl::init(0), cl::Hidden); 78 79 // FIXME: Find a good default for this flag and remove the flag. 80 static cl::opt<unsigned> ExitBlockBias( 81 "block-placement-exit-block-bias", 82 cl::desc("Block frequency percentage a loop exit block needs " 83 "over the original exit to be considered the new exit."), 84 cl::init(0), cl::Hidden); 85 86 // Definition: 87 // - Outlining: placement of a basic block outside the chain or hot path. 88 89 static cl::opt<bool> OutlineOptionalBranches( 90 "outline-optional-branches", 91 cl::desc("Outlining optional branches will place blocks that are optional " 92 "branches, i.e. branches with a common post dominator, outside " 93 "the hot path or chain"), 94 cl::init(false), cl::Hidden); 95 96 static cl::opt<unsigned> OutlineOptionalThreshold( 97 "outline-optional-threshold", 98 cl::desc("Don't outline optional branches that are a single block with an " 99 "instruction count below this threshold"), 100 cl::init(4), cl::Hidden); 101 102 static cl::opt<unsigned> LoopToColdBlockRatio( 103 "loop-to-cold-block-ratio", 104 cl::desc("Outline loop blocks from loop chain if (frequency of loop) / " 105 "(frequency of block) is greater than this ratio"), 106 cl::init(5), cl::Hidden); 107 108 static cl::opt<bool> 109 PreciseRotationCost("precise-rotation-cost", 110 cl::desc("Model the cost of loop rotation more " 111 "precisely by using profile data."), 112 cl::init(false), cl::Hidden); 113 static cl::opt<bool> 114 ForcePreciseRotationCost("force-precise-rotation-cost", 115 cl::desc("Force the use of precise cost " 116 "loop rotation strategy."), 117 cl::init(false), cl::Hidden); 118 119 static cl::opt<unsigned> MisfetchCost( 120 "misfetch-cost", 121 cl::desc("Cost that models the probabilistic risk of an instruction " 122 "misfetch due to a jump comparing to falling through, whose cost " 123 "is zero."), 124 cl::init(1), cl::Hidden); 125 126 static cl::opt<unsigned> JumpInstCost("jump-inst-cost", 127 cl::desc("Cost of jump instructions."), 128 cl::init(1), cl::Hidden); 129 static cl::opt<bool> 130 TailDupPlacement("tail-dup-placement", 131 cl::desc("Perform tail duplication during placement. " 132 "Creates more fallthrough opportunites in " 133 "outline branches."), 134 cl::init(true), cl::Hidden); 135 136 static cl::opt<bool> 137 BranchFoldPlacement("branch-fold-placement", 138 cl::desc("Perform branch folding during placement. " 139 "Reduces code size."), 140 cl::init(true), cl::Hidden); 141 142 // Heuristic for tail duplication. 143 static cl::opt<unsigned> TailDupPlacementThreshold( 144 "tail-dup-placement-threshold", 145 cl::desc("Instruction cutoff for tail duplication during layout. " 146 "Tail merging during layout is forced to have a threshold " 147 "that won't conflict."), cl::init(2), 148 cl::Hidden); 149 150 // Heuristic for tail duplication. 151 static cl::opt<unsigned> TailDupPlacementPenalty( 152 "tail-dup-placement-penalty", 153 cl::desc("Cost penalty for blocks that can avoid breaking CFG by copying. " 154 "Copying can increase fallthrough, but it also increases icache " 155 "pressure. This parameter controls the penalty to account for that. " 156 "Percent as integer."), 157 cl::init(2), 158 cl::Hidden); 159 160 extern cl::opt<unsigned> StaticLikelyProb; 161 extern cl::opt<unsigned> ProfileLikelyProb; 162 163 // Internal option used to control BFI display only after MBP pass. 164 // Defined in CodeGen/MachineBlockFrequencyInfo.cpp: 165 // -view-block-layout-with-bfi= 166 extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI; 167 168 // Command line option to specify the name of the function for CFG dump 169 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name= 170 extern cl::opt<std::string> ViewBlockFreqFuncName; 171 172 namespace { 173 class BlockChain; 174 /// \brief Type for our function-wide basic block -> block chain mapping. 175 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 176 } 177 178 namespace { 179 /// \brief A chain of blocks which will be laid out contiguously. 180 /// 181 /// This is the datastructure representing a chain of consecutive blocks that 182 /// are profitable to layout together in order to maximize fallthrough 183 /// probabilities and code locality. We also can use a block chain to represent 184 /// a sequence of basic blocks which have some external (correctness) 185 /// requirement for sequential layout. 186 /// 187 /// Chains can be built around a single basic block and can be merged to grow 188 /// them. They participate in a block-to-chain mapping, which is updated 189 /// automatically as chains are merged together. 190 class BlockChain { 191 /// \brief The sequence of blocks belonging to this chain. 192 /// 193 /// This is the sequence of blocks for a particular chain. These will be laid 194 /// out in-order within the function. 195 SmallVector<MachineBasicBlock *, 4> Blocks; 196 197 /// \brief A handle to the function-wide basic block to block chain mapping. 198 /// 199 /// This is retained in each block chain to simplify the computation of child 200 /// block chains for SCC-formation and iteration. We store the edges to child 201 /// basic blocks, and map them back to their associated chains using this 202 /// structure. 203 BlockToChainMapType &BlockToChain; 204 205 public: 206 /// \brief Construct a new BlockChain. 207 /// 208 /// This builds a new block chain representing a single basic block in the 209 /// function. It also registers itself as the chain that block participates 210 /// in with the BlockToChain mapping. 211 BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) 212 : Blocks(1, BB), BlockToChain(BlockToChain), UnscheduledPredecessors(0) { 213 assert(BB && "Cannot create a chain with a null basic block"); 214 BlockToChain[BB] = this; 215 } 216 217 /// \brief Iterator over blocks within the chain. 218 typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator; 219 220 /// \brief Beginning of blocks within the chain. 221 iterator begin() { return Blocks.begin(); } 222 223 /// \brief End of blocks within the chain. 224 iterator end() { return Blocks.end(); } 225 226 bool remove(MachineBasicBlock* BB) { 227 for(iterator i = begin(); i != end(); ++i) { 228 if (*i == BB) { 229 Blocks.erase(i); 230 return true; 231 } 232 } 233 return false; 234 } 235 236 /// \brief Merge a block chain into this one. 237 /// 238 /// This routine merges a block chain into this one. It takes care of forming 239 /// a contiguous sequence of basic blocks, updating the edge list, and 240 /// updating the block -> chain mapping. It does not free or tear down the 241 /// old chain, but the old chain's block list is no longer valid. 242 void merge(MachineBasicBlock *BB, BlockChain *Chain) { 243 assert(BB); 244 assert(!Blocks.empty()); 245 246 // Fast path in case we don't have a chain already. 247 if (!Chain) { 248 assert(!BlockToChain[BB]); 249 Blocks.push_back(BB); 250 BlockToChain[BB] = this; 251 return; 252 } 253 254 assert(BB == *Chain->begin()); 255 assert(Chain->begin() != Chain->end()); 256 257 // Update the incoming blocks to point to this chain, and add them to the 258 // chain structure. 259 for (MachineBasicBlock *ChainBB : *Chain) { 260 Blocks.push_back(ChainBB); 261 assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain"); 262 BlockToChain[ChainBB] = this; 263 } 264 } 265 266 #ifndef NDEBUG 267 /// \brief Dump the blocks in this chain. 268 LLVM_DUMP_METHOD void dump() { 269 for (MachineBasicBlock *MBB : *this) 270 MBB->dump(); 271 } 272 #endif // NDEBUG 273 274 /// \brief Count of predecessors of any block within the chain which have not 275 /// yet been scheduled. In general, we will delay scheduling this chain 276 /// until those predecessors are scheduled (or we find a sufficiently good 277 /// reason to override this heuristic.) Note that when forming loop chains, 278 /// blocks outside the loop are ignored and treated as if they were already 279 /// scheduled. 280 /// 281 /// Note: This field is reinitialized multiple times - once for each loop, 282 /// and then once for the function as a whole. 283 unsigned UnscheduledPredecessors; 284 }; 285 } 286 287 namespace { 288 class MachineBlockPlacement : public MachineFunctionPass { 289 /// \brief A typedef for a block filter set. 290 typedef SmallSetVector<MachineBasicBlock *, 16> BlockFilterSet; 291 292 /// Pair struct containing basic block and taildup profitiability 293 struct BlockAndTailDupResult { 294 MachineBasicBlock * BB; 295 bool ShouldTailDup; 296 }; 297 298 /// \brief work lists of blocks that are ready to be laid out 299 SmallVector<MachineBasicBlock *, 16> BlockWorkList; 300 SmallVector<MachineBasicBlock *, 16> EHPadWorkList; 301 302 /// \brief Machine Function 303 MachineFunction *F; 304 305 /// \brief A handle to the branch probability pass. 306 const MachineBranchProbabilityInfo *MBPI; 307 308 /// \brief A handle to the function-wide block frequency pass. 309 std::unique_ptr<BranchFolder::MBFIWrapper> MBFI; 310 311 /// \brief A handle to the loop info. 312 MachineLoopInfo *MLI; 313 314 /// \brief Preferred loop exit. 315 /// Member variable for convenience. It may be removed by duplication deep 316 /// in the call stack. 317 MachineBasicBlock *PreferredLoopExit; 318 319 /// \brief A handle to the target's instruction info. 320 const TargetInstrInfo *TII; 321 322 /// \brief A handle to the target's lowering info. 323 const TargetLoweringBase *TLI; 324 325 /// \brief A handle to the dominator tree. 326 MachineDominatorTree *MDT; 327 328 /// \brief A handle to the post dominator tree. 329 MachinePostDominatorTree *MPDT; 330 331 /// \brief Duplicator used to duplicate tails during placement. 332 /// 333 /// Placement decisions can open up new tail duplication opportunities, but 334 /// since tail duplication affects placement decisions of later blocks, it 335 /// must be done inline. 336 TailDuplicator TailDup; 337 338 /// \brief A set of blocks that are unavoidably execute, i.e. they dominate 339 /// all terminators of the MachineFunction. 340 SmallPtrSet<MachineBasicBlock *, 4> UnavoidableBlocks; 341 342 /// \brief Allocator and owner of BlockChain structures. 343 /// 344 /// We build BlockChains lazily while processing the loop structure of 345 /// a function. To reduce malloc traffic, we allocate them using this 346 /// slab-like allocator, and destroy them after the pass completes. An 347 /// important guarantee is that this allocator produces stable pointers to 348 /// the chains. 349 SpecificBumpPtrAllocator<BlockChain> ChainAllocator; 350 351 /// \brief Function wide BasicBlock to BlockChain mapping. 352 /// 353 /// This mapping allows efficiently moving from any given basic block to the 354 /// BlockChain it participates in, if any. We use it to, among other things, 355 /// allow implicitly defining edges between chains as the existing edges 356 /// between basic blocks. 357 DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain; 358 359 #ifndef NDEBUG 360 /// The set of basic blocks that have terminators that cannot be fully 361 /// analyzed. These basic blocks cannot be re-ordered safely by 362 /// MachineBlockPlacement, and we must preserve physical layout of these 363 /// blocks and their successors through the pass. 364 SmallPtrSet<MachineBasicBlock *, 4> BlocksWithUnanalyzableExits; 365 #endif 366 367 /// Decrease the UnscheduledPredecessors count for all blocks in chain, and 368 /// if the count goes to 0, add them to the appropriate work list. 369 void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, 370 const BlockFilterSet *BlockFilter = nullptr); 371 372 /// Decrease the UnscheduledPredecessors count for a single block, and 373 /// if the count goes to 0, add them to the appropriate work list. 374 void markBlockSuccessors( 375 BlockChain &Chain, MachineBasicBlock *BB, MachineBasicBlock *LoopHeaderBB, 376 const BlockFilterSet *BlockFilter = nullptr); 377 378 379 BranchProbability 380 collectViableSuccessors(MachineBasicBlock *BB, BlockChain &Chain, 381 const BlockFilterSet *BlockFilter, 382 SmallVector<MachineBasicBlock *, 4> &Successors); 383 bool shouldPredBlockBeOutlined(MachineBasicBlock *BB, MachineBasicBlock *Succ, 384 BlockChain &Chain, 385 const BlockFilterSet *BlockFilter, 386 BranchProbability SuccProb, 387 BranchProbability HotProb); 388 bool repeatedlyTailDuplicateBlock( 389 MachineBasicBlock *BB, MachineBasicBlock *&LPred, 390 MachineBasicBlock *LoopHeaderBB, 391 BlockChain &Chain, BlockFilterSet *BlockFilter, 392 MachineFunction::iterator &PrevUnplacedBlockIt); 393 bool maybeTailDuplicateBlock(MachineBasicBlock *BB, MachineBasicBlock *LPred, 394 const BlockChain &Chain, 395 BlockFilterSet *BlockFilter, 396 MachineFunction::iterator &PrevUnplacedBlockIt, 397 bool &DuplicatedToPred); 398 bool 399 hasBetterLayoutPredecessor(MachineBasicBlock *BB, MachineBasicBlock *Succ, 400 BlockChain &SuccChain, BranchProbability SuccProb, 401 BranchProbability RealSuccProb, BlockChain &Chain, 402 const BlockFilterSet *BlockFilter); 403 BlockAndTailDupResult selectBestSuccessor(MachineBasicBlock *BB, 404 BlockChain &Chain, 405 const BlockFilterSet *BlockFilter); 406 MachineBasicBlock * 407 selectBestCandidateBlock(BlockChain &Chain, 408 SmallVectorImpl<MachineBasicBlock *> &WorkList); 409 MachineBasicBlock * 410 getFirstUnplacedBlock(const BlockChain &PlacedChain, 411 MachineFunction::iterator &PrevUnplacedBlockIt, 412 const BlockFilterSet *BlockFilter); 413 414 /// \brief Add a basic block to the work list if it is appropriate. 415 /// 416 /// If the optional parameter BlockFilter is provided, only MBB 417 /// present in the set will be added to the worklist. If nullptr 418 /// is provided, no filtering occurs. 419 void fillWorkLists(MachineBasicBlock *MBB, 420 SmallPtrSetImpl<BlockChain *> &UpdatedPreds, 421 const BlockFilterSet *BlockFilter); 422 void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 423 BlockFilterSet *BlockFilter = nullptr); 424 MachineBasicBlock *findBestLoopTop(MachineLoop &L, 425 const BlockFilterSet &LoopBlockSet); 426 MachineBasicBlock *findBestLoopExit(MachineLoop &L, 427 const BlockFilterSet &LoopBlockSet); 428 BlockFilterSet collectLoopBlockSet(MachineLoop &L); 429 void buildLoopChains(MachineLoop &L); 430 void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, 431 const BlockFilterSet &LoopBlockSet); 432 void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L, 433 const BlockFilterSet &LoopBlockSet); 434 void collectMustExecuteBBs(); 435 void buildCFGChains(); 436 void optimizeBranches(); 437 void alignBlocks(); 438 bool shouldTailDuplicate(MachineBasicBlock *BB); 439 /// Check the edge frequencies to see if tail duplication will increase 440 /// fallthroughs. 441 bool isProfitableToTailDup( 442 MachineBasicBlock *BB, MachineBasicBlock *Succ, 443 BranchProbability AdjustedSumProb, 444 BlockChain &Chain, const BlockFilterSet *BlockFilter); 445 /// Returns true if a block can tail duplicate into all unplaced 446 /// predecessors. Filters based on loop. 447 bool canTailDuplicateUnplacedPreds( 448 MachineBasicBlock *BB, MachineBasicBlock *Succ, 449 BlockChain &Chain, const BlockFilterSet *BlockFilter); 450 451 public: 452 static char ID; // Pass identification, replacement for typeid 453 MachineBlockPlacement() : MachineFunctionPass(ID) { 454 initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); 455 } 456 457 bool runOnMachineFunction(MachineFunction &F) override; 458 459 void getAnalysisUsage(AnalysisUsage &AU) const override { 460 AU.addRequired<MachineBranchProbabilityInfo>(); 461 AU.addRequired<MachineBlockFrequencyInfo>(); 462 AU.addRequired<MachineDominatorTree>(); 463 if (TailDupPlacement) 464 AU.addRequired<MachinePostDominatorTree>(); 465 AU.addRequired<MachineLoopInfo>(); 466 AU.addRequired<TargetPassConfig>(); 467 MachineFunctionPass::getAnalysisUsage(AU); 468 } 469 }; 470 } 471 472 char MachineBlockPlacement::ID = 0; 473 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; 474 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement", 475 "Branch Probability Basic Block Placement", false, false) 476 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 477 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 478 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 479 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree) 480 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 481 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement", 482 "Branch Probability Basic Block Placement", false, false) 483 484 #ifndef NDEBUG 485 /// \brief Helper to print the name of a MBB. 486 /// 487 /// Only used by debug logging. 488 static std::string getBlockName(MachineBasicBlock *BB) { 489 std::string Result; 490 raw_string_ostream OS(Result); 491 OS << "BB#" << BB->getNumber(); 492 OS << " ('" << BB->getName() << "')"; 493 OS.flush(); 494 return Result; 495 } 496 #endif 497 498 /// \brief Mark a chain's successors as having one fewer preds. 499 /// 500 /// When a chain is being merged into the "placed" chain, this routine will 501 /// quickly walk the successors of each block in the chain and mark them as 502 /// having one fewer active predecessor. It also adds any successors of this 503 /// chain which reach the zero-predecessor state to the appropriate worklist. 504 void MachineBlockPlacement::markChainSuccessors( 505 BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, 506 const BlockFilterSet *BlockFilter) { 507 // Walk all the blocks in this chain, marking their successors as having 508 // a predecessor placed. 509 for (MachineBasicBlock *MBB : Chain) { 510 markBlockSuccessors(Chain, MBB, LoopHeaderBB, BlockFilter); 511 } 512 } 513 514 /// \brief Mark a single block's successors as having one fewer preds. 515 /// 516 /// Under normal circumstances, this is only called by markChainSuccessors, 517 /// but if a block that was to be placed is completely tail-duplicated away, 518 /// and was duplicated into the chain end, we need to redo markBlockSuccessors 519 /// for just that block. 520 void MachineBlockPlacement::markBlockSuccessors( 521 BlockChain &Chain, MachineBasicBlock *MBB, MachineBasicBlock *LoopHeaderBB, 522 const BlockFilterSet *BlockFilter) { 523 // Add any successors for which this is the only un-placed in-loop 524 // predecessor to the worklist as a viable candidate for CFG-neutral 525 // placement. No subsequent placement of this block will violate the CFG 526 // shape, so we get to use heuristics to choose a favorable placement. 527 for (MachineBasicBlock *Succ : MBB->successors()) { 528 if (BlockFilter && !BlockFilter->count(Succ)) 529 continue; 530 BlockChain &SuccChain = *BlockToChain[Succ]; 531 // Disregard edges within a fixed chain, or edges to the loop header. 532 if (&Chain == &SuccChain || Succ == LoopHeaderBB) 533 continue; 534 535 // This is a cross-chain edge that is within the loop, so decrement the 536 // loop predecessor count of the destination chain. 537 if (SuccChain.UnscheduledPredecessors == 0 || 538 --SuccChain.UnscheduledPredecessors > 0) 539 continue; 540 541 auto *NewBB = *SuccChain.begin(); 542 if (NewBB->isEHPad()) 543 EHPadWorkList.push_back(NewBB); 544 else 545 BlockWorkList.push_back(NewBB); 546 } 547 } 548 549 /// This helper function collects the set of successors of block 550 /// \p BB that are allowed to be its layout successors, and return 551 /// the total branch probability of edges from \p BB to those 552 /// blocks. 553 BranchProbability MachineBlockPlacement::collectViableSuccessors( 554 MachineBasicBlock *BB, BlockChain &Chain, const BlockFilterSet *BlockFilter, 555 SmallVector<MachineBasicBlock *, 4> &Successors) { 556 // Adjust edge probabilities by excluding edges pointing to blocks that is 557 // either not in BlockFilter or is already in the current chain. Consider the 558 // following CFG: 559 // 560 // --->A 561 // | / \ 562 // | B C 563 // | \ / \ 564 // ----D E 565 // 566 // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after 567 // A->C is chosen as a fall-through, D won't be selected as a successor of C 568 // due to CFG constraint (the probability of C->D is not greater than 569 // HotProb to break top-order). If we exclude E that is not in BlockFilter 570 // when calculating the probability of C->D, D will be selected and we 571 // will get A C D B as the layout of this loop. 572 auto AdjustedSumProb = BranchProbability::getOne(); 573 for (MachineBasicBlock *Succ : BB->successors()) { 574 bool SkipSucc = false; 575 if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) { 576 SkipSucc = true; 577 } else { 578 BlockChain *SuccChain = BlockToChain[Succ]; 579 if (SuccChain == &Chain) { 580 SkipSucc = true; 581 } else if (Succ != *SuccChain->begin()) { 582 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Mid chain!\n"); 583 continue; 584 } 585 } 586 if (SkipSucc) 587 AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ); 588 else 589 Successors.push_back(Succ); 590 } 591 592 return AdjustedSumProb; 593 } 594 595 /// The helper function returns the branch probability that is adjusted 596 /// or normalized over the new total \p AdjustedSumProb. 597 static BranchProbability 598 getAdjustedProbability(BranchProbability OrigProb, 599 BranchProbability AdjustedSumProb) { 600 BranchProbability SuccProb; 601 uint32_t SuccProbN = OrigProb.getNumerator(); 602 uint32_t SuccProbD = AdjustedSumProb.getNumerator(); 603 if (SuccProbN >= SuccProbD) 604 SuccProb = BranchProbability::getOne(); 605 else 606 SuccProb = BranchProbability(SuccProbN, SuccProbD); 607 608 return SuccProb; 609 } 610 611 /// Check if a block should be tail duplicated. 612 /// \p BB Block to check. 613 bool MachineBlockPlacement::shouldTailDuplicate(MachineBasicBlock *BB) { 614 // Blocks with single successors don't create additional fallthrough 615 // opportunities. Don't duplicate them. TODO: When conditional exits are 616 // analyzable, allow them to be duplicated. 617 bool IsSimple = TailDup.isSimpleBB(BB); 618 619 if (BB->succ_size() == 1) 620 return false; 621 return TailDup.shouldTailDuplicate(IsSimple, *BB); 622 } 623 624 /// Compare 2 BlockFrequency's with a small penalty for \p A. 625 /// In order to be conservative, we apply a X% penalty to account for 626 /// increased icache pressure and static heuristics. For small frequencies 627 /// we use only the numerators to improve accuracy. For simplicity, we assume the 628 /// penalty is less than 100% 629 /// TODO(iteratee): Use 64-bit fixed point edge frequencies everywhere. 630 static bool greaterWithBias(BlockFrequency A, BlockFrequency B, 631 uint64_t EntryFreq) { 632 BranchProbability ThresholdProb(TailDupPlacementPenalty, 100); 633 BlockFrequency Gain = A - B; 634 return (Gain / ThresholdProb).getFrequency() >= EntryFreq; 635 } 636 637 /// Check the edge frequencies to see if tail duplication will increase 638 /// fallthroughs. It only makes sense to call this function when 639 /// \p Succ would not be chosen otherwise. Tail duplication of \p Succ is 640 /// always locally profitable if we would have picked \p Succ without 641 /// considering duplication. 642 bool MachineBlockPlacement::isProfitableToTailDup( 643 MachineBasicBlock *BB, MachineBasicBlock *Succ, 644 BranchProbability QProb, 645 BlockChain &Chain, const BlockFilterSet *BlockFilter) { 646 // We need to do a probability calculation to make sure this is profitable. 647 // First: does succ have a successor that post-dominates? This affects the 648 // calculation. The 2 relevant cases are: 649 // BB BB 650 // | \Qout | \Qout 651 // P| C |P C 652 // = C' = C' 653 // | /Qin | /Qin 654 // | / | / 655 // Succ Succ 656 // / \ | \ V 657 // U/ =V |U \ 658 // / \ = D 659 // D E | / 660 // | / 661 // |/ 662 // PDom 663 // '=' : Branch taken for that CFG edge 664 // In the second case, Placing Succ while duplicating it into C prevents the 665 // fallthrough of Succ into either D or PDom, because they now have C as an 666 // unplaced predecessor 667 668 // Start by figuring out which case we fall into 669 MachineBasicBlock *PDom = nullptr; 670 SmallVector<MachineBasicBlock *, 4> SuccSuccs; 671 // Only scan the relevant successors 672 auto AdjustedSuccSumProb = 673 collectViableSuccessors(Succ, Chain, BlockFilter, SuccSuccs); 674 BranchProbability PProb = MBPI->getEdgeProbability(BB, Succ); 675 auto BBFreq = MBFI->getBlockFreq(BB); 676 auto SuccFreq = MBFI->getBlockFreq(Succ); 677 BlockFrequency P = BBFreq * PProb; 678 BlockFrequency Qout = BBFreq * QProb; 679 uint64_t EntryFreq = MBFI->getEntryFreq(); 680 // If there are no more successors, it is profitable to copy, as it strictly 681 // increases fallthrough. 682 if (SuccSuccs.size() == 0) 683 return greaterWithBias(P, Qout, EntryFreq); 684 685 auto BestSuccSucc = BranchProbability::getZero(); 686 // Find the PDom or the best Succ if no PDom exists. 687 for (MachineBasicBlock *SuccSucc : SuccSuccs) { 688 auto Prob = MBPI->getEdgeProbability(Succ, SuccSucc); 689 if (Prob > BestSuccSucc) 690 BestSuccSucc = Prob; 691 if (PDom == nullptr) 692 if (MPDT->dominates(SuccSucc, Succ)) { 693 PDom = SuccSucc; 694 break; 695 } 696 } 697 // For the comparisons, we need to know Succ's best incoming edge that isn't 698 // from BB. 699 auto SuccBestPred = BlockFrequency(0); 700 for (MachineBasicBlock *SuccPred : Succ->predecessors()) { 701 if (SuccPred == Succ || SuccPred == BB 702 || BlockToChain[SuccPred] == &Chain 703 || (BlockFilter && !BlockFilter->count(SuccPred))) 704 continue; 705 auto Freq = MBFI->getBlockFreq(SuccPred) 706 * MBPI->getEdgeProbability(SuccPred, Succ); 707 if (Freq > SuccBestPred) 708 SuccBestPred = Freq; 709 } 710 // Qin is Succ's best unplaced incoming edge that isn't BB 711 BlockFrequency Qin = SuccBestPred; 712 // If it doesn't have a post-dominating successor, here is the calculation: 713 // BB BB 714 // | \Qout | \ 715 // P| C | = 716 // = C' | C 717 // | /Qin | | 718 // | / | C' (+Succ) 719 // Succ Succ /| 720 // / \ | \/ | 721 // U/ =V = /= = 722 // / \ | / \| 723 // D E D E 724 // '=' : Branch taken for that CFG edge 725 // Cost in the first case is: P + V 726 // For this calculation, we always assume P > Qout. If Qout > P 727 // The result of this function will be ignored at the caller. 728 // Cost in the second case is: Qout + Qin * V + P * U + P * V 729 // TODO(iteratee): If we lay out D after Succ, the P * U term 730 // goes away. This logic is coming in D28522. 731 732 if (PDom == nullptr || !Succ->isSuccessor(PDom)) { 733 BranchProbability UProb = BestSuccSucc; 734 BranchProbability VProb = AdjustedSuccSumProb - UProb; 735 BlockFrequency V = SuccFreq * VProb; 736 BlockFrequency QinV = Qin * VProb; 737 BlockFrequency BaseCost = P + V; 738 BlockFrequency DupCost = Qout + QinV + P * AdjustedSuccSumProb; 739 return greaterWithBias(BaseCost, DupCost, EntryFreq); 740 } 741 BranchProbability UProb = MBPI->getEdgeProbability(Succ, PDom); 742 BranchProbability VProb = AdjustedSuccSumProb - UProb; 743 BlockFrequency U = SuccFreq * UProb; 744 BlockFrequency V = SuccFreq * VProb; 745 // If there is a post-dominating successor, here is the calculation: 746 // BB BB BB BB 747 // | \Qout | \ | \Qout | \ 748 // |P C | = |P C | = 749 // = C' |P C = C' |P C 750 // | /Qin | | | /Qin | | 751 // | / | C' (+Succ) | / | C' (+Succ) 752 // Succ Succ /| Succ Succ /| 753 // | \ V | \/ | | \ V | \/ | 754 // |U \ |U /\ | |U = |U /\ | 755 // = D = = =| | D | = =| 756 // | / |/ D | / |/ D 757 // | / | / | = | / 758 // |/ | / |/ | = 759 // Dom Dom Dom Dom 760 // '=' : Branch taken for that CFG edge 761 // The cost for taken branches in the first case is P + U 762 // The cost in the second case (assuming independence), given the layout: 763 // BB, Succ, (C+Succ), D, Dom 764 // is Qout + P * V + Qin * U 765 // compare P + U vs Qout + P + Qin * U. 766 // 767 // The 3rd and 4th cases cover when Dom would be chosen to follow Succ. 768 // 769 // For the 3rd case, the cost is P + 2 * V 770 // For the 4th case, the cost is Qout + Qin * U + P * V + V 771 // We choose 4 over 3 when (P + V) > Qout + Qin * U + P * V 772 if (UProb > AdjustedSuccSumProb / 2 773 && !hasBetterLayoutPredecessor(Succ, PDom, *BlockToChain[PDom], 774 UProb, UProb, Chain, BlockFilter)) { 775 // Cases 3 & 4 776 return greaterWithBias((P + V), (Qout + Qin * UProb + P * VProb), 777 EntryFreq); 778 } 779 // Cases 1 & 2 780 return greaterWithBias( 781 (P + U), (Qout + Qin * UProb + P * AdjustedSuccSumProb), EntryFreq); 782 } 783 784 785 /// When the option TailDupPlacement is on, this method checks if the 786 /// fallthrough candidate block \p Succ (of block \p BB) can be tail-duplicated 787 /// into all of its unplaced, unfiltered predecessors, that are not BB. 788 bool MachineBlockPlacement::canTailDuplicateUnplacedPreds( 789 MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &Chain, 790 const BlockFilterSet *BlockFilter) { 791 if (!shouldTailDuplicate(Succ)) 792 return false; 793 794 for (MachineBasicBlock *Pred : Succ->predecessors()) { 795 // Make sure all unplaced and unfiltered predecessors can be 796 // tail-duplicated into. 797 if (Pred == BB || (BlockFilter && !BlockFilter->count(Pred)) 798 || BlockToChain[Pred] == &Chain) 799 continue; 800 if (!TailDup.canTailDuplicate(Succ, Pred)) 801 return false; 802 } 803 return true; 804 } 805 806 /// When the option OutlineOptionalBranches is on, this method 807 /// checks if the fallthrough candidate block \p Succ (of block 808 /// \p BB) also has other unscheduled predecessor blocks which 809 /// are also successors of \p BB (forming triangular shape CFG). 810 /// If none of such predecessors are small, it returns true. 811 /// The caller can choose to select \p Succ as the layout successors 812 /// so that \p Succ's predecessors (optional branches) can be 813 /// outlined. 814 /// FIXME: fold this with more general layout cost analysis. 815 bool MachineBlockPlacement::shouldPredBlockBeOutlined( 816 MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &Chain, 817 const BlockFilterSet *BlockFilter, BranchProbability SuccProb, 818 BranchProbability HotProb) { 819 if (!OutlineOptionalBranches) 820 return false; 821 // If we outline optional branches, look whether Succ is unavoidable, i.e. 822 // dominates all terminators of the MachineFunction. If it does, other 823 // successors must be optional. Don't do this for cold branches. 824 if (SuccProb > HotProb.getCompl() && UnavoidableBlocks.count(Succ) > 0) { 825 for (MachineBasicBlock *Pred : Succ->predecessors()) { 826 // Check whether there is an unplaced optional branch. 827 if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) || 828 BlockToChain[Pred] == &Chain) 829 continue; 830 // Check whether the optional branch has exactly one BB. 831 if (Pred->pred_size() > 1 || *Pred->pred_begin() != BB) 832 continue; 833 // Check whether the optional branch is small. 834 if (Pred->size() < OutlineOptionalThreshold) 835 return false; 836 } 837 return true; 838 } else 839 return false; 840 } 841 842 // When profile is not present, return the StaticLikelyProb. 843 // When profile is available, we need to handle the triangle-shape CFG. 844 static BranchProbability getLayoutSuccessorProbThreshold( 845 MachineBasicBlock *BB) { 846 if (!BB->getParent()->getFunction()->getEntryCount()) 847 return BranchProbability(StaticLikelyProb, 100); 848 if (BB->succ_size() == 2) { 849 const MachineBasicBlock *Succ1 = *BB->succ_begin(); 850 const MachineBasicBlock *Succ2 = *(BB->succ_begin() + 1); 851 if (Succ1->isSuccessor(Succ2) || Succ2->isSuccessor(Succ1)) { 852 /* See case 1 below for the cost analysis. For BB->Succ to 853 * be taken with smaller cost, the following needs to hold: 854 * Prob(BB->Succ) > 2 * Prob(BB->Pred) 855 * So the threshold T in the calculation below 856 * (1-T) * Prob(BB->Succ) > T * Prob(BB->Pred) 857 * So T / (1 - T) = 2, Yielding T = 2/3 858 * Also adding user specified branch bias, we have 859 * T = (2/3)*(ProfileLikelyProb/50) 860 * = (2*ProfileLikelyProb)/150) 861 */ 862 return BranchProbability(2 * ProfileLikelyProb, 150); 863 } 864 } 865 return BranchProbability(ProfileLikelyProb, 100); 866 } 867 868 /// Checks to see if the layout candidate block \p Succ has a better layout 869 /// predecessor than \c BB. If yes, returns true. 870 /// \p SuccProb: The probability adjusted for only remaining blocks. 871 /// Only used for logging 872 /// \p RealSuccProb: The un-adjusted probability. 873 /// \p Chain: The chain that BB belongs to and Succ is being considered for. 874 /// \p BlockFilter: if non-null, the set of blocks that make up the loop being 875 /// considered 876 bool MachineBlockPlacement::hasBetterLayoutPredecessor( 877 MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &SuccChain, 878 BranchProbability SuccProb, BranchProbability RealSuccProb, 879 BlockChain &Chain, const BlockFilterSet *BlockFilter) { 880 881 // There isn't a better layout when there are no unscheduled predecessors. 882 if (SuccChain.UnscheduledPredecessors == 0) 883 return false; 884 885 // There are two basic scenarios here: 886 // ------------------------------------- 887 // Case 1: triangular shape CFG (if-then): 888 // BB 889 // | \ 890 // | \ 891 // | Pred 892 // | / 893 // Succ 894 // In this case, we are evaluating whether to select edge -> Succ, e.g. 895 // set Succ as the layout successor of BB. Picking Succ as BB's 896 // successor breaks the CFG constraints (FIXME: define these constraints). 897 // With this layout, Pred BB 898 // is forced to be outlined, so the overall cost will be cost of the 899 // branch taken from BB to Pred, plus the cost of back taken branch 900 // from Pred to Succ, as well as the additional cost associated 901 // with the needed unconditional jump instruction from Pred To Succ. 902 903 // The cost of the topological order layout is the taken branch cost 904 // from BB to Succ, so to make BB->Succ a viable candidate, the following 905 // must hold: 906 // 2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost 907 // < freq(BB->Succ) * taken_branch_cost. 908 // Ignoring unconditional jump cost, we get 909 // freq(BB->Succ) > 2 * freq(BB->Pred), i.e., 910 // prob(BB->Succ) > 2 * prob(BB->Pred) 911 // 912 // When real profile data is available, we can precisely compute the 913 // probability threshold that is needed for edge BB->Succ to be considered. 914 // Without profile data, the heuristic requires the branch bias to be 915 // a lot larger to make sure the signal is very strong (e.g. 80% default). 916 // ----------------------------------------------------------------- 917 // Case 2: diamond like CFG (if-then-else): 918 // S 919 // / \ 920 // | \ 921 // BB Pred 922 // \ / 923 // Succ 924 // .. 925 // 926 // The current block is BB and edge BB->Succ is now being evaluated. 927 // Note that edge S->BB was previously already selected because 928 // prob(S->BB) > prob(S->Pred). 929 // At this point, 2 blocks can be placed after BB: Pred or Succ. If we 930 // choose Pred, we will have a topological ordering as shown on the left 931 // in the picture below. If we choose Succ, we have the solution as shown 932 // on the right: 933 // 934 // topo-order: 935 // 936 // S----- ---S 937 // | | | | 938 // ---BB | | BB 939 // | | | | 940 // | pred-- | Succ-- 941 // | | | | 942 // ---succ ---pred-- 943 // 944 // cost = freq(S->Pred) + freq(BB->Succ) cost = 2 * freq (S->Pred) 945 // = freq(S->Pred) + freq(S->BB) 946 // 947 // If we have profile data (i.e, branch probabilities can be trusted), the 948 // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 * 949 // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB). 950 // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which 951 // means the cost of topological order is greater. 952 // When profile data is not available, however, we need to be more 953 // conservative. If the branch prediction is wrong, breaking the topo-order 954 // will actually yield a layout with large cost. For this reason, we need 955 // strong biased branch at block S with Prob(S->BB) in order to select 956 // BB->Succ. This is equivalent to looking the CFG backward with backward 957 // edge: Prob(Succ->BB) needs to >= HotProb in order to be selected (without 958 // profile data). 959 // -------------------------------------------------------------------------- 960 // Case 3: forked diamond 961 // S 962 // / \ 963 // / \ 964 // BB Pred 965 // | \ / | 966 // | \ / | 967 // | X | 968 // | / \ | 969 // | / \ | 970 // S1 S2 971 // 972 // The current block is BB and edge BB->S1 is now being evaluated. 973 // As above S->BB was already selected because 974 // prob(S->BB) > prob(S->Pred). Assume that prob(BB->S1) >= prob(BB->S2). 975 // 976 // topo-order: 977 // 978 // S-------| ---S 979 // | | | | 980 // ---BB | | BB 981 // | | | | 982 // | Pred----| | S1---- 983 // | | | | 984 // --(S1 or S2) ---Pred-- 985 // 986 // topo-cost = freq(S->Pred) + freq(BB->S1) + freq(BB->S2) 987 // + min(freq(Pred->S1), freq(Pred->S2)) 988 // Non-topo-order cost: 989 // In the worst case, S2 will not get laid out after Pred. 990 // non-topo-cost = 2 * freq(S->Pred) + freq(BB->S2). 991 // To be conservative, we can assume that min(freq(Pred->S1), freq(Pred->S2)) 992 // is 0. Then the non topo layout is better when 993 // freq(S->Pred) < freq(BB->S1). 994 // This is exactly what is checked below. 995 // Note there are other shapes that apply (Pred may not be a single block, 996 // but they all fit this general pattern.) 997 BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB); 998 999 // Make sure that a hot successor doesn't have a globally more 1000 // important predecessor. 1001 BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb; 1002 bool BadCFGConflict = false; 1003 1004 for (MachineBasicBlock *Pred : Succ->predecessors()) { 1005 if (Pred == Succ || BlockToChain[Pred] == &SuccChain || 1006 (BlockFilter && !BlockFilter->count(Pred)) || 1007 BlockToChain[Pred] == &Chain || 1008 // This check is redundant except for look ahead. This function is 1009 // called for lookahead by isProfitableToTailDup when BB hasn't been 1010 // placed yet. 1011 (Pred == BB)) 1012 continue; 1013 // Do backward checking. 1014 // For all cases above, we need a backward checking to filter out edges that 1015 // are not 'strongly' biased. 1016 // BB Pred 1017 // \ / 1018 // Succ 1019 // We select edge BB->Succ if 1020 // freq(BB->Succ) > freq(Succ) * HotProb 1021 // i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) * 1022 // HotProb 1023 // i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb 1024 // Case 1 is covered too, because the first equation reduces to: 1025 // prob(BB->Succ) > HotProb. (freq(Succ) = freq(BB) for a triangle) 1026 BlockFrequency PredEdgeFreq = 1027 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ); 1028 if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) { 1029 BadCFGConflict = true; 1030 break; 1031 } 1032 } 1033 1034 if (BadCFGConflict) { 1035 DEBUG(dbgs() << " Not a candidate: " << getBlockName(Succ) << " -> " << SuccProb 1036 << " (prob) (non-cold CFG conflict)\n"); 1037 return true; 1038 } 1039 1040 return false; 1041 } 1042 1043 /// \brief Select the best successor for a block. 1044 /// 1045 /// This looks across all successors of a particular block and attempts to 1046 /// select the "best" one to be the layout successor. It only considers direct 1047 /// successors which also pass the block filter. It will attempt to avoid 1048 /// breaking CFG structure, but cave and break such structures in the case of 1049 /// very hot successor edges. 1050 /// 1051 /// \returns The best successor block found, or null if none are viable, along 1052 /// with a boolean indicating if tail duplication is necessary. 1053 MachineBlockPlacement::BlockAndTailDupResult 1054 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, 1055 BlockChain &Chain, 1056 const BlockFilterSet *BlockFilter) { 1057 const BranchProbability HotProb(StaticLikelyProb, 100); 1058 1059 BlockAndTailDupResult BestSucc = { nullptr, false }; 1060 auto BestProb = BranchProbability::getZero(); 1061 1062 SmallVector<MachineBasicBlock *, 4> Successors; 1063 auto AdjustedSumProb = 1064 collectViableSuccessors(BB, Chain, BlockFilter, Successors); 1065 1066 DEBUG(dbgs() << "Selecting best successor for: " << getBlockName(BB) << "\n"); 1067 1068 // For blocks with CFG violations, we may be able to lay them out anyway with 1069 // tail-duplication. We keep this vector so we can perform the probability 1070 // calculations the minimum number of times. 1071 SmallVector<std::tuple<BranchProbability, MachineBasicBlock *>, 4> 1072 DupCandidates; 1073 for (MachineBasicBlock *Succ : Successors) { 1074 auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ); 1075 BranchProbability SuccProb = 1076 getAdjustedProbability(RealSuccProb, AdjustedSumProb); 1077 1078 // This heuristic is off by default. 1079 if (shouldPredBlockBeOutlined(BB, Succ, Chain, BlockFilter, SuccProb, 1080 HotProb)) { 1081 BestSucc.BB = Succ; 1082 return BestSucc; 1083 } 1084 1085 BlockChain &SuccChain = *BlockToChain[Succ]; 1086 // Skip the edge \c BB->Succ if block \c Succ has a better layout 1087 // predecessor that yields lower global cost. 1088 if (hasBetterLayoutPredecessor(BB, Succ, SuccChain, SuccProb, RealSuccProb, 1089 Chain, BlockFilter)) { 1090 // If tail duplication would make Succ profitable, place it. 1091 if (TailDupPlacement && shouldTailDuplicate(Succ)) 1092 DupCandidates.push_back(std::make_tuple(SuccProb, Succ)); 1093 continue; 1094 } 1095 1096 DEBUG( 1097 dbgs() << " Candidate: " << getBlockName(Succ) << ", probability: " 1098 << SuccProb 1099 << (SuccChain.UnscheduledPredecessors != 0 ? " (CFG break)" : "") 1100 << "\n"); 1101 1102 if (BestSucc.BB && BestProb >= SuccProb) { 1103 DEBUG(dbgs() << " Not the best candidate, continuing\n"); 1104 continue; 1105 } 1106 1107 DEBUG(dbgs() << " Setting it as best candidate\n"); 1108 BestSucc.BB = Succ; 1109 BestProb = SuccProb; 1110 } 1111 // Handle the tail duplication candidates in order of decreasing probability. 1112 // Stop at the first one that is profitable. Also stop if they are less 1113 // profitable than BestSucc. Position is important because we preserve it and 1114 // prefer first best match. Here we aren't comparing in order, so we capture 1115 // the position instead. 1116 if (DupCandidates.size() != 0) { 1117 auto cmp = 1118 [](const std::tuple<BranchProbability, MachineBasicBlock *> &a, 1119 const std::tuple<BranchProbability, MachineBasicBlock *> &b) { 1120 return std::get<0>(a) > std::get<0>(b); 1121 }; 1122 std::stable_sort(DupCandidates.begin(), DupCandidates.end(), cmp); 1123 } 1124 for(auto &Tup : DupCandidates) { 1125 BranchProbability DupProb; 1126 MachineBasicBlock *Succ; 1127 std::tie(DupProb, Succ) = Tup; 1128 if (DupProb < BestProb) 1129 break; 1130 if (canTailDuplicateUnplacedPreds(BB, Succ, Chain, BlockFilter) 1131 // If tail duplication gives us fallthrough when we otherwise wouldn't 1132 // have it, that is a strict gain. 1133 && (BestSucc.BB == nullptr 1134 || isProfitableToTailDup(BB, Succ, BestProb, Chain, 1135 BlockFilter))) { 1136 DEBUG( 1137 dbgs() << " Candidate: " << getBlockName(Succ) << ", probability: " 1138 << DupProb 1139 << " (Tail Duplicate)\n"); 1140 BestSucc.BB = Succ; 1141 BestSucc.ShouldTailDup = true; 1142 break; 1143 } 1144 } 1145 1146 if (BestSucc.BB) 1147 DEBUG(dbgs() << " Selected: " << getBlockName(BestSucc.BB) << "\n"); 1148 1149 return BestSucc; 1150 } 1151 1152 /// \brief Select the best block from a worklist. 1153 /// 1154 /// This looks through the provided worklist as a list of candidate basic 1155 /// blocks and select the most profitable one to place. The definition of 1156 /// profitable only really makes sense in the context of a loop. This returns 1157 /// the most frequently visited block in the worklist, which in the case of 1158 /// a loop, is the one most desirable to be physically close to the rest of the 1159 /// loop body in order to improve i-cache behavior. 1160 /// 1161 /// \returns The best block found, or null if none are viable. 1162 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( 1163 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList) { 1164 // Once we need to walk the worklist looking for a candidate, cleanup the 1165 // worklist of already placed entries. 1166 // FIXME: If this shows up on profiles, it could be folded (at the cost of 1167 // some code complexity) into the loop below. 1168 WorkList.erase(remove_if(WorkList, 1169 [&](MachineBasicBlock *BB) { 1170 return BlockToChain.lookup(BB) == &Chain; 1171 }), 1172 WorkList.end()); 1173 1174 if (WorkList.empty()) 1175 return nullptr; 1176 1177 bool IsEHPad = WorkList[0]->isEHPad(); 1178 1179 MachineBasicBlock *BestBlock = nullptr; 1180 BlockFrequency BestFreq; 1181 for (MachineBasicBlock *MBB : WorkList) { 1182 assert(MBB->isEHPad() == IsEHPad); 1183 1184 BlockChain &SuccChain = *BlockToChain[MBB]; 1185 if (&SuccChain == &Chain) 1186 continue; 1187 1188 assert(SuccChain.UnscheduledPredecessors == 0 && "Found CFG-violating block"); 1189 1190 BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB); 1191 DEBUG(dbgs() << " " << getBlockName(MBB) << " -> "; 1192 MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n"); 1193 1194 // For ehpad, we layout the least probable first as to avoid jumping back 1195 // from least probable landingpads to more probable ones. 1196 // 1197 // FIXME: Using probability is probably (!) not the best way to achieve 1198 // this. We should probably have a more principled approach to layout 1199 // cleanup code. 1200 // 1201 // The goal is to get: 1202 // 1203 // +--------------------------+ 1204 // | V 1205 // InnerLp -> InnerCleanup OuterLp -> OuterCleanup -> Resume 1206 // 1207 // Rather than: 1208 // 1209 // +-------------------------------------+ 1210 // V | 1211 // OuterLp -> OuterCleanup -> Resume InnerLp -> InnerCleanup 1212 if (BestBlock && (IsEHPad ^ (BestFreq >= CandidateFreq))) 1213 continue; 1214 1215 BestBlock = MBB; 1216 BestFreq = CandidateFreq; 1217 } 1218 1219 return BestBlock; 1220 } 1221 1222 /// \brief Retrieve the first unplaced basic block. 1223 /// 1224 /// This routine is called when we are unable to use the CFG to walk through 1225 /// all of the basic blocks and form a chain due to unnatural loops in the CFG. 1226 /// We walk through the function's blocks in order, starting from the 1227 /// LastUnplacedBlockIt. We update this iterator on each call to avoid 1228 /// re-scanning the entire sequence on repeated calls to this routine. 1229 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( 1230 const BlockChain &PlacedChain, 1231 MachineFunction::iterator &PrevUnplacedBlockIt, 1232 const BlockFilterSet *BlockFilter) { 1233 for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F->end(); I != E; 1234 ++I) { 1235 if (BlockFilter && !BlockFilter->count(&*I)) 1236 continue; 1237 if (BlockToChain[&*I] != &PlacedChain) { 1238 PrevUnplacedBlockIt = I; 1239 // Now select the head of the chain to which the unplaced block belongs 1240 // as the block to place. This will force the entire chain to be placed, 1241 // and satisfies the requirements of merging chains. 1242 return *BlockToChain[&*I]->begin(); 1243 } 1244 } 1245 return nullptr; 1246 } 1247 1248 void MachineBlockPlacement::fillWorkLists( 1249 MachineBasicBlock *MBB, 1250 SmallPtrSetImpl<BlockChain *> &UpdatedPreds, 1251 const BlockFilterSet *BlockFilter = nullptr) { 1252 BlockChain &Chain = *BlockToChain[MBB]; 1253 if (!UpdatedPreds.insert(&Chain).second) 1254 return; 1255 1256 assert(Chain.UnscheduledPredecessors == 0); 1257 for (MachineBasicBlock *ChainBB : Chain) { 1258 assert(BlockToChain[ChainBB] == &Chain); 1259 for (MachineBasicBlock *Pred : ChainBB->predecessors()) { 1260 if (BlockFilter && !BlockFilter->count(Pred)) 1261 continue; 1262 if (BlockToChain[Pred] == &Chain) 1263 continue; 1264 ++Chain.UnscheduledPredecessors; 1265 } 1266 } 1267 1268 if (Chain.UnscheduledPredecessors != 0) 1269 return; 1270 1271 MBB = *Chain.begin(); 1272 if (MBB->isEHPad()) 1273 EHPadWorkList.push_back(MBB); 1274 else 1275 BlockWorkList.push_back(MBB); 1276 } 1277 1278 void MachineBlockPlacement::buildChain( 1279 MachineBasicBlock *BB, BlockChain &Chain, 1280 BlockFilterSet *BlockFilter) { 1281 assert(BB && "BB must not be null.\n"); 1282 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match.\n"); 1283 MachineFunction::iterator PrevUnplacedBlockIt = F->begin(); 1284 1285 MachineBasicBlock *LoopHeaderBB = BB; 1286 markChainSuccessors(Chain, LoopHeaderBB, BlockFilter); 1287 BB = *std::prev(Chain.end()); 1288 for (;;) { 1289 assert(BB && "null block found at end of chain in loop."); 1290 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop."); 1291 assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain."); 1292 1293 1294 // Look for the best viable successor if there is one to place immediately 1295 // after this block. 1296 auto Result = selectBestSuccessor(BB, Chain, BlockFilter); 1297 MachineBasicBlock* BestSucc = Result.BB; 1298 bool ShouldTailDup = Result.ShouldTailDup; 1299 if (TailDupPlacement) 1300 ShouldTailDup |= (BestSucc && shouldTailDuplicate(BestSucc)); 1301 1302 // If an immediate successor isn't available, look for the best viable 1303 // block among those we've identified as not violating the loop's CFG at 1304 // this point. This won't be a fallthrough, but it will increase locality. 1305 if (!BestSucc) 1306 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList); 1307 if (!BestSucc) 1308 BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList); 1309 1310 if (!BestSucc) { 1311 BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt, BlockFilter); 1312 if (!BestSucc) 1313 break; 1314 1315 DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " 1316 "layout successor until the CFG reduces\n"); 1317 } 1318 1319 // Placement may have changed tail duplication opportunities. 1320 // Check for that now. 1321 if (TailDupPlacement && BestSucc && ShouldTailDup) { 1322 // If the chosen successor was duplicated into all its predecessors, 1323 // don't bother laying it out, just go round the loop again with BB as 1324 // the chain end. 1325 if (repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain, 1326 BlockFilter, PrevUnplacedBlockIt)) 1327 continue; 1328 } 1329 1330 // Place this block, updating the datastructures to reflect its placement. 1331 BlockChain &SuccChain = *BlockToChain[BestSucc]; 1332 // Zero out UnscheduledPredecessors for the successor we're about to merge in case 1333 // we selected a successor that didn't fit naturally into the CFG. 1334 SuccChain.UnscheduledPredecessors = 0; 1335 DEBUG(dbgs() << "Merging from " << getBlockName(BB) << " to " 1336 << getBlockName(BestSucc) << "\n"); 1337 markChainSuccessors(SuccChain, LoopHeaderBB, BlockFilter); 1338 Chain.merge(BestSucc, &SuccChain); 1339 BB = *std::prev(Chain.end()); 1340 } 1341 1342 DEBUG(dbgs() << "Finished forming chain for header block " 1343 << getBlockName(*Chain.begin()) << "\n"); 1344 } 1345 1346 /// \brief Find the best loop top block for layout. 1347 /// 1348 /// Look for a block which is strictly better than the loop header for laying 1349 /// out at the top of the loop. This looks for one and only one pattern: 1350 /// a latch block with no conditional exit. This block will cause a conditional 1351 /// jump around it or will be the bottom of the loop if we lay it out in place, 1352 /// but if it it doesn't end up at the bottom of the loop for any reason, 1353 /// rotation alone won't fix it. Because such a block will always result in an 1354 /// unconditional jump (for the backedge) rotating it in front of the loop 1355 /// header is always profitable. 1356 MachineBasicBlock * 1357 MachineBlockPlacement::findBestLoopTop(MachineLoop &L, 1358 const BlockFilterSet &LoopBlockSet) { 1359 // Placing the latch block before the header may introduce an extra branch 1360 // that skips this block the first time the loop is executed, which we want 1361 // to avoid when optimising for size. 1362 // FIXME: in theory there is a case that does not introduce a new branch, 1363 // i.e. when the layout predecessor does not fallthrough to the loop header. 1364 // In practice this never happens though: there always seems to be a preheader 1365 // that can fallthrough and that is also placed before the header. 1366 if (F->getFunction()->optForSize()) 1367 return L.getHeader(); 1368 1369 // Check that the header hasn't been fused with a preheader block due to 1370 // crazy branches. If it has, we need to start with the header at the top to 1371 // prevent pulling the preheader into the loop body. 1372 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 1373 if (!LoopBlockSet.count(*HeaderChain.begin())) 1374 return L.getHeader(); 1375 1376 DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader()) 1377 << "\n"); 1378 1379 BlockFrequency BestPredFreq; 1380 MachineBasicBlock *BestPred = nullptr; 1381 for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) { 1382 if (!LoopBlockSet.count(Pred)) 1383 continue; 1384 DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", has " 1385 << Pred->succ_size() << " successors, "; 1386 MBFI->printBlockFreq(dbgs(), Pred) << " freq\n"); 1387 if (Pred->succ_size() > 1) 1388 continue; 1389 1390 BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); 1391 if (!BestPred || PredFreq > BestPredFreq || 1392 (!(PredFreq < BestPredFreq) && 1393 Pred->isLayoutSuccessor(L.getHeader()))) { 1394 BestPred = Pred; 1395 BestPredFreq = PredFreq; 1396 } 1397 } 1398 1399 // If no direct predecessor is fine, just use the loop header. 1400 if (!BestPred) { 1401 DEBUG(dbgs() << " final top unchanged\n"); 1402 return L.getHeader(); 1403 } 1404 1405 // Walk backwards through any straight line of predecessors. 1406 while (BestPred->pred_size() == 1 && 1407 (*BestPred->pred_begin())->succ_size() == 1 && 1408 *BestPred->pred_begin() != L.getHeader()) 1409 BestPred = *BestPred->pred_begin(); 1410 1411 DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); 1412 return BestPred; 1413 } 1414 1415 /// \brief Find the best loop exiting block for layout. 1416 /// 1417 /// This routine implements the logic to analyze the loop looking for the best 1418 /// block to layout at the top of the loop. Typically this is done to maximize 1419 /// fallthrough opportunities. 1420 MachineBasicBlock * 1421 MachineBlockPlacement::findBestLoopExit(MachineLoop &L, 1422 const BlockFilterSet &LoopBlockSet) { 1423 // We don't want to layout the loop linearly in all cases. If the loop header 1424 // is just a normal basic block in the loop, we want to look for what block 1425 // within the loop is the best one to layout at the top. However, if the loop 1426 // header has be pre-merged into a chain due to predecessors not having 1427 // analyzable branches, *and* the predecessor it is merged with is *not* part 1428 // of the loop, rotating the header into the middle of the loop will create 1429 // a non-contiguous range of blocks which is Very Bad. So start with the 1430 // header and only rotate if safe. 1431 BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 1432 if (!LoopBlockSet.count(*HeaderChain.begin())) 1433 return nullptr; 1434 1435 BlockFrequency BestExitEdgeFreq; 1436 unsigned BestExitLoopDepth = 0; 1437 MachineBasicBlock *ExitingBB = nullptr; 1438 // If there are exits to outer loops, loop rotation can severely limit 1439 // fallthrough opportunities unless it selects such an exit. Keep a set of 1440 // blocks where rotating to exit with that block will reach an outer loop. 1441 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; 1442 1443 DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader()) 1444 << "\n"); 1445 for (MachineBasicBlock *MBB : L.getBlocks()) { 1446 BlockChain &Chain = *BlockToChain[MBB]; 1447 // Ensure that this block is at the end of a chain; otherwise it could be 1448 // mid-way through an inner loop or a successor of an unanalyzable branch. 1449 if (MBB != *std::prev(Chain.end())) 1450 continue; 1451 1452 // Now walk the successors. We need to establish whether this has a viable 1453 // exiting successor and whether it has a viable non-exiting successor. 1454 // We store the old exiting state and restore it if a viable looping 1455 // successor isn't found. 1456 MachineBasicBlock *OldExitingBB = ExitingBB; 1457 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; 1458 bool HasLoopingSucc = false; 1459 for (MachineBasicBlock *Succ : MBB->successors()) { 1460 if (Succ->isEHPad()) 1461 continue; 1462 if (Succ == MBB) 1463 continue; 1464 BlockChain &SuccChain = *BlockToChain[Succ]; 1465 // Don't split chains, either this chain or the successor's chain. 1466 if (&Chain == &SuccChain) { 1467 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " 1468 << getBlockName(Succ) << " (chain conflict)\n"); 1469 continue; 1470 } 1471 1472 auto SuccProb = MBPI->getEdgeProbability(MBB, Succ); 1473 if (LoopBlockSet.count(Succ)) { 1474 DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> " 1475 << getBlockName(Succ) << " (" << SuccProb << ")\n"); 1476 HasLoopingSucc = true; 1477 continue; 1478 } 1479 1480 unsigned SuccLoopDepth = 0; 1481 if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) { 1482 SuccLoopDepth = ExitLoop->getLoopDepth(); 1483 if (ExitLoop->contains(&L)) 1484 BlocksExitingToOuterLoop.insert(MBB); 1485 } 1486 1487 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb; 1488 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> " 1489 << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] ("; 1490 MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n"); 1491 // Note that we bias this toward an existing layout successor to retain 1492 // incoming order in the absence of better information. The exit must have 1493 // a frequency higher than the current exit before we consider breaking 1494 // the layout. 1495 BranchProbability Bias(100 - ExitBlockBias, 100); 1496 if (!ExitingBB || SuccLoopDepth > BestExitLoopDepth || 1497 ExitEdgeFreq > BestExitEdgeFreq || 1498 (MBB->isLayoutSuccessor(Succ) && 1499 !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) { 1500 BestExitEdgeFreq = ExitEdgeFreq; 1501 ExitingBB = MBB; 1502 } 1503 } 1504 1505 if (!HasLoopingSucc) { 1506 // Restore the old exiting state, no viable looping successor was found. 1507 ExitingBB = OldExitingBB; 1508 BestExitEdgeFreq = OldBestExitEdgeFreq; 1509 } 1510 } 1511 // Without a candidate exiting block or with only a single block in the 1512 // loop, just use the loop header to layout the loop. 1513 if (!ExitingBB) { 1514 DEBUG(dbgs() << " No other candidate exit blocks, using loop header\n"); 1515 return nullptr; 1516 } 1517 if (L.getNumBlocks() == 1) { 1518 DEBUG(dbgs() << " Loop has 1 block, using loop header as exit\n"); 1519 return nullptr; 1520 } 1521 1522 // Also, if we have exit blocks which lead to outer loops but didn't select 1523 // one of them as the exiting block we are rotating toward, disable loop 1524 // rotation altogether. 1525 if (!BlocksExitingToOuterLoop.empty() && 1526 !BlocksExitingToOuterLoop.count(ExitingBB)) 1527 return nullptr; 1528 1529 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 1530 return ExitingBB; 1531 } 1532 1533 /// \brief Attempt to rotate an exiting block to the bottom of the loop. 1534 /// 1535 /// Once we have built a chain, try to rotate it to line up the hot exit block 1536 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary 1537 /// branches. For example, if the loop has fallthrough into its header and out 1538 /// of its bottom already, don't rotate it. 1539 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, 1540 MachineBasicBlock *ExitingBB, 1541 const BlockFilterSet &LoopBlockSet) { 1542 if (!ExitingBB) 1543 return; 1544 1545 MachineBasicBlock *Top = *LoopChain.begin(); 1546 bool ViableTopFallthrough = false; 1547 for (MachineBasicBlock *Pred : Top->predecessors()) { 1548 BlockChain *PredChain = BlockToChain[Pred]; 1549 if (!LoopBlockSet.count(Pred) && 1550 (!PredChain || Pred == *std::prev(PredChain->end()))) { 1551 ViableTopFallthrough = true; 1552 break; 1553 } 1554 } 1555 1556 // If the header has viable fallthrough, check whether the current loop 1557 // bottom is a viable exiting block. If so, bail out as rotating will 1558 // introduce an unnecessary branch. 1559 if (ViableTopFallthrough) { 1560 MachineBasicBlock *Bottom = *std::prev(LoopChain.end()); 1561 for (MachineBasicBlock *Succ : Bottom->successors()) { 1562 BlockChain *SuccChain = BlockToChain[Succ]; 1563 if (!LoopBlockSet.count(Succ) && 1564 (!SuccChain || Succ == *SuccChain->begin())) 1565 return; 1566 } 1567 } 1568 1569 BlockChain::iterator ExitIt = find(LoopChain, ExitingBB); 1570 if (ExitIt == LoopChain.end()) 1571 return; 1572 1573 std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end()); 1574 } 1575 1576 /// \brief Attempt to rotate a loop based on profile data to reduce branch cost. 1577 /// 1578 /// With profile data, we can determine the cost in terms of missed fall through 1579 /// opportunities when rotating a loop chain and select the best rotation. 1580 /// Basically, there are three kinds of cost to consider for each rotation: 1581 /// 1. The possibly missed fall through edge (if it exists) from BB out of 1582 /// the loop to the loop header. 1583 /// 2. The possibly missed fall through edges (if they exist) from the loop 1584 /// exits to BB out of the loop. 1585 /// 3. The missed fall through edge (if it exists) from the last BB to the 1586 /// first BB in the loop chain. 1587 /// Therefore, the cost for a given rotation is the sum of costs listed above. 1588 /// We select the best rotation with the smallest cost. 1589 void MachineBlockPlacement::rotateLoopWithProfile( 1590 BlockChain &LoopChain, MachineLoop &L, const BlockFilterSet &LoopBlockSet) { 1591 auto HeaderBB = L.getHeader(); 1592 auto HeaderIter = find(LoopChain, HeaderBB); 1593 auto RotationPos = LoopChain.end(); 1594 1595 BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency(); 1596 1597 // A utility lambda that scales up a block frequency by dividing it by a 1598 // branch probability which is the reciprocal of the scale. 1599 auto ScaleBlockFrequency = [](BlockFrequency Freq, 1600 unsigned Scale) -> BlockFrequency { 1601 if (Scale == 0) 1602 return 0; 1603 // Use operator / between BlockFrequency and BranchProbability to implement 1604 // saturating multiplication. 1605 return Freq / BranchProbability(1, Scale); 1606 }; 1607 1608 // Compute the cost of the missed fall-through edge to the loop header if the 1609 // chain head is not the loop header. As we only consider natural loops with 1610 // single header, this computation can be done only once. 1611 BlockFrequency HeaderFallThroughCost(0); 1612 for (auto *Pred : HeaderBB->predecessors()) { 1613 BlockChain *PredChain = BlockToChain[Pred]; 1614 if (!LoopBlockSet.count(Pred) && 1615 (!PredChain || Pred == *std::prev(PredChain->end()))) { 1616 auto EdgeFreq = 1617 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, HeaderBB); 1618 auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost); 1619 // If the predecessor has only an unconditional jump to the header, we 1620 // need to consider the cost of this jump. 1621 if (Pred->succ_size() == 1) 1622 FallThruCost += ScaleBlockFrequency(EdgeFreq, JumpInstCost); 1623 HeaderFallThroughCost = std::max(HeaderFallThroughCost, FallThruCost); 1624 } 1625 } 1626 1627 // Here we collect all exit blocks in the loop, and for each exit we find out 1628 // its hottest exit edge. For each loop rotation, we define the loop exit cost 1629 // as the sum of frequencies of exit edges we collect here, excluding the exit 1630 // edge from the tail of the loop chain. 1631 SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq; 1632 for (auto BB : LoopChain) { 1633 auto LargestExitEdgeProb = BranchProbability::getZero(); 1634 for (auto *Succ : BB->successors()) { 1635 BlockChain *SuccChain = BlockToChain[Succ]; 1636 if (!LoopBlockSet.count(Succ) && 1637 (!SuccChain || Succ == *SuccChain->begin())) { 1638 auto SuccProb = MBPI->getEdgeProbability(BB, Succ); 1639 LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb); 1640 } 1641 } 1642 if (LargestExitEdgeProb > BranchProbability::getZero()) { 1643 auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb; 1644 ExitsWithFreq.emplace_back(BB, ExitFreq); 1645 } 1646 } 1647 1648 // In this loop we iterate every block in the loop chain and calculate the 1649 // cost assuming the block is the head of the loop chain. When the loop ends, 1650 // we should have found the best candidate as the loop chain's head. 1651 for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()), 1652 EndIter = LoopChain.end(); 1653 Iter != EndIter; Iter++, TailIter++) { 1654 // TailIter is used to track the tail of the loop chain if the block we are 1655 // checking (pointed by Iter) is the head of the chain. 1656 if (TailIter == LoopChain.end()) 1657 TailIter = LoopChain.begin(); 1658 1659 auto TailBB = *TailIter; 1660 1661 // Calculate the cost by putting this BB to the top. 1662 BlockFrequency Cost = 0; 1663 1664 // If the current BB is the loop header, we need to take into account the 1665 // cost of the missed fall through edge from outside of the loop to the 1666 // header. 1667 if (Iter != HeaderIter) 1668 Cost += HeaderFallThroughCost; 1669 1670 // Collect the loop exit cost by summing up frequencies of all exit edges 1671 // except the one from the chain tail. 1672 for (auto &ExitWithFreq : ExitsWithFreq) 1673 if (TailBB != ExitWithFreq.first) 1674 Cost += ExitWithFreq.second; 1675 1676 // The cost of breaking the once fall-through edge from the tail to the top 1677 // of the loop chain. Here we need to consider three cases: 1678 // 1. If the tail node has only one successor, then we will get an 1679 // additional jmp instruction. So the cost here is (MisfetchCost + 1680 // JumpInstCost) * tail node frequency. 1681 // 2. If the tail node has two successors, then we may still get an 1682 // additional jmp instruction if the layout successor after the loop 1683 // chain is not its CFG successor. Note that the more frequently executed 1684 // jmp instruction will be put ahead of the other one. Assume the 1685 // frequency of those two branches are x and y, where x is the frequency 1686 // of the edge to the chain head, then the cost will be 1687 // (x * MisfetechCost + min(x, y) * JumpInstCost) * tail node frequency. 1688 // 3. If the tail node has more than two successors (this rarely happens), 1689 // we won't consider any additional cost. 1690 if (TailBB->isSuccessor(*Iter)) { 1691 auto TailBBFreq = MBFI->getBlockFreq(TailBB); 1692 if (TailBB->succ_size() == 1) 1693 Cost += ScaleBlockFrequency(TailBBFreq.getFrequency(), 1694 MisfetchCost + JumpInstCost); 1695 else if (TailBB->succ_size() == 2) { 1696 auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter); 1697 auto TailToHeadFreq = TailBBFreq * TailToHeadProb; 1698 auto ColderEdgeFreq = TailToHeadProb > BranchProbability(1, 2) 1699 ? TailBBFreq * TailToHeadProb.getCompl() 1700 : TailToHeadFreq; 1701 Cost += ScaleBlockFrequency(TailToHeadFreq, MisfetchCost) + 1702 ScaleBlockFrequency(ColderEdgeFreq, JumpInstCost); 1703 } 1704 } 1705 1706 DEBUG(dbgs() << "The cost of loop rotation by making " << getBlockName(*Iter) 1707 << " to the top: " << Cost.getFrequency() << "\n"); 1708 1709 if (Cost < SmallestRotationCost) { 1710 SmallestRotationCost = Cost; 1711 RotationPos = Iter; 1712 } 1713 } 1714 1715 if (RotationPos != LoopChain.end()) { 1716 DEBUG(dbgs() << "Rotate loop by making " << getBlockName(*RotationPos) 1717 << " to the top\n"); 1718 std::rotate(LoopChain.begin(), RotationPos, LoopChain.end()); 1719 } 1720 } 1721 1722 /// \brief Collect blocks in the given loop that are to be placed. 1723 /// 1724 /// When profile data is available, exclude cold blocks from the returned set; 1725 /// otherwise, collect all blocks in the loop. 1726 MachineBlockPlacement::BlockFilterSet 1727 MachineBlockPlacement::collectLoopBlockSet(MachineLoop &L) { 1728 BlockFilterSet LoopBlockSet; 1729 1730 // Filter cold blocks off from LoopBlockSet when profile data is available. 1731 // Collect the sum of frequencies of incoming edges to the loop header from 1732 // outside. If we treat the loop as a super block, this is the frequency of 1733 // the loop. Then for each block in the loop, we calculate the ratio between 1734 // its frequency and the frequency of the loop block. When it is too small, 1735 // don't add it to the loop chain. If there are outer loops, then this block 1736 // will be merged into the first outer loop chain for which this block is not 1737 // cold anymore. This needs precise profile data and we only do this when 1738 // profile data is available. 1739 if (F->getFunction()->getEntryCount()) { 1740 BlockFrequency LoopFreq(0); 1741 for (auto LoopPred : L.getHeader()->predecessors()) 1742 if (!L.contains(LoopPred)) 1743 LoopFreq += MBFI->getBlockFreq(LoopPred) * 1744 MBPI->getEdgeProbability(LoopPred, L.getHeader()); 1745 1746 for (MachineBasicBlock *LoopBB : L.getBlocks()) { 1747 auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency(); 1748 if (Freq == 0 || LoopFreq.getFrequency() / Freq > LoopToColdBlockRatio) 1749 continue; 1750 LoopBlockSet.insert(LoopBB); 1751 } 1752 } else 1753 LoopBlockSet.insert(L.block_begin(), L.block_end()); 1754 1755 return LoopBlockSet; 1756 } 1757 1758 /// \brief Forms basic block chains from the natural loop structures. 1759 /// 1760 /// These chains are designed to preserve the existing *structure* of the code 1761 /// as much as possible. We can then stitch the chains together in a way which 1762 /// both preserves the topological structure and minimizes taken conditional 1763 /// branches. 1764 void MachineBlockPlacement::buildLoopChains(MachineLoop &L) { 1765 // First recurse through any nested loops, building chains for those inner 1766 // loops. 1767 for (MachineLoop *InnerLoop : L) 1768 buildLoopChains(*InnerLoop); 1769 1770 assert(BlockWorkList.empty()); 1771 assert(EHPadWorkList.empty()); 1772 BlockFilterSet LoopBlockSet = collectLoopBlockSet(L); 1773 1774 // Check if we have profile data for this function. If yes, we will rotate 1775 // this loop by modeling costs more precisely which requires the profile data 1776 // for better layout. 1777 bool RotateLoopWithProfile = 1778 ForcePreciseRotationCost || 1779 (PreciseRotationCost && F->getFunction()->getEntryCount()); 1780 1781 // First check to see if there is an obviously preferable top block for the 1782 // loop. This will default to the header, but may end up as one of the 1783 // predecessors to the header if there is one which will result in strictly 1784 // fewer branches in the loop body. 1785 // When we use profile data to rotate the loop, this is unnecessary. 1786 MachineBasicBlock *LoopTop = 1787 RotateLoopWithProfile ? L.getHeader() : findBestLoopTop(L, LoopBlockSet); 1788 1789 // If we selected just the header for the loop top, look for a potentially 1790 // profitable exit block in the event that rotating the loop can eliminate 1791 // branches by placing an exit edge at the bottom. 1792 if (!RotateLoopWithProfile && LoopTop == L.getHeader()) 1793 PreferredLoopExit = findBestLoopExit(L, LoopBlockSet); 1794 1795 BlockChain &LoopChain = *BlockToChain[LoopTop]; 1796 1797 // FIXME: This is a really lame way of walking the chains in the loop: we 1798 // walk the blocks, and use a set to prevent visiting a particular chain 1799 // twice. 1800 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 1801 assert(LoopChain.UnscheduledPredecessors == 0); 1802 UpdatedPreds.insert(&LoopChain); 1803 1804 for (MachineBasicBlock *LoopBB : LoopBlockSet) 1805 fillWorkLists(LoopBB, UpdatedPreds, &LoopBlockSet); 1806 1807 buildChain(LoopTop, LoopChain, &LoopBlockSet); 1808 1809 if (RotateLoopWithProfile) 1810 rotateLoopWithProfile(LoopChain, L, LoopBlockSet); 1811 else 1812 rotateLoop(LoopChain, PreferredLoopExit, LoopBlockSet); 1813 1814 DEBUG({ 1815 // Crash at the end so we get all of the debugging output first. 1816 bool BadLoop = false; 1817 if (LoopChain.UnscheduledPredecessors) { 1818 BadLoop = true; 1819 dbgs() << "Loop chain contains a block without its preds placed!\n" 1820 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 1821 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 1822 } 1823 for (MachineBasicBlock *ChainBB : LoopChain) { 1824 dbgs() << " ... " << getBlockName(ChainBB) << "\n"; 1825 if (!LoopBlockSet.remove(ChainBB)) { 1826 // We don't mark the loop as bad here because there are real situations 1827 // where this can occur. For example, with an unanalyzable fallthrough 1828 // from a loop block to a non-loop block or vice versa. 1829 dbgs() << "Loop chain contains a block not contained by the loop!\n" 1830 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 1831 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 1832 << " Bad block: " << getBlockName(ChainBB) << "\n"; 1833 } 1834 } 1835 1836 if (!LoopBlockSet.empty()) { 1837 BadLoop = true; 1838 for (MachineBasicBlock *LoopBB : LoopBlockSet) 1839 dbgs() << "Loop contains blocks never placed into a chain!\n" 1840 << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 1841 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 1842 << " Bad block: " << getBlockName(LoopBB) << "\n"; 1843 } 1844 assert(!BadLoop && "Detected problems with the placement of this loop."); 1845 }); 1846 1847 BlockWorkList.clear(); 1848 EHPadWorkList.clear(); 1849 } 1850 1851 /// When OutlineOpitonalBranches is on, this method collects BBs that 1852 /// dominates all terminator blocks of the function \p F. 1853 void MachineBlockPlacement::collectMustExecuteBBs() { 1854 if (OutlineOptionalBranches) { 1855 // Find the nearest common dominator of all of F's terminators. 1856 MachineBasicBlock *Terminator = nullptr; 1857 for (MachineBasicBlock &MBB : *F) { 1858 if (MBB.succ_size() == 0) { 1859 if (Terminator == nullptr) 1860 Terminator = &MBB; 1861 else 1862 Terminator = MDT->findNearestCommonDominator(Terminator, &MBB); 1863 } 1864 } 1865 1866 // MBBs dominating this common dominator are unavoidable. 1867 UnavoidableBlocks.clear(); 1868 for (MachineBasicBlock &MBB : *F) { 1869 if (MDT->dominates(&MBB, Terminator)) { 1870 UnavoidableBlocks.insert(&MBB); 1871 } 1872 } 1873 } 1874 } 1875 1876 void MachineBlockPlacement::buildCFGChains() { 1877 // Ensure that every BB in the function has an associated chain to simplify 1878 // the assumptions of the remaining algorithm. 1879 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 1880 for (MachineFunction::iterator FI = F->begin(), FE = F->end(); FI != FE; 1881 ++FI) { 1882 MachineBasicBlock *BB = &*FI; 1883 BlockChain *Chain = 1884 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 1885 // Also, merge any blocks which we cannot reason about and must preserve 1886 // the exact fallthrough behavior for. 1887 for (;;) { 1888 Cond.clear(); 1889 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 1890 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 1891 break; 1892 1893 MachineFunction::iterator NextFI = std::next(FI); 1894 MachineBasicBlock *NextBB = &*NextFI; 1895 // Ensure that the layout successor is a viable block, as we know that 1896 // fallthrough is a possibility. 1897 assert(NextFI != FE && "Can't fallthrough past the last block."); 1898 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 1899 << getBlockName(BB) << " -> " << getBlockName(NextBB) 1900 << "\n"); 1901 Chain->merge(NextBB, nullptr); 1902 #ifndef NDEBUG 1903 BlocksWithUnanalyzableExits.insert(&*BB); 1904 #endif 1905 FI = NextFI; 1906 BB = NextBB; 1907 } 1908 } 1909 1910 // Turned on with OutlineOptionalBranches option 1911 collectMustExecuteBBs(); 1912 1913 // Build any loop-based chains. 1914 PreferredLoopExit = nullptr; 1915 for (MachineLoop *L : *MLI) 1916 buildLoopChains(*L); 1917 1918 assert(BlockWorkList.empty()); 1919 assert(EHPadWorkList.empty()); 1920 1921 SmallPtrSet<BlockChain *, 4> UpdatedPreds; 1922 for (MachineBasicBlock &MBB : *F) 1923 fillWorkLists(&MBB, UpdatedPreds); 1924 1925 BlockChain &FunctionChain = *BlockToChain[&F->front()]; 1926 buildChain(&F->front(), FunctionChain); 1927 1928 #ifndef NDEBUG 1929 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 1930 #endif 1931 DEBUG({ 1932 // Crash at the end so we get all of the debugging output first. 1933 bool BadFunc = false; 1934 FunctionBlockSetType FunctionBlockSet; 1935 for (MachineBasicBlock &MBB : *F) 1936 FunctionBlockSet.insert(&MBB); 1937 1938 for (MachineBasicBlock *ChainBB : FunctionChain) 1939 if (!FunctionBlockSet.erase(ChainBB)) { 1940 BadFunc = true; 1941 dbgs() << "Function chain contains a block not in the function!\n" 1942 << " Bad block: " << getBlockName(ChainBB) << "\n"; 1943 } 1944 1945 if (!FunctionBlockSet.empty()) { 1946 BadFunc = true; 1947 for (MachineBasicBlock *RemainingBB : FunctionBlockSet) 1948 dbgs() << "Function contains blocks never placed into a chain!\n" 1949 << " Bad block: " << getBlockName(RemainingBB) << "\n"; 1950 } 1951 assert(!BadFunc && "Detected problems with the block placement."); 1952 }); 1953 1954 // Splice the blocks into place. 1955 MachineFunction::iterator InsertPos = F->begin(); 1956 DEBUG(dbgs() << "[MBP] Function: "<< F->getName() << "\n"); 1957 for (MachineBasicBlock *ChainBB : FunctionChain) { 1958 DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain " 1959 : " ... ") 1960 << getBlockName(ChainBB) << "\n"); 1961 if (InsertPos != MachineFunction::iterator(ChainBB)) 1962 F->splice(InsertPos, ChainBB); 1963 else 1964 ++InsertPos; 1965 1966 // Update the terminator of the previous block. 1967 if (ChainBB == *FunctionChain.begin()) 1968 continue; 1969 MachineBasicBlock *PrevBB = &*std::prev(MachineFunction::iterator(ChainBB)); 1970 1971 // FIXME: It would be awesome of updateTerminator would just return rather 1972 // than assert when the branch cannot be analyzed in order to remove this 1973 // boiler plate. 1974 Cond.clear(); 1975 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 1976 1977 #ifndef NDEBUG 1978 if (!BlocksWithUnanalyzableExits.count(PrevBB)) { 1979 // Given the exact block placement we chose, we may actually not _need_ to 1980 // be able to edit PrevBB's terminator sequence, but not being _able_ to 1981 // do that at this point is a bug. 1982 assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) || 1983 !PrevBB->canFallThrough()) && 1984 "Unexpected block with un-analyzable fallthrough!"); 1985 Cond.clear(); 1986 TBB = FBB = nullptr; 1987 } 1988 #endif 1989 1990 // The "PrevBB" is not yet updated to reflect current code layout, so, 1991 // o. it may fall-through to a block without explicit "goto" instruction 1992 // before layout, and no longer fall-through it after layout; or 1993 // o. just opposite. 1994 // 1995 // analyzeBranch() may return erroneous value for FBB when these two 1996 // situations take place. For the first scenario FBB is mistakenly set NULL; 1997 // for the 2nd scenario, the FBB, which is expected to be NULL, is 1998 // mistakenly pointing to "*BI". 1999 // Thus, if the future change needs to use FBB before the layout is set, it 2000 // has to correct FBB first by using the code similar to the following: 2001 // 2002 // if (!Cond.empty() && (!FBB || FBB == ChainBB)) { 2003 // PrevBB->updateTerminator(); 2004 // Cond.clear(); 2005 // TBB = FBB = nullptr; 2006 // if (TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) { 2007 // // FIXME: This should never take place. 2008 // TBB = FBB = nullptr; 2009 // } 2010 // } 2011 if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) 2012 PrevBB->updateTerminator(); 2013 } 2014 2015 // Fixup the last block. 2016 Cond.clear(); 2017 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 2018 if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond)) 2019 F->back().updateTerminator(); 2020 2021 BlockWorkList.clear(); 2022 EHPadWorkList.clear(); 2023 } 2024 2025 void MachineBlockPlacement::optimizeBranches() { 2026 BlockChain &FunctionChain = *BlockToChain[&F->front()]; 2027 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 2028 2029 // Now that all the basic blocks in the chain have the proper layout, 2030 // make a final call to AnalyzeBranch with AllowModify set. 2031 // Indeed, the target may be able to optimize the branches in a way we 2032 // cannot because all branches may not be analyzable. 2033 // E.g., the target may be able to remove an unconditional branch to 2034 // a fallthrough when it occurs after predicated terminators. 2035 for (MachineBasicBlock *ChainBB : FunctionChain) { 2036 Cond.clear(); 2037 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 2038 if (!TII->analyzeBranch(*ChainBB, TBB, FBB, Cond, /*AllowModify*/ true)) { 2039 // If PrevBB has a two-way branch, try to re-order the branches 2040 // such that we branch to the successor with higher probability first. 2041 if (TBB && !Cond.empty() && FBB && 2042 MBPI->getEdgeProbability(ChainBB, FBB) > 2043 MBPI->getEdgeProbability(ChainBB, TBB) && 2044 !TII->reverseBranchCondition(Cond)) { 2045 DEBUG(dbgs() << "Reverse order of the two branches: " 2046 << getBlockName(ChainBB) << "\n"); 2047 DEBUG(dbgs() << " Edge probability: " 2048 << MBPI->getEdgeProbability(ChainBB, FBB) << " vs " 2049 << MBPI->getEdgeProbability(ChainBB, TBB) << "\n"); 2050 DebugLoc dl; // FIXME: this is nowhere 2051 TII->removeBranch(*ChainBB); 2052 TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl); 2053 ChainBB->updateTerminator(); 2054 } 2055 } 2056 } 2057 } 2058 2059 void MachineBlockPlacement::alignBlocks() { 2060 // Walk through the backedges of the function now that we have fully laid out 2061 // the basic blocks and align the destination of each backedge. We don't rely 2062 // exclusively on the loop info here so that we can align backedges in 2063 // unnatural CFGs and backedges that were introduced purely because of the 2064 // loop rotations done during this layout pass. 2065 if (F->getFunction()->optForSize()) 2066 return; 2067 BlockChain &FunctionChain = *BlockToChain[&F->front()]; 2068 if (FunctionChain.begin() == FunctionChain.end()) 2069 return; // Empty chain. 2070 2071 const BranchProbability ColdProb(1, 5); // 20% 2072 BlockFrequency EntryFreq = MBFI->getBlockFreq(&F->front()); 2073 BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; 2074 for (MachineBasicBlock *ChainBB : FunctionChain) { 2075 if (ChainBB == *FunctionChain.begin()) 2076 continue; 2077 2078 // Don't align non-looping basic blocks. These are unlikely to execute 2079 // enough times to matter in practice. Note that we'll still handle 2080 // unnatural CFGs inside of a natural outer loop (the common case) and 2081 // rotated loops. 2082 MachineLoop *L = MLI->getLoopFor(ChainBB); 2083 if (!L) 2084 continue; 2085 2086 unsigned Align = TLI->getPrefLoopAlignment(L); 2087 if (!Align) 2088 continue; // Don't care about loop alignment. 2089 2090 // If the block is cold relative to the function entry don't waste space 2091 // aligning it. 2092 BlockFrequency Freq = MBFI->getBlockFreq(ChainBB); 2093 if (Freq < WeightedEntryFreq) 2094 continue; 2095 2096 // If the block is cold relative to its loop header, don't align it 2097 // regardless of what edges into the block exist. 2098 MachineBasicBlock *LoopHeader = L->getHeader(); 2099 BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); 2100 if (Freq < (LoopHeaderFreq * ColdProb)) 2101 continue; 2102 2103 // Check for the existence of a non-layout predecessor which would benefit 2104 // from aligning this block. 2105 MachineBasicBlock *LayoutPred = 2106 &*std::prev(MachineFunction::iterator(ChainBB)); 2107 2108 // Force alignment if all the predecessors are jumps. We already checked 2109 // that the block isn't cold above. 2110 if (!LayoutPred->isSuccessor(ChainBB)) { 2111 ChainBB->setAlignment(Align); 2112 continue; 2113 } 2114 2115 // Align this block if the layout predecessor's edge into this block is 2116 // cold relative to the block. When this is true, other predecessors make up 2117 // all of the hot entries into the block and thus alignment is likely to be 2118 // important. 2119 BranchProbability LayoutProb = 2120 MBPI->getEdgeProbability(LayoutPred, ChainBB); 2121 BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; 2122 if (LayoutEdgeFreq <= (Freq * ColdProb)) 2123 ChainBB->setAlignment(Align); 2124 } 2125 } 2126 2127 /// Tail duplicate \p BB into (some) predecessors if profitable, repeating if 2128 /// it was duplicated into its chain predecessor and removed. 2129 /// \p BB - Basic block that may be duplicated. 2130 /// 2131 /// \p LPred - Chosen layout predecessor of \p BB. 2132 /// Updated to be the chain end if LPred is removed. 2133 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong. 2134 /// \p BlockFilter - Set of blocks that belong to the loop being laid out. 2135 /// Used to identify which blocks to update predecessor 2136 /// counts. 2137 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was 2138 /// chosen in the given order due to unnatural CFG 2139 /// only needed if \p BB is removed and 2140 /// \p PrevUnplacedBlockIt pointed to \p BB. 2141 /// @return true if \p BB was removed. 2142 bool MachineBlockPlacement::repeatedlyTailDuplicateBlock( 2143 MachineBasicBlock *BB, MachineBasicBlock *&LPred, 2144 MachineBasicBlock *LoopHeaderBB, 2145 BlockChain &Chain, BlockFilterSet *BlockFilter, 2146 MachineFunction::iterator &PrevUnplacedBlockIt) { 2147 bool Removed, DuplicatedToLPred; 2148 bool DuplicatedToOriginalLPred; 2149 Removed = maybeTailDuplicateBlock(BB, LPred, Chain, BlockFilter, 2150 PrevUnplacedBlockIt, 2151 DuplicatedToLPred); 2152 if (!Removed) 2153 return false; 2154 DuplicatedToOriginalLPred = DuplicatedToLPred; 2155 // Iteratively try to duplicate again. It can happen that a block that is 2156 // duplicated into is still small enough to be duplicated again. 2157 // No need to call markBlockSuccessors in this case, as the blocks being 2158 // duplicated from here on are already scheduled. 2159 // Note that DuplicatedToLPred always implies Removed. 2160 while (DuplicatedToLPred) { 2161 assert (Removed && "Block must have been removed to be duplicated into its " 2162 "layout predecessor."); 2163 MachineBasicBlock *DupBB, *DupPred; 2164 // The removal callback causes Chain.end() to be updated when a block is 2165 // removed. On the first pass through the loop, the chain end should be the 2166 // same as it was on function entry. On subsequent passes, because we are 2167 // duplicating the block at the end of the chain, if it is removed the 2168 // chain will have shrunk by one block. 2169 BlockChain::iterator ChainEnd = Chain.end(); 2170 DupBB = *(--ChainEnd); 2171 // Now try to duplicate again. 2172 if (ChainEnd == Chain.begin()) 2173 break; 2174 DupPred = *std::prev(ChainEnd); 2175 Removed = maybeTailDuplicateBlock(DupBB, DupPred, Chain, BlockFilter, 2176 PrevUnplacedBlockIt, 2177 DuplicatedToLPred); 2178 } 2179 // If BB was duplicated into LPred, it is now scheduled. But because it was 2180 // removed, markChainSuccessors won't be called for its chain. Instead we 2181 // call markBlockSuccessors for LPred to achieve the same effect. This must go 2182 // at the end because repeating the tail duplication can increase the number 2183 // of unscheduled predecessors. 2184 LPred = *std::prev(Chain.end()); 2185 if (DuplicatedToOriginalLPred) 2186 markBlockSuccessors(Chain, LPred, LoopHeaderBB, BlockFilter); 2187 return true; 2188 } 2189 2190 /// Tail duplicate \p BB into (some) predecessors if profitable. 2191 /// \p BB - Basic block that may be duplicated 2192 /// \p LPred - Chosen layout predecessor of \p BB 2193 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong. 2194 /// \p BlockFilter - Set of blocks that belong to the loop being laid out. 2195 /// Used to identify which blocks to update predecessor 2196 /// counts. 2197 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was 2198 /// chosen in the given order due to unnatural CFG 2199 /// only needed if \p BB is removed and 2200 /// \p PrevUnplacedBlockIt pointed to \p BB. 2201 /// \p DuplicatedToLPred - True if the block was duplicated into LPred. Will 2202 /// only be true if the block was removed. 2203 /// \return - True if the block was duplicated into all preds and removed. 2204 bool MachineBlockPlacement::maybeTailDuplicateBlock( 2205 MachineBasicBlock *BB, MachineBasicBlock *LPred, 2206 const BlockChain &Chain, BlockFilterSet *BlockFilter, 2207 MachineFunction::iterator &PrevUnplacedBlockIt, 2208 bool &DuplicatedToLPred) { 2209 2210 DuplicatedToLPred = false; 2211 DEBUG(dbgs() << "Redoing tail duplication for Succ#" 2212 << BB->getNumber() << "\n"); 2213 2214 if (!shouldTailDuplicate(BB)) 2215 return false; 2216 // This has to be a callback because none of it can be done after 2217 // BB is deleted. 2218 bool Removed = false; 2219 auto RemovalCallback = 2220 [&](MachineBasicBlock *RemBB) { 2221 // Signal to outer function 2222 Removed = true; 2223 2224 // Conservative default. 2225 bool InWorkList = true; 2226 // Remove from the Chain and Chain Map 2227 if (BlockToChain.count(RemBB)) { 2228 BlockChain *Chain = BlockToChain[RemBB]; 2229 InWorkList = Chain->UnscheduledPredecessors == 0; 2230 Chain->remove(RemBB); 2231 BlockToChain.erase(RemBB); 2232 } 2233 2234 // Handle the unplaced block iterator 2235 if (&(*PrevUnplacedBlockIt) == RemBB) { 2236 PrevUnplacedBlockIt++; 2237 } 2238 2239 // Handle the Work Lists 2240 if (InWorkList) { 2241 SmallVectorImpl<MachineBasicBlock *> &RemoveList = BlockWorkList; 2242 if (RemBB->isEHPad()) 2243 RemoveList = EHPadWorkList; 2244 RemoveList.erase( 2245 remove_if(RemoveList, 2246 [RemBB](MachineBasicBlock *BB) {return BB == RemBB;}), 2247 RemoveList.end()); 2248 } 2249 2250 // Handle the filter set 2251 if (BlockFilter) { 2252 BlockFilter->remove(RemBB); 2253 } 2254 2255 // Remove the block from loop info. 2256 MLI->removeBlock(RemBB); 2257 if (RemBB == PreferredLoopExit) 2258 PreferredLoopExit = nullptr; 2259 2260 DEBUG(dbgs() << "TailDuplicator deleted block: " 2261 << getBlockName(RemBB) << "\n"); 2262 }; 2263 auto RemovalCallbackRef = 2264 llvm::function_ref<void(MachineBasicBlock*)>(RemovalCallback); 2265 2266 SmallVector<MachineBasicBlock *, 8> DuplicatedPreds; 2267 bool IsSimple = TailDup.isSimpleBB(BB); 2268 TailDup.tailDuplicateAndUpdate(IsSimple, BB, LPred, 2269 &DuplicatedPreds, &RemovalCallbackRef); 2270 2271 // Update UnscheduledPredecessors to reflect tail-duplication. 2272 DuplicatedToLPred = false; 2273 for (MachineBasicBlock *Pred : DuplicatedPreds) { 2274 // We're only looking for unscheduled predecessors that match the filter. 2275 BlockChain* PredChain = BlockToChain[Pred]; 2276 if (Pred == LPred) 2277 DuplicatedToLPred = true; 2278 if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred)) 2279 || PredChain == &Chain) 2280 continue; 2281 for (MachineBasicBlock *NewSucc : Pred->successors()) { 2282 if (BlockFilter && !BlockFilter->count(NewSucc)) 2283 continue; 2284 BlockChain *NewChain = BlockToChain[NewSucc]; 2285 if (NewChain != &Chain && NewChain != PredChain) 2286 NewChain->UnscheduledPredecessors++; 2287 } 2288 } 2289 return Removed; 2290 } 2291 2292 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 2293 if (skipFunction(*MF.getFunction())) 2294 return false; 2295 2296 // Check for single-block functions and skip them. 2297 if (std::next(MF.begin()) == MF.end()) 2298 return false; 2299 2300 F = &MF; 2301 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 2302 MBFI = llvm::make_unique<BranchFolder::MBFIWrapper>( 2303 getAnalysis<MachineBlockFrequencyInfo>()); 2304 MLI = &getAnalysis<MachineLoopInfo>(); 2305 TII = MF.getSubtarget().getInstrInfo(); 2306 TLI = MF.getSubtarget().getTargetLowering(); 2307 MDT = &getAnalysis<MachineDominatorTree>(); 2308 MPDT = nullptr; 2309 2310 // Initialize PreferredLoopExit to nullptr here since it may never be set if 2311 // there are no MachineLoops. 2312 PreferredLoopExit = nullptr; 2313 2314 if (TailDupPlacement) { 2315 MPDT = &getAnalysis<MachinePostDominatorTree>(); 2316 unsigned TailDupSize = TailDupPlacementThreshold; 2317 if (MF.getFunction()->optForSize()) 2318 TailDupSize = 1; 2319 TailDup.initMF(MF, MBPI, /* LayoutMode */ true, TailDupSize); 2320 } 2321 2322 assert(BlockToChain.empty()); 2323 2324 buildCFGChains(); 2325 2326 // Changing the layout can create new tail merging opportunities. 2327 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 2328 // TailMerge can create jump into if branches that make CFG irreducible for 2329 // HW that requires structured CFG. 2330 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() && 2331 PassConfig->getEnableTailMerge() && 2332 BranchFoldPlacement; 2333 // No tail merging opportunities if the block number is less than four. 2334 if (MF.size() > 3 && EnableTailMerge) { 2335 unsigned TailMergeSize = TailDupPlacementThreshold + 1; 2336 BranchFolder BF(/*EnableTailMerge=*/true, /*CommonHoist=*/false, *MBFI, 2337 *MBPI, TailMergeSize); 2338 2339 if (BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(), 2340 getAnalysisIfAvailable<MachineModuleInfo>(), MLI, 2341 /*AfterBlockPlacement=*/true)) { 2342 // Redo the layout if tail merging creates/removes/moves blocks. 2343 BlockToChain.clear(); 2344 // Must redo the dominator tree if blocks were changed. 2345 MDT->runOnMachineFunction(MF); 2346 if (MPDT) 2347 MPDT->runOnMachineFunction(MF); 2348 ChainAllocator.DestroyAll(); 2349 buildCFGChains(); 2350 } 2351 } 2352 2353 optimizeBranches(); 2354 alignBlocks(); 2355 2356 BlockToChain.clear(); 2357 ChainAllocator.DestroyAll(); 2358 2359 if (AlignAllBlock) 2360 // Align all of the blocks in the function to a specific alignment. 2361 for (MachineBasicBlock &MBB : MF) 2362 MBB.setAlignment(AlignAllBlock); 2363 else if (AlignAllNonFallThruBlocks) { 2364 // Align all of the blocks that have no fall-through predecessors to a 2365 // specific alignment. 2366 for (auto MBI = std::next(MF.begin()), MBE = MF.end(); MBI != MBE; ++MBI) { 2367 auto LayoutPred = std::prev(MBI); 2368 if (!LayoutPred->isSuccessor(&*MBI)) 2369 MBI->setAlignment(AlignAllNonFallThruBlocks); 2370 } 2371 } 2372 if (ViewBlockLayoutWithBFI != GVDT_None && 2373 (ViewBlockFreqFuncName.empty() || 2374 F->getFunction()->getName().equals(ViewBlockFreqFuncName))) { 2375 MBFI->view(false); 2376 } 2377 2378 2379 // We always return true as we have no way to track whether the final order 2380 // differs from the original order. 2381 return true; 2382 } 2383 2384 namespace { 2385 /// \brief A pass to compute block placement statistics. 2386 /// 2387 /// A separate pass to compute interesting statistics for evaluating block 2388 /// placement. This is separate from the actual placement pass so that they can 2389 /// be computed in the absence of any placement transformations or when using 2390 /// alternative placement strategies. 2391 class MachineBlockPlacementStats : public MachineFunctionPass { 2392 /// \brief A handle to the branch probability pass. 2393 const MachineBranchProbabilityInfo *MBPI; 2394 2395 /// \brief A handle to the function-wide block frequency pass. 2396 const MachineBlockFrequencyInfo *MBFI; 2397 2398 public: 2399 static char ID; // Pass identification, replacement for typeid 2400 MachineBlockPlacementStats() : MachineFunctionPass(ID) { 2401 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 2402 } 2403 2404 bool runOnMachineFunction(MachineFunction &F) override; 2405 2406 void getAnalysisUsage(AnalysisUsage &AU) const override { 2407 AU.addRequired<MachineBranchProbabilityInfo>(); 2408 AU.addRequired<MachineBlockFrequencyInfo>(); 2409 AU.setPreservesAll(); 2410 MachineFunctionPass::getAnalysisUsage(AU); 2411 } 2412 }; 2413 } 2414 2415 char MachineBlockPlacementStats::ID = 0; 2416 char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 2417 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 2418 "Basic Block Placement Stats", false, false) 2419 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 2420 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 2421 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 2422 "Basic Block Placement Stats", false, false) 2423 2424 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 2425 // Check for single-block functions and skip them. 2426 if (std::next(F.begin()) == F.end()) 2427 return false; 2428 2429 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 2430 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 2431 2432 for (MachineBasicBlock &MBB : F) { 2433 BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB); 2434 Statistic &NumBranches = 2435 (MBB.succ_size() > 1) ? NumCondBranches : NumUncondBranches; 2436 Statistic &BranchTakenFreq = 2437 (MBB.succ_size() > 1) ? CondBranchTakenFreq : UncondBranchTakenFreq; 2438 for (MachineBasicBlock *Succ : MBB.successors()) { 2439 // Skip if this successor is a fallthrough. 2440 if (MBB.isLayoutSuccessor(Succ)) 2441 continue; 2442 2443 BlockFrequency EdgeFreq = 2444 BlockFreq * MBPI->getEdgeProbability(&MBB, Succ); 2445 ++NumBranches; 2446 BranchTakenFreq += EdgeFreq.getFrequency(); 2447 } 2448 } 2449 2450 return false; 2451 } 2452