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
13#include "llvm/Analysis/SyntheticCountsUtils.h"
14#include "llvm/ADT/DenseSet.h"
15#include "llvm/ADT/SCCIterator.h"
16#include "llvm/Analysis/CallGraph.h"
17#include "llvm/IR/Function.h"
18#include "llvm/IR/InstIterator.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/ModuleSummaryIndex.h"
21
22using namespace llvm;
23
24// Given an SCC, propagate entry counts along the edge of the SCC nodes.
25template <typename CallGraphType>
26void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
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
85template <typename CallGraphType>
86void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
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
102template class llvm::SyntheticCountsUtils<const CallGraph *>;
103template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;
104