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