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