Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h
Line
Count
Source (jump to first uncovered line)
1
//==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==//
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
// Shared implementation of BlockFrequency for IR and Machine Instructions.
10
// See the documentation below for BlockFrequencyInfoImpl for details.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
15
#define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/ADT/DenseSet.h"
19
#include "llvm/ADT/GraphTraits.h"
20
#include "llvm/ADT/Optional.h"
21
#include "llvm/ADT/PostOrderIterator.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/SparseBitVector.h"
24
#include "llvm/ADT/Twine.h"
25
#include "llvm/ADT/iterator_range.h"
26
#include "llvm/IR/BasicBlock.h"
27
#include "llvm/Support/BlockFrequency.h"
28
#include "llvm/Support/BranchProbability.h"
29
#include "llvm/Support/DOTGraphTraits.h"
30
#include "llvm/Support/Debug.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Support/Format.h"
33
#include "llvm/Support/ScaledNumber.h"
34
#include "llvm/Support/raw_ostream.h"
35
#include <algorithm>
36
#include <cassert>
37
#include <cstddef>
38
#include <cstdint>
39
#include <deque>
40
#include <iterator>
41
#include <limits>
42
#include <list>
43
#include <string>
44
#include <utility>
45
#include <vector>
46
47
#define DEBUG_TYPE "block-freq"
48
49
namespace llvm {
50
51
class BranchProbabilityInfo;
52
class Function;
53
class Loop;
54
class LoopInfo;
55
class MachineBasicBlock;
56
class MachineBranchProbabilityInfo;
57
class MachineFunction;
58
class MachineLoop;
59
class MachineLoopInfo;
60
61
namespace bfi_detail {
62
63
struct IrreducibleGraph;
64
65
// This is part of a workaround for a GCC 4.7 crash on lambdas.
66
template <class BT> struct BlockEdgesAdder;
67
68
/// Mass of a block.
69
///
70
/// This class implements a sort of fixed-point fraction always between 0.0 and
71
/// 1.0.  getMass() == std::numeric_limits<uint64_t>::max() indicates a value of
72
/// 1.0.
73
///
74
/// Masses can be added and subtracted.  Simple saturation arithmetic is used,
75
/// so arithmetic operations never overflow or underflow.
76
///
77
/// Masses can be multiplied.  Multiplication treats full mass as 1.0 and uses
78
/// an inexpensive floating-point algorithm that's off-by-one (almost, but not
79
/// quite, maximum precision).
80
///
81
/// Masses can be scaled by \a BranchProbability at maximum precision.
82
class BlockMass {
83
  uint64_t Mass = 0;
84
85
public:
86
61.3M
  BlockMass() = default;
87
8.42M
  explicit BlockMass(uint64_t Mass) : Mass(Mass) {}
88
89
27.7k
  static BlockMass getEmpty() { return BlockMass(); }
90
91
8.42M
  static BlockMass getFull() {
92
8.42M
    return BlockMass(std::numeric_limits<uint64_t>::max());
93
8.42M
  }
94
95
24.6M
  uint64_t getMass() const { return Mass; }
96
97
30.6M
  bool isFull() const { return Mass == std::numeric_limits<uint64_t>::max(); }
98
2.04M
  bool isEmpty() const { return !Mass; }
99
100
0
  bool operator!() const { return isEmpty(); }
101
102
  /// Add another mass.
103
  ///
104
  /// Adds another mass, saturating at \a isFull() rather than overflowing.
105
35.9M
  BlockMass &operator+=(BlockMass X) {
106
35.9M
    uint64_t Sum = Mass + X.Mass;
107
35.9M
    Mass = Sum < Mass ? 
std::numeric_limits<uint64_t>::max()0
: Sum;
108
35.9M
    return *this;
109
35.9M
  }
110
111
  /// Subtract another mass.
112
  ///
113
  /// Subtracts another mass, saturating at \a isEmpty() rather than
114
  /// undeflowing.
115
38.6M
  BlockMass &operator-=(BlockMass X) {
116
38.6M
    uint64_t Diff = Mass - X.Mass;
117
38.6M
    Mass = Diff > Mass ? 
00
: Diff;
118
38.6M
    return *this;
119
38.6M
  }
120
121
36.6M
  BlockMass &operator*=(BranchProbability P) {
122
36.6M
    Mass = P.scale(Mass);
123
36.6M
    return *this;
124
36.6M
  }
125
126
0
  bool operator==(BlockMass X) const { return Mass == X.Mass; }
127
0
  bool operator!=(BlockMass X) const { return Mass != X.Mass; }
128
0
  bool operator<=(BlockMass X) const { return Mass <= X.Mass; }
129
0
  bool operator>=(BlockMass X) const { return Mass >= X.Mass; }
130
0
  bool operator<(BlockMass X) const { return Mass < X.Mass; }
131
0
  bool operator>(BlockMass X) const { return Mass > X.Mass; }
132
133
  /// Convert to scaled number.
134
  ///
135
  /// Convert to \a ScaledNumber.  \a isFull() gives 1.0, while \a isEmpty()
136
  /// gives slightly above 0.0.
137
  ScaledNumber<uint64_t> toScaled() const;
138
139
  void dump() const;
140
  raw_ostream &print(raw_ostream &OS) const;
141
};
142
143
0
inline BlockMass operator+(BlockMass L, BlockMass R) {
144
0
  return BlockMass(L) += R;
145
0
}
146
2.04M
inline BlockMass operator-(BlockMass L, BlockMass R) {
147
2.04M
  return BlockMass(L) -= R;
148
2.04M
}
149
36.6M
inline BlockMass operator*(BlockMass L, BranchProbability R) {
150
36.6M
  return BlockMass(L) *= R;
151
36.6M
}
152
0
inline BlockMass operator*(BranchProbability L, BlockMass R) {
153
0
  return BlockMass(R) *= L;
154
0
}
155
156
0
inline raw_ostream &operator<<(raw_ostream &OS, BlockMass X) {
157
0
  return X.print(OS);
158
0
}
159
160
} // end namespace bfi_detail
161
162
/// Base class for BlockFrequencyInfoImpl
163
///
164
/// BlockFrequencyInfoImplBase has supporting data structures and some
165
/// algorithms for BlockFrequencyInfoImplBase.  Only algorithms that depend on
166
/// the block type (or that call such algorithms) are skipped here.
167
///
168
/// Nevertheless, the majority of the overall algorithm documention lives with
169
/// BlockFrequencyInfoImpl.  See there for details.
170
class BlockFrequencyInfoImplBase {
171
public:
172
  using Scaled64 = ScaledNumber<uint64_t>;
173
  using BlockMass = bfi_detail::BlockMass;
174
175
  /// Representative of a block.
176
  ///
177
  /// This is a simple wrapper around an index into the reverse-post-order
178
  /// traversal of the blocks.
179
  ///
180
  /// Unlike a block pointer, its order has meaning (location in the
181
  /// topological sort) and it's class is the same regardless of block type.
182
  struct BlockNode {
183
    using IndexType = uint32_t;
184
185
    IndexType Index;
186
187
26.7M
    BlockNode() : Index(std::numeric_limits<uint32_t>::max()) {}
188
85.0M
    BlockNode(IndexType Index) : Index(Index) {}
189
190
74.1M
    bool operator==(const BlockNode &X) const { return Index == X.Index; }
191
26.6M
    bool operator!=(const BlockNode &X) const { return Index != X.Index; }
192
0
    bool operator<=(const BlockNode &X) const { return Index <= X.Index; }
193
0
    bool operator>=(const BlockNode &X) const { return Index >= X.Index; }
194
46.8M
    bool operator<(const BlockNode &X) const { return Index < X.Index; }
195
0
    bool operator>(const BlockNode &X) const { return Index > X.Index; }
196
197
48.2M
    bool isValid() const { return Index <= getMaxIndex(); }
198
199
48.2M
    static size_t getMaxIndex() {
200
48.2M
       return std::numeric_limits<uint32_t>::max() - 1;
201
48.2M
    }
202
  };
203
204
  /// Stats about a block itself.
205
  struct FrequencyData {
206
    Scaled64 Scaled;
207
    uint64_t Integer;
208
  };
209
210
  /// Data about a loop.
211
  ///
212
  /// Contains the data necessary to represent a loop as a pseudo-node once it's
213
  /// packaged.
214
  struct LoopData {
215
    using ExitMap = SmallVector<std::pair<BlockNode, BlockMass>, 4>;
216
    using NodeList = SmallVector<BlockNode, 4>;
217
    using HeaderMassList = SmallVector<BlockMass, 1>;
218
219
    LoopData *Parent;            ///< The parent loop.
220
    bool IsPackaged = false;     ///< Whether this has been packaged.
221
    uint32_t NumHeaders = 1;     ///< Number of headers.
222
    ExitMap Exits;               ///< Successor edges (and weights).
223
    NodeList Nodes;              ///< Header and the members of the loop.
224
    HeaderMassList BackedgeMass; ///< Mass returned to each loop header.
225
    BlockMass Mass;
226
    Scaled64 Scale;
227
228
    LoopData(LoopData *Parent, const BlockNode &Header)
229
2.04M
      : Parent(Parent), Nodes(1, Header), BackedgeMass(1) {}
230
231
    template <class It1, class It2>
232
    LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther,
233
             It2 LastOther)
234
833
        : Parent(Parent), Nodes(FirstHeader, LastHeader) {
235
833
      NumHeaders = Nodes.size();
236
833
      Nodes.insert(Nodes.end(), FirstOther, LastOther);
237
833
      BackedgeMass.resize(NumHeaders);
238
833
    }
239
240
60.8M
    bool isHeader(const BlockNode &Node) const {
241
60.8M
      if (isIrreducible())
242
83.8k
        return std::binary_search(Nodes.begin(), Nodes.begin() + NumHeaders,
243
83.8k
                                  Node);
244
60.7M
      return Node == Nodes[0];
245
60.7M
    }
246
247
15.6M
    BlockNode getHeader() const { return Nodes[0]; }
248
67.1M
    bool isIrreducible() const { return NumHeaders > 1; }
249
250
2.07M
    HeaderMassList::difference_type getHeaderIndex(const BlockNode &B) {
251
2.07M
      assert(isHeader(B) && "this is only valid on loop header blocks");
252
2.07M
      if (isIrreducible())
253
7.61k
        return std::lower_bound(Nodes.begin(), Nodes.begin() + NumHeaders, B) -
254
7.61k
               Nodes.begin();
255
2.06M
      return 0;
256
2.06M
    }
257
258
2.04M
    NodeList::const_iterator members_begin() const {
259
2.04M
      return Nodes.begin() + NumHeaders;
260
2.04M
    }
261
262
2.04M
    NodeList::const_iterator members_end() const { return Nodes.end(); }
263
2.04M
    iterator_range<NodeList::const_iterator> members() const {
264
2.04M
      return make_range(members_begin(), members_end());
265
2.04M
    }
266
  };
267
268
  /// Index of loop information.
269
  struct WorkingData {
270
    BlockNode Node;           ///< This node.
271
    LoopData *Loop = nullptr; ///< The loop this block is inside.
272
    BlockMass Mass;           ///< Mass distribution from the entry block.
273
274
26.5M
    WorkingData(const BlockNode &Node) : Node(Node) {}
275
276
136M
    bool isLoopHeader() const { return Loop && 
Loop->isHeader(Node)48.6M
; }
277
278
8.23M
    bool isDoubleLoopHeader() const {
279
8.23M
      return isLoopHeader() && Loop->Parent && 
Loop->Parent->isIrreducible()2.19M
&&
280
8.23M
             
Loop->Parent->isHeader(Node)4.69k
;
281
8.23M
    }
282
283
36.8M
    LoopData *getContainingLoop() const {
284
36.8M
      if (!isLoopHeader())
285
32.7M
        return Loop;
286
4.12M
      if (!isDoubleLoopHeader())
287
4.12M
        return Loop->Parent;
288
193
      return Loop->Parent->Parent;
289
193
    }
290
291
    /// Resolve a node to its representative.
292
    ///
293
    /// Get the node currently representing Node, which could be a containing
294
    /// loop.
295
    ///
296
    /// This function should only be called when distributing mass.  As long as
297
    /// there are no irreducible edges to Node, then it will have complexity
298
    /// O(1) in this context.
299
    ///
300
    /// In general, the complexity is O(L), where L is the number of loop
301
    /// headers Node has been packaged into.  Since this method is called in
302
    /// the context of distributing mass, L will be the number of loop headers
303
    /// an early exit edge jumps out of.
304
63.5M
    BlockNode getResolvedNode() const {
305
63.5M
      auto L = getPackagedLoop();
306
63.5M
      return L ? 
L->getHeader()8.75M
:
Node54.7M
;
307
63.5M
    }
308
309
99.9M
    LoopData *getPackagedLoop() const {
310
99.9M
      if (!Loop || 
!Loop->IsPackaged34.7M
)
311
88.0M
        return nullptr;
312
11.8M
      auto L = Loop;
313
14.1M
      while (L->Parent && 
L->Parent->IsPackaged4.48M
)
314
2.28M
        L = L->Parent;
315
11.8M
      return L;
316
11.8M
    }
317
318
    /// Get the appropriate mass for a node.
319
    ///
320
    /// Get appropriate mass for Node.  If Node is a loop-header (whose loop
321
    /// has been packaged), returns the mass of its pseudo-node.  If it's a
322
    /// node inside a packaged loop, it returns the loop's mass.
323
66.8M
    BlockMass &getMass() {
324
66.8M
      if (!isAPackage())
325
62.7M
        return Mass;
326
4.10M
      if (!isADoublePackage())
327
4.10M
        return Loop->Mass;
328
141
      return Loop->Parent->Mass;
329
141
    }
330
331
    /// Has ContainingLoop been packaged up?
332
26.6M
    bool isPackaged() const { return getResolvedNode() != Node; }
333
334
    /// Has Loop been packaged up?
335
74.1M
    bool isAPackage() const { return isLoopHeader() && 
Loop->IsPackaged10.7M
; }
336
337
    /// Has Loop been packaged up twice?
338
4.10M
    bool isADoublePackage() const {
339
4.10M
      return isDoubleLoopHeader() && 
Loop->Parent->IsPackaged810
;
340
4.10M
    }
341
  };
342
343
  /// Unscaled probability weight.
344
  ///
345
  /// Probability weight for an edge in the graph (including the
346
  /// successor/target node).
347
  ///
348
  /// All edges in the original function are 32-bit.  However, exit edges from
349
  /// loop packages are taken from 64-bit exit masses, so we need 64-bits of
350
  /// space in general.
351
  ///
352
  /// In addition to the raw weight amount, Weight stores the type of the edge
353
  /// in the current context (i.e., the context of the loop being processed).
354
  /// Is this a local edge within the loop, an exit from the loop, or a
355
  /// backedge to the loop header?
356
  struct Weight {
357
    enum DistType { Local, Exit, Backedge };
358
    DistType Type = Local;
359
    BlockNode TargetNode;
360
    uint64_t Amount = 0;
361
362
16.7k
    Weight() = default;
363
    Weight(DistType Type, BlockNode TargetNode, uint64_t Amount)
364
36.9M
        : Type(Type), TargetNode(TargetNode), Amount(Amount) {}
365
  };
366
367
  /// Distribution of unscaled probability weight.
368
  ///
369
  /// Distribution of unscaled probability weight to a set of successors.
370
  ///
371
  /// This class collates the successor edge weights for later processing.
372
  ///
373
  /// \a DidOverflow indicates whether \a Total did overflow while adding to
374
  /// the distribution.  It should never overflow twice.
375
  struct Distribution {
376
    using WeightList = SmallVector<Weight, 4>;
377
378
    WeightList Weights;       ///< Individual successor weights.
379
    uint64_t Total = 0;       ///< Sum of all weights.
380
    bool DidOverflow = false; ///< Whether \a Total did overflow.
381
382
28.6M
    Distribution() = default;
383
384
32.0M
    void addLocal(const BlockNode &Node, uint64_t Amount) {
385
32.0M
      add(Node, Amount, Weight::Local);
386
32.0M
    }
387
388
2.80M
    void addExit(const BlockNode &Node, uint64_t Amount) {
389
2.80M
      add(Node, Amount, Weight::Exit);
390
2.80M
    }
391
392
2.07M
    void addBackedge(const BlockNode &Node, uint64_t Amount) {
393
2.07M
      add(Node, Amount, Weight::Backedge);
394
2.07M
    }
395
396
    /// Normalize the distribution.
397
    ///
398
    /// Combines multiple edges to the same \a Weight::TargetNode and scales
399
    /// down so that \a Total fits into 32-bits.
400
    ///
401
    /// This is linear in the size of \a Weights.  For the vast majority of
402
    /// cases, adjacent edge weights are combined by sorting WeightList and
403
    /// combining adjacent weights.  However, for very large edge lists an
404
    /// auxiliary hash table is used.
405
    void normalize();
406
407
  private:
408
    void add(const BlockNode &Node, uint64_t Amount, Weight::DistType Type);
409
  };
410
411
  /// Data about each block.  This is used downstream.
412
  std::vector<FrequencyData> Freqs;
413
414
  /// Whether each block is an irreducible loop header.
415
  /// This is used downstream.
416
  SparseBitVector<> IsIrrLoopHeader;
417
418
  /// Loop data: see initializeLoops().
419
  std::vector<WorkingData> Working;
420
421
  /// Indexed information about loops.
422
  std::list<LoopData> Loops;
423
424
  /// Virtual destructor.
425
  ///
426
  /// Need a virtual destructor to mask the compiler warning about
427
  /// getBlockName().
428
4.33M
  virtual ~BlockFrequencyInfoImplBase() = default;
429
430
  /// Add all edges out of a packaged loop to the distribution.
431
  ///
432
  /// Adds all edges from LocalLoopHead to Dist.  Calls addToDist() to add each
433
  /// successor edge.
434
  ///
435
  /// \return \c true unless there's an irreducible backedge.
436
  bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop,
437
                               Distribution &Dist);
