SyntheticCountsUtils.cpp revision 336809 
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
24using namespace llvm;
25
26// Given an SCC, propagate entry counts along the edge of the SCC nodes.
27template <typename CallGraphType>
28void 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
95template <typename CallGraphType>
96void 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
113template class llvm::SyntheticCountsUtils<const CallGraph *>;
114