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