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