LLVM 17.0.0git
LowerTypeTests.cpp
Go to the documentation of this file.
1//===- LowerTypeTests.cpp - type metadata lowering pass -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass lowers type metadata and calls to the llvm.type.test intrinsic.
10// It also ensures that globals are properly laid out for the
11// llvm.icall.branch.funnel intrinsic.
12// See http://llvm.org/docs/TypeMetadata.html for more information.
13//
14//===----------------------------------------------------------------------===//
15
17#include "llvm/ADT/APInt.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/ADT/StringRef.h"
30#include "llvm/IR/Attributes.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/Constant.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/Function.h"
37#include "llvm/IR/GlobalAlias.h"
39#include "llvm/IR/GlobalValue.h"
41#include "llvm/IR/IRBuilder.h"
42#include "llvm/IR/InlineAsm.h"
43#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Intrinsics.h"
47#include "llvm/IR/LLVMContext.h"
48#include "llvm/IR/Metadata.h"
49#include "llvm/IR/Module.h"
52#include "llvm/IR/Operator.h"
53#include "llvm/IR/PassManager.h"
55#include "llvm/IR/Type.h"
56#include "llvm/IR/Use.h"
57#include "llvm/IR/User.h"
58#include "llvm/IR/Value.h"
60#include "llvm/Pass.h"
64#include "llvm/Support/Debug.h"
65#include "llvm/Support/Error.h"
74#include "llvm/Transforms/IPO.h"
77#include <algorithm>
78#include <cassert>
79#include <cstdint>
80#include <memory>
81#include <set>
82#include <string>
83#include <system_error>
84#include <utility>
85#include <vector>
86
87using namespace llvm;
88using namespace lowertypetests;
89
90#define DEBUG_TYPE "lowertypetests"
91
92STATISTIC(ByteArraySizeBits, "Byte array size in bits");
93STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
94STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
95STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
96STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
97
99 "lowertypetests-avoid-reuse",
100 cl::desc("Try to avoid reuse of byte array addresses using aliases"),
101 cl::Hidden, cl::init(true));
102
104 "lowertypetests-summary-action",
105 cl::desc("What to do with the summary when running this pass"),
106 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
107 clEnumValN(PassSummaryAction::Import, "import",
108 "Import typeid resolutions from summary and globals"),
109 clEnumValN(PassSummaryAction::Export, "export",
110 "Export typeid resolutions to summary and globals")),
111 cl::Hidden);
112
114 "lowertypetests-read-summary",
115 cl::desc("Read summary from given YAML file before running pass"),
116 cl::Hidden);
117
119 "lowertypetests-write-summary",
120 cl::desc("Write summary to given YAML file after running pass"),
121 cl::Hidden);
122
123static cl::opt<bool>
124 ClDropTypeTests("lowertypetests-drop-type-tests",
125 cl::desc("Simply drop type test assume sequences"),
126 cl::Hidden, cl::init(false));
127
129 if (Offset < ByteOffset)
130 return false;
131
132 if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
133 return false;
134
135 uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
136 if (BitOffset >= BitSize)
137 return false;
138
139 return Bits.count(BitOffset);
140}
141
143 OS << "offset " << ByteOffset << " size " << BitSize << " align "
144 << (1 << AlignLog2);
145
146 if (isAllOnes()) {
147 OS << " all-ones\n";
148 return;
149 }
150
151 OS << " { ";
152 for (uint64_t B : Bits)
153 OS << B << ' ';
154 OS << "}\n";
155}
156
158 if (Min > Max)
159 Min = 0;
160
161 // Normalize each offset against the minimum observed offset, and compute
162 // the bitwise OR of each of the offsets. The number of trailing zeros
163 // in the mask gives us the log2 of the alignment of all offsets, which
164 // allows us to compress the bitset by only storing one bit per aligned
165 // address.
166 uint64_t Mask = 0;
167 for (uint64_t &Offset : Offsets) {
168 Offset -= Min;
169 Mask |= Offset;
170 }
171
172 BitSetInfo BSI;
173 BSI.ByteOffset = Min;
174
175 BSI.AlignLog2 = 0;
176 if (Mask != 0)
177 BSI.AlignLog2 = llvm::countr_zero(Mask);
178
179 // Build the compressed bitset while normalizing the offsets against the
180 // computed alignment.
181 BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
182 for (uint64_t Offset : Offsets) {
183 Offset >>= BSI.AlignLog2;
184 BSI.Bits.insert(Offset);
185 }
186
187 return BSI;
188}
189
190void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
191 // Create a new fragment to hold the layout for F.
192 Fragments.emplace_back();
193 std::vector<uint64_t> &Fragment = Fragments.back();
194 uint64_t FragmentIndex = Fragments.size() - 1;
195
196 for (auto ObjIndex : F) {
197 uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
198 if (OldFragmentIndex == 0) {
199 // We haven't seen this object index before, so just add it to the current
200 // fragment.
201 Fragment.push_back(ObjIndex);
202 } else {
203 // This index belongs to an existing fragment. Copy the elements of the
204 // old fragment into this one and clear the old fragment. We don't update
205 // the fragment map just yet, this ensures that any further references to
206 // indices from the old fragment in this fragment do not insert any more
207 // indices.
208 std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
209 llvm::append_range(Fragment, OldFragment);
210 OldFragment.clear();
211 }
212 }
213
214 // Update the fragment map to point our object indices to this fragment.
215 for (uint64_t ObjIndex : Fragment)
216 FragmentMap[ObjIndex] = FragmentIndex;
217}
218
219void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
220 uint64_t BitSize, uint64_t &AllocByteOffset,
221 uint8_t &AllocMask) {
222 // Find the smallest current allocation.
223 unsigned Bit = 0;
224 for (unsigned I = 1; I != BitsPerByte; ++I)
225 if (BitAllocs[I] < BitAllocs[Bit])
226 Bit = I;
227
228 AllocByteOffset = BitAllocs[Bit];
229
230 // Add our size to it.
231 unsigned ReqSize = AllocByteOffset + BitSize;
232 BitAllocs[Bit] = ReqSize;
233 if (Bytes.size() < ReqSize)
234 Bytes.resize(ReqSize);
235
236 // Set our bits.
237 AllocMask = 1 << Bit;
238 for (uint64_t B : Bits)
239 Bytes[AllocByteOffset + B] |= AllocMask;
240}
241
243 if (F->isDeclarationForLinker())
244 return false;
245 auto *CI = mdconst::extract_or_null<ConstantInt>(
246 F->getParent()->getModuleFlag("CFI Canonical Jump Tables"));
247 if (!CI || !CI->isZero())
248 return true;
249 return F->hasFnAttribute("cfi-canonical-jump-table");
250}
251
252namespace {
253
254struct ByteArrayInfo {
255 std::set<uint64_t> Bits;
256 uint64_t BitSize;
257 GlobalVariable *ByteArray;
258 GlobalVariable *MaskGlobal;
259 uint8_t *MaskPtr = nullptr;
260};
261
262/// A POD-like structure that we use to store a global reference together with
263/// its metadata types. In this pass we frequently need to query the set of
264/// metadata types referenced by a global, which at the IR level is an expensive
265/// operation involving a map lookup; this data structure helps to reduce the
266/// number of times we need to do this lookup.
267class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
268 friend TrailingObjects;
269
270 GlobalObject *GO;
271 size_t NTypes;
272
273 // For functions: true if the jump table is canonical. This essentially means
274 // whether the canonical address (i.e. the symbol table entry) of the function
275 // is provided by the local jump table. This is normally the same as whether
276 // the function is defined locally, but if canonical jump tables are disabled
277 // by the user then the jump table never provides a canonical definition.
278 bool IsJumpTableCanonical;
279
280 // For functions: true if this function is either defined or used in a thinlto
281 // module and its jumptable entry needs to be exported to thinlto backends.
282 bool IsExported;
283
284 size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; }
285
286public:
287 static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
288 bool IsJumpTableCanonical, bool IsExported,
289 ArrayRef<MDNode *> Types) {
290 auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
291 totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember)));
292 GTM->GO = GO;
293 GTM->NTypes = Types.size();
294 GTM->IsJumpTableCanonical = IsJumpTableCanonical;
295 GTM->IsExported = IsExported;
296 std::uninitialized_copy(Types.begin(), Types.end(),
297 GTM->getTrailingObjects<MDNode *>());
298 return GTM;
299 }
300
301 GlobalObject *getGlobal() const {
302 return GO;
303 }
304
305 bool isJumpTableCanonical() const {
306 return IsJumpTableCanonical;
307 }
308
309 bool isExported() const {
310 return IsExported;
311 }
312
313 ArrayRef<MDNode *> types() const {
314 return ArrayRef(getTrailingObjects<MDNode *>(), NTypes);
315 }
316};
317
318struct ICallBranchFunnel final
319 : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
320 static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
322 unsigned UniqueId) {
323 auto *Call = static_cast<ICallBranchFunnel *>(
324 Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()),
325 alignof(ICallBranchFunnel)));
326 Call->CI = CI;
327 Call->UniqueId = UniqueId;
328 Call->NTargets = Targets.size();
329 std::uninitialized_copy(Targets.begin(), Targets.end(),
330 Call->getTrailingObjects<GlobalTypeMember *>());
331 return Call;
332 }
333
334 CallInst *CI;
335 ArrayRef<GlobalTypeMember *> targets() const {
336 return ArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
337 }
338
339 unsigned UniqueId;
340
341private:
342 size_t NTargets;
343};
344
345struct ScopedSaveAliaseesAndUsed {
346 Module &M;
348 std::vector<std::pair<GlobalAlias *, Function *>> FunctionAliases;
349 std::vector<std::pair<GlobalIFunc *, Function *>> ResolverIFuncs;
350
351 ScopedSaveAliaseesAndUsed(Module &M) : M(M) {
352 // The users of this class want to replace all function references except
353 // for aliases and llvm.used/llvm.compiler.used with references to a jump
354 // table. We avoid replacing aliases in order to avoid introducing a double
355 // indirection (or an alias pointing to a declaration in ThinLTO mode), and
356 // we avoid replacing llvm.used/llvm.compiler.used because these global
357 // variables describe properties of the global, not the jump table (besides,
358 // offseted references to the jump table in llvm.used are invalid).
359 // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly
360 // indirect) users", so what we do is save the list of globals referenced by
361 // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW
362 // replace the aliasees and then set them back to their original values at
363 // the end.
364 if (GlobalVariable *GV = collectUsedGlobalVariables(M, Used, false))
365 GV->eraseFromParent();
366 if (GlobalVariable *GV = collectUsedGlobalVariables(M, CompilerUsed, true))
367 GV->eraseFromParent();
368
369 for (auto &GA : M.aliases()) {
370 // FIXME: This should look past all aliases not just interposable ones,
371 // see discussion on D65118.
372 if (auto *F = dyn_cast<Function>(GA.getAliasee()->stripPointerCasts()))
373 FunctionAliases.push_back({&GA, F});
374 }
375
376 for (auto &GI : M.ifuncs())
377 if (auto *F = dyn_cast<Function>(GI.getResolver()->stripPointerCasts()))
378 ResolverIFuncs.push_back({&GI, F});
379 }
380
381 ~ScopedSaveAliaseesAndUsed() {
382 appendToUsed(M, Used);
383 appendToCompilerUsed(M, CompilerUsed);
384
385 for (auto P : FunctionAliases)
386 P.first->setAliasee(
387 ConstantExpr::getBitCast(P.second, P.first->getType()));
388
389 for (auto P : ResolverIFuncs) {
390 // This does not preserve pointer casts that may have been stripped by the
391 // constructor, but the resolver's type is different from that of the
392 // ifunc anyway.
393 P.first->setResolver(P.second);
394 }
395 }
396};
397
398class LowerTypeTestsModule {
399 Module &M;
400
401 ModuleSummaryIndex *ExportSummary;
402 const ModuleSummaryIndex *ImportSummary;
403 // Set when the client has invoked this to simply drop all type test assume
404 // sequences.
405 bool DropTypeTests;
406
407 Triple::ArchType Arch;
409 Triple::ObjectFormatType ObjectFormat;
410
411 // Determines which kind of Thumb jump table we generate. If arch is
412 // either 'arm' or 'thumb' we need to find this out, because
413 // selectJumpTableArmEncoding may decide to use Thumb in either case.
414 bool CanUseArmJumpTable = false, CanUseThumbBWJumpTable = false;
415
416 // The jump table type we ended up deciding on. (Usually the same as
417 // Arch, except that 'arm' and 'thumb' are often interchangeable.)
419
420 IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
421 IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
422 PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
423 ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0);
424 IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
425 PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty);
426 IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
427 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
428
429 // Indirect function call index assignment counter for WebAssembly
430 uint64_t IndirectIndex = 1;
431
432 // Mapping from type identifiers to the call sites that test them, as well as
433 // whether the type identifier needs to be exported to ThinLTO backends as
434 // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
435 struct TypeIdUserInfo {
436 std::vector<CallInst *> CallSites;
437 bool IsExported = false;
438 };
440
441 /// This structure describes how to lower type tests for a particular type
442 /// identifier. It is either built directly from the global analysis (during
443 /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
444 /// identifier summaries and external symbol references (in ThinLTO backends).
445 struct TypeIdLowering {
447
448 /// All except Unsat: the start address within the combined global.
449 Constant *OffsetedGlobal;
450
451 /// ByteArray, Inline, AllOnes: log2 of the required global alignment
452 /// relative to the start address.
453 Constant *AlignLog2;
454
455 /// ByteArray, Inline, AllOnes: one less than the size of the memory region
456 /// covering members of this type identifier as a multiple of 2^AlignLog2.
457 Constant *SizeM1;
458
459 /// ByteArray: the byte array to test the address against.
460 Constant *TheByteArray;
461
462 /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
463 Constant *BitMask;
464
465 /// Inline: the bit mask to test the address against.
466 Constant *InlineBits;
467 };
468
469 std::vector<ByteArrayInfo> ByteArrayInfos;
470
471 Function *WeakInitializerFn = nullptr;
472
473 bool shouldExportConstantsAsAbsoluteSymbols();
474 uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
475 TypeIdLowering importTypeId(StringRef TypeId);
476 void importTypeTest(CallInst *CI);
477 void importFunction(Function *F, bool isJumpTableCanonical,
478 std::vector<GlobalAlias *> &AliasesToErase);
479
481 buildBitSet(Metadata *TypeId,
482 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
483 ByteArrayInfo *createByteArray(BitSetInfo &BSI);
484 void allocateByteArrays();
485 Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
486 Value *BitOffset);
487 void lowerTypeTestCalls(
488 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
489 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
490 Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
491 const TypeIdLowering &TIL);
492
493 void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
496 selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions);
497 unsigned getJumpTableEntrySize();
498 Type *getJumpTableEntryType();
499 void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
500 Triple::ArchType JumpTableArch,
501 SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
502 void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
503 void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
505 void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
507 void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
509 void
510 buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
512 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
513
514 void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT,
515 bool IsJumpTableCanonical);
516 void moveInitializerToModuleConstructor(GlobalVariable *GV);
517 void findGlobalVariableUsersOf(Constant *C,
519
520 void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
521
522 /// replaceCfiUses - Go through the uses list for this definition
523 /// and make each use point to "V" instead of "this" when the use is outside
524 /// the block. 'This's use list is expected to have at least one element.
525 /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
526 /// uses.
527 void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical);
528
529 /// replaceDirectCalls - Go through the uses list for this definition and
530 /// replace each use, which is a direct function call.
531 void replaceDirectCalls(Value *Old, Value *New);
532
533public:
534 LowerTypeTestsModule(Module &M, ModuleAnalysisManager &AM,
535 ModuleSummaryIndex *ExportSummary,
536 const ModuleSummaryIndex *ImportSummary,
537 bool DropTypeTests);
538
539 bool lower();
540
541 // Lower the module using the action and summary passed as command line
542 // arguments. For testing purposes only.
543 static bool runForTesting(Module &M, ModuleAnalysisManager &AM);
544};
545} // end anonymous namespace
546
547/// Build a bit set for TypeId using the object layouts in
548/// GlobalLayout.
549BitSetInfo LowerTypeTestsModule::buildBitSet(
550 Metadata *TypeId,
551 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
552 BitSetBuilder BSB;
553
554 // Compute the byte offset of each address associated with this type
555 // identifier.
556 for (const auto &GlobalAndOffset : GlobalLayout) {
557 for (MDNode *Type : GlobalAndOffset.first->types()) {
558 if (Type->getOperand(1) != TypeId)
559 continue;
561 cast<ConstantInt>(
562 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
563 ->getZExtValue();
564 BSB.addOffset(GlobalAndOffset.second + Offset);
565 }
566 }
567
568 return BSB.build();
569}
570
571/// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
572/// Bits. This pattern matches to the bt instruction on x86.
574 Value *BitOffset) {
575 auto BitsType = cast<IntegerType>(Bits->getType());
576 unsigned BitWidth = BitsType->getBitWidth();
577
578 BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
579 Value *BitIndex =
580 B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
581 Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
582 Value *MaskedBits = B.CreateAnd(Bits, BitMask);
583 return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
584}
585
586ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
587 // Create globals to stand in for byte arrays and masks. These never actually
588 // get initialized, we RAUW and erase them later in allocateByteArrays() once
589 // we know the offset and mask to use.
590 auto ByteArrayGlobal = new GlobalVariable(
591 M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
592 auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
594
595 ByteArrayInfos.emplace_back();
596 ByteArrayInfo *BAI = &ByteArrayInfos.back();
597
598 BAI->Bits = BSI.Bits;
599 BAI->BitSize = BSI.BitSize;
600 BAI->ByteArray = ByteArrayGlobal;
601 BAI->MaskGlobal = MaskGlobal;
602 return BAI;
603}
604
605void LowerTypeTestsModule::allocateByteArrays() {
606 llvm::stable_sort(ByteArrayInfos,
607 [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
608 return BAI1.BitSize > BAI2.BitSize;
609 });
610
611 std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
612
614 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
615 ByteArrayInfo *BAI = &ByteArrayInfos[I];
616
617 uint8_t Mask;
618 BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
619
620 BAI->MaskGlobal->replaceAllUsesWith(
621 ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
622 BAI->MaskGlobal->eraseFromParent();
623 if (BAI->MaskPtr)
624 *BAI->MaskPtr = Mask;
625 }
626
627 Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
628 auto ByteArray =
629 new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
630 GlobalValue::PrivateLinkage, ByteArrayConst);
631
632 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
633 ByteArrayInfo *BAI = &ByteArrayInfos[I];
634
635 Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
636 ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
638 ByteArrayConst->getType(), ByteArray, Idxs);
639
640 // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
641 // that the pc-relative displacement is folded into the lea instead of the
642 // test instruction getting another displacement.
644 Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
645 BAI->ByteArray->replaceAllUsesWith(Alias);
646 BAI->ByteArray->eraseFromParent();
647 }
648
649 ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
650 BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
651 BAB.BitAllocs[6] + BAB.BitAllocs[7];
652 ByteArraySizeBytes = BAB.Bytes.size();
653}
654
655/// Build a test that bit BitOffset is set in the type identifier that was
656/// lowered to TIL, which must be either an Inline or a ByteArray.
657Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
658 const TypeIdLowering &TIL,
659 Value *BitOffset) {
660 if (TIL.TheKind == TypeTestResolution::Inline) {
661 // If the bit set is sufficiently small, we can avoid a load by bit testing
662 // a constant.
663 return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
664 } else {
665 Constant *ByteArray = TIL.TheByteArray;
666 if (AvoidReuse && !ImportSummary) {
667 // Each use of the byte array uses a different alias. This makes the
668 // backend less likely to reuse previously computed byte array addresses,
669 // improving the security of the CFI mechanism based on this pass.
670 // This won't work when importing because TheByteArray is external.
672 "bits_use", ByteArray, &M);
673 }
674
675 Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
676 Value *Byte = B.CreateLoad(Int8Ty, ByteAddr);
677
678 Value *ByteAndMask =
679 B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
680 return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
681 }
682}
683
684static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
685 Value *V, uint64_t COffset) {
686 if (auto GV = dyn_cast<GlobalObject>(V)) {
688 GV->getMetadata(LLVMContext::MD_type, Types);
689 for (MDNode *Type : Types) {
690 if (Type->getOperand(1) != TypeId)
691 continue;
693 cast<ConstantInt>(
694 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
695 ->getZExtValue();
696 if (COffset == Offset)
697 return true;
698 }
699 return false;
700 }
701
702 if (auto GEP = dyn_cast<GEPOperator>(V)) {
703 APInt APOffset(DL.getIndexSizeInBits(0), 0);
704 bool Result = GEP->accumulateConstantOffset(DL, APOffset);
705 if (!Result)
706 return false;
707 COffset += APOffset.getZExtValue();
708 return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
709 }
710
711 if (auto Op = dyn_cast<Operator>(V)) {
712 if (Op->getOpcode() == Instruction::BitCast)
713 return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
714
715 if (Op->getOpcode() == Instruction::Select)
716 return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
717 isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
718 }
719
720 return false;
721}
722
723/// Lower a llvm.type.test call to its implementation. Returns the value to
724/// replace the call with.
725Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
726 const TypeIdLowering &TIL) {
727 // Delay lowering if the resolution is currently unknown.
728 if (TIL.TheKind == TypeTestResolution::Unknown)
729 return nullptr;
730 if (TIL.TheKind == TypeTestResolution::Unsat)
731 return ConstantInt::getFalse(M.getContext());
732
733 Value *Ptr = CI->getArgOperand(0);
734 const DataLayout &DL = M.getDataLayout();
735 if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
736 return ConstantInt::getTrue(M.getContext());
737
738 BasicBlock *InitialBB = CI->getParent();
739
740 IRBuilder<> B(CI);
741
742 Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
743
744 Constant *OffsetedGlobalAsInt =
745 ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
746 if (TIL.TheKind == TypeTestResolution::Single)
747 return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
748
749 Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
750
751 // We need to check that the offset both falls within our range and is
752 // suitably aligned. We can check both properties at the same time by
753 // performing a right rotate by log2(alignment) followed by an integer
754 // comparison against the bitset size. The rotate will move the lower
755 // order bits that need to be zero into the higher order bits of the
756 // result, causing the comparison to fail if they are nonzero. The rotate
757 // also conveniently gives us a bit offset to use during the load from
758 // the bitset.
759 Value *OffsetSHR =
760 B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
761 Value *OffsetSHL = B.CreateShl(
762 PtrOffset, ConstantExpr::getZExt(
764 ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
765 TIL.AlignLog2),
766 IntPtrTy));
767 Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
768
769 Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1);
770
771 // If the bit set is all ones, testing against it is unnecessary.
772 if (TIL.TheKind == TypeTestResolution::AllOnes)
773 return OffsetInRange;
774
775 // See if the intrinsic is used in the following common pattern:
776 // br(llvm.type.test(...), thenbb, elsebb)
777 // where nothing happens between the type test and the br.
778 // If so, create slightly simpler IR.
779 if (CI->hasOneUse())
780 if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin()))
781 if (CI->getNextNode() == Br) {
782 BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator());
783 BasicBlock *Else = Br->getSuccessor(1);
784 BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange);
785 NewBr->setMetadata(LLVMContext::MD_prof,
786 Br->getMetadata(LLVMContext::MD_prof));
787 ReplaceInstWithInst(InitialBB->getTerminator(), NewBr);
788
789 // Update phis in Else resulting from InitialBB being split
790 for (auto &Phi : Else->phis())
791 Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB);
792
793 IRBuilder<> ThenB(CI);
794 return createBitSetTest(ThenB, TIL, BitOffset);
795 }
796
797 IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false));
798
799 // Now that we know that the offset is in range and aligned, load the
800 // appropriate bit from the bitset.
801 Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
802
803 // The value we want is 0 if we came directly from the initial block
804 // (having failed the range or alignment checks), or the loaded bit if
805 // we came from the block in which we loaded it.
806 B.SetInsertPoint(CI);
807 PHINode *P = B.CreatePHI(Int1Ty, 2);
808 P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
809 P->addIncoming(Bit, ThenB.GetInsertBlock());
810 return P;
811}
812
813/// Given a disjoint set of type identifiers and globals, lay out the globals,
814/// build the bit sets and lower the llvm.type.test calls.
815void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
817 // Build a new global with the combined contents of the referenced globals.
818 // This global is a struct whose even-indexed elements contain the original
819 // contents of the referenced globals and whose odd-indexed elements contain
820 // any padding required to align the next element to the next power of 2 plus
821 // any additional padding required to meet its alignment requirements.
822 std::vector<Constant *> GlobalInits;
823 const DataLayout &DL = M.getDataLayout();
825 Align MaxAlign;
826 uint64_t CurOffset = 0;
827 uint64_t DesiredPadding = 0;
828 for (GlobalTypeMember *G : Globals) {
829 auto *GV = cast<GlobalVariable>(G->getGlobal());
830 Align Alignment =
831 DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType());
832 MaxAlign = std::max(MaxAlign, Alignment);
833 uint64_t GVOffset = alignTo(CurOffset + DesiredPadding, Alignment);
834 GlobalLayout[G] = GVOffset;
835 if (GVOffset != 0) {
836 uint64_t Padding = GVOffset - CurOffset;
837 GlobalInits.push_back(
839 }
840
841 GlobalInits.push_back(GV->getInitializer());
842 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
843 CurOffset = GVOffset + InitSize;
844
845 // Compute the amount of padding that we'd like for the next element.
846 DesiredPadding = NextPowerOf2(InitSize - 1) - InitSize;
847
848 // Experiments of different caps with Chromium on both x64 and ARM64
849 // have shown that the 32-byte cap generates the smallest binary on
850 // both platforms while different caps yield similar performance.
851 // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
852 if (DesiredPadding > 32)
853 DesiredPadding = alignTo(InitSize, 32) - InitSize;
854 }
855
856 Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
857 auto *CombinedGlobal =
858 new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
860 CombinedGlobal->setAlignment(MaxAlign);
861
862 StructType *NewTy = cast<StructType>(NewInit->getType());
863 lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
864
865 // Build aliases pointing to offsets into the combined global for each
866 // global from which we built the combined global, and replace references
867 // to the original globals with references to the aliases.
868 for (unsigned I = 0; I != Globals.size(); ++I) {
869 GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
870
871 // Multiply by 2 to account for padding elements.
872 Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
874 Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
875 NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
876 assert(GV->getType()->getAddressSpace() == 0);
877 GlobalAlias *GAlias =
878 GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(),
879 "", CombinedGlobalElemPtr, &M);
880 GAlias->setVisibility(GV->getVisibility());
881 GAlias->takeName(GV);
882 GV->replaceAllUsesWith(GAlias);
883 GV->eraseFromParent();
884 }
885}
886
887bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
888 return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
889 ObjectFormat == Triple::ELF;
890}
891
892/// Export the given type identifier so that ThinLTO backends may import it.
893/// Type identifiers are exported by adding coarse-grained information about how
894/// to test the type identifier to the summary, and creating symbols in the
895/// object file (aliases and absolute symbols) containing fine-grained
896/// information about the type identifier.
897///
898/// Returns a pointer to the location in which to store the bitmask, if
899/// applicable.
900uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
901 const TypeIdLowering &TIL) {
902 TypeTestResolution &TTRes =
903 ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
904 TTRes.TheKind = TIL.TheKind;
905
906 auto ExportGlobal = [&](StringRef Name, Constant *C) {
907 GlobalAlias *GA =
909 "__typeid_" + TypeId + "_" + Name, C, &M);
911 };
912
913 auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
914 if (shouldExportConstantsAsAbsoluteSymbols())
915 ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy));
916 else
917 Storage = cast<ConstantInt>(C)->getZExtValue();
918 };
919
920 if (TIL.TheKind != TypeTestResolution::Unsat)
921 ExportGlobal("global_addr", TIL.OffsetedGlobal);
922
923 if (TIL.TheKind == TypeTestResolution::ByteArray ||
924 TIL.TheKind == TypeTestResolution::Inline ||
925 TIL.TheKind == TypeTestResolution::AllOnes) {
926 ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
927 ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
928
929 uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
930 if (TIL.TheKind == TypeTestResolution::Inline)
931 TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
932 else
933 TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
934 }
935
936 if (TIL.TheKind == TypeTestResolution::ByteArray) {
937 ExportGlobal("byte_array", TIL.TheByteArray);
938 if (shouldExportConstantsAsAbsoluteSymbols())
939 ExportGlobal("bit_mask", TIL.BitMask);
940 else
941 return &TTRes.BitMask;
942 }
943
944 if (TIL.TheKind == TypeTestResolution::Inline)
945 ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
946
947 return nullptr;
948}
949
950LowerTypeTestsModule::TypeIdLowering
951LowerTypeTestsModule::importTypeId(StringRef TypeId) {
952 const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
953 if (!TidSummary)
954 return {}; // Unsat: no globals match this type id.
955 const TypeTestResolution &TTRes = TidSummary->TTRes;
956
957 TypeIdLowering TIL;
958 TIL.TheKind = TTRes.TheKind;
959
960 auto ImportGlobal = [&](StringRef Name) {
961 // Give the global a type of length 0 so that it is not assumed not to alias
962 // with any other global.
963 Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(),
964 Int8Arr0Ty);
965 if (auto *GV = dyn_cast<GlobalVariable>(C))
967 C = ConstantExpr::getBitCast(C, Int8PtrTy);
968 return C;
969 };
970
971 auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
972 Type *Ty) {
973 if (!shouldExportConstantsAsAbsoluteSymbols()) {
974 Constant *C =
975 ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const);
976 if (!isa<IntegerType>(Ty))
978 return C;
979 }
980
981 Constant *C = ImportGlobal(Name);
982 auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
983 if (isa<IntegerType>(Ty))
985 if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
986 return C;
987
988 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
989 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
990 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
991 GV->setMetadata(LLVMContext::MD_absolute_symbol,
992 MDNode::get(M.getContext(), {MinC, MaxC}));
993 };
994 if (AbsWidth == IntPtrTy->getBitWidth())
995 SetAbsRange(~0ull, ~0ull); // Full set.
996 else
997 SetAbsRange(0, 1ull << AbsWidth);
998 return C;
999 };
1000
1001 if (TIL.TheKind != TypeTestResolution::Unsat)
1002 TIL.OffsetedGlobal = ImportGlobal("global_addr");
1003
1004 if (TIL.TheKind == TypeTestResolution::ByteArray ||
1005 TIL.TheKind == TypeTestResolution::Inline ||
1006 TIL.TheKind == TypeTestResolution::AllOnes) {
1007 TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty);
1008 TIL.SizeM1 =
1009 ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
1010 }
1011
1012 if (TIL.TheKind == TypeTestResolution::ByteArray) {
1013 TIL.TheByteArray = ImportGlobal("byte_array");
1014 TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy);
1015 }
1016
1017 if (TIL.TheKind == TypeTestResolution::Inline)
1018 TIL.InlineBits = ImportConstant(
1019 "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
1020 TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
1021
1022 return TIL;
1023}
1024
1025void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
1026 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
1027 if (!TypeIdMDVal)
1028 report_fatal_error("Second argument of llvm.type.test must be metadata");
1029
1030 auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
1031 // If this is a local unpromoted type, which doesn't have a metadata string,
1032 // treat as Unknown and delay lowering, so that we can still utilize it for
1033 // later optimizations.
1034 if (!TypeIdStr)
1035 return;
1036
1037 TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
1038 Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
1039 if (Lowered) {
1040 CI->replaceAllUsesWith(Lowered);
1041 CI->eraseFromParent();
1042 }
1043}
1044
1045// ThinLTO backend: the function F has a jump table entry; update this module
1046// accordingly. isJumpTableCanonical describes the type of the jump table entry.
1047void LowerTypeTestsModule::importFunction(
1049 std::vector<GlobalAlias *> &AliasesToErase) {
1050 assert(F->getType()->getAddressSpace() == 0);
1051
1052 GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1053 std::string Name = std::string(F->getName());
1054
1055 if (F->isDeclarationForLinker() && isJumpTableCanonical) {
1056 // Non-dso_local functions may be overriden at run time,
1057 // don't short curcuit them
1058 if (F->isDSOLocal()) {
1059 Function *RealF = Function::Create(F->getFunctionType(),
1061 F->getAddressSpace(),
1062 Name + ".cfi", &M);
1064 replaceDirectCalls(F, RealF);
1065 }
1066 return;
1067 }
1068
1069 Function *FDecl;
1070 if (!isJumpTableCanonical) {
1071 // Either a declaration of an external function or a reference to a locally
1072 // defined jump table.
1073 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1074 F->getAddressSpace(), Name + ".cfi_jt", &M);
1076 } else {
1077 F->setName(Name + ".cfi");
1078 F->setLinkage(GlobalValue::ExternalLinkage);
1079 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1080 F->getAddressSpace(), Name, &M);
1081 FDecl->setVisibility(Visibility);
1082 Visibility = GlobalValue::HiddenVisibility;
1083
1084 // Delete aliases pointing to this function, they'll be re-created in the
1085 // merged output. Don't do it yet though because ScopedSaveAliaseesAndUsed
1086 // will want to reset the aliasees first.
1087 for (auto &U : F->uses()) {
1088 if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
1089 Function *AliasDecl = Function::Create(
1090 F->getFunctionType(), GlobalValue::ExternalLinkage,
1091 F->getAddressSpace(), "", &M);
1092 AliasDecl->takeName(A);
1093 A->replaceAllUsesWith(AliasDecl);
1094 AliasesToErase.push_back(A);
1095 }
1096 }
1097 }
1098
1099 if (F->hasExternalWeakLinkage())
1100 replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isJumpTableCanonical);
1101 else
1102 replaceCfiUses(F, FDecl, isJumpTableCanonical);
1103
1104 // Set visibility late because it's used in replaceCfiUses() to determine
1105 // whether uses need to to be replaced.
1106 F->setVisibility(Visibility);
1107}
1108
1109void LowerTypeTestsModule::lowerTypeTestCalls(
1110 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1111 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1112 CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
1113
1114 // For each type identifier in this disjoint set...
1115 for (Metadata *TypeId : TypeIds) {
1116 // Build the bitset.
1117 BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
1118 LLVM_DEBUG({
1119 if (auto MDS = dyn_cast<MDString>(TypeId))
1120 dbgs() << MDS->getString() << ": ";
1121 else
1122 dbgs() << "<unnamed>: ";
1123 BSI.print(dbgs());
1124 });
1125
1126 ByteArrayInfo *BAI = nullptr;
1127 TypeIdLowering TIL;
1128 TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
1129 Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
1130 TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
1131 TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1);
1132 if (BSI.isAllOnes()) {
1133 TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1135 } else if (BSI.BitSize <= 64) {
1136 TIL.TheKind = TypeTestResolution::Inline;
1137 uint64_t InlineBits = 0;
1138 for (auto Bit : BSI.Bits)
1139 InlineBits |= uint64_t(1) << Bit;
1140 if (InlineBits == 0)
1141 TIL.TheKind = TypeTestResolution::Unsat;
1142 else
1143 TIL.InlineBits = ConstantInt::get(
1144 (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
1145 } else {
1146 TIL.TheKind = TypeTestResolution::ByteArray;
1147 ++NumByteArraysCreated;
1148 BAI = createByteArray(BSI);
1149 TIL.TheByteArray = BAI->ByteArray;
1150 TIL.BitMask = BAI->MaskGlobal;
1151 }
1152
1153 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1154
1155 if (TIUI.IsExported) {
1156 uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
1157 if (BAI)
1158 BAI->MaskPtr = MaskPtr;
1159 }
1160
1161 // Lower each call to llvm.type.test for this type identifier.
1162 for (CallInst *CI : TIUI.CallSites) {
1163 ++NumTypeTestCallsLowered;
1164 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1165 if (Lowered) {
1166 CI->replaceAllUsesWith(Lowered);
1167 CI->eraseFromParent();
1168 }
1169 }
1170 }
1171}
1172
1173void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1174 if (Type->getNumOperands() != 2)
1175 report_fatal_error("All operands of type metadata must have 2 elements");
1176
1177 if (GO->isThreadLocal())
1178 report_fatal_error("Bit set element may not be thread-local");
1179 if (isa<GlobalVariable>(GO) && GO->hasSection())
1181 "A member of a type identifier may not have an explicit section");
1182
1183 // FIXME: We previously checked that global var member of a type identifier
1184 // must be a definition, but the IR linker may leave type metadata on
1185 // declarations. We should restore this check after fixing PR31759.
1186
1187 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
1188 if (!OffsetConstMD)
1189 report_fatal_error("Type offset must be a constant");
1190 auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
1191 if (!OffsetInt)
1192 report_fatal_error("Type offset must be an integer constant");
1193}
1194
1195static const unsigned kX86JumpTableEntrySize = 8;
1196static const unsigned kX86IBTJumpTableEntrySize = 16;
1197static const unsigned kARMJumpTableEntrySize = 4;
1198static const unsigned kARMBTIJumpTableEntrySize = 8;
1199static const unsigned kARMv6MJumpTableEntrySize = 16;
1200static const unsigned kRISCVJumpTableEntrySize = 8;
1201
1202unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
1203 switch (JumpTableArch) {
1204 case Triple::x86:
1205 case Triple::x86_64:
1206 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1207 M.getModuleFlag("cf-protection-branch")))
1208 if (MD->getZExtValue())
1211 case Triple::arm:
1213 case Triple::thumb:
1214 if (CanUseThumbBWJumpTable)
1216 else
1218 case Triple::aarch64:
1219 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1220 M.getModuleFlag("branch-target-enforcement")))
1221 if (BTE->getZExtValue())
1224 case Triple::riscv32:
1225 case Triple::riscv64:
1227 default:
1228 report_fatal_error("Unsupported architecture for jump tables");
1229 }
1230}
1231
1232// Create a jump table entry for the target. This consists of an instruction
1233// sequence containing a relative branch to Dest. Appends inline asm text,
1234// constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
1235void LowerTypeTestsModule::createJumpTableEntry(
1236 raw_ostream &AsmOS, raw_ostream &ConstraintOS,
1237 Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs,
1238 Function *Dest) {
1239 unsigned ArgIndex = AsmArgs.size();
1240
1241 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1242 bool Endbr = false;
1243 if (const auto *MD = mdconst::extract_or_null<ConstantInt>(
1244 Dest->getParent()->getModuleFlag("cf-protection-branch")))
1245 Endbr = !MD->isZero();
1246 if (Endbr)
1247 AsmOS << (JumpTableArch == Triple::x86 ? "endbr32\n" : "endbr64\n");
1248 AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
1249 if (Endbr)
1250 AsmOS << ".balign 16, 0xcc\n";
1251 else
1252 AsmOS << "int3\nint3\nint3\n";
1253 } else if (JumpTableArch == Triple::arm) {
1254 AsmOS << "b $" << ArgIndex << "\n";
1255 } else if (JumpTableArch == Triple::aarch64) {
1256 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1257 Dest->getParent()->getModuleFlag("branch-target-enforcement")))
1258 if (BTE->getZExtValue())
1259 AsmOS << "bti c\n";
1260 AsmOS << "b $" << ArgIndex << "\n";
1261 } else if (JumpTableArch == Triple::thumb) {
1262 if (!CanUseThumbBWJumpTable) {
1263 // In Armv6-M, this sequence will generate a branch without corrupting
1264 // any registers. We use two stack words; in the second, we construct the
1265 // address we'll pop into pc, and the first is used to save and restore
1266 // r0 which we use as a temporary register.
1267 //
1268 // To support position-independent use cases, the offset of the target
1269 // function is stored as a relative offset (which will expand into an
1270 // R_ARM_REL32 relocation in ELF, and presumably the equivalent in other
1271 // object file types), and added to pc after we load it. (The alternative
1272 // B.W is automatically pc-relative.)
1273 //
1274 // There are five 16-bit Thumb instructions here, so the .balign 4 adds a
1275 // sixth halfword of padding, and then the offset consumes a further 4
1276 // bytes, for a total of 16, which is very convenient since entries in
1277 // this jump table need to have power-of-two size.
1278 AsmOS << "push {r0,r1}\n"
1279 << "ldr r0, 1f\n"
1280 << "0: add r0, r0, pc\n"
1281 << "str r0, [sp, #4]\n"
1282 << "pop {r0,pc}\n"
1283 << ".balign 4\n"
1284 << "1: .word $" << ArgIndex << " - (0b + 4)\n";
1285 } else {
1286 AsmOS << "b.w $" << ArgIndex << "\n";
1287 }
1288 } else if (JumpTableArch == Triple::riscv32 ||
1289 JumpTableArch == Triple::riscv64) {
1290 AsmOS << "tail $" << ArgIndex << "@plt\n";
1291 } else {
1292 report_fatal_error("Unsupported architecture for jump tables");
1293 }
1294
1295 ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
1296 AsmArgs.push_back(Dest);
1297}
1298
1299Type *LowerTypeTestsModule::getJumpTableEntryType() {
1300 return ArrayType::get(Int8Ty, getJumpTableEntrySize());
1301}
1302
1303/// Given a disjoint set of type identifiers and functions, build the bit sets
1304/// and lower the llvm.type.test calls, architecture dependently.
1305void LowerTypeTestsModule::buildBitSetsFromFunctions(
1307 if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1308 Arch == Triple::thumb || Arch == Triple::aarch64 ||
1309 Arch == Triple::riscv32 || Arch == Triple::riscv64)
1310 buildBitSetsFromFunctionsNative(TypeIds, Functions);
1311 else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1312 buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1313 else
1314 report_fatal_error("Unsupported architecture for jump tables");
1315}
1316
1317void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1318 GlobalVariable *GV) {
1319 if (WeakInitializerFn == nullptr) {
1320 WeakInitializerFn = Function::Create(
1321 FunctionType::get(Type::getVoidTy(M.getContext()),
1322 /* IsVarArg */ false),
1324 M.getDataLayout().getProgramAddressSpace(),
1325 "__cfi_global_var_init", &M);
1326 BasicBlock *BB =
1327 BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
1328 ReturnInst::Create(M.getContext(), BB);
1329 WeakInitializerFn->setSection(
1330 ObjectFormat == Triple::MachO
1331 ? "__TEXT,__StaticInit,regular,pure_instructions"
1332 : ".text.startup");
1333 // This code is equivalent to relocation application, and should run at the
1334 // earliest possible time (i.e. with the highest priority).
1335 appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
1336 }
1337
1338 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1339 GV->setConstant(false);
1340 IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlign());
1342}
1343
1344void LowerTypeTestsModule::findGlobalVariableUsersOf(
1346 for (auto *U : C->users()){
1347 if (auto *GV = dyn_cast<GlobalVariable>(U))
1348 Out.insert(GV);
1349 else if (auto *C2 = dyn_cast<Constant>(U))
1350 findGlobalVariableUsersOf(C2, Out);
1351 }
1352}
1353
1354// Replace all uses of F with (F ? JT : 0).
1355void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1356 Function *F, Constant *JT, bool IsJumpTableCanonical) {
1357 // The target expression can not appear in a constant initializer on most
1358 // (all?) targets. Switch to a runtime initializer.
1360 findGlobalVariableUsersOf(F, GlobalVarUsers);
1361 for (auto *GV : GlobalVarUsers)
1362 moveInitializerToModuleConstructor(GV);
1363
1364 // Can not RAUW F with an expression that uses F. Replace with a temporary
1365 // placeholder first.
1366 Function *PlaceholderFn =
1367 Function::Create(cast<FunctionType>(F->getValueType()),
1369 F->getAddressSpace(), "", &M);
1370 replaceCfiUses(F, PlaceholderFn, IsJumpTableCanonical);
1371
1373 // Don't use range based loop, because use list will be modified.
1374 while (!PlaceholderFn->use_empty()) {
1375 Use &U = *PlaceholderFn->use_begin();
1376 auto *InsertPt = dyn_cast<Instruction>(U.getUser());
1377 assert(InsertPt && "Non-instruction users should have been eliminated");
1378 auto *PN = dyn_cast<PHINode>(InsertPt);
1379 if (PN)
1380 InsertPt = PN->getIncomingBlock(U)->getTerminator();
1381 IRBuilder Builder(InsertPt);
1382 Value *ICmp = Builder.CreateICmp(CmpInst::ICMP_NE, F,
1383 Constant::getNullValue(F->getType()));
1384 Value *Select = Builder.CreateSelect(ICmp, JT,
1385 Constant::getNullValue(F->getType()));
1386 // For phi nodes, we need to update the incoming value for all operands
1387 // with the same predecessor.
1388 if (PN)
1389 PN->setIncomingValueForBlock(InsertPt->getParent(), Select);
1390 else
1391 U.set(Select);
1392 }
1393 PlaceholderFn->eraseFromParent();
1394}
1395
1396static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1397 Attribute TFAttr = F->getFnAttribute("target-features");
1398 if (TFAttr.isValid()) {
1400 TFAttr.getValueAsString().split(Features, ',');
1401 for (StringRef Feature : Features) {
1402 if (Feature == "-thumb-mode")
1403 return false;
1404 else if (Feature == "+thumb-mode")
1405 return true;
1406 }
1407 }
1408
1409 return ModuleArch == Triple::thumb;
1410}
1411
1412// Each jump table must be either ARM or Thumb as a whole for the bit-test math
1413// to work. Pick one that matches the majority of members to minimize interop
1414// veneers inserted by the linker.
1415Triple::ArchType LowerTypeTestsModule::selectJumpTableArmEncoding(
1416 ArrayRef<GlobalTypeMember *> Functions) {
1417 if (Arch != Triple::arm && Arch != Triple::thumb)
1418 return Arch;
1419
1420 if (!CanUseThumbBWJumpTable && CanUseArmJumpTable) {
1421 // In architectures that provide Arm and Thumb-1 but not Thumb-2,
1422 // we should always prefer the Arm jump table format, because the
1423 // Thumb-1 one is larger and slower.
1424 return Triple::arm;
1425 }
1426
1427 // Otherwise, go with majority vote.
1428 unsigned ArmCount = 0, ThumbCount = 0;
1429 for (const auto GTM : Functions) {
1430 if (!GTM->isJumpTableCanonical()) {
1431 // PLT stubs are always ARM.
1432 // FIXME: This is the wrong heuristic for non-canonical jump tables.
1433 ++ArmCount;
1434 continue;
1435 }
1436
1437 Function *F = cast<Function>(GTM->getGlobal());
1438 ++(isThumbFunction(F, Arch) ? ThumbCount : ArmCount);
1439 }
1440
1441 return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1442}
1443
1444void LowerTypeTestsModule::createJumpTable(
1446 std::string AsmStr, ConstraintStr;
1447 raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
1449 AsmArgs.reserve(Functions.size() * 2);
1450
1451 for (GlobalTypeMember *GTM : Functions)
1452 createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
1453 cast<Function>(GTM->getGlobal()));
1454
1455 // Align the whole table by entry size.
1456 F->setAlignment(Align(getJumpTableEntrySize()));
1457 // Skip prologue.
1458 // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
1459 // Luckily, this function does not get any prologue even without the
1460 // attribute.
1461 if (OS != Triple::Win32)
1462 F->addFnAttr(Attribute::Naked);
1463 if (JumpTableArch == Triple::arm)
1464 F->addFnAttr("target-features", "-thumb-mode");
1465 if (JumpTableArch == Triple::thumb) {
1466 F->addFnAttr("target-features", "+thumb-mode");
1467 if (CanUseThumbBWJumpTable) {
1468 // Thumb jump table assembly needs Thumb2. The following attribute is
1469 // added by Clang for -march=armv7.
1470 F->addFnAttr("target-cpu", "cortex-a8");
1471 }
1472 }
1473 // When -mbranch-protection= is used, the inline asm adds a BTI. Suppress BTI
1474 // for the function to avoid double BTI. This is a no-op without
1475 // -mbranch-protection=.
1476 if (JumpTableArch == Triple::aarch64) {
1477 F->addFnAttr("branch-target-enforcement", "false");
1478 F->addFnAttr("sign-return-address", "none");
1479 }
1480 if (JumpTableArch == Triple::riscv32 || JumpTableArch == Triple::riscv64) {
1481 // Make sure the jump table assembly is not modified by the assembler or
1482 // the linker.
1483 F->addFnAttr("target-features", "-c,-relax");
1484 }
1485 // When -fcf-protection= is used, the inline asm adds an ENDBR. Suppress ENDBR
1486 // for the function to avoid double ENDBR. This is a no-op without
1487 // -fcf-protection=.
1488 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64)
1489 F->addFnAttr(Attribute::NoCfCheck);
1490 // Make sure we don't emit .eh_frame for this function.
1491 F->addFnAttr(Attribute::NoUnwind);
1492
1493 BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
1494 IRBuilder<> IRB(BB);
1495
1496 SmallVector<Type *, 16> ArgTypes;
1497 ArgTypes.reserve(AsmArgs.size());
1498 for (const auto &Arg : AsmArgs)
1499 ArgTypes.push_back(Arg->getType());
1500 InlineAsm *JumpTableAsm =
1501 InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
1502 AsmOS.str(), ConstraintOS.str(),
1503 /*hasSideEffects=*/true);
1504
1505 IRB.CreateCall(JumpTableAsm, AsmArgs);
1506 IRB.CreateUnreachable();
1507}
1508
1509/// Given a disjoint set of type identifiers and functions, build a jump table
1510/// for the functions, build the bit sets and lower the llvm.type.test calls.
1511void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1513 // Unlike the global bitset builder, the function bitset builder cannot
1514 // re-arrange functions in a particular order and base its calculations on the
1515 // layout of the functions' entry points, as we have no idea how large a
1516 // particular function will end up being (the size could even depend on what
1517 // this pass does!) Instead, we build a jump table, which is a block of code
1518 // consisting of one branch instruction for each of the functions in the bit
1519 // set that branches to the target function, and redirect any taken function
1520 // addresses to the corresponding jump table entry. In the object file's
1521 // symbol table, the symbols for the target functions also refer to the jump
1522 // table entries, so that addresses taken outside the module will pass any
1523 // verification done inside the module.
1524 //
1525 // In more concrete terms, suppose we have three functions f, g, h which are
1526 // of the same type, and a function foo that returns their addresses:
1527 //
1528 // f:
1529 // mov 0, %eax
1530 // ret
1531 //
1532 // g:
1533 // mov 1, %eax
1534 // ret
1535 //
1536 // h:
1537 // mov 2, %eax
1538 // ret
1539 //
1540 // foo:
1541 // mov f, %eax
1542 // mov g, %edx
1543 // mov h, %ecx
1544 // ret
1545 //
1546 // We output the jump table as module-level inline asm string. The end result
1547 // will (conceptually) look like this:
1548 //
1549 // f = .cfi.jumptable
1550 // g = .cfi.jumptable + 4
1551 // h = .cfi.jumptable + 8
1552 // .cfi.jumptable:
1553 // jmp f.cfi ; 5 bytes
1554 // int3 ; 1 byte
1555 // int3 ; 1 byte
1556 // int3 ; 1 byte
1557 // jmp g.cfi ; 5 bytes
1558 // int3 ; 1 byte
1559 // int3 ; 1 byte
1560 // int3 ; 1 byte
1561 // jmp h.cfi ; 5 bytes
1562 // int3 ; 1 byte
1563 // int3 ; 1 byte
1564 // int3 ; 1 byte
1565 //
1566 // f.cfi:
1567 // mov 0, %eax
1568 // ret
1569 //
1570 // g.cfi:
1571 // mov 1, %eax
1572 // ret
1573 //
1574 // h.cfi:
1575 // mov 2, %eax
1576 // ret
1577 //
1578 // foo:
1579 // mov f, %eax
1580 // mov g, %edx
1581 // mov h, %ecx
1582 // ret
1583 //
1584 // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1585 // normal case the check can be carried out using the same kind of simple
1586 // arithmetic that we normally use for globals.
1587
1588 // FIXME: find a better way to represent the jumptable in the IR.
1589 assert(!Functions.empty());
1590
1591 // Decide on the jump table encoding, so that we know how big the
1592 // entries will be.
1593 JumpTableArch = selectJumpTableArmEncoding(Functions);
1594
1595 // Build a simple layout based on the regular layout of jump tables.
1597 unsigned EntrySize = getJumpTableEntrySize();
1598 for (unsigned I = 0; I != Functions.size(); ++I)
1599 GlobalLayout[Functions[I]] = I * EntrySize;
1600
1601 Function *JumpTableFn =
1603 /* IsVarArg */ false),
1605 M.getDataLayout().getProgramAddressSpace(),
1606 ".cfi.jumptable", &M);
1608 ArrayType::get(getJumpTableEntryType(), Functions.size());
1609 auto JumpTable =
1610 ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
1611
1612 lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
1613
1614 {
1615 ScopedSaveAliaseesAndUsed S(M);
1616
1617 // Build aliases pointing to offsets into the jump table, and replace
1618 // references to the original functions with references to the aliases.
1619 for (unsigned I = 0; I != Functions.size(); ++I) {
1620 Function *F = cast<Function>(Functions[I]->getGlobal());
1621 bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
1622
1623 Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
1625 JumpTableType, JumpTable,
1627 ConstantInt::get(IntPtrTy, I)}),
1628 F->getType());
1629
1630 const bool IsExported = Functions[I]->isExported();
1631 if (!IsJumpTableCanonical) {
1632 GlobalValue::LinkageTypes LT = IsExported
1635 GlobalAlias *JtAlias = GlobalAlias::create(F->getValueType(), 0, LT,
1636 F->getName() + ".cfi_jt",
1637 CombinedGlobalElemPtr, &M);
1638 if (IsExported)
1640 else
1641 appendToUsed(M, {JtAlias});
1642 }
1643
1644 if (IsExported) {
1645 if (IsJumpTableCanonical)
1646 ExportSummary->cfiFunctionDefs().insert(std::string(F->getName()));
1647 else
1648 ExportSummary->cfiFunctionDecls().insert(std::string(F->getName()));
1649 }
1650
1651 if (!IsJumpTableCanonical) {
1652 if (F->hasExternalWeakLinkage())
1653 replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr,
1654 IsJumpTableCanonical);
1655 else
1656 replaceCfiUses(F, CombinedGlobalElemPtr, IsJumpTableCanonical);
1657 } else {
1658 assert(F->getType()->getAddressSpace() == 0);
1659
1660 GlobalAlias *FAlias =
1661 GlobalAlias::create(F->getValueType(), 0, F->getLinkage(), "",
1662 CombinedGlobalElemPtr, &M);
1663 FAlias->setVisibility(F->getVisibility());
1664 FAlias->takeName(F);
1665 if (FAlias->hasName())
1666 F->setName(FAlias->getName() + ".cfi");
1667 replaceCfiUses(F, FAlias, IsJumpTableCanonical);
1668 if (!F->hasLocalLinkage())
1669 F->setVisibility(GlobalVariable::HiddenVisibility);
1670 }
1671 }
1672 }
1673
1674 createJumpTable(JumpTableFn, Functions);
1675}
1676
1677/// Assign a dummy layout using an incrementing counter, tag each function
1678/// with its index represented as metadata, and lower each type test to an
1679/// integer range comparison. During generation of the indirect function call
1680/// table in the backend, it will assign the given indexes.
1681/// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1682/// been finalized.
1683void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1685 assert(!Functions.empty());
1686
1687 // Build consecutive monotonic integer ranges for each call target set
1689
1690 for (GlobalTypeMember *GTM : Functions) {
1691 Function *F = cast<Function>(GTM->getGlobal());
1692
1693 // Skip functions that are not address taken, to avoid bloating the table
1694 if (!F->hasAddressTaken())
1695 continue;
1696
1697 // Store metadata with the index for each function
1698 MDNode *MD = MDNode::get(F->getContext(),
1700 ConstantInt::get(Int64Ty, IndirectIndex))));
1701 F->setMetadata("wasm.index", MD);
1702
1703 // Assign the counter value
1704 GlobalLayout[GTM] = IndirectIndex++;
1705 }
1706
1707 // The indirect function table index space starts at zero, so pass a NULL
1708 // pointer as the subtracted "jump table" offset.
1709 lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
1710 GlobalLayout);
1711}
1712
1713void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1715 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
1716 DenseMap<Metadata *, uint64_t> TypeIdIndices;
1717 for (unsigned I = 0; I != TypeIds.size(); ++I)
1718 TypeIdIndices[TypeIds[I]] = I;
1719
1720 // For each type identifier, build a set of indices that refer to members of
1721 // the type identifier.
1722 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1723 unsigned GlobalIndex = 0;
1725 for (GlobalTypeMember *GTM : Globals) {
1726 for (MDNode *Type : GTM->types()) {
1727 // Type = { offset, type identifier }
1728 auto I = TypeIdIndices.find(Type->getOperand(1));
1729 if (I != TypeIdIndices.end())
1730 TypeMembers[I->second].insert(GlobalIndex);
1731 }
1732 GlobalIndices[GTM] = GlobalIndex;
1733 GlobalIndex++;
1734 }
1735
1736 for (ICallBranchFunnel *JT : ICallBranchFunnels) {
1737 TypeMembers.emplace_back();
1738 std::set<uint64_t> &TMSet = TypeMembers.back();
1739 for (GlobalTypeMember *T : JT->targets())
1740 TMSet.insert(GlobalIndices[T]);
1741 }
1742
1743 // Order the sets of indices by size. The GlobalLayoutBuilder works best
1744 // when given small index sets first.
1745 llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1,
1746 const std::set<uint64_t> &O2) {
1747 return O1.size() < O2.size();
1748 });
1749
1750 // Create a GlobalLayoutBuilder and provide it with index sets as layout
1751 // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1752 // close together as possible.
1753 GlobalLayoutBuilder GLB(Globals.size());
1754 for (auto &&MemSet : TypeMembers)
1755 GLB.addFragment(MemSet);
1756
1757 // Build a vector of globals with the computed layout.
1758 bool IsGlobalSet =
1759 Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
1760 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1761 auto OGTMI = OrderedGTMs.begin();
1762 for (auto &&F : GLB.Fragments) {
1763 for (auto &&Offset : F) {
1764 if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
1765 report_fatal_error("Type identifier may not contain both global "
1766 "variables and functions");
1767 *OGTMI++ = Globals[Offset];
1768 }
1769 }
1770
1771 // Build the bitsets from this disjoint set.
1772 if (IsGlobalSet)
1773 buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
1774 else
1775 buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
1776}
1777
1778/// Lower all type tests in this module.
1779LowerTypeTestsModule::LowerTypeTestsModule(
1780 Module &M, ModuleAnalysisManager &AM, ModuleSummaryIndex *ExportSummary,
1781 const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
1782 : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary),
1783 DropTypeTests(DropTypeTests || ClDropTypeTests) {
1784 assert(!(ExportSummary && ImportSummary));
1785 Triple TargetTriple(M.getTargetTriple());
1786 Arch = TargetTriple.getArch();
1787 if (Arch == Triple::arm)
1788 CanUseArmJumpTable = true;
1789 if (Arch == Triple::arm || Arch == Triple::thumb) {
1790 auto &FAM =
1792 for (Function &F : M) {
1794 if (TTI.hasArmWideBranch(false))
1795 CanUseArmJumpTable = true;
1796 if (TTI.hasArmWideBranch(true))
1797 CanUseThumbBWJumpTable = true;
1798 }
1799 }
1800 OS = TargetTriple.getOS();
1801 ObjectFormat = TargetTriple.getObjectFormat();
1802}
1803
1804bool LowerTypeTestsModule::runForTesting(Module &M, ModuleAnalysisManager &AM) {
1805 ModuleSummaryIndex Summary(/*HaveGVs=*/false);
1806
1807 // Handle the command-line summary arguments. This code is for testing
1808 // purposes only, so we handle errors directly.
1809 if (!ClReadSummary.empty()) {
1810 ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1811 ": ");
1812 auto ReadSummaryFile =
1814
1815 yaml::Input In(ReadSummaryFile->getBuffer());
1816 In >> Summary;
1817 ExitOnErr(errorCodeToError(In.error()));
1818 }
1819
1820 bool Changed =
1821 LowerTypeTestsModule(
1822 M, AM,
1823 ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
1824 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr,
1825 /*DropTypeTests*/ false)
1826 .lower();
1827
1828 if (!ClWriteSummary.empty()) {
1829 ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
1830 ": ");
1831 std::error_code EC;
1833 ExitOnErr(errorCodeToError(EC));
1834
1835 yaml::Output Out(OS);
1836 Out << Summary;
1837 }
1838
1839 return Changed;
1840}
1841
1842static bool isDirectCall(Use& U) {
1843 auto *Usr = dyn_cast<CallInst>(U.getUser());
1844 if (Usr) {
1845 auto *CB = dyn_cast<CallBase>(Usr);
1846 if (CB && CB->isCallee(&U))
1847 return true;
1848 }
1849 return false;
1850}
1851
1852void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
1853 bool IsJumpTableCanonical) {
1855 for (Use &U : llvm::make_early_inc_range(Old->uses())) {
1856 // Skip block addresses and no_cfi values, which refer to the function
1857 // body instead of the jump table.
1858 if (isa<BlockAddress, NoCFIValue>(U.getUser()))
1859 continue;
1860
1861 // Skip direct calls to externally defined or non-dso_local functions
1862 if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
1863 continue;
1864
1865 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
1866 // constant because they are uniqued.
1867 if (auto *C = dyn_cast<Constant>(U.getUser())) {
1868 if (!isa<GlobalValue>(C)) {
1869 // Save unique users to avoid processing operand replacement
1870 // more than once.
1871 Constants.insert(C);
1872 continue;
1873 }
1874 }
1875
1876 U.set(New);
1877 }
1878
1879 // Process operand replacement of saved constants.
1880 for (auto *C : Constants)
1881 C->handleOperandChange(Old, New);
1882}
1883
1884void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
1886}
1887
1888static void dropTypeTests(Module &M, Function &TypeTestFunc) {
1889 for (Use &U : llvm::make_early_inc_range(TypeTestFunc.uses())) {
1890 auto *CI = cast<CallInst>(U.getUser());
1891 // Find and erase llvm.assume intrinsics for this llvm.type.test call.
1892 for (Use &CIU : llvm::make_early_inc_range(CI->uses()))
1893 if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
1894 Assume->eraseFromParent();
1895 // If the assume was merged with another assume, we might have a use on a
1896 // phi (which will feed the assume). Simply replace the use on the phi
1897 // with "true" and leave the merged assume.
1898 if (!CI->use_empty()) {
1899 assert(
1900 all_of(CI->users(), [](User *U) -> bool { return isa<PHINode>(U); }));
1901 CI->replaceAllUsesWith(ConstantInt::getTrue(M.getContext()));
1902 }
1903 CI->eraseFromParent();
1904 }
1905}
1906
1907bool LowerTypeTestsModule::lower() {
1908 Function *TypeTestFunc =
1909 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1910
1911 if (DropTypeTests) {
1912 if (TypeTestFunc)
1913 dropTypeTests(M, *TypeTestFunc);
1914 // Normally we'd have already removed all @llvm.public.type.test calls,
1915 // except for in the case where we originally were performing ThinLTO but
1916 // decided not to in the backend.
1917 Function *PublicTypeTestFunc =
1918 M.getFunction(Intrinsic::getName(Intrinsic::public_type_test));
1919 if (PublicTypeTestFunc)
1920 dropTypeTests(M, *PublicTypeTestFunc);
1921 if (TypeTestFunc || PublicTypeTestFunc) {
1922 // We have deleted the type intrinsics, so we no longer have enough
1923 // information to reason about the liveness of virtual function pointers
1924 // in GlobalDCE.
1925 for (GlobalVariable &GV : M.globals())
1926 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1927 return true;
1928 }
1929 return false;
1930 }
1931
1932 // If only some of the modules were split, we cannot correctly perform
1933 // this transformation. We already checked for the presense of type tests
1934 // with partially split modules during the thin link, and would have emitted
1935 // an error if any were found, so here we can simply return.
1936 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1937 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
1938 return false;
1939
1940 Function *ICallBranchFunnelFunc =
1941 M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel));
1942 if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
1943 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
1944 !ExportSummary && !ImportSummary)
1945 return false;
1946
1947 if (ImportSummary) {
1948 if (TypeTestFunc)
1949 for (Use &U : llvm::make_early_inc_range(TypeTestFunc->uses()))
1950 importTypeTest(cast<CallInst>(U.getUser()));
1951
1952 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
1954 "unexpected call to llvm.icall.branch.funnel during import phase");
1955
1958 for (auto &F : M) {
1959 // CFI functions are either external, or promoted. A local function may
1960 // have the same name, but it's not the one we are looking for.
1961 if (F.hasLocalLinkage())
1962 continue;
1963 if (ImportSummary->cfiFunctionDefs().count(std::string(F.getName())))
1964 Defs.push_back(&F);
1965 else if (ImportSummary->cfiFunctionDecls().count(
1966 std::string(F.getName())))
1967 Decls.push_back(&F);
1968 }
1969
1970 std::vector<GlobalAlias *> AliasesToErase;
1971 {
1972 ScopedSaveAliaseesAndUsed S(M);
1973 for (auto *F : Defs)
1974 importFunction(F, /*isJumpTableCanonical*/ true, AliasesToErase);
1975 for (auto *F : Decls)
1976 importFunction(F, /*isJumpTableCanonical*/ false, AliasesToErase);
1977 }
1978 for (GlobalAlias *GA : AliasesToErase)
1979 GA->eraseFromParent();
1980
1981 return true;
1982 }
1983
1984 // Equivalence class set containing type identifiers and the globals that
1985 // reference them. This is used to partition the set of type identifiers in
1986 // the module into disjoint sets.
1987 using GlobalClassesTy = EquivalenceClasses<
1989 GlobalClassesTy GlobalClasses;
1990
1991 // Verify the type metadata and build a few data structures to let us
1992 // efficiently enumerate the type identifiers associated with a global:
1993 // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
1994 // of associated type metadata) and a mapping from type identifiers to their
1995 // list of GlobalTypeMembers and last observed index in the list of globals.
1996 // The indices will be used later to deterministically order the list of type
1997 // identifiers.
1998 BumpPtrAllocator Alloc;
1999 struct TIInfo {
2000 unsigned UniqueId;
2001 std::vector<GlobalTypeMember *> RefGlobals;
2002 };
2004 unsigned CurUniqueId = 0;
2006
2007 // Cross-DSO CFI emits jumptable entries for exported functions as well as
2008 // address taken functions in case they are address taken in other modules.
2009 const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr;
2010
2011 struct ExportedFunctionInfo {
2013 MDNode *FuncMD; // {name, linkage, type[, type...]}
2014 };
2016 if (ExportSummary) {
2017 // A set of all functions that are address taken by a live global object.
2018 DenseSet<GlobalValue::GUID> AddressTaken;
2019 for (auto &I : *ExportSummary)
2020 for (auto &GVS : I.second.SummaryList)
2021 if (GVS->isLive())
2022 for (const auto &Ref : GVS->refs())
2023 AddressTaken.insert(Ref.getGUID());
2024
2025 NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions");
2026 if (CfiFunctionsMD) {
2027 for (auto *FuncMD : CfiFunctionsMD->operands()) {
2028 assert(FuncMD->getNumOperands() >= 2);
2029 StringRef FunctionName =
2030 cast<MDString>(FuncMD->getOperand(0))->getString();
2032 cast<ConstantAsMetadata>(FuncMD->getOperand(1))
2033 ->getValue()
2034 ->getUniqueInteger()
2035 .getZExtValue());
2038 // Do not emit jumptable entries for functions that are not-live and
2039 // have no live references (and are not exported with cross-DSO CFI.)
2040 if (!ExportSummary->isGUIDLive(GUID))
2041 continue;
2042 if (!AddressTaken.count(GUID)) {
2043 if (!CrossDsoCfi || Linkage != CFL_Definition)
2044 continue;
2045
2046 bool Exported = false;
2047 if (auto VI = ExportSummary->getValueInfo(GUID))
2048 for (const auto &GVS : VI.getSummaryList())
2049 if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
2050 Exported = true;
2051
2052 if (!Exported)
2053 continue;
2054 }
2055 auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}});
2056 if (!P.second && P.first->second.Linkage != CFL_Definition)
2057 P.first->second = {Linkage, FuncMD};
2058 }
2059
2060 for (const auto &P : ExportedFunctions) {
2061 StringRef FunctionName = P.first;
2062 CfiFunctionLinkage Linkage = P.second.Linkage;
2063 MDNode *FuncMD = P.second.FuncMD;
2064 Function *F = M.getFunction(FunctionName);
2065 if (F && F->hasLocalLinkage()) {
2066 // Locally defined function that happens to have the same name as a
2067 // function defined in a ThinLTO module. Rename it to move it out of
2068 // the way of the external reference that we're about to create.
2069 // Note that setName will find a unique name for the function, so even
2070 // if there is an existing function with the suffix there won't be a
2071 // name collision.
2072 F->setName(F->getName() + ".1");
2073 F = nullptr;
2074 }
2075
2076 if (!F)
2078 FunctionType::get(Type::getVoidTy(M.getContext()), false),
2079 GlobalVariable::ExternalLinkage,
2080 M.getDataLayout().getProgramAddressSpace(), FunctionName, &M);
2081
2082 // If the function is available_externally, remove its definition so
2083 // that it is handled the same way as a declaration. Later we will try
2084 // to create an alias using this function's linkage, which will fail if
2085 // the linkage is available_externally. This will also result in us
2086 // following the code path below to replace the type metadata.
2087 if (F->hasAvailableExternallyLinkage()) {
2088 F->setLinkage(GlobalValue::ExternalLinkage);
2089 F->deleteBody();
2090 F->setComdat(nullptr);
2091 F->clearMetadata();
2092 }
2093
2094 // Update the linkage for extern_weak declarations when a definition
2095 // exists.
2096 if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
2097 F->setLinkage(GlobalValue::ExternalLinkage);
2098
2099 // If the function in the full LTO module is a declaration, replace its
2100 // type metadata with the type metadata we found in cfi.functions. That
2101 // metadata is presumed to be more accurate than the metadata attached
2102 // to the declaration.
2103 if (F->isDeclaration()) {
2104 if (Linkage == CFL_WeakDeclaration)
2106
2107 F->eraseMetadata(LLVMContext::MD_type);
2108 for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
2109 F->addMetadata(LLVMContext::MD_type,
2110 *cast<MDNode>(FuncMD->getOperand(I).get()));
2111 }
2112 }
2113 }
2114 }
2115
2117 for (GlobalObject &GO : M.global_objects()) {
2118 if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
2119 continue;
2120
2121 Types.clear();
2122 GO.getMetadata(LLVMContext::MD_type, Types);
2123
2124 bool IsJumpTableCanonical = false;
2125 bool IsExported = false;
2126 if (Function *F = dyn_cast<Function>(&GO)) {
2127 IsJumpTableCanonical = isJumpTableCanonical(F);
2128 if (ExportedFunctions.count(F->getName())) {
2129 IsJumpTableCanonical |=
2130 ExportedFunctions[F->getName()].Linkage == CFL_Definition;
2131 IsExported = true;
2132 // TODO: The logic here checks only that the function is address taken,
2133 // not that the address takers are live. This can be updated to check
2134 // their liveness and emit fewer jumptable entries once monolithic LTO
2135 // builds also emit summaries.
2136 } else if (!F->hasAddressTaken()) {
2137 if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
2138 continue;
2139 }
2140 }
2141
2142 auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical,
2143 IsExported, Types);
2144 GlobalTypeMembers[&GO] = GTM;
2145 for (MDNode *Type : Types) {
2146 verifyTypeMDNode(&GO, Type);
2147 auto &Info = TypeIdInfo[Type->getOperand(1)];
2148 Info.UniqueId = ++CurUniqueId;
2149 Info.RefGlobals.push_back(GTM);
2150 }
2151 }
2152
2153 auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
2154 // Add the call site to the list of call sites for this type identifier. We
2155 // also use TypeIdUsers to keep track of whether we have seen this type
2156 // identifier before. If we have, we don't need to re-add the referenced
2157 // globals to the equivalence class.
2158 auto Ins = TypeIdUsers.insert({TypeId, {}});
2159 if (Ins.second) {
2160 // Add the type identifier to the equivalence class.
2161 GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
2162 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
2163
2164 // Add the referenced globals to the type identifier's equivalence class.
2165 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2166 CurSet = GlobalClasses.unionSets(
2167 CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
2168 }
2169
2170 return Ins.first->second;
2171 };
2172
2173 if (TypeTestFunc) {
2174 for (const Use &U : TypeTestFunc->uses()) {
2175 auto CI = cast<CallInst>(U.getUser());
2176 // If this type test is only used by llvm.assume instructions, it
2177 // was used for whole program devirtualization, and is being kept
2178 // for use by other optimization passes. We do not need or want to
2179 // lower it here. We also don't want to rewrite any associated globals
2180 // unnecessarily. These will be removed by a subsequent LTT invocation
2181 // with the DropTypeTests flag set.
2182 bool OnlyAssumeUses = !CI->use_empty();
2183 for (const Use &CIU : CI->uses()) {
2184 if (isa<AssumeInst>(CIU.getUser()))
2185 continue;
2186 OnlyAssumeUses = false;
2187 break;
2188 }
2189 if (OnlyAssumeUses)
2190 continue;
2191
2192 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
2193 if (!TypeIdMDVal)
2194 report_fatal_error("Second argument of llvm.type.test must be metadata");
2195 auto TypeId = TypeIdMDVal->getMetadata();
2196 AddTypeIdUse(TypeId).CallSites.push_back(CI);
2197 }
2198 }
2199
2200 if (ICallBranchFunnelFunc) {
2201 for (const Use &U : ICallBranchFunnelFunc->uses()) {
2202 if (Arch != Triple::x86_64)
2204 "llvm.icall.branch.funnel not supported on this target");
2205
2206 auto CI = cast<CallInst>(U.getUser());
2207
2208 std::vector<GlobalTypeMember *> Targets;
2209 if (CI->arg_size() % 2 != 1)
2210 report_fatal_error("number of arguments should be odd");
2211
2212 GlobalClassesTy::member_iterator CurSet;
2213 for (unsigned I = 1; I != CI->arg_size(); I += 2) {
2214 int64_t Offset;
2215 auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
2216 CI->getOperand(I), Offset, M.getDataLayout()));
2217 if (!Base)
2219 "Expected branch funnel operand to be global value");
2220
2221 GlobalTypeMember *GTM = GlobalTypeMembers[Base];
2222 Targets.push_back(GTM);
2223 GlobalClassesTy::member_iterator NewSet =
2224 GlobalClasses.findLeader(GlobalClasses.insert(GTM));
2225 if (I == 1)
2226 CurSet = NewSet;
2227 else
2228 CurSet = GlobalClasses.unionSets(CurSet, NewSet);
2229 }
2230
2231 GlobalClasses.unionSets(
2232 CurSet, GlobalClasses.findLeader(
2233 GlobalClasses.insert(ICallBranchFunnel::create(
2234 Alloc, CI, Targets, ++CurUniqueId))));
2235 }
2236 }
2237
2238 if (ExportSummary) {
2240 for (auto &P : TypeIdInfo) {
2241 if (auto *TypeId = dyn_cast<MDString>(P.first))
2242 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
2243 TypeId);
2244 }
2245
2246 for (auto &P : *ExportSummary) {
2247 for (auto &S : P.second.SummaryList) {
2248 if (!ExportSummary->isGlobalValueLive(S.get()))
2249 continue;
2250 if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject()))
2251 for (GlobalValue::GUID G : FS->type_tests())
2252 for (Metadata *MD : MetadataByGUID[G])
2253 AddTypeIdUse(MD).IsExported = true;
2254 }
2255 }
2256 }
2257
2258 if (GlobalClasses.empty())
2259 return false;
2260
2261 // Build a list of disjoint sets ordered by their maximum global index for
2262 // determinism.
2263 std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
2264 for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
2265 E = GlobalClasses.end();
2266 I != E; ++I) {
2267 if (!I->isLeader())
2268 continue;
2269 ++NumTypeIdDisjointSets;
2270
2271 unsigned MaxUniqueId = 0;
2272 for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
2273 MI != GlobalClasses.member_end(); ++MI) {
2274 if (auto *MD = MI->dyn_cast<Metadata *>())
2275 MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
2276 else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
2277 MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
2278 }
2279 Sets.emplace_back(I, MaxUniqueId);
2280 }
2282
2283 // For each disjoint set we found...
2284 for (const auto &S : Sets) {
2285 // Build the list of type identifiers in this disjoint set.
2286 std::vector<Metadata *> TypeIds;
2287 std::vector<GlobalTypeMember *> Globals;
2288 std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2289 for (GlobalClassesTy::member_iterator MI =
2290 GlobalClasses.member_begin(S.first);
2291 MI != GlobalClasses.member_end(); ++MI) {
2292 if (MI->is<Metadata *>())
2293 TypeIds.push_back(MI->get<Metadata *>());
2294 else if (MI->is<GlobalTypeMember *>())
2295 Globals.push_back(MI->get<GlobalTypeMember *>());
2296 else
2297 ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
2298 }
2299
2300 // Order type identifiers by unique ID for determinism. This ordering is
2301 // stable as there is a one-to-one mapping between metadata and unique IDs.
2302 llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) {
2303 return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2304 });
2305
2306 // Same for the branch funnels.
2307 llvm::sort(ICallBranchFunnels,
2308 [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2309 return F1->UniqueId < F2->UniqueId;
2310 });
2311
2312 // Build bitsets for this disjoint set.
2313 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2314 }
2315
2316 allocateByteArrays();
2317
2318 // Parse alias data to replace stand-in function declarations for aliases
2319 // with an alias to the intended target.
2320 if (ExportSummary) {
2321 if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {
2322 for (auto *AliasMD : AliasesMD->operands()) {
2323 assert(AliasMD->getNumOperands() >= 4);
2324 StringRef AliasName =
2325 cast<MDString>(AliasMD->getOperand(0))->getString();
2326 StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
2327
2328 if (!ExportedFunctions.count(Aliasee) ||
2329 ExportedFunctions[Aliasee].Linkage != CFL_Definition ||
2330 !M.getNamedAlias(Aliasee))
2331 continue;
2332
2333 GlobalValue::VisibilityTypes Visibility =
2334 static_cast<GlobalValue::VisibilityTypes>(
2335 cast<ConstantAsMetadata>(AliasMD->getOperand(2))
2336 ->getValue()
2337 ->getUniqueInteger()
2338 .getZExtValue());
2339 bool Weak =
2340 static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
2341 ->getValue()
2342 ->getUniqueInteger()
2343 .getZExtValue());
2344
2345 auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee));
2346 Alias->setVisibility(Visibility);
2347 if (Weak)
2349
2350 if (auto *F = M.getFunction(AliasName)) {
2351 Alias->takeName(F);
2352 F->replaceAllUsesWith(Alias);
2353 F->eraseFromParent();
2354 } else {
2355 Alias->setName(AliasName);
2356 }
2357 }
2358 }
2359 }
2360
2361 // Emit .symver directives for exported functions, if they exist.
2362 if (ExportSummary) {
2363 if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) {
2364 for (auto *Symver : SymversMD->operands()) {
2365 assert(Symver->getNumOperands() >= 2);
2367 cast<MDString>(Symver->getOperand(0))->getString();
2368 StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
2369
2370 if (!ExportedFunctions.count(SymbolName))
2371 continue;
2372
2373 M.appendModuleInlineAsm(
2374 (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2375 }
2376 }
2377 }
2378
2379 return true;
2380}
2381
2384 bool Changed;
2385 if (UseCommandLine)
2386 Changed = LowerTypeTestsModule::runForTesting(M, AM);
2387 else
2388 Changed =
2389 LowerTypeTestsModule(M, AM, ExportSummary, ImportSummary, DropTypeTests)
2390 .lower();
2391 if (!Changed)
2392 return PreservedAnalyses::all();
2393 return PreservedAnalyses::none();
2394}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
This file defines the BumpPtrAllocator interface.
assume Assume Builder
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:678
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
std::string Name
Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...
Hexagon Common GEP
IRTranslator LLVM IR MI
static const unsigned kARMJumpTableEntrySize
static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL, Value *V, uint64_t COffset)
static const unsigned kX86IBTJumpTableEntrySize
static cl::opt< std::string > ClReadSummary("lowertypetests-read-summary", cl::desc("Read summary from given YAML file before running pass"), cl::Hidden)
static const unsigned kRISCVJumpTableEntrySize
static Value * createMaskedBitTest(IRBuilder<> &B, Value *Bits, Value *BitOffset)
Build a test that bit BitOffset mod sizeof(Bits)*8 is set in Bits.
static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch)
static const unsigned kX86JumpTableEntrySize
static cl::opt< bool > AvoidReuse("lowertypetests-avoid-reuse", cl::desc("Try to avoid reuse of byte array addresses using aliases"), cl::Hidden, cl::init(true))
static void dropTypeTests(Module &M, Function &TypeTestFunc)
static cl::opt< PassSummaryAction > ClSummaryAction("lowertypetests-summary-action", cl::desc("What to do with the summary when running this pass"), cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), clEnumValN(PassSummaryAction::Import, "import", "Import typeid resolutions from summary and globals"), clEnumValN(PassSummaryAction::Export, "export", "Export typeid resolutions to summary and globals")), cl::Hidden)
static const unsigned kARMBTIJumpTableEntrySize
static cl::opt< bool > ClDropTypeTests("lowertypetests-drop-type-tests", cl::desc("Simply drop type test assume sequences"), cl::Hidden, cl::init(false))
static cl::opt< std::string > ClWriteSummary("lowertypetests-write-summary", cl::desc("Write summary to given YAML file after running pass"), cl::Hidden)
static bool isDirectCall(Use &U)
static const unsigned kARMv6MJumpTableEntrySize
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
This file contains the declarations for metadata subclasses.
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
Module.h This file contains the declarations for the Module class.
IntegerType * Int32Ty
#define P(N)
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file defines the PointerUnion class, which is a discriminated union of pointer types.
@ VI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
@ Targets
Definition: TextStubV5.cpp:90
@ Globals
Definition: TextStubV5.cpp:115
@ Weak
Definition: TextStubV5.cpp:113
This header defines support for implementing classes that have some trailing object (or arrays of obj...
This defines the Use class.
Class for arbitrary precision integers.
Definition: APInt.h:75
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:658
StringRef getValueAsString() const
Return the attribute's value as a string.
Definition: Attributes.cpp:317
bool isValid() const
Return true if the attribute is any kind of attribute.
Definition: Attributes.h:187
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:410
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1353
unsigned arg_size() const
Definition: InstrTypes.h:1351
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1586
static ConstantAsMetadata * get(Constant *C)
Definition: Metadata.h:419
static Constant * get(LLVMContext &Context, ArrayRef< ElementTy > Elts)
get() constructor - Return a constant with array type with an element count and element type matching...
Definition: Constants.h:695
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2206
static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList)
Create an "inbounds" getelementptr.
Definition: Constants.h:1258
static Constant * getPointerCast(Constant *C, Type *Ty)
Create a BitCast, AddrSpaceCast, or a PtrToInt cast constant expression.
Definition: Constants.cpp:2032
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2621
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2110
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2192
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, std::optional< unsigned > InRangeIndex=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
Definition: Constants.h:1232
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2220
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1698
static Constant * getAnon(ArrayRef< Constant * > V, bool Packed=false)
Return an anonymous struct that has the specified elements.
Definition: Constants.h:466
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
Helper for check-and-exit error handling.
Definition: Error.h:1355
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Function.cpp:366
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:552
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
Definition: Globals.cpp:520
MaybeAlign getAlign() const
Returns the alignment of the given variable or function.
Definition: GlobalObject.h:79
void setMetadata(unsigned KindID, MDNode *Node)
Set a particular kind of metadata attachment.
Definition: Metadata.cpp:1325
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
Definition: Metadata.cpp:1288
bool eraseMetadata(unsigned KindID)
Erase all metadata attachments with the given kind.
Definition: Metadata.cpp:1370
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:109
bool isDSOLocal() const
Definition: GlobalValue.h:301
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Definition: GlobalValue.h:259
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:244
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:404
LinkageTypes getLinkage() const
Definition: GlobalValue.h:541
static StringRef dropLLVMManglingEscape(StringRef Name)
If the given string begins with the GlobalValue name mangling escape character '\1',...
Definition: GlobalValue.h:562
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:532
bool isDeclarationForLinker() const
Definition: GlobalValue.h:614
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:591
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:290
VisibilityTypes
An enumeration for the kinds of visibility of global values.
Definition: GlobalValue.h:62
@ HiddenVisibility
The GV is hidden.
Definition: GlobalValue.h:64
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:250
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:47
@ PrivateLinkage
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
@ WeakAnyLinkage
Keep one copy of named function when linking (weak)
Definition: GlobalValue.h:52
@ ExternalWeakLinkage
ExternalWeak linkage description.
Definition: GlobalValue.h:57
Type * getValueType() const
Definition: GlobalValue.h:292
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition: Globals.cpp:472
void setConstant(bool Val)
void eraseFromParent()
eraseFromParent - This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:468
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2564
static InlineAsm * get(FunctionType *Ty, StringRef AsmString, StringRef Constraints, bool hasSideEffects, bool isAlignStack=false, AsmDialect asmDialect=AD_ATT, bool canThrow=false)
InlineAsm::get - Return the specified uniqued inline asm string.
Definition: InlineAsm.cpp:43
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:933
const BasicBlock * getParent() const
Definition: Instruction.h:90
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1455
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
Class to represent integer types.
Definition: DerivedTypes.h:40
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Metadata node.
Definition: Metadata.h:943
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1291
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1399
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1297
Metadata * get() const
Definition: Metadata.h:794
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false, std::optional< Align > Alignment=std::nullopt)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
Root of the metadata hierarchy.
Definition: Metadata.h:61
Class to hold module path string table and global value map, and encapsulate methods for operating on...
std::set< std::string > & cfiFunctionDecls()
TypeIdSummary & getOrInsertTypeIdSummary(StringRef TypeId)
Return an existing or new TypeIdSummary entry for TypeId.
const TypeIdSummary * getTypeIdSummary(StringRef TypeId) const
This returns either a pointer to the type id summary (if present in the summary map) or null (if not ...
std::set< std::string > & cfiFunctionDefs()
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Metadata * getModuleFlag(StringRef Key) const
Return the corresponding value if Key appears in module flags, otherwise return null.
Definition: Module.cpp:322
A tuple of MDNodes.
Definition: Metadata.h:1587
iterator_range< op_iterator > operands()
Definition: Metadata.h:1683
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:118
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:312
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
Definition: StringRef.h:687
Class to represent struct types.
Definition: DerivedTypes.h:213
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:328
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasArmWideBranch(bool Thumb) const
See the file comment for details on the usage of the TrailingObjects type.
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:44
@ UnknownArch
Definition: Triple.h:47
ObjectFormatType
Definition: Triple.h:280
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt1Ty(LLVMContext &C)
static Type * getVoidTy(LLVMContext &C)
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static IntegerType * getInt32Ty(LLVMContext &C)
static IntegerType * getInt64Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
user_iterator user_begin()
Definition: Value.h:397
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
iterator_range< user_iterator > users()
Definition: Value.h:421
use_iterator use_begin()
Definition: Value.h:360
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
Definition: Value.cpp:540
bool use_empty() const
Definition: Value.h:344
iterator_range< use_iterator > uses()
Definition: Value.h:376
bool hasName() const
Definition: Value.h:261
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
self_iterator getIterator()
Definition: ilist_node.h:82
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:454
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
constexpr char SymbolName[]
Key for Kernel::Metadata::mSymbolName.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:119
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:979
@ FS
Definition: X86.h:208
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:703
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
bool isJumpTableCanonical(Function *F)
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
Definition: FileSystem.h:770
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
@ Offset
Definition: DWP.cpp:406
void stable_sort(R &&Range)
Definition: STLExtras.h:2063
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
bool convertUsersOfConstantsToInstructions(ArrayRef< Constant * > Consts)
Replace constant expressions users of the given constants with instructions.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: bit.h:179
unsigned M1(unsigned Val)
Definition: VE.h:468
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
@ Ref
The access may reference the value stored in memory.
void appendToCompilerUsed(Module &M, ArrayRef< GlobalValue * > Values)
Adds global values to the llvm.compiler.used list.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
Definition: Error.h:1186
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
void appendToGlobalCtors(Module &M, Function *F, int Priority, Constant *Data=nullptr)
Append F to the list of global ctors of module M with the given Priority.
Definition: ModuleUtils.cpp:71
Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
Definition: Error.cpp:92
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
void appendToUsed(Module &M, ArrayRef< GlobalValue * > Values)
Adds global values to the llvm.used list.
CfiFunctionLinkage
The type of CFI jumptable needed for a function.
@ CFL_WeakDeclaration
@ CFL_Definition
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:450
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallVectorImpl< GlobalValue * > &Vec, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
Definition: Module.cpp:807
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
TypeTestResolution TTRes
Kind
Specifies which kind of type check we should emit for this byte array.
@ Unknown
Unknown (analysis not performed, don't lower)
@ Single
Single element (last example in "Short Inline Bit Vectors")
@ Inline
Inlined bit vector ("Short Inline Bit Vectors")
@ Unsat
Unsatisfiable type (i.e. no global has this type metadata)
@ AllOnes
All-ones bit vector ("Eliminating Bit Vector Checks for All-Ones Bit Vectors")
@ ByteArray
Test a byte array (first example)
unsigned SizeM1BitWidth
Range of size-1 expressed as a bit width.
enum llvm::TypeTestResolution::Kind TheKind
Function object to check whether the second component of a container supported by std::get (like std:...
Definition: STLExtras.h:1546
SmallVector< uint64_t, 16 > Offsets
bool containsGlobalOffset(uint64_t Offset) const
void print(raw_ostream &OS) const
This class is used to build a byte array containing overlapping bit sets.
uint64_t BitAllocs[BitsPerByte]
The number of bytes allocated so far for each of the bits.
std::vector< uint8_t > Bytes
The byte array built so far.
void allocate(const std::set< uint64_t > &Bits, uint64_t BitSize, uint64_t &AllocByteOffset, uint8_t &AllocMask)
Allocate BitSize bits in the byte array where Bits contains the bits to set.
This class implements a layout algorithm for globals referenced by bit sets that tries to keep member...
std::vector< std::vector< uint64_t > > Fragments
The computed layout.
void addFragment(const std::set< uint64_t > &F)
Add F to the layout while trying to keep its indices contiguous.
std::vector< uint64_t > FragmentMap
Mapping from object index to fragment index.