LLVM  12.0.0git
SyntheticCountsPropagation.cpp
Go to the documentation of this file.
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 
28 #include "llvm/ADT/DenseSet.h"
29 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/Module.h"
38 #include "llvm/Support/Debug.h"
40 
41 using namespace llvm;
44 
45 #define DEBUG_TYPE "synthetic-counts-propagation"
46 
47 /// Initial synthetic count assigned to functions.
49  InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
51  cl::desc("Initial value of synthetic entry count."));
52 
53 /// Initial synthetic count assigned to inline functions.
55  "inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore,
56  cl::desc("Initial synthetic entry count for inline functions."));
57 
58 /// Initial synthetic count assigned to cold functions.
60  "cold-synthetic-count", cl::Hidden, cl::init(5), cl::ZeroOrMore,
61  cl::desc("Initial synthetic entry count for cold functions."));
62 
63 // Assign initial synthetic entry counts to functions.
64 static void
65 initializeCounts(Module &M, function_ref<void(Function *, uint64_t)> SetCount) {
66  auto MayHaveIndirectCalls = [](Function &F) {
67  for (auto *U : F.users()) {
68  if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
69  return true;
70  }
71  return false;
72  };
73 
74  for (Function &F : M) {
75  uint64_t InitialCount = InitialSyntheticCount;
76  if (F.isDeclaration())
77  continue;
78  if (F.hasFnAttribute(Attribute::AlwaysInline) ||
79  F.hasFnAttribute(Attribute::InlineHint)) {
80  // Use a higher value for inline functions to account for the fact that
81  // these are usually beneficial to inline.
82  InitialCount = InlineSyntheticCount;
83  } else if (F.hasLocalLinkage() && !MayHaveIndirectCalls(F)) {
84  // Local functions without inline hints get counts only through
85  // propagation.
86  InitialCount = 0;
87  } else if (F.hasFnAttribute(Attribute::Cold) ||
88  F.hasFnAttribute(Attribute::NoInline)) {
89  // Use a lower value for noinline and cold functions.
90  InitialCount = ColdSyntheticCount;
91  }
92  SetCount(&F, InitialCount);
93  }
94 }
95 
97  ModuleAnalysisManager &MAM) {
99  MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
101  // Set initial entry counts.
103  M, [&](Function *F, uint64_t Count) { Counts[F] = Scaled64(Count, 0); });
104 
105  // Edge includes information about the source. Hence ignore the first
106  // parameter.
107  auto GetCallSiteProfCount = [&](const CallGraphNode *,
108  const CallGraphNode::CallRecord &Edge) {
109  Optional<Scaled64> Res = None;
110  if (!Edge.first)
111  return Res;
112  CallBase &CB = *cast<CallBase>(*Edge.first);
113  Function *Caller = CB.getCaller();
114  auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller);
115 
116  // Now compute the callsite count from relative frequency and
117  // entry count:
118  BasicBlock *CSBB = CB.getParent();
119  Scaled64 EntryFreq(BFI.getEntryFreq(), 0);
120  Scaled64 BBCount(BFI.getBlockFreq(CSBB).getFrequency(), 0);
121  BBCount /= EntryFreq;
122  BBCount *= Counts[Caller];
123  return Optional<Scaled64>(BBCount);
124  };
125 
126  CallGraph CG(M);
127  // Propgate the entry counts on the callgraph.
129  &CG, GetCallSiteProfCount, [&](const CallGraphNode *N, Scaled64 New) {
130  auto F = N->getFunction();
131  if (!F || F->isDeclaration())
132  return;
133 
134  Counts[F] += New;
135  });
136 
137  // Set the counts as metadata.
138  for (auto Entry : Counts) {
139  Entry.first->setEntryCount(ProfileCount(
140  Entry.second.template toInt<uint64_t>(), Function::PCT_Synthetic));
141  }
142 
143  return PreservedAnalyses::all();
144 }
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
Function * getCaller()
Helper to get the caller (the parent function).
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
cl::opt< int > InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10), cl::ZeroOrMore, cl::desc("Initial value of synthetic entry count."))
Initial synthetic count assigned to functions.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
A node in the call graph for a module.
Definition: CallGraph.h:174
static cl::opt< int > ColdSyntheticCount("cold-synthetic-count", cl::Hidden, cl::init(5), cl::ZeroOrMore, cl::desc("Initial synthetic entry count for cold functions."))
Initial synthetic count assigned to cold functions.
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
static void propagate(const CallGraphType &CG, GetProfCountTy GetProfCount, AddCountTy AddCount)
Propgate synthetic entry counts on a callgraph CG.
Function::ProfileCount ProfileCount
std::pair< Optional< WeakTrackingVH >, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called...
Definition: CallGraph.h:186
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
Class to represent profile counts.
Definition: Function.h:267
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:205
Analysis pass which computes BlockFrequencyInfo.
Module.h This file contains the declarations for the Module class.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM)
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
#define N
static void initializeCounts(Module &M, function_ref< void(Function *, uint64_t)> SetCount)
static cl::opt< int > InlineSyntheticCount("inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore, cl::desc("Initial synthetic entry count for inline functions."))
Initial synthetic count assigned to inline functions.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:227
ScaledNumber< uint64_t > Scaled64
A container for analyses that lazily runs them and caches their results.
const BasicBlock * getParent() const
Definition: Instruction.h:94
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:953