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