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