1//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
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 pass implements whole program optimization of virtual calls in cases
10// where we know (via !type metadata) that the list of callees is fixed. This
11// includes the following:
12// - Single implementation devirtualization: if a virtual call has a single
13// possible callee, replace all calls with a direct call to that callee.
14// - Virtual constant propagation: if the virtual function's return type is an
15// integer <=64 bits and all possible callees are readnone, for each class and
16// each list of constant arguments: evaluate the function, store the return
17// value alongside the virtual table, and rewrite each virtual call as a load
18// from the virtual table.
19// - Uniform return value optimization: if the conditions for virtual constant
20// propagation hold and each function returns the same constant value, replace
21// each virtual call with that constant.
22// - Unique return value optimization for i1 return values: if the conditions
23// for virtual constant propagation hold and a single vtable's function
24// returns 0, or a single vtable's function returns 1, replace each virtual
25// call with a comparison of the vptr against that vtable's address.
26//
27// This pass is intended to be used during the regular/thin and non-LTO
28// pipelines:
29//
30// During regular LTO, the pass determines the best optimization for each
31// virtual call and applies the resolutions directly to virtual calls that are
32// eligible for virtual call optimization (i.e. calls that use either of the
33// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics).
34//
35// During hybrid Regular/ThinLTO, the pass operates in two phases:
36// - Export phase: this is run during the thin link over a single merged module
37// that contains all vtables with !type metadata that participate in the link.
38// The pass computes a resolution for each virtual call and stores it in the
39// type identifier summary.
40// - Import phase: this is run during the thin backends over the individual
41// modules. The pass applies the resolutions previously computed during the
42// import phase to each eligible virtual call.
43//
44// During ThinLTO, the pass operates in two phases:
45// - Export phase: this is run during the thin link over the index which
46// contains a summary of all vtables with !type metadata that participate in
47// the link. It computes a resolution for each virtual call and stores it in
48// the type identifier summary. Only single implementation devirtualization
49// is supported.
50// - Import phase: (same as with hybrid case above).
51//
52// During Speculative devirtualization mode -not restricted to LTO-:
53// - The pass applies speculative devirtualization without requiring any type of
54// visibility.
55// - Skips other features like virtual constant propagation, uniform return
56// value optimization, unique return value optimization and branch funnels as
57// they need LTO.
58// - This mode is enabled via 'devirtualize-speculatively' flag.
59//
60//===----------------------------------------------------------------------===//
61
62#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
63#include "IPOOptions.h"
64#include "llvm/ADT/ArrayRef.h"
65#include "llvm/ADT/DenseMap.h"
66#include "llvm/ADT/DenseMapInfo.h"
67#include "llvm/ADT/DenseSet.h"
68#include "llvm/ADT/MapVector.h"
69#include "llvm/ADT/STLExtras.h"
70#include "llvm/ADT/SmallPtrSet.h"
71#include "llvm/ADT/SmallVector.h"
72#include "llvm/ADT/Statistic.h"
73#include "llvm/Analysis/AssumptionCache.h"
74#include "llvm/Analysis/BasicAliasAnalysis.h"
75#include "llvm/Analysis/BlockFrequencyInfo.h"
76#include "llvm/Analysis/ModuleSummaryAnalysis.h"
77#include "llvm/Analysis/OptimizationRemarkEmitter.h"
78#include "llvm/Analysis/ProfileSummaryInfo.h"
79#include "llvm/Analysis/TypeMetadataUtils.h"
80#include "llvm/Bitcode/BitcodeReader.h"
81#include "llvm/Bitcode/BitcodeWriter.h"
82#include "llvm/IR/Constants.h"
83#include "llvm/IR/DataLayout.h"
84#include "llvm/IR/DebugLoc.h"
85#include "llvm/IR/DerivedTypes.h"
86#include "llvm/IR/DiagnosticInfo.h"
87#include "llvm/IR/Dominators.h"
88#include "llvm/IR/Function.h"
89#include "llvm/IR/GlobalAlias.h"
90#include "llvm/IR/GlobalVariable.h"
91#include "llvm/IR/IRBuilder.h"
92#include "llvm/IR/InstrTypes.h"
93#include "llvm/IR/Instruction.h"
94#include "llvm/IR/Instructions.h"
95#include "llvm/IR/Intrinsics.h"
96#include "llvm/IR/LLVMContext.h"
97#include "llvm/IR/MDBuilder.h"
98#include "llvm/IR/Metadata.h"
99#include "llvm/IR/Module.h"
100#include "llvm/IR/ModuleSummaryIndexYAML.h"
101#include "llvm/IR/PassManager.h"
102#include "llvm/IR/ProfDataUtils.h"
103#include "llvm/ProfileData/InstrProf.h"
104#include "llvm/Support/Casting.h"
105#include "llvm/Support/CommandLine.h"
106#include "llvm/Support/DebugCounter.h"
107#include "llvm/Support/Errc.h"
108#include "llvm/Support/Error.h"
109#include "llvm/Support/FileSystem.h"
110#include "llvm/Support/GlobPattern.h"
111#include "llvm/Support/TimeProfiler.h"
112#include "llvm/TargetParser/Triple.h"
113#include "llvm/Transforms/IPO.h"
114#include "llvm/Transforms/IPO/FunctionAttrs.h"
115#include "llvm/Transforms/Utils/BasicBlockUtils.h"
116#include "llvm/Transforms/Utils/CallPromotionUtils.h"
117#include "llvm/Transforms/Utils/Evaluator.h"
118#include <algorithm>
119#include <cmath>
120#include <cstddef>
121#include <limits>
122#include <map>
123#include <set>
124#include <string>
125
126using namespace llvm;
127using namespace wholeprogramdevirt;
128
129#define DEBUG_TYPE "wholeprogramdevirt"
130
131STATISTIC(NumDevirtTargets, "Number of whole program devirtualization targets");
132STATISTIC(NumSingleImpl, "Number of single implementation devirtualizations");
133STATISTIC(NumBranchFunnel, "Number of branch funnels");
134STATISTIC(NumUniformRetVal, "Number of uniform return value optimizations");
135STATISTIC(NumUniqueRetVal, "Number of unique return value optimizations");
136STATISTIC(NumVirtConstProp1Bit,
137 "Number of 1 bit virtual constant propagations");
138STATISTIC(NumVirtConstProp, "Number of virtual constant propagations");
139DEBUG_COUNTER(CallsToDevirt, "calls-to-devirt",
140 "Controls how many calls should be devirtualized.");
141
142namespace llvm {
143
144static cl::opt<bool>
145 PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,
146 cl::desc("Print index-based devirtualization messages"));
147
148/// Provide a way to force enable whole program visibility in tests.
149/// This is needed to support legacy tests that don't contain
150/// !vcall_visibility metadata (the mere presense of type tests
151/// previously implied hidden visibility).
152static cl::opt<bool>
153 WholeProgramVisibility("whole-program-visibility", cl::Hidden,
154 cl::desc("Enable whole program visibility"));
155
156/// Provide a way to force disable whole program for debugging or workarounds,
157/// when enabled via the linker.
158static cl::opt<bool> DisableWholeProgramVisibility(
159 "disable-whole-program-visibility", cl::Hidden,
160 cl::desc("Disable whole program visibility (overrides enabling options)"));
161
162/// Provide way to prevent certain function from being devirtualized
163static cl::list<std::string>
164 SkipFunctionNames("wholeprogramdevirt-skip",
165 cl::desc("Prevent function(s) from being devirtualized"),
166 cl::Hidden, cl::CommaSeparated);
167
168} // end namespace llvm
169
170/// With Clang, a pure virtual class's deleting destructor is emitted as a
171/// `llvm.trap` intrinsic followed by an unreachable IR instruction. In the
172/// context of whole program devirtualization, the deleting destructor of a pure
173/// virtual class won't be invoked by the source code so safe to skip as a
174/// devirtualize target.
175///
176/// However, not all unreachable functions are safe to skip. In some cases, the
177/// program intends to run such functions and terminate, for instance, a unit
178/// test may run a death test. A non-test program might (or allowed to) invoke
179/// such functions to report failures (whether/when it's a good practice or not
180/// is a different topic).
181///
182/// This option is enabled to keep an unreachable function as a possible
183/// devirtualize target to conservatively keep the program behavior.
184///
185/// TODO: Make a pure virtual class's deleting destructor precisely identifiable
186/// in Clang's codegen for more devirtualization in LLVM.
187static cl::opt<bool> WholeProgramDevirtKeepUnreachableFunction(
188 "wholeprogramdevirt-keep-unreachable-function",
189 cl::desc("Regard unreachable functions as possible devirtualize targets."),
190 cl::Hidden, cl::init(Val: true));
191
192namespace {
193struct PatternList {
194 std::vector<GlobPattern> Patterns;
195 template <class T> void init(const T &StringList) {
196 for (const auto &S : StringList)
197 if (Expected<GlobPattern> Pat = GlobPattern::create(Pat: S))
198 Patterns.push_back(x: std::move(*Pat));
199 }
200 bool match(StringRef S) {
201 for (const GlobPattern &P : Patterns)
202 if (P.match(S))
203 return true;
204 return false;
205 }
206};
207} // namespace
208
209// Find the minimum offset that we may store a value of size Size bits at. If
210// IsAfter is set, look for an offset before the object, otherwise look for an
211// offset after the object.
212uint64_t
213wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
214 bool IsAfter, uint64_t Size) {
215 // Find a minimum offset taking into account only vtable sizes.
216 uint64_t MinByte = 0;
217 for (const VirtualCallTarget &Target : Targets) {
218 if (IsAfter)
219 MinByte = std::max(a: MinByte, b: Target.minAfterBytes());
220 else
221 MinByte = std::max(a: MinByte, b: Target.minBeforeBytes());
222 }
223
224 // Build a vector of arrays of bytes covering, for each target, a slice of the
225 // used region (see AccumBitVector::BytesUsed in
226 // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
227 // this aligns the used regions to start at MinByte.
228 //
229 // In this example, A, B and C are vtables, # is a byte already allocated for
230 // a virtual function pointer, AAAA... (etc.) are the used regions for the
231 // vtables and Offset(X) is the value computed for the Offset variable below
232 // for X.
233 //
234 // Offset(A)
235 // | |
236 // |MinByte
237 // A: ################AAAAAAAA|AAAAAAAA
238 // B: ########BBBBBBBBBBBBBBBB|BBBB
239 // C: ########################|CCCCCCCCCCCCCCCC
240 // | Offset(B) |
241 //
242 // This code produces the slices of A, B and C that appear after the divider
243 // at MinByte.
244 std::vector<ArrayRef<uint8_t>> Used;
245 for (const VirtualCallTarget &Target : Targets) {
246 ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
247 : Target.TM->Bits->Before.BytesUsed;
248 uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
249 : MinByte - Target.minBeforeBytes();
250
251 // Disregard used regions that are smaller than Offset. These are
252 // effectively all-free regions that do not need to be checked.
253 if (VTUsed.size() > Offset)
254 Used.push_back(x: VTUsed.slice(N: Offset));
255 }
256
257 if (Size == 1) {
258 // Find a free bit in each member of Used.
259 for (unsigned I = 0;; ++I) {
260 uint8_t BitsUsed = 0;
261 for (auto &&B : Used)
262 if (I < B.size())
263 BitsUsed |= B[I];
264 if (BitsUsed != 0xff)
265 return (MinByte + I) * 8 + llvm::countr_zero(Val: uint8_t(~BitsUsed));
266 }
267 } else {
268 // Find a free (Size/8) byte region in each member of Used.
269 // FIXME: see if alignment helps.
270 for (unsigned I = 0;; ++I) {
271 for (auto &&B : Used) {
272 unsigned Byte = 0;
273 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
274 if (B[I + Byte])
275 goto NextI;
276 ++Byte;
277 }
278 }
279 // Rounding up ensures the constant is always stored at address we
280 // can directly load from without misalignment.
281 return alignTo(Value: (MinByte + I) * 8, Align: Size);
282 NextI:;
283 }
284 }
285}
286
287void wholeprogramdevirt::setBeforeReturnValues(
288 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
289 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
290 if (BitWidth == 1)
291 OffsetByte = -(AllocBefore / 8 + 1);
292 else
293 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
294 OffsetBit = AllocBefore % 8;
295
296 for (VirtualCallTarget &Target : Targets) {
297 if (BitWidth == 1)
298 Target.setBeforeBit(AllocBefore);
299 else
300 Target.setBeforeBytes(Pos: AllocBefore, Size: (BitWidth + 7) / 8);
301 }
302}
303
304void wholeprogramdevirt::setAfterReturnValues(
305 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
306 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
307 if (BitWidth == 1)
308 OffsetByte = AllocAfter / 8;
309 else
310 OffsetByte = (AllocAfter + 7) / 8;
311 OffsetBit = AllocAfter % 8;
312
313 for (VirtualCallTarget &Target : Targets) {
314 if (BitWidth == 1)
315 Target.setAfterBit(AllocAfter);
316 else
317 Target.setAfterBytes(Pos: AllocAfter, Size: (BitWidth + 7) / 8);
318 }
319}
320
321VirtualCallTarget::VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM)
322 : Fn(Fn), TM(TM),
323 IsBigEndian(Fn->getDataLayout().isBigEndian()),
324 WasDevirt(false) {}
325
326namespace {
327
328// A slot in a set of virtual tables. The TypeID identifies the set of virtual
329// tables, and the ByteOffset is the offset in bytes from the address point to
330// the virtual function pointer.
331struct VTableSlot {
332 Metadata *TypeID;
333 uint64_t ByteOffset;
334};
335
336} // end anonymous namespace
337
338template <> struct llvm::DenseMapInfo<VTableSlot> {
339 static unsigned getHashValue(const VTableSlot &I) {
340 return DenseMapInfo<Metadata *>::getHashValue(PtrVal: I.TypeID) ^
341 DenseMapInfo<uint64_t>::getHashValue(Val: I.ByteOffset);
342 }
343 static bool isEqual(const VTableSlot &LHS,
344 const VTableSlot &RHS) {
345 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
346 }
347};
348
349template <> struct llvm::DenseMapInfo<VTableSlotSummary> {
350 static unsigned getHashValue(const VTableSlotSummary &I) {
351 return DenseMapInfo<StringRef>::getHashValue(Val: I.TypeID) ^
352 DenseMapInfo<uint64_t>::getHashValue(Val: I.ByteOffset);
353 }
354 static bool isEqual(const VTableSlotSummary &LHS,
355 const VTableSlotSummary &RHS) {
356 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
357 }
358};
359
360// Returns true if the function must be unreachable based on ValueInfo.
361//
362// In particular, identifies a function as unreachable in the following
363// conditions
364// 1) All summaries are live.
365// 2) All function summaries indicate it's unreachable
366// 3) There is no non-function with the same GUID (which is rare)
367static bool mustBeUnreachableFunction(ValueInfo TheFnVI) {
368 if (WholeProgramDevirtKeepUnreachableFunction)
369 return false;
370
371 if ((!TheFnVI) || TheFnVI.getSummaryList().empty()) {
372 // Returns false if ValueInfo is absent, or the summary list is empty
373 // (e.g., function declarations).
374 return false;
375 }
376
377 for (const auto &Summary : TheFnVI.getSummaryList()) {
378 // Conservatively returns false if any non-live functions are seen.
379 // In general either all summaries should be live or all should be dead.
380 if (!Summary->isLive())
381 return false;
382 if (auto *FS = dyn_cast<FunctionSummary>(Val: Summary->getBaseObject())) {
383 if (!FS->fflags().MustBeUnreachable)
384 return false;
385 }
386 // Be conservative if a non-function has the same GUID (which is rare).
387 else
388 return false;
389 }
390 // All function summaries are live and all of them agree that the function is
391 // unreachble.
392 return true;
393}
394
395namespace {
396// A virtual call site. VTable is the loaded virtual table pointer, and CS is
397// the indirect virtual call.
398struct VirtualCallSite {
399 Value *VTable = nullptr;
400 CallBase &CB;
401
402 // If non-null, this field points to the associated unsafe use count stored in
403 // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
404 // of that field for details.
405 unsigned *NumUnsafeUses = nullptr;
406
407 void
408 emitRemark(const StringRef OptName, const StringRef TargetName,
409 function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter) {
410 Function *F = CB.getCaller();
411 DebugLoc DLoc = CB.getDebugLoc();
412 BasicBlock *Block = CB.getParent();
413
414 using namespace ore;
415 OREGetter(*F).emit(OptDiag: OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
416 << NV("Optimization", OptName)
417 << ": devirtualized a call to "
418 << NV("FunctionName", TargetName));
419 }
420
421 void replaceAndErase(
422 const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
423 function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter,
424 Value *New) {
425 if (RemarksEnabled)
426 emitRemark(OptName, TargetName, OREGetter);
427 CB.replaceAllUsesWith(V: New);
428 if (auto *II = dyn_cast<InvokeInst>(Val: &CB)) {
429 UncondBrInst::Create(Target: II->getNormalDest(), InsertBefore: CB.getIterator());
430 II->getUnwindDest()->removePredecessor(Pred: II->getParent());
431 }
432 CB.eraseFromParent();
433 // This use is no longer unsafe.
434 if (NumUnsafeUses)
435 --*NumUnsafeUses;
436 }
437};
438
439// Call site information collected for a specific VTableSlot and possibly a list
440// of constant integer arguments. The grouping by arguments is handled by the
441// VTableSlotInfo class.
442struct CallSiteInfo {
443 /// The set of call sites for this slot. Used during regular LTO and the
444 /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
445 /// call sites that appear in the merged module itself); in each of these
446 /// cases we are directly operating on the call sites at the IR level.
447 std::vector<VirtualCallSite> CallSites;
448
449 /// Whether all call sites represented by this CallSiteInfo, including those
450 /// in summaries, have been devirtualized. This starts off as true because a
451 /// default constructed CallSiteInfo represents no call sites.
452 ///
453 /// If at the end of the pass there are still undevirtualized calls, we will
454 /// need to add a use of llvm.type.test to each of the function summaries in
455 /// the vector.
456 bool AllCallSitesDevirted = true;
457
458 // These fields are used during the export phase of ThinLTO and reflect
459 // information collected from function summaries.
460
461 /// CFI-specific: a vector containing the list of function summaries that use
462 /// the llvm.type.checked.load intrinsic and therefore will require
463 /// resolutions for llvm.type.test in order to implement CFI checks if
464 /// devirtualization was unsuccessful.
465 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
466
467 /// A vector containing the list of function summaries that use
468 /// assume(llvm.type.test).
469 std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
470
471 bool isExported() const {
472 return !SummaryTypeCheckedLoadUsers.empty() ||
473 !SummaryTypeTestAssumeUsers.empty();
474 }
475
476 void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
477 SummaryTypeCheckedLoadUsers.push_back(x: FS);
478 AllCallSitesDevirted = false;
479 }
480
481 void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
482 SummaryTypeTestAssumeUsers.push_back(x: FS);
483 AllCallSitesDevirted = false;
484 }
485
486 void markDevirt() { AllCallSitesDevirted = true; }
487};
488
489// Call site information collected for a specific VTableSlot.
490struct VTableSlotInfo {
491 // The set of call sites which do not have all constant integer arguments
492 // (excluding "this").
493 CallSiteInfo CSInfo;
494
495 // The set of call sites with all constant integer arguments (excluding
496 // "this"), grouped by argument list.
497 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
498
499 void addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses);
500
501private:
502 CallSiteInfo &findCallSiteInfo(CallBase &CB);
503};
504
505CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) {
506 std::vector<uint64_t> Args;
507 auto *CBType = dyn_cast<IntegerType>(Val: CB.getType());
508 if (!CBType || CBType->getBitWidth() > 64 || CB.arg_empty())
509 return CSInfo;
510 for (auto &&Arg : drop_begin(RangeOrContainer: CB.args())) {
511 auto *CI = dyn_cast<ConstantInt>(Val&: Arg);
512 if (!CI || CI->getBitWidth() > 64)
513 return CSInfo;
514 Args.push_back(x: CI->getZExtValue());
515 }
516 return ConstCSInfo[Args];
517}
518
519void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB,
520 unsigned *NumUnsafeUses) {
521 auto &CSI = findCallSiteInfo(CB);
522 CSI.AllCallSitesDevirted = false;
523 CSI.CallSites.push_back(x: {.VTable: VTable, .CB: CB, .NumUnsafeUses: NumUnsafeUses});
524}
525
526struct DevirtModule {
527 const IPOOptions &Opts;
528 Module &M;
529 ModuleAnalysisManager &MAM;
530 FunctionAnalysisManager &FAM;
531
532 ModuleSummaryIndex *const ExportSummary;
533 const ModuleSummaryIndex *const ImportSummary;
534
535 IntegerType *const Int8Ty;
536 PointerType *const Int8PtrTy;
537 IntegerType *const Int32Ty;
538 IntegerType *const Int64Ty;
539 IntegerType *const IntPtrTy;
540 /// Sizeless array type, used for imported vtables. This provides a signal
541 /// to analyzers that these imports may alias, as they do for example
542 /// when multiple unique return values occur in the same vtable.
543 ArrayType *const Int8Arr0Ty;
544
545 const bool RemarksEnabled;
546 std::function<OptimizationRemarkEmitter &(Function &)> OREGetter;
547 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
548
549 // Calls that have already been optimized. We may add a call to multiple
550 // VTableSlotInfos if vtable loads are coalesced and need to make sure not to
551 // optimize a call more than once.
552 SmallPtrSet<CallBase *, 8> OptimizedCalls;
553
554 // Store calls that had their ptrauth bundle removed. They are to be deleted
555 // at the end of the optimization.
556 SmallVector<CallBase *, 8> CallsWithPtrAuthBundleRemoved;
557
558 // This map keeps track of the number of "unsafe" uses of a loaded function
559 // pointer. The key is the associated llvm.type.test intrinsic call generated
560 // by this pass. An unsafe use is one that calls the loaded function pointer
561 // directly. Every time we eliminate an unsafe use (for example, by
562 // devirtualizing it or by applying virtual constant propagation), we
563 // decrement the value stored in this map. If a value reaches zero, we can
564 // eliminate the type check by RAUWing the associated llvm.type.test call with
565 // true.
566 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
567 PatternList FunctionsToSkip;
568
569 const bool DevirtSpeculatively;
570 DevirtModule(Module &M, ModuleAnalysisManager &MAM,
571 ModuleSummaryIndex *ExportSummary,
572 const ModuleSummaryIndex *ImportSummary,
573 bool DevirtSpeculatively)
574 : Opts(getIPOOptions(M)), M(M), MAM(MAM),
575 FAM(MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager()),
576 ExportSummary(ExportSummary), ImportSummary(ImportSummary),
577 Int8Ty(Type::getInt8Ty(C&: M.getContext())),
578 Int8PtrTy(PointerType::getUnqual(C&: M.getContext())),
579 Int32Ty(Type::getInt32Ty(C&: M.getContext())),
580 Int64Ty(Type::getInt64Ty(C&: M.getContext())),
581 IntPtrTy(M.getDataLayout().getIntPtrType(C&: M.getContext(), AddressSpace: 0)),
582 Int8Arr0Ty(ArrayType::get(ElementType: Type::getInt8Ty(C&: M.getContext()), NumElements: 0)),
583 RemarksEnabled(areRemarksEnabled()),
584 OREGetter([&](Function &F) -> OptimizationRemarkEmitter & {
585 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
586 }),
587 DevirtSpeculatively(
588 DevirtSpeculatively ||
589 (ImportSummary && ImportSummary->withSpeculativeDevirt())) {
590 assert(!(ExportSummary && ImportSummary));
591 FunctionsToSkip.init(StringList: SkipFunctionNames);
592 }
593
594 bool areRemarksEnabled();
595
596 void
597 scanTypeTestUsers(Function *TypeTestFunc,
598 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
599 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
600
601 void buildTypeIdentifierMap(
602 std::vector<VTableBits> &Bits,
603 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
604
605 bool tryFindVirtualCallTargets(
606 std::vector<VirtualCallTarget> &TargetsForSlot,
607 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset,
608 ModuleSummaryIndex *ExportSummary, bool &HasPublicTarget);
609
610 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
611 bool HasPublicTarget, bool &IsExported);
612 bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,
613 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
614 VTableSlotInfo &SlotInfo,
615 WholeProgramDevirtResolution *Res,
616 bool HasPublicTarget);
617
618 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Function &JT,
619 bool &IsExported);
620 void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
621 VTableSlotInfo &SlotInfo,
622 WholeProgramDevirtResolution *Res, VTableSlot Slot);
623
624 bool tryEvaluateFunctionsWithArgs(
625 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
626 ArrayRef<uint64_t> Args);
627
628 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
629 uint64_t TheRetVal);
630 bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
631 CallSiteInfo &CSInfo,
632 WholeProgramDevirtResolution::ByArg *Res);
633
634 // Returns the global symbol name that is used to export information about the
635 // given vtable slot and list of arguments.
636 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
637 StringRef Name);
638
639 bool shouldExportConstantsAsAbsoluteSymbols();
640
641 // This function is called during the export phase to create a symbol
642 // definition containing information about the given vtable slot and list of
643 // arguments.
644 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
645 Constant *C);
646 void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
647 uint32_t Const, uint32_t &Storage);
648
649 // This function is called during the import phase to create a reference to
650 // the symbol definition created during the export phase.
651 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
652 StringRef Name);
653 Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
654 StringRef Name, IntegerType *IntTy,
655 uint32_t Storage);
656
657 Constant *getMemberAddr(const TypeMemberInfo *M);
658
659 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
660 Constant *UniqueMemberAddr);
661 bool tryUniqueRetValOpt(unsigned BitWidth,
662 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
663 CallSiteInfo &CSInfo,
664 WholeProgramDevirtResolution::ByArg *Res,
665 VTableSlot Slot, ArrayRef<uint64_t> Args);
666
667 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
668 Constant *Byte, Constant *Bit);
669 bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
670 VTableSlotInfo &SlotInfo,
671 WholeProgramDevirtResolution *Res, VTableSlot Slot);
672
673 void rebuildGlobal(VTableBits &B);
674
675 // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
676 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
677
678 // If we were able to eliminate all unsafe uses for a type checked load,
679 // eliminate the associated type tests by replacing them with true.
680 void removeRedundantTypeTests();
681
682 bool run();
683
684 // Look up the corresponding ValueInfo entry of `TheFn` in `ExportSummary`.
685 //
686 // Caller guarantees that `ExportSummary` is not nullptr.
687 static ValueInfo lookUpFunctionValueInfo(Function *TheFn,
688 ModuleSummaryIndex *ExportSummary);
689
690 // Returns true if the function definition must be unreachable.
691 //
692 // Note if this helper function returns true, `F` is guaranteed
693 // to be unreachable; if it returns false, `F` might still
694 // be unreachable but not covered by this helper function.
695 //
696 // Implementation-wise, if function definition is present, IR is analyzed; if
697 // not, look up function flags from ExportSummary as a fallback.
698 static bool mustBeUnreachableFunction(Function *const F,
699 ModuleSummaryIndex *ExportSummary);
700
701 // Lower the module using the action and summary passed as command line
702 // arguments. For testing purposes only.
703 static bool runForTesting(Module &M, ModuleAnalysisManager &MAM,
704 bool DevirtSpeculatively);
705};
706
707struct DevirtIndex {
708 ModuleSummaryIndex &ExportSummary;
709 // The set in which to record GUIDs exported from their module by
710 // devirtualization, used by client to ensure they are not internalized.
711 std::set<GlobalValue::GUID> &ExportedGUIDs;
712 // A map in which to record the information necessary to locate the WPD
713 // resolution for local targets in case they are exported by cross module
714 // importing.
715 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
716 // We have hardcoded the promoted and renamed function name in the WPD
717 // summary, so we need to ensure that they will be renamed. Note this and
718 // that adding the current names to this set ensures we continue to rename
719 // them.
720 DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr;
721
722 MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;
723
724 PatternList FunctionsToSkip;
725
726 // Whether speculative devirtualization is enabled, as recorded in the
727 // combined index by runWholeProgramDevirtOnIndex.
728 const bool DevirtSpeculatively;
729
730 DevirtIndex(
731 ModuleSummaryIndex &ExportSummary,
732 std::set<GlobalValue::GUID> &ExportedGUIDs,
733 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap,
734 DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr)
735 : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
736 LocalWPDTargetsMap(LocalWPDTargetsMap),
737 ExternallyVisibleSymbolNamesPtr(ExternallyVisibleSymbolNamesPtr),
738 DevirtSpeculatively(ExportSummary.withSpeculativeDevirt()) {
739 FunctionsToSkip.init(StringList: SkipFunctionNames);
740 }
741
742 bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
743 const TypeIdCompatibleVtableInfo TIdInfo,
744 uint64_t ByteOffset, bool &HasPublicTarget);
745
746 bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
747 VTableSlotSummary &SlotSummary,
748 VTableSlotInfo &SlotInfo,
749 WholeProgramDevirtResolution *Res,
750 std::set<ValueInfo> &DevirtTargets,
751 bool HasPublicTarget);
752
753 void run();
754};
755} // end anonymous namespace
756
757PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
758 ModuleAnalysisManager &MAM) {
759 const bool DevirtualizeSpeculatively =
760 DevirtSpeculatively || getIPOOptions(M).devirtualize_speculatively;
761
762 if (UseCommandLine) {
763 if (!DevirtModule::runForTesting(M, MAM, DevirtSpeculatively: DevirtualizeSpeculatively))
764 return PreservedAnalyses::all();
765 return PreservedAnalyses::none();
766 }
767
768 // FIXME: The state of a run should not be kept in the pass. A more resilient
769 // design would create an object in run() that holds the values the run
770 // needs, such as the module, the analyses and the summaries.
771 std::optional<ModuleSummaryIndex> Index;
772 ModuleSummaryIndex *Export = ExportSummary;
773 if (!ExportSummary && !ImportSummary && DevirtualizeSpeculatively) {
774 // Build the ExportSummary from the module.
775 ProfileSummaryInfo PSI(M);
776 Index.emplace(args: buildModuleSummaryIndex(M, GetBFICallback: nullptr, PSI: &PSI));
777 Export = &*Index;
778 }
779 if (!DevirtModule(M, MAM, Export, ImportSummary, DevirtualizeSpeculatively)
780 .run())
781 return PreservedAnalyses::all();
782 return PreservedAnalyses::none();
783}
784
785// Enable whole program visibility if enabled by client (e.g. linker) or
786// internal option, and not force disabled.
787bool llvm::hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) {
788 return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) &&
789 !DisableWholeProgramVisibility;
790}
791
792static bool
793typeIDVisibleToRegularObj(StringRef TypeID,
794 function_ref<bool(StringRef)> IsVisibleToRegularObj) {
795 // TypeID for member function pointer type is an internal construct
796 // and won't exist in IsVisibleToRegularObj. The full TypeID
797 // will be present and participate in invalidation.
798 if (TypeID.ends_with(Suffix: ".virtual"))
799 return false;
800
801 // TypeID that doesn't start with Itanium mangling (_ZTS) will be
802 // non-externally visible types which cannot interact with
803 // external native files. See CodeGenModule::CreateMetadataIdentifierImpl.
804 if (!TypeID.consume_front(Prefix: "_ZTS"))
805 return false;
806
807 // TypeID is keyed off the type name symbol (_ZTS). However, the native
808 // object may not contain this symbol if it does not contain a key
809 // function for the base type and thus only contains a reference to the
810 // type info (_ZTI). To catch this case we query using the type info
811 // symbol corresponding to the TypeID.
812 std::string TypeInfo = ("_ZTI" + TypeID).str();
813 return IsVisibleToRegularObj(TypeInfo);
814}
815
816static bool
817skipUpdateDueToValidation(GlobalVariable &GV,
818 function_ref<bool(StringRef)> IsVisibleToRegularObj) {
819 SmallVector<MDNode *, 2> Types;
820 GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
821
822 for (auto *Type : Types)
823 if (auto *TypeID = dyn_cast<MDString>(Val: Type->getOperand(I: 1).get()))
824 return typeIDVisibleToRegularObj(TypeID: TypeID->getString(),
825 IsVisibleToRegularObj);
826
827 return false;
828}
829
830/// If whole program visibility asserted, then upgrade all public vcall
831/// visibility metadata on vtable definitions to linkage unit visibility in
832/// Module IR (for regular or hybrid LTO).
833void llvm::updateVCallVisibilityInModule(
834 Module &M, bool WholeProgramVisibilityEnabledInLTO,
835 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,
836 bool ValidateAllVtablesHaveTypeInfos,
837 function_ref<bool(StringRef)> IsVisibleToRegularObj) {
838 if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
839 return;
840
841 for (GlobalVariable &GV : M.globals()) {
842 // Add linkage unit visibility to any variable with type metadata, which are
843 // the vtable definitions. We won't have an existing vcall_visibility
844 // metadata on vtable definitions with public visibility.
845 if (GV.hasMetadata(KindID: LLVMContext::MD_type) &&
846 GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic &&
847 // Don't upgrade the visibility for symbols exported to the dynamic
848 // linker, as we have no information on their eventual use.
849 !DynamicExportSymbols.count(V: GV.getGUID()) &&
850 // With validation enabled, we want to exclude symbols visible to
851 // regular objects. Local symbols will be in this group due to the
852 // current implementation but those with VCallVisibilityTranslationUnit
853 // will have already been marked in clang so are unaffected.
854 !(ValidateAllVtablesHaveTypeInfos &&
855 skipUpdateDueToValidation(GV, IsVisibleToRegularObj)))
856 GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit);
857 }
858}
859
860void llvm::updatePublicTypeTestCalls(Module &M,
861 bool WholeProgramVisibilityEnabledInLTO,
862 bool DevirtSpeculativelyInIndex) {
863 llvm::TimeTraceScope timeScope("Update public type test calls");
864 Function *PublicTypeTestFunc =
865 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test);
866 if (!PublicTypeTestFunc)
867 return;
868 if (hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) {
869 Function *TypeTestFunc =
870 Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::type_test);
871 for (Use &U : make_early_inc_range(Range: PublicTypeTestFunc->uses())) {
872 auto *CI = cast<CallInst>(Val: U.getUser());
873 auto *NewCI = CallInst::Create(
874 Func: TypeTestFunc, Args: {CI->getArgOperand(i: 0), CI->getArgOperand(i: 1)}, Bundles: {}, NameStr: "",
875 InsertBefore: CI->getIterator());
876 CI->replaceAllUsesWith(V: NewCI);
877 CI->eraseFromParent();
878 }
879 } else if (!DevirtSpeculativelyInIndex &&
880 !getIPOOptions(M).devirtualize_speculatively) {
881 // Keep the public type tests when speculative devirtualization is enabled,
882 // either via the option or as recorded in the combined index by the thin
883 // link (needed by distributed ThinLTO backends, which don't see the
884 // option), since WPD uses them to find the call sites to devirtualize.
885 auto *True = ConstantInt::getTrue(Context&: M.getContext());
886 for (Use &U : make_early_inc_range(Range: PublicTypeTestFunc->uses())) {
887 auto *CI = cast<CallInst>(Val: U.getUser());
888 CI->replaceAllUsesWith(V: True);
889 CI->eraseFromParent();
890 }
891 }
892}
893
894/// Based on typeID string, get all associated vtable GUIDS that are
895/// visible to regular objects.
896void llvm::getVisibleToRegularObjVtableGUIDs(
897 ModuleSummaryIndex &Index,
898 DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols,
899 function_ref<bool(StringRef)> IsVisibleToRegularObj) {
900 for (const auto &TypeID : Index.typeIdCompatibleVtableMap()) {
901 if (typeIDVisibleToRegularObj(TypeID: TypeID.first, IsVisibleToRegularObj))
902 for (const TypeIdOffsetVtableInfo &P : TypeID.second)
903 VisibleToRegularObjSymbols.insert(V: P.VTableVI.getGUID());
904 }
905}
906
907/// If whole program visibility asserted, then upgrade all public vcall
908/// visibility metadata on vtable definition summaries to linkage unit
909/// visibility in Module summary index (for ThinLTO).
910void llvm::updateVCallVisibilityInIndex(
911 ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
912 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,
913 const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols) {
914 if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
915 return;
916 for (auto &P : Index) {
917 // Don't upgrade the visibility for symbols exported to the dynamic
918 // linker, as we have no information on their eventual use.
919 if (DynamicExportSymbols.count(V: P.first))
920 continue;
921 // With validation enabled, we want to exclude symbols visible to regular
922 // objects. Local symbols will be in this group due to the current
923 // implementation but those with VCallVisibilityTranslationUnit will have
924 // already been marked in clang so are unaffected.
925 if (VisibleToRegularObjSymbols.count(V: P.first))
926 continue;
927 for (auto &S : P.second.getSummaryList()) {
928 auto *GVar = dyn_cast<GlobalVarSummary>(Val: S.get());
929 if (!GVar ||
930 GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic)
931 continue;
932 GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit);
933 }
934 }
935}
936
937void llvm::runWholeProgramDevirtOnIndex(
938 ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
939 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap,
940 DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr,
941 const LLVMContext *Ctx) {
942 // Record in the combined index whether speculative devirtualization is
943 // enabled. This is consulted by the index-based WPD below, and by the
944 // backends (in particular distributed ThinLTO backends, which do not see the
945 // option) so that they apply the speculative resolutions.
946 if (Ctx && getIPOOptions(C: *Ctx).devirtualize_speculatively)
947 Summary.setWithSpeculativeDevirt();
948 DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap,
949 ExternallyVisibleSymbolNamesPtr)
950 .run();
951}
952
953void llvm::updateIndexWPDForExports(
954 ModuleSummaryIndex &Summary,
955 function_ref<bool(StringRef, ValueInfo)> IsExported,
956 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap,
957 DenseSet<StringRef> *ExternallyVisibleSymbolNamesPtr) {
958 for (auto &T : LocalWPDTargetsMap) {
959 auto &VI = T.first;
960 // This was enforced earlier during trySingleImplDevirt.
961 assert(VI.getSummaryList().size() == 1 &&
962 "Devirt of local target has more than one copy");
963 auto &S = VI.getSummaryList()[0];
964 if (!IsExported(S->modulePath(), VI))
965 continue;
966
967 // It's been exported by a cross module import.
968 for (auto &SlotSummary : T.second) {
969 auto *TIdSum = Summary.getTypeIdSummary(TypeId: SlotSummary.TypeID);
970 assert(TIdSum);
971 auto WPDRes = TIdSum->WPDRes.find(x: SlotSummary.ByteOffset);
972 assert(WPDRes != TIdSum->WPDRes.end());
973 if (ExternallyVisibleSymbolNamesPtr)
974 ExternallyVisibleSymbolNamesPtr->insert(V: WPDRes->second.SingleImplName);
975 WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
976 Name: WPDRes->second.SingleImplName,
977 ModHash: Summary.getModuleHash(ModPath: S->modulePath()));
978 }
979 }
980}
981
982static Error checkCombinedSummaryForTesting(const IPOOptions &Opts,
983 ModuleSummaryIndex *Summary) {
984 // Check that summary index contains regular LTO module when performing
985 // export to prevent occasional use of index from pure ThinLTO compilation
986 // (-fno-split-lto-module). This kind of summary index is passed to
987 // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting.
988 const auto &ModPaths = Summary->modulePaths();
989 if (Opts.wholeprogramdevirt_summary_action != PassSummaryAction::Import &&
990 !ModPaths.contains(Key: ModuleSummaryIndex::getRegularLTOModuleName()))
991 return createStringError(
992 EC: errc::invalid_argument,
993 S: "combined summary should contain Regular LTO module");
994 return ErrorSuccess();
995}
996
997bool DevirtModule::runForTesting(Module &M, ModuleAnalysisManager &MAM,
998 bool DevirtSpeculatively) {
999 const IPOOptions &Opts = getIPOOptions(M);
1000 StringRef ReadSummary = Opts.wholeprogramdevirt_read_summary;
1001 StringRef WriteSummary = Opts.wholeprogramdevirt_write_summary;
1002 PassSummaryAction SummaryAction = Opts.wholeprogramdevirt_summary_action;
1003 std::unique_ptr<ModuleSummaryIndex> Summary =
1004 std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/args: false);
1005
1006 // Handle the command-line summary arguments. This code is for testing
1007 // purposes only, so we handle errors directly.
1008 if (!ReadSummary.empty()) {
1009 ExitOnError ExitOnErr(
1010 ("-wholeprogramdevirt-read-summary: " + ReadSummary + ": ").str());
1011 auto ReadSummaryFile =
1012 ExitOnErr(errorOrToExpected(EO: MemoryBuffer::getFile(Filename: ReadSummary)));
1013 if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =
1014 getModuleSummaryIndex(Buffer: *ReadSummaryFile)) {
1015 Summary = std::move(*SummaryOrErr);
1016 ExitOnErr(checkCombinedSummaryForTesting(Opts, Summary: Summary.get()));
1017 } else {
1018 // Try YAML if we've failed with bitcode.
1019 consumeError(Err: SummaryOrErr.takeError());
1020 yaml::Input In(ReadSummaryFile->getBuffer());
1021 In >> *Summary;
1022 ExitOnErr(errorCodeToError(EC: In.error()));
1023 }
1024 }
1025
1026 bool Changed =
1027 DevirtModule(
1028 M, MAM,
1029 SummaryAction == PassSummaryAction::Export ? Summary.get() : nullptr,
1030 SummaryAction == PassSummaryAction::Import ? Summary.get() : nullptr,
1031 DevirtSpeculatively)
1032 .run();
1033
1034 if (!WriteSummary.empty()) {
1035 ExitOnError ExitOnErr(
1036 ("-wholeprogramdevirt-write-summary: " + WriteSummary + ": ").str());
1037 std::error_code EC;
1038 if (WriteSummary.ends_with(Suffix: ".bc")) {
1039 raw_fd_ostream OS(WriteSummary, EC, sys::fs::OF_None);
1040 ExitOnErr(errorCodeToError(EC));
1041 writeIndexToFile(Index: *Summary, Out&: OS);
1042 } else {
1043 raw_fd_ostream OS(WriteSummary, EC, sys::fs::OF_TextWithCRLF);
1044 ExitOnErr(errorCodeToError(EC));
1045 yaml::Output Out(OS);
1046 Out << *Summary;
1047 }
1048 }
1049
1050 return Changed;
1051}
1052
1053void DevirtModule::buildTypeIdentifierMap(
1054 std::vector<VTableBits> &Bits,
1055 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
1056 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
1057 Bits.reserve(n: M.global_size());
1058 SmallVector<MDNode *, 2> Types;
1059 for (GlobalVariable &GV : M.globals()) {
1060 Types.clear();
1061 GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
1062 if (GV.isDeclaration() || Types.empty())
1063 continue;
1064
1065 VTableBits *&BitsPtr = GVToBits[&GV];
1066 if (!BitsPtr) {
1067 Bits.emplace_back();
1068 Bits.back().GV = &GV;
1069 Bits.back().ObjectSize =
1070 M.getDataLayout().getTypeAllocSize(Ty: GV.getInitializer()->getType());
1071 BitsPtr = &Bits.back();
1072 }
1073
1074 for (MDNode *Type : Types) {
1075 auto *TypeID = Type->getOperand(I: 1).get();
1076
1077 uint64_t Offset =
1078 cast<ConstantInt>(
1079 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
1080 ->getZExtValue();
1081
1082 TypeIdMap[TypeID].insert(x: {.Bits: BitsPtr, .Offset: Offset});
1083 }
1084 }
1085}
1086
1087bool DevirtModule::tryFindVirtualCallTargets(
1088 std::vector<VirtualCallTarget> &TargetsForSlot,
1089 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset,
1090 ModuleSummaryIndex *ExportSummary, bool &HasPublicTarget) {
1091 HasPublicTarget = false;
1092
1093 for (const TypeMemberInfo &TM : TypeMemberInfos) {
1094 if (!TM.Bits->GV->isConstant())
1095 return false;
1096
1097 if (TM.Bits->GV->getVCallVisibility() ==
1098 GlobalObject::VCallVisibilityPublic) {
1099 HasPublicTarget = true;
1100 if (!DevirtSpeculatively)
1101 return false;
1102 }
1103
1104 // A local vtable without live uses cannot be loaded from, so it does not
1105 // provide a call target.
1106 if (TM.Bits->GV->hasLocalLinkage() && TM.Bits->GV->hasZeroLiveUses())
1107 continue;
1108
1109 Function *Fn = nullptr;
1110 Constant *C = nullptr;
1111 std::tie(args&: Fn, args&: C) =
1112 getFunctionAtVTableOffset(GV: TM.Bits->GV, Offset: TM.Offset + ByteOffset, M);
1113
1114 if (!Fn)
1115 return false;
1116
1117 if (FunctionsToSkip.match(S: Fn->getName()))
1118 return false;
1119
1120 // We can disregard __cxa_pure_virtual as a possible call target, as
1121 // calls to pure virtuals are UB.
1122 if (Fn->getName() == "__cxa_pure_virtual")
1123 continue;
1124
1125 // We can disregard unreachable functions as possible call targets, as
1126 // unreachable functions shouldn't be called.
1127 if (mustBeUnreachableFunction(F: Fn, ExportSummary))
1128 continue;
1129
1130 // Save the symbol used in the vtable to use as the devirtualization
1131 // target.
1132 auto *GV = dyn_cast<GlobalValue>(Val: C);
1133 assert(GV);
1134 if (auto *GA = dyn_cast<GlobalAlias>(Val: GV))
1135 if (!GA->isInterposable() && !GA->getAliaseeObject()->isInterposable())
1136 GV = GA->getAliaseeObject();
1137 TargetsForSlot.push_back(x: {GV, &TM});
1138 }
1139
1140 // In most cases empty functions will be overridden by the
1141 // implementation of the derived class, so we can skip them
1142 // for speculative devirtualization.
1143 if (HasPublicTarget) {
1144 erase_if(C&: TargetsForSlot, P: [](const VirtualCallTarget &Target) {
1145 const auto *Fn = dyn_cast<Function>(Val: Target.Fn);
1146 if (!Fn)
1147 Fn = cast<Function>(Val: cast<GlobalAlias>(Val: Target.Fn)->getAliasee());
1148 // TODO: This heuristic is currently not applied during hybrid LTO because
1149 // we skip all declarations. If there is a function summary, we should get
1150 // the instruction from there instead.
1151 return !Fn->isDeclaration() && Fn->getReturnType()->isVoidTy() &&
1152 Fn->getInstructionCount() <= 1;
1153 });
1154 }
1155
1156 // Give up if we couldn't find any targets.
1157 return !TargetsForSlot.empty();
1158}
1159
1160bool DevirtIndex::tryFindVirtualCallTargets(
1161 std::vector<ValueInfo> &TargetsForSlot,
1162 const TypeIdCompatibleVtableInfo TIdInfo, uint64_t ByteOffset,
1163 bool &HasPublicTarget) {
1164 HasPublicTarget = false;
1165
1166 for (const TypeIdOffsetVtableInfo &P : TIdInfo) {
1167 // Find a representative copy of the vtable initializer.
1168 // We can have multiple available_externally, linkonce_odr and weak_odr
1169 // vtable initializers. We can also have multiple external vtable
1170 // initializers in the case of comdats, which we cannot check here.
1171 // The linker should give an error in this case.
1172 //
1173 // Also, handle the case of same-named local Vtables with the same path
1174 // and therefore the same GUID. This can happen if there isn't enough
1175 // distinguishing path when compiling the source file. In that case we
1176 // conservatively return false early.
1177 if (P.VTableVI.hasLocal() && P.VTableVI.getSummaryList().size() > 1)
1178 return false;
1179 const GlobalVarSummary *VS = nullptr;
1180 for (const auto &S : P.VTableVI.getSummaryList()) {
1181 auto *CurVS = cast<GlobalVarSummary>(Val: S->getBaseObject());
1182 if (!CurVS->vTableFuncs().empty() ||
1183 // Previously clang did not attach the necessary type metadata to
1184 // available_externally vtables, in which case there would not
1185 // be any vtable functions listed in the summary and we need
1186 // to treat this case conservatively (in case the bitcode is old).
1187 // However, we will also not have any vtable functions in the
1188 // case of a pure virtual base class. In that case we do want
1189 // to set VS to avoid treating it conservatively.
1190 !GlobalValue::isAvailableExternallyLinkage(Linkage: S->linkage())) {
1191 VS = CurVS;
1192 // We cannot perform whole program devirtualization analysis on a vtable
1193 // with public LTO visibility.
1194 if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic) {
1195 HasPublicTarget = true;
1196 if (!DevirtSpeculatively)
1197 return false;
1198 }
1199 break;
1200 }
1201 }
1202 // There will be no VS if all copies are available_externally having no
1203 // type metadata. In that case we can't safely perform WPD.
1204 if (!VS)
1205 return false;
1206 if (!VS->isLive())
1207 continue;
1208 for (auto VTP : VS->vTableFuncs()) {
1209 if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
1210 continue;
1211
1212 if (mustBeUnreachableFunction(TheFnVI: VTP.FuncVI))
1213 continue;
1214
1215 TargetsForSlot.push_back(x: VTP.FuncVI);
1216 }
1217 }
1218
1219 // Give up if we couldn't find any targets.
1220 return !TargetsForSlot.empty();
1221}
1222
1223void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
1224 Constant *TheFn, bool HasPublicTarget,
1225 bool &IsExported) {
1226 // Don't devirtualize function if we're told to skip it
1227 // in -wholeprogramdevirt-skip.
1228 if (FunctionsToSkip.match(S: TheFn->stripPointerCasts()->getName()))
1229 return;
1230 auto Apply = [&](CallSiteInfo &CSInfo) {
1231 for (auto &&VCallSite : CSInfo.CallSites) {
1232 if (!OptimizedCalls.insert(Ptr: &VCallSite.CB).second)
1233 continue;
1234
1235 // Stop when the number of devirted calls reaches the cutoff.
1236 if (!DebugCounter::shouldExecute(Counter&: CallsToDevirt))
1237 continue;
1238
1239 if (RemarksEnabled)
1240 VCallSite.emitRemark(OptName: "single-impl",
1241 TargetName: TheFn->stripPointerCasts()->getName(), OREGetter);
1242 NumSingleImpl++;
1243 auto &CB = VCallSite.CB;
1244 assert(!CB.getCalledFunction() && "devirtualizing direct call?");
1245 IRBuilder<> Builder(&CB);
1246 Value *Callee =
1247 Builder.CreateBitCast(V: TheFn, DestTy: CB.getCalledOperand()->getType());
1248
1249 // If trap checking is enabled, add support to compare the virtual
1250 // function pointer to the devirtualized target. In case of a mismatch,
1251 // perform a debug trap.
1252 if (Opts.wholeprogramdevirt_check == WPDCheckMode::Trap) {
1253 auto *Cond = Builder.CreateICmpNE(LHS: CB.getCalledOperand(), RHS: Callee);
1254 Instruction *ThenTerm = SplitBlockAndInsertIfThen(
1255 Cond, SplitBefore: &CB, /*Unreachable=*/false,
1256 BranchWeights: MDBuilder(M.getContext()).createUnlikelyBranchWeights());
1257 Builder.SetInsertPoint(ThenTerm);
1258 Function *TrapFn =
1259 Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::debugtrap);
1260 auto *CallTrap = Builder.CreateCall(Callee: TrapFn);
1261 CallTrap->setDebugLoc(CB.getDebugLoc());
1262 }
1263
1264 // If fallback checking or speculative devirtualization are enabled,
1265 // add support to compare the virtual function pointer to the
1266 // devirtualized target. In case of a mismatch, fall back to indirect
1267 // call. The guard's weights come from the indirect call's value
1268 // profile when one is available.
1269 if (Opts.wholeprogramdevirt_check == WPDCheckMode::Fallback ||
1270 HasPublicTarget) {
1271 MDBuilder MDB(M.getContext());
1272 uint64_t TotalCount = 0;
1273 SmallVector<InstrProfValueData> ValueData = getValueProfDataFromInst(
1274 Inst: CB, ValueKind: InstrProfValueKind::IPVK_IndirectCallTarget,
1275 MaxNumValueData: std::numeric_limits<uint32_t>::max(), TotalC&: TotalCount);
1276 MDNode *Weights = nullptr;
1277 if (ValueData.empty() || TotalCount == 0) {
1278 Weights = MDB.createLikelyBranchWeights();
1279 } else {
1280 GlobalValue::GUID TargetGUID = cast<GlobalValue>(Val: TheFn)->getGUID();
1281 auto It = llvm::find_if(Range&: ValueData, P: [&](const InstrProfValueData &VD) {
1282 return VD.Value == TargetGUID;
1283 });
1284 if (It == ValueData.end()) {
1285 Weights = MDB.createLikelyBranchWeights();
1286 } else {
1287 uint64_t FallbackCount =
1288 TotalCount - std::min(a: TotalCount, b: It->Count);
1289 assert((FallbackCount != 0 || It->Count != 0) &&
1290 "devirt branch weights are both zero.");
1291 Weights =
1292 MDB.createBranchWeights(Weights: fitWeights(Weights: {It->Count, FallbackCount}));
1293 }
1294 }
1295 // Version the indirect call site. If the called value is equal to the
1296 // given callee, 'NewInst' will be executed, otherwise the original call
1297 // site will be executed.
1298 CallBase &NewInst = versionCallSite(CB, Callee, BranchWeights: Weights);
1299 NewInst.setCalledOperand(Callee);
1300 // Since the new call site is direct, we must clear metadata that
1301 // is only appropriate for indirect calls. This includes !prof and
1302 // !callees metadata.
1303 NewInst.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1304 NewInst.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr);
1305 // Additionally, we should remove them from the fallback indirect call,
1306 // so that we don't attempt to perform indirect call promotion later.
1307 CB.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1308 CB.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr);
1309 }
1310
1311 // In either trapping or non-checking mode, devirtualize original call.
1312 else {
1313 // Devirtualize unconditionally.
1314 assert(!HasPublicTarget);
1315 CB.setCalledOperand(Callee);
1316 // Since the call site is now direct, we must clear metadata that
1317 // is only appropriate for indirect calls. This includes !prof and
1318 // !callees metadata.
1319 CB.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1320 CB.setMetadata(KindID: LLVMContext::MD_callees, Node: nullptr);
1321 if (CB.getCalledOperand() &&
1322 CB.getOperandBundle(ID: LLVMContext::OB_ptrauth)) {
1323 auto *NewCS = CallBase::removeOperandBundle(
1324 CB: &CB, ID: LLVMContext::OB_ptrauth, InsertPt: CB.getIterator());
1325 CB.replaceAllUsesWith(V: NewCS);
1326 // Schedule for deletion at the end of pass run.
1327 CallsWithPtrAuthBundleRemoved.push_back(Elt: &CB);
1328 }
1329
1330 // This use is no longer unsafe.
1331 if (VCallSite.NumUnsafeUses)
1332 --*VCallSite.NumUnsafeUses;
1333 }
1334 }
1335 if (CSInfo.isExported())
1336 IsExported = true;
1337 if (!HasPublicTarget &&
1338 Opts.wholeprogramdevirt_check != WPDCheckMode::Fallback)
1339 CSInfo.markDevirt();
1340 };
1341 Apply(SlotInfo.CSInfo);
1342 for (auto &P : SlotInfo.ConstCSInfo)
1343 Apply(P.second);
1344}
1345
1346static bool addCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) {
1347 // We can't add calls if we haven't seen a definition
1348 if (Callee.getSummaryList().empty())
1349 return false;
1350
1351 // Insert calls into the summary index so that the devirtualized targets
1352 // are eligible for import.
1353 // FIXME: Annotate type tests with hotness. For now, mark these as hot
1354 // to better ensure we have the opportunity to inline them.
1355 bool IsExported = false;
1356 auto &S = Callee.getSummaryList()[0];
1357 CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* HasTailCall = */ false);
1358 auto AddCalls = [&](CallSiteInfo &CSInfo) {
1359 for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1360 FS->addCall(E: {Callee, CI});
1361 IsExported |= S->modulePath() != FS->modulePath();
1362 }
1363 for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
1364 FS->addCall(E: {Callee, CI});
1365 IsExported |= S->modulePath() != FS->modulePath();
1366 }
1367 };
1368 AddCalls(SlotInfo.CSInfo);
1369 for (auto &P : SlotInfo.ConstCSInfo)
1370 AddCalls(P.second);
1371 return IsExported;
1372}
1373
1374bool DevirtModule::trySingleImplDevirt(
1375 ModuleSummaryIndex *ExportSummary,
1376 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1377 WholeProgramDevirtResolution *Res, bool HasPublicTarget) {
1378 // See if the program contains a single implementation of this virtual
1379 // function.
1380 auto *TheFn = TargetsForSlot[0].Fn;
1381 for (auto &&Target : TargetsForSlot)
1382 if (TheFn != Target.Fn)
1383 return false;
1384
1385 // If so, update each call site to call that implementation directly.
1386 if (RemarksEnabled || AreStatisticsEnabled())
1387 TargetsForSlot[0].WasDevirt = true;
1388
1389 bool IsExported = false;
1390 applySingleImplDevirt(SlotInfo, TheFn, HasPublicTarget, IsExported);
1391 if (!IsExported)
1392 return false;
1393
1394 // If the only implementation has local linkage, we must promote to external
1395 // to make it visible to thin LTO objects. We can only get here during the
1396 // ThinLTO export phase.
1397 if (TheFn->hasLocalLinkage()) {
1398 std::string NewName = (TheFn->getName() + ".llvm.merged").str();
1399
1400 // Since we are renaming the function, any comdats with the same name must
1401 // also be renamed. This is required when targeting COFF, as the comdat name
1402 // must match one of the names of the symbols in the comdat.
1403 if (Comdat *C = TheFn->getComdat()) {
1404 if (C->getName() == TheFn->getName()) {
1405 Comdat *NewC = M.getOrInsertComdat(Name: NewName);
1406 NewC->setSelectionKind(C->getSelectionKind());
1407 for (GlobalObject &GO : M.global_objects())
1408 if (GO.getComdat() == C)
1409 GO.setComdat(NewC);
1410 }
1411 }
1412
1413 TheFn->setLinkage(GlobalValue::ExternalLinkage);
1414 TheFn->setVisibility(GlobalValue::HiddenVisibility);
1415 TheFn->setName(NewName);
1416 }
1417 if (ValueInfo TheFnVI = ExportSummary->getValueInfo(GUID: TheFn->getGUID()))
1418 // Any needed promotion of 'TheFn' has already been done during
1419 // LTO unit split, so we can ignore return value of AddCalls.
1420 addCalls(SlotInfo, Callee: TheFnVI);
1421
1422 if (HasPublicTarget)
1423 Res->TheKind = WholeProgramDevirtResolution::Speculative;
1424 else
1425 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
1426
1427 Res->SingleImplName = std::string(TheFn->getName());
1428
1429 return true;
1430}
1431
1432bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
1433 VTableSlotSummary &SlotSummary,
1434 VTableSlotInfo &SlotInfo,
1435 WholeProgramDevirtResolution *Res,
1436 std::set<ValueInfo> &DevirtTargets,
1437 bool HasPublicTarget) {
1438 // See if the program contains a single implementation of this virtual
1439 // function.
1440 auto TheFn = TargetsForSlot[0];
1441 for (auto &&Target : TargetsForSlot)
1442 if (TheFn != Target)
1443 return false;
1444
1445 // Don't devirtualize if we don't have target definition.
1446 auto Size = TheFn.getSummaryList().size();
1447 if (!Size)
1448 return false;
1449
1450 // Don't devirtualize function if we're told to skip it
1451 // in -wholeprogramdevirt-skip.
1452 if (FunctionsToSkip.match(S: TheFn.name()))
1453 return false;
1454
1455 // If the summary list contains multiple summaries where at least one is
1456 // a local, give up, as we won't know which (possibly promoted) name to use.
1457 if (TheFn.hasLocal() && Size > 1)
1458 return false;
1459
1460 // Collect functions devirtualized at least for one call site for stats.
1461 if (PrintSummaryDevirt || AreStatisticsEnabled())
1462 DevirtTargets.insert(x: TheFn);
1463
1464 auto &S = TheFn.getSummaryList()[0];
1465 bool IsExported = addCalls(SlotInfo, Callee: TheFn);
1466 if (IsExported)
1467 ExportedGUIDs.insert(x: TheFn.getGUID());
1468
1469 // Record in summary for use in devirtualization during the ThinLTO import
1470 // step.
1471 if (HasPublicTarget)
1472 Res->TheKind = WholeProgramDevirtResolution::Speculative;
1473 else
1474 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
1475
1476 if (GlobalValue::isLocalLinkage(Linkage: S->linkage())) {
1477 if (IsExported) {
1478 // If target is a local function and we are exporting it by
1479 // devirtualizing a call in another module, we need to record the
1480 // promoted name.
1481 if (ExternallyVisibleSymbolNamesPtr)
1482 ExternallyVisibleSymbolNamesPtr->insert(V: TheFn.name());
1483 Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
1484 Name: TheFn.name(), ModHash: ExportSummary.getModuleHash(ModPath: S->modulePath()));
1485 } else {
1486 LocalWPDTargetsMap[TheFn].push_back(x: SlotSummary);
1487 Res->SingleImplName = std::string(TheFn.name());
1488 }
1489 } else
1490 Res->SingleImplName = std::string(TheFn.name());
1491
1492 // Name will be empty if this thin link driven off of serialized combined
1493 // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
1494 // legacy LTO API anyway.
1495 assert(!Res->SingleImplName.empty());
1496
1497 return true;
1498}
1499
1500void DevirtModule::tryICallBranchFunnel(
1501 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1502 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1503 Triple T(M.getTargetTriple());
1504 if (T.getArch() != Triple::x86_64)
1505 return;
1506
1507 if (TargetsForSlot.size() > Opts.wholeprogramdevirt_branch_funnel_threshold)
1508 return;
1509
1510 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1511 if (!HasNonDevirt)
1512 for (auto &P : SlotInfo.ConstCSInfo)
1513 if (!P.second.AllCallSitesDevirted) {
1514 HasNonDevirt = true;
1515 break;
1516 }
1517
1518 if (!HasNonDevirt)
1519 return;
1520
1521 // If any GV is AvailableExternally, not to generate branch.funnel.
1522 // NOTE: It is to avoid crash in LowerTypeTest.
1523 // If the branch.funnel is generated, because GV.isDeclarationForLinker(),
1524 // in LowerTypeTestsModule::lower(), its GlobalTypeMember would NOT
1525 // be saved in GlobalTypeMembers[&GV]. Then crash happens in
1526 // buildBitSetsFromDisjointSet due to GlobalTypeMembers[&GV] is NULL.
1527 // Even doing experiment to save it in GlobalTypeMembers[&GV] and
1528 // making GlobalTypeMembers[&GV] be not NULL, crash could avoid from
1529 // buildBitSetsFromDisjointSet. But still report_fatal_error in Verifier
1530 // or SelectionDAGBuilder later, because operands linkage type consistency
1531 // check of icall.branch.funnel can not pass.
1532 for (auto &T : TargetsForSlot) {
1533 if (T.TM->Bits->GV->hasAvailableExternallyLinkage())
1534 return;
1535 }
1536
1537 FunctionType *FT =
1538 FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), Params: {Int8PtrTy}, isVarArg: true);
1539 Function *JT;
1540 if (isa<MDString>(Val: Slot.TypeID)) {
1541 JT = Function::Create(Ty: FT, Linkage: Function::ExternalLinkage,
1542 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
1543 N: getGlobalName(Slot, Args: {}, Name: "branch_funnel"), M: &M);
1544 JT->setVisibility(GlobalValue::HiddenVisibility);
1545 } else {
1546 JT = Function::Create(Ty: FT, Linkage: Function::InternalLinkage,
1547 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
1548 N: "branch_funnel", M: &M);
1549 }
1550 JT->addParamAttr(ArgNo: 0, Kind: Attribute::Nest);
1551
1552 std::vector<Value *> JTArgs;
1553 JTArgs.push_back(x: JT->arg_begin());
1554 for (auto &T : TargetsForSlot) {
1555 JTArgs.push_back(x: getMemberAddr(M: T.TM));
1556 JTArgs.push_back(x: T.Fn);
1557 }
1558
1559 BasicBlock *BB = BasicBlock::Create(Context&: M.getContext(), Name: "", Parent: JT, InsertBefore: nullptr);
1560 Function *Intr = Intrinsic::getOrInsertDeclaration(
1561 M: &M, id: llvm::Intrinsic::icall_branch_funnel, OverloadTys: {});
1562
1563 auto *CI = CallInst::Create(Func: Intr, Args: JTArgs, NameStr: "", InsertBefore: BB);
1564 CI->setTailCallKind(CallInst::TCK_MustTail);
1565 ReturnInst::Create(C&: M.getContext(), retVal: nullptr, InsertBefore: BB);
1566
1567 bool IsExported = false;
1568 applyICallBranchFunnel(SlotInfo, JT&: *JT, IsExported);
1569 if (IsExported)
1570 Res->TheKind = WholeProgramDevirtResolution::BranchFunnel;
1571
1572 if (!JT->getEntryCount().has_value()) {
1573 // FIXME: we could pass through thinlto the necessary information.
1574 setExplicitlyUnknownFunctionEntryCount(F&: *JT, DEBUG_TYPE);
1575 }
1576}
1577
1578void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1579 Function &JT, bool &IsExported) {
1580 DenseMap<Function *, double> FunctionEntryCounts;
1581 auto Apply = [&](CallSiteInfo &CSInfo) {
1582 if (CSInfo.isExported())
1583 IsExported = true;
1584 if (CSInfo.AllCallSitesDevirted)
1585 return;
1586
1587 std::map<CallBase *, CallBase *> CallBases;
1588 for (auto &&VCallSite : CSInfo.CallSites) {
1589 CallBase &CB = VCallSite.CB;
1590
1591 if (CallBases.find(x: &CB) != CallBases.end()) {
1592 // When finding devirtualizable calls, it's possible to find the same
1593 // vtable passed to multiple llvm.type.test or llvm.type.checked.load
1594 // calls, which can cause duplicate call sites to be recorded in
1595 // [Const]CallSites. If we've already found one of these
1596 // call instances, just ignore it. It will be replaced later.
1597 continue;
1598 }
1599
1600 // Jump tables are only profitable if the retpoline mitigation is enabled.
1601 Attribute FSAttr = CB.getCaller()->getFnAttribute(Kind: "target-features");
1602 if (!FSAttr.isValid() ||
1603 !FSAttr.getValueAsString().contains(Other: "+retpoline"))
1604 continue;
1605
1606 NumBranchFunnel++;
1607 if (RemarksEnabled)
1608 VCallSite.emitRemark(OptName: "branch-funnel", TargetName: JT.getName(), OREGetter);
1609
1610 // Pass the address of the vtable in the nest register, which is r10 on
1611 // x86_64.
1612 std::vector<Type *> NewArgs;
1613 NewArgs.push_back(x: Int8PtrTy);
1614 append_range(C&: NewArgs, R: CB.getFunctionType()->params());
1615 FunctionType *NewFT =
1616 FunctionType::get(Result: CB.getFunctionType()->getReturnType(), Params: NewArgs,
1617 isVarArg: CB.getFunctionType()->isVarArg());
1618 IRBuilder<> IRB(&CB);
1619 std::vector<Value *> Args;
1620 Args.push_back(x: VCallSite.VTable);
1621 llvm::append_range(C&: Args, R: CB.args());
1622
1623 CallBase *NewCS = nullptr;
1624 if (!JT.isDeclaration()) {
1625 // Accumulate the call frequencies of the original call site, and use
1626 // that as total entry count for the funnel function.
1627 auto &F = *CB.getCaller();
1628 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
1629 auto EC = BFI.getBlockFreq(BB: &F.getEntryBlock());
1630 auto CC = F.getEntryCount();
1631 double CallCount = 0.0;
1632 if (EC.getFrequency() != 0 && CC && *CC != 0) {
1633 double CallFreq =
1634 static_cast<double>(
1635 BFI.getBlockFreq(BB: CB.getParent()).getFrequency()) /
1636 EC.getFrequency();
1637 CallCount = CallFreq * *CC;
1638 }
1639 FunctionEntryCounts[&JT] += CallCount;
1640 }
1641 if (isa<CallInst>(Val: CB))
1642 NewCS = IRB.CreateCall(FTy: NewFT, Callee: &JT, Args);
1643 else
1644 NewCS =
1645 IRB.CreateInvoke(Ty: NewFT, Callee: &JT, NormalDest: cast<InvokeInst>(Val&: CB).getNormalDest(),
1646 UnwindDest: cast<InvokeInst>(Val&: CB).getUnwindDest(), Args);
1647 NewCS->setCallingConv(CB.getCallingConv());
1648
1649 AttributeList Attrs = CB.getAttributes();
1650 std::vector<AttributeSet> NewArgAttrs;
1651 NewArgAttrs.push_back(x: AttributeSet::get(
1652 C&: M.getContext(), Attrs: ArrayRef<Attribute>{Attribute::get(
1653 Context&: M.getContext(), Kind: Attribute::Nest)}));
1654 for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1655 NewArgAttrs.push_back(x: Attrs.getParamAttrs(ArgNo: I));
1656 NewCS->setAttributes(
1657 AttributeList::get(C&: M.getContext(), FnAttrs: Attrs.getFnAttrs(),
1658 RetAttrs: Attrs.getRetAttrs(), ArgAttrs: NewArgAttrs));
1659
1660 CallBases[&CB] = NewCS;
1661
1662 // This use is no longer unsafe.
1663 if (VCallSite.NumUnsafeUses)
1664 --*VCallSite.NumUnsafeUses;
1665 }
1666 // Don't mark as devirtualized because there may be callers compiled without
1667 // retpoline mitigation, which would mean that they are lowered to
1668 // llvm.type.test and therefore require an llvm.type.test resolution for the
1669 // type identifier.
1670
1671 for (auto &[Old, New] : CallBases) {
1672 Old->replaceAllUsesWith(V: New);
1673 Old->eraseFromParent();
1674 }
1675 };
1676 Apply(SlotInfo.CSInfo);
1677 for (auto &P : SlotInfo.ConstCSInfo)
1678 Apply(P.second);
1679 for (auto &[F, C] : FunctionEntryCounts) {
1680 assert(!F->getEntryCount() &&
1681 "Unexpected entry count for funnel that was freshly synthesized");
1682 F->setEntryCount(Count: static_cast<uint64_t>(std::round(x: C)));
1683 }
1684}
1685
1686bool DevirtModule::tryEvaluateFunctionsWithArgs(
1687 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1688 ArrayRef<uint64_t> Args) {
1689 // Evaluate each function and store the result in each target's RetVal
1690 // field.
1691 for (VirtualCallTarget &Target : TargetsForSlot) {
1692 // TODO: Skip for now if the vtable symbol was an alias to a function,
1693 // need to evaluate whether it would be correct to analyze the aliasee
1694 // function for this optimization.
1695 auto *Fn = dyn_cast<Function>(Val: Target.Fn);
1696 if (!Fn)
1697 return false;
1698
1699 if (Fn->arg_size() != Args.size() + 1)
1700 return false;
1701
1702 Evaluator Eval(M.getDataLayout(), nullptr);
1703 SmallVector<Constant *, 2> EvalArgs;
1704 EvalArgs.push_back(
1705 Elt: Constant::getNullValue(Ty: Fn->getFunctionType()->getParamType(i: 0)));
1706 for (unsigned I = 0; I != Args.size(); ++I) {
1707 auto *ArgTy =
1708 dyn_cast<IntegerType>(Val: Fn->getFunctionType()->getParamType(i: I + 1));
1709 if (!ArgTy)
1710 return false;
1711 EvalArgs.push_back(Elt: ConstantInt::get(Ty: ArgTy, V: Args[I]));
1712 }
1713
1714 Constant *RetVal;
1715 if (!Eval.EvaluateFunction(F: Fn, RetVal, ActualArgs: EvalArgs) ||
1716 !isa<ConstantInt>(Val: RetVal))
1717 return false;
1718 Target.RetVal = cast<ConstantInt>(Val: RetVal)->getZExtValue();
1719 }
1720 return true;
1721}
1722
1723void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1724 uint64_t TheRetVal) {
1725 for (auto Call : CSInfo.CallSites) {
1726 if (!OptimizedCalls.insert(Ptr: &Call.CB).second)
1727 continue;
1728 NumUniformRetVal++;
1729 Call.replaceAndErase(
1730 OptName: "uniform-ret-val", TargetName: FnName, RemarksEnabled, OREGetter,
1731 New: ConstantInt::get(Ty: cast<IntegerType>(Val: Call.CB.getType()), V: TheRetVal));
1732 }
1733 CSInfo.markDevirt();
1734}
1735
1736bool DevirtModule::tryUniformRetValOpt(
1737 MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1738 WholeProgramDevirtResolution::ByArg *Res) {
1739 // Uniform return value optimization. If all functions return the same
1740 // constant, replace all calls with that constant.
1741 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1742 for (const VirtualCallTarget &Target : TargetsForSlot)
1743 if (Target.RetVal != TheRetVal)
1744 return false;
1745
1746 if (CSInfo.isExported()) {
1747 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
1748 Res->Info = TheRetVal;
1749 }
1750
1751 applyUniformRetValOpt(CSInfo, FnName: TargetsForSlot[0].Fn->getName(), TheRetVal);
1752 if (RemarksEnabled || AreStatisticsEnabled())
1753 for (auto &&Target : TargetsForSlot)
1754 Target.WasDevirt = true;
1755 return true;
1756}
1757
1758std::string DevirtModule::getGlobalName(VTableSlot Slot,
1759 ArrayRef<uint64_t> Args,
1760 StringRef Name) {
1761 std::string FullName = "__typeid_";
1762 raw_string_ostream OS(FullName);
1763 OS << cast<MDString>(Val: Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1764 for (uint64_t Arg : Args)
1765 OS << '_' << Arg;
1766 OS << '_' << Name;
1767 return FullName;
1768}
1769
1770bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1771 Triple T(M.getTargetTriple());
1772 return T.isX86() && T.getObjectFormat() == Triple::ELF;
1773}
1774
1775void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1776 StringRef Name, Constant *C) {
1777 GlobalAlias *GA = GlobalAlias::create(Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::ExternalLinkage,
1778 Name: getGlobalName(Slot, Args, Name), Aliasee: C, Parent: &M);
1779 GA->setVisibility(GlobalValue::HiddenVisibility);
1780}
1781
1782void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1783 StringRef Name, uint32_t Const,
1784 uint32_t &Storage) {
1785 if (shouldExportConstantsAsAbsoluteSymbols()) {
1786 exportGlobal(
1787 Slot, Args, Name,
1788 C: ConstantExpr::getIntToPtr(C: ConstantInt::get(Ty: Int32Ty, V: Const), Ty: Int8PtrTy));
1789 return;
1790 }
1791
1792 Storage = Const;
1793}
1794
1795Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1796 StringRef Name) {
1797 GlobalVariable *GV =
1798 M.getOrInsertGlobal(Name: getGlobalName(Slot, Args, Name), Ty: Int8Arr0Ty);
1799 GV->setVisibility(GlobalValue::HiddenVisibility);
1800 return GV;
1801}
1802
1803Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1804 StringRef Name, IntegerType *IntTy,
1805 uint32_t Storage) {
1806 if (!shouldExportConstantsAsAbsoluteSymbols())
1807 return ConstantInt::get(Ty: IntTy, V: Storage);
1808
1809 Constant *C = importGlobal(Slot, Args, Name);
1810 auto *GV = cast<GlobalVariable>(Val: C->stripPointerCasts());
1811 C = ConstantExpr::getPtrToInt(C, Ty: IntTy);
1812
1813 // We only need to set metadata if the global is newly created, in which
1814 // case it would not have hidden visibility.
1815 if (GV->hasMetadata(KindID: LLVMContext::MD_absolute_symbol))
1816 return C;
1817
1818 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1819 auto *MinC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Min));
1820 auto *MaxC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Max));
1821 GV->setMetadata(KindID: LLVMContext::MD_absolute_symbol,
1822 Node: MDNode::get(Context&: M.getContext(), MDs: {MinC, MaxC}));
1823 };
1824 unsigned AbsWidth = IntTy->getBitWidth();
1825 if (AbsWidth == IntPtrTy->getBitWidth()) {
1826 uint64_t AllOnes = IntTy->getBitMask();
1827 SetAbsRange(AllOnes, AllOnes); // Full set.
1828 } else {
1829 SetAbsRange(0, 1ull << AbsWidth);
1830 }
1831 return C;
1832}
1833
1834void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1835 bool IsOne,
1836 Constant *UniqueMemberAddr) {
1837 for (auto &&Call : CSInfo.CallSites) {
1838 if (!OptimizedCalls.insert(Ptr: &Call.CB).second)
1839 continue;
1840 IRBuilder<> B(&Call.CB);
1841 Value *Cmp =
1842 B.CreateICmp(P: IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, LHS: Call.VTable,
1843 RHS: B.CreateBitCast(V: UniqueMemberAddr, DestTy: Call.VTable->getType()));
1844 Cmp = B.CreateZExt(V: Cmp, DestTy: Call.CB.getType());
1845 NumUniqueRetVal++;
1846 Call.replaceAndErase(OptName: "unique-ret-val", TargetName: FnName, RemarksEnabled, OREGetter,
1847 New: Cmp);
1848 }
1849 CSInfo.markDevirt();
1850}
1851
1852Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1853 return ConstantExpr::getPtrAdd(Ptr: M->Bits->GV,
1854 Offset: ConstantInt::get(Ty: Int64Ty, V: M->Offset));
1855}
1856
1857bool DevirtModule::tryUniqueRetValOpt(
1858 unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1859 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1860 VTableSlot Slot, ArrayRef<uint64_t> Args) {
1861 // IsOne controls whether we look for a 0 or a 1.
1862 auto tryUniqueRetValOptFor = [&](bool IsOne) {
1863 const TypeMemberInfo *UniqueMember = nullptr;
1864 for (const VirtualCallTarget &Target : TargetsForSlot) {
1865 if (Target.RetVal == (IsOne ? 1 : 0)) {
1866 if (UniqueMember)
1867 return false;
1868 UniqueMember = Target.TM;
1869 }
1870 }
1871
1872 // We should have found a unique member or bailed out by now. We already
1873 // checked for a uniform return value in tryUniformRetValOpt.
1874 assert(UniqueMember);
1875
1876 Constant *UniqueMemberAddr = getMemberAddr(M: UniqueMember);
1877 if (CSInfo.isExported()) {
1878 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
1879 Res->Info = IsOne;
1880
1881 exportGlobal(Slot, Args, Name: "unique_member", C: UniqueMemberAddr);
1882 }
1883
1884 // Replace each call with the comparison.
1885 applyUniqueRetValOpt(CSInfo, FnName: TargetsForSlot[0].Fn->getName(), IsOne,
1886 UniqueMemberAddr);
1887
1888 // Update devirtualization statistics for targets.
1889 if (RemarksEnabled || AreStatisticsEnabled())
1890 for (auto &&Target : TargetsForSlot)
1891 Target.WasDevirt = true;
1892
1893 return true;
1894 };
1895
1896 if (BitWidth == 1) {
1897 if (tryUniqueRetValOptFor(true))
1898 return true;
1899 if (tryUniqueRetValOptFor(false))
1900 return true;
1901 }
1902 return false;
1903}
1904
1905void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1906 Constant *Byte, Constant *Bit) {
1907 for (auto Call : CSInfo.CallSites) {
1908 if (!OptimizedCalls.insert(Ptr: &Call.CB).second)
1909 continue;
1910 auto *RetType = cast<IntegerType>(Val: Call.CB.getType());
1911 IRBuilder<> B(&Call.CB);
1912 Value *Addr = B.CreatePtrAddWithSExtOrTrunc(Ptr: Call.VTable, Offset: Byte);
1913 if (RetType->getBitWidth() == 1) {
1914 Value *Bits = B.CreateLoad(Ty: Int8Ty, Ptr: Addr);
1915 Value *BitsAndBit = B.CreateAnd(LHS: Bits, RHS: Bit);
1916 auto IsBitSet = B.CreateICmpNE(LHS: BitsAndBit, RHS: ConstantInt::get(Ty: Int8Ty, V: 0));
1917 NumVirtConstProp1Bit++;
1918 Call.replaceAndErase(OptName: "virtual-const-prop-1-bit", TargetName: FnName, RemarksEnabled,
1919 OREGetter, New: IsBitSet);
1920 } else {
1921 Value *Val = B.CreateLoad(Ty: RetType, Ptr: Addr);
1922 NumVirtConstProp++;
1923 Call.replaceAndErase(OptName: "virtual-const-prop", TargetName: FnName, RemarksEnabled,
1924 OREGetter, New: Val);
1925 }
1926 }
1927 CSInfo.markDevirt();
1928}
1929
1930bool DevirtModule::tryVirtualConstProp(
1931 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1932 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1933 // TODO: Skip for now if the vtable symbol was an alias to a function,
1934 // need to evaluate whether it would be correct to analyze the aliasee
1935 // function for this optimization.
1936 auto *Fn = dyn_cast<Function>(Val: TargetsForSlot[0].Fn);
1937 if (!Fn)
1938 return false;
1939 // This only works if the function returns an integer.
1940 auto *RetType = dyn_cast<IntegerType>(Val: Fn->getReturnType());
1941 if (!RetType)
1942 return false;
1943 unsigned BitWidth = RetType->getBitWidth();
1944
1945 // TODO: Since we can evaluated these constants at compile-time, we can save
1946 // some space by calculating the smallest range of values that all these
1947 // constants can fit in, then only allocate enough space to fit those values.
1948 // At each callsite, we can get the original type by doing a sign/zero
1949 // extension. For example, if we would store an i64, but we can see that all
1950 // the values fit into an i16, then we can store an i16 before/after the
1951 // vtable and at each callsite do a s/zext.
1952 if (BitWidth > 64)
1953 return false;
1954
1955 Align TypeAlignment = M.getDataLayout().getABIIntegerTypeAlignment(BitWidth);
1956
1957 // Make sure that each function is defined, does not access memory, takes at
1958 // least one argument, does not use its first argument (which we assume is
1959 // 'this'), and has the same return type.
1960 //
1961 // Note that we test whether this copy of the function is readnone, rather
1962 // than testing function attributes, which must hold for any copy of the
1963 // function, even a less optimized version substituted at link time. This is
1964 // sound because the virtual constant propagation optimizations effectively
1965 // inline all implementations of the virtual function into each call site,
1966 // rather than using function attributes to perform local optimization.
1967 for (VirtualCallTarget &Target : TargetsForSlot) {
1968 // TODO: Skip for now if the vtable symbol was an alias to a function,
1969 // need to evaluate whether it would be correct to analyze the aliasee
1970 // function for this optimization.
1971 auto *Fn = dyn_cast<Function>(Val: Target.Fn);
1972 if (!Fn)
1973 return false;
1974
1975 if (Fn->isDeclaration() || Fn->isInterposable() ||
1976 !computeFunctionBodyMemoryAccess(F&: *Fn, AAR&: FAM.getResult<AAManager>(IR&: *Fn))
1977 .doesNotAccessMemory() ||
1978 Fn->arg_empty() || !Fn->arg_begin()->use_empty() ||
1979 Fn->getReturnType() != RetType)
1980 return false;
1981
1982 // This only works if the integer size is at most the alignment of the
1983 // vtable. If the table is underaligned, then we can't guarantee that the
1984 // constant will always be aligned to the integer type alignment. For
1985 // example, if the table is `align 1`, we can never guarantee that an i32
1986 // stored before/after the vtable is 32-bit aligned without changing the
1987 // alignment of the new global.
1988 GlobalVariable *GV = Target.TM->Bits->GV;
1989 Align TableAlignment = M.getDataLayout().getValueOrABITypeAlignment(
1990 Alignment: GV->getAlign(), Ty: GV->getValueType());
1991 if (TypeAlignment > TableAlignment)
1992 return false;
1993 }
1994
1995 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1996 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, Args: CSByConstantArg.first))
1997 continue;
1998
1999 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
2000 if (Res)
2001 ResByArg = &Res->ResByArg[CSByConstantArg.first];
2002
2003 if (tryUniformRetValOpt(TargetsForSlot, CSInfo&: CSByConstantArg.second, Res: ResByArg))
2004 continue;
2005
2006 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSInfo&: CSByConstantArg.second,
2007 Res: ResByArg, Slot, Args: CSByConstantArg.first))
2008 continue;
2009
2010 // Find an allocation offset in bits in all vtables associated with the
2011 // type.
2012 // TODO: If there would be "holes" in the vtable that were added by
2013 // padding, we could place i1s there to reduce any extra padding that
2014 // would be introduced by the i1s.
2015 uint64_t AllocBefore =
2016 findLowestOffset(Targets: TargetsForSlot, /*IsAfter=*/false, Size: BitWidth);
2017 uint64_t AllocAfter =
2018 findLowestOffset(Targets: TargetsForSlot, /*IsAfter=*/true, Size: BitWidth);
2019
2020 // Calculate the total amount of padding needed to store a value at both
2021 // ends of the object.
2022 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
2023 for (auto &&Target : TargetsForSlot) {
2024 TotalPaddingBefore += std::max<int64_t>(
2025 a: (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, b: 0);
2026 TotalPaddingAfter += std::max<int64_t>(
2027 a: (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, b: 0);
2028 }
2029
2030 // If the amount of padding is too large, give up.
2031 // FIXME: do something smarter here.
2032 if (std::min(a: TotalPaddingBefore, b: TotalPaddingAfter) > 128)
2033 continue;
2034
2035 // Calculate the offset to the value as a (possibly negative) byte offset
2036 // and (if applicable) a bit offset, and store the values in the targets.
2037 int64_t OffsetByte;
2038 uint64_t OffsetBit;
2039 if (TotalPaddingBefore <= TotalPaddingAfter)
2040 setBeforeReturnValues(Targets: TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
2041 OffsetBit);
2042 else
2043 setAfterReturnValues(Targets: TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
2044 OffsetBit);
2045
2046 // In an earlier check we forbade constant propagation from operating on
2047 // tables whose alignment is less than the alignment needed for loading
2048 // the constant. Thus, the address we take the offset from will always be
2049 // aligned to at least this integer alignment. Now, we need to ensure that
2050 // the offset is also aligned to this integer alignment to ensure we always
2051 // have an aligned load.
2052 assert(OffsetByte % TypeAlignment.value() == 0);
2053
2054 if (RemarksEnabled || AreStatisticsEnabled())
2055 for (auto &&Target : TargetsForSlot)
2056 Target.WasDevirt = true;
2057
2058
2059 if (CSByConstantArg.second.isExported()) {
2060 ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;
2061 ResByArg->Byte = OffsetByte;
2062 exportConstant(Slot, Args: CSByConstantArg.first, Name: "bit", Const: 1ULL << OffsetBit,
2063 Storage&: ResByArg->Bit);
2064 }
2065
2066 // Rewrite each call to a load from OffsetByte/OffsetBit.
2067 Constant *ByteConst = ConstantInt::getSigned(Ty: Int32Ty, V: OffsetByte);
2068 Constant *BitConst = ConstantInt::get(Ty: Int8Ty, V: 1ULL << OffsetBit);
2069 applyVirtualConstProp(CSInfo&: CSByConstantArg.second,
2070 FnName: TargetsForSlot[0].Fn->getName(), Byte: ByteConst, Bit: BitConst);
2071 }
2072 return true;
2073}
2074
2075void DevirtModule::rebuildGlobal(VTableBits &B) {
2076 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
2077 return;
2078
2079 // Align the before byte array to the global's minimum alignment so that we
2080 // don't break any alignment requirements on the global.
2081 Align Alignment = M.getDataLayout().getValueOrABITypeAlignment(
2082 Alignment: B.GV->getAlign(), Ty: B.GV->getValueType());
2083 B.Before.Bytes.resize(new_size: alignTo(Size: B.Before.Bytes.size(), A: Alignment));
2084
2085 // Before was stored in reverse order; flip it now.
2086 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
2087 std::swap(a&: B.Before.Bytes[I], b&: B.Before.Bytes[Size - 1 - I]);
2088
2089 // Build an anonymous global containing the before bytes, followed by the
2090 // original initializer, followed by the after bytes.
2091 auto *NewInit = ConstantStruct::getAnon(
2092 V: {ConstantDataArray::get(Context&: M.getContext(), Elts&: B.Before.Bytes),
2093 B.GV->getInitializer(),
2094 ConstantDataArray::get(Context&: M.getContext(), Elts&: B.After.Bytes)});
2095 auto *NewGV =
2096 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
2097 GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
2098 NewGV->setSection(B.GV->getSection());
2099 NewGV->setComdat(B.GV->getComdat());
2100 NewGV->setAlignment(B.GV->getAlign());
2101
2102 // Copy the original vtable's metadata to the anonymous global, adjusting
2103 // offsets as required.
2104 NewGV->copyMetadata(Src: B.GV, Offset: B.Before.Bytes.size());
2105
2106 // Build an alias named after the original global, pointing at the second
2107 // element (the original initializer).
2108 auto *Alias = GlobalAlias::create(
2109 Ty: B.GV->getInitializer()->getType(), AddressSpace: 0, Linkage: B.GV->getLinkage(), Name: "",
2110 Aliasee: ConstantExpr::getGetElementPtr(
2111 DL: M.getDataLayout(), Ty: NewInit->getType(), C: NewGV,
2112 IdxList: {ConstantInt::get(Ty: Int32Ty, V: 0), ConstantInt::get(Ty: Int32Ty, V: 1)},
2113 NW: GEPNoWrapFlags::inBounds()),
2114 Parent: &M);
2115 Alias->setVisibility(B.GV->getVisibility());
2116 Alias->takeName(V: B.GV);
2117
2118 B.GV->replaceAllUsesWith(V: Alias);
2119 B.GV->eraseFromParent();
2120}
2121
2122bool DevirtModule::areRemarksEnabled() {
2123 const auto &FL = M.getFunctionList();
2124 for (const Function &Fn : FL) {
2125 if (Fn.empty())
2126 continue;
2127 auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &Fn.front());
2128 return DI.isEnabled();
2129 }
2130 return false;
2131}
2132
2133/// Find assumes whose conditions depend on this type test through phi or select
2134/// nodes. SimplifyCFG can produce these patterns by merging type test + assume
2135/// sequences from different predecessors.
2136static void
2137findAssumesThroughMergesForTypeTest(SmallVectorImpl<CallInst *> &Assumes,
2138 CallInst &TypeTest,
2139 SmallPtrSetImpl<Value *> &VisitedMerges) {
2140 SmallVector<Value *, 4> Worklist;
2141#ifndef NDEBUG
2142 SmallPtrSet<CallInst *, 4> DirectAssumes(Assumes.begin(), Assumes.end());
2143#endif
2144
2145 auto GetMergeUser = [](User *U, Value *V) -> Value * {
2146 if (isa<PHINode>(Val: U))
2147 return U;
2148 if (auto *Select = dyn_cast<SelectInst>(Val: U);
2149 Select && (Select->getTrueValue() == V || Select->getFalseValue() == V))
2150 return Select;
2151 return nullptr;
2152 };
2153
2154 // Direct assume users were already collected by
2155 // findDevirtualizableCallsForTypeTest. Start from merge users so this search
2156 // finds only assumptions that depend on the type test through merges.
2157 for (User *U : TypeTest.users())
2158 if (Value *Merge = GetMergeUser(U, &TypeTest))
2159 Worklist.push_back(Elt: Merge);
2160
2161 while (!Worklist.empty()) {
2162 Value *V = Worklist.pop_back_val();
2163 if (!VisitedMerges.insert(Ptr: V).second)
2164 continue;
2165
2166 for (User *U : V->users()) {
2167 if (auto *Assume = dyn_cast<AssumeInst>(Val: U)) {
2168 if (Assume->getArgOperand(i: 0) == V) {
2169 assert(!DirectAssumes.contains(Assume) &&
2170 "assume must not be both direct and merged");
2171 Assumes.push_back(Elt: Assume);
2172 }
2173 continue;
2174 }
2175
2176 if (Value *Merge = GetMergeUser(U, V))
2177 Worklist.push_back(Elt: Merge);
2178 }
2179 }
2180}
2181
2182void DevirtModule::scanTypeTestUsers(
2183 Function *TypeTestFunc,
2184 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
2185 // Cleanup removes every assume reachable through a merge, so each merge only
2186 // needs to be processed once even if multiple unresolved type tests reach it.
2187 SmallPtrSet<Value *, 8> VisitedMerges;
2188
2189 // Find all virtual calls via a virtual table pointer %p under an assumption
2190 // of the form llvm.assume(llvm.type.test(%p, %md)) or
2191 // llvm.assume(llvm.public.type.test(%p, %md)).
2192 // This indicates that %p points to a member of the type identifier %md.
2193 // Group calls by (type ID, offset) pair (effectively the identity of the
2194 // virtual function) and store to CallSlots.
2195 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc->uses())) {
2196 auto *CI = dyn_cast<CallInst>(Val: U.getUser());
2197 if (!CI)
2198 continue;
2199 // Search for virtual calls based on %p and add them to DevirtCalls.
2200 SmallVector<DevirtCallSite, 1> DevirtCalls;
2201 SmallVector<CallInst *, 1> Assumes;
2202 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: *CI->getFunction());
2203 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
2204
2205 Metadata *TypeId =
2206 cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1))->getMetadata();
2207 // If we found any, add them to CallSlots.
2208 if (!Assumes.empty()) {
2209 Value *Ptr = CI->getArgOperand(i: 0)->stripPointerCasts();
2210 for (DevirtCallSite Call : DevirtCalls)
2211 CallSlots[{.TypeID: TypeId, .ByteOffset: Call.Offset}].addCallSite(VTable: Ptr, CB&: Call.CB, NumUnsafeUses: nullptr);
2212 }
2213
2214 auto RemoveTypeTestAssumes = [&]() {
2215 // A merge of type test results does not imply that any individual type
2216 // test can be assumed, so don't use these assumes to identify
2217 // devirtualizable calls. They still need to be removed when type
2218 // information is missing for any value contributing to the merge.
2219 findAssumesThroughMergesForTypeTest(Assumes, TypeTest&: *CI, VisitedMerges);
2220
2221 // We no longer need the assumes or the type test.
2222 for (auto *Assume : Assumes)
2223 Assume->eraseFromParent();
2224 // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
2225 // may use the vtable argument later.
2226 if (CI->use_empty())
2227 CI->eraseFromParent();
2228 };
2229
2230 // At this point we could remove all type test assume sequences, as they
2231 // were originally inserted for WPD. However, we can keep these in the
2232 // code stream for later analysis (e.g. to help drive more efficient ICP
2233 // sequences). They will eventually be removed by a second LowerTypeTests
2234 // invocation that cleans them up. In order to do this correctly, the first
2235 // LowerTypeTests invocation needs to know that they have "Unknown" type
2236 // test resolution, so that they aren't treated as Unsat and lowered to
2237 // False, which will break any uses on assumes. Below we remove any type
2238 // test assumes that will not be treated as Unknown by LTT.
2239
2240 // The type test assumes will be treated by LTT as Unsat if the type id is
2241 // not used on a global (in which case it has no entry in the TypeIdMap).
2242 if (!TypeIdMap.count(Val: TypeId))
2243 RemoveTypeTestAssumes();
2244
2245 // For ThinLTO importing, we need to remove the type test assumes if this is
2246 // an MDString type id without a corresponding TypeIdSummary. Any
2247 // non-MDString type ids are ignored and treated as Unknown by LTT, so their
2248 // type test assumes can be kept. If the MDString type id is missing a
2249 // TypeIdSummary (e.g. because there was no use on a vcall, preventing the
2250 // exporting phase of WPD from analyzing it), then it would be treated as
2251 // Unsat by LTT and we need to remove its type test assumes here. If not
2252 // used on a vcall we don't need them for later optimization use in any
2253 // case.
2254 else if (ImportSummary && isa<MDString>(Val: TypeId)) {
2255 const TypeIdSummary *TidSummary =
2256 ImportSummary->getTypeIdSummary(TypeId: cast<MDString>(Val: TypeId)->getString());
2257 if (!TidSummary)
2258 RemoveTypeTestAssumes();
2259 else
2260 // If one was created it should not be Unsat, because if we reached here
2261 // the type id was used on a global.
2262 assert(TidSummary->TTRes.TheKind != TypeTestResolution::Unsat);
2263 }
2264 }
2265}
2266
2267void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
2268 Function *TypeTestFunc =
2269 Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::type_test);
2270
2271 for (Use &U : llvm::make_early_inc_range(Range: TypeCheckedLoadFunc->uses())) {
2272 auto *CI = dyn_cast<CallInst>(Val: U.getUser());
2273 if (!CI)
2274 continue;
2275
2276 Value *Ptr = CI->getArgOperand(i: 0);
2277 Value *Offset = CI->getArgOperand(i: 1);
2278 Value *TypeIdValue = CI->getArgOperand(i: 2);
2279 Metadata *TypeId = cast<MetadataAsValue>(Val: TypeIdValue)->getMetadata();
2280
2281 SmallVector<DevirtCallSite, 1> DevirtCalls;
2282 SmallVector<Instruction *, 1> LoadedPtrs;
2283 SmallVector<Instruction *, 1> Preds;
2284 bool HasNonCallUses = false;
2285 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: *CI->getFunction());
2286 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
2287 HasNonCallUses, CI, DT);
2288
2289 // Start by generating "pessimistic" code that explicitly loads the function
2290 // pointer from the vtable and performs the type check. If possible, we will
2291 // eliminate the load and the type check later.
2292
2293 // If possible, only generate the load at the point where it is used.
2294 // This helps avoid unnecessary spills.
2295 IRBuilder<> LoadB(
2296 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
2297
2298 Value *LoadedValue = nullptr;
2299 if (TypeCheckedLoadFunc->getIntrinsicID() ==
2300 Intrinsic::type_checked_load_relative) {
2301 Function *LoadRelFunc = Intrinsic::getOrInsertDeclaration(
2302 M: &M, id: Intrinsic::load_relative, OverloadTys: {Int32Ty});
2303 LoadedValue = LoadB.CreateCall(Callee: LoadRelFunc, Args: {Ptr, Offset});
2304 } else {
2305 Value *GEP = LoadB.CreatePtrAddWithSExtOrTrunc(Ptr, Offset);
2306 LoadedValue = LoadB.CreateLoad(Ty: Int8PtrTy, Ptr: GEP);
2307 }
2308
2309 for (Instruction *LoadedPtr : LoadedPtrs) {
2310 LoadedPtr->replaceAllUsesWith(V: LoadedValue);
2311 LoadedPtr->eraseFromParent();
2312 }
2313
2314 // Likewise for the type test.
2315 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
2316 CallInst *TypeTestCall = CallB.CreateCall(Callee: TypeTestFunc, Args: {Ptr, TypeIdValue});
2317
2318 for (Instruction *Pred : Preds) {
2319 Pred->replaceAllUsesWith(V: TypeTestCall);
2320 Pred->eraseFromParent();
2321 }
2322
2323 // We have already erased any extractvalue instructions that refer to the
2324 // intrinsic call, but the intrinsic may have other non-extractvalue uses
2325 // (although this is unlikely). In that case, explicitly build a pair and
2326 // RAUW it.
2327 if (!CI->use_empty()) {
2328 Value *Pair = PoisonValue::get(T: CI->getType());
2329 IRBuilder<> B(CI);
2330 Pair = B.CreateInsertValue(Agg: Pair, Val: LoadedValue, Idxs: {0});
2331 Pair = B.CreateInsertValue(Agg: Pair, Val: TypeTestCall, Idxs: {1});
2332 CI->replaceAllUsesWith(V: Pair);
2333 }
2334
2335 // The number of unsafe uses is initially the number of uses.
2336 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
2337 NumUnsafeUses = DevirtCalls.size();
2338
2339 // If the function pointer has a non-call user, we cannot eliminate the type
2340 // check, as one of those users may eventually call the pointer. Increment
2341 // the unsafe use count to make sure it cannot reach zero.
2342 if (HasNonCallUses)
2343 ++NumUnsafeUses;
2344 for (DevirtCallSite Call : DevirtCalls) {
2345 CallSlots[{.TypeID: TypeId, .ByteOffset: Call.Offset}].addCallSite(VTable: Ptr, CB&: Call.CB,
2346 NumUnsafeUses: &NumUnsafeUses);
2347 }
2348
2349 CI->eraseFromParent();
2350 }
2351}
2352
2353void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
2354 auto *TypeId = dyn_cast<MDString>(Val: Slot.TypeID);
2355 if (!TypeId)
2356 return;
2357 const TypeIdSummary *TidSummary =
2358 ImportSummary->getTypeIdSummary(TypeId: TypeId->getString());
2359 if (!TidSummary)
2360 return;
2361 auto ResI = TidSummary->WPDRes.find(x: Slot.ByteOffset);
2362 if (ResI == TidSummary->WPDRes.end())
2363 return;
2364 const WholeProgramDevirtResolution &Res = ResI->second;
2365
2366 if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl ||
2367 Res.TheKind == WholeProgramDevirtResolution::Speculative) {
2368 assert(!Res.SingleImplName.empty());
2369 // The type of the function in the declaration is irrelevant because every
2370 // call site will cast it to the correct type.
2371 Value *SingleImplVal =
2372 M.getOrInsertFunction(Name: Res.SingleImplName,
2373 RetTy: Type::getVoidTy(C&: M.getContext()))
2374 .getCallee();
2375 if (auto *A = dyn_cast<GlobalAlias>(Val: SingleImplVal->stripPointerCasts()))
2376 if (!A->isInterposable() && !A->getAliaseeObject()->isInterposable())
2377 SingleImplVal = A->getAliaseeObject();
2378 Constant *SingleImpl = cast<Constant>(Val: SingleImplVal);
2379
2380 // This is the import phase so we should not be exporting anything.
2381 bool IsExported = false;
2382 bool IsSpeculative =
2383 Res.TheKind == WholeProgramDevirtResolution::Speculative;
2384 applySingleImplDevirt(SlotInfo, TheFn: SingleImpl, HasPublicTarget: IsSpeculative, IsExported);
2385 assert(!IsExported);
2386 }
2387
2388 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
2389 auto I = Res.ResByArg.find(x: CSByConstantArg.first);
2390 if (I == Res.ResByArg.end())
2391 continue;
2392 auto &ResByArg = I->second;
2393 // FIXME: We should figure out what to do about the "function name" argument
2394 // to the apply* functions, as the function names are unavailable during the
2395 // importing phase. For now we just pass the empty string. This does not
2396 // impact correctness because the function names are just used for remarks.
2397 switch (ResByArg.TheKind) {
2398 case WholeProgramDevirtResolution::ByArg::UniformRetVal:
2399 applyUniformRetValOpt(CSInfo&: CSByConstantArg.second, FnName: "", TheRetVal: ResByArg.Info);
2400 break;
2401 case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
2402 Constant *UniqueMemberAddr =
2403 importGlobal(Slot, Args: CSByConstantArg.first, Name: "unique_member");
2404 applyUniqueRetValOpt(CSInfo&: CSByConstantArg.second, FnName: "", IsOne: ResByArg.Info,
2405 UniqueMemberAddr);
2406 break;
2407 }
2408 case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
2409 Constant *Byte = ConstantInt::get(Ty: Int32Ty, V: ResByArg.Byte);
2410 Constant *Bit = importConstant(Slot, Args: CSByConstantArg.first, Name: "bit", IntTy: Int8Ty,
2411 Storage: ResByArg.Bit);
2412 applyVirtualConstProp(CSInfo&: CSByConstantArg.second, FnName: "", Byte, Bit);
2413 break;
2414 }
2415 default:
2416 break;
2417 }
2418 }
2419
2420 if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) {
2421 // The type of the function is irrelevant, because it's bitcast at calls
2422 // anyhow.
2423 auto *JT = cast<Function>(
2424 Val: M.getOrInsertFunction(Name: getGlobalName(Slot, Args: {}, Name: "branch_funnel"),
2425 RetTy: Type::getVoidTy(C&: M.getContext()))
2426 .getCallee());
2427 bool IsExported = false;
2428 applyICallBranchFunnel(SlotInfo, JT&: *JT, IsExported);
2429 assert(!IsExported);
2430 }
2431}
2432
2433void DevirtModule::removeRedundantTypeTests() {
2434 auto *True = ConstantInt::getTrue(Context&: M.getContext());
2435 for (auto &&U : NumUnsafeUsesForTypeTest) {
2436 if (U.second == 0) {
2437 U.first->replaceAllUsesWith(V: True);
2438 U.first->eraseFromParent();
2439 }
2440 }
2441}
2442
2443ValueInfo
2444DevirtModule::lookUpFunctionValueInfo(Function *TheFn,
2445 ModuleSummaryIndex *ExportSummary) {
2446 assert((ExportSummary != nullptr) &&
2447 "Caller guarantees ExportSummary is not nullptr");
2448
2449 const auto TheFnGUID = TheFn->getGUID();
2450 const auto TheFnGUIDWithExportedName =
2451 GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: TheFn->getName());
2452 // Look up ValueInfo with the GUID in the current linkage.
2453 ValueInfo TheFnVI = ExportSummary->getValueInfo(GUID: TheFnGUID);
2454 // If no entry is found and GUID is different from GUID computed using
2455 // exported name, look up ValueInfo with the exported name unconditionally.
2456 // This is a fallback.
2457 //
2458 // The reason to have a fallback:
2459 // 1. LTO could enable global value internalization via
2460 // `enable-lto-internalization`.
2461 // 2. The GUID in ExportedSummary is computed using exported name.
2462 if ((!TheFnVI) && (TheFnGUID != TheFnGUIDWithExportedName)) {
2463 TheFnVI = ExportSummary->getValueInfo(GUID: TheFnGUIDWithExportedName);
2464 }
2465 return TheFnVI;
2466}
2467
2468bool DevirtModule::mustBeUnreachableFunction(
2469 Function *const F, ModuleSummaryIndex *ExportSummary) {
2470 if (WholeProgramDevirtKeepUnreachableFunction)
2471 return false;
2472 // First, learn unreachability by analyzing function IR.
2473 if (!F->isDeclaration()) {
2474 // A function must be unreachable if its entry block ends with an
2475 // 'unreachable'.
2476 return isa<UnreachableInst>(Val: F->getEntryBlock().getTerminator());
2477 }
2478 // Learn unreachability from ExportSummary if ExportSummary is present.
2479 return ExportSummary &&
2480 ::mustBeUnreachableFunction(
2481 TheFnVI: DevirtModule::lookUpFunctionValueInfo(TheFn: F, ExportSummary));
2482}
2483
2484bool DevirtModule::run() {
2485 // If only some of the modules were split, we cannot correctly perform
2486 // this transformation. We already checked for the presense of type tests
2487 // with partially split modules during the thin link, and would have emitted
2488 // an error if any were found, so here we can simply return.
2489 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
2490 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
2491 return false;
2492
2493 Function *PublicTypeTestFunc = nullptr;
2494 // If we are in speculative devirtualization mode, we can work on the public
2495 // type test intrinsics.
2496 if (DevirtSpeculatively)
2497 PublicTypeTestFunc =
2498 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test);
2499 Function *TypeTestFunc =
2500 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
2501 Function *TypeCheckedLoadFunc =
2502 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_checked_load);
2503 Function *TypeCheckedLoadRelativeFunc = Intrinsic::getDeclarationIfExists(
2504 M: &M, id: Intrinsic::type_checked_load_relative);
2505 Function *AssumeFunc =
2506 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::assume);
2507
2508 // Normally if there are no users of the devirtualization intrinsics in the
2509 // module, this pass has nothing to do. But if we are exporting, we also need
2510 // to handle any users that appear only in the function summaries.
2511 if (!ExportSummary &&
2512 (((!PublicTypeTestFunc || PublicTypeTestFunc->use_empty()) &&
2513 (!TypeTestFunc || TypeTestFunc->use_empty())) ||
2514 !AssumeFunc || AssumeFunc->use_empty()) &&
2515 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()) &&
2516 (!TypeCheckedLoadRelativeFunc ||
2517 TypeCheckedLoadRelativeFunc->use_empty()))
2518 return false;
2519
2520 // Rebuild type metadata into a map for easy lookup.
2521 std::vector<VTableBits> Bits;
2522 DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
2523 buildTypeIdentifierMap(Bits, TypeIdMap);
2524
2525 if (PublicTypeTestFunc && AssumeFunc)
2526 scanTypeTestUsers(TypeTestFunc: PublicTypeTestFunc, TypeIdMap);
2527
2528 if (TypeTestFunc && AssumeFunc)
2529 scanTypeTestUsers(TypeTestFunc, TypeIdMap);
2530
2531 if (TypeCheckedLoadFunc)
2532 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
2533
2534 if (TypeCheckedLoadRelativeFunc)
2535 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc: TypeCheckedLoadRelativeFunc);
2536
2537 if (ImportSummary) {
2538 for (auto &S : CallSlots)
2539 importResolution(Slot: S.first, SlotInfo&: S.second);
2540
2541 removeRedundantTypeTests();
2542
2543 // We have lowered or deleted the type intrinsics, so we will no longer have
2544 // enough information to reason about the liveness of virtual function
2545 // pointers in GlobalDCE.
2546 for (GlobalVariable &GV : M.globals())
2547 GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility);
2548
2549 // The rest of the code is only necessary when exporting or during regular
2550 // LTO, so we are done.
2551 return true;
2552 }
2553
2554 if (TypeIdMap.empty())
2555 return true;
2556
2557 // Collect information from summary about which calls to try to devirtualize.
2558 if (ExportSummary) {
2559 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
2560 for (auto &P : TypeIdMap) {
2561 if (auto *TypeId = dyn_cast<MDString>(Val: P.first))
2562 MetadataByGUID[GlobalValue::getGUIDAssumingExternalLinkage(
2563 GlobalName: TypeId->getString())]
2564 .push_back(NewVal: TypeId);
2565 }
2566
2567 for (auto &P : *ExportSummary) {
2568 for (auto &S : P.second.getSummaryList()) {
2569 auto *FS = dyn_cast<FunctionSummary>(Val: S.get());
2570 if (!FS)
2571 continue;
2572 // FIXME: Only add live functions.
2573 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2574 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2575 CallSlots[{.TypeID: MD, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2576 }
2577 }
2578 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2579 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2580 CallSlots[{.TypeID: MD, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2581 }
2582 }
2583 for (const FunctionSummary::ConstVCall &VC :
2584 FS->type_test_assume_const_vcalls()) {
2585 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2586 CallSlots[{.TypeID: MD, .ByteOffset: VC.VFunc.Offset}]
2587 .ConstCSInfo[VC.Args]
2588 .addSummaryTypeTestAssumeUser(FS);
2589 }
2590 }
2591 for (const FunctionSummary::ConstVCall &VC :
2592 FS->type_checked_load_const_vcalls()) {
2593 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2594 CallSlots[{.TypeID: MD, .ByteOffset: VC.VFunc.Offset}]
2595 .ConstCSInfo[VC.Args]
2596 .addSummaryTypeCheckedLoadUser(FS);
2597 }
2598 }
2599 }
2600 }
2601 }
2602
2603 // For each (type, offset) pair:
2604 bool DidVirtualConstProp = false;
2605 std::map<std::string, GlobalValue *> DevirtTargets;
2606 for (auto &S : CallSlots) {
2607 // Search each of the members of the type identifier for the virtual
2608 // function implementation at offset S.first.ByteOffset, and add to
2609 // TargetsForSlot.
2610 std::vector<VirtualCallTarget> TargetsForSlot;
2611 WholeProgramDevirtResolution *Res = nullptr;
2612 const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[S.first.TypeID];
2613 if (ExportSummary && isa<MDString>(Val: S.first.TypeID) &&
2614 TypeMemberInfos.size())
2615 // For any type id used on a global's type metadata, create the type id
2616 // summary resolution regardless of whether we can devirtualize, so that
2617 // lower type tests knows the type id is not Unsat. If it was not used on
2618 // a global's type metadata, the TypeIdMap entry set will be empty, and
2619 // we don't want to create an entry (with the default Unknown type
2620 // resolution), which can prevent detection of the Unsat.
2621 Res = &ExportSummary
2622 ->getOrInsertTypeIdSummary(
2623 TypeId: cast<MDString>(Val: S.first.TypeID)->getString())
2624 .WPDRes[S.first.ByteOffset];
2625
2626 bool HasPublicTarget = true;
2627 if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos,
2628 ByteOffset: S.first.ByteOffset, ExportSummary,
2629 HasPublicTarget)) {
2630 bool SingleImplDevirt = trySingleImplDevirt(
2631 ExportSummary, TargetsForSlot, SlotInfo&: S.second, Res, HasPublicTarget);
2632 if (!SingleImplDevirt && !HasPublicTarget) {
2633 DidVirtualConstProp |=
2634 tryVirtualConstProp(TargetsForSlot, SlotInfo&: S.second, Res, Slot: S.first);
2635
2636 tryICallBranchFunnel(TargetsForSlot, SlotInfo&: S.second, Res, Slot: S.first);
2637 }
2638
2639 // Collect functions devirtualized at least for one call site for stats.
2640 if (RemarksEnabled || AreStatisticsEnabled())
2641 for (const auto &T : TargetsForSlot)
2642 if (T.WasDevirt)
2643 DevirtTargets[std::string(T.Fn->getName())] = T.Fn;
2644 }
2645
2646 // CFI-specific: if we are exporting and any llvm.type.checked.load
2647 // intrinsics were *not* devirtualized, we need to add the resulting
2648 // llvm.type.test intrinsics to the function summaries so that the
2649 // LowerTypeTests pass will export them.
2650 if (ExportSummary && isa<MDString>(Val: S.first.TypeID)) {
2651 auto GUID = GlobalValue::getGUIDAssumingExternalLinkage(
2652 GlobalName: cast<MDString>(Val: S.first.TypeID)->getString());
2653 auto AddTypeTestsForTypeCheckedLoads = [&](CallSiteInfo &CSI) {
2654 if (!CSI.AllCallSitesDevirted)
2655 for (auto *FS : CSI.SummaryTypeCheckedLoadUsers)
2656 FS->addTypeTest(Guid: GUID);
2657 };
2658 AddTypeTestsForTypeCheckedLoads(S.second.CSInfo);
2659 for (auto &CCS : S.second.ConstCSInfo)
2660 AddTypeTestsForTypeCheckedLoads(CCS.second);
2661 }
2662 }
2663
2664 if (RemarksEnabled) {
2665 // Generate remarks for each devirtualized function.
2666 for (const auto &DT : DevirtTargets) {
2667 GlobalValue *GV = DT.second;
2668 auto *F = dyn_cast<Function>(Val: GV);
2669 if (!F) {
2670 auto *A = dyn_cast<GlobalAlias>(Val: GV);
2671 assert(A && isa<Function>(A->getAliasee()));
2672 F = dyn_cast<Function>(Val: A->getAliasee());
2673 assert(F);
2674 }
2675
2676 using namespace ore;
2677 OREGetter(*F).emit(OptDiag: OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
2678 << "devirtualized " << NV("FunctionName", DT.first));
2679 }
2680 }
2681
2682 NumDevirtTargets += DevirtTargets.size();
2683
2684 removeRedundantTypeTests();
2685
2686 // Rebuild each global we touched as part of virtual constant propagation to
2687 // include the before and after bytes.
2688 if (DidVirtualConstProp)
2689 for (VTableBits &B : Bits)
2690 rebuildGlobal(B);
2691
2692 // We have lowered or deleted the type intrinsics, so we will no longer have
2693 // enough information to reason about the liveness of virtual function
2694 // pointers in GlobalDCE.
2695 for (GlobalVariable &GV : M.globals())
2696 GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility);
2697
2698 for (auto *CI : CallsWithPtrAuthBundleRemoved)
2699 CI->eraseFromParent();
2700
2701 return true;
2702}
2703
2704void DevirtIndex::run() {
2705 if (ExportSummary.typeIdCompatibleVtableMap().empty())
2706 return;
2707
2708 // Assert that we haven't made any changes that would affect the hasLocal()
2709 // flag on the GUID summary info.
2710 assert(!ExportSummary.withInternalizeAndPromote() &&
2711 "Expect index-based WPD to run before internalization and promotion");
2712
2713 DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
2714 for (const auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
2715 NameByGUID[GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: P.first)].push_back(
2716 x: P.first);
2717 // Create the type id summary resolution regardlness of whether we can
2718 // devirtualize, so that lower type tests knows the type id is used on
2719 // a global and not Unsat. We do this here rather than in the loop over the
2720 // CallSlots, since that handling will only see type tests that directly
2721 // feed assumes, and we would miss any that aren't currently handled by WPD
2722 // (such as type tests that feed assumes via phis).
2723 ExportSummary.getOrInsertTypeIdSummary(TypeId: P.first);
2724 }
2725
2726 // Collect information from summary about which calls to try to devirtualize.
2727 for (auto &P : ExportSummary) {
2728 for (auto &S : P.second.getSummaryList()) {
2729 auto *FS = dyn_cast<FunctionSummary>(Val: S.get());
2730 if (!FS)
2731 continue;
2732 // FIXME: Only add live functions.
2733 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2734 for (StringRef Name : NameByGUID[VF.GUID]) {
2735 CallSlots[{.TypeID: Name, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2736 }
2737 }
2738 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2739 for (StringRef Name : NameByGUID[VF.GUID]) {
2740 CallSlots[{.TypeID: Name, .ByteOffset: VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2741 }
2742 }
2743 for (const FunctionSummary::ConstVCall &VC :
2744 FS->type_test_assume_const_vcalls()) {
2745 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2746 CallSlots[{.TypeID: Name, .ByteOffset: VC.VFunc.Offset}]
2747 .ConstCSInfo[VC.Args]
2748 .addSummaryTypeTestAssumeUser(FS);
2749 }
2750 }
2751 for (const FunctionSummary::ConstVCall &VC :
2752 FS->type_checked_load_const_vcalls()) {
2753 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2754 CallSlots[{.TypeID: Name, .ByteOffset: VC.VFunc.Offset}]
2755 .ConstCSInfo[VC.Args]
2756 .addSummaryTypeCheckedLoadUser(FS);
2757 }
2758 }
2759 }
2760 }
2761
2762 std::set<ValueInfo> DevirtTargets;
2763 // For each (type, offset) pair:
2764 for (auto &S : CallSlots) {
2765 // Search each of the members of the type identifier for the virtual
2766 // function implementation at offset S.first.ByteOffset, and add to
2767 // TargetsForSlot.
2768 std::vector<ValueInfo> TargetsForSlot;
2769 auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(TypeId: S.first.TypeID);
2770 assert(TidSummary);
2771 // The type id summary would have been created while building the NameByGUID
2772 // map earlier.
2773 WholeProgramDevirtResolution *Res =
2774 &ExportSummary.getTypeIdSummary(TypeId: S.first.TypeID)
2775 ->WPDRes[S.first.ByteOffset];
2776
2777 bool HasPublicTarget = true;
2778 if (tryFindVirtualCallTargets(TargetsForSlot, TIdInfo: *TidSummary,
2779 ByteOffset: S.first.ByteOffset, HasPublicTarget)) {
2780
2781 if (!trySingleImplDevirt(TargetsForSlot, SlotSummary&: S.first, SlotInfo&: S.second, Res,
2782 DevirtTargets, HasPublicTarget))
2783 continue;
2784 }
2785 }
2786
2787 // Optionally have the thin link print message for each devirtualized
2788 // function.
2789 if (PrintSummaryDevirt)
2790 for (const auto &DT : DevirtTargets)
2791 errs() << "Devirtualized call to " << DT << "\n";
2792
2793 NumDevirtTargets += DevirtTargets.size();
2794}
2795