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/CallSite.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/ModuleSummaryIndex.h"
22
23 using namespace llvm;
24
25 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
26 template <typename CallGraphType>
propagateFromSCC(const SccTy & SCC,GetProfCountTy GetProfCount,AddCountTy AddCount)27 void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
28 const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
29
30 DenseSet<NodeRef> SCCNodes;
31 SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
32
33 for (auto &Node : SCC)
34 SCCNodes.insert(Node);
35
36 // Partition the edges coming out of the SCC into those whose destination is
37 // in the SCC and the rest.
38 for (const auto &Node : SCCNodes) {
39 for (auto &E : children_edges<CallGraphType>(Node)) {
40 if (SCCNodes.count(CGT::edge_dest(E)))
41 SCCEdges.emplace_back(Node, E);
42 else
43 NonSCCEdges.emplace_back(Node, E);
44 }
45 }
46
47 // For nodes in the same SCC, update the counts in two steps:
48 // 1. Compute the additional count for each node by propagating the counts
49 // along all incoming edges to the node that originate from within the same
50 // SCC and summing them up.
51 // 2. Add the additional counts to the nodes in the SCC.
52 // This ensures that the order of
53 // traversal of nodes within the SCC doesn't affect the final result.
54
55 DenseMap<NodeRef, Scaled64> AdditionalCounts;
56 for (auto &E : SCCEdges) {
57 auto OptProfCount = GetProfCount(E.first, E.second);
58 if (!OptProfCount)
59 continue;
60 auto Callee = CGT::edge_dest(E.second);
61 AdditionalCounts[Callee] += OptProfCount.getValue();
62 }
63
64 // Update the counts for the nodes in the SCC.
65 for (auto &Entry : AdditionalCounts)
66 AddCount(Entry.first, Entry.second);
67
68 // Now update the counts for nodes outside the SCC.
69 for (auto &E : NonSCCEdges) {
70 auto OptProfCount = GetProfCount(E.first, E.second);
71 if (!OptProfCount)
72 continue;
73 auto Callee = CGT::edge_dest(E.second);
74 AddCount(Callee, OptProfCount.getValue());
75 }
76 }
77
78 /// Propgate synthetic entry counts on a callgraph \p CG.
79 ///
80 /// This performs a reverse post-order traversal of the callgraph SCC. For each
81 /// SCC, it first propagates the entry counts to the nodes within the SCC
82 /// through call edges and updates them in one shot. Then the entry counts are
83 /// propagated to nodes outside the SCC. This requires \p GraphTraits
84 /// to have a specialization for \p CallGraphType.
85
86 template <typename CallGraphType>
propagate(const CallGraphType & CG,GetProfCountTy GetProfCount,AddCountTy AddCount)87 void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
88 GetProfCountTy GetProfCount,
89 AddCountTy AddCount) {
90 std::vector<SccTy> SCCs;
91
92 // Collect all the SCCs.
93 for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
94 SCCs.push_back(*I);
95
96 // The callgraph-scc needs to be visited in top-down order for propagation.
97 // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
98 // and call propagateFromSCC.
99 for (auto &SCC : reverse(SCCs))
100 propagateFromSCC(SCC, GetProfCount, AddCount);
101 }
102
103 template class llvm::SyntheticCountsUtils<const CallGraph *>;
104 template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;
105