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

   1 //===- LowerTypeTests.cpp - type metadata lowering pass -------------------===//
   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 lowers type metadata and calls to the llvm.type.test intrinsic.
  11 // It also ensures that globals are properly laid out for the
  12 // llvm.icall.branch.funnel intrinsic.
  13 // See http://llvm.org/docs/TypeMetadata.html for more information.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/IPO/LowerTypeTests.h"
  18 #include "llvm/ADT/APInt.h"
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/EquivalenceClasses.h"
  22 #include "llvm/ADT/PointerUnion.h"
  23 #include "llvm/ADT/SetVector.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/TinyPtrVector.h"
  28 #include "llvm/ADT/Triple.h"
  29 #include "llvm/Analysis/TypeMetadataUtils.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/IR/Attributes.h"
  32 #include "llvm/IR/BasicBlock.h"
  33 #include "llvm/IR/Constant.h"
  34 #include "llvm/IR/Constants.h"
  35 #include "llvm/IR/DataLayout.h"
  36 #include "llvm/IR/DerivedTypes.h"
  37 #include "llvm/IR/Function.h"
  38 #include "llvm/IR/GlobalAlias.h"
  39 #include "llvm/IR/GlobalObject.h"
  40 #include "llvm/IR/GlobalValue.h"
  41 #include "llvm/IR/GlobalVariable.h"
  42 #include "llvm/IR/IRBuilder.h"
  43 #include "llvm/IR/InlineAsm.h"
  44 #include "llvm/IR/Instruction.h"
  45 #include "llvm/IR/Instructions.h"
  46 #include "llvm/IR/Intrinsics.h"
  47 #include "llvm/IR/LLVMContext.h"
  48 #include "llvm/IR/Metadata.h"
  49 #include "llvm/IR/Module.h"
  50 #include "llvm/IR/ModuleSummaryIndex.h"
  51 #include "llvm/IR/ModuleSummaryIndexYAML.h"
  52 #include "llvm/IR/Operator.h"
  53 #include "llvm/IR/PassManager.h"
  54 #include "llvm/IR/Type.h"
  55 #include "llvm/IR/Use.h"
  56 #include "llvm/IR/User.h"
  57 #include "llvm/IR/Value.h"
  58 #include "llvm/Pass.h"
  59 #include "llvm/Support/Allocator.h"
  60 #include "llvm/Support/Casting.h"
  61 #include "llvm/Support/CommandLine.h"
  62 #include "llvm/Support/Debug.h"
  63 #include "llvm/Support/Error.h"
  64 #include "llvm/Support/ErrorHandling.h"
  65 #include "llvm/Support/FileSystem.h"
  66 #include "llvm/Support/MathExtras.h"
  67 #include "llvm/Support/MemoryBuffer.h"
  68 #include "llvm/Support/TrailingObjects.h"
  69 #include "llvm/Support/YAMLTraits.h"
  70 #include "llvm/Support/raw_ostream.h"
  71 #include "llvm/Transforms/IPO.h"
  72 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  73 #include "llvm/Transforms/Utils/ModuleUtils.h"
  74 #include <algorithm>
  75 #include <cassert>
  76 #include <cstdint>
  77 #include <memory>
  78 #include <set>
  79 #include <string>
  80 #include <system_error>
  81 #include <utility>
  82 #include <vector>
  83
  84 using namespace llvm;
  85 using namespace lowertypetests;
  86
  87 #define DEBUG_TYPE "lowertypetests"
  88
  89 STATISTIC(ByteArraySizeBits, "Byte array size in bits");
  90 STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
  91 STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
  92 STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
  93 STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
  94
  95 static cl::opt<bool> AvoidReuse(
  96     "lowertypetests-avoid-reuse",
  97     cl::desc("Try to avoid reuse of byte array addresses using aliases"),
  98     cl::Hidden, cl::init(true));
  99
 100 static cl::opt<PassSummaryAction> ClSummaryAction(
 101     "lowertypetests-summary-action",
 102     cl::desc("What to do with the summary when running this pass"),
 103     cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
 104                clEnumValN(PassSummaryAction::Import, "import",
 105                           "Import typeid resolutions from summary and globals"),
 106                clEnumValN(PassSummaryAction::Export, "export",
 107                           "Export typeid resolutions to summary and globals")),
 108     cl::Hidden);
 109
 110 static cl::opt<std::string> ClReadSummary(
 111     "lowertypetests-read-summary",
 112     cl::desc("Read summary from given YAML file before running pass"),
 113     cl::Hidden);
 114
 115 static cl::opt<std::string> ClWriteSummary(
 116     "lowertypetests-write-summary",
 117     cl::desc("Write summary to given YAML file after running pass"),
 118     cl::Hidden);
 119
 120 bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
 121   if (Offset < ByteOffset)
 122     return false;
 123
 124   if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
 125     return false;
 126
 127   uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
 128   if (BitOffset >= BitSize)
 129     return false;
 130
 131   return Bits.count(BitOffset);
 132 }
 133
 134 void BitSetInfo::print(raw_ostream &OS) const {
 135   OS << "offset " << ByteOffset << " size " << BitSize << " align "
 136      << (1 << AlignLog2);
 137
 138   if (isAllOnes()) {
 139     OS << " all-ones\n";
 140     return;
 141   }
 142
 143   OS << " { ";
 144   for (uint64_t B : Bits)
 145     OS << B << ' ';
 146   OS << "}\n";
 147 }
 148
 149 BitSetInfo BitSetBuilder::build() {
 150   if (Min > Max)
 151     Min = 0;
 152
 153   // Normalize each offset against the minimum observed offset, and compute
 154   // the bitwise OR of each of the offsets. The number of trailing zeros
 155   // in the mask gives us the log2 of the alignment of all offsets, which
 156   // allows us to compress the bitset by only storing one bit per aligned
 157   // address.
 158   uint64_t Mask = 0;
 159   for (uint64_t &Offset : Offsets) {
 160     Offset -= Min;
 161     Mask |= Offset;
 162   }
 163
 164   BitSetInfo BSI;
 165   BSI.ByteOffset = Min;
 166
 167   BSI.AlignLog2 = 0;
 168   if (Mask != 0)
 169     BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined);
 170
 171   // Build the compressed bitset while normalizing the offsets against the
 172   // computed alignment.
 173   BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
 174   for (uint64_t Offset : Offsets) {
 175     Offset >>= BSI.AlignLog2;
 176     BSI.Bits.insert(Offset);
 177   }
 178
 179   return BSI;
 180 }
 181
 182 void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
 183   // Create a new fragment to hold the layout for F.
 184   Fragments.emplace_back();
 185   std::vector<uint64_t> &Fragment = Fragments.back();
 186   uint64_t FragmentIndex = Fragments.size() - 1;
 187
 188   for (auto ObjIndex : F) {
 189     uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
 190     if (OldFragmentIndex == 0) {
 191       // We haven't seen this object index before, so just add it to the current
 192       // fragment.
 193       Fragment.push_back(ObjIndex);
 194     } else {
 195       // This index belongs to an existing fragment. Copy the elements of the
 196       // old fragment into this one and clear the old fragment. We don't update
 197       // the fragment map just yet, this ensures that any further references to
 198       // indices from the old fragment in this fragment do not insert any more
 199       // indices.
 200       std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
 201       Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end());
 202       OldFragment.clear();
 203     }
 204   }
 205
 206   // Update the fragment map to point our object indices to this fragment.
 207   for (uint64_t ObjIndex : Fragment)
 208     FragmentMap[ObjIndex] = FragmentIndex;
 209 }
 210
 211 void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
 212                                 uint64_t BitSize, uint64_t &AllocByteOffset,
 213                                 uint8_t &AllocMask) {
 214   // Find the smallest current allocation.
 215   unsigned Bit = 0;
 216   for (unsigned I = 1; I != BitsPerByte; ++I)
 217     if (BitAllocs[I] < BitAllocs[Bit])
 218       Bit = I;
 219
 220   AllocByteOffset = BitAllocs[Bit];
 221
 222   // Add our size to it.
 223   unsigned ReqSize = AllocByteOffset + BitSize;
 224   BitAllocs[Bit] = ReqSize;
 225   if (Bytes.size() < ReqSize)
 226     Bytes.resize(ReqSize);
 227
 228   // Set our bits.
 229   AllocMask = 1 << Bit;
 230   for (uint64_t B : Bits)
 231     Bytes[AllocByteOffset + B] |= AllocMask;
 232 }
 233
 234 namespace {
 235
 236 struct ByteArrayInfo {
 237   std::set<uint64_t> Bits;
 238   uint64_t BitSize;
 239   GlobalVariable *ByteArray;
 240   GlobalVariable *MaskGlobal;
 241   uint8_t *MaskPtr = nullptr;
 242 };
 243
 244 /// A POD-like structure that we use to store a global reference together with
 245 /// its metadata types. In this pass we frequently need to query the set of
 246 /// metadata types referenced by a global, which at the IR level is an expensive
 247 /// operation involving a map lookup; this data structure helps to reduce the
 248 /// number of times we need to do this lookup.
 249 class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
 250   friend TrailingObjects;
 251
 252   GlobalObject *GO;
 253   size_t NTypes;
 254
 255   // For functions: true if this is a definition (either in the merged module or
 256   // in one of the thinlto modules).
 257   bool IsDefinition;
 258
 259   // For functions: true if this function is either defined or used in a thinlto
 260   // module and its jumptable entry needs to be exported to thinlto backends.
 261   bool IsExported;
 262
 263   size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; }
 264
 265 public:
 266   static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
 267                                   bool IsDefinition, bool IsExported,
 268                                   ArrayRef<MDNode *> Types) {
 269     auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
 270         totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember)));
 271     GTM->GO = GO;
 272     GTM->NTypes = Types.size();
 273     GTM->IsDefinition = IsDefinition;
 274     GTM->IsExported = IsExported;
 275     std::uninitialized_copy(Types.begin(), Types.end(),
 276                             GTM->getTrailingObjects<MDNode *>());
 277     return GTM;
 278   }
 279
 280   GlobalObject *getGlobal() const {
 281     return GO;
 282   }
 283
 284   bool isDefinition() const {
 285     return IsDefinition;
 286   }
 287
 288   bool isExported() const {
 289     return IsExported;
 290   }
 291
 292   ArrayRef<MDNode *> types() const {
 293     return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
 294   }
 295 };
 296
 297 struct ICallBranchFunnel final
 298     : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
 299   static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
 300                                    ArrayRef<GlobalTypeMember *> Targets,
 301                                    unsigned UniqueId) {
 302     auto *Call = static_cast<ICallBranchFunnel *>(
 303         Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()),
 304                        alignof(ICallBranchFunnel)));
 305     Call->CI = CI;
 306     Call->UniqueId = UniqueId;
 307     Call->NTargets = Targets.size();
 308     std::uninitialized_copy(Targets.begin(), Targets.end(),
 309                             Call->getTrailingObjects<GlobalTypeMember *>());
 310     return Call;
 311   }
 312
 313   CallInst *CI;
 314   ArrayRef<GlobalTypeMember *> targets() const {
 315     return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
 316   }
 317
 318   unsigned UniqueId;
 319
 320 private:
 321   size_t NTargets;
 322 };
 323
 324 class LowerTypeTestsModule {
 325   Module &M;
 326
 327   ModuleSummaryIndex *ExportSummary;
 328   const ModuleSummaryIndex *ImportSummary;
 329
 330   Triple::ArchType Arch;
 331   Triple::OSType OS;
 332   Triple::ObjectFormatType ObjectFormat;
 333
 334   IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
 335   IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
 336   PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
 337   ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0);
 338   IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
 339   PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty);
 340   IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
 341   IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
 342
 343   // Indirect function call index assignment counter for WebAssembly
 344   uint64_t IndirectIndex = 1;
 345
 346   // Mapping from type identifiers to the call sites that test them, as well as
 347   // whether the type identifier needs to be exported to ThinLTO backends as
 348   // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
 349   struct TypeIdUserInfo {
 350     std::vector<CallInst *> CallSites;
 351     bool IsExported = false;
 352   };
 353   DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers;
 354
 355   /// This structure describes how to lower type tests for a particular type
 356   /// identifier. It is either built directly from the global analysis (during
 357   /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
 358   /// identifier summaries and external symbol references (in ThinLTO backends).
 359   struct TypeIdLowering {
 360     TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat;
 361
 362     /// All except Unsat: the start address within the combined global.
 363     Constant *OffsetedGlobal;
 364
 365     /// ByteArray, Inline, AllOnes: log2 of the required global alignment
 366     /// relative to the start address.
 367     Constant *AlignLog2;
 368
 369     /// ByteArray, Inline, AllOnes: one less than the size of the memory region
 370     /// covering members of this type identifier as a multiple of 2^AlignLog2.
 371     Constant *SizeM1;
 372
 373     /// ByteArray: the byte array to test the address against.
 374     Constant *TheByteArray;
 375
 376     /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
 377     Constant *BitMask;
 378
 379     /// Inline: the bit mask to test the address against.
 380     Constant *InlineBits;
 381   };
 382
 383   std::vector<ByteArrayInfo> ByteArrayInfos;
 384
 385   Function *WeakInitializerFn = nullptr;
 386
 387   bool shouldExportConstantsAsAbsoluteSymbols();
 388   uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
 389   TypeIdLowering importTypeId(StringRef TypeId);
 390   void importTypeTest(CallInst *CI);
 391   void importFunction(Function *F, bool isDefinition);
 392
 393   BitSetInfo
 394   buildBitSet(Metadata *TypeId,
 395               const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
 396   ByteArrayInfo *createByteArray(BitSetInfo &BSI);
 397   void allocateByteArrays();
 398   Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
 399                           Value *BitOffset);
 400   void lowerTypeTestCalls(
 401       ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
 402       const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
 403   Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
 404                            const TypeIdLowering &TIL);
 405
 406   void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
 407                                        ArrayRef<GlobalTypeMember *> Globals);
 408   unsigned getJumpTableEntrySize();
 409   Type *getJumpTableEntryType();
 410   void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
 411                             Triple::ArchType JumpTableArch,
 412                             SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
 413   void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
 414   void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
 415                                  ArrayRef<GlobalTypeMember *> Functions);
 416   void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
 417                                        ArrayRef<GlobalTypeMember *> Functions);
 418   void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
 419                                      ArrayRef<GlobalTypeMember *> Functions);
 420   void
 421   buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
 422                               ArrayRef<GlobalTypeMember *> Globals,
 423                               ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
 424
 425   void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT, bool IsDefinition);
 426   void moveInitializerToModuleConstructor(GlobalVariable *GV);
 427   void findGlobalVariableUsersOf(Constant *C,
 428                                  SmallSetVector<GlobalVariable *, 8> &Out);
 429
 430   void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
 431
 432   /// replaceCfiUses - Go through the uses list for this definition
 433   /// and make each use point to "V" instead of "this" when the use is outside
 434   /// the block. 'This's use list is expected to have at least one element.
 435   /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
 436   /// uses.
 437   void replaceCfiUses(Function *Old, Value *New, bool IsDefinition);
 438
 439   /// replaceDirectCalls - Go through the uses list for this definition and
 440   /// replace each use, which is a direct function call.
 441   void replaceDirectCalls(Value *Old, Value *New);
 442
 443 public:
 444   LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary,
 445                        const ModuleSummaryIndex *ImportSummary);
 446
 447   bool lower();
 448
 449   // Lower the module using the action and summary passed as command line
 450   // arguments. For testing purposes only.
 451   static bool runForTesting(Module &M);
 452 };
 453
 454 struct LowerTypeTests : public ModulePass {
 455   static char ID;
 456
 457   bool UseCommandLine = false;
 458
 459   ModuleSummaryIndex *ExportSummary;
 460   const ModuleSummaryIndex *ImportSummary;
 461
 462   LowerTypeTests() : ModulePass(ID), UseCommandLine(true) {
 463     initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
 464   }
 465
 466   LowerTypeTests(ModuleSummaryIndex *ExportSummary,
 467                  const ModuleSummaryIndex *ImportSummary)
 468       : ModulePass(ID), ExportSummary(ExportSummary),
 469         ImportSummary(ImportSummary) {
 470     initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
 471   }
 472
 473   bool runOnModule(Module &M) override {
 474     if (UseCommandLine)
 475       return LowerTypeTestsModule::runForTesting(M);
 476     return LowerTypeTestsModule(M, ExportSummary, ImportSummary).lower();
 477   }
 478 };
 479
 480 } // end anonymous namespace
 481
 482 char LowerTypeTests::ID = 0;
 483
 484 INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,
 485                 false)
 486
 487 ModulePass *
 488 llvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary,
 489                                const ModuleSummaryIndex *ImportSummary) {
 490   return new LowerTypeTests(ExportSummary, ImportSummary);
 491 }
 492
 493 /// Build a bit set for TypeId using the object layouts in
 494 /// GlobalLayout.
 495 BitSetInfo LowerTypeTestsModule::buildBitSet(
 496     Metadata *TypeId,
 497     const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
 498   BitSetBuilder BSB;
 499
 500   // Compute the byte offset of each address associated with this type
 501   // identifier.
 502   for (auto &GlobalAndOffset : GlobalLayout) {
 503     for (MDNode *Type : GlobalAndOffset.first->types()) {
 504       if (Type->getOperand(1) != TypeId)
 505         continue;
 506       uint64_t Offset =
 507           cast<ConstantInt>(
 508               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 509               ->getZExtValue();
 510       BSB.addOffset(GlobalAndOffset.second + Offset);
 511     }
 512   }
 513
 514   return BSB.build();
 515 }
 516
 517 /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
 518 /// Bits. This pattern matches to the bt instruction on x86.
 519 static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits,
 520                                   Value *BitOffset) {
 521   auto BitsType = cast<IntegerType>(Bits->getType());
 522   unsigned BitWidth = BitsType->getBitWidth();
 523
 524   BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
 525   Value *BitIndex =
 526       B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
 527   Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
 528   Value *MaskedBits = B.CreateAnd(Bits, BitMask);
 529   return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
 530 }
 531
 532 ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
 533   // Create globals to stand in for byte arrays and masks. These never actually
 534   // get initialized, we RAUW and erase them later in allocateByteArrays() once
 535   // we know the offset and mask to use.
 536   auto ByteArrayGlobal = new GlobalVariable(
 537       M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
 538   auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
 539                                        GlobalValue::PrivateLinkage, nullptr);
 540
 541   ByteArrayInfos.emplace_back();
 542   ByteArrayInfo *BAI = &ByteArrayInfos.back();
 543
 544   BAI->Bits = BSI.Bits;
 545   BAI->BitSize = BSI.BitSize;
 546   BAI->ByteArray = ByteArrayGlobal;
 547   BAI->MaskGlobal = MaskGlobal;
 548   return BAI;
 549 }
 550
 551 void LowerTypeTestsModule::allocateByteArrays() {
 552   std::stable_sort(ByteArrayInfos.begin(), ByteArrayInfos.end(),
 553                    [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
 554                      return BAI1.BitSize > BAI2.BitSize;
 555                    });
 556
 557   std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
 558
 559   ByteArrayBuilder BAB;
 560   for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
 561     ByteArrayInfo *BAI = &ByteArrayInfos[I];
 562
 563     uint8_t Mask;
 564     BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
 565
 566     BAI->MaskGlobal->replaceAllUsesWith(
 567         ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
 568     BAI->MaskGlobal->eraseFromParent();
 569     if (BAI->MaskPtr)
 570       *BAI->MaskPtr = Mask;
 571   }
 572
 573   Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
 574   auto ByteArray =
 575       new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
 576                          GlobalValue::PrivateLinkage, ByteArrayConst);
 577
 578   for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
 579     ByteArrayInfo *BAI = &ByteArrayInfos[I];
 580
 581     Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
 582                         ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
 583     Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(
 584         ByteArrayConst->getType(), ByteArray, Idxs);
 585
 586     // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
 587     // that the pc-relative displacement is folded into the lea instead of the
 588     // test instruction getting another displacement.
 589     GlobalAlias *Alias = GlobalAlias::create(
 590         Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
 591     BAI->ByteArray->replaceAllUsesWith(Alias);
 592     BAI->ByteArray->eraseFromParent();
 593   }
 594
 595   ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
 596                       BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
 597                       BAB.BitAllocs[6] + BAB.BitAllocs[7];
 598   ByteArraySizeBytes = BAB.Bytes.size();
 599 }
 600
 601 /// Build a test that bit BitOffset is set in the type identifier that was
 602 /// lowered to TIL, which must be either an Inline or a ByteArray.
 603 Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
 604                                               const TypeIdLowering &TIL,
 605                                               Value *BitOffset) {
 606   if (TIL.TheKind == TypeTestResolution::Inline) {
 607     // If the bit set is sufficiently small, we can avoid a load by bit testing
 608     // a constant.
 609     return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
 610   } else {
 611     Constant *ByteArray = TIL.TheByteArray;
 612     if (AvoidReuse && !ImportSummary) {
 613       // Each use of the byte array uses a different alias. This makes the
 614       // backend less likely to reuse previously computed byte array addresses,
 615       // improving the security of the CFI mechanism based on this pass.
 616       // This won't work when importing because TheByteArray is external.
 617       ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage,
 618                                       "bits_use", ByteArray, &M);
 619     }
 620
 621     Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
 622     Value *Byte = B.CreateLoad(ByteAddr);
 623
 624     Value *ByteAndMask =
 625         B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
 626     return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
 627   }
 628 }
 629
 630 static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
 631                                 Value *V, uint64_t COffset) {
 632   if (auto GV = dyn_cast<GlobalObject>(V)) {
 633     SmallVector<MDNode *, 2> Types;
 634     GV->getMetadata(LLVMContext::MD_type, Types);
 635     for (MDNode *Type : Types) {
 636       if (Type->getOperand(1) != TypeId)
 637         continue;
 638       uint64_t Offset =
 639           cast<ConstantInt>(
 640               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 641               ->getZExtValue();
 642       if (COffset == Offset)
 643         return true;
 644     }
 645     return false;
 646   }
 647
 648   if (auto GEP = dyn_cast<GEPOperator>(V)) {
 649     APInt APOffset(DL.getPointerSizeInBits(0), 0);
 650     bool Result = GEP->accumulateConstantOffset(DL, APOffset);
 651     if (!Result)
 652       return false;
 653     COffset += APOffset.getZExtValue();
 654     return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
 655   }
 656
 657   if (auto Op = dyn_cast<Operator>(V)) {
 658     if (Op->getOpcode() == Instruction::BitCast)
 659       return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
 660
 661     if (Op->getOpcode() == Instruction::Select)
 662       return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
 663              isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
 664   }
 665
 666   return false;
 667 }
 668
 669 /// Lower a llvm.type.test call to its implementation. Returns the value to
 670 /// replace the call with.
 671 Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
 672                                                const TypeIdLowering &TIL) {
 673   if (TIL.TheKind == TypeTestResolution::Unsat)
 674     return ConstantInt::getFalse(M.getContext());
 675
 676   Value *Ptr = CI->getArgOperand(0);
 677   const DataLayout &DL = M.getDataLayout();
 678   if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
 679     return ConstantInt::getTrue(M.getContext());
 680
 681   BasicBlock *InitialBB = CI->getParent();
 682
 683   IRBuilder<> B(CI);
 684
 685   Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
 686
 687   Constant *OffsetedGlobalAsInt =
 688       ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
 689   if (TIL.TheKind == TypeTestResolution::Single)
 690     return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
 691
 692   Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
 693
 694   // We need to check that the offset both falls within our range and is
 695   // suitably aligned. We can check both properties at the same time by
 696   // performing a right rotate by log2(alignment) followed by an integer
 697   // comparison against the bitset size. The rotate will move the lower
 698   // order bits that need to be zero into the higher order bits of the
 699   // result, causing the comparison to fail if they are nonzero. The rotate
 700   // also conveniently gives us a bit offset to use during the load from
 701   // the bitset.
 702   Value *OffsetSHR =
 703       B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
 704   Value *OffsetSHL = B.CreateShl(
 705       PtrOffset, ConstantExpr::getZExt(
 706                      ConstantExpr::getSub(
 707                          ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
 708                          TIL.AlignLog2),
 709                      IntPtrTy));
 710   Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
 711
 712   Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1);
 713
 714   // If the bit set is all ones, testing against it is unnecessary.
 715   if (TIL.TheKind == TypeTestResolution::AllOnes)
 716     return OffsetInRange;
 717
 718   // See if the intrinsic is used in the following common pattern:
 719   //   br(llvm.type.test(...), thenbb, elsebb)
 720   // where nothing happens between the type test and the br.
 721   // If so, create slightly simpler IR.
 722   if (CI->hasOneUse())
 723     if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin()))
 724       if (CI->getNextNode() == Br) {
 725         BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator());
 726         BasicBlock *Else = Br->getSuccessor(1);
 727         BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange);
 728         NewBr->setMetadata(LLVMContext::MD_prof,
 729                            Br->getMetadata(LLVMContext::MD_prof));
 730         ReplaceInstWithInst(InitialBB->getTerminator(), NewBr);
 731
 732         // Update phis in Else resulting from InitialBB being split
 733         for (auto &Phi : Else->phis())
 734           Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB);
 735
 736         IRBuilder<> ThenB(CI);
 737         return createBitSetTest(ThenB, TIL, BitOffset);
 738       }
 739
 740   IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false));
 741
 742   // Now that we know that the offset is in range and aligned, load the
 743   // appropriate bit from the bitset.
 744   Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
 745
 746   // The value we want is 0 if we came directly from the initial block
 747   // (having failed the range or alignment checks), or the loaded bit if
 748   // we came from the block in which we loaded it.
 749   B.SetInsertPoint(CI);
 750   PHINode *P = B.CreatePHI(Int1Ty, 2);
 751   P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
 752   P->addIncoming(Bit, ThenB.GetInsertBlock());
 753   return P;
 754 }
 755
 756 /// Given a disjoint set of type identifiers and globals, lay out the globals,
 757 /// build the bit sets and lower the llvm.type.test calls.
 758 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
 759     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
 760   // Build a new global with the combined contents of the referenced globals.
 761   // This global is a struct whose even-indexed elements contain the original
 762   // contents of the referenced globals and whose odd-indexed elements contain
 763   // any padding required to align the next element to the next power of 2.
 764   std::vector<Constant *> GlobalInits;
 765   const DataLayout &DL = M.getDataLayout();
 766   for (GlobalTypeMember *G : Globals) {
 767     GlobalVariable *GV = cast<GlobalVariable>(G->getGlobal());
 768     GlobalInits.push_back(GV->getInitializer());
 769     uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
 770
 771     // Compute the amount of padding required.
 772     uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize;
 773
 774     // Experiments of different caps with Chromium on both x64 and ARM64
 775     // have shown that the 32-byte cap generates the smallest binary on
 776     // both platforms while different caps yield similar performance.
 777     // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
 778     if (Padding > 32)
 779       Padding = alignTo(InitSize, 32) - InitSize;
 780
 781     GlobalInits.push_back(
 782         ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding)));
 783   }
 784   if (!GlobalInits.empty())
 785     GlobalInits.pop_back();
 786   Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
 787   auto *CombinedGlobal =
 788       new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
 789                          GlobalValue::PrivateLinkage, NewInit);
 790
 791   StructType *NewTy = cast<StructType>(NewInit->getType());
 792   const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy);
 793
 794   // Compute the offsets of the original globals within the new global.
 795   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
 796   for (unsigned I = 0; I != Globals.size(); ++I)
 797     // Multiply by 2 to account for padding elements.
 798     GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2);
 799
 800   lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
 801
 802   // Build aliases pointing to offsets into the combined global for each
 803   // global from which we built the combined global, and replace references
 804   // to the original globals with references to the aliases.
 805   for (unsigned I = 0; I != Globals.size(); ++I) {
 806     GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
 807
 808     // Multiply by 2 to account for padding elements.
 809     Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
 810                                       ConstantInt::get(Int32Ty, I * 2)};
 811     Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
 812         NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
 813     assert(GV->getType()->getAddressSpace() == 0);
 814     GlobalAlias *GAlias =
 815         GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(),
 816                             "", CombinedGlobalElemPtr, &M);
 817     GAlias->setVisibility(GV->getVisibility());
 818     GAlias->takeName(GV);
 819     GV->replaceAllUsesWith(GAlias);
 820     GV->eraseFromParent();
 821   }
 822 }
 823
 824 bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
 825   return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
 826          ObjectFormat == Triple::ELF;
 827 }
 828
 829 /// Export the given type identifier so that ThinLTO backends may import it.
 830 /// Type identifiers are exported by adding coarse-grained information about how
 831 /// to test the type identifier to the summary, and creating symbols in the
 832 /// object file (aliases and absolute symbols) containing fine-grained
 833 /// information about the type identifier.
 834 ///
 835 /// Returns a pointer to the location in which to store the bitmask, if
 836 /// applicable.
 837 uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
 838                                             const TypeIdLowering &TIL) {
 839   TypeTestResolution &TTRes =
 840       ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
 841   TTRes.TheKind = TIL.TheKind;
 842
 843   auto ExportGlobal = [&](StringRef Name, Constant *C) {
 844     GlobalAlias *GA =
 845         GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
 846                             "__typeid_" + TypeId + "_" + Name, C, &M);
 847     GA->setVisibility(GlobalValue::HiddenVisibility);
 848   };
 849
 850   auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
 851     if (shouldExportConstantsAsAbsoluteSymbols())
 852       ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy));
 853     else
 854       Storage = cast<ConstantInt>(C)->getZExtValue();
 855   };
 856
 857   if (TIL.TheKind != TypeTestResolution::Unsat)
 858     ExportGlobal("global_addr", TIL.OffsetedGlobal);
 859
 860   if (TIL.TheKind == TypeTestResolution::ByteArray ||
 861       TIL.TheKind == TypeTestResolution::Inline ||
 862       TIL.TheKind == TypeTestResolution::AllOnes) {
 863     ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
 864     ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
 865
 866     uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
 867     if (TIL.TheKind == TypeTestResolution::Inline)
 868       TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
 869     else
 870       TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
 871   }
 872
 873   if (TIL.TheKind == TypeTestResolution::ByteArray) {
 874     ExportGlobal("byte_array", TIL.TheByteArray);
 875     if (shouldExportConstantsAsAbsoluteSymbols())
 876       ExportGlobal("bit_mask", TIL.BitMask);
 877     else
 878       return &TTRes.BitMask;
 879   }
 880
 881   if (TIL.TheKind == TypeTestResolution::Inline)
 882     ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
 883
 884   return nullptr;
 885 }
 886
 887 LowerTypeTestsModule::TypeIdLowering
 888 LowerTypeTestsModule::importTypeId(StringRef TypeId) {
 889   const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
 890   if (!TidSummary)
 891     return {}; // Unsat: no globals match this type id.
 892   const TypeTestResolution &TTRes = TidSummary->TTRes;
 893
 894   TypeIdLowering TIL;
 895   TIL.TheKind = TTRes.TheKind;
 896
 897   auto ImportGlobal = [&](StringRef Name) {
 898     // Give the global a type of length 0 so that it is not assumed not to alias
 899     // with any other global.
 900     Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(),
 901                                       Int8Arr0Ty);
 902     if (auto *GV = dyn_cast<GlobalVariable>(C))
 903       GV->setVisibility(GlobalValue::HiddenVisibility);
 904     C = ConstantExpr::getBitCast(C, Int8PtrTy);
 905     return C;
 906   };
 907
 908   auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
 909                             Type *Ty) {
 910     if (!shouldExportConstantsAsAbsoluteSymbols()) {
 911       Constant *C =
 912           ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const);
 913       if (!isa<IntegerType>(Ty))
 914         C = ConstantExpr::getIntToPtr(C, Ty);
 915       return C;
 916     }
 917
 918     Constant *C = ImportGlobal(Name);
 919     auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
 920     if (isa<IntegerType>(Ty))
 921       C = ConstantExpr::getPtrToInt(C, Ty);
 922     if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
 923       return C;
 924
 925     auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
 926       auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
 927       auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
 928       GV->setMetadata(LLVMContext::MD_absolute_symbol,
 929                       MDNode::get(M.getContext(), {MinC, MaxC}));
 930     };
 931     if (AbsWidth == IntPtrTy->getBitWidth())
 932       SetAbsRange(~0ull, ~0ull); // Full set.
 933     else
 934       SetAbsRange(0, 1ull << AbsWidth);
 935     return C;
 936   };
 937
 938   if (TIL.TheKind != TypeTestResolution::Unsat)
 939     TIL.OffsetedGlobal = ImportGlobal("global_addr");
 940
 941   if (TIL.TheKind == TypeTestResolution::ByteArray ||
 942       TIL.TheKind == TypeTestResolution::Inline ||
 943       TIL.TheKind == TypeTestResolution::AllOnes) {
 944     TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty);
 945     TIL.SizeM1 =
 946         ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
 947   }
 948
 949   if (TIL.TheKind == TypeTestResolution::ByteArray) {
 950     TIL.TheByteArray = ImportGlobal("byte_array");
 951     TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy);
 952   }
 953
 954   if (TIL.TheKind == TypeTestResolution::Inline)
 955     TIL.InlineBits = ImportConstant(
 956         "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
 957         TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
 958
 959   return TIL;
 960 }
 961
 962 void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
 963   auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
 964   if (!TypeIdMDVal)
 965     report_fatal_error("Second argument of llvm.type.test must be metadata");
 966
 967   auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
 968   if (!TypeIdStr)
 969     report_fatal_error(
 970         "Second argument of llvm.type.test must be a metadata string");
 971
 972   TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
 973   Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
 974   CI->replaceAllUsesWith(Lowered);
 975   CI->eraseFromParent();
 976 }
 977
 978 // ThinLTO backend: the function F has a jump table entry; update this module
 979 // accordingly. isDefinition describes the type of the jump table entry.
 980 void LowerTypeTestsModule::importFunction(Function *F, bool isDefinition) {
 981   assert(F->getType()->getAddressSpace() == 0);
 982
 983   GlobalValue::VisibilityTypes Visibility = F->getVisibility();
 984   std::string Name = F->getName();
 985
 986   if (F->isDeclarationForLinker() && isDefinition) {
 987     // Non-dso_local functions may be overriden at run time,
 988     // don't short curcuit them
 989     if (F->isDSOLocal()) {
 990       Function *RealF = Function::Create(F->getFunctionType(),
 991                                          GlobalValue::ExternalLinkage,
 992                                          F->getAddressSpace(),
 993                                          Name + ".cfi", &M);
 994       RealF->setVisibility(GlobalVariable::HiddenVisibility);
 995       replaceDirectCalls(F, RealF);
 996     }
 997     return;
 998   }
 999
1000   Function *FDecl;
1001   if (F->isDeclarationForLinker() && !isDefinition) {
1002     // Declaration of an external function.
1003     FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1004                              F->getAddressSpace(), Name + ".cfi_jt", &M);
1005     FDecl->setVisibility(GlobalValue::HiddenVisibility);
1006   } else if (isDefinition) {
1007     F->setName(Name + ".cfi");
1008     F->setLinkage(GlobalValue::ExternalLinkage);
1009     FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1010                              F->getAddressSpace(), Name, &M);
1011     FDecl->setVisibility(Visibility);
1012     Visibility = GlobalValue::HiddenVisibility;
1013
1014     // Delete aliases pointing to this function, they'll be re-created in the
1015     // merged output
1016     SmallVector<GlobalAlias*, 4> ToErase;
1017     for (auto &U : F->uses()) {
1018       if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
1019         Function *AliasDecl = Function::Create(
1020             F->getFunctionType(), GlobalValue::ExternalLinkage,
1021             F->getAddressSpace(), "", &M);
1022         AliasDecl->takeName(A);
1023         A->replaceAllUsesWith(AliasDecl);
1024         ToErase.push_back(A);
1025       }
1026     }
1027     for (auto *A : ToErase)
1028       A->eraseFromParent();
1029   } else {
1030     // Function definition without type metadata, where some other translation
1031     // unit contained a declaration with type metadata. This normally happens
1032     // during mixed CFI + non-CFI compilation. We do nothing with the function
1033     // so that it is treated the same way as a function defined outside of the
1034     // LTO unit.
1035     return;
1036   }
1037
1038   if (F->isWeakForLinker())
1039     replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isDefinition);
1040   else
1041     replaceCfiUses(F, FDecl, isDefinition);
1042
1043   // Set visibility late because it's used in replaceCfiUses() to determine
1044   // whether uses need to to be replaced.
1045   F->setVisibility(Visibility);
1046 }
1047
1048 void LowerTypeTestsModule::lowerTypeTestCalls(
1049     ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1050     const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1051   CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
1052
1053   // For each type identifier in this disjoint set...
1054   for (Metadata *TypeId : TypeIds) {
1055     // Build the bitset.
1056     BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
1057     LLVM_DEBUG({
1058       if (auto MDS = dyn_cast<MDString>(TypeId))
1059         dbgs() << MDS->getString() << ": ";
1060       else
1061         dbgs() << "<unnamed>: ";
1062       BSI.print(dbgs());
1063     });
1064
1065     ByteArrayInfo *BAI = nullptr;
1066     TypeIdLowering TIL;
1067     TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
1068         Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
1069     TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
1070     TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1);
1071     if (BSI.isAllOnes()) {
1072       TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1073                                        : TypeTestResolution::AllOnes;
1074     } else if (BSI.BitSize <= 64) {
1075       TIL.TheKind = TypeTestResolution::Inline;
1076       uint64_t InlineBits = 0;
1077       for (auto Bit : BSI.Bits)
1078         InlineBits |= uint64_t(1) << Bit;
1079       if (InlineBits == 0)
1080         TIL.TheKind = TypeTestResolution::Unsat;
1081       else
1082         TIL.InlineBits = ConstantInt::get(
1083             (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
1084     } else {
1085       TIL.TheKind = TypeTestResolution::ByteArray;
1086       ++NumByteArraysCreated;
1087       BAI = createByteArray(BSI);
1088       TIL.TheByteArray = BAI->ByteArray;
1089       TIL.BitMask = BAI->MaskGlobal;
1090     }
1091
1092     TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1093
1094     if (TIUI.IsExported) {
1095       uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
1096       if (BAI)
1097         BAI->MaskPtr = MaskPtr;
1098     }
1099
1100     // Lower each call to llvm.type.test for this type identifier.
1101     for (CallInst *CI : TIUI.CallSites) {
1102       ++NumTypeTestCallsLowered;
1103       Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1104       CI->replaceAllUsesWith(Lowered);
1105       CI->eraseFromParent();
1106     }
1107   }
1108 }
1109
1110 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1111   if (Type->getNumOperands() != 2)
1112     report_fatal_error("All operands of type metadata must have 2 elements");
1113
1114   if (GO->isThreadLocal())
1115     report_fatal_error("Bit set element may not be thread-local");
1116   if (isa<GlobalVariable>(GO) && GO->hasSection())
1117     report_fatal_error(
1118         "A member of a type identifier may not have an explicit section");
1119
1120   // FIXME: We previously checked that global var member of a type identifier
1121   // must be a definition, but the IR linker may leave type metadata on
1122   // declarations. We should restore this check after fixing PR31759.
1123
1124   auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
1125   if (!OffsetConstMD)
1126     report_fatal_error("Type offset must be a constant");
1127   auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
1128   if (!OffsetInt)
1129     report_fatal_error("Type offset must be an integer constant");
1130 }
1131
1132 static const unsigned kX86JumpTableEntrySize = 8;
1133 static const unsigned kARMJumpTableEntrySize = 4;
1134
1135 unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
1136   switch (Arch) {
1137     case Triple::x86:
1138     case Triple::x86_64:
1139       return kX86JumpTableEntrySize;
1140     case Triple::arm:
1141     case Triple::thumb:
1142     case Triple::aarch64:
1143       return kARMJumpTableEntrySize;
1144     default:
1145       report_fatal_error("Unsupported architecture for jump tables");
1146   }
1147 }
1148
1149 // Create a jump table entry for the target. This consists of an instruction
1150 // sequence containing a relative branch to Dest. Appends inline asm text,
1151 // constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
1152 void LowerTypeTestsModule::createJumpTableEntry(
1153     raw_ostream &AsmOS, raw_ostream &ConstraintOS,
1154     Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs,
1155     Function *Dest) {
1156   unsigned ArgIndex = AsmArgs.size();
1157
1158   if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1159     AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
1160     AsmOS << "int3\nint3\nint3\n";
1161   } else if (JumpTableArch == Triple::arm || JumpTableArch == Triple::aarch64) {
1162     AsmOS << "b $" << ArgIndex << "\n";
1163   } else if (JumpTableArch == Triple::thumb) {
1164     AsmOS << "b.w $" << ArgIndex << "\n";
1165   } else {
1166     report_fatal_error("Unsupported architecture for jump tables");
1167   }
1168
1169   ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
1170   AsmArgs.push_back(Dest);
1171 }
1172
1173 Type *LowerTypeTestsModule::getJumpTableEntryType() {
1174   return ArrayType::get(Int8Ty, getJumpTableEntrySize());
1175 }
1176
1177 /// Given a disjoint set of type identifiers and functions, build the bit sets
1178 /// and lower the llvm.type.test calls, architecture dependently.
1179 void LowerTypeTestsModule::buildBitSetsFromFunctions(
1180     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1181   if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1182       Arch == Triple::thumb || Arch == Triple::aarch64)
1183     buildBitSetsFromFunctionsNative(TypeIds, Functions);
1184   else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1185     buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1186   else
1187     report_fatal_error("Unsupported architecture for jump tables");
1188 }
1189
1190 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1191     GlobalVariable *GV) {
1192   if (WeakInitializerFn == nullptr) {
1193     WeakInitializerFn = Function::Create(
1194         FunctionType::get(Type::getVoidTy(M.getContext()),
1195                           /* IsVarArg */ false),
1196         GlobalValue::InternalLinkage,
1197         M.getDataLayout().getProgramAddressSpace(),
1198         "__cfi_global_var_init", &M);
1199     BasicBlock *BB =
1200         BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
1201     ReturnInst::Create(M.getContext(), BB);
1202     WeakInitializerFn->setSection(
1203         ObjectFormat == Triple::MachO
1204             ? "__TEXT,__StaticInit,regular,pure_instructions"
1205             : ".text.startup");
1206     // This code is equivalent to relocation application, and should run at the
1207     // earliest possible time (i.e. with the highest priority).
1208     appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
1209   }
1210
1211   IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1212   GV->setConstant(false);
1213   IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlignment());
1214   GV->setInitializer(Constant::getNullValue(GV->getValueType()));
1215 }
1216
1217 void LowerTypeTestsModule::findGlobalVariableUsersOf(
1218     Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
1219   for (auto *U : C->users()){
1220     if (auto *GV = dyn_cast<GlobalVariable>(U))
1221       Out.insert(GV);
1222     else if (auto *C2 = dyn_cast<Constant>(U))
1223       findGlobalVariableUsersOf(C2, Out);
1224   }
1225 }
1226
1227 // Replace all uses of F with (F ? JT : 0).
1228 void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1229     Function *F, Constant *JT, bool IsDefinition) {
1230   // The target expression can not appear in a constant initializer on most
1231   // (all?) targets. Switch to a runtime initializer.
1232   SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
1233   findGlobalVariableUsersOf(F, GlobalVarUsers);
1234   for (auto GV : GlobalVarUsers)
1235     moveInitializerToModuleConstructor(GV);
1236
1237   // Can not RAUW F with an expression that uses F. Replace with a temporary
1238   // placeholder first.
1239   Function *PlaceholderFn =
1240       Function::Create(cast<FunctionType>(F->getValueType()),
1241                        GlobalValue::ExternalWeakLinkage,
1242                        F->getAddressSpace(), "", &M);
1243   replaceCfiUses(F, PlaceholderFn, IsDefinition);
1244
1245   Constant *Target = ConstantExpr::getSelect(
1246       ConstantExpr::getICmp(CmpInst::ICMP_NE, F,
1247                             Constant::getNullValue(F->getType())),
1248       JT, Constant::getNullValue(F->getType()));
1249   PlaceholderFn->replaceAllUsesWith(Target);
1250   PlaceholderFn->eraseFromParent();
1251 }
1252
1253 static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1254   Attribute TFAttr = F->getFnAttribute("target-features");
1255   if (!TFAttr.hasAttribute(Attribute::None)) {
1256     SmallVector<StringRef, 6> Features;
1257     TFAttr.getValueAsString().split(Features, ',');
1258     for (StringRef Feature : Features) {
1259       if (Feature == "-thumb-mode")
1260         return false;
1261       else if (Feature == "+thumb-mode")
1262         return true;
1263     }
1264   }
1265
1266   return ModuleArch == Triple::thumb;
1267 }
1268
1269 // Each jump table must be either ARM or Thumb as a whole for the bit-test math
1270 // to work. Pick one that matches the majority of members to minimize interop
1271 // veneers inserted by the linker.
1272 static Triple::ArchType
1273 selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions,
1274                            Triple::ArchType ModuleArch) {
1275   if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb)
1276     return ModuleArch;
1277
1278   unsigned ArmCount = 0, ThumbCount = 0;
1279   for (const auto GTM : Functions) {
1280     if (!GTM->isDefinition()) {
1281       // PLT stubs are always ARM.
1282       ++ArmCount;
1283       continue;
1284     }
1285
1286     Function *F = cast<Function>(GTM->getGlobal());
1287     ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount);
1288   }
1289
1290   return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1291 }
1292
1293 void LowerTypeTestsModule::createJumpTable(
1294     Function *F, ArrayRef<GlobalTypeMember *> Functions) {
1295   std::string AsmStr, ConstraintStr;
1296   raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
1297   SmallVector<Value *, 16> AsmArgs;
1298   AsmArgs.reserve(Functions.size() * 2);
1299
1300   Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch);
1301
1302   for (unsigned I = 0; I != Functions.size(); ++I)
1303     createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
1304                          cast<Function>(Functions[I]->getGlobal()));
1305
1306   // Align the whole table by entry size.
1307   F->setAlignment(getJumpTableEntrySize());
1308   // Skip prologue.
1309   // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
1310   // Luckily, this function does not get any prologue even without the
1311   // attribute.
1312   if (OS != Triple::Win32)
1313     F->addFnAttr(Attribute::Naked);
1314   if (JumpTableArch == Triple::arm)
1315     F->addFnAttr("target-features", "-thumb-mode");
1316   if (JumpTableArch == Triple::thumb) {
1317     F->addFnAttr("target-features", "+thumb-mode");
1318     // Thumb jump table assembly needs Thumb2. The following attribute is added
1319     // by Clang for -march=armv7.
1320     F->addFnAttr("target-cpu", "cortex-a8");
1321   }
1322   // Make sure we don't emit .eh_frame for this function.
1323   F->addFnAttr(Attribute::NoUnwind);
1324
1325   BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
1326   IRBuilder<> IRB(BB);
1327
1328   SmallVector<Type *, 16> ArgTypes;
1329   ArgTypes.reserve(AsmArgs.size());
1330   for (const auto &Arg : AsmArgs)
1331     ArgTypes.push_back(Arg->getType());
1332   InlineAsm *JumpTableAsm =
1333       InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
1334                      AsmOS.str(), ConstraintOS.str(),
1335                      /*hasSideEffects=*/true);
1336
1337   IRB.CreateCall(JumpTableAsm, AsmArgs);
1338   IRB.CreateUnreachable();
1339 }
1340
1341 /// Given a disjoint set of type identifiers and functions, build a jump table
1342 /// for the functions, build the bit sets and lower the llvm.type.test calls.
1343 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1344     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1345   // Unlike the global bitset builder, the function bitset builder cannot
1346   // re-arrange functions in a particular order and base its calculations on the
1347   // layout of the functions' entry points, as we have no idea how large a
1348   // particular function will end up being (the size could even depend on what
1349   // this pass does!) Instead, we build a jump table, which is a block of code
1350   // consisting of one branch instruction for each of the functions in the bit
1351   // set that branches to the target function, and redirect any taken function
1352   // addresses to the corresponding jump table entry. In the object file's
1353   // symbol table, the symbols for the target functions also refer to the jump
1354   // table entries, so that addresses taken outside the module will pass any
1355   // verification done inside the module.
1356   //
1357   // In more concrete terms, suppose we have three functions f, g, h which are
1358   // of the same type, and a function foo that returns their addresses:
1359   //
1360   // f:
1361   // mov 0, %eax
1362   // ret
1363   //
1364   // g:
1365   // mov 1, %eax
1366   // ret
1367   //
1368   // h:
1369   // mov 2, %eax
1370   // ret
1371   //
1372   // foo:
1373   // mov f, %eax
1374   // mov g, %edx
1375   // mov h, %ecx
1376   // ret
1377   //
1378   // We output the jump table as module-level inline asm string. The end result
1379   // will (conceptually) look like this:
1380   //
1381   // f = .cfi.jumptable
1382   // g = .cfi.jumptable + 4
1383   // h = .cfi.jumptable + 8
1384   // .cfi.jumptable:
1385   // jmp f.cfi  ; 5 bytes
1386   // int3       ; 1 byte
1387   // int3       ; 1 byte
1388   // int3       ; 1 byte
1389   // jmp g.cfi  ; 5 bytes
1390   // int3       ; 1 byte
1391   // int3       ; 1 byte
1392   // int3       ; 1 byte
1393   // jmp h.cfi  ; 5 bytes
1394   // int3       ; 1 byte
1395   // int3       ; 1 byte
1396   // int3       ; 1 byte
1397   //
1398   // f.cfi:
1399   // mov 0, %eax
1400   // ret
1401   //
1402   // g.cfi:
1403   // mov 1, %eax
1404   // ret
1405   //
1406   // h.cfi:
1407   // mov 2, %eax
1408   // ret
1409   //
1410   // foo:
1411   // mov f, %eax
1412   // mov g, %edx
1413   // mov h, %ecx
1414   // ret
1415   //
1416   // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1417   // normal case the check can be carried out using the same kind of simple
1418   // arithmetic that we normally use for globals.
1419
1420   // FIXME: find a better way to represent the jumptable in the IR.
1421   assert(!Functions.empty());
1422
1423   // Build a simple layout based on the regular layout of jump tables.
1424   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1425   unsigned EntrySize = getJumpTableEntrySize();
1426   for (unsigned I = 0; I != Functions.size(); ++I)
1427     GlobalLayout[Functions[I]] = I * EntrySize;
1428
1429   Function *JumpTableFn =
1430       Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()),
1431                                          /* IsVarArg */ false),
1432                        GlobalValue::PrivateLinkage,
1433                        M.getDataLayout().getProgramAddressSpace(),
1434                        ".cfi.jumptable", &M);
1435   ArrayType *JumpTableType =
1436       ArrayType::get(getJumpTableEntryType(), Functions.size());
1437   auto JumpTable =
1438       ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
1439
1440   lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
1441
1442   // Build aliases pointing to offsets into the jump table, and replace
1443   // references to the original functions with references to the aliases.
1444   for (unsigned I = 0; I != Functions.size(); ++I) {
1445     Function *F = cast<Function>(Functions[I]->getGlobal());
1446     bool IsDefinition = Functions[I]->isDefinition();
1447
1448     Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
1449         ConstantExpr::getInBoundsGetElementPtr(
1450             JumpTableType, JumpTable,
1451             ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0),
1452                                  ConstantInt::get(IntPtrTy, I)}),
1453         F->getType());
1454     if (Functions[I]->isExported()) {
1455       if (IsDefinition) {
1456         ExportSummary->cfiFunctionDefs().insert(F->getName());
1457       } else {
1458         GlobalAlias *JtAlias = GlobalAlias::create(
1459             F->getValueType(), 0, GlobalValue::ExternalLinkage,
1460             F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M);
1461         JtAlias->setVisibility(GlobalValue::HiddenVisibility);
1462         ExportSummary->cfiFunctionDecls().insert(F->getName());
1463       }
1464     }
1465     if (!IsDefinition) {
1466       if (F->isWeakForLinker())
1467         replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr, IsDefinition);
1468       else
1469         replaceCfiUses(F, CombinedGlobalElemPtr, IsDefinition);
1470     } else {
1471       assert(F->getType()->getAddressSpace() == 0);
1472
1473       GlobalAlias *FAlias = GlobalAlias::create(
1474           F->getValueType(), 0, F->getLinkage(), "", CombinedGlobalElemPtr, &M);
1475       FAlias->setVisibility(F->getVisibility());
1476       FAlias->takeName(F);
1477       if (FAlias->hasName())
1478         F->setName(FAlias->getName() + ".cfi");
1479       replaceCfiUses(F, FAlias, IsDefinition);
1480       if (!F->hasLocalLinkage())
1481         F->setVisibility(GlobalVariable::HiddenVisibility);
1482     }
1483   }
1484
1485   createJumpTable(JumpTableFn, Functions);
1486 }
1487
1488 /// Assign a dummy layout using an incrementing counter, tag each function
1489 /// with its index represented as metadata, and lower each type test to an
1490 /// integer range comparison. During generation of the indirect function call
1491 /// table in the backend, it will assign the given indexes.
1492 /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1493 /// been finalized.
1494 void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1495     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1496   assert(!Functions.empty());
1497
1498   // Build consecutive monotonic integer ranges for each call target set
1499   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1500
1501   for (GlobalTypeMember *GTM : Functions) {
1502     Function *F = cast<Function>(GTM->getGlobal());
1503
1504     // Skip functions that are not address taken, to avoid bloating the table
1505     if (!F->hasAddressTaken())
1506       continue;
1507
1508     // Store metadata with the index for each function
1509     MDNode *MD = MDNode::get(F->getContext(),
1510                              ArrayRef<Metadata *>(ConstantAsMetadata::get(
1511                                  ConstantInt::get(Int64Ty, IndirectIndex))));
1512     F->setMetadata("wasm.index", MD);
1513
1514     // Assign the counter value
1515     GlobalLayout[GTM] = IndirectIndex++;
1516   }
1517
1518   // The indirect function table index space starts at zero, so pass a NULL
1519   // pointer as the subtracted "jump table" offset.
1520   lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
1521                      GlobalLayout);
1522 }
1523
1524 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1525     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
1526     ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
1527   DenseMap<Metadata *, uint64_t> TypeIdIndices;
1528   for (unsigned I = 0; I != TypeIds.size(); ++I)
1529     TypeIdIndices[TypeIds[I]] = I;
1530
1531   // For each type identifier, build a set of indices that refer to members of
1532   // the type identifier.
1533   std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1534   unsigned GlobalIndex = 0;
1535   DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
1536   for (GlobalTypeMember *GTM : Globals) {
1537     for (MDNode *Type : GTM->types()) {
1538       // Type = { offset, type identifier }
1539       auto I = TypeIdIndices.find(Type->getOperand(1));
1540       if (I != TypeIdIndices.end())
1541         TypeMembers[I->second].insert(GlobalIndex);
1542     }
1543     GlobalIndices[GTM] = GlobalIndex;
1544     GlobalIndex++;
1545   }
1546
1547   for (ICallBranchFunnel *JT : ICallBranchFunnels) {
1548     TypeMembers.emplace_back();
1549     std::set<uint64_t> &TMSet = TypeMembers.back();
1550     for (GlobalTypeMember *T : JT->targets())
1551       TMSet.insert(GlobalIndices[T]);
1552   }
1553
1554   // Order the sets of indices by size. The GlobalLayoutBuilder works best
1555   // when given small index sets first.
1556   std::stable_sort(
1557       TypeMembers.begin(), TypeMembers.end(),
1558       [](const std::set<uint64_t> &O1, const std::set<uint64_t> &O2) {
1559         return O1.size() < O2.size();
1560       });
1561
1562   // Create a GlobalLayoutBuilder and provide it with index sets as layout
1563   // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1564   // close together as possible.
1565   GlobalLayoutBuilder GLB(Globals.size());
1566   for (auto &&MemSet : TypeMembers)
1567     GLB.addFragment(MemSet);
1568
1569   // Build a vector of globals with the computed layout.
1570   bool IsGlobalSet =
1571       Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
1572   std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1573   auto OGTMI = OrderedGTMs.begin();
1574   for (auto &&F : GLB.Fragments) {
1575     for (auto &&Offset : F) {
1576       if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
1577         report_fatal_error("Type identifier may not contain both global "
1578                            "variables and functions");
1579       *OGTMI++ = Globals[Offset];
1580     }
1581   }
1582
1583   // Build the bitsets from this disjoint set.
1584   if (IsGlobalSet)
1585     buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
1586   else
1587     buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
1588 }
1589
1590 /// Lower all type tests in this module.
1591 LowerTypeTestsModule::LowerTypeTestsModule(
1592     Module &M, ModuleSummaryIndex *ExportSummary,
1593     const ModuleSummaryIndex *ImportSummary)
1594     : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
1595   assert(!(ExportSummary && ImportSummary));
1596   Triple TargetTriple(M.getTargetTriple());
1597   Arch = TargetTriple.getArch();
1598   OS = TargetTriple.getOS();
1599   ObjectFormat = TargetTriple.getObjectFormat();
1600 }
1601
1602 bool LowerTypeTestsModule::runForTesting(Module &M) {
1603   ModuleSummaryIndex Summary(/*HaveGVs=*/false);
1604
1605   // Handle the command-line summary arguments. This code is for testing
1606   // purposes only, so we handle errors directly.
1607   if (!ClReadSummary.empty()) {
1608     ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1609                           ": ");
1610     auto ReadSummaryFile =
1611         ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
1612
1613     yaml::Input In(ReadSummaryFile->getBuffer());
1614     In >> Summary;
1615     ExitOnErr(errorCodeToError(In.error()));
1616   }
1617
1618   bool Changed =
1619       LowerTypeTestsModule(
1620           M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
1621           ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
1622           .lower();
1623
1624   if (!ClWriteSummary.empty()) {
1625     ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
1626                           ": ");
1627     std::error_code EC;
1628     raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text);
1629     ExitOnErr(errorCodeToError(EC));
1630
1631     yaml::Output Out(OS);
1632     Out << Summary;
1633   }
1634
1635   return Changed;
1636 }
1637
1638 static bool isDirectCall(Use& U) {
1639   auto *Usr = dyn_cast<CallInst>(U.getUser());
1640   if (Usr) {
1641     CallSite CS(Usr);
1642     if (CS.isCallee(&U))
1643       return true;
1644   }
1645   return false;
1646 }
1647
1648 void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New, bool IsDefinition) {
1649   SmallSetVector<Constant *, 4> Constants;
1650   auto UI = Old->use_begin(), E = Old->use_end();
1651   for (; UI != E;) {
1652     Use &U = *UI;
1653     ++UI;
1654
1655     // Skip block addresses
1656     if (isa<BlockAddress>(U.getUser()))
1657       continue;
1658
1659     // Skip direct calls to externally defined or non-dso_local functions
1660     if (isDirectCall(U) && (Old->isDSOLocal() || !IsDefinition))
1661       continue;
1662
1663     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
1664     // constant because they are uniqued.
1665     if (auto *C = dyn_cast<Constant>(U.getUser())) {
1666       if (!isa<GlobalValue>(C)) {
1667         // Save unique users to avoid processing operand replacement
1668         // more than once.
1669         Constants.insert(C);
1670         continue;
1671       }
1672     }
1673
1674     U.set(New);
1675   }
1676
1677   // Process operand replacement of saved constants.
1678   for (auto *C : Constants)
1679     C->handleOperandChange(Old, New);
1680 }
1681
1682 void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
1683   auto UI = Old->use_begin(), E = Old->use_end();
1684   for (; UI != E;) {
1685     Use &U = *UI;
1686     ++UI;
1687
1688     if (!isDirectCall(U))
1689       continue;
1690
1691     U.set(New);
1692   }
1693 }
1694
1695 bool LowerTypeTestsModule::lower() {
1696   Function *TypeTestFunc =
1697       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1698   Function *ICallBranchFunnelFunc =
1699       M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel));
1700   if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
1701       (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
1702       !ExportSummary && !ImportSummary)
1703     return false;
1704
1705   // If only some of the modules were split, we cannot correctly handle
1706   // code that contains type tests.
1707   if (TypeTestFunc && !TypeTestFunc->use_empty() &&
1708       ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1709        (ImportSummary && ImportSummary->partiallySplitLTOUnits())))
1710     report_fatal_error("inconsistent LTO Unit splitting with llvm.type.test");
1711
1712   if (ImportSummary) {
1713     if (TypeTestFunc) {
1714       for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
1715            UI != UE;) {
1716         auto *CI = cast<CallInst>((*UI++).getUser());
1717         importTypeTest(CI);
1718       }
1719     }
1720
1721     if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
1722       report_fatal_error(
1723           "unexpected call to llvm.icall.branch.funnel during import phase");
1724
1725     SmallVector<Function *, 8> Defs;
1726     SmallVector<Function *, 8> Decls;
1727     for (auto &F : M) {
1728       // CFI functions are either external, or promoted. A local function may
1729       // have the same name, but it's not the one we are looking for.
1730       if (F.hasLocalLinkage())
1731         continue;
1732       if (ImportSummary->cfiFunctionDefs().count(F.getName()))
1733         Defs.push_back(&F);
1734       else if (ImportSummary->cfiFunctionDecls().count(F.getName()))
1735         Decls.push_back(&F);
1736     }
1737
1738     for (auto F : Defs)
1739       importFunction(F, /*isDefinition*/ true);
1740     for (auto F : Decls)
1741       importFunction(F, /*isDefinition*/ false);
1742
1743     return true;
1744   }
1745
1746   // Equivalence class set containing type identifiers and the globals that
1747   // reference them. This is used to partition the set of type identifiers in
1748   // the module into disjoint sets.
1749   using GlobalClassesTy = EquivalenceClasses<
1750       PointerUnion3<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>;
1751   GlobalClassesTy GlobalClasses;
1752
1753   // Verify the type metadata and build a few data structures to let us
1754   // efficiently enumerate the type identifiers associated with a global:
1755   // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
1756   // of associated type metadata) and a mapping from type identifiers to their
1757   // list of GlobalTypeMembers and last observed index in the list of globals.
1758   // The indices will be used later to deterministically order the list of type
1759   // identifiers.
1760   BumpPtrAllocator Alloc;
1761   struct TIInfo {
1762     unsigned UniqueId;
1763     std::vector<GlobalTypeMember *> RefGlobals;
1764   };
1765   DenseMap<Metadata *, TIInfo> TypeIdInfo;
1766   unsigned CurUniqueId = 0;
1767   SmallVector<MDNode *, 2> Types;
1768
1769   // Cross-DSO CFI emits jumptable entries for exported functions as well as
1770   // address taken functions in case they are address taken in other modules.
1771   const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr;
1772
1773   struct ExportedFunctionInfo {
1774     CfiFunctionLinkage Linkage;
1775     MDNode *FuncMD; // {name, linkage, type[, type...]}
1776   };
1777   DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions;
1778   if (ExportSummary) {
1779     // A set of all functions that are address taken by a live global object.
1780     DenseSet<GlobalValue::GUID> AddressTaken;
1781     for (auto &I : *ExportSummary)
1782       for (auto &GVS : I.second.SummaryList)
1783         if (GVS->isLive())
1784           for (auto &Ref : GVS->refs())
1785             AddressTaken.insert(Ref.getGUID());
1786
1787     NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions");
1788     if (CfiFunctionsMD) {
1789       for (auto FuncMD : CfiFunctionsMD->operands()) {
1790         assert(FuncMD->getNumOperands() >= 2);
1791         StringRef FunctionName =
1792             cast<MDString>(FuncMD->getOperand(0))->getString();
1793         CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>(
1794             cast<ConstantAsMetadata>(FuncMD->getOperand(1))
1795                 ->getValue()
1796                 ->getUniqueInteger()
1797                 .getZExtValue());
1798         const GlobalValue::GUID GUID = GlobalValue::getGUID(
1799                 GlobalValue::dropLLVMManglingEscape(FunctionName));
1800         // Do not emit jumptable entries for functions that are not-live and
1801         // have no live references (and are not exported with cross-DSO CFI.)
1802         if (!ExportSummary->isGUIDLive(GUID))
1803           continue;
1804         if (!AddressTaken.count(GUID)) {
1805           if (!CrossDsoCfi || Linkage != CFL_Definition)
1806             continue;
1807
1808           bool Exported = false;
1809           if (auto VI = ExportSummary->getValueInfo(GUID))
1810             for (auto &GVS : VI.getSummaryList())
1811               if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
1812                 Exported = true;
1813
1814           if (!Exported)
1815             continue;
1816         }
1817         auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}});
1818         if (!P.second && P.first->second.Linkage != CFL_Definition)
1819           P.first->second = {Linkage, FuncMD};
1820       }
1821
1822       for (const auto &P : ExportedFunctions) {
1823         StringRef FunctionName = P.first;
1824         CfiFunctionLinkage Linkage = P.second.Linkage;
1825         MDNode *FuncMD = P.second.FuncMD;
1826         Function *F = M.getFunction(FunctionName);
1827         if (!F)
1828           F = Function::Create(
1829               FunctionType::get(Type::getVoidTy(M.getContext()), false),
1830               GlobalVariable::ExternalLinkage,
1831               M.getDataLayout().getProgramAddressSpace(), FunctionName, &M);
1832
1833         // If the function is available_externally, remove its definition so
1834         // that it is handled the same way as a declaration. Later we will try
1835         // to create an alias using this function's linkage, which will fail if
1836         // the linkage is available_externally. This will also result in us
1837         // following the code path below to replace the type metadata.
1838         if (F->hasAvailableExternallyLinkage()) {
1839           F->setLinkage(GlobalValue::ExternalLinkage);
1840           F->deleteBody();
1841           F->setComdat(nullptr);
1842           F->clearMetadata();
1843         }
1844
1845         // Update the linkage for extern_weak declarations when a definition
1846         // exists.
1847         if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
1848           F->setLinkage(GlobalValue::ExternalLinkage);
1849
1850         // If the function in the full LTO module is a declaration, replace its
1851         // type metadata with the type metadata we found in cfi.functions. That
1852         // metadata is presumed to be more accurate than the metadata attached
1853         // to the declaration.
1854         if (F->isDeclaration()) {
1855           if (Linkage == CFL_WeakDeclaration)
1856             F->setLinkage(GlobalValue::ExternalWeakLinkage);
1857
1858           F->eraseMetadata(LLVMContext::MD_type);
1859           for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
1860             F->addMetadata(LLVMContext::MD_type,
1861                            *cast<MDNode>(FuncMD->getOperand(I).get()));
1862         }
1863       }
1864     }
1865   }
1866
1867   DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
1868   for (GlobalObject &GO : M.global_objects()) {
1869     if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
1870       continue;
1871
1872     Types.clear();
1873     GO.getMetadata(LLVMContext::MD_type, Types);
1874
1875     bool IsDefinition = !GO.isDeclarationForLinker();
1876     bool IsExported = false;
1877     if (Function *F = dyn_cast<Function>(&GO)) {
1878       if (ExportedFunctions.count(F->getName())) {
1879         IsDefinition |= ExportedFunctions[F->getName()].Linkage == CFL_Definition;
1880         IsExported = true;
1881       // TODO: The logic here checks only that the function is address taken,
1882       // not that the address takers are live. This can be updated to check
1883       // their liveness and emit fewer jumptable entries once monolithic LTO
1884       // builds also emit summaries.
1885       } else if (!F->hasAddressTaken()) {
1886         if (!CrossDsoCfi || !IsDefinition || F->hasLocalLinkage())
1887           continue;
1888       }
1889     }
1890
1891     auto *GTM =
1892         GlobalTypeMember::create(Alloc, &GO, IsDefinition, IsExported, Types);
1893     GlobalTypeMembers[&GO] = GTM;
1894     for (MDNode *Type : Types) {
1895       verifyTypeMDNode(&GO, Type);
1896       auto &Info = TypeIdInfo[Type->getOperand(1)];
1897       Info.UniqueId = ++CurUniqueId;
1898       Info.RefGlobals.push_back(GTM);
1899     }
1900   }
1901
1902   auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
1903     // Add the call site to the list of call sites for this type identifier. We
1904     // also use TypeIdUsers to keep track of whether we have seen this type
1905     // identifier before. If we have, we don't need to re-add the referenced
1906     // globals to the equivalence class.
1907     auto Ins = TypeIdUsers.insert({TypeId, {}});
1908     if (Ins.second) {
1909       // Add the type identifier to the equivalence class.
1910       GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
1911       GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
1912
1913       // Add the referenced globals to the type identifier's equivalence class.
1914       for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
1915         CurSet = GlobalClasses.unionSets(
1916             CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
1917     }
1918
1919     return Ins.first->second;
1920   };
1921
1922   if (TypeTestFunc) {
1923     for (const Use &U : TypeTestFunc->uses()) {
1924       auto CI = cast<CallInst>(U.getUser());
1925
1926       auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
1927       if (!TypeIdMDVal)
1928         report_fatal_error("Second argument of llvm.type.test must be metadata");
1929       auto TypeId = TypeIdMDVal->getMetadata();
1930       AddTypeIdUse(TypeId).CallSites.push_back(CI);
1931     }
1932   }
1933
1934   if (ICallBranchFunnelFunc) {
1935     for (const Use &U : ICallBranchFunnelFunc->uses()) {
1936       if (Arch != Triple::x86_64)
1937         report_fatal_error(
1938             "llvm.icall.branch.funnel not supported on this target");
1939
1940       auto CI = cast<CallInst>(U.getUser());
1941
1942       std::vector<GlobalTypeMember *> Targets;
1943       if (CI->getNumArgOperands() % 2 != 1)
1944         report_fatal_error("number of arguments should be odd");
1945
1946       GlobalClassesTy::member_iterator CurSet;
1947       for (unsigned I = 1; I != CI->getNumArgOperands(); I += 2) {
1948         int64_t Offset;
1949         auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
1950             CI->getOperand(I), Offset, M.getDataLayout()));
1951         if (!Base)
1952           report_fatal_error(
1953               "Expected branch funnel operand to be global value");
1954
1955         GlobalTypeMember *GTM = GlobalTypeMembers[Base];
1956         Targets.push_back(GTM);
1957         GlobalClassesTy::member_iterator NewSet =
1958             GlobalClasses.findLeader(GlobalClasses.insert(GTM));
1959         if (I == 1)
1960           CurSet = NewSet;
1961         else
1962           CurSet = GlobalClasses.unionSets(CurSet, NewSet);
1963       }
1964
1965       GlobalClasses.unionSets(
1966           CurSet, GlobalClasses.findLeader(
1967                       GlobalClasses.insert(ICallBranchFunnel::create(
1968                           Alloc, CI, Targets, ++CurUniqueId))));
1969     }
1970   }
1971
1972   if (ExportSummary) {
1973     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
1974     for (auto &P : TypeIdInfo) {
1975       if (auto *TypeId = dyn_cast<MDString>(P.first))
1976         MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
1977             TypeId);
1978     }
1979
1980     for (auto &P : *ExportSummary) {
1981       for (auto &S : P.second.SummaryList) {
1982         if (!ExportSummary->isGlobalValueLive(S.get()))
1983           continue;
1984         if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject()))
1985           for (GlobalValue::GUID G : FS->type_tests())
1986             for (Metadata *MD : MetadataByGUID[G])
1987               AddTypeIdUse(MD).IsExported = true;
1988       }
1989     }
1990   }
1991
1992   if (GlobalClasses.empty())
1993     return false;
1994
1995   // Build a list of disjoint sets ordered by their maximum global index for
1996   // determinism.
1997   std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
1998   for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
1999                                  E = GlobalClasses.end();
2000        I != E; ++I) {
2001     if (!I->isLeader())
2002       continue;
2003     ++NumTypeIdDisjointSets;
2004
2005     unsigned MaxUniqueId = 0;
2006     for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
2007          MI != GlobalClasses.member_end(); ++MI) {
2008       if (auto *MD = MI->dyn_cast<Metadata *>())
2009         MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
2010       else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
2011         MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
2012     }
2013     Sets.emplace_back(I, MaxUniqueId);
2014   }
2015   llvm::sort(Sets,
2016              [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
2017                 const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
2018                return S1.second < S2.second;
2019              });
2020
2021   // For each disjoint set we found...
2022   for (const auto &S : Sets) {
2023     // Build the list of type identifiers in this disjoint set.
2024     std::vector<Metadata *> TypeIds;
2025     std::vector<GlobalTypeMember *> Globals;
2026     std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2027     for (GlobalClassesTy::member_iterator MI =
2028              GlobalClasses.member_begin(S.first);
2029          MI != GlobalClasses.member_end(); ++MI) {
2030       if (MI->is<Metadata *>())
2031         TypeIds.push_back(MI->get<Metadata *>());
2032       else if (MI->is<GlobalTypeMember *>())
2033         Globals.push_back(MI->get<GlobalTypeMember *>());
2034       else
2035         ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
2036     }
2037
2038     // Order type identifiers by unique ID for determinism. This ordering is
2039     // stable as there is a one-to-one mapping between metadata and unique IDs.
2040     llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) {
2041       return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2042     });
2043
2044     // Same for the branch funnels.
2045     llvm::sort(ICallBranchFunnels,
2046                [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2047                  return F1->UniqueId < F2->UniqueId;
2048                });
2049
2050     // Build bitsets for this disjoint set.
2051     buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2052   }
2053
2054   allocateByteArrays();
2055
2056   // Parse alias data to replace stand-in function declarations for aliases
2057   // with an alias to the intended target.
2058   if (ExportSummary) {
2059     if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {
2060       for (auto AliasMD : AliasesMD->operands()) {
2061         assert(AliasMD->getNumOperands() >= 4);
2062         StringRef AliasName =
2063             cast<MDString>(AliasMD->getOperand(0))->getString();
2064         StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
2065
2066         if (!ExportedFunctions.count(Aliasee) ||
2067             ExportedFunctions[Aliasee].Linkage != CFL_Definition ||
2068             !M.getNamedAlias(Aliasee))
2069           continue;
2070
2071         GlobalValue::VisibilityTypes Visibility =
2072             static_cast<GlobalValue::VisibilityTypes>(
2073                 cast<ConstantAsMetadata>(AliasMD->getOperand(2))
2074                     ->getValue()
2075                     ->getUniqueInteger()
2076                     .getZExtValue());
2077         bool Weak =
2078             static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
2079                                   ->getValue()
2080                                   ->getUniqueInteger()
2081                                   .getZExtValue());
2082
2083         auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee));
2084         Alias->setVisibility(Visibility);
2085         if (Weak)
2086           Alias->setLinkage(GlobalValue::WeakAnyLinkage);
2087
2088         if (auto *F = M.getFunction(AliasName)) {
2089           Alias->takeName(F);
2090           F->replaceAllUsesWith(Alias);
2091           F->eraseFromParent();
2092         } else {
2093           Alias->setName(AliasName);
2094         }
2095       }
2096     }
2097   }
2098
2099   // Emit .symver directives for exported functions, if they exist.
2100   if (ExportSummary) {
2101     if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) {
2102       for (auto Symver : SymversMD->operands()) {
2103         assert(Symver->getNumOperands() >= 2);
2104         StringRef SymbolName =
2105             cast<MDString>(Symver->getOperand(0))->getString();
2106         StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
2107
2108         if (!ExportedFunctions.count(SymbolName))
2109           continue;
2110
2111         M.appendModuleInlineAsm(
2112             (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2113       }
2114     }
2115   }
2116
2117   return true;
2118 }
2119
2120 PreservedAnalyses LowerTypeTestsPass::run(Module &M,
2121                                           ModuleAnalysisManager &AM) {
2122   bool Changed = LowerTypeTestsModule(M, ExportSummary, ImportSummary).lower();
2123   if (!Changed)
2124     return PreservedAnalyses::all();
2125   return PreservedAnalyses::none();
2126 }