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