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