brintos / llvm-project-archived public Read only

1//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass implements whole program optimization of virtual calls in cases10// where we know (via !type metadata) that the list of callees is fixed. This11// includes the following:12// - Single implementation devirtualization: if a virtual call has a single13//   possible callee, replace all calls with a direct call to that callee.14// - Virtual constant propagation: if the virtual function's return type is an15//   integer <=64 bits and all possible callees are readnone, for each class and16//   each list of constant arguments: evaluate the function, store the return17//   value alongside the virtual table, and rewrite each virtual call as a load18//   from the virtual table.19// - Uniform return value optimization: if the conditions for virtual constant20//   propagation hold and each function returns the same constant value, replace21//   each virtual call with that constant.22// - Unique return value optimization for i1 return values: if the conditions23//   for virtual constant propagation hold and a single vtable's function24//   returns 0, or a single vtable's function returns 1, replace each virtual25//   call with a comparison of the vptr against that vtable's address.26//27// This pass is intended to be used during the regular/thin and non-LTO28// pipelines:29//30// During regular LTO, the pass determines the best optimization for each31// virtual call and applies the resolutions directly to virtual calls that are32// eligible for virtual call optimization (i.e. calls that use either of the33// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics).34//35// During hybrid Regular/ThinLTO, the pass operates in two phases:36// - Export phase: this is run during the thin link over a single merged module37//   that contains all vtables with !type metadata that participate in the link.38//   The pass computes a resolution for each virtual call and stores it in the39//   type identifier summary.40// - Import phase: this is run during the thin backends over the individual41//   modules. The pass applies the resolutions previously computed during the42//   import phase to each eligible virtual call.43//44// During ThinLTO, the pass operates in two phases:45// - Export phase: this is run during the thin link over the index which46//   contains a summary of all vtables with !type metadata that participate in47//   the link. It computes a resolution for each virtual call and stores it in48//   the type identifier summary. Only single implementation devirtualization49//   is supported.50// - Import phase: (same as with hybrid case above).51//52// During Speculative devirtualization mode -not restricted to LTO-:53// - The pass applies speculative devirtualization without requiring any type of54//   visibility.55// - Skips other features like virtual constant propagation, uniform return56//   value optimization, unique return value optimization and branch funnels as57//   they need LTO.58// - This mode is enabled via 'devirtualize-speculatively' flag.59//60//===----------------------------------------------------------------------===//61 62#include "llvm/Transforms/IPO/WholeProgramDevirt.h"63#include "llvm/ADT/ArrayRef.h"64#include "llvm/ADT/DenseMap.h"65#include "llvm/ADT/DenseMapInfo.h"66#include "llvm/ADT/DenseSet.h"67#include "llvm/ADT/MapVector.h"68#include "llvm/ADT/SmallVector.h"69#include "llvm/ADT/Statistic.h"70#include "llvm/Analysis/AssumptionCache.h"71#include "llvm/Analysis/BasicAliasAnalysis.h"72#include "llvm/Analysis/BlockFrequencyInfo.h"73#include "llvm/Analysis/ModuleSummaryAnalysis.h"74#include "llvm/Analysis/OptimizationRemarkEmitter.h"75#include "llvm/Analysis/ProfileSummaryInfo.h"76#include "llvm/Analysis/TypeMetadataUtils.h"77#include "llvm/Bitcode/BitcodeReader.h"78#include "llvm/Bitcode/BitcodeWriter.h"79#include "llvm/IR/Constants.h"80#include "llvm/IR/DataLayout.h"81#include "llvm/IR/DebugLoc.h"82#include "llvm/IR/DerivedTypes.h"83#include "llvm/IR/DiagnosticInfo.h"84#include "llvm/IR/Dominators.h"85#include "llvm/IR/Function.h"86#include "llvm/IR/GlobalAlias.h"87#include "llvm/IR/GlobalVariable.h"88#include "llvm/IR/IRBuilder.h"89#include "llvm/IR/InstrTypes.h"90#include "llvm/IR/Instruction.h"91#include "llvm/IR/Instructions.h"92#include "llvm/IR/Intrinsics.h"93#include "llvm/IR/LLVMContext.h"94#include "llvm/IR/MDBuilder.h"95#include "llvm/IR/Metadata.h"96#include "llvm/IR/Module.h"97#include "llvm/IR/ModuleSummaryIndexYAML.h"98#include "llvm/IR/PassManager.h"99#include "llvm/IR/ProfDataUtils.h"100#include "llvm/Support/Casting.h"101#include "llvm/Support/CommandLine.h"102#include "llvm/Support/DebugCounter.h"103#include "llvm/Support/Errc.h"104#include "llvm/Support/Error.h"105#include "llvm/Support/FileSystem.h"106#include "llvm/Support/GlobPattern.h"107#include "llvm/Support/TimeProfiler.h"108#include "llvm/TargetParser/Triple.h"109#include "llvm/Transforms/IPO.h"110#include "llvm/Transforms/IPO/FunctionAttrs.h"111#include "llvm/Transforms/Utils/BasicBlockUtils.h"112#include "llvm/Transforms/Utils/CallPromotionUtils.h"113#include "llvm/Transforms/Utils/Evaluator.h"114#include <algorithm>115#include <cmath>116#include <cstddef>117#include <map>118#include <set>119#include <string>120 121using namespace llvm;122using namespace wholeprogramdevirt;123 124#define DEBUG_TYPE "wholeprogramdevirt"125 126STATISTIC(NumDevirtTargets, "Number of whole program devirtualization targets");127STATISTIC(NumSingleImpl, "Number of single implementation devirtualizations");128STATISTIC(NumBranchFunnel, "Number of branch funnels");129STATISTIC(NumUniformRetVal, "Number of uniform return value optimizations");130STATISTIC(NumUniqueRetVal, "Number of unique return value optimizations");131STATISTIC(NumVirtConstProp1Bit,132          "Number of 1 bit virtual constant propagations");133STATISTIC(NumVirtConstProp, "Number of virtual constant propagations");134DEBUG_COUNTER(CallsToDevirt, "calls-to-devirt",135              "Controls how many calls should be devirtualized.");136 137namespace llvm {138 139static cl::opt<PassSummaryAction> ClSummaryAction(140    "wholeprogramdevirt-summary-action",141    cl::desc("What to do with the summary when running this pass"),142    cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),143               clEnumValN(PassSummaryAction::Import, "import",144                          "Import typeid resolutions from summary and globals"),145               clEnumValN(PassSummaryAction::Export, "export",146                          "Export typeid resolutions to summary and globals")),147    cl::Hidden);148 149static cl::opt<std::string> ClReadSummary(150    "wholeprogramdevirt-read-summary",151    cl::desc(152        "Read summary from given bitcode or YAML file before running pass"),153    cl::Hidden);154 155static cl::opt<std::string> ClWriteSummary(156    "wholeprogramdevirt-write-summary",157    cl::desc("Write summary to given bitcode or YAML file after running pass. "158             "Output file format is deduced from extension: *.bc means writing "159             "bitcode, otherwise YAML"),160    cl::Hidden);161 162// TODO: This option eventually should support any public visibility vtables163// with/out LTO.164static cl::opt<bool> ClDevirtualizeSpeculatively(165    "devirtualize-speculatively",166    cl::desc("Enable speculative devirtualization optimization"),167    cl::init(false));168 169static cl::opt<unsigned>170    ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,171                cl::init(10),172                cl::desc("Maximum number of call targets per "173                         "call site to enable branch funnels"));174 175static cl::opt<bool>176    PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,177                       cl::desc("Print index-based devirtualization messages"));178 179/// Provide a way to force enable whole program visibility in tests.180/// This is needed to support legacy tests that don't contain181/// !vcall_visibility metadata (the mere presense of type tests182/// previously implied hidden visibility).183static cl::opt<bool>184    WholeProgramVisibility("whole-program-visibility", cl::Hidden,185                           cl::desc("Enable whole program visibility"));186 187/// Provide a way to force disable whole program for debugging or workarounds,188/// when enabled via the linker.189static cl::opt<bool> DisableWholeProgramVisibility(190    "disable-whole-program-visibility", cl::Hidden,191    cl::desc("Disable whole program visibility (overrides enabling options)"));192 193/// Provide way to prevent certain function from being devirtualized194static cl::list<std::string>195    SkipFunctionNames("wholeprogramdevirt-skip",196                      cl::desc("Prevent function(s) from being devirtualized"),197                      cl::Hidden, cl::CommaSeparated);198 199extern cl::opt<bool> ProfcheckDisableMetadataFixes;200 201} // end namespace llvm202 203/// With Clang, a pure virtual class's deleting destructor is emitted as a204/// `llvm.trap` intrinsic followed by an unreachable IR instruction. In the205/// context of whole program devirtualization, the deleting destructor of a pure206/// virtual class won't be invoked by the source code so safe to skip as a207/// devirtualize target.208///209/// However, not all unreachable functions are safe to skip. In some cases, the210/// program intends to run such functions and terminate, for instance, a unit211/// test may run a death test. A non-test program might (or allowed to) invoke212/// such functions to report failures (whether/when it's a good practice or not213/// is a different topic).214///215/// This option is enabled to keep an unreachable function as a possible216/// devirtualize target to conservatively keep the program behavior.217///218/// TODO: Make a pure virtual class's deleting destructor precisely identifiable219/// in Clang's codegen for more devirtualization in LLVM.220static cl::opt<bool> WholeProgramDevirtKeepUnreachableFunction(221    "wholeprogramdevirt-keep-unreachable-function",222    cl::desc("Regard unreachable functions as possible devirtualize targets."),223    cl::Hidden, cl::init(true));224 225/// Mechanism to add runtime checking of devirtualization decisions, optionally226/// trapping or falling back to indirect call on any that are not correct.227/// Trapping mode is useful for debugging undefined behavior leading to failures228/// with WPD. Fallback mode is useful for ensuring safety when whole program229/// visibility may be compromised.230enum WPDCheckMode { None, Trap, Fallback };231static cl::opt<WPDCheckMode> DevirtCheckMode(232    "wholeprogramdevirt-check", cl::Hidden,233    cl::desc("Type of checking for incorrect devirtualizations"),234    cl::values(clEnumValN(WPDCheckMode::None, "none", "No checking"),235               clEnumValN(WPDCheckMode::Trap, "trap", "Trap when incorrect"),236               clEnumValN(WPDCheckMode::Fallback, "fallback",237                          "Fallback to indirect when incorrect")));238 239namespace {240struct PatternList {241  std::vector<GlobPattern> Patterns;242  template <class T> void init(const T &StringList) {243    for (const auto &S : StringList)244      if (Expected<GlobPattern> Pat = GlobPattern::create(S))245        Patterns.push_back(std::move(*Pat));246  }247  bool match(StringRef S) {248    for (const GlobPattern &P : Patterns)249      if (P.match(S))250        return true;251    return false;252  }253};254} // namespace255 256// Find the minimum offset that we may store a value of size Size bits at. If257// IsAfter is set, look for an offset before the object, otherwise look for an258// offset after the object.259uint64_t260wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,261                                     bool IsAfter, uint64_t Size) {262  // Find a minimum offset taking into account only vtable sizes.263  uint64_t MinByte = 0;264  for (const VirtualCallTarget &Target : Targets) {265    if (IsAfter)266      MinByte = std::max(MinByte, Target.minAfterBytes());267    else268      MinByte = std::max(MinByte, Target.minBeforeBytes());269  }270 271  // Build a vector of arrays of bytes covering, for each target, a slice of the272  // used region (see AccumBitVector::BytesUsed in273  // llvm/Transforms/IPO/WholeProgramDevirt.h) starting at MinByte. Effectively,274  // this aligns the used regions to start at MinByte.275  //276  // In this example, A, B and C are vtables, # is a byte already allocated for277  // a virtual function pointer, AAAA... (etc.) are the used regions for the278  // vtables and Offset(X) is the value computed for the Offset variable below279  // for X.280  //281  //                    Offset(A)282  //                    |       |283  //                            |MinByte284  // A: ################AAAAAAAA|AAAAAAAA285  // B: ########BBBBBBBBBBBBBBBB|BBBB286  // C: ########################|CCCCCCCCCCCCCCCC287  //            |   Offset(B)   |288  //289  // This code produces the slices of A, B and C that appear after the divider290  // at MinByte.291  std::vector<ArrayRef<uint8_t>> Used;292  for (const VirtualCallTarget &Target : Targets) {293    ArrayRef<uint8_t> VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed294                                       : Target.TM->Bits->Before.BytesUsed;295    uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()296                              : MinByte - Target.minBeforeBytes();297 298    // Disregard used regions that are smaller than Offset. These are299    // effectively all-free regions that do not need to be checked.300    if (VTUsed.size() > Offset)301      Used.push_back(VTUsed.slice(Offset));302  }303 304  if (Size == 1) {305    // Find a free bit in each member of Used.306    for (unsigned I = 0;; ++I) {307      uint8_t BitsUsed = 0;308      for (auto &&B : Used)309        if (I < B.size())310          BitsUsed |= B[I];311      if (BitsUsed != 0xff)312        return (MinByte + I) * 8 + llvm::countr_zero(uint8_t(~BitsUsed));313    }314  } else {315    // Find a free (Size/8) byte region in each member of Used.316    // FIXME: see if alignment helps.317    for (unsigned I = 0;; ++I) {318      for (auto &&B : Used) {319        unsigned Byte = 0;320        while ((I + Byte) < B.size() && Byte < (Size / 8)) {321          if (B[I + Byte])322            goto NextI;323          ++Byte;324        }325      }326      // Rounding up ensures the constant is always stored at address we327      // can directly load from without misalignment.328      return alignTo((MinByte + I) * 8, Size);329    NextI:;330    }331  }332}333 334void wholeprogramdevirt::setBeforeReturnValues(335    MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,336    unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {337  if (BitWidth == 1)338    OffsetByte = -(AllocBefore / 8 + 1);339  else340    OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);341  OffsetBit = AllocBefore % 8;342 343  for (VirtualCallTarget &Target : Targets) {344    if (BitWidth == 1)345      Target.setBeforeBit(AllocBefore);346    else347      Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);348  }349}350 351void wholeprogramdevirt::setAfterReturnValues(352    MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,353    unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {354  if (BitWidth == 1)355    OffsetByte = AllocAfter / 8;356  else357    OffsetByte = (AllocAfter + 7) / 8;358  OffsetBit = AllocAfter % 8;359 360  for (VirtualCallTarget &Target : Targets) {361    if (BitWidth == 1)362      Target.setAfterBit(AllocAfter);363    else364      Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);365  }366}367 368VirtualCallTarget::VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM)369    : Fn(Fn), TM(TM),370      IsBigEndian(Fn->getDataLayout().isBigEndian()),371      WasDevirt(false) {}372 373namespace {374 375// A slot in a set of virtual tables. The TypeID identifies the set of virtual376// tables, and the ByteOffset is the offset in bytes from the address point to377// the virtual function pointer.378struct VTableSlot {379  Metadata *TypeID;380  uint64_t ByteOffset;381};382 383} // end anonymous namespace384 385template <> struct llvm::DenseMapInfo<VTableSlot> {386  static VTableSlot getEmptyKey() {387    return {DenseMapInfo<Metadata *>::getEmptyKey(),388            DenseMapInfo<uint64_t>::getEmptyKey()};389  }390  static VTableSlot getTombstoneKey() {391    return {DenseMapInfo<Metadata *>::getTombstoneKey(),392            DenseMapInfo<uint64_t>::getTombstoneKey()};393  }394  static unsigned getHashValue(const VTableSlot &I) {395    return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^396           DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);397  }398  static bool isEqual(const VTableSlot &LHS,399                      const VTableSlot &RHS) {400    return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;401  }402};403 404template <> struct llvm::DenseMapInfo<VTableSlotSummary> {405  static VTableSlotSummary getEmptyKey() {406    return {DenseMapInfo<StringRef>::getEmptyKey(),407            DenseMapInfo<uint64_t>::getEmptyKey()};408  }409  static VTableSlotSummary getTombstoneKey() {410    return {DenseMapInfo<StringRef>::getTombstoneKey(),411            DenseMapInfo<uint64_t>::getTombstoneKey()};412  }413  static unsigned getHashValue(const VTableSlotSummary &I) {414    return DenseMapInfo<StringRef>::getHashValue(I.TypeID) ^415           DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);416  }417  static bool isEqual(const VTableSlotSummary &LHS,418                      const VTableSlotSummary &RHS) {419    return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;420  }421};422 423// Returns true if the function must be unreachable based on ValueInfo.424//425// In particular, identifies a function as unreachable in the following426// conditions427//   1) All summaries are live.428//   2) All function summaries indicate it's unreachable429//   3) There is no non-function with the same GUID (which is rare)430static bool mustBeUnreachableFunction(ValueInfo TheFnVI) {431  if (WholeProgramDevirtKeepUnreachableFunction)432    return false;433 434  if ((!TheFnVI) || TheFnVI.getSummaryList().empty()) {435    // Returns false if ValueInfo is absent, or the summary list is empty436    // (e.g., function declarations).437    return false;438  }439 440  for (const auto &Summary : TheFnVI.getSummaryList()) {441    // Conservatively returns false if any non-live functions are seen.442    // In general either all summaries should be live or all should be dead.443    if (!Summary->isLive())444      return false;445    if (auto *FS = dyn_cast<FunctionSummary>(Summary->getBaseObject())) {446      if (!FS->fflags().MustBeUnreachable)447        return false;448    }449    // Be conservative if a non-function has the same GUID (which is rare).450    else451      return false;452  }453  // All function summaries are live and all of them agree that the function is454  // unreachble.455  return true;456}457 458namespace {459// A virtual call site. VTable is the loaded virtual table pointer, and CS is460// the indirect virtual call.461struct VirtualCallSite {462  Value *VTable = nullptr;463  CallBase &CB;464 465  // If non-null, this field points to the associated unsafe use count stored in466  // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description467  // of that field for details.468  unsigned *NumUnsafeUses = nullptr;469 470  void471  emitRemark(const StringRef OptName, const StringRef TargetName,472             function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter) {473    Function *F = CB.getCaller();474    DebugLoc DLoc = CB.getDebugLoc();475    BasicBlock *Block = CB.getParent();476 477    using namespace ore;478    OREGetter(*F).emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)479                       << NV("Optimization", OptName)480                       << ": devirtualized a call to "481                       << NV("FunctionName", TargetName));482  }483 484  void replaceAndErase(485      const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,486      function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter,487      Value *New) {488    if (RemarksEnabled)489      emitRemark(OptName, TargetName, OREGetter);490    CB.replaceAllUsesWith(New);491    if (auto *II = dyn_cast<InvokeInst>(&CB)) {492      BranchInst::Create(II->getNormalDest(), CB.getIterator());493      II->getUnwindDest()->removePredecessor(II->getParent());494    }495    CB.eraseFromParent();496    // This use is no longer unsafe.497    if (NumUnsafeUses)498      --*NumUnsafeUses;499  }500};501 502// Call site information collected for a specific VTableSlot and possibly a list503// of constant integer arguments. The grouping by arguments is handled by the504// VTableSlotInfo class.505struct CallSiteInfo {506  /// The set of call sites for this slot. Used during regular LTO and the507  /// import phase of ThinLTO (as well as the export phase of ThinLTO for any508  /// call sites that appear in the merged module itself); in each of these509  /// cases we are directly operating on the call sites at the IR level.510  std::vector<VirtualCallSite> CallSites;511 512  /// Whether all call sites represented by this CallSiteInfo, including those513  /// in summaries, have been devirtualized. This starts off as true because a514  /// default constructed CallSiteInfo represents no call sites.515  ///516  /// If at the end of the pass there are still undevirtualized calls, we will517  /// need to add a use of llvm.type.test to each of the function summaries in518  /// the vector.519  bool AllCallSitesDevirted = true;520 521  // These fields are used during the export phase of ThinLTO and reflect522  // information collected from function summaries.523 524  /// CFI-specific: a vector containing the list of function summaries that use525  /// the llvm.type.checked.load intrinsic and therefore will require526  /// resolutions for llvm.type.test in order to implement CFI checks if527  /// devirtualization was unsuccessful.528  std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;529 530  /// A vector containing the list of function summaries that use531  /// assume(llvm.type.test).532  std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;533 534  bool isExported() const {535    return !SummaryTypeCheckedLoadUsers.empty() ||536           !SummaryTypeTestAssumeUsers.empty();537  }538 539  void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {540    SummaryTypeCheckedLoadUsers.push_back(FS);541    AllCallSitesDevirted = false;542  }543 544  void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {545    SummaryTypeTestAssumeUsers.push_back(FS);546    AllCallSitesDevirted = false;547  }548 549  void markDevirt() { AllCallSitesDevirted = true; }550};551 552// Call site information collected for a specific VTableSlot.553struct VTableSlotInfo {554  // The set of call sites which do not have all constant integer arguments555  // (excluding "this").556  CallSiteInfo CSInfo;557 558  // The set of call sites with all constant integer arguments (excluding559  // "this"), grouped by argument list.560  std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;561 562  void addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses);563 564private:565  CallSiteInfo &findCallSiteInfo(CallBase &CB);566};567 568CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) {569  std::vector<uint64_t> Args;570  auto *CBType = dyn_cast<IntegerType>(CB.getType());571  if (!CBType || CBType->getBitWidth() > 64 || CB.arg_empty())572    return CSInfo;573  for (auto &&Arg : drop_begin(CB.args())) {574    auto *CI = dyn_cast<ConstantInt>(Arg);575    if (!CI || CI->getBitWidth() > 64)576      return CSInfo;577    Args.push_back(CI->getZExtValue());578  }579  return ConstCSInfo[Args];580}581 582void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB,583                                 unsigned *NumUnsafeUses) {584  auto &CSI = findCallSiteInfo(CB);585  CSI.AllCallSitesDevirted = false;586  CSI.CallSites.push_back({VTable, CB, NumUnsafeUses});587}588 589struct DevirtModule {590  Module &M;591  ModuleAnalysisManager &MAM;592  FunctionAnalysisManager &FAM;593 594  ModuleSummaryIndex *const ExportSummary;595  const ModuleSummaryIndex *const ImportSummary;596 597  IntegerType *const Int8Ty;598  PointerType *const Int8PtrTy;599  IntegerType *const Int32Ty;600  IntegerType *const Int64Ty;601  IntegerType *const IntPtrTy;602  /// Sizeless array type, used for imported vtables. This provides a signal603  /// to analyzers that these imports may alias, as they do for example604  /// when multiple unique return values occur in the same vtable.605  ArrayType *const Int8Arr0Ty;606 607  const bool RemarksEnabled;608  std::function<OptimizationRemarkEmitter &(Function &)> OREGetter;609  MapVector<VTableSlot, VTableSlotInfo> CallSlots;610 611  // Calls that have already been optimized. We may add a call to multiple612  // VTableSlotInfos if vtable loads are coalesced and need to make sure not to613  // optimize a call more than once.614  SmallPtrSet<CallBase *, 8> OptimizedCalls;615 616  // Store calls that had their ptrauth bundle removed. They are to be deleted617  // at the end of the optimization.618  SmallVector<CallBase *, 8> CallsWithPtrAuthBundleRemoved;619 620  // This map keeps track of the number of "unsafe" uses of a loaded function621  // pointer. The key is the associated llvm.type.test intrinsic call generated622  // by this pass. An unsafe use is one that calls the loaded function pointer623  // directly. Every time we eliminate an unsafe use (for example, by624  // devirtualizing it or by applying virtual constant propagation), we625  // decrement the value stored in this map. If a value reaches zero, we can626  // eliminate the type check by RAUWing the associated llvm.type.test call with627  // true.628  std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;629  PatternList FunctionsToSkip;630 631  DevirtModule(Module &M, ModuleAnalysisManager &MAM,632               ModuleSummaryIndex *ExportSummary,633               const ModuleSummaryIndex *ImportSummary)634      : M(M), MAM(MAM),635        FAM(MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager()),636        ExportSummary(ExportSummary), ImportSummary(ImportSummary),637        Int8Ty(Type::getInt8Ty(M.getContext())),638        Int8PtrTy(PointerType::getUnqual(M.getContext())),639        Int32Ty(Type::getInt32Ty(M.getContext())),640        Int64Ty(Type::getInt64Ty(M.getContext())),641        IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),642        Int8Arr0Ty(ArrayType::get(Type::getInt8Ty(M.getContext()), 0)),643        RemarksEnabled(areRemarksEnabled()),644        OREGetter([&](Function &F) -> OptimizationRemarkEmitter & {645          return FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);646        }) {647    assert(!(ExportSummary && ImportSummary));648    FunctionsToSkip.init(SkipFunctionNames);649  }650 651  bool areRemarksEnabled();652 653  void654  scanTypeTestUsers(Function *TypeTestFunc,655                    DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);656  void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);657 658  void buildTypeIdentifierMap(659      std::vector<VTableBits> &Bits,660      DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);661 662  bool663  tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,664                            const std::set<TypeMemberInfo> &TypeMemberInfos,665                            uint64_t ByteOffset,666                            ModuleSummaryIndex *ExportSummary);667 668  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,669                             bool &IsExported);670  bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,671                           MutableArrayRef<VirtualCallTarget> TargetsForSlot,672                           VTableSlotInfo &SlotInfo,673                           WholeProgramDevirtResolution *Res);674 675  void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Function &JT,676                              bool &IsExported);677  void tryICallBranchFunnel(MutableArrayRef<VirtualCallTarget> TargetsForSlot,678                            VTableSlotInfo &SlotInfo,679                            WholeProgramDevirtResolution *Res, VTableSlot Slot);680 681  bool tryEvaluateFunctionsWithArgs(682      MutableArrayRef<VirtualCallTarget> TargetsForSlot,683      ArrayRef<uint64_t> Args);684 685  void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,686                             uint64_t TheRetVal);687  bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,688                           CallSiteInfo &CSInfo,689                           WholeProgramDevirtResolution::ByArg *Res);690 691  // Returns the global symbol name that is used to export information about the692  // given vtable slot and list of arguments.693  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,694                            StringRef Name);695 696  bool shouldExportConstantsAsAbsoluteSymbols();697 698  // This function is called during the export phase to create a symbol699  // definition containing information about the given vtable slot and list of700  // arguments.701  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,702                    Constant *C);703  void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,704                      uint32_t Const, uint32_t &Storage);705 706  // This function is called during the import phase to create a reference to707  // the symbol definition created during the export phase.708  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,709                         StringRef Name);710  Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,711                           StringRef Name, IntegerType *IntTy,712                           uint32_t Storage);713 714  Constant *getMemberAddr(const TypeMemberInfo *M);715 716  void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,717                            Constant *UniqueMemberAddr);718  bool tryUniqueRetValOpt(unsigned BitWidth,719                          MutableArrayRef<VirtualCallTarget> TargetsForSlot,720                          CallSiteInfo &CSInfo,721                          WholeProgramDevirtResolution::ByArg *Res,722                          VTableSlot Slot, ArrayRef<uint64_t> Args);723 724  void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,725                             Constant *Byte, Constant *Bit);726  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,727                           VTableSlotInfo &SlotInfo,728                           WholeProgramDevirtResolution *Res, VTableSlot Slot);729 730  void rebuildGlobal(VTableBits &B);731 732  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.733  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);734 735  // If we were able to eliminate all unsafe uses for a type checked load,736  // eliminate the associated type tests by replacing them with true.737  void removeRedundantTypeTests();738 739  bool run();740 741  // Look up the corresponding ValueInfo entry of `TheFn` in `ExportSummary`.742  //743  // Caller guarantees that `ExportSummary` is not nullptr.744  static ValueInfo lookUpFunctionValueInfo(Function *TheFn,745                                           ModuleSummaryIndex *ExportSummary);746 747  // Returns true if the function definition must be unreachable.748  //749  // Note if this helper function returns true, `F` is guaranteed750  // to be unreachable; if it returns false, `F` might still751  // be unreachable but not covered by this helper function.752  //753  // Implementation-wise, if function definition is present, IR is analyzed; if754  // not, look up function flags from ExportSummary as a fallback.755  static bool mustBeUnreachableFunction(Function *const F,756                                        ModuleSummaryIndex *ExportSummary);757 758  // Lower the module using the action and summary passed as command line759  // arguments. For testing purposes only.760  static bool runForTesting(Module &M, ModuleAnalysisManager &MAM);761};762 763struct DevirtIndex {764  ModuleSummaryIndex &ExportSummary;765  // The set in which to record GUIDs exported from their module by766  // devirtualization, used by client to ensure they are not internalized.767  std::set<GlobalValue::GUID> &ExportedGUIDs;768  // A map in which to record the information necessary to locate the WPD769  // resolution for local targets in case they are exported by cross module770  // importing.771  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;772 773  MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;774 775  PatternList FunctionsToSkip;776 777  DevirtIndex(778      ModuleSummaryIndex &ExportSummary,779      std::set<GlobalValue::GUID> &ExportedGUIDs,780      std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)781      : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),782        LocalWPDTargetsMap(LocalWPDTargetsMap) {783    FunctionsToSkip.init(SkipFunctionNames);784  }785 786  bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,787                                 const TypeIdCompatibleVtableInfo TIdInfo,788                                 uint64_t ByteOffset);789 790  bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,791                           VTableSlotSummary &SlotSummary,792                           VTableSlotInfo &SlotInfo,793                           WholeProgramDevirtResolution *Res,794                           std::set<ValueInfo> &DevirtTargets);795 796  void run();797};798} // end anonymous namespace799 800PreservedAnalyses WholeProgramDevirtPass::run(Module &M,801                                              ModuleAnalysisManager &MAM) {802  if (UseCommandLine) {803    if (!DevirtModule::runForTesting(M, MAM))804      return PreservedAnalyses::all();805    return PreservedAnalyses::none();806  }807  if (!DevirtModule(M, MAM, ExportSummary, ImportSummary).run())808    return PreservedAnalyses::all();809  return PreservedAnalyses::none();810}811 812// Enable whole program visibility if enabled by client (e.g. linker) or813// internal option, and not force disabled.814bool llvm::hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) {815  return (WholeProgramVisibilityEnabledInLTO || WholeProgramVisibility) &&816         !DisableWholeProgramVisibility;817}818 819static bool820typeIDVisibleToRegularObj(StringRef TypeID,821                          function_ref<bool(StringRef)> IsVisibleToRegularObj) {822  // TypeID for member function pointer type is an internal construct823  // and won't exist in IsVisibleToRegularObj. The full TypeID824  // will be present and participate in invalidation.825  if (TypeID.ends_with(".virtual"))826    return false;827 828  // TypeID that doesn't start with Itanium mangling (_ZTS) will be829  // non-externally visible types which cannot interact with830  // external native files. See CodeGenModule::CreateMetadataIdentifierImpl.831  if (!TypeID.consume_front("_ZTS"))832    return false;833 834  // TypeID is keyed off the type name symbol (_ZTS). However, the native835  // object may not contain this symbol if it does not contain a key836  // function for the base type and thus only contains a reference to the837  // type info (_ZTI). To catch this case we query using the type info838  // symbol corresponding to the TypeID.839  std::string TypeInfo = ("_ZTI" + TypeID).str();840  return IsVisibleToRegularObj(TypeInfo);841}842 843static bool844skipUpdateDueToValidation(GlobalVariable &GV,845                          function_ref<bool(StringRef)> IsVisibleToRegularObj) {846  SmallVector<MDNode *, 2> Types;847  GV.getMetadata(LLVMContext::MD_type, Types);848 849  for (auto *Type : Types)850    if (auto *TypeID = dyn_cast<MDString>(Type->getOperand(1).get()))851      return typeIDVisibleToRegularObj(TypeID->getString(),852                                       IsVisibleToRegularObj);853 854  return false;855}856 857/// If whole program visibility asserted, then upgrade all public vcall858/// visibility metadata on vtable definitions to linkage unit visibility in859/// Module IR (for regular or hybrid LTO).860void llvm::updateVCallVisibilityInModule(861    Module &M, bool WholeProgramVisibilityEnabledInLTO,862    const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,863    bool ValidateAllVtablesHaveTypeInfos,864    function_ref<bool(StringRef)> IsVisibleToRegularObj) {865  if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))866    return;867  for (GlobalVariable &GV : M.globals()) {868    // Add linkage unit visibility to any variable with type metadata, which are869    // the vtable definitions. We won't have an existing vcall_visibility870    // metadata on vtable definitions with public visibility.871    if (GV.hasMetadata(LLVMContext::MD_type) &&872        GV.getVCallVisibility() == GlobalObject::VCallVisibilityPublic &&873        // Don't upgrade the visibility for symbols exported to the dynamic874        // linker, as we have no information on their eventual use.875        !DynamicExportSymbols.count(GV.getGUID()) &&876        // With validation enabled, we want to exclude symbols visible to877        // regular objects. Local symbols will be in this group due to the878        // current implementation but those with VCallVisibilityTranslationUnit879        // will have already been marked in clang so are unaffected.880        !(ValidateAllVtablesHaveTypeInfos &&881          skipUpdateDueToValidation(GV, IsVisibleToRegularObj)))882      GV.setVCallVisibilityMetadata(GlobalObject::VCallVisibilityLinkageUnit);883  }884}885 886void llvm::updatePublicTypeTestCalls(Module &M,887                                     bool WholeProgramVisibilityEnabledInLTO) {888  llvm::TimeTraceScope timeScope("Update public type test calls");889  Function *PublicTypeTestFunc =890      Intrinsic::getDeclarationIfExists(&M, Intrinsic::public_type_test);891  if (!PublicTypeTestFunc)892    return;893  if (hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO)) {894    Function *TypeTestFunc =895        Intrinsic::getOrInsertDeclaration(&M, Intrinsic::type_test);896    for (Use &U : make_early_inc_range(PublicTypeTestFunc->uses())) {897      auto *CI = cast<CallInst>(U.getUser());898      auto *NewCI = CallInst::Create(899          TypeTestFunc, {CI->getArgOperand(0), CI->getArgOperand(1)}, {}, "",900          CI->getIterator());901      CI->replaceAllUsesWith(NewCI);902      CI->eraseFromParent();903    }904  } else {905    // TODO: Don't replace public type tests when speculative devirtualization906    // gets enabled in LTO mode.907    auto *True = ConstantInt::getTrue(M.getContext());908    for (Use &U : make_early_inc_range(PublicTypeTestFunc->uses())) {909      auto *CI = cast<CallInst>(U.getUser());910      CI->replaceAllUsesWith(True);911      CI->eraseFromParent();912    }913  }914}915 916/// Based on typeID string, get all associated vtable GUIDS that are917/// visible to regular objects.918void llvm::getVisibleToRegularObjVtableGUIDs(919    ModuleSummaryIndex &Index,920    DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols,921    function_ref<bool(StringRef)> IsVisibleToRegularObj) {922  for (const auto &TypeID : Index.typeIdCompatibleVtableMap()) {923    if (typeIDVisibleToRegularObj(TypeID.first, IsVisibleToRegularObj))924      for (const TypeIdOffsetVtableInfo &P : TypeID.second)925        VisibleToRegularObjSymbols.insert(P.VTableVI.getGUID());926  }927}928 929/// If whole program visibility asserted, then upgrade all public vcall930/// visibility metadata on vtable definition summaries to linkage unit931/// visibility in Module summary index (for ThinLTO).932void llvm::updateVCallVisibilityInIndex(933    ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,934    const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,935    const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols) {936  if (!hasWholeProgramVisibility(WholeProgramVisibilityEnabledInLTO))937    return;938  for (auto &P : Index) {939    // Don't upgrade the visibility for symbols exported to the dynamic940    // linker, as we have no information on their eventual use.941    if (DynamicExportSymbols.count(P.first))942      continue;943    // With validation enabled, we want to exclude symbols visible to regular944    // objects. Local symbols will be in this group due to the current945    // implementation but those with VCallVisibilityTranslationUnit will have946    // already been marked in clang so are unaffected.947    if (VisibleToRegularObjSymbols.count(P.first))948      continue;949    for (auto &S : P.second.getSummaryList()) {950      auto *GVar = dyn_cast<GlobalVarSummary>(S.get());951      if (!GVar ||952          GVar->getVCallVisibility() != GlobalObject::VCallVisibilityPublic)953        continue;954      GVar->setVCallVisibility(GlobalObject::VCallVisibilityLinkageUnit);955    }956  }957}958 959void llvm::runWholeProgramDevirtOnIndex(960    ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,961    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {962  DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();963}964 965void llvm::updateIndexWPDForExports(966    ModuleSummaryIndex &Summary,967    function_ref<bool(StringRef, ValueInfo)> IsExported,968    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {969  for (auto &T : LocalWPDTargetsMap) {970    auto &VI = T.first;971    // This was enforced earlier during trySingleImplDevirt.972    assert(VI.getSummaryList().size() == 1 &&973           "Devirt of local target has more than one copy");974    auto &S = VI.getSummaryList()[0];975    if (!IsExported(S->modulePath(), VI))976      continue;977 978    // It's been exported by a cross module import.979    for (auto &SlotSummary : T.second) {980      auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);981      assert(TIdSum);982      auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);983      assert(WPDRes != TIdSum->WPDRes.end());984      WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(985          WPDRes->second.SingleImplName,986          Summary.getModuleHash(S->modulePath()));987    }988  }989}990 991static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) {992  // Check that summary index contains regular LTO module when performing993  // export to prevent occasional use of index from pure ThinLTO compilation994  // (-fno-split-lto-module). This kind of summary index is passed to995  // DevirtIndex::run, not to DevirtModule::run used by opt/runForTesting.996  const auto &ModPaths = Summary->modulePaths();997  if (ClSummaryAction != PassSummaryAction::Import &&998      !ModPaths.contains(ModuleSummaryIndex::getRegularLTOModuleName()))999    return createStringError(1000        errc::invalid_argument,1001        "combined summary should contain Regular LTO module");1002  return ErrorSuccess();1003}1004 1005bool DevirtModule::runForTesting(Module &M, ModuleAnalysisManager &MAM) {1006  std::unique_ptr<ModuleSummaryIndex> Summary =1007      std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/false);1008 1009  // Handle the command-line summary arguments. This code is for testing1010  // purposes only, so we handle errors directly.1011  if (!ClReadSummary.empty()) {1012    ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +1013                          ": ");1014    auto ReadSummaryFile =1015        ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));1016    if (Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =1017            getModuleSummaryIndex(*ReadSummaryFile)) {1018      Summary = std::move(*SummaryOrErr);1019      ExitOnErr(checkCombinedSummaryForTesting(Summary.get()));1020    } else {1021      // Try YAML if we've failed with bitcode.1022      consumeError(SummaryOrErr.takeError());1023      yaml::Input In(ReadSummaryFile->getBuffer());1024      In >> *Summary;1025      ExitOnErr(errorCodeToError(In.error()));1026    }1027  }1028 1029  bool Changed =1030      DevirtModule(M, MAM,1031                   ClSummaryAction == PassSummaryAction::Export ? Summary.get()1032                                                                : nullptr,1033                   ClSummaryAction == PassSummaryAction::Import ? Summary.get()1034                                                                : nullptr)1035          .run();1036 1037  if (!ClWriteSummary.empty()) {1038    ExitOnError ExitOnErr(1039        "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");1040    std::error_code EC;1041    if (StringRef(ClWriteSummary).ends_with(".bc")) {1042      raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_None);1043      ExitOnErr(errorCodeToError(EC));1044      writeIndexToFile(*Summary, OS);1045    } else {1046      raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF);1047      ExitOnErr(errorCodeToError(EC));1048      yaml::Output Out(OS);1049      Out << *Summary;1050    }1051  }1052 1053  return Changed;1054}1055 1056void DevirtModule::buildTypeIdentifierMap(1057    std::vector<VTableBits> &Bits,1058    DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {1059  DenseMap<GlobalVariable *, VTableBits *> GVToBits;1060  Bits.reserve(M.global_size());1061  SmallVector<MDNode *, 2> Types;1062  for (GlobalVariable &GV : M.globals()) {1063    Types.clear();1064    GV.getMetadata(LLVMContext::MD_type, Types);1065    if (GV.isDeclaration() || Types.empty())1066      continue;1067 1068    VTableBits *&BitsPtr = GVToBits[&GV];1069    if (!BitsPtr) {1070      Bits.emplace_back();1071      Bits.back().GV = &GV;1072      Bits.back().ObjectSize =1073          M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());1074      BitsPtr = &Bits.back();1075    }1076 1077    for (MDNode *Type : Types) {1078      auto *TypeID = Type->getOperand(1).get();1079 1080      uint64_t Offset =1081          cast<ConstantInt>(1082              cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())1083              ->getZExtValue();1084 1085      TypeIdMap[TypeID].insert({BitsPtr, Offset});1086    }1087  }1088}1089 1090bool DevirtModule::tryFindVirtualCallTargets(1091    std::vector<VirtualCallTarget> &TargetsForSlot,1092    const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset,1093    ModuleSummaryIndex *ExportSummary) {1094  for (const TypeMemberInfo &TM : TypeMemberInfos) {1095    if (!TM.Bits->GV->isConstant())1096      return false;1097 1098    // Without ClDevirtualizeSpeculatively, we cannot perform whole program1099    // devirtualization analysis on a vtable with public LTO visibility.1100    if (!ClDevirtualizeSpeculatively && TM.Bits->GV->getVCallVisibility() ==1101                                            GlobalObject::VCallVisibilityPublic)1102      return false;1103 1104    Function *Fn = nullptr;1105    Constant *C = nullptr;1106    std::tie(Fn, C) =1107        getFunctionAtVTableOffset(TM.Bits->GV, TM.Offset + ByteOffset, M);1108 1109    if (!Fn)1110      return false;1111 1112    if (FunctionsToSkip.match(Fn->getName()))1113      return false;1114 1115    // We can disregard __cxa_pure_virtual as a possible call target, as1116    // calls to pure virtuals are UB.1117    if (Fn->getName() == "__cxa_pure_virtual")1118      continue;1119 1120    // In most cases empty functions will be overridden by the1121    // implementation of the derived class, so we can skip them.1122    if (ClDevirtualizeSpeculatively && Fn->getReturnType()->isVoidTy() &&1123        Fn->getInstructionCount() <= 1)1124      continue;1125 1126    // We can disregard unreachable functions as possible call targets, as1127    // unreachable functions shouldn't be called.1128    if (mustBeUnreachableFunction(Fn, ExportSummary))1129      continue;1130 1131    // Save the symbol used in the vtable to use as the devirtualization1132    // target.1133    auto *GV = dyn_cast<GlobalValue>(C);1134    assert(GV);1135    TargetsForSlot.push_back({GV, &TM});1136  }1137 1138  // Give up if we couldn't find any targets.1139  return !TargetsForSlot.empty();1140}1141 1142bool DevirtIndex::tryFindVirtualCallTargets(1143    std::vector<ValueInfo> &TargetsForSlot,1144    const TypeIdCompatibleVtableInfo TIdInfo, uint64_t ByteOffset) {1145  for (const TypeIdOffsetVtableInfo &P : TIdInfo) {1146    // Find a representative copy of the vtable initializer.1147    // We can have multiple available_externally, linkonce_odr and weak_odr1148    // vtable initializers. We can also have multiple external vtable1149    // initializers in the case of comdats, which we cannot check here.1150    // The linker should give an error in this case.1151    //1152    // Also, handle the case of same-named local Vtables with the same path1153    // and therefore the same GUID. This can happen if there isn't enough1154    // distinguishing path when compiling the source file. In that case we1155    // conservatively return false early.1156    if (P.VTableVI.hasLocal() && P.VTableVI.getSummaryList().size() > 1)1157      return false;1158    const GlobalVarSummary *VS = nullptr;1159    for (const auto &S : P.VTableVI.getSummaryList()) {1160      auto *CurVS = cast<GlobalVarSummary>(S->getBaseObject());1161      if (!CurVS->vTableFuncs().empty() ||1162          // Previously clang did not attach the necessary type metadata to1163          // available_externally vtables, in which case there would not1164          // be any vtable functions listed in the summary and we need1165          // to treat this case conservatively (in case the bitcode is old).1166          // However, we will also not have any vtable functions in the1167          // case of a pure virtual base class. In that case we do want1168          // to set VS to avoid treating it conservatively.1169          !GlobalValue::isAvailableExternallyLinkage(S->linkage())) {1170        VS = CurVS;1171        // We cannot perform whole program devirtualization analysis on a vtable1172        // with public LTO visibility.1173        if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic)1174          return false;1175        break;1176      }1177    }1178    // There will be no VS if all copies are available_externally having no1179    // type metadata. In that case we can't safely perform WPD.1180    if (!VS)1181      return false;1182    if (!VS->isLive())1183      continue;1184    for (auto VTP : VS->vTableFuncs()) {1185      if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)1186        continue;1187 1188      if (mustBeUnreachableFunction(VTP.FuncVI))1189        continue;1190 1191      TargetsForSlot.push_back(VTP.FuncVI);1192    }1193  }1194 1195  // Give up if we couldn't find any targets.1196  return !TargetsForSlot.empty();1197}1198 1199void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,1200                                         Constant *TheFn, bool &IsExported) {1201  // Don't devirtualize function if we're told to skip it1202  // in -wholeprogramdevirt-skip.1203  if (FunctionsToSkip.match(TheFn->stripPointerCasts()->getName()))1204    return;1205  auto Apply = [&](CallSiteInfo &CSInfo) {1206    for (auto &&VCallSite : CSInfo.CallSites) {1207      if (!OptimizedCalls.insert(&VCallSite.CB).second)1208        continue;1209 1210      // Stop when the number of devirted calls reaches the cutoff.1211      if (!DebugCounter::shouldExecute(CallsToDevirt))1212        continue;1213 1214      if (RemarksEnabled)1215        VCallSite.emitRemark("single-impl",1216                             TheFn->stripPointerCasts()->getName(), OREGetter);1217      NumSingleImpl++;1218      auto &CB = VCallSite.CB;1219      assert(!CB.getCalledFunction() && "devirtualizing direct call?");1220      IRBuilder<> Builder(&CB);1221      Value *Callee =1222          Builder.CreateBitCast(TheFn, CB.getCalledOperand()->getType());1223 1224      // If trap checking is enabled, add support to compare the virtual1225      // function pointer to the devirtualized target. In case of a mismatch,1226      // perform a debug trap.1227      if (DevirtCheckMode == WPDCheckMode::Trap) {1228        auto *Cond = Builder.CreateICmpNE(CB.getCalledOperand(), Callee);1229        Instruction *ThenTerm = SplitBlockAndInsertIfThen(1230            Cond, &CB, /*Unreachable=*/false,1231            MDBuilder(M.getContext()).createUnlikelyBranchWeights());1232        Builder.SetInsertPoint(ThenTerm);1233        Function *TrapFn =1234            Intrinsic::getOrInsertDeclaration(&M, Intrinsic::debugtrap);1235        auto *CallTrap = Builder.CreateCall(TrapFn);1236        CallTrap->setDebugLoc(CB.getDebugLoc());1237      }1238 1239      // If fallback checking or speculative devirtualization are enabled,1240      // add support to compare the virtual function pointer to the1241      // devirtualized target. In case of a mismatch, fall back to indirect1242      // call.1243      if (DevirtCheckMode == WPDCheckMode::Fallback ||1244          ClDevirtualizeSpeculatively) {1245        MDNode *Weights = MDBuilder(M.getContext()).createLikelyBranchWeights();1246        // Version the indirect call site. If the called value is equal to the1247        // given callee, 'NewInst' will be executed, otherwise the original call1248        // site will be executed.1249        CallBase &NewInst = versionCallSite(CB, Callee, Weights);1250        NewInst.setCalledOperand(Callee);1251        // Since the new call site is direct, we must clear metadata that1252        // is only appropriate for indirect calls. This includes !prof and1253        // !callees metadata.1254        NewInst.setMetadata(LLVMContext::MD_prof, nullptr);1255        NewInst.setMetadata(LLVMContext::MD_callees, nullptr);1256        // Additionally, we should remove them from the fallback indirect call,1257        // so that we don't attempt to perform indirect call promotion later.1258        CB.setMetadata(LLVMContext::MD_prof, nullptr);1259        CB.setMetadata(LLVMContext::MD_callees, nullptr);1260      }1261 1262      // In either trapping or non-checking mode, devirtualize original call.1263      else {1264        // Devirtualize unconditionally.1265        CB.setCalledOperand(Callee);1266        // Since the call site is now direct, we must clear metadata that1267        // is only appropriate for indirect calls. This includes !prof and1268        // !callees metadata.1269        CB.setMetadata(LLVMContext::MD_prof, nullptr);1270        CB.setMetadata(LLVMContext::MD_callees, nullptr);1271        if (CB.getCalledOperand() &&1272            CB.getOperandBundle(LLVMContext::OB_ptrauth)) {1273          auto *NewCS = CallBase::removeOperandBundle(1274              &CB, LLVMContext::OB_ptrauth, CB.getIterator());1275          CB.replaceAllUsesWith(NewCS);1276          // Schedule for deletion at the end of pass run.1277          CallsWithPtrAuthBundleRemoved.push_back(&CB);1278        }1279      }1280 1281      // This use is no longer unsafe.1282      if (VCallSite.NumUnsafeUses)1283        --*VCallSite.NumUnsafeUses;1284    }1285    if (CSInfo.isExported())1286      IsExported = true;1287    CSInfo.markDevirt();1288  };1289  Apply(SlotInfo.CSInfo);1290  for (auto &P : SlotInfo.ConstCSInfo)1291    Apply(P.second);1292}1293 1294static bool addCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) {1295  // We can't add calls if we haven't seen a definition1296  if (Callee.getSummaryList().empty())1297    return false;1298 1299  // Insert calls into the summary index so that the devirtualized targets1300  // are eligible for import.1301  // FIXME: Annotate type tests with hotness. For now, mark these as hot1302  // to better ensure we have the opportunity to inline them.1303  bool IsExported = false;1304  auto &S = Callee.getSummaryList()[0];1305  CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* HasTailCall = */ false,1306                /* RelBF = */ 0);1307  auto AddCalls = [&](CallSiteInfo &CSInfo) {1308    for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {1309      FS->addCall({Callee, CI});1310      IsExported |= S->modulePath() != FS->modulePath();1311    }1312    for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {1313      FS->addCall({Callee, CI});1314      IsExported |= S->modulePath() != FS->modulePath();1315    }1316  };1317  AddCalls(SlotInfo.CSInfo);1318  for (auto &P : SlotInfo.ConstCSInfo)1319    AddCalls(P.second);1320  return IsExported;1321}1322 1323bool DevirtModule::trySingleImplDevirt(1324    ModuleSummaryIndex *ExportSummary,1325    MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,1326    WholeProgramDevirtResolution *Res) {1327  // See if the program contains a single implementation of this virtual1328  // function.1329  auto *TheFn = TargetsForSlot[0].Fn;1330  for (auto &&Target : TargetsForSlot)1331    if (TheFn != Target.Fn)1332      return false;1333 1334  // If so, update each call site to call that implementation directly.1335  if (RemarksEnabled || AreStatisticsEnabled())1336    TargetsForSlot[0].WasDevirt = true;1337 1338  bool IsExported = false;1339  applySingleImplDevirt(SlotInfo, TheFn, IsExported);1340  if (!IsExported)1341    return false;1342 1343  // If the only implementation has local linkage, we must promote to external1344  // to make it visible to thin LTO objects. We can only get here during the1345  // ThinLTO export phase.1346  if (TheFn->hasLocalLinkage()) {1347    std::string NewName = (TheFn->getName() + ".llvm.merged").str();1348 1349    // Since we are renaming the function, any comdats with the same name must1350    // also be renamed. This is required when targeting COFF, as the comdat name1351    // must match one of the names of the symbols in the comdat.1352    if (Comdat *C = TheFn->getComdat()) {1353      if (C->getName() == TheFn->getName()) {1354        Comdat *NewC = M.getOrInsertComdat(NewName);1355        NewC->setSelectionKind(C->getSelectionKind());1356        for (GlobalObject &GO : M.global_objects())1357          if (GO.getComdat() == C)1358            GO.setComdat(NewC);1359      }1360    }1361 1362    TheFn->setLinkage(GlobalValue::ExternalLinkage);1363    TheFn->setVisibility(GlobalValue::HiddenVisibility);1364    TheFn->setName(NewName);1365  }1366  if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID()))1367    // Any needed promotion of 'TheFn' has already been done during1368    // LTO unit split, so we can ignore return value of AddCalls.1369    addCalls(SlotInfo, TheFnVI);1370 1371  Res->TheKind = WholeProgramDevirtResolution::SingleImpl;1372  Res->SingleImplName = std::string(TheFn->getName());1373 1374  return true;1375}1376 1377bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,1378                                      VTableSlotSummary &SlotSummary,1379                                      VTableSlotInfo &SlotInfo,1380                                      WholeProgramDevirtResolution *Res,1381                                      std::set<ValueInfo> &DevirtTargets) {1382  // See if the program contains a single implementation of this virtual1383  // function.1384  auto TheFn = TargetsForSlot[0];1385  for (auto &&Target : TargetsForSlot)1386    if (TheFn != Target)1387      return false;1388 1389  // Don't devirtualize if we don't have target definition.1390  auto Size = TheFn.getSummaryList().size();1391  if (!Size)1392    return false;1393 1394  // Don't devirtualize function if we're told to skip it1395  // in -wholeprogramdevirt-skip.1396  if (FunctionsToSkip.match(TheFn.name()))1397    return false;1398 1399  // If the summary list contains multiple summaries where at least one is1400  // a local, give up, as we won't know which (possibly promoted) name to use.1401  if (TheFn.hasLocal() && Size > 1)1402    return false;1403 1404  // Collect functions devirtualized at least for one call site for stats.1405  if (PrintSummaryDevirt || AreStatisticsEnabled())1406    DevirtTargets.insert(TheFn);1407 1408  auto &S = TheFn.getSummaryList()[0];1409  bool IsExported = addCalls(SlotInfo, TheFn);1410  if (IsExported)1411    ExportedGUIDs.insert(TheFn.getGUID());1412 1413  // Record in summary for use in devirtualization during the ThinLTO import1414  // step.1415  Res->TheKind = WholeProgramDevirtResolution::SingleImpl;1416  if (GlobalValue::isLocalLinkage(S->linkage())) {1417    if (IsExported)1418      // If target is a local function and we are exporting it by1419      // devirtualizing a call in another module, we need to record the1420      // promoted name.1421      Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(1422          TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));1423    else {1424      LocalWPDTargetsMap[TheFn].push_back(SlotSummary);1425      Res->SingleImplName = std::string(TheFn.name());1426    }1427  } else1428    Res->SingleImplName = std::string(TheFn.name());1429 1430  // Name will be empty if this thin link driven off of serialized combined1431  // index (e.g. llvm-lto). However, WPD is not supported/invoked for the1432  // legacy LTO API anyway.1433  assert(!Res->SingleImplName.empty());1434 1435  return true;1436}1437 1438void DevirtModule::tryICallBranchFunnel(1439    MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,1440    WholeProgramDevirtResolution *Res, VTableSlot Slot) {1441  Triple T(M.getTargetTriple());1442  if (T.getArch() != Triple::x86_64)1443    return;1444 1445  if (TargetsForSlot.size() > ClThreshold)1446    return;1447 1448  bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;1449  if (!HasNonDevirt)1450    for (auto &P : SlotInfo.ConstCSInfo)1451      if (!P.second.AllCallSitesDevirted) {1452        HasNonDevirt = true;1453        break;1454      }1455 1456  if (!HasNonDevirt)1457    return;1458 1459  // If any GV is AvailableExternally, not to generate branch.funnel.1460  // NOTE: It is to avoid crash in LowerTypeTest.1461  // If the branch.funnel is generated, because GV.isDeclarationForLinker(),1462  // in LowerTypeTestsModule::lower(), its GlobalTypeMember would NOT1463  // be saved in GlobalTypeMembers[&GV]. Then crash happens in1464  // buildBitSetsFromDisjointSet due to GlobalTypeMembers[&GV] is NULL.1465  // Even doing experiment to save it in GlobalTypeMembers[&GV] and1466  // making GlobalTypeMembers[&GV] be not NULL, crash could avoid from1467  // buildBitSetsFromDisjointSet. But still report_fatal_error in Verifier1468  // or SelectionDAGBuilder later, because operands linkage type consistency1469  // check of icall.branch.funnel can not pass.1470  for (auto &T : TargetsForSlot) {1471    if (T.TM->Bits->GV->hasAvailableExternallyLinkage())1472      return;1473  }1474 1475  FunctionType *FT =1476      FunctionType::get(Type::getVoidTy(M.getContext()), {Int8PtrTy}, true);1477  Function *JT;1478  if (isa<MDString>(Slot.TypeID)) {1479    JT = Function::Create(FT, Function::ExternalLinkage,1480                          M.getDataLayout().getProgramAddressSpace(),1481                          getGlobalName(Slot, {}, "branch_funnel"), &M);1482    JT->setVisibility(GlobalValue::HiddenVisibility);1483  } else {1484    JT = Function::Create(FT, Function::InternalLinkage,1485                          M.getDataLayout().getProgramAddressSpace(),1486                          "branch_funnel", &M);1487  }1488  JT->addParamAttr(0, Attribute::Nest);1489 1490  std::vector<Value *> JTArgs;1491  JTArgs.push_back(JT->arg_begin());1492  for (auto &T : TargetsForSlot) {1493    JTArgs.push_back(getMemberAddr(T.TM));1494    JTArgs.push_back(T.Fn);1495  }1496 1497  BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);1498  Function *Intr = Intrinsic::getOrInsertDeclaration(1499      &M, llvm::Intrinsic::icall_branch_funnel, {});1500 1501  auto *CI = CallInst::Create(Intr, JTArgs, "", BB);1502  CI->setTailCallKind(CallInst::TCK_MustTail);1503  ReturnInst::Create(M.getContext(), nullptr, BB);1504 1505  bool IsExported = false;1506  applyICallBranchFunnel(SlotInfo, *JT, IsExported);1507  if (IsExported)1508    Res->TheKind = WholeProgramDevirtResolution::BranchFunnel;1509 1510  if (!JT->getEntryCount().has_value()) {1511    // FIXME: we could pass through thinlto the necessary information.1512    setExplicitlyUnknownFunctionEntryCount(*JT, DEBUG_TYPE);1513  }1514}1515 1516void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,1517                                          Function &JT, bool &IsExported) {1518  DenseMap<Function *, double> FunctionEntryCounts;1519  auto Apply = [&](CallSiteInfo &CSInfo) {1520    if (CSInfo.isExported())1521      IsExported = true;1522    if (CSInfo.AllCallSitesDevirted)1523      return;1524 1525    std::map<CallBase *, CallBase *> CallBases;1526    for (auto &&VCallSite : CSInfo.CallSites) {1527      CallBase &CB = VCallSite.CB;1528 1529      if (CallBases.find(&CB) != CallBases.end()) {1530        // When finding devirtualizable calls, it's possible to find the same1531        // vtable passed to multiple llvm.type.test or llvm.type.checked.load1532        // calls, which can cause duplicate call sites to be recorded in1533        // [Const]CallSites. If we've already found one of these1534        // call instances, just ignore it. It will be replaced later.1535        continue;1536      }1537 1538      // Jump tables are only profitable if the retpoline mitigation is enabled.1539      Attribute FSAttr = CB.getCaller()->getFnAttribute("target-features");1540      if (!FSAttr.isValid() ||1541          !FSAttr.getValueAsString().contains("+retpoline"))1542        continue;1543 1544      NumBranchFunnel++;1545      if (RemarksEnabled)1546        VCallSite.emitRemark("branch-funnel", JT.getName(), OREGetter);1547 1548      // Pass the address of the vtable in the nest register, which is r10 on1549      // x86_64.1550      std::vector<Type *> NewArgs;1551      NewArgs.push_back(Int8PtrTy);1552      append_range(NewArgs, CB.getFunctionType()->params());1553      FunctionType *NewFT =1554          FunctionType::get(CB.getFunctionType()->getReturnType(), NewArgs,1555                            CB.getFunctionType()->isVarArg());1556      IRBuilder<> IRB(&CB);1557      std::vector<Value *> Args;1558      Args.push_back(VCallSite.VTable);1559      llvm::append_range(Args, CB.args());1560 1561      CallBase *NewCS = nullptr;1562      if (!JT.isDeclaration() && !ProfcheckDisableMetadataFixes) {1563        // Accumulate the call frequencies of the original call site, and use1564        // that as total entry count for the funnel function.1565        auto &F = *CB.getCaller();1566        auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);1567        auto EC = BFI.getBlockFreq(&F.getEntryBlock());1568        auto CC = F.getEntryCount(/*AllowSynthetic=*/true);1569        double CallCount = 0.0;1570        if (EC.getFrequency() != 0 && CC && CC->getCount() != 0) {1571          double CallFreq =1572              static_cast<double>(1573                  BFI.getBlockFreq(CB.getParent()).getFrequency()) /1574              EC.getFrequency();1575          CallCount = CallFreq * CC->getCount();1576        }1577        FunctionEntryCounts[&JT] += CallCount;1578      }1579      if (isa<CallInst>(CB))1580        NewCS = IRB.CreateCall(NewFT, &JT, Args);1581      else1582        NewCS =1583            IRB.CreateInvoke(NewFT, &JT, cast<InvokeInst>(CB).getNormalDest(),1584                             cast<InvokeInst>(CB).getUnwindDest(), Args);1585      NewCS->setCallingConv(CB.getCallingConv());1586 1587      AttributeList Attrs = CB.getAttributes();1588      std::vector<AttributeSet> NewArgAttrs;1589      NewArgAttrs.push_back(AttributeSet::get(1590          M.getContext(), ArrayRef<Attribute>{Attribute::get(1591                              M.getContext(), Attribute::Nest)}));1592      for (unsigned I = 0; I + 2 <  Attrs.getNumAttrSets(); ++I)1593        NewArgAttrs.push_back(Attrs.getParamAttrs(I));1594      NewCS->setAttributes(1595          AttributeList::get(M.getContext(), Attrs.getFnAttrs(),1596                             Attrs.getRetAttrs(), NewArgAttrs));1597 1598      CallBases[&CB] = NewCS;1599 1600      // This use is no longer unsafe.1601      if (VCallSite.NumUnsafeUses)1602        --*VCallSite.NumUnsafeUses;1603    }1604    // Don't mark as devirtualized because there may be callers compiled without1605    // retpoline mitigation, which would mean that they are lowered to1606    // llvm.type.test and therefore require an llvm.type.test resolution for the1607    // type identifier.1608 1609    for (auto &[Old, New] : CallBases) {1610      Old->replaceAllUsesWith(New);1611      Old->eraseFromParent();1612    }1613  };1614  Apply(SlotInfo.CSInfo);1615  for (auto &P : SlotInfo.ConstCSInfo)1616    Apply(P.second);1617  for (auto &[F, C] : FunctionEntryCounts) {1618    assert(!F->getEntryCount(/*AllowSynthetic=*/true) &&1619           "Unexpected entry count for funnel that was freshly synthesized");1620    F->setEntryCount(static_cast<uint64_t>(std::round(C)));1621  }1622}1623 1624bool DevirtModule::tryEvaluateFunctionsWithArgs(1625    MutableArrayRef<VirtualCallTarget> TargetsForSlot,1626    ArrayRef<uint64_t> Args) {1627  // Evaluate each function and store the result in each target's RetVal1628  // field.1629  for (VirtualCallTarget &Target : TargetsForSlot) {1630    // TODO: Skip for now if the vtable symbol was an alias to a function,1631    // need to evaluate whether it would be correct to analyze the aliasee1632    // function for this optimization.1633    auto *Fn = dyn_cast<Function>(Target.Fn);1634    if (!Fn)1635      return false;1636 1637    if (Fn->arg_size() != Args.size() + 1)1638      return false;1639 1640    Evaluator Eval(M.getDataLayout(), nullptr);1641    SmallVector<Constant *, 2> EvalArgs;1642    EvalArgs.push_back(1643        Constant::getNullValue(Fn->getFunctionType()->getParamType(0)));1644    for (unsigned I = 0; I != Args.size(); ++I) {1645      auto *ArgTy =1646          dyn_cast<IntegerType>(Fn->getFunctionType()->getParamType(I + 1));1647      if (!ArgTy)1648        return false;1649      EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));1650    }1651 1652    Constant *RetVal;1653    if (!Eval.EvaluateFunction(Fn, RetVal, EvalArgs) ||1654        !isa<ConstantInt>(RetVal))1655      return false;1656    Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();1657  }1658  return true;1659}1660 1661void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,1662                                         uint64_t TheRetVal) {1663  for (auto Call : CSInfo.CallSites) {1664    if (!OptimizedCalls.insert(&Call.CB).second)1665      continue;1666    NumUniformRetVal++;1667    Call.replaceAndErase(1668        "uniform-ret-val", FnName, RemarksEnabled, OREGetter,1669        ConstantInt::get(cast<IntegerType>(Call.CB.getType()), TheRetVal));1670  }1671  CSInfo.markDevirt();1672}1673 1674bool DevirtModule::tryUniformRetValOpt(1675    MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,1676    WholeProgramDevirtResolution::ByArg *Res) {1677  // Uniform return value optimization. If all functions return the same1678  // constant, replace all calls with that constant.1679  uint64_t TheRetVal = TargetsForSlot[0].RetVal;1680  for (const VirtualCallTarget &Target : TargetsForSlot)1681    if (Target.RetVal != TheRetVal)1682      return false;1683 1684  if (CSInfo.isExported()) {1685    Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;1686    Res->Info = TheRetVal;1687  }1688 1689  applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);1690  if (RemarksEnabled || AreStatisticsEnabled())1691    for (auto &&Target : TargetsForSlot)1692      Target.WasDevirt = true;1693  return true;1694}1695 1696std::string DevirtModule::getGlobalName(VTableSlot Slot,1697                                        ArrayRef<uint64_t> Args,1698                                        StringRef Name) {1699  std::string FullName = "__typeid_";1700  raw_string_ostream OS(FullName);1701  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;1702  for (uint64_t Arg : Args)1703    OS << '_' << Arg;1704  OS << '_' << Name;1705  return FullName;1706}1707 1708bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {1709  Triple T(M.getTargetTriple());1710  return T.isX86() && T.getObjectFormat() == Triple::ELF;1711}1712 1713void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,1714                                StringRef Name, Constant *C) {1715  GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,1716                                        getGlobalName(Slot, Args, Name), C, &M);1717  GA->setVisibility(GlobalValue::HiddenVisibility);1718}1719 1720void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,1721                                  StringRef Name, uint32_t Const,1722                                  uint32_t &Storage) {1723  if (shouldExportConstantsAsAbsoluteSymbols()) {1724    exportGlobal(1725        Slot, Args, Name,1726        ConstantExpr::getIntToPtr(ConstantInt::get(Int32Ty, Const), Int8PtrTy));1727    return;1728  }1729 1730  Storage = Const;1731}1732 1733Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,1734                                     StringRef Name) {1735  GlobalVariable *GV =1736      M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Arr0Ty);1737  GV->setVisibility(GlobalValue::HiddenVisibility);1738  return GV;1739}1740 1741Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,1742                                       StringRef Name, IntegerType *IntTy,1743                                       uint32_t Storage) {1744  if (!shouldExportConstantsAsAbsoluteSymbols())1745    return ConstantInt::get(IntTy, Storage);1746 1747  Constant *C = importGlobal(Slot, Args, Name);1748  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());1749  C = ConstantExpr::getPtrToInt(C, IntTy);1750 1751  // We only need to set metadata if the global is newly created, in which1752  // case it would not have hidden visibility.1753  if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))1754    return C;1755 1756  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {1757    auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));1758    auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));1759    GV->setMetadata(LLVMContext::MD_absolute_symbol,1760                    MDNode::get(M.getContext(), {MinC, MaxC}));1761  };1762  unsigned AbsWidth = IntTy->getBitWidth();1763  if (AbsWidth == IntPtrTy->getBitWidth())1764    SetAbsRange(~0ull, ~0ull); // Full set.1765  else1766    SetAbsRange(0, 1ull << AbsWidth);1767  return C;1768}1769 1770void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,1771                                        bool IsOne,1772                                        Constant *UniqueMemberAddr) {1773  for (auto &&Call : CSInfo.CallSites) {1774    if (!OptimizedCalls.insert(&Call.CB).second)1775      continue;1776    IRBuilder<> B(&Call.CB);1777    Value *Cmp =1778        B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, Call.VTable,1779                     B.CreateBitCast(UniqueMemberAddr, Call.VTable->getType()));1780    Cmp = B.CreateZExt(Cmp, Call.CB.getType());1781    NumUniqueRetVal++;1782    Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,1783                         Cmp);1784  }1785  CSInfo.markDevirt();1786}1787 1788Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {1789  return ConstantExpr::getGetElementPtr(Int8Ty, M->Bits->GV,1790                                        ConstantInt::get(Int64Ty, M->Offset));1791}1792 1793bool DevirtModule::tryUniqueRetValOpt(1794    unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,1795    CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,1796    VTableSlot Slot, ArrayRef<uint64_t> Args) {1797  // IsOne controls whether we look for a 0 or a 1.1798  auto tryUniqueRetValOptFor = [&](bool IsOne) {1799    const TypeMemberInfo *UniqueMember = nullptr;1800    for (const VirtualCallTarget &Target : TargetsForSlot) {1801      if (Target.RetVal == (IsOne ? 1 : 0)) {1802        if (UniqueMember)1803          return false;1804        UniqueMember = Target.TM;1805      }1806    }1807 1808    // We should have found a unique member or bailed out by now. We already1809    // checked for a uniform return value in tryUniformRetValOpt.1810    assert(UniqueMember);1811 1812    Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);1813    if (CSInfo.isExported()) {1814      Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;1815      Res->Info = IsOne;1816 1817      exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);1818    }1819 1820    // Replace each call with the comparison.1821    applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,1822                         UniqueMemberAddr);1823 1824    // Update devirtualization statistics for targets.1825    if (RemarksEnabled || AreStatisticsEnabled())1826      for (auto &&Target : TargetsForSlot)1827        Target.WasDevirt = true;1828 1829    return true;1830  };1831 1832  if (BitWidth == 1) {1833    if (tryUniqueRetValOptFor(true))1834      return true;1835    if (tryUniqueRetValOptFor(false))1836      return true;1837  }1838  return false;1839}1840 1841void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,1842                                         Constant *Byte, Constant *Bit) {1843  for (auto Call : CSInfo.CallSites) {1844    if (!OptimizedCalls.insert(&Call.CB).second)1845      continue;1846    auto *RetType = cast<IntegerType>(Call.CB.getType());1847    IRBuilder<> B(&Call.CB);1848    Value *Addr = B.CreatePtrAdd(Call.VTable, Byte);1849    if (RetType->getBitWidth() == 1) {1850      Value *Bits = B.CreateLoad(Int8Ty, Addr);1851      Value *BitsAndBit = B.CreateAnd(Bits, Bit);1852      auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));1853      NumVirtConstProp1Bit++;1854      Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,1855                           OREGetter, IsBitSet);1856    } else {1857      Value *Val = B.CreateLoad(RetType, Addr);1858      NumVirtConstProp++;1859      Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,1860                           OREGetter, Val);1861    }1862  }1863  CSInfo.markDevirt();1864}1865 1866bool DevirtModule::tryVirtualConstProp(1867    MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,1868    WholeProgramDevirtResolution *Res, VTableSlot Slot) {1869  // TODO: Skip for now if the vtable symbol was an alias to a function,1870  // need to evaluate whether it would be correct to analyze the aliasee1871  // function for this optimization.1872  auto *Fn = dyn_cast<Function>(TargetsForSlot[0].Fn);1873  if (!Fn)1874    return false;1875  // This only works if the function returns an integer.1876  auto *RetType = dyn_cast<IntegerType>(Fn->getReturnType());1877  if (!RetType)1878    return false;1879  unsigned BitWidth = RetType->getBitWidth();1880 1881  // TODO: Since we can evaluated these constants at compile-time, we can save1882  // some space by calculating the smallest range of values that all these1883  // constants can fit in, then only allocate enough space to fit those values.1884  // At each callsite, we can get the original type by doing a sign/zero1885  // extension. For example, if we would store an i64, but we can see that all1886  // the values fit into an i16, then we can store an i16 before/after the1887  // vtable and at each callsite do a s/zext.1888  if (BitWidth > 64)1889    return false;1890 1891  Align TypeAlignment = M.getDataLayout().getABIIntegerTypeAlignment(BitWidth);1892 1893  // Make sure that each function is defined, does not access memory, takes at1894  // least one argument, does not use its first argument (which we assume is1895  // 'this'), and has the same return type.1896  //1897  // Note that we test whether this copy of the function is readnone, rather1898  // than testing function attributes, which must hold for any copy of the1899  // function, even a less optimized version substituted at link time. This is1900  // sound because the virtual constant propagation optimizations effectively1901  // inline all implementations of the virtual function into each call site,1902  // rather than using function attributes to perform local optimization.1903  for (VirtualCallTarget &Target : TargetsForSlot) {1904    // TODO: Skip for now if the vtable symbol was an alias to a function,1905    // need to evaluate whether it would be correct to analyze the aliasee1906    // function for this optimization.1907    auto *Fn = dyn_cast<Function>(Target.Fn);1908    if (!Fn)1909      return false;1910 1911    if (Fn->isDeclaration() ||1912        !computeFunctionBodyMemoryAccess(*Fn, FAM.getResult<AAManager>(*Fn))1913             .doesNotAccessMemory() ||1914        Fn->arg_empty() || !Fn->arg_begin()->use_empty() ||1915        Fn->getReturnType() != RetType)1916      return false;1917 1918    // This only works if the integer size is at most the alignment of the1919    // vtable. If the table is underaligned, then we can't guarantee that the1920    // constant will always be aligned to the integer type alignment. For1921    // example, if the table is `align 1`, we can never guarantee that an i321922    // stored before/after the vtable is 32-bit aligned without changing the1923    // alignment of the new global.1924    GlobalVariable *GV = Target.TM->Bits->GV;1925    Align TableAlignment = M.getDataLayout().getValueOrABITypeAlignment(1926        GV->getAlign(), GV->getValueType());1927    if (TypeAlignment > TableAlignment)1928      return false;1929  }1930 1931  for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {1932    if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))1933      continue;1934 1935    WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;1936    if (Res)1937      ResByArg = &Res->ResByArg[CSByConstantArg.first];1938 1939    if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))1940      continue;1941 1942    if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,1943                           ResByArg, Slot, CSByConstantArg.first))1944      continue;1945 1946    // Find an allocation offset in bits in all vtables associated with the1947    // type.1948    // TODO: If there would be "holes" in the vtable that were added by1949    // padding, we could place i1s there to reduce any extra padding that1950    // would be introduced by the i1s.1951    uint64_t AllocBefore =1952        findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);1953    uint64_t AllocAfter =1954        findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);1955 1956    // Calculate the total amount of padding needed to store a value at both1957    // ends of the object.1958    uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;1959    for (auto &&Target : TargetsForSlot) {1960      TotalPaddingBefore += std::max<int64_t>(1961          (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);1962      TotalPaddingAfter += std::max<int64_t>(1963          (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);1964    }1965 1966    // If the amount of padding is too large, give up.1967    // FIXME: do something smarter here.1968    if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)1969      continue;1970 1971    // Calculate the offset to the value as a (possibly negative) byte offset1972    // and (if applicable) a bit offset, and store the values in the targets.1973    int64_t OffsetByte;1974    uint64_t OffsetBit;1975    if (TotalPaddingBefore <= TotalPaddingAfter)1976      setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,1977                            OffsetBit);1978    else1979      setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,1980                           OffsetBit);1981 1982    // In an earlier check we forbade constant propagation from operating on1983    // tables whose alignment is less than the alignment needed for loading1984    // the constant. Thus, the address we take the offset from will always be1985    // aligned to at least this integer alignment. Now, we need to ensure that1986    // the offset is also aligned to this integer alignment to ensure we always1987    // have an aligned load.1988    assert(OffsetByte % TypeAlignment.value() == 0);1989 1990    if (RemarksEnabled || AreStatisticsEnabled())1991      for (auto &&Target : TargetsForSlot)1992        Target.WasDevirt = true;1993 1994 1995    if (CSByConstantArg.second.isExported()) {1996      ResByArg->TheKind = WholeProgramDevirtResolution::ByArg::VirtualConstProp;1997      exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,1998                     ResByArg->Byte);1999      exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,2000                     ResByArg->Bit);2001    }2002 2003    // Rewrite each call to a load from OffsetByte/OffsetBit.2004    Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);2005    Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);2006    applyVirtualConstProp(CSByConstantArg.second,2007                          TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);2008  }2009  return true;2010}2011 2012void DevirtModule::rebuildGlobal(VTableBits &B) {2013  if (B.Before.Bytes.empty() && B.After.Bytes.empty())2014    return;2015 2016  // Align the before byte array to the global's minimum alignment so that we2017  // don't break any alignment requirements on the global.2018  Align Alignment = M.getDataLayout().getValueOrABITypeAlignment(2019      B.GV->getAlign(), B.GV->getValueType());2020  B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment));2021 2022  // Before was stored in reverse order; flip it now.2023  for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)2024    std::swap(B.Before.Bytes[I], B.Before.Bytes[Size - 1 - I]);2025 2026  // Build an anonymous global containing the before bytes, followed by the2027  // original initializer, followed by the after bytes.2028  auto *NewInit = ConstantStruct::getAnon(2029      {ConstantDataArray::get(M.getContext(), B.Before.Bytes),2030       B.GV->getInitializer(),2031       ConstantDataArray::get(M.getContext(), B.After.Bytes)});2032  auto *NewGV =2033      new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),2034                         GlobalVariable::PrivateLinkage, NewInit, "", B.GV);2035  NewGV->setSection(B.GV->getSection());2036  NewGV->setComdat(B.GV->getComdat());2037  NewGV->setAlignment(B.GV->getAlign());2038 2039  // Copy the original vtable's metadata to the anonymous global, adjusting2040  // offsets as required.2041  NewGV->copyMetadata(B.GV, B.Before.Bytes.size());2042 2043  // Build an alias named after the original global, pointing at the second2044  // element (the original initializer).2045  auto *Alias = GlobalAlias::create(2046      B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",2047      ConstantExpr::getInBoundsGetElementPtr(2048          NewInit->getType(), NewGV,2049          ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),2050                               ConstantInt::get(Int32Ty, 1)}),2051      &M);2052  Alias->setVisibility(B.GV->getVisibility());2053  Alias->takeName(B.GV);2054 2055  B.GV->replaceAllUsesWith(Alias);2056  B.GV->eraseFromParent();2057}2058 2059bool DevirtModule::areRemarksEnabled() {2060  const auto &FL = M.getFunctionList();2061  for (const Function &Fn : FL) {2062    if (Fn.empty())2063      continue;2064    auto DI = OptimizationRemark(DEBUG_TYPE, "", DebugLoc(), &Fn.front());2065    return DI.isEnabled();2066  }2067  return false;2068}2069 2070void DevirtModule::scanTypeTestUsers(2071    Function *TypeTestFunc,2072    DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) {2073  // Find all virtual calls via a virtual table pointer %p under an assumption2074  // of the form llvm.assume(llvm.type.test(%p, %md)) or2075  // llvm.assume(llvm.public.type.test(%p, %md)).2076  // This indicates that %p points to a member of the type identifier %md.2077  // Group calls by (type ID, offset) pair (effectively the identity of the2078  // virtual function) and store to CallSlots.2079  for (Use &U : llvm::make_early_inc_range(TypeTestFunc->uses())) {2080    auto *CI = dyn_cast<CallInst>(U.getUser());2081    if (!CI)2082      continue;2083    // Search for virtual calls based on %p and add them to DevirtCalls.2084    SmallVector<DevirtCallSite, 1> DevirtCalls;2085    SmallVector<CallInst *, 1> Assumes;2086    auto &DT = FAM.getResult<DominatorTreeAnalysis>(*CI->getFunction());2087    findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);2088 2089    Metadata *TypeId =2090        cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();2091    // If we found any, add them to CallSlots.2092    if (!Assumes.empty()) {2093      Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();2094      for (DevirtCallSite Call : DevirtCalls)2095        CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB, nullptr);2096    }2097 2098    auto RemoveTypeTestAssumes = [&]() {2099      // We no longer need the assumes or the type test.2100      for (auto *Assume : Assumes)2101        Assume->eraseFromParent();2102      // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we2103      // may use the vtable argument later.2104      if (CI->use_empty())2105        CI->eraseFromParent();2106    };2107 2108    // At this point we could remove all type test assume sequences, as they2109    // were originally inserted for WPD. However, we can keep these in the2110    // code stream for later analysis (e.g. to help drive more efficient ICP2111    // sequences). They will eventually be removed by a second LowerTypeTests2112    // invocation that cleans them up. In order to do this correctly, the first2113    // LowerTypeTests invocation needs to know that they have "Unknown" type2114    // test resolution, so that they aren't treated as Unsat and lowered to2115    // False, which will break any uses on assumes. Below we remove any type2116    // test assumes that will not be treated as Unknown by LTT.2117 2118    // The type test assumes will be treated by LTT as Unsat if the type id is2119    // not used on a global (in which case it has no entry in the TypeIdMap).2120    if (!TypeIdMap.count(TypeId))2121      RemoveTypeTestAssumes();2122 2123    // For ThinLTO importing, we need to remove the type test assumes if this is2124    // an MDString type id without a corresponding TypeIdSummary. Any2125    // non-MDString type ids are ignored and treated as Unknown by LTT, so their2126    // type test assumes can be kept. If the MDString type id is missing a2127    // TypeIdSummary (e.g. because there was no use on a vcall, preventing the2128    // exporting phase of WPD from analyzing it), then it would be treated as2129    // Unsat by LTT and we need to remove its type test assumes here. If not2130    // used on a vcall we don't need them for later optimization use in any2131    // case.2132    else if (ImportSummary && isa<MDString>(TypeId)) {2133      const TypeIdSummary *TidSummary =2134          ImportSummary->getTypeIdSummary(cast<MDString>(TypeId)->getString());2135      if (!TidSummary)2136        RemoveTypeTestAssumes();2137      else2138        // If one was created it should not be Unsat, because if we reached here2139        // the type id was used on a global.2140        assert(TidSummary->TTRes.TheKind != TypeTestResolution::Unsat);2141    }2142  }2143}2144 2145void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {2146  Function *TypeTestFunc =2147      Intrinsic::getOrInsertDeclaration(&M, Intrinsic::type_test);2148 2149  for (Use &U : llvm::make_early_inc_range(TypeCheckedLoadFunc->uses())) {2150    auto *CI = dyn_cast<CallInst>(U.getUser());2151    if (!CI)2152      continue;2153 2154    Value *Ptr = CI->getArgOperand(0);2155    Value *Offset = CI->getArgOperand(1);2156    Value *TypeIdValue = CI->getArgOperand(2);2157    Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();2158 2159    SmallVector<DevirtCallSite, 1> DevirtCalls;2160    SmallVector<Instruction *, 1> LoadedPtrs;2161    SmallVector<Instruction *, 1> Preds;2162    bool HasNonCallUses = false;2163    auto &DT = FAM.getResult<DominatorTreeAnalysis>(*CI->getFunction());2164    findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,2165                                               HasNonCallUses, CI, DT);2166 2167    // Start by generating "pessimistic" code that explicitly loads the function2168    // pointer from the vtable and performs the type check. If possible, we will2169    // eliminate the load and the type check later.2170 2171    // If possible, only generate the load at the point where it is used.2172    // This helps avoid unnecessary spills.2173    IRBuilder<> LoadB(2174        (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);2175 2176    Value *LoadedValue = nullptr;2177    if (TypeCheckedLoadFunc->getIntrinsicID() ==2178        Intrinsic::type_checked_load_relative) {2179      Function *LoadRelFunc = Intrinsic::getOrInsertDeclaration(2180          &M, Intrinsic::load_relative, {Int32Ty});2181      LoadedValue = LoadB.CreateCall(LoadRelFunc, {Ptr, Offset});2182    } else {2183      Value *GEP = LoadB.CreatePtrAdd(Ptr, Offset);2184      LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEP);2185    }2186 2187    for (Instruction *LoadedPtr : LoadedPtrs) {2188      LoadedPtr->replaceAllUsesWith(LoadedValue);2189      LoadedPtr->eraseFromParent();2190    }2191 2192    // Likewise for the type test.2193    IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);2194    CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});2195 2196    for (Instruction *Pred : Preds) {2197      Pred->replaceAllUsesWith(TypeTestCall);2198      Pred->eraseFromParent();2199    }2200 2201    // We have already erased any extractvalue instructions that refer to the2202    // intrinsic call, but the intrinsic may have other non-extractvalue uses2203    // (although this is unlikely). In that case, explicitly build a pair and2204    // RAUW it.2205    if (!CI->use_empty()) {2206      Value *Pair = PoisonValue::get(CI->getType());2207      IRBuilder<> B(CI);2208      Pair = B.CreateInsertValue(Pair, LoadedValue, {0});2209      Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});2210      CI->replaceAllUsesWith(Pair);2211    }2212 2213    // The number of unsafe uses is initially the number of uses.2214    auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];2215    NumUnsafeUses = DevirtCalls.size();2216 2217    // If the function pointer has a non-call user, we cannot eliminate the type2218    // check, as one of those users may eventually call the pointer. Increment2219    // the unsafe use count to make sure it cannot reach zero.2220    if (HasNonCallUses)2221      ++NumUnsafeUses;2222    for (DevirtCallSite Call : DevirtCalls) {2223      CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB,2224                                                   &NumUnsafeUses);2225    }2226 2227    CI->eraseFromParent();2228  }2229}2230 2231void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {2232  auto *TypeId = dyn_cast<MDString>(Slot.TypeID);2233  if (!TypeId)2234    return;2235  const TypeIdSummary *TidSummary =2236      ImportSummary->getTypeIdSummary(TypeId->getString());2237  if (!TidSummary)2238    return;2239  auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);2240  if (ResI == TidSummary->WPDRes.end())2241    return;2242  const WholeProgramDevirtResolution &Res = ResI->second;2243 2244  if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {2245    assert(!Res.SingleImplName.empty());2246    // The type of the function in the declaration is irrelevant because every2247    // call site will cast it to the correct type.2248    Constant *SingleImpl =2249        cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,2250                                             Type::getVoidTy(M.getContext()))2251                           .getCallee());2252 2253    // This is the import phase so we should not be exporting anything.2254    bool IsExported = false;2255    applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);2256    assert(!IsExported);2257  }2258 2259  for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {2260    auto I = Res.ResByArg.find(CSByConstantArg.first);2261    if (I == Res.ResByArg.end())2262      continue;2263    auto &ResByArg = I->second;2264    // FIXME: We should figure out what to do about the "function name" argument2265    // to the apply* functions, as the function names are unavailable during the2266    // importing phase. For now we just pass the empty string. This does not2267    // impact correctness because the function names are just used for remarks.2268    switch (ResByArg.TheKind) {2269    case WholeProgramDevirtResolution::ByArg::UniformRetVal:2270      applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);2271      break;2272    case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {2273      Constant *UniqueMemberAddr =2274          importGlobal(Slot, CSByConstantArg.first, "unique_member");2275      applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,2276                           UniqueMemberAddr);2277      break;2278    }2279    case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {2280      Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",2281                                      Int32Ty, ResByArg.Byte);2282      Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,2283                                     ResByArg.Bit);2284      applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);2285      break;2286    }2287    default:2288      break;2289    }2290  }2291 2292  if (Res.TheKind == WholeProgramDevirtResolution::BranchFunnel) {2293    // The type of the function is irrelevant, because it's bitcast at calls2294    // anyhow.2295    auto *JT = cast<Function>(2296        M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),2297                              Type::getVoidTy(M.getContext()))2298            .getCallee());2299    bool IsExported = false;2300    applyICallBranchFunnel(SlotInfo, *JT, IsExported);2301    assert(!IsExported);2302  }2303}2304 2305void DevirtModule::removeRedundantTypeTests() {2306  auto *True = ConstantInt::getTrue(M.getContext());2307  for (auto &&U : NumUnsafeUsesForTypeTest) {2308    if (U.second == 0) {2309      U.first->replaceAllUsesWith(True);2310      U.first->eraseFromParent();2311    }2312  }2313}2314 2315ValueInfo2316DevirtModule::lookUpFunctionValueInfo(Function *TheFn,2317                                      ModuleSummaryIndex *ExportSummary) {2318  assert((ExportSummary != nullptr) &&2319         "Caller guarantees ExportSummary is not nullptr");2320 2321  const auto TheFnGUID = TheFn->getGUID();2322  const auto TheFnGUIDWithExportedName =2323      GlobalValue::getGUIDAssumingExternalLinkage(TheFn->getName());2324  // Look up ValueInfo with the GUID in the current linkage.2325  ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFnGUID);2326  // If no entry is found and GUID is different from GUID computed using2327  // exported name, look up ValueInfo with the exported name unconditionally.2328  // This is a fallback.2329  //2330  // The reason to have a fallback:2331  // 1. LTO could enable global value internalization via2332  // `enable-lto-internalization`.2333  // 2. The GUID in ExportedSummary is computed using exported name.2334  if ((!TheFnVI) && (TheFnGUID != TheFnGUIDWithExportedName)) {2335    TheFnVI = ExportSummary->getValueInfo(TheFnGUIDWithExportedName);2336  }2337  return TheFnVI;2338}2339 2340bool DevirtModule::mustBeUnreachableFunction(2341    Function *const F, ModuleSummaryIndex *ExportSummary) {2342  if (WholeProgramDevirtKeepUnreachableFunction)2343    return false;2344  // First, learn unreachability by analyzing function IR.2345  if (!F->isDeclaration()) {2346    // A function must be unreachable if its entry block ends with an2347    // 'unreachable'.2348    return isa<UnreachableInst>(F->getEntryBlock().getTerminator());2349  }2350  // Learn unreachability from ExportSummary if ExportSummary is present.2351  return ExportSummary &&2352         ::mustBeUnreachableFunction(2353             DevirtModule::lookUpFunctionValueInfo(F, ExportSummary));2354}2355 2356bool DevirtModule::run() {2357  // If only some of the modules were split, we cannot correctly perform2358  // this transformation. We already checked for the presense of type tests2359  // with partially split modules during the thin link, and would have emitted2360  // an error if any were found, so here we can simply return.2361  if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||2362      (ImportSummary && ImportSummary->partiallySplitLTOUnits()))2363    return false;2364 2365  Function *PublicTypeTestFunc = nullptr;2366  // If we are in speculative devirtualization mode, we can work on the public2367  // type test intrinsics.2368  if (ClDevirtualizeSpeculatively)2369    PublicTypeTestFunc =2370        Intrinsic::getDeclarationIfExists(&M, Intrinsic::public_type_test);2371  Function *TypeTestFunc =2372      Intrinsic::getDeclarationIfExists(&M, Intrinsic::type_test);2373  Function *TypeCheckedLoadFunc =2374      Intrinsic::getDeclarationIfExists(&M, Intrinsic::type_checked_load);2375  Function *TypeCheckedLoadRelativeFunc = Intrinsic::getDeclarationIfExists(2376      &M, Intrinsic::type_checked_load_relative);2377  Function *AssumeFunc =2378      Intrinsic::getDeclarationIfExists(&M, Intrinsic::assume);2379 2380  // Normally if there are no users of the devirtualization intrinsics in the2381  // module, this pass has nothing to do. But if we are exporting, we also need2382  // to handle any users that appear only in the function summaries.2383  if (!ExportSummary &&2384      (((!PublicTypeTestFunc || PublicTypeTestFunc->use_empty()) &&2385        (!TypeTestFunc || TypeTestFunc->use_empty())) ||2386       !AssumeFunc || AssumeFunc->use_empty()) &&2387      (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()) &&2388      (!TypeCheckedLoadRelativeFunc ||2389       TypeCheckedLoadRelativeFunc->use_empty()))2390    return false;2391 2392  // Rebuild type metadata into a map for easy lookup.2393  std::vector<VTableBits> Bits;2394  DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;2395  buildTypeIdentifierMap(Bits, TypeIdMap);2396 2397  if (PublicTypeTestFunc && AssumeFunc)2398    scanTypeTestUsers(PublicTypeTestFunc, TypeIdMap);2399 2400  if (TypeTestFunc && AssumeFunc)2401    scanTypeTestUsers(TypeTestFunc, TypeIdMap);2402 2403  if (TypeCheckedLoadFunc)2404    scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);2405 2406  if (TypeCheckedLoadRelativeFunc)2407    scanTypeCheckedLoadUsers(TypeCheckedLoadRelativeFunc);2408 2409  if (ImportSummary) {2410    for (auto &S : CallSlots)2411      importResolution(S.first, S.second);2412 2413    removeRedundantTypeTests();2414 2415    // We have lowered or deleted the type intrinsics, so we will no longer have2416    // enough information to reason about the liveness of virtual function2417    // pointers in GlobalDCE.2418    for (GlobalVariable &GV : M.globals())2419      GV.eraseMetadata(LLVMContext::MD_vcall_visibility);2420 2421    // The rest of the code is only necessary when exporting or during regular2422    // LTO, so we are done.2423    return true;2424  }2425 2426  if (TypeIdMap.empty())2427    return true;2428 2429  // Collect information from summary about which calls to try to devirtualize.2430  if (ExportSummary) {2431    DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;2432    for (auto &P : TypeIdMap) {2433      if (auto *TypeId = dyn_cast<MDString>(P.first))2434        MetadataByGUID[GlobalValue::getGUIDAssumingExternalLinkage(2435                           TypeId->getString())]2436            .push_back(TypeId);2437    }2438 2439    for (auto &P : *ExportSummary) {2440      for (auto &S : P.second.getSummaryList()) {2441        auto *FS = dyn_cast<FunctionSummary>(S.get());2442        if (!FS)2443          continue;2444        // FIXME: Only add live functions.2445        for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {2446          for (Metadata *MD : MetadataByGUID[VF.GUID]) {2447            CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);2448          }2449        }2450        for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {2451          for (Metadata *MD : MetadataByGUID[VF.GUID]) {2452            CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);2453          }2454        }2455        for (const FunctionSummary::ConstVCall &VC :2456             FS->type_test_assume_const_vcalls()) {2457          for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {2458            CallSlots[{MD, VC.VFunc.Offset}]2459                .ConstCSInfo[VC.Args]2460                .addSummaryTypeTestAssumeUser(FS);2461          }2462        }2463        for (const FunctionSummary::ConstVCall &VC :2464             FS->type_checked_load_const_vcalls()) {2465          for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {2466            CallSlots[{MD, VC.VFunc.Offset}]2467                .ConstCSInfo[VC.Args]2468                .addSummaryTypeCheckedLoadUser(FS);2469          }2470        }2471      }2472    }2473  }2474 2475  // For each (type, offset) pair:2476  bool DidVirtualConstProp = false;2477  std::map<std::string, GlobalValue *> DevirtTargets;2478  for (auto &S : CallSlots) {2479    // Search each of the members of the type identifier for the virtual2480    // function implementation at offset S.first.ByteOffset, and add to2481    // TargetsForSlot.2482    std::vector<VirtualCallTarget> TargetsForSlot;2483    WholeProgramDevirtResolution *Res = nullptr;2484    const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[S.first.TypeID];2485    if (ExportSummary && isa<MDString>(S.first.TypeID) &&2486        TypeMemberInfos.size())2487      // For any type id used on a global's type metadata, create the type id2488      // summary resolution regardless of whether we can devirtualize, so that2489      // lower type tests knows the type id is not Unsat. If it was not used on2490      // a global's type metadata, the TypeIdMap entry set will be empty, and2491      // we don't want to create an entry (with the default Unknown type2492      // resolution), which can prevent detection of the Unsat.2493      Res = &ExportSummary2494                 ->getOrInsertTypeIdSummary(2495                     cast<MDString>(S.first.TypeID)->getString())2496                 .WPDRes[S.first.ByteOffset];2497    if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos,2498                                  S.first.ByteOffset, ExportSummary)) {2499      bool SingleImplDevirt =2500          trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res);2501      // Out of speculative devirtualization mode, Try to apply virtual constant2502      // propagation or branch funneling.2503      // TODO: This should eventually be enabled for non-public type tests.2504      if (!SingleImplDevirt && !ClDevirtualizeSpeculatively) {2505        DidVirtualConstProp |=2506            tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);2507 2508        tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);2509      }2510 2511      // Collect functions devirtualized at least for one call site for stats.2512      if (RemarksEnabled || AreStatisticsEnabled())2513        for (const auto &T : TargetsForSlot)2514          if (T.WasDevirt)2515            DevirtTargets[std::string(T.Fn->getName())] = T.Fn;2516    }2517 2518    // CFI-specific: if we are exporting and any llvm.type.checked.load2519    // intrinsics were *not* devirtualized, we need to add the resulting2520    // llvm.type.test intrinsics to the function summaries so that the2521    // LowerTypeTests pass will export them.2522    if (ExportSummary && isa<MDString>(S.first.TypeID)) {2523      auto GUID = GlobalValue::getGUIDAssumingExternalLinkage(2524          cast<MDString>(S.first.TypeID)->getString());2525      auto AddTypeTestsForTypeCheckedLoads = [&](CallSiteInfo &CSI) {2526        if (!CSI.AllCallSitesDevirted)2527          for (auto *FS : CSI.SummaryTypeCheckedLoadUsers)2528            FS->addTypeTest(GUID);2529      };2530      AddTypeTestsForTypeCheckedLoads(S.second.CSInfo);2531      for (auto &CCS : S.second.ConstCSInfo)2532        AddTypeTestsForTypeCheckedLoads(CCS.second);2533    }2534  }2535 2536  if (RemarksEnabled) {2537    // Generate remarks for each devirtualized function.2538    for (const auto &DT : DevirtTargets) {2539      GlobalValue *GV = DT.second;2540      auto *F = dyn_cast<Function>(GV);2541      if (!F) {2542        auto *A = dyn_cast<GlobalAlias>(GV);2543        assert(A && isa<Function>(A->getAliasee()));2544        F = dyn_cast<Function>(A->getAliasee());2545        assert(F);2546      }2547 2548      using namespace ore;2549      OREGetter(*F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)2550                         << "devirtualized " << NV("FunctionName", DT.first));2551    }2552  }2553 2554  NumDevirtTargets += DevirtTargets.size();2555 2556  removeRedundantTypeTests();2557 2558  // Rebuild each global we touched as part of virtual constant propagation to2559  // include the before and after bytes.2560  if (DidVirtualConstProp)2561    for (VTableBits &B : Bits)2562      rebuildGlobal(B);2563 2564  // We have lowered or deleted the type intrinsics, so we will no longer have2565  // enough information to reason about the liveness of virtual function2566  // pointers in GlobalDCE.2567  for (GlobalVariable &GV : M.globals())2568    GV.eraseMetadata(LLVMContext::MD_vcall_visibility);2569 2570  for (auto *CI : CallsWithPtrAuthBundleRemoved)2571    CI->eraseFromParent();2572 2573  return true;2574}2575 2576void DevirtIndex::run() {2577  if (ExportSummary.typeIdCompatibleVtableMap().empty())2578    return;2579 2580  // Assert that we haven't made any changes that would affect the hasLocal()2581  // flag on the GUID summary info.2582  assert(!ExportSummary.withInternalizeAndPromote() &&2583         "Expect index-based WPD to run before internalization and promotion");2584 2585  DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;2586  for (const auto &P : ExportSummary.typeIdCompatibleVtableMap()) {2587    NameByGUID[GlobalValue::getGUIDAssumingExternalLinkage(P.first)].push_back(2588        P.first);2589    // Create the type id summary resolution regardlness of whether we can2590    // devirtualize, so that lower type tests knows the type id is used on2591    // a global and not Unsat. We do this here rather than in the loop over the2592    // CallSlots, since that handling will only see type tests that directly2593    // feed assumes, and we would miss any that aren't currently handled by WPD2594    // (such as type tests that feed assumes via phis).2595    ExportSummary.getOrInsertTypeIdSummary(P.first);2596  }2597 2598  // Collect information from summary about which calls to try to devirtualize.2599  for (auto &P : ExportSummary) {2600    for (auto &S : P.second.getSummaryList()) {2601      auto *FS = dyn_cast<FunctionSummary>(S.get());2602      if (!FS)2603        continue;2604      // FIXME: Only add live functions.2605      for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {2606        for (StringRef Name : NameByGUID[VF.GUID]) {2607          CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);2608        }2609      }2610      for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {2611        for (StringRef Name : NameByGUID[VF.GUID]) {2612          CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);2613        }2614      }2615      for (const FunctionSummary::ConstVCall &VC :2616           FS->type_test_assume_const_vcalls()) {2617        for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {2618          CallSlots[{Name, VC.VFunc.Offset}]2619              .ConstCSInfo[VC.Args]2620              .addSummaryTypeTestAssumeUser(FS);2621        }2622      }2623      for (const FunctionSummary::ConstVCall &VC :2624           FS->type_checked_load_const_vcalls()) {2625        for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {2626          CallSlots[{Name, VC.VFunc.Offset}]2627              .ConstCSInfo[VC.Args]2628              .addSummaryTypeCheckedLoadUser(FS);2629        }2630      }2631    }2632  }2633 2634  std::set<ValueInfo> DevirtTargets;2635  // For each (type, offset) pair:2636  for (auto &S : CallSlots) {2637    // Search each of the members of the type identifier for the virtual2638    // function implementation at offset S.first.ByteOffset, and add to2639    // TargetsForSlot.2640    std::vector<ValueInfo> TargetsForSlot;2641    auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);2642    assert(TidSummary);2643    // The type id summary would have been created while building the NameByGUID2644    // map earlier.2645    WholeProgramDevirtResolution *Res =2646        &ExportSummary.getTypeIdSummary(S.first.TypeID)2647             ->WPDRes[S.first.ByteOffset];2648    if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,2649                                  S.first.ByteOffset)) {2650 2651      if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,2652                               DevirtTargets))2653        continue;2654    }2655  }2656 2657  // Optionally have the thin link print message for each devirtualized2658  // function.2659  if (PrintSummaryDevirt)2660    for (const auto &DT : DevirtTargets)2661      errs() << "Devirtualized call to " << DT << "\n";2662 2663  NumDevirtTargets += DevirtTargets.size();2664}2665