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