1 //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements basic block placement transformations using the CFG
11 // structure and branch probability estimates.
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.
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
26 //===----------------------------------------------------------------------===//
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/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
37 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
38 #include "llvm/CodeGen/MachineDominators.h"
39 #include "llvm/CodeGen/MachineFunction.h"
40 #include "llvm/CodeGen/MachineFunctionPass.h"
41 #include "llvm/CodeGen/MachineLoopInfo.h"
42 #include "llvm/CodeGen/MachineModuleInfo.h"
43 #include "llvm/CodeGen/TailDuplicator.h"
44 #include "llvm/Support/Allocator.h"
45 #include "llvm/Support/CommandLine.h"
46 #include "llvm/Support/Debug.h"
47 #include "llvm/Support/raw_ostream.h"
48 #include "llvm/Target/TargetInstrInfo.h"
49 #include "llvm/Target/TargetLowering.h"
50 #include "llvm/Target/TargetSubtargetInfo.h"
54 #define DEBUG_TYPE "block-placement"
56 STATISTIC(NumCondBranches, "Number of conditional branches");
57 STATISTIC(NumUncondBranches, "Number of unconditional branches");
58 STATISTIC(CondBranchTakenFreq,
59 "Potential frequency of taking conditional branches");
60 STATISTIC(UncondBranchTakenFreq,
61 "Potential frequency of taking unconditional branches");
63 static cl::opt<unsigned> AlignAllBlock("align-all-blocks",
64 cl::desc("Force the alignment of all "
65 "blocks in the function."),
66 cl::init(0), cl::Hidden);
68 static cl::opt<unsigned> AlignAllNonFallThruBlocks(
69 "align-all-nofallthru-blocks",
70 cl::desc("Force the alignment of all "
71 "blocks that have no fall-through predecessors (i.e. don't add "
72 "nops that are executed)."),
73 cl::init(0), cl::Hidden);
75 // FIXME: Find a good default for this flag and remove the flag.
76 static cl::opt<unsigned> ExitBlockBias(
77 "block-placement-exit-block-bias",
78 cl::desc("Block frequency percentage a loop exit block needs "
79 "over the original exit to be considered the new exit."),
80 cl::init(0), cl::Hidden);
83 // - Outlining: placement of a basic block outside the chain or hot path.
85 static cl::opt<bool> OutlineOptionalBranches(
86 "outline-optional-branches",
87 cl::desc("Outlining optional branches will place blocks that are optional "
88 "branches, i.e. branches with a common post dominator, outside "
89 "the hot path or chain"),
90 cl::init(false), cl::Hidden);
92 static cl::opt<unsigned> OutlineOptionalThreshold(
93 "outline-optional-threshold",
94 cl::desc("Don't outline optional branches that are a single block with an "
95 "instruction count below this threshold"),
96 cl::init(4), cl::Hidden);
98 static cl::opt<unsigned> LoopToColdBlockRatio(
99 "loop-to-cold-block-ratio",
100 cl::desc("Outline loop blocks from loop chain if (frequency of loop) / "
101 "(frequency of block) is greater than this ratio"),
102 cl::init(5), cl::Hidden);
105 PreciseRotationCost("precise-rotation-cost",
106 cl::desc("Model the cost of loop rotation more "
107 "precisely by using profile data."),
108 cl::init(false), cl::Hidden);
110 ForcePreciseRotationCost("force-precise-rotation-cost",
111 cl::desc("Force the use of precise cost "
112 "loop rotation strategy."),
113 cl::init(false), cl::Hidden);
115 static cl::opt<unsigned> MisfetchCost(
117 cl::desc("Cost that models the probabilistic risk of an instruction "
118 "misfetch due to a jump comparing to falling through, whose cost "
120 cl::init(1), cl::Hidden);
122 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
123 cl::desc("Cost of jump instructions."),
124 cl::init(1), cl::Hidden);
126 TailDupPlacement("tail-dup-placement",
127 cl::desc("Perform tail duplication during placement. "
128 "Creates more fallthrough opportunites in "
129 "outline branches."),
130 cl::init(true), cl::Hidden);
133 BranchFoldPlacement("branch-fold-placement",
134 cl::desc("Perform branch folding during placement. "
135 "Reduces code size."),
136 cl::init(true), cl::Hidden);
138 // Heuristic for tail duplication.
139 static cl::opt<unsigned> TailDuplicatePlacementThreshold(
140 "tail-dup-placement-threshold",
141 cl::desc("Instruction cutoff for tail duplication during layout. "
142 "Tail merging during layout is forced to have a threshold "
143 "that won't conflict."), cl::init(2),
146 extern cl::opt<unsigned> StaticLikelyProb;
147 extern cl::opt<unsigned> ProfileLikelyProb;
151 /// \brief Type for our function-wide basic block -> block chain mapping.
152 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
156 /// \brief A chain of blocks which will be laid out contiguously.
158 /// This is the datastructure representing a chain of consecutive blocks that
159 /// are profitable to layout together in order to maximize fallthrough
160 /// probabilities and code locality. We also can use a block chain to represent
161 /// a sequence of basic blocks which have some external (correctness)
162 /// requirement for sequential layout.
164 /// Chains can be built around a single basic block and can be merged to grow
165 /// them. They participate in a block-to-chain mapping, which is updated
166 /// automatically as chains are merged together.
168 /// \brief The sequence of blocks belonging to this chain.
170 /// This is the sequence of blocks for a particular chain. These will be laid
171 /// out in-order within the function.
172 SmallVector<MachineBasicBlock *, 4> Blocks;
174 /// \brief A handle to the function-wide basic block to block chain mapping.
176 /// This is retained in each block chain to simplify the computation of child
177 /// block chains for SCC-formation and iteration. We store the edges to child
178 /// basic blocks, and map them back to their associated chains using this
180 BlockToChainMapType &BlockToChain;
183 /// \brief Construct a new BlockChain.
185 /// This builds a new block chain representing a single basic block in the
186 /// function. It also registers itself as the chain that block participates
187 /// in with the BlockToChain mapping.
188 BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
189 : Blocks(1, BB), BlockToChain(BlockToChain), UnscheduledPredecessors(0) {
190 assert(BB && "Cannot create a chain with a null basic block");
191 BlockToChain[BB] = this;
194 /// \brief Iterator over blocks within the chain.
195 typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
197 /// \brief Beginning of blocks within the chain.
198 iterator begin() { return Blocks.begin(); }
200 /// \brief End of blocks within the chain.
201 iterator end() { return Blocks.end(); }
203 bool remove(MachineBasicBlock* BB) {
204 for(iterator i = begin(); i != end(); ++i) {
213 /// \brief Merge a block chain into this one.
215 /// This routine merges a block chain into this one. It takes care of forming
216 /// a contiguous sequence of basic blocks, updating the edge list, and
217 /// updating the block -> chain mapping. It does not free or tear down the
218 /// old chain, but the old chain's block list is no longer valid.
219 void merge(MachineBasicBlock *BB, BlockChain *Chain) {
221 assert(!Blocks.empty());
223 // Fast path in case we don't have a chain already.
225 assert(!BlockToChain[BB]);
226 Blocks.push_back(BB);
227 BlockToChain[BB] = this;
231 assert(BB == *Chain->begin());
232 assert(Chain->begin() != Chain->end());
234 // Update the incoming blocks to point to this chain, and add them to the
236 for (MachineBasicBlock *ChainBB : *Chain) {
237 Blocks.push_back(ChainBB);
238 assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain");
239 BlockToChain[ChainBB] = this;
244 /// \brief Dump the blocks in this chain.
245 LLVM_DUMP_METHOD void dump() {
246 for (MachineBasicBlock *MBB : *this)
251 /// \brief Count of predecessors of any block within the chain which have not
252 /// yet been scheduled. In general, we will delay scheduling this chain
253 /// until those predecessors are scheduled (or we find a sufficiently good
254 /// reason to override this heuristic.) Note that when forming loop chains,
255 /// blocks outside the loop are ignored and treated as if they were already
258 /// Note: This field is reinitialized multiple times - once for each loop,
259 /// and then once for the function as a whole.
260 unsigned UnscheduledPredecessors;
265 class MachineBlockPlacement : public MachineFunctionPass {
266 /// \brief A typedef for a block filter set.
267 typedef SmallSetVector<MachineBasicBlock *, 16> BlockFilterSet;
269 /// \brief work lists of blocks that are ready to be laid out
270 SmallVector<MachineBasicBlock *, 16> BlockWorkList;
271 SmallVector<MachineBasicBlock *, 16> EHPadWorkList;
273 /// \brief Machine Function
276 /// \brief A handle to the branch probability pass.
277 const MachineBranchProbabilityInfo *MBPI;
279 /// \brief A handle to the function-wide block frequency pass.
280 std::unique_ptr<BranchFolder::MBFIWrapper> MBFI;
282 /// \brief A handle to the loop info.
283 MachineLoopInfo *MLI;
285 /// \brief Preferred loop exit.
286 /// Member variable for convenience. It may be removed by duplication deep
287 /// in the call stack.
288 MachineBasicBlock *PreferredLoopExit;
290 /// \brief A handle to the target's instruction info.
291 const TargetInstrInfo *TII;
293 /// \brief A handle to the target's lowering info.
294 const TargetLoweringBase *TLI;
296 /// \brief A handle to the post dominator tree.
297 MachineDominatorTree *MDT;
299 /// \brief Duplicator used to duplicate tails during placement.
301 /// Placement decisions can open up new tail duplication opportunities, but
302 /// since tail duplication affects placement decisions of later blocks, it
303 /// must be done inline.
304 TailDuplicator TailDup;
306 /// \brief A set of blocks that are unavoidably execute, i.e. they dominate
307 /// all terminators of the MachineFunction.
308 SmallPtrSet<MachineBasicBlock *, 4> UnavoidableBlocks;
310 /// \brief Allocator and owner of BlockChain structures.
312 /// We build BlockChains lazily while processing the loop structure of
313 /// a function. To reduce malloc traffic, we allocate them using this
314 /// slab-like allocator, and destroy them after the pass completes. An
315 /// important guarantee is that this allocator produces stable pointers to
317 SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
319 /// \brief Function wide BasicBlock to BlockChain mapping.
321 /// This mapping allows efficiently moving from any given basic block to the
322 /// BlockChain it participates in, if any. We use it to, among other things,
323 /// allow implicitly defining edges between chains as the existing edges
324 /// between basic blocks.
325 DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
328 /// The set of basic blocks that have terminators that cannot be fully
329 /// analyzed. These basic blocks cannot be re-ordered safely by
330 /// MachineBlockPlacement, and we must preserve physical layout of these
331 /// blocks and their successors through the pass.
332 SmallPtrSet<MachineBasicBlock *, 4> BlocksWithUnanalyzableExits;
335 /// Decrease the UnscheduledPredecessors count for all blocks in chain, and
336 /// if the count goes to 0, add them to the appropriate work list.
337 void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
338 const BlockFilterSet *BlockFilter = nullptr);
340 /// Decrease the UnscheduledPredecessors count for a single block, and
341 /// if the count goes to 0, add them to the appropriate work list.
342 void markBlockSuccessors(
343 BlockChain &Chain, MachineBasicBlock *BB, MachineBasicBlock *LoopHeaderBB,
344 const BlockFilterSet *BlockFilter = nullptr);
348 collectViableSuccessors(MachineBasicBlock *BB, BlockChain &Chain,
349 const BlockFilterSet *BlockFilter,
350 SmallVector<MachineBasicBlock *, 4> &Successors);
351 bool shouldPredBlockBeOutlined(MachineBasicBlock *BB, MachineBasicBlock *Succ,
353 const BlockFilterSet *BlockFilter,
354 BranchProbability SuccProb,
355 BranchProbability HotProb);
356 bool repeatedlyTailDuplicateBlock(
357 MachineBasicBlock *BB, MachineBasicBlock *&LPred,
358 MachineBasicBlock *LoopHeaderBB,
359 BlockChain &Chain, BlockFilterSet *BlockFilter,
360 MachineFunction::iterator &PrevUnplacedBlockIt);
361 bool maybeTailDuplicateBlock(MachineBasicBlock *BB, MachineBasicBlock *LPred,
362 const BlockChain &Chain,
363 BlockFilterSet *BlockFilter,
364 MachineFunction::iterator &PrevUnplacedBlockIt,
365 bool &DuplicatedToPred);
367 hasBetterLayoutPredecessor(MachineBasicBlock *BB, MachineBasicBlock *Succ,
368 BlockChain &SuccChain, BranchProbability SuccProb,
369 BranchProbability RealSuccProb, BlockChain &Chain,
370 const BlockFilterSet *BlockFilter);
371 MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
373 const BlockFilterSet *BlockFilter);
375 selectBestCandidateBlock(BlockChain &Chain,
376 SmallVectorImpl<MachineBasicBlock *> &WorkList);
378 getFirstUnplacedBlock(const BlockChain &PlacedChain,
379 MachineFunction::iterator &PrevUnplacedBlockIt,
380 const BlockFilterSet *BlockFilter);
382 /// \brief Add a basic block to the work list if it is appropriate.
384 /// If the optional parameter BlockFilter is provided, only MBB
385 /// present in the set will be added to the worklist. If nullptr
386 /// is provided, no filtering occurs.
387 void fillWorkLists(MachineBasicBlock *MBB,
388 SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
389 const BlockFilterSet *BlockFilter);
390 void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
391 BlockFilterSet *BlockFilter = nullptr);
392 MachineBasicBlock *findBestLoopTop(MachineLoop &L,
393 const BlockFilterSet &LoopBlockSet);
394 MachineBasicBlock *findBestLoopExit(MachineLoop &L,
395 const BlockFilterSet &LoopBlockSet);
396 BlockFilterSet collectLoopBlockSet(MachineLoop &L);
397 void buildLoopChains(MachineLoop &L);
398 void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB,
399 const BlockFilterSet &LoopBlockSet);
400 void rotateLoopWithProfile(BlockChain &LoopChain, MachineLoop &L,
401 const BlockFilterSet &LoopBlockSet);
402 void collectMustExecuteBBs();
403 void buildCFGChains();
404 void optimizeBranches();
408 static char ID; // Pass identification, replacement for typeid
409 MachineBlockPlacement() : MachineFunctionPass(ID) {
410 initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
413 bool runOnMachineFunction(MachineFunction &F) override;
415 void getAnalysisUsage(AnalysisUsage &AU) const override {
416 AU.addRequired<MachineBranchProbabilityInfo>();
417 AU.addRequired<MachineBlockFrequencyInfo>();
418 AU.addRequired<MachineDominatorTree>();
419 AU.addRequired<MachineLoopInfo>();
420 AU.addRequired<TargetPassConfig>();
421 MachineFunctionPass::getAnalysisUsage(AU);
426 char MachineBlockPlacement::ID = 0;
427 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
428 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement",
429 "Branch Probability Basic Block Placement", false, false)
430 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
431 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
432 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
433 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
434 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement",
435 "Branch Probability Basic Block Placement", false, false)
438 /// \brief Helper to print the name of a MBB.
440 /// Only used by debug logging.
441 static std::string getBlockName(MachineBasicBlock *BB) {
443 raw_string_ostream OS(Result);
444 OS << "BB#" << BB->getNumber();
445 OS << " ('" << BB->getName() << "')";
451 /// \brief Mark a chain's successors as having one fewer preds.
453 /// When a chain is being merged into the "placed" chain, this routine will
454 /// quickly walk the successors of each block in the chain and mark them as
455 /// having one fewer active predecessor. It also adds any successors of this
456 /// chain which reach the zero-predecessor state to the appropriate worklist.
457 void MachineBlockPlacement::markChainSuccessors(
458 BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
459 const BlockFilterSet *BlockFilter) {
460 // Walk all the blocks in this chain, marking their successors as having
461 // a predecessor placed.
462 for (MachineBasicBlock *MBB : Chain) {
463 markBlockSuccessors(Chain, MBB, LoopHeaderBB, BlockFilter);
467 /// \brief Mark a single block's successors as having one fewer preds.
469 /// Under normal circumstances, this is only called by markChainSuccessors,
470 /// but if a block that was to be placed is completely tail-duplicated away,
471 /// and was duplicated into the chain end, we need to redo markBlockSuccessors
472 /// for just that block.
473 void MachineBlockPlacement::markBlockSuccessors(
474 BlockChain &Chain, MachineBasicBlock *MBB, MachineBasicBlock *LoopHeaderBB,
475 const BlockFilterSet *BlockFilter) {
476 // Add any successors for which this is the only un-placed in-loop
477 // predecessor to the worklist as a viable candidate for CFG-neutral
478 // placement. No subsequent placement of this block will violate the CFG
479 // shape, so we get to use heuristics to choose a favorable placement.
480 for (MachineBasicBlock *Succ : MBB->successors()) {
481 if (BlockFilter && !BlockFilter->count(Succ))
483 BlockChain &SuccChain = *BlockToChain[Succ];
484 // Disregard edges within a fixed chain, or edges to the loop header.
485 if (&Chain == &SuccChain || Succ == LoopHeaderBB)
488 // This is a cross-chain edge that is within the loop, so decrement the
489 // loop predecessor count of the destination chain.
490 if (SuccChain.UnscheduledPredecessors == 0 ||
491 --SuccChain.UnscheduledPredecessors > 0)
494 auto *NewBB = *SuccChain.begin();
495 if (NewBB->isEHPad())
496 EHPadWorkList.push_back(NewBB);
498 BlockWorkList.push_back(NewBB);
502 /// This helper function collects the set of successors of block
503 /// \p BB that are allowed to be its layout successors, and return
504 /// the total branch probability of edges from \p BB to those
506 BranchProbability MachineBlockPlacement::collectViableSuccessors(
507 MachineBasicBlock *BB, BlockChain &Chain, const BlockFilterSet *BlockFilter,
508 SmallVector<MachineBasicBlock *, 4> &Successors) {
509 // Adjust edge probabilities by excluding edges pointing to blocks that is
510 // either not in BlockFilter or is already in the current chain. Consider the
519 // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after
520 // A->C is chosen as a fall-through, D won't be selected as a successor of C
521 // due to CFG constraint (the probability of C->D is not greater than
522 // HotProb to break top-order). If we exclude E that is not in BlockFilter
523 // when calculating the probability of C->D, D will be selected and we
524 // will get A C D B as the layout of this loop.
525 auto AdjustedSumProb = BranchProbability::getOne();
526 for (MachineBasicBlock *Succ : BB->successors()) {
527 bool SkipSucc = false;
528 if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) {
531 BlockChain *SuccChain = BlockToChain[Succ];
532 if (SuccChain == &Chain) {
534 } else if (Succ != *SuccChain->begin()) {
535 DEBUG(dbgs() << " " << getBlockName(Succ) << " -> Mid chain!\n");
540 AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ);
542 Successors.push_back(Succ);
545 return AdjustedSumProb;
548 /// The helper function returns the branch probability that is adjusted
549 /// or normalized over the new total \p AdjustedSumProb.
550 static BranchProbability
551 getAdjustedProbability(BranchProbability OrigProb,
552 BranchProbability AdjustedSumProb) {
553 BranchProbability SuccProb;
554 uint32_t SuccProbN = OrigProb.getNumerator();
555 uint32_t SuccProbD = AdjustedSumProb.getNumerator();
556 if (SuccProbN >= SuccProbD)
557 SuccProb = BranchProbability::getOne();
559 SuccProb = BranchProbability(SuccProbN, SuccProbD);
564 /// When the option OutlineOptionalBranches is on, this method
565 /// checks if the fallthrough candidate block \p Succ (of block
566 /// \p BB) also has other unscheduled predecessor blocks which
567 /// are also successors of \p BB (forming triangular shape CFG).
568 /// If none of such predecessors are small, it returns true.
569 /// The caller can choose to select \p Succ as the layout successors
570 /// so that \p Succ's predecessors (optional branches) can be
572 /// FIXME: fold this with more general layout cost analysis.
573 bool MachineBlockPlacement::shouldPredBlockBeOutlined(
574 MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &Chain,
575 const BlockFilterSet *BlockFilter, BranchProbability SuccProb,
576 BranchProbability HotProb) {
577 if (!OutlineOptionalBranches)
579 // If we outline optional branches, look whether Succ is unavoidable, i.e.
580 // dominates all terminators of the MachineFunction. If it does, other
581 // successors must be optional. Don't do this for cold branches.
582 if (SuccProb > HotProb.getCompl() && UnavoidableBlocks.count(Succ) > 0) {
583 for (MachineBasicBlock *Pred : Succ->predecessors()) {
584 // Check whether there is an unplaced optional branch.
585 if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
586 BlockToChain[Pred] == &Chain)
588 // Check whether the optional branch has exactly one BB.
589 if (Pred->pred_size() > 1 || *Pred->pred_begin() != BB)
591 // Check whether the optional branch is small.
592 if (Pred->size() < OutlineOptionalThreshold)
600 // When profile is not present, return the StaticLikelyProb.
601 // When profile is available, we need to handle the triangle-shape CFG.
602 static BranchProbability getLayoutSuccessorProbThreshold(
603 MachineBasicBlock *BB) {
604 if (!BB->getParent()->getFunction()->getEntryCount())
605 return BranchProbability(StaticLikelyProb, 100);
606 if (BB->succ_size() == 2) {
607 const MachineBasicBlock *Succ1 = *BB->succ_begin();
608 const MachineBasicBlock *Succ2 = *(BB->succ_begin() + 1);
609 if (Succ1->isSuccessor(Succ2) || Succ2->isSuccessor(Succ1)) {
610 /* See case 1 below for the cost analysis. For BB->Succ to
611 * be taken with smaller cost, the following needs to hold:
612 * Prob(BB->Succ) > 2* Prob(BB->Pred)
614 * T = 2 * (1-Prob(BB->Pred). Since T + Prob(BB->Pred) == 1,
615 * We have T + T/2 = 1, i.e. T = 2/3. Also adding user specified
616 * branch bias, we have
617 * T = (2/3)*(ProfileLikelyProb/50)
618 * = (2*ProfileLikelyProb)/150)
620 return BranchProbability(2 * ProfileLikelyProb, 150);
623 return BranchProbability(ProfileLikelyProb, 100);
626 /// Checks to see if the layout candidate block \p Succ has a better layout
627 /// predecessor than \c BB. If yes, returns true.
628 bool MachineBlockPlacement::hasBetterLayoutPredecessor(
629 MachineBasicBlock *BB, MachineBasicBlock *Succ, BlockChain &SuccChain,
630 BranchProbability SuccProb, BranchProbability RealSuccProb,
631 BlockChain &Chain, const BlockFilterSet *BlockFilter) {
633 // There isn't a better layout when there are no unscheduled predecessors.
634 if (SuccChain.UnscheduledPredecessors == 0)
637 // There are two basic scenarios here:
638 // -------------------------------------
639 // Case 1: triangular shape CFG (if-then):
646 // In this case, we are evaluating whether to select edge -> Succ, e.g.
647 // set Succ as the layout successor of BB. Picking Succ as BB's
648 // successor breaks the CFG constraints (FIXME: define these constraints).
649 // With this layout, Pred BB
650 // is forced to be outlined, so the overall cost will be cost of the
651 // branch taken from BB to Pred, plus the cost of back taken branch
652 // from Pred to Succ, as well as the additional cost associated
653 // with the needed unconditional jump instruction from Pred To Succ.
655 // The cost of the topological order layout is the taken branch cost
656 // from BB to Succ, so to make BB->Succ a viable candidate, the following
658 // 2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost
659 // < freq(BB->Succ) * taken_branch_cost.
660 // Ignoring unconditional jump cost, we get
661 // freq(BB->Succ) > 2 * freq(BB->Pred), i.e.,
662 // prob(BB->Succ) > 2 * prob(BB->Pred)
664 // When real profile data is available, we can precisely compute the
665 // probability threshold that is needed for edge BB->Succ to be considered.
666 // Without profile data, the heuristic requires the branch bias to be
667 // a lot larger to make sure the signal is very strong (e.g. 80% default).
668 // -----------------------------------------------------------------
669 // Case 2: diamond like CFG (if-then-else):
678 // The current block is BB and edge BB->Succ is now being evaluated.
679 // Note that edge S->BB was previously already selected because
680 // prob(S->BB) > prob(S->Pred).
681 // At this point, 2 blocks can be placed after BB: Pred or Succ. If we
682 // choose Pred, we will have a topological ordering as shown on the left
683 // in the picture below. If we choose Succ, we have the solution as shown
696 // cost = freq(S->Pred) + freq(BB->Succ) cost = 2 * freq (S->Pred)
697 // = freq(S->Pred) + freq(S->BB)
699 // If we have profile data (i.e, branch probabilities can be trusted), the
700 // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 *
701 // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB).
702 // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which
703 // means the cost of topological order is greater.
704 // When profile data is not available, however, we need to be more
705 // conservative. If the branch prediction is wrong, breaking the topo-order
706 // will actually yield a layout with large cost. For this reason, we need
707 // strong biased branch at block S with Prob(S->BB) in order to select
708 // BB->Succ. This is equivalent to looking the CFG backward with backward
709 // edge: Prob(Succ->BB) needs to >= HotProb in order to be selected (without
711 // --------------------------------------------------------------------------
712 // Case 3: forked diamond
724 // The current block is BB and edge BB->S1 is now being evaluated.
725 // As above S->BB was already selected because
726 // prob(S->BB) > prob(S->Pred). Assume that prob(BB->S1) >= prob(BB->S2).
734 // | Pred----| | S1----
736 // --(S1 or S2) ---Pred--
738 // topo-cost = freq(S->Pred) + freq(BB->S1) + freq(BB->S2)
739 // + min(freq(Pred->S1), freq(Pred->S2))
740 // Non-topo-order cost:
741 // In the worst case, S2 will not get laid out after Pred.
742 // non-topo-cost = 2 * freq(S->Pred) + freq(BB->S2).
743 // To be conservative, we can assume that min(freq(Pred->S1), freq(Pred->S2))
744 // is 0. Then the non topo layout is better when
745 // freq(S->Pred) < freq(BB->S1).
746 // This is exactly what is checked below.
747 // Note there are other shapes that apply (Pred may not be a single block,
748 // but they all fit this general pattern.)
749 BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB);
751 // Make sure that a hot successor doesn't have a globally more
752 // important predecessor.
753 BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
754 bool BadCFGConflict = false;
756 for (MachineBasicBlock *Pred : Succ->predecessors()) {
757 if (Pred == Succ || BlockToChain[Pred] == &SuccChain ||
758 (BlockFilter && !BlockFilter->count(Pred)) ||
759 BlockToChain[Pred] == &Chain)
761 // Do backward checking.
762 // For all cases above, we need a backward checking to filter out edges that
763 // are not 'strongly' biased. With profile data available, the check is
764 // mostly redundant for case 2 (when threshold prob is set at 50%) unless S
765 // has more than two successors.
769 // We select edge BB->Succ if
770 // freq(BB->Succ) > freq(Succ) * HotProb
771 // i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) *
773 // i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb
774 // Case 1 is covered too, because the first equation reduces to:
775 // prob(BB->Succ) > HotProb. (freq(Succ) = freq(BB) for a triangle)
776 BlockFrequency PredEdgeFreq =
777 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
778 if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) {
779 BadCFGConflict = true;
784 if (BadCFGConflict) {
785 DEBUG(dbgs() << " Not a candidate: " << getBlockName(Succ) << " -> " << SuccProb
786 << " (prob) (non-cold CFG conflict)\n");
793 /// \brief Select the best successor for a block.
795 /// This looks across all successors of a particular block and attempts to
796 /// select the "best" one to be the layout successor. It only considers direct
797 /// successors which also pass the block filter. It will attempt to avoid
798 /// breaking CFG structure, but cave and break such structures in the case of
799 /// very hot successor edges.
801 /// \returns The best successor block found, or null if none are viable.
803 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
805 const BlockFilterSet *BlockFilter) {
806 const BranchProbability HotProb(StaticLikelyProb, 100);
808 MachineBasicBlock *BestSucc = nullptr;
809 auto BestProb = BranchProbability::getZero();
811 SmallVector<MachineBasicBlock *, 4> Successors;
812 auto AdjustedSumProb =
813 collectViableSuccessors(BB, Chain, BlockFilter, Successors);
815 DEBUG(dbgs() << "Selecting best successor for: " << getBlockName(BB) << "\n");
816 for (MachineBasicBlock *Succ : Successors) {
817 auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
818 BranchProbability SuccProb =
819 getAdjustedProbability(RealSuccProb, AdjustedSumProb);
821 // This heuristic is off by default.
822 if (shouldPredBlockBeOutlined(BB, Succ, Chain, BlockFilter, SuccProb,
826 BlockChain &SuccChain = *BlockToChain[Succ];
827 // Skip the edge \c BB->Succ if block \c Succ has a better layout
828 // predecessor that yields lower global cost.
829 if (hasBetterLayoutPredecessor(BB, Succ, SuccChain, SuccProb, RealSuccProb,
834 dbgs() << " Candidate: " << getBlockName(Succ) << ", probability: "
836 << (SuccChain.UnscheduledPredecessors != 0 ? " (CFG break)" : "")
839 if (BestSucc && BestProb >= SuccProb) {
840 DEBUG(dbgs() << " Not the best candidate, continuing\n");
844 DEBUG(dbgs() << " Setting it as best candidate\n");
849 DEBUG(dbgs() << " Selected: " << getBlockName(BestSucc) << "\n");
854 /// \brief Select the best block from a worklist.
856 /// This looks through the provided worklist as a list of candidate basic
857 /// blocks and select the most profitable one to place. The definition of
858 /// profitable only really makes sense in the context of a loop. This returns
859 /// the most frequently visited block in the worklist, which in the case of
860 /// a loop, is the one most desirable to be physically close to the rest of the
861 /// loop body in order to improve i-cache behavior.
863 /// \returns The best block found, or null if none are viable.
864 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
865 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList) {
866 // Once we need to walk the worklist looking for a candidate, cleanup the
867 // worklist of already placed entries.
868 // FIXME: If this shows up on profiles, it could be folded (at the cost of
869 // some code complexity) into the loop below.
870 WorkList.erase(remove_if(WorkList,
871 [&](MachineBasicBlock *BB) {
872 return BlockToChain.lookup(BB) == &Chain;
876 if (WorkList.empty())
879 bool IsEHPad = WorkList[0]->isEHPad();
881 MachineBasicBlock *BestBlock = nullptr;
882 BlockFrequency BestFreq;
883 for (MachineBasicBlock *MBB : WorkList) {
884 assert(MBB->isEHPad() == IsEHPad);
886 BlockChain &SuccChain = *BlockToChain[MBB];
887 if (&SuccChain == &Chain)
890 assert(SuccChain.UnscheduledPredecessors == 0 && "Found CFG-violating block");
892 BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB);
893 DEBUG(dbgs() << " " << getBlockName(MBB) << " -> ";
894 MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n");
896 // For ehpad, we layout the least probable first as to avoid jumping back
897 // from least probable landingpads to more probable ones.
899 // FIXME: Using probability is probably (!) not the best way to achieve
900 // this. We should probably have a more principled approach to layout
903 // The goal is to get:
905 // +--------------------------+
907 // InnerLp -> InnerCleanup OuterLp -> OuterCleanup -> Resume
911 // +-------------------------------------+
913 // OuterLp -> OuterCleanup -> Resume InnerLp -> InnerCleanup
914 if (BestBlock && (IsEHPad ^ (BestFreq >= CandidateFreq)))
918 BestFreq = CandidateFreq;
924 /// \brief Retrieve the first unplaced basic block.
926 /// This routine is called when we are unable to use the CFG to walk through
927 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
928 /// We walk through the function's blocks in order, starting from the
929 /// LastUnplacedBlockIt. We update this iterator on each call to avoid
930 /// re-scanning the entire sequence on repeated calls to this routine.
931 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock(
932 const BlockChain &PlacedChain,
933 MachineFunction::iterator &PrevUnplacedBlockIt,
934 const BlockFilterSet *BlockFilter) {
935 for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F->end(); I != E;
937 if (BlockFilter && !BlockFilter->count(&*I))
939 if (BlockToChain[&*I] != &PlacedChain) {
940 PrevUnplacedBlockIt = I;
941 // Now select the head of the chain to which the unplaced block belongs
942 // as the block to place. This will force the entire chain to be placed,
943 // and satisfies the requirements of merging chains.
944 return *BlockToChain[&*I]->begin();
950 void MachineBlockPlacement::fillWorkLists(
951 MachineBasicBlock *MBB,
952 SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
953 const BlockFilterSet *BlockFilter = nullptr) {
954 BlockChain &Chain = *BlockToChain[MBB];
955 if (!UpdatedPreds.insert(&Chain).second)
958 assert(Chain.UnscheduledPredecessors == 0);
959 for (MachineBasicBlock *ChainBB : Chain) {
960 assert(BlockToChain[ChainBB] == &Chain);
961 for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
962 if (BlockFilter && !BlockFilter->count(Pred))
964 if (BlockToChain[Pred] == &Chain)
966 ++Chain.UnscheduledPredecessors;
970 if (Chain.UnscheduledPredecessors != 0)
973 MBB = *Chain.begin();
975 EHPadWorkList.push_back(MBB);
977 BlockWorkList.push_back(MBB);
980 void MachineBlockPlacement::buildChain(
981 MachineBasicBlock *BB, BlockChain &Chain,
982 BlockFilterSet *BlockFilter) {
983 assert(BB && "BB must not be null.\n");
984 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match.\n");
985 MachineFunction::iterator PrevUnplacedBlockIt = F->begin();
987 MachineBasicBlock *LoopHeaderBB = BB;
988 markChainSuccessors(Chain, LoopHeaderBB, BlockFilter);
989 BB = *std::prev(Chain.end());
991 assert(BB && "null block found at end of chain in loop.");
992 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop.");
993 assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain.");
996 // Look for the best viable successor if there is one to place immediately
998 MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
1000 // If an immediate successor isn't available, look for the best viable
1001 // block among those we've identified as not violating the loop's CFG at
1002 // this point. This won't be a fallthrough, but it will increase locality.
1004 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList);
1006 BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList);
1009 BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt, BlockFilter);
1013 DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
1014 "layout successor until the CFG reduces\n");
1017 // Placement may have changed tail duplication opportunities.
1018 // Check for that now.
1019 if (TailDupPlacement && BestSucc) {
1020 // If the chosen successor was duplicated into all its predecessors,
1021 // don't bother laying it out, just go round the loop again with BB as
1023 if (repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain,
1024 BlockFilter, PrevUnplacedBlockIt))
1028 // Place this block, updating the datastructures to reflect its placement.
1029 BlockChain &SuccChain = *BlockToChain[BestSucc];
1030 // Zero out UnscheduledPredecessors for the successor we're about to merge in case
1031 // we selected a successor that didn't fit naturally into the CFG.
1032 SuccChain.UnscheduledPredecessors = 0;
1033 DEBUG(dbgs() << "Merging from " << getBlockName(BB) << " to "
1034 << getBlockName(BestSucc) << "\n");
1035 markChainSuccessors(SuccChain, LoopHeaderBB, BlockFilter);
1036 Chain.merge(BestSucc, &SuccChain);
1037 BB = *std::prev(Chain.end());
1040 DEBUG(dbgs() << "Finished forming chain for header block "
1041 << getBlockName(*Chain.begin()) << "\n");
1044 /// \brief Find the best loop top block for layout.
1046 /// Look for a block which is strictly better than the loop header for laying
1047 /// out at the top of the loop. This looks for one and only one pattern:
1048 /// a latch block with no conditional exit. This block will cause a conditional
1049 /// jump around it or will be the bottom of the loop if we lay it out in place,
1050 /// but if it it doesn't end up at the bottom of the loop for any reason,
1051 /// rotation alone won't fix it. Because such a block will always result in an
1052 /// unconditional jump (for the backedge) rotating it in front of the loop
1053 /// header is always profitable.
1055 MachineBlockPlacement::findBestLoopTop(MachineLoop &L,
1056 const BlockFilterSet &LoopBlockSet) {
1057 // Placing the latch block before the header may introduce an extra branch
1058 // that skips this block the first time the loop is executed, which we want
1059 // to avoid when optimising for size.
1060 // FIXME: in theory there is a case that does not introduce a new branch,
1061 // i.e. when the layout predecessor does not fallthrough to the loop header.
1062 // In practice this never happens though: there always seems to be a preheader
1063 // that can fallthrough and that is also placed before the header.
1064 if (F->getFunction()->optForSize())
1065 return L.getHeader();
1067 // Check that the header hasn't been fused with a preheader block due to
1068 // crazy branches. If it has, we need to start with the header at the top to
1069 // prevent pulling the preheader into the loop body.
1070 BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
1071 if (!LoopBlockSet.count(*HeaderChain.begin()))
1072 return L.getHeader();
1074 DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
1077 BlockFrequency BestPredFreq;
1078 MachineBasicBlock *BestPred = nullptr;
1079 for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
1080 if (!LoopBlockSet.count(Pred))
1082 DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", has "
1083 << Pred->succ_size() << " successors, ";
1084 MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
1085 if (Pred->succ_size() > 1)
1088 BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
1089 if (!BestPred || PredFreq > BestPredFreq ||
1090 (!(PredFreq < BestPredFreq) &&
1091 Pred->isLayoutSuccessor(L.getHeader()))) {
1093 BestPredFreq = PredFreq;
1097 // If no direct predecessor is fine, just use the loop header.
1099 DEBUG(dbgs() << " final top unchanged\n");
1100 return L.getHeader();
1103 // Walk backwards through any straight line of predecessors.
1104 while (BestPred->pred_size() == 1 &&
1105 (*BestPred->pred_begin())->succ_size() == 1 &&
1106 *BestPred->pred_begin() != L.getHeader())
1107 BestPred = *BestPred->pred_begin();
1109 DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n");
1113 /// \brief Find the best loop exiting block for layout.
1115 /// This routine implements the logic to analyze the loop looking for the best
1116 /// block to layout at the top of the loop. Typically this is done to maximize
1117 /// fallthrough opportunities.
1119 MachineBlockPlacement::findBestLoopExit(MachineLoop &L,
1120 const BlockFilterSet &LoopBlockSet) {
1121 // We don't want to layout the loop linearly in all cases. If the loop header
1122 // is just a normal basic block in the loop, we want to look for what block
1123 // within the loop is the best one to layout at the top. However, if the loop
1124 // header has be pre-merged into a chain due to predecessors not having
1125 // analyzable branches, *and* the predecessor it is merged with is *not* part
1126 // of the loop, rotating the header into the middle of the loop will create
1127 // a non-contiguous range of blocks which is Very Bad. So start with the
1128 // header and only rotate if safe.
1129 BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
1130 if (!LoopBlockSet.count(*HeaderChain.begin()))
1133 BlockFrequency BestExitEdgeFreq;
1134 unsigned BestExitLoopDepth = 0;
1135 MachineBasicBlock *ExitingBB = nullptr;
1136 // If there are exits to outer loops, loop rotation can severely limit
1137 // fallthrough opportunities unless it selects such an exit. Keep a set of
1138 // blocks where rotating to exit with that block will reach an outer loop.
1139 SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
1141 DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader())
1143 for (MachineBasicBlock *MBB : L.getBlocks()) {
1144 BlockChain &Chain = *BlockToChain[MBB];
1145 // Ensure that this block is at the end of a chain; otherwise it could be
1146 // mid-way through an inner loop or a successor of an unanalyzable branch.
1147 if (MBB != *std::prev(Chain.end()))
1150 // Now walk the successors. We need to establish whether this has a viable
1151 // exiting successor and whether it has a viable non-exiting successor.
1152 // We store the old exiting state and restore it if a viable looping
1153 // successor isn't found.
1154 MachineBasicBlock *OldExitingBB = ExitingBB;
1155 BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq;
1156 bool HasLoopingSucc = false;
1157 for (MachineBasicBlock *Succ : MBB->successors()) {
1158 if (Succ->isEHPad())
1162 BlockChain &SuccChain = *BlockToChain[Succ];
1163 // Don't split chains, either this chain or the successor's chain.
1164 if (&Chain == &SuccChain) {
1165 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
1166 << getBlockName(Succ) << " (chain conflict)\n");
1170 auto SuccProb = MBPI->getEdgeProbability(MBB, Succ);
1171 if (LoopBlockSet.count(Succ)) {
1172 DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> "
1173 << getBlockName(Succ) << " (" << SuccProb << ")\n");
1174 HasLoopingSucc = true;
1178 unsigned SuccLoopDepth = 0;
1179 if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) {
1180 SuccLoopDepth = ExitLoop->getLoopDepth();
1181 if (ExitLoop->contains(&L))
1182 BlocksExitingToOuterLoop.insert(MBB);
1185 BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
1186 DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
1187 << getBlockName(Succ) << " [L:" << SuccLoopDepth << "] (";
1188 MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n");
1189 // Note that we bias this toward an existing layout successor to retain
1190 // incoming order in the absence of better information. The exit must have
1191 // a frequency higher than the current exit before we consider breaking
1193 BranchProbability Bias(100 - ExitBlockBias, 100);
1194 if (!ExitingBB || SuccLoopDepth > BestExitLoopDepth ||
1195 ExitEdgeFreq > BestExitEdgeFreq ||
1196 (MBB->isLayoutSuccessor(Succ) &&
1197 !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) {
1198 BestExitEdgeFreq = ExitEdgeFreq;
1203 if (!HasLoopingSucc) {
1204 // Restore the old exiting state, no viable looping successor was found.
1205 ExitingBB = OldExitingBB;
1206 BestExitEdgeFreq = OldBestExitEdgeFreq;
1209 // Without a candidate exiting block or with only a single block in the
1210 // loop, just use the loop header to layout the loop.
1212 DEBUG(dbgs() << " No other candidate exit blocks, using loop header\n");
1215 if (L.getNumBlocks() == 1) {
1216 DEBUG(dbgs() << " Loop has 1 block, using loop header as exit\n");
1220 // Also, if we have exit blocks which lead to outer loops but didn't select
1221 // one of them as the exiting block we are rotating toward, disable loop
1222 // rotation altogether.
1223 if (!BlocksExitingToOuterLoop.empty() &&
1224 !BlocksExitingToOuterLoop.count(ExitingBB))
1227 DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n");
1231 /// \brief Attempt to rotate an exiting block to the bottom of the loop.
1233 /// Once we have built a chain, try to rotate it to line up the hot exit block
1234 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary
1235 /// branches. For example, if the loop has fallthrough into its header and out
1236 /// of its bottom already, don't rotate it.
1237 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
1238 MachineBasicBlock *ExitingBB,
1239 const BlockFilterSet &LoopBlockSet) {
1243 MachineBasicBlock *Top = *LoopChain.begin();
1244 bool ViableTopFallthrough = false;
1245 for (MachineBasicBlock *Pred : Top->predecessors()) {
1246 BlockChain *PredChain = BlockToChain[Pred];
1247 if (!LoopBlockSet.count(Pred) &&
1248 (!PredChain || Pred == *std::prev(PredChain->end()))) {
1249 ViableTopFallthrough = true;
1254 // If the header has viable fallthrough, check whether the current loop
1255 // bottom is a viable exiting block. If so, bail out as rotating will
1256 // introduce an unnecessary branch.
1257 if (ViableTopFallthrough) {
1258 MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
1259 for (MachineBasicBlock *Succ : Bottom->successors()) {
1260 BlockChain *SuccChain = BlockToChain[Succ];
1261 if (!LoopBlockSet.count(Succ) &&
1262 (!SuccChain || Succ == *SuccChain->begin()))
1267 BlockChain::iterator ExitIt = find(LoopChain, ExitingBB);
1268 if (ExitIt == LoopChain.end())
1271 std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end());
1274 /// \brief Attempt to rotate a loop based on profile data to reduce branch cost.
1276 /// With profile data, we can determine the cost in terms of missed fall through
1277 /// opportunities when rotating a loop chain and select the best rotation.
1278 /// Basically, there are three kinds of cost to consider for each rotation:
1279 /// 1. The possibly missed fall through edge (if it exists) from BB out of
1280 /// the loop to the loop header.
1281 /// 2. The possibly missed fall through edges (if they exist) from the loop
1282 /// exits to BB out of the loop.
1283 /// 3. The missed fall through edge (if it exists) from the last BB to the
1284 /// first BB in the loop chain.
1285 /// Therefore, the cost for a given rotation is the sum of costs listed above.
1286 /// We select the best rotation with the smallest cost.
1287 void MachineBlockPlacement::rotateLoopWithProfile(
1288 BlockChain &LoopChain, MachineLoop &L, const BlockFilterSet &LoopBlockSet) {
1289 auto HeaderBB = L.getHeader();
1290 auto HeaderIter = find(LoopChain, HeaderBB);
1291 auto RotationPos = LoopChain.end();
1293 BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency();
1295 // A utility lambda that scales up a block frequency by dividing it by a
1296 // branch probability which is the reciprocal of the scale.
1297 auto ScaleBlockFrequency = [](BlockFrequency Freq,
1298 unsigned Scale) -> BlockFrequency {
1301 // Use operator / between BlockFrequency and BranchProbability to implement
1302 // saturating multiplication.
1303 return Freq / BranchProbability(1, Scale);
1306 // Compute the cost of the missed fall-through edge to the loop header if the
1307 // chain head is not the loop header. As we only consider natural loops with
1308 // single header, this computation can be done only once.
1309 BlockFrequency HeaderFallThroughCost(0);
1310 for (auto *Pred : HeaderBB->predecessors()) {
1311 BlockChain *PredChain = BlockToChain[Pred];
1312 if (!LoopBlockSet.count(Pred) &&
1313 (!PredChain || Pred == *std::prev(PredChain->end()))) {
1315 MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, HeaderBB);
1316 auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost);
1317 // If the predecessor has only an unconditional jump to the header, we
1318 // need to consider the cost of this jump.
1319 if (Pred->succ_size() == 1)
1320 FallThruCost += ScaleBlockFrequency(EdgeFreq, JumpInstCost);
1321 HeaderFallThroughCost = std::max(HeaderFallThroughCost, FallThruCost);
1325 // Here we collect all exit blocks in the loop, and for each exit we find out
1326 // its hottest exit edge. For each loop rotation, we define the loop exit cost
1327 // as the sum of frequencies of exit edges we collect here, excluding the exit
1328 // edge from the tail of the loop chain.
1329 SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq;
1330 for (auto BB : LoopChain) {
1331 auto LargestExitEdgeProb = BranchProbability::getZero();
1332 for (auto *Succ : BB->successors()) {
1333 BlockChain *SuccChain = BlockToChain[Succ];
1334 if (!LoopBlockSet.count(Succ) &&
1335 (!SuccChain || Succ == *SuccChain->begin())) {
1336 auto SuccProb = MBPI->getEdgeProbability(BB, Succ);
1337 LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb);
1340 if (LargestExitEdgeProb > BranchProbability::getZero()) {
1341 auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb;
1342 ExitsWithFreq.emplace_back(BB, ExitFreq);
1346 // In this loop we iterate every block in the loop chain and calculate the
1347 // cost assuming the block is the head of the loop chain. When the loop ends,
1348 // we should have found the best candidate as the loop chain's head.
1349 for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()),
1350 EndIter = LoopChain.end();
1351 Iter != EndIter; Iter++, TailIter++) {
1352 // TailIter is used to track the tail of the loop chain if the block we are
1353 // checking (pointed by Iter) is the head of the chain.
1354 if (TailIter == LoopChain.end())
1355 TailIter = LoopChain.begin();
1357 auto TailBB = *TailIter;
1359 // Calculate the cost by putting this BB to the top.
1360 BlockFrequency Cost = 0;
1362 // If the current BB is the loop header, we need to take into account the
1363 // cost of the missed fall through edge from outside of the loop to the
1365 if (Iter != HeaderIter)
1366 Cost += HeaderFallThroughCost;
1368 // Collect the loop exit cost by summing up frequencies of all exit edges
1369 // except the one from the chain tail.
1370 for (auto &ExitWithFreq : ExitsWithFreq)
1371 if (TailBB != ExitWithFreq.first)
1372 Cost += ExitWithFreq.second;
1374 // The cost of breaking the once fall-through edge from the tail to the top
1375 // of the loop chain. Here we need to consider three cases:
1376 // 1. If the tail node has only one successor, then we will get an
1377 // additional jmp instruction. So the cost here is (MisfetchCost +
1378 // JumpInstCost) * tail node frequency.
1379 // 2. If the tail node has two successors, then we may still get an
1380 // additional jmp instruction if the layout successor after the loop
1381 // chain is not its CFG successor. Note that the more frequently executed
1382 // jmp instruction will be put ahead of the other one. Assume the
1383 // frequency of those two branches are x and y, where x is the frequency
1384 // of the edge to the chain head, then the cost will be
1385 // (x * MisfetechCost + min(x, y) * JumpInstCost) * tail node frequency.
1386 // 3. If the tail node has more than two successors (this rarely happens),
1387 // we won't consider any additional cost.
1388 if (TailBB->isSuccessor(*Iter)) {
1389 auto TailBBFreq = MBFI->getBlockFreq(TailBB);
1390 if (TailBB->succ_size() == 1)
1391 Cost += ScaleBlockFrequency(TailBBFreq.getFrequency(),
1392 MisfetchCost + JumpInstCost);
1393 else if (TailBB->succ_size() == 2) {
1394 auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter);
1395 auto TailToHeadFreq = TailBBFreq * TailToHeadProb;
1396 auto ColderEdgeFreq = TailToHeadProb > BranchProbability(1, 2)
1397 ? TailBBFreq * TailToHeadProb.getCompl()
1399 Cost += ScaleBlockFrequency(TailToHeadFreq, MisfetchCost) +
1400 ScaleBlockFrequency(ColderEdgeFreq, JumpInstCost);
1404 DEBUG(dbgs() << "The cost of loop rotation by making " << getBlockName(*Iter)
1405 << " to the top: " << Cost.getFrequency() << "\n");
1407 if (Cost < SmallestRotationCost) {
1408 SmallestRotationCost = Cost;
1413 if (RotationPos != LoopChain.end()) {
1414 DEBUG(dbgs() << "Rotate loop by making " << getBlockName(*RotationPos)
1415 << " to the top\n");
1416 std::rotate(LoopChain.begin(), RotationPos, LoopChain.end());
1420 /// \brief Collect blocks in the given loop that are to be placed.
1422 /// When profile data is available, exclude cold blocks from the returned set;
1423 /// otherwise, collect all blocks in the loop.
1424 MachineBlockPlacement::BlockFilterSet
1425 MachineBlockPlacement::collectLoopBlockSet(MachineLoop &L) {
1426 BlockFilterSet LoopBlockSet;
1428 // Filter cold blocks off from LoopBlockSet when profile data is available.
1429 // Collect the sum of frequencies of incoming edges to the loop header from
1430 // outside. If we treat the loop as a super block, this is the frequency of
1431 // the loop. Then for each block in the loop, we calculate the ratio between
1432 // its frequency and the frequency of the loop block. When it is too small,
1433 // don't add it to the loop chain. If there are outer loops, then this block
1434 // will be merged into the first outer loop chain for which this block is not
1435 // cold anymore. This needs precise profile data and we only do this when
1436 // profile data is available.
1437 if (F->getFunction()->getEntryCount()) {
1438 BlockFrequency LoopFreq(0);
1439 for (auto LoopPred : L.getHeader()->predecessors())
1440 if (!L.contains(LoopPred))
1441 LoopFreq += MBFI->getBlockFreq(LoopPred) *
1442 MBPI->getEdgeProbability(LoopPred, L.getHeader());
1444 for (MachineBasicBlock *LoopBB : L.getBlocks()) {
1445 auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency();
1446 if (Freq == 0 || LoopFreq.getFrequency() / Freq > LoopToColdBlockRatio)
1448 LoopBlockSet.insert(LoopBB);
1451 LoopBlockSet.insert(L.block_begin(), L.block_end());
1453 return LoopBlockSet;
1456 /// \brief Forms basic block chains from the natural loop structures.
1458 /// These chains are designed to preserve the existing *structure* of the code
1459 /// as much as possible. We can then stitch the chains together in a way which
1460 /// both preserves the topological structure and minimizes taken conditional
1462 void MachineBlockPlacement::buildLoopChains(MachineLoop &L) {
1463 // First recurse through any nested loops, building chains for those inner
1465 for (MachineLoop *InnerLoop : L)
1466 buildLoopChains(*InnerLoop);
1468 assert(BlockWorkList.empty());
1469 assert(EHPadWorkList.empty());
1470 BlockFilterSet LoopBlockSet = collectLoopBlockSet(L);
1472 // Check if we have profile data for this function. If yes, we will rotate
1473 // this loop by modeling costs more precisely which requires the profile data
1474 // for better layout.
1475 bool RotateLoopWithProfile =
1476 ForcePreciseRotationCost ||
1477 (PreciseRotationCost && F->getFunction()->getEntryCount());
1479 // First check to see if there is an obviously preferable top block for the
1480 // loop. This will default to the header, but may end up as one of the
1481 // predecessors to the header if there is one which will result in strictly
1482 // fewer branches in the loop body.
1483 // When we use profile data to rotate the loop, this is unnecessary.
1484 MachineBasicBlock *LoopTop =
1485 RotateLoopWithProfile ? L.getHeader() : findBestLoopTop(L, LoopBlockSet);
1487 // If we selected just the header for the loop top, look for a potentially
1488 // profitable exit block in the event that rotating the loop can eliminate
1489 // branches by placing an exit edge at the bottom.
1490 if (!RotateLoopWithProfile && LoopTop == L.getHeader())
1491 PreferredLoopExit = findBestLoopExit(L, LoopBlockSet);
1493 BlockChain &LoopChain = *BlockToChain[LoopTop];
1495 // FIXME: This is a really lame way of walking the chains in the loop: we
1496 // walk the blocks, and use a set to prevent visiting a particular chain
1498 SmallPtrSet<BlockChain *, 4> UpdatedPreds;
1499 assert(LoopChain.UnscheduledPredecessors == 0);
1500 UpdatedPreds.insert(&LoopChain);
1502 for (MachineBasicBlock *LoopBB : LoopBlockSet)
1503 fillWorkLists(LoopBB, UpdatedPreds, &LoopBlockSet);
1505 buildChain(LoopTop, LoopChain, &LoopBlockSet);
1507 if (RotateLoopWithProfile)
1508 rotateLoopWithProfile(LoopChain, L, LoopBlockSet);
1510 rotateLoop(LoopChain, PreferredLoopExit, LoopBlockSet);
1513 // Crash at the end so we get all of the debugging output first.
1514 bool BadLoop = false;
1515 if (LoopChain.UnscheduledPredecessors) {
1517 dbgs() << "Loop chain contains a block without its preds placed!\n"
1518 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
1519 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
1521 for (MachineBasicBlock *ChainBB : LoopChain) {
1522 dbgs() << " ... " << getBlockName(ChainBB) << "\n";
1523 if (!LoopBlockSet.remove(ChainBB)) {
1524 // We don't mark the loop as bad here because there are real situations
1525 // where this can occur. For example, with an unanalyzable fallthrough
1526 // from a loop block to a non-loop block or vice versa.
1527 dbgs() << "Loop chain contains a block not contained by the loop!\n"
1528 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
1529 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
1530 << " Bad block: " << getBlockName(ChainBB) << "\n";
1534 if (!LoopBlockSet.empty()) {
1536 for (MachineBasicBlock *LoopBB : LoopBlockSet)
1537 dbgs() << "Loop contains blocks never placed into a chain!\n"
1538 << " Loop header: " << getBlockName(*L.block_begin()) << "\n"
1539 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
1540 << " Bad block: " << getBlockName(LoopBB) << "\n";
1542 assert(!BadLoop && "Detected problems with the placement of this loop.");
1545 BlockWorkList.clear();
1546 EHPadWorkList.clear();
1549 /// When OutlineOpitonalBranches is on, this method collects BBs that
1550 /// dominates all terminator blocks of the function \p F.
1551 void MachineBlockPlacement::collectMustExecuteBBs() {
1552 if (OutlineOptionalBranches) {
1553 // Find the nearest common dominator of all of F's terminators.
1554 MachineBasicBlock *Terminator = nullptr;
1555 for (MachineBasicBlock &MBB : *F) {
1556 if (MBB.succ_size() == 0) {
1557 if (Terminator == nullptr)
1560 Terminator = MDT->findNearestCommonDominator(Terminator, &MBB);
1564 // MBBs dominating this common dominator are unavoidable.
1565 UnavoidableBlocks.clear();
1566 for (MachineBasicBlock &MBB : *F) {
1567 if (MDT->dominates(&MBB, Terminator)) {
1568 UnavoidableBlocks.insert(&MBB);
1574 void MachineBlockPlacement::buildCFGChains() {
1575 // Ensure that every BB in the function has an associated chain to simplify
1576 // the assumptions of the remaining algorithm.
1577 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
1578 for (MachineFunction::iterator FI = F->begin(), FE = F->end(); FI != FE;
1580 MachineBasicBlock *BB = &*FI;
1582 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
1583 // Also, merge any blocks which we cannot reason about and must preserve
1584 // the exact fallthrough behavior for.
1587 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
1588 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
1591 MachineFunction::iterator NextFI = std::next(FI);
1592 MachineBasicBlock *NextBB = &*NextFI;
1593 // Ensure that the layout successor is a viable block, as we know that
1594 // fallthrough is a possibility.
1595 assert(NextFI != FE && "Can't fallthrough past the last block.");
1596 DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: "
1597 << getBlockName(BB) << " -> " << getBlockName(NextBB)
1599 Chain->merge(NextBB, nullptr);
1601 BlocksWithUnanalyzableExits.insert(&*BB);
1608 // Turned on with OutlineOptionalBranches option
1609 collectMustExecuteBBs();
1611 // Build any loop-based chains.
1612 PreferredLoopExit = nullptr;
1613 for (MachineLoop *L : *MLI)
1614 buildLoopChains(*L);
1616 assert(BlockWorkList.empty());
1617 assert(EHPadWorkList.empty());
1619 SmallPtrSet<BlockChain *, 4> UpdatedPreds;
1620 for (MachineBasicBlock &MBB : *F)
1621 fillWorkLists(&MBB, UpdatedPreds);
1623 BlockChain &FunctionChain = *BlockToChain[&F->front()];
1624 buildChain(&F->front(), FunctionChain);
1627 typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
1630 // Crash at the end so we get all of the debugging output first.
1631 bool BadFunc = false;
1632 FunctionBlockSetType FunctionBlockSet;
1633 for (MachineBasicBlock &MBB : *F)
1634 FunctionBlockSet.insert(&MBB);
1636 for (MachineBasicBlock *ChainBB : FunctionChain)
1637 if (!FunctionBlockSet.erase(ChainBB)) {
1639 dbgs() << "Function chain contains a block not in the function!\n"
1640 << " Bad block: " << getBlockName(ChainBB) << "\n";
1643 if (!FunctionBlockSet.empty()) {
1645 for (MachineBasicBlock *RemainingBB : FunctionBlockSet)
1646 dbgs() << "Function contains blocks never placed into a chain!\n"
1647 << " Bad block: " << getBlockName(RemainingBB) << "\n";
1649 assert(!BadFunc && "Detected problems with the block placement.");
1652 // Splice the blocks into place.
1653 MachineFunction::iterator InsertPos = F->begin();
1654 DEBUG(dbgs() << "[MBP] Function: "<< F->getName() << "\n");
1655 for (MachineBasicBlock *ChainBB : FunctionChain) {
1656 DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain "
1658 << getBlockName(ChainBB) << "\n");
1659 if (InsertPos != MachineFunction::iterator(ChainBB))
1660 F->splice(InsertPos, ChainBB);
1664 // Update the terminator of the previous block.
1665 if (ChainBB == *FunctionChain.begin())
1667 MachineBasicBlock *PrevBB = &*std::prev(MachineFunction::iterator(ChainBB));
1669 // FIXME: It would be awesome of updateTerminator would just return rather
1670 // than assert when the branch cannot be analyzed in order to remove this
1673 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
1676 if (!BlocksWithUnanalyzableExits.count(PrevBB)) {
1677 // Given the exact block placement we chose, we may actually not _need_ to
1678 // be able to edit PrevBB's terminator sequence, but not being _able_ to
1679 // do that at this point is a bug.
1680 assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
1681 !PrevBB->canFallThrough()) &&
1682 "Unexpected block with un-analyzable fallthrough!");
1684 TBB = FBB = nullptr;
1688 // The "PrevBB" is not yet updated to reflect current code layout, so,
1689 // o. it may fall-through to a block without explicit "goto" instruction
1690 // before layout, and no longer fall-through it after layout; or
1691 // o. just opposite.
1693 // analyzeBranch() may return erroneous value for FBB when these two
1694 // situations take place. For the first scenario FBB is mistakenly set NULL;
1695 // for the 2nd scenario, the FBB, which is expected to be NULL, is
1696 // mistakenly pointing to "*BI".
1697 // Thus, if the future change needs to use FBB before the layout is set, it
1698 // has to correct FBB first by using the code similar to the following:
1700 // if (!Cond.empty() && (!FBB || FBB == ChainBB)) {
1701 // PrevBB->updateTerminator();
1703 // TBB = FBB = nullptr;
1704 // if (TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) {
1705 // // FIXME: This should never take place.
1706 // TBB = FBB = nullptr;
1709 if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond))
1710 PrevBB->updateTerminator();
1713 // Fixup the last block.
1715 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
1716 if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond))
1717 F->back().updateTerminator();
1719 BlockWorkList.clear();
1720 EHPadWorkList.clear();
1723 void MachineBlockPlacement::optimizeBranches() {
1724 BlockChain &FunctionChain = *BlockToChain[&F->front()];
1725 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
1727 // Now that all the basic blocks in the chain have the proper layout,
1728 // make a final call to AnalyzeBranch with AllowModify set.
1729 // Indeed, the target may be able to optimize the branches in a way we
1730 // cannot because all branches may not be analyzable.
1731 // E.g., the target may be able to remove an unconditional branch to
1732 // a fallthrough when it occurs after predicated terminators.
1733 for (MachineBasicBlock *ChainBB : FunctionChain) {
1735 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
1736 if (!TII->analyzeBranch(*ChainBB, TBB, FBB, Cond, /*AllowModify*/ true)) {
1737 // If PrevBB has a two-way branch, try to re-order the branches
1738 // such that we branch to the successor with higher probability first.
1739 if (TBB && !Cond.empty() && FBB &&
1740 MBPI->getEdgeProbability(ChainBB, FBB) >
1741 MBPI->getEdgeProbability(ChainBB, TBB) &&
1742 !TII->reverseBranchCondition(Cond)) {
1743 DEBUG(dbgs() << "Reverse order of the two branches: "
1744 << getBlockName(ChainBB) << "\n");
1745 DEBUG(dbgs() << " Edge probability: "
1746 << MBPI->getEdgeProbability(ChainBB, FBB) << " vs "
1747 << MBPI->getEdgeProbability(ChainBB, TBB) << "\n");
1748 DebugLoc dl; // FIXME: this is nowhere
1749 TII->removeBranch(*ChainBB);
1750 TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl);
1751 ChainBB->updateTerminator();
1757 void MachineBlockPlacement::alignBlocks() {
1758 // Walk through the backedges of the function now that we have fully laid out
1759 // the basic blocks and align the destination of each backedge. We don't rely
1760 // exclusively on the loop info here so that we can align backedges in
1761 // unnatural CFGs and backedges that were introduced purely because of the
1762 // loop rotations done during this layout pass.
1763 if (F->getFunction()->optForSize())
1765 BlockChain &FunctionChain = *BlockToChain[&F->front()];
1766 if (FunctionChain.begin() == FunctionChain.end())
1767 return; // Empty chain.
1769 const BranchProbability ColdProb(1, 5); // 20%
1770 BlockFrequency EntryFreq = MBFI->getBlockFreq(&F->front());
1771 BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb;
1772 for (MachineBasicBlock *ChainBB : FunctionChain) {
1773 if (ChainBB == *FunctionChain.begin())
1776 // Don't align non-looping basic blocks. These are unlikely to execute
1777 // enough times to matter in practice. Note that we'll still handle
1778 // unnatural CFGs inside of a natural outer loop (the common case) and
1780 MachineLoop *L = MLI->getLoopFor(ChainBB);
1784 unsigned Align = TLI->getPrefLoopAlignment(L);
1786 continue; // Don't care about loop alignment.
1788 // If the block is cold relative to the function entry don't waste space
1790 BlockFrequency Freq = MBFI->getBlockFreq(ChainBB);
1791 if (Freq < WeightedEntryFreq)
1794 // If the block is cold relative to its loop header, don't align it
1795 // regardless of what edges into the block exist.
1796 MachineBasicBlock *LoopHeader = L->getHeader();
1797 BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader);
1798 if (Freq < (LoopHeaderFreq * ColdProb))
1801 // Check for the existence of a non-layout predecessor which would benefit
1802 // from aligning this block.
1803 MachineBasicBlock *LayoutPred =
1804 &*std::prev(MachineFunction::iterator(ChainBB));
1806 // Force alignment if all the predecessors are jumps. We already checked
1807 // that the block isn't cold above.
1808 if (!LayoutPred->isSuccessor(ChainBB)) {
1809 ChainBB->setAlignment(Align);
1813 // Align this block if the layout predecessor's edge into this block is
1814 // cold relative to the block. When this is true, other predecessors make up
1815 // all of the hot entries into the block and thus alignment is likely to be
1817 BranchProbability LayoutProb =
1818 MBPI->getEdgeProbability(LayoutPred, ChainBB);
1819 BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb;
1820 if (LayoutEdgeFreq <= (Freq * ColdProb))
1821 ChainBB->setAlignment(Align);
1825 /// Tail duplicate \p BB into (some) predecessors if profitable, repeating if
1826 /// it was duplicated into its chain predecessor and removed.
1827 /// \p BB - Basic block that may be duplicated.
1829 /// \p LPred - Chosen layout predecessor of \p BB.
1830 /// Updated to be the chain end if LPred is removed.
1831 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
1832 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
1833 /// Used to identify which blocks to update predecessor
1835 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
1836 /// chosen in the given order due to unnatural CFG
1837 /// only needed if \p BB is removed and
1838 /// \p PrevUnplacedBlockIt pointed to \p BB.
1839 /// @return true if \p BB was removed.
1840 bool MachineBlockPlacement::repeatedlyTailDuplicateBlock(
1841 MachineBasicBlock *BB, MachineBasicBlock *&LPred,
1842 MachineBasicBlock *LoopHeaderBB,
1843 BlockChain &Chain, BlockFilterSet *BlockFilter,
1844 MachineFunction::iterator &PrevUnplacedBlockIt) {
1845 bool Removed, DuplicatedToLPred;
1846 bool DuplicatedToOriginalLPred;
1847 Removed = maybeTailDuplicateBlock(BB, LPred, Chain, BlockFilter,
1848 PrevUnplacedBlockIt,
1852 DuplicatedToOriginalLPred = DuplicatedToLPred;
1853 // Iteratively try to duplicate again. It can happen that a block that is
1854 // duplicated into is still small enough to be duplicated again.
1855 // No need to call markBlockSuccessors in this case, as the blocks being
1856 // duplicated from here on are already scheduled.
1857 // Note that DuplicatedToLPred always implies Removed.
1858 while (DuplicatedToLPred) {
1859 assert (Removed && "Block must have been removed to be duplicated into its "
1860 "layout predecessor.");
1861 MachineBasicBlock *DupBB, *DupPred;
1862 // The removal callback causes Chain.end() to be updated when a block is
1863 // removed. On the first pass through the loop, the chain end should be the
1864 // same as it was on function entry. On subsequent passes, because we are
1865 // duplicating the block at the end of the chain, if it is removed the
1866 // chain will have shrunk by one block.
1867 BlockChain::iterator ChainEnd = Chain.end();
1868 DupBB = *(--ChainEnd);
1869 // Now try to duplicate again.
1870 if (ChainEnd == Chain.begin())
1872 DupPred = *std::prev(ChainEnd);
1873 Removed = maybeTailDuplicateBlock(DupBB, DupPred, Chain, BlockFilter,
1874 PrevUnplacedBlockIt,
1877 // If BB was duplicated into LPred, it is now scheduled. But because it was
1878 // removed, markChainSuccessors won't be called for its chain. Instead we
1879 // call markBlockSuccessors for LPred to achieve the same effect. This must go
1880 // at the end because repeating the tail duplication can increase the number
1881 // of unscheduled predecessors.
1882 LPred = *std::prev(Chain.end());
1883 if (DuplicatedToOriginalLPred)
1884 markBlockSuccessors(Chain, LPred, LoopHeaderBB, BlockFilter);
1888 /// Tail duplicate \p BB into (some) predecessors if profitable.
1889 /// \p BB - Basic block that may be duplicated
1890 /// \p LPred - Chosen layout predecessor of \p BB
1891 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
1892 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
1893 /// Used to identify which blocks to update predecessor
1895 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
1896 /// chosen in the given order due to unnatural CFG
1897 /// only needed if \p BB is removed and
1898 /// \p PrevUnplacedBlockIt pointed to \p BB.
1899 /// \p DuplicatedToLPred - True if the block was duplicated into LPred. Will
1900 /// only be true if the block was removed.
1901 /// \return - True if the block was duplicated into all preds and removed.
1902 bool MachineBlockPlacement::maybeTailDuplicateBlock(
1903 MachineBasicBlock *BB, MachineBasicBlock *LPred,
1904 const BlockChain &Chain, BlockFilterSet *BlockFilter,
1905 MachineFunction::iterator &PrevUnplacedBlockIt,
1906 bool &DuplicatedToLPred) {
1908 DuplicatedToLPred = false;
1909 DEBUG(dbgs() << "Redoing tail duplication for Succ#"
1910 << BB->getNumber() << "\n");
1911 bool IsSimple = TailDup.isSimpleBB(BB);
1912 // Blocks with single successors don't create additional fallthrough
1913 // opportunities. Don't duplicate them. TODO: When conditional exits are
1914 // analyzable, allow them to be duplicated.
1915 if (!IsSimple && BB->succ_size() == 1)
1917 if (!TailDup.shouldTailDuplicate(IsSimple, *BB))
1919 // This has to be a callback because none of it can be done after
1921 bool Removed = false;
1922 auto RemovalCallback =
1923 [&](MachineBasicBlock *RemBB) {
1924 // Signal to outer function
1927 // Conservative default.
1928 bool InWorkList = true;
1929 // Remove from the Chain and Chain Map
1930 if (BlockToChain.count(RemBB)) {
1931 BlockChain *Chain = BlockToChain[RemBB];
1932 InWorkList = Chain->UnscheduledPredecessors == 0;
1933 Chain->remove(RemBB);
1934 BlockToChain.erase(RemBB);
1937 // Handle the unplaced block iterator
1938 if (&(*PrevUnplacedBlockIt) == RemBB) {
1939 PrevUnplacedBlockIt++;
1942 // Handle the Work Lists
1944 SmallVectorImpl<MachineBasicBlock *> &RemoveList = BlockWorkList;
1945 if (RemBB->isEHPad())
1946 RemoveList = EHPadWorkList;
1948 remove_if(RemoveList,
1949 [RemBB](MachineBasicBlock *BB) {return BB == RemBB;}),
1953 // Handle the filter set
1955 BlockFilter->remove(RemBB);
1958 // Remove the block from loop info.
1959 MLI->removeBlock(RemBB);
1960 if (RemBB == PreferredLoopExit)
1961 PreferredLoopExit = nullptr;
1963 DEBUG(dbgs() << "TailDuplicator deleted block: "
1964 << getBlockName(RemBB) << "\n");
1966 auto RemovalCallbackRef =
1967 llvm::function_ref<void(MachineBasicBlock*)>(RemovalCallback);
1969 SmallVector<MachineBasicBlock *, 8> DuplicatedPreds;
1970 TailDup.tailDuplicateAndUpdate(IsSimple, BB, LPred,
1971 &DuplicatedPreds, &RemovalCallbackRef);
1973 // Update UnscheduledPredecessors to reflect tail-duplication.
1974 DuplicatedToLPred = false;
1975 for (MachineBasicBlock *Pred : DuplicatedPreds) {
1976 // We're only looking for unscheduled predecessors that match the filter.
1977 BlockChain* PredChain = BlockToChain[Pred];
1979 DuplicatedToLPred = true;
1980 if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred))
1981 || PredChain == &Chain)
1983 for (MachineBasicBlock *NewSucc : Pred->successors()) {
1984 if (BlockFilter && !BlockFilter->count(NewSucc))
1986 BlockChain *NewChain = BlockToChain[NewSucc];
1987 if (NewChain != &Chain && NewChain != PredChain)
1988 NewChain->UnscheduledPredecessors++;
1994 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
1995 if (skipFunction(*MF.getFunction()))
1998 // Check for single-block functions and skip them.
1999 if (std::next(MF.begin()) == MF.end())
2003 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
2004 MBFI = llvm::make_unique<BranchFolder::MBFIWrapper>(
2005 getAnalysis<MachineBlockFrequencyInfo>());
2006 MLI = &getAnalysis<MachineLoopInfo>();
2007 TII = MF.getSubtarget().getInstrInfo();
2008 TLI = MF.getSubtarget().getTargetLowering();
2009 MDT = &getAnalysis<MachineDominatorTree>();
2011 // Initialize PreferredLoopExit to nullptr here since it may never be set if
2012 // there are no MachineLoops.
2013 PreferredLoopExit = nullptr;
2015 if (TailDupPlacement) {
2016 unsigned TailDupSize = TailDuplicatePlacementThreshold;
2017 if (MF.getFunction()->optForSize())
2019 TailDup.initMF(MF, MBPI, /* LayoutMode */ true, TailDupSize);
2022 assert(BlockToChain.empty());
2026 // Changing the layout can create new tail merging opportunities.
2027 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
2028 // TailMerge can create jump into if branches that make CFG irreducible for
2029 // HW that requires structured CFG.
2030 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
2031 PassConfig->getEnableTailMerge() &&
2032 BranchFoldPlacement;
2033 // No tail merging opportunities if the block number is less than four.
2034 if (MF.size() > 3 && EnableTailMerge) {
2035 unsigned TailMergeSize = TailDuplicatePlacementThreshold + 1;
2036 BranchFolder BF(/*EnableTailMerge=*/true, /*CommonHoist=*/false, *MBFI,
2037 *MBPI, TailMergeSize);
2039 if (BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(),
2040 getAnalysisIfAvailable<MachineModuleInfo>(), MLI,
2041 /*AfterBlockPlacement=*/true)) {
2042 // Redo the layout if tail merging creates/removes/moves blocks.
2043 BlockToChain.clear();
2044 // Must redo the dominator tree if blocks were changed.
2045 MDT->runOnMachineFunction(MF);
2046 ChainAllocator.DestroyAll();
2054 BlockToChain.clear();
2055 ChainAllocator.DestroyAll();
2058 // Align all of the blocks in the function to a specific alignment.
2059 for (MachineBasicBlock &MBB : MF)
2060 MBB.setAlignment(AlignAllBlock);
2061 else if (AlignAllNonFallThruBlocks) {
2062 // Align all of the blocks that have no fall-through predecessors to a
2063 // specific alignment.
2064 for (auto MBI = std::next(MF.begin()), MBE = MF.end(); MBI != MBE; ++MBI) {
2065 auto LayoutPred = std::prev(MBI);
2066 if (!LayoutPred->isSuccessor(&*MBI))
2067 MBI->setAlignment(AlignAllNonFallThruBlocks);
2071 // We always return true as we have no way to track whether the final order
2072 // differs from the original order.
2077 /// \brief A pass to compute block placement statistics.
2079 /// A separate pass to compute interesting statistics for evaluating block
2080 /// placement. This is separate from the actual placement pass so that they can
2081 /// be computed in the absence of any placement transformations or when using
2082 /// alternative placement strategies.
2083 class MachineBlockPlacementStats : public MachineFunctionPass {
2084 /// \brief A handle to the branch probability pass.
2085 const MachineBranchProbabilityInfo *MBPI;
2087 /// \brief A handle to the function-wide block frequency pass.
2088 const MachineBlockFrequencyInfo *MBFI;
2091 static char ID; // Pass identification, replacement for typeid
2092 MachineBlockPlacementStats() : MachineFunctionPass(ID) {
2093 initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
2096 bool runOnMachineFunction(MachineFunction &F) override;
2098 void getAnalysisUsage(AnalysisUsage &AU) const override {
2099 AU.addRequired<MachineBranchProbabilityInfo>();
2100 AU.addRequired<MachineBlockFrequencyInfo>();
2101 AU.setPreservesAll();
2102 MachineFunctionPass::getAnalysisUsage(AU);
2107 char MachineBlockPlacementStats::ID = 0;
2108 char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID;
2109 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
2110 "Basic Block Placement Stats", false, false)
2111 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
2112 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
2113 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
2114 "Basic Block Placement Stats", false, false)
2116 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
2117 // Check for single-block functions and skip them.
2118 if (std::next(F.begin()) == F.end())
2121 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
2122 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2124 for (MachineBasicBlock &MBB : F) {
2125 BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
2126 Statistic &NumBranches =
2127 (MBB.succ_size() > 1) ? NumCondBranches : NumUncondBranches;
2128 Statistic &BranchTakenFreq =
2129 (MBB.succ_size() > 1) ? CondBranchTakenFreq : UncondBranchTakenFreq;
2130 for (MachineBasicBlock *Succ : MBB.successors()) {
2131 // Skip if this successor is a fallthrough.
2132 if (MBB.isLayoutSuccessor(Succ))
2135 BlockFrequency EdgeFreq =
2136 BlockFreq * MBPI->getEdgeProbability(&MBB, Succ);
2138 BranchTakenFreq += EdgeFreq.getFrequency();