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/EquivalenceClasses.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/ADT/Triple.h"
  20 #include "llvm/IR/Constant.h"
  21 #include "llvm/IR/Constants.h"
  22 #include "llvm/IR/Function.h"
  23 #include "llvm/IR/GlobalObject.h"
  24 #include "llvm/IR/GlobalVariable.h"
  25 #include "llvm/IR/IRBuilder.h"
  26 #include "llvm/IR/InlineAsm.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/Intrinsics.h"
  29 #include "llvm/IR/Module.h"
  30 #include "llvm/IR/ModuleSummaryIndexYAML.h"
  31 #include "llvm/IR/Operator.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/Error.h"
  35 #include "llvm/Support/FileSystem.h"
  36 #include "llvm/Support/TrailingObjects.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include "llvm/Transforms/IPO.h"
  39 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  40 #include "llvm/Transforms/Utils/ModuleUtils.h"
  41
  42 using namespace llvm;
  43 using namespace lowertypetests;
  44
  45 using SummaryAction = LowerTypeTestsSummaryAction;
  46
  47 #define DEBUG_TYPE "lowertypetests"
  48
  49 STATISTIC(ByteArraySizeBits, "Byte array size in bits");
  50 STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
  51 STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
  52 STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
  53 STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
  54
  55 static cl::opt<bool> AvoidReuse(
  56     "lowertypetests-avoid-reuse",
  57     cl::desc("Try to avoid reuse of byte array addresses using aliases"),
  58     cl::Hidden, cl::init(true));
  59
  60 static cl::opt<SummaryAction> ClSummaryAction(
  61     "lowertypetests-summary-action",
  62     cl::desc("What to do with the summary when running this pass"),
  63     cl::values(clEnumValN(SummaryAction::None, "none", "Do nothing"),
  64                clEnumValN(SummaryAction::Import, "import",
  65                           "Import typeid resolutions from summary and globals"),
  66                clEnumValN(SummaryAction::Export, "export",
  67                           "Export typeid resolutions to summary and globals")),
  68     cl::Hidden);
  69
  70 static cl::opt<std::string> ClReadSummary(
  71     "lowertypetests-read-summary",
  72     cl::desc("Read summary from given YAML file before running pass"),
  73     cl::Hidden);
  74
  75 static cl::opt<std::string> ClWriteSummary(
  76     "lowertypetests-write-summary",
  77     cl::desc("Write summary to given YAML file after running pass"),
  78     cl::Hidden);
  79
  80 bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
  81   if (Offset < ByteOffset)
  82     return false;
  83
  84   if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
  85     return false;
  86
  87   uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
  88   if (BitOffset >= BitSize)
  89     return false;
  90
  91   return Bits.count(BitOffset);
  92 }
  93
  94 void BitSetInfo::print(raw_ostream &OS) const {
  95   OS << "offset " << ByteOffset << " size " << BitSize << " align "
  96      << (1 << AlignLog2);
  97
  98   if (isAllOnes()) {
  99     OS << " all-ones\n";
 100     return;
 101   }
 102
 103   OS << " { ";
 104   for (uint64_t B : Bits)
 105     OS << B << ' ';
 106   OS << "}\n";
 107 }
 108
 109 BitSetInfo BitSetBuilder::build() {
 110   if (Min > Max)
 111     Min = 0;
 112
 113   // Normalize each offset against the minimum observed offset, and compute
 114   // the bitwise OR of each of the offsets. The number of trailing zeros
 115   // in the mask gives us the log2 of the alignment of all offsets, which
 116   // allows us to compress the bitset by only storing one bit per aligned
 117   // address.
 118   uint64_t Mask = 0;
 119   for (uint64_t &Offset : Offsets) {
 120     Offset -= Min;
 121     Mask |= Offset;
 122   }
 123
 124   BitSetInfo BSI;
 125   BSI.ByteOffset = Min;
 126
 127   BSI.AlignLog2 = 0;
 128   if (Mask != 0)
 129     BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined);
 130
 131   // Build the compressed bitset while normalizing the offsets against the
 132   // computed alignment.
 133   BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
 134   for (uint64_t Offset : Offsets) {
 135     Offset >>= BSI.AlignLog2;
 136     BSI.Bits.insert(Offset);
 137   }
 138
 139   return BSI;
 140 }
 141
 142 void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
 143   // Create a new fragment to hold the layout for F.
 144   Fragments.emplace_back();
 145   std::vector<uint64_t> &Fragment = Fragments.back();
 146   uint64_t FragmentIndex = Fragments.size() - 1;
 147
 148   for (auto ObjIndex : F) {
 149     uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
 150     if (OldFragmentIndex == 0) {
 151       // We haven't seen this object index before, so just add it to the current
 152       // fragment.
 153       Fragment.push_back(ObjIndex);
 154     } else {
 155       // This index belongs to an existing fragment. Copy the elements of the
 156       // old fragment into this one and clear the old fragment. We don't update
 157       // the fragment map just yet, this ensures that any further references to
 158       // indices from the old fragment in this fragment do not insert any more
 159       // indices.
 160       std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
 161       Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end());
 162       OldFragment.clear();
 163     }
 164   }
 165
 166   // Update the fragment map to point our object indices to this fragment.
 167   for (uint64_t ObjIndex : Fragment)
 168     FragmentMap[ObjIndex] = FragmentIndex;
 169 }
 170
 171 void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
 172                                 uint64_t BitSize, uint64_t &AllocByteOffset,
 173                                 uint8_t &AllocMask) {
 174   // Find the smallest current allocation.
 175   unsigned Bit = 0;
 176   for (unsigned I = 1; I != BitsPerByte; ++I)
 177     if (BitAllocs[I] < BitAllocs[Bit])
 178       Bit = I;
 179
 180   AllocByteOffset = BitAllocs[Bit];
 181
 182   // Add our size to it.
 183   unsigned ReqSize = AllocByteOffset + BitSize;
 184   BitAllocs[Bit] = ReqSize;
 185   if (Bytes.size() < ReqSize)
 186     Bytes.resize(ReqSize);
 187
 188   // Set our bits.
 189   AllocMask = 1 << Bit;
 190   for (uint64_t B : Bits)
 191     Bytes[AllocByteOffset + B] |= AllocMask;
 192 }
 193
 194 namespace {
 195
 196 struct ByteArrayInfo {
 197   std::set<uint64_t> Bits;
 198   uint64_t BitSize;
 199   GlobalVariable *ByteArray;
 200   GlobalVariable *MaskGlobal;
 201 };
 202
 203 /// A POD-like structure that we use to store a global reference together with
 204 /// its metadata types. In this pass we frequently need to query the set of
 205 /// metadata types referenced by a global, which at the IR level is an expensive
 206 /// operation involving a map lookup; this data structure helps to reduce the
 207 /// number of times we need to do this lookup.
 208 class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
 209   GlobalObject *GO;
 210   size_t NTypes;
 211
 212   friend TrailingObjects;
 213   size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; }
 214
 215 public:
 216   static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
 217                                   ArrayRef<MDNode *> Types) {
 218     auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
 219         totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember)));
 220     GTM->GO = GO;
 221     GTM->NTypes = Types.size();
 222     std::uninitialized_copy(Types.begin(), Types.end(),
 223                             GTM->getTrailingObjects<MDNode *>());
 224     return GTM;
 225   }
 226   GlobalObject *getGlobal() const {
 227     return GO;
 228   }
 229   ArrayRef<MDNode *> types() const {
 230     return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
 231   }
 232 };
 233
 234 class LowerTypeTestsModule {
 235   Module &M;
 236
 237   SummaryAction Action;
 238   ModuleSummaryIndex *Summary;
 239
 240   bool LinkerSubsectionsViaSymbols;
 241   Triple::ArchType Arch;
 242   Triple::OSType OS;
 243   Triple::ObjectFormatType ObjectFormat;
 244
 245   IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
 246   IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
 247   PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
 248   IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
 249   PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty);
 250   IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
 251   IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
 252
 253   // Indirect function call index assignment counter for WebAssembly
 254   uint64_t IndirectIndex = 1;
 255
 256   // Mapping from type identifiers to the call sites that test them.
 257   DenseMap<Metadata *, std::vector<CallInst *>> TypeTestCallSites;
 258
 259   /// This structure describes how to lower type tests for a particular type
 260   /// identifier. It is either built directly from the global analysis (during
 261   /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
 262   /// identifier summaries and external symbol references (in ThinLTO backends).
 263   struct TypeIdLowering {
 264     TypeTestResolution::Kind TheKind;
 265
 266     /// All except Unsat: the start address within the combined global.
 267     Constant *OffsetedGlobal;
 268
 269     /// ByteArray, Inline, AllOnes: log2 of the required global alignment
 270     /// relative to the start address.
 271     Constant *AlignLog2;
 272
 273     /// ByteArray, Inline, AllOnes: one less than the size of the memory region
 274     /// covering members of this type identifier as a multiple of 2^AlignLog2.
 275     Constant *SizeM1;
 276
 277     /// ByteArray, Inline, AllOnes: range of SizeM1 expressed as a bit width.
 278     unsigned SizeM1BitWidth;
 279
 280     /// ByteArray: the byte array to test the address against.
 281     Constant *TheByteArray;
 282
 283     /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
 284     Constant *BitMask;
 285
 286     /// Inline: the bit mask to test the address against.
 287     Constant *InlineBits;
 288   };
 289
 290   std::vector<ByteArrayInfo> ByteArrayInfos;
 291
 292   Function *WeakInitializerFn = nullptr;
 293
 294   BitSetInfo
 295   buildBitSet(Metadata *TypeId,
 296               const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
 297   ByteArrayInfo *createByteArray(BitSetInfo &BSI);
 298   void allocateByteArrays();
 299   Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
 300                           Value *BitOffset);
 301   void lowerTypeTestCalls(
 302       ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
 303       const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
 304   Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
 305                            const TypeIdLowering &TIL);
 306   void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
 307                                        ArrayRef<GlobalTypeMember *> Globals);
 308   unsigned getJumpTableEntrySize();
 309   Type *getJumpTableEntryType();
 310   void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
 311                             SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
 312   void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
 313   void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
 314                                  ArrayRef<GlobalTypeMember *> Functions);
 315   void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
 316                                     ArrayRef<GlobalTypeMember *> Functions);
 317   void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
 318                                      ArrayRef<GlobalTypeMember *> Functions);
 319   void buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
 320                                    ArrayRef<GlobalTypeMember *> Globals);
 321
 322   void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT);
 323   void moveInitializerToModuleConstructor(GlobalVariable *GV);
 324   void findGlobalVariableUsersOf(Constant *C,
 325                                  SmallSetVector<GlobalVariable *, 8> &Out);
 326
 327   void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
 328
 329 public:
 330   LowerTypeTestsModule(Module &M, SummaryAction Action,
 331                        ModuleSummaryIndex *Summary);
 332   bool lower();
 333
 334   // Lower the module using the action and summary passed as command line
 335   // arguments. For testing purposes only.
 336   static bool runForTesting(Module &M);
 337 };
 338
 339 struct LowerTypeTests : public ModulePass {
 340   static char ID;
 341
 342   bool UseCommandLine = false;
 343
 344   SummaryAction Action;
 345   ModuleSummaryIndex *Summary;
 346
 347   LowerTypeTests() : ModulePass(ID), UseCommandLine(true) {
 348     initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
 349   }
 350
 351   LowerTypeTests(SummaryAction Action, ModuleSummaryIndex *Summary)
 352       : ModulePass(ID), Action(Action), Summary(Summary) {
 353     initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
 354   }
 355
 356   bool runOnModule(Module &M) override {
 357     if (skipModule(M))
 358       return false;
 359     if (UseCommandLine)
 360       return LowerTypeTestsModule::runForTesting(M);
 361     return LowerTypeTestsModule(M, Action, Summary).lower();
 362   }
 363 };
 364
 365 } // anonymous namespace
 366
 367 INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,
 368                 false)
 369 char LowerTypeTests::ID = 0;
 370
 371 ModulePass *llvm::createLowerTypeTestsPass(SummaryAction Action,
 372                                            ModuleSummaryIndex *Summary) {
 373   return new LowerTypeTests(Action, Summary);
 374 }
 375
 376 /// Build a bit set for TypeId using the object layouts in
 377 /// GlobalLayout.
 378 BitSetInfo LowerTypeTestsModule::buildBitSet(
 379     Metadata *TypeId,
 380     const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
 381   BitSetBuilder BSB;
 382
 383   // Compute the byte offset of each address associated with this type
 384   // identifier.
 385   for (auto &GlobalAndOffset : GlobalLayout) {
 386     for (MDNode *Type : GlobalAndOffset.first->types()) {
 387       if (Type->getOperand(1) != TypeId)
 388         continue;
 389       uint64_t Offset =
 390           cast<ConstantInt>(
 391               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 392               ->getZExtValue();
 393       BSB.addOffset(GlobalAndOffset.second + Offset);
 394     }
 395   }
 396
 397   return BSB.build();
 398 }
 399
 400 /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
 401 /// Bits. This pattern matches to the bt instruction on x86.
 402 static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits,
 403                                   Value *BitOffset) {
 404   auto BitsType = cast<IntegerType>(Bits->getType());
 405   unsigned BitWidth = BitsType->getBitWidth();
 406
 407   BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
 408   Value *BitIndex =
 409       B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
 410   Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
 411   Value *MaskedBits = B.CreateAnd(Bits, BitMask);
 412   return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
 413 }
 414
 415 ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
 416   // Create globals to stand in for byte arrays and masks. These never actually
 417   // get initialized, we RAUW and erase them later in allocateByteArrays() once
 418   // we know the offset and mask to use.
 419   auto ByteArrayGlobal = new GlobalVariable(
 420       M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
 421   auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
 422                                        GlobalValue::PrivateLinkage, nullptr);
 423
 424   ByteArrayInfos.emplace_back();
 425   ByteArrayInfo *BAI = &ByteArrayInfos.back();
 426
 427   BAI->Bits = BSI.Bits;
 428   BAI->BitSize = BSI.BitSize;
 429   BAI->ByteArray = ByteArrayGlobal;
 430   BAI->MaskGlobal = MaskGlobal;
 431   return BAI;
 432 }
 433
 434 void LowerTypeTestsModule::allocateByteArrays() {
 435   std::stable_sort(ByteArrayInfos.begin(), ByteArrayInfos.end(),
 436                    [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
 437                      return BAI1.BitSize > BAI2.BitSize;
 438                    });
 439
 440   std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
 441
 442   ByteArrayBuilder BAB;
 443   for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
 444     ByteArrayInfo *BAI = &ByteArrayInfos[I];
 445
 446     uint8_t Mask;
 447     BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
 448
 449     BAI->MaskGlobal->replaceAllUsesWith(
 450         ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
 451     BAI->MaskGlobal->eraseFromParent();
 452   }
 453
 454   Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
 455   auto ByteArray =
 456       new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
 457                          GlobalValue::PrivateLinkage, ByteArrayConst);
 458
 459   for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
 460     ByteArrayInfo *BAI = &ByteArrayInfos[I];
 461
 462     Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
 463                         ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
 464     Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(
 465         ByteArrayConst->getType(), ByteArray, Idxs);
 466
 467     // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
 468     // that the pc-relative displacement is folded into the lea instead of the
 469     // test instruction getting another displacement.
 470     if (LinkerSubsectionsViaSymbols) {
 471       BAI->ByteArray->replaceAllUsesWith(GEP);
 472     } else {
 473       GlobalAlias *Alias = GlobalAlias::create(
 474           Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
 475       BAI->ByteArray->replaceAllUsesWith(Alias);
 476     }
 477     BAI->ByteArray->eraseFromParent();
 478   }
 479
 480   ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
 481                       BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
 482                       BAB.BitAllocs[6] + BAB.BitAllocs[7];
 483   ByteArraySizeBytes = BAB.Bytes.size();
 484 }
 485
 486 /// Build a test that bit BitOffset is set in the type identifier that was
 487 /// lowered to TIL, which must be either an Inline or a ByteArray.
 488 Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
 489                                               const TypeIdLowering &TIL,
 490                                               Value *BitOffset) {
 491   if (TIL.TheKind == TypeTestResolution::Inline) {
 492     // If the bit set is sufficiently small, we can avoid a load by bit testing
 493     // a constant.
 494     return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
 495   } else {
 496     Constant *ByteArray = TIL.TheByteArray;
 497     if (!LinkerSubsectionsViaSymbols && AvoidReuse) {
 498       // Each use of the byte array uses a different alias. This makes the
 499       // backend less likely to reuse previously computed byte array addresses,
 500       // improving the security of the CFI mechanism based on this pass.
 501       ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage,
 502                                       "bits_use", ByteArray, &M);
 503     }
 504
 505     Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
 506     Value *Byte = B.CreateLoad(ByteAddr);
 507
 508     Value *ByteAndMask =
 509         B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
 510     return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
 511   }
 512 }
 513
 514 static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
 515                                 Value *V, uint64_t COffset) {
 516   if (auto GV = dyn_cast<GlobalObject>(V)) {
 517     SmallVector<MDNode *, 2> Types;
 518     GV->getMetadata(LLVMContext::MD_type, Types);
 519     for (MDNode *Type : Types) {
 520       if (Type->getOperand(1) != TypeId)
 521         continue;
 522       uint64_t Offset =
 523           cast<ConstantInt>(
 524               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 525               ->getZExtValue();
 526       if (COffset == Offset)
 527         return true;
 528     }
 529     return false;
 530   }
 531
 532   if (auto GEP = dyn_cast<GEPOperator>(V)) {
 533     APInt APOffset(DL.getPointerSizeInBits(0), 0);
 534     bool Result = GEP->accumulateConstantOffset(DL, APOffset);
 535     if (!Result)
 536       return false;
 537     COffset += APOffset.getZExtValue();
 538     return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
 539   }
 540
 541   if (auto Op = dyn_cast<Operator>(V)) {
 542     if (Op->getOpcode() == Instruction::BitCast)
 543       return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
 544
 545     if (Op->getOpcode() == Instruction::Select)
 546       return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
 547              isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
 548   }
 549
 550   return false;
 551 }
 552
 553 /// Lower a llvm.type.test call to its implementation. Returns the value to
 554 /// replace the call with.
 555 Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
 556                                                const TypeIdLowering &TIL) {
 557   if (TIL.TheKind == TypeTestResolution::Unsat)
 558     return ConstantInt::getFalse(M.getContext());
 559
 560   Value *Ptr = CI->getArgOperand(0);
 561   const DataLayout &DL = M.getDataLayout();
 562   if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
 563     return ConstantInt::getTrue(M.getContext());
 564
 565   BasicBlock *InitialBB = CI->getParent();
 566
 567   IRBuilder<> B(CI);
 568
 569   Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
 570
 571   Constant *OffsetedGlobalAsInt =
 572       ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
 573   if (TIL.TheKind == TypeTestResolution::Single)
 574     return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
 575
 576   Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
 577
 578   // We need to check that the offset both falls within our range and is
 579   // suitably aligned. We can check both properties at the same time by
 580   // performing a right rotate by log2(alignment) followed by an integer
 581   // comparison against the bitset size. The rotate will move the lower
 582   // order bits that need to be zero into the higher order bits of the
 583   // result, causing the comparison to fail if they are nonzero. The rotate
 584   // also conveniently gives us a bit offset to use during the load from
 585   // the bitset.
 586   Value *OffsetSHR =
 587       B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
 588   Value *OffsetSHL = B.CreateShl(
 589       PtrOffset, ConstantExpr::getZExt(
 590                      ConstantExpr::getSub(
 591                          ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
 592                          TIL.AlignLog2),
 593                      IntPtrTy));
 594   Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
 595
 596   Constant *BitSizeConst = ConstantExpr::getZExt(TIL.SizeM1, IntPtrTy);
 597   Value *OffsetInRange = B.CreateICmpULE(BitOffset, BitSizeConst);
 598
 599   // If the bit set is all ones, testing against it is unnecessary.
 600   if (TIL.TheKind == TypeTestResolution::AllOnes)
 601     return OffsetInRange;
 602
 603   TerminatorInst *Term = SplitBlockAndInsertIfThen(OffsetInRange, CI, false);
 604   IRBuilder<> ThenB(Term);
 605
 606   // Now that we know that the offset is in range and aligned, load the
 607   // appropriate bit from the bitset.
 608   Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
 609
 610   // The value we want is 0 if we came directly from the initial block
 611   // (having failed the range or alignment checks), or the loaded bit if
 612   // we came from the block in which we loaded it.
 613   B.SetInsertPoint(CI);
 614   PHINode *P = B.CreatePHI(Int1Ty, 2);
 615   P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
 616   P->addIncoming(Bit, ThenB.GetInsertBlock());
 617   return P;
 618 }
 619
 620 /// Given a disjoint set of type identifiers and globals, lay out the globals,
 621 /// build the bit sets and lower the llvm.type.test calls.
 622 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
 623     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
 624   // Build a new global with the combined contents of the referenced globals.
 625   // This global is a struct whose even-indexed elements contain the original
 626   // contents of the referenced globals and whose odd-indexed elements contain
 627   // any padding required to align the next element to the next power of 2.
 628   std::vector<Constant *> GlobalInits;
 629   const DataLayout &DL = M.getDataLayout();
 630   for (GlobalTypeMember *G : Globals) {
 631     GlobalVariable *GV = cast<GlobalVariable>(G->getGlobal());
 632     GlobalInits.push_back(GV->getInitializer());
 633     uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
 634
 635     // Compute the amount of padding required.
 636     uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize;
 637
 638     // Cap at 128 was found experimentally to have a good data/instruction
 639     // overhead tradeoff.
 640     if (Padding > 128)
 641       Padding = alignTo(InitSize, 128) - InitSize;
 642
 643     GlobalInits.push_back(
 644         ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding)));
 645   }
 646   if (!GlobalInits.empty())
 647     GlobalInits.pop_back();
 648   Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
 649   auto *CombinedGlobal =
 650       new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
 651                          GlobalValue::PrivateLinkage, NewInit);
 652
 653   StructType *NewTy = cast<StructType>(NewInit->getType());
 654   const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy);
 655
 656   // Compute the offsets of the original globals within the new global.
 657   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
 658   for (unsigned I = 0; I != Globals.size(); ++I)
 659     // Multiply by 2 to account for padding elements.
 660     GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2);
 661
 662   lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
 663
 664   // Build aliases pointing to offsets into the combined global for each
 665   // global from which we built the combined global, and replace references
 666   // to the original globals with references to the aliases.
 667   for (unsigned I = 0; I != Globals.size(); ++I) {
 668     GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
 669
 670     // Multiply by 2 to account for padding elements.
 671     Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
 672                                       ConstantInt::get(Int32Ty, I * 2)};
 673     Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
 674         NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
 675     if (LinkerSubsectionsViaSymbols) {
 676       GV->replaceAllUsesWith(CombinedGlobalElemPtr);
 677     } else {
 678       assert(GV->getType()->getAddressSpace() == 0);
 679       GlobalAlias *GAlias = GlobalAlias::create(NewTy->getElementType(I * 2), 0,
 680                                                 GV->getLinkage(), "",
 681                                                 CombinedGlobalElemPtr, &M);
 682       GAlias->setVisibility(GV->getVisibility());
 683       GAlias->takeName(GV);
 684       GV->replaceAllUsesWith(GAlias);
 685     }
 686     GV->eraseFromParent();
 687   }
 688 }
 689
 690 void LowerTypeTestsModule::lowerTypeTestCalls(
 691     ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
 692     const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
 693   CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
 694
 695   // For each type identifier in this disjoint set...
 696   for (Metadata *TypeId : TypeIds) {
 697     // Build the bitset.
 698     BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
 699     DEBUG({
 700       if (auto MDS = dyn_cast<MDString>(TypeId))
 701         dbgs() << MDS->getString() << ": ";
 702       else
 703         dbgs() << "<unnamed>: ";
 704       BSI.print(dbgs());
 705     });
 706
 707     TypeIdLowering TIL;
 708     TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
 709         Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
 710     TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
 711     if (BSI.isAllOnes()) {
 712       TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
 713                                        : TypeTestResolution::AllOnes;
 714       TIL.SizeM1BitWidth = (BSI.BitSize <= 128) ? 7 : 32;
 715       TIL.SizeM1 = ConstantInt::get((BSI.BitSize <= 128) ? Int8Ty : Int32Ty,
 716                                     BSI.BitSize - 1);
 717     } else if (BSI.BitSize <= 64) {
 718       TIL.TheKind = TypeTestResolution::Inline;
 719       TIL.SizeM1BitWidth = (BSI.BitSize <= 32) ? 5 : 6;
 720       TIL.SizeM1 = ConstantInt::get(Int8Ty, BSI.BitSize - 1);
 721       uint64_t InlineBits = 0;
 722       for (auto Bit : BSI.Bits)
 723         InlineBits |= uint64_t(1) << Bit;
 724       if (InlineBits == 0)
 725         TIL.TheKind = TypeTestResolution::Unsat;
 726       else
 727         TIL.InlineBits = ConstantInt::get(
 728             (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
 729     } else {
 730       TIL.TheKind = TypeTestResolution::ByteArray;
 731       TIL.SizeM1BitWidth = (BSI.BitSize <= 128) ? 7 : 32;
 732       TIL.SizeM1 = ConstantInt::get((BSI.BitSize <= 128) ? Int8Ty : Int32Ty,
 733                                     BSI.BitSize - 1);
 734       ++NumByteArraysCreated;
 735       ByteArrayInfo *BAI = createByteArray(BSI);
 736       TIL.TheByteArray = BAI->ByteArray;
 737       TIL.BitMask = BAI->MaskGlobal;
 738     }
 739
 740     // Lower each call to llvm.type.test for this type identifier.
 741     for (CallInst *CI : TypeTestCallSites[TypeId]) {
 742       ++NumTypeTestCallsLowered;
 743       Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
 744       CI->replaceAllUsesWith(Lowered);
 745       CI->eraseFromParent();
 746     }
 747   }
 748 }
 749
 750 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
 751   if (Type->getNumOperands() != 2)
 752     report_fatal_error("All operands of type metadata must have 2 elements");
 753
 754   if (GO->isThreadLocal())
 755     report_fatal_error("Bit set element may not be thread-local");
 756   if (isa<GlobalVariable>(GO) && GO->hasSection())
 757     report_fatal_error(
 758         "A member of a type identifier may not have an explicit section");
 759
 760   if (isa<GlobalVariable>(GO) && GO->isDeclarationForLinker())
 761     report_fatal_error(
 762         "A global var member of a type identifier must be a definition");
 763
 764   auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
 765   if (!OffsetConstMD)
 766     report_fatal_error("Type offset must be a constant");
 767   auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
 768   if (!OffsetInt)
 769     report_fatal_error("Type offset must be an integer constant");
 770 }
 771
 772 static const unsigned kX86JumpTableEntrySize = 8;
 773 static const unsigned kARMJumpTableEntrySize = 4;
 774
 775 unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
 776   switch (Arch) {
 777     case Triple::x86:
 778     case Triple::x86_64:
 779       return kX86JumpTableEntrySize;
 780     case Triple::arm:
 781     case Triple::thumb:
 782     case Triple::aarch64:
 783       return kARMJumpTableEntrySize;
 784     default:
 785       report_fatal_error("Unsupported architecture for jump tables");
 786   }
 787 }
 788
 789 // Create a jump table entry for the target. This consists of an instruction
 790 // sequence containing a relative branch to Dest. Appends inline asm text,
 791 // constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
 792 void LowerTypeTestsModule::createJumpTableEntry(
 793     raw_ostream &AsmOS, raw_ostream &ConstraintOS,
 794     SmallVectorImpl<Value *> &AsmArgs, Function *Dest) {
 795   unsigned ArgIndex = AsmArgs.size();
 796
 797   if (Arch == Triple::x86 || Arch == Triple::x86_64) {
 798     AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
 799     AsmOS << "int3\nint3\nint3\n";
 800   } else if (Arch == Triple::arm || Arch == Triple::aarch64) {
 801     AsmOS << "b $" << ArgIndex << "\n";
 802   } else if (Arch == Triple::thumb) {
 803     AsmOS << "b.w $" << ArgIndex << "\n";
 804   } else {
 805     report_fatal_error("Unsupported architecture for jump tables");
 806   }
 807
 808   ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
 809   AsmArgs.push_back(Dest);
 810 }
 811
 812 Type *LowerTypeTestsModule::getJumpTableEntryType() {
 813   return ArrayType::get(Int8Ty, getJumpTableEntrySize());
 814 }
 815
 816 /// Given a disjoint set of type identifiers and functions, build the bit sets
 817 /// and lower the llvm.type.test calls, architecture dependently.
 818 void LowerTypeTestsModule::buildBitSetsFromFunctions(
 819     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
 820   if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
 821       Arch == Triple::thumb || Arch == Triple::aarch64)
 822     buildBitSetsFromFunctionsNative(TypeIds, Functions);
 823   else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
 824     buildBitSetsFromFunctionsWASM(TypeIds, Functions);
 825   else
 826     report_fatal_error("Unsupported architecture for jump tables");
 827 }
 828
 829 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
 830     GlobalVariable *GV) {
 831   if (WeakInitializerFn == nullptr) {
 832     WeakInitializerFn = Function::Create(
 833         FunctionType::get(Type::getVoidTy(M.getContext()),
 834                           /* IsVarArg */ false),
 835         GlobalValue::InternalLinkage, "__cfi_global_var_init", &M);
 836     BasicBlock *BB =
 837         BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
 838     ReturnInst::Create(M.getContext(), BB);
 839     WeakInitializerFn->setSection(
 840         ObjectFormat == Triple::MachO
 841             ? "__TEXT,__StaticInit,regular,pure_instructions"
 842             : ".text.startup");
 843     // This code is equivalent to relocation application, and should run at the
 844     // earliest possible time (i.e. with the highest priority).
 845     appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
 846   }
 847
 848   IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
 849   GV->setConstant(false);
 850   IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlignment());
 851   GV->setInitializer(Constant::getNullValue(GV->getValueType()));
 852 }
 853
 854 void LowerTypeTestsModule::findGlobalVariableUsersOf(
 855     Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
 856   for (auto *U : C->users()){
 857     if (auto *GV = dyn_cast<GlobalVariable>(U))
 858       Out.insert(GV);
 859     else if (auto *C2 = dyn_cast<Constant>(U))
 860       findGlobalVariableUsersOf(C2, Out);
 861   }
 862 }
 863
 864 // Replace all uses of F with (F ? JT : 0).
 865 void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
 866     Function *F, Constant *JT) {
 867   // The target expression can not appear in a constant initializer on most
 868   // (all?) targets. Switch to a runtime initializer.
 869   SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
 870   findGlobalVariableUsersOf(F, GlobalVarUsers);
 871   for (auto GV : GlobalVarUsers)
 872     moveInitializerToModuleConstructor(GV);
 873
 874   // Can not RAUW F with an expression that uses F. Replace with a temporary
 875   // placeholder first.
 876   Function *PlaceholderFn =
 877       Function::Create(cast<FunctionType>(F->getValueType()),
 878                        GlobalValue::ExternalWeakLinkage, "", &M);
 879   F->replaceAllUsesWith(PlaceholderFn);
 880
 881   Constant *Target = ConstantExpr::getSelect(
 882       ConstantExpr::getICmp(CmpInst::ICMP_NE, F,
 883                             Constant::getNullValue(F->getType())),
 884       JT, Constant::getNullValue(F->getType()));
 885   PlaceholderFn->replaceAllUsesWith(Target);
 886   PlaceholderFn->eraseFromParent();
 887 }
 888
 889 void LowerTypeTestsModule::createJumpTable(
 890     Function *F, ArrayRef<GlobalTypeMember *> Functions) {
 891   std::string AsmStr, ConstraintStr;
 892   raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
 893   SmallVector<Value *, 16> AsmArgs;
 894   AsmArgs.reserve(Functions.size() * 2);
 895
 896   for (unsigned I = 0; I != Functions.size(); ++I)
 897     createJumpTableEntry(AsmOS, ConstraintOS, AsmArgs,
 898                          cast<Function>(Functions[I]->getGlobal()));
 899
 900   // Try to emit the jump table at the end of the text segment.
 901   // Jump table must come after __cfi_check in the cross-dso mode.
 902   // FIXME: this magic section name seems to do the trick.
 903   F->setSection(ObjectFormat == Triple::MachO
 904                     ? "__TEXT,__text,regular,pure_instructions"
 905                     : ".text.cfi");
 906   // Align the whole table by entry size.
 907   F->setAlignment(getJumpTableEntrySize());
 908   // Skip prologue.
 909   // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
 910   // Luckily, this function does not get any prologue even without the
 911   // attribute.
 912   if (OS != Triple::Win32)
 913     F->addFnAttr(llvm::Attribute::Naked);
 914   // Thumb jump table assembly needs Thumb2. The following attribute is added by
 915   // Clang for -march=armv7.
 916   if (Arch == Triple::thumb)
 917     F->addFnAttr("target-cpu", "cortex-a8");
 918
 919   BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
 920   IRBuilder<> IRB(BB);
 921
 922   SmallVector<Type *, 16> ArgTypes;
 923   ArgTypes.reserve(AsmArgs.size());
 924   for (const auto &Arg : AsmArgs)
 925     ArgTypes.push_back(Arg->getType());
 926   InlineAsm *JumpTableAsm =
 927       InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
 928                      AsmOS.str(), ConstraintOS.str(),
 929                      /*hasSideEffects=*/true);
 930
 931   IRB.CreateCall(JumpTableAsm, AsmArgs);
 932   IRB.CreateUnreachable();
 933 }
 934
 935 /// Given a disjoint set of type identifiers and functions, build a jump table
 936 /// for the functions, build the bit sets and lower the llvm.type.test calls.
 937 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
 938     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
 939   // Unlike the global bitset builder, the function bitset builder cannot
 940   // re-arrange functions in a particular order and base its calculations on the
 941   // layout of the functions' entry points, as we have no idea how large a
 942   // particular function will end up being (the size could even depend on what
 943   // this pass does!) Instead, we build a jump table, which is a block of code
 944   // consisting of one branch instruction for each of the functions in the bit
 945   // set that branches to the target function, and redirect any taken function
 946   // addresses to the corresponding jump table entry. In the object file's
 947   // symbol table, the symbols for the target functions also refer to the jump
 948   // table entries, so that addresses taken outside the module will pass any
 949   // verification done inside the module.
 950   //
 951   // In more concrete terms, suppose we have three functions f, g, h which are
 952   // of the same type, and a function foo that returns their addresses:
 953   //
 954   // f:
 955   // mov 0, %eax
 956   // ret
 957   //
 958   // g:
 959   // mov 1, %eax
 960   // ret
 961   //
 962   // h:
 963   // mov 2, %eax
 964   // ret
 965   //
 966   // foo:
 967   // mov f, %eax
 968   // mov g, %edx
 969   // mov h, %ecx
 970   // ret
 971   //
 972   // We output the jump table as module-level inline asm string. The end result
 973   // will (conceptually) look like this:
 974   //
 975   // f = .cfi.jumptable
 976   // g = .cfi.jumptable + 4
 977   // h = .cfi.jumptable + 8
 978   // .cfi.jumptable:
 979   // jmp f.cfi  ; 5 bytes
 980   // int3       ; 1 byte
 981   // int3       ; 1 byte
 982   // int3       ; 1 byte
 983   // jmp g.cfi  ; 5 bytes
 984   // int3       ; 1 byte
 985   // int3       ; 1 byte
 986   // int3       ; 1 byte
 987   // jmp h.cfi  ; 5 bytes
 988   // int3       ; 1 byte
 989   // int3       ; 1 byte
 990   // int3       ; 1 byte
 991   //
 992   // f.cfi:
 993   // mov 0, %eax
 994   // ret
 995   //
 996   // g.cfi:
 997   // mov 1, %eax
 998   // ret
 999   //
