SyntheticCountsUtils.cpp revision 344779
1336809Sdim//===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===// 2336809Sdim// 3336809Sdim// The LLVM Compiler Infrastructure 4336809Sdim// 5336809Sdim// This file is distributed under the University of Illinois Open Source 6336809Sdim// License. See LICENSE.TXT for details. 7336809Sdim// 8336809Sdim//===----------------------------------------------------------------------===// 9336809Sdim// 10336809Sdim// This file defines utilities for propagating synthetic counts. 11336809Sdim// 12336809Sdim//===----------------------------------------------------------------------===// 13336809Sdim 14336809Sdim#include "llvm/Analysis/SyntheticCountsUtils.h" 15336809Sdim#include "llvm/ADT/DenseSet.h" 16336809Sdim#include "llvm/ADT/SCCIterator.h" 17336809Sdim#include "llvm/Analysis/CallGraph.h" 18336809Sdim#include "llvm/IR/CallSite.h" 19336809Sdim#include "llvm/IR/Function.h" 20336809Sdim#include "llvm/IR/InstIterator.h" 21336809Sdim#include "llvm/IR/Instructions.h" 22344779Sdim#include "llvm/IR/ModuleSummaryIndex.h" 23336809Sdim 24336809Sdimusing namespace llvm; 25336809Sdim 26336809Sdim// Given an SCC, propagate entry counts along the edge of the SCC nodes. 27336809Sdimtemplate <typename CallGraphType> 28336809Sdimvoid SyntheticCountsUtils<CallGraphType>::propagateFromSCC( 29344779Sdim const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) { 30336809Sdim 31344779Sdim DenseSet<NodeRef> SCCNodes; 32336809Sdim SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges; 33336809Sdim 34336809Sdim for (auto &Node : SCC) 35336809Sdim SCCNodes.insert(Node); 36336809Sdim 37336809Sdim // Partition the edges coming out of the SCC into those whose destination is 38336809Sdim // in the SCC and the rest. 39336809Sdim for (const auto &Node : SCCNodes) { 40336809Sdim for (auto &E : children_edges<CallGraphType>(Node)) { 41336809Sdim if (SCCNodes.count(CGT::edge_dest(E))) 42336809Sdim SCCEdges.emplace_back(Node, E); 43336809Sdim else 44336809Sdim NonSCCEdges.emplace_back(Node, E); 45336809Sdim } 46336809Sdim } 47336809Sdim 48336809Sdim // For nodes in the same SCC, update the counts in two steps: 49336809Sdim // 1. Compute the additional count for each node by propagating the counts 50336809Sdim // along all incoming edges to the node that originate from within the same 51336809Sdim // SCC and summing them up. 52336809Sdim // 2. Add the additional counts to the nodes in the SCC. 53336809Sdim // This ensures that the order of 54336809Sdim // traversal of nodes within the SCC doesn't affect the final result. 55336809Sdim 56344779Sdim DenseMap<NodeRef, Scaled64> AdditionalCounts; 57336809Sdim for (auto &E : SCCEdges) { 58344779Sdim auto OptProfCount = GetProfCount(E.first, E.second); 59344779Sdim if (!OptProfCount) 60336809Sdim continue; 61336809Sdim auto Callee = CGT::edge_dest(E.second); 62344779Sdim AdditionalCounts[Callee] += OptProfCount.getValue(); 63336809Sdim } 64336809Sdim 65336809Sdim // Update the counts for the nodes in the SCC. 66336809Sdim for (auto &Entry : AdditionalCounts) 67336809Sdim AddCount(Entry.first, Entry.second); 68336809Sdim 69336809Sdim // Now update the counts for nodes outside the SCC. 70336809Sdim for (auto &E : NonSCCEdges) { 71344779Sdim auto OptProfCount = GetProfCount(E.first, E.second); 72344779Sdim if (!OptProfCount) 73336809Sdim continue; 74336809Sdim auto Callee = CGT::edge_dest(E.second); 75344779Sdim AddCount(Callee, OptProfCount.getValue()); 76336809Sdim } 77336809Sdim} 78336809Sdim 79336809Sdim/// Propgate synthetic entry counts on a callgraph \p CG. 80336809Sdim/// 81336809Sdim/// This performs a reverse post-order traversal of the callgraph SCC. For each 82336809Sdim/// SCC, it first propagates the entry counts to the nodes within the SCC 83336809Sdim/// through call edges and updates them in one shot. Then the entry counts are 84336809Sdim/// propagated to nodes outside the SCC. This requires \p GraphTraits 85336809Sdim/// to have a specialization for \p CallGraphType. 86336809Sdim 87336809Sdimtemplate <typename CallGraphType> 88336809Sdimvoid SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG, 89344779Sdim GetProfCountTy GetProfCount, 90336809Sdim AddCountTy AddCount) { 91336809Sdim std::vector<SccTy> SCCs; 92336809Sdim 93336809Sdim // Collect all the SCCs. 94336809Sdim for (auto I = scc_begin(CG); !I.isAtEnd(); ++I) 95336809Sdim SCCs.push_back(*I); 96336809Sdim 97336809Sdim // The callgraph-scc needs to be visited in top-down order for propagation. 98336809Sdim // The scc iterator returns the scc in bottom-up order, so reverse the SCCs 99336809Sdim // and call propagateFromSCC. 100336809Sdim for (auto &SCC : reverse(SCCs)) 101344779Sdim propagateFromSCC(SCC, GetProfCount, AddCount); 102336809Sdim} 103336809Sdim 104336809Sdimtemplate class llvm::SyntheticCountsUtils<const CallGraph *>; 105344779Sdimtemplate class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>; 106