438
439
  /// Add an edge to the distribution.
440
  ///
441
  /// Adds an edge to Succ to Dist.  If \c LoopHead.isValid(), then whether the
442
  /// edge is local/exit/backedge is in the context of LoopHead.  Otherwise,
443
  /// every edge should be a local edge (since all the loops are packaged up).
444
  ///
445
  /// \return \c true unless aborted due to an irreducible backedge.
446
  bool addToDist(Distribution &Dist, const LoopData *OuterLoop,
447
                 const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight);
448
449
0
  LoopData &getLoopPackage(const BlockNode &Head) {
450
0
    assert(Head.Index < Working.size());
451
0
    assert(Working[Head.Index].isLoopHeader());
452
0
    return *Working[Head.Index].Loop;
453
0
  }
454
455
  /// Analyze irreducible SCCs.
456
  ///
457
  /// Separate irreducible SCCs from \c G, which is an explict graph of \c
458
  /// OuterLoop (or the top-level function, if \c OuterLoop is \c nullptr).
459
  /// Insert them into \a Loops before \c Insert.
460
  ///
461
  /// \return the \c LoopData nodes representing the irreducible SCCs.
462
  iterator_range<std::list<LoopData>::iterator>
463
  analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop,
464
                     std::list<LoopData>::iterator Insert);
465
466
  /// Update a loop after packaging irreducible SCCs inside of it.
467
  ///
468
  /// Update \c OuterLoop.  Before finding irreducible control flow, it was
469
  /// partway through \a computeMassInLoop(), so \a LoopData::Exits and \a
470
  /// LoopData::BackedgeMass need to be reset.  Also, nodes that were packaged
471
  /// up need to be removed from \a OuterLoop::Nodes.
472
  void updateLoopWithIrreducible(LoopData &OuterLoop);
473
474
  /// Distribute mass according to a distribution.
475
  ///
476
  /// Distributes the mass in Source according to Dist.  If LoopHead.isValid(),
477
  /// backedges and exits are stored in its entry in Loops.
478
  ///
479
  /// Mass is distributed in parallel from two copies of the source mass.
480
  void distributeMass(const BlockNode &Source, LoopData *OuterLoop,
481
                      Distribution &Dist);
482
483
  /// Compute the loop scale for a loop.
484
  void computeLoopScale(LoopData &Loop);
485
486
  /// Adjust the mass of all headers in an irreducible loop.
487
  ///
488
  /// Initially, irreducible loops are assumed to distribute their mass
489
  /// equally among its headers. This can lead to wrong frequency estimates
490
  /// since some headers may be executed more frequently than others.
491
  ///
492
  /// This adjusts header mass distribution so it matches the weights of
493
  /// the backedges going into each of the loop headers.
494
  void adjustLoopHeaderMass(LoopData &Loop);
495
496
  void distributeIrrLoopHeaderMass(Distribution &Dist);
497
498
  /// Package up a loop.
499
  void packageLoop(LoopData &Loop);
500
501
  /// Unwrap loops.
502
  void unwrapLoops();
503
504
  /// Finalize frequency metrics.
505
  ///
506
  /// Calculates final frequencies and cleans up no-longer-needed data
507
  /// structures.
508
  void finalizeMetrics();
509
510
  /// Clear all memory.
511
  void clear();
512
513
  virtual std::string getBlockName(const BlockNode &Node) const;
514
  std::string getLoopName(const LoopData &Loop) const;
515
516
0
  virtual raw_ostream &print(raw_ostream &OS) const { return OS; }
517
0
  void dump() const { print(dbgs()); }
518
519
  Scaled64 getFloatingBlockFreq(const BlockNode &Node) const;
520
521
  BlockFrequency getBlockFreq(const BlockNode &Node) const;
522
  Optional<uint64_t> getBlockProfileCount(const Function &F,
523
                                          const BlockNode &Node,
524
                                          bool AllowSynthetic = false) const;
525
  Optional<uint64_t> getProfileCountFromFreq(const Function &F,
526
                                             uint64_t Freq,
527
                                             bool AllowSynthetic = false) const;
528
  bool isIrrLoopHeader(const BlockNode &Node);
529
530
  void setBlockFreq(const BlockNode &Node, uint64_t Freq);
531
532
  raw_ostream &printBlockFreq(raw_ostream &OS, const BlockNode &Node) const;
533
  raw_ostream &printBlockFreq(raw_ostream &OS,
534
                              const BlockFrequency &Freq) const;
535
536
25.9M
  uint64_t getEntryFreq() const {
537
25.9M
    assert(!Freqs.empty());
538
25.9M
    return Freqs[0].Integer;
539
25.9M
  }
540
};
541
542
namespace bfi_detail {
543
544
template <class BlockT> struct TypeMap {};
545
template <> struct TypeMap<BasicBlock> {
546
  using BlockT = BasicBlock;
547
  using FunctionT = Function;
548
  using BranchProbabilityInfoT = BranchProbabilityInfo;
549
  using LoopT = Loop;
550
  using LoopInfoT = LoopInfo;
551
};
552
template <> struct TypeMap<MachineBasicBlock> {
553
  using BlockT = MachineBasicBlock;
554
  using FunctionT = MachineFunction;
555
  using BranchProbabilityInfoT = MachineBranchProbabilityInfo;
556
  using LoopT = MachineLoop;
557
  using LoopInfoT = MachineLoopInfo;
558
};
559
560
/// Get the name of a MachineBasicBlock.
561
///
562
/// Get the name of a MachineBasicBlock.  It's templated so that including from
563
/// CodeGen is unnecessary (that would be a layering issue).
564
///
565
/// This is used mainly for debug output.  The name is similar to
566
/// MachineBasicBlock::getFullName(), but skips the name of the function.
567
77
template <class BlockT> std::string getBlockName(const BlockT *BB) {
568
77
  assert(BB && "Unexpected nullptr");
569
77
  auto MachineName = "BB" + Twine(BB->getNumber());
570
77
  if (BB->getBasicBlock())
571
77
    return (MachineName + "[" + BB->getName() + "]").str();
572
0
  return MachineName.str();
573
0
}
574
/// Get the name of a BasicBlock.
575
532
template <> inline std::string getBlockName(const BasicBlock *BB) {
576
532
  assert(BB && "Unexpected nullptr");
577
532
  return BB->getName().str();
578
532
}
579
580
/// Graph of irreducible control flow.
581
///
582
/// This graph is used for determining the SCCs in a loop (or top-level
583
/// function) that has irreducible control flow.
584
///
585
/// During the block frequency algorithm, the local graphs are defined in a
586
/// light-weight way, deferring to the \a BasicBlock or \a MachineBasicBlock
587
/// graphs for most edges, but getting others from \a LoopData::ExitMap.  The
588
/// latter only has successor information.
589
///
590
/// \a IrreducibleGraph makes this graph explicit.  It's in a form that can use
591
/// \a GraphTraits (so that \a analyzeIrreducible() can use \a scc_iterator),
592
/// and it explicitly lists predecessors and successors.  The initialization
593
/// that relies on \c MachineBasicBlock is defined in the header.
594
struct IrreducibleGraph {
595
  using BFIBase = BlockFrequencyInfoImplBase;
596
597
  BFIBase &BFI;
598
599
  using BlockNode = BFIBase::BlockNode;
600
  struct IrrNode {
601
    BlockNode Node;
602
    unsigned NumIn = 0;
603
    std::deque<const IrrNode *> Edges;
604
605
27.6k
    IrrNode(const BlockNode &Node) : Node(Node) {}
606
607
    using iterator = std::deque<const IrrNode *>::const_iterator;
608
609
22.1k
    iterator pred_begin() const { return Edges.begin(); }
610
49.8k
    iterator succ_begin() const { return Edges.begin() + NumIn; }
611
22.1k
    iterator pred_end() const { return succ_begin(); }
612
69.6k
    iterator succ_end() const { return Edges.end(); }
613
  };
614
  BlockNode Start;
615
  const IrrNode *StartIrr = nullptr;
616
  std::vector<IrrNode> Nodes;
617
  SmallDenseMap<uint32_t, IrrNode *, 4> Lookup;
618
619
  /// Construct an explicit graph containing irreducible control flow.
620
  ///
621
  /// Construct an explicit graph of the control flow in \c OuterLoop (or the
622
  /// top-level function, if \c OuterLoop is \c nullptr).  Uses \c
623
  /// addBlockEdges to add block successors that have not been packaged into
624
  /// loops.
625
  ///
626
  /// \a BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected
627
  /// user of this.
628
  template <class BlockEdgesAdder>
629
  IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop,
630
717
                   BlockEdgesAdder addBlockEdges) : BFI(BFI) {
631
717
    initialize(OuterLoop, addBlockEdges);
632
717
  }
llvm::bfi_detail::IrreducibleGraph::IrreducibleGraph<llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock> >(llvm::BlockFrequencyInfoImplBase&, llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock>)
Line
Count
Source
630
346
                   BlockEdgesAdder addBlockEdges) : BFI(BFI) {
631
346
    initialize(OuterLoop, addBlockEdges);
632
346
  }
