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