106f32e7eSjoerg //===- LowerTypeTests.cpp - type metadata lowering pass -------------------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This pass lowers type metadata and calls to the llvm.type.test intrinsic.
1006f32e7eSjoerg // It also ensures that globals are properly laid out for the
1106f32e7eSjoerg // llvm.icall.branch.funnel intrinsic.
1206f32e7eSjoerg // See http://llvm.org/docs/TypeMetadata.html for more information.
1306f32e7eSjoerg //
1406f32e7eSjoerg //===----------------------------------------------------------------------===//
1506f32e7eSjoerg
1606f32e7eSjoerg #include "llvm/Transforms/IPO/LowerTypeTests.h"
1706f32e7eSjoerg #include "llvm/ADT/APInt.h"
1806f32e7eSjoerg #include "llvm/ADT/ArrayRef.h"
1906f32e7eSjoerg #include "llvm/ADT/DenseMap.h"
2006f32e7eSjoerg #include "llvm/ADT/EquivalenceClasses.h"
2106f32e7eSjoerg #include "llvm/ADT/PointerUnion.h"
2206f32e7eSjoerg #include "llvm/ADT/SetVector.h"
2306f32e7eSjoerg #include "llvm/ADT/SmallVector.h"
2406f32e7eSjoerg #include "llvm/ADT/Statistic.h"
2506f32e7eSjoerg #include "llvm/ADT/StringRef.h"
2606f32e7eSjoerg #include "llvm/ADT/TinyPtrVector.h"
2706f32e7eSjoerg #include "llvm/ADT/Triple.h"
2806f32e7eSjoerg #include "llvm/Analysis/TypeMetadataUtils.h"
2906f32e7eSjoerg #include "llvm/Analysis/ValueTracking.h"
3006f32e7eSjoerg #include "llvm/IR/Attributes.h"
3106f32e7eSjoerg #include "llvm/IR/BasicBlock.h"
3206f32e7eSjoerg #include "llvm/IR/Constant.h"
3306f32e7eSjoerg #include "llvm/IR/Constants.h"
3406f32e7eSjoerg #include "llvm/IR/DataLayout.h"
3506f32e7eSjoerg #include "llvm/IR/DerivedTypes.h"
3606f32e7eSjoerg #include "llvm/IR/Function.h"
3706f32e7eSjoerg #include "llvm/IR/GlobalAlias.h"
3806f32e7eSjoerg #include "llvm/IR/GlobalObject.h"
3906f32e7eSjoerg #include "llvm/IR/GlobalValue.h"
4006f32e7eSjoerg #include "llvm/IR/GlobalVariable.h"
4106f32e7eSjoerg #include "llvm/IR/IRBuilder.h"
4206f32e7eSjoerg #include "llvm/IR/InlineAsm.h"
4306f32e7eSjoerg #include "llvm/IR/Instruction.h"
4406f32e7eSjoerg #include "llvm/IR/Instructions.h"
4506f32e7eSjoerg #include "llvm/IR/Intrinsics.h"
4606f32e7eSjoerg #include "llvm/IR/LLVMContext.h"
4706f32e7eSjoerg #include "llvm/IR/Metadata.h"
4806f32e7eSjoerg #include "llvm/IR/Module.h"
4906f32e7eSjoerg #include "llvm/IR/ModuleSummaryIndex.h"
5006f32e7eSjoerg #include "llvm/IR/ModuleSummaryIndexYAML.h"
5106f32e7eSjoerg #include "llvm/IR/Operator.h"
5206f32e7eSjoerg #include "llvm/IR/PassManager.h"
5306f32e7eSjoerg #include "llvm/IR/Type.h"
5406f32e7eSjoerg #include "llvm/IR/Use.h"
5506f32e7eSjoerg #include "llvm/IR/User.h"
5606f32e7eSjoerg #include "llvm/IR/Value.h"
57*da58b97aSjoerg #include "llvm/InitializePasses.h"
5806f32e7eSjoerg #include "llvm/Pass.h"
5906f32e7eSjoerg #include "llvm/Support/Allocator.h"
6006f32e7eSjoerg #include "llvm/Support/Casting.h"
6106f32e7eSjoerg #include "llvm/Support/CommandLine.h"
6206f32e7eSjoerg #include "llvm/Support/Debug.h"
6306f32e7eSjoerg #include "llvm/Support/Error.h"
6406f32e7eSjoerg #include "llvm/Support/ErrorHandling.h"
6506f32e7eSjoerg #include "llvm/Support/FileSystem.h"
6606f32e7eSjoerg #include "llvm/Support/MathExtras.h"
6706f32e7eSjoerg #include "llvm/Support/MemoryBuffer.h"
6806f32e7eSjoerg #include "llvm/Support/TrailingObjects.h"
6906f32e7eSjoerg #include "llvm/Support/YAMLTraits.h"
7006f32e7eSjoerg #include "llvm/Support/raw_ostream.h"
7106f32e7eSjoerg #include "llvm/Transforms/IPO.h"
7206f32e7eSjoerg #include "llvm/Transforms/Utils/BasicBlockUtils.h"
7306f32e7eSjoerg #include "llvm/Transforms/Utils/ModuleUtils.h"
7406f32e7eSjoerg #include <algorithm>
7506f32e7eSjoerg #include <cassert>
7606f32e7eSjoerg #include <cstdint>
7706f32e7eSjoerg #include <memory>
7806f32e7eSjoerg #include <set>
7906f32e7eSjoerg #include <string>
8006f32e7eSjoerg #include <system_error>
8106f32e7eSjoerg #include <utility>
8206f32e7eSjoerg #include <vector>
8306f32e7eSjoerg
8406f32e7eSjoerg using namespace llvm;
8506f32e7eSjoerg using namespace lowertypetests;
8606f32e7eSjoerg
8706f32e7eSjoerg #define DEBUG_TYPE "lowertypetests"
8806f32e7eSjoerg
8906f32e7eSjoerg STATISTIC(ByteArraySizeBits, "Byte array size in bits");
9006f32e7eSjoerg STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
9106f32e7eSjoerg STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
9206f32e7eSjoerg STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
9306f32e7eSjoerg STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
9406f32e7eSjoerg
9506f32e7eSjoerg static cl::opt<bool> AvoidReuse(
9606f32e7eSjoerg "lowertypetests-avoid-reuse",
9706f32e7eSjoerg cl::desc("Try to avoid reuse of byte array addresses using aliases"),
9806f32e7eSjoerg cl::Hidden, cl::init(true));
9906f32e7eSjoerg
10006f32e7eSjoerg static cl::opt<PassSummaryAction> ClSummaryAction(
10106f32e7eSjoerg "lowertypetests-summary-action",
10206f32e7eSjoerg cl::desc("What to do with the summary when running this pass"),
10306f32e7eSjoerg cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"),
10406f32e7eSjoerg clEnumValN(PassSummaryAction::Import, "import",
10506f32e7eSjoerg "Import typeid resolutions from summary and globals"),
10606f32e7eSjoerg clEnumValN(PassSummaryAction::Export, "export",
10706f32e7eSjoerg "Export typeid resolutions to summary and globals")),
10806f32e7eSjoerg cl::Hidden);
10906f32e7eSjoerg
11006f32e7eSjoerg static cl::opt<std::string> ClReadSummary(
11106f32e7eSjoerg "lowertypetests-read-summary",
11206f32e7eSjoerg cl::desc("Read summary from given YAML file before running pass"),
11306f32e7eSjoerg cl::Hidden);
11406f32e7eSjoerg
11506f32e7eSjoerg static cl::opt<std::string> ClWriteSummary(
11606f32e7eSjoerg "lowertypetests-write-summary",
11706f32e7eSjoerg cl::desc("Write summary to given YAML file after running pass"),
11806f32e7eSjoerg cl::Hidden);
11906f32e7eSjoerg
containsGlobalOffset(uint64_t Offset) const12006f32e7eSjoerg bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
12106f32e7eSjoerg if (Offset < ByteOffset)
12206f32e7eSjoerg return false;
12306f32e7eSjoerg
12406f32e7eSjoerg if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
12506f32e7eSjoerg return false;
12606f32e7eSjoerg
12706f32e7eSjoerg uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
12806f32e7eSjoerg if (BitOffset >= BitSize)
12906f32e7eSjoerg return false;
13006f32e7eSjoerg
13106f32e7eSjoerg return Bits.count(BitOffset);
13206f32e7eSjoerg }
13306f32e7eSjoerg
print(raw_ostream & OS) const13406f32e7eSjoerg void BitSetInfo::print(raw_ostream &OS) const {
13506f32e7eSjoerg OS << "offset " << ByteOffset << " size " << BitSize << " align "
13606f32e7eSjoerg << (1 << AlignLog2);
13706f32e7eSjoerg
13806f32e7eSjoerg if (isAllOnes()) {
13906f32e7eSjoerg OS << " all-ones\n";
14006f32e7eSjoerg return;
14106f32e7eSjoerg }
14206f32e7eSjoerg
14306f32e7eSjoerg OS << " { ";
14406f32e7eSjoerg for (uint64_t B : Bits)
14506f32e7eSjoerg OS << B << ' ';
14606f32e7eSjoerg OS << "}\n";
14706f32e7eSjoerg }
14806f32e7eSjoerg
build()14906f32e7eSjoerg BitSetInfo BitSetBuilder::build() {
15006f32e7eSjoerg if (Min > Max)
15106f32e7eSjoerg Min = 0;
15206f32e7eSjoerg
15306f32e7eSjoerg // Normalize each offset against the minimum observed offset, and compute
15406f32e7eSjoerg // the bitwise OR of each of the offsets. The number of trailing zeros
15506f32e7eSjoerg // in the mask gives us the log2 of the alignment of all offsets, which
15606f32e7eSjoerg // allows us to compress the bitset by only storing one bit per aligned
15706f32e7eSjoerg // address.
15806f32e7eSjoerg uint64_t Mask = 0;
15906f32e7eSjoerg for (uint64_t &Offset : Offsets) {
16006f32e7eSjoerg Offset -= Min;
16106f32e7eSjoerg Mask |= Offset;
16206f32e7eSjoerg }
16306f32e7eSjoerg
16406f32e7eSjoerg BitSetInfo BSI;
16506f32e7eSjoerg BSI.ByteOffset = Min;
16606f32e7eSjoerg
16706f32e7eSjoerg BSI.AlignLog2 = 0;
16806f32e7eSjoerg if (Mask != 0)
16906f32e7eSjoerg BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined);
17006f32e7eSjoerg
17106f32e7eSjoerg // Build the compressed bitset while normalizing the offsets against the
17206f32e7eSjoerg // computed alignment.
17306f32e7eSjoerg BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1;
17406f32e7eSjoerg for (uint64_t Offset : Offsets) {
17506f32e7eSjoerg Offset >>= BSI.AlignLog2;
17606f32e7eSjoerg BSI.Bits.insert(Offset);
17706f32e7eSjoerg }
17806f32e7eSjoerg
17906f32e7eSjoerg return BSI;
18006f32e7eSjoerg }
18106f32e7eSjoerg
addFragment(const std::set<uint64_t> & F)18206f32e7eSjoerg void GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) {
18306f32e7eSjoerg // Create a new fragment to hold the layout for F.
18406f32e7eSjoerg Fragments.emplace_back();
18506f32e7eSjoerg std::vector<uint64_t> &Fragment = Fragments.back();
18606f32e7eSjoerg uint64_t FragmentIndex = Fragments.size() - 1;
18706f32e7eSjoerg
18806f32e7eSjoerg for (auto ObjIndex : F) {
18906f32e7eSjoerg uint64_t OldFragmentIndex = FragmentMap[ObjIndex];
19006f32e7eSjoerg if (OldFragmentIndex == 0) {
19106f32e7eSjoerg // We haven't seen this object index before, so just add it to the current
19206f32e7eSjoerg // fragment.
19306f32e7eSjoerg Fragment.push_back(ObjIndex);
19406f32e7eSjoerg } else {
19506f32e7eSjoerg // This index belongs to an existing fragment. Copy the elements of the
19606f32e7eSjoerg // old fragment into this one and clear the old fragment. We don't update
19706f32e7eSjoerg // the fragment map just yet, this ensures that any further references to
19806f32e7eSjoerg // indices from the old fragment in this fragment do not insert any more
19906f32e7eSjoerg // indices.
20006f32e7eSjoerg std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex];
201*da58b97aSjoerg llvm::append_range(Fragment, OldFragment);
20206f32e7eSjoerg OldFragment.clear();
20306f32e7eSjoerg }
20406f32e7eSjoerg }
20506f32e7eSjoerg
20606f32e7eSjoerg // Update the fragment map to point our object indices to this fragment.
20706f32e7eSjoerg for (uint64_t ObjIndex : Fragment)
20806f32e7eSjoerg FragmentMap[ObjIndex] = FragmentIndex;
20906f32e7eSjoerg }
21006f32e7eSjoerg
allocate(const std::set<uint64_t> & Bits,uint64_t BitSize,uint64_t & AllocByteOffset,uint8_t & AllocMask)21106f32e7eSjoerg void ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits,
21206f32e7eSjoerg uint64_t BitSize, uint64_t &AllocByteOffset,
21306f32e7eSjoerg uint8_t &AllocMask) {
21406f32e7eSjoerg // Find the smallest current allocation.
21506f32e7eSjoerg unsigned Bit = 0;
21606f32e7eSjoerg for (unsigned I = 1; I != BitsPerByte; ++I)
21706f32e7eSjoerg if (BitAllocs[I] < BitAllocs[Bit])
21806f32e7eSjoerg Bit = I;
21906f32e7eSjoerg
22006f32e7eSjoerg AllocByteOffset = BitAllocs[Bit];
22106f32e7eSjoerg
22206f32e7eSjoerg // Add our size to it.
22306f32e7eSjoerg unsigned ReqSize = AllocByteOffset + BitSize;
22406f32e7eSjoerg BitAllocs[Bit] = ReqSize;
22506f32e7eSjoerg if (Bytes.size() < ReqSize)
22606f32e7eSjoerg Bytes.resize(ReqSize);
22706f32e7eSjoerg
22806f32e7eSjoerg // Set our bits.
22906f32e7eSjoerg AllocMask = 1 << Bit;
23006f32e7eSjoerg for (uint64_t B : Bits)
23106f32e7eSjoerg Bytes[AllocByteOffset + B] |= AllocMask;
23206f32e7eSjoerg }
23306f32e7eSjoerg
isJumpTableCanonical(Function * F)23406f32e7eSjoerg bool lowertypetests::isJumpTableCanonical(Function *F) {
23506f32e7eSjoerg if (F->isDeclarationForLinker())
23606f32e7eSjoerg return false;
23706f32e7eSjoerg auto *CI = mdconst::extract_or_null<ConstantInt>(
23806f32e7eSjoerg F->getParent()->getModuleFlag("CFI Canonical Jump Tables"));
23906f32e7eSjoerg if (!CI || CI->getZExtValue() != 0)
24006f32e7eSjoerg return true;
24106f32e7eSjoerg return F->hasFnAttribute("cfi-canonical-jump-table");
24206f32e7eSjoerg }
24306f32e7eSjoerg
24406f32e7eSjoerg namespace {
24506f32e7eSjoerg
24606f32e7eSjoerg struct ByteArrayInfo {
24706f32e7eSjoerg std::set<uint64_t> Bits;
24806f32e7eSjoerg uint64_t BitSize;
24906f32e7eSjoerg GlobalVariable *ByteArray;
25006f32e7eSjoerg GlobalVariable *MaskGlobal;
25106f32e7eSjoerg uint8_t *MaskPtr = nullptr;
25206f32e7eSjoerg };
25306f32e7eSjoerg
25406f32e7eSjoerg /// A POD-like structure that we use to store a global reference together with
25506f32e7eSjoerg /// its metadata types. In this pass we frequently need to query the set of
25606f32e7eSjoerg /// metadata types referenced by a global, which at the IR level is an expensive
25706f32e7eSjoerg /// operation involving a map lookup; this data structure helps to reduce the
25806f32e7eSjoerg /// number of times we need to do this lookup.
25906f32e7eSjoerg class GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> {
26006f32e7eSjoerg friend TrailingObjects;
26106f32e7eSjoerg
26206f32e7eSjoerg GlobalObject *GO;
26306f32e7eSjoerg size_t NTypes;
26406f32e7eSjoerg
26506f32e7eSjoerg // For functions: true if the jump table is canonical. This essentially means
26606f32e7eSjoerg // whether the canonical address (i.e. the symbol table entry) of the function
26706f32e7eSjoerg // is provided by the local jump table. This is normally the same as whether
26806f32e7eSjoerg // the function is defined locally, but if canonical jump tables are disabled
26906f32e7eSjoerg // by the user then the jump table never provides a canonical definition.
27006f32e7eSjoerg bool IsJumpTableCanonical;
27106f32e7eSjoerg
27206f32e7eSjoerg // For functions: true if this function is either defined or used in a thinlto
27306f32e7eSjoerg // module and its jumptable entry needs to be exported to thinlto backends.
27406f32e7eSjoerg bool IsExported;
27506f32e7eSjoerg
numTrailingObjects(OverloadToken<MDNode * >) const27606f32e7eSjoerg size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; }
27706f32e7eSjoerg
27806f32e7eSjoerg public:
create(BumpPtrAllocator & Alloc,GlobalObject * GO,bool IsJumpTableCanonical,bool IsExported,ArrayRef<MDNode * > Types)27906f32e7eSjoerg static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO,
28006f32e7eSjoerg bool IsJumpTableCanonical, bool IsExported,
28106f32e7eSjoerg ArrayRef<MDNode *> Types) {
28206f32e7eSjoerg auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate(
28306f32e7eSjoerg totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember)));
28406f32e7eSjoerg GTM->GO = GO;
28506f32e7eSjoerg GTM->NTypes = Types.size();
28606f32e7eSjoerg GTM->IsJumpTableCanonical = IsJumpTableCanonical;
28706f32e7eSjoerg GTM->IsExported = IsExported;
28806f32e7eSjoerg std::uninitialized_copy(Types.begin(), Types.end(),
28906f32e7eSjoerg GTM->getTrailingObjects<MDNode *>());
29006f32e7eSjoerg return GTM;
29106f32e7eSjoerg }
29206f32e7eSjoerg
getGlobal() const29306f32e7eSjoerg GlobalObject *getGlobal() const {
29406f32e7eSjoerg return GO;
29506f32e7eSjoerg }
29606f32e7eSjoerg
isJumpTableCanonical() const29706f32e7eSjoerg bool isJumpTableCanonical() const {
29806f32e7eSjoerg return IsJumpTableCanonical;
29906f32e7eSjoerg }
30006f32e7eSjoerg
isExported() const30106f32e7eSjoerg bool isExported() const {
30206f32e7eSjoerg return IsExported;
30306f32e7eSjoerg }
30406f32e7eSjoerg
types() const30506f32e7eSjoerg ArrayRef<MDNode *> types() const {
30606f32e7eSjoerg return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
30706f32e7eSjoerg }
30806f32e7eSjoerg };
30906f32e7eSjoerg
31006f32e7eSjoerg struct ICallBranchFunnel final
31106f32e7eSjoerg : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
create__anonb458f8240111::ICallBranchFunnel31206f32e7eSjoerg static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
31306f32e7eSjoerg ArrayRef<GlobalTypeMember *> Targets,
31406f32e7eSjoerg unsigned UniqueId) {
31506f32e7eSjoerg auto *Call = static_cast<ICallBranchFunnel *>(
31606f32e7eSjoerg Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()),
31706f32e7eSjoerg alignof(ICallBranchFunnel)));
31806f32e7eSjoerg Call->CI = CI;
31906f32e7eSjoerg Call->UniqueId = UniqueId;
32006f32e7eSjoerg Call->NTargets = Targets.size();
32106f32e7eSjoerg std::uninitialized_copy(Targets.begin(), Targets.end(),
32206f32e7eSjoerg Call->getTrailingObjects<GlobalTypeMember *>());
32306f32e7eSjoerg return Call;
32406f32e7eSjoerg }
32506f32e7eSjoerg
32606f32e7eSjoerg CallInst *CI;
targets__anonb458f8240111::ICallBranchFunnel32706f32e7eSjoerg ArrayRef<GlobalTypeMember *> targets() const {
32806f32e7eSjoerg return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
32906f32e7eSjoerg }
33006f32e7eSjoerg
33106f32e7eSjoerg unsigned UniqueId;
33206f32e7eSjoerg
33306f32e7eSjoerg private:
33406f32e7eSjoerg size_t NTargets;
33506f32e7eSjoerg };
33606f32e7eSjoerg
33706f32e7eSjoerg struct ScopedSaveAliaseesAndUsed {
33806f32e7eSjoerg Module &M;
339*da58b97aSjoerg SmallVector<GlobalValue *, 4> Used, CompilerUsed;
34006f32e7eSjoerg std::vector<std::pair<GlobalIndirectSymbol *, Function *>> FunctionAliases;
34106f32e7eSjoerg
ScopedSaveAliaseesAndUsed__anonb458f8240111::ScopedSaveAliaseesAndUsed34206f32e7eSjoerg ScopedSaveAliaseesAndUsed(Module &M) : M(M) {
34306f32e7eSjoerg // The users of this class want to replace all function references except
34406f32e7eSjoerg // for aliases and llvm.used/llvm.compiler.used with references to a jump
34506f32e7eSjoerg // table. We avoid replacing aliases in order to avoid introducing a double
34606f32e7eSjoerg // indirection (or an alias pointing to a declaration in ThinLTO mode), and
34706f32e7eSjoerg // we avoid replacing llvm.used/llvm.compiler.used because these global
34806f32e7eSjoerg // variables describe properties of the global, not the jump table (besides,
34906f32e7eSjoerg // offseted references to the jump table in llvm.used are invalid).
35006f32e7eSjoerg // Unfortunately, LLVM doesn't have a "RAUW except for these (possibly
35106f32e7eSjoerg // indirect) users", so what we do is save the list of globals referenced by
35206f32e7eSjoerg // llvm.used/llvm.compiler.used and aliases, erase the used lists, let RAUW
35306f32e7eSjoerg // replace the aliasees and then set them back to their original values at
35406f32e7eSjoerg // the end.
35506f32e7eSjoerg if (GlobalVariable *GV = collectUsedGlobalVariables(M, Used, false))
35606f32e7eSjoerg GV->eraseFromParent();
35706f32e7eSjoerg if (GlobalVariable *GV = collectUsedGlobalVariables(M, CompilerUsed, true))
35806f32e7eSjoerg GV->eraseFromParent();
35906f32e7eSjoerg
36006f32e7eSjoerg for (auto &GIS : concat<GlobalIndirectSymbol>(M.aliases(), M.ifuncs())) {
36106f32e7eSjoerg // FIXME: This should look past all aliases not just interposable ones,
36206f32e7eSjoerg // see discussion on D65118.
36306f32e7eSjoerg if (auto *F =
36406f32e7eSjoerg dyn_cast<Function>(GIS.getIndirectSymbol()->stripPointerCasts()))
36506f32e7eSjoerg FunctionAliases.push_back({&GIS, F});
36606f32e7eSjoerg }
36706f32e7eSjoerg }
36806f32e7eSjoerg
~ScopedSaveAliaseesAndUsed__anonb458f8240111::ScopedSaveAliaseesAndUsed36906f32e7eSjoerg ~ScopedSaveAliaseesAndUsed() {
370*da58b97aSjoerg appendToUsed(M, Used);
371*da58b97aSjoerg appendToCompilerUsed(M, CompilerUsed);
37206f32e7eSjoerg
37306f32e7eSjoerg for (auto P : FunctionAliases)
37406f32e7eSjoerg P.first->setIndirectSymbol(
37506f32e7eSjoerg ConstantExpr::getBitCast(P.second, P.first->getType()));
37606f32e7eSjoerg }
37706f32e7eSjoerg };
37806f32e7eSjoerg
37906f32e7eSjoerg class LowerTypeTestsModule {
38006f32e7eSjoerg Module &M;
38106f32e7eSjoerg
38206f32e7eSjoerg ModuleSummaryIndex *ExportSummary;
38306f32e7eSjoerg const ModuleSummaryIndex *ImportSummary;
384*da58b97aSjoerg // Set when the client has invoked this to simply drop all type test assume
385*da58b97aSjoerg // sequences.
386*da58b97aSjoerg bool DropTypeTests;
38706f32e7eSjoerg
38806f32e7eSjoerg Triple::ArchType Arch;
38906f32e7eSjoerg Triple::OSType OS;
39006f32e7eSjoerg Triple::ObjectFormatType ObjectFormat;
39106f32e7eSjoerg
39206f32e7eSjoerg IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
39306f32e7eSjoerg IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
39406f32e7eSjoerg PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
39506f32e7eSjoerg ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0);
39606f32e7eSjoerg IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
39706f32e7eSjoerg PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty);
39806f32e7eSjoerg IntegerType *Int64Ty = Type::getInt64Ty(M.getContext());
39906f32e7eSjoerg IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0);
40006f32e7eSjoerg
40106f32e7eSjoerg // Indirect function call index assignment counter for WebAssembly
40206f32e7eSjoerg uint64_t IndirectIndex = 1;
40306f32e7eSjoerg
40406f32e7eSjoerg // Mapping from type identifiers to the call sites that test them, as well as
40506f32e7eSjoerg // whether the type identifier needs to be exported to ThinLTO backends as
40606f32e7eSjoerg // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId).
40706f32e7eSjoerg struct TypeIdUserInfo {
40806f32e7eSjoerg std::vector<CallInst *> CallSites;
40906f32e7eSjoerg bool IsExported = false;
41006f32e7eSjoerg };
41106f32e7eSjoerg DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers;
41206f32e7eSjoerg
41306f32e7eSjoerg /// This structure describes how to lower type tests for a particular type
41406f32e7eSjoerg /// identifier. It is either built directly from the global analysis (during
41506f32e7eSjoerg /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type
41606f32e7eSjoerg /// identifier summaries and external symbol references (in ThinLTO backends).
41706f32e7eSjoerg struct TypeIdLowering {
41806f32e7eSjoerg TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat;
41906f32e7eSjoerg
42006f32e7eSjoerg /// All except Unsat: the start address within the combined global.
42106f32e7eSjoerg Constant *OffsetedGlobal;
42206f32e7eSjoerg
42306f32e7eSjoerg /// ByteArray, Inline, AllOnes: log2 of the required global alignment
42406f32e7eSjoerg /// relative to the start address.
42506f32e7eSjoerg Constant *AlignLog2;
42606f32e7eSjoerg
42706f32e7eSjoerg /// ByteArray, Inline, AllOnes: one less than the size of the memory region
42806f32e7eSjoerg /// covering members of this type identifier as a multiple of 2^AlignLog2.
42906f32e7eSjoerg Constant *SizeM1;
43006f32e7eSjoerg
43106f32e7eSjoerg /// ByteArray: the byte array to test the address against.
43206f32e7eSjoerg Constant *TheByteArray;
43306f32e7eSjoerg
43406f32e7eSjoerg /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
43506f32e7eSjoerg Constant *BitMask;
43606f32e7eSjoerg
43706f32e7eSjoerg /// Inline: the bit mask to test the address against.
43806f32e7eSjoerg Constant *InlineBits;
43906f32e7eSjoerg };
44006f32e7eSjoerg
44106f32e7eSjoerg std::vector<ByteArrayInfo> ByteArrayInfos;
44206f32e7eSjoerg
44306f32e7eSjoerg Function *WeakInitializerFn = nullptr;
44406f32e7eSjoerg
44506f32e7eSjoerg bool shouldExportConstantsAsAbsoluteSymbols();
44606f32e7eSjoerg uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL);
44706f32e7eSjoerg TypeIdLowering importTypeId(StringRef TypeId);
44806f32e7eSjoerg void importTypeTest(CallInst *CI);
44906f32e7eSjoerg void importFunction(Function *F, bool isJumpTableCanonical,
45006f32e7eSjoerg std::vector<GlobalAlias *> &AliasesToErase);
45106f32e7eSjoerg
45206f32e7eSjoerg BitSetInfo
45306f32e7eSjoerg buildBitSet(Metadata *TypeId,
45406f32e7eSjoerg const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
45506f32e7eSjoerg ByteArrayInfo *createByteArray(BitSetInfo &BSI);
45606f32e7eSjoerg void allocateByteArrays();
45706f32e7eSjoerg Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
45806f32e7eSjoerg Value *BitOffset);
45906f32e7eSjoerg void lowerTypeTestCalls(
46006f32e7eSjoerg ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
46106f32e7eSjoerg const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
46206f32e7eSjoerg Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
46306f32e7eSjoerg const TypeIdLowering &TIL);
46406f32e7eSjoerg
46506f32e7eSjoerg void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
46606f32e7eSjoerg ArrayRef<GlobalTypeMember *> Globals);
46706f32e7eSjoerg unsigned getJumpTableEntrySize();
46806f32e7eSjoerg Type *getJumpTableEntryType();
46906f32e7eSjoerg void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
47006f32e7eSjoerg Triple::ArchType JumpTableArch,
47106f32e7eSjoerg SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
47206f32e7eSjoerg void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
47306f32e7eSjoerg void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
47406f32e7eSjoerg ArrayRef<GlobalTypeMember *> Functions);
47506f32e7eSjoerg void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
47606f32e7eSjoerg ArrayRef<GlobalTypeMember *> Functions);
47706f32e7eSjoerg void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
47806f32e7eSjoerg ArrayRef<GlobalTypeMember *> Functions);
47906f32e7eSjoerg void
48006f32e7eSjoerg buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
48106f32e7eSjoerg ArrayRef<GlobalTypeMember *> Globals,
48206f32e7eSjoerg ArrayRef<ICallBranchFunnel *> ICallBranchFunnels);
48306f32e7eSjoerg
48406f32e7eSjoerg void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT,
48506f32e7eSjoerg bool IsJumpTableCanonical);
48606f32e7eSjoerg void moveInitializerToModuleConstructor(GlobalVariable *GV);
48706f32e7eSjoerg void findGlobalVariableUsersOf(Constant *C,
48806f32e7eSjoerg SmallSetVector<GlobalVariable *, 8> &Out);
48906f32e7eSjoerg
49006f32e7eSjoerg void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
49106f32e7eSjoerg
49206f32e7eSjoerg /// replaceCfiUses - Go through the uses list for this definition
49306f32e7eSjoerg /// and make each use point to "V" instead of "this" when the use is outside
49406f32e7eSjoerg /// the block. 'This's use list is expected to have at least one element.
49506f32e7eSjoerg /// Unlike replaceAllUsesWith this function skips blockaddr and direct call
49606f32e7eSjoerg /// uses.
49706f32e7eSjoerg void replaceCfiUses(Function *Old, Value *New, bool IsJumpTableCanonical);
49806f32e7eSjoerg
49906f32e7eSjoerg /// replaceDirectCalls - Go through the uses list for this definition and
50006f32e7eSjoerg /// replace each use, which is a direct function call.
50106f32e7eSjoerg void replaceDirectCalls(Value *Old, Value *New);
50206f32e7eSjoerg
50306f32e7eSjoerg public:
50406f32e7eSjoerg LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary,
505*da58b97aSjoerg const ModuleSummaryIndex *ImportSummary,
506*da58b97aSjoerg bool DropTypeTests);
50706f32e7eSjoerg
50806f32e7eSjoerg bool lower();
50906f32e7eSjoerg
51006f32e7eSjoerg // Lower the module using the action and summary passed as command line
51106f32e7eSjoerg // arguments. For testing purposes only.
51206f32e7eSjoerg static bool runForTesting(Module &M);
51306f32e7eSjoerg };
51406f32e7eSjoerg
51506f32e7eSjoerg struct LowerTypeTests : public ModulePass {
51606f32e7eSjoerg static char ID;
51706f32e7eSjoerg
51806f32e7eSjoerg bool UseCommandLine = false;
51906f32e7eSjoerg
52006f32e7eSjoerg ModuleSummaryIndex *ExportSummary;
52106f32e7eSjoerg const ModuleSummaryIndex *ImportSummary;
522*da58b97aSjoerg bool DropTypeTests;
52306f32e7eSjoerg
LowerTypeTests__anonb458f8240111::LowerTypeTests52406f32e7eSjoerg LowerTypeTests() : ModulePass(ID), UseCommandLine(true) {
52506f32e7eSjoerg initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
52606f32e7eSjoerg }
52706f32e7eSjoerg
LowerTypeTests__anonb458f8240111::LowerTypeTests52806f32e7eSjoerg LowerTypeTests(ModuleSummaryIndex *ExportSummary,
529*da58b97aSjoerg const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
53006f32e7eSjoerg : ModulePass(ID), ExportSummary(ExportSummary),
531*da58b97aSjoerg ImportSummary(ImportSummary), DropTypeTests(DropTypeTests) {
53206f32e7eSjoerg initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
53306f32e7eSjoerg }
53406f32e7eSjoerg
runOnModule__anonb458f8240111::LowerTypeTests53506f32e7eSjoerg bool runOnModule(Module &M) override {
53606f32e7eSjoerg if (UseCommandLine)
53706f32e7eSjoerg return LowerTypeTestsModule::runForTesting(M);
538*da58b97aSjoerg return LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
539*da58b97aSjoerg .lower();
54006f32e7eSjoerg }
54106f32e7eSjoerg };
54206f32e7eSjoerg
54306f32e7eSjoerg } // end anonymous namespace
54406f32e7eSjoerg
54506f32e7eSjoerg char LowerTypeTests::ID = 0;
54606f32e7eSjoerg
54706f32e7eSjoerg INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false,
54806f32e7eSjoerg false)
54906f32e7eSjoerg
55006f32e7eSjoerg ModulePass *
createLowerTypeTestsPass(ModuleSummaryIndex * ExportSummary,const ModuleSummaryIndex * ImportSummary,bool DropTypeTests)55106f32e7eSjoerg llvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary,
552*da58b97aSjoerg const ModuleSummaryIndex *ImportSummary,
553*da58b97aSjoerg bool DropTypeTests) {
554*da58b97aSjoerg return new LowerTypeTests(ExportSummary, ImportSummary, DropTypeTests);
55506f32e7eSjoerg }
55606f32e7eSjoerg
55706f32e7eSjoerg /// Build a bit set for TypeId using the object layouts in
55806f32e7eSjoerg /// GlobalLayout.
buildBitSet(Metadata * TypeId,const DenseMap<GlobalTypeMember *,uint64_t> & GlobalLayout)55906f32e7eSjoerg BitSetInfo LowerTypeTestsModule::buildBitSet(
56006f32e7eSjoerg Metadata *TypeId,
56106f32e7eSjoerg const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
56206f32e7eSjoerg BitSetBuilder BSB;
56306f32e7eSjoerg
56406f32e7eSjoerg // Compute the byte offset of each address associated with this type
56506f32e7eSjoerg // identifier.
56606f32e7eSjoerg for (auto &GlobalAndOffset : GlobalLayout) {
56706f32e7eSjoerg for (MDNode *Type : GlobalAndOffset.first->types()) {
56806f32e7eSjoerg if (Type->getOperand(1) != TypeId)
56906f32e7eSjoerg continue;
57006f32e7eSjoerg uint64_t Offset =
57106f32e7eSjoerg cast<ConstantInt>(
57206f32e7eSjoerg cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
57306f32e7eSjoerg ->getZExtValue();
57406f32e7eSjoerg BSB.addOffset(GlobalAndOffset.second + Offset);
57506f32e7eSjoerg }
57606f32e7eSjoerg }
57706f32e7eSjoerg
57806f32e7eSjoerg return BSB.build();
57906f32e7eSjoerg }
58006f32e7eSjoerg
58106f32e7eSjoerg /// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in
58206f32e7eSjoerg /// Bits. This pattern matches to the bt instruction on x86.
createMaskedBitTest(IRBuilder<> & B,Value * Bits,Value * BitOffset)58306f32e7eSjoerg static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits,
58406f32e7eSjoerg Value *BitOffset) {
58506f32e7eSjoerg auto BitsType = cast<IntegerType>(Bits->getType());
58606f32e7eSjoerg unsigned BitWidth = BitsType->getBitWidth();
58706f32e7eSjoerg
58806f32e7eSjoerg BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType);
58906f32e7eSjoerg Value *BitIndex =
59006f32e7eSjoerg B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1));
59106f32e7eSjoerg Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex);
59206f32e7eSjoerg Value *MaskedBits = B.CreateAnd(Bits, BitMask);
59306f32e7eSjoerg return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0));
59406f32e7eSjoerg }
59506f32e7eSjoerg
createByteArray(BitSetInfo & BSI)59606f32e7eSjoerg ByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) {
59706f32e7eSjoerg // Create globals to stand in for byte arrays and masks. These never actually
59806f32e7eSjoerg // get initialized, we RAUW and erase them later in allocateByteArrays() once
59906f32e7eSjoerg // we know the offset and mask to use.
60006f32e7eSjoerg auto ByteArrayGlobal = new GlobalVariable(
60106f32e7eSjoerg M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr);
60206f32e7eSjoerg auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true,
60306f32e7eSjoerg GlobalValue::PrivateLinkage, nullptr);
60406f32e7eSjoerg
60506f32e7eSjoerg ByteArrayInfos.emplace_back();
60606f32e7eSjoerg ByteArrayInfo *BAI = &ByteArrayInfos.back();
60706f32e7eSjoerg
60806f32e7eSjoerg BAI->Bits = BSI.Bits;
60906f32e7eSjoerg BAI->BitSize = BSI.BitSize;
61006f32e7eSjoerg BAI->ByteArray = ByteArrayGlobal;
61106f32e7eSjoerg BAI->MaskGlobal = MaskGlobal;
61206f32e7eSjoerg return BAI;
61306f32e7eSjoerg }
61406f32e7eSjoerg
allocateByteArrays()61506f32e7eSjoerg void LowerTypeTestsModule::allocateByteArrays() {
61606f32e7eSjoerg llvm::stable_sort(ByteArrayInfos,
61706f32e7eSjoerg [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) {
61806f32e7eSjoerg return BAI1.BitSize > BAI2.BitSize;
61906f32e7eSjoerg });
62006f32e7eSjoerg
62106f32e7eSjoerg std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
62206f32e7eSjoerg
62306f32e7eSjoerg ByteArrayBuilder BAB;
62406f32e7eSjoerg for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
62506f32e7eSjoerg ByteArrayInfo *BAI = &ByteArrayInfos[I];
62606f32e7eSjoerg
62706f32e7eSjoerg uint8_t Mask;
62806f32e7eSjoerg BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask);
62906f32e7eSjoerg
63006f32e7eSjoerg BAI->MaskGlobal->replaceAllUsesWith(
63106f32e7eSjoerg ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy));
63206f32e7eSjoerg BAI->MaskGlobal->eraseFromParent();
63306f32e7eSjoerg if (BAI->MaskPtr)
63406f32e7eSjoerg *BAI->MaskPtr = Mask;
63506f32e7eSjoerg }
63606f32e7eSjoerg
63706f32e7eSjoerg Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes);
63806f32e7eSjoerg auto ByteArray =
63906f32e7eSjoerg new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true,
64006f32e7eSjoerg GlobalValue::PrivateLinkage, ByteArrayConst);
64106f32e7eSjoerg
64206f32e7eSjoerg for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) {
64306f32e7eSjoerg ByteArrayInfo *BAI = &ByteArrayInfos[I];
64406f32e7eSjoerg
64506f32e7eSjoerg Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0),
64606f32e7eSjoerg ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])};
64706f32e7eSjoerg Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(
64806f32e7eSjoerg ByteArrayConst->getType(), ByteArray, Idxs);
64906f32e7eSjoerg
65006f32e7eSjoerg // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures
65106f32e7eSjoerg // that the pc-relative displacement is folded into the lea instead of the
65206f32e7eSjoerg // test instruction getting another displacement.
65306f32e7eSjoerg GlobalAlias *Alias = GlobalAlias::create(
65406f32e7eSjoerg Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M);
65506f32e7eSjoerg BAI->ByteArray->replaceAllUsesWith(Alias);
65606f32e7eSjoerg BAI->ByteArray->eraseFromParent();
65706f32e7eSjoerg }
65806f32e7eSjoerg
65906f32e7eSjoerg ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] +
66006f32e7eSjoerg BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] +
66106f32e7eSjoerg BAB.BitAllocs[6] + BAB.BitAllocs[7];
66206f32e7eSjoerg ByteArraySizeBytes = BAB.Bytes.size();
66306f32e7eSjoerg }
66406f32e7eSjoerg
66506f32e7eSjoerg /// Build a test that bit BitOffset is set in the type identifier that was
66606f32e7eSjoerg /// lowered to TIL, which must be either an Inline or a ByteArray.
createBitSetTest(IRBuilder<> & B,const TypeIdLowering & TIL,Value * BitOffset)66706f32e7eSjoerg Value *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B,
66806f32e7eSjoerg const TypeIdLowering &TIL,
66906f32e7eSjoerg Value *BitOffset) {
67006f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Inline) {
67106f32e7eSjoerg // If the bit set is sufficiently small, we can avoid a load by bit testing
67206f32e7eSjoerg // a constant.
67306f32e7eSjoerg return createMaskedBitTest(B, TIL.InlineBits, BitOffset);
67406f32e7eSjoerg } else {
67506f32e7eSjoerg Constant *ByteArray = TIL.TheByteArray;
67606f32e7eSjoerg if (AvoidReuse && !ImportSummary) {
67706f32e7eSjoerg // Each use of the byte array uses a different alias. This makes the
67806f32e7eSjoerg // backend less likely to reuse previously computed byte array addresses,
67906f32e7eSjoerg // improving the security of the CFI mechanism based on this pass.
68006f32e7eSjoerg // This won't work when importing because TheByteArray is external.
68106f32e7eSjoerg ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage,
68206f32e7eSjoerg "bits_use", ByteArray, &M);
68306f32e7eSjoerg }
68406f32e7eSjoerg
68506f32e7eSjoerg Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset);
68606f32e7eSjoerg Value *Byte = B.CreateLoad(Int8Ty, ByteAddr);
68706f32e7eSjoerg
68806f32e7eSjoerg Value *ByteAndMask =
68906f32e7eSjoerg B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty));
69006f32e7eSjoerg return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0));
69106f32e7eSjoerg }
69206f32e7eSjoerg }
69306f32e7eSjoerg
isKnownTypeIdMember(Metadata * TypeId,const DataLayout & DL,Value * V,uint64_t COffset)69406f32e7eSjoerg static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL,
69506f32e7eSjoerg Value *V, uint64_t COffset) {
69606f32e7eSjoerg if (auto GV = dyn_cast<GlobalObject>(V)) {
69706f32e7eSjoerg SmallVector<MDNode *, 2> Types;
69806f32e7eSjoerg GV->getMetadata(LLVMContext::MD_type, Types);
69906f32e7eSjoerg for (MDNode *Type : Types) {
70006f32e7eSjoerg if (Type->getOperand(1) != TypeId)
70106f32e7eSjoerg continue;
70206f32e7eSjoerg uint64_t Offset =
70306f32e7eSjoerg cast<ConstantInt>(
70406f32e7eSjoerg cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
70506f32e7eSjoerg ->getZExtValue();
70606f32e7eSjoerg if (COffset == Offset)
70706f32e7eSjoerg return true;
70806f32e7eSjoerg }
70906f32e7eSjoerg return false;
71006f32e7eSjoerg }
71106f32e7eSjoerg
71206f32e7eSjoerg if (auto GEP = dyn_cast<GEPOperator>(V)) {
71306f32e7eSjoerg APInt APOffset(DL.getPointerSizeInBits(0), 0);
71406f32e7eSjoerg bool Result = GEP->accumulateConstantOffset(DL, APOffset);
71506f32e7eSjoerg if (!Result)
71606f32e7eSjoerg return false;
71706f32e7eSjoerg COffset += APOffset.getZExtValue();
71806f32e7eSjoerg return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset);
71906f32e7eSjoerg }
72006f32e7eSjoerg
72106f32e7eSjoerg if (auto Op = dyn_cast<Operator>(V)) {
72206f32e7eSjoerg if (Op->getOpcode() == Instruction::BitCast)
72306f32e7eSjoerg return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset);
72406f32e7eSjoerg
72506f32e7eSjoerg if (Op->getOpcode() == Instruction::Select)
72606f32e7eSjoerg return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) &&
72706f32e7eSjoerg isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset);
72806f32e7eSjoerg }
72906f32e7eSjoerg
73006f32e7eSjoerg return false;
73106f32e7eSjoerg }
73206f32e7eSjoerg
73306f32e7eSjoerg /// Lower a llvm.type.test call to its implementation. Returns the value to
73406f32e7eSjoerg /// replace the call with.
lowerTypeTestCall(Metadata * TypeId,CallInst * CI,const TypeIdLowering & TIL)73506f32e7eSjoerg Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
73606f32e7eSjoerg const TypeIdLowering &TIL) {
737*da58b97aSjoerg // Delay lowering if the resolution is currently unknown.
738*da58b97aSjoerg if (TIL.TheKind == TypeTestResolution::Unknown)
739*da58b97aSjoerg return nullptr;
74006f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Unsat)
74106f32e7eSjoerg return ConstantInt::getFalse(M.getContext());
74206f32e7eSjoerg
74306f32e7eSjoerg Value *Ptr = CI->getArgOperand(0);
74406f32e7eSjoerg const DataLayout &DL = M.getDataLayout();
74506f32e7eSjoerg if (isKnownTypeIdMember(TypeId, DL, Ptr, 0))
74606f32e7eSjoerg return ConstantInt::getTrue(M.getContext());
74706f32e7eSjoerg
74806f32e7eSjoerg BasicBlock *InitialBB = CI->getParent();
74906f32e7eSjoerg
75006f32e7eSjoerg IRBuilder<> B(CI);
75106f32e7eSjoerg
75206f32e7eSjoerg Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy);
75306f32e7eSjoerg
75406f32e7eSjoerg Constant *OffsetedGlobalAsInt =
75506f32e7eSjoerg ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy);
75606f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Single)
75706f32e7eSjoerg return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
75806f32e7eSjoerg
75906f32e7eSjoerg Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
76006f32e7eSjoerg
76106f32e7eSjoerg // We need to check that the offset both falls within our range and is
76206f32e7eSjoerg // suitably aligned. We can check both properties at the same time by
76306f32e7eSjoerg // performing a right rotate by log2(alignment) followed by an integer
76406f32e7eSjoerg // comparison against the bitset size. The rotate will move the lower
76506f32e7eSjoerg // order bits that need to be zero into the higher order bits of the
76606f32e7eSjoerg // result, causing the comparison to fail if they are nonzero. The rotate
76706f32e7eSjoerg // also conveniently gives us a bit offset to use during the load from
76806f32e7eSjoerg // the bitset.
76906f32e7eSjoerg Value *OffsetSHR =
77006f32e7eSjoerg B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy));
77106f32e7eSjoerg Value *OffsetSHL = B.CreateShl(
77206f32e7eSjoerg PtrOffset, ConstantExpr::getZExt(
77306f32e7eSjoerg ConstantExpr::getSub(
77406f32e7eSjoerg ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
77506f32e7eSjoerg TIL.AlignLog2),
77606f32e7eSjoerg IntPtrTy));
77706f32e7eSjoerg Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
77806f32e7eSjoerg
77906f32e7eSjoerg Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1);
78006f32e7eSjoerg
78106f32e7eSjoerg // If the bit set is all ones, testing against it is unnecessary.
78206f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::AllOnes)
78306f32e7eSjoerg return OffsetInRange;
78406f32e7eSjoerg
78506f32e7eSjoerg // See if the intrinsic is used in the following common pattern:
78606f32e7eSjoerg // br(llvm.type.test(...), thenbb, elsebb)
78706f32e7eSjoerg // where nothing happens between the type test and the br.
78806f32e7eSjoerg // If so, create slightly simpler IR.
78906f32e7eSjoerg if (CI->hasOneUse())
79006f32e7eSjoerg if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin()))
79106f32e7eSjoerg if (CI->getNextNode() == Br) {
79206f32e7eSjoerg BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator());
79306f32e7eSjoerg BasicBlock *Else = Br->getSuccessor(1);
79406f32e7eSjoerg BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange);
79506f32e7eSjoerg NewBr->setMetadata(LLVMContext::MD_prof,
79606f32e7eSjoerg Br->getMetadata(LLVMContext::MD_prof));
79706f32e7eSjoerg ReplaceInstWithInst(InitialBB->getTerminator(), NewBr);
79806f32e7eSjoerg
79906f32e7eSjoerg // Update phis in Else resulting from InitialBB being split
80006f32e7eSjoerg for (auto &Phi : Else->phis())
80106f32e7eSjoerg Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB);
80206f32e7eSjoerg
80306f32e7eSjoerg IRBuilder<> ThenB(CI);
80406f32e7eSjoerg return createBitSetTest(ThenB, TIL, BitOffset);
80506f32e7eSjoerg }
80606f32e7eSjoerg
80706f32e7eSjoerg IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false));
80806f32e7eSjoerg
80906f32e7eSjoerg // Now that we know that the offset is in range and aligned, load the
81006f32e7eSjoerg // appropriate bit from the bitset.
81106f32e7eSjoerg Value *Bit = createBitSetTest(ThenB, TIL, BitOffset);
81206f32e7eSjoerg
81306f32e7eSjoerg // The value we want is 0 if we came directly from the initial block
81406f32e7eSjoerg // (having failed the range or alignment checks), or the loaded bit if
81506f32e7eSjoerg // we came from the block in which we loaded it.
81606f32e7eSjoerg B.SetInsertPoint(CI);
81706f32e7eSjoerg PHINode *P = B.CreatePHI(Int1Ty, 2);
81806f32e7eSjoerg P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
81906f32e7eSjoerg P->addIncoming(Bit, ThenB.GetInsertBlock());
82006f32e7eSjoerg return P;
82106f32e7eSjoerg }
82206f32e7eSjoerg
82306f32e7eSjoerg /// Given a disjoint set of type identifiers and globals, lay out the globals,
82406f32e7eSjoerg /// build the bit sets and lower the llvm.type.test calls.
buildBitSetsFromGlobalVariables(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Globals)82506f32e7eSjoerg void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
82606f32e7eSjoerg ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
82706f32e7eSjoerg // Build a new global with the combined contents of the referenced globals.
82806f32e7eSjoerg // This global is a struct whose even-indexed elements contain the original
82906f32e7eSjoerg // contents of the referenced globals and whose odd-indexed elements contain
83006f32e7eSjoerg // any padding required to align the next element to the next power of 2 plus
83106f32e7eSjoerg // any additional padding required to meet its alignment requirements.
83206f32e7eSjoerg std::vector<Constant *> GlobalInits;
83306f32e7eSjoerg const DataLayout &DL = M.getDataLayout();
83406f32e7eSjoerg DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
83506f32e7eSjoerg Align MaxAlign;
83606f32e7eSjoerg uint64_t CurOffset = 0;
83706f32e7eSjoerg uint64_t DesiredPadding = 0;
83806f32e7eSjoerg for (GlobalTypeMember *G : Globals) {
83906f32e7eSjoerg auto *GV = cast<GlobalVariable>(G->getGlobal());
840*da58b97aSjoerg Align Alignment =
841*da58b97aSjoerg DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType());
842*da58b97aSjoerg MaxAlign = std::max(MaxAlign, Alignment);
843*da58b97aSjoerg uint64_t GVOffset = alignTo(CurOffset + DesiredPadding, Alignment);
84406f32e7eSjoerg GlobalLayout[G] = GVOffset;
84506f32e7eSjoerg if (GVOffset != 0) {
84606f32e7eSjoerg uint64_t Padding = GVOffset - CurOffset;
84706f32e7eSjoerg GlobalInits.push_back(
84806f32e7eSjoerg ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding)));
84906f32e7eSjoerg }
85006f32e7eSjoerg
85106f32e7eSjoerg GlobalInits.push_back(GV->getInitializer());
85206f32e7eSjoerg uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
85306f32e7eSjoerg CurOffset = GVOffset + InitSize;
85406f32e7eSjoerg
85506f32e7eSjoerg // Compute the amount of padding that we'd like for the next element.
85606f32e7eSjoerg DesiredPadding = NextPowerOf2(InitSize - 1) - InitSize;
85706f32e7eSjoerg
85806f32e7eSjoerg // Experiments of different caps with Chromium on both x64 and ARM64
85906f32e7eSjoerg // have shown that the 32-byte cap generates the smallest binary on
86006f32e7eSjoerg // both platforms while different caps yield similar performance.
86106f32e7eSjoerg // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html)
86206f32e7eSjoerg if (DesiredPadding > 32)
86306f32e7eSjoerg DesiredPadding = alignTo(InitSize, 32) - InitSize;
86406f32e7eSjoerg }
86506f32e7eSjoerg
86606f32e7eSjoerg Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits);
86706f32e7eSjoerg auto *CombinedGlobal =
86806f32e7eSjoerg new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true,
86906f32e7eSjoerg GlobalValue::PrivateLinkage, NewInit);
87006f32e7eSjoerg CombinedGlobal->setAlignment(MaxAlign);
87106f32e7eSjoerg
87206f32e7eSjoerg StructType *NewTy = cast<StructType>(NewInit->getType());
87306f32e7eSjoerg lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
87406f32e7eSjoerg
87506f32e7eSjoerg // Build aliases pointing to offsets into the combined global for each
87606f32e7eSjoerg // global from which we built the combined global, and replace references
87706f32e7eSjoerg // to the original globals with references to the aliases.
87806f32e7eSjoerg for (unsigned I = 0; I != Globals.size(); ++I) {
87906f32e7eSjoerg GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
88006f32e7eSjoerg
88106f32e7eSjoerg // Multiply by 2 to account for padding elements.
88206f32e7eSjoerg Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0),
88306f32e7eSjoerg ConstantInt::get(Int32Ty, I * 2)};
88406f32e7eSjoerg Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr(
88506f32e7eSjoerg NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs);
88606f32e7eSjoerg assert(GV->getType()->getAddressSpace() == 0);
88706f32e7eSjoerg GlobalAlias *GAlias =
88806f32e7eSjoerg GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(),
88906f32e7eSjoerg "", CombinedGlobalElemPtr, &M);
89006f32e7eSjoerg GAlias->setVisibility(GV->getVisibility());
89106f32e7eSjoerg GAlias->takeName(GV);
89206f32e7eSjoerg GV->replaceAllUsesWith(GAlias);
89306f32e7eSjoerg GV->eraseFromParent();
89406f32e7eSjoerg }
89506f32e7eSjoerg }
89606f32e7eSjoerg
shouldExportConstantsAsAbsoluteSymbols()89706f32e7eSjoerg bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
89806f32e7eSjoerg return (Arch == Triple::x86 || Arch == Triple::x86_64) &&
89906f32e7eSjoerg ObjectFormat == Triple::ELF;
90006f32e7eSjoerg }
90106f32e7eSjoerg
90206f32e7eSjoerg /// Export the given type identifier so that ThinLTO backends may import it.
90306f32e7eSjoerg /// Type identifiers are exported by adding coarse-grained information about how
90406f32e7eSjoerg /// to test the type identifier to the summary, and creating symbols in the
90506f32e7eSjoerg /// object file (aliases and absolute symbols) containing fine-grained
90606f32e7eSjoerg /// information about the type identifier.
90706f32e7eSjoerg ///
90806f32e7eSjoerg /// Returns a pointer to the location in which to store the bitmask, if
90906f32e7eSjoerg /// applicable.
exportTypeId(StringRef TypeId,const TypeIdLowering & TIL)91006f32e7eSjoerg uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId,
91106f32e7eSjoerg const TypeIdLowering &TIL) {
91206f32e7eSjoerg TypeTestResolution &TTRes =
91306f32e7eSjoerg ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes;
91406f32e7eSjoerg TTRes.TheKind = TIL.TheKind;
91506f32e7eSjoerg
91606f32e7eSjoerg auto ExportGlobal = [&](StringRef Name, Constant *C) {
91706f32e7eSjoerg GlobalAlias *GA =
91806f32e7eSjoerg GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
91906f32e7eSjoerg "__typeid_" + TypeId + "_" + Name, C, &M);
92006f32e7eSjoerg GA->setVisibility(GlobalValue::HiddenVisibility);
92106f32e7eSjoerg };
92206f32e7eSjoerg
92306f32e7eSjoerg auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) {
92406f32e7eSjoerg if (shouldExportConstantsAsAbsoluteSymbols())
92506f32e7eSjoerg ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy));
92606f32e7eSjoerg else
92706f32e7eSjoerg Storage = cast<ConstantInt>(C)->getZExtValue();
92806f32e7eSjoerg };
92906f32e7eSjoerg
93006f32e7eSjoerg if (TIL.TheKind != TypeTestResolution::Unsat)
93106f32e7eSjoerg ExportGlobal("global_addr", TIL.OffsetedGlobal);
93206f32e7eSjoerg
93306f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::ByteArray ||
93406f32e7eSjoerg TIL.TheKind == TypeTestResolution::Inline ||
93506f32e7eSjoerg TIL.TheKind == TypeTestResolution::AllOnes) {
93606f32e7eSjoerg ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2);
93706f32e7eSjoerg ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1);
93806f32e7eSjoerg
93906f32e7eSjoerg uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
94006f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Inline)
94106f32e7eSjoerg TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6;
94206f32e7eSjoerg else
94306f32e7eSjoerg TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32;
94406f32e7eSjoerg }
94506f32e7eSjoerg
94606f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::ByteArray) {
94706f32e7eSjoerg ExportGlobal("byte_array", TIL.TheByteArray);
94806f32e7eSjoerg if (shouldExportConstantsAsAbsoluteSymbols())
94906f32e7eSjoerg ExportGlobal("bit_mask", TIL.BitMask);
95006f32e7eSjoerg else
95106f32e7eSjoerg return &TTRes.BitMask;
95206f32e7eSjoerg }
95306f32e7eSjoerg
95406f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Inline)
95506f32e7eSjoerg ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits);
95606f32e7eSjoerg
95706f32e7eSjoerg return nullptr;
95806f32e7eSjoerg }
95906f32e7eSjoerg
96006f32e7eSjoerg LowerTypeTestsModule::TypeIdLowering
importTypeId(StringRef TypeId)96106f32e7eSjoerg LowerTypeTestsModule::importTypeId(StringRef TypeId) {
96206f32e7eSjoerg const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId);
96306f32e7eSjoerg if (!TidSummary)
96406f32e7eSjoerg return {}; // Unsat: no globals match this type id.
96506f32e7eSjoerg const TypeTestResolution &TTRes = TidSummary->TTRes;
96606f32e7eSjoerg
96706f32e7eSjoerg TypeIdLowering TIL;
96806f32e7eSjoerg TIL.TheKind = TTRes.TheKind;
96906f32e7eSjoerg
97006f32e7eSjoerg auto ImportGlobal = [&](StringRef Name) {
97106f32e7eSjoerg // Give the global a type of length 0 so that it is not assumed not to alias
97206f32e7eSjoerg // with any other global.
97306f32e7eSjoerg Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(),
97406f32e7eSjoerg Int8Arr0Ty);
97506f32e7eSjoerg if (auto *GV = dyn_cast<GlobalVariable>(C))
97606f32e7eSjoerg GV->setVisibility(GlobalValue::HiddenVisibility);
97706f32e7eSjoerg C = ConstantExpr::getBitCast(C, Int8PtrTy);
97806f32e7eSjoerg return C;
97906f32e7eSjoerg };
98006f32e7eSjoerg
98106f32e7eSjoerg auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth,
98206f32e7eSjoerg Type *Ty) {
98306f32e7eSjoerg if (!shouldExportConstantsAsAbsoluteSymbols()) {
98406f32e7eSjoerg Constant *C =
98506f32e7eSjoerg ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const);
98606f32e7eSjoerg if (!isa<IntegerType>(Ty))
98706f32e7eSjoerg C = ConstantExpr::getIntToPtr(C, Ty);
98806f32e7eSjoerg return C;
98906f32e7eSjoerg }
99006f32e7eSjoerg
99106f32e7eSjoerg Constant *C = ImportGlobal(Name);
99206f32e7eSjoerg auto *GV = cast<GlobalVariable>(C->stripPointerCasts());
99306f32e7eSjoerg if (isa<IntegerType>(Ty))
99406f32e7eSjoerg C = ConstantExpr::getPtrToInt(C, Ty);
99506f32e7eSjoerg if (GV->getMetadata(LLVMContext::MD_absolute_symbol))
99606f32e7eSjoerg return C;
99706f32e7eSjoerg
99806f32e7eSjoerg auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
99906f32e7eSjoerg auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min));
100006f32e7eSjoerg auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max));
100106f32e7eSjoerg GV->setMetadata(LLVMContext::MD_absolute_symbol,
100206f32e7eSjoerg MDNode::get(M.getContext(), {MinC, MaxC}));
100306f32e7eSjoerg };
100406f32e7eSjoerg if (AbsWidth == IntPtrTy->getBitWidth())
100506f32e7eSjoerg SetAbsRange(~0ull, ~0ull); // Full set.
100606f32e7eSjoerg else
100706f32e7eSjoerg SetAbsRange(0, 1ull << AbsWidth);
100806f32e7eSjoerg return C;
100906f32e7eSjoerg };
101006f32e7eSjoerg
101106f32e7eSjoerg if (TIL.TheKind != TypeTestResolution::Unsat)
101206f32e7eSjoerg TIL.OffsetedGlobal = ImportGlobal("global_addr");
101306f32e7eSjoerg
101406f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::ByteArray ||
101506f32e7eSjoerg TIL.TheKind == TypeTestResolution::Inline ||
101606f32e7eSjoerg TIL.TheKind == TypeTestResolution::AllOnes) {
101706f32e7eSjoerg TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty);
101806f32e7eSjoerg TIL.SizeM1 =
101906f32e7eSjoerg ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy);
102006f32e7eSjoerg }
102106f32e7eSjoerg
102206f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::ByteArray) {
102306f32e7eSjoerg TIL.TheByteArray = ImportGlobal("byte_array");
102406f32e7eSjoerg TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy);
102506f32e7eSjoerg }
102606f32e7eSjoerg
102706f32e7eSjoerg if (TIL.TheKind == TypeTestResolution::Inline)
102806f32e7eSjoerg TIL.InlineBits = ImportConstant(
102906f32e7eSjoerg "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth,
103006f32e7eSjoerg TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty);
103106f32e7eSjoerg
103206f32e7eSjoerg return TIL;
103306f32e7eSjoerg }
103406f32e7eSjoerg
importTypeTest(CallInst * CI)103506f32e7eSjoerg void LowerTypeTestsModule::importTypeTest(CallInst *CI) {
103606f32e7eSjoerg auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
103706f32e7eSjoerg if (!TypeIdMDVal)
103806f32e7eSjoerg report_fatal_error("Second argument of llvm.type.test must be metadata");
103906f32e7eSjoerg
104006f32e7eSjoerg auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
1041*da58b97aSjoerg // If this is a local unpromoted type, which doesn't have a metadata string,
1042*da58b97aSjoerg // treat as Unknown and delay lowering, so that we can still utilize it for
1043*da58b97aSjoerg // later optimizations.
104406f32e7eSjoerg if (!TypeIdStr)
1045*da58b97aSjoerg return;
104606f32e7eSjoerg
104706f32e7eSjoerg TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
104806f32e7eSjoerg Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
1049*da58b97aSjoerg if (Lowered) {
105006f32e7eSjoerg CI->replaceAllUsesWith(Lowered);
105106f32e7eSjoerg CI->eraseFromParent();
105206f32e7eSjoerg }
1053*da58b97aSjoerg }
105406f32e7eSjoerg
105506f32e7eSjoerg // ThinLTO backend: the function F has a jump table entry; update this module
105606f32e7eSjoerg // accordingly. isJumpTableCanonical describes the type of the jump table entry.
importFunction(Function * F,bool isJumpTableCanonical,std::vector<GlobalAlias * > & AliasesToErase)105706f32e7eSjoerg void LowerTypeTestsModule::importFunction(
105806f32e7eSjoerg Function *F, bool isJumpTableCanonical,
105906f32e7eSjoerg std::vector<GlobalAlias *> &AliasesToErase) {
106006f32e7eSjoerg assert(F->getType()->getAddressSpace() == 0);
106106f32e7eSjoerg
106206f32e7eSjoerg GlobalValue::VisibilityTypes Visibility = F->getVisibility();
1063*da58b97aSjoerg std::string Name = std::string(F->getName());
106406f32e7eSjoerg
106506f32e7eSjoerg if (F->isDeclarationForLinker() && isJumpTableCanonical) {
106606f32e7eSjoerg // Non-dso_local functions may be overriden at run time,
106706f32e7eSjoerg // don't short curcuit them
106806f32e7eSjoerg if (F->isDSOLocal()) {
106906f32e7eSjoerg Function *RealF = Function::Create(F->getFunctionType(),
107006f32e7eSjoerg GlobalValue::ExternalLinkage,
107106f32e7eSjoerg F->getAddressSpace(),
107206f32e7eSjoerg Name + ".cfi", &M);
107306f32e7eSjoerg RealF->setVisibility(GlobalVariable::HiddenVisibility);
107406f32e7eSjoerg replaceDirectCalls(F, RealF);
107506f32e7eSjoerg }
107606f32e7eSjoerg return;
107706f32e7eSjoerg }
107806f32e7eSjoerg
107906f32e7eSjoerg Function *FDecl;
108006f32e7eSjoerg if (!isJumpTableCanonical) {
108106f32e7eSjoerg // Either a declaration of an external function or a reference to a locally
108206f32e7eSjoerg // defined jump table.
108306f32e7eSjoerg FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
108406f32e7eSjoerg F->getAddressSpace(), Name + ".cfi_jt", &M);
108506f32e7eSjoerg FDecl->setVisibility(GlobalValue::HiddenVisibility);
108606f32e7eSjoerg } else {
108706f32e7eSjoerg F->setName(Name + ".cfi");
108806f32e7eSjoerg F->setLinkage(GlobalValue::ExternalLinkage);
108906f32e7eSjoerg FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage,
109006f32e7eSjoerg F->getAddressSpace(), Name, &M);
109106f32e7eSjoerg FDecl->setVisibility(Visibility);
109206f32e7eSjoerg Visibility = GlobalValue::HiddenVisibility;
109306f32e7eSjoerg
109406f32e7eSjoerg // Delete aliases pointing to this function, they'll be re-created in the
109506f32e7eSjoerg // merged output. Don't do it yet though because ScopedSaveAliaseesAndUsed
109606f32e7eSjoerg // will want to reset the aliasees first.
109706f32e7eSjoerg for (auto &U : F->uses()) {
109806f32e7eSjoerg if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
109906f32e7eSjoerg Function *AliasDecl = Function::Create(
110006f32e7eSjoerg F->getFunctionType(), GlobalValue::ExternalLinkage,
110106f32e7eSjoerg F->getAddressSpace(), "", &M);
110206f32e7eSjoerg AliasDecl->takeName(A);
110306f32e7eSjoerg A->replaceAllUsesWith(AliasDecl);
110406f32e7eSjoerg AliasesToErase.push_back(A);
110506f32e7eSjoerg }
110606f32e7eSjoerg }
110706f32e7eSjoerg }
110806f32e7eSjoerg
110906f32e7eSjoerg if (F->hasExternalWeakLinkage())
111006f32e7eSjoerg replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isJumpTableCanonical);
111106f32e7eSjoerg else
111206f32e7eSjoerg replaceCfiUses(F, FDecl, isJumpTableCanonical);
111306f32e7eSjoerg
111406f32e7eSjoerg // Set visibility late because it's used in replaceCfiUses() to determine
111506f32e7eSjoerg // whether uses need to to be replaced.
111606f32e7eSjoerg F->setVisibility(Visibility);
111706f32e7eSjoerg }
111806f32e7eSjoerg
lowerTypeTestCalls(ArrayRef<Metadata * > TypeIds,Constant * CombinedGlobalAddr,const DenseMap<GlobalTypeMember *,uint64_t> & GlobalLayout)111906f32e7eSjoerg void LowerTypeTestsModule::lowerTypeTestCalls(
112006f32e7eSjoerg ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
112106f32e7eSjoerg const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
112206f32e7eSjoerg CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy);
112306f32e7eSjoerg
112406f32e7eSjoerg // For each type identifier in this disjoint set...
112506f32e7eSjoerg for (Metadata *TypeId : TypeIds) {
112606f32e7eSjoerg // Build the bitset.
112706f32e7eSjoerg BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
112806f32e7eSjoerg LLVM_DEBUG({
112906f32e7eSjoerg if (auto MDS = dyn_cast<MDString>(TypeId))
113006f32e7eSjoerg dbgs() << MDS->getString() << ": ";
113106f32e7eSjoerg else
113206f32e7eSjoerg dbgs() << "<unnamed>: ";
113306f32e7eSjoerg BSI.print(dbgs());
113406f32e7eSjoerg });
113506f32e7eSjoerg
113606f32e7eSjoerg ByteArrayInfo *BAI = nullptr;
113706f32e7eSjoerg TypeIdLowering TIL;
113806f32e7eSjoerg TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
113906f32e7eSjoerg Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
114006f32e7eSjoerg TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
114106f32e7eSjoerg TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1);
114206f32e7eSjoerg if (BSI.isAllOnes()) {
114306f32e7eSjoerg TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
114406f32e7eSjoerg : TypeTestResolution::AllOnes;
114506f32e7eSjoerg } else if (BSI.BitSize <= 64) {
114606f32e7eSjoerg TIL.TheKind = TypeTestResolution::Inline;
114706f32e7eSjoerg uint64_t InlineBits = 0;
114806f32e7eSjoerg for (auto Bit : BSI.Bits)
114906f32e7eSjoerg InlineBits |= uint64_t(1) << Bit;
115006f32e7eSjoerg if (InlineBits == 0)
115106f32e7eSjoerg TIL.TheKind = TypeTestResolution::Unsat;
115206f32e7eSjoerg else
115306f32e7eSjoerg TIL.InlineBits = ConstantInt::get(
115406f32e7eSjoerg (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
115506f32e7eSjoerg } else {
115606f32e7eSjoerg TIL.TheKind = TypeTestResolution::ByteArray;
115706f32e7eSjoerg ++NumByteArraysCreated;
115806f32e7eSjoerg BAI = createByteArray(BSI);
115906f32e7eSjoerg TIL.TheByteArray = BAI->ByteArray;
116006f32e7eSjoerg TIL.BitMask = BAI->MaskGlobal;
116106f32e7eSjoerg }
116206f32e7eSjoerg
116306f32e7eSjoerg TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
116406f32e7eSjoerg
116506f32e7eSjoerg if (TIUI.IsExported) {
116606f32e7eSjoerg uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
116706f32e7eSjoerg if (BAI)
116806f32e7eSjoerg BAI->MaskPtr = MaskPtr;
116906f32e7eSjoerg }
117006f32e7eSjoerg
117106f32e7eSjoerg // Lower each call to llvm.type.test for this type identifier.
117206f32e7eSjoerg for (CallInst *CI : TIUI.CallSites) {
117306f32e7eSjoerg ++NumTypeTestCallsLowered;
117406f32e7eSjoerg Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1175*da58b97aSjoerg if (Lowered) {
117606f32e7eSjoerg CI->replaceAllUsesWith(Lowered);
117706f32e7eSjoerg CI->eraseFromParent();
117806f32e7eSjoerg }
117906f32e7eSjoerg }
118006f32e7eSjoerg }
1181*da58b97aSjoerg }
118206f32e7eSjoerg
verifyTypeMDNode(GlobalObject * GO,MDNode * Type)118306f32e7eSjoerg void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
118406f32e7eSjoerg if (Type->getNumOperands() != 2)
118506f32e7eSjoerg report_fatal_error("All operands of type metadata must have 2 elements");
118606f32e7eSjoerg
118706f32e7eSjoerg if (GO->isThreadLocal())
118806f32e7eSjoerg report_fatal_error("Bit set element may not be thread-local");
118906f32e7eSjoerg if (isa<GlobalVariable>(GO) && GO->hasSection())
119006f32e7eSjoerg report_fatal_error(
119106f32e7eSjoerg "A member of a type identifier may not have an explicit section");
119206f32e7eSjoerg
119306f32e7eSjoerg // FIXME: We previously checked that global var member of a type identifier
119406f32e7eSjoerg // must be a definition, but the IR linker may leave type metadata on
119506f32e7eSjoerg // declarations. We should restore this check after fixing PR31759.
119606f32e7eSjoerg
119706f32e7eSjoerg auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0));
119806f32e7eSjoerg if (!OffsetConstMD)
119906f32e7eSjoerg report_fatal_error("Type offset must be a constant");
120006f32e7eSjoerg auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
120106f32e7eSjoerg if (!OffsetInt)
120206f32e7eSjoerg report_fatal_error("Type offset must be an integer constant");
120306f32e7eSjoerg }
120406f32e7eSjoerg
120506f32e7eSjoerg static const unsigned kX86JumpTableEntrySize = 8;
120606f32e7eSjoerg static const unsigned kARMJumpTableEntrySize = 4;
1207*da58b97aSjoerg static const unsigned kARMBTIJumpTableEntrySize = 8;
120806f32e7eSjoerg
getJumpTableEntrySize()120906f32e7eSjoerg unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
121006f32e7eSjoerg switch (Arch) {
121106f32e7eSjoerg case Triple::x86:
121206f32e7eSjoerg case Triple::x86_64:
121306f32e7eSjoerg return kX86JumpTableEntrySize;
121406f32e7eSjoerg case Triple::arm:
121506f32e7eSjoerg case Triple::thumb:
1216*da58b97aSjoerg return kARMJumpTableEntrySize;
121706f32e7eSjoerg case Triple::aarch64:
1218*da58b97aSjoerg if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1219*da58b97aSjoerg M.getModuleFlag("branch-target-enforcement")))
1220*da58b97aSjoerg if (BTE->getZExtValue())
1221*da58b97aSjoerg return kARMBTIJumpTableEntrySize;
122206f32e7eSjoerg return kARMJumpTableEntrySize;
122306f32e7eSjoerg default:
122406f32e7eSjoerg report_fatal_error("Unsupported architecture for jump tables");
122506f32e7eSjoerg }
122606f32e7eSjoerg }
122706f32e7eSjoerg
122806f32e7eSjoerg // Create a jump table entry for the target. This consists of an instruction
122906f32e7eSjoerg // sequence containing a relative branch to Dest. Appends inline asm text,
123006f32e7eSjoerg // constraints and arguments to AsmOS, ConstraintOS and AsmArgs.
createJumpTableEntry(raw_ostream & AsmOS,raw_ostream & ConstraintOS,Triple::ArchType JumpTableArch,SmallVectorImpl<Value * > & AsmArgs,Function * Dest)123106f32e7eSjoerg void LowerTypeTestsModule::createJumpTableEntry(
123206f32e7eSjoerg raw_ostream &AsmOS, raw_ostream &ConstraintOS,
123306f32e7eSjoerg Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs,
123406f32e7eSjoerg Function *Dest) {
123506f32e7eSjoerg unsigned ArgIndex = AsmArgs.size();
123606f32e7eSjoerg
123706f32e7eSjoerg if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) {
123806f32e7eSjoerg AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n";
123906f32e7eSjoerg AsmOS << "int3\nint3\nint3\n";
1240*da58b97aSjoerg } else if (JumpTableArch == Triple::arm) {
1241*da58b97aSjoerg AsmOS << "b $" << ArgIndex << "\n";
1242*da58b97aSjoerg } else if (JumpTableArch == Triple::aarch64) {
1243*da58b97aSjoerg if (const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1244*da58b97aSjoerg Dest->getParent()->getModuleFlag("branch-target-enforcement")))
1245*da58b97aSjoerg if (BTE->getZExtValue())
1246*da58b97aSjoerg AsmOS << "bti c\n";
124706f32e7eSjoerg AsmOS << "b $" << ArgIndex << "\n";
124806f32e7eSjoerg } else if (JumpTableArch == Triple::thumb) {
124906f32e7eSjoerg AsmOS << "b.w $" << ArgIndex << "\n";
125006f32e7eSjoerg } else {
125106f32e7eSjoerg report_fatal_error("Unsupported architecture for jump tables");
125206f32e7eSjoerg }
125306f32e7eSjoerg
125406f32e7eSjoerg ConstraintOS << (ArgIndex > 0 ? ",s" : "s");
125506f32e7eSjoerg AsmArgs.push_back(Dest);
125606f32e7eSjoerg }
125706f32e7eSjoerg
getJumpTableEntryType()125806f32e7eSjoerg Type *LowerTypeTestsModule::getJumpTableEntryType() {
125906f32e7eSjoerg return ArrayType::get(Int8Ty, getJumpTableEntrySize());
126006f32e7eSjoerg }
126106f32e7eSjoerg
126206f32e7eSjoerg /// Given a disjoint set of type identifiers and functions, build the bit sets
126306f32e7eSjoerg /// and lower the llvm.type.test calls, architecture dependently.
buildBitSetsFromFunctions(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)126406f32e7eSjoerg void LowerTypeTestsModule::buildBitSetsFromFunctions(
126506f32e7eSjoerg ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
126606f32e7eSjoerg if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
126706f32e7eSjoerg Arch == Triple::thumb || Arch == Triple::aarch64)
126806f32e7eSjoerg buildBitSetsFromFunctionsNative(TypeIds, Functions);
126906f32e7eSjoerg else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
127006f32e7eSjoerg buildBitSetsFromFunctionsWASM(TypeIds, Functions);
127106f32e7eSjoerg else
127206f32e7eSjoerg report_fatal_error("Unsupported architecture for jump tables");
127306f32e7eSjoerg }
127406f32e7eSjoerg
moveInitializerToModuleConstructor(GlobalVariable * GV)127506f32e7eSjoerg void LowerTypeTestsModule::moveInitializerToModuleConstructor(
127606f32e7eSjoerg GlobalVariable *GV) {
127706f32e7eSjoerg if (WeakInitializerFn == nullptr) {
127806f32e7eSjoerg WeakInitializerFn = Function::Create(
127906f32e7eSjoerg FunctionType::get(Type::getVoidTy(M.getContext()),
128006f32e7eSjoerg /* IsVarArg */ false),
128106f32e7eSjoerg GlobalValue::InternalLinkage,
128206f32e7eSjoerg M.getDataLayout().getProgramAddressSpace(),
128306f32e7eSjoerg "__cfi_global_var_init", &M);
128406f32e7eSjoerg BasicBlock *BB =
128506f32e7eSjoerg BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn);
128606f32e7eSjoerg ReturnInst::Create(M.getContext(), BB);
128706f32e7eSjoerg WeakInitializerFn->setSection(
128806f32e7eSjoerg ObjectFormat == Triple::MachO
128906f32e7eSjoerg ? "__TEXT,__StaticInit,regular,pure_instructions"
129006f32e7eSjoerg : ".text.startup");
129106f32e7eSjoerg // This code is equivalent to relocation application, and should run at the
129206f32e7eSjoerg // earliest possible time (i.e. with the highest priority).
129306f32e7eSjoerg appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0);
129406f32e7eSjoerg }
129506f32e7eSjoerg
129606f32e7eSjoerg IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
129706f32e7eSjoerg GV->setConstant(false);
1298*da58b97aSjoerg IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlign());
129906f32e7eSjoerg GV->setInitializer(Constant::getNullValue(GV->getValueType()));
130006f32e7eSjoerg }
130106f32e7eSjoerg
findGlobalVariableUsersOf(Constant * C,SmallSetVector<GlobalVariable *,8> & Out)130206f32e7eSjoerg void LowerTypeTestsModule::findGlobalVariableUsersOf(
130306f32e7eSjoerg Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) {
130406f32e7eSjoerg for (auto *U : C->users()){
130506f32e7eSjoerg if (auto *GV = dyn_cast<GlobalVariable>(U))
130606f32e7eSjoerg Out.insert(GV);
130706f32e7eSjoerg else if (auto *C2 = dyn_cast<Constant>(U))
130806f32e7eSjoerg findGlobalVariableUsersOf(C2, Out);
130906f32e7eSjoerg }
131006f32e7eSjoerg }
131106f32e7eSjoerg
131206f32e7eSjoerg // Replace all uses of F with (F ? JT : 0).
replaceWeakDeclarationWithJumpTablePtr(Function * F,Constant * JT,bool IsJumpTableCanonical)131306f32e7eSjoerg void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
131406f32e7eSjoerg Function *F, Constant *JT, bool IsJumpTableCanonical) {
131506f32e7eSjoerg // The target expression can not appear in a constant initializer on most
131606f32e7eSjoerg // (all?) targets. Switch to a runtime initializer.
131706f32e7eSjoerg SmallSetVector<GlobalVariable *, 8> GlobalVarUsers;
131806f32e7eSjoerg findGlobalVariableUsersOf(F, GlobalVarUsers);
131906f32e7eSjoerg for (auto GV : GlobalVarUsers)
132006f32e7eSjoerg moveInitializerToModuleConstructor(GV);
132106f32e7eSjoerg
132206f32e7eSjoerg // Can not RAUW F with an expression that uses F. Replace with a temporary
132306f32e7eSjoerg // placeholder first.
132406f32e7eSjoerg Function *PlaceholderFn =
132506f32e7eSjoerg Function::Create(cast<FunctionType>(F->getValueType()),
132606f32e7eSjoerg GlobalValue::ExternalWeakLinkage,
132706f32e7eSjoerg F->getAddressSpace(), "", &M);
132806f32e7eSjoerg replaceCfiUses(F, PlaceholderFn, IsJumpTableCanonical);
132906f32e7eSjoerg
133006f32e7eSjoerg Constant *Target = ConstantExpr::getSelect(
133106f32e7eSjoerg ConstantExpr::getICmp(CmpInst::ICMP_NE, F,
133206f32e7eSjoerg Constant::getNullValue(F->getType())),
133306f32e7eSjoerg JT, Constant::getNullValue(F->getType()));
133406f32e7eSjoerg PlaceholderFn->replaceAllUsesWith(Target);
133506f32e7eSjoerg PlaceholderFn->eraseFromParent();
133606f32e7eSjoerg }
133706f32e7eSjoerg
isThumbFunction(Function * F,Triple::ArchType ModuleArch)133806f32e7eSjoerg static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) {
133906f32e7eSjoerg Attribute TFAttr = F->getFnAttribute("target-features");
1340*da58b97aSjoerg if (TFAttr.isValid()) {
134106f32e7eSjoerg SmallVector<StringRef, 6> Features;
134206f32e7eSjoerg TFAttr.getValueAsString().split(Features, ',');
134306f32e7eSjoerg for (StringRef Feature : Features) {
134406f32e7eSjoerg if (Feature == "-thumb-mode")
134506f32e7eSjoerg return false;
134606f32e7eSjoerg else if (Feature == "+thumb-mode")
134706f32e7eSjoerg return true;
134806f32e7eSjoerg }
134906f32e7eSjoerg }
135006f32e7eSjoerg
135106f32e7eSjoerg return ModuleArch == Triple::thumb;
135206f32e7eSjoerg }
135306f32e7eSjoerg
135406f32e7eSjoerg // Each jump table must be either ARM or Thumb as a whole for the bit-test math
135506f32e7eSjoerg // to work. Pick one that matches the majority of members to minimize interop
135606f32e7eSjoerg // veneers inserted by the linker.
135706f32e7eSjoerg static Triple::ArchType
selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember * > Functions,Triple::ArchType ModuleArch)135806f32e7eSjoerg selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions,
135906f32e7eSjoerg Triple::ArchType ModuleArch) {
136006f32e7eSjoerg if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb)
136106f32e7eSjoerg return ModuleArch;
136206f32e7eSjoerg
136306f32e7eSjoerg unsigned ArmCount = 0, ThumbCount = 0;
136406f32e7eSjoerg for (const auto GTM : Functions) {
136506f32e7eSjoerg if (!GTM->isJumpTableCanonical()) {
136606f32e7eSjoerg // PLT stubs are always ARM.
136706f32e7eSjoerg // FIXME: This is the wrong heuristic for non-canonical jump tables.
136806f32e7eSjoerg ++ArmCount;
136906f32e7eSjoerg continue;
137006f32e7eSjoerg }
137106f32e7eSjoerg
137206f32e7eSjoerg Function *F = cast<Function>(GTM->getGlobal());
137306f32e7eSjoerg ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount);
137406f32e7eSjoerg }
137506f32e7eSjoerg
137606f32e7eSjoerg return ArmCount > ThumbCount ? Triple::arm : Triple::thumb;
137706f32e7eSjoerg }
137806f32e7eSjoerg
createJumpTable(Function * F,ArrayRef<GlobalTypeMember * > Functions)137906f32e7eSjoerg void LowerTypeTestsModule::createJumpTable(
138006f32e7eSjoerg Function *F, ArrayRef<GlobalTypeMember *> Functions) {
138106f32e7eSjoerg std::string AsmStr, ConstraintStr;
138206f32e7eSjoerg raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr);
138306f32e7eSjoerg SmallVector<Value *, 16> AsmArgs;
138406f32e7eSjoerg AsmArgs.reserve(Functions.size() * 2);
138506f32e7eSjoerg
138606f32e7eSjoerg Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch);
138706f32e7eSjoerg
138806f32e7eSjoerg for (unsigned I = 0; I != Functions.size(); ++I)
138906f32e7eSjoerg createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
139006f32e7eSjoerg cast<Function>(Functions[I]->getGlobal()));
139106f32e7eSjoerg
139206f32e7eSjoerg // Align the whole table by entry size.
139306f32e7eSjoerg F->setAlignment(Align(getJumpTableEntrySize()));
139406f32e7eSjoerg // Skip prologue.
139506f32e7eSjoerg // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
139606f32e7eSjoerg // Luckily, this function does not get any prologue even without the
139706f32e7eSjoerg // attribute.
139806f32e7eSjoerg if (OS != Triple::Win32)
139906f32e7eSjoerg F->addFnAttr(Attribute::Naked);
140006f32e7eSjoerg if (JumpTableArch == Triple::arm)
140106f32e7eSjoerg F->addFnAttr("target-features", "-thumb-mode");
140206f32e7eSjoerg if (JumpTableArch == Triple::thumb) {
140306f32e7eSjoerg F->addFnAttr("target-features", "+thumb-mode");
140406f32e7eSjoerg // Thumb jump table assembly needs Thumb2. The following attribute is added
140506f32e7eSjoerg // by Clang for -march=armv7.
140606f32e7eSjoerg F->addFnAttr("target-cpu", "cortex-a8");
140706f32e7eSjoerg }
1408*da58b97aSjoerg if (JumpTableArch == Triple::aarch64) {
1409*da58b97aSjoerg F->addFnAttr("branch-target-enforcement", "false");
1410*da58b97aSjoerg F->addFnAttr("sign-return-address", "none");
1411*da58b97aSjoerg }
141206f32e7eSjoerg // Make sure we don't emit .eh_frame for this function.
141306f32e7eSjoerg F->addFnAttr(Attribute::NoUnwind);
141406f32e7eSjoerg
141506f32e7eSjoerg BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F);
141606f32e7eSjoerg IRBuilder<> IRB(BB);
141706f32e7eSjoerg
141806f32e7eSjoerg SmallVector<Type *, 16> ArgTypes;
141906f32e7eSjoerg ArgTypes.reserve(AsmArgs.size());
142006f32e7eSjoerg for (const auto &Arg : AsmArgs)
142106f32e7eSjoerg ArgTypes.push_back(Arg->getType());
142206f32e7eSjoerg InlineAsm *JumpTableAsm =
142306f32e7eSjoerg InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false),
142406f32e7eSjoerg AsmOS.str(), ConstraintOS.str(),
142506f32e7eSjoerg /*hasSideEffects=*/true);
142606f32e7eSjoerg
142706f32e7eSjoerg IRB.CreateCall(JumpTableAsm, AsmArgs);
142806f32e7eSjoerg IRB.CreateUnreachable();
142906f32e7eSjoerg }
143006f32e7eSjoerg
143106f32e7eSjoerg /// Given a disjoint set of type identifiers and functions, build a jump table
143206f32e7eSjoerg /// for the functions, build the bit sets and lower the llvm.type.test calls.
buildBitSetsFromFunctionsNative(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)143306f32e7eSjoerg void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
143406f32e7eSjoerg ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
143506f32e7eSjoerg // Unlike the global bitset builder, the function bitset builder cannot
143606f32e7eSjoerg // re-arrange functions in a particular order and base its calculations on the
143706f32e7eSjoerg // layout of the functions' entry points, as we have no idea how large a
143806f32e7eSjoerg // particular function will end up being (the size could even depend on what
143906f32e7eSjoerg // this pass does!) Instead, we build a jump table, which is a block of code
144006f32e7eSjoerg // consisting of one branch instruction for each of the functions in the bit
144106f32e7eSjoerg // set that branches to the target function, and redirect any taken function
144206f32e7eSjoerg // addresses to the corresponding jump table entry. In the object file's
144306f32e7eSjoerg // symbol table, the symbols for the target functions also refer to the jump
144406f32e7eSjoerg // table entries, so that addresses taken outside the module will pass any
144506f32e7eSjoerg // verification done inside the module.
144606f32e7eSjoerg //
144706f32e7eSjoerg // In more concrete terms, suppose we have three functions f, g, h which are
144806f32e7eSjoerg // of the same type, and a function foo that returns their addresses:
144906f32e7eSjoerg //
145006f32e7eSjoerg // f:
145106f32e7eSjoerg // mov 0, %eax
145206f32e7eSjoerg // ret
145306f32e7eSjoerg //
145406f32e7eSjoerg // g:
145506f32e7eSjoerg // mov 1, %eax
145606f32e7eSjoerg // ret
145706f32e7eSjoerg //
145806f32e7eSjoerg // h:
145906f32e7eSjoerg // mov 2, %eax
146006f32e7eSjoerg // ret
146106f32e7eSjoerg //
146206f32e7eSjoerg // foo:
146306f32e7eSjoerg // mov f, %eax
146406f32e7eSjoerg // mov g, %edx
146506f32e7eSjoerg // mov h, %ecx
146606f32e7eSjoerg // ret
146706f32e7eSjoerg //
146806f32e7eSjoerg // We output the jump table as module-level inline asm string. The end result
146906f32e7eSjoerg // will (conceptually) look like this:
147006f32e7eSjoerg //
147106f32e7eSjoerg // f = .cfi.jumptable
147206f32e7eSjoerg // g = .cfi.jumptable + 4
147306f32e7eSjoerg // h = .cfi.jumptable + 8
147406f32e7eSjoerg // .cfi.jumptable:
147506f32e7eSjoerg // jmp f.cfi ; 5 bytes
147606f32e7eSjoerg // int3 ; 1 byte
147706f32e7eSjoerg // int3 ; 1 byte
147806f32e7eSjoerg // int3 ; 1 byte
147906f32e7eSjoerg // jmp g.cfi ; 5 bytes
148006f32e7eSjoerg // int3 ; 1 byte
148106f32e7eSjoerg // int3 ; 1 byte
148206f32e7eSjoerg // int3 ; 1 byte
148306f32e7eSjoerg // jmp h.cfi ; 5 bytes
148406f32e7eSjoerg // int3 ; 1 byte
148506f32e7eSjoerg // int3 ; 1 byte
148606f32e7eSjoerg // int3 ; 1 byte
148706f32e7eSjoerg //
148806f32e7eSjoerg // f.cfi:
148906f32e7eSjoerg // mov 0, %eax
149006f32e7eSjoerg // ret
149106f32e7eSjoerg //
149206f32e7eSjoerg // g.cfi:
149306f32e7eSjoerg // mov 1, %eax
149406f32e7eSjoerg // ret
149506f32e7eSjoerg //
149606f32e7eSjoerg // h.cfi:
149706f32e7eSjoerg // mov 2, %eax
149806f32e7eSjoerg // ret
149906f32e7eSjoerg //
150006f32e7eSjoerg // foo:
150106f32e7eSjoerg // mov f, %eax
150206f32e7eSjoerg // mov g, %edx
150306f32e7eSjoerg // mov h, %ecx
150406f32e7eSjoerg // ret
150506f32e7eSjoerg //
150606f32e7eSjoerg // Because the addresses of f, g, h are evenly spaced at a power of 2, in the
150706f32e7eSjoerg // normal case the check can be carried out using the same kind of simple
150806f32e7eSjoerg // arithmetic that we normally use for globals.
150906f32e7eSjoerg
151006f32e7eSjoerg // FIXME: find a better way to represent the jumptable in the IR.
151106f32e7eSjoerg assert(!Functions.empty());
151206f32e7eSjoerg
151306f32e7eSjoerg // Build a simple layout based on the regular layout of jump tables.
151406f32e7eSjoerg DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
151506f32e7eSjoerg unsigned EntrySize = getJumpTableEntrySize();
151606f32e7eSjoerg for (unsigned I = 0; I != Functions.size(); ++I)
151706f32e7eSjoerg GlobalLayout[Functions[I]] = I * EntrySize;
151806f32e7eSjoerg
151906f32e7eSjoerg Function *JumpTableFn =
152006f32e7eSjoerg Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()),
152106f32e7eSjoerg /* IsVarArg */ false),
152206f32e7eSjoerg GlobalValue::PrivateLinkage,
152306f32e7eSjoerg M.getDataLayout().getProgramAddressSpace(),
152406f32e7eSjoerg ".cfi.jumptable", &M);
152506f32e7eSjoerg ArrayType *JumpTableType =
152606f32e7eSjoerg ArrayType::get(getJumpTableEntryType(), Functions.size());
152706f32e7eSjoerg auto JumpTable =
152806f32e7eSjoerg ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
152906f32e7eSjoerg
153006f32e7eSjoerg lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
153106f32e7eSjoerg
153206f32e7eSjoerg {
153306f32e7eSjoerg ScopedSaveAliaseesAndUsed S(M);
153406f32e7eSjoerg
153506f32e7eSjoerg // Build aliases pointing to offsets into the jump table, and replace
153606f32e7eSjoerg // references to the original functions with references to the aliases.
153706f32e7eSjoerg for (unsigned I = 0; I != Functions.size(); ++I) {
153806f32e7eSjoerg Function *F = cast<Function>(Functions[I]->getGlobal());
153906f32e7eSjoerg bool IsJumpTableCanonical = Functions[I]->isJumpTableCanonical();
154006f32e7eSjoerg
154106f32e7eSjoerg Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
154206f32e7eSjoerg ConstantExpr::getInBoundsGetElementPtr(
154306f32e7eSjoerg JumpTableType, JumpTable,
154406f32e7eSjoerg ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0),
154506f32e7eSjoerg ConstantInt::get(IntPtrTy, I)}),
154606f32e7eSjoerg F->getType());
154706f32e7eSjoerg if (Functions[I]->isExported()) {
154806f32e7eSjoerg if (IsJumpTableCanonical) {
1549*da58b97aSjoerg ExportSummary->cfiFunctionDefs().insert(std::string(F->getName()));
155006f32e7eSjoerg } else {
155106f32e7eSjoerg GlobalAlias *JtAlias = GlobalAlias::create(
155206f32e7eSjoerg F->getValueType(), 0, GlobalValue::ExternalLinkage,
155306f32e7eSjoerg F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M);
155406f32e7eSjoerg JtAlias->setVisibility(GlobalValue::HiddenVisibility);
1555*da58b97aSjoerg ExportSummary->cfiFunctionDecls().insert(std::string(F->getName()));
155606f32e7eSjoerg }
155706f32e7eSjoerg }
155806f32e7eSjoerg if (!IsJumpTableCanonical) {
155906f32e7eSjoerg if (F->hasExternalWeakLinkage())
156006f32e7eSjoerg replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr,
156106f32e7eSjoerg IsJumpTableCanonical);
156206f32e7eSjoerg else
156306f32e7eSjoerg replaceCfiUses(F, CombinedGlobalElemPtr, IsJumpTableCanonical);
156406f32e7eSjoerg } else {
156506f32e7eSjoerg assert(F->getType()->getAddressSpace() == 0);
156606f32e7eSjoerg
156706f32e7eSjoerg GlobalAlias *FAlias =
156806f32e7eSjoerg GlobalAlias::create(F->getValueType(), 0, F->getLinkage(), "",
156906f32e7eSjoerg CombinedGlobalElemPtr, &M);
157006f32e7eSjoerg FAlias->setVisibility(F->getVisibility());
157106f32e7eSjoerg FAlias->takeName(F);
157206f32e7eSjoerg if (FAlias->hasName())
157306f32e7eSjoerg F->setName(FAlias->getName() + ".cfi");
157406f32e7eSjoerg replaceCfiUses(F, FAlias, IsJumpTableCanonical);
157506f32e7eSjoerg if (!F->hasLocalLinkage())
157606f32e7eSjoerg F->setVisibility(GlobalVariable::HiddenVisibility);
157706f32e7eSjoerg }
157806f32e7eSjoerg }
157906f32e7eSjoerg }
158006f32e7eSjoerg
158106f32e7eSjoerg createJumpTable(JumpTableFn, Functions);
158206f32e7eSjoerg }
158306f32e7eSjoerg
158406f32e7eSjoerg /// Assign a dummy layout using an incrementing counter, tag each function
158506f32e7eSjoerg /// with its index represented as metadata, and lower each type test to an
158606f32e7eSjoerg /// integer range comparison. During generation of the indirect function call
158706f32e7eSjoerg /// table in the backend, it will assign the given indexes.
158806f32e7eSjoerg /// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet
158906f32e7eSjoerg /// been finalized.
buildBitSetsFromFunctionsWASM(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Functions)159006f32e7eSjoerg void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
159106f32e7eSjoerg ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
159206f32e7eSjoerg assert(!Functions.empty());
159306f32e7eSjoerg
159406f32e7eSjoerg // Build consecutive monotonic integer ranges for each call target set
159506f32e7eSjoerg DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
159606f32e7eSjoerg
159706f32e7eSjoerg for (GlobalTypeMember *GTM : Functions) {
159806f32e7eSjoerg Function *F = cast<Function>(GTM->getGlobal());
159906f32e7eSjoerg
160006f32e7eSjoerg // Skip functions that are not address taken, to avoid bloating the table
160106f32e7eSjoerg if (!F->hasAddressTaken())
160206f32e7eSjoerg continue;
160306f32e7eSjoerg
160406f32e7eSjoerg // Store metadata with the index for each function
160506f32e7eSjoerg MDNode *MD = MDNode::get(F->getContext(),
160606f32e7eSjoerg ArrayRef<Metadata *>(ConstantAsMetadata::get(
160706f32e7eSjoerg ConstantInt::get(Int64Ty, IndirectIndex))));
160806f32e7eSjoerg F->setMetadata("wasm.index", MD);
160906f32e7eSjoerg
161006f32e7eSjoerg // Assign the counter value
161106f32e7eSjoerg GlobalLayout[GTM] = IndirectIndex++;
161206f32e7eSjoerg }
161306f32e7eSjoerg
161406f32e7eSjoerg // The indirect function table index space starts at zero, so pass a NULL
161506f32e7eSjoerg // pointer as the subtracted "jump table" offset.
161606f32e7eSjoerg lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
161706f32e7eSjoerg GlobalLayout);
161806f32e7eSjoerg }
161906f32e7eSjoerg
buildBitSetsFromDisjointSet(ArrayRef<Metadata * > TypeIds,ArrayRef<GlobalTypeMember * > Globals,ArrayRef<ICallBranchFunnel * > ICallBranchFunnels)162006f32e7eSjoerg void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
162106f32e7eSjoerg ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
162206f32e7eSjoerg ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) {
162306f32e7eSjoerg DenseMap<Metadata *, uint64_t> TypeIdIndices;
162406f32e7eSjoerg for (unsigned I = 0; I != TypeIds.size(); ++I)
162506f32e7eSjoerg TypeIdIndices[TypeIds[I]] = I;
162606f32e7eSjoerg
162706f32e7eSjoerg // For each type identifier, build a set of indices that refer to members of
162806f32e7eSjoerg // the type identifier.
162906f32e7eSjoerg std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
163006f32e7eSjoerg unsigned GlobalIndex = 0;
163106f32e7eSjoerg DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
163206f32e7eSjoerg for (GlobalTypeMember *GTM : Globals) {
163306f32e7eSjoerg for (MDNode *Type : GTM->types()) {
163406f32e7eSjoerg // Type = { offset, type identifier }
163506f32e7eSjoerg auto I = TypeIdIndices.find(Type->getOperand(1));
163606f32e7eSjoerg if (I != TypeIdIndices.end())
163706f32e7eSjoerg TypeMembers[I->second].insert(GlobalIndex);
163806f32e7eSjoerg }
163906f32e7eSjoerg GlobalIndices[GTM] = GlobalIndex;
164006f32e7eSjoerg GlobalIndex++;
164106f32e7eSjoerg }
164206f32e7eSjoerg
164306f32e7eSjoerg for (ICallBranchFunnel *JT : ICallBranchFunnels) {
164406f32e7eSjoerg TypeMembers.emplace_back();
164506f32e7eSjoerg std::set<uint64_t> &TMSet = TypeMembers.back();
164606f32e7eSjoerg for (GlobalTypeMember *T : JT->targets())
164706f32e7eSjoerg TMSet.insert(GlobalIndices[T]);
164806f32e7eSjoerg }
164906f32e7eSjoerg
165006f32e7eSjoerg // Order the sets of indices by size. The GlobalLayoutBuilder works best
165106f32e7eSjoerg // when given small index sets first.
165206f32e7eSjoerg llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1,
165306f32e7eSjoerg const std::set<uint64_t> &O2) {
165406f32e7eSjoerg return O1.size() < O2.size();
165506f32e7eSjoerg });
165606f32e7eSjoerg
165706f32e7eSjoerg // Create a GlobalLayoutBuilder and provide it with index sets as layout
165806f32e7eSjoerg // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as
165906f32e7eSjoerg // close together as possible.
166006f32e7eSjoerg GlobalLayoutBuilder GLB(Globals.size());
166106f32e7eSjoerg for (auto &&MemSet : TypeMembers)
166206f32e7eSjoerg GLB.addFragment(MemSet);
166306f32e7eSjoerg
166406f32e7eSjoerg // Build a vector of globals with the computed layout.
166506f32e7eSjoerg bool IsGlobalSet =
166606f32e7eSjoerg Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
166706f32e7eSjoerg std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
166806f32e7eSjoerg auto OGTMI = OrderedGTMs.begin();
166906f32e7eSjoerg for (auto &&F : GLB.Fragments) {
167006f32e7eSjoerg for (auto &&Offset : F) {
167106f32e7eSjoerg if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
167206f32e7eSjoerg report_fatal_error("Type identifier may not contain both global "
167306f32e7eSjoerg "variables and functions");
167406f32e7eSjoerg *OGTMI++ = Globals[Offset];
167506f32e7eSjoerg }
167606f32e7eSjoerg }
167706f32e7eSjoerg
167806f32e7eSjoerg // Build the bitsets from this disjoint set.
167906f32e7eSjoerg if (IsGlobalSet)
168006f32e7eSjoerg buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
168106f32e7eSjoerg else
168206f32e7eSjoerg buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
168306f32e7eSjoerg }
168406f32e7eSjoerg
168506f32e7eSjoerg /// Lower all type tests in this module.
LowerTypeTestsModule(Module & M,ModuleSummaryIndex * ExportSummary,const ModuleSummaryIndex * ImportSummary,bool DropTypeTests)168606f32e7eSjoerg LowerTypeTestsModule::LowerTypeTestsModule(
168706f32e7eSjoerg Module &M, ModuleSummaryIndex *ExportSummary,
1688*da58b97aSjoerg const ModuleSummaryIndex *ImportSummary, bool DropTypeTests)
1689*da58b97aSjoerg : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary),
1690*da58b97aSjoerg DropTypeTests(DropTypeTests) {
169106f32e7eSjoerg assert(!(ExportSummary && ImportSummary));
169206f32e7eSjoerg Triple TargetTriple(M.getTargetTriple());
169306f32e7eSjoerg Arch = TargetTriple.getArch();
169406f32e7eSjoerg OS = TargetTriple.getOS();
169506f32e7eSjoerg ObjectFormat = TargetTriple.getObjectFormat();
169606f32e7eSjoerg }
169706f32e7eSjoerg
runForTesting(Module & M)169806f32e7eSjoerg bool LowerTypeTestsModule::runForTesting(Module &M) {
169906f32e7eSjoerg ModuleSummaryIndex Summary(/*HaveGVs=*/false);
170006f32e7eSjoerg
170106f32e7eSjoerg // Handle the command-line summary arguments. This code is for testing
170206f32e7eSjoerg // purposes only, so we handle errors directly.
170306f32e7eSjoerg if (!ClReadSummary.empty()) {
170406f32e7eSjoerg ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
170506f32e7eSjoerg ": ");
170606f32e7eSjoerg auto ReadSummaryFile =
170706f32e7eSjoerg ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
170806f32e7eSjoerg
170906f32e7eSjoerg yaml::Input In(ReadSummaryFile->getBuffer());
171006f32e7eSjoerg In >> Summary;
171106f32e7eSjoerg ExitOnErr(errorCodeToError(In.error()));
171206f32e7eSjoerg }
171306f32e7eSjoerg
171406f32e7eSjoerg bool Changed =
171506f32e7eSjoerg LowerTypeTestsModule(
171606f32e7eSjoerg M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr,
1717*da58b97aSjoerg ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr,
1718*da58b97aSjoerg /*DropTypeTests*/ false)
171906f32e7eSjoerg .lower();
172006f32e7eSjoerg
172106f32e7eSjoerg if (!ClWriteSummary.empty()) {
172206f32e7eSjoerg ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
172306f32e7eSjoerg ": ");
172406f32e7eSjoerg std::error_code EC;
1725*da58b97aSjoerg raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::OF_TextWithCRLF);
172606f32e7eSjoerg ExitOnErr(errorCodeToError(EC));
172706f32e7eSjoerg
172806f32e7eSjoerg yaml::Output Out(OS);
172906f32e7eSjoerg Out << Summary;
173006f32e7eSjoerg }
173106f32e7eSjoerg
173206f32e7eSjoerg return Changed;
173306f32e7eSjoerg }
173406f32e7eSjoerg
isDirectCall(Use & U)173506f32e7eSjoerg static bool isDirectCall(Use& U) {
173606f32e7eSjoerg auto *Usr = dyn_cast<CallInst>(U.getUser());
173706f32e7eSjoerg if (Usr) {
1738*da58b97aSjoerg auto *CB = dyn_cast<CallBase>(Usr);
1739*da58b97aSjoerg if (CB && CB->isCallee(&U))
174006f32e7eSjoerg return true;
174106f32e7eSjoerg }
174206f32e7eSjoerg return false;
174306f32e7eSjoerg }
174406f32e7eSjoerg
replaceCfiUses(Function * Old,Value * New,bool IsJumpTableCanonical)174506f32e7eSjoerg void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New,
174606f32e7eSjoerg bool IsJumpTableCanonical) {
174706f32e7eSjoerg SmallSetVector<Constant *, 4> Constants;
174806f32e7eSjoerg auto UI = Old->use_begin(), E = Old->use_end();
174906f32e7eSjoerg for (; UI != E;) {
175006f32e7eSjoerg Use &U = *UI;
175106f32e7eSjoerg ++UI;
175206f32e7eSjoerg
175306f32e7eSjoerg // Skip block addresses
175406f32e7eSjoerg if (isa<BlockAddress>(U.getUser()))
175506f32e7eSjoerg continue;
175606f32e7eSjoerg
175706f32e7eSjoerg // Skip direct calls to externally defined or non-dso_local functions
175806f32e7eSjoerg if (isDirectCall(U) && (Old->isDSOLocal() || !IsJumpTableCanonical))
175906f32e7eSjoerg continue;
176006f32e7eSjoerg
176106f32e7eSjoerg // Must handle Constants specially, we cannot call replaceUsesOfWith on a
176206f32e7eSjoerg // constant because they are uniqued.
176306f32e7eSjoerg if (auto *C = dyn_cast<Constant>(U.getUser())) {
176406f32e7eSjoerg if (!isa<GlobalValue>(C)) {
176506f32e7eSjoerg // Save unique users to avoid processing operand replacement
176606f32e7eSjoerg // more than once.
176706f32e7eSjoerg Constants.insert(C);
176806f32e7eSjoerg continue;
176906f32e7eSjoerg }
177006f32e7eSjoerg }
177106f32e7eSjoerg
177206f32e7eSjoerg U.set(New);
177306f32e7eSjoerg }
177406f32e7eSjoerg
177506f32e7eSjoerg // Process operand replacement of saved constants.
177606f32e7eSjoerg for (auto *C : Constants)
177706f32e7eSjoerg C->handleOperandChange(Old, New);
177806f32e7eSjoerg }
177906f32e7eSjoerg
replaceDirectCalls(Value * Old,Value * New)178006f32e7eSjoerg void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) {
178106f32e7eSjoerg Old->replaceUsesWithIf(New, [](Use &U) { return isDirectCall(U); });
178206f32e7eSjoerg }
178306f32e7eSjoerg
lower()178406f32e7eSjoerg bool LowerTypeTestsModule::lower() {
1785*da58b97aSjoerg Function *TypeTestFunc =
1786*da58b97aSjoerg M.getFunction(Intrinsic::getName(Intrinsic::type_test));
1787*da58b97aSjoerg
1788*da58b97aSjoerg if (DropTypeTests && TypeTestFunc) {
1789*da58b97aSjoerg for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
1790*da58b97aSjoerg UI != UE;) {
1791*da58b97aSjoerg auto *CI = cast<CallInst>((*UI++).getUser());
1792*da58b97aSjoerg // Find and erase llvm.assume intrinsics for this llvm.type.test call.
1793*da58b97aSjoerg for (auto CIU = CI->use_begin(), CIUE = CI->use_end(); CIU != CIUE;)
1794*da58b97aSjoerg if (auto *Assume = dyn_cast<AssumeInst>((*CIU++).getUser()))
1795*da58b97aSjoerg Assume->eraseFromParent();
1796*da58b97aSjoerg CI->eraseFromParent();
1797*da58b97aSjoerg }
1798*da58b97aSjoerg
1799*da58b97aSjoerg // We have deleted the type intrinsics, so we no longer have enough
1800*da58b97aSjoerg // information to reason about the liveness of virtual function pointers
1801*da58b97aSjoerg // in GlobalDCE.
1802*da58b97aSjoerg for (GlobalVariable &GV : M.globals())
1803*da58b97aSjoerg GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
1804*da58b97aSjoerg
1805*da58b97aSjoerg return true;
1806*da58b97aSjoerg }
1807*da58b97aSjoerg
180806f32e7eSjoerg // If only some of the modules were split, we cannot correctly perform
180906f32e7eSjoerg // this transformation. We already checked for the presense of type tests
181006f32e7eSjoerg // with partially split modules during the thin link, and would have emitted
181106f32e7eSjoerg // an error if any were found, so here we can simply return.
181206f32e7eSjoerg if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
181306f32e7eSjoerg (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
181406f32e7eSjoerg return false;
181506f32e7eSjoerg
181606f32e7eSjoerg Function *ICallBranchFunnelFunc =
181706f32e7eSjoerg M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel));
181806f32e7eSjoerg if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
181906f32e7eSjoerg (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) &&
182006f32e7eSjoerg !ExportSummary && !ImportSummary)
182106f32e7eSjoerg return false;
182206f32e7eSjoerg
182306f32e7eSjoerg if (ImportSummary) {
182406f32e7eSjoerg if (TypeTestFunc) {
182506f32e7eSjoerg for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
182606f32e7eSjoerg UI != UE;) {
182706f32e7eSjoerg auto *CI = cast<CallInst>((*UI++).getUser());
182806f32e7eSjoerg importTypeTest(CI);
182906f32e7eSjoerg }
183006f32e7eSjoerg }
183106f32e7eSjoerg
183206f32e7eSjoerg if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty())
183306f32e7eSjoerg report_fatal_error(
183406f32e7eSjoerg "unexpected call to llvm.icall.branch.funnel during import phase");
183506f32e7eSjoerg
183606f32e7eSjoerg SmallVector<Function *, 8> Defs;
183706f32e7eSjoerg SmallVector<Function *, 8> Decls;
183806f32e7eSjoerg for (auto &F : M) {
183906f32e7eSjoerg // CFI functions are either external, or promoted. A local function may
184006f32e7eSjoerg // have the same name, but it's not the one we are looking for.
184106f32e7eSjoerg if (F.hasLocalLinkage())
184206f32e7eSjoerg continue;
1843*da58b97aSjoerg if (ImportSummary->cfiFunctionDefs().count(std::string(F.getName())))
184406f32e7eSjoerg Defs.push_back(&F);
1845*da58b97aSjoerg else if (ImportSummary->cfiFunctionDecls().count(
1846*da58b97aSjoerg std::string(F.getName())))
184706f32e7eSjoerg Decls.push_back(&F);
184806f32e7eSjoerg }
184906f32e7eSjoerg
185006f32e7eSjoerg std::vector<GlobalAlias *> AliasesToErase;
185106f32e7eSjoerg {
185206f32e7eSjoerg ScopedSaveAliaseesAndUsed S(M);
185306f32e7eSjoerg for (auto F : Defs)
185406f32e7eSjoerg importFunction(F, /*isJumpTableCanonical*/ true, AliasesToErase);
185506f32e7eSjoerg for (auto F : Decls)
185606f32e7eSjoerg importFunction(F, /*isJumpTableCanonical*/ false, AliasesToErase);
185706f32e7eSjoerg }
185806f32e7eSjoerg for (GlobalAlias *GA : AliasesToErase)
185906f32e7eSjoerg GA->eraseFromParent();
186006f32e7eSjoerg
186106f32e7eSjoerg return true;
186206f32e7eSjoerg }
186306f32e7eSjoerg
186406f32e7eSjoerg // Equivalence class set containing type identifiers and the globals that
186506f32e7eSjoerg // reference them. This is used to partition the set of type identifiers in
186606f32e7eSjoerg // the module into disjoint sets.
186706f32e7eSjoerg using GlobalClassesTy = EquivalenceClasses<
1868*da58b97aSjoerg PointerUnion<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>;
186906f32e7eSjoerg GlobalClassesTy GlobalClasses;
187006f32e7eSjoerg
187106f32e7eSjoerg // Verify the type metadata and build a few data structures to let us
187206f32e7eSjoerg // efficiently enumerate the type identifiers associated with a global:
187306f32e7eSjoerg // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
187406f32e7eSjoerg // of associated type metadata) and a mapping from type identifiers to their
187506f32e7eSjoerg // list of GlobalTypeMembers and last observed index in the list of globals.
187606f32e7eSjoerg // The indices will be used later to deterministically order the list of type
187706f32e7eSjoerg // identifiers.
187806f32e7eSjoerg BumpPtrAllocator Alloc;
187906f32e7eSjoerg struct TIInfo {
188006f32e7eSjoerg unsigned UniqueId;
188106f32e7eSjoerg std::vector<GlobalTypeMember *> RefGlobals;
188206f32e7eSjoerg };
188306f32e7eSjoerg DenseMap<Metadata *, TIInfo> TypeIdInfo;
188406f32e7eSjoerg unsigned CurUniqueId = 0;
188506f32e7eSjoerg SmallVector<MDNode *, 2> Types;
188606f32e7eSjoerg
188706f32e7eSjoerg // Cross-DSO CFI emits jumptable entries for exported functions as well as
188806f32e7eSjoerg // address taken functions in case they are address taken in other modules.
188906f32e7eSjoerg const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr;
189006f32e7eSjoerg
189106f32e7eSjoerg struct ExportedFunctionInfo {
189206f32e7eSjoerg CfiFunctionLinkage Linkage;
189306f32e7eSjoerg MDNode *FuncMD; // {name, linkage, type[, type...]}
189406f32e7eSjoerg };
189506f32e7eSjoerg DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions;
189606f32e7eSjoerg if (ExportSummary) {
189706f32e7eSjoerg // A set of all functions that are address taken by a live global object.
189806f32e7eSjoerg DenseSet<GlobalValue::GUID> AddressTaken;
189906f32e7eSjoerg for (auto &I : *ExportSummary)
190006f32e7eSjoerg for (auto &GVS : I.second.SummaryList)
190106f32e7eSjoerg if (GVS->isLive())
190206f32e7eSjoerg for (auto &Ref : GVS->refs())
190306f32e7eSjoerg AddressTaken.insert(Ref.getGUID());
190406f32e7eSjoerg
190506f32e7eSjoerg NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions");
190606f32e7eSjoerg if (CfiFunctionsMD) {
190706f32e7eSjoerg for (auto FuncMD : CfiFunctionsMD->operands()) {
190806f32e7eSjoerg assert(FuncMD->getNumOperands() >= 2);
190906f32e7eSjoerg StringRef FunctionName =
191006f32e7eSjoerg cast<MDString>(FuncMD->getOperand(0))->getString();
191106f32e7eSjoerg CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>(
191206f32e7eSjoerg cast<ConstantAsMetadata>(FuncMD->getOperand(1))
191306f32e7eSjoerg ->getValue()
191406f32e7eSjoerg ->getUniqueInteger()
191506f32e7eSjoerg .getZExtValue());
191606f32e7eSjoerg const GlobalValue::GUID GUID = GlobalValue::getGUID(
191706f32e7eSjoerg GlobalValue::dropLLVMManglingEscape(FunctionName));
191806f32e7eSjoerg // Do not emit jumptable entries for functions that are not-live and
191906f32e7eSjoerg // have no live references (and are not exported with cross-DSO CFI.)
192006f32e7eSjoerg if (!ExportSummary->isGUIDLive(GUID))
192106f32e7eSjoerg continue;
192206f32e7eSjoerg if (!AddressTaken.count(GUID)) {
192306f32e7eSjoerg if (!CrossDsoCfi || Linkage != CFL_Definition)
192406f32e7eSjoerg continue;
192506f32e7eSjoerg
192606f32e7eSjoerg bool Exported = false;
192706f32e7eSjoerg if (auto VI = ExportSummary->getValueInfo(GUID))
192806f32e7eSjoerg for (auto &GVS : VI.getSummaryList())
192906f32e7eSjoerg if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
193006f32e7eSjoerg Exported = true;
193106f32e7eSjoerg
193206f32e7eSjoerg if (!Exported)
193306f32e7eSjoerg continue;
193406f32e7eSjoerg }
193506f32e7eSjoerg auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}});
193606f32e7eSjoerg if (!P.second && P.first->second.Linkage != CFL_Definition)
193706f32e7eSjoerg P.first->second = {Linkage, FuncMD};
193806f32e7eSjoerg }
193906f32e7eSjoerg
194006f32e7eSjoerg for (const auto &P : ExportedFunctions) {
194106f32e7eSjoerg StringRef FunctionName = P.first;
194206f32e7eSjoerg CfiFunctionLinkage Linkage = P.second.Linkage;
194306f32e7eSjoerg MDNode *FuncMD = P.second.FuncMD;
194406f32e7eSjoerg Function *F = M.getFunction(FunctionName);
194506f32e7eSjoerg if (F && F->hasLocalLinkage()) {
194606f32e7eSjoerg // Locally defined function that happens to have the same name as a
194706f32e7eSjoerg // function defined in a ThinLTO module. Rename it to move it out of
194806f32e7eSjoerg // the way of the external reference that we're about to create.
194906f32e7eSjoerg // Note that setName will find a unique name for the function, so even
195006f32e7eSjoerg // if there is an existing function with the suffix there won't be a
195106f32e7eSjoerg // name collision.
195206f32e7eSjoerg F->setName(F->getName() + ".1");
195306f32e7eSjoerg F = nullptr;
195406f32e7eSjoerg }
195506f32e7eSjoerg
195606f32e7eSjoerg if (!F)
195706f32e7eSjoerg F = Function::Create(
195806f32e7eSjoerg FunctionType::get(Type::getVoidTy(M.getContext()), false),
195906f32e7eSjoerg GlobalVariable::ExternalLinkage,
196006f32e7eSjoerg M.getDataLayout().getProgramAddressSpace(), FunctionName, &M);
196106f32e7eSjoerg
196206f32e7eSjoerg // If the function is available_externally, remove its definition so
196306f32e7eSjoerg // that it is handled the same way as a declaration. Later we will try
196406f32e7eSjoerg // to create an alias using this function's linkage, which will fail if
196506f32e7eSjoerg // the linkage is available_externally. This will also result in us
196606f32e7eSjoerg // following the code path below to replace the type metadata.
196706f32e7eSjoerg if (F->hasAvailableExternallyLinkage()) {
196806f32e7eSjoerg F->setLinkage(GlobalValue::ExternalLinkage);
196906f32e7eSjoerg F->deleteBody();
197006f32e7eSjoerg F->setComdat(nullptr);
197106f32e7eSjoerg F->clearMetadata();
197206f32e7eSjoerg }
197306f32e7eSjoerg
197406f32e7eSjoerg // Update the linkage for extern_weak declarations when a definition
197506f32e7eSjoerg // exists.
197606f32e7eSjoerg if (Linkage == CFL_Definition && F->hasExternalWeakLinkage())
197706f32e7eSjoerg F->setLinkage(GlobalValue::ExternalLinkage);
197806f32e7eSjoerg
197906f32e7eSjoerg // If the function in the full LTO module is a declaration, replace its
198006f32e7eSjoerg // type metadata with the type metadata we found in cfi.functions. That
198106f32e7eSjoerg // metadata is presumed to be more accurate than the metadata attached
198206f32e7eSjoerg // to the declaration.
198306f32e7eSjoerg if (F->isDeclaration()) {
198406f32e7eSjoerg if (Linkage == CFL_WeakDeclaration)
198506f32e7eSjoerg F->setLinkage(GlobalValue::ExternalWeakLinkage);
198606f32e7eSjoerg
198706f32e7eSjoerg F->eraseMetadata(LLVMContext::MD_type);
198806f32e7eSjoerg for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
198906f32e7eSjoerg F->addMetadata(LLVMContext::MD_type,
199006f32e7eSjoerg *cast<MDNode>(FuncMD->getOperand(I).get()));
199106f32e7eSjoerg }
199206f32e7eSjoerg }
199306f32e7eSjoerg }
199406f32e7eSjoerg }
199506f32e7eSjoerg
199606f32e7eSjoerg DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
199706f32e7eSjoerg for (GlobalObject &GO : M.global_objects()) {
199806f32e7eSjoerg if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
199906f32e7eSjoerg continue;
200006f32e7eSjoerg
200106f32e7eSjoerg Types.clear();
200206f32e7eSjoerg GO.getMetadata(LLVMContext::MD_type, Types);
200306f32e7eSjoerg
200406f32e7eSjoerg bool IsJumpTableCanonical = false;
200506f32e7eSjoerg bool IsExported = false;
200606f32e7eSjoerg if (Function *F = dyn_cast<Function>(&GO)) {
200706f32e7eSjoerg IsJumpTableCanonical = isJumpTableCanonical(F);
200806f32e7eSjoerg if (ExportedFunctions.count(F->getName())) {
200906f32e7eSjoerg IsJumpTableCanonical |=
201006f32e7eSjoerg ExportedFunctions[F->getName()].Linkage == CFL_Definition;
201106f32e7eSjoerg IsExported = true;
201206f32e7eSjoerg // TODO: The logic here checks only that the function is address taken,
201306f32e7eSjoerg // not that the address takers are live. This can be updated to check
201406f32e7eSjoerg // their liveness and emit fewer jumptable entries once monolithic LTO
201506f32e7eSjoerg // builds also emit summaries.
201606f32e7eSjoerg } else if (!F->hasAddressTaken()) {
201706f32e7eSjoerg if (!CrossDsoCfi || !IsJumpTableCanonical || F->hasLocalLinkage())
201806f32e7eSjoerg continue;
201906f32e7eSjoerg }
202006f32e7eSjoerg }
202106f32e7eSjoerg
202206f32e7eSjoerg auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical,
202306f32e7eSjoerg IsExported, Types);
202406f32e7eSjoerg GlobalTypeMembers[&GO] = GTM;
202506f32e7eSjoerg for (MDNode *Type : Types) {
202606f32e7eSjoerg verifyTypeMDNode(&GO, Type);
202706f32e7eSjoerg auto &Info = TypeIdInfo[Type->getOperand(1)];
202806f32e7eSjoerg Info.UniqueId = ++CurUniqueId;
202906f32e7eSjoerg Info.RefGlobals.push_back(GTM);
203006f32e7eSjoerg }
203106f32e7eSjoerg }
203206f32e7eSjoerg
203306f32e7eSjoerg auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
203406f32e7eSjoerg // Add the call site to the list of call sites for this type identifier. We
203506f32e7eSjoerg // also use TypeIdUsers to keep track of whether we have seen this type
203606f32e7eSjoerg // identifier before. If we have, we don't need to re-add the referenced
203706f32e7eSjoerg // globals to the equivalence class.
203806f32e7eSjoerg auto Ins = TypeIdUsers.insert({TypeId, {}});
203906f32e7eSjoerg if (Ins.second) {
204006f32e7eSjoerg // Add the type identifier to the equivalence class.
204106f32e7eSjoerg GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
204206f32e7eSjoerg GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
204306f32e7eSjoerg
204406f32e7eSjoerg // Add the referenced globals to the type identifier's equivalence class.
204506f32e7eSjoerg for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
204606f32e7eSjoerg CurSet = GlobalClasses.unionSets(
204706f32e7eSjoerg CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
204806f32e7eSjoerg }
204906f32e7eSjoerg
205006f32e7eSjoerg return Ins.first->second;
205106f32e7eSjoerg };
205206f32e7eSjoerg
205306f32e7eSjoerg if (TypeTestFunc) {
205406f32e7eSjoerg for (const Use &U : TypeTestFunc->uses()) {
205506f32e7eSjoerg auto CI = cast<CallInst>(U.getUser());
2056*da58b97aSjoerg // If this type test is only used by llvm.assume instructions, it
2057*da58b97aSjoerg // was used for whole program devirtualization, and is being kept
2058*da58b97aSjoerg // for use by other optimization passes. We do not need or want to
2059*da58b97aSjoerg // lower it here. We also don't want to rewrite any associated globals
2060*da58b97aSjoerg // unnecessarily. These will be removed by a subsequent LTT invocation
2061*da58b97aSjoerg // with the DropTypeTests flag set.
2062*da58b97aSjoerg bool OnlyAssumeUses = !CI->use_empty();
2063*da58b97aSjoerg for (const Use &CIU : CI->uses()) {
2064*da58b97aSjoerg if (isa<AssumeInst>(CIU.getUser()))
2065*da58b97aSjoerg continue;
2066*da58b97aSjoerg OnlyAssumeUses = false;
2067*da58b97aSjoerg break;
2068*da58b97aSjoerg }
2069*da58b97aSjoerg if (OnlyAssumeUses)
2070*da58b97aSjoerg continue;
207106f32e7eSjoerg
207206f32e7eSjoerg auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
207306f32e7eSjoerg if (!TypeIdMDVal)
207406f32e7eSjoerg report_fatal_error("Second argument of llvm.type.test must be metadata");
207506f32e7eSjoerg auto TypeId = TypeIdMDVal->getMetadata();
207606f32e7eSjoerg AddTypeIdUse(TypeId).CallSites.push_back(CI);
207706f32e7eSjoerg }
207806f32e7eSjoerg }
207906f32e7eSjoerg
208006f32e7eSjoerg if (ICallBranchFunnelFunc) {
208106f32e7eSjoerg for (const Use &U : ICallBranchFunnelFunc->uses()) {
208206f32e7eSjoerg if (Arch != Triple::x86_64)
208306f32e7eSjoerg report_fatal_error(
208406f32e7eSjoerg "llvm.icall.branch.funnel not supported on this target");
208506f32e7eSjoerg
208606f32e7eSjoerg auto CI = cast<CallInst>(U.getUser());
208706f32e7eSjoerg
208806f32e7eSjoerg std::vector<GlobalTypeMember *> Targets;
208906f32e7eSjoerg if (CI->getNumArgOperands() % 2 != 1)
209006f32e7eSjoerg report_fatal_error("number of arguments should be odd");
209106f32e7eSjoerg
209206f32e7eSjoerg GlobalClassesTy::member_iterator CurSet;
209306f32e7eSjoerg for (unsigned I = 1; I != CI->getNumArgOperands(); I += 2) {
209406f32e7eSjoerg int64_t Offset;
209506f32e7eSjoerg auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
209606f32e7eSjoerg CI->getOperand(I), Offset, M.getDataLayout()));
209706f32e7eSjoerg if (!Base)
209806f32e7eSjoerg report_fatal_error(
209906f32e7eSjoerg "Expected branch funnel operand to be global value");
210006f32e7eSjoerg
210106f32e7eSjoerg GlobalTypeMember *GTM = GlobalTypeMembers[Base];
210206f32e7eSjoerg Targets.push_back(GTM);
210306f32e7eSjoerg GlobalClassesTy::member_iterator NewSet =
210406f32e7eSjoerg GlobalClasses.findLeader(GlobalClasses.insert(GTM));
210506f32e7eSjoerg if (I == 1)
210606f32e7eSjoerg CurSet = NewSet;
210706f32e7eSjoerg else
210806f32e7eSjoerg CurSet = GlobalClasses.unionSets(CurSet, NewSet);
210906f32e7eSjoerg }
211006f32e7eSjoerg
211106f32e7eSjoerg GlobalClasses.unionSets(
211206f32e7eSjoerg CurSet, GlobalClasses.findLeader(
211306f32e7eSjoerg GlobalClasses.insert(ICallBranchFunnel::create(
211406f32e7eSjoerg Alloc, CI, Targets, ++CurUniqueId))));
211506f32e7eSjoerg }
211606f32e7eSjoerg }
211706f32e7eSjoerg
211806f32e7eSjoerg if (ExportSummary) {
211906f32e7eSjoerg DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
212006f32e7eSjoerg for (auto &P : TypeIdInfo) {
212106f32e7eSjoerg if (auto *TypeId = dyn_cast<MDString>(P.first))
212206f32e7eSjoerg MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
212306f32e7eSjoerg TypeId);
212406f32e7eSjoerg }
212506f32e7eSjoerg
212606f32e7eSjoerg for (auto &P : *ExportSummary) {
212706f32e7eSjoerg for (auto &S : P.second.SummaryList) {
212806f32e7eSjoerg if (!ExportSummary->isGlobalValueLive(S.get()))
212906f32e7eSjoerg continue;
213006f32e7eSjoerg if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject()))
213106f32e7eSjoerg for (GlobalValue::GUID G : FS->type_tests())
213206f32e7eSjoerg for (Metadata *MD : MetadataByGUID[G])
213306f32e7eSjoerg AddTypeIdUse(MD).IsExported = true;
213406f32e7eSjoerg }
213506f32e7eSjoerg }
213606f32e7eSjoerg }
213706f32e7eSjoerg
213806f32e7eSjoerg if (GlobalClasses.empty())
213906f32e7eSjoerg return false;
214006f32e7eSjoerg
214106f32e7eSjoerg // Build a list of disjoint sets ordered by their maximum global index for
214206f32e7eSjoerg // determinism.
214306f32e7eSjoerg std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
214406f32e7eSjoerg for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
214506f32e7eSjoerg E = GlobalClasses.end();
214606f32e7eSjoerg I != E; ++I) {
214706f32e7eSjoerg if (!I->isLeader())
214806f32e7eSjoerg continue;
214906f32e7eSjoerg ++NumTypeIdDisjointSets;
215006f32e7eSjoerg
215106f32e7eSjoerg unsigned MaxUniqueId = 0;
215206f32e7eSjoerg for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
215306f32e7eSjoerg MI != GlobalClasses.member_end(); ++MI) {
215406f32e7eSjoerg if (auto *MD = MI->dyn_cast<Metadata *>())
215506f32e7eSjoerg MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
215606f32e7eSjoerg else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
215706f32e7eSjoerg MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
215806f32e7eSjoerg }
215906f32e7eSjoerg Sets.emplace_back(I, MaxUniqueId);
216006f32e7eSjoerg }
216106f32e7eSjoerg llvm::sort(Sets,
216206f32e7eSjoerg [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
216306f32e7eSjoerg const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
216406f32e7eSjoerg return S1.second < S2.second;
216506f32e7eSjoerg });
216606f32e7eSjoerg
216706f32e7eSjoerg // For each disjoint set we found...
216806f32e7eSjoerg for (const auto &S : Sets) {
216906f32e7eSjoerg // Build the list of type identifiers in this disjoint set.
217006f32e7eSjoerg std::vector<Metadata *> TypeIds;
217106f32e7eSjoerg std::vector<GlobalTypeMember *> Globals;
217206f32e7eSjoerg std::vector<ICallBranchFunnel *> ICallBranchFunnels;
217306f32e7eSjoerg for (GlobalClassesTy::member_iterator MI =
217406f32e7eSjoerg GlobalClasses.member_begin(S.first);
217506f32e7eSjoerg MI != GlobalClasses.member_end(); ++MI) {
217606f32e7eSjoerg if (MI->is<Metadata *>())
217706f32e7eSjoerg TypeIds.push_back(MI->get<Metadata *>());
217806f32e7eSjoerg else if (MI->is<GlobalTypeMember *>())
217906f32e7eSjoerg Globals.push_back(MI->get<GlobalTypeMember *>());
218006f32e7eSjoerg else
218106f32e7eSjoerg ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
218206f32e7eSjoerg }
218306f32e7eSjoerg
218406f32e7eSjoerg // Order type identifiers by unique ID for determinism. This ordering is
218506f32e7eSjoerg // stable as there is a one-to-one mapping between metadata and unique IDs.
218606f32e7eSjoerg llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) {
218706f32e7eSjoerg return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
218806f32e7eSjoerg });
218906f32e7eSjoerg
219006f32e7eSjoerg // Same for the branch funnels.
219106f32e7eSjoerg llvm::sort(ICallBranchFunnels,
219206f32e7eSjoerg [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
219306f32e7eSjoerg return F1->UniqueId < F2->UniqueId;
219406f32e7eSjoerg });
219506f32e7eSjoerg
219606f32e7eSjoerg // Build bitsets for this disjoint set.
219706f32e7eSjoerg buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
219806f32e7eSjoerg }
219906f32e7eSjoerg
220006f32e7eSjoerg allocateByteArrays();
220106f32e7eSjoerg
220206f32e7eSjoerg // Parse alias data to replace stand-in function declarations for aliases
220306f32e7eSjoerg // with an alias to the intended target.
220406f32e7eSjoerg if (ExportSummary) {
220506f32e7eSjoerg if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {
220606f32e7eSjoerg for (auto AliasMD : AliasesMD->operands()) {
220706f32e7eSjoerg assert(AliasMD->getNumOperands() >= 4);
220806f32e7eSjoerg StringRef AliasName =
220906f32e7eSjoerg cast<MDString>(AliasMD->getOperand(0))->getString();
221006f32e7eSjoerg StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
221106f32e7eSjoerg
221206f32e7eSjoerg if (!ExportedFunctions.count(Aliasee) ||
221306f32e7eSjoerg ExportedFunctions[Aliasee].Linkage != CFL_Definition ||
221406f32e7eSjoerg !M.getNamedAlias(Aliasee))
221506f32e7eSjoerg continue;
221606f32e7eSjoerg
221706f32e7eSjoerg GlobalValue::VisibilityTypes Visibility =
221806f32e7eSjoerg static_cast<GlobalValue::VisibilityTypes>(
221906f32e7eSjoerg cast<ConstantAsMetadata>(AliasMD->getOperand(2))
222006f32e7eSjoerg ->getValue()
222106f32e7eSjoerg ->getUniqueInteger()
222206f32e7eSjoerg .getZExtValue());
222306f32e7eSjoerg bool Weak =
222406f32e7eSjoerg static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
222506f32e7eSjoerg ->getValue()
222606f32e7eSjoerg ->getUniqueInteger()
222706f32e7eSjoerg .getZExtValue());
222806f32e7eSjoerg
222906f32e7eSjoerg auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee));
223006f32e7eSjoerg Alias->setVisibility(Visibility);
223106f32e7eSjoerg if (Weak)
223206f32e7eSjoerg Alias->setLinkage(GlobalValue::WeakAnyLinkage);
223306f32e7eSjoerg
223406f32e7eSjoerg if (auto *F = M.getFunction(AliasName)) {
223506f32e7eSjoerg Alias->takeName(F);
223606f32e7eSjoerg F->replaceAllUsesWith(Alias);
223706f32e7eSjoerg F->eraseFromParent();
223806f32e7eSjoerg } else {
223906f32e7eSjoerg Alias->setName(AliasName);
224006f32e7eSjoerg }
224106f32e7eSjoerg }
224206f32e7eSjoerg }
224306f32e7eSjoerg }
224406f32e7eSjoerg
224506f32e7eSjoerg // Emit .symver directives for exported functions, if they exist.
224606f32e7eSjoerg if (ExportSummary) {
224706f32e7eSjoerg if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) {
224806f32e7eSjoerg for (auto Symver : SymversMD->operands()) {
224906f32e7eSjoerg assert(Symver->getNumOperands() >= 2);
225006f32e7eSjoerg StringRef SymbolName =
225106f32e7eSjoerg cast<MDString>(Symver->getOperand(0))->getString();
225206f32e7eSjoerg StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
225306f32e7eSjoerg
225406f32e7eSjoerg if (!ExportedFunctions.count(SymbolName))
225506f32e7eSjoerg continue;
225606f32e7eSjoerg
225706f32e7eSjoerg M.appendModuleInlineAsm(
225806f32e7eSjoerg (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str());
225906f32e7eSjoerg }
226006f32e7eSjoerg }
226106f32e7eSjoerg }
226206f32e7eSjoerg
226306f32e7eSjoerg return true;
226406f32e7eSjoerg }
226506f32e7eSjoerg
run(Module & M,ModuleAnalysisManager & AM)226606f32e7eSjoerg PreservedAnalyses LowerTypeTestsPass::run(Module &M,
226706f32e7eSjoerg ModuleAnalysisManager &AM) {
2268*da58b97aSjoerg bool Changed;
2269*da58b97aSjoerg if (UseCommandLine)
2270*da58b97aSjoerg Changed = LowerTypeTestsModule::runForTesting(M);
2271*da58b97aSjoerg else
2272*da58b97aSjoerg Changed =
2273*da58b97aSjoerg LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
2274*da58b97aSjoerg .lower();
227506f32e7eSjoerg if (!Changed)
227606f32e7eSjoerg return PreservedAnalyses::all();
227706f32e7eSjoerg return PreservedAnalyses::none();
227806f32e7eSjoerg }
2279