contrib/llvm-project/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

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