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/Function.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40
41 using namespace llvm;
42 using Scaled64 = ScaledNumber<uint64_t>;
43 using ProfileCount = Function::ProfileCount;
44
45 #define DEBUG_TYPE "synthetic-counts-propagation"
46
47 /// Initial synthetic count assigned to functions.
48 cl::opt<int>
49 InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
50 cl::ZeroOrMore,
51 cl::desc("Initial value of synthetic entry count."));
52
53 /// Initial synthetic count assigned to inline functions.
54 static cl::opt<int> InlineSyntheticCount(
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.
59 static cl::opt<int> ColdSyntheticCount(
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
initializeCounts(Module & M,function_ref<void (Function *,uint64_t)> SetCount)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
run(Module & M,ModuleAnalysisManager & MAM)96 PreservedAnalyses SyntheticCountsPropagation::run(Module &M,
97 ModuleAnalysisManager &MAM) {
98 FunctionAnalysisManager &FAM =
99 MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
100 DenseMap<Function *, Scaled64> Counts;
101 // Set initial entry counts.
102 initializeCounts(
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.
128 SyntheticCountsUtils<const CallGraph *>::propagate(
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 }
145