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