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