llvm::bfi_detail::IrreducibleGraph::IrreducibleGraph<llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock> >(llvm::BlockFrequencyInfoImplBase&, llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock>)
Line
Count
Source
630
371
                   BlockEdgesAdder addBlockEdges) : BFI(BFI) {
631
371
    initialize(OuterLoop, addBlockEdges);
632
371
  }
633
634
  template <class BlockEdgesAdder>
635
  void initialize(const BFIBase::LoopData *OuterLoop,
636
                  BlockEdgesAdder addBlockEdges);
637
  void addNodesInLoop(const BFIBase::LoopData &OuterLoop);
638
  void addNodesInFunction();
639
640
27.6k
  void addNode(const BlockNode &Node) {
641
27.6k
    Nodes.emplace_back(Node);
642
27.6k
    BFI.Working[Node.Index].getMass() = BlockMass::getEmpty();
643
27.6k
  }
644
645
  void indexNodes();
646
  template <class BlockEdgesAdder>
647
  void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop,
648
                BlockEdgesAdder addBlockEdges);
649
  void addEdge(IrrNode &Irr, const BlockNode &Succ,
650
               const BFIBase::LoopData *OuterLoop);
651
};
652
653
template <class BlockEdgesAdder>
654
void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop,
655
717
                                  BlockEdgesAdder addBlockEdges) {
656
717
  if (OuterLoop) {
657
142
    addNodesInLoop(*OuterLoop);
658
142
    for (auto N : OuterLoop->Nodes)
659
6.67k
      addEdges(N, OuterLoop, addBlockEdges);
660
575
  } else {
661
575
    addNodesInFunction();
662
23.9k
    for (uint32_t Index = 0; Index < BFI.Working.size(); 
++Index23.3k
)
663
23.3k
      addEdges(Index, OuterLoop, addBlockEdges);
664
575
  }
665
717
  StartIrr = Lookup[Start.Index];
666
717
}
void llvm::bfi_detail::IrreducibleGraph::initialize<llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock> >(llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock>)
Line
Count
Source
655
346
                                  BlockEdgesAdder addBlockEdges) {
656
346
  if (OuterLoop) {
657
72
    addNodesInLoop(*OuterLoop);
658
72
    for (auto N : OuterLoop->Nodes)
659
3.23k
      addEdges(N, OuterLoop, addBlockEdges);
660
274
  } else {
661
274
    addNodesInFunction();
662
11.9k
    for (uint32_t Index = 0; Index < BFI.Working.size(); 
++Index11.7k
)
663
11.7k
      addEdges(Index, OuterLoop, addBlockEdges);
664
274
  }
665
346
  StartIrr = Lookup[Start.Index];
666
346
}
void llvm::bfi_detail::IrreducibleGraph::initialize<llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock> >(llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock>)
Line
Count
Source
655
371
                                  BlockEdgesAdder addBlockEdges) {
656
371
  if (OuterLoop) {
657
70
    addNodesInLoop(*OuterLoop);
658
70
    for (auto N : OuterLoop->Nodes)
659
3.43k
      addEdges(N, OuterLoop, addBlockEdges);
660
301
  } else {
661
301
    addNodesInFunction();
662
11.9k
    for (uint32_t Index = 0; Index < BFI.Working.size(); 
++Index11.6k
)
663
11.6k
      addEdges(Index, OuterLoop, addBlockEdges);
664
301
  }
665
371
  StartIrr = Lookup[Start.Index];
666
371
}
667
668
template <class BlockEdgesAdder>
669
void IrreducibleGraph::addEdges(const BlockNode &Node,
670
                                const BFIBase::LoopData *OuterLoop,
671
30.0k
                                BlockEdgesAdder addBlockEdges) {
672
30.0k
  auto L = Lookup.find(Node.Index);
673
30.0k
  if (L == Lookup.end())
674
2.41k
    return;
675
27.6k
  IrrNode &Irr = *L->second;
676
27.6k
  const auto &Working = BFI.Working[Node.Index];
677
27.6k
678
27.6k
  if (Working.isAPackage())
679
2.44k
    for (const auto &I : Working.Loop->Exits)
680
7.09k
      addEdge(Irr, I.first, OuterLoop);
681
25.1k
  else
682
25.1k
    addBlockEdges(*this, Irr, OuterLoop);
683
27.6k
}
void llvm::bfi_detail::IrreducibleGraph::addEdges<llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock> >(llvm::BlockFrequencyInfoImplBase::BlockNode const&, llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock>)
Line
Count
Source
671
14.9k
                                BlockEdgesAdder addBlockEdges) {
672
14.9k
  auto L = Lookup.find(Node.Index);
673
14.9k
  if (L == Lookup.end())
674
1.36k
    return;
675
13.5k
  IrrNode &Irr = *L->second;
676
13.5k
  const auto &Working = BFI.Working[Node.Index];
677
13.5k
678
13.5k
  if (Working.isAPackage())
679
1.01k
    for (const auto &I : Working.Loop->Exits)
680
2.67k
      addEdge(Irr, I.first, OuterLoop);
681
12.5k
  else
682
12.5k
    addBlockEdges(*this, Irr, OuterLoop);
683
13.5k
}
void llvm::bfi_detail::IrreducibleGraph::addEdges<llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock> >(llvm::BlockFrequencyInfoImplBase::BlockNode const&, llvm::BlockFrequencyInfoImplBase::LoopData const*, llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock>)
Line
Count
Source
671
15.1k
                                BlockEdgesAdder addBlockEdges) {
672
15.1k
  auto L = Lookup.find(Node.Index);
673
15.1k
  if (L == Lookup.end())
674
1.05k
    return;
675
14.0k
  IrrNode &Irr = *L->second;
676
14.0k
  const auto &Working = BFI.Working[Node.Index];
677
14.0k
678
14.0k
  if (Working.isAPackage())
679
1.42k
    for (const auto &I : Working.Loop->Exits)
680
4.41k
      addEdge(Irr, I.first, OuterLoop);
681
12.6k
  else
682
12.6k
    addBlockEdges(*this, Irr, OuterLoop);
683
14.0k
}
684
685
} // end namespace bfi_detail
686
687
/// Shared implementation for block frequency analysis.
688
///
689
/// This is a shared implementation of BlockFrequencyInfo and
690
/// MachineBlockFrequencyInfo, and calculates the relative frequencies of
691
/// blocks.
692
///
693
/// LoopInfo defines a loop as a "non-trivial" SCC dominated by a single block,
694
/// which is called the header.  A given loop, L, can have sub-loops, which are
695
/// loops within the subgraph of L that exclude its header.  (A "trivial" SCC
696
/// consists of a single block that does not have a self-edge.)
697
///
698
/// In addition to loops, this algorithm has limited support for irreducible
699
/// SCCs, which are SCCs with multiple entry blocks.  Irreducible SCCs are
700
/// discovered on they fly, and modelled as loops with multiple headers.
701
///
702
/// The headers of irreducible sub-SCCs consist of its entry blocks and all
703
/// nodes that are targets of a backedge within it (excluding backedges within
704
/// true sub-loops).  Block frequency calculations act as if a block is
705
/// inserted that intercepts all the edges to the headers.  All backedges and
706
/// entries point to this block.  Its successors are the headers, which split
707
/// the frequency evenly.
708
///
709
/// This algorithm leverages BlockMass and ScaledNumber to maintain precision,
710
/// separates mass distribution from loop scaling, and dithers to eliminate
711
/// probability mass loss.
712
///
713
/// The implementation is split between BlockFrequencyInfoImpl, which knows the
714
/// type of graph being modelled (BasicBlock vs. MachineBasicBlock), and
715
/// BlockFrequencyInfoImplBase, which doesn't.  The base class uses \a
716
/// BlockNode, a wrapper around a uint32_t.  BlockNode is numbered from 0 in
717
/// reverse-post order.  This gives two advantages:  it's easy to compare the
718
/// relative ordering of two nodes, and maps keyed on BlockT can be represented
719
/// by vectors.
720
///
721
/// This algorithm is O(V+E), unless there is irreducible control flow, in
722
/// which case it's O(V*E) in the worst case.
723
///
724
/// These are the main stages:
725
///
726
///  0. Reverse post-order traversal (\a initializeRPOT()).
727
///
728
///     Run a single post-order traversal and save it (in reverse) in RPOT.
729
///     All other stages make use of this ordering.  Save a lookup from BlockT
730
///     to BlockNode (the index into RPOT) in Nodes.
731
///
732
///  1. Loop initialization (\a initializeLoops()).
733
///
734
///     Translate LoopInfo/MachineLoopInfo into a form suitable for the rest of
735
///     the algorithm.  In particular, store the immediate members of each loop
736
///     in reverse post-order.
737
///
738
///  2. Calculate mass and scale in loops (\a computeMassInLoops()).
739
///
740
///     For each loop (bottom-up), distribute mass through the DAG resulting
741
///     from ignoring backedges and treating sub-loops as a single pseudo-node.
742
///     Track the backedge mass distributed to the loop header, and use it to
743
///     calculate the loop scale (number of loop iterations).  Immediate
744
///     members that represent sub-loops will already have been visited and
745
///     packaged into a pseudo-node.
746
///
747
///     Distributing mass in a loop is a reverse-post-order traversal through
748
///     the loop.  Start by assigning full mass to the Loop header.  For each
749
///     node in the loop:
750
///
751
///         - Fetch and categorize the weight distribution for its successors.
752
///           If this is a packaged-subloop, the weight distribution is stored
753
///           in \a LoopData::Exits.  Otherwise, fetch it from
754
///           BranchProbabilityInfo.
755
///
756
///         - Each successor is categorized as \a Weight::Local, a local edge
757
///           within the current loop, \a Weight::Backedge, a backedge to the
758
///           loop header, or \a Weight::Exit, any successor outside the loop.
759
///           The weight, the successor, and its category are stored in \a
760
///           Distribution.  There can be multiple edges to each successor.
761
///
762
///         - If there's a backedge to a non-header, there's an irreducible SCC.
763
///           The usual flow is temporarily aborted.  \a
764
///           computeIrreducibleMass() finds the irreducible SCCs within the
765
///           loop, packages them up, and restarts the flow.
766
///
767
///         - Normalize the distribution:  scale weights down so that their sum
768
///           is 32-bits, and coalesce multiple edges to the same node.
769
///
770
///         - Distribute the mass accordingly, dithering to minimize mass loss,
771
///           as described in \a distributeMass().
772
///
773
///     In the case of irreducible loops, instead of a single loop header,
774
///     there will be several. The computation of backedge masses is similar
775
///     but instead of having a single backedge mass, there will be one
776
///     backedge per loop header. In these cases, each backedge will carry
777
///     a mass proportional to the edge weights along the corresponding
778
///     path.
779
///
780
///     At the end of propagation, the full mass assigned to the loop will be
781
///     distributed among the loop headers proportionally according to the
782
///     mass flowing through their backedges.
783
///
784
///     Finally, calculate the loop scale from the accumulated backedge mass.
785
///
786
///  3. Distribute mass in the function (\a computeMassInFunction()).
787
///
788
///     Finally, distribute mass through the DAG resulting from packaging all
789
///     loops in the function.  This uses the same algorithm as distributing
790
///     mass in a loop, except that there are no exit or backedge edges.
791
///
792
///  4. Unpackage loops (\a unwrapLoops()).
793
///
794
///     Initialize each block's frequency to a floating point representation of
795
///     its mass.
796
///
797
///     Visit loops top-down, scaling the frequencies of its immediate members
798
///     by the loop's pseudo-node's frequency.
799
///
800
///  5. Convert frequencies to a 64-bit range (\a finalizeMetrics()).
801
///
802
///     Using the min and max frequencies as a guide, translate floating point
803
///     frequencies to an appropriate range in uint64_t.
804
///
805
/// It has some known flaws.
806
///
807
///   - The model of irreducible control flow is a rough approximation.
808
///
809
///     Modelling irreducible control flow exactly involves setting up and
810
///     solving a group of infinite geometric series.  Such precision is
811
///     unlikely to be worthwhile, since most of our algorithms give up on
812
///     irreducible control flow anyway.
813
///
814
///     Nevertheless, we might find that we need to get closer.  Here's a sort
815
///     of TODO list for the model with diminishing returns, to be completed as
816
///     necessary.
817
///
818
///       - The headers for the \a LoopData representing an irreducible SCC
819
///         include non-entry blocks.  When these extra blocks exist, they
820
///         indicate a self-contained irreducible sub-SCC.  We could treat them
821
///         as sub-loops, rather than arbitrarily shoving the problematic
822
///         blocks into the headers of the main irreducible SCC.
823
///
824
///       - Entry frequencies are assumed to be evenly split between the
825
///         headers of a given irreducible SCC, which is the only option if we
826
///         need to compute mass in the SCC before its parent loop.  Instead,
827
///         we could partially compute mass in the parent loop, and stop when
828
///         we get to the SCC.  Here, we have the correct ratio of entry
829
///         masses, which we can use to adjust their relative frequencies.
830
///         Compute mass in the SCC, and then continue propagation in the
831
///         parent.
832
///
833
///       - We can propagate mass iteratively through the SCC, for some fixed
834
///         number of iterations.  Each iteration starts by assigning the entry
835
///         blocks their backedge mass from the prior iteration.  The final
836
///         mass for each block (and each exit, and the total backedge mass
837
///         used for computing loop scale) is the sum of all iterations.
838
///         (Running this until fixed point would "solve" the geometric
839
///         series by simulation.)
840
template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase {
841
  // This is part of a workaround for a GCC 4.7 crash on lambdas.
842
  friend struct bfi_detail::BlockEdgesAdder<BT>;
843
844
  using BlockT = typename bfi_detail::TypeMap<BT>::BlockT;
845
  using FunctionT = typename bfi_detail::TypeMap<BT>::FunctionT;
846
  using BranchProbabilityInfoT =
847
      typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT;
848
  using LoopT = typename bfi_detail::TypeMap<BT>::LoopT;
849
  using LoopInfoT = typename bfi_detail::TypeMap<BT>::LoopInfoT;
850
  using Successor = GraphTraits<const BlockT *>;
851
  using Predecessor = GraphTraits<Inverse<const BlockT *>>;
852
853
  const BranchProbabilityInfoT *BPI = nullptr;
854
  const LoopInfoT *LI = nullptr;
855
  const FunctionT *F = nullptr;
856
857
  // All blocks in reverse postorder.
858
  std::vector<const BlockT *> RPOT;
859
  DenseMap<const BlockT *, BlockNode> Nodes;
860
861
  using rpot_iterator = typename std::vector<const BlockT *>::const_iterator;
862
863
61.8M
  rpot_iterator rpot_begin() const { return RPOT.begin(); }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::rpot_begin() const
Line
Count
Source
863
35.5M
  rpot_iterator rpot_begin() const { return RPOT.begin(); }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::rpot_begin() const
Line
Count
Source
863
26.3M
  rpot_iterator rpot_begin() const { return RPOT.begin(); }
864
8.67M
  rpot_iterator rpot_end() const { return RPOT.end(); }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::rpot_end() const
Line
Count
Source
864
4.60M
  rpot_iterator rpot_end() const { return RPOT.end(); }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::rpot_end() const
Line
Count
Source
864
4.07M
  rpot_iterator rpot_end() const { return RPOT.end(); }
865
866
53.1M
  size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getIndex(std::__1::__wrap_iter<llvm::BasicBlock const* const*> const&) const
Line
Count
Source
866
30.9M
  size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getIndex(std::__1::__wrap_iter<llvm::MachineBasicBlock const* const*> const&) const
Line
Count
Source
866
22.2M
  size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); }
