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