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