Bug Summary

File:llvm/lib/Transforms/IPO/LowerTypeTests.cpp
Warning:line 1519, column 11
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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