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