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/DenseMap.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/StringRef.h"
19#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
20#include "llvm/Analysis/IndirectCallVisitor.h"
21#include "llvm/Analysis/OptimizationRemarkEmitter.h"
22#include "llvm/Analysis/ProfileSummaryInfo.h"
23#include "llvm/Analysis/TypeMetadataUtils.h"
24#include "llvm/IR/DiagnosticInfo.h"
25#include "llvm/IR/Dominators.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/InstrTypes.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/LLVMContext.h"
30#include "llvm/IR/MDBuilder.h"
31#include "llvm/IR/PassManager.h"
32#include "llvm/IR/ProfDataUtils.h"
33#include "llvm/IR/Value.h"
34#include "llvm/ProfileData/InstrProf.h"
35#include "llvm/ProfileData/ProfileCommon.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/Error.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
42#include "llvm/Transforms/Utils/CallPromotionUtils.h"
43#include "llvm/Transforms/Utils/Instrumentation.h"
44#include <cassert>
45#include <cstdint>
46#include <set>
47#include <string>
48#include <utility>
49#include <vector>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "pgo-icall-prom"
54
55STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
56STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
57
58namespace llvm {
59extern cl::opt<unsigned> MaxNumVTableAnnotations;
60
61extern cl::opt<bool> EnableVTableProfileUse;
62} // namespace llvm
63
64// Command line option to disable indirect-call promotion with the default as
65// false. This is for debug purpose.
66static cl::opt<bool> DisableICP("disable-icp", cl::init(Val: false), cl::Hidden,
67 cl::desc("Disable indirect call promotion"));
68
69// Set the cutoff value for the promotion. If the value is other than 0, we
70// stop the transformation once the total number of promotions equals the cutoff
71// value.
72// For debug use only.
73static cl::opt<unsigned>
74 ICPCutOff("icp-cutoff", cl::init(Val: 0), cl::Hidden,
75 cl::desc("Max number of promotions for this compilation"));
76
77// If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.
78// For debug use only.
79static cl::opt<unsigned>
80 ICPCSSkip("icp-csskip", cl::init(Val: 0), cl::Hidden,
81 cl::desc("Skip Callsite up to this number for this compilation"));
82
83// ICP the candidate function even when only a declaration is present.
84static cl::opt<bool> ICPAllowDecls(
85 "icp-allow-decls", cl::init(Val: false), cl::Hidden,
86 cl::desc("Promote the target candidate even when the definition "
87 " is not available"));
88
89// ICP hot candidate functions only. When setting to false, non-cold functions
90// (warm functions) can also be promoted.
91static cl::opt<bool>
92 ICPAllowHotOnly("icp-allow-hot-only", cl::init(Val: true), cl::Hidden,
93 cl::desc("Promote the target candidate only if it is a "
94 "hot function. Otherwise, warm functions can "
95 "also be promoted"));
96
97// If one target cannot be ICP'd, proceed with the remaining targets instead
98// of exiting the callsite.
99static cl::opt<bool> ICPAllowCandidateSkip(
100 "icp-allow-candidate-skip", cl::init(Val: false), cl::Hidden,
101 cl::desc("Continue with the remaining targets instead of exiting "
102 "when failing in a candidate"));
103
104// Set if the pass is called in LTO optimization. The difference for LTO mode
105// is the pass won't prefix the source module name to the internal linkage
106// symbols.
107static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(Val: false), cl::Hidden,
108 cl::desc("Run indirect-call promotion in LTO "
109 "mode"));
110
111// Set if the pass is called in SamplePGO mode. The difference for SamplePGO
112// mode is it will add prof metadatato the created direct call.
113static cl::opt<bool>
114 ICPSamplePGOMode("icp-samplepgo", cl::init(Val: false), cl::Hidden,
115 cl::desc("Run indirect-call promotion in SamplePGO mode"));
116
117// If the option is set to true, only call instructions will be considered for
118// transformation -- invoke instructions will be ignored.
119static cl::opt<bool>
120 ICPCallOnly("icp-call-only", cl::init(Val: false), cl::Hidden,
121 cl::desc("Run indirect-call promotion for call instructions "
122 "only"));
123
124// If the option is set to true, only invoke instructions will be considered for
125// transformation -- call instructions will be ignored.
126static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(Val: false),
127 cl::Hidden,
128 cl::desc("Run indirect-call promotion for "
129 "invoke instruction only"));
130
131// Dump the function level IR if the transformation happened in this
132// function. For debug use only.
133static cl::opt<bool>
134 ICPDUMPAFTER("icp-dumpafter", cl::init(Val: false), cl::Hidden,
135 cl::desc("Dump IR after transformation happens"));
136
137// Indirect call promotion pass will fall back to function-based comparison if
138// vtable-count / function-count is smaller than this threshold.
139static cl::opt<float> ICPVTablePercentageThreshold(
140 "icp-vtable-percentage-threshold", cl::init(Val: 0.995), cl::Hidden,
141 cl::desc("The percentage threshold of vtable-count / function-count for "
142 "cost-benefit analysis."));
143
144// Although comparing vtables can save a vtable load, we may need to compare
145// vtable pointer with multiple vtable address points due to class inheritance.
146// Comparing with multiple vtables inserts additional instructions on hot code
147// path, and doing so for an earlier candidate delays the comparisons for later
148// candidates. For the last candidate, only the fallback path is affected.
149// We allow multiple vtable comparison for the last function candidate and use
150// the option below to cap the number of vtables.
151static cl::opt<int> ICPMaxNumVTableLastCandidate(
152 "icp-max-num-vtable-last-candidate", cl::init(Val: 1), cl::Hidden,
153 cl::desc("The maximum number of vtable for the last candidate."));
154
155static cl::list<std::string> ICPIgnoredBaseTypes(
156 "icp-ignored-base-types", cl::Hidden,
157 cl::desc(
158 "A list of mangled vtable type info names. Classes specified by the "
159 "type info names and their derived ones will not be vtable-ICP'ed. "
160 "Useful when the profiled types and actual types in the optimized "
161 "binary could be different due to profiling limitations. Type info "
162 "names are those string literals used in LLVM type metadata"));
163
164static cl::opt<int> HotFuncCutoffForICP(
165 "hot-func-cutoff-for-icp", cl::Hidden, cl::init(Val: -1),
166 cl::desc("A count is hot for indirect call promotion if it exceeds "
167 "the minimum count to reach this percentile of total counts."
168 "Note that this percentile is specified as "
169 "percentile * 10000 = HotFuncCutoffForICP."
170 "Default value -1 means that if the flag is unspecified then "
171 "the value of ProfileSummaryCutoffHot will be used instead."));
172namespace {
173
174// The key is a vtable global variable, and the value is a map.
175// In the inner map, the key represents address point offsets and the value is a
176// constant for this address point.
177using VTableAddressPointOffsetValMap =
178 SmallDenseMap<const GlobalVariable *, DenseMap<int, Constant *>>;
179
180// A struct to collect type information for a virtual call site.
181struct VirtualCallSiteInfo {
182 // The offset from the address point to virtual function in the vtable.
183 uint64_t FunctionOffset;
184 // The instruction that computes the address point of vtable.
185 Instruction *VPtr;
186 // The compatible type used in LLVM type intrinsics.
187 StringRef CompatibleTypeStr;
188};
189
190// The key is a virtual call, and value is its type information.
191using VirtualCallSiteTypeInfoMap =
192 SmallDenseMap<const CallBase *, VirtualCallSiteInfo>;
193
194// The key is vtable GUID, and value is its value profile count.
195using VTableGUIDCountsMap = SmallDenseMap<uint64_t, uint64_t, 16>;
196
197// Return the address point offset of the given compatible type.
198//
199// Type metadata of a vtable specifies the types that can contain a pointer to
200// this vtable, for example, `Base*` can be a pointer to an derived type
201// but not vice versa. See also https://llvm.org/docs/TypeMetadata.html
202static std::optional<uint64_t>
203getAddressPointOffset(const GlobalVariable &VTableVar,
204 StringRef CompatibleType) {
205 SmallVector<MDNode *> Types;
206 VTableVar.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
207
208 for (MDNode *Type : Types)
209 if (auto *TypeId = dyn_cast<MDString>(Val: Type->getOperand(I: 1).get());
210 TypeId && TypeId->getString() == CompatibleType)
211 return cast<ConstantInt>(
212 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
213 ->getZExtValue();
214
215 return std::nullopt;
216}
217
218// Return a constant representing the vtable's address point specified by the
219// offset.
220static Constant *getVTableAddressPointOffset(GlobalVariable *VTable,
221 uint32_t AddressPointOffset) {
222 Module &M = *VTable->getParent();
223 LLVMContext &Context = M.getContext();
224 assert(AddressPointOffset < VTable->getGlobalSize(M.getDataLayout()) &&
225 "Out-of-bound access");
226
227 return ConstantExpr::getInBoundsPtrAdd(
228 Ptr: VTable,
229 Offset: llvm::ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: AddressPointOffset));
230}
231
232// Return the basic block in which Use `U` is used via its `UserInst`.
233static BasicBlock *getUserBasicBlock(Use &U, Instruction *UserInst) {
234 if (PHINode *PN = dyn_cast<PHINode>(Val: UserInst))
235 return PN->getIncomingBlock(U);
236
237 return UserInst->getParent();
238}
239
240// `DestBB` is a suitable basic block to sink `Inst` into when `Inst` have users
241// and all users are in `DestBB`. The caller guarantees that `Inst->getParent()`
242// is the sole predecessor of `DestBB` and `DestBB` is dominated by
243// `Inst->getParent()`.
244static bool isDestBBSuitableForSink(Instruction *Inst, BasicBlock *DestBB) {
245 // 'BB' is used only by assert.
246 [[maybe_unused]] BasicBlock *BB = Inst->getParent();
247
248 assert(BB != DestBB && BB->getTerminator()->getNumSuccessors() == 2 &&
249 DestBB->getUniquePredecessor() == BB &&
250 "Guaranteed by ICP transformation");
251
252 BasicBlock *UserBB = nullptr;
253 for (Use &Use : Inst->uses()) {
254 User *User = Use.getUser();
255 // Do checked cast since IR verifier guarantees that the user of an
256 // instruction must be an instruction. See `Verifier::visitInstruction`.
257 Instruction *UserInst = cast<Instruction>(Val: User);
258 // We can sink debug or pseudo instructions together with Inst.
259 if (UserInst->isDebugOrPseudoInst())
260 continue;
261 UserBB = getUserBasicBlock(U&: Use, UserInst);
262 // Do not sink if Inst is used in a basic block that is not DestBB.
263 // TODO: Sink to the common dominator of all user blocks.
264 if (UserBB != DestBB)
265 return false;
266 }
267 return UserBB != nullptr;
268}
269
270// For the virtual call dispatch sequence, try to sink vtable load instructions
271// to the cold indirect call fallback.
272// FIXME: Move the sink eligibility check below to a utility function in
273// Transforms/Utils/ directory.
274static bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
275 if (!isDestBBSuitableForSink(Inst: I, DestBB: DestBlock))
276 return false;
277
278 // Do not move control-flow-involving, volatile loads, vaarg, alloca
279 // instructions, etc.
280 if (isa<PHINode>(Val: I) || I->isEHPad() || I->mayThrow() || !I->willReturn() ||
281 isa<AllocaInst>(Val: I))
282 return false;
283
284 // Do not sink convergent call instructions.
285 if (const auto *C = dyn_cast<CallBase>(Val: I))
286 if (C->isInlineAsm() || C->cannotMerge() || C->isConvergent())
287 return false;
288
289 // Do not move an instruction that may write to memory.
290 if (I->mayWriteToMemory())
291 return false;
292
293 // We can only sink load instructions if there is nothing between the load and
294 // the end of block that could change the value.
295 if (I->mayReadFromMemory()) {
296 // We already know that SrcBlock is the unique predecessor of DestBlock.
297 for (BasicBlock::iterator Scan = std::next(x: I->getIterator()),
298 E = I->getParent()->end();
299 Scan != E; ++Scan) {
300 // Note analysis analysis can tell whether two pointers can point to the
301 // same object in memory or not thereby find further opportunities to
302 // sink.
303 if (Scan->mayWriteToMemory())
304 return false;
305 }
306 }
307
308 BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
309 I->moveBefore(BB&: *DestBlock, I: InsertPos);
310
311 // TODO: Sink debug intrinsic users of I to 'DestBlock'.
312 // 'InstCombinerImpl::tryToSinkInstructionDbgValues' and
313 // 'InstCombinerImpl::tryToSinkInstructionDbgVariableRecords' already have
314 // the core logic to do this.
315 return true;
316}
317
318// Try to sink instructions after VPtr to the indirect call fallback.
319// Return the number of sunk IR instructions.
320static int tryToSinkInstructions(BasicBlock *OriginalBB,
321 BasicBlock *IndirectCallBB) {
322 int SinkCount = 0;
323 // Do not sink across a critical edge for simplicity.
324 if (IndirectCallBB->getUniquePredecessor() != OriginalBB)
325 return SinkCount;
326 // Sink all eligible instructions in OriginalBB in reverse order.
327 for (Instruction &I :
328 llvm::make_early_inc_range(Range: llvm::drop_begin(RangeOrContainer: llvm::reverse(C&: *OriginalBB))))
329 if (tryToSinkInstruction(I: &I, DestBlock: IndirectCallBB))
330 SinkCount++;
331
332 return SinkCount;
333}
334
335// Promote indirect calls to conditional direct calls, keeping track of
336// thresholds.
337class IndirectCallPromoter {
338private:
339 Function &F;
340 Module &M;
341
342 // Symtab that maps indirect call profile values to function names and
343 // defines.
344 InstrProfSymtab *const Symtab;
345
346 const bool SamplePGO;
347
348 // A map from a virtual call to its type information.
349 const VirtualCallSiteTypeInfoMap &VirtualCSInfo;
350
351 VTableAddressPointOffsetValMap &VTableAddressPointOffsetVal;
352
353 OptimizationRemarkEmitter &ORE;
354
355 const DenseSet<StringRef> &IgnoredBaseTypes;
356
357 // A struct that records the direct target and it's call count.
358 struct PromotionCandidate {
359 Function *const TargetFunction;
360 const uint64_t Count;
361 const uint32_t Index;
362
363 // The following fields only exists for promotion candidates with vtable
364 // information.
365 //
366 // Due to class inheritance, one virtual call candidate can come from
367 // multiple vtables. `VTableGUIDAndCounts` tracks the vtable GUIDs and
368 // counts for 'TargetFunction'. `AddressPoints` stores the vtable address
369 // points for comparison.
370 VTableGUIDCountsMap VTableGUIDAndCounts;
371 SmallVector<Constant *> AddressPoints;
372
373 PromotionCandidate(Function *F, uint64_t C, uint32_t I)
374 : TargetFunction(F), Count(C), Index(I) {}
375 };
376
377 // Check if the indirect-call call site should be promoted. Return the number
378 // of promotions. Inst is the candidate indirect call, ValueDataRef
379 // contains the array of value profile data for profiled targets,
380 // TotalCount is the total profiled count of call executions, and
381 // NumCandidates is the number of candidate entries in ValueDataRef.
382 std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
383 const CallBase &CB, ArrayRef<InstrProfValueData> ValueDataRef,
384 uint64_t TotalCount, uint32_t NumCandidates);
385
386 // Promote a list of targets for one indirect-call callsite by comparing
387 // indirect callee with functions. Return true if there are IR
388 // transformations and false otherwise.
389 bool tryToPromoteWithFuncCmp(
390 CallBase &CB, Instruction *VPtr, ArrayRef<PromotionCandidate> Candidates,
391 uint64_t TotalCount, MutableArrayRef<InstrProfValueData> ICallProfDataRef,
392 uint32_t NumCandidates, VTableGUIDCountsMap &VTableGUIDCounts);
393
394 // Promote a list of targets for one indirect call by comparing vtables with
395 // functions. Return true if there are IR transformations and false
396 // otherwise.
397 bool tryToPromoteWithVTableCmp(
398 CallBase &CB, Instruction *VPtr, ArrayRef<PromotionCandidate> Candidates,
399 uint64_t TotalFuncCount, uint32_t NumCandidates,
400 MutableArrayRef<InstrProfValueData> ICallProfDataRef,
401 VTableGUIDCountsMap &VTableGUIDCounts);
402
403 // Return true if it's profitable to compare vtables for the callsite.
404 bool isProfitableToCompareVTables(const CallBase &CB,
405 ArrayRef<PromotionCandidate> Candidates);
406
407 // Return true if the vtable corresponding to VTableGUID should be skipped
408 // for vtable-based comparison.
409 bool shouldSkipVTable(uint64_t VTableGUID);
410
411 // Given an indirect callsite and the list of function candidates, compute
412 // the following vtable information in output parameters and return vtable
413 // pointer if type profiles exist.
414 // - Populate `VTableGUIDCounts` with <vtable-guid, count> using !prof
415 // metadata attached on the vtable pointer.
416 // - For each function candidate, finds out the vtables from which it gets
417 // called and stores the <vtable-guid, count> in promotion candidate.
418 Instruction *computeVTableInfos(const CallBase *CB,
419 VTableGUIDCountsMap &VTableGUIDCounts,
420 std::vector<PromotionCandidate> &Candidates);
421
422 Constant *getOrCreateVTableAddressPointVar(GlobalVariable *GV,
423 uint64_t AddressPointOffset);
424
425 void updateFuncValueProfiles(CallBase &CB,
426 MutableArrayRef<InstrProfValueData> VDs,
427 uint64_t Sum, uint32_t MaxMDCount);
428
429 void updateVPtrValueProfiles(Instruction *VPtr,
430 VTableGUIDCountsMap &VTableGUIDCounts);
431
432 bool isValidTarget(uint64_t, Function *, const CallBase &, uint64_t);
433
434public:
435 IndirectCallPromoter(
436 Function &Func, Module &M, InstrProfSymtab *Symtab, bool SamplePGO,
437 const VirtualCallSiteTypeInfoMap &VirtualCSInfo,
438 VTableAddressPointOffsetValMap &VTableAddressPointOffsetVal,
439 const DenseSet<StringRef> &IgnoredBaseTypes,
440 OptimizationRemarkEmitter &ORE)
441 : F(Func), M(M), Symtab(Symtab), SamplePGO(SamplePGO),
442 VirtualCSInfo(VirtualCSInfo),
443 VTableAddressPointOffsetVal(VTableAddressPointOffsetVal), ORE(ORE),
444 IgnoredBaseTypes(IgnoredBaseTypes) {}
445 IndirectCallPromoter(const IndirectCallPromoter &) = delete;
446 IndirectCallPromoter &operator=(const IndirectCallPromoter &) = delete;
447
448 bool processFunction(ProfileSummaryInfo *PSI);
449};
450
451} // end anonymous namespace
452
453bool IndirectCallPromoter::isValidTarget(uint64_t Target,
454 Function *TargetFunction,
455 const CallBase &CB, uint64_t Count) {
456 // Don't promote if the symbol is not defined in the module. This avoids
457 // creating a reference to a symbol that doesn't exist in the module
458 // This can happen when we compile with a sample profile collected from
459 // one binary but used for another, which may have profiled targets that
460 // aren't used in the new binary. We might have a declaration initially in
461 // the case where the symbol is globally dead in the binary and removed by
462 // ThinLTO.
463 using namespace ore;
464 if (TargetFunction == nullptr) {
465 LLVM_DEBUG(dbgs() << " Not promote: Cannot find the target\n");
466 ORE.emit(RemarkBuilder: [&]() {
467 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", &CB)
468 << "Cannot promote indirect call: target with md5sum "
469 << NV("target md5sum", Target)
470 << " not found (count=" << NV("Count", Count) << ")";
471 });
472 return false;
473 }
474 if (!ICPAllowDecls && TargetFunction->isDeclaration()) {
475 LLVM_DEBUG(dbgs() << " Not promote: target definition is not available\n");
476 ORE.emit(RemarkBuilder: [&]() {
477 return OptimizationRemarkMissed(DEBUG_TYPE, "NoTargetDef", &CB)
478 << "Do not promote indirect call: target with md5sum "
479 << NV("target md5sum", Target)
480 << " definition not available (count=" << ore::NV("Count", Count)
481 << ")";
482 });
483 return false;
484 }
485
486 const char *Reason = nullptr;
487 if (!isLegalToPromote(CB, Callee: TargetFunction, FailureReason: &Reason)) {
488
489 ORE.emit(RemarkBuilder: [&]() {
490 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", &CB)
491 << "Cannot promote indirect call to "
492 << NV("TargetFunction", TargetFunction)
493 << " (count=" << NV("Count", Count) << "): " << Reason;
494 });
495 return false;
496 }
497 return true;
498}
499
500// Indirect-call promotion heuristic. The direct targets are sorted based on
501// the count. Stop at the first target that is not promoted.
502std::vector<IndirectCallPromoter::PromotionCandidate>
503IndirectCallPromoter::getPromotionCandidatesForCallSite(
504 const CallBase &CB, ArrayRef<InstrProfValueData> ValueDataRef,
505 uint64_t TotalCount, uint32_t NumCandidates) {
506 std::vector<PromotionCandidate> Ret;
507
508 LLVM_DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << CB
509 << " Num_targets: " << ValueDataRef.size()
510 << " Num_candidates: " << NumCandidates << "\n");
511 NumOfPGOICallsites++;
512 if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
513 LLVM_DEBUG(dbgs() << " Skip: User options.\n");
514 return Ret;
515 }
516
517 for (uint32_t I = 0; I < NumCandidates; I++) {
518 uint64_t Count = ValueDataRef[I].Count;
519 assert(Count <= TotalCount);
520 (void)TotalCount;
521 uint64_t Target = ValueDataRef[I].Value;
522 LLVM_DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
523 << " Target_func: " << Target << "\n");
524
525 if (ICPInvokeOnly && isa<CallInst>(Val: CB)) {
526 LLVM_DEBUG(dbgs() << " Not promote: User options.\n");
527 ORE.emit(RemarkBuilder: [&]() {
528 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB)
529 << " Not promote: User options";
530 });
531 break;
532 }
533 if (ICPCallOnly && isa<InvokeInst>(Val: CB)) {
534 LLVM_DEBUG(dbgs() << " Not promote: User option.\n");
535 ORE.emit(RemarkBuilder: [&]() {
536 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB)
537 << " Not promote: User options";
538 });
539 break;
540 }
541 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
542 LLVM_DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
543 ORE.emit(RemarkBuilder: [&]() {
544 return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", &CB)
545 << " Not promote: Cutoff reached";
546 });
547 break;
548 }
549
550 Function *TargetFunction = Symtab->getFunction(FuncMD5Hash: Target);
551 if (!isValidTarget(Target, TargetFunction, CB, Count)) {
552 if (ICPAllowCandidateSkip)
553 continue;
554 else
555 break;
556 }
557
558 Ret.push_back(x: PromotionCandidate(TargetFunction, Count, I));
559 TotalCount -= Count;
560 }
561 return Ret;
562}
563
564Constant *IndirectCallPromoter::getOrCreateVTableAddressPointVar(
565 GlobalVariable *GV, uint64_t AddressPointOffset) {
566 auto [Iter, Inserted] =
567 VTableAddressPointOffsetVal[GV].try_emplace(Key: AddressPointOffset, Args: nullptr);
568 if (Inserted)
569 Iter->second = getVTableAddressPointOffset(VTable: GV, AddressPointOffset);
570 return Iter->second;
571}
572
573Instruction *IndirectCallPromoter::computeVTableInfos(
574 const CallBase *CB, VTableGUIDCountsMap &GUIDCountsMap,
575 std::vector<PromotionCandidate> &Candidates) {
576 if (!EnableVTableProfileUse)
577 return nullptr;
578
579 // Take the following code sequence as an example, here is how the code works
580 // @vtable1 = {[n x ptr] [... ptr @func1]}
581 // @vtable2 = {[m x ptr] [... ptr @func2]}
582 //
583 // %vptr = load ptr, ptr %d, !prof !0
584 // %0 = tail call i1 @llvm.type.test(ptr %vptr, metadata !"vtable1")
585 // tail call void @llvm.assume(i1 %0)
586 // %vfn = getelementptr inbounds ptr, ptr %vptr, i64 1
587 // %1 = load ptr, ptr %vfn
588 // call void %1(ptr %d), !prof !1
589 //
590 // !0 = !{!"VP", i32 2, i64 100, i64 123, i64 50, i64 456, i64 50}
591 // !1 = !{!"VP", i32 0, i64 100, i64 789, i64 50, i64 579, i64 50}
592 //
593 // Step 1. Find out the %vptr instruction for indirect call and use its !prof
594 // to populate `GUIDCountsMap`.
595 // Step 2. For each vtable-guid, look up its definition from symtab. LTO can
596 // make vtable definitions visible across modules.
597 // Step 3. Compute the byte offset of the virtual call, by adding vtable
598 // address point offset and function's offset relative to vtable address
599 // point. For each function candidate, this step tells us the vtable from
600 // which it comes from, and the vtable address point to compare %vptr with.
601
602 // Only virtual calls have virtual call site info.
603 auto Iter = VirtualCSInfo.find(Val: CB);
604 if (Iter == VirtualCSInfo.end())
605 return nullptr;
606
607 LLVM_DEBUG(dbgs() << "\nComputing vtable infos for callsite #"
608 << NumOfPGOICallsites << "\n");
609
610 const auto &VirtualCallInfo = Iter->second;
611 Instruction *VPtr = VirtualCallInfo.VPtr;
612
613 SmallDenseMap<Function *, int, 4> CalleeIndexMap;
614 for (size_t I = 0; I < Candidates.size(); I++)
615 CalleeIndexMap[Candidates[I].TargetFunction] = I;
616
617 uint64_t TotalVTableCount = 0;
618 auto VTableValueDataArray =
619 getValueProfDataFromInst(Inst: *VirtualCallInfo.VPtr, ValueKind: IPVK_VTableTarget,
620 MaxNumValueData: MaxNumVTableAnnotations, TotalC&: TotalVTableCount);
621 if (VTableValueDataArray.empty())
622 return VPtr;
623
624 // Compute the functions and counts from by each vtable.
625 for (const auto &V : VTableValueDataArray) {
626 uint64_t VTableVal = V.Value;
627 GUIDCountsMap[VTableVal] = V.Count;
628 GlobalVariable *VTableVar = Symtab->getGlobalVariable(MD5Hash: VTableVal);
629 if (!VTableVar) {
630 LLVM_DEBUG(dbgs() << " Cannot find vtable definition for " << VTableVal
631 << "; maybe the vtable isn't imported\n");
632 continue;
633 }
634
635 std::optional<uint64_t> MaybeAddressPointOffset =
636 getAddressPointOffset(VTableVar: *VTableVar, CompatibleType: VirtualCallInfo.CompatibleTypeStr);
637 if (!MaybeAddressPointOffset)
638 continue;
639
640 const uint64_t AddressPointOffset = *MaybeAddressPointOffset;
641
642 Function *Callee = nullptr;
643 std::tie(args&: Callee, args: std::ignore) = getFunctionAtVTableOffset(
644 GV: VTableVar, Offset: AddressPointOffset + VirtualCallInfo.FunctionOffset, M);
645 if (!Callee)
646 continue;
647 auto CalleeIndexIter = CalleeIndexMap.find(Val: Callee);
648 if (CalleeIndexIter == CalleeIndexMap.end())
649 continue;
650
651 auto &Candidate = Candidates[CalleeIndexIter->second];
652 // There should never be duplicate GUIDs in one !prof metdata, as this is
653 // an IR invariant enforced by the verifier. Assigning counters directly
654 // won't cause overwrite or counter loss.
655 Candidate.VTableGUIDAndCounts[VTableVal] = V.Count;
656 Candidate.AddressPoints.push_back(
657 Elt: getOrCreateVTableAddressPointVar(GV: VTableVar, AddressPointOffset));
658 }
659
660 return VPtr;
661}
662
663// Creates 'branch_weights' prof metadata using TrueWeight and FalseWeight.
664// Scales uint64_t counters down to uint32_t if necessary to prevent overflow.
665static MDNode *createBranchWeights(LLVMContext &Context, uint64_t TrueWeight,
666 uint64_t FalseWeight) {
667 MDBuilder MDB(Context);
668 uint64_t Scale = calculateCountScale(MaxCount: std::max(a: TrueWeight, b: FalseWeight));
669 return MDB.createBranchWeights(TrueWeight: scaleBranchCount(Count: TrueWeight, Scale),
670 FalseWeight: scaleBranchCount(Count: FalseWeight, Scale));
671}
672
673CallBase &llvm::pgo::promoteIndirectCall(CallBase &CB, Function *DirectCallee,
674 uint64_t Count, uint64_t TotalCount,
675 bool AttachProfToDirectCall,
676 OptimizationRemarkEmitter *ORE) {
677 CallBase &NewInst = promoteCallWithIfThenElse(
678 CB, Callee: DirectCallee,
679 BranchWeights: createBranchWeights(Context&: CB.getContext(), TrueWeight: Count, FalseWeight: TotalCount - Count));
680
681 if (AttachProfToDirectCall)
682 setFittedBranchWeights(I&: NewInst, Weights: {Count},
683 /*IsExpected=*/false);
684
685 using namespace ore;
686
687 if (ORE)
688 ORE->emit(RemarkBuilder: [&]() {
689 return OptimizationRemark(DEBUG_TYPE, "Promoted", &CB)
690 << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
691 << " with count " << NV("Count", Count) << " out of "
692 << NV("TotalCount", TotalCount);
693 });
694 return NewInst;
695}
696
697// Promote indirect-call to conditional direct-call for one callsite.
698bool IndirectCallPromoter::tryToPromoteWithFuncCmp(
699 CallBase &CB, Instruction *VPtr, ArrayRef<PromotionCandidate> Candidates,
700 uint64_t TotalCount, MutableArrayRef<InstrProfValueData> ICallProfDataRef,
701 uint32_t NumCandidates, VTableGUIDCountsMap &VTableGUIDCounts) {
702 uint32_t NumPromoted = 0;
703
704 for (const auto &C : Candidates) {
705 uint64_t FuncCount = C.Count;
706 pgo::promoteIndirectCall(CB, DirectCallee: C.TargetFunction, Count: FuncCount, TotalCount,
707 AttachProfToDirectCall: SamplePGO, ORE: &ORE);
708 assert(TotalCount >= FuncCount);
709 TotalCount -= FuncCount;
710 NumOfPGOICallPromotion++;
711 NumPromoted++;
712
713 // Update the count and this entry will be erased later.
714 ICallProfDataRef[C.Index].Count = 0;
715 if (!EnableVTableProfileUse || C.VTableGUIDAndCounts.empty())
716 continue;
717
718 // After a virtual call candidate gets promoted, update the vtable's counts
719 // proportionally. Each vtable-guid in `C.VTableGUIDAndCounts` represents
720 // a vtable from which the virtual call is loaded. Compute the sum and use
721 // 128-bit APInt to improve accuracy.
722 uint64_t SumVTableCount = 0;
723 for (const auto &[GUID, VTableCount] : C.VTableGUIDAndCounts)
724 SumVTableCount += VTableCount;
725
726 for (const auto &[GUID, VTableCount] : C.VTableGUIDAndCounts) {
727 APInt APFuncCount((unsigned)128, FuncCount, false /*signed*/);
728 APFuncCount *= VTableCount;
729 VTableGUIDCounts[GUID] -= APFuncCount.udiv(RHS: SumVTableCount).getZExtValue();
730 }
731 }
732 if (NumPromoted == 0)
733 return false;
734
735 assert(NumPromoted <= ICallProfDataRef.size() &&
736 "Number of promoted functions should not be greater than the number "
737 "of values in profile metadata");
738
739 updateFuncValueProfiles(CB, VDs: ICallProfDataRef, Sum: TotalCount, MaxMDCount: NumCandidates);
740 updateVPtrValueProfiles(VPtr, VTableGUIDCounts);
741 return true;
742}
743
744void IndirectCallPromoter::updateFuncValueProfiles(
745 CallBase &CB, MutableArrayRef<InstrProfValueData> CallVDs,
746 uint64_t TotalCount, uint32_t MaxMDCount) {
747 // First clear the existing !prof.
748 CB.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
749
750 // Sort value profiles by count in descending order.
751 llvm::stable_sort(Range&: CallVDs, C: [](const InstrProfValueData &LHS,
752 const InstrProfValueData &RHS) {
753 return LHS.Count > RHS.Count;
754 });
755 // Drop the <target-value, count> pair if count is zero.
756 ArrayRef<InstrProfValueData> VDs(
757 CallVDs.begin(),
758 llvm::upper_bound(Range&: CallVDs, Value: 0U,
759 C: [](uint64_t Count, const InstrProfValueData &ProfData) {
760 return ProfData.Count <= Count;
761 }));
762
763 // Annotate the remaining value profiles if counter is not zero.
764 if (TotalCount != 0)
765 annotateValueSite(M, Inst&: CB, VDs, Sum: TotalCount, ValueKind: IPVK_IndirectCallTarget,
766 MaxMDCount);
767}
768
769void IndirectCallPromoter::updateVPtrValueProfiles(
770 Instruction *VPtr, VTableGUIDCountsMap &VTableGUIDCounts) {
771 if (!EnableVTableProfileUse || VPtr == nullptr ||
772 !VPtr->getMetadata(KindID: LLVMContext::MD_prof))
773 return;
774 VPtr->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
775 std::vector<InstrProfValueData> VTableValueProfiles;
776 uint64_t TotalVTableCount = 0;
777 for (auto [GUID, Count] : VTableGUIDCounts) {
778 if (Count == 0)
779 continue;
780
781 VTableValueProfiles.push_back(x: {.Value: GUID, .Count: Count});
782 TotalVTableCount += Count;
783 }
784 llvm::sort(C&: VTableValueProfiles,
785 Comp: [](const InstrProfValueData &LHS, const InstrProfValueData &RHS) {
786 return LHS.Count > RHS.Count;
787 });
788
789 annotateValueSite(M, Inst&: *VPtr, VDs: VTableValueProfiles, Sum: TotalVTableCount,
790 ValueKind: IPVK_VTableTarget, MaxMDCount: VTableValueProfiles.size());
791}
792
793bool IndirectCallPromoter::tryToPromoteWithVTableCmp(
794 CallBase &CB, Instruction *VPtr, ArrayRef<PromotionCandidate> Candidates,
795 uint64_t TotalFuncCount, uint32_t NumCandidates,
796 MutableArrayRef<InstrProfValueData> ICallProfDataRef,
797 VTableGUIDCountsMap &VTableGUIDCounts) {
798 SmallVector<std::pair<uint32_t, uint64_t>, 4> PromotedFuncCount;
799
800 for (const auto &Candidate : Candidates) {
801 for (auto &[GUID, Count] : Candidate.VTableGUIDAndCounts)
802 VTableGUIDCounts[GUID] -= Count;
803
804 // 'OriginalBB' is the basic block of indirect call. After each candidate
805 // is promoted, a new basic block is created for the indirect fallback basic
806 // block and indirect call `CB` is moved into this new BB.
807 BasicBlock *OriginalBB = CB.getParent();
808 promoteCallWithVTableCmp(
809 CB, VPtr, Callee: Candidate.TargetFunction, AddressPoints: Candidate.AddressPoints,
810 BranchWeights: createBranchWeights(Context&: CB.getContext(), TrueWeight: Candidate.Count,
811 FalseWeight: TotalFuncCount - Candidate.Count));
812
813 int SinkCount = tryToSinkInstructions(OriginalBB, IndirectCallBB: CB.getParent());
814
815 ORE.emit(RemarkBuilder: [&]() {
816 OptimizationRemark Remark(DEBUG_TYPE, "Promoted", &CB);
817
818 const auto &VTableGUIDAndCounts = Candidate.VTableGUIDAndCounts;
819 Remark << "Promote indirect call to "
820 << ore::NV("DirectCallee", Candidate.TargetFunction)
821 << " with count " << ore::NV("Count", Candidate.Count)
822 << " out of " << ore::NV("TotalCount", TotalFuncCount) << ", sink "
823 << ore::NV("SinkCount", SinkCount)
824 << " instruction(s) and compare "
825 << ore::NV("VTable", VTableGUIDAndCounts.size())
826 << " vtable(s): {";
827
828 // Sort GUIDs so remark message is deterministic.
829 std::set<uint64_t> GUIDSet;
830 for (auto [GUID, Count] : VTableGUIDAndCounts)
831 GUIDSet.insert(x: GUID);
832 for (auto Iter = GUIDSet.begin(); Iter != GUIDSet.end(); Iter++) {
833 if (Iter != GUIDSet.begin())
834 Remark << ", ";
835 Remark << ore::NV("VTable", Symtab->getGlobalVariable(MD5Hash: *Iter));
836 }
837
838 Remark << "}";
839
840 return Remark;
841 });
842
843 PromotedFuncCount.push_back(Elt: {Candidate.Index, Candidate.Count});
844
845 assert(TotalFuncCount >= Candidate.Count &&
846 "Within one prof metadata, total count is the sum of counts from "
847 "individual <target, count> pairs");
848 // Use std::min since 'TotalFuncCount' is the saturated sum of individual
849 // counts, see
850 // https://github.com/llvm/llvm-project/blob/abedb3b8356d5d56f1c575c4f7682fba2cb19787/llvm/lib/ProfileData/InstrProf.cpp#L1281-L1288
851 TotalFuncCount -= std::min(a: TotalFuncCount, b: Candidate.Count);
852 NumOfPGOICallPromotion++;
853 }
854
855 if (PromotedFuncCount.empty())
856 return false;
857
858 // Update value profiles for 'CB' and 'VPtr', assuming that each 'CB' has a
859 // a distinct 'VPtr'.
860 // FIXME: When Clang `-fstrict-vtable-pointers` is enabled, a vtable might be
861 // used to load multiple virtual functions. The vtable profiles needs to be
862 // updated properly in that case (e.g, for each indirect call annotate both
863 // type profiles and function profiles in one !prof).
864 for (size_t I = 0; I < PromotedFuncCount.size(); I++) {
865 uint32_t Index = PromotedFuncCount[I].first;
866 ICallProfDataRef[Index].Count -=
867 std::max(a: PromotedFuncCount[I].second, b: ICallProfDataRef[Index].Count);
868 }
869 updateFuncValueProfiles(CB, CallVDs: ICallProfDataRef, TotalCount: TotalFuncCount, MaxMDCount: NumCandidates);
870 updateVPtrValueProfiles(VPtr, VTableGUIDCounts);
871 return true;
872}
873
874// Traverse all the indirect-call callsite and get the value profile
875// annotation to perform indirect-call promotion.
876bool IndirectCallPromoter::processFunction(ProfileSummaryInfo *PSI) {
877 bool Changed = false;
878 ICallPromotionAnalysis ICallAnalysis;
879 for (auto *CB : findIndirectCalls(F)) {
880 uint32_t NumCandidates;
881 uint64_t TotalCount;
882 auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
883 I: CB, TotalCount, NumCandidates);
884 if (!NumCandidates)
885 continue;
886 if (PSI && PSI->hasProfileSummary()) {
887 // Don't promote cold candidates.
888 if (PSI->isColdCount(C: TotalCount)) {
889 LLVM_DEBUG(dbgs() << "Don't promote the cold candidate: TotalCount="
890 << TotalCount << "\n");
891 continue;
892 }
893 // Only promote hot if ICPAllowHotOnly is true. ICP has its own cutoff
894 // threshold for hotness, which defaults to ProfileSummaryCutoffHot if
895 // unspecified.
896 if (ICPAllowHotOnly &&
897 !PSI->isHotCountNthPercentile(PercentileCutoff: HotFuncCutoffForICP == -1
898 ? ProfileSummaryCutoffHot
899 : HotFuncCutoffForICP,
900 C: TotalCount)) {
901 LLVM_DEBUG(dbgs() << "Don't promote the non-hot candidate: TotalCount="
902 << TotalCount << "\n");
903 continue;
904 }
905 }
906
907 auto PromotionCandidates = getPromotionCandidatesForCallSite(
908 CB: *CB, ValueDataRef: ICallProfDataRef, TotalCount, NumCandidates);
909
910 VTableGUIDCountsMap VTableGUIDCounts;
911 Instruction *VPtr =
912 computeVTableInfos(CB, GUIDCountsMap&: VTableGUIDCounts, Candidates&: PromotionCandidates);
913
914 if (isProfitableToCompareVTables(CB: *CB, Candidates: PromotionCandidates))
915 Changed |= tryToPromoteWithVTableCmp(CB&: *CB, VPtr, Candidates: PromotionCandidates,
916 TotalFuncCount: TotalCount, NumCandidates,
917 ICallProfDataRef, VTableGUIDCounts);
918 else
919 Changed |= tryToPromoteWithFuncCmp(CB&: *CB, VPtr, Candidates: PromotionCandidates,
920 TotalCount, ICallProfDataRef,
921 NumCandidates, VTableGUIDCounts);
922 }
923 return Changed;
924}
925
926// TODO: Return false if the function addressing and vtable load instructions
927// cannot sink to indirect fallback.
928bool IndirectCallPromoter::isProfitableToCompareVTables(
929 const CallBase &CB, ArrayRef<PromotionCandidate> Candidates) {
930 if (!EnableVTableProfileUse || Candidates.empty())
931 return false;
932 LLVM_DEBUG(dbgs() << "\nEvaluating vtable profitability for callsite #"
933 << NumOfPGOICallsites << CB << "\n");
934 const size_t CandidateSize = Candidates.size();
935 for (size_t I = 0; I < CandidateSize; I++) {
936 auto &Candidate = Candidates[I];
937 auto &VTableGUIDAndCounts = Candidate.VTableGUIDAndCounts;
938
939 LLVM_DEBUG({
940 dbgs() << " Candidate " << I << " FunctionCount: " << Candidate.Count
941 << ", VTableCounts:";
942 for (const auto &[GUID, Count] : VTableGUIDAndCounts)
943 dbgs() << " {" << Symtab->getGlobalVariable(GUID)->getName() << ", "
944 << Count << "}";
945 dbgs() << "\n";
946 });
947
948 uint64_t CandidateVTableCount = 0;
949
950 for (auto &[GUID, Count] : VTableGUIDAndCounts) {
951 CandidateVTableCount += Count;
952
953 if (shouldSkipVTable(VTableGUID: GUID))
954 return false;
955 }
956
957 if (CandidateVTableCount < Candidate.Count * ICPVTablePercentageThreshold) {
958 LLVM_DEBUG(
959 dbgs() << " function count " << Candidate.Count
960 << " and its vtable sum count " << CandidateVTableCount
961 << " have discrepancies. Bail out vtable comparison.\n");
962 return false;
963 }
964
965 // 'MaxNumVTable' limits the number of vtables to make vtable comparison
966 // profitable. Comparing multiple vtables for one function candidate will
967 // insert additional instructions on the hot path, and allowing more than
968 // one vtable for non last candidates may or may not elongate the dependency
969 // chain for the subsequent candidates. Set its value to 1 for non-last
970 // candidate and allow option to override it for the last candidate.
971 int MaxNumVTable = 1;
972 if (I == CandidateSize - 1)
973 MaxNumVTable = ICPMaxNumVTableLastCandidate;
974
975 if ((int)Candidate.AddressPoints.size() > MaxNumVTable) {
976 LLVM_DEBUG(dbgs() << " allow at most " << MaxNumVTable << " and got "
977 << Candidate.AddressPoints.size()
978 << " vtables. Bail out for vtable comparison.\n");
979 return false;
980 }
981 }
982
983 return true;
984}
985
986bool IndirectCallPromoter::shouldSkipVTable(uint64_t VTableGUID) {
987 if (IgnoredBaseTypes.empty())
988 return false;
989
990 auto *VTableVar = Symtab->getGlobalVariable(MD5Hash: VTableGUID);
991
992 assert(VTableVar && "VTableVar must exist for GUID in VTableGUIDAndCounts");
993
994 SmallVector<MDNode *, 2> Types;
995 VTableVar->getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
996
997 for (auto *Type : Types)
998 if (auto *TypeId = dyn_cast<MDString>(Val: Type->getOperand(I: 1).get()))
999 if (IgnoredBaseTypes.contains(V: TypeId->getString())) {
1000 LLVM_DEBUG(dbgs() << " vtable profiles should be ignored. Bail "
1001 "out of vtable comparison.");
1002 return true;
1003 }
1004 return false;
1005}
1006
1007// For virtual calls in the module, collect per-callsite information which will
1008// be used to associate an ICP candidate with a vtable and a specific function
1009// in the vtable. With type intrinsics (llvm.type.test), we can find virtual
1010// calls in a compile-time efficient manner (by iterating its users) and more
1011// importantly use the compatible type later to figure out the function byte
1012// offset relative to the start of vtables.
1013static void
1014computeVirtualCallSiteTypeInfoMap(Module &M, ModuleAnalysisManager &MAM,
1015 VirtualCallSiteTypeInfoMap &VirtualCSInfo) {
1016 // Right now only llvm.type.test is used to find out virtual call sites.
1017 // With ThinLTO and whole-program-devirtualization, llvm.type.test and
1018 // llvm.public.type.test are emitted, and llvm.public.type.test is either
1019 // refined to llvm.type.test or dropped before indirect-call-promotion pass.
1020 //
1021 // FIXME: For fullLTO with VFE, `llvm.type.checked.load intrinsic` is emitted.
1022 // Find out virtual calls by looking at users of llvm.type.checked.load in
1023 // that case.
1024 Function *TypeTestFunc =
1025 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
1026 if (!TypeTestFunc || TypeTestFunc->use_empty())
1027 return;
1028
1029 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1030 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
1031 return FAM.getResult<DominatorTreeAnalysis>(IR&: F);
1032 };
1033 // Iterate all type.test calls to find all indirect calls.
1034 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc->uses())) {
1035 auto *CI = dyn_cast<CallInst>(Val: U.getUser());
1036 if (!CI)
1037 continue;
1038 auto *TypeMDVal = cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
1039 if (!TypeMDVal)
1040 continue;
1041 auto *CompatibleTypeId = dyn_cast<MDString>(Val: TypeMDVal->getMetadata());
1042 if (!CompatibleTypeId)
1043 continue;
1044
1045 // Find out all devirtualizable call sites given a llvm.type.test
1046 // intrinsic call.
1047 SmallVector<DevirtCallSite, 1> DevirtCalls;
1048 SmallVector<CallInst *, 1> Assumes;
1049 auto &DT = LookupDomTree(*CI->getFunction());
1050 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1051
1052 for (auto &DevirtCall : DevirtCalls) {
1053 CallBase &CB = DevirtCall.CB;
1054 // Given an indirect call, try find the instruction which loads a
1055 // pointer to virtual table.
1056 Instruction *VTablePtr =
1057 PGOIndirectCallVisitor::tryGetVTableInstruction(CB: &CB);
1058 if (!VTablePtr)
1059 continue;
1060 VirtualCSInfo[&CB] = {.FunctionOffset: DevirtCall.Offset, .VPtr: VTablePtr,
1061 .CompatibleTypeStr: CompatibleTypeId->getString()};
1062 }
1063 }
1064}
1065
1066// A wrapper function that does the actual work.
1067static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI, bool InLTO,
1068 bool SamplePGO, ModuleAnalysisManager &MAM) {
1069 if (DisableICP)
1070 return false;
1071 InstrProfSymtab Symtab;
1072 if (Error E = Symtab.create(M, InLTO)) {
1073 std::string SymtabFailure = toString(E: std::move(E));
1074 M.getContext().emitError(ErrorStr: "Failed to create symtab: " + SymtabFailure);
1075 return false;
1076 }
1077 bool Changed = false;
1078 VirtualCallSiteTypeInfoMap VirtualCSInfo;
1079
1080 DenseSet<StringRef> IgnoredBaseTypes;
1081
1082 if (EnableVTableProfileUse) {
1083 computeVirtualCallSiteTypeInfoMap(M, MAM, VirtualCSInfo);
1084
1085 IgnoredBaseTypes.insert_range(R&: ICPIgnoredBaseTypes);
1086 }
1087
1088 // VTableAddressPointOffsetVal stores the vtable address points. The vtable
1089 // address point of a given <vtable, address point offset> is static (doesn't
1090 // change after being computed once).
1091 // IndirectCallPromoter::getOrCreateVTableAddressPointVar creates the map
1092 // entry the first time a <vtable, offset> pair is seen, as
1093 // promoteIndirectCalls processes an IR module and calls IndirectCallPromoter
1094 // repeatedly on each function.
1095 VTableAddressPointOffsetValMap VTableAddressPointOffsetVal;
1096
1097 for (auto &F : M) {
1098 if (F.isDeclaration() || F.hasOptNone())
1099 continue;
1100
1101 auto &FAM =
1102 MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1103 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
1104
1105 IndirectCallPromoter CallPromoter(F, M, &Symtab, SamplePGO, VirtualCSInfo,
1106 VTableAddressPointOffsetVal,
1107 IgnoredBaseTypes, ORE);
1108 bool FuncChanged = CallPromoter.processFunction(PSI);
1109 if (ICPDUMPAFTER && FuncChanged) {
1110 LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
1111 LLVM_DEBUG(dbgs() << "\n");
1112 }
1113 Changed |= FuncChanged;
1114 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
1115 LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n");
1116 break;
1117 }
1118 }
1119 return Changed;
1120}
1121
1122PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
1123 ModuleAnalysisManager &MAM) {
1124 ProfileSummaryInfo *PSI = &MAM.getResult<ProfileSummaryAnalysis>(IR&: M);
1125
1126 if (!promoteIndirectCalls(M, PSI, InLTO: InLTO | ICPLTOMode,
1127 SamplePGO: SamplePGO | ICPSamplePGOMode, MAM))
1128 return PreservedAnalyses::all();
1129
1130 return PreservedAnalyses::none();
1131}
1132