Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/IPO/LowerTypeTests.cpp
Warning:line 1561, column 11
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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