LLVM  9.0.0svn
WholeProgramDevirt.cpp
Go to the documentation of this file.
1 //===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass implements whole program optimization of virtual calls in cases
11 // where we know (via !type metadata) that the list of callees is fixed. This
12 // includes the following:
13 // - Single implementation devirtualization: if a virtual call has a single
14 // possible callee, replace all calls with a direct call to that callee.
15 // - Virtual constant propagation: if the virtual function's return type is an
16 // integer <=64 bits and all possible callees are readnone, for each class and
17 // each list of constant arguments: evaluate the function, store the return
18 // value alongside the virtual table, and rewrite each virtual call as a load
19 // from the virtual table.
20 // - Uniform return value optimization: if the conditions for virtual constant
21 // propagation hold and each function returns the same constant value, replace
22 // each virtual call with that constant.
23 // - Unique return value optimization for i1 return values: if the conditions
24 // for virtual constant propagation hold and a single vtable's function
25 // returns 0, or a single vtable's function returns 1, replace each virtual
26 // call with a comparison of the vptr against that vtable's address.
27 //
28 // This pass is intended to be used during the regular and thin LTO pipelines.
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). During
33 // ThinLTO, the pass operates in two phases:
34 // - Export phase: this is run during the thin link over a single merged module
35 // that contains all vtables with !type metadata that participate in the link.
36 // The pass computes a resolution for each virtual call and stores it in the
37 // type identifier summary.
38 // - Import phase: this is run during the thin backends over the individual
39 // modules. The pass applies the resolutions previously computed during the
40 // import phase to each eligible virtual call.
41 //
42 //===----------------------------------------------------------------------===//
43 
45 #include "llvm/ADT/ArrayRef.h"
46 #include "llvm/ADT/DenseMap.h"
47 #include "llvm/ADT/DenseMapInfo.h"
48 #include "llvm/ADT/DenseSet.h"
49 #include "llvm/ADT/MapVector.h"
50 #include "llvm/ADT/SmallVector.h"
56 #include "llvm/IR/CallSite.h"
57 #include "llvm/IR/Constants.h"
58 #include "llvm/IR/DataLayout.h"
59 #include "llvm/IR/DebugLoc.h"
60 #include "llvm/IR/DerivedTypes.h"
61 #include "llvm/IR/Dominators.h"
62 #include "llvm/IR/Function.h"
63 #include "llvm/IR/GlobalAlias.h"
64 #include "llvm/IR/GlobalVariable.h"
65 #include "llvm/IR/IRBuilder.h"
66 #include "llvm/IR/InstrTypes.h"
67 #include "llvm/IR/Instruction.h"
68 #include "llvm/IR/Instructions.h"
69 #include "llvm/IR/Intrinsics.h"
70 #include "llvm/IR/LLVMContext.h"
71 #include "llvm/IR/Metadata.h"
72 #include "llvm/IR/Module.h"
74 #include "llvm/Pass.h"
75 #include "llvm/PassRegistry.h"
76 #include "llvm/PassSupport.h"
77 #include "llvm/Support/Casting.h"
78 #include "llvm/Support/Error.h"
81 #include "llvm/Transforms/IPO.h"
84 #include <algorithm>
85 #include <cstddef>
86 #include <map>
87 #include <set>
88 #include <string>
89 
90 using namespace llvm;
91 using namespace wholeprogramdevirt;
92 
93 #define DEBUG_TYPE "wholeprogramdevirt"
94 
96  "wholeprogramdevirt-summary-action",
97  cl::desc("What to do with the summary when running this pass"),
98  cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
100  "Import typeid resolutions from summary and globals"),
102  "Export typeid resolutions to summary and globals")),
103  cl::Hidden);
104 
106  "wholeprogramdevirt-read-summary",
107  cl::desc("Read summary from given YAML file before running pass"),
108  cl::Hidden);
109 
111  "wholeprogramdevirt-write-summary",
112  cl::desc("Write summary to given YAML file after running pass"),
113  cl::Hidden);
114 
115 static cl::opt<unsigned>
116  ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
118  cl::desc("Maximum number of call targets per "
119  "call site to enable branch funnels"));
120 
121 // Find the minimum offset that we may store a value of size Size bits at. If
122 // IsAfter is set, look for an offset before the object, otherwise look for an
123 // offset after the object.
124 uint64_t
126  bool IsAfter, uint64_t Size) {
127  // Find a minimum offset taking into account only vtable sizes.
128  uint64_t MinByte = 0;
129  for (const VirtualCallTarget &Target : Targets) {
130  if (IsAfter)
131  MinByte = std::max(MinByte, Target.minAfterBytes());
132  else
133  MinByte = std::max(MinByte, Target.minBeforeBytes());
134  }
135 
136  // Build a vector of arrays of bytes covering, for each target, a slice of the
137  // used region (see AccumBitVector::BytesUsed in
138  // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
139  // this aligns the used regions to start at MinByte.
140  //
141  // In this example, A, B and C are vtables, # is a byte already allocated for
142  // a virtual function pointer, AAAA... (etc.) are the used regions for the
143  // vtables and Offset(X) is the value computed for the Offset variable below
144  // for X.
145  //
146  // Offset(A)
147  // | |
148  // |MinByte
149  // A: ################AAAAAAAA|AAAAAAAA
150  // B: ########BBBBBBBBBBBBBBBB|BBBB
151  // C: ########################|CCCCCCCCCCCCCCCC
152  // | Offset(B) |
153  //
154  // This code produces the slices of A, B and C that appear after the divider
155  // at MinByte.
156  std::vector<ArrayRef<uint8_t>> Used;
157  for (const VirtualCallTarget &Target : Targets) {
158  ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
159  : Target.TM->Bits->Before.BytesUsed;
160  uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
161  : MinByte - Target.minBeforeBytes();
162 
163  // Disregard used regions that are smaller than Offset. These are
164  // effectively all-free regions that do not need to be checked.
165  if (VTUsed.size() > Offset)
166  Used.push_back(VTUsed.slice(Offset));
167  }
168 
169  if (Size == 1) {
170  // Find a free bit in each member of Used.
171  for (unsigned I = 0;; ++I) {
172  uint8_t BitsUsed = 0;
173  for (auto &&B : Used)
174  if (I < B.size())
175  BitsUsed |= B[I];
176  if (BitsUsed != 0xff)
177  return (MinByte + I) * 8 +
178  countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
179  }
180  } else {
181  // Find a free (Size/8) byte region in each member of Used.
182  // FIXME: see if alignment helps.
183  for (unsigned I = 0;; ++I) {
184  for (auto &&B : Used) {
185  unsigned Byte = 0;
186  while ((I + Byte) < B.size() && Byte < (Size / 8)) {
187  if (B[I + Byte])
188  goto NextI;
189  ++Byte;
190  }
191  }
192  return (MinByte + I) * 8;
193  NextI:;
194  }
195  }
196 }
197 
199  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
200  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
201  if (BitWidth == 1)
202  OffsetByte = -(AllocBefore / 8 + 1);
203  else
204  OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
205  OffsetBit = AllocBefore % 8;
206 
207  for (VirtualCallTarget &Target : Targets) {
208  if (BitWidth == 1)
209  Target.setBeforeBit(AllocBefore);
210  else
211  Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
212  }
213 }
214 
216  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
217  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
218  if (BitWidth == 1)
219  OffsetByte = AllocAfter / 8;
220  else
221  OffsetByte = (AllocAfter + 7) / 8;
222  OffsetBit = AllocAfter % 8;
223 
224  for (VirtualCallTarget &Target : Targets) {
225  if (BitWidth == 1)
226  Target.setAfterBit(AllocAfter);
227  else
228  Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
229  }
230 }
231 
233  : Fn(Fn), TM(TM),
234  IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
235 
236 namespace {
237 
238 // A slot in a set of virtual tables. The TypeID identifies the set of virtual
239 // tables, and the ByteOffset is the offset in bytes from the address point to
240 // the virtual function pointer.
241 struct VTableSlot {
242  Metadata *TypeID;
243  uint64_t ByteOffset;
244 };
245 
246 } // end anonymous namespace
247 
248 namespace llvm {
249 
250 template <> struct DenseMapInfo<VTableSlot> {
251  static VTableSlot getEmptyKey() {
254  }
255  static VTableSlot getTombstoneKey() {
258  }
259  static unsigned getHashValue(const VTableSlot &I) {
260  return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
262  }
263  static bool isEqual(const VTableSlot &LHS,
264  const VTableSlot &RHS) {
265  return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
266  }
267 };
268 
269 } // end namespace llvm
270 
271 namespace {
272 
273 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
274 // the indirect virtual call.
275 struct VirtualCallSite {
276  Value *VTable;
277  CallSite CS;
278 
279  // If non-null, this field points to the associated unsafe use count stored in
280  // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
281  // of that field for details.
282  unsigned *NumUnsafeUses;
283 
284  void
285  emitRemark(const StringRef OptName, const StringRef TargetName,
287  Function *F = CS.getCaller();
288  DebugLoc DLoc = CS->getDebugLoc();
289  BasicBlock *Block = CS.getParent();
290 
291  using namespace ore;
292  OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
293  << NV("Optimization", OptName)
294  << ": devirtualized a call to "
295  << NV("FunctionName", TargetName));
296  }
297 
298  void replaceAndErase(
299  const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
301  Value *New) {
302  if (RemarksEnabled)
303  emitRemark(OptName, TargetName, OREGetter);
304  CS->replaceAllUsesWith(New);
305  if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
306  BranchInst::Create(II->getNormalDest(), CS.getInstruction());
307  II->getUnwindDest()->removePredecessor(II->getParent());
308  }
309  CS->eraseFromParent();
310  // This use is no longer unsafe.
311  if (NumUnsafeUses)
312  --*NumUnsafeUses;
313  }
314 };
315 
316 // Call site information collected for a specific VTableSlot and possibly a list
317 // of constant integer arguments. The grouping by arguments is handled by the
318 // VTableSlotInfo class.
319 struct CallSiteInfo {
320  /// The set of call sites for this slot. Used during regular LTO and the
321  /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
322  /// call sites that appear in the merged module itself); in each of these
323  /// cases we are directly operating on the call sites at the IR level.
324  std::vector<VirtualCallSite> CallSites;
325 
326  /// Whether all call sites represented by this CallSiteInfo, including those
327  /// in summaries, have been devirtualized. This starts off as true because a
328  /// default constructed CallSiteInfo represents no call sites.
329  bool AllCallSitesDevirted = true;
330 
331  // These fields are used during the export phase of ThinLTO and reflect
332  // information collected from function summaries.
333 
334  /// Whether any function summary contains an llvm.assume(llvm.type.test) for
335  /// this slot.
336  bool SummaryHasTypeTestAssumeUsers = false;
337 
338  /// CFI-specific: a vector containing the list of function summaries that use
339  /// the llvm.type.checked.load intrinsic and therefore will require
340  /// resolutions for llvm.type.test in order to implement CFI checks if
341  /// devirtualization was unsuccessful. If devirtualization was successful, the
342  /// pass will clear this vector by calling markDevirt(). If at the end of the
343  /// pass the vector is non-empty, we will need to add a use of llvm.type.test
344  /// to each of the function summaries in the vector.
345  std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
346 
347  bool isExported() const {
348  return SummaryHasTypeTestAssumeUsers ||
349  !SummaryTypeCheckedLoadUsers.empty();
350  }
351 
352  void markSummaryHasTypeTestAssumeUsers() {
353  SummaryHasTypeTestAssumeUsers = true;
354  AllCallSitesDevirted = false;
355  }
356 
357  void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
358  SummaryTypeCheckedLoadUsers.push_back(FS);
359  AllCallSitesDevirted = false;
360  }
361 
362  void markDevirt() {
363  AllCallSitesDevirted = true;
364 
365  // As explained in the comment for SummaryTypeCheckedLoadUsers.
366  SummaryTypeCheckedLoadUsers.clear();
367  }
368 };
369 
370 // Call site information collected for a specific VTableSlot.
371 struct VTableSlotInfo {
372  // The set of call sites which do not have all constant integer arguments
373  // (excluding "this").
374  CallSiteInfo CSInfo;
375 
376  // The set of call sites with all constant integer arguments (excluding
377  // "this"), grouped by argument list.
378  std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
379 
380  void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
381 
382 private:
383  CallSiteInfo &findCallSiteInfo(CallSite CS);
384 };
385 
386 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
387  std::vector<uint64_t> Args;
388  auto *CI = dyn_cast<IntegerType>(CS.getType());
389  if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
390  return CSInfo;
391  for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
392  auto *CI = dyn_cast<ConstantInt>(Arg);
393  if (!CI || CI->getBitWidth() > 64)
394  return CSInfo;
395  Args.push_back(CI->getZExtValue());
396  }
397  return ConstCSInfo[Args];
398 }
399 
400 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
401  unsigned *NumUnsafeUses) {
402  auto &CSI = findCallSiteInfo(CS);
403  CSI.AllCallSitesDevirted = false;
404  CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
405 }
406 
407 struct DevirtModule {
408  Module &M;
411 
412  ModuleSummaryIndex *ExportSummary;
413  const ModuleSummaryIndex *ImportSummary;
414 
415  IntegerType *Int8Ty;
416  PointerType *Int8PtrTy;
418  IntegerType *Int64Ty;
419  IntegerType *IntPtrTy;
420 
421  bool RemarksEnabled;
423 
425 
426  // This map keeps track of the number of "unsafe" uses of a loaded function
427  // pointer. The key is the associated llvm.type.test intrinsic call generated
428  // by this pass. An unsafe use is one that calls the loaded function pointer
429  // directly. Every time we eliminate an unsafe use (for example, by
430  // devirtualizing it or by applying virtual constant propagation), we
431  // decrement the value stored in this map. If a value reaches zero, we can
432  // eliminate the type check by RAUWing the associated llvm.type.test call with
433  // true.
434  std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
435 
436  DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
438  function_ref<DominatorTree &(Function &)> LookupDomTree,
439  ModuleSummaryIndex *ExportSummary,
440  const ModuleSummaryIndex *ImportSummary)
441  : M(M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
442  ExportSummary(ExportSummary), ImportSummary(ImportSummary),
443  Int8Ty(Type::getInt8Ty(M.getContext())),
444  Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
446  Int64Ty(Type::getInt64Ty(M.getContext())),
447  IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
448  RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
449  assert(!(ExportSummary && ImportSummary));
450  }
451 
452  bool areRemarksEnabled();
453 
454  void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
455  void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
456 
457  void buildTypeIdentifierMap(
458  std::vector<VTableBits> &Bits,
459  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
460  Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
461  bool
462  tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
463  const std::set<TypeMemberInfo> &TypeMemberInfos,
464  uint64_t ByteOffset);
465 
466  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
467  bool &IsExported);
468  bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
469  VTableSlotInfo &SlotInfo,
471 
472  void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT,
473  bool &IsExported);
474  void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
475  VTableSlotInfo &SlotInfo,
476  WholeProgramDevirtResolution *Res, VTableSlot Slot);
477 
478  bool tryEvaluateFunctionsWithArgs(
479  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
481 
482  void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
483  uint64_t TheRetVal);
484  bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
485  CallSiteInfo &CSInfo,
487 
488  // Returns the global symbol name that is used to export information about the
489  // given vtable slot and list of arguments.
490  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
491  StringRef Name);
492 
493  bool shouldExportConstantsAsAbsoluteSymbols();
494 
495  // This function is called during the export phase to create a symbol
496  // definition containing information about the given vtable slot and list of
497  // arguments.
498  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
499  Constant *C);
500  void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
501  uint32_t Const, uint32_t &Storage);
502 
503  // This function is called during the import phase to create a reference to
504  // the symbol definition created during the export phase.
505  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
506  StringRef Name);
507  Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
508  StringRef Name, IntegerType *IntTy,
509  uint32_t Storage);
510 
511  Constant *getMemberAddr(const TypeMemberInfo *M);
512 
513  void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
514  Constant *UniqueMemberAddr);
515  bool tryUniqueRetValOpt(unsigned BitWidth,
516  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
517  CallSiteInfo &CSInfo,
519  VTableSlot Slot, ArrayRef<uint64_t> Args);
520 
521  void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
522  Constant *Byte, Constant *Bit);
523  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
524  VTableSlotInfo &SlotInfo,
525  WholeProgramDevirtResolution *Res, VTableSlot Slot);
526 
527  void rebuildGlobal(VTableBits &B);
528 
529  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
530  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
531 
532  // If we were able to eliminate all unsafe uses for a type checked load,
533  // eliminate the associated type tests by replacing them with true.
534  void removeRedundantTypeTests();
535 
536  bool run();
537 
538  // Lower the module using the action and summary passed as command line
539  // arguments. For testing purposes only.
540  static bool
541  runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
543  function_ref<DominatorTree &(Function &)> LookupDomTree);
544 };
545 
546 struct WholeProgramDevirt : public ModulePass {
547  static char ID;
548 
549  bool UseCommandLine = false;
550 
551  ModuleSummaryIndex *ExportSummary;
552  const ModuleSummaryIndex *ImportSummary;
553 
554  WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
556  }
557 
558  WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
559  const ModuleSummaryIndex *ImportSummary)
560  : ModulePass(ID), ExportSummary(ExportSummary),
561  ImportSummary(ImportSummary) {
563  }
564 
565  bool runOnModule(Module &M) override {
566  if (skipModule(M))
567  return false;
568 
569  // In the new pass manager, we can request the optimization
570  // remark emitter pass on a per-function-basis, which the
571  // OREGetter will do for us.
572  // In the old pass manager, this is harder, so we just build
573  // an optimization remark emitter on the fly, when we need it.
574  std::unique_ptr<OptimizationRemarkEmitter> ORE;
575  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
576  ORE = make_unique<OptimizationRemarkEmitter>(F);
577  return *ORE;
578  };
579 
580  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
581  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
582  };
583 
584  if (UseCommandLine)
585  return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter,
586  LookupDomTree);
587 
588  return DevirtModule(M, LegacyAARGetter(*this), OREGetter, LookupDomTree,
589  ExportSummary, ImportSummary)
590  .run();
591  }
592 
593  void getAnalysisUsage(AnalysisUsage &AU) const override {
597  }
598 };
599 
600 } // end anonymous namespace
601 
602 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
603  "Whole program devirtualization", false, false)
608  "Whole program devirtualization", false, false)
609 char WholeProgramDevirt::ID = 0;
610 
611 ModulePass *
613  const ModuleSummaryIndex *ImportSummary) {
614  return new WholeProgramDevirt(ExportSummary, ImportSummary);
615 }
616 
618  ModuleAnalysisManager &AM) {
619  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
620  auto AARGetter = [&](Function &F) -> AAResults & {
621  return FAM.getResult<AAManager>(F);
622  };
623  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
624  return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
625  };
626  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
627  return FAM.getResult<DominatorTreeAnalysis>(F);
628  };
629  if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
630  ImportSummary)
631  .run())
632  return PreservedAnalyses::all();
633  return PreservedAnalyses::none();
634 }
635 
636 bool DevirtModule::runForTesting(
637  Module &M, function_ref<AAResults &(Function &)> AARGetter,
639  function_ref<DominatorTree &(Function &)> LookupDomTree) {
640  ModuleSummaryIndex Summary(/*HaveGVs=*/false);
641 
642  // Handle the command-line summary arguments. This code is for testing
643  // purposes only, so we handle errors directly.
644  if (!ClReadSummary.empty()) {
645  ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
646  ": ");
647  auto ReadSummaryFile =
649 
650  yaml::Input In(ReadSummaryFile->getBuffer());
651  In >> Summary;
652  ExitOnErr(errorCodeToError(In.error()));
653  }
654 
655  bool Changed =
656  DevirtModule(
657  M, AARGetter, OREGetter, LookupDomTree,
658  ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
659  ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
660  .run();
661 
662  if (!ClWriteSummary.empty()) {
663  ExitOnError ExitOnErr(
664  "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
665  std::error_code EC;
667  ExitOnErr(errorCodeToError(EC));
668 
669  yaml::Output Out(OS);
670  Out << Summary;
671  }
672 
673  return Changed;
674 }
675 
676 void DevirtModule::buildTypeIdentifierMap(
677  std::vector<VTableBits> &Bits,
678  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
680  Bits.reserve(M.getGlobalList().size());
682  for (GlobalVariable &GV : M.globals()) {
683  Types.clear();
684  GV.getMetadata(LLVMContext::MD_type, Types);
685  if (GV.isDeclaration() || Types.empty())
686  continue;
687 
688  VTableBits *&BitsPtr = GVToBits[&GV];
689  if (!BitsPtr) {
690  Bits.emplace_back();
691  Bits.back().GV = &GV;
692  Bits.back().ObjectSize =
693  M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
694  BitsPtr = &Bits.back();
695  }
696 
697  for (MDNode *Type : Types) {
698  auto TypeID = Type->getOperand(1).get();
699 
700  uint64_t Offset =
701  cast<ConstantInt>(
702  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
703  ->getZExtValue();
704 
705  TypeIdMap[TypeID].insert({BitsPtr, Offset});
706  }
707  }
708 }
709 
710 Constant *DevirtModule::getPointerAtOffset(Constant *I, uint64_t Offset) {
711  if (I->getType()->isPointerTy()) {
712  if (Offset == 0)
713  return I;
714  return nullptr;
715  }
716 
717  const DataLayout &DL = M.getDataLayout();
718 
719  if (auto *C = dyn_cast<ConstantStruct>(I)) {
720  const StructLayout *SL = DL.getStructLayout(C->getType());
721  if (Offset >= SL->getSizeInBytes())
722  return nullptr;
723 
724  unsigned Op = SL->getElementContainingOffset(Offset);
725  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
726  Offset - SL->getElementOffset(Op));
727  }
728  if (auto *C = dyn_cast<ConstantArray>(I)) {
729  ArrayType *VTableTy = C->getType();
730  uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
731 
732  unsigned Op = Offset / ElemSize;
733  if (Op >= C->getNumOperands())
734  return nullptr;
735 
736  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
737  Offset % ElemSize);
738  }
739  return nullptr;
740 }
741 
742 bool DevirtModule::tryFindVirtualCallTargets(
743  std::vector<VirtualCallTarget> &TargetsForSlot,
744  const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
745  for (const TypeMemberInfo &TM : TypeMemberInfos) {
746  if (!TM.Bits->GV->isConstant())
747  return false;
748 
749  Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
750  TM.Offset + ByteOffset);
751  if (!Ptr)
752  return false;
753 
754  auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
755  if (!Fn)
756  return false;
757 
758  // We can disregard __cxa_pure_virtual as a possible call target, as
759  // calls to pure virtuals are UB.
760  if (Fn->getName() == "__cxa_pure_virtual")
761  continue;
762 
763  TargetsForSlot.push_back({Fn, &TM});
764  }
765 
766  // Give up if we couldn't find any targets.
767  return !TargetsForSlot.empty();
768 }
769 
770 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
771  Constant *TheFn, bool &IsExported) {
772  auto Apply = [&](CallSiteInfo &CSInfo) {
773  for (auto &&VCallSite : CSInfo.CallSites) {
774  if (RemarksEnabled)
775  VCallSite.emitRemark("single-impl",
776  TheFn->stripPointerCasts()->getName(), OREGetter);
777  VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
778  TheFn, VCallSite.CS.getCalledValue()->getType()));
779  // This use is no longer unsafe.
780  if (VCallSite.NumUnsafeUses)
781  --*VCallSite.NumUnsafeUses;
782  }
783  if (CSInfo.isExported())
784  IsExported = true;
785  CSInfo.markDevirt();
786  };
787  Apply(SlotInfo.CSInfo);
788  for (auto &P : SlotInfo.ConstCSInfo)
789  Apply(P.second);
790 }
791 
792 bool DevirtModule::trySingleImplDevirt(
793  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
794  VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
795  // See if the program contains a single implementation of this virtual
796  // function.
797  Function *TheFn = TargetsForSlot[0].Fn;
798  for (auto &&Target : TargetsForSlot)
799  if (TheFn != Target.Fn)
800  return false;
801 
802  // If so, update each call site to call that implementation directly.
803  if (RemarksEnabled)
804  TargetsForSlot[0].WasDevirt = true;
805 
806  bool IsExported = false;
807  applySingleImplDevirt(SlotInfo, TheFn, IsExported);
808  if (!IsExported)
809  return false;
810 
811  // If the only implementation has local linkage, we must promote to external
812  // to make it visible to thin LTO objects. We can only get here during the
813  // ThinLTO export phase.
814  if (TheFn->hasLocalLinkage()) {
815  std::string NewName = (TheFn->getName() + "$merged").str();
816 
817  // Since we are renaming the function, any comdats with the same name must
818  // also be renamed. This is required when targeting COFF, as the comdat name
819  // must match one of the names of the symbols in the comdat.
820  if (Comdat *C = TheFn->getComdat()) {
821  if (C->getName() == TheFn->getName()) {
822  Comdat *NewC = M.getOrInsertComdat(NewName);
823  NewC->setSelectionKind(C->getSelectionKind());
824  for (GlobalObject &GO : M.global_objects())
825  if (GO.getComdat() == C)
826  GO.setComdat(NewC);
827  }
828  }
829 
832  TheFn->setName(NewName);
833  }
834 
836  Res->SingleImplName = TheFn->getName();
837 
838  return true;
839 }
840 
841 void DevirtModule::tryICallBranchFunnel(
842  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
843  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
844  Triple T(M.getTargetTriple());
845  if (T.getArch() != Triple::x86_64)
846  return;
847 
848  if (TargetsForSlot.size() > ClThreshold)
849  return;
850 
851  bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
852  if (!HasNonDevirt)
853  for (auto &P : SlotInfo.ConstCSInfo)
854  if (!P.second.AllCallSitesDevirted) {
855  HasNonDevirt = true;
856  break;
857  }
858 
859  if (!HasNonDevirt)
860  return;
861 
862  FunctionType *FT =
863  FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);
864  Function *JT;
865  if (isa<MDString>(Slot.TypeID)) {
868  getGlobalName(Slot, {}, "branch_funnel"), &M);
869  JT->setVisibility(GlobalValue::HiddenVisibility);
870  } else {
873  "branch_funnel", &M);
874  }
875  JT->addAttribute(1, Attribute::Nest);
876 
877  std::vector<Value *> JTArgs;
878  JTArgs.push_back(JT->arg_begin());
879  for (auto &T : TargetsForSlot) {
880  JTArgs.push_back(getMemberAddr(T.TM));
881  JTArgs.push_back(T.Fn);
882  }
883 
884  BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
885  Constant *Intr =
886  Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_branch_funnel, {});
887 
888  auto *CI = CallInst::Create(Intr, JTArgs, "", BB);
889  CI->setTailCallKind(CallInst::TCK_MustTail);
890  ReturnInst::Create(M.getContext(), nullptr, BB);
891 
892  bool IsExported = false;
893  applyICallBranchFunnel(SlotInfo, JT, IsExported);
894  if (IsExported)
896 }
897 
898 void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
899  Constant *JT, bool &IsExported) {
900  auto Apply = [&](CallSiteInfo &CSInfo) {
901  if (CSInfo.isExported())
902  IsExported = true;
903  if (CSInfo.AllCallSitesDevirted)
904  return;
905  for (auto &&VCallSite : CSInfo.CallSites) {
906  CallSite CS = VCallSite.CS;
907 
908  // Jump tables are only profitable if the retpoline mitigation is enabled.
909  Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
910  if (FSAttr.hasAttribute(Attribute::None) ||
911  !FSAttr.getValueAsString().contains("+retpoline"))
912  continue;
913 
914  if (RemarksEnabled)
915  VCallSite.emitRemark("branch-funnel",
916  JT->stripPointerCasts()->getName(), OREGetter);
917 
918  // Pass the address of the vtable in the nest register, which is r10 on
919  // x86_64.
920  std::vector<Type *> NewArgs;
921  NewArgs.push_back(Int8PtrTy);
922  for (Type *T : CS.getFunctionType()->params())
923  NewArgs.push_back(T);
926  CS.getFunctionType()->isVarArg()));
927 
928  IRBuilder<> IRB(CS.getInstruction());
929  std::vector<Value *> Args;
930  Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
931  for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
932  Args.push_back(CS.getArgOperand(I));
933 
934  CallSite NewCS;
935  if (CS.isCall())
936  NewCS = IRB.CreateCall(IRB.CreateBitCast(JT, NewFT), Args);
937  else
938  NewCS = IRB.CreateInvoke(
939  IRB.CreateBitCast(JT, NewFT),
940  cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
941  cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
942  NewCS.setCallingConv(CS.getCallingConv());
943 
945  std::vector<AttributeSet> NewArgAttrs;
946  NewArgAttrs.push_back(AttributeSet::get(
948  M.getContext(), Attribute::Nest)}));
949  for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
950  NewArgAttrs.push_back(Attrs.getParamAttributes(I));
951  NewCS.setAttributes(
953  Attrs.getRetAttributes(), NewArgAttrs));
954 
955  CS->replaceAllUsesWith(NewCS.getInstruction());
956  CS->eraseFromParent();
957 
958  // This use is no longer unsafe.
959  if (VCallSite.NumUnsafeUses)
960  --*VCallSite.NumUnsafeUses;
961  }
962  // Don't mark as devirtualized because there may be callers compiled without
963  // retpoline mitigation, which would mean that they are lowered to
964  // llvm.type.test and therefore require an llvm.type.test resolution for the
965  // type identifier.
966  };
967  Apply(SlotInfo.CSInfo);
968  for (auto &P : SlotInfo.ConstCSInfo)
969  Apply(P.second);
970 }
971 
972 bool DevirtModule::tryEvaluateFunctionsWithArgs(
973  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
975  // Evaluate each function and store the result in each target's RetVal
976  // field.
977  for (VirtualCallTarget &Target : TargetsForSlot) {
978  if (Target.Fn->arg_size() != Args.size() + 1)
979  return false;
980 
981  Evaluator Eval(M.getDataLayout(), nullptr);
983  EvalArgs.push_back(
984  Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
985  for (unsigned I = 0; I != Args.size(); ++I) {
986  auto *ArgTy = dyn_cast<IntegerType>(
987  Target.Fn->getFunctionType()->getParamType(I + 1));
988  if (!ArgTy)
989  return false;
990  EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
991  }
992 
993  Constant *RetVal;
994  if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
995  !isa<ConstantInt>(RetVal))
996  return false;
997  Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
998  }
999  return true;
1000 }
1001 
1002 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1003  uint64_t TheRetVal) {
1004  for (auto Call : CSInfo.CallSites)
1005  Call.replaceAndErase(
1006  "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1007  ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
1008  CSInfo.markDevirt();
1009 }
1010 
1011 bool DevirtModule::tryUniformRetValOpt(
1012  MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
1014  // Uniform return value optimization. If all functions return the same
1015  // constant, replace all calls with that constant.
1016  uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1017  for (const VirtualCallTarget &Target : TargetsForSlot)
1018  if (Target.RetVal != TheRetVal)
1019  return false;
1020 
1021  if (CSInfo.isExported()) {
1023  Res->Info = TheRetVal;
1024  }
1025 
1026  applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1027  if (RemarksEnabled)
1028  for (auto &&Target : TargetsForSlot)
1029  Target.WasDevirt = true;
1030  return true;
1031 }
1032 
1033 std::string DevirtModule::getGlobalName(VTableSlot Slot,
1034  ArrayRef<uint64_t> Args,
1035  StringRef Name) {
1036  std::string FullName = "__typeid_";
1037  raw_string_ostream OS(FullName);
1038  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1039  for (uint64_t Arg : Args)
1040  OS << '_' << Arg;
1041  OS << '_' << Name;
1042  return OS.str();
1043 }
1044 
1045 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1046  Triple T(M.getTargetTriple());
1047  return (T.getArch() == Triple::x86 || T.getArch() == Triple::x86_64) &&
1048  T.getObjectFormat() == Triple::ELF;
1049 }
1050 
1051 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1052  StringRef Name, Constant *C) {
1054  getGlobalName(Slot, Args, Name), C, &M);
1056 }
1057 
1058 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1059  StringRef Name, uint32_t Const,
1060  uint32_t &Storage) {
1061  if (shouldExportConstantsAsAbsoluteSymbols()) {
1062  exportGlobal(
1063  Slot, Args, Name,
1064  ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));
1065  return;
1066  }
1067 
1068  Storage = Const;
1069 }
1070 
1071 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1072  StringRef Name) {
1073  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
1074  auto *GV = dyn_cast<GlobalVariable>(C);
1075  if (GV)
1077  return C;
1078 }
1079 
1080 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1081  StringRef Name, IntegerType *IntTy,
1082  uint32_t Storage) {
1083  if (!shouldExportConstantsAsAbsoluteSymbols())
1084  return ConstantInt::get(IntTy, Storage);
1085 
1086  Constant *C = importGlobal(Slot, Args, Name);
1087  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1088  C = ConstantExpr::getPtrToInt(C, IntTy);
1089 
1090  // We only need to set metadata if the global is newly created, in which
1091  // case it would not have hidden visibility.
1092  if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1093  return C;
1094 
1095  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1096  auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1097  auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1098  GV->setMetadata(LLVMContext::MD_absolute_symbol,
1099  MDNode::get(M.getContext(), {MinC, MaxC}));
1100  };
1101  unsigned AbsWidth = IntTy->getBitWidth();
1102  if (AbsWidth == IntPtrTy->getBitWidth())
1103  SetAbsRange(~0ull, ~0ull); // Full set.
1104  else
1105  SetAbsRange(0, 1ull << AbsWidth);
1106  return C;
1107 }
1108 
1109 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1110  bool IsOne,
1111  Constant *UniqueMemberAddr) {
1112  for (auto &&Call : CSInfo.CallSites) {
1113  IRBuilder<> B(Call.CS.getInstruction());
1114  Value *Cmp =
1115  B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
1116  B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
1117  Cmp = B.CreateZExt(Cmp, Call.CS->getType());
1118  Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1119  Cmp);
1120  }
1121  CSInfo.markDevirt();
1122 }
1123 
1124 Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
1125  Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
1126  return ConstantExpr::getGetElementPtr(Int8Ty, C,
1127  ConstantInt::get(Int64Ty, M->Offset));
1128 }
1129 
1130 bool DevirtModule::tryUniqueRetValOpt(
1131  unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
1132  CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1133  VTableSlot Slot, ArrayRef<uint64_t> Args) {
1134  // IsOne controls whether we look for a 0 or a 1.
1135  auto tryUniqueRetValOptFor = [&](bool IsOne) {
1136  const TypeMemberInfo *UniqueMember = nullptr;
1137  for (const VirtualCallTarget &Target : TargetsForSlot) {
1138  if (Target.RetVal == (IsOne ? 1 : 0)) {
1139  if (UniqueMember)
1140  return false;
1141  UniqueMember = Target.TM;
1142  }
1143  }
1144 
1145  // We should have found a unique member or bailed out by now. We already
1146  // checked for a uniform return value in tryUniformRetValOpt.
1147  assert(UniqueMember);
1148 
1149  Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1150  if (CSInfo.isExported()) {
1152  Res->Info = IsOne;
1153 
1154  exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1155  }
1156 
1157  // Replace each call with the comparison.
1158  applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1159  UniqueMemberAddr);
1160 
1161  // Update devirtualization statistics for targets.
1162  if (RemarksEnabled)
1163  for (auto &&Target : TargetsForSlot)
1164  Target.WasDevirt = true;
1165 
1166  return true;
1167  };
1168 
1169  if (BitWidth == 1) {
1170  if (tryUniqueRetValOptFor(true))
1171  return true;
1172  if (tryUniqueRetValOptFor(false))
1173  return true;
1174  }
1175  return false;
1176 }
1177 
1178 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1179  Constant *Byte, Constant *Bit) {
1180  for (auto Call : CSInfo.CallSites) {
1181  auto *RetType = cast<IntegerType>(Call.CS.getType());
1182  IRBuilder<> B(Call.CS.getInstruction());
1183  Value *Addr =
1184  B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1185  if (RetType->getBitWidth() == 1) {
1186  Value *Bits = B.CreateLoad(Addr);
1187  Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1188  auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1189  Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1190  OREGetter, IsBitSet);
1191  } else {
1192  Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1193  Value *Val = B.CreateLoad(RetType, ValAddr);
1194  Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1195  OREGetter, Val);
1196  }
1197  }
1198  CSInfo.markDevirt();
1199 }
1200 
1201 bool DevirtModule::tryVirtualConstProp(
1202  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1203  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1204  // This only works if the function returns an integer.
1205  auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1206  if (!RetType)
1207  return false;
1208  unsigned BitWidth = RetType->getBitWidth();
1209  if (BitWidth > 64)
1210  return false;
1211 
1212  // Make sure that each function is defined, does not access memory, takes at
1213  // least one argument, does not use its first argument (which we assume is
1214  // 'this'), and has the same return type.
1215  //
1216  // Note that we test whether this copy of the function is readnone, rather
1217  // than testing function attributes, which must hold for any copy of the
1218  // function, even a less optimized version substituted at link time. This is
1219  // sound because the virtual constant propagation optimizations effectively
1220  // inline all implementations of the virtual function into each call site,
1221  // rather than using function attributes to perform local optimization.
1222  for (VirtualCallTarget &Target : TargetsForSlot) {
1223  if (Target.Fn->isDeclaration() ||
1224  computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1225  MAK_ReadNone ||
1226  Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1227  Target.Fn->getReturnType() != RetType)
1228  return false;
1229  }
1230 
1231  for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1232  if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1233  continue;
1234 
1235  WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1236  if (Res)
1237  ResByArg = &Res->ResByArg[CSByConstantArg.first];
1238 
1239  if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1240  continue;
1241 
1242  if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1243  ResByArg, Slot, CSByConstantArg.first))
1244  continue;
1245 
1246  // Find an allocation offset in bits in all vtables associated with the
1247  // type.
1248  uint64_t AllocBefore =
1249  findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1250  uint64_t AllocAfter =
1251  findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1252 
1253  // Calculate the total amount of padding needed to store a value at both
1254  // ends of the object.
1255  uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1256  for (auto &&Target : TargetsForSlot) {
1257  TotalPaddingBefore += std::max<int64_t>(
1258  (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1259  TotalPaddingAfter += std::max<int64_t>(
1260  (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1261  }
1262 
1263  // If the amount of padding is too large, give up.
1264  // FIXME: do something smarter here.
1265  if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1266  continue;
1267 
1268  // Calculate the offset to the value as a (possibly negative) byte offset
1269  // and (if applicable) a bit offset, and store the values in the targets.
1270  int64_t OffsetByte;
1271  uint64_t OffsetBit;
1272  if (TotalPaddingBefore <= TotalPaddingAfter)
1273  setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1274  OffsetBit);
1275  else
1276  setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1277  OffsetBit);
1278 
1279  if (RemarksEnabled)
1280  for (auto &&Target : TargetsForSlot)
1281  Target.WasDevirt = true;
1282 
1283 
1284  if (CSByConstantArg.second.isExported()) {
1286  exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1287  ResByArg->Byte);
1288  exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1289  ResByArg->Bit);
1290  }
1291 
1292  // Rewrite each call to a load from OffsetByte/OffsetBit.
1293  Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1294  Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1295  applyVirtualConstProp(CSByConstantArg.second,
1296  TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1297  }
1298  return true;
1299 }
1300 
1301 void DevirtModule::rebuildGlobal(VTableBits &B) {
1302  if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1303  return;
1304 
1305  // Align each byte array to pointer width.
1306  unsigned PointerSize = M.getDataLayout().getPointerSize();
1307  B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
1308  B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));
1309 
1310  // Before was stored in reverse order; flip it now.
1311  for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1312  std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1313 
1314  // Build an anonymous global containing the before bytes, followed by the
1315  // original initializer, followed by the after bytes.
1316  auto NewInit = ConstantStruct::getAnon(
1317  {ConstantDataArray::get(M.getContext(), B.Before.Bytes),
1318  B.GV->getInitializer(),
1319  ConstantDataArray::get(M.getContext(), B.After.Bytes)});
1320  auto NewGV =
1321  new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1322  GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1323  NewGV->setSection(B.GV->getSection());
1324  NewGV->setComdat(B.GV->getComdat());
1325 
1326  // Copy the original vtable's metadata to the anonymous global, adjusting
1327  // offsets as required.
1328  NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1329 
1330  // Build an alias named after the original global, pointing at the second
1331  // element (the original initializer).
1332  auto Alias = GlobalAlias::create(
1333  B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1335  NewInit->getType(), NewGV,
1337  ConstantInt::get(Int32Ty, 1)}),
1338  &M);
1339  Alias->setVisibility(B.GV->getVisibility());
1340  Alias->takeName(B.GV);
1341 
1342  B.GV->replaceAllUsesWith(Alias);
1343  B.GV->eraseFromParent();
1344 }
1345 
1346 bool DevirtModule::areRemarksEnabled() {
1347  const auto &FL = M.getFunctionList();
1348  for (const Function &Fn : FL) {
1349  const auto &BBL = Fn.getBasicBlockList();
1350  if (BBL.empty())
1351  continue;
1352  auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1353  return DI.isEnabled();
1354  }
1355  return false;
1356 }
1357 
1358 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1359  Function *AssumeFunc) {
1360  // Find all virtual calls via a virtual table pointer %p under an assumption
1361  // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1362  // points to a member of the type identifier %md. Group calls by (type ID,
1363  // offset) pair (effectively the identity of the virtual function) and store
1364  // to CallSlots.
1365  DenseSet<CallSite> SeenCallSites;
1366  for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1367  I != E;) {
1368  auto CI = dyn_cast<CallInst>(I->getUser());
1369  ++I;
1370  if (!CI)
1371  continue;
1372 
1373  // Search for virtual calls based on %p and add them to DevirtCalls.
1374  SmallVector<DevirtCallSite, 1> DevirtCalls;
1376  auto &DT = LookupDomTree(*CI->getFunction());
1377  findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
1378 
1379  // If we found any, add them to CallSlots.
1380  if (!Assumes.empty()) {
1381  Metadata *TypeId =
1382  cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1383  Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1384  for (DevirtCallSite Call : DevirtCalls) {
1385  // Only add this CallSite if we haven't seen it before. The vtable
1386  // pointer may have been CSE'd with pointers from other call sites,
1387  // and we don't want to process call sites multiple times. We can't
1388  // just skip the vtable Ptr if it has been seen before, however, since
1389  // it may be shared by type tests that dominate different calls.
1390  if (SeenCallSites.insert(Call.CS).second)
1391  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1392  }
1393  }
1394 
1395  // We no longer need the assumes or the type test.
1396  for (auto Assume : Assumes)
1397  Assume->eraseFromParent();
1398  // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1399  // may use the vtable argument later.
1400  if (CI->use_empty())
1401  CI->eraseFromParent();
1402  }
1403 }
1404 
1405 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1406  Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1407 
1408  for (auto I = TypeCheckedLoadFunc->use_begin(),
1409  E = TypeCheckedLoadFunc->use_end();
1410  I != E;) {
1411  auto CI = dyn_cast<CallInst>(I->getUser());
1412  ++I;
1413  if (!CI)
1414  continue;
1415 
1416  Value *Ptr = CI->getArgOperand(0);
1417  Value *Offset = CI->getArgOperand(1);
1418  Value *TypeIdValue = CI->getArgOperand(2);
1419  Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1420 
1421  SmallVector<DevirtCallSite, 1> DevirtCalls;
1422  SmallVector<Instruction *, 1> LoadedPtrs;
1424  bool HasNonCallUses = false;
1425  auto &DT = LookupDomTree(*CI->getFunction());
1426  findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1427  HasNonCallUses, CI, DT);
1428 
1429  // Start by generating "pessimistic" code that explicitly loads the function
1430  // pointer from the vtable and performs the type check. If possible, we will
1431  // eliminate the load and the type check later.
1432 
1433  // If possible, only generate the load at the point where it is used.
1434  // This helps avoid unnecessary spills.
1435  IRBuilder<> LoadB(
1436  (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1437  Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1438  Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1439  Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1440 
1441  for (Instruction *LoadedPtr : LoadedPtrs) {
1442  LoadedPtr->replaceAllUsesWith(LoadedValue);
1443  LoadedPtr->eraseFromParent();
1444  }
1445 
1446  // Likewise for the type test.
1447  IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1448  CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1449 
1450  for (Instruction *Pred : Preds) {
1451  Pred->replaceAllUsesWith(TypeTestCall);
1452  Pred->eraseFromParent();
1453  }
1454 
1455  // We have already erased any extractvalue instructions that refer to the
1456  // intrinsic call, but the intrinsic may have other non-extractvalue uses
1457  // (although this is unlikely). In that case, explicitly build a pair and
1458  // RAUW it.
1459  if (!CI->use_empty()) {
1460  Value *Pair = UndefValue::get(CI->getType());
1461  IRBuilder<> B(CI);
1462  Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1463  Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1464  CI->replaceAllUsesWith(Pair);
1465  }
1466 
1467  // The number of unsafe uses is initially the number of uses.
1468  auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1469  NumUnsafeUses = DevirtCalls.size();
1470 
1471  // If the function pointer has a non-call user, we cannot eliminate the type
1472  // check, as one of those users may eventually call the pointer. Increment
1473  // the unsafe use count to make sure it cannot reach zero.
1474  if (HasNonCallUses)
1475  ++NumUnsafeUses;
1476  for (DevirtCallSite Call : DevirtCalls) {
1477  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1478  &NumUnsafeUses);
1479  }
1480 
1481  CI->eraseFromParent();
1482  }
1483 }
1484 
1485 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1486  const TypeIdSummary *TidSummary =
1487  ImportSummary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString());
1488  if (!TidSummary)
1489  return;
1490  auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1491  if (ResI == TidSummary->WPDRes.end())
1492  return;
1493  const WholeProgramDevirtResolution &Res = ResI->second;
1494 
1496  // The type of the function in the declaration is irrelevant because every
1497  // call site will cast it to the correct type.
1498  auto *SingleImpl = M.getOrInsertFunction(
1499  Res.SingleImplName, Type::getVoidTy(M.getContext()));
1500 
1501  // This is the import phase so we should not be exporting anything.
1502  bool IsExported = false;
1503  applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1504  assert(!IsExported);
1505  }
1506 
1507  for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1508  auto I = Res.ResByArg.find(CSByConstantArg.first);
1509  if (I == Res.ResByArg.end())
1510  continue;
1511  auto &ResByArg = I->second;
1512  // FIXME: We should figure out what to do about the "function name" argument
1513  // to the apply* functions, as the function names are unavailable during the
1514  // importing phase. For now we just pass the empty string. This does not
1515  // impact correctness because the function names are just used for remarks.
1516  switch (ResByArg.TheKind) {
1518  applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1519  break;
1521  Constant *UniqueMemberAddr =
1522  importGlobal(Slot, CSByConstantArg.first, "unique_member");
1523  applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1524  UniqueMemberAddr);
1525  break;
1526  }
1528  Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1529  Int32Ty, ResByArg.Byte);
1530  Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1531  ResByArg.Bit);
1532  applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1533  break;
1534  }
1535  default:
1536  break;
1537  }
1538  }
1539 
1541  auto *JT = M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
1542  Type::getVoidTy(M.getContext()));
1543  bool IsExported = false;
1544  applyICallBranchFunnel(SlotInfo, JT, IsExported);
1545  assert(!IsExported);
1546  }
1547 }
1548 
1549 void DevirtModule::removeRedundantTypeTests() {
1550  auto True = ConstantInt::getTrue(M.getContext());
1551  for (auto &&U : NumUnsafeUsesForTypeTest) {
1552  if (U.second == 0) {
1553  U.first->replaceAllUsesWith(True);
1554  U.first->eraseFromParent();
1555  }
1556  }
1557 }
1558 
1559 bool DevirtModule::run() {
1560  Function *TypeTestFunc =
1561  M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1562  Function *TypeCheckedLoadFunc =
1563  M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1564  Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1565 
1566  // If only some of the modules were split, we cannot correctly handle
1567  // code that contains type tests or type checked loads.
1568  if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1569  (ImportSummary && ImportSummary->partiallySplitLTOUnits())) {
1570  if ((TypeTestFunc && !TypeTestFunc->use_empty()) ||
1571  (TypeCheckedLoadFunc && !TypeCheckedLoadFunc->use_empty()))
1572  report_fatal_error("inconsistent LTO Unit splitting with llvm.type.test "
1573  "or llvm.type.checked.load");
1574  return false;
1575  }
1576 
1577  // Normally if there are no users of the devirtualization intrinsics in the
1578  // module, this pass has nothing to do. But if we are exporting, we also need
1579  // to handle any users that appear only in the function summaries.
1580  if (!ExportSummary &&
1581  (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1582  AssumeFunc->use_empty()) &&
1583  (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1584  return false;
1585 
1586  if (TypeTestFunc && AssumeFunc)
1587  scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1588 
1589  if (TypeCheckedLoadFunc)
1590  scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1591 
1592  if (ImportSummary) {
1593  for (auto &S : CallSlots)
1594  importResolution(S.first, S.second);
1595 
1596  removeRedundantTypeTests();
1597 
1598  // The rest of the code is only necessary when exporting or during regular
1599  // LTO, so we are done.
1600  return true;
1601  }
1602 
1603  // Rebuild type metadata into a map for easy lookup.
1604  std::vector<VTableBits> Bits;
1606  buildTypeIdentifierMap(Bits, TypeIdMap);
1607  if (TypeIdMap.empty())
1608  return true;
1609 
1610  // Collect information from summary about which calls to try to devirtualize.
1611  if (ExportSummary) {
1613  for (auto &P : TypeIdMap) {
1614  if (auto *TypeId = dyn_cast<MDString>(P.first))
1615  MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1616  TypeId);
1617  }
1618 
1619  for (auto &P : *ExportSummary) {
1620  for (auto &S : P.second.SummaryList) {
1621  auto *FS = dyn_cast<FunctionSummary>(S.get());
1622  if (!FS)
1623  continue;
1624  // FIXME: Only add live functions.
1625  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1626  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1627  CallSlots[{MD, VF.Offset}]
1628  .CSInfo.markSummaryHasTypeTestAssumeUsers();
1629  }
1630  }
1631  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1632  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1633  CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
1634  }
1635  }
1636  for (const FunctionSummary::ConstVCall &VC :
1637  FS->type_test_assume_const_vcalls()) {
1638  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1639  CallSlots[{MD, VC.VFunc.Offset}]
1640  .ConstCSInfo[VC.Args]
1641  .markSummaryHasTypeTestAssumeUsers();
1642  }
1643  }
1644  for (const FunctionSummary::ConstVCall &VC :
1645  FS->type_checked_load_const_vcalls()) {
1646  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1647  CallSlots[{MD, VC.VFunc.Offset}]
1648  .ConstCSInfo[VC.Args]
1649  .addSummaryTypeCheckedLoadUser(FS);
1650  }
1651  }
1652  }
1653  }
1654  }
1655 
1656  // For each (type, offset) pair:
1657  bool DidVirtualConstProp = false;
1658  std::map<std::string, Function*> DevirtTargets;
1659  for (auto &S : CallSlots) {
1660  // Search each of the members of the type identifier for the virtual
1661  // function implementation at offset S.first.ByteOffset, and add to
1662  // TargetsForSlot.
1663  std::vector<VirtualCallTarget> TargetsForSlot;
1664  if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
1665  S.first.ByteOffset)) {
1666  WholeProgramDevirtResolution *Res = nullptr;
1667  if (ExportSummary && isa<MDString>(S.first.TypeID))
1668  Res = &ExportSummary
1669  ->getOrInsertTypeIdSummary(
1670  cast<MDString>(S.first.TypeID)->getString())
1671  .WPDRes[S.first.ByteOffset];
1672 
1673  if (!trySingleImplDevirt(TargetsForSlot, S.second, Res)) {
1674  DidVirtualConstProp |=
1675  tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
1676 
1677  tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
1678  }
1679 
1680  // Collect functions devirtualized at least for one call site for stats.
1681  if (RemarksEnabled)
1682  for (const auto &T : TargetsForSlot)
1683  if (T.WasDevirt)
1684  DevirtTargets[T.Fn->getName()] = T.Fn;
1685  }
1686 
1687  // CFI-specific: if we are exporting and any llvm.type.checked.load
1688  // intrinsics were *not* devirtualized, we need to add the resulting
1689  // llvm.type.test intrinsics to the function summaries so that the
1690  // LowerTypeTests pass will export them.
1691  if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1692  auto GUID =
1693  GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1694  for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1695  FS->addTypeTest(GUID);
1696  for (auto &CCS : S.second.ConstCSInfo)
1697  for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1698  FS->addTypeTest(GUID);
1699  }
1700  }
1701 
1702  if (RemarksEnabled) {
1703  // Generate remarks for each devirtualized function.
1704  for (const auto &DT : DevirtTargets) {
1705  Function *F = DT.second;
1706 
1707  using namespace ore;
1708  OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
1709  << "devirtualized "
1710  << NV("FunctionName", F->getName()));
1711  }
1712  }
1713 
1714  removeRedundantTypeTests();
1715 
1716  // Rebuild each global we touched as part of virtual constant propagation to
1717  // include the before and after bytes.
1718  if (DidVirtualConstProp)
1719  for (VTableBits &B : Bits)
1720  rebuildGlobal(B);
1721 
1722  return true;
1723 }
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:239
uint64_t CallInst * C
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:90
use_iterator use_end()
Definition: Value.h:347
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
const std::string & getTargetTriple() const
Get the target triple which is a string describing the target host.
Definition: Module.h:240
bool empty() const
Definition: Function.h:662
bool hasLocalLinkage() const
Definition: GlobalValue.h:436
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
DiagnosticInfoOptimizationBase::Argument NV
CallingConv::ID getCallingConv() const
Get the calling convention of the call.
Definition: CallSite.h:312
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:770
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
This class represents lattice values for constants.
Definition: AllocatorList.h:24
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool contains(StringRef Other) const
Return true if the given string is a substring of *this, and false otherwise.
Definition: StringRef.h:448
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:1357
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:1154
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:250
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:588
void push_back(const T &Elt)
Definition: SmallVector.h:218
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:1225
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:117
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1760
uint64_t Info
Additional information for the resolution:
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:57
Externally visible function.
Definition: GlobalValue.h:49
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:38
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:864
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:685
const GlobalListType & getGlobalList() const
Get the Module&#39;s list of global variables (constant).
Definition: Module.h:521
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:177
Hexagon Common GEP
MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
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...
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it...
Definition: DataLayout.cpp:84
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:265
Export information to summary.
const char * getName() const
getName - Get the target name.
iterator_range< global_object_iterator > global_objects()
Definition: Module.h:659
bool arg_empty() const
Definition: CallSite.h:218
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)
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()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:529
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
amdgpu Simplify well known AMD library false Value Value const Twine & Name
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:626
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:371
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...
IterTy arg_end() const
Definition: CallSite.h:575
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
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.
InstrTy * getInstruction() const
Definition: CallSite.h:92
unsigned Intr
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
static bool isEqual(const VTableSlot &LHS, const VTableSlot &RHS)
enum llvm::WholeProgramDevirtResolution::Kind TheKind
Class to represent function types.
Definition: DerivedTypes.h:103
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1732
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
#define T
ValTy * getArgOperand(unsigned i) const
Definition: CallSite.h:297
Class to represent array types.
Definition: DerivedTypes.h:369
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
bool isVarArg() const
Definition: DerivedTypes.h:123
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
LinkageTypes getLinkage() const
Definition: GlobalValue.h:451
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:66
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:410
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
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:1020
Value * getOperand(unsigned i) const
Definition: User.h:170
Class to represent pointers.
Definition: DerivedTypes.h:467
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:157
bool isCall() const
Return true if a CallInst is enclosed.
Definition: CallSite.h:87
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1773
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:750
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1166
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:333
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
Definition: Attributes.cpp:202
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
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:154
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
Definition: Attributes.cpp:513
std::size_t 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:120
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:233
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
Import information from summary.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
A call site that could be devirtualized.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
Definition: Error.cpp:88
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:643
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
#define DEBUG_TYPE
A manager for alias analyses.
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:359
INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt", "Whole program devirtualization", false, false) INITIALIZE_PASS_END(WholeProgramDevirt
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:130
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
Definition: Error.h:1104
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:368
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
Type::TypeID TypeID
void setCallingConv(CallingConv::ID CC)
Set the calling convention of the call.
Definition: CallSite.h:316
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:297
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:130
Class to represent integer types.
Definition: DerivedTypes.h:40
enum llvm::WholeProgramDevirtResolution::ByArg::Kind TheKind
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
const Constant * stripPointerCasts() const
Definition: Constant.h:174
Comdat * getOrInsertComdat(StringRef Name)
Return the Comdat in the module with the specified name.
Definition: Module.cpp:484
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:529
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
unsigned getNumArgOperands() const
Definition: CallSite.h:293
size_t size() const
Definition: SmallVector.h:53
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
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:499
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:44
An "identifier" for a virtual function.
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:39
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1458
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:192
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:482
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
void setSelectionKind(SelectionKind Val)
Definition: Comdat.h:46
IterTy arg_begin() const
Definition: CallSite.h:571
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
Single implementation devirtualization.
Type * getReturnType() const
Definition: DerivedTypes.h:124
uint64_t getSizeInBytes() const
Definition: DataLayout.h:537
unsigned getProgramAddressSpace() const
Definition: DataLayout.h:260
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:622
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:578
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:97
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:445
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
wholeprogramdevirt
Target - Wrapper for Target specific information.
unsigned getNumAttrSets() const
A specification for a virtual function call with all constant integer arguments.
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:501
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:179
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:618
amdgpu Simplify well known AMD library false Value Value * Arg
const Comdat * getComdat() const
Definition: GlobalObject.h:101
ModulePass * createWholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary)
This pass implements whole-program devirtualization using type metadata.
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:436
use_iterator use_begin()
Definition: Value.h:339
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:267
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:206
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:366
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:551
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:195
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:1747
#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:225
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:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:633
uint32_t Size
Definition: Profile.cpp:47
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1974
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:81
Provides passes for computing function attributes based on interprocedural analyses.
Function summary information to aid decisions and implementation of importing.
Type * getType() const
Return the type of the instruction that generated this call site.
Definition: CallSite.h:264
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.
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:483
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:73
FunctionType * getFunctionType() const
Definition: CallSite.h:320
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:331
static Constant * getAnon(ArrayRef< Constant *> V, bool Packed=false)
Return an anonymous struct that has the specified elements.
Definition: Constants.h:469
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:703
Type * getElementType() const
Definition: DerivedTypes.h:360
iterator_range< global_iterator > globals()
Definition: Module.h:584
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
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:260
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:329
Root of the metadata hierarchy.
Definition: Metadata.h:58
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:174
void setSection(StringRef S)
Change the section for this global.
Definition: Globals.cpp:189
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:323
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:423
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:873
IntegerType * Int32Ty
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1038