Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name WholeProgramDevirt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -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~svn374877/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/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~svn374877/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -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-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/lib/Transforms/IPO/WholeProgramDevirt.cpp

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

/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h

1//===- llvm/Value.h - Definition of the Value class -------------*- C++ -*-===//
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 file declares the Value class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_IR_VALUE_H
14#define LLVM_IR_VALUE_H
15
16#include "llvm-c/Types.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/IR/Use.h"
20#include "llvm/Support/CBindingWrapping.h"
21#include "llvm/Support/Casting.h"
22#include <cassert>
23#include <iterator>
24#include <memory>
25
26namespace llvm {
27
28class APInt;
29class Argument;
30class BasicBlock;
31class Constant;
32class ConstantData;
33class ConstantAggregate;
34class DataLayout;
35class Function;
36class GlobalAlias;
37class GlobalIFunc;
38class GlobalIndirectSymbol;
39class GlobalObject;
40class GlobalValue;
41class GlobalVariable;
42class InlineAsm;
43class Instruction;
44class LLVMContext;
45class Module;
46class ModuleSlotTracker;
47class raw_ostream;
48template<typename ValueTy> class StringMapEntry;
49class StringRef;
50class Twine;
51class Type;
52class User;
53
54using ValueName = StringMapEntry<Value *>;
55
56//===----------------------------------------------------------------------===//
57// Value Class
58//===----------------------------------------------------------------------===//
59
60/// LLVM Value Representation
61///
62/// This is a very important LLVM class. It is the base class of all values
63/// computed by a program that may be used as operands to other values. Value is
64/// the super class of other important classes such as Instruction and Function.
65/// All Values have a Type. Type is not a subclass of Value. Some values can
66/// have a name and they belong to some Module. Setting the name on the Value
67/// automatically updates the module's symbol table.
68///
69/// Every value has a "use list" that keeps track of which other Values are
70/// using this Value. A Value can also have an arbitrary number of ValueHandle
71/// objects that watch it and listen to RAUW and Destroy events. See
72/// llvm/IR/ValueHandle.h for details.
73class Value {
74 // The least-significant bit of the first word of Value *must* be zero:
75 // http://www.llvm.org/docs/ProgrammersManual.html#the-waymarking-algorithm
76 Type *VTy;
77 Use *UseList;
78
79 friend class ValueAsMetadata; // Allow access to IsUsedByMD.
80 friend class ValueHandleBase;
81
82 const unsigned char SubclassID; // Subclass identifier (for isa/dyn_cast)
83 unsigned char HasValueHandle : 1; // Has a ValueHandle pointing to this?
84
85protected:
86 /// Hold subclass data that can be dropped.
87 ///
88 /// This member is similar to SubclassData, however it is for holding
89 /// information which may be used to aid optimization, but which may be
90 /// cleared to zero without affecting conservative interpretation.
91 unsigned char SubclassOptionalData : 7;
92
93private:
94 /// Hold arbitrary subclass data.
95 ///
96 /// This member is defined by this class, but is not used for anything.
97 /// Subclasses can use it to hold whatever state they find useful. This
98 /// field is initialized to zero by the ctor.
99 unsigned short SubclassData;
100
101protected:
102 /// The number of operands in the subclass.
103 ///
104 /// This member is defined by this class, but not used for anything.
105 /// Subclasses can use it to store their number of operands, if they have
106 /// any.
107 ///
108 /// This is stored here to save space in User on 64-bit hosts. Since most
109 /// instances of Value have operands, 32-bit hosts aren't significantly
110 /// affected.
111 ///
112 /// Note, this should *NOT* be used directly by any class other than User.
113 /// User uses this value to find the Use list.
114 enum : unsigned { NumUserOperandsBits = 28 };
115 unsigned NumUserOperands : NumUserOperandsBits;
116
117 // Use the same type as the bitfield above so that MSVC will pack them.
118 unsigned IsUsedByMD : 1;
119 unsigned HasName : 1;
120 unsigned HasHungOffUses : 1;
121 unsigned HasDescriptor : 1;
122
123private:
124 template <typename UseT> // UseT == 'Use' or 'const Use'
125 class use_iterator_impl
126 : public std::iterator<std::forward_iterator_tag, UseT *> {
127 friend class Value;
128
129 UseT *U;
130
131 explicit use_iterator_impl(UseT *u) : U(u) {}
132
133 public:
134 use_iterator_impl() : U() {}
135
136 bool operator==(const use_iterator_impl &x) const { return U == x.U; }
137 bool operator!=(const use_iterator_impl &x) const { return !operator==(x); }
138
139 use_iterator_impl &operator++() { // Preincrement
140 assert(U && "Cannot increment end iterator!")((U && "Cannot increment end iterator!") ? static_cast
<void> (0) : __assert_fail ("U && \"Cannot increment end iterator!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 140, __PRETTY_FUNCTION__))
;
141 U = U->getNext();
142 return *this;
143 }
144
145 use_iterator_impl operator++(int) { // Postincrement
146 auto tmp = *this;
147 ++*this;
148 return tmp;
149 }
150
151 UseT &operator*() const {
152 assert(U && "Cannot dereference end iterator!")((U && "Cannot dereference end iterator!") ? static_cast
<void> (0) : __assert_fail ("U && \"Cannot dereference end iterator!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 152, __PRETTY_FUNCTION__))
;
153 return *U;
154 }
155
156 UseT *operator->() const { return &operator*(); }
157
158 operator use_iterator_impl<const UseT>() const {
159 return use_iterator_impl<const UseT>(U);
160 }
161 };
162
163 template <typename UserTy> // UserTy == 'User' or 'const User'
164 class user_iterator_impl
165 : public std::iterator<std::forward_iterator_tag, UserTy *> {
166 use_iterator_impl<Use> UI;
167 explicit user_iterator_impl(Use *U) : UI(U) {}
168 friend class Value;
169
170 public:
171 user_iterator_impl() = default;
172
173 bool operator==(const user_iterator_impl &x) const { return UI == x.UI; }
174 bool operator!=(const user_iterator_impl &x) const { return !operator==(x); }
175
176 /// Returns true if this iterator is equal to user_end() on the value.
177 bool atEnd() const { return *this == user_iterator_impl(); }
178
179 user_iterator_impl &operator++() { // Preincrement
180 ++UI;
181 return *this;
182 }
183
184 user_iterator_impl operator++(int) { // Postincrement
185 auto tmp = *this;
186 ++*this;
187 return tmp;
188 }
189
190 // Retrieve a pointer to the current User.
191 UserTy *operator*() const {
192 return UI->getUser();
193 }
194
195 UserTy *operator->() const { return operator*(); }
196
197 operator user_iterator_impl<const UserTy>() const {
198 return user_iterator_impl<const UserTy>(*UI);
199 }
200
201 Use &getUse() const { return *UI; }
202 };
203
204protected:
205 Value(Type *Ty, unsigned scid);
206
207 /// Value's destructor should be virtual by design, but that would require
208 /// that Value and all of its subclasses have a vtable that effectively
209 /// duplicates the information in the value ID. As a size optimization, the
210 /// destructor has been protected, and the caller should manually call
211 /// deleteValue.
212 ~Value(); // Use deleteValue() to delete a generic Value.
213
214public:
215 Value(const Value &) = delete;
216 Value &operator=(const Value &) = delete;
217
218 /// Delete a pointer to a generic Value.
219 void deleteValue();
220
221 /// Support for debugging, callable in GDB: V->dump()
222 void dump() const;
223
224 /// Implement operator<< on Value.
225 /// @{
226 void print(raw_ostream &O, bool IsForDebug = false) const;
227 void print(raw_ostream &O, ModuleSlotTracker &MST,
228 bool IsForDebug = false) const;
229 /// @}
230
231 /// Print the name of this Value out to the specified raw_ostream.
232 ///
233 /// This is useful when you just want to print 'int %reg126', not the
234 /// instruction that generated it. If you specify a Module for context, then
235 /// even constanst get pretty-printed; for example, the type of a null
236 /// pointer is printed symbolically.
237 /// @{
238 void printAsOperand(raw_ostream &O, bool PrintType = true,
239 const Module *M = nullptr) const;
240 void printAsOperand(raw_ostream &O, bool PrintType,
241 ModuleSlotTracker &MST) const;
242 /// @}
243
244 /// All values are typed, get the type of this value.
245 Type *getType() const { return VTy; }
246
247 /// All values hold a context through their type.
248 LLVMContext &getContext() const;
249
250 // All values can potentially be named.
251 bool hasName() const { return HasName; }
252 ValueName *getValueName() const;
253 void setValueName(ValueName *VN);
254
255private:
256 void destroyValueName();
257 enum class ReplaceMetadataUses { No, Yes };
258 void doRAUW(Value *New, ReplaceMetadataUses);
259 void setNameImpl(const Twine &Name);
260
261public:
262 /// Return a constant reference to the value's name.
263 ///
264 /// This guaranteed to return the same reference as long as the value is not
265 /// modified. If the value has a name, this does a hashtable lookup, so it's
266 /// not free.
267 StringRef getName() const;
268
269 /// Change the name of the value.
270 ///
271 /// Choose a new unique name if the provided name is taken.
272 ///
273 /// \param Name The new name; or "" if the value's name should be removed.
274 void setName(const Twine &Name);
275
276 /// Transfer the name from V to this value.
277 ///
278 /// After taking V's name, sets V's name to empty.
279 ///
280 /// \note It is an error to call V->takeName(V).
281 void takeName(Value *V);
282
283 /// Change all uses of this to point to a new Value.
284 ///
285 /// Go through the uses list for this definition and make each use point to
286 /// "V" instead of "this". After this completes, 'this's use list is
287 /// guaranteed to be empty.
288 void replaceAllUsesWith(Value *V);
289
290 /// Change non-metadata uses of this to point to a new Value.
291 ///
292 /// Go through the uses list for this definition and make each use point to
293 /// "V" instead of "this". This function skips metadata entries in the list.
294 void replaceNonMetadataUsesWith(Value *V);
295
296 /// Go through the uses list for this definition and make each use point
297 /// to "V" if the callback ShouldReplace returns true for the given Use.
298 /// Unlike replaceAllUsesWith() this function does not support basic block
299 /// values or constant users.
300 void replaceUsesWithIf(Value *New,
301 llvm::function_ref<bool(Use &U)> ShouldReplace) {
302 assert(New && "Value::replaceUsesWithIf(<null>) is invalid!")((New && "Value::replaceUsesWithIf(<null>) is invalid!"
) ? static_cast<void> (0) : __assert_fail ("New && \"Value::replaceUsesWithIf(<null>) is invalid!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 302, __PRETTY_FUNCTION__))
;
303 assert(New->getType() == getType() &&((New->getType() == getType() && "replaceUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 304, __PRETTY_FUNCTION__))
304 "replaceUses of value with new value of different type!")((New->getType() == getType() && "replaceUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 304, __PRETTY_FUNCTION__))
;
305
306 for (use_iterator UI = use_begin(), E = use_end(); UI != E;) {
307 Use &U = *UI;
308 ++UI;
309 if (!ShouldReplace(U))
310 continue;
311 U.set(New);
312 }
313 }
314
315 /// replaceUsesOutsideBlock - Go through the uses list for this definition and
316 /// make each use point to "V" instead of "this" when the use is outside the
317 /// block. 'This's use list is expected to have at least one element.
318 /// Unlike replaceAllUsesWith() this function does not support basic block
319 /// values or constant users.
320 void replaceUsesOutsideBlock(Value *V, BasicBlock *BB);
321
322 //----------------------------------------------------------------------
323 // Methods for handling the chain of uses of this Value.
324 //
325 // Materializing a function can introduce new uses, so these methods come in
326 // two variants:
327 // The methods that start with materialized_ check the uses that are
328 // currently known given which functions are materialized. Be very careful
329 // when using them since you might not get all uses.
330 // The methods that don't start with materialized_ assert that modules is
331 // fully materialized.
332 void assertModuleIsMaterializedImpl() const;
333 // This indirection exists so we can keep assertModuleIsMaterializedImpl()
334 // around in release builds of Value.cpp to be linked with other code built
335 // in debug mode. But this avoids calling it in any of the release built code.
336 void assertModuleIsMaterialized() const {
337#ifndef NDEBUG
338 assertModuleIsMaterializedImpl();
339#endif
340 }
341
342 bool use_empty() const {
343 assertModuleIsMaterialized();
344 return UseList == nullptr;
5
Assuming the condition is false
6
Returning zero, which participates in a condition later
10
Assuming the condition is false
11
Returning zero, which participates in a condition later
345 }
346
347 bool materialized_use_empty() const {
348 return UseList == nullptr;
349 }
350
351 using use_iterator = use_iterator_impl<Use>;
352 using const_use_iterator = use_iterator_impl<const Use>;
353
354 use_iterator materialized_use_begin() { return use_iterator(UseList); }
355 const_use_iterator materialized_use_begin() const {
356 return const_use_iterator(UseList);
357 }
358 use_iterator use_begin() {
359 assertModuleIsMaterialized();
360 return materialized_use_begin();
361 }
362 const_use_iterator use_begin() const {
363 assertModuleIsMaterialized();
364 return materialized_use_begin();
365 }
366 use_iterator use_end() { return use_iterator(); }
367 const_use_iterator use_end() const { return const_use_iterator(); }
368 iterator_range<use_iterator> materialized_uses() {
369 return make_range(materialized_use_begin(), use_end());
370 }
371 iterator_range<const_use_iterator> materialized_uses() const {
372 return make_range(materialized_use_begin(), use_end());
373 }
374 iterator_range<use_iterator> uses() {
375 assertModuleIsMaterialized();
376 return materialized_uses();
377 }
378 iterator_range<const_use_iterator> uses() const {
379 assertModuleIsMaterialized();
380 return materialized_uses();
381 }
382
383 bool user_empty() const {
384 assertModuleIsMaterialized();
385 return UseList == nullptr;
386 }
387
388 using user_iterator = user_iterator_impl<User>;
389 using const_user_iterator = user_iterator_impl<const User>;
390
391 user_iterator materialized_user_begin() { return user_iterator(UseList); }
392 const_user_iterator materialized_user_begin() const {
393 return const_user_iterator(UseList);
394 }
395 user_iterator user_begin() {
396 assertModuleIsMaterialized();
397 return materialized_user_begin();
398 }
399 const_user_iterator user_begin() const {
400 assertModuleIsMaterialized();
401 return materialized_user_begin();
402 }
403 user_iterator user_end() { return user_iterator(); }
404 const_user_iterator user_end() const { return const_user_iterator(); }
405 User *user_back() {
406 assertModuleIsMaterialized();
407 return *materialized_user_begin();
408 }
409 const User *user_back() const {
410 assertModuleIsMaterialized();
411 return *materialized_user_begin();
412 }
413 iterator_range<user_iterator> materialized_users() {
414 return make_range(materialized_user_begin(), user_end());
415 }
416 iterator_range<const_user_iterator> materialized_users() const {
417 return make_range(materialized_user_begin(), user_end());
418 }
419 iterator_range<user_iterator> users() {
420 assertModuleIsMaterialized();
421 return materialized_users();
422 }
423 iterator_range<const_user_iterator> users() const {
424 assertModuleIsMaterialized();
425 return materialized_users();
426 }
427
428 /// Return true if there is exactly one user of this value.
429 ///
430 /// This is specialized because it is a common request and does not require
431 /// traversing the whole use list.
432 bool hasOneUse() const {
433 const_use_iterator I = use_begin(), E = use_end();
434 if (I == E) return false;
435 return ++I == E;
436 }
437
438 /// Return true if this Value has exactly N users.
439 bool hasNUses(unsigned N) const;
440
441 /// Return true if this value has N users or more.
442 ///
443 /// This is logically equivalent to getNumUses() >= N.
444 bool hasNUsesOrMore(unsigned N) const;
445
446 /// Check if this value is used in the specified basic block.
447 bool isUsedInBasicBlock(const BasicBlock *BB) const;
448
449 /// This method computes the number of uses of this Value.
450 ///
451 /// This is a linear time operation. Use hasOneUse, hasNUses, or
452 /// hasNUsesOrMore to check for specific values.
453 unsigned getNumUses() const;
454
455 /// This method should only be used by the Use class.
456 void addUse(Use &U) { U.addToList(&UseList); }
457
458 /// Concrete subclass of this.
459 ///
460 /// An enumeration for keeping track of the concrete subclass of Value that
461 /// is actually instantiated. Values of this enumeration are kept in the
462 /// Value classes SubclassID field. They are used for concrete type
463 /// identification.
464 enum ValueTy {
465#define HANDLE_VALUE(Name) Name##Val,
466#include "llvm/IR/Value.def"
467
468 // Markers:
469#define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val,
470#include "llvm/IR/Value.def"
471 };
472
473 /// Return an ID for the concrete type of this object.
474 ///
475 /// This is used to implement the classof checks. This should not be used
476 /// for any other purpose, as the values may change as LLVM evolves. Also,
477 /// note that for instructions, the Instruction's opcode is added to
478 /// InstructionVal. So this means three things:
479 /// # there is no value with code InstructionVal (no opcode==0).
480 /// # there are more possible values for the value type than in ValueTy enum.
481 /// # the InstructionVal enumerator must be the highest valued enumerator in
482 /// the ValueTy enum.
483 unsigned getValueID() const {
484 return SubclassID;
485 }
486
487 /// Return the raw optional flags value contained in this value.
488 ///
489 /// This should only be used when testing two Values for equivalence.
490 unsigned getRawSubclassOptionalData() const {
491 return SubclassOptionalData;
492 }
493
494 /// Clear the optional flags contained in this value.
495 void clearSubclassOptionalData() {
496 SubclassOptionalData = 0;
497 }
498
499 /// Check the optional flags for equality.
500 bool hasSameSubclassOptionalData(const Value *V) const {
501 return SubclassOptionalData == V->SubclassOptionalData;
502 }
503
504 /// Return true if there is a value handle associated with this value.
505 bool hasValueHandle() const { return HasValueHandle; }
506
507 /// Return true if there is metadata referencing this value.
508 bool isUsedByMetadata() const { return IsUsedByMD; }
509
510 /// Return true if this value is a swifterror value.
511 ///
512 /// swifterror values can be either a function argument or an alloca with a
513 /// swifterror attribute.
514 bool isSwiftError() const;
515
516 /// Strip off pointer casts, all-zero GEPs and address space casts.
517 ///
518 /// Returns the original uncasted value. If this is called on a non-pointer
519 /// value, it returns 'this'.
520 const Value *stripPointerCasts() const;
521 Value *stripPointerCasts() {
522 return const_cast<Value *>(
523 static_cast<const Value *>(this)->stripPointerCasts());
524 }
525
526 /// Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
527 ///
528 /// Returns the original uncasted value. If this is called on a non-pointer
529 /// value, it returns 'this'.
530 const Value *stripPointerCastsAndAliases() const;
531 Value *stripPointerCastsAndAliases() {
532 return const_cast<Value *>(
533 static_cast<const Value *>(this)->stripPointerCastsAndAliases());
534 }
535
536 /// Strip off pointer casts, all-zero GEPs and address space casts
537 /// but ensures the representation of the result stays the same.
538 ///
539 /// Returns the original uncasted value with the same representation. If this
540 /// is called on a non-pointer value, it returns 'this'.
541 const Value *stripPointerCastsSameRepresentation() const;
542 Value *stripPointerCastsSameRepresentation() {
543 return const_cast<Value *>(static_cast<const Value *>(this)
544 ->stripPointerCastsSameRepresentation());
545 }
546
547 /// Strip off pointer casts, all-zero GEPs and invariant group info.
548 ///
549 /// Returns the original uncasted value. If this is called on a non-pointer
550 /// value, it returns 'this'. This function should be used only in
551 /// Alias analysis.
552 const Value *stripPointerCastsAndInvariantGroups() const;
553 Value *stripPointerCastsAndInvariantGroups() {
554 return const_cast<Value *>(static_cast<const Value *>(this)
555 ->stripPointerCastsAndInvariantGroups());
556 }
557
558 /// Strip off pointer casts and all-constant inbounds GEPs.
559 ///
560 /// Returns the original pointer value. If this is called on a non-pointer
561 /// value, it returns 'this'.
562 const Value *stripInBoundsConstantOffsets() const;
563 Value *stripInBoundsConstantOffsets() {
564 return const_cast<Value *>(
565 static_cast<const Value *>(this)->stripInBoundsConstantOffsets());
566 }
567
568 /// Accumulate the constant offset this value has compared to a base pointer.
569 /// Only 'getelementptr' instructions (GEPs) with constant indices are
570 /// accumulated but other instructions, e.g., casts, are stripped away as
571 /// well. The accumulated constant offset is added to \p Offset and the base
572 /// pointer is returned.
573 ///
574 /// The APInt \p Offset has to have a bit-width equal to the IntPtr type for
575 /// the address space of 'this' pointer value, e.g., use
576 /// DataLayout::getIndexTypeSizeInBits(Ty).
577 ///
578 /// If \p AllowNonInbounds is true, constant offsets in GEPs are stripped and
579 /// accumulated even if the GEP is not "inbounds".
580 ///
581 /// If this is called on a non-pointer value, it returns 'this' and the
582 /// \p Offset is not modified.
583 ///
584 /// Note that this function will never return a nullptr. It will also never
585 /// manipulate the \p Offset in a way that would not match the difference
586 /// between the underlying value and the returned one. Thus, if no constant
587 /// offset was found, the returned value is the underlying one and \p Offset
588 /// is unchanged.
589 const Value *stripAndAccumulateConstantOffsets(const DataLayout &DL,
590 APInt &Offset,
591 bool AllowNonInbounds) const;
592 Value *stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset,
593 bool AllowNonInbounds) {
594 return const_cast<Value *>(
595 static_cast<const Value *>(this)->stripAndAccumulateConstantOffsets(
596 DL, Offset, AllowNonInbounds));
597 }
598
599 /// This is a wrapper around stripAndAccumulateConstantOffsets with the
600 /// in-bounds requirement set to false.
601 const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
602 APInt &Offset) const {
603 return stripAndAccumulateConstantOffsets(DL, Offset,
604 /* AllowNonInbounds */ false);
605 }
606 Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
607 APInt &Offset) {
608 return stripAndAccumulateConstantOffsets(DL, Offset,
609 /* AllowNonInbounds */ false);
610 }
611
612 /// Strip off pointer casts and inbounds GEPs.
613 ///
614 /// Returns the original pointer value. If this is called on a non-pointer
615 /// value, it returns 'this'.
616 const Value *stripInBoundsOffsets() const;
617 Value *stripInBoundsOffsets() {
618 return const_cast<Value *>(
619 static_cast<const Value *>(this)->stripInBoundsOffsets());
620 }
621
622 /// Returns the number of bytes known to be dereferenceable for the
623 /// pointer value.
624 ///
625 /// If CanBeNull is set by this function the pointer can either be null or be
626 /// dereferenceable up to the returned number of bytes.
627 uint64_t getPointerDereferenceableBytes(const DataLayout &DL,
628 bool &CanBeNull) const;
629
630 /// Returns an alignment of the pointer value.
631 ///
632 /// Returns an alignment which is either specified explicitly, e.g. via
633 /// align attribute of a function argument, or guaranteed by DataLayout.
634 unsigned getPointerAlignment(const DataLayout &DL) const;
635
636 /// Translate PHI node to its predecessor from the given basic block.
637 ///
638 /// If this value is a PHI node with CurBB as its parent, return the value in
639 /// the PHI node corresponding to PredBB. If not, return ourself. This is
640 /// useful if you want to know the value something has in a predecessor
641 /// block.
642 const Value *DoPHITranslation(const BasicBlock *CurBB,
643 const BasicBlock *PredBB) const;
644 Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) {
645 return const_cast<Value *>(
646 static_cast<const Value *>(this)->DoPHITranslation(CurBB, PredBB));
647 }
648
649 /// The maximum alignment for instructions.
650 ///
651 /// This is the greatest alignment value supported by load, store, and alloca
652 /// instructions, and global values.
653 static const unsigned MaxAlignmentExponent = 29;
654 static const unsigned MaximumAlignment = 1u << MaxAlignmentExponent;
655
656 /// Mutate the type of this Value to be of the specified type.
657 ///
658 /// Note that this is an extremely dangerous operation which can create
659 /// completely invalid IR very easily. It is strongly recommended that you
660 /// recreate IR objects with the right types instead of mutating them in
661 /// place.
662 void mutateType(Type *Ty) {
663 VTy = Ty;
664 }
665
666 /// Sort the use-list.
667 ///
668 /// Sorts the Value's use-list by Cmp using a stable mergesort. Cmp is
669 /// expected to compare two \a Use references.
670 template <class Compare> void sortUseList(Compare Cmp);
671
672 /// Reverse the use-list.
673 void reverseUseList();
674
675private:
676 /// Merge two lists together.
677 ///
678 /// Merges \c L and \c R using \c Cmp. To enable stable sorts, always pushes
679 /// "equal" items from L before items from R.
680 ///
681 /// \return the first element in the list.
682 ///
683 /// \note Completely ignores \a Use::Prev (doesn't read, doesn't update).
684 template <class Compare>
685 static Use *mergeUseLists(Use *L, Use *R, Compare Cmp) {
686 Use *Merged;
687 Use **Next = &Merged;
688
689 while (true) {
690 if (!L) {
691 *Next = R;
692 break;
693 }
694 if (!R) {
695 *Next = L;
696 break;
697 }
698 if (Cmp(*R, *L)) {
699 *Next = R;
700 Next = &R->Next;
701 R = R->Next;
702 } else {
703 *Next = L;
704 Next = &L->Next;
705 L = L->Next;
706 }
707 }
708
709 return Merged;
710 }
711
712protected:
713 unsigned short getSubclassDataFromValue() const { return SubclassData; }
714 void setValueSubclassData(unsigned short D) { SubclassData = D; }
715};
716
717struct ValueDeleter { void operator()(Value *V) { V->deleteValue(); } };
718
719/// Use this instead of std::unique_ptr<Value> or std::unique_ptr<Instruction>.
720/// Those don't work because Value and Instruction's destructors are protected,
721/// aren't virtual, and won't destroy the complete object.
722using unique_value = std::unique_ptr<Value, ValueDeleter>;
723
724inline raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
725 V.print(OS);
726 return OS;
727}
728
729void Use::set(Value *V) {
730 if (Val) removeFromList();
731 Val = V;
732 if (V) V->addUse(*this);
733}
734
735Value *Use::operator=(Value *RHS) {
736 set(RHS);
737 return RHS;
738}
739
740const Use &Use::operator=(const Use &RHS) {
741 set(RHS.Val);
742 return *this;
743}
744
745template <class Compare> void Value::sortUseList(Compare Cmp) {
746 if (!UseList || !UseList->Next)
747 // No need to sort 0 or 1 uses.
748 return;
749
750 // Note: this function completely ignores Prev pointers until the end when
751 // they're fixed en masse.
752
753 // Create a binomial vector of sorted lists, visiting uses one at a time and
754 // merging lists as necessary.
755 const unsigned MaxSlots = 32;
756 Use *Slots[MaxSlots];
757
758 // Collect the first use, turning it into a single-item list.
759 Use *Next = UseList->Next;
760 UseList->Next = nullptr;
761 unsigned NumSlots = 1;
762 Slots[0] = UseList;
763
764 // Collect all but the last use.
765 while (Next->Next) {
766 Use *Current = Next;
767 Next = Current->Next;
768
769 // Turn Current into a single-item list.
770 Current->Next = nullptr;
771
772 // Save Current in the first available slot, merging on collisions.
773 unsigned I;
774 for (I = 0; I < NumSlots; ++I) {
775 if (!Slots[I])
776 break;
777
778 // Merge two lists, doubling the size of Current and emptying slot I.
779 //
780 // Since the uses in Slots[I] originally preceded those in Current, send
781 // Slots[I] in as the left parameter to maintain a stable sort.
782 Current = mergeUseLists(Slots[I], Current, Cmp);
783 Slots[I] = nullptr;
784 }
785 // Check if this is a new slot.
786 if (I == NumSlots) {
787 ++NumSlots;
788 assert(NumSlots <= MaxSlots && "Use list bigger than 2^32")((NumSlots <= MaxSlots && "Use list bigger than 2^32"
) ? static_cast<void> (0) : __assert_fail ("NumSlots <= MaxSlots && \"Use list bigger than 2^32\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 788, __PRETTY_FUNCTION__))
;
789 }
790
791 // Found an open slot.
792 Slots[I] = Current;
793 }
794
795 // Merge all the lists together.
796 assert(Next && "Expected one more Use")((Next && "Expected one more Use") ? static_cast<void
> (0) : __assert_fail ("Next && \"Expected one more Use\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 796, __PRETTY_FUNCTION__))
;
797 assert(!Next->Next && "Expected only one Use")((!Next->Next && "Expected only one Use") ? static_cast
<void> (0) : __assert_fail ("!Next->Next && \"Expected only one Use\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/IR/Value.h"
, 797, __PRETTY_FUNCTION__))
;
798 UseList = Next;
799 for (unsigned I = 0; I < NumSlots; ++I)
800 if (Slots[I])
801 // Since the uses in Slots[I] originally preceded those in UseList, send
802 // Slots[I] in as the left parameter to maintain a stable sort.
803 UseList = mergeUseLists(Slots[I], UseList, Cmp);
804
805 // Fix the Prev pointers.
806 for (Use *I = UseList, **Prev = &UseList; I; I = I->Next) {
807 I->setPrev(Prev);
808 Prev = &I->Next;
809 }
810}
811
812// isa - Provide some specializations of isa so that we don't have to include
813// the subtype header files to test to see if the value is a subclass...
814//
815template <> struct isa_impl<Constant, Value> {
816 static inline bool doit(const Value &Val) {
817 static_assert(Value::ConstantFirstVal == 0, "Val.getValueID() >= Value::ConstantFirstVal");
818 return Val.getValueID() <= Value::ConstantLastVal;
819 }
820};
821
822template <> struct isa_impl<ConstantData, Value> {
823 static inline bool doit(const Value &Val) {
824 return Val.getValueID() >= Value::ConstantDataFirstVal &&
825 Val.getValueID() <= Value::ConstantDataLastVal;
826 }
827};
828
829template <> struct isa_impl<ConstantAggregate, Value> {
830 static inline bool doit(const Value &Val) {
831 return Val.getValueID() >= Value::ConstantAggregateFirstVal &&
832 Val.getValueID() <= Value::ConstantAggregateLastVal;
833 }
834};
835
836template <> struct isa_impl<Argument, Value> {
837 static inline bool doit (const Value &Val) {
838 return Val.getValueID() == Value::ArgumentVal;
839 }
840};
841
842template <> struct isa_impl<InlineAsm, Value> {
843 static inline bool doit(const Value &Val) {
844 return Val.getValueID() == Value::InlineAsmVal;
845 }
846};
847
848template <> struct isa_impl<Instruction, Value> {
849 static inline bool doit(const Value &Val) {
850 return Val.getValueID() >= Value::InstructionVal;
851 }
852};
853
854template <> struct isa_impl<BasicBlock, Value> {
855 static inline bool doit(const Value &Val) {
856 return Val.getValueID() == Value::BasicBlockVal;
857 }
858};
859
860template <> struct isa_impl<Function, Value> {
861 static inline bool doit(const Value &Val) {
862 return Val.getValueID() == Value::FunctionVal;
863 }
864};
865
866template <> struct isa_impl<GlobalVariable, Value> {
867 static inline bool doit(const Value &Val) {
868 return Val.getValueID() == Value::GlobalVariableVal;
869 }
870};
871
872template <> struct isa_impl<GlobalAlias, Value> {
873 static inline bool doit(const Value &Val) {
874 return Val.getValueID() == Value::GlobalAliasVal;
875 }
876};
877
878template <> struct isa_impl<GlobalIFunc, Value> {
879 static inline bool doit(const Value &Val) {
880 return Val.getValueID() == Value::GlobalIFuncVal;
881 }
882};
883
884template <> struct isa_impl<GlobalIndirectSymbol, Value> {
885 static inline bool doit(const Value &Val) {
886 return isa<GlobalAlias>(Val) || isa<GlobalIFunc>(Val);
887 }
888};
889
890template <> struct isa_impl<GlobalValue, Value> {
891 static inline bool doit(const Value &Val) {
892 return isa<GlobalObject>(Val) || isa<GlobalIndirectSymbol>(Val);
893 }
894};
895
896template <> struct isa_impl<GlobalObject, Value> {
897 static inline bool doit(const Value &Val) {
898 return isa<GlobalVariable>(Val) || isa<Function>(Val);
899 }
900};
901
902// Create wrappers for C Binding types (see CBindingWrapping.h).
903DEFINE_ISA_CONVERSION_FUNCTIONS(Value, LLVMValueRef)inline Value *unwrap(LLVMValueRef P) { return reinterpret_cast
<Value*>(P); } inline LLVMValueRef wrap(const Value *P)
{ return reinterpret_cast<LLVMValueRef>(const_cast<
Value*>(P)); } template<typename T> inline T *unwrap
(LLVMValueRef P) { return cast<T>(unwrap(P)); }
904
905// Specialized opaque value conversions.
906inline Value **unwrap(LLVMValueRef *Vals) {
907 return reinterpret_cast<Value**>(Vals);
908}
909
910template<typename T>
911inline T **unwrap(LLVMValueRef *Vals, unsigned Length) {
912#ifndef NDEBUG
913 for (LLVMValueRef *I = Vals, *E = Vals + Length; I != E; ++I)
914 unwrap<T>(*I); // For side effect of calling assert on invalid usage.
915#endif
916 (void)Length;
917 return reinterpret_cast<T**>(Vals);
918}
919
920inline LLVMValueRef *wrap(const Value **Vals) {
921 return reinterpret_cast<LLVMValueRef*>(const_cast<Value**>(Vals));
922}
923
924} // end namespace llvm
925
926#endif // LLVM_IR_VALUE_H