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