Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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