1 //===- LowerTypeTests.cpp - type metadata lowering pass -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass lowers type metadata and calls to the llvm.type.test intrinsic.
10 // It also ensures that globals are properly laid out for the
11 // llvm.icall.branch.funnel intrinsic.
12 // See http://llvm.org/docs/TypeMetadata.html for more information.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Transforms/IPO/LowerTypeTests.h"
17 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/EquivalenceClasses.h"
21 #include "llvm/ADT/PointerUnion.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/ADT/TinyPtrVector.h"
27 #include "llvm/ADT/Triple.h"
28 #include "llvm/Analysis/TypeMetadataUtils.h"
29 #include "llvm/Analysis/ValueTracking.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"
35 #include "llvm/IR/DerivedTypes.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/GlobalAlias.h"
38 #include "llvm/IR/GlobalObject.h"
39 #include "llvm/IR/GlobalValue.h"
40 #include "llvm/IR/GlobalVariable.h"
41 #include "llvm/IR/IRBuilder.h"
42 #include "llvm/IR/InlineAsm.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/Intrinsics.h"
46 #include "llvm/IR/LLVMContext.h"
47 #include "llvm/IR/Metadata.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/IR/ModuleSummaryIndex.h"
50 #include "llvm/IR/ModuleSummaryIndexYAML.h"
51 #include "llvm/IR/Operator.h"
52 #include "llvm/IR/PassManager.h"
53 #include "llvm/IR/Type.h"
54 #include "llvm/IR/Use.h"
55 #include "llvm/IR/User.h"
56 #include "llvm/IR/Value.h"
57 #include "llvm/InitializePasses.h"
58 #include "llvm/Pass.h"
59 #include "llvm/Support/Allocator.h"
60 #include "llvm/Support/Casting.h"
61 #include "llvm/Support/CommandLine.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/Error.h"
64 #include "llvm/Support/ErrorHandling.h"
65 #include "llvm/Support/FileSystem.h"
66 #include "llvm/Support/MathExtras.h"
67 #include "llvm/Support/MemoryBuffer.h"
68 #include "llvm/Support/TrailingObjects.h"
69 #include "llvm/Support/YAMLTraits.h"
70 #include "llvm/Support/raw_ostream.h"
71 #include "llvm/Transforms/IPO.h"
72 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
73 #include "llvm/Transforms/Utils/ModuleUtils.h"
74 #include <algorithm>
75 #include <cassert>
76 #include <cstdint>
77 #include <memory>
78 #include <set>
79 #include <string>
80 #include <system_error>
81 #include <utility>
82 #include <vector>
83
84 using namespace llvm;
85 using namespace lowertypetests;
86
87 #define DEBUG_TYPE "lowertypetests"
88
89 STATISTIC(ByteArraySizeBits, "Byte array size in bits");
90 STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
91 STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
92 STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
93 STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
94
95 static cl::opt<bool> AvoidReuse(
96 "lowertypetests-avoid-reuse",
97 cl::desc("Try to avoid reuse of byte array addresses using aliases"),
98 cl::Hidden, cl::init(true));
99
100 static cl::opt<PassSummaryAction> ClSummaryAction(
101 "lowertypetests-summary-action",
102 cl::desc("What to do with the summary when running this pass"),
103 cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
104 clEnumValN(PassSummaryAction::Import, "import",
105 "Import typeid resolutions from summary and globals"),
106 clEnumValN(PassSummaryAction::Export, "export",
107 "Export typeid resolutions to summary and globals")),
108 cl::Hidden);
109
110 static cl::opt<std::string> ClReadSummary(
111 "lowertypetests-read-summary",
112 cl::desc("Read summary from given YAML file before running pass"),
113 cl::Hidden);
114
115 static cl::opt<std::string> ClWriteSummary(
116 "lowertypetests-write-summary",
117 cl::desc("Write summary to given YAML file after running pass"),
118 cl::Hidden);
119
containsGlobalOffset(uint64_t Offset) const120 bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
121 if (Offset < ByteOffset)
122 return false;
123
124 if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
125 return false;
126
127 uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
128 if (BitOffset >= BitSize)
129 return false;
130
131 return Bits.count(BitOffset);
132 }
133
print(raw_ostream & OS) const134 void BitSetInfo::print(raw_ostream &OS) const {
135 OS << "offset " << ByteOffset << " size " << BitSize << " align "
136 << (1 << AlignLog2);
137
138 if (isAllOnes()) {
139 OS << " all-ones\n";
140 return;
141 }
142
143 OS << " { ";
144 for (uint64_t B : Bits)
145 OS << B << ' ';
146 OS << "}\n";
147 }
148
build()149 BitSetInfo BitSetBuilder::build() {
150 if (Min > Max)
151 Min = 0;
152
153 // Normalize each offset against the minimum observed offset, and compute
154 // the bitwise OR of each of the offsets. The number of trailing zeros
155 // in the mask gives us the log2 of the alignment of all offsets, which
156 // allows us to compress the bitset by only storing one bit per aligned
157 // address.
158 uint64_t Mask = 0;
159 for (uint64_t &Offset : Offsets) {
160 Offset -= Min;
161 Mask |= Offset;
162 }
163
164 BitSetInfo BSI;
165 BSI.ByteOffset = Min;
166
167 BSI.AlignLog2 = 0;
168 if (Mask != 0)
169 BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined);
170
171 // Build the compressed bitset while normalizing the offsets against the
172 // computed alignment.
173 BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
174 for (uint64_t Offset : Offsets) {
175 Offset >>= BSI.AlignLog2;
176 BSI.Bits.insert(Offset);
177 }
178
179 return BSI;
180 }
181
addFragment(const std::set<uint64_t> & F)182 void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
183 // Create a new fragment to hold the layout for F.
184 Fragments.emplace_back();
185 std::vector<uint64_t> &Fragment = Fragments.back();
186 uint64_t FragmentIndex = Fragments.size() - 1;
187
188 for (auto ObjIndex : F) {
189 uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
190 if (OldFragmentIndex == 0) {
191 // We haven't seen this object index before, so just add it to the current
192 // fragment.
193 Fragment.push_back(ObjIndex);
194 } else {
195 // This index belongs to an existing fragment. Copy the elements of the
196 // old fragment into this one and clear the old fragment. We don't update
197 // the fragment map just yet, this ensures that any further references to
198 // indices from the old fragment in this fragment do not insert any more
199 // indices.
200 std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
201 Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end());
202 OldFragment.clear();
203 }
204 }
205
206 // Update the fragment map to point our object indices to this fragment.
207 for (uint64_t ObjIndex : Fragment)
208 FragmentMap[ObjIndex] = FragmentIndex;
209 }
210
allocate(const std::set<uint64_t> & Bits,uint64_t BitSize,uint64_t & AllocByteOffset,uint8_t & AllocMask)211 void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
212 uint64_t BitSize, uint64_t &AllocByteOffset,
213 uint8_t &AllocMask) {
214 // Find the smallest current allocation.
215 unsigned Bit = 0;
216 for (unsigned I = 1; I != BitsPerByte; ++I)
217 if (BitAllocs[I] < BitAllocs[Bit])
218 Bit = I;
219
220 AllocByteOffset = BitAllocs[Bit];
221
222 // Add our size to it.
223 unsigned ReqSize = AllocByteOffset + BitSize;
224 BitAllocs[Bit] = ReqSize;
225 if (Bytes.size() < ReqSize)
226 Bytes.resize(ReqSize);
227
228 // Set our bits.
229 AllocMask = 1 << Bit;
230 for (uint64_t B : Bits)
231 Bytes[AllocByteOffset + B] |= AllocMask;
232 }
233
isJumpTableCanonical(Function * F)234 bool lowertypetests::isJumpTableCanonical(Function *F) {
235 if (F->isDeclarationForLinker())
236 return false;
237 auto *CI = mdconst::extract_or_null<ConstantInt>(
238 F->getParent()->getModuleFlag("CFI Canonical Jump Tables"));
239 if (!CI || CI->getZExtValue() != 0)
240 return true;
241 return F->hasFnAttribute("cfi-canonical-jump-table");
242 }
243
244 namespace {
245
246 struct ByteArrayInfo {
247 std::set<uint64_t> Bits;
248 uint64_t BitSize;
249 GlobalVariable *ByteArray;
250 GlobalVariable *MaskGlobal;
251 uint8_t *MaskPtr = nullptr;
252 };
253
254 /// A POD-like structure that we use to store a global reference together with
255 /// its metadata types. In this pass we frequently need to query the set of
256 /// metadata types referenced by a global, which at the IR level is an expensive
257 /// operation involving a map lookup; this data structure helps to reduce the
258 /// number of times we need to do this lookup.
259 class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
260 friend TrailingObjects;
261
262 GlobalObject *GO;
263 size_t NTypes;
264
265 // For functions: true if the jump table is canonical. This essentially means
266 // whether the canonical address (i.e. the symbol table entry) of the function
267 // is provided by the local jump table. This is normally the same as whether
268 // the function is defined locally, but if canonical jump tables are disabled
269 // by the user then the jump table never provides a canonical definition.
270 bool IsJumpTableCanonical;
271
272 // For functions: true if this function is either defined or used in a thinlto
273 // module and its jumptable entry needs to be exported to thinlto backends.
274 bool IsExported;
275
numTrailingObjects(OverloadToken<MDNode * >) const276 size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; }
277
278 public:
create(BumpPtrAllocator & Alloc,GlobalObject * GO,bool IsJumpTableCanonical,bool IsExported,ArrayRef<MDNode * > Types)279 static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
280 bool IsJumpTableCanonical, bool IsExported,
281 ArrayRef<MDNode *> Types) {
282 auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
283 totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember)));
284 GTM->GO = GO;
285 GTM->NTypes = Types.size();
286 GTM->IsJumpTableCanonical = IsJumpTableCanonical;
287 GTM->IsExported = IsExported;
288 std::uninitialized_copy(Types.begin(), Types.end(),
289 GTM->getTrailingObjects<MDNode *>());
290 return GTM;
291 }
292
getGlobal() const293 GlobalObject *getGlobal() const {
294 return GO;
295 }
296
isJumpTableCanonical() const297 bool isJumpTableCanonical() const {
298 return IsJumpTableCanonical;
299 }
300
isExported() const301 bool isExported() const {
302 return IsExported;
303 }
304
types() const305 ArrayRef<MDNode *> types() const {
306 return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
307 }
308 };
309
310 struct ICallBranchFunnel final
311 : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
create__anon93f228dc0111::ICallBranchFunnel312 static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
313 ArrayRef<GlobalTypeMember *> Targets,
314 unsigned UniqueId) {
315 auto *Call = static_cast<ICallBranchFunnel *>(
316 Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()),
317 alignof(ICallBranchFunnel)));
318 Call->CI = CI;
319 Call->UniqueId = UniqueId;
320 Call->NTargets = Targets.size();
321 std::uninitialized_copy(Targets.begin(), Targets.end(),
322 Call->getTrailingObjects<GlobalTypeMember *>());
323 return Call;
324 }
325
326 CallInst *CI;
targets__anon93f228dc0111::ICallBranchFunnel327 ArrayRef<GlobalTypeMember *> targets() const {
328 return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
329 }
330
331 unsigned UniqueId;
332
333 private:
334 size_t NTargets;
335 };
336
337 struct ScopedSaveAliaseesAndUsed {
338 Module &M;
339 SmallPtrSet<GlobalValue *, 16> Used, CompilerUsed;
340 std::vector<std::pair<GlobalIndirectSymbol *, Function *>> FunctionAliases;
341
ScopedSaveAliaseesAndUsed__anon93f228dc0111::ScopedSaveAliaseesAndUsed342 ScopedSaveAliaseesAndUsed(Module &M) : M(M) {
343 // The users of this class want to replace all function references except
344 // for aliases and llvm.used/llvm.compiler.used with references to a jump
345 // table. We avoid replacing aliases in order to avoid introducing a double
346 // indirection (or an alias pointing to a declaration in ThinLTO mode), and
347 // we avoid replacing llvm.used/llvm.compiler.used because these global
348 // variables describe properties of the global, not the jump table (besides,
349 // offseted references to the jump table in llvm.used are invalid).
350 // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly
351 // indirect) users", so what we do is save the list of globals referenced by
352 // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW
353 // replace the aliasees and then set them back to their original values at
354 // the end.
355 if (GlobalVariable *GV = collectUsedGlobalVariables(M, Used, false))
356 GV->eraseFromParent();
357 if (GlobalVariable *GV = collectUsedGlobalVariables(M, CompilerUsed, true))
358 GV->eraseFromParent();
359
360 for (auto &GIS : concat<GlobalIndirectSymbol>(M.aliases(), M.ifuncs())) {
361 // FIXME: This should look past all aliases not just interposable ones,
362 // see discussion on D65118.
363 if (auto *F =
364 dyn_cast<Function>(GIS.getIndirectSymbol()->stripPointerCasts()))
365 FunctionAliases.push_back({&GIS, F});
366 }
367 }
368
~ScopedSaveAliaseesAndUsed__anon93f228dc0111::ScopedSaveAliaseesAndUsed369 ~ScopedSaveAliaseesAndUsed() {
370 appendToUsed(M, std::vector<GlobalValue *>(Used.begin(), Used.end()));
371 appendToCompilerUsed(M, std::vector<GlobalValue *>(CompilerUsed.begin(),
372 CompilerUsed.end()));
373
374 for (auto P : FunctionAliases)
375 P.first->setIndirectSymbol(
376 ConstantExpr::getBitCast(P.second, P.first->getType()));
377 }
378 };
379
380 class LowerTypeTestsModule {
381 Module &M;
382
383 ModuleSummaryIndex *ExportSummary;
384 const ModuleSummaryIndex *ImportSummary;
385 // Set when the client has invoked this to simply drop all type test assume
386 // sequences.
387 bool DropTypeTests;
388
389 Triple::ArchType Arch;
390 Triple::OSType OS;
391 Triple::ObjectFormatType ObjectFormat;
392
393 IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
394 IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
395 PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
396 ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0);
397 IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
398 PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty);
399 IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
400 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
401
402 // Indirect function call index assignment counter for WebAssembly
403 uint64_t IndirectIndex = 1;
404
405 // Mapping from type identifiers to the call sites that test them, as well as
406 // whether the type identifier needs to be exported to ThinLTO backends as
407 // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
408 struct TypeIdUserInfo {
409 std::vector<CallInst *> CallSites;
410 bool IsExported = false;
411 };
412 DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers;
413
414 /// This structure describes how to lower type tests for a particular type
415 /// identifier. It is either built directly from the global analysis (during
416 /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
417 /// identifier summaries and external symbol references (in ThinLTO backends).
418 struct TypeIdLowering {
419 TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat;
420
421 /// All except Unsat: the start address within the combined global.
422 Constant *OffsetedGlobal;
423
424 /// ByteArray, Inline, AllOnes: log2 of the required global alignment
425 /// relative to the start address.
426 Constant *AlignLog2;
427
428 /// ByteArray, Inline, AllOnes: one less than the size of the memory region
429 /// covering members of this type identifier as a multiple of 2^AlignLog2.
430 Constant *SizeM1;
431
432 /// ByteArray: the byte array to test the address against.
433 Constant *TheByteArray;
434
435 /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
436 Constant *BitMask;
437
438 /// Inline: the bit mask to test the address against.
439 Constant *InlineBits;
440 };
441
442 std::vector<ByteArrayInfo> ByteArrayInfos;
443
444 Function *WeakInitializerFn = nullptr;
445
446 bool shouldExportConstantsAsAbsoluteSymbols();
447 uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
448 TypeIdLowering importTypeId(StringRef TypeId);
449 void importTypeTest(CallInst *CI);
450 void importFunction(Function *F, bool isJumpTableCanonical,
451 std::vector<GlobalAlias *> &AliasesToErase);
452
453 BitSetInfo
454 buildBitSet(Metadata *TypeId,
455 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
456 ByteArrayInfo *createByteArray(BitSetInfo &BSI);
457 void allocateByteArrays();
458 Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
459 Value *BitOffset);
460 void lowerTypeTestCalls(
461 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
462 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
463 Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
464 const TypeIdLowering &TIL);
465
466 void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
467 ArrayRef<GlobalTypeMember *> Globals);
468 unsigned getJumpTableEntrySize();
469 Type *getJumpTableEntryType();
470 void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
471 Triple::ArchType JumpTableArch,
472 SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
473 void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
474 void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
475 ArrayRef<GlobalTypeMember *> Functions);
476 void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
477 ArrayRef<GlobalTypeMember *> Functions);
478 void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
479 ArrayRef<GlobalTypeMember *> Functions);
480 void
481 buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
482 ArrayRef<GlobalTypeMember *> Globals,
483 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
484
485 void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT,
486 bool IsJumpTableCanonical);
487 void moveInitializerToModuleConstructor(GlobalVariable *GV);
488 void findGlobalVariableUsersOf(Constant *C,
489 SmallSetVector<GlobalVariable *, 8> &Out);
490
491 void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
492
493 /// replaceCfiUses - Go through the uses list for this definition
494 /// and make each use point to "V" instead of "this" when the use is outside
495 /// the block. 'This's use list is expected to have at least one element.
496 /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
497 /// uses.
498 void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical);
499
500 /// replaceDirectCalls - Go through the uses list for this definition and
501 /// replace each use, which is a direct function call.
502 void replaceDirectCalls(Value *Old, Value *New);
503
504 public:
505 LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary,
506 const ModuleSummaryIndex *ImportSummary,
507 bool DropTypeTests);
508
509 bool lower();
510
511 // Lower the module using the action and summary passed as command line
512 // arguments. For testing purposes only.
513 static bool runForTesting(Module &M);
514 };
515
516 struct LowerTypeTests : public ModulePass {
517 static char ID;
518
519 bool UseCommandLine = false;
520
521 ModuleSummaryIndex *ExportSummary;
522 const ModuleSummaryIndex *ImportSummary;
523 bool DropTypeTests;
524
LowerTypeTests__anon93f228dc0111::LowerTypeTests525 LowerTypeTests() : ModulePass(ID), UseCommandLine(true) {
526 initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
527 }
528
LowerTypeTests__anon93f228dc0111::LowerTypeTests529 LowerTypeTests(ModuleSummaryIndex *ExportSummary,
530 const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
531 : ModulePass(ID), ExportSummary(ExportSummary),
532 ImportSummary(ImportSummary), DropTypeTests(DropTypeTests) {
533 initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
534 }
535
runOnModule__anon93f228dc0111::LowerTypeTests536 bool runOnModule(Module &M) override {
537 if (UseCommandLine)
538 return LowerTypeTestsModule::runForTesting(M);
539 return LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
540 .lower();
541 }
542 };
543
544 } // end anonymous namespace
545
546 char LowerTypeTests::ID = 0;
547
548 INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,
549 false)
550
551 ModulePass *
createLowerTypeTestsPass(ModuleSummaryIndex * ExportSummary,const ModuleSummaryIndex * ImportSummary,bool DropTypeTests)552 llvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary,
553 const ModuleSummaryIndex *ImportSummary,
554 bool DropTypeTests) {
555 return new LowerTypeTests(ExportSummary, ImportSummary, DropTypeTests);
556 }
557
558 /// Build a bit set for TypeId using the object layouts in
559 /// GlobalLayout.
buildBitSet(Metadata * TypeId,const DenseMap<GlobalTypeMember *,uint64_t> & GlobalLayout)560 BitSetInfo LowerTypeTestsModule::buildBitSet(
561 Metadata *TypeId,
562 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
563 BitSetBuilder BSB;
564
565 // Compute the byte offset of each address associated with this type
566 // identifier.
567 for (auto &GlobalAndOffset : GlobalLayout) {
568 for (MDNode *Type : GlobalAndOffset.first->types()) {
569 if (Type->getOperand(1) != TypeId)
570 continue;
571 uint64_t Offset =
572 cast<ConstantInt>(
573 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
574 ->getZExtValue();
575 BSB.addOffset(GlobalAndOffset.second + Offset);
576 }
577 }
578
579 return BSB.build();
580 }
581
582 /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
583 /// Bits. This pattern matches to the bt instruction on x86.
createMaskedBitTest(IRBuilder<> & B,Value * Bits,Value * BitOffset)584 static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits,
585 Value *BitOffset) {
586 auto BitsType = cast<IntegerType>(Bits->getType());
587 unsigned BitWidth = BitsType->getBitWidth();
588
589 BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
590 Value *BitIndex =
591 B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
592 Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
593 Value *MaskedBits = B.CreateAnd(Bits, BitMask);
594 return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
595 }
596
createByteArray(BitSetInfo & BSI)597 ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
598 // Create globals to stand in for byte arrays and masks. These never actually
599 // get initialized, we RAUW and erase them later in allocateByteArrays() once
600 // we know the offset and mask to use.
601 auto ByteArrayGlobal = new GlobalVariable(
602 M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
603 auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
604 GlobalValue::PrivateLinkage, nullptr);
605
606 ByteArrayInfos.emplace_back();
607 ByteArrayInfo *BAI = &ByteArrayInfos.back();
608
609 BAI->Bits = BSI.Bits;
610 BAI->BitSize = BSI.BitSize;
611 BAI->ByteArray = ByteArrayGlobal;
612 BAI->MaskGlobal = MaskGlobal;
613 return BAI;
614 }
615
allocateByteArrays()616 void LowerTypeTestsModule::allocateByteArrays() {
617 llvm::stable_sort(ByteArrayInfos,
618 [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
619 return BAI1.BitSize > BAI2.BitSize;
620 });
621
622 std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
623
624 ByteArrayBuilder BAB;
625 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
626 ByteArrayInfo *BAI = &ByteArrayInfos[I];
627
628 uint8_t Mask;
629 BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
630
631 BAI->MaskGlobal->replaceAllUsesWith(
632 ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
633 BAI->MaskGlobal->eraseFromParent();
634 if (BAI->MaskPtr)
635 *BAI->MaskPtr = Mask;
636 }
637
638 Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
639 auto ByteArray =
640 new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
641 GlobalValue::PrivateLinkage, ByteArrayConst);
642
643 for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
644 ByteArrayInfo *BAI = &ByteArrayInfos[I];
645
646 Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
647 ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
648 Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(
649 ByteArrayConst->getType(), ByteArray, Idxs);
650
651 // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
652 // that the pc-relative displacement is folded into the lea instead of the
653 // test instruction getting another displacement.
654 GlobalAlias *Alias = GlobalAlias::create(
655 Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
656 BAI->ByteArray->replaceAllUsesWith(Alias);
657 BAI->ByteArray->eraseFromParent();
658 }
659
660 ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
661 BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
662 BAB.BitAllocs[6] + BAB.BitAllocs[7];
663 ByteArraySizeBytes = BAB.Bytes.size();
664 }
665
666 /// Build a test that bit BitOffset is set in the type identifier that was
667 /// lowered to TIL, which must be either an Inline or a ByteArray.
createBitSetTest(IRBuilder<> & B,const TypeIdLowering & TIL,Value * BitOffset)668 Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
669 const TypeIdLowering &TIL,
670 Value *BitOffset) {
671 if (TIL.TheKind == TypeTestResolution::Inline) {
672 // If the bit set is sufficiently small, we can avoid a load by bit testing
673 // a constant.
674 return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
675 } else {
676 Constant *ByteArray = TIL.TheByteArray;
677 if (AvoidReuse && !ImportSummary) {
678 // Each use of the byte array uses a different alias. This makes the
679 // backend less likely to reuse previously computed byte array addresses,
680 // improving the security of the CFI mechanism based on this pass.
681 // This won't work when importing because TheByteArray is external.
682 ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage,
683 "bits_use", ByteArray, &M);
684 }
685
686 Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
687 Value *Byte = B.CreateLoad(Int8Ty, ByteAddr);
688
689 Value *ByteAndMask =
690 B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
691 return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
692 }
693 }
694
isKnownTypeIdMember(Metadata * TypeId,const DataLayout & DL,Value * V,uint64_t COffset)695 static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
696 Value *V, uint64_t COffset) {
697 if (auto GV = dyn_cast<GlobalObject>(V)) {
698 SmallVector<MDNode *, 2> Types;
699 GV->getMetadata(LLVMContext::MD_type, Types);
700 for (MDNode *Type : Types) {
701 if (Type->getOperand(1) != TypeId)
702 continue;
703 uint64_t Offset =
704 cast<ConstantInt>(
705 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
706 ->getZExtValue();
707 if (COffset == Offset)
708 return true;
709 }
710 return false;
711 }
712
713 if (auto GEP = dyn_cast<GEPOperator>(V)) {
714 APInt APOffset(DL.getPointerSizeInBits(0), 0);
715 bool Result = GEP->accumulateConstantOffset(DL, APOffset);
716 if (!Result)
717 return false;
718 COffset += APOffset.getZExtValue();
719 return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
720 }
721
722 if (auto Op = dyn_cast<Operator>(V)) {
723 if (Op->getOpcode() == Instruction::BitCast)
724 return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
725
726 if (Op->getOpcode() == Instruction::Select)
727 return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
728 isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
729 }
730
731 return false;
732 }
733
734 /// Lower a llvm.type.test call to its implementation. Returns the value to
735 /// replace the call with.
lowerTypeTestCall(Metadata * TypeId,CallInst * CI,const TypeIdLowering & TIL)736 Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
737 const TypeIdLowering &TIL) {
738 // Delay lowering if the resolution is currently unknown.
739 if (TIL.TheKind == TypeTestResolution::Unknown)
740 return nullptr;
741 if (TIL.TheKind == TypeTestResolution::Unsat)
742 return ConstantInt::getFalse(M.getContext());
743
744 Value *Ptr = CI->getArgOperand(0);
745 const DataLayout &DL = M.getDataLayout();
746 if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
747 return ConstantInt::getTrue(M.getContext());
748
749 BasicBlock *InitialBB = CI->getParent();
750
751 IRBuilder<> B(CI);
752
753 Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
754
755 Constant *OffsetedGlobalAsInt =
756 ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
757 if (TIL.TheKind == TypeTestResolution::Single)
758 return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
759
760 Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
761
762 // We need to check that the offset both falls within our range and is
763 // suitably aligned. We can check both properties at the same time by
764 // performing a right rotate by log2(alignment) followed by an integer
765 // comparison against the bitset size. The rotate will move the lower
766 // order bits that need to be zero into the higher order bits of the
767 // result, causing the comparison to fail if they are nonzero. The rotate
768 // also conveniently gives us a bit offset to use during the load from
769 // the bitset.
770 Value *OffsetSHR =
771 B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
772 Value *OffsetSHL = B.CreateShl(
773 PtrOffset, ConstantExpr::getZExt(
774 ConstantExpr::getSub(
775 ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
776 TIL.AlignLog2),
777 IntPtrTy));
778 Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
779
780 Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1);
781
782 // If the bit set is all ones, testing against it is unnecessary.
783 if (TIL.TheKind == TypeTestResolution::AllOnes)
784 return OffsetInRange;
785
786 // See if the intrinsic is used in the following common pattern:
787 // br(llvm.type.test(...), thenbb, elsebb)
788 // where nothing happens between the type test and the br.
789 // If so, create slightly simpler IR.
790 if (CI->hasOneUse())
791 if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin()))
792 if (CI->getNextNode() == Br) {
793 BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator());
794 BasicBlock *Else = Br->getSuccessor(1);
795 BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange);
796 NewBr->setMetadata(LLVMContext::MD_prof,
797 Br->getMetadata(LLVMContext::MD_prof));
798 ReplaceInstWithInst(InitialBB->getTerminator(), NewBr);
799
800 // Update phis in Else resulting from InitialBB being split
801 for (auto &Phi : Else->phis())
802 Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB);
803
804 IRBuilder<> ThenB(CI);
805 return createBitSetTest(ThenB, TIL, BitOffset);
806 }
807
808 IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false));
809
810 // Now that we know that the offset is in range and aligned, load the
811 // appropriate bit from the bitset.
812 Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
813
814 // The value we want is 0 if we came directly from the initial block
815 // (having failed the range or alignment checks), or the loaded bit if
816 // we came from the block in which we loaded it.
817 B.SetInsertPoint(CI);
818 PHINode *P = B.CreatePHI(Int1Ty, 2);
819 P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
820 P->addIncoming(Bit, ThenB.GetInsertBlock());
821 return P;
822 }
823
824 /// Given a disjoint set of type identifiers and globals, lay out the globals,
825 /// build the bit sets and lower the llvm.type.test calls.
buildBitSetsFromGlobalVariables(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Globals)826 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
827 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
828 // Build a new global with the combined contents of the referenced globals.
829 // This global is a struct whose even-indexed elements contain the original
830 // contents of the referenced globals and whose odd-indexed elements contain
831 // any padding required to align the next element to the next power of 2 plus
832 // any additional padding required to meet its alignment requirements.
833 std::vector<Constant *> GlobalInits;
834 const DataLayout &DL = M.getDataLayout();
835 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
836 Align MaxAlign;
837 uint64_t CurOffset = 0;
838 uint64_t DesiredPadding = 0;
839 for (GlobalTypeMember *G : Globals) {
840 auto *GV = cast<GlobalVariable>(G->getGlobal());
841 Align Alignment =
842 DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType());
843 MaxAlign = std::max(MaxAlign, Alignment);
844 uint64_t GVOffset = alignTo(CurOffset + DesiredPadding, Alignment);
845 GlobalLayout[G] = GVOffset;
846 if (GVOffset != 0) {
847 uint64_t Padding = GVOffset - CurOffset;
848 GlobalInits.push_back(
849 ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding)));
850 }
851
852 GlobalInits.push_back(GV->getInitializer());
853 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
854 CurOffset = GVOffset + InitSize;
855
856 // Compute the amount of padding that we'd like for the next element.
857 DesiredPadding = NextPowerOf2(InitSize - 1) - InitSize;
858
859 // Experiments of different caps with Chromium on both x64 and ARM64
860 // have shown that the 32-byte cap generates the smallest binary on
861 // both platforms while different caps yield similar performance.
862 // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
863 if (DesiredPadding > 32)
864 DesiredPadding = alignTo(InitSize, 32) - InitSize;
865 }
866
867 Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
868 auto *CombinedGlobal =
869 new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
870 GlobalValue::PrivateLinkage, NewInit);
871 CombinedGlobal->setAlignment(MaxAlign);
872
873 StructType *NewTy = cast<StructType>(NewInit->getType());
874 lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
875
876 // Build aliases pointing to offsets into the combined global for each
877 // global from which we built the combined global, and replace references
878 // to the original globals with references to the aliases.
879 for (unsigned I = 0; I != Globals.size(); ++I) {
880 GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
881
882 // Multiply by 2 to account for padding elements.
883 Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
884 ConstantInt::get(Int32Ty, I * 2)};
885 Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
886 NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
887 assert(GV->getType()->getAddressSpace() == 0);
888 GlobalAlias *GAlias =
889 GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(),
890 "", CombinedGlobalElemPtr, &M);
891 GAlias->setVisibility(GV->getVisibility());
892 GAlias->takeName(GV);
893 GV->replaceAllUsesWith(GAlias);
894 GV->eraseFromParent();
895 }
896 }
897
shouldExportConstantsAsAbsoluteSymbols()898 bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
899 return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
900 ObjectFormat == Triple::ELF;
901 }
902
903 /// Export the given type identifier so that ThinLTO backends may import it.
904 /// Type identifiers are exported by adding coarse-grained information about how
905 /// to test the type identifier to the summary, and creating symbols in the
906 /// object file (aliases and absolute symbols) containing fine-grained
907 /// information about the type identifier.
908 ///
909 /// Returns a pointer to the location in which to store the bitmask, if
910 /// applicable.
exportTypeId(StringRef TypeId,const TypeIdLowering & TIL)911 uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
912 const TypeIdLowering &TIL) {
913 TypeTestResolution &TTRes =
914 ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
915 TTRes.TheKind = TIL.TheKind;
916
917 auto ExportGlobal = [&](StringRef Name, Constant *C) {
918 GlobalAlias *GA =
919 GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
920 "__typeid_" + TypeId + "_" + Name, C, &M);
921 GA->setVisibility(GlobalValue::HiddenVisibility);
922 };
923
924 auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
925 if (shouldExportConstantsAsAbsoluteSymbols())
926 ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy));
927 else
928 Storage = cast<ConstantInt>(C)->getZExtValue();
929 };
930
931 if (TIL.TheKind != TypeTestResolution::Unsat)
932 ExportGlobal("global_addr", TIL.OffsetedGlobal);
933
934 if (TIL.TheKind == TypeTestResolution::ByteArray ||
935 TIL.TheKind == TypeTestResolution::Inline ||
936 TIL.TheKind == TypeTestResolution::AllOnes) {
937 ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
938 ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
939
940 uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
941 if (TIL.TheKind == TypeTestResolution::Inline)
942 TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
943 else
944 TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
945 }
946
947 if (TIL.TheKind == TypeTestResolution::ByteArray) {
948 ExportGlobal("byte_array", TIL.TheByteArray);
949 if (shouldExportConstantsAsAbsoluteSymbols())
950 ExportGlobal("bit_mask", TIL.BitMask);
951 else
952 return &TTRes.BitMask;
953 }
954
955 if (TIL.TheKind == TypeTestResolution::Inline)
956 ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
957
958 return nullptr;
959 }
960
961 LowerTypeTestsModule::TypeIdLowering
importTypeId(StringRef TypeId)962 LowerTypeTestsModule::importTypeId(StringRef TypeId) {
963 const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
964 if (!TidSummary)
965 return {}; // Unsat: no globals match this type id.
966 const TypeTestResolution &TTRes = TidSummary->TTRes;
967
968 TypeIdLowering TIL;
969 TIL.TheKind = TTRes.TheKind;
970
971 auto ImportGlobal = [&](StringRef Name) {
972 // Give the global a type of length 0 so that it is not assumed not to alias
973 // with any other global.
974 Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(),
975 Int8Arr0Ty);
976 if (auto *GV = dyn_cast<GlobalVariable>(C))
977 GV->setVisibility(GlobalValue::HiddenVisibility);
978 C = ConstantExpr::getBitCast(C, Int8PtrTy);
979 return C;
980 };
981
982 auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
983 Type *Ty) {
984 if (!shouldExportConstantsAsAbsoluteSymbols()) {
985 Constant *C =
986 ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const);
987 if (!isa<IntegerType>(Ty))
988 C = ConstantExpr::getIntToPtr(C, Ty);
989 return C;
990 }
991
992 Constant *C = ImportGlobal(Name);
993 auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
994 if (isa<IntegerType>(Ty))
995 C = ConstantExpr::getPtrToInt(C, Ty);
996 if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
997 return C;
998
999 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1000 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
1001 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
1002 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1003 MDNode::get(M.getContext(), {MinC, MaxC}));
1004 };
1005 if (AbsWidth == IntPtrTy->getBitWidth())
1006 SetAbsRange(~0ull, ~0ull); // Full set.
1007 else
1008 SetAbsRange(0, 1ull << AbsWidth);
1009 return C;
1010 };
1011
1012 if (TIL.TheKind != TypeTestResolution::Unsat)
1013 TIL.OffsetedGlobal = ImportGlobal("global_addr");
1014
1015 if (TIL.TheKind == TypeTestResolution::ByteArray ||
1016 TIL.TheKind == TypeTestResolution::Inline ||
1017 TIL.TheKind == TypeTestResolution::AllOnes) {
1018 TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty);
1019 TIL.SizeM1 =
1020 ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
1021 }
1022
1023 if (TIL.TheKind == TypeTestResolution::ByteArray) {
1024 TIL.TheByteArray = ImportGlobal("byte_array");
1025 TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy);
1026 }
1027
1028 if (TIL.TheKind == TypeTestResolution::Inline)
1029 TIL.InlineBits = ImportConstant(
1030 "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
1031 TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
1032
1033 return TIL;
1034 }
1035
importTypeTest(CallInst * CI)1036 void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
1037 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
1038 if (!TypeIdMDVal)
1039 report_fatal_error("Second argument of llvm.type.test must be metadata");
1040
1041 auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
1042 // If this is a local unpromoted type, which doesn't have a metadata string,
1043 // treat as Unknown and delay lowering, so that we can still utilize it for
1044 // later optimizations.
1045 if (!TypeIdStr)
1046 return;
1047
1048 TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
1049 Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
1050 if (Lowered) {
1051 CI->replaceAllUsesWith(Lowered);
1052 CI->eraseFromParent();
1053 }
1054 }
1055
1056 // ThinLTO backend: the function F has a jump table entry; update this module
1057 // accordingly. isJumpTableCanonical describes the type of the jump table entry.
importFunction(Function * F,bool isJumpTableCanonical,std::vector<GlobalAlias * > & AliasesToErase)1058 void LowerTypeTestsModule::importFunction(
1059 Function *F, bool isJumpTableCanonical,
1060 std::vector<GlobalAlias *> &AliasesToErase) {
1061 assert(F->getType()->getAddressSpace() == 0);
1062
1063 GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1064 std::string Name = std::string(F->getName());
1065
1066 if (F->isDeclarationForLinker() && isJumpTableCanonical) {
1067 // Non-dso_local functions may be overriden at run time,
1068 // don't short curcuit them
1069 if (F->isDSOLocal()) {
1070 Function *RealF = Function::Create(F->getFunctionType(),
1071 GlobalValue::ExternalLinkage,
1072 F->getAddressSpace(),
1073 Name + ".cfi", &M);
1074 RealF->setVisibility(GlobalVariable::HiddenVisibility);
1075 replaceDirectCalls(F, RealF);
1076 }
1077 return;
1078 }
1079
1080 Function *FDecl;
1081 if (!isJumpTableCanonical) {
1082 // Either a declaration of an external function or a reference to a locally
1083 // defined jump table.
1084 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1085 F->getAddressSpace(), Name + ".cfi_jt", &M);
1086 FDecl->setVisibility(GlobalValue::HiddenVisibility);
1087 } else {
1088 F->setName(Name + ".cfi");
1089 F->setLinkage(GlobalValue::ExternalLinkage);
1090 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
1091 F->getAddressSpace(), Name, &M);
1092 FDecl->setVisibility(Visibility);
1093 Visibility = GlobalValue::HiddenVisibility;
1094
1095 // Delete aliases pointing to this function, they'll be re-created in the
1096 // merged output. Don't do it yet though because ScopedSaveAliaseesAndUsed
1097 // will want to reset the aliasees first.
1098 for (auto &U : F->uses()) {
1099 if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
1100 Function *AliasDecl = Function::Create(
1101 F->getFunctionType(), GlobalValue::ExternalLinkage,
1102 F->getAddressSpace(), "", &M);
1103 AliasDecl->takeName(A);
1104 A->replaceAllUsesWith(AliasDecl);
1105 AliasesToErase.push_back(A);
1106 }
1107 }
1108 }
1109
1110 if (F->hasExternalWeakLinkage())
1111 replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isJumpTableCanonical);
1112 else
1113 replaceCfiUses(F, FDecl, isJumpTableCanonical);
1114
1115 // Set visibility late because it's used in replaceCfiUses() to determine
1116 // whether uses need to to be replaced.
1117 F->setVisibility(Visibility);
1118 }
1119
lowerTypeTestCalls(ArrayRef<Metadata * > TypeIds,Constant * CombinedGlobalAddr,const DenseMap<GlobalTypeMember *,uint64_t> & GlobalLayout)1120 void LowerTypeTestsModule::lowerTypeTestCalls(
1121 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
1122 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
1123 CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
1124
1125 // For each type identifier in this disjoint set...
1126 for (Metadata *TypeId : TypeIds) {
1127 // Build the bitset.
1128 BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
1129 LLVM_DEBUG({
1130 if (auto MDS = dyn_cast<MDString>(TypeId))
1131 dbgs() << MDS->getString() << ": ";
1132 else
1133 dbgs() << "<unnamed>: ";
1134 BSI.print(dbgs());
1135 });
1136
1137 ByteArrayInfo *BAI = nullptr;
1138 TypeIdLowering TIL;
1139 TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
1140 Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
1141 TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
1142 TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1);
1143 if (BSI.isAllOnes()) {
1144 TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
1145 : TypeTestResolution::AllOnes;
1146 } else if (BSI.BitSize <= 64) {
1147 TIL.TheKind = TypeTestResolution::Inline;
1148 uint64_t InlineBits = 0;
1149 for (auto Bit : BSI.Bits)
1150 InlineBits |= uint64_t(1) << Bit;
1151 if (InlineBits == 0)
1152 TIL.TheKind = TypeTestResolution::Unsat;
1153 else
1154 TIL.InlineBits = ConstantInt::get(
1155 (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
1156 } else {
1157 TIL.TheKind = TypeTestResolution::ByteArray;
1158 ++NumByteArraysCreated;
1159 BAI = createByteArray(BSI);
1160 TIL.TheByteArray = BAI->ByteArray;
1161 TIL.BitMask = BAI->MaskGlobal;
1162 }
1163
1164 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1165
1166 if (TIUI.IsExported) {
1167 uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
1168 if (BAI)
1169 BAI->MaskPtr = MaskPtr;
1170 }
1171
1172 // Lower each call to llvm.type.test for this type identifier.
1173 for (CallInst *CI : TIUI.CallSites) {
1174 ++NumTypeTestCallsLowered;
1175 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1176 if (Lowered) {
1177 CI->replaceAllUsesWith(Lowered);
1178 CI->eraseFromParent();
1179 }
1180 }
1181 }
1182 }
1183
verifyTypeMDNode(GlobalObject * GO,MDNode * Type)1184 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
1185 if (Type->getNumOperands() != 2)
1186 report_fatal_error("All operands of type metadata must have 2 elements");
1187
1188 if (GO->isThreadLocal())
1189 report_fatal_error("Bit set element may not be thread-local");
1190 if (isa<GlobalVariable>(GO) && GO->hasSection())
1191 report_fatal_error(
1192 "A member of a type identifier may not have an explicit section");
1193
1194 // FIXME: We previously checked that global var member of a type identifier
1195 // must be a definition, but the IR linker may leave type metadata on
1196 // declarations. We should restore this check after fixing PR31759.
1197
1198 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
1199 if (!OffsetConstMD)
1200 report_fatal_error("Type offset must be a constant");
1201 auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
1202 if (!OffsetInt)
1203 report_fatal_error("Type offset must be an integer constant");
1204 }
1205
1206 static const unsigned kX86JumpTableEntrySize = 8;
1207 static const unsigned kARMJumpTableEntrySize = 4;
1208 static const unsigned kARMBTIJumpTableEntrySize = 8;
1209
getJumpTableEntrySize()1210 unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
1211 switch (Arch) {
1212 case Triple::x86:
1213 case Triple::x86_64:
1214 return kX86JumpTableEntrySize;
1215 case Triple::arm:
1216 case Triple::thumb:
1217 return kARMJumpTableEntrySize;
1218 case Triple::aarch64:
1219 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1220 M.getModuleFlag("branch-target-enforcement")))
1221 if (BTE->getZExtValue())
1222 return kARMBTIJumpTableEntrySize;
1223 return kARMJumpTableEntrySize;
1224 default:
1225 report_fatal_error("Unsupported architecture for jump tables");
1226 }
1227 }
1228
1229 // Create a jump table entry for the target. This consists of an instruction
1230 // sequence containing a relative branch to Dest. Appends inline asm text,
1231 // constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
createJumpTableEntry(raw_ostream & AsmOS,raw_ostream & ConstraintOS,Triple::ArchType JumpTableArch,SmallVectorImpl<Value * > & AsmArgs,Function * Dest)1232 void LowerTypeTestsModule::createJumpTableEntry(
1233 raw_ostream &AsmOS, raw_ostream &ConstraintOS,
1234 Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs,
1235 Function *Dest) {
1236 unsigned ArgIndex = AsmArgs.size();
1237
1238 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
1239 AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
1240 AsmOS << "int3\nint3\nint3\n";
1241 } else if (JumpTableArch == Triple::arm) {
1242 AsmOS << "b $" << ArgIndex << "\n";
1243 } else if (JumpTableArch == Triple::aarch64) {
1244 if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1245 Dest->getParent()->getModuleFlag("branch-target-enforcement")))
1246 if (BTE->getZExtValue())
1247 AsmOS << "bti c\n";
1248 AsmOS << "b $" << ArgIndex << "\n";
1249 } else if (JumpTableArch == Triple::thumb) {
1250 AsmOS << "b.w $" << ArgIndex << "\n";
1251 } else {
1252 report_fatal_error("Unsupported architecture for jump tables");
1253 }
1254
1255 ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
1256 AsmArgs.push_back(Dest);
1257 }
1258
getJumpTableEntryType()1259 Type *LowerTypeTestsModule::getJumpTableEntryType() {
1260 return ArrayType::get(Int8Ty, getJumpTableEntrySize());
1261 }
1262
1263 /// Given a disjoint set of type identifiers and functions, build the bit sets
1264 /// and lower the llvm.type.test calls, architecture dependently.
buildBitSetsFromFunctions(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)1265 void LowerTypeTestsModule::buildBitSetsFromFunctions(
1266 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1267 if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
1268 Arch == Triple::thumb || Arch == Triple::aarch64)
1269 buildBitSetsFromFunctionsNative(TypeIds, Functions);
1270 else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
1271 buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1272 else
1273 report_fatal_error("Unsupported architecture for jump tables");
1274 }
1275
moveInitializerToModuleConstructor(GlobalVariable * GV)1276 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1277 GlobalVariable *GV) {
1278 if (WeakInitializerFn == nullptr) {
1279 WeakInitializerFn = Function::Create(
1280 FunctionType::get(Type::getVoidTy(M.getContext()),
1281 /* IsVarArg */ false),
1282 GlobalValue::InternalLinkage,
1283 M.getDataLayout().getProgramAddressSpace(),
1284 "__cfi_global_var_init", &M);
1285 BasicBlock *BB =
1286 BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
1287 ReturnInst::Create(M.getContext(), BB);
1288 WeakInitializerFn->setSection(
1289 ObjectFormat == Triple::MachO
1290 ? "__TEXT,__StaticInit,regular,pure_instructions"
1291 : ".text.startup");
1292 // This code is equivalent to relocation application, and should run at the
1293 // earliest possible time (i.e. with the highest priority).
1294 appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
1295 }
1296
1297 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1298 GV->setConstant(false);
1299 IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlign());
1300 GV->setInitializer(Constant::getNullValue(GV->getValueType()));
1301 }
1302
findGlobalVariableUsersOf(Constant * C,SmallSetVector<GlobalVariable *,8> & Out)1303 void LowerTypeTestsModule::findGlobalVariableUsersOf(
1304 Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
1305 for (auto *U : C->users()){
1306 if (auto *GV = dyn_cast<GlobalVariable>(U))
1307 Out.insert(GV);
1308 else if (auto *C2 = dyn_cast<Constant>(U))
1309 findGlobalVariableUsersOf(C2, Out);
1310 }
1311 }
1312
1313 // Replace all uses of F with (F ? JT : 0).
replaceWeakDeclarationWithJumpTablePtr(Function * F,Constant * JT,bool IsJumpTableCanonical)1314 void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1315 Function *F, Constant *JT, bool IsJumpTableCanonical) {
1316 // The target expression can not appear in a constant initializer on most
1317 // (all?) targets. Switch to a runtime initializer.
1318 SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
1319 findGlobalVariableUsersOf(F, GlobalVarUsers);
1320 for (auto GV : GlobalVarUsers)
1321 moveInitializerToModuleConstructor(GV);
1322
1323 // Can not RAUW F with an expression that uses F. Replace with a temporary
1324 // placeholder first.
1325 Function *PlaceholderFn =
1326 Function::Create(cast<FunctionType>(F->getValueType()),
1327 GlobalValue::ExternalWeakLinkage,
1328 F->getAddressSpace(), "", &M);
1329 replaceCfiUses(F, PlaceholderFn, IsJumpTableCanonical);
1330
1331 Constant *Target = ConstantExpr::getSelect(
1332 ConstantExpr::getICmp(CmpInst::ICMP_NE, F,
1333 Constant::getNullValue(F->getType())),
1334 JT, Constant::getNullValue(F->getType()));
1335 PlaceholderFn->replaceAllUsesWith(Target);
1336 PlaceholderFn->eraseFromParent();
1337 }
1338
isThumbFunction(Function * F,Triple::ArchType ModuleArch)1339 static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
1340 Attribute TFAttr = F->getFnAttribute("target-features");
1341 if (TFAttr.isValid()) {
1342 SmallVector<StringRef, 6> Features;
1343 TFAttr.getValueAsString().split(Features, ',');
1344 for (StringRef Feature : Features) {
1345 if (Feature == "-thumb-mode")
1346 return false;
1347 else if (Feature == "+thumb-mode")
1348 return true;
1349 }
1350 }
1351
1352 return ModuleArch == Triple::thumb;
1353 }
1354
1355 // Each jump table must be either ARM or Thumb as a whole for the bit-test math
1356 // to work. Pick one that matches the majority of members to minimize interop
1357 // veneers inserted by the linker.
1358 static Triple::ArchType
selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember * > Functions,Triple::ArchType ModuleArch)1359 selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions,
1360 Triple::ArchType ModuleArch) {
1361 if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb)
1362 return ModuleArch;
1363
1364 unsigned ArmCount = 0, ThumbCount = 0;
1365 for (const auto GTM : Functions) {
1366 if (!GTM->isJumpTableCanonical()) {
1367 // PLT stubs are always ARM.
1368 // FIXME: This is the wrong heuristic for non-canonical jump tables.
1369 ++ArmCount;
1370 continue;
1371 }
1372
1373 Function *F = cast<Function>(GTM->getGlobal());
1374 ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount);
1375 }
1376
1377 return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
1378 }
1379
createJumpTable(Function * F,ArrayRef<GlobalTypeMember * > Functions)1380 void LowerTypeTestsModule::createJumpTable(
1381 Function *F, ArrayRef<GlobalTypeMember *> Functions) {
1382 std::string AsmStr, ConstraintStr;
1383 raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
1384 SmallVector<Value *, 16> AsmArgs;
1385 AsmArgs.reserve(Functions.size() * 2);
1386
1387 Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch);
1388
1389 for (unsigned I = 0; I != Functions.size(); ++I)
1390 createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
1391 cast<Function>(Functions[I]->getGlobal()));
1392
1393 // Align the whole table by entry size.
1394 F->setAlignment(Align(getJumpTableEntrySize()));
1395 // Skip prologue.
1396 // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
1397 // Luckily, this function does not get any prologue even without the
1398 // attribute.
1399 if (OS != Triple::Win32)
1400 F->addFnAttr(Attribute::Naked);
1401 if (JumpTableArch == Triple::arm)
1402 F->addFnAttr("target-features", "-thumb-mode");
1403 if (JumpTableArch == Triple::thumb) {
1404 F->addFnAttr("target-features", "+thumb-mode");
1405 // Thumb jump table assembly needs Thumb2. The following attribute is added
1406 // by Clang for -march=armv7.
1407 F->addFnAttr("target-cpu", "cortex-a8");
1408 }
1409 if (JumpTableArch == Triple::aarch64) {
1410 F->addFnAttr("branch-target-enforcement", "false");
1411 F->addFnAttr("sign-return-address", "none");
1412 }
1413 // Make sure we don't emit .eh_frame for this function.
1414 F->addFnAttr(Attribute::NoUnwind);
1415
1416 BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
1417 IRBuilder<> IRB(BB);
1418
1419 SmallVector<Type *, 16> ArgTypes;
1420 ArgTypes.reserve(AsmArgs.size());
1421 for (const auto &Arg : AsmArgs)
1422 ArgTypes.push_back(Arg->getType());
1423 InlineAsm *JumpTableAsm =
1424 InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
1425 AsmOS.str(), ConstraintOS.str(),
1426 /*hasSideEffects=*/true);
1427
1428 IRB.CreateCall(JumpTableAsm, AsmArgs);
1429 IRB.CreateUnreachable();
1430 }
1431
1432 /// Given a disjoint set of type identifiers and functions, build a jump table
1433 /// for the functions, build the bit sets and lower the llvm.type.test calls.
buildBitSetsFromFunctionsNative(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)1434 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1435 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1436 // Unlike the global bitset builder, the function bitset builder cannot
1437 // re-arrange functions in a particular order and base its calculations on the
1438 // layout of the functions' entry points, as we have no idea how large a
1439 // particular function will end up being (the size could even depend on what
1440 // this pass does!) Instead, we build a jump table, which is a block of code
1441 // consisting of one branch instruction for each of the functions in the bit
1442 // set that branches to the target function, and redirect any taken function
1443 // addresses to the corresponding jump table entry. In the object file's
1444 // symbol table, the symbols for the target functions also refer to the jump
1445 // table entries, so that addresses taken outside the module will pass any
1446 // verification done inside the module.
1447 //
1448 // In more concrete terms, suppose we have three functions f, g, h which are
1449 // of the same type, and a function foo that returns their addresses:
1450 //
1451 // f:
1452 // mov 0, %eax
1453 // ret
1454 //
1455 // g:
1456 // mov 1, %eax
1457 // ret
1458 //
1459 // h:
1460 // mov 2, %eax
1461 // ret
1462 //
1463 // foo:
1464 // mov f, %eax
1465 // mov g, %edx
1466 // mov h, %ecx
1467 // ret
1468 //
1469 // We output the jump table as module-level inline asm string. The end result
1470 // will (conceptually) look like this:
1471 //
1472 // f = .cfi.jumptable
1473 // g = .cfi.jumptable + 4
1474 // h = .cfi.jumptable + 8
1475 // .cfi.jumptable:
1476 // jmp f.cfi ; 5 bytes
1477 // int3 ; 1 byte
1478 // int3 ; 1 byte
1479 // int3 ; 1 byte
1480 // jmp g.cfi ; 5 bytes
1481 // int3 ; 1 byte
1482 // int3 ; 1 byte
1483 // int3 ; 1 byte
1484 // jmp h.cfi ; 5 bytes
1485 // int3 ; 1 byte
1486 // int3 ; 1 byte
1487 // int3 ; 1 byte
1488 //
1489 // f.cfi:
1490 // mov 0, %eax
1491 // ret
1492 //
1493 // g.cfi:
1494 // mov 1, %eax
1495 // ret
1496 //
1497 // h.cfi:
1498 // mov 2, %eax
1499 // ret
1500 //
1501 // foo:
1502 // mov f, %eax
1503 // mov g, %edx
1504 // mov h, %ecx
1505 // ret
1506 //
1507 // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
1508 // normal case the check can be carried out using the same kind of simple
1509 // arithmetic that we normally use for globals.
1510
1511 // FIXME: find a better way to represent the jumptable in the IR.
1512 assert(!Functions.empty());
1513
1514 // Build a simple layout based on the regular layout of jump tables.
1515 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1516 unsigned EntrySize = getJumpTableEntrySize();
1517 for (unsigned I = 0; I != Functions.size(); ++I)
1518 GlobalLayout[Functions[I]] = I * EntrySize;
1519
1520 Function *JumpTableFn =
1521 Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()),
1522 /* IsVarArg */ false),
1523 GlobalValue::PrivateLinkage,
1524 M.getDataLayout().getProgramAddressSpace(),
1525 ".cfi.jumptable", &M);
1526 ArrayType *JumpTableType =
1527 ArrayType::get(getJumpTableEntryType(), Functions.size());
1528 auto JumpTable =
1529 ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
1530
1531 lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
1532
1533 {
1534 ScopedSaveAliaseesAndUsed S(M);
1535
1536 // Build aliases pointing to offsets into the jump table, and replace
1537 // references to the original functions with references to the aliases.
1538 for (unsigned I = 0; I != Functions.size(); ++I) {
1539 Function *F = cast<Function>(Functions[I]->getGlobal());
1540 bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
1541
1542 Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
1543 ConstantExpr::getInBoundsGetElementPtr(
1544 JumpTableType, JumpTable,
1545 ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0),
1546 ConstantInt::get(IntPtrTy, I)}),
1547 F->getType());
1548 if (Functions[I]->isExported()) {
1549 if (IsJumpTableCanonical) {
1550 ExportSummary->cfiFunctionDefs().insert(std::string(F->getName()));
1551 } else {
1552 GlobalAlias *JtAlias = GlobalAlias::create(
1553 F->getValueType(), 0, GlobalValue::ExternalLinkage,
1554 F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M);
1555 JtAlias->setVisibility(GlobalValue::HiddenVisibility);
1556 ExportSummary->cfiFunctionDecls().insert(std::string(F->getName()));
1557 }
1558 }
1559 if (!IsJumpTableCanonical) {
1560 if (F->hasExternalWeakLinkage())
1561 replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr,
1562 IsJumpTableCanonical);
1563 else
1564 replaceCfiUses(F, CombinedGlobalElemPtr, IsJumpTableCanonical);
1565 } else {
1566 assert(F->getType()->getAddressSpace() == 0);
1567
1568 GlobalAlias *FAlias =
1569 GlobalAlias::create(F->getValueType(), 0, F->getLinkage(), "",
1570 CombinedGlobalElemPtr, &M);
1571 FAlias->setVisibility(F->getVisibility());
1572 FAlias->takeName(F);
1573 if (FAlias->hasName())
1574 F->setName(FAlias->getName() + ".cfi");
1575 replaceCfiUses(F, FAlias, IsJumpTableCanonical);
1576 if (!F->hasLocalLinkage())
1577 F->setVisibility(GlobalVariable::HiddenVisibility);
1578 }
1579 }
1580 }
1581
1582 createJumpTable(JumpTableFn, Functions);
1583 }
1584
1585 /// Assign a dummy layout using an incrementing counter, tag each function
1586 /// with its index represented as metadata, and lower each type test to an
1587 /// integer range comparison. During generation of the indirect function call
1588 /// table in the backend, it will assign the given indexes.
1589 /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
1590 /// been finalized.
buildBitSetsFromFunctionsWASM(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)1591 void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1592 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
1593 assert(!Functions.empty());
1594
1595 // Build consecutive monotonic integer ranges for each call target set
1596 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
1597
1598 for (GlobalTypeMember *GTM : Functions) {
1599 Function *F = cast<Function>(GTM->getGlobal());
1600
1601 // Skip functions that are not address taken, to avoid bloating the table
1602 if (!F->hasAddressTaken())
1603 continue;
1604
1605 // Store metadata with the index for each function
1606 MDNode *MD = MDNode::get(F->getContext(),
1607 ArrayRef<Metadata *>(ConstantAsMetadata::get(
1608 ConstantInt::get(Int64Ty, IndirectIndex))));
1609 F->setMetadata("wasm.index", MD);
1610
1611 // Assign the counter value
1612 GlobalLayout[GTM] = IndirectIndex++;
1613 }
1614
1615 // The indirect function table index space starts at zero, so pass a NULL
1616 // pointer as the subtracted "jump table" offset.
1617 lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
1618 GlobalLayout);
1619 }
1620
buildBitSetsFromDisjointSet(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Globals,ArrayRef<ICallBranchFunnel * > ICallBranchFunnels)1621 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1622 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
1623 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
1624 DenseMap<Metadata *, uint64_t> TypeIdIndices;
1625 for (unsigned I = 0; I != TypeIds.size(); ++I)
1626 TypeIdIndices[TypeIds[I]] = I;
1627
1628 // For each type identifier, build a set of indices that refer to members of
1629 // the type identifier.
1630 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
1631 unsigned GlobalIndex = 0;
1632 DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
1633 for (GlobalTypeMember *GTM : Globals) {
1634 for (MDNode *Type : GTM->types()) {
1635 // Type = { offset, type identifier }
1636 auto I = TypeIdIndices.find(Type->getOperand(1));
1637 if (I != TypeIdIndices.end())
1638 TypeMembers[I->second].insert(GlobalIndex);
1639 }
1640 GlobalIndices[GTM] = GlobalIndex;
1641 GlobalIndex++;
1642 }
1643
1644 for (ICallBranchFunnel *JT : ICallBranchFunnels) {
1645 TypeMembers.emplace_back();
1646 std::set<uint64_t> &TMSet = TypeMembers.back();
1647 for (GlobalTypeMember *T : JT->targets())
1648 TMSet.insert(GlobalIndices[T]);
1649 }
1650
1651 // Order the sets of indices by size. The GlobalLayoutBuilder works best
1652 // when given small index sets first.
1653 llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1,
1654 const std::set<uint64_t> &O2) {
1655 return O1.size() < O2.size();
1656 });
1657
1658 // Create a GlobalLayoutBuilder and provide it with index sets as layout
1659 // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
1660 // close together as possible.
1661 GlobalLayoutBuilder GLB(Globals.size());
1662 for (auto &&MemSet : TypeMembers)
1663 GLB.addFragment(MemSet);
1664
1665 // Build a vector of globals with the computed layout.
1666 bool IsGlobalSet =
1667 Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
1668 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1669 auto OGTMI = OrderedGTMs.begin();
1670 for (auto &&F : GLB.Fragments) {
1671 for (auto &&Offset : F) {
1672 if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
1673 report_fatal_error("Type identifier may not contain both global "
1674 "variables and functions");
1675 *OGTMI++ = Globals[Offset];
1676 }
1677 }
1678
1679 // Build the bitsets from this disjoint set.
1680 if (IsGlobalSet)
1681 buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
1682 else
1683 buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
1684 }
1685
1686 /// Lower all type tests in this module.
LowerTypeTestsModule(Module & M,ModuleSummaryIndex * ExportSummary,const ModuleSummaryIndex * ImportSummary,bool DropTypeTests)1687 LowerTypeTestsModule::LowerTypeTestsModule(
1688 Module &M, ModuleSummaryIndex *ExportSummary,
1689 const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
1690 : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary),
1691 DropTypeTests(DropTypeTests) {
1692 assert(!(ExportSummary && ImportSummary));
1693 Triple TargetTriple(M.getTargetTriple());
1694 Arch = TargetTriple.getArch();
1695 OS = TargetTriple.getOS();
1696 ObjectFormat = TargetTriple.getObjectFormat();
1697 }
1698
runForTesting(Module & M)1699 bool LowerTypeTestsModule::runForTesting(Module &M) {
1700 ModuleSummaryIndex Summary(/*HaveGVs=*/false);
1701
1702 // Handle the command-line summary arguments. This code is for testing
1703 // purposes only, so we handle errors directly.
1704 if (!ClReadSummary.empty()) {
1705 ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
1706 ": ");
1707 auto ReadSummaryFile =
1708 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
1709
1710 yaml::Input In(ReadSummaryFile->getBuffer());
1711 In >> Summary;
1712 ExitOnErr(errorCodeToError(In.error()));
1713 }
1714
1715 bool Changed =
1716 LowerTypeTestsModule(
1717 M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
1718 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr,
1719 /*DropTypeTests*/ false)
1720 .lower();
1721
1722 if (!ClWriteSummary.empty()) {
1723 ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
1724 ": ");
1725 std::error_code EC;
1726 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_Text);
1727 ExitOnErr(errorCodeToError(EC));
1728
1729 yaml::Output Out(OS);
1730 Out << Summary;
1731 }
1732
1733 return Changed;
1734 }
1735
isDirectCall(Use & U)1736 static bool isDirectCall(Use& U) {
1737 auto *Usr = dyn_cast<CallInst>(U.getUser());
1738 if (Usr) {
1739 auto *CB = dyn_cast<CallBase>(Usr);
1740 if (CB && CB->isCallee(&U))
1741 return true;
1742 }
1743 return false;
1744 }
1745
replaceCfiUses(Function * Old,Value * New,bool IsJumpTableCanonical)1746 void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
1747 bool IsJumpTableCanonical) {
1748 SmallSetVector<Constant *, 4> Constants;
1749 auto UI = Old->use_begin(), E = Old->use_end();
1750 for (; UI != E;) {
1751 Use &U = *UI;
1752 ++UI;
1753
1754 // Skip block addresses
1755 if (isa<BlockAddress>(U.getUser()))
1756 continue;
1757
1758 // Skip direct calls to externally defined or non-dso_local functions
1759 if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
1760 continue;
1761
1762 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
1763 // constant because they are uniqued.
1764 if (auto *C = dyn_cast<Constant>(U.getUser())) {
1765 if (!isa<GlobalValue>(C)) {
1766 // Save unique users to avoid processing operand replacement
1767 // more than once.
1768 Constants.insert(C);
1769 continue;
1770 }
1771 }
1772
1773 U.set(New);
1774 }
1775
1776 // Process operand replacement of saved constants.
1777 for (auto *C : Constants)
1778 C->handleOperandChange(Old, New);
1779 }
1780
replaceDirectCalls(Value * Old,Value * New)1781 void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
1782 Old->replaceUsesWithIf(New, [](Use &U) { return isDirectCall(U); });
1783 }
1784
lower()1785 bool LowerTypeTestsModule::lower() {
1786 Function *TypeTestFunc =
1787 M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1788
1789 if (DropTypeTests && TypeTestFunc) {
1790 for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
1791 UI != UE;) {
1792 auto *CI = cast<CallInst>((*UI++).getUser());
1793 // Find and erase llvm.assume intrinsics for this llvm.type.test call.
1794 for (auto CIU = CI->use_begin(), CIUE = CI->use_end(); CIU != CIUE;) {
1795 if (auto *AssumeCI = dyn_cast<CallInst>((*CIU++).getUser())) {
1796 Function *F = AssumeCI->getCalledFunction();
1797 if (F && F->getIntrinsicID() == Intrinsic::assume)
1798 AssumeCI->eraseFromParent();
1799 }
1800 }
1801 CI->eraseFromParent();
1802 }
1803
1804 // We have deleted the type intrinsics, so we no longer have enough
1805 // information to reason about the liveness of virtual function pointers
1806 // in GlobalDCE.
1807 for (GlobalVariable &GV : M.globals())
1808 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1809
1810 return true;
1811 }
1812
1813 // If only some of the modules were split, we cannot correctly perform
1814 // this transformation. We already checked for the presense of type tests
1815 // with partially split modules during the thin link, and would have emitted
1816 // an error if any were found, so here we can simply return.
1817 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
1818 (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
1819 return false;
1820
1821 Function *ICallBranchFunnelFunc =
1822 M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel));
1823 if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
1824 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
1825 !ExportSummary && !ImportSummary)
1826 return false;
1827
1828 if (ImportSummary) {
1829 if (TypeTestFunc) {
1830 for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
1831 UI != UE;) {
1832 auto *CI = cast<CallInst>((*UI++).getUser());
1833 importTypeTest(CI);
1834 }
1835 }
1836
1837 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
1838 report_fatal_error(
1839 "unexpected call to llvm.icall.branch.funnel during import phase");
1840
1841 SmallVector<Function *, 8> Defs;
1842 SmallVector<Function *, 8> Decls;
1843 for (auto &F : M) {
1844 // CFI functions are either external, or promoted. A local function may
1845 // have the same name, but it's not the one we are looking for.
1846 if (F.hasLocalLinkage())
1847 continue;
1848 if (ImportSummary->cfiFunctionDefs().count(std::string(F.getName())))
1849 Defs.push_back(&F);
1850 else if (ImportSummary->cfiFunctionDecls().count(
1851 std::string(F.getName())))
1852 Decls.push_back(&F);
1853 }
1854
1855 std::vector<GlobalAlias *> AliasesToErase;
1856 {
1857 ScopedSaveAliaseesAndUsed S(M);
1858 for (auto F : Defs)
1859 importFunction(F, /*isJumpTableCanonical*/ true, AliasesToErase);
1860 for (auto F : Decls)
1861 importFunction(F, /*isJumpTableCanonical*/ false, AliasesToErase);
1862 }
1863 for (GlobalAlias *GA : AliasesToErase)
1864 GA->eraseFromParent();
1865
1866 return true;
1867 }
1868
1869 // Equivalence class set containing type identifiers and the globals that
1870 // reference them. This is used to partition the set of type identifiers in
1871 // the module into disjoint sets.
1872 using GlobalClassesTy = EquivalenceClasses<
1873 PointerUnion<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>;
1874 GlobalClassesTy GlobalClasses;
1875
1876 // Verify the type metadata and build a few data structures to let us
1877 // efficiently enumerate the type identifiers associated with a global:
1878 // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
1879 // of associated type metadata) and a mapping from type identifiers to their
1880 // list of GlobalTypeMembers and last observed index in the list of globals.
1881 // The indices will be used later to deterministically order the list of type
1882 // identifiers.
1883 BumpPtrAllocator Alloc;
1884 struct TIInfo {
1885 unsigned UniqueId;
1886 std::vector<GlobalTypeMember *> RefGlobals;
1887 };
1888 DenseMap<Metadata *, TIInfo> TypeIdInfo;
1889 unsigned CurUniqueId = 0;
1890 SmallVector<MDNode *, 2> Types;
1891
1892 // Cross-DSO CFI emits jumptable entries for exported functions as well as
1893 // address taken functions in case they are address taken in other modules.
1894 const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr;
1895
1896 struct ExportedFunctionInfo {
1897 CfiFunctionLinkage Linkage;
1898 MDNode *FuncMD; // {name, linkage, type[, type...]}
1899 };
1900 DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions;
1901 if (ExportSummary) {
1902 // A set of all functions that are address taken by a live global object.
1903 DenseSet<GlobalValue::GUID> AddressTaken;
1904 for (auto &I : *ExportSummary)
1905 for (auto &GVS : I.second.SummaryList)
1906 if (GVS->isLive())
1907 for (auto &Ref : GVS->refs())
1908 AddressTaken.insert(Ref.getGUID());
1909
1910 NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions");
1911 if (CfiFunctionsMD) {
1912 for (auto FuncMD : CfiFunctionsMD->operands()) {
1913 assert(FuncMD->getNumOperands() >= 2);
1914 StringRef FunctionName =
1915 cast<MDString>(FuncMD->getOperand(0))->getString();
1916 CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>(
1917 cast<ConstantAsMetadata>(FuncMD->getOperand(1))
1918 ->getValue()
1919 ->getUniqueInteger()
1920 .getZExtValue());
1921 const GlobalValue::GUID GUID = GlobalValue::getGUID(
1922 GlobalValue::dropLLVMManglingEscape(FunctionName));
1923 // Do not emit jumptable entries for functions that are not-live and
1924 // have no live references (and are not exported with cross-DSO CFI.)
1925 if (!ExportSummary->isGUIDLive(GUID))
1926 continue;
1927 if (!AddressTaken.count(GUID)) {
1928 if (!CrossDsoCfi || Linkage != CFL_Definition)
1929 continue;
1930
1931 bool Exported = false;
1932 if (auto VI = ExportSummary->getValueInfo(GUID))
1933 for (auto &GVS : VI.getSummaryList())
1934 if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
1935 Exported = true;
1936
1937 if (!Exported)
1938 continue;
1939 }
1940 auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}});
1941 if (!P.second && P.first->second.Linkage != CFL_Definition)
1942 P.first->second = {Linkage, FuncMD};
1943 }
1944
1945 for (const auto &P : ExportedFunctions) {
1946 StringRef FunctionName = P.first;
1947 CfiFunctionLinkage Linkage = P.second.Linkage;
1948 MDNode *FuncMD = P.second.FuncMD;
1949 Function *F = M.getFunction(FunctionName);
1950 if (F && F->hasLocalLinkage()) {
1951 // Locally defined function that happens to have the same name as a
1952 // function defined in a ThinLTO module. Rename it to move it out of
1953 // the way of the external reference that we're about to create.
1954 // Note that setName will find a unique name for the function, so even
1955 // if there is an existing function with the suffix there won't be a
1956 // name collision.
1957 F->setName(F->getName() + ".1");
1958 F = nullptr;
1959 }
1960
1961 if (!F)
1962 F = Function::Create(
1963 FunctionType::get(Type::getVoidTy(M.getContext()), false),
1964 GlobalVariable::ExternalLinkage,
1965 M.getDataLayout().getProgramAddressSpace(), FunctionName, &M);
1966
1967 // If the function is available_externally, remove its definition so
1968 // that it is handled the same way as a declaration. Later we will try
1969 // to create an alias using this function's linkage, which will fail if
1970 // the linkage is available_externally. This will also result in us
1971 // following the code path below to replace the type metadata.
1972 if (F->hasAvailableExternallyLinkage()) {
1973 F->setLinkage(GlobalValue::ExternalLinkage);
1974 F->deleteBody();
1975 F->setComdat(nullptr);
1976 F->clearMetadata();
1977 }
1978
1979 // Update the linkage for extern_weak declarations when a definition
1980 // exists.
1981 if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
1982 F->setLinkage(GlobalValue::ExternalLinkage);
1983
1984 // If the function in the full LTO module is a declaration, replace its
1985 // type metadata with the type metadata we found in cfi.functions. That
1986 // metadata is presumed to be more accurate than the metadata attached
1987 // to the declaration.
1988 if (F->isDeclaration()) {
1989 if (Linkage == CFL_WeakDeclaration)
1990 F->setLinkage(GlobalValue::ExternalWeakLinkage);
1991
1992 F->eraseMetadata(LLVMContext::MD_type);
1993 for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
1994 F->addMetadata(LLVMContext::MD_type,
1995 *cast<MDNode>(FuncMD->getOperand(I).get()));
1996 }
1997 }
1998 }
1999 }
2000
2001 DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
2002 for (GlobalObject &GO : M.global_objects()) {
2003 if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
2004 continue;
2005
2006 Types.clear();
2007 GO.getMetadata(LLVMContext::MD_type, Types);
2008
2009 bool IsJumpTableCanonical = false;
2010 bool IsExported = false;
2011 if (Function *F = dyn_cast<Function>(&GO)) {
2012 IsJumpTableCanonical = isJumpTableCanonical(F);
2013 if (ExportedFunctions.count(F->getName())) {
2014 IsJumpTableCanonical |=
2015 ExportedFunctions[F->getName()].Linkage == CFL_Definition;
2016 IsExported = true;
2017 // TODO: The logic here checks only that the function is address taken,
2018 // not that the address takers are live. This can be updated to check
2019 // their liveness and emit fewer jumptable entries once monolithic LTO
2020 // builds also emit summaries.
2021 } else if (!F->hasAddressTaken()) {
2022 if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
2023 continue;
2024 }
2025 }
2026
2027 auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical,
2028 IsExported, Types);
2029 GlobalTypeMembers[&GO] = GTM;
2030 for (MDNode *Type : Types) {
2031 verifyTypeMDNode(&GO, Type);
2032 auto &Info = TypeIdInfo[Type->getOperand(1)];
2033 Info.UniqueId = ++CurUniqueId;
2034 Info.RefGlobals.push_back(GTM);
2035 }
2036 }
2037
2038 auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
2039 // Add the call site to the list of call sites for this type identifier. We
2040 // also use TypeIdUsers to keep track of whether we have seen this type
2041 // identifier before. If we have, we don't need to re-add the referenced
2042 // globals to the equivalence class.
2043 auto Ins = TypeIdUsers.insert({TypeId, {}});
2044 if (Ins.second) {
2045 // Add the type identifier to the equivalence class.
2046 GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
2047 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
2048
2049 // Add the referenced globals to the type identifier's equivalence class.
2050 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2051 CurSet = GlobalClasses.unionSets(
2052 CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
2053 }
2054
2055 return Ins.first->second;
2056 };
2057
2058 if (TypeTestFunc) {
2059 for (const Use &U : TypeTestFunc->uses()) {
2060 auto CI = cast<CallInst>(U.getUser());
2061
2062 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
2063 if (!TypeIdMDVal)
2064 report_fatal_error("Second argument of llvm.type.test must be metadata");
2065 auto TypeId = TypeIdMDVal->getMetadata();
2066 AddTypeIdUse(TypeId).CallSites.push_back(CI);
2067 }
2068 }
2069
2070 if (ICallBranchFunnelFunc) {
2071 for (const Use &U : ICallBranchFunnelFunc->uses()) {
2072 if (Arch != Triple::x86_64)
2073 report_fatal_error(
2074 "llvm.icall.branch.funnel not supported on this target");
2075
2076 auto CI = cast<CallInst>(U.getUser());
2077
2078 std::vector<GlobalTypeMember *> Targets;
2079 if (CI->getNumArgOperands() % 2 != 1)
2080 report_fatal_error("number of arguments should be odd");
2081
2082 GlobalClassesTy::member_iterator CurSet;
2083 for (unsigned I = 1; I != CI->getNumArgOperands(); I += 2) {
2084 int64_t Offset;
2085 auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
2086 CI->getOperand(I), Offset, M.getDataLayout()));
2087 if (!Base)
2088 report_fatal_error(
2089 "Expected branch funnel operand to be global value");
2090
2091 GlobalTypeMember *GTM = GlobalTypeMembers[Base];
2092 Targets.push_back(GTM);
2093 GlobalClassesTy::member_iterator NewSet =
2094 GlobalClasses.findLeader(GlobalClasses.insert(GTM));
2095 if (I == 1)
2096 CurSet = NewSet;
2097 else
2098 CurSet = GlobalClasses.unionSets(CurSet, NewSet);
2099 }
2100
2101 GlobalClasses.unionSets(
2102 CurSet, GlobalClasses.findLeader(
2103 GlobalClasses.insert(ICallBranchFunnel::create(
2104 Alloc, CI, Targets, ++CurUniqueId))));
2105 }
2106 }
2107
2108 if (ExportSummary) {
2109 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
2110 for (auto &P : TypeIdInfo) {
2111 if (auto *TypeId = dyn_cast<MDString>(P.first))
2112 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
2113 TypeId);
2114 }
2115
2116 for (auto &P : *ExportSummary) {
2117 for (auto &S : P.second.SummaryList) {
2118 if (!ExportSummary->isGlobalValueLive(S.get()))
2119 continue;
2120 if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject()))
2121 for (GlobalValue::GUID G : FS->type_tests())
2122 for (Metadata *MD : MetadataByGUID[G])
2123 AddTypeIdUse(MD).IsExported = true;
2124 }
2125 }
2126 }
2127
2128 if (GlobalClasses.empty())
2129 return false;
2130
2131 // Build a list of disjoint sets ordered by their maximum global index for
2132 // determinism.
2133 std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
2134 for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
2135 E = GlobalClasses.end();
2136 I != E; ++I) {
2137 if (!I->isLeader())
2138 continue;
2139 ++NumTypeIdDisjointSets;
2140
2141 unsigned MaxUniqueId = 0;
2142 for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
2143 MI != GlobalClasses.member_end(); ++MI) {
2144 if (auto *MD = MI->dyn_cast<Metadata *>())
2145 MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
2146 else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
2147 MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
2148 }
2149 Sets.emplace_back(I, MaxUniqueId);
2150 }
2151 llvm::sort(Sets,
2152 [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
2153 const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
2154 return S1.second < S2.second;
2155 });
2156
2157 // For each disjoint set we found...
2158 for (const auto &S : Sets) {
2159 // Build the list of type identifiers in this disjoint set.
2160 std::vector<Metadata *> TypeIds;
2161 std::vector<GlobalTypeMember *> Globals;
2162 std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2163 for (GlobalClassesTy::member_iterator MI =
2164 GlobalClasses.member_begin(S.first);
2165 MI != GlobalClasses.member_end(); ++MI) {
2166 if (MI->is<Metadata *>())
2167 TypeIds.push_back(MI->get<Metadata *>());
2168 else if (MI->is<GlobalTypeMember *>())
2169 Globals.push_back(MI->get<GlobalTypeMember *>());
2170 else
2171 ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
2172 }
2173
2174 // Order type identifiers by unique ID for determinism. This ordering is
2175 // stable as there is a one-to-one mapping between metadata and unique IDs.
2176 llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) {
2177 return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
2178 });
2179
2180 // Same for the branch funnels.
2181 llvm::sort(ICallBranchFunnels,
2182 [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2183 return F1->UniqueId < F2->UniqueId;
2184 });
2185
2186 // Build bitsets for this disjoint set.
2187 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2188 }
2189
2190 allocateByteArrays();
2191
2192 // Parse alias data to replace stand-in function declarations for aliases
2193 // with an alias to the intended target.
2194 if (ExportSummary) {
2195 if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {
2196 for (auto AliasMD : AliasesMD->operands()) {
2197 assert(AliasMD->getNumOperands() >= 4);
2198 StringRef AliasName =
2199 cast<MDString>(AliasMD->getOperand(0))->getString();
2200 StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
2201
2202 if (!ExportedFunctions.count(Aliasee) ||
2203 ExportedFunctions[Aliasee].Linkage != CFL_Definition ||
2204 !M.getNamedAlias(Aliasee))
2205 continue;
2206
2207 GlobalValue::VisibilityTypes Visibility =
2208 static_cast<GlobalValue::VisibilityTypes>(
2209 cast<ConstantAsMetadata>(AliasMD->getOperand(2))
2210 ->getValue()
2211 ->getUniqueInteger()
2212 .getZExtValue());
2213 bool Weak =
2214 static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
2215 ->getValue()
2216 ->getUniqueInteger()
2217 .getZExtValue());
2218
2219 auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee));
2220 Alias->setVisibility(Visibility);
2221 if (Weak)
2222 Alias->setLinkage(GlobalValue::WeakAnyLinkage);
2223
2224 if (auto *F = M.getFunction(AliasName)) {
2225 Alias->takeName(F);
2226 F->replaceAllUsesWith(Alias);
2227 F->eraseFromParent();
2228 } else {
2229 Alias->setName(AliasName);
2230 }
2231 }
2232 }
2233 }
2234
2235 // Emit .symver directives for exported functions, if they exist.
2236 if (ExportSummary) {
2237 if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) {
2238 for (auto Symver : SymversMD->operands()) {
2239 assert(Symver->getNumOperands() >= 2);
2240 StringRef SymbolName =
2241 cast<MDString>(Symver->getOperand(0))->getString();
2242 StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
2243
2244 if (!ExportedFunctions.count(SymbolName))
2245 continue;
2246
2247 M.appendModuleInlineAsm(
2248 (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
2249 }
2250 }
2251 }
2252
2253 return true;
2254 }
2255
run(Module & M,ModuleAnalysisManager & AM)2256 PreservedAnalyses LowerTypeTestsPass::run(Module &M,
2257 ModuleAnalysisManager &AM) {
2258 bool Changed;
2259 if (UseCommandLine)
2260 Changed = LowerTypeTestsModule::runForTesting(M);
2261 else
2262 Changed =
2263 LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
2264 .lower();
2265 if (!Changed)
2266 return PreservedAnalyses::all();
2267 return PreservedAnalyses::none();
2268 }
2269