llvm/lib/Analysis/SyntheticCountsUtils.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-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
  22 using namespace llvm;
  23
  24 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
  25 template <typename CallGraphType>
  26 void 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
  85 template <typename CallGraphType>
  86 void 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
 102 template class llvm::SyntheticCountsUtils<const CallGraph *>;
 103 template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;