867
868
53.1M
  BlockNode getNode(const rpot_iterator &I) const {
869
53.1M
    return BlockNode(getIndex(I));
870
53.1M
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getNode(std::__1::__wrap_iter<llvm::BasicBlock const* const*> const&) const
Line
Count
Source
868
30.9M
  BlockNode getNode(const rpot_iterator &I) const {
869
30.9M
    return BlockNode(getIndex(I));
870
30.9M
  }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getNode(std::__1::__wrap_iter<llvm::MachineBasicBlock const* const*> const&) const
Line
Count
Source
868
22.2M
  BlockNode getNode(const rpot_iterator &I) const {
869
22.2M
    return BlockNode(getIndex(I));
870
22.2M
  }
871
89.1M
  BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB); }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getNode(llvm::BasicBlock const*) const
Line
Count
Source
871
27.2M
  BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB); }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getNode(llvm::MachineBasicBlock const*) const
Line
Count
Source
871
61.8M
  BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB); }
872
873
26.6M
  const BlockT *getBlock(const BlockNode &Node) const {
874
26.6M
    assert(Node.Index < RPOT.size());
875
26.6M
    return RPOT[Node.Index];
876
26.6M
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getBlock(llvm::BlockFrequencyInfoImplBase::BlockNode const&) const
Line
Count
Source
873
15.4M
  const BlockT *getBlock(const BlockNode &Node) const {
874
15.4M
    assert(Node.Index < RPOT.size());
875
15.4M
    return RPOT[Node.Index];
876
15.4M
  }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getBlock(llvm::BlockFrequencyInfoImplBase::BlockNode const&) const
Line
Count
Source
873
11.1M
  const BlockT *getBlock(const BlockNode &Node) const {
874
11.1M
    assert(Node.Index < RPOT.size());
875
11.1M
    return RPOT[Node.Index];
876
11.1M
  }
877
878
  /// Run (and save) a post-order traversal.
879
  ///
880
  /// Saves a reverse post-order traversal of all the nodes in \a F.
881
  void initializeRPOT();
882
883
  /// Initialize loop data.
884
  ///
885
  /// Build up \a Loops using \a LoopInfo.  \a LoopInfo gives us a mapping from
886
  /// each block to the deepest loop it's in, but we need the inverse.  For each
887
  /// loop, we store in reverse post-order its "immediate" members, defined as
888
  /// the header, the headers of immediate sub-loops, and all other blocks in
889
  /// the loop that are not in sub-loops.
890
  void initializeLoops();
891
892
  /// Propagate to a block's successors.
893
  ///
894
  /// In the context of distributing mass through \c OuterLoop, divide the mass
895
  /// currently assigned to \c Node between its successors.
896
  ///
897
  /// \return \c true unless there's an irreducible backedge.
898
  bool propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node);
899
900
  /// Compute mass in a particular loop.
901
  ///
902
  /// Assign mass to \c Loop's header, and then for each block in \c Loop in
903
  /// reverse post-order, distribute mass to its successors.  Only visits nodes
904
  /// that have not been packaged into sub-loops.
905
  ///
906
  /// \pre \a computeMassInLoop() has been called for each subloop of \c Loop.
907
  /// \return \c true unless there's an irreducible backedge.
908
  bool computeMassInLoop(LoopData &Loop);
909
910
  /// Try to compute mass in the top-level function.
911
  ///
912
  /// Assign mass to the entry block, and then for each block in reverse
913
  /// post-order, distribute mass to its successors.  Skips nodes that have
914
  /// been packaged into loops.
915
  ///
916
  /// \pre \a computeMassInLoops() has been called.
917
  /// \return \c true unless there's an irreducible backedge.
918
  bool tryToComputeMassInFunction();
919
920
  /// Compute mass in (and package up) irreducible SCCs.
921
  ///
922
  /// Find the irreducible SCCs in \c OuterLoop, add them to \a Loops (in front
923
  /// of \c Insert), and call \a computeMassInLoop() on each of them.
924
  ///
925
  /// If \c OuterLoop is \c nullptr, it refers to the top-level function.
926
  ///
927
  /// \pre \a computeMassInLoop() has been called for each subloop of \c
928
  /// OuterLoop.
929
  /// \pre \c Insert points at the last loop successfully processed by \a
930
  /// computeMassInLoop().
931
  /// \pre \c OuterLoop has irreducible SCCs.
932
  void computeIrreducibleMass(LoopData *OuterLoop,
933
                              std::list<LoopData>::iterator Insert);
934
935
  /// Compute mass in all loops.
936
  ///
937
  /// For each loop bottom-up, call \a computeMassInLoop().
938
  ///
939
  /// \a computeMassInLoop() aborts (and returns \c false) on loops that
940
  /// contain a irreducible sub-SCCs.  Use \a computeIrreducibleMass() and then
941
  /// re-enter \a computeMassInLoop().
942
  ///
943
  /// \post \a computeMassInLoop() has returned \c true for every loop.
944
  void computeMassInLoops();
945
946
  /// Compute mass in the top-level function.
947
  ///
948
  /// Uses \a tryToComputeMassInFunction() and \a computeIrreducibleMass() to
949
  /// compute mass in the top-level function.
950
  ///
951
  /// \post \a tryToComputeMassInFunction() has returned \c true.
952
  void computeMassInFunction();
953
954
0
  std::string getBlockName(const BlockNode &Node) const override {
955
0
    return bfi_detail::getBlockName(getBlock(Node));
956
0
  }
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getBlockName(llvm::BlockFrequencyInfoImplBase::BlockNode const&) const
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getBlockName(llvm::BlockFrequencyInfoImplBase::BlockNode const&) const
957
958
public:
959
4.33M
  BlockFrequencyInfoImpl() = default;
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::BlockFrequencyInfoImpl()
Line
Count
Source
959
2.30M
  BlockFrequencyInfoImpl() = default;
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::BlockFrequencyInfoImpl()
Line
Count
Source
959
2.03M
  BlockFrequencyInfoImpl() = default;
960
961
2.05k
  const FunctionT *getFunction() const { return F; }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getFunction() const
Line
Count
Source
961
1.99k
  const FunctionT *getFunction() const { return F; }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getFunction() const
Line
Count
Source
961
58
  const FunctionT *getFunction() const { return F; }
962
963
  void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI,
964
                 const LoopInfoT &LI);
965
966
  using BlockFrequencyInfoImplBase::getEntryFreq;
967
968
48.2M
  BlockFrequency getBlockFreq(const BlockT *BB) const {
969
48.2M
    return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB));
970
48.2M
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getBlockFreq(llvm::BasicBlock const*) const
Line
Count
Source
968
2.81M
  BlockFrequency getBlockFreq(const BlockT *BB) const {
969
2.81M
    return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB));
970
2.81M
  }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getBlockFreq(llvm::MachineBasicBlock const*) const
Line
Count
Source
968
45.4M
  BlockFrequency getBlockFreq(const BlockT *BB) const {
969
45.4M
    return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB));
970
45.4M
  }
971
972
  Optional<uint64_t> getBlockProfileCount(const Function &F,
973
                                          const BlockT *BB,
974
1.95k
                                          bool AllowSynthetic = false) const {
975
1.95k
    return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB),
976
1.95k
                                                            AllowSynthetic);
977
1.95k
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getBlockProfileCount(llvm::Function const&, llvm::BasicBlock const*, bool) const
Line
Count
Source
974
1.90k
                                          bool AllowSynthetic = false) const {
975
1.90k
    return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB),
976
1.90k
                                                            AllowSynthetic);
977
1.90k
  }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getBlockProfileCount(llvm::Function const&, llvm::MachineBasicBlock const*, bool) const
Line
Count
Source
974
58
                                          bool AllowSynthetic = false) const {
975
58
    return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB),
976
58
                                                            AllowSynthetic);
977
58
  }
978
979
  Optional<uint64_t> getProfileCountFromFreq(const Function &F,
980
                                             uint64_t Freq,
981
94
                                             bool AllowSynthetic = false) const {
982
94
    return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F, Freq,
983
94
                                                               AllowSynthetic);
984
94
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getProfileCountFromFreq(llvm::Function const&, unsigned long long, bool) const
Line
Count
Source
981
94
                                             bool AllowSynthetic = false) const {
982
94
    return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F, Freq,
983
94
                                                               AllowSynthetic);
984
94
  }
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getProfileCountFromFreq(llvm::Function const&, unsigned long long, bool) const
985
986
371
  bool isIrrLoopHeader(const BlockT *BB) {
987
371
    return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB));
988
371
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::isIrrLoopHeader(llvm::BasicBlock const*)
Line
Count
Source
986
371
  bool isIrrLoopHeader(const BlockT *BB) {
987
371
    return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB));
988
371
  }
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::isIrrLoopHeader(llvm::MachineBasicBlock const*)
989
990
  void setBlockFreq(const BlockT *BB, uint64_t Freq);
991
992
609
  Scaled64 getFloatingBlockFreq(const BlockT *BB) const {
993
609
    return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB));
994
609
  }
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getFloatingBlockFreq(llvm::BasicBlock const*) const
Line
Count
Source
992
532
  Scaled64 getFloatingBlockFreq(const BlockT *BB) const {
993
532
    return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB));
994
532
  }
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getFloatingBlockFreq(llvm::MachineBasicBlock const*) const
Line
Count
Source
992
77
  Scaled64 getFloatingBlockFreq(const BlockT *BB) const {
993
77
    return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB));
994
77
  }
995
996
0
  const BranchProbabilityInfoT &getBPI() const { return *BPI; }
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::getBPI() const
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::getBPI() const
997
998
  /// Print the frequencies for the current function.
999
  ///
1000
  /// Prints the frequencies for the blocks in the current function.
1001
  ///
1002
  /// Blocks are printed in the natural iteration order of the function, rather
1003
  /// than reverse post-order.  This provides two advantages:  writing -analyze
1004
  /// tests is easier (since blocks come out in source order), and even
1005
  /// unreachable blocks are printed.
1006
  ///
1007
  /// \a BlockFrequencyInfoImplBase::print() only knows reverse post-order, so
1008
  /// we need to override it here.
1009
  raw_ostream &print(raw_ostream &OS) const override;
1010
1011
  using BlockFrequencyInfoImplBase::dump;
1012
  using BlockFrequencyInfoImplBase::printBlockFreq;
1013
1014
0
  raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const {
1015
0
    return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB));
1016
0
  }
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::printBlockFreq(llvm::raw_ostream&, llvm::BasicBlock const*) const
Unexecuted instantiation: llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::printBlockFreq(llvm::raw_ostream&, llvm::MachineBasicBlock const*) const
1017
};
1018
1019
template <class BT>
1020
void BlockFrequencyInfoImpl<BT>::calculate(const FunctionT &F,
1021
                                           const BranchProbabilityInfoT &BPI,
1022
4.33M
                                           const LoopInfoT &LI) {
1023
4.33M
  // Save the parameters.
1024
4.33M
  this->BPI = &BPI;
1025
4.33M
  this->LI = &LI;
1026
4.33M
  this->F = &F;
1027
4.33M
1028
4.33M
  // Clean up left-over data structures.
1029
4.33M
  BlockFrequencyInfoImplBase::clear();
1030
4.33M
  RPOT.clear();
1031
4.33M
  Nodes.clear();
1032
4.33M
1033
4.33M
  // Initialize.
1034
4.33M
  LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName()
1035
4.33M
                    << "\n================="
1036
4.33M
                    << std::string(F.getName().size(), '=') << "\n");
