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

Generated by: LCOV version 1.13