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
42using namespace llvm;
43using Scaled64 = ScaledNumber<uint64_t>;
44using ProfileCount = Function::ProfileCount;
45
46#define DEBUG_TYPE "synthetic-counts-propagation"
47
48/// Initial synthetic count assigned to functions.
49cl::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.
55static 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.
60static 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.
65static void
66initializeCounts(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
97PreservedAnalyses 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}
147