Bug Summary

File:lib/Transforms/IPO/WholeProgramDevirt.cpp
Warning:line 1263, column 25
Access to field 'TheKind' results in a dereference of a null pointer (loaded from variable 'ResByArg')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name WholeProgramDevirt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Transforms/IPO -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO/WholeProgramDevirt.cpp -faddrsig
1//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
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.
27//
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.
41//
42//===----------------------------------------------------------------------===//
43
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/OptimizationRemarkEmitter.h"
55#include "llvm/Analysis/TypeMetadataUtils.h"
56#include "llvm/IR/CallSite.h"
57#include "llvm/IR/Constants.h"
58#include "llvm/IR/DataLayout.h"
59#include "llvm/IR/DebugLoc.h"
60#include "llvm/IR/DerivedTypes.h"
61#include "llvm/IR/Function.h"
62#include "llvm/IR/GlobalAlias.h"
63#include "llvm/IR/GlobalVariable.h"
64#include "llvm/IR/IRBuilder.h"
65#include "llvm/IR/InstrTypes.h"
66#include "llvm/IR/Instruction.h"
67#include "llvm/IR/Instructions.h"
68#include "llvm/IR/Intrinsics.h"
69#include "llvm/IR/LLVMContext.h"
70#include "llvm/IR/Metadata.h"
71#include "llvm/IR/Module.h"
72#include "llvm/IR/ModuleSummaryIndexYAML.h"
73#include "llvm/Pass.h"
74#include "llvm/PassRegistry.h"
75#include "llvm/PassSupport.h"
76#include "llvm/Support/Casting.h"
77#include "llvm/Support/Error.h"
78#include "llvm/Support/FileSystem.h"
79#include "llvm/Support/MathExtras.h"
80#include "llvm/Transforms/IPO.h"
81#include "llvm/Transforms/IPO/FunctionAttrs.h"
82#include "llvm/Transforms/Utils/Evaluator.h"
83#include <algorithm>
84#include <cstddef>
85#include <map>
86#include <set>
87#include <string>
88
89using namespace llvm;
90using namespace wholeprogramdevirt;
91
92#define DEBUG_TYPE"wholeprogramdevirt" "wholeprogramdevirt"
93
94static cl::opt<PassSummaryAction> ClSummaryAction(
95 "wholeprogramdevirt-summary-action",
96 cl::desc("What to do with the summary when running this pass"),
97 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing")llvm::cl::OptionEnumValue { "none", int(PassSummaryAction::None
), "Do nothing" }
,
98 clEnumValN(PassSummaryAction::Import, "import",llvm::cl::OptionEnumValue { "import", int(PassSummaryAction::
Import), "Import typeid resolutions from summary and globals"
}
99 "Import typeid resolutions from summary and globals")llvm::cl::OptionEnumValue { "import", int(PassSummaryAction::
Import), "Import typeid resolutions from summary and globals"
}
,
100 clEnumValN(PassSummaryAction::Export, "export",llvm::cl::OptionEnumValue { "export", int(PassSummaryAction::
Export), "Export typeid resolutions to summary and globals" }
101 "Export typeid resolutions to summary and globals")llvm::cl::OptionEnumValue { "export", int(PassSummaryAction::
Export), "Export typeid resolutions to summary and globals" }
),
102 cl::Hidden);
103
104static cl::opt<std::string> ClReadSummary(
105 "wholeprogramdevirt-read-summary",
106 cl::desc("Read summary from given YAML file before running pass"),
107 cl::Hidden);
108
109static cl::opt<std::string> ClWriteSummary(
110 "wholeprogramdevirt-write-summary",
111 cl::desc("Write summary to given YAML file after running pass"),
112 cl::Hidden);
113
114static cl::opt<unsigned>
115 ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
116 cl::init(10), cl::ZeroOrMore,
117 cl::desc("Maximum number of call targets per "
118 "call site to enable branch funnels"));
119
120// Find the minimum offset that we may store a value of size Size bits at. If
121// IsAfter is set, look for an offset before the object, otherwise look for an
122// offset after the object.
123uint64_t
124wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
125 bool IsAfter, uint64_t Size) {
126 // Find a minimum offset taking into account only vtable sizes.
127 uint64_t MinByte = 0;
128 for (const VirtualCallTarget &Target : Targets) {
129 if (IsAfter)
130 MinByte = std::max(MinByte, Target.minAfterBytes());
131 else
132 MinByte = std::max(MinByte, Target.minBeforeBytes());
133 }
134
135 // Build a vector of arrays of bytes covering, for each target, a slice of the
136 // used region (see AccumBitVector::BytesUsed in
137 // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
138 // this aligns the used regions to start at MinByte.
139 //
140 // In this example, A, B and C are vtables, # is a byte already allocated for
141 // a virtual function pointer, AAAA... (etc.) are the used regions for the
142 // vtables and Offset(X) is the value computed for the Offset variable below
143 // for X.
144 //
145 // Offset(A)
146 // | |
147 // |MinByte
148 // A: ################AAAAAAAA|AAAAAAAA
149 // B: ########BBBBBBBBBBBBBBBB|BBBB
150 // C: ########################|CCCCCCCCCCCCCCCC
151 // | Offset(B) |
152 //
153 // This code produces the slices of A, B and C that appear after the divider
154 // at MinByte.
155 std::vector<ArrayRef<uint8_t>> Used;
156 for (const VirtualCallTarget &Target : Targets) {
157 ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
158 : Target.TM->Bits->Before.BytesUsed;
159 uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
160 : MinByte - Target.minBeforeBytes();
161
162 // Disregard used regions that are smaller than Offset. These are
163 // effectively all-free regions that do not need to be checked.
164 if (VTUsed.size() > Offset)
165 Used.push_back(VTUsed.slice(Offset));
166 }
167
168 if (Size == 1) {
169 // Find a free bit in each member of Used.
170 for (unsigned I = 0;; ++I) {
171 uint8_t BitsUsed = 0;
172 for (auto &&B : Used)
173 if (I < B.size())
174 BitsUsed |= B[I];
175 if (BitsUsed != 0xff)
176 return (MinByte + I) * 8 +
177 countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
178 }
179 } else {
180 // Find a free (Size/8) byte region in each member of Used.
181 // FIXME: see if alignment helps.
182 for (unsigned I = 0;; ++I) {
183 for (auto &&B : Used) {
184 unsigned Byte = 0;
185 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
186 if (B[I + Byte])
187 goto NextI;
188 ++Byte;
189 }
190 }
191 return (MinByte + I) * 8;
192 NextI:;
193 }
194 }
195}
196
197void wholeprogramdevirt::setBeforeReturnValues(
198 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
199 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
200 if (BitWidth == 1)
201 OffsetByte = -(AllocBefore / 8 + 1);
202 else
203 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
204 OffsetBit = AllocBefore % 8;
205
206 for (VirtualCallTarget &Target : Targets) {
207 if (BitWidth == 1)
208 Target.setBeforeBit(AllocBefore);
209 else
210 Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
211 }
212}
213
214void wholeprogramdevirt::setAfterReturnValues(
215 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
216 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
217 if (BitWidth == 1)
218 OffsetByte = AllocAfter / 8;
219 else
220 OffsetByte = (AllocAfter + 7) / 8;
221 OffsetBit = AllocAfter % 8;
222
223 for (VirtualCallTarget &Target : Targets) {
224 if (BitWidth == 1)
225 Target.setAfterBit(AllocAfter);
226 else
227 Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
228 }
229}
230
231VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
232 : Fn(Fn), TM(TM),
233 IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
234
235namespace {
236
237// A slot in a set of virtual tables. The TypeID identifies the set of virtual
238// tables, and the ByteOffset is the offset in bytes from the address point to
239// the virtual function pointer.
240struct VTableSlot {
241 Metadata *TypeID;
242 uint64_t ByteOffset;
243};
244
245} // end anonymous namespace
246
247namespace llvm {
248
249template <> struct DenseMapInfo<VTableSlot> {
250 static VTableSlot getEmptyKey() {
251 return {DenseMapInfo<Metadata *>::getEmptyKey(),
252 DenseMapInfo<uint64_t>::getEmptyKey()};
253 }
254 static VTableSlot getTombstoneKey() {
255 return {DenseMapInfo<Metadata *>::getTombstoneKey(),
256 DenseMapInfo<uint64_t>::getTombstoneKey()};
257 }
258 static unsigned getHashValue(const VTableSlot &I) {
259 return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
260 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
261 }
262 static bool isEqual(const VTableSlot &LHS,
263 const VTableSlot &RHS) {
264 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
265 }
266};
267
268} // end namespace llvm
269
270namespace {
271
272// A virtual call site. VTable is the loaded virtual table pointer, and CS is
273// the indirect virtual call.
274struct VirtualCallSite {
275 Value *VTable;
276 CallSite CS;
277
278 // If non-null, this field points to the associated unsafe use count stored in
279 // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
280 // of that field for details.
281 unsigned *NumUnsafeUses;
282
283 void
284 emitRemark(const StringRef OptName, const StringRef TargetName,
285 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter) {
286 Function *F = CS.getCaller();
287 DebugLoc DLoc = CS->getDebugLoc();
288 BasicBlock *Block = CS.getParent();
289
290 using namespace ore;
291 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", OptName, DLoc, Block)
292 << NV("Optimization", OptName)
293 << ": devirtualized a call to "
294 << NV("FunctionName", TargetName));
295 }
296
297 void replaceAndErase(
298 const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
299 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
300 Value *New) {
301 if (RemarksEnabled)
302 emitRemark(OptName, TargetName, OREGetter);
303 CS->replaceAllUsesWith(New);
304 if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
305 BranchInst::Create(II->getNormalDest(), CS.getInstruction());
306 II->getUnwindDest()->removePredecessor(II->getParent());
307 }
308 CS->eraseFromParent();
309 // This use is no longer unsafe.
310 if (NumUnsafeUses)
311 --*NumUnsafeUses;
312 }
313};
314
315// Call site information collected for a specific VTableSlot and possibly a list
316// of constant integer arguments. The grouping by arguments is handled by the
317// VTableSlotInfo class.
318struct CallSiteInfo {
319 /// The set of call sites for this slot. Used during regular LTO and the
320 /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
321 /// call sites that appear in the merged module itself); in each of these
322 /// cases we are directly operating on the call sites at the IR level.
323 std::vector<VirtualCallSite> CallSites;
324
325 /// Whether all call sites represented by this CallSiteInfo, including those
326 /// in summaries, have been devirtualized. This starts off as true because a
327 /// default constructed CallSiteInfo represents no call sites.
328 bool AllCallSitesDevirted = true;
329
330 // These fields are used during the export phase of ThinLTO and reflect
331 // information collected from function summaries.
332
333 /// Whether any function summary contains an llvm.assume(llvm.type.test) for
334 /// this slot.
335 bool SummaryHasTypeTestAssumeUsers = false;
336
337 /// CFI-specific: a vector containing the list of function summaries that use
338 /// the llvm.type.checked.load intrinsic and therefore will require
339 /// resolutions for llvm.type.test in order to implement CFI checks if
340 /// devirtualization was unsuccessful. If devirtualization was successful, the
341 /// pass will clear this vector by calling markDevirt(). If at the end of the
342 /// pass the vector is non-empty, we will need to add a use of llvm.type.test
343 /// to each of the function summaries in the vector.
344 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
345
346 bool isExported() const {
347 return SummaryHasTypeTestAssumeUsers ||
348 !SummaryTypeCheckedLoadUsers.empty();
349 }
350
351 void markSummaryHasTypeTestAssumeUsers() {
352 SummaryHasTypeTestAssumeUsers = true;
353 AllCallSitesDevirted = false;
354 }
355
356 void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
357 SummaryTypeCheckedLoadUsers.push_back(FS);
358 AllCallSitesDevirted = false;
359 }
360
361 void markDevirt() {
362 AllCallSitesDevirted = true;
363
364 // As explained in the comment for SummaryTypeCheckedLoadUsers.
365 SummaryTypeCheckedLoadUsers.clear();
366 }
367};
368
369// Call site information collected for a specific VTableSlot.
370struct VTableSlotInfo {
371 // The set of call sites which do not have all constant integer arguments
372 // (excluding "this").
373 CallSiteInfo CSInfo;
374
375 // The set of call sites with all constant integer arguments (excluding
376 // "this"), grouped by argument list.
377 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
378
379 void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
380
381private:
382 CallSiteInfo &findCallSiteInfo(CallSite CS);
383};
384
385CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
386 std::vector<uint64_t> Args;
387 auto *CI = dyn_cast<IntegerType>(CS.getType());
388 if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
389 return CSInfo;
390 for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
391 auto *CI = dyn_cast<ConstantInt>(Arg);
392 if (!CI || CI->getBitWidth() > 64)
393 return CSInfo;
394 Args.push_back(CI->getZExtValue());
395 }
396 return ConstCSInfo[Args];
397}
398
399void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
400 unsigned *NumUnsafeUses) {
401 auto &CSI = findCallSiteInfo(CS);
402 CSI.AllCallSitesDevirted = false;
403 CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
404}
405
406struct DevirtModule {
407 Module &M;
408 function_ref<AAResults &(Function &)> AARGetter;
409
410 ModuleSummaryIndex *ExportSummary;
411 const ModuleSummaryIndex *ImportSummary;
412
413 IntegerType *Int8Ty;
414 PointerType *Int8PtrTy;
415 IntegerType *Int32Ty;
416 IntegerType *Int64Ty;
417 IntegerType *IntPtrTy;
418
419 bool RemarksEnabled;
420 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter;
421
422 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
423
424 // This map keeps track of the number of "unsafe" uses of a loaded function
425 // pointer. The key is the associated llvm.type.test intrinsic call generated
426 // by this pass. An unsafe use is one that calls the loaded function pointer
427 // directly. Every time we eliminate an unsafe use (for example, by
428 // devirtualizing it or by applying virtual constant propagation), we
429 // decrement the value stored in this map. If a value reaches zero, we can
430 // eliminate the type check by RAUWing the associated llvm.type.test call with
431 // true.
432 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
433
434 DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
435 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
436 ModuleSummaryIndex *ExportSummary,
437 const ModuleSummaryIndex *ImportSummary)
438 : M(M), AARGetter(AARGetter), ExportSummary(ExportSummary),
439 ImportSummary(ImportSummary), Int8Ty(Type::getInt8Ty(M.getContext())),
440 Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
441 Int32Ty(Type::getInt32Ty(M.getContext())),
442 Int64Ty(Type::getInt64Ty(M.getContext())),
443 IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
444 RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
445 assert(!(ExportSummary && ImportSummary))(static_cast <bool> (!(ExportSummary && ImportSummary
)) ? void (0) : __assert_fail ("!(ExportSummary && ImportSummary)"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 445, __extension__ __PRETTY_FUNCTION__))
;
446 }
447
448 bool areRemarksEnabled();
449
450 void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
451 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
452
453 void buildTypeIdentifierMap(
454 std::vector<VTableBits> &Bits,
455 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
456 Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
457 bool
458 tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
459 const std::set<TypeMemberInfo> &TypeMemberInfos,
460 uint64_t ByteOffset);
461
462 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
463 bool &IsExported);
464 bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
465 VTableSlotInfo &SlotInfo,
466 WholeProgramDevirtResolution *Res);
467
468 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
469 bool &IsExported);
470 void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
471 VTableSlotInfo &SlotInfo,
472 WholeProgramDevirtResolution *Res, VTableSlot Slot);
473
474 bool tryEvaluateFunctionsWithArgs(
475 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
476 ArrayRef<uint64_t> Args);
477
478 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
479 uint64_t TheRetVal);
480 bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
481 CallSiteInfo &CSInfo,
482 WholeProgramDevirtResolution::ByArg *Res);
483
484 // Returns the global symbol name that is used to export information about the
485 // given vtable slot and list of arguments.
486 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
487 StringRef Name);
488
489 bool shouldExportConstantsAsAbsoluteSymbols();
490
491 // This function is called during the export phase to create a symbol
492 // definition containing information about the given vtable slot and list of
493 // arguments.
494 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
495 Constant *C);
496 void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
497 uint32_t Const, uint32_t &Storage);
498
499 // This function is called during the import phase to create a reference to
500 // the symbol definition created during the export phase.
501 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
502 StringRef Name);
503 Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
504 StringRef Name, IntegerType *IntTy,
505 uint32_t Storage);
506
507 Constant *getMemberAddr(const TypeMemberInfo *M);
508
509 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
510 Constant *UniqueMemberAddr);
511 bool tryUniqueRetValOpt(unsigned BitWidth,
512 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
513 CallSiteInfo &CSInfo,
514 WholeProgramDevirtResolution::ByArg *Res,
515 VTableSlot Slot, ArrayRef<uint64_t> Args);
516
517 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
518 Constant *Byte, Constant *Bit);
519 bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
520 VTableSlotInfo &SlotInfo,
521 WholeProgramDevirtResolution *Res, VTableSlot Slot);
522
523 void rebuildGlobal(VTableBits &B);
524
525 // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
526 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
527
528 // If we were able to eliminate all unsafe uses for a type checked load,
529 // eliminate the associated type tests by replacing them with true.
530 void removeRedundantTypeTests();
531
532 bool run();
533
534 // Lower the module using the action and summary passed as command line
535 // arguments. For testing purposes only.
536 static bool runForTesting(
537 Module &M, function_ref<AAResults &(Function &)> AARGetter,
538 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter);
539};
540
541struct WholeProgramDevirt : public ModulePass {
542 static char ID;
543
544 bool UseCommandLine = false;
545
546 ModuleSummaryIndex *ExportSummary;
547 const ModuleSummaryIndex *ImportSummary;
548
549 WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
550 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
551 }
552
553 WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
554 const ModuleSummaryIndex *ImportSummary)
555 : ModulePass(ID), ExportSummary(ExportSummary),
556 ImportSummary(ImportSummary) {
557 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
558 }
559
560 bool runOnModule(Module &M) override {
561 if (skipModule(M))
562 return false;
563
564 // In the new pass manager, we can request the optimization
565 // remark emitter pass on a per-function-basis, which the
566 // OREGetter will do for us.
567 // In the old pass manager, this is harder, so we just build
568 // an optimization remark emitter on the fly, when we need it.
569 std::unique_ptr<OptimizationRemarkEmitter> ORE;
570 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
571 ORE = make_unique<OptimizationRemarkEmitter>(F);
572 return *ORE;
573 };
574
575 if (UseCommandLine)
576 return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter);
577
578 return DevirtModule(M, LegacyAARGetter(*this), OREGetter, ExportSummary,
579 ImportSummary)
580 .run();
581 }
582
583 void getAnalysisUsage(AnalysisUsage &AU) const override {
584 AU.addRequired<AssumptionCacheTracker>();
585 AU.addRequired<TargetLibraryInfoWrapperPass>();
586 }
587};
588
589} // end anonymous namespace
590
591INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",static void *initializeWholeProgramDevirtPassOnce(PassRegistry
&Registry) {
592 "Whole program devirtualization", false, false)static void *initializeWholeProgramDevirtPassOnce(PassRegistry
&Registry) {
593INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
594INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
595INITIALIZE_PASS_END(WholeProgramDevirt, "wholeprogramdevirt",PassInfo *PI = new PassInfo( "Whole program devirtualization"
, "wholeprogramdevirt", &WholeProgramDevirt::ID, PassInfo
::NormalCtor_t(callDefaultCtor<WholeProgramDevirt>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeWholeProgramDevirtPassFlag; void llvm
::initializeWholeProgramDevirtPass(PassRegistry &Registry
) { llvm::call_once(InitializeWholeProgramDevirtPassFlag, initializeWholeProgramDevirtPassOnce
, std::ref(Registry)); }
596 "Whole program devirtualization", false, false)PassInfo *PI = new PassInfo( "Whole program devirtualization"
, "wholeprogramdevirt", &WholeProgramDevirt::ID, PassInfo
::NormalCtor_t(callDefaultCtor<WholeProgramDevirt>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeWholeProgramDevirtPassFlag; void llvm
::initializeWholeProgramDevirtPass(PassRegistry &Registry
) { llvm::call_once(InitializeWholeProgramDevirtPassFlag, initializeWholeProgramDevirtPassOnce
, std::ref(Registry)); }
597char WholeProgramDevirt::ID = 0;
598
599ModulePass *
600llvm::createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
601 const ModuleSummaryIndex *ImportSummary) {
602 return new WholeProgramDevirt(ExportSummary, ImportSummary);
603}
604
605PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
606 ModuleAnalysisManager &AM) {
607 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
608 auto AARGetter = [&](Function &F) -> AAResults & {
609 return FAM.getResult<AAManager>(F);
610 };
611 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
612 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
613 };
614 if (!DevirtModule(M, AARGetter, OREGetter, ExportSummary, ImportSummary)
615 .run())
616 return PreservedAnalyses::all();
617 return PreservedAnalyses::none();
618}
619
620bool DevirtModule::runForTesting(
621 Module &M, function_ref<AAResults &(Function &)> AARGetter,
622 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter) {
623 ModuleSummaryIndex Summary(/*HaveGVs=*/false);
624
625 // Handle the command-line summary arguments. This code is for testing
626 // purposes only, so we handle errors directly.
627 if (!ClReadSummary.empty()) {
628 ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
629 ": ");
630 auto ReadSummaryFile =
631 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
632
633 yaml::Input In(ReadSummaryFile->getBuffer());
634 In >> Summary;
635 ExitOnErr(errorCodeToError(In.error()));
636 }
637
638 bool Changed =
639 DevirtModule(
640 M, AARGetter, OREGetter,
641 ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
642 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
643 .run();
644
645 if (!ClWriteSummary.empty()) {
646 ExitOnError ExitOnErr(
647 "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
648 std::error_code EC;
649 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text);
650 ExitOnErr(errorCodeToError(EC));
651
652 yaml::Output Out(OS);
653 Out << Summary;
654 }
655
656 return Changed;
657}
658
659void DevirtModule::buildTypeIdentifierMap(
660 std::vector<VTableBits> &Bits,
661 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
662 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
663 Bits.reserve(M.getGlobalList().size());
664 SmallVector<MDNode *, 2> Types;
665 for (GlobalVariable &GV : M.globals()) {
666 Types.clear();
667 GV.getMetadata(LLVMContext::MD_type, Types);
668 if (Types.empty())
669 continue;
670
671 VTableBits *&BitsPtr = GVToBits[&GV];
672 if (!BitsPtr) {
673 Bits.emplace_back();
674 Bits.back().GV = &GV;
675 Bits.back().ObjectSize =
676 M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
677 BitsPtr = &Bits.back();
678 }
679
680 for (MDNode *Type : Types) {
681 auto TypeID = Type->getOperand(1).get();
682
683 uint64_t Offset =
684 cast<ConstantInt>(
685 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
686 ->getZExtValue();
687
688 TypeIdMap[TypeID].insert({BitsPtr, Offset});
689 }
690 }
691}
692
693Constant *DevirtModule::getPointerAtOffset(Constant *I, uint64_t Offset) {
694 if (I->getType()->isPointerTy()) {
695 if (Offset == 0)
696 return I;
697 return nullptr;
698 }
699
700 const DataLayout &DL = M.getDataLayout();
701
702 if (auto *C = dyn_cast<ConstantStruct>(I)) {
703 const StructLayout *SL = DL.getStructLayout(C->getType());
704 if (Offset >= SL->getSizeInBytes())
705 return nullptr;
706
707 unsigned Op = SL->getElementContainingOffset(Offset);
708 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
709 Offset - SL->getElementOffset(Op));
710 }
711 if (auto *C = dyn_cast<ConstantArray>(I)) {
712 ArrayType *VTableTy = C->getType();
713 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
714
715 unsigned Op = Offset / ElemSize;
716 if (Op >= C->getNumOperands())
717 return nullptr;
718
719 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
720 Offset % ElemSize);
721 }
722 return nullptr;
723}
724
725bool DevirtModule::tryFindVirtualCallTargets(
726 std::vector<VirtualCallTarget> &TargetsForSlot,
727 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
728 for (const TypeMemberInfo &TM : TypeMemberInfos) {
729 if (!TM.Bits->GV->isConstant())
730 return false;
731
732 Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
733 TM.Offset + ByteOffset);
734 if (!Ptr)
735 return false;
736
737 auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
738 if (!Fn)
739 return false;
740
741 // We can disregard __cxa_pure_virtual as a possible call target, as
742 // calls to pure virtuals are UB.
743 if (Fn->getName() == "__cxa_pure_virtual")
744 continue;
745
746 TargetsForSlot.push_back({Fn, &TM});
747 }
748
749 // Give up if we couldn't find any targets.
750 return !TargetsForSlot.empty();
751}
752
753void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
754 Constant *TheFn, bool &IsExported) {
755 auto Apply = [&](CallSiteInfo &CSInfo) {
756 for (auto &&VCallSite : CSInfo.CallSites) {
757 if (RemarksEnabled)
758 VCallSite.emitRemark("single-impl", TheFn->getName(), OREGetter);
759 VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
760 TheFn, VCallSite.CS.getCalledValue()->getType()));
761 // This use is no longer unsafe.
762 if (VCallSite.NumUnsafeUses)
763 --*VCallSite.NumUnsafeUses;
764 }
765 if (CSInfo.isExported())
766 IsExported = true;
767 CSInfo.markDevirt();
768 };
769 Apply(SlotInfo.CSInfo);
770 for (auto &P : SlotInfo.ConstCSInfo)
771 Apply(P.second);
772}
773
774bool DevirtModule::trySingleImplDevirt(
775 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
776 VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
777 // See if the program contains a single implementation of this virtual
778 // function.
779 Function *TheFn = TargetsForSlot[0].Fn;
780 for (auto &&Target : TargetsForSlot)
781 if (TheFn != Target.Fn)
782 return false;
783
784 // If so, update each call site to call that implementation directly.
785 if (RemarksEnabled)
786 TargetsForSlot[0].WasDevirt = true;
787
788 bool IsExported = false;
789 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
790 if (!IsExported)
791 return false;
792
793 // If the only implementation has local linkage, we must promote to external
794 // to make it visible to thin LTO objects. We can only get here during the
795 // ThinLTO export phase.
796 if (TheFn->hasLocalLinkage()) {
797 std::string NewName = (TheFn->getName() + "$merged").str();
798
799 // Since we are renaming the function, any comdats with the same name must
800 // also be renamed. This is required when targeting COFF, as the comdat name
801 // must match one of the names of the symbols in the comdat.
802 if (Comdat *C = TheFn->getComdat()) {
803 if (C->getName() == TheFn->getName()) {
804 Comdat *NewC = M.getOrInsertComdat(NewName);
805 NewC->setSelectionKind(C->getSelectionKind());
806 for (GlobalObject &GO : M.global_objects())
807 if (GO.getComdat() == C)
808 GO.setComdat(NewC);
809 }
810 }
811
812 TheFn->setLinkage(GlobalValue::ExternalLinkage);
813 TheFn->setVisibility(GlobalValue::HiddenVisibility);
814 TheFn->setName(NewName);
815 }
816
817 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
818 Res->SingleImplName = TheFn->getName();
819
820 return true;
821}
822
823void DevirtModule::tryICallBranchFunnel(
824 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
825 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
826 Triple T(M.getTargetTriple());
827 if (T.getArch() != Triple::x86_64)
828 return;
829
830 if (TargetsForSlot.size() > ClThreshold)
831 return;
832
833 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
834 if (!HasNonDevirt)
835 for (auto &P : SlotInfo.ConstCSInfo)
836 if (!P.second.AllCallSitesDevirted) {
837 HasNonDevirt = true;
838 break;
839 }
840
841 if (!HasNonDevirt)
842 return;
843
844 FunctionType *FT =
845 FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
846 Function *JT;
847 if (isa<MDString>(Slot.TypeID)) {
848 JT = Function::Create(FT, Function::ExternalLinkage,
849 getGlobalName(Slot, {}, "branch_funnel"), &M);
850 JT->setVisibility(GlobalValue::HiddenVisibility);
851 } else {
852 JT = Function::Create(FT, Function::InternalLinkage, "branch_funnel", &M);
853 }
854 JT->addAttribute(1, Attribute::Nest);
855
856 std::vector<Value *> JTArgs;
857 JTArgs.push_back(JT->arg_begin());
858 for (auto &T : TargetsForSlot) {
859 JTArgs.push_back(getMemberAddr(T.TM));
860 JTArgs.push_back(T.Fn);
861 }
862
863 BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
864 Constant *Intr =
865 Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
866
867 auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
868 CI->setTailCallKind(CallInst::TCK_MustTail);
869 ReturnInst::Create(M.getContext(), nullptr, BB);
870
871 bool IsExported = false;
872 applyICallBranchFunnel(SlotInfo, JT, IsExported);
873 if (IsExported)
874 Res->TheKind = WholeProgramDevirtResolution::BranchFunnel;
875}
876
877void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
878 Constant *JT, bool &IsExported) {
879 auto Apply = [&](CallSiteInfo &CSInfo) {
880 if (CSInfo.isExported())
881 IsExported = true;
882 if (CSInfo.AllCallSitesDevirted)
883 return;
884 for (auto &&VCallSite : CSInfo.CallSites) {
885 CallSite CS = VCallSite.CS;
886
887 // Jump tables are only profitable if the retpoline mitigation is enabled.
888 Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
889 if (FSAttr.hasAttribute(Attribute::None) ||
890 !FSAttr.getValueAsString().contains("+retpoline"))
891 continue;
892
893 if (RemarksEnabled)
894 VCallSite.emitRemark("branch-funnel", JT->getName(), OREGetter);
895
896 // Pass the address of the vtable in the nest register, which is r10 on
897 // x86_64.
898 std::vector<Type *> NewArgs;
899 NewArgs.push_back(Int8PtrTy);
900 for (Type *T : CS.getFunctionType()->params())
901 NewArgs.push_back(T);
902 PointerType *NewFT = PointerType::getUnqual(
903 FunctionType::get(CS.getFunctionType()->getReturnType(), NewArgs,
904 CS.getFunctionType()->isVarArg()));
905
906 IRBuilder<> IRB(CS.getInstruction());
907 std::vector<Value *> Args;
908 Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
909 for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
910 Args.push_back(CS.getArgOperand(I));
911
912 CallSite NewCS;
913 if (CS.isCall())
914 NewCS = IRB.CreateCall(IRB.CreateBitCast(JT, NewFT), Args);
915 else
916 NewCS = IRB.CreateInvoke(
917 IRB.CreateBitCast(JT, NewFT),
918 cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
919 cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
920 NewCS.setCallingConv(CS.getCallingConv());
921
922 AttributeList Attrs = CS.getAttributes();
923 std::vector<AttributeSet> NewArgAttrs;
924 NewArgAttrs.push_back(AttributeSet::get(
925 M.getContext(), ArrayRef<Attribute>{Attribute::get(
926 M.getContext(), Attribute::Nest)}));
927 for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
928 NewArgAttrs.push_back(Attrs.getParamAttributes(I));
929 NewCS.setAttributes(
930 AttributeList::get(M.getContext(), Attrs.getFnAttributes(),
931 Attrs.getRetAttributes(), NewArgAttrs));
932
933 CS->replaceAllUsesWith(NewCS.getInstruction());
934 CS->eraseFromParent();
935
936 // This use is no longer unsafe.
937 if (VCallSite.NumUnsafeUses)
938 --*VCallSite.NumUnsafeUses;
939 }
940 // Don't mark as devirtualized because there may be callers compiled without
941 // retpoline mitigation, which would mean that they are lowered to
942 // llvm.type.test and therefore require an llvm.type.test resolution for the
943 // type identifier.
944 };
945 Apply(SlotInfo.CSInfo);
946 for (auto &P : SlotInfo.ConstCSInfo)
947 Apply(P.second);
948}
949
950bool DevirtModule::tryEvaluateFunctionsWithArgs(
951 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
952 ArrayRef<uint64_t> Args) {
953 // Evaluate each function and store the result in each target's RetVal
954 // field.
955 for (VirtualCallTarget &Target : TargetsForSlot) {
956 if (Target.Fn->arg_size() != Args.size() + 1)
957 return false;
958
959 Evaluator Eval(M.getDataLayout(), nullptr);
960 SmallVector<Constant *, 2> EvalArgs;
961 EvalArgs.push_back(
962 Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
963 for (unsigned I = 0; I != Args.size(); ++I) {
964 auto *ArgTy = dyn_cast<IntegerType>(
965 Target.Fn->getFunctionType()->getParamType(I + 1));
966 if (!ArgTy)
967 return false;
968 EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
969 }
970
971 Constant *RetVal;
972 if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
973 !isa<ConstantInt>(RetVal))
974 return false;
975 Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
976 }
977 return true;
978}
979
980void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
981 uint64_t TheRetVal) {
982 for (auto Call : CSInfo.CallSites)
983 Call.replaceAndErase(
984 "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
985 ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
986 CSInfo.markDevirt();
987}
988
989bool DevirtModule::tryUniformRetValOpt(
990 MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
991 WholeProgramDevirtResolution::ByArg *Res) {
992 // Uniform return value optimization. If all functions return the same
993 // constant, replace all calls with that constant.
994 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
995 for (const VirtualCallTarget &Target : TargetsForSlot)
996 if (Target.RetVal != TheRetVal)
997 return false;
998
999 if (CSInfo.isExported()) {
1000 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
1001 Res->Info = TheRetVal;
1002 }
1003
1004 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1005 if (RemarksEnabled)
1006 for (auto &&Target : TargetsForSlot)
1007 Target.WasDevirt = true;
1008 return true;
1009}
1010
1011std::string DevirtModule::getGlobalName(VTableSlot Slot,
1012 ArrayRef<uint64_t> Args,
1013 StringRef Name) {
1014 std::string FullName = "__typeid_";
1015 raw_string_ostream OS(FullName);
1016 OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1017 for (uint64_t Arg : Args)
1018 OS << '_' << Arg;
1019 OS << '_' << Name;
1020 return OS.str();
1021}
1022
1023bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1024 Triple T(M.getTargetTriple());
1025 return (T.getArch() == Triple::x86 || T.getArch() == Triple::x86_64) &&
1026 T.getObjectFormat() == Triple::ELF;
1027}
1028
1029void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1030 StringRef Name, Constant *C) {
1031 GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
1032 getGlobalName(Slot, Args, Name), C, &M);
1033 GA->setVisibility(GlobalValue::HiddenVisibility);
1034}
1035
1036void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1037 StringRef Name, uint32_t Const,
1038 uint32_t &Storage) {
1039 if (shouldExportConstantsAsAbsoluteSymbols()) {
1040 exportGlobal(
1041 Slot, Args, Name,
1042 ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1043 return;
1044 }
1045
1046 Storage = Const;
1047}
1048
1049Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1050 StringRef Name) {
1051 Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
1052 auto *GV = dyn_cast<GlobalVariable>(C);
1053 if (GV)
1054 GV->setVisibility(GlobalValue::HiddenVisibility);
1055 return C;
1056}
1057
1058Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1059 StringRef Name, IntegerType *IntTy,
1060 uint32_t Storage) {
1061 if (!shouldExportConstantsAsAbsoluteSymbols())
1062 return ConstantInt::get(IntTy, Storage);
1063
1064 Constant *C = importGlobal(Slot, Args, Name);
1065 auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1066 C = ConstantExpr::getPtrToInt(C, IntTy);
1067
1068 // We only need to set metadata if the global is newly created, in which
1069 // case it would not have hidden visibility.
1070 if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1071 return C;
1072
1073 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1074 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1075 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1076 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1077 MDNode::get(M.getContext(), {MinC, MaxC}));
1078 };
1079 unsigned AbsWidth = IntTy->getBitWidth();
1080 if (AbsWidth == IntPtrTy->getBitWidth())
1081 SetAbsRange(~0ull, ~0ull); // Full set.
1082 else
1083 SetAbsRange(0, 1ull << AbsWidth);
1084 return C;
1085}
1086
1087void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1088 bool IsOne,
1089 Constant *UniqueMemberAddr) {
1090 for (auto &&Call : CSInfo.CallSites) {
1091 IRBuilder<> B(Call.CS.getInstruction());
1092 Value *Cmp =
1093 B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
1094 B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
1095 Cmp = B.CreateZExt(Cmp, Call.CS->getType());
1096 Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1097 Cmp);
1098 }
1099 CSInfo.markDevirt();
1100}
1101
1102Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1103 Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1104 return ConstantExpr::getGetElementPtr(Int8Ty, C,
1105 ConstantInt::get(Int64Ty, M->Offset));
1106}
1107
1108bool DevirtModule::tryUniqueRetValOpt(
1109 unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1110 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1111 VTableSlot Slot, ArrayRef<uint64_t> Args) {
1112 // IsOne controls whether we look for a 0 or a 1.
1113 auto tryUniqueRetValOptFor = [&](bool IsOne) {
1114 const TypeMemberInfo *UniqueMember = nullptr;
1115 for (const VirtualCallTarget &Target : TargetsForSlot) {
1116 if (Target.RetVal == (IsOne ? 1 : 0)) {
1117 if (UniqueMember)
1118 return false;
1119 UniqueMember = Target.TM;
1120 }
1121 }
1122
1123 // We should have found a unique member or bailed out by now. We already
1124 // checked for a uniform return value in tryUniformRetValOpt.
1125 assert(UniqueMember)(static_cast <bool> (UniqueMember) ? void (0) : __assert_fail
("UniqueMember", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1125, __extension__ __PRETTY_FUNCTION__))
;
1126
1127 Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1128 if (CSInfo.isExported()) {
1129 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
1130 Res->Info = IsOne;
1131
1132 exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1133 }
1134
1135 // Replace each call with the comparison.
1136 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1137 UniqueMemberAddr);
1138
1139 // Update devirtualization statistics for targets.
1140 if (RemarksEnabled)
1141 for (auto &&Target : TargetsForSlot)
1142 Target.WasDevirt = true;
1143
1144 return true;
1145 };
1146
1147 if (BitWidth == 1) {
1148 if (tryUniqueRetValOptFor(true))
1149 return true;
1150 if (tryUniqueRetValOptFor(false))
1151 return true;
1152 }
1153 return false;
1154}
1155
1156void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1157 Constant *Byte, Constant *Bit) {
1158 for (auto Call : CSInfo.CallSites) {
1159 auto *RetType = cast<IntegerType>(Call.CS.getType());
1160 IRBuilder<> B(Call.CS.getInstruction());
1161 Value *Addr =
1162 B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1163 if (RetType->getBitWidth() == 1) {
1164 Value *Bits = B.CreateLoad(Addr);
1165 Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1166 auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1167 Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1168 OREGetter, IsBitSet);
1169 } else {
1170 Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1171 Value *Val = B.CreateLoad(RetType, ValAddr);
1172 Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1173 OREGetter, Val);
1174 }
1175 }
1176 CSInfo.markDevirt();
1177}
1178
1179bool DevirtModule::tryVirtualConstProp(
1180 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1181 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1182 // This only works if the function returns an integer.
1183 auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1184 if (!RetType)
14
Assuming 'RetType' is non-null
15
Taking false branch
1185 return false;
1186 unsigned BitWidth = RetType->getBitWidth();
1187 if (BitWidth > 64)
16
Assuming 'BitWidth' is <= 64
17
Taking false branch
1188 return false;
1189
1190 // Make sure that each function is defined, does not access memory, takes at
1191 // least one argument, does not use its first argument (which we assume is
1192 // 'this'), and has the same return type.
1193 //
1194 // Note that we test whether this copy of the function is readnone, rather
1195 // than testing function attributes, which must hold for any copy of the
1196 // function, even a less optimized version substituted at link time. This is
1197 // sound because the virtual constant propagation optimizations effectively
1198 // inline all implementations of the virtual function into each call site,
1199 // rather than using function attributes to perform local optimization.
1200 for (VirtualCallTarget &Target : TargetsForSlot) {
18
Assuming '__begin1' is equal to '__end1'
1201 if (Target.Fn->isDeclaration() ||
1202 computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1203 MAK_ReadNone ||
1204 Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1205 Target.Fn->getReturnType() != RetType)
1206 return false;
1207 }
1208
1209 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1210 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
19
Taking false branch
1211 continue;
1212
1213 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
20
'ResByArg' initialized to a null pointer value
1214 if (Res)
21
Taking false branch
1215 ResByArg = &Res->ResByArg[CSByConstantArg.first];
1216
1217 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
22
Taking false branch
1218 continue;
1219
1220 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
23
Taking false branch
1221 ResByArg, Slot, CSByConstantArg.first))
1222 continue;
1223
1224 // Find an allocation offset in bits in all vtables associated with the
1225 // type.
1226 uint64_t AllocBefore =
1227 findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1228 uint64_t AllocAfter =
1229 findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1230
1231 // Calculate the total amount of padding needed to store a value at both
1232 // ends of the object.
1233 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1234 for (auto &&Target : TargetsForSlot) {
24
Assuming '__begin2' is equal to '__end2'
1235 TotalPaddingBefore += std::max<int64_t>(
1236 (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1237 TotalPaddingAfter += std::max<int64_t>(
1238 (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1239 }
1240
1241 // If the amount of padding is too large, give up.
1242 // FIXME: do something smarter here.
1243 if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
25
Taking false branch
1244 continue;
1245
1246 // Calculate the offset to the value as a (possibly negative) byte offset
1247 // and (if applicable) a bit offset, and store the values in the targets.
1248 int64_t OffsetByte;
1249 uint64_t OffsetBit;
1250 if (TotalPaddingBefore <= TotalPaddingAfter)
26
Taking true branch
1251 setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1252 OffsetBit);
1253 else
1254 setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1255 OffsetBit);
1256
1257 if (RemarksEnabled)
27
Taking false branch
1258 for (auto &&Target : TargetsForSlot)
1259 Target.WasDevirt = true;
1260
1261
1262 if (CSByConstantArg.second.isExported()) {
28
Taking true branch
1263 ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;
29
Access to field 'TheKind' results in a dereference of a null pointer (loaded from variable 'ResByArg')
1264 exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1265 ResByArg->Byte);
1266 exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1267 ResByArg->Bit);
1268 }
1269
1270 // Rewrite each call to a load from OffsetByte/OffsetBit.
1271 Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1272 Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1273 applyVirtualConstProp(CSByConstantArg.second,
1274 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1275 }
1276 return true;
1277}
1278
1279void DevirtModule::rebuildGlobal(VTableBits &B) {
1280 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1281 return;
1282
1283 // Align each byte array to pointer width.
1284 unsigned PointerSize = M.getDataLayout().getPointerSize();
1285 B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
1286 B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));
1287
1288 // Before was stored in reverse order; flip it now.
1289 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1290 std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1291
1292 // Build an anonymous global containing the before bytes, followed by the
1293 // original initializer, followed by the after bytes.
1294 auto NewInit = ConstantStruct::getAnon(
1295 {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1296 B.GV->getInitializer(),
1297 ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1298 auto NewGV =
1299 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1300 GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1301 NewGV->setSection(B.GV->getSection());
1302 NewGV->setComdat(B.GV->getComdat());
1303
1304 // Copy the original vtable's metadata to the anonymous global, adjusting
1305 // offsets as required.
1306 NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1307
1308 // Build an alias named after the original global, pointing at the second
1309 // element (the original initializer).
1310 auto Alias = GlobalAlias::create(
1311 B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1312 ConstantExpr::getGetElementPtr(
1313 NewInit->getType(), NewGV,
1314 ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
1315 ConstantInt::get(Int32Ty, 1)}),
1316 &M);
1317 Alias->setVisibility(B.GV->getVisibility());
1318 Alias->takeName(B.GV);
1319
1320 B.GV->replaceAllUsesWith(Alias);
1321 B.GV->eraseFromParent();
1322}
1323
1324bool DevirtModule::areRemarksEnabled() {
1325 const auto &FL = M.getFunctionList();
1326 if (FL.empty())
1327 return false;
1328 const Function &Fn = FL.front();
1329
1330 const auto &BBL = Fn.getBasicBlockList();
1331 if (BBL.empty())
1332 return false;
1333 auto DI = OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "", DebugLoc(), &BBL.front());
1334 return DI.isEnabled();
1335}
1336
1337void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1338 Function *AssumeFunc) {
1339 // Find all virtual calls via a virtual table pointer %p under an assumption
1340 // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1341 // points to a member of the type identifier %md. Group calls by (type ID,
1342 // offset) pair (effectively the identity of the virtual function) and store
1343 // to CallSlots.
1344 DenseSet<Value *> SeenPtrs;
1345 for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1346 I != E;) {
1347 auto CI = dyn_cast<CallInst>(I->getUser());
1348 ++I;
1349 if (!CI)
1350 continue;
1351
1352 // Search for virtual calls based on %p and add them to DevirtCalls.
1353 SmallVector<DevirtCallSite, 1> DevirtCalls;
1354 SmallVector<CallInst *, 1> Assumes;
1355 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
1356
1357 // If we found any, add them to CallSlots. Only do this if we haven't seen
1358 // the vtable pointer before, as it may have been CSE'd with pointers from
1359 // other call sites, and we don't want to process call sites multiple times.
1360 if (!Assumes.empty()) {
1361 Metadata *TypeId =
1362 cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1363 Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1364 if (SeenPtrs.insert(Ptr).second) {
1365 for (DevirtCallSite Call : DevirtCalls) {
1366 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1367 }
1368 }
1369 }
1370
1371 // We no longer need the assumes or the type test.
1372 for (auto Assume : Assumes)
1373 Assume->eraseFromParent();
1374 // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1375 // may use the vtable argument later.
1376 if (CI->use_empty())
1377 CI->eraseFromParent();
1378 }
1379}
1380
1381void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1382 Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1383
1384 for (auto I = TypeCheckedLoadFunc->use_begin(),
1385 E = TypeCheckedLoadFunc->use_end();
1386 I != E;) {
1387 auto CI = dyn_cast<CallInst>(I->getUser());
1388 ++I;
1389 if (!CI)
1390 continue;
1391
1392 Value *Ptr = CI->getArgOperand(0);
1393 Value *Offset = CI->getArgOperand(1);
1394 Value *TypeIdValue = CI->getArgOperand(2);
1395 Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1396
1397 SmallVector<DevirtCallSite, 1> DevirtCalls;
1398 SmallVector<Instruction *, 1> LoadedPtrs;
1399 SmallVector<Instruction *, 1> Preds;
1400 bool HasNonCallUses = false;
1401 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1402 HasNonCallUses, CI);
1403
1404 // Start by generating "pessimistic" code that explicitly loads the function
1405 // pointer from the vtable and performs the type check. If possible, we will
1406 // eliminate the load and the type check later.
1407
1408 // If possible, only generate the load at the point where it is used.
1409 // This helps avoid unnecessary spills.
1410 IRBuilder<> LoadB(
1411 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1412 Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1413 Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1414 Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1415
1416 for (Instruction *LoadedPtr : LoadedPtrs) {
1417 LoadedPtr->replaceAllUsesWith(LoadedValue);
1418 LoadedPtr->eraseFromParent();
1419 }
1420
1421 // Likewise for the type test.
1422 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1423 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1424
1425 for (Instruction *Pred : Preds) {
1426 Pred->replaceAllUsesWith(TypeTestCall);
1427 Pred->eraseFromParent();
1428 }
1429
1430 // We have already erased any extractvalue instructions that refer to the
1431 // intrinsic call, but the intrinsic may have other non-extractvalue uses
1432 // (although this is unlikely). In that case, explicitly build a pair and
1433 // RAUW it.
1434 if (!CI->use_empty()) {
1435 Value *Pair = UndefValue::get(CI->getType());
1436 IRBuilder<> B(CI);
1437 Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1438 Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1439 CI->replaceAllUsesWith(Pair);
1440 }
1441
1442 // The number of unsafe uses is initially the number of uses.
1443 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1444 NumUnsafeUses = DevirtCalls.size();
1445
1446 // If the function pointer has a non-call user, we cannot eliminate the type
1447 // check, as one of those users may eventually call the pointer. Increment
1448 // the unsafe use count to make sure it cannot reach zero.
1449 if (HasNonCallUses)
1450 ++NumUnsafeUses;
1451 for (DevirtCallSite Call : DevirtCalls) {
1452 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1453 &NumUnsafeUses);
1454 }
1455
1456 CI->eraseFromParent();
1457 }
1458}
1459
1460void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1461 const TypeIdSummary *TidSummary =
1462 ImportSummary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString());
1463 if (!TidSummary)
1464 return;
1465 auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1466 if (ResI == TidSummary->WPDRes.end())
1467 return;
1468 const WholeProgramDevirtResolution &Res = ResI->second;
1469
1470 if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
1471 // The type of the function in the declaration is irrelevant because every
1472 // call site will cast it to the correct type.
1473 auto *SingleImpl = M.getOrInsertFunction(
1474 Res.SingleImplName, Type::getVoidTy(M.getContext()));
1475
1476 // This is the import phase so we should not be exporting anything.
1477 bool IsExported = false;
1478 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1479 assert(!IsExported)(static_cast <bool> (!IsExported) ? void (0) : __assert_fail
("!IsExported", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1479, __extension__ __PRETTY_FUNCTION__))
;
1480 }
1481
1482 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1483 auto I = Res.ResByArg.find(CSByConstantArg.first);
1484 if (I == Res.ResByArg.end())
1485 continue;
1486 auto &ResByArg = I->second;
1487 // FIXME: We should figure out what to do about the "function name" argument
1488 // to the apply* functions, as the function names are unavailable during the
1489 // importing phase. For now we just pass the empty string. This does not
1490 // impact correctness because the function names are just used for remarks.
1491 switch (ResByArg.TheKind) {
1492 case WholeProgramDevirtResolution::ByArg::UniformRetVal:
1493 applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1494 break;
1495 case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
1496 Constant *UniqueMemberAddr =
1497 importGlobal(Slot, CSByConstantArg.first, "unique_member");
1498 applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1499 UniqueMemberAddr);
1500 break;
1501 }
1502 case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
1503 Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1504 Int32Ty, ResByArg.Byte);
1505 Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1506 ResByArg.Bit);
1507 applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1508 break;
1509 }
1510 default:
1511 break;
1512 }
1513 }
1514
1515 if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) {
1516 auto *JT = M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
1517 Type::getVoidTy(M.getContext()));
1518 bool IsExported = false;
1519 applyICallBranchFunnel(SlotInfo, JT, IsExported);
1520 assert(!IsExported)(static_cast <bool> (!IsExported) ? void (0) : __assert_fail
("!IsExported", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1520, __extension__ __PRETTY_FUNCTION__))
;
1521 }
1522}
1523
1524void DevirtModule::removeRedundantTypeTests() {
1525 auto True = ConstantInt::getTrue(M.getContext());
1526 for (auto &&U : NumUnsafeUsesForTypeTest) {
1527 if (U.second == 0) {
1528 U.first->replaceAllUsesWith(True);
1529 U.first->eraseFromParent();
1530 }
1531 }
1532}
1533
1534bool DevirtModule::run() {
1535 Function *TypeTestFunc =
1536 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1537 Function *TypeCheckedLoadFunc =
1538 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1539 Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1540
1541 // Normally if there are no users of the devirtualization intrinsics in the
1542 // module, this pass has nothing to do. But if we are exporting, we also need
1543 // to handle any users that appear only in the function summaries.
1544 if (!ExportSummary &&
1
Assuming the condition is false
1545 (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1546 AssumeFunc->use_empty()) &&
1547 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1548 return false;
1549
1550 if (TypeTestFunc && AssumeFunc)
2
Assuming 'TypeTestFunc' is null
1551 scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1552
1553 if (TypeCheckedLoadFunc)
3
Assuming 'TypeCheckedLoadFunc' is null
4
Taking false branch
1554 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1555
1556 if (ImportSummary) {
5
Assuming the condition is false
6
Taking false branch
1557 for (auto &S : CallSlots)
1558 importResolution(S.first, S.second);
1559
1560 removeRedundantTypeTests();
1561
1562 // The rest of the code is only necessary when exporting or during regular
1563 // LTO, so we are done.
1564 return true;
1565 }
1566
1567 // Rebuild type metadata into a map for easy lookup.
1568 std::vector<VTableBits> Bits;
1569 DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
1570 buildTypeIdentifierMap(Bits, TypeIdMap);
1571 if (TypeIdMap.empty())
7
Assuming the condition is false
8
Taking false branch
1572 return true;
1573
1574 // Collect information from summary about which calls to try to devirtualize.
1575 if (ExportSummary) {
9
Taking true branch
1576 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
1577 for (auto &P : TypeIdMap) {
1578 if (auto *TypeId = dyn_cast<MDString>(P.first))
1579 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1580 TypeId);
1581 }
1582
1583 for (auto &P : *ExportSummary) {
1584 for (auto &S : P.second.SummaryList) {
1585 auto *FS = dyn_cast<FunctionSummary>(S.get());
1586 if (!FS)
1587 continue;
1588 // FIXME: Only add live functions.
1589 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1590 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1591 CallSlots[{MD, VF.Offset}]
1592 .CSInfo.markSummaryHasTypeTestAssumeUsers();
1593 }
1594 }
1595 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1596 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1597 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1598 }
1599 }
1600 for (const FunctionSummary::ConstVCall &VC :
1601 FS->type_test_assume_const_vcalls()) {
1602 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1603 CallSlots[{MD, VC.VFunc.Offset}]
1604 .ConstCSInfo[VC.Args]
1605 .markSummaryHasTypeTestAssumeUsers();
1606 }
1607 }
1608 for (const FunctionSummary::ConstVCall &VC :
1609 FS->type_checked_load_const_vcalls()) {
1610 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1611 CallSlots[{MD, VC.VFunc.Offset}]
1612 .ConstCSInfo[VC.Args]
1613 .addSummaryTypeCheckedLoadUser(FS);
1614 }
1615 }
1616 }
1617 }
1618 }
1619
1620 // For each (type, offset) pair:
1621 bool DidVirtualConstProp = false;
1622 std::map<std::string, Function*> DevirtTargets;
1623 for (auto &S : CallSlots) {
1624 // Search each of the members of the type identifier for the virtual
1625 // function implementation at offset S.first.ByteOffset, and add to
1626 // TargetsForSlot.
1627 std::vector<VirtualCallTarget> TargetsForSlot;
1628 if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
10
Taking true branch
1629 S.first.ByteOffset)) {
1630 WholeProgramDevirtResolution *Res = nullptr;
1631 if (ExportSummary && isa<MDString>(S.first.TypeID))
11
Assuming the condition is false
1632 Res = &ExportSummary
1633 ->getOrInsertTypeIdSummary(
1634 cast<MDString>(S.first.TypeID)->getString())
1635 .WPDRes[S.first.ByteOffset];
1636
1637 if (!trySingleImplDevirt(TargetsForSlot, S.second, Res)) {
12
Taking true branch
1638 DidVirtualConstProp |=
1639 tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
13
Calling 'DevirtModule::tryVirtualConstProp'
1640
1641 tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
1642 }
1643
1644 // Collect functions devirtualized at least for one call site for stats.
1645 if (RemarksEnabled)
1646 for (const auto &T : TargetsForSlot)
1647 if (T.WasDevirt)
1648 DevirtTargets[T.Fn->getName()] = T.Fn;
1649 }
1650
1651 // CFI-specific: if we are exporting and any llvm.type.checked.load
1652 // intrinsics were *not* devirtualized, we need to add the resulting
1653 // llvm.type.test intrinsics to the function summaries so that the
1654 // LowerTypeTests pass will export them.
1655 if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1656 auto GUID =
1657 GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1658 for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1659 FS->addTypeTest(GUID);
1660 for (auto &CCS : S.second.ConstCSInfo)
1661 for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1662 FS->addTypeTest(GUID);
1663 }
1664 }
1665
1666 if (RemarksEnabled) {
1667 // Generate remarks for each devirtualized function.
1668 for (const auto &DT : DevirtTargets) {
1669 Function *F = DT.second;
1670
1671 using namespace ore;
1672 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "Devirtualized", F)
1673 << "devirtualized "
1674 << NV("FunctionName", F->getName()));
1675 }
1676 }
1677
1678 removeRedundantTypeTests();
1679
1680 // Rebuild each global we touched as part of virtual constant propagation to
1681 // include the before and after bytes.
1682 if (DidVirtualConstProp)
1683 for (VTableBits &B : Bits)
1684 rebuildGlobal(B);
1685
1686 return true;
1687}