lib/Analysis/SyntheticCountsUtils.cpp

   1 //===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines utilities for propagating synthetic counts.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/SyntheticCountsUtils.h"
  15 #include "llvm/ADT/DenseSet.h"
  16 #include "llvm/ADT/SCCIterator.h"
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/Analysis/CallGraph.h"
  19 #include "llvm/IR/CallSite.h"
  20 #include "llvm/IR/Function.h"
  21 #include "llvm/IR/InstIterator.h"
  22 #include "llvm/IR/Instructions.h"
  23
  24 using namespace llvm;
  25
  26 // Given an SCC, propagate entry counts along the edge of the SCC nodes.
  27 template <typename CallGraphType>
  28 void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
  29     const SccTy &SCC, GetRelBBFreqTy GetRelBBFreq, GetCountTy GetCount,
  30     AddCountTy AddCount) {
  31
  32   SmallPtrSet<NodeRef, 8> SCCNodes;
  33   SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
  34
  35   for (auto &Node : SCC)
  36     SCCNodes.insert(Node);
  37
  38   // Partition the edges coming out of the SCC into those whose destination is
  39   // in the SCC and the rest.
  40   for (const auto &Node : SCCNodes) {
  41     for (auto &E : children_edges<CallGraphType>(Node)) {
  42       if (SCCNodes.count(CGT::edge_dest(E)))
  43         SCCEdges.emplace_back(Node, E);
  44       else
  45         NonSCCEdges.emplace_back(Node, E);
  46     }
  47   }
  48
  49   // For nodes in the same SCC, update the counts in two steps:
  50   // 1. Compute the additional count for each node by propagating the counts
  51   // along all incoming edges to the node that originate from within the same
  52   // SCC and summing them up.
  53   // 2. Add the additional counts to the nodes in the SCC.
  54   // This ensures that the order of
  55   // traversal of nodes within the SCC doesn't affect the final result.
  56
  57   DenseMap<NodeRef, uint64_t> AdditionalCounts;
  58   for (auto &E : SCCEdges) {
  59     auto OptRelFreq = GetRelBBFreq(E.second);
  60     if (!OptRelFreq)
  61       continue;
  62     Scaled64 RelFreq = OptRelFreq.getValue();
  63     auto Caller = E.first;
  64     auto Callee = CGT::edge_dest(E.second);
  65     RelFreq *= Scaled64(GetCount(Caller), 0);
  66     uint64_t AdditionalCount = RelFreq.toInt<uint64_t>();
  67     AdditionalCounts[Callee] += AdditionalCount;
  68   }
  69
  70   // Update the counts for the nodes in the SCC.
  71   for (auto &Entry : AdditionalCounts)
  72     AddCount(Entry.first, Entry.second);
  73
  74   // Now update the counts for nodes outside the SCC.
  75   for (auto &E : NonSCCEdges) {
  76     auto OptRelFreq = GetRelBBFreq(E.second);
  77     if (!OptRelFreq)
  78       continue;
  79     Scaled64 RelFreq = OptRelFreq.getValue();
  80     auto Caller = E.first;
  81     auto Callee = CGT::edge_dest(E.second);
  82     RelFreq *= Scaled64(GetCount(Caller), 0);
  83     AddCount(Callee, RelFreq.toInt<uint64_t>());
  84   }
  85 }
  86
  87 /// Propgate synthetic entry counts on a callgraph \p CG.
  88 ///
  89 /// This performs a reverse post-order traversal of the callgraph SCC. For each
  90 /// SCC, it first propagates the entry counts to the nodes within the SCC
  91 /// through call edges and updates them in one shot. Then the entry counts are
  92 /// propagated to nodes outside the SCC. This requires \p GraphTraits
  93 /// to have a specialization for \p CallGraphType.
  94
  95 template <typename CallGraphType>
  96 void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
  97                                                     GetRelBBFreqTy GetRelBBFreq,
  98                                                     GetCountTy GetCount,
  99                                                     AddCountTy AddCount) {
 100   std::vector<SccTy> SCCs;
 101
 102   // Collect all the SCCs.
 103   for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
 104     SCCs.push_back(*I);
 105
 106   // The callgraph-scc needs to be visited in top-down order for propagation.
 107   // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
 108   // and call propagateFromSCC.
 109   for (auto &SCC : reverse(SCCs))
 110     propagateFromSCC(SCC, GetRelBBFreq, GetCount, AddCount);
 111 }
 112
 113 template class llvm::SyntheticCountsUtils<const CallGraph *>;