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