LLVM  11.0.0git
SyntheticCountsUtils.cpp
Go to the documentation of this file.
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 
14 #include "llvm/ADT/DenseSet.h"
15 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/InstIterator.h"
19 #include "llvm/IR/Instructions.h"
21 
22 using namespace llvm;
23 
24 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
25 template <typename CallGraphType>
27  const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
28 
29  DenseSet<NodeRef> SCCNodes;
30  SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
31 
32  for (auto &Node : SCC)
33  SCCNodes.insert(Node);
34 
35  // Partition the edges coming out of the SCC into those whose destination is
36  // in the SCC and the rest.
37  for (const auto &Node : SCCNodes) {
38  for (auto &E : children_edges<CallGraphType>(Node)) {
39  if (SCCNodes.count(CGT::edge_dest(E)))
40  SCCEdges.emplace_back(Node, E);
41  else
42  NonSCCEdges.emplace_back(Node, E);
43  }
44  }
45 
46  // For nodes in the same SCC, update the counts in two steps:
47  // 1. Compute the additional count for each node by propagating the counts
48  // along all incoming edges to the node that originate from within the same
49  // SCC and summing them up.
50  // 2. Add the additional counts to the nodes in the SCC.
51  // This ensures that the order of
52  // traversal of nodes within the SCC doesn't affect the final result.
53 
54  DenseMap<NodeRef, Scaled64> AdditionalCounts;
55  for (auto &E : SCCEdges) {
56  auto OptProfCount = GetProfCount(E.first, E.second);
57  if (!OptProfCount)
58  continue;
59  auto Callee = CGT::edge_dest(E.second);
60  AdditionalCounts[Callee] += OptProfCount.getValue();
61  }
62 
63  // Update the counts for the nodes in the SCC.
64  for (auto &Entry : AdditionalCounts)
65  AddCount(Entry.first, Entry.second);
66 
67  // Now update the counts for nodes outside the SCC.
68  for (auto &E : NonSCCEdges) {
69  auto OptProfCount = GetProfCount(E.first, E.second);
70  if (!OptProfCount)
71  continue;
72  auto Callee = CGT::edge_dest(E.second);
73  AddCount(Callee, OptProfCount.getValue());
74  }
75 }
76 
77 /// Propgate synthetic entry counts on a callgraph \p CG.
78 ///
79 /// This performs a reverse post-order traversal of the callgraph SCC. For each
80 /// SCC, it first propagates the entry counts to the nodes within the SCC
81 /// through call edges and updates them in one shot. Then the entry counts are
82 /// propagated to nodes outside the SCC. This requires \p GraphTraits
83 /// to have a specialization for \p CallGraphType.
84 
85 template <typename CallGraphType>
87  GetProfCountTy GetProfCount,
88  AddCountTy AddCount) {
89  std::vector<SccTy> SCCs;
90 
91  // Collect all the SCCs.
92  for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
93  SCCs.push_back(*I);
94 
95  // The callgraph-scc needs to be visited in top-down order for propagation.
96  // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
97  // and call propagateFromSCC.
98  for (auto &SCC : reverse(SCCs))
99  propagateFromSCC(SCC, GetProfCount, AddCount);
100 }
101 
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:687
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:255
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static void propagate(const CallGraphType &CG, GetProfCountTy GetProfCount, AddCountTy AddCount)
Propgate synthetic entry counts on a callgraph CG.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
amdgpu Simplify well known AMD library false FunctionCallee Callee
#define I(x, y, z)
Definition: MD5.cpp:59
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:341
Class with methods to propagate synthetic entry counts.