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 
19 using namespace llvm;
20 
21 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
22 template <typename CallGraphType>
23 void 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 
82 template <typename CallGraphType>
83 void 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 
99 template class llvm::SyntheticCountsUtils<const CallGraph *>;
100 template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;
101