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