1000   // h.cfi:
1001   // mov 2, %eax
1002   // ret
1003   //
1004   // foo:
1005   // mov f, %eax
1006   // mov g, %edx
1007   // mov h, %ecx
1008   // ret
1009   //
1010   // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1011   // normal case the check can be carried out using the same kind of simple
1012   // arithmetic that we normally use for globals.
1013
1014   // FIXME: find a better way to represent the jumptable in the IR.
1015
1016   assert(!Functions.empty());
1017
1018   // Build a simple layout based on the regular layout of jump tables.
1019   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1020   unsigned EntrySize = getJumpTableEntrySize();
1021   for (unsigned I = 0; I != Functions.size(); ++I)
1022     GlobalLayout[Functions[I]] = I * EntrySize;
1023
1024   Function *JumpTableFn =
1025       Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()),
1026                                          /* IsVarArg */ false),
1027                        GlobalValue::PrivateLinkage, ".cfi.jumptable", &M);
1028   ArrayType *JumpTableType =
1029       ArrayType::get(getJumpTableEntryType(), Functions.size());
1030   auto JumpTable =
1031       ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
1032
1033   lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
1034
1035   // Build aliases pointing to offsets into the jump table, and replace
1036   // references to the original functions with references to the aliases.
1037   for (unsigned I = 0; I != Functions.size(); ++I) {
1038     Function *F = cast<Function>(Functions[I]->getGlobal());
1039
1040     Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
1041         ConstantExpr::getInBoundsGetElementPtr(
1042             JumpTableType, JumpTable,
1043             ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0),
1044                                  ConstantInt::get(IntPtrTy, I)}),
1045         F->getType());
1046     if (LinkerSubsectionsViaSymbols || F->isDeclarationForLinker()) {
1047
1048       if (F->isWeakForLinker())
1049         replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr);
1050       else
1051         F->replaceAllUsesWith(CombinedGlobalElemPtr);
1052     } else {
1053       assert(F->getType()->getAddressSpace() == 0);
1054
1055       GlobalAlias *FAlias = GlobalAlias::create(F->getValueType(), 0,
1056                                                 F->getLinkage(), "",
1057                                                 CombinedGlobalElemPtr, &M);
1058       FAlias->setVisibility(F->getVisibility());
1059       FAlias->takeName(F);
1060       if (FAlias->hasName())
1061         F->setName(FAlias->getName() + ".cfi");
1062       F->replaceAllUsesWith(FAlias);
1063     }
1064     if (!F->isDeclarationForLinker())
1065       F->setLinkage(GlobalValue::InternalLinkage);
1066   }
1067
1068   createJumpTable(JumpTableFn, Functions);
1069 }
1070
1071 /// Assign a dummy layout using an incrementing counter, tag each function
1072 /// with its index represented as metadata, and lower each type test to an
1073 /// integer range comparison. During generation of the indirect function call
1074 /// table in the backend, it will assign the given indexes.
1075 /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1076 /// been finalized.
1077 void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1078     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1079   assert(!Functions.empty());
1080
1081   // Build consecutive monotonic integer ranges for each call target set
1082   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1083
1084   for (GlobalTypeMember *GTM : Functions) {
1085     Function *F = cast<Function>(GTM->getGlobal());
1086
1087     // Skip functions that are not address taken, to avoid bloating the table
1088     if (!F->hasAddressTaken())
1089       continue;
1090
1091     // Store metadata with the index for each function
1092     MDNode *MD = MDNode::get(F->getContext(),
1093                              ArrayRef<Metadata *>(ConstantAsMetadata::get(
1094                                  ConstantInt::get(Int64Ty, IndirectIndex))));
1095     F->setMetadata("wasm.index", MD);
1096
1097     // Assign the counter value
1098     GlobalLayout[GTM] = IndirectIndex++;
1099   }
1100
1101   // The indirect function table index space starts at zero, so pass a NULL
1102   // pointer as the subtracted "jump table" offset.
1103   lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
1104                      GlobalLayout);
1105 }
1106
1107 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1108     ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
1109   llvm::DenseMap<Metadata *, uint64_t> TypeIdIndices;
1110   for (unsigned I = 0; I != TypeIds.size(); ++I)
1111     TypeIdIndices[TypeIds[I]] = I;
1112
1113   // For each type identifier, build a set of indices that refer to members of
1114   // the type identifier.
1115   std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1116   unsigned GlobalIndex = 0;
1117   for (GlobalTypeMember *GTM : Globals) {
1118     for (MDNode *Type : GTM->types()) {
1119       // Type = { offset, type identifier }
1120       unsigned TypeIdIndex = TypeIdIndices[Type->getOperand(1)];
1121       TypeMembers[TypeIdIndex].insert(GlobalIndex);
1122     }
1123     GlobalIndex++;
1124   }
1125
1126   // Order the sets of indices by size. The GlobalLayoutBuilder works best
1127   // when given small index sets first.
1128   std::stable_sort(
1129       TypeMembers.begin(), TypeMembers.end(),
1130       [](const std::set<uint64_t> &O1, const std::set<uint64_t> &O2) {
1131         return O1.size() < O2.size();
1132       });
1133
1134   // Create a GlobalLayoutBuilder and provide it with index sets as layout
1135   // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1136   // close together as possible.
1137   GlobalLayoutBuilder GLB(Globals.size());
1138   for (auto &&MemSet : TypeMembers)
1139     GLB.addFragment(MemSet);
1140
1141   // Build the bitsets from this disjoint set.
1142   if (Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal())) {
1143     // Build a vector of global variables with the computed layout.
1144     std::vector<GlobalTypeMember *> OrderedGVs(Globals.size());
1145     auto OGI = OrderedGVs.begin();
1146     for (auto &&F : GLB.Fragments) {
1147       for (auto &&Offset : F) {
1148         auto GV = dyn_cast<GlobalVariable>(Globals[Offset]->getGlobal());
1149         if (!GV)
1150           report_fatal_error("Type identifier may not contain both global "
1151                              "variables and functions");
1152         *OGI++ = Globals[Offset];
1153       }
1154     }
1155
1156     buildBitSetsFromGlobalVariables(TypeIds, OrderedGVs);
1157   } else {
1158     // Build a vector of functions with the computed layout.
1159     std::vector<GlobalTypeMember *> OrderedFns(Globals.size());
1160     auto OFI = OrderedFns.begin();
1161     for (auto &&F : GLB.Fragments) {
1162       for (auto &&Offset : F) {
1163         auto Fn = dyn_cast<Function>(Globals[Offset]->getGlobal());
1164         if (!Fn)
1165           report_fatal_error("Type identifier may not contain both global "
1166                              "variables and functions");
1167         *OFI++ = Globals[Offset];
1168       }
1169     }
1170
1171     buildBitSetsFromFunctions(TypeIds, OrderedFns);
1172   }
1173 }
1174
1175 /// Lower all type tests in this module.
1176 LowerTypeTestsModule::LowerTypeTestsModule(Module &M, SummaryAction Action,
1177                                            ModuleSummaryIndex *Summary)
1178     : M(M), Action(Action), Summary(Summary) {
1179   // FIXME: Use these fields.
1180   (void)this->Action;
1181   (void)this->Summary;
1182
1183   Triple TargetTriple(M.getTargetTriple());
1184   LinkerSubsectionsViaSymbols = TargetTriple.isMacOSX();
1185   Arch = TargetTriple.getArch();
1186   OS = TargetTriple.getOS();
1187   ObjectFormat = TargetTriple.getObjectFormat();
1188 }
1189
1190 bool LowerTypeTestsModule::runForTesting(Module &M) {
1191   ModuleSummaryIndex Summary;
1192
1193   // Handle the command-line summary arguments. This code is for testing
1194   // purposes only, so we handle errors directly.
1195   if (!ClReadSummary.empty()) {
1196     ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1197                           ": ");
1198     auto ReadSummaryFile =
1199         ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
1200
1201     yaml::Input In(ReadSummaryFile->getBuffer());
1202     In >> Summary;
1203     ExitOnErr(errorCodeToError(In.error()));
1204   }
1205
1206   bool Changed = LowerTypeTestsModule(M, ClSummaryAction, &Summary).lower();
1207
1208   if (!ClWriteSummary.empty()) {
1209     ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
1210                           ": ");
1211     std::error_code EC;
1212     raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text);
1213     ExitOnErr(errorCodeToError(EC));
1214
1215     yaml::Output Out(OS);
1216     Out << Summary;
1217   }
1218
1219   return Changed;
1220 }
1221
1222 bool LowerTypeTestsModule::lower() {
1223   Function *TypeTestFunc =
1224       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1225   if (!TypeTestFunc || TypeTestFunc->use_empty())
1226     return false;
1227
1228   // Equivalence class set containing type identifiers and the globals that
1229   // reference them. This is used to partition the set of type identifiers in
1230   // the module into disjoint sets.
1231   typedef EquivalenceClasses<PointerUnion<GlobalTypeMember *, Metadata *>>
1232       GlobalClassesTy;
1233   GlobalClassesTy GlobalClasses;
1234
1235   // Verify the type metadata and build a few data structures to let us
1236   // efficiently enumerate the type identifiers associated with a global:
1237   // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
1238   // of associated type metadata) and a mapping from type identifiers to their
1239   // list of GlobalTypeMembers and last observed index in the list of globals.
1240   // The indices will be used later to deterministically order the list of type
1241   // identifiers.
1242   BumpPtrAllocator Alloc;
1243   struct TIInfo {
1244     unsigned Index;
1245     std::vector<GlobalTypeMember *> RefGlobals;
1246   };
1247   llvm::DenseMap<Metadata *, TIInfo> TypeIdInfo;
1248   unsigned I = 0;
1249   SmallVector<MDNode *, 2> Types;
1250   for (GlobalObject &GO : M.global_objects()) {
1251     Types.clear();
1252     GO.getMetadata(LLVMContext::MD_type, Types);
1253     if (Types.empty())
1254       continue;
1255
1256     auto *GTM = GlobalTypeMember::create(Alloc, &GO, Types);
1257     for (MDNode *Type : Types) {
1258       verifyTypeMDNode(&GO, Type);
1259       auto &Info = TypeIdInfo[cast<MDNode>(Type)->getOperand(1)];
1260       Info.Index = ++I;
1261       Info.RefGlobals.push_back(GTM);
1262     }
1263   }
1264
1265   for (const Use &U : TypeTestFunc->uses()) {
1266     auto CI = cast<CallInst>(U.getUser());
1267
1268     auto BitSetMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
1269     if (!BitSetMDVal)
1270       report_fatal_error("Second argument of llvm.type.test must be metadata");
1271     auto BitSet = BitSetMDVal->getMetadata();
1272
1273     // Add the call site to the list of call sites for this type identifier. We
1274     // also use TypeTestCallSites to keep track of whether we have seen this
1275     // type identifier before. If we have, we don't need to re-add the
1276     // referenced globals to the equivalence class.
1277     std::pair<DenseMap<Metadata *, std::vector<CallInst *>>::iterator, bool>
1278         Ins = TypeTestCallSites.insert(
1279             std::make_pair(BitSet, std::vector<CallInst *>()));
1280     Ins.first->second.push_back(CI);
1281     if (!Ins.second)
1282       continue;
1283
1284     // Add the type identifier to the equivalence class.
1285     GlobalClassesTy::iterator GCI = GlobalClasses.insert(BitSet);
1286     GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
1287
1288     // Add the referenced globals to the type identifier's equivalence class.
1289     for (GlobalTypeMember *GTM : TypeIdInfo[BitSet].RefGlobals)
1290       CurSet = GlobalClasses.unionSets(
1291           CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
1292   }
1293
1294   if (GlobalClasses.empty())
1295     return false;
1296
1297   // Build a list of disjoint sets ordered by their maximum global index for
1298   // determinism.
1299   std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
1300   for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
1301                                  E = GlobalClasses.end();
1302        I != E; ++I) {
1303     if (!I->isLeader())
1304       continue;
1305     ++NumTypeIdDisjointSets;
1306
1307     unsigned MaxIndex = 0;
1308     for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
1309          MI != GlobalClasses.member_end(); ++MI) {
1310       if ((*MI).is<Metadata *>())
1311         MaxIndex = std::max(MaxIndex, TypeIdInfo[MI->get<Metadata *>()].Index);
1312     }
1313     Sets.emplace_back(I, MaxIndex);
1314   }
1315   std::sort(Sets.begin(), Sets.end(),
1316             [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
1317                const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
1318               return S1.second < S2.second;
1319             });
1320
1321   // For each disjoint set we found...
1322   for (const auto &S : Sets) {
1323     // Build the list of type identifiers in this disjoint set.
1324     std::vector<Metadata *> TypeIds;
1325     std::vector<GlobalTypeMember *> Globals;
1326     for (GlobalClassesTy::member_iterator MI =
1327              GlobalClasses.member_begin(S.first);
1328          MI != GlobalClasses.member_end(); ++MI) {
1329       if ((*MI).is<Metadata *>())
1330         TypeIds.push_back(MI->get<Metadata *>());
1331       else
1332         Globals.push_back(MI->get<GlobalTypeMember *>());
1333     }
1334
1335     // Order type identifiers by global index for determinism. This ordering is
1336     // stable as there is a one-to-one mapping between metadata and indices.
1337     std::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) {
1338       return TypeIdInfo[M1].Index < TypeIdInfo[M2].Index;
1339     });
1340
1341     // Build bitsets for this disjoint set.
1342     buildBitSetsFromDisjointSet(TypeIds, Globals);
1343   }
1344
1345   allocateByteArrays();
1346
1347   return true;
1348 }
1349
1350 PreservedAnalyses LowerTypeTestsPass::run(Module &M,
1351                                           ModuleAnalysisManager &AM) {
1352   bool Changed =
1353       LowerTypeTestsModule(M, SummaryAction::None, /*Summary=*/nullptr).lower();
1354   if (!Changed)
1355     return PreservedAnalyses::all();
1356   return PreservedAnalyses::none();
1357 }