LLVM: lib/Transforms/IPO/WholeProgramDevirt.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
114#include
115#include
116#include
117#include
118#include
119#include
120
121using namespace llvm;
123
124#define DEBUG_TYPE "wholeprogramdevirt"
125
126STATISTIC(NumDevirtTargets, "Number of whole program devirtualization targets");
127STATISTIC(NumSingleImpl, "Number of single implementation devirtualizations");
128STATISTIC(NumBranchFunnel, "Number of branch funnels");
129STATISTIC(NumUniformRetVal, "Number of uniform return value optimizations");
130STATISTIC(NumUniqueRetVal, "Number of unique return value optimizations");
132 "Number of 1 bit virtual constant propagations");
133STATISTIC(NumVirtConstProp, "Number of virtual constant propagations");
135 "Controls how many calls should be devirtualized.");
136
137namespace llvm {
138
140 "wholeprogramdevirt-summary-action",
141 cl::desc("What to do with the summary when running this pass"),
144 "Import typeid resolutions from summary and globals"),
146 "Export typeid resolutions to summary and globals")),
148
150 "wholeprogramdevirt-read-summary",
152 "Read summary from given bitcode or YAML file before running pass"),
154
156 "wholeprogramdevirt-write-summary",
157 cl::desc("Write summary to given bitcode or YAML file after running pass. "
158 "Output file format is deduced from extension: *.bc means writing "
159 "bitcode, otherwise YAML"),
161
162
163
165 "devirtualize-speculatively",
166 cl::desc("Enable speculative devirtualization optimization"),
168
172 cl::desc("Maximum number of call targets per "
173 "call site to enable branch funnels"));
174
177 cl::desc("Print index-based devirtualization messages"));
178
179
180
181
182
185 cl::desc("Enable whole program visibility"));
186
187
188
190 "disable-whole-program-visibility", cl::Hidden,
191 cl::desc("Disable whole program visibility (overrides enabling options)"));
192
193
196 cl::desc("Prevent function(s) from being devirtualized"),
198
200
201}
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
221 "wholeprogramdevirt-keep-unreachable-function",
222 cl::desc("Regard unreachable functions as possible devirtualize targets."),
224
225
226
227
228
229
232 "wholeprogramdevirt-check", cl::Hidden,
233 cl::desc("Type of checking for incorrect devirtualizations"),
237 "Fallback to indirect when incorrect")));
238
239namespace {
240struct PatternList {
241 std::vector Patterns;
242 template void init(const T &StringList) {
243 for (const auto &S : StringList)
245 Patterns.push_back(std::move(*Pat));
246 }
247 bool match(StringRef S) {
248 for (const GlobPattern &P : Patterns)
249 if (P.match(S))
250 return true;
251 return false;
252 }
253};
254}
255
256
257
258
262
265 if (IsAfter)
266 MinByte = std::max(MinByte, Target.minAfterBytes());
267 else
268 MinByte = std::max(MinByte, Target.minBeforeBytes());
269 }
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291 std::vector<ArrayRef<uint8_t>> Used;
294 : Target.TM->Bits->Before.BytesUsed;
296 : MinByte - Target.minBeforeBytes();
297
298
299
302 }
303
304 if (Size == 1) {
305
306 for (unsigned I = 0;; ++I) {
308 for (auto &&B : Used)
311 if (BitsUsed != 0xff)
313 }
314 } else {
315
316
317 for (unsigned I = 0;; ++I) {
318 for (auto &&B : Used) {
319 unsigned Byte = 0;
320 while ((I + Byte) < B.size() && Byte < (Size / 8)) {
322 goto NextI;
323 ++Byte;
324 }
325 }
326
327
329 NextI:;
330 }
331 }
332}
333
336 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
338 OffsetByte = -(AllocBefore / 8 + 1);
339 else
340 OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
341 OffsetBit = AllocBefore % 8;
342
345 Target.setBeforeBit(AllocBefore);
346 else
347 Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
348 }
349}
350
353 unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
355 OffsetByte = AllocAfter / 8;
356 else
357 OffsetByte = (AllocAfter + 7) / 8;
358 OffsetBit = AllocAfter % 8;
359
362 Target.setAfterBit(AllocAfter);
363 else
364 Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
365 }
366}
367
372
373namespace {
374
375
376
377
378struct VTableSlot {
381};
382
383}
384
398 static bool isEqual(const VTableSlot &LHS,
399 const VTableSlot &RHS) {
400 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
401 }
402};
403
419 return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
420 }
421};
422
423
424
425
426
427
428
429
432 return false;
433
434 if ((!TheFnVI) || TheFnVI.getSummaryList().empty()) {
435
436
437 return false;
438 }
439
440 for (const auto &Summary : TheFnVI.getSummaryList()) {
441
442
443 if (!Summary->isLive())
444 return false;
446 if (!FS->fflags().MustBeUnreachable)
447 return false;
448 }
449
450 else
451 return false;
452 }
453
454
455 return true;
456}
457
458namespace {
459
460
461struct VirtualCallSite {
463 CallBase &CB;
464
465
466
467
468 unsigned *NumUnsafeUses = nullptr;
469
470 void
471 emitRemark(const StringRef OptName, const StringRef TargetName,
472 function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter) {
476
477 using namespace ore;
478 OREGetter(*F).emit(OptimizationRemark(DEBUG_TYPE, OptName, DLoc, Block)
479 << NV("Optimization", OptName)
480 << ": devirtualized a call to "
481 << NV("FunctionName", TargetName));
482 }
483
484 void replaceAndErase(
485 const StringRef OptName, const StringRef TargetName, bool RemarksEnabled,
486 function_ref<OptimizationRemarkEmitter &(Function &)> OREGetter,
488 if (RemarksEnabled)
489 emitRemark(OptName, TargetName, OREGetter);
493 II->getUnwindDest()->removePredecessor(II->getParent());
494 }
496
497 if (NumUnsafeUses)
498 --*NumUnsafeUses;
499 }
500};
501
502
503
504
506
507
508
509
510 std::vector CallSites;
511
512
513
514
515
516
517
518
519 bool AllCallSitesDevirted = true;
520
521
522
523
524
525
526
527
528 std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
529
530
531
532 std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
533
534 bool isExported() const {
535 return !SummaryTypeCheckedLoadUsers.empty() ||
536 !SummaryTypeTestAssumeUsers.empty();
537 }
538
539 void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
540 SummaryTypeCheckedLoadUsers.push_back(FS);
541 AllCallSitesDevirted = false;
542 }
543
544 void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
545 SummaryTypeTestAssumeUsers.push_back(FS);
546 AllCallSitesDevirted = false;
547 }
548
549 void markDevirt() { AllCallSitesDevirted = true; }
550};
551
552
553struct VTableSlotInfo {
554
555
557
558
559
560 std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
561
562 void addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses);
563
564private:
565 CallSiteInfo &findCallSiteInfo(CallBase &CB);
566};
567
568CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) {
569 std::vector<uint64_t> Args;
571 if (!CBType || CBType->getBitWidth() > 64 || CB.arg_empty())
572 return CSInfo;
575 if (!CI || CI->getBitWidth() > 64)
576 return CSInfo;
577 Args.push_back(CI->getZExtValue());
578 }
579 return ConstCSInfo[Args];
580}
581
582void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB,
583 unsigned *NumUnsafeUses) {
584 auto &CSI = findCallSiteInfo(CB);
585 CSI.AllCallSitesDevirted = false;
586 CSI.CallSites.push_back({VTable, CB, NumUnsafeUses});
587}
588
589struct DevirtModule {
593
594 ModuleSummaryIndex *const ExportSummary;
595 const ModuleSummaryIndex *const ImportSummary;
596
597 IntegerType *const Int8Ty;
599 IntegerType *const Int32Ty;
600 IntegerType *const Int64Ty;
601 IntegerType *const IntPtrTy;
602
603
604
606
607 const bool RemarksEnabled;
608 std::function<OptimizationRemarkEmitter &(Function &)> OREGetter;
609 MapVector<VTableSlot, VTableSlotInfo> CallSlots;
610
611
612
613
614 SmallPtrSet<CallBase *, 8> OptimizedCalls;
615
616
617
619
620
621
622
623
624
625
626
627
628 std::map<CallInst *, unsigned> NumUnsafeUsesForTypeTest;
629 PatternList FunctionsToSkip;
630
631 const bool DevirtSpeculatively;
633 ModuleSummaryIndex *ExportSummary,
634 const ModuleSummaryIndex *ImportSummary,
635 bool DevirtSpeculatively)
638 ExportSummary(ExportSummary), ImportSummary(ImportSummary),
643 IntPtrTy(M.getDataLayout().getIntPtrType(M.getContext(), 0)),
645 RemarksEnabled(areRemarksEnabled()),
646 OREGetter([&](Function &F) -> OptimizationRemarkEmitter & {
648 }),
649 DevirtSpeculatively(DevirtSpeculatively) {
650 assert(!(ExportSummary && ImportSummary));
652 }
653
654 bool areRemarksEnabled();
655
656 void
657 scanTypeTestUsers(Function *TypeTestFunc,
658 DenseMap<Metadata *, std::set> &TypeIdMap);
659 void scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc);
660
661 void buildTypeIdentifierMap(
662 std::vector &Bits,
663 DenseMap<Metadata *, std::set> &TypeIdMap);
664
665 bool
666 tryFindVirtualCallTargets(std::vector &TargetsForSlot,
667 const std::set &TypeMemberInfos,
668 uint64_t ByteOffset,
669 ModuleSummaryIndex *ExportSummary);
670
671 void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
672 bool &IsExported);
673 bool trySingleImplDevirt(ModuleSummaryIndex *ExportSummary,
675 VTableSlotInfo &SlotInfo,
676 WholeProgramDevirtResolution *Res);
677
678 void applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Function &JT,
679 bool &IsExported);
681 VTableSlotInfo &SlotInfo,
682 WholeProgramDevirtResolution *Res, VTableSlot Slot);
683
684 bool tryEvaluateFunctionsWithArgs(
686 ArrayRef<uint64_t> Args);
687
688 void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
689 uint64_t TheRetVal);
692 WholeProgramDevirtResolution::ByArg *Res);
693
694
695
696 std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
697 StringRef Name);
698
699 bool shouldExportConstantsAsAbsoluteSymbols();
700
701
702
703
704 void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
705 Constant *C);
706 void exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
707 uint32_t Const, uint32_t &Storage);
708
709
710
711 Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
712 StringRef Name);
713 Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
714 StringRef Name, IntegerType *IntTy,
715 uint32_t Storage);
716
717 Constant *getMemberAddr(const TypeMemberInfo *M);
718
719 void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
720 Constant *UniqueMemberAddr);
721 bool tryUniqueRetValOpt(unsigned BitWidth,
724 WholeProgramDevirtResolution::ByArg *Res,
725 VTableSlot Slot, ArrayRef<uint64_t> Args);
726
727 void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
728 Constant *Byte, Constant *Bit);
730 VTableSlotInfo &SlotInfo,
731 WholeProgramDevirtResolution *Res, VTableSlot Slot);
732
733 void rebuildGlobal(VTableBits &B);
734
735
736 void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
737
738
739
740 void removeRedundantTypeTests();
741
742 bool run();
743
744
745
746
747 static ValueInfo lookUpFunctionValueInfo(Function *TheFn,
748 ModuleSummaryIndex *ExportSummary);
749
750
751
752
753
754
755
756
757
759 ModuleSummaryIndex *ExportSummary);
760
761
762
764 bool DevirtSpeculatively);
765};
766
767struct DevirtIndex {
768 ModuleSummaryIndex &ExportSummary;
769
770
771 std::setGlobalValue::GUID &ExportedGUIDs;
772
773
774
775 std::map<ValueInfo, std::vector> &LocalWPDTargetsMap;
776
777 MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;
778
779 PatternList FunctionsToSkip;
780
781 DevirtIndex(
782 ModuleSummaryIndex &ExportSummary,
783 std::setGlobalValue::GUID &ExportedGUIDs,
784 std::map<ValueInfo, std::vector> &LocalWPDTargetsMap)
785 : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
786 LocalWPDTargetsMap(LocalWPDTargetsMap) {
788 }
789
790 bool tryFindVirtualCallTargets(std::vector &TargetsForSlot,
792 uint64_t ByteOffset);
793
795 VTableSlotSummary &SlotSummary,
796 VTableSlotInfo &SlotInfo,
797 WholeProgramDevirtResolution *Res,
798 std::set &DevirtTargets);
799
800 void run();
801};
802}
803
810 }
811
812 std::optional Index;
814
816 "ExportSummary is expected to be empty in non-LTO mode");
819 ExportSummary = Index.has_value() ? &Index.value() : nullptr;
820 }
825}
826
827
828
833
834static bool
837
838
839
840 if (TypeID.ends_with(".virtual"))
841 return false;
842
843
844
845
846 if (.consume_front("_ZTS"))
847 return false;
848
849
850
851
852
853
854 std::string TypeInfo = ("_ZTI" + TypeID).str();
855 return IsVisibleToRegularObj(TypeInfo);
856}
857
858static bool
862 GV.getMetadata(LLVMContext::MD_type, Types);
863
864 for (auto *Type : Types)
867 IsVisibleToRegularObj);
868
869 return false;
870}
871
872
873
874
876 Module &M, bool WholeProgramVisibilityEnabledInLTO,
878 bool ValidateAllVtablesHaveTypeInfos,
881 return;
883
884
885
886 if (GV.hasMetadata(LLVMContext::MD_type) &&
888
889
891
892
893
894
895 !(ValidateAllVtablesHaveTypeInfos &&
898 }
899}
900
902 bool WholeProgramVisibilityEnabledInLTO) {
904 Function *PublicTypeTestFunc =
906 if (!PublicTypeTestFunc)
907 return;
914 TypeTestFunc, {CI->getArgOperand(0), CI->getArgOperand(1)}, {}, "",
916 CI->replaceAllUsesWith(NewCI);
917 CI->eraseFromParent();
918 }
919 } else {
920
921
925 CI->replaceAllUsesWith(True);
926 CI->eraseFromParent();
927 }
928 }
929}
930
931
932
937 for (const auto &TypeID : Index.typeIdCompatibleVtableMap()) {
940 VisibleToRegularObjSymbols.insert(P.VTableVI.getGUID());
941 }
942}
943
944
945
946
952 return;
953 for (auto &P : Index) {
954
955
956 if (DynamicExportSymbols.count(P.first))
957 continue;
958
959
960
961
962 if (VisibleToRegularObjSymbols.count(P.first))
963 continue;
964 for (auto &S : P.second.getSummaryList()) {
966 if (!GVar ||
968 continue;
970 }
971 }
972}
973
975 ModuleSummaryIndex &Summary, std::setGlobalValue::GUID &ExportedGUIDs,
976 std::map<ValueInfo, std::vector> &LocalWPDTargetsMap) {
977 DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
978}
979
983 std::map<ValueInfo, std::vector> &LocalWPDTargetsMap) {
984 for (auto &T : LocalWPDTargetsMap) {
985 auto &VI = T.first;
986
987 assert(VI.getSummaryList().size() == 1 &&
988 "Devirt of local target has more than one copy");
989 auto &S = VI.getSummaryList()[0];
990 if (!IsExported(S->modulePath(), VI))
991 continue;
992
993
994 for (auto &SlotSummary : T.second) {
995 auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
997 auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
998 assert(WPDRes != TIdSum->WPDRes.end());
1000 WPDRes->second.SingleImplName,
1001 Summary.getModuleHash(S->modulePath()));
1002 }
1003 }
1004}
1005
1007
1008
1009
1010
1011 const auto &ModPaths = Summary->modulePaths();
1016 "combined summary should contain Regular LTO module");
1018}
1019
1021 bool DevirtSpeculatively) {
1022 std::unique_ptr Summary =
1023 std::make_unique(false);
1024
1025
1026
1028 ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary +
1029 ": ");
1030 auto ReadSummaryFile =
1032 if (Expected<std::unique_ptr> SummaryOrErr =
1034 Summary = std::move(*SummaryOrErr);
1036 } else {
1037
1039 yaml::Input In(ReadSummaryFile->getBuffer());
1042 }
1043 }
1044
1046 DevirtModule(M, MAM,
1048 : nullptr,
1050 : nullptr,
1051 DevirtSpeculatively)
1052 .run();
1053
1055 ExitOnError ExitOnErr(
1056 "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": ");
1057 std::error_code EC;
1062 } else {
1065 yaml::Output Out(OS);
1067 }
1068 }
1069
1071}
1072
1073void DevirtModule::buildTypeIdentifierMap(
1074 std::vector &Bits,
1075 DenseMap<Metadata *, std::set> &TypeIdMap) {
1076 DenseMap<GlobalVariable *, VTableBits *> GVToBits;
1077 Bits.reserve(M.global_size());
1079 for (GlobalVariable &GV : M.globals()) {
1081 GV.getMetadata(LLVMContext::MD_type, Types);
1083 continue;
1084
1085 VTableBits *&BitsPtr = GVToBits[&GV];
1086 if (!BitsPtr) {
1087 Bits.emplace_back();
1088 Bits.back().GV = &GV;
1089 Bits.back().ObjectSize =
1091 BitsPtr = &Bits.back();
1092 }
1093
1094 for (MDNode *Type : Types) {
1095 auto *TypeID = Type->getOperand(1).get();
1096
1100 ->getZExtValue();
1101
1102 TypeIdMap[TypeID].insert({BitsPtr, Offset});
1103 }
1104 }
1105}
1106
1107bool DevirtModule::tryFindVirtualCallTargets(
1108 std::vector &TargetsForSlot,
1109 const std::set &TypeMemberInfos, uint64_t ByteOffset,
1110 ModuleSummaryIndex *ExportSummary) {
1112 if (!TM.Bits->GV->isConstant())
1113 return false;
1114
1115
1116
1117 if (!DevirtSpeculatively && TM.Bits->GV->getVCallVisibility() ==
1119 return false;
1120
1123 std::tie(Fn, C) =
1125
1126 if (!Fn)
1127 return false;
1128
1129 if (FunctionsToSkip.match(Fn->getName()))
1130 return false;
1131
1132
1133
1134 if (Fn->getName() == "__cxa_pure_virtual")
1135 continue;
1136
1137
1138
1141 continue;
1142
1143
1144
1146 continue;
1147
1148
1149
1152 TargetsForSlot.push_back({GV, &TM});
1153 }
1154
1155
1156 return !TargetsForSlot.empty();
1157}
1158
1159bool DevirtIndex::tryFindVirtualCallTargets(
1160 std::vector &TargetsForSlot,
1162 for (const TypeIdOffsetVtableInfo &P : TIdInfo) {
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173 if (P.VTableVI.hasLocal() && P.VTableVI.getSummaryList().size() > 1)
1174 return false;
1175 const GlobalVarSummary *VS = nullptr;
1176 for (const auto &S : P.VTableVI.getSummaryList()) {
1178 if (!CurVS->vTableFuncs().empty() ||
1179
1180
1181
1182
1183
1184
1185
1187 VS = CurVS;
1188
1189
1191 return false;
1192 break;
1193 }
1194 }
1195
1196
1197 if (!VS)
1198 return false;
1199 if (->isLive())
1200 continue;
1201 for (auto VTP : VS->vTableFuncs()) {
1202 if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
1203 continue;
1204
1206 continue;
1207
1208 TargetsForSlot.push_back(VTP.FuncVI);
1209 }
1210 }
1211
1212
1213 return !TargetsForSlot.empty();
1214}
1215
1216void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
1217 Constant *TheFn, bool &IsExported) {
1218
1219
1221 return;
1223 for (auto &&VCallSite : CSInfo.CallSites) {
1224 if (!OptimizedCalls.insert(&VCallSite.CB).second)
1225 continue;
1226
1227
1229 continue;
1230
1231 if (RemarksEnabled)
1232 VCallSite.emitRemark("single-impl",
1234 NumSingleImpl++;
1235 auto &CB = VCallSite.CB;
1240
1241
1242
1243
1247 Cond, &CB, false,
1248 MDBuilder(M.getContext()).createUnlikelyBranchWeights());
1249 Builder.SetInsertPoint(ThenTerm);
1252 auto *CallTrap = Builder.CreateCall(TrapFn);
1253 CallTrap->setDebugLoc(CB.getDebugLoc());
1254 }
1255
1256
1257
1258
1259
1261 MDNode *Weights = MDBuilder(M.getContext()).createLikelyBranchWeights();
1262
1263
1264
1265 CallBase &NewInst = versionCallSite(CB, Callee, Weights);
1267
1268
1269
1270 NewInst.setMetadata(LLVMContext::MD_prof, nullptr);
1271 NewInst.setMetadata(LLVMContext::MD_callees, nullptr);
1272
1273
1274 CB.setMetadata(LLVMContext::MD_prof, nullptr);
1275 CB.setMetadata(LLVMContext::MD_callees, nullptr);
1276 }
1277
1278
1279 else {
1280
1282
1283
1284
1285 CB.setMetadata(LLVMContext::MD_prof, nullptr);
1286 CB.setMetadata(LLVMContext::MD_callees, nullptr);
1292
1293 CallsWithPtrAuthBundleRemoved.push_back(&CB);
1294 }
1295 }
1296
1297
1298 if (VCallSite.NumUnsafeUses)
1299 --*VCallSite.NumUnsafeUses;
1300 }
1301 if (CSInfo.isExported())
1302 IsExported = true;
1303 CSInfo.markDevirt();
1304 };
1305 Apply(SlotInfo.CSInfo);
1306 for (auto &P : SlotInfo.ConstCSInfo)
1307 Apply(P.second);
1308}
1309
1311
1312 if (Callee.getSummaryList().empty())
1313 return false;
1314
1315
1316
1317
1318
1319 bool IsExported = false;
1320 auto &S = Callee.getSummaryList()[0];
1322 0);
1323 auto AddCalls = [&](CallSiteInfo &CSInfo) {
1324 for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
1325 FS->addCall({Callee, CI});
1326 IsExported |= S->modulePath() != FS->modulePath();
1327 }
1328 for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
1329 FS->addCall({Callee, CI});
1330 IsExported |= S->modulePath() != FS->modulePath();
1331 }
1332 };
1333 AddCalls(SlotInfo.CSInfo);
1334 for (auto &P : SlotInfo.ConstCSInfo)
1335 AddCalls(P.second);
1336 return IsExported;
1337}
1338
1339bool DevirtModule::trySingleImplDevirt(
1340 ModuleSummaryIndex *ExportSummary,
1342 WholeProgramDevirtResolution *Res) {
1343
1344
1345 auto *TheFn = TargetsForSlot[0].Fn;
1346 for (auto &&Target : TargetsForSlot)
1347 if (TheFn != Target.Fn)
1348 return false;
1349
1350
1352 TargetsForSlot[0].WasDevirt = true;
1353
1354 bool IsExported = false;
1355 applySingleImplDevirt(SlotInfo, TheFn, IsExported);
1356 if (!IsExported)
1357 return false;
1358
1359
1360
1361
1362 if (TheFn->hasLocalLinkage()) {
1363 std::string NewName = (TheFn->getName() + ".llvm.merged").str();
1364
1365
1366
1367
1368 if (Comdat *C = TheFn->getComdat()) {
1369 if (C->getName() == TheFn->getName()) {
1370 Comdat *NewC = M.getOrInsertComdat(NewName);
1372 for (GlobalObject &GO : M.global_objects())
1373 if (GO.getComdat() == C)
1374 GO.setComdat(NewC);
1375 }
1376 }
1377
1380 TheFn->setName(NewName);
1381 }
1382 if (ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFn->getGUID()))
1383
1384
1385 addCalls(SlotInfo, TheFnVI);
1386
1389
1390 return true;
1391}
1392
1394 VTableSlotSummary &SlotSummary,
1395 VTableSlotInfo &SlotInfo,
1396 WholeProgramDevirtResolution *Res,
1397 std::set &DevirtTargets) {
1398
1399
1400 auto TheFn = TargetsForSlot[0];
1401 for (auto &&Target : TargetsForSlot)
1402 if (TheFn != Target)
1403 return false;
1404
1405
1406 auto Size = TheFn.getSummaryList().size();
1408 return false;
1409
1410
1411
1412 if (FunctionsToSkip.match(TheFn.name()))
1413 return false;
1414
1415
1416
1417 if (TheFn.hasLocal() && Size > 1)
1418 return false;
1419
1420
1422 DevirtTargets.insert(TheFn);
1423
1424 auto &S = TheFn.getSummaryList()[0];
1425 bool IsExported = addCalls(SlotInfo, TheFn);
1426 if (IsExported)
1427 ExportedGUIDs.insert(TheFn.getGUID());
1428
1429
1430
1433 if (IsExported)
1434
1435
1436
1438 TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
1439 else {
1440 LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
1442 }
1443 } else
1445
1446
1447
1448
1450
1451 return true;
1452}
1453
1454void DevirtModule::tryICallBranchFunnel(
1456 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1457 Triple T(M.getTargetTriple());
1459 return;
1460
1462 return;
1463
1464 bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
1465 if (!HasNonDevirt)
1466 for (auto &P : SlotInfo.ConstCSInfo)
1467 if (.second.AllCallSitesDevirted) {
1468 HasNonDevirt = true;
1469 break;
1470 }
1471
1472 if (!HasNonDevirt)
1473 return;
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486 for (auto &T : TargetsForSlot) {
1487 if (T.TM->Bits->GV->hasAvailableExternallyLinkage())
1488 return;
1489 }
1490
1491 FunctionType *FT =
1496 M.getDataLayout().getProgramAddressSpace(),
1497 getGlobalName(Slot, {}, "branch_funnel"), &M);
1499 } else {
1501 M.getDataLayout().getProgramAddressSpace(),
1502 "branch_funnel", &M);
1503 }
1504 JT->addParamAttr(0, Attribute::Nest);
1505
1506 std::vector<Value *> JTArgs;
1507 JTArgs.push_back(JT->arg_begin());
1508 for (auto &T : TargetsForSlot) {
1509 JTArgs.push_back(getMemberAddr(T.TM));
1510 JTArgs.push_back(T.Fn);
1511 }
1512
1515 &M, llvm::Intrinsic::icall_branch_funnel, {});
1516
1520
1521 bool IsExported = false;
1522 applyICallBranchFunnel(SlotInfo, *JT, IsExported);
1523 if (IsExported)
1525
1526 if (->getEntryCount().has_value()) {
1527
1529 }
1530}
1531
1532void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo,
1533 Function &JT, bool &IsExported) {
1534 DenseMap<Function *, double> FunctionEntryCounts;
1536 if (CSInfo.isExported())
1537 IsExported = true;
1538 if (CSInfo.AllCallSitesDevirted)
1539 return;
1540
1541 std::map<CallBase *, CallBase *> CallBases;
1542 for (auto &&VCallSite : CSInfo.CallSites) {
1543 CallBase &CB = VCallSite.CB;
1544
1545 if (CallBases.find(&CB) != CallBases.end()) {
1546
1547
1548
1549
1550
1551 continue;
1552 }
1553
1554
1556 if (!FSAttr.isValid() ||
1558 continue;
1559
1560 NumBranchFunnel++;
1561 if (RemarksEnabled)
1562 VCallSite.emitRemark("branch-funnel", JT.getName(), OREGetter);
1563
1564
1565
1566 std::vector<Type *> NewArgs;
1567 NewArgs.push_back(Int8PtrTy);
1569 FunctionType *NewFT =
1573 std::vector<Value *> Args;
1574 Args.push_back(VCallSite.VTable);
1576
1577 CallBase *NewCS = nullptr;
1579
1580
1582 auto &BFI = FAM.getResult(F);
1583 auto EC = BFI.getBlockFreq(&F.getEntryBlock());
1584 auto CC = F.getEntryCount(true);
1585 double CallCount = 0.0;
1586 if (EC.getFrequency() != 0 && CC && CC->getCount() != 0) {
1587 double CallFreq =
1588 static_cast<double>(
1589 BFI.getBlockFreq(CB.getParent()).getFrequency()) /
1590 EC.getFrequency();
1591 CallCount = CallFreq * CC->getCount();
1592 }
1593 FunctionEntryCounts[&JT] += CallCount;
1594 }
1596 NewCS = IRB.CreateCall(NewFT, &JT, Args);
1597 else
1598 NewCS =
1599 IRB.CreateInvoke(NewFT, &JT, cast(CB).getNormalDest(),
1602
1604 std::vector NewArgAttrs;
1607 M.getContext(), Attribute::Nest)}));
1608 for (unsigned I = 0; I + 2 < Attrs.getNumAttrSets(); ++I)
1609 NewArgAttrs.push_back(Attrs.getParamAttrs(I));
1611 AttributeList::get(M.getContext(), Attrs.getFnAttrs(),
1612 Attrs.getRetAttrs(), NewArgAttrs));
1613
1614 CallBases[&CB] = NewCS;
1615
1616
1617 if (VCallSite.NumUnsafeUses)
1618 --*VCallSite.NumUnsafeUses;
1619 }
1620
1621
1622
1623
1624
1625 for (auto &[Old, New] : CallBases) {
1626 Old->replaceAllUsesWith(New);
1627 Old->eraseFromParent();
1628 }
1629 };
1630 Apply(SlotInfo.CSInfo);
1631 for (auto &P : SlotInfo.ConstCSInfo)
1632 Apply(P.second);
1633 for (auto &[F, C] : FunctionEntryCounts) {
1634 assert(->getEntryCount(true) &&
1635 "Unexpected entry count for funnel that was freshly synthesized");
1636 F->setEntryCount(static_cast<uint64_t>(std::round(C)));
1637 }
1638}
1639
1640bool DevirtModule::tryEvaluateFunctionsWithArgs(
1642 ArrayRef<uint64_t> Args) {
1643
1644
1646
1647
1648
1650 if (!Fn)
1651 return false;
1652
1654 return false;
1655
1656 Evaluator Eval(M.getDataLayout(), nullptr);
1660 for (unsigned I = 0; I != Args.size(); ++I) {
1661 auto *ArgTy =
1663 if (!ArgTy)
1664 return false;
1665 EvalArgs.push_back(ConstantInt::get(ArgTy, Args[I]));
1666 }
1667
1669 if (!Eval.EvaluateFunction(Fn, RetVal, EvalArgs) ||
1671 return false;
1673 }
1674 return true;
1675}
1676
1677void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1678 uint64_t TheRetVal) {
1679 for (auto Call : CSInfo.CallSites) {
1680 if (!OptimizedCalls.insert(&Call.CB).second)
1681 continue;
1682 NumUniformRetVal++;
1683 Call.replaceAndErase(
1684 "uniform-ret-val", FnName, RemarksEnabled, OREGetter,
1686 }
1687 CSInfo.markDevirt();
1688}
1689
1690bool DevirtModule::tryUniformRetValOpt(
1692 WholeProgramDevirtResolution::ByArg *Res) {
1693
1694
1695 uint64_t TheRetVal = TargetsForSlot[0].RetVal;
1697 if (Target.RetVal != TheRetVal)
1698 return false;
1699
1700 if (CSInfo.isExported()) {
1702 Res->Info = TheRetVal;
1703 }
1704
1705 applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
1707 for (auto &&Target : TargetsForSlot)
1708 Target.WasDevirt = true;
1709 return true;
1710}
1711
1712std::string DevirtModule::getGlobalName(VTableSlot Slot,
1713 ArrayRef<uint64_t> Args,
1714 StringRef Name) {
1715 std::string FullName = "__typeid_";
1716 raw_string_ostream OS(FullName);
1717 OS << cast(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
1718 for (uint64_t Arg : Args)
1719 OS << '_' << Arg;
1720 OS << '_' << Name;
1721 return FullName;
1722}
1723
1724bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() {
1725 Triple T(M.getTargetTriple());
1726 return T.isX86() && T.getObjectFormat() == Triple::ELF;
1727}
1728
1729void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1730 StringRef Name, Constant *C) {
1732 getGlobalName(Slot, Args, Name), C, &M);
1734}
1735
1736void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1737 StringRef Name, uint32_t Const,
1738 uint32_t &Storage) {
1739 if (shouldExportConstantsAsAbsoluteSymbols()) {
1740 exportGlobal(
1741 Slot, Args, Name,
1743 return;
1744 }
1745
1746 Storage = Const;
1747}
1748
1749Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
1750 StringRef Name) {
1751 GlobalVariable *GV =
1752 M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Arr0Ty);
1754 return GV;
1755}
1756
1757Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
1758 StringRef Name, IntegerType *IntTy,
1759 uint32_t Storage) {
1760 if (!shouldExportConstantsAsAbsoluteSymbols())
1761 return ConstantInt::get(IntTy, Storage);
1762
1763 Constant *C = importGlobal(Slot, Args, Name);
1766
1767
1768
1769 if (GV->hasMetadata(LLVMContext::MD_absolute_symbol))
1770 return C;
1771
1772 auto SetAbsRange = [&](uint64_t Min, uint64_t Max) {
1775 GV->setMetadata(LLVMContext::MD_absolute_symbol,
1777 };
1778 unsigned AbsWidth = IntTy->getBitWidth();
1779 if (AbsWidth == IntPtrTy->getBitWidth())
1780 SetAbsRange(~0ull, ~0ull);
1781 else
1782 SetAbsRange(0, 1ull << AbsWidth);
1783 return C;
1784}
1785
1786void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
1787 bool IsOne,
1788 Constant *UniqueMemberAddr) {
1789 for (auto &&Call : CSInfo.CallSites) {
1790 if (!OptimizedCalls.insert(&Call.CB).second)
1791 continue;
1795 B.CreateBitCast(UniqueMemberAddr, Call.VTable->getType()));
1797 NumUniqueRetVal++;
1798 Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
1799 Cmp);
1800 }
1801 CSInfo.markDevirt();
1802}
1803
1806 ConstantInt::get(Int64Ty, M->Offset));
1807}
1808
1809bool DevirtModule::tryUniqueRetValOpt(
1811 CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
1812 VTableSlot Slot, ArrayRef<uint64_t> Args) {
1813
1814 auto tryUniqueRetValOptFor = [&](bool IsOne) {
1817 if (Target.RetVal == (IsOne ? 1 : 0)) {
1818 if (UniqueMember)
1819 return false;
1820 UniqueMember = Target.TM;
1821 }
1822 }
1823
1824
1825
1826 assert(UniqueMember);
1827
1828 Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
1829 if (CSInfo.isExported()) {
1831 Res->Info = IsOne;
1832
1833 exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
1834 }
1835
1836
1837 applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
1838 UniqueMemberAddr);
1839
1840
1842 for (auto &&Target : TargetsForSlot)
1843 Target.WasDevirt = true;
1844
1845 return true;
1846 };
1847
1849 if (tryUniqueRetValOptFor(true))
1850 return true;
1851 if (tryUniqueRetValOptFor(false))
1852 return true;
1853 }
1854 return false;
1855}
1856
1857void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
1858 Constant *Byte, Constant *Bit) {
1859 for (auto Call : CSInfo.CallSites) {
1860 if (!OptimizedCalls.insert(&Call.CB).second)
1861 continue;
1864 Value *Addr = B.CreatePtrAdd(Call.VTable, Byte);
1865 if (RetType->getBitWidth() == 1) {
1866 Value *Bits = B.CreateLoad(Int8Ty, Addr);
1867 Value *BitsAndBit = B.CreateAnd(Bits, Bit);
1868 auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
1869 NumVirtConstProp1Bit++;
1870 Call.replaceAndErase("virtual-const-prop-1-bit", FnName, RemarksEnabled,
1871 OREGetter, IsBitSet);
1872 } else {
1873 Value *Val = B.CreateLoad(RetType, Addr);
1874 NumVirtConstProp++;
1875 Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled,
1876 OREGetter, Val);
1877 }
1878 }
1879 CSInfo.markDevirt();
1880}
1881
1882bool DevirtModule::tryVirtualConstProp(
1884 WholeProgramDevirtResolution *Res, VTableSlot Slot) {
1885
1886
1887
1889 if (!Fn)
1890 return false;
1891
1893 if (!RetType)
1894 return false;
1895 unsigned BitWidth = RetType->getBitWidth();
1896
1897
1898
1899
1900
1901
1902
1903
1905 return false;
1906
1907 Align TypeAlignment = M.getDataLayout().getABIIntegerTypeAlignment(BitWidth);
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1920
1921
1922
1924 if (!Fn)
1925 return false;
1926
1932 return false;
1933
1934
1935
1936
1937
1938
1939
1940 GlobalVariable *GV = Target.TM->Bits->GV;
1941 Align TableAlignment = M.getDataLayout().getValueOrABITypeAlignment(
1943 if (TypeAlignment > TableAlignment)
1944 return false;
1945 }
1946
1947 for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
1948 if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
1949 continue;
1950
1951 WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
1952 if (Res)
1953 ResByArg = &Res->ResByArg[CSByConstantArg.first];
1954
1955 if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
1956 continue;
1957
1958 if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
1959 ResByArg, Slot, CSByConstantArg.first))
1960 continue;
1961
1962
1963
1964
1965
1966
1967 uint64_t AllocBefore =
1969 uint64_t AllocAfter =
1971
1972
1973
1974 uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
1975 for (auto &&Target : TargetsForSlot) {
1976 TotalPaddingBefore += std::max<int64_t>(
1977 (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
1978 TotalPaddingAfter += std::max<int64_t>(
1979 (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
1980 }
1981
1982
1983
1984 if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
1985 continue;
1986
1987
1988
1989 int64_t OffsetByte;
1990 uint64_t OffsetBit;
1991 if (TotalPaddingBefore <= TotalPaddingAfter)
1993 OffsetBit);
1994 else
1996 OffsetBit);
1997
1998
1999
2000
2001
2002
2003
2004 assert(OffsetByte % TypeAlignment.value() == 0);
2005
2007 for (auto &&Target : TargetsForSlot)
2008 Target.WasDevirt = true;
2009
2010
2011 if (CSByConstantArg.second.isExported()) {
2013 exportConstant(Slot, CSByConstantArg.first, "byte", OffsetByte,
2014 ResByArg->Byte);
2015 exportConstant(Slot, CSByConstantArg.first, "bit", 1ULL << OffsetBit,
2016 ResByArg->Bit);
2017 }
2018
2019
2020 Constant *ByteConst = ConstantInt::get(Int32Ty, OffsetByte);
2021 Constant *BitConst = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
2022 applyVirtualConstProp(CSByConstantArg.second,
2023 TargetsForSlot[0].Fn->getName(), ByteConst, BitConst);
2024 }
2025 return true;
2026}
2027
2028void DevirtModule::rebuildGlobal(VTableBits &B) {
2029 if (B.Before.Bytes.empty() && B.After.Bytes.empty())
2030 return;
2031
2032
2033
2034 Align Alignment = M.getDataLayout().getValueOrABITypeAlignment(
2035 B.GV->getAlign(), B.GV->getValueType());
2036 B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), Alignment));
2037
2038
2039 for (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I)
2041
2042
2043
2046 B.GV->getInitializer(),
2048 auto *NewGV =
2049 new GlobalVariable(M, NewInit->getType(), B.GV->isConstant(),
2051 NewGV->setSection(B.GV->getSection());
2052 NewGV->setComdat(B.GV->getComdat());
2053 NewGV->setAlignment(B.GV->getAlign());
2054
2055
2056
2057 NewGV->copyMetadata(B.GV, B.Before.Bytes.size());
2058
2059
2060
2062 B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
2064 NewInit->getType(), NewGV,
2066 ConstantInt::get(Int32Ty, 1)}),
2067 &M);
2068 Alias->setVisibility(B.GV->getVisibility());
2069 Alias->takeName(B.GV);
2070
2071 B.GV->replaceAllUsesWith(Alias);
2072 B.GV->eraseFromParent();
2073}
2074
2075bool DevirtModule::areRemarksEnabled() {
2076 const auto &FL = M.getFunctionList();
2077 for (const Function &Fn : FL) {
2079 continue;
2081 return DI.isEnabled();
2082 }
2083 return false;
2084}
2085
2086void DevirtModule::scanTypeTestUsers(
2087 Function *TypeTestFunc,
2088 DenseMap<Metadata *, std::set> &TypeIdMap) {
2089
2090
2091
2092
2093
2094
2097 if (!CI)
2098 continue;
2099
2102 auto &DT = FAM.getResult(*CI->getFunction());
2104
2107
2108 if (!Assumes.empty()) {
2109 Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
2110 for (DevirtCallSite Call : DevirtCalls)
2111 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB, nullptr);
2112 }
2113
2114 auto RemoveTypeTestAssumes = [&]() {
2115
2116 for (auto *Assume : Assumes)
2117 Assume->eraseFromParent();
2118
2119
2120 if (CI->use_empty())
2121 CI->eraseFromParent();
2122 };
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136 if (!TypeIdMap.count(TypeId))
2137 RemoveTypeTestAssumes();
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148 else if (ImportSummary && isa(TypeId)) {
2149 const TypeIdSummary *TidSummary =
2151 if (!TidSummary)
2152 RemoveTypeTestAssumes();
2153 else
2154
2155
2157 }
2158 }
2159}
2160
2161void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) {
2164
2167 if (!CI)
2168 continue;
2169
2170 Value *Ptr = CI->getArgOperand(0);
2172 Value *TypeIdValue = CI->getArgOperand(2);
2174
2178 bool HasNonCallUses = false;
2179 auto &DT = FAM.getResult(*CI->getFunction());
2181 HasNonCallUses, CI, DT);
2182
2183
2184
2185
2186
2187
2188
2190 (LoadedPtrs.size() == 1 && !HasNonCallUses) ? LoadedPtrs[0] : CI);
2191
2192 Value *LoadedValue = nullptr;
2194 Intrinsic::type_checked_load_relative) {
2196 &M, Intrinsic::load_relative, {Int32Ty});
2197 LoadedValue = LoadB.CreateCall(LoadRelFunc, {Ptr, Offset});
2198 } else {
2200 LoadedValue = LoadB.CreateLoad(Int8PtrTy, GEP);
2201 }
2202
2203 for (Instruction *LoadedPtr : LoadedPtrs) {
2204 LoadedPtr->replaceAllUsesWith(LoadedValue);
2205 LoadedPtr->eraseFromParent();
2206 }
2207
2208
2209 IRBuilder<> CallB((Preds.size() == 1 && !HasNonCallUses) ? Preds[0] : CI);
2210 CallInst *TypeTestCall = CallB.CreateCall(TypeTestFunc, {Ptr, TypeIdValue});
2211
2212 for (Instruction *Pred : Preds) {
2213 Pred->replaceAllUsesWith(TypeTestCall);
2214 Pred->eraseFromParent();
2215 }
2216
2217
2218
2219
2220
2221 if (!CI->use_empty()) {
2224 Pair = B.CreateInsertValue(Pair, LoadedValue, {0});
2225 Pair = B.CreateInsertValue(Pair, TypeTestCall, {1});
2227 }
2228
2229
2230 auto &NumUnsafeUses = NumUnsafeUsesForTypeTest[TypeTestCall];
2231 NumUnsafeUses = DevirtCalls.size();
2232
2233
2234
2235
2236 if (HasNonCallUses)
2237 ++NumUnsafeUses;
2238 for (DevirtCallSite Call : DevirtCalls) {
2239 CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CB,
2240 &NumUnsafeUses);
2241 }
2242
2243 CI->eraseFromParent();
2244 }
2245}
2246
2247void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
2249 if (!TypeId)
2250 return;
2251 const TypeIdSummary *TidSummary =
2253 if (!TidSummary)
2254 return;
2255 auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
2256 if (ResI == TidSummary->WPDRes.end())
2257 return;
2258 const WholeProgramDevirtResolution &Res = ResI->second;
2259
2262
2263
2267 .getCallee());
2268
2269
2270 bool IsExported = false;
2271 applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
2272 assert(!IsExported);
2273 }
2274
2275 for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
2276 auto I = Res.ResByArg.find(CSByConstantArg.first);
2278 continue;
2279 auto &ResByArg = I->second;
2280
2281
2282
2283
2284 switch (ResByArg.TheKind) {
2286 applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
2287 break;
2289 Constant *UniqueMemberAddr =
2290 importGlobal(Slot, CSByConstantArg.first, "unique_member");
2291 applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
2292 UniqueMemberAddr);
2293 break;
2294 }
2296 Constant *Byte = importConstant(Slot, CSByConstantArg.first, "byte",
2298 Constant *Bit = importConstant(Slot, CSByConstantArg.first, "bit", Int8Ty,
2299 ResByArg.Bit);
2300 applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
2301 break;
2302 }
2303 default:
2304 break;
2305 }
2306 }
2307
2309
2310
2312 M.getOrInsertFunction(getGlobalName(Slot, {}, "branch_funnel"),
2314 .getCallee());
2315 bool IsExported = false;
2316 applyICallBranchFunnel(SlotInfo, *JT, IsExported);
2317 assert(!IsExported);
2318 }
2319}
2320
2321void DevirtModule::removeRedundantTypeTests() {
2323 for (auto &&U : NumUnsafeUsesForTypeTest) {
2324 if (U.second == 0) {
2325 U.first->replaceAllUsesWith(True);
2326 U.first->eraseFromParent();
2327 }
2328 }
2329}
2330
2331ValueInfo
2332DevirtModule::lookUpFunctionValueInfo(Function *TheFn,
2333 ModuleSummaryIndex *ExportSummary) {
2334 assert((ExportSummary != nullptr) &&
2335 "Caller guarantees ExportSummary is not nullptr");
2336
2337 const auto TheFnGUID = TheFn->getGUID();
2338 const auto TheFnGUIDWithExportedName =
2340
2341 ValueInfo TheFnVI = ExportSummary->getValueInfo(TheFnGUID);
2342
2343
2344
2345
2346
2347
2348
2349
2350 if ((!TheFnVI) && (TheFnGUID != TheFnGUIDWithExportedName)) {
2351 TheFnVI = ExportSummary->getValueInfo(TheFnGUIDWithExportedName);
2352 }
2353 return TheFnVI;
2354}
2355
2356bool DevirtModule::mustBeUnreachableFunction(
2357 Function *const F, ModuleSummaryIndex *ExportSummary) {
2359 return false;
2360
2361 if (->isDeclaration()) {
2362
2363
2365 }
2366
2367 return ExportSummary &&
2369 DevirtModule::lookUpFunctionValueInfo(F, ExportSummary));
2370}
2371
2372bool DevirtModule::run() {
2373
2374
2375
2376
2379 return false;
2380
2381 Function *PublicTypeTestFunc = nullptr;
2382
2383
2384 if (DevirtSpeculatively)
2385 PublicTypeTestFunc =
2389 Function *TypeCheckedLoadFunc =
2392 &M, Intrinsic::type_checked_load_relative);
2395
2396
2397
2398
2399 if (!ExportSummary &&
2400 (((!PublicTypeTestFunc || PublicTypeTestFunc->use_empty()) &&
2401 (!TypeTestFunc || TypeTestFunc->use_empty())) ||
2402 !AssumeFunc || AssumeFunc->use_empty()) &&
2403 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()) &&
2404 (!TypeCheckedLoadRelativeFunc ||
2405 TypeCheckedLoadRelativeFunc->use_empty()))
2406 return false;
2407
2408
2409 std::vector Bits;
2410 DenseMap<Metadata *, std::set> TypeIdMap;
2411 buildTypeIdentifierMap(Bits, TypeIdMap);
2412
2413 if (PublicTypeTestFunc && AssumeFunc)
2414 scanTypeTestUsers(PublicTypeTestFunc, TypeIdMap);
2415
2416 if (TypeTestFunc && AssumeFunc)
2417 scanTypeTestUsers(TypeTestFunc, TypeIdMap);
2418
2419 if (TypeCheckedLoadFunc)
2420 scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
2421
2422 if (TypeCheckedLoadRelativeFunc)
2423 scanTypeCheckedLoadUsers(TypeCheckedLoadRelativeFunc);
2424
2425 if (ImportSummary) {
2426 for (auto &S : CallSlots)
2427 importResolution(S.first, S.second);
2428
2429 removeRedundantTypeTests();
2430
2431
2432
2433
2434 for (GlobalVariable &GV : M.globals())
2435 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2436
2437
2438
2439 return true;
2440 }
2441
2442 if (TypeIdMap.empty())
2443 return true;
2444
2445
2446 if (ExportSummary) {
2447 DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
2448 for (auto &P : TypeIdMap) {
2451 TypeId->getString())]
2452 .push_back(TypeId);
2453 }
2454
2455 for (auto &P : *ExportSummary) {
2456 for (auto &S : P.second.getSummaryList()) {
2458 if (!FS)
2459 continue;
2460
2461 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2462 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2463 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2464 }
2465 }
2466 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2467 for (Metadata *MD : MetadataByGUID[VF.GUID]) {
2468 CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2469 }
2470 }
2471 for (const FunctionSummary::ConstVCall &VC :
2472 FS->type_test_assume_const_vcalls()) {
2473 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2474 CallSlots[{MD, VC.VFunc.Offset}]
2475 .ConstCSInfo[VC.Args]
2476 .addSummaryTypeTestAssumeUser(FS);
2477 }
2478 }
2479 for (const FunctionSummary::ConstVCall &VC :
2480 FS->type_checked_load_const_vcalls()) {
2481 for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
2482 CallSlots[{MD, VC.VFunc.Offset}]
2483 .ConstCSInfo[VC.Args]
2484 .addSummaryTypeCheckedLoadUser(FS);
2485 }
2486 }
2487 }
2488 }
2489 }
2490
2491
2492 bool DidVirtualConstProp = false;
2493 std::map<std::string, GlobalValue *> DevirtTargets;
2494 for (auto &S : CallSlots) {
2495
2496
2497
2498 std::vector TargetsForSlot;
2499 WholeProgramDevirtResolution *Res = nullptr;
2500 const std::set &TypeMemberInfos = TypeIdMap[S.first.TypeID];
2501 if (ExportSummary && isa(S.first.TypeID) &&
2502 TypeMemberInfos.size())
2503
2504
2505
2506
2507
2508
2509 Res = &ExportSummary
2510 ->getOrInsertTypeIdSummary(
2512 .WPDRes[S.first.ByteOffset];
2513 if (tryFindVirtualCallTargets(TargetsForSlot, TypeMemberInfos,
2514 S.first.ByteOffset, ExportSummary)) {
2515 bool SingleImplDevirt =
2516 trySingleImplDevirt(ExportSummary, TargetsForSlot, S.second, Res);
2517
2518
2519
2520 if (!SingleImplDevirt && !DevirtSpeculatively) {
2521 DidVirtualConstProp |=
2522 tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
2523
2524 tryICallBranchFunnel(TargetsForSlot, S.second, Res, S.first);
2525 }
2526
2527
2529 for (const auto &T : TargetsForSlot)
2530 if (T.WasDevirt)
2531 DevirtTargets[std::string(T.Fn->getName())] = T.Fn;
2532 }
2533
2534
2535
2536
2537
2538 if (ExportSummary && isa(S.first.TypeID)) {
2541 auto AddTypeTestsForTypeCheckedLoads = [&](CallSiteInfo &CSI) {
2542 if (!CSI.AllCallSitesDevirted)
2543 for (auto *FS : CSI.SummaryTypeCheckedLoadUsers)
2544 FS->addTypeTest(GUID);
2545 };
2546 AddTypeTestsForTypeCheckedLoads(S.second.CSInfo);
2547 for (auto &CCS : S.second.ConstCSInfo)
2548 AddTypeTestsForTypeCheckedLoads(CCS.second);
2549 }
2550 }
2551
2552 if (RemarksEnabled) {
2553
2554 for (const auto &DT : DevirtTargets) {
2555 GlobalValue *GV = DT.second;
2557 if () {
2562 }
2563
2564 using namespace ore;
2565 OREGetter(*F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
2566 << "devirtualized " << NV("FunctionName", DT.first));
2567 }
2568 }
2569
2570 NumDevirtTargets += DevirtTargets.size();
2571
2572 removeRedundantTypeTests();
2573
2574
2575
2576 if (DidVirtualConstProp)
2578 rebuildGlobal(B);
2579
2580
2581
2582
2583 for (GlobalVariable &GV : M.globals())
2584 GV.eraseMetadata(LLVMContext::MD_vcall_visibility);
2585
2586 for (auto *CI : CallsWithPtrAuthBundleRemoved)
2587 CI->eraseFromParent();
2588
2589 return true;
2590}
2591
2592void DevirtIndex::run() {
2593 if (ExportSummary.typeIdCompatibleVtableMap().empty())
2594 return;
2595
2596
2597
2598 assert(!ExportSummary.withInternalizeAndPromote() &&
2599 "Expect index-based WPD to run before internalization and promotion");
2600
2601 DenseMap<GlobalValue::GUID, std::vector> NameByGUID;
2602 for (const auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
2604 P.first);
2605
2606
2607
2608
2609
2610
2611 ExportSummary.getOrInsertTypeIdSummary(P.first);
2612 }
2613
2614
2615 for (auto &P : ExportSummary) {
2616 for (auto &S : P.second.getSummaryList()) {
2618 if (!FS)
2619 continue;
2620
2621 for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
2622 for (StringRef Name : NameByGUID[VF.GUID]) {
2623 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
2624 }
2625 }
2626 for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
2627 for (StringRef Name : NameByGUID[VF.GUID]) {
2628 CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
2629 }
2630 }
2631 for (const FunctionSummary::ConstVCall &VC :
2632 FS->type_test_assume_const_vcalls()) {
2633 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2634 CallSlots[{Name, VC.VFunc.Offset}]
2635 .ConstCSInfo[VC.Args]
2636 .addSummaryTypeTestAssumeUser(FS);
2637 }
2638 }
2639 for (const FunctionSummary::ConstVCall &VC :
2640 FS->type_checked_load_const_vcalls()) {
2641 for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
2642 CallSlots[{Name, VC.VFunc.Offset}]
2643 .ConstCSInfo[VC.Args]
2644 .addSummaryTypeCheckedLoadUser(FS);
2645 }
2646 }
2647 }
2648 }
2649
2650 std::set DevirtTargets;
2651
2652 for (auto &S : CallSlots) {
2653
2654
2655
2656 std::vector TargetsForSlot;
2657 auto TidSummary = ExportSummary.getTypeIdCompatibleVtableSummary(S.first.TypeID);
2659
2660
2661 WholeProgramDevirtResolution *Res =
2662 &ExportSummary.getTypeIdSummary(S.first.TypeID)
2663 ->WPDRes[S.first.ByteOffset];
2664 if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
2665 S.first.ByteOffset)) {
2666
2667 if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
2668 DevirtTargets))
2669 continue;
2670 }
2671 }
2672
2673
2674
2676 for (const auto &DT : DevirtTargets)
2677 errs() << "Devirtualized call to " << DT << "\n";
2678
2679 NumDevirtTargets += DevirtTargets.size();
2680}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static std::optional< bool > isBigEndian(const SmallDenseMap< int64_t, int64_t, 8 > &MemOffset2Idx, int64_t LowestIdx)
Given a map from byte offsets in memory to indices in a load/store, determine if that map corresponds...
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Provides passes for computing function attributes based on interprocedural analyses.
static void emitRemark(const Function &F, OptimizationRemarkEmitter &ORE, bool Skip)
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
static cl::opt< PassSummaryAction > ClSummaryAction("lowertypetests-summary-action", cl::desc("What to do with the summary when running this pass"), cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), clEnumValN(PassSummaryAction::Import, "import", "Import typeid resolutions from summary and globals"), clEnumValN(PassSummaryAction::Export, "export", "Export typeid resolutions to summary and globals")), cl::Hidden)
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
static bool mustBeUnreachableFunction(const Function &F)
This is the interface to build a ModuleSummaryIndex for a module.
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
WPDCheckMode
Mechanism to add runtime checking of devirtualization decisions, optionally trapping or falling back ...
Definition WholeProgramDevirt.cpp:230
@ Trap
Definition WholeProgramDevirt.cpp:230
@ Fallback
Definition WholeProgramDevirt.cpp:230
@ None
Definition WholeProgramDevirt.cpp:230
static bool typeIDVisibleToRegularObj(StringRef TypeID, function_ref< bool(StringRef)> IsVisibleToRegularObj)
Definition WholeProgramDevirt.cpp:835
static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary)
Definition WholeProgramDevirt.cpp:1006
static bool addCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee)
Definition WholeProgramDevirt.cpp:1310
static cl::opt< WPDCheckMode > DevirtCheckMode("wholeprogramdevirt-check", cl::Hidden, cl::desc("Type of checking for incorrect devirtualizations"), cl::values(clEnumValN(WPDCheckMode::None, "none", "No checking"), clEnumValN(WPDCheckMode::Trap, "trap", "Trap when incorrect"), clEnumValN(WPDCheckMode::Fallback, "fallback", "Fallback to indirect when incorrect")))
static cl::opt< bool > WholeProgramDevirtKeepUnreachableFunction("wholeprogramdevirt-keep-unreachable-function", cl::desc("Regard unreachable functions as possible devirtualize targets."), cl::Hidden, cl::init(true))
With Clang, a pure virtual class's deleting destructor is emitted as a llvm.trap intrinsic followed b...
static bool skipUpdateDueToValidation(GlobalVariable &GV, function_ref< bool(StringRef)> IsVisibleToRegularObj)
Definition WholeProgramDevirt.cpp:859
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
static LLVM_ABI AttributeSet get(LLVMContext &C, const AttrBuilder &B)
LLVM_ABI StringRef getValueAsString() const
Return the attribute's value as a string.
bool isValid() const
Return true if the attribute is any kind of attribute.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
void setCallingConv(CallingConv::ID CC)
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
CallingConv::ID getCallingConv() const
Value * getCalledOperand() const
void setAttributes(AttributeList A)
Set the attributes for this call.
FunctionType * getFunctionType() const
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
void setCalledOperand(Value *V)
static LLVM_ABI CallBase * removeOperandBundle(CallBase *CB, uint32_t ID, InsertPosition InsertPt=nullptr)
Create a clone of CB with operand bundle ID removed.
AttributeList getAttributes() const
Return the attributes for this call.
LLVM_ABI Function * getCaller()
Helper to get the caller (the parent function).
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
void setSelectionKind(SelectionKind Val)
static Constant * get(LLVMContext &Context, ArrayRef< ElementTy > Elts)
get() constructor - Return a constant with array type with an element count and element type matching...
static LLVM_ABI Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList)
Create an "inbounds" getelementptr.
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, GEPNoWrapFlags NW=GEPNoWrapFlags::none(), std::optional< ConstantRange > InRange=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static Constant * getAnon(ArrayRef< Constant * > V, bool Packed=false)
Return an anonymous struct that has the specified elements.
const Constant * stripPointerCasts() const
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
static bool shouldExecute(CounterInfo &Counter)
Implements a dense probed hash-table based set.
Subclass of Error for the sole purpose of identifying the success path in the type system.
Lightweight error class with error context and mandatory checking.
Tagged union holding either a T or a Error.
Type * getParamType(unsigned i) const
Parameter type accessors.
ArrayRef< Type * > params() const
Type * getReturnType() const
static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
FunctionType * getFunctionType() const
Returns the FunctionType for me.
const BasicBlock & front() const
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Type * getReturnType() const
Returns the type of the ret val.
unsigned getInstructionCount() const
Returns the number of non-debug IR instructions in this function.
static LLVM_ABI Expected< GlobPattern > create(StringRef Pat, std::optional< size_t > MaxSubPatterns={})
static LLVM_ABI GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
bool hasMetadata() const
Return true if this value has any metadata attached to it.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set a particular kind of metadata attachment.
LLVM_ABI VCallVisibility getVCallVisibility() const
LLVM_ABI bool eraseMetadata(unsigned KindID)
Erase all metadata attachments with the given kind.
@ VCallVisibilityLinkageUnit
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
LLVM_ABI void setVCallVisibilityMetadata(VCallVisibility Visibility)
static LLVM_ABI GUID getGUIDAssumingExternalLinkage(StringRef GlobalName)
Return a 64-bit global unique ID constructed from the name of a global symbol.
static bool isLocalLinkage(LinkageTypes Linkage)
LLVM_ABI bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
@ HiddenVisibility
The GV is hidden.
void setVisibility(VisibilityTypes V)
@ PrivateLinkage
Like Internal, but omit from symbol table.
@ InternalLinkage
Rename collisions when linking (static functions).
@ ExternalLinkage
Externally visible function.
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
MaybeAlign getAlign() const
Returns the alignment of the given variable.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false, std::optional< Align > Alignment=std::nullopt)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
bool doesNotAccessMemory() const
Whether this function accesses no memory.
Class to hold module path string table and global value map, and encapsulate methods for operating on...
const TypeIdSummary * getTypeIdSummary(StringRef TypeId) const
This returns either a pointer to the type id summary (if present in the summary map) or null (if not ...
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
const ModuleHash & getModuleHash(const StringRef ModPath) const
Get the module SHA1 hash recorded for the given module path.
static constexpr const char * getRegularLTOModuleName()
bool partiallySplitLTOUnits() const
static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash)
Convenience method for creating a promoted global name for the given value name of a local,...
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Analysis providing profile information.
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, InsertPosition InsertBefore=nullptr)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
bool contains(StringRef Other) const
Return true if the given string is a substring of *this, and false otherwise.
Target - Wrapper for Target specific information.
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
The instances of the Type class are immutable: once they are created, they are never changed.
static LLVM_ABI Type * getVoidTy(LLVMContext &C)
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI bool eraseMetadata(unsigned KindID)
Erase all metadata attachments with the given kind.
iterator_range< use_iterator > uses()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
self_iterator getIterator()
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)
Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.
bool match(Val *V, const Pattern &P)
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ Assume
Do not drop type tests (default).
DiagnosticInfoOptimizationBase::Argument NV
Context & getContext() const
friend class Instruction
Iterator for Instructions in a `BasicBlock.
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
LLVM_ABI uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
Definition WholeProgramDevirt.cpp:260
LLVM_ABI void setAfterReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
Definition WholeProgramDevirt.cpp:351
LLVM_ABI void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
Definition WholeProgramDevirt.cpp:334
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
FunctionAddr VTableAddr Value
LLVM_ABI MemoryEffects computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
static cl::opt< bool > DisableWholeProgramVisibility("disable-whole-program-visibility", cl::Hidden, cl::desc("Disable whole program visibility (overrides enabling options)"))
Provide a way to force disable whole program for debugging or workarounds, when enabled via the linke...
static cl::opt< bool > WholeProgramVisibility("whole-program-visibility", cl::Hidden, cl::desc("Enable whole program visibility"))
Provide a way to force enable whole program visibility in tests.
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty
static cl::opt< unsigned > ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden, cl::init(10), cl::desc("Maximum number of call targets per " "call site to enable branch funnels"))
@ Export
Export information to summary.
@ Import
Import information from summary.
static cl::opt< std::string > ClReadSummary("wholeprogramdevirt-read-summary", cl::desc("Read summary from given bitcode or YAML file before running pass"), cl::Hidden)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
LLVM_ABI ModuleSummaryIndex buildModuleSummaryIndex(const Module &M, std::function< BlockFrequencyInfo *(const Function &F)> GetBFICallback, ProfileSummaryInfo *PSI, std::function< const StackSafetyInfo *(const Function &F)> GetSSICallback=[](const Function &F) -> const StackSafetyInfo *{ return nullptr;})
Direct function to compute a ModuleSummaryIndex from a given module.
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
LLVM_ABI bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO)
Definition WholeProgramDevirt.cpp:829
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
LLVM_ABI void writeIndexToFile(const ModuleSummaryIndex &Index, raw_ostream &Out, const ModuleToSummariesForIndexTy *ModuleToSummariesForIndex=nullptr, const GVSummaryPtrSet *DecSummaries=nullptr)
Write the specified module summary index to the given raw output stream, where it will be written in ...
LLVM_ABI Expected< std::unique_ptr< ModuleSummaryIndex > > getModuleSummaryIndex(MemoryBufferRef Buffer)
Parse the specified bitcode buffer, returning the module summary index.
static cl::opt< std::string > ClWriteSummary("wholeprogramdevirt-write-summary", cl::desc("Write summary to given bitcode or YAML file after running pass. " "Output file format is deduced from extension: *.bc means writing " "bitcode, otherwise YAML"), cl::Hidden)
LLVM_ABI void updatePublicTypeTestCalls(Module &M, bool WholeProgramVisibilityEnabledInLTO)
Definition WholeProgramDevirt.cpp:901
LLVM_ABI void getVisibleToRegularObjVtableGUIDs(ModuleSummaryIndex &Index, DenseSet< GlobalValue::GUID > &VisibleToRegularObjSymbols, function_ref< bool(StringRef)> IsVisibleToRegularObj)
Based on typeID string, get all associated vtable GUIDS that are visible to regular objects.
Definition WholeProgramDevirt.cpp:933
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void findDevirtualizableCallsForTypeCheckedLoad(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< Instruction * > &LoadedPtrs, SmallVectorImpl< Instruction * > &Preds, bool &HasNonCallUses, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.checked.load, find all devirtualizable call sites based on t...
LLVM_ABI CallBase & versionCallSite(CallBase &CB, Value *Callee, MDNode *BranchWeights)
Predicate and clone the given call site.
LLVM_ABI bool AreStatisticsEnabled()
Check if statistics are enabled.
LLVM_ABI void updateIndexWPDForExports(ModuleSummaryIndex &Summary, function_ref< bool(StringRef, ValueInfo)> isExported, std::map< ValueInfo, std::vector< VTableSlotSummary > > &LocalWPDTargetsMap)
Call after cross-module importing to update the recorded single impl devirt target names for any loca...
Definition WholeProgramDevirt.cpp:980
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI void setExplicitlyUnknownFunctionEntryCount(Function &F, StringRef PassName)
Analogous to setExplicitlyUnknownBranchWeights, but for functions and their entry counts.
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
static cl::list< std::string > SkipFunctionNames("wholeprogramdevirt-skip", cl::desc("Prevent function(s) from being devirtualized"), cl::Hidden, cl::CommaSeparated)
Provide way to prevent certain function from being devirtualized.
LLVM_ABI void runWholeProgramDevirtOnIndex(ModuleSummaryIndex &Summary, std::set< GlobalValue::GUID > &ExportedGUIDs, std::map< ValueInfo, std::vector< VTableSlotSummary > > &LocalWPDTargetsMap)
Perform index-based whole program devirtualization on the Summary index.
Definition WholeProgramDevirt.cpp:974
static cl::opt< PassSummaryAction > ClSummaryAction("wholeprogramdevirt-summary-action", cl::desc("What to do with the summary when running this pass"), cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), clEnumValN(PassSummaryAction::Import, "import", "Import typeid resolutions from summary and globals"), clEnumValN(PassSummaryAction::Export, "export", "Export typeid resolutions to summary and globals")), cl::Hidden)
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr to an Expected.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
static cl::opt< bool > ClDevirtualizeSpeculatively("devirtualize-speculatively", cl::desc("Enable speculative devirtualization optimization"), cl::init(false))
LLVM_ABI Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
std::vector< TypeIdOffsetVtableInfo > TypeIdCompatibleVtableInfo
List of vtable definitions decorated by a particular type identifier, and their corresponding offsets...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
static cl::opt< bool > PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden, cl::desc("Print index-based devirtualization messages"))
void consumeError(Error Err)
Consume a Error without doing anything.
void findDevirtualizableCallsForTypeTest(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< CallInst * > &Assumes, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.test, find all devirtualizable call sites based on the call ...
LLVM_ABI void updateVCallVisibilityInModule(Module &M, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols, bool ValidateAllVtablesHaveTypeInfos, function_ref< bool(StringRef)> IsVisibleToRegularObj)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
Definition WholeProgramDevirt.cpp:875
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
std::pair< Function *, Constant * > getFunctionAtVTableOffset(GlobalVariable *GV, uint64_t Offset, Module &M)
Given a vtable and a specified offset, returns the function and the trivial pointer at the specified ...
LLVM_ABI void updateVCallVisibilityInIndex(ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols, const DenseSet< GlobalValue::GUID > &VisibleToRegularObjSymbols)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
Definition WholeProgramDevirt.cpp:947
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
constexpr uint64_t value() const
This is a hole in the type system and should not be abused.
Class to accumulate and hold information about a callee.
static unsigned getHashValue(const VTableSlotSummary &I)
Definition WholeProgramDevirt.cpp:413
static bool isEqual(const VTableSlotSummary &LHS, const VTableSlotSummary &RHS)
Definition WholeProgramDevirt.cpp:417
static VTableSlotSummary getTombstoneKey()
Definition WholeProgramDevirt.cpp:409
static VTableSlotSummary getEmptyKey()
Definition WholeProgramDevirt.cpp:405
static VTableSlot getTombstoneKey()
Definition WholeProgramDevirt.cpp:390
static VTableSlot getEmptyKey()
Definition WholeProgramDevirt.cpp:386
static bool isEqual(const VTableSlot &LHS, const VTableSlot &RHS)
Definition WholeProgramDevirt.cpp:398
static unsigned getHashValue(const VTableSlot &I)
Definition WholeProgramDevirt.cpp:394
An information struct used to provide DenseMap with the various necessary components for a given valu...
The following data structures summarize type metadata information.
std::map< uint64_t, WholeProgramDevirtResolution > WPDRes
Mapping from byte offset to whole-program devirt resolution for that (typeid, byte offset) pair.
@ Unsat
Unsatisfiable type (i.e. no global has this type metadata)
enum llvm::TypeTestResolution::Kind TheKind
Struct that holds a reference to a particular GUID in a global value summary.
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
const ModuleSummaryIndex * ImportSummary
ModuleSummaryIndex * ExportSummary
LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition WholeProgramDevirt.cpp:804
@ UniformRetVal
Uniform return value optimization.
@ VirtualConstProp
Virtual constant propagation.
@ UniqueRetVal
Unique return value optimization.
uint64_t Info
Additional information for the resolution:
enum llvm::WholeProgramDevirtResolution::ByArg::Kind TheKind
enum llvm::WholeProgramDevirtResolution::Kind TheKind
std::map< std::vector< uint64_t >, ByArg > ResByArg
Resolutions for calls with all constant integer arguments (excluding the first argument,...
std::string SingleImplName
@ SingleImpl
Single implementation devirtualization.
@ BranchFunnel
When retpoline mitigation is enabled, use a branch funnel that is defined in the merged module.
LLVM_ABI VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM)
Definition WholeProgramDevirt.cpp:368
const TypeMemberInfo * TM