1 //===- IndirectCallPromotion.cpp - Optimizations based on value profiling -===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the transformation that promotes indirect calls to
10 // conditional direct calls when the indirect-call value profile metadata is
11 // available.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
21 #include "llvm/Analysis/IndirectCallVisitor.h"
22 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
23 #include "llvm/Analysis/ProfileSummaryInfo.h"
24 #include "llvm/IR/Attributes.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/DiagnosticInfo.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/IR/MDBuilder.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/ProfileData/InstrProf.h"
42 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/CommandLine.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/Error.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include "llvm/Transforms/Instrumentation.h"
48 #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
49 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
50 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
51 #include <cassert>
52 #include <cstdint>
53 #include <memory>
54 #include <string>
55 #include <utility>
56 #include <vector>
57
58 using namespace llvm;
59
60 #define DEBUG_TYPE "pgo-icall-prom"
61
62 STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
63 STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
64
65 // Command line option to disable indirect-call promotion with the default as
66 // false. This is for debug purpose.
67 static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,
68 cl::desc("Disable indirect call promotion"));
69
70 // Set the cutoff value for the promotion. If the value is other than 0, we
71 // stop the transformation once the total number of promotions equals the cutoff
72 // value.
73 // For debug use only.
74 static cl::opt<unsigned>
75 ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore,
76 cl::desc("Max number of promotions for this compilation"));
77
78 // If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.
79 // For debug use only.
80 static cl::opt<unsigned>
81 ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore,
82 cl::desc("Skip Callsite up to this number for this compilation"));
83
84 // Set if the pass is called in LTO optimization. The difference for LTO mode
85 // is the pass won't prefix the source module name to the internal linkage
86 // symbols.
87 static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(false), cl::Hidden,
88 cl::desc("Run indirect-call promotion in LTO "
89 "mode"));
90
91 // Set if the pass is called in SamplePGO mode. The difference for SamplePGO
92 // mode is it will add prof metadatato the created direct call.
93 static cl::opt<bool>
94 ICPSamplePGOMode("icp-samplepgo", cl::init(false), cl::Hidden,
95 cl::desc("Run indirect-call promotion in SamplePGO mode"));
96
97 // If the option is set to true, only call instructions will be considered for
98 // transformation -- invoke instructions will be ignored.
99 static cl::opt<bool>
100 ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden,
101 cl::desc("Run indirect-call promotion for call instructions "
102 "only"));
103
104 // If the option is set to true, only invoke instructions will be considered for
105 // transformation -- call instructions will be ignored.
106 static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false),
107 cl::Hidden,
108 cl::desc("Run indirect-call promotion for "
109 "invoke instruction only"));
110
111 // Dump the function level IR if the transformation happened in this
112 // function. For debug use only.
113 static cl::opt<bool>
114 ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
115 cl::desc("Dump IR after transformation happens"));
116
117 namespace {
118
119 class PGOIndirectCallPromotionLegacyPass : public ModulePass {
120 public:
121 static char ID;
122
PGOIndirectCallPromotionLegacyPass(bool InLTO=false,bool SamplePGO=false)123 PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false)
124 : ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) {
125 initializePGOIndirectCallPromotionLegacyPassPass(
126 *PassRegistry::getPassRegistry());
127 }
128
getAnalysisUsage(AnalysisUsage & AU) const129 void getAnalysisUsage(AnalysisUsage &AU) const override {
130 AU.addRequired<ProfileSummaryInfoWrapperPass>();
131 }
132
getPassName() const133 StringRef getPassName() const override { return "PGOIndirectCallPromotion"; }
134
135 private:
136 bool runOnModule(Module &M) override;
137
138 // If this pass is called in LTO. We need to special handling the PGOFuncName
139 // for the static variables due to LTO's internalization.
140 bool InLTO;
141
142 // If this pass is called in SamplePGO. We need to add the prof metadata to
143 // the promoted direct call.
144 bool SamplePGO;
145 };
146
147 } // end anonymous namespace
148
149 char PGOIndirectCallPromotionLegacyPass::ID = 0;
150
151 INITIALIZE_PASS_BEGIN(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
152 "Use PGO instrumentation profile to promote indirect "
153 "calls to direct calls.",
154 false, false)
INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)155 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
156 INITIALIZE_PASS_END(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
157 "Use PGO instrumentation profile to promote indirect "
158 "calls to direct calls.",
159 false, false)
160
161 ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,
162 bool SamplePGO) {
163 return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);
164 }
165
166 namespace {
167
168 // The class for main data structure to promote indirect calls to conditional
169 // direct calls.
170 class ICallPromotionFunc {
171 private:
172 Function &F;
173 Module *M;
174
175 // Symtab that maps indirect call profile values to function names and
176 // defines.
177 InstrProfSymtab *Symtab;
178
179 bool SamplePGO;
180
181 OptimizationRemarkEmitter &ORE;
182
183 // A struct that records the direct target and it's call count.
184 struct PromotionCandidate {
185 Function *TargetFunction;
186 uint64_t Count;
187
PromotionCandidate__anon29466d500211::ICallPromotionFunc::PromotionCandidate188 PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {}
189 };
190
191 // Check if the indirect-call call site should be promoted. Return the number
192 // of promotions. Inst is the candidate indirect call, ValueDataRef
193 // contains the array of value profile data for profiled targets,
194 // TotalCount is the total profiled count of call executions, and
195 // NumCandidates is the number of candidate entries in ValueDataRef.
196 std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
197 Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
198 uint64_t TotalCount, uint32_t NumCandidates);
199
200 // Promote a list of targets for one indirect-call callsite. Return
201 // the number of promotions.
202 uint32_t tryToPromote(Instruction *Inst,
203 const std::vector<PromotionCandidate> &Candidates,
204 uint64_t &TotalCount);
205
206 public:
ICallPromotionFunc(Function & Func,Module * Modu,InstrProfSymtab * Symtab,bool SamplePGO,OptimizationRemarkEmitter & ORE)207 ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab,
208 bool SamplePGO, OptimizationRemarkEmitter &ORE)
209 : F(Func), M(Modu), Symtab(Symtab), SamplePGO(SamplePGO), ORE(ORE) {}
210 ICallPromotionFunc(const ICallPromotionFunc &) = delete;
211 ICallPromotionFunc &operator=(const ICallPromotionFunc &) = delete;
212
213 bool processFunction(ProfileSummaryInfo *PSI);
214 };
215
216 } // end anonymous namespace
217
218 // Indirect-call promotion heuristic. The direct targets are sorted based on
219 // the count. Stop at the first target that is not promoted.
220 std::vector<ICallPromotionFunc::PromotionCandidate>
getPromotionCandidatesForCallSite(Instruction * Inst,const ArrayRef<InstrProfValueData> & ValueDataRef,uint64_t TotalCount,uint32_t NumCandidates)221 ICallPromotionFunc::getPromotionCandidatesForCallSite(
222 Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
223 uint64_t TotalCount, uint32_t NumCandidates) {
224 std::vector<PromotionCandidate> Ret;
225
226 LLVM_DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
227 << " Num_targets: " << ValueDataRef.size()
228 << " Num_candidates: " << NumCandidates << "\n");
229 NumOfPGOICallsites++;
230 if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
231 LLVM_DEBUG(dbgs() << " Skip: User options.\n");
232 return Ret;
233 }
234
235 for (uint32_t I = 0; I < NumCandidates; I++) {
236 uint64_t Count = ValueDataRef[I].Count;
237 assert(Count <= TotalCount);
238 uint64_t Target = ValueDataRef[I].Value;
239 LLVM_DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
240 << " Target_func: " << Target << "\n");
241
242 if (ICPInvokeOnly && isa<CallInst>(Inst)) {
243 LLVM_DEBUG(dbgs() << " Not promote: User options.\n");
244 ORE.emit([&]() {
245 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
246 << " Not promote: User options";
247 });
248 break;
249 }
250 if (ICPCallOnly && isa<InvokeInst>(Inst)) {
251 LLVM_DEBUG(dbgs() << " Not promote: User option.\n");
252 ORE.emit([&]() {
253 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
254 << " Not promote: User options";
255 });
256 break;
257 }
258 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
259 LLVM_DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
260 ORE.emit([&]() {
261 return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", Inst)
262 << " Not promote: Cutoff reached";
263 });
264 break;
265 }
266
267 Function *TargetFunction = Symtab->getFunction(Target);
268 if (TargetFunction == nullptr) {
269 LLVM_DEBUG(dbgs() << " Not promote: Cannot find the target\n");
270 ORE.emit([&]() {
271 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", Inst)
272 << "Cannot promote indirect call: target with md5sum "
273 << ore::NV("target md5sum", Target) << " not found";
274 });
275 break;
276 }
277
278 const char *Reason = nullptr;
279 if (!isLegalToPromote(CallSite(Inst), TargetFunction, &Reason)) {
280 using namespace ore;
281
282 ORE.emit([&]() {
283 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", Inst)
284 << "Cannot promote indirect call to "
285 << NV("TargetFunction", TargetFunction) << " with count of "
286 << NV("Count", Count) << ": " << Reason;
287 });
288 break;
289 }
290
291 Ret.push_back(PromotionCandidate(TargetFunction, Count));
292 TotalCount -= Count;
293 }
294 return Ret;
295 }
296
promoteIndirectCall(Instruction * Inst,Function * DirectCallee,uint64_t Count,uint64_t TotalCount,bool AttachProfToDirectCall,OptimizationRemarkEmitter * ORE)297 Instruction *llvm::pgo::promoteIndirectCall(Instruction *Inst,
298 Function *DirectCallee,
299 uint64_t Count, uint64_t TotalCount,
300 bool AttachProfToDirectCall,
301 OptimizationRemarkEmitter *ORE) {
302
303 uint64_t ElseCount = TotalCount - Count;
304 uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
305 uint64_t Scale = calculateCountScale(MaxCount);
306 MDBuilder MDB(Inst->getContext());
307 MDNode *BranchWeights = MDB.createBranchWeights(
308 scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
309
310 Instruction *NewInst =
311 promoteCallWithIfThenElse(CallSite(Inst), DirectCallee, BranchWeights);
312
313 if (AttachProfToDirectCall) {
314 MDBuilder MDB(NewInst->getContext());
315 NewInst->setMetadata(
316 LLVMContext::MD_prof,
317 MDB.createBranchWeights({static_cast<uint32_t>(Count)}));
318 }
319
320 using namespace ore;
321
322 if (ORE)
323 ORE->emit([&]() {
324 return OptimizationRemark(DEBUG_TYPE, "Promoted", Inst)
325 << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
326 << " with count " << NV("Count", Count) << " out of "
327 << NV("TotalCount", TotalCount);
328 });
329 return NewInst;
330 }
331
332 // Promote indirect-call to conditional direct-call for one callsite.
tryToPromote(Instruction * Inst,const std::vector<PromotionCandidate> & Candidates,uint64_t & TotalCount)333 uint32_t ICallPromotionFunc::tryToPromote(
334 Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
335 uint64_t &TotalCount) {
336 uint32_t NumPromoted = 0;
337
338 for (auto &C : Candidates) {
339 uint64_t Count = C.Count;
340 pgo::promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount,
341 SamplePGO, &ORE);
342 assert(TotalCount >= Count);
343 TotalCount -= Count;
344 NumOfPGOICallPromotion++;
345 NumPromoted++;
346 }
347 return NumPromoted;
348 }
349
350 // Traverse all the indirect-call callsite and get the value profile
351 // annotation to perform indirect-call promotion.
processFunction(ProfileSummaryInfo * PSI)352 bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) {
353 bool Changed = false;
354 ICallPromotionAnalysis ICallAnalysis;
355 for (auto &I : findIndirectCalls(F)) {
356 uint32_t NumVals, NumCandidates;
357 uint64_t TotalCount;
358 auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
359 I, NumVals, TotalCount, NumCandidates);
360 if (!NumCandidates ||
361 (PSI && PSI->hasProfileSummary() && !PSI->isHotCount(TotalCount)))
362 continue;
363 auto PromotionCandidates = getPromotionCandidatesForCallSite(
364 I, ICallProfDataRef, TotalCount, NumCandidates);
365 uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
366 if (NumPromoted == 0)
367 continue;
368
369 Changed = true;
370 // Adjust the MD.prof metadata. First delete the old one.
371 I->setMetadata(LLVMContext::MD_prof, nullptr);
372 // If all promoted, we don't need the MD.prof metadata.
373 if (TotalCount == 0 || NumPromoted == NumVals)
374 continue;
375 // Otherwise we need update with the un-promoted records back.
376 annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
377 IPVK_IndirectCallTarget, NumCandidates);
378 }
379 return Changed;
380 }
381
382 // A wrapper function that does the actual work.
promoteIndirectCalls(Module & M,ProfileSummaryInfo * PSI,bool InLTO,bool SamplePGO,ModuleAnalysisManager * AM=nullptr)383 static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI,
384 bool InLTO, bool SamplePGO,
385 ModuleAnalysisManager *AM = nullptr) {
386 if (DisableICP)
387 return false;
388 InstrProfSymtab Symtab;
389 if (Error E = Symtab.create(M, InLTO)) {
390 std::string SymtabFailure = toString(std::move(E));
391 LLVM_DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
392 (void)SymtabFailure;
393 return false;
394 }
395 bool Changed = false;
396 for (auto &F : M) {
397 if (F.isDeclaration() || F.hasOptNone())
398 continue;
399
400 std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
401 OptimizationRemarkEmitter *ORE;
402 if (AM) {
403 auto &FAM =
404 AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
405 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
406 } else {
407 OwnedORE = std::make_unique<OptimizationRemarkEmitter>(&F);
408 ORE = OwnedORE.get();
409 }
410
411 ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE);
412 bool FuncChanged = ICallPromotion.processFunction(PSI);
413 if (ICPDUMPAFTER && FuncChanged) {
414 LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
415 LLVM_DEBUG(dbgs() << "\n");
416 }
417 Changed |= FuncChanged;
418 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
419 LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n");
420 break;
421 }
422 }
423 return Changed;
424 }
425
runOnModule(Module & M)426 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
427 ProfileSummaryInfo *PSI =
428 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
429
430 // Command-line option has the priority for InLTO.
431 return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
432 SamplePGO | ICPSamplePGOMode);
433 }
434
run(Module & M,ModuleAnalysisManager & AM)435 PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
436 ModuleAnalysisManager &AM) {
437 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
438
439 if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
440 SamplePGO | ICPSamplePGOMode, &AM))
441 return PreservedAnalyses::all();
442
443 return PreservedAnalyses::none();
444 }
445