Bug Summary

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

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-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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.0.0/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-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
1//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass implements whole program optimization of virtual calls in cases
10// where we know (via !type metadata) that the list of callees is fixed. This
11// includes the following:
12// - Single implementation devirtualization: if a virtual call has a single
13// possible callee, replace all calls with a direct call to that callee.
14// - Virtual constant propagation: if the virtual function's return type is an
15// integer <=64 bits and all possible callees are readnone, for each class and
16// each list of constant arguments: evaluate the function, store the return
17// value alongside the virtual table, and rewrite each virtual call as a load
18// from the virtual table.
19// - Uniform return value optimization: if the conditions for virtual constant
20// propagation hold and each function returns the same constant value, replace
21// each virtual call with that constant.
22// - Unique return value optimization for i1 return values: if the conditions
23// for virtual constant propagation hold and a single vtable's function
24// returns 0, or a single vtable's function returns 1, replace each virtual
25// call with a comparison of the vptr against that vtable's address.
26//
27// This pass is intended to be used during the regular and thin LTO pipelines:
28//
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).
33//
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.
42//
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).
50//
51//===----------------------------------------------------------------------===//
52
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/Bitcode/BitcodeReader.h"
66#include "llvm/Bitcode/BitcodeWriter.h"
67#include "llvm/IR/CallSite.h"
68#include "llvm/IR/Constants.h"
69#include "llvm/IR/DataLayout.h"
70#include "llvm/IR/DebugLoc.h"
71#include "llvm/IR/DerivedTypes.h"
72#include "llvm/IR/Dominators.h"
73#include "llvm/IR/Function.h"
74#include "llvm/IR/GlobalAlias.h"
75#include "llvm/IR/GlobalVariable.h"
76#include "llvm/IR/IRBuilder.h"
77#include "llvm/IR/InstrTypes.h"
78#include "llvm/IR/Instruction.h"
79#include "llvm/IR/Instructions.h"
80#include "llvm/IR/Intrinsics.h"
81#include "llvm/IR/LLVMContext.h"
82#include "llvm/IR/Metadata.h"
83#include "llvm/IR/Module.h"
84#include "llvm/IR/ModuleSummaryIndexYAML.h"
85#include "llvm/InitializePasses.h"
86#include "llvm/Pass.h"
87#include "llvm/PassRegistry.h"
88#include "llvm/PassSupport.h"
89#include "llvm/Support/Casting.h"
90#include "llvm/Support/CommandLine.h"
91#include "llvm/Support/Errc.h"
92#include "llvm/Support/Error.h"
93#include "llvm/Support/FileSystem.h"
94#include "llvm/Support/MathExtras.h"
95#include "llvm/Transforms/IPO.h"
96#include "llvm/Transforms/IPO/FunctionAttrs.h"
97#include "llvm/Transforms/Utils/Evaluator.h"
98#include <algorithm>
99#include <cstddef>
100#include <map>
101#include <set>
102#include <string>
103
104using namespace llvm;
105using namespace wholeprogramdevirt;
106
107#define DEBUG_TYPE"wholeprogramdevirt" "wholeprogramdevirt"
108
109static cl::opt<PassSummaryAction> ClSummaryAction(
110 "wholeprogramdevirt-summary-action",
111 cl::desc("What to do with the summary when running this pass"),
112 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing")llvm::cl::OptionEnumValue { "none", int(PassSummaryAction::None
), "Do nothing" }
,
113 clEnumValN(PassSummaryAction::Import, "import",llvm::cl::OptionEnumValue { "import", int(PassSummaryAction::
Import), "Import typeid resolutions from summary and globals"
}
114 "Import typeid resolutions from summary and globals")llvm::cl::OptionEnumValue { "import", int(PassSummaryAction::
Import), "Import typeid resolutions from summary and globals"
}
,
115 clEnumValN(PassSummaryAction::Export, "export",llvm::cl::OptionEnumValue { "export", int(PassSummaryAction::
Export), "Export typeid resolutions to summary and globals" }
116 "Export typeid resolutions to summary and globals")llvm::cl::OptionEnumValue { "export", int(PassSummaryAction::
Export), "Export typeid resolutions to summary and globals" }
),
117 cl::Hidden);
118
119static cl::opt<std::string> ClReadSummary(
120 "wholeprogramdevirt-read-summary",
121 cl::desc(
122 "Read summary from given bitcode or YAML file before running pass"),
123 cl::Hidden);
124
125static cl::opt<std::string> ClWriteSummary(
126 "wholeprogramdevirt-write-summary",
127 cl::desc("Write summary to given bitcode or YAML file after running pass. "
128 "Output file format is deduced from extension: *.bc means writing "
129 "bitcode, otherwise YAML"),
130 cl::Hidden);
131
132static cl::opt<unsigned>
133 ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
134 cl::init(10), cl::ZeroOrMore,
135 cl::desc("Maximum number of call targets per "
136 "call site to enable branch funnels"));
137
138static cl::opt<bool>
139 PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,
140 cl::init(false), cl::ZeroOrMore,
141 cl::desc("Print index-based devirtualization messages"));
142
143/// Provide a way to force enable whole program visibility in tests.
144/// This is needed to support legacy tests that don't contain
145/// !vcall_visibility metadata (the mere presense of type tests
146/// previously implied hidden visibility).
147cl::opt<bool>
148 WholeProgramVisibility("whole-program-visibility", cl::init(false),
149 cl::Hidden, cl::ZeroOrMore,
150 cl::desc("Enable whole program visibility"));
151
152/// Provide a way to force disable whole program for debugging or workarounds,
153/// when enabled via the linker.
154cl::opt<bool> DisableWholeProgramVisibility(
155 "disable-whole-program-visibility", cl::init(false), cl::Hidden,
156 cl::ZeroOrMore,
157 cl::desc("Disable whole program visibility (overrides enabling options)"));
158
159// Find the minimum offset that we may store a value of size Size bits at. If
160// IsAfter is set, look for an offset before the object, otherwise look for an
161// offset after the object.
162uint64_t
163wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
164 bool IsAfter, uint64_t Size) {
165 // Find a minimum offset taking into account only vtable sizes.
166 uint64_t MinByte = 0;
167 for (const VirtualCallTarget &Target : Targets) {
168 if (IsAfter)
169 MinByte = std::max(MinByte, Target.minAfterBytes());
170 else
171 MinByte = std::max(MinByte, Target.minBeforeBytes());
172 }
173
174 // Build a vector of arrays of bytes covering, for each target, a slice of the
175 // used region (see AccumBitVector::BytesUsed in
176 // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
177 // this aligns the used regions to start at MinByte.
178 //
179 // In this example, A, B and C are vtables, # is a byte already allocated for
180 // a virtual function pointer, AAAA... (etc.) are the used regions for the
181 // vtables and Offset(X) is the value computed for the Offset variable below
182 // for X.
183 //
184 // Offset(A)
185 // | |
186 // |MinByte
187 // A: ################AAAAAAAA|AAAAAAAA
188 // B: ########BBBBBBBBBBBBBBBB|BBBB
189 // C: ########################|CCCCCCCCCCCCCCCC
190 // | Offset(B) |
191 //
192 // This code produces the slices of A, B and C that appear after the divider
193 // at MinByte.
194 std::vector<ArrayRef<uint8_t>> Used;
195 for (const VirtualCallTarget &Target : Targets) {
196 ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
197 : Target.TM->Bits->Before.BytesUsed;
198 uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
199 : MinByte - Target.minBeforeBytes();
200
201 // Disregard used regions that are smaller than Offset. These are
202 // effectively all-free regions that do not need to be checked.
203 if (VTUsed.size() > Offset)
204 Used.push_back(VTUsed.slice(Offset));
205 }
206
207 if (Size == 1) {
208 // Find a free bit in each member of Used.
209 for (unsigned I = 0;; ++I) {
210 uint8_t BitsUsed = 0;
211 for (auto &&B : Used)
212 if (I < B.size())
213 BitsUsed |= B[I];
214 if (BitsUsed != 0xff)
215 return (MinByte + I) * 8 +
216 countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
217 }
218 } else {
219 // Find a free (Size/8) byte region in each member of Used.
220 // FIXME: see if alignment helps.
221 for (unsigned I = 0;; ++I) {
222 for (auto &&B : Used) {
223 unsigned Byte = 0;
224 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
225 if (B[I + Byte])
226 goto NextI;
227 ++Byte;
228 }
229 }
230 return (MinByte + I) * 8;
231 NextI:;
232 }
233 }
234}
235
236void wholeprogramdevirt::setBeforeReturnValues(
237 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
238 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
239 if (BitWidth == 1)
240 OffsetByte = -(AllocBefore / 8 + 1);
241 else
242 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
243 OffsetBit = AllocBefore % 8;
244
245 for (VirtualCallTarget &Target : Targets) {
246 if (BitWidth == 1)
247 Target.setBeforeBit(AllocBefore);
248 else
249 Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
250 }
251}
252
253void wholeprogramdevirt::setAfterReturnValues(
254 MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
255 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
256 if (BitWidth == 1)
257 OffsetByte = AllocAfter / 8;
258 else
259 OffsetByte = (AllocAfter + 7) / 8;
260 OffsetBit = AllocAfter % 8;
261
262 for (VirtualCallTarget &Target : Targets) {
263 if (BitWidth == 1)
264 Target.setAfterBit(AllocAfter);
265 else
266 Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
267 }
268}
269
270VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
271 : Fn(Fn), TM(TM),
272 IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
273
274namespace {
275
276// A slot in a set of virtual tables. The TypeID identifies the set of virtual
277// tables, and the ByteOffset is the offset in bytes from the address point to
278// the virtual function pointer.
279struct VTableSlot {
280 Metadata *TypeID;
281 uint64_t ByteOffset;
282};
283
284} // end anonymous namespace
285
286namespace llvm {
287
288template <> struct DenseMapInfo<VTableSlot> {
289 static VTableSlot getEmptyKey() {
290 return {DenseMapInfo<Metadata *>::getEmptyKey(),
291 DenseMapInfo<uint64_t>::getEmptyKey()};
292 }
293 static VTableSlot getTombstoneKey() {
294 return {DenseMapInfo<Metadata *>::getTombstoneKey(),
295 DenseMapInfo<uint64_t>::getTombstoneKey()};
296 }
297 static unsigned getHashValue(const VTableSlot &I) {
298 return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
299 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
300 }
301 static bool isEqual(const VTableSlot &LHS,
302 const VTableSlot &RHS) {
303 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
304 }
305};
306
307template <> struct DenseMapInfo<VTableSlotSummary> {
308 static VTableSlotSummary getEmptyKey() {
309 return {DenseMapInfo<StringRef>::getEmptyKey(),
310 DenseMapInfo<uint64_t>::getEmptyKey()};
311 }
312 static VTableSlotSummary getTombstoneKey() {
313 return {DenseMapInfo<StringRef>::getTombstoneKey(),
314 DenseMapInfo<uint64_t>::getTombstoneKey()};
315 }
316 static unsigned getHashValue(const VTableSlotSummary &I) {
317 return DenseMapInfo<StringRef>::getHashValue(I.TypeID) ^
318 DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
319 }
320 static bool isEqual(const VTableSlotSummary &LHS,
321 const VTableSlotSummary &RHS) {
322 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
323 }
324};
325
326} // end namespace llvm
327
328namespace {
329
330// A virtual call site. VTable is the loaded virtual table pointer, and CS is
331// the indirect virtual call.
332struct VirtualCallSite {
333 Value *VTable;
334 CallSite CS;
335
336 // If non-null, this field points to the associated unsafe use count stored in
337 // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
338 // of that field for details.
339 unsigned *NumUnsafeUses;
340
341 void
342 emitRemark(const StringRef OptName, const StringRef TargetName,
343 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter) {
344 Function *F = CS.getCaller();
345 DebugLoc DLoc = CS->getDebugLoc();
346 BasicBlock *Block = CS.getParent();
347
348 using namespace ore;
349 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", OptName, DLoc, Block)
350 << NV("Optimization", OptName)
351 << ": devirtualized a call to "
352 << NV("FunctionName", TargetName));
353 }
354
355 void replaceAndErase(
356 const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
357 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
358 Value *New) {
359 if (RemarksEnabled)
360 emitRemark(OptName, TargetName, OREGetter);
361 CS->replaceAllUsesWith(New);
362 if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
363 BranchInst::Create(II->getNormalDest(), CS.getInstruction());
364 II->getUnwindDest()->removePredecessor(II->getParent());
365 }
366 CS->eraseFromParent();
367 // This use is no longer unsafe.
368 if (NumUnsafeUses)
369 --*NumUnsafeUses;
370 }
371};
372
373// Call site information collected for a specific VTableSlot and possibly a list
374// of constant integer arguments. The grouping by arguments is handled by the
375// VTableSlotInfo class.
376struct CallSiteInfo {
377 /// The set of call sites for this slot. Used during regular LTO and the
378 /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
379 /// call sites that appear in the merged module itself); in each of these
380 /// cases we are directly operating on the call sites at the IR level.
381 std::vector<VirtualCallSite> CallSites;
382
383 /// Whether all call sites represented by this CallSiteInfo, including those
384 /// in summaries, have been devirtualized. This starts off as true because a
385 /// default constructed CallSiteInfo represents no call sites.
386 bool AllCallSitesDevirted = true;
387
388 // These fields are used during the export phase of ThinLTO and reflect
389 // information collected from function summaries.
390
391 /// Whether any function summary contains an llvm.assume(llvm.type.test) for
392 /// this slot.
393 bool SummaryHasTypeTestAssumeUsers = false;
394
395 /// CFI-specific: a vector containing the list of function summaries that use
396 /// the llvm.type.checked.load intrinsic and therefore will require
397 /// resolutions for llvm.type.test in order to implement CFI checks if
398 /// devirtualization was unsuccessful. If devirtualization was successful, the
399 /// pass will clear this vector by calling markDevirt(). If at the end of the
400 /// pass the vector is non-empty, we will need to add a use of llvm.type.test
401 /// to each of the function summaries in the vector.
402 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
403 std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
404
405 bool isExported() const {
406 return SummaryHasTypeTestAssumeUsers ||
32
Assuming field 'SummaryHasTypeTestAssumeUsers' is true
33
Returning the value 1, which participates in a condition later
407 !SummaryTypeCheckedLoadUsers.empty();
408 }
409
410 void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
411 SummaryTypeCheckedLoadUsers.push_back(FS);
412 AllCallSitesDevirted = false;
413 }
414
415 void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
416 SummaryTypeTestAssumeUsers.push_back(FS);
417 SummaryHasTypeTestAssumeUsers = true;
418 AllCallSitesDevirted = false;
419 }
420
421 void markDevirt() {
422 AllCallSitesDevirted = true;
423
424 // As explained in the comment for SummaryTypeCheckedLoadUsers.
425 SummaryTypeCheckedLoadUsers.clear();
426 }
427};
428
429// Call site information collected for a specific VTableSlot.
430struct VTableSlotInfo {
431 // The set of call sites which do not have all constant integer arguments
432 // (excluding "this").
433 CallSiteInfo CSInfo;
434
435 // The set of call sites with all constant integer arguments (excluding
436 // "this"), grouped by argument list.
437 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
438
439 void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
440
441private:
442 CallSiteInfo &findCallSiteInfo(CallSite CS);
443};
444
445CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
446 std::vector<uint64_t> Args;
447 auto *CI = dyn_cast<IntegerType>(CS.getType());
448 if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
449 return CSInfo;
450 for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
451 auto *CI = dyn_cast<ConstantInt>(Arg);
452 if (!CI || CI->getBitWidth() > 64)
453 return CSInfo;
454 Args.push_back(CI->getZExtValue());
455 }
456 return ConstCSInfo[Args];
457}
458
459void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
460 unsigned *NumUnsafeUses) {
461 auto &CSI = findCallSiteInfo(CS);
462 CSI.AllCallSitesDevirted = false;
463 CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
464}
465
466struct DevirtModule {
467 Module &M;
468 function_ref<AAResults &(Function &)> AARGetter;
469 function_ref<DominatorTree &(Function &)> LookupDomTree;
470
471 ModuleSummaryIndex *ExportSummary;
472 const ModuleSummaryIndex *ImportSummary;
473
474 IntegerType *Int8Ty;
475 PointerType *Int8PtrTy;
476 IntegerType *Int32Ty;
477 IntegerType *Int64Ty;
478 IntegerType *IntPtrTy;
479
480 bool RemarksEnabled;
481 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter;
482
483 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
484
485 // This map keeps track of the number of "unsafe" uses of a loaded function
486 // pointer. The key is the associated llvm.type.test intrinsic call generated
487 // by this pass. An unsafe use is one that calls the loaded function pointer
488 // directly. Every time we eliminate an unsafe use (for example, by
489 // devirtualizing it or by applying virtual constant propagation), we
490 // decrement the value stored in this map. If a value reaches zero, we can
491 // eliminate the type check by RAUWing the associated llvm.type.test call with
492 // true.
493 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
494
495 DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
496 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
497 function_ref<DominatorTree &(Function &)> LookupDomTree,
498 ModuleSummaryIndex *ExportSummary,
499 const ModuleSummaryIndex *ImportSummary)
500 : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
501 ExportSummary(ExportSummary), ImportSummary(ImportSummary),
502 Int8Ty(Type::getInt8Ty(M.getContext())),
503 Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
504 Int32Ty(Type::getInt32Ty(M.getContext())),
505 Int64Ty(Type::getInt64Ty(M.getContext())),
506 IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
507 RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
508 assert(!(ExportSummary && ImportSummary))((!(ExportSummary && ImportSummary)) ? static_cast<
void> (0) : __assert_fail ("!(ExportSummary && ImportSummary)"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 508, __PRETTY_FUNCTION__))
;
509 }
510
511 bool areRemarksEnabled();
512
513 void scanTypeTestUsers(Function *TypeTestFunc);
514 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
515
516 void buildTypeIdentifierMap(
517 std::vector<VTableBits> &Bits,
518 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
519 bool
520 tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
521 const std::set<TypeMemberInfo> &TypeMemberInfos,
522 uint64_t ByteOffset);
523
524 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
525 bool &IsExported);
526 bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,
527 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
528 VTableSlotInfo &SlotInfo,
529 WholeProgramDevirtResolution *Res);
530
531 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
532 bool &IsExported);
533 void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
534 VTableSlotInfo &SlotInfo,
535 WholeProgramDevirtResolution *Res, VTableSlot Slot);
536
537 bool tryEvaluateFunctionsWithArgs(
538 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
539 ArrayRef<uint64_t> Args);
540
541 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
542 uint64_t TheRetVal);
543 bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
544 CallSiteInfo &CSInfo,
545 WholeProgramDevirtResolution::ByArg *Res);
546
547 // Returns the global symbol name that is used to export information about the
548 // given vtable slot and list of arguments.
549 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
550 StringRef Name);
551
552 bool shouldExportConstantsAsAbsoluteSymbols();
553
554 // This function is called during the export phase to create a symbol
555 // definition containing information about the given vtable slot and list of
556 // arguments.
557 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
558 Constant *C);
559 void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
560 uint32_t Const, uint32_t &Storage);
561
562 // This function is called during the import phase to create a reference to
563 // the symbol definition created during the export phase.
564 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
565 StringRef Name);
566 Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
567 StringRef Name, IntegerType *IntTy,
568 uint32_t Storage);
569
570 Constant *getMemberAddr(const TypeMemberInfo *M);
571
572 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
573 Constant *UniqueMemberAddr);
574 bool tryUniqueRetValOpt(unsigned BitWidth,
575 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
576 CallSiteInfo &CSInfo,
577 WholeProgramDevirtResolution::ByArg *Res,
578 VTableSlot Slot, ArrayRef<uint64_t> Args);
579
580 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
581 Constant *Byte, Constant *Bit);
582 bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
583 VTableSlotInfo &SlotInfo,
584 WholeProgramDevirtResolution *Res, VTableSlot Slot);
585
586 void rebuildGlobal(VTableBits &B);
587
588 // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
589 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
590
591 // If we were able to eliminate all unsafe uses for a type checked load,
592 // eliminate the associated type tests by replacing them with true.
593 void removeRedundantTypeTests();
594
595 bool run();
596
597 // Lower the module using the action and summary passed as command line
598 // arguments. For testing purposes only.
599 static bool
600 runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
601 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
602 function_ref<DominatorTree &(Function &)> LookupDomTree);
603};
604
605struct DevirtIndex {
606 ModuleSummaryIndex &ExportSummary;
607 // The set in which to record GUIDs exported from their module by
608 // devirtualization, used by client to ensure they are not internalized.
609 std::set<GlobalValue::GUID> &ExportedGUIDs;
610 // A map in which to record the information necessary to locate the WPD
611 // resolution for local targets in case they are exported by cross module
612 // importing.
613 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
614
615 MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;
616
617 DevirtIndex(
618 ModuleSummaryIndex &ExportSummary,
619 std::set<GlobalValue::GUID> &ExportedGUIDs,
620 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
621 : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
622 LocalWPDTargetsMap(LocalWPDTargetsMap) {}
623
624 bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
625 const TypeIdCompatibleVtableInfo TIdInfo,
626 uint64_t ByteOffset);
627
628 bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
629 VTableSlotSummary &SlotSummary,
630 VTableSlotInfo &SlotInfo,
631 WholeProgramDevirtResolution *Res,
632 std::set<ValueInfo> &DevirtTargets);
633
634 void run();
635};
636
637struct WholeProgramDevirt : public ModulePass {
638 static char ID;
639
640 bool UseCommandLine = false;
641
642 ModuleSummaryIndex *ExportSummary = nullptr;
643 const ModuleSummaryIndex *ImportSummary = nullptr;
644
645 WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
646 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
647 }
648
649 WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
650 const ModuleSummaryIndex *ImportSummary)
651 : ModulePass(ID), ExportSummary(ExportSummary),
652 ImportSummary(ImportSummary) {
653 initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
654 }
655
656 bool runOnModule(Module &M) override {
657 if (skipModule(M))
658 return false;
659
660 // In the new pass manager, we can request the optimization
661 // remark emitter pass on a per-function-basis, which the
662 // OREGetter will do for us.
663 // In the old pass manager, this is harder, so we just build
664 // an optimization remark emitter on the fly, when we need it.
665 std::unique_ptr<OptimizationRemarkEmitter> ORE;
666 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
667 ORE = std::make_unique<OptimizationRemarkEmitter>(F);
668 return *ORE;
669 };
670
671 auto LookupDomTree = [this](Function &F) -> DominatorTree & {
672 return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
673 };
674
675 if (UseCommandLine)
676 return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter,
677 LookupDomTree);
678
679 return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree,
680 ExportSummary, ImportSummary)
681 .run();
682 }
683
684 void getAnalysisUsage(AnalysisUsage &AU) const override {
685 AU.addRequired<AssumptionCacheTracker>();
686 AU.addRequired<TargetLibraryInfoWrapperPass>();
687 AU.addRequired<DominatorTreeWrapperPass>();
688 }
689};
690
691} // end anonymous namespace
692
693INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",static void *initializeWholeProgramDevirtPassOnce(PassRegistry
&Registry) {
694 "Whole program devirtualization", false, false)static void *initializeWholeProgramDevirtPassOnce(PassRegistry
&Registry) {
695INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
696INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
697INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
698INITIALIZE_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)); }
699 "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)); }
700char WholeProgramDevirt::ID = 0;
701
702ModulePass *
703llvm::createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
704 const ModuleSummaryIndex *ImportSummary) {
705 return new WholeProgramDevirt(ExportSummary, ImportSummary);
706}
707
708PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
709 ModuleAnalysisManager &AM) {
710 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
711 auto AARGetter = [&](Function &F) -> AAResults & {
712 return FAM.getResult<AAManager>(F);
713 };
714 auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
715 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
716 };
717 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
718 return FAM.getResult<DominatorTreeAnalysis>(F);
719 };
720 if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
721 ImportSummary)
722 .run())
723 return PreservedAnalyses::all();
724 return PreservedAnalyses::none();
725}
726
727// Enable whole program visibility if enabled by client (e.g. linker) or
728// internal option, and not force disabled.
729static bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) {
730 return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) &&
731 !DisableWholeProgramVisibility;
732}
733
734namespace llvm {
735
736/// If whole program visibility asserted, then upgrade all public vcall
737/// visibility metadata on vtable definitions to linkage unit visibility in
738/// Module IR (for regular or hybrid LTO).
739void updateVCallVisibilityInModule(Module &M,
740 bool WholeProgramVisibilityEnabledInLTO) {
741 if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
742 return;
743 for (GlobalVariable &GV : M.globals())
744 // Add linkage unit visibility to any variable with type metadata, which are
745 // the vtable definitions. We won't have an existing vcall_visibility
746 // metadata on vtable definitions with public visibility.
747 if (GV.hasMetadata(LLVMContext::MD_type) &&
748 GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic)
749 GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit);
750}
751
752/// If whole program visibility asserted, then upgrade all public vcall
753/// visibility metadata on vtable definition summaries to linkage unit
754/// visibility in Module summary index (for ThinLTO).
755void updateVCallVisibilityInIndex(ModuleSummaryIndex &Index,
756 bool WholeProgramVisibilityEnabledInLTO) {
757 if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
758 return;
759 for (auto &P : Index) {
760 for (auto &S : P.second.SummaryList) {
761 auto *GVar = dyn_cast<GlobalVarSummary>(S.get());
762 if (!GVar || GVar->vTableFuncs().empty() ||
763 GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic)
764 continue;
765 GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit);
766 }
767 }
768}
769
770void runWholeProgramDevirtOnIndex(
771 ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
772 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
773 DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
774}
775
776void updateIndexWPDForExports(
777 ModuleSummaryIndex &Summary,
778 function_ref<bool(StringRef, ValueInfo)> isExported,
779 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
780 for (auto &T : LocalWPDTargetsMap) {
781 auto &VI = T.first;
782 // This was enforced earlier during trySingleImplDevirt.
783 assert(VI.getSummaryList().size() == 1 &&((VI.getSummaryList().size() == 1 && "Devirt of local target has more than one copy"
) ? static_cast<void> (0) : __assert_fail ("VI.getSummaryList().size() == 1 && \"Devirt of local target has more than one copy\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 784, __PRETTY_FUNCTION__))
784 "Devirt of local target has more than one copy")((VI.getSummaryList().size() == 1 && "Devirt of local target has more than one copy"
) ? static_cast<void> (0) : __assert_fail ("VI.getSummaryList().size() == 1 && \"Devirt of local target has more than one copy\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 784, __PRETTY_FUNCTION__))
;
785 auto &S = VI.getSummaryList()[0];
786 if (!isExported(S->modulePath(), VI))
787 continue;
788
789 // It's been exported by a cross module import.
790 for (auto &SlotSummary : T.second) {
791 auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
792 assert(TIdSum)((TIdSum) ? static_cast<void> (0) : __assert_fail ("TIdSum"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 792, __PRETTY_FUNCTION__))
;
793 auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
794 assert(WPDRes != TIdSum->WPDRes.end())((WPDRes != TIdSum->WPDRes.end()) ? static_cast<void>
(0) : __assert_fail ("WPDRes != TIdSum->WPDRes.end()", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 794, __PRETTY_FUNCTION__))
;
795 WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
796 WPDRes->second.SingleImplName,
797 Summary.getModuleHash(S->modulePath()));
798 }
799 }
800}
801
802} // end namespace llvm
803
804static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) {
805 // Check that summary index contains regular LTO module when performing
806 // export to prevent occasional use of index from pure ThinLTO compilation
807 // (-fno-split-lto-module). This kind of summary index is passed to
808 // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting.
809 const auto &ModPaths = Summary->modulePaths();
810 if (ClSummaryAction != PassSummaryAction::Import &&
811 ModPaths.find(ModuleSummaryIndex::getRegularLTOModuleName()) ==
812 ModPaths.end())
813 return createStringError(
814 errc::invalid_argument,
815 "combined summary should contain Regular LTO module");
816 return ErrorSuccess();
817}
818
819bool DevirtModule::runForTesting(
820 Module &M, function_ref<AAResults &(Function &)> AARGetter,
821 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
822 function_ref<DominatorTree &(Function &)> LookupDomTree) {
823 std::unique_ptr<ModuleSummaryIndex> Summary =
824 std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false);
825
826 // Handle the command-line summary arguments. This code is for testing
827 // purposes only, so we handle errors directly.
828 if (!ClReadSummary.empty()) {
829 ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
830 ": ");
831 auto ReadSummaryFile =
832 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
833 if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =
834 getModuleSummaryIndex(*ReadSummaryFile)) {
835 Summary = std::move(*SummaryOrErr);
836 ExitOnErr(checkCombinedSummaryForTesting(Summary.get()));
837 } else {
838 // Try YAML if we've failed with bitcode.
839 consumeError(SummaryOrErr.takeError());
840 yaml::Input In(ReadSummaryFile->getBuffer());
841 In >> *Summary;
842 ExitOnErr(errorCodeToError(In.error()));
843 }
844 }
845
846 bool Changed =
847 DevirtModule(M, AARGetter, OREGetter, LookupDomTree,
848 ClSummaryAction == PassSummaryAction::Export ? Summary.get()
849 : nullptr,
850 ClSummaryAction == PassSummaryAction::Import ? Summary.get()
851 : nullptr)
852 .run();
853
854 if (!ClWriteSummary.empty()) {
855 ExitOnError ExitOnErr(
856 "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
857 std::error_code EC;
858 if (StringRef(ClWriteSummary).endswith(".bc")) {
859 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_None);
860 ExitOnErr(errorCodeToError(EC));
861 WriteIndexToFile(*Summary, OS);
862 } else {
863 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_Text);
864 ExitOnErr(errorCodeToError(EC));
865 yaml::Output Out(OS);
866 Out << *Summary;
867 }
868 }
869
870 return Changed;
871}
872
873void DevirtModule::buildTypeIdentifierMap(
874 std::vector<VTableBits> &Bits,
875 DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
876 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
877 Bits.reserve(M.getGlobalList().size());
878 SmallVector<MDNode *, 2> Types;
879 for (GlobalVariable &GV : M.globals()) {
880 Types.clear();
881 GV.getMetadata(LLVMContext::MD_type, Types);
882 if (GV.isDeclaration() || Types.empty())
883 continue;
884
885 VTableBits *&BitsPtr = GVToBits[&GV];
886 if (!BitsPtr) {
887 Bits.emplace_back();
888 Bits.back().GV = &GV;
889 Bits.back().ObjectSize =
890 M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
891 BitsPtr = &Bits.back();
892 }
893
894 for (MDNode *Type : Types) {
895 auto TypeID = Type->getOperand(1).get();
896
897 uint64_t Offset =
898 cast<ConstantInt>(
899 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
900 ->getZExtValue();
901
902 TypeIdMap[TypeID].insert({BitsPtr, Offset});
903 }
904 }
905}
906
907bool DevirtModule::tryFindVirtualCallTargets(
908 std::vector<VirtualCallTarget> &TargetsForSlot,
909 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
910 for (const TypeMemberInfo &TM : TypeMemberInfos) {
911 if (!TM.Bits->GV->isConstant())
912 return false;
913
914 // We cannot perform whole program devirtualization analysis on a vtable
915 // with public LTO visibility.
916 if (TM.Bits->GV->getVCallVisibility() ==
917 GlobalObject::VCallVisibilityPublic)
918 return false;
919
920 Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
921 TM.Offset + ByteOffset, M);
922 if (!Ptr)
923 return false;
924
925 auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
926 if (!Fn)
927 return false;
928
929 // We can disregard __cxa_pure_virtual as a possible call target, as
930 // calls to pure virtuals are UB.
931 if (Fn->getName() == "__cxa_pure_virtual")
932 continue;
933
934 TargetsForSlot.push_back({Fn, &TM});
935 }
936
937 // Give up if we couldn't find any targets.
938 return !TargetsForSlot.empty();
939}
940
941bool DevirtIndex::tryFindVirtualCallTargets(
942 std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo,
943 uint64_t ByteOffset) {
944 for (const TypeIdOffsetVtableInfo &P : TIdInfo) {
945 // Find the first non-available_externally linkage vtable initializer.
946 // We can have multiple available_externally, linkonce_odr and weak_odr
947 // vtable initializers, however we want to skip available_externally as they
948 // do not have type metadata attached, and therefore the summary will not
949 // contain any vtable functions. We can also have multiple external
950 // vtable initializers in the case of comdats, which we cannot check here.
951 // The linker should give an error in this case.
952 //
953 // Also, handle the case of same-named local Vtables with the same path
954 // and therefore the same GUID. This can happen if there isn't enough
955 // distinguishing path when compiling the source file. In that case we
956 // conservatively return false early.
957 const GlobalVarSummary *VS = nullptr;
958 bool LocalFound = false;
959 for (auto &S : P.VTableVI.getSummaryList()) {
960 if (GlobalValue::isLocalLinkage(S->linkage())) {
961 if (LocalFound)
962 return false;
963 LocalFound = true;
964 }
965 if (!GlobalValue::isAvailableExternallyLinkage(S->linkage())) {
966 VS = cast<GlobalVarSummary>(S->getBaseObject());
967 // We cannot perform whole program devirtualization analysis on a vtable
968 // with public LTO visibility.
969 if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic)
970 return false;
971 }
972 }
973 if (!VS->isLive())
974 continue;
975 for (auto VTP : VS->vTableFuncs()) {
976 if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
977 continue;
978
979 TargetsForSlot.push_back(VTP.FuncVI);
980 }
981 }
982
983 // Give up if we couldn't find any targets.
984 return !TargetsForSlot.empty();
985}
986
987void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
988 Constant *TheFn, bool &IsExported) {
989 auto Apply = [&](CallSiteInfo &CSInfo) {
990 for (auto &&VCallSite : CSInfo.CallSites) {
991 if (RemarksEnabled)
992 VCallSite.emitRemark("single-impl",
993 TheFn->stripPointerCasts()->getName(), OREGetter);
994 VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
995 TheFn, VCallSite.CS.getCalledValue()->getType()));
996 // This use is no longer unsafe.
997 if (VCallSite.NumUnsafeUses)
998 --*VCallSite.NumUnsafeUses;
999 }
1000 if (CSInfo.isExported())
1001 IsExported = true;
1002 CSInfo.markDevirt();
1003 };
1004 Apply(SlotInfo.CSInfo);
1005 for (auto &P : SlotInfo.ConstCSInfo)
1006 Apply(P.second);
1007}
1008
1009static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) {
1010 // We can't add calls if we haven't seen a definition
1011 if (Callee.getSummaryList().empty())
1012 return false;
1013
1014 // Insert calls into the summary index so that the devirtualized targets
1015 // are eligible for import.
1016 // FIXME: Annotate type tests with hotness. For now, mark these as hot
1017 // to better ensure we have the opportunity to inline them.
1018 bool IsExported = false;
1019 auto &S = Callee.getSummaryList()[0];
1020 CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0);
1021 auto AddCalls = [&](CallSiteInfo &CSInfo) {
1022 for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1023 FS->addCall({Callee, CI});
1024 IsExported |= S->modulePath() != FS->modulePath();
1025 }
1026 for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
1027 FS->addCall({Callee, CI});
1028 IsExported |= S->modulePath() != FS->modulePath();
1029 }
1030 };
1031 AddCalls(SlotInfo.CSInfo);
1032 for (auto &P : SlotInfo.ConstCSInfo)
1033 AddCalls(P.second);
1034 return IsExported;
1035}
1036
1037bool DevirtModule::trySingleImplDevirt(
1038 ModuleSummaryIndex *ExportSummary,
1039 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1040 WholeProgramDevirtResolution *Res) {
1041 // See if the program contains a single implementation of this virtual
1042 // function.
1043 Function *TheFn = TargetsForSlot[0].Fn;
1044 for (auto &&Target : TargetsForSlot)
1045 if (TheFn != Target.Fn)
1046 return false;
1047
1048 // If so, update each call site to call that implementation directly.
1049 if (RemarksEnabled)
1050 TargetsForSlot[0].WasDevirt = true;
1051
1052 bool IsExported = false;
1053 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
1054 if (!IsExported)
1055 return false;
1056
1057 // If the only implementation has local linkage, we must promote to external
1058 // to make it visible to thin LTO objects. We can only get here during the
1059 // ThinLTO export phase.
1060 if (TheFn->hasLocalLinkage()) {
1061 std::string NewName = (TheFn->getName() + "$merged").str();
1062
1063 // Since we are renaming the function, any comdats with the same name must
1064 // also be renamed. This is required when targeting COFF, as the comdat name
1065 // must match one of the names of the symbols in the comdat.
1066 if (Comdat *C = TheFn->getComdat()) {
1067 if (C->getName() == TheFn->getName()) {
1068 Comdat *NewC = M.getOrInsertComdat(NewName);
1069 NewC->setSelectionKind(C->getSelectionKind());
1070 for (GlobalObject &GO : M.global_objects())
1071 if (GO.getComdat() == C)
1072 GO.setComdat(NewC);
1073 }
1074 }
1075
1076 TheFn->setLinkage(GlobalValue::ExternalLinkage);
1077 TheFn->setVisibility(GlobalValue::HiddenVisibility);
1078 TheFn->setName(NewName);
1079 }
1080 if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID()))
1081 // Any needed promotion of 'TheFn' has already been done during
1082 // LTO unit split, so we can ignore return value of AddCalls.
1083 AddCalls(SlotInfo, TheFnVI);
1084
1085 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
1086 Res->SingleImplName = std::string(TheFn->getName());
1087
1088 return true;
1089}
1090
1091bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
1092 VTableSlotSummary &SlotSummary,
1093 VTableSlotInfo &SlotInfo,
1094 WholeProgramDevirtResolution *Res,
1095 std::set<ValueInfo> &DevirtTargets) {
1096 // See if the program contains a single implementation of this virtual
1097 // function.
1098 auto TheFn = TargetsForSlot[0];
1099 for (auto &&Target : TargetsForSlot)
1100 if (TheFn != Target)
1101 return false;
1102
1103 // Don't devirtualize if we don't have target definition.
1104 auto Size = TheFn.getSummaryList().size();
1105 if (!Size)
1106 return false;
1107
1108 // If the summary list contains multiple summaries where at least one is
1109 // a local, give up, as we won't know which (possibly promoted) name to use.
1110 for (auto &S : TheFn.getSummaryList())
1111 if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1)
1112 return false;
1113
1114 // Collect functions devirtualized at least for one call site for stats.
1115 if (PrintSummaryDevirt)
1116 DevirtTargets.insert(TheFn);
1117
1118 auto &S = TheFn.getSummaryList()[0];
1119 bool IsExported = AddCalls(SlotInfo, TheFn);
1120 if (IsExported)
1121 ExportedGUIDs.insert(TheFn.getGUID());
1122
1123 // Record in summary for use in devirtualization during the ThinLTO import
1124 // step.
1125 Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
1126 if (GlobalValue::isLocalLinkage(S->linkage())) {
1127 if (IsExported)
1128 // If target is a local function and we are exporting it by
1129 // devirtualizing a call in another module, we need to record the
1130 // promoted name.
1131 Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
1132 TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
1133 else {
1134 LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1135 Res->SingleImplName = std::string(TheFn.name());
1136 }
1137 } else
1138 Res->SingleImplName = std::string(TheFn.name());
1139
1140 // Name will be empty if this thin link driven off of serialized combined
1141 // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
1142 // legacy LTO API anyway.
1143 assert(!Res->SingleImplName.empty())((!Res->SingleImplName.empty()) ? static_cast<void> (
0) : __assert_fail ("!Res->SingleImplName.empty()", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1143, __PRETTY_FUNCTION__))
;
1144
1145 return true;
1146}
1147
1148void DevirtModule::tryICallBranchFunnel(
1149 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1150 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1151 Triple T(M.getTargetTriple());
1152 if (T.getArch() != Triple::x86_64)
1153 return;
1154
1155 if (TargetsForSlot.size() > ClThreshold)
1156 return;
1157
1158 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1159 if (!HasNonDevirt)
1160 for (auto &P : SlotInfo.ConstCSInfo)
1161 if (!P.second.AllCallSitesDevirted) {
1162 HasNonDevirt = true;
1163 break;
1164 }
1165
1166 if (!HasNonDevirt)
1167 return;
1168
1169 FunctionType *FT =
1170 FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
1171 Function *JT;
1172 if (isa<MDString>(Slot.TypeID)) {
1173 JT = Function::Create(FT, Function::ExternalLinkage,
1174 M.getDataLayout().getProgramAddressSpace(),
1175 getGlobalName(Slot, {}, "branch_funnel"), &M);
1176 JT->setVisibility(GlobalValue::HiddenVisibility);
1177 } else {
1178 JT = Function::Create(FT, Function::InternalLinkage,
1179 M.getDataLayout().getProgramAddressSpace(),
1180 "branch_funnel", &M);
1181 }
1182 JT->addAttribute(1, Attribute::Nest);
1183
1184 std::vector<Value *> JTArgs;
1185 JTArgs.push_back(JT->arg_begin());
1186 for (auto &T : TargetsForSlot) {
1187 JTArgs.push_back(getMemberAddr(T.TM));
1188 JTArgs.push_back(T.Fn);
1189 }
1190
1191 BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
1192 Function *Intr =
1193 Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
1194
1195 auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
1196 CI->setTailCallKind(CallInst::TCK_MustTail);
1197 ReturnInst::Create(M.getContext(), nullptr, BB);
1198
1199 bool IsExported = false;
1200 applyICallBranchFunnel(SlotInfo, JT, IsExported);
1201 if (IsExported)
1202 Res->TheKind = WholeProgramDevirtResolution::BranchFunnel;
1203}
1204
1205void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1206 Constant *JT, bool &IsExported) {
1207 auto Apply = [&](CallSiteInfo &CSInfo) {
1208 if (CSInfo.isExported())
1209 IsExported = true;
1210 if (CSInfo.AllCallSitesDevirted)
1211 return;
1212 for (auto &&VCallSite : CSInfo.CallSites) {
1213 CallSite CS = VCallSite.CS;
1214
1215 // Jump tables are only profitable if the retpoline mitigation is enabled.
1216 Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
1217 if (FSAttr.hasAttribute(Attribute::None) ||
1218 !FSAttr.getValueAsString().contains("+retpoline"))
1219 continue;
1220
1221 if (RemarksEnabled)
1222 VCallSite.emitRemark("branch-funnel",
1223 JT->stripPointerCasts()->getName(), OREGetter);
1224
1225 // Pass the address of the vtable in the nest register, which is r10 on
1226 // x86_64.
1227 std::vector<Type *> NewArgs;
1228 NewArgs.push_back(Int8PtrTy);
1229 for (Type *T : CS.getFunctionType()->params())
1230 NewArgs.push_back(T);
1231 FunctionType *NewFT =
1232 FunctionType::get(CS.getFunctionType()->getReturnType(), NewArgs,
1233 CS.getFunctionType()->isVarArg());
1234 PointerType *NewFTPtr = PointerType::getUnqual(NewFT);
1235
1236 IRBuilder<> IRB(CS.getInstruction());
1237 std::vector<Value *> Args;
1238 Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
1239 for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
1240 Args.push_back(CS.getArgOperand(I));
1241
1242 CallSite NewCS;
1243 if (CS.isCall())
1244 NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(JT, NewFTPtr), Args);
1245 else
1246 NewCS = IRB.CreateInvoke(
1247 NewFT, IRB.CreateBitCast(JT, NewFTPtr),
1248 cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
1249 cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
1250 NewCS.setCallingConv(CS.getCallingConv());
1251
1252 AttributeList Attrs = CS.getAttributes();
1253 std::vector<AttributeSet> NewArgAttrs;
1254 NewArgAttrs.push_back(AttributeSet::get(
1255 M.getContext(), ArrayRef<Attribute>{Attribute::get(
1256 M.getContext(), Attribute::Nest)}));
1257 for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1258 NewArgAttrs.push_back(Attrs.getParamAttributes(I));
1259 NewCS.setAttributes(
1260 AttributeList::get(M.getContext(), Attrs.getFnAttributes(),
1261 Attrs.getRetAttributes(), NewArgAttrs));
1262
1263 CS->replaceAllUsesWith(NewCS.getInstruction());
1264 CS->eraseFromParent();
1265
1266 // This use is no longer unsafe.
1267 if (VCallSite.NumUnsafeUses)
1268 --*VCallSite.NumUnsafeUses;
1269 }
1270 // Don't mark as devirtualized because there may be callers compiled without
1271 // retpoline mitigation, which would mean that they are lowered to
1272 // llvm.type.test and therefore require an llvm.type.test resolution for the
1273 // type identifier.
1274 };
1275 Apply(SlotInfo.CSInfo);
1276 for (auto &P : SlotInfo.ConstCSInfo)
1277 Apply(P.second);
1278}
1279
1280bool DevirtModule::tryEvaluateFunctionsWithArgs(
1281 MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1282 ArrayRef<uint64_t> Args) {
1283 // Evaluate each function and store the result in each target's RetVal
1284 // field.
1285 for (VirtualCallTarget &Target : TargetsForSlot) {
22
Assuming '__begin1' is equal to '__end1'
1286 if (Target.Fn->arg_size() != Args.size() + 1)
1287 return false;
1288
1289 Evaluator Eval(M.getDataLayout(), nullptr);
1290 SmallVector<Constant *, 2> EvalArgs;
1291 EvalArgs.push_back(
1292 Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
1293 for (unsigned I = 0; I != Args.size(); ++I) {
1294 auto *ArgTy = dyn_cast<IntegerType>(
1295 Target.Fn->getFunctionType()->getParamType(I + 1));
1296 if (!ArgTy)
1297 return false;
1298 EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
1299 }
1300
1301 Constant *RetVal;
1302 if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
1303 !isa<ConstantInt>(RetVal))
1304 return false;
1305 Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
1306 }
1307 return true;
23
Returning the value 1, which participates in a condition later
1308}
1309
1310void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1311 uint64_t TheRetVal) {
1312 for (auto Call : CSInfo.CallSites)
1313 Call.replaceAndErase(
1314 "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1315 ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
1316 CSInfo.markDevirt();
1317}
1318
1319bool DevirtModule::tryUniformRetValOpt(
1320 MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1321 WholeProgramDevirtResolution::ByArg *Res) {
1322 // Uniform return value optimization. If all functions return the same
1323 // constant, replace all calls with that constant.
1324 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1325 for (const VirtualCallTarget &Target : TargetsForSlot)
30
Assuming '__begin1' is equal to '__end1'
1326 if (Target.RetVal != TheRetVal)
1327 return false;
1328
1329 if (CSInfo.isExported()) {
31
Calling 'CallSiteInfo::isExported'
34
Returning from 'CallSiteInfo::isExported'
35
Taking true branch
1330 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
36
Access to field 'TheKind' results in a dereference of a null pointer (loaded from variable 'Res')
1331 Res->Info = TheRetVal;
1332 }
1333
1334 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1335 if (RemarksEnabled)
1336 for (auto &&Target : TargetsForSlot)
1337 Target.WasDevirt = true;
1338 return true;
1339}
1340
1341std::string DevirtModule::getGlobalName(VTableSlot Slot,
1342 ArrayRef<uint64_t> Args,
1343 StringRef Name) {
1344 std::string FullName = "__typeid_";
1345 raw_string_ostream OS(FullName);
1346 OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1347 for (uint64_t Arg : Args)
1348 OS << '_' << Arg;
1349 OS << '_' << Name;
1350 return OS.str();
1351}
1352
1353bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1354 Triple T(M.getTargetTriple());
1355 return T.isX86() && T.getObjectFormat() == Triple::ELF;
1356}
1357
1358void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1359 StringRef Name, Constant *C) {
1360 GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
1361 getGlobalName(Slot, Args, Name), C, &M);
1362 GA->setVisibility(GlobalValue::HiddenVisibility);
1363}
1364
1365void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1366 StringRef Name, uint32_t Const,
1367 uint32_t &Storage) {
1368 if (shouldExportConstantsAsAbsoluteSymbols()) {
1369 exportGlobal(
1370 Slot, Args, Name,
1371 ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1372 return;
1373 }
1374
1375 Storage = Const;
1376}
1377
1378Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1379 StringRef Name) {
1380 Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
1381 auto *GV = dyn_cast<GlobalVariable>(C);
1382 if (GV)
1383 GV->setVisibility(GlobalValue::HiddenVisibility);
1384 return C;
1385}
1386
1387Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1388 StringRef Name, IntegerType *IntTy,
1389 uint32_t Storage) {
1390 if (!shouldExportConstantsAsAbsoluteSymbols())
1391 return ConstantInt::get(IntTy, Storage);
1392
1393 Constant *C = importGlobal(Slot, Args, Name);
1394 auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1395 C = ConstantExpr::getPtrToInt(C, IntTy);
1396
1397 // We only need to set metadata if the global is newly created, in which
1398 // case it would not have hidden visibility.
1399 if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1400 return C;
1401
1402 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1403 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1404 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1405 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1406 MDNode::get(M.getContext(), {MinC, MaxC}));
1407 };
1408 unsigned AbsWidth = IntTy->getBitWidth();
1409 if (AbsWidth == IntPtrTy->getBitWidth())
1410 SetAbsRange(~0ull, ~0ull); // Full set.
1411 else
1412 SetAbsRange(0, 1ull << AbsWidth);
1413 return C;
1414}
1415
1416void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1417 bool IsOne,
1418 Constant *UniqueMemberAddr) {
1419 for (auto &&Call : CSInfo.CallSites) {
1420 IRBuilder<> B(Call.CS.getInstruction());
1421 Value *Cmp =
1422 B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
1423 B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
1424 Cmp = B.CreateZExt(Cmp, Call.CS->getType());
1425 Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1426 Cmp);
1427 }
1428 CSInfo.markDevirt();
1429}
1430
1431Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1432 Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1433 return ConstantExpr::getGetElementPtr(Int8Ty, C,
1434 ConstantInt::get(Int64Ty, M->Offset));
1435}
1436
1437bool DevirtModule::tryUniqueRetValOpt(
1438 unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1439 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1440 VTableSlot Slot, ArrayRef<uint64_t> Args) {
1441 // IsOne controls whether we look for a 0 or a 1.
1442 auto tryUniqueRetValOptFor = [&](bool IsOne) {
1443 const TypeMemberInfo *UniqueMember = nullptr;
1444 for (const VirtualCallTarget &Target : TargetsForSlot) {
1445 if (Target.RetVal == (IsOne ? 1 : 0)) {
1446 if (UniqueMember)
1447 return false;
1448 UniqueMember = Target.TM;
1449 }
1450 }
1451
1452 // We should have found a unique member or bailed out by now. We already
1453 // checked for a uniform return value in tryUniformRetValOpt.
1454 assert(UniqueMember)((UniqueMember) ? static_cast<void> (0) : __assert_fail
("UniqueMember", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1454, __PRETTY_FUNCTION__))
;
1455
1456 Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1457 if (CSInfo.isExported()) {
1458 Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
1459 Res->Info = IsOne;
1460
1461 exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1462 }
1463
1464 // Replace each call with the comparison.
1465 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1466 UniqueMemberAddr);
1467
1468 // Update devirtualization statistics for targets.
1469 if (RemarksEnabled)
1470 for (auto &&Target : TargetsForSlot)
1471 Target.WasDevirt = true;
1472
1473 return true;
1474 };
1475
1476 if (BitWidth == 1) {
1477 if (tryUniqueRetValOptFor(true))
1478 return true;
1479 if (tryUniqueRetValOptFor(false))
1480 return true;
1481 }
1482 return false;
1483}
1484
1485void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1486 Constant *Byte, Constant *Bit) {
1487 for (auto Call : CSInfo.CallSites) {
1488 auto *RetType = cast<IntegerType>(Call.CS.getType());
1489 IRBuilder<> B(Call.CS.getInstruction());
1490 Value *Addr =
1491 B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1492 if (RetType->getBitWidth() == 1) {
1493 Value *Bits = B.CreateLoad(Int8Ty, Addr);
1494 Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1495 auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1496 Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1497 OREGetter, IsBitSet);
1498 } else {
1499 Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1500 Value *Val = B.CreateLoad(RetType, ValAddr);
1501 Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1502 OREGetter, Val);
1503 }
1504 }
1505 CSInfo.markDevirt();
1506}
1507
1508bool DevirtModule::tryVirtualConstProp(
1509 MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1510 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1511 // This only works if the function returns an integer.
1512 auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
16
Assuming the object is a 'IntegerType'
1513 if (!RetType
16.1
'RetType' is non-null
)
17
Taking false branch
1514 return false;
1515 unsigned BitWidth = RetType->getBitWidth();
1516 if (BitWidth > 64)
18
Assuming 'BitWidth' is <= 64
19
Taking false branch
1517 return false;
1518
1519 // Make sure that each function is defined, does not access memory, takes at
1520 // least one argument, does not use its first argument (which we assume is
1521 // 'this'), and has the same return type.
1522 //
1523 // Note that we test whether this copy of the function is readnone, rather
1524 // than testing function attributes, which must hold for any copy of the
1525 // function, even a less optimized version substituted at link time. This is
1526 // sound because the virtual constant propagation optimizations effectively
1527 // inline all implementations of the virtual function into each call site,
1528 // rather than using function attributes to perform local optimization.
1529 for (VirtualCallTarget &Target : TargetsForSlot) {
20
Assuming '__begin1' is equal to '__end1'
1530 if (Target.Fn->isDeclaration() ||
1531 computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1532 MAK_ReadNone ||
1533 Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1534 Target.Fn->getReturnType() != RetType)
1535 return false;
1536 }
1537
1538 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1539 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
21
Calling 'DevirtModule::tryEvaluateFunctionsWithArgs'
24
Returning from 'DevirtModule::tryEvaluateFunctionsWithArgs'
25
Taking false branch
1540 continue;
1541
1542 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
26
'ResByArg' initialized to a null pointer value
1543 if (Res
26.1
'Res' is null
)
27
Taking false branch
1544 ResByArg = &Res->ResByArg[CSByConstantArg.first];
1545
1546 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
28
Passing null pointer value via 3rd parameter 'Res'
29
Calling 'DevirtModule::tryUniformRetValOpt'
1547 continue;
1548
1549 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1550 ResByArg, Slot, CSByConstantArg.first))
1551 continue;
1552
1553 // Find an allocation offset in bits in all vtables associated with the
1554 // type.
1555 uint64_t AllocBefore =
1556 findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1557 uint64_t AllocAfter =
1558 findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1559
1560 // Calculate the total amount of padding needed to store a value at both
1561 // ends of the object.
1562 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1563 for (auto &&Target : TargetsForSlot) {
1564 TotalPaddingBefore += std::max<int64_t>(
1565 (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1566 TotalPaddingAfter += std::max<int64_t>(
1567 (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1568 }
1569
1570 // If the amount of padding is too large, give up.
1571 // FIXME: do something smarter here.
1572 if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1573 continue;
1574
1575 // Calculate the offset to the value as a (possibly negative) byte offset
1576 // and (if applicable) a bit offset, and store the values in the targets.
1577 int64_t OffsetByte;
1578 uint64_t OffsetBit;
1579 if (TotalPaddingBefore <= TotalPaddingAfter)
1580 setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1581 OffsetBit);
1582 else
1583 setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1584 OffsetBit);
1585
1586 if (RemarksEnabled)
1587 for (auto &&Target : TargetsForSlot)
1588 Target.WasDevirt = true;
1589
1590
1591 if (CSByConstantArg.second.isExported()) {
1592 ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;
1593 exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1594 ResByArg->Byte);
1595 exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1596 ResByArg->Bit);
1597 }
1598
1599 // Rewrite each call to a load from OffsetByte/OffsetBit.
1600 Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1601 Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1602 applyVirtualConstProp(CSByConstantArg.second,
1603 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1604 }
1605 return true;
1606}
1607
1608void DevirtModule::rebuildGlobal(VTableBits &B) {
1609 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1610 return;
1611
1612 // Align the before byte array to the global's minimum alignment so that we
1613 // don't break any alignment requirements on the global.
1614 MaybeAlign Alignment(B.GV->getAlignment());
1615 if (!Alignment)
1616 Alignment =
1617 Align(M.getDataLayout().getABITypeAlignment(B.GV->getValueType()));
1618 B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment));
1619
1620 // Before was stored in reverse order; flip it now.
1621 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1622 std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1623
1624 // Build an anonymous global containing the before bytes, followed by the
1625 // original initializer, followed by the after bytes.
1626 auto NewInit = ConstantStruct::getAnon(
1627 {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1628 B.GV->getInitializer(),
1629 ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1630 auto NewGV =
1631 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1632 GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1633 NewGV->setSection(B.GV->getSection());
1634 NewGV->setComdat(B.GV->getComdat());
1635 NewGV->setAlignment(MaybeAlign(B.GV->getAlignment()));
1636
1637 // Copy the original vtable's metadata to the anonymous global, adjusting
1638 // offsets as required.
1639 NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1640
1641 // Build an alias named after the original global, pointing at the second
1642 // element (the original initializer).
1643 auto Alias = GlobalAlias::create(
1644 B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1645 ConstantExpr::getGetElementPtr(
1646 NewInit->getType(), NewGV,
1647 ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
1648 ConstantInt::get(Int32Ty, 1)}),
1649 &M);
1650 Alias->setVisibility(B.GV->getVisibility());
1651 Alias->takeName(B.GV);
1652
1653 B.GV->replaceAllUsesWith(Alias);
1654 B.GV->eraseFromParent();
1655}
1656
1657bool DevirtModule::areRemarksEnabled() {
1658 const auto &FL = M.getFunctionList();
1659 for (const Function &Fn : FL) {
1660 const auto &BBL = Fn.getBasicBlockList();
1661 if (BBL.empty())
1662 continue;
1663 auto DI = OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "", DebugLoc(), &BBL.front());
1664 return DI.isEnabled();
1665 }
1666 return false;
1667}
1668
1669void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc) {
1670 // Find all virtual calls via a virtual table pointer %p under an assumption
1671 // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1672 // points to a member of the type identifier %md. Group calls by (type ID,
1673 // offset) pair (effectively the identity of the virtual function) and store
1674 // to CallSlots.
1675 DenseSet<CallSite> SeenCallSites;
1676 for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1677 I != E;) {
1678 auto CI = dyn_cast<CallInst>(I->getUser());
1679 ++I;
1680 if (!CI)
1681 continue;
1682
1683 // Search for virtual calls based on %p and add them to DevirtCalls.
1684 SmallVector<DevirtCallSite, 1> DevirtCalls;
1685 SmallVector<CallInst *, 1> Assumes;
1686 auto &DT = LookupDomTree(*CI->getFunction());
1687 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1688
1689 // If we found any, add them to CallSlots.
1690 if (!Assumes.empty()) {
1691 Metadata *TypeId =
1692 cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1693 Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1694 for (DevirtCallSite Call : DevirtCalls) {
1695 // Only add this CallSite if we haven't seen it before. The vtable
1696 // pointer may have been CSE'd with pointers from other call sites,
1697 // and we don't want to process call sites multiple times. We can't
1698 // just skip the vtable Ptr if it has been seen before, however, since
1699 // it may be shared by type tests that dominate different calls.
1700 if (SeenCallSites.insert(Call.CS).second)
1701 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1702 }
1703 }
1704
1705 // We no longer need the assumes or the type test.
1706 for (auto Assume : Assumes)
1707 Assume->eraseFromParent();
1708 // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1709 // may use the vtable argument later.
1710 if (CI->use_empty())
1711 CI->eraseFromParent();
1712 }
1713}
1714
1715void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1716 Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1717
1718 for (auto I = TypeCheckedLoadFunc->use_begin(),
1719 E = TypeCheckedLoadFunc->use_end();
1720 I != E;) {
1721 auto CI = dyn_cast<CallInst>(I->getUser());
1722 ++I;
1723 if (!CI)
1724 continue;
1725
1726 Value *Ptr = CI->getArgOperand(0);
1727 Value *Offset = CI->getArgOperand(1);
1728 Value *TypeIdValue = CI->getArgOperand(2);
1729 Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1730
1731 SmallVector<DevirtCallSite, 1> DevirtCalls;
1732 SmallVector<Instruction *, 1> LoadedPtrs;
1733 SmallVector<Instruction *, 1> Preds;
1734 bool HasNonCallUses = false;
1735 auto &DT = LookupDomTree(*CI->getFunction());
1736 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1737 HasNonCallUses, CI, DT);
1738
1739 // Start by generating "pessimistic" code that explicitly loads the function
1740 // pointer from the vtable and performs the type check. If possible, we will
1741 // eliminate the load and the type check later.
1742
1743 // If possible, only generate the load at the point where it is used.
1744 // This helps avoid unnecessary spills.
1745 IRBuilder<> LoadB(
1746 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1747 Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1748 Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1749 Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1750
1751 for (Instruction *LoadedPtr : LoadedPtrs) {
1752 LoadedPtr->replaceAllUsesWith(LoadedValue);
1753 LoadedPtr->eraseFromParent();
1754 }
1755
1756 // Likewise for the type test.
1757 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1758 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1759
1760 for (Instruction *Pred : Preds) {
1761 Pred->replaceAllUsesWith(TypeTestCall);
1762 Pred->eraseFromParent();
1763 }
1764
1765 // We have already erased any extractvalue instructions that refer to the
1766 // intrinsic call, but the intrinsic may have other non-extractvalue uses
1767 // (although this is unlikely). In that case, explicitly build a pair and
1768 // RAUW it.
1769 if (!CI->use_empty()) {
1770 Value *Pair = UndefValue::get(CI->getType());
1771 IRBuilder<> B(CI);
1772 Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1773 Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1774 CI->replaceAllUsesWith(Pair);
1775 }
1776
1777 // The number of unsafe uses is initially the number of uses.
1778 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1779 NumUnsafeUses = DevirtCalls.size();
1780
1781 // If the function pointer has a non-call user, we cannot eliminate the type
1782 // check, as one of those users may eventually call the pointer. Increment
1783 // the unsafe use count to make sure it cannot reach zero.
1784 if (HasNonCallUses)
1785 ++NumUnsafeUses;
1786 for (DevirtCallSite Call : DevirtCalls) {
1787 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1788 &NumUnsafeUses);
1789 }
1790
1791 CI->eraseFromParent();
1792 }
1793}
1794
1795void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1796 auto *TypeId = dyn_cast<MDString>(Slot.TypeID);
1797 if (!TypeId)
1798 return;
1799 const TypeIdSummary *TidSummary =
1800 ImportSummary->getTypeIdSummary(TypeId->getString());
1801 if (!TidSummary)
1802 return;
1803 auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1804 if (ResI == TidSummary->WPDRes.end())
1805 return;
1806 const WholeProgramDevirtResolution &Res = ResI->second;
1807
1808 if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
1809 assert(!Res.SingleImplName.empty())((!Res.SingleImplName.empty()) ? static_cast<void> (0) :
__assert_fail ("!Res.SingleImplName.empty()", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1809, __PRETTY_FUNCTION__))
;
1810 // The type of the function in the declaration is irrelevant because every
1811 // call site will cast it to the correct type.
1812 Constant *SingleImpl =
1813 cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,
1814 Type::getVoidTy(M.getContext()))
1815 .getCallee());
1816
1817 // This is the import phase so we should not be exporting anything.
1818 bool IsExported = false;
1819 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1820 assert(!IsExported)((!IsExported) ? static_cast<void> (0) : __assert_fail (
"!IsExported", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1820, __PRETTY_FUNCTION__))
;
1821 }
1822
1823 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1824 auto I = Res.ResByArg.find(CSByConstantArg.first);
1825 if (I == Res.ResByArg.end())
1826 continue;
1827 auto &ResByArg = I->second;
1828 // FIXME: We should figure out what to do about the "function name" argument
1829 // to the apply* functions, as the function names are unavailable during the
1830 // importing phase. For now we just pass the empty string. This does not
1831 // impact correctness because the function names are just used for remarks.
1832 switch (ResByArg.TheKind) {
1833 case WholeProgramDevirtResolution::ByArg::UniformRetVal:
1834 applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1835 break;
1836 case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
1837 Constant *UniqueMemberAddr =
1838 importGlobal(Slot, CSByConstantArg.first, "unique_member");
1839 applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1840 UniqueMemberAddr);
1841 break;
1842 }
1843 case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
1844 Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1845 Int32Ty, ResByArg.Byte);
1846 Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1847 ResByArg.Bit);
1848 applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1849 break;
1850 }
1851 default:
1852 break;
1853 }
1854 }
1855
1856 if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) {
1857 // The type of the function is irrelevant, because it's bitcast at calls
1858 // anyhow.
1859 Constant *JT = cast<Constant>(
1860 M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
1861 Type::getVoidTy(M.getContext()))
1862 .getCallee());
1863 bool IsExported = false;
1864 applyICallBranchFunnel(SlotInfo, JT, IsExported);
1865 assert(!IsExported)((!IsExported) ? static_cast<void> (0) : __assert_fail (
"!IsExported", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 1865, __PRETTY_FUNCTION__))
;
1866 }
1867}
1868
1869void DevirtModule::removeRedundantTypeTests() {
1870 auto True = ConstantInt::getTrue(M.getContext());
1871 for (auto &&U : NumUnsafeUsesForTypeTest) {
1872 if (U.second == 0) {
1873 U.first->replaceAllUsesWith(True);
1874 U.first->eraseFromParent();
1875 }
1876 }
1877}
1878
1879bool DevirtModule::run() {
1880 // If only some of the modules were split, we cannot correctly perform
1881 // this transformation. We already checked for the presense of type tests
1882 // with partially split modules during the thin link, and would have emitted
1883 // an error if any were found, so here we can simply return.
1884 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1
Assuming field 'ExportSummary' is null
1885 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
2
Assuming field 'ImportSummary' is null
1886 return false;
1887
1888 Function *TypeTestFunc =
1889 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1890 Function *TypeCheckedLoadFunc =
1891 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1892 Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1893
1894 // Normally if there are no users of the devirtualization intrinsics in the
1895 // module, this pass has nothing to do. But if we are exporting, we also need
1896 // to handle any users that appear only in the function summaries.
1897 if (!ExportSummary
2.1
Field 'ExportSummary' is null
&&
1898 (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
3
Assuming 'TypeTestFunc' is non-null
4
Assuming 'AssumeFunc' is non-null
1899 AssumeFunc->use_empty()) &&
1900 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1901 return false;
1902
1903 if (TypeTestFunc
4.1
'TypeTestFunc' is non-null
&& AssumeFunc
4.2
'AssumeFunc' is non-null
)
5
Taking true branch
1904 scanTypeTestUsers(TypeTestFunc);
1905
1906 if (TypeCheckedLoadFunc)
6
Assuming 'TypeCheckedLoadFunc' is null
7
Taking false branch
1907 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1908
1909 if (ImportSummary
7.1
Field 'ImportSummary' is null
) {
8
Taking false branch
1910 for (auto &S : CallSlots)
1911 importResolution(S.first, S.second);
1912
1913 removeRedundantTypeTests();
1914
1915 // We have lowered or deleted the type instrinsics, so we will no
1916 // longer have enough information to reason about the liveness of virtual
1917 // function pointers in GlobalDCE.
1918 for (GlobalVariable &GV : M.globals())
1919 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1920
1921 // The rest of the code is only necessary when exporting or during regular
1922 // LTO, so we are done.
1923 return true;
1924 }
1925
1926 // Rebuild type metadata into a map for easy lookup.
1927 std::vector<VTableBits> Bits;
1928 DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
1929 buildTypeIdentifierMap(Bits, TypeIdMap);
1930 if (TypeIdMap.empty())
9
Assuming the condition is false
10
Taking false branch
1931 return true;
1932
1933 // Collect information from summary about which calls to try to devirtualize.
1934 if (ExportSummary
10.1
Field 'ExportSummary' is null
) {
11
Taking false branch
1935 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
1936 for (auto &P : TypeIdMap) {
1937 if (auto *TypeId = dyn_cast<MDString>(P.first))
1938 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1939 TypeId);
1940 }
1941
1942 for (auto &P : *ExportSummary) {
1943 for (auto &S : P.second.SummaryList) {
1944 auto *FS = dyn_cast<FunctionSummary>(S.get());
1945 if (!FS)
1946 continue;
1947 // FIXME: Only add live functions.
1948 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1949 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1950 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
1951 }
1952 }
1953 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1954 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1955 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1956 }
1957 }
1958 for (const FunctionSummary::ConstVCall &VC :
1959 FS->type_test_assume_const_vcalls()) {
1960 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1961 CallSlots[{MD, VC.VFunc.Offset}]
1962 .ConstCSInfo[VC.Args]
1963 .addSummaryTypeTestAssumeUser(FS);
1964 }
1965 }
1966 for (const FunctionSummary::ConstVCall &VC :
1967 FS->type_checked_load_const_vcalls()) {
1968 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1969 CallSlots[{MD, VC.VFunc.Offset}]
1970 .ConstCSInfo[VC.Args]
1971 .addSummaryTypeCheckedLoadUser(FS);
1972 }
1973 }
1974 }
1975 }
1976 }
1977
1978 // For each (type, offset) pair:
1979 bool DidVirtualConstProp = false;
1980 std::map<std::string, Function*> DevirtTargets;
1981 for (auto &S : CallSlots) {
1982 // Search each of the members of the type identifier for the virtual
1983 // function implementation at offset S.first.ByteOffset, and add to
1984 // TargetsForSlot.
1985 std::vector<VirtualCallTarget> TargetsForSlot;
1986 if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
12
Taking true branch
1987 S.first.ByteOffset)) {
1988 WholeProgramDevirtResolution *Res = nullptr;
1989 if (ExportSummary && isa<MDString>(S.first.TypeID))
13
Assuming field 'ExportSummary' is null
1990 Res = &ExportSummary
1991 ->getOrInsertTypeIdSummary(
1992 cast<MDString>(S.first.TypeID)->getString())
1993 .WPDRes[S.first.ByteOffset];
1994
1995 if (!trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res)) {
14
Taking true branch
1996 DidVirtualConstProp |=
1997 tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
15
Calling 'DevirtModule::tryVirtualConstProp'
1998
1999 tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
2000 }
2001
2002 // Collect functions devirtualized at least for one call site for stats.
2003 if (RemarksEnabled)
2004 for (const auto &T : TargetsForSlot)
2005 if (T.WasDevirt)
2006 DevirtTargets[std::string(T.Fn->getName())] = T.Fn;
2007 }
2008
2009 // CFI-specific: if we are exporting and any llvm.type.checked.load
2010 // intrinsics were *not* devirtualized, we need to add the resulting
2011 // llvm.type.test intrinsics to the function summaries so that the
2012 // LowerTypeTests pass will export them.
2013 if (ExportSummary && isa<MDString>(S.first.TypeID)) {
2014 auto GUID =
2015 GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
2016 for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
2017 FS->addTypeTest(GUID);
2018 for (auto &CCS : S.second.ConstCSInfo)
2019 for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
2020 FS->addTypeTest(GUID);
2021 }
2022 }
2023
2024 if (RemarksEnabled) {
2025 // Generate remarks for each devirtualized function.
2026 for (const auto &DT : DevirtTargets) {
2027 Function *F = DT.second;
2028
2029 using namespace ore;
2030 OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE"wholeprogramdevirt", "Devirtualized", F)
2031 << "devirtualized "
2032 << NV("FunctionName", DT.first));
2033 }
2034 }
2035
2036 removeRedundantTypeTests();
2037
2038 // Rebuild each global we touched as part of virtual constant propagation to
2039 // include the before and after bytes.
2040 if (DidVirtualConstProp)
2041 for (VTableBits &B : Bits)
2042 rebuildGlobal(B);
2043
2044 // We have lowered or deleted the type instrinsics, so we will no
2045 // longer have enough information to reason about the liveness of virtual
2046 // function pointers in GlobalDCE.
2047 for (GlobalVariable &GV : M.globals())
2048 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2049
2050 return true;
2051}
2052
2053void DevirtIndex::run() {
2054 if (ExportSummary.typeIdCompatibleVtableMap().empty())
2055 return;
2056
2057 DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
2058 for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
2059 NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
2060 }
2061
2062 // Collect information from summary about which calls to try to devirtualize.
2063 for (auto &P : ExportSummary) {
2064 for (auto &S : P.second.SummaryList) {
2065 auto *FS = dyn_cast<FunctionSummary>(S.get());
2066 if (!FS)
2067 continue;
2068 // FIXME: Only add live functions.
2069 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2070 for (StringRef Name : NameByGUID[VF.GUID]) {
2071 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2072 }
2073 }
2074 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2075 for (StringRef Name : NameByGUID[VF.GUID]) {
2076 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2077 }
2078 }
2079 for (const FunctionSummary::ConstVCall &VC :
2080 FS->type_test_assume_const_vcalls()) {
2081 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2082 CallSlots[{Name, VC.VFunc.Offset}]
2083 .ConstCSInfo[VC.Args]
2084 .addSummaryTypeTestAssumeUser(FS);
2085 }
2086 }
2087 for (const FunctionSummary::ConstVCall &VC :
2088 FS->type_checked_load_const_vcalls()) {
2089 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2090 CallSlots[{Name, VC.VFunc.Offset}]
2091 .ConstCSInfo[VC.Args]
2092 .addSummaryTypeCheckedLoadUser(FS);
2093 }
2094 }
2095 }
2096 }
2097
2098 std::set<ValueInfo> DevirtTargets;
2099 // For each (type, offset) pair:
2100 for (auto &S : CallSlots) {
2101 // Search each of the members of the type identifier for the virtual
2102 // function implementation at offset S.first.ByteOffset, and add to
2103 // TargetsForSlot.
2104 std::vector<ValueInfo> TargetsForSlot;
2105 auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
2106 assert(TidSummary)((TidSummary) ? static_cast<void> (0) : __assert_fail (
"TidSummary", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp"
, 2106, __PRETTY_FUNCTION__))
;
2107 if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
2108 S.first.ByteOffset)) {
2109 WholeProgramDevirtResolution *Res =
2110 &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
2111 .WPDRes[S.first.ByteOffset];
2112
2113 if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
2114 DevirtTargets))
2115 continue;
2116 }
2117 }
2118
2119 // Optionally have the thin link print message for each devirtualized
2120 // function.
2121 if (PrintSummaryDevirt)
2122 for (const auto &DT : DevirtTargets)
2123 errs() << "Devirtualized call to " << DT << "\n";
2124
2125 return;
2126}