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
16#include "llvm/Transforms/IPO/LowerTypeTests.h"
17#include "llvm/ADT/APInt.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/EquivalenceClasses.h"
21#include "llvm/ADT/PointerUnion.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/STLForwardCompat.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/ADT/StringRef.h"
28#include "llvm/ADT/TinyPtrVector.h"
29#include "llvm/Analysis/LoopInfo.h"
30#include "llvm/Analysis/PostDominators.h"
31#include "llvm/Analysis/TargetTransformInfo.h"
32#include "llvm/Analysis/TypeMetadataUtils.h"
33#include "llvm/Analysis/ValueTracking.h"
34#include "llvm/BinaryFormat/ELF.h"
35#include "llvm/IR/Attributes.h"
36#include "llvm/IR/BasicBlock.h"
37#include "llvm/IR/Constant.h"
38#include "llvm/IR/Constants.h"
39#include "llvm/IR/DIBuilder.h"
40#include "llvm/IR/DataLayout.h"
41#include "llvm/IR/DerivedTypes.h"
42#include "llvm/IR/Function.h"
43#include "llvm/IR/GlobalAlias.h"
44#include "llvm/IR/GlobalObject.h"
45#include "llvm/IR/GlobalValue.h"
46#include "llvm/IR/GlobalVariable.h"
47#include "llvm/IR/IRBuilder.h"
48#include "llvm/IR/InlineAsm.h"
49#include "llvm/IR/Instruction.h"
50#include "llvm/IR/Instructions.h"
51#include "llvm/IR/IntrinsicInst.h"
52#include "llvm/IR/Intrinsics.h"
53#include "llvm/IR/LLVMContext.h"
54#include "llvm/IR/MDBuilder.h"
55#include "llvm/IR/Metadata.h"
56#include "llvm/IR/Module.h"
57#include "llvm/IR/ModuleSummaryIndex.h"
58#include "llvm/IR/ModuleSummaryIndexYAML.h"
59#include "llvm/IR/Operator.h"
60#include "llvm/IR/PassManager.h"
61#include "llvm/IR/ProfDataUtils.h"
62#include "llvm/IR/ReplaceConstant.h"
63#include "llvm/IR/Type.h"
64#include "llvm/IR/Use.h"
65#include "llvm/IR/User.h"
66#include "llvm/IR/Value.h"
67#include "llvm/Support/Allocator.h"
68#include "llvm/Support/Casting.h"
69#include "llvm/Support/CommandLine.h"
70#include "llvm/Support/Debug.h"
71#include "llvm/Support/Error.h"
72#include "llvm/Support/ErrorHandling.h"
73#include "llvm/Support/FileSystem.h"
74#include "llvm/Support/MathExtras.h"
75#include "llvm/Support/MemoryBuffer.h"
76#include "llvm/Support/TrailingObjects.h"
77#include "llvm/Support/YAMLTraits.h"
78#include "llvm/Support/raw_ostream.h"
79#include "llvm/TargetParser/Triple.h"
80#include "llvm/Transforms/IPO.h"
81#include "llvm/Transforms/Utils/BasicBlockUtils.h"
82#include "llvm/Transforms/Utils/ModuleUtils.h"
83#include <algorithm>
84#include <cassert>
85#include <cstdint>
86#include <set>
87#include <string>
88#include <system_error>
89#include <utility>
90#include <vector>
91
92using namespace llvm;
93using namespace lowertypetests;
94
95#define DEBUG_TYPE "lowertypetests"
96
97STATISTIC(ByteArraySizeBits, "Byte array size in bits");
98STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
99STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
100STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
101STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
102
103static cl::opt<bool> AvoidReuse(
104 "lowertypetests-avoid-reuse",
105 cl::desc("Try to avoid reuse of byte array addresses using aliases"),
106 cl::Hidden, cl::init(Val: true));
107
108static cl::opt<PassSummaryAction> ClSummaryAction(
109 "lowertypetests-summary-action",
110 cl::desc("What to do with the summary when running this pass"),
111 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
112 clEnumValN(PassSummaryAction::Import, "import",
113 "Import typeid resolutions from summary and globals"),
114 clEnumValN(PassSummaryAction::Export, "export",
115 "Export typeid resolutions to summary and globals")),
116 cl::Hidden);
117
118static cl::opt<std::string> ClReadSummary(
119 "lowertypetests-read-summary",
120 cl::desc("Read summary from given YAML file before running pass"),
121 cl::Hidden);
122
123static cl::opt<std::string> ClWriteSummary(
124 "lowertypetests-write-summary",
125 cl::desc("Write summary to given YAML file after running pass"),
126 cl::Hidden);
127
128// FIXME: Remove in clang 24.
129static cl::opt<bool> EnableJumpTableDebugInfo(
130 "lowertypetests-jump-table-debug-info", cl::init(Val: true), cl::Hidden,
131 cl::desc("Enable debug info generation for jump tables"));
132
133bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
134 if (Offset < ByteOffset)
135 return false;
136
137 if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
138 return false;
139
140 uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
141 if (BitOffset >= BitSize)
142 return false;
143
144 return Bits.count(x: BitSize - 1 - BitOffset);
145}
146
147void BitSetInfo::print(raw_ostream &OS) const {
148 OS << "offset " << ByteOffset << " size " << BitSize << " align "
149 << (1 << AlignLog2);
150
151 if (isAllOnes()) {
152 OS << " all-ones\n";
153 return;
154 }
155
156 OS << " { ";
157 for (uint64_t B : Bits)
158 OS << B << ' ';
159 OS << "}\n";
160}
161
162BitSetInfo BitSetBuilder::build() {
163 if (Min > Max)
164 Min = 0;
165
166 // Normalize each offset against the minimum observed offset, and compute
167 // the bitwise OR of each of the offsets. The number of trailing zeros
168 // in the mask gives us the log2 of the alignment of all offsets, which
169 // allows us to compress the bitset by only storing one bit per aligned
170 // address.
171 uint64_t Mask = 0;
172 for (uint64_t &Offset : Offsets) {
173 Offset -= Min;
174 Mask |= Offset;
175 }
176
177 BitSetInfo BSI;
178 BSI.ByteOffset = Min;
179
180 BSI.AlignLog2 = 0;
181 if (Mask != 0)
182 BSI.AlignLog2 = llvm::countr_zero(Val: Mask);
183
184 // Build the compressed bitset while normalizing the offsets against the
185 // computed alignment.
186 BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
187 for (uint64_t Offset : Offsets) {
188 Offset >>= BSI.AlignLog2;
189 // We invert the order of bits when adding them to the bitset. This is
190 // because the offset that we test against is computed by subtracting the
191 // address that we are testing from the global's address, which means that
192 // the offset increases as the tested address decreases.
193 BSI.Bits.insert(x: BSI.BitSize - 1 - Offset);
194 }
195
196 return BSI;
197}
198
199void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
200 // Create a new fragment to hold the layout for F.
201 Fragments.emplace_back();
202 std::vector<uint64_t> &Fragment = Fragments.back();
203 uint64_t FragmentIndex = Fragments.size() - 1;
204
205 for (auto ObjIndex : F) {
206 uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
207 if (OldFragmentIndex == 0) {
208 // We haven't seen this object index before, so just add it to the current
209 // fragment.
210 Fragment.push_back(x: ObjIndex);
211 } else {
212 // This index belongs to an existing fragment. Copy the elements of the
213 // old fragment into this one and clear the old fragment. We don't update
214 // the fragment map just yet, this ensures that any further references to
215 // indices from the old fragment in this fragment do not insert any more
216 // indices.
217 std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
218 llvm::append_range(C&: Fragment, R&: OldFragment);
219 OldFragment.clear();
220 }
221 }
222
223 // Update the fragment map to point our object indices to this fragment.
224 for (uint64_t ObjIndex : Fragment)
225 FragmentMap[ObjIndex] = FragmentIndex;
226}
227
228void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
229 uint64_t BitSize, uint64_t &AllocByteOffset,
230 uint8_t &AllocMask) {
231 // Find the smallest current allocation.
232 unsigned Bit = 0;
233 for (unsigned I = 1; I != BitsPerByte; ++I)
234 if (BitAllocs[I] < BitAllocs[Bit])
235 Bit = I;
236
237 AllocByteOffset = BitAllocs[Bit];
238
239 // Add our size to it.
240 unsigned ReqSize = AllocByteOffset + BitSize;
241 BitAllocs[Bit] = ReqSize;
242 if (Bytes.size() < ReqSize)
243 Bytes.resize(new_size: ReqSize);
244
245 // Set our bits.
246 AllocMask = 1 << Bit;
247 for (uint64_t B : Bits)
248 Bytes[AllocByteOffset + B] |= AllocMask;
249}
250
251bool lowertypetests::isJumpTableCanonical(Function *F) {
252 if (F->isDeclarationForLinker())
253 return false;
254 auto *CI = mdconst::extract_or_null<ConstantInt>(
255 MD: F->getParent()->getModuleFlag(Key: "CFI Canonical Jump Tables"));
256 if (!CI || !CI->isZero())
257 return true;
258 return F->hasFnAttribute(Kind: "cfi-canonical-jump-table");
259}
260
261namespace {
262
263struct ByteArrayInfo {
264 std::set<uint64_t> Bits;
265 uint64_t BitSize;
266 GlobalVariable *ByteArray;
267 GlobalVariable *MaskGlobal;
268 uint8_t *MaskPtr = nullptr;
269};
270
271/// A POD-like structure that we use to store a global reference together with
272/// its metadata types. In this pass we frequently need to query the set of
273/// metadata types referenced by a global, which at the IR level is an expensive
274/// operation involving a map lookup; this data structure helps to reduce the
275/// number of times we need to do this lookup.
276class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
277 friend TrailingObjects;
278
279 GlobalObject *GO;
280 size_t NTypes;
281
282 // For functions: true if the jump table is canonical. This essentially means
283 // whether the canonical address (i.e. the symbol table entry) of the function
284 // is provided by the local jump table. This is normally the same as whether
285 // the function is defined locally, but if canonical jump tables are disabled
286 // by the user then the jump table never provides a canonical definition.
287 bool IsJumpTableCanonical;
288
289 // For functions: true if this function is either defined or used in a thinlto
290 // module and its jumptable entry needs to be exported to thinlto backends.
291 bool IsExported;
292
293public:
294 static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
295 bool IsJumpTableCanonical, bool IsExported,
296 ArrayRef<MDNode *> Types) {
297 auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
298 Size: totalSizeToAlloc<MDNode *>(Counts: Types.size()), Alignment: alignof(GlobalTypeMember)));
299 GTM->GO = GO;
300 GTM->NTypes = Types.size();
301 GTM->IsJumpTableCanonical = IsJumpTableCanonical;
302 GTM->IsExported = IsExported;
303 llvm::copy(Range&: Types, Out: GTM->getTrailingObjects());
304 return GTM;
305 }
306
307 GlobalObject *getGlobal() const {
308 return GO;
309 }
310
311 bool isJumpTableCanonical() const {
312 return IsJumpTableCanonical;
313 }
314
315 bool isExported() const {
316 return IsExported;
317 }
318
319 ArrayRef<MDNode *> types() const { return getTrailingObjects(N: NTypes); }
320};
321
322struct ICallBranchFunnel final
323 : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
324 static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
325 ArrayRef<GlobalTypeMember *> Targets,
326 unsigned UniqueId) {
327 auto *Call = static_cast<ICallBranchFunnel *>(
328 Alloc.Allocate(Size: totalSizeToAlloc<GlobalTypeMember *>(Counts: Targets.size()),
329 Alignment: alignof(ICallBranchFunnel)));
330 Call->CI = CI;
331 Call->UniqueId = UniqueId;
332 Call->NTargets = Targets.size();
333 llvm::copy(Range&: Targets, Out: Call->getTrailingObjects());
334 return Call;
335 }
336
337 CallInst *CI;
338 ArrayRef<GlobalTypeMember *> targets() const {
339 return getTrailingObjects(N: NTargets);
340 }
341
342 unsigned UniqueId;
343
344private:
345 size_t NTargets;
346};
347
348struct ScopedSaveAliaseesAndUsed {
349 Module &M;
350 SmallVector<GlobalValue *, 4> Used, CompilerUsed;
351 std::vector<std::pair<GlobalAlias *, Function *>> FunctionAliases;
352 std::vector<std::pair<GlobalIFunc *, Function *>> ResolverIFuncs;
353
354 // This function only removes functions from llvm.used and llvm.compiler.used.
355 // We cannot remove global variables because they need to follow RAUW, as
356 // they may be deleted by buildBitSetsFromGlobalVariables.
357 void collectAndEraseUsedFunctions(Module &M,
358 SmallVectorImpl<GlobalValue *> &Vec,
359 bool CompilerUsed) {
360 auto *GV = collectUsedGlobalVariables(M, Vec, CompilerUsed);
361 if (!GV)
362 return;
363 // There's no API to only remove certain array elements from
364 // llvm.used/llvm.compiler.used, so we remove all of them and add back only
365 // the non-functions.
366 GV->eraseFromParent();
367 auto NonFuncBegin =
368 std::stable_partition(first: Vec.begin(), last: Vec.end(), pred: [](GlobalValue *GV) {
369 return isa<Function>(Val: GV);
370 });
371 if (CompilerUsed)
372 appendToCompilerUsed(M, Values: {NonFuncBegin, Vec.end()});
373 else
374 appendToUsed(M, Values: {NonFuncBegin, Vec.end()});
375 Vec.resize(N: NonFuncBegin - Vec.begin());
376 }
377
378 ScopedSaveAliaseesAndUsed(Module &M) : M(M) {
379 // The users of this class want to replace all function references except
380 // for aliases and llvm.used/llvm.compiler.used with references to a jump
381 // table. We avoid replacing aliases in order to avoid introducing a double
382 // indirection (or an alias pointing to a declaration in ThinLTO mode), and
383 // we avoid replacing llvm.used/llvm.compiler.used because these global
384 // variables describe properties of the global, not the jump table (besides,
385 // offseted references to the jump table in llvm.used are invalid).
386 // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly
387 // indirect) users", so what we do is save the list of globals referenced by
388 // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW
389 // replace the aliasees and then set them back to their original values at
390 // the end.
391 collectAndEraseUsedFunctions(M, Vec&: Used, CompilerUsed: false);
392 collectAndEraseUsedFunctions(M, Vec&: CompilerUsed, CompilerUsed: true);
393
394 for (auto &GA : M.aliases()) {
395 // FIXME: This should look past all aliases not just interposable ones,
396 // see discussion on D65118.
397 if (auto *F = dyn_cast<Function>(Val: GA.getAliasee()->stripPointerCasts()))
398 FunctionAliases.push_back(x: {&GA, F});
399 }
400
401 for (auto &GI : M.ifuncs())
402 if (auto *F = dyn_cast<Function>(Val: GI.getResolver()->stripPointerCasts()))
403 ResolverIFuncs.push_back(x: {&GI, F});
404 }
405
406 ~ScopedSaveAliaseesAndUsed() {
407 appendToUsed(M, Values: Used);
408 appendToCompilerUsed(M, Values: CompilerUsed);
409
410 for (auto P : FunctionAliases)
411 P.first->setAliasee(P.second);
412
413 for (auto P : ResolverIFuncs) {
414 // This does not preserve pointer casts that may have been stripped by the
415 // constructor, but the resolver's type is different from that of the
416 // ifunc anyway.
417 P.first->setResolver(P.second);
418 }
419 }
420};
421
422class LowerTypeTestsModule {
423 Module &M;
424
425 ModuleSummaryIndex *ExportSummary;
426 const ModuleSummaryIndex *ImportSummary;
427
428 Triple::ArchType Arch;
429 Triple::OSType OS;
430 Triple::ObjectFormatType ObjectFormat;
431
432 // Determines which kind of Thumb jump table we generate. If arch is
433 // either 'arm' or 'thumb' we need to find this out, because
434 // selectJumpTableArmEncoding may decide to use Thumb in either case.
435 bool CanUseArmJumpTable = false, CanUseThumbBWJumpTable = false;
436
437 // Cache variable used by hasBranchTargetEnforcement().
438 int HasBranchTargetEnforcement = -1;
439
440 IntegerType *Int1Ty = Type::getInt1Ty(C&: M.getContext());
441 IntegerType *Int8Ty = Type::getInt8Ty(C&: M.getContext());
442 PointerType *PtrTy = PointerType::getUnqual(C&: M.getContext());
443 ArrayType *Int8Arr0Ty = ArrayType::get(ElementType: Type::getInt8Ty(C&: M.getContext()), NumElements: 0);
444 IntegerType *Int32Ty = Type::getInt32Ty(C&: M.getContext());
445 IntegerType *Int64Ty = Type::getInt64Ty(C&: M.getContext());
446 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(C&: M.getContext(), AddressSpace: 0);
447
448 // Indirect function call index assignment counter for WebAssembly
449 uint64_t IndirectIndex = 1;
450
451 // Mapping from type identifiers to the call sites that test them, as well as
452 // whether the type identifier needs to be exported to ThinLTO backends as
453 // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
454 struct TypeIdUserInfo {
455 std::vector<CallInst *> CallSites;
456 bool IsExported = false;
457 };
458 DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers;
459
460 /// This structure describes how to lower type tests for a particular type
461 /// identifier. It is either built directly from the global analysis (during
462 /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
463 /// identifier summaries and external symbol references (in ThinLTO backends).
464 struct TypeIdLowering {
465 TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat;
466
467 /// All except Unsat: the address of the last element within the combined
468 /// global.
469 Constant *OffsetedGlobal;
470
471 /// ByteArray, Inline, AllOnes: log2 of the required global alignment
472 /// relative to the start address.
473 Constant *AlignLog2;
474
475 /// ByteArray, Inline, AllOnes: one less than the size of the memory region
476 /// covering members of this type identifier as a multiple of 2^AlignLog2.
477 Constant *SizeM1;
478
479 /// ByteArray: the byte array to test the address against.
480 Constant *TheByteArray;
481
482 /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
483 Constant *BitMask;
484
485 /// Inline: the bit mask to test the address against.
486 Constant *InlineBits;
487 };
488
489 std::vector<ByteArrayInfo> ByteArrayInfos;
490
491 Function *WeakInitializerFn = nullptr;
492
493 GlobalVariable *GlobalAnnotation;
494 DenseSet<Value *> FunctionAnnotations;
495
496 // Cross-DSO CFI emits jumptable entries for exported functions as well as
497 // address taken functions in case they are address taken in other modules.
498 bool CrossDsoCfi = M.getModuleFlag(Key: "Cross-DSO CFI") != nullptr;
499
500 bool shouldExportConstantsAsAbsoluteSymbols();
501 uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
502 TypeIdLowering importTypeId(StringRef TypeId);
503 void importTypeTest(CallInst *CI);
504 void importFunction(Function *F, bool isJumpTableCanonical);
505
506 ByteArrayInfo *createByteArray(const BitSetInfo &BSI);
507 void allocateByteArrays();
508 Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
509 Value *BitOffset);
510 void lowerTypeTestCalls(
511 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
512 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
513 Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
514 const TypeIdLowering &TIL);
515
516 void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
517 ArrayRef<GlobalTypeMember *> Globals);
518 Triple::ArchType
519 selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions);
520 bool hasBranchTargetEnforcement();
521 unsigned getJumpTableEntrySize(Triple::ArchType JumpTableArch);
522 InlineAsm *createJumpTableEntryAsm(Triple::ArchType JumpTableArch);
523 void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
524 void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
525 ArrayRef<GlobalTypeMember *> Functions);
526 void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
527 ArrayRef<GlobalTypeMember *> Functions);
528 void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
529 ArrayRef<GlobalTypeMember *> Functions);
530 void
531 buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
532 ArrayRef<GlobalTypeMember *> Globals,
533 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
534
535 void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT,
536 bool IsJumpTableCanonical);
537 void moveInitializerToModuleConstructor(GlobalVariable *GV);
538 void findGlobalVariableUsersOf(Constant *C,
539 SmallSetVector<GlobalVariable *, 8> &Out);
540
541 void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions,
542 Triple::ArchType JumpTableArch);
543
544 /// replaceCfiUses - Go through the uses list for this definition
545 /// and make each use point to "V" instead of "this" when the use is outside
546 /// the block. 'This's use list is expected to have at least one element.
547 /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
548 /// uses.
549 void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical);
550
551 /// replaceDirectCalls - Go through the uses list for this definition and
552 /// replace each use, which is a direct function call.
553 void replaceDirectCalls(Value *Old, Value *New);
554
555 bool isFunctionAnnotation(Value *V) const {
556 return FunctionAnnotations.contains(V);
557 }
558
559 void maybeReplaceComdat(Function *F, StringRef OriginalName);
560
561public:
562 LowerTypeTestsModule(Module &M, ModuleAnalysisManager &AM,
563 ModuleSummaryIndex *ExportSummary,
564 const ModuleSummaryIndex *ImportSummary);
565
566 bool lower();
567
568 // Lower the module using the action and summary passed as command line
569 // arguments. For testing purposes only.
570 static bool runForTesting(Module &M, ModuleAnalysisManager &AM);
571};
572} // end anonymous namespace
573
574/// Build a bit set for list of offsets.
575static BitSetInfo buildBitSet(ArrayRef<uint64_t> Offsets) {
576 // Compute the byte offset of each address associated with this type
577 // identifier.
578 return BitSetBuilder(Offsets).build();
579}
580
581/// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
582/// Bits. This pattern matches to the bt instruction on x86.
583static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits,
584 Value *BitOffset) {
585 auto BitsType = cast<IntegerType>(Val: Bits->getType());
586 unsigned BitWidth = BitsType->getBitWidth();
587
588 BitOffset = B.CreateZExtOrTrunc(V: BitOffset, DestTy: BitsType);
589 Value *BitIndex =
590 B.CreateAnd(LHS: BitOffset, RHS: ConstantInt::get(Ty: BitsType, V: BitWidth - 1));
591 Value *BitMask = B.CreateShl(LHS: ConstantInt::get(Ty: BitsType, V: 1), RHS: BitIndex);
592 Value *MaskedBits = B.CreateAnd(LHS: Bits, RHS: BitMask);
593 return B.CreateICmpNE(LHS: MaskedBits, RHS: ConstantInt::get(Ty: BitsType, V: 0));
594}
595
596ByteArrayInfo *LowerTypeTestsModule::createByteArray(const BitSetInfo &BSI) {
597 // Create globals to stand in for byte arrays and masks. These never actually
598 // get initialized, we RAUW and erase them later in allocateByteArrays() once
599 // we know the offset and mask to use.
600 auto ByteArrayGlobal = new GlobalVariable(
601 M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
602 auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
603 GlobalValue::PrivateLinkage, nullptr);
604
605 ByteArrayInfos.emplace_back();
606 ByteArrayInfo *BAI = &ByteArrayInfos.back();
607
608 BAI->Bits = BSI.Bits;
609 BAI->BitSize = BSI.BitSize;
610 BAI->ByteArray = ByteArrayGlobal;
611 BAI->MaskGlobal = MaskGlobal;
612 return BAI;
613}
614
615void LowerTypeTestsModule::allocateByteArrays() {
616 llvm::stable_sort(Range&: ByteArrayInfos,
617 C: [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
618 return BAI1.BitSize > BAI2.BitSize;
619 });
620
621 std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
622
623 ByteArrayBuilder BAB;
624 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
625 ByteArrayInfo *BAI = &ByteArrayInfos[I];
626
627 uint8_t Mask;
628 BAB.allocate(Bits: BAI->Bits, BitSize: BAI->BitSize, AllocByteOffset&: ByteArrayOffsets[I], AllocMask&: Mask);
629
630 BAI->MaskGlobal->replaceAllUsesWith(
631 V: ConstantExpr::getIntToPtr(C: ConstantInt::get(Ty: Int8Ty, V: Mask), Ty: PtrTy));
632 BAI->MaskGlobal->eraseFromParent();
633 if (BAI->MaskPtr)
634 *BAI->MaskPtr = Mask;
635 }
636
637 Constant *ByteArrayConst = ConstantDataArray::get(Context&: M.getContext(), Elts&: BAB.Bytes);
638 auto ByteArray =
639 new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
640 GlobalValue::PrivateLinkage, ByteArrayConst);
641
642 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
643 ByteArrayInfo *BAI = &ByteArrayInfos[I];
644 Constant *GEP = ConstantExpr::getInBoundsPtrAdd(
645 Ptr: ByteArray, Offset: ConstantInt::get(Ty: IntPtrTy, V: ByteArrayOffsets[I]));
646
647 // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
648 // that the pc-relative displacement is folded into the lea instead of the
649 // test instruction getting another displacement.
650 GlobalAlias *Alias = GlobalAlias::create(
651 Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::PrivateLinkage, Name: "bits", Aliasee: GEP, Parent: &M);
652 BAI->ByteArray->replaceAllUsesWith(V: Alias);
653 BAI->ByteArray->eraseFromParent();
654 }
655
656 ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
657 BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
658 BAB.BitAllocs[6] + BAB.BitAllocs[7];
659 ByteArraySizeBytes = BAB.Bytes.size();
660}
661
662/// Build a test that bit BitOffset is set in the type identifier that was
663/// lowered to TIL, which must be either an Inline or a ByteArray.
664Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
665 const TypeIdLowering &TIL,
666 Value *BitOffset) {
667 if (TIL.TheKind == TypeTestResolution::Inline) {
668 // If the bit set is sufficiently small, we can avoid a load by bit testing
669 // a constant.
670 return createMaskedBitTest(B, Bits: TIL.InlineBits, BitOffset);
671 } else {
672 Constant *ByteArray = TIL.TheByteArray;
673 if (AvoidReuse && !ImportSummary) {
674 // Each use of the byte array uses a different alias. This makes the
675 // backend less likely to reuse previously computed byte array addresses,
676 // improving the security of the CFI mechanism based on this pass.
677 // This won't work when importing because TheByteArray is external.
678 ByteArray = GlobalAlias::create(Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::PrivateLinkage,
679 Name: "bits_use", Aliasee: ByteArray, Parent: &M);
680 }
681
682 Value *ByteAddr = B.CreateGEP(Ty: Int8Ty, Ptr: ByteArray, IdxList: BitOffset);
683 Value *Byte = B.CreateLoad(Ty: Int8Ty, Ptr: ByteAddr);
684
685 Value *ByteAndMask =
686 B.CreateAnd(LHS: Byte, RHS: ConstantExpr::getPtrToInt(C: TIL.BitMask, Ty: Int8Ty));
687 return B.CreateICmpNE(LHS: ByteAndMask, RHS: ConstantInt::get(Ty: Int8Ty, V: 0));
688 }
689}
690
691static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
692 Value *V, uint64_t COffset) {
693 if (auto GV = dyn_cast<GlobalObject>(Val: V)) {
694 SmallVector<MDNode *, 2> Types;
695 GV->getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
696 for (MDNode *Type : Types) {
697 if (Type->getOperand(I: 1) != TypeId)
698 continue;
699 uint64_t Offset =
700 cast<ConstantInt>(
701 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
702 ->getZExtValue();
703 if (COffset == Offset)
704 return true;
705 }
706 return false;
707 }
708
709 if (auto GEP = dyn_cast<GEPOperator>(Val: V)) {
710 APInt APOffset(DL.getIndexSizeInBits(AS: 0), 0);
711 bool Result = GEP->accumulateConstantOffset(DL, Offset&: APOffset);
712 if (!Result)
713 return false;
714 COffset += APOffset.getZExtValue();
715 return isKnownTypeIdMember(TypeId, DL, V: GEP->getPointerOperand(), COffset);
716 }
717
718 if (auto Op = dyn_cast<Operator>(Val: V)) {
719 if (Op->getOpcode() == Instruction::BitCast)
720 return isKnownTypeIdMember(TypeId, DL, V: Op->getOperand(i: 0), COffset);
721
722 if (Op->getOpcode() == Instruction::Select)
723 return isKnownTypeIdMember(TypeId, DL, V: Op->getOperand(i: 1), COffset) &&
724 isKnownTypeIdMember(TypeId, DL, V: Op->getOperand(i: 2), COffset);
725 }
726
727 return false;
728}
729
730/// Lower a llvm.type.test call to its implementation. Returns the value to
731/// replace the call with.
732Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
733 const TypeIdLowering &TIL) {
734 // Delay lowering if the resolution is currently unknown.
735 if (TIL.TheKind == TypeTestResolution::Unknown)
736 return nullptr;
737 if (TIL.TheKind == TypeTestResolution::Unsat)
738 return ConstantInt::getFalse(Context&: M.getContext());
739
740 Value *Ptr = CI->getArgOperand(i: 0);
741 const DataLayout &DL = M.getDataLayout();
742 if (isKnownTypeIdMember(TypeId, DL, V: Ptr, COffset: 0))
743 return ConstantInt::getTrue(Context&: M.getContext());
744
745 BasicBlock *InitialBB = CI->getParent();
746
747 IRBuilder<> B(CI);
748
749 Value *PtrAsInt = B.CreatePtrToInt(V: Ptr, DestTy: IntPtrTy);
750
751 Constant *OffsetedGlobalAsInt =
752 ConstantExpr::getPtrToInt(C: TIL.OffsetedGlobal, Ty: IntPtrTy);
753 if (TIL.TheKind == TypeTestResolution::Single)
754 return B.CreateICmpEQ(LHS: PtrAsInt, RHS: OffsetedGlobalAsInt);
755
756 // Here we compute `last element - address`. The reason why we do this instead
757 // of computing `address - first element` is that it leads to a slightly
758 // shorter instruction sequence on x86. Because it doesn't matter how we do
759 // the subtraction on other architectures, we do so unconditionally.
760 Value *PtrOffset = B.CreateSub(LHS: OffsetedGlobalAsInt, RHS: PtrAsInt);
761
762 // We need to check that the offset both falls within our range and is
763 // suitably aligned. We can check both properties at the same time by
764 // performing a right rotate by log2(alignment) followed by an integer
765 // comparison against the bitset size. The rotate will move the lower
766 // order bits that need to be zero into the higher order bits of the
767 // result, causing the comparison to fail if they are nonzero. The rotate
768 // also conveniently gives us a bit offset to use during the load from
769 // the bitset.
770 Value *BitOffset = B.CreateIntrinsic(RetTy: IntPtrTy, ID: Intrinsic::fshr,
771 Args: {PtrOffset, PtrOffset, TIL.AlignLog2});
772
773 Value *OffsetInRange = B.CreateICmpULE(LHS: BitOffset, RHS: TIL.SizeM1);
774
775 // If the bit set is all ones, testing against it is unnecessary.
776 if (TIL.TheKind == TypeTestResolution::AllOnes)
777 return OffsetInRange;
778
779 // See if the intrinsic is used in the following common pattern:
780 // br(llvm.type.test(...), thenbb, elsebb)
781 // where nothing happens between the type test and the br.
782 // If so, create slightly simpler IR.
783 if (CI->hasOneUse())
784 if (auto *Br = dyn_cast<CondBrInst>(Val: *CI->user_begin()))
785 if (CI->getNextNode() == Br) {
786 BasicBlock *Then = InitialBB->splitBasicBlock(I: CI->getIterator());
787 BasicBlock *Else = Br->getSuccessor(i: 1);
788 CondBrInst *NewBr = CondBrInst::Create(Cond: OffsetInRange, IfTrue: Then, IfFalse: Else);
789 NewBr->setMetadata(KindID: LLVMContext::MD_prof,
790 Node: Br->getMetadata(KindID: LLVMContext::MD_prof));
791 ReplaceInstWithInst(From: InitialBB->getTerminator(), To: NewBr);
792
793 // Update phis in Else resulting from InitialBB being split
794 for (auto &Phi : Else->phis())
795 Phi.addIncoming(V: Phi.getIncomingValueForBlock(BB: Then), BB: InitialBB);
796
797 IRBuilder<> ThenB(CI);
798 return createBitSetTest(B&: ThenB, TIL, BitOffset);
799 }
800
801 MDBuilder MDB(M.getContext());
802 IRBuilder<> ThenB(SplitBlockAndInsertIfThen(Cond: OffsetInRange, SplitBefore: CI, Unreachable: false,
803 BranchWeights: MDB.createLikelyBranchWeights()));
804
805 // Now that we know that the offset is in range and aligned, load the
806 // appropriate bit from the bitset.
807 Value *Bit = createBitSetTest(B&: ThenB, TIL, BitOffset);
808
809 // The value we want is 0 if we came directly from the initial block
810 // (having failed the range or alignment checks), or the loaded bit if
811 // we came from the block in which we loaded it.
812 B.SetInsertPoint(CI);
813 PHINode *P = B.CreatePHI(Ty: Int1Ty, NumReservedValues: 2);
814 P->addIncoming(V: ConstantInt::get(Ty: Int1Ty, V: 0), BB: InitialBB);
815 P->addIncoming(V: Bit, BB: ThenB.GetInsertBlock());
816 return P;
817}
818
819/// Given a disjoint set of type identifiers and globals, lay out the globals,
820/// build the bit sets and lower the llvm.type.test calls.
821void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
822 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
823 // Build a new global with the combined contents of the referenced globals.
824 // This global is a struct whose even-indexed elements contain the original
825 // contents of the referenced globals and whose odd-indexed elements contain
826 // any padding required to align the next element to the next power of 2 plus
827 // any additional padding required to meet its alignment requirements.
828 std::vector<Constant *> GlobalInits;
829 const DataLayout &DL = M.getDataLayout();
830 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
831 Align MaxAlign;
832 uint64_t CurOffset = 0;
833 uint64_t DesiredPadding = 0;
834 for (GlobalTypeMember *G : Globals) {
835 auto *GV = cast<GlobalVariable>(Val: G->getGlobal());
836 Align Alignment =
837 DL.getValueOrABITypeAlignment(Alignment: GV->getAlign(), Ty: GV->getValueType());
838 MaxAlign = std::max(a: MaxAlign, b: Alignment);
839 uint64_t GVOffset = alignTo(Size: CurOffset + DesiredPadding, A: Alignment);
840 GlobalLayout[G] = GVOffset;
841 if (GVOffset != 0) {
842 uint64_t Padding = GVOffset - CurOffset;
843 GlobalInits.push_back(
844 x: ConstantAggregateZero::get(Ty: ArrayType::get(ElementType: Int8Ty, NumElements: Padding)));
845 }
846
847 GlobalInits.push_back(x: GV->getInitializer());
848 uint64_t InitSize = GV->getGlobalSize(DL);
849 CurOffset = GVOffset + InitSize;
850
851 // Compute the amount of padding that we'd like for the next element.
852 DesiredPadding = NextPowerOf2(A: InitSize - 1) - InitSize;
853
854 // Experiments of different caps with Chromium on both x64 and ARM64
855 // have shown that the 32-byte cap generates the smallest binary on
856 // both platforms while different caps yield similar performance.
857 // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
858 if (DesiredPadding > 32)
859 DesiredPadding = alignTo(Value: InitSize, Align: 32) - InitSize;
860 }
861
862 Constant *NewInit = ConstantStruct::getAnon(Ctx&: M.getContext(), V: GlobalInits);
863 auto *CombinedGlobal =
864 new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
865 GlobalValue::PrivateLinkage, NewInit);
866 CombinedGlobal->setAlignment(MaxAlign);
867
868 StructType *NewTy = cast<StructType>(Val: NewInit->getType());
869 lowerTypeTestCalls(TypeIds, CombinedGlobalAddr: CombinedGlobal, GlobalLayout);
870
871 // Build aliases pointing to offsets into the combined global for each
872 // global from which we built the combined global, and replace references
873 // to the original globals with references to the aliases.
874 for (unsigned I = 0; I != Globals.size(); ++I) {
875 GlobalVariable *GV = cast<GlobalVariable>(Val: Globals[I]->getGlobal());
876
877 // Multiply by 2 to account for padding elements.
878 Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Ty: Int32Ty, V: 0),
879 ConstantInt::get(Ty: Int32Ty, V: I * 2)};
880 Constant *CombinedGlobalElemPtr = ConstantExpr::getInBoundsGetElementPtr(
881 Ty: NewInit->getType(), C: CombinedGlobal, IdxList: CombinedGlobalIdxs);
882 assert(GV->getType()->getAddressSpace() == 0);
883 GlobalAlias *GAlias =
884 GlobalAlias::create(Ty: NewTy->getElementType(N: I * 2), AddressSpace: 0, Linkage: GV->getLinkage(),
885 Name: "", Aliasee: CombinedGlobalElemPtr, Parent: &M);
886 GAlias->setVisibility(GV->getVisibility());
887 GAlias->takeName(V: GV);
888 GV->replaceAllUsesWith(V: GAlias);
889 GV->eraseFromParent();
890 }
891}
892
893bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
894 return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
895 ObjectFormat == Triple::ELF;
896}
897
898/// Export the given type identifier so that ThinLTO backends may import it.
899/// Type identifiers are exported by adding coarse-grained information about how
900/// to test the type identifier to the summary, and creating symbols in the
901/// object file (aliases and absolute symbols) containing fine-grained
902/// information about the type identifier.
903///
904/// Returns a pointer to the location in which to store the bitmask, if
905/// applicable.
906uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
907 const TypeIdLowering &TIL) {
908 TypeTestResolution &TTRes =
909 ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
910 TTRes.TheKind = TIL.TheKind;
911
912 auto ExportGlobal = [&](StringRef Name, Constant *C) {
913 GlobalAlias *GA =
914 GlobalAlias::create(Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::ExternalLinkage,
915 Name: "__typeid_" + TypeId + "_" + Name, Aliasee: C, Parent: &M);
916 GA->setVisibility(GlobalValue::HiddenVisibility);
917 };
918
919 auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
920 if (shouldExportConstantsAsAbsoluteSymbols())
921 ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Ty: PtrTy));
922 else
923 Storage = cast<ConstantInt>(Val: C)->getZExtValue();
924 };
925
926 if (TIL.TheKind != TypeTestResolution::Unsat)
927 ExportGlobal("global_addr", TIL.OffsetedGlobal);
928
929 if (TIL.TheKind == TypeTestResolution::ByteArray ||
930 TIL.TheKind == TypeTestResolution::Inline ||
931 TIL.TheKind == TypeTestResolution::AllOnes) {
932 ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
933 ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
934
935 uint64_t BitSize = cast<ConstantInt>(Val: TIL.SizeM1)->getZExtValue() + 1;
936 if (TIL.TheKind == TypeTestResolution::Inline)
937 TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
938 else
939 TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
940 }
941
942 if (TIL.TheKind == TypeTestResolution::ByteArray) {
943 ExportGlobal("byte_array", TIL.TheByteArray);
944 if (shouldExportConstantsAsAbsoluteSymbols())
945 ExportGlobal("bit_mask", TIL.BitMask);
946 else
947 return &TTRes.BitMask;
948 }
949
950 if (TIL.TheKind == TypeTestResolution::Inline)
951 ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
952
953 return nullptr;
954}
955
956LowerTypeTestsModule::TypeIdLowering
957LowerTypeTestsModule::importTypeId(StringRef TypeId) {
958 const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
959 if (!TidSummary)
960 return {}; // Unsat: no globals match this type id.
961 const TypeTestResolution &TTRes = TidSummary->TTRes;
962
963 TypeIdLowering TIL;
964 TIL.TheKind = TTRes.TheKind;
965
966 auto ImportGlobal = [&](StringRef Name) {
967 // Give the global a type of length 0 so that it is not assumed not to alias
968 // with any other global.
969 GlobalVariable *GV = M.getOrInsertGlobal(
970 Name: ("__typeid_" + TypeId + "_" + Name).str(), Ty: Int8Arr0Ty);
971 GV->setVisibility(GlobalValue::HiddenVisibility);
972 return GV;
973 };
974
975 auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
976 Type *Ty) {
977 if (!shouldExportConstantsAsAbsoluteSymbols()) {
978 Constant *C =
979 ConstantInt::get(Ty: isa<IntegerType>(Val: Ty) ? Ty : Int64Ty, V: Const);
980 if (!isa<IntegerType>(Val: Ty))
981 C = ConstantExpr::getIntToPtr(C, Ty);
982 return C;
983 }
984
985 Constant *C = ImportGlobal(Name);
986 auto *GV = cast<GlobalVariable>(Val: C->stripPointerCasts());
987 if (isa<IntegerType>(Val: Ty))
988 C = ConstantExpr::getPtrToInt(C, Ty);
989 if (GV->getMetadata(KindID: LLVMContext::MD_absolute_symbol))
990 return C;
991
992 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
993 auto *MinC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Min));
994 auto *MaxC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Max));
995 GV->setMetadata(KindID: LLVMContext::MD_absolute_symbol,
996 Node: MDNode::get(Context&: M.getContext(), MDs: {MinC, MaxC}));
997 };
998 if (AbsWidth == IntPtrTy->getBitWidth()) {
999 uint64_t AllOnes = IntPtrTy->getBitMask();
1000 SetAbsRange(AllOnes, AllOnes); // Full set.
1001 } else {
1002 SetAbsRange(0, 1ull << AbsWidth);
1003 }
1004 return C;
1005 };
1006
1007 if (TIL.TheKind != TypeTestResolution::Unsat) {
1008 auto *GV = ImportGlobal("global_addr");
1009 // This is either a vtable (in .data.rel.ro) or a jump table (in .text).
1010 // Either way it's expected to be in the low 2 GiB, so set the small code
1011 // model.
1012 //
1013 // For .data.rel.ro, we currently place all such sections in the low 2 GiB
1014 // [1], and for .text the sections are expected to be in the low 2 GiB under
1015 // the small and medium code models [2] and this pass only supports those
1016 // code models (e.g. jump tables use jmp instead of movabs/jmp).
1017 //
1018 // [1]https://github.com/llvm/llvm-project/pull/137742
1019 // [2]https://maskray.me/blog/2023-05-14-relocation-overflow-and-code-models
1020 GV->setCodeModel(CodeModel::Small);
1021 TIL.OffsetedGlobal = GV;
1022 }
1023
1024 if (TIL.TheKind == TypeTestResolution::ByteArray ||
1025 TIL.TheKind == TypeTestResolution::Inline ||
1026 TIL.TheKind == TypeTestResolution::AllOnes) {
1027 TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, IntPtrTy);
1028 TIL.SizeM1 =
1029 ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
1030 }
1031
1032 if (TIL.TheKind == TypeTestResolution::ByteArray) {
1033 TIL.TheByteArray = ImportGlobal("byte_array");
1034 TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, PtrTy);
1035 }
1036
1037 if (TIL.TheKind == TypeTestResolution::Inline)
1038 TIL.InlineBits = ImportConstant(
1039 "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
1040 TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
1041
1042 return TIL;
1043}
1044
1045void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
1046 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
1047 if (!TypeIdMDVal)
1048 report_fatal_error(reason: "Second argument of llvm.type.test must be metadata");
1049
1050 auto TypeIdStr = dyn_cast<MDString>(Val: TypeIdMDVal->getMetadata());
1051 // If this is a local unpromoted type, which doesn't have a metadata string,
1052 // treat as Unknown and delay lowering, so that we can still utilize it for
1053 // later optimizations.
1054 if (!TypeIdStr)
1055 return;
1056
1057 TypeIdLowering TIL = importTypeId(TypeId: TypeIdStr->getString());
1058 Value *Lowered = lowerTypeTestCall(TypeId: TypeIdStr, CI, TIL);
1059 if (Lowered) {
1060 CI->replaceAllUsesWith(V: Lowered);
1061 CI->eraseFromParent();
1062 }
1063}
1064
1065void LowerTypeTestsModule::maybeReplaceComdat(Function *F,
1066 StringRef OriginalName) {
1067 // For COFF we should also rename the comdat if this function also
1068 // happens to be the key function. Even if the comdat name changes, this
1069 // should still be fine since comdat and symbol resolution happens
1070 // before LTO, so all symbols which would prevail have been selected.
1071 if (F->hasComdat() && ObjectFormat == Triple::COFF &&
1072 F->getComdat()->getName() == OriginalName) {
1073 Comdat *OldComdat = F->getComdat();
1074 Comdat *NewComdat = M.getOrInsertComdat(Name: F->getName());
1075 for (GlobalObject &GO : M.global_objects()) {
1076 if (GO.getComdat() == OldComdat)
1077 GO.setComdat(NewComdat);
1078 }
1079 }
1080}
1081
1082// ThinLTO backend: the function F has a jump table entry; update this module
1083// accordingly. isJumpTableCanonical describes the type of the jump table entry.
1084void LowerTypeTestsModule::importFunction(Function *F,
1085 bool isJumpTableCanonical) {
1086 assert(F->getType()->getAddressSpace() == 0);
1087
1088 GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1089 std::string Name = std::string(F->getName());
1090
1091 if (F->isDeclarationForLinker() && isJumpTableCanonical) {
1092 // Non-dso_local functions may be overriden at run time,
1093 // don't short curcuit them
1094 if (F->isDSOLocal()) {
1095 Function *RealF = Function::Create(Ty: F->getFunctionType(),
1096 Linkage: GlobalValue::ExternalLinkage,
1097 AddrSpace: F->getAddressSpace(),
1098 N: Name + ".cfi", M: &M);
1099 RealF->setVisibility(GlobalVariable::HiddenVisibility);
1100 replaceDirectCalls(Old: F, New: RealF);
1101 }
1102 return;
1103 }
1104
1105 Function *FDecl;
1106 if (!isJumpTableCanonical) {
1107 // Either a declaration of an external function or a reference to a locally
1108 // defined jump table.
1109 FDecl = Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1110 AddrSpace: F->getAddressSpace(), N: Name + ".cfi_jt", M: &M);
1111 FDecl->setVisibility(GlobalValue::HiddenVisibility);
1112 } else {
1113 F->setName(Name + ".cfi");
1114 maybeReplaceComdat(F, OriginalName: Name);
1115 FDecl = Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1116 AddrSpace: F->getAddressSpace(), N: Name, M: &M);
1117 FDecl->setVisibility(Visibility);
1118 Visibility = GlobalValue::HiddenVisibility;
1119
1120 // Update aliases pointing to this function to also include the ".cfi" suffix,
1121 // We expect the jump table entry to either point to the real function or an
1122 // alias. Redirect all other users to the jump table entry.
1123 for (auto &U : F->uses()) {
1124 if (auto *A = dyn_cast<GlobalAlias>(Val: U.getUser())) {
1125 std::string AliasName = A->getName().str() + ".cfi";
1126 Function *AliasDecl = Function::Create(
1127 Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1128 AddrSpace: F->getAddressSpace(), N: "", M: &M);
1129 AliasDecl->takeName(V: A);
1130 A->replaceAllUsesWith(V: AliasDecl);
1131 A->setName(AliasName);
1132 }
1133 }
1134 }
1135
1136 if (F->hasExternalWeakLinkage())
1137 replaceWeakDeclarationWithJumpTablePtr(F, JT: FDecl, IsJumpTableCanonical: isJumpTableCanonical);
1138 else
1139 replaceCfiUses(Old: F, New: FDecl, IsJumpTableCanonical: isJumpTableCanonical);
1140
1141 // Set visibility late because it's used in replaceCfiUses() to determine
1142 // whether uses need to be replaced.
1143 F->setVisibility(Visibility);
1144}
1145
1146static auto
1147buildBitSets(ArrayRef<Metadata *> TypeIds,
1148 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1149 DenseMap<Metadata *, SmallVector<uint64_t, 16>> OffsetsByTypeID;
1150 // Pre-populate the map with interesting type identifiers.
1151 for (Metadata *TypeId : TypeIds)
1152 OffsetsByTypeID[TypeId];
1153 for (const auto &[Mem, MemOff] : GlobalLayout) {
1154 for (MDNode *Type : Mem->types()) {
1155 auto It = OffsetsByTypeID.find(Val: Type->getOperand(I: 1));
1156 if (It == OffsetsByTypeID.end())
1157 continue;
1158 uint64_t Offset =
1159 cast<ConstantInt>(
1160 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
1161 ->getZExtValue();
1162 It->second.push_back(Elt: MemOff + Offset);
1163 }
1164 }
1165
1166 SmallVector<std::pair<Metadata *, BitSetInfo>> BitSets;
1167 BitSets.reserve(N: TypeIds.size());
1168 for (Metadata *TypeId : TypeIds) {
1169 BitSets.emplace_back(Args&: TypeId, Args: buildBitSet(Offsets: OffsetsByTypeID[TypeId]));
1170 LLVM_DEBUG({
1171 if (auto MDS = dyn_cast<MDString>(TypeId))
1172 dbgs() << MDS->getString() << ": ";
1173 else
1174 dbgs() << "<unnamed>: ";
1175 BitSets.back().second.print(dbgs());
1176 });
1177 }
1178
1179 return BitSets;
1180}
1181
1182void LowerTypeTestsModule::lowerTypeTestCalls(
1183 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1184 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1185 // For each type identifier in this disjoint set...
1186 for (const auto &[TypeId, BSI] : buildBitSets(TypeIds, GlobalLayout)) {
1187 ByteArrayInfo *BAI = nullptr;
1188 TypeIdLowering TIL;
1189
1190 uint64_t GlobalOffset =
1191 BSI.ByteOffset + ((BSI.BitSize - 1) << BSI.AlignLog2);
1192 TIL.OffsetedGlobal = ConstantExpr::getPtrAdd(
1193 Ptr: CombinedGlobalAddr, Offset: ConstantInt::get(Ty: IntPtrTy, V: GlobalOffset)),
1194 TIL.AlignLog2 = ConstantInt::get(Ty: IntPtrTy, V: BSI.AlignLog2);
1195 TIL.SizeM1 = ConstantInt::get(Ty: IntPtrTy, V: BSI.BitSize - 1);
1196 if (BSI.isAllOnes()) {
1197 TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1198 : TypeTestResolution::AllOnes;
1199 } else if (BSI.BitSize <= IntPtrTy->getBitWidth()) {
1200 TIL.TheKind = TypeTestResolution::Inline;
1201 uint64_t InlineBits = 0;
1202 for (auto Bit : BSI.Bits)
1203 InlineBits |= uint64_t(1) << Bit;
1204 if (InlineBits == 0)
1205 TIL.TheKind = TypeTestResolution::Unsat;
1206 else
1207 TIL.InlineBits = ConstantInt::get(
1208 Ty: (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, V: InlineBits);
1209 } else {
1210 TIL.TheKind = TypeTestResolution::ByteArray;
1211 ++NumByteArraysCreated;
1212 BAI = createByteArray(BSI);
1213 TIL.TheByteArray = BAI->ByteArray;
1214 TIL.BitMask = BAI->MaskGlobal;
1215 }
1216
1217 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1218
1219 if (TIUI.IsExported) {
1220 uint8_t *MaskPtr = exportTypeId(TypeId: cast<MDString>(Val: TypeId)->getString(), TIL);
1221 if (BAI)
1222 BAI->MaskPtr = MaskPtr;
1223 }
1224
1225 // Lower each call to llvm.type.test for this type identifier.
1226 for (CallInst *CI : TIUI.CallSites) {
1227 ++NumTypeTestCallsLowered;
1228 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1229 if (Lowered) {
1230 CI->replaceAllUsesWith(V: Lowered);
1231 CI->eraseFromParent();
1232 }
1233 }
1234 }
1235}
1236
1237void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1238 if (Type->getNumOperands() != 2)
1239 report_fatal_error(reason: "All operands of type metadata must have 2 elements");
1240
1241 if (GO->isThreadLocal())
1242 report_fatal_error(reason: "Bit set element may not be thread-local");
1243 if (isa<GlobalVariable>(Val: GO) && GO->hasSection())
1244 report_fatal_error(
1245 reason: "A member of a type identifier may not have an explicit section");
1246
1247 // FIXME: We previously checked that global var member of a type identifier
1248 // must be a definition, but the IR linker may leave type metadata on
1249 // declarations. We should restore this check after fixing PR31759.
1250
1251 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0));
1252 if (!OffsetConstMD)
1253 report_fatal_error(reason: "Type offset must be a constant");
1254 auto OffsetInt = dyn_cast<ConstantInt>(Val: OffsetConstMD->getValue());
1255 if (!OffsetInt)
1256 report_fatal_error(reason: "Type offset must be an integer constant");
1257}
1258
1259static const unsigned kX86JumpTableEntrySize = 8;
1260static const unsigned kX86IBTJumpTableEntrySize = 16;
1261static const unsigned kARMJumpTableEntrySize = 4;
1262static const unsigned kARMBTIJumpTableEntrySize = 8;
1263static const unsigned kARMv6MJumpTableEntrySize = 16;
1264static const unsigned kRISCVJumpTableEntrySize = 8;
1265static const unsigned kLOONGARCH64JumpTableEntrySize = 8;
1266static const unsigned kHexagonJumpTableEntrySize = 4;
1267
1268bool LowerTypeTestsModule::hasBranchTargetEnforcement() {
1269 if (HasBranchTargetEnforcement == -1) {
1270 // First time this query has been called. Find out the answer by checking
1271 // the module flags.
1272 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1273 MD: M.getModuleFlag(Key: "branch-target-enforcement")))
1274 HasBranchTargetEnforcement = !BTE->isZero();
1275 else
1276 HasBranchTargetEnforcement = 0;
1277 }
1278 return HasBranchTargetEnforcement;
1279}
1280
1281unsigned
1282LowerTypeTestsModule::getJumpTableEntrySize(Triple::ArchType JumpTableArch) {
1283 switch (JumpTableArch) {
1284 case Triple::x86:
1285 case Triple::x86_64:
1286 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1287 MD: M.getModuleFlag(Key: "cf-protection-branch")))
1288 if (MD->getZExtValue())
1289 return kX86IBTJumpTableEntrySize;
1290 return kX86JumpTableEntrySize;
1291 case Triple::arm:
1292 return kARMJumpTableEntrySize;
1293 case Triple::thumb:
1294 if (CanUseThumbBWJumpTable) {
1295 if (hasBranchTargetEnforcement())
1296 return kARMBTIJumpTableEntrySize;
1297 return kARMJumpTableEntrySize;
1298 } else {
1299 return kARMv6MJumpTableEntrySize;
1300 }
1301 case Triple::aarch64:
1302 if (hasBranchTargetEnforcement())
1303 return kARMBTIJumpTableEntrySize;
1304 return kARMJumpTableEntrySize;
1305 case Triple::riscv32:
1306 case Triple::riscv64:
1307 return kRISCVJumpTableEntrySize;
1308 case Triple::loongarch64:
1309 return kLOONGARCH64JumpTableEntrySize;
1310 case Triple::hexagon:
1311 return kHexagonJumpTableEntrySize;
1312 default:
1313 report_fatal_error(reason: "Unsupported architecture for jump tables");
1314 }
1315}
1316
1317// Create an inline asm constant representing a jump table entry for the target.
1318// This consists of an instruction sequence containing a relative branch to
1319// Dest.
1320InlineAsm *
1321LowerTypeTestsModule::createJumpTableEntryAsm(Triple::ArchType JumpTableArch) {
1322 std::string Asm;
1323 raw_string_ostream AsmOS(Asm);
1324
1325 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1326 bool Endbr = false;
1327 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1328 MD: M.getModuleFlag(Key: "cf-protection-branch")))
1329 Endbr = !MD->isZero();
1330 if (Endbr)
1331 AsmOS << (JumpTableArch == Triple::x86 ? "endbr32\n" : "endbr64\n");
1332 AsmOS << "jmp ${0:c}@plt\n";
1333 if (Endbr)
1334 AsmOS << ".balign 16, 0xcc\n";
1335 else
1336 AsmOS << "int3\nint3\nint3\n";
1337 } else if (JumpTableArch == Triple::arm) {
1338 AsmOS << "b $0\n";
1339 } else if (JumpTableArch == Triple::aarch64) {
1340 if (hasBranchTargetEnforcement())
1341 AsmOS << "bti c\n";
1342 AsmOS << "b $0\n";
1343 } else if (JumpTableArch == Triple::thumb) {
1344 if (!CanUseThumbBWJumpTable) {
1345 // In Armv6-M, this sequence will generate a branch without corrupting
1346 // any registers. We use two stack words; in the second, we construct the
1347 // address we'll pop into pc, and the first is used to save and restore
1348 // r0 which we use as a temporary register.
1349 //
1350 // To support position-independent use cases, the offset of the target
1351 // function is stored as a relative offset (which will expand into an
1352 // R_ARM_REL32 relocation in ELF, and presumably the equivalent in other
1353 // object file types), and added to pc after we load it. (The alternative
1354 // B.W is automatically pc-relative.)
1355 //
1356 // There are five 16-bit Thumb instructions here, so the .balign 4 adds a
1357 // sixth halfword of padding, and then the offset consumes a further 4
1358 // bytes, for a total of 16, which is very convenient since entries in
1359 // this jump table need to have power-of-two size.
1360 AsmOS << "push {r0,r1}\n"
1361 << "ldr r0, 1f\n"
1362 << "0: add r0, r0, pc\n"
1363 << "str r0, [sp, #4]\n"
1364 << "pop {r0,pc}\n"
1365 << ".balign 4\n"
1366 << "1: .word $0 - (0b + 4)\n";
1367 } else {
1368 if (hasBranchTargetEnforcement())
1369 AsmOS << "bti\n";
1370 AsmOS << "b.w $0\n";
1371 }
1372 } else if (JumpTableArch == Triple::riscv32 ||
1373 JumpTableArch == Triple::riscv64) {
1374 AsmOS << "tail $0@plt\n";
1375 } else if (JumpTableArch == Triple::loongarch64) {
1376 AsmOS << "pcalau12i $$t0, %pc_hi20($0)\n"
1377 << "jirl $$r0, $$t0, %pc_lo12($0)\n";
1378 } else if (JumpTableArch == Triple::hexagon) {
1379 AsmOS << "jump $0\n";
1380 } else {
1381 report_fatal_error(reason: "Unsupported architecture for jump tables");
1382 }
1383
1384 return InlineAsm::get(
1385 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), Params: PtrTy, isVarArg: false),
1386 AsmString: AsmOS.str(), Constraints: "s",
1387 /*hasSideEffects=*/true);
1388}
1389
1390/// Given a disjoint set of type identifiers and functions, build the bit sets
1391/// and lower the llvm.type.test calls, architecture dependently.
1392void LowerTypeTestsModule::buildBitSetsFromFunctions(
1393 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1394 if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1395 Arch == Triple::thumb || Arch == Triple::aarch64 ||
1396 Arch == Triple::riscv32 || Arch == Triple::riscv64 ||
1397 Arch == Triple::loongarch64 || Arch == Triple::hexagon)
1398 buildBitSetsFromFunctionsNative(TypeIds, Functions);
1399 else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1400 buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1401 else
1402 report_fatal_error(reason: "Unsupported architecture for jump tables");
1403}
1404
1405void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1406 GlobalVariable *GV) {
1407 if (WeakInitializerFn == nullptr) {
1408 WeakInitializerFn = Function::Create(
1409 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()),
1410 /* IsVarArg */ isVarArg: false),
1411 Linkage: GlobalValue::InternalLinkage,
1412 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
1413 N: "__cfi_global_var_init", M: &M);
1414 BasicBlock *BB =
1415 BasicBlock::Create(Context&: M.getContext(), Name: "entry", Parent: WeakInitializerFn);
1416 ReturnInst::Create(C&: M.getContext(), InsertAtEnd: BB);
1417 WeakInitializerFn->setSection(
1418 ObjectFormat == Triple::MachO
1419 ? "__TEXT,__StaticInit,regular,pure_instructions"
1420 : ".text.startup");
1421 // This code is equivalent to relocation application, and should run at the
1422 // earliest possible time (i.e. with the highest priority).
1423 appendToGlobalCtors(M, F: WeakInitializerFn, /* Priority */ 0);
1424 }
1425
1426 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1427 GV->setConstant(false);
1428 IRB.CreateAlignedStore(Val: GV->getInitializer(), Ptr: GV, Align: GV->getAlign());
1429 GV->setInitializer(Constant::getNullValue(Ty: GV->getValueType()));
1430}
1431
1432void LowerTypeTestsModule::findGlobalVariableUsersOf(
1433 Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
1434 for (auto *U : C->users()){
1435 if (auto *GV = dyn_cast<GlobalVariable>(Val: U))
1436 Out.insert(X: GV);
1437 else if (auto *C2 = dyn_cast<Constant>(Val: U))
1438 findGlobalVariableUsersOf(C: C2, Out);
1439 }
1440}
1441
1442// Replace all uses of F with (F ? JT : 0).
1443void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1444 Function *F, Constant *JT, bool IsJumpTableCanonical) {
1445 // The target expression can not appear in a constant initializer on most
1446 // (all?) targets. Switch to a runtime initializer.
1447 SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
1448 findGlobalVariableUsersOf(C: F, Out&: GlobalVarUsers);
1449 for (auto *GV : GlobalVarUsers) {
1450 if (GV == GlobalAnnotation)
1451 continue;
1452 moveInitializerToModuleConstructor(GV);
1453 }
1454
1455 // Can not RAUW F with an expression that uses F. Replace with a temporary
1456 // placeholder first.
1457 Function *PlaceholderFn =
1458 Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalWeakLinkage,
1459 AddrSpace: F->getAddressSpace(), N: "", M: &M);
1460 replaceCfiUses(Old: F, New: PlaceholderFn, IsJumpTableCanonical);
1461
1462 convertUsersOfConstantsToInstructions(Consts: PlaceholderFn);
1463 // Don't use range based loop, because use list will be modified.
1464 while (!PlaceholderFn->use_empty()) {
1465 Use &U = *PlaceholderFn->use_begin();
1466 auto *InsertPt = dyn_cast<Instruction>(Val: U.getUser());
1467 assert(InsertPt && "Non-instruction users should have been eliminated");
1468 auto *PN = dyn_cast<PHINode>(Val: InsertPt);
1469 if (PN)
1470 InsertPt = PN->getIncomingBlock(U)->getTerminator();
1471 IRBuilder Builder(InsertPt);
1472 Value *ICmp = Builder.CreateICmp(P: CmpInst::ICMP_NE, LHS: F,
1473 RHS: Constant::getNullValue(Ty: F->getType()));
1474 Value *Select = Builder.CreateSelect(C: ICmp, True: JT,
1475 False: Constant::getNullValue(Ty: F->getType()));
1476
1477 if (auto *SI = dyn_cast<SelectInst>(Val: Select))
1478 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *SI, DEBUG_TYPE);
1479 // For phi nodes, we need to update the incoming value for all operands
1480 // with the same predecessor.
1481 if (PN)
1482 PN->setIncomingValueForBlock(BB: InsertPt->getParent(), V: Select);
1483 else
1484 U.set(Select);
1485 }
1486 PlaceholderFn->eraseFromParent();
1487}
1488
1489static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1490 Attribute TFAttr = F->getFnAttribute(Kind: "target-features");
1491 if (TFAttr.isValid()) {
1492 SmallVector<StringRef, 6> Features;
1493 TFAttr.getValueAsString().split(A&: Features, Separator: ',');
1494 for (StringRef Feature : Features) {
1495 if (Feature == "-thumb-mode")
1496 return false;
1497 else if (Feature == "+thumb-mode")
1498 return true;
1499 }
1500 }
1501
1502 return ModuleArch == Triple::thumb;
1503}
1504
1505// Each jump table must be either ARM or Thumb as a whole for the bit-test math
1506// to work. Pick one that matches the majority of members to minimize interop
1507// veneers inserted by the linker.
1508Triple::ArchType LowerTypeTestsModule::selectJumpTableArmEncoding(
1509 ArrayRef<GlobalTypeMember *> Functions) {
1510 if (Arch != Triple::arm && Arch != Triple::thumb)
1511 return Arch;
1512
1513 if (!CanUseThumbBWJumpTable && CanUseArmJumpTable) {
1514 // In architectures that provide Arm and Thumb-1 but not Thumb-2,
1515 // we should always prefer the Arm jump table format, because the
1516 // Thumb-1 one is larger and slower.
1517 return Triple::arm;
1518 }
1519
1520 // Otherwise, go with majority vote.
1521 unsigned ArmCount = 0, ThumbCount = 0;
1522 for (const auto GTM : Functions) {
1523 if (!GTM->isJumpTableCanonical()) {
1524 // PLT stubs are always ARM.
1525 // FIXME: This is the wrong heuristic for non-canonical jump tables.
1526 ++ArmCount;
1527 continue;
1528 }
1529
1530 Function *F = cast<Function>(Val: GTM->getGlobal());
1531 ++(isThumbFunction(F, ModuleArch: Arch) ? ThumbCount : ArmCount);
1532 }
1533
1534 return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1535}
1536
1537// Create location for each function entry which should look like this:
1538// frame #0: c::c() (.cfi_jt) at sanitizer/ubsan_interface.h:0:0
1539// frame #1: __ubsan_check_cfi_icall_jt at sanitizer/ubsan_interface.h:0
1540static SmallVector<DILocation *>
1541createJumpTableDebugInfo(Function *F, ArrayRef<GlobalTypeMember *> Functions) {
1542 Module &M = *F->getParent();
1543 DICompileUnit *CU = nullptr;
1544 auto CUs = M.debug_compile_units();
1545 if (!CUs.empty())
1546 CU = *CUs.begin();
1547
1548 DIBuilder DIB(M, /*AllowUnresolved=*/true, CU);
1549 DIFile *File = DIB.createFile(Filename: "ubsan_interface.h", Directory: "sanitizer");
1550 if (!CU) {
1551 // Synthetic module (like ld-temp.o), it frequently lacks a DICompileUnit
1552 // even if the rest of the program has debug info.
1553 CU = DIB.createCompileUnit(
1554 Lang: DISourceLanguageName(dwarf::DW_LANG_C), File, Producer: "llvm", isOptimized: true, Flags: "", RV: 0, SplitName: "",
1555 Kind: DICompileUnit::DebugEmissionKind::LineTablesOnly);
1556 }
1557
1558 DISubroutineType *DIFnTy = DIB.createSubroutineType(ParameterTypes: nullptr);
1559
1560 DISubprogram *UbsanSP = DIB.createFunction(
1561 Scope: CU, Name: "__ubsan_check_cfi_icall_jt", LinkageName: {}, File, LineNo: 0, Ty: DIFnTy, ScopeLine: 0,
1562 Flags: DINode::FlagArtificial, SPFlags: DISubprogram::SPFlagDefinition);
1563
1564 F->setSubprogram(UbsanSP);
1565
1566 DILocation *UbsanLoc = DILocation::get(Context&: M.getContext(), Line: 0, Column: 0, Scope: UbsanSP);
1567
1568 SmallVector<DILocation *> Locations;
1569 Locations.reserve(N: Functions.size());
1570
1571 for (auto *Func : Functions) {
1572 StringRef FuncName = Func->getGlobal()->getName();
1573 FuncName.consume_back(Suffix: ".cfi");
1574 DISubprogram *JumpSP = DIB.createFunction(
1575 Scope: CU, Name: (FuncName + ".cfi_jt").str(), LinkageName: {}, File, LineNo: 0, Ty: DIFnTy, ScopeLine: 0,
1576 Flags: DINode::FlagArtificial, SPFlags: DISubprogram::SPFlagDefinition);
1577
1578 DILocation *EntryLoc =
1579 DILocation::get(Context&: M.getContext(), Line: 0, Column: 0, Scope: JumpSP, InlinedAt: UbsanLoc);
1580
1581 Locations.push_back(Elt: EntryLoc);
1582 }
1583
1584 DIB.finalize();
1585
1586 return Locations;
1587}
1588
1589void LowerTypeTestsModule::createJumpTable(
1590 Function *F, ArrayRef<GlobalTypeMember *> Functions,
1591 Triple::ArchType JumpTableArch) {
1592 unsigned JumpTableEntrySize = getJumpTableEntrySize(JumpTableArch);
1593 // Give the jumptable section this type in order to enable jumptable
1594 // relaxation. Only do this if cross-DSO CFI is disabled because jumptable
1595 // relaxation violates cross-DSO CFI's restrictions on the ordering of the
1596 // jumptable relative to other sections.
1597 if (!CrossDsoCfi)
1598 F->setMetadata(KindID: LLVMContext::MD_elf_section_properties,
1599 Node: MDNode::get(Context&: F->getContext(),
1600 MDs: ArrayRef<Metadata *>{
1601 ConstantAsMetadata::get(C: ConstantInt::get(
1602 Ty: Int64Ty, V: ELF::SHT_LLVM_CFI_JUMP_TABLE)),
1603 ConstantAsMetadata::get(C: ConstantInt::get(
1604 Ty: Int64Ty, V: JumpTableEntrySize))}));
1605
1606 BasicBlock *BB = BasicBlock::Create(Context&: M.getContext(), Name: "entry", Parent: F);
1607 IRBuilder<> IRB(BB);
1608
1609 SmallVector<DILocation *> Locations;
1610 if (M.getDwarfVersion() != 0 && EnableJumpTableDebugInfo)
1611 Locations = createJumpTableDebugInfo(F, Functions);
1612
1613 InlineAsm *JumpTableAsm = createJumpTableEntryAsm(JumpTableArch);
1614
1615 // Check if all entries have the NoUnwind attribute.
1616 // If all entries have it, we can safely mark the
1617 // cfi.jumptable as NoUnwind, otherwise, direct calls
1618 // to the jump table will not handle exceptions properly
1619 bool areAllEntriesNounwind = true;
1620 assert(Locations.empty() || Functions.size() == Locations.size());
1621 for (auto [GTM, Loc] : zip_longest(t&: Functions, u&: Locations)) {
1622 if (Loc.has_value())
1623 IRB.SetCurrentDebugLocation(*Loc);
1624 if (!cast<Function>(Val: (*GTM)->getGlobal())
1625 ->hasFnAttribute(Kind: Attribute::NoUnwind)) {
1626 areAllEntriesNounwind = false;
1627 }
1628 IRB.CreateCall(Callee: JumpTableAsm, Args: (*GTM)->getGlobal());
1629 }
1630 IRB.CreateUnreachable();
1631
1632 // Align the whole table by entry size.
1633 F->setPreferredAlignment(Align(JumpTableEntrySize));
1634 F->addFnAttr(Kind: Attribute::Naked);
1635 if (JumpTableArch == Triple::arm)
1636 F->addFnAttr(Kind: "target-features", Val: "-thumb-mode");
1637 if (JumpTableArch == Triple::thumb) {
1638 if (hasBranchTargetEnforcement()) {
1639 // If we're generating a Thumb jump table with BTI, add a target-features
1640 // setting to ensure BTI can be assembled.
1641 F->addFnAttr(Kind: "target-features", Val: "+thumb-mode,+pacbti");
1642 } else {
1643 F->addFnAttr(Kind: "target-features", Val: "+thumb-mode");
1644 if (CanUseThumbBWJumpTable) {
1645 // Thumb jump table assembly needs Thumb2. The following attribute is
1646 // added by Clang for -march=armv7.
1647 F->addFnAttr(Kind: "target-cpu", Val: "cortex-a8");
1648 }
1649 }
1650 }
1651 // When -mbranch-protection= is used, the inline asm adds a BTI. Suppress BTI
1652 // for the function to avoid double BTI. This is a no-op without
1653 // -mbranch-protection=.
1654 if (JumpTableArch == Triple::aarch64 || JumpTableArch == Triple::thumb) {
1655 if (F->hasFnAttribute(Kind: "branch-target-enforcement"))
1656 F->removeFnAttr(Kind: "branch-target-enforcement");
1657 if (F->hasFnAttribute(Kind: "sign-return-address"))
1658 F->removeFnAttr(Kind: "sign-return-address");
1659 }
1660 if (JumpTableArch == Triple::riscv32 || JumpTableArch == Triple::riscv64) {
1661 // Make sure the jump table assembly is not modified by the assembler or
1662 // the linker.
1663 F->addFnAttr(Kind: "target-features", Val: "-c,-relax");
1664 }
1665 // When -fcf-protection= is used, the inline asm adds an ENDBR. Suppress ENDBR
1666 // for the function to avoid double ENDBR. This is a no-op without
1667 // -fcf-protection=.
1668 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64)
1669 F->addFnAttr(Kind: Attribute::NoCfCheck);
1670
1671 // Make sure we don't emit .eh_frame for this function if it isn't needed.
1672 if (areAllEntriesNounwind)
1673 F->addFnAttr(Kind: Attribute::NoUnwind);
1674
1675 // Make sure we do not inline any calls to the cfi.jumptable.
1676 F->addFnAttr(Kind: Attribute::NoInline);
1677}
1678
1679/// Given a disjoint set of type identifiers and functions, build a jump table
1680/// for the functions, build the bit sets and lower the llvm.type.test calls.
1681void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1682 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1683 // Unlike the global bitset builder, the function bitset builder cannot
1684 // re-arrange functions in a particular order and base its calculations on the
1685 // layout of the functions' entry points, as we have no idea how large a
1686 // particular function will end up being (the size could even depend on what
1687 // this pass does!) Instead, we build a jump table, which is a block of code
1688 // consisting of one branch instruction for each of the functions in the bit
1689 // set that branches to the target function, and redirect any taken function
1690 // addresses to the corresponding jump table entry. In the object file's
1691 // symbol table, the symbols for the target functions also refer to the jump
1692 // table entries, so that addresses taken outside the module will pass any
1693 // verification done inside the module.
1694 //
1695 // In more concrete terms, suppose we have three functions f, g, h which are
1696 // of the same type, and a function foo that returns their addresses:
1697 //
1698 // f:
1699 // mov 0, %eax
1700 // ret
1701 //
1702 // g:
1703 // mov 1, %eax
1704 // ret
1705 //
1706 // h:
1707 // mov 2, %eax
1708 // ret
1709 //
1710 // foo:
1711 // mov f, %eax
1712 // mov g, %edx
1713 // mov h, %ecx
1714 // ret
1715 //
1716 // We output the jump table as module-level inline asm string. The end result
1717 // will (conceptually) look like this:
1718 //
1719 // f = .cfi.jumptable
1720 // g = .cfi.jumptable + 4
1721 // h = .cfi.jumptable + 8
1722 // .cfi.jumptable:
1723 // jmp f.cfi ; 5 bytes
1724 // int3 ; 1 byte
1725 // int3 ; 1 byte
1726 // int3 ; 1 byte
1727 // jmp g.cfi ; 5 bytes
1728 // int3 ; 1 byte
1729 // int3 ; 1 byte
1730 // int3 ; 1 byte
1731 // jmp h.cfi ; 5 bytes
1732 // int3 ; 1 byte
1733 // int3 ; 1 byte
1734 // int3 ; 1 byte
1735 //
1736 // f.cfi:
1737 // mov 0, %eax
1738 // ret
1739 //
1740 // g.cfi:
1741 // mov 1, %eax
1742 // ret
1743 //
1744 // h.cfi:
1745 // mov 2, %eax
1746 // ret
1747 //
1748 // foo:
1749 // mov f, %eax
1750 // mov g, %edx
1751 // mov h, %ecx
1752 // ret
1753 //
1754 // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1755 // normal case the check can be carried out using the same kind of simple
1756 // arithmetic that we normally use for globals.
1757
1758 // FIXME: find a better way to represent the jumptable in the IR.
1759 assert(!Functions.empty());
1760
1761 // Decide on the jump table encoding, so that we know how big the
1762 // entries will be.
1763 Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions);
1764
1765 // Build a simple layout based on the regular layout of jump tables.
1766 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1767 unsigned EntrySize = getJumpTableEntrySize(JumpTableArch);
1768 for (unsigned I = 0; I != Functions.size(); ++I)
1769 GlobalLayout[Functions[I]] = I * EntrySize;
1770
1771 Function *JumpTableFn =
1772 Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()),
1773 /* IsVarArg */ isVarArg: false),
1774 Linkage: GlobalValue::PrivateLinkage,
1775 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
1776 N: ".cfi.jumptable", M: &M);
1777 ArrayType *JumpTableEntryType = ArrayType::get(ElementType: Int8Ty, NumElements: EntrySize);
1778 ArrayType *JumpTableType =
1779 ArrayType::get(ElementType: JumpTableEntryType, NumElements: Functions.size());
1780 auto JumpTable = ConstantExpr::getPointerCast(
1781 C: JumpTableFn, Ty: PointerType::getUnqual(C&: M.getContext()));
1782
1783 lowerTypeTestCalls(TypeIds, CombinedGlobalAddr: JumpTable, GlobalLayout);
1784
1785 // Build aliases pointing to offsets into the jump table, and replace
1786 // references to the original functions with references to the aliases.
1787 for (unsigned I = 0; I != Functions.size(); ++I) {
1788 Function *F = cast<Function>(Val: Functions[I]->getGlobal());
1789 bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
1790
1791 Constant *CombinedGlobalElemPtr = ConstantExpr::getInBoundsGetElementPtr(
1792 Ty: JumpTableType, C: JumpTable,
1793 IdxList: ArrayRef<Constant *>{ConstantInt::get(Ty: IntPtrTy, V: 0),
1794 ConstantInt::get(Ty: IntPtrTy, V: I)});
1795
1796 const bool IsExported = Functions[I]->isExported();
1797 if (!IsJumpTableCanonical) {
1798 GlobalValue::LinkageTypes LT = IsExported ? GlobalValue::ExternalLinkage
1799 : GlobalValue::InternalLinkage;
1800 GlobalAlias *JtAlias = GlobalAlias::create(Ty: JumpTableEntryType, AddressSpace: 0, Linkage: LT,
1801 Name: F->getName() + ".cfi_jt",
1802 Aliasee: CombinedGlobalElemPtr, Parent: &M);
1803 if (IsExported)
1804 JtAlias->setVisibility(GlobalValue::HiddenVisibility);
1805 else
1806 appendToUsed(M, Values: {JtAlias});
1807 }
1808
1809 if (IsExported) {
1810 // TODO: use F->getGUID() once #184065 is relanded.
1811 GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
1812 GlobalName: GlobalValue::dropLLVMManglingEscape(Name: F->getName()));
1813 if (IsJumpTableCanonical)
1814 ExportSummary->cfiFunctionDefs().addSymbolWithThinLTOGUID(Name: F->getName(),
1815 GUID);
1816 else
1817 ExportSummary->cfiFunctionDecls().addSymbolWithThinLTOGUID(Name: F->getName(),
1818 GUID);
1819 }
1820
1821 if (!IsJumpTableCanonical) {
1822 if (F->hasExternalWeakLinkage())
1823 replaceWeakDeclarationWithJumpTablePtr(F, JT: CombinedGlobalElemPtr,
1824 IsJumpTableCanonical);
1825 else
1826 replaceCfiUses(Old: F, New: CombinedGlobalElemPtr, IsJumpTableCanonical);
1827 } else {
1828 assert(F->getType()->getAddressSpace() == 0);
1829
1830 GlobalAlias *FAlias =
1831 GlobalAlias::create(Ty: JumpTableEntryType, AddressSpace: 0, Linkage: F->getLinkage(), Name: "",
1832 Aliasee: CombinedGlobalElemPtr, Parent: &M);
1833 FAlias->setVisibility(F->getVisibility());
1834 FAlias->takeName(V: F);
1835 if (FAlias->hasName()) {
1836 F->setName(FAlias->getName() + ".cfi");
1837 maybeReplaceComdat(F, OriginalName: FAlias->getName());
1838 }
1839 replaceCfiUses(Old: F, New: FAlias, IsJumpTableCanonical);
1840 if (!F->hasLocalLinkage())
1841 F->setVisibility(GlobalVariable::HiddenVisibility);
1842 }
1843 }
1844
1845 createJumpTable(F: JumpTableFn, Functions, JumpTableArch);
1846}
1847
1848/// Assign a dummy layout using an incrementing counter, tag each function
1849/// with its index represented as metadata, and lower each type test to an
1850/// integer range comparison. During generation of the indirect function call
1851/// table in the backend, it will assign the given indexes.
1852/// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1853/// been finalized.
1854void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1855 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1856 assert(!Functions.empty());
1857
1858 // Build consecutive monotonic integer ranges for each call target set
1859 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1860
1861 for (GlobalTypeMember *GTM : Functions) {
1862 Function *F = cast<Function>(Val: GTM->getGlobal());
1863
1864 // Skip functions that are not address taken, to avoid bloating the table
1865 if (!F->hasAddressTaken())
1866 continue;
1867
1868 // Store metadata with the index for each function
1869 MDNode *MD = MDNode::get(Context&: F->getContext(),
1870 MDs: ArrayRef<Metadata *>(ConstantAsMetadata::get(
1871 C: ConstantInt::get(Ty: Int64Ty, V: IndirectIndex))));
1872 F->setMetadata(Kind: "wasm.index", Node: MD);
1873
1874 // Assign the counter value
1875 GlobalLayout[GTM] = IndirectIndex++;
1876 }
1877
1878 // The indirect function table index space starts at zero, so pass a NULL
1879 // pointer as the subtracted "jump table" offset.
1880 lowerTypeTestCalls(TypeIds, CombinedGlobalAddr: ConstantPointerNull::get(T: PtrTy),
1881 GlobalLayout);
1882}
1883
1884void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1885 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
1886 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
1887 DenseMap<Metadata *, uint64_t> TypeIdIndices;
1888 for (unsigned I = 0; I != TypeIds.size(); ++I)
1889 TypeIdIndices[TypeIds[I]] = I;
1890
1891 // For each type identifier, build a set of indices that refer to members of
1892 // the type identifier.
1893 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1894 unsigned GlobalIndex = 0;
1895 DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
1896 for (GlobalTypeMember *GTM : Globals) {
1897 for (MDNode *Type : GTM->types()) {
1898 // Type = { offset, type identifier }
1899 auto I = TypeIdIndices.find(Val: Type->getOperand(I: 1));
1900 if (I != TypeIdIndices.end())
1901 TypeMembers[I->second].insert(x: GlobalIndex);
1902 }
1903 GlobalIndices[GTM] = GlobalIndex;
1904 GlobalIndex++;
1905 }
1906
1907 for (ICallBranchFunnel *JT : ICallBranchFunnels) {
1908 TypeMembers.emplace_back();
1909 std::set<uint64_t> &TMSet = TypeMembers.back();
1910 for (GlobalTypeMember *T : JT->targets())
1911 TMSet.insert(x: GlobalIndices[T]);
1912 }
1913
1914 // Order the sets of indices by size. The GlobalLayoutBuilder works best
1915 // when given small index sets first.
1916 llvm::stable_sort(Range&: TypeMembers, C: [](const std::set<uint64_t> &O1,
1917 const std::set<uint64_t> &O2) {
1918 return O1.size() < O2.size();
1919 });
1920
1921 // Create a GlobalLayoutBuilder and provide it with index sets as layout
1922 // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1923 // close together as possible.
1924 GlobalLayoutBuilder GLB(Globals.size());
1925 for (auto &&MemSet : TypeMembers)
1926 GLB.addFragment(F: MemSet);
1927
1928 // Build a vector of globals with the computed layout.
1929 bool IsGlobalSet =
1930 Globals.empty() || isa<GlobalVariable>(Val: Globals[0]->getGlobal());
1931 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1932 auto OGTMI = OrderedGTMs.begin();
1933 for (auto &&F : GLB.Fragments) {
1934 for (auto &&Offset : F) {
1935 if (IsGlobalSet != isa<GlobalVariable>(Val: Globals[Offset]->getGlobal()))
1936 report_fatal_error(reason: "Type identifier may not contain both global "
1937 "variables and functions");
1938 *OGTMI++ = Globals[Offset];
1939 }
1940 }
1941
1942 // Build the bitsets from this disjoint set.
1943 if (IsGlobalSet)
1944 buildBitSetsFromGlobalVariables(TypeIds, Globals: OrderedGTMs);
1945 else
1946 buildBitSetsFromFunctions(TypeIds, Functions: OrderedGTMs);
1947}
1948
1949/// Lower all type tests in this module.
1950LowerTypeTestsModule::LowerTypeTestsModule(
1951 Module &M, ModuleAnalysisManager &AM, ModuleSummaryIndex *ExportSummary,
1952 const ModuleSummaryIndex *ImportSummary)
1953 : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
1954 assert(!(ExportSummary && ImportSummary));
1955 Triple TargetTriple(M.getTargetTriple());
1956 Arch = TargetTriple.getArch();
1957 if (Arch == Triple::arm)
1958 CanUseArmJumpTable = true;
1959 if (Arch == Triple::arm || Arch == Triple::thumb) {
1960 auto &FAM =
1961 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1962 for (Function &F : M) {
1963 // Skip declarations since we should not query the TTI for them.
1964 if (F.isDeclaration())
1965 continue;
1966 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
1967 if (TTI.hasArmWideBranch(Thumb: false))
1968 CanUseArmJumpTable = true;
1969 if (TTI.hasArmWideBranch(Thumb: true))
1970 CanUseThumbBWJumpTable = true;
1971 }
1972 }
1973 OS = TargetTriple.getOS();
1974 ObjectFormat = TargetTriple.getObjectFormat();
1975
1976 // Function annotation describes or applies to function itself, and
1977 // shouldn't be associated with jump table thunk generated for CFI.
1978 GlobalAnnotation = M.getGlobalVariable(Name: "llvm.global.annotations");
1979 if (GlobalAnnotation && GlobalAnnotation->hasInitializer()) {
1980 const ConstantArray *CA =
1981 cast<ConstantArray>(Val: GlobalAnnotation->getInitializer());
1982 FunctionAnnotations.insert_range(R: CA->operands());
1983 }
1984}
1985
1986bool LowerTypeTestsModule::runForTesting(Module &M, ModuleAnalysisManager &AM) {
1987 ModuleSummaryIndex Summary(/*HaveGVs=*/false);
1988
1989 // Handle the command-line summary arguments. This code is for testing
1990 // purposes only, so we handle errors directly.
1991 if (!ClReadSummary.empty()) {
1992 ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1993 ": ");
1994 auto ReadSummaryFile = ExitOnErr(errorOrToExpected(
1995 EO: MemoryBuffer::getFile(Filename: ClReadSummary, /*IsText=*/true)));
1996
1997 yaml::Input In(ReadSummaryFile->getBuffer());
1998 In >> Summary;
1999 ExitOnErr(errorCodeToError(EC: In.error()));
2000 }
2001
2002 bool Changed =
2003 LowerTypeTestsModule(
2004 M, AM,
2005 ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
2006 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr)
2007 .lower();
2008
2009 if (!ClWriteSummary.empty()) {
2010 ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
2011 ": ");
2012 std::error_code EC;
2013 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF);
2014 ExitOnErr(errorCodeToError(EC));
2015
2016 yaml::Output Out(OS);
2017 Out << Summary;
2018 }
2019
2020 return Changed;
2021}
2022
2023static bool isDirectCall(Use& U) {
2024 auto *Usr = dyn_cast<CallInst>(Val: U.getUser());
2025 return Usr && Usr->isCallee(U: &U);
2026}
2027
2028void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
2029 bool IsJumpTableCanonical) {
2030 SmallSetVector<Constant *, 4> Constants;
2031 for (Use &U : llvm::make_early_inc_range(Range: Old->uses())) {
2032 // Skip no_cfi values, which refer to the function body instead of the jump
2033 // table.
2034 if (isa<NoCFIValue>(Val: U.getUser()))
2035 continue;
2036
2037 // Skip direct calls to externally defined or non-dso_local functions.
2038 if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
2039 continue;
2040
2041 // Skip function annotation.
2042 if (isFunctionAnnotation(V: U.getUser()))
2043 continue;
2044
2045 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
2046 // constant because they are uniqued.
2047 if (auto *C = dyn_cast<Constant>(Val: U.getUser())) {
2048 if (!isa<GlobalValue>(Val: C)) {
2049 // Save unique users to avoid processing operand replacement
2050 // more than once.
2051 Constants.insert(X: C);
2052 continue;
2053 }
2054 }
2055
2056 U.set(New);
2057 }
2058
2059 // Process operand replacement of saved constants.
2060 for (auto *C : Constants)
2061 C->handleOperandChange(Old, New);
2062}
2063
2064void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
2065 Old->replaceUsesWithIf(New, ShouldReplace: isDirectCall);
2066}
2067
2068static void dropTypeTests(Module &M, Function &TypeTestFunc,
2069 bool ShouldDropAll) {
2070 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc.uses())) {
2071 auto *CI = cast<CallInst>(Val: U.getUser());
2072 // Find and erase llvm.assume intrinsics for this llvm.type.test call.
2073 for (Use &CIU : llvm::make_early_inc_range(Range: CI->uses()))
2074 if (auto *Assume = dyn_cast<AssumeInst>(Val: CIU.getUser()))
2075 Assume->eraseFromParent();
2076 // If the assume was merged with another assume, we might have a use on a
2077 // phi or select (which will feed the assume). Simply replace the use on
2078 // the phi/select with "true" and leave the merged assume.
2079 //
2080 // If ShouldDropAll is set, then we we need to update any remaining uses,
2081 // regardless of the instruction type.
2082 if (!CI->use_empty()) {
2083 assert(ShouldDropAll || all_of(CI->users(), [](User *U) -> bool {
2084 return isa<PHINode>(U) || isa<SelectInst>(U);
2085 }));
2086 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
2087 }
2088 CI->eraseFromParent();
2089 }
2090}
2091
2092static bool dropTypeTests(Module &M, bool ShouldDropAll) {
2093 Function *TypeTestFunc =
2094 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
2095 if (TypeTestFunc)
2096 dropTypeTests(M, TypeTestFunc&: *TypeTestFunc, ShouldDropAll);
2097 // Normally we'd have already removed all @llvm.public.type.test calls,
2098 // except for in the case where we originally were performing ThinLTO but
2099 // decided not to in the backend.
2100 Function *PublicTypeTestFunc =
2101 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test);
2102 if (PublicTypeTestFunc)
2103 dropTypeTests(M, TypeTestFunc&: *PublicTypeTestFunc, ShouldDropAll);
2104 if (TypeTestFunc || PublicTypeTestFunc) {
2105 // We have deleted the type intrinsics, so we no longer have enough
2106 // information to reason about the liveness of virtual function pointers
2107 // in GlobalDCE.
2108 for (GlobalVariable &GV : M.globals())
2109 GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility);
2110 return true;
2111 }
2112 return false;
2113}
2114
2115bool LowerTypeTestsModule::lower() {
2116 Function *TypeTestFunc =
2117 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
2118
2119 // If only some of the modules were split, we cannot correctly perform
2120 // this transformation. We already checked for the presense of type tests
2121 // with partially split modules during the thin link, and would have emitted
2122 // an error if any were found, so here we can simply return.
2123 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
2124 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
2125 return false;
2126
2127 Function *ICallBranchFunnelFunc =
2128 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::icall_branch_funnel);
2129 if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
2130 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
2131 !ExportSummary && !ImportSummary)
2132 return false;
2133
2134 if (ImportSummary) {
2135 if (TypeTestFunc)
2136 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc->uses()))
2137 importTypeTest(CI: cast<CallInst>(Val: U.getUser()));
2138
2139 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
2140 report_fatal_error(
2141 reason: "unexpected call to llvm.icall.branch.funnel during import phase");
2142
2143 SmallVector<Function *, 8> Defs;
2144 SmallVector<Function *, 8> Decls;
2145 for (auto &F : M) {
2146 // CFI functions are either external, or promoted. A local function may
2147 // have the same name, but it's not the one we are looking for.
2148 if (F.hasLocalLinkage())
2149 continue;
2150 if (ImportSummary->cfiFunctionDefs().contains(Name: F.getName()))
2151 Defs.push_back(Elt: &F);
2152 else if (ImportSummary->cfiFunctionDecls().contains(Name: F.getName()))
2153 Decls.push_back(Elt: &F);
2154 }
2155
2156 {
2157 ScopedSaveAliaseesAndUsed S(M);
2158 for (auto *F : Defs)
2159 importFunction(F, /*isJumpTableCanonical*/ true);
2160 for (auto *F : Decls)
2161 importFunction(F, /*isJumpTableCanonical*/ false);
2162 }
2163
2164 return true;
2165 }
2166
2167 // Equivalence class set containing type identifiers and the globals that
2168 // reference them. This is used to partition the set of type identifiers in
2169 // the module into disjoint sets.
2170 using GlobalClassesTy = EquivalenceClasses<
2171 PointerUnion<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>;
2172 GlobalClassesTy GlobalClasses;
2173
2174 // Verify the type metadata and build a few data structures to let us
2175 // efficiently enumerate the type identifiers associated with a global:
2176 // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
2177 // of associated type metadata) and a mapping from type identifiers to their
2178 // list of GlobalTypeMembers and last observed index in the list of globals.
2179 // The indices will be used later to deterministically order the list of type
2180 // identifiers.
2181 BumpPtrAllocator Alloc;
2182 struct TIInfo {
2183 unsigned UniqueId;
2184 std::vector<GlobalTypeMember *> RefGlobals;
2185 };
2186 DenseMap<Metadata *, TIInfo> TypeIdInfo;
2187 unsigned CurUniqueId = 0;
2188 SmallVector<MDNode *, 2> Types;
2189
2190 struct ExportedFunctionInfo {
2191 CfiFunctionLinkage Linkage;
2192 MDNode *FuncMD; // {name, linkage, type[, type...]}
2193 };
2194 MapVector<StringRef, ExportedFunctionInfo> ExportedFunctions;
2195 if (ExportSummary) {
2196 NamedMDNode *CfiFunctionsMD = M.getNamedMetadata(Name: "cfi.functions");
2197 if (CfiFunctionsMD) {
2198 // A set of all functions that are address taken by a live global object.
2199 DenseSet<GlobalValue::GUID> AddressTaken;
2200 for (auto &I : *ExportSummary)
2201 for (auto &GVS : I.second.getSummaryList())
2202 if (GVS->isLive())
2203 for (const auto &Ref : GVS->refs()) {
2204 AddressTaken.insert(V: Ref.getGUID());
2205 for (auto &RefGVS : Ref.getSummaryList())
2206 if (auto Alias = dyn_cast<AliasSummary>(Val: RefGVS.get()))
2207 AddressTaken.insert(V: Alias->getAliaseeGUID());
2208 }
2209 auto IsAddressTaken = [&](GlobalValue::GUID GUID) {
2210 if (AddressTaken.count(V: GUID))
2211 return true;
2212 auto VI = ExportSummary->getValueInfo(GUID);
2213 if (!VI)
2214 return false;
2215 for (auto &I : VI.getSummaryList())
2216 if (auto Alias = dyn_cast<AliasSummary>(Val: I.get()))
2217 if (AddressTaken.count(V: Alias->getAliaseeGUID()))
2218 return true;
2219 return false;
2220 };
2221 for (auto *FuncMD : CfiFunctionsMD->operands()) {
2222 assert(FuncMD->getNumOperands() >= 2);
2223 StringRef FunctionName =
2224 cast<MDString>(Val: FuncMD->getOperand(I: 0))->getString();
2225 CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>(
2226 cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 1))
2227 ->getValue()
2228 ->getUniqueInteger()
2229 .getZExtValue());
2230 const GlobalValue::GUID GUID =
2231 cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 2))
2232 ->getValue()
2233 ->getUniqueInteger()
2234 .getZExtValue();
2235 // Do not emit jumptable entries for functions that are not-live and
2236 // have no live references (and are not exported with cross-DSO CFI.)
2237 if (!ExportSummary->isGUIDLive(GUID))
2238 continue;
2239 if (!IsAddressTaken(GUID)) {
2240 if (!CrossDsoCfi || Linkage != CFL_Definition)
2241 continue;
2242
2243 bool Exported = false;
2244 if (auto VI = ExportSummary->getValueInfo(GUID))
2245 for (const auto &GVS : VI.getSummaryList())
2246 if (GVS->isLive() && !GlobalValue::isLocalLinkage(Linkage: GVS->linkage()))
2247 Exported = true;
2248
2249 if (!Exported)
2250 continue;
2251 }
2252 auto P = ExportedFunctions.insert(KV: {FunctionName, {.Linkage: Linkage, .FuncMD: FuncMD}});
2253 if (!P.second && P.first->second.Linkage != CFL_Definition)
2254 P.first->second = {.Linkage: Linkage, .FuncMD: FuncMD};
2255 }
2256
2257 for (const auto &P : ExportedFunctions) {
2258 StringRef FunctionName = P.first;
2259 CfiFunctionLinkage Linkage = P.second.Linkage;
2260 MDNode *FuncMD = P.second.FuncMD;
2261 Function *F = M.getFunction(Name: FunctionName);
2262 if (F && F->hasLocalLinkage()) {
2263 // Locally defined function that happens to have the same name as a
2264 // function defined in a ThinLTO module. Rename it to move it out of
2265 // the way of the external reference that we're about to create.
2266 // Note that setName will find a unique name for the function, so even
2267 // if there is an existing function with the suffix there won't be a
2268 // name collision.
2269 F->setName(F->getName() + ".1");
2270 F = nullptr;
2271 }
2272
2273 if (!F)
2274 F = Function::Create(
2275 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), isVarArg: false),
2276 Linkage: GlobalVariable::ExternalLinkage,
2277 AddrSpace: M.getDataLayout().getProgramAddressSpace(), N: FunctionName, M: &M);
2278
2279 // If the function is available_externally, remove its definition so
2280 // that it is handled the same way as a declaration. Later we will try
2281 // to create an alias using this function's linkage, which will fail if
2282 // the linkage is available_externally. This will also result in us
2283 // following the code path below to replace the type metadata.
2284 if (F->hasAvailableExternallyLinkage()) {
2285 F->setLinkage(GlobalValue::ExternalLinkage);
2286 F->deleteBody();
2287 F->setComdat(nullptr);
2288 F->clearMetadata();
2289 }
2290
2291 // Update the linkage for extern_weak declarations when a definition
2292 // exists.
2293 if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
2294 F->setLinkage(GlobalValue::ExternalLinkage);
2295
2296 // If the function in the full LTO module is a declaration, replace its
2297 // type metadata with the type metadata we found in cfi.functions. That
2298 // metadata is presumed to be more accurate than the metadata attached
2299 // to the declaration.
2300 if (F->isDeclaration()) {
2301 if (Linkage == CFL_WeakDeclaration)
2302 F->setLinkage(GlobalValue::ExternalWeakLinkage);
2303
2304 F->eraseMetadata(KindID: LLVMContext::MD_type);
2305 for (unsigned I = 3; I < FuncMD->getNumOperands(); ++I)
2306 F->addMetadata(KindID: LLVMContext::MD_type,
2307 MD&: *cast<MDNode>(Val: FuncMD->getOperand(I).get()));
2308 }
2309 }
2310 }
2311 }
2312
2313 struct AliasToCreate {
2314 Function *Alias;
2315 std::string TargetName;
2316 };
2317 std::vector<AliasToCreate> AliasesToCreate;
2318
2319 // Parse alias data to replace stand-in function declarations for aliases
2320 // with an alias to the intended target.
2321 if (ExportSummary) {
2322 if (NamedMDNode *AliasesMD = M.getNamedMetadata(Name: "aliases")) {
2323 for (auto *AliasMD : AliasesMD->operands()) {
2324 SmallVector<Function *> Aliases;
2325 for (Metadata *MD : AliasMD->operands()) {
2326 auto *MDS = dyn_cast<MDString>(Val: MD);
2327 if (!MDS)
2328 continue;
2329 StringRef AliasName = MDS->getString();
2330 if (!ExportedFunctions.count(Key: AliasName))
2331 continue;
2332 auto *AliasF = M.getFunction(Name: AliasName);
2333 if (AliasF)
2334 Aliases.push_back(Elt: AliasF);
2335 }
2336
2337 if (Aliases.empty())
2338 continue;
2339
2340 for (unsigned I = 1; I != Aliases.size(); ++I) {
2341 auto *AliasF = Aliases[I];
2342 ExportedFunctions.erase(Key: AliasF->getName());
2343 AliasesToCreate.push_back(
2344 x: {.Alias: AliasF, .TargetName: std::string(Aliases[0]->getName())});
2345 }
2346 }
2347 }
2348 }
2349
2350 DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
2351 for (GlobalObject &GO : M.global_objects()) {
2352 if (isa<GlobalVariable>(Val: GO) && GO.isDeclarationForLinker())
2353 continue;
2354
2355 Types.clear();
2356 GO.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
2357
2358 bool IsJumpTableCanonical = false;
2359 bool IsExported = false;
2360 if (Function *F = dyn_cast<Function>(Val: &GO)) {
2361 IsJumpTableCanonical = isJumpTableCanonical(F);
2362 if (auto It = ExportedFunctions.find(Key: F->getName());
2363 It != ExportedFunctions.end()) {
2364 IsJumpTableCanonical |= It->second.Linkage == CFL_Definition;
2365 IsExported = true;
2366 // TODO: The logic here checks only that the function is address taken,
2367 // not that the address takers are live. This can be updated to check
2368 // their liveness and emit fewer jumptable entries once monolithic LTO
2369 // builds also emit summaries.
2370 } else if (!F->hasAddressTaken()) {
2371 if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
2372 continue;
2373 }
2374 }
2375
2376 auto *GTM = GlobalTypeMember::create(Alloc, GO: &GO, IsJumpTableCanonical,
2377 IsExported, Types);
2378 GlobalTypeMembers[&GO] = GTM;
2379 for (MDNode *Type : Types) {
2380 verifyTypeMDNode(GO: &GO, Type);
2381 auto &Info = TypeIdInfo[Type->getOperand(I: 1)];
2382 Info.UniqueId = ++CurUniqueId;
2383 Info.RefGlobals.push_back(x: GTM);
2384 }
2385 }
2386
2387 auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
2388 // Add the call site to the list of call sites for this type identifier. We
2389 // also use TypeIdUsers to keep track of whether we have seen this type
2390 // identifier before. If we have, we don't need to re-add the referenced
2391 // globals to the equivalence class.
2392 auto Ins = TypeIdUsers.insert(KV: {TypeId, {}});
2393 if (Ins.second) {
2394 // Add the type identifier to the equivalence class.
2395 auto &GCI = GlobalClasses.insert(Data: TypeId);
2396 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(ECV: GCI);
2397
2398 // Add the referenced globals to the type identifier's equivalence class.
2399 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2400 CurSet = GlobalClasses.unionSets(
2401 L1: CurSet, L2: GlobalClasses.findLeader(ECV: GlobalClasses.insert(Data: GTM)));
2402 }
2403
2404 return Ins.first->second;
2405 };
2406
2407 if (TypeTestFunc) {
2408 for (const Use &U : TypeTestFunc->uses()) {
2409 auto CI = cast<CallInst>(Val: U.getUser());
2410 // If this type test is only used by llvm.assume instructions, it
2411 // was used for whole program devirtualization, and is being kept
2412 // for use by other optimization passes. We do not need or want to
2413 // lower it here. We also don't want to rewrite any associated globals
2414 // unnecessarily. These will be removed by a subsequent LTT invocation
2415 // with the DropTypeTests flag set.
2416 bool OnlyAssumeUses = !CI->use_empty();
2417 for (const Use &CIU : CI->uses()) {
2418 if (isa<AssumeInst>(Val: CIU.getUser()))
2419 continue;
2420 OnlyAssumeUses = false;
2421 break;
2422 }
2423 if (OnlyAssumeUses)
2424 continue;
2425
2426 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
2427 if (!TypeIdMDVal)
2428 report_fatal_error(reason: "Second argument of llvm.type.test must be metadata");
2429 auto TypeId = TypeIdMDVal->getMetadata();
2430 AddTypeIdUse(TypeId).CallSites.push_back(x: CI);
2431 }
2432 }
2433
2434 if (ICallBranchFunnelFunc) {
2435 for (const Use &U : ICallBranchFunnelFunc->uses()) {
2436 if (Arch != Triple::x86_64)
2437 report_fatal_error(
2438 reason: "llvm.icall.branch.funnel not supported on this target");
2439
2440 auto CI = cast<CallInst>(Val: U.getUser());
2441
2442 std::vector<GlobalTypeMember *> Targets;
2443 if (CI->arg_size() % 2 != 1)
2444 report_fatal_error(reason: "number of arguments should be odd");
2445
2446 GlobalClassesTy::member_iterator CurSet;
2447 for (unsigned I = 1; I != CI->arg_size(); I += 2) {
2448 int64_t Offset;
2449 auto *Base = dyn_cast<GlobalObject>(Val: GetPointerBaseWithConstantOffset(
2450 Ptr: CI->getOperand(i_nocapture: I), Offset, DL: M.getDataLayout()));
2451 if (!Base)
2452 report_fatal_error(
2453 reason: "Expected branch funnel operand to be global value");
2454
2455 GlobalTypeMember *GTM = GlobalTypeMembers[Base];
2456 Targets.push_back(x: GTM);
2457 GlobalClassesTy::member_iterator NewSet =
2458 GlobalClasses.findLeader(ECV: GlobalClasses.insert(Data: GTM));
2459 if (I == 1)
2460 CurSet = NewSet;
2461 else
2462 CurSet = GlobalClasses.unionSets(L1: CurSet, L2: NewSet);
2463 }
2464
2465 GlobalClasses.unionSets(
2466 L1: CurSet, L2: GlobalClasses.findLeader(
2467 ECV: GlobalClasses.insert(Data: ICallBranchFunnel::create(
2468 Alloc, CI, Targets, UniqueId: ++CurUniqueId))));
2469 }
2470 }
2471
2472 if (ExportSummary) {
2473 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
2474 for (auto &P : TypeIdInfo) {
2475 if (auto *TypeId = dyn_cast<MDString>(Val: P.first))
2476 MetadataByGUID[GlobalValue::getGUIDAssumingExternalLinkage(
2477 GlobalName: TypeId->getString())]
2478 .push_back(NewVal: TypeId);
2479 }
2480
2481 for (auto &P : *ExportSummary) {
2482 for (auto &S : P.second.getSummaryList()) {
2483 if (!ExportSummary->isGlobalValueLive(GVS: S.get()))
2484 continue;
2485 if (auto *FS = dyn_cast<FunctionSummary>(Val: S->getBaseObject()))
2486 for (GlobalValue::GUID G : FS->type_tests())
2487 for (Metadata *MD : MetadataByGUID[G])
2488 AddTypeIdUse(MD).IsExported = true;
2489 }
2490 }
2491 }
2492
2493 if (GlobalClasses.empty())
2494 return false;
2495
2496 {
2497 ScopedSaveAliaseesAndUsed S(M);
2498 // For each disjoint set we found...
2499 for (const auto &C : GlobalClasses) {
2500 if (!C->isLeader())
2501 continue;
2502
2503 ++NumTypeIdDisjointSets;
2504 // Build the list of type identifiers in this disjoint set.
2505 std::vector<Metadata *> TypeIds;
2506 std::vector<GlobalTypeMember *> Globals;
2507 std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2508 for (auto M : GlobalClasses.members(ECV: *C)) {
2509 if (isa<Metadata *>(Val: M))
2510 TypeIds.push_back(x: cast<Metadata *>(Val&: M));
2511 else if (isa<GlobalTypeMember *>(Val: M))
2512 Globals.push_back(x: cast<GlobalTypeMember *>(Val&: M));
2513 else
2514 ICallBranchFunnels.push_back(x: cast<ICallBranchFunnel *>(Val&: M));
2515 }
2516
2517 // Order type identifiers by unique ID for determinism. This ordering is
2518 // stable as there is a one-to-one mapping between metadata and unique
2519 // IDs.
2520 llvm::sort(C&: TypeIds, Comp: [&](Metadata *M1, Metadata *M2) {
2521 return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2522 });
2523
2524 // Same for the branch funnels.
2525 llvm::sort(C&: ICallBranchFunnels,
2526 Comp: [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2527 return F1->UniqueId < F2->UniqueId;
2528 });
2529
2530 // Build bitsets for this disjoint set.
2531 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2532 }
2533 }
2534
2535 allocateByteArrays();
2536
2537 for (auto A : AliasesToCreate) {
2538 auto *Target = M.getNamedValue(Name: A.TargetName);
2539 if (!isa<GlobalAlias>(Val: Target))
2540 continue;
2541 auto *AliasGA = GlobalAlias::create(Name: "", Aliasee: Target);
2542 AliasGA->setVisibility(A.Alias->getVisibility());
2543 AliasGA->setLinkage(A.Alias->getLinkage());
2544 AliasGA->takeName(V: A.Alias);
2545 A.Alias->replaceAllUsesWith(V: AliasGA);
2546 A.Alias->eraseFromParent();
2547 }
2548
2549 // Emit .symver directives for exported functions, if they exist.
2550 if (ExportSummary) {
2551 if (NamedMDNode *SymversMD = M.getNamedMetadata(Name: "symvers")) {
2552 for (auto *Symver : SymversMD->operands()) {
2553 assert(Symver->getNumOperands() >= 2);
2554 StringRef SymbolName =
2555 cast<MDString>(Val: Symver->getOperand(I: 0))->getString();
2556 StringRef Alias = cast<MDString>(Val: Symver->getOperand(I: 1))->getString();
2557
2558 if (!ExportedFunctions.count(Key: SymbolName))
2559 continue;
2560
2561 M.appendModuleInlineAsm(
2562 Asm: (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2563 }
2564 }
2565 }
2566
2567 return true;
2568}
2569
2570PreservedAnalyses LowerTypeTestsPass::run(Module &M,
2571 ModuleAnalysisManager &AM) {
2572 bool Changed;
2573 if (UseCommandLine)
2574 Changed = LowerTypeTestsModule::runForTesting(M, AM);
2575 else
2576 Changed = LowerTypeTestsModule(M, AM, ExportSummary, ImportSummary).lower();
2577 if (!Changed)
2578 return PreservedAnalyses::all();
2579 return PreservedAnalyses::none();
2580}
2581
2582void DropTypeTestsPass::printPipeline(
2583 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2584 static_cast<PassInfoMixin<DropTypeTestsPass> *>(this)->printPipeline(
2585 OS, MapClassName2PassName);
2586 OS << '<';
2587 switch (Kind) {
2588 case DropTestKind::Assume:
2589 OS << "assume";
2590 break;
2591 case DropTestKind::All:
2592 OS << "all";
2593 break;
2594 }
2595 OS << '>';
2596}
2597
2598PreservedAnalyses DropTypeTestsPass::run(Module &M, ModuleAnalysisManager &AM) {
2599 return dropTypeTests(M, ShouldDropAll: Kind == DropTestKind::All) ? PreservedAnalyses::none()
2600 : PreservedAnalyses::all();
2601}
2602
2603PreservedAnalyses SimplifyTypeTestsPass::run(Module &M,
2604 ModuleAnalysisManager &AM) {
2605 bool Changed = false;
2606 // Figure out whether inlining has exposed a constant address to a lowered
2607 // type test, and remove the test if so and the address is known to pass the
2608 // test. Unfortunately this pass ends up needing to reverse engineer what
2609 // LowerTypeTests did; this is currently inherent to the design of ThinLTO
2610 // importing where LowerTypeTests needs to run at the start.
2611 //
2612 // We look for things like:
2613 //
2614 // sub (i64 ptrtoint (ptr @_Z2fpv to i64), i64 ptrtoint (ptr
2615 // @__typeid__ZTSFvvE_global_addr to i64))
2616 //
2617 // which gets replaced with 0 if _Z2fpv (more specifically _Z2fpv.cfi, the
2618 // function referred to by the jump table) is a member of the type _ZTSFvv, as
2619 // well as things like
2620 //
2621 // icmp eq ptr @_Z2fpv, @__typeid__ZTSFvvE_global_addr
2622 //
2623 // which gets replaced with true if _Z2fpv is a member.
2624 for (auto &GV : M.globals()) {
2625 if (!GV.getName().starts_with(Prefix: "__typeid_") ||
2626 !GV.getName().ends_with(Suffix: "_global_addr"))
2627 continue;
2628 // __typeid_foo_global_addr -> foo
2629 auto *MD = MDString::get(Context&: M.getContext(),
2630 Str: GV.getName().substr(Start: 9, N: GV.getName().size() - 21));
2631 auto MaySimplifyPtr = [&](Value *Ptr) {
2632 if (auto *GV = dyn_cast<GlobalValue>(Val: Ptr))
2633 if (auto *CFIGV = M.getNamedValue(Name: (GV->getName() + ".cfi").str()))
2634 Ptr = CFIGV;
2635 return isKnownTypeIdMember(TypeId: MD, DL: M.getDataLayout(), V: Ptr, COffset: 0);
2636 };
2637 auto MaySimplifyInt = [&](Value *Op) {
2638 auto *PtrAsInt = dyn_cast<ConstantExpr>(Val: Op);
2639 if (!PtrAsInt || PtrAsInt->getOpcode() != Instruction::PtrToInt)
2640 return false;
2641 return MaySimplifyPtr(PtrAsInt->getOperand(i_nocapture: 0));
2642 };
2643 for (User *U : make_early_inc_range(Range: GV.users())) {
2644 if (auto *CI = dyn_cast<ICmpInst>(Val: U)) {
2645 if (CI->getPredicate() == CmpInst::ICMP_EQ &&
2646 MaySimplifyPtr(CI->getOperand(i_nocapture: 0))) {
2647 // This is an equality comparison (TypeTestResolution::Single case in
2648 // lowerTypeTestCall). In this case we just replace the comparison
2649 // with true.
2650 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
2651 CI->eraseFromParent();
2652 Changed = true;
2653 continue;
2654 }
2655 }
2656 auto *CE = dyn_cast<ConstantExpr>(Val: U);
2657 if (!CE || CE->getOpcode() != Instruction::PtrToInt)
2658 continue;
2659 for (Use &U : make_early_inc_range(Range: CE->uses())) {
2660 auto *CE = dyn_cast<ConstantExpr>(Val: U.getUser());
2661 if (U.getOperandNo() == 0 && CE &&
2662 CE->getOpcode() == Instruction::Sub &&
2663 MaySimplifyInt(CE->getOperand(i_nocapture: 1))) {
2664 // This is a computation of PtrOffset as generated by
2665 // LowerTypeTestsModule::lowerTypeTestCall above. If
2666 // isKnownTypeIdMember passes we just pretend it evaluated to 0. This
2667 // should cause later passes to remove the range and alignment checks.
2668 // The bitset checks won't be removed but those are uncommon.
2669 CE->replaceAllUsesWith(V: ConstantInt::get(Ty: CE->getType(), V: 0));
2670 Changed = true;
2671 }
2672 auto *CI = dyn_cast<ICmpInst>(Val: U.getUser());
2673 if (U.getOperandNo() == 1 && CI &&
2674 CI->getPredicate() == CmpInst::ICMP_EQ &&
2675 MaySimplifyInt(CI->getOperand(i_nocapture: 0))) {
2676 // This is an equality comparison. Unlike in the case above it
2677 // remained as an integer compare.
2678 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
2679 CI->eraseFromParent();
2680 Changed = true;
2681 }
2682 }
2683 }
2684 }
2685
2686 if (!Changed)
2687 return PreservedAnalyses::all();
2688 PreservedAnalyses PA = PreservedAnalyses::none();
2689 PA.preserve<DominatorTreeAnalysis>();
2690 PA.preserve<PostDominatorTreeAnalysis>();
2691 PA.preserve<LoopAnalysis>();
2692 return PA;
2693}
2694