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