LLVM  10.0.0svn
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"
65 #include "llvm/IR/CallSite.h"
66 #include "llvm/IR/Constants.h"
67 #include "llvm/IR/DataLayout.h"
68 #include "llvm/IR/DebugLoc.h"
69 #include "llvm/IR/DerivedTypes.h"
70 #include "llvm/IR/Dominators.h"
71 #include "llvm/IR/Function.h"
72 #include "llvm/IR/GlobalAlias.h"
73 #include "llvm/IR/GlobalVariable.h"
74 #include "llvm/IR/IRBuilder.h"
75 #include "llvm/IR/InstrTypes.h"
76 #include "llvm/IR/Instruction.h"
77 #include "llvm/IR/Instructions.h"
78 #include "llvm/IR/Intrinsics.h"
79 #include "llvm/IR/LLVMContext.h"
80 #include "llvm/IR/Metadata.h"
81 #include "llvm/IR/Module.h"
83 #include "llvm/Pass.h"
84 #include "llvm/PassRegistry.h"
85 #include "llvm/PassSupport.h"
86 #include "llvm/Support/Casting.h"
87 #include "llvm/Support/Error.h"
90 #include "llvm/Transforms/IPO.h"
93 #include <algorithm>
94 #include <cstddef>
95 #include <map>
96 #include <set>
97 #include <string>
98 
99 using namespace llvm;
100 using namespace wholeprogramdevirt;
101 
102 #define DEBUG_TYPE "wholeprogramdevirt"
103 
105  "wholeprogramdevirt-summary-action",
106  cl::desc("What to do with the summary when running this pass"),
107  cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
109  "Import typeid resolutions from summary and globals"),
111  "Export typeid resolutions to summary and globals")),
112  cl::Hidden);
113 
115  "wholeprogramdevirt-read-summary",
116  cl::desc("Read summary from given YAML file before running pass"),
117  cl::Hidden);
118 
120  "wholeprogramdevirt-write-summary",
121  cl::desc("Write summary to given YAML file after running pass"),
122  cl::Hidden);
123 
124 static cl::opt<unsigned>
125  ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
127  cl::desc("Maximum number of call targets per "
128  "call site to enable branch funnels"));
129 
130 static cl::opt<bool>
131  PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,
132  cl::init(false), cl::ZeroOrMore,
133  cl::desc("Print index-based devirtualization messages"));
134 
135 // Find the minimum offset that we may store a value of size Size bits at. If
136 // IsAfter is set, look for an offset before the object, otherwise look for an
137 // offset after the object.
138 uint64_t
140  bool IsAfter, uint64_t Size) {
141  // Find a minimum offset taking into account only vtable sizes.
142  uint64_t MinByte = 0;
143  for (const VirtualCallTarget &Target : Targets) {
144  if (IsAfter)
145  MinByte = std::max(MinByte, Target.minAfterBytes());
146  else
147  MinByte = std::max(MinByte, Target.minBeforeBytes());
148  }
149 
150  // Build a vector of arrays of bytes covering, for each target, a slice of the
151  // used region (see AccumBitVector::BytesUsed in
152  // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
153  // this aligns the used regions to start at MinByte.
154  //
155  // In this example, A, B and C are vtables, # is a byte already allocated for
156  // a virtual function pointer, AAAA... (etc.) are the used regions for the
157  // vtables and Offset(X) is the value computed for the Offset variable below
158  // for X.
159  //
160  // Offset(A)
161  // | |
162  // |MinByte
163  // A: ################AAAAAAAA|AAAAAAAA
164  // B: ########BBBBBBBBBBBBBBBB|BBBB
165  // C: ########################|CCCCCCCCCCCCCCCC
166  // | Offset(B) |
167  //
168  // This code produces the slices of A, B and C that appear after the divider
169  // at MinByte.
170  std::vector<ArrayRef<uint8_t>> Used;
171  for (const VirtualCallTarget &Target : Targets) {
172  ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
173  : Target.TM->Bits->Before.BytesUsed;
174  uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
175  : MinByte - Target.minBeforeBytes();
176 
177  // Disregard used regions that are smaller than Offset. These are
178  // effectively all-free regions that do not need to be checked.
179  if (VTUsed.size() > Offset)
180  Used.push_back(VTUsed.slice(Offset));
181  }
182 
183  if (Size == 1) {
184  // Find a free bit in each member of Used.
185  for (unsigned I = 0;; ++I) {
186  uint8_t BitsUsed = 0;
187  for (auto &&B : Used)
188  if (I < B.size())
189  BitsUsed |= B[I];
190  if (BitsUsed != 0xff)
191  return (MinByte + I) * 8 +
192  countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
193  }
194  } else {
195  // Find a free (Size/8) byte region in each member of Used.
196  // FIXME: see if alignment helps.
197  for (unsigned I = 0;; ++I) {
198  for (auto &&B : Used) {
199  unsigned Byte = 0;
200  while ((I + Byte) < B.size() && Byte < (Size / 8)) {
201  if (B[I + Byte])
202  goto NextI;
203  ++Byte;
204  }
205  }
206  return (MinByte + I) * 8;
207  NextI:;
208  }
209  }
210 }
211 
213  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
214  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
215  if (BitWidth == 1)
216  OffsetByte = -(AllocBefore / 8 + 1);
217  else
218  OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
219  OffsetBit = AllocBefore % 8;
220 
221  for (VirtualCallTarget &Target : Targets) {
222  if (BitWidth == 1)
223  Target.setBeforeBit(AllocBefore);
224  else
225  Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
226  }
227 }
228 
230  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
231  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
232  if (BitWidth == 1)
233  OffsetByte = AllocAfter / 8;
234  else
235  OffsetByte = (AllocAfter + 7) / 8;
236  OffsetBit = AllocAfter % 8;
237 
238  for (VirtualCallTarget &Target : Targets) {
239  if (BitWidth == 1)
240  Target.setAfterBit(AllocAfter);
241  else
242  Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
243  }
244 }
245 
247  : Fn(Fn), TM(TM),
248  IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
249 
250 namespace {
251 
252 // A slot in a set of virtual tables. The TypeID identifies the set of virtual
253 // tables, and the ByteOffset is the offset in bytes from the address point to
254 // the virtual function pointer.
255 struct VTableSlot {
256  Metadata *TypeID;
257  uint64_t ByteOffset;
258 };
259 
260 } // end anonymous namespace
261 
262 namespace llvm {
263 
264 template <> struct DenseMapInfo<VTableSlot> {
265  static VTableSlot getEmptyKey() {
268  }
269  static VTableSlot getTombstoneKey() {
272  }
273  static unsigned getHashValue(const VTableSlot &I) {
274  return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
276  }
277  static bool isEqual(const VTableSlot &LHS,
278  const VTableSlot &RHS) {
279  return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
280  }
281 };
282 
283 template <> struct DenseMapInfo<VTableSlotSummary> {
287  }
291  }
292  static unsigned getHashValue(const VTableSlotSummary &I) {
295  }
296  static bool isEqual(const VTableSlotSummary &LHS,
297  const VTableSlotSummary &RHS) {
298  return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
299  }
300 };
301 
302 } // end namespace llvm
303 
304 namespace {
305 
306 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
307 // the indirect virtual call.
308 struct VirtualCallSite {
309  Value *VTable;
310  CallSite CS;
311 
312  // If non-null, this field points to the associated unsafe use count stored in
313  // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
314  // of that field for details.
315  unsigned *NumUnsafeUses;
316 
317  void
318  emitRemark(const StringRef OptName, const StringRef TargetName,
320  Function *F = CS.getCaller();
321  DebugLoc DLoc = CS->getDebugLoc();
322  BasicBlock *Block = CS.getParent();
323 
324  using namespace ore;
325  OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
326  << NV("Optimization", OptName)
327  << ": devirtualized a call to "
328  << NV("FunctionName", TargetName));
329  }
330 
331  void replaceAndErase(
332  const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
334  Value *New) {
335  if (RemarksEnabled)
336  emitRemark(OptName, TargetName, OREGetter);
337  CS->replaceAllUsesWith(New);
338  if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
339  BranchInst::Create(II->getNormalDest(), CS.getInstruction());
340  II->getUnwindDest()->removePredecessor(II->getParent());
341  }
342  CS->eraseFromParent();
343  // This use is no longer unsafe.
344  if (NumUnsafeUses)
345  --*NumUnsafeUses;
346  }
347 };
348 
349 // Call site information collected for a specific VTableSlot and possibly a list
350 // of constant integer arguments. The grouping by arguments is handled by the
351 // VTableSlotInfo class.
352 struct CallSiteInfo {
353  /// The set of call sites for this slot. Used during regular LTO and the
354  /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
355  /// call sites that appear in the merged module itself); in each of these
356  /// cases we are directly operating on the call sites at the IR level.
357  std::vector<VirtualCallSite> CallSites;
358 
359  /// Whether all call sites represented by this CallSiteInfo, including those
360  /// in summaries, have been devirtualized. This starts off as true because a
361  /// default constructed CallSiteInfo represents no call sites.
362  bool AllCallSitesDevirted = true;
363 
364  // These fields are used during the export phase of ThinLTO and reflect
365  // information collected from function summaries.
366 
367  /// Whether any function summary contains an llvm.assume(llvm.type.test) for
368  /// this slot.
369  bool SummaryHasTypeTestAssumeUsers = false;
370 
371  /// CFI-specific: a vector containing the list of function summaries that use
372  /// the llvm.type.checked.load intrinsic and therefore will require
373  /// resolutions for llvm.type.test in order to implement CFI checks if
374  /// devirtualization was unsuccessful. If devirtualization was successful, the
375  /// pass will clear this vector by calling markDevirt(). If at the end of the
376  /// pass the vector is non-empty, we will need to add a use of llvm.type.test
377  /// to each of the function summaries in the vector.
378  std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
379  std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
380 
381  bool isExported() const {
382  return SummaryHasTypeTestAssumeUsers ||
383  !SummaryTypeCheckedLoadUsers.empty();
384  }
385 
386  void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
387  SummaryTypeCheckedLoadUsers.push_back(FS);
388  AllCallSitesDevirted = false;
389  }
390 
391  void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
392  SummaryTypeTestAssumeUsers.push_back(FS);
393  SummaryHasTypeTestAssumeUsers = true;
394  AllCallSitesDevirted = false;
395  }
396 
397  void markDevirt() {
398  AllCallSitesDevirted = true;
399 
400  // As explained in the comment for SummaryTypeCheckedLoadUsers.
401  SummaryTypeCheckedLoadUsers.clear();
402  }
403 };
404 
405 // Call site information collected for a specific VTableSlot.
406 struct VTableSlotInfo {
407  // The set of call sites which do not have all constant integer arguments
408  // (excluding "this").
409  CallSiteInfo CSInfo;
410 
411  // The set of call sites with all constant integer arguments (excluding
412  // "this"), grouped by argument list.
413  std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
414 
415  void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
416 
417 private:
418  CallSiteInfo &findCallSiteInfo(CallSite CS);
419 };
420 
421 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
422  std::vector<uint64_t> Args;
423  auto *CI = dyn_cast<IntegerType>(CS.getType());
424  if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
425  return CSInfo;
426  for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
427  auto *CI = dyn_cast<ConstantInt>(Arg);
428  if (!CI || CI->getBitWidth() > 64)
429  return CSInfo;
430  Args.push_back(CI->getZExtValue());
431  }
432  return ConstCSInfo[Args];
433 }
434 
435 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
436  unsigned *NumUnsafeUses) {
437  auto &CSI = findCallSiteInfo(CS);
438  CSI.AllCallSitesDevirted = false;
439  CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
440 }
441 
442 struct DevirtModule {
443  Module &M;
446 
447  ModuleSummaryIndex *ExportSummary;
448  const ModuleSummaryIndex *ImportSummary;
449 
450  IntegerType *Int8Ty;
451  PointerType *Int8PtrTy;
453  IntegerType *Int64Ty;
454  IntegerType *IntPtrTy;
455 
456  bool RemarksEnabled;
458 
460 
461  // This map keeps track of the number of "unsafe" uses of a loaded function
462  // pointer. The key is the associated llvm.type.test intrinsic call generated
463  // by this pass. An unsafe use is one that calls the loaded function pointer
464  // directly. Every time we eliminate an unsafe use (for example, by
465  // devirtualizing it or by applying virtual constant propagation), we
466  // decrement the value stored in this map. If a value reaches zero, we can
467  // eliminate the type check by RAUWing the associated llvm.type.test call with
468  // true.
469  std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
470 
471  DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
473  function_ref<DominatorTree &(Function &)> LookupDomTree,
474  ModuleSummaryIndex *ExportSummary,
475  const ModuleSummaryIndex *ImportSummary)
476  : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
477  ExportSummary(ExportSummary), ImportSummary(ImportSummary),
478  Int8Ty(Type::getInt8Ty(M.getContext())),
479  Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
481  Int64Ty(Type::getInt64Ty(M.getContext())),
482  IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
483  RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
484  assert(!(ExportSummary && ImportSummary));
485  }
486 
487  bool areRemarksEnabled();
488 
489  void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
490  void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
491 
492  void buildTypeIdentifierMap(
493  std::vector<VTableBits> &Bits,
494  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
495  bool
496  tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
497  const std::set<TypeMemberInfo> &TypeMemberInfos,
498  uint64_t ByteOffset);
499 
500  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
501  bool &IsExported);
502  bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,
503  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
504  VTableSlotInfo &SlotInfo,
506 
507  void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
508  bool &IsExported);
509  void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
510  VTableSlotInfo &SlotInfo,
511  WholeProgramDevirtResolution *Res, VTableSlot Slot);
512 
513  bool tryEvaluateFunctionsWithArgs(
514  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
516 
517  void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
518  uint64_t TheRetVal);
519  bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
520  CallSiteInfo &CSInfo,
522 
523  // Returns the global symbol name that is used to export information about the
524  // given vtable slot and list of arguments.
525  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
526  StringRef Name);
527 
528  bool shouldExportConstantsAsAbsoluteSymbols();
529 
530  // This function is called during the export phase to create a symbol
531  // definition containing information about the given vtable slot and list of
532  // arguments.
533  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
534  Constant *C);
535  void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
536  uint32_t Const, uint32_t &Storage);
537 
538  // This function is called during the import phase to create a reference to
539  // the symbol definition created during the export phase.
540  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
541  StringRef Name);
542  Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
543  StringRef Name, IntegerType *IntTy,
544  uint32_t Storage);
545 
546  Constant *getMemberAddr(const TypeMemberInfo *M);
547 
548  void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
549  Constant *UniqueMemberAddr);
550  bool tryUniqueRetValOpt(unsigned BitWidth,
551  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
552  CallSiteInfo &CSInfo,
554  VTableSlot Slot, ArrayRef<uint64_t> Args);
555 
556  void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
557  Constant *Byte, Constant *Bit);
558  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
559  VTableSlotInfo &SlotInfo,
560  WholeProgramDevirtResolution *Res, VTableSlot Slot);
561 
562  void rebuildGlobal(VTableBits &B);
563 
564  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
565  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
566 
567  // If we were able to eliminate all unsafe uses for a type checked load,
568  // eliminate the associated type tests by replacing them with true.
569  void removeRedundantTypeTests();
570 
571  bool run();
572 
573  // Lower the module using the action and summary passed as command line
574  // arguments. For testing purposes only.
575  static bool
576  runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
578  function_ref<DominatorTree &(Function &)> LookupDomTree);
579 };
580 
581 struct DevirtIndex {
582  ModuleSummaryIndex &ExportSummary;
583  // The set in which to record GUIDs exported from their module by
584  // devirtualization, used by client to ensure they are not internalized.
585  std::set<GlobalValue::GUID> &ExportedGUIDs;
586  // A map in which to record the information necessary to locate the WPD
587  // resolution for local targets in case they are exported by cross module
588  // importing.
589  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
590 
592 
593  DevirtIndex(
594  ModuleSummaryIndex &ExportSummary,
595  std::set<GlobalValue::GUID> &ExportedGUIDs,
596  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
597  : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
598  LocalWPDTargetsMap(LocalWPDTargetsMap) {}
599 
600  bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
601  const TypeIdCompatibleVtableInfo TIdInfo,
602  uint64_t ByteOffset);
603 
604  bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
605  VTableSlotSummary &SlotSummary,
606  VTableSlotInfo &SlotInfo,
608  std::set<ValueInfo> &DevirtTargets);
609 
610  void run();
611 };
612 
613 struct WholeProgramDevirt : public ModulePass {
614  static char ID;
615 
616  bool UseCommandLine = false;
617 
618  ModuleSummaryIndex *ExportSummary;
619  const ModuleSummaryIndex *ImportSummary;
620 
621  WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
623  }
624 
625  WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
626  const ModuleSummaryIndex *ImportSummary)
627  : ModulePass(ID), ExportSummary(ExportSummary),
628  ImportSummary(ImportSummary) {
630  }
631 
632  bool runOnModule(Module &M) override {
633  if (skipModule(M))
634  return false;
635 
636  // In the new pass manager, we can request the optimization
637  // remark emitter pass on a per-function-basis, which the
638  // OREGetter will do for us.
639  // In the old pass manager, this is harder, so we just build
640  // an optimization remark emitter on the fly, when we need it.
641  std::unique_ptr<OptimizationRemarkEmitter> ORE;
642  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
643  ORE = std::make_unique<OptimizationRemarkEmitter>(F);
644  return *ORE;
645  };
646 
647  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
648  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
649  };
650 
651  if (UseCommandLine)
652  return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter,
653  LookupDomTree);
654 
655  return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree,
656  ExportSummary, ImportSummary)
657  .run();
658  }
659 
660  void getAnalysisUsage(AnalysisUsage &AU) const override {
664  }
665 };
666 
667 } // end anonymous namespace
668 
669 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
670  "Whole program devirtualization", false, false)
675  "Whole program devirtualization", false, false)
676 char WholeProgramDevirt::ID = 0;
677 
678 ModulePass *
680  const ModuleSummaryIndex *ImportSummary) {
681  return new WholeProgramDevirt(ExportSummary, ImportSummary);
682 }
683 
685  ModuleAnalysisManager &AM) {
686  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
687  auto AARGetter = [&](Function &F) -> AAResults & {
688  return FAM.getResult<AAManager>(F);
689  };
690  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
691  return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
692  };
693  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
694  return FAM.getResult<DominatorTreeAnalysis>(F);
695  };
696  if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
697  ImportSummary)
698  .run())
699  return PreservedAnalyses::all();
700  return PreservedAnalyses::none();
701 }
702 
703 namespace llvm {
705  ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
706  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
707  DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
708 }
709 
711  ModuleSummaryIndex &Summary,
712  function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
713  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
714  for (auto &T : LocalWPDTargetsMap) {
715  auto &VI = T.first;
716  // This was enforced earlier during trySingleImplDevirt.
717  assert(VI.getSummaryList().size() == 1 &&
718  "Devirt of local target has more than one copy");
719  auto &S = VI.getSummaryList()[0];
720  if (!isExported(S->modulePath(), VI.getGUID()))
721  continue;
722 
723  // It's been exported by a cross module import.
724  for (auto &SlotSummary : T.second) {
725  auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
726  assert(TIdSum);
727  auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
728  assert(WPDRes != TIdSum->WPDRes.end());
729  WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
730  WPDRes->second.SingleImplName,
731  Summary.getModuleHash(S->modulePath()));
732  }
733  }
734 }
735 
736 } // end namespace llvm
737 
738 bool DevirtModule::runForTesting(
739  Module &M, function_ref<AAResults &(Function &)> AARGetter,
741  function_ref<DominatorTree &(Function &)> LookupDomTree) {
742  ModuleSummaryIndex Summary(/*HaveGVs=*/false);
743 
744  // Handle the command-line summary arguments. This code is for testing
745  // purposes only, so we handle errors directly.
746  if (!ClReadSummary.empty()) {
747  ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
748  ": ");
749  auto ReadSummaryFile =
751 
752  yaml::Input In(ReadSummaryFile->getBuffer());
753  In >> Summary;
754  ExitOnErr(errorCodeToError(In.error()));
755  }
756 
757  bool Changed =
758  DevirtModule(
759  M, AARGetter, OREGetter, LookupDomTree,
760  ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
761  ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
762  .run();
763 
764  if (!ClWriteSummary.empty()) {
765  ExitOnError ExitOnErr(
766  "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
767  std::error_code EC;
769  ExitOnErr(errorCodeToError(EC));
770 
771  yaml::Output Out(OS);
772  Out << Summary;
773  }
774 
775  return Changed;
776 }
777 
778 void DevirtModule::buildTypeIdentifierMap(
779  std::vector<VTableBits> &Bits,
780  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
782  Bits.reserve(M.getGlobalList().size());
784  for (GlobalVariable &GV : M.globals()) {
785  Types.clear();
786  GV.getMetadata(LLVMContext::MD_type, Types);
787  if (GV.isDeclaration() || Types.empty())
788  continue;
789 
790  VTableBits *&BitsPtr = GVToBits[&GV];
791  if (!BitsPtr) {
792  Bits.emplace_back();
793  Bits.back().GV = &GV;
794  Bits.back().ObjectSize =
795  M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
796  BitsPtr = &Bits.back();
797  }
798 
799  for (MDNode *Type : Types) {
800  auto TypeID = Type->getOperand(1).get();
801 
802  uint64_t Offset =
803  cast<ConstantInt>(
804  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
805  ->getZExtValue();
806 
807  TypeIdMap[TypeID].insert({BitsPtr, Offset});
808  }
809  }
810 }
811 
812 bool DevirtModule::tryFindVirtualCallTargets(
813  std::vector<VirtualCallTarget> &TargetsForSlot,
814  const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
815  for (const TypeMemberInfo &TM : TypeMemberInfos) {
816  if (!TM.Bits->GV->isConstant())
817  return false;
818 
820  TM.Offset + ByteOffset, M);
821  if (!Ptr)
822  return false;
823 
824  auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
825  if (!Fn)
826  return false;
827 
828  // We can disregard __cxa_pure_virtual as a possible call target, as
829  // calls to pure virtuals are UB.
830  if (Fn->getName() == "__cxa_pure_virtual")
831  continue;
832 
833  TargetsForSlot.push_back({Fn, &TM});
834  }
835 
836  // Give up if we couldn't find any targets.
837  return !TargetsForSlot.empty();
838 }
839 
840 bool DevirtIndex::tryFindVirtualCallTargets(
841  std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo,
842  uint64_t ByteOffset) {
843  for (const TypeIdOffsetVtableInfo P : TIdInfo) {
844  // VTable initializer should have only one summary, or all copies must be
845  // linkonce/weak ODR.
846  assert(P.VTableVI.getSummaryList().size() == 1 ||
847  llvm::all_of(
848  P.VTableVI.getSummaryList(),
849  [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
850  return GlobalValue::isLinkOnceODRLinkage(Summary->linkage()) ||
851  GlobalValue::isWeakODRLinkage(Summary->linkage());
852  }));
853  const auto *VS = cast<GlobalVarSummary>(P.VTableVI.getSummaryList()[0].get());
854  if (!P.VTableVI.getSummaryList()[0]->isLive())
855  continue;
856  for (auto VTP : VS->vTableFuncs()) {
857  if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
858  continue;
859 
860  TargetsForSlot.push_back(VTP.FuncVI);
861  }
862  }
863 
864  // Give up if we couldn't find any targets.
865  return !TargetsForSlot.empty();
866 }
867 
868 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
869  Constant *TheFn, bool &IsExported) {
870  auto Apply = [&](CallSiteInfo &CSInfo) {
871  for (auto &&VCallSite : CSInfo.CallSites) {
872  if (RemarksEnabled)
873  VCallSite.emitRemark("single-impl",
874  TheFn->stripPointerCasts()->getName(), OREGetter);
875  VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
876  TheFn, VCallSite.CS.getCalledValue()->getType()));
877  // This use is no longer unsafe.
878  if (VCallSite.NumUnsafeUses)
879  --*VCallSite.NumUnsafeUses;
880  }
881  if (CSInfo.isExported())
882  IsExported = true;
883  CSInfo.markDevirt();
884  };
885  Apply(SlotInfo.CSInfo);
886  for (auto &P : SlotInfo.ConstCSInfo)
887  Apply(P.second);
888 }
889 
890 static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) {
891  // We can't add calls if we haven't seen a definition
892  if (Callee.getSummaryList().empty())
893  return false;
894 
895  // Insert calls into the summary index so that the devirtualized targets
896  // are eligible for import.
897  // FIXME: Annotate type tests with hotness. For now, mark these as hot
898  // to better ensure we have the opportunity to inline them.
899  bool IsExported = false;
900  auto &S = Callee.getSummaryList()[0];
901  CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0);
902  auto AddCalls = [&](CallSiteInfo &CSInfo) {
903  for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
904  FS->addCall({Callee, CI});
905  IsExported |= S->modulePath() != FS->modulePath();
906  }
907  for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
908  FS->addCall({Callee, CI});
909  IsExported |= S->modulePath() != FS->modulePath();
910  }
911  };
912  AddCalls(SlotInfo.CSInfo);
913  for (auto &P : SlotInfo.ConstCSInfo)
914  AddCalls(P.second);
915  return IsExported;
916 }
917 
918 bool DevirtModule::trySingleImplDevirt(
919  ModuleSummaryIndex *ExportSummary,
920  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
922  // See if the program contains a single implementation of this virtual
923  // function.
924  Function *TheFn = TargetsForSlot[0].Fn;
925  for (auto &&Target : TargetsForSlot)
926  if (TheFn != Target.Fn)
927  return false;
928 
929  // If so, update each call site to call that implementation directly.
930  if (RemarksEnabled)
931  TargetsForSlot[0].WasDevirt = true;
932 
933  bool IsExported = false;
934  applySingleImplDevirt(SlotInfo, TheFn, IsExported);
935  if (!IsExported)
936  return false;
937 
938  // If the only implementation has local linkage, we must promote to external
939  // to make it visible to thin LTO objects. We can only get here during the
940  // ThinLTO export phase.
941  if (TheFn->hasLocalLinkage()) {
942  std::string NewName = (TheFn->getName() + "$merged").str();
943 
944  // Since we are renaming the function, any comdats with the same name must
945  // also be renamed. This is required when targeting COFF, as the comdat name
946  // must match one of the names of the symbols in the comdat.
947  if (Comdat *C = TheFn->getComdat()) {
948  if (C->getName() == TheFn->getName()) {
949  Comdat *NewC = M.getOrInsertComdat(NewName);
950  NewC->setSelectionKind(C->getSelectionKind());
951  for (GlobalObject &GO : M.global_objects())
952  if (GO.getComdat() == C)
953  GO.setComdat(NewC);
954  }
955  }
956 
959  TheFn->setName(NewName);
960  }
961  if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID()))
962  // Any needed promotion of 'TheFn' has already been done during
963  // LTO unit split, so we can ignore return value of AddCalls.
964  AddCalls(SlotInfo, TheFnVI);
965 
967  Res->SingleImplName = TheFn->getName();
968 
969  return true;
970 }
971 
972 bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
973  VTableSlotSummary &SlotSummary,
974  VTableSlotInfo &SlotInfo,
976  std::set<ValueInfo> &DevirtTargets) {
977  // See if the program contains a single implementation of this virtual
978  // function.
979  auto TheFn = TargetsForSlot[0];
980  for (auto &&Target : TargetsForSlot)
981  if (TheFn != Target)
982  return false;
983 
984  // Don't devirtualize if we don't have target definition.
985  auto Size = TheFn.getSummaryList().size();
986  if (!Size)
987  return false;
988 
989  // If the summary list contains multiple summaries where at least one is
990  // a local, give up, as we won't know which (possibly promoted) name to use.
991  for (auto &S : TheFn.getSummaryList())
992  if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1)
993  return false;
994 
995  // Collect functions devirtualized at least for one call site for stats.
996  if (PrintSummaryDevirt)
997  DevirtTargets.insert(TheFn);
998 
999  auto &S = TheFn.getSummaryList()[0];
1000  bool IsExported = AddCalls(SlotInfo, TheFn);
1001  if (IsExported)
1002  ExportedGUIDs.insert(TheFn.getGUID());
1003 
1004  // Record in summary for use in devirtualization during the ThinLTO import
1005  // step.
1007  if (GlobalValue::isLocalLinkage(S->linkage())) {
1008  if (IsExported)
1009  // If target is a local function and we are exporting it by
1010  // devirtualizing a call in another module, we need to record the
1011  // promoted name.
1013  TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
1014  else {
1015  LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1016  Res->SingleImplName = TheFn.name();
1017  }
1018  } else
1019  Res->SingleImplName = TheFn.name();
1020 
1021  // Name will be empty if this thin link driven off of serialized combined
1022  // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
1023  // legacy LTO API anyway.
1024  assert(!Res->SingleImplName.empty());
1025 
1026  return true;
1027 }
1028 
1029 void DevirtModule::tryICallBranchFunnel(
1030  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1031  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1032  Triple T(M.getTargetTriple());
1033  if (T.getArch() != Triple::x86_64)
1034  return;
1035 
1036  if (TargetsForSlot.size() > ClThreshold)
1037  return;
1038 
1039  bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1040  if (!HasNonDevirt)
1041  for (auto &P : SlotInfo.ConstCSInfo)
1042  if (!P.second.AllCallSitesDevirted) {
1043  HasNonDevirt = true;
1044  break;
1045  }
1046 
1047  if (!HasNonDevirt)
1048  return;
1049 
1050  FunctionType *FT =
1051  FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
1052  Function *JT;
1053  if (isa<MDString>(Slot.TypeID)) {
1056  getGlobalName(Slot, {}, "branch_funnel"), &M);
1057  JT->setVisibility(GlobalValue::HiddenVisibility);
1058  } else {
1061  "branch_funnel", &M);
1062  }
1063  JT->addAttribute(1, Attribute::Nest);
1064 
1065  std::vector<Value *> JTArgs;
1066  JTArgs.push_back(JT->arg_begin());
1067  for (auto &T : TargetsForSlot) {
1068  JTArgs.push_back(getMemberAddr(T.TM));
1069  JTArgs.push_back(T.Fn);
1070  }
1071 
1072  BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
1073  Function *Intr =
1074  Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
1075 
1076  auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
1077  CI->setTailCallKind(CallInst::TCK_MustTail);
1078  ReturnInst::Create(M.getContext(), nullptr, BB);
1079 
1080  bool IsExported = false;
1081  applyICallBranchFunnel(SlotInfo, JT, IsExported);
1082  if (IsExported)
1084 }
1085 
1086 void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1087  Constant *JT, bool &IsExported) {
1088  auto Apply = [&](CallSiteInfo &CSInfo) {
1089  if (CSInfo.isExported())
1090  IsExported = true;
1091  if (CSInfo.AllCallSitesDevirted)
1092  return;
1093  for (auto &&VCallSite : CSInfo.CallSites) {
1094  CallSite CS = VCallSite.CS;
1095 
1096  // Jump tables are only profitable if the retpoline mitigation is enabled.
1097  Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
1098  if (FSAttr.hasAttribute(Attribute::None) ||
1099  !FSAttr.getValueAsString().contains("+retpoline"))
1100  continue;
1101 
1102  if (RemarksEnabled)
1103  VCallSite.emitRemark("branch-funnel",
1104  JT->stripPointerCasts()->getName(), OREGetter);
1105 
1106  // Pass the address of the vtable in the nest register, which is r10 on
1107  // x86_64.
1108  std::vector<Type *> NewArgs;
1109  NewArgs.push_back(Int8PtrTy);
1110  for (Type *T : CS.getFunctionType()->params())
1111  NewArgs.push_back(T);
1112  FunctionType *NewFT =
1114  CS.getFunctionType()->isVarArg());
1115  PointerType *NewFTPtr = PointerType::getUnqual(NewFT);
1116 
1117  IRBuilder<> IRB(CS.getInstruction());
1118  std::vector<Value *> Args;
1119  Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
1120  for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
1121  Args.push_back(CS.getArgOperand(I));
1122 
1123  CallSite NewCS;
1124  if (CS.isCall())
1125  NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(JT, NewFTPtr), Args);
1126  else
1127  NewCS = IRB.CreateInvoke(
1128  NewFT, IRB.CreateBitCast(JT, NewFTPtr),
1129  cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
1130  cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
1131  NewCS.setCallingConv(CS.getCallingConv());
1132 
1134  std::vector<AttributeSet> NewArgAttrs;
1135  NewArgAttrs.push_back(AttributeSet::get(
1137  M.getContext(), Attribute::Nest)}));
1138  for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1139  NewArgAttrs.push_back(Attrs.getParamAttributes(I));
1140  NewCS.setAttributes(
1142  Attrs.getRetAttributes(), NewArgAttrs));
1143 
1144  CS->replaceAllUsesWith(NewCS.getInstruction());
1145  CS->eraseFromParent();
1146 
1147  // This use is no longer unsafe.
1148  if (VCallSite.NumUnsafeUses)
1149  --*VCallSite.NumUnsafeUses;
1150  }
1151  // Don't mark as devirtualized because there may be callers compiled without
1152  // retpoline mitigation, which would mean that they are lowered to
1153  // llvm.type.test and therefore require an llvm.type.test resolution for the
1154  // type identifier.
1155  };
1156  Apply(SlotInfo.CSInfo);
1157  for (auto &P : SlotInfo.ConstCSInfo)
1158  Apply(P.second);
1159 }
1160 
1161 bool DevirtModule::tryEvaluateFunctionsWithArgs(
1162  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1164  // Evaluate each function and store the result in each target's RetVal
1165  // field.
1166  for (VirtualCallTarget &Target : TargetsForSlot) {
1167  if (Target.Fn->arg_size() != Args.size() + 1)
1168  return false;
1169 
1170  Evaluator Eval(M.getDataLayout(), nullptr);
1171  SmallVector<Constant *, 2> EvalArgs;
1172  EvalArgs.push_back(
1173  Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
1174  for (unsigned I = 0; I != Args.size(); ++I) {
1175  auto *ArgTy = dyn_cast<IntegerType>(
1176  Target.Fn->getFunctionType()->getParamType(I + 1));
1177  if (!ArgTy)
1178  return false;
1179  EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
1180  }
1181 
1182  Constant *RetVal;
1183  if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
1184  !isa<ConstantInt>(RetVal))
1185  return false;
1186  Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
1187  }
1188  return true;
1189 }
1190 
1191 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1192  uint64_t TheRetVal) {
1193  for (auto Call : CSInfo.CallSites)
1194  Call.replaceAndErase(
1195  "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1196  ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
1197  CSInfo.markDevirt();
1198 }
1199 
1200 bool DevirtModule::tryUniformRetValOpt(
1201  MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1203  // Uniform return value optimization. If all functions return the same
1204  // constant, replace all calls with that constant.
1205  uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1206  for (const VirtualCallTarget &Target : TargetsForSlot)
1207  if (Target.RetVal != TheRetVal)
1208  return false;
1209 
1210  if (CSInfo.isExported()) {
1212  Res->Info = TheRetVal;
1213  }
1214 
1215  applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1216  if (RemarksEnabled)
1217  for (auto &&Target : TargetsForSlot)
1218  Target.WasDevirt = true;
1219  return true;
1220 }
1221 
1222 std::string DevirtModule::getGlobalName(VTableSlot Slot,
1223  ArrayRef<uint64_t> Args,
1224  StringRef Name) {
1225  std::string FullName = "__typeid_";
1226  raw_string_ostream OS(FullName);
1227  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1228  for (uint64_t Arg : Args)
1229  OS << '_' << Arg;
1230  OS << '_' << Name;
1231  return OS.str();
1232 }
1233 
1234 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1235  Triple T(M.getTargetTriple());
1236  return (T.getArch() == Triple::x86 || T.getArch() == Triple::x86_64) &&
1237  T.getObjectFormat() == Triple::ELF;
1238 }
1239 
1240 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1241  StringRef Name, Constant *C) {
1243  getGlobalName(Slot, Args, Name), C, &M);
1245 }
1246 
1247 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1248  StringRef Name, uint32_t Const,
1249  uint32_t &Storage) {
1250  if (shouldExportConstantsAsAbsoluteSymbols()) {
1251  exportGlobal(
1252  Slot, Args, Name,
1253  ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1254  return;
1255  }
1256 
1257  Storage = Const;
1258 }
1259 
1260 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1261  StringRef Name) {
1262  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
1263  auto *GV = dyn_cast<GlobalVariable>(C);
1264  if (GV)
1266  return C;
1267 }
1268 
1269 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1270  StringRef Name, IntegerType *IntTy,
1271  uint32_t Storage) {
1272  if (!shouldExportConstantsAsAbsoluteSymbols())
1273  return ConstantInt::get(IntTy, Storage);
1274 
1275  Constant *C = importGlobal(Slot, Args, Name);
1276  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1277  C = ConstantExpr::getPtrToInt(C, IntTy);
1278 
1279  // We only need to set metadata if the global is newly created, in which
1280  // case it would not have hidden visibility.
1281  if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1282  return C;
1283 
1284  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1285  auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1286  auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1287  GV->setMetadata(LLVMContext::MD_absolute_symbol,
1288  MDNode::get(M.getContext(), {MinC, MaxC}));
1289  };
1290  unsigned AbsWidth = IntTy->getBitWidth();
1291  if (AbsWidth == IntPtrTy->getBitWidth())
1292  SetAbsRange(~0ull, ~0ull); // Full set.
1293  else
1294  SetAbsRange(0, 1ull << AbsWidth);
1295  return C;
1296 }
1297 
1298 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1299  bool IsOne,
1300  Constant *UniqueMemberAddr) {
1301  for (auto &&Call : CSInfo.CallSites) {
1302  IRBuilder<> B(Call.CS.getInstruction());
1303  Value *Cmp =
1304  B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
1305  B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
1306  Cmp = B.CreateZExt(Cmp, Call.CS->getType());
1307  Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1308  Cmp);
1309  }
1310  CSInfo.markDevirt();
1311 }
1312 
1313 Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1314  Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1315  return ConstantExpr::getGetElementPtr(Int8Ty, C,
1316  ConstantInt::get(Int64Ty, M->Offset));
1317 }
1318 
1319 bool DevirtModule::tryUniqueRetValOpt(
1320  unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1321  CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1322  VTableSlot Slot, ArrayRef<uint64_t> Args) {
1323  // IsOne controls whether we look for a 0 or a 1.
1324  auto tryUniqueRetValOptFor = [&](bool IsOne) {
1325  const TypeMemberInfo *UniqueMember = nullptr;
1326  for (const VirtualCallTarget &Target : TargetsForSlot) {
1327  if (Target.RetVal == (IsOne ? 1 : 0)) {
1328  if (UniqueMember)
1329  return false;
1330  UniqueMember = Target.TM;
1331  }
1332  }
1333 
1334  // We should have found a unique member or bailed out by now. We already
1335  // checked for a uniform return value in tryUniformRetValOpt.
1336  assert(UniqueMember);
1337 
1338  Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1339  if (CSInfo.isExported()) {
1341  Res->Info = IsOne;
1342 
1343  exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1344  }
1345 
1346  // Replace each call with the comparison.
1347  applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1348  UniqueMemberAddr);
1349 
1350  // Update devirtualization statistics for targets.
1351  if (RemarksEnabled)
1352  for (auto &&Target : TargetsForSlot)
1353  Target.WasDevirt = true;
1354 
1355  return true;
1356  };
1357 
1358  if (BitWidth == 1) {
1359  if (tryUniqueRetValOptFor(true))
1360  return true;
1361  if (tryUniqueRetValOptFor(false))
1362  return true;
1363  }
1364  return false;
1365 }
1366 
1367 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1368  Constant *Byte, Constant *Bit) {
1369  for (auto Call : CSInfo.CallSites) {
1370  auto *RetType = cast<IntegerType>(Call.CS.getType());
1371  IRBuilder<> B(Call.CS.getInstruction());
1372  Value *Addr =
1373  B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1374  if (RetType->getBitWidth() == 1) {
1375  Value *Bits = B.CreateLoad(Int8Ty, Addr);
1376  Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1377  auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1378  Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1379  OREGetter, IsBitSet);
1380  } else {
1381  Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1382  Value *Val = B.CreateLoad(RetType, ValAddr);
1383  Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1384  OREGetter, Val);
1385  }
1386  }
1387  CSInfo.markDevirt();
1388 }
1389 
1390 bool DevirtModule::tryVirtualConstProp(
1391  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1392  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1393  // This only works if the function returns an integer.
1394  auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1395  if (!RetType)
1396  return false;
1397  unsigned BitWidth = RetType->getBitWidth();
1398  if (BitWidth > 64)
1399  return false;
1400 
1401  // Make sure that each function is defined, does not access memory, takes at
1402  // least one argument, does not use its first argument (which we assume is
1403  // 'this'), and has the same return type.
1404  //
1405  // Note that we test whether this copy of the function is readnone, rather
1406  // than testing function attributes, which must hold for any copy of the
1407  // function, even a less optimized version substituted at link time. This is
1408  // sound because the virtual constant propagation optimizations effectively
1409  // inline all implementations of the virtual function into each call site,
1410  // rather than using function attributes to perform local optimization.
1411  for (VirtualCallTarget &Target : TargetsForSlot) {
1412  if (Target.Fn->isDeclaration() ||
1413  computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1414  MAK_ReadNone ||
1415  Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1416  Target.Fn->getReturnType() != RetType)
1417  return false;
1418  }
1419 
1420  for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1421  if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1422  continue;
1423 
1424  WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1425  if (Res)
1426  ResByArg = &Res->ResByArg[CSByConstantArg.first];
1427 
1428  if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1429  continue;
1430 
1431  if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1432  ResByArg, Slot, CSByConstantArg.first))
1433  continue;
1434 
1435  // Find an allocation offset in bits in all vtables associated with the
1436  // type.
1437  uint64_t AllocBefore =
1438  findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1439  uint64_t AllocAfter =
1440  findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1441 
1442  // Calculate the total amount of padding needed to store a value at both
1443  // ends of the object.
1444  uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1445  for (auto &&Target : TargetsForSlot) {
1446  TotalPaddingBefore += std::max<int64_t>(
1447  (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1448  TotalPaddingAfter += std::max<int64_t>(
1449  (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1450  }
1451 
1452  // If the amount of padding is too large, give up.
1453  // FIXME: do something smarter here.
1454  if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1455  continue;
1456 
1457  // Calculate the offset to the value as a (possibly negative) byte offset
1458  // and (if applicable) a bit offset, and store the values in the targets.
1459  int64_t OffsetByte;
1460  uint64_t OffsetBit;
1461  if (TotalPaddingBefore <= TotalPaddingAfter)
1462  setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1463  OffsetBit);
1464  else
1465  setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1466  OffsetBit);
1467 
1468  if (RemarksEnabled)
1469  for (auto &&Target : TargetsForSlot)
1470  Target.WasDevirt = true;
1471 
1472 
1473  if (CSByConstantArg.second.isExported()) {
1475  exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1476  ResByArg->Byte);
1477  exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1478  ResByArg->Bit);
1479  }
1480 
1481  // Rewrite each call to a load from OffsetByte/OffsetBit.
1482  Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1483  Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1484  applyVirtualConstProp(CSByConstantArg.second,
1485  TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1486  }
1487  return true;
1488 }
1489 
1490 void DevirtModule::rebuildGlobal(VTableBits &B) {
1491  if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1492  return;
1493 
1494  // Align the before byte array to the global's minimum alignment so that we
1495  // don't break any alignment requirements on the global.
1496  MaybeAlign Alignment(B.GV->getAlignment());
1497  if (!Alignment)
1498  Alignment =
1499  Align(M.getDataLayout().getABITypeAlignment(B.GV->getValueType()));
1500  B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment));
1501 
1502  // Before was stored in reverse order; flip it now.
1503  for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1504  std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1505 
1506  // Build an anonymous global containing the before bytes, followed by the
1507  // original initializer, followed by the after bytes.
1508  auto NewInit = ConstantStruct::getAnon(
1509  {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1510  B.GV->getInitializer(),
1511  ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1512  auto NewGV =
1513  new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1514  GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1515  NewGV->setSection(B.GV->getSection());
1516  NewGV->setComdat(B.GV->getComdat());
1517  NewGV->setAlignment(MaybeAlign(B.GV->getAlignment()));
1518 
1519  // Copy the original vtable's metadata to the anonymous global, adjusting
1520  // offsets as required.
1521  NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1522 
1523  // Build an alias named after the original global, pointing at the second
1524  // element (the original initializer).
1525  auto Alias = GlobalAlias::create(
1526  B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1528  NewInit->getType(), NewGV,
1530  ConstantInt::get(Int32Ty, 1)}),
1531  &M);
1532  Alias->setVisibility(B.GV->getVisibility());
1533  Alias->takeName(B.GV);
1534 
1535  B.GV->replaceAllUsesWith(Alias);
1536  B.GV->eraseFromParent();
1537 }
1538 
1539 bool DevirtModule::areRemarksEnabled() {
1540  const auto &FL = M.getFunctionList();
1541  for (const Function &Fn : FL) {
1542  const auto &BBL = Fn.getBasicBlockList();
1543  if (BBL.empty())
1544  continue;
1545  auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1546  return DI.isEnabled();
1547  }
1548  return false;
1549 }
1550 
1551 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1552  Function *AssumeFunc) {
1553  // Find all virtual calls via a virtual table pointer %p under an assumption
1554  // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1555  // points to a member of the type identifier %md. Group calls by (type ID,
1556  // offset) pair (effectively the identity of the virtual function) and store
1557  // to CallSlots.
1558  DenseSet<CallSite> SeenCallSites;
1559  for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1560  I != E;) {
1561  auto CI = dyn_cast<CallInst>(I->getUser());
1562  ++I;
1563  if (!CI)
1564  continue;
1565 
1566  // Search for virtual calls based on %p and add them to DevirtCalls.
1567  SmallVector<DevirtCallSite, 1> DevirtCalls;
1569  auto &DT = LookupDomTree(*CI->getFunction());
1570  findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1571 
1572  // If we found any, add them to CallSlots.
1573  if (!Assumes.empty()) {
1574  Metadata *TypeId =
1575  cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1576  Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1577  for (DevirtCallSite Call : DevirtCalls) {
1578  // Only add this CallSite if we haven't seen it before. The vtable
1579  // pointer may have been CSE'd with pointers from other call sites,
1580  // and we don't want to process call sites multiple times. We can't
1581  // just skip the vtable Ptr if it has been seen before, however, since
1582  // it may be shared by type tests that dominate different calls.
1583  if (SeenCallSites.insert(Call.CS).second)
1584  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1585  }
1586  }
1587 
1588  // We no longer need the assumes or the type test.
1589  for (auto Assume : Assumes)
1590  Assume->eraseFromParent();
1591  // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1592  // may use the vtable argument later.
1593  if (CI->use_empty())
1594  CI->eraseFromParent();
1595  }
1596 }
1597 
1598 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1599  Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1600 
1601  for (auto I = TypeCheckedLoadFunc->use_begin(),
1602  E = TypeCheckedLoadFunc->use_end();
1603  I != E;) {
1604  auto CI = dyn_cast<CallInst>(I->getUser());
1605  ++I;
1606  if (!CI)
1607  continue;
1608 
1609  Value *Ptr = CI->getArgOperand(0);
1610  Value *Offset = CI->getArgOperand(1);
1611  Value *TypeIdValue = CI->getArgOperand(2);
1612  Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1613 
1614  SmallVector<DevirtCallSite, 1> DevirtCalls;
1615  SmallVector<Instruction *, 1> LoadedPtrs;
1617  bool HasNonCallUses = false;
1618  auto &DT = LookupDomTree(*CI->getFunction());
1619  findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1620  HasNonCallUses, CI, DT);
1621 
1622  // Start by generating "pessimistic" code that explicitly loads the function
1623  // pointer from the vtable and performs the type check. If possible, we will
1624  // eliminate the load and the type check later.
1625 
1626  // If possible, only generate the load at the point where it is used.
1627  // This helps avoid unnecessary spills.
1628  IRBuilder<> LoadB(
1629  (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1630  Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1631  Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1632  Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1633 
1634  for (Instruction *LoadedPtr : LoadedPtrs) {
1635  LoadedPtr->replaceAllUsesWith(LoadedValue);
1636  LoadedPtr->eraseFromParent();
1637  }
1638 
1639  // Likewise for the type test.
1640  IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1641  CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1642 
1643  for (Instruction *Pred : Preds) {
1644  Pred->replaceAllUsesWith(TypeTestCall);
1645  Pred->eraseFromParent();
1646  }
1647 
1648  // We have already erased any extractvalue instructions that refer to the
1649  // intrinsic call, but the intrinsic may have other non-extractvalue uses
1650  // (although this is unlikely). In that case, explicitly build a pair and
1651  // RAUW it.
1652  if (!CI->use_empty()) {
1653  Value *Pair = UndefValue::get(CI->getType());
1654  IRBuilder<> B(CI);
1655  Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1656  Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1657  CI->replaceAllUsesWith(Pair);
1658  }
1659 
1660  // The number of unsafe uses is initially the number of uses.
1661  auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1662  NumUnsafeUses = DevirtCalls.size();
1663 
1664  // If the function pointer has a non-call user, we cannot eliminate the type
1665  // check, as one of those users may eventually call the pointer. Increment
1666  // the unsafe use count to make sure it cannot reach zero.
1667  if (HasNonCallUses)
1668  ++NumUnsafeUses;
1669  for (DevirtCallSite Call : DevirtCalls) {
1670  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1671  &NumUnsafeUses);
1672  }
1673 
1674  CI->eraseFromParent();
1675  }
1676 }
1677 
1678 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1679  auto *TypeId = dyn_cast<MDString>(Slot.TypeID);
1680  if (!TypeId)
1681  return;
1682  const TypeIdSummary *TidSummary =
1683  ImportSummary->getTypeIdSummary(TypeId->getString());
1684  if (!TidSummary)
1685  return;
1686  auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1687  if (ResI == TidSummary->WPDRes.end())
1688  return;
1689  const WholeProgramDevirtResolution &Res = ResI->second;
1690 
1692  assert(!Res.SingleImplName.empty());
1693  // The type of the function in the declaration is irrelevant because every
1694  // call site will cast it to the correct type.
1695  Constant *SingleImpl =
1696  cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,
1697  Type::getVoidTy(M.getContext()))
1698  .getCallee());
1699 
1700  // This is the import phase so we should not be exporting anything.
1701  bool IsExported = false;
1702  applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1703  assert(!IsExported);
1704  }
1705 
1706  for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1707  auto I = Res.ResByArg.find(CSByConstantArg.first);
1708  if (I == Res.ResByArg.end())
1709  continue;
1710  auto &ResByArg = I->second;
1711  // FIXME: We should figure out what to do about the "function name" argument
1712  // to the apply* functions, as the function names are unavailable during the
1713  // importing phase. For now we just pass the empty string. This does not
1714  // impact correctness because the function names are just used for remarks.
1715  switch (ResByArg.TheKind) {
1717  applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1718  break;
1720  Constant *UniqueMemberAddr =
1721  importGlobal(Slot, CSByConstantArg.first, "unique_member");
1722  applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1723  UniqueMemberAddr);
1724  break;
1725  }
1727  Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1728  Int32Ty, ResByArg.Byte);
1729  Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1730  ResByArg.Bit);
1731  applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1732  break;
1733  }
1734  default:
1735  break;
1736  }
1737  }
1738 
1740  // The type of the function is irrelevant, because it's bitcast at calls
1741  // anyhow.
1742  Constant *JT = cast<Constant>(
1743  M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
1744  Type::getVoidTy(M.getContext()))
1745  .getCallee());
1746  bool IsExported = false;
1747  applyICallBranchFunnel(SlotInfo, JT, IsExported);
1748  assert(!IsExported);
1749  }
1750 }
1751 
1752 void DevirtModule::removeRedundantTypeTests() {
1753  auto True = ConstantInt::getTrue(M.getContext());
1754  for (auto &&U : NumUnsafeUsesForTypeTest) {
1755  if (U.second == 0) {
1756  U.first->replaceAllUsesWith(True);
1757  U.first->eraseFromParent();
1758  }
1759  }
1760 }
1761 
1762 bool DevirtModule::run() {
1763  // If only some of the modules were split, we cannot correctly perform
1764  // this transformation. We already checked for the presense of type tests
1765  // with partially split modules during the thin link, and would have emitted
1766  // an error if any were found, so here we can simply return.
1767  if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1768  (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
1769  return false;
1770 
1771  Function *TypeTestFunc =
1772  M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1773  Function *TypeCheckedLoadFunc =
1774  M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1775  Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1776 
1777  // Normally if there are no users of the devirtualization intrinsics in the
1778  // module, this pass has nothing to do. But if we are exporting, we also need
1779  // to handle any users that appear only in the function summaries.
1780  if (!ExportSummary &&
1781  (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1782  AssumeFunc->use_empty()) &&
1783  (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1784  return false;
1785 
1786  if (TypeTestFunc && AssumeFunc)
1787  scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1788 
1789  if (TypeCheckedLoadFunc)
1790  scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1791 
1792  if (ImportSummary) {
1793  for (auto &S : CallSlots)
1794  importResolution(S.first, S.second);
1795 
1796  removeRedundantTypeTests();
1797 
1798  // The rest of the code is only necessary when exporting or during regular
1799  // LTO, so we are done.
1800  return true;
1801  }
1802 
1803  // Rebuild type metadata into a map for easy lookup.
1804  std::vector<VTableBits> Bits;
1806  buildTypeIdentifierMap(Bits, TypeIdMap);
1807  if (TypeIdMap.empty())
1808  return true;
1809 
1810  // Collect information from summary about which calls to try to devirtualize.
1811  if (ExportSummary) {
1813  for (auto &P : TypeIdMap) {
1814  if (auto *TypeId = dyn_cast<MDString>(P.first))
1815  MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1816  TypeId);
1817  }
1818 
1819  for (auto &P : *ExportSummary) {
1820  for (auto &S : P.second.SummaryList) {
1821  auto *FS = dyn_cast<FunctionSummary>(S.get());
1822  if (!FS)
1823  continue;
1824  // FIXME: Only add live functions.
1825  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1826  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1827  CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
1828  }
1829  }
1830  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1831  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1832  CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1833  }
1834  }
1835  for (const FunctionSummary::ConstVCall &VC :
1836  FS->type_test_assume_const_vcalls()) {
1837  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1838  CallSlots[{MD, VC.VFunc.Offset}]
1839  .ConstCSInfo[VC.Args]
1840  .addSummaryTypeTestAssumeUser(FS);
1841  }
1842  }
1843  for (const FunctionSummary::ConstVCall &VC :
1844  FS->type_checked_load_const_vcalls()) {
1845  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1846  CallSlots[{MD, VC.VFunc.Offset}]
1847  .ConstCSInfo[VC.Args]
1848  .addSummaryTypeCheckedLoadUser(FS);
1849  }
1850  }
1851  }
1852  }
1853  }
1854 
1855  // For each (type, offset) pair:
1856  bool DidVirtualConstProp = false;
1857  std::map<std::string, Function*> DevirtTargets;
1858  for (auto &S : CallSlots) {
1859  // Search each of the members of the type identifier for the virtual
1860  // function implementation at offset S.first.ByteOffset, and add to
1861  // TargetsForSlot.
1862  std::vector<VirtualCallTarget> TargetsForSlot;
1863  if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
1864  S.first.ByteOffset)) {
1865  WholeProgramDevirtResolution *Res = nullptr;
1866  if (ExportSummary && isa<MDString>(S.first.TypeID))
1867  Res = &ExportSummary
1869  cast<MDString>(S.first.TypeID)->getString())
1870  .WPDRes[S.first.ByteOffset];
1871 
1872  if (!trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res)) {
1873  DidVirtualConstProp |=
1874  tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
1875 
1876  tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
1877  }
1878 
1879  // Collect functions devirtualized at least for one call site for stats.
1880  if (RemarksEnabled)
1881  for (const auto &T : TargetsForSlot)
1882  if (T.WasDevirt)
1883  DevirtTargets[T.Fn->getName()] = T.Fn;
1884  }
1885 
1886  // CFI-specific: if we are exporting and any llvm.type.checked.load
1887  // intrinsics were *not* devirtualized, we need to add the resulting
1888  // llvm.type.test intrinsics to the function summaries so that the
1889  // LowerTypeTests pass will export them.
1890  if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1891  auto GUID =
1892  GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1893  for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1894  FS->addTypeTest(GUID);
1895  for (auto &CCS : S.second.ConstCSInfo)
1896  for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1897  FS->addTypeTest(GUID);
1898  }
1899  }
1900 
1901  if (RemarksEnabled) {
1902  // Generate remarks for each devirtualized function.
1903  for (const auto &DT : DevirtTargets) {
1904  Function *F = DT.second;
1905 
1906  using namespace ore;
1907  OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
1908  << "devirtualized "
1909  << NV("FunctionName", DT.first));
1910  }
1911  }
1912 
1913  removeRedundantTypeTests();
1914 
1915  // Rebuild each global we touched as part of virtual constant propagation to
1916  // include the before and after bytes.
1917  if (DidVirtualConstProp)
1918  for (VTableBits &B : Bits)
1919  rebuildGlobal(B);
1920 
1921  // We have lowered or deleted the type checked load intrinsics, so we no
1922  // longer have enough information to reason about the liveness of virtual
1923  // function pointers in GlobalDCE.
1924  for (GlobalVariable &GV : M.globals())
1925  GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1926 
1927  return true;
1928 }
1929 
1930 void DevirtIndex::run() {
1931  if (ExportSummary.typeIdCompatibleVtableMap().empty())
1932  return;
1933 
1935  for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
1936  NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
1937  }
1938 
1939  // Collect information from summary about which calls to try to devirtualize.
1940  for (auto &P : ExportSummary) {
1941  for (auto &S : P.second.SummaryList) {
1942  auto *FS = dyn_cast<FunctionSummary>(S.get());
1943  if (!FS)
1944  continue;
1945  // FIXME: Only add live functions.
1946  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1947  for (StringRef Name : NameByGUID[VF.GUID]) {
1948  CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
1949  }
1950  }
1951  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1952  for (StringRef Name : NameByGUID[VF.GUID]) {
1953  CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1954  }
1955  }
1956  for (const FunctionSummary::ConstVCall &VC :
1957  FS->type_test_assume_const_vcalls()) {
1958  for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
1959  CallSlots[{Name, VC.VFunc.Offset}]
1960  .ConstCSInfo[VC.Args]
1961  .addSummaryTypeTestAssumeUser(FS);
1962  }
1963  }
1964  for (const FunctionSummary::ConstVCall &VC :
1965  FS->type_checked_load_const_vcalls()) {
1966  for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
1967  CallSlots[{Name, VC.VFunc.Offset}]
1968  .ConstCSInfo[VC.Args]
1969  .addSummaryTypeCheckedLoadUser(FS);
1970  }
1971  }
1972  }
1973  }
1974 
1975  std::set<ValueInfo> DevirtTargets;
1976  // For each (type, offset) pair:
1977  for (auto &S : CallSlots) {
1978  // Search each of the members of the type identifier for the virtual
1979  // function implementation at offset S.first.ByteOffset, and add to
1980  // TargetsForSlot.
1981  std::vector<ValueInfo> TargetsForSlot;
1982  auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
1983  assert(TidSummary);
1984  if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
1985  S.first.ByteOffset)) {
1987  &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
1988  .WPDRes[S.first.ByteOffset];
1989 
1990  if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
1991  DevirtTargets))
1992  continue;
1993  }
1994  }
1995 
1996  // Optionally have the thin link print message for each devirtualized
1997  // function.
1998  if (PrintSummaryDevirt)
1999  for (const auto &DT : DevirtTargets)
2000  errs() << "Devirtualized call to " << DT << "\n";
2001 
2002  return;
2003 }
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:242
IterTy arg_end() const
Definition: CallSite.h:588
uint64_t CallInst * C
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:109
unsigned getAlignment() const
Definition: GlobalObject.h:73
use_iterator use_end()
Definition: Value.h:367
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
const std::string & getTargetTriple() const
Get the target triple which is a string describing the target host.
Definition: Module.h:240
std::vector< TypeIdOffsetVtableInfo > TypeIdCompatibleVtableInfo
List of vtable definitions decorated by a particular type identifier, and their corresponding offsets...
bool empty() const
Definition: Function.h:686
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
Whole program devirtualization
static unsigned getHashValue(const VTableSlot &I)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:502
IterTy arg_begin() const
Definition: CallSite.h:584
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
LoadInst * CreateLoad(Type *Ty, Value *Ptr, const char *Name)
Provided to resolve &#39;CreateLoad(Ty, Ptr, "...")&#39; correctly, instead of converting the string to &#39;bool...
Definition: IRBuilder.h:1574
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant *> IdxList, bool InBounds=false, Optional< unsigned > InRangeIndex=None, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1153
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
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 ...
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
void push_back(const T &Elt)
Definition: SmallVector.h:211
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Helper for check-and-exit error handling.
Definition: Error.h:1293
void initializeWholeProgramDevirtPass(PassRegistry &)
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:104
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1791
uint64_t Info
Additional information for the resolution:
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
void setCallingConv(CallingConv::ID CC)
Set the calling convention of the call.
Definition: CallSite.h:324
Externally visible function.
Definition: GlobalValue.h:48
const std::map< std::string, TypeIdCompatibleVtableInfo > & typeIdCompatibleVtableMap() const
static cl::opt< unsigned > ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden, cl::init(10), cl::ZeroOrMore, cl::desc("Maximum number of call targets per " "call site to enable branch funnels"))
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1165
A debug info location.
Definition: DebugLoc.h:33
Metadata node.
Definition: Metadata.h:863
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
const GlobalListType & getGlobalList() const
Get the Module&#39;s list of global variables (constant).
Definition: Module.h:524
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:181
Hexagon Common GEP
MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
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 ...
void setAfterReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
std::map< uint64_t, WholeProgramDevirtResolution > WPDRes
Mapping from byte offset to whole-program devirt resolution for that (typeid, byte offset) pair...
static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee)
FunctionType * getFunctionType() const
Definition: CallSite.h:328
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:330
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
CallingConv::ID getCallingConv() const
Get the calling convention of the call.
Definition: CallSite.h:320
Export information to summary.
const char * getName() const
getName - Get the target name.
iterator_range< global_object_iterator > global_objects()
Definition: Module.h:662
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:156
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...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:640
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
When retpoline mitigation is enabled, use a branch funnel that is defined in the merged module...
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
The returned value is undefined.
Definition: MathExtras.h:46
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
static bool isEqual(const VTableSlotSummary &LHS, const VTableSlotSummary &RHS)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash)
Convenience method for creating a promoted global name for the given value name of a local...
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
TypeID
Definitions of all of the base types for the Type system.
Definition: Type.h:55
No attributes have been set.
Definition: Attributes.h:72
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
unsigned Intr
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
Type * getType() const
Return the type of the instruction that generated this call site.
Definition: CallSite.h:272
static bool isLinkOnceODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:306
static bool isEqual(const VTableSlot &LHS, const VTableSlot &RHS)
enum llvm::WholeProgramDevirtResolution::Kind TheKind
InstrTy * getInstruction() const
Definition: CallSite.h:96
Class to represent function types.
Definition: DerivedTypes.h:108
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1962
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
bool isVarArg() const
Definition: DerivedTypes.h:128
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
TypeIdSummary & getOrInsertTypeIdSummary(StringRef TypeId)
Return an existing or new TypeIdSummary entry for TypeId.
LinkageTypes getLinkage() const
Definition: GlobalValue.h:460
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:71
Class to hold module path string table and global value map, and encapsulate methods for operating on...
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:409
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1093
The file should be opened in text mode on platforms that make this distinction.
Definition: FileSystem.h:767
Class to represent pointers.
Definition: DerivedTypes.h:575
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1804
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space...
Definition: DataLayout.cpp:769
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
Definition: Attributes.cpp:235
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:135
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
Definition: Attributes.cpp:589
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:236
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:290
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.
unsigned getNumArgOperands() const
Definition: CallSite.h:303
Import information from summary.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static bool isWeakODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:315
A call site that could be devirtualized.
static Optional< bool > isBigEndian(const SmallVector< int64_t, 4 > &ByteOffsets, int64_t FirstOffset)
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
Definition: Error.cpp:87
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:652
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define DEBUG_TYPE
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:337
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:487
A manager for alias analyses.
Class to accumulate and hold information about a callee.
Diagnostic information for applied optimization remarks.
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Globals.cpp:384
INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt", "Whole program devirtualization", false, false) INITIALIZE_PASS_END(WholeProgramDevirt
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:135
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
Definition: Error.h:1137
Represent the analysis usage information of a pass.
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
Definition: Function.cpp:381
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:165
Type::TypeID TypeID
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:301
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:103
const ModuleHash & getModuleHash(const StringRef ModPath) const
Get the module SHA1 hash recorded for the given module path.
LLVM_NODISCARD bool contains(StringRef Other) const
Return true if the given string is a substring of *this, and false otherwise.
Definition: StringRef.h:446
Class to represent integer types.
Definition: DerivedTypes.h:40
enum llvm::WholeProgramDevirtResolution::ByArg::Kind TheKind
static GUID getGUID(StringRef GlobalName)
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:506
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
const Constant * stripPointerCasts() const
Definition: Constant.h:183
Comdat * getOrInsertComdat(StringRef Name)
Return the Comdat in the module with the specified name.
Definition: Module.cpp:482
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:529
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
size_t size() const
Definition: SmallVector.h:52
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:224
bool isEnabled() const override
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:519
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:43
An "identifier" for a virtual function.
bool arg_empty() const
Definition: CallSite.h:225
Struct that holds a reference to a particular GUID in a global value summary.
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:38
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1675
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the generic address space (address sp...
Definition: DerivedTypes.h:590
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void setSelectionKind(SelectionKind Val)
Definition: Comdat.h:45
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:117
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Single implementation devirtualization.
Type * getReturnType() const
Definition: DerivedTypes.h:129
unsigned getProgramAddressSpace() const
Definition: DataLayout.h:287
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:653
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:609
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
wholeprogramdevirt
Target - Wrapper for Target specific information.
unsigned getNumAttrSets() const
A specification for a virtual function call with all constant integer arguments.
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:101
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:510
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:178
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:627
const Comdat * getComdat() const
Definition: GlobalObject.h:120
ModulePass * createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary)
This pass implements whole-program devirtualization using type metadata.
use_iterator use_begin()
Definition: Value.h:359
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:163
std::map< std::vector< uint64_t >, ByArg > ResByArg
Resolutions for calls with all constant integer arguments (excluding the first argument, "this"), where the key is the argument vector.
Constant * getOrInsertGlobal(StringRef Name, Type *Ty, function_ref< GlobalVariable *()> CreateGlobalCallback)
Look up the specified global in the module symbol table.
Definition: Module.cpp:204
void updateIndexWPDForExports(ModuleSummaryIndex &Summary, function_ref< bool(StringRef, GlobalValue::GUID)> 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...
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:384
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:180
uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:220
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1778
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
Type * getValueType() const
Definition: GlobalValue.h:279
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:657
uint32_t Size
Definition: Profile.cpp:46
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2238
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:80
Provides passes for computing function attributes based on interprocedural analyses.
Function summary information to aid decisions and implementation of importing.
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, int64_t FileSize=-1, bool RequiresNullTerminator=true, bool IsVolatile=false)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful, otherwise returning null.
bool isCall() const
Return true if a CallInst is enclosed.
Definition: CallSite.h:87
static cl::opt< bool > PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::desc("Print index-based devirtualization messages"))
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)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:503
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:74
static const Function * getParent(const Value *V)
AttributeSet getFnAttributes() const
The function attributes are returned.
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:333
static Constant * getAnon(ArrayRef< Constant *> V, bool Packed=false)
Return an anonymous struct that has the specified elements.
Definition: Constants.h:468
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:702
iterator_range< global_iterator > globals()
Definition: Module.h:587
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A single uniqued string.
Definition: Metadata.h:603
static cl::opt< std::string > ClReadSummary("wholeprogramdevirt-read-summary", cl::desc("Read summary from given YAML file before running pass"), cl::Hidden)
static cl::opt< std::string > ClWriteSummary("wholeprogramdevirt-write-summary", cl::desc("Write summary to given YAML file after running pass"), cl::Hidden)
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
Root of the metadata hierarchy.
Definition: Metadata.h:57
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:178
void setSection(StringRef S)
Change the section for this global.
Definition: Globals.cpp:215
The optimization diagnostic interface.
static unsigned getHashValue(const VTableSlotSummary &I)
bool use_empty() const
Definition: Value.h:343
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M)
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
Definition: Globals.cpp:485
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
The following data structures summarize type metadata information.
ValTy * getArgOperand(unsigned i) const
Definition: CallSite.h:307
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:970
IntegerType * Int32Ty
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:275