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