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
13#include "llvm/Analysis/SyntheticCountsUtils.h"
14#include "llvm/ADT/DenseSet.h"
15#include "llvm/ADT/SCCIterator.h"
16#include "llvm/Analysis/CallGraph.h"
17#include "llvm/IR/ModuleSummaryIndex.h"
18
19using namespace llvm;
20
21// Given an SCC, propagate entry counts along the edge of the SCC nodes.
22template <typename CallGraphType>
23void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
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>
83void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
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
99template class llvm::SyntheticCountsUtils<const CallGraph *>;
100template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;
101