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