1037
4.33M
  initializeRPOT();
1038
4.33M
  initializeLoops();
1039
4.33M
1040
4.33M
  // Visit loops in post-order to find the local mass distribution, and then do
1041
4.33M
  // the full function.
1042
4.33M
  computeMassInLoops();
1043
4.33M
  computeMassInFunction();
1044
4.33M
  unwrapLoops();
1045
4.33M
  finalizeMetrics();
1046
4.33M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::calculate(llvm::Function const&, llvm::BranchProbabilityInfo const&, llvm::LoopInfo const&)
Line
Count
Source
1022
2.30M
                                           const LoopInfoT &LI) {
1023
2.30M
  // Save the parameters.
1024
2.30M
  this->BPI = &BPI;
1025
2.30M
  this->LI = &LI;
1026
2.30M
  this->F = &F;
1027
2.30M
1028
2.30M
  // Clean up left-over data structures.
1029
2.30M
  BlockFrequencyInfoImplBase::clear();
1030
2.30M
  RPOT.clear();
1031
2.30M
  Nodes.clear();
1032
2.30M
1033
2.30M
  // Initialize.
1034
2.30M
  LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName()
1035
2.30M
                    << "\n================="
1036
2.30M
                    << std::string(F.getName().size(), '=') << "\n");
1037
2.30M
  initializeRPOT();
1038
2.30M
  initializeLoops();
1039
2.30M
1040
2.30M
  // Visit loops in post-order to find the local mass distribution, and then do
1041
2.30M
  // the full function.
1042
2.30M
  computeMassInLoops();
1043
2.30M
  computeMassInFunction();
1044
2.30M
  unwrapLoops();
1045
2.30M
  finalizeMetrics();
1046
2.30M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::calculate(llvm::MachineFunction const&, llvm::MachineBranchProbabilityInfo const&, llvm::MachineLoopInfo const&)
Line
Count
Source
1022
2.03M
                                           const LoopInfoT &LI) {
1023
2.03M
  // Save the parameters.
1024
2.03M
  this->BPI = &BPI;
1025
2.03M
  this->LI = &LI;
1026
2.03M
  this->F = &F;
1027
2.03M
1028
2.03M
  // Clean up left-over data structures.
1029
2.03M
  BlockFrequencyInfoImplBase::clear();
1030
2.03M
  RPOT.clear();
1031
2.03M
  Nodes.clear();
1032
2.03M
1033
2.03M
  // Initialize.
1034
2.03M
  LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName()
1035
2.03M
                    << "\n================="
1036
2.03M
                    << std::string(F.getName().size(), '=') << "\n");
1037
2.03M
  initializeRPOT();
1038
2.03M
  initializeLoops();
1039
2.03M
1040
2.03M
  // Visit loops in post-order to find the local mass distribution, and then do
1041
2.03M
  // the full function.
1042
2.03M
  computeMassInLoops();
1043
2.03M
  computeMassInFunction();
1044
2.03M
  unwrapLoops();
1045
2.03M
  finalizeMetrics();
1046
2.03M
}
1047
1048
template <class BT>
1049
3.29k
void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, uint64_t Freq) {
1050
3.29k
  if (Nodes.count(BB))
1051
2.01k
    BlockFrequencyInfoImplBase::setBlockFreq(getNode(BB), Freq);
1052
1.28k
  else {
1053
1.28k
    // If BB is a newly added block after BFI is done, we need to create a new
1054
1.28k
    // BlockNode for it assigned with a new index. The index can be determined
1055
1.28k
    // by the size of Freqs.
1056
1.28k
    BlockNode NewNode(Freqs.size());
1057
1.28k
    Nodes[BB] = NewNode;
1058
1.28k
    Freqs.emplace_back();
1059
1.28k
    BlockFrequencyInfoImplBase::setBlockFreq(NewNode, Freq);
1060
1.28k
  }
1061
3.29k
}
1062
1063
4.33M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() {
1064
4.33M
  const BlockT *Entry = &F->front();
1065
4.33M
  RPOT.reserve(F->size());
1066
4.33M
  std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
1067
4.33M
  std::reverse(RPOT.begin(), RPOT.end());
1068
4.33M
1069
4.33M
  assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1070
4.33M
         "More nodes in function than Block Frequency Info supports");
1071
4.33M
1072
4.33M
  LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
1073
30.9M
  for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; 
++I26.5M
) {
1074
26.5M
    BlockNode Node = getNode(I);
1075
26.5M
    LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node)
1076
26.5M
                      << "\n");
1077
26.5M
    Nodes[*I] = Node;
1078
26.5M
  }
1079
4.33M
1080
4.33M
  Working.reserve(RPOT.size());
1081
30.9M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index26.5M
)
1082
26.5M
    Working.emplace_back(Index);
1083
4.33M
  Freqs.resize(RPOT.size());
1084
4.33M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::initializeRPOT()
Line
Count
Source
1063
2.30M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() {
1064
2.30M
  const BlockT *Entry = &F->front();
1065
2.30M
  RPOT.reserve(F->size());
1066
2.30M
  std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
1067
2.30M
  std::reverse(RPOT.begin(), RPOT.end());
1068
2.30M
1069
2.30M
  assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1070
2.30M
         "More nodes in function than Block Frequency Info supports");
1071
2.30M
1072
2.30M
  LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
1073
17.7M
  for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; 
++I15.4M
) {
1074
15.4M
    BlockNode Node = getNode(I);
1075
15.4M
    LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node)
1076
15.4M
                      << "\n");
1077
15.4M
    Nodes[*I] = Node;
1078
15.4M
  }
1079
2.30M
1080
2.30M
  Working.reserve(RPOT.size());
1081
17.7M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index15.4M
)
1082
15.4M
    Working.emplace_back(Index);
1083
2.30M
  Freqs.resize(RPOT.size());
1084
2.30M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::initializeRPOT()
Line
Count
Source
1063
2.03M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() {
1064
2.03M
  const BlockT *Entry = &F->front();
1065
2.03M
  RPOT.reserve(F->size());
1066
2.03M
  std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
1067
2.03M
  std::reverse(RPOT.begin(), RPOT.end());
1068
2.03M
1069
2.03M
  assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1070
2.03M
         "More nodes in function than Block Frequency Info supports");
1071
2.03M
1072
2.03M
  LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
1073
13.1M
  for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; 
++I11.1M
) {
1074
11.1M
    BlockNode Node = getNode(I);
1075
11.1M
    LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node)
1076
11.1M
                      << "\n");
1077
11.1M
    Nodes[*I] = Node;
1078
11.1M
  }
1079
2.03M
1080
2.03M
  Working.reserve(RPOT.size());
1081
13.1M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index11.1M
)
1082
11.1M
    Working.emplace_back(Index);
1083
2.03M
  Freqs.resize(RPOT.size());
1084
2.03M
}
1085
1086
4.33M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1087
4.33M
  LLVM_DEBUG(dbgs() << "loop-detection\n");
1088
4.33M
  if (LI->empty())
1089
3.66M
    return;
1090
676k
1091
676k
  // Visit loops top down and assign them an index.
1092
676k
  std::deque<std::pair<const LoopT *, LoopData *>> Q;
1093
676k
  for (const LoopT *L : *LI)
1094
1.49M
    Q.emplace_back(L, nullptr);
1095
2.71M
  while (!Q.empty()) {
1096
2.04M
    const LoopT *Loop = Q.front().first;
1097
2.04M
    LoopData *Parent = Q.front().second;
1098
2.04M
    Q.pop_front();
1099
2.04M
1100
2.04M
    BlockNode Header = getNode(Loop->getHeader());
1101
2.04M
    assert(Header.isValid());
1102
2.04M
1103
2.04M
    Loops.emplace_back(Parent, Header);
1104
2.04M
    Working[Header.Index].Loop = &Loops.back();
1105
2.04M
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n");
1106
2.04M
1107
2.04M
    for (const LoopT *L : *Loop)
1108
546k
      Q.emplace_back(L, &Loops.back());
1109
2.04M
  }
1110
676k
1111
676k
  // Visit nodes in reverse post-order and add them to their deepest containing
1112
676k
  // loop.
1113
17.5M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index16.8M
) {
1114
16.8M
    // Loop headers have already been mostly mapped.
1115
16.8M
    if (Working[Index].isLoopHeader()) {
1116
2.04M
      LoopData *ContainingLoop = Working[Index].getContainingLoop();
1117
2.04M
      if (ContainingLoop)
1118
546k
        ContainingLoop->Nodes.push_back(Index);
1119
2.04M
      continue;
1120
2.04M
    }
1121
14.7M
1122
14.7M
    const LoopT *Loop = LI->getLoopFor(RPOT[Index]);
1123
14.7M
    if (!Loop)
1124
10.1M
      continue;
1125
4.63M
1126
4.63M
    // Add this node to its containing loop's member list.
1127
4.63M
    BlockNode Header = getNode(Loop->getHeader());
1128
4.63M
    assert(Header.isValid());
1129
4.63M
    const auto &HeaderData = Working[Header.Index];
1130
4.63M
    assert(HeaderData.isLoopHeader());
1131
4.63M
1132
4.63M
    Working[Index].Loop = HeaderData.Loop;
1133
4.63M
    HeaderData.Loop->Nodes.push_back(Index);
1134
4.63M
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header)
1135
4.63M
                      << ": member = " << getBlockName(Index) << "\n");
1136
4.63M
  }
1137
676k
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::initializeLoops()
Line
Count
Source
1086
2.30M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1087
2.30M
  LLVM_DEBUG(dbgs() << "loop-detection\n");
1088
2.30M
  if (LI->empty())
1089
1.90M
    return;
1090
399k
1091
399k
  // Visit loops top down and assign them an index.
1092
399k
  std::deque<std::pair<const LoopT *, LoopData *>> Q;
1093
399k
  for (const LoopT *L : *LI)
1094
871k
    Q.emplace_back(L, nullptr);
1095
1.59M
  while (!Q.empty()) {
1096
1.19M
    const LoopT *Loop = Q.front().first;
1097
1.19M
    LoopData *Parent = Q.front().second;
1098
1.19M
    Q.pop_front();
1099
1.19M
1100
1.19M
    BlockNode Header = getNode(Loop->getHeader());
1101
1.19M
    assert(Header.isValid());
1102
1.19M
1103
1.19M
    Loops.emplace_back(Parent, Header);
1104
1.19M
    Working[Header.Index].Loop = &Loops.back();
1105
1.19M
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n");
1106
1.19M
1107
1.19M
    for (const LoopT *L : *Loop)
1108
324k
      Q.emplace_back(L, &Loops.back());
1109
1.19M
  }
1110
399k
1111
399k
  // Visit nodes in reverse post-order and add them to their deepest containing
1112
399k
  // loop.
1113
10.3M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index9.93M
) {
1114
9.93M
    // Loop headers have already been mostly mapped.
1115
9.93M
    if (Working[Index].isLoopHeader()) {
1116
1.19M
      LoopData *ContainingLoop = Working[Index].getContainingLoop();
1117
1.19M
      if (ContainingLoop)
1118
324k
        ContainingLoop->Nodes.push_back(Index);
1119
1.19M
      continue;
1120
1.19M
    }
1121
8.74M
1122
8.74M
    const LoopT *Loop = LI->getLoopFor(RPOT[Index]);
1123
8.74M
    if (!Loop)
1124
5.97M
      continue;
1125
2.76M
1126
2.76M
    // Add this node to its containing loop's member list.
1127
2.76M
    BlockNode Header = getNode(Loop->getHeader());
1128
2.76M
    assert(Header.isValid());
1129
2.76M
    const auto &HeaderData = Working[Header.Index];
1130
2.76M
    assert(HeaderData.isLoopHeader());
1131
2.76M
1132
2.76M
    Working[Index].Loop = HeaderData.Loop;
1133
2.76M
    HeaderData.Loop->Nodes.push_back(Index);
1134
2.76M
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header)
1135
2.76M
                      << ": member = " << getBlockName(Index) << "\n");
1136
2.76M
  }
1137
399k
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::initializeLoops()
Line
Count
Source
1086
2.03M
template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1087
2.03M
  LLVM_DEBUG(dbgs() << "loop-detection\n");
1088
2.03M
  if (LI->empty())
1089
1.75M
    return;
1090
277k
1091
277k
  // Visit loops top down and assign them an index.
1092
277k
  std::deque<std::pair<const LoopT *, LoopData *>> Q;
1093
277k
  for (const LoopT *L : *LI)
1094
622k
    Q.emplace_back(L, nullptr);
1095
1.12M
  while (!Q.empty()) {
1096
844k
    const LoopT *Loop = Q.front().first;
1097
844k
    LoopData *Parent = Q.front().second;
1098
844k
    Q.pop_front();
1099
844k
1100
844k
    BlockNode Header = getNode(Loop->getHeader());
1101
844k
    assert(Header.isValid());
1102
844k
1103
844k
    Loops.emplace_back(Parent, Header);
1104
844k
    Working[Header.Index].Loop = &Loops.back();
1105
844k
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n");
1106
844k
1107
844k
    for (const LoopT *L : *Loop)
1108
222k
      Q.emplace_back(L, &Loops.back());
1109
844k
  }
1110
277k
1111
277k
  // Visit nodes in reverse post-order and add them to their deepest containing
1112
277k
  // loop.
