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 namespace llvm { 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 } // namespace llvm 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 CallBase &CB = *cast<CallBase>(*Edge.first); 114 Function *Caller = CB.getCaller(); 115 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller); 116 117 // Now compute the callsite count from relative frequency and 118 // entry count: 119 BasicBlock *CSBB = CB.getParent(); 120 Scaled64 EntryFreq(BFI.getEntryFreq(), 0); 121 Scaled64 BBCount(BFI.getBlockFreq(CSBB).getFrequency(), 0); 122 BBCount /= EntryFreq; 123 BBCount *= Counts[Caller]; 124 return Optional<Scaled64>(BBCount); 125 }; 126 127 CallGraph CG(M); 128 // Propgate the entry counts on the callgraph. 129 SyntheticCountsUtils<const CallGraph *>::propagate( 130 &CG, GetCallSiteProfCount, [&](const CallGraphNode *N, Scaled64 New) { 131 auto F = N->getFunction(); 132 if (!F || F->isDeclaration()) 133 return; 134 135 Counts[F] += New; 136 }); 137 138 // Set the counts as metadata. 139 for (auto Entry : Counts) { 140 Entry.first->setEntryCount(ProfileCount( 141 Entry.second.template toInt<uint64_t>(), Function::PCT_Synthetic)); 142 } 143 144 return PreservedAnalyses::all(); 145 } 146