Coverage Report

Created: 2019-07-24 05:18

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