1113
7.17M
  for (size_t Index = 0; Index < RPOT.size(); 
++Index6.89M
) {
1114
6.89M
    // Loop headers have already been mostly mapped.
1115
6.89M
    if (Working[Index].isLoopHeader()) {
1116
844k
      LoopData *ContainingLoop = Working[Index].getContainingLoop();
1117
844k
      if (ContainingLoop)
1118
222k
        ContainingLoop->Nodes.push_back(Index);
1119
844k
      continue;
1120
844k
    }
1121
6.05M
1122
6.05M
    const LoopT *Loop = LI->getLoopFor(RPOT[Index]);
1123
6.05M
    if (!Loop)
1124
4.19M
      continue;
1125
1.86M
1126
1.86M
    // Add this node to its containing loop's member list.
1127
1.86M
    BlockNode Header = getNode(Loop->getHeader());
1128
1.86M
    assert(Header.isValid());
1129
1.86M
    const auto &HeaderData = Working[Header.Index];
1130
1.86M
    assert(HeaderData.isLoopHeader());
1131
1.86M
1132
1.86M
    Working[Index].Loop = HeaderData.Loop;
1133
1.86M
    HeaderData.Loop->Nodes.push_back(Index);
1134
1.86M
    LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header)
1135
1.86M
                      << ": member = " << getBlockName(Index) << "\n");
1136
1.86M
  }
1137
277k
}
1138
1139
4.33M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1140
4.33M
  // Visit loops with the deepest first, and the top-level loops last.
1141
6.37M
  for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; 
++L2.04M
) {
1142
2.04M
    if (computeMassInLoop(*L))
1143
2.03M
      continue;
1144
142
    auto Next = std::next(L);
1145
142
    computeIrreducibleMass(&*L, L.base());
1146
142
    L = std::prev(Next);
1147
142
    if (computeMassInLoop(*L))
1148
142
      continue;
1149
0
    llvm_unreachable("unhandled irreducible control flow");
1150
0
  }
1151
4.33M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::computeMassInLoops()
Line
Count
Source
1139
2.30M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1140
2.30M
  // Visit loops with the deepest first, and the top-level loops last.
1141
3.49M
  for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; 
++L1.19M
) {
1142
1.19M
    if (computeMassInLoop(*L))
1143
1.19M
      continue;
1144
72
    auto Next = std::next(L);
1145
72
    computeIrreducibleMass(&*L, L.base());
1146
72
    L = std::prev(Next);
1147
72
    if (computeMassInLoop(*L))
1148
72
      continue;
1149
0
    llvm_unreachable("unhandled irreducible control flow");
1150
0
  }
1151
2.30M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::computeMassInLoops()
Line
Count
Source
1139
2.03M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1140
2.03M
  // Visit loops with the deepest first, and the top-level loops last.
1141
2.88M
  for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; 
++L844k
) {
1142
844k
    if (computeMassInLoop(*L))
1143
844k
      continue;
1144
70
    auto Next = std::next(L);
1145
70
    computeIrreducibleMass(&*L, L.base());
1146
70
    L = std::prev(Next);
1147
70
    if (computeMassInLoop(*L))
1148
70
      continue;
1149
0
    llvm_unreachable("unhandled irreducible control flow");
1150
0
  }
1151
2.03M
}
1152
1153
template <class BT>
1154
2.04M
bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1155
2.04M
  // Compute mass in loop.
1156
2.04M
  LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n");
1157
2.04M
1158
2.04M
  if (Loop.isIrreducible()) {
1159
833
    LLVM_DEBUG(dbgs() << "isIrreducible = true\n");
1160
833
    Distribution Dist;
1161
833
    unsigned NumHeadersWithWeight = 0;
1162
833
    Optional<uint64_t> MinHeaderWeight;
1163
833
    DenseSet<uint32_t> HeadersWithoutWeight;
1164
833
    HeadersWithoutWeight.reserve(Loop.NumHeaders);
1165
3.22k
    for (uint32_t H = 0; H < Loop.NumHeaders; 
++H2.39k
) {
1166
2.39k
      auto &HeaderNode = Loop.Nodes[H];
1167
2.39k
      const BlockT *Block = getBlock(HeaderNode);
1168
2.39k
      IsIrrLoopHeader.set(Loop.Nodes[H].Index);
1169
2.39k
      Optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight();
1170
2.39k
      if (!HeaderWeight) {
1171
2.38k
        LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on "
1172
2.38k
                          << getBlockName(HeaderNode) << "\n");
1173
2.38k
        HeadersWithoutWeight.insert(H);
1174
2.38k
        continue;
1175
2.38k
      }
1176
16
      LLVM_DEBUG(dbgs() << getBlockName(HeaderNode)
1177
16
                        << " has irr loop header weight "
1178
16
                        << HeaderWeight.getValue() << "\n");
1179
16
      NumHeadersWithWeight++;
1180
16
      uint64_t HeaderWeightValue = HeaderWeight.getValue();
1181
16
      if (!MinHeaderWeight || 
HeaderWeightValue < MinHeaderWeight10
)
1182
12
        MinHeaderWeight = HeaderWeightValue;
1183
16
      if (HeaderWeightValue) {
1184
16
        Dist.addLocal(HeaderNode, HeaderWeightValue);
1185
16
      }
1186
16
    }
1187
833
    // As a heuristic, if some headers don't have a weight, give them the
1188
833
    // minimium weight seen (not to disrupt the existing trends too much by
1189
833
    // using a weight that's in the general range of the other headers' weights,
1190
833
    // and the minimum seems to perform better than the average.)
1191
833
    // FIXME: better update in the passes that drop the header weight.
1192
833
    // If no headers have a weight, give them even weight (use weight 1).
1193
833
    if (!MinHeaderWeight)
1194
827
      MinHeaderWeight = 1;
1195
2.38k
    for (uint32_t H : HeadersWithoutWeight) {
1196
2.38k
      auto &HeaderNode = Loop.Nodes[H];
1197
2.38k
      assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1198
2.38k
             "Shouldn't have a weight metadata");
1199
2.38k
      uint64_t MinWeight = MinHeaderWeight.getValue();
1200
2.38k
      LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to "
1201
2.38k
                        << getBlockName(HeaderNode) << "\n");
1202
2.38k
      if (MinWeight)
1203
2.38k
        Dist.addLocal(HeaderNode, MinWeight);
1204
2.38k
    }
1205
833
    distributeIrrLoopHeaderMass(Dist);
1206
833
    for (const BlockNode &M : Loop.Nodes)
1207
12.1k
      if (!propagateMassToSuccessors(&Loop, M))
1208
12.1k
        
llvm_unreachable0
("unhandled irreducible control flow");
1209
833
    if (NumHeadersWithWeight == 0)
1210
827
      // No headers have a metadata. Adjust header mass.
1211
827
      adjustLoopHeaderMass(Loop);
1212
2.04M
  } else {
1213
2.04M
    Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1214
2.04M
    if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1215
2.04M
      
llvm_unreachable0
("irreducible control flow to loop header!?");
1216
2.04M
    for (const BlockNode &M : Loop.members())
1217
5.18M
      if (!propagateMassToSuccessors(&Loop, M))
1218
142
        // Irreducible backedge.
1219
142
        return false;
1220
2.04M
  }
1221
2.04M
1222
2.04M
  computeLoopScale(Loop);
1223
2.04M
  packageLoop(Loop);
1224
2.04M
  return true;
1225
2.04M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::computeMassInLoop(llvm::BlockFrequencyInfoImplBase::LoopData&)
Line
Count
Source
1154
1.19M
bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1155
1.19M
  // Compute mass in loop.
1156
1.19M
  LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n");
1157
1.19M
1158
1.19M
  if (Loop.isIrreducible()) {
1159
421
    LLVM_DEBUG(dbgs() << "isIrreducible = true\n");
1160
421
    Distribution Dist;
1161
421
    unsigned NumHeadersWithWeight = 0;
1162
421
    Optional<uint64_t> MinHeaderWeight;
1163
421
    DenseSet<uint32_t> HeadersWithoutWeight;
1164
421
    HeadersWithoutWeight.reserve(Loop.NumHeaders);
1165
1.67k
    for (uint32_t H = 0; H < Loop.NumHeaders; 
++H1.25k
) {
1166
1.25k
      auto &HeaderNode = Loop.Nodes[H];
1167
1.25k
      const BlockT *Block = getBlock(HeaderNode);
1168
1.25k
      IsIrrLoopHeader.set(Loop.Nodes[H].Index);
1169
1.25k
      Optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight();
1170
1.25k
      if (!HeaderWeight) {
1171
1.24k
        LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on "
1172
1.24k
                          << getBlockName(HeaderNode) << "\n");
1173
1.24k
        HeadersWithoutWeight.insert(H);
1174
1.24k
        continue;
1175
1.24k
      }
1176
16
      LLVM_DEBUG(dbgs() << getBlockName(HeaderNode)
1177
16
                        << " has irr loop header weight "
1178
16
                        << HeaderWeight.getValue() << "\n");
1179
16
      NumHeadersWithWeight++;
1180
16
      uint64_t HeaderWeightValue = HeaderWeight.getValue();
1181
16
      if (!MinHeaderWeight || 
HeaderWeightValue < MinHeaderWeight10
)
1182
12
        MinHeaderWeight = HeaderWeightValue;
1183
16
      if (HeaderWeightValue) {
1184
16
        Dist.addLocal(HeaderNode, HeaderWeightValue);
1185
16
      }
1186
16
    }
1187
421
    // As a heuristic, if some headers don't have a weight, give them the
1188
421
    // minimium weight seen (not to disrupt the existing trends too much by
1189
421
    // using a weight that's in the general range of the other headers' weights,
1190
421
    // and the minimum seems to perform better than the average.)
1191
421
    // FIXME: better update in the passes that drop the header weight.
1192
421
    // If no headers have a weight, give them even weight (use weight 1).
1193
421
    if (!MinHeaderWeight)
1194
415
      MinHeaderWeight = 1;
1195
1.24k
    for (uint32_t H : HeadersWithoutWeight) {
1196
1.24k
      auto &HeaderNode = Loop.Nodes[H];
1197
1.24k
      assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1198
1.24k
             "Shouldn't have a weight metadata");
1199
1.24k
      uint64_t MinWeight = MinHeaderWeight.getValue();
1200
1.24k
      LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to "
1201
1.24k
                        << getBlockName(HeaderNode) << "\n");
1202
1.24k
      if (MinWeight)
1203
1.24k
        Dist.addLocal(HeaderNode, MinWeight);
1204
1.24k
    }
1205
421
    distributeIrrLoopHeaderMass(Dist);
1206
421
    for (const BlockNode &M : Loop.Nodes)
1207
6.69k
      if (!propagateMassToSuccessors(&Loop, M))
1208
6.69k
        
llvm_unreachable0
("unhandled irreducible control flow");
1209
421
    if (NumHeadersWithWeight == 0)
1210
415
      // No headers have a metadata. Adjust header mass.
1211
415
      adjustLoopHeaderMass(Loop);
1212
1.19M
  } else {
1213
1.19M
    Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1214
1.19M
    if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1215
1.19M
      
llvm_unreachable0
("irreducible control flow to loop header!?");
1216
1.19M
    for (const BlockNode &M : Loop.members())
1217
3.09M
      if (!propagateMassToSuccessors(&Loop, M))
1218
72
        // Irreducible backedge.
1219
72
        return false;
1220
1.19M
  }
1221
1.19M
1222
1.19M
  computeLoopScale(Loop);
1223
1.19M
  packageLoop(Loop);
1224
1.19M
  return true;
1225
1.19M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::computeMassInLoop(llvm::BlockFrequencyInfoImplBase::LoopData&)
Line
Count
Source
1154
845k
bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1155
845k
  // Compute mass in loop.
1156
845k
  LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n");
1157
845k
1158
845k
  if (Loop.isIrreducible()) {
1159
412
    LLVM_DEBUG(dbgs() << "isIrreducible = true\n");
1160
412
    Distribution Dist;
1161
412
    unsigned NumHeadersWithWeight = 0;
1162
412
    Optional<uint64_t> MinHeaderWeight;
1163
412
    DenseSet<uint32_t> HeadersWithoutWeight;
1164
412
    HeadersWithoutWeight.reserve(Loop.NumHeaders);
1165
1.55k
    for (uint32_t H = 0; H < Loop.NumHeaders; 
++H1.13k
) {
1166
1.13k
      auto &HeaderNode = Loop.Nodes[H];
1167
1.13k
      const BlockT *Block = getBlock(HeaderNode);
1168
1.13k
      IsIrrLoopHeader.set(Loop.Nodes[H].Index);
1169
1.13k
      Optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight();
1170
1.13k
      if (!HeaderWeight) {
1171
1.13k
        LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on "
1172
1.13k
                          << getBlockName(HeaderNode) << "\n");
1173
1.13k
        HeadersWithoutWeight.insert(H);
1174
1.13k
        continue;
1175
1.13k
      }
1176
0
      LLVM_DEBUG(dbgs() << getBlockName(HeaderNode)
1177
0
                        << " has irr loop header weight "
1178
0
                        << HeaderWeight.getValue() << "\n");
1179
0
      NumHeadersWithWeight++;
1180
0
      uint64_t HeaderWeightValue = HeaderWeight.getValue();
1181
0
      if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
1182
0
        MinHeaderWeight = HeaderWeightValue;
1183
0
      if (HeaderWeightValue) {
1184
0
        Dist.addLocal(HeaderNode, HeaderWeightValue);
1185
0
      }
1186
0
    }
