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