lib/Transforms/IPO/SyntheticCountsPropagation.cpp

   1 //=- SyntheticCountsPropagation.cpp - Propagate function counts --*- C++ -*-=//
   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 implements a transformation that synthesizes entry counts for
  10 // functions and attaches !prof metadata to functions with the synthesized
  11 // counts. The presence of !prof metadata with counter name set to
  12 // 'synthesized_function_entry_count' indicate that the value of the counter is
  13 // an estimation of the likely execution count of the function. This transform
  14 // is applied only in non PGO mode as functions get 'real' profile-based
  15 // function entry counts in the PGO mode.
  16 //
  17 // The transformation works by first assigning some initial values to the entry
  18 // counts of all functions and then doing a top-down traversal of the
  19 // callgraph-scc to propagate the counts. For each function the set of callsites
  20 // and their relative block frequency is gathered. The relative block frequency
  21 // multiplied by the entry count of the caller and added to the callee's entry
  22 // count. For non-trivial SCCs, the new counts are computed from the previous
  23 // counts and updated in one shot.
  24 //
  25 //===----------------------------------------------------------------------===//
  26
  27 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
  28 #include "llvm/ADT/DenseSet.h"
  29 #include "llvm/ADT/STLExtras.h"
  30 #include "llvm/Analysis/BlockFrequencyInfo.h"
  31 #include "llvm/Analysis/CallGraph.h"
  32 #include "llvm/Analysis/ProfileSummaryInfo.h"
  33 #include "llvm/Analysis/SyntheticCountsUtils.h"
  34 #include "llvm/IR/CallSite.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/Instructions.h"
  37 #include "llvm/IR/Module.h"
  38 #include "llvm/Support/CommandLine.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Support/raw_ostream.h"
  41
  42 using namespace llvm;
  43 using Scaled64 = ScaledNumber<uint64_t>;
  44 using ProfileCount = Function::ProfileCount;
  45
  46 #define DEBUG_TYPE "synthetic-counts-propagation"
  47
  48 /// Initial synthetic count assigned to functions.
  49 cl::opt<int>
  50     InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
  51                           cl::ZeroOrMore,
  52                           cl::desc("Initial value of synthetic entry count."));
  53
  54 /// Initial synthetic count assigned to inline functions.
  55 static cl::opt<int> InlineSyntheticCount(
  56     "inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore,
  57     cl::desc("Initial synthetic entry count for inline functions."));
  58
  59 /// Initial synthetic count assigned to cold functions.
  60 static cl::opt<int> ColdSyntheticCount(
  61     "cold-synthetic-count", cl::Hidden, cl::init(5), cl::ZeroOrMore,
  62     cl::desc("Initial synthetic entry count for cold functions."));
  63
  64 // Assign initial synthetic entry counts to functions.
  65 static void
  66 initializeCounts(Module &M, function_ref<void(Function *, uint64_t)> SetCount) {
  67   auto MayHaveIndirectCalls = [](Function &F) {
  68     for (auto *U : F.users()) {
  69       if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
  70         return true;
  71     }
  72     return false;
  73   };
  74
  75   for (Function &F : M) {
  76     uint64_t InitialCount = InitialSyntheticCount;
  77     if (F.isDeclaration())
  78       continue;
  79     if (F.hasFnAttribute(Attribute::AlwaysInline) ||
  80         F.hasFnAttribute(Attribute::InlineHint)) {
  81       // Use a higher value for inline functions to account for the fact that
  82       // these are usually beneficial to inline.
  83       InitialCount = InlineSyntheticCount;
  84     } else if (F.hasLocalLinkage() && !MayHaveIndirectCalls(F)) {
  85       // Local functions without inline hints get counts only through
  86       // propagation.
  87       InitialCount = 0;
  88     } else if (F.hasFnAttribute(Attribute::Cold) ||
  89                F.hasFnAttribute(Attribute::NoInline)) {
  90       // Use a lower value for noinline and cold functions.
  91       InitialCount = ColdSyntheticCount;
  92     }
  93     SetCount(&F, InitialCount);
  94   }
  95 }
  96
  97 PreservedAnalyses SyntheticCountsPropagation::run(Module &M,
  98                                                   ModuleAnalysisManager &MAM) {
  99   FunctionAnalysisManager &FAM =
 100       MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 101   DenseMap<Function *, Scaled64> Counts;
 102   // Set initial entry counts.
 103   initializeCounts(
 104       M, [&](Function *F, uint64_t Count) { Counts[F] = Scaled64(Count, 0); });
 105
 106   // Edge includes information about the source. Hence ignore the first
 107   // parameter.
 108   auto GetCallSiteProfCount = [&](const CallGraphNode *,
 109                                   const CallGraphNode::CallRecord &Edge) {
 110     Optional<Scaled64> Res = None;
 111     if (!Edge.first)
 112       return Res;
 113     assert(isa<Instruction>(Edge.first));
 114     CallSite CS(cast<Instruction>(Edge.first));
 115     Function *Caller = CS.getCaller();
 116     auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller);
 117
 118     // Now compute the callsite count from relative frequency and
 119     // entry count:
 120     BasicBlock *CSBB = CS.getInstruction()->getParent();
 121     Scaled64 EntryFreq(BFI.getEntryFreq(), 0);
 122     Scaled64 BBCount(BFI.getBlockFreq(CSBB).getFrequency(), 0);
 123     BBCount /= EntryFreq;
 124     BBCount *= Counts[Caller];
 125     return Optional<Scaled64>(BBCount);
 126   };
 127
 128   CallGraph CG(M);
 129   // Propgate the entry counts on the callgraph.
 130   SyntheticCountsUtils<const CallGraph *>::propagate(
 131       &CG, GetCallSiteProfCount, [&](const CallGraphNode *N, Scaled64 New) {
 132         auto F = N->getFunction();
 133         if (!F || F->isDeclaration())
 134           return;
 135
 136         Counts[F] += New;
 137       });
 138
 139   // Set the counts as metadata.
 140   for (auto Entry : Counts) {
 141     Entry.first->setEntryCount(ProfileCount(
 142         Entry.second.template toInt<uint64_t>(), Function::PCT_Synthetic));
 143   }
 144
 145   return PreservedAnalyses::all();
 146 }