1 //===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass implements whole program optimization of virtual calls in cases
11 // where we know (via !type metadata) that the list of callees is fixed. This
12 // includes the following:
13 // - Single implementation devirtualization: if a virtual call has a single
14 // possible callee, replace all calls with a direct call to that callee.
15 // - Virtual constant propagation: if the virtual function's return type is an
16 // integer <=64 bits and all possible callees are readnone, for each class and
17 // each list of constant arguments: evaluate the function, store the return
18 // value alongside the virtual table, and rewrite each virtual call as a load
19 // from the virtual table.
20 // - Uniform return value optimization: if the conditions for virtual constant
21 // propagation hold and each function returns the same constant value, replace
22 // each virtual call with that constant.
23 // - Unique return value optimization for i1 return values: if the conditions
24 // for virtual constant propagation hold and a single vtable's function
25 // returns 0, or a single vtable's function returns 1, replace each virtual
26 // call with a comparison of the vptr against that vtable's address.
28 // This pass is intended to be used during the regular and thin LTO pipelines.
29 // During regular LTO, the pass determines the best optimization for each
30 // virtual call and applies the resolutions directly to virtual calls that are
31 // eligible for virtual call optimization (i.e. calls that use either of the
32 // llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics). During
33 // ThinLTO, the pass operates in two phases:
34 // - Export phase: this is run during the thin link over a single merged module
35 // that contains all vtables with !type metadata that participate in the link.
36 // The pass computes a resolution for each virtual call and stores it in the
37 // type identifier summary.
38 // - Import phase: this is run during the thin backends over the individual
39 // modules. The pass applies the resolutions previously computed during the
40 // import phase to each eligible virtual call.
42 //===----------------------------------------------------------------------===//
44 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
45 #include "llvm/ADT/ArrayRef.h"
46 #include "llvm/ADT/DenseMap.h"
47 #include "llvm/ADT/DenseMapInfo.h"
48 #include "llvm/ADT/DenseSet.h"
49 #include "llvm/ADT/MapVector.h"
50 #include "llvm/ADT/SmallVector.h"
51 #include "llvm/ADT/iterator_range.h"
52 #include "llvm/Analysis/AliasAnalysis.h"
53 #include "llvm/Analysis/BasicAliasAnalysis.h"
54 #include "llvm/Analysis/TypeMetadataUtils.h"
55 #include "llvm/IR/CallSite.h"
56 #include "llvm/IR/Constants.h"
57 #include "llvm/IR/DataLayout.h"
58 #include "llvm/IR/DebugInfoMetadata.h"
59 #include "llvm/IR/DebugLoc.h"
60 #include "llvm/IR/DerivedTypes.h"
61 #include "llvm/IR/DiagnosticInfo.h"
62 #include "llvm/IR/Function.h"
63 #include "llvm/IR/GlobalAlias.h"
64 #include "llvm/IR/GlobalVariable.h"
65 #include "llvm/IR/IRBuilder.h"
66 #include "llvm/IR/InstrTypes.h"
67 #include "llvm/IR/Instruction.h"
68 #include "llvm/IR/Instructions.h"
69 #include "llvm/IR/Intrinsics.h"
70 #include "llvm/IR/LLVMContext.h"
71 #include "llvm/IR/Metadata.h"
72 #include "llvm/IR/Module.h"
73 #include "llvm/IR/ModuleSummaryIndexYAML.h"
74 #include "llvm/Pass.h"
75 #include "llvm/PassRegistry.h"
76 #include "llvm/PassSupport.h"
77 #include "llvm/Support/Casting.h"
78 #include "llvm/Support/Error.h"
79 #include "llvm/Support/FileSystem.h"
80 #include "llvm/Support/MathExtras.h"
81 #include "llvm/Transforms/IPO.h"
82 #include "llvm/Transforms/IPO/FunctionAttrs.h"
83 #include "llvm/Transforms/Utils/Evaluator.h"
91 using namespace wholeprogramdevirt;
93 #define DEBUG_TYPE "wholeprogramdevirt"
95 static cl::opt<PassSummaryAction> ClSummaryAction(
96 "wholeprogramdevirt-summary-action",
97 cl::desc("What to do with the summary when running this pass"),
98 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
99 clEnumValN(PassSummaryAction::Import, "import",
100 "Import typeid resolutions from summary and globals"),
101 clEnumValN(PassSummaryAction::Export, "export",
102 "Export typeid resolutions to summary and globals")),
105 static cl::opt<std::string> ClReadSummary(
106 "wholeprogramdevirt-read-summary",
107 cl::desc("Read summary from given YAML file before running pass"),
110 static cl::opt<std::string> ClWriteSummary(
111 "wholeprogramdevirt-write-summary",
112 cl::desc("Write summary to given YAML file after running pass"),
115 // Find the minimum offset that we may store a value of size Size bits at. If
116 // IsAfter is set, look for an offset before the object, otherwise look for an
117 // offset after the object.
119 wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
120 bool IsAfter, uint64_t Size) {
121 // Find a minimum offset taking into account only vtable sizes.
122 uint64_t MinByte = 0;
123 for (const VirtualCallTarget &Target : Targets) {
125 MinByte = std::max(MinByte, Target.minAfterBytes());
127 MinByte = std::max(MinByte, Target.minBeforeBytes());
130 // Build a vector of arrays of bytes covering, for each target, a slice of the
131 // used region (see AccumBitVector::BytesUsed in
132 // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
133 // this aligns the used regions to start at MinByte.
135 // In this example, A, B and C are vtables, # is a byte already allocated for
136 // a virtual function pointer, AAAA... (etc.) are the used regions for the
137 // vtables and Offset(X) is the value computed for the Offset variable below
143 // A: ################AAAAAAAA|AAAAAAAA
144 // B: ########BBBBBBBBBBBBBBBB|BBBB
145 // C: ########################|CCCCCCCCCCCCCCCC
148 // This code produces the slices of A, B and C that appear after the divider
150 std::vector<ArrayRef<uint8_t>> Used;
151 for (const VirtualCallTarget &Target : Targets) {
152 ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
153 : Target.TM->Bits->Before.BytesUsed;
154 uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
155 : MinByte - Target.minBeforeBytes();
157 // Disregard used regions that are smaller than Offset. These are
158 // effectively all-free regions that do not need to be checked.
159 if (VTUsed.size() > Offset)
160 Used.push_back(VTUsed.slice(Offset));
164 // Find a free bit in each member of Used.
165 for (unsigned I = 0;; ++I) {
166 uint8_t BitsUsed = 0;
167 for (auto &&B : Used)
170 if (BitsUsed != 0xff)
171 return (MinByte + I) * 8 +
172 countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
175 // Find a free (Size/8) byte region in each member of Used.
176 // FIXME: see if alignment helps.
177 for (unsigned I = 0;; ++I) {
178 for (auto &&B : Used) {
180 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
186 return (MinByte + I) * 8;
192 void wholeprogramdevirt::setBeforeReturnValues(
193 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
194 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
196 OffsetByte = -(AllocBefore / 8 + 1);
198 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
199 OffsetBit = AllocBefore % 8;
201 for (VirtualCallTarget &Target : Targets) {
203 Target.setBeforeBit(AllocBefore);
205 Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
209 void wholeprogramdevirt::setAfterReturnValues(
210 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
211 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
213 OffsetByte = AllocAfter / 8;
215 OffsetByte = (AllocAfter + 7) / 8;
216 OffsetBit = AllocAfter % 8;
218 for (VirtualCallTarget &Target : Targets) {
220 Target.setAfterBit(AllocAfter);
222 Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
226 VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
228 IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
232 // A slot in a set of virtual tables. The TypeID identifies the set of virtual
233 // tables, and the ByteOffset is the offset in bytes from the address point to
234 // the virtual function pointer.
240 } // end anonymous namespace
244 template <> struct DenseMapInfo<VTableSlot> {
245 static VTableSlot getEmptyKey() {
246 return {DenseMapInfo<Metadata *>::getEmptyKey(),
247 DenseMapInfo<uint64_t>::getEmptyKey()};
249 static VTableSlot getTombstoneKey() {
250 return {DenseMapInfo<Metadata *>::getTombstoneKey(),
251 DenseMapInfo<uint64_t>::getTombstoneKey()};
253 static unsigned getHashValue(const VTableSlot &I) {
254 return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
255 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
257 static bool isEqual(const VTableSlot &LHS,
258 const VTableSlot &RHS) {
259 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
263 } // end namespace llvm
267 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
268 // the indirect virtual call.
269 struct VirtualCallSite {
273 // If non-null, this field points to the associated unsafe use count stored in
274 // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
275 // of that field for details.
276 unsigned *NumUnsafeUses;
278 void emitRemark(const Twine &OptName, const Twine &TargetName) {
279 Function *F = CS.getCaller();
280 emitOptimizationRemark(
281 F->getContext(), DEBUG_TYPE, *F,
282 CS.getInstruction()->getDebugLoc(),
283 OptName + ": devirtualized a call to " + TargetName);
286 void replaceAndErase(const Twine &OptName, const Twine &TargetName,
287 bool RemarksEnabled, Value *New) {
289 emitRemark(OptName, TargetName);
290 CS->replaceAllUsesWith(New);
291 if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
292 BranchInst::Create(II->getNormalDest(), CS.getInstruction());
293 II->getUnwindDest()->removePredecessor(II->getParent());
295 CS->eraseFromParent();
296 // This use is no longer unsafe.
302 // Call site information collected for a specific VTableSlot and possibly a list
303 // of constant integer arguments. The grouping by arguments is handled by the
304 // VTableSlotInfo class.
305 struct CallSiteInfo {
306 /// The set of call sites for this slot. Used during regular LTO and the
307 /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
308 /// call sites that appear in the merged module itself); in each of these
309 /// cases we are directly operating on the call sites at the IR level.
310 std::vector<VirtualCallSite> CallSites;
312 // These fields are used during the export phase of ThinLTO and reflect
313 // information collected from function summaries.
315 /// Whether any function summary contains an llvm.assume(llvm.type.test) for
317 bool SummaryHasTypeTestAssumeUsers;
319 /// CFI-specific: a vector containing the list of function summaries that use
320 /// the llvm.type.checked.load intrinsic and therefore will require
321 /// resolutions for llvm.type.test in order to implement CFI checks if
322 /// devirtualization was unsuccessful. If devirtualization was successful, the
323 /// pass will clear this vector by calling markDevirt(). If at the end of the
324 /// pass the vector is non-empty, we will need to add a use of llvm.type.test
325 /// to each of the function summaries in the vector.
326 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
328 bool isExported() const {
329 return SummaryHasTypeTestAssumeUsers ||
330 !SummaryTypeCheckedLoadUsers.empty();
333 /// As explained in the comment for SummaryTypeCheckedLoadUsers.
334 void markDevirt() { SummaryTypeCheckedLoadUsers.clear(); }
337 // Call site information collected for a specific VTableSlot.
338 struct VTableSlotInfo {
339 // The set of call sites which do not have all constant integer arguments
340 // (excluding "this").
343 // The set of call sites with all constant integer arguments (excluding
344 // "this"), grouped by argument list.
345 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
347 void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
350 CallSiteInfo &findCallSiteInfo(CallSite CS);
353 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
354 std::vector<uint64_t> Args;
355 auto *CI = dyn_cast<IntegerType>(CS.getType());
356 if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
358 for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
359 auto *CI = dyn_cast<ConstantInt>(Arg);
360 if (!CI || CI->getBitWidth() > 64)
362 Args.push_back(CI->getZExtValue());
364 return ConstCSInfo[Args];
367 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
368 unsigned *NumUnsafeUses) {
369 findCallSiteInfo(CS).CallSites.push_back({VTable, CS, NumUnsafeUses});
372 struct DevirtModule {
374 function_ref<AAResults &(Function &)> AARGetter;
376 ModuleSummaryIndex *ExportSummary;
377 const ModuleSummaryIndex *ImportSummary;
380 PointerType *Int8PtrTy;
381 IntegerType *Int32Ty;
382 IntegerType *Int64Ty;
383 IntegerType *IntPtrTy;
387 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
389 // This map keeps track of the number of "unsafe" uses of a loaded function
390 // pointer. The key is the associated llvm.type.test intrinsic call generated
391 // by this pass. An unsafe use is one that calls the loaded function pointer
392 // directly. Every time we eliminate an unsafe use (for example, by
393 // devirtualizing it or by applying virtual constant propagation), we
394 // decrement the value stored in this map. If a value reaches zero, we can
395 // eliminate the type check by RAUWing the associated llvm.type.test call with
397 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
399 DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
400 ModuleSummaryIndex *ExportSummary,
401 const ModuleSummaryIndex *ImportSummary)
402 : M(M), AARGetter(AARGetter), ExportSummary(ExportSummary),
403 ImportSummary(ImportSummary), Int8Ty(Type::getInt8Ty(M.getContext())),
404 Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
405 Int32Ty(Type::getInt32Ty(M.getContext())),
406 Int64Ty(Type::getInt64Ty(M.getContext())),
407 IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
408 RemarksEnabled(areRemarksEnabled()) {
409 assert(!(ExportSummary && ImportSummary));
412 bool areRemarksEnabled();
414 void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
415 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
417 void buildTypeIdentifierMap(
418 std::vector<VTableBits> &Bits,
419 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
420 Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
422 tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
423 const std::set<TypeMemberInfo> &TypeMemberInfos,
424 uint64_t ByteOffset);
426 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
428 bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
429 VTableSlotInfo &SlotInfo,
430 WholeProgramDevirtResolution *Res);
432 bool tryEvaluateFunctionsWithArgs(
433 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
434 ArrayRef<uint64_t> Args);
436 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
438 bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
439 CallSiteInfo &CSInfo,
440 WholeProgramDevirtResolution::ByArg *Res);
442 // Returns the global symbol name that is used to export information about the
443 // given vtable slot and list of arguments.
444 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
447 // This function is called during the export phase to create a symbol
448 // definition containing information about the given vtable slot and list of
450 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
453 // This function is called during the import phase to create a reference to
454 // the symbol definition created during the export phase.
455 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
456 StringRef Name, unsigned AbsWidth = 0);
458 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
459 Constant *UniqueMemberAddr);
460 bool tryUniqueRetValOpt(unsigned BitWidth,
461 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
462 CallSiteInfo &CSInfo,
463 WholeProgramDevirtResolution::ByArg *Res,
464 VTableSlot Slot, ArrayRef<uint64_t> Args);
466 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
467 Constant *Byte, Constant *Bit);
468 bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
469 VTableSlotInfo &SlotInfo,
470 WholeProgramDevirtResolution *Res, VTableSlot Slot);
472 void rebuildGlobal(VTableBits &B);
474 // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
475 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
477 // If we were able to eliminate all unsafe uses for a type checked load,
478 // eliminate the associated type tests by replacing them with true.
479 void removeRedundantTypeTests();
483 // Lower the module using the action and summary passed as command line
484 // arguments. For testing purposes only.
485 static bool runForTesting(Module &M,
486 function_ref<AAResults &(Function &)> AARGetter);
489 struct WholeProgramDevirt : public ModulePass {
492 bool UseCommandLine = false;
494 ModuleSummaryIndex *ExportSummary;
495 const ModuleSummaryIndex *ImportSummary;
497 WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
498 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
501 WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
502 const ModuleSummaryIndex *ImportSummary)
503 : ModulePass(ID), ExportSummary(ExportSummary),
504 ImportSummary(ImportSummary) {
505 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
508 bool runOnModule(Module &M) override {
512 return DevirtModule::runForTesting(M, LegacyAARGetter(*this));
513 return DevirtModule(M, LegacyAARGetter(*this), ExportSummary, ImportSummary)
517 void getAnalysisUsage(AnalysisUsage &AU) const override {
518 AU.addRequired<AssumptionCacheTracker>();
519 AU.addRequired<TargetLibraryInfoWrapperPass>();
523 } // end anonymous namespace
525 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
526 "Whole program devirtualization", false, false)
527 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
528 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
529 INITIALIZE_PASS_END(WholeProgramDevirt, "wholeprogramdevirt",
530 "Whole program devirtualization", false, false)
531 char WholeProgramDevirt::ID = 0;
534 llvm::createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
535 const ModuleSummaryIndex *ImportSummary) {
536 return new WholeProgramDevirt(ExportSummary, ImportSummary);
539 PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
540 ModuleAnalysisManager &AM) {
541 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
542 auto AARGetter = [&](Function &F) -> AAResults & {
543 return FAM.getResult<AAManager>(F);
545 if (!DevirtModule(M, AARGetter, nullptr, nullptr).run())
546 return PreservedAnalyses::all();
547 return PreservedAnalyses::none();
550 bool DevirtModule::runForTesting(
551 Module &M, function_ref<AAResults &(Function &)> AARGetter) {
552 ModuleSummaryIndex Summary;
554 // Handle the command-line summary arguments. This code is for testing
555 // purposes only, so we handle errors directly.
556 if (!ClReadSummary.empty()) {
557 ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
559 auto ReadSummaryFile =
560 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
562 yaml::Input In(ReadSummaryFile->getBuffer());
564 ExitOnErr(errorCodeToError(In.error()));
570 ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
571 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
574 if (!ClWriteSummary.empty()) {
575 ExitOnError ExitOnErr(
576 "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
578 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text);
579 ExitOnErr(errorCodeToError(EC));
581 yaml::Output Out(OS);
588 void DevirtModule::buildTypeIdentifierMap(
589 std::vector<VTableBits> &Bits,
590 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
591 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
592 Bits.reserve(M.getGlobalList().size());
593 SmallVector<MDNode *, 2> Types;
594 for (GlobalVariable &GV : M.globals()) {
596 GV.getMetadata(LLVMContext::MD_type, Types);
600 VTableBits *&BitsPtr = GVToBits[&GV];
603 Bits.back().GV = &GV;
604 Bits.back().ObjectSize =
605 M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
606 BitsPtr = &Bits.back();
609 for (MDNode *Type : Types) {
610 auto TypeID = Type->getOperand(1).get();
614 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
617 TypeIdMap[TypeID].insert({BitsPtr, Offset});
622 Constant *DevirtModule::getPointerAtOffset(Constant *I, uint64_t Offset) {
623 if (I->getType()->isPointerTy()) {
629 const DataLayout &DL = M.getDataLayout();
631 if (auto *C = dyn_cast<ConstantStruct>(I)) {
632 const StructLayout *SL = DL.getStructLayout(C->getType());
633 if (Offset >= SL->getSizeInBytes())
636 unsigned Op = SL->getElementContainingOffset(Offset);
637 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
638 Offset - SL->getElementOffset(Op));
640 if (auto *C = dyn_cast<ConstantArray>(I)) {
641 ArrayType *VTableTy = C->getType();
642 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
644 unsigned Op = Offset / ElemSize;
645 if (Op >= C->getNumOperands())
648 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
654 bool DevirtModule::tryFindVirtualCallTargets(
655 std::vector<VirtualCallTarget> &TargetsForSlot,
656 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
657 for (const TypeMemberInfo &TM : TypeMemberInfos) {
658 if (!TM.Bits->GV->isConstant())
661 Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
662 TM.Offset + ByteOffset);
666 auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
670 // We can disregard __cxa_pure_virtual as a possible call target, as
671 // calls to pure virtuals are UB.
672 if (Fn->getName() == "__cxa_pure_virtual")
675 TargetsForSlot.push_back({Fn, &TM});
678 // Give up if we couldn't find any targets.
679 return !TargetsForSlot.empty();
682 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
683 Constant *TheFn, bool &IsExported) {
684 auto Apply = [&](CallSiteInfo &CSInfo) {
685 for (auto &&VCallSite : CSInfo.CallSites) {
687 VCallSite.emitRemark("single-impl", TheFn->getName());
688 VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
689 TheFn, VCallSite.CS.getCalledValue()->getType()));
690 // This use is no longer unsafe.
691 if (VCallSite.NumUnsafeUses)
692 --*VCallSite.NumUnsafeUses;
694 if (CSInfo.isExported()) {
699 Apply(SlotInfo.CSInfo);
700 for (auto &P : SlotInfo.ConstCSInfo)
704 bool DevirtModule::trySingleImplDevirt(
705 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
706 VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
707 // See if the program contains a single implementation of this virtual
709 Function *TheFn = TargetsForSlot[0].Fn;
710 for (auto &&Target : TargetsForSlot)
711 if (TheFn != Target.Fn)
714 // If so, update each call site to call that implementation directly.
716 TargetsForSlot[0].WasDevirt = true;
718 bool IsExported = false;
719 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
723 // If the only implementation has local linkage, we must promote to external
724 // to make it visible to thin LTO objects. We can only get here during the
725 // ThinLTO export phase.
726 if (TheFn->hasLocalLinkage()) {
727 TheFn->setLinkage(GlobalValue::ExternalLinkage);
728 TheFn->setVisibility(GlobalValue::HiddenVisibility);
729 TheFn->setName(TheFn->getName() + "$merged");
732 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
733 Res->SingleImplName = TheFn->getName();
738 bool DevirtModule::tryEvaluateFunctionsWithArgs(
739 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
740 ArrayRef<uint64_t> Args) {
741 // Evaluate each function and store the result in each target's RetVal
743 for (VirtualCallTarget &Target : TargetsForSlot) {
744 if (Target.Fn->arg_size() != Args.size() + 1)
747 Evaluator Eval(M.getDataLayout(), nullptr);
748 SmallVector<Constant *, 2> EvalArgs;
750 Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
751 for (unsigned I = 0; I != Args.size(); ++I) {
752 auto *ArgTy = dyn_cast<IntegerType>(
753 Target.Fn->getFunctionType()->getParamType(I + 1));
756 EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
760 if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
761 !isa<ConstantInt>(RetVal))
763 Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
768 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
769 uint64_t TheRetVal) {
770 for (auto Call : CSInfo.CallSites)
771 Call.replaceAndErase(
772 "uniform-ret-val", FnName, RemarksEnabled,
773 ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
777 bool DevirtModule::tryUniformRetValOpt(
778 MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
779 WholeProgramDevirtResolution::ByArg *Res) {
780 // Uniform return value optimization. If all functions return the same
781 // constant, replace all calls with that constant.
782 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
783 for (const VirtualCallTarget &Target : TargetsForSlot)
784 if (Target.RetVal != TheRetVal)
787 if (CSInfo.isExported()) {
788 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
789 Res->Info = TheRetVal;
792 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
794 for (auto &&Target : TargetsForSlot)
795 Target.WasDevirt = true;
799 std::string DevirtModule::getGlobalName(VTableSlot Slot,
800 ArrayRef<uint64_t> Args,
802 std::string FullName = "__typeid_";
803 raw_string_ostream OS(FullName);
804 OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
805 for (uint64_t Arg : Args)
811 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
812 StringRef Name, Constant *C) {
813 GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
814 getGlobalName(Slot, Args, Name), C, &M);
815 GA->setVisibility(GlobalValue::HiddenVisibility);
818 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
819 StringRef Name, unsigned AbsWidth) {
820 Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
821 auto *GV = dyn_cast<GlobalVariable>(C);
822 // We only need to set metadata if the global is newly created, in which
823 // case it would not have hidden visibility.
824 if (!GV || GV->getVisibility() == GlobalValue::HiddenVisibility)
827 GV->setVisibility(GlobalValue::HiddenVisibility);
828 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
829 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
830 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
831 GV->setMetadata(LLVMContext::MD_absolute_symbol,
832 MDNode::get(M.getContext(), {MinC, MaxC}));
834 if (AbsWidth == IntPtrTy->getBitWidth())
835 SetAbsRange(~0ull, ~0ull); // Full set.
837 SetAbsRange(0, 1ull << AbsWidth);
841 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
843 Constant *UniqueMemberAddr) {
844 for (auto &&Call : CSInfo.CallSites) {
845 IRBuilder<> B(Call.CS.getInstruction());
846 Value *Cmp = B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
847 Call.VTable, UniqueMemberAddr);
848 Cmp = B.CreateZExt(Cmp, Call.CS->getType());
849 Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, Cmp);
854 bool DevirtModule::tryUniqueRetValOpt(
855 unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
856 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
857 VTableSlot Slot, ArrayRef<uint64_t> Args) {
858 // IsOne controls whether we look for a 0 or a 1.
859 auto tryUniqueRetValOptFor = [&](bool IsOne) {
860 const TypeMemberInfo *UniqueMember = nullptr;
861 for (const VirtualCallTarget &Target : TargetsForSlot) {
862 if (Target.RetVal == (IsOne ? 1 : 0)) {
865 UniqueMember = Target.TM;
869 // We should have found a unique member or bailed out by now. We already
870 // checked for a uniform return value in tryUniformRetValOpt.
871 assert(UniqueMember);
873 Constant *UniqueMemberAddr =
874 ConstantExpr::getBitCast(UniqueMember->Bits->GV, Int8PtrTy);
875 UniqueMemberAddr = ConstantExpr::getGetElementPtr(
876 Int8Ty, UniqueMemberAddr,
877 ConstantInt::get(Int64Ty, UniqueMember->Offset));
879 if (CSInfo.isExported()) {
880 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
883 exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
886 // Replace each call with the comparison.
887 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
890 // Update devirtualization statistics for targets.
892 for (auto &&Target : TargetsForSlot)
893 Target.WasDevirt = true;
899 if (tryUniqueRetValOptFor(true))
901 if (tryUniqueRetValOptFor(false))
907 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
908 Constant *Byte, Constant *Bit) {
909 for (auto Call : CSInfo.CallSites) {
910 auto *RetType = cast<IntegerType>(Call.CS.getType());
911 IRBuilder<> B(Call.CS.getInstruction());
912 Value *Addr = B.CreateGEP(Int8Ty, Call.VTable, Byte);
913 if (RetType->getBitWidth() == 1) {
914 Value *Bits = B.CreateLoad(Addr);
915 Value *BitsAndBit = B.CreateAnd(Bits, Bit);
916 auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
917 Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
920 Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
921 Value *Val = B.CreateLoad(RetType, ValAddr);
922 Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled, Val);
928 bool DevirtModule::tryVirtualConstProp(
929 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
930 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
931 // This only works if the function returns an integer.
932 auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
935 unsigned BitWidth = RetType->getBitWidth();
939 // Make sure that each function is defined, does not access memory, takes at
940 // least one argument, does not use its first argument (which we assume is
941 // 'this'), and has the same return type.
943 // Note that we test whether this copy of the function is readnone, rather
944 // than testing function attributes, which must hold for any copy of the
945 // function, even a less optimized version substituted at link time. This is
946 // sound because the virtual constant propagation optimizations effectively
947 // inline all implementations of the virtual function into each call site,
948 // rather than using function attributes to perform local optimization.
949 for (VirtualCallTarget &Target : TargetsForSlot) {
950 if (Target.Fn->isDeclaration() ||
951 computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
953 Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
954 Target.Fn->getReturnType() != RetType)
958 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
959 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
962 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
964 ResByArg = &Res->ResByArg[CSByConstantArg.first];
966 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
969 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
970 ResByArg, Slot, CSByConstantArg.first))
973 // Find an allocation offset in bits in all vtables associated with the
975 uint64_t AllocBefore =
976 findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
977 uint64_t AllocAfter =
978 findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
980 // Calculate the total amount of padding needed to store a value at both
981 // ends of the object.
982 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
983 for (auto &&Target : TargetsForSlot) {
984 TotalPaddingBefore += std::max<int64_t>(
985 (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
986 TotalPaddingAfter += std::max<int64_t>(
987 (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
990 // If the amount of padding is too large, give up.
991 // FIXME: do something smarter here.
992 if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
995 // Calculate the offset to the value as a (possibly negative) byte offset
996 // and (if applicable) a bit offset, and store the values in the targets.
999 if (TotalPaddingBefore <= TotalPaddingAfter)
1000 setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1003 setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1007 for (auto &&Target : TargetsForSlot)
1008 Target.WasDevirt = true;
1010 Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1011 Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1013 if (CSByConstantArg.second.isExported()) {
1014 ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;
1015 exportGlobal(Slot, CSByConstantArg.first, "byte",
1016 ConstantExpr::getIntToPtr(ByteConst, Int8PtrTy));
1017 exportGlobal(Slot, CSByConstantArg.first, "bit",
1018 ConstantExpr::getIntToPtr(BitConst, Int8PtrTy));
1021 // Rewrite each call to a load from OffsetByte/OffsetBit.
1022 applyVirtualConstProp(CSByConstantArg.second,
1023 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1028 void DevirtModule::rebuildGlobal(VTableBits &B) {
1029 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1032 // Align each byte array to pointer width.
1033 unsigned PointerSize = M.getDataLayout().getPointerSize();
1034 B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
1035 B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));
1037 // Before was stored in reverse order; flip it now.
1038 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1039 std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1041 // Build an anonymous global containing the before bytes, followed by the
1042 // original initializer, followed by the after bytes.
1043 auto NewInit = ConstantStruct::getAnon(
1044 {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1045 B.GV->getInitializer(),
1046 ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1048 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1049 GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1050 NewGV->setSection(B.GV->getSection());
1051 NewGV->setComdat(B.GV->getComdat());
1053 // Copy the original vtable's metadata to the anonymous global, adjusting
1054 // offsets as required.
1055 NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1057 // Build an alias named after the original global, pointing at the second
1058 // element (the original initializer).
1059 auto Alias = GlobalAlias::create(
1060 B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1061 ConstantExpr::getGetElementPtr(
1062 NewInit->getType(), NewGV,
1063 ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
1064 ConstantInt::get(Int32Ty, 1)}),
1066 Alias->setVisibility(B.GV->getVisibility());
1067 Alias->takeName(B.GV);
1069 B.GV->replaceAllUsesWith(Alias);
1070 B.GV->eraseFromParent();
1073 bool DevirtModule::areRemarksEnabled() {
1074 const auto &FL = M.getFunctionList();
1077 const Function &Fn = FL.front();
1079 const auto &BBL = Fn.getBasicBlockList();
1082 auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1083 return DI.isEnabled();
1086 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1087 Function *AssumeFunc) {
1088 // Find all virtual calls via a virtual table pointer %p under an assumption
1089 // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1090 // points to a member of the type identifier %md. Group calls by (type ID,
1091 // offset) pair (effectively the identity of the virtual function) and store
1093 DenseSet<Value *> SeenPtrs;
1094 for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1096 auto CI = dyn_cast<CallInst>(I->getUser());
1101 // Search for virtual calls based on %p and add them to DevirtCalls.
1102 SmallVector<DevirtCallSite, 1> DevirtCalls;
1103 SmallVector<CallInst *, 1> Assumes;
1104 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
1106 // If we found any, add them to CallSlots. Only do this if we haven't seen
1107 // the vtable pointer before, as it may have been CSE'd with pointers from
1108 // other call sites, and we don't want to process call sites multiple times.
1109 if (!Assumes.empty()) {
1111 cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1112 Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1113 if (SeenPtrs.insert(Ptr).second) {
1114 for (DevirtCallSite Call : DevirtCalls) {
1115 CallSlots[{TypeId, Call.Offset}].addCallSite(CI->getArgOperand(0),
1121 // We no longer need the assumes or the type test.
1122 for (auto Assume : Assumes)
1123 Assume->eraseFromParent();
1124 // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1125 // may use the vtable argument later.
1126 if (CI->use_empty())
1127 CI->eraseFromParent();
1131 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1132 Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1134 for (auto I = TypeCheckedLoadFunc->use_begin(),
1135 E = TypeCheckedLoadFunc->use_end();
1137 auto CI = dyn_cast<CallInst>(I->getUser());
1142 Value *Ptr = CI->getArgOperand(0);
1143 Value *Offset = CI->getArgOperand(1);
1144 Value *TypeIdValue = CI->getArgOperand(2);
1145 Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1147 SmallVector<DevirtCallSite, 1> DevirtCalls;
1148 SmallVector<Instruction *, 1> LoadedPtrs;
1149 SmallVector<Instruction *, 1> Preds;
1150 bool HasNonCallUses = false;
1151 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1152 HasNonCallUses, CI);
1154 // Start by generating "pessimistic" code that explicitly loads the function
1155 // pointer from the vtable and performs the type check. If possible, we will
1156 // eliminate the load and the type check later.
1158 // If possible, only generate the load at the point where it is used.
1159 // This helps avoid unnecessary spills.
1161 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1162 Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1163 Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1164 Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1166 for (Instruction *LoadedPtr : LoadedPtrs) {
1167 LoadedPtr->replaceAllUsesWith(LoadedValue);
1168 LoadedPtr->eraseFromParent();
1171 // Likewise for the type test.
1172 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1173 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1175 for (Instruction *Pred : Preds) {
1176 Pred->replaceAllUsesWith(TypeTestCall);
1177 Pred->eraseFromParent();
1180 // We have already erased any extractvalue instructions that refer to the
1181 // intrinsic call, but the intrinsic may have other non-extractvalue uses
1182 // (although this is unlikely). In that case, explicitly build a pair and
1184 if (!CI->use_empty()) {
1185 Value *Pair = UndefValue::get(CI->getType());
1187 Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1188 Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1189 CI->replaceAllUsesWith(Pair);
1192 // The number of unsafe uses is initially the number of uses.
1193 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1194 NumUnsafeUses = DevirtCalls.size();
1196 // If the function pointer has a non-call user, we cannot eliminate the type
1197 // check, as one of those users may eventually call the pointer. Increment
1198 // the unsafe use count to make sure it cannot reach zero.
1201 for (DevirtCallSite Call : DevirtCalls) {
1202 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1206 CI->eraseFromParent();
1210 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1211 const TypeIdSummary *TidSummary =
1212 ImportSummary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString());
1215 auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1216 if (ResI == TidSummary->WPDRes.end())
1218 const WholeProgramDevirtResolution &Res = ResI->second;
1220 if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
1221 // The type of the function in the declaration is irrelevant because every
1222 // call site will cast it to the correct type.
1223 auto *SingleImpl = M.getOrInsertFunction(
1224 Res.SingleImplName, Type::getVoidTy(M.getContext()));
1226 // This is the import phase so we should not be exporting anything.
1227 bool IsExported = false;
1228 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1229 assert(!IsExported);
1232 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1233 auto I = Res.ResByArg.find(CSByConstantArg.first);
1234 if (I == Res.ResByArg.end())
1236 auto &ResByArg = I->second;
1237 // FIXME: We should figure out what to do about the "function name" argument
1238 // to the apply* functions, as the function names are unavailable during the
1239 // importing phase. For now we just pass the empty string. This does not
1240 // impact correctness because the function names are just used for remarks.
1241 switch (ResByArg.TheKind) {
1242 case WholeProgramDevirtResolution::ByArg::UniformRetVal:
1243 applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1245 case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
1246 Constant *UniqueMemberAddr =
1247 importGlobal(Slot, CSByConstantArg.first, "unique_member");
1248 applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1252 case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
1253 Constant *Byte = importGlobal(Slot, CSByConstantArg.first, "byte", 32);
1254 Byte = ConstantExpr::getPtrToInt(Byte, Int32Ty);
1255 Constant *Bit = importGlobal(Slot, CSByConstantArg.first, "bit", 8);
1256 Bit = ConstantExpr::getPtrToInt(Bit, Int8Ty);
1257 applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1265 void DevirtModule::removeRedundantTypeTests() {
1266 auto True = ConstantInt::getTrue(M.getContext());
1267 for (auto &&U : NumUnsafeUsesForTypeTest) {
1268 if (U.second == 0) {
1269 U.first->replaceAllUsesWith(True);
1270 U.first->eraseFromParent();
1275 bool DevirtModule::run() {
1276 Function *TypeTestFunc =
1277 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1278 Function *TypeCheckedLoadFunc =
1279 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1280 Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1282 // Normally if there are no users of the devirtualization intrinsics in the
1283 // module, this pass has nothing to do. But if we are exporting, we also need
1284 // to handle any users that appear only in the function summaries.
1285 if (!ExportSummary &&
1286 (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1287 AssumeFunc->use_empty()) &&
1288 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1291 if (TypeTestFunc && AssumeFunc)
1292 scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1294 if (TypeCheckedLoadFunc)
1295 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1297 if (ImportSummary) {
1298 for (auto &S : CallSlots)
1299 importResolution(S.first, S.second);
1301 removeRedundantTypeTests();
1303 // The rest of the code is only necessary when exporting or during regular
1304 // LTO, so we are done.
1308 // Rebuild type metadata into a map for easy lookup.
1309 std::vector<VTableBits> Bits;
1310 DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
1311 buildTypeIdentifierMap(Bits, TypeIdMap);
1312 if (TypeIdMap.empty())
1315 // Collect information from summary about which calls to try to devirtualize.
1316 if (ExportSummary) {
1317 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
1318 for (auto &P : TypeIdMap) {
1319 if (auto *TypeId = dyn_cast<MDString>(P.first))
1320 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1324 for (auto &P : *ExportSummary) {
1325 for (auto &S : P.second.SummaryList) {
1326 auto *FS = dyn_cast<FunctionSummary>(S.get());
1329 // FIXME: Only add live functions.
1330 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1331 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1332 CallSlots[{MD, VF.Offset}].CSInfo.SummaryHasTypeTestAssumeUsers =
1336 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1337 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1338 CallSlots[{MD, VF.Offset}]
1339 .CSInfo.SummaryTypeCheckedLoadUsers.push_back(FS);
1342 for (const FunctionSummary::ConstVCall &VC :
1343 FS->type_test_assume_const_vcalls()) {
1344 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1345 CallSlots[{MD, VC.VFunc.Offset}]
1346 .ConstCSInfo[VC.Args]
1347 .SummaryHasTypeTestAssumeUsers = true;
1350 for (const FunctionSummary::ConstVCall &VC :
1351 FS->type_checked_load_const_vcalls()) {
1352 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1353 CallSlots[{MD, VC.VFunc.Offset}]
1354 .ConstCSInfo[VC.Args]
1355 .SummaryTypeCheckedLoadUsers.push_back(FS);
1362 // For each (type, offset) pair:
1363 bool DidVirtualConstProp = false;
1364 std::map<std::string, Function*> DevirtTargets;
1365 for (auto &S : CallSlots) {
1366 // Search each of the members of the type identifier for the virtual
1367 // function implementation at offset S.first.ByteOffset, and add to
1369 std::vector<VirtualCallTarget> TargetsForSlot;
1370 if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
1371 S.first.ByteOffset)) {
1372 WholeProgramDevirtResolution *Res = nullptr;
1373 if (ExportSummary && isa<MDString>(S.first.TypeID))
1374 Res = &ExportSummary
1375 ->getOrInsertTypeIdSummary(
1376 cast<MDString>(S.first.TypeID)->getString())
1377 .WPDRes[S.first.ByteOffset];
1379 if (!trySingleImplDevirt(TargetsForSlot, S.second, Res) &&
1380 tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first))
1381 DidVirtualConstProp = true;
1383 // Collect functions devirtualized at least for one call site for stats.
1385 for (const auto &T : TargetsForSlot)
1387 DevirtTargets[T.Fn->getName()] = T.Fn;
1390 // CFI-specific: if we are exporting and any llvm.type.checked.load
1391 // intrinsics were *not* devirtualized, we need to add the resulting
1392 // llvm.type.test intrinsics to the function summaries so that the
1393 // LowerTypeTests pass will export them.
1394 if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1396 GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1397 for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1398 FS->addTypeTest(GUID);
1399 for (auto &CCS : S.second.ConstCSInfo)
1400 for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1401 FS->addTypeTest(GUID);
1405 if (RemarksEnabled) {
1406 // Generate remarks for each devirtualized function.
1407 for (const auto &DT : DevirtTargets) {
1408 Function *F = DT.second;
1409 DISubprogram *SP = F->getSubprogram();
1410 emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, SP,
1411 Twine("devirtualized ") + F->getName());
1415 removeRedundantTypeTests();
1417 // Rebuild each global we touched as part of virtual constant propagation to
1418 // include the before and after bytes.
1419 if (DidVirtualConstProp)
1420 for (VTableBits &B : Bits)