Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
Warning:line 1373, column 18
Access to field 'TheKind' results in a dereference of a null pointer (loaded from variable 'Res')

Annotated Source Code

Press '?' to see keyboard shortcuts

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