LLVM  14.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).
148 static cl::opt<bool>
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.
169 static cl::opt<bool>
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  // Calls that have already been optimized. We may add a call to multiple
522  // VTableSlotInfos if vtable loads are coalesced and need to make sure not to
523  // optimize a call more than once.
524  SmallPtrSet<CallBase *, 8> OptimizedCalls;
525 
526  // This map keeps track of the number of "unsafe" uses of a loaded function
527  // pointer. The key is the associated llvm.type.test intrinsic call generated
528  // by this pass. An unsafe use is one that calls the loaded function pointer
529  // directly. Every time we eliminate an unsafe use (for example, by
530  // devirtualizing it or by applying virtual constant propagation), we
531  // decrement the value stored in this map. If a value reaches zero, we can
532  // eliminate the type check by RAUWing the associated llvm.type.test call with
533  // true.
534  std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
535  PatternList FunctionsToSkip;
536 
537  DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
539  function_ref<DominatorTree &(Function &)> LookupDomTree,
540  ModuleSummaryIndex *ExportSummary,
541  const ModuleSummaryIndex *ImportSummary)
542  : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
543  ExportSummary(ExportSummary), ImportSummary(ImportSummary),
544  Int8Ty(Type::getInt8Ty(M.getContext())),
545  Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
546  Int32Ty(Type::getInt32Ty(M.getContext())),
547  Int64Ty(Type::getInt64Ty(M.getContext())),
548  IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
549  Int8Arr0Ty(ArrayType::get(Type::getInt8Ty(M.getContext()), 0)),
550  RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
551  assert(!(ExportSummary && ImportSummary));
552  FunctionsToSkip.init(SkipFunctionNames);
553  }
554 
555  bool areRemarksEnabled();
556 
557  void
558  scanTypeTestUsers(Function *TypeTestFunc,
559  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
560  void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
561 
562  void buildTypeIdentifierMap(
563  std::vector<VTableBits> &Bits,
564  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
565  bool
566  tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
567  const std::set<TypeMemberInfo> &TypeMemberInfos,
568  uint64_t ByteOffset);
569 
570  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
571  bool &IsExported);
572  bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,
573  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
574  VTableSlotInfo &SlotInfo,
576 
577  void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
578  bool &IsExported);
579  void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
580  VTableSlotInfo &SlotInfo,
581  WholeProgramDevirtResolution *Res, VTableSlot Slot);
582 
583  bool tryEvaluateFunctionsWithArgs(
584  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
586 
587  void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
588  uint64_t TheRetVal);
589  bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
590  CallSiteInfo &CSInfo,
592 
593  // Returns the global symbol name that is used to export information about the
594  // given vtable slot and list of arguments.
595  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
596  StringRef Name);
597 
598  bool shouldExportConstantsAsAbsoluteSymbols();
599 
600  // This function is called during the export phase to create a symbol
601  // definition containing information about the given vtable slot and list of
602  // arguments.
603  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
604  Constant *C);
605  void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
606  uint32_t Const, uint32_t &Storage);
607 
608  // This function is called during the import phase to create a reference to
609  // the symbol definition created during the export phase.
610  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
611  StringRef Name);
612  Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
613  StringRef Name, IntegerType *IntTy,
614  uint32_t Storage);
615 
616  Constant *getMemberAddr(const TypeMemberInfo *M);
617 
618  void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
619  Constant *UniqueMemberAddr);
620  bool tryUniqueRetValOpt(unsigned BitWidth,
621  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
622  CallSiteInfo &CSInfo,
624  VTableSlot Slot, ArrayRef<uint64_t> Args);
625 
626  void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
627  Constant *Byte, Constant *Bit);
628  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
629  VTableSlotInfo &SlotInfo,
630  WholeProgramDevirtResolution *Res, VTableSlot Slot);
631 
632  void rebuildGlobal(VTableBits &B);
633 
634  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
635  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
636 
637  // If we were able to eliminate all unsafe uses for a type checked load,
638  // eliminate the associated type tests by replacing them with true.
639  void removeRedundantTypeTests();
640 
641  bool run();
642 
643  // Lower the module using the action and summary passed as command line
644  // arguments. For testing purposes only.
645  static bool
646  runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
648  function_ref<DominatorTree &(Function &)> LookupDomTree);
649 };
650 
651 struct DevirtIndex {
652  ModuleSummaryIndex &ExportSummary;
653  // The set in which to record GUIDs exported from their module by
654  // devirtualization, used by client to ensure they are not internalized.
655  std::set<GlobalValue::GUID> &ExportedGUIDs;
656  // A map in which to record the information necessary to locate the WPD
657  // resolution for local targets in case they are exported by cross module
658  // importing.
659  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
660 
662 
663  PatternList FunctionsToSkip;
664 
665  DevirtIndex(
666  ModuleSummaryIndex &ExportSummary,
667  std::set<GlobalValue::GUID> &ExportedGUIDs,
668  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
669  : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
670  LocalWPDTargetsMap(LocalWPDTargetsMap) {
671  FunctionsToSkip.init(SkipFunctionNames);
672  }
673 
674  bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
675  const TypeIdCompatibleVtableInfo TIdInfo,
676  uint64_t ByteOffset);
677 
678  bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
679  VTableSlotSummary &SlotSummary,
680  VTableSlotInfo &SlotInfo,
682  std::set<ValueInfo> &DevirtTargets);
683 
684  void run();
685 };
686 
687 struct WholeProgramDevirt : public ModulePass {
688  static char ID;
689 
690  bool UseCommandLine = false;
691 
692  ModuleSummaryIndex *ExportSummary = nullptr;
693  const ModuleSummaryIndex *ImportSummary = nullptr;
694 
695  WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
697  }
698 
699  WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
700  const ModuleSummaryIndex *ImportSummary)
701  : ModulePass(ID), ExportSummary(ExportSummary),
702  ImportSummary(ImportSummary) {
704  }
705 
706  bool runOnModule(Module &M) override {
707  if (skipModule(M))
708  return false;
709 
710  // In the new pass manager, we can request the optimization
711  // remark emitter pass on a per-function-basis, which the
712  // OREGetter will do for us.
713  // In the old pass manager, this is harder, so we just build
714  // an optimization remark emitter on the fly, when we need it.
715  std::unique_ptr<OptimizationRemarkEmitter> ORE;
716  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
717  ORE = std::make_unique<OptimizationRemarkEmitter>(F);
718  return *ORE;
719  };
720 
721  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
722  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
723  };
724 
725  if (UseCommandLine)
726  return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter,
727  LookupDomTree);
728 
729  return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree,
730  ExportSummary, ImportSummary)
731  .run();
732  }
733 
734  void getAnalysisUsage(AnalysisUsage &AU) const override {
738  }
739 };
740 
741 } // end anonymous namespace
742 
743 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
744  "Whole program devirtualization", false, false)
749  "Whole program devirtualization", false, false)
750 char WholeProgramDevirt::ID = 0;
751 
752 ModulePass *
754  const ModuleSummaryIndex *ImportSummary) {
755  return new WholeProgramDevirt(ExportSummary, ImportSummary);
756 }
757 
759  ModuleAnalysisManager &AM) {
760  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
761  auto AARGetter = [&](Function &F) -> AAResults & {
762  return FAM.getResult<AAManager>(F);
763  };
764  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
766  };
767  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
769  };
770  if (UseCommandLine) {
771  if (DevirtModule::runForTesting(M, AARGetter, OREGetter, LookupDomTree))
772  return PreservedAnalyses::all();
773  return PreservedAnalyses::none();
774  }
775  if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
776  ImportSummary)
777  .run())
778  return PreservedAnalyses::all();
779  return PreservedAnalyses::none();
780 }
781 
782 // Enable whole program visibility if enabled by client (e.g. linker) or
783 // internal option, and not force disabled.
784 static bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) {
785  return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) &&
787 }
788 
789 namespace llvm {
790 
791 /// If whole program visibility asserted, then upgrade all public vcall
792 /// visibility metadata on vtable definitions to linkage unit visibility in
793 /// Module IR (for regular or hybrid LTO).
795  Module &M, bool WholeProgramVisibilityEnabledInLTO,
796  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols) {
797  if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
798  return;
799  for (GlobalVariable &GV : M.globals())
800  // Add linkage unit visibility to any variable with type metadata, which are
801  // the vtable definitions. We won't have an existing vcall_visibility
802  // metadata on vtable definitions with public visibility.
803  if (GV.hasMetadata(LLVMContext::MD_type) &&
804  GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic &&
805  // Don't upgrade the visibility for symbols exported to the dynamic
806  // linker, as we have no information on their eventual use.
807  !DynamicExportSymbols.count(GV.getGUID()))
808  GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit);
809 }
810 
811 /// If whole program visibility asserted, then upgrade all public vcall
812 /// visibility metadata on vtable definition summaries to linkage unit
813 /// visibility in Module summary index (for ThinLTO).
815  ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
816  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols) {
817  if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))
818  return;
819  for (auto &P : Index) {
820  for (auto &S : P.second.SummaryList) {
821  auto *GVar = dyn_cast<GlobalVarSummary>(S.get());
822  if (!GVar ||
823  GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic ||
824  // Don't upgrade the visibility for symbols exported to the dynamic
825  // linker, as we have no information on their eventual use.
826  DynamicExportSymbols.count(P.first))
827  continue;
828  GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit);
829  }
830  }
831 }
832 
834  ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
835  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
836  DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
837 }
838 
840  ModuleSummaryIndex &Summary,
841  function_ref<bool(StringRef, ValueInfo)> isExported,
842  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
843  for (auto &T : LocalWPDTargetsMap) {
844  auto &VI = T.first;
845  // This was enforced earlier during trySingleImplDevirt.
846  assert(VI.getSummaryList().size() == 1 &&
847  "Devirt of local target has more than one copy");
848  auto &S = VI.getSummaryList()[0];
849  if (!isExported(S->modulePath(), VI))
850  continue;
851 
852  // It's been exported by a cross module import.
853  for (auto &SlotSummary : T.second) {
854  auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
855  assert(TIdSum);
856  auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
857  assert(WPDRes != TIdSum->WPDRes.end());
858  WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
859  WPDRes->second.SingleImplName,
860  Summary.getModuleHash(S->modulePath()));
861  }
862  }
863 }
864 
865 } // end namespace llvm
866 
868  // Check that summary index contains regular LTO module when performing
869  // export to prevent occasional use of index from pure ThinLTO compilation
870  // (-fno-split-lto-module). This kind of summary index is passed to
871  // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting.
872  const auto &ModPaths = Summary->modulePaths();
875  ModPaths.end())
876  return createStringError(
878  "combined summary should contain Regular LTO module");
879  return ErrorSuccess();
880 }
881 
882 bool DevirtModule::runForTesting(
883  Module &M, function_ref<AAResults &(Function &)> AARGetter,
885  function_ref<DominatorTree &(Function &)> LookupDomTree) {
886  std::unique_ptr<ModuleSummaryIndex> Summary =
887  std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false);
888 
889  // Handle the command-line summary arguments. This code is for testing
890  // purposes only, so we handle errors directly.
891  if (!ClReadSummary.empty()) {
892  ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
893  ": ");
894  auto ReadSummaryFile =
896  if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =
897  getModuleSummaryIndex(*ReadSummaryFile)) {
898  Summary = std::move(*SummaryOrErr);
899  ExitOnErr(checkCombinedSummaryForTesting(Summary.get()));
900  } else {
901  // Try YAML if we've failed with bitcode.
902  consumeError(SummaryOrErr.takeError());
903  yaml::Input In(ReadSummaryFile->getBuffer());
904  In >> *Summary;
905  ExitOnErr(errorCodeToError(In.error()));
906  }
907  }
908 
909  bool Changed =
910  DevirtModule(M, AARGetter, OREGetter, LookupDomTree,
911  ClSummaryAction == PassSummaryAction::Export ? Summary.get()
912  : nullptr,
913  ClSummaryAction == PassSummaryAction::Import ? Summary.get()
914  : nullptr)
915  .run();
916 
917  if (!ClWriteSummary.empty()) {
918  ExitOnError ExitOnErr(
919  "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
920  std::error_code EC;
921  if (StringRef(ClWriteSummary).endswith(".bc")) {
923  ExitOnErr(errorCodeToError(EC));
924  WriteIndexToFile(*Summary, OS);
925  } else {
927  ExitOnErr(errorCodeToError(EC));
928  yaml::Output Out(OS);
929  Out << *Summary;
930  }
931  }
932 
933  return Changed;
934 }
935 
936 void DevirtModule::buildTypeIdentifierMap(
937  std::vector<VTableBits> &Bits,
938  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
940  Bits.reserve(M.getGlobalList().size());
942  for (GlobalVariable &GV : M.globals()) {
943  Types.clear();
944  GV.getMetadata(LLVMContext::MD_type, Types);
945  if (GV.isDeclaration() || Types.empty())
946  continue;
947 
948  VTableBits *&BitsPtr = GVToBits[&GV];
949  if (!BitsPtr) {
950  Bits.emplace_back();
951  Bits.back().GV = &GV;
952  Bits.back().ObjectSize =
953  M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
954  BitsPtr = &Bits.back();
955  }
956 
957  for (MDNode *Type : Types) {
958  auto TypeID = Type->getOperand(1).get();
959 
960  uint64_t Offset =
961  cast<ConstantInt>(
962  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
963  ->getZExtValue();
964 
965  TypeIdMap[TypeID].insert({BitsPtr, Offset});
966  }
967  }
968 }
969 
970 bool DevirtModule::tryFindVirtualCallTargets(
971  std::vector<VirtualCallTarget> &TargetsForSlot,
972  const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
973  for (const TypeMemberInfo &TM : TypeMemberInfos) {
974  if (!TM.Bits->GV->isConstant())
975  return false;
976 
977  // We cannot perform whole program devirtualization analysis on a vtable
978  // with public LTO visibility.
979  if (TM.Bits->GV->getVCallVisibility() ==
981  return false;
982 
983  Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
984  TM.Offset + ByteOffset, M);
985  if (!Ptr)
986  return false;
987 
988  auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
989  if (!Fn)
990  return false;
991 
992  if (FunctionsToSkip.match(Fn->getName()))
993  return false;
994 
995  // We can disregard __cxa_pure_virtual as a possible call target, as
996  // calls to pure virtuals are UB.
997  if (Fn->getName() == "__cxa_pure_virtual")
998  continue;
999 
1000  TargetsForSlot.push_back({Fn, &TM});
1001  }
1002 
1003  // Give up if we couldn't find any targets.
1004  return !TargetsForSlot.empty();
1005 }
1006 
1007 bool DevirtIndex::tryFindVirtualCallTargets(
1008  std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo,
1009  uint64_t ByteOffset) {
1010  for (const TypeIdOffsetVtableInfo &P : TIdInfo) {
1011  // Find a representative copy of the vtable initializer.
1012  // We can have multiple available_externally, linkonce_odr and weak_odr
1013  // vtable initializers. We can also have multiple external vtable
1014  // initializers in the case of comdats, which we cannot check here.
1015  // The linker should give an error in this case.
1016  //
1017  // Also, handle the case of same-named local Vtables with the same path
1018  // and therefore the same GUID. This can happen if there isn't enough
1019  // distinguishing path when compiling the source file. In that case we
1020  // conservatively return false early.
1021  const GlobalVarSummary *VS = nullptr;
1022  bool LocalFound = false;
1023  for (auto &S : P.VTableVI.getSummaryList()) {
1024  if (GlobalValue::isLocalLinkage(S->linkage())) {
1025  if (LocalFound)
1026  return false;
1027  LocalFound = true;
1028  }
1029  auto *CurVS = cast<GlobalVarSummary>(S->getBaseObject());
1030  if (!CurVS->vTableFuncs().empty() ||
1031  // Previously clang did not attach the necessary type metadata to
1032  // available_externally vtables, in which case there would not
1033  // be any vtable functions listed in the summary and we need
1034  // to treat this case conservatively (in case the bitcode is old).
1035  // However, we will also not have any vtable functions in the
1036  // case of a pure virtual base class. In that case we do want
1037  // to set VS to avoid treating it conservatively.
1039  VS = CurVS;
1040  // We cannot perform whole program devirtualization analysis on a vtable
1041  // with public LTO visibility.
1042  if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic)
1043  return false;
1044  }
1045  }
1046  // There will be no VS if all copies are available_externally having no
1047  // type metadata. In that case we can't safely perform WPD.
1048  if (!VS)
1049  return false;
1050  if (!VS->isLive())
1051  continue;
1052  for (auto VTP : VS->vTableFuncs()) {
1053  if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
1054  continue;
1055 
1056  TargetsForSlot.push_back(VTP.FuncVI);
1057  }
1058  }
1059 
1060  // Give up if we couldn't find any targets.
1061  return !TargetsForSlot.empty();
1062 }
1063 
1064 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
1065  Constant *TheFn, bool &IsExported) {
1066  // Don't devirtualize function if we're told to skip it
1067  // in -wholeprogramdevirt-skip.
1068  if (FunctionsToSkip.match(TheFn->stripPointerCasts()->getName()))
1069  return;
1070  auto Apply = [&](CallSiteInfo &CSInfo) {
1071  for (auto &&VCallSite : CSInfo.CallSites) {
1072  if (!OptimizedCalls.insert(&VCallSite.CB).second)
1073  continue;
1074 
1075  if (RemarksEnabled)
1076  VCallSite.emitRemark("single-impl",
1077  TheFn->stripPointerCasts()->getName(), OREGetter);
1078  auto &CB = VCallSite.CB;
1079  assert(!CB.getCalledFunction() && "devirtualizing direct call?");
1080  IRBuilder<> Builder(&CB);
1081  Value *Callee =
1082  Builder.CreateBitCast(TheFn, CB.getCalledOperand()->getType());
1083 
1084  // If checking is enabled, add support to compare the virtual function
1085  // pointer to the devirtualized target. In case of a mismatch, perform a
1086  // debug trap.
1087  if (CheckDevirt) {
1088  auto *Cond = Builder.CreateICmpNE(CB.getCalledOperand(), Callee);
1089  Instruction *ThenTerm =
1090  SplitBlockAndInsertIfThen(Cond, &CB, /*Unreachable=*/false);
1091  Builder.SetInsertPoint(ThenTerm);
1092  Function *TrapFn = Intrinsic::getDeclaration(&M, Intrinsic::debugtrap);
1093  auto *CallTrap = Builder.CreateCall(TrapFn);
1094  CallTrap->setDebugLoc(CB.getDebugLoc());
1095  }
1096 
1097  // Devirtualize.
1098  CB.setCalledOperand(Callee);
1099 
1100  // This use is no longer unsafe.
1101  if (VCallSite.NumUnsafeUses)
1102  --*VCallSite.NumUnsafeUses;
1103  }
1104  if (CSInfo.isExported())
1105  IsExported = true;
1106  CSInfo.markDevirt();
1107  };
1108  Apply(SlotInfo.CSInfo);
1109  for (auto &P : SlotInfo.ConstCSInfo)
1110  Apply(P.second);
1111 }
1112 
1113 static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) {
1114  // We can't add calls if we haven't seen a definition
1115  if (Callee.getSummaryList().empty())
1116  return false;
1117 
1118  // Insert calls into the summary index so that the devirtualized targets
1119  // are eligible for import.
1120  // FIXME: Annotate type tests with hotness. For now, mark these as hot
1121  // to better ensure we have the opportunity to inline them.
1122  bool IsExported = false;
1123  auto &S = Callee.getSummaryList()[0];
1124  CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0);
1125  auto AddCalls = [&](CallSiteInfo &CSInfo) {
1126  for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1127  FS->addCall({Callee, CI});
1128  IsExported |= S->modulePath() != FS->modulePath();
1129  }
1130  for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
1131  FS->addCall({Callee, CI});
1132  IsExported |= S->modulePath() != FS->modulePath();
1133  }
1134  };
1135  AddCalls(SlotInfo.CSInfo);
1136  for (auto &P : SlotInfo.ConstCSInfo)
1137  AddCalls(P.second);
1138  return IsExported;
1139 }
1140 
1141 bool DevirtModule::trySingleImplDevirt(
1142  ModuleSummaryIndex *ExportSummary,
1143  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1145  // See if the program contains a single implementation of this virtual
1146  // function.
1147  Function *TheFn = TargetsForSlot[0].Fn;
1148  for (auto &&Target : TargetsForSlot)
1149  if (TheFn != Target.Fn)
1150  return false;
1151 
1152  // If so, update each call site to call that implementation directly.
1153  if (RemarksEnabled)
1154  TargetsForSlot[0].WasDevirt = true;
1155 
1156  bool IsExported = false;
1157  applySingleImplDevirt(SlotInfo, TheFn, IsExported);
1158  if (!IsExported)
1159  return false;
1160 
1161  // If the only implementation has local linkage, we must promote to external
1162  // to make it visible to thin LTO objects. We can only get here during the
1163  // ThinLTO export phase.
1164  if (TheFn->hasLocalLinkage()) {
1165  std::string NewName = (TheFn->getName() + ".llvm.merged").str();
1166 
1167  // Since we are renaming the function, any comdats with the same name must
1168  // also be renamed. This is required when targeting COFF, as the comdat name
1169  // must match one of the names of the symbols in the comdat.
1170  if (Comdat *C = TheFn->getComdat()) {
1171  if (C->getName() == TheFn->getName()) {
1172  Comdat *NewC = M.getOrInsertComdat(NewName);
1173  NewC->setSelectionKind(C->getSelectionKind());
1174  for (GlobalObject &GO : M.global_objects())
1175  if (GO.getComdat() == C)
1176  GO.setComdat(NewC);
1177  }
1178  }
1179 
1182  TheFn->setName(NewName);
1183  }
1184  if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID()))
1185  // Any needed promotion of 'TheFn' has already been done during
1186  // LTO unit split, so we can ignore return value of AddCalls.
1187  AddCalls(SlotInfo, TheFnVI);
1188 
1190  Res->SingleImplName = std::string(TheFn->getName());
1191 
1192  return true;
1193 }
1194 
1195 bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
1196  VTableSlotSummary &SlotSummary,
1197  VTableSlotInfo &SlotInfo,
1199  std::set<ValueInfo> &DevirtTargets) {
1200  // See if the program contains a single implementation of this virtual
1201  // function.
1202  auto TheFn = TargetsForSlot[0];
1203  for (auto &&Target : TargetsForSlot)
1204  if (TheFn != Target)
1205  return false;
1206 
1207  // Don't devirtualize if we don't have target definition.
1208  auto Size = TheFn.getSummaryList().size();
1209  if (!Size)
1210  return false;
1211 
1212  // Don't devirtualize function if we're told to skip it
1213  // in -wholeprogramdevirt-skip.
1214  if (FunctionsToSkip.match(TheFn.name()))
1215  return false;
1216 
1217  // If the summary list contains multiple summaries where at least one is
1218  // a local, give up, as we won't know which (possibly promoted) name to use.
1219  for (auto &S : TheFn.getSummaryList())
1220  if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1)
1221  return false;
1222 
1223  // Collect functions devirtualized at least for one call site for stats.
1224  if (PrintSummaryDevirt)
1225  DevirtTargets.insert(TheFn);
1226 
1227  auto &S = TheFn.getSummaryList()[0];
1228  bool IsExported = AddCalls(SlotInfo, TheFn);
1229  if (IsExported)
1230  ExportedGUIDs.insert(TheFn.getGUID());
1231 
1232  // Record in summary for use in devirtualization during the ThinLTO import
1233  // step.
1235  if (GlobalValue::isLocalLinkage(S->linkage())) {
1236  if (IsExported)
1237  // If target is a local function and we are exporting it by
1238  // devirtualizing a call in another module, we need to record the
1239  // promoted name.
1241  TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
1242  else {
1243  LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1244  Res->SingleImplName = std::string(TheFn.name());
1245  }
1246  } else
1247  Res->SingleImplName = std::string(TheFn.name());
1248 
1249  // Name will be empty if this thin link driven off of serialized combined
1250  // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
1251  // legacy LTO API anyway.
1252  assert(!Res->SingleImplName.empty());
1253 
1254  return true;
1255 }
1256 
1257 void DevirtModule::tryICallBranchFunnel(
1258  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1259  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1260  Triple T(M.getTargetTriple());
1261  if (T.getArch() != Triple::x86_64)
1262  return;
1263 
1264  if (TargetsForSlot.size() > ClThreshold)
1265  return;
1266 
1267  bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1268  if (!HasNonDevirt)
1269  for (auto &P : SlotInfo.ConstCSInfo)
1270  if (!P.second.AllCallSitesDevirted) {
1271  HasNonDevirt = true;
1272  break;
1273  }
1274 
1275  if (!HasNonDevirt)
1276  return;
1277 
1278  FunctionType *FT =
1279  FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
1280  Function *JT;
1281  if (isa<MDString>(Slot.TypeID)) {
1283  M.getDataLayout().getProgramAddressSpace(),
1284  getGlobalName(Slot, {}, "branch_funnel"), &M);
1285  JT->setVisibility(GlobalValue::HiddenVisibility);
1286  } else {
1288  M.getDataLayout().getProgramAddressSpace(),
1289  "branch_funnel", &M);
1290  }
1291  JT->addAttribute(1, Attribute::Nest);
1292 
1293  std::vector<Value *> JTArgs;
1294  JTArgs.push_back(JT->arg_begin());
1295  for (auto &T : TargetsForSlot) {
1296  JTArgs.push_back(getMemberAddr(T.TM));
1297  JTArgs.push_back(T.Fn);
1298  }
1299 
1300  BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
1301  Function *Intr =
1302  Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
1303 
1304  auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
1305  CI->setTailCallKind(CallInst::TCK_MustTail);
1306  ReturnInst::Create(M.getContext(), nullptr, BB);
1307 
1308  bool IsExported = false;
1309  applyICallBranchFunnel(SlotInfo, JT, IsExported);
1310  if (IsExported)
1312 }
1313 
1314 void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1315  Constant *JT, bool &IsExported) {
1316  auto Apply = [&](CallSiteInfo &CSInfo) {
1317  if (CSInfo.isExported())
1318  IsExported = true;
1319  if (CSInfo.AllCallSitesDevirted)
1320  return;
1321  for (auto &&VCallSite : CSInfo.CallSites) {
1322  CallBase &CB = VCallSite.CB;
1323 
1324  // Jump tables are only profitable if the retpoline mitigation is enabled.
1325  Attribute FSAttr = CB.getCaller()->getFnAttribute("target-features");
1326  if (!FSAttr.isValid() ||
1327  !FSAttr.getValueAsString().contains("+retpoline"))
1328  continue;
1329 
1330  if (RemarksEnabled)
1331  VCallSite.emitRemark("branch-funnel",
1332  JT->stripPointerCasts()->getName(), OREGetter);
1333 
1334  // Pass the address of the vtable in the nest register, which is r10 on
1335  // x86_64.
1336  std::vector<Type *> NewArgs;
1337  NewArgs.push_back(Int8PtrTy);
1338  append_range(NewArgs, CB.getFunctionType()->params());
1339  FunctionType *NewFT =
1341  CB.getFunctionType()->isVarArg());
1342  PointerType *NewFTPtr = PointerType::getUnqual(NewFT);
1343 
1344  IRBuilder<> IRB(&CB);
1345  std::vector<Value *> Args;
1346  Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
1347  llvm::append_range(Args, CB.args());
1348 
1349  CallBase *NewCS = nullptr;
1350  if (isa<CallInst>(CB))
1351  NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(JT, NewFTPtr), Args);
1352  else
1353  NewCS = IRB.CreateInvoke(NewFT, IRB.CreateBitCast(JT, NewFTPtr),
1354  cast<InvokeInst>(CB).getNormalDest(),
1355  cast<InvokeInst>(CB).getUnwindDest(), Args);
1356  NewCS->setCallingConv(CB.getCallingConv());
1357 
1359  std::vector<AttributeSet> NewArgAttrs;
1360  NewArgAttrs.push_back(AttributeSet::get(
1361  M.getContext(), ArrayRef<Attribute>{Attribute::get(
1362  M.getContext(), Attribute::Nest)}));
1363  for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1364  NewArgAttrs.push_back(Attrs.getParamAttributes(I));
1365  NewCS->setAttributes(
1366  AttributeList::get(M.getContext(), Attrs.getFnAttributes(),
1367  Attrs.getRetAttributes(), NewArgAttrs));
1368 
1369  CB.replaceAllUsesWith(NewCS);
1370  CB.eraseFromParent();
1371 
1372  // This use is no longer unsafe.
1373  if (VCallSite.NumUnsafeUses)
1374  --*VCallSite.NumUnsafeUses;
1375  }
1376  // Don't mark as devirtualized because there may be callers compiled without
1377  // retpoline mitigation, which would mean that they are lowered to
1378  // llvm.type.test and therefore require an llvm.type.test resolution for the
1379  // type identifier.
1380  };
1381  Apply(SlotInfo.CSInfo);
1382  for (auto &P : SlotInfo.ConstCSInfo)
1383  Apply(P.second);
1384 }
1385 
1386 bool DevirtModule::tryEvaluateFunctionsWithArgs(
1387  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1389  // Evaluate each function and store the result in each target's RetVal
1390  // field.
1391  for (VirtualCallTarget &Target : TargetsForSlot) {
1392  if (Target.Fn->arg_size() != Args.size() + 1)
1393  return false;
1394 
1395  Evaluator Eval(M.getDataLayout(), nullptr);
1396  SmallVector<Constant *, 2> EvalArgs;
1397  EvalArgs.push_back(
1398  Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
1399  for (unsigned I = 0; I != Args.size(); ++I) {
1400  auto *ArgTy = dyn_cast<IntegerType>(
1401  Target.Fn->getFunctionType()->getParamType(I + 1));
1402  if (!ArgTy)
1403  return false;
1404  EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
1405  }
1406 
1407  Constant *RetVal;
1408  if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
1409  !isa<ConstantInt>(RetVal))
1410  return false;
1411  Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
1412  }
1413  return true;
1414 }
1415 
1416 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1417  uint64_t TheRetVal) {
1418  for (auto Call : CSInfo.CallSites) {
1419  if (!OptimizedCalls.insert(&Call.CB).second)
1420  continue;
1421  Call.replaceAndErase(
1422  "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1423  ConstantInt::get(cast<IntegerType>(Call.CB.getType()), TheRetVal));
1424  }
1425  CSInfo.markDevirt();
1426 }
1427 
1428 bool DevirtModule::tryUniformRetValOpt(
1429  MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1431  // Uniform return value optimization. If all functions return the same
1432  // constant, replace all calls with that constant.
1433  uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1434  for (const VirtualCallTarget &Target : TargetsForSlot)
1435  if (Target.RetVal != TheRetVal)
1436  return false;
1437 
1438  if (CSInfo.isExported()) {
1440  Res->Info = TheRetVal;
1441  }
1442 
1443  applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1444  if (RemarksEnabled)
1445  for (auto &&Target : TargetsForSlot)
1446  Target.WasDevirt = true;
1447  return true;
1448 }
1449 
1450 std::string DevirtModule::getGlobalName(VTableSlot Slot,
1452  StringRef Name) {
1453  std::string FullName = "__typeid_";
1454  raw_string_ostream OS(FullName);
1455  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1456  for (uint64_t Arg : Args)
1457  OS << '_' << Arg;
1458  OS << '_' << Name;
1459  return OS.str();
1460 }
1461 
1462 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1463  Triple T(M.getTargetTriple());
1464  return T.isX86() && T.getObjectFormat() == Triple::ELF;
1465 }
1466 
1467 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1468  StringRef Name, Constant *C) {
1470  getGlobalName(Slot, Args, Name), C, &M);
1472 }
1473 
1474 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1475  StringRef Name, uint32_t Const,
1476  uint32_t &Storage) {
1477  if (shouldExportConstantsAsAbsoluteSymbols()) {
1478  exportGlobal(
1479  Slot, Args, Name,
1480  ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1481  return;
1482  }
1483 
1484  Storage = Const;
1485 }
1486 
1487 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1488  StringRef Name) {
1489  Constant *C =
1490  M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Arr0Ty);
1491  auto *GV = dyn_cast<GlobalVariable>(C);
1492  if (GV)
1493  GV->setVisibility(GlobalValue::HiddenVisibility);
1494  return C;
1495 }
1496 
1497 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1498  StringRef Name, IntegerType *IntTy,
1499  uint32_t Storage) {
1500  if (!shouldExportConstantsAsAbsoluteSymbols())
1501  return ConstantInt::get(IntTy, Storage);
1502 
1503  Constant *C = importGlobal(Slot, Args, Name);
1504  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1505  C = ConstantExpr::getPtrToInt(C, IntTy);
1506 
1507  // We only need to set metadata if the global is newly created, in which
1508  // case it would not have hidden visibility.
1509  if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1510  return C;
1511 
1512  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1513  auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1514  auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1515  GV->setMetadata(LLVMContext::MD_absolute_symbol,
1516  MDNode::get(M.getContext(), {MinC, MaxC}));
1517  };
1518  unsigned AbsWidth = IntTy->getBitWidth();
1519  if (AbsWidth == IntPtrTy->getBitWidth())
1520  SetAbsRange(~0ull, ~0ull); // Full set.
1521  else
1522  SetAbsRange(0, 1ull << AbsWidth);
1523  return C;
1524 }
1525 
1526 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1527  bool IsOne,
1528  Constant *UniqueMemberAddr) {
1529  for (auto &&Call : CSInfo.CallSites) {
1530  if (!OptimizedCalls.insert(&Call.CB).second)
1531  continue;
1532  IRBuilder<> B(&Call.CB);
1533  Value *Cmp =
1534  B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, Call.VTable,
1535  B.CreateBitCast(UniqueMemberAddr, Call.VTable->getType()));
1536  Cmp = B.CreateZExt(Cmp, Call.CB.getType());
1537  Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1538  Cmp);
1539  }
1540  CSInfo.markDevirt();
1541 }
1542 
1543 Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1544  Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1545  return ConstantExpr::getGetElementPtr(Int8Ty, C,
1546  ConstantInt::get(Int64Ty, M->Offset));
1547 }
1548 
1549 bool DevirtModule::tryUniqueRetValOpt(
1550  unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1551  CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1552  VTableSlot Slot, ArrayRef<uint64_t> Args) {
1553  // IsOne controls whether we look for a 0 or a 1.
1554  auto tryUniqueRetValOptFor = [&](bool IsOne) {
1555  const TypeMemberInfo *UniqueMember = nullptr;
1556  for (const VirtualCallTarget &Target : TargetsForSlot) {
1557  if (Target.RetVal == (IsOne ? 1 : 0)) {
1558  if (UniqueMember)
1559  return false;
1560  UniqueMember = Target.TM;
1561  }
1562  }
1563 
1564  // We should have found a unique member or bailed out by now. We already
1565  // checked for a uniform return value in tryUniformRetValOpt.
1566  assert(UniqueMember);
1567 
1568  Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1569  if (CSInfo.isExported()) {
1571  Res->Info = IsOne;
1572 
1573  exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1574  }
1575 
1576  // Replace each call with the comparison.
1577  applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1578  UniqueMemberAddr);
1579 
1580  // Update devirtualization statistics for targets.
1581  if (RemarksEnabled)
1582  for (auto &&Target : TargetsForSlot)
1583  Target.WasDevirt = true;
1584 
1585  return true;
1586  };
1587 
1588  if (BitWidth == 1) {
1589  if (tryUniqueRetValOptFor(true))
1590  return true;
1591  if (tryUniqueRetValOptFor(false))
1592  return true;
1593  }
1594  return false;
1595 }
1596 
1597 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1598  Constant *Byte, Constant *Bit) {
1599  for (auto Call : CSInfo.CallSites) {
1600  if (!OptimizedCalls.insert(&Call.CB).second)
1601  continue;
1602  auto *RetType = cast<IntegerType>(Call.CB.getType());
1603  IRBuilder<> B(&Call.CB);
1604  Value *Addr =
1605  B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1606  if (RetType->getBitWidth() == 1) {
1607  Value *Bits = B.CreateLoad(Int8Ty, Addr);
1608  Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1609  auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1610  Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1611  OREGetter, IsBitSet);
1612  } else {
1613  Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1614  Value *Val = B.CreateLoad(RetType, ValAddr);
1615  Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1616  OREGetter, Val);
1617  }
1618  }
1619  CSInfo.markDevirt();
1620 }
1621 
1622 bool DevirtModule::tryVirtualConstProp(
1623  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1624  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1625  // This only works if the function returns an integer.
1626  auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1627  if (!RetType)
1628  return false;
1629  unsigned BitWidth = RetType->getBitWidth();
1630  if (BitWidth > 64)
1631  return false;
1632 
1633  // Make sure that each function is defined, does not access memory, takes at
1634  // least one argument, does not use its first argument (which we assume is
1635  // 'this'), and has the same return type.
1636  //
1637  // Note that we test whether this copy of the function is readnone, rather
1638  // than testing function attributes, which must hold for any copy of the
1639  // function, even a less optimized version substituted at link time. This is
1640  // sound because the virtual constant propagation optimizations effectively
1641  // inline all implementations of the virtual function into each call site,
1642  // rather than using function attributes to perform local optimization.
1643  for (VirtualCallTarget &Target : TargetsForSlot) {
1644  if (Target.Fn->isDeclaration() ||
1645  computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1646  MAK_ReadNone ||
1647  Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1648  Target.Fn->getReturnType() != RetType)
1649  return false;
1650  }
1651 
1652  for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1653  if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1654  continue;
1655 
1656  WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1657  if (Res)
1658  ResByArg = &Res->ResByArg[CSByConstantArg.first];
1659 
1660  if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1661  continue;
1662 
1663  if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1664  ResByArg, Slot, CSByConstantArg.first))
1665  continue;
1666 
1667  // Find an allocation offset in bits in all vtables associated with the
1668  // type.
1669  uint64_t AllocBefore =
1670  findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1671  uint64_t AllocAfter =
1672  findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1673 
1674  // Calculate the total amount of padding needed to store a value at both
1675  // ends of the object.
1676  uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1677  for (auto &&Target : TargetsForSlot) {
1678  TotalPaddingBefore += std::max<int64_t>(
1679  (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1680  TotalPaddingAfter += std::max<int64_t>(
1681  (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1682  }
1683 
1684  // If the amount of padding is too large, give up.
1685  // FIXME: do something smarter here.
1686  if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1687  continue;
1688 
1689  // Calculate the offset to the value as a (possibly negative) byte offset
1690  // and (if applicable) a bit offset, and store the values in the targets.
1691  int64_t OffsetByte;
1692  uint64_t OffsetBit;
1693  if (TotalPaddingBefore <= TotalPaddingAfter)
1694  setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1695  OffsetBit);
1696  else
1697  setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1698  OffsetBit);
1699 
1700  if (RemarksEnabled)
1701  for (auto &&Target : TargetsForSlot)
1702  Target.WasDevirt = true;
1703 
1704 
1705  if (CSByConstantArg.second.isExported()) {
1707  exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1708  ResByArg->Byte);
1709  exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1710  ResByArg->Bit);
1711  }
1712 
1713  // Rewrite each call to a load from OffsetByte/OffsetBit.
1714  Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1715  Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1716  applyVirtualConstProp(CSByConstantArg.second,
1717  TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1718  }
1719  return true;
1720 }
1721 
1722 void DevirtModule::rebuildGlobal(VTableBits &B) {
1723  if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1724  return;
1725 
1726  // Align the before byte array to the global's minimum alignment so that we
1727  // don't break any alignment requirements on the global.
1728  Align Alignment = M.getDataLayout().getValueOrABITypeAlignment(
1729  B.GV->getAlign(), B.GV->getValueType());
1730  B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment));
1731 
1732  // Before was stored in reverse order; flip it now.
1733  for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1734  std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1735 
1736  // Build an anonymous global containing the before bytes, followed by the
1737  // original initializer, followed by the after bytes.
1738  auto NewInit = ConstantStruct::getAnon(
1739  {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1740  B.GV->getInitializer(),
1741  ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1742  auto NewGV =
1743  new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1744  GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1745  NewGV->setSection(B.GV->getSection());
1746  NewGV->setComdat(B.GV->getComdat());
1747  NewGV->setAlignment(MaybeAlign(B.GV->getAlignment()));
1748 
1749  // Copy the original vtable's metadata to the anonymous global, adjusting
1750  // offsets as required.
1751  NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1752 
1753  // Build an alias named after the original global, pointing at the second
1754  // element (the original initializer).
1755  auto Alias = GlobalAlias::create(
1756  B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1758  NewInit->getType(), NewGV,
1759  ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
1760  ConstantInt::get(Int32Ty, 1)}),
1761  &M);
1762  Alias->setVisibility(B.GV->getVisibility());
1763  Alias->takeName(B.GV);
1764 
1765  B.GV->replaceAllUsesWith(Alias);
1766  B.GV->eraseFromParent();
1767 }
1768 
1769 bool DevirtModule::areRemarksEnabled() {
1770  const auto &FL = M.getFunctionList();
1771  for (const Function &Fn : FL) {
1772  const auto &BBL = Fn.getBasicBlockList();
1773  if (BBL.empty())
1774  continue;
1775  auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1776  return DI.isEnabled();
1777  }
1778  return false;
1779 }
1780 
1781 void DevirtModule::scanTypeTestUsers(
1782  Function *TypeTestFunc,
1783  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
1784  // Find all virtual calls via a virtual table pointer %p under an assumption
1785  // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1786  // points to a member of the type identifier %md. Group calls by (type ID,
1787  // offset) pair (effectively the identity of the virtual function) and store
1788  // to CallSlots.
1789  for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1790  I != E;) {
1791  auto CI = dyn_cast<CallInst>(I->getUser());
1792  ++I;
1793  if (!CI)
1794  continue;
1795 
1796  // Search for virtual calls based on %p and add them to DevirtCalls.
1797  SmallVector<DevirtCallSite, 1> DevirtCalls;
1799  auto &DT = LookupDomTree(*CI->getFunction());
1800  findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1801 
1802  Metadata *TypeId =
1803  cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1804  // If we found any, add them to CallSlots.
1805  if (!Assumes.empty()) {
1806  Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1807  for (DevirtCallSite Call : DevirtCalls)
1808  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB, nullptr);
1809  }
1810 
1811  auto RemoveTypeTestAssumes = [&]() {
1812  // We no longer need the assumes or the type test.
1813  for (auto Assume : Assumes)
1814  Assume->eraseFromParent();
1815  // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1816  // may use the vtable argument later.
1817  if (CI->use_empty())
1818  CI->eraseFromParent();
1819  };
1820 
1821  // At this point we could remove all type test assume sequences, as they
1822  // were originally inserted for WPD. However, we can keep these in the
1823  // code stream for later analysis (e.g. to help drive more efficient ICP
1824  // sequences). They will eventually be removed by a second LowerTypeTests
1825  // invocation that cleans them up. In order to do this correctly, the first
1826  // LowerTypeTests invocation needs to know that they have "Unknown" type
1827  // test resolution, so that they aren't treated as Unsat and lowered to
1828  // False, which will break any uses on assumes. Below we remove any type
1829  // test assumes that will not be treated as Unknown by LTT.
1830 
1831  // The type test assumes will be treated by LTT as Unsat if the type id is
1832  // not used on a global (in which case it has no entry in the TypeIdMap).
1833  if (!TypeIdMap.count(TypeId))
1834  RemoveTypeTestAssumes();
1835 
1836  // For ThinLTO importing, we need to remove the type test assumes if this is
1837  // an MDString type id without a corresponding TypeIdSummary. Any
1838  // non-MDString type ids are ignored and treated as Unknown by LTT, so their
1839  // type test assumes can be kept. If the MDString type id is missing a
1840  // TypeIdSummary (e.g. because there was no use on a vcall, preventing the
1841  // exporting phase of WPD from analyzing it), then it would be treated as
1842  // Unsat by LTT and we need to remove its type test assumes here. If not
1843  // used on a vcall we don't need them for later optimization use in any
1844  // case.
1845  else if (ImportSummary && isa<MDString>(TypeId)) {
1846  const TypeIdSummary *TidSummary =
1847  ImportSummary->getTypeIdSummary(cast<MDString>(TypeId)->getString());
1848  if (!TidSummary)
1849  RemoveTypeTestAssumes();
1850  else
1851  // If one was created it should not be Unsat, because if we reached here
1852  // the type id was used on a global.
1854  }
1855  }
1856 }
1857 
1858 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1859  Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1860 
1861  for (auto I = TypeCheckedLoadFunc->use_begin(),
1862  E = TypeCheckedLoadFunc->use_end();
1863  I != E;) {
1864  auto CI = dyn_cast<CallInst>(I->getUser());
1865  ++I;
1866  if (!CI)
1867  continue;
1868 
1869  Value *Ptr = CI->getArgOperand(0);
1870  Value *Offset = CI->getArgOperand(1);
1871  Value *TypeIdValue = CI->getArgOperand(2);
1872  Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1873 
1874  SmallVector<DevirtCallSite, 1> DevirtCalls;
1875  SmallVector<Instruction *, 1> LoadedPtrs;
1877  bool HasNonCallUses = false;
1878  auto &DT = LookupDomTree(*CI->getFunction());
1879  findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1880  HasNonCallUses, CI, DT);
1881 
1882  // Start by generating "pessimistic" code that explicitly loads the function
1883  // pointer from the vtable and performs the type check. If possible, we will
1884  // eliminate the load and the type check later.
1885 
1886  // If possible, only generate the load at the point where it is used.
1887  // This helps avoid unnecessary spills.
1888  IRBuilder<> LoadB(
1889  (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1890  Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1891  Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1892  Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1893 
1894  for (Instruction *LoadedPtr : LoadedPtrs) {
1895  LoadedPtr->replaceAllUsesWith(LoadedValue);
1896  LoadedPtr->eraseFromParent();
1897  }
1898 
1899  // Likewise for the type test.
1900  IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1901  CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1902 
1903  for (Instruction *Pred : Preds) {
1904  Pred->replaceAllUsesWith(TypeTestCall);
1905  Pred->eraseFromParent();
1906  }
1907 
1908  // We have already erased any extractvalue instructions that refer to the
1909  // intrinsic call, but the intrinsic may have other non-extractvalue uses
1910  // (although this is unlikely). In that case, explicitly build a pair and
1911  // RAUW it.
1912  if (!CI->use_empty()) {
1913  Value *Pair = UndefValue::get(CI->getType());
1914  IRBuilder<> B(CI);
1915  Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1916  Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1917  CI->replaceAllUsesWith(Pair);
1918  }
1919 
1920  // The number of unsafe uses is initially the number of uses.
1921  auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1922  NumUnsafeUses = DevirtCalls.size();
1923 
1924  // If the function pointer has a non-call user, we cannot eliminate the type
1925  // check, as one of those users may eventually call the pointer. Increment
1926  // the unsafe use count to make sure it cannot reach zero.
1927  if (HasNonCallUses)
1928  ++NumUnsafeUses;
1929  for (DevirtCallSite Call : DevirtCalls) {
1930  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB,
1931  &NumUnsafeUses);
1932  }
1933 
1934  CI->eraseFromParent();
1935  }
1936 }
1937 
1938 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1939  auto *TypeId = dyn_cast<MDString>(Slot.TypeID);
1940  if (!TypeId)
1941  return;
1942  const TypeIdSummary *TidSummary =
1943  ImportSummary->getTypeIdSummary(TypeId->getString());
1944  if (!TidSummary)
1945  return;
1946  auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1947  if (ResI == TidSummary->WPDRes.end())
1948  return;
1949  const WholeProgramDevirtResolution &Res = ResI->second;
1950 
1952  assert(!Res.SingleImplName.empty());
1953  // The type of the function in the declaration is irrelevant because every
1954  // call site will cast it to the correct type.
1955  Constant *SingleImpl =
1956  cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,
1957  Type::getVoidTy(M.getContext()))
1958  .getCallee());
1959 
1960  // This is the import phase so we should not be exporting anything.
1961  bool IsExported = false;
1962  applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1963  assert(!IsExported);
1964  }
1965 
1966  for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1967  auto I = Res.ResByArg.find(CSByConstantArg.first);
1968  if (I == Res.ResByArg.end())
1969  continue;
1970  auto &ResByArg = I->second;
1971  // FIXME: We should figure out what to do about the "function name" argument
1972  // to the apply* functions, as the function names are unavailable during the
1973  // importing phase. For now we just pass the empty string. This does not
1974  // impact correctness because the function names are just used for remarks.
1975  switch (ResByArg.TheKind) {
1977  applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1978  break;
1980  Constant *UniqueMemberAddr =
1981  importGlobal(Slot, CSByConstantArg.first, "unique_member");
1982  applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1983  UniqueMemberAddr);
1984  break;
1985  }
1987  Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1988  Int32Ty, ResByArg.Byte);
1989  Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1990  ResByArg.Bit);
1991  applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1992  break;
1993  }
1994  default:
1995  break;
1996  }
1997  }
1998 
2000  // The type of the function is irrelevant, because it's bitcast at calls
2001  // anyhow.
2002  Constant *JT = cast<Constant>(
2003  M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
2004  Type::getVoidTy(M.getContext()))
2005  .getCallee());
2006  bool IsExported = false;
2007  applyICallBranchFunnel(SlotInfo, JT, IsExported);
2008  assert(!IsExported);
2009  }
2010 }
2011 
2012 void DevirtModule::removeRedundantTypeTests() {
2013  auto True = ConstantInt::getTrue(M.getContext());
2014  for (auto &&U : NumUnsafeUsesForTypeTest) {
2015  if (U.second == 0) {
2016  U.first->replaceAllUsesWith(True);
2017  U.first->eraseFromParent();
2018  }
2019  }
2020 }
2021 
2022 bool DevirtModule::run() {
2023  // If only some of the modules were split, we cannot correctly perform
2024  // this transformation. We already checked for the presense of type tests
2025  // with partially split modules during the thin link, and would have emitted
2026  // an error if any were found, so here we can simply return.
2027  if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
2028  (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
2029  return false;
2030 
2031  Function *TypeTestFunc =
2032  M.getFunction(Intrinsic::getName(Intrinsic::type_test));
2033  Function *TypeCheckedLoadFunc =
2034  M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
2035  Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
2036 
2037  // Normally if there are no users of the devirtualization intrinsics in the
2038  // module, this pass has nothing to do. But if we are exporting, we also need
2039  // to handle any users that appear only in the function summaries.
2040  if (!ExportSummary &&
2041  (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
2042  AssumeFunc->use_empty()) &&
2043  (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
2044  return false;
2045 
2046  // Rebuild type metadata into a map for easy lookup.
2047  std::vector<VTableBits> Bits;
2049  buildTypeIdentifierMap(Bits, TypeIdMap);
2050 
2051  if (TypeTestFunc && AssumeFunc)
2052  scanTypeTestUsers(TypeTestFunc, TypeIdMap);
2053 
2054  if (TypeCheckedLoadFunc)
2055  scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
2056 
2057  if (ImportSummary) {
2058  for (auto &S : CallSlots)
2059  importResolution(S.first, S.second);
2060 
2061  removeRedundantTypeTests();
2062 
2063  // We have lowered or deleted the type instrinsics, so we will no
2064  // longer have enough information to reason about the liveness of virtual
2065  // function pointers in GlobalDCE.
2066  for (GlobalVariable &GV : M.globals())
2067  GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2068 
2069  // The rest of the code is only necessary when exporting or during regular
2070  // LTO, so we are done.
2071  return true;
2072  }
2073 
2074  if (TypeIdMap.empty())
2075  return true;
2076 
2077  // Collect information from summary about which calls to try to devirtualize.
2078  if (ExportSummary) {
2080  for (auto &P : TypeIdMap) {
2081  if (auto *TypeId = dyn_cast<MDString>(P.first))
2082  MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
2083  TypeId);
2084  }
2085 
2086  for (auto &P : *ExportSummary) {
2087  for (auto &S : P.second.SummaryList) {
2088  auto *FS = dyn_cast<FunctionSummary>(S.get());
2089  if (!FS)
2090  continue;
2091  // FIXME: Only add live functions.
2092  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2093  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2094  CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2095  }
2096  }
2097  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2098  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2099  CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2100  }
2101  }
2102  for (const FunctionSummary::ConstVCall &VC :
2103  FS->type_test_assume_const_vcalls()) {
2104  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2105  CallSlots[{MD, VC.VFunc.Offset}]
2106  .ConstCSInfo[VC.Args]
2107  .addSummaryTypeTestAssumeUser(FS);
2108  }
2109  }
2110  for (const FunctionSummary::ConstVCall &VC :
2111  FS->type_checked_load_const_vcalls()) {
2112  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2113  CallSlots[{MD, VC.VFunc.Offset}]
2114  .ConstCSInfo[VC.Args]
2115  .addSummaryTypeCheckedLoadUser(FS);
2116  }
2117  }
2118  }
2119  }
2120  }
2121 
2122  // For each (type, offset) pair:
2123  bool DidVirtualConstProp = false;
2124  std::map<std::string, Function*> DevirtTargets;
2125  for (auto &S : CallSlots) {
2126  // Search each of the members of the type identifier for the virtual
2127  // function implementation at offset S.first.ByteOffset, and add to
2128  // TargetsForSlot.
2129  std::vector<VirtualCallTarget> TargetsForSlot;
2130  WholeProgramDevirtResolution *Res = nullptr;
2131  const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[S.first.TypeID];
2132  if (ExportSummary && isa<MDString>(S.first.TypeID) &&
2133  TypeMemberInfos.size())
2134  // For any type id used on a global's type metadata, create the type id
2135  // summary resolution regardless of whether we can devirtualize, so that
2136  // lower type tests knows the type id is not Unsat. If it was not used on
2137  // a global's type metadata, the TypeIdMap entry set will be empty, and
2138  // we don't want to create an entry (with the default Unknown type
2139  // resolution), which can prevent detection of the Unsat.
2140  Res = &ExportSummary
2141  ->getOrInsertTypeIdSummary(
2142  cast<MDString>(S.first.TypeID)->getString())
2143  .WPDRes[S.first.ByteOffset];
2144  if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos,
2145  S.first.ByteOffset)) {
2146 
2147  if (!trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res)) {
2148  DidVirtualConstProp |=
2149  tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
2150 
2151  tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
2152  }
2153 
2154  // Collect functions devirtualized at least for one call site for stats.
2155  if (RemarksEnabled)
2156  for (const auto &T : TargetsForSlot)
2157  if (T.WasDevirt)
2158  DevirtTargets[std::string(T.Fn->getName())] = T.Fn;
2159  }
2160 
2161  // CFI-specific: if we are exporting and any llvm.type.checked.load
2162  // intrinsics were *not* devirtualized, we need to add the resulting
2163  // llvm.type.test intrinsics to the function summaries so that the
2164  // LowerTypeTests pass will export them.
2165  if (ExportSummary && isa<MDString>(S.first.TypeID)) {
2166  auto GUID =
2167  GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
2168  for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
2169  FS->addTypeTest(GUID);
2170  for (auto &CCS : S.second.ConstCSInfo)
2171  for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
2172  FS->addTypeTest(GUID);
2173  }
2174  }
2175 
2176  if (RemarksEnabled) {
2177  // Generate remarks for each devirtualized function.
2178  for (const auto &DT : DevirtTargets) {
2179  Function *F = DT.second;
2180 
2181  using namespace ore;
2182  OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
2183  << "devirtualized "
2184  << NV("FunctionName", DT.first));
2185  }
2186  }
2187 
2188  removeRedundantTypeTests();
2189 
2190  // Rebuild each global we touched as part of virtual constant propagation to
2191  // include the before and after bytes.
2192  if (DidVirtualConstProp)
2193  for (VTableBits &B : Bits)
2194  rebuildGlobal(B);
2195 
2196  // We have lowered or deleted the type instrinsics, so we will no
2197  // longer have enough information to reason about the liveness of virtual
2198  // function pointers in GlobalDCE.
2199  for (GlobalVariable &GV : M.globals())
2200  GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2201 
2202  return true;
2203 }
2204 
2205 void DevirtIndex::run() {
2206  if (ExportSummary.typeIdCompatibleVtableMap().empty())
2207  return;
2208 
2210  for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
2211  NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
2212  }
2213 
2214  // Collect information from summary about which calls to try to devirtualize.
2215  for (auto &P : ExportSummary) {
2216  for (auto &S : P.second.SummaryList) {
2217  auto *FS = dyn_cast<FunctionSummary>(S.get());
2218  if (!FS)
2219  continue;
2220  // FIXME: Only add live functions.
2221  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2222  for (StringRef Name : NameByGUID[VF.GUID]) {
2223  CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2224  }
2225  }
2226  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2227  for (StringRef Name : NameByGUID[VF.GUID]) {
2228  CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2229  }
2230  }
2231  for (const FunctionSummary::ConstVCall &VC :
2232  FS->type_test_assume_const_vcalls()) {
2233  for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2234  CallSlots[{Name, VC.VFunc.Offset}]
2235  .ConstCSInfo[VC.Args]
2236  .addSummaryTypeTestAssumeUser(FS);
2237  }
2238  }
2239  for (const FunctionSummary::ConstVCall &VC :
2240  FS->type_checked_load_const_vcalls()) {
2241  for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2242  CallSlots[{Name, VC.VFunc.Offset}]
2243  .ConstCSInfo[VC.Args]
2244  .addSummaryTypeCheckedLoadUser(FS);
2245  }
2246  }
2247  }
2248  }
2249 
2250  std::set<ValueInfo> DevirtTargets;
2251  // For each (type, offset) pair:
2252  for (auto &S : CallSlots) {
2253  // Search each of the members of the type identifier for the virtual
2254  // function implementation at offset S.first.ByteOffset, and add to
2255  // TargetsForSlot.
2256  std::vector<ValueInfo> TargetsForSlot;
2257  auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
2258  assert(TidSummary);
2259  // Create the type id summary resolution regardlness of whether we can
2260  // devirtualize, so that lower type tests knows the type id is used on
2261  // a global and not Unsat.
2263  &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
2264  .WPDRes[S.first.ByteOffset];
2265  if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
2266  S.first.ByteOffset)) {
2267 
2268  if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
2269  DevirtTargets))
2270  continue;
2271  }
2272  }
2273 
2274  // Optionally have the thin link print message for each devirtualized
2275  // function.
2276  if (PrintSummaryDevirt)
2277  for (const auto &DT : DevirtTargets)
2278  errs() << "Devirtualized call to " << DT << "\n";
2279 }
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:971
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:148
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:1233
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::Attribute::isValid
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition: Attributes.h:167
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:741
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:266
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:757
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:1336
Metadata.h
DisableWholeProgramVisibility
static 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:1394
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:769
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:52
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:834
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:623
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
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:169
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:833
llvm::TypeTestResolution::Unsat
@ Unsat
Unsatisfiable type (i.e. no global has this type metadata)
Definition: ModuleSummaryIndex.h:912
llvm::Intrinsic::getName
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:836
llvm::IRBuilder<>
MapVector.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
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:2221
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:327
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:1040
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
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
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:45
DenseMap.h
Module.h
llvm::Triple::x86_64
@ x86_64
Definition: Triple.h:84
llvm::AttributeList
Definition: Attributes.h:398
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1468
llvm::CallBase::getFunctionType
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1241
llvm::TypeIdOffsetVtableInfo
The following data structures summarize type metadata information.
Definition: ModuleSummaryIndex.h:1013
llvm::ExitOnError
Helper for check-and-exit error handling.
Definition: Error.h:1335
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:94
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::GlobPattern
Definition: GlobPattern.h:29
llvm::ConstantAsMetadata::get
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:419
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:1459
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
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
CheckDevirt
static 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:136
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
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:7027
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:356
checkCombinedSummaryForTesting
static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary)
Definition: WholeProgramDevirt.cpp:867
BasicAliasAnalysis.h
llvm::CallInst::TCK_MustTail
@ TCK_MustTail
Definition: Instructions.h:1655
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:1035
llvm::ZB_Undefined
@ ZB_Undefined
The returned value is undefined.
Definition: MathExtras.h:46
llvm::PassSummaryAction::Export
@ Export
Export information to summary.
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1198
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:758
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:537
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:206
Instruction.h
CommandLine.h
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::MemoryBuffer::getFile
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
Definition: MemoryBuffer.cpp:246
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:262
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:456
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:753
BitcodeWriter.h
Intr
unsigned Intr
Definition: AMDGPUBaseInfo.cpp:1987
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:2207
SkipFunctionNames
static 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::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::GlobalObject
Definition: GlobalObject.h:28
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1472
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:1518
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:2193
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
llvm::GlobalObject::getComdat
const Comdat * getComdat() const
Definition: GlobalObject.h:123
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
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:965
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:4677
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:462
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:364
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
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:899
llvm::FunctionType::params
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:129
AddCalls
static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee)
Definition: WholeProgramDevirt.cpp:1113
DebugLoc.h
llvm::GlobalObject::VCallVisibilityPublic
@ VCallVisibilityPublic
Definition: GlobalObject.h:35
llvm::computeFunctionBodyMemoryAccess
MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
Definition: FunctionAttrs.cpp:236
llvm::WholeProgramDevirtResolution::BranchFunnel
@ BranchFunnel
When retpoline mitigation is enabled, use a branch funnel that is defined in the merged module.
Definition: ModuleSummaryIndex.h:941
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:153
llvm::Comdat
Definition: Comdat.h:31
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::CallBase::getCallingConv
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1449
llvm::Attribute::getValueAsString
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:301
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:195
llvm::PassSummaryAction::Import
@ Import
Import information from summary.
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
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:282
Evaluator.h
llvm::CalleeInfo
Class to accumulate and hold information about a callee.
Definition: ModuleSummaryIndex.h:57
llvm::WholeProgramDevirtResolution::SingleImpl
@ SingleImpl
Single implementation devirtualization.
Definition: ModuleSummaryIndex.h:940
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:168
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::initializeWholeProgramDevirtPass
void initializeWholeProgramDevirtPass(PassRegistry &)
llvm::sys::fs::OF_TextWithCRLF
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
Definition: FileSystem.h:770
llvm::WholeProgramDevirtResolution::SingleImplName
std::string SingleImplName
Definition: ModuleSummaryIndex.h:946
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:120
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:814
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::WholeProgramDevirtResolution::ByArg::UniformRetVal
@ UniformRetVal
Uniform return value optimization.
Definition: ModuleSummaryIndex.h:951
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:1422
llvm::FunctionSummary::VFuncId
An "identifier" for a virtual function.
Definition: ModuleSummaryIndex.h:529
llvm::CalleeInfo::HotnessType::Hot
@ Hot
llvm::Triple::ELF
@ ELF
Definition: Triple.h:235
VI
@ VI
Definition: SIInstrInfo.cpp:7542
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:699
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::PointerType::getUnqual
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
Definition: DerivedTypes.h:650
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
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:590
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:1256
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:3088
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:329
llvm::DenseMapInfo< VTableSlot >::getTombstoneKey
static VTableSlot getTombstoneKey()
Definition: WholeProgramDevirt.cpp:325
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::X86AS::FS
@ FS
Definition: X86.h:188
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:443
llvm::DenseMapInfo< VTableSlotSummary >::getEmptyKey
static VTableSlotSummary getEmptyKey()
Definition: WholeProgramDevirt.cpp:340
llvm::WholeProgramDevirtResolution::ByArg::UniqueRetVal
@ UniqueRetVal
Unique return value optimization.
Definition: ModuleSummaryIndex.h:952
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:631
WholeProgramVisibility
static 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:974
llvm::ModuleSummaryIndex::modulePaths
const StringMap< std::pair< uint64_t, ModuleHash > > & modulePaths() const
Table of modules, containing module hash and id.
Definition: ModuleSummaryIndex.h:1379
llvm::ConstantStruct::getAnon
static Constant * getAnon(ArrayRef< Constant * > V, bool Packed=false)
Return an anonymous struct that has the specified elements.
Definition: Constants.h:462
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:840
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:361
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:839
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:897
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::getPointerAtOffset
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M)
Definition: TypeMetadataUtils.cpp:129
llvm::ModuleSummaryIndex::partiallySplitLTOUnits
bool partiallySplitLTOUnits() const
Definition: ModuleSummaryIndex.h:1244
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:794
ModuleSummaryIndexYAML.h
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::GlobPattern::create
static Expected< GlobPattern > create(StringRef Pat)
Definition: GlobPattern.cpp:108
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::countTrailingZeros
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: MathExtras.h:156
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt", "Whole program devirtualization", false, false) INITIALIZE_PASS_END(WholeProgramDevirt
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:256
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:691
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
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:776
uint32_t
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1744
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:369
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:674
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:1024
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:297
llvm::raw_fd_ostream
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:441
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:206
GlobPattern.h
llvm::DenseMapInfo< VTableSlotSummary >::getTombstoneKey
static VTableSlotSummary getTombstoneKey()
Definition: WholeProgramDevirt.cpp:344
llvm::WholeProgramDevirtResolution::ByArg
Definition: ModuleSummaryIndex.h:948
llvm::FunctionSummary
Function summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:513
llvm::createStringError
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1231
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:847
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::AArch64CC::VS
@ VS
Definition: AArch64BaseInfo.h:261
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:346
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:95
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:365
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:960
llvm::WholeProgramDevirtResolution::ByArg::VirtualConstProp
@ VirtualConstProp
Virtual constant propagation.
Definition: ModuleSummaryIndex.h:953
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:2977
llvm::CallBase::arg_empty
bool arg_empty() const
Definition: InstrTypes.h:1325
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:1386
WholeProgramDevirt.h
GlobalAlias.h
llvm::codeview::ModifierOptions::Const
@ Const
llvm::CallBase::setCalledOperand
void setCalledOperand(Value *V)
Definition: InstrTypes.h:1426
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:252
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:186
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:979
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:1171
llvm::GlobalValue::PrivateLinkage
@ PrivateLinkage
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
Instructions.h
devirtualization
Whole program devirtualization
Definition: WholeProgramDevirt.cpp:749
llvm::pdb::DbgHeaderType::Max
@ Max
llvm::TypeIdSummary::TTRes
TypeTestResolution TTRes
Definition: ModuleSummaryIndex.h:975
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:372
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1028
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:1402
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:165
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:340
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:1161
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:926
llvm::WholeProgramDevirtResolution
Definition: ModuleSummaryIndex.h:937
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:1475
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:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
wholeprogramdevirt
wholeprogramdevirt
Definition: WholeProgramDevirt.cpp:748
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:1418
llvm::Type::TypeID
TypeID
Definitions of all of the base types for the Type system.
Definition: Type.h:54
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::cl::desc
Definition: CommandLine.h:414
BitcodeReader.h
BasicBlockUtils.h
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
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:271
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:235
InitializePasses.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::WholeProgramDevirtResolution::ByArg::Bit
uint32_t Bit
Definition: ModuleSummaryIndex.h:966
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:38
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:75
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1319
hasWholeProgramVisibility
static bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO)
Definition: WholeProgramDevirt.cpp:784
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1453
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:102
llvm::Function::size
size_t size() const
Definition: Function.h:783
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::ModuleSummaryIndex::getRegularLTOModuleName
static constexpr const char * getRegularLTOModuleName()
Definition: ModuleSummaryIndex.h:1127
llvm::cl::list
Definition: CommandLine.h:1630