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