/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/IPO/LowerTypeTests.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- LowerTypeTests.cpp - type metadata lowering pass ------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This pass lowers type metadata and calls to the llvm.type.test intrinsic. |
11 | | // See http://llvm.org/docs/TypeMetadata.html for more information. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "llvm/Transforms/IPO/LowerTypeTests.h" |
16 | | #include "llvm/ADT/EquivalenceClasses.h" |
17 | | #include "llvm/ADT/SetVector.h" |
18 | | #include "llvm/ADT/Statistic.h" |
19 | | #include "llvm/ADT/Triple.h" |
20 | | #include "llvm/Analysis/TypeMetadataUtils.h" |
21 | | #include "llvm/IR/Constant.h" |
22 | | #include "llvm/IR/Constants.h" |
23 | | #include "llvm/IR/Function.h" |
24 | | #include "llvm/IR/GlobalObject.h" |
25 | | #include "llvm/IR/GlobalVariable.h" |
26 | | #include "llvm/IR/IRBuilder.h" |
27 | | #include "llvm/IR/InlineAsm.h" |
28 | | #include "llvm/IR/Instructions.h" |
29 | | #include "llvm/IR/Intrinsics.h" |
30 | | #include "llvm/IR/Module.h" |
31 | | #include "llvm/IR/ModuleSummaryIndexYAML.h" |
32 | | #include "llvm/IR/Operator.h" |
33 | | #include "llvm/Pass.h" |
34 | | #include "llvm/Support/Debug.h" |
35 | | #include "llvm/Support/Error.h" |
36 | | #include "llvm/Support/FileSystem.h" |
37 | | #include "llvm/Support/TrailingObjects.h" |
38 | | #include "llvm/Support/raw_ostream.h" |
39 | | #include "llvm/Transforms/IPO.h" |
40 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
41 | | #include "llvm/Transforms/Utils/ModuleUtils.h" |
42 | | |
43 | | using namespace llvm; |
44 | | using namespace lowertypetests; |
45 | | |
46 | | #define DEBUG_TYPE "lowertypetests" |
47 | | |
48 | | STATISTIC(ByteArraySizeBits, "Byte array size in bits"); |
49 | | STATISTIC(ByteArraySizeBytes, "Byte array size in bytes"); |
50 | | STATISTIC(NumByteArraysCreated, "Number of byte arrays created"); |
51 | | STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered"); |
52 | | STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers"); |
53 | | |
54 | | static cl::opt<bool> AvoidReuse( |
55 | | "lowertypetests-avoid-reuse", |
56 | | cl::desc("Try to avoid reuse of byte array addresses using aliases"), |
57 | | cl::Hidden, cl::init(true)); |
58 | | |
59 | | static cl::opt<PassSummaryAction> ClSummaryAction( |
60 | | "lowertypetests-summary-action", |
61 | | cl::desc("What to do with the summary when running this pass"), |
62 | | cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), |
63 | | clEnumValN(PassSummaryAction::Import, "import", |
64 | | "Import typeid resolutions from summary and globals"), |
65 | | clEnumValN(PassSummaryAction::Export, "export", |
66 | | "Export typeid resolutions to summary and globals")), |
67 | | cl::Hidden); |
68 | | |
69 | | static cl::opt<std::string> ClReadSummary( |
70 | | "lowertypetests-read-summary", |
71 | | cl::desc("Read summary from given YAML file before running pass"), |
72 | | cl::Hidden); |
73 | | |
74 | | static cl::opt<std::string> ClWriteSummary( |
75 | | "lowertypetests-write-summary", |
76 | | cl::desc("Write summary to given YAML file after running pass"), |
77 | | cl::Hidden); |
78 | | |
79 | 3.58k | bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const { |
80 | 3.58k | if (Offset < ByteOffset) |
81 | 44 | return false; |
82 | 3.54k | |
83 | 3.54k | if (3.54k (Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 03.54k ) |
84 | 892 | return false; |
85 | 2.64k | |
86 | 2.64k | uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2; |
87 | 2.64k | if (BitOffset >= BitSize) |
88 | 2.58k | return false; |
89 | 63 | |
90 | 63 | return Bits.count(BitOffset); |
91 | 63 | } |
92 | | |
93 | 0 | void BitSetInfo::print(raw_ostream &OS) const { |
94 | 0 | OS << "offset " << ByteOffset << " size " << BitSize << " align " |
95 | 0 | << (1 << AlignLog2); |
96 | 0 |
|
97 | 0 | if (isAllOnes()0 ) { |
98 | 0 | OS << " all-ones\n"; |
99 | 0 | return; |
100 | 0 | } |
101 | 0 |
|
102 | 0 | OS << " { "; |
103 | 0 | for (uint64_t B : Bits) |
104 | 0 | OS << B << ' '; |
105 | 0 | OS << "}\n"; |
106 | 0 | } |
107 | | |
108 | 77 | BitSetInfo BitSetBuilder::build() { |
109 | 77 | if (Min > Max) |
110 | 4 | Min = 0; |
111 | 77 | |
112 | 77 | // Normalize each offset against the minimum observed offset, and compute |
113 | 77 | // the bitwise OR of each of the offsets. The number of trailing zeros |
114 | 77 | // in the mask gives us the log2 of the alignment of all offsets, which |
115 | 77 | // allows us to compress the bitset by only storing one bit per aligned |
116 | 77 | // address. |
117 | 77 | uint64_t Mask = 0; |
118 | 398 | for (uint64_t &Offset : Offsets) { |
119 | 398 | Offset -= Min; |
120 | 398 | Mask |= Offset; |
121 | 398 | } |
122 | 77 | |
123 | 77 | BitSetInfo BSI; |
124 | 77 | BSI.ByteOffset = Min; |
125 | 77 | |
126 | 77 | BSI.AlignLog2 = 0; |
127 | 77 | if (Mask != 0) |
128 | 47 | BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined); |
129 | 77 | |
130 | 77 | // Build the compressed bitset while normalizing the offsets against the |
131 | 77 | // computed alignment. |
132 | 77 | BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1; |
133 | 398 | for (uint64_t Offset : Offsets) { |
134 | 398 | Offset >>= BSI.AlignLog2; |
135 | 398 | BSI.Bits.insert(Offset); |
136 | 398 | } |
137 | 77 | |
138 | 77 | return BSI; |
139 | 77 | } |
140 | | |
141 | 75 | void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) { |
142 | 75 | // Create a new fragment to hold the layout for F. |
143 | 75 | Fragments.emplace_back(); |
144 | 75 | std::vector<uint64_t> &Fragment = Fragments.back(); |
145 | 75 | uint64_t FragmentIndex = Fragments.size() - 1; |
146 | 75 | |
147 | 121 | for (auto ObjIndex : F) { |
148 | 121 | uint64_t OldFragmentIndex = FragmentMap[ObjIndex]; |
149 | 121 | if (OldFragmentIndex == 0121 ) { |
150 | 98 | // We haven't seen this object index before, so just add it to the current |
151 | 98 | // fragment. |
152 | 98 | Fragment.push_back(ObjIndex); |
153 | 121 | } else { |
154 | 23 | // This index belongs to an existing fragment. Copy the elements of the |
155 | 23 | // old fragment into this one and clear the old fragment. We don't update |
156 | 23 | // the fragment map just yet, this ensures that any further references to |
157 | 23 | // indices from the old fragment in this fragment do not insert any more |
158 | 23 | // indices. |
159 | 23 | std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex]; |
160 | 23 | Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end()); |
161 | 23 | OldFragment.clear(); |
162 | 23 | } |
163 | 121 | } |
164 | 75 | |
165 | 75 | // Update the fragment map to point our object indices to this fragment. |
166 | 75 | for (uint64_t ObjIndex : Fragment) |
167 | 133 | FragmentMap[ObjIndex] = FragmentIndex; |
168 | 75 | } |
169 | | |
170 | | void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits, |
171 | | uint64_t BitSize, uint64_t &AllocByteOffset, |
172 | 25 | uint8_t &AllocMask) { |
173 | 25 | // Find the smallest current allocation. |
174 | 25 | unsigned Bit = 0; |
175 | 200 | for (unsigned I = 1; I != BitsPerByte200 ; ++I175 ) |
176 | 175 | if (175 BitAllocs[I] < BitAllocs[Bit]175 ) |
177 | 61 | Bit = I; |
178 | 25 | |
179 | 25 | AllocByteOffset = BitAllocs[Bit]; |
180 | 25 | |
181 | 25 | // Add our size to it. |
182 | 25 | unsigned ReqSize = AllocByteOffset + BitSize; |
183 | 25 | BitAllocs[Bit] = ReqSize; |
184 | 25 | if (Bytes.size() < ReqSize) |
185 | 6 | Bytes.resize(ReqSize); |
186 | 25 | |
187 | 25 | // Set our bits. |
188 | 25 | AllocMask = 1 << Bit; |
189 | 25 | for (uint64_t B : Bits) |
190 | 35 | Bytes[AllocByteOffset + B] |= AllocMask; |
191 | 25 | } |
192 | | |
193 | | namespace { |
194 | | |
195 | | struct ByteArrayInfo { |
196 | | std::set<uint64_t> Bits; |
197 | | uint64_t BitSize; |
198 | | GlobalVariable *ByteArray; |
199 | | GlobalVariable *MaskGlobal; |
200 | | uint8_t *MaskPtr = nullptr; |
201 | | }; |
202 | | |
203 | | /// A POD-like structure that we use to store a global reference together with |
204 | | /// its metadata types. In this pass we frequently need to query the set of |
205 | | /// metadata types referenced by a global, which at the IR level is an expensive |
206 | | /// operation involving a map lookup; this data structure helps to reduce the |
207 | | /// number of times we need to do this lookup. |
208 | | class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> { |
209 | | GlobalObject *GO; |
210 | | size_t NTypes; |
211 | | // For functions: true if this is a definition (either in the merged module or |
212 | | // in one of the thinlto modules). |
213 | | bool IsDefinition; |
214 | | // For functions: true if this function is either defined or used in a thinlto |
215 | | // module and its jumptable entry needs to be exported to thinlto backends. |
216 | | bool IsExported; |
217 | | |
218 | | friend TrailingObjects; |
219 | 0 | size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; } |
220 | | |
221 | | public: |
222 | | static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO, |
223 | | bool IsDefinition, bool IsExported, |
224 | 85 | ArrayRef<MDNode *> Types) { |
225 | 85 | auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate( |
226 | 85 | totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember))); |
227 | 85 | GTM->GO = GO; |
228 | 85 | GTM->NTypes = Types.size(); |
229 | 85 | GTM->IsDefinition = IsDefinition; |
230 | 85 | GTM->IsExported = IsExported; |
231 | 85 | std::uninitialized_copy(Types.begin(), Types.end(), |
232 | 85 | GTM->getTrailingObjects<MDNode *>()); |
233 | 85 | return GTM; |
234 | 85 | } |
235 | 282 | GlobalObject *getGlobal() const { |
236 | 282 | return GO; |
237 | 282 | } |
238 | 49 | bool isDefinition() const { |
239 | 49 | return IsDefinition; |
240 | 49 | } |
241 | 39 | bool isExported() const { |
242 | 39 | return IsExported; |
243 | 39 | } |
244 | 189 | ArrayRef<MDNode *> types() const { |
245 | 189 | return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes); |
246 | 189 | } |
247 | | }; |
248 | | |
249 | | class LowerTypeTestsModule { |
250 | | Module &M; |
251 | | |
252 | | ModuleSummaryIndex *ExportSummary; |
253 | | const ModuleSummaryIndex *ImportSummary; |
254 | | |
255 | | Triple::ArchType Arch; |
256 | | Triple::OSType OS; |
257 | | Triple::ObjectFormatType ObjectFormat; |
258 | | |
259 | | IntegerType *Int1Ty = Type::getInt1Ty(M.getContext()); |
260 | | IntegerType *Int8Ty = Type::getInt8Ty(M.getContext()); |
261 | | PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext()); |
262 | | IntegerType *Int32Ty = Type::getInt32Ty(M.getContext()); |
263 | | PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty); |
264 | | IntegerType *Int64Ty = Type::getInt64Ty(M.getContext()); |
265 | | IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0); |
266 | | |
267 | | // Indirect function call index assignment counter for WebAssembly |
268 | | uint64_t IndirectIndex = 1; |
269 | | |
270 | | // Mapping from type identifiers to the call sites that test them, as well as |
271 | | // whether the type identifier needs to be exported to ThinLTO backends as |
272 | | // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId). |
273 | | struct TypeIdUserInfo { |
274 | | std::vector<CallInst *> CallSites; |
275 | | bool IsExported = false; |
276 | | }; |
277 | | DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers; |
278 | | |
279 | | /// This structure describes how to lower type tests for a particular type |
280 | | /// identifier. It is either built directly from the global analysis (during |
281 | | /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type |
282 | | /// identifier summaries and external symbol references (in ThinLTO backends). |
283 | | struct TypeIdLowering { |
284 | | TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat; |
285 | | |
286 | | /// All except Unsat: the start address within the combined global. |
287 | | Constant *OffsetedGlobal; |
288 | | |
289 | | /// ByteArray, Inline, AllOnes: log2 of the required global alignment |
290 | | /// relative to the start address. |
291 | | Constant *AlignLog2; |
292 | | |
293 | | /// ByteArray, Inline, AllOnes: one less than the size of the memory region |
294 | | /// covering members of this type identifier as a multiple of 2^AlignLog2. |
295 | | Constant *SizeM1; |
296 | | |
297 | | /// ByteArray: the byte array to test the address against. |
298 | | Constant *TheByteArray; |
299 | | |
300 | | /// ByteArray: the bit mask to apply to bytes loaded from the byte array. |
301 | | Constant *BitMask; |
302 | | |
303 | | /// Inline: the bit mask to test the address against. |
304 | | Constant *InlineBits; |
305 | | }; |
306 | | |
307 | | std::vector<ByteArrayInfo> ByteArrayInfos; |
308 | | |
309 | | Function *WeakInitializerFn = nullptr; |
310 | | |
311 | | bool shouldExportConstantsAsAbsoluteSymbols(); |
312 | | uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL); |
313 | | TypeIdLowering importTypeId(StringRef TypeId); |
314 | | void importTypeTest(CallInst *CI); |
315 | | void importFunction(Function *F, bool isDefinition); |
316 | | |
317 | | BitSetInfo |
318 | | buildBitSet(Metadata *TypeId, |
319 | | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); |
320 | | ByteArrayInfo *createByteArray(BitSetInfo &BSI); |
321 | | void allocateByteArrays(); |
322 | | Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL, |
323 | | Value *BitOffset); |
324 | | void lowerTypeTestCalls( |
325 | | ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, |
326 | | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); |
327 | | Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI, |
328 | | const TypeIdLowering &TIL); |
329 | | void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds, |
330 | | ArrayRef<GlobalTypeMember *> Globals); |
331 | | unsigned getJumpTableEntrySize(); |
332 | | Type *getJumpTableEntryType(); |
333 | | void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS, |
334 | | Triple::ArchType JumpTableArch, |
335 | | SmallVectorImpl<Value *> &AsmArgs, Function *Dest); |
336 | | void verifyTypeMDNode(GlobalObject *GO, MDNode *Type); |
337 | | void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds, |
338 | | ArrayRef<GlobalTypeMember *> Functions); |
339 | | void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds, |
340 | | ArrayRef<GlobalTypeMember *> Functions); |
341 | | void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds, |
342 | | ArrayRef<GlobalTypeMember *> Functions); |
343 | | void buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds, |
344 | | ArrayRef<GlobalTypeMember *> Globals); |
345 | | |
346 | | void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT); |
347 | | void moveInitializerToModuleConstructor(GlobalVariable *GV); |
348 | | void findGlobalVariableUsersOf(Constant *C, |
349 | | SmallSetVector<GlobalVariable *, 8> &Out); |
350 | | |
351 | | void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions); |
352 | | |
353 | | public: |
354 | | LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary, |
355 | | const ModuleSummaryIndex *ImportSummary); |
356 | | bool lower(); |
357 | | |
358 | | // Lower the module using the action and summary passed as command line |
359 | | // arguments. For testing purposes only. |
360 | | static bool runForTesting(Module &M); |
361 | | }; |
362 | | |
363 | | struct LowerTypeTests : public ModulePass { |
364 | | static char ID; |
365 | | |
366 | | bool UseCommandLine = false; |
367 | | |
368 | | ModuleSummaryIndex *ExportSummary; |
369 | | const ModuleSummaryIndex *ImportSummary; |
370 | | |
371 | 44 | LowerTypeTests() : ModulePass(ID), UseCommandLine(true) { |
372 | 44 | initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); |
373 | 44 | } |
374 | | |
375 | | LowerTypeTests(ModuleSummaryIndex *ExportSummary, |
376 | | const ModuleSummaryIndex *ImportSummary) |
377 | | : ModulePass(ID), ExportSummary(ExportSummary), |
378 | 342 | ImportSummary(ImportSummary) { |
379 | 342 | initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); |
380 | 342 | } |
381 | | |
382 | 386 | bool runOnModule(Module &M) override { |
383 | 386 | if (skipModule(M)) |
384 | 0 | return false; |
385 | 386 | if (386 UseCommandLine386 ) |
386 | 44 | return LowerTypeTestsModule::runForTesting(M); |
387 | 342 | return LowerTypeTestsModule(M, ExportSummary, ImportSummary).lower(); |
388 | 342 | } |
389 | | }; |
390 | | |
391 | | } // anonymous namespace |
392 | | |
393 | | INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false, |
394 | | false) |
395 | | char LowerTypeTests::ID = 0; |
396 | | |
397 | | ModulePass * |
398 | | llvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, |
399 | 342 | const ModuleSummaryIndex *ImportSummary) { |
400 | 342 | return new LowerTypeTests(ExportSummary, ImportSummary); |
401 | 342 | } |
402 | | |
403 | | /// Build a bit set for TypeId using the object layouts in |
404 | | /// GlobalLayout. |
405 | | BitSetInfo LowerTypeTestsModule::buildBitSet( |
406 | | Metadata *TypeId, |
407 | 63 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { |
408 | 63 | BitSetBuilder BSB; |
409 | 63 | |
410 | 63 | // Compute the byte offset of each address associated with this type |
411 | 63 | // identifier. |
412 | 112 | for (auto &GlobalAndOffset : GlobalLayout) { |
413 | 686 | for (MDNode *Type : GlobalAndOffset.first->types()) { |
414 | 686 | if (Type->getOperand(1) != TypeId) |
415 | 328 | continue; |
416 | 358 | uint64_t Offset = |
417 | 358 | cast<ConstantInt>( |
418 | 358 | cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) |
419 | 358 | ->getZExtValue(); |
420 | 358 | BSB.addOffset(GlobalAndOffset.second + Offset); |
421 | 358 | } |
422 | 112 | } |
423 | 63 | |
424 | 63 | return BSB.build(); |
425 | 63 | } |
426 | | |
427 | | /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in |
428 | | /// Bits. This pattern matches to the bt instruction on x86. |
429 | | static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits, |
430 | 4 | Value *BitOffset) { |
431 | 4 | auto BitsType = cast<IntegerType>(Bits->getType()); |
432 | 4 | unsigned BitWidth = BitsType->getBitWidth(); |
433 | 4 | |
434 | 4 | BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType); |
435 | 4 | Value *BitIndex = |
436 | 4 | B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1)); |
437 | 4 | Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex); |
438 | 4 | Value *MaskedBits = B.CreateAnd(Bits, BitMask); |
439 | 4 | return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0)); |
440 | 4 | } |
441 | | |
442 | 8 | ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) { |
443 | 8 | // Create globals to stand in for byte arrays and masks. These never actually |
444 | 8 | // get initialized, we RAUW and erase them later in allocateByteArrays() once |
445 | 8 | // we know the offset and mask to use. |
446 | 8 | auto ByteArrayGlobal = new GlobalVariable( |
447 | 8 | M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); |
448 | 8 | auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true, |
449 | 8 | GlobalValue::PrivateLinkage, nullptr); |
450 | 8 | |
451 | 8 | ByteArrayInfos.emplace_back(); |
452 | 8 | ByteArrayInfo *BAI = &ByteArrayInfos.back(); |
453 | 8 | |
454 | 8 | BAI->Bits = BSI.Bits; |
455 | 8 | BAI->BitSize = BSI.BitSize; |
456 | 8 | BAI->ByteArray = ByteArrayGlobal; |
457 | 8 | BAI->MaskGlobal = MaskGlobal; |
458 | 8 | return BAI; |
459 | 8 | } |
460 | | |
461 | 43 | void LowerTypeTestsModule::allocateByteArrays() { |
462 | 43 | std::stable_sort(ByteArrayInfos.begin(), ByteArrayInfos.end(), |
463 | 4 | [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) { |
464 | 4 | return BAI1.BitSize > BAI2.BitSize; |
465 | 4 | }); |
466 | 43 | |
467 | 43 | std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size()); |
468 | 43 | |
469 | 43 | ByteArrayBuilder BAB; |
470 | 51 | for (unsigned I = 0; I != ByteArrayInfos.size()51 ; ++I8 ) { |
471 | 8 | ByteArrayInfo *BAI = &ByteArrayInfos[I]; |
472 | 8 | |
473 | 8 | uint8_t Mask; |
474 | 8 | BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask); |
475 | 8 | |
476 | 8 | BAI->MaskGlobal->replaceAllUsesWith( |
477 | 8 | ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy)); |
478 | 8 | BAI->MaskGlobal->eraseFromParent(); |
479 | 8 | if (BAI->MaskPtr) |
480 | 2 | *BAI->MaskPtr = Mask; |
481 | 8 | } |
482 | 43 | |
483 | 43 | Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes); |
484 | 43 | auto ByteArray = |
485 | 43 | new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true, |
486 | 43 | GlobalValue::PrivateLinkage, ByteArrayConst); |
487 | 43 | |
488 | 51 | for (unsigned I = 0; I != ByteArrayInfos.size()51 ; ++I8 ) { |
489 | 8 | ByteArrayInfo *BAI = &ByteArrayInfos[I]; |
490 | 8 | |
491 | 8 | Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0), |
492 | 8 | ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])}; |
493 | 8 | Constant *GEP = ConstantExpr::getInBoundsGetElementPtr( |
494 | 8 | ByteArrayConst->getType(), ByteArray, Idxs); |
495 | 8 | |
496 | 8 | // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures |
497 | 8 | // that the pc-relative displacement is folded into the lea instead of the |
498 | 8 | // test instruction getting another displacement. |
499 | 8 | GlobalAlias *Alias = GlobalAlias::create( |
500 | 8 | Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M); |
501 | 8 | BAI->ByteArray->replaceAllUsesWith(Alias); |
502 | 8 | BAI->ByteArray->eraseFromParent(); |
503 | 8 | } |
504 | 43 | |
505 | 43 | ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] + |
506 | 43 | BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] + |
507 | 43 | BAB.BitAllocs[6] + BAB.BitAllocs[7]; |
508 | 43 | ByteArraySizeBytes = BAB.Bytes.size(); |
509 | 43 | } |
510 | | |
511 | | /// Build a test that bit BitOffset is set in the type identifier that was |
512 | | /// lowered to TIL, which must be either an Inline or a ByteArray. |
513 | | Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B, |
514 | | const TypeIdLowering &TIL, |
515 | 16 | Value *BitOffset) { |
516 | 16 | if (TIL.TheKind == TypeTestResolution::Inline16 ) { |
517 | 4 | // If the bit set is sufficiently small, we can avoid a load by bit testing |
518 | 4 | // a constant. |
519 | 4 | return createMaskedBitTest(B, TIL.InlineBits, BitOffset); |
520 | 0 | } else { |
521 | 12 | Constant *ByteArray = TIL.TheByteArray; |
522 | 12 | if (AvoidReuse && 12 !ImportSummary12 ) { |
523 | 6 | // Each use of the byte array uses a different alias. This makes the |
524 | 6 | // backend less likely to reuse previously computed byte array addresses, |
525 | 6 | // improving the security of the CFI mechanism based on this pass. |
526 | 6 | // This won't work when importing because TheByteArray is external. |
527 | 6 | ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage, |
528 | 6 | "bits_use", ByteArray, &M); |
529 | 6 | } |
530 | 12 | |
531 | 12 | Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset); |
532 | 12 | Value *Byte = B.CreateLoad(ByteAddr); |
533 | 12 | |
534 | 12 | Value *ByteAndMask = |
535 | 12 | B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty)); |
536 | 12 | return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0)); |
537 | 12 | } |
538 | 0 | } |
539 | | |
540 | | static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL, |
541 | 85 | Value *V, uint64_t COffset) { |
542 | 85 | if (auto GV85 = dyn_cast<GlobalObject>(V)) { |
543 | 7 | SmallVector<MDNode *, 2> Types; |
544 | 7 | GV->getMetadata(LLVMContext::MD_type, Types); |
545 | 7 | for (MDNode *Type : Types) { |
546 | 7 | if (Type->getOperand(1) != TypeId) |
547 | 0 | continue; |
548 | 7 | uint64_t Offset = |
549 | 7 | cast<ConstantInt>( |
550 | 7 | cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) |
551 | 7 | ->getZExtValue(); |
552 | 7 | if (COffset == Offset) |
553 | 5 | return true; |
554 | 2 | } |
555 | 2 | return false; |
556 | 2 | } |
557 | 78 | |
558 | 78 | if (auto 78 GEP78 = dyn_cast<GEPOperator>(V)) { |
559 | 2 | APInt APOffset(DL.getPointerSizeInBits(0), 0); |
560 | 2 | bool Result = GEP->accumulateConstantOffset(DL, APOffset); |
561 | 2 | if (!Result) |
562 | 0 | return false; |
563 | 2 | COffset += APOffset.getZExtValue(); |
564 | 2 | return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset); |
565 | 2 | } |
566 | 76 | |
567 | 76 | if (auto 76 Op76 = dyn_cast<Operator>(V)) { |
568 | 18 | if (Op->getOpcode() == Instruction::BitCast) |
569 | 18 | return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset); |
570 | 0 |
|
571 | 0 | if (0 Op->getOpcode() == Instruction::Select0 ) |
572 | 0 | return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) && |
573 | 0 | isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset); |
574 | 58 | } |
575 | 58 | |
576 | 58 | return false; |
577 | 58 | } |
578 | | |
579 | | /// Lower a llvm.type.test call to its implementation. Returns the value to |
580 | | /// replace the call with. |
581 | | Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI, |
582 | 77 | const TypeIdLowering &TIL) { |
583 | 77 | if (TIL.TheKind == TypeTestResolution::Unsat) |
584 | 12 | return ConstantInt::getFalse(M.getContext()); |
585 | 65 | |
586 | 65 | Value *Ptr = CI->getArgOperand(0); |
587 | 65 | const DataLayout &DL = M.getDataLayout(); |
588 | 65 | if (isKnownTypeIdMember(TypeId, DL, Ptr, 0)) |
589 | 5 | return ConstantInt::getTrue(M.getContext()); |
590 | 60 | |
591 | 60 | BasicBlock *InitialBB = CI->getParent(); |
592 | 60 | |
593 | 60 | IRBuilder<> B(CI); |
594 | 60 | |
595 | 60 | Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); |
596 | 60 | |
597 | 60 | Constant *OffsetedGlobalAsInt = |
598 | 60 | ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy); |
599 | 60 | if (TIL.TheKind == TypeTestResolution::Single) |
600 | 23 | return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt); |
601 | 37 | |
602 | 37 | Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt); |
603 | 37 | |
604 | 37 | // We need to check that the offset both falls within our range and is |
605 | 37 | // suitably aligned. We can check both properties at the same time by |
606 | 37 | // performing a right rotate by log2(alignment) followed by an integer |
607 | 37 | // comparison against the bitset size. The rotate will move the lower |
608 | 37 | // order bits that need to be zero into the higher order bits of the |
609 | 37 | // result, causing the comparison to fail if they are nonzero. The rotate |
610 | 37 | // also conveniently gives us a bit offset to use during the load from |
611 | 37 | // the bitset. |
612 | 37 | Value *OffsetSHR = |
613 | 37 | B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy)); |
614 | 37 | Value *OffsetSHL = B.CreateShl( |
615 | 37 | PtrOffset, ConstantExpr::getZExt( |
616 | 37 | ConstantExpr::getSub( |
617 | 37 | ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)), |
618 | 37 | TIL.AlignLog2), |
619 | 37 | IntPtrTy)); |
620 | 37 | Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL); |
621 | 37 | |
622 | 37 | Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1); |
623 | 37 | |
624 | 37 | // If the bit set is all ones, testing against it is unnecessary. |
625 | 37 | if (TIL.TheKind == TypeTestResolution::AllOnes) |
626 | 21 | return OffsetInRange; |
627 | 16 | |
628 | 16 | // See if the intrinsic is used in the following common pattern: |
629 | 16 | // br(llvm.type.test(...), thenbb, elsebb) |
630 | 16 | // where nothing happens between the type test and the br. |
631 | 16 | // If so, create slightly simpler IR. |
632 | 16 | if (16 CI->hasOneUse()16 ) |
633 | 14 | if (auto *14 Br14 = dyn_cast<BranchInst>(*CI->user_begin())) |
634 | 2 | if (2 CI->getNextNode() == Br2 ) { |
635 | 2 | BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator()); |
636 | 2 | BasicBlock *Else = Br->getSuccessor(1); |
637 | 2 | BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange); |
638 | 2 | NewBr->setMetadata(LLVMContext::MD_prof, |
639 | 2 | Br->getMetadata(LLVMContext::MD_prof)); |
640 | 2 | ReplaceInstWithInst(InitialBB->getTerminator(), NewBr); |
641 | 2 | |
642 | 2 | // Update phis in Else resulting from InitialBB being split |
643 | 2 | for (auto &Phi : Else->phis()) |
644 | 1 | Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB); |
645 | 14 | |
646 | 14 | IRBuilder<> ThenB(CI); |
647 | 14 | return createBitSetTest(ThenB, TIL, BitOffset); |
648 | 14 | } |
649 | 14 | |
650 | 14 | IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false)); |
651 | 14 | |
652 | 14 | // Now that we know that the offset is in range and aligned, load the |
653 | 14 | // appropriate bit from the bitset. |
654 | 14 | Value *Bit = createBitSetTest(ThenB, TIL, BitOffset); |
655 | 14 | |
656 | 14 | // The value we want is 0 if we came directly from the initial block |
657 | 14 | // (having failed the range or alignment checks), or the loaded bit if |
658 | 14 | // we came from the block in which we loaded it. |
659 | 14 | B.SetInsertPoint(CI); |
660 | 14 | PHINode *P = B.CreatePHI(Int1Ty, 2); |
661 | 14 | P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB); |
662 | 14 | P->addIncoming(Bit, ThenB.GetInsertBlock()); |
663 | 14 | return P; |
664 | 14 | } |
665 | | |
666 | | /// Given a disjoint set of type identifiers and globals, lay out the globals, |
667 | | /// build the bit sets and lower the llvm.type.test calls. |
668 | | void LowerTypeTestsModule::buildBitSetsFromGlobalVariables( |
669 | 21 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) { |
670 | 21 | // Build a new global with the combined contents of the referenced globals. |
671 | 21 | // This global is a struct whose even-indexed elements contain the original |
672 | 21 | // contents of the referenced globals and whose odd-indexed elements contain |
673 | 21 | // any padding required to align the next element to the next power of 2. |
674 | 21 | std::vector<Constant *> GlobalInits; |
675 | 21 | const DataLayout &DL = M.getDataLayout(); |
676 | 33 | for (GlobalTypeMember *G : Globals) { |
677 | 33 | GlobalVariable *GV = cast<GlobalVariable>(G->getGlobal()); |
678 | 33 | GlobalInits.push_back(GV->getInitializer()); |
679 | 33 | uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType()); |
680 | 33 | |
681 | 33 | // Compute the amount of padding required. |
682 | 33 | uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize; |
683 | 33 | |
684 | 33 | // Cap at 128 was found experimentally to have a good data/instruction |
685 | 33 | // overhead tradeoff. |
686 | 33 | if (Padding > 128) |
687 | 0 | Padding = alignTo(InitSize, 128) - InitSize; |
688 | 33 | |
689 | 33 | GlobalInits.push_back( |
690 | 33 | ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding))); |
691 | 33 | } |
692 | 21 | if (!GlobalInits.empty()) |
693 | 19 | GlobalInits.pop_back(); |
694 | 21 | Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits); |
695 | 21 | auto *CombinedGlobal = |
696 | 21 | new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true, |
697 | 21 | GlobalValue::PrivateLinkage, NewInit); |
698 | 21 | |
699 | 21 | StructType *NewTy = cast<StructType>(NewInit->getType()); |
700 | 21 | const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy); |
701 | 21 | |
702 | 21 | // Compute the offsets of the original globals within the new global. |
703 | 21 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; |
704 | 54 | for (unsigned I = 0; I != Globals.size()54 ; ++I33 ) |
705 | 21 | // Multiply by 2 to account for padding elements. |
706 | 33 | GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2); |
707 | 21 | |
708 | 21 | lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout); |
709 | 21 | |
710 | 21 | // Build aliases pointing to offsets into the combined global for each |
711 | 21 | // global from which we built the combined global, and replace references |
712 | 21 | // to the original globals with references to the aliases. |
713 | 54 | for (unsigned I = 0; I != Globals.size()54 ; ++I33 ) { |
714 | 33 | GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal()); |
715 | 33 | |
716 | 33 | // Multiply by 2 to account for padding elements. |
717 | 33 | Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), |
718 | 33 | ConstantInt::get(Int32Ty, I * 2)}; |
719 | 33 | Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( |
720 | 33 | NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs); |
721 | 33 | assert(GV->getType()->getAddressSpace() == 0); |
722 | 33 | GlobalAlias *GAlias = |
723 | 33 | GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(), |
724 | 33 | "", CombinedGlobalElemPtr, &M); |
725 | 33 | GAlias->setVisibility(GV->getVisibility()); |
726 | 33 | GAlias->takeName(GV); |
727 | 33 | GV->replaceAllUsesWith(GAlias); |
728 | 33 | GV->eraseFromParent(); |
729 | 33 | } |
730 | 21 | } |
731 | | |
732 | 78 | bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() { |
733 | 78 | return (Arch == Triple::x86 || Arch == Triple::x86_64) && |
734 | 39 | ObjectFormat == Triple::ELF; |
735 | 78 | } |
736 | | |
737 | | /// Export the given type identifier so that ThinLTO backends may import it. |
738 | | /// Type identifiers are exported by adding coarse-grained information about how |
739 | | /// to test the type identifier to the summary, and creating symbols in the |
740 | | /// object file (aliases and absolute symbols) containing fine-grained |
741 | | /// information about the type identifier. |
742 | | /// |
743 | | /// Returns a pointer to the location in which to store the bitmask, if |
744 | | /// applicable. |
745 | | uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId, |
746 | 24 | const TypeIdLowering &TIL) { |
747 | 24 | TypeTestResolution &TTRes = |
748 | 24 | ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes; |
749 | 24 | TTRes.TheKind = TIL.TheKind; |
750 | 24 | |
751 | 48 | auto ExportGlobal = [&](StringRef Name, Constant *C) { |
752 | 48 | GlobalAlias *GA = |
753 | 48 | GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage, |
754 | 48 | "__typeid_" + TypeId + "_" + Name, C, &M); |
755 | 48 | GA->setVisibility(GlobalValue::HiddenVisibility); |
756 | 48 | }; |
757 | 24 | |
758 | 36 | auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) { |
759 | 36 | if (shouldExportConstantsAsAbsoluteSymbols()) |
760 | 18 | ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy)); |
761 | 36 | else |
762 | 18 | Storage = cast<ConstantInt>(C)->getZExtValue(); |
763 | 36 | }; |
764 | 24 | |
765 | 24 | if (TIL.TheKind != TypeTestResolution::Unsat) |
766 | 24 | ExportGlobal("global_addr", TIL.OffsetedGlobal); |
767 | 24 | |
768 | 24 | if (TIL.TheKind == TypeTestResolution::ByteArray || |
769 | 20 | TIL.TheKind == TypeTestResolution::Inline || |
770 | 24 | TIL.TheKind == TypeTestResolution::AllOnes16 ) { |
771 | 16 | ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2); |
772 | 16 | ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1); |
773 | 16 | |
774 | 16 | uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1; |
775 | 16 | if (TIL.TheKind == TypeTestResolution::Inline) |
776 | 4 | TTRes.SizeM1BitWidth = (BitSize <= 32) ? 4 52 : 62 ; |
777 | 16 | else |
778 | 12 | TTRes.SizeM1BitWidth = (BitSize <= 128) ? 12 78 : 324 ; |
779 | 16 | } |
780 | 24 | |
781 | 24 | if (TIL.TheKind == TypeTestResolution::ByteArray24 ) { |
782 | 4 | ExportGlobal("byte_array", TIL.TheByteArray); |
783 | 4 | if (shouldExportConstantsAsAbsoluteSymbols()) |
784 | 2 | ExportGlobal("bit_mask", TIL.BitMask); |
785 | 4 | else |
786 | 2 | return &TTRes.BitMask; |
787 | 22 | } |
788 | 22 | |
789 | 22 | if (22 TIL.TheKind == TypeTestResolution::Inline22 ) |
790 | 4 | ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits); |
791 | 24 | |
792 | 24 | return nullptr; |
793 | 24 | } |
794 | | |
795 | | LowerTypeTestsModule::TypeIdLowering |
796 | 32 | LowerTypeTestsModule::importTypeId(StringRef TypeId) { |
797 | 32 | const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId); |
798 | 32 | if (!TidSummary) |
799 | 8 | return {}; // Unsat: no globals match this type id. |
800 | 24 | const TypeTestResolution &TTRes = TidSummary->TTRes; |
801 | 24 | |
802 | 24 | TypeIdLowering TIL; |
803 | 24 | TIL.TheKind = TTRes.TheKind; |
804 | 24 | |
805 | 48 | auto ImportGlobal = [&](StringRef Name) { |
806 | 48 | Constant *C = |
807 | 48 | M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(), Int8Ty); |
808 | 48 | if (auto *GV = dyn_cast<GlobalVariable>(C)) |
809 | 48 | GV->setVisibility(GlobalValue::HiddenVisibility); |
810 | 48 | return C; |
811 | 48 | }; |
812 | 24 | |
813 | 24 | auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth, |
814 | 38 | Type *Ty) { |
815 | 38 | if (!shouldExportConstantsAsAbsoluteSymbols()38 ) { |
816 | 19 | Constant *C = |
817 | 19 | ConstantInt::get(isa<IntegerType>(Ty) ? Ty16 : Int64Ty3 , Const); |
818 | 19 | if (!isa<IntegerType>(Ty)) |
819 | 3 | C = ConstantExpr::getIntToPtr(C, Ty); |
820 | 19 | return C; |
821 | 19 | } |
822 | 19 | |
823 | 19 | Constant *C = ImportGlobal(Name); |
824 | 19 | auto *GV = cast<GlobalVariable>(C->stripPointerCasts()); |
825 | 19 | if (isa<IntegerType>(Ty)) |
826 | 16 | C = ConstantExpr::getPtrToInt(C, Ty); |
827 | 19 | if (GV->getMetadata(LLVMContext::MD_absolute_symbol)) |
828 | 0 | return C; |
829 | 19 | |
830 | 19 | auto SetAbsRange = [&](uint64_t Min, uint64_t Max) 19 { |
831 | 19 | auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min)); |
832 | 19 | auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max)); |
833 | 19 | GV->setMetadata(LLVMContext::MD_absolute_symbol, |
834 | 19 | MDNode::get(M.getContext(), {MinC, MaxC})); |
835 | 19 | }; |
836 | 19 | if (AbsWidth == IntPtrTy->getBitWidth()) |
837 | 1 | SetAbsRange(~0ull, ~0ull); // Full set. |
838 | 19 | else |
839 | 18 | SetAbsRange(0, 1ull << AbsWidth); |
840 | 38 | return C; |
841 | 38 | }; |
842 | 24 | |
843 | 24 | if (TIL.TheKind != TypeTestResolution::Unsat) |
844 | 23 | TIL.OffsetedGlobal = ImportGlobal("global_addr"); |
845 | 24 | |
846 | 24 | if (TIL.TheKind == TypeTestResolution::ByteArray || |
847 | 18 | TIL.TheKind == TypeTestResolution::Inline || |
848 | 24 | TIL.TheKind == TypeTestResolution::AllOnes14 ) { |
849 | 14 | TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty); |
850 | 14 | TIL.SizeM1 = |
851 | 14 | ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy); |
852 | 14 | } |
853 | 24 | |
854 | 24 | if (TIL.TheKind == TypeTestResolution::ByteArray24 ) { |
855 | 6 | TIL.TheByteArray = ImportGlobal("byte_array"); |
856 | 6 | TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy); |
857 | 6 | } |
858 | 24 | |
859 | 24 | if (TIL.TheKind == TypeTestResolution::Inline) |
860 | 4 | TIL.InlineBits = ImportConstant( |
861 | 4 | "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth, |
862 | 4 | TTRes.SizeM1BitWidth <= 5 ? Int32Ty2 : Int64Ty2 ); |
863 | 32 | |
864 | 32 | return TIL; |
865 | 32 | } |
866 | | |
867 | 32 | void LowerTypeTestsModule::importTypeTest(CallInst *CI) { |
868 | 32 | auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); |
869 | 32 | if (!TypeIdMDVal) |
870 | 0 | report_fatal_error("Second argument of llvm.type.test must be metadata"); |
871 | 32 | |
872 | 32 | auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata()); |
873 | 32 | if (!TypeIdStr) |
874 | 0 | report_fatal_error( |
875 | 0 | "Second argument of llvm.type.test must be a metadata string"); |
876 | 32 | |
877 | 32 | TypeIdLowering TIL = importTypeId(TypeIdStr->getString()); |
878 | 32 | Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL); |
879 | 32 | CI->replaceAllUsesWith(Lowered); |
880 | 32 | CI->eraseFromParent(); |
881 | 32 | } |
882 | | |
883 | | // ThinLTO backend: the function F has a jump table entry; update this module |
884 | | // accordingly. isDefinition describes the type of the jump table entry. |
885 | 8 | void LowerTypeTestsModule::importFunction(Function *F, bool isDefinition) { |
886 | 8 | assert(F->getType()->getAddressSpace() == 0); |
887 | 8 | |
888 | 8 | // Declaration of a local function - nothing to do. |
889 | 8 | if (F->isDeclarationForLinker() && 8 isDefinition4 ) |
890 | 1 | return; |
891 | 7 | |
892 | 7 | GlobalValue::VisibilityTypes Visibility = F->getVisibility(); |
893 | 7 | std::string Name = F->getName(); |
894 | 7 | Function *FDecl; |
895 | 7 | |
896 | 7 | if (F->isDeclarationForLinker() && 7 !isDefinition3 ) { |
897 | 3 | // Declaration of an external function. |
898 | 3 | FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, |
899 | 3 | Name + ".cfi_jt", &M); |
900 | 3 | FDecl->setVisibility(GlobalValue::HiddenVisibility); |
901 | 7 | } else if (4 isDefinition4 ) { |
902 | 3 | F->setName(Name + ".cfi"); |
903 | 3 | F->setLinkage(GlobalValue::ExternalLinkage); |
904 | 3 | F->setVisibility(GlobalValue::HiddenVisibility); |
905 | 3 | FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, |
906 | 3 | Name, &M); |
907 | 3 | FDecl->setVisibility(Visibility); |
908 | 4 | } else { |
909 | 1 | // Function definition without type metadata, where some other translation |
910 | 1 | // unit contained a declaration with type metadata. This normally happens |
911 | 1 | // during mixed CFI + non-CFI compilation. We do nothing with the function |
912 | 1 | // so that it is treated the same way as a function defined outside of the |
913 | 1 | // LTO unit. |
914 | 1 | return; |
915 | 1 | } |
916 | 6 | |
917 | 6 | if (6 F->isWeakForLinker()6 ) |
918 | 1 | replaceWeakDeclarationWithJumpTablePtr(F, FDecl); |
919 | 6 | else |
920 | 5 | F->replaceAllUsesWith(FDecl); |
921 | 8 | } |
922 | | |
923 | | void LowerTypeTestsModule::lowerTypeTestCalls( |
924 | | ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, |
925 | 49 | const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { |
926 | 49 | CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy); |
927 | 49 | |
928 | 49 | // For each type identifier in this disjoint set... |
929 | 63 | for (Metadata *TypeId : TypeIds) { |
930 | 63 | // Build the bitset. |
931 | 63 | BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout); |
932 | 63 | DEBUG({ |
933 | 63 | if (auto MDS = dyn_cast<MDString>(TypeId)) |
934 | 63 | dbgs() << MDS->getString() << ": "; |
935 | 63 | else |
936 | 63 | dbgs() << "<unnamed>: "; |
937 | 63 | BSI.print(dbgs()); |
938 | 63 | }); |
939 | 63 | |
940 | 63 | ByteArrayInfo *BAI = nullptr; |
941 | 63 | TypeIdLowering TIL; |
942 | 63 | TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr( |
943 | 63 | Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)), |
944 | 63 | TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2); |
945 | 63 | TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1); |
946 | 63 | if (BSI.isAllOnes()63 ) { |
947 | 23 | TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single |
948 | 25 | : TypeTestResolution::AllOnes; |
949 | 63 | } else if (15 BSI.BitSize <= 6415 ) { |
950 | 7 | TIL.TheKind = TypeTestResolution::Inline; |
951 | 7 | uint64_t InlineBits = 0; |
952 | 7 | for (auto Bit : BSI.Bits) |
953 | 8 | InlineBits |= uint64_t(1) << Bit; |
954 | 7 | if (InlineBits == 0) |
955 | 3 | TIL.TheKind = TypeTestResolution::Unsat; |
956 | 7 | else |
957 | 4 | TIL.InlineBits = ConstantInt::get( |
958 | 4 | (BSI.BitSize <= 32) ? Int32Ty2 : Int64Ty2 , InlineBits); |
959 | 15 | } else { |
960 | 8 | TIL.TheKind = TypeTestResolution::ByteArray; |
961 | 8 | ++NumByteArraysCreated; |
962 | 8 | BAI = createByteArray(BSI); |
963 | 8 | TIL.TheByteArray = BAI->ByteArray; |
964 | 8 | TIL.BitMask = BAI->MaskGlobal; |
965 | 8 | } |
966 | 63 | |
967 | 63 | TypeIdUserInfo &TIUI = TypeIdUsers[TypeId]; |
968 | 63 | |
969 | 63 | if (TIUI.IsExported63 ) { |
970 | 24 | uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL); |
971 | 24 | if (BAI) |
972 | 4 | BAI->MaskPtr = MaskPtr; |
973 | 24 | } |
974 | 63 | |
975 | 63 | // Lower each call to llvm.type.test for this type identifier. |
976 | 45 | for (CallInst *CI : TIUI.CallSites) { |
977 | 45 | ++NumTypeTestCallsLowered; |
978 | 45 | Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL); |
979 | 45 | CI->replaceAllUsesWith(Lowered); |
980 | 45 | CI->eraseFromParent(); |
981 | 45 | } |
982 | 63 | } |
983 | 49 | } |
984 | | |
985 | 367 | void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) { |
986 | 367 | if (Type->getNumOperands() != 2) |
987 | 0 | report_fatal_error("All operands of type metadata must have 2 elements"); |
988 | 367 | |
989 | 367 | if (367 GO->isThreadLocal()367 ) |
990 | 0 | report_fatal_error("Bit set element may not be thread-local"); |
991 | 367 | if (367 isa<GlobalVariable>(GO) && 367 GO->hasSection()319 ) |
992 | 0 | report_fatal_error( |
993 | 0 | "A member of a type identifier may not have an explicit section"); |
994 | 367 | |
995 | 367 | // FIXME: We previously checked that global var member of a type identifier |
996 | 367 | // must be a definition, but the IR linker may leave type metadata on |
997 | 367 | // declarations. We should restore this check after fixing PR31759. |
998 | 367 | |
999 | 367 | auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0)); |
1000 | 367 | if (!OffsetConstMD) |
1001 | 0 | report_fatal_error("Type offset must be a constant"); |
1002 | 367 | auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue()); |
1003 | 367 | if (!OffsetInt) |
1004 | 0 | report_fatal_error("Type offset must be an integer constant"); |
1005 | 367 | } |
1006 | | |
1007 | | static const unsigned kX86JumpTableEntrySize = 8; |
1008 | | static const unsigned kARMJumpTableEntrySize = 4; |
1009 | | |
1010 | 72 | unsigned LowerTypeTestsModule::getJumpTableEntrySize() { |
1011 | 72 | switch (Arch) { |
1012 | 51 | case Triple::x86: |
1013 | 51 | case Triple::x86_64: |
1014 | 51 | return kX86JumpTableEntrySize; |
1015 | 21 | case Triple::arm: |
1016 | 21 | case Triple::thumb: |
1017 | 21 | case Triple::aarch64: |
1018 | 21 | return kARMJumpTableEntrySize; |
1019 | 0 | default: |
1020 | 0 | report_fatal_error("Unsupported architecture for jump tables"); |
1021 | 0 | } |
1022 | 0 | } |
1023 | | |
1024 | | // Create a jump table entry for the target. This consists of an instruction |
1025 | | // sequence containing a relative branch to Dest. Appends inline asm text, |
1026 | | // constraints and arguments to AsmOS, ConstraintOS and AsmArgs. |
1027 | | void LowerTypeTestsModule::createJumpTableEntry( |
1028 | | raw_ostream &AsmOS, raw_ostream &ConstraintOS, |
1029 | | Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs, |
1030 | 39 | Function *Dest) { |
1031 | 39 | unsigned ArgIndex = AsmArgs.size(); |
1032 | 39 | |
1033 | 39 | if (JumpTableArch == Triple::x86 || 39 JumpTableArch == Triple::x86_6433 ) { |
1034 | 26 | AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n"; |
1035 | 26 | AsmOS << "int3\nint3\nint3\n"; |
1036 | 39 | } else if (13 JumpTableArch == Triple::arm || 13 JumpTableArch == Triple::aarch647 ) { |
1037 | 9 | AsmOS << "b $" << ArgIndex << "\n"; |
1038 | 13 | } else if (4 JumpTableArch == Triple::thumb4 ) { |
1039 | 4 | AsmOS << "b.w $" << ArgIndex << "\n"; |
1040 | 4 | } else { |
1041 | 0 | report_fatal_error("Unsupported architecture for jump tables"); |
1042 | 0 | } |
1043 | 39 | |
1044 | 39 | ConstraintOS << (ArgIndex > 0 ? 39 ",s"15 : "s"24 ); |
1045 | 39 | AsmArgs.push_back(Dest); |
1046 | 39 | } |
1047 | | |
1048 | 24 | Type *LowerTypeTestsModule::getJumpTableEntryType() { |
1049 | 24 | return ArrayType::get(Int8Ty, getJumpTableEntrySize()); |
1050 | 24 | } |
1051 | | |
1052 | | /// Given a disjoint set of type identifiers and functions, build the bit sets |
1053 | | /// and lower the llvm.type.test calls, architecture dependently. |
1054 | | void LowerTypeTestsModule::buildBitSetsFromFunctions( |
1055 | 28 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { |
1056 | 28 | if (Arch == Triple::x86 || 28 Arch == Triple::x86_6424 || Arch == Triple::arm11 || |
1057 | 28 | Arch == Triple::thumb7 || Arch == Triple::aarch646 ) |
1058 | 24 | buildBitSetsFromFunctionsNative(TypeIds, Functions); |
1059 | 4 | else if (4 Arch == Triple::wasm32 || 4 Arch == Triple::wasm640 ) |
1060 | 4 | buildBitSetsFromFunctionsWASM(TypeIds, Functions); |
1061 | 4 | else |
1062 | 0 | report_fatal_error("Unsupported architecture for jump tables"); |
1063 | 28 | } |
1064 | | |
1065 | | void LowerTypeTestsModule::moveInitializerToModuleConstructor( |
1066 | 20 | GlobalVariable *GV) { |
1067 | 20 | if (WeakInitializerFn == nullptr20 ) { |
1068 | 4 | WeakInitializerFn = Function::Create( |
1069 | 4 | FunctionType::get(Type::getVoidTy(M.getContext()), |
1070 | 4 | /* IsVarArg */ false), |
1071 | 4 | GlobalValue::InternalLinkage, "__cfi_global_var_init", &M); |
1072 | 4 | BasicBlock *BB = |
1073 | 4 | BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn); |
1074 | 4 | ReturnInst::Create(M.getContext(), BB); |
1075 | 4 | WeakInitializerFn->setSection( |
1076 | 4 | ObjectFormat == Triple::MachO |
1077 | 0 | ? "__TEXT,__StaticInit,regular,pure_instructions" |
1078 | 4 | : ".text.startup"); |
1079 | 4 | // This code is equivalent to relocation application, and should run at the |
1080 | 4 | // earliest possible time (i.e. with the highest priority). |
1081 | 4 | appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0); |
1082 | 4 | } |
1083 | 20 | |
1084 | 20 | IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator()); |
1085 | 20 | GV->setConstant(false); |
1086 | 20 | IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlignment()); |
1087 | 20 | GV->setInitializer(Constant::getNullValue(GV->getValueType())); |
1088 | 20 | } |
1089 | | |
1090 | | void LowerTypeTestsModule::findGlobalVariableUsersOf( |
1091 | 30 | Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) { |
1092 | 57 | for (auto *U : C->users()){ |
1093 | 57 | if (auto *GV = dyn_cast<GlobalVariable>(U)) |
1094 | 24 | Out.insert(GV); |
1095 | 33 | else if (auto *33 C233 = dyn_cast<Constant>(U)) |
1096 | 24 | findGlobalVariableUsersOf(C2, Out); |
1097 | 57 | } |
1098 | 30 | } |
1099 | | |
1100 | | // Replace all uses of F with (F ? JT : 0). |
1101 | | void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr( |
1102 | 6 | Function *F, Constant *JT) { |
1103 | 6 | // The target expression can not appear in a constant initializer on most |
1104 | 6 | // (all?) targets. Switch to a runtime initializer. |
1105 | 6 | SmallSetVector<GlobalVariable *, 8> GlobalVarUsers; |
1106 | 6 | findGlobalVariableUsersOf(F, GlobalVarUsers); |
1107 | 6 | for (auto GV : GlobalVarUsers) |
1108 | 20 | moveInitializerToModuleConstructor(GV); |
1109 | 6 | |
1110 | 6 | // Can not RAUW F with an expression that uses F. Replace with a temporary |
1111 | 6 | // placeholder first. |
1112 | 6 | Function *PlaceholderFn = |
1113 | 6 | Function::Create(cast<FunctionType>(F->getValueType()), |
1114 | 6 | GlobalValue::ExternalWeakLinkage, "", &M); |
1115 | 6 | F->replaceAllUsesWith(PlaceholderFn); |
1116 | 6 | |
1117 | 6 | Constant *Target = ConstantExpr::getSelect( |
1118 | 6 | ConstantExpr::getICmp(CmpInst::ICMP_NE, F, |
1119 | 6 | Constant::getNullValue(F->getType())), |
1120 | 6 | JT, Constant::getNullValue(F->getType())); |
1121 | 6 | PlaceholderFn->replaceAllUsesWith(Target); |
1122 | 6 | PlaceholderFn->eraseFromParent(); |
1123 | 6 | } |
1124 | | |
1125 | 9 | static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) { |
1126 | 9 | Attribute TFAttr = F->getFnAttribute("target-features"); |
1127 | 9 | if (!TFAttr.hasAttribute(Attribute::None)9 ) { |
1128 | 5 | SmallVector<StringRef, 6> Features; |
1129 | 5 | TFAttr.getValueAsString().split(Features, ','); |
1130 | 5 | for (StringRef Feature : Features) { |
1131 | 5 | if (Feature == "-thumb-mode") |
1132 | 3 | return false; |
1133 | 2 | else if (2 Feature == "+thumb-mode"2 ) |
1134 | 2 | return true; |
1135 | 4 | } |
1136 | 5 | } |
1137 | 4 | |
1138 | 4 | return ModuleArch == Triple::thumb; |
1139 | 4 | } |
1140 | | |
1141 | | // Each jump table must be either ARM or Thumb as a whole for the bit-test math |
1142 | | // to work. Pick one that matches the majority of members to minimize interop |
1143 | | // veneers inserted by the linker. |
1144 | | static Triple::ArchType |
1145 | | selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions, |
1146 | 24 | Triple::ArchType ModuleArch) { |
1147 | 24 | if (ModuleArch != Triple::arm && 24 ModuleArch != Triple::thumb20 ) |
1148 | 19 | return ModuleArch; |
1149 | 5 | |
1150 | 5 | unsigned ArmCount = 0, ThumbCount = 0; |
1151 | 10 | for (const auto GTM : Functions) { |
1152 | 10 | if (!GTM->isDefinition()10 ) { |
1153 | 1 | // PLT stubs are always ARM. |
1154 | 1 | ++ArmCount; |
1155 | 1 | continue; |
1156 | 1 | } |
1157 | 9 | |
1158 | 9 | Function *F = cast<Function>(GTM->getGlobal()); |
1159 | 9 | ++(isThumbFunction(F, ModuleArch) ? ThumbCount4 : ArmCount5 ); |
1160 | 10 | } |
1161 | 5 | |
1162 | 5 | return ArmCount > ThumbCount ? Triple::arm3 : Triple::thumb2 ; |
1163 | 24 | } |
1164 | | |
1165 | | void LowerTypeTestsModule::createJumpTable( |
1166 | 24 | Function *F, ArrayRef<GlobalTypeMember *> Functions) { |
1167 | 24 | std::string AsmStr, ConstraintStr; |
1168 | 24 | raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr); |
1169 | 24 | SmallVector<Value *, 16> AsmArgs; |
1170 | 24 | AsmArgs.reserve(Functions.size() * 2); |
1171 | 24 | |
1172 | 24 | Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch); |
1173 | 24 | |
1174 | 63 | for (unsigned I = 0; I != Functions.size()63 ; ++I39 ) |
1175 | 39 | createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs, |
1176 | 39 | cast<Function>(Functions[I]->getGlobal())); |
1177 | 24 | |
1178 | 24 | // Try to emit the jump table at the end of the text segment. |
1179 | 24 | // Jump table must come after __cfi_check in the cross-dso mode. |
1180 | 24 | // FIXME: this magic section name seems to do the trick. |
1181 | 24 | F->setSection(ObjectFormat == Triple::MachO |
1182 | 0 | ? "__TEXT,__text,regular,pure_instructions" |
1183 | 24 | : ".text.cfi"); |
1184 | 24 | // Align the whole table by entry size. |
1185 | 24 | F->setAlignment(getJumpTableEntrySize()); |
1186 | 24 | // Skip prologue. |
1187 | 24 | // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3. |
1188 | 24 | // Luckily, this function does not get any prologue even without the |
1189 | 24 | // attribute. |
1190 | 24 | if (OS != Triple::Win32) |
1191 | 22 | F->addFnAttr(llvm::Attribute::Naked); |
1192 | 24 | if (JumpTableArch == Triple::arm) |
1193 | 3 | F->addFnAttr("target-features", "-thumb-mode"); |
1194 | 24 | if (JumpTableArch == Triple::thumb24 ) { |
1195 | 2 | F->addFnAttr("target-features", "+thumb-mode"); |
1196 | 2 | // Thumb jump table assembly needs Thumb2. The following attribute is added |
1197 | 2 | // by Clang for -march=armv7. |
1198 | 2 | F->addFnAttr("target-cpu", "cortex-a8"); |
1199 | 2 | } |
1200 | 24 | |
1201 | 24 | BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F); |
1202 | 24 | IRBuilder<> IRB(BB); |
1203 | 24 | |
1204 | 24 | SmallVector<Type *, 16> ArgTypes; |
1205 | 24 | ArgTypes.reserve(AsmArgs.size()); |
1206 | 24 | for (const auto &Arg : AsmArgs) |
1207 | 39 | ArgTypes.push_back(Arg->getType()); |
1208 | 24 | InlineAsm *JumpTableAsm = |
1209 | 24 | InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false), |
1210 | 24 | AsmOS.str(), ConstraintOS.str(), |
1211 | 24 | /*hasSideEffects=*/true); |
1212 | 24 | |
1213 | 24 | IRB.CreateCall(JumpTableAsm, AsmArgs); |
1214 | 24 | IRB.CreateUnreachable(); |
1215 | 24 | } |
1216 | | |
1217 | | /// Given a disjoint set of type identifiers and functions, build a jump table |
1218 | | /// for the functions, build the bit sets and lower the llvm.type.test calls. |
1219 | | void LowerTypeTestsModule::buildBitSetsFromFunctionsNative( |
1220 | 24 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { |
1221 | 24 | // Unlike the global bitset builder, the function bitset builder cannot |
1222 | 24 | // re-arrange functions in a particular order and base its calculations on the |
1223 | 24 | // layout of the functions' entry points, as we have no idea how large a |
1224 | 24 | // particular function will end up being (the size could even depend on what |
1225 | 24 | // this pass does!) Instead, we build a jump table, which is a block of code |
1226 | 24 | // consisting of one branch instruction for each of the functions in the bit |
1227 | 24 | // set that branches to the target function, and redirect any taken function |
1228 | 24 | // addresses to the corresponding jump table entry. In the object file's |
1229 | 24 | // symbol table, the symbols for the target functions also refer to the jump |
1230 | 24 | // table entries, so that addresses taken outside the module will pass any |
1231 | 24 | // verification done inside the module. |
1232 | 24 | // |
1233 | 24 | // In more concrete terms, suppose we have three functions f, g, h which are |
1234 | 24 | // of the same type, and a function foo that returns their addresses: |
1235 | 24 | // |
1236 | 24 | // f: |
1237 | 24 | // mov 0, %eax |
1238 | 24 | // ret |
1239 | 24 | // |
1240 | 24 | // g: |
1241 | 24 | // mov 1, %eax |
1242 | 24 | // ret |
1243 | 24 | // |
1244 | 24 | // h: |
1245 | 24 | // mov 2, %eax |
1246 | 24 | // ret |
1247 | 24 | // |
1248 | 24 | // foo: |
1249 | 24 | // mov f, %eax |
1250 | 24 | // mov g, %edx |
1251 | 24 | // mov h, %ecx |
1252 | 24 | // ret |
1253 | 24 | // |
1254 | 24 | // We output the jump table as module-level inline asm string. The end result |
1255 | 24 | // will (conceptually) look like this: |
1256 | 24 | // |
1257 | 24 | // f = .cfi.jumptable |
1258 | 24 | // g = .cfi.jumptable + 4 |
1259 | 24 | // h = .cfi.jumptable + 8 |
1260 | 24 | // .cfi.jumptable: |
1261 | 24 | // jmp f.cfi ; 5 bytes |
1262 | 24 | // int3 ; 1 byte |
1263 | 24 | // int3 ; 1 byte |
1264 | 24 | // int3 ; 1 byte |
1265 | 24 | // jmp g.cfi ; 5 bytes |
1266 | 24 | // int3 ; 1 byte |
1267 | 24 | // int3 ; 1 byte |
1268 | 24 | // int3 ; 1 byte |
1269 | 24 | // jmp h.cfi ; 5 bytes |
1270 | 24 | // int3 ; 1 byte |
1271 | 24 | // int3 ; 1 byte |
1272 | 24 | // int3 ; 1 byte |
1273 | 24 | // |
1274 | 24 | // f.cfi: |
1275 | 24 | // mov 0, %eax |
1276 | 24 | // ret |
1277 | 24 | // |
1278 | 24 | // g.cfi: |
1279 | 24 | // mov 1, %eax |
1280 | 24 | // ret |
1281 | 24 | // |
1282 | 24 | // h.cfi: |
1283 | 24 | // mov 2, %eax |
1284 | 24 | // ret |
1285 | 24 | // |
1286 | 24 | // foo: |
1287 | 24 | // mov f, %eax |
1288 | 24 | // mov g, %edx |
1289 | 24 | // mov h, %ecx |
1290 | 24 | // ret |
1291 | 24 | // |
1292 | 24 | // Because the addresses of f, g, h are evenly spaced at a power of 2, in the |
1293 | 24 | // normal case the check can be carried out using the same kind of simple |
1294 | 24 | // arithmetic that we normally use for globals. |
1295 | 24 | |
1296 | 24 | // FIXME: find a better way to represent the jumptable in the IR. |
1297 | 24 | assert(!Functions.empty()); |
1298 | 24 | |
1299 | 24 | // Build a simple layout based on the regular layout of jump tables. |
1300 | 24 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; |
1301 | 24 | unsigned EntrySize = getJumpTableEntrySize(); |
1302 | 63 | for (unsigned I = 0; I != Functions.size()63 ; ++I39 ) |
1303 | 39 | GlobalLayout[Functions[I]] = I * EntrySize; |
1304 | 24 | |
1305 | 24 | Function *JumpTableFn = |
1306 | 24 | Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()), |
1307 | 24 | /* IsVarArg */ false), |
1308 | 24 | GlobalValue::PrivateLinkage, ".cfi.jumptable", &M); |
1309 | 24 | ArrayType *JumpTableType = |
1310 | 24 | ArrayType::get(getJumpTableEntryType(), Functions.size()); |
1311 | 24 | auto JumpTable = |
1312 | 24 | ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0)); |
1313 | 24 | |
1314 | 24 | lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout); |
1315 | 24 | |
1316 | 24 | // Build aliases pointing to offsets into the jump table, and replace |
1317 | 24 | // references to the original functions with references to the aliases. |
1318 | 63 | for (unsigned I = 0; I != Functions.size()63 ; ++I39 ) { |
1319 | 39 | Function *F = cast<Function>(Functions[I]->getGlobal()); |
1320 | 39 | bool IsDefinition = Functions[I]->isDefinition(); |
1321 | 39 | |
1322 | 39 | Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast( |
1323 | 39 | ConstantExpr::getInBoundsGetElementPtr( |
1324 | 39 | JumpTableType, JumpTable, |
1325 | 39 | ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0), |
1326 | 39 | ConstantInt::get(IntPtrTy, I)}), |
1327 | 39 | F->getType()); |
1328 | 39 | if (Functions[I]->isExported()39 ) { |
1329 | 11 | if (IsDefinition11 ) { |
1330 | 7 | ExportSummary->cfiFunctionDefs().insert(F->getName()); |
1331 | 11 | } else { |
1332 | 4 | GlobalAlias *JtAlias = GlobalAlias::create( |
1333 | 4 | F->getValueType(), 0, GlobalValue::ExternalLinkage, |
1334 | 4 | F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M); |
1335 | 4 | JtAlias->setVisibility(GlobalValue::HiddenVisibility); |
1336 | 4 | ExportSummary->cfiFunctionDecls().insert(F->getName()); |
1337 | 4 | } |
1338 | 11 | } |
1339 | 39 | if (!IsDefinition39 ) { |
1340 | 9 | if (F->isWeakForLinker()) |
1341 | 5 | replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr); |
1342 | 9 | else |
1343 | 4 | F->replaceAllUsesWith(CombinedGlobalElemPtr); |
1344 | 39 | } else { |
1345 | 30 | assert(F->getType()->getAddressSpace() == 0); |
1346 | 30 | |
1347 | 30 | GlobalAlias *FAlias = GlobalAlias::create( |
1348 | 30 | F->getValueType(), 0, F->getLinkage(), "", CombinedGlobalElemPtr, &M); |
1349 | 30 | FAlias->setVisibility(F->getVisibility()); |
1350 | 30 | FAlias->takeName(F); |
1351 | 30 | if (FAlias->hasName()) |
1352 | 30 | F->setName(FAlias->getName() + ".cfi"); |
1353 | 30 | F->replaceAllUsesWith(FAlias); |
1354 | 30 | } |
1355 | 39 | if (!F->isDeclarationForLinker()) |
1356 | 24 | F->setLinkage(GlobalValue::InternalLinkage); |
1357 | 39 | } |
1358 | 24 | |
1359 | 24 | createJumpTable(JumpTableFn, Functions); |
1360 | 24 | } |
1361 | | |
1362 | | /// Assign a dummy layout using an incrementing counter, tag each function |
1363 | | /// with its index represented as metadata, and lower each type test to an |
1364 | | /// integer range comparison. During generation of the indirect function call |
1365 | | /// table in the backend, it will assign the given indexes. |
1366 | | /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet |
1367 | | /// been finalized. |
1368 | | void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM( |
1369 | 4 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { |
1370 | 4 | assert(!Functions.empty()); |
1371 | 4 | |
1372 | 4 | // Build consecutive monotonic integer ranges for each call target set |
1373 | 4 | DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; |
1374 | 4 | |
1375 | 5 | for (GlobalTypeMember *GTM : Functions) { |
1376 | 5 | Function *F = cast<Function>(GTM->getGlobal()); |
1377 | 5 | |
1378 | 5 | // Skip functions that are not address taken, to avoid bloating the table |
1379 | 5 | if (!F->hasAddressTaken()) |
1380 | 1 | continue; |
1381 | 4 | |
1382 | 4 | // Store metadata with the index for each function |
1383 | 4 | MDNode *MD = MDNode::get(F->getContext(), |
1384 | 4 | ArrayRef<Metadata *>(ConstantAsMetadata::get( |
1385 | 4 | ConstantInt::get(Int64Ty, IndirectIndex)))); |
1386 | 4 | F->setMetadata("wasm.index", MD); |
1387 | 4 | |
1388 | 4 | // Assign the counter value |
1389 | 4 | GlobalLayout[GTM] = IndirectIndex++; |
1390 | 4 | } |
1391 | 4 | |
1392 | 4 | // The indirect function table index space starts at zero, so pass a NULL |
1393 | 4 | // pointer as the subtracted "jump table" offset. |
1394 | 4 | lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy), |
1395 | 4 | GlobalLayout); |
1396 | 4 | } |
1397 | | |
1398 | | void LowerTypeTestsModule::buildBitSetsFromDisjointSet( |
1399 | 49 | ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) { |
1400 | 49 | llvm::DenseMap<Metadata *, uint64_t> TypeIdIndices; |
1401 | 112 | for (unsigned I = 0; I != TypeIds.size()112 ; ++I63 ) |
1402 | 63 | TypeIdIndices[TypeIds[I]] = I; |
1403 | 49 | |
1404 | 49 | // For each type identifier, build a set of indices that refer to members of |
1405 | 49 | // the type identifier. |
1406 | 49 | std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size()); |
1407 | 49 | unsigned GlobalIndex = 0; |
1408 | 77 | for (GlobalTypeMember *GTM : Globals) { |
1409 | 359 | for (MDNode *Type : GTM->types()) { |
1410 | 359 | // Type = { offset, type identifier } |
1411 | 359 | unsigned TypeIdIndex = TypeIdIndices[Type->getOperand(1)]; |
1412 | 359 | TypeMembers[TypeIdIndex].insert(GlobalIndex); |
1413 | 359 | } |
1414 | 77 | GlobalIndex++; |
1415 | 77 | } |
1416 | 49 | |
1417 | 49 | // Order the sets of indices by size. The GlobalLayoutBuilder works best |
1418 | 49 | // when given small index sets first. |
1419 | 49 | std::stable_sort( |
1420 | 49 | TypeMembers.begin(), TypeMembers.end(), |
1421 | 15 | [](const std::set<uint64_t> &O1, const std::set<uint64_t> &O2) { |
1422 | 15 | return O1.size() < O2.size(); |
1423 | 15 | }); |
1424 | 49 | |
1425 | 49 | // Create a GlobalLayoutBuilder and provide it with index sets as layout |
1426 | 49 | // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as |
1427 | 49 | // close together as possible. |
1428 | 49 | GlobalLayoutBuilder GLB(Globals.size()); |
1429 | 49 | for (auto &&MemSet : TypeMembers) |
1430 | 63 | GLB.addFragment(MemSet); |
1431 | 49 | |
1432 | 49 | // Build the bitsets from this disjoint set. |
1433 | 49 | if (Globals.empty() || 49 isa<GlobalVariable>(Globals[0]->getGlobal())47 ) { |
1434 | 21 | // Build a vector of global variables with the computed layout. |
1435 | 21 | std::vector<GlobalTypeMember *> OrderedGVs(Globals.size()); |
1436 | 21 | auto OGI = OrderedGVs.begin(); |
1437 | 56 | for (auto &&F : GLB.Fragments) { |
1438 | 33 | for (auto &&Offset : F) { |
1439 | 33 | auto GV = dyn_cast<GlobalVariable>(Globals[Offset]->getGlobal()); |
1440 | 33 | if (!GV) |
1441 | 0 | report_fatal_error("Type identifier may not contain both global " |
1442 | 0 | "variables and functions"); |
1443 | 33 | *OGI++ = Globals[Offset]; |
1444 | 33 | } |
1445 | 56 | } |
1446 | 21 | |
1447 | 21 | buildBitSetsFromGlobalVariables(TypeIds, OrderedGVs); |
1448 | 49 | } else { |
1449 | 28 | // Build a vector of functions with the computed layout. |
1450 | 28 | std::vector<GlobalTypeMember *> OrderedFns(Globals.size()); |
1451 | 28 | auto OFI = OrderedFns.begin(); |
1452 | 56 | for (auto &&F : GLB.Fragments) { |
1453 | 44 | for (auto &&Offset : F) { |
1454 | 44 | auto Fn = dyn_cast<Function>(Globals[Offset]->getGlobal()); |
1455 | 44 | if (!Fn) |
1456 | 0 | report_fatal_error("Type identifier may not contain both global " |
1457 | 0 | "variables and functions"); |
1458 | 44 | *OFI++ = Globals[Offset]; |
1459 | 44 | } |
1460 | 56 | } |
1461 | 28 | |
1462 | 28 | buildBitSetsFromFunctions(TypeIds, OrderedFns); |
1463 | 28 | } |
1464 | 49 | } |
1465 | | |
1466 | | /// Lower all type tests in this module. |
1467 | | LowerTypeTestsModule::LowerTypeTestsModule( |
1468 | | Module &M, ModuleSummaryIndex *ExportSummary, |
1469 | | const ModuleSummaryIndex *ImportSummary) |
1470 | 386 | : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) { |
1471 | 386 | assert(!(ExportSummary && ImportSummary)); |
1472 | 386 | Triple TargetTriple(M.getTargetTriple()); |
1473 | 386 | Arch = TargetTriple.getArch(); |
1474 | 386 | OS = TargetTriple.getOS(); |
1475 | 386 | ObjectFormat = TargetTriple.getObjectFormat(); |
1476 | 386 | } |
1477 | | |
1478 | 44 | bool LowerTypeTestsModule::runForTesting(Module &M) { |
1479 | 44 | ModuleSummaryIndex Summary; |
1480 | 44 | |
1481 | 44 | // Handle the command-line summary arguments. This code is for testing |
1482 | 44 | // purposes only, so we handle errors directly. |
1483 | 44 | if (!ClReadSummary.empty()44 ) { |
1484 | 16 | ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary + |
1485 | 16 | ": "); |
1486 | 16 | auto ReadSummaryFile = |
1487 | 16 | ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary))); |
1488 | 16 | |
1489 | 16 | yaml::Input In(ReadSummaryFile->getBuffer()); |
1490 | 16 | In >> Summary; |
1491 | 16 | ExitOnErr(errorCodeToError(In.error())); |
1492 | 16 | } |
1493 | 44 | |
1494 | 44 | bool Changed = |
1495 | 44 | LowerTypeTestsModule( |
1496 | 44 | M, ClSummaryAction == PassSummaryAction::Export ? &Summary12 : nullptr32 , |
1497 | 44 | ClSummaryAction == PassSummaryAction::Import ? &Summary6 : nullptr38 ) |
1498 | 44 | .lower(); |
1499 | 44 | |
1500 | 44 | if (!ClWriteSummary.empty()44 ) { |
1501 | 12 | ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary + |
1502 | 12 | ": "); |
1503 | 12 | std::error_code EC; |
1504 | 12 | raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text); |
1505 | 12 | ExitOnErr(errorCodeToError(EC)); |
1506 | 12 | |
1507 | 12 | yaml::Output Out(OS); |
1508 | 12 | Out << Summary; |
1509 | 12 | } |
1510 | 44 | |
1511 | 44 | return Changed; |
1512 | 44 | } |
1513 | | |
1514 | 385 | bool LowerTypeTestsModule::lower() { |
1515 | 385 | Function *TypeTestFunc = |
1516 | 385 | M.getFunction(Intrinsic::getName(Intrinsic::type_test)); |
1517 | 385 | if ((!TypeTestFunc || 385 TypeTestFunc->use_empty()47 ) && !ExportSummary339 && |
1518 | 158 | !ImportSummary) |
1519 | 43 | return false; |
1520 | 342 | |
1521 | 342 | if (342 ImportSummary342 ) { |
1522 | 135 | if (TypeTestFunc135 ) { |
1523 | 19 | for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end(); |
1524 | 51 | UI != UE51 ;) { |
1525 | 32 | auto *CI = cast<CallInst>((*UI++).getUser()); |
1526 | 32 | importTypeTest(CI); |
1527 | 32 | } |
1528 | 19 | } |
1529 | 135 | |
1530 | 135 | SmallVector<Function *, 8> Defs; |
1531 | 135 | SmallVector<Function *, 8> Decls; |
1532 | 327 | for (auto &F : M) { |
1533 | 327 | // CFI functions are either external, or promoted. A local function may |
1534 | 327 | // have the same name, but it's not the one we are looking for. |
1535 | 327 | if (F.hasLocalLinkage()) |
1536 | 33 | continue; |
1537 | 294 | if (294 ImportSummary->cfiFunctionDefs().count(F.getName())294 ) |
1538 | 4 | Defs.push_back(&F); |
1539 | 290 | else if (290 ImportSummary->cfiFunctionDecls().count(F.getName())290 ) |
1540 | 4 | Decls.push_back(&F); |
1541 | 327 | } |
1542 | 135 | |
1543 | 135 | for (auto F : Defs) |
1544 | 4 | importFunction(F, /*isDefinition*/ true); |
1545 | 135 | for (auto F : Decls) |
1546 | 4 | importFunction(F, /*isDefinition*/ false); |
1547 | 135 | |
1548 | 135 | return true; |
1549 | 135 | } |
1550 | 207 | |
1551 | 207 | // Equivalence class set containing type identifiers and the globals that |
1552 | 207 | // reference them. This is used to partition the set of type identifiers in |
1553 | 207 | // the module into disjoint sets. |
1554 | 207 | typedef EquivalenceClasses<PointerUnion<GlobalTypeMember *, Metadata *>> |
1555 | 207 | GlobalClassesTy; |
1556 | 207 | GlobalClassesTy GlobalClasses; |
1557 | 207 | |
1558 | 207 | // Verify the type metadata and build a few data structures to let us |
1559 | 207 | // efficiently enumerate the type identifiers associated with a global: |
1560 | 207 | // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector |
1561 | 207 | // of associated type metadata) and a mapping from type identifiers to their |
1562 | 207 | // list of GlobalTypeMembers and last observed index in the list of globals. |
1563 | 207 | // The indices will be used later to deterministically order the list of type |
1564 | 207 | // identifiers. |
1565 | 207 | BumpPtrAllocator Alloc; |
1566 | 207 | struct TIInfo { |
1567 | 207 | unsigned Index; |
1568 | 207 | std::vector<GlobalTypeMember *> RefGlobals; |
1569 | 207 | }; |
1570 | 207 | llvm::DenseMap<Metadata *, TIInfo> TypeIdInfo; |
1571 | 207 | unsigned I = 0; |
1572 | 207 | SmallVector<MDNode *, 2> Types; |
1573 | 207 | |
1574 | 207 | struct ExportedFunctionInfo { |
1575 | 207 | CfiFunctionLinkage Linkage; |
1576 | 207 | MDNode *FuncMD; // {name, linkage, type[, type...]} |
1577 | 207 | }; |
1578 | 207 | DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions; |
1579 | 207 | if (ExportSummary207 ) { |
1580 | 183 | NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions"); |
1581 | 183 | if (CfiFunctionsMD183 ) { |
1582 | 17 | for (auto FuncMD : CfiFunctionsMD->operands()) { |
1583 | 17 | assert(FuncMD->getNumOperands() >= 2); |
1584 | 17 | StringRef FunctionName = |
1585 | 17 | cast<MDString>(FuncMD->getOperand(0))->getString(); |
1586 | 17 | if (!ExportSummary->isGUIDLive(GlobalValue::getGUID( |
1587 | 17 | GlobalValue::dropLLVMManglingEscape(FunctionName)))) |
1588 | 0 | continue; |
1589 | 17 | CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>( |
1590 | 17 | cast<ConstantAsMetadata>(FuncMD->getOperand(1)) |
1591 | 17 | ->getValue() |
1592 | 17 | ->getUniqueInteger() |
1593 | 17 | .getZExtValue()); |
1594 | 17 | auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}}); |
1595 | 17 | if (!P.second && 17 P.first->second.Linkage != CFL_Definition2 ) |
1596 | 2 | P.first->second = {Linkage, FuncMD}; |
1597 | 17 | } |
1598 | 5 | |
1599 | 15 | for (const auto &P : ExportedFunctions) { |
1600 | 15 | StringRef FunctionName = P.first; |
1601 | 15 | CfiFunctionLinkage Linkage = P.second.Linkage; |
1602 | 15 | MDNode *FuncMD = P.second.FuncMD; |
1603 | 15 | Function *F = M.getFunction(FunctionName); |
1604 | 15 | if (!F) |
1605 | 11 | F = Function::Create( |
1606 | 11 | FunctionType::get(Type::getVoidTy(M.getContext()), false), |
1607 | 11 | GlobalVariable::ExternalLinkage, FunctionName, &M); |
1608 | 15 | |
1609 | 15 | // If the function is available_externally, remove its definition so |
1610 | 15 | // that it is handled the same way as a declaration. Later we will try |
1611 | 15 | // to create an alias using this function's linkage, which will fail if |
1612 | 15 | // the linkage is available_externally. This will also result in us |
1613 | 15 | // following the code path below to replace the type metadata. |
1614 | 15 | if (F->hasAvailableExternallyLinkage()15 ) { |
1615 | 1 | F->setLinkage(GlobalValue::ExternalLinkage); |
1616 | 1 | F->deleteBody(); |
1617 | 1 | F->setComdat(nullptr); |
1618 | 1 | F->clearMetadata(); |
1619 | 1 | } |
1620 | 15 | |
1621 | 15 | // If the function in the full LTO module is a declaration, replace its |
1622 | 15 | // type metadata with the type metadata we found in cfi.functions. That |
1623 | 15 | // metadata is presumed to be more accurate than the metadata attached |
1624 | 15 | // to the declaration. |
1625 | 15 | if (F->isDeclaration()15 ) { |
1626 | 13 | if (Linkage == CFL_WeakDeclaration) |
1627 | 1 | F->setLinkage(GlobalValue::ExternalWeakLinkage); |
1628 | 13 | |
1629 | 13 | F->eraseMetadata(LLVMContext::MD_type); |
1630 | 26 | for (unsigned I = 2; I < FuncMD->getNumOperands()26 ; ++I13 ) |
1631 | 13 | F->addMetadata(LLVMContext::MD_type, |
1632 | 13 | *cast<MDNode>(FuncMD->getOperand(I).get())); |
1633 | 13 | } |
1634 | 15 | } |
1635 | 5 | } |
1636 | 183 | } |
1637 | 207 | |
1638 | 478 | for (GlobalObject &GO : M.global_objects()) { |
1639 | 478 | if (isa<GlobalVariable>(GO) && 478 GO.isDeclarationForLinker()121 ) |
1640 | 15 | continue; |
1641 | 463 | |
1642 | 463 | Types.clear(); |
1643 | 463 | GO.getMetadata(LLVMContext::MD_type, Types); |
1644 | 463 | if (Types.empty()) |
1645 | 378 | continue; |
1646 | 85 | |
1647 | 85 | bool IsDefinition = !GO.isDeclarationForLinker(); |
1648 | 85 | bool IsExported = false; |
1649 | 85 | if (isa<Function>(GO) && 85 ExportedFunctions.count(GO.getName())48 ) { |
1650 | 15 | IsDefinition |= ExportedFunctions[GO.getName()].Linkage == CFL_Definition; |
1651 | 15 | IsExported = true; |
1652 | 15 | } |
1653 | 85 | |
1654 | 85 | auto *GTM = |
1655 | 85 | GlobalTypeMember::create(Alloc, &GO, IsDefinition, IsExported, Types); |
1656 | 367 | for (MDNode *Type : Types) { |
1657 | 367 | verifyTypeMDNode(&GO, Type); |
1658 | 367 | auto &Info = TypeIdInfo[cast<MDNode>(Type)->getOperand(1)]; |
1659 | 367 | Info.Index = ++I; |
1660 | 367 | Info.RefGlobals.push_back(GTM); |
1661 | 367 | } |
1662 | 478 | } |
1663 | 207 | |
1664 | 69 | auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & { |
1665 | 69 | // Add the call site to the list of call sites for this type identifier. We |
1666 | 69 | // also use TypeIdUsers to keep track of whether we have seen this type |
1667 | 69 | // identifier before. If we have, we don't need to re-add the referenced |
1668 | 69 | // globals to the equivalence class. |
1669 | 69 | auto Ins = TypeIdUsers.insert({TypeId, {}}); |
1670 | 69 | if (Ins.second69 ) { |
1671 | 63 | // Add the type identifier to the equivalence class. |
1672 | 63 | GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId); |
1673 | 63 | GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); |
1674 | 63 | |
1675 | 63 | // Add the referenced globals to the type identifier's equivalence class. |
1676 | 63 | for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals) |
1677 | 359 | CurSet = GlobalClasses.unionSets( |
1678 | 359 | CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM))); |
1679 | 63 | } |
1680 | 69 | |
1681 | 69 | return Ins.first->second; |
1682 | 69 | }; |
1683 | 207 | |
1684 | 207 | if (TypeTestFunc207 ) { |
1685 | 45 | for (const Use &U : TypeTestFunc->uses()) { |
1686 | 45 | auto CI = cast<CallInst>(U.getUser()); |
1687 | 45 | |
1688 | 45 | auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); |
1689 | 45 | if (!TypeIdMDVal) |
1690 | 0 | report_fatal_error("Second argument of llvm.type.test must be metadata"); |
1691 | 45 | auto TypeId = TypeIdMDVal->getMetadata(); |
1692 | 45 | AddTypeIdUse(TypeId).CallSites.push_back(CI); |
1693 | 45 | } |
1694 | 28 | } |
1695 | 207 | |
1696 | 207 | if (207 ExportSummary207 ) { |
1697 | 183 | DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID; |
1698 | 32 | for (auto &P : TypeIdInfo) { |
1699 | 32 | if (auto *TypeId = dyn_cast<MDString>(P.first)) |
1700 | 32 | MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back( |
1701 | 32 | TypeId); |
1702 | 32 | } |
1703 | 183 | |
1704 | 75 | for (auto &P : *ExportSummary) { |
1705 | 58 | for (auto &S : P.second.SummaryList) { |
1706 | 58 | if (!ExportSummary->isGlobalValueLive(S.get())) |
1707 | 10 | continue; |
1708 | 48 | if (auto *48 FS48 = dyn_cast<FunctionSummary>(S->getBaseObject())) |
1709 | 43 | for (GlobalValue::GUID G : FS->type_tests()) |
1710 | 27 | for (Metadata *MD : MetadataByGUID[G]) |
1711 | 24 | AddTypeIdUse(MD).IsExported = true; |
1712 | 58 | } |
1713 | 75 | } |
1714 | 183 | } |
1715 | 207 | |
1716 | 207 | if (GlobalClasses.empty()) |
1717 | 167 | return false; |
1718 | 40 | |
1719 | 40 | // Build a list of disjoint sets ordered by their maximum global index for |
1720 | 40 | // determinism. |
1721 | 40 | std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets; |
1722 | 40 | for (GlobalClassesTy::iterator I = GlobalClasses.begin(), |
1723 | 40 | E = GlobalClasses.end(); |
1724 | 180 | I != E180 ; ++I140 ) { |
1725 | 140 | if (!I->isLeader()) |
1726 | 91 | continue; |
1727 | 49 | ++NumTypeIdDisjointSets; |
1728 | 49 | |
1729 | 49 | unsigned MaxIndex = 0; |
1730 | 49 | for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); |
1731 | 189 | MI != GlobalClasses.member_end()189 ; ++MI140 ) { |
1732 | 140 | if ((*MI).is<Metadata *>()) |
1733 | 63 | MaxIndex = std::max(MaxIndex, TypeIdInfo[MI->get<Metadata *>()].Index); |
1734 | 140 | } |
1735 | 140 | Sets.emplace_back(I, MaxIndex); |
1736 | 140 | } |
1737 | 40 | std::sort(Sets.begin(), Sets.end(), |
1738 | 40 | [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1, |
1739 | 6 | const std::pair<GlobalClassesTy::iterator, unsigned> &S2) { |
1740 | 6 | return S1.second < S2.second; |
1741 | 6 | }); |
1742 | 40 | |
1743 | 40 | // For each disjoint set we found... |
1744 | 49 | for (const auto &S : Sets) { |
1745 | 49 | // Build the list of type identifiers in this disjoint set. |
1746 | 49 | std::vector<Metadata *> TypeIds; |
1747 | 49 | std::vector<GlobalTypeMember *> Globals; |
1748 | 49 | for (GlobalClassesTy::member_iterator MI = |
1749 | 49 | GlobalClasses.member_begin(S.first); |
1750 | 189 | MI != GlobalClasses.member_end()189 ; ++MI140 ) { |
1751 | 140 | if ((*MI).is<Metadata *>()) |
1752 | 63 | TypeIds.push_back(MI->get<Metadata *>()); |
1753 | 140 | else |
1754 | 77 | Globals.push_back(MI->get<GlobalTypeMember *>()); |
1755 | 140 | } |
1756 | 49 | |
1757 | 49 | // Order type identifiers by global index for determinism. This ordering is |
1758 | 49 | // stable as there is a one-to-one mapping between metadata and indices. |
1759 | 18 | std::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) { |
1760 | 18 | return TypeIdInfo[M1].Index < TypeIdInfo[M2].Index; |
1761 | 18 | }); |
1762 | 49 | |
1763 | 49 | // Build bitsets for this disjoint set. |
1764 | 49 | buildBitSetsFromDisjointSet(TypeIds, Globals); |
1765 | 49 | } |
1766 | 385 | |
1767 | 385 | allocateByteArrays(); |
1768 | 385 | |
1769 | 385 | return true; |
1770 | 385 | } |
1771 | | |
1772 | | PreservedAnalyses LowerTypeTestsPass::run(Module &M, |
1773 | 1 | ModuleAnalysisManager &AM) { |
1774 | 1 | bool Changed = LowerTypeTestsModule(M, /*ExportSummary=*/nullptr, |
1775 | 1 | /*ImportSummary=*/nullptr) |
1776 | 1 | .lower(); |
1777 | 1 | if (!Changed) |
1778 | 0 | return PreservedAnalyses::all(); |
1779 | 1 | return PreservedAnalyses::none(); |
1780 | 1 | } |