xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/MachineBlockPlacement.cpp (revision c7a063741720ef81d4caa4613242579d12f1d605)
1 //===- MachineBlockPlacement.cpp - Basic Block Code Layout optimization ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements basic block placement transformations using the CFG
10 // structure and branch probability estimates.
11 //
12 // The pass strives to preserve the structure of the CFG (that is, retain
13 // a topological ordering of basic blocks) in the absence of a *strong* signal
14 // to the contrary from probabilities. However, within the CFG structure, it
15 // attempts to choose an ordering which favors placing more likely sequences of
16 // blocks adjacent to each other.
17 //
18 // The algorithm works from the inner-most loop within a function outward, and
19 // at each stage walks through the basic blocks, trying to coalesce them into
20 // sequential chains where allowed by the CFG (or demanded by heavy
21 // probabilities). Finally, it walks the blocks in topological order, and the
22 // first time it reaches a chain of basic blocks, it schedules them in the
23 // function in-order.
24 //
25 //===----------------------------------------------------------------------===//
26 
27 #include "BranchFolding.h"
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SetVector.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/Analysis/ProfileSummaryInfo.h"
37 #include "llvm/CodeGen/MachineBasicBlock.h"
38 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
39 #include "llvm/CodeGen/MachineBranchProbabilityInfo.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/MachineSizeOpts.h"
46 #include "llvm/CodeGen/TailDuplicator.h"
47 #include "llvm/CodeGen/TargetInstrInfo.h"
48 #include "llvm/CodeGen/TargetLowering.h"
49 #include "llvm/CodeGen/TargetPassConfig.h"
50 #include "llvm/CodeGen/TargetSubtargetInfo.h"
51 #include "llvm/IR/DebugLoc.h"
52 #include "llvm/IR/Function.h"
53 #include "llvm/InitializePasses.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Support/Allocator.h"
56 #include "llvm/Support/BlockFrequency.h"
57 #include "llvm/Support/BranchProbability.h"
58 #include "llvm/Support/CodeGen.h"
59 #include "llvm/Support/CommandLine.h"
60 #include "llvm/Support/Compiler.h"
61 #include "llvm/Support/Debug.h"
62 #include "llvm/Support/raw_ostream.h"
63 #include "llvm/Target/TargetMachine.h"
64 #include "llvm/Transforms/Utils/CodeLayout.h"
65 #include <algorithm>
66 #include <cassert>
67 #include <cstdint>
68 #include <iterator>
69 #include <memory>
70 #include <string>
71 #include <tuple>
72 #include <utility>
73 #include <vector>
74 
75 using namespace llvm;
76 
77 #define DEBUG_TYPE "block-placement"
78 
79 STATISTIC(NumCondBranches, "Number of conditional branches");
80 STATISTIC(NumUncondBranches, "Number of unconditional branches");
81 STATISTIC(CondBranchTakenFreq,
82           "Potential frequency of taking conditional branches");
83 STATISTIC(UncondBranchTakenFreq,
84           "Potential frequency of taking unconditional branches");
85 
86 static cl::opt<unsigned> AlignAllBlock(
87     "align-all-blocks",
88     cl::desc("Force the alignment of all blocks in the function in log2 format "
89              "(e.g 4 means align on 16B boundaries)."),
90     cl::init(0), cl::Hidden);
91 
92 static cl::opt<unsigned> AlignAllNonFallThruBlocks(
93     "align-all-nofallthru-blocks",
94     cl::desc("Force the alignment of all blocks that have no fall-through "
95              "predecessors (i.e. don't add nops that are executed). In log2 "
96              "format (e.g 4 means align on 16B boundaries)."),
97     cl::init(0), cl::Hidden);
98 
99 static cl::opt<unsigned> MaxBytesForAlignmentOverride(
100     "max-bytes-for-alignment",
101     cl::desc("Forces the maximum bytes allowed to be emitted when padding for "
102              "alignment"),
103     cl::init(0), cl::Hidden);
104 
105 // FIXME: Find a good default for this flag and remove the flag.
106 static cl::opt<unsigned> ExitBlockBias(
107     "block-placement-exit-block-bias",
108     cl::desc("Block frequency percentage a loop exit block needs "
109              "over the original exit to be considered the new exit."),
110     cl::init(0), cl::Hidden);
111 
112 // Definition:
113 // - Outlining: placement of a basic block outside the chain or hot path.
114 
115 static cl::opt<unsigned> LoopToColdBlockRatio(
116     "loop-to-cold-block-ratio",
117     cl::desc("Outline loop blocks from loop chain if (frequency of loop) / "
118              "(frequency of block) is greater than this ratio"),
119     cl::init(5), cl::Hidden);
120 
121 static cl::opt<bool> ForceLoopColdBlock(
122     "force-loop-cold-block",
123     cl::desc("Force outlining cold blocks from loops."),
124     cl::init(false), cl::Hidden);
125 
126 static cl::opt<bool>
127     PreciseRotationCost("precise-rotation-cost",
128                         cl::desc("Model the cost of loop rotation more "
129                                  "precisely by using profile data."),
130                         cl::init(false), cl::Hidden);
131 
132 static cl::opt<bool>
133     ForcePreciseRotationCost("force-precise-rotation-cost",
134                              cl::desc("Force the use of precise cost "
135                                       "loop rotation strategy."),
136                              cl::init(false), cl::Hidden);
137 
138 static cl::opt<unsigned> MisfetchCost(
139     "misfetch-cost",
140     cl::desc("Cost that models the probabilistic risk of an instruction "
141              "misfetch due to a jump comparing to falling through, whose cost "
142              "is zero."),
143     cl::init(1), cl::Hidden);
144 
145 static cl::opt<unsigned> JumpInstCost("jump-inst-cost",
146                                       cl::desc("Cost of jump instructions."),
147                                       cl::init(1), cl::Hidden);
148 static cl::opt<bool>
149 TailDupPlacement("tail-dup-placement",
150               cl::desc("Perform tail duplication during placement. "
151                        "Creates more fallthrough opportunites in "
152                        "outline branches."),
153               cl::init(true), cl::Hidden);
154 
155 static cl::opt<bool>
156 BranchFoldPlacement("branch-fold-placement",
157               cl::desc("Perform branch folding during placement. "
158                        "Reduces code size."),
159               cl::init(true), cl::Hidden);
160 
161 // Heuristic for tail duplication.
162 static cl::opt<unsigned> TailDupPlacementThreshold(
163     "tail-dup-placement-threshold",
164     cl::desc("Instruction cutoff for tail duplication during layout. "
165              "Tail merging during layout is forced to have a threshold "
166              "that won't conflict."), cl::init(2),
167     cl::Hidden);
168 
169 // Heuristic for aggressive tail duplication.
170 static cl::opt<unsigned> TailDupPlacementAggressiveThreshold(
171     "tail-dup-placement-aggressive-threshold",
172     cl::desc("Instruction cutoff for aggressive tail duplication during "
173              "layout. Used at -O3. Tail merging during layout is forced to "
174              "have a threshold that won't conflict."), cl::init(4),
175     cl::Hidden);
176 
177 // Heuristic for tail duplication.
178 static cl::opt<unsigned> TailDupPlacementPenalty(
179     "tail-dup-placement-penalty",
180     cl::desc("Cost penalty for blocks that can avoid breaking CFG by copying. "
181              "Copying can increase fallthrough, but it also increases icache "
182              "pressure. This parameter controls the penalty to account for that. "
183              "Percent as integer."),
184     cl::init(2),
185     cl::Hidden);
186 
187 // Heuristic for tail duplication if profile count is used in cost model.
188 static cl::opt<unsigned> TailDupProfilePercentThreshold(
189     "tail-dup-profile-percent-threshold",
190     cl::desc("If profile count information is used in tail duplication cost "
191              "model, the gained fall through number from tail duplication "
192              "should be at least this percent of hot count."),
193     cl::init(50), cl::Hidden);
194 
195 // Heuristic for triangle chains.
196 static cl::opt<unsigned> TriangleChainCount(
197     "triangle-chain-count",
198     cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the "
199              "triangle tail duplication heuristic to kick in. 0 to disable."),
200     cl::init(2),
201     cl::Hidden);
202 
203 static cl::opt<bool> EnableExtTspBlockPlacement(
204     "enable-ext-tsp-block-placement", cl::Hidden, cl::init(false),
205     cl::desc("Enable machine block placement based on the ext-tsp model, "
206              "optimizing I-cache utilization."));
207 
208 namespace llvm {
209 extern cl::opt<unsigned> StaticLikelyProb;
210 extern cl::opt<unsigned> ProfileLikelyProb;
211 
212 // Internal option used to control BFI display only after MBP pass.
213 // Defined in CodeGen/MachineBlockFrequencyInfo.cpp:
214 // -view-block-layout-with-bfi=
215 extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI;
216 
217 // Command line option to specify the name of the function for CFG dump
218 // Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
219 extern cl::opt<std::string> ViewBlockFreqFuncName;
220 } // namespace llvm
221 
222 namespace {
223 
224 class BlockChain;
225 
226 /// Type for our function-wide basic block -> block chain mapping.
227 using BlockToChainMapType = DenseMap<const MachineBasicBlock *, BlockChain *>;
228 
229 /// A chain of blocks which will be laid out contiguously.
230 ///
231 /// This is the datastructure representing a chain of consecutive blocks that
232 /// are profitable to layout together in order to maximize fallthrough
233 /// probabilities and code locality. We also can use a block chain to represent
234 /// a sequence of basic blocks which have some external (correctness)
235 /// requirement for sequential layout.
236 ///
237 /// Chains can be built around a single basic block and can be merged to grow
238 /// them. They participate in a block-to-chain mapping, which is updated
239 /// automatically as chains are merged together.
240 class BlockChain {
241   /// The sequence of blocks belonging to this chain.
242   ///
243   /// This is the sequence of blocks for a particular chain. These will be laid
244   /// out in-order within the function.
245   SmallVector<MachineBasicBlock *, 4> Blocks;
246 
247   /// A handle to the function-wide basic block to block chain mapping.
248   ///
249   /// This is retained in each block chain to simplify the computation of child
250   /// block chains for SCC-formation and iteration. We store the edges to child
251   /// basic blocks, and map them back to their associated chains using this
252   /// structure.
253   BlockToChainMapType &BlockToChain;
254 
255 public:
256   /// Construct a new BlockChain.
257   ///
258   /// This builds a new block chain representing a single basic block in the
259   /// function. It also registers itself as the chain that block participates
260   /// in with the BlockToChain mapping.
261   BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
262       : Blocks(1, BB), BlockToChain(BlockToChain) {
263     assert(BB && "Cannot create a chain with a null basic block");
264     BlockToChain[BB] = this;
265   }
266 
267   /// Iterator over blocks within the chain.
268   using iterator = SmallVectorImpl<MachineBasicBlock *>::iterator;
269   using const_iterator = SmallVectorImpl<MachineBasicBlock *>::const_iterator;
270 
271   /// Beginning of blocks within the chain.
272   iterator begin() { return Blocks.begin(); }
273   const_iterator begin() const { return Blocks.begin(); }
274 
275   /// End of blocks within the chain.
276   iterator end() { return Blocks.end(); }
277   const_iterator end() const { return Blocks.end(); }
278 
279   bool remove(MachineBasicBlock* BB) {
280     for(iterator i = begin(); i != end(); ++i) {
281       if (*i == BB) {
282         Blocks.erase(i);
283         return true;
284       }
285     }
286     return false;
287   }
288 
289   /// Merge a block chain into this one.
290   ///
291   /// This routine merges a block chain into this one. It takes care of forming
292   /// a contiguous sequence of basic blocks, updating the edge list, and
293   /// updating the block -> chain mapping. It does not free or tear down the
294   /// old chain, but the old chain's block list is no longer valid.
295   void merge(MachineBasicBlock *BB, BlockChain *Chain) {
296     assert(BB && "Can't merge a null block.");
297     assert(!Blocks.empty() && "Can't merge into an empty chain.");
298 
299     // Fast path in case we don't have a chain already.
300     if (!Chain) {
301       assert(!BlockToChain[BB] &&
302              "Passed chain is null, but BB has entry in BlockToChain.");
303       Blocks.push_back(BB);
304       BlockToChain[BB] = this;
305       return;
306     }
307 
308     assert(BB == *Chain->begin() && "Passed BB is not head of Chain.");
309     assert(Chain->begin() != Chain->end());
310 
311     // Update the incoming blocks to point to this chain, and add them to the
312     // chain structure.
313     for (MachineBasicBlock *ChainBB : *Chain) {
314       Blocks.push_back(ChainBB);
315       assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain.");
316       BlockToChain[ChainBB] = this;
317     }
318   }
319 
320 #ifndef NDEBUG
321   /// Dump the blocks in this chain.
322   LLVM_DUMP_METHOD void dump() {
323     for (MachineBasicBlock *MBB : *this)
324       MBB->dump();
325   }
326 #endif // NDEBUG
327 
328   /// Count of predecessors of any block within the chain which have not
329   /// yet been scheduled.  In general, we will delay scheduling this chain
330   /// until those predecessors are scheduled (or we find a sufficiently good
331   /// reason to override this heuristic.)  Note that when forming loop chains,
332   /// blocks outside the loop are ignored and treated as if they were already
333   /// scheduled.
334   ///
335   /// Note: This field is reinitialized multiple times - once for each loop,
336   /// and then once for the function as a whole.
337   unsigned UnscheduledPredecessors = 0;
338 };
339 
340 class MachineBlockPlacement : public MachineFunctionPass {
341   /// A type for a block filter set.
342   using BlockFilterSet = SmallSetVector<const MachineBasicBlock *, 16>;
343 
344   /// Pair struct containing basic block and taildup profitability
345   struct BlockAndTailDupResult {
346     MachineBasicBlock *BB;
347     bool ShouldTailDup;
348   };
349 
350   /// Triple struct containing edge weight and the edge.
351   struct WeightedEdge {
352     BlockFrequency Weight;
353     MachineBasicBlock *Src;
354     MachineBasicBlock *Dest;
355   };
356 
357   /// work lists of blocks that are ready to be laid out
358   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
359   SmallVector<MachineBasicBlock *, 16> EHPadWorkList;
360 
361   /// Edges that have already been computed as optimal.
362   DenseMap<const MachineBasicBlock *, BlockAndTailDupResult> ComputedEdges;
363 
364   /// Machine Function
365   MachineFunction *F;
366 
367   /// A handle to the branch probability pass.
368   const MachineBranchProbabilityInfo *MBPI;
369 
370   /// A handle to the function-wide block frequency pass.
371   std::unique_ptr<MBFIWrapper> MBFI;
372 
373   /// A handle to the loop info.
374   MachineLoopInfo *MLI;
375 
376   /// Preferred loop exit.
377   /// Member variable for convenience. It may be removed by duplication deep
378   /// in the call stack.
379   MachineBasicBlock *PreferredLoopExit;
380 
381   /// A handle to the target's instruction info.
382   const TargetInstrInfo *TII;
383 
384   /// A handle to the target's lowering info.
385   const TargetLoweringBase *TLI;
386 
387   /// A handle to the post dominator tree.
388   MachinePostDominatorTree *MPDT;
389 
390   ProfileSummaryInfo *PSI;
391 
392   /// Duplicator used to duplicate tails during placement.
393   ///
394   /// Placement decisions can open up new tail duplication opportunities, but
395   /// since tail duplication affects placement decisions of later blocks, it
396   /// must be done inline.
397   TailDuplicator TailDup;
398 
399   /// Partial tail duplication threshold.
400   BlockFrequency DupThreshold;
401 
402   /// True:  use block profile count to compute tail duplication cost.
403   /// False: use block frequency to compute tail duplication cost.
404   bool UseProfileCount;
405 
406   /// Allocator and owner of BlockChain structures.
407   ///
408   /// We build BlockChains lazily while processing the loop structure of
409   /// a function. To reduce malloc traffic, we allocate them using this
410   /// slab-like allocator, and destroy them after the pass completes. An
411   /// important guarantee is that this allocator produces stable pointers to
412   /// the chains.
413   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
414 
415   /// Function wide BasicBlock to BlockChain mapping.
416   ///
417   /// This mapping allows efficiently moving from any given basic block to the
418   /// BlockChain it participates in, if any. We use it to, among other things,
419   /// allow implicitly defining edges between chains as the existing edges
420   /// between basic blocks.
421   DenseMap<const MachineBasicBlock *, BlockChain *> BlockToChain;
422 
423 #ifndef NDEBUG
424   /// The set of basic blocks that have terminators that cannot be fully
425   /// analyzed.  These basic blocks cannot be re-ordered safely by
426   /// MachineBlockPlacement, and we must preserve physical layout of these
427   /// blocks and their successors through the pass.
428   SmallPtrSet<MachineBasicBlock *, 4> BlocksWithUnanalyzableExits;
429 #endif
430 
431   /// Get block profile count or frequency according to UseProfileCount.
432   /// The return value is used to model tail duplication cost.
433   BlockFrequency getBlockCountOrFrequency(const MachineBasicBlock *BB) {
434     if (UseProfileCount) {
435       auto Count = MBFI->getBlockProfileCount(BB);
436       if (Count)
437         return *Count;
438       else
439         return 0;
440     } else
441       return MBFI->getBlockFreq(BB);
442   }
443 
444   /// Scale the DupThreshold according to basic block size.
445   BlockFrequency scaleThreshold(MachineBasicBlock *BB);
446   void initDupThreshold();
447 
448   /// Decrease the UnscheduledPredecessors count for all blocks in chain, and
449   /// if the count goes to 0, add them to the appropriate work list.
450   void markChainSuccessors(
451       const BlockChain &Chain, const MachineBasicBlock *LoopHeaderBB,
452       const BlockFilterSet *BlockFilter = nullptr);
453 
454   /// Decrease the UnscheduledPredecessors count for a single block, and
455   /// if the count goes to 0, add them to the appropriate work list.
456   void markBlockSuccessors(
457       const BlockChain &Chain, const MachineBasicBlock *BB,
458       const MachineBasicBlock *LoopHeaderBB,
459       const BlockFilterSet *BlockFilter = nullptr);
460 
461   BranchProbability
462   collectViableSuccessors(
463       const MachineBasicBlock *BB, const BlockChain &Chain,
464       const BlockFilterSet *BlockFilter,
465       SmallVector<MachineBasicBlock *, 4> &Successors);
466   bool isBestSuccessor(MachineBasicBlock *BB, MachineBasicBlock *Pred,
467                        BlockFilterSet *BlockFilter);
468   void findDuplicateCandidates(SmallVectorImpl<MachineBasicBlock *> &Candidates,
469                                MachineBasicBlock *BB,
470                                BlockFilterSet *BlockFilter);
471   bool repeatedlyTailDuplicateBlock(
472       MachineBasicBlock *BB, MachineBasicBlock *&LPred,
473       const MachineBasicBlock *LoopHeaderBB,
474       BlockChain &Chain, BlockFilterSet *BlockFilter,
475       MachineFunction::iterator &PrevUnplacedBlockIt);
476   bool maybeTailDuplicateBlock(
477       MachineBasicBlock *BB, MachineBasicBlock *LPred,
478       BlockChain &Chain, BlockFilterSet *BlockFilter,
479       MachineFunction::iterator &PrevUnplacedBlockIt,
480       bool &DuplicatedToLPred);
481   bool hasBetterLayoutPredecessor(
482       const MachineBasicBlock *BB, const MachineBasicBlock *Succ,
483       const BlockChain &SuccChain, BranchProbability SuccProb,
484       BranchProbability RealSuccProb, const BlockChain &Chain,
485       const BlockFilterSet *BlockFilter);
486   BlockAndTailDupResult selectBestSuccessor(
487       const MachineBasicBlock *BB, const BlockChain &Chain,
488       const BlockFilterSet *BlockFilter);
489   MachineBasicBlock *selectBestCandidateBlock(
490       const BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList);
491   MachineBasicBlock *getFirstUnplacedBlock(
492       const BlockChain &PlacedChain,
493       MachineFunction::iterator &PrevUnplacedBlockIt,
494       const BlockFilterSet *BlockFilter);
495 
496   /// Add a basic block to the work list if it is appropriate.
497   ///
498   /// If the optional parameter BlockFilter is provided, only MBB
499   /// present in the set will be added to the worklist. If nullptr
500   /// is provided, no filtering occurs.
501   void fillWorkLists(const MachineBasicBlock *MBB,
502                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
503                      const BlockFilterSet *BlockFilter);
504 
505   void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
506                   BlockFilterSet *BlockFilter = nullptr);
507   bool canMoveBottomBlockToTop(const MachineBasicBlock *BottomBlock,
508                                const MachineBasicBlock *OldTop);
509   bool hasViableTopFallthrough(const MachineBasicBlock *Top,
510                                const BlockFilterSet &LoopBlockSet);
511   BlockFrequency TopFallThroughFreq(const MachineBasicBlock *Top,
512                                     const BlockFilterSet &LoopBlockSet);
513   BlockFrequency FallThroughGains(const MachineBasicBlock *NewTop,
514                                   const MachineBasicBlock *OldTop,
515                                   const MachineBasicBlock *ExitBB,
516                                   const BlockFilterSet &LoopBlockSet);
517   MachineBasicBlock *findBestLoopTopHelper(MachineBasicBlock *OldTop,
518       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
519   MachineBasicBlock *findBestLoopTop(
520       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
521   MachineBasicBlock *findBestLoopExit(
522       const MachineLoop &L, const BlockFilterSet &LoopBlockSet,
523       BlockFrequency &ExitFreq);
524   BlockFilterSet collectLoopBlockSet(const MachineLoop &L);
525   void buildLoopChains(const MachineLoop &L);
526   void rotateLoop(
527       BlockChain &LoopChain, const MachineBasicBlock *ExitingBB,
528       BlockFrequency ExitFreq, const BlockFilterSet &LoopBlockSet);
529   void rotateLoopWithProfile(
530       BlockChain &LoopChain, const MachineLoop &L,
531       const BlockFilterSet &LoopBlockSet);
532   void buildCFGChains();
533   void optimizeBranches();
534   void alignBlocks();
535   /// Returns true if a block should be tail-duplicated to increase fallthrough
536   /// opportunities.
537   bool shouldTailDuplicate(MachineBasicBlock *BB);
538   /// Check the edge frequencies to see if tail duplication will increase
539   /// fallthroughs.
540   bool isProfitableToTailDup(
541     const MachineBasicBlock *BB, const MachineBasicBlock *Succ,
542     BranchProbability QProb,
543     const BlockChain &Chain, const BlockFilterSet *BlockFilter);
544 
545   /// Check for a trellis layout.
546   bool isTrellis(const MachineBasicBlock *BB,
547                  const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
548                  const BlockChain &Chain, const BlockFilterSet *BlockFilter);
549 
550   /// Get the best successor given a trellis layout.
551   BlockAndTailDupResult getBestTrellisSuccessor(
552       const MachineBasicBlock *BB,
553       const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
554       BranchProbability AdjustedSumProb, const BlockChain &Chain,
555       const BlockFilterSet *BlockFilter);
556 
557   /// Get the best pair of non-conflicting edges.
558   static std::pair<WeightedEdge, WeightedEdge> getBestNonConflictingEdges(
559       const MachineBasicBlock *BB,
560       MutableArrayRef<SmallVector<WeightedEdge, 8>> Edges);
561 
562   /// Returns true if a block can tail duplicate into all unplaced
563   /// predecessors. Filters based on loop.
564   bool canTailDuplicateUnplacedPreds(
565       const MachineBasicBlock *BB, MachineBasicBlock *Succ,
566       const BlockChain &Chain, const BlockFilterSet *BlockFilter);
567 
568   /// Find chains of triangles to tail-duplicate where a global analysis works,
569   /// but a local analysis would not find them.
570   void precomputeTriangleChains();
571 
572   /// Apply a post-processing step optimizing block placement.
573   void applyExtTsp();
574 
575   /// Modify the existing block placement in the function and adjust all jumps.
576   void assignBlockOrder(const std::vector<const MachineBasicBlock *> &NewOrder);
577 
578   /// Create a single CFG chain from the current block order.
579   void createCFGChainExtTsp();
580 
581 public:
582   static char ID; // Pass identification, replacement for typeid
583 
584   MachineBlockPlacement() : MachineFunctionPass(ID) {
585     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
586   }
587 
588   bool runOnMachineFunction(MachineFunction &F) override;
589 
590   bool allowTailDupPlacement() const {
591     assert(F);
592     return TailDupPlacement && !F->getTarget().requiresStructuredCFG();
593   }
594 
595   void getAnalysisUsage(AnalysisUsage &AU) const override {
596     AU.addRequired<MachineBranchProbabilityInfo>();
597     AU.addRequired<MachineBlockFrequencyInfo>();
598     if (TailDupPlacement)
599       AU.addRequired<MachinePostDominatorTree>();
600     AU.addRequired<MachineLoopInfo>();
601     AU.addRequired<ProfileSummaryInfoWrapperPass>();
602     AU.addRequired<TargetPassConfig>();
603     MachineFunctionPass::getAnalysisUsage(AU);
604   }
605 };
606 
607 } // end anonymous namespace
608 
609 char MachineBlockPlacement::ID = 0;
610 
611 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
612 
613 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, DEBUG_TYPE,
614                       "Branch Probability Basic Block Placement", false, false)
615 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
616 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
617 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
618 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
619 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
620 INITIALIZE_PASS_END(MachineBlockPlacement, DEBUG_TYPE,
621                     "Branch Probability Basic Block Placement", false, false)
622 
623 #ifndef NDEBUG
624 /// Helper to print the name of a MBB.
625 ///
626 /// Only used by debug logging.
627 static std::string getBlockName(const MachineBasicBlock *BB) {
628   std::string Result;
629   raw_string_ostream OS(Result);
630   OS << printMBBReference(*BB);
631   OS << " ('" << BB->getName() << "')";
632   OS.flush();
633   return Result;
634 }
635 #endif
636 
637 /// Mark a chain's successors as having one fewer preds.
638 ///
639 /// When a chain is being merged into the "placed" chain, this routine will
640 /// quickly walk the successors of each block in the chain and mark them as
641 /// having one fewer active predecessor. It also adds any successors of this
642 /// chain which reach the zero-predecessor state to the appropriate worklist.
643 void MachineBlockPlacement::markChainSuccessors(
644     const BlockChain &Chain, const MachineBasicBlock *LoopHeaderBB,
645     const BlockFilterSet *BlockFilter) {
646   // Walk all the blocks in this chain, marking their successors as having
647   // a predecessor placed.
648   for (MachineBasicBlock *MBB : Chain) {
649     markBlockSuccessors(Chain, MBB, LoopHeaderBB, BlockFilter);
650   }
651 }
652 
653 /// Mark a single block's successors as having one fewer preds.
654 ///
655 /// Under normal circumstances, this is only called by markChainSuccessors,
656 /// but if a block that was to be placed is completely tail-duplicated away,
657 /// and was duplicated into the chain end, we need to redo markBlockSuccessors
658 /// for just that block.
659 void MachineBlockPlacement::markBlockSuccessors(
660     const BlockChain &Chain, const MachineBasicBlock *MBB,
661     const MachineBasicBlock *LoopHeaderBB, const BlockFilterSet *BlockFilter) {
662   // Add any successors for which this is the only un-placed in-loop
663   // predecessor to the worklist as a viable candidate for CFG-neutral
664   // placement. No subsequent placement of this block will violate the CFG
665   // shape, so we get to use heuristics to choose a favorable placement.
666   for (MachineBasicBlock *Succ : MBB->successors()) {
667     if (BlockFilter && !BlockFilter->count(Succ))
668       continue;
669     BlockChain &SuccChain = *BlockToChain[Succ];
670     // Disregard edges within a fixed chain, or edges to the loop header.
671     if (&Chain == &SuccChain || Succ == LoopHeaderBB)
672       continue;
673 
674     // This is a cross-chain edge that is within the loop, so decrement the
675     // loop predecessor count of the destination chain.
676     if (SuccChain.UnscheduledPredecessors == 0 ||
677         --SuccChain.UnscheduledPredecessors > 0)
678       continue;
679 
680     auto *NewBB = *SuccChain.begin();
681     if (NewBB->isEHPad())
682       EHPadWorkList.push_back(NewBB);
683     else
684       BlockWorkList.push_back(NewBB);
685   }
686 }
687 
688 /// This helper function collects the set of successors of block
689 /// \p BB that are allowed to be its layout successors, and return
690 /// the total branch probability of edges from \p BB to those
691 /// blocks.
692 BranchProbability MachineBlockPlacement::collectViableSuccessors(
693     const MachineBasicBlock *BB, const BlockChain &Chain,
694     const BlockFilterSet *BlockFilter,
695     SmallVector<MachineBasicBlock *, 4> &Successors) {
696   // Adjust edge probabilities by excluding edges pointing to blocks that is
697   // either not in BlockFilter or is already in the current chain. Consider the
698   // following CFG:
699   //
700   //     --->A
701   //     |  / \
702   //     | B   C
703   //     |  \ / \
704   //     ----D   E
705   //
706   // Assume A->C is very hot (>90%), and C->D has a 50% probability, then after
707   // A->C is chosen as a fall-through, D won't be selected as a successor of C
708   // due to CFG constraint (the probability of C->D is not greater than
709   // HotProb to break topo-order). If we exclude E that is not in BlockFilter
710   // when calculating the probability of C->D, D will be selected and we
711   // will get A C D B as the layout of this loop.
712   auto AdjustedSumProb = BranchProbability::getOne();
713   for (MachineBasicBlock *Succ : BB->successors()) {
714     bool SkipSucc = false;
715     if (Succ->isEHPad() || (BlockFilter && !BlockFilter->count(Succ))) {
716       SkipSucc = true;
717     } else {
718       BlockChain *SuccChain = BlockToChain[Succ];
719       if (SuccChain == &Chain) {
720         SkipSucc = true;
721       } else if (Succ != *SuccChain->begin()) {
722         LLVM_DEBUG(dbgs() << "    " << getBlockName(Succ)
723                           << " -> Mid chain!\n");
724         continue;
725       }
726     }
727     if (SkipSucc)
728       AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ);
729     else
730       Successors.push_back(Succ);
731   }
732 
733   return AdjustedSumProb;
734 }
735 
736 /// The helper function returns the branch probability that is adjusted
737 /// or normalized over the new total \p AdjustedSumProb.
738 static BranchProbability
739 getAdjustedProbability(BranchProbability OrigProb,
740                        BranchProbability AdjustedSumProb) {
741   BranchProbability SuccProb;
742   uint32_t SuccProbN = OrigProb.getNumerator();
743   uint32_t SuccProbD = AdjustedSumProb.getNumerator();
744   if (SuccProbN >= SuccProbD)
745     SuccProb = BranchProbability::getOne();
746   else
747     SuccProb = BranchProbability(SuccProbN, SuccProbD);
748 
749   return SuccProb;
750 }
751 
752 /// Check if \p BB has exactly the successors in \p Successors.
753 static bool
754 hasSameSuccessors(MachineBasicBlock &BB,
755                   SmallPtrSetImpl<const MachineBasicBlock *> &Successors) {
756   if (BB.succ_size() != Successors.size())
757     return false;
758   // We don't want to count self-loops
759   if (Successors.count(&BB))
760     return false;
761   for (MachineBasicBlock *Succ : BB.successors())
762     if (!Successors.count(Succ))
763       return false;
764   return true;
765 }
766 
767 /// Check if a block should be tail duplicated to increase fallthrough
768 /// opportunities.
769 /// \p BB Block to check.
770 bool MachineBlockPlacement::shouldTailDuplicate(MachineBasicBlock *BB) {
771   // Blocks with single successors don't create additional fallthrough
772   // opportunities. Don't duplicate them. TODO: When conditional exits are
773   // analyzable, allow them to be duplicated.
774   bool IsSimple = TailDup.isSimpleBB(BB);
775 
776   if (BB->succ_size() == 1)
777     return false;
778   return TailDup.shouldTailDuplicate(IsSimple, *BB);
779 }
780 
781 /// Compare 2 BlockFrequency's with a small penalty for \p A.
782 /// In order to be conservative, we apply a X% penalty to account for
783 /// increased icache pressure and static heuristics. For small frequencies
784 /// we use only the numerators to improve accuracy. For simplicity, we assume the
785 /// penalty is less than 100%
786 /// TODO(iteratee): Use 64-bit fixed point edge frequencies everywhere.
787 static bool greaterWithBias(BlockFrequency A, BlockFrequency B,
788                             uint64_t EntryFreq) {
789   BranchProbability ThresholdProb(TailDupPlacementPenalty, 100);
790   BlockFrequency Gain = A - B;
791   return (Gain / ThresholdProb).getFrequency() >= EntryFreq;
792 }
793 
794 /// Check the edge frequencies to see if tail duplication will increase
795 /// fallthroughs. It only makes sense to call this function when
796 /// \p Succ would not be chosen otherwise. Tail duplication of \p Succ is
797 /// always locally profitable if we would have picked \p Succ without
798 /// considering duplication.
799 bool MachineBlockPlacement::isProfitableToTailDup(
800     const MachineBasicBlock *BB, const MachineBasicBlock *Succ,
801     BranchProbability QProb,
802     const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
803   // We need to do a probability calculation to make sure this is profitable.
804   // First: does succ have a successor that post-dominates? This affects the
805   // calculation. The 2 relevant cases are:
806   //    BB         BB
807   //    | \Qout    | \Qout
808   //   P|  C       |P C
809   //    =   C'     =   C'
810   //    |  /Qin    |  /Qin
811   //    | /        | /
812   //    Succ       Succ
813   //    / \        | \  V
814   //  U/   =V      |U \
815   //  /     \      =   D
816   //  D      E     |  /
817   //               | /
818   //               |/
819   //               PDom
820   //  '=' : Branch taken for that CFG edge
821   // In the second case, Placing Succ while duplicating it into C prevents the
822   // fallthrough of Succ into either D or PDom, because they now have C as an
823   // unplaced predecessor
824 
825   // Start by figuring out which case we fall into
826   MachineBasicBlock *PDom = nullptr;
827   SmallVector<MachineBasicBlock *, 4> SuccSuccs;
828   // Only scan the relevant successors
829   auto AdjustedSuccSumProb =
830       collectViableSuccessors(Succ, Chain, BlockFilter, SuccSuccs);
831   BranchProbability PProb = MBPI->getEdgeProbability(BB, Succ);
832   auto BBFreq = MBFI->getBlockFreq(BB);
833   auto SuccFreq = MBFI->getBlockFreq(Succ);
834   BlockFrequency P = BBFreq * PProb;
835   BlockFrequency Qout = BBFreq * QProb;
836   uint64_t EntryFreq = MBFI->getEntryFreq();
837   // If there are no more successors, it is profitable to copy, as it strictly
838   // increases fallthrough.
839   if (SuccSuccs.size() == 0)
840     return greaterWithBias(P, Qout, EntryFreq);
841 
842   auto BestSuccSucc = BranchProbability::getZero();
843   // Find the PDom or the best Succ if no PDom exists.
844   for (MachineBasicBlock *SuccSucc : SuccSuccs) {
845     auto Prob = MBPI->getEdgeProbability(Succ, SuccSucc);
846     if (Prob > BestSuccSucc)
847       BestSuccSucc = Prob;
848     if (PDom == nullptr)
849       if (MPDT->dominates(SuccSucc, Succ)) {
850         PDom = SuccSucc;
851         break;
852       }
853   }
854   // For the comparisons, we need to know Succ's best incoming edge that isn't
855   // from BB.
856   auto SuccBestPred = BlockFrequency(0);
857   for (MachineBasicBlock *SuccPred : Succ->predecessors()) {
858     if (SuccPred == Succ || SuccPred == BB
859         || BlockToChain[SuccPred] == &Chain
860         || (BlockFilter && !BlockFilter->count(SuccPred)))
861       continue;
862     auto Freq = MBFI->getBlockFreq(SuccPred)
863         * MBPI->getEdgeProbability(SuccPred, Succ);
864     if (Freq > SuccBestPred)
865       SuccBestPred = Freq;
866   }
867   // Qin is Succ's best unplaced incoming edge that isn't BB
868   BlockFrequency Qin = SuccBestPred;
869   // If it doesn't have a post-dominating successor, here is the calculation:
870   //    BB        BB
871   //    | \Qout   |  \
872   //   P|  C      |   =
873   //    =   C'    |    C
874   //    |  /Qin   |     |
875   //    | /       |     C' (+Succ)
876   //    Succ      Succ /|
877   //    / \       |  \/ |
878   //  U/   =V     |  == |
879   //  /     \     | /  \|
880   //  D      E    D     E
881   //  '=' : Branch taken for that CFG edge
882   //  Cost in the first case is: P + V
883   //  For this calculation, we always assume P > Qout. If Qout > P
884   //  The result of this function will be ignored at the caller.
885   //  Let F = SuccFreq - Qin
886   //  Cost in the second case is: Qout + min(Qin, F) * U + max(Qin, F) * V
887 
888   if (PDom == nullptr || !Succ->isSuccessor(PDom)) {
889     BranchProbability UProb = BestSuccSucc;
890     BranchProbability VProb = AdjustedSuccSumProb - UProb;
891     BlockFrequency F = SuccFreq - Qin;
892     BlockFrequency V = SuccFreq * VProb;
893     BlockFrequency QinU = std::min(Qin, F) * UProb;
894     BlockFrequency BaseCost = P + V;
895     BlockFrequency DupCost = Qout + QinU + std::max(Qin, F) * VProb;
896     return greaterWithBias(BaseCost, DupCost, EntryFreq);
897   }
898   BranchProbability UProb = MBPI->getEdgeProbability(Succ, PDom);
899   BranchProbability VProb = AdjustedSuccSumProb - UProb;
900   BlockFrequency U = SuccFreq * UProb;
901   BlockFrequency V = SuccFreq * VProb;
902   BlockFrequency F = SuccFreq - Qin;
903   // If there is a post-dominating successor, here is the calculation:
904   // BB         BB                 BB          BB
905   // | \Qout    |   \               | \Qout     |  \
906   // |P C       |    =              |P C        |   =
907   // =   C'     |P    C             =   C'      |P   C
908   // |  /Qin    |      |            |  /Qin     |     |
909   // | /        |      C' (+Succ)   | /         |     C' (+Succ)
910   // Succ       Succ  /|            Succ        Succ /|
911   // | \  V     |   \/ |            | \  V      |  \/ |
912   // |U \       |U  /\ =?           |U =        |U /\ |
913   // =   D      = =  =?|            |   D       | =  =|
914   // |  /       |/     D            |  /        |/    D
915   // | /        |     /             | =         |    /
916   // |/         |    /              |/          |   =
917   // Dom         Dom                Dom         Dom
918   //  '=' : Branch taken for that CFG edge
919   // The cost for taken branches in the first case is P + U
920   // Let F = SuccFreq - Qin
921   // The cost in the second case (assuming independence), given the layout:
922   // BB, Succ, (C+Succ), D, Dom or the layout:
923   // BB, Succ, D, Dom, (C+Succ)
924   // is Qout + max(F, Qin) * U + min(F, Qin)
925   // compare P + U vs Qout + P * U + Qin.
926   //
927   // The 3rd and 4th cases cover when Dom would be chosen to follow Succ.
928   //
929   // For the 3rd case, the cost is P + 2 * V
930   // For the 4th case, the cost is Qout + min(Qin, F) * U + max(Qin, F) * V + V
931   // We choose 4 over 3 when (P + V) > Qout + min(Qin, F) * U + max(Qin, F) * V
932   if (UProb > AdjustedSuccSumProb / 2 &&
933       !hasBetterLayoutPredecessor(Succ, PDom, *BlockToChain[PDom], UProb, UProb,
934                                   Chain, BlockFilter))
935     // Cases 3 & 4
936     return greaterWithBias(
937         (P + V), (Qout + std::max(Qin, F) * VProb + std::min(Qin, F) * UProb),
938         EntryFreq);
939   // Cases 1 & 2
940   return greaterWithBias((P + U),
941                          (Qout + std::min(Qin, F) * AdjustedSuccSumProb +
942                           std::max(Qin, F) * UProb),
943                          EntryFreq);
944 }
945 
946 /// Check for a trellis layout. \p BB is the upper part of a trellis if its
947 /// successors form the lower part of a trellis. A successor set S forms the
948 /// lower part of a trellis if all of the predecessors of S are either in S or
949 /// have all of S as successors. We ignore trellises where BB doesn't have 2
950 /// successors because for fewer than 2, it's trivial, and for 3 or greater they
951 /// are very uncommon and complex to compute optimally. Allowing edges within S
952 /// is not strictly a trellis, but the same algorithm works, so we allow it.
953 bool MachineBlockPlacement::isTrellis(
954     const MachineBasicBlock *BB,
955     const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
956     const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
957   // Technically BB could form a trellis with branching factor higher than 2.
958   // But that's extremely uncommon.
959   if (BB->succ_size() != 2 || ViableSuccs.size() != 2)
960     return false;
961 
962   SmallPtrSet<const MachineBasicBlock *, 2> Successors(BB->succ_begin(),
963                                                        BB->succ_end());
964   // To avoid reviewing the same predecessors twice.
965   SmallPtrSet<const MachineBasicBlock *, 8> SeenPreds;
966 
967   for (MachineBasicBlock *Succ : ViableSuccs) {
968     int PredCount = 0;
969     for (auto SuccPred : Succ->predecessors()) {
970       // Allow triangle successors, but don't count them.
971       if (Successors.count(SuccPred)) {
972         // Make sure that it is actually a triangle.
973         for (MachineBasicBlock *CheckSucc : SuccPred->successors())
974           if (!Successors.count(CheckSucc))
975             return false;
976         continue;
977       }
978       const BlockChain *PredChain = BlockToChain[SuccPred];
979       if (SuccPred == BB || (BlockFilter && !BlockFilter->count(SuccPred)) ||
980           PredChain == &Chain || PredChain == BlockToChain[Succ])
981         continue;
982       ++PredCount;
983       // Perform the successor check only once.
984       if (!SeenPreds.insert(SuccPred).second)
985         continue;
986       if (!hasSameSuccessors(*SuccPred, Successors))
987         return false;
988     }
989     // If one of the successors has only BB as a predecessor, it is not a
990     // trellis.
991     if (PredCount < 1)
992       return false;
993   }
994   return true;
995 }
996 
997 /// Pick the highest total weight pair of edges that can both be laid out.
998 /// The edges in \p Edges[0] are assumed to have a different destination than
999 /// the edges in \p Edges[1]. Simple counting shows that the best pair is either
1000 /// the individual highest weight edges to the 2 different destinations, or in
1001 /// case of a conflict, one of them should be replaced with a 2nd best edge.
1002 std::pair<MachineBlockPlacement::WeightedEdge,
1003           MachineBlockPlacement::WeightedEdge>
1004 MachineBlockPlacement::getBestNonConflictingEdges(
1005     const MachineBasicBlock *BB,
1006     MutableArrayRef<SmallVector<MachineBlockPlacement::WeightedEdge, 8>>
1007         Edges) {
1008   // Sort the edges, and then for each successor, find the best incoming
1009   // predecessor. If the best incoming predecessors aren't the same,
1010   // then that is clearly the best layout. If there is a conflict, one of the
1011   // successors will have to fallthrough from the second best predecessor. We
1012   // compare which combination is better overall.
1013 
1014   // Sort for highest frequency.
1015   auto Cmp = [](WeightedEdge A, WeightedEdge B) { return A.Weight > B.Weight; };
1016 
1017   llvm::stable_sort(Edges[0], Cmp);
1018   llvm::stable_sort(Edges[1], Cmp);
1019   auto BestA = Edges[0].begin();
1020   auto BestB = Edges[1].begin();
1021   // Arrange for the correct answer to be in BestA and BestB
1022   // If the 2 best edges don't conflict, the answer is already there.
1023   if (BestA->Src == BestB->Src) {
1024     // Compare the total fallthrough of (Best + Second Best) for both pairs
1025     auto SecondBestA = std::next(BestA);
1026     auto SecondBestB = std::next(BestB);
1027     BlockFrequency BestAScore = BestA->Weight + SecondBestB->Weight;
1028     BlockFrequency BestBScore = BestB->Weight + SecondBestA->Weight;
1029     if (BestAScore < BestBScore)
1030       BestA = SecondBestA;
1031     else
1032       BestB = SecondBestB;
1033   }
1034   // Arrange for the BB edge to be in BestA if it exists.
1035   if (BestB->Src == BB)
1036     std::swap(BestA, BestB);
1037   return std::make_pair(*BestA, *BestB);
1038 }
1039 
1040 /// Get the best successor from \p BB based on \p BB being part of a trellis.
1041 /// We only handle trellises with 2 successors, so the algorithm is
1042 /// straightforward: Find the best pair of edges that don't conflict. We find
1043 /// the best incoming edge for each successor in the trellis. If those conflict,
1044 /// we consider which of them should be replaced with the second best.
1045 /// Upon return the two best edges will be in \p BestEdges. If one of the edges
1046 /// comes from \p BB, it will be in \p BestEdges[0]
1047 MachineBlockPlacement::BlockAndTailDupResult
1048 MachineBlockPlacement::getBestTrellisSuccessor(
1049     const MachineBasicBlock *BB,
1050     const SmallVectorImpl<MachineBasicBlock *> &ViableSuccs,
1051     BranchProbability AdjustedSumProb, const BlockChain &Chain,
1052     const BlockFilterSet *BlockFilter) {
1053 
1054   BlockAndTailDupResult Result = {nullptr, false};
1055   SmallPtrSet<const MachineBasicBlock *, 4> Successors(BB->succ_begin(),
1056                                                        BB->succ_end());
1057 
1058   // We assume size 2 because it's common. For general n, we would have to do
1059   // the Hungarian algorithm, but it's not worth the complexity because more
1060   // than 2 successors is fairly uncommon, and a trellis even more so.
1061   if (Successors.size() != 2 || ViableSuccs.size() != 2)
1062     return Result;
1063 
1064   // Collect the edge frequencies of all edges that form the trellis.
1065   SmallVector<WeightedEdge, 8> Edges[2];
1066   int SuccIndex = 0;
1067   for (auto Succ : ViableSuccs) {
1068     for (MachineBasicBlock *SuccPred : Succ->predecessors()) {
1069       // Skip any placed predecessors that are not BB
1070       if (SuccPred != BB)
1071         if ((BlockFilter && !BlockFilter->count(SuccPred)) ||
1072             BlockToChain[SuccPred] == &Chain ||
1073             BlockToChain[SuccPred] == BlockToChain[Succ])
1074           continue;
1075       BlockFrequency EdgeFreq = MBFI->getBlockFreq(SuccPred) *
1076                                 MBPI->getEdgeProbability(SuccPred, Succ);
1077       Edges[SuccIndex].push_back({EdgeFreq, SuccPred, Succ});
1078     }
1079     ++SuccIndex;
1080   }
1081 
1082   // Pick the best combination of 2 edges from all the edges in the trellis.
1083   WeightedEdge BestA, BestB;
1084   std::tie(BestA, BestB) = getBestNonConflictingEdges(BB, Edges);
1085 
1086   if (BestA.Src != BB) {
1087     // If we have a trellis, and BB doesn't have the best fallthrough edges,
1088     // we shouldn't choose any successor. We've already looked and there's a
1089     // better fallthrough edge for all the successors.
1090     LLVM_DEBUG(dbgs() << "Trellis, but not one of the chosen edges.\n");
1091     return Result;
1092   }
1093 
1094   // Did we pick the triangle edge? If tail-duplication is profitable, do
1095   // that instead. Otherwise merge the triangle edge now while we know it is
1096   // optimal.
1097   if (BestA.Dest == BestB.Src) {
1098     // The edges are BB->Succ1->Succ2, and we're looking to see if BB->Succ2
1099     // would be better.
1100     MachineBasicBlock *Succ1 = BestA.Dest;
1101     MachineBasicBlock *Succ2 = BestB.Dest;
1102     // Check to see if tail-duplication would be profitable.
1103     if (allowTailDupPlacement() && shouldTailDuplicate(Succ2) &&
1104         canTailDuplicateUnplacedPreds(BB, Succ2, Chain, BlockFilter) &&
1105         isProfitableToTailDup(BB, Succ2, MBPI->getEdgeProbability(BB, Succ1),
1106                               Chain, BlockFilter)) {
1107       LLVM_DEBUG(BranchProbability Succ2Prob = getAdjustedProbability(
1108                      MBPI->getEdgeProbability(BB, Succ2), AdjustedSumProb);
1109                  dbgs() << "    Selected: " << getBlockName(Succ2)
1110                         << ", probability: " << Succ2Prob
1111                         << " (Tail Duplicate)\n");
1112       Result.BB = Succ2;
1113       Result.ShouldTailDup = true;
1114       return Result;
1115     }
1116   }
1117   // We have already computed the optimal edge for the other side of the
1118   // trellis.
1119   ComputedEdges[BestB.Src] = { BestB.Dest, false };
1120 
1121   auto TrellisSucc = BestA.Dest;
1122   LLVM_DEBUG(BranchProbability SuccProb = getAdjustedProbability(
1123                  MBPI->getEdgeProbability(BB, TrellisSucc), AdjustedSumProb);
1124              dbgs() << "    Selected: " << getBlockName(TrellisSucc)
1125                     << ", probability: " << SuccProb << " (Trellis)\n");
1126   Result.BB = TrellisSucc;
1127   return Result;
1128 }
1129 
1130 /// When the option allowTailDupPlacement() is on, this method checks if the
1131 /// fallthrough candidate block \p Succ (of block \p BB) can be tail-duplicated
1132 /// into all of its unplaced, unfiltered predecessors, that are not BB.
1133 bool MachineBlockPlacement::canTailDuplicateUnplacedPreds(
1134     const MachineBasicBlock *BB, MachineBasicBlock *Succ,
1135     const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
1136   if (!shouldTailDuplicate(Succ))
1137     return false;
1138 
1139   // The result of canTailDuplicate.
1140   bool Duplicate = true;
1141   // Number of possible duplication.
1142   unsigned int NumDup = 0;
1143 
1144   // For CFG checking.
1145   SmallPtrSet<const MachineBasicBlock *, 4> Successors(BB->succ_begin(),
1146                                                        BB->succ_end());
1147   for (MachineBasicBlock *Pred : Succ->predecessors()) {
1148     // Make sure all unplaced and unfiltered predecessors can be
1149     // tail-duplicated into.
1150     // Skip any blocks that are already placed or not in this loop.
1151     if (Pred == BB || (BlockFilter && !BlockFilter->count(Pred))
1152         || BlockToChain[Pred] == &Chain)
1153       continue;
1154     if (!TailDup.canTailDuplicate(Succ, Pred)) {
1155       if (Successors.size() > 1 && hasSameSuccessors(*Pred, Successors))
1156         // This will result in a trellis after tail duplication, so we don't
1157         // need to copy Succ into this predecessor. In the presence
1158         // of a trellis tail duplication can continue to be profitable.
1159         // For example:
1160         // A            A
1161         // |\           |\
1162         // | \          | \
1163         // |  C         |  C+BB
1164         // | /          |  |
1165         // |/           |  |
1166         // BB    =>     BB |
1167         // |\           |\/|
1168         // | \          |/\|
1169         // |  D         |  D
1170         // | /          | /
1171         // |/           |/
1172         // Succ         Succ
1173         //
1174         // After BB was duplicated into C, the layout looks like the one on the
1175         // right. BB and C now have the same successors. When considering
1176         // whether Succ can be duplicated into all its unplaced predecessors, we
1177         // ignore C.
1178         // We can do this because C already has a profitable fallthrough, namely
1179         // D. TODO(iteratee): ignore sufficiently cold predecessors for
1180         // duplication and for this test.
1181         //
1182         // This allows trellises to be laid out in 2 separate chains
1183         // (A,B,Succ,...) and later (C,D,...) This is a reasonable heuristic
1184         // because it allows the creation of 2 fallthrough paths with links
1185         // between them, and we correctly identify the best layout for these
1186         // CFGs. We want to extend trellises that the user created in addition
1187         // to trellises created by tail-duplication, so we just look for the
1188         // CFG.
1189         continue;
1190       Duplicate = false;
1191       continue;
1192     }
1193     NumDup++;
1194   }
1195 
1196   // No possible duplication in current filter set.
1197   if (NumDup == 0)
1198     return false;
1199 
1200   // If profile information is available, findDuplicateCandidates can do more
1201   // precise benefit analysis.
1202   if (F->getFunction().hasProfileData())
1203     return true;
1204 
1205   // This is mainly for function exit BB.
1206   // The integrated tail duplication is really designed for increasing
1207   // fallthrough from predecessors from Succ to its successors. We may need
1208   // other machanism to handle different cases.
1209   if (Succ->succ_empty())
1210     return true;
1211 
1212   // Plus the already placed predecessor.
1213   NumDup++;
1214 
1215   // If the duplication candidate has more unplaced predecessors than
1216   // successors, the extra duplication can't bring more fallthrough.
1217   //
1218   //     Pred1 Pred2 Pred3
1219   //         \   |   /
1220   //          \  |  /
1221   //           \ | /
1222   //            Dup
1223   //            / \
1224   //           /   \
1225   //       Succ1  Succ2
1226   //
1227   // In this example Dup has 2 successors and 3 predecessors, duplication of Dup
1228   // can increase the fallthrough from Pred1 to Succ1 and from Pred2 to Succ2,
1229   // but the duplication into Pred3 can't increase fallthrough.
1230   //
1231   // A small number of extra duplication may not hurt too much. We need a better
1232   // heuristic to handle it.
1233   if ((NumDup > Succ->succ_size()) || !Duplicate)
1234     return false;
1235 
1236   return true;
1237 }
1238 
1239 /// Find chains of triangles where we believe it would be profitable to
1240 /// tail-duplicate them all, but a local analysis would not find them.
1241 /// There are 3 ways this can be profitable:
1242 /// 1) The post-dominators marked 50% are actually taken 55% (This shrinks with
1243 ///    longer chains)
1244 /// 2) The chains are statically correlated. Branch probabilities have a very
1245 ///    U-shaped distribution.
1246 ///    [http://nrs.harvard.edu/urn-3:HUL.InstRepos:24015805]
1247 ///    If the branches in a chain are likely to be from the same side of the
1248 ///    distribution as their predecessor, but are independent at runtime, this
1249 ///    transformation is profitable. (Because the cost of being wrong is a small
1250 ///    fixed cost, unlike the standard triangle layout where the cost of being
1251 ///    wrong scales with the # of triangles.)
1252 /// 3) The chains are dynamically correlated. If the probability that a previous
1253 ///    branch was taken positively influences whether the next branch will be
1254 ///    taken
1255 /// We believe that 2 and 3 are common enough to justify the small margin in 1.
1256 void MachineBlockPlacement::precomputeTriangleChains() {
1257   struct TriangleChain {
1258     std::vector<MachineBasicBlock *> Edges;
1259 
1260     TriangleChain(MachineBasicBlock *src, MachineBasicBlock *dst)
1261         : Edges({src, dst}) {}
1262 
1263     void append(MachineBasicBlock *dst) {
1264       assert(getKey()->isSuccessor(dst) &&
1265              "Attempting to append a block that is not a successor.");
1266       Edges.push_back(dst);
1267     }
1268 
1269     unsigned count() const { return Edges.size() - 1; }
1270 
1271     MachineBasicBlock *getKey() const {
1272       return Edges.back();
1273     }
1274   };
1275 
1276   if (TriangleChainCount == 0)
1277     return;
1278 
1279   LLVM_DEBUG(dbgs() << "Pre-computing triangle chains.\n");
1280   // Map from last block to the chain that contains it. This allows us to extend
1281   // chains as we find new triangles.
1282   DenseMap<const MachineBasicBlock *, TriangleChain> TriangleChainMap;
1283   for (MachineBasicBlock &BB : *F) {
1284     // If BB doesn't have 2 successors, it doesn't start a triangle.
1285     if (BB.succ_size() != 2)
1286       continue;
1287     MachineBasicBlock *PDom = nullptr;
1288     for (MachineBasicBlock *Succ : BB.successors()) {
1289       if (!MPDT->dominates(Succ, &BB))
1290         continue;
1291       PDom = Succ;
1292       break;
1293     }
1294     // If BB doesn't have a post-dominating successor, it doesn't form a
1295     // triangle.
1296     if (PDom == nullptr)
1297       continue;
1298     // If PDom has a hint that it is low probability, skip this triangle.
1299     if (MBPI->getEdgeProbability(&BB, PDom) < BranchProbability(50, 100))
1300       continue;
1301     // If PDom isn't eligible for duplication, this isn't the kind of triangle
1302     // we're looking for.
1303     if (!shouldTailDuplicate(PDom))
1304       continue;
1305     bool CanTailDuplicate = true;
1306     // If PDom can't tail-duplicate into it's non-BB predecessors, then this
1307     // isn't the kind of triangle we're looking for.
1308     for (MachineBasicBlock* Pred : PDom->predecessors()) {
1309       if (Pred == &BB)
1310         continue;
1311       if (!TailDup.canTailDuplicate(PDom, Pred)) {
1312         CanTailDuplicate = false;
1313         break;
1314       }
1315     }
1316     // If we can't tail-duplicate PDom to its predecessors, then skip this
1317     // triangle.
1318     if (!CanTailDuplicate)
1319       continue;
1320 
1321     // Now we have an interesting triangle. Insert it if it's not part of an
1322     // existing chain.
1323     // Note: This cannot be replaced with a call insert() or emplace() because
1324     // the find key is BB, but the insert/emplace key is PDom.
1325     auto Found = TriangleChainMap.find(&BB);
1326     // If it is, remove the chain from the map, grow it, and put it back in the
1327     // map with the end as the new key.
1328     if (Found != TriangleChainMap.end()) {
1329       TriangleChain Chain = std::move(Found->second);
1330       TriangleChainMap.erase(Found);
1331       Chain.append(PDom);
1332       TriangleChainMap.insert(std::make_pair(Chain.getKey(), std::move(Chain)));
1333     } else {
1334       auto InsertResult = TriangleChainMap.try_emplace(PDom, &BB, PDom);
1335       assert(InsertResult.second && "Block seen twice.");
1336       (void)InsertResult;
1337     }
1338   }
1339 
1340   // Iterating over a DenseMap is safe here, because the only thing in the body
1341   // of the loop is inserting into another DenseMap (ComputedEdges).
1342   // ComputedEdges is never iterated, so this doesn't lead to non-determinism.
1343   for (auto &ChainPair : TriangleChainMap) {
1344     TriangleChain &Chain = ChainPair.second;
1345     // Benchmarking has shown that due to branch correlation duplicating 2 or
1346     // more triangles is profitable, despite the calculations assuming
1347     // independence.
1348     if (Chain.count() < TriangleChainCount)
1349       continue;
1350     MachineBasicBlock *dst = Chain.Edges.back();
1351     Chain.Edges.pop_back();
1352     for (MachineBasicBlock *src : reverse(Chain.Edges)) {
1353       LLVM_DEBUG(dbgs() << "Marking edge: " << getBlockName(src) << "->"
1354                         << getBlockName(dst)
1355                         << " as pre-computed based on triangles.\n");
1356 
1357       auto InsertResult = ComputedEdges.insert({src, {dst, true}});
1358       assert(InsertResult.second && "Block seen twice.");
1359       (void)InsertResult;
1360 
1361       dst = src;
1362     }
1363   }
1364 }
1365 
1366 // When profile is not present, return the StaticLikelyProb.
1367 // When profile is available, we need to handle the triangle-shape CFG.
1368 static BranchProbability getLayoutSuccessorProbThreshold(
1369       const MachineBasicBlock *BB) {
1370   if (!BB->getParent()->getFunction().hasProfileData())
1371     return BranchProbability(StaticLikelyProb, 100);
1372   if (BB->succ_size() == 2) {
1373     const MachineBasicBlock *Succ1 = *BB->succ_begin();
1374     const MachineBasicBlock *Succ2 = *(BB->succ_begin() + 1);
1375     if (Succ1->isSuccessor(Succ2) || Succ2->isSuccessor(Succ1)) {
1376       /* See case 1 below for the cost analysis. For BB->Succ to
1377        * be taken with smaller cost, the following needs to hold:
1378        *   Prob(BB->Succ) > 2 * Prob(BB->Pred)
1379        *   So the threshold T in the calculation below
1380        *   (1-T) * Prob(BB->Succ) > T * Prob(BB->Pred)
1381        *   So T / (1 - T) = 2, Yielding T = 2/3
1382        * Also adding user specified branch bias, we have
1383        *   T = (2/3)*(ProfileLikelyProb/50)
1384        *     = (2*ProfileLikelyProb)/150)
1385        */
1386       return BranchProbability(2 * ProfileLikelyProb, 150);
1387     }
1388   }
1389   return BranchProbability(ProfileLikelyProb, 100);
1390 }
1391 
1392 /// Checks to see if the layout candidate block \p Succ has a better layout
1393 /// predecessor than \c BB. If yes, returns true.
1394 /// \p SuccProb: The probability adjusted for only remaining blocks.
1395 ///   Only used for logging
1396 /// \p RealSuccProb: The un-adjusted probability.
1397 /// \p Chain: The chain that BB belongs to and Succ is being considered for.
1398 /// \p BlockFilter: if non-null, the set of blocks that make up the loop being
1399 ///    considered
1400 bool MachineBlockPlacement::hasBetterLayoutPredecessor(
1401     const MachineBasicBlock *BB, const MachineBasicBlock *Succ,
1402     const BlockChain &SuccChain, BranchProbability SuccProb,
1403     BranchProbability RealSuccProb, const BlockChain &Chain,
1404     const BlockFilterSet *BlockFilter) {
1405 
1406   // There isn't a better layout when there are no unscheduled predecessors.
1407   if (SuccChain.UnscheduledPredecessors == 0)
1408     return false;
1409 
1410   // There are two basic scenarios here:
1411   // -------------------------------------
1412   // Case 1: triangular shape CFG (if-then):
1413   //     BB
1414   //     | \
1415   //     |  \
1416   //     |   Pred
1417   //     |   /
1418   //     Succ
1419   // In this case, we are evaluating whether to select edge -> Succ, e.g.
1420   // set Succ as the layout successor of BB. Picking Succ as BB's
1421   // successor breaks the CFG constraints (FIXME: define these constraints).
1422   // With this layout, Pred BB
1423   // is forced to be outlined, so the overall cost will be cost of the
1424   // branch taken from BB to Pred, plus the cost of back taken branch
1425   // from Pred to Succ, as well as the additional cost associated
1426   // with the needed unconditional jump instruction from Pred To Succ.
1427 
1428   // The cost of the topological order layout is the taken branch cost
1429   // from BB to Succ, so to make BB->Succ a viable candidate, the following
1430   // must hold:
1431   //     2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost
1432   //      < freq(BB->Succ) *  taken_branch_cost.
1433   // Ignoring unconditional jump cost, we get
1434   //    freq(BB->Succ) > 2 * freq(BB->Pred), i.e.,
1435   //    prob(BB->Succ) > 2 * prob(BB->Pred)
1436   //
1437   // When real profile data is available, we can precisely compute the
1438   // probability threshold that is needed for edge BB->Succ to be considered.
1439   // Without profile data, the heuristic requires the branch bias to be
1440   // a lot larger to make sure the signal is very strong (e.g. 80% default).
1441   // -----------------------------------------------------------------
1442   // Case 2: diamond like CFG (if-then-else):
1443   //     S
1444   //    / \
1445   //   |   \
1446   //  BB    Pred
1447   //   \    /
1448   //    Succ
1449   //    ..
1450   //
1451   // The current block is BB and edge BB->Succ is now being evaluated.
1452   // Note that edge S->BB was previously already selected because
1453   // prob(S->BB) > prob(S->Pred).
1454   // At this point, 2 blocks can be placed after BB: Pred or Succ. If we
1455   // choose Pred, we will have a topological ordering as shown on the left
1456   // in the picture below. If we choose Succ, we have the solution as shown
1457   // on the right:
1458   //
1459   //   topo-order:
1460   //
1461   //       S-----                             ---S
1462   //       |    |                             |  |
1463   //    ---BB   |                             |  BB
1464   //    |       |                             |  |
1465   //    |  Pred--                             |  Succ--
1466   //    |  |                                  |       |
1467   //    ---Succ                               ---Pred--
1468   //
1469   // cost = freq(S->Pred) + freq(BB->Succ)    cost = 2 * freq (S->Pred)
1470   //      = freq(S->Pred) + freq(S->BB)
1471   //
1472   // If we have profile data (i.e, branch probabilities can be trusted), the
1473   // cost (number of taken branches) with layout S->BB->Succ->Pred is 2 *
1474   // freq(S->Pred) while the cost of topo order is freq(S->Pred) + freq(S->BB).
1475   // We know Prob(S->BB) > Prob(S->Pred), so freq(S->BB) > freq(S->Pred), which
1476   // means the cost of topological order is greater.
1477   // When profile data is not available, however, we need to be more
1478   // conservative. If the branch prediction is wrong, breaking the topo-order
1479   // will actually yield a layout with large cost. For this reason, we need
1480   // strong biased branch at block S with Prob(S->BB) in order to select
1481   // BB->Succ. This is equivalent to looking the CFG backward with backward
1482   // edge: Prob(Succ->BB) needs to >= HotProb in order to be selected (without
1483   // profile data).
1484   // --------------------------------------------------------------------------
1485   // Case 3: forked diamond
1486   //       S
1487   //      / \
1488   //     /   \
1489   //   BB    Pred
1490   //   | \   / |
1491   //   |  \ /  |
1492   //   |   X   |
1493   //   |  / \  |
1494   //   | /   \ |
1495   //   S1     S2
1496   //
1497   // The current block is BB and edge BB->S1 is now being evaluated.
1498   // As above S->BB was already selected because
1499   // prob(S->BB) > prob(S->Pred). Assume that prob(BB->S1) >= prob(BB->S2).
1500   //
1501   // topo-order:
1502   //
1503   //     S-------|                     ---S
1504   //     |       |                     |  |
1505   //  ---BB      |                     |  BB
1506   //  |          |                     |  |
1507   //  |  Pred----|                     |  S1----
1508   //  |  |                             |       |
1509   //  --(S1 or S2)                     ---Pred--
1510   //                                        |
1511   //                                       S2
1512   //
1513   // topo-cost = freq(S->Pred) + freq(BB->S1) + freq(BB->S2)
1514   //    + min(freq(Pred->S1), freq(Pred->S2))
1515   // Non-topo-order cost:
1516   // non-topo-cost = 2 * freq(S->Pred) + freq(BB->S2).
1517   // To be conservative, we can assume that min(freq(Pred->S1), freq(Pred->S2))
1518   // is 0. Then the non topo layout is better when
1519   // freq(S->Pred) < freq(BB->S1).
1520   // This is exactly what is checked below.
1521   // Note there are other shapes that apply (Pred may not be a single block,
1522   // but they all fit this general pattern.)
1523   BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB);
1524 
1525   // Make sure that a hot successor doesn't have a globally more
1526   // important predecessor.
1527   BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
1528   bool BadCFGConflict = false;
1529 
1530   for (MachineBasicBlock *Pred : Succ->predecessors()) {
1531     BlockChain *PredChain = BlockToChain[Pred];
1532     if (Pred == Succ || PredChain == &SuccChain ||
1533         (BlockFilter && !BlockFilter->count(Pred)) ||
1534         PredChain == &Chain || Pred != *std::prev(PredChain->end()) ||
1535         // This check is redundant except for look ahead. This function is
1536         // called for lookahead by isProfitableToTailDup when BB hasn't been
1537         // placed yet.
1538         (Pred == BB))
1539       continue;
1540     // Do backward checking.
1541     // For all cases above, we need a backward checking to filter out edges that
1542     // are not 'strongly' biased.
1543     // BB  Pred
1544     //  \ /
1545     //  Succ
1546     // We select edge BB->Succ if
1547     //      freq(BB->Succ) > freq(Succ) * HotProb
1548     //      i.e. freq(BB->Succ) > freq(BB->Succ) * HotProb + freq(Pred->Succ) *
1549     //      HotProb
1550     //      i.e. freq((BB->Succ) * (1 - HotProb) > freq(Pred->Succ) * HotProb
1551     // Case 1 is covered too, because the first equation reduces to:
1552     // prob(BB->Succ) > HotProb. (freq(Succ) = freq(BB) for a triangle)
1553     BlockFrequency PredEdgeFreq =
1554         MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
1555     if (PredEdgeFreq * HotProb >= CandidateEdgeFreq * HotProb.getCompl()) {
1556       BadCFGConflict = true;
1557       break;
1558     }
1559   }
1560 
1561   if (BadCFGConflict) {
1562     LLVM_DEBUG(dbgs() << "    Not a candidate: " << getBlockName(Succ) << " -> "
1563                       << SuccProb << " (prob) (non-cold CFG conflict)\n");
1564     return true;
1565   }
1566 
1567   return false;
1568 }
1569 
1570 /// Select the best successor for a block.
1571 ///
1572 /// This looks across all successors of a particular block and attempts to
1573 /// select the "best" one to be the layout successor. It only considers direct
1574 /// successors which also pass the block filter. It will attempt to avoid
1575 /// breaking CFG structure, but cave and break such structures in the case of
1576 /// very hot successor edges.
1577 ///
1578 /// \returns The best successor block found, or null if none are viable, along
1579 /// with a boolean indicating if tail duplication is necessary.
1580 MachineBlockPlacement::BlockAndTailDupResult
1581 MachineBlockPlacement::selectBestSuccessor(
1582     const MachineBasicBlock *BB, const BlockChain &Chain,
1583     const BlockFilterSet *BlockFilter) {
1584   const BranchProbability HotProb(StaticLikelyProb, 100);
1585 
1586   BlockAndTailDupResult BestSucc = { nullptr, false };
1587   auto BestProb = BranchProbability::getZero();
1588 
1589   SmallVector<MachineBasicBlock *, 4> Successors;
1590   auto AdjustedSumProb =
1591       collectViableSuccessors(BB, Chain, BlockFilter, Successors);
1592 
1593   LLVM_DEBUG(dbgs() << "Selecting best successor for: " << getBlockName(BB)
1594                     << "\n");
1595 
1596   // if we already precomputed the best successor for BB, return that if still
1597   // applicable.
1598   auto FoundEdge = ComputedEdges.find(BB);
1599   if (FoundEdge != ComputedEdges.end()) {
1600     MachineBasicBlock *Succ = FoundEdge->second.BB;
1601     ComputedEdges.erase(FoundEdge);
1602     BlockChain *SuccChain = BlockToChain[Succ];
1603     if (BB->isSuccessor(Succ) && (!BlockFilter || BlockFilter->count(Succ)) &&
1604         SuccChain != &Chain && Succ == *SuccChain->begin())
1605       return FoundEdge->second;
1606   }
1607 
1608   // if BB is part of a trellis, Use the trellis to determine the optimal
1609   // fallthrough edges
1610   if (isTrellis(BB, Successors, Chain, BlockFilter))
1611     return getBestTrellisSuccessor(BB, Successors, AdjustedSumProb, Chain,
1612                                    BlockFilter);
1613 
1614   // For blocks with CFG violations, we may be able to lay them out anyway with
1615   // tail-duplication. We keep this vector so we can perform the probability
1616   // calculations the minimum number of times.
1617   SmallVector<std::pair<BranchProbability, MachineBasicBlock *>, 4>
1618       DupCandidates;
1619   for (MachineBasicBlock *Succ : Successors) {
1620     auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
1621     BranchProbability SuccProb =
1622         getAdjustedProbability(RealSuccProb, AdjustedSumProb);
1623 
1624     BlockChain &SuccChain = *BlockToChain[Succ];
1625     // Skip the edge \c BB->Succ if block \c Succ has a better layout
1626     // predecessor that yields lower global cost.
1627     if (hasBetterLayoutPredecessor(BB, Succ, SuccChain, SuccProb, RealSuccProb,
1628                                    Chain, BlockFilter)) {
1629       // If tail duplication would make Succ profitable, place it.
1630       if (allowTailDupPlacement() && shouldTailDuplicate(Succ))
1631         DupCandidates.emplace_back(SuccProb, Succ);
1632       continue;
1633     }
1634 
1635     LLVM_DEBUG(
1636         dbgs() << "    Candidate: " << getBlockName(Succ)
1637                << ", probability: " << SuccProb
1638                << (SuccChain.UnscheduledPredecessors != 0 ? " (CFG break)" : "")
1639                << "\n");
1640 
1641     if (BestSucc.BB && BestProb >= SuccProb) {
1642       LLVM_DEBUG(dbgs() << "    Not the best candidate, continuing\n");
1643       continue;
1644     }
1645 
1646     LLVM_DEBUG(dbgs() << "    Setting it as best candidate\n");
1647     BestSucc.BB = Succ;
1648     BestProb = SuccProb;
1649   }
1650   // Handle the tail duplication candidates in order of decreasing probability.
1651   // Stop at the first one that is profitable. Also stop if they are less
1652   // profitable than BestSucc. Position is important because we preserve it and
1653   // prefer first best match. Here we aren't comparing in order, so we capture
1654   // the position instead.
1655   llvm::stable_sort(DupCandidates,
1656                     [](std::tuple<BranchProbability, MachineBasicBlock *> L,
1657                        std::tuple<BranchProbability, MachineBasicBlock *> R) {
1658                       return std::get<0>(L) > std::get<0>(R);
1659                     });
1660   for (auto &Tup : DupCandidates) {
1661     BranchProbability DupProb;
1662     MachineBasicBlock *Succ;
1663     std::tie(DupProb, Succ) = Tup;
1664     if (DupProb < BestProb)
1665       break;
1666     if (canTailDuplicateUnplacedPreds(BB, Succ, Chain, BlockFilter)
1667         && (isProfitableToTailDup(BB, Succ, BestProb, Chain, BlockFilter))) {
1668       LLVM_DEBUG(dbgs() << "    Candidate: " << getBlockName(Succ)
1669                         << ", probability: " << DupProb
1670                         << " (Tail Duplicate)\n");
1671       BestSucc.BB = Succ;
1672       BestSucc.ShouldTailDup = true;
1673       break;
1674     }
1675   }
1676 
1677   if (BestSucc.BB)
1678     LLVM_DEBUG(dbgs() << "    Selected: " << getBlockName(BestSucc.BB) << "\n");
1679 
1680   return BestSucc;
1681 }
1682 
1683 /// Select the best block from a worklist.
1684 ///
1685 /// This looks through the provided worklist as a list of candidate basic
1686 /// blocks and select the most profitable one to place. The definition of
1687 /// profitable only really makes sense in the context of a loop. This returns
1688 /// the most frequently visited block in the worklist, which in the case of
1689 /// a loop, is the one most desirable to be physically close to the rest of the
1690 /// loop body in order to improve i-cache behavior.
1691 ///
1692 /// \returns The best block found, or null if none are viable.
1693 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
1694     const BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList) {
1695   // Once we need to walk the worklist looking for a candidate, cleanup the
1696   // worklist of already placed entries.
1697   // FIXME: If this shows up on profiles, it could be folded (at the cost of
1698   // some code complexity) into the loop below.
1699   llvm::erase_if(WorkList, [&](MachineBasicBlock *BB) {
1700     return BlockToChain.lookup(BB) == &Chain;
1701   });
1702 
1703   if (WorkList.empty())
1704     return nullptr;
1705 
1706   bool IsEHPad = WorkList[0]->isEHPad();
1707 
1708   MachineBasicBlock *BestBlock = nullptr;
1709   BlockFrequency BestFreq;
1710   for (MachineBasicBlock *MBB : WorkList) {
1711     assert(MBB->isEHPad() == IsEHPad &&
1712            "EHPad mismatch between block and work list.");
1713 
1714     BlockChain &SuccChain = *BlockToChain[MBB];
1715     if (&SuccChain == &Chain)
1716       continue;
1717 
1718     assert(SuccChain.UnscheduledPredecessors == 0 &&
1719            "Found CFG-violating block");
1720 
1721     BlockFrequency CandidateFreq = MBFI->getBlockFreq(MBB);
1722     LLVM_DEBUG(dbgs() << "    " << getBlockName(MBB) << " -> ";
1723                MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n");
1724 
1725     // For ehpad, we layout the least probable first as to avoid jumping back
1726     // from least probable landingpads to more probable ones.
1727     //
1728     // FIXME: Using probability is probably (!) not the best way to achieve
1729     // this. We should probably have a more principled approach to layout
1730     // cleanup code.
1731     //
1732     // The goal is to get:
1733     //
1734     //                 +--------------------------+
1735     //                 |                          V
1736     // InnerLp -> InnerCleanup    OuterLp -> OuterCleanup -> Resume
1737     //
1738     // Rather than:
1739     //
1740     //                 +-------------------------------------+
1741     //                 V                                     |
1742     // OuterLp -> OuterCleanup -> Resume     InnerLp -> InnerCleanup
1743     if (BestBlock && (IsEHPad ^ (BestFreq >= CandidateFreq)))
1744       continue;
1745 
1746     BestBlock = MBB;
1747     BestFreq = CandidateFreq;
1748   }
1749 
1750   return BestBlock;
1751 }
1752 
1753 /// Retrieve the first unplaced basic block.
1754 ///
1755 /// This routine is called when we are unable to use the CFG to walk through
1756 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
1757 /// We walk through the function's blocks in order, starting from the
1758 /// LastUnplacedBlockIt. We update this iterator on each call to avoid
1759 /// re-scanning the entire sequence on repeated calls to this routine.
1760 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock(
1761     const BlockChain &PlacedChain,
1762     MachineFunction::iterator &PrevUnplacedBlockIt,
1763     const BlockFilterSet *BlockFilter) {
1764   for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F->end(); I != E;
1765        ++I) {
1766     if (BlockFilter && !BlockFilter->count(&*I))
1767       continue;
1768     if (BlockToChain[&*I] != &PlacedChain) {
1769       PrevUnplacedBlockIt = I;
1770       // Now select the head of the chain to which the unplaced block belongs
1771       // as the block to place. This will force the entire chain to be placed,
1772       // and satisfies the requirements of merging chains.
1773       return *BlockToChain[&*I]->begin();
1774     }
1775   }
1776   return nullptr;
1777 }
1778 
1779 void MachineBlockPlacement::fillWorkLists(
1780     const MachineBasicBlock *MBB,
1781     SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
1782     const BlockFilterSet *BlockFilter = nullptr) {
1783   BlockChain &Chain = *BlockToChain[MBB];
1784   if (!UpdatedPreds.insert(&Chain).second)
1785     return;
1786 
1787   assert(
1788       Chain.UnscheduledPredecessors == 0 &&
1789       "Attempting to place block with unscheduled predecessors in worklist.");
1790   for (MachineBasicBlock *ChainBB : Chain) {
1791     assert(BlockToChain[ChainBB] == &Chain &&
1792            "Block in chain doesn't match BlockToChain map.");
1793     for (MachineBasicBlock *Pred : ChainBB->predecessors()) {
1794       if (BlockFilter && !BlockFilter->count(Pred))
1795         continue;
1796       if (BlockToChain[Pred] == &Chain)
1797         continue;
1798       ++Chain.UnscheduledPredecessors;
1799     }
1800   }
1801 
1802   if (Chain.UnscheduledPredecessors != 0)
1803     return;
1804 
1805   MachineBasicBlock *BB = *Chain.begin();
1806   if (BB->isEHPad())
1807     EHPadWorkList.push_back(BB);
1808   else
1809     BlockWorkList.push_back(BB);
1810 }
1811 
1812 void MachineBlockPlacement::buildChain(
1813     const MachineBasicBlock *HeadBB, BlockChain &Chain,
1814     BlockFilterSet *BlockFilter) {
1815   assert(HeadBB && "BB must not be null.\n");
1816   assert(BlockToChain[HeadBB] == &Chain && "BlockToChainMap mis-match.\n");
1817   MachineFunction::iterator PrevUnplacedBlockIt = F->begin();
1818 
1819   const MachineBasicBlock *LoopHeaderBB = HeadBB;
1820   markChainSuccessors(Chain, LoopHeaderBB, BlockFilter);
1821   MachineBasicBlock *BB = *std::prev(Chain.end());
1822   while (true) {
1823     assert(BB && "null block found at end of chain in loop.");
1824     assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop.");
1825     assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain.");
1826 
1827 
1828     // Look for the best viable successor if there is one to place immediately
1829     // after this block.
1830     auto Result = selectBestSuccessor(BB, Chain, BlockFilter);
1831     MachineBasicBlock* BestSucc = Result.BB;
1832     bool ShouldTailDup = Result.ShouldTailDup;
1833     if (allowTailDupPlacement())
1834       ShouldTailDup |= (BestSucc && canTailDuplicateUnplacedPreds(BB, BestSucc,
1835                                                                   Chain,
1836                                                                   BlockFilter));
1837 
1838     // If an immediate successor isn't available, look for the best viable
1839     // block among those we've identified as not violating the loop's CFG at
1840     // this point. This won't be a fallthrough, but it will increase locality.
1841     if (!BestSucc)
1842       BestSucc = selectBestCandidateBlock(Chain, BlockWorkList);
1843     if (!BestSucc)
1844       BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList);
1845 
1846     if (!BestSucc) {
1847       BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt, BlockFilter);
1848       if (!BestSucc)
1849         break;
1850 
1851       LLVM_DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "
1852                            "layout successor until the CFG reduces\n");
1853     }
1854 
1855     // Placement may have changed tail duplication opportunities.
1856     // Check for that now.
1857     if (allowTailDupPlacement() && BestSucc && ShouldTailDup) {
1858       repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain,
1859                                        BlockFilter, PrevUnplacedBlockIt);
1860       // If the chosen successor was duplicated into BB, don't bother laying
1861       // it out, just go round the loop again with BB as the chain end.
1862       if (!BB->isSuccessor(BestSucc))
1863         continue;
1864     }
1865 
1866     // Place this block, updating the datastructures to reflect its placement.
1867     BlockChain &SuccChain = *BlockToChain[BestSucc];
1868     // Zero out UnscheduledPredecessors for the successor we're about to merge in case
1869     // we selected a successor that didn't fit naturally into the CFG.
1870     SuccChain.UnscheduledPredecessors = 0;
1871     LLVM_DEBUG(dbgs() << "Merging from " << getBlockName(BB) << " to "
1872                       << getBlockName(BestSucc) << "\n");
1873     markChainSuccessors(SuccChain, LoopHeaderBB, BlockFilter);
1874     Chain.merge(BestSucc, &SuccChain);
1875     BB = *std::prev(Chain.end());
1876   }
1877 
1878   LLVM_DEBUG(dbgs() << "Finished forming chain for header block "
1879                     << getBlockName(*Chain.begin()) << "\n");
1880 }
1881 
1882 // If bottom of block BB has only one successor OldTop, in most cases it is
1883 // profitable to move it before OldTop, except the following case:
1884 //
1885 //     -->OldTop<-
1886 //     |    .    |
1887 //     |    .    |
1888 //     |    .    |
1889 //     ---Pred   |
1890 //          |    |
1891 //         BB-----
1892 //
1893 // If BB is moved before OldTop, Pred needs a taken branch to BB, and it can't
1894 // layout the other successor below it, so it can't reduce taken branch.
1895 // In this case we keep its original layout.
1896 bool
1897 MachineBlockPlacement::canMoveBottomBlockToTop(
1898     const MachineBasicBlock *BottomBlock,
1899     const MachineBasicBlock *OldTop) {
1900   if (BottomBlock->pred_size() != 1)
1901     return true;
1902   MachineBasicBlock *Pred = *BottomBlock->pred_begin();
1903   if (Pred->succ_size() != 2)
1904     return true;
1905 
1906   MachineBasicBlock *OtherBB = *Pred->succ_begin();
1907   if (OtherBB == BottomBlock)
1908     OtherBB = *Pred->succ_rbegin();
1909   if (OtherBB == OldTop)
1910     return false;
1911 
1912   return true;
1913 }
1914 
1915 // Find out the possible fall through frequence to the top of a loop.
1916 BlockFrequency
1917 MachineBlockPlacement::TopFallThroughFreq(
1918     const MachineBasicBlock *Top,
1919     const BlockFilterSet &LoopBlockSet) {
1920   BlockFrequency MaxFreq = 0;
1921   for (MachineBasicBlock *Pred : Top->predecessors()) {
1922     BlockChain *PredChain = BlockToChain[Pred];
1923     if (!LoopBlockSet.count(Pred) &&
1924         (!PredChain || Pred == *std::prev(PredChain->end()))) {
1925       // Found a Pred block can be placed before Top.
1926       // Check if Top is the best successor of Pred.
1927       auto TopProb = MBPI->getEdgeProbability(Pred, Top);
1928       bool TopOK = true;
1929       for (MachineBasicBlock *Succ : Pred->successors()) {
1930         auto SuccProb = MBPI->getEdgeProbability(Pred, Succ);
1931         BlockChain *SuccChain = BlockToChain[Succ];
1932         // Check if Succ can be placed after Pred.
1933         // Succ should not be in any chain, or it is the head of some chain.
1934         if (!LoopBlockSet.count(Succ) && (SuccProb > TopProb) &&
1935             (!SuccChain || Succ == *SuccChain->begin())) {
1936           TopOK = false;
1937           break;
1938         }
1939       }
1940       if (TopOK) {
1941         BlockFrequency EdgeFreq = MBFI->getBlockFreq(Pred) *
1942                                   MBPI->getEdgeProbability(Pred, Top);
1943         if (EdgeFreq > MaxFreq)
1944           MaxFreq = EdgeFreq;
1945       }
1946     }
1947   }
1948   return MaxFreq;
1949 }
1950 
1951 // Compute the fall through gains when move NewTop before OldTop.
1952 //
1953 // In following diagram, edges marked as "-" are reduced fallthrough, edges
1954 // marked as "+" are increased fallthrough, this function computes
1955 //
1956 //      SUM(increased fallthrough) - SUM(decreased fallthrough)
1957 //
1958 //              |
1959 //              | -
1960 //              V
1961 //        --->OldTop
1962 //        |     .
1963 //        |     .
1964 //       +|     .    +
1965 //        |   Pred --->
1966 //        |     |-
1967 //        |     V
1968 //        --- NewTop <---
1969 //              |-
1970 //              V
1971 //
1972 BlockFrequency
1973 MachineBlockPlacement::FallThroughGains(
1974     const MachineBasicBlock *NewTop,
1975     const MachineBasicBlock *OldTop,
1976     const MachineBasicBlock *ExitBB,
1977     const BlockFilterSet &LoopBlockSet) {
1978   BlockFrequency FallThrough2Top = TopFallThroughFreq(OldTop, LoopBlockSet);
1979   BlockFrequency FallThrough2Exit = 0;
1980   if (ExitBB)
1981     FallThrough2Exit = MBFI->getBlockFreq(NewTop) *
1982         MBPI->getEdgeProbability(NewTop, ExitBB);
1983   BlockFrequency BackEdgeFreq = MBFI->getBlockFreq(NewTop) *
1984       MBPI->getEdgeProbability(NewTop, OldTop);
1985 
1986   // Find the best Pred of NewTop.
1987    MachineBasicBlock *BestPred = nullptr;
1988    BlockFrequency FallThroughFromPred = 0;
1989    for (MachineBasicBlock *Pred : NewTop->predecessors()) {
1990      if (!LoopBlockSet.count(Pred))
1991        continue;
1992      BlockChain *PredChain = BlockToChain[Pred];
1993      if (!PredChain || Pred == *std::prev(PredChain->end())) {
1994        BlockFrequency EdgeFreq = MBFI->getBlockFreq(Pred) *
1995            MBPI->getEdgeProbability(Pred, NewTop);
1996        if (EdgeFreq > FallThroughFromPred) {
1997          FallThroughFromPred = EdgeFreq;
1998          BestPred = Pred;
1999        }
2000      }
2001    }
2002 
2003    // If NewTop is not placed after Pred, another successor can be placed
2004    // after Pred.
2005    BlockFrequency NewFreq = 0;
2006    if (BestPred) {
2007      for (MachineBasicBlock *Succ : BestPred->successors()) {
2008        if ((Succ == NewTop) || (Succ == BestPred) || !LoopBlockSet.count(Succ))
2009          continue;
2010        if (ComputedEdges.find(Succ) != ComputedEdges.end())
2011          continue;
2012        BlockChain *SuccChain = BlockToChain[Succ];
2013        if ((SuccChain && (Succ != *SuccChain->begin())) ||
2014            (SuccChain == BlockToChain[BestPred]))
2015          continue;
2016        BlockFrequency EdgeFreq = MBFI->getBlockFreq(BestPred) *
2017            MBPI->getEdgeProbability(BestPred, Succ);
2018        if (EdgeFreq > NewFreq)
2019          NewFreq = EdgeFreq;
2020      }
2021      BlockFrequency OrigEdgeFreq = MBFI->getBlockFreq(BestPred) *
2022          MBPI->getEdgeProbability(BestPred, NewTop);
2023      if (NewFreq > OrigEdgeFreq) {
2024        // If NewTop is not the best successor of Pred, then Pred doesn't
2025        // fallthrough to NewTop. So there is no FallThroughFromPred and
2026        // NewFreq.
2027        NewFreq = 0;
2028        FallThroughFromPred = 0;
2029      }
2030    }
2031 
2032    BlockFrequency Result = 0;
2033    BlockFrequency Gains = BackEdgeFreq + NewFreq;
2034    BlockFrequency Lost = FallThrough2Top + FallThrough2Exit +
2035        FallThroughFromPred;
2036    if (Gains > Lost)
2037      Result = Gains - Lost;
2038    return Result;
2039 }
2040 
2041 /// Helper function of findBestLoopTop. Find the best loop top block
2042 /// from predecessors of old top.
2043 ///
2044 /// Look for a block which is strictly better than the old top for laying
2045 /// out before the old top of the loop. This looks for only two patterns:
2046 ///
2047 ///     1. a block has only one successor, the old loop top
2048 ///
2049 ///        Because such a block will always result in an unconditional jump,
2050 ///        rotating it in front of the old top is always profitable.
2051 ///
2052 ///     2. a block has two successors, one is old top, another is exit
2053 ///        and it has more than one predecessors
2054 ///
2055 ///        If it is below one of its predecessors P, only P can fall through to
2056 ///        it, all other predecessors need a jump to it, and another conditional
2057 ///        jump to loop header. If it is moved before loop header, all its
2058 ///        predecessors jump to it, then fall through to loop header. So all its
2059 ///        predecessors except P can reduce one taken branch.
2060 ///        At the same time, move it before old top increases the taken branch
2061 ///        to loop exit block, so the reduced taken branch will be compared with
2062 ///        the increased taken branch to the loop exit block.
2063 MachineBasicBlock *
2064 MachineBlockPlacement::findBestLoopTopHelper(
2065     MachineBasicBlock *OldTop,
2066     const MachineLoop &L,
2067     const BlockFilterSet &LoopBlockSet) {
2068   // Check that the header hasn't been fused with a preheader block due to
2069   // crazy branches. If it has, we need to start with the header at the top to
2070   // prevent pulling the preheader into the loop body.
2071   BlockChain &HeaderChain = *BlockToChain[OldTop];
2072   if (!LoopBlockSet.count(*HeaderChain.begin()))
2073     return OldTop;
2074   if (OldTop != *HeaderChain.begin())
2075     return OldTop;
2076 
2077   LLVM_DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(OldTop)
2078                     << "\n");
2079 
2080   BlockFrequency BestGains = 0;
2081   MachineBasicBlock *BestPred = nullptr;
2082   for (MachineBasicBlock *Pred : OldTop->predecessors()) {
2083     if (!LoopBlockSet.count(Pred))
2084       continue;
2085     if (Pred == L.getHeader())
2086       continue;
2087     LLVM_DEBUG(dbgs() << "   old top pred: " << getBlockName(Pred) << ", has "
2088                       << Pred->succ_size() << " successors, ";
2089                MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
2090     if (Pred->succ_size() > 2)
2091       continue;
2092 
2093     MachineBasicBlock *OtherBB = nullptr;
2094     if (Pred->succ_size() == 2) {
2095       OtherBB = *Pred->succ_begin();
2096       if (OtherBB == OldTop)
2097         OtherBB = *Pred->succ_rbegin();
2098     }
2099 
2100     if (!canMoveBottomBlockToTop(Pred, OldTop))
2101       continue;
2102 
2103     BlockFrequency Gains = FallThroughGains(Pred, OldTop, OtherBB,
2104                                             LoopBlockSet);
2105     if ((Gains > 0) && (Gains > BestGains ||
2106         ((Gains == BestGains) && Pred->isLayoutSuccessor(OldTop)))) {
2107       BestPred = Pred;
2108       BestGains = Gains;
2109     }
2110   }
2111 
2112   // If no direct predecessor is fine, just use the loop header.
2113   if (!BestPred) {
2114     LLVM_DEBUG(dbgs() << "    final top unchanged\n");
2115     return OldTop;
2116   }
2117 
2118   // Walk backwards through any straight line of predecessors.
2119   while (BestPred->pred_size() == 1 &&
2120          (*BestPred->pred_begin())->succ_size() == 1 &&
2121          *BestPred->pred_begin() != L.getHeader())
2122     BestPred = *BestPred->pred_begin();
2123 
2124   LLVM_DEBUG(dbgs() << "    final top: " << getBlockName(BestPred) << "\n");
2125   return BestPred;
2126 }
2127 
2128 /// Find the best loop top block for layout.
2129 ///
2130 /// This function iteratively calls findBestLoopTopHelper, until no new better
2131 /// BB can be found.
2132 MachineBasicBlock *
2133 MachineBlockPlacement::findBestLoopTop(const MachineLoop &L,
2134                                        const BlockFilterSet &LoopBlockSet) {
2135   // Placing the latch block before the header may introduce an extra branch
2136   // that skips this block the first time the loop is executed, which we want
2137   // to avoid when optimising for size.
2138   // FIXME: in theory there is a case that does not introduce a new branch,
2139   // i.e. when the layout predecessor does not fallthrough to the loop header.
2140   // In practice this never happens though: there always seems to be a preheader
2141   // that can fallthrough and that is also placed before the header.
2142   bool OptForSize = F->getFunction().hasOptSize() ||
2143                     llvm::shouldOptimizeForSize(L.getHeader(), PSI, MBFI.get());
2144   if (OptForSize)
2145     return L.getHeader();
2146 
2147   MachineBasicBlock *OldTop = nullptr;
2148   MachineBasicBlock *NewTop = L.getHeader();
2149   while (NewTop != OldTop) {
2150     OldTop = NewTop;
2151     NewTop = findBestLoopTopHelper(OldTop, L, LoopBlockSet);
2152     if (NewTop != OldTop)
2153       ComputedEdges[NewTop] = { OldTop, false };
2154   }
2155   return NewTop;
2156 }
2157 
2158 /// Find the best loop exiting block for layout.
2159 ///
2160 /// This routine implements the logic to analyze the loop looking for the best
2161 /// block to layout at the top of the loop. Typically this is done to maximize
2162 /// fallthrough opportunities.
2163 MachineBasicBlock *
2164 MachineBlockPlacement::findBestLoopExit(const MachineLoop &L,
2165                                         const BlockFilterSet &LoopBlockSet,
2166                                         BlockFrequency &ExitFreq) {
2167   // We don't want to layout the loop linearly in all cases. If the loop header
2168   // is just a normal basic block in the loop, we want to look for what block
2169   // within the loop is the best one to layout at the top. However, if the loop
2170   // header has be pre-merged into a chain due to predecessors not having
2171   // analyzable branches, *and* the predecessor it is merged with is *not* part
2172   // of the loop, rotating the header into the middle of the loop will create
2173   // a non-contiguous range of blocks which is Very Bad. So start with the
2174   // header and only rotate if safe.
2175   BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
2176   if (!LoopBlockSet.count(*HeaderChain.begin()))
2177     return nullptr;
2178 
2179   BlockFrequency BestExitEdgeFreq;
2180   unsigned BestExitLoopDepth = 0;
2181   MachineBasicBlock *ExitingBB = nullptr;
2182   // If there are exits to outer loops, loop rotation can severely limit
2183   // fallthrough opportunities unless it selects such an exit. Keep a set of
2184   // blocks where rotating to exit with that block will reach an outer loop.
2185   SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
2186 
2187   LLVM_DEBUG(dbgs() << "Finding best loop exit for: "
2188                     << getBlockName(L.getHeader()) << "\n");
2189   for (MachineBasicBlock *MBB : L.getBlocks()) {
2190     BlockChain &Chain = *BlockToChain[MBB];
2191     // Ensure that this block is at the end of a chain; otherwise it could be
2192     // mid-way through an inner loop or a successor of an unanalyzable branch.
2193     if (MBB != *std::prev(Chain.end()))
2194       continue;
2195 
2196     // Now walk the successors. We need to establish whether this has a viable
2197     // exiting successor and whether it has a viable non-exiting successor.
2198     // We store the old exiting state and restore it if a viable looping
2199     // successor isn't found.
2200     MachineBasicBlock *OldExitingBB = ExitingBB;
2201     BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq;
2202     bool HasLoopingSucc = false;
2203     for (MachineBasicBlock *Succ : MBB->successors()) {
2204       if (Succ->isEHPad())
2205         continue;
2206       if (Succ == MBB)
2207         continue;
2208       BlockChain &SuccChain = *BlockToChain[Succ];
2209       // Don't split chains, either this chain or the successor's chain.
2210       if (&Chain == &SuccChain) {
2211         LLVM_DEBUG(dbgs() << "    exiting: " << getBlockName(MBB) << " -> "
2212                           << getBlockName(Succ) << " (chain conflict)\n");
2213         continue;
2214       }
2215 
2216       auto SuccProb = MBPI->getEdgeProbability(MBB, Succ);
2217       if (LoopBlockSet.count(Succ)) {
2218         LLVM_DEBUG(dbgs() << "    looping: " << getBlockName(MBB) << " -> "
2219                           << getBlockName(Succ) << " (" << SuccProb << ")\n");
2220         HasLoopingSucc = true;
2221         continue;
2222       }
2223 
2224       unsigned SuccLoopDepth = 0;
2225       if (MachineLoop *ExitLoop = MLI->getLoopFor(Succ)) {
2226         SuccLoopDepth = ExitLoop->getLoopDepth();
2227         if (ExitLoop->contains(&L))
2228           BlocksExitingToOuterLoop.insert(MBB);
2229       }
2230 
2231       BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
2232       LLVM_DEBUG(dbgs() << "    exiting: " << getBlockName(MBB) << " -> "
2233                         << getBlockName(Succ) << " [L:" << SuccLoopDepth
2234                         << "] (";
2235                  MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n");
2236       // Note that we bias this toward an existing layout successor to retain
2237       // incoming order in the absence of better information. The exit must have
2238       // a frequency higher than the current exit before we consider breaking
2239       // the layout.
2240       BranchProbability Bias(100 - ExitBlockBias, 100);
2241       if (!ExitingBB || SuccLoopDepth > BestExitLoopDepth ||
2242           ExitEdgeFreq > BestExitEdgeFreq ||
2243           (MBB->isLayoutSuccessor(Succ) &&
2244            !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) {
2245         BestExitEdgeFreq = ExitEdgeFreq;
2246         ExitingBB = MBB;
2247       }
2248     }
2249 
2250     if (!HasLoopingSucc) {
2251       // Restore the old exiting state, no viable looping successor was found.
2252       ExitingBB = OldExitingBB;
2253       BestExitEdgeFreq = OldBestExitEdgeFreq;
2254     }
2255   }
2256   // Without a candidate exiting block or with only a single block in the
2257   // loop, just use the loop header to layout the loop.
2258   if (!ExitingBB) {
2259     LLVM_DEBUG(
2260         dbgs() << "    No other candidate exit blocks, using loop header\n");
2261     return nullptr;
2262   }
2263   if (L.getNumBlocks() == 1) {
2264     LLVM_DEBUG(dbgs() << "    Loop has 1 block, using loop header as exit\n");
2265     return nullptr;
2266   }
2267 
2268   // Also, if we have exit blocks which lead to outer loops but didn't select
2269   // one of them as the exiting block we are rotating toward, disable loop
2270   // rotation altogether.
2271   if (!BlocksExitingToOuterLoop.empty() &&
2272       !BlocksExitingToOuterLoop.count(ExitingBB))
2273     return nullptr;
2274 
2275   LLVM_DEBUG(dbgs() << "  Best exiting block: " << getBlockName(ExitingBB)
2276                     << "\n");
2277   ExitFreq = BestExitEdgeFreq;
2278   return ExitingBB;
2279 }
2280 
2281 /// Check if there is a fallthrough to loop header Top.
2282 ///
2283 ///   1. Look for a Pred that can be layout before Top.
2284 ///   2. Check if Top is the most possible successor of Pred.
2285 bool
2286 MachineBlockPlacement::hasViableTopFallthrough(
2287     const MachineBasicBlock *Top,
2288     const BlockFilterSet &LoopBlockSet) {
2289   for (MachineBasicBlock *Pred : Top->predecessors()) {
2290     BlockChain *PredChain = BlockToChain[Pred];
2291     if (!LoopBlockSet.count(Pred) &&
2292         (!PredChain || Pred == *std::prev(PredChain->end()))) {
2293       // Found a Pred block can be placed before Top.
2294       // Check if Top is the best successor of Pred.
2295       auto TopProb = MBPI->getEdgeProbability(Pred, Top);
2296       bool TopOK = true;
2297       for (MachineBasicBlock *Succ : Pred->successors()) {
2298         auto SuccProb = MBPI->getEdgeProbability(Pred, Succ);
2299         BlockChain *SuccChain = BlockToChain[Succ];
2300         // Check if Succ can be placed after Pred.
2301         // Succ should not be in any chain, or it is the head of some chain.
2302         if ((!SuccChain || Succ == *SuccChain->begin()) && SuccProb > TopProb) {
2303           TopOK = false;
2304           break;
2305         }
2306       }
2307       if (TopOK)
2308         return true;
2309     }
2310   }
2311   return false;
2312 }
2313 
2314 /// Attempt to rotate an exiting block to the bottom of the loop.
2315 ///
2316 /// Once we have built a chain, try to rotate it to line up the hot exit block
2317 /// with fallthrough out of the loop if doing so doesn't introduce unnecessary
2318 /// branches. For example, if the loop has fallthrough into its header and out
2319 /// of its bottom already, don't rotate it.
2320 void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
2321                                        const MachineBasicBlock *ExitingBB,
2322                                        BlockFrequency ExitFreq,
2323                                        const BlockFilterSet &LoopBlockSet) {
2324   if (!ExitingBB)
2325     return;
2326 
2327   MachineBasicBlock *Top = *LoopChain.begin();
2328   MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
2329 
2330   // If ExitingBB is already the last one in a chain then nothing to do.
2331   if (Bottom == ExitingBB)
2332     return;
2333 
2334   // The entry block should always be the first BB in a function.
2335   if (Top->isEntryBlock())
2336     return;
2337 
2338   bool ViableTopFallthrough = hasViableTopFallthrough(Top, LoopBlockSet);
2339 
2340   // If the header has viable fallthrough, check whether the current loop
2341   // bottom is a viable exiting block. If so, bail out as rotating will
2342   // introduce an unnecessary branch.
2343   if (ViableTopFallthrough) {
2344     for (MachineBasicBlock *Succ : Bottom->successors()) {
2345       BlockChain *SuccChain = BlockToChain[Succ];
2346       if (!LoopBlockSet.count(Succ) &&
2347           (!SuccChain || Succ == *SuccChain->begin()))
2348         return;
2349     }
2350 
2351     // Rotate will destroy the top fallthrough, we need to ensure the new exit
2352     // frequency is larger than top fallthrough.
2353     BlockFrequency FallThrough2Top = TopFallThroughFreq(Top, LoopBlockSet);
2354     if (FallThrough2Top >= ExitFreq)
2355       return;
2356   }
2357 
2358   BlockChain::iterator ExitIt = llvm::find(LoopChain, ExitingBB);
2359   if (ExitIt == LoopChain.end())
2360     return;
2361 
2362   // Rotating a loop exit to the bottom when there is a fallthrough to top
2363   // trades the entry fallthrough for an exit fallthrough.
2364   // If there is no bottom->top edge, but the chosen exit block does have
2365   // a fallthrough, we break that fallthrough for nothing in return.
2366 
2367   // Let's consider an example. We have a built chain of basic blocks
2368   // B1, B2, ..., Bn, where Bk is a ExitingBB - chosen exit block.
2369   // By doing a rotation we get
2370   // Bk+1, ..., Bn, B1, ..., Bk
2371   // Break of fallthrough to B1 is compensated by a fallthrough from Bk.
2372   // If we had a fallthrough Bk -> Bk+1 it is broken now.
2373   // It might be compensated by fallthrough Bn -> B1.
2374   // So we have a condition to avoid creation of extra branch by loop rotation.
2375   // All below must be true to avoid loop rotation:
2376   //   If there is a fallthrough to top (B1)
2377   //   There was fallthrough from chosen exit block (Bk) to next one (Bk+1)
2378   //   There is no fallthrough from bottom (Bn) to top (B1).
2379   // Please note that there is no exit fallthrough from Bn because we checked it
2380   // above.
2381   if (ViableTopFallthrough) {
2382     assert(std::next(ExitIt) != LoopChain.end() &&
2383            "Exit should not be last BB");
2384     MachineBasicBlock *NextBlockInChain = *std::next(ExitIt);
2385     if (ExitingBB->isSuccessor(NextBlockInChain))
2386       if (!Bottom->isSuccessor(Top))
2387         return;
2388   }
2389 
2390   LLVM_DEBUG(dbgs() << "Rotating loop to put exit " << getBlockName(ExitingBB)
2391                     << " at bottom\n");
2392   std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end());
2393 }
2394 
2395 /// Attempt to rotate a loop based on profile data to reduce branch cost.
2396 ///
2397 /// With profile data, we can determine the cost in terms of missed fall through
2398 /// opportunities when rotating a loop chain and select the best rotation.
2399 /// Basically, there are three kinds of cost to consider for each rotation:
2400 ///    1. The possibly missed fall through edge (if it exists) from BB out of
2401 ///    the loop to the loop header.
2402 ///    2. The possibly missed fall through edges (if they exist) from the loop
2403 ///    exits to BB out of the loop.
2404 ///    3. The missed fall through edge (if it exists) from the last BB to the
2405 ///    first BB in the loop chain.
2406 ///  Therefore, the cost for a given rotation is the sum of costs listed above.
2407 ///  We select the best rotation with the smallest cost.
2408 void MachineBlockPlacement::rotateLoopWithProfile(
2409     BlockChain &LoopChain, const MachineLoop &L,
2410     const BlockFilterSet &LoopBlockSet) {
2411   auto RotationPos = LoopChain.end();
2412   MachineBasicBlock *ChainHeaderBB = *LoopChain.begin();
2413 
2414   // The entry block should always be the first BB in a function.
2415   if (ChainHeaderBB->isEntryBlock())
2416     return;
2417 
2418   BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency();
2419 
2420   // A utility lambda that scales up a block frequency by dividing it by a
2421   // branch probability which is the reciprocal of the scale.
2422   auto ScaleBlockFrequency = [](BlockFrequency Freq,
2423                                 unsigned Scale) -> BlockFrequency {
2424     if (Scale == 0)
2425       return 0;
2426     // Use operator / between BlockFrequency and BranchProbability to implement
2427     // saturating multiplication.
2428     return Freq / BranchProbability(1, Scale);
2429   };
2430 
2431   // Compute the cost of the missed fall-through edge to the loop header if the
2432   // chain head is not the loop header. As we only consider natural loops with
2433   // single header, this computation can be done only once.
2434   BlockFrequency HeaderFallThroughCost(0);
2435   for (auto *Pred : ChainHeaderBB->predecessors()) {
2436     BlockChain *PredChain = BlockToChain[Pred];
2437     if (!LoopBlockSet.count(Pred) &&
2438         (!PredChain || Pred == *std::prev(PredChain->end()))) {
2439       auto EdgeFreq = MBFI->getBlockFreq(Pred) *
2440           MBPI->getEdgeProbability(Pred, ChainHeaderBB);
2441       auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost);
2442       // If the predecessor has only an unconditional jump to the header, we
2443       // need to consider the cost of this jump.
2444       if (Pred->succ_size() == 1)
2445         FallThruCost += ScaleBlockFrequency(EdgeFreq, JumpInstCost);
2446       HeaderFallThroughCost = std::max(HeaderFallThroughCost, FallThruCost);
2447     }
2448   }
2449 
2450   // Here we collect all exit blocks in the loop, and for each exit we find out
2451   // its hottest exit edge. For each loop rotation, we define the loop exit cost
2452   // as the sum of frequencies of exit edges we collect here, excluding the exit
2453   // edge from the tail of the loop chain.
2454   SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq;
2455   for (auto BB : LoopChain) {
2456     auto LargestExitEdgeProb = BranchProbability::getZero();
2457     for (auto *Succ : BB->successors()) {
2458       BlockChain *SuccChain = BlockToChain[Succ];
2459       if (!LoopBlockSet.count(Succ) &&
2460           (!SuccChain || Succ == *SuccChain->begin())) {
2461         auto SuccProb = MBPI->getEdgeProbability(BB, Succ);
2462         LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb);
2463       }
2464     }
2465     if (LargestExitEdgeProb > BranchProbability::getZero()) {
2466       auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb;
2467       ExitsWithFreq.emplace_back(BB, ExitFreq);
2468     }
2469   }
2470 
2471   // In this loop we iterate every block in the loop chain and calculate the
2472   // cost assuming the block is the head of the loop chain. When the loop ends,
2473   // we should have found the best candidate as the loop chain's head.
2474   for (auto Iter = LoopChain.begin(), TailIter = std::prev(LoopChain.end()),
2475             EndIter = LoopChain.end();
2476        Iter != EndIter; Iter++, TailIter++) {
2477     // TailIter is used to track the tail of the loop chain if the block we are
2478     // checking (pointed by Iter) is the head of the chain.
2479     if (TailIter == LoopChain.end())
2480       TailIter = LoopChain.begin();
2481 
2482     auto TailBB = *TailIter;
2483 
2484     // Calculate the cost by putting this BB to the top.
2485     BlockFrequency Cost = 0;
2486 
2487     // If the current BB is the loop header, we need to take into account the
2488     // cost of the missed fall through edge from outside of the loop to the
2489     // header.
2490     if (Iter != LoopChain.begin())
2491       Cost += HeaderFallThroughCost;
2492 
2493     // Collect the loop exit cost by summing up frequencies of all exit edges
2494     // except the one from the chain tail.
2495     for (auto &ExitWithFreq : ExitsWithFreq)
2496       if (TailBB != ExitWithFreq.first)
2497         Cost += ExitWithFreq.second;
2498 
2499     // The cost of breaking the once fall-through edge from the tail to the top
2500     // of the loop chain. Here we need to consider three cases:
2501     // 1. If the tail node has only one successor, then we will get an
2502     //    additional jmp instruction. So the cost here is (MisfetchCost +
2503     //    JumpInstCost) * tail node frequency.
2504     // 2. If the tail node has two successors, then we may still get an
2505     //    additional jmp instruction if the layout successor after the loop
2506     //    chain is not its CFG successor. Note that the more frequently executed
2507     //    jmp instruction will be put ahead of the other one. Assume the
2508     //    frequency of those two branches are x and y, where x is the frequency
2509     //    of the edge to the chain head, then the cost will be
2510     //    (x * MisfetechCost + min(x, y) * JumpInstCost) * tail node frequency.
2511     // 3. If the tail node has more than two successors (this rarely happens),
2512     //    we won't consider any additional cost.
2513     if (TailBB->isSuccessor(*Iter)) {
2514       auto TailBBFreq = MBFI->getBlockFreq(TailBB);
2515       if (TailBB->succ_size() == 1)
2516         Cost += ScaleBlockFrequency(TailBBFreq.getFrequency(),
2517                                     MisfetchCost + JumpInstCost);
2518       else if (TailBB->succ_size() == 2) {
2519         auto TailToHeadProb = MBPI->getEdgeProbability(TailBB, *Iter);
2520         auto TailToHeadFreq = TailBBFreq * TailToHeadProb;
2521         auto ColderEdgeFreq = TailToHeadProb > BranchProbability(1, 2)
2522                                   ? TailBBFreq * TailToHeadProb.getCompl()
2523                                   : TailToHeadFreq;
2524         Cost += ScaleBlockFrequency(TailToHeadFreq, MisfetchCost) +
2525                 ScaleBlockFrequency(ColderEdgeFreq, JumpInstCost);
2526       }
2527     }
2528 
2529     LLVM_DEBUG(dbgs() << "The cost of loop rotation by making "
2530                       << getBlockName(*Iter)
2531                       << " to the top: " << Cost.getFrequency() << "\n");
2532 
2533     if (Cost < SmallestRotationCost) {
2534       SmallestRotationCost = Cost;
2535       RotationPos = Iter;
2536     }
2537   }
2538 
2539   if (RotationPos != LoopChain.end()) {
2540     LLVM_DEBUG(dbgs() << "Rotate loop by making " << getBlockName(*RotationPos)
2541                       << " to the top\n");
2542     std::rotate(LoopChain.begin(), RotationPos, LoopChain.end());
2543   }
2544 }
2545 
2546 /// Collect blocks in the given loop that are to be placed.
2547 ///
2548 /// When profile data is available, exclude cold blocks from the returned set;
2549 /// otherwise, collect all blocks in the loop.
2550 MachineBlockPlacement::BlockFilterSet
2551 MachineBlockPlacement::collectLoopBlockSet(const MachineLoop &L) {
2552   BlockFilterSet LoopBlockSet;
2553 
2554   // Filter cold blocks off from LoopBlockSet when profile data is available.
2555   // Collect the sum of frequencies of incoming edges to the loop header from
2556   // outside. If we treat the loop as a super block, this is the frequency of
2557   // the loop. Then for each block in the loop, we calculate the ratio between
2558   // its frequency and the frequency of the loop block. When it is too small,
2559   // don't add it to the loop chain. If there are outer loops, then this block
2560   // will be merged into the first outer loop chain for which this block is not
2561   // cold anymore. This needs precise profile data and we only do this when
2562   // profile data is available.
2563   if (F->getFunction().hasProfileData() || ForceLoopColdBlock) {
2564     BlockFrequency LoopFreq(0);
2565     for (auto LoopPred : L.getHeader()->predecessors())
2566       if (!L.contains(LoopPred))
2567         LoopFreq += MBFI->getBlockFreq(LoopPred) *
2568                     MBPI->getEdgeProbability(LoopPred, L.getHeader());
2569 
2570     for (MachineBasicBlock *LoopBB : L.getBlocks()) {
2571       if (LoopBlockSet.count(LoopBB))
2572         continue;
2573       auto Freq = MBFI->getBlockFreq(LoopBB).getFrequency();
2574       if (Freq == 0 || LoopFreq.getFrequency() / Freq > LoopToColdBlockRatio)
2575         continue;
2576       BlockChain *Chain = BlockToChain[LoopBB];
2577       for (MachineBasicBlock *ChainBB : *Chain)
2578         LoopBlockSet.insert(ChainBB);
2579     }
2580   } else
2581     LoopBlockSet.insert(L.block_begin(), L.block_end());
2582 
2583   return LoopBlockSet;
2584 }
2585 
2586 /// Forms basic block chains from the natural loop structures.
2587 ///
2588 /// These chains are designed to preserve the existing *structure* of the code
2589 /// as much as possible. We can then stitch the chains together in a way which
2590 /// both preserves the topological structure and minimizes taken conditional
2591 /// branches.
2592 void MachineBlockPlacement::buildLoopChains(const MachineLoop &L) {
2593   // First recurse through any nested loops, building chains for those inner
2594   // loops.
2595   for (const MachineLoop *InnerLoop : L)
2596     buildLoopChains(*InnerLoop);
2597 
2598   assert(BlockWorkList.empty() &&
2599          "BlockWorkList not empty when starting to build loop chains.");
2600   assert(EHPadWorkList.empty() &&
2601          "EHPadWorkList not empty when starting to build loop chains.");
2602   BlockFilterSet LoopBlockSet = collectLoopBlockSet(L);
2603 
2604   // Check if we have profile data for this function. If yes, we will rotate
2605   // this loop by modeling costs more precisely which requires the profile data
2606   // for better layout.
2607   bool RotateLoopWithProfile =
2608       ForcePreciseRotationCost ||
2609       (PreciseRotationCost && F->getFunction().hasProfileData());
2610 
2611   // First check to see if there is an obviously preferable top block for the
2612   // loop. This will default to the header, but may end up as one of the
2613   // predecessors to the header if there is one which will result in strictly
2614   // fewer branches in the loop body.
2615   MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet);
2616 
2617   // If we selected just the header for the loop top, look for a potentially
2618   // profitable exit block in the event that rotating the loop can eliminate
2619   // branches by placing an exit edge at the bottom.
2620   //
2621   // Loops are processed innermost to uttermost, make sure we clear
2622   // PreferredLoopExit before processing a new loop.
2623   PreferredLoopExit = nullptr;
2624   BlockFrequency ExitFreq;
2625   if (!RotateLoopWithProfile && LoopTop == L.getHeader())
2626     PreferredLoopExit = findBestLoopExit(L, LoopBlockSet, ExitFreq);
2627 
2628   BlockChain &LoopChain = *BlockToChain[LoopTop];
2629 
2630   // FIXME: This is a really lame way of walking the chains in the loop: we
2631   // walk the blocks, and use a set to prevent visiting a particular chain
2632   // twice.
2633   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
2634   assert(LoopChain.UnscheduledPredecessors == 0 &&
2635          "LoopChain should not have unscheduled predecessors.");
2636   UpdatedPreds.insert(&LoopChain);
2637 
2638   for (const MachineBasicBlock *LoopBB : LoopBlockSet)
2639     fillWorkLists(LoopBB, UpdatedPreds, &LoopBlockSet);
2640 
2641   buildChain(LoopTop, LoopChain, &LoopBlockSet);
2642 
2643   if (RotateLoopWithProfile)
2644     rotateLoopWithProfile(LoopChain, L, LoopBlockSet);
2645   else
2646     rotateLoop(LoopChain, PreferredLoopExit, ExitFreq, LoopBlockSet);
2647 
2648   LLVM_DEBUG({
2649     // Crash at the end so we get all of the debugging output first.
2650     bool BadLoop = false;
2651     if (LoopChain.UnscheduledPredecessors) {
2652       BadLoop = true;
2653       dbgs() << "Loop chain contains a block without its preds placed!\n"
2654              << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
2655              << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
2656     }
2657     for (MachineBasicBlock *ChainBB : LoopChain) {
2658       dbgs() << "          ... " << getBlockName(ChainBB) << "\n";
2659       if (!LoopBlockSet.remove(ChainBB)) {
2660         // We don't mark the loop as bad here because there are real situations
2661         // where this can occur. For example, with an unanalyzable fallthrough
2662         // from a loop block to a non-loop block or vice versa.
2663         dbgs() << "Loop chain contains a block not contained by the loop!\n"
2664                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
2665                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
2666                << "  Bad block:    " << getBlockName(ChainBB) << "\n";
2667       }
2668     }
2669 
2670     if (!LoopBlockSet.empty()) {
2671       BadLoop = true;
2672       for (const MachineBasicBlock *LoopBB : LoopBlockSet)
2673         dbgs() << "Loop contains blocks never placed into a chain!\n"
2674                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
2675                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
2676                << "  Bad block:    " << getBlockName(LoopBB) << "\n";
2677     }
2678     assert(!BadLoop && "Detected problems with the placement of this loop.");
2679   });
2680 
2681   BlockWorkList.clear();
2682   EHPadWorkList.clear();
2683 }
2684 
2685 void MachineBlockPlacement::buildCFGChains() {
2686   // Ensure that every BB in the function has an associated chain to simplify
2687   // the assumptions of the remaining algorithm.
2688   SmallVector<MachineOperand, 4> Cond; // For analyzeBranch.
2689   for (MachineFunction::iterator FI = F->begin(), FE = F->end(); FI != FE;
2690        ++FI) {
2691     MachineBasicBlock *BB = &*FI;
2692     BlockChain *Chain =
2693         new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
2694     // Also, merge any blocks which we cannot reason about and must preserve
2695     // the exact fallthrough behavior for.
2696     while (true) {
2697       Cond.clear();
2698       MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
2699       if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
2700         break;
2701 
2702       MachineFunction::iterator NextFI = std::next(FI);
2703       MachineBasicBlock *NextBB = &*NextFI;
2704       // Ensure that the layout successor is a viable block, as we know that
2705       // fallthrough is a possibility.
2706       assert(NextFI != FE && "Can't fallthrough past the last block.");
2707       LLVM_DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: "
2708                         << getBlockName(BB) << " -> " << getBlockName(NextBB)
2709                         << "\n");
2710       Chain->merge(NextBB, nullptr);
2711 #ifndef NDEBUG
2712       BlocksWithUnanalyzableExits.insert(&*BB);
2713 #endif
2714       FI = NextFI;
2715       BB = NextBB;
2716     }
2717   }
2718 
2719   // Build any loop-based chains.
2720   PreferredLoopExit = nullptr;
2721   for (MachineLoop *L : *MLI)
2722     buildLoopChains(*L);
2723 
2724   assert(BlockWorkList.empty() &&
2725          "BlockWorkList should be empty before building final chain.");
2726   assert(EHPadWorkList.empty() &&
2727          "EHPadWorkList should be empty before building final chain.");
2728 
2729   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
2730   for (MachineBasicBlock &MBB : *F)
2731     fillWorkLists(&MBB, UpdatedPreds);
2732 
2733   BlockChain &FunctionChain = *BlockToChain[&F->front()];
2734   buildChain(&F->front(), FunctionChain);
2735 
2736 #ifndef NDEBUG
2737   using FunctionBlockSetType = SmallPtrSet<MachineBasicBlock *, 16>;
2738 #endif
2739   LLVM_DEBUG({
2740     // Crash at the end so we get all of the debugging output first.
2741     bool BadFunc = false;
2742     FunctionBlockSetType FunctionBlockSet;
2743     for (MachineBasicBlock &MBB : *F)
2744       FunctionBlockSet.insert(&MBB);
2745 
2746     for (MachineBasicBlock *ChainBB : FunctionChain)
2747       if (!FunctionBlockSet.erase(ChainBB)) {
2748         BadFunc = true;
2749         dbgs() << "Function chain contains a block not in the function!\n"
2750                << "  Bad block:    " << getBlockName(ChainBB) << "\n";
2751       }
2752 
2753     if (!FunctionBlockSet.empty()) {
2754       BadFunc = true;
2755       for (MachineBasicBlock *RemainingBB : FunctionBlockSet)
2756         dbgs() << "Function contains blocks never placed into a chain!\n"
2757                << "  Bad block:    " << getBlockName(RemainingBB) << "\n";
2758     }
2759     assert(!BadFunc && "Detected problems with the block placement.");
2760   });
2761 
2762   // Remember original layout ordering, so we can update terminators after
2763   // reordering to point to the original layout successor.
2764   SmallVector<MachineBasicBlock *, 4> OriginalLayoutSuccessors(
2765       F->getNumBlockIDs());
2766   {
2767     MachineBasicBlock *LastMBB = nullptr;
2768     for (auto &MBB : *F) {
2769       if (LastMBB != nullptr)
2770         OriginalLayoutSuccessors[LastMBB->getNumber()] = &MBB;
2771       LastMBB = &MBB;
2772     }
2773     OriginalLayoutSuccessors[F->back().getNumber()] = nullptr;
2774   }
2775 
2776   // Splice the blocks into place.
2777   MachineFunction::iterator InsertPos = F->begin();
2778   LLVM_DEBUG(dbgs() << "[MBP] Function: " << F->getName() << "\n");
2779   for (MachineBasicBlock *ChainBB : FunctionChain) {
2780     LLVM_DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain "
2781                                                             : "          ... ")
2782                       << getBlockName(ChainBB) << "\n");
2783     if (InsertPos != MachineFunction::iterator(ChainBB))
2784       F->splice(InsertPos, ChainBB);
2785     else
2786       ++InsertPos;
2787 
2788     // Update the terminator of the previous block.
2789     if (ChainBB == *FunctionChain.begin())
2790       continue;
2791     MachineBasicBlock *PrevBB = &*std::prev(MachineFunction::iterator(ChainBB));
2792 
2793     // FIXME: It would be awesome of updateTerminator would just return rather
2794     // than assert when the branch cannot be analyzed in order to remove this
2795     // boiler plate.
2796     Cond.clear();
2797     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
2798 
2799 #ifndef NDEBUG
2800     if (!BlocksWithUnanalyzableExits.count(PrevBB)) {
2801       // Given the exact block placement we chose, we may actually not _need_ to
2802       // be able to edit PrevBB's terminator sequence, but not being _able_ to
2803       // do that at this point is a bug.
2804       assert((!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond) ||
2805               !PrevBB->canFallThrough()) &&
2806              "Unexpected block with un-analyzable fallthrough!");
2807       Cond.clear();
2808       TBB = FBB = nullptr;
2809     }
2810 #endif
2811 
2812     // The "PrevBB" is not yet updated to reflect current code layout, so,
2813     //   o. it may fall-through to a block without explicit "goto" instruction
2814     //      before layout, and no longer fall-through it after layout; or
2815     //   o. just opposite.
2816     //
2817     // analyzeBranch() may return erroneous value for FBB when these two
2818     // situations take place. For the first scenario FBB is mistakenly set NULL;
2819     // for the 2nd scenario, the FBB, which is expected to be NULL, is
2820     // mistakenly pointing to "*BI".
2821     // Thus, if the future change needs to use FBB before the layout is set, it
2822     // has to correct FBB first by using the code similar to the following:
2823     //
2824     // if (!Cond.empty() && (!FBB || FBB == ChainBB)) {
2825     //   PrevBB->updateTerminator();
2826     //   Cond.clear();
2827     //   TBB = FBB = nullptr;
2828     //   if (TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) {
2829     //     // FIXME: This should never take place.
2830     //     TBB = FBB = nullptr;
2831     //   }
2832     // }
2833     if (!TII->analyzeBranch(*PrevBB, TBB, FBB, Cond)) {
2834       PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]);
2835     }
2836   }
2837 
2838   // Fixup the last block.
2839   Cond.clear();
2840   MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
2841   if (!TII->analyzeBranch(F->back(), TBB, FBB, Cond)) {
2842     MachineBasicBlock *PrevBB = &F->back();
2843     PrevBB->updateTerminator(OriginalLayoutSuccessors[PrevBB->getNumber()]);
2844   }
2845 
2846   BlockWorkList.clear();
2847   EHPadWorkList.clear();
2848 }
2849 
2850 void MachineBlockPlacement::optimizeBranches() {
2851   BlockChain &FunctionChain = *BlockToChain[&F->front()];
2852   SmallVector<MachineOperand, 4> Cond; // For analyzeBranch.
2853 
2854   // Now that all the basic blocks in the chain have the proper layout,
2855   // make a final call to analyzeBranch with AllowModify set.
2856   // Indeed, the target may be able to optimize the branches in a way we
2857   // cannot because all branches may not be analyzable.
2858   // E.g., the target may be able to remove an unconditional branch to
2859   // a fallthrough when it occurs after predicated terminators.
2860   for (MachineBasicBlock *ChainBB : FunctionChain) {
2861     Cond.clear();
2862     MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
2863     if (!TII->analyzeBranch(*ChainBB, TBB, FBB, Cond, /*AllowModify*/ true)) {
2864       // If PrevBB has a two-way branch, try to re-order the branches
2865       // such that we branch to the successor with higher probability first.
2866       if (TBB && !Cond.empty() && FBB &&
2867           MBPI->getEdgeProbability(ChainBB, FBB) >
2868               MBPI->getEdgeProbability(ChainBB, TBB) &&
2869           !TII->reverseBranchCondition(Cond)) {
2870         LLVM_DEBUG(dbgs() << "Reverse order of the two branches: "
2871                           << getBlockName(ChainBB) << "\n");
2872         LLVM_DEBUG(dbgs() << "    Edge probability: "
2873                           << MBPI->getEdgeProbability(ChainBB, FBB) << " vs "
2874                           << MBPI->getEdgeProbability(ChainBB, TBB) << "\n");
2875         DebugLoc dl; // FIXME: this is nowhere
2876         TII->removeBranch(*ChainBB);
2877         TII->insertBranch(*ChainBB, FBB, TBB, Cond, dl);
2878       }
2879     }
2880   }
2881 }
2882 
2883 void MachineBlockPlacement::alignBlocks() {
2884   // Walk through the backedges of the function now that we have fully laid out
2885   // the basic blocks and align the destination of each backedge. We don't rely
2886   // exclusively on the loop info here so that we can align backedges in
2887   // unnatural CFGs and backedges that were introduced purely because of the
2888   // loop rotations done during this layout pass.
2889   if (F->getFunction().hasMinSize() ||
2890       (F->getFunction().hasOptSize() && !TLI->alignLoopsWithOptSize()))
2891     return;
2892   BlockChain &FunctionChain = *BlockToChain[&F->front()];
2893   if (FunctionChain.begin() == FunctionChain.end())
2894     return; // Empty chain.
2895 
2896   const BranchProbability ColdProb(1, 5); // 20%
2897   BlockFrequency EntryFreq = MBFI->getBlockFreq(&F->front());
2898   BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb;
2899   for (MachineBasicBlock *ChainBB : FunctionChain) {
2900     if (ChainBB == *FunctionChain.begin())
2901       continue;
2902 
2903     // Don't align non-looping basic blocks. These are unlikely to execute
2904     // enough times to matter in practice. Note that we'll still handle
2905     // unnatural CFGs inside of a natural outer loop (the common case) and
2906     // rotated loops.
2907     MachineLoop *L = MLI->getLoopFor(ChainBB);
2908     if (!L)
2909       continue;
2910 
2911     const Align Align = TLI->getPrefLoopAlignment(L);
2912     if (Align == 1)
2913       continue; // Don't care about loop alignment.
2914 
2915     // If the block is cold relative to the function entry don't waste space
2916     // aligning it.
2917     BlockFrequency Freq = MBFI->getBlockFreq(ChainBB);
2918     if (Freq < WeightedEntryFreq)
2919       continue;
2920 
2921     // If the block is cold relative to its loop header, don't align it
2922     // regardless of what edges into the block exist.
2923     MachineBasicBlock *LoopHeader = L->getHeader();
2924     BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader);
2925     if (Freq < (LoopHeaderFreq * ColdProb))
2926       continue;
2927 
2928     // If the global profiles indicates so, don't align it.
2929     if (llvm::shouldOptimizeForSize(ChainBB, PSI, MBFI.get()) &&
2930         !TLI->alignLoopsWithOptSize())
2931       continue;
2932 
2933     // Check for the existence of a non-layout predecessor which would benefit
2934     // from aligning this block.
2935     MachineBasicBlock *LayoutPred =
2936         &*std::prev(MachineFunction::iterator(ChainBB));
2937 
2938     auto DetermineMaxAlignmentPadding = [&]() {
2939       // Set the maximum bytes allowed to be emitted for alignment.
2940       unsigned MaxBytes;
2941       if (MaxBytesForAlignmentOverride.getNumOccurrences() > 0)
2942         MaxBytes = MaxBytesForAlignmentOverride;
2943       else
2944         MaxBytes = TLI->getMaxPermittedBytesForAlignment(ChainBB);
2945       ChainBB->setMaxBytesForAlignment(MaxBytes);
2946     };
2947 
2948     // Force alignment if all the predecessors are jumps. We already checked
2949     // that the block isn't cold above.
2950     if (!LayoutPred->isSuccessor(ChainBB)) {
2951       ChainBB->setAlignment(Align);
2952       DetermineMaxAlignmentPadding();
2953       continue;
2954     }
2955 
2956     // Align this block if the layout predecessor's edge into this block is
2957     // cold relative to the block. When this is true, other predecessors make up
2958     // all of the hot entries into the block and thus alignment is likely to be
2959     // important.
2960     BranchProbability LayoutProb =
2961         MBPI->getEdgeProbability(LayoutPred, ChainBB);
2962     BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb;
2963     if (LayoutEdgeFreq <= (Freq * ColdProb)) {
2964       ChainBB->setAlignment(Align);
2965       DetermineMaxAlignmentPadding();
2966     }
2967   }
2968 }
2969 
2970 /// Tail duplicate \p BB into (some) predecessors if profitable, repeating if
2971 /// it was duplicated into its chain predecessor and removed.
2972 /// \p BB    - Basic block that may be duplicated.
2973 ///
2974 /// \p LPred - Chosen layout predecessor of \p BB.
2975 ///            Updated to be the chain end if LPred is removed.
2976 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
2977 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
2978 ///                  Used to identify which blocks to update predecessor
2979 ///                  counts.
2980 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
2981 ///                          chosen in the given order due to unnatural CFG
2982 ///                          only needed if \p BB is removed and
2983 ///                          \p PrevUnplacedBlockIt pointed to \p BB.
2984 /// @return true if \p BB was removed.
2985 bool MachineBlockPlacement::repeatedlyTailDuplicateBlock(
2986     MachineBasicBlock *BB, MachineBasicBlock *&LPred,
2987     const MachineBasicBlock *LoopHeaderBB,
2988     BlockChain &Chain, BlockFilterSet *BlockFilter,
2989     MachineFunction::iterator &PrevUnplacedBlockIt) {
2990   bool Removed, DuplicatedToLPred;
2991   bool DuplicatedToOriginalLPred;
2992   Removed = maybeTailDuplicateBlock(BB, LPred, Chain, BlockFilter,
2993                                     PrevUnplacedBlockIt,
2994                                     DuplicatedToLPred);
2995   if (!Removed)
2996     return false;
2997   DuplicatedToOriginalLPred = DuplicatedToLPred;
2998   // Iteratively try to duplicate again. It can happen that a block that is
2999   // duplicated into is still small enough to be duplicated again.
3000   // No need to call markBlockSuccessors in this case, as the blocks being
3001   // duplicated from here on are already scheduled.
3002   while (DuplicatedToLPred && Removed) {
3003     MachineBasicBlock *DupBB, *DupPred;
3004     // The removal callback causes Chain.end() to be updated when a block is
3005     // removed. On the first pass through the loop, the chain end should be the
3006     // same as it was on function entry. On subsequent passes, because we are
3007     // duplicating the block at the end of the chain, if it is removed the
3008     // chain will have shrunk by one block.
3009     BlockChain::iterator ChainEnd = Chain.end();
3010     DupBB = *(--ChainEnd);
3011     // Now try to duplicate again.
3012     if (ChainEnd == Chain.begin())
3013       break;
3014     DupPred = *std::prev(ChainEnd);
3015     Removed = maybeTailDuplicateBlock(DupBB, DupPred, Chain, BlockFilter,
3016                                       PrevUnplacedBlockIt,
3017                                       DuplicatedToLPred);
3018   }
3019   // If BB was duplicated into LPred, it is now scheduled. But because it was
3020   // removed, markChainSuccessors won't be called for its chain. Instead we
3021   // call markBlockSuccessors for LPred to achieve the same effect. This must go
3022   // at the end because repeating the tail duplication can increase the number
3023   // of unscheduled predecessors.
3024   LPred = *std::prev(Chain.end());
3025   if (DuplicatedToOriginalLPred)
3026     markBlockSuccessors(Chain, LPred, LoopHeaderBB, BlockFilter);
3027   return true;
3028 }
3029 
3030 /// Tail duplicate \p BB into (some) predecessors if profitable.
3031 /// \p BB    - Basic block that may be duplicated
3032 /// \p LPred - Chosen layout predecessor of \p BB
3033 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
3034 /// \p BlockFilter - Set of blocks that belong to the loop being laid out.
3035 ///                  Used to identify which blocks to update predecessor
3036 ///                  counts.
3037 /// \p PrevUnplacedBlockIt - Iterator pointing to the last block that was
3038 ///                          chosen in the given order due to unnatural CFG
3039 ///                          only needed if \p BB is removed and
3040 ///                          \p PrevUnplacedBlockIt pointed to \p BB.
3041 /// \p DuplicatedToLPred - True if the block was duplicated into LPred.
3042 /// \return  - True if the block was duplicated into all preds and removed.
3043 bool MachineBlockPlacement::maybeTailDuplicateBlock(
3044     MachineBasicBlock *BB, MachineBasicBlock *LPred,
3045     BlockChain &Chain, BlockFilterSet *BlockFilter,
3046     MachineFunction::iterator &PrevUnplacedBlockIt,
3047     bool &DuplicatedToLPred) {
3048   DuplicatedToLPred = false;
3049   if (!shouldTailDuplicate(BB))
3050     return false;
3051 
3052   LLVM_DEBUG(dbgs() << "Redoing tail duplication for Succ#" << BB->getNumber()
3053                     << "\n");
3054 
3055   // This has to be a callback because none of it can be done after
3056   // BB is deleted.
3057   bool Removed = false;
3058   auto RemovalCallback =
3059       [&](MachineBasicBlock *RemBB) {
3060         // Signal to outer function
3061         Removed = true;
3062 
3063         // Conservative default.
3064         bool InWorkList = true;
3065         // Remove from the Chain and Chain Map
3066         if (BlockToChain.count(RemBB)) {
3067           BlockChain *Chain = BlockToChain[RemBB];
3068           InWorkList = Chain->UnscheduledPredecessors == 0;
3069           Chain->remove(RemBB);
3070           BlockToChain.erase(RemBB);
3071         }
3072 
3073         // Handle the unplaced block iterator
3074         if (&(*PrevUnplacedBlockIt) == RemBB) {
3075           PrevUnplacedBlockIt++;
3076         }
3077 
3078         // Handle the Work Lists
3079         if (InWorkList) {
3080           SmallVectorImpl<MachineBasicBlock *> &RemoveList = BlockWorkList;
3081           if (RemBB->isEHPad())
3082             RemoveList = EHPadWorkList;
3083           llvm::erase_value(RemoveList, RemBB);
3084         }
3085 
3086         // Handle the filter set
3087         if (BlockFilter) {
3088           BlockFilter->remove(RemBB);
3089         }
3090 
3091         // Remove the block from loop info.
3092         MLI->removeBlock(RemBB);
3093         if (RemBB == PreferredLoopExit)
3094           PreferredLoopExit = nullptr;
3095 
3096         LLVM_DEBUG(dbgs() << "TailDuplicator deleted block: "
3097                           << getBlockName(RemBB) << "\n");
3098       };
3099   auto RemovalCallbackRef =
3100       function_ref<void(MachineBasicBlock*)>(RemovalCallback);
3101 
3102   SmallVector<MachineBasicBlock *, 8> DuplicatedPreds;
3103   bool IsSimple = TailDup.isSimpleBB(BB);
3104   SmallVector<MachineBasicBlock *, 8> CandidatePreds;
3105   SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr;
3106   if (F->getFunction().hasProfileData()) {
3107     // We can do partial duplication with precise profile information.
3108     findDuplicateCandidates(CandidatePreds, BB, BlockFilter);
3109     if (CandidatePreds.size() == 0)
3110       return false;
3111     if (CandidatePreds.size() < BB->pred_size())
3112       CandidatePtr = &CandidatePreds;
3113   }
3114   TailDup.tailDuplicateAndUpdate(IsSimple, BB, LPred, &DuplicatedPreds,
3115                                  &RemovalCallbackRef, CandidatePtr);
3116 
3117   // Update UnscheduledPredecessors to reflect tail-duplication.
3118   DuplicatedToLPred = false;
3119   for (MachineBasicBlock *Pred : DuplicatedPreds) {
3120     // We're only looking for unscheduled predecessors that match the filter.
3121     BlockChain* PredChain = BlockToChain[Pred];
3122     if (Pred == LPred)
3123       DuplicatedToLPred = true;
3124     if (Pred == LPred || (BlockFilter && !BlockFilter->count(Pred))
3125         || PredChain == &Chain)
3126       continue;
3127     for (MachineBasicBlock *NewSucc : Pred->successors()) {
3128       if (BlockFilter && !BlockFilter->count(NewSucc))
3129         continue;
3130       BlockChain *NewChain = BlockToChain[NewSucc];
3131       if (NewChain != &Chain && NewChain != PredChain)
3132         NewChain->UnscheduledPredecessors++;
3133     }
3134   }
3135   return Removed;
3136 }
3137 
3138 // Count the number of actual machine instructions.
3139 static uint64_t countMBBInstruction(MachineBasicBlock *MBB) {
3140   uint64_t InstrCount = 0;
3141   for (MachineInstr &MI : *MBB) {
3142     if (!MI.isPHI() && !MI.isMetaInstruction())
3143       InstrCount += 1;
3144   }
3145   return InstrCount;
3146 }
3147 
3148 // The size cost of duplication is the instruction size of the duplicated block.
3149 // So we should scale the threshold accordingly. But the instruction size is not
3150 // available on all targets, so we use the number of instructions instead.
3151 BlockFrequency MachineBlockPlacement::scaleThreshold(MachineBasicBlock *BB) {
3152   return DupThreshold.getFrequency() * countMBBInstruction(BB);
3153 }
3154 
3155 // Returns true if BB is Pred's best successor.
3156 bool MachineBlockPlacement::isBestSuccessor(MachineBasicBlock *BB,
3157                                             MachineBasicBlock *Pred,
3158                                             BlockFilterSet *BlockFilter) {
3159   if (BB == Pred)
3160     return false;
3161   if (BlockFilter && !BlockFilter->count(Pred))
3162     return false;
3163   BlockChain *PredChain = BlockToChain[Pred];
3164   if (PredChain && (Pred != *std::prev(PredChain->end())))
3165     return false;
3166 
3167   // Find the successor with largest probability excluding BB.
3168   BranchProbability BestProb = BranchProbability::getZero();
3169   for (MachineBasicBlock *Succ : Pred->successors())
3170     if (Succ != BB) {
3171       if (BlockFilter && !BlockFilter->count(Succ))
3172         continue;
3173       BlockChain *SuccChain = BlockToChain[Succ];
3174       if (SuccChain && (Succ != *SuccChain->begin()))
3175         continue;
3176       BranchProbability SuccProb = MBPI->getEdgeProbability(Pred, Succ);
3177       if (SuccProb > BestProb)
3178         BestProb = SuccProb;
3179     }
3180 
3181   BranchProbability BBProb = MBPI->getEdgeProbability(Pred, BB);
3182   if (BBProb <= BestProb)
3183     return false;
3184 
3185   // Compute the number of reduced taken branches if Pred falls through to BB
3186   // instead of another successor. Then compare it with threshold.
3187   BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
3188   BlockFrequency Gain = PredFreq * (BBProb - BestProb);
3189   return Gain > scaleThreshold(BB);
3190 }
3191 
3192 // Find out the predecessors of BB and BB can be beneficially duplicated into
3193 // them.
3194 void MachineBlockPlacement::findDuplicateCandidates(
3195     SmallVectorImpl<MachineBasicBlock *> &Candidates,
3196     MachineBasicBlock *BB,
3197     BlockFilterSet *BlockFilter) {
3198   MachineBasicBlock *Fallthrough = nullptr;
3199   BranchProbability DefaultBranchProb = BranchProbability::getZero();
3200   BlockFrequency BBDupThreshold(scaleThreshold(BB));
3201   SmallVector<MachineBasicBlock *, 8> Preds(BB->predecessors());
3202   SmallVector<MachineBasicBlock *, 8> Succs(BB->successors());
3203 
3204   // Sort for highest frequency.
3205   auto CmpSucc = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
3206     return MBPI->getEdgeProbability(BB, A) > MBPI->getEdgeProbability(BB, B);
3207   };
3208   auto CmpPred = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
3209     return MBFI->getBlockFreq(A) > MBFI->getBlockFreq(B);
3210   };
3211   llvm::stable_sort(Succs, CmpSucc);
3212   llvm::stable_sort(Preds, CmpPred);
3213 
3214   auto SuccIt = Succs.begin();
3215   if (SuccIt != Succs.end()) {
3216     DefaultBranchProb = MBPI->getEdgeProbability(BB, *SuccIt).getCompl();
3217   }
3218 
3219   // For each predecessors of BB, compute the benefit of duplicating BB,
3220   // if it is larger than the threshold, add it into Candidates.
3221   //
3222   // If we have following control flow.
3223   //
3224   //     PB1 PB2 PB3 PB4
3225   //      \   |  /    /\
3226   //       \  | /    /  \
3227   //        \ |/    /    \
3228   //         BB----/     OB
3229   //         /\
3230   //        /  \
3231   //      SB1 SB2
3232   //
3233   // And it can be partially duplicated as
3234   //
3235   //   PB2+BB
3236   //      |  PB1 PB3 PB4
3237   //      |   |  /    /\
3238   //      |   | /    /  \
3239   //      |   |/    /    \
3240   //      |  BB----/     OB
3241   //      |\ /|
3242   //      | X |
3243   //      |/ \|
3244   //     SB2 SB1
3245   //
3246   // The benefit of duplicating into a predecessor is defined as
3247   //         Orig_taken_branch - Duplicated_taken_branch
3248   //
3249   // The Orig_taken_branch is computed with the assumption that predecessor
3250   // jumps to BB and the most possible successor is laid out after BB.
3251   //
3252   // The Duplicated_taken_branch is computed with the assumption that BB is
3253   // duplicated into PB, and one successor is layout after it (SB1 for PB1 and
3254   // SB2 for PB2 in our case). If there is no available successor, the combined
3255   // block jumps to all BB's successor, like PB3 in this example.
3256   //
3257   // If a predecessor has multiple successors, so BB can't be duplicated into
3258   // it. But it can beneficially fall through to BB, and duplicate BB into other
3259   // predecessors.
3260   for (MachineBasicBlock *Pred : Preds) {
3261     BlockFrequency PredFreq = getBlockCountOrFrequency(Pred);
3262 
3263     if (!TailDup.canTailDuplicate(BB, Pred)) {
3264       // BB can't be duplicated into Pred, but it is possible to be layout
3265       // below Pred.
3266       if (!Fallthrough && isBestSuccessor(BB, Pred, BlockFilter)) {
3267         Fallthrough = Pred;
3268         if (SuccIt != Succs.end())
3269           SuccIt++;
3270       }
3271       continue;
3272     }
3273 
3274     BlockFrequency OrigCost = PredFreq + PredFreq * DefaultBranchProb;
3275     BlockFrequency DupCost;
3276     if (SuccIt == Succs.end()) {
3277       // Jump to all successors;
3278       if (Succs.size() > 0)
3279         DupCost += PredFreq;
3280     } else {
3281       // Fallthrough to *SuccIt, jump to all other successors;
3282       DupCost += PredFreq;
3283       DupCost -= PredFreq * MBPI->getEdgeProbability(BB, *SuccIt);
3284     }
3285 
3286     assert(OrigCost >= DupCost);
3287     OrigCost -= DupCost;
3288     if (OrigCost > BBDupThreshold) {
3289       Candidates.push_back(Pred);
3290       if (SuccIt != Succs.end())
3291         SuccIt++;
3292     }
3293   }
3294 
3295   // No predecessors can optimally fallthrough to BB.
3296   // So we can change one duplication into fallthrough.
3297   if (!Fallthrough) {
3298     if ((Candidates.size() < Preds.size()) && (Candidates.size() > 0)) {
3299       Candidates[0] = Candidates.back();
3300       Candidates.pop_back();
3301     }
3302   }
3303 }
3304 
3305 void MachineBlockPlacement::initDupThreshold() {
3306   DupThreshold = 0;
3307   if (!F->getFunction().hasProfileData())
3308     return;
3309 
3310   // We prefer to use prifile count.
3311   uint64_t HotThreshold = PSI->getOrCompHotCountThreshold();
3312   if (HotThreshold != UINT64_MAX) {
3313     UseProfileCount = true;
3314     DupThreshold = HotThreshold * TailDupProfilePercentThreshold / 100;
3315     return;
3316   }
3317 
3318   // Profile count is not available, we can use block frequency instead.
3319   BlockFrequency MaxFreq = 0;
3320   for (MachineBasicBlock &MBB : *F) {
3321     BlockFrequency Freq = MBFI->getBlockFreq(&MBB);
3322     if (Freq > MaxFreq)
3323       MaxFreq = Freq;
3324   }
3325 
3326   BranchProbability ThresholdProb(TailDupPlacementPenalty, 100);
3327   DupThreshold = MaxFreq * ThresholdProb;
3328   UseProfileCount = false;
3329 }
3330 
3331 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
3332   if (skipFunction(MF.getFunction()))
3333     return false;
3334 
3335   // Check for single-block functions and skip them.
3336   if (std::next(MF.begin()) == MF.end())
3337     return false;
3338 
3339   F = &MF;
3340   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
3341   MBFI = std::make_unique<MBFIWrapper>(
3342       getAnalysis<MachineBlockFrequencyInfo>());
3343   MLI = &getAnalysis<MachineLoopInfo>();
3344   TII = MF.getSubtarget().getInstrInfo();
3345   TLI = MF.getSubtarget().getTargetLowering();
3346   MPDT = nullptr;
3347   PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
3348 
3349   initDupThreshold();
3350 
3351   // Initialize PreferredLoopExit to nullptr here since it may never be set if
3352   // there are no MachineLoops.
3353   PreferredLoopExit = nullptr;
3354 
3355   assert(BlockToChain.empty() &&
3356          "BlockToChain map should be empty before starting placement.");
3357   assert(ComputedEdges.empty() &&
3358          "Computed Edge map should be empty before starting placement.");
3359 
3360   unsigned TailDupSize = TailDupPlacementThreshold;
3361   // If only the aggressive threshold is explicitly set, use it.
3362   if (TailDupPlacementAggressiveThreshold.getNumOccurrences() != 0 &&
3363       TailDupPlacementThreshold.getNumOccurrences() == 0)
3364     TailDupSize = TailDupPlacementAggressiveThreshold;
3365 
3366   TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
3367   // For aggressive optimization, we can adjust some thresholds to be less
3368   // conservative.
3369   if (PassConfig->getOptLevel() >= CodeGenOpt::Aggressive) {
3370     // At O3 we should be more willing to copy blocks for tail duplication. This
3371     // increases size pressure, so we only do it at O3
3372     // Do this unless only the regular threshold is explicitly set.
3373     if (TailDupPlacementThreshold.getNumOccurrences() == 0 ||
3374         TailDupPlacementAggressiveThreshold.getNumOccurrences() != 0)
3375       TailDupSize = TailDupPlacementAggressiveThreshold;
3376   }
3377 
3378   // If there's no threshold provided through options, query the target
3379   // information for a threshold instead.
3380   if (TailDupPlacementThreshold.getNumOccurrences() == 0 &&
3381       (PassConfig->getOptLevel() < CodeGenOpt::Aggressive ||
3382        TailDupPlacementAggressiveThreshold.getNumOccurrences() == 0))
3383     TailDupSize = TII->getTailDuplicateSize(PassConfig->getOptLevel());
3384 
3385   if (allowTailDupPlacement()) {
3386     MPDT = &getAnalysis<MachinePostDominatorTree>();
3387     bool OptForSize = MF.getFunction().hasOptSize() ||
3388                       llvm::shouldOptimizeForSize(&MF, PSI, &MBFI->getMBFI());
3389     if (OptForSize)
3390       TailDupSize = 1;
3391     bool PreRegAlloc = false;
3392     TailDup.initMF(MF, PreRegAlloc, MBPI, MBFI.get(), PSI,
3393                    /* LayoutMode */ true, TailDupSize);
3394     precomputeTriangleChains();
3395   }
3396 
3397   buildCFGChains();
3398 
3399   // Changing the layout can create new tail merging opportunities.
3400   // TailMerge can create jump into if branches that make CFG irreducible for
3401   // HW that requires structured CFG.
3402   bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
3403                          PassConfig->getEnableTailMerge() &&
3404                          BranchFoldPlacement;
3405   // No tail merging opportunities if the block number is less than four.
3406   if (MF.size() > 3 && EnableTailMerge) {
3407     unsigned TailMergeSize = TailDupSize + 1;
3408     BranchFolder BF(/*DefaultEnableTailMerge=*/true, /*CommonHoist=*/false,
3409                     *MBFI, *MBPI, PSI, TailMergeSize);
3410 
3411     if (BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(), MLI,
3412                             /*AfterPlacement=*/true)) {
3413       // Redo the layout if tail merging creates/removes/moves blocks.
3414       BlockToChain.clear();
3415       ComputedEdges.clear();
3416       // Must redo the post-dominator tree if blocks were changed.
3417       if (MPDT)
3418         MPDT->runOnMachineFunction(MF);
3419       ChainAllocator.DestroyAll();
3420       buildCFGChains();
3421     }
3422   }
3423 
3424   // Apply a post-processing optimizing block placement.
3425   if (MF.size() >= 3 && EnableExtTspBlockPlacement) {
3426     // Find a new placement and modify the layout of the blocks in the function.
3427     applyExtTsp();
3428 
3429     // Re-create CFG chain so that we can optimizeBranches and alignBlocks.
3430     createCFGChainExtTsp();
3431   }
3432 
3433   optimizeBranches();
3434   alignBlocks();
3435 
3436   BlockToChain.clear();
3437   ComputedEdges.clear();
3438   ChainAllocator.DestroyAll();
3439 
3440   bool HasMaxBytesOverride =
3441       MaxBytesForAlignmentOverride.getNumOccurrences() > 0;
3442 
3443   if (AlignAllBlock)
3444     // Align all of the blocks in the function to a specific alignment.
3445     for (MachineBasicBlock &MBB : MF) {
3446       if (HasMaxBytesOverride)
3447         MBB.setAlignment(Align(1ULL << AlignAllBlock),
3448                          MaxBytesForAlignmentOverride);
3449       else
3450         MBB.setAlignment(Align(1ULL << AlignAllBlock));
3451     }
3452   else if (AlignAllNonFallThruBlocks) {
3453     // Align all of the blocks that have no fall-through predecessors to a
3454     // specific alignment.
3455     for (auto MBI = std::next(MF.begin()), MBE = MF.end(); MBI != MBE; ++MBI) {
3456       auto LayoutPred = std::prev(MBI);
3457       if (!LayoutPred->isSuccessor(&*MBI)) {
3458         if (HasMaxBytesOverride)
3459           MBI->setAlignment(Align(1ULL << AlignAllNonFallThruBlocks),
3460                             MaxBytesForAlignmentOverride);
3461         else
3462           MBI->setAlignment(Align(1ULL << AlignAllNonFallThruBlocks));
3463       }
3464     }
3465   }
3466   if (ViewBlockLayoutWithBFI != GVDT_None &&
3467       (ViewBlockFreqFuncName.empty() ||
3468        F->getFunction().getName().equals(ViewBlockFreqFuncName))) {
3469     MBFI->view("MBP." + MF.getName(), false);
3470   }
3471 
3472   // We always return true as we have no way to track whether the final order
3473   // differs from the original order.
3474   return true;
3475 }
3476 
3477 void MachineBlockPlacement::applyExtTsp() {
3478   // Prepare data; blocks are indexed by their index in the current ordering.
3479   DenseMap<const MachineBasicBlock *, uint64_t> BlockIndex;
3480   BlockIndex.reserve(F->size());
3481   std::vector<const MachineBasicBlock *> CurrentBlockOrder;
3482   CurrentBlockOrder.reserve(F->size());
3483   size_t NumBlocks = 0;
3484   for (const MachineBasicBlock &MBB : *F) {
3485     BlockIndex[&MBB] = NumBlocks++;
3486     CurrentBlockOrder.push_back(&MBB);
3487   }
3488 
3489   auto BlockSizes = std::vector<uint64_t>(F->size());
3490   auto BlockCounts = std::vector<uint64_t>(F->size());
3491   DenseMap<std::pair<uint64_t, uint64_t>, uint64_t> JumpCounts;
3492   for (MachineBasicBlock &MBB : *F) {
3493     // Getting the block frequency.
3494     BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
3495     BlockCounts[BlockIndex[&MBB]] = BlockFreq.getFrequency();
3496     // Getting the block size:
3497     // - approximate the size of an instruction by 4 bytes, and
3498     // - ignore debug instructions.
3499     // Note: getting the exact size of each block is target-dependent and can be
3500     // done by extending the interface of MCCodeEmitter. Experimentally we do
3501     // not see a perf improvement with the exact block sizes.
3502     auto NonDbgInsts =
3503         instructionsWithoutDebug(MBB.instr_begin(), MBB.instr_end());
3504     int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
3505     BlockSizes[BlockIndex[&MBB]] = 4 * NumInsts;
3506     // Getting jump frequencies.
3507     for (MachineBasicBlock *Succ : MBB.successors()) {
3508       auto EP = MBPI->getEdgeProbability(&MBB, Succ);
3509       BlockFrequency EdgeFreq = BlockFreq * EP;
3510       auto Edge = std::make_pair(BlockIndex[&MBB], BlockIndex[Succ]);
3511       JumpCounts[Edge] = EdgeFreq.getFrequency();
3512     }
3513   }
3514 
3515   LLVM_DEBUG(dbgs() << "Applying ext-tsp layout for |V| = " << F->size()
3516                     << " with profile = " << F->getFunction().hasProfileData()
3517                     << " (" << F->getName().str() << ")"
3518                     << "\n");
3519   LLVM_DEBUG(
3520       dbgs() << format("  original  layout score: %0.2f\n",
3521                        calcExtTspScore(BlockSizes, BlockCounts, JumpCounts)));
3522 
3523   // Run the layout algorithm.
3524   auto NewOrder = applyExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
3525   std::vector<const MachineBasicBlock *> NewBlockOrder;
3526   NewBlockOrder.reserve(F->size());
3527   for (uint64_t Node : NewOrder) {
3528     NewBlockOrder.push_back(CurrentBlockOrder[Node]);
3529   }
3530   LLVM_DEBUG(dbgs() << format("  optimized layout score: %0.2f\n",
3531                               calcExtTspScore(NewOrder, BlockSizes, BlockCounts,
3532                                               JumpCounts)));
3533 
3534   // Assign new block order.
3535   assignBlockOrder(NewBlockOrder);
3536 }
3537 
3538 void MachineBlockPlacement::assignBlockOrder(
3539     const std::vector<const MachineBasicBlock *> &NewBlockOrder) {
3540   assert(F->size() == NewBlockOrder.size() && "Incorrect size of block order");
3541   F->RenumberBlocks();
3542 
3543   bool HasChanges = false;
3544   for (size_t I = 0; I < NewBlockOrder.size(); I++) {
3545     if (NewBlockOrder[I] != F->getBlockNumbered(I)) {
3546       HasChanges = true;
3547       break;
3548     }
3549   }
3550   // Stop early if the new block order is identical to the existing one.
3551   if (!HasChanges)
3552     return;
3553 
3554   SmallVector<MachineBasicBlock *, 4> PrevFallThroughs(F->getNumBlockIDs());
3555   for (auto &MBB : *F) {
3556     PrevFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
3557   }
3558 
3559   // Sort basic blocks in the function according to the computed order.
3560   DenseMap<const MachineBasicBlock *, size_t> NewIndex;
3561   for (const MachineBasicBlock *MBB : NewBlockOrder) {
3562     NewIndex[MBB] = NewIndex.size();
3563   }
3564   F->sort([&](MachineBasicBlock &L, MachineBasicBlock &R) {
3565     return NewIndex[&L] < NewIndex[&R];
3566   });
3567 
3568   // Update basic block branches by inserting explicit fallthrough branches
3569   // when required and re-optimize branches when possible.
3570   const TargetInstrInfo *TII = F->getSubtarget().getInstrInfo();
3571   SmallVector<MachineOperand, 4> Cond;
3572   for (auto &MBB : *F) {
3573     MachineFunction::iterator NextMBB = std::next(MBB.getIterator());
3574     MachineFunction::iterator EndIt = MBB.getParent()->end();
3575     auto *FTMBB = PrevFallThroughs[MBB.getNumber()];
3576     // If this block had a fallthrough before we need an explicit unconditional
3577     // branch to that block if the fallthrough block is not adjacent to the
3578     // block in the new order.
3579     if (FTMBB && (NextMBB == EndIt || &*NextMBB != FTMBB)) {
3580       TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
3581     }
3582 
3583     // It might be possible to optimize branches by flipping the condition.
3584     Cond.clear();
3585     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
3586     if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
3587       continue;
3588     MBB.updateTerminator(FTMBB);
3589   }
3590 
3591 #ifndef NDEBUG
3592   // Make sure we correctly constructed all branches.
3593   F->verify(this, "After optimized block reordering");
3594 #endif
3595 }
3596 
3597 void MachineBlockPlacement::createCFGChainExtTsp() {
3598   BlockToChain.clear();
3599   ComputedEdges.clear();
3600   ChainAllocator.DestroyAll();
3601 
3602   MachineBasicBlock *HeadBB = &F->front();
3603   BlockChain *FunctionChain =
3604       new (ChainAllocator.Allocate()) BlockChain(BlockToChain, HeadBB);
3605 
3606   for (MachineBasicBlock &MBB : *F) {
3607     if (HeadBB == &MBB)
3608       continue; // Ignore head of the chain
3609     FunctionChain->merge(&MBB, nullptr);
3610   }
3611 }
3612 
3613 namespace {
3614 
3615 /// A pass to compute block placement statistics.
3616 ///
3617 /// A separate pass to compute interesting statistics for evaluating block
3618 /// placement. This is separate from the actual placement pass so that they can
3619 /// be computed in the absence of any placement transformations or when using
3620 /// alternative placement strategies.
3621 class MachineBlockPlacementStats : public MachineFunctionPass {
3622   /// A handle to the branch probability pass.
3623   const MachineBranchProbabilityInfo *MBPI;
3624 
3625   /// A handle to the function-wide block frequency pass.
3626   const MachineBlockFrequencyInfo *MBFI;
3627 
3628 public:
3629   static char ID; // Pass identification, replacement for typeid
3630 
3631   MachineBlockPlacementStats() : MachineFunctionPass(ID) {
3632     initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
3633   }
3634 
3635   bool runOnMachineFunction(MachineFunction &F) override;
3636 
3637   void getAnalysisUsage(AnalysisUsage &AU) const override {
3638     AU.addRequired<MachineBranchProbabilityInfo>();
3639     AU.addRequired<MachineBlockFrequencyInfo>();
3640     AU.setPreservesAll();
3641     MachineFunctionPass::getAnalysisUsage(AU);
3642   }
3643 };
3644 
3645 } // end anonymous namespace
3646 
3647 char MachineBlockPlacementStats::ID = 0;
3648 
3649 char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID;
3650 
3651 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
3652                       "Basic Block Placement Stats", false, false)
3653 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
3654 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
3655 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
3656                     "Basic Block Placement Stats", false, false)
3657 
3658 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
3659   // Check for single-block functions and skip them.
3660   if (std::next(F.begin()) == F.end())
3661     return false;
3662 
3663   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
3664   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
3665 
3666   for (MachineBasicBlock &MBB : F) {
3667     BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
3668     Statistic &NumBranches =
3669         (MBB.succ_size() > 1) ? NumCondBranches : NumUncondBranches;
3670     Statistic &BranchTakenFreq =
3671         (MBB.succ_size() > 1) ? CondBranchTakenFreq : UncondBranchTakenFreq;
3672     for (MachineBasicBlock *Succ : MBB.successors()) {
3673       // Skip if this successor is a fallthrough.
3674       if (MBB.isLayoutSuccessor(Succ))
3675         continue;
3676 
3677       BlockFrequency EdgeFreq =
3678           BlockFreq * MBPI->getEdgeProbability(&MBB, Succ);
3679       ++NumBranches;
3680       BranchTakenFreq += EdgeFreq.getFrequency();
3681     }
3682   }
3683 
3684   return false;
3685 }
3686