Coverage Report

Created: 2017-10-03 07:32

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