LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineBlockPlacement.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 690 719 96.0 %
Date: 2018-06-17 00:07:59 Functions: 45 50 90.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13