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

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