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