LLVM  6.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"
60 #include "llvm/IR/DebugLoc.h"
61 #include "llvm/IR/DerivedTypes.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 // Find the minimum offset that we may store a value of size Size bits at. If
116 // IsAfter is set, look for an offset before the object, otherwise look for an
117 // offset after the object.
118 uint64_t
120  bool IsAfter, uint64_t Size) {
121  // Find a minimum offset taking into account only vtable sizes.
122  uint64_t MinByte = 0;
123  for (const VirtualCallTarget &Target : Targets) {
124  if (IsAfter)
125  MinByte = std::max(MinByte, Target.minAfterBytes());
126  else
127  MinByte = std::max(MinByte, Target.minBeforeBytes());
128  }
129 
130  // Build a vector of arrays of bytes covering, for each target, a slice of the
131  // used region (see AccumBitVector::BytesUsed in
132  // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,
133  // this aligns the used regions to start at MinByte.
134  //
135  // In this example, A, B and C are vtables, # is a byte already allocated for
136  // a virtual function pointer, AAAA... (etc.) are the used regions for the
137  // vtables and Offset(X) is the value computed for the Offset variable below
138  // for X.
139  //
140  // Offset(A)
141  // | |
142  // |MinByte
143  // A: ################AAAAAAAA|AAAAAAAA
144  // B: ########BBBBBBBBBBBBBBBB|BBBB
145  // C: ########################|CCCCCCCCCCCCCCCC
146  // | Offset(B) |
147  //
148  // This code produces the slices of A, B and C that appear after the divider
149  // at MinByte.
150  std::vector<ArrayRef<uint8_t>> Used;
151  for (const VirtualCallTarget &Target : Targets) {
152  ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed
153  : Target.TM->Bits->Before.BytesUsed;
154  uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
155  : MinByte - Target.minBeforeBytes();
156 
157  // Disregard used regions that are smaller than Offset. These are
158  // effectively all-free regions that do not need to be checked.
159  if (VTUsed.size() > Offset)
160  Used.push_back(VTUsed.slice(Offset));
161  }
162 
163  if (Size == 1) {
164  // Find a free bit in each member of Used.
165  for (unsigned I = 0;; ++I) {
166  uint8_t BitsUsed = 0;
167  for (auto &&B : Used)
168  if (I < B.size())
169  BitsUsed |= B[I];
170  if (BitsUsed != 0xff)
171  return (MinByte + I) * 8 +
172  countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
173  }
174  } else {
175  // Find a free (Size/8) byte region in each member of Used.
176  // FIXME: see if alignment helps.
177  for (unsigned I = 0;; ++I) {
178  for (auto &&B : Used) {
179  unsigned Byte = 0;
180  while ((I + Byte) < B.size() && Byte < (Size / 8)) {
181  if (B[I + Byte])
182  goto NextI;
183  ++Byte;
184  }
185  }
186  return (MinByte + I) * 8;
187  NextI:;
188  }
189  }
190 }
191 
193  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
194  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
195  if (BitWidth == 1)
196  OffsetByte = -(AllocBefore / 8 + 1);
197  else
198  OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
199  OffsetBit = AllocBefore % 8;
200 
201  for (VirtualCallTarget &Target : Targets) {
202  if (BitWidth == 1)
203  Target.setBeforeBit(AllocBefore);
204  else
205  Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
206  }
207 }
208 
210  MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
211  unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
212  if (BitWidth == 1)
213  OffsetByte = AllocAfter / 8;
214  else
215  OffsetByte = (AllocAfter + 7) / 8;
216  OffsetBit = AllocAfter % 8;
217 
218  for (VirtualCallTarget &Target : Targets) {
219  if (BitWidth == 1)
220  Target.setAfterBit(AllocAfter);
221  else
222  Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
223  }
224 }
225 
227  : Fn(Fn), TM(TM),
228  IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()), WasDevirt(false) {}
229 
230 namespace {
231 
232 // A slot in a set of virtual tables. The TypeID identifies the set of virtual
233 // tables, and the ByteOffset is the offset in bytes from the address point to
234 // the virtual function pointer.
235 struct VTableSlot {
236  Metadata *TypeID;
237  uint64_t ByteOffset;
238 };
239 
240 } // end anonymous namespace
241 
242 namespace llvm {
243 
244 template <> struct DenseMapInfo<VTableSlot> {
245  static VTableSlot getEmptyKey() {
248  }
249  static VTableSlot getTombstoneKey() {
252  }
253  static unsigned getHashValue(const VTableSlot &I) {
254  return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
256  }
257  static bool isEqual(const VTableSlot &LHS,
258  const VTableSlot &RHS) {
259  return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
260  }
261 };
262 
263 } // end namespace llvm
264 
265 namespace {
266 
267 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
268 // the indirect virtual call.
269 struct VirtualCallSite {
270  Value *VTable;
271  CallSite CS;
272 
273  // If non-null, this field points to the associated unsafe use count stored in
274  // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
275  // of that field for details.
276  unsigned *NumUnsafeUses;
277 
278  void
279  emitRemark(const StringRef OptName, const StringRef TargetName,
281  Function *F = CS.getCaller();
282  DebugLoc DLoc = CS->getDebugLoc();
283  BasicBlock *Block = CS.getParent();
284 
285  // In the new pass manager, we can request the optimization
286  // remark emitter pass on a per-function-basis, which the
287  // OREGetter will do for us.
288  // In the old pass manager, this is harder, so we just build
289  // a optimization remark emitter on the fly, when we need it.
290  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
292  if (OREGetter)
293  ORE = &OREGetter(F);
294  else {
295  OwnedORE = make_unique<OptimizationRemarkEmitter>(F);
296  ORE = OwnedORE.get();
297  }
298 
299  using namespace ore;
300  ORE->emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
301  << NV("Optimization", OptName) << ": devirtualized a call to "
302  << NV("FunctionName", TargetName));
303  }
304 
305  void replaceAndErase(
306  const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
308  Value *New) {
309  if (RemarksEnabled)
310  emitRemark(OptName, TargetName, OREGetter);
311  CS->replaceAllUsesWith(New);
312  if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
313  BranchInst::Create(II->getNormalDest(), CS.getInstruction());
314  II->getUnwindDest()->removePredecessor(II->getParent());
315  }
316  CS->eraseFromParent();
317  // This use is no longer unsafe.
318  if (NumUnsafeUses)
319  --*NumUnsafeUses;
320  }
321 };
322 
323 // Call site information collected for a specific VTableSlot and possibly a list
324 // of constant integer arguments. The grouping by arguments is handled by the
325 // VTableSlotInfo class.
326 struct CallSiteInfo {
327  /// The set of call sites for this slot. Used during regular LTO and the
328  /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
329  /// call sites that appear in the merged module itself); in each of these
330  /// cases we are directly operating on the call sites at the IR level.
331  std::vector<VirtualCallSite> CallSites;
332 
333  // These fields are used during the export phase of ThinLTO and reflect
334  // information collected from function summaries.
335 
336  /// Whether any function summary contains an llvm.assume(llvm.type.test) for
337  /// this slot.
338  bool SummaryHasTypeTestAssumeUsers;
339 
340  /// CFI-specific: a vector containing the list of function summaries that use
341  /// the llvm.type.checked.load intrinsic and therefore will require
342  /// resolutions for llvm.type.test in order to implement CFI checks if
343  /// devirtualization was unsuccessful. If devirtualization was successful, the
344  /// pass will clear this vector by calling markDevirt(). If at the end of the
345  /// pass the vector is non-empty, we will need to add a use of llvm.type.test
346  /// to each of the function summaries in the vector.
347  std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
348 
349  bool isExported() const {
350  return SummaryHasTypeTestAssumeUsers ||
351  !SummaryTypeCheckedLoadUsers.empty();
352  }
353 
354  /// As explained in the comment for SummaryTypeCheckedLoadUsers.
355  void markDevirt() { SummaryTypeCheckedLoadUsers.clear(); }
356 };
357 
358 // Call site information collected for a specific VTableSlot.
359 struct VTableSlotInfo {
360  // The set of call sites which do not have all constant integer arguments
361  // (excluding "this").
362  CallSiteInfo CSInfo;
363 
364  // The set of call sites with all constant integer arguments (excluding
365  // "this"), grouped by argument list.
366  std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
367 
368  void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
369 
370 private:
371  CallSiteInfo &findCallSiteInfo(CallSite CS);
372 };
373 
374 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallSite CS) {
375  std::vector<uint64_t> Args;
376  auto *CI = dyn_cast<IntegerType>(CS.getType());
377  if (!CI || CI->getBitWidth() > 64 || CS.arg_empty())
378  return CSInfo;
379  for (auto &&Arg : make_range(CS.arg_begin() + 1, CS.arg_end())) {
380  auto *CI = dyn_cast<ConstantInt>(Arg);
381  if (!CI || CI->getBitWidth() > 64)
382  return CSInfo;
383  Args.push_back(CI->getZExtValue());
384  }
385  return ConstCSInfo[Args];
386 }
387 
388 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
389  unsigned *NumUnsafeUses) {
390  findCallSiteInfo(CS).CallSites.push_back({VTable, CS, NumUnsafeUses});
391 }
392 
393 struct DevirtModule {
394  Module &M;
396 
397  ModuleSummaryIndex *ExportSummary;
398  const ModuleSummaryIndex *ImportSummary;
399 
400  IntegerType *Int8Ty;
401  PointerType *Int8PtrTy;
403  IntegerType *Int64Ty;
404  IntegerType *IntPtrTy;
405 
406  bool RemarksEnabled;
408 
410 
411  // This map keeps track of the number of "unsafe" uses of a loaded function
412  // pointer. The key is the associated llvm.type.test intrinsic call generated
413  // by this pass. An unsafe use is one that calls the loaded function pointer
414  // directly. Every time we eliminate an unsafe use (for example, by
415  // devirtualizing it or by applying virtual constant propagation), we
416  // decrement the value stored in this map. If a value reaches zero, we can
417  // eliminate the type check by RAUWing the associated llvm.type.test call with
418  // true.
419  std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
420 
421  DevirtModule(Module &M, function_ref<AAResults &(Function &)> AARGetter,
423  ModuleSummaryIndex *ExportSummary,
424  const ModuleSummaryIndex *ImportSummary)
425  : M(M), AARGetter(AARGetter), ExportSummary(ExportSummary),
426  ImportSummary(ImportSummary), Int8Ty(Type::getInt8Ty(M.getContext())),
427  Int8PtrTy(Type::getInt8PtrTy(M.getContext())),
429  Int64Ty(Type::getInt64Ty(M.getContext())),
430  IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
431  RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
432  assert(!(ExportSummary && ImportSummary));
433  }
434 
435  bool areRemarksEnabled();
436 
437  void scanTypeTestUsers(Function *TypeTestFunc, Function *AssumeFunc);
438  void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
439 
440  void buildTypeIdentifierMap(
441  std::vector<VTableBits> &Bits,
442  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
443  Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
444  bool
445  tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
446  const std::set<TypeMemberInfo> &TypeMemberInfos,
447  uint64_t ByteOffset);
448 
449  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
450  bool &IsExported);
451  bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
452  VTableSlotInfo &SlotInfo,
454 
455  bool tryEvaluateFunctionsWithArgs(
456  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
458 
459  void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
460  uint64_t TheRetVal);
461  bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
462  CallSiteInfo &CSInfo,
464 
465  // Returns the global symbol name that is used to export information about the
466  // given vtable slot and list of arguments.
467  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
468  StringRef Name);
469 
470  bool shouldExportConstantsAsAbsoluteSymbols();
471 
472  // This function is called during the export phase to create a symbol
473  // definition containing information about the given vtable slot and list of
474  // arguments.
475  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
476  Constant *C);
477  void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
478  uint32_t Const, uint32_t &Storage);
479 
480  // This function is called during the import phase to create a reference to
481  // the symbol definition created during the export phase.
482  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
483  StringRef Name);
484  Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
485  StringRef Name, IntegerType *IntTy,
486  uint32_t Storage);
487 
488  void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
489  Constant *UniqueMemberAddr);
490  bool tryUniqueRetValOpt(unsigned BitWidth,
491  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
492  CallSiteInfo &CSInfo,
494  VTableSlot Slot, ArrayRef<uint64_t> Args);
495 
496  void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
497  Constant *Byte, Constant *Bit);
498  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
499  VTableSlotInfo &SlotInfo,
500  WholeProgramDevirtResolution *Res, VTableSlot Slot);
501 
502  void rebuildGlobal(VTableBits &B);
503 
504  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
505  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
506 
507  // If we were able to eliminate all unsafe uses for a type checked load,
508  // eliminate the associated type tests by replacing them with true.
509  void removeRedundantTypeTests();
510 
511  bool run();
512 
513  // Lower the module using the action and summary passed as command line
514  // arguments. For testing purposes only.
515  static bool runForTesting(
516  Module &M, function_ref<AAResults &(Function &)> AARGetter,
518 };
519 
520 struct WholeProgramDevirt : public ModulePass {
521  static char ID;
522 
523  bool UseCommandLine = false;
524 
525  ModuleSummaryIndex *ExportSummary;
526  const ModuleSummaryIndex *ImportSummary;
527 
528  WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) {
530  }
531 
532  WholeProgramDevirt(ModuleSummaryIndex *ExportSummary,
533  const ModuleSummaryIndex *ImportSummary)
534  : ModulePass(ID), ExportSummary(ExportSummary),
535  ImportSummary(ImportSummary) {
537  }
538 
539  bool runOnModule(Module &M) override {
540  if (skipModule(M))
541  return false;
542 
544 
545  if (UseCommandLine)
546  return DevirtModule::runForTesting(M, LegacyAARGetter(*this), OREGetter);
547 
548  return DevirtModule(M, LegacyAARGetter(*this), OREGetter, ExportSummary,
549  ImportSummary)
550  .run();
551  }
552 
553  void getAnalysisUsage(AnalysisUsage &AU) const override {
556  }
557 };
558 
559 } // end anonymous namespace
560 
561 INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
562  "Whole program devirtualization", false, false)
566  "Whole program devirtualization", false, false)
567 char WholeProgramDevirt::ID = 0;
568 
569 ModulePass *
571  const ModuleSummaryIndex *ImportSummary) {
572  return new WholeProgramDevirt(ExportSummary, ImportSummary);
573 }
574 
576  ModuleAnalysisManager &AM) {
577  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
578  auto AARGetter = [&](Function &F) -> AAResults & {
579  return FAM.getResult<AAManager>(F);
580  };
581  auto OREGetter = [&](Function *F) -> OptimizationRemarkEmitter & {
582  return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*F);
583  };
584  if (!DevirtModule(M, AARGetter, OREGetter, nullptr, nullptr).run())
585  return PreservedAnalyses::all();
586  return PreservedAnalyses::none();
587 }
588 
589 bool DevirtModule::runForTesting(
590  Module &M, function_ref<AAResults &(Function &)> AARGetter,
592  ModuleSummaryIndex Summary;
593 
594  // Handle the command-line summary arguments. This code is for testing
595  // purposes only, so we handle errors directly.
596  if (!ClReadSummary.empty()) {
597  ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
598  ": ");
599  auto ReadSummaryFile =
601 
602  yaml::Input In(ReadSummaryFile->getBuffer());
603  In >> Summary;
604  ExitOnErr(errorCodeToError(In.error()));
605  }
606 
607  bool Changed =
608  DevirtModule(
609  M, AARGetter, OREGetter,
610  ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
611  ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
612  .run();
613 
614  if (!ClWriteSummary.empty()) {
615  ExitOnError ExitOnErr(
616  "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
617  std::error_code EC;
619  ExitOnErr(errorCodeToError(EC));
620 
621  yaml::Output Out(OS);
622  Out << Summary;
623  }
624 
625  return Changed;
626 }
627 
628 void DevirtModule::buildTypeIdentifierMap(
629  std::vector<VTableBits> &Bits,
630  DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {
632  Bits.reserve(M.getGlobalList().size());
634  for (GlobalVariable &GV : M.globals()) {
635  Types.clear();
636  GV.getMetadata(LLVMContext::MD_type, Types);
637  if (Types.empty())
638  continue;
639 
640  VTableBits *&BitsPtr = GVToBits[&GV];
641  if (!BitsPtr) {
642  Bits.emplace_back();
643  Bits.back().GV = &GV;
644  Bits.back().ObjectSize =
645  M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
646  BitsPtr = &Bits.back();
647  }
648 
649  for (MDNode *Type : Types) {
650  auto TypeID = Type->getOperand(1).get();
651 
652  uint64_t Offset =
653  cast<ConstantInt>(
654  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
655  ->getZExtValue();
656 
657  TypeIdMap[TypeID].insert({BitsPtr, Offset});
658  }
659  }
660 }
661 
662 Constant *DevirtModule::getPointerAtOffset(Constant *I, uint64_t Offset) {
663  if (I->getType()->isPointerTy()) {
664  if (Offset == 0)
665  return I;
666  return nullptr;
667  }
668 
669  const DataLayout &DL = M.getDataLayout();
670 
671  if (auto *C = dyn_cast<ConstantStruct>(I)) {
672  const StructLayout *SL = DL.getStructLayout(C->getType());
673  if (Offset >= SL->getSizeInBytes())
674  return nullptr;
675 
676  unsigned Op = SL->getElementContainingOffset(Offset);
677  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
678  Offset - SL->getElementOffset(Op));
679  }
680  if (auto *C = dyn_cast<ConstantArray>(I)) {
681  ArrayType *VTableTy = C->getType();
682  uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
683 
684  unsigned Op = Offset / ElemSize;
685  if (Op >= C->getNumOperands())
686  return nullptr;
687 
688  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
689  Offset % ElemSize);
690  }
691  return nullptr;
692 }
693 
694 bool DevirtModule::tryFindVirtualCallTargets(
695  std::vector<VirtualCallTarget> &TargetsForSlot,
696  const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
697  for (const TypeMemberInfo &TM : TypeMemberInfos) {
698  if (!TM.Bits->GV->isConstant())
699  return false;
700 
701  Constant *Ptr = getPointerAtOffset(TM.Bits->GV->getInitializer(),
702  TM.Offset + ByteOffset);
703  if (!Ptr)
704  return false;
705 
706  auto Fn = dyn_cast<Function>(Ptr->stripPointerCasts());
707  if (!Fn)
708  return false;
709 
710  // We can disregard __cxa_pure_virtual as a possible call target, as
711  // calls to pure virtuals are UB.
712  if (Fn->getName() == "__cxa_pure_virtual")
713  continue;
714 
715  TargetsForSlot.push_back({Fn, &TM});
716  }
717 
718  // Give up if we couldn't find any targets.
719  return !TargetsForSlot.empty();
720 }
721 
722 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
723  Constant *TheFn, bool &IsExported) {
724  auto Apply = [&](CallSiteInfo &CSInfo) {
725  for (auto &&VCallSite : CSInfo.CallSites) {
726  if (RemarksEnabled)
727  VCallSite.emitRemark("single-impl", TheFn->getName(), OREGetter);
728  VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
729  TheFn, VCallSite.CS.getCalledValue()->getType()));
730  // This use is no longer unsafe.
731  if (VCallSite.NumUnsafeUses)
732  --*VCallSite.NumUnsafeUses;
733  }
734  if (CSInfo.isExported()) {
735  IsExported = true;
736  CSInfo.markDevirt();
737  }
738  };
739  Apply(SlotInfo.CSInfo);
740  for (auto &P : SlotInfo.ConstCSInfo)
741  Apply(P.second);
742 }
743 
744 bool DevirtModule::trySingleImplDevirt(
745  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
746  VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
747  // See if the program contains a single implementation of this virtual
748  // function.
749  Function *TheFn = TargetsForSlot[0].Fn;
750  for (auto &&Target : TargetsForSlot)
751  if (TheFn != Target.Fn)
752  return false;
753 
754  // If so, update each call site to call that implementation directly.
755  if (RemarksEnabled)
756  TargetsForSlot[0].WasDevirt = true;
757 
758  bool IsExported = false;
759  applySingleImplDevirt(SlotInfo, TheFn, IsExported);
760  if (!IsExported)
761  return false;
762 
763  // If the only implementation has local linkage, we must promote to external
764  // to make it visible to thin LTO objects. We can only get here during the
765  // ThinLTO export phase.
766  if (TheFn->hasLocalLinkage()) {
767  std::string NewName = (TheFn->getName() + "$merged").str();
768 
769  // Since we are renaming the function, any comdats with the same name must
770  // also be renamed. This is required when targeting COFF, as the comdat name
771  // must match one of the names of the symbols in the comdat.
772  if (Comdat *C = TheFn->getComdat()) {
773  if (C->getName() == TheFn->getName()) {
774  Comdat *NewC = M.getOrInsertComdat(NewName);
775  NewC->setSelectionKind(C->getSelectionKind());
776  for (GlobalObject &GO : M.global_objects())
777  if (GO.getComdat() == C)
778  GO.setComdat(NewC);
779  }
780  }
781 
784  TheFn->setName(NewName);
785  }
786 
788  Res->SingleImplName = TheFn->getName();
789 
790  return true;
791 }
792 
793 bool DevirtModule::tryEvaluateFunctionsWithArgs(
794  MutableArrayRef<VirtualCallTarget> TargetsForSlot,
796  // Evaluate each function and store the result in each target's RetVal
797  // field.
798  for (VirtualCallTarget &Target : TargetsForSlot) {
799  if (Target.Fn->arg_size() != Args.size() + 1)
800  return false;
801 
802  Evaluator Eval(M.getDataLayout(), nullptr);
804  EvalArgs.push_back(
805  Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
806  for (unsigned I = 0; I != Args.size(); ++I) {
807  auto *ArgTy = dyn_cast<IntegerType>(
808  Target.Fn->getFunctionType()->getParamType(I + 1));
809  if (!ArgTy)
810  return false;
811  EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
812  }
813 
814  Constant *RetVal;
815  if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
816  !isa<ConstantInt>(RetVal))
817  return false;
818  Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
819  }
820  return true;
821 }
822 
823 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
824  uint64_t TheRetVal) {
825  for (auto Call : CSInfo.CallSites)
826  Call.replaceAndErase(
827  "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
828  ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
829  CSInfo.markDevirt();
830 }
831 
832 bool DevirtModule::tryUniformRetValOpt(
833  MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
835  // Uniform return value optimization. If all functions return the same
836  // constant, replace all calls with that constant.
837  uint64_t TheRetVal = TargetsForSlot[0].RetVal;
838  for (const VirtualCallTarget &Target : TargetsForSlot)
839  if (Target.RetVal != TheRetVal)
840  return false;
841 
842  if (CSInfo.isExported()) {
844  Res->Info = TheRetVal;
845  }
846 
847  applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
848  if (RemarksEnabled)
849  for (auto &&Target : TargetsForSlot)
850  Target.WasDevirt = true;
851  return true;
852 }
853 
854 std::string DevirtModule::getGlobalName(VTableSlot Slot,
855  ArrayRef<uint64_t> Args,
856  StringRef Name) {
857  std::string FullName = "__typeid_";
858  raw_string_ostream OS(FullName);
859  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
860  for (uint64_t Arg : Args)
861  OS << '_' << Arg;
862  OS << '_' << Name;
863  return OS.str();
864 }
865 
866 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
867  Triple T(M.getTargetTriple());
868  return (T.getArch() == Triple::x86 || T.getArch() == Triple::x86_64) &&
869  T.getObjectFormat() == Triple::ELF;
870 }
871 
872 void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
873  StringRef Name, Constant *C) {
875  getGlobalName(Slot, Args, Name), C, &M);
877 }
878 
879 void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
880  StringRef Name, uint32_t Const,
881  uint32_t &Storage) {
882  if (shouldExportConstantsAsAbsoluteSymbols()) {
883  exportGlobal(
884  Slot, Args, Name,
886  return;
887  }
888 
889  Storage = Const;
890 }
891 
892 Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
893  StringRef Name) {
894  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
895  auto *GV = dyn_cast<GlobalVariable>(C);
896  if (GV)
898  return C;
899 }
900 
901 Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
902  StringRef Name, IntegerType *IntTy,
903  uint32_t Storage) {
904  if (!shouldExportConstantsAsAbsoluteSymbols())
905  return ConstantInt::get(IntTy, Storage);
906 
907  Constant *C = importGlobal(Slot, Args, Name);
908  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
909  C = ConstantExpr::getPtrToInt(C, IntTy);
910 
911  // We only need to set metadata if the global is newly created, in which
912  // case it would not have hidden visibility.
913  if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
914  return C;
915 
916  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
917  auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
918  auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
919  GV->setMetadata(LLVMContext::MD_absolute_symbol,
920  MDNode::get(M.getContext(), {MinC, MaxC}));
921  };
922  unsigned AbsWidth = IntTy->getBitWidth();
923  if (AbsWidth == IntPtrTy->getBitWidth())
924  SetAbsRange(~0ull, ~0ull); // Full set.
925  else
926  SetAbsRange(0, 1ull << AbsWidth);
927  return C;
928 }
929 
930 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
931  bool IsOne,
932  Constant *UniqueMemberAddr) {
933  for (auto &&Call : CSInfo.CallSites) {
934  IRBuilder<> B(Call.CS.getInstruction());
935  Value *Cmp =
936  B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
937  B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
938  Cmp = B.CreateZExt(Cmp, Call.CS->getType());
939  Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
940  Cmp);
941  }
942  CSInfo.markDevirt();
943 }
944 
945 bool DevirtModule::tryUniqueRetValOpt(
946  unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
947  CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
948  VTableSlot Slot, ArrayRef<uint64_t> Args) {
949  // IsOne controls whether we look for a 0 or a 1.
950  auto tryUniqueRetValOptFor = [&](bool IsOne) {
951  const TypeMemberInfo *UniqueMember = nullptr;
952  for (const VirtualCallTarget &Target : TargetsForSlot) {
953  if (Target.RetVal == (IsOne ? 1 : 0)) {
954  if (UniqueMember)
955  return false;
956  UniqueMember = Target.TM;
957  }
958  }
959 
960  // We should have found a unique member or bailed out by now. We already
961  // checked for a uniform return value in tryUniformRetValOpt.
962  assert(UniqueMember);
963 
964  Constant *UniqueMemberAddr =
965  ConstantExpr::getBitCast(UniqueMember->Bits->GV, Int8PtrTy);
966  UniqueMemberAddr = ConstantExpr::getGetElementPtr(
967  Int8Ty, UniqueMemberAddr,
968  ConstantInt::get(Int64Ty, UniqueMember->Offset));
969 
970  if (CSInfo.isExported()) {
972  Res->Info = IsOne;
973 
974  exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
975  }
976 
977  // Replace each call with the comparison.
978  applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
979  UniqueMemberAddr);
980 
981  // Update devirtualization statistics for targets.
982  if (RemarksEnabled)
983  for (auto &&Target : TargetsForSlot)
984  Target.WasDevirt = true;
985 
986  return true;
987  };
988 
989  if (BitWidth == 1) {
990  if (tryUniqueRetValOptFor(true))
991  return true;
992  if (tryUniqueRetValOptFor(false))
993  return true;
994  }
995  return false;
996 }
997 
998 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
999  Constant *Byte, Constant *Bit) {
1000  for (auto Call : CSInfo.CallSites) {
1001  auto *RetType = cast<IntegerType>(Call.CS.getType());
1002  IRBuilder<> B(Call.CS.getInstruction());
1003  Value *Addr =
1004  B.CreateGEP(Int8Ty, B.CreateBitCast(Call.VTable, Int8PtrTy), Byte);
1005  if (RetType->getBitWidth() == 1) {
1006  Value *Bits = B.CreateLoad(Addr);
1007  Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1008  auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1009  Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1010  OREGetter, IsBitSet);
1011  } else {
1012  Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
1013  Value *Val = B.CreateLoad(RetType, ValAddr);
1014  Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1015  OREGetter, Val);
1016  }
1017  }
1018  CSInfo.markDevirt();
1019 }
1020 
1021 bool DevirtModule::tryVirtualConstProp(
1022  MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
1023  WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1024  // This only works if the function returns an integer.
1025  auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1026  if (!RetType)
1027  return false;
1028  unsigned BitWidth = RetType->getBitWidth();
1029  if (BitWidth > 64)
1030  return false;
1031 
1032  // Make sure that each function is defined, does not access memory, takes at
1033  // least one argument, does not use its first argument (which we assume is
1034  // 'this'), and has the same return type.
1035  //
1036  // Note that we test whether this copy of the function is readnone, rather
1037  // than testing function attributes, which must hold for any copy of the
1038  // function, even a less optimized version substituted at link time. This is
1039  // sound because the virtual constant propagation optimizations effectively
1040  // inline all implementations of the virtual function into each call site,
1041  // rather than using function attributes to perform local optimization.
1042  for (VirtualCallTarget &Target : TargetsForSlot) {
1043  if (Target.Fn->isDeclaration() ||
1044  computeFunctionBodyMemoryAccess(*Target.Fn, AARGetter(*Target.Fn)) !=
1045  MAK_ReadNone ||
1046  Target.Fn->arg_empty() || !Target.Fn->arg_begin()->use_empty() ||
1047  Target.Fn->getReturnType() != RetType)
1048  return false;
1049  }
1050 
1051  for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1052  if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1053  continue;
1054 
1055  WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1056  if (Res)
1057  ResByArg = &Res->ResByArg[CSByConstantArg.first];
1058 
1059  if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1060  continue;
1061 
1062  if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1063  ResByArg, Slot, CSByConstantArg.first))
1064  continue;
1065 
1066  // Find an allocation offset in bits in all vtables associated with the
1067  // type.
1068  uint64_t AllocBefore =
1069  findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
1070  uint64_t AllocAfter =
1071  findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
1072 
1073  // Calculate the total amount of padding needed to store a value at both
1074  // ends of the object.
1075  uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1076  for (auto &&Target : TargetsForSlot) {
1077  TotalPaddingBefore += std::max<int64_t>(
1078  (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1079  TotalPaddingAfter += std::max<int64_t>(
1080  (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1081  }
1082 
1083  // If the amount of padding is too large, give up.
1084  // FIXME: do something smarter here.
1085  if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1086  continue;
1087 
1088  // Calculate the offset to the value as a (possibly negative) byte offset
1089  // and (if applicable) a bit offset, and store the values in the targets.
1090  int64_t OffsetByte;
1091  uint64_t OffsetBit;
1092  if (TotalPaddingBefore <= TotalPaddingAfter)
1093  setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
1094  OffsetBit);
1095  else
1096  setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
1097  OffsetBit);
1098 
1099  if (RemarksEnabled)
1100  for (auto &&Target : TargetsForSlot)
1101  Target.WasDevirt = true;
1102 
1103 
1104  if (CSByConstantArg.second.isExported()) {
1106  exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
1107  ResByArg->Byte);
1108  exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
1109  ResByArg->Bit);
1110  }
1111 
1112  // Rewrite each call to a load from OffsetByte/OffsetBit.
1113  Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
1114  Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
1115  applyVirtualConstProp(CSByConstantArg.second,
1116  TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1117  }
1118  return true;
1119 }
1120 
1121 void DevirtModule::rebuildGlobal(VTableBits &B) {
1122  if (B.Before.Bytes.empty() && B.After.Bytes.empty())
1123  return;
1124 
1125  // Align each byte array to pointer width.
1126  unsigned PointerSize = M.getDataLayout().getPointerSize();
1127  B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
1128  B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));
1129 
1130  // Before was stored in reverse order; flip it now.
1131  for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
1132  std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);
1133 
1134  // Build an anonymous global containing the before bytes, followed by the
1135  // original initializer, followed by the after bytes.
1136  auto NewInit = ConstantStruct::getAnon(
1138  B.GV->getInitializer(),
1140  auto NewGV =
1141  new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
1142  GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
1143  NewGV->setSection(B.GV->getSection());
1144  NewGV->setComdat(B.GV->getComdat());
1145 
1146  // Copy the original vtable's metadata to the anonymous global, adjusting
1147  // offsets as required.
1148  NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
1149 
1150  // Build an alias named after the original global, pointing at the second
1151  // element (the original initializer).
1152  auto Alias = GlobalAlias::create(
1153  B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
1155  NewInit->getType(), NewGV,
1157  ConstantInt::get(Int32Ty, 1)}),
1158  &M);
1159  Alias->setVisibility(B.GV->getVisibility());
1160  Alias->takeName(B.GV);
1161 
1162  B.GV->replaceAllUsesWith(Alias);
1163  B.GV->eraseFromParent();
1164 }
1165 
1166 bool DevirtModule::areRemarksEnabled() {
1167  const auto &FL = M.getFunctionList();
1168  if (FL.empty())
1169  return false;
1170  const Function &Fn = FL.front();
1171 
1172  const auto &BBL = Fn.getBasicBlockList();
1173  if (BBL.empty())
1174  return false;
1175  auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &BBL.front());
1176  return DI.isEnabled();
1177 }
1178 
1179 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
1180  Function *AssumeFunc) {
1181  // Find all virtual calls via a virtual table pointer %p under an assumption
1182  // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
1183  // points to a member of the type identifier %md. Group calls by (type ID,
1184  // offset) pair (effectively the identity of the virtual function) and store
1185  // to CallSlots.
1186  DenseSet<Value *> SeenPtrs;
1187  for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
1188  I != E;) {
1189  auto CI = dyn_cast<CallInst>(I->getUser());
1190  ++I;
1191  if (!CI)
1192  continue;
1193 
1194  // Search for virtual calls based on %p and add them to DevirtCalls.
1195  SmallVector<DevirtCallSite, 1> DevirtCalls;
1197  findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
1198 
1199  // If we found any, add them to CallSlots. Only do this if we haven't seen
1200  // the vtable pointer before, as it may have been CSE'd with pointers from
1201  // other call sites, and we don't want to process call sites multiple times.
1202  if (!Assumes.empty()) {
1203  Metadata *TypeId =
1204  cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1205  Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
1206  if (SeenPtrs.insert(Ptr).second) {
1207  for (DevirtCallSite Call : DevirtCalls) {
1208  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS, nullptr);
1209  }
1210  }
1211  }
1212 
1213  // We no longer need the assumes or the type test.
1214  for (auto Assume : Assumes)
1215  Assume->eraseFromParent();
1216  // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
1217  // may use the vtable argument later.
1218  if (CI->use_empty())
1219  CI->eraseFromParent();
1220  }
1221 }
1222 
1223 void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
1224  Function *TypeTestFunc = Intrinsic::getDeclaration(&M, Intrinsic::type_test);
1225 
1226  for (auto I = TypeCheckedLoadFunc->use_begin(),
1227  E = TypeCheckedLoadFunc->use_end();
1228  I != E;) {
1229  auto CI = dyn_cast<CallInst>(I->getUser());
1230  ++I;
1231  if (!CI)
1232  continue;
1233 
1234  Value *Ptr = CI->getArgOperand(0);
1235  Value *Offset = CI->getArgOperand(1);
1236  Value *TypeIdValue = CI->getArgOperand(2);
1237  Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1238 
1239  SmallVector<DevirtCallSite, 1> DevirtCalls;
1240  SmallVector<Instruction *, 1> LoadedPtrs;
1242  bool HasNonCallUses = false;
1243  findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
1244  HasNonCallUses, CI);
1245 
1246  // Start by generating "pessimistic" code that explicitly loads the function
1247  // pointer from the vtable and performs the type check. If possible, we will
1248  // eliminate the load and the type check later.
1249 
1250  // If possible, only generate the load at the point where it is used.
1251  // This helps avoid unnecessary spills.
1252  IRBuilder<> LoadB(
1253  (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1254  Value *GEP = LoadB.CreateGEP(Int8Ty, Ptr, Offset);
1255  Value *GEPPtr = LoadB.CreateBitCast(GEP, PointerType::getUnqual(Int8PtrTy));
1256  Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1257 
1258  for (Instruction *LoadedPtr : LoadedPtrs) {
1259  LoadedPtr->replaceAllUsesWith(LoadedValue);
1260  LoadedPtr->eraseFromParent();
1261  }
1262 
1263  // Likewise for the type test.
1264  IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1265  CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1266 
1267  for (Instruction *Pred : Preds) {
1268  Pred->replaceAllUsesWith(TypeTestCall);
1269  Pred->eraseFromParent();
1270  }
1271 
1272  // We have already erased any extractvalue instructions that refer to the
1273  // intrinsic call, but the intrinsic may have other non-extractvalue uses
1274  // (although this is unlikely). In that case, explicitly build a pair and
1275  // RAUW it.
1276  if (!CI->use_empty()) {
1277  Value *Pair = UndefValue::get(CI->getType());
1278  IRBuilder<> B(CI);
1279  Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
1280  Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
1281  CI->replaceAllUsesWith(Pair);
1282  }
1283 
1284  // The number of unsafe uses is initially the number of uses.
1285  auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1286  NumUnsafeUses = DevirtCalls.size();
1287 
1288  // If the function pointer has a non-call user, we cannot eliminate the type
1289  // check, as one of those users may eventually call the pointer. Increment
1290  // the unsafe use count to make sure it cannot reach zero.
1291  if (HasNonCallUses)
1292  ++NumUnsafeUses;
1293  for (DevirtCallSite Call : DevirtCalls) {
1294  CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
1295  &NumUnsafeUses);
1296  }
1297 
1298  CI->eraseFromParent();
1299  }
1300 }
1301 
1302 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1303  const TypeIdSummary *TidSummary =
1304  ImportSummary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString());
1305  if (!TidSummary)
1306  return;
1307  auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
1308  if (ResI == TidSummary->WPDRes.end())
1309  return;
1310  const WholeProgramDevirtResolution &Res = ResI->second;
1311 
1313  // The type of the function in the declaration is irrelevant because every
1314  // call site will cast it to the correct type.
1315  auto *SingleImpl = M.getOrInsertFunction(
1317 
1318  // This is the import phase so we should not be exporting anything.
1319  bool IsExported = false;
1320  applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1321  assert(!IsExported);
1322  }
1323 
1324  for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1325  auto I = Res.ResByArg.find(CSByConstantArg.first);
1326  if (I == Res.ResByArg.end())
1327  continue;
1328  auto &ResByArg = I->second;
1329  // FIXME: We should figure out what to do about the "function name" argument
1330  // to the apply* functions, as the function names are unavailable during the
1331  // importing phase. For now we just pass the empty string. This does not
1332  // impact correctness because the function names are just used for remarks.
1333  switch (ResByArg.TheKind) {
1335  applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
1336  break;
1338  Constant *UniqueMemberAddr =
1339  importGlobal(Slot, CSByConstantArg.first, "unique_member");
1340  applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
1341  UniqueMemberAddr);
1342  break;
1343  }
1345  Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
1346  Int32Ty, ResByArg.Byte);
1347  Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
1348  ResByArg.Bit);
1349  applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
1350  }
1351  default:
1352  break;
1353  }
1354  }
1355 }
1356 
1357 void DevirtModule::removeRedundantTypeTests() {
1358  auto True = ConstantInt::getTrue(M.getContext());
1359  for (auto &&U : NumUnsafeUsesForTypeTest) {
1360  if (U.second == 0) {
1361  U.first->replaceAllUsesWith(True);
1362  U.first->eraseFromParent();
1363  }
1364  }
1365 }
1366 
1367 bool DevirtModule::run() {
1368  Function *TypeTestFunc =
1369  M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1370  Function *TypeCheckedLoadFunc =
1371  M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
1372  Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
1373 
1374  // Normally if there are no users of the devirtualization intrinsics in the
1375  // module, this pass has nothing to do. But if we are exporting, we also need
1376  // to handle any users that appear only in the function summaries.
1377  if (!ExportSummary &&
1378  (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
1379  AssumeFunc->use_empty()) &&
1380  (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
1381  return false;
1382 
1383  if (TypeTestFunc && AssumeFunc)
1384  scanTypeTestUsers(TypeTestFunc, AssumeFunc);
1385 
1386  if (TypeCheckedLoadFunc)
1387  scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
1388 
1389  if (ImportSummary) {
1390  for (auto &S : CallSlots)
1391  importResolution(S.first, S.second);
1392 
1393  removeRedundantTypeTests();
1394 
1395  // The rest of the code is only necessary when exporting or during regular
1396  // LTO, so we are done.
1397  return true;
1398  }
1399 
1400  // Rebuild type metadata into a map for easy lookup.
1401  std::vector<VTableBits> Bits;
1403  buildTypeIdentifierMap(Bits, TypeIdMap);
1404  if (TypeIdMap.empty())
1405  return true;
1406 
1407  // Collect information from summary about which calls to try to devirtualize.
1408  if (ExportSummary) {
1410  for (auto &P : TypeIdMap) {
1411  if (auto *TypeId = dyn_cast<MDString>(P.first))
1412  MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1413  TypeId);
1414  }
1415 
1416  for (auto &P : *ExportSummary) {
1417  for (auto &S : P.second.SummaryList) {
1418  auto *FS = dyn_cast<FunctionSummary>(S.get());
1419  if (!FS)
1420  continue;
1421  // FIXME: Only add live functions.
1422  for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
1423  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1424  CallSlots[{MD, VF.Offset}].CSInfo.SummaryHasTypeTestAssumeUsers =
1425  true;
1426  }
1427  }
1428  for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
1429  for (Metadata *MD : MetadataByGUID[VF.GUID]) {
1430  CallSlots[{MD, VF.Offset}]
1431  .CSInfo.SummaryTypeCheckedLoadUsers.push_back(FS);
1432  }
1433  }
1434  for (const FunctionSummary::ConstVCall &VC :
1435  FS->type_test_assume_const_vcalls()) {
1436  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1437  CallSlots[{MD, VC.VFunc.Offset}]
1438  .ConstCSInfo[VC.Args]
1439  .SummaryHasTypeTestAssumeUsers = true;
1440  }
1441  }
1442  for (const FunctionSummary::ConstVCall &VC :
1443  FS->type_checked_load_const_vcalls()) {
1444  for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
1445  CallSlots[{MD, VC.VFunc.Offset}]
1446  .ConstCSInfo[VC.Args]
1447  .SummaryTypeCheckedLoadUsers.push_back(FS);
1448  }
1449  }
1450  }
1451  }
1452  }
1453 
1454  // For each (type, offset) pair:
1455  bool DidVirtualConstProp = false;
1456  std::map<std::string, Function*> DevirtTargets;
1457  for (auto &S : CallSlots) {
1458  // Search each of the members of the type identifier for the virtual
1459  // function implementation at offset S.first.ByteOffset, and add to
1460  // TargetsForSlot.
1461  std::vector<VirtualCallTarget> TargetsForSlot;
1462  if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
1463  S.first.ByteOffset)) {
1464  WholeProgramDevirtResolution *Res = nullptr;
1465  if (ExportSummary && isa<MDString>(S.first.TypeID))
1466  Res = &ExportSummary
1467  ->getOrInsertTypeIdSummary(
1468  cast<MDString>(S.first.TypeID)->getString())
1469  .WPDRes[S.first.ByteOffset];
1470 
1471  if (!trySingleImplDevirt(TargetsForSlot, S.second, Res) &&
1472  tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first))
1473  DidVirtualConstProp = true;
1474 
1475  // Collect functions devirtualized at least for one call site for stats.
1476  if (RemarksEnabled)
1477  for (const auto &T : TargetsForSlot)
1478  if (T.WasDevirt)
1479  DevirtTargets[T.Fn->getName()] = T.Fn;
1480  }
1481 
1482  // CFI-specific: if we are exporting and any llvm.type.checked.load
1483  // intrinsics were *not* devirtualized, we need to add the resulting
1484  // llvm.type.test intrinsics to the function summaries so that the
1485  // LowerTypeTests pass will export them.
1486  if (ExportSummary && isa<MDString>(S.first.TypeID)) {
1487  auto GUID =
1488  GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
1489  for (auto FS : S.second.CSInfo.SummaryTypeCheckedLoadUsers)
1490  FS->addTypeTest(GUID);
1491  for (auto &CCS : S.second.ConstCSInfo)
1492  for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
1493  FS->addTypeTest(GUID);
1494  }
1495  }
1496 
1497  if (RemarksEnabled) {
1498  // Generate remarks for each devirtualized function.
1499  for (const auto &DT : DevirtTargets) {
1500  Function *F = DT.second;
1501 
1502  // In the new pass manager, we can request the optimization
1503  // remark emitter pass on a per-function-basis, which the
1504  // OREGetter will do for us.
1505  // In the old pass manager, this is harder, so we just build
1506  // a optimization remark emitter on the fly, when we need it.
1507  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
1509  if (OREGetter)
1510  ORE = &OREGetter(F);
1511  else {
1512  OwnedORE = make_unique<OptimizationRemarkEmitter>(F);
1513  ORE = OwnedORE.get();
1514  }
1515 
1516  using namespace ore;
1517  ORE->emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
1518  << "devirtualized " << NV("FunctionName", F->getName()));
1519  }
1520  }
1521 
1522  removeRedundantTypeTests();
1523 
1524  // Rebuild each global we touched as part of virtual constant propagation to
1525  // include the before and after bytes.
1526  if (DidVirtualConstProp)
1527  for (VTableBits &B : Bits)
1528  rebuildGlobal(B);
1529 
1530  return true;
1531 }
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:231
uint64_t CallInst * C
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:90
void push_back(const T &Elt)
Definition: SmallVector.h:212
use_iterator use_end()
Definition: Value.h:348
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
const std::string & getTargetTriple() const
Get the target triple which is a string describing the target host.
Definition: Module.h:233
bool empty() const
Definition: Function.h:594
bool hasLocalLinkage() const
Definition: GlobalValue.h:427
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
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:687
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Constant * getOrInsertFunction(StringRef Name, FunctionType *T, AttributeList AttributeList)
Look up the specified function in the module symbol table.
Definition: Module.cpp:142
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
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:1115
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
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:562
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:1108
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:89
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1665
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
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:862
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:677
const GlobalListType & getGlobalList() const
Get the Module&#39;s list of global variables (constant).
Definition: Module.h:498
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:207
Export information to summary.
const char * getName() const
getName - Get the target name.
iterator_range< global_object_iterator > global_objects()
Definition: Module.h:636
bool arg_empty() const
Definition: CallSite.h:218
void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
void findDevirtualizableCallsForTypeTest(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< CallInst *> &Assumes, const CallInst *CI)
Given a call to the intrinsic .type.test, find all devirtualizable call sites based on the call and r...
AnalysisUsage & addRequired()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:491
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:591
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
static Constant * get(LLVMContext &Context, ArrayRef< uint8_t > Elts)
get() constructors - Return a constant with array type with an element count and element type matchin...
Definition: Constants.cpp:2396
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:237
The returned value is undefined.
Definition: MathExtras.h:38
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:668
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
InstrTy * getInstruction() const
Definition: CallSite.h:92
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
static bool isEqual(const VTableSlot &LHS, const VTableSlot &RHS)
enum llvm::WholeProgramDevirtResolution::Kind TheKind
The Input class is used to parse a yaml document into in-memory structs and vectors.
Definition: YAMLTraits.h:1108
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1448
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
#define T
Class to represent array types.
Definition: DerivedTypes.h:369
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:441
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
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:408
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:980
Value * getOperand(unsigned i) const
Definition: User.h:154
Class to represent pointers.
Definition: DerivedTypes.h:467
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:1678
LoadInst * CreateLoad(Value *Ptr, const char *Name)
Definition: IRBuilder.h:1168
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:702
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
#define P(N)
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.
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:112
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:225
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
Import information from summary.
const FunctionListType & getFunctionList() const
Get the Module&#39;s list of functions (constant).
Definition: Module.h:507
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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.
Constant * getOrInsertGlobal(StringRef Name, Type *Ty)
Look up the specified global in the module symbol table.
Definition: Module.cpp:202
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:78
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:626
unsigned getPointerSize(unsigned AS=0) const
Layout pointer size FIXME: The defaults need to be removed once all of the backends/clients are updat...
Definition: DataLayout.cpp:605
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:221
#define DEBUG_TYPE
A manager for alias analyses.
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
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:336
INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt", "Whole program devirtualization", false, false) INITIALIZE_PASS_END(WholeProgramDevirt
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
Definition: Error.h:1070
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
Type::TypeID TypeID
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:100
Class to represent integer types.
Definition: DerivedTypes.h:40
enum llvm::WholeProgramDevirtResolution::ByArg::Kind TheKind
The Output class is used to generate a yaml document from in-memory structs and vectors.
Definition: YAMLTraits.h:1260
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
const Constant * stripPointerCasts() const
Definition: Constant.h:153
Comdat * getOrInsertComdat(StringRef Name)
Return the Comdat in the module with the specified name.
Definition: Module.cpp:467
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:558
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:478
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:38
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1227
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:176
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:43
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
void findDevirtualizableCallsForTypeCheckedLoad(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< Instruction *> &LoadedPtrs, SmallVectorImpl< Instruction *> &Preds, bool &HasNonCallUses, const CallInst *CI)
Given a call to the intrinsic .type.checked.load, find all devirtualizable call sites based on the ca...
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:864
Module.h This file contains the declarations for the Module class.
Single implementation devirtualization.
uint64_t getSizeInBytes() const
Definition: DataLayout.h:499
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:560
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:516
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:97
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:436
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:172
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
wholeprogramdevirt
Target - Wrapper for Target specific information.
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:491
The file should be opened in text mode on platforms that make this distinction.
Definition: FileSystem.h:769
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:601
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:403
use_iterator use_begin()
Definition: Value.h:340
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.
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:361
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:513
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:61
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1652
#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:565
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())
const BasicBlock & front() const
Definition: Function.h:595
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:462
aarch64 promote const
LLVM Value Representation.
Definition: Value.h:73
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
static const Function * getParent(const Value *V)
static Constant * getAnon(ArrayRef< Constant *> V, bool Packed=false)
Return an anonymous struct that has the specified elements.
Definition: Constants.h:460
Type * getElementType() const
Definition: DerivedTypes.h:360
iterator_range< global_iterator > globals()
Definition: Module.h:561
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.
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:184
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:328
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:400
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
IntegerType * Int32Ty
CallInst * CreateCall(Value *Callee, ArrayRef< Value *> Args=None, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1663
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:946