LLVM  16.0.0git
SyntheticCountsUtils.cpp
Go to the documentation of this file.
1 //===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines utilities for propagating synthetic counts.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/ADT/SCCIterator.h"
18 
19 using namespace llvm;
20 
21 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
22 template <typename CallGraphType>
24  const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
25 
26  DenseSet<NodeRef> SCCNodes;
27  SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
28 
29  for (auto &Node : SCC)
30  SCCNodes.insert(Node);
31 
32  // Partition the edges coming out of the SCC into those whose destination is
33  // in the SCC and the rest.
34  for (const auto &Node : SCCNodes) {
35  for (auto &E : children_edges<CallGraphType>(Node)) {
36  if (SCCNodes.count(CGT::edge_dest(E)))
37  SCCEdges.emplace_back(Node, E);
38  else
39  NonSCCEdges.emplace_back(Node, E);
40  }
41  }
42 
43  // For nodes in the same SCC, update the counts in two steps:
44  // 1. Compute the additional count for each node by propagating the counts
45  // along all incoming edges to the node that originate from within the same
46  // SCC and summing them up.
47  // 2. Add the additional counts to the nodes in the SCC.
48  // This ensures that the order of
49  // traversal of nodes within the SCC doesn't affect the final result.
50 
51  DenseMap<NodeRef, Scaled64> AdditionalCounts;
52  for (auto &E : SCCEdges) {
53  auto OptProfCount = GetProfCount(E.first, E.second);
54  if (!OptProfCount)
55  continue;
56  auto Callee = CGT::edge_dest(E.second);
57  AdditionalCounts[Callee] += *OptProfCount;
58  }
59 
60  // Update the counts for the nodes in the SCC.
61  for (auto &Entry : AdditionalCounts)
62  AddCount(Entry.first, Entry.second);
63 
64  // Now update the counts for nodes outside the SCC.
65  for (auto &E : NonSCCEdges) {
66  auto OptProfCount = GetProfCount(E.first, E.second);
67  if (!OptProfCount)
68  continue;
69  auto Callee = CGT::edge_dest(E.second);
70  AddCount(Callee, *OptProfCount);
71  }
72 }
73 
74 /// Propgate synthetic entry counts on a callgraph \p CG.
75 ///
76 /// This performs a reverse post-order traversal of the callgraph SCC. For each
77 /// SCC, it first propagates the entry counts to the nodes within the SCC
78 /// through call edges and updates them in one shot. Then the entry counts are
79 /// propagated to nodes outside the SCC. This requires \p GraphTraits
80 /// to have a specialization for \p CallGraphType.
81 
82 template <typename CallGraphType>
84  GetProfCountTy GetProfCount,
85  AddCountTy AddCount) {
86  std::vector<SccTy> SCCs;
87 
88  // Collect all the SCCs.
89  for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
90  SCCs.push_back(*I);
91 
92  // The callgraph-scc needs to be visited in top-down order for propagation.
93  // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
94  // and call propagateFromSCC.
95  for (auto &SCC : reverse(SCCs))
96  propagateFromSCC(SCC, GetProfCount, AddCount);
97 }
98 
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
SCCIterator.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::SyntheticCountsUtils::propagate
static void propagate(const CallGraphType &CG, GetProfCountTy GetProfCount, AddCountTy AddCount)
Propgate synthetic entry counts on a callgraph CG.
Definition: SyntheticCountsUtils.cpp:83
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
ModuleSummaryIndex.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
DenseSet.h
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:310
SyntheticCountsUtils.h
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
CallGraph.h
llvm::SyntheticCountsUtils
Class with methods to propagate synthetic entry counts.
Definition: SyntheticCountsUtils.h:27
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941