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