105 using namespace llvm;
108 #define DEBUG_TYPE "wholeprogramdevirt"
111 "wholeprogramdevirt-summary-action",
112 cl::desc(
"What to do with the summary when running this pass"),
115 "Import typeid resolutions from summary and globals"),
117 "Export typeid resolutions to summary and globals")),
121 "wholeprogramdevirt-read-summary",
123 "Read summary from given bitcode or YAML file before running pass"),
127 "wholeprogramdevirt-write-summary",
128 cl::desc(
"Write summary to given bitcode or YAML file after running pass. "
129 "Output file format is deduced from extension: *.bc means writing "
130 "bitcode, otherwise YAML"),
136 cl::desc(
"Maximum number of call targets per "
137 "call site to enable branch funnels"));
142 cl::desc(
"Print index-based devirtualization messages"));
151 cl::desc(
"Enable whole program visibility"));
158 cl::desc(
"Disable whole program visibility (overrides enabling options)"));
163 cl::desc(
"Prevent function(s) from being devirtualized"),
172 cl::desc(
"Add code to trap on incorrect devirtualizations"));
176 std::vector<GlobPattern> Patterns;
177 template <
class T>
void init(
const T &StringList) {
178 for (
const auto &
S : StringList)
196 bool IsAfter, uint64_t
Size) {
198 uint64_t MinByte = 0;
226 std::vector<ArrayRef<uint8_t>> Used;
229 :
Target.TM->Bits->Before.BytesUsed;
230 uint64_t
Offset = IsAfter ? MinByte -
Target.minAfterBytes()
231 : MinByte -
Target.minBeforeBytes();
241 for (
unsigned I = 0;; ++
I) {
242 uint8_t BitsUsed = 0;
243 for (
auto &&
B : Used)
246 if (BitsUsed != 0xff)
247 return (MinByte +
I) * 8 +
253 for (
unsigned I = 0;; ++
I) {
254 for (
auto &&
B : Used) {
256 while ((
I + Byte) <
B.size() && Byte < (
Size / 8)) {
262 return (MinByte +
I) * 8;
270 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
272 OffsetByte = -(AllocBefore / 8 + 1);
274 OffsetByte = -((AllocBefore + 7) / 8 + (
BitWidth + 7) / 8);
275 OffsetBit = AllocBefore % 8;
279 Target.setBeforeBit(AllocBefore);
287 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
289 OffsetByte = AllocAfter / 8;
291 OffsetByte = (AllocAfter + 7) / 8;
292 OffsetBit = AllocAfter % 8;
296 Target.setAfterBit(AllocAfter);
334 const VTableSlot &RHS) {
335 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
364 struct VirtualCallSite {
371 unsigned *NumUnsafeUses =
nullptr;
382 <<
NV(
"Optimization", OptName)
383 <<
": devirtualized a call to "
384 <<
NV(
"FunctionName", TargetName));
387 void replaceAndErase(
392 emitRemark(OptName, TargetName, OREGetter);
394 if (
auto *II = dyn_cast<InvokeInst>(&CB)) {
396 II->getUnwindDest()->removePredecessor(II->getParent());
408 struct CallSiteInfo {
413 std::vector<VirtualCallSite> CallSites;
418 bool AllCallSitesDevirted =
true;
425 bool SummaryHasTypeTestAssumeUsers =
false;
434 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
435 std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
437 bool isExported()
const {
438 return SummaryHasTypeTestAssumeUsers ||
439 !SummaryTypeCheckedLoadUsers.empty();
443 SummaryTypeCheckedLoadUsers.push_back(
FS);
444 AllCallSitesDevirted =
false;
448 SummaryTypeTestAssumeUsers.push_back(
FS);
449 SummaryHasTypeTestAssumeUsers =
true;
450 AllCallSitesDevirted =
false;
454 AllCallSitesDevirted =
true;
457 SummaryTypeCheckedLoadUsers.clear();
462 struct VTableSlotInfo {
469 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
471 void addCallSite(
Value *VTable,
CallBase &CB,
unsigned *NumUnsafeUses);
474 CallSiteInfo &findCallSiteInfo(
CallBase &CB);
477 CallSiteInfo &VTableSlotInfo::findCallSiteInfo(
CallBase &CB) {
478 std::vector<uint64_t>
Args;
479 auto *CBType = dyn_cast<IntegerType>(CB.
getType());
480 if (!CBType || CBType->getBitWidth() > 64 || CB.
arg_empty())
483 auto *CI = dyn_cast<ConstantInt>(
Arg);
484 if (!CI || CI->getBitWidth() > 64)
486 Args.push_back(CI->getZExtValue());
488 return ConstCSInfo[
Args];
491 void VTableSlotInfo::addCallSite(
Value *VTable,
CallBase &CB,
492 unsigned *NumUnsafeUses) {
493 auto &CSI = findCallSiteInfo(CB);
494 CSI.AllCallSitesDevirted =
false;
495 CSI.CallSites.push_back({
VTable, CB, NumUnsafeUses});
498 struct DevirtModule {
529 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
530 PatternList FunctionsToSkip;
537 :
M(
M), AARGetter(AARGetter), LookupDomTree(LookupDomTree),
538 ExportSummary(ExportSummary), ImportSummary(ImportSummary),
539 Int8Ty(
Type::getInt8Ty(
M.getContext())),
540 Int8PtrTy(
Type::getInt8PtrTy(
M.getContext())),
542 Int64Ty(
Type::getInt64Ty(
M.getContext())),
543 IntPtrTy(
M.getDataLayout().getIntPtrType(
M.getContext(), 0)),
545 RemarksEnabled(areRemarksEnabled()), OREGetter(OREGetter) {
546 assert(!(ExportSummary && ImportSummary));
550 bool areRemarksEnabled();
553 scanTypeTestUsers(
Function *TypeTestFunc,
555 void scanTypeCheckedLoadUsers(
Function *TypeCheckedLoadFunc);
557 void buildTypeIdentifierMap(
558 std::vector<VTableBits> &
Bits,
561 tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
562 const std::set<TypeMemberInfo> &TypeMemberInfos,
563 uint64_t ByteOffset);
565 void applySingleImplDevirt(VTableSlotInfo &SlotInfo,
Constant *TheFn,
569 VTableSlotInfo &SlotInfo,
572 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
Constant *
JT,
575 VTableSlotInfo &SlotInfo,
578 bool tryEvaluateFunctionsWithArgs(
582 void applyUniformRetValOpt(CallSiteInfo &CSInfo,
StringRef FnName,
585 CallSiteInfo &CSInfo,
593 bool shouldExportConstantsAsAbsoluteSymbols();
613 void applyUniqueRetValOpt(CallSiteInfo &CSInfo,
StringRef FnName,
bool IsOne,
615 bool tryUniqueRetValOpt(
unsigned BitWidth,
617 CallSiteInfo &CSInfo,
621 void applyVirtualConstProp(CallSiteInfo &CSInfo,
StringRef FnName,
624 VTableSlotInfo &SlotInfo,
630 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
634 void removeRedundantTypeTests();
650 std::set<GlobalValue::GUID> &ExportedGUIDs;
654 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
658 PatternList FunctionsToSkip;
662 std::set<GlobalValue::GUID> &ExportedGUIDs,
663 std::map<
ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
664 : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
665 LocalWPDTargetsMap(LocalWPDTargetsMap) {
669 bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
671 uint64_t ByteOffset);
675 VTableSlotInfo &SlotInfo,
677 std::set<ValueInfo> &DevirtTargets);
682 struct WholeProgramDevirt :
public ModulePass {
685 bool UseCommandLine =
false;
697 ImportSummary(ImportSummary) {
701 bool runOnModule(
Module &M)
override {
710 std::unique_ptr<OptimizationRemarkEmitter> ORE;
712 ORE = std::make_unique<OptimizationRemarkEmitter>(
F);
717 return this->getAnalysis<DominatorTreeWrapperPass>(
F).getDomTree();
721 return DevirtModule::runForTesting(M,
LegacyAARGetter(*
this), OREGetter,
724 return DevirtModule(M,
LegacyAARGetter(*
this), OREGetter, LookupDomTree,
725 ExportSummary, ImportSummary)
739 "Whole program devirtualization",
false,
false)
745 char WholeProgramDevirt::
ID = 0;
750 return new WholeProgramDevirt(ExportSummary, ImportSummary);
765 if (UseCommandLine) {
766 if (DevirtModule::runForTesting(
M, AARGetter, OREGetter, LookupDomTree))
770 if (!DevirtModule(
M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
790 Module &M,
bool WholeProgramVisibilityEnabledInLTO,
798 if (GV.hasMetadata(LLVMContext::MD_type) &&
802 !DynamicExportSymbols.
count(GV.getGUID()))
815 for (
auto &
S :
P.second.SummaryList) {
816 auto *GVar = dyn_cast<GlobalVarSummary>(
S.get());
821 DynamicExportSymbols.
count(
P.first))
830 std::map<
ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
831 DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
837 std::map<
ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
838 for (
auto &
T : LocalWPDTargetsMap) {
841 assert(
VI.getSummaryList().size() == 1 &&
842 "Devirt of local target has more than one copy");
843 auto &
S =
VI.getSummaryList()[0];
844 if (!isExported(
S->modulePath(),
VI))
848 for (
auto &SlotSummary :
T.second) {
851 auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
852 assert(WPDRes != TIdSum->WPDRes.end());
854 WPDRes->second.SingleImplName,
873 "combined summary should contain Regular LTO module");
877 bool DevirtModule::runForTesting(
881 std::unique_ptr<ModuleSummaryIndex> Summary =
882 std::make_unique<ModuleSummaryIndex>(
false);
889 auto ReadSummaryFile =
891 if (
Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr =
898 yaml::Input
In(ReadSummaryFile->getBuffer());
905 DevirtModule(M, AARGetter, OREGetter, LookupDomTree,
923 yaml::Output Out(OS);
931 void DevirtModule::buildTypeIdentifierMap(
932 std::vector<VTableBits> &
Bits,
935 Bits.reserve(
M.getGlobalList().size());
939 GV.getMetadata(LLVMContext::MD_type, Types);
940 if (GV.isDeclaration() || Types.empty())
946 Bits.back().GV = &GV;
947 Bits.back().ObjectSize =
948 M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType());
949 BitsPtr = &
Bits.back();
957 cast<ConstantAsMetadata>(
Type->getOperand(0))->getValue())
965 bool DevirtModule::tryFindVirtualCallTargets(
966 std::vector<VirtualCallTarget> &TargetsForSlot,
967 const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset) {
969 if (!
TM.Bits->GV->isConstant())
974 if (
TM.Bits->GV->getVCallVisibility() ==
979 TM.Offset + ByteOffset, M);
987 if (FunctionsToSkip.match(Fn->getName()))
992 if (Fn->getName() ==
"__cxa_pure_virtual")
995 TargetsForSlot.push_back({Fn, &
TM});
999 return !TargetsForSlot.empty();
1002 bool DevirtIndex::tryFindVirtualCallTargets(
1004 uint64_t ByteOffset) {
1017 bool LocalFound =
false;
1018 for (
auto &
S :
P.VTableVI.getSummaryList()) {
1024 auto *CurVS = cast<GlobalVarSummary>(
S->getBaseObject());
1025 if (!CurVS->vTableFuncs().empty() ||
1047 for (
auto VTP :
VS->vTableFuncs()) {
1048 if (VTP.VTableOffset !=
P.AddressPointOffset + ByteOffset)
1051 TargetsForSlot.push_back(VTP.FuncVI);
1056 return !TargetsForSlot.empty();
1059 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
1060 Constant *TheFn,
bool &IsExported) {
1065 auto Apply = [&](CallSiteInfo &CSInfo) {
1066 for (
auto &&VCallSite : CSInfo.CallSites) {
1068 VCallSite.emitRemark(
"single-impl",
1070 auto &CB = VCallSite.CB;
1082 Builder.SetInsertPoint(ThenTerm);
1084 auto *CallTrap =
Builder.CreateCall(TrapFn);
1092 if (VCallSite.NumUnsafeUses)
1093 --*VCallSite.NumUnsafeUses;
1095 if (CSInfo.isExported())
1097 CSInfo.markDevirt();
1099 Apply(SlotInfo.CSInfo);
1100 for (
auto &
P : SlotInfo.ConstCSInfo)
1106 if (
Callee.getSummaryList().empty())
1113 bool IsExported =
false;
1114 auto &
S =
Callee.getSummaryList()[0];
1116 auto AddCalls = [&](CallSiteInfo &CSInfo) {
1117 for (
auto *
FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1119 IsExported |=
S->modulePath() !=
FS->modulePath();
1121 for (
auto *
FS : CSInfo.SummaryTypeTestAssumeUsers) {
1123 IsExported |=
S->modulePath() !=
FS->modulePath();
1127 for (
auto &
P : SlotInfo.ConstCSInfo)
1132 bool DevirtModule::trySingleImplDevirt(
1138 Function *TheFn = TargetsForSlot[0].Fn;
1139 for (
auto &&
Target : TargetsForSlot)
1145 TargetsForSlot[0].WasDevirt =
true;
1147 bool IsExported =
false;
1148 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
1156 std::string NewName = (TheFn->
getName() +
"$merged").str();
1162 if (
C->getName() == TheFn->
getName()) {
1163 Comdat *NewC =
M.getOrInsertComdat(NewName);
1166 if (GO.getComdat() ==
C)
1188 VTableSlotInfo &SlotInfo,
1190 std::set<ValueInfo> &DevirtTargets) {
1193 auto TheFn = TargetsForSlot[0];
1194 for (
auto &&
Target : TargetsForSlot)
1199 auto Size = TheFn.getSummaryList().
size();
1205 if (FunctionsToSkip.match(TheFn.name()))
1210 for (
auto &
S : TheFn.getSummaryList())
1216 DevirtTargets.insert(TheFn);
1218 auto &
S = TheFn.getSummaryList()[0];
1219 bool IsExported =
AddCalls(SlotInfo, TheFn);
1221 ExportedGUIDs.insert(TheFn.
getGUID());
1234 LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1248 void DevirtModule::tryICallBranchFunnel(
1258 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1260 for (
auto &
P : SlotInfo.ConstCSInfo)
1261 if (!
P.second.AllCallSitesDevirted) {
1262 HasNonDevirt =
true;
1272 if (isa<MDString>(
Slot.TypeID)) {
1274 M.getDataLayout().getProgramAddressSpace(),
1275 getGlobalName(Slot, {},
"branch_funnel"), &M);
1279 M.getDataLayout().getProgramAddressSpace(),
1280 "branch_funnel", &M);
1282 JT->addAttribute(1, Attribute::Nest);
1284 std::vector<Value *> JTArgs;
1285 JTArgs.push_back(
JT->arg_begin());
1286 for (
auto &T : TargetsForSlot) {
1287 JTArgs.push_back(getMemberAddr(
T.TM));
1288 JTArgs.push_back(
T.Fn);
1299 bool IsExported =
false;
1300 applyICallBranchFunnel(SlotInfo,
JT, IsExported);
1305 void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1307 auto Apply = [&](CallSiteInfo &CSInfo) {
1308 if (CSInfo.isExported())
1310 if (CSInfo.AllCallSitesDevirted)
1312 for (
auto &&VCallSite : CSInfo.CallSites) {
1322 VCallSite.emitRemark(
"branch-funnel",
1323 JT->stripPointerCasts()->getName(), OREGetter);
1327 std::vector<Type *> NewArgs;
1328 NewArgs.push_back(Int8PtrTy);
1336 std::vector<Value *>
Args;
1337 Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
1341 if (isa<CallInst>(CB))
1342 NewCS = IRB.CreateCall(NewFT, IRB.CreateBitCast(
JT, NewFTPtr),
Args);
1344 NewCS = IRB.CreateInvoke(NewFT, IRB.CreateBitCast(
JT, NewFTPtr),
1345 cast<InvokeInst>(CB).getNormalDest(),
1346 cast<InvokeInst>(CB).getUnwindDest(),
Args);
1350 std::vector<AttributeSet> NewArgAttrs;
1353 M.getContext(), Attribute::Nest)}));
1354 for (
unsigned I = 0;
I + 2 <
Attrs.getNumAttrSets(); ++
I)
1355 NewArgAttrs.push_back(
Attrs.getParamAttributes(
I));
1358 Attrs.getRetAttributes(), NewArgAttrs));
1364 if (VCallSite.NumUnsafeUses)
1365 --*VCallSite.NumUnsafeUses;
1372 Apply(SlotInfo.CSInfo);
1373 for (
auto &
P : SlotInfo.ConstCSInfo)
1377 bool DevirtModule::tryEvaluateFunctionsWithArgs(
1383 if (
Target.Fn->arg_size() !=
Args.size() + 1)
1390 for (
unsigned I = 0;
I !=
Args.size(); ++
I) {
1391 auto *ArgTy = dyn_cast<IntegerType>(
1392 Target.Fn->getFunctionType()->getParamType(
I + 1));
1399 if (!Eval.EvaluateFunction(
Target.Fn, RetVal, EvalArgs) ||
1400 !isa<ConstantInt>(RetVal))
1402 Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
1407 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo,
StringRef FnName,
1408 uint64_t TheRetVal) {
1409 for (
auto Call : CSInfo.CallSites)
1410 Call.replaceAndErase(
1411 "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1413 CSInfo.markDevirt();
1416 bool DevirtModule::tryUniformRetValOpt(
1421 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1423 if (
Target.RetVal != TheRetVal)
1426 if (CSInfo.isExported()) {
1428 Res->
Info = TheRetVal;
1431 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1433 for (
auto &&
Target : TargetsForSlot)
1438 std::string DevirtModule::getGlobalName(VTableSlot Slot,
1441 std::string FullName =
"__typeid_";
1443 OS << cast<MDString>(
Slot.TypeID)->getString() <<
'_' <<
Slot.ByteOffset;
1450 bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1458 getGlobalName(Slot,
Args,
Name),
C, &M);
1465 if (shouldExportConstantsAsAbsoluteSymbols()) {
1478 M.getOrInsertGlobal(getGlobalName(Slot,
Args,
Name), Int8Arr0Ty);
1479 auto *GV = dyn_cast<GlobalVariable>(
C);
1488 if (!shouldExportConstantsAsAbsoluteSymbols())
1492 auto *GV = cast<GlobalVariable>(
C->stripPointerCasts());
1497 if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1500 auto SetAbsRange = [&](uint64_t Min, uint64_t
Max) {
1503 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1508 SetAbsRange(~0ull, ~0ull);
1510 SetAbsRange(0, 1ull << AbsWidth);
1514 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo,
StringRef FnName,
1517 for (
auto &&Call : CSInfo.CallSites) {
1521 B.CreateBitCast(UniqueMemberAddr,
Call.VTable->getType()));
1522 Cmp =
B.CreateZExt(Cmp,
Call.CB.getType());
1523 Call.replaceAndErase(
"unique-ret-val", FnName, RemarksEnabled, OREGetter,
1526 CSInfo.markDevirt();
1535 bool DevirtModule::tryUniqueRetValOpt(
1540 auto tryUniqueRetValOptFor = [&](
bool IsOne) {
1543 if (
Target.RetVal == (IsOne ? 1 : 0)) {
1546 UniqueMember =
Target.TM;
1554 Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1555 if (CSInfo.isExported()) {
1559 exportGlobal(Slot,
Args,
"unique_member", UniqueMemberAddr);
1563 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1568 for (
auto &&
Target : TargetsForSlot)
1575 if (tryUniqueRetValOptFor(
true))
1577 if (tryUniqueRetValOptFor(
false))
1583 void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo,
StringRef FnName,
1585 for (
auto Call : CSInfo.CallSites) {
1586 auto *RetType = cast<IntegerType>(
Call.CB.getType());
1589 B.CreateGEP(Int8Ty,
B.CreateBitCast(
Call.VTable, Int8PtrTy), Byte);
1590 if (RetType->getBitWidth() == 1) {
1594 Call.replaceAndErase(
"virtual-const-prop-1-bit", FnName, RemarksEnabled,
1595 OREGetter, IsBitSet);
1597 Value *ValAddr =
B.CreateBitCast(
Addr, RetType->getPointerTo());
1598 Value *Val =
B.CreateLoad(RetType, ValAddr);
1599 Call.replaceAndErase(
"virtual-const-prop", FnName, RemarksEnabled,
1603 CSInfo.markDevirt();
1606 bool DevirtModule::tryVirtualConstProp(
1610 auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
1613 unsigned BitWidth = RetType->getBitWidth();
1628 if (
Target.Fn->isDeclaration() ||
1631 Target.Fn->arg_empty() || !
Target.Fn->arg_begin()->use_empty() ||
1632 Target.Fn->getReturnType() != RetType)
1636 for (
auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1637 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1642 ResByArg = &Res->
ResByArg[CSByConstantArg.first];
1644 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1647 if (tryUniqueRetValOpt(
BitWidth, TargetsForSlot, CSByConstantArg.second,
1648 ResByArg, Slot, CSByConstantArg.first))
1653 uint64_t AllocBefore =
1655 uint64_t AllocAfter =
1660 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1661 for (
auto &&
Target : TargetsForSlot) {
1662 TotalPaddingBefore += std::max<int64_t>(
1663 (AllocBefore + 7) / 8 -
Target.allocatedBeforeBytes() - 1, 0);
1664 TotalPaddingAfter += std::max<int64_t>(
1665 (AllocAfter + 7) / 8 -
Target.allocatedAfterBytes() - 1, 0);
1670 if (
std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1677 if (TotalPaddingBefore <= TotalPaddingAfter)
1685 for (
auto &&
Target : TargetsForSlot)
1689 if (CSByConstantArg.second.isExported()) {
1691 exportConstant(Slot, CSByConstantArg.first,
"byte", OffsetByte,
1693 exportConstant(Slot, CSByConstantArg.first,
"bit", 1ULL << OffsetBit,
1700 applyVirtualConstProp(CSByConstantArg.second,
1701 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
1707 if (
B.Before.Bytes.empty() &&
B.After.Bytes.empty())
1712 Align Alignment =
M.getDataLayout().getValueOrABITypeAlignment(
1713 B.GV->getAlign(),
B.GV->getValueType());
1714 B.Before.Bytes.resize(
alignTo(
B.Before.Bytes.size(), Alignment));
1717 for (
size_t I = 0,
Size =
B.Before.Bytes.size();
I !=
Size / 2; ++
I)
1724 B.GV->getInitializer(),
1729 NewGV->setSection(
B.GV->getSection());
1730 NewGV->setComdat(
B.GV->getComdat());
1731 NewGV->setAlignment(
MaybeAlign(
B.GV->getAlignment()));
1735 NewGV->copyMetadata(
B.GV,
B.Before.Bytes.size());
1740 B.GV->getInitializer()->getType(), 0,
B.GV->getLinkage(),
"",
1742 NewInit->getType(), NewGV,
1744 ConstantInt::get(Int32Ty, 1)}),
1746 Alias->setVisibility(
B.GV->getVisibility());
1747 Alias->takeName(
B.GV);
1749 B.GV->replaceAllUsesWith(Alias);
1750 B.GV->eraseFromParent();
1753 bool DevirtModule::areRemarksEnabled() {
1754 const auto &FL =
M.getFunctionList();
1756 const auto &BBL = Fn.getBasicBlockList();
1760 return DI.isEnabled();
1765 void DevirtModule::scanTypeTestUsers(
1775 auto CI = dyn_cast<CallInst>(
I->getUser());
1783 auto &DT = LookupDomTree(*CI->getFunction());
1787 cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
1789 if (!Assumes.empty()) {
1792 CallSlots[{TypeId,
Call.Offset}].addCallSite(Ptr,
Call.CB,
nullptr);
1795 auto RemoveTypeTestAssumes = [&]() {
1797 for (
auto Assume : Assumes)
1798 Assume->eraseFromParent();
1801 if (CI->use_empty())
1802 CI->eraseFromParent();
1817 if (!TypeIdMap.count(TypeId))
1818 RemoveTypeTestAssumes();
1829 else if (ImportSummary && isa<MDString>(TypeId)) {
1833 RemoveTypeTestAssumes();
1842 void DevirtModule::scanTypeCheckedLoadUsers(
Function *TypeCheckedLoadFunc) {
1845 for (
auto I = TypeCheckedLoadFunc->
use_begin(),
1846 E = TypeCheckedLoadFunc->
use_end();
1848 auto CI = dyn_cast<CallInst>(
I->getUser());
1853 Value *Ptr = CI->getArgOperand(0);
1855 Value *TypeIdValue = CI->getArgOperand(2);
1856 Metadata *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
1861 bool HasNonCallUses =
false;
1862 auto &DT = LookupDomTree(*CI->getFunction());
1864 HasNonCallUses, CI, DT);
1873 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
1876 Value *LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEPPtr);
1880 LoadedPtr->eraseFromParent();
1884 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
1885 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
1889 Pred->eraseFromParent();
1896 if (!CI->use_empty()) {
1899 Pair =
B.CreateInsertValue(Pair, LoadedValue, {0});
1900 Pair =
B.CreateInsertValue(Pair, TypeTestCall, {1});
1901 CI->replaceAllUsesWith(Pair);
1905 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
1906 NumUnsafeUses = DevirtCalls.size();
1914 CallSlots[{TypeId,
Call.Offset}].addCallSite(Ptr,
Call.CB,
1918 CI->eraseFromParent();
1922 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
1923 auto *TypeId = dyn_cast<MDString>(
Slot.TypeID);
1930 auto ResI = TidSummary->
WPDRes.find(
Slot.ByteOffset);
1931 if (ResI == TidSummary->
WPDRes.end())
1945 bool IsExported =
false;
1946 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
1950 for (
auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
1951 auto I = Res.
ResByArg.find(CSByConstantArg.first);
1954 auto &ResByArg =
I->second;
1961 applyUniformRetValOpt(CSByConstantArg.second,
"", ResByArg.
Info);
1965 importGlobal(Slot, CSByConstantArg.first,
"unique_member");
1966 applyUniqueRetValOpt(CSByConstantArg.second,
"", ResByArg.
Info,
1971 Constant *
Byte = importConstant(Slot, CSByConstantArg.first,
"byte",
1973 Constant *
Bit = importConstant(Slot, CSByConstantArg.first,
"bit", Int8Ty,
1975 applyVirtualConstProp(CSByConstantArg.second,
"", Byte,
Bit);
1987 M.getOrInsertFunction(getGlobalName(Slot, {},
"branch_funnel"),
1990 bool IsExported =
false;
1991 applyICallBranchFunnel(SlotInfo,
JT, IsExported);
1996 void DevirtModule::removeRedundantTypeTests() {
1998 for (
auto &&U : NumUnsafeUsesForTypeTest) {
1999 if (U.second == 0) {
2000 U.first->replaceAllUsesWith(True);
2001 U.first->eraseFromParent();
2006 bool DevirtModule::run() {
2024 if (!ExportSummary &&
2025 (!TypeTestFunc || TypeTestFunc->
use_empty() || !AssumeFunc ||
2027 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->
use_empty()))
2031 std::vector<VTableBits>
Bits;
2033 buildTypeIdentifierMap(
Bits, TypeIdMap);
2035 if (TypeTestFunc && AssumeFunc)
2036 scanTypeTestUsers(TypeTestFunc, TypeIdMap);
2038 if (TypeCheckedLoadFunc)
2039 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
2041 if (ImportSummary) {
2042 for (
auto &
S : CallSlots)
2043 importResolution(
S.first,
S.second);
2045 removeRedundantTypeTests();
2051 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2058 if (TypeIdMap.
empty())
2062 if (ExportSummary) {
2064 for (
auto &
P : TypeIdMap) {
2065 if (
auto *TypeId = dyn_cast<MDString>(
P.first))
2070 for (
auto &
P : *ExportSummary) {
2071 for (
auto &
S :
P.second.SummaryList) {
2072 auto *
FS = dyn_cast<FunctionSummary>(
S.get());
2077 for (
Metadata *MD : MetadataByGUID[VF.GUID]) {
2078 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(
FS);
2082 for (
Metadata *MD : MetadataByGUID[VF.GUID]) {
2083 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(
FS);
2087 FS->type_test_assume_const_vcalls()) {
2088 for (
Metadata *MD : MetadataByGUID[
VC.VFunc.GUID]) {
2089 CallSlots[{MD,
VC.VFunc.Offset}]
2090 .ConstCSInfo[
VC.Args]
2091 .addSummaryTypeTestAssumeUser(
FS);
2095 FS->type_checked_load_const_vcalls()) {
2096 for (
Metadata *MD : MetadataByGUID[
VC.VFunc.GUID]) {
2097 CallSlots[{MD,
VC.VFunc.Offset}]
2098 .ConstCSInfo[
VC.Args]
2099 .addSummaryTypeCheckedLoadUser(
FS);
2107 bool DidVirtualConstProp =
false;
2108 std::map<std::string, Function*> DevirtTargets;
2109 for (
auto &
S : CallSlots) {
2113 std::vector<VirtualCallTarget> TargetsForSlot;
2115 const std::set<TypeMemberInfo> &TypeMemberInfos = TypeIdMap[
S.first.TypeID];
2116 if (ExportSummary && isa<MDString>(
S.first.TypeID) &&
2117 TypeMemberInfos.size())
2124 Res = &ExportSummary
2125 ->getOrInsertTypeIdSummary(
2126 cast<MDString>(
S.first.TypeID)->getString())
2127 .WPDRes[
S.first.ByteOffset];
2128 if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos,
2129 S.first.ByteOffset)) {
2131 if (!trySingleImplDevirt(ExportSummary, TargetsForSlot,
S.second, Res)) {
2132 DidVirtualConstProp |=
2133 tryVirtualConstProp(TargetsForSlot,
S.second, Res,
S.first);
2135 tryICallBranchFunnel(TargetsForSlot,
S.second, Res,
S.first);
2140 for (
const auto &T : TargetsForSlot)
2142 DevirtTargets[std::string(
T.Fn->getName())] =
T.Fn;
2149 if (ExportSummary && isa<MDString>(
S.first.TypeID)) {
2152 for (
auto FS :
S.second.CSInfo.SummaryTypeCheckedLoadUsers)
2153 FS->addTypeTest(GUID);
2154 for (
auto &CCS :
S.second.ConstCSInfo)
2155 for (
auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
2156 FS->addTypeTest(GUID);
2160 if (RemarksEnabled) {
2162 for (
const auto &DT : DevirtTargets) {
2165 using namespace ore;
2168 <<
NV(
"FunctionName", DT.first));
2172 removeRedundantTypeTests();
2176 if (DidVirtualConstProp)
2184 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2189 void DevirtIndex::run() {
2190 if (ExportSummary.typeIdCompatibleVtableMap().empty())
2194 for (
auto &
P : ExportSummary.typeIdCompatibleVtableMap()) {
2199 for (
auto &
P : ExportSummary) {
2200 for (
auto &
S :
P.second.SummaryList) {
2201 auto *
FS = dyn_cast<FunctionSummary>(
S.get());
2207 CallSlots[{
Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(
FS);
2212 CallSlots[{
Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(
FS);
2216 FS->type_test_assume_const_vcalls()) {
2218 CallSlots[{
Name,
VC.VFunc.Offset}]
2219 .ConstCSInfo[
VC.Args]
2220 .addSummaryTypeTestAssumeUser(
FS);
2224 FS->type_checked_load_const_vcalls()) {
2226 CallSlots[{
Name,
VC.VFunc.Offset}]
2227 .ConstCSInfo[
VC.Args]
2228 .addSummaryTypeCheckedLoadUser(
FS);
2234 std::set<ValueInfo> DevirtTargets;
2236 for (
auto &
S : CallSlots) {
2240 std::vector<ValueInfo> TargetsForSlot;
2241 auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(
S.first.TypeID);
2247 &ExportSummary.getOrInsertTypeIdSummary(
S.first.TypeID)
2248 .WPDRes[
S.first.ByteOffset];
2249 if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
2250 S.first.ByteOffset)) {
2252 if (!trySingleImplDevirt(TargetsForSlot,
S.first,
S.second, Res,
2261 for (
const auto &DT : DevirtTargets)
2262 errs() <<
"Devirtualized call to " << DT <<
"\n";