LLVM 19.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
31#include "llvm/IR/Function.h"
33#include "llvm/IR/Module.h"
35
36using namespace llvm;
39
40#define DEBUG_TYPE "synthetic-counts-propagation"
41
42namespace llvm {
44 InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
45 cl::desc("Initial value of synthetic entry count"));
46} // namespace llvm
47
48/// Initial synthetic count assigned to inline functions.
50 "inline-synthetic-count", cl::Hidden, cl::init(15),
51 cl::desc("Initial synthetic entry count for inline functions."));
52
53/// Initial synthetic count assigned to cold functions.
55 "cold-synthetic-count", cl::Hidden, cl::init(5),
56 cl::desc("Initial synthetic entry count for cold functions."));
57
58// Assign initial synthetic entry counts to functions.
59static void
61 auto MayHaveIndirectCalls = [](Function &F) {
62 for (auto *U : F.users()) {
63 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
64 return true;
65 }
66 return false;
67 };
68
69 for (Function &F : M) {
70 uint64_t InitialCount = InitialSyntheticCount;
71 if (F.isDeclaration())
72 continue;
73 if (F.hasFnAttribute(Attribute::AlwaysInline) ||
74 F.hasFnAttribute(Attribute::InlineHint)) {
75 // Use a higher value for inline functions to account for the fact that
76 // these are usually beneficial to inline.
77 InitialCount = InlineSyntheticCount;
78 } else if (F.hasLocalLinkage() && !MayHaveIndirectCalls(F)) {
79 // Local functions without inline hints get counts only through
80 // propagation.
81 InitialCount = 0;
82 } else if (F.hasFnAttribute(Attribute::Cold) ||
83 F.hasFnAttribute(Attribute::NoInline)) {
84 // Use a lower value for noinline and cold functions.
85 InitialCount = ColdSyntheticCount;
86 }
87 SetCount(&F, InitialCount);
88 }
89}
90
96 // Set initial entry counts.
98 M, [&](Function *F, uint64_t Count) { Counts[F] = Scaled64(Count, 0); });
99
100 // Edge includes information about the source. Hence ignore the first
101 // parameter.
102 auto GetCallSiteProfCount = [&](const CallGraphNode *,
103 const CallGraphNode::CallRecord &Edge) {
104 std::optional<Scaled64> Res;
105 if (!Edge.first)
106 return Res;
107 CallBase &CB = *cast<CallBase>(*Edge.first);
108 Function *Caller = CB.getCaller();
109 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller);
110
111 // Now compute the callsite count from relative frequency and
112 // entry count:
113 BasicBlock *CSBB = CB.getParent();
114 Scaled64 EntryFreq(BFI.getEntryFreq().getFrequency(), 0);
115 Scaled64 BBCount(BFI.getBlockFreq(CSBB).getFrequency(), 0);
116 BBCount /= EntryFreq;
117 BBCount *= Counts[Caller];
118 return std::optional<Scaled64>(BBCount);
119 };
120
121 CallGraph CG(M);
122 // Propgate the entry counts on the callgraph.
124 &CG, GetCallSiteProfCount, [&](const CallGraphNode *N, Scaled64 New) {
125 auto F = N->getFunction();
126 if (!F || F->isDeclaration())
127 return;
128
129 Counts[F] += New;
130 });
131
132 // Set the counts as metadata.
133 for (auto Entry : Counts) {
134 Entry.first->setEntryCount(ProfileCount(
135 Entry.second.template toInt<uint64_t>(), Function::PCT_Synthetic));
136 }
137
138 return PreservedAnalyses::all();
139}
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
#define F(x, y, z)
Definition: MD5.cpp:55
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
static void initializeCounts(ModuleSummaryIndex &Index)
ScaledNumber< uint64_t > Scaled64
static void initializeCounts(Module &M, function_ref< void(Function *, uint64_t)> SetCount)
static cl::opt< int > ColdSyntheticCount("cold-synthetic-count", cl::Hidden, cl::init(5), cl::desc("Initial synthetic entry count for cold functions."))
Initial synthetic count assigned to cold functions.
static cl::opt< int > InlineSyntheticCount("inline-synthetic-count", cl::Hidden, cl::init(15), cl::desc("Initial synthetic entry count for inline functions."))
Initial synthetic count assigned to inline functions.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Analysis pass which computes BlockFrequencyInfo.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1455
Function * getCaller()
Helper to get the caller (the parent function).
A node in the call graph for a module.
Definition: CallGraph.h:166
std::pair< std::optional< WeakTrackingVH >, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called.
Definition: CallGraph.h:178
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
Class to represent profile counts.
Definition: Function.h:277
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
const BasicBlock * getParent() const
Definition: Instruction.h:150
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM)
static void propagate(const CallGraphType &CG, GetProfCountTy GetProfCount, AddCountTy AddCount)
Propgate synthetic entry counts on a callgraph CG.
An efficient, type-erasing, non-owning reference to a callable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Function::ProfileCount ProfileCount
cl::opt< int > InitialSyntheticCount
#define N