Line data    Source code

       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          17 : 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          36 :   for (auto &Node : SCC)
      36          19 :     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          36 :   for (const auto &Node : SCCNodes) {
      41          41 :     for (auto &E : children_edges<CallGraphType>(Node)) {
      42          22 :       if (SCCNodes.count(CGT::edge_dest(E)))
      43           4 :         SCCEdges.emplace_back(Node, E);
      44             :       else
      45          18 :         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          21 :   for (auto &E : SCCEdges) {
      59           4 :     auto OptRelFreq = GetRelBBFreq(E.second);
      60           4 :     if (!OptRelFreq)
      61             :       continue;
      62           4 :     Scaled64 RelFreq = OptRelFreq.getValue();
      63           4 :     auto Caller = E.first;
      64           4 :     auto Callee = CGT::edge_dest(E.second);
      65           4 :     RelFreq *= Scaled64(GetCount(Caller), 0);
      66           4 :     uint64_t AdditionalCount = RelFreq.toInt<uint64_t>();
      67           4 :     AdditionalCounts[Callee] += AdditionalCount;
      68             :   }
      69             : 
      70             :   // Update the counts for the nodes in the SCC.
      71          21 :   for (auto &Entry : AdditionalCounts)
      72           4 :     AddCount(Entry.first, Entry.second);
      73             : 
      74             :   // Now update the counts for nodes outside the SCC.
      75          35 :   for (auto &E : NonSCCEdges) {
      76          18 :     auto OptRelFreq = GetRelBBFreq(E.second);
      77          18 :     if (!OptRelFreq)
      78             :       continue;
      79           3 :     Scaled64 RelFreq = OptRelFreq.getValue();
      80           3 :     auto Caller = E.first;
      81           3 :     auto Callee = CGT::edge_dest(E.second);
      82           3 :     RelFreq *= Scaled64(GetCount(Caller), 0);
      83           3 :     AddCount(Callee, RelFreq.toInt<uint64_t>());
      84             :   }
      85          17 : }
      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           3 : void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
      97             :                                                     GetRelBBFreqTy GetRelBBFreq,
      98             :                                                     GetCountTy GetCount,
      99             :                                                     AddCountTy AddCount) {
     100           3 :   std::vector<SccTy> SCCs;
     101             : 
     102             :   // Collect all the SCCs.
     103          20 :   for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
     104          17 :     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          20 :   for (auto &SCC : reverse(SCCs))
     110          17 :     propagateFromSCC(SCC, GetRelBBFreq, GetCount, AddCount);
     111           3 : }
     112             : 
     113             : template class llvm::SyntheticCountsUtils<const CallGraph *>;