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::getInBoundsGetElementPtr(
1176 Ty: NewInit->getType(), C: CombinedGlobal, IdxList: CombinedGlobalIdxs);
1177 assert(GV->getType()->getAddressSpace() == 0);
1178 GlobalAlias *GAlias =
1179 GlobalAlias::create(Ty: NewTy->getElementType(N: I * 2), AddressSpace: 0, Linkage: GV->getLinkage(),
1180 Name: "", Aliasee: CombinedGlobalElemPtr, Parent: &M);
1181 GAlias->setVisibility(GV->getVisibility());
1182 GAlias->takeName(V: GV);
1183 GV->replaceAllUsesWith(V: GAlias);
1184 GV->eraseFromParent();
1185 }
1186}
1187
1188bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
1189 return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
1190 ObjectFormat == Triple::ELF;
1191}
1192
1193/// Export the given type identifier so that ThinLTO backends may import it.
1194/// Type identifiers are exported by adding coarse-grained information about how
1195/// to test the type identifier to the summary, and creating symbols in the
1196/// object file (aliases and absolute symbols) containing fine-grained
1197/// information about the type identifier.
1198///
1199/// Returns a pointer to the location in which to store the bitmask, if
1200/// applicable.
1201uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
1202 const TypeIdLowering &TIL) {
1203 TypeTestResolution &TTRes =
1204 ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
1205 TTRes.TheKind = TIL.TheKind;
1206
1207 auto ExportGlobal = [&](StringRef Name, Constant *C) {
1208 GlobalAlias *GA =
1209 GlobalAlias::create(Ty: Int8Ty, AddressSpace: 0, Linkage: GlobalValue::ExternalLinkage,
1210 Name: "__typeid_" + TypeId + "_" + Name, Aliasee: C, Parent: &M);
1211 GA->setVisibility(GlobalValue::HiddenVisibility);
1212 };
1213
1214 auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
1215 if (shouldExportConstantsAsAbsoluteSymbols())
1216 ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Ty: PtrTy));
1217 else
1218 Storage = cast<ConstantInt>(Val: C)->getZExtValue();
1219 };
1220
1221 if (TIL.TheKind != TypeTestResolution::Unsat)
1222 ExportGlobal("global_addr", TIL.OffsetedGlobal);
1223
1224 if (TIL.TheKind == TypeTestResolution::ByteArray ||
1225 TIL.TheKind == TypeTestResolution::Inline ||
1226 TIL.TheKind == TypeTestResolution::AllOnes) {
1227 ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
1228 ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
1229
1230 uint64_t BitSize = cast<ConstantInt>(Val: TIL.SizeM1)->getZExtValue() + 1;
1231 if (TIL.TheKind == TypeTestResolution::Inline)
1232 TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
1233 else
1234 TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
1235 }
1236
1237 if (TIL.TheKind == TypeTestResolution::ByteArray) {
1238 ExportGlobal("byte_array", TIL.TheByteArray);
1239 if (shouldExportConstantsAsAbsoluteSymbols())
1240 ExportGlobal("bit_mask", TIL.BitMask);
1241 else
1242 return &TTRes.BitMask;
1243 }
1244
1245 if (TIL.TheKind == TypeTestResolution::Inline)
1246 ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
1247
1248 return nullptr;
1249}
1250
1251LowerTypeTestsModule::TypeIdLowering
1252LowerTypeTestsModule::importTypeId(StringRef TypeId) {
1253 const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
1254 if (!TidSummary)
1255 return {}; // Unsat: no globals match this type id.
1256 const TypeTestResolution &TTRes = TidSummary->TTRes;
1257
1258 TypeIdLowering TIL;
1259 TIL.TheKind = TTRes.TheKind;
1260
1261 auto ImportGlobal = [&](StringRef Name) {
1262 // Give the global a type of length 0 so that it is not assumed not to alias
1263 // with any other global.
1264 GlobalVariable *GV = M.getOrInsertGlobal(
1265 Name: ("__typeid_" + TypeId + "_" + Name).str(), Ty: Int8Arr0Ty);
1266 GV->setVisibility(GlobalValue::HiddenVisibility);
1267 return GV;
1268 };
1269
1270 auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
1271 Type *Ty) {
1272 if (!shouldExportConstantsAsAbsoluteSymbols()) {
1273 Constant *C =
1274 ConstantInt::get(Ty: isa<IntegerType>(Val: Ty) ? Ty : Int64Ty, V: Const);
1275 if (!isa<IntegerType>(Val: Ty))
1276 C = ConstantExpr::getIntToPtr(C, Ty);
1277 return C;
1278 }
1279
1280 Constant *C = ImportGlobal(Name);
1281 auto *GV = cast<GlobalVariable>(Val: C->stripPointerCasts());
1282 if (isa<IntegerType>(Val: Ty))
1283 C = ConstantExpr::getPtrToInt(C, Ty);
1284 if (GV->getMetadata(KindID: LLVMContext::MD_absolute_symbol))
1285 return C;
1286
1287 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1288 auto *MinC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Min));
1289 auto *MaxC = ConstantAsMetadata::get(C: ConstantInt::get(Ty: IntPtrTy, V: Max));
1290 GV->setMetadata(KindID: LLVMContext::MD_absolute_symbol,
1291 Node: MDNode::get(Context&: M.getContext(), MDs: {MinC, MaxC}));
1292 };
1293 if (AbsWidth == IntPtrTy->getBitWidth()) {
1294 uint64_t AllOnes = IntPtrTy->getBitMask();
1295 SetAbsRange(AllOnes, AllOnes); // Full set.
1296 } else {
1297 SetAbsRange(0, 1ull << AbsWidth);
1298 }
1299 return C;
1300 };
1301
1302 if (TIL.TheKind != TypeTestResolution::Unsat) {
1303 auto *GV = ImportGlobal("global_addr");
1304 // This is either a vtable (in .data.rel.ro) or a jump table (in .text).
1305 // Either way it's expected to be in the low 2 GiB, so set the small code
1306 // model.
1307 //
1308 // For .data.rel.ro, we currently place all such sections in the low 2 GiB
1309 // [1], and for .text the sections are expected to be in the low 2 GiB under
1310 // the small and medium code models [2] and this pass only supports those
1311 // code models (e.g. jump tables use jmp instead of movabs/jmp).
1312 //
1313 // [1]https://github.com/llvm/llvm-project/pull/137742
1314 // [2]https://maskray.me/blog/2023-05-14-relocation-overflow-and-code-models
1315 GV->setCodeModel(CodeModel::Small);
1316 TIL.OffsetedGlobal = GV;
1317 }
1318
1319 if (TIL.TheKind == TypeTestResolution::ByteArray ||
1320 TIL.TheKind == TypeTestResolution::Inline ||
1321 TIL.TheKind == TypeTestResolution::AllOnes) {
1322 TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, IntPtrTy);
1323 TIL.SizeM1 =
1324 ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
1325 }
1326
1327 if (TIL.TheKind == TypeTestResolution::ByteArray) {
1328 TIL.TheByteArray = ImportGlobal("byte_array");
1329 TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, PtrTy);
1330 }
1331
1332 if (TIL.TheKind == TypeTestResolution::Inline)
1333 TIL.InlineBits = ImportConstant(
1334 "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
1335 TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
1336
1337 return TIL;
1338}
1339
1340void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
1341 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
1342 if (!TypeIdMDVal)
1343 report_fatal_error(reason: "Second argument of llvm.type.test must be metadata");
1344
1345 auto TypeIdStr = dyn_cast<MDString>(Val: TypeIdMDVal->getMetadata());
1346 // If this is a local unpromoted type, which doesn't have a metadata string,
1347 // treat as Unknown and delay lowering, so that we can still utilize it for
1348 // later optimizations.
1349 if (!TypeIdStr)
1350 return;
1351
1352 TypeIdLowering TIL = importTypeId(TypeId: TypeIdStr->getString());
1353 Value *Lowered = lowerTypeTestCall(TypeId: TypeIdStr, CI, TIL);
1354 if (Lowered) {
1355 CI->replaceAllUsesWith(V: Lowered);
1356 CI->eraseFromParent();
1357 }
1358}
1359
1360void LowerTypeTestsModule::maybeReplaceComdat(Function *F,
1361 StringRef OriginalName) {
1362 // For COFF we should also rename the comdat if this function also
1363 // happens to be the key function. Even if the comdat name changes, this
1364 // should still be fine since comdat and symbol resolution happens
1365 // before LTO, so all symbols which would prevail have been selected.
1366 if (F->hasComdat() && ObjectFormat == Triple::COFF &&
1367 F->getComdat()->getName() == OriginalName) {
1368 Comdat *OldComdat = F->getComdat();
1369 Comdat *NewComdat = M.getOrInsertComdat(Name: F->getName());
1370 for (GlobalObject &GO : M.global_objects()) {
1371 if (GO.getComdat() == OldComdat)
1372 GO.setComdat(NewComdat);
1373 }
1374 }
1375}
1376
1377// ThinLTO backend: the function F has a jump table entry; update this module
1378// accordingly. isJumpTableCanonical describes the type of the jump table entry.
1379void LowerTypeTestsModule::importFunction(Function *F,
1380 bool isJumpTableCanonical) {
1381 assert(F->getType()->getAddressSpace() == 0);
1382
1383 GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1384 std::string Name = std::string(F->getName());
1385
1386 if (F->isDeclarationForLinker() && isJumpTableCanonical) {
1387 // Non-dso_local functions may be overriden at run time,
1388 // don't short curcuit them
1389 if (!F->isDSOLocal())
1390 return;
1391 if (F->isDeclaration()) {
1392 // Direct calls do not need the type check, so let them skip the jump
1393 // table and call the real function directly.
1394 Function *RealF = Function::Create(Ty: F->getFunctionType(),
1395 Linkage: GlobalValue::ExternalLinkage,
1396 AddrSpace: F->getAddressSpace(),
1397 N: Name + ".cfi", M: &M);
1398 RealF->setVisibility(GlobalVariable::HiddenVisibility);
1399 replaceDirectCalls(Old: F, New: RealF);
1400 return;
1401 }
1402 // Otherwise F is an available_externally definition imported from
1403 // another module. Handle it like a local definition below: the body is
1404 // renamed to Name.cfi and stays the target of direct calls, so it remains
1405 // inlinable, while address-taken uses are redirected to the jump table
1406 // entry. If the body is not inlined and is dropped later, the reference
1407 // to Name.cfi resolves to the real function at link time, exactly as for
1408 // a declaration.
1409 }
1410
1411 Function *FDecl;
1412 if (!isJumpTableCanonical) {
1413 // Either a declaration of an external function or a reference to a locally
1414 // defined jump table.
1415 FDecl = Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1416 AddrSpace: F->getAddressSpace(), N: Name + ".cfi_jt", M: &M);
1417 FDecl->setVisibility(GlobalValue::HiddenVisibility);
1418 } else {
1419 F->setName(Name + ".cfi");
1420 maybeReplaceComdat(F, OriginalName: Name);
1421 FDecl = Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1422 AddrSpace: F->getAddressSpace(), N: Name, M: &M);
1423 FDecl->setVisibility(Visibility);
1424 FDecl->setDSOLocal(F->isDSOLocal());
1425 Visibility = GlobalValue::HiddenVisibility;
1426
1427 // Update aliases pointing to this function to also include the ".cfi" suffix,
1428 // We expect the jump table entry to either point to the real function or an
1429 // alias. Redirect all other users to the jump table entry.
1430 for (auto &U : F->uses()) {
1431 if (auto *A = dyn_cast<GlobalAlias>(Val: U.getUser())) {
1432 std::string AliasName = A->getName().str() + ".cfi";
1433 Function *AliasDecl = Function::Create(
1434 Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalLinkage,
1435 AddrSpace: F->getAddressSpace(), N: "", M: &M);
1436 AliasDecl->takeName(V: A);
1437 A->replaceAllUsesWith(V: AliasDecl);
1438 A->setName(AliasName);
1439 AliasDecl->setDSOLocal(A->isDSOLocal());
1440 }
1441 }
1442 }
1443
1444 if (F->hasExternalWeakLinkage())
1445 replaceWeakDeclarationWithJumpTablePtr(F, JT: FDecl, IsJumpTableCanonical: isJumpTableCanonical);
1446 else
1447 replaceCfiUses(Old: F, New: FDecl, IsJumpTableCanonical: isJumpTableCanonical);
1448
1449 // Set visibility late because it's used in replaceCfiUses() to determine
1450 // whether uses need to be replaced.
1451 F->setVisibility(Visibility);
1452}
1453
1454static auto
1455buildBitSets(ArrayRef<Metadata *> TypeIds,
1456 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1457 DenseMap<Metadata *, SmallVector<uint64_t, 16>> OffsetsByTypeID;
1458 // Pre-populate the map with interesting type identifiers.
1459 for (Metadata *TypeId : TypeIds)
1460 OffsetsByTypeID[TypeId];
1461 for (const auto &[Mem, MemOff] : GlobalLayout) {
1462 for (MDNode *Type : Mem->types()) {
1463 auto It = OffsetsByTypeID.find(Val: Type->getOperand(I: 1));
1464 if (It == OffsetsByTypeID.end())
1465 continue;
1466 uint64_t Offset =
1467 cast<ConstantInt>(
1468 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
1469 ->getZExtValue();
1470 It->second.push_back(Elt: MemOff + Offset);
1471 }
1472 }
1473
1474 SmallVector<std::pair<Metadata *, BitSetInfo>> BitSets;
1475 BitSets.reserve(N: TypeIds.size());
1476 for (Metadata *TypeId : TypeIds) {
1477 BitSets.emplace_back(Args&: TypeId, Args: buildBitSet(Offsets: OffsetsByTypeID[TypeId]));
1478 LLVM_DEBUG({
1479 if (auto MDS = dyn_cast<MDString>(TypeId))
1480 dbgs() << MDS->getString() << ": ";
1481 else
1482 dbgs() << "<unnamed>: ";
1483 BitSets.back().second.print(dbgs());
1484 });
1485 }
1486
1487 return BitSets;
1488}
1489
1490void LowerTypeTestsModule::lowerTypeTestCalls(
1491 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1492 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1493 // For each type identifier in this disjoint set...
1494 for (const auto &[TypeId, BSI] : buildBitSets(TypeIds, GlobalLayout)) {
1495 ByteArrayInfo *BAI = nullptr;
1496 TypeIdLowering TIL;
1497
1498 uint64_t GlobalOffset =
1499 BSI.ByteOffset + ((BSI.BitSize - 1) << BSI.AlignLog2);
1500 TIL.OffsetedGlobal = ConstantExpr::getPtrAdd(
1501 Ptr: CombinedGlobalAddr, Offset: ConstantInt::get(Ty: IntPtrTy, V: GlobalOffset)),
1502 TIL.AlignLog2 = ConstantInt::get(Ty: IntPtrTy, V: BSI.AlignLog2);
1503 TIL.SizeM1 = ConstantInt::get(Ty: IntPtrTy, V: BSI.BitSize - 1);
1504 if (BSI.isAllOnes()) {
1505 TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1506 : TypeTestResolution::AllOnes;
1507 } else if (BSI.BitSize <= IntPtrTy->getBitWidth()) {
1508 TIL.TheKind = TypeTestResolution::Inline;
1509 uint64_t InlineBits = 0;
1510 for (auto Bit : BSI.Bits)
1511 InlineBits |= uint64_t(1) << Bit;
1512 if (InlineBits == 0)
1513 TIL.TheKind = TypeTestResolution::Unsat;
1514 else
1515 TIL.InlineBits = ConstantInt::get(
1516 Ty: (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, V: InlineBits);
1517 } else {
1518 TIL.TheKind = TypeTestResolution::ByteArray;
1519 ++NumByteArraysCreated;
1520 BAI = createByteArray(BSI);
1521 TIL.TheByteArray = BAI->ByteArray;
1522 TIL.BitMask = BAI->MaskGlobal;
1523 }
1524
1525 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1526
1527 if (TIUI.IsExported) {
1528 uint8_t *MaskPtr = exportTypeId(TypeId: cast<MDString>(Val: TypeId)->getString(), TIL);
1529 if (BAI)
1530 BAI->MaskPtr = MaskPtr;
1531 }
1532
1533 // Lower each call to llvm.type.test for this type identifier.
1534 for (CallInst *CI : TIUI.CallSites) {
1535 ++NumTypeTestCallsLowered;
1536 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1537 if (Lowered) {
1538 CI->replaceAllUsesWith(V: Lowered);
1539 CI->eraseFromParent();
1540 }
1541 }
1542 }
1543}
1544
1545void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1546 if (Type->getNumOperands() != 2)
1547 report_fatal_error(reason: "All operands of type metadata must have 2 elements");
1548
1549 if (GO->isThreadLocal())
1550 report_fatal_error(reason: "Bit set element may not be thread-local");
1551 if (isa<GlobalVariable>(Val: GO) && GO->hasSection())
1552 report_fatal_error(
1553 reason: "A member of a type identifier may not have an explicit section");
1554
1555 // FIXME: We previously checked that global var member of a type identifier
1556 // must be a definition, but the IR linker may leave type metadata on
1557 // declarations. We should restore this check after fixing PR31759.
1558
1559 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0));
1560 if (!OffsetConstMD)
1561 report_fatal_error(reason: "Type offset must be a constant");
1562 auto OffsetInt = dyn_cast<ConstantInt>(Val: OffsetConstMD->getValue());
1563 if (!OffsetInt)
1564 report_fatal_error(reason: "Type offset must be an integer constant");
1565}
1566
1567static const unsigned kX86JumpTableEntrySize = 8;
1568static const unsigned kX86IBTJumpTableEntrySize = 16;
1569static const unsigned kARMJumpTableEntrySize = 4;
1570static const unsigned kARMBTIJumpTableEntrySize = 8;
1571static const unsigned kARMv6MJumpTableEntrySize = 16;
1572static const unsigned kRISCVJumpTableEntrySize = 8;
1573static const unsigned kLOONGARCH64JumpTableEntrySize = 8;
1574static const unsigned kHexagonJumpTableEntrySize = 4;
1575
1576bool LowerTypeTestsModule::hasBranchTargetEnforcement() {
1577 if (HasBranchTargetEnforcement == -1) {
1578 // First time this query has been called. Find out the answer by checking
1579 // the module flags.
1580 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1581 MD: M.getModuleFlag(Key: "branch-target-enforcement")))
1582 HasBranchTargetEnforcement = !BTE->isZero();
1583 else
1584 HasBranchTargetEnforcement = 0;
1585 }
1586 return HasBranchTargetEnforcement;
1587}
1588
1589unsigned
1590LowerTypeTestsModule::getJumpTableEntrySize(Triple::ArchType JumpTableArch) {
1591 switch (JumpTableArch) {
1592 case Triple::x86:
1593 case Triple::x86_64:
1594 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1595 MD: M.getModuleFlag(Key: "cf-protection-branch")))
1596 if (MD->getZExtValue())
1597 return kX86IBTJumpTableEntrySize;
1598 return kX86JumpTableEntrySize;
1599 case Triple::arm:
1600 return kARMJumpTableEntrySize;
1601 case Triple::thumb:
1602 if (CanUseThumbBWJumpTable) {
1603 if (hasBranchTargetEnforcement())
1604 return kARMBTIJumpTableEntrySize;
1605 return kARMJumpTableEntrySize;
1606 } else {
1607 return kARMv6MJumpTableEntrySize;
1608 }
1609 case Triple::aarch64:
1610 if (hasBranchTargetEnforcement())
1611 return kARMBTIJumpTableEntrySize;
1612 return kARMJumpTableEntrySize;
1613 case Triple::riscv32:
1614 case Triple::riscv64:
1615 return kRISCVJumpTableEntrySize;
1616 case Triple::loongarch64:
1617 return kLOONGARCH64JumpTableEntrySize;
1618 case Triple::hexagon:
1619 return kHexagonJumpTableEntrySize;
1620 default:
1621 report_fatal_error(reason: "Unsupported architecture for jump tables");
1622 }
1623}
1624
1625// Create an inline asm constant representing a jump table entry for the target.
1626// This consists of an instruction sequence containing a relative branch to
1627// Dest.
1628InlineAsm *
1629LowerTypeTestsModule::createJumpTableEntryAsm(Triple::ArchType JumpTableArch) {
1630 std::string Asm;
1631 raw_string_ostream AsmOS(Asm);
1632
1633 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1634 bool Endbr = false;
1635 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1636 MD: M.getModuleFlag(Key: "cf-protection-branch")))
1637 Endbr = !MD->isZero();
1638 if (Endbr)
1639 AsmOS << (JumpTableArch == Triple::x86 ? "endbr32\n" : "endbr64\n");
1640 AsmOS << "jmp ${0:c}@plt\n";
1641 if (Endbr)
1642 AsmOS << ".balign 16, 0xcc\n";
1643 else
1644 AsmOS << "int3\nint3\nint3\n";
1645 } else if (JumpTableArch == Triple::arm) {
1646 AsmOS << "b $0\n";
1647 } else if (JumpTableArch == Triple::aarch64) {
1648 if (hasBranchTargetEnforcement())
1649 AsmOS << "bti c\n";
1650 AsmOS << "b $0\n";
1651 } else if (JumpTableArch == Triple::thumb) {
1652 if (!CanUseThumbBWJumpTable) {
1653 // In Armv6-M, this sequence will generate a branch without corrupting
1654 // any registers. We use two stack words; in the second, we construct the
1655 // address we'll pop into pc, and the first is used to save and restore
1656 // r0 which we use as a temporary register.
1657 //
1658 // To support position-independent use cases, the offset of the target
1659 // function is stored as a relative offset (which will expand into an
1660 // R_ARM_REL32 relocation in ELF, and presumably the equivalent in other
1661 // object file types), and added to pc after we load it. (The alternative
1662 // B.W is automatically pc-relative.)
1663 //
1664 // There are five 16-bit Thumb instructions here, so the .balign 4 adds a
1665 // sixth halfword of padding, and then the offset consumes a further 4
1666 // bytes, for a total of 16, which is very convenient since entries in
1667 // this jump table need to have power-of-two size.
1668 AsmOS << "push {r0,r1}\n"
1669 << "ldr r0, 1f\n"
1670 << "0: add r0, r0, pc\n"
1671 << "str r0, [sp, #4]\n"
1672 << "pop {r0,pc}\n"
1673 << ".balign 4\n"
1674 << "1: .word $0 - (0b + 4)\n";
1675 } else {
1676 if (hasBranchTargetEnforcement())
1677 AsmOS << "bti\n";
1678 AsmOS << "b.w $0\n";
1679 }
1680 } else if (JumpTableArch == Triple::riscv32 ||
1681 JumpTableArch == Triple::riscv64) {
1682 AsmOS << "tail $0@plt\n";
1683 } else if (JumpTableArch == Triple::loongarch64) {
1684 AsmOS << "pcalau12i $$t0, %pc_hi20($0)\n"
1685 << "jirl $$r0, $$t0, %pc_lo12($0)\n";
1686 } else if (JumpTableArch == Triple::hexagon) {
1687 AsmOS << "jump $0\n";
1688 } else {
1689 report_fatal_error(reason: "Unsupported architecture for jump tables");
1690 }
1691
1692 return InlineAsm::get(
1693 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), Params: PtrTy, isVarArg: false),
1694 AsmString: AsmOS.str(), Constraints: "s",
1695 /*hasSideEffects=*/true);
1696}
1697
1698/// Given a disjoint set of type identifiers and functions, build the bit sets
1699/// and lower the llvm.type.test calls, architecture dependently.
1700void LowerTypeTestsModule::buildBitSetsFromFunctions(
1701 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1702 if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1703 Arch == Triple::thumb || Arch == Triple::aarch64 ||
1704 Arch == Triple::riscv32 || Arch == Triple::riscv64 ||
1705 Arch == Triple::loongarch64 || Arch == Triple::hexagon)
1706 buildBitSetsFromFunctionsNative(TypeIds, Functions);
1707 else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1708 buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1709 else
1710 report_fatal_error(reason: "Unsupported architecture for jump tables");
1711}
1712
1713void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1714 GlobalVariable *GV) {
1715 if (WeakInitializerFn == nullptr) {
1716 WeakInitializerFn = Function::Create(
1717 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()),
1718 /* IsVarArg */ isVarArg: false),
1719 Linkage: GlobalValue::InternalLinkage,
1720 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
1721 N: "__cfi_global_var_init", M: &M);
1722 BasicBlock *BB =
1723 BasicBlock::Create(Context&: M.getContext(), Name: "entry", Parent: WeakInitializerFn);
1724 ReturnInst::Create(C&: M.getContext(), InsertAtEnd: BB);
1725 WeakInitializerFn->setSection(
1726 ObjectFormat == Triple::MachO
1727 ? "__TEXT,__StaticInit,regular,pure_instructions"
1728 : ".text.startup");
1729 // This code is equivalent to relocation application, and should run at the
1730 // earliest possible time (i.e. with the highest priority).
1731 appendToGlobalCtors(M, F: WeakInitializerFn, /* Priority */ 0);
1732 }
1733
1734 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1735 GV->setConstant(false);
1736 IRB.CreateAlignedStore(Val: GV->getInitializer(), Ptr: GV, Align: GV->getAlign());
1737 GV->setInitializer(Constant::getNullValue(Ty: GV->getValueType()));
1738}
1739
1740void LowerTypeTestsModule::findGlobalVariableUsersOf(
1741 Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
1742 for (auto *U : C->users()){
1743 if (auto *GV = dyn_cast<GlobalVariable>(Val: U))
1744 Out.insert(X: GV);
1745 else if (auto *C2 = dyn_cast<Constant>(Val: U))
1746 findGlobalVariableUsersOf(C: C2, Out);
1747 }
1748}
1749
1750// Replace all uses of F with (F ? JT : 0).
1751void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1752 Function *F, Constant *JT, bool IsJumpTableCanonical) {
1753 // The target expression can not appear in a constant initializer on most
1754 // (all?) targets. Switch to a runtime initializer.
1755 SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
1756 findGlobalVariableUsersOf(C: F, Out&: GlobalVarUsers);
1757 for (auto *GV : GlobalVarUsers) {
1758 if (GV == GlobalAnnotation)
1759 continue;
1760 moveInitializerToModuleConstructor(GV);
1761 }
1762
1763 // Can not RAUW F with an expression that uses F. Replace with a temporary
1764 // placeholder first.
1765 Function *PlaceholderFn =
1766 Function::Create(Ty: F->getFunctionType(), Linkage: GlobalValue::ExternalWeakLinkage,
1767 AddrSpace: F->getAddressSpace(), N: "", M: &M);
1768 replaceCfiUses(Old: F, New: PlaceholderFn, IsJumpTableCanonical);
1769
1770 convertUsersOfConstantsToInstructions(Consts: PlaceholderFn);
1771 // Don't use range based loop, because use list will be modified.
1772 while (!PlaceholderFn->use_empty()) {
1773 Use &U = *PlaceholderFn->use_begin();
1774 auto *InsertPt = dyn_cast<Instruction>(Val: U.getUser());
1775 assert(InsertPt && "Non-instruction users should have been eliminated");
1776 auto *PN = dyn_cast<PHINode>(Val: InsertPt);
1777 if (PN)
1778 InsertPt = PN->getIncomingBlock(U)->getTerminator();
1779 IRBuilder Builder(InsertPt);
1780 Value *ICmp = Builder.CreateICmp(P: CmpInst::ICMP_NE, LHS: F,
1781 RHS: Constant::getNullValue(Ty: F->getType()));
1782 Value *Select = Builder.CreateSelect(C: ICmp, True: JT,
1783 False: Constant::getNullValue(Ty: F->getType()));
1784
1785 if (auto *SI = dyn_cast<SelectInst>(Val: Select))
1786 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *SI, DEBUG_TYPE);
1787 // For phi nodes, we need to update the incoming value for all operands
1788 // with the same predecessor.
1789 if (PN)
1790 PN->setIncomingValueForBlock(BB: InsertPt->getParent(), V: Select);
1791 else
1792 U.set(Select);
1793 }
1794 PlaceholderFn->eraseFromParent();
1795}
1796
1797static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1798 Attribute TFAttr = F->getFnAttribute(Kind: "target-features");
1799 if (TFAttr.isValid()) {
1800 SmallVector<StringRef, 6> Features;
1801 TFAttr.getValueAsString().split(A&: Features, Separator: ',');
1802 for (StringRef Feature : Features) {
1803 if (Feature == "-thumb-mode")
1804 return false;
1805 else if (Feature == "+thumb-mode")
1806 return true;
1807 }
1808 }
1809
1810 return ModuleArch == Triple::thumb;
1811}
1812
1813// Each jump table must be either ARM or Thumb as a whole for the bit-test math
1814// to work. Pick one that matches the majority of members to minimize interop
1815// veneers inserted by the linker.
1816Triple::ArchType LowerTypeTestsModule::selectJumpTableArmEncoding(
1817 ArrayRef<GlobalTypeMember *> Functions) {
1818 if (Arch != Triple::arm && Arch != Triple::thumb)
1819 return Arch;
1820
1821 if (!CanUseThumbBWJumpTable && CanUseArmJumpTable) {
1822 // In architectures that provide Arm and Thumb-1 but not Thumb-2,
1823 // we should always prefer the Arm jump table format, because the
1824 // Thumb-1 one is larger and slower.
1825 return Triple::arm;
1826 }
1827
1828 // Otherwise, go with majority vote.
1829 unsigned ArmCount = 0, ThumbCount = 0;
1830 for (const auto GTM : Functions) {
1831 if (!GTM->isJumpTableCanonical()) {
1832 // PLT stubs are always ARM.
1833 // FIXME: This is the wrong heuristic for non-canonical jump tables.
1834 ++ArmCount;
1835 continue;
1836 }
1837
1838 Function *F = cast<Function>(Val: GTM->getGlobal());
1839 ++(isThumbFunction(F, ModuleArch: Arch) ? ThumbCount : ArmCount);
1840 }
1841
1842 return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1843}
1844
1845// Create location for each function entry which should look like this:
1846// frame #0: c::c() (.cfi_jt) at sanitizer/ubsan_interface.h:0:0
1847// frame #1: __ubsan_check_cfi_icall_jt at sanitizer/ubsan_interface.h:0
1848static SmallVector<DILocation *>
1849createJumpTableDebugInfo(Function *F, ArrayRef<GlobalTypeMember *> Functions) {
1850 Module &M = *F->getParent();
1851 DICompileUnit *CU = nullptr;
1852 auto CUs = M.debug_compile_units();
1853 if (!CUs.empty())
1854 CU = *CUs.begin();
1855
1856 DIBuilder DIB(M, /*AllowUnresolved=*/true, CU);
1857 DIFile *File = DIB.createFile(Filename: "ubsan_interface.h", Directory: "sanitizer");
1858 if (!CU) {
1859 // Synthetic module (like ld-temp.o), it frequently lacks a DICompileUnit
1860 // even if the rest of the program has debug info.
1861 CU = DIB.createCompileUnit(
1862 Lang: DISourceLanguageName(dwarf::DW_LANG_C), File, Producer: "llvm", isOptimized: true, Flags: "", RV: 0, SplitName: "",
1863 Kind: DICompileUnit::DebugEmissionKind::LineTablesOnly);
1864 }
1865
1866 DISubroutineType *DIFnTy = DIB.createSubroutineType(ParameterTypes: nullptr);
1867
1868 DISubprogram *UbsanSP = DIB.createFunction(
1869 Scope: CU, Name: "__ubsan_check_cfi_icall_jt", LinkageName: {}, File, LineNo: 0, Ty: DIFnTy, ScopeLine: 0,
1870 Flags: DINode::FlagArtificial, SPFlags: DISubprogram::SPFlagDefinition);
1871
1872 F->setSubprogram(UbsanSP);
1873
1874 DILocation *UbsanLoc = DILocation::get(Context&: M.getContext(), Line: 0, Column: 0, Scope: UbsanSP);
1875
1876 SmallVector<DILocation *> Locations;
1877 Locations.reserve(N: Functions.size());
1878
1879 for (auto *Func : Functions) {
1880 StringRef FuncName = Func->getGlobal()->getName();
1881 FuncName.consume_back(Suffix: ".cfi");
1882 DISubprogram *JumpSP = DIB.createFunction(
1883 Scope: CU, Name: (FuncName + ".cfi_jt").str(), LinkageName: {}, File, LineNo: 0, Ty: DIFnTy, ScopeLine: 0,
1884 Flags: DINode::FlagArtificial, SPFlags: DISubprogram::SPFlagDefinition);
1885
1886 DILocation *EntryLoc =
1887 DILocation::get(Context&: M.getContext(), Line: 0, Column: 0, Scope: JumpSP, InlinedAt: UbsanLoc);
1888
1889 Locations.push_back(Elt: EntryLoc);
1890 }
1891
1892 DIB.finalize();
1893
1894 return Locations;
1895}
1896
1897void LowerTypeTestsModule::createJumpTable(
1898 Function *F, ArrayRef<GlobalTypeMember *> Functions,
1899 Triple::ArchType JumpTableArch) {
1900 unsigned JumpTableEntrySize = getJumpTableEntrySize(JumpTableArch);
1901 // Give the jumptable section this type in order to enable jumptable
1902 // relaxation. Only do this if cross-DSO CFI is disabled because jumptable
1903 // relaxation violates cross-DSO CFI's restrictions on the ordering of the
1904 // jumptable relative to other sections.
1905 if (!CrossDsoCfi)
1906 F->setMetadata(KindID: LLVMContext::MD_elf_section_properties,
1907 Node: MDNode::get(Context&: F->getContext(),
1908 MDs: ArrayRef<Metadata *>{
1909 ConstantAsMetadata::get(C: ConstantInt::get(
1910 Ty: Int64Ty, V: ELF::SHT_LLVM_CFI_JUMP_TABLE)),
1911 ConstantAsMetadata::get(C: ConstantInt::get(
1912 Ty: Int64Ty, V: JumpTableEntrySize))}));
1913
1914 BasicBlock *BB = BasicBlock::Create(Context&: M.getContext(), Name: "entry", Parent: F);
1915 IRBuilder<> IRB(BB);
1916
1917 SmallVector<DILocation *> Locations;
1918 if (M.getDwarfVersion() != 0 && EnableJumpTableDebugInfo)
1919 Locations = createJumpTableDebugInfo(F, Functions);
1920
1921 InlineAsm *JumpTableAsm = createJumpTableEntryAsm(JumpTableArch);
1922
1923 // Check if all entries have the NoUnwind attribute.
1924 // If all entries have it, we can safely mark the
1925 // cfi.jumptable as NoUnwind, otherwise, direct calls
1926 // to the jump table will not handle exceptions properly
1927 bool areAllEntriesNounwind = true;
1928 assert(Locations.empty() || Functions.size() == Locations.size());
1929 for (auto [GTM, Loc] : zip_longest(t&: Functions, u&: Locations)) {
1930 if (Loc.has_value())
1931 IRB.SetCurrentDebugLocation(*Loc);
1932 if (!cast<Function>(Val: (*GTM)->getGlobal())
1933 ->hasFnAttribute(Kind: Attribute::NoUnwind)) {
1934 areAllEntriesNounwind = false;
1935 }
1936 IRB.CreateCall(Callee: JumpTableAsm, Args: (*GTM)->getGlobal());
1937 }
1938 IRB.CreateUnreachable();
1939
1940 // Align the whole table by entry size.
1941 F->setPreferredAlignment(Align(JumpTableEntrySize));
1942 F->addFnAttr(Kind: Attribute::Naked);
1943 if (JumpTableArch == Triple::arm)
1944 F->addFnAttr(Kind: "target-features", Val: "-thumb-mode");
1945 if (JumpTableArch == Triple::thumb) {
1946 if (hasBranchTargetEnforcement()) {
1947 // If we're generating a Thumb jump table with BTI, add a target-features
1948 // setting to ensure BTI can be assembled.
1949 F->addFnAttr(Kind: "target-features", Val: "+thumb-mode,+pacbti");
1950 } else {
1951 F->addFnAttr(Kind: "target-features", Val: "+thumb-mode");
1952 if (CanUseThumbBWJumpTable) {
1953 // Thumb jump table assembly needs Thumb2. The following attribute is
1954 // added by Clang for -march=armv7.
1955 F->addFnAttr(Kind: "target-cpu", Val: "cortex-a8");
1956 }
1957 }
1958 }
1959 // When -mbranch-protection= is used, the inline asm adds a BTI. Suppress BTI
1960 // for the function to avoid double BTI. This is a no-op without
1961 // -mbranch-protection=.
1962 if (JumpTableArch == Triple::aarch64 || JumpTableArch == Triple::thumb) {
1963 if (F->hasFnAttribute(Kind: "branch-target-enforcement"))
1964 F->removeFnAttr(Kind: "branch-target-enforcement");
1965 if (F->hasFnAttribute(Kind: "sign-return-address"))
1966 F->removeFnAttr(Kind: "sign-return-address");
1967 }
1968 if (JumpTableArch == Triple::riscv32 || JumpTableArch == Triple::riscv64) {
1969 // Make sure the jump table assembly is not modified by the assembler or
1970 // the linker.
1971 F->addFnAttr(Kind: "target-features", Val: "-c,-relax");
1972 }
1973 // When -fcf-protection= is used, the inline asm adds an ENDBR. Suppress ENDBR
1974 // for the function to avoid double ENDBR. This is a no-op without
1975 // -fcf-protection=.
1976 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64)
1977 F->addFnAttr(Kind: Attribute::NoCfCheck);
1978
1979 // Make sure we don't emit .eh_frame for this function if it isn't needed.
1980 if (areAllEntriesNounwind)
1981 F->addFnAttr(Kind: Attribute::NoUnwind);
1982
1983 // Make sure we do not inline any calls to the cfi.jumptable.
1984 F->addFnAttr(Kind: Attribute::NoInline);
1985}
1986
1987/// Given a disjoint set of type identifiers and functions, build a jump table
1988/// for the functions, build the bit sets and lower the llvm.type.test calls.
1989void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1990 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1991 // Unlike the global bitset builder, the function bitset builder cannot
1992 // re-arrange functions in a particular order and base its calculations on the
1993 // layout of the functions' entry points, as we have no idea how large a
1994 // particular function will end up being (the size could even depend on what
1995 // this pass does!) Instead, we build a jump table, which is a block of code
1996 // consisting of one branch instruction for each of the functions in the bit
1997 // set that branches to the target function, and redirect any taken function
1998 // addresses to the corresponding jump table entry. In the object file's
1999 // symbol table, the symbols for the target functions also refer to the jump
2000 // table entries, so that addresses taken outside the module will pass any
2001 // verification done inside the module.
2002 //
2003 // In more concrete terms, suppose we have three functions f, g, h which are
2004 // of the same type, and a function foo that returns their addresses:
2005 //
2006 // f:
2007 // mov 0, %eax
2008 // ret
2009 //
2010 // g:
2011 // mov 1, %eax
2012 // ret
2013 //
2014 // h:
2015 // mov 2, %eax
2016 // ret
2017 //
2018 // foo:
2019 // mov f, %eax
2020 // mov g, %edx
2021 // mov h, %ecx
2022 // ret
2023 //
2024 // We output the jump table as module-level inline asm string. The end result
2025 // will (conceptually) look like this:
2026 //
2027 // f = .cfi.jumptable
2028 // g = .cfi.jumptable + 4
2029 // h = .cfi.jumptable + 8
2030 // .cfi.jumptable:
2031 // jmp f.cfi ; 5 bytes
2032 // int3 ; 1 byte
2033 // int3 ; 1 byte
2034 // int3 ; 1 byte
2035 // jmp g.cfi ; 5 bytes
2036 // int3 ; 1 byte
2037 // int3 ; 1 byte
2038 // int3 ; 1 byte
2039 // jmp h.cfi ; 5 bytes
2040 // int3 ; 1 byte
2041 // int3 ; 1 byte
2042 // int3 ; 1 byte
2043 //
2044 // f.cfi:
2045 // mov 0, %eax
2046 // ret
2047 //
2048 // g.cfi:
2049 // mov 1, %eax
2050 // ret
2051 //
2052 // h.cfi:
2053 // mov 2, %eax
2054 // ret
2055 //
2056 // foo:
2057 // mov f, %eax
2058 // mov g, %edx
2059 // mov h, %ecx
2060 // ret
2061 //
2062 // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
2063 // normal case the check can be carried out using the same kind of simple
2064 // arithmetic that we normally use for globals.
2065
2066 // FIXME: find a better way to represent the jumptable in the IR.
2067 assert(!Functions.empty());
2068
2069 // Decide on the jump table encoding, so that we know how big the
2070 // entries will be.
2071 Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions);
2072
2073 // Build a simple layout based on the regular layout of jump tables.
2074 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
2075 unsigned EntrySize = getJumpTableEntrySize(JumpTableArch);
2076 for (unsigned I = 0; I != Functions.size(); ++I)
2077 GlobalLayout[Functions[I]] = I * EntrySize;
2078
2079 Function *JumpTableFn =
2080 Function::Create(Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()),
2081 /* IsVarArg */ isVarArg: false),
2082 Linkage: GlobalValue::PrivateLinkage,
2083 AddrSpace: M.getDataLayout().getProgramAddressSpace(),
2084 N: ".cfi.jumptable", M: &M);
2085 ArrayType *JumpTableEntryType = ArrayType::get(ElementType: Int8Ty, NumElements: EntrySize);
2086 ArrayType *JumpTableType =
2087 ArrayType::get(ElementType: JumpTableEntryType, NumElements: Functions.size());
2088 auto JumpTable = ConstantExpr::getPointerCast(
2089 C: JumpTableFn, Ty: PointerType::getUnqual(C&: M.getContext()));
2090
2091 lowerTypeTestCalls(TypeIds, CombinedGlobalAddr: JumpTable, GlobalLayout);
2092
2093 // Build aliases pointing to offsets into the jump table, and replace
2094 // references to the original functions with references to the aliases.
2095 for (unsigned I = 0; I != Functions.size(); ++I) {
2096 Function *F = cast<Function>(Val: Functions[I]->getGlobal());
2097 bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
2098
2099 Constant *CombinedGlobalElemPtr = ConstantExpr::getInBoundsGetElementPtr(
2100 Ty: JumpTableType, C: JumpTable,
2101 IdxList: ArrayRef<Constant *>{ConstantInt::get(Ty: IntPtrTy, V: 0),
2102 ConstantInt::get(Ty: IntPtrTy, V: I)});
2103
2104 const bool IsExported = Functions[I]->isExported();
2105 if (!IsJumpTableCanonical) {
2106 GlobalValue::LinkageTypes LT = IsExported ? GlobalValue::ExternalLinkage
2107 : GlobalValue::InternalLinkage;
2108 GlobalAlias *JtAlias = GlobalAlias::create(Ty: JumpTableEntryType, AddressSpace: 0, Linkage: LT,
2109 Name: F->getName() + ".cfi_jt",
2110 Aliasee: CombinedGlobalElemPtr, Parent: &M);
2111 if (IsExported)
2112 JtAlias->setVisibility(GlobalValue::HiddenVisibility);
2113 else
2114 appendToUsed(M, Values: {JtAlias});
2115 }
2116
2117 if (IsExported) {
2118 GlobalValue::GUID GUID = F->getGUID();
2119 if (IsJumpTableCanonical)
2120 ExportSummary->cfiFunctionDefs().addSymbolWithThinLTOGUID(Name: F->getName(),
2121 GUID);
2122 else
2123 ExportSummary->cfiFunctionDecls().addSymbolWithThinLTOGUID(Name: F->getName(),
2124 GUID);
2125 }
2126
2127 if (!IsJumpTableCanonical) {
2128 if (F->hasExternalWeakLinkage())
2129 replaceWeakDeclarationWithJumpTablePtr(F, JT: CombinedGlobalElemPtr,
2130 IsJumpTableCanonical);
2131 else
2132 replaceCfiUses(Old: F, New: CombinedGlobalElemPtr, IsJumpTableCanonical);
2133 } else {
2134 assert(F->getType()->getAddressSpace() == 0);
2135
2136 GlobalAlias *FAlias =
2137 GlobalAlias::create(Ty: JumpTableEntryType, AddressSpace: 0, Linkage: F->getLinkage(), Name: "",
2138 Aliasee: CombinedGlobalElemPtr, Parent: &M);
2139 FAlias->setVisibility(F->getVisibility());
2140 FAlias->setDSOLocal(F->isDSOLocal());
2141 FAlias->takeName(V: F);
2142 if (FAlias->hasName()) {
2143 F->setName(FAlias->getName() + ".cfi");
2144 maybeReplaceComdat(F, OriginalName: FAlias->getName());
2145 }
2146 replaceCfiUses(Old: F, New: FAlias, IsJumpTableCanonical);
2147 if (!F->hasLocalLinkage())
2148 F->setVisibility(GlobalVariable::HiddenVisibility);
2149 }
2150 }
2151
2152 createJumpTable(F: JumpTableFn, Functions, JumpTableArch);
2153}
2154
2155/// Assign a dummy layout using an incrementing counter, tag each function
2156/// with its index represented as metadata, and lower each type test to an
2157/// integer range comparison. During generation of the indirect function call
2158/// table in the backend, it will assign the given indexes.
2159/// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
2160/// been finalized.
2161void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
2162 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
2163 assert(!Functions.empty());
2164
2165 // Build consecutive monotonic integer ranges for each call target set
2166 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
2167
2168 for (GlobalTypeMember *GTM : Functions) {
2169 Function *F = cast<Function>(Val: GTM->getGlobal());
2170
2171 // Skip functions that are not address taken, to avoid bloating the table
2172 if (!F->hasAddressTaken())
2173 continue;
2174
2175 // Store metadata with the index for each function
2176 MDNode *MD = MDNode::get(Context&: F->getContext(),
2177 MDs: ArrayRef<Metadata *>(ConstantAsMetadata::get(
2178 C: ConstantInt::get(Ty: Int64Ty, V: IndirectIndex))));
2179 F->setMetadata(Kind: "wasm.index", Node: MD);
2180
2181 // Assign the counter value
2182 GlobalLayout[GTM] = IndirectIndex++;
2183 }
2184
2185 // The indirect function table index space starts at zero, so pass a NULL
2186 // pointer as the subtracted "jump table" offset.
2187 lowerTypeTestCalls(TypeIds, CombinedGlobalAddr: ConstantPointerNull::get(T: PtrTy),
2188 GlobalLayout);
2189}
2190
2191void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
2192 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
2193 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
2194 DenseMap<Metadata *, uint64_t> TypeIdIndices;
2195 for (unsigned I = 0; I != TypeIds.size(); ++I)
2196 TypeIdIndices[TypeIds[I]] = I;
2197
2198 // For each type identifier, build a set of indices that refer to members of
2199 // the type identifier.
2200 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
2201 unsigned GlobalIndex = 0;
2202 DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
2203 for (GlobalTypeMember *GTM : Globals) {
2204 for (MDNode *Type : GTM->types()) {
2205 // Type = { offset, type identifier }
2206 auto I = TypeIdIndices.find(Val: Type->getOperand(I: 1));
2207 if (I != TypeIdIndices.end())
2208 TypeMembers[I->second].insert(x: GlobalIndex);
2209 }
2210 GlobalIndices[GTM] = GlobalIndex;
2211 GlobalIndex++;
2212 }
2213
2214 for (ICallBranchFunnel *JT : ICallBranchFunnels) {
2215 TypeMembers.emplace_back();
2216 std::set<uint64_t> &TMSet = TypeMembers.back();
2217 for (GlobalTypeMember *T : JT->targets())
2218 TMSet.insert(x: GlobalIndices[T]);
2219 }
2220
2221 // Order the sets of indices by size. The GlobalLayoutBuilder works best
2222 // when given small index sets first.
2223 llvm::stable_sort(Range&: TypeMembers, C: [](const std::set<uint64_t> &O1,
2224 const std::set<uint64_t> &O2) {
2225 return O1.size() < O2.size();
2226 });
2227
2228 bool IsGlobalSet =
2229 Globals.empty() || isa<GlobalVariable>(Val: Globals[0]->getGlobal());
2230
2231 unique_function<bool(uint64_t, uint64_t)> Less;
2232 if (!IsGlobalSet && !FunctionSummaryHotness.empty() &&
2233 ReorderCfiJumpTablesProfiles) {
2234 // Estimated weight of each jump entry.
2235 std::vector<CfiFunctionHotness> GTMHotness;
2236 GTMHotness.reserve(n: Globals.size());
2237 for (GlobalTypeMember *GTM : Globals) {
2238 GTMHotness.push_back(
2239 x: FunctionSummaryHotness.lookup(Val: cast<Function>(Val: GTM->getGlobal())));
2240 }
2241
2242 // Order jump table entries by hotness ascending so that the hottest
2243 // entry is placed at the end of the jump table:
2244 // 1. Under jump table relaxation (SHT_LLVM_CFI_JUMP_TABLE), the linker
2245 // moves the jump table directly before the target of the last entry
2246 // and deletes its branch so the target function body acts as the
2247 // last entry.
2248 // 2. The jump table is placed into the output section of that last
2249 // target. Jump tables are critical to performance; if the last
2250 // entry were a cold function, the jump table would be dragged into a
2251 // cold binary section (such as .text.unlikely). Placing the hottest
2252 // entry at the end ensures the jump table lands in a hot section and
2253 // the hottest callee benefits from fall-through without a branch.
2254 Less = [GTMHotness = std::move(GTMHotness)](uint64_t A, uint64_t B) {
2255 return GTMHotness[A] < GTMHotness[B];
2256 };
2257 }
2258
2259 // Create a GlobalLayoutBuilder and provide it with index sets as layout
2260 // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
2261 // close together as possible.
2262 GlobalLayoutBuilder GLB(Globals.size(), std::move(Less));
2263 for (auto &&MemSet : TypeMembers)
2264 GLB.addFragment(F: MemSet);
2265
2266 // Build a vector of globals with the computed layout.
2267 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
2268 auto OGTMI = OrderedGTMs.begin();
2269 for (uint64_t Offset : GLB.build()) {
2270 if (IsGlobalSet != isa<GlobalVariable>(Val: Globals[Offset]->getGlobal()))
2271 report_fatal_error(reason: "Type identifier may not contain both global "
2272 "variables and functions");
2273 *OGTMI++ = Globals[Offset];
2274 }
2275
2276 // Build the bitsets from this disjoint set.
2277 if (IsGlobalSet)
2278 buildBitSetsFromGlobalVariables(TypeIds, Globals: OrderedGTMs);
2279 else
2280 buildBitSetsFromFunctions(TypeIds, Functions: OrderedGTMs);
2281}
2282
2283/// Lower all type tests in this module.
2284LowerTypeTestsModule::LowerTypeTestsModule(
2285 Module &M, ModuleAnalysisManager &AM, ModuleSummaryIndex *ExportSummary,
2286 const ModuleSummaryIndex *ImportSummary)
2287 : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
2288 assert(!(ExportSummary && ImportSummary));
2289 Triple TargetTriple(M.getTargetTriple());
2290 Arch = TargetTriple.getArch();
2291 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
2292
2293 if (Arch == Triple::arm)
2294 CanUseArmJumpTable = true;
2295 if (Arch == Triple::arm || Arch == Triple::thumb) {
2296 for (Function &F : M) {
2297 // Skip declarations since we should not query the TTI for them.
2298 if (F.isDeclaration())
2299 continue;
2300 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
2301 if (TTI.hasArmWideBranch(Thumb: false))
2302 CanUseArmJumpTable = true;
2303 if (TTI.hasArmWideBranch(Thumb: true))
2304 CanUseThumbBWJumpTable = true;
2305 }
2306 }
2307 OS = TargetTriple.getOS();
2308 ObjectFormat = TargetTriple.getObjectFormat();
2309
2310 // Function annotation describes or applies to function itself, and
2311 // shouldn't be associated with jump table thunk generated for CFI.
2312 GlobalAnnotation = M.getGlobalVariable(Name: "llvm.global.annotations");
2313 if (GlobalAnnotation && GlobalAnnotation->hasInitializer()) {
2314 const ConstantArray *CA =
2315 cast<ConstantArray>(Val: GlobalAnnotation->getInitializer());
2316 FunctionAnnotations.insert_range(R: CA->operands());
2317 }
2318}
2319
2320bool LowerTypeTestsModule::runForTesting(Module &M, ModuleAnalysisManager &AM) {
2321 std::unique_ptr<ModuleSummaryIndex> Summary;
2322
2323 // Handle the command-line summary arguments. This code is for testing
2324 // purposes only, so we handle errors directly.
2325 if (!ClReadSummary.empty()) {
2326 ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
2327 ": ");
2328 auto ReadSummaryFile = ExitOnErr(errorOrToExpected(
2329 EO: MemoryBuffer::getFile(Filename: ClReadSummary, /*IsText=*/true)));
2330 // TODO: Convert the rest of tests (some YAML features are missing from
2331 // textual summary assembly) and remove YAML from this file.
2332 if (ReadSummaryFile->getBuffer().starts_with(Prefix: "---")) {
2333 Summary = std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/args: false);
2334 yaml::Input In(ReadSummaryFile->getBuffer());
2335 In >> *Summary;
2336 ExitOnErr(errorCodeToError(EC: In.error()));
2337 } else {
2338 SMDiagnostic Err;
2339 Summary =
2340 parseSummaryIndexAssembly(F: ReadSummaryFile->getMemBufferRef(), Err);
2341 if (!Summary) {
2342 Err.print(ProgName: ClReadSummary.c_str(), S&: errs());
2343 report_fatal_error(reason: "Failed to parse summary index assembly");
2344 }
2345 }
2346 } else {
2347 Summary = std::make_unique<ModuleSummaryIndex>(/*HaveGVs=*/args: false);
2348 }
2349
2350 bool Changed =
2351 LowerTypeTestsModule(
2352 M, AM,
2353 ClSummaryAction == PassSummaryAction::Export ? Summary.get()
2354 : nullptr,
2355 ClSummaryAction == PassSummaryAction::Import ? Summary.get()
2356 : nullptr)
2357 .lower();
2358
2359 if (!ClWriteSummary.empty()) {
2360 ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
2361 ": ");
2362 std::error_code EC;
2363 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF);
2364 ExitOnErr(errorCodeToError(EC));
2365
2366 yaml::Output Out(OS);
2367 Out << *Summary;
2368 }
2369
2370 return Changed;
2371}
2372
2373static bool isDirectCall(Use& U) {
2374 auto *Usr = dyn_cast<CallInst>(Val: U.getUser());
2375 return Usr && Usr->isCallee(U: &U);
2376}
2377
2378void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
2379 bool IsJumpTableCanonical) {
2380 SmallSetVector<Constant *, 4> Constants;
2381 for (Use &U : llvm::make_early_inc_range(Range: Old->uses())) {
2382 // Skip no_cfi values, which refer to the function body instead of the jump
2383 // table.
2384 if (isa<NoCFIValue>(Val: U.getUser()))
2385 continue;
2386
2387 // Skip direct calls to externally defined or dso_local functions.
2388 if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
2389 continue;
2390
2391 // Skip function annotation.
2392 if (isFunctionAnnotation(V: U.getUser()))
2393 continue;
2394
2395 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
2396 // constant because they are uniqued.
2397 if (auto *C = dyn_cast<Constant>(Val: U.getUser())) {
2398 if (!isa<GlobalValue>(Val: C)) {
2399 // Save unique users to avoid processing operand replacement
2400 // more than once.
2401 Constants.insert(X: C);
2402 continue;
2403 }
2404 }
2405
2406 U.set(New);
2407 }
2408
2409 // Process operand replacement of saved constants.
2410 for (auto *C : Constants)
2411 C->handleOperandChange(Old, New);
2412}
2413
2414void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
2415 Old->replaceUsesWithIf(New, ShouldReplace: isDirectCall);
2416}
2417
2418static void dropTypeTests(Module &M, Function &TypeTestFunc,
2419 bool ShouldDropAll) {
2420 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc.uses())) {
2421 auto *CI = cast<CallInst>(Val: U.getUser());
2422 // Find and erase llvm.assume intrinsics for this llvm.type.test call.
2423 for (Use &CIU : llvm::make_early_inc_range(Range: CI->uses()))
2424 if (auto *Assume = dyn_cast<AssumeInst>(Val: CIU.getUser()))
2425 Assume->eraseFromParent();
2426 // If the assume was merged with another assume, we might have a use on a
2427 // phi or select (which will feed the assume). Simply replace the use on
2428 // the phi/select with "true" and leave the merged assume.
2429 //
2430 // If ShouldDropAll is set, then we we need to update any remaining uses,
2431 // regardless of the instruction type.
2432 if (!CI->use_empty()) {
2433 assert(ShouldDropAll || all_of(CI->users(), [](User *U) -> bool {
2434 return isa<PHINode>(U) || isa<SelectInst>(U);
2435 }));
2436 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
2437 }
2438 CI->eraseFromParent();
2439 }
2440}
2441
2442static bool dropTypeTests(Module &M, bool ShouldDropAll) {
2443 Function *TypeTestFunc =
2444 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
2445 if (TypeTestFunc)
2446 dropTypeTests(M, TypeTestFunc&: *TypeTestFunc, ShouldDropAll);
2447 // Normally we'd have already removed all @llvm.public.type.test calls,
2448 // except for in the case where we originally were performing ThinLTO but
2449 // decided not to in the backend.
2450 Function *PublicTypeTestFunc =
2451 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::public_type_test);
2452 if (PublicTypeTestFunc)
2453 dropTypeTests(M, TypeTestFunc&: *PublicTypeTestFunc, ShouldDropAll);
2454 if (TypeTestFunc || PublicTypeTestFunc) {
2455 // We have deleted the type intrinsics, so we no longer have enough
2456 // information to reason about the liveness of virtual function pointers
2457 // in GlobalDCE.
2458 for (GlobalVariable &GV : M.globals())
2459 GV.eraseMetadata(KindID: LLVMContext::MD_vcall_visibility);
2460 return true;
2461 }
2462 return false;
2463}
2464
2465bool LowerTypeTestsModule::lower() {
2466 Function *TypeTestFunc =
2467 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_test);
2468
2469 // If only some of the modules were split, we cannot correctly perform
2470 // this transformation. We already checked for the presense of type tests
2471 // with partially split modules during the thin link, and would have emitted
2472 // an error if any were found, so here we can simply return.
2473 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
2474 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
2475 return false;
2476
2477 Function *ICallBranchFunnelFunc =
2478 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::icall_branch_funnel);
2479 if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
2480 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
2481 !ExportSummary && !ImportSummary)
2482 return false;
2483
2484 if (ImportSummary) {
2485 if (TypeTestFunc)
2486 for (Use &U : llvm::make_early_inc_range(Range: TypeTestFunc->uses()))
2487 importTypeTest(CI: cast<CallInst>(Val: U.getUser()));
2488
2489 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
2490 report_fatal_error(
2491 reason: "unexpected call to llvm.icall.branch.funnel during import phase");
2492
2493 SmallVector<Function *, 8> Defs;
2494 SmallVector<Function *, 8> Decls;
2495 for (auto &F : M) {
2496 // CFI functions are either external, or promoted. A local function may
2497 // have the same name, but it's not the one we are looking for.
2498 if (F.hasLocalLinkage())
2499 continue;
2500 if (ImportSummary->cfiFunctionDefs().contains(Name: F.getName()))
2501 Defs.push_back(Elt: &F);
2502 else if (ImportSummary->cfiFunctionDecls().contains(Name: F.getName()))
2503 Decls.push_back(Elt: &F);
2504 }
2505
2506 {
2507 ScopedSaveAliaseesAndUsed S(M);
2508 for (auto *F : Defs)
2509 importFunction(F, /*isJumpTableCanonical*/ true);
2510 for (auto *F : Decls)
2511 importFunction(F, /*isJumpTableCanonical*/ false);
2512 }
2513
2514 return true;
2515 }
2516
2517 // Equivalence class set containing type identifiers and the globals that
2518 // reference them. This is used to partition the set of type identifiers in
2519 // the module into disjoint sets.
2520 using GlobalClassesTy = EquivalenceClasses<
2521 PointerUnion<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>;
2522 GlobalClassesTy GlobalClasses;
2523
2524 // Verify the type metadata and build a few data structures to let us
2525 // efficiently enumerate the type identifiers associated with a global:
2526 // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
2527 // of associated type metadata) and a mapping from type identifiers to their
2528 // list of GlobalTypeMembers and last observed index in the list of globals.
2529 // The indices will be used later to deterministically order the list of type
2530 // identifiers.
2531 BumpPtrAllocator Alloc;
2532 struct TIInfo {
2533 unsigned UniqueId;
2534 std::vector<GlobalTypeMember *> RefGlobals;
2535 };
2536 DenseMap<Metadata *, TIInfo> TypeIdInfo;
2537 unsigned CurUniqueId = 0;
2538 SmallVector<MDNode *, 2> Types;
2539
2540 struct ExportedFunctionInfo {
2541 CfiFunctionLinkage Linkage;
2542 MDNode *FuncMD; // {name, linkage, type[, type...]}
2543 };
2544 MapVector<StringRef, ExportedFunctionInfo> ExportedFunctions;
2545 if (ExportSummary) {
2546 NamedMDNode *CfiFunctionsMD = M.getNamedMetadata(Name: "cfi.functions");
2547 if (CfiFunctionsMD) {
2548 // A set of all functions that are address taken by a live global object.
2549 DenseSet<GlobalValue::GUID> AddressTaken;
2550 for (auto &I : *ExportSummary)
2551 for (auto &GVS : I.second.getSummaryList())
2552 if (GVS->isLive())
2553 for (const auto &Ref : GVS->refs()) {
2554 AddressTaken.insert(V: Ref.getGUID());
2555 for (auto &RefGVS : Ref.getSummaryList())
2556 if (auto Alias = dyn_cast<AliasSummary>(Val: RefGVS.get()))
2557 AddressTaken.insert(V: Alias->getAliaseeGUID());
2558 }
2559 auto IsAddressTaken = [&](GlobalValue::GUID GUID) {
2560 if (AddressTaken.count(V: GUID))
2561 return true;
2562 auto VI = ExportSummary->getValueInfo(GUID);
2563 if (!VI)
2564 return false;
2565 for (auto &I : VI.getSummaryList())
2566 if (auto Alias = dyn_cast<AliasSummary>(Val: I.get()))
2567 if (AddressTaken.count(V: Alias->getAliaseeGUID()))
2568 return true;
2569 return false;
2570 };
2571 for (auto *FuncMD : CfiFunctionsMD->operands()) {
2572 assert(FuncMD->getNumOperands() >= 2);
2573 StringRef FunctionName =
2574 cast<MDString>(Val: FuncMD->getOperand(I: 0))->getString();
2575 CfiFunctionLinkage Linkage = decodeCfiFunctionLinkage(
2576 Encoded: cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 1))
2577 ->getValue()
2578 ->getUniqueInteger()
2579 .getZExtValue());
2580 const GlobalValue::GUID GUID =
2581 cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 2))
2582 ->getValue()
2583 ->getUniqueInteger()
2584 .getZExtValue();
2585 // Do not emit jumptable entries for functions that are not-live and
2586 // have no live references (and are not exported with cross-DSO CFI.)
2587 if (!ExportSummary->isGUIDLive(GUID))
2588 continue;
2589 if (!IsAddressTaken(GUID)) {
2590 if (!CrossDsoCfi || Linkage != CfiFunctionLinkage::Definition)
2591 continue;
2592
2593 bool Exported = false;
2594 if (auto VI = ExportSummary->getValueInfo(GUID))
2595 for (const auto &GVS : VI.getSummaryList())
2596 if (GVS->isLive() && !GlobalValue::isLocalLinkage(Linkage: GVS->linkage()))
2597 Exported = true;
2598
2599 if (!Exported)
2600 continue;
2601 }
2602 auto P = ExportedFunctions.insert(KV: {FunctionName, {.Linkage: Linkage, .FuncMD: FuncMD}});
2603 if (!P.second &&
2604 P.first->second.Linkage != CfiFunctionLinkage::Definition)
2605 P.first->second = {.Linkage: Linkage, .FuncMD: FuncMD};
2606 }
2607
2608 for (const auto &P : ExportedFunctions) {
2609 StringRef FunctionName = P.first;
2610 CfiFunctionLinkage Linkage = P.second.Linkage;
2611 MDNode *FuncMD = P.second.FuncMD;
2612 Function *F = M.getFunction(Name: FunctionName);
2613 if (F && F->hasLocalLinkage()) {
2614 // Locally defined function that happens to have the same name as a
2615 // function defined in a ThinLTO module. Rename it to move it out of
2616 // the way of the external reference that we're about to create.
2617 // Note that setName will find a unique name for the function, so even
2618 // if there is an existing function with the suffix there won't be a
2619 // name collision.
2620 F->setName(F->getName() + ".1");
2621 F = nullptr;
2622 }
2623
2624 if (!F) {
2625 F = Function::Create(
2626 Ty: FunctionType::get(Result: Type::getVoidTy(C&: M.getContext()), isVarArg: false),
2627 Linkage: GlobalVariable::ExternalLinkage,
2628 AddrSpace: M.getDataLayout().getProgramAddressSpace(), N: FunctionName, M: &M);
2629 F->setMetadata(
2630 KindID: LLVMContext::MD_guid,
2631 Node: MDTuple::get(Context&: M.getContext(), MDs: {FuncMD->getOperand(I: 2).get()}));
2632 if (ExportSummary) {
2633 GlobalValue::GUID GUID =
2634 cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 2))
2635 ->getValue()
2636 ->getUniqueInteger()
2637 .getZExtValue();
2638 if (auto VI = ExportSummary->getValueInfo(GUID))
2639 F->setDSOLocal(
2640 VI.isDSOLocal(WithDSOLocalPropagation: ExportSummary->withDSOLocalPropagation()));
2641 }
2642 }
2643 // If the function is available_externally, remove its definition so
2644 // that it is handled the same way as a declaration. Later we will try
2645 // to create an alias using this function's linkage, which will fail if
2646 // the linkage is available_externally. This will also result in us
2647 // following the code path below to replace the type metadata.
2648 if (F->hasAvailableExternallyLinkage()) {
2649 // Maintain !guid metadata.
2650 auto *OrigGUIDMD = F->getMetadata(KindID: LLVMContext::MD_guid);
2651 F->setLinkage(GlobalValue::ExternalLinkage);
2652 F->deleteBody();
2653 F->setComdat(nullptr);
2654 F->clearMetadata();
2655 F->setMetadata(KindID: LLVMContext::MD_guid, Node: OrigGUIDMD);
2656 }
2657
2658 // Update the linkage for extern_weak declarations when a definition
2659 // exists.
2660 if (Linkage == CfiFunctionLinkage::Definition &&
2661 F->hasExternalWeakLinkage())
2662 F->setLinkage(GlobalValue::ExternalLinkage);
2663
2664 // If the function in the full LTO module is a declaration, replace its
2665 // type metadata with the type metadata we found in cfi.functions. That
2666 // metadata is presumed to be more accurate than the metadata attached
2667 // to the declaration.
2668 if (F->isDeclaration()) {
2669 if (Linkage == CfiFunctionLinkage::WeakDeclaration)
2670 F->setLinkage(GlobalValue::ExternalWeakLinkage);
2671
2672 F->eraseMetadata(KindID: LLVMContext::MD_type);
2673 for (unsigned I = 3; I < FuncMD->getNumOperands(); ++I)
2674 F->addMetadata(KindID: LLVMContext::MD_type,
2675 MD&: *cast<MDNode>(Val: FuncMD->getOperand(I).get()));
2676 }
2677 uint8_t Encoded = cast<ConstantAsMetadata>(Val: FuncMD->getOperand(I: 1))
2678 ->getValue()
2679 ->getUniqueInteger()
2680 .getZExtValue();
2681 // TODO: Implement for Full LTO.
2682 FunctionSummaryHotness[F] = decodeCfiFunctionHotness(Encoded);
2683 }
2684 }
2685 }
2686
2687 struct AliasToCreate {
2688 Function *Alias;
2689 std::string TargetName;
2690 };
2691 std::vector<AliasToCreate> AliasesToCreate;
2692
2693 // Parse alias data to replace stand-in function declarations for aliases
2694 // with an alias to the intended target.
2695 if (ExportSummary) {
2696 if (NamedMDNode *AliasesMD = M.getNamedMetadata(Name: "aliases")) {
2697 for (auto *AliasMD : AliasesMD->operands()) {
2698 SmallVector<Function *> Aliases;
2699 for (MDString *MDS : make_isa_range<MDString>(Range: AliasMD->operands())) {
2700 StringRef AliasName = MDS->getString();
2701 if (!ExportedFunctions.count(Key: AliasName))
2702 continue;
2703 auto *AliasF = M.getFunction(Name: AliasName);
2704 if (AliasF)
2705 Aliases.push_back(Elt: AliasF);
2706 }
2707
2708 if (Aliases.empty())
2709 continue;
2710
2711 for (unsigned I = 1; I != Aliases.size(); ++I) {
2712 auto *AliasF = Aliases[I];
2713 ExportedFunctions.erase(Key: AliasF->getName());
2714 AliasesToCreate.push_back(
2715 x: {.Alias: AliasF, .TargetName: std::string(Aliases[0]->getName())});
2716 }
2717 }
2718 }
2719 }
2720
2721 DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
2722 for (GlobalObject &GO : M.global_objects()) {
2723 if (isa<GlobalVariable>(Val: GO) && GO.isDeclarationForLinker())
2724 continue;
2725
2726 Types.clear();
2727 GO.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
2728
2729 bool IsJumpTableCanonical = false;
2730 bool IsExported = false;
2731 if (Function *F = dyn_cast<Function>(Val: &GO)) {
2732 IsJumpTableCanonical = isJumpTableCanonical(F);
2733 if (auto It = ExportedFunctions.find(Key: F->getName());
2734 It != ExportedFunctions.end()) {
2735 IsJumpTableCanonical |=
2736 It->second.Linkage == CfiFunctionLinkage::Definition;
2737 IsExported = true;
2738 // TODO: The logic here checks only that the function is address taken,
2739 // not that the address takers are live. This can be updated to check
2740 // their liveness and emit fewer jumptable entries once monolithic LTO
2741 // builds also emit summaries.
2742 } else if (!F->hasAddressTaken()) {
2743 if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
2744 continue;
2745 }
2746
2747 // TODO: Pre-fill for full LTO.
2748 // if (!ExportSummary)
2749 // FunctionSummaryHotness[F] = getHotness(*F, PSI, BFIGetter);
2750 }
2751
2752 auto *GTM = GlobalTypeMember::create(Alloc, GO: &GO, IsJumpTableCanonical,
2753 IsExported, Types);
2754 GlobalTypeMembers[&GO] = GTM;
2755 for (MDNode *Type : Types) {
2756 verifyTypeMDNode(GO: &GO, Type);
2757 auto &Info = TypeIdInfo[Type->getOperand(I: 1)];
2758 Info.UniqueId = ++CurUniqueId;
2759 Info.RefGlobals.push_back(x: GTM);
2760 }
2761 }
2762
2763 auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
2764 // Add the call site to the list of call sites for this type identifier. We
2765 // also use TypeIdUsers to keep track of whether we have seen this type
2766 // identifier before. If we have, we don't need to re-add the referenced
2767 // globals to the equivalence class.
2768 auto Ins = TypeIdUsers.insert(KV: {TypeId, {}});
2769 if (Ins.second) {
2770 // Add the type identifier to the equivalence class.
2771 auto &GCI = GlobalClasses.insert(Data: TypeId);
2772 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(ECV: GCI);
2773
2774 // Add the referenced globals to the type identifier's equivalence class.
2775 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2776 CurSet = GlobalClasses.unionSets(
2777 L1: CurSet, L2: GlobalClasses.findLeader(ECV: GlobalClasses.insert(Data: GTM)));
2778 }
2779
2780 return Ins.first->second;
2781 };
2782
2783 if (TypeTestFunc) {
2784 for (const Use &U : TypeTestFunc->uses()) {
2785 auto CI = cast<CallInst>(Val: U.getUser());
2786 // If this type test is only used by llvm.assume instructions, it
2787 // was used for whole program devirtualization, and is being kept
2788 // for use by other optimization passes. We do not need or want to
2789 // lower it here. We also don't want to rewrite any associated globals
2790 // unnecessarily. These will be removed by a subsequent LTT invocation
2791 // with the DropTypeTests flag set.
2792 bool OnlyAssumeUses = !CI->use_empty();
2793 for (const Use &CIU : CI->uses()) {
2794 if (isa<AssumeInst>(Val: CIU.getUser()))
2795 continue;
2796 OnlyAssumeUses = false;
2797 break;
2798 }
2799 if (OnlyAssumeUses)
2800 continue;
2801
2802 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
2803 if (!TypeIdMDVal)
2804 report_fatal_error(reason: "Second argument of llvm.type.test must be metadata");
2805 auto TypeId = TypeIdMDVal->getMetadata();
2806 AddTypeIdUse(TypeId).CallSites.push_back(x: CI);
2807 }
2808 }
2809
2810 if (ICallBranchFunnelFunc) {
2811 for (const Use &U : ICallBranchFunnelFunc->uses()) {
2812 if (Arch != Triple::x86_64)
2813 report_fatal_error(
2814 reason: "llvm.icall.branch.funnel not supported on this target");
2815
2816 auto CI = cast<CallInst>(Val: U.getUser());
2817
2818 std::vector<GlobalTypeMember *> Targets;
2819 if (CI->arg_size() % 2 != 1)
2820 report_fatal_error(reason: "number of arguments should be odd");
2821
2822 GlobalClassesTy::member_iterator CurSet;
2823 for (unsigned I = 1; I != CI->arg_size(); I += 2) {
2824 int64_t Offset;
2825 auto *Base = dyn_cast<GlobalObject>(Val: GetPointerBaseWithConstantOffset(
2826 Ptr: CI->getOperand(i_nocapture: I), Offset, DL: M.getDataLayout()));
2827 if (!Base)
2828 report_fatal_error(
2829 reason: "Expected branch funnel operand to be global value");
2830
2831 auto It = GlobalTypeMembers.find(Val: Base);
2832 if (It == GlobalTypeMembers.end())
2833 reportFatalUsageError(reason: "Expected branch funnel operand to be a "
2834 "defined global value with type metadata");
2835 GlobalTypeMember *GTM = It->second;
2836 Targets.push_back(x: GTM);
2837 GlobalClassesTy::member_iterator NewSet =
2838 GlobalClasses.findLeader(ECV: GlobalClasses.insert(Data: GTM));
2839 if (I == 1)
2840 CurSet = NewSet;
2841 else
2842 CurSet = GlobalClasses.unionSets(L1: CurSet, L2: NewSet);
2843 }
2844
2845 GlobalClasses.unionSets(
2846 L1: CurSet, L2: GlobalClasses.findLeader(
2847 ECV: GlobalClasses.insert(Data: ICallBranchFunnel::create(
2848 Alloc, CI, Targets, UniqueId: ++CurUniqueId))));
2849 }
2850 }
2851
2852 if (ExportSummary) {
2853 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
2854 for (auto &P : TypeIdInfo) {
2855 if (auto *TypeId = dyn_cast<MDString>(Val: P.first))
2856 MetadataByGUID[GlobalValue::getGUIDAssumingExternalLinkage(
2857 GlobalName: TypeId->getString())]
2858 .push_back(NewVal: TypeId);
2859 }
2860
2861 for (auto &P : *ExportSummary) {
2862 for (auto &S : P.second.getSummaryList()) {
2863 if (!ExportSummary->isGlobalValueLive(GVS: S.get()))
2864 continue;
2865 if (auto *FS = dyn_cast<FunctionSummary>(Val: S->getBaseObject()))
2866 for (GlobalValue::GUID G : FS->type_tests())
2867 for (Metadata *MD : MetadataByGUID[G])
2868 AddTypeIdUse(MD).IsExported = true;
2869 }
2870 }
2871 }
2872
2873 if (GlobalClasses.empty())
2874 return false;
2875
2876 {
2877 ScopedSaveAliaseesAndUsed S(M);
2878 // For each disjoint set we found...
2879 for (const auto &C : GlobalClasses) {
2880 if (!C->isLeader())
2881 continue;
2882
2883 ++NumTypeIdDisjointSets;
2884 // Build the list of type identifiers in this disjoint set.
2885 std::vector<Metadata *> TypeIds;
2886 std::vector<GlobalTypeMember *> Globals;
2887 std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2888 for (auto M : GlobalClasses.members(ECV: *C)) {
2889 if (isa<Metadata *>(Val: M))
2890 TypeIds.push_back(x: cast<Metadata *>(Val&: M));
2891 else if (isa<GlobalTypeMember *>(Val: M))
2892 Globals.push_back(x: cast<GlobalTypeMember *>(Val&: M));
2893 else
2894 ICallBranchFunnels.push_back(x: cast<ICallBranchFunnel *>(Val&: M));
2895 }
2896
2897 // Order type identifiers by unique ID for determinism. This ordering is
2898 // stable as there is a one-to-one mapping between metadata and unique
2899 // IDs.
2900 llvm::sort(C&: TypeIds, Comp: [&](Metadata *M1, Metadata *M2) {
2901 return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2902 });
2903
2904 // Same for the branch funnels.
2905 llvm::sort(C&: ICallBranchFunnels,
2906 Comp: [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2907 return F1->UniqueId < F2->UniqueId;
2908 });
2909
2910 // Build bitsets for this disjoint set.
2911 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2912 }
2913 }
2914
2915 allocateByteArrays();
2916
2917 for (auto A : AliasesToCreate) {
2918 auto *Target = M.getNamedValue(Name: A.TargetName);
2919 if (!isa<GlobalAlias>(Val: Target))
2920 continue;
2921 auto *AliasGA = GlobalAlias::create(Name: "", Aliasee: Target);
2922 AliasGA->setVisibility(A.Alias->getVisibility());
2923 AliasGA->setLinkage(A.Alias->getLinkage());
2924 AliasGA->setDSOLocal(A.Alias->isDSOLocal());
2925 AliasGA->takeName(V: A.Alias);
2926 A.Alias->replaceAllUsesWith(V: AliasGA);
2927 A.Alias->eraseFromParent();
2928 }
2929
2930 // Emit .symver directives for exported functions, if they exist.
2931 if (ExportSummary) {
2932 if (NamedMDNode *SymversMD = M.getNamedMetadata(Name: "symvers")) {
2933 for (auto *Symver : SymversMD->operands()) {
2934 assert(Symver->getNumOperands() >= 2);
2935 StringRef SymbolName =
2936 cast<MDString>(Val: Symver->getOperand(I: 0))->getString();
2937 StringRef Alias = cast<MDString>(Val: Symver->getOperand(I: 1))->getString();
2938
2939 if (!ExportedFunctions.count(Key: SymbolName))
2940 continue;
2941
2942 M.appendModuleInlineAsm(
2943 Fragment: (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2944 }
2945 }
2946 }
2947
2948 return true;
2949}
2950
2951PreservedAnalyses LowerTypeTestsPass::run(Module &M,
2952 ModuleAnalysisManager &AM) {
2953 bool Changed;
2954 if (UseCommandLine)
2955 Changed = LowerTypeTestsModule::runForTesting(M, AM);
2956 else
2957 Changed = LowerTypeTestsModule(M, AM, ExportSummary, ImportSummary).lower();
2958 if (!Changed)
2959 return PreservedAnalyses::all();
2960 return PreservedAnalyses::none();
2961}
2962
2963void DropTypeTestsPass::printPipeline(
2964 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2965 static_cast<PassInfoMixin<DropTypeTestsPass> *>(this)->printPipeline(
2966 OS, MapClassName2PassName);
2967 OS << '<';
2968 switch (Kind) {
2969 case DropTestKind::Assume:
2970 OS << "assume";
2971 break;
2972 case DropTestKind::All:
2973 OS << "all";
2974 break;
2975 }
2976 OS << '>';
2977}
2978
2979PreservedAnalyses DropTypeTestsPass::run(Module &M, ModuleAnalysisManager &AM) {
2980 return dropTypeTests(M, ShouldDropAll: Kind == DropTestKind::All) ? PreservedAnalyses::none()
2981 : PreservedAnalyses::all();
2982}
2983
2984PreservedAnalyses SimplifyTypeTestsPass::run(Module &M,
2985 ModuleAnalysisManager &AM) {
2986 bool Changed = false;
2987 // Figure out whether inlining has exposed a constant address to a lowered
2988 // type test, and remove the test if so and the address is known to pass the
2989 // test. Unfortunately this pass ends up needing to reverse engineer what
2990 // LowerTypeTests did; this is currently inherent to the design of ThinLTO
2991 // importing where LowerTypeTests needs to run at the start.
2992 //
2993 // We look for things like:
2994 //
2995 // sub (i64 ptrtoint (ptr @_Z2fpv to i64), i64 ptrtoint (ptr
2996 // @__typeid__ZTSFvvE_global_addr to i64))
2997 //
2998 // which gets replaced with 0 if _Z2fpv (more specifically _Z2fpv.cfi, the
2999 // function referred to by the jump table) is a member of the type _ZTSFvv, as
3000 // well as things like
3001 //
3002 // icmp eq ptr @_Z2fpv, @__typeid__ZTSFvvE_global_addr
3003 //
3004 // which gets replaced with true if _Z2fpv is a member.
3005 for (auto &GV : M.globals()) {
3006 if (!GV.getName().starts_with(Prefix: "__typeid_") ||
3007 !GV.getName().ends_with(Suffix: "_global_addr"))
3008 continue;
3009 // __typeid_foo_global_addr -> foo
3010 auto *MD = MDString::get(Context&: M.getContext(),
3011 Str: GV.getName().substr(Start: 9, N: GV.getName().size() - 21));
3012 auto MaySimplifyPtr = [&](Value *Ptr) {
3013 if (auto *GV = dyn_cast<GlobalValue>(Val: Ptr))
3014 if (auto *CFIGV = M.getNamedValue(Name: (GV->getName() + ".cfi").str()))
3015 Ptr = CFIGV;
3016 return isKnownTypeIdMember(TypeId: MD, DL: M.getDataLayout(), V: Ptr, COffset: 0);
3017 };
3018 auto MaySimplifyInt = [&](Value *Op) {
3019 auto *PtrAsInt = dyn_cast<ConstantExpr>(Val: Op);
3020 if (!PtrAsInt || PtrAsInt->getOpcode() != Instruction::PtrToInt)
3021 return false;
3022 return MaySimplifyPtr(PtrAsInt->getOperand(i_nocapture: 0));
3023 };
3024 for (User *U : make_early_inc_range(Range: GV.users())) {
3025 if (auto *CI = dyn_cast<ICmpInst>(Val: U)) {
3026 if (CI->getPredicate() == CmpInst::ICMP_EQ &&
3027 MaySimplifyPtr(CI->getOperand(i_nocapture: 0))) {
3028 // This is an equality comparison (TypeTestResolution::Single case in
3029 // lowerTypeTestCall). In this case we just replace the comparison
3030 // with true.
3031 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
3032 CI->eraseFromParent();
3033 Changed = true;
3034 continue;
3035 }
3036 }
3037 auto *CE = dyn_cast<ConstantExpr>(Val: U);
3038 if (!CE || CE->getOpcode() != Instruction::PtrToInt)
3039 continue;
3040 for (Use &U : make_early_inc_range(Range: CE->uses())) {
3041 auto *CE = dyn_cast<ConstantExpr>(Val: U.getUser());
3042 if (U.getOperandNo() == 0 && CE &&
3043 CE->getOpcode() == Instruction::Sub &&
3044 MaySimplifyInt(CE->getOperand(i_nocapture: 1))) {
3045 // This is a computation of PtrOffset as generated by
3046 // LowerTypeTestsModule::lowerTypeTestCall above. If
3047 // isKnownTypeIdMember passes we just pretend it evaluated to 0. This
3048 // should cause later passes to remove the range and alignment checks.
3049 // The bitset checks won't be removed but those are uncommon.
3050 CE->replaceAllUsesWith(V: ConstantInt::get(Ty: CE->getType(), V: 0));
3051 Changed = true;
3052 }
3053 auto *CI = dyn_cast<ICmpInst>(Val: U.getUser());
3054 if (U.getOperandNo() == 1 && CI &&
3055 CI->getPredicate() == CmpInst::ICMP_EQ &&
3056 MaySimplifyInt(CI->getOperand(i_nocapture: 0))) {
3057 // This is an equality comparison. Unlike in the case above it
3058 // remained as an integer compare.
3059 CI->replaceAllUsesWith(V: ConstantInt::getTrue(Context&: M.getContext()));
3060 CI->eraseFromParent();
3061 Changed = true;
3062 }
3063 }
3064 }
3065 }
3066
3067 if (!Changed)
3068 return PreservedAnalyses::all();
3069 PreservedAnalyses PA = PreservedAnalyses::none();
3070 PA.preserve<DominatorTreeAnalysis>();
3071 PA.preserve<PostDominatorTreeAnalysis>();
3072 PA.preserve<LoopAnalysis>();
3073 return PA;
3074}
3075