106f32e7eSjoerg //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file implements the SampleProfileLoader transformation. This pass
1006f32e7eSjoerg // reads a profile file generated by a sampling profiler (e.g. Linux Perf -
1106f32e7eSjoerg // http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
1206f32e7eSjoerg // profile information in the given profile.
1306f32e7eSjoerg //
1406f32e7eSjoerg // This pass generates branch weight annotations on the IR:
1506f32e7eSjoerg //
1606f32e7eSjoerg // - prof: Represents branch weights. This annotation is added to branches
1706f32e7eSjoerg // to indicate the weights of each edge coming out of the branch.
1806f32e7eSjoerg // The weight of each edge is the weight of the target block for
1906f32e7eSjoerg // that edge. The weight of a block B is computed as the maximum
2006f32e7eSjoerg // number of samples found in B.
2106f32e7eSjoerg //
2206f32e7eSjoerg //===----------------------------------------------------------------------===//
2306f32e7eSjoerg
2406f32e7eSjoerg #include "llvm/Transforms/IPO/SampleProfile.h"
2506f32e7eSjoerg #include "llvm/ADT/ArrayRef.h"
2606f32e7eSjoerg #include "llvm/ADT/DenseMap.h"
2706f32e7eSjoerg #include "llvm/ADT/DenseSet.h"
2806f32e7eSjoerg #include "llvm/ADT/None.h"
29*da58b97aSjoerg #include "llvm/ADT/PriorityQueue.h"
30*da58b97aSjoerg #include "llvm/ADT/SCCIterator.h"
3106f32e7eSjoerg #include "llvm/ADT/SmallPtrSet.h"
3206f32e7eSjoerg #include "llvm/ADT/SmallSet.h"
3306f32e7eSjoerg #include "llvm/ADT/SmallVector.h"
34*da58b97aSjoerg #include "llvm/ADT/Statistic.h"
3506f32e7eSjoerg #include "llvm/ADT/StringMap.h"
3606f32e7eSjoerg #include "llvm/ADT/StringRef.h"
3706f32e7eSjoerg #include "llvm/ADT/Twine.h"
3806f32e7eSjoerg #include "llvm/Analysis/AssumptionCache.h"
39*da58b97aSjoerg #include "llvm/Analysis/CallGraph.h"
40*da58b97aSjoerg #include "llvm/Analysis/CallGraphSCCPass.h"
41*da58b97aSjoerg #include "llvm/Analysis/InlineAdvisor.h"
4206f32e7eSjoerg #include "llvm/Analysis/InlineCost.h"
4306f32e7eSjoerg #include "llvm/Analysis/LoopInfo.h"
4406f32e7eSjoerg #include "llvm/Analysis/OptimizationRemarkEmitter.h"
4506f32e7eSjoerg #include "llvm/Analysis/PostDominators.h"
4606f32e7eSjoerg #include "llvm/Analysis/ProfileSummaryInfo.h"
47*da58b97aSjoerg #include "llvm/Analysis/ReplayInlineAdvisor.h"
48*da58b97aSjoerg #include "llvm/Analysis/TargetLibraryInfo.h"
4906f32e7eSjoerg #include "llvm/Analysis/TargetTransformInfo.h"
5006f32e7eSjoerg #include "llvm/IR/BasicBlock.h"
5106f32e7eSjoerg #include "llvm/IR/CFG.h"
5206f32e7eSjoerg #include "llvm/IR/DebugInfoMetadata.h"
5306f32e7eSjoerg #include "llvm/IR/DebugLoc.h"
5406f32e7eSjoerg #include "llvm/IR/DiagnosticInfo.h"
5506f32e7eSjoerg #include "llvm/IR/Dominators.h"
5606f32e7eSjoerg #include "llvm/IR/Function.h"
5706f32e7eSjoerg #include "llvm/IR/GlobalValue.h"
5806f32e7eSjoerg #include "llvm/IR/InstrTypes.h"
5906f32e7eSjoerg #include "llvm/IR/Instruction.h"
6006f32e7eSjoerg #include "llvm/IR/Instructions.h"
6106f32e7eSjoerg #include "llvm/IR/IntrinsicInst.h"
6206f32e7eSjoerg #include "llvm/IR/LLVMContext.h"
6306f32e7eSjoerg #include "llvm/IR/MDBuilder.h"
6406f32e7eSjoerg #include "llvm/IR/Module.h"
6506f32e7eSjoerg #include "llvm/IR/PassManager.h"
6606f32e7eSjoerg #include "llvm/IR/ValueSymbolTable.h"
67*da58b97aSjoerg #include "llvm/InitializePasses.h"
6806f32e7eSjoerg #include "llvm/Pass.h"
6906f32e7eSjoerg #include "llvm/ProfileData/InstrProf.h"
7006f32e7eSjoerg #include "llvm/ProfileData/SampleProf.h"
7106f32e7eSjoerg #include "llvm/ProfileData/SampleProfReader.h"
7206f32e7eSjoerg #include "llvm/Support/Casting.h"
7306f32e7eSjoerg #include "llvm/Support/CommandLine.h"
7406f32e7eSjoerg #include "llvm/Support/Debug.h"
7506f32e7eSjoerg #include "llvm/Support/ErrorHandling.h"
7606f32e7eSjoerg #include "llvm/Support/ErrorOr.h"
7706f32e7eSjoerg #include "llvm/Support/GenericDomTree.h"
7806f32e7eSjoerg #include "llvm/Support/raw_ostream.h"
7906f32e7eSjoerg #include "llvm/Transforms/IPO.h"
80*da58b97aSjoerg #include "llvm/Transforms/IPO/ProfiledCallGraph.h"
81*da58b97aSjoerg #include "llvm/Transforms/IPO/SampleContextTracker.h"
82*da58b97aSjoerg #include "llvm/Transforms/IPO/SampleProfileProbe.h"
8306f32e7eSjoerg #include "llvm/Transforms/Instrumentation.h"
8406f32e7eSjoerg #include "llvm/Transforms/Utils/CallPromotionUtils.h"
8506f32e7eSjoerg #include "llvm/Transforms/Utils/Cloning.h"
86*da58b97aSjoerg #include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"
87*da58b97aSjoerg #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
8806f32e7eSjoerg #include <algorithm>
8906f32e7eSjoerg #include <cassert>
9006f32e7eSjoerg #include <cstdint>
9106f32e7eSjoerg #include <functional>
9206f32e7eSjoerg #include <limits>
9306f32e7eSjoerg #include <map>
9406f32e7eSjoerg #include <memory>
9506f32e7eSjoerg #include <queue>
9606f32e7eSjoerg #include <string>
9706f32e7eSjoerg #include <system_error>
9806f32e7eSjoerg #include <utility>
9906f32e7eSjoerg #include <vector>
10006f32e7eSjoerg
10106f32e7eSjoerg using namespace llvm;
10206f32e7eSjoerg using namespace sampleprof;
103*da58b97aSjoerg using namespace llvm::sampleprofutil;
10406f32e7eSjoerg using ProfileCount = Function::ProfileCount;
10506f32e7eSjoerg #define DEBUG_TYPE "sample-profile"
106*da58b97aSjoerg #define CSINLINE_DEBUG DEBUG_TYPE "-inline"
107*da58b97aSjoerg
108*da58b97aSjoerg STATISTIC(NumCSInlined,
109*da58b97aSjoerg "Number of functions inlined with context sensitive profile");
110*da58b97aSjoerg STATISTIC(NumCSNotInlined,
111*da58b97aSjoerg "Number of functions not inlined with context sensitive profile");
112*da58b97aSjoerg STATISTIC(NumMismatchedProfile,
113*da58b97aSjoerg "Number of functions with CFG mismatched profile");
114*da58b97aSjoerg STATISTIC(NumMatchedProfile, "Number of functions with CFG matched profile");
115*da58b97aSjoerg STATISTIC(NumDuplicatedInlinesite,
116*da58b97aSjoerg "Number of inlined callsites with a partial distribution factor");
117*da58b97aSjoerg
118*da58b97aSjoerg STATISTIC(NumCSInlinedHitMinLimit,
119*da58b97aSjoerg "Number of functions with FDO inline stopped due to min size limit");
120*da58b97aSjoerg STATISTIC(NumCSInlinedHitMaxLimit,
121*da58b97aSjoerg "Number of functions with FDO inline stopped due to max size limit");
122*da58b97aSjoerg STATISTIC(
123*da58b97aSjoerg NumCSInlinedHitGrowthLimit,
124*da58b97aSjoerg "Number of functions with FDO inline stopped due to growth size limit");
12506f32e7eSjoerg
12606f32e7eSjoerg // Command line option to specify the file to read samples from. This is
12706f32e7eSjoerg // mainly used for debugging.
12806f32e7eSjoerg static cl::opt<std::string> SampleProfileFile(
12906f32e7eSjoerg "sample-profile-file", cl::init(""), cl::value_desc("filename"),
13006f32e7eSjoerg cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
13106f32e7eSjoerg
13206f32e7eSjoerg // The named file contains a set of transformations that may have been applied
13306f32e7eSjoerg // to the symbol names between the program from which the sample data was
13406f32e7eSjoerg // collected and the current program's symbols.
13506f32e7eSjoerg static cl::opt<std::string> SampleProfileRemappingFile(
13606f32e7eSjoerg "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"),
13706f32e7eSjoerg cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden);
13806f32e7eSjoerg
13906f32e7eSjoerg static cl::opt<bool> ProfileSampleAccurate(
14006f32e7eSjoerg "profile-sample-accurate", cl::Hidden, cl::init(false),
14106f32e7eSjoerg cl::desc("If the sample profile is accurate, we will mark all un-sampled "
14206f32e7eSjoerg "callsite and function as having 0 samples. Otherwise, treat "
14306f32e7eSjoerg "un-sampled callsites and functions conservatively as unknown. "));
14406f32e7eSjoerg
14506f32e7eSjoerg static cl::opt<bool> ProfileAccurateForSymsInList(
14606f32e7eSjoerg "profile-accurate-for-symsinlist", cl::Hidden, cl::ZeroOrMore,
14706f32e7eSjoerg cl::init(true),
14806f32e7eSjoerg cl::desc("For symbols in profile symbol list, regard their profiles to "
14906f32e7eSjoerg "be accurate. It may be overriden by profile-sample-accurate. "));
15006f32e7eSjoerg
151*da58b97aSjoerg static cl::opt<bool> ProfileMergeInlinee(
152*da58b97aSjoerg "sample-profile-merge-inlinee", cl::Hidden, cl::init(true),
153*da58b97aSjoerg cl::desc("Merge past inlinee's profile to outline version if sample "
154*da58b97aSjoerg "profile loader decided not to inline a call site. It will "
155*da58b97aSjoerg "only be enabled when top-down order of profile loading is "
156*da58b97aSjoerg "enabled. "));
157*da58b97aSjoerg
158*da58b97aSjoerg static cl::opt<bool> ProfileTopDownLoad(
159*da58b97aSjoerg "sample-profile-top-down-load", cl::Hidden, cl::init(true),
160*da58b97aSjoerg cl::desc("Do profile annotation and inlining for functions in top-down "
161*da58b97aSjoerg "order of call graph during sample profile loading. It only "
162*da58b97aSjoerg "works for new pass manager. "));
163*da58b97aSjoerg
164*da58b97aSjoerg static cl::opt<bool>
165*da58b97aSjoerg UseProfiledCallGraph("use-profiled-call-graph", cl::init(true), cl::Hidden,
166*da58b97aSjoerg cl::desc("Process functions in a top-down order "
167*da58b97aSjoerg "defined by the profiled call graph when "
168*da58b97aSjoerg "-sample-profile-top-down-load is on."));
169*da58b97aSjoerg
170*da58b97aSjoerg static cl::opt<bool> ProfileSizeInline(
171*da58b97aSjoerg "sample-profile-inline-size", cl::Hidden, cl::init(false),
172*da58b97aSjoerg cl::desc("Inline cold call sites in profile loader if it's beneficial "
173*da58b97aSjoerg "for code size."));
174*da58b97aSjoerg
175*da58b97aSjoerg cl::opt<int> ProfileInlineGrowthLimit(
176*da58b97aSjoerg "sample-profile-inline-growth-limit", cl::Hidden, cl::init(12),
177*da58b97aSjoerg cl::desc("The size growth ratio limit for proirity-based sample profile "
178*da58b97aSjoerg "loader inlining."));
179*da58b97aSjoerg
180*da58b97aSjoerg cl::opt<int> ProfileInlineLimitMin(
181*da58b97aSjoerg "sample-profile-inline-limit-min", cl::Hidden, cl::init(100),
182*da58b97aSjoerg cl::desc("The lower bound of size growth limit for "
183*da58b97aSjoerg "proirity-based sample profile loader inlining."));
184*da58b97aSjoerg
185*da58b97aSjoerg cl::opt<int> ProfileInlineLimitMax(
186*da58b97aSjoerg "sample-profile-inline-limit-max", cl::Hidden, cl::init(10000),
187*da58b97aSjoerg cl::desc("The upper bound of size growth limit for "
188*da58b97aSjoerg "proirity-based sample profile loader inlining."));
189*da58b97aSjoerg
190*da58b97aSjoerg cl::opt<int> SampleHotCallSiteThreshold(
191*da58b97aSjoerg "sample-profile-hot-inline-threshold", cl::Hidden, cl::init(3000),
192*da58b97aSjoerg cl::desc("Hot callsite threshold for proirity-based sample profile loader "
193*da58b97aSjoerg "inlining."));
194*da58b97aSjoerg
195*da58b97aSjoerg cl::opt<int> SampleColdCallSiteThreshold(
196*da58b97aSjoerg "sample-profile-cold-inline-threshold", cl::Hidden, cl::init(45),
197*da58b97aSjoerg cl::desc("Threshold for inlining cold callsites"));
198*da58b97aSjoerg
199*da58b97aSjoerg static cl::opt<int> ProfileICPThreshold(
200*da58b97aSjoerg "sample-profile-icp-threshold", cl::Hidden, cl::init(5),
201*da58b97aSjoerg cl::desc(
202*da58b97aSjoerg "Relative hotness threshold for indirect "
203*da58b97aSjoerg "call promotion in proirity-based sample profile loader inlining."));
204*da58b97aSjoerg
205*da58b97aSjoerg static cl::opt<bool> CallsitePrioritizedInline(
206*da58b97aSjoerg "sample-profile-prioritized-inline", cl::Hidden, cl::ZeroOrMore,
207*da58b97aSjoerg cl::init(false),
208*da58b97aSjoerg cl::desc("Use call site prioritized inlining for sample profile loader."
209*da58b97aSjoerg "Currently only CSSPGO is supported."));
210*da58b97aSjoerg
211*da58b97aSjoerg static cl::opt<std::string> ProfileInlineReplayFile(
212*da58b97aSjoerg "sample-profile-inline-replay", cl::init(""), cl::value_desc("filename"),
213*da58b97aSjoerg cl::desc(
214*da58b97aSjoerg "Optimization remarks file containing inline remarks to be replayed "
215*da58b97aSjoerg "by inlining from sample profile loader."),
216*da58b97aSjoerg cl::Hidden);
217*da58b97aSjoerg
218*da58b97aSjoerg static cl::opt<unsigned>
219*da58b97aSjoerg MaxNumPromotions("sample-profile-icp-max-prom", cl::init(3), cl::Hidden,
220*da58b97aSjoerg cl::ZeroOrMore,
221*da58b97aSjoerg cl::desc("Max number of promotions for a single indirect "
222*da58b97aSjoerg "call callsite in sample profile loader"));
223*da58b97aSjoerg
224*da58b97aSjoerg static cl::opt<bool> OverwriteExistingWeights(
225*da58b97aSjoerg "overwrite-existing-weights", cl::Hidden, cl::init(false),
226*da58b97aSjoerg cl::desc("Ignore existing branch weights on IR and always overwrite."));
227*da58b97aSjoerg
22806f32e7eSjoerg namespace {
22906f32e7eSjoerg
23006f32e7eSjoerg using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>;
23106f32e7eSjoerg using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>;
23206f32e7eSjoerg using Edge = std::pair<const BasicBlock *, const BasicBlock *>;
23306f32e7eSjoerg using EdgeWeightMap = DenseMap<Edge, uint64_t>;
23406f32e7eSjoerg using BlockEdgeMap =
23506f32e7eSjoerg DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>;
23606f32e7eSjoerg
23706f32e7eSjoerg class GUIDToFuncNameMapper {
23806f32e7eSjoerg public:
GUIDToFuncNameMapper(Module & M,SampleProfileReader & Reader,DenseMap<uint64_t,StringRef> & GUIDToFuncNameMap)23906f32e7eSjoerg GUIDToFuncNameMapper(Module &M, SampleProfileReader &Reader,
24006f32e7eSjoerg DenseMap<uint64_t, StringRef> &GUIDToFuncNameMap)
24106f32e7eSjoerg : CurrentReader(Reader), CurrentModule(M),
24206f32e7eSjoerg CurrentGUIDToFuncNameMap(GUIDToFuncNameMap) {
243*da58b97aSjoerg if (!CurrentReader.useMD5())
24406f32e7eSjoerg return;
24506f32e7eSjoerg
24606f32e7eSjoerg for (const auto &F : CurrentModule) {
24706f32e7eSjoerg StringRef OrigName = F.getName();
24806f32e7eSjoerg CurrentGUIDToFuncNameMap.insert(
24906f32e7eSjoerg {Function::getGUID(OrigName), OrigName});
25006f32e7eSjoerg
25106f32e7eSjoerg // Local to global var promotion used by optimization like thinlto
25206f32e7eSjoerg // will rename the var and add suffix like ".llvm.xxx" to the
25306f32e7eSjoerg // original local name. In sample profile, the suffixes of function
25406f32e7eSjoerg // names are all stripped. Since it is possible that the mapper is
25506f32e7eSjoerg // built in post-thin-link phase and var promotion has been done,
25606f32e7eSjoerg // we need to add the substring of function name without the suffix
25706f32e7eSjoerg // into the GUIDToFuncNameMap.
25806f32e7eSjoerg StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
25906f32e7eSjoerg if (CanonName != OrigName)
26006f32e7eSjoerg CurrentGUIDToFuncNameMap.insert(
26106f32e7eSjoerg {Function::getGUID(CanonName), CanonName});
26206f32e7eSjoerg }
26306f32e7eSjoerg
26406f32e7eSjoerg // Update GUIDToFuncNameMap for each function including inlinees.
26506f32e7eSjoerg SetGUIDToFuncNameMapForAll(&CurrentGUIDToFuncNameMap);
26606f32e7eSjoerg }
26706f32e7eSjoerg
~GUIDToFuncNameMapper()26806f32e7eSjoerg ~GUIDToFuncNameMapper() {
269*da58b97aSjoerg if (!CurrentReader.useMD5())
27006f32e7eSjoerg return;
27106f32e7eSjoerg
27206f32e7eSjoerg CurrentGUIDToFuncNameMap.clear();
27306f32e7eSjoerg
27406f32e7eSjoerg // Reset GUIDToFuncNameMap for of each function as they're no
27506f32e7eSjoerg // longer valid at this point.
27606f32e7eSjoerg SetGUIDToFuncNameMapForAll(nullptr);
27706f32e7eSjoerg }
27806f32e7eSjoerg
27906f32e7eSjoerg private:
SetGUIDToFuncNameMapForAll(DenseMap<uint64_t,StringRef> * Map)28006f32e7eSjoerg void SetGUIDToFuncNameMapForAll(DenseMap<uint64_t, StringRef> *Map) {
28106f32e7eSjoerg std::queue<FunctionSamples *> FSToUpdate;
28206f32e7eSjoerg for (auto &IFS : CurrentReader.getProfiles()) {
28306f32e7eSjoerg FSToUpdate.push(&IFS.second);
28406f32e7eSjoerg }
28506f32e7eSjoerg
28606f32e7eSjoerg while (!FSToUpdate.empty()) {
28706f32e7eSjoerg FunctionSamples *FS = FSToUpdate.front();
28806f32e7eSjoerg FSToUpdate.pop();
28906f32e7eSjoerg FS->GUIDToFuncNameMap = Map;
29006f32e7eSjoerg for (const auto &ICS : FS->getCallsiteSamples()) {
29106f32e7eSjoerg const FunctionSamplesMap &FSMap = ICS.second;
29206f32e7eSjoerg for (auto &IFS : FSMap) {
29306f32e7eSjoerg FunctionSamples &FS = const_cast<FunctionSamples &>(IFS.second);
29406f32e7eSjoerg FSToUpdate.push(&FS);
29506f32e7eSjoerg }
29606f32e7eSjoerg }
29706f32e7eSjoerg }
29806f32e7eSjoerg }
29906f32e7eSjoerg
30006f32e7eSjoerg SampleProfileReader &CurrentReader;
30106f32e7eSjoerg Module &CurrentModule;
30206f32e7eSjoerg DenseMap<uint64_t, StringRef> &CurrentGUIDToFuncNameMap;
30306f32e7eSjoerg };
30406f32e7eSjoerg
305*da58b97aSjoerg // Inline candidate used by iterative callsite prioritized inliner
306*da58b97aSjoerg struct InlineCandidate {
307*da58b97aSjoerg CallBase *CallInstr;
308*da58b97aSjoerg const FunctionSamples *CalleeSamples;
309*da58b97aSjoerg // Prorated callsite count, which will be used to guide inlining. For example,
310*da58b97aSjoerg // if a callsite is duplicated in LTO prelink, then in LTO postlink the two
311*da58b97aSjoerg // copies will get their own distribution factors and their prorated counts
312*da58b97aSjoerg // will be used to decide if they should be inlined independently.
313*da58b97aSjoerg uint64_t CallsiteCount;
314*da58b97aSjoerg // Call site distribution factor to prorate the profile samples for a
315*da58b97aSjoerg // duplicated callsite. Default value is 1.0.
316*da58b97aSjoerg float CallsiteDistribution;
317*da58b97aSjoerg };
318*da58b97aSjoerg
319*da58b97aSjoerg // Inline candidate comparer using call site weight
320*da58b97aSjoerg struct CandidateComparer {
operator ()__anon048d08790111::CandidateComparer321*da58b97aSjoerg bool operator()(const InlineCandidate &LHS, const InlineCandidate &RHS) {
322*da58b97aSjoerg if (LHS.CallsiteCount != RHS.CallsiteCount)
323*da58b97aSjoerg return LHS.CallsiteCount < RHS.CallsiteCount;
324*da58b97aSjoerg
325*da58b97aSjoerg const FunctionSamples *LCS = LHS.CalleeSamples;
326*da58b97aSjoerg const FunctionSamples *RCS = RHS.CalleeSamples;
327*da58b97aSjoerg assert(LCS && RCS && "Expect non-null FunctionSamples");
328*da58b97aSjoerg
329*da58b97aSjoerg // Tie breaker using number of samples try to favor smaller functions first
330*da58b97aSjoerg if (LCS->getBodySamples().size() != RCS->getBodySamples().size())
331*da58b97aSjoerg return LCS->getBodySamples().size() > RCS->getBodySamples().size();
332*da58b97aSjoerg
333*da58b97aSjoerg // Tie breaker using GUID so we have stable/deterministic inlining order
334*da58b97aSjoerg return LCS->getGUID(LCS->getName()) < RCS->getGUID(RCS->getName());
335*da58b97aSjoerg }
336*da58b97aSjoerg };
337*da58b97aSjoerg
338*da58b97aSjoerg using CandidateQueue =
339*da58b97aSjoerg PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,
340*da58b97aSjoerg CandidateComparer>;
341*da58b97aSjoerg
34206f32e7eSjoerg /// Sample profile pass.
34306f32e7eSjoerg ///
34406f32e7eSjoerg /// This pass reads profile data from the file specified by
34506f32e7eSjoerg /// -sample-profile-file and annotates every affected function with the
34606f32e7eSjoerg /// profile information found in that file.
347*da58b97aSjoerg class SampleProfileLoader final
348*da58b97aSjoerg : public SampleProfileLoaderBaseImpl<BasicBlock> {
34906f32e7eSjoerg public:
SampleProfileLoader(StringRef Name,StringRef RemapName,ThinOrFullLTOPhase LTOPhase,std::function<AssumptionCache & (Function &)> GetAssumptionCache,std::function<TargetTransformInfo & (Function &)> GetTargetTransformInfo,std::function<const TargetLibraryInfo & (Function &)> GetTLI)35006f32e7eSjoerg SampleProfileLoader(
351*da58b97aSjoerg StringRef Name, StringRef RemapName, ThinOrFullLTOPhase LTOPhase,
35206f32e7eSjoerg std::function<AssumptionCache &(Function &)> GetAssumptionCache,
353*da58b97aSjoerg std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo,
354*da58b97aSjoerg std::function<const TargetLibraryInfo &(Function &)> GetTLI)
355*da58b97aSjoerg : SampleProfileLoaderBaseImpl(std::string(Name)),
356*da58b97aSjoerg GetAC(std::move(GetAssumptionCache)),
357*da58b97aSjoerg GetTTI(std::move(GetTargetTransformInfo)), GetTLI(std::move(GetTLI)),
358*da58b97aSjoerg RemappingFilename(std::string(RemapName)), LTOPhase(LTOPhase) {}
35906f32e7eSjoerg
360*da58b97aSjoerg bool doInitialization(Module &M, FunctionAnalysisManager *FAM = nullptr);
36106f32e7eSjoerg bool runOnModule(Module &M, ModuleAnalysisManager *AM,
362*da58b97aSjoerg ProfileSummaryInfo *_PSI, CallGraph *CG);
36306f32e7eSjoerg
36406f32e7eSjoerg protected:
36506f32e7eSjoerg bool runOnFunction(Function &F, ModuleAnalysisManager *AM);
36606f32e7eSjoerg bool emitAnnotations(Function &F);
367*da58b97aSjoerg ErrorOr<uint64_t> getInstWeight(const Instruction &I) override;
368*da58b97aSjoerg ErrorOr<uint64_t> getProbeWeight(const Instruction &I);
369*da58b97aSjoerg const FunctionSamples *findCalleeFunctionSamples(const CallBase &I) const;
370*da58b97aSjoerg const FunctionSamples *
371*da58b97aSjoerg findFunctionSamples(const Instruction &I) const override;
37206f32e7eSjoerg std::vector<const FunctionSamples *>
37306f32e7eSjoerg findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
374*da58b97aSjoerg void findExternalInlineCandidate(const FunctionSamples *Samples,
375*da58b97aSjoerg DenseSet<GlobalValue::GUID> &InlinedGUIDs,
376*da58b97aSjoerg const StringMap<Function *> &SymbolMap,
377*da58b97aSjoerg uint64_t Threshold);
378*da58b97aSjoerg // Attempt to promote indirect call and also inline the promoted call
379*da58b97aSjoerg bool tryPromoteAndInlineCandidate(
380*da58b97aSjoerg Function &F, InlineCandidate &Candidate, uint64_t SumOrigin,
381*da58b97aSjoerg uint64_t &Sum, SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
38206f32e7eSjoerg bool inlineHotFunctions(Function &F,
38306f32e7eSjoerg DenseSet<GlobalValue::GUID> &InlinedGUIDs);
384*da58b97aSjoerg InlineCost shouldInlineCandidate(InlineCandidate &Candidate);
385*da58b97aSjoerg bool getInlineCandidate(InlineCandidate *NewCandidate, CallBase *CB);
386*da58b97aSjoerg bool
387*da58b97aSjoerg tryInlineCandidate(InlineCandidate &Candidate,
388*da58b97aSjoerg SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
389*da58b97aSjoerg bool
390*da58b97aSjoerg inlineHotFunctionsWithPriority(Function &F,
391*da58b97aSjoerg DenseSet<GlobalValue::GUID> &InlinedGUIDs);
392*da58b97aSjoerg // Inline cold/small functions in addition to hot ones
393*da58b97aSjoerg bool shouldInlineColdCallee(CallBase &CallInst);
394*da58b97aSjoerg void emitOptimizationRemarksForInlineCandidates(
395*da58b97aSjoerg const SmallVectorImpl<CallBase *> &Candidates, const Function &F,
396*da58b97aSjoerg bool Hot);
397*da58b97aSjoerg std::vector<Function *> buildFunctionOrder(Module &M, CallGraph *CG);
398*da58b97aSjoerg std::unique_ptr<ProfiledCallGraph> buildProfiledCallGraph(CallGraph &CG);
399*da58b97aSjoerg void generateMDProfMetadata(Function &F);
40006f32e7eSjoerg
40106f32e7eSjoerg /// Map from function name to Function *. Used to find the function from
40206f32e7eSjoerg /// the function name. If the function name contains suffix, additional
40306f32e7eSjoerg /// entry is added to map from the stripped name to the function if there
40406f32e7eSjoerg /// is one-to-one mapping.
40506f32e7eSjoerg StringMap<Function *> SymbolMap;
40606f32e7eSjoerg
40706f32e7eSjoerg std::function<AssumptionCache &(Function &)> GetAC;
40806f32e7eSjoerg std::function<TargetTransformInfo &(Function &)> GetTTI;
409*da58b97aSjoerg std::function<const TargetLibraryInfo &(Function &)> GetTLI;
41006f32e7eSjoerg
411*da58b97aSjoerg /// Profile tracker for different context.
412*da58b97aSjoerg std::unique_ptr<SampleContextTracker> ContextTracker;
41306f32e7eSjoerg
41406f32e7eSjoerg /// Name of the profile remapping file to load.
41506f32e7eSjoerg std::string RemappingFilename;
41606f32e7eSjoerg
41706f32e7eSjoerg /// Flag indicating whether the profile input loaded successfully.
41806f32e7eSjoerg bool ProfileIsValid = false;
41906f32e7eSjoerg
420*da58b97aSjoerg /// Flag indicating whether input profile is context-sensitive
421*da58b97aSjoerg bool ProfileIsCS = false;
42206f32e7eSjoerg
423*da58b97aSjoerg /// Flag indicating which LTO/ThinLTO phase the pass is invoked in.
424*da58b97aSjoerg ///
425*da58b97aSjoerg /// We need to know the LTO phase because for example in ThinLTOPrelink
426*da58b97aSjoerg /// phase, in annotation, we should not promote indirect calls. Instead,
427*da58b97aSjoerg /// we will mark GUIDs that needs to be annotated to the function.
428*da58b97aSjoerg ThinOrFullLTOPhase LTOPhase;
42906f32e7eSjoerg
43006f32e7eSjoerg /// Profle Symbol list tells whether a function name appears in the binary
43106f32e7eSjoerg /// used to generate the current profile.
43206f32e7eSjoerg std::unique_ptr<ProfileSymbolList> PSL;
43306f32e7eSjoerg
43406f32e7eSjoerg /// Total number of samples collected in this profile.
43506f32e7eSjoerg ///
43606f32e7eSjoerg /// This is the sum of all the samples collected in all the functions executed
43706f32e7eSjoerg /// at runtime.
43806f32e7eSjoerg uint64_t TotalCollectedSamples = 0;
43906f32e7eSjoerg
44006f32e7eSjoerg // Information recorded when we declined to inline a call site
44106f32e7eSjoerg // because we have determined it is too cold is accumulated for
44206f32e7eSjoerg // each callee function. Initially this is just the entry count.
44306f32e7eSjoerg struct NotInlinedProfileInfo {
44406f32e7eSjoerg uint64_t entryCount;
44506f32e7eSjoerg };
44606f32e7eSjoerg DenseMap<Function *, NotInlinedProfileInfo> notInlinedCallInfo;
44706f32e7eSjoerg
44806f32e7eSjoerg // GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
44906f32e7eSjoerg // all the function symbols defined or declared in current module.
45006f32e7eSjoerg DenseMap<uint64_t, StringRef> GUIDToFuncNameMap;
45106f32e7eSjoerg
45206f32e7eSjoerg // All the Names used in FunctionSamples including outline function
45306f32e7eSjoerg // names, inline instance names and call target names.
45406f32e7eSjoerg StringSet<> NamesInProfile;
45506f32e7eSjoerg
45606f32e7eSjoerg // For symbol in profile symbol list, whether to regard their profiles
45706f32e7eSjoerg // to be accurate. It is mainly decided by existance of profile symbol
45806f32e7eSjoerg // list and -profile-accurate-for-symsinlist flag, but it can be
45906f32e7eSjoerg // overriden by -profile-sample-accurate or profile-sample-accurate
46006f32e7eSjoerg // attribute.
46106f32e7eSjoerg bool ProfAccForSymsInList;
462*da58b97aSjoerg
463*da58b97aSjoerg // External inline advisor used to replay inline decision from remarks.
464*da58b97aSjoerg std::unique_ptr<ReplayInlineAdvisor> ExternalInlineAdvisor;
465*da58b97aSjoerg
466*da58b97aSjoerg // A pseudo probe helper to correlate the imported sample counts.
467*da58b97aSjoerg std::unique_ptr<PseudoProbeManager> ProbeManager;
46806f32e7eSjoerg };
46906f32e7eSjoerg
47006f32e7eSjoerg class SampleProfileLoaderLegacyPass : public ModulePass {
47106f32e7eSjoerg public:
47206f32e7eSjoerg // Class identification, replacement for typeinfo
47306f32e7eSjoerg static char ID;
47406f32e7eSjoerg
SampleProfileLoaderLegacyPass(StringRef Name=SampleProfileFile,ThinOrFullLTOPhase LTOPhase=ThinOrFullLTOPhase::None)475*da58b97aSjoerg SampleProfileLoaderLegacyPass(
476*da58b97aSjoerg StringRef Name = SampleProfileFile,
477*da58b97aSjoerg ThinOrFullLTOPhase LTOPhase = ThinOrFullLTOPhase::None)
478*da58b97aSjoerg : ModulePass(ID), SampleLoader(
479*da58b97aSjoerg Name, SampleProfileRemappingFile, LTOPhase,
48006f32e7eSjoerg [&](Function &F) -> AssumptionCache & {
48106f32e7eSjoerg return ACT->getAssumptionCache(F);
48206f32e7eSjoerg },
__anon048d08790302(Function &F) 48306f32e7eSjoerg [&](Function &F) -> TargetTransformInfo & {
48406f32e7eSjoerg return TTIWP->getTTI(F);
485*da58b97aSjoerg },
__anon048d08790402(Function &F) 486*da58b97aSjoerg [&](Function &F) -> TargetLibraryInfo & {
487*da58b97aSjoerg return TLIWP->getTLI(F);
48806f32e7eSjoerg }) {
48906f32e7eSjoerg initializeSampleProfileLoaderLegacyPassPass(
49006f32e7eSjoerg *PassRegistry::getPassRegistry());
49106f32e7eSjoerg }
49206f32e7eSjoerg
dump()49306f32e7eSjoerg void dump() { SampleLoader.dump(); }
49406f32e7eSjoerg
doInitialization(Module & M)49506f32e7eSjoerg bool doInitialization(Module &M) override {
49606f32e7eSjoerg return SampleLoader.doInitialization(M);
49706f32e7eSjoerg }
49806f32e7eSjoerg
getPassName() const49906f32e7eSjoerg StringRef getPassName() const override { return "Sample profile pass"; }
50006f32e7eSjoerg bool runOnModule(Module &M) override;
50106f32e7eSjoerg
getAnalysisUsage(AnalysisUsage & AU) const50206f32e7eSjoerg void getAnalysisUsage(AnalysisUsage &AU) const override {
50306f32e7eSjoerg AU.addRequired<AssumptionCacheTracker>();
50406f32e7eSjoerg AU.addRequired<TargetTransformInfoWrapperPass>();
505*da58b97aSjoerg AU.addRequired<TargetLibraryInfoWrapperPass>();
50606f32e7eSjoerg AU.addRequired<ProfileSummaryInfoWrapperPass>();
50706f32e7eSjoerg }
50806f32e7eSjoerg
50906f32e7eSjoerg private:
51006f32e7eSjoerg SampleProfileLoader SampleLoader;
51106f32e7eSjoerg AssumptionCacheTracker *ACT = nullptr;
51206f32e7eSjoerg TargetTransformInfoWrapperPass *TTIWP = nullptr;
513*da58b97aSjoerg TargetLibraryInfoWrapperPass *TLIWP = nullptr;
51406f32e7eSjoerg };
51506f32e7eSjoerg
51606f32e7eSjoerg } // end anonymous namespace
51706f32e7eSjoerg
getInstWeight(const Instruction & Inst)51806f32e7eSjoerg ErrorOr<uint64_t> SampleProfileLoader::getInstWeight(const Instruction &Inst) {
519*da58b97aSjoerg if (FunctionSamples::ProfileIsProbeBased)
520*da58b97aSjoerg return getProbeWeight(Inst);
521*da58b97aSjoerg
52206f32e7eSjoerg const DebugLoc &DLoc = Inst.getDebugLoc();
52306f32e7eSjoerg if (!DLoc)
52406f32e7eSjoerg return std::error_code();
52506f32e7eSjoerg
52606f32e7eSjoerg // Ignore all intrinsics, phinodes and branch instructions.
527*da58b97aSjoerg // Branch and phinodes instruction usually contains debug info from sources
528*da58b97aSjoerg // outside of the residing basic block, thus we ignore them during annotation.
52906f32e7eSjoerg if (isa<BranchInst>(Inst) || isa<IntrinsicInst>(Inst) || isa<PHINode>(Inst))
53006f32e7eSjoerg return std::error_code();
53106f32e7eSjoerg
532*da58b97aSjoerg // For non-CS profile, if a direct call/invoke instruction is inlined in
533*da58b97aSjoerg // profile (findCalleeFunctionSamples returns non-empty result), but not
534*da58b97aSjoerg // inlined here, it means that the inlined callsite has no sample, thus the
535*da58b97aSjoerg // call instruction should have 0 count.
536*da58b97aSjoerg // For CS profile, the callsite count of previously inlined callees is
537*da58b97aSjoerg // populated with the entry count of the callees.
538*da58b97aSjoerg if (!ProfileIsCS)
539*da58b97aSjoerg if (const auto *CB = dyn_cast<CallBase>(&Inst))
540*da58b97aSjoerg if (!CB->isIndirectCall() && findCalleeFunctionSamples(*CB))
54106f32e7eSjoerg return 0;
54206f32e7eSjoerg
543*da58b97aSjoerg return getInstWeightImpl(Inst);
544*da58b97aSjoerg }
545*da58b97aSjoerg
546*da58b97aSjoerg // Here use error_code to represent: 1) The dangling probe. 2) Ignore the weight
547*da58b97aSjoerg // of non-probe instruction. So if all instructions of the BB give error_code,
548*da58b97aSjoerg // tell the inference algorithm to infer the BB weight.
getProbeWeight(const Instruction & Inst)549*da58b97aSjoerg ErrorOr<uint64_t> SampleProfileLoader::getProbeWeight(const Instruction &Inst) {
550*da58b97aSjoerg assert(FunctionSamples::ProfileIsProbeBased &&
551*da58b97aSjoerg "Profile is not pseudo probe based");
552*da58b97aSjoerg Optional<PseudoProbe> Probe = extractProbe(Inst);
553*da58b97aSjoerg // Ignore the non-probe instruction. If none of the instruction in the BB is
554*da58b97aSjoerg // probe, we choose to infer the BB's weight.
555*da58b97aSjoerg if (!Probe)
556*da58b97aSjoerg return std::error_code();
557*da58b97aSjoerg
558*da58b97aSjoerg // This is not the dangling probe from the training pass but generated by the
559*da58b97aSjoerg // current compilation. Ignore this since they are logically deleted and
560*da58b97aSjoerg // should not consume any profile samples.
561*da58b97aSjoerg if (Probe->isDangling())
562*da58b97aSjoerg return std::error_code();
563*da58b97aSjoerg
564*da58b97aSjoerg const FunctionSamples *FS = findFunctionSamples(Inst);
565*da58b97aSjoerg // If none of the instruction has FunctionSample, we choose to return zero
566*da58b97aSjoerg // value sample to indicate the BB is cold. This could happen when the
567*da58b97aSjoerg // instruction is from inlinee and no profile data is found.
568*da58b97aSjoerg // FIXME: This should not be affected by the source drift issue as 1) if the
569*da58b97aSjoerg // newly added function is top-level inliner, it won't match the CFG checksum
570*da58b97aSjoerg // in the function profile or 2) if it's the inlinee, the inlinee should have
571*da58b97aSjoerg // a profile, otherwise it wouldn't be inlined. For non-probe based profile,
572*da58b97aSjoerg // we can improve it by adding a switch for profile-sample-block-accurate for
573*da58b97aSjoerg // block level counts in the future.
574*da58b97aSjoerg if (!FS)
575*da58b97aSjoerg return 0;
576*da58b97aSjoerg
577*da58b97aSjoerg // For non-CS profile, If a direct call/invoke instruction is inlined in
578*da58b97aSjoerg // profile (findCalleeFunctionSamples returns non-empty result), but not
579*da58b97aSjoerg // inlined here, it means that the inlined callsite has no sample, thus the
580*da58b97aSjoerg // call instruction should have 0 count.
581*da58b97aSjoerg // For CS profile, the callsite count of previously inlined callees is
582*da58b97aSjoerg // populated with the entry count of the callees.
583*da58b97aSjoerg if (!ProfileIsCS)
584*da58b97aSjoerg if (const auto *CB = dyn_cast<CallBase>(&Inst))
585*da58b97aSjoerg if (!CB->isIndirectCall() && findCalleeFunctionSamples(*CB))
586*da58b97aSjoerg return 0;
587*da58b97aSjoerg
588*da58b97aSjoerg const ErrorOr<uint64_t> &R = FS->findSamplesAt(Probe->Id, 0);
58906f32e7eSjoerg if (R) {
590*da58b97aSjoerg uint64_t Samples = R.get() * Probe->Factor;
591*da58b97aSjoerg bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples);
59206f32e7eSjoerg if (FirstMark) {
59306f32e7eSjoerg ORE->emit([&]() {
59406f32e7eSjoerg OptimizationRemarkAnalysis Remark(DEBUG_TYPE, "AppliedSamples", &Inst);
595*da58b97aSjoerg Remark << "Applied " << ore::NV("NumSamples", Samples);
596*da58b97aSjoerg Remark << " samples from profile (ProbeId=";
597*da58b97aSjoerg Remark << ore::NV("ProbeId", Probe->Id);
598*da58b97aSjoerg Remark << ", Factor=";
599*da58b97aSjoerg Remark << ore::NV("Factor", Probe->Factor);
600*da58b97aSjoerg Remark << ", OriginalSamples=";
601*da58b97aSjoerg Remark << ore::NV("OriginalSamples", R.get());
60206f32e7eSjoerg Remark << ")";
60306f32e7eSjoerg return Remark;
60406f32e7eSjoerg });
60506f32e7eSjoerg }
606*da58b97aSjoerg LLVM_DEBUG(dbgs() << " " << Probe->Id << ":" << Inst
607*da58b97aSjoerg << " - weight: " << R.get() << " - factor: "
608*da58b97aSjoerg << format("%0.2f", Probe->Factor) << ")\n");
609*da58b97aSjoerg return Samples;
61006f32e7eSjoerg }
61106f32e7eSjoerg return R;
61206f32e7eSjoerg }
61306f32e7eSjoerg
61406f32e7eSjoerg /// Get the FunctionSamples for a call instruction.
61506f32e7eSjoerg ///
61606f32e7eSjoerg /// The FunctionSamples of a call/invoke instruction \p Inst is the inlined
61706f32e7eSjoerg /// instance in which that call instruction is calling to. It contains
61806f32e7eSjoerg /// all samples that resides in the inlined instance. We first find the
61906f32e7eSjoerg /// inlined instance in which the call instruction is from, then we
62006f32e7eSjoerg /// traverse its children to find the callsite with the matching
62106f32e7eSjoerg /// location.
62206f32e7eSjoerg ///
62306f32e7eSjoerg /// \param Inst Call/Invoke instruction to query.
62406f32e7eSjoerg ///
62506f32e7eSjoerg /// \returns The FunctionSamples pointer to the inlined instance.
62606f32e7eSjoerg const FunctionSamples *
findCalleeFunctionSamples(const CallBase & Inst) const627*da58b97aSjoerg SampleProfileLoader::findCalleeFunctionSamples(const CallBase &Inst) const {
62806f32e7eSjoerg const DILocation *DIL = Inst.getDebugLoc();
62906f32e7eSjoerg if (!DIL) {
63006f32e7eSjoerg return nullptr;
63106f32e7eSjoerg }
63206f32e7eSjoerg
63306f32e7eSjoerg StringRef CalleeName;
634*da58b97aSjoerg if (Function *Callee = Inst.getCalledFunction())
63506f32e7eSjoerg CalleeName = Callee->getName();
63606f32e7eSjoerg
637*da58b97aSjoerg if (ProfileIsCS)
638*da58b97aSjoerg return ContextTracker->getCalleeContextSamplesFor(Inst, CalleeName);
639*da58b97aSjoerg
64006f32e7eSjoerg const FunctionSamples *FS = findFunctionSamples(Inst);
64106f32e7eSjoerg if (FS == nullptr)
64206f32e7eSjoerg return nullptr;
64306f32e7eSjoerg
644*da58b97aSjoerg return FS->findFunctionSamplesAt(FunctionSamples::getCallSiteIdentifier(DIL),
645*da58b97aSjoerg CalleeName, Reader->getRemapper());
64606f32e7eSjoerg }
64706f32e7eSjoerg
64806f32e7eSjoerg /// Returns a vector of FunctionSamples that are the indirect call targets
64906f32e7eSjoerg /// of \p Inst. The vector is sorted by the total number of samples. Stores
65006f32e7eSjoerg /// the total call count of the indirect call in \p Sum.
65106f32e7eSjoerg std::vector<const FunctionSamples *>
findIndirectCallFunctionSamples(const Instruction & Inst,uint64_t & Sum) const65206f32e7eSjoerg SampleProfileLoader::findIndirectCallFunctionSamples(
65306f32e7eSjoerg const Instruction &Inst, uint64_t &Sum) const {
65406f32e7eSjoerg const DILocation *DIL = Inst.getDebugLoc();
65506f32e7eSjoerg std::vector<const FunctionSamples *> R;
65606f32e7eSjoerg
65706f32e7eSjoerg if (!DIL) {
65806f32e7eSjoerg return R;
65906f32e7eSjoerg }
66006f32e7eSjoerg
661*da58b97aSjoerg auto FSCompare = [](const FunctionSamples *L, const FunctionSamples *R) {
662*da58b97aSjoerg assert(L && R && "Expect non-null FunctionSamples");
663*da58b97aSjoerg if (L->getEntrySamples() != R->getEntrySamples())
664*da58b97aSjoerg return L->getEntrySamples() > R->getEntrySamples();
665*da58b97aSjoerg return FunctionSamples::getGUID(L->getName()) <
666*da58b97aSjoerg FunctionSamples::getGUID(R->getName());
667*da58b97aSjoerg };
668*da58b97aSjoerg
669*da58b97aSjoerg if (ProfileIsCS) {
670*da58b97aSjoerg auto CalleeSamples =
671*da58b97aSjoerg ContextTracker->getIndirectCalleeContextSamplesFor(DIL);
672*da58b97aSjoerg if (CalleeSamples.empty())
673*da58b97aSjoerg return R;
674*da58b97aSjoerg
675*da58b97aSjoerg // For CSSPGO, we only use target context profile's entry count
676*da58b97aSjoerg // as that already includes both inlined callee and non-inlined ones..
677*da58b97aSjoerg Sum = 0;
678*da58b97aSjoerg for (const auto *const FS : CalleeSamples) {
679*da58b97aSjoerg Sum += FS->getEntrySamples();
680*da58b97aSjoerg R.push_back(FS);
681*da58b97aSjoerg }
682*da58b97aSjoerg llvm::sort(R, FSCompare);
683*da58b97aSjoerg return R;
684*da58b97aSjoerg }
685*da58b97aSjoerg
68606f32e7eSjoerg const FunctionSamples *FS = findFunctionSamples(Inst);
68706f32e7eSjoerg if (FS == nullptr)
68806f32e7eSjoerg return R;
68906f32e7eSjoerg
690*da58b97aSjoerg auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL);
691*da58b97aSjoerg auto T = FS->findCallTargetMapAt(CallSite);
69206f32e7eSjoerg Sum = 0;
69306f32e7eSjoerg if (T)
69406f32e7eSjoerg for (const auto &T_C : T.get())
69506f32e7eSjoerg Sum += T_C.second;
696*da58b97aSjoerg if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(CallSite)) {
69706f32e7eSjoerg if (M->empty())
69806f32e7eSjoerg return R;
69906f32e7eSjoerg for (const auto &NameFS : *M) {
70006f32e7eSjoerg Sum += NameFS.second.getEntrySamples();
70106f32e7eSjoerg R.push_back(&NameFS.second);
70206f32e7eSjoerg }
703*da58b97aSjoerg llvm::sort(R, FSCompare);
70406f32e7eSjoerg }
70506f32e7eSjoerg return R;
70606f32e7eSjoerg }
70706f32e7eSjoerg
70806f32e7eSjoerg const FunctionSamples *
findFunctionSamples(const Instruction & Inst) const70906f32e7eSjoerg SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
710*da58b97aSjoerg if (FunctionSamples::ProfileIsProbeBased) {
711*da58b97aSjoerg Optional<PseudoProbe> Probe = extractProbe(Inst);
712*da58b97aSjoerg if (!Probe)
713*da58b97aSjoerg return nullptr;
714*da58b97aSjoerg }
715*da58b97aSjoerg
71606f32e7eSjoerg const DILocation *DIL = Inst.getDebugLoc();
71706f32e7eSjoerg if (!DIL)
71806f32e7eSjoerg return Samples;
71906f32e7eSjoerg
72006f32e7eSjoerg auto it = DILocation2SampleMap.try_emplace(DIL,nullptr);
721*da58b97aSjoerg if (it.second) {
722*da58b97aSjoerg if (ProfileIsCS)
723*da58b97aSjoerg it.first->second = ContextTracker->getContextSamplesFor(DIL);
724*da58b97aSjoerg else
725*da58b97aSjoerg it.first->second =
726*da58b97aSjoerg Samples->findFunctionSamples(DIL, Reader->getRemapper());
727*da58b97aSjoerg }
72806f32e7eSjoerg return it.first->second;
72906f32e7eSjoerg }
73006f32e7eSjoerg
731*da58b97aSjoerg /// Check whether the indirect call promotion history of \p Inst allows
732*da58b97aSjoerg /// the promotion for \p Candidate.
733*da58b97aSjoerg /// If the profile count for the promotion candidate \p Candidate is
734*da58b97aSjoerg /// NOMORE_ICP_MAGICNUM, it means \p Candidate has already been promoted
735*da58b97aSjoerg /// for \p Inst. If we already have at least MaxNumPromotions
736*da58b97aSjoerg /// NOMORE_ICP_MAGICNUM count values in the value profile of \p Inst, we
737*da58b97aSjoerg /// cannot promote for \p Inst anymore.
doesHistoryAllowICP(const Instruction & Inst,StringRef Candidate)738*da58b97aSjoerg static bool doesHistoryAllowICP(const Instruction &Inst, StringRef Candidate) {
739*da58b97aSjoerg uint32_t NumVals = 0;
740*da58b97aSjoerg uint64_t TotalCount = 0;
741*da58b97aSjoerg std::unique_ptr<InstrProfValueData[]> ValueData =
742*da58b97aSjoerg std::make_unique<InstrProfValueData[]>(MaxNumPromotions);
743*da58b97aSjoerg bool Valid =
744*da58b97aSjoerg getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,
745*da58b97aSjoerg ValueData.get(), NumVals, TotalCount, true);
746*da58b97aSjoerg // No valid value profile so no promoted targets have been recorded
747*da58b97aSjoerg // before. Ok to do ICP.
748*da58b97aSjoerg if (!Valid)
749*da58b97aSjoerg return true;
750*da58b97aSjoerg
751*da58b97aSjoerg unsigned NumPromoted = 0;
752*da58b97aSjoerg for (uint32_t I = 0; I < NumVals; I++) {
753*da58b97aSjoerg if (ValueData[I].Count != NOMORE_ICP_MAGICNUM)
754*da58b97aSjoerg continue;
755*da58b97aSjoerg
756*da58b97aSjoerg // If the promotion candidate has NOMORE_ICP_MAGICNUM count in the
757*da58b97aSjoerg // metadata, it means the candidate has been promoted for this
758*da58b97aSjoerg // indirect call.
759*da58b97aSjoerg if (ValueData[I].Value == Function::getGUID(Candidate))
760*da58b97aSjoerg return false;
761*da58b97aSjoerg NumPromoted++;
762*da58b97aSjoerg // If already have MaxNumPromotions promotion, don't do it anymore.
763*da58b97aSjoerg if (NumPromoted == MaxNumPromotions)
76406f32e7eSjoerg return false;
76506f32e7eSjoerg }
76606f32e7eSjoerg return true;
76706f32e7eSjoerg }
768*da58b97aSjoerg
769*da58b97aSjoerg /// Update indirect call target profile metadata for \p Inst.
770*da58b97aSjoerg /// Usually \p Sum is the sum of counts of all the targets for \p Inst.
771*da58b97aSjoerg /// If it is 0, it means updateIDTMetaData is used to mark a
772*da58b97aSjoerg /// certain target to be promoted already. If it is not zero,
773*da58b97aSjoerg /// we expect to use it to update the total count in the value profile.
774*da58b97aSjoerg static void
updateIDTMetaData(Instruction & Inst,const SmallVectorImpl<InstrProfValueData> & CallTargets,uint64_t Sum)775*da58b97aSjoerg updateIDTMetaData(Instruction &Inst,
776*da58b97aSjoerg const SmallVectorImpl<InstrProfValueData> &CallTargets,
777*da58b97aSjoerg uint64_t Sum) {
778*da58b97aSjoerg uint32_t NumVals = 0;
779*da58b97aSjoerg // OldSum is the existing total count in the value profile data.
780*da58b97aSjoerg uint64_t OldSum = 0;
781*da58b97aSjoerg std::unique_ptr<InstrProfValueData[]> ValueData =
782*da58b97aSjoerg std::make_unique<InstrProfValueData[]>(MaxNumPromotions);
783*da58b97aSjoerg bool Valid =
784*da58b97aSjoerg getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,
785*da58b97aSjoerg ValueData.get(), NumVals, OldSum, true);
786*da58b97aSjoerg
787*da58b97aSjoerg DenseMap<uint64_t, uint64_t> ValueCountMap;
788*da58b97aSjoerg if (Sum == 0) {
789*da58b97aSjoerg assert((CallTargets.size() == 1 &&
790*da58b97aSjoerg CallTargets[0].Count == NOMORE_ICP_MAGICNUM) &&
791*da58b97aSjoerg "If sum is 0, assume only one element in CallTargets "
792*da58b97aSjoerg "with count being NOMORE_ICP_MAGICNUM");
793*da58b97aSjoerg // Initialize ValueCountMap with existing value profile data.
794*da58b97aSjoerg if (Valid) {
795*da58b97aSjoerg for (uint32_t I = 0; I < NumVals; I++)
796*da58b97aSjoerg ValueCountMap[ValueData[I].Value] = ValueData[I].Count;
797*da58b97aSjoerg }
798*da58b97aSjoerg auto Pair =
799*da58b97aSjoerg ValueCountMap.try_emplace(CallTargets[0].Value, CallTargets[0].Count);
800*da58b97aSjoerg // If the target already exists in value profile, decrease the total
801*da58b97aSjoerg // count OldSum and reset the target's count to NOMORE_ICP_MAGICNUM.
802*da58b97aSjoerg if (!Pair.second) {
803*da58b97aSjoerg OldSum -= Pair.first->second;
804*da58b97aSjoerg Pair.first->second = NOMORE_ICP_MAGICNUM;
805*da58b97aSjoerg }
806*da58b97aSjoerg Sum = OldSum;
807*da58b97aSjoerg } else {
808*da58b97aSjoerg // Initialize ValueCountMap with existing NOMORE_ICP_MAGICNUM
809*da58b97aSjoerg // counts in the value profile.
810*da58b97aSjoerg if (Valid) {
811*da58b97aSjoerg for (uint32_t I = 0; I < NumVals; I++) {
812*da58b97aSjoerg if (ValueData[I].Count == NOMORE_ICP_MAGICNUM)
813*da58b97aSjoerg ValueCountMap[ValueData[I].Value] = ValueData[I].Count;
814*da58b97aSjoerg }
815*da58b97aSjoerg }
816*da58b97aSjoerg
817*da58b97aSjoerg for (const auto &Data : CallTargets) {
818*da58b97aSjoerg auto Pair = ValueCountMap.try_emplace(Data.Value, Data.Count);
819*da58b97aSjoerg if (Pair.second)
820*da58b97aSjoerg continue;
821*da58b97aSjoerg // The target represented by Data.Value has already been promoted.
822*da58b97aSjoerg // Keep the count as NOMORE_ICP_MAGICNUM in the profile and decrease
823*da58b97aSjoerg // Sum by Data.Count.
824*da58b97aSjoerg assert(Sum >= Data.Count && "Sum should never be less than Data.Count");
825*da58b97aSjoerg Sum -= Data.Count;
826*da58b97aSjoerg }
827*da58b97aSjoerg }
828*da58b97aSjoerg
829*da58b97aSjoerg SmallVector<InstrProfValueData, 8> NewCallTargets;
830*da58b97aSjoerg for (const auto &ValueCount : ValueCountMap) {
831*da58b97aSjoerg NewCallTargets.emplace_back(
832*da58b97aSjoerg InstrProfValueData{ValueCount.first, ValueCount.second});
833*da58b97aSjoerg }
834*da58b97aSjoerg
835*da58b97aSjoerg llvm::sort(NewCallTargets,
836*da58b97aSjoerg [](const InstrProfValueData &L, const InstrProfValueData &R) {
837*da58b97aSjoerg if (L.Count != R.Count)
838*da58b97aSjoerg return L.Count > R.Count;
839*da58b97aSjoerg return L.Value > R.Value;
840*da58b97aSjoerg });
841*da58b97aSjoerg
842*da58b97aSjoerg uint32_t MaxMDCount =
843*da58b97aSjoerg std::min(NewCallTargets.size(), static_cast<size_t>(MaxNumPromotions));
844*da58b97aSjoerg annotateValueSite(*Inst.getParent()->getParent()->getParent(), Inst,
845*da58b97aSjoerg NewCallTargets, Sum, IPVK_IndirectCallTarget, MaxMDCount);
846*da58b97aSjoerg }
847*da58b97aSjoerg
848*da58b97aSjoerg /// Attempt to promote indirect call and also inline the promoted call.
849*da58b97aSjoerg ///
850*da58b97aSjoerg /// \param F Caller function.
851*da58b97aSjoerg /// \param Candidate ICP and inline candidate.
852*da58b97aSjoerg /// \param SumOrigin Original sum of target counts for indirect call before
853*da58b97aSjoerg /// promoting given candidate.
854*da58b97aSjoerg /// \param Sum Prorated sum of remaining target counts for indirect call
855*da58b97aSjoerg /// after promoting given candidate.
856*da58b97aSjoerg /// \param InlinedCallSite Output vector for new call sites exposed after
857*da58b97aSjoerg /// inlining.
tryPromoteAndInlineCandidate(Function & F,InlineCandidate & Candidate,uint64_t SumOrigin,uint64_t & Sum,SmallVector<CallBase *,8> * InlinedCallSite)858*da58b97aSjoerg bool SampleProfileLoader::tryPromoteAndInlineCandidate(
859*da58b97aSjoerg Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, uint64_t &Sum,
860*da58b97aSjoerg SmallVector<CallBase *, 8> *InlinedCallSite) {
861*da58b97aSjoerg auto CalleeFunctionName = Candidate.CalleeSamples->getFuncName();
862*da58b97aSjoerg auto R = SymbolMap.find(CalleeFunctionName);
863*da58b97aSjoerg if (R == SymbolMap.end() || !R->getValue())
86406f32e7eSjoerg return false;
865*da58b97aSjoerg
866*da58b97aSjoerg auto &CI = *Candidate.CallInstr;
867*da58b97aSjoerg if (!doesHistoryAllowICP(CI, R->getValue()->getName()))
868*da58b97aSjoerg return false;
869*da58b97aSjoerg
870*da58b97aSjoerg const char *Reason = "Callee function not available";
871*da58b97aSjoerg // R->getValue() != &F is to prevent promoting a recursive call.
872*da58b97aSjoerg // If it is a recursive call, we do not inline it as it could bloat
873*da58b97aSjoerg // the code exponentially. There is way to better handle this, e.g.
874*da58b97aSjoerg // clone the caller first, and inline the cloned caller if it is
875*da58b97aSjoerg // recursive. As llvm does not inline recursive calls, we will
876*da58b97aSjoerg // simply ignore it instead of handling it explicitly.
877*da58b97aSjoerg if (!R->getValue()->isDeclaration() && R->getValue()->getSubprogram() &&
878*da58b97aSjoerg R->getValue()->hasFnAttribute("use-sample-profile") &&
879*da58b97aSjoerg R->getValue() != &F && isLegalToPromote(CI, R->getValue(), &Reason)) {
880*da58b97aSjoerg // For promoted target, set its value with NOMORE_ICP_MAGICNUM count
881*da58b97aSjoerg // in the value profile metadata so the target won't be promoted again.
882*da58b97aSjoerg SmallVector<InstrProfValueData, 1> SortedCallTargets = {InstrProfValueData{
883*da58b97aSjoerg Function::getGUID(R->getValue()->getName()), NOMORE_ICP_MAGICNUM}};
884*da58b97aSjoerg updateIDTMetaData(CI, SortedCallTargets, 0);
885*da58b97aSjoerg
886*da58b97aSjoerg auto *DI = &pgo::promoteIndirectCall(
887*da58b97aSjoerg CI, R->getValue(), Candidate.CallsiteCount, Sum, false, ORE);
888*da58b97aSjoerg if (DI) {
889*da58b97aSjoerg Sum -= Candidate.CallsiteCount;
890*da58b97aSjoerg // Do not prorate the indirect callsite distribution since the original
891*da58b97aSjoerg // distribution will be used to scale down non-promoted profile target
892*da58b97aSjoerg // counts later. By doing this we lose track of the real callsite count
893*da58b97aSjoerg // for the leftover indirect callsite as a trade off for accurate call
894*da58b97aSjoerg // target counts.
895*da58b97aSjoerg // TODO: Ideally we would have two separate factors, one for call site
896*da58b97aSjoerg // counts and one is used to prorate call target counts.
897*da58b97aSjoerg // Do not update the promoted direct callsite distribution at this
898*da58b97aSjoerg // point since the original distribution combined with the callee profile
899*da58b97aSjoerg // will be used to prorate callsites from the callee if inlined. Once not
900*da58b97aSjoerg // inlined, the direct callsite distribution should be prorated so that
901*da58b97aSjoerg // the it will reflect the real callsite counts.
902*da58b97aSjoerg Candidate.CallInstr = DI;
903*da58b97aSjoerg if (isa<CallInst>(DI) || isa<InvokeInst>(DI)) {
904*da58b97aSjoerg bool Inlined = tryInlineCandidate(Candidate, InlinedCallSite);
905*da58b97aSjoerg if (!Inlined) {
906*da58b97aSjoerg // Prorate the direct callsite distribution so that it reflects real
907*da58b97aSjoerg // callsite counts.
908*da58b97aSjoerg setProbeDistributionFactor(
909*da58b97aSjoerg *DI, static_cast<float>(Candidate.CallsiteCount) / SumOrigin);
910*da58b97aSjoerg }
911*da58b97aSjoerg return Inlined;
912*da58b97aSjoerg }
913*da58b97aSjoerg }
914*da58b97aSjoerg } else {
915*da58b97aSjoerg LLVM_DEBUG(dbgs() << "\nFailed to promote indirect call to "
916*da58b97aSjoerg << Candidate.CalleeSamples->getFuncName() << " because "
917*da58b97aSjoerg << Reason << "\n");
918*da58b97aSjoerg }
919*da58b97aSjoerg return false;
920*da58b97aSjoerg }
921*da58b97aSjoerg
shouldInlineColdCallee(CallBase & CallInst)922*da58b97aSjoerg bool SampleProfileLoader::shouldInlineColdCallee(CallBase &CallInst) {
923*da58b97aSjoerg if (!ProfileSizeInline)
924*da58b97aSjoerg return false;
925*da58b97aSjoerg
926*da58b97aSjoerg Function *Callee = CallInst.getCalledFunction();
927*da58b97aSjoerg if (Callee == nullptr)
928*da58b97aSjoerg return false;
929*da58b97aSjoerg
930*da58b97aSjoerg InlineCost Cost = getInlineCost(CallInst, getInlineParams(), GetTTI(*Callee),
931*da58b97aSjoerg GetAC, GetTLI);
932*da58b97aSjoerg
933*da58b97aSjoerg if (Cost.isNever())
934*da58b97aSjoerg return false;
935*da58b97aSjoerg
936*da58b97aSjoerg if (Cost.isAlways())
937*da58b97aSjoerg return true;
938*da58b97aSjoerg
939*da58b97aSjoerg return Cost.getCost() <= SampleColdCallSiteThreshold;
940*da58b97aSjoerg }
941*da58b97aSjoerg
emitOptimizationRemarksForInlineCandidates(const SmallVectorImpl<CallBase * > & Candidates,const Function & F,bool Hot)942*da58b97aSjoerg void SampleProfileLoader::emitOptimizationRemarksForInlineCandidates(
943*da58b97aSjoerg const SmallVectorImpl<CallBase *> &Candidates, const Function &F,
944*da58b97aSjoerg bool Hot) {
945*da58b97aSjoerg for (auto I : Candidates) {
946*da58b97aSjoerg Function *CalledFunction = I->getCalledFunction();
947*da58b97aSjoerg if (CalledFunction) {
948*da58b97aSjoerg ORE->emit(OptimizationRemarkAnalysis(CSINLINE_DEBUG, "InlineAttempt",
949*da58b97aSjoerg I->getDebugLoc(), I->getParent())
950*da58b97aSjoerg << "previous inlining reattempted for "
951*da58b97aSjoerg << (Hot ? "hotness: '" : "size: '")
952*da58b97aSjoerg << ore::NV("Callee", CalledFunction) << "' into '"
953*da58b97aSjoerg << ore::NV("Caller", &F) << "'");
954*da58b97aSjoerg }
955*da58b97aSjoerg }
956*da58b97aSjoerg }
957*da58b97aSjoerg
findExternalInlineCandidate(const FunctionSamples * Samples,DenseSet<GlobalValue::GUID> & InlinedGUIDs,const StringMap<Function * > & SymbolMap,uint64_t Threshold)958*da58b97aSjoerg void SampleProfileLoader::findExternalInlineCandidate(
959*da58b97aSjoerg const FunctionSamples *Samples, DenseSet<GlobalValue::GUID> &InlinedGUIDs,
960*da58b97aSjoerg const StringMap<Function *> &SymbolMap, uint64_t Threshold) {
961*da58b97aSjoerg assert(Samples && "expect non-null caller profile");
962*da58b97aSjoerg
963*da58b97aSjoerg // For AutoFDO profile, retrieve candidate profiles by walking over
964*da58b97aSjoerg // the nested inlinee profiles.
965*da58b97aSjoerg if (!ProfileIsCS) {
966*da58b97aSjoerg Samples->findInlinedFunctions(InlinedGUIDs, SymbolMap, Threshold);
967*da58b97aSjoerg return;
968*da58b97aSjoerg }
969*da58b97aSjoerg
970*da58b97aSjoerg ContextTrieNode *Caller =
971*da58b97aSjoerg ContextTracker->getContextFor(Samples->getContext());
972*da58b97aSjoerg std::queue<ContextTrieNode *> CalleeList;
973*da58b97aSjoerg CalleeList.push(Caller);
974*da58b97aSjoerg while (!CalleeList.empty()) {
975*da58b97aSjoerg ContextTrieNode *Node = CalleeList.front();
976*da58b97aSjoerg CalleeList.pop();
977*da58b97aSjoerg FunctionSamples *CalleeSample = Node->getFunctionSamples();
978*da58b97aSjoerg // For CSSPGO profile, retrieve candidate profile by walking over the
979*da58b97aSjoerg // trie built for context profile. Note that also take call targets
980*da58b97aSjoerg // even if callee doesn't have a corresponding context profile.
981*da58b97aSjoerg if (!CalleeSample || CalleeSample->getEntrySamples() < Threshold)
982*da58b97aSjoerg continue;
983*da58b97aSjoerg
984*da58b97aSjoerg StringRef Name = CalleeSample->getFuncName();
985*da58b97aSjoerg Function *Func = SymbolMap.lookup(Name);
986*da58b97aSjoerg // Add to the import list only when it's defined out of module.
987*da58b97aSjoerg if (!Func || Func->isDeclaration())
988*da58b97aSjoerg InlinedGUIDs.insert(FunctionSamples::getGUID(Name));
989*da58b97aSjoerg
990*da58b97aSjoerg // Import hot CallTargets, which may not be available in IR because full
991*da58b97aSjoerg // profile annotation cannot be done until backend compilation in ThinLTO.
992*da58b97aSjoerg for (const auto &BS : CalleeSample->getBodySamples())
993*da58b97aSjoerg for (const auto &TS : BS.second.getCallTargets())
994*da58b97aSjoerg if (TS.getValue() > Threshold) {
995*da58b97aSjoerg StringRef CalleeName = CalleeSample->getFuncName(TS.getKey());
996*da58b97aSjoerg const Function *Callee = SymbolMap.lookup(CalleeName);
997*da58b97aSjoerg if (!Callee || Callee->isDeclaration())
998*da58b97aSjoerg InlinedGUIDs.insert(FunctionSamples::getGUID(CalleeName));
999*da58b97aSjoerg }
1000*da58b97aSjoerg
1001*da58b97aSjoerg // Import hot child context profile associted with callees. Note that this
1002*da58b97aSjoerg // may have some overlap with the call target loop above, but doing this
1003*da58b97aSjoerg // based child context profile again effectively allow us to use the max of
1004*da58b97aSjoerg // entry count and call target count to determine importing.
1005*da58b97aSjoerg for (auto &Child : Node->getAllChildContext()) {
1006*da58b97aSjoerg ContextTrieNode *CalleeNode = &Child.second;
1007*da58b97aSjoerg CalleeList.push(CalleeNode);
1008*da58b97aSjoerg }
1009*da58b97aSjoerg }
101006f32e7eSjoerg }
101106f32e7eSjoerg
101206f32e7eSjoerg /// Iteratively inline hot callsites of a function.
101306f32e7eSjoerg ///
101406f32e7eSjoerg /// Iteratively traverse all callsites of the function \p F, and find if
101506f32e7eSjoerg /// the corresponding inlined instance exists and is hot in profile. If
101606f32e7eSjoerg /// it is hot enough, inline the callsites and adds new callsites of the
101706f32e7eSjoerg /// callee into the caller. If the call is an indirect call, first promote
101806f32e7eSjoerg /// it to direct call. Each indirect call is limited with a single target.
101906f32e7eSjoerg ///
102006f32e7eSjoerg /// \param F function to perform iterative inlining.
102106f32e7eSjoerg /// \param InlinedGUIDs a set to be updated to include all GUIDs that are
102206f32e7eSjoerg /// inlined in the profiled binary.
102306f32e7eSjoerg ///
102406f32e7eSjoerg /// \returns True if there is any inline happened.
inlineHotFunctions(Function & F,DenseSet<GlobalValue::GUID> & InlinedGUIDs)102506f32e7eSjoerg bool SampleProfileLoader::inlineHotFunctions(
102606f32e7eSjoerg Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
1027*da58b97aSjoerg // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
1028*da58b97aSjoerg // Profile symbol list is ignored when profile-sample-accurate is on.
1029*da58b97aSjoerg assert((!ProfAccForSymsInList ||
1030*da58b97aSjoerg (!ProfileSampleAccurate &&
1031*da58b97aSjoerg !F.hasFnAttribute("profile-sample-accurate"))) &&
1032*da58b97aSjoerg "ProfAccForSymsInList should be false when profile-sample-accurate "
1033*da58b97aSjoerg "is enabled");
1034*da58b97aSjoerg
1035*da58b97aSjoerg DenseMap<CallBase *, const FunctionSamples *> LocalNotInlinedCallSites;
1036*da58b97aSjoerg bool Changed = false;
1037*da58b97aSjoerg bool LocalChanged = true;
1038*da58b97aSjoerg while (LocalChanged) {
1039*da58b97aSjoerg LocalChanged = false;
1040*da58b97aSjoerg SmallVector<CallBase *, 10> CIS;
1041*da58b97aSjoerg for (auto &BB : F) {
1042*da58b97aSjoerg bool Hot = false;
1043*da58b97aSjoerg SmallVector<CallBase *, 10> AllCandidates;
1044*da58b97aSjoerg SmallVector<CallBase *, 10> ColdCandidates;
1045*da58b97aSjoerg for (auto &I : BB.getInstList()) {
1046*da58b97aSjoerg const FunctionSamples *FS = nullptr;
1047*da58b97aSjoerg if (auto *CB = dyn_cast<CallBase>(&I)) {
1048*da58b97aSjoerg if (!isa<IntrinsicInst>(I) && (FS = findCalleeFunctionSamples(*CB))) {
1049*da58b97aSjoerg assert((!FunctionSamples::UseMD5 || FS->GUIDToFuncNameMap) &&
1050*da58b97aSjoerg "GUIDToFuncNameMap has to be populated");
1051*da58b97aSjoerg AllCandidates.push_back(CB);
1052*da58b97aSjoerg if (FS->getEntrySamples() > 0 || ProfileIsCS)
1053*da58b97aSjoerg LocalNotInlinedCallSites.try_emplace(CB, FS);
1054*da58b97aSjoerg if (callsiteIsHot(FS, PSI, ProfAccForSymsInList))
1055*da58b97aSjoerg Hot = true;
1056*da58b97aSjoerg else if (shouldInlineColdCallee(*CB))
1057*da58b97aSjoerg ColdCandidates.push_back(CB);
1058*da58b97aSjoerg }
1059*da58b97aSjoerg }
1060*da58b97aSjoerg }
1061*da58b97aSjoerg if (Hot || ExternalInlineAdvisor) {
1062*da58b97aSjoerg CIS.insert(CIS.begin(), AllCandidates.begin(), AllCandidates.end());
1063*da58b97aSjoerg emitOptimizationRemarksForInlineCandidates(AllCandidates, F, true);
1064*da58b97aSjoerg } else {
1065*da58b97aSjoerg CIS.insert(CIS.begin(), ColdCandidates.begin(), ColdCandidates.end());
1066*da58b97aSjoerg emitOptimizationRemarksForInlineCandidates(ColdCandidates, F, false);
1067*da58b97aSjoerg }
1068*da58b97aSjoerg }
1069*da58b97aSjoerg for (CallBase *I : CIS) {
1070*da58b97aSjoerg Function *CalledFunction = I->getCalledFunction();
1071*da58b97aSjoerg InlineCandidate Candidate = {
1072*da58b97aSjoerg I,
1073*da58b97aSjoerg LocalNotInlinedCallSites.count(I) ? LocalNotInlinedCallSites[I]
1074*da58b97aSjoerg : nullptr,
1075*da58b97aSjoerg 0 /* dummy count */, 1.0 /* dummy distribution factor */};
1076*da58b97aSjoerg // Do not inline recursive calls.
1077*da58b97aSjoerg if (CalledFunction == &F)
1078*da58b97aSjoerg continue;
1079*da58b97aSjoerg if (I->isIndirectCall()) {
1080*da58b97aSjoerg uint64_t Sum;
1081*da58b97aSjoerg for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
1082*da58b97aSjoerg uint64_t SumOrigin = Sum;
1083*da58b97aSjoerg if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1084*da58b97aSjoerg findExternalInlineCandidate(FS, InlinedGUIDs, SymbolMap,
1085*da58b97aSjoerg PSI->getOrCompHotCountThreshold());
1086*da58b97aSjoerg continue;
1087*da58b97aSjoerg }
1088*da58b97aSjoerg if (!callsiteIsHot(FS, PSI, ProfAccForSymsInList))
1089*da58b97aSjoerg continue;
1090*da58b97aSjoerg
1091*da58b97aSjoerg Candidate = {I, FS, FS->getEntrySamples(), 1.0};
1092*da58b97aSjoerg if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum)) {
1093*da58b97aSjoerg LocalNotInlinedCallSites.erase(I);
1094*da58b97aSjoerg LocalChanged = true;
1095*da58b97aSjoerg }
1096*da58b97aSjoerg }
1097*da58b97aSjoerg } else if (CalledFunction && CalledFunction->getSubprogram() &&
1098*da58b97aSjoerg !CalledFunction->isDeclaration()) {
1099*da58b97aSjoerg if (tryInlineCandidate(Candidate)) {
1100*da58b97aSjoerg LocalNotInlinedCallSites.erase(I);
1101*da58b97aSjoerg LocalChanged = true;
1102*da58b97aSjoerg }
1103*da58b97aSjoerg } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1104*da58b97aSjoerg findExternalInlineCandidate(findCalleeFunctionSamples(*I), InlinedGUIDs,
1105*da58b97aSjoerg SymbolMap,
1106*da58b97aSjoerg PSI->getOrCompHotCountThreshold());
1107*da58b97aSjoerg }
1108*da58b97aSjoerg }
1109*da58b97aSjoerg Changed |= LocalChanged;
1110*da58b97aSjoerg }
1111*da58b97aSjoerg
1112*da58b97aSjoerg // For CS profile, profile for not inlined context will be merged when
1113*da58b97aSjoerg // base profile is being trieved
1114*da58b97aSjoerg if (ProfileIsCS)
1115*da58b97aSjoerg return Changed;
1116*da58b97aSjoerg
1117*da58b97aSjoerg // Accumulate not inlined callsite information into notInlinedSamples
1118*da58b97aSjoerg for (const auto &Pair : LocalNotInlinedCallSites) {
1119*da58b97aSjoerg CallBase *I = Pair.getFirst();
1120*da58b97aSjoerg Function *Callee = I->getCalledFunction();
1121*da58b97aSjoerg if (!Callee || Callee->isDeclaration())
1122*da58b97aSjoerg continue;
1123*da58b97aSjoerg
1124*da58b97aSjoerg ORE->emit(OptimizationRemarkAnalysis(CSINLINE_DEBUG, "NotInline",
1125*da58b97aSjoerg I->getDebugLoc(), I->getParent())
1126*da58b97aSjoerg << "previous inlining not repeated: '"
1127*da58b97aSjoerg << ore::NV("Callee", Callee) << "' into '"
1128*da58b97aSjoerg << ore::NV("Caller", &F) << "'");
1129*da58b97aSjoerg
1130*da58b97aSjoerg ++NumCSNotInlined;
1131*da58b97aSjoerg const FunctionSamples *FS = Pair.getSecond();
1132*da58b97aSjoerg if (FS->getTotalSamples() == 0 && FS->getEntrySamples() == 0) {
1133*da58b97aSjoerg continue;
1134*da58b97aSjoerg }
1135*da58b97aSjoerg
1136*da58b97aSjoerg if (ProfileMergeInlinee) {
1137*da58b97aSjoerg // A function call can be replicated by optimizations like callsite
1138*da58b97aSjoerg // splitting or jump threading and the replicates end up sharing the
1139*da58b97aSjoerg // sample nested callee profile instead of slicing the original inlinee's
1140*da58b97aSjoerg // profile. We want to do merge exactly once by filtering out callee
1141*da58b97aSjoerg // profiles with a non-zero head sample count.
1142*da58b97aSjoerg if (FS->getHeadSamples() == 0) {
1143*da58b97aSjoerg // Use entry samples as head samples during the merge, as inlinees
1144*da58b97aSjoerg // don't have head samples.
1145*da58b97aSjoerg const_cast<FunctionSamples *>(FS)->addHeadSamples(
1146*da58b97aSjoerg FS->getEntrySamples());
1147*da58b97aSjoerg
1148*da58b97aSjoerg // Note that we have to do the merge right after processing function.
1149*da58b97aSjoerg // This allows OutlineFS's profile to be used for annotation during
1150*da58b97aSjoerg // top-down processing of functions' annotation.
1151*da58b97aSjoerg FunctionSamples *OutlineFS = Reader->getOrCreateSamplesFor(*Callee);
1152*da58b97aSjoerg OutlineFS->merge(*FS);
1153*da58b97aSjoerg }
1154*da58b97aSjoerg } else {
1155*da58b97aSjoerg auto pair =
1156*da58b97aSjoerg notInlinedCallInfo.try_emplace(Callee, NotInlinedProfileInfo{0});
1157*da58b97aSjoerg pair.first->second.entryCount += FS->getEntrySamples();
1158*da58b97aSjoerg }
1159*da58b97aSjoerg }
1160*da58b97aSjoerg return Changed;
1161*da58b97aSjoerg }
1162*da58b97aSjoerg
tryInlineCandidate(InlineCandidate & Candidate,SmallVector<CallBase *,8> * InlinedCallSites)1163*da58b97aSjoerg bool SampleProfileLoader::tryInlineCandidate(
1164*da58b97aSjoerg InlineCandidate &Candidate, SmallVector<CallBase *, 8> *InlinedCallSites) {
1165*da58b97aSjoerg
1166*da58b97aSjoerg CallBase &CB = *Candidate.CallInstr;
1167*da58b97aSjoerg Function *CalledFunction = CB.getCalledFunction();
1168*da58b97aSjoerg assert(CalledFunction && "Expect a callee with definition");
1169*da58b97aSjoerg DebugLoc DLoc = CB.getDebugLoc();
1170*da58b97aSjoerg BasicBlock *BB = CB.getParent();
1171*da58b97aSjoerg
1172*da58b97aSjoerg InlineCost Cost = shouldInlineCandidate(Candidate);
1173*da58b97aSjoerg if (Cost.isNever()) {
1174*da58b97aSjoerg ORE->emit(OptimizationRemarkAnalysis(CSINLINE_DEBUG, "InlineFail", DLoc, BB)
1175*da58b97aSjoerg << "incompatible inlining");
1176*da58b97aSjoerg return false;
1177*da58b97aSjoerg }
1178*da58b97aSjoerg
1179*da58b97aSjoerg if (!Cost)
1180*da58b97aSjoerg return false;
1181*da58b97aSjoerg
1182*da58b97aSjoerg InlineFunctionInfo IFI(nullptr, GetAC);
1183*da58b97aSjoerg IFI.UpdateProfile = false;
1184*da58b97aSjoerg if (InlineFunction(CB, IFI).isSuccess()) {
1185*da58b97aSjoerg // The call to InlineFunction erases I, so we can't pass it here.
1186*da58b97aSjoerg emitInlinedInto(*ORE, DLoc, BB, *CalledFunction, *BB->getParent(), Cost,
1187*da58b97aSjoerg true, CSINLINE_DEBUG);
1188*da58b97aSjoerg
1189*da58b97aSjoerg // Now populate the list of newly exposed call sites.
1190*da58b97aSjoerg if (InlinedCallSites) {
1191*da58b97aSjoerg InlinedCallSites->clear();
1192*da58b97aSjoerg for (auto &I : IFI.InlinedCallSites)
1193*da58b97aSjoerg InlinedCallSites->push_back(I);
1194*da58b97aSjoerg }
1195*da58b97aSjoerg
1196*da58b97aSjoerg if (ProfileIsCS)
1197*da58b97aSjoerg ContextTracker->markContextSamplesInlined(Candidate.CalleeSamples);
1198*da58b97aSjoerg ++NumCSInlined;
1199*da58b97aSjoerg
1200*da58b97aSjoerg // Prorate inlined probes for a duplicated inlining callsite which probably
1201*da58b97aSjoerg // has a distribution less than 100%. Samples for an inlinee should be
1202*da58b97aSjoerg // distributed among the copies of the original callsite based on each
1203*da58b97aSjoerg // callsite's distribution factor for counts accuracy. Note that an inlined
1204*da58b97aSjoerg // probe may come with its own distribution factor if it has been duplicated
1205*da58b97aSjoerg // in the inlinee body. The two factor are multiplied to reflect the
1206*da58b97aSjoerg // aggregation of duplication.
1207*da58b97aSjoerg if (Candidate.CallsiteDistribution < 1) {
1208*da58b97aSjoerg for (auto &I : IFI.InlinedCallSites) {
1209*da58b97aSjoerg if (Optional<PseudoProbe> Probe = extractProbe(*I))
1210*da58b97aSjoerg setProbeDistributionFactor(*I, Probe->Factor *
1211*da58b97aSjoerg Candidate.CallsiteDistribution);
1212*da58b97aSjoerg }
1213*da58b97aSjoerg NumDuplicatedInlinesite++;
1214*da58b97aSjoerg }
1215*da58b97aSjoerg
1216*da58b97aSjoerg return true;
1217*da58b97aSjoerg }
1218*da58b97aSjoerg return false;
1219*da58b97aSjoerg }
1220*da58b97aSjoerg
getInlineCandidate(InlineCandidate * NewCandidate,CallBase * CB)1221*da58b97aSjoerg bool SampleProfileLoader::getInlineCandidate(InlineCandidate *NewCandidate,
1222*da58b97aSjoerg CallBase *CB) {
1223*da58b97aSjoerg assert(CB && "Expect non-null call instruction");
1224*da58b97aSjoerg
1225*da58b97aSjoerg if (isa<IntrinsicInst>(CB))
1226*da58b97aSjoerg return false;
1227*da58b97aSjoerg
1228*da58b97aSjoerg // Find the callee's profile. For indirect call, find hottest target profile.
1229*da58b97aSjoerg const FunctionSamples *CalleeSamples = findCalleeFunctionSamples(*CB);
1230*da58b97aSjoerg if (!CalleeSamples)
1231*da58b97aSjoerg return false;
1232*da58b97aSjoerg
1233*da58b97aSjoerg float Factor = 1.0;
1234*da58b97aSjoerg if (Optional<PseudoProbe> Probe = extractProbe(*CB))
1235*da58b97aSjoerg Factor = Probe->Factor;
1236*da58b97aSjoerg
1237*da58b97aSjoerg uint64_t CallsiteCount = 0;
1238*da58b97aSjoerg ErrorOr<uint64_t> Weight = getBlockWeight(CB->getParent());
1239*da58b97aSjoerg if (Weight)
1240*da58b97aSjoerg CallsiteCount = Weight.get();
1241*da58b97aSjoerg if (CalleeSamples)
1242*da58b97aSjoerg CallsiteCount = std::max(
1243*da58b97aSjoerg CallsiteCount, uint64_t(CalleeSamples->getEntrySamples() * Factor));
1244*da58b97aSjoerg
1245*da58b97aSjoerg *NewCandidate = {CB, CalleeSamples, CallsiteCount, Factor};
1246*da58b97aSjoerg return true;
1247*da58b97aSjoerg }
1248*da58b97aSjoerg
1249*da58b97aSjoerg InlineCost
shouldInlineCandidate(InlineCandidate & Candidate)1250*da58b97aSjoerg SampleProfileLoader::shouldInlineCandidate(InlineCandidate &Candidate) {
1251*da58b97aSjoerg std::unique_ptr<InlineAdvice> Advice = nullptr;
1252*da58b97aSjoerg if (ExternalInlineAdvisor) {
1253*da58b97aSjoerg Advice = ExternalInlineAdvisor->getAdvice(*Candidate.CallInstr);
1254*da58b97aSjoerg if (!Advice->isInliningRecommended()) {
1255*da58b97aSjoerg Advice->recordUnattemptedInlining();
1256*da58b97aSjoerg return InlineCost::getNever("not previously inlined");
1257*da58b97aSjoerg }
1258*da58b97aSjoerg Advice->recordInlining();
1259*da58b97aSjoerg return InlineCost::getAlways("previously inlined");
1260*da58b97aSjoerg }
1261*da58b97aSjoerg
1262*da58b97aSjoerg // Adjust threshold based on call site hotness, only do this for callsite
1263*da58b97aSjoerg // prioritized inliner because otherwise cost-benefit check is done earlier.
1264*da58b97aSjoerg int SampleThreshold = SampleColdCallSiteThreshold;
1265*da58b97aSjoerg if (CallsitePrioritizedInline) {
1266*da58b97aSjoerg if (Candidate.CallsiteCount > PSI->getHotCountThreshold())
1267*da58b97aSjoerg SampleThreshold = SampleHotCallSiteThreshold;
1268*da58b97aSjoerg else if (!ProfileSizeInline)
1269*da58b97aSjoerg return InlineCost::getNever("cold callsite");
1270*da58b97aSjoerg }
1271*da58b97aSjoerg
1272*da58b97aSjoerg Function *Callee = Candidate.CallInstr->getCalledFunction();
1273*da58b97aSjoerg assert(Callee && "Expect a definition for inline candidate of direct call");
1274*da58b97aSjoerg
1275*da58b97aSjoerg InlineParams Params = getInlineParams();
1276*da58b97aSjoerg Params.ComputeFullInlineCost = true;
1277*da58b97aSjoerg // Checks if there is anything in the reachable portion of the callee at
1278*da58b97aSjoerg // this callsite that makes this inlining potentially illegal. Need to
1279*da58b97aSjoerg // set ComputeFullInlineCost, otherwise getInlineCost may return early
1280*da58b97aSjoerg // when cost exceeds threshold without checking all IRs in the callee.
1281*da58b97aSjoerg // The acutal cost does not matter because we only checks isNever() to
1282*da58b97aSjoerg // see if it is legal to inline the callsite.
1283*da58b97aSjoerg InlineCost Cost = getInlineCost(*Candidate.CallInstr, Callee, Params,
1284*da58b97aSjoerg GetTTI(*Callee), GetAC, GetTLI);
1285*da58b97aSjoerg
1286*da58b97aSjoerg // Honor always inline and never inline from call analyzer
1287*da58b97aSjoerg if (Cost.isNever() || Cost.isAlways())
1288*da58b97aSjoerg return Cost;
1289*da58b97aSjoerg
1290*da58b97aSjoerg // For old FDO inliner, we inline the call site as long as cost is not
1291*da58b97aSjoerg // "Never". The cost-benefit check is done earlier.
1292*da58b97aSjoerg if (!CallsitePrioritizedInline) {
1293*da58b97aSjoerg return InlineCost::get(Cost.getCost(), INT_MAX);
1294*da58b97aSjoerg }
1295*da58b97aSjoerg
1296*da58b97aSjoerg // Otherwise only use the cost from call analyzer, but overwite threshold with
1297*da58b97aSjoerg // Sample PGO threshold.
1298*da58b97aSjoerg return InlineCost::get(Cost.getCost(), SampleThreshold);
1299*da58b97aSjoerg }
1300*da58b97aSjoerg
inlineHotFunctionsWithPriority(Function & F,DenseSet<GlobalValue::GUID> & InlinedGUIDs)1301*da58b97aSjoerg bool SampleProfileLoader::inlineHotFunctionsWithPriority(
1302*da58b97aSjoerg Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
1303*da58b97aSjoerg assert(ProfileIsCS && "Prioritiy based inliner only works with CSSPGO now");
130406f32e7eSjoerg
130506f32e7eSjoerg // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
130606f32e7eSjoerg // Profile symbol list is ignored when profile-sample-accurate is on.
130706f32e7eSjoerg assert((!ProfAccForSymsInList ||
130806f32e7eSjoerg (!ProfileSampleAccurate &&
130906f32e7eSjoerg !F.hasFnAttribute("profile-sample-accurate"))) &&
131006f32e7eSjoerg "ProfAccForSymsInList should be false when profile-sample-accurate "
131106f32e7eSjoerg "is enabled");
131206f32e7eSjoerg
1313*da58b97aSjoerg // Populating worklist with initial call sites from root inliner, along
1314*da58b97aSjoerg // with call site weights.
1315*da58b97aSjoerg CandidateQueue CQueue;
1316*da58b97aSjoerg InlineCandidate NewCandidate;
131706f32e7eSjoerg for (auto &BB : F) {
131806f32e7eSjoerg for (auto &I : BB.getInstList()) {
1319*da58b97aSjoerg auto *CB = dyn_cast<CallBase>(&I);
1320*da58b97aSjoerg if (!CB)
1321*da58b97aSjoerg continue;
1322*da58b97aSjoerg if (getInlineCandidate(&NewCandidate, CB))
1323*da58b97aSjoerg CQueue.push(NewCandidate);
132406f32e7eSjoerg }
132506f32e7eSjoerg }
1326*da58b97aSjoerg
1327*da58b97aSjoerg // Cap the size growth from profile guided inlining. This is needed even
1328*da58b97aSjoerg // though cost of each inline candidate already accounts for callee size,
1329*da58b97aSjoerg // because with top-down inlining, we can grow inliner size significantly
1330*da58b97aSjoerg // with large number of smaller inlinees each pass the cost check.
1331*da58b97aSjoerg assert(ProfileInlineLimitMax >= ProfileInlineLimitMin &&
1332*da58b97aSjoerg "Max inline size limit should not be smaller than min inline size "
1333*da58b97aSjoerg "limit.");
1334*da58b97aSjoerg unsigned SizeLimit = F.getInstructionCount() * ProfileInlineGrowthLimit;
1335*da58b97aSjoerg SizeLimit = std::min(SizeLimit, (unsigned)ProfileInlineLimitMax);
1336*da58b97aSjoerg SizeLimit = std::max(SizeLimit, (unsigned)ProfileInlineLimitMin);
1337*da58b97aSjoerg if (ExternalInlineAdvisor)
1338*da58b97aSjoerg SizeLimit = std::numeric_limits<unsigned>::max();
1339*da58b97aSjoerg
1340*da58b97aSjoerg // Perform iterative BFS call site prioritized inlining
1341*da58b97aSjoerg bool Changed = false;
1342*da58b97aSjoerg while (!CQueue.empty() && F.getInstructionCount() < SizeLimit) {
1343*da58b97aSjoerg InlineCandidate Candidate = CQueue.top();
1344*da58b97aSjoerg CQueue.pop();
1345*da58b97aSjoerg CallBase *I = Candidate.CallInstr;
1346*da58b97aSjoerg Function *CalledFunction = I->getCalledFunction();
1347*da58b97aSjoerg
134806f32e7eSjoerg if (CalledFunction == &F)
134906f32e7eSjoerg continue;
1350*da58b97aSjoerg if (I->isIndirectCall()) {
1351*da58b97aSjoerg uint64_t Sum = 0;
1352*da58b97aSjoerg auto CalleeSamples = findIndirectCallFunctionSamples(*I, Sum);
1353*da58b97aSjoerg uint64_t SumOrigin = Sum;
1354*da58b97aSjoerg Sum *= Candidate.CallsiteDistribution;
1355*da58b97aSjoerg for (const auto *FS : CalleeSamples) {
1356*da58b97aSjoerg // TODO: Consider disable pre-lTO ICP for MonoLTO as well
1357*da58b97aSjoerg if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1358*da58b97aSjoerg findExternalInlineCandidate(FS, InlinedGUIDs, SymbolMap,
135906f32e7eSjoerg PSI->getOrCompHotCountThreshold());
136006f32e7eSjoerg continue;
136106f32e7eSjoerg }
1362*da58b97aSjoerg uint64_t EntryCountDistributed =
1363*da58b97aSjoerg FS->getEntrySamples() * Candidate.CallsiteDistribution;
1364*da58b97aSjoerg // In addition to regular inline cost check, we also need to make sure
1365*da58b97aSjoerg // ICP isn't introducing excessive speculative checks even if individual
1366*da58b97aSjoerg // target looks beneficial to promote and inline. That means we should
1367*da58b97aSjoerg // only do ICP when there's a small number dominant targets.
1368*da58b97aSjoerg if (EntryCountDistributed < SumOrigin / ProfileICPThreshold)
1369*da58b97aSjoerg break;
1370*da58b97aSjoerg // TODO: Fix CallAnalyzer to handle all indirect calls.
1371*da58b97aSjoerg // For indirect call, we don't run CallAnalyzer to get InlineCost
1372*da58b97aSjoerg // before actual inlining. This is because we could see two different
1373*da58b97aSjoerg // types from the same definition, which makes CallAnalyzer choke as
1374*da58b97aSjoerg // it's expecting matching parameter type on both caller and callee
1375*da58b97aSjoerg // side. See example from PR18962 for the triggering cases (the bug was
1376*da58b97aSjoerg // fixed, but we generate different types).
1377*da58b97aSjoerg if (!PSI->isHotCount(EntryCountDistributed))
1378*da58b97aSjoerg break;
1379*da58b97aSjoerg SmallVector<CallBase *, 8> InlinedCallSites;
1380*da58b97aSjoerg // Attach function profile for promoted indirect callee, and update
1381*da58b97aSjoerg // call site count for the promoted inline candidate too.
1382*da58b97aSjoerg Candidate = {I, FS, EntryCountDistributed,
1383*da58b97aSjoerg Candidate.CallsiteDistribution};
1384*da58b97aSjoerg if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum,
1385*da58b97aSjoerg &InlinedCallSites)) {
1386*da58b97aSjoerg for (auto *CB : InlinedCallSites) {
1387*da58b97aSjoerg if (getInlineCandidate(&NewCandidate, CB))
1388*da58b97aSjoerg CQueue.emplace(NewCandidate);
138906f32e7eSjoerg }
1390*da58b97aSjoerg Changed = true;
139106f32e7eSjoerg }
139206f32e7eSjoerg }
139306f32e7eSjoerg } else if (CalledFunction && CalledFunction->getSubprogram() &&
139406f32e7eSjoerg !CalledFunction->isDeclaration()) {
1395*da58b97aSjoerg SmallVector<CallBase *, 8> InlinedCallSites;
1396*da58b97aSjoerg if (tryInlineCandidate(Candidate, &InlinedCallSites)) {
1397*da58b97aSjoerg for (auto *CB : InlinedCallSites) {
1398*da58b97aSjoerg if (getInlineCandidate(&NewCandidate, CB))
1399*da58b97aSjoerg CQueue.emplace(NewCandidate);
140006f32e7eSjoerg }
140106f32e7eSjoerg Changed = true;
140206f32e7eSjoerg }
1403*da58b97aSjoerg } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1404*da58b97aSjoerg findExternalInlineCandidate(Candidate.CalleeSamples, InlinedGUIDs,
1405*da58b97aSjoerg SymbolMap, PSI->getOrCompHotCountThreshold());
1406*da58b97aSjoerg }
1407*da58b97aSjoerg }
1408*da58b97aSjoerg
1409*da58b97aSjoerg if (!CQueue.empty()) {
1410*da58b97aSjoerg if (SizeLimit == (unsigned)ProfileInlineLimitMax)
1411*da58b97aSjoerg ++NumCSInlinedHitMaxLimit;
1412*da58b97aSjoerg else if (SizeLimit == (unsigned)ProfileInlineLimitMin)
1413*da58b97aSjoerg ++NumCSInlinedHitMinLimit;
141406f32e7eSjoerg else
1415*da58b97aSjoerg ++NumCSInlinedHitGrowthLimit;
141606f32e7eSjoerg }
141706f32e7eSjoerg
141806f32e7eSjoerg return Changed;
141906f32e7eSjoerg }
142006f32e7eSjoerg
142106f32e7eSjoerg /// Returns the sorted CallTargetMap \p M by count in descending order.
1422*da58b97aSjoerg static SmallVector<InstrProfValueData, 2>
GetSortedValueDataFromCallTargets(const SampleRecord::CallTargetMap & M)1423*da58b97aSjoerg GetSortedValueDataFromCallTargets(const SampleRecord::CallTargetMap &M) {
142406f32e7eSjoerg SmallVector<InstrProfValueData, 2> R;
142506f32e7eSjoerg for (const auto &I : SampleRecord::SortCallTargets(M)) {
1426*da58b97aSjoerg R.emplace_back(
1427*da58b97aSjoerg InstrProfValueData{FunctionSamples::getGUID(I.first), I.second});
142806f32e7eSjoerg }
142906f32e7eSjoerg return R;
143006f32e7eSjoerg }
143106f32e7eSjoerg
1432*da58b97aSjoerg // Generate MD_prof metadata for every branch instruction using the
1433*da58b97aSjoerg // edge weights computed during propagation.
generateMDProfMetadata(Function & F)1434*da58b97aSjoerg void SampleProfileLoader::generateMDProfMetadata(Function &F) {
143506f32e7eSjoerg // Generate MD_prof metadata for every branch instruction using the
143606f32e7eSjoerg // edge weights computed during propagation.
143706f32e7eSjoerg LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
143806f32e7eSjoerg LLVMContext &Ctx = F.getContext();
143906f32e7eSjoerg MDBuilder MDB(Ctx);
144006f32e7eSjoerg for (auto &BI : F) {
144106f32e7eSjoerg BasicBlock *BB = &BI;
144206f32e7eSjoerg
144306f32e7eSjoerg if (BlockWeights[BB]) {
144406f32e7eSjoerg for (auto &I : BB->getInstList()) {
144506f32e7eSjoerg if (!isa<CallInst>(I) && !isa<InvokeInst>(I))
144606f32e7eSjoerg continue;
1447*da58b97aSjoerg if (!cast<CallBase>(I).getCalledFunction()) {
144806f32e7eSjoerg const DebugLoc &DLoc = I.getDebugLoc();
144906f32e7eSjoerg if (!DLoc)
145006f32e7eSjoerg continue;
145106f32e7eSjoerg const DILocation *DIL = DLoc;
145206f32e7eSjoerg const FunctionSamples *FS = findFunctionSamples(I);
145306f32e7eSjoerg if (!FS)
145406f32e7eSjoerg continue;
1455*da58b97aSjoerg auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL);
1456*da58b97aSjoerg auto T = FS->findCallTargetMapAt(CallSite);
145706f32e7eSjoerg if (!T || T.get().empty())
145806f32e7eSjoerg continue;
1459*da58b97aSjoerg if (FunctionSamples::ProfileIsProbeBased) {
1460*da58b97aSjoerg // Prorate the callsite counts based on the pre-ICP distribution
1461*da58b97aSjoerg // factor to reflect what is already done to the callsite before
1462*da58b97aSjoerg // ICP, such as calliste cloning.
1463*da58b97aSjoerg if (Optional<PseudoProbe> Probe = extractProbe(I)) {
1464*da58b97aSjoerg if (Probe->Factor < 1)
1465*da58b97aSjoerg T = SampleRecord::adjustCallTargets(T.get(), Probe->Factor);
1466*da58b97aSjoerg }
1467*da58b97aSjoerg }
146806f32e7eSjoerg SmallVector<InstrProfValueData, 2> SortedCallTargets =
146906f32e7eSjoerg GetSortedValueDataFromCallTargets(T.get());
1470*da58b97aSjoerg uint64_t Sum = 0;
1471*da58b97aSjoerg for (const auto &C : T.get())
1472*da58b97aSjoerg Sum += C.second;
1473*da58b97aSjoerg // With CSSPGO all indirect call targets are counted torwards the
1474*da58b97aSjoerg // original indirect call site in the profile, including both
1475*da58b97aSjoerg // inlined and non-inlined targets.
1476*da58b97aSjoerg if (!FunctionSamples::ProfileIsCS) {
1477*da58b97aSjoerg if (const FunctionSamplesMap *M =
1478*da58b97aSjoerg FS->findFunctionSamplesMapAt(CallSite)) {
1479*da58b97aSjoerg for (const auto &NameFS : *M)
1480*da58b97aSjoerg Sum += NameFS.second.getEntrySamples();
1481*da58b97aSjoerg }
1482*da58b97aSjoerg }
1483*da58b97aSjoerg if (Sum)
1484*da58b97aSjoerg updateIDTMetaData(I, SortedCallTargets, Sum);
1485*da58b97aSjoerg else if (OverwriteExistingWeights)
1486*da58b97aSjoerg I.setMetadata(LLVMContext::MD_prof, nullptr);
148706f32e7eSjoerg } else if (!isa<IntrinsicInst>(&I)) {
148806f32e7eSjoerg I.setMetadata(LLVMContext::MD_prof,
148906f32e7eSjoerg MDB.createBranchWeights(
149006f32e7eSjoerg {static_cast<uint32_t>(BlockWeights[BB])}));
149106f32e7eSjoerg }
149206f32e7eSjoerg }
1493*da58b97aSjoerg } else if (OverwriteExistingWeights) {
1494*da58b97aSjoerg // Set profile metadata (possibly annotated by LTO prelink) to zero or
1495*da58b97aSjoerg // clear it for cold code.
1496*da58b97aSjoerg for (auto &I : BB->getInstList()) {
1497*da58b97aSjoerg if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
1498*da58b97aSjoerg if (cast<CallBase>(I).isIndirectCall())
1499*da58b97aSjoerg I.setMetadata(LLVMContext::MD_prof, nullptr);
1500*da58b97aSjoerg else
1501*da58b97aSjoerg I.setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(0));
150206f32e7eSjoerg }
1503*da58b97aSjoerg }
1504*da58b97aSjoerg }
1505*da58b97aSjoerg
150606f32e7eSjoerg Instruction *TI = BB->getTerminator();
150706f32e7eSjoerg if (TI->getNumSuccessors() == 1)
150806f32e7eSjoerg continue;
1509*da58b97aSjoerg if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI) &&
1510*da58b97aSjoerg !isa<IndirectBrInst>(TI))
151106f32e7eSjoerg continue;
151206f32e7eSjoerg
151306f32e7eSjoerg DebugLoc BranchLoc = TI->getDebugLoc();
151406f32e7eSjoerg LLVM_DEBUG(dbgs() << "\nGetting weights for branch at line "
151506f32e7eSjoerg << ((BranchLoc) ? Twine(BranchLoc.getLine())
151606f32e7eSjoerg : Twine("<UNKNOWN LOCATION>"))
151706f32e7eSjoerg << ".\n");
151806f32e7eSjoerg SmallVector<uint32_t, 4> Weights;
151906f32e7eSjoerg uint32_t MaxWeight = 0;
152006f32e7eSjoerg Instruction *MaxDestInst;
152106f32e7eSjoerg for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
152206f32e7eSjoerg BasicBlock *Succ = TI->getSuccessor(I);
152306f32e7eSjoerg Edge E = std::make_pair(BB, Succ);
152406f32e7eSjoerg uint64_t Weight = EdgeWeights[E];
152506f32e7eSjoerg LLVM_DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
152606f32e7eSjoerg // Use uint32_t saturated arithmetic to adjust the incoming weights,
152706f32e7eSjoerg // if needed. Sample counts in profiles are 64-bit unsigned values,
152806f32e7eSjoerg // but internally branch weights are expressed as 32-bit values.
152906f32e7eSjoerg if (Weight > std::numeric_limits<uint32_t>::max()) {
153006f32e7eSjoerg LLVM_DEBUG(dbgs() << " (saturated due to uint32_t overflow)");
153106f32e7eSjoerg Weight = std::numeric_limits<uint32_t>::max();
153206f32e7eSjoerg }
153306f32e7eSjoerg // Weight is added by one to avoid propagation errors introduced by
153406f32e7eSjoerg // 0 weights.
153506f32e7eSjoerg Weights.push_back(static_cast<uint32_t>(Weight + 1));
153606f32e7eSjoerg if (Weight != 0) {
153706f32e7eSjoerg if (Weight > MaxWeight) {
153806f32e7eSjoerg MaxWeight = Weight;
153906f32e7eSjoerg MaxDestInst = Succ->getFirstNonPHIOrDbgOrLifetime();
154006f32e7eSjoerg }
154106f32e7eSjoerg }
154206f32e7eSjoerg }
154306f32e7eSjoerg
154406f32e7eSjoerg uint64_t TempWeight;
154506f32e7eSjoerg // Only set weights if there is at least one non-zero weight.
154606f32e7eSjoerg // In any other case, let the analyzer set weights.
1547*da58b97aSjoerg // Do not set weights if the weights are present unless under
1548*da58b97aSjoerg // OverwriteExistingWeights. In ThinLTO, the profile annotation is done
1549*da58b97aSjoerg // twice. If the first annotation already set the weights, the second pass
1550*da58b97aSjoerg // does not need to set it. With OverwriteExistingWeights, Blocks with zero
1551*da58b97aSjoerg // weight should have their existing metadata (possibly annotated by LTO
1552*da58b97aSjoerg // prelink) cleared.
1553*da58b97aSjoerg if (MaxWeight > 0 &&
1554*da58b97aSjoerg (!TI->extractProfTotalWeight(TempWeight) || OverwriteExistingWeights)) {
155506f32e7eSjoerg LLVM_DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
1556*da58b97aSjoerg TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
155706f32e7eSjoerg ORE->emit([&]() {
155806f32e7eSjoerg return OptimizationRemark(DEBUG_TYPE, "PopularDest", MaxDestInst)
155906f32e7eSjoerg << "most popular destination for conditional branches at "
156006f32e7eSjoerg << ore::NV("CondBranchesLoc", BranchLoc);
156106f32e7eSjoerg });
156206f32e7eSjoerg } else {
1563*da58b97aSjoerg if (OverwriteExistingWeights) {
1564*da58b97aSjoerg TI->setMetadata(LLVMContext::MD_prof, nullptr);
1565*da58b97aSjoerg LLVM_DEBUG(dbgs() << "CLEARED. All branch weights are zero.\n");
1566*da58b97aSjoerg } else {
156706f32e7eSjoerg LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
156806f32e7eSjoerg }
156906f32e7eSjoerg }
157006f32e7eSjoerg }
157106f32e7eSjoerg }
157206f32e7eSjoerg
157306f32e7eSjoerg /// Once all the branch weights are computed, we emit the MD_prof
157406f32e7eSjoerg /// metadata on BB using the computed values for each of its branches.
157506f32e7eSjoerg ///
157606f32e7eSjoerg /// \param F The function to query.
157706f32e7eSjoerg ///
157806f32e7eSjoerg /// \returns true if \p F was modified. Returns false, otherwise.
emitAnnotations(Function & F)157906f32e7eSjoerg bool SampleProfileLoader::emitAnnotations(Function &F) {
158006f32e7eSjoerg bool Changed = false;
158106f32e7eSjoerg
1582*da58b97aSjoerg if (FunctionSamples::ProfileIsProbeBased) {
1583*da58b97aSjoerg if (!ProbeManager->profileIsValid(F, *Samples)) {
1584*da58b97aSjoerg LLVM_DEBUG(
1585*da58b97aSjoerg dbgs() << "Profile is invalid due to CFG mismatch for Function "
1586*da58b97aSjoerg << F.getName());
1587*da58b97aSjoerg ++NumMismatchedProfile;
1588*da58b97aSjoerg return false;
1589*da58b97aSjoerg }
1590*da58b97aSjoerg ++NumMatchedProfile;
1591*da58b97aSjoerg } else {
159206f32e7eSjoerg if (getFunctionLoc(F) == 0)
159306f32e7eSjoerg return false;
159406f32e7eSjoerg
159506f32e7eSjoerg LLVM_DEBUG(dbgs() << "Line number for the first instruction in "
159606f32e7eSjoerg << F.getName() << ": " << getFunctionLoc(F) << "\n");
1597*da58b97aSjoerg }
159806f32e7eSjoerg
159906f32e7eSjoerg DenseSet<GlobalValue::GUID> InlinedGUIDs;
1600*da58b97aSjoerg if (ProfileIsCS && CallsitePrioritizedInline)
1601*da58b97aSjoerg Changed |= inlineHotFunctionsWithPriority(F, InlinedGUIDs);
1602*da58b97aSjoerg else
160306f32e7eSjoerg Changed |= inlineHotFunctions(F, InlinedGUIDs);
160406f32e7eSjoerg
1605*da58b97aSjoerg Changed |= computeAndPropagateWeights(F, InlinedGUIDs);
160606f32e7eSjoerg
1607*da58b97aSjoerg if (Changed)
1608*da58b97aSjoerg generateMDProfMetadata(F);
160906f32e7eSjoerg
1610*da58b97aSjoerg emitCoverageRemarks(F);
161106f32e7eSjoerg return Changed;
161206f32e7eSjoerg }
161306f32e7eSjoerg
161406f32e7eSjoerg char SampleProfileLoaderLegacyPass::ID = 0;
161506f32e7eSjoerg
161606f32e7eSjoerg INITIALIZE_PASS_BEGIN(SampleProfileLoaderLegacyPass, "sample-profile",
161706f32e7eSjoerg "Sample Profile loader", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)161806f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
161906f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1620*da58b97aSjoerg INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
162106f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
162206f32e7eSjoerg INITIALIZE_PASS_END(SampleProfileLoaderLegacyPass, "sample-profile",
162306f32e7eSjoerg "Sample Profile loader", false, false)
162406f32e7eSjoerg
1625*da58b97aSjoerg std::unique_ptr<ProfiledCallGraph>
1626*da58b97aSjoerg SampleProfileLoader::buildProfiledCallGraph(CallGraph &CG) {
1627*da58b97aSjoerg std::unique_ptr<ProfiledCallGraph> ProfiledCG;
1628*da58b97aSjoerg if (ProfileIsCS)
1629*da58b97aSjoerg ProfiledCG = std::make_unique<ProfiledCallGraph>(*ContextTracker);
1630*da58b97aSjoerg else
1631*da58b97aSjoerg ProfiledCG = std::make_unique<ProfiledCallGraph>(Reader->getProfiles());
1632*da58b97aSjoerg
1633*da58b97aSjoerg // Add all functions into the profiled call graph even if they are not in
1634*da58b97aSjoerg // the profile. This makes sure functions missing from the profile still
1635*da58b97aSjoerg // gets a chance to be processed.
1636*da58b97aSjoerg for (auto &Node : CG) {
1637*da58b97aSjoerg const auto *F = Node.first;
1638*da58b97aSjoerg if (!F || F->isDeclaration() || !F->hasFnAttribute("use-sample-profile"))
1639*da58b97aSjoerg continue;
1640*da58b97aSjoerg ProfiledCG->addProfiledFunction(FunctionSamples::getCanonicalFnName(*F));
1641*da58b97aSjoerg }
1642*da58b97aSjoerg
1643*da58b97aSjoerg return ProfiledCG;
1644*da58b97aSjoerg }
1645*da58b97aSjoerg
1646*da58b97aSjoerg std::vector<Function *>
buildFunctionOrder(Module & M,CallGraph * CG)1647*da58b97aSjoerg SampleProfileLoader::buildFunctionOrder(Module &M, CallGraph *CG) {
1648*da58b97aSjoerg std::vector<Function *> FunctionOrderList;
1649*da58b97aSjoerg FunctionOrderList.reserve(M.size());
1650*da58b97aSjoerg
1651*da58b97aSjoerg if (!ProfileTopDownLoad && UseProfiledCallGraph)
1652*da58b97aSjoerg errs() << "WARNING: -use-profiled-call-graph ignored, should be used "
1653*da58b97aSjoerg "together with -sample-profile-top-down-load.\n";
1654*da58b97aSjoerg
1655*da58b97aSjoerg if (!ProfileTopDownLoad || CG == nullptr) {
1656*da58b97aSjoerg if (ProfileMergeInlinee) {
1657*da58b97aSjoerg // Disable ProfileMergeInlinee if profile is not loaded in top down order,
1658*da58b97aSjoerg // because the profile for a function may be used for the profile
1659*da58b97aSjoerg // annotation of its outline copy before the profile merging of its
1660*da58b97aSjoerg // non-inlined inline instances, and that is not the way how
1661*da58b97aSjoerg // ProfileMergeInlinee is supposed to work.
1662*da58b97aSjoerg ProfileMergeInlinee = false;
1663*da58b97aSjoerg }
1664*da58b97aSjoerg
1665*da58b97aSjoerg for (Function &F : M)
1666*da58b97aSjoerg if (!F.isDeclaration() && F.hasFnAttribute("use-sample-profile"))
1667*da58b97aSjoerg FunctionOrderList.push_back(&F);
1668*da58b97aSjoerg return FunctionOrderList;
1669*da58b97aSjoerg }
1670*da58b97aSjoerg
1671*da58b97aSjoerg assert(&CG->getModule() == &M);
1672*da58b97aSjoerg
1673*da58b97aSjoerg if (UseProfiledCallGraph ||
1674*da58b97aSjoerg (ProfileIsCS && !UseProfiledCallGraph.getNumOccurrences())) {
1675*da58b97aSjoerg // Use profiled call edges to augment the top-down order. There are cases
1676*da58b97aSjoerg // that the top-down order computed based on the static call graph doesn't
1677*da58b97aSjoerg // reflect real execution order. For example
1678*da58b97aSjoerg //
1679*da58b97aSjoerg // 1. Incomplete static call graph due to unknown indirect call targets.
1680*da58b97aSjoerg // Adjusting the order by considering indirect call edges from the
1681*da58b97aSjoerg // profile can enable the inlining of indirect call targets by allowing
1682*da58b97aSjoerg // the caller processed before them.
1683*da58b97aSjoerg // 2. Mutual call edges in an SCC. The static processing order computed for
1684*da58b97aSjoerg // an SCC may not reflect the call contexts in the context-sensitive
1685*da58b97aSjoerg // profile, thus may cause potential inlining to be overlooked. The
1686*da58b97aSjoerg // function order in one SCC is being adjusted to a top-down order based
1687*da58b97aSjoerg // on the profile to favor more inlining. This is only a problem with CS
1688*da58b97aSjoerg // profile.
1689*da58b97aSjoerg // 3. Transitive indirect call edges due to inlining. When a callee function
1690*da58b97aSjoerg // (say B) is inlined into into a caller function (say A) in LTO prelink,
1691*da58b97aSjoerg // every call edge originated from the callee B will be transferred to
1692*da58b97aSjoerg // the caller A. If any transferred edge (say A->C) is indirect, the
1693*da58b97aSjoerg // original profiled indirect edge B->C, even if considered, would not
1694*da58b97aSjoerg // enforce a top-down order from the caller A to the potential indirect
1695*da58b97aSjoerg // call target C in LTO postlink since the inlined callee B is gone from
1696*da58b97aSjoerg // the static call graph.
1697*da58b97aSjoerg // 4. #3 can happen even for direct call targets, due to functions defined
1698*da58b97aSjoerg // in header files. A header function (say A), when included into source
1699*da58b97aSjoerg // files, is defined multiple times but only one definition survives due
1700*da58b97aSjoerg // to ODR. Therefore, the LTO prelink inlining done on those dropped
1701*da58b97aSjoerg // definitions can be useless based on a local file scope. More
1702*da58b97aSjoerg // importantly, the inlinee (say B), once fully inlined to a
1703*da58b97aSjoerg // to-be-dropped A, will have no profile to consume when its outlined
1704*da58b97aSjoerg // version is compiled. This can lead to a profile-less prelink
1705*da58b97aSjoerg // compilation for the outlined version of B which may be called from
1706*da58b97aSjoerg // external modules. while this isn't easy to fix, we rely on the
1707*da58b97aSjoerg // postlink AutoFDO pipeline to optimize B. Since the survived copy of
1708*da58b97aSjoerg // the A can be inlined in its local scope in prelink, it may not exist
1709*da58b97aSjoerg // in the merged IR in postlink, and we'll need the profiled call edges
1710*da58b97aSjoerg // to enforce a top-down order for the rest of the functions.
1711*da58b97aSjoerg //
1712*da58b97aSjoerg // Considering those cases, a profiled call graph completely independent of
1713*da58b97aSjoerg // the static call graph is constructed based on profile data, where
1714*da58b97aSjoerg // function objects are not even needed to handle case #3 and case 4.
1715*da58b97aSjoerg //
1716*da58b97aSjoerg // Note that static callgraph edges are completely ignored since they
1717*da58b97aSjoerg // can be conflicting with profiled edges for cyclic SCCs and may result in
1718*da58b97aSjoerg // an SCC order incompatible with profile-defined one. Using strictly
1719*da58b97aSjoerg // profile order ensures a maximum inlining experience. On the other hand,
1720*da58b97aSjoerg // static call edges are not so important when they don't correspond to a
1721*da58b97aSjoerg // context in the profile.
1722*da58b97aSjoerg
1723*da58b97aSjoerg std::unique_ptr<ProfiledCallGraph> ProfiledCG = buildProfiledCallGraph(*CG);
1724*da58b97aSjoerg scc_iterator<ProfiledCallGraph *> CGI = scc_begin(ProfiledCG.get());
1725*da58b97aSjoerg while (!CGI.isAtEnd()) {
1726*da58b97aSjoerg for (ProfiledCallGraphNode *Node : *CGI) {
1727*da58b97aSjoerg Function *F = SymbolMap.lookup(Node->Name);
1728*da58b97aSjoerg if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
1729*da58b97aSjoerg FunctionOrderList.push_back(F);
1730*da58b97aSjoerg }
1731*da58b97aSjoerg ++CGI;
1732*da58b97aSjoerg }
1733*da58b97aSjoerg } else {
1734*da58b97aSjoerg scc_iterator<CallGraph *> CGI = scc_begin(CG);
1735*da58b97aSjoerg while (!CGI.isAtEnd()) {
1736*da58b97aSjoerg for (CallGraphNode *Node : *CGI) {
1737*da58b97aSjoerg auto *F = Node->getFunction();
1738*da58b97aSjoerg if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
1739*da58b97aSjoerg FunctionOrderList.push_back(F);
1740*da58b97aSjoerg }
1741*da58b97aSjoerg ++CGI;
1742*da58b97aSjoerg }
1743*da58b97aSjoerg }
1744*da58b97aSjoerg
1745*da58b97aSjoerg LLVM_DEBUG({
1746*da58b97aSjoerg dbgs() << "Function processing order:\n";
1747*da58b97aSjoerg for (auto F : reverse(FunctionOrderList)) {
1748*da58b97aSjoerg dbgs() << F->getName() << "\n";
1749*da58b97aSjoerg }
1750*da58b97aSjoerg });
1751*da58b97aSjoerg
1752*da58b97aSjoerg std::reverse(FunctionOrderList.begin(), FunctionOrderList.end());
1753*da58b97aSjoerg return FunctionOrderList;
1754*da58b97aSjoerg }
1755*da58b97aSjoerg
doInitialization(Module & M,FunctionAnalysisManager * FAM)1756*da58b97aSjoerg bool SampleProfileLoader::doInitialization(Module &M,
1757*da58b97aSjoerg FunctionAnalysisManager *FAM) {
175806f32e7eSjoerg auto &Ctx = M.getContext();
175906f32e7eSjoerg
176006f32e7eSjoerg auto ReaderOrErr =
176106f32e7eSjoerg SampleProfileReader::create(Filename, Ctx, RemappingFilename);
176206f32e7eSjoerg if (std::error_code EC = ReaderOrErr.getError()) {
176306f32e7eSjoerg std::string Msg = "Could not open profile: " + EC.message();
176406f32e7eSjoerg Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
176506f32e7eSjoerg return false;
176606f32e7eSjoerg }
176706f32e7eSjoerg Reader = std::move(ReaderOrErr.get());
1768*da58b97aSjoerg Reader->setSkipFlatProf(LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink);
1769*da58b97aSjoerg // set module before reading the profile so reader may be able to only
1770*da58b97aSjoerg // read the function profiles which are used by the current module.
1771*da58b97aSjoerg Reader->setModule(&M);
1772*da58b97aSjoerg if (std::error_code EC = Reader->read()) {
1773*da58b97aSjoerg std::string Msg = "profile reading failed: " + EC.message();
1774*da58b97aSjoerg Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
1775*da58b97aSjoerg return false;
1776*da58b97aSjoerg }
1777*da58b97aSjoerg
177806f32e7eSjoerg PSL = Reader->getProfileSymbolList();
177906f32e7eSjoerg
178006f32e7eSjoerg // While profile-sample-accurate is on, ignore symbol list.
178106f32e7eSjoerg ProfAccForSymsInList =
178206f32e7eSjoerg ProfileAccurateForSymsInList && PSL && !ProfileSampleAccurate;
178306f32e7eSjoerg if (ProfAccForSymsInList) {
178406f32e7eSjoerg NamesInProfile.clear();
178506f32e7eSjoerg if (auto NameTable = Reader->getNameTable())
178606f32e7eSjoerg NamesInProfile.insert(NameTable->begin(), NameTable->end());
1787*da58b97aSjoerg CoverageTracker.setProfAccForSymsInList(true);
1788*da58b97aSjoerg }
1789*da58b97aSjoerg
1790*da58b97aSjoerg if (FAM && !ProfileInlineReplayFile.empty()) {
1791*da58b97aSjoerg ExternalInlineAdvisor = std::make_unique<ReplayInlineAdvisor>(
1792*da58b97aSjoerg M, *FAM, Ctx, /*OriginalAdvisor=*/nullptr, ProfileInlineReplayFile,
1793*da58b97aSjoerg /*EmitRemarks=*/false);
1794*da58b97aSjoerg if (!ExternalInlineAdvisor->areReplayRemarksLoaded())
1795*da58b97aSjoerg ExternalInlineAdvisor.reset();
1796*da58b97aSjoerg }
1797*da58b97aSjoerg
1798*da58b97aSjoerg // Apply tweaks if context-sensitive profile is available.
1799*da58b97aSjoerg if (Reader->profileIsCS()) {
1800*da58b97aSjoerg ProfileIsCS = true;
1801*da58b97aSjoerg FunctionSamples::ProfileIsCS = true;
1802*da58b97aSjoerg
1803*da58b97aSjoerg // Enable priority-base inliner and size inline by default for CSSPGO.
1804*da58b97aSjoerg if (!ProfileSizeInline.getNumOccurrences())
1805*da58b97aSjoerg ProfileSizeInline = true;
1806*da58b97aSjoerg if (!CallsitePrioritizedInline.getNumOccurrences())
1807*da58b97aSjoerg CallsitePrioritizedInline = true;
1808*da58b97aSjoerg
1809*da58b97aSjoerg // Tracker for profiles under different context
1810*da58b97aSjoerg ContextTracker =
1811*da58b97aSjoerg std::make_unique<SampleContextTracker>(Reader->getProfiles());
1812*da58b97aSjoerg }
1813*da58b97aSjoerg
1814*da58b97aSjoerg // Load pseudo probe descriptors for probe-based function samples.
1815*da58b97aSjoerg if (Reader->profileIsProbeBased()) {
1816*da58b97aSjoerg ProbeManager = std::make_unique<PseudoProbeManager>(M);
1817*da58b97aSjoerg if (!ProbeManager->moduleIsProbed(M)) {
1818*da58b97aSjoerg const char *Msg =
1819*da58b97aSjoerg "Pseudo-probe-based profile requires SampleProfileProbePass";
1820*da58b97aSjoerg Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
1821*da58b97aSjoerg return false;
1822*da58b97aSjoerg }
182306f32e7eSjoerg }
182406f32e7eSjoerg
182506f32e7eSjoerg return true;
182606f32e7eSjoerg }
182706f32e7eSjoerg
createSampleProfileLoaderPass()182806f32e7eSjoerg ModulePass *llvm::createSampleProfileLoaderPass() {
182906f32e7eSjoerg return new SampleProfileLoaderLegacyPass();
183006f32e7eSjoerg }
183106f32e7eSjoerg
createSampleProfileLoaderPass(StringRef Name)183206f32e7eSjoerg ModulePass *llvm::createSampleProfileLoaderPass(StringRef Name) {
183306f32e7eSjoerg return new SampleProfileLoaderLegacyPass(Name);
183406f32e7eSjoerg }
183506f32e7eSjoerg
runOnModule(Module & M,ModuleAnalysisManager * AM,ProfileSummaryInfo * _PSI,CallGraph * CG)183606f32e7eSjoerg bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager *AM,
1837*da58b97aSjoerg ProfileSummaryInfo *_PSI, CallGraph *CG) {
183806f32e7eSjoerg GUIDToFuncNameMapper Mapper(M, *Reader, GUIDToFuncNameMap);
183906f32e7eSjoerg
184006f32e7eSjoerg PSI = _PSI;
1841*da58b97aSjoerg if (M.getProfileSummary(/* IsCS */ false) == nullptr) {
184206f32e7eSjoerg M.setProfileSummary(Reader->getSummary().getMD(M.getContext()),
184306f32e7eSjoerg ProfileSummary::PSK_Sample);
1844*da58b97aSjoerg PSI->refresh();
1845*da58b97aSjoerg }
184606f32e7eSjoerg // Compute the total number of samples collected in this profile.
184706f32e7eSjoerg for (const auto &I : Reader->getProfiles())
184806f32e7eSjoerg TotalCollectedSamples += I.second.getTotalSamples();
184906f32e7eSjoerg
1850*da58b97aSjoerg auto Remapper = Reader->getRemapper();
185106f32e7eSjoerg // Populate the symbol map.
185206f32e7eSjoerg for (const auto &N_F : M.getValueSymbolTable()) {
185306f32e7eSjoerg StringRef OrigName = N_F.getKey();
185406f32e7eSjoerg Function *F = dyn_cast<Function>(N_F.getValue());
1855*da58b97aSjoerg if (F == nullptr || OrigName.empty())
185606f32e7eSjoerg continue;
185706f32e7eSjoerg SymbolMap[OrigName] = F;
1858*da58b97aSjoerg StringRef NewName = FunctionSamples::getCanonicalFnName(*F);
1859*da58b97aSjoerg if (OrigName != NewName && !NewName.empty()) {
186006f32e7eSjoerg auto r = SymbolMap.insert(std::make_pair(NewName, F));
186106f32e7eSjoerg // Failiing to insert means there is already an entry in SymbolMap,
186206f32e7eSjoerg // thus there are multiple functions that are mapped to the same
186306f32e7eSjoerg // stripped name. In this case of name conflicting, set the value
186406f32e7eSjoerg // to nullptr to avoid confusion.
186506f32e7eSjoerg if (!r.second)
186606f32e7eSjoerg r.first->second = nullptr;
1867*da58b97aSjoerg OrigName = NewName;
1868*da58b97aSjoerg }
1869*da58b97aSjoerg // Insert the remapped names into SymbolMap.
1870*da58b97aSjoerg if (Remapper) {
1871*da58b97aSjoerg if (auto MapName = Remapper->lookUpNameInProfile(OrigName)) {
1872*da58b97aSjoerg if (*MapName != OrigName && !MapName->empty())
1873*da58b97aSjoerg SymbolMap.insert(std::make_pair(*MapName, F));
187406f32e7eSjoerg }
187506f32e7eSjoerg }
1876*da58b97aSjoerg }
1877*da58b97aSjoerg assert(SymbolMap.count(StringRef()) == 0 &&
1878*da58b97aSjoerg "No empty StringRef should be added in SymbolMap");
187906f32e7eSjoerg
188006f32e7eSjoerg bool retval = false;
1881*da58b97aSjoerg for (auto F : buildFunctionOrder(M, CG)) {
1882*da58b97aSjoerg assert(!F->isDeclaration());
188306f32e7eSjoerg clearFunctionData();
1884*da58b97aSjoerg retval |= runOnFunction(*F, AM);
188506f32e7eSjoerg }
188606f32e7eSjoerg
188706f32e7eSjoerg // Account for cold calls not inlined....
1888*da58b97aSjoerg if (!ProfileIsCS)
188906f32e7eSjoerg for (const std::pair<Function *, NotInlinedProfileInfo> &pair :
189006f32e7eSjoerg notInlinedCallInfo)
189106f32e7eSjoerg updateProfileCallee(pair.first, pair.second.entryCount);
189206f32e7eSjoerg
189306f32e7eSjoerg return retval;
189406f32e7eSjoerg }
189506f32e7eSjoerg
runOnModule(Module & M)189606f32e7eSjoerg bool SampleProfileLoaderLegacyPass::runOnModule(Module &M) {
189706f32e7eSjoerg ACT = &getAnalysis<AssumptionCacheTracker>();
189806f32e7eSjoerg TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>();
1899*da58b97aSjoerg TLIWP = &getAnalysis<TargetLibraryInfoWrapperPass>();
190006f32e7eSjoerg ProfileSummaryInfo *PSI =
190106f32e7eSjoerg &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
1902*da58b97aSjoerg return SampleLoader.runOnModule(M, nullptr, PSI, nullptr);
190306f32e7eSjoerg }
190406f32e7eSjoerg
runOnFunction(Function & F,ModuleAnalysisManager * AM)190506f32e7eSjoerg bool SampleProfileLoader::runOnFunction(Function &F, ModuleAnalysisManager *AM) {
1906*da58b97aSjoerg LLVM_DEBUG(dbgs() << "\n\nProcessing Function " << F.getName() << "\n");
190706f32e7eSjoerg DILocation2SampleMap.clear();
190806f32e7eSjoerg // By default the entry count is initialized to -1, which will be treated
190906f32e7eSjoerg // conservatively by getEntryCount as the same as unknown (None). This is
191006f32e7eSjoerg // to avoid newly added code to be treated as cold. If we have samples
191106f32e7eSjoerg // this will be overwritten in emitAnnotations.
191206f32e7eSjoerg uint64_t initialEntryCount = -1;
191306f32e7eSjoerg
191406f32e7eSjoerg ProfAccForSymsInList = ProfileAccurateForSymsInList && PSL;
191506f32e7eSjoerg if (ProfileSampleAccurate || F.hasFnAttribute("profile-sample-accurate")) {
191606f32e7eSjoerg // initialize all the function entry counts to 0. It means all the
191706f32e7eSjoerg // functions without profile will be regarded as cold.
191806f32e7eSjoerg initialEntryCount = 0;
191906f32e7eSjoerg // profile-sample-accurate is a user assertion which has a higher precedence
192006f32e7eSjoerg // than symbol list. When profile-sample-accurate is on, ignore symbol list.
192106f32e7eSjoerg ProfAccForSymsInList = false;
192206f32e7eSjoerg }
1923*da58b97aSjoerg CoverageTracker.setProfAccForSymsInList(ProfAccForSymsInList);
192406f32e7eSjoerg
192506f32e7eSjoerg // PSL -- profile symbol list include all the symbols in sampled binary.
192606f32e7eSjoerg // If ProfileAccurateForSymsInList is enabled, PSL is used to treat
192706f32e7eSjoerg // old functions without samples being cold, without having to worry
192806f32e7eSjoerg // about new and hot functions being mistakenly treated as cold.
192906f32e7eSjoerg if (ProfAccForSymsInList) {
193006f32e7eSjoerg // Initialize the entry count to 0 for functions in the list.
193106f32e7eSjoerg if (PSL->contains(F.getName()))
193206f32e7eSjoerg initialEntryCount = 0;
193306f32e7eSjoerg
193406f32e7eSjoerg // Function in the symbol list but without sample will be regarded as
193506f32e7eSjoerg // cold. To minimize the potential negative performance impact it could
193606f32e7eSjoerg // have, we want to be a little conservative here saying if a function
193706f32e7eSjoerg // shows up in the profile, no matter as outline function, inline instance
193806f32e7eSjoerg // or call targets, treat the function as not being cold. This will handle
193906f32e7eSjoerg // the cases such as most callsites of a function are inlined in sampled
194006f32e7eSjoerg // binary but not inlined in current build (because of source code drift,
194106f32e7eSjoerg // imprecise debug information, or the callsites are all cold individually
194206f32e7eSjoerg // but not cold accumulatively...), so the outline function showing up as
194306f32e7eSjoerg // cold in sampled binary will actually not be cold after current build.
194406f32e7eSjoerg StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
194506f32e7eSjoerg if (NamesInProfile.count(CanonName))
194606f32e7eSjoerg initialEntryCount = -1;
194706f32e7eSjoerg }
194806f32e7eSjoerg
1949*da58b97aSjoerg // Initialize entry count when the function has no existing entry
1950*da58b97aSjoerg // count value.
1951*da58b97aSjoerg if (!F.getEntryCount().hasValue())
195206f32e7eSjoerg F.setEntryCount(ProfileCount(initialEntryCount, Function::PCT_Real));
195306f32e7eSjoerg std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
195406f32e7eSjoerg if (AM) {
195506f32e7eSjoerg auto &FAM =
195606f32e7eSjoerg AM->getResult<FunctionAnalysisManagerModuleProxy>(*F.getParent())
195706f32e7eSjoerg .getManager();
195806f32e7eSjoerg ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
195906f32e7eSjoerg } else {
196006f32e7eSjoerg OwnedORE = std::make_unique<OptimizationRemarkEmitter>(&F);
196106f32e7eSjoerg ORE = OwnedORE.get();
196206f32e7eSjoerg }
1963*da58b97aSjoerg
1964*da58b97aSjoerg if (ProfileIsCS)
1965*da58b97aSjoerg Samples = ContextTracker->getBaseSamplesFor(F);
1966*da58b97aSjoerg else
196706f32e7eSjoerg Samples = Reader->getSamplesFor(F);
1968*da58b97aSjoerg
196906f32e7eSjoerg if (Samples && !Samples->empty())
197006f32e7eSjoerg return emitAnnotations(F);
197106f32e7eSjoerg return false;
197206f32e7eSjoerg }
197306f32e7eSjoerg
run(Module & M,ModuleAnalysisManager & AM)197406f32e7eSjoerg PreservedAnalyses SampleProfileLoaderPass::run(Module &M,
197506f32e7eSjoerg ModuleAnalysisManager &AM) {
197606f32e7eSjoerg FunctionAnalysisManager &FAM =
197706f32e7eSjoerg AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
197806f32e7eSjoerg
197906f32e7eSjoerg auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
198006f32e7eSjoerg return FAM.getResult<AssumptionAnalysis>(F);
198106f32e7eSjoerg };
198206f32e7eSjoerg auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
198306f32e7eSjoerg return FAM.getResult<TargetIRAnalysis>(F);
198406f32e7eSjoerg };
1985*da58b97aSjoerg auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
1986*da58b97aSjoerg return FAM.getResult<TargetLibraryAnalysis>(F);
1987*da58b97aSjoerg };
198806f32e7eSjoerg
198906f32e7eSjoerg SampleProfileLoader SampleLoader(
199006f32e7eSjoerg ProfileFileName.empty() ? SampleProfileFile : ProfileFileName,
199106f32e7eSjoerg ProfileRemappingFileName.empty() ? SampleProfileRemappingFile
199206f32e7eSjoerg : ProfileRemappingFileName,
1993*da58b97aSjoerg LTOPhase, GetAssumptionCache, GetTTI, GetTLI);
199406f32e7eSjoerg
1995*da58b97aSjoerg if (!SampleLoader.doInitialization(M, &FAM))
1996*da58b97aSjoerg return PreservedAnalyses::all();
199706f32e7eSjoerg
199806f32e7eSjoerg ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
1999*da58b97aSjoerg CallGraph &CG = AM.getResult<CallGraphAnalysis>(M);
2000*da58b97aSjoerg if (!SampleLoader.runOnModule(M, &AM, PSI, &CG))
200106f32e7eSjoerg return PreservedAnalyses::all();
200206f32e7eSjoerg
200306f32e7eSjoerg return PreservedAnalyses::none();
200406f32e7eSjoerg }
2005