81 #include <system_error>
86 using namespace lowertypetests;
88 #define DEBUG_TYPE "lowertypetests"
90 STATISTIC(ByteArraySizeBits,
"Byte array size in bits");
91 STATISTIC(ByteArraySizeBytes,
"Byte array size in bytes");
92 STATISTIC(NumByteArraysCreated,
"Number of byte arrays created");
93 STATISTIC(NumTypeTestCallsLowered,
"Number of type test calls lowered");
94 STATISTIC(NumTypeIdDisjointSets,
"Number of disjoint sets of type identifiers");
97 "lowertypetests-avoid-reuse",
98 cl::desc(
"Try to avoid reuse of byte array addresses using aliases"),
102 "lowertypetests-summary-action",
103 cl::desc(
"What to do with the summary when running this pass"),
106 "Import typeid resolutions from summary and globals"),
108 "Export typeid resolutions to summary and globals")),
112 "lowertypetests-read-summary",
113 cl::desc(
"Read summary from given YAML file before running pass"),
117 "lowertypetests-write-summary",
118 cl::desc(
"Write summary to given YAML file after running pass"),
123 cl::desc(
"Simply drop type test assume sequences"),
137 return Bits.count(BitOffset);
182 BSI.
Bits.insert(Offset);
191 std::vector<uint64_t> &Fragment =
Fragments.back();
194 for (
auto ObjIndex :
F) {
196 if (OldFragmentIndex == 0) {
199 Fragment.push_back(ObjIndex);
206 std::vector<uint64_t> &OldFragment =
Fragments[OldFragmentIndex];
219 uint8_t &AllocMask) {
229 unsigned ReqSize = AllocByteOffset + BitSize;
231 if (
Bytes.size() < ReqSize)
232 Bytes.resize(ReqSize);
235 AllocMask = 1 <<
Bit;
237 Bytes[AllocByteOffset +
B] |= AllocMask;
241 if (
F->isDeclarationForLinker())
243 auto *CI = mdconst::extract_or_null<ConstantInt>(
244 F->getParent()->getModuleFlag(
"CFI Canonical Jump Tables"));
245 if (!CI || CI->getZExtValue() != 0)
247 return F->hasFnAttribute(
"cfi-canonical-jump-table");
252 struct ByteArrayInfo {
253 std::set<uint64_t>
Bits;
257 uint8_t *MaskPtr =
nullptr;
265 class GlobalTypeMember final :
TrailingObjects<GlobalTypeMember, MDNode *> {
276 bool IsJumpTableCanonical;
282 size_t numTrailingObjects(OverloadToken<MDNode *>)
const {
return NTypes; }
286 bool IsJumpTableCanonical,
bool IsExported,
288 auto *GTM =
static_cast<GlobalTypeMember *
>(Alloc.
Allocate(
289 totalSizeToAlloc<MDNode *>(Types.
size()),
alignof(GlobalTypeMember)));
291 GTM->NTypes = Types.
size();
292 GTM->IsJumpTableCanonical = IsJumpTableCanonical;
293 GTM->IsExported = IsExported;
294 std::uninitialized_copy(Types.
begin(), Types.
end(),
295 GTM->getTrailingObjects<
MDNode *>());
304 return IsJumpTableCanonical;
307 bool isExported()
const {
312 return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
316 struct ICallBranchFunnel final
321 auto *
Call =
static_cast<ICallBranchFunnel *
>(
322 Alloc.
Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.
size()),
323 alignof(ICallBranchFunnel)));
325 Call->UniqueId = UniqueId;
327 std::uninitialized_copy(Targets.
begin(), Targets.
end(),
328 Call->getTrailingObjects<GlobalTypeMember *>());
334 return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
343 struct ScopedSaveAliaseesAndUsed {
346 std::vector<std::pair<GlobalAlias *, Function *>> FunctionAliases;
347 std::vector<std::pair<GlobalIFunc *, Function *>> ResolverIFuncs;
349 ScopedSaveAliaseesAndUsed(
Module &M) :
M(
M) {
363 GV->eraseFromParent();
365 GV->eraseFromParent();
367 for (
auto &GA :
M.aliases()) {
370 if (
auto *
F = dyn_cast<Function>(GA.getAliasee()->stripPointerCasts()))
371 FunctionAliases.push_back({&GA,
F});
374 for (
auto &GI :
M.ifuncs())
375 if (
auto *
F = dyn_cast<Function>(GI.getResolver()->stripPointerCasts()))
376 ResolverIFuncs.push_back({&GI,
F});
379 ~ScopedSaveAliaseesAndUsed() {
383 for (
auto P : FunctionAliases)
387 for (
auto P : ResolverIFuncs) {
391 P.first->setResolver(
P.second);
396 class LowerTypeTestsModule {
416 IntegerType *IntPtrTy =
M.getDataLayout().getIntPtrType(
M.getContext(), 0);
424 struct TypeIdUserInfo {
425 std::vector<CallInst *> CallSites;
426 bool IsExported =
false;
434 struct TypeIdLowering {
458 std::vector<ByteArrayInfo> ByteArrayInfos;
460 Function *WeakInitializerFn =
nullptr;
462 bool shouldExportConstantsAsAbsoluteSymbols();
463 uint8_t *exportTypeId(
StringRef TypeId,
const TypeIdLowering &TIL);
464 TypeIdLowering importTypeId(
StringRef TypeId);
467 std::vector<GlobalAlias *> &AliasesToErase);
472 ByteArrayInfo *createByteArray(
BitSetInfo &BSI);
473 void allocateByteArrays();
476 void lowerTypeTestCalls(
480 const TypeIdLowering &TIL);
484 unsigned getJumpTableEntrySize();
485 Type *getJumpTableEntryType();
502 bool IsJumpTableCanonical);
504 void findGlobalVariableUsersOf(
Constant *
C,
514 void replaceCfiUses(
Function *Old,
Value *New,
bool IsJumpTableCanonical);
518 void replaceDirectCalls(
Value *Old,
Value *New);
529 static bool runForTesting(
Module &M);
535 bool UseCommandLine =
false;
548 ImportSummary(ImportSummary),
553 bool runOnModule(
Module &M)
override {
555 return LowerTypeTestsModule::runForTesting(M);
556 return LowerTypeTestsModule(M, ExportSummary, ImportSummary, DropTypeTests)
571 bool DropTypeTests) {
572 return new LowerTypeTests(ExportSummary, ImportSummary, DropTypeTests);
584 for (
auto &GlobalAndOffset : GlobalLayout) {
585 for (
MDNode *
Type : GlobalAndOffset.first->types()) {
586 if (
Type->getOperand(1) != TypeId)
590 cast<ConstantAsMetadata>(
Type->getOperand(0))->getValue())
592 BSB.
addOffset(GlobalAndOffset.second + Offset);
603 auto BitsType = cast<IntegerType>(
Bits->getType());
604 unsigned BitWidth = BitsType->getBitWidth();
606 BitOffset =
B.CreateZExtOrTrunc(BitOffset, BitsType);
610 Value *MaskedBits =
B.CreateAnd(
Bits, BitMask);
614 ByteArrayInfo *LowerTypeTestsModule::createByteArray(
BitSetInfo &BSI) {
623 ByteArrayInfos.emplace_back();
624 ByteArrayInfo *BAI = &ByteArrayInfos.back();
626 BAI->Bits = BSI.
Bits;
628 BAI->ByteArray = ByteArrayGlobal;
629 BAI->MaskGlobal = MaskGlobal;
633 void LowerTypeTestsModule::allocateByteArrays() {
635 [](
const ByteArrayInfo &BAI1,
const ByteArrayInfo &BAI2) {
636 return BAI1.BitSize > BAI2.BitSize;
639 std::vector<uint64_t> ByteArrayOffsets(ByteArrayInfos.size());
642 for (
unsigned I = 0;
I != ByteArrayInfos.size(); ++
I) {
643 ByteArrayInfo *BAI = &ByteArrayInfos[
I];
646 BAB.
allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[
I],
Mask);
648 BAI->MaskGlobal->replaceAllUsesWith(
650 BAI->MaskGlobal->eraseFromParent();
652 *BAI->MaskPtr =
Mask;
660 for (
unsigned I = 0;
I != ByteArrayInfos.size(); ++
I) {
661 ByteArrayInfo *BAI = &ByteArrayInfos[
I];
666 ByteArrayConst->
getType(), ByteArray, Idxs);
673 BAI->ByteArray->replaceAllUsesWith(Alias);
674 BAI->ByteArray->eraseFromParent();
680 ByteArraySizeBytes = BAB.
Bytes.size();
686 const TypeIdLowering &TIL,
693 Constant *ByteArray = TIL.TheByteArray;
700 "bits_use", ByteArray, &M);
703 Value *ByteAddr =
B.CreateGEP(Int8Ty, ByteArray, BitOffset);
714 if (
auto GV = dyn_cast<GlobalObject>(V)) {
716 GV->getMetadata(LLVMContext::MD_type, Types);
718 if (
Type->getOperand(1) != TypeId)
722 cast<ConstantAsMetadata>(
Type->getOperand(0))->getValue())
724 if (COffset == Offset)
730 if (
auto GEP = dyn_cast<GEPOperator>(V)) {
731 APInt APOffset(
DL.getPointerSizeInBits(0), 0);
732 bool Result =
GEP->accumulateConstantOffset(
DL, APOffset);
739 if (
auto Op = dyn_cast<Operator>(V)) {
740 if (
Op->getOpcode() == Instruction::BitCast)
754 const TypeIdLowering &TIL) {
770 Value *PtrAsInt =
B.CreatePtrToInt(Ptr, IntPtrTy);
775 return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt);
777 Value *PtrOffset =
B.CreateSub(PtrAsInt, OffsetedGlobalAsInt);
789 Value *OffsetSHL =
B.CreateShl(
795 Value *BitOffset =
B.CreateOr(OffsetSHR, OffsetSHL);
797 Value *OffsetInRange =
B.CreateICmpULE(BitOffset, TIL.SizeM1);
801 return OffsetInRange;
808 if (
auto *Br = dyn_cast<BranchInst>(*CI->
user_begin()))
814 Br->getMetadata(LLVMContext::MD_prof));
818 for (
auto &Phi :
Else->phis())
819 Phi.addIncoming(Phi.getIncomingValueForBlock(
Then), InitialBB);
822 return createBitSetTest(ThenB, TIL, BitOffset);
829 Value *
Bit = createBitSetTest(ThenB, TIL, BitOffset);
834 B.SetInsertPoint(CI);
837 P->addIncoming(
Bit, ThenB.GetInsertBlock());
843 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
850 std::vector<Constant *> GlobalInits;
856 for (GlobalTypeMember *
G : Globals) {
857 auto *GV = cast<GlobalVariable>(
G->getGlobal());
859 DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getValueType());
860 MaxAlign =
std::max(MaxAlign, Alignment);
862 GlobalLayout[
G] = GVOffset;
865 GlobalInits.push_back(
869 GlobalInits.push_back(GV->getInitializer());
870 uint64_t InitSize =
DL.getTypeAllocSize(GV->getValueType());
871 CurOffset = GVOffset + InitSize;
880 if (DesiredPadding > 32)
881 DesiredPadding =
alignTo(InitSize, 32) - InitSize;
885 auto *CombinedGlobal =
888 CombinedGlobal->setAlignment(MaxAlign);
891 lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
896 for (
unsigned I = 0;
I != Globals.size(); ++
I) {
903 NewInit->
getType(), CombinedGlobal, CombinedGlobalIdxs);
907 "", CombinedGlobalElemPtr, &M);
915 bool LowerTypeTestsModule::shouldExportConstantsAsAbsoluteSymbols() {
928 uint8_t *LowerTypeTestsModule::exportTypeId(
StringRef TypeId,
929 const TypeIdLowering &TIL) {
937 "__typeid_" + TypeId +
"_" +
Name,
C, &M);
942 if (shouldExportConstantsAsAbsoluteSymbols())
945 Storage = cast<ConstantInt>(
C)->getZExtValue();
949 ExportGlobal(
"global_addr", TIL.OffsetedGlobal);
954 ExportConstant(
"align", TTRes.
AlignLog2, TIL.AlignLog2);
955 ExportConstant(
"size_m1", TTRes.
SizeM1, TIL.SizeM1);
957 uint64_t BitSize = cast<ConstantInt>(TIL.SizeM1)->getZExtValue() + 1;
965 ExportGlobal(
"byte_array", TIL.TheByteArray);
966 if (shouldExportConstantsAsAbsoluteSymbols())
967 ExportGlobal(
"bit_mask", TIL.BitMask);
973 ExportConstant(
"inline_bits", TTRes.
InlineBits, TIL.InlineBits);
978 LowerTypeTestsModule::TypeIdLowering
979 LowerTypeTestsModule::importTypeId(
StringRef TypeId) {
991 Constant *
C =
M.getOrInsertGlobal((
"__typeid_" + TypeId +
"_" +
Name).str(),
993 if (
auto *GV = dyn_cast<GlobalVariable>(
C))
1001 if (!shouldExportConstantsAsAbsoluteSymbols()) {
1004 if (!isa<IntegerType>(Ty))
1010 auto *GV = cast<GlobalVariable>(
C->stripPointerCasts());
1011 if (isa<IntegerType>(Ty))
1013 if (GV->
getMetadata(LLVMContext::MD_absolute_symbol))
1023 SetAbsRange(~0ull, ~0ull);
1025 SetAbsRange(0, 1ull << AbsWidth);
1030 TIL.OffsetedGlobal = ImportGlobal(
"global_addr");
1035 TIL.AlignLog2 = ImportConstant(
"align", TTRes.
AlignLog2, 8, Int8Ty);
1041 TIL.TheByteArray = ImportGlobal(
"byte_array");
1042 TIL.BitMask = ImportConstant(
"bit_mask", TTRes.
BitMask, 8, Int8PtrTy);
1046 TIL.InlineBits = ImportConstant(
1053 void LowerTypeTestsModule::importTypeTest(
CallInst *CI) {
1054 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->
getArgOperand(1));
1058 auto TypeIdStr = dyn_cast<MDString>(TypeIdMDVal->getMetadata());
1065 TypeIdLowering TIL = importTypeId(TypeIdStr->getString());
1066 Value *Lowered = lowerTypeTestCall(TypeIdStr, CI, TIL);
1075 void LowerTypeTestsModule::importFunction(
1077 std::vector<GlobalAlias *> &AliasesToErase) {
1078 assert(
F->getType()->getAddressSpace() == 0);
1081 std::string
Name = std::string(
F->getName());
1086 if (
F->isDSOLocal()) {
1089 F->getAddressSpace(),
1092 replaceDirectCalls(
F, RealF);
1102 F->getAddressSpace(),
Name +
".cfi_jt", &M);
1105 F->setName(
Name +
".cfi");
1108 F->getAddressSpace(),
Name, &M);
1115 for (
auto &U :
F->uses()) {
1116 if (
auto *A = dyn_cast<GlobalAlias>(U.getUser())) {
1119 F->getAddressSpace(),
"", &M);
1121 A->replaceAllUsesWith(AliasDecl);
1122 AliasesToErase.push_back(A);
1127 if (
F->hasExternalWeakLinkage())
1134 F->setVisibility(Visibility);
1137 void LowerTypeTestsModule::lowerTypeTestCalls(
1145 BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout);
1147 if (
auto MDS = dyn_cast<MDString>(TypeId))
1148 dbgs() << MDS->getString() <<
": ";
1150 dbgs() <<
"<unnamed>: ";
1154 ByteArrayInfo *BAI =
nullptr;
1163 }
else if (BSI.
BitSize <= 64) {
1168 if (InlineBits == 0)
1175 ++NumByteArraysCreated;
1176 BAI = createByteArray(BSI);
1177 TIL.TheByteArray = BAI->ByteArray;
1178 TIL.BitMask = BAI->MaskGlobal;
1181 TypeIdUserInfo &TIUI = TypeIdUsers[TypeId];
1183 if (TIUI.IsExported) {
1184 uint8_t *MaskPtr = exportTypeId(cast<MDString>(TypeId)->getString(), TIL);
1186 BAI->MaskPtr = MaskPtr;
1190 for (
CallInst *CI : TIUI.CallSites) {
1191 ++NumTypeTestCallsLowered;
1192 Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
1202 if (
Type->getNumOperands() != 2)
1207 if (isa<GlobalVariable>(GO) && GO->
hasSection())
1209 "A member of a type identifier may not have an explicit section");
1215 auto OffsetConstMD = dyn_cast<ConstantAsMetadata>(
Type->getOperand(0));
1218 auto OffsetInt = dyn_cast<ConstantInt>(OffsetConstMD->getValue());
1228 unsigned LowerTypeTestsModule::getJumpTableEntrySize() {
1237 if (
const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1238 M.getModuleFlag(
"branch-target-enforcement")))
1239 if (BTE->getZExtValue())
1253 void LowerTypeTestsModule::createJumpTableEntry(
1257 unsigned ArgIndex = AsmArgs.size();
1260 AsmOS <<
"jmp ${" << ArgIndex <<
":c}@plt\n";
1261 AsmOS <<
"int3\nint3\nint3\n";
1263 AsmOS <<
"b $" << ArgIndex <<
"\n";
1265 if (
const auto *BTE = mdconst::extract_or_null<ConstantInt>(
1267 if (BTE->getZExtValue())
1269 AsmOS <<
"b $" << ArgIndex <<
"\n";
1271 AsmOS <<
"b.w $" << ArgIndex <<
"\n";
1274 AsmOS <<
"tail $" << ArgIndex <<
"@plt\n";
1279 ConstraintOS << (ArgIndex > 0 ?
",s" :
"s");
1280 AsmArgs.push_back(Dest);
1283 Type *LowerTypeTestsModule::getJumpTableEntryType() {
1289 void LowerTypeTestsModule::buildBitSetsFromFunctions(
1294 buildBitSetsFromFunctionsNative(TypeIds, Functions);
1296 buildBitSetsFromFunctionsWASM(TypeIds, Functions);
1301 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
1303 if (WeakInitializerFn ==
nullptr) {
1308 M.getDataLayout().getProgramAddressSpace(),
1309 "__cfi_global_var_init", &M);
1313 WeakInitializerFn->setSection(
1315 ?
"__TEXT,__StaticInit,regular,pure_instructions"
1322 IRBuilder<> IRB(WeakInitializerFn->getEntryBlock().getTerminator());
1328 void LowerTypeTestsModule::findGlobalVariableUsersOf(
1330 for (
auto *U :
C->users()){
1331 if (
auto *GV = dyn_cast<GlobalVariable>(U))
1333 else if (
auto *C2 = dyn_cast<Constant>(U))
1334 findGlobalVariableUsersOf(C2, Out);
1339 void LowerTypeTestsModule::replaceWeakDeclarationWithJumpTablePtr(
1344 findGlobalVariableUsersOf(
F, GlobalVarUsers);
1345 for (
auto GV : GlobalVarUsers)
1346 moveInitializerToModuleConstructor(GV);
1353 F->getAddressSpace(),
"", &M);
1354 replaceCfiUses(
F, PlaceholderFn, IsJumpTableCanonical);
1365 Attribute TFAttr =
F->getFnAttribute(
"target-features");
1370 if (Feature ==
"-thumb-mode")
1372 else if (Feature ==
"+thumb-mode")
1389 unsigned ArmCount = 0, ThumbCount = 0;
1390 for (
const auto GTM : Functions) {
1391 if (!GTM->isJumpTableCanonical()) {
1398 Function *
F = cast<Function>(GTM->getGlobal());
1405 void LowerTypeTestsModule::createJumpTable(
1407 std::string AsmStr, ConstraintStr;
1414 for (
unsigned I = 0;
I != Functions.
size(); ++
I)
1415 createJumpTableEntry(AsmOS, ConstraintOS, JumpTableArch, AsmArgs,
1416 cast<Function>(Functions[
I]->getGlobal()));
1419 F->setAlignment(
Align(getJumpTableEntrySize()));
1425 F->addFnAttr(Attribute::Naked);
1427 F->addFnAttr(
"target-features",
"-thumb-mode");
1429 F->addFnAttr(
"target-features",
"+thumb-mode");
1432 F->addFnAttr(
"target-cpu",
"cortex-a8");
1435 F->addFnAttr(
"branch-target-enforcement",
"false");
1436 F->addFnAttr(
"sign-return-address",
"none");
1441 F->addFnAttr(
"target-features",
"-c,-relax");
1444 F->addFnAttr(Attribute::NoUnwind);
1450 ArgTypes.
reserve(AsmArgs.size());
1451 for (
const auto &
Arg : AsmArgs)
1452 ArgTypes.push_back(
Arg->getType());
1455 AsmOS.str(), ConstraintOS.str(),
1458 IRB.CreateCall(JumpTableAsm, AsmArgs);
1459 IRB.CreateUnreachable();
1464 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
1546 unsigned EntrySize = getJumpTableEntrySize();
1547 for (
unsigned I = 0;
I != Functions.
size(); ++
I)
1548 GlobalLayout[Functions[
I]] =
I * EntrySize;
1554 M.getDataLayout().getProgramAddressSpace(),
1555 ".cfi.jumptable", &M);
1561 lowerTypeTestCalls(TypeIds,
JumpTable, GlobalLayout);
1564 ScopedSaveAliaseesAndUsed
S(M);
1568 for (
unsigned I = 0;
I != Functions.
size(); ++
I) {
1569 Function *
F = cast<Function>(Functions[
I]->getGlobal());
1570 bool IsJumpTableCanonical = Functions[
I]->isJumpTableCanonical();
1579 const bool IsExported = Functions[
I]->isExported();
1580 if (!IsJumpTableCanonical) {
1585 F->getName() +
".cfi_jt",
1586 CombinedGlobalElemPtr, &M);
1594 if (IsJumpTableCanonical)
1600 if (!IsJumpTableCanonical) {
1601 if (
F->hasExternalWeakLinkage())
1602 replaceWeakDeclarationWithJumpTablePtr(
F, CombinedGlobalElemPtr,
1603 IsJumpTableCanonical);
1605 replaceCfiUses(
F, CombinedGlobalElemPtr, IsJumpTableCanonical);
1607 assert(
F->getType()->getAddressSpace() == 0);
1611 CombinedGlobalElemPtr, &M);
1615 F->setName(FAlias->
getName() +
".cfi");
1616 replaceCfiUses(
F, FAlias, IsJumpTableCanonical);
1617 if (!
F->hasLocalLinkage())
1623 createJumpTable(JumpTableFn, Functions);
1632 void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
1639 for (GlobalTypeMember *GTM : Functions) {
1640 Function *
F = cast<Function>(GTM->getGlobal());
1643 if (!
F->hasAddressTaken())
1650 F->setMetadata(
"wasm.index", MD);
1653 GlobalLayout[GTM] = IndirectIndex++;
1662 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
1666 for (
unsigned I = 0;
I != TypeIds.
size(); ++
I)
1667 TypeIdIndices[TypeIds[
I]] =
I;
1671 std::vector<std::set<uint64_t>> TypeMembers(TypeIds.
size());
1672 unsigned GlobalIndex = 0;
1674 for (GlobalTypeMember *GTM : Globals) {
1677 auto I = TypeIdIndices.
find(
Type->getOperand(1));
1678 if (
I != TypeIdIndices.
end())
1679 TypeMembers[
I->second].insert(GlobalIndex);
1681 GlobalIndices[GTM] = GlobalIndex;
1685 for (ICallBranchFunnel *
JT : ICallBranchFunnels) {
1686 TypeMembers.emplace_back();
1687 std::set<uint64_t> &TMSet = TypeMembers.back();
1688 for (GlobalTypeMember *
T :
JT->targets())
1689 TMSet.
insert(GlobalIndices[
T]);
1695 const std::set<uint64_t> &O2) {
1696 return O1.size() < O2.size();
1703 for (
auto &&MemSet : TypeMembers)
1704 GLB.addFragment(MemSet);
1708 Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal());
1709 std::vector<GlobalTypeMember *> OrderedGTMs(Globals.size());
1710 auto OGTMI = OrderedGTMs.begin();
1711 for (
auto &&
F : GLB.Fragments) {
1712 for (
auto &&Offset :
F) {
1713 if (IsGlobalSet != isa<GlobalVariable>(Globals[Offset]->getGlobal()))
1715 "variables and functions");
1716 *OGTMI++ = Globals[
Offset];
1722 buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
1724 buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
1728 LowerTypeTestsModule::LowerTypeTestsModule(
1731 :
M(
M), ExportSummary(ExportSummary), ImportSummary(ImportSummary),
1733 assert(!(ExportSummary && ImportSummary));
1734 Triple TargetTriple(
M.getTargetTriple());
1735 Arch = TargetTriple.getArch();
1736 OS = TargetTriple.getOS();
1737 ObjectFormat = TargetTriple.getObjectFormat();
1740 bool LowerTypeTestsModule::runForTesting(
Module &
M) {
1748 auto ReadSummaryFile =
1751 yaml::Input
In(ReadSummaryFile->getBuffer());
1757 LowerTypeTestsModule(
1770 yaml::Output Out(OS);
1778 auto *Usr = dyn_cast<CallInst>(U.
getUser());
1780 auto *CB = dyn_cast<CallBase>(Usr);
1781 if (CB && CB->isCallee(&U))
1787 void LowerTypeTestsModule::replaceCfiUses(
Function *Old,
Value *New,
1788 bool IsJumpTableCanonical) {
1793 if (isa<BlockAddress, NoCFIValue>(U.getUser()))
1802 if (
auto *
C = dyn_cast<Constant>(U.getUser())) {
1803 if (!isa<GlobalValue>(
C)) {
1816 C->handleOperandChange(Old, New);
1819 void LowerTypeTestsModule::replaceDirectCalls(
Value *Old,
Value *New) {
1823 bool LowerTypeTestsModule::lower() {
1827 if (DropTypeTests && TypeTestFunc) {
1829 auto *CI = cast<CallInst>(U.getUser());
1832 if (
auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
1833 Assume->eraseFromParent();
1839 [](
User *U) ->
bool { return isa<PHINode>(U); }));
1864 if ((!TypeTestFunc || TypeTestFunc->
use_empty()) &&
1865 (!ICallBranchFunnelFunc || ICallBranchFunnelFunc->
use_empty()) &&
1866 !ExportSummary && !ImportSummary)
1869 if (ImportSummary) {
1872 importTypeTest(cast<CallInst>(U.getUser()));
1874 if (ICallBranchFunnelFunc && !ICallBranchFunnelFunc->
use_empty())
1876 "unexpected call to llvm.icall.branch.funnel during import phase");
1883 if (
F.hasLocalLinkage())
1888 std::string(
F.getName())))
1889 Decls.push_back(&
F);
1892 std::vector<GlobalAlias *> AliasesToErase;
1894 ScopedSaveAliaseesAndUsed
S(
M);
1896 importFunction(
F,
true, AliasesToErase);
1897 for (
auto F : Decls)
1898 importFunction(
F,
false, AliasesToErase);
1911 GlobalClassesTy GlobalClasses;
1923 std::vector<GlobalTypeMember *> RefGlobals;
1926 unsigned CurUniqueId = 0;
1931 const bool CrossDsoCfi =
M.getModuleFlag(
"Cross-DSO CFI") !=
nullptr;
1933 struct ExportedFunctionInfo {
1938 if (ExportSummary) {
1941 for (
auto &
I : *ExportSummary)
1942 for (
auto &GVS :
I.second.SummaryList)
1944 for (
auto &Ref : GVS->refs())
1947 NamedMDNode *CfiFunctionsMD =
M.getNamedMetadata(
"cfi.functions");
1948 if (CfiFunctionsMD) {
1949 for (
auto FuncMD : CfiFunctionsMD->
operands()) {
1950 assert(FuncMD->getNumOperands() >= 2);
1952 cast<MDString>(FuncMD->getOperand(0))->getString();
1954 cast<ConstantAsMetadata>(FuncMD->getOperand(1))
1956 ->getUniqueInteger()
1959 GlobalValue::dropLLVMManglingEscape(FunctionName));
1962 if (!ExportSummary->isGUIDLive(GUID))
1964 if (!AddressTaken.
count(GUID)) {
1968 bool Exported =
false;
1969 if (
auto VI = ExportSummary->getValueInfo(GUID))
1970 for (
auto &GVS :
VI.getSummaryList())
1971 if (GVS->isLive() && !GlobalValue::isLocalLinkage(GVS->linkage()))
1979 P.first->second = {
Linkage, FuncMD};
1985 MDNode *FuncMD =
P.second.FuncMD;
1987 if (
F &&
F->hasLocalLinkage()) {
1994 F->setName(
F->getName() +
".1");
1999 F = Function::Create(
2001 GlobalVariable::ExternalLinkage,
2002 M.getDataLayout().getProgramAddressSpace(), FunctionName, &
M);
2009 if (
F->hasAvailableExternallyLinkage()) {
2010 F->setLinkage(GlobalValue::ExternalLinkage);
2012 F->setComdat(
nullptr);
2019 F->setLinkage(GlobalValue::ExternalLinkage);
2025 if (
F->isDeclaration()) {
2027 F->setLinkage(GlobalValue::ExternalWeakLinkage);
2029 F->eraseMetadata(LLVMContext::MD_type);
2031 F->addMetadata(LLVMContext::MD_type,
2046 bool IsJumpTableCanonical =
false;
2047 bool IsExported =
false;
2048 if (
Function *
F = dyn_cast<Function>(&GO)) {
2051 IsJumpTableCanonical |=
2058 }
else if (!
F->hasAddressTaken()) {
2059 if (!CrossDsoCfi || !IsJumpTableCanonical ||
F->hasLocalLinkage())
2064 auto *GTM = GlobalTypeMember::create(Alloc, &GO, IsJumpTableCanonical,
2066 GlobalTypeMembers[&GO] = GTM;
2068 verifyTypeMDNode(&GO,
Type);
2069 auto &
Info = TypeIdInfo[
Type->getOperand(1)];
2070 Info.UniqueId = ++CurUniqueId;
2071 Info.RefGlobals.push_back(GTM);
2075 auto AddTypeIdUse = [&](
Metadata *TypeId) -> TypeIdUserInfo & {
2080 auto Ins = TypeIdUsers.insert({TypeId, {}});
2083 GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId);
2084 GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI);
2087 for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals)
2088 CurSet = GlobalClasses.unionSets(
2089 CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM)));
2092 return Ins.first->second;
2096 for (
const Use &U : TypeTestFunc->
uses()) {
2097 auto CI = cast<CallInst>(U.getUser());
2105 for (
const Use &CIU : CI->
uses()) {
2106 if (isa<AssumeInst>(CIU.getUser()))
2108 OnlyAssumeUses =
false;
2114 auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->
getArgOperand(1));
2117 auto TypeId = TypeIdMDVal->getMetadata();
2118 AddTypeIdUse(TypeId).CallSites.push_back(CI);
2122 if (ICallBranchFunnelFunc) {
2123 for (
const Use &U : ICallBranchFunnelFunc->
uses()) {
2124 if (Arch != Triple::x86_64)
2126 "llvm.icall.branch.funnel not supported on this target");
2128 auto CI = cast<CallInst>(U.getUser());
2130 std::vector<GlobalTypeMember *> Targets;
2134 GlobalClassesTy::member_iterator CurSet;
2135 for (
unsigned I = 1;
I != CI->
arg_size();
I += 2) {
2141 "Expected branch funnel operand to be global value");
2143 GlobalTypeMember *GTM = GlobalTypeMembers[
Base];
2144 Targets.push_back(GTM);
2145 GlobalClassesTy::member_iterator NewSet =
2146 GlobalClasses.findLeader(GlobalClasses.insert(GTM));
2150 CurSet = GlobalClasses.unionSets(CurSet, NewSet);
2153 GlobalClasses.unionSets(
2154 CurSet, GlobalClasses.findLeader(
2155 GlobalClasses.insert(ICallBranchFunnel::create(
2156 Alloc, CI, Targets, ++CurUniqueId))));
2160 if (ExportSummary) {
2162 for (
auto &
P : TypeIdInfo) {
2163 if (
auto *TypeId = dyn_cast<MDString>(
P.first))
2164 MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
2168 for (
auto &
P : *ExportSummary) {
2169 for (
auto &
S :
P.second.SummaryList) {
2170 if (!ExportSummary->isGlobalValueLive(
S.get()))
2172 if (
auto *
FS = dyn_cast<FunctionSummary>(
S->getBaseObject()))
2175 AddTypeIdUse(MD).IsExported =
true;
2180 if (GlobalClasses.empty())
2185 std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
2186 for (GlobalClassesTy::iterator
I = GlobalClasses.begin(),
2187 E = GlobalClasses.end();
2191 ++NumTypeIdDisjointSets;
2193 unsigned MaxUniqueId = 0;
2194 for (GlobalClassesTy::member_iterator
MI = GlobalClasses.member_begin(
I);
2195 MI != GlobalClasses.member_end(); ++
MI) {
2197 MaxUniqueId =
std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
2198 else if (
auto *BF =
MI->dyn_cast<ICallBranchFunnel *>())
2199 MaxUniqueId =
std::max(MaxUniqueId, BF->UniqueId);
2201 Sets.emplace_back(
I, MaxUniqueId);
2206 for (
const auto &
S : Sets) {
2208 std::vector<Metadata *> TypeIds;
2209 std::vector<GlobalTypeMember *> Globals;
2210 std::vector<ICallBranchFunnel *> ICallBranchFunnels;
2211 for (GlobalClassesTy::member_iterator
MI =
2212 GlobalClasses.member_begin(
S.first);
2213 MI != GlobalClasses.member_end(); ++
MI) {
2216 else if (
MI->is<GlobalTypeMember *>())
2217 Globals.push_back(
MI->get<GlobalTypeMember *>());
2219 ICallBranchFunnels.push_back(
MI->get<ICallBranchFunnel *>());
2225 return TypeIdInfo[
M1].UniqueId < TypeIdInfo[M2].UniqueId;
2230 [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
2231 return F1->UniqueId < F2->UniqueId;
2235 buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
2238 allocateByteArrays();
2242 if (ExportSummary) {
2243 if (
NamedMDNode *AliasesMD =
M.getNamedMetadata(
"aliases")) {
2244 for (
auto AliasMD : AliasesMD->operands()) {
2245 assert(AliasMD->getNumOperands() >= 4);
2247 cast<MDString>(AliasMD->getOperand(0))->getString();
2248 StringRef Aliasee = cast<MDString>(AliasMD->getOperand(1))->getString();
2252 !
M.getNamedAlias(Aliasee))
2257 cast<ConstantAsMetadata>(AliasMD->getOperand(2))
2259 ->getUniqueInteger()
2262 static_cast<bool>(cast<ConstantAsMetadata>(AliasMD->getOperand(3))
2264 ->getUniqueInteger()
2267 auto *Alias = GlobalAlias::create(
"",
M.getNamedAlias(Aliasee));
2270 Alias->
setLinkage(GlobalValue::WeakAnyLinkage);
2272 if (
auto *
F =
M.getFunction(AliasName)) {
2274 F->replaceAllUsesWith(Alias);
2275 F->eraseFromParent();
2284 if (ExportSummary) {
2285 if (
NamedMDNode *SymversMD =
M.getNamedMetadata(
"symvers")) {
2286 for (
auto Symver : SymversMD->operands()) {
2287 assert(Symver->getNumOperands() >= 2);
2289 cast<MDString>(Symver->getOperand(0))->getString();
2290 StringRef Alias = cast<MDString>(Symver->getOperand(1))->getString();
2295 M.appendModuleInlineAsm(
2308 Changed = LowerTypeTestsModule::runForTesting(
M);
2311 LowerTypeTestsModule(
M, ExportSummary, ImportSummary, DropTypeTests)