LLVM 19.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"
18
19using namespace llvm;
20
21// Given an SCC, propagate entry counts along the edge of the SCC nodes.
22template <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
82template <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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
This file defines the DenseSet and SmallDenseSet classes.
#define I(x, y, z)
Definition: MD5.cpp:58
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Class with methods to propagate synthetic entry counts.
static void propagate(const CallGraphType &CG, GetProfCountTy GetProfCount, AddCountTy AddCount)
Propgate synthetic entry counts on a callgraph CG.
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
An efficient, type-erasing, non-owning reference to a callable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:233
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428