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 22 using namespace llvm; 23 24 // Given an SCC, propagate entry counts along the edge of the SCC nodes. 25 template <typename CallGraphType> 26 void 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 85 template <typename CallGraphType> 86 void 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 102 template class llvm::SyntheticCountsUtils<const CallGraph *>; 103 template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>; 104