1187
412
    // As a heuristic, if some headers don't have a weight, give them the
1188
412
    // minimium weight seen (not to disrupt the existing trends too much by
1189
412
    // using a weight that's in the general range of the other headers' weights,
1190
412
    // and the minimum seems to perform better than the average.)
1191
412
    // FIXME: better update in the passes that drop the header weight.
1192
412
    // If no headers have a weight, give them even weight (use weight 1).
1193
412
    if (!MinHeaderWeight)
1194
412
      MinHeaderWeight = 1;
1195
1.13k
    for (uint32_t H : HeadersWithoutWeight) {
1196
1.13k
      auto &HeaderNode = Loop.Nodes[H];
1197
1.13k
      assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1198
1.13k
             "Shouldn't have a weight metadata");
1199
1.13k
      uint64_t MinWeight = MinHeaderWeight.getValue();
1200
1.13k
      LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to "
1201
1.13k
                        << getBlockName(HeaderNode) << "\n");
1202
1.13k
      if (MinWeight)
1203
1.13k
        Dist.addLocal(HeaderNode, MinWeight);
1204
1.13k
    }
1205
412
    distributeIrrLoopHeaderMass(Dist);
1206
412
    for (const BlockNode &M : Loop.Nodes)
1207
5.45k
      if (!propagateMassToSuccessors(&Loop, M))
1208
5.45k
        
llvm_unreachable0
("unhandled irreducible control flow");
1209
412
    if (NumHeadersWithWeight == 0)
1210
412
      // No headers have a metadata. Adjust header mass.
1211
412
      adjustLoopHeaderMass(Loop);
1212
844k
  } else {
1213
844k
    Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1214
844k
    if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1215
844k
      
llvm_unreachable0
("irreducible control flow to loop header!?");
1216
844k
    for (const BlockNode &M : Loop.members())
1217
2.08M
      if (!propagateMassToSuccessors(&Loop, M))
1218
70
        // Irreducible backedge.
1219
70
        return false;
1220
844k
  }
1221
845k
1222
845k
  computeLoopScale(Loop);
1223
845k
  packageLoop(Loop);
1224
845k
  return true;
1225
845k
}
1226
1227
template <class BT>
1228
4.33M
bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1229
4.33M
  // Compute mass in function.
1230
4.33M
  LLVM_DEBUG(dbgs() << "compute-mass-in-function\n");
1231
4.33M
  assert(!Working.empty() && "no blocks in function");
1232
4.33M
  assert(!Working[0].isLoopHeader() && "entry block is a loop header");
1233
4.33M
1234
4.33M
  Working[0].getMass() = BlockMass::getFull();
1235
30.9M
  for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; 
++I26.6M
) {
1236
26.6M
    // Check for nodes that have been packaged.
1237
26.6M
    BlockNode Node = getNode(I);
1238
26.6M
    if (Working[Node.Index].isPackaged())
1239
5.19M
      continue;
1240
21.4M
1241
21.4M
    if (!propagateMassToSuccessors(nullptr, Node))
1242
575
      return false;
1243
21.4M
  }
1244
4.33M
  
return true4.33M
;
1245
4.33M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::tryToComputeMassInFunction()
Line
Count
Source
1228
2.30M
bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1229
2.30M
  // Compute mass in function.
1230
2.30M
  LLVM_DEBUG(dbgs() << "compute-mass-in-function\n");
1231
2.30M
  assert(!Working.empty() && "no blocks in function");
1232
2.30M
  assert(!Working[0].isLoopHeader() && "entry block is a loop header");
1233
2.30M
1234
2.30M
  Working[0].getMass() = BlockMass::getFull();
1235
17.7M
  for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; 
++I15.4M
) {
1236
15.4M
    // Check for nodes that have been packaged.
1237
15.4M
    BlockNode Node = getNode(I);
1238
15.4M
    if (Working[Node.Index].isPackaged())
1239
3.09M
      continue;
1240
12.3M
1241
12.3M
    if (!propagateMassToSuccessors(nullptr, Node))
1242
274
      return false;
1243
12.3M
  }
1244
2.30M
  
return true2.30M
;
1245
2.30M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::tryToComputeMassInFunction()
Line
Count
Source
1228
2.03M
bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1229
2.03M
  // Compute mass in function.
1230
2.03M
  LLVM_DEBUG(dbgs() << "compute-mass-in-function\n");
1231
2.03M
  assert(!Working.empty() && "no blocks in function");
1232
2.03M
  assert(!Working[0].isLoopHeader() && "entry block is a loop header");
1233
2.03M
1234
2.03M
  Working[0].getMass() = BlockMass::getFull();
1235
13.1M
  for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; 
++I11.1M
) {
1236
11.1M
    // Check for nodes that have been packaged.
1237
11.1M
    BlockNode Node = getNode(I);
1238
11.1M
    if (Working[Node.Index].isPackaged())
1239
2.09M
      continue;
1240
9.03M
1241
9.03M
    if (!propagateMassToSuccessors(nullptr, Node))
1242
301
      return false;
1243
9.03M
  }
1244
2.03M
  
return true2.03M
;
1245
2.03M
}
1246
1247
4.33M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1248
4.33M
  if (tryToComputeMassInFunction())
1249
4.33M
    return;
1250
560
  computeIrreducibleMass(nullptr, Loops.begin());
1251
560
  if (tryToComputeMassInFunction())
1252
575
    return;
1253
18.4E
  llvm_unreachable("unhandled irreducible control flow");
1254
18.4E
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::computeMassInFunction()
Line
Count
Source
1247
2.30M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1248
2.30M
  if (tryToComputeMassInFunction())
1249
2.30M
    return;
1250
263
  computeIrreducibleMass(nullptr, Loops.begin());
1251
263
  if (tryToComputeMassInFunction())
1252
274
    return;
1253
18.4E
  llvm_unreachable("unhandled irreducible control flow");
1254
18.4E
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::computeMassInFunction()
Line
Count
Source
1247
2.03M
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1248
2.03M
  if (tryToComputeMassInFunction())
1249
2.03M
    return;
1250
297
  computeIrreducibleMass(nullptr, Loops.begin());
1251
297
  if (tryToComputeMassInFunction())
1252
301
    return;
1253
18.4E
  llvm_unreachable("unhandled irreducible control flow");
1254
18.4E
}
1255
1256
/// \note This should be a lambda, but that crashes GCC 4.7.
1257
namespace bfi_detail {
1258
1259
template <class BT> struct BlockEdgesAdder {
1260
  using BlockT = BT;
1261
  using LoopData = BlockFrequencyInfoImplBase::LoopData;
1262
  using Successor = GraphTraits<const BlockT *>;
1263
1264
  const BlockFrequencyInfoImpl<BT> &BFI;
1265
1266
  explicit BlockEdgesAdder(const BlockFrequencyInfoImpl<BT> &BFI)
1267
717
      : BFI(BFI) {}
llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock>::BlockEdgesAdder(llvm::BlockFrequencyInfoImpl<llvm::BasicBlock> const&)
Line
Count
Source
1267
346
      : BFI(BFI) {}
llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock>::BlockEdgesAdder(llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock> const&)
Line
Count
Source
1267
371
      : BFI(BFI) {}
1268
1269
  void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr,
1270
25.1k
                  const LoopData *OuterLoop) {
1271
25.1k
    const BlockT *BB = BFI.RPOT[Irr.Node.Index];
1272
25.1k
    for (const auto Succ : children<const BlockT *>(BB))
1273
36.6k
      G.addEdge(Irr, BFI.getNode(Succ), OuterLoop);
1274
25.1k
  }
llvm::bfi_detail::BlockEdgesAdder<llvm::BasicBlock>::operator()(llvm::bfi_detail::IrreducibleGraph&, llvm::bfi_detail::IrreducibleGraph::IrrNode&, llvm::BlockFrequencyInfoImplBase::LoopData const*)
Line
Count
Source
1270
12.5k
                  const LoopData *OuterLoop) {
1271
12.5k
    const BlockT *BB = BFI.RPOT[Irr.Node.Index];
1272
12.5k
    for (const auto Succ : children<const BlockT *>(BB))
1273
18.2k
      G.addEdge(Irr, BFI.getNode(Succ), OuterLoop);
1274
12.5k
  }
llvm::bfi_detail::BlockEdgesAdder<llvm::MachineBasicBlock>::operator()(llvm::bfi_detail::IrreducibleGraph&, llvm::bfi_detail::IrreducibleGraph::IrrNode&, llvm::BlockFrequencyInfoImplBase::LoopData const*)
Line
Count
Source
1270
12.6k
                  const LoopData *OuterLoop) {
1271
12.6k
    const BlockT *BB = BFI.RPOT[Irr.Node.Index];
1272
12.6k
    for (const auto Succ : children<const BlockT *>(BB))
1273
18.3k
      G.addEdge(Irr, BFI.getNode(Succ), OuterLoop);
1274
12.6k
  }
1275
};
1276
1277
} // end namespace bfi_detail
1278
1279
template <class BT>
1280
void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
1281
717
    LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1282
717
  LLVM_DEBUG(dbgs() << "analyze-irreducible-in-";
1283
717
             if (OuterLoop) dbgs()
1284
717
             << "loop: " << getLoopName(*OuterLoop) << "\n";
1285
717
             else dbgs() << "function\n");
1286
717
1287
717
  using namespace bfi_detail;
1288
717
1289
717
  // Ideally, addBlockEdges() would be declared here as a lambda, but that
1290
717
  // crashes GCC 4.7.
1291
717
  BlockEdgesAdder<BT> addBlockEdges(*this);
1292
717
  IrreducibleGraph G(*this, OuterLoop, addBlockEdges);
1293
717
1294
717
  for (auto &L : analyzeIrreducible(G, OuterLoop, Insert))
1295
833
    computeMassInLoop(L);
1296
717
1297
717
  if (!OuterLoop)
1298
575
    return;
1299
142
  updateLoopWithIrreducible(*OuterLoop);
1300
142
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::computeIrreducibleMass(llvm::BlockFrequencyInfoImplBase::LoopData*, std::__1::__list_iterator<llvm::BlockFrequencyInfoImplBase::LoopData, void*>)
Line
Count
Source
1281
346
    LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1282
346
  LLVM_DEBUG(dbgs() << "analyze-irreducible-in-";
1283
346
             if (OuterLoop) dbgs()
1284
346
             << "loop: " << getLoopName(*OuterLoop) << "\n";
1285
346
             else dbgs() << "function\n");
1286
346
1287
346
  using namespace bfi_detail;
1288
346
1289
346
  // Ideally, addBlockEdges() would be declared here as a lambda, but that
1290
346
  // crashes GCC 4.7.
1291
346
  BlockEdgesAdder<BT> addBlockEdges(*this);
1292
346
  IrreducibleGraph G(*this, OuterLoop, addBlockEdges);
1293
346
1294
346
  for (auto &L : analyzeIrreducible(G, OuterLoop, Insert))
1295
421
    computeMassInLoop(L);
1296
346
1297
346
  if (!OuterLoop)
1298
274
    return;
1299
72
  updateLoopWithIrreducible(*OuterLoop);
1300
72
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::computeIrreducibleMass(llvm::BlockFrequencyInfoImplBase::LoopData*, std::__1::__list_iterator<llvm::BlockFrequencyInfoImplBase::LoopData, void*>)
Line
Count
Source
1281
371
    LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1282
371
  LLVM_DEBUG(dbgs() << "analyze-irreducible-in-";
1283
371
             if (OuterLoop) dbgs()
1284
371
             << "loop: " << getLoopName(*OuterLoop) << "\n";
1285
371
             else dbgs() << "function\n");
1286
371
1287
371
  using namespace bfi_detail;
1288
371
1289
371
  // Ideally, addBlockEdges() would be declared here as a lambda, but that
1290
371
  // crashes GCC 4.7.
1291
371
  BlockEdgesAdder<BT> addBlockEdges(*this);
1292
371
  IrreducibleGraph G(*this, OuterLoop, addBlockEdges);
1293
371
1294
371
  for (auto &L : analyzeIrreducible(G, OuterLoop, Insert))
1295
412
    computeMassInLoop(L);
1296
371
1297
371
  if (!OuterLoop)
1298
301
    return;
1299
70
  updateLoopWithIrreducible(*OuterLoop);
1300
70
}
1301
1302
// A helper function that converts a branch probability into weight.
1303
34.1M
inline uint32_t getWeightFromBranchProb(const BranchProbability Prob) {
1304
34.1M
  return Prob.getNumerator();
1305
34.1M
}
1306
1307
template <class BT>
1308
bool
1309
BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
1310
28.6M
                                                      const BlockNode &Node) {
1311
28.6M
  LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
1312
28.6M
  // Calculate probability for successors.
1313
28.6M
  Distribution Dist;
1314
28.6M
  if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
1315
2.04M
    assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
1316
2.04M
    if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1317
44
      // Irreducible backedge.
1318
44
      return false;
1319
26.6M
  } else {
1320
26.6M
    const BlockT *BB = getBlock(Node);
1321
26.6M
    for (auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1322
26.6M
              SE = GraphTraits<const BlockT *>::child_end(BB);
1323
60.7M
         SI != SE; 
++SI34.1M
)
1324
34.1M
      if (!addToDist(
1325
34.1M
              Dist, OuterLoop, Node, getNode(*SI),
1326
34.1M
              getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
1327
673
        // Irreducible backedge.
1328
673
        return false;
1329
26.6M
  }
1330
28.6M
1331
28.6M
  // Distribute mass to successors, saving exit and backedge data in the
1332
28.6M
  // loop header.
1333
28.6M
  distributeMass(Node, OuterLoop, Dist);
1334
28.6M
  return true;
1335
28.6M
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::propagateMassToSuccessors(llvm::BlockFrequencyInfoImplBase::LoopData*, llvm::BlockFrequencyInfoImplBase::BlockNode const&)
Line
Count
Source
1310
16.6M
                                                      const BlockNode &Node) {
1311
16.6M
  LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
1312
16.6M
  // Calculate probability for successors.
1313
16.6M
  Distribution Dist;
1314
16.6M
  if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
1315
1.19M
    assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
1316
1.19M
    if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1317
12
      // Irreducible backedge.
1318
12
      return false;
1319
15.4M
  } else {
1320
15.4M
    const BlockT *BB = getBlock(Node);
1321
15.4M
    for (auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1322
15.4M
              SE = GraphTraits<const BlockT *>::child_end(BB);
1323
35.9M
         SI != SE; 
++SI20.4M
)
1324
20.4M
      if (!addToDist(
1325
20.4M
              Dist, OuterLoop, Node, getNode(*SI),
1326
20.4M
              getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
1327
334
        // Irreducible backedge.
1328
334
        return false;
1329
15.4M
  }
1330
16.6M
1331
16.6M
  // Distribute mass to successors, saving exit and backedge data in the
1332
16.6M
  // loop header.
1333
16.6M
  distributeMass(Node, OuterLoop, Dist);
1334
16.6M
  return true;
1335
16.6M
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::propagateMassToSuccessors(llvm::BlockFrequencyInfoImplBase::LoopData*, llvm::BlockFrequencyInfoImplBase::BlockNode const&)
Line
Count
Source
1310
11.9M
                                                      const BlockNode &Node) {
1311
11.9M
  LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
1312
11.9M
  // Calculate probability for successors.
1313
11.9M
  Distribution Dist;
1314
11.9M
  if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
1315
846k
    assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
1316
846k
    if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1317
32
      // Irreducible backedge.
1318
32
      return false;
1319
11.1M
  } else {
1320
11.1M
    const BlockT *BB = getBlock(Node);
1321
11.1M
    for (auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1322
11.1M
              SE = GraphTraits<const BlockT *>::child_end(BB);
1323
24.8M
         SI != SE; 
++SI13.6M
)
1324
13.6M
      if (!addToDist(
1325
13.6M
              Dist, OuterLoop, Node, getNode(*SI),
1326
13.6M
              getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
1327
339
        // Irreducible backedge.
1328
339
        return false;
1329
11.1M
  }
1330
11.9M
1331
11.9M
  // Distribute mass to successors, saving exit and backedge data in the
1332
11.9M
  // loop header.
1333
11.9M
  distributeMass(Node, OuterLoop, Dist);
1334
11.9M
  return true;
1335
11.9M
}
1336
1337
template <class BT>
1338
69
raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const {
1339
69
  if (!F)
1340
0
    return OS;
1341
69
  OS << "block-frequency-info: " << F->getName() << "\n";
1342
609
  for (const BlockT &BB : *F) {
1343
609
    OS << " - " << bfi_detail::getBlockName(&BB) << ": float = ";
1344
609
    getFloatingBlockFreq(&BB).print(OS, 5)
1345
609
        << ", int = " << getBlockFreq(&BB).getFrequency();
1346
609
    if (Optional<uint64_t> ProfileCount =
1347
78
        BlockFrequencyInfoImplBase::getBlockProfileCount(
1348
78
            F->getFunction(), getNode(&BB)))
1349
78
      OS << ", count = " << ProfileCount.getValue();
1350
609
    if (Optional<uint64_t> IrrLoopHeaderWeight =
1351
16
        BB.getIrrLoopHeaderWeight())
1352
16
      OS << ", irr_loop_header_weight = " << IrrLoopHeaderWeight.getValue();
1353
609
    OS << "\n";
1354
609
  }
1355
69
1356
69
  // Add an extra newline for readability.
1357
69
  OS << "\n";
1358
69
  return OS;
1359
69
}
llvm::BlockFrequencyInfoImpl<llvm::BasicBlock>::print(llvm::raw_ostream&) const
Line
Count
Source
1338
63
raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const {
1339
63
  if (!F)
1340
0
    return OS;
1341
63
  OS << "block-frequency-info: " << F->getName() << "\n";
1342
532
  for (const BlockT &BB : *F) {
1343
532
    OS << " - " << bfi_detail::getBlockName(&BB) << ": float = ";
1344
532
    getFloatingBlockFreq(&BB).print(OS, 5)
1345
532
        << ", int = " << getBlockFreq(&BB).getFrequency();
1346
532
    if (Optional<uint64_t> ProfileCount =
1347
78
        BlockFrequencyInfoImplBase::getBlockProfileCount(
1348
78
            F->getFunction(), getNode(&BB)))
1349
78
      OS << ", count = " << ProfileCount.getValue();
1350
532
    if (Optional<uint64_t> IrrLoopHeaderWeight =
1351
16
        BB.getIrrLoopHeaderWeight())
1352
16
      OS << ", irr_loop_header_weight = " << IrrLoopHeaderWeight.getValue();
1353
532
    OS << "\n";
1354
532
  }
1355
63
1356
63
  // Add an extra newline for readability.
1357
63
  OS << "\n";
1358
63
  return OS;
1359
63
}
llvm::BlockFrequencyInfoImpl<llvm::MachineBasicBlock>::print(llvm::raw_ostream&) const
Line
Count
Source
1338
6
raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const {
1339
6
  if (!F)
1340
0
    return OS;
1341
6
  OS << "block-frequency-info: " << F->getName() << "\n";
1342
77
  for (const BlockT &BB : *F) {
1343
77
    OS << " - " << bfi_detail::getBlockName(&BB) << ": float = ";
1344
77
    getFloatingBlockFreq(&BB).print(OS, 5)
1345
77
        << ", int = " << getBlockFreq(&BB).getFrequency();
1346
77
    if (Optional<uint64_t> ProfileCount =
1347
0
        BlockFrequencyInfoImplBase::getBlockProfileCount(
1348
0
            F->getFunction(), getNode(&BB)))
1349
0
      OS << ", count = " << ProfileCount.getValue();
1350
77
    if (Optional<uint64_t> IrrLoopHeaderWeight =
1351
0
        BB.getIrrLoopHeaderWeight())
1352
0
      OS << ", irr_loop_header_weight = " << IrrLoopHeaderWeight.getValue();
1353
77
    OS << "\n";
1354
77
  }
1355
6
1356
6
  // Add an extra newline for readability.
1357
6
  OS << "\n";
1358
6
  return OS;
1359
6
}
1360
1361
// Graph trait base class for block frequency information graph
1362
// viewer.
1363
1364
enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count };
1365
1366
template <class BlockFrequencyInfoT, class BranchProbabilityInfoT>
1367
struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits {
1368
  using GTraits = GraphTraits<BlockFrequencyInfoT *>;
1369
  using NodeRef = typename GTraits::NodeRef;
1370
  using EdgeIter = typename GTraits::ChildIteratorType;
1371
  using NodeIter = typename GTraits::nodes_iterator;
1372
1373
  uint64_t MaxFrequency = 0;
1374
1375
  explicit BFIDOTGraphTraitsBase(bool isSimple = false)
1376
0
      : DefaultDOTGraphTraits(isSimple) {}
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::BlockFrequencyInfo, llvm::BranchProbabilityInfo>::BFIDOTGraphTraitsBase(bool)
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::MachineBlockFrequencyInfo, llvm::MachineBranchProbabilityInfo>::BFIDOTGraphTraitsBase(bool)
1377
1378
0
  static std::string getGraphName(const BlockFrequencyInfoT *G) {
1379
0
    return G->getFunction()->getName();
1380
0
  }
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::BlockFrequencyInfo, llvm::BranchProbabilityInfo>::getGraphName(llvm::BlockFrequencyInfo const*)
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::MachineBlockFrequencyInfo, llvm::MachineBranchProbabilityInfo>::getGraphName(llvm::MachineBlockFrequencyInfo const*)
1381
1382
  std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph,
1383
0
                                unsigned HotPercentThreshold = 0) {
1384
0
    std::string Result;
1385
0
    if (!HotPercentThreshold)
1386
0
      return Result;
1387
0
1388
0
    // Compute MaxFrequency on the fly:
1389
0
    if (!MaxFrequency) {
1390
0
      for (NodeIter I = GTraits::nodes_begin(Graph),
1391
0
                    E = GTraits::nodes_end(Graph);
1392
0
           I != E; ++I) {
1393
0
        NodeRef N = *I;
1394
0
        MaxFrequency =
1395
0
            std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency());
1396
0
      }
1397
0
    }
1398
0
    BlockFrequency Freq = Graph->getBlockFreq(Node);
1399
0
    BlockFrequency HotFreq =
1400
0
        (BlockFrequency(MaxFrequency) *
1401
0
         BranchProbability::getBranchProbability(HotPercentThreshold, 100));
1402
0
1403
0
    if (Freq < HotFreq)
1404
0
      return Result;
1405
0
1406
0
    raw_string_ostream OS(Result);
1407
0
    OS << "color=\"red\"";
1408
0
    OS.flush();
1409
0
    return Result;
1410
0
  }
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::BlockFrequencyInfo, llvm::BranchProbabilityInfo>::getNodeAttributes(llvm::BasicBlock const*, llvm::BlockFrequencyInfo const*, unsigned int)
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::MachineBlockFrequencyInfo, llvm::MachineBranchProbabilityInfo>::getNodeAttributes(llvm::MachineBasicBlock const*, llvm::MachineBlockFrequencyInfo const*, unsigned int)
1411
1412
  std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph,
1413
0
                           GVDAGType GType, int layout_order = -1) {
1414
0
    std::string Result;
1415
0
    raw_string_ostream OS(Result);
1416
0
1417
0
    if (layout_order != -1)
1418
0
      OS << Node->getName() << "[" << layout_order << "] : ";
1419
0
    else
1420
0
      OS << Node->getName() << " : ";
1421
0
    switch (GType) {
1422
0
    case GVDT_Fraction:
1423
0
      Graph->printBlockFreq(OS, Node);
1424
0
      break;
1425
0
    case GVDT_Integer:
1426
0
      OS << Graph->getBlockFreq(Node).getFrequency();
1427
0
      break;
1428
0
    case GVDT_Count: {
1429
0
      auto Count = Graph->getBlockProfileCount(Node);
1430
0
      if (Count)
1431
0
        OS << Count.getValue();
1432
0
      else
1433
0
        OS << "Unknown";
1434
0
      break;
1435
0
    }
1436
0
    case GVDT_None:
1437
0
      llvm_unreachable("If we are not supposed to render a graph we should "
1438
0
                       "never reach this point.");
1439
0
    }
1440
0
    return Result;
1441
0
  }
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::BlockFrequencyInfo, llvm::BranchProbabilityInfo>::getNodeLabel(llvm::BasicBlock const*, llvm::BlockFrequencyInfo const*, llvm::GVDAGType, int)
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::MachineBlockFrequencyInfo, llvm::MachineBranchProbabilityInfo>::getNodeLabel(llvm::MachineBasicBlock const*, llvm::MachineBlockFrequencyInfo const*, llvm::GVDAGType, int)
1442
1443
  std::string getEdgeAttributes(NodeRef Node, EdgeIter EI,
1444
                                const BlockFrequencyInfoT *BFI,
1445
                                const BranchProbabilityInfoT *BPI,
1446
0
                                unsigned HotPercentThreshold = 0) {
1447
0
    std::string Str;
1448
0
    if (!BPI)
1449
0
      return Str;
1450
0
1451
0
    BranchProbability BP = BPI->getEdgeProbability(Node, EI);
1452
0
    uint32_t N = BP.getNumerator();
1453
0
    uint32_t D = BP.getDenominator();
1454
0
    double Percent = 100.0 * N / D;
1455
0
    raw_string_ostream OS(Str);
1456
0
    OS << format("label=\"%.1f%%\"", Percent);
1457
0
1458
0
    if (HotPercentThreshold) {
1459
0
      BlockFrequency EFreq = BFI->getBlockFreq(Node) * BP;
1460
0
      BlockFrequency HotFreq = BlockFrequency(MaxFrequency) *
1461
0
                               BranchProbability(HotPercentThreshold, 100);
1462
0
1463
0
      if (EFreq >= HotFreq) {
1464
0
        OS << ",color=\"red\"";
1465
0
      }
1466
0
    }
1467
0
1468
0
    OS.flush();
1469
0
    return Str;
1470
0
  }
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::BlockFrequencyInfo, llvm::BranchProbabilityInfo>::getEdgeAttributes(llvm::BasicBlock const*, llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>, llvm::BlockFrequencyInfo const*, llvm::BranchProbabilityInfo const*, unsigned int)
Unexecuted instantiation: llvm::BFIDOTGraphTraitsBase<llvm::MachineBlockFrequencyInfo, llvm::MachineBranchProbabilityInfo>::getEdgeAttributes(llvm::MachineBasicBlock const*, std::__1::__wrap_iter<llvm::MachineBasicBlock* const*>, llvm::MachineBlockFrequencyInfo const*, llvm::MachineBranchProbabilityInfo const*, unsigned int)
1471
};
1472
1473
} // end namespace llvm
1474
1475
#undef DEBUG_TYPE
1476
1477
#endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H