LowerTypeTests.cpp revision 355940
125184Sjkh//===- LowerTypeTests.cpp - type metadata lowering pass -------------------===// 2113674Smtm// 3113674Smtm// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4113674Smtm// See https://llvm.org/LICENSE.txt for license information. 5113674Smtm// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6113674Smtm// 7113674Smtm//===----------------------------------------------------------------------===// 8113674Smtm// 9113674Smtm// This pass lowers type metadata and calls to the llvm.type.test intrinsic. 10113674Smtm// It also ensures that globals are properly laid out for the 11113674Smtm// llvm.icall.branch.funnel intrinsic. 12113674Smtm// See http://llvm.org/docs/TypeMetadata.html for more information. 13113674Smtm// 14113674Smtm//===----------------------------------------------------------------------===// 15113674Smtm 16113674Smtm#include "llvm/Transforms/IPO/LowerTypeTests.h" 17113674Smtm#include "llvm/ADT/APInt.h" 18113674Smtm#include "llvm/ADT/ArrayRef.h" 19113674Smtm#include "llvm/ADT/DenseMap.h" 20113674Smtm#include "llvm/ADT/EquivalenceClasses.h" 21113674Smtm#include "llvm/ADT/PointerUnion.h" 22113674Smtm#include "llvm/ADT/SetVector.h" 23113674Smtm#include "llvm/ADT/SmallVector.h" 24113674Smtm#include "llvm/ADT/Statistic.h" 2550472Speter#include "llvm/ADT/StringRef.h" 2666830Sobrien#include "llvm/ADT/TinyPtrVector.h" 2725184Sjkh#include "llvm/ADT/Triple.h" 28113674Smtm#include "llvm/Analysis/TypeMetadataUtils.h" 29113674Smtm#include "llvm/Analysis/ValueTracking.h" 30113674Smtm#include "llvm/IR/Attributes.h" 31113674Smtm#include "llvm/IR/BasicBlock.h" 3225184Sjkh#include "llvm/IR/Constant.h" 33113674Smtm#include "llvm/IR/Constants.h" 34113674Smtm#include "llvm/IR/DataLayout.h" 35113674Smtm#include "llvm/IR/DerivedTypes.h" 36113674Smtm#include "llvm/IR/Function.h" 37147088Sbrooks#include "llvm/IR/GlobalAlias.h" 38147088Sbrooks#include "llvm/IR/GlobalObject.h" 39113674Smtm#include "llvm/IR/GlobalValue.h" 40113674Smtm#include "llvm/IR/GlobalVariable.h" 41113674Smtm#include "llvm/IR/IRBuilder.h" 42147088Sbrooks#include "llvm/IR/InlineAsm.h" 43147088Sbrooks#include "llvm/IR/Instruction.h" 44147088Sbrooks#include "llvm/IR/Instructions.h" 45113674Smtm#include "llvm/IR/Intrinsics.h" 46113674Smtm#include "llvm/IR/LLVMContext.h" 47147088Sbrooks#include "llvm/IR/Metadata.h" 48113674Smtm#include "llvm/IR/Module.h" 49147088Sbrooks#include "llvm/IR/ModuleSummaryIndex.h" 50147088Sbrooks#include "llvm/IR/ModuleSummaryIndexYAML.h" 51147088Sbrooks#include "llvm/IR/Operator.h" 52147088Sbrooks#include "llvm/IR/PassManager.h" 53147088Sbrooks#include "llvm/IR/Type.h" 54147088Sbrooks#include "llvm/IR/Use.h" 55147088Sbrooks#include "llvm/IR/User.h" 56147088Sbrooks#include "llvm/IR/Value.h" 57147088Sbrooks#include "llvm/Pass.h" 58147088Sbrooks#include "llvm/Support/Allocator.h" 59147088Sbrooks#include "llvm/Support/Casting.h" 60147121Sbrooks#include "llvm/Support/CommandLine.h" 61113674Smtm#include "llvm/Support/Debug.h" 6225184Sjkh#include "llvm/Support/Error.h" 63116029Smtm#include "llvm/Support/ErrorHandling.h" 64116029Smtm#include "llvm/Support/FileSystem.h" 65116029Smtm#include "llvm/Support/MathExtras.h" 66116100Smtm#include "llvm/Support/MemoryBuffer.h" 67116029Smtm#include "llvm/Support/TrailingObjects.h" 68116029Smtm#include "llvm/Support/YAMLTraits.h" 69116029Smtm#include "llvm/Support/raw_ostream.h" 70116029Smtm#include "llvm/Transforms/IPO.h" 71116029Smtm#include "llvm/Transforms/Utils/BasicBlockUtils.h" 72147121Sbrooks#include "llvm/Transforms/Utils/ModuleUtils.h" 73116029Smtm#include <algorithm> 74116029Smtm#include <cassert> 75116029Smtm#include <cstdint> 76116029Smtm#include <memory> 77116029Smtm#include <set> 78116029Smtm#include <string> 79116029Smtm#include <system_error> 80116029Smtm#include <utility> 81116029Smtm#include <vector> 82116029Smtm 83116029Smtmusing namespace llvm; 84116032Smtmusing namespace lowertypetests; 85116032Smtm 86116032Smtm#define DEBUG_TYPE "lowertypetests" 87147121Sbrooks 88116029SmtmSTATISTIC(ByteArraySizeBits, "Byte array size in bits"); 89116029SmtmSTATISTIC(ByteArraySizeBytes, "Byte array size in bytes"); 90116029SmtmSTATISTIC(NumByteArraysCreated, "Number of byte arrays created"); 91147088SbrooksSTATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered"); 92147088SbrooksSTATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers"); 93147121Sbrooks 94147088Sbrooksstatic cl::opt<bool> AvoidReuse( 95147088Sbrooks "lowertypetests-avoid-reuse", 96147088Sbrooks cl::desc("Try to avoid reuse of byte array addresses using aliases"), 97147088Sbrooks cl::Hidden, cl::init(true)); 98147088Sbrooks 99147088Sbrooksstatic cl::opt<PassSummaryAction> ClSummaryAction( 100147088Sbrooks "lowertypetests-summary-action", 101147121Sbrooks cl::desc("What to do with the summary when running this pass"), 102116029Smtm cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), 103116029Smtm clEnumValN(PassSummaryAction::Import, "import", 104147088Sbrooks "Import typeid resolutions from summary and globals"), 105147088Sbrooks clEnumValN(PassSummaryAction::Export, "export", 106147088Sbrooks "Export typeid resolutions to summary and globals")), 107147088Sbrooks cl::Hidden); 108147088Sbrooks 109147088Sbrooksstatic cl::opt<std::string> ClReadSummary( 110147088Sbrooks "lowertypetests-read-summary", 111147088Sbrooks cl::desc("Read summary from given YAML file before running pass"), 112147088Sbrooks cl::Hidden); 113147088Sbrooks 114147088Sbrooksstatic cl::opt<std::string> ClWriteSummary( 115147088Sbrooks "lowertypetests-write-summary", 116147088Sbrooks cl::desc("Write summary to given YAML file after running pass"), 117147088Sbrooks cl::Hidden); 118147088Sbrooks 119147088Sbrooksbool BitSetInfo::containsGlobalOffset(uint64_t Offset) const { 120147088Sbrooks if (Offset < ByteOffset) 121147088Sbrooks return false; 122147088Sbrooks 123147088Sbrooks if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0) 124147088Sbrooks return false; 125147088Sbrooks 126147088Sbrooks uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2; 127147088Sbrooks if (BitOffset >= BitSize) 128147088Sbrooks return false; 129147088Sbrooks 130147088Sbrooks return Bits.count(BitOffset); 131147088Sbrooks} 132147088Sbrooks 133147088Sbrooksvoid BitSetInfo::print(raw_ostream &OS) const { 134147088Sbrooks OS << "offset " << ByteOffset << " size " << BitSize << " align " 135147088Sbrooks << (1 << AlignLog2); 136147088Sbrooks 137147088Sbrooks if (isAllOnes()) { 138147088Sbrooks OS << " all-ones\n"; 139147088Sbrooks return; 140147088Sbrooks } 141147088Sbrooks 142147088Sbrooks OS << " { "; 143147088Sbrooks for (uint64_t B : Bits) 144147088Sbrooks OS << B << ' '; 145147088Sbrooks OS << "}\n"; 146147088Sbrooks} 147147088Sbrooks 148147088SbrooksBitSetInfo BitSetBuilder::build() { 149147088Sbrooks if (Min > Max) 150147088Sbrooks Min = 0; 151147088Sbrooks 152147088Sbrooks // Normalize each offset against the minimum observed offset, and compute 153147088Sbrooks // the bitwise OR of each of the offsets. The number of trailing zeros 154147088Sbrooks // in the mask gives us the log2 of the alignment of all offsets, which 155147088Sbrooks // allows us to compress the bitset by only storing one bit per aligned 156147088Sbrooks // address. 157147088Sbrooks uint64_t Mask = 0; 158147088Sbrooks for (uint64_t &Offset : Offsets) { 159147088Sbrooks Offset -= Min; 160147088Sbrooks Mask |= Offset; 161147088Sbrooks } 162147088Sbrooks 163147088Sbrooks BitSetInfo BSI; 164147088Sbrooks BSI.ByteOffset = Min; 165147088Sbrooks 166147088Sbrooks BSI.AlignLog2 = 0; 167147088Sbrooks if (Mask != 0) 168147088Sbrooks BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined); 169147088Sbrooks 170147088Sbrooks // Build the compressed bitset while normalizing the offsets against the 171147088Sbrooks // computed alignment. 172147088Sbrooks BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1; 173147088Sbrooks for (uint64_t Offset : Offsets) { 174147088Sbrooks Offset >>= BSI.AlignLog2; 175147088Sbrooks BSI.Bits.insert(Offset); 176147088Sbrooks } 177147088Sbrooks 178147088Sbrooks return BSI; 179147088Sbrooks} 180147088Sbrooks 181147088Sbrooksvoid GlobalLayoutBuilder::addFragment(const std::set<uint64_t> &F) { 182147088Sbrooks // Create a new fragment to hold the layout for F. 183147088Sbrooks Fragments.emplace_back(); 184113674Smtm std::vector<uint64_t> &Fragment = Fragments.back(); 185113674Smtm uint64_t FragmentIndex = Fragments.size() - 1; 186113674Smtm 187113674Smtm for (auto ObjIndex : F) { 188113674Smtm uint64_t OldFragmentIndex = FragmentMap[ObjIndex]; 189113674Smtm if (OldFragmentIndex == 0) { 190113674Smtm // We haven't seen this object index before, so just add it to the current 191113674Smtm // fragment. 192113674Smtm Fragment.push_back(ObjIndex); 193113674Smtm } else { 194113674Smtm // This index belongs to an existing fragment. Copy the elements of the 195113674Smtm // old fragment into this one and clear the old fragment. We don't update 196113674Smtm // the fragment map just yet, this ensures that any further references to 197113674Smtm // indices from the old fragment in this fragment do not insert any more 198113674Smtm // indices. 199113674Smtm std::vector<uint64_t> &OldFragment = Fragments[OldFragmentIndex]; 200113674Smtm Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end()); 201113674Smtm OldFragment.clear(); 202113674Smtm } 203113674Smtm } 204113674Smtm 205100280Sgordon // Update the fragment map to point our object indices to this fragment. 206116029Smtm for (uint64_t ObjIndex : Fragment) 207116029Smtm FragmentMap[ObjIndex] = FragmentIndex; 208116029Smtm} 209116029Smtm 210116029Smtmvoid ByteArrayBuilder::allocate(const std::set<uint64_t> &Bits, 211116029Smtm uint64_t BitSize, uint64_t &AllocByteOffset, 212116029Smtm uint8_t &AllocMask) { 213116029Smtm // Find the smallest current allocation. 214116029Smtm unsigned Bit = 0; 215116029Smtm for (unsigned I = 1; I != BitsPerByte; ++I) 216116029Smtm if (BitAllocs[I] < BitAllocs[Bit]) 217116029Smtm Bit = I; 218116029Smtm 219116029Smtm AllocByteOffset = BitAllocs[Bit]; 220116029Smtm 221116029Smtm // Add our size to it. 222116029Smtm unsigned ReqSize = AllocByteOffset + BitSize; 223116029Smtm BitAllocs[Bit] = ReqSize; 224116029Smtm if (Bytes.size() < ReqSize) 225116029Smtm Bytes.resize(ReqSize); 226116029Smtm 227116029Smtm // Set our bits. 228113674Smtm AllocMask = 1 << Bit; 229113674Smtm for (uint64_t B : Bits) 230113674Smtm Bytes[AllocByteOffset + B] |= AllocMask; 231113674Smtm} 232113674Smtm 233113674Smtmnamespace { 234100280Sgordon 235113674Smtmstruct ByteArrayInfo { 236113674Smtm std::set<uint64_t> Bits; 237113674Smtm uint64_t BitSize; 238113674Smtm GlobalVariable *ByteArray; 239113674Smtm GlobalVariable *MaskGlobal; 240100280Sgordon uint8_t *MaskPtr = nullptr; 241100280Sgordon}; 242116029Smtm 243116029Smtm/// A POD-like structure that we use to store a global reference together with 244116029Smtm/// its metadata types. In this pass we frequently need to query the set of 245116029Smtm/// metadata types referenced by a global, which at the IR level is an expensive 246116029Smtm/// operation involving a map lookup; this data structure helps to reduce the 247116029Smtm/// number of times we need to do this lookup. 248116029Smtmclass GlobalTypeMember final : TrailingObjects<GlobalTypeMember, MDNode *> { 249116029Smtm friend TrailingObjects; 250116029Smtm 251116029Smtm GlobalObject *GO; 252116029Smtm size_t NTypes; 253116029Smtm 254116029Smtm // For functions: true if this is a definition (either in the merged module or 255116029Smtm // in one of the thinlto modules). 256113674Smtm bool IsDefinition; 257113674Smtm 258113674Smtm // For functions: true if this function is either defined or used in a thinlto 259100280Sgordon // module and its jumptable entry needs to be exported to thinlto backends. 260113674Smtm bool IsExported; 261113674Smtm 262113674Smtm size_t numTrailingObjects(OverloadToken<MDNode *>) const { return NTypes; } 263113674Smtm 264116774Skuriyamapublic: 265113674Smtm static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalObject *GO, 266113674Smtm bool IsDefinition, bool IsExported, 267113674Smtm ArrayRef<MDNode *> Types) { 268113674Smtm auto *GTM = static_cast<GlobalTypeMember *>(Alloc.Allocate( 269113674Smtm totalSizeToAlloc<MDNode *>(Types.size()), alignof(GlobalTypeMember))); 270113674Smtm GTM->GO = GO; 271100280Sgordon GTM->NTypes = Types.size(); 272113674Smtm GTM->IsDefinition = IsDefinition; 273113674Smtm GTM->IsExported = IsExported; 274113674Smtm std::uninitialized_copy(Types.begin(), Types.end(), 275113674Smtm GTM->getTrailingObjects<MDNode *>()); 276113674Smtm return GTM; 277113674Smtm } 278113674Smtm 279113674Smtm GlobalObject *getGlobal() const { 280113674Smtm return GO; 281116774Skuriyama } 282113674Smtm 283113674Smtm bool isDefinition() const { 284113674Smtm return IsDefinition; 285113674Smtm } 286113674Smtm 287100280Sgordon bool isExported() const { 288100280Sgordon return IsExported; 289113674Smtm } 290100282Sdougb 291100282Sdougb ArrayRef<MDNode *> types() const { 292100282Sdougb return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes); 293100282Sdougb } 294100282Sdougb}; 295100282Sdougb 296100282Sdougbstruct ICallBranchFunnel final 297100282Sdougb : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> { 298100282Sdougb static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI, 299100282Sdougb ArrayRef<GlobalTypeMember *> Targets, 300100282Sdougb unsigned UniqueId) { 301100282Sdougb auto *Call = static_cast<ICallBranchFunnel *>( 302100282Sdougb Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()), 303103710Sume alignof(ICallBranchFunnel))); 304100282Sdougb Call->CI = CI; 305100282Sdougb Call->UniqueId = UniqueId; 306100282Sdougb Call->NTargets = Targets.size(); 307100282Sdougb std::uninitialized_copy(Targets.begin(), Targets.end(), 308100282Sdougb Call->getTrailingObjects<GlobalTypeMember *>()); 309100282Sdougb return Call; 310100282Sdougb } 311113674Smtm 312113674Smtm CallInst *CI; 313113674Smtm ArrayRef<GlobalTypeMember *> targets() const { 314113674Smtm return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets); 315113674Smtm } 316113674Smtm 317100280Sgordon unsigned UniqueId; 318113674Smtm 319113674Smtmprivate: 320113674Smtm size_t NTargets; 321113674Smtm}; 322113674Smtm 32385831Sdesclass LowerTypeTestsModule { 324113674Smtm Module &M; 325113674Smtm 32685831Sdes ModuleSummaryIndex *ExportSummary; 327116029Smtm const ModuleSummaryIndex *ImportSummary; 328116029Smtm 329116029Smtm Triple::ArchType Arch; 330113674Smtm Triple::OSType OS; 331116029Smtm Triple::ObjectFormatType ObjectFormat; 332116029Smtm 333116100Smtm IntegerType *Int1Ty = Type::getInt1Ty(M.getContext()); 334116100Smtm IntegerType *Int8Ty = Type::getInt8Ty(M.getContext()); 335116100Smtm PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext()); 336116100Smtm ArrayType *Int8Arr0Ty = ArrayType::get(Type::getInt8Ty(M.getContext()), 0); 337116100Smtm IntegerType *Int32Ty = Type::getInt32Ty(M.getContext()); 338116100Smtm PointerType *Int32PtrTy = PointerType::getUnqual(Int32Ty); 339116100Smtm IntegerType *Int64Ty = Type::getInt64Ty(M.getContext()); 340116100Smtm IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0); 341116100Smtm 342116100Smtm // Indirect function call index assignment counter for WebAssembly 343116100Smtm uint64_t IndirectIndex = 1; 344116100Smtm 345116100Smtm // Mapping from type identifiers to the call sites that test them, as well as 346116100Smtm // whether the type identifier needs to be exported to ThinLTO backends as 347116100Smtm // part of the regular LTO phase of the ThinLTO pipeline (see exportTypeId). 348116100Smtm struct TypeIdUserInfo { 349116100Smtm std::vector<CallInst *> CallSites; 350116100Smtm bool IsExported = false; 351116100Smtm }; 352116100Smtm DenseMap<Metadata *, TypeIdUserInfo> TypeIdUsers; 353116100Smtm 354116100Smtm /// This structure describes how to lower type tests for a particular type 355116029Smtm /// identifier. It is either built directly from the global analysis (during 356116029Smtm /// regular LTO or the regular LTO phase of ThinLTO), or indirectly using type 357137070Spjd /// identifier summaries and external symbol references (in ThinLTO backends). 358137070Spjd struct TypeIdLowering { 359116029Smtm TypeTestResolution::Kind TheKind = TypeTestResolution::Unsat; 360137070Spjd 361137070Spjd /// All except Unsat: the start address within the combined global. 362137070Spjd Constant *OffsetedGlobal; 363138386Srse 364137070Spjd /// ByteArray, Inline, AllOnes: log2 of the required global alignment 365137070Spjd /// relative to the start address. 366137070Spjd Constant *AlignLog2; 367137070Spjd 368137070Spjd /// ByteArray, Inline, AllOnes: one less than the size of the memory region 369137070Spjd /// covering members of this type identifier as a multiple of 2^AlignLog2. 370137070Spjd Constant *SizeM1; 371137070Spjd 372137070Spjd /// ByteArray: the byte array to test the address against. 373137070Spjd Constant *TheByteArray; 374137070Spjd 375113674Smtm /// ByteArray: the bit mask to apply to bytes loaded from the byte array. 376113674Smtm Constant *BitMask; 377113674Smtm 378113674Smtm /// Inline: the bit mask to test the address against. 379113674Smtm Constant *InlineBits; 380113674Smtm }; 381113674Smtm 382134429Syar std::vector<ByteArrayInfo> ByteArrayInfos; 383134429Syar 384134429Syar Function *WeakInitializerFn = nullptr; 385113674Smtm 386113674Smtm bool shouldExportConstantsAsAbsoluteSymbols(); 387113674Smtm uint8_t *exportTypeId(StringRef TypeId, const TypeIdLowering &TIL); 388113674Smtm TypeIdLowering importTypeId(StringRef TypeId); 38965532Snectar void importTypeTest(CallInst *CI); 390113674Smtm void importFunction(Function *F, bool isDefinition); 39151231Ssheldonh 39251231Ssheldonh BitSetInfo 39351231Ssheldonh buildBitSet(Metadata *TypeId, 394113674Smtm const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); 39551231Ssheldonh ByteArrayInfo *createByteArray(BitSetInfo &BSI); 39683677Sbrooks void allocateByteArrays(); 397134429Syar Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL, 39883677Sbrooks Value *BitOffset); 39951231Ssheldonh void lowerTypeTestCalls( 40049122Sbrian ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, 401113674Smtm const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout); 402113674Smtm Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI, 403113674Smtm const TypeIdLowering &TIL); 404113674Smtm 40549122Sbrian void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds, 406138385Srse ArrayRef<GlobalTypeMember *> Globals); 407113674Smtm unsigned getJumpTableEntrySize(); 408113674Smtm Type *getJumpTableEntryType(); 409134376Syar void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS, 410113674Smtm Triple::ArchType JumpTableArch, 411113674Smtm SmallVectorImpl<Value *> &AsmArgs, Function *Dest); 412113674Smtm void verifyTypeMDNode(GlobalObject *GO, MDNode *Type); 41351231Ssheldonh void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds, 414113674Smtm ArrayRef<GlobalTypeMember *> Functions); 415113674Smtm void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds, 41651231Ssheldonh ArrayRef<GlobalTypeMember *> Functions); 417113674Smtm void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds, 418113674Smtm ArrayRef<GlobalTypeMember *> Functions); 419113674Smtm void 42051231Ssheldonh buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds, 42151231Ssheldonh ArrayRef<GlobalTypeMember *> Globals, 42254458Sobrien ArrayRef<ICallBranchFunnel *> ICallBranchFunnels); 42351231Ssheldonh 424118797Smbr void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT, bool IsDefinition); 425118797Smbr void moveInitializerToModuleConstructor(GlobalVariable *GV); 426118797Smbr void findGlobalVariableUsersOf(Constant *C, 427118797Smbr SmallSetVector<GlobalVariable *, 8> &Out); 428118797Smbr 429118797Smbr void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions); 430118797Smbr 431118797Smbr /// replaceCfiUses - Go through the uses list for this definition 432118797Smbr /// and make each use point to "V" instead of "this" when the use is outside 433118797Smbr /// the block. 'This's use list is expected to have at least one element. 434118797Smbr /// Unlike replaceAllUsesWith this function skips blockaddr and direct call 435118797Smbr /// uses. 436118797Smbr void replaceCfiUses(Function *Old, Value *New, bool IsDefinition); 437118797Smbr 438118797Smbr /// replaceDirectCalls - Go through the uses list for this definition and 439118797Smbr /// replace each use, which is a direct function call. 440118797Smbr void replaceDirectCalls(Value *Old, Value *New); 441118797Smbr 442113674Smtmpublic: 443113674Smtm LowerTypeTestsModule(Module &M, ModuleSummaryIndex *ExportSummary, 444113674Smtm const ModuleSummaryIndex *ImportSummary); 445113674Smtm 446113674Smtm bool lower(); 447113674Smtm 448113674Smtm // Lower the module using the action and summary passed as command line 449113674Smtm // arguments. For testing purposes only. 450130151Sschweikh static bool runForTesting(Module &M); 45125184Sjkh}; 452114942Sume 453114942Sumestruct LowerTypeTests : public ModulePass { 454114942Sume static char ID; 455114942Sume 456114942Sume bool UseCommandLine = false; 457114942Sume 458114942Sume ModuleSummaryIndex *ExportSummary; 459114942Sume const ModuleSummaryIndex *ImportSummary; 460114942Sume 461114942Sume LowerTypeTests() : ModulePass(ID), UseCommandLine(true) { 462114942Sume initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); 463114942Sume } 464114942Sume 465114942Sume LowerTypeTests(ModuleSummaryIndex *ExportSummary, 466114942Sume const ModuleSummaryIndex *ImportSummary) 467114942Sume : ModulePass(ID), ExportSummary(ExportSummary), 468114942Sume ImportSummary(ImportSummary) { 469114942Sume initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); 470114942Sume } 471114942Sume 472114942Sume bool runOnModule(Module &M) override { 473114942Sume if (UseCommandLine) 474114942Sume return LowerTypeTestsModule::runForTesting(M); 475114942Sume return LowerTypeTestsModule(M, ExportSummary, ImportSummary).lower(); 476114942Sume } 477114942Sume}; 478114942Sume 479114942Sume} // end anonymous namespace 480114942Sume 481114942Sumechar LowerTypeTests::ID = 0; 482114942Sume 483114942SumeINITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false, 484114942Sume false) 485114942Sume 486114942SumeModulePass * 487114942Sumellvm::createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, 488114942Sume const ModuleSummaryIndex *ImportSummary) { 489114942Sume return new LowerTypeTests(ExportSummary, ImportSummary); 490114942Sume} 491114942Sume 492114942Sume/// Build a bit set for TypeId using the object layouts in 493114942Sume/// GlobalLayout. 494114942SumeBitSetInfo LowerTypeTestsModule::buildBitSet( 495114942Sume Metadata *TypeId, 496114942Sume const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { 497114942Sume BitSetBuilder BSB; 498114942Sume 499114942Sume // Compute the byte offset of each address associated with this type 500114942Sume // identifier. 501114942Sume for (auto &GlobalAndOffset : GlobalLayout) { 502114942Sume for (MDNode *Type : GlobalAndOffset.first->types()) { 503114942Sume if (Type->getOperand(1) != TypeId) 504114942Sume continue; 505114942Sume uint64_t Offset = 506114942Sume cast<ConstantInt>( 507114942Sume cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 508114942Sume ->getZExtValue(); 509114942Sume BSB.addOffset(GlobalAndOffset.second + Offset); 510114942Sume } 511114942Sume } 512114942Sume 513114942Sume return BSB.build(); 514114942Sume} 515114942Sume 516114942Sume/// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in 517114942Sume/// Bits. This pattern matches to the bt instruction on x86. 518114942Sumestatic Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits, 519114942Sume Value *BitOffset) { 520114942Sume auto BitsType = cast<IntegerType>(Bits->getType()); 521114942Sume unsigned BitWidth = BitsType->getBitWidth(); 522114942Sume 523114942Sume BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType); 524114942Sume Value *BitIndex = 525114942Sume B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1)); 526114942Sume Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex); 527114942Sume Value *MaskedBits = B.CreateAnd(Bits, BitMask); 528114942Sume return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0)); 529114942Sume} 530114942Sume 531114942SumeByteArrayInfo *LowerTypeTestsModule::createByteArray(BitSetInfo &BSI) { 532114942Sume // Create globals to stand in for byte arrays and masks. These never actually 533114942Sume // get initialized, we RAUW and erase them later in allocateByteArrays() once 534114942Sume // we know the offset and mask to use. 535114942Sume auto ByteArrayGlobal = new GlobalVariable( 536114942Sume M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); 537114942Sume auto MaskGlobal = new GlobalVariable(M, Int8Ty, /*isConstant=*/true, 538114942Sume GlobalValue::PrivateLinkage, nullptr); 539114942Sume 540114942Sume ByteArrayInfos.emplace_back(); 541114942Sume ByteArrayInfo *BAI = &ByteArrayInfos.back(); 542114942Sume 543114942Sume BAI->Bits = BSI.Bits; 544114942Sume BAI->BitSize = BSI.BitSize; 545114942Sume BAI->ByteArray = ByteArrayGlobal; 546114942Sume BAI->MaskGlobal = MaskGlobal; 547114942Sume return BAI; 548114942Sume} 549114942Sume 550118666Sumevoid LowerTypeTestsModule::allocateByteArrays() { 551114942Sume llvm::stable_sort(ByteArrayInfos, 552114942Sume [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) { 553114942Sume return BAI1.BitSize > BAI2.BitSize; 554114942Sume }); 555114942Sume 556114942Sume std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size()); 557114942Sume 558114942Sume ByteArrayBuilder BAB; 559114942Sume for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { 560114942Sume ByteArrayInfo *BAI = &ByteArrayInfos[I]; 561114942Sume 562114942Sume uint8_t Mask; 563114942Sume BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask); 564114942Sume 565114942Sume BAI->MaskGlobal->replaceAllUsesWith( 566114942Sume ConstantExpr::getIntToPtr(ConstantInt::get(Int8Ty, Mask), Int8PtrTy)); 567114942Sume BAI->MaskGlobal->eraseFromParent(); 568114942Sume if (BAI->MaskPtr) 569114942Sume *BAI->MaskPtr = Mask; 570114942Sume } 571114942Sume 572114942Sume Constant *ByteArrayConst = ConstantDataArray::get(M.getContext(), BAB.Bytes); 573114942Sume auto ByteArray = 574114942Sume new GlobalVariable(M, ByteArrayConst->getType(), /*isConstant=*/true, 575114942Sume GlobalValue::PrivateLinkage, ByteArrayConst); 576114942Sume 577114942Sume for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { 578114942Sume ByteArrayInfo *BAI = &ByteArrayInfos[I]; 579114942Sume 580114942Sume Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0), 581114942Sume ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])}; 582114942Sume Constant *GEP = ConstantExpr::getInBoundsGetElementPtr( 583114942Sume ByteArrayConst->getType(), ByteArray, Idxs); 584114942Sume 585114942Sume // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures 586114942Sume // that the pc-relative displacement is folded into the lea instead of the 587114942Sume // test instruction getting another displacement. 588114942Sume GlobalAlias *Alias = GlobalAlias::create( 589114942Sume Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, &M); 590114942Sume BAI->ByteArray->replaceAllUsesWith(Alias); 591114942Sume BAI->ByteArray->eraseFromParent(); 592114942Sume } 593114942Sume 594114942Sume ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] + 595114942Sume BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] + 596114942Sume BAB.BitAllocs[6] + BAB.BitAllocs[7]; 597114942Sume ByteArraySizeBytes = BAB.Bytes.size(); 598114942Sume} 599114942Sume 600114942Sume/// Build a test that bit BitOffset is set in the type identifier that was 601114942Sume/// lowered to TIL, which must be either an Inline or a ByteArray. 602114942SumeValue *LowerTypeTestsModule::createBitSetTest(IRBuilder<> &B, 603114942Sume const TypeIdLowering &TIL, 604114942Sume Value *BitOffset) { 605114942Sume if (TIL.TheKind == TypeTestResolution::Inline) { 606114942Sume // If the bit set is sufficiently small, we can avoid a load by bit testing 607114942Sume // a constant. 608114942Sume return createMaskedBitTest(B, TIL.InlineBits, BitOffset); 609114942Sume } else { 610114942Sume Constant *ByteArray = TIL.TheByteArray; 611114942Sume if (AvoidReuse && !ImportSummary) { 612114942Sume // Each use of the byte array uses a different alias. This makes the 613114942Sume // backend less likely to reuse previously computed byte array addresses, 614114942Sume // improving the security of the CFI mechanism based on this pass. 615114942Sume // This won't work when importing because TheByteArray is external. 616114942Sume ByteArray = GlobalAlias::create(Int8Ty, 0, GlobalValue::PrivateLinkage, 617114942Sume "bits_use", ByteArray, &M); 618114942Sume } 619114942Sume 620114942Sume Value *ByteAddr = B.CreateGEP(Int8Ty, ByteArray, BitOffset); 621114942Sume Value *Byte = B.CreateLoad(Int8Ty, ByteAddr); 622114942Sume 623114942Sume Value *ByteAndMask = 624114942Sume B.CreateAnd(Byte, ConstantExpr::getPtrToInt(TIL.BitMask, Int8Ty)); 625114942Sume return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0)); 626114942Sume } 627114942Sume} 628114942Sume 629114942Sumestatic bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL, 630114942Sume Value *V, uint64_t COffset) { 631114942Sume if (auto GV = dyn_cast<GlobalObject>(V)) { 632114942Sume SmallVector<MDNode *, 2> Types; 633114942Sume GV->getMetadata(LLVMContext::MD_type, Types); 634114942Sume for (MDNode *Type : Types) { 635114942Sume if (Type->getOperand(1) != TypeId) 636114942Sume continue; 637114942Sume uint64_t Offset = 638114942Sume cast<ConstantInt>( 639114942Sume cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 640114942Sume ->getZExtValue(); 641114942Sume if (COffset == Offset) 642114942Sume return true; 643114942Sume } 644114942Sume return false; 645114942Sume } 646114942Sume 647114942Sume if (auto GEP = dyn_cast<GEPOperator>(V)) { 648114942Sume APInt APOffset(DL.getPointerSizeInBits(0), 0); 649114942Sume bool Result = GEP->accumulateConstantOffset(DL, APOffset); 650114942Sume if (!Result) 651114942Sume return false; 652114942Sume COffset += APOffset.getZExtValue(); 653114942Sume return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset); 654114942Sume } 655114942Sume 656114942Sume if (auto Op = dyn_cast<Operator>(V)) { 657114942Sume if (Op->getOpcode() == Instruction::BitCast) 658114942Sume return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset); 659114942Sume 660114942Sume if (Op->getOpcode() == Instruction::Select) 661114942Sume return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) && 662114942Sume isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset); 663114942Sume } 664114942Sume 665114942Sume return false; 666114942Sume} 667114942Sume 668114942Sume/// Lower a llvm.type.test call to its implementation. Returns the value to 669114942Sume/// replace the call with. 670114942SumeValue *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI, 671114942Sume const TypeIdLowering &TIL) { 672114942Sume if (TIL.TheKind == TypeTestResolution::Unsat) 673114942Sume return ConstantInt::getFalse(M.getContext()); 674114942Sume 675114942Sume Value *Ptr = CI->getArgOperand(0); 676114942Sume const DataLayout &DL = M.getDataLayout(); 677114942Sume if (isKnownTypeIdMember(TypeId, DL, Ptr, 0)) 678114942Sume return ConstantInt::getTrue(M.getContext()); 679114942Sume 680114942Sume BasicBlock *InitialBB = CI->getParent(); 681114942Sume 682114942Sume IRBuilder<> B(CI); 683114942Sume 684114942Sume Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); 685114942Sume 686114942Sume Constant *OffsetedGlobalAsInt = 687114942Sume ConstantExpr::getPtrToInt(TIL.OffsetedGlobal, IntPtrTy); 688114942Sume if (TIL.TheKind == TypeTestResolution::Single) 689114942Sume return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt); 690114942Sume 691114942Sume Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt); 692114942Sume 693114942Sume // We need to check that the offset both falls within our range and is 694114942Sume // suitably aligned. We can check both properties at the same time by 695114942Sume // performing a right rotate by log2(alignment) followed by an integer 696114942Sume // comparison against the bitset size. The rotate will move the lower 697114942Sume // order bits that need to be zero into the higher order bits of the 698114942Sume // result, causing the comparison to fail if they are nonzero. The rotate 699114942Sume // also conveniently gives us a bit offset to use during the load from 700114942Sume // the bitset. 701114942Sume Value *OffsetSHR = 702114942Sume B.CreateLShr(PtrOffset, ConstantExpr::getZExt(TIL.AlignLog2, IntPtrTy)); 703114942Sume Value *OffsetSHL = B.CreateShl( 704114942Sume PtrOffset, ConstantExpr::getZExt( 705114942Sume ConstantExpr::getSub( 706114942Sume ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)), 707114942Sume TIL.AlignLog2), 708114942Sume IntPtrTy)); 709114942Sume Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL); 710114942Sume 711114942Sume Value *OffsetInRange = B.CreateICmpULE(BitOffset, TIL.SizeM1); 712114942Sume 713114942Sume // If the bit set is all ones, testing against it is unnecessary. 714114942Sume if (TIL.TheKind == TypeTestResolution::AllOnes) 715114942Sume return OffsetInRange; 716114942Sume 717114942Sume // See if the intrinsic is used in the following common pattern: 718114942Sume // br(llvm.type.test(...), thenbb, elsebb) 719114942Sume // where nothing happens between the type test and the br. 720114942Sume // If so, create slightly simpler IR. 721114942Sume if (CI->hasOneUse()) 722114942Sume if (auto *Br = dyn_cast<BranchInst>(*CI->user_begin())) 723114942Sume if (CI->getNextNode() == Br) { 724114942Sume BasicBlock *Then = InitialBB->splitBasicBlock(CI->getIterator()); 725114942Sume BasicBlock *Else = Br->getSuccessor(1); 726114942Sume BranchInst *NewBr = BranchInst::Create(Then, Else, OffsetInRange); 727114942Sume NewBr->setMetadata(LLVMContext::MD_prof, 728114942Sume Br->getMetadata(LLVMContext::MD_prof)); 729114942Sume ReplaceInstWithInst(InitialBB->getTerminator(), NewBr); 730114942Sume 731114942Sume // Update phis in Else resulting from InitialBB being split 732114942Sume for (auto &Phi : Else->phis()) 733114942Sume Phi.addIncoming(Phi.getIncomingValueForBlock(Then), InitialBB); 734114942Sume 735114942Sume IRBuilder<> ThenB(CI); 736114942Sume return createBitSetTest(ThenB, TIL, BitOffset); 737114942Sume } 738114942Sume 739114942Sume IRBuilder<> ThenB(SplitBlockAndInsertIfThen(OffsetInRange, CI, false)); 740114942Sume 741114942Sume // Now that we know that the offset is in range and aligned, load the 742114942Sume // appropriate bit from the bitset. 743114942Sume Value *Bit = createBitSetTest(ThenB, TIL, BitOffset); 744114942Sume 745114942Sume // The value we want is 0 if we came directly from the initial block 746114942Sume // (having failed the range or alignment checks), or the loaded bit if 747114942Sume // we came from the block in which we loaded it. 748 B.SetInsertPoint(CI); 749 PHINode *P = B.CreatePHI(Int1Ty, 2); 750 P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB); 751 P->addIncoming(Bit, ThenB.GetInsertBlock()); 752 return P; 753} 754 755/// Given a disjoint set of type identifiers and globals, lay out the globals, 756/// build the bit sets and lower the llvm.type.test calls. 757void LowerTypeTestsModule::buildBitSetsFromGlobalVariables( 758 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) { 759 // Build a new global with the combined contents of the referenced globals. 760 // This global is a struct whose even-indexed elements contain the original 761 // contents of the referenced globals and whose odd-indexed elements contain 762 // any padding required to align the next element to the next power of 2. 763 std::vector<Constant *> GlobalInits; 764 const DataLayout &DL = M.getDataLayout(); 765 for (GlobalTypeMember *G : Globals) { 766 GlobalVariable *GV = cast<GlobalVariable>(G->getGlobal()); 767 GlobalInits.push_back(GV->getInitializer()); 768 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType()); 769 770 // Compute the amount of padding required. 771 uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize; 772 773 // Experiments of different caps with Chromium on both x64 and ARM64 774 // have shown that the 32-byte cap generates the smallest binary on 775 // both platforms while different caps yield similar performance. 776 // (see https://lists.llvm.org/pipermail/llvm-dev/2018-July/124694.html) 777 if (Padding > 32) 778 Padding = alignTo(InitSize, 32) - InitSize; 779 780 GlobalInits.push_back( 781 ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding))); 782 } 783 if (!GlobalInits.empty()) 784 GlobalInits.pop_back(); 785 Constant *NewInit = ConstantStruct::getAnon(M.getContext(), GlobalInits); 786 auto *CombinedGlobal = 787 new GlobalVariable(M, NewInit->getType(), /*isConstant=*/true, 788 GlobalValue::PrivateLinkage, NewInit); 789 790 StructType *NewTy = cast<StructType>(NewInit->getType()); 791 const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy); 792 793 // Compute the offsets of the original globals within the new global. 794 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; 795 for (unsigned I = 0; I != Globals.size(); ++I) 796 // Multiply by 2 to account for padding elements. 797 GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2); 798 799 lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout); 800 801 // Build aliases pointing to offsets into the combined global for each 802 // global from which we built the combined global, and replace references 803 // to the original globals with references to the aliases. 804 for (unsigned I = 0; I != Globals.size(); ++I) { 805 GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal()); 806 807 // Multiply by 2 to account for padding elements. 808 Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), 809 ConstantInt::get(Int32Ty, I * 2)}; 810 Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( 811 NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs); 812 assert(GV->getType()->getAddressSpace() == 0); 813 GlobalAlias *GAlias = 814 GlobalAlias::create(NewTy->getElementType(I * 2), 0, GV->getLinkage(), 815 "", CombinedGlobalElemPtr, &M); 816 GAlias->setVisibility(GV->getVisibility()); 817 GAlias->takeName(GV); 818 GV->replaceAllUsesWith(GAlias); 819 GV->eraseFromParent(); 820 } 821} 822 823bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() { 824 return (Arch == Triple::x86 || Arch == Triple::x86_64) && 825 ObjectFormat == Triple::ELF; 826} 827 828/// Export the given type identifier so that ThinLTO backends may import it. 829/// Type identifiers are exported by adding coarse-grained information about how 830/// to test the type identifier to the summary, and creating symbols in the 831/// object file (aliases and absolute symbols) containing fine-grained 832/// information about the type identifier. 833/// 834/// Returns a pointer to the location in which to store the bitmask, if 835/// applicable. 836uint8_t *LowerTypeTestsModule::exportTypeId(StringRef TypeId, 837 const TypeIdLowering &TIL) { 838 TypeTestResolution &TTRes = 839 ExportSummary->getOrInsertTypeIdSummary(TypeId).TTRes; 840 TTRes.TheKind = TIL.TheKind; 841 842 auto ExportGlobal = [&](StringRef Name, Constant *C) { 843 GlobalAlias *GA = 844 GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage, 845 "__typeid_" + TypeId + "_" + Name, C, &M); 846 GA->setVisibility(GlobalValue::HiddenVisibility); 847 }; 848 849 auto ExportConstant = [&](StringRef Name, uint64_t &Storage, Constant *C) { 850 if (shouldExportConstantsAsAbsoluteSymbols()) 851 ExportGlobal(Name, ConstantExpr::getIntToPtr(C, Int8PtrTy)); 852 else 853 Storage = cast<ConstantInt>(C)->getZExtValue(); 854 }; 855 856 if (TIL.TheKind != TypeTestResolution::Unsat) 857 ExportGlobal("global_addr", TIL.OffsetedGlobal); 858 859 if (TIL.TheKind == TypeTestResolution::ByteArray || 860 TIL.TheKind == TypeTestResolution::Inline || 861 TIL.TheKind == TypeTestResolution::AllOnes) { 862 ExportConstant("align", TTRes.AlignLog2, TIL.AlignLog2); 863 ExportConstant("size_m1", TTRes.SizeM1, TIL.SizeM1); 864 865 uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1; 866 if (TIL.TheKind == TypeTestResolution::Inline) 867 TTRes.SizeM1BitWidth = (BitSize <= 32) ? 5 : 6; 868 else 869 TTRes.SizeM1BitWidth = (BitSize <= 128) ? 7 : 32; 870 } 871 872 if (TIL.TheKind == TypeTestResolution::ByteArray) { 873 ExportGlobal("byte_array", TIL.TheByteArray); 874 if (shouldExportConstantsAsAbsoluteSymbols()) 875 ExportGlobal("bit_mask", TIL.BitMask); 876 else 877 return &TTRes.BitMask; 878 } 879 880 if (TIL.TheKind == TypeTestResolution::Inline) 881 ExportConstant("inline_bits", TTRes.InlineBits, TIL.InlineBits); 882 883 return nullptr; 884} 885 886LowerTypeTestsModule::TypeIdLowering 887LowerTypeTestsModule::importTypeId(StringRef TypeId) { 888 const TypeIdSummary *TidSummary = ImportSummary->getTypeIdSummary(TypeId); 889 if (!TidSummary) 890 return {}; // Unsat: no globals match this type id. 891 const TypeTestResolution &TTRes = TidSummary->TTRes; 892 893 TypeIdLowering TIL; 894 TIL.TheKind = TTRes.TheKind; 895 896 auto ImportGlobal = [&](StringRef Name) { 897 // Give the global a type of length 0 so that it is not assumed not to alias 898 // with any other global. 899 Constant *C = M.getOrInsertGlobal(("__typeid_" + TypeId + "_" + Name).str(), 900 Int8Arr0Ty); 901 if (auto *GV = dyn_cast<GlobalVariable>(C)) 902 GV->setVisibility(GlobalValue::HiddenVisibility); 903 C = ConstantExpr::getBitCast(C, Int8PtrTy); 904 return C; 905 }; 906 907 auto ImportConstant = [&](StringRef Name, uint64_t Const, unsigned AbsWidth, 908 Type *Ty) { 909 if (!shouldExportConstantsAsAbsoluteSymbols()) { 910 Constant *C = 911 ConstantInt::get(isa<IntegerType>(Ty) ? Ty : Int64Ty, Const); 912 if (!isa<IntegerType>(Ty)) 913 C = ConstantExpr::getIntToPtr(C, Ty); 914 return C; 915 } 916 917 Constant *C = ImportGlobal(Name); 918 auto *GV = cast<GlobalVariable>(C->stripPointerCasts()); 919 if (isa<IntegerType>(Ty)) 920 C = ConstantExpr::getPtrToInt(C, Ty); 921 if (GV->getMetadata(LLVMContext::MD_absolute_symbol)) 922 return C; 923 924 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) { 925 auto *MinC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Min)); 926 auto *MaxC = ConstantAsMetadata::get(ConstantInt::get(IntPtrTy, Max)); 927 GV->setMetadata(LLVMContext::MD_absolute_symbol, 928 MDNode::get(M.getContext(), {MinC, MaxC})); 929 }; 930 if (AbsWidth == IntPtrTy->getBitWidth()) 931 SetAbsRange(~0ull, ~0ull); // Full set. 932 else 933 SetAbsRange(0, 1ull << AbsWidth); 934 return C; 935 }; 936 937 if (TIL.TheKind != TypeTestResolution::Unsat) 938 TIL.OffsetedGlobal = ImportGlobal("global_addr"); 939 940 if (TIL.TheKind == TypeTestResolution::ByteArray || 941 TIL.TheKind == TypeTestResolution::Inline || 942 TIL.TheKind == TypeTestResolution::AllOnes) { 943 TIL.AlignLog2 = ImportConstant("align", TTRes.AlignLog2, 8, Int8Ty); 944 TIL.SizeM1 = 945 ImportConstant("size_m1", TTRes.SizeM1, TTRes.SizeM1BitWidth, IntPtrTy); 946 } 947 948 if (TIL.TheKind == TypeTestResolution::ByteArray) { 949 TIL.TheByteArray = ImportGlobal("byte_array"); 950 TIL.BitMask = ImportConstant("bit_mask", TTRes.BitMask, 8, Int8PtrTy); 951 } 952 953 if (TIL.TheKind == TypeTestResolution::Inline) 954 TIL.InlineBits = ImportConstant( 955 "inline_bits", TTRes.InlineBits, 1 << TTRes.SizeM1BitWidth, 956 TTRes.SizeM1BitWidth <= 5 ? Int32Ty : Int64Ty); 957 958 return TIL; 959} 960 961void LowerTypeTestsModule::importTypeTest(CallInst *CI) { 962 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); 963 if (!TypeIdMDVal) 964 report_fatal_error("Second argument of llvm.type.test must be metadata"); 965 966 auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata()); 967 if (!TypeIdStr) 968 report_fatal_error( 969 "Second argument of llvm.type.test must be a metadata string"); 970 971 TypeIdLowering TIL = importTypeId(TypeIdStr->getString()); 972 Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL); 973 CI->replaceAllUsesWith(Lowered); 974 CI->eraseFromParent(); 975} 976 977// ThinLTO backend: the function F has a jump table entry; update this module 978// accordingly. isDefinition describes the type of the jump table entry. 979void LowerTypeTestsModule::importFunction(Function *F, bool isDefinition) { 980 assert(F->getType()->getAddressSpace() == 0); 981 982 GlobalValue::VisibilityTypes Visibility = F->getVisibility(); 983 std::string Name = F->getName(); 984 985 if (F->isDeclarationForLinker() && isDefinition) { 986 // Non-dso_local functions may be overriden at run time, 987 // don't short curcuit them 988 if (F->isDSOLocal()) { 989 Function *RealF = Function::Create(F->getFunctionType(), 990 GlobalValue::ExternalLinkage, 991 F->getAddressSpace(), 992 Name + ".cfi", &M); 993 RealF->setVisibility(GlobalVariable::HiddenVisibility); 994 replaceDirectCalls(F, RealF); 995 } 996 return; 997 } 998 999 Function *FDecl; 1000 if (F->isDeclarationForLinker() && !isDefinition) { 1001 // Declaration of an external function. 1002 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, 1003 F->getAddressSpace(), Name + ".cfi_jt", &M); 1004 FDecl->setVisibility(GlobalValue::HiddenVisibility); 1005 } else if (isDefinition) { 1006 F->setName(Name + ".cfi"); 1007 F->setLinkage(GlobalValue::ExternalLinkage); 1008 FDecl = Function::Create(F->getFunctionType(), GlobalValue::ExternalLinkage, 1009 F->getAddressSpace(), Name, &M); 1010 FDecl->setVisibility(Visibility); 1011 Visibility = GlobalValue::HiddenVisibility; 1012 1013 // Delete aliases pointing to this function, they'll be re-created in the 1014 // merged output 1015 SmallVector<GlobalAlias*, 4> ToErase; 1016 for (auto &U : F->uses()) { 1017 if (auto *A = dyn_cast<GlobalAlias>(U.getUser())) { 1018 Function *AliasDecl = Function::Create( 1019 F->getFunctionType(), GlobalValue::ExternalLinkage, 1020 F->getAddressSpace(), "", &M); 1021 AliasDecl->takeName(A); 1022 A->replaceAllUsesWith(AliasDecl); 1023 ToErase.push_back(A); 1024 } 1025 } 1026 for (auto *A : ToErase) 1027 A->eraseFromParent(); 1028 } else { 1029 // Function definition without type metadata, where some other translation 1030 // unit contained a declaration with type metadata. This normally happens 1031 // during mixed CFI + non-CFI compilation. We do nothing with the function 1032 // so that it is treated the same way as a function defined outside of the 1033 // LTO unit. 1034 return; 1035 } 1036 1037 if (F->isWeakForLinker()) 1038 replaceWeakDeclarationWithJumpTablePtr(F, FDecl, isDefinition); 1039 else 1040 replaceCfiUses(F, FDecl, isDefinition); 1041 1042 // Set visibility late because it's used in replaceCfiUses() to determine 1043 // whether uses need to to be replaced. 1044 F->setVisibility(Visibility); 1045} 1046 1047void LowerTypeTestsModule::lowerTypeTestCalls( 1048 ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr, 1049 const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) { 1050 CombinedGlobalAddr = ConstantExpr::getBitCast(CombinedGlobalAddr, Int8PtrTy); 1051 1052 // For each type identifier in this disjoint set... 1053 for (Metadata *TypeId : TypeIds) { 1054 // Build the bitset. 1055 BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout); 1056 LLVM_DEBUG({ 1057 if (auto MDS = dyn_cast<MDString>(TypeId)) 1058 dbgs() << MDS->getString() << ": "; 1059 else 1060 dbgs() << "<unnamed>: "; 1061 BSI.print(dbgs()); 1062 }); 1063 1064 ByteArrayInfo *BAI = nullptr; 1065 TypeIdLowering TIL; 1066 TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr( 1067 Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)), 1068 TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2); 1069 TIL.SizeM1 = ConstantInt::get(IntPtrTy, BSI.BitSize - 1); 1070 if (BSI.isAllOnes()) { 1071 TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single 1072 : TypeTestResolution::AllOnes; 1073 } else if (BSI.BitSize <= 64) { 1074 TIL.TheKind = TypeTestResolution::Inline; 1075 uint64_t InlineBits = 0; 1076 for (auto Bit : BSI.Bits) 1077 InlineBits |= uint64_t(1) << Bit; 1078 if (InlineBits == 0) 1079 TIL.TheKind = TypeTestResolution::Unsat; 1080 else 1081 TIL.InlineBits = ConstantInt::get( 1082 (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits); 1083 } else { 1084 TIL.TheKind = TypeTestResolution::ByteArray; 1085 ++NumByteArraysCreated; 1086 BAI = createByteArray(BSI); 1087 TIL.TheByteArray = BAI->ByteArray; 1088 TIL.BitMask = BAI->MaskGlobal; 1089 } 1090 1091 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId]; 1092 1093 if (TIUI.IsExported) { 1094 uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL); 1095 if (BAI) 1096 BAI->MaskPtr = MaskPtr; 1097 } 1098 1099 // Lower each call to llvm.type.test for this type identifier. 1100 for (CallInst *CI : TIUI.CallSites) { 1101 ++NumTypeTestCallsLowered; 1102 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL); 1103 CI->replaceAllUsesWith(Lowered); 1104 CI->eraseFromParent(); 1105 } 1106 } 1107} 1108 1109void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) { 1110 if (Type->getNumOperands() != 2) 1111 report_fatal_error("All operands of type metadata must have 2 elements"); 1112 1113 if (GO->isThreadLocal()) 1114 report_fatal_error("Bit set element may not be thread-local"); 1115 if (isa<GlobalVariable>(GO) && GO->hasSection()) 1116 report_fatal_error( 1117 "A member of a type identifier may not have an explicit section"); 1118 1119 // FIXME: We previously checked that global var member of a type identifier 1120 // must be a definition, but the IR linker may leave type metadata on 1121 // declarations. We should restore this check after fixing PR31759. 1122 1123 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(Type->getOperand(0)); 1124 if (!OffsetConstMD) 1125 report_fatal_error("Type offset must be a constant"); 1126 auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue()); 1127 if (!OffsetInt) 1128 report_fatal_error("Type offset must be an integer constant"); 1129} 1130 1131static const unsigned kX86JumpTableEntrySize = 8; 1132static const unsigned kARMJumpTableEntrySize = 4; 1133 1134unsigned LowerTypeTestsModule::getJumpTableEntrySize() { 1135 switch (Arch) { 1136 case Triple::x86: 1137 case Triple::x86_64: 1138 return kX86JumpTableEntrySize; 1139 case Triple::arm: 1140 case Triple::thumb: 1141 case Triple::aarch64: 1142 return kARMJumpTableEntrySize; 1143 default: 1144 report_fatal_error("Unsupported architecture for jump tables"); 1145 } 1146} 1147 1148// Create a jump table entry for the target. This consists of an instruction 1149// sequence containing a relative branch to Dest. Appends inline asm text, 1150// constraints and arguments to AsmOS, ConstraintOS and AsmArgs. 1151void LowerTypeTestsModule::createJumpTableEntry( 1152 raw_ostream &AsmOS, raw_ostream &ConstraintOS, 1153 Triple::ArchType JumpTableArch, SmallVectorImpl<Value *> &AsmArgs, 1154 Function *Dest) { 1155 unsigned ArgIndex = AsmArgs.size(); 1156 1157 if (JumpTableArch == Triple::x86 || JumpTableArch == Triple::x86_64) { 1158 AsmOS << "jmp ${" << ArgIndex << ":c}@plt\n"; 1159 AsmOS << "int3\nint3\nint3\n"; 1160 } else if (JumpTableArch == Triple::arm || JumpTableArch == Triple::aarch64) { 1161 AsmOS << "b $" << ArgIndex << "\n"; 1162 } else if (JumpTableArch == Triple::thumb) { 1163 AsmOS << "b.w $" << ArgIndex << "\n"; 1164 } else { 1165 report_fatal_error("Unsupported architecture for jump tables"); 1166 } 1167 1168 ConstraintOS << (ArgIndex > 0 ? ",s" : "s"); 1169 AsmArgs.push_back(Dest); 1170} 1171 1172Type *LowerTypeTestsModule::getJumpTableEntryType() { 1173 return ArrayType::get(Int8Ty, getJumpTableEntrySize()); 1174} 1175 1176/// Given a disjoint set of type identifiers and functions, build the bit sets 1177/// and lower the llvm.type.test calls, architecture dependently. 1178void LowerTypeTestsModule::buildBitSetsFromFunctions( 1179 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { 1180 if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm || 1181 Arch == Triple::thumb || Arch == Triple::aarch64) 1182 buildBitSetsFromFunctionsNative(TypeIds, Functions); 1183 else if (Arch == Triple::wasm32 || Arch == Triple::wasm64) 1184 buildBitSetsFromFunctionsWASM(TypeIds, Functions); 1185 else 1186 report_fatal_error("Unsupported architecture for jump tables"); 1187} 1188 1189void LowerTypeTestsModule::moveInitializerToModuleConstructor( 1190 GlobalVariable *GV) { 1191 if (WeakInitializerFn == nullptr) { 1192 WeakInitializerFn = Function::Create( 1193 FunctionType::get(Type::getVoidTy(M.getContext()), 1194 /* IsVarArg */ false), 1195 GlobalValue::InternalLinkage, 1196 M.getDataLayout().getProgramAddressSpace(), 1197 "__cfi_global_var_init", &M); 1198 BasicBlock *BB = 1199 BasicBlock::Create(M.getContext(), "entry", WeakInitializerFn); 1200 ReturnInst::Create(M.getContext(), BB); 1201 WeakInitializerFn->setSection( 1202 ObjectFormat == Triple::MachO 1203 ? "__TEXT,__StaticInit,regular,pure_instructions" 1204 : ".text.startup"); 1205 // This code is equivalent to relocation application, and should run at the 1206 // earliest possible time (i.e. with the highest priority). 1207 appendToGlobalCtors(M, WeakInitializerFn, /* Priority */ 0); 1208 } 1209 1210 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator()); 1211 GV->setConstant(false); 1212 IRB.CreateAlignedStore(GV->getInitializer(), GV, GV->getAlignment()); 1213 GV->setInitializer(Constant::getNullValue(GV->getValueType())); 1214} 1215 1216void LowerTypeTestsModule::findGlobalVariableUsersOf( 1217 Constant *C, SmallSetVector<GlobalVariable *, 8> &Out) { 1218 for (auto *U : C->users()){ 1219 if (auto *GV = dyn_cast<GlobalVariable>(U)) 1220 Out.insert(GV); 1221 else if (auto *C2 = dyn_cast<Constant>(U)) 1222 findGlobalVariableUsersOf(C2, Out); 1223 } 1224} 1225 1226// Replace all uses of F with (F ? JT : 0). 1227void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr( 1228 Function *F, Constant *JT, bool IsDefinition) { 1229 // The target expression can not appear in a constant initializer on most 1230 // (all?) targets. Switch to a runtime initializer. 1231 SmallSetVector<GlobalVariable *, 8> GlobalVarUsers; 1232 findGlobalVariableUsersOf(F, GlobalVarUsers); 1233 for (auto GV : GlobalVarUsers) 1234 moveInitializerToModuleConstructor(GV); 1235 1236 // Can not RAUW F with an expression that uses F. Replace with a temporary 1237 // placeholder first. 1238 Function *PlaceholderFn = 1239 Function::Create(cast<FunctionType>(F->getValueType()), 1240 GlobalValue::ExternalWeakLinkage, 1241 F->getAddressSpace(), "", &M); 1242 replaceCfiUses(F, PlaceholderFn, IsDefinition); 1243 1244 Constant *Target = ConstantExpr::getSelect( 1245 ConstantExpr::getICmp(CmpInst::ICMP_NE, F, 1246 Constant::getNullValue(F->getType())), 1247 JT, Constant::getNullValue(F->getType())); 1248 PlaceholderFn->replaceAllUsesWith(Target); 1249 PlaceholderFn->eraseFromParent(); 1250} 1251 1252static bool isThumbFunction(Function *F, Triple::ArchType ModuleArch) { 1253 Attribute TFAttr = F->getFnAttribute("target-features"); 1254 if (!TFAttr.hasAttribute(Attribute::None)) { 1255 SmallVector<StringRef, 6> Features; 1256 TFAttr.getValueAsString().split(Features, ','); 1257 for (StringRef Feature : Features) { 1258 if (Feature == "-thumb-mode") 1259 return false; 1260 else if (Feature == "+thumb-mode") 1261 return true; 1262 } 1263 } 1264 1265 return ModuleArch == Triple::thumb; 1266} 1267 1268// Each jump table must be either ARM or Thumb as a whole for the bit-test math 1269// to work. Pick one that matches the majority of members to minimize interop 1270// veneers inserted by the linker. 1271static Triple::ArchType 1272selectJumpTableArmEncoding(ArrayRef<GlobalTypeMember *> Functions, 1273 Triple::ArchType ModuleArch) { 1274 if (ModuleArch != Triple::arm && ModuleArch != Triple::thumb) 1275 return ModuleArch; 1276 1277 unsigned ArmCount = 0, ThumbCount = 0; 1278 for (const auto GTM : Functions) { 1279 if (!GTM->isDefinition()) { 1280 // PLT stubs are always ARM. 1281 ++ArmCount; 1282 continue; 1283 } 1284 1285 Function *F = cast<Function>(GTM->getGlobal()); 1286 ++(isThumbFunction(F, ModuleArch) ? ThumbCount : ArmCount); 1287 } 1288 1289 return ArmCount > ThumbCount ? Triple::arm : Triple::thumb; 1290} 1291 1292void LowerTypeTestsModule::createJumpTable( 1293 Function *F, ArrayRef<GlobalTypeMember *> Functions) { 1294 std::string AsmStr, ConstraintStr; 1295 raw_string_ostream AsmOS(AsmStr), ConstraintOS(ConstraintStr); 1296 SmallVector<Value *, 16> AsmArgs; 1297 AsmArgs.reserve(Functions.size() * 2); 1298 1299 Triple::ArchType JumpTableArch = selectJumpTableArmEncoding(Functions, Arch); 1300 1301 for (unsigned I = 0; I != Functions.size(); ++I) 1302 createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs, 1303 cast<Function>(Functions[I]->getGlobal())); 1304 1305 // Align the whole table by entry size. 1306 F->setAlignment(getJumpTableEntrySize()); 1307 // Skip prologue. 1308 // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3. 1309 // Luckily, this function does not get any prologue even without the 1310 // attribute. 1311 if (OS != Triple::Win32) 1312 F->addFnAttr(Attribute::Naked); 1313 if (JumpTableArch == Triple::arm) 1314 F->addFnAttr("target-features", "-thumb-mode"); 1315 if (JumpTableArch == Triple::thumb) { 1316 F->addFnAttr("target-features", "+thumb-mode"); 1317 // Thumb jump table assembly needs Thumb2. The following attribute is added 1318 // by Clang for -march=armv7. 1319 F->addFnAttr("target-cpu", "cortex-a8"); 1320 } 1321 // Make sure we don't emit .eh_frame for this function. 1322 F->addFnAttr(Attribute::NoUnwind); 1323 1324 BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", F); 1325 IRBuilder<> IRB(BB); 1326 1327 SmallVector<Type *, 16> ArgTypes; 1328 ArgTypes.reserve(AsmArgs.size()); 1329 for (const auto &Arg : AsmArgs) 1330 ArgTypes.push_back(Arg->getType()); 1331 InlineAsm *JumpTableAsm = 1332 InlineAsm::get(FunctionType::get(IRB.getVoidTy(), ArgTypes, false), 1333 AsmOS.str(), ConstraintOS.str(), 1334 /*hasSideEffects=*/true); 1335 1336 IRB.CreateCall(JumpTableAsm, AsmArgs); 1337 IRB.CreateUnreachable(); 1338} 1339 1340/// Given a disjoint set of type identifiers and functions, build a jump table 1341/// for the functions, build the bit sets and lower the llvm.type.test calls. 1342void LowerTypeTestsModule::buildBitSetsFromFunctionsNative( 1343 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { 1344 // Unlike the global bitset builder, the function bitset builder cannot 1345 // re-arrange functions in a particular order and base its calculations on the 1346 // layout of the functions' entry points, as we have no idea how large a 1347 // particular function will end up being (the size could even depend on what 1348 // this pass does!) Instead, we build a jump table, which is a block of code 1349 // consisting of one branch instruction for each of the functions in the bit 1350 // set that branches to the target function, and redirect any taken function 1351 // addresses to the corresponding jump table entry. In the object file's 1352 // symbol table, the symbols for the target functions also refer to the jump 1353 // table entries, so that addresses taken outside the module will pass any 1354 // verification done inside the module. 1355 // 1356 // In more concrete terms, suppose we have three functions f, g, h which are 1357 // of the same type, and a function foo that returns their addresses: 1358 // 1359 // f: 1360 // mov 0, %eax 1361 // ret 1362 // 1363 // g: 1364 // mov 1, %eax 1365 // ret 1366 // 1367 // h: 1368 // mov 2, %eax 1369 // ret 1370 // 1371 // foo: 1372 // mov f, %eax 1373 // mov g, %edx 1374 // mov h, %ecx 1375 // ret 1376 // 1377 // We output the jump table as module-level inline asm string. The end result 1378 // will (conceptually) look like this: 1379 // 1380 // f = .cfi.jumptable 1381 // g = .cfi.jumptable + 4 1382 // h = .cfi.jumptable + 8 1383 // .cfi.jumptable: 1384 // jmp f.cfi ; 5 bytes 1385 // int3 ; 1 byte 1386 // int3 ; 1 byte 1387 // int3 ; 1 byte 1388 // jmp g.cfi ; 5 bytes 1389 // int3 ; 1 byte 1390 // int3 ; 1 byte 1391 // int3 ; 1 byte 1392 // jmp h.cfi ; 5 bytes 1393 // int3 ; 1 byte 1394 // int3 ; 1 byte 1395 // int3 ; 1 byte 1396 // 1397 // f.cfi: 1398 // mov 0, %eax 1399 // ret 1400 // 1401 // g.cfi: 1402 // mov 1, %eax 1403 // ret 1404 // 1405 // h.cfi: 1406 // mov 2, %eax 1407 // ret 1408 // 1409 // foo: 1410 // mov f, %eax 1411 // mov g, %edx 1412 // mov h, %ecx 1413 // ret 1414 // 1415 // Because the addresses of f, g, h are evenly spaced at a power of 2, in the 1416 // normal case the check can be carried out using the same kind of simple 1417 // arithmetic that we normally use for globals. 1418 1419 // FIXME: find a better way to represent the jumptable in the IR. 1420 assert(!Functions.empty()); 1421 1422 // Build a simple layout based on the regular layout of jump tables. 1423 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; 1424 unsigned EntrySize = getJumpTableEntrySize(); 1425 for (unsigned I = 0; I != Functions.size(); ++I) 1426 GlobalLayout[Functions[I]] = I * EntrySize; 1427 1428 Function *JumpTableFn = 1429 Function::Create(FunctionType::get(Type::getVoidTy(M.getContext()), 1430 /* IsVarArg */ false), 1431 GlobalValue::PrivateLinkage, 1432 M.getDataLayout().getProgramAddressSpace(), 1433 ".cfi.jumptable", &M); 1434 ArrayType *JumpTableType = 1435 ArrayType::get(getJumpTableEntryType(), Functions.size()); 1436 auto JumpTable = 1437 ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0)); 1438 1439 lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout); 1440 1441 // Build aliases pointing to offsets into the jump table, and replace 1442 // references to the original functions with references to the aliases. 1443 for (unsigned I = 0; I != Functions.size(); ++I) { 1444 Function *F = cast<Function>(Functions[I]->getGlobal()); 1445 bool IsDefinition = Functions[I]->isDefinition(); 1446 1447 Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast( 1448 ConstantExpr::getInBoundsGetElementPtr( 1449 JumpTableType, JumpTable, 1450 ArrayRef<Constant *>{ConstantInt::get(IntPtrTy, 0), 1451 ConstantInt::get(IntPtrTy, I)}), 1452 F->getType()); 1453 if (Functions[I]->isExported()) { 1454 if (IsDefinition) { 1455 ExportSummary->cfiFunctionDefs().insert(F->getName()); 1456 } else { 1457 GlobalAlias *JtAlias = GlobalAlias::create( 1458 F->getValueType(), 0, GlobalValue::ExternalLinkage, 1459 F->getName() + ".cfi_jt", CombinedGlobalElemPtr, &M); 1460 JtAlias->setVisibility(GlobalValue::HiddenVisibility); 1461 ExportSummary->cfiFunctionDecls().insert(F->getName()); 1462 } 1463 } 1464 if (!IsDefinition) { 1465 if (F->isWeakForLinker()) 1466 replaceWeakDeclarationWithJumpTablePtr(F, CombinedGlobalElemPtr, IsDefinition); 1467 else 1468 replaceCfiUses(F, CombinedGlobalElemPtr, IsDefinition); 1469 } else { 1470 assert(F->getType()->getAddressSpace() == 0); 1471 1472 GlobalAlias *FAlias = GlobalAlias::create( 1473 F->getValueType(), 0, F->getLinkage(), "", CombinedGlobalElemPtr, &M); 1474 FAlias->setVisibility(F->getVisibility()); 1475 FAlias->takeName(F); 1476 if (FAlias->hasName()) 1477 F->setName(FAlias->getName() + ".cfi"); 1478 replaceCfiUses(F, FAlias, IsDefinition); 1479 if (!F->hasLocalLinkage()) 1480 F->setVisibility(GlobalVariable::HiddenVisibility); 1481 } 1482 } 1483 1484 createJumpTable(JumpTableFn, Functions); 1485} 1486 1487/// Assign a dummy layout using an incrementing counter, tag each function 1488/// with its index represented as metadata, and lower each type test to an 1489/// integer range comparison. During generation of the indirect function call 1490/// table in the backend, it will assign the given indexes. 1491/// Note: Dynamic linking is not supported, as the WebAssembly ABI has not yet 1492/// been finalized. 1493void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM( 1494 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) { 1495 assert(!Functions.empty()); 1496 1497 // Build consecutive monotonic integer ranges for each call target set 1498 DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout; 1499 1500 for (GlobalTypeMember *GTM : Functions) { 1501 Function *F = cast<Function>(GTM->getGlobal()); 1502 1503 // Skip functions that are not address taken, to avoid bloating the table 1504 if (!F->hasAddressTaken()) 1505 continue; 1506 1507 // Store metadata with the index for each function 1508 MDNode *MD = MDNode::get(F->getContext(), 1509 ArrayRef<Metadata *>(ConstantAsMetadata::get( 1510 ConstantInt::get(Int64Ty, IndirectIndex)))); 1511 F->setMetadata("wasm.index", MD); 1512 1513 // Assign the counter value 1514 GlobalLayout[GTM] = IndirectIndex++; 1515 } 1516 1517 // The indirect function table index space starts at zero, so pass a NULL 1518 // pointer as the subtracted "jump table" offset. 1519 lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy), 1520 GlobalLayout); 1521} 1522 1523void LowerTypeTestsModule::buildBitSetsFromDisjointSet( 1524 ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals, 1525 ArrayRef<ICallBranchFunnel *> ICallBranchFunnels) { 1526 DenseMap<Metadata *, uint64_t> TypeIdIndices; 1527 for (unsigned I = 0; I != TypeIds.size(); ++I) 1528 TypeIdIndices[TypeIds[I]] = I; 1529 1530 // For each type identifier, build a set of indices that refer to members of 1531 // the type identifier. 1532 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size()); 1533 unsigned GlobalIndex = 0; 1534 DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices; 1535 for (GlobalTypeMember *GTM : Globals) { 1536 for (MDNode *Type : GTM->types()) { 1537 // Type = { offset, type identifier } 1538 auto I = TypeIdIndices.find(Type->getOperand(1)); 1539 if (I != TypeIdIndices.end()) 1540 TypeMembers[I->second].insert(GlobalIndex); 1541 } 1542 GlobalIndices[GTM] = GlobalIndex; 1543 GlobalIndex++; 1544 } 1545 1546 for (ICallBranchFunnel *JT : ICallBranchFunnels) { 1547 TypeMembers.emplace_back(); 1548 std::set<uint64_t> &TMSet = TypeMembers.back(); 1549 for (GlobalTypeMember *T : JT->targets()) 1550 TMSet.insert(GlobalIndices[T]); 1551 } 1552 1553 // Order the sets of indices by size. The GlobalLayoutBuilder works best 1554 // when given small index sets first. 1555 llvm::stable_sort(TypeMembers, [](const std::set<uint64_t> &O1, 1556 const std::set<uint64_t> &O2) { 1557 return O1.size() < O2.size(); 1558 }); 1559 1560 // Create a GlobalLayoutBuilder and provide it with index sets as layout 1561 // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as 1562 // close together as possible. 1563 GlobalLayoutBuilder GLB(Globals.size()); 1564 for (auto &&MemSet : TypeMembers) 1565 GLB.addFragment(MemSet); 1566 1567 // Build a vector of globals with the computed layout. 1568 bool IsGlobalSet = 1569 Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal()); 1570 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size()); 1571 auto OGTMI = OrderedGTMs.begin(); 1572 for (auto &&F : GLB.Fragments) { 1573 for (auto &&Offset : F) { 1574 if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal())) 1575 report_fatal_error("Type identifier may not contain both global " 1576 "variables and functions"); 1577 *OGTMI++ = Globals[Offset]; 1578 } 1579 } 1580 1581 // Build the bitsets from this disjoint set. 1582 if (IsGlobalSet) 1583 buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs); 1584 else 1585 buildBitSetsFromFunctions(TypeIds, OrderedGTMs); 1586} 1587 1588/// Lower all type tests in this module. 1589LowerTypeTestsModule::LowerTypeTestsModule( 1590 Module &M, ModuleSummaryIndex *ExportSummary, 1591 const ModuleSummaryIndex *ImportSummary) 1592 : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) { 1593 assert(!(ExportSummary && ImportSummary)); 1594 Triple TargetTriple(M.getTargetTriple()); 1595 Arch = TargetTriple.getArch(); 1596 OS = TargetTriple.getOS(); 1597 ObjectFormat = TargetTriple.getObjectFormat(); 1598} 1599 1600bool LowerTypeTestsModule::runForTesting(Module &M) { 1601 ModuleSummaryIndex Summary(/*HaveGVs=*/false); 1602 1603 // Handle the command-line summary arguments. This code is for testing 1604 // purposes only, so we handle errors directly. 1605 if (!ClReadSummary.empty()) { 1606 ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary + 1607 ": "); 1608 auto ReadSummaryFile = 1609 ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary))); 1610 1611 yaml::Input In(ReadSummaryFile->getBuffer()); 1612 In >> Summary; 1613 ExitOnErr(errorCodeToError(In.error())); 1614 } 1615 1616 bool Changed = 1617 LowerTypeTestsModule( 1618 M, ClSummaryAction == PassSummaryAction::Export ? &Summary : nullptr, 1619 ClSummaryAction == PassSummaryAction::Import ? &Summary : nullptr) 1620 .lower(); 1621 1622 if (!ClWriteSummary.empty()) { 1623 ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary + 1624 ": "); 1625 std::error_code EC; 1626 raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text); 1627 ExitOnErr(errorCodeToError(EC)); 1628 1629 yaml::Output Out(OS); 1630 Out << Summary; 1631 } 1632 1633 return Changed; 1634} 1635 1636static bool isDirectCall(Use& U) { 1637 auto *Usr = dyn_cast<CallInst>(U.getUser()); 1638 if (Usr) { 1639 CallSite CS(Usr); 1640 if (CS.isCallee(&U)) 1641 return true; 1642 } 1643 return false; 1644} 1645 1646void LowerTypeTestsModule::replaceCfiUses(Function *Old, Value *New, bool IsDefinition) { 1647 SmallSetVector<Constant *, 4> Constants; 1648 auto UI = Old->use_begin(), E = Old->use_end(); 1649 for (; UI != E;) { 1650 Use &U = *UI; 1651 ++UI; 1652 1653 // Skip block addresses 1654 if (isa<BlockAddress>(U.getUser())) 1655 continue; 1656 1657 // Skip direct calls to externally defined or non-dso_local functions 1658 if (isDirectCall(U) && (Old->isDSOLocal() || !IsDefinition)) 1659 continue; 1660 1661 // Must handle Constants specially, we cannot call replaceUsesOfWith on a 1662 // constant because they are uniqued. 1663 if (auto *C = dyn_cast<Constant>(U.getUser())) { 1664 if (!isa<GlobalValue>(C)) { 1665 // Save unique users to avoid processing operand replacement 1666 // more than once. 1667 Constants.insert(C); 1668 continue; 1669 } 1670 } 1671 1672 U.set(New); 1673 } 1674 1675 // Process operand replacement of saved constants. 1676 for (auto *C : Constants) 1677 C->handleOperandChange(Old, New); 1678} 1679 1680void LowerTypeTestsModule::replaceDirectCalls(Value *Old, Value *New) { 1681 auto UI = Old->use_begin(), E = Old->use_end(); 1682 for (; UI != E;) { 1683 Use &U = *UI; 1684 ++UI; 1685 1686 if (!isDirectCall(U)) 1687 continue; 1688 1689 U.set(New); 1690 } 1691} 1692 1693bool LowerTypeTestsModule::lower() { 1694 // If only some of the modules were split, we cannot correctly perform 1695 // this transformation. We already checked for the presense of type tests 1696 // with partially split modules during the thin link, and would have emitted 1697 // an error if any were found, so here we can simply return. 1698 if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) || 1699 (ImportSummary && ImportSummary->partiallySplitLTOUnits())) 1700 return false; 1701 1702 Function *TypeTestFunc = 1703 M.getFunction(Intrinsic::getName(Intrinsic::type_test)); 1704 Function *ICallBranchFunnelFunc = 1705 M.getFunction(Intrinsic::getName(Intrinsic::icall_branch_funnel)); 1706 if ((!TypeTestFunc || TypeTestFunc->use_empty()) && 1707 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->use_empty()) && 1708 !ExportSummary && !ImportSummary) 1709 return false; 1710 1711 if (ImportSummary) { 1712 if (TypeTestFunc) { 1713 for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end(); 1714 UI != UE;) { 1715 auto *CI = cast<CallInst>((*UI++).getUser()); 1716 importTypeTest(CI); 1717 } 1718 } 1719 1720 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->use_empty()) 1721 report_fatal_error( 1722 "unexpected call to llvm.icall.branch.funnel during import phase"); 1723 1724 SmallVector<Function *, 8> Defs; 1725 SmallVector<Function *, 8> Decls; 1726 for (auto &F : M) { 1727 // CFI functions are either external, or promoted. A local function may 1728 // have the same name, but it's not the one we are looking for. 1729 if (F.hasLocalLinkage()) 1730 continue; 1731 if (ImportSummary->cfiFunctionDefs().count(F.getName())) 1732 Defs.push_back(&F); 1733 else if (ImportSummary->cfiFunctionDecls().count(F.getName())) 1734 Decls.push_back(&F); 1735 } 1736 1737 for (auto F : Defs) 1738 importFunction(F, /*isDefinition*/ true); 1739 for (auto F : Decls) 1740 importFunction(F, /*isDefinition*/ false); 1741 1742 return true; 1743 } 1744 1745 // Equivalence class set containing type identifiers and the globals that 1746 // reference them. This is used to partition the set of type identifiers in 1747 // the module into disjoint sets. 1748 using GlobalClassesTy = EquivalenceClasses< 1749 PointerUnion3<GlobalTypeMember *, Metadata *, ICallBranchFunnel *>>; 1750 GlobalClassesTy GlobalClasses; 1751 1752 // Verify the type metadata and build a few data structures to let us 1753 // efficiently enumerate the type identifiers associated with a global: 1754 // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector 1755 // of associated type metadata) and a mapping from type identifiers to their 1756 // list of GlobalTypeMembers and last observed index in the list of globals. 1757 // The indices will be used later to deterministically order the list of type 1758 // identifiers. 1759 BumpPtrAllocator Alloc; 1760 struct TIInfo { 1761 unsigned UniqueId; 1762 std::vector<GlobalTypeMember *> RefGlobals; 1763 }; 1764 DenseMap<Metadata *, TIInfo> TypeIdInfo; 1765 unsigned CurUniqueId = 0; 1766 SmallVector<MDNode *, 2> Types; 1767 1768 // Cross-DSO CFI emits jumptable entries for exported functions as well as 1769 // address taken functions in case they are address taken in other modules. 1770 const bool CrossDsoCfi = M.getModuleFlag("Cross-DSO CFI") != nullptr; 1771 1772 struct ExportedFunctionInfo { 1773 CfiFunctionLinkage Linkage; 1774 MDNode *FuncMD; // {name, linkage, type[, type...]} 1775 }; 1776 DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions; 1777 if (ExportSummary) { 1778 // A set of all functions that are address taken by a live global object. 1779 DenseSet<GlobalValue::GUID> AddressTaken; 1780 for (auto &I : *ExportSummary) 1781 for (auto &GVS : I.second.SummaryList) 1782 if (GVS->isLive()) 1783 for (auto &Ref : GVS->refs()) 1784 AddressTaken.insert(Ref.getGUID()); 1785 1786 NamedMDNode *CfiFunctionsMD = M.getNamedMetadata("cfi.functions"); 1787 if (CfiFunctionsMD) { 1788 for (auto FuncMD : CfiFunctionsMD->operands()) { 1789 assert(FuncMD->getNumOperands() >= 2); 1790 StringRef FunctionName = 1791 cast<MDString>(FuncMD->getOperand(0))->getString(); 1792 CfiFunctionLinkage Linkage = static_cast<CfiFunctionLinkage>( 1793 cast<ConstantAsMetadata>(FuncMD->getOperand(1)) 1794 ->getValue() 1795 ->getUniqueInteger() 1796 .getZExtValue()); 1797 const GlobalValue::GUID GUID = GlobalValue::getGUID( 1798 GlobalValue::dropLLVMManglingEscape(FunctionName)); 1799 // Do not emit jumptable entries for functions that are not-live and 1800 // have no live references (and are not exported with cross-DSO CFI.) 1801 if (!ExportSummary->isGUIDLive(GUID)) 1802 continue; 1803 if (!AddressTaken.count(GUID)) { 1804 if (!CrossDsoCfi || Linkage != CFL_Definition) 1805 continue; 1806 1807 bool Exported = false; 1808 if (auto VI = ExportSummary->getValueInfo(GUID)) 1809 for (auto &GVS : VI.getSummaryList()) 1810 if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage())) 1811 Exported = true; 1812 1813 if (!Exported) 1814 continue; 1815 } 1816 auto P = ExportedFunctions.insert({FunctionName, {Linkage, FuncMD}}); 1817 if (!P.second && P.first->second.Linkage != CFL_Definition) 1818 P.first->second = {Linkage, FuncMD}; 1819 } 1820 1821 for (const auto &P : ExportedFunctions) { 1822 StringRef FunctionName = P.first; 1823 CfiFunctionLinkage Linkage = P.second.Linkage; 1824 MDNode *FuncMD = P.second.FuncMD; 1825 Function *F = M.getFunction(FunctionName); 1826 if (!F) 1827 F = Function::Create( 1828 FunctionType::get(Type::getVoidTy(M.getContext()), false), 1829 GlobalVariable::ExternalLinkage, 1830 M.getDataLayout().getProgramAddressSpace(), FunctionName, &M); 1831 1832 // If the function is available_externally, remove its definition so 1833 // that it is handled the same way as a declaration. Later we will try 1834 // to create an alias using this function's linkage, which will fail if 1835 // the linkage is available_externally. This will also result in us 1836 // following the code path below to replace the type metadata. 1837 if (F->hasAvailableExternallyLinkage()) { 1838 F->setLinkage(GlobalValue::ExternalLinkage); 1839 F->deleteBody(); 1840 F->setComdat(nullptr); 1841 F->clearMetadata(); 1842 } 1843 1844 // Update the linkage for extern_weak declarations when a definition 1845 // exists. 1846 if (Linkage == CFL_Definition && F->hasExternalWeakLinkage()) 1847 F->setLinkage(GlobalValue::ExternalLinkage); 1848 1849 // If the function in the full LTO module is a declaration, replace its 1850 // type metadata with the type metadata we found in cfi.functions. That 1851 // metadata is presumed to be more accurate than the metadata attached 1852 // to the declaration. 1853 if (F->isDeclaration()) { 1854 if (Linkage == CFL_WeakDeclaration) 1855 F->setLinkage(GlobalValue::ExternalWeakLinkage); 1856 1857 F->eraseMetadata(LLVMContext::MD_type); 1858 for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I) 1859 F->addMetadata(LLVMContext::MD_type, 1860 *cast<MDNode>(FuncMD->getOperand(I).get())); 1861 } 1862 } 1863 } 1864 } 1865 1866 DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers; 1867 for (GlobalObject &GO : M.global_objects()) { 1868 if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker()) 1869 continue; 1870 1871 Types.clear(); 1872 GO.getMetadata(LLVMContext::MD_type, Types); 1873 1874 bool IsDefinition = !GO.isDeclarationForLinker(); 1875 bool IsExported = false; 1876 if (Function *F = dyn_cast<Function>(&GO)) { 1877 if (ExportedFunctions.count(F->getName())) { 1878 IsDefinition |= ExportedFunctions[F->getName()].Linkage == CFL_Definition; 1879 IsExported = true; 1880 // TODO: The logic here checks only that the function is address taken, 1881 // not that the address takers are live. This can be updated to check 1882 // their liveness and emit fewer jumptable entries once monolithic LTO 1883 // builds also emit summaries. 1884 } else if (!F->hasAddressTaken()) { 1885 if (!CrossDsoCfi || !IsDefinition || F->hasLocalLinkage()) 1886 continue; 1887 } 1888 } 1889 1890 auto *GTM = 1891 GlobalTypeMember::create(Alloc, &GO, IsDefinition, IsExported, Types); 1892 GlobalTypeMembers[&GO] = GTM; 1893 for (MDNode *Type : Types) { 1894 verifyTypeMDNode(&GO, Type); 1895 auto &Info = TypeIdInfo[Type->getOperand(1)]; 1896 Info.UniqueId = ++CurUniqueId; 1897 Info.RefGlobals.push_back(GTM); 1898 } 1899 } 1900 1901 auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & { 1902 // Add the call site to the list of call sites for this type identifier. We 1903 // also use TypeIdUsers to keep track of whether we have seen this type 1904 // identifier before. If we have, we don't need to re-add the referenced 1905 // globals to the equivalence class. 1906 auto Ins = TypeIdUsers.insert({TypeId, {}}); 1907 if (Ins.second) { 1908 // Add the type identifier to the equivalence class. 1909 GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId); 1910 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); 1911 1912 // Add the referenced globals to the type identifier's equivalence class. 1913 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals) 1914 CurSet = GlobalClasses.unionSets( 1915 CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM))); 1916 } 1917 1918 return Ins.first->second; 1919 }; 1920 1921 if (TypeTestFunc) { 1922 for (const Use &U : TypeTestFunc->uses()) { 1923 auto CI = cast<CallInst>(U.getUser()); 1924 1925 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1)); 1926 if (!TypeIdMDVal) 1927 report_fatal_error("Second argument of llvm.type.test must be metadata"); 1928 auto TypeId = TypeIdMDVal->getMetadata(); 1929 AddTypeIdUse(TypeId).CallSites.push_back(CI); 1930 } 1931 } 1932 1933 if (ICallBranchFunnelFunc) { 1934 for (const Use &U : ICallBranchFunnelFunc->uses()) { 1935 if (Arch != Triple::x86_64) 1936 report_fatal_error( 1937 "llvm.icall.branch.funnel not supported on this target"); 1938 1939 auto CI = cast<CallInst>(U.getUser()); 1940 1941 std::vector<GlobalTypeMember *> Targets; 1942 if (CI->getNumArgOperands() % 2 != 1) 1943 report_fatal_error("number of arguments should be odd"); 1944 1945 GlobalClassesTy::member_iterator CurSet; 1946 for (unsigned I = 1; I != CI->getNumArgOperands(); I += 2) { 1947 int64_t Offset; 1948 auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset( 1949 CI->getOperand(I), Offset, M.getDataLayout())); 1950 if (!Base) 1951 report_fatal_error( 1952 "Expected branch funnel operand to be global value"); 1953 1954 GlobalTypeMember *GTM = GlobalTypeMembers[Base]; 1955 Targets.push_back(GTM); 1956 GlobalClassesTy::member_iterator NewSet = 1957 GlobalClasses.findLeader(GlobalClasses.insert(GTM)); 1958 if (I == 1) 1959 CurSet = NewSet; 1960 else 1961 CurSet = GlobalClasses.unionSets(CurSet, NewSet); 1962 } 1963 1964 GlobalClasses.unionSets( 1965 CurSet, GlobalClasses.findLeader( 1966 GlobalClasses.insert(ICallBranchFunnel::create( 1967 Alloc, CI, Targets, ++CurUniqueId)))); 1968 } 1969 } 1970 1971 if (ExportSummary) { 1972 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID; 1973 for (auto &P : TypeIdInfo) { 1974 if (auto *TypeId = dyn_cast<MDString>(P.first)) 1975 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back( 1976 TypeId); 1977 } 1978 1979 for (auto &P : *ExportSummary) { 1980 for (auto &S : P.second.SummaryList) { 1981 if (!ExportSummary->isGlobalValueLive(S.get())) 1982 continue; 1983 if (auto *FS = dyn_cast<FunctionSummary>(S->getBaseObject())) 1984 for (GlobalValue::GUID G : FS->type_tests()) 1985 for (Metadata *MD : MetadataByGUID[G]) 1986 AddTypeIdUse(MD).IsExported = true; 1987 } 1988 } 1989 } 1990 1991 if (GlobalClasses.empty()) 1992 return false; 1993 1994 // Build a list of disjoint sets ordered by their maximum global index for 1995 // determinism. 1996 std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets; 1997 for (GlobalClassesTy::iterator I = GlobalClasses.begin(), 1998 E = GlobalClasses.end(); 1999 I != E; ++I) { 2000 if (!I->isLeader()) 2001 continue; 2002 ++NumTypeIdDisjointSets; 2003 2004 unsigned MaxUniqueId = 0; 2005 for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); 2006 MI != GlobalClasses.member_end(); ++MI) { 2007 if (auto *MD = MI->dyn_cast<Metadata *>()) 2008 MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId); 2009 else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>()) 2010 MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId); 2011 } 2012 Sets.emplace_back(I, MaxUniqueId); 2013 } 2014 llvm::sort(Sets, 2015 [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1, 2016 const std::pair<GlobalClassesTy::iterator, unsigned> &S2) { 2017 return S1.second < S2.second; 2018 }); 2019 2020 // For each disjoint set we found... 2021 for (const auto &S : Sets) { 2022 // Build the list of type identifiers in this disjoint set. 2023 std::vector<Metadata *> TypeIds; 2024 std::vector<GlobalTypeMember *> Globals; 2025 std::vector<ICallBranchFunnel *> ICallBranchFunnels; 2026 for (GlobalClassesTy::member_iterator MI = 2027 GlobalClasses.member_begin(S.first); 2028 MI != GlobalClasses.member_end(); ++MI) { 2029 if (MI->is<Metadata *>()) 2030 TypeIds.push_back(MI->get<Metadata *>()); 2031 else if (MI->is<GlobalTypeMember *>()) 2032 Globals.push_back(MI->get<GlobalTypeMember *>()); 2033 else 2034 ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>()); 2035 } 2036 2037 // Order type identifiers by unique ID for determinism. This ordering is 2038 // stable as there is a one-to-one mapping between metadata and unique IDs. 2039 llvm::sort(TypeIds, [&](Metadata *M1, Metadata *M2) { 2040 return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId; 2041 }); 2042 2043 // Same for the branch funnels. 2044 llvm::sort(ICallBranchFunnels, 2045 [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) { 2046 return F1->UniqueId < F2->UniqueId; 2047 }); 2048 2049 // Build bitsets for this disjoint set. 2050 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels); 2051 } 2052 2053 allocateByteArrays(); 2054 2055 // Parse alias data to replace stand-in function declarations for aliases 2056 // with an alias to the intended target. 2057 if (ExportSummary) { 2058 if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) { 2059 for (auto AliasMD : AliasesMD->operands()) { 2060 assert(AliasMD->getNumOperands() >= 4); 2061 StringRef AliasName = 2062 cast<MDString>(AliasMD->getOperand(0))->getString(); 2063 StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString(); 2064 2065 if (!ExportedFunctions.count(Aliasee) || 2066 ExportedFunctions[Aliasee].Linkage != CFL_Definition || 2067 !M.getNamedAlias(Aliasee)) 2068 continue; 2069 2070 GlobalValue::VisibilityTypes Visibility = 2071 static_cast<GlobalValue::VisibilityTypes>( 2072 cast<ConstantAsMetadata>(AliasMD->getOperand(2)) 2073 ->getValue() 2074 ->getUniqueInteger() 2075 .getZExtValue()); 2076 bool Weak = 2077 static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3)) 2078 ->getValue() 2079 ->getUniqueInteger() 2080 .getZExtValue()); 2081 2082 auto *Alias = GlobalAlias::create("", M.getNamedAlias(Aliasee)); 2083 Alias->setVisibility(Visibility); 2084 if (Weak) 2085 Alias->setLinkage(GlobalValue::WeakAnyLinkage); 2086 2087 if (auto *F = M.getFunction(AliasName)) { 2088 Alias->takeName(F); 2089 F->replaceAllUsesWith(Alias); 2090 F->eraseFromParent(); 2091 } else { 2092 Alias->setName(AliasName); 2093 } 2094 } 2095 } 2096 } 2097 2098 // Emit .symver directives for exported functions, if they exist. 2099 if (ExportSummary) { 2100 if (NamedMDNode *SymversMD = M.getNamedMetadata("symvers")) { 2101 for (auto Symver : SymversMD->operands()) { 2102 assert(Symver->getNumOperands() >= 2); 2103 StringRef SymbolName = 2104 cast<MDString>(Symver->getOperand(0))->getString(); 2105 StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString(); 2106 2107 if (!ExportedFunctions.count(SymbolName)) 2108 continue; 2109 2110 M.appendModuleInlineAsm( 2111 (llvm::Twine(".symver ") + SymbolName + ", " + Alias).str()); 2112 } 2113 } 2114 } 2115 2116 return true; 2117} 2118 2119PreservedAnalyses LowerTypeTestsPass::run(Module &M, 2120 ModuleAnalysisManager &AM) { 2121 bool Changed = LowerTypeTestsModule(M, ExportSummary, ImportSummary).lower(); 2122 if (!Changed) 2123 return PreservedAnalyses::all(); 2124 return PreservedAnalyses::none(); 2125} 2126