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