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<GlobalAlias *, Function *>> FunctionAliases;
346  std::vector<std::pair<GlobalIFunc *, Function *>> ResolverIFuncs;
347 
348  ScopedSaveAliaseesAndUsed(Module &M) : M(M) {
349  // The users of this class want to replace all function references except
350  // for aliases and llvm.used/llvm.compiler.used with references to a jump
351  // table. We avoid replacing aliases in order to avoid introducing a double
352  // indirection (or an alias pointing to a declaration in ThinLTO mode), and
353  // we avoid replacing llvm.used/llvm.compiler.used because these global
354  // variables describe properties of the global, not the jump table (besides,
355  // offseted references to the jump table in llvm.used are invalid).
356  // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly
357  // indirect) users", so what we do is save the list of globals referenced by
358  // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW
359  // replace the aliasees and then set them back to their original values at
360  // the end.
361  if (GlobalVariable *GV = collectUsedGlobalVariables(M, Used, false))
362  GV->eraseFromParent();
363  if (GlobalVariable *GV = collectUsedGlobalVariables(M, CompilerUsed, true))
364  GV->eraseFromParent();
365 
366  for (auto &GA : M.aliases()) {
367  // FIXME: This should look past all aliases not just interposable ones,
368  // see discussion on D65118.
369  if (auto *F = dyn_cast<Function>(GA.getAliasee()->stripPointerCasts()))
370  FunctionAliases.push_back({&GA, F});
371  }
372 
373  for (auto &GI : M.ifuncs())
374  if (auto *F = dyn_cast<Function>(GI.getResolver()->stripPointerCasts()))
375  ResolverIFuncs.push_back({&GI, F});
376  }
377 
378  ~ScopedSaveAliaseesAndUsed() {
379  appendToUsed(M, Used);
380  appendToCompilerUsed(M, CompilerUsed);
381 
382  for (auto P : FunctionAliases)
383  P.first->setAliasee(
384  ConstantExpr::getBitCast(P.second, P.first->getType()));
385 
386  for (auto P : ResolverIFuncs) {
387  // This does not preserve pointer casts that may have been stripped by the
388  // constructor, but the resolver's type is different from that of the
389  // ifunc anyway.
390  P.first->setResolver(P.second);
391  }
392  }
393 };
394 
395 class LowerTypeTestsModule {
396  Module &M;
397 
398  ModuleSummaryIndex *ExportSummary;
399  const ModuleSummaryIndex *ImportSummary;
400  // Set when the client has invoked this to simply drop all type test assume
401  // sequences.
402  bool DropTypeTests;
403 
404  Triple::ArchType Arch;
405  Triple::OSType OS;
406  Triple::ObjectFormatType ObjectFormat;
407 
408  IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
409  IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
410  PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
411  ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0);
412  IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
414  IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
415  IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
416 
417  // Indirect function call index assignment counter for WebAssembly
418  uint64_t IndirectIndex = 1;
419 
420  // Mapping from type identifiers to the call sites that test them, as well as
421  // whether the type identifier needs to be exported to ThinLTO backends as
422  // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
423  struct TypeIdUserInfo {
424  std::vector<CallInst *> CallSites;
425  bool IsExported = false;
426  };
428 
429  /// This structure describes how to lower type tests for a particular type
430  /// identifier. It is either built directly from the global analysis (during
431  /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
432  /// identifier summaries and external symbol references (in ThinLTO backends).
433  struct TypeIdLowering {
435 
436  /// All except Unsat: the start address within the combined global.
437  Constant *OffsetedGlobal;
438 
439  /// ByteArray, Inline, AllOnes: log2 of the required global alignment
440  /// relative to the start address.
441  Constant *AlignLog2;
442 
443  /// ByteArray, Inline, AllOnes: one less than the size of the memory region
444  /// covering members of this type identifier as a multiple of 2^AlignLog2.
445  Constant *SizeM1;
446 
447  /// ByteArray: the byte array to test the address against.
448  Constant *TheByteArray;
449 
450  /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
451  Constant *BitMask;
452 
453  /// Inline: the bit mask to test the address against.
454  Constant *InlineBits;
455  };
456 
457  std::vector<ByteArrayInfo> ByteArrayInfos;
458 
459  Function *WeakInitializerFn = nullptr;
460 
461  bool shouldExportConstantsAsAbsoluteSymbols();
462  uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
463  TypeIdLowering importTypeId(StringRef TypeId);
464  void importTypeTest(CallInst *CI);
465  void importFunction(Function *F, bool isJumpTableCanonical,
466  std::vector<GlobalAlias *> &AliasesToErase);
467 
468  BitSetInfo
469  buildBitSet(Metadata *TypeId,
470  const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
471  ByteArrayInfo *createByteArray(BitSetInfo &BSI);
472  void allocateByteArrays();
473  Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
474  Value *BitOffset);
475  void lowerTypeTestCalls(
476  ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
477  const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
478  Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
479  const TypeIdLowering &TIL);
480 
481  void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
483  unsigned getJumpTableEntrySize();
484  Type *getJumpTableEntryType();
485  void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
486  Triple::ArchType JumpTableArch,
487  SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
488  void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
489  void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
490  ArrayRef<GlobalTypeMember *> Functions);
491  void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
492  ArrayRef<GlobalTypeMember *> Functions);
493  void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
494  ArrayRef<GlobalTypeMember *> Functions);
495  void
496  buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
498  ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
499 
500  void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT,
501  bool IsJumpTableCanonical);
502  void moveInitializerToModuleConstructor(GlobalVariable *GV);
503  void findGlobalVariableUsersOf(Constant *C,
505 
506  void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
507 
508  /// replaceCfiUses - Go through the uses list for this definition
509  /// and make each use point to "V" instead of "this" when the use is outside
510  /// the block. 'This's use list is expected to have at least one element.
511  /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
512  /// uses.
513  void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical);
514 
515  /// replaceDirectCalls - Go through the uses list for this definition and
516  /// replace each use, which is a direct function call.
517  void replaceDirectCalls(Value *Old, Value *New);
518 
519 public:
520  LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary,
521  const ModuleSummaryIndex *ImportSummary,
522  bool DropTypeTests);
523 
524  bool lower();
525 
526  // Lower the module using the action and summary passed as command line
527  // arguments. For testing purposes only.
528  static bool runForTesting(Module &M);
529 };
530 
531 struct LowerTypeTests : public ModulePass {
532  static char ID;
533 
534  bool UseCommandLine = false;
535 
536  ModuleSummaryIndex *ExportSummary;
537  const ModuleSummaryIndex *ImportSummary;
538  bool DropTypeTests;
539 
540  LowerTypeTests() : ModulePass(ID), UseCommandLine(true) {
542  }
543 
544  LowerTypeTests(ModuleSummaryIndex *ExportSummary,
545  const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
546  : ModulePass(ID), ExportSummary(ExportSummary),
547  ImportSummary(ImportSummary),
548  DropTypeTests(DropTypeTests || ClDropTypeTests) {
550  }
551 
552  bool runOnModule(Module &M) override {
553  if (UseCommandLine)
554  return LowerTypeTestsModule::runForTesting(M);
555  return LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
556  .lower();
557  }
558 };
559 
560 } // end anonymous namespace
561 
562 char LowerTypeTests::ID = 0;
563 
564 INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,
565  false)
566 
567 ModulePass *
569  const ModuleSummaryIndex *ImportSummary,
570  bool DropTypeTests) {
571  return new LowerTypeTests(ExportSummary, ImportSummary, DropTypeTests);
572 }
573 
574 /// Build a bit set for TypeId using the object layouts in
575 /// GlobalLayout.
576 BitSetInfo LowerTypeTestsModule::buildBitSet(
577  Metadata *TypeId,
578  const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
579  BitSetBuilder BSB;
580 
581  // Compute the byte offset of each address associated with this type
582  // identifier.
583  for (auto &GlobalAndOffset : GlobalLayout) {
584  for (MDNode *Type : GlobalAndOffset.first->types()) {
585  if (Type->getOperand(1) != TypeId)
586  continue;
587  uint64_t Offset =
588  cast<ConstantInt>(
589  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
590  ->getZExtValue();
591  BSB.addOffset(GlobalAndOffset.second + Offset);
592  }
593  }
594 
595  return BSB.build();
596 }
597 
598 /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
599 /// Bits. This pattern matches to the bt instruction on x86.
601  Value *BitOffset) {
602  auto BitsType = cast<IntegerType>(Bits->getType());
603  unsigned BitWidth = BitsType->getBitWidth();
604 
605  BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
606  Value *BitIndex =
607  B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
608  Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
609  Value *MaskedBits = B.CreateAnd(Bits, BitMask);
610  return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
611 }
612 
613 ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
614  // Create globals to stand in for byte arrays and masks. These never actually
615  // get initialized, we RAUW and erase them later in allocateByteArrays() once
616  // we know the offset and mask to use.
617  auto ByteArrayGlobal = new GlobalVariable(
618  M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
619  auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
620  GlobalValue::PrivateLinkage, nullptr);
621 
622  ByteArrayInfos.emplace_back();
623  ByteArrayInfo *BAI = &ByteArrayInfos.back();
624 
625  BAI->Bits = BSI.Bits;
626  BAI->BitSize = BSI.BitSize;
627  BAI->ByteArray = ByteArrayGlobal;
628  BAI->MaskGlobal = MaskGlobal;
629  return BAI;
630 }
631 
632 void LowerTypeTestsModule::allocateByteArrays() {
633  llvm::stable_sort(ByteArrayInfos,
634  [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
635  return BAI1.BitSize > BAI2.BitSize;
636  });
637 
638  std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
639 
640  ByteArrayBuilder BAB;
641  for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
642  ByteArrayInfo *BAI = &ByteArrayInfos[I];
643 
644  uint8_t Mask;
645  BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
646 
647  BAI->MaskGlobal->replaceAllUsesWith(
648  ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
649  BAI->MaskGlobal->eraseFromParent();
650  if (BAI->MaskPtr)
651  *BAI->MaskPtr = Mask;
652  }
653 
654  Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
655  auto ByteArray =
656  new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
657  GlobalValue::PrivateLinkage, ByteArrayConst);
658 
659  for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
660  ByteArrayInfo *BAI = &ByteArrayInfos[I];
661 
662  Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
663  ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
665  ByteArrayConst->getType(), ByteArray, Idxs);
666 
667  // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
668  // that the pc-relative displacement is folded into the lea instead of the
669  // test instruction getting another displacement.
671  Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
672  BAI->ByteArray->replaceAllUsesWith(Alias);
673  BAI->ByteArray->eraseFromParent();
674  }
675 
676  ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
677  BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
678  BAB.BitAllocs[6] + BAB.BitAllocs[7];
679  ByteArraySizeBytes = BAB.Bytes.size();
680 }
681 
682 /// Build a test that bit BitOffset is set in the type identifier that was
683 /// lowered to TIL, which must be either an Inline or a ByteArray.
684 Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
685  const TypeIdLowering &TIL,
686  Value *BitOffset) {
687  if (TIL.TheKind == TypeTestResolution::Inline) {
688  // If the bit set is sufficiently small, we can avoid a load by bit testing
689  // a constant.
690  return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
691  } else {
692  Constant *ByteArray = TIL.TheByteArray;
693  if (AvoidReuse && !ImportSummary) {
694  // Each use of the byte array uses a different alias. This makes the
695  // backend less likely to reuse previously computed byte array addresses,
696  // improving the security of the CFI mechanism based on this pass.
697  // This won't work when importing because TheByteArray is external.
698  ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage,
699  "bits_use", ByteArray, &M);
700  }
701 
702  Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
703  Value *Byte = B.CreateLoad(Int8Ty, ByteAddr);
704 
705  Value *ByteAndMask =
706  B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
707  return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
708  }
709 }
710 
711 static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
712  Value *V, uint64_t COffset) {
713  if (auto GV = dyn_cast<GlobalObject>(V)) {
715  GV->getMetadata(LLVMContext::MD_type, Types);
716  for (MDNode *Type : Types) {
717  if (Type->getOperand(1) != TypeId)
718  continue;
719  uint64_t Offset =
720  cast<ConstantInt>(
721  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
722  ->getZExtValue();
723  if (COffset == Offset)
724  return true;
725  }
726  return false;
727  }
728 
729  if (auto GEP = dyn_cast<GEPOperator>(V)) {
730  APInt APOffset(DL.getPointerSizeInBits(0), 0);
731  bool Result = GEP->accumulateConstantOffset(DL, APOffset);
732  if (!Result)
733  return false;
734  COffset += APOffset.getZExtValue();
735  return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
736  }
737 
738  if (auto Op = dyn_cast<Operator>(V)) {
739  if (Op->getOpcode() == Instruction::BitCast)
740  return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
741 
742  if (Op->getOpcode() == Instruction::Select)
743  return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
744  isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
745  }
746 
747  return false;
748 }
749 
750 /// Lower a llvm.type.test call to its implementation. Returns the value to
751 /// replace the call with.
752 Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
753  const TypeIdLowering &TIL) {
754  // Delay lowering if the resolution is currently unknown.
755  if (TIL.TheKind == TypeTestResolution::Unknown)
756  return nullptr;
757  if (TIL.TheKind == TypeTestResolution::Unsat)
758  return ConstantInt::getFalse(M.getContext());
759 
760  Value *Ptr = CI->getArgOperand(0);
761  const DataLayout &DL = M.getDataLayout();
762  if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
763  return ConstantInt::getTrue(M.getContext());
764 
765  BasicBlock *InitialBB = CI->getParent();
766 
767  IRBuilder<> B(CI);
768 
769  Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
770 
771  Constant *OffsetedGlobalAsInt =
772  ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
773  if (TIL.TheKind == TypeTestResolution::Single)
774  return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
775 
776  Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
777 
778  // We need to check that the offset both falls within our range and is
779  // suitably aligned. We can check both properties at the same time by
780  // performing a right rotate by log2(alignment) followed by an integer
781  // comparison against the bitset size. The rotate will move the lower
782  // order bits that need to be zero into the higher order bits of the
783  // result, causing the comparison to fail if they are nonzero. The rotate
784  // also conveniently gives us a bit offset to use during the load from
785  // the bitset.
786  Value *OffsetSHR =
787  B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
788  Value *OffsetSHL = B.CreateShl(
789  PtrOffset, ConstantExpr::getZExt(
791  ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
792  TIL.AlignLog2),
793  IntPtrTy));
794  Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
795 
796  Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1);
797 
798  // If the bit set is all ones, testing against it is unnecessary.
799  if (TIL.TheKind == TypeTestResolution::AllOnes)
800  return OffsetInRange;
801 
802  // See if the intrinsic is used in the following common pattern:
803  // br(llvm.type.test(...), thenbb, elsebb)
804  // where nothing happens between the type test and the br.
805  // If so, create slightly simpler IR.
806  if (CI->hasOneUse())
807  if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin()))
808  if (CI->getNextNode() == Br) {
809  BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator());
810  BasicBlock *Else = Br->getSuccessor(1);
811  BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange);
812  NewBr->setMetadata(LLVMContext::MD_prof,
813  Br->getMetadata(LLVMContext::MD_prof));
814  ReplaceInstWithInst(InitialBB->getTerminator(), NewBr);
815 
816  // Update phis in Else resulting from InitialBB being split
817  for (auto &Phi : Else->phis())
818  Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB);
819 
820  IRBuilder<> ThenB(CI);
821  return createBitSetTest(ThenB, TIL, BitOffset);
822  }
823 
824  IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false));
825 
826  // Now that we know that the offset is in range and aligned, load the
827  // appropriate bit from the bitset.
828  Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
829 
830  // The value we want is 0 if we came directly from the initial block
831  // (having failed the range or alignment checks), or the loaded bit if
832  // we came from the block in which we loaded it.
833  B.SetInsertPoint(CI);
834  PHINode *P = B.CreatePHI(Int1Ty, 2);
835  P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
836  P->addIncoming(Bit, ThenB.GetInsertBlock());
837  return P;
838 }
839 
840 /// Given a disjoint set of type identifiers and globals, lay out the globals,
841 /// build the bit sets and lower the llvm.type.test calls.
842 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
844  // Build a new global with the combined contents of the referenced globals.
845  // This global is a struct whose even-indexed elements contain the original
846  // contents of the referenced globals and whose odd-indexed elements contain
847  // any padding required to align the next element to the next power of 2 plus
848  // any additional padding required to meet its alignment requirements.
849  std::vector<Constant *> GlobalInits;
850  const DataLayout &DL = M.getDataLayout();
852  Align MaxAlign;
853  uint64_t CurOffset = 0;
854  uint64_t DesiredPadding = 0;
855  for (GlobalTypeMember *G : Globals) {
856  auto *GV = cast<GlobalVariable>(G->getGlobal());
857  Align Alignment =
858  DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType());
859  MaxAlign = std::max(MaxAlign, Alignment);
860  uint64_t GVOffset = alignTo(CurOffset + DesiredPadding, Alignment);
861  GlobalLayout[G] = GVOffset;
862  if (GVOffset != 0) {
863  uint64_t Padding = GVOffset - CurOffset;
864  GlobalInits.push_back(
865  ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding)));
866  }
867 
868  GlobalInits.push_back(GV->getInitializer());
869  uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
870  CurOffset = GVOffset + InitSize;
871 
872  // Compute the amount of padding that we'd like for the next element.
873  DesiredPadding = NextPowerOf2(InitSize - 1) - InitSize;
874 
875  // Experiments of different caps with Chromium on both x64 and ARM64
876  // have shown that the 32-byte cap generates the smallest binary on
877  // both platforms while different caps yield similar performance.
878  // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
879  if (DesiredPadding > 32)
880  DesiredPadding = alignTo(InitSize, 32) - InitSize;
881  }
882 
883  Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
884  auto *CombinedGlobal =
885  new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
886  GlobalValue::PrivateLinkage, NewInit);
887  CombinedGlobal->setAlignment(MaxAlign);
888 
889  StructType *NewTy = cast<StructType>(NewInit->getType());
890  lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
891 
892  // Build aliases pointing to offsets into the combined global for each
893  // global from which we built the combined global, and replace references
894  // to the original globals with references to the aliases.
895  for (unsigned I = 0; I != Globals.size(); ++I) {
896  GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
897 
898  // Multiply by 2 to account for padding elements.
899  Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
900  ConstantInt::get(Int32Ty, I * 2)};
901  Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
902  NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
903  assert(GV->getType()->getAddressSpace() == 0);
904  GlobalAlias *GAlias =
905  GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(),
906  "", CombinedGlobalElemPtr, &M);
907  GAlias->setVisibility(GV->getVisibility());
908  GAlias->takeName(GV);
909  GV->replaceAllUsesWith(GAlias);
910  GV->eraseFromParent();
911  }
912 }
913 
914 bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
915  return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
916  ObjectFormat == Triple::ELF;
917 }
918 
919 /// Export the given type identifier so that ThinLTO backends may import it.
920 /// Type identifiers are exported by adding coarse-grained information about how
921 /// to test the type identifier to the summary, and creating symbols in the
922 /// object file (aliases and absolute symbols) containing fine-grained
923 /// information about the type identifier.
924 ///
925 /// Returns a pointer to the location in which to store the bitmask, if
926 /// applicable.
927 uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
928  const TypeIdLowering &TIL) {
929  TypeTestResolution &TTRes =
930  ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
931  TTRes.TheKind = TIL.TheKind;
932 
933  auto ExportGlobal = [&](StringRef Name, Constant *C) {
934  GlobalAlias *GA =
936  "__typeid_" + TypeId + "_" + Name, C, &M);
938  };
939 
940  auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
941  if (shouldExportConstantsAsAbsoluteSymbols())
942  ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy));
943  else
944  Storage = cast<ConstantInt>(C)->getZExtValue();
945  };
946 
947  if (TIL.TheKind != TypeTestResolution::Unsat)
948  ExportGlobal("global_addr", TIL.OffsetedGlobal);
949 
950  if (TIL.TheKind == TypeTestResolution::ByteArray ||
951  TIL.TheKind == TypeTestResolution::Inline ||
952  TIL.TheKind == TypeTestResolution::AllOnes) {
953  ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
954  ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
955 
956  uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
957  if (TIL.TheKind == TypeTestResolution::Inline)
958  TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
959  else
960  TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
961  }
962 
963  if (TIL.TheKind == TypeTestResolution::ByteArray) {
964  ExportGlobal("byte_array", TIL.TheByteArray);
965  if (shouldExportConstantsAsAbsoluteSymbols())
966  ExportGlobal("bit_mask", TIL.BitMask);
967  else
968  return &TTRes.BitMask;
969  }
970 
971  if (TIL.TheKind == TypeTestResolution::Inline)
972  ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
973 
974  return nullptr;
975 }
976 
977 LowerTypeTestsModule::TypeIdLowering
978 LowerTypeTestsModule::importTypeId(StringRef TypeId) {
979  const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
980  if (!TidSummary)
981  return {}; // Unsat: no globals match this type id.
982  const TypeTestResolution &TTRes = TidSummary->TTRes;
983 
984  TypeIdLowering TIL;
985  TIL.TheKind = TTRes.TheKind;
986 
987  auto ImportGlobal = [&](StringRef Name) {
988  // Give the global a type of length 0 so that it is not assumed not to alias
989  // with any other global.
990  Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(),
991  Int8Arr0Ty);
992  if (auto *GV = dyn_cast<GlobalVariable>(C))
994  C = ConstantExpr::getBitCast(C, Int8PtrTy);
995  return C;
996  };
997 
998  auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
999  Type *Ty) {
1000  if (!shouldExportConstantsAsAbsoluteSymbols()) {
1001  Constant *C =
1002  ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const);
1003  if (!isa<IntegerType>(Ty))
1004  C = ConstantExpr::getIntToPtr(C, Ty);
1005  return C;
1006  }
1007 
1008  Constant *C = ImportGlobal(Name);
1009  auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
1010  if (isa<IntegerType>(Ty))
1011  C = ConstantExpr::getPtrToInt(C, Ty);
1012  if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
1013  return C;
1014 
1015  auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1016  auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1017  auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1018  GV->setMetadata(LLVMContext::MD_absolute_symbol,
1019  MDNode::get(M.getContext(), {MinC, MaxC}));
1020  };
1021  if (AbsWidth == IntPtrTy->getBitWidth())
1022  SetAbsRange(~0ull, ~0ull); // Full set.
1023  else
1024  SetAbsRange(0, 1ull << AbsWidth);
1025  return C;
1026  };
1027 
1028  if (TIL.TheKind != TypeTestResolution::Unsat)
1029  TIL.OffsetedGlobal = ImportGlobal("global_addr");
1030 
1031  if (TIL.TheKind == TypeTestResolution::ByteArray ||
1032  TIL.TheKind == TypeTestResolution::Inline ||
1033  TIL.TheKind == TypeTestResolution::AllOnes) {
1034  TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty);
1035  TIL.SizeM1 =
1036  ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
1037  }
1038 
1039  if (TIL.TheKind == TypeTestResolution::ByteArray) {
1040  TIL.TheByteArray = ImportGlobal("byte_array");
1041  TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy);
1042  }
1043 
1044  if (TIL.TheKind == TypeTestResolution::Inline)
1045  TIL.InlineBits = ImportConstant(
1046  "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
1047  TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
1048 
1049  return TIL;
1050 }
1051 
1052 void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
1053  auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
1054  if (!TypeIdMDVal)
1055  report_fatal_error("Second argument of llvm.type.test must be metadata");
1056 
1057  auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
1058  // If this is a local unpromoted type, which doesn't have a metadata string,
1059  // treat as Unknown and delay lowering, so that we can still utilize it for
1060  // later optimizations.
1061  if (!TypeIdStr)
1062  return;
1063 
1064  TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
1065  Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
1066  if (Lowered) {
1067  CI->replaceAllUsesWith(Lowered);
1068  CI->eraseFromParent();
1069  }
1070 }
1071 
1072 // ThinLTO backend: the function F has a jump table entry; update this module
1073 // accordingly. isJumpTableCanonical describes the type of the jump table entry.
1074 void LowerTypeTestsModule::importFunction(
1076  std::vector<GlobalAlias *> &AliasesToErase) {
1077  assert(F->getType()->getAddressSpace() == 0);
1078 
1079  GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1080  std::string Name = std::string(F->getName());
1081 
1082  if (F->isDeclarationForLinker() && isJumpTableCanonical) {
1083  // Non-dso_local functions may be overriden at run time,
1084  // don't short curcuit them
1085  if (F->isDSOLocal()) {
1086  Function *RealF = Function::Create(F->getFunctionType(),
1088  F->getAddressSpace(),
1089  Name + ".cfi", &M);
1091  replaceDirectCalls(F, RealF);
1092  }
1093  return;
1094  }
1095 
1096  Function *FDecl;
1097  if (!isJumpTableCanonical) {
1098  // Either a declaration of an external function or a reference to a locally
1099  // defined jump table.
1100  FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1101  F->getAddressSpace(), Name + ".cfi_jt", &M);
1103  } else {
1104  F->setName(Name + ".cfi");
1105  F->setLinkage(GlobalValue::ExternalLinkage);
1106  FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1107  F->getAddressSpace(), Name, &M);
1108  FDecl->setVisibility(Visibility);
1109  Visibility = GlobalValue::HiddenVisibility;
1110 
1111  // Delete aliases pointing to this function, they'll be re-created in the
1112  // merged output. Don't do it yet though because ScopedSaveAliaseesAndUsed
1113  // will want to reset the aliasees first.
1114  for (auto &U : F->uses()) {
1115  if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
1116  Function *AliasDecl = Function::Create(
1117  F->getFunctionType(), GlobalValue::ExternalLinkage,
1118  F->getAddressSpace(), "", &M);
1119  AliasDecl->takeName(A);
1120  A->replaceAllUsesWith(AliasDecl);
1121  AliasesToErase.push_back(A);
1122  }
1123  }
1124  }
1125 
1126  if (F->hasExternalWeakLinkage())
1127  replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isJumpTableCanonical);
1128  else
1129  replaceCfiUses(F, FDecl, isJumpTableCanonical);
1130 
1131  // Set visibility late because it's used in replaceCfiUses() to determine
1132  // whether uses need to to be replaced.
1133  F->setVisibility(Visibility);
1134 }
1135 
1136 void LowerTypeTestsModule::lowerTypeTestCalls(
1137  ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1138  const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1139  CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
1140 
1141  // For each type identifier in this disjoint set...
1142  for (Metadata *TypeId : TypeIds) {
1143  // Build the bitset.
1144  BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
1145  LLVM_DEBUG({
1146  if (auto MDS = dyn_cast<MDString>(TypeId))
1147  dbgs() << MDS->getString() << ": ";
1148  else
1149  dbgs() << "<unnamed>: ";
1150  BSI.print(dbgs());
1151  });
1152 
1153  ByteArrayInfo *BAI = nullptr;
1154  TypeIdLowering TIL;
1155  TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
1156  Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
1157  TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
1158  TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1);
1159  if (BSI.isAllOnes()) {
1160  TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1162  } else if (BSI.BitSize <= 64) {
1163  TIL.TheKind = TypeTestResolution::Inline;
1164  uint64_t InlineBits = 0;
1165  for (auto Bit : BSI.Bits)
1166  InlineBits |= uint64_t(1) << Bit;
1167  if (InlineBits == 0)
1168  TIL.TheKind = TypeTestResolution::Unsat;
1169  else
1170  TIL.InlineBits = ConstantInt::get(
1171  (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
1172  } else {
1173  TIL.TheKind = TypeTestResolution::ByteArray;
1174  ++NumByteArraysCreated;
1175  BAI = createByteArray(BSI);
1176  TIL.TheByteArray = BAI->ByteArray;
1177  TIL.BitMask = BAI->MaskGlobal;
1178  }
1179 
1180  TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1181 
1182  if (TIUI.IsExported) {
1183  uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
1184  if (BAI)
1185  BAI->MaskPtr = MaskPtr;
1186  }
1187 
1188  // Lower each call to llvm.type.test for this type identifier.
1189  for (CallInst *CI : TIUI.CallSites) {
1190  ++NumTypeTestCallsLowered;
1191  Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1192  if (Lowered) {
1193  CI->replaceAllUsesWith(Lowered);
1194  CI->eraseFromParent();
1195  }
1196  }
1197  }
1198 }
1199 
1200 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1201  if (Type->getNumOperands() != 2)
1202  report_fatal_error("All operands of type metadata must have 2 elements");
1203 
1204  if (GO->isThreadLocal())
1205  report_fatal_error("Bit set element may not be thread-local");
1206  if (isa<GlobalVariable>(GO) && GO->hasSection())
1208  "A member of a type identifier may not have an explicit section");
1209 
1210  // FIXME: We previously checked that global var member of a type identifier
1211  // must be a definition, but the IR linker may leave type metadata on
1212  // declarations. We should restore this check after fixing PR31759.
1213 
1214  auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
1215  if (!OffsetConstMD)
1216  report_fatal_error("Type offset must be a constant");
1217  auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
1218  if (!OffsetInt)
1219  report_fatal_error("Type offset must be an integer constant");
1220 }
1221 
1222 static const unsigned kX86JumpTableEntrySize = 8;
1223 static const unsigned kARMJumpTableEntrySize = 4;
1224 static const unsigned kARMBTIJumpTableEntrySize = 8;
1225 
1226 unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
1227  switch (Arch) {
1228  case Triple::x86:
1229  case Triple::x86_64:
1230  return kX86JumpTableEntrySize;
1231  case Triple::arm:
1232  case Triple::thumb:
1233  return kARMJumpTableEntrySize;
1234  case Triple::aarch64:
1235  if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1236  M.getModuleFlag("branch-target-enforcement")))
1237  if (BTE->getZExtValue())
1239  return kARMJumpTableEntrySize;
1240  default:
1241  report_fatal_error("Unsupported architecture for jump tables");
1242  }
1243 }
1244 
1245 // Create a jump table entry for the target. This consists of an instruction
1246 // sequence containing a relative branch to Dest. Appends inline asm text,
1247 // constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
1248 void LowerTypeTestsModule::createJumpTableEntry(
1249  raw_ostream &AsmOS, raw_ostream &ConstraintOS,
1250  Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs,
1251  Function *Dest) {
1252  unsigned ArgIndex = AsmArgs.size();
1253 
1254  if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1255  AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
1256  AsmOS << "int3\nint3\nint3\n";
1257  } else if (JumpTableArch == Triple::arm) {
1258  AsmOS << "b $" << ArgIndex << "\n";
1259  } else if (JumpTableArch == Triple::aarch64) {
1260  if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1261  Dest->getParent()->getModuleFlag("branch-target-enforcement")))
1262  if (BTE->getZExtValue())
1263  AsmOS << "bti c\n";
1264  AsmOS << "b $" << ArgIndex << "\n";
1265  } else if (JumpTableArch == Triple::thumb) {
1266  AsmOS << "b.w $" << ArgIndex << "\n";
1267  } else {
1268  report_fatal_error("Unsupported architecture for jump tables");
1269  }
1270 
1271  ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
1272  AsmArgs.push_back(Dest);
1273 }
1274 
1275 Type *LowerTypeTestsModule::getJumpTableEntryType() {
1276  return ArrayType::get(Int8Ty, getJumpTableEntrySize());
1277 }
1278 
1279 /// Given a disjoint set of type identifiers and functions, build the bit sets
1280 /// and lower the llvm.type.test calls, architecture dependently.
1281 void LowerTypeTestsModule::buildBitSetsFromFunctions(
1283  if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1284  Arch == Triple::thumb || Arch == Triple::aarch64)
1285  buildBitSetsFromFunctionsNative(TypeIds, Functions);
1286  else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1287  buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1288  else
1289  report_fatal_error("Unsupported architecture for jump tables");
1290 }
1291 
1292 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1293  GlobalVariable *GV) {
1294  if (WeakInitializerFn == nullptr) {
1295  WeakInitializerFn = Function::Create(
1296  FunctionType::get(Type::getVoidTy(M.getContext()),
1297  /* IsVarArg */ false),
1299  M.getDataLayout().getProgramAddressSpace(),
1300  "__cfi_global_var_init", &M);
1301  BasicBlock *BB =
1302  BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
1303  ReturnInst::Create(M.getContext(), BB);
1304  WeakInitializerFn->setSection(
1305  ObjectFormat == Triple::MachO
1306  ? "__TEXT,__StaticInit,regular,pure_instructions"
1307  : ".text.startup");
1308  // This code is equivalent to relocation application, and should run at the
1309  // earliest possible time (i.e. with the highest priority).
1310  appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
1311  }
1312 
1313  IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1314  GV->setConstant(false);
1315  IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlign());
1317 }
1318 
1319 void LowerTypeTestsModule::findGlobalVariableUsersOf(
1321  for (auto *U : C->users()){
1322  if (auto *GV = dyn_cast<GlobalVariable>(U))
1323  Out.insert(GV);
1324  else if (auto *C2 = dyn_cast<Constant>(U))
1325  findGlobalVariableUsersOf(C2, Out);
1326  }
1327 }
1328 
1329 // Replace all uses of F with (F ? JT : 0).
1330 void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1331  Function *F, Constant *JT, bool IsJumpTableCanonical) {
1332  // The target expression can not appear in a constant initializer on most
1333  // (all?) targets. Switch to a runtime initializer.
1334  SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
1335  findGlobalVariableUsersOf(F, GlobalVarUsers);
1336  for (auto GV : GlobalVarUsers)
1337  moveInitializerToModuleConstructor(GV);
1338 
1339  // Can not RAUW F with an expression that uses F. Replace with a temporary
1340  // placeholder first.
1341  Function *PlaceholderFn =
1342  Function::Create(cast<FunctionType>(F->getValueType()),
1344  F->getAddressSpace(), "", &M);
1345  replaceCfiUses(F, PlaceholderFn, IsJumpTableCanonical);
1346 
1349  Constant::getNullValue(F->getType())),
1350  JT, Constant::getNullValue(F->getType()));
1351  PlaceholderFn->replaceAllUsesWith(Target);
1352  PlaceholderFn->eraseFromParent();
1353 }
1354 
1355 static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1356  Attribute TFAttr = F->getFnAttribute("target-features");
1357  if (TFAttr.isValid()) {
1358  SmallVector<StringRef, 6> Features;
1359  TFAttr.getValueAsString().split(Features, ',');
1360  for (StringRef Feature : Features) {
1361  if (Feature == "-thumb-mode")
1362  return false;
1363  else if (Feature == "+thumb-mode")
1364  return true;
1365  }
1366  }
1367 
1368  return ModuleArch == Triple::thumb;
1369 }
1370 
1371 // Each jump table must be either ARM or Thumb as a whole for the bit-test math
1372 // to work. Pick one that matches the majority of members to minimize interop
1373 // veneers inserted by the linker.
1374 static Triple::ArchType
1376  Triple::ArchType ModuleArch) {
1377  if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb)
1378  return ModuleArch;
1379 
1380  unsigned ArmCount = 0, ThumbCount = 0;
1381  for (const auto GTM : Functions) {
1382  if (!GTM->isJumpTableCanonical()) {
1383  // PLT stubs are always ARM.
1384  // FIXME: This is the wrong heuristic for non-canonical jump tables.
1385  ++ArmCount;
1386  continue;
1387  }
1388 
1389  Function *F = cast<Function>(GTM->getGlobal());
1390  ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount);
1391  }
1392 
1393  return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1394 }
1395 
1396 void LowerTypeTestsModule::createJumpTable(
1397  Function *F, ArrayRef<GlobalTypeMember *> Functions) {
1398  std::string AsmStr, ConstraintStr;
1399  raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
1400  SmallVector<Value *, 16> AsmArgs;
1401  AsmArgs.reserve(Functions.size() * 2);
1402 
1403  Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch);
1404 
1405  for (unsigned I = 0; I != Functions.size(); ++I)
1406  createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
1407  cast<Function>(Functions[I]->getGlobal()));
1408 
1409  // Align the whole table by entry size.
1410  F->setAlignment(Align(getJumpTableEntrySize()));
1411  // Skip prologue.
1412  // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
1413  // Luckily, this function does not get any prologue even without the
1414  // attribute.
1415  if (OS != Triple::Win32)
1416  F->addFnAttr(Attribute::Naked);
1417  if (JumpTableArch == Triple::arm)
1418  F->addFnAttr("target-features", "-thumb-mode");
1419  if (JumpTableArch == Triple::thumb) {
1420  F->addFnAttr("target-features", "+thumb-mode");
1421  // Thumb jump table assembly needs Thumb2. The following attribute is added
1422  // by Clang for -march=armv7.
1423  F->addFnAttr("target-cpu", "cortex-a8");
1424  }
1425  if (JumpTableArch == Triple::aarch64) {
1426  F->addFnAttr("branch-target-enforcement", "false");
1427  F->addFnAttr("sign-return-address", "none");
1428  }
1429  // Make sure we don't emit .eh_frame for this function.
1430  F->addFnAttr(Attribute::NoUnwind);
1431 
1432  BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
1433  IRBuilder<> IRB(BB);
1434 
1435  SmallVector<Type *, 16> ArgTypes;
1436  ArgTypes.reserve(AsmArgs.size());
1437  for (const auto &Arg : AsmArgs)
1438  ArgTypes.push_back(Arg->getType());
1439  InlineAsm *JumpTableAsm =
1440  InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
1441  AsmOS.str(), ConstraintOS.str(),
1442  /*hasSideEffects=*/true);
1443 
1444  IRB.CreateCall(JumpTableAsm, AsmArgs);
1445  IRB.CreateUnreachable();
1446 }
1447 
1448 /// Given a disjoint set of type identifiers and functions, build a jump table
1449 /// for the functions, build the bit sets and lower the llvm.type.test calls.
1450 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1452  // Unlike the global bitset builder, the function bitset builder cannot
1453  // re-arrange functions in a particular order and base its calculations on the
1454  // layout of the functions' entry points, as we have no idea how large a
1455  // particular function will end up being (the size could even depend on what
1456  // this pass does!) Instead, we build a jump table, which is a block of code
1457  // consisting of one branch instruction for each of the functions in the bit
1458  // set that branches to the target function, and redirect any taken function
1459  // addresses to the corresponding jump table entry. In the object file's
1460  // symbol table, the symbols for the target functions also refer to the jump
1461  // table entries, so that addresses taken outside the module will pass any
1462  // verification done inside the module.
1463  //
1464  // In more concrete terms, suppose we have three functions f, g, h which are
1465  // of the same type, and a function foo that returns their addresses:
1466  //
1467  // f:
1468  // mov 0, %eax
1469  // ret
1470  //
1471  // g:
1472  // mov 1, %eax
1473  // ret
1474  //
1475  // h:
1476  // mov 2, %eax
1477  // ret
1478  //
1479  // foo:
1480  // mov f, %eax
1481  // mov g, %edx
1482  // mov h, %ecx
1483  // ret
1484  //
1485  // We output the jump table as module-level inline asm string. The end result
1486  // will (conceptually) look like this:
1487  //
1488  // f = .cfi.jumptable
1489  // g = .cfi.jumptable + 4
1490  // h = .cfi.jumptable + 8
1491  // .cfi.jumptable:
1492  // jmp f.cfi ; 5 bytes
1493  // int3 ; 1 byte
1494  // int3 ; 1 byte
1495  // int3 ; 1 byte
1496  // jmp g.cfi ; 5 bytes
1497  // int3 ; 1 byte
1498  // int3 ; 1 byte
1499  // int3 ; 1 byte
1500  // jmp h.cfi ; 5 bytes
1501  // int3 ; 1 byte
1502  // int3 ; 1 byte
1503  // int3 ; 1 byte
1504  //
1505  // f.cfi:
1506  // mov 0, %eax
1507  // ret
1508  //
1509  // g.cfi:
1510  // mov 1, %eax
1511  // ret
1512  //
1513  // h.cfi:
1514  // mov 2, %eax
1515  // ret
1516  //
1517  // foo:
1518  // mov f, %eax
1519  // mov g, %edx
1520  // mov h, %ecx
1521  // ret
1522  //
1523  // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1524  // normal case the check can be carried out using the same kind of simple
1525  // arithmetic that we normally use for globals.
1526 
1527  // FIXME: find a better way to represent the jumptable in the IR.
1528  assert(!Functions.empty());
1529 
1530  // Build a simple layout based on the regular layout of jump tables.
1532  unsigned EntrySize = getJumpTableEntrySize();
1533  for (unsigned I = 0; I != Functions.size(); ++I)
1534  GlobalLayout[Functions[I]] = I * EntrySize;
1535 
1536  Function *JumpTableFn =
1538  /* IsVarArg */ false),
1540  M.getDataLayout().getProgramAddressSpace(),
1541  ".cfi.jumptable", &M);
1543  ArrayType::get(getJumpTableEntryType(), Functions.size());
1544  auto JumpTable =
1545  ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
1546 
1547  lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
1548 
1549  {
1550  ScopedSaveAliaseesAndUsed S(M);
1551 
1552  // Build aliases pointing to offsets into the jump table, and replace
1553  // references to the original functions with references to the aliases.
1554  for (unsigned I = 0; I != Functions.size(); ++I) {
1555  Function *F = cast<Function>(Functions[I]->getGlobal());
1556  bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
1557 
1558  Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
1562  ConstantInt::get(IntPtrTy, I)}),
1563  F->getType());
1564 
1565  const bool IsExported = Functions[I]->isExported();
1566  if (!IsJumpTableCanonical) {
1567  GlobalValue::LinkageTypes LT = IsExported
1570  GlobalAlias *JtAlias = GlobalAlias::create(F->getValueType(), 0, LT,
1571  F->getName() + ".cfi_jt",
1572  CombinedGlobalElemPtr, &M);
1573  if (IsExported)
1575  else
1576  appendToUsed(M, {JtAlias});
1577  }
1578 
1579  if (IsExported) {
1580  if (IsJumpTableCanonical)
1581  ExportSummary->cfiFunctionDefs().insert(std::string(F->getName()));
1582  else
1583  ExportSummary->cfiFunctionDecls().insert(std::string(F->getName()));
1584  }
1585 
1586  if (!IsJumpTableCanonical) {
1587  if (F->hasExternalWeakLinkage())
1588  replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr,
1589  IsJumpTableCanonical);
1590  else
1591  replaceCfiUses(F, CombinedGlobalElemPtr, IsJumpTableCanonical);
1592  } else {
1593  assert(F->getType()->getAddressSpace() == 0);
1594 
1595  GlobalAlias *FAlias =
1596  GlobalAlias::create(F->getValueType(), 0, F->getLinkage(), "",
1597  CombinedGlobalElemPtr, &M);
1598  FAlias->setVisibility(F->getVisibility());
1599  FAlias->takeName(F);
1600  if (FAlias->hasName())
1601  F->setName(FAlias->getName() + ".cfi");
1602  replaceCfiUses(F, FAlias, IsJumpTableCanonical);
1603  if (!F->hasLocalLinkage())
1604  F->setVisibility(GlobalVariable::HiddenVisibility);
1605  }
1606  }
1607  }
1608 
1609  createJumpTable(JumpTableFn, Functions);
1610 }
1611 
1612 /// Assign a dummy layout using an incrementing counter, tag each function
1613 /// with its index represented as metadata, and lower each type test to an
1614 /// integer range comparison. During generation of the indirect function call
1615 /// table in the backend, it will assign the given indexes.
1616 /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1617 /// been finalized.
1618 void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1620  assert(!Functions.empty());
1621 
1622  // Build consecutive monotonic integer ranges for each call target set
1624 
1625  for (GlobalTypeMember *GTM : Functions) {
1626  Function *F = cast<Function>(GTM->getGlobal());
1627 
1628  // Skip functions that are not address taken, to avoid bloating the table
1629  if (!F->hasAddressTaken())
1630  continue;
1631 
1632  // Store metadata with the index for each function
1633  MDNode *MD = MDNode::get(F->getContext(),
1635  ConstantInt::get(Int64Ty, IndirectIndex))));
1636  F->setMetadata("wasm.index", MD);
1637 
1638  // Assign the counter value
1639  GlobalLayout[GTM] = IndirectIndex++;
1640  }
1641 
1642  // The indirect function table index space starts at zero, so pass a NULL
1643  // pointer as the subtracted "jump table" offset.
1644  lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
1645  GlobalLayout);
1646 }
1647 
1648 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1650  ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
1651  DenseMap<Metadata *, uint64_t> TypeIdIndices;
1652  for (unsigned I = 0; I != TypeIds.size(); ++I)
1653  TypeIdIndices[TypeIds[I]] = I;
1654 
1655  // For each type identifier, build a set of indices that refer to members of
1656  // the type identifier.
1657  std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1658  unsigned GlobalIndex = 0;
1660  for (GlobalTypeMember *GTM : Globals) {
1661  for (MDNode *Type : GTM->types()) {
1662  // Type = { offset, type identifier }
1663  auto I = TypeIdIndices.find(Type->getOperand(1));
1664  if (I != TypeIdIndices.end())
1665  TypeMembers[I->second].insert(GlobalIndex);
1666  }
1667  GlobalIndices[GTM] = GlobalIndex;
1668  GlobalIndex++;
1669  }
1670 
1671  for (ICallBranchFunnel *JT : ICallBranchFunnels) {
1672  TypeMembers.emplace_back();
1673  std::set<uint64_t> &TMSet = TypeMembers.back();
1674  for (GlobalTypeMember *T : JT->targets())
1675  TMSet.insert(GlobalIndices[T]);
1676  }
1677 
1678  // Order the sets of indices by size. The GlobalLayoutBuilder works best
1679  // when given small index sets first.
1680  llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1,
1681  const std::set<uint64_t> &O2) {
1682  return O1.size() < O2.size();
1683  });
1684 
1685  // Create a GlobalLayoutBuilder and provide it with index sets as layout
1686  // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1687  // close together as possible.
1688  GlobalLayoutBuilder GLB(Globals.size());
1689  for (auto &&MemSet : TypeMembers)
1690  GLB.addFragment(MemSet);
1691 
1692  // Build a vector of globals with the computed layout.
1693  bool IsGlobalSet =
1694  Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
1695  std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1696  auto OGTMI = OrderedGTMs.begin();
1697  for (auto &&F : GLB.Fragments) {
1698  for (auto &&Offset : F) {
1699  if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
1700  report_fatal_error("Type identifier may not contain both global "
1701  "variables and functions");
1702  *OGTMI++ = Globals[Offset];
1703  }
1704  }
1705 
1706  // Build the bitsets from this disjoint set.
1707  if (IsGlobalSet)
1708  buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
1709  else
1710  buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
1711 }
1712 
1713 /// Lower all type tests in this module.
1714 LowerTypeTestsModule::LowerTypeTestsModule(
1715  Module &M, ModuleSummaryIndex *ExportSummary,
1716  const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
1717  : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary),
1718  DropTypeTests(DropTypeTests || ClDropTypeTests) {
1719  assert(!(ExportSummary && ImportSummary));
1720  Triple TargetTriple(M.getTargetTriple());
1721  Arch = TargetTriple.getArch();
1722  OS = TargetTriple.getOS();
1723  ObjectFormat = TargetTriple.getObjectFormat();
1724 }
1725 
1726 bool LowerTypeTestsModule::runForTesting(Module &M) {
1727  ModuleSummaryIndex Summary(/*HaveGVs=*/false);
1728 
1729  // Handle the command-line summary arguments. This code is for testing
1730  // purposes only, so we handle errors directly.
1731  if (!ClReadSummary.empty()) {
1732  ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1733  ": ");
1734  auto ReadSummaryFile =
1735  ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
1736 
1737  yaml::Input In(ReadSummaryFile->getBuffer());
1738  In >> Summary;
1739  ExitOnErr(errorCodeToError(In.error()));
1740  }
1741 
1742  bool Changed =
1743  LowerTypeTestsModule(
1744  M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
1745  ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr,
1746  /*DropTypeTests*/ false)
1747  .lower();
1748 
1749  if (!ClWriteSummary.empty()) {
1750  ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
1751  ": ");
1752  std::error_code EC;
1754  ExitOnErr(errorCodeToError(EC));
1755 
1756  yaml::Output Out(OS);
1757  Out << Summary;
1758  }
1759 
1760  return Changed;
1761 }
1762 
1763 static bool isDirectCall(Use& U) {
1764  auto *Usr = dyn_cast<CallInst>(U.getUser());
1765  if (Usr) {
1766  auto *CB = dyn_cast<CallBase>(Usr);
1767  if (CB && CB->isCallee(&U))
1768  return true;
1769  }
1770  return false;
1771 }
1772 
1773 void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
1774  bool IsJumpTableCanonical) {
1776  for (Use &U : llvm::make_early_inc_range(Old->uses())) {
1777  // Skip block addresses and no_cfi values, which refer to the function
1778  // body instead of the jump table.
1779  if (isa<BlockAddress, NoCFIValue>(U.getUser()))
1780  continue;
1781 
1782  // Skip direct calls to externally defined or non-dso_local functions
1783  if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
1784  continue;
1785 
1786  // Must handle Constants specially, we cannot call replaceUsesOfWith on a
1787  // constant because they are uniqued.
1788  if (auto *C = dyn_cast<Constant>(U.getUser())) {
1789  if (!isa<GlobalValue>(C)) {
1790  // Save unique users to avoid processing operand replacement
1791  // more than once.
1792  Constants.insert(C);
1793  continue;
1794  }
1795  }
1796 
1797  U.set(New);
1798  }
1799 
1800  // Process operand replacement of saved constants.
1801  for (auto *C : Constants)
1802  C->handleOperandChange(Old, New);
1803 }
1804 
1805 void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
1806  Old->replaceUsesWithIf(New, isDirectCall);
1807 }
1808 
1809 bool LowerTypeTestsModule::lower() {
1810  Function *TypeTestFunc =
1811  M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1812 
1813  if (DropTypeTests && TypeTestFunc) {
1814  for (Use &U : llvm::make_early_inc_range(TypeTestFunc->uses())) {
1815  auto *CI = cast<CallInst>(U.getUser());
1816  // Find and erase llvm.assume intrinsics for this llvm.type.test call.
1817  for (Use &CIU : llvm::make_early_inc_range(CI->uses()))
1818  if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
1819  Assume->eraseFromParent();
1820  // If the assume was merged with another assume, we might have a use on a
1821  // phi (which will feed the assume). Simply replace the use on the phi
1822  // with "true" and leave the merged assume.
1823  if (!CI->use_empty()) {
1824  assert(all_of(CI->users(),
1825  [](User *U) -> bool { return isa<PHINode>(U); }));
1826  CI->replaceAllUsesWith(ConstantInt::getTrue(M.getContext()));
1827  }
1828  CI->eraseFromParent();
1829  }
1830 
1831  // We have deleted the type intrinsics, so we no longer have enough
1832  // information to reason about the liveness of virtual function pointers
1833  // in GlobalDCE.
1834  for (GlobalVariable &GV : M.globals())
1835  GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1836 
1837  return true;
1838  }
1839 
1840  // If only some of the modules were split, we cannot correctly perform
1841  // this transformation. We already checked for the presense of type tests
1842  // with partially split modules during the thin link, and would have emitted
1843  // an error if any were found, so here we can simply return.
1844  if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1845  (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
1846  return false;
1847 
1848  Function *ICallBranchFunnelFunc =
1849  M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel));
1850  if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
1851  (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
1852  !ExportSummary && !ImportSummary)
1853  return false;
1854 
1855  if (ImportSummary) {
1856  if (TypeTestFunc)
1857  for (Use &U : llvm::make_early_inc_range(TypeTestFunc->uses()))
1858  importTypeTest(cast<CallInst>(U.getUser()));
1859 
1860  if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
1862  "unexpected call to llvm.icall.branch.funnel during import phase");
1863 
1866  for (auto &F : M) {
1867  // CFI functions are either external, or promoted. A local function may
1868  // have the same name, but it's not the one we are looking for.
1869  if (F.hasLocalLinkage())
1870  continue;
1871  if (ImportSummary->cfiFunctionDefs().count(std::string(F.getName())))
1872  Defs.push_back(&F);
1873  else if (ImportSummary->cfiFunctionDecls().count(
1874  std::string(F.getName())))
1875  Decls.push_back(&F);
1876  }
1877 
1878  std::vector<GlobalAlias *> AliasesToErase;
1879  {
1880  ScopedSaveAliaseesAndUsed S(M);
1881  for (auto F : Defs)
1882  importFunction(F, /*isJumpTableCanonical*/ true, AliasesToErase);
1883  for (auto F : Decls)
1884  importFunction(F, /*isJumpTableCanonical*/ false, AliasesToErase);
1885  }
1886  for (GlobalAlias *GA : AliasesToErase)
1887  GA->eraseFromParent();
1888 
1889  return true;
1890  }
1891 
1892  // Equivalence class set containing type identifiers and the globals that
1893  // reference them. This is used to partition the set of type identifiers in
1894  // the module into disjoint sets.
1895  using GlobalClassesTy = EquivalenceClasses<
1897  GlobalClassesTy GlobalClasses;
1898 
1899  // Verify the type metadata and build a few data structures to let us
1900  // efficiently enumerate the type identifiers associated with a global:
1901  // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
1902  // of associated type metadata) and a mapping from type identifiers to their
1903  // list of GlobalTypeMembers and last observed index in the list of globals.
1904  // The indices will be used later to deterministically order the list of type
1905  // identifiers.
1906  BumpPtrAllocator Alloc;
1907  struct TIInfo {
1908  unsigned UniqueId;
1909  std::vector<GlobalTypeMember *> RefGlobals;
1910  };
1911  DenseMap<Metadata *, TIInfo> TypeIdInfo;
1912  unsigned CurUniqueId = 0;
1914 
1915  // Cross-DSO CFI emits jumptable entries for exported functions as well as
1916  // address taken functions in case they are address taken in other modules.
1917  const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr;
1918 
1919  struct ExportedFunctionInfo {
1921  MDNode *FuncMD; // {name, linkage, type[, type...]}
1922  };
1924  if (ExportSummary) {
1925  // A set of all functions that are address taken by a live global object.
1926  DenseSet<GlobalValue::GUID> AddressTaken;
1927  for (auto &I : *ExportSummary)
1928  for (auto &GVS : I.second.SummaryList)
1929  if (GVS->isLive())
1930  for (auto &Ref : GVS->refs())
1931  AddressTaken.insert(Ref.getGUID());
1932 
1933  NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions");
1934  if (CfiFunctionsMD) {
1935  for (auto FuncMD : CfiFunctionsMD->operands()) {
1936  assert(FuncMD->getNumOperands() >= 2);
1937  StringRef FunctionName =
1938  cast<MDString>(FuncMD->getOperand(0))->getString();
1940  cast<ConstantAsMetadata>(FuncMD->getOperand(1))
1941  ->getValue()
1942  ->getUniqueInteger()
1943  .getZExtValue());
1944  const GlobalValue::GUID GUID = GlobalValue::getGUID(
1945  GlobalValue::dropLLVMManglingEscape(FunctionName));
1946  // Do not emit jumptable entries for functions that are not-live and
1947  // have no live references (and are not exported with cross-DSO CFI.)
1948  if (!ExportSummary->isGUIDLive(GUID))
1949  continue;
1950  if (!AddressTaken.count(GUID)) {
1951  if (!CrossDsoCfi || Linkage != CFL_Definition)
1952  continue;
1953 
1954  bool Exported = false;
1955  if (auto VI = ExportSummary->getValueInfo(GUID))
1956  for (auto &GVS : VI.getSummaryList())
1957  if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
1958  Exported = true;
1959 
1960  if (!Exported)
1961  continue;
1962  }
1963  auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}});
1964  if (!P.second && P.first->second.Linkage != CFL_Definition)
1965  P.first->second = {Linkage, FuncMD};
1966  }
1967 
1968  for (const auto &P : ExportedFunctions) {
1969  StringRef FunctionName = P.first;
1970  CfiFunctionLinkage Linkage = P.second.Linkage;
1971  MDNode *FuncMD = P.second.FuncMD;
1972  Function *F = M.getFunction(FunctionName);
1973  if (F && F->hasLocalLinkage()) {
1974  // Locally defined function that happens to have the same name as a
1975  // function defined in a ThinLTO module. Rename it to move it out of
1976  // the way of the external reference that we're about to create.
1977  // Note that setName will find a unique name for the function, so even
1978  // if there is an existing function with the suffix there won't be a
1979  // name collision.
1980  F->setName(F->getName() + ".1");
1981  F = nullptr;
1982  }
1983 
1984  if (!F)
1985  F = Function::Create(
1986  FunctionType::get(Type::getVoidTy(M.getContext()), false),
1987  GlobalVariable::ExternalLinkage,
1988  M.getDataLayout().getProgramAddressSpace(), FunctionName, &M);
1989 
1990  // If the function is available_externally, remove its definition so
1991  // that it is handled the same way as a declaration. Later we will try
1992  // to create an alias using this function's linkage, which will fail if
1993  // the linkage is available_externally. This will also result in us
1994  // following the code path below to replace the type metadata.
1995  if (F->hasAvailableExternallyLinkage()) {
1996  F->setLinkage(GlobalValue::ExternalLinkage);
1997  F->deleteBody();
1998  F->setComdat(nullptr);
1999  F->clearMetadata();
2000  }
2001 
2002  // Update the linkage for extern_weak declarations when a definition
2003  // exists.
2004  if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
2005  F->setLinkage(GlobalValue::ExternalLinkage);
2006 
2007  // If the function in the full LTO module is a declaration, replace its
2008  // type metadata with the type metadata we found in cfi.functions. That
2009  // metadata is presumed to be more accurate than the metadata attached
2010  // to the declaration.
2011  if (F->isDeclaration()) {
2013  F->setLinkage(GlobalValue::ExternalWeakLinkage);
2014 
2015  F->eraseMetadata(LLVMContext::MD_type);
2016  for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
2017  F->addMetadata(LLVMContext::MD_type,
2018  *cast<MDNode>(FuncMD->getOperand(I).get()));
2019  }
2020  }
2021  }
2022  }
2023 
2025  for (GlobalObject &GO : M.global_objects()) {
2026  if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
2027  continue;
2028 
2029  Types.clear();
2030  GO.getMetadata(LLVMContext::MD_type, Types);
2031 
2032  bool IsJumpTableCanonical = false;
2033  bool IsExported = false;
2034  if (Function *F = dyn_cast<Function>(&GO)) {
2035  IsJumpTableCanonical = isJumpTableCanonical(F);
2036  if (ExportedFunctions.count(F->getName())) {
2037  IsJumpTableCanonical |=
2038  ExportedFunctions[F->getName()].Linkage == CFL_Definition;
2039  IsExported = true;
2040  // TODO: The logic here checks only that the function is address taken,
2041  // not that the address takers are live. This can be updated to check
2042  // their liveness and emit fewer jumptable entries once monolithic LTO
2043  // builds also emit summaries.
2044  } else if (!F->hasAddressTaken()) {
2045  if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
2046  continue;
2047  }
2048  }
2049 
2050  auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical,
2051  IsExported, Types);
2052  GlobalTypeMembers[&GO] = GTM;
2053  for (MDNode *Type : Types) {
2054  verifyTypeMDNode(&GO, Type);
2055  auto &Info = TypeIdInfo[Type->getOperand(1)];
2056  Info.UniqueId = ++CurUniqueId;
2057  Info.RefGlobals.push_back(GTM);
2058  }
2059  }
2060 
2061  auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
2062  // Add the call site to the list of call sites for this type identifier. We
2063  // also use TypeIdUsers to keep track of whether we have seen this type
2064  // identifier before. If we have, we don't need to re-add the referenced
2065  // globals to the equivalence class.
2066  auto Ins = TypeIdUsers.insert({TypeId, {}});
2067  if (Ins.second) {
2068  // Add the type identifier to the equivalence class.
2069  GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
2070  GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
2071 
2072  // Add the referenced globals to the type identifier's equivalence class.
2073  for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2074  CurSet = GlobalClasses.unionSets(
2075  CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
2076  }
2077 
2078  return Ins.first->second;
2079  };
2080 
2081  if (TypeTestFunc) {
2082  for (const Use &U : TypeTestFunc->uses()) {
2083  auto CI = cast<CallInst>(U.getUser());
2084  // If this type test is only used by llvm.assume instructions, it
2085  // was used for whole program devirtualization, and is being kept
2086  // for use by other optimization passes. We do not need or want to
2087  // lower it here. We also don't want to rewrite any associated globals
2088  // unnecessarily. These will be removed by a subsequent LTT invocation
2089  // with the DropTypeTests flag set.
2090  bool OnlyAssumeUses = !CI->use_empty();
2091  for (const Use &CIU : CI->uses()) {
2092  if (isa<AssumeInst>(CIU.getUser()))
2093  continue;
2094  OnlyAssumeUses = false;
2095  break;
2096  }
2097  if (OnlyAssumeUses)
2098  continue;
2099 
2100  auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
2101  if (!TypeIdMDVal)
2102  report_fatal_error("Second argument of llvm.type.test must be metadata");
2103  auto TypeId = TypeIdMDVal->getMetadata();
2104  AddTypeIdUse(TypeId).CallSites.push_back(CI);
2105  }
2106  }
2107 
2108  if (ICallBranchFunnelFunc) {
2109  for (const Use &U : ICallBranchFunnelFunc->uses()) {
2110  if (Arch != Triple::x86_64)
2112  "llvm.icall.branch.funnel not supported on this target");
2113 
2114  auto CI = cast<CallInst>(U.getUser());
2115 
2116  std::vector<GlobalTypeMember *> Targets;
2117  if (CI->arg_size() % 2 != 1)
2118  report_fatal_error("number of arguments should be odd");
2119 
2120  GlobalClassesTy::member_iterator CurSet;
2121  for (unsigned I = 1; I != CI->arg_size(); I += 2) {
2122  int64_t Offset;
2123  auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
2124  CI->getOperand(I), Offset, M.getDataLayout()));
2125  if (!Base)
2127  "Expected branch funnel operand to be global value");
2128 
2129  GlobalTypeMember *GTM = GlobalTypeMembers[Base];
2130  Targets.push_back(GTM);
2131  GlobalClassesTy::member_iterator NewSet =
2132  GlobalClasses.findLeader(GlobalClasses.insert(GTM));
2133  if (I == 1)
2134  CurSet = NewSet;
2135  else
2136  CurSet = GlobalClasses.unionSets(CurSet, NewSet);
2137  }
2138 
2139  GlobalClasses.unionSets(
2140  CurSet, GlobalClasses.findLeader(
2141  GlobalClasses.insert(ICallBranchFunnel::create(
2142  Alloc, CI, Targets, ++CurUniqueId))));
2143  }
2144  }
2145 
2146  if (ExportSummary) {
2148  for (auto &P : TypeIdInfo) {
2149  if (auto *TypeId = dyn_cast<MDString>(P.first))
2150  MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
2151  TypeId);
2152  }
2153 
2154  for (auto &P : *ExportSummary) {
2155  for (auto &S : P.second.SummaryList) {
2156  if (!ExportSummary->isGlobalValueLive(S.get()))
2157  continue;
2158  if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject()))
2159  for (GlobalValue::GUID G : FS->type_tests())
2160  for (Metadata *MD : MetadataByGUID[G])
2161  AddTypeIdUse(MD).IsExported = true;
2162  }
2163  }
2164  }
2165 
2166  if (GlobalClasses.empty())
2167  return false;
2168 
2169  // Build a list of disjoint sets ordered by their maximum global index for
2170  // determinism.
2171  std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
2172  for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
2173  E = GlobalClasses.end();
2174  I != E; ++I) {
2175  if (!I->isLeader())
2176  continue;
2177  ++NumTypeIdDisjointSets;
2178 
2179  unsigned MaxUniqueId = 0;
2180  for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
2181  MI != GlobalClasses.member_end(); ++MI) {
2182  if (auto *MD = MI->dyn_cast<Metadata *>())
2183  MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
2184  else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
2185  MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
2186  }
2187  Sets.emplace_back(I, MaxUniqueId);
2188  }
2189  llvm::sort(Sets,
2190  [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
2191  const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
2192  return S1.second < S2.second;
2193  });
2194 
2195  // For each disjoint set we found...
2196  for (const auto &S : Sets) {
2197  // Build the list of type identifiers in this disjoint set.
2198  std::vector<Metadata *> TypeIds;
2199  std::vector<GlobalTypeMember *> Globals;
2200  std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2201  for (GlobalClassesTy::member_iterator MI =
2202  GlobalClasses.member_begin(S.first);
2203  MI != GlobalClasses.member_end(); ++MI) {
2204  if (MI->is<Metadata *>())
2205  TypeIds.push_back(MI->get<Metadata *>());
2206  else if (MI->is<GlobalTypeMember *>())
2207  Globals.push_back(MI->get<GlobalTypeMember *>());
2208  else
2209  ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
2210  }
2211 
2212  // Order type identifiers by unique ID for determinism. This ordering is
2213  // stable as there is a one-to-one mapping between metadata and unique IDs.
2214  llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) {
2215  return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2216  });
2217 
2218  // Same for the branch funnels.
2219  llvm::sort(ICallBranchFunnels,
2220  [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2221  return F1->UniqueId < F2->UniqueId;
2222  });
2223 
2224  // Build bitsets for this disjoint set.
2225  buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2226  }
2227 
2228  allocateByteArrays();
2229 
2230  // Parse alias data to replace stand-in function declarations for aliases
2231  // with an alias to the intended target.
2232  if (ExportSummary) {
2233  if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {
2234  for (auto AliasMD : AliasesMD->operands()) {
2235  assert(AliasMD->getNumOperands() >= 4);
2236  StringRef AliasName =
2237  cast<MDString>(AliasMD->getOperand(0))->getString();
2238  StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
2239 
2240  if (!ExportedFunctions.count(Aliasee) ||
2241  ExportedFunctions[Aliasee].Linkage != CFL_Definition ||
2242  !M.getNamedAlias(Aliasee))
2243  continue;
2244 
2245  GlobalValue::VisibilityTypes Visibility =
2246  static_cast<GlobalValue::VisibilityTypes>(
2247  cast<ConstantAsMetadata>(AliasMD->getOperand(2))
2248  ->getValue()
2249  ->getUniqueInteger()
2250  .getZExtValue());
2251  bool Weak =
2252  static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
2253  ->getValue()
2254  ->getUniqueInteger()
2255  .getZExtValue());
2256 
2257  auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee));
2258  Alias->setVisibility(Visibility);
2259  if (Weak)
2260  Alias->setLinkage(GlobalValue::WeakAnyLinkage);
2261 
2262  if (auto *F = M.getFunction(AliasName)) {
2263  Alias->takeName(F);
2264  F->replaceAllUsesWith(Alias);
2265  F->eraseFromParent();
2266  } else {
2267  Alias->setName(AliasName);
2268  }
2269  }
2270  }
2271  }
2272 
2273  // Emit .symver directives for exported functions, if they exist.
2274  if (ExportSummary) {
2275  if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) {
2276  for (auto Symver : SymversMD->operands()) {
2277  assert(Symver->getNumOperands() >= 2);
2279  cast<MDString>(Symver->getOperand(0))->getString();
2280  StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
2281 
2282  if (!ExportedFunctions.count(SymbolName))
2283  continue;
2284 
2285  M.appendModuleInlineAsm(
2286  (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2287  }
2288  }
2289  }
2290 
2291  return true;
2292 }
2293 
2294 PreservedAnalyses LowerTypeTestsPass::run(Module &M,
2295  ModuleAnalysisManager &AM) {
2296  bool Changed;
2297  if (UseCommandLine)
2298  Changed = LowerTypeTestsModule::runForTesting(M);
2299  else
2300  Changed =
2301  LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
2302  .lower();
2303  if (!Changed)
2304  return PreservedAnalyses::all();
2305  return PreservedAnalyses::none();
2306 }
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:430
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:105
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::Attribute::isValid
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition: Attributes.h:168
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:238
llvm::dwarf::Constants
Constants
Definition: Dwarf.h:428
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:1421
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
FileSystem.h
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
llvm::X86AS::FS
@ FS
Definition: X86.h:188
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:293
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:153
llvm::Triple::wasm32
@ wasm32
Definition: Triple.h:100
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2143
llvm::GlobalValue::getLinkage
LinkageTypes getLinkage() const
Definition: GlobalValue.h:467
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:971
T
llvm::Function
Definition: Function.h:62
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:82
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:632
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:1176
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:2522
llvm::initializeLowerTypeTestsPass
void initializeLowerTypeTestsPass(PassRegistry &)
llvm::EquivalenceClasses
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Definition: EquivalenceClasses.h:59
llvm::TypeTestResolution::InlineBits
uint64_t InlineBits
Definition: ModuleSummaryIndex.h:994
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:261
ErrorHandling.h
llvm::TypeTestResolution::Unsat
@ Unsat
Unsatisfiable type (i.e. no global has this type metadata)
Definition: ModuleSummaryIndex.h:972
llvm::IRBuilder<>
llvm::GlobalVariable
Definition: GlobalVariable.h:39
Allocator.h
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:689
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:743
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2253
llvm::ModuleSummaryIndex::getOrInsertTypeIdSummary
TypeIdSummary & getOrInsertTypeIdSummary(StringRef TypeId)
Return an existing or new TypeIdSummary entry for TypeId.
Definition: ModuleSummaryIndex.h:1507
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:363
llvm::GlobalAlias
Definition: GlobalAlias.h:28
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:2440
llvm::Triple
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
llvm::TypeTestResolution::AllOnes
@ AllOnes
All-ones bit vector ("Eliminating Bit Vector Checks for All-Ones Bit Vectors")
Definition: ModuleSummaryIndex.h:976
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::CFL_Definition
@ CFL_Definition
Definition: TypeMetadataUtils.h:32
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
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
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:83
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:1348
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:385
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:1519
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
Operator.h
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:397
llvm::ConstantExpr::getInBoundsGetElementPtr
static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList)
Create an "inbounds" getelementptr.
Definition: Constants.h:1265
llvm::lowertypetests::GlobalLayoutBuilder::Fragments
std::vector< std::vector< uint64_t > > Fragments
The computed layout.
Definition: LowerTypeTests.h:129
llvm::GlobalValue::LinkageTypes
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:47
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:205
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:96
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:239
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:241
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:158
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1233
F
#define F(x, y, z)
Definition: MD5.cpp:55
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:782
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:2065
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1143
llvm::AArch64CC::LT
@ LT
Definition: AArch64BaseInfo.h:266
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:2721
llvm::JumpTable::JumpTableType
JumpTableType
Definition: TargetOptions.h:44
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:185
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:564
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:1592
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:46
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::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:2239
llvm::GlobalObject
Definition: GlobalObject.h:27
llvm::errorCodeToError
Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
Definition: Error.cpp:90
llvm::PassSummaryAction::None
@ None
Do nothing.
TypeMetadataUtils.h
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2225
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:479
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
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:1222
llvm::Triple::Win32
@ Win32
Definition: Triple.h:187
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:143
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1467
llvm::CFL_WeakDeclaration
@ CFL_WeakDeclaration
Definition: TypeMetadataUtils.h:34
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:54
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:925
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:82
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:993
llvm::TypeTestResolution::Inline
@ Inline
Inlined bit vector ("Short Inline Bit Vectors")
Definition: ModuleSummaryIndex.h:974
isDirectCall
static bool isDirectCall(Use &U)
Definition: LowerTypeTests.cpp:1763
llvm::lowertypetests::ByteArrayBuilder::BitsPerByte
@ BitsPerByte
Definition: LowerTypeTests.h:178
llvm::Attribute::getValueAsString
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:304
llvm::PassSummaryAction::Import
@ Import
Import information from summary.
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
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:1224
isThumbFunction
static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch)
Definition: LowerTypeTests.cpp:1355
llvm::TypeTestResolution::AlignLog2
uint64_t AlignLog2
Definition: ModuleSummaryIndex.h:991
llvm::TypeTestResolution::Single
@ Single
Single element (last example in "Short Inline Bit Vectors")
Definition: ModuleSummaryIndex.h:975
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1137
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:267
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:711
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:241
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:135
VI
@ VI
Definition: SIInstrInfo.cpp:7695
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:697
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:578
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:1761
IPO.h
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
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:3148
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::appendToUsed
void appendToUsed(Module &M, ArrayRef< GlobalValue * > Values)
Adds global values to the llvm.used list.
Definition: ModuleUtils.cpp:106
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:585
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:460
ArrayRef.h
llvm::TypeIdSummary
Definition: ModuleSummaryIndex.h:1034
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:139
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::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:640
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:65
llvm::ModuleSummaryIndex::cfiFunctionDefs
std::set< std::string > & cfiFunctionDefs()
Definition: ModuleSummaryIndex.h:1358
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
TinyPtrVector.h
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:140
llvm::ModuleSummaryIndex::partiallySplitLTOUnits
bool partiallySplitLTOUnits() const
Definition: ModuleSummaryIndex.h:1304
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:49
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:255
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:80
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1789
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:672
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:966
llvm::ModuleSummaryIndex::cfiFunctionDecls
std::set< std::string > & cfiFunctionDecls()
Definition: ModuleSummaryIndex.h:1361
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:978
llvm::Triple::ObjectFormatType
ObjectFormatType
Definition: Triple.h:237
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:152
llvm::raw_fd_ostream
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:444
llvm::NamedMDNode::operands
iterator_range< op_iterator > operands()
Definition: Metadata.h:1517
llvm::PointerUnion
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:107
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:880
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:1727
llvm::TypeTestResolution::SizeM1
uint64_t SizeM1
Definition: ModuleSummaryIndex.h:992
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:242
llvm::Triple::OSType
OSType
Definition: Triple.h:170
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:873
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
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:482
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:325
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:151
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
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1341
GlobalVariable.h
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:143
Casting.h
llvm::Triple::MachO
@ MachO
Definition: Triple.h:243
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:1375
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:1533
PassManager.h
EquivalenceClasses.h
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3037
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:278
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:1238
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:580
llvm::CfiFunctionLinkage
CfiFunctionLinkage
The type of CFI jumptable needed for a function.
Definition: TypeMetadataUtils.h:31
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:474
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:224
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:1179
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:1035
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:1088
ModuleUtils.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1343
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:129
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
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:540
llvm::PHINode
Definition: Instructions.h:2657
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:306
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:1478
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:514
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:1444
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:412
llvm::M1
unsigned M1(unsigned Val)
Definition: VE.h:371
llvm::GlobalValue::ExternalWeakLinkage
@ ExternalWeakLinkage
ExternalWeak linkage description.
Definition: GlobalValue.h:57
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3092
raw_ostream.h
llvm::TypeTestResolution::ByteArray
@ ByteArray
Test a byte array (first example)
Definition: ModuleSummaryIndex.h:973
llvm::ConstantAggregateZero::get
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1654
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:633
llvm::GlobalValue::isDSOLocal
bool isDSOLocal() const
Definition: GlobalValue.h:282
BasicBlockUtils.h
Value.h
llvm::Triple::wasm64
@ wasm64
Definition: Triple.h:101
llvm::lowertypetests::isJumpTableCanonical
bool isJumpTableCanonical(Function *F)
Definition: LowerTypeTests.cpp:239
kARMJumpTableEntrySize
static const unsigned kARMJumpTableEntrySize
Definition: LowerTypeTests.cpp:1223
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:235
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::MDOperand::get
Metadata * get() const
Definition: Metadata.h:764
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::Triple::aarch64
@ aarch64
Definition: Triple.h:51
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152
llvm::TypeTestResolution::SizeM1BitWidth
unsigned SizeM1BitWidth
Range of size-1 expressed as a bit width.
Definition: ModuleSummaryIndex.h:984
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:434
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:38
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:600