Bug Summary

File:llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
Warning:line 1025, column 10
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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