[ASan] Make insertion of version mismatch guard configurable
[llvm-core.git] / lib / Transforms / IPO / WholeProgramDevirt.cpp
blob4490a7ef62adf008cd0180ccbe2f236709f9fc38
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.
27 // 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).
34 // During hybrid Regular/ThinLTO, the pass operates in two phases:
35 // - Export phase: this is run during the thin link over a single merged module
36 // that contains all vtables with !type metadata that participate in the link.
37 // The pass computes a resolution for each virtual call and stores it in the
38 // type identifier summary.
39 // - Import phase: this is run during the thin backends over the individual
40 // modules. The pass applies the resolutions previously computed during the
41 // import phase to each eligible virtual call.
43 // During ThinLTO, the pass operates in two phases:
44 // - Export phase: this is run during the thin link over the index which
45 // contains a summary of all vtables with !type metadata that participate in
46 // the link. It computes a resolution for each virtual call and stores it in
47 // the type identifier summary. Only single implementation devirtualization
48 // is supported.
49 // - Import phase: (same as with hybrid case above).
51 //===----------------------------------------------------------------------===//
53 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
54 #include "llvm/ADT/ArrayRef.h"
55 #include "llvm/ADT/DenseMap.h"
56 #include "llvm/ADT/DenseMapInfo.h"
57 #include "llvm/ADT/DenseSet.h"
58 #include "llvm/ADT/MapVector.h"
59 #include "llvm/ADT/SmallVector.h"
60 #include "llvm/ADT/iterator_range.h"
61 #include "llvm/Analysis/AliasAnalysis.h"
62 #include "llvm/Analysis/BasicAliasAnalysis.h"
63 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
64 #include "llvm/Analysis/TypeMetadataUtils.h"
65 #include "llvm/IR/CallSite.h"
66 #include "llvm/IR/Constants.h"
67 #include "llvm/IR/DataLayout.h"
68 #include "llvm/IR/DebugLoc.h"
69 #include "llvm/IR/DerivedTypes.h"
70 #include "llvm/IR/Dominators.h"
71 #include "llvm/IR/Function.h"
72 #include "llvm/IR/GlobalAlias.h"
73 #include "llvm/IR/GlobalVariable.h"
74 #include "llvm/IR/IRBuilder.h"
75 #include "llvm/IR/InstrTypes.h"
76 #include "llvm/IR/Instruction.h"
77 #include "llvm/IR/Instructions.h"
78 #include "llvm/IR/Intrinsics.h"
79 #include "llvm/IR/LLVMContext.h"
80 #include "llvm/IR/Metadata.h"
81 #include "llvm/IR/Module.h"
82 #include "llvm/IR/ModuleSummaryIndexYAML.h"
83 #include "llvm/Pass.h"
84 #include "llvm/PassRegistry.h"
85 #include "llvm/PassSupport.h"
86 #include "llvm/Support/Casting.h"
87 #include "llvm/Support/Error.h"
88 #include "llvm/Support/FileSystem.h"
89 #include "llvm/Support/MathExtras.h"
90 #include "llvm/Transforms/IPO.h"
91 #include "llvm/Transforms/IPO/FunctionAttrs.h"
92 #include "llvm/Transforms/Utils/Evaluator.h"
93 #include <algorithm>
94 #include <cstddef>
95 #include <map>
96 #include <set>
97 #include <string>
99 using namespace llvm;
100 using namespace wholeprogramdevirt;
102 #define DEBUG_TYPE "wholeprogramdevirt"
104 static cl::opt<PassSummaryAction> ClSummaryAction(
105 "wholeprogramdevirt-summary-action",
106 cl::desc("What to do with the summary when running this pass"),
107 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
108 clEnumValN(PassSummaryAction::Import, "import",
109 "Import typeid resolutions from summary and globals"),
110 clEnumValN(PassSummaryAction::Export, "export",
111 "Export typeid resolutions to summary and globals")),
112 cl::Hidden);
114 static cl::opt<std::string> ClReadSummary(
115 "wholeprogramdevirt-read-summary",
116 cl::desc("Read summary from given YAML file before running pass"),
117 cl::Hidden);
119 static cl::opt<std::string> ClWriteSummary(
120 "wholeprogramdevirt-write-summary",
121 cl::desc("Write summary to given YAML file after running pass"),
122 cl::Hidden);
124 static cl::opt<unsigned>
125 ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
126 cl::init(10), cl::ZeroOrMore,
127 cl::desc("Maximum number of call targets per "
128 "call site to enable branch funnels"));
130 static cl::opt<bool>
131 PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,
132 cl::init(false), cl::ZeroOrMore,
133 cl::desc("Print index-based devirtualization messages"));
135 // Find the minimum offset that we may store a value of size Size bits at. If
136 // IsAfter is set, look for an offset before the object, otherwise look for an
137 // offset after the object.
138 uint64_t
139 wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
140 bool IsAfter, uint64_t Size) {
141 // Find a minimum offset taking into account only vtable sizes.
142 uint64_t MinByte = 0;
143 for (const VirtualCallTarget &Target : Targets) {
144 if (IsAfter)
145 MinByte = std::max(MinByte, Target.minAfterBytes());
146 else
147 MinByte = std::max(MinByte, Target.minBeforeBytes());
150 // Build a vector of arrays of bytes covering, for each target, a slice of the
151 // used region (see AccumBitVector::BytesUsed in
152 // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
153 // this aligns the used regions to start at MinByte.
155 // In this example, A, B and C are vtables, # is a byte already allocated for
156 // a virtual function pointer, AAAA... (etc.) are the used regions for the
157 // vtables and Offset(X) is the value computed for the Offset variable below
158 // for X.
160 // Offset(A)
161 // | |
162 // |MinByte
163 // A: ################AAAAAAAA|AAAAAAAA
164 // B: ########BBBBBBBBBBBBBBBB|BBBB
165 // C: ########################|CCCCCCCCCCCCCCCC
166 // | Offset(B) |
168 // This code produces the slices of A, B and C that appear after the divider
169 // at MinByte.
170 std::vector<ArrayRef<uint8_t>> Used;
171 for (const VirtualCallTarget &Target : Targets) {
172 ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
173 : Target.TM->Bits->Before.BytesUsed;
174 uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
175 : MinByte - Target.minBeforeBytes();
177 // Disregard used regions that are smaller than Offset. These are
178 // effectively all-free regions that do not need to be checked.
179 if (VTUsed.size() > Offset)
180 Used.push_back(VTUsed.slice(Offset));
183 if (Size == 1) {
184 // Find a free bit in each member of Used.
185 for (unsigned I = 0;; ++I) {
186 uint8_t BitsUsed = 0;
187 for (auto &&B : Used)
188 if (I < B.size())
189 BitsUsed |= B[I];
190 if (BitsUsed != 0xff)
191 return (MinByte + I) * 8 +
192 countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
194 } else {
195 // Find a free (Size/8) byte region in each member of Used.
196 // FIXME: see if alignment helps.
197 for (unsigned I = 0;; ++I) {
198 for (auto &&B : Used) {
199 unsigned Byte = 0;
200 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
201 if (B[I + Byte])
202 goto NextI;
203 ++Byte;
206 return (MinByte + I) * 8;
207 NextI:;
212 void wholeprogramdevirt::setBeforeReturnValues(
213 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
214 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
215 if (BitWidth == 1)
216 OffsetByte = -(AllocBefore / 8 + 1);
217 else
218 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
219 OffsetBit = AllocBefore % 8;
221 for (VirtualCallTarget &Target : Targets) {
222 if (BitWidth == 1)
223 Target.setBeforeBit(AllocBefore);
224 else
225 Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
229 void wholeprogramdevirt::setAfterReturnValues(
230 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
231 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
232 if (BitWidth == 1)
233 OffsetByte = AllocAfter / 8;
234 else
235 OffsetByte = (AllocAfter + 7) / 8;
236 OffsetBit = AllocAfter % 8;
238 for (VirtualCallTarget &Target : Targets) {
239 if (BitWidth == 1)
240 Target.setAfterBit(AllocAfter);
241 else
242 Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
246 VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
247 : Fn(Fn), TM(TM),
248 IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
250 namespace {
252 // A slot in a set of virtual tables. The TypeID identifies the set of virtual
253 // tables, and the ByteOffset is the offset in bytes from the address point to
254 // the virtual function pointer.
255 struct VTableSlot {
256 Metadata *TypeID;
257 uint64_t ByteOffset;
260 } // end anonymous namespace
262 namespace llvm {
264 template <> struct DenseMapInfo<VTableSlot> {
265 static VTableSlot getEmptyKey() {
266 return {DenseMapInfo<Metadata *>::getEmptyKey(),
267 DenseMapInfo<uint64_t>::getEmptyKey()};
269 static VTableSlot getTombstoneKey() {
270 return {DenseMapInfo<Metadata *>::getTombstoneKey(),
271 DenseMapInfo<uint64_t>::getTombstoneKey()};
273 static unsigned getHashValue(const VTableSlot &I) {
274 return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
275 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
277 static bool isEqual(const VTableSlot &LHS,
278 const VTableSlot &RHS) {
279 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
283 template <> struct DenseMapInfo<VTableSlotSummary> {
284 static VTableSlotSummary getEmptyKey() {
285 return {DenseMapInfo<StringRef>::getEmptyKey(),
286 DenseMapInfo<uint64_t>::getEmptyKey()};
288 static VTableSlotSummary getTombstoneKey() {
289 return {DenseMapInfo<StringRef>::getTombstoneKey(),
290 DenseMapInfo<uint64_t>::getTombstoneKey()};
292 static unsigned getHashValue(const VTableSlotSummary &I) {
293 return DenseMapInfo<StringRef>::getHashValue(I.TypeID) ^
294 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
296 static bool isEqual(const VTableSlotSummary &LHS,
297 const VTableSlotSummary &RHS) {
298 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
302 } // end namespace llvm
304 namespace {
306 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
307 // the indirect virtual call.
308 struct VirtualCallSite {
309 Value *VTable;
310 CallSite CS;
312 // If non-null, this field points to the associated unsafe use count stored in
313 // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
314 // of that field for details.
315 unsigned *NumUnsafeUses;
317 void
318 emitRemark(const StringRef OptName, const StringRef TargetName,
319 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter) {
320 Function *F = CS.getCaller();
321 DebugLoc DLoc = CS->getDebugLoc();
322 BasicBlock *Block = CS.getParent();
324 using namespace ore;
325 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
326 << NV("Optimization", OptName)
327 << ": devirtualized a call to "
328 << NV("FunctionName", TargetName));
331 void replaceAndErase(
332 const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
333 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
334 Value *New) {
335 if (RemarksEnabled)
336 emitRemark(OptName, TargetName, OREGetter);
337 CS->replaceAllUsesWith(New);
338 if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
339 BranchInst::Create(II->getNormalDest(), CS.getInstruction());
340 II->getUnwindDest()->removePredecessor(II->getParent());
342 CS->eraseFromParent();
343 // This use is no longer unsafe.
344 if (NumUnsafeUses)
345 --*NumUnsafeUses;
349 // Call site information collected for a specific VTableSlot and possibly a list
350 // of constant integer arguments. The grouping by arguments is handled by the
351 // VTableSlotInfo class.
352 struct CallSiteInfo {
353 /// The set of call sites for this slot. Used during regular LTO and the
354 /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
355 /// call sites that appear in the merged module itself); in each of these
356 /// cases we are directly operating on the call sites at the IR level.
357 std::vector<VirtualCallSite> CallSites;
359 /// Whether all call sites represented by this CallSiteInfo, including those
360 /// in summaries, have been devirtualized. This starts off as true because a
361 /// default constructed CallSiteInfo represents no call sites.
362 bool AllCallSitesDevirted = true;
364 // These fields are used during the export phase of ThinLTO and reflect
365 // information collected from function summaries.
367 /// Whether any function summary contains an llvm.assume(llvm.type.test) for
368 /// this slot.
369 bool SummaryHasTypeTestAssumeUsers = false;
371 /// CFI-specific: a vector containing the list of function summaries that use
372 /// the llvm.type.checked.load intrinsic and therefore will require
373 /// resolutions for llvm.type.test in order to implement CFI checks if
374 /// devirtualization was unsuccessful. If devirtualization was successful, the
375 /// pass will clear this vector by calling markDevirt(). If at the end of the
376 /// pass the vector is non-empty, we will need to add a use of llvm.type.test
377 /// to each of the function summaries in the vector.
378 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
379 std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
381 bool isExported() const {
382 return SummaryHasTypeTestAssumeUsers ||
383 !SummaryTypeCheckedLoadUsers.empty();
386 void markSummaryHasTypeTestAssumeUsers() {
387 SummaryHasTypeTestAssumeUsers = true;
388 AllCallSitesDevirted = false;
391 void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
392 SummaryTypeCheckedLoadUsers.push_back(FS);
393 AllCallSitesDevirted = false;
396 void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
397 SummaryTypeTestAssumeUsers.push_back(FS);
398 markSummaryHasTypeTestAssumeUsers();
401 void markDevirt() {
402 AllCallSitesDevirted = true;
404 // As explained in the comment for SummaryTypeCheckedLoadUsers.
405 SummaryTypeCheckedLoadUsers.clear();
409 // Call site information collected for a specific VTableSlot.
410 struct VTableSlotInfo {
411 // The set of call sites which do not have all constant integer arguments
412 // (excluding "this").
413 CallSiteInfo CSInfo;
415 // The set of call sites with all constant integer arguments (excluding
416 // "this"), grouped by argument list.
417 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
419 void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
421 private:
422 CallSiteInfo &findCallSiteInfo(CallSite CS);
425 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
426 std::vector<uint64_t> Args;
427 auto *CI = dyn_cast<IntegerType>(CS.getType());
428 if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
429 return CSInfo;
430 for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
431 auto *CI = dyn_cast<ConstantInt>(Arg);
432 if (!CI || CI->getBitWidth() > 64)
433 return CSInfo;
434 Args.push_back(CI->getZExtValue());
436 return ConstCSInfo[Args];
439 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
440 unsigned *NumUnsafeUses) {
441 auto &CSI = findCallSiteInfo(CS);
442 CSI.AllCallSitesDevirted = false;
443 CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
446 struct DevirtModule {
447 Module &M;
448 function_ref<AAResults &(Function &)> AARGetter;
449 function_ref<DominatorTree &(Function &)> LookupDomTree;
451 ModuleSummaryIndex *ExportSummary;
452 const ModuleSummaryIndex *ImportSummary;
454 IntegerType *Int8Ty;
455 PointerType *Int8PtrTy;
456 IntegerType *Int32Ty;
457 IntegerType *Int64Ty;
458 IntegerType *IntPtrTy;
460 bool RemarksEnabled;
461 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter;
463 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
465 // This map keeps track of the number of "unsafe" uses of a loaded function
466 // pointer. The key is the associated llvm.type.test intrinsic call generated
467 // by this pass. An unsafe use is one that calls the loaded function pointer
468 // directly. Every time we eliminate an unsafe use (for example, by
469 // devirtualizing it or by applying virtual constant propagation), we
470 // decrement the value stored in this map. If a value reaches zero, we can
471 // eliminate the type check by RAUWing the associated llvm.type.test call with
472 // true.
473 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
475 DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
476 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
477 function_ref<DominatorTree &(Function &)> LookupDomTree,
478 ModuleSummaryIndex *ExportSummary,
479 const ModuleSummaryIndex *ImportSummary)
480 : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
481 ExportSummary(ExportSummary), ImportSummary(ImportSummary),
482 Int8Ty(Type::getInt8Ty(M.getContext())),
483 Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
484 Int32Ty(Type::getInt32Ty(M.getContext())),
485 Int64Ty(Type::getInt64Ty(M.getContext())),
486 IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
487 RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
488 assert(!(ExportSummary && ImportSummary));
491 bool areRemarksEnabled();
493 void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
494 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
496 void buildTypeIdentifierMap(
497 std::vector<VTableBits> &Bits,
498 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
499 Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
500 bool
501 tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
502 const std::set<TypeMemberInfo> &TypeMemberInfos,
503 uint64_t ByteOffset);
505 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
506 bool &IsExported);
507 bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
508 VTableSlotInfo &SlotInfo,
509 WholeProgramDevirtResolution *Res);
511 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
512 bool &IsExported);
513 void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
514 VTableSlotInfo &SlotInfo,
515 WholeProgramDevirtResolution *Res, VTableSlot Slot);
517 bool tryEvaluateFunctionsWithArgs(
518 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
519 ArrayRef<uint64_t> Args);
521 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
522 uint64_t TheRetVal);
523 bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
524 CallSiteInfo &CSInfo,
525 WholeProgramDevirtResolution::ByArg *Res);
527 // Returns the global symbol name that is used to export information about the
528 // given vtable slot and list of arguments.
529 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
530 StringRef Name);
532 bool shouldExportConstantsAsAbsoluteSymbols();
534 // This function is called during the export phase to create a symbol
535 // definition containing information about the given vtable slot and list of
536 // arguments.
537 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
538 Constant *C);
539 void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
540 uint32_t Const, uint32_t &Storage);
542 // This function is called during the import phase to create a reference to
543 // the symbol definition created during the export phase.
544 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
545 StringRef Name);
546 Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
547 StringRef Name, IntegerType *IntTy,
548 uint32_t Storage);
550 Constant *getMemberAddr(const TypeMemberInfo *M);
552 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
553 Constant *UniqueMemberAddr);
554 bool tryUniqueRetValOpt(unsigned BitWidth,
555 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
556 CallSiteInfo &CSInfo,
557 WholeProgramDevirtResolution::ByArg *Res,
558 VTableSlot Slot, ArrayRef<uint64_t> Args);
560 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
561 Constant *Byte, Constant *Bit);
562 bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
563 VTableSlotInfo &SlotInfo,
564 WholeProgramDevirtResolution *Res, VTableSlot Slot);
566 void rebuildGlobal(VTableBits &B);
568 // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
569 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
571 // If we were able to eliminate all unsafe uses for a type checked load,
572 // eliminate the associated type tests by replacing them with true.
573 void removeRedundantTypeTests();
575 bool run();
577 // Lower the module using the action and summary passed as command line
578 // arguments. For testing purposes only.
579 static bool
580 runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
581 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
582 function_ref<DominatorTree &(Function &)> LookupDomTree);
585 struct DevirtIndex {
586 ModuleSummaryIndex &ExportSummary;
587 // The set in which to record GUIDs exported from their module by
588 // devirtualization, used by client to ensure they are not internalized.
589 std::set<GlobalValue::GUID> &ExportedGUIDs;
590 // A map in which to record the information necessary to locate the WPD
591 // resolution for local targets in case they are exported by cross module
592 // importing.
593 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
595 MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;
597 DevirtIndex(
598 ModuleSummaryIndex &ExportSummary,
599 std::set<GlobalValue::GUID> &ExportedGUIDs,
600 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
601 : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
602 LocalWPDTargetsMap(LocalWPDTargetsMap) {}
604 bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
605 const TypeIdCompatibleVtableInfo TIdInfo,
606 uint64_t ByteOffset);
608 bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
609 VTableSlotSummary &SlotSummary,
610 VTableSlotInfo &SlotInfo,
611 WholeProgramDevirtResolution *Res,
612 std::set<ValueInfo> &DevirtTargets);
614 void run();
617 struct WholeProgramDevirt : public ModulePass {
618 static char ID;
620 bool UseCommandLine = false;
622 ModuleSummaryIndex *ExportSummary;
623 const ModuleSummaryIndex *ImportSummary;
625 WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
626 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
629 WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
630 const ModuleSummaryIndex *ImportSummary)
631 : ModulePass(ID), ExportSummary(ExportSummary),
632 ImportSummary(ImportSummary) {
633 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
636 bool runOnModule(Module &M) override {
637 if (skipModule(M))
638 return false;
640 // In the new pass manager, we can request the optimization
641 // remark emitter pass on a per-function-basis, which the
642 // OREGetter will do for us.
643 // In the old pass manager, this is harder, so we just build
644 // an optimization remark emitter on the fly, when we need it.
645 std::unique_ptr<OptimizationRemarkEmitter> ORE;
646 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
647 ORE = std::make_unique<OptimizationRemarkEmitter>(F);
648 return *ORE;
651 auto LookupDomTree = [this](Function &F) -> DominatorTree & {
652 return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
655 if (UseCommandLine)
656 return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter,
657 LookupDomTree);
659 return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree,
660 ExportSummary, ImportSummary)
661 .run();
664 void getAnalysisUsage(AnalysisUsage &AU) const override {
665 AU.addRequired<AssumptionCacheTracker>();
666 AU.addRequired<TargetLibraryInfoWrapperPass>();
667 AU.addRequired<DominatorTreeWrapperPass>();
671 } // end anonymous namespace
673 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
674 "Whole program devirtualization", false, false)
675 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
676 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
677 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
678 INITIALIZE_PASS_END(WholeProgramDevirt, "wholeprogramdevirt",
679 "Whole program devirtualization", false, false)
680 char WholeProgramDevirt::ID = 0;
682 ModulePass *
683 llvm::createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
684 const ModuleSummaryIndex *ImportSummary) {
685 return new WholeProgramDevirt(ExportSummary, ImportSummary);
688 PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
689 ModuleAnalysisManager &AM) {
690 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
691 auto AARGetter = [&](Function &F) -> AAResults & {
692 return FAM.getResult<AAManager>(F);
694 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
695 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
697 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
698 return FAM.getResult<DominatorTreeAnalysis>(F);
700 if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
701 ImportSummary)
702 .run())
703 return PreservedAnalyses::all();
704 return PreservedAnalyses::none();
707 namespace llvm {
708 void runWholeProgramDevirtOnIndex(
709 ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
710 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
711 DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
714 void updateIndexWPDForExports(
715 ModuleSummaryIndex &Summary,
716 StringMap<FunctionImporter::ExportSetTy> &ExportLists,
717 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
718 for (auto &T : LocalWPDTargetsMap) {
719 auto &VI = T.first;
720 // This was enforced earlier during trySingleImplDevirt.
721 assert(VI.getSummaryList().size() == 1 &&
722 "Devirt of local target has more than one copy");
723 auto &S = VI.getSummaryList()[0];
724 const auto &ExportList = ExportLists.find(S->modulePath());
725 if (ExportList == ExportLists.end() ||
726 !ExportList->second.count(VI.getGUID()))
727 continue;
729 // It's been exported by a cross module import.
730 for (auto &SlotSummary : T.second) {
731 auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
732 assert(TIdSum);
733 auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
734 assert(WPDRes != TIdSum->WPDRes.end());
735 WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
736 WPDRes->second.SingleImplName,
737 Summary.getModuleHash(S->modulePath()));
742 } // end namespace llvm
744 bool DevirtModule::runForTesting(
745 Module &M, function_ref<AAResults &(Function &)> AARGetter,
746 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
747 function_ref<DominatorTree &(Function &)> LookupDomTree) {
748 ModuleSummaryIndex Summary(/*HaveGVs=*/false);
750 // Handle the command-line summary arguments. This code is for testing
751 // purposes only, so we handle errors directly.
752 if (!ClReadSummary.empty()) {
753 ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
754 ": ");
755 auto ReadSummaryFile =
756 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
758 yaml::Input In(ReadSummaryFile->getBuffer());
759 In >> Summary;
760 ExitOnErr(errorCodeToError(In.error()));
763 bool Changed =
764 DevirtModule(
765 M, AARGetter, OREGetter, LookupDomTree,
766 ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
767 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
768 .run();
770 if (!ClWriteSummary.empty()) {
771 ExitOnError ExitOnErr(
772 "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
773 std::error_code EC;
774 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_Text);
775 ExitOnErr(errorCodeToError(EC));
777 yaml::Output Out(OS);
778 Out << Summary;
781 return Changed;
784 void DevirtModule::buildTypeIdentifierMap(
785 std::vector<VTableBits> &Bits,
786 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
787 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
788 Bits.reserve(M.getGlobalList().size());
789 SmallVector<MDNode *, 2> Types;
790 for (GlobalVariable &GV : M.globals()) {
791 Types.clear();
792 GV.getMetadata(LLVMContext::MD_type, Types);
793 if (GV.isDeclaration() || Types.empty())
794 continue;
796 VTableBits *&BitsPtr = GVToBits[&GV];
797 if (!BitsPtr) {
798 Bits.emplace_back();
799 Bits.back().GV = &GV;
800 Bits.back().ObjectSize =
801 M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
802 BitsPtr = &Bits.back();
805 for (MDNode *Type : Types) {
806 auto TypeID = Type->getOperand(1).get();
808 uint64_t Offset =
809 cast<ConstantInt>(
810 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
811 ->getZExtValue();
813 TypeIdMap[TypeID].insert({BitsPtr, Offset});
818 Constant *DevirtModule::getPointerAtOffset(Constant *I, uint64_t Offset) {
819 if (I->getType()->isPointerTy()) {
820 if (Offset == 0)
821 return I;
822 return nullptr;
825 const DataLayout &DL = M.getDataLayout();
827 if (auto *C = dyn_cast<ConstantStruct>(I)) {
828 const StructLayout *SL = DL.getStructLayout(C->getType());
829 if (Offset >= SL->getSizeInBytes())
830 return nullptr;
832 unsigned Op = SL->getElementContainingOffset(Offset);
833 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
834 Offset - SL->getElementOffset(Op));
836 if (auto *C = dyn_cast<ConstantArray>(I)) {
837 ArrayType *VTableTy = C->getType();
838 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
840 unsigned Op = Offset / ElemSize;
841 if (Op >= C->getNumOperands())
842 return nullptr;
844 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
845 Offset % ElemSize);
847 return nullptr;
850 bool DevirtModule::tryFindVirtualCallTargets(
851 std::vector<VirtualCallTarget> &TargetsForSlot,
852 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
853 for (const TypeMemberInfo &TM : TypeMemberInfos) {
854 if (!TM.Bits->GV->isConstant())
855 return false;
857 Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
858 TM.Offset + ByteOffset);
859 if (!Ptr)
860 return false;
862 auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
863 if (!Fn)
864 return false;
866 // We can disregard __cxa_pure_virtual as a possible call target, as
867 // calls to pure virtuals are UB.
868 if (Fn->getName() == "__cxa_pure_virtual")
869 continue;
871 TargetsForSlot.push_back({Fn, &TM});
874 // Give up if we couldn't find any targets.
875 return !TargetsForSlot.empty();
878 bool DevirtIndex::tryFindVirtualCallTargets(
879 std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo,
880 uint64_t ByteOffset) {
881 for (const TypeIdOffsetVtableInfo P : TIdInfo) {
882 // VTable initializer should have only one summary, or all copies must be
883 // linkonce/weak ODR.
884 assert(P.VTableVI.getSummaryList().size() == 1 ||
885 llvm::all_of(
886 P.VTableVI.getSummaryList(),
887 [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
888 return GlobalValue::isLinkOnceODRLinkage(Summary->linkage()) ||
889 GlobalValue::isWeakODRLinkage(Summary->linkage());
890 }));
891 const auto *VS = cast<GlobalVarSummary>(P.VTableVI.getSummaryList()[0].get());
892 if (!P.VTableVI.getSummaryList()[0]->isLive())
893 continue;
894 for (auto VTP : VS->vTableFuncs()) {
895 if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
896 continue;
898 TargetsForSlot.push_back(VTP.FuncVI);
902 // Give up if we couldn't find any targets.
903 return !TargetsForSlot.empty();
906 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
907 Constant *TheFn, bool &IsExported) {
908 auto Apply = [&](CallSiteInfo &CSInfo) {
909 for (auto &&VCallSite : CSInfo.CallSites) {
910 if (RemarksEnabled)
911 VCallSite.emitRemark("single-impl",
912 TheFn->stripPointerCasts()->getName(), OREGetter);
913 VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
914 TheFn, VCallSite.CS.getCalledValue()->getType()));
915 // This use is no longer unsafe.
916 if (VCallSite.NumUnsafeUses)
917 --*VCallSite.NumUnsafeUses;
919 if (CSInfo.isExported())
920 IsExported = true;
921 CSInfo.markDevirt();
923 Apply(SlotInfo.CSInfo);
924 for (auto &P : SlotInfo.ConstCSInfo)
925 Apply(P.second);
928 bool DevirtModule::trySingleImplDevirt(
929 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
930 VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
931 // See if the program contains a single implementation of this virtual
932 // function.
933 Function *TheFn = TargetsForSlot[0].Fn;
934 for (auto &&Target : TargetsForSlot)
935 if (TheFn != Target.Fn)
936 return false;
938 // If so, update each call site to call that implementation directly.
939 if (RemarksEnabled)
940 TargetsForSlot[0].WasDevirt = true;
942 bool IsExported = false;
943 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
944 if (!IsExported)
945 return false;
947 // If the only implementation has local linkage, we must promote to external
948 // to make it visible to thin LTO objects. We can only get here during the
949 // ThinLTO export phase.
950 if (TheFn->hasLocalLinkage()) {
951 std::string NewName = (TheFn->getName() + "$merged").str();
953 // Since we are renaming the function, any comdats with the same name must
954 // also be renamed. This is required when targeting COFF, as the comdat name
955 // must match one of the names of the symbols in the comdat.
956 if (Comdat *C = TheFn->getComdat()) {
957 if (C->getName() == TheFn->getName()) {
958 Comdat *NewC = M.getOrInsertComdat(NewName);
959 NewC->setSelectionKind(C->getSelectionKind());
960 for (GlobalObject &GO : M.global_objects())
961 if (GO.getComdat() == C)
962 GO.setComdat(NewC);
966 TheFn->setLinkage(GlobalValue::ExternalLinkage);
967 TheFn->setVisibility(GlobalValue::HiddenVisibility);
968 TheFn->setName(NewName);
971 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
972 Res->SingleImplName = TheFn->getName();
974 return true;
977 bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
978 VTableSlotSummary &SlotSummary,
979 VTableSlotInfo &SlotInfo,
980 WholeProgramDevirtResolution *Res,
981 std::set<ValueInfo> &DevirtTargets) {
982 // See if the program contains a single implementation of this virtual
983 // function.
984 auto TheFn = TargetsForSlot[0];
985 for (auto &&Target : TargetsForSlot)
986 if (TheFn != Target)
987 return false;
989 // Don't devirtualize if we don't have target definition.
990 auto Size = TheFn.getSummaryList().size();
991 if (!Size)
992 return false;
994 // If the summary list contains multiple summaries where at least one is
995 // a local, give up, as we won't know which (possibly promoted) name to use.
996 for (auto &S : TheFn.getSummaryList())
997 if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1)
998 return false;
1000 // Collect functions devirtualized at least for one call site for stats.
1001 if (PrintSummaryDevirt)
1002 DevirtTargets.insert(TheFn);
1004 auto &S = TheFn.getSummaryList()[0];
1005 bool IsExported = false;
1007 // Insert calls into the summary index so that the devirtualized targets
1008 // are eligible for import.
1009 // FIXME: Annotate type tests with hotness. For now, mark these as hot
1010 // to better ensure we have the opportunity to inline them.
1011 CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0);
1012 auto AddCalls = [&](CallSiteInfo &CSInfo) {
1013 for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1014 FS->addCall({TheFn, CI});
1015 IsExported |= S->modulePath() != FS->modulePath();
1017 for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
1018 FS->addCall({TheFn, CI});
1019 IsExported |= S->modulePath() != FS->modulePath();
1022 AddCalls(SlotInfo.CSInfo);
1023 for (auto &P : SlotInfo.ConstCSInfo)
1024 AddCalls(P.second);
1026 if (IsExported)
1027 ExportedGUIDs.insert(TheFn.getGUID());
1029 // Record in summary for use in devirtualization during the ThinLTO import
1030 // step.
1031 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
1032 if (GlobalValue::isLocalLinkage(S->linkage())) {
1033 if (IsExported)
1034 // If target is a local function and we are exporting it by
1035 // devirtualizing a call in another module, we need to record the
1036 // promoted name.
1037 Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
1038 TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
1039 else {
1040 LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1041 Res->SingleImplName = TheFn.name();
1043 } else
1044 Res->SingleImplName = TheFn.name();
1046 // Name will be empty if this thin link driven off of serialized combined
1047 // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
1048 // legacy LTO API anyway.
1049 assert(!Res->SingleImplName.empty());
1051 return true;
1054 void DevirtModule::tryICallBranchFunnel(
1055 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1056 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1057 Triple T(M.getTargetTriple());
1058 if (T.getArch() != Triple::x86_64)
1059 return;
1061 if (TargetsForSlot.size() > ClThreshold)
1062 return;
1064 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1065 if (!HasNonDevirt)
1066 for (auto &P : SlotInfo.ConstCSInfo)
1067 if (!P.second.AllCallSitesDevirted) {
1068 HasNonDevirt = true;
1069 break;
1072 if (!HasNonDevirt)
1073 return;
1075 FunctionType *FT =
1076 FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
1077 Function *JT;
1078 if (isa<MDString>(Slot.TypeID)) {
1079 JT = Function::Create(FT, Function::ExternalLinkage,
1080 M.getDataLayout().getProgramAddressSpace(),
1081 getGlobalName(Slot, {}, "branch_funnel"), &M);
1082 JT->setVisibility(GlobalValue::HiddenVisibility);
1083 } else {
1084 JT = Function::Create(FT, Function::InternalLinkage,
1085 M.getDataLayout().getProgramAddressSpace(),
1086 "branch_funnel", &M);
1088 JT->addAttribute(1, Attribute::Nest);
1090 std::vector<Value *> JTArgs;
1091 JTArgs.push_back(JT->arg_begin());
1092 for (auto &T : TargetsForSlot) {
1093 JTArgs.push_back(getMemberAddr(T.TM));
1094 JTArgs.push_back(T.Fn);
1097 BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
1098 Function *Intr =
1099 Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
1101 auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
1102 CI->setTailCallKind(CallInst::TCK_MustTail);
1103 ReturnInst::Create(M.getContext(), nullptr, BB);
1105 bool IsExported = false;
1106 applyICallBranchFunnel(SlotInfo, JT, IsExported);
1107 if (IsExported)
1108 Res->TheKind = WholeProgramDevirtResolution::BranchFunnel;
1111 void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1112 Constant *JT, bool &IsExported) {
1113 auto Apply = [&](CallSiteInfo &CSInfo) {
1114 if (CSInfo.isExported())
1115 IsExported = true;
1116 if (CSInfo.AllCallSitesDevirted)
1117 return;
1118 for (auto &&VCallSite : CSInfo.CallSites) {
1119 CallSite CS = VCallSite.CS;
1121 // Jump tables are only profitable if the retpoline mitigation is enabled.
1122 Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
1123 if (FSAttr.hasAttribute(Attribute::None) ||
1124 !FSAttr.getValueAsString().contains("+retpoline"))
1125 continue;
1127 if (RemarksEnabled)
1128 VCallSite.emitRemark("branch-funnel",
1129 JT->stripPointerCasts()->getName(), OREGetter);
1131 // Pass the address of the vtable in the nest register, which is r10 on
1132 // x86_64.
1133 std::vector<Type *> NewArgs;
1134 NewArgs.push_back(Int8PtrTy);
1135 for (Type *T : CS.getFunctionType()->params())
1136 NewArgs.push_back(T);
1137 FunctionType *NewFT =
1138 FunctionType::get(CS.getFunctionType()->getReturnType(), NewArgs,
1139 CS.getFunctionType()->isVarArg());
1140 PointerType *NewFTPtr = PointerType::getUnqual(NewFT);
1142 IRBuilder<> IRB(CS.getInstruction());
1143 std::vector<Value *> Args;
1144 Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
1145 for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
1146 Args.push_back(CS.getArgOperand(I));
1148 CallSite NewCS;
1149 if (CS.isCall())
1150 NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(JT, NewFTPtr), Args);
1151 else
1152 NewCS = IRB.CreateInvoke(
1153 NewFT, IRB.CreateBitCast(JT, NewFTPtr),
1154 cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
1155 cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
1156 NewCS.setCallingConv(CS.getCallingConv());
1158 AttributeList Attrs = CS.getAttributes();
1159 std::vector<AttributeSet> NewArgAttrs;
1160 NewArgAttrs.push_back(AttributeSet::get(
1161 M.getContext(), ArrayRef<Attribute>{Attribute::get(
1162 M.getContext(), Attribute::Nest)}));
1163 for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1164 NewArgAttrs.push_back(Attrs.getParamAttributes(I));
1165 NewCS.setAttributes(
1166 AttributeList::get(M.getContext(), Attrs.getFnAttributes(),
1167 Attrs.getRetAttributes(), NewArgAttrs));
1169 CS->replaceAllUsesWith(NewCS.getInstruction());
1170 CS->eraseFromParent();
1172 // This use is no longer unsafe.
1173 if (VCallSite.NumUnsafeUses)
1174 --*VCallSite.NumUnsafeUses;
1176 // Don't mark as devirtualized because there may be callers compiled without
1177 // retpoline mitigation, which would mean that they are lowered to
1178 // llvm.type.test and therefore require an llvm.type.test resolution for the
1179 // type identifier.
1181 Apply(SlotInfo.CSInfo);
1182 for (auto &P : SlotInfo.ConstCSInfo)
1183 Apply(P.second);
1186 bool DevirtModule::tryEvaluateFunctionsWithArgs(
1187 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1188 ArrayRef<uint64_t> Args) {
1189 // Evaluate each function and store the result in each target's RetVal
1190 // field.
1191 for (VirtualCallTarget &Target : TargetsForSlot) {
1192 if (Target.Fn->arg_size() != Args.size() + 1)
1193 return false;
1195 Evaluator Eval(M.getDataLayout(), nullptr);
1196 SmallVector<Constant *, 2> EvalArgs;
1197 EvalArgs.push_back(
1198 Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
1199 for (unsigned I = 0; I != Args.size(); ++I) {
1200 auto *ArgTy = dyn_cast<IntegerType>(
1201 Target.Fn->getFunctionType()->getParamType(I + 1));
1202 if (!ArgTy)
1203 return false;
1204 EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
1207 Constant *RetVal;
1208 if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
1209 !isa<ConstantInt>(RetVal))
1210 return false;
1211 Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
1213 return true;
1216 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1217 uint64_t TheRetVal) {
1218 for (auto Call : CSInfo.CallSites)
1219 Call.replaceAndErase(
1220 "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1221 ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
1222 CSInfo.markDevirt();
1225 bool DevirtModule::tryUniformRetValOpt(
1226 MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1227 WholeProgramDevirtResolution::ByArg *Res) {
1228 // Uniform return value optimization. If all functions return the same
1229 // constant, replace all calls with that constant.
1230 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1231 for (const VirtualCallTarget &Target : TargetsForSlot)
1232 if (Target.RetVal != TheRetVal)
1233 return false;
1235 if (CSInfo.isExported()) {
1236 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
1237 Res->Info = TheRetVal;
1240 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1241 if (RemarksEnabled)
1242 for (auto &&Target : TargetsForSlot)
1243 Target.WasDevirt = true;
1244 return true;
1247 std::string DevirtModule::getGlobalName(VTableSlot Slot,
1248 ArrayRef<uint64_t> Args,
1249 StringRef Name) {
1250 std::string FullName = "__typeid_";
1251 raw_string_ostream OS(FullName);
1252 OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1253 for (uint64_t Arg : Args)
1254 OS << '_' << Arg;
1255 OS << '_' << Name;
1256 return OS.str();
1259 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1260 Triple T(M.getTargetTriple());
1261 return (T.getArch() == Triple::x86 || T.getArch() == Triple::x86_64) &&
1262 T.getObjectFormat() == Triple::ELF;
1265 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1266 StringRef Name, Constant *C) {
1267 GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
1268 getGlobalName(Slot, Args, Name), C, &M);
1269 GA->setVisibility(GlobalValue::HiddenVisibility);
1272 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1273 StringRef Name, uint32_t Const,
1274 uint32_t &Storage) {
1275 if (shouldExportConstantsAsAbsoluteSymbols()) {
1276 exportGlobal(
1277 Slot, Args, Name,
1278 ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1279 return;
1282 Storage = Const;
1285 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1286 StringRef Name) {
1287 Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
1288 auto *GV = dyn_cast<GlobalVariable>(C);
1289 if (GV)
1290 GV->setVisibility(GlobalValue::HiddenVisibility);
1291 return C;
1294 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1295 StringRef Name, IntegerType *IntTy,
1296 uint32_t Storage) {
1297 if (!shouldExportConstantsAsAbsoluteSymbols())
1298 return ConstantInt::get(IntTy, Storage);
1300 Constant *C = importGlobal(Slot, Args, Name);
1301 auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1302 C = ConstantExpr::getPtrToInt(C, IntTy);
1304 // We only need to set metadata if the global is newly created, in which
1305 // case it would not have hidden visibility.
1306 if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1307 return C;
1309 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1310 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1311 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1312 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1313 MDNode::get(M.getContext(), {MinC, MaxC}));
1315 unsigned AbsWidth = IntTy->getBitWidth();
1316 if (AbsWidth == IntPtrTy->getBitWidth())
1317 SetAbsRange(~0ull, ~0ull); // Full set.
1318 else
1319 SetAbsRange(0, 1ull << AbsWidth);
1320 return C;
1323 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1324 bool IsOne,
1325 Constant *UniqueMemberAddr) {
1326 for (auto &&Call : CSInfo.CallSites) {
1327 IRBuilder<> B(Call.CS.getInstruction());
1328 Value *Cmp =
1329 B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
1330 B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
1331 Cmp = B.CreateZExt(Cmp, Call.CS->getType());
1332 Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1333 Cmp);
1335 CSInfo.markDevirt();
1338 Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1339 Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1340 return ConstantExpr::getGetElementPtr(Int8Ty, C,
1341 ConstantInt::get(Int64Ty, M->Offset));
1344 bool DevirtModule::tryUniqueRetValOpt(
1345 unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1346 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1347 VTableSlot Slot, ArrayRef<uint64_t> Args) {
1348 // IsOne controls whether we look for a 0 or a 1.
1349 auto tryUniqueRetValOptFor = [&](bool IsOne) {
1350 const TypeMemberInfo *UniqueMember = nullptr;
1351 for (const VirtualCallTarget &Target : TargetsForSlot) {
1352 if (Target.RetVal == (IsOne ? 1 : 0)) {
1353 if (UniqueMember)
1354 return false;
1355 UniqueMember = Target.TM;
1359 // We should have found a unique member or bailed out by now. We already
1360 // checked for a uniform return value in tryUniformRetValOpt.
1361 assert(UniqueMember);
1363 Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1364 if (CSInfo.isExported()) {
1365 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
1366 Res->Info = IsOne;
1368 exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1371 // Replace each call with the comparison.
1372 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1373 UniqueMemberAddr);
1375 // Update devirtualization statistics for targets.
1376 if (RemarksEnabled)
1377 for (auto &&Target : TargetsForSlot)
1378 Target.WasDevirt = true;
1380 return true;
1383 if (BitWidth == 1) {
1384 if (tryUniqueRetValOptFor(true))
1385 return true;
1386 if (tryUniqueRetValOptFor(false))
1387 return true;
1389 return false;
1392 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1393 Constant *Byte, Constant *Bit) {
1394 for (auto Call : CSInfo.CallSites) {
1395 auto *RetType = cast<IntegerType>(Call.CS.getType());
1396 IRBuilder<> B(Call.CS.getInstruction());
1397 Value *Addr =
1398 B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1399 if (RetType->getBitWidth() == 1) {
1400 Value *Bits = B.CreateLoad(Int8Ty, Addr);
1401 Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1402 auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1403 Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1404 OREGetter, IsBitSet);
1405 } else {
1406 Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1407 Value *Val = B.CreateLoad(RetType, ValAddr);
1408 Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1409 OREGetter, Val);
1412 CSInfo.markDevirt();
1415 bool DevirtModule::tryVirtualConstProp(
1416 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1417 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1418 // This only works if the function returns an integer.
1419 auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1420 if (!RetType)
1421 return false;
1422 unsigned BitWidth = RetType->getBitWidth();
1423 if (BitWidth > 64)
1424 return false;
1426 // Make sure that each function is defined, does not access memory, takes at
1427 // least one argument, does not use its first argument (which we assume is
1428 // 'this'), and has the same return type.
1430 // Note that we test whether this copy of the function is readnone, rather
1431 // than testing function attributes, which must hold for any copy of the
1432 // function, even a less optimized version substituted at link time. This is
1433 // sound because the virtual constant propagation optimizations effectively
1434 // inline all implementations of the virtual function into each call site,
1435 // rather than using function attributes to perform local optimization.
1436 for (VirtualCallTarget &Target : TargetsForSlot) {
1437 if (Target.Fn->isDeclaration() ||
1438 computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1439 MAK_ReadNone ||
1440 Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1441 Target.Fn->getReturnType() != RetType)
1442 return false;
1445 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1446 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1447 continue;
1449 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1450 if (Res)
1451 ResByArg = &Res->ResByArg[CSByConstantArg.first];
1453 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1454 continue;
1456 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1457 ResByArg, Slot, CSByConstantArg.first))
1458 continue;
1460 // Find an allocation offset in bits in all vtables associated with the
1461 // type.
1462 uint64_t AllocBefore =
1463 findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1464 uint64_t AllocAfter =
1465 findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1467 // Calculate the total amount of padding needed to store a value at both
1468 // ends of the object.
1469 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1470 for (auto &&Target : TargetsForSlot) {
1471 TotalPaddingBefore += std::max<int64_t>(
1472 (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1473 TotalPaddingAfter += std::max<int64_t>(
1474 (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1477 // If the amount of padding is too large, give up.
1478 // FIXME: do something smarter here.
1479 if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1480 continue;
1482 // Calculate the offset to the value as a (possibly negative) byte offset
1483 // and (if applicable) a bit offset, and store the values in the targets.
1484 int64_t OffsetByte;
1485 uint64_t OffsetBit;
1486 if (TotalPaddingBefore <= TotalPaddingAfter)
1487 setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1488 OffsetBit);
1489 else
1490 setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1491 OffsetBit);
1493 if (RemarksEnabled)
1494 for (auto &&Target : TargetsForSlot)
1495 Target.WasDevirt = true;
1498 if (CSByConstantArg.second.isExported()) {
1499 ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;
1500 exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1501 ResByArg->Byte);
1502 exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1503 ResByArg->Bit);
1506 // Rewrite each call to a load from OffsetByte/OffsetBit.
1507 Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1508 Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1509 applyVirtualConstProp(CSByConstantArg.second,
1510 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1512 return true;
1515 void DevirtModule::rebuildGlobal(VTableBits &B) {
1516 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1517 return;
1519 // Align the before byte array to the global's minimum alignment so that we
1520 // don't break any alignment requirements on the global.
1521 unsigned Align = B.GV->getAlignment();
1522 if (Align == 0)
1523 Align = M.getDataLayout().getABITypeAlignment(B.GV->getValueType());
1524 B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Align));
1526 // Before was stored in reverse order; flip it now.
1527 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1528 std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1530 // Build an anonymous global containing the before bytes, followed by the
1531 // original initializer, followed by the after bytes.
1532 auto NewInit = ConstantStruct::getAnon(
1533 {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1534 B.GV->getInitializer(),
1535 ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1536 auto NewGV =
1537 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1538 GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1539 NewGV->setSection(B.GV->getSection());
1540 NewGV->setComdat(B.GV->getComdat());
1541 NewGV->setAlignment(B.GV->getAlignment());
1543 // Copy the original vtable's metadata to the anonymous global, adjusting
1544 // offsets as required.
1545 NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1547 // Build an alias named after the original global, pointing at the second
1548 // element (the original initializer).
1549 auto Alias = GlobalAlias::create(
1550 B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1551 ConstantExpr::getGetElementPtr(
1552 NewInit->getType(), NewGV,
1553 ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
1554 ConstantInt::get(Int32Ty, 1)}),
1555 &M);
1556 Alias->setVisibility(B.GV->getVisibility());
1557 Alias->takeName(B.GV);
1559 B.GV->replaceAllUsesWith(Alias);
1560 B.GV->eraseFromParent();
1563 bool DevirtModule::areRemarksEnabled() {
1564 const auto &FL = M.getFunctionList();
1565 for (const Function &Fn : FL) {
1566 const auto &BBL = Fn.getBasicBlockList();
1567 if (BBL.empty())
1568 continue;
1569 auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1570 return DI.isEnabled();
1572 return false;
1575 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1576 Function *AssumeFunc) {
1577 // Find all virtual calls via a virtual table pointer %p under an assumption
1578 // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1579 // points to a member of the type identifier %md. Group calls by (type ID,
1580 // offset) pair (effectively the identity of the virtual function) and store
1581 // to CallSlots.
1582 DenseSet<CallSite> SeenCallSites;
1583 for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1584 I != E;) {
1585 auto CI = dyn_cast<CallInst>(I->getUser());
1586 ++I;
1587 if (!CI)
1588 continue;
1590 // Search for virtual calls based on %p and add them to DevirtCalls.
1591 SmallVector<DevirtCallSite, 1> DevirtCalls;
1592 SmallVector<CallInst *, 1> Assumes;
1593 auto &DT = LookupDomTree(*CI->getFunction());
1594 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1596 // If we found any, add them to CallSlots.
1597 if (!Assumes.empty()) {
1598 Metadata *TypeId =
1599 cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1600 Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1601 for (DevirtCallSite Call : DevirtCalls) {
1602 // Only add this CallSite if we haven't seen it before. The vtable
1603 // pointer may have been CSE'd with pointers from other call sites,
1604 // and we don't want to process call sites multiple times. We can't
1605 // just skip the vtable Ptr if it has been seen before, however, since
1606 // it may be shared by type tests that dominate different calls.
1607 if (SeenCallSites.insert(Call.CS).second)
1608 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1612 // We no longer need the assumes or the type test.
1613 for (auto Assume : Assumes)
1614 Assume->eraseFromParent();
1615 // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1616 // may use the vtable argument later.
1617 if (CI->use_empty())
1618 CI->eraseFromParent();
1622 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1623 Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1625 for (auto I = TypeCheckedLoadFunc->use_begin(),
1626 E = TypeCheckedLoadFunc->use_end();
1627 I != E;) {
1628 auto CI = dyn_cast<CallInst>(I->getUser());
1629 ++I;
1630 if (!CI)
1631 continue;
1633 Value *Ptr = CI->getArgOperand(0);
1634 Value *Offset = CI->getArgOperand(1);
1635 Value *TypeIdValue = CI->getArgOperand(2);
1636 Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1638 SmallVector<DevirtCallSite, 1> DevirtCalls;
1639 SmallVector<Instruction *, 1> LoadedPtrs;
1640 SmallVector<Instruction *, 1> Preds;
1641 bool HasNonCallUses = false;
1642 auto &DT = LookupDomTree(*CI->getFunction());
1643 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1644 HasNonCallUses, CI, DT);
1646 // Start by generating "pessimistic" code that explicitly loads the function
1647 // pointer from the vtable and performs the type check. If possible, we will
1648 // eliminate the load and the type check later.
1650 // If possible, only generate the load at the point where it is used.
1651 // This helps avoid unnecessary spills.
1652 IRBuilder<> LoadB(
1653 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1654 Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1655 Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1656 Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1658 for (Instruction *LoadedPtr : LoadedPtrs) {
1659 LoadedPtr->replaceAllUsesWith(LoadedValue);
1660 LoadedPtr->eraseFromParent();
1663 // Likewise for the type test.
1664 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1665 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1667 for (Instruction *Pred : Preds) {
1668 Pred->replaceAllUsesWith(TypeTestCall);
1669 Pred->eraseFromParent();
1672 // We have already erased any extractvalue instructions that refer to the
1673 // intrinsic call, but the intrinsic may have other non-extractvalue uses
1674 // (although this is unlikely). In that case, explicitly build a pair and
1675 // RAUW it.
1676 if (!CI->use_empty()) {
1677 Value *Pair = UndefValue::get(CI->getType());
1678 IRBuilder<> B(CI);
1679 Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1680 Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1681 CI->replaceAllUsesWith(Pair);
1684 // The number of unsafe uses is initially the number of uses.
1685 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1686 NumUnsafeUses = DevirtCalls.size();
1688 // If the function pointer has a non-call user, we cannot eliminate the type
1689 // check, as one of those users may eventually call the pointer. Increment
1690 // the unsafe use count to make sure it cannot reach zero.
1691 if (HasNonCallUses)
1692 ++NumUnsafeUses;
1693 for (DevirtCallSite Call : DevirtCalls) {
1694 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1695 &NumUnsafeUses);
1698 CI->eraseFromParent();
1702 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1703 auto *TypeId = dyn_cast<MDString>(Slot.TypeID);
1704 if (!TypeId)
1705 return;
1706 const TypeIdSummary *TidSummary =
1707 ImportSummary->getTypeIdSummary(TypeId->getString());
1708 if (!TidSummary)
1709 return;
1710 auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1711 if (ResI == TidSummary->WPDRes.end())
1712 return;
1713 const WholeProgramDevirtResolution &Res = ResI->second;
1715 if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
1716 assert(!Res.SingleImplName.empty());
1717 // The type of the function in the declaration is irrelevant because every
1718 // call site will cast it to the correct type.
1719 Constant *SingleImpl =
1720 cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,
1721 Type::getVoidTy(M.getContext()))
1722 .getCallee());
1724 // This is the import phase so we should not be exporting anything.
1725 bool IsExported = false;
1726 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1727 assert(!IsExported);
1730 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1731 auto I = Res.ResByArg.find(CSByConstantArg.first);
1732 if (I == Res.ResByArg.end())
1733 continue;
1734 auto &ResByArg = I->second;
1735 // FIXME: We should figure out what to do about the "function name" argument
1736 // to the apply* functions, as the function names are unavailable during the
1737 // importing phase. For now we just pass the empty string. This does not
1738 // impact correctness because the function names are just used for remarks.
1739 switch (ResByArg.TheKind) {
1740 case WholeProgramDevirtResolution::ByArg::UniformRetVal:
1741 applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1742 break;
1743 case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
1744 Constant *UniqueMemberAddr =
1745 importGlobal(Slot, CSByConstantArg.first, "unique_member");
1746 applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1747 UniqueMemberAddr);
1748 break;
1750 case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
1751 Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1752 Int32Ty, ResByArg.Byte);
1753 Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1754 ResByArg.Bit);
1755 applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1756 break;
1758 default:
1759 break;
1763 if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) {
1764 // The type of the function is irrelevant, because it's bitcast at calls
1765 // anyhow.
1766 Constant *JT = cast<Constant>(
1767 M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
1768 Type::getVoidTy(M.getContext()))
1769 .getCallee());
1770 bool IsExported = false;
1771 applyICallBranchFunnel(SlotInfo, JT, IsExported);
1772 assert(!IsExported);
1776 void DevirtModule::removeRedundantTypeTests() {
1777 auto True = ConstantInt::getTrue(M.getContext());
1778 for (auto &&U : NumUnsafeUsesForTypeTest) {
1779 if (U.second == 0) {
1780 U.first->replaceAllUsesWith(True);
1781 U.first->eraseFromParent();
1786 bool DevirtModule::run() {
1787 // If only some of the modules were split, we cannot correctly perform
1788 // this transformation. We already checked for the presense of type tests
1789 // with partially split modules during the thin link, and would have emitted
1790 // an error if any were found, so here we can simply return.
1791 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1792 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
1793 return false;
1795 Function *TypeTestFunc =
1796 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1797 Function *TypeCheckedLoadFunc =
1798 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1799 Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1801 // Normally if there are no users of the devirtualization intrinsics in the
1802 // module, this pass has nothing to do. But if we are exporting, we also need
1803 // to handle any users that appear only in the function summaries.
1804 if (!ExportSummary &&
1805 (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1806 AssumeFunc->use_empty()) &&
1807 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1808 return false;
1810 if (TypeTestFunc && AssumeFunc)
1811 scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1813 if (TypeCheckedLoadFunc)
1814 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1816 if (ImportSummary) {
1817 for (auto &S : CallSlots)
1818 importResolution(S.first, S.second);
1820 removeRedundantTypeTests();
1822 // The rest of the code is only necessary when exporting or during regular
1823 // LTO, so we are done.
1824 return true;
1827 // Rebuild type metadata into a map for easy lookup.
1828 std::vector<VTableBits> Bits;
1829 DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
1830 buildTypeIdentifierMap(Bits, TypeIdMap);
1831 if (TypeIdMap.empty())
1832 return true;
1834 // Collect information from summary about which calls to try to devirtualize.
1835 if (ExportSummary) {
1836 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
1837 for (auto &P : TypeIdMap) {
1838 if (auto *TypeId = dyn_cast<MDString>(P.first))
1839 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1840 TypeId);
1843 for (auto &P : *ExportSummary) {
1844 for (auto &S : P.second.SummaryList) {
1845 auto *FS = dyn_cast<FunctionSummary>(S.get());
1846 if (!FS)
1847 continue;
1848 // FIXME: Only add live functions.
1849 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1850 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1851 CallSlots[{MD, VF.Offset}]
1852 .CSInfo.markSummaryHasTypeTestAssumeUsers();
1855 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1856 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1857 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1860 for (const FunctionSummary::ConstVCall &VC :
1861 FS->type_test_assume_const_vcalls()) {
1862 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1863 CallSlots[{MD, VC.VFunc.Offset}]
1864 .ConstCSInfo[VC.Args]
1865 .markSummaryHasTypeTestAssumeUsers();
1868 for (const FunctionSummary::ConstVCall &VC :
1869 FS->type_checked_load_const_vcalls()) {
1870 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1871 CallSlots[{MD, VC.VFunc.Offset}]
1872 .ConstCSInfo[VC.Args]
1873 .addSummaryTypeCheckedLoadUser(FS);
1880 // For each (type, offset) pair:
1881 bool DidVirtualConstProp = false;
1882 std::map<std::string, Function*> DevirtTargets;
1883 for (auto &S : CallSlots) {
1884 // Search each of the members of the type identifier for the virtual
1885 // function implementation at offset S.first.ByteOffset, and add to
1886 // TargetsForSlot.
1887 std::vector<VirtualCallTarget> TargetsForSlot;
1888 if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
1889 S.first.ByteOffset)) {
1890 WholeProgramDevirtResolution *Res = nullptr;
1891 if (ExportSummary && isa<MDString>(S.first.TypeID))
1892 Res = &ExportSummary
1893 ->getOrInsertTypeIdSummary(
1894 cast<MDString>(S.first.TypeID)->getString())
1895 .WPDRes[S.first.ByteOffset];
1897 if (!trySingleImplDevirt(TargetsForSlot, S.second, Res)) {
1898 DidVirtualConstProp |=
1899 tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
1901 tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
1904 // Collect functions devirtualized at least for one call site for stats.
1905 if (RemarksEnabled)
1906 for (const auto &T : TargetsForSlot)
1907 if (T.WasDevirt)
1908 DevirtTargets[T.Fn->getName()] = T.Fn;
1911 // CFI-specific: if we are exporting and any llvm.type.checked.load
1912 // intrinsics were *not* devirtualized, we need to add the resulting
1913 // llvm.type.test intrinsics to the function summaries so that the
1914 // LowerTypeTests pass will export them.
1915 if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1916 auto GUID =
1917 GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1918 for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1919 FS->addTypeTest(GUID);
1920 for (auto &CCS : S.second.ConstCSInfo)
1921 for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1922 FS->addTypeTest(GUID);
1926 if (RemarksEnabled) {
1927 // Generate remarks for each devirtualized function.
1928 for (const auto &DT : DevirtTargets) {
1929 Function *F = DT.second;
1931 using namespace ore;
1932 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
1933 << "devirtualized "
1934 << NV("FunctionName", DT.first));
1938 removeRedundantTypeTests();
1940 // Rebuild each global we touched as part of virtual constant propagation to
1941 // include the before and after bytes.
1942 if (DidVirtualConstProp)
1943 for (VTableBits &B : Bits)
1944 rebuildGlobal(B);
1946 return true;
1949 void DevirtIndex::run() {
1950 if (ExportSummary.typeIdCompatibleVtableMap().empty())
1951 return;
1953 DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
1954 for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
1955 NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
1958 // Collect information from summary about which calls to try to devirtualize.
1959 for (auto &P : ExportSummary) {
1960 for (auto &S : P.second.SummaryList) {
1961 auto *FS = dyn_cast<FunctionSummary>(S.get());
1962 if (!FS)
1963 continue;
1964 // FIXME: Only add live functions.
1965 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1966 for (StringRef Name : NameByGUID[VF.GUID]) {
1967 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
1970 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1971 for (StringRef Name : NameByGUID[VF.GUID]) {
1972 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1975 for (const FunctionSummary::ConstVCall &VC :
1976 FS->type_test_assume_const_vcalls()) {
1977 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
1978 CallSlots[{Name, VC.VFunc.Offset}]
1979 .ConstCSInfo[VC.Args]
1980 .addSummaryTypeTestAssumeUser(FS);
1983 for (const FunctionSummary::ConstVCall &VC :
1984 FS->type_checked_load_const_vcalls()) {
1985 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
1986 CallSlots[{Name, VC.VFunc.Offset}]
1987 .ConstCSInfo[VC.Args]
1988 .addSummaryTypeCheckedLoadUser(FS);
1994 std::set<ValueInfo> DevirtTargets;
1995 // For each (type, offset) pair:
1996 for (auto &S : CallSlots) {
1997 // Search each of the members of the type identifier for the virtual
1998 // function implementation at offset S.first.ByteOffset, and add to
1999 // TargetsForSlot.
2000 std::vector<ValueInfo> TargetsForSlot;
2001 auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
2002 assert(TidSummary);
2003 if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
2004 S.first.ByteOffset)) {
2005 WholeProgramDevirtResolution *Res =
2006 &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
2007 .WPDRes[S.first.ByteOffset];
2009 if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
2010 DevirtTargets))
2011 continue;
2015 // Optionally have the thin link print message for each devirtualized
2016 // function.
2017 if (PrintSummaryDevirt)
2018 for (const auto &DT : DevirtTargets)
2019 errs() << "Devirtualized call to " << DT << "\n";
2021 return;