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