Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name WholeProgramDevirt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/IPO -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/include -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-05-202135-9119-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

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

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