1 //==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==//
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
7 //===----------------------------------------------------------------------===//
9 // Shared implementation of BlockFrequency for IR and Machine Instructions.
10 // See the documentation below for BlockFrequencyInfoImpl for details.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
15 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
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"
47 #define DEBUG_TYPE "block-freq"
51 class BranchProbabilityInfo
;
55 class MachineBasicBlock
;
56 class MachineBranchProbabilityInfo
;
57 class MachineFunction
;
59 class MachineLoopInfo
;
61 namespace bfi_detail
{
63 struct IrreducibleGraph
;
65 // This is part of a workaround for a GCC 4.7 crash on lambdas.
66 template <class BT
> struct BlockEdgesAdder
;
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
74 /// Masses can be added and subtracted. Simple saturation arithmetic is used,
75 /// so arithmetic operations never overflow or underflow.
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).
81 /// Masses can be scaled by \a BranchProbability at maximum precision.
86 BlockMass() = default;
87 explicit BlockMass(uint64_t Mass
) : Mass(Mass
) {}
89 static BlockMass
getEmpty() { return BlockMass(); }
91 static BlockMass
getFull() {
92 return BlockMass(std::numeric_limits
<uint64_t>::max());
95 uint64_t getMass() const { return Mass
; }
97 bool isFull() const { return Mass
== std::numeric_limits
<uint64_t>::max(); }
98 bool isEmpty() const { return !Mass
; }
100 bool operator!() const { return isEmpty(); }
102 /// Add another mass.
104 /// Adds another mass, saturating at \a isFull() rather than overflowing.
105 BlockMass
&operator+=(BlockMass X
) {
106 uint64_t Sum
= Mass
+ X
.Mass
;
107 Mass
= Sum
< Mass
? std::numeric_limits
<uint64_t>::max() : Sum
;
111 /// Subtract another mass.
113 /// Subtracts another mass, saturating at \a isEmpty() rather than
115 BlockMass
&operator-=(BlockMass X
) {
116 uint64_t Diff
= Mass
- X
.Mass
;
117 Mass
= Diff
> Mass
? 0 : Diff
;
121 BlockMass
&operator*=(BranchProbability P
) {
122 Mass
= P
.scale(Mass
);
126 bool operator==(BlockMass X
) const { return Mass
== X
.Mass
; }
127 bool operator!=(BlockMass X
) const { return Mass
!= X
.Mass
; }
128 bool operator<=(BlockMass X
) const { return Mass
<= X
.Mass
; }
129 bool operator>=(BlockMass X
) const { return Mass
>= X
.Mass
; }
130 bool operator<(BlockMass X
) const { return Mass
< X
.Mass
; }
131 bool operator>(BlockMass X
) const { return Mass
> X
.Mass
; }
133 /// Convert to scaled number.
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;
140 raw_ostream
&print(raw_ostream
&OS
) const;
143 inline BlockMass
operator+(BlockMass L
, BlockMass R
) {
144 return BlockMass(L
) += R
;
146 inline BlockMass
operator-(BlockMass L
, BlockMass R
) {
147 return BlockMass(L
) -= R
;
149 inline BlockMass
operator*(BlockMass L
, BranchProbability R
) {
150 return BlockMass(L
) *= R
;
152 inline BlockMass
operator*(BranchProbability L
, BlockMass R
) {
153 return BlockMass(R
) *= L
;
156 inline raw_ostream
&operator<<(raw_ostream
&OS
, BlockMass X
) {
160 } // end namespace bfi_detail
162 /// Base class for BlockFrequencyInfoImpl
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.
168 /// Nevertheless, the majority of the overall algorithm documention lives with
169 /// BlockFrequencyInfoImpl. See there for details.
170 class BlockFrequencyInfoImplBase
{
172 using Scaled64
= ScaledNumber
<uint64_t>;
173 using BlockMass
= bfi_detail::BlockMass
;
175 /// Representative of a block.
177 /// This is a simple wrapper around an index into the reverse-post-order
178 /// traversal of the blocks.
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.
183 using IndexType
= uint32_t;
187 BlockNode() : Index(std::numeric_limits
<uint32_t>::max()) {}
188 BlockNode(IndexType Index
) : Index(Index
) {}
190 bool operator==(const BlockNode
&X
) const { return Index
== X
.Index
; }
191 bool operator!=(const BlockNode
&X
) const { return Index
!= X
.Index
; }
192 bool operator<=(const BlockNode
&X
) const { return Index
<= X
.Index
; }
193 bool operator>=(const BlockNode
&X
) const { return Index
>= X
.Index
; }
194 bool operator<(const BlockNode
&X
) const { return Index
< X
.Index
; }
195 bool operator>(const BlockNode
&X
) const { return Index
> X
.Index
; }
197 bool isValid() const { return Index
<= getMaxIndex(); }
199 static size_t getMaxIndex() {
200 return std::numeric_limits
<uint32_t>::max() - 1;
204 /// Stats about a block itself.
205 struct FrequencyData
{
210 /// Data about a loop.
212 /// Contains the data necessary to represent a loop as a pseudo-node once it's
215 using ExitMap
= SmallVector
<std::pair
<BlockNode
, BlockMass
>, 4>;
216 using NodeList
= SmallVector
<BlockNode
, 4>;
217 using HeaderMassList
= SmallVector
<BlockMass
, 1>;
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.
228 LoopData(LoopData
*Parent
, const BlockNode
&Header
)
229 : Parent(Parent
), Nodes(1, Header
), BackedgeMass(1) {}
231 template <class It1
, class It2
>
232 LoopData(LoopData
*Parent
, It1 FirstHeader
, It1 LastHeader
, It2 FirstOther
,
234 : Parent(Parent
), Nodes(FirstHeader
, LastHeader
) {
235 NumHeaders
= Nodes
.size();
236 Nodes
.insert(Nodes
.end(), FirstOther
, LastOther
);
237 BackedgeMass
.resize(NumHeaders
);
240 bool isHeader(const BlockNode
&Node
) const {
242 return std::binary_search(Nodes
.begin(), Nodes
.begin() + NumHeaders
,
244 return Node
== Nodes
[0];
247 BlockNode
getHeader() const { return Nodes
[0]; }
248 bool isIrreducible() const { return NumHeaders
> 1; }
250 HeaderMassList::difference_type
getHeaderIndex(const BlockNode
&B
) {
251 assert(isHeader(B
) && "this is only valid on loop header blocks");
253 return std::lower_bound(Nodes
.begin(), Nodes
.begin() + NumHeaders
, B
) -
258 NodeList::const_iterator
members_begin() const {
259 return Nodes
.begin() + NumHeaders
;
262 NodeList::const_iterator
members_end() const { return Nodes
.end(); }
263 iterator_range
<NodeList::const_iterator
> members() const {
264 return make_range(members_begin(), members_end());
268 /// Index of loop information.
270 BlockNode Node
; ///< This node.
271 LoopData
*Loop
= nullptr; ///< The loop this block is inside.
272 BlockMass Mass
; ///< Mass distribution from the entry block.
274 WorkingData(const BlockNode
&Node
) : Node(Node
) {}
276 bool isLoopHeader() const { return Loop
&& Loop
->isHeader(Node
); }
278 bool isDoubleLoopHeader() const {
279 return isLoopHeader() && Loop
->Parent
&& Loop
->Parent
->isIrreducible() &&
280 Loop
->Parent
->isHeader(Node
);
283 LoopData
*getContainingLoop() const {
286 if (!isDoubleLoopHeader())
288 return Loop
->Parent
->Parent
;
291 /// Resolve a node to its representative.
293 /// Get the node currently representing Node, which could be a containing
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.
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 BlockNode
getResolvedNode() const {
305 auto L
= getPackagedLoop();
306 return L
? L
->getHeader() : Node
;
309 LoopData
*getPackagedLoop() const {
310 if (!Loop
|| !Loop
->IsPackaged
)
313 while (L
->Parent
&& L
->Parent
->IsPackaged
)
318 /// Get the appropriate mass for a node.
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 BlockMass
&getMass() {
326 if (!isADoublePackage())
328 return Loop
->Parent
->Mass
;
331 /// Has ContainingLoop been packaged up?
332 bool isPackaged() const { return getResolvedNode() != Node
; }
334 /// Has Loop been packaged up?
335 bool isAPackage() const { return isLoopHeader() && Loop
->IsPackaged
; }
337 /// Has Loop been packaged up twice?
338 bool isADoublePackage() const {
339 return isDoubleLoopHeader() && Loop
->Parent
->IsPackaged
;
343 /// Unscaled probability weight.
345 /// Probability weight for an edge in the graph (including the
346 /// successor/target node).
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.
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?
357 enum DistType
{ Local
, Exit
, Backedge
};
358 DistType Type
= Local
;
359 BlockNode TargetNode
;
363 Weight(DistType Type
, BlockNode TargetNode
, uint64_t Amount
)
364 : Type(Type
), TargetNode(TargetNode
), Amount(Amount
) {}
367 /// Distribution of unscaled probability weight.
369 /// Distribution of unscaled probability weight to a set of successors.
371 /// This class collates the successor edge weights for later processing.
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>;
378 WeightList Weights
; ///< Individual successor weights.
379 uint64_t Total
= 0; ///< Sum of all weights.
380 bool DidOverflow
= false; ///< Whether \a Total did overflow.
382 Distribution() = default;
384 void addLocal(const BlockNode
&Node
, uint64_t Amount
) {
385 add(Node
, Amount
, Weight::Local
);
388 void addExit(const BlockNode
&Node
, uint64_t Amount
) {
389 add(Node
, Amount
, Weight::Exit
);
392 void addBackedge(const BlockNode
&Node
, uint64_t Amount
) {
393 add(Node
, Amount
, Weight::Backedge
);
396 /// Normalize the distribution.
398 /// Combines multiple edges to the same \a Weight::TargetNode and scales
399 /// down so that \a Total fits into 32-bits.
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.
408 void add(const BlockNode
&Node
, uint64_t Amount
, Weight::DistType Type
);
411 /// Data about each block. This is used downstream.
412 std::vector
<FrequencyData
> Freqs
;
414 /// Whether each block is an irreducible loop header.
415 /// This is used downstream.
416 SparseBitVector
<> IsIrrLoopHeader
;
418 /// Loop data: see initializeLoops().
419 std::vector
<WorkingData
> Working
;
421 /// Indexed information about loops.
422 std::list
<LoopData
> Loops
;
424 /// Virtual destructor.
426 /// Need a virtual destructor to mask the compiler warning about
428 virtual ~BlockFrequencyInfoImplBase() = default;
430 /// Add all edges out of a packaged loop to the distribution.
432 /// Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each
435 /// \return \c true unless there's an irreducible backedge.
436 bool addLoopSuccessorsToDist(const LoopData
*OuterLoop
, LoopData
&Loop
,
439 /// Add an edge to the distribution.
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).
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
);
449 LoopData
&getLoopPackage(const BlockNode
&Head
) {
450 assert(Head
.Index
< Working
.size());
451 assert(Working
[Head
.Index
].isLoopHeader());
452 return *Working
[Head
.Index
].Loop
;
455 /// Analyze irreducible SCCs.
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.
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
);
466 /// Update a loop after packaging irreducible SCCs inside of it.
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
);
474 /// Distribute mass according to a distribution.
476 /// Distributes the mass in Source according to Dist. If LoopHead.isValid(),
477 /// backedges and exits are stored in its entry in Loops.
479 /// Mass is distributed in parallel from two copies of the source mass.
480 void distributeMass(const BlockNode
&Source
, LoopData
*OuterLoop
,
483 /// Compute the loop scale for a loop.
484 void computeLoopScale(LoopData
&Loop
);
486 /// Adjust the mass of all headers in an irreducible loop.
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.
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
);
496 void distributeIrrLoopHeaderMass(Distribution
&Dist
);
498 /// Package up a loop.
499 void packageLoop(LoopData
&Loop
);
504 /// Finalize frequency metrics.
506 /// Calculates final frequencies and cleans up no-longer-needed data
508 void finalizeMetrics();
510 /// Clear all memory.
513 virtual std::string
getBlockName(const BlockNode
&Node
) const;
514 std::string
getLoopName(const LoopData
&Loop
) const;
516 virtual raw_ostream
&print(raw_ostream
&OS
) const { return OS
; }
517 void dump() const { print(dbgs()); }
519 Scaled64
getFloatingBlockFreq(const BlockNode
&Node
) const;
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
,
527 bool AllowSynthetic
= false) const;
528 bool isIrrLoopHeader(const BlockNode
&Node
);
530 void setBlockFreq(const BlockNode
&Node
, uint64_t Freq
);
532 raw_ostream
&printBlockFreq(raw_ostream
&OS
, const BlockNode
&Node
) const;
533 raw_ostream
&printBlockFreq(raw_ostream
&OS
,
534 const BlockFrequency
&Freq
) const;
536 uint64_t getEntryFreq() const {
537 assert(!Freqs
.empty());
538 return Freqs
[0].Integer
;
542 namespace bfi_detail
{
544 template <class BlockT
> struct TypeMap
{};
545 template <> struct TypeMap
<BasicBlock
> {
546 using BlockT
= BasicBlock
;
547 using FunctionT
= Function
;
548 using BranchProbabilityInfoT
= BranchProbabilityInfo
;
550 using LoopInfoT
= LoopInfo
;
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
;
560 /// Get the name of a MachineBasicBlock.
562 /// Get the name of a MachineBasicBlock. It's templated so that including from
563 /// CodeGen is unnecessary (that would be a layering issue).
565 /// This is used mainly for debug output. The name is similar to
566 /// MachineBasicBlock::getFullName(), but skips the name of the function.
567 template <class BlockT
> std::string
getBlockName(const BlockT
*BB
) {
568 assert(BB
&& "Unexpected nullptr");
569 auto MachineName
= "BB" + Twine(BB
->getNumber());
570 if (BB
->getBasicBlock())
571 return (MachineName
+ "[" + BB
->getName() + "]").str();
572 return MachineName
.str();
574 /// Get the name of a BasicBlock.
575 template <> inline std::string
getBlockName(const BasicBlock
*BB
) {
576 assert(BB
&& "Unexpected nullptr");
577 return BB
->getName().str();
580 /// Graph of irreducible control flow.
582 /// This graph is used for determining the SCCs in a loop (or top-level
583 /// function) that has irreducible control flow.
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.
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
;
599 using BlockNode
= BFIBase::BlockNode
;
603 std::deque
<const IrrNode
*> Edges
;
605 IrrNode(const BlockNode
&Node
) : Node(Node
) {}
607 using iterator
= std::deque
<const IrrNode
*>::const_iterator
;
609 iterator
pred_begin() const { return Edges
.begin(); }
610 iterator
succ_begin() const { return Edges
.begin() + NumIn
; }
611 iterator
pred_end() const { return succ_begin(); }
612 iterator
succ_end() const { return Edges
.end(); }
615 const IrrNode
*StartIrr
= nullptr;
616 std::vector
<IrrNode
> Nodes
;
617 SmallDenseMap
<uint32_t, IrrNode
*, 4> Lookup
;
619 /// Construct an explicit graph containing irreducible control flow.
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
626 /// \a BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected
628 template <class BlockEdgesAdder
>
629 IrreducibleGraph(BFIBase
&BFI
, const BFIBase::LoopData
*OuterLoop
,
630 BlockEdgesAdder addBlockEdges
) : BFI(BFI
) {
631 initialize(OuterLoop
, addBlockEdges
);
634 template <class BlockEdgesAdder
>
635 void initialize(const BFIBase::LoopData
*OuterLoop
,
636 BlockEdgesAdder addBlockEdges
);
637 void addNodesInLoop(const BFIBase::LoopData
&OuterLoop
);
638 void addNodesInFunction();
640 void addNode(const BlockNode
&Node
) {
641 Nodes
.emplace_back(Node
);
642 BFI
.Working
[Node
.Index
].getMass() = BlockMass::getEmpty();
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
);
653 template <class BlockEdgesAdder
>
654 void IrreducibleGraph::initialize(const BFIBase::LoopData
*OuterLoop
,
655 BlockEdgesAdder addBlockEdges
) {
657 addNodesInLoop(*OuterLoop
);
658 for (auto N
: OuterLoop
->Nodes
)
659 addEdges(N
, OuterLoop
, addBlockEdges
);
661 addNodesInFunction();
662 for (uint32_t Index
= 0; Index
< BFI
.Working
.size(); ++Index
)
663 addEdges(Index
, OuterLoop
, addBlockEdges
);
665 StartIrr
= Lookup
[Start
.Index
];
668 template <class BlockEdgesAdder
>
669 void IrreducibleGraph::addEdges(const BlockNode
&Node
,
670 const BFIBase::LoopData
*OuterLoop
,
671 BlockEdgesAdder addBlockEdges
) {
672 auto L
= Lookup
.find(Node
.Index
);
673 if (L
== Lookup
.end())
675 IrrNode
&Irr
= *L
->second
;
676 const auto &Working
= BFI
.Working
[Node
.Index
];
678 if (Working
.isAPackage())
679 for (const auto &I
: Working
.Loop
->Exits
)
680 addEdge(Irr
, I
.first
, OuterLoop
);
682 addBlockEdges(*this, Irr
, OuterLoop
);
685 } // end namespace bfi_detail
687 /// Shared implementation for block frequency analysis.
689 /// This is a shared implementation of BlockFrequencyInfo and
690 /// MachineBlockFrequencyInfo, and calculates the relative frequencies of
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.)
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.
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.
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.
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
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.
724 /// These are the main stages:
726 /// 0. Reverse post-order traversal (\a initializeRPOT()).
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.
732 /// 1. Loop initialization (\a initializeLoops()).
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.
738 /// 2. Calculate mass and scale in loops (\a computeMassInLoops()).
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.
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:
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.
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.
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.
767 /// - Normalize the distribution: scale weights down so that their sum
768 /// is 32-bits, and coalesce multiple edges to the same node.
770 /// - Distribute the mass accordingly, dithering to minimize mass loss,
771 /// as described in \a distributeMass().
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
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.
784 /// Finally, calculate the loop scale from the accumulated backedge mass.
786 /// 3. Distribute mass in the function (\a computeMassInFunction()).
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.
792 /// 4. Unpackage loops (\a unwrapLoops()).
794 /// Initialize each block's frequency to a floating point representation of
797 /// Visit loops top-down, scaling the frequencies of its immediate members
798 /// by the loop's pseudo-node's frequency.
800 /// 5. Convert frequencies to a 64-bit range (\a finalizeMetrics()).
802 /// Using the min and max frequencies as a guide, translate floating point
803 /// frequencies to an appropriate range in uint64_t.
805 /// It has some known flaws.
807 /// - The model of irreducible control flow is a rough approximation.
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.
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
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.
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
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
>;
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
*>>;
853 const BranchProbabilityInfoT
*BPI
= nullptr;
854 const LoopInfoT
*LI
= nullptr;
855 const FunctionT
*F
= nullptr;
857 // All blocks in reverse postorder.
858 std::vector
<const BlockT
*> RPOT
;
859 DenseMap
<const BlockT
*, BlockNode
> Nodes
;
861 using rpot_iterator
= typename
std::vector
<const BlockT
*>::const_iterator
;
863 rpot_iterator
rpot_begin() const { return RPOT
.begin(); }
864 rpot_iterator
rpot_end() const { return RPOT
.end(); }
866 size_t getIndex(const rpot_iterator
&I
) const { return I
- rpot_begin(); }
868 BlockNode
getNode(const rpot_iterator
&I
) const {
869 return BlockNode(getIndex(I
));
871 BlockNode
getNode(const BlockT
*BB
) const { return Nodes
.lookup(BB
); }
873 const BlockT
*getBlock(const BlockNode
&Node
) const {
874 assert(Node
.Index
< RPOT
.size());
875 return RPOT
[Node
.Index
];
878 /// Run (and save) a post-order traversal.
880 /// Saves a reverse post-order traversal of all the nodes in \a F.
881 void initializeRPOT();
883 /// Initialize loop data.
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();
892 /// Propagate to a block's successors.
894 /// In the context of distributing mass through \c OuterLoop, divide the mass
895 /// currently assigned to \c Node between its successors.
897 /// \return \c true unless there's an irreducible backedge.
898 bool propagateMassToSuccessors(LoopData
*OuterLoop
, const BlockNode
&Node
);
900 /// Compute mass in a particular loop.
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.
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
);
910 /// Try to compute mass in the top-level function.
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.
916 /// \pre \a computeMassInLoops() has been called.
917 /// \return \c true unless there's an irreducible backedge.
918 bool tryToComputeMassInFunction();
920 /// Compute mass in (and package up) irreducible SCCs.
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.
925 /// If \c OuterLoop is \c nullptr, it refers to the top-level function.
927 /// \pre \a computeMassInLoop() has been called for each subloop of \c
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
);
935 /// Compute mass in all loops.
937 /// For each loop bottom-up, call \a computeMassInLoop().
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().
943 /// \post \a computeMassInLoop() has returned \c true for every loop.
944 void computeMassInLoops();
946 /// Compute mass in the top-level function.
948 /// Uses \a tryToComputeMassInFunction() and \a computeIrreducibleMass() to
949 /// compute mass in the top-level function.
951 /// \post \a tryToComputeMassInFunction() has returned \c true.
952 void computeMassInFunction();
954 std::string
getBlockName(const BlockNode
&Node
) const override
{
955 return bfi_detail::getBlockName(getBlock(Node
));
959 BlockFrequencyInfoImpl() = default;
961 const FunctionT
*getFunction() const { return F
; }
963 void calculate(const FunctionT
&F
, const BranchProbabilityInfoT
&BPI
,
964 const LoopInfoT
&LI
);
966 using BlockFrequencyInfoImplBase::getEntryFreq
;
968 BlockFrequency
getBlockFreq(const BlockT
*BB
) const {
969 return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB
));
972 Optional
<uint64_t> getBlockProfileCount(const Function
&F
,
974 bool AllowSynthetic
= false) const {
975 return BlockFrequencyInfoImplBase::getBlockProfileCount(F
, getNode(BB
),
979 Optional
<uint64_t> getProfileCountFromFreq(const Function
&F
,
981 bool AllowSynthetic
= false) const {
982 return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F
, Freq
,
986 bool isIrrLoopHeader(const BlockT
*BB
) {
987 return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB
));
990 void setBlockFreq(const BlockT
*BB
, uint64_t Freq
);
992 Scaled64
getFloatingBlockFreq(const BlockT
*BB
) const {
993 return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB
));
996 const BranchProbabilityInfoT
&getBPI() const { return *BPI
; }
998 /// Print the frequencies for the current function.
1000 /// Prints the frequencies for the blocks in the current function.
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.
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
;
1011 using BlockFrequencyInfoImplBase::dump
;
1012 using BlockFrequencyInfoImplBase::printBlockFreq
;
1014 raw_ostream
&printBlockFreq(raw_ostream
&OS
, const BlockT
*BB
) const {
1015 return BlockFrequencyInfoImplBase::printBlockFreq(OS
, getNode(BB
));
1020 void BlockFrequencyInfoImpl
<BT
>::calculate(const FunctionT
&F
,
1021 const BranchProbabilityInfoT
&BPI
,
1022 const LoopInfoT
&LI
) {
1023 // Save the parameters.
1028 // Clean up left-over data structures.
1029 BlockFrequencyInfoImplBase::clear();
1034 LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F
.getName()
1035 << "\n================="
1036 << std::string(F
.getName().size(), '=') << "\n");
1040 // Visit loops in post-order to find the local mass distribution, and then do
1041 // the full function.
1042 computeMassInLoops();
1043 computeMassInFunction();
1049 void BlockFrequencyInfoImpl
<BT
>::setBlockFreq(const BlockT
*BB
, uint64_t Freq
) {
1050 if (Nodes
.count(BB
))
1051 BlockFrequencyInfoImplBase::setBlockFreq(getNode(BB
), Freq
);
1053 // If BB is a newly added block after BFI is done, we need to create a new
1054 // BlockNode for it assigned with a new index. The index can be determined
1055 // by the size of Freqs.
1056 BlockNode
NewNode(Freqs
.size());
1057 Nodes
[BB
] = NewNode
;
1058 Freqs
.emplace_back();
1059 BlockFrequencyInfoImplBase::setBlockFreq(NewNode
, Freq
);
1063 template <class BT
> void BlockFrequencyInfoImpl
<BT
>::initializeRPOT() {
1064 const BlockT
*Entry
= &F
->front();
1065 RPOT
.reserve(F
->size());
1066 std::copy(po_begin(Entry
), po_end(Entry
), std::back_inserter(RPOT
));
1067 std::reverse(RPOT
.begin(), RPOT
.end());
1069 assert(RPOT
.size() - 1 <= BlockNode::getMaxIndex() &&
1070 "More nodes in function than Block Frequency Info supports");
1072 LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
1073 for (rpot_iterator I
= rpot_begin(), E
= rpot_end(); I
!= E
; ++I
) {
1074 BlockNode Node
= getNode(I
);
1075 LLVM_DEBUG(dbgs() << " - " << getIndex(I
) << ": " << getBlockName(Node
)
1080 Working
.reserve(RPOT
.size());
1081 for (size_t Index
= 0; Index
< RPOT
.size(); ++Index
)
1082 Working
.emplace_back(Index
);
1083 Freqs
.resize(RPOT
.size());
1086 template <class BT
> void BlockFrequencyInfoImpl
<BT
>::initializeLoops() {
1087 LLVM_DEBUG(dbgs() << "loop-detection\n");
1091 // Visit loops top down and assign them an index.
1092 std::deque
<std::pair
<const LoopT
*, LoopData
*>> Q
;
1093 for (const LoopT
*L
: *LI
)
1094 Q
.emplace_back(L
, nullptr);
1095 while (!Q
.empty()) {
1096 const LoopT
*Loop
= Q
.front().first
;
1097 LoopData
*Parent
= Q
.front().second
;
1100 BlockNode Header
= getNode(Loop
->getHeader());
1101 assert(Header
.isValid());
1103 Loops
.emplace_back(Parent
, Header
);
1104 Working
[Header
.Index
].Loop
= &Loops
.back();
1105 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header
) << "\n");
1107 for (const LoopT
*L
: *Loop
)
1108 Q
.emplace_back(L
, &Loops
.back());
1111 // Visit nodes in reverse post-order and add them to their deepest containing
1113 for (size_t Index
= 0; Index
< RPOT
.size(); ++Index
) {
1114 // Loop headers have already been mostly mapped.
1115 if (Working
[Index
].isLoopHeader()) {
1116 LoopData
*ContainingLoop
= Working
[Index
].getContainingLoop();
1118 ContainingLoop
->Nodes
.push_back(Index
);
1122 const LoopT
*Loop
= LI
->getLoopFor(RPOT
[Index
]);
1126 // Add this node to its containing loop's member list.
1127 BlockNode Header
= getNode(Loop
->getHeader());
1128 assert(Header
.isValid());
1129 const auto &HeaderData
= Working
[Header
.Index
];
1130 assert(HeaderData
.isLoopHeader());
1132 Working
[Index
].Loop
= HeaderData
.Loop
;
1133 HeaderData
.Loop
->Nodes
.push_back(Index
);
1134 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header
)
1135 << ": member = " << getBlockName(Index
) << "\n");
1139 template <class BT
> void BlockFrequencyInfoImpl
<BT
>::computeMassInLoops() {
1140 // Visit loops with the deepest first, and the top-level loops last.
1141 for (auto L
= Loops
.rbegin(), E
= Loops
.rend(); L
!= E
; ++L
) {
1142 if (computeMassInLoop(*L
))
1144 auto Next
= std::next(L
);
1145 computeIrreducibleMass(&*L
, L
.base());
1146 L
= std::prev(Next
);
1147 if (computeMassInLoop(*L
))
1149 llvm_unreachable("unhandled irreducible control flow");
1154 bool BlockFrequencyInfoImpl
<BT
>::computeMassInLoop(LoopData
&Loop
) {
1155 // Compute mass in loop.
1156 LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop
) << "\n");
1158 if (Loop
.isIrreducible()) {
1159 LLVM_DEBUG(dbgs() << "isIrreducible = true\n");
1161 unsigned NumHeadersWithWeight
= 0;
1162 Optional
<uint64_t> MinHeaderWeight
;
1163 DenseSet
<uint32_t> HeadersWithoutWeight
;
1164 HeadersWithoutWeight
.reserve(Loop
.NumHeaders
);
1165 for (uint32_t H
= 0; H
< Loop
.NumHeaders
; ++H
) {
1166 auto &HeaderNode
= Loop
.Nodes
[H
];
1167 const BlockT
*Block
= getBlock(HeaderNode
);
1168 IsIrrLoopHeader
.set(Loop
.Nodes
[H
].Index
);
1169 Optional
<uint64_t> HeaderWeight
= Block
->getIrrLoopHeaderWeight();
1170 if (!HeaderWeight
) {
1171 LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on "
1172 << getBlockName(HeaderNode
) << "\n");
1173 HeadersWithoutWeight
.insert(H
);
1176 LLVM_DEBUG(dbgs() << getBlockName(HeaderNode
)
1177 << " has irr loop header weight "
1178 << HeaderWeight
.getValue() << "\n");
1179 NumHeadersWithWeight
++;
1180 uint64_t HeaderWeightValue
= HeaderWeight
.getValue();
1181 if (!MinHeaderWeight
|| HeaderWeightValue
< MinHeaderWeight
)
1182 MinHeaderWeight
= HeaderWeightValue
;
1183 if (HeaderWeightValue
) {
1184 Dist
.addLocal(HeaderNode
, HeaderWeightValue
);
1187 // As a heuristic, if some headers don't have a weight, give them the
1188 // minimium weight seen (not to disrupt the existing trends too much by
1189 // using a weight that's in the general range of the other headers' weights,
1190 // and the minimum seems to perform better than the average.)
1191 // FIXME: better update in the passes that drop the header weight.
1192 // If no headers have a weight, give them even weight (use weight 1).
1193 if (!MinHeaderWeight
)
1194 MinHeaderWeight
= 1;
1195 for (uint32_t H
: HeadersWithoutWeight
) {
1196 auto &HeaderNode
= Loop
.Nodes
[H
];
1197 assert(!getBlock(HeaderNode
)->getIrrLoopHeaderWeight() &&
1198 "Shouldn't have a weight metadata");
1199 uint64_t MinWeight
= MinHeaderWeight
.getValue();
1200 LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight
<< " to "
1201 << getBlockName(HeaderNode
) << "\n");
1203 Dist
.addLocal(HeaderNode
, MinWeight
);
1205 distributeIrrLoopHeaderMass(Dist
);
1206 for (const BlockNode
&M
: Loop
.Nodes
)
1207 if (!propagateMassToSuccessors(&Loop
, M
))
1208 llvm_unreachable("unhandled irreducible control flow");
1209 if (NumHeadersWithWeight
== 0)
1210 // No headers have a metadata. Adjust header mass.
1211 adjustLoopHeaderMass(Loop
);
1213 Working
[Loop
.getHeader().Index
].getMass() = BlockMass::getFull();
1214 if (!propagateMassToSuccessors(&Loop
, Loop
.getHeader()))
1215 llvm_unreachable("irreducible control flow to loop header!?");
1216 for (const BlockNode
&M
: Loop
.members())
1217 if (!propagateMassToSuccessors(&Loop
, M
))
1218 // Irreducible backedge.
1222 computeLoopScale(Loop
);
1228 bool BlockFrequencyInfoImpl
<BT
>::tryToComputeMassInFunction() {
1229 // Compute mass in function.
1230 LLVM_DEBUG(dbgs() << "compute-mass-in-function\n");
1231 assert(!Working
.empty() && "no blocks in function");
1232 assert(!Working
[0].isLoopHeader() && "entry block is a loop header");
1234 Working
[0].getMass() = BlockMass::getFull();
1235 for (rpot_iterator I
= rpot_begin(), IE
= rpot_end(); I
!= IE
; ++I
) {
1236 // Check for nodes that have been packaged.
1237 BlockNode Node
= getNode(I
);
1238 if (Working
[Node
.Index
].isPackaged())
1241 if (!propagateMassToSuccessors(nullptr, Node
))
1247 template <class BT
> void BlockFrequencyInfoImpl
<BT
>::computeMassInFunction() {
1248 if (tryToComputeMassInFunction())
1250 computeIrreducibleMass(nullptr, Loops
.begin());
1251 if (tryToComputeMassInFunction())
1253 llvm_unreachable("unhandled irreducible control flow");
1256 /// \note This should be a lambda, but that crashes GCC 4.7.
1257 namespace bfi_detail
{
1259 template <class BT
> struct BlockEdgesAdder
{
1261 using LoopData
= BlockFrequencyInfoImplBase::LoopData
;
1262 using Successor
= GraphTraits
<const BlockT
*>;
1264 const BlockFrequencyInfoImpl
<BT
> &BFI
;
1266 explicit BlockEdgesAdder(const BlockFrequencyInfoImpl
<BT
> &BFI
)
1269 void operator()(IrreducibleGraph
&G
, IrreducibleGraph::IrrNode
&Irr
,
1270 const LoopData
*OuterLoop
) {
1271 const BlockT
*BB
= BFI
.RPOT
[Irr
.Node
.Index
];
1272 for (const auto Succ
: children
<const BlockT
*>(BB
))
1273 G
.addEdge(Irr
, BFI
.getNode(Succ
), OuterLoop
);
1277 } // end namespace bfi_detail
1280 void BlockFrequencyInfoImpl
<BT
>::computeIrreducibleMass(
1281 LoopData
*OuterLoop
, std::list
<LoopData
>::iterator Insert
) {
1282 LLVM_DEBUG(dbgs() << "analyze-irreducible-in-";
1283 if (OuterLoop
) dbgs()
1284 << "loop: " << getLoopName(*OuterLoop
) << "\n";
1285 else dbgs() << "function\n");
1287 using namespace bfi_detail
;
1289 // Ideally, addBlockEdges() would be declared here as a lambda, but that
1291 BlockEdgesAdder
<BT
> addBlockEdges(*this);
1292 IrreducibleGraph
G(*this, OuterLoop
, addBlockEdges
);
1294 for (auto &L
: analyzeIrreducible(G
, OuterLoop
, Insert
))
1295 computeMassInLoop(L
);
1299 updateLoopWithIrreducible(*OuterLoop
);
1302 // A helper function that converts a branch probability into weight.
1303 inline uint32_t getWeightFromBranchProb(const BranchProbability Prob
) {
1304 return Prob
.getNumerator();
1309 BlockFrequencyInfoImpl
<BT
>::propagateMassToSuccessors(LoopData
*OuterLoop
,
1310 const BlockNode
&Node
) {
1311 LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node
) << "\n");
1312 // Calculate probability for successors.
1314 if (auto *Loop
= Working
[Node
.Index
].getPackagedLoop()) {
1315 assert(Loop
!= OuterLoop
&& "Cannot propagate mass in a packaged loop");
1316 if (!addLoopSuccessorsToDist(OuterLoop
, *Loop
, Dist
))
1317 // Irreducible backedge.
1320 const BlockT
*BB
= getBlock(Node
);
1321 for (auto SI
= GraphTraits
<const BlockT
*>::child_begin(BB
),
1322 SE
= GraphTraits
<const BlockT
*>::child_end(BB
);
1325 Dist
, OuterLoop
, Node
, getNode(*SI
),
1326 getWeightFromBranchProb(BPI
->getEdgeProbability(BB
, SI
))))
1327 // Irreducible backedge.
1331 // Distribute mass to successors, saving exit and backedge data in the
1333 distributeMass(Node
, OuterLoop
, Dist
);
1338 raw_ostream
&BlockFrequencyInfoImpl
<BT
>::print(raw_ostream
&OS
) const {
1341 OS
<< "block-frequency-info: " << F
->getName() << "\n";
1342 for (const BlockT
&BB
: *F
) {
1343 OS
<< " - " << bfi_detail::getBlockName(&BB
) << ": float = ";
1344 getFloatingBlockFreq(&BB
).print(OS
, 5)
1345 << ", int = " << getBlockFreq(&BB
).getFrequency();
1346 if (Optional
<uint64_t> ProfileCount
=
1347 BlockFrequencyInfoImplBase::getBlockProfileCount(
1348 F
->getFunction(), getNode(&BB
)))
1349 OS
<< ", count = " << ProfileCount
.getValue();
1350 if (Optional
<uint64_t> IrrLoopHeaderWeight
=
1351 BB
.getIrrLoopHeaderWeight())
1352 OS
<< ", irr_loop_header_weight = " << IrrLoopHeaderWeight
.getValue();
1356 // Add an extra newline for readability.
1361 // Graph trait base class for block frequency information graph
1364 enum GVDAGType
{ GVDT_None
, GVDT_Fraction
, GVDT_Integer
, GVDT_Count
};
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
;
1373 uint64_t MaxFrequency
= 0;
1375 explicit BFIDOTGraphTraitsBase(bool isSimple
= false)
1376 : DefaultDOTGraphTraits(isSimple
) {}
1378 static std::string
getGraphName(const BlockFrequencyInfoT
*G
) {
1379 return G
->getFunction()->getName();
1382 std::string
getNodeAttributes(NodeRef Node
, const BlockFrequencyInfoT
*Graph
,
1383 unsigned HotPercentThreshold
= 0) {
1385 if (!HotPercentThreshold
)
1388 // Compute MaxFrequency on the fly:
1389 if (!MaxFrequency
) {
1390 for (NodeIter I
= GTraits::nodes_begin(Graph
),
1391 E
= GTraits::nodes_end(Graph
);
1395 std::max(MaxFrequency
, Graph
->getBlockFreq(N
).getFrequency());
1398 BlockFrequency Freq
= Graph
->getBlockFreq(Node
);
1399 BlockFrequency HotFreq
=
1400 (BlockFrequency(MaxFrequency
) *
1401 BranchProbability::getBranchProbability(HotPercentThreshold
, 100));
1406 raw_string_ostream
OS(Result
);
1407 OS
<< "color=\"red\"";
1412 std::string
getNodeLabel(NodeRef Node
, const BlockFrequencyInfoT
*Graph
,
1413 GVDAGType GType
, int layout_order
= -1) {
1415 raw_string_ostream
OS(Result
);
1417 if (layout_order
!= -1)
1418 OS
<< Node
->getName() << "[" << layout_order
<< "] : ";
1420 OS
<< Node
->getName() << " : ";
1423 Graph
->printBlockFreq(OS
, Node
);
1426 OS
<< Graph
->getBlockFreq(Node
).getFrequency();
1429 auto Count
= Graph
->getBlockProfileCount(Node
);
1431 OS
<< Count
.getValue();
1437 llvm_unreachable("If we are not supposed to render a graph we should "
1438 "never reach this point.");
1443 std::string
getEdgeAttributes(NodeRef Node
, EdgeIter EI
,
1444 const BlockFrequencyInfoT
*BFI
,
1445 const BranchProbabilityInfoT
*BPI
,
1446 unsigned HotPercentThreshold
= 0) {
1451 BranchProbability BP
= BPI
->getEdgeProbability(Node
, EI
);
1452 uint32_t N
= BP
.getNumerator();
1453 uint32_t D
= BP
.getDenominator();
1454 double Percent
= 100.0 * N
/ D
;
1455 raw_string_ostream
OS(Str
);
1456 OS
<< format("label=\"%.1f%%\"", Percent
);
1458 if (HotPercentThreshold
) {
1459 BlockFrequency EFreq
= BFI
->getBlockFreq(Node
) * BP
;
1460 BlockFrequency HotFreq
= BlockFrequency(MaxFrequency
) *
1461 BranchProbability(HotPercentThreshold
, 100);
1463 if (EFreq
>= HotFreq
) {
1464 OS
<< ",color=\"red\"";
1473 } // end namespace llvm
1477 #endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H