1336809Sdim//===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===// 2336809Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336809Sdim// 7336809Sdim//===----------------------------------------------------------------------===// 8336809Sdim// 9336809Sdim// This file defines utilities for propagating synthetic counts. 10336809Sdim// 11336809Sdim//===----------------------------------------------------------------------===// 12336809Sdim 13336809Sdim#include "llvm/Analysis/SyntheticCountsUtils.h" 14336809Sdim#include "llvm/ADT/DenseSet.h" 15336809Sdim#include "llvm/ADT/SCCIterator.h" 16336809Sdim#include "llvm/Analysis/CallGraph.h" 17336809Sdim#include "llvm/IR/CallSite.h" 18336809Sdim#include "llvm/IR/Function.h" 19336809Sdim#include "llvm/IR/InstIterator.h" 20336809Sdim#include "llvm/IR/Instructions.h" 21344779Sdim#include "llvm/IR/ModuleSummaryIndex.h" 22336809Sdim 23336809Sdimusing namespace llvm; 24336809Sdim 25336809Sdim// Given an SCC, propagate entry counts along the edge of the SCC nodes. 26336809Sdimtemplate <typename CallGraphType> 27336809Sdimvoid SyntheticCountsUtils<CallGraphType>::propagateFromSCC( 28344779Sdim const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) { 29336809Sdim 30344779Sdim DenseSet<NodeRef> SCCNodes; 31336809Sdim SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges; 32336809Sdim 33336809Sdim for (auto &Node : SCC) 34336809Sdim SCCNodes.insert(Node); 35336809Sdim 36336809Sdim // Partition the edges coming out of the SCC into those whose destination is 37336809Sdim // in the SCC and the rest. 38336809Sdim for (const auto &Node : SCCNodes) { 39336809Sdim for (auto &E : children_edges<CallGraphType>(Node)) { 40336809Sdim if (SCCNodes.count(CGT::edge_dest(E))) 41336809Sdim SCCEdges.emplace_back(Node, E); 42336809Sdim else 43336809Sdim NonSCCEdges.emplace_back(Node, E); 44336809Sdim } 45336809Sdim } 46336809Sdim 47336809Sdim // For nodes in the same SCC, update the counts in two steps: 48336809Sdim // 1. Compute the additional count for each node by propagating the counts 49336809Sdim // along all incoming edges to the node that originate from within the same 50336809Sdim // SCC and summing them up. 51336809Sdim // 2. Add the additional counts to the nodes in the SCC. 52336809Sdim // This ensures that the order of 53336809Sdim // traversal of nodes within the SCC doesn't affect the final result. 54336809Sdim 55344779Sdim DenseMap<NodeRef, Scaled64> AdditionalCounts; 56336809Sdim for (auto &E : SCCEdges) { 57344779Sdim auto OptProfCount = GetProfCount(E.first, E.second); 58344779Sdim if (!OptProfCount) 59336809Sdim continue; 60336809Sdim auto Callee = CGT::edge_dest(E.second); 61344779Sdim AdditionalCounts[Callee] += OptProfCount.getValue(); 62336809Sdim } 63336809Sdim 64336809Sdim // Update the counts for the nodes in the SCC. 65336809Sdim for (auto &Entry : AdditionalCounts) 66336809Sdim AddCount(Entry.first, Entry.second); 67336809Sdim 68336809Sdim // Now update the counts for nodes outside the SCC. 69336809Sdim for (auto &E : NonSCCEdges) { 70344779Sdim auto OptProfCount = GetProfCount(E.first, E.second); 71344779Sdim if (!OptProfCount) 72336809Sdim continue; 73336809Sdim auto Callee = CGT::edge_dest(E.second); 74344779Sdim AddCount(Callee, OptProfCount.getValue()); 75336809Sdim } 76336809Sdim} 77336809Sdim 78336809Sdim/// Propgate synthetic entry counts on a callgraph \p CG. 79336809Sdim/// 80336809Sdim/// This performs a reverse post-order traversal of the callgraph SCC. For each 81336809Sdim/// SCC, it first propagates the entry counts to the nodes within the SCC 82336809Sdim/// through call edges and updates them in one shot. Then the entry counts are 83336809Sdim/// propagated to nodes outside the SCC. This requires \p GraphTraits 84336809Sdim/// to have a specialization for \p CallGraphType. 85336809Sdim 86336809Sdimtemplate <typename CallGraphType> 87336809Sdimvoid SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG, 88344779Sdim GetProfCountTy GetProfCount, 89336809Sdim AddCountTy AddCount) { 90336809Sdim std::vector<SccTy> SCCs; 91336809Sdim 92336809Sdim // Collect all the SCCs. 93336809Sdim for (auto I = scc_begin(CG); !I.isAtEnd(); ++I) 94336809Sdim SCCs.push_back(*I); 95336809Sdim 96336809Sdim // The callgraph-scc needs to be visited in top-down order for propagation. 97336809Sdim // The scc iterator returns the scc in bottom-up order, so reverse the SCCs 98336809Sdim // and call propagateFromSCC. 99336809Sdim for (auto &SCC : reverse(SCCs)) 100344779Sdim propagateFromSCC(SCC, GetProfCount, AddCount); 101336809Sdim} 102336809Sdim 103336809Sdimtemplate class llvm::SyntheticCountsUtils<const CallGraph *>; 104344779Sdimtemplate class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>; 105