LLVM: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
15
67#include
68#include
69#include
70#include
71#include
72#include
73#include
74#include
75#include
76
77#define DEBUG_TYPE "rewrite-statepoints-for-gc"
78
79using namespace llvm;
80
81
86
87
90
91
92
96
97#ifdef EXPENSIVE_CHECKS
99#else
101#endif
102
106
110
113
114
115
116
117
118
119
120
121
122
123
124
126
127
129
131
134 bool Changed = false;
137
138 if (F.isDeclaration() || F.empty())
139 continue;
140
141
142
144 continue;
145
150 }
151 if (!Changed)
153
154
155
156
158
162 return PA;
163}
164
165namespace {
166
167struct GCPtrLivenessData {
168
170
171
172
174
175
176
178
179
180
182};
183
184
185
186
187
188
189
190
191
192
193
198using RematerializedValueMapTy =
200
201struct PartiallyConstructedSafepointRecord {
202
203 StatepointLiveSetTy LiveSet;
204
205
206
208
209
210
212
213
214
215
216 RematerializedValueMapTy RematerializedValues;
217};
218
219struct RematerizlizationCandidateRecord {
220
222
223 Value *RootOfChain;
224
226};
228
229}
230
232 std::optional DeoptBundle =
234
235 if (!DeoptBundle) {
237 "Found non-leaf call without deopt info!");
238 return {};
239 }
240
241 return DeoptBundle->Inputs;
242}
243
244
247
248
249
251 StatepointLiveSetTy &out, GCStrategy *GC);
252
254 assert(GC && "GC Strategy for isGCPointerType cannot be null");
255
256 if (!isa(T))
257 return false;
258
259
260 return GC->isGCManagedPointer(T).value_or(true);
261}
262
263
264
265
266
268
270 return true;
271
272
273 if (auto VT = dyn_cast(T))
275 return true;
276 return false;
277}
278
279#ifndef NDEBUG
280
281
284 return true;
285 if (VectorType *VT = dyn_cast(Ty))
287 if (ArrayType *AT = dyn_cast(Ty))
289 if (StructType *ST = dyn_cast(Ty))
291 [GC](Type *Ty) { return containsGCPtrType(Ty, GC); });
292 return false;
293}
294
295
296
297
300}
301#endif
302
303
304
307 return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
308}
309
310
311
312
313
316 PartiallyConstructedSafepointRecord &Result, GCStrategy *GC) {
317 StatepointLiveSetTy LiveSet;
319
321 dbgs() << "Live Variables:\n";
322 for (Value *V : LiveSet)
323 dbgs() << " " << V->getName() << " " << *V << "\n";
324 }
326 dbgs() << "Safepoint For: " << Call->getCalledOperand()->getName() << "\n";
327 dbgs() << "Number live values: " << LiveSet.size() << "\n";
328 }
329 Result.LiveSet = LiveSet;
330}
331
332
333static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases);
334
335
336
338 IsKnownBaseMapTy &KnownBases);
339
341 IsKnownBaseMapTy &KnownBases);
342
343
344
345
346
347
348
349
350
351
353 IsKnownBaseMapTy &KnownBases) {
354
355
356
357 auto Cached = Cache.find(I);
358 if (Cached != Cache.end())
359 return Cached->second;
360
361 if (isa(I)) {
362
364 setKnownBase(I, true, KnownBases);
365 return I;
366 }
367
368 if (isa(I)) {
369
370
372 Cache[I] = CAZ;
373 setKnownBase(CAZ, true, KnownBases);
374 return CAZ;
375 }
376
377 if (isa(I)) {
379 setKnownBase(I, true, KnownBases);
380 return I;
381 }
382
383 if (isa(I)) {
384
385
386
388 setKnownBase(I, false, KnownBases);
389 return I;
390 }
391
392 if (isa(I)) {
393
394
395
396
397
399 setKnownBase(I, false, KnownBases);
400 return I;
401 }
402
403
404
405 if (auto *GEP = dyn_cast(I)) {
406 auto *BDV =
408 Cache[GEP] = BDV;
409 return BDV;
410 }
411
412
413
414 if (auto *Freeze = dyn_cast(I)) {
416 Cache[Freeze] = BDV;
417 return BDV;
418 }
419
420
421
422 if (auto *BC = dyn_cast(I)) {
424 Cache[BC] = BDV;
425 return BDV;
426 }
427
428
429
430
433 setKnownBase(I, true, KnownBases);
434 return I;
435 }
436
437
438
439 assert((isa(I) || isa(I)) &&
440 "unknown vector instruction - no base found for vector element");
442 setKnownBase(I, false, KnownBases);
443 return I;
444}
445
446
447
448
449
451 IsKnownBaseMapTy &KnownBases) {
452 assert(I->getType()->isPtrOrPtrVectorTy() &&
453 "Illegal to ask for the base pointer of a non-pointer type");
454 auto Cached = Cache.find(I);
455 if (Cached != Cache.end())
456 return Cached->second;
457
458 if (I->getType()->isVectorTy())
460
461 if (isa(I)) {
462
463
465 setKnownBase(I, true, KnownBases);
466 return I;
467 }
468
469 if (isa(I)) {
470
471
472
473
474
475
476
477
478
479
481 Cache[I] = CPN;
482 setKnownBase(CPN, true, KnownBases);
483 return CPN;
484 }
485
486
487
488
489
490
491 if (isa(I)) {
493 setKnownBase(I, true, KnownBases);
494 return I;
495 }
496
497 if (CastInst *CI = dyn_cast(I)) {
498 Value *Def = CI->stripPointerCasts();
499
500
501 assert(cast(Def->getType())->getAddressSpace() ==
502 cast(CI->getType())->getAddressSpace() &&
503 "unsupported addrspacecast");
504
505
506
507 assert(!isa(Def) && "shouldn't find another cast here");
509 Cache[CI] = BDV;
510 return BDV;
511 }
512
513 if (isa(I)) {
514
516 setKnownBase(I, true, KnownBases);
517 return I;
518 }
519
521
522 auto *BDV =
524 Cache[GEP] = BDV;
525 return BDV;
526 }
527
528 if (auto *Freeze = dyn_cast(I)) {
530 Cache[Freeze] = BDV;
531 return BDV;
532 }
533
535 switch (II->getIntrinsicID()) {
536 default:
537
538 break;
539 case Intrinsic::experimental_gc_statepoint:
541 case Intrinsic::experimental_gc_relocate:
542
543
544
545 llvm_unreachable("repeat safepoint insertion is not supported");
546 case Intrinsic::gcroot:
547
548
549
551 "interaction with the gcroot mechanism is not supported");
552 case Intrinsic::experimental_gc_get_pointer_base:
554 Cache[II] = BDV;
555 return BDV;
556 }
557 }
558
559
560
563 setKnownBase(I, true, KnownBases);
564 return I;
565 }
566
567
568
569 assert(!isa(I) && "Landing Pad is unimplemented");
570
571 if (isa(I)) {
572
573
574
576 setKnownBase(I, true, KnownBases);
577 return I;
578 }
579
580 if (isa(I)) {
582 "Only Xchg is allowed for pointer values");
583
584
586 setKnownBase(I, true, KnownBases);
587 return I;
588 }
589
590
591
592
593 if (isa(I)) {
595 setKnownBase(I, true, KnownBases);
596 return I;
597 }
598
599
600
602 "Base pointer for a struct is meaningless");
603
604
605
606 bool IsKnownBase =
607 isa(I) && cast(I)->getMetadata("is_base_value");
608 setKnownBase(I, IsKnownBase, KnownBases);
610
611
612
613
614
615 if (isa(I))
616
617
618
619 return I;
620
621
622
623
624
625 assert((isa(I) || isa(I)) &&
626 "missing instruction case in findBaseDefiningValue");
627 return I;
628}
629
630
632 IsKnownBaseMapTy &KnownBases) {
633 if (!Cache.contains(I)) {
635 Cache[I] = BDV;
636 LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "
637 << Cache[I]->getName() << ", is known base = "
638 << KnownBases[I] << "\n");
639 }
640 assert(Cache[I] != nullptr);
641 assert(KnownBases.contains(Cache[I]) &&
642 "Cached value must be present in known bases map");
643 return Cache[I];
644}
645
646
647
649 IsKnownBaseMapTy &KnownBases) {
651 auto Found = Cache.find(Def);
652 if (Found != Cache.end()) {
653
654 return Found->second;
655 }
656
657 return Def;
658}
659
660#ifndef NDEBUG
661
662
664
665 return !isa(V) && !isa(V) &&
666 !isa(V) && !isa(V) &&
667 !isa(V);
668}
669#endif
670
672 auto It = KnownBases.find(V);
673 assert(It != KnownBases.end() && "Value not present in the map");
674 return It->second;
675}
676
678 IsKnownBaseMapTy &KnownBases) {
679#ifndef NDEBUG
680 auto It = KnownBases.find(V);
681 if (It != KnownBases.end())
682 assert(It->second == IsKnownBase && "Changing already present value");
683#endif
684 KnownBases[V] = IsKnownBase;
685}
686
687
689 return isa(First->getType()) ==
690 isa(Second->getType());
691}
692
693namespace {
694
695
696
697
698class BDVState {
699public:
700 enum StatusTy {
701
703
704
705
707
708 Conflict
709 };
710
711 BDVState() {
713 }
714
715 explicit BDVState(Value *OriginalValue)
716 : OriginalValue(OriginalValue) {}
717 explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr)
718 : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) {
720 }
721
722 StatusTy getStatus() const { return Status; }
723 Value *getOriginalValue() const { return OriginalValue; }
724 Value *getBaseValue() const { return BaseValue; }
725
726 bool isBase() const { return getStatus() == Base; }
727 bool isUnknown() const { return getStatus() == Unknown; }
728 bool isConflict() const { return getStatus() == Conflict; }
729
730
731
732
733 void meet(const BDVState &Other) {
734 auto markConflict = [&]() {
735 Status = BDVState::Conflict;
736 BaseValue = nullptr;
737 };
738
739 if (isConflict())
740 return;
741
742 if (isUnknown()) {
744 BaseValue = Other.getBaseValue();
745 return;
746 }
747
748 assert(isBase() && "Unknown state");
749
750 if (Other.isUnknown())
751 return;
752
753 if (Other.isConflict())
754 return markConflict();
755
756 assert(Other.isBase() && "Unknown state");
757
758 if (getBaseValue() != Other.getBaseValue())
759 return markConflict();
760
761 }
762
764 return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue &&
766 }
767
768 bool operator!=(const BDVState &other) const { return !(*this == other); }
769
771 void dump() const {
773 dbgs() << '\n';
774 }
775
777 switch (getStatus()) {
779 OS << "U";
780 break;
782 OS << "B";
783 break;
784 case Conflict:
785 OS << "C";
786 break;
787 }
788 OS << " (base " << getBaseValue() << " - "
789 << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"
790 << " for " << OriginalValue->getName() << ":";
791 }
792
793private:
794 AssertingVH OriginalValue;
796 AssertingVH BaseValue = nullptr;
797};
798
799}
800
801#ifndef NDEBUG
803 State.print(OS);
804 return OS;
805}
806#endif
807
808
809
810
811
813 IsKnownBaseMapTy &KnownBases) {
815
817 return Def;
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841#ifndef NDEBUG
842 auto isExpectedBDVType = [](Value *BDV) {
843 return isa(BDV) || isa(BDV) ||
844 isa(BDV) || isa(BDV) ||
845 isa(BDV);
846 };
847#endif
848
849
850
851
852
853
855
856#ifndef NDEBUG
857 auto VerifyStates = [&]() {
858 for (auto &Entry : States) {
859 assert(Entry.first == Entry.second.getOriginalValue());
860 }
861 };
862#endif
863
864 auto visitBDVOperands = [](Value *BDV, std::function<void (Value*)> F) {
865 if (PHINode *PN = dyn_cast(BDV)) {
866 for (Value *InVal : PN->incoming_values())
867 F(InVal);
868 } else if (SelectInst *SI = dyn_cast(BDV)) {
869 F(SI->getTrueValue());
870 F(SI->getFalseValue());
871 } else if (auto *EE = dyn_cast(BDV)) {
872 F(EE->getVectorOperand());
873 } else if (auto *IE = dyn_cast(BDV)) {
874 F(IE->getOperand(0));
875 F(IE->getOperand(1));
876 } else if (auto *SV = dyn_cast(BDV)) {
877
878
879 F(SV->getOperand(0));
880 if (!SV->isZeroEltSplat())
881 F(SV->getOperand(1));
882 } else {
884 }
885 };
886
887
888
889
890 {
893 States.insert({Def, BDVState(Def)});
894 while (!Worklist.empty()) {
897
898 auto visitIncomingValue = [&](Value *InVal) {
901
902
903
904
905
906 return;
907 assert(isExpectedBDVType(Base) && "the only non-base values "
908 "we see should be base defining values");
909 if (States.insert(std::make_pair(Base, BDVState(Base))).second)
911 };
912
913 visitBDVOperands(Current, visitIncomingValue);
914 }
915 }
916
917#ifndef NDEBUG
918 VerifyStates();
919 LLVM_DEBUG(dbgs() << "States after initialization:\n");
920 for (const auto &Pair : States) {
921 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
922 }
923#endif
924
925
926
927
928
929
931 do {
933 for (auto Pair : States) {
934 Value *BDV = Pair.first;
935 auto canPruneInput = [&](Value *V) {
936
937
938 if (V->stripPointerCasts() == BDV)
939 return true;
941 if (V->stripPointerCasts() != VBDV)
942 return false;
943
944
945 return States.count(VBDV) == 0;
946 };
947
948 bool CanPrune = true;
949 visitBDVOperands(BDV, [&](Value *Op) {
950 CanPrune = CanPrune && canPruneInput(Op);
951 });
952 if (CanPrune)
954 }
956 States.erase(V);
957
958 Cache[V] = V;
959 }
961
962
963 if (!States.count(Def))
964 return Def;
965
966
967
968 auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {
969 auto I = States.find(BaseValue);
971 return I->second;
973 return BDVState(BaseValue, BDVState::Base, BaseValue);
974 };
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
995
997 return true;
998
999
1000 if (isa(I))
1001 return true;
1002
1003
1004
1005
1006
1007
1008
1010 return true;
1011 return false;
1012 };
1013
1014 bool Progress = true;
1015 while (Progress) {
1016#ifndef NDEBUG
1017 const size_t OldSize = States.size();
1018#endif
1019 Progress = false;
1020
1021
1022
1023
1024 for (auto Pair : States) {
1025 Value *BDV = Pair.first;
1026
1027
1028
1031 "why did it get added?");
1032
1033 BDVState NewState(BDV);
1034 visitBDVOperands(BDV, [&](Value *Op) {
1036 auto OpState = GetStateForBDV(BDV, Op);
1037 NewState.meet(OpState);
1038 });
1039
1040
1041
1042
1043 auto I = cast(BDV);
1044 auto BV = NewState.getBaseValue();
1045 if (BV && MarkConflict(I, BV))
1046 NewState = BDVState(I, BDVState::Conflict);
1047
1048 BDVState OldState = Pair.second;
1049 if (OldState != NewState) {
1050 Progress = true;
1051 States[BDV] = NewState;
1052 }
1053 }
1054
1055 assert(OldSize == States.size() &&
1056 "fixed point shouldn't be adding any new nodes to state");
1057 }
1058
1059#ifndef NDEBUG
1060 VerifyStates();
1061 LLVM_DEBUG(dbgs() << "States after meet iteration:\n");
1062 for (const auto &Pair : States) {
1063 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
1064 }
1065
1066
1067
1068 for (auto Pair : States) {
1069 Instruction *I = cast(Pair.first);
1070 BDVState State = Pair.second;
1071 auto *BaseValue = State.getBaseValue();
1072
1073
1074
1077 "why did it get added?");
1078 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1079 }
1080#endif
1081
1082
1083
1084 for (auto Pair : States) {
1085 Instruction *I = cast(Pair.first);
1086 BDVState State = Pair.second;
1087
1088
1089
1092 "why did it get added?");
1093 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1094
1095
1096
1097
1098 assert(!isa(I) || State.isConflict());
1099
1100 if (!State.isConflict())
1101 continue;
1102
1103 auto getMangledName = [](Instruction *I) -> std::string {
1104 if (isa(I)) {
1106 } else if (isa(I)) {
1108 } else if (isa(I)) {
1110 } else if (isa(I)) {
1112 } else {
1114 }
1115 };
1116
1119 BaseInst->setName(getMangledName(I));
1120
1122 States[I] = BDVState(I, BDVState::Conflict, BaseInst);
1123 setKnownBase(BaseInst, true, KnownBases);
1124 }
1125
1126#ifndef NDEBUG
1127 VerifyStates();
1128#endif
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138 auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {
1141 if (!States.count(BDV)) {
1144 } else {
1145
1147 Base = States[BDV].getBaseValue();
1148 }
1150
1151 if (Base->getType() != Input->getType() && InsertPt)
1153 InsertPt->getIterator());
1154 return Base;
1155 };
1156
1157
1158
1159
1160 for (auto Pair : States) {
1161 Instruction *BDV = cast(Pair.first);
1162 BDVState State = Pair.second;
1163
1164
1165
1166
1169 "why did it get added?");
1170 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
1171 if (!State.isConflict())
1172 continue;
1173
1174 if (PHINode *BasePHI = dyn_cast(State.getBaseValue())) {
1175 PHINode *PN = cast(BDV);
1177
1178
1179
1180
1181
1183 for (unsigned i = 0; i < NumPHIValues; i++) {
1186 if (!BlockToValue.count(InBB))
1187 BlockToValue[InBB] = getBaseForInput(InVal, InBB->getTerminator());
1188 else {
1189#ifndef NDEBUG
1190 Value *OldBase = BlockToValue[InBB];
1191 Value *Base = getBaseForInput(InVal, nullptr);
1192
1193
1194
1195 auto StripBitCasts = [](Value *V) -> Value * {
1196 while (auto *BC = dyn_cast(V))
1197 V = BC->getOperand(0);
1198 return V;
1199 };
1200
1201
1202
1203
1204
1205
1206 assert(StripBitCasts(Base) == StripBitCasts(OldBase) &&
1207 "findBaseOrBDV should be pure!");
1208#endif
1209 }
1210 Value *Base = BlockToValue[InBB];
1211 BasePHI->setIncomingValue(i, Base);
1212 }
1214 dyn_cast(State.getBaseValue())) {
1215 SelectInst *SI = cast(BDV);
1216
1217
1218
1219 BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
1220 BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
1221 } else if (auto *BaseEE =
1222 dyn_cast(State.getBaseValue())) {
1223 Value *InVal = cast(BDV)->getVectorOperand();
1224
1225
1226 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1227 } else if (auto *BaseIE = dyn_cast(State.getBaseValue())){
1228 auto *BdvIE = cast(BDV);
1229 auto UpdateOperand = [&](int OperandIdx) {
1230 Value *InVal = BdvIE->getOperand(OperandIdx);
1231 Value *Base = getBaseForInput(InVal, BaseIE);
1232 BaseIE->setOperand(OperandIdx, Base);
1233 };
1234 UpdateOperand(0);
1235 UpdateOperand(1);
1236 } else {
1237 auto *BaseSV = cast(State.getBaseValue());
1238 auto *BdvSV = cast(BDV);
1239 auto UpdateOperand = [&](int OperandIdx) {
1240 Value *InVal = BdvSV->getOperand(OperandIdx);
1241 Value *Base = getBaseForInput(InVal, BaseSV);
1242 BaseSV->setOperand(OperandIdx, Base);
1243 };
1244 UpdateOperand(0);
1245 if (!BdvSV->isZeroEltSplat())
1246 UpdateOperand(1);
1247 else {
1248
1249 Value *InVal = BdvSV->getOperand(1);
1251 }
1252 }
1253 }
1254
1255#ifndef NDEBUG
1256 VerifyStates();
1257#endif
1258
1259
1260 [[maybe_unused]] auto &DL =
1261 castllvm::Instruction(Def)->getDataLayout();
1262
1263
1264
1265 for (auto Pair : States) {
1266 auto *BDV = Pair.first;
1267 Value *Base = Pair.second.getBaseValue();
1269
1270
1272 DL.getTypeAllocSize(Base->getType()) &&
1273 "Derived and base values should have same size");
1274
1275
1276
1279 "why did it get added?");
1280
1282 dbgs() << "Updating base value cache"
1283 << " for: " << BDV->getName() << " from: "
1284 << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")
1285 << " to: " << Base->getName() << "\n");
1286
1287 Cache[BDV] = Base;
1288 }
1289 assert(Cache.count(Def));
1290 return Cache[Def];
1291}
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1309 PointerToBaseTy &PointerToBase, DominatorTree *DT,
1310 DefiningValueMapTy &DVCache,
1311 IsKnownBaseMapTy &KnownBases) {
1314 assert(base && "failed to find base pointer");
1315 PointerToBase[ptr] = base;
1316 assert((!isa(base) || !isa(ptr) ||
1317 DT->dominates(cast(base)->getParent(),
1318 cast(ptr)->getParent())) &&
1319 "The base we found better dominate the derived pointer");
1320 }
1321}
1322
1323
1324
1327 PartiallyConstructedSafepointRecord &result,
1328 PointerToBaseTy &PointerToBase,
1329 IsKnownBaseMapTy &KnownBases) {
1330 StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;
1331
1332
1333
1334
1335
1337 for (Value *V : Opt->Inputs) {
1338 if (!PotentiallyDerivedPointers.count(V))
1339 continue;
1340 PotentiallyDerivedPointers.remove(V);
1341 PointerToBase[V] = V;
1342 }
1343 findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache,
1344 KnownBases);
1345}
1346
1347
1348
1351 PartiallyConstructedSafepointRecord &result,
1352 PointerToBaseTy &PointerToBase,
1354
1358 PointerToBaseTy &PointerToBase, GCStrategy *GC) {
1359
1360
1361 GCPtrLivenessData RevisedLivenessData;
1363 for (size_t i = 0; i < records.size(); i++) {
1364 struct PartiallyConstructedSafepointRecord &info = records[i];
1366 GC);
1367 }
1368}
1369
1370
1371
1372
1375 Value *RootOfChain,
1376 Value *AlternateLiveBase) {
1379
1382
1383
1384
1385
1386 assert(isa(Instr) || isa(Instr));
1387
1388 Instruction *ClonedValue = Instr->clone();
1390 ClonedValue->setName(Instr->getName() + ".remat");
1391
1392
1393
1394 if (LastClonedValue) {
1397#ifndef NDEBUG
1398 for (auto *OpValue : ClonedValue->operand_values()) {
1399
1400
1402 "incorrect use in rematerialization chain");
1403
1404
1405 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
1406 }
1407#endif
1408 } else {
1409
1410
1411
1412
1413
1414 if (RootOfChain != AlternateLiveBase)
1416 }
1417
1418 LastClonedValue = ClonedValue;
1419 LastValue = Instr;
1420 }
1421 assert(LastClonedValue);
1422 return LastClonedValue;
1423}
1424
1425
1426
1427
1428
1429
1430
1437
1438
1439
1441 assert(!isa(Ret->begin()) &&
1442 "All PHI nodes should have been removed!");
1443
1444
1445
1446 return Ret;
1447}
1448
1449
1450
1451
1452
1453
1455 {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};
1456
1457
1458
1463 return StatepointAL;
1464
1465
1470
1474 }
1475
1476 StatepointAL = StatepointAL.addFnAttributes(Ctx, FnAttrs);
1477
1478
1479
1480
1481 if (IsMemIntrinsic)
1482 return StatepointAL;
1483
1484
1485
1486
1487 for (unsigned I : llvm::seq(Call->arg_size()))
1491
1492
1493 return StatepointAL;
1494}
1495
1496
1497
1498
1499
1500
1501
1502
1503
1509 return;
1510
1512 auto ValIt = llvm::find(LiveVec, Val);
1513 assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
1514 size_t Index = std::distance(LiveVec.begin(), ValIt);
1517 };
1519
1520
1521
1522
1523
1524
1525
1526
1527 auto getGCRelocateDecl = [&](Type *Ty) {
1529 auto AS = Ty->getScalarType()->getPointerAddressSpace();
1531 if (auto *VT = dyn_cast(Ty))
1535 M, Intrinsic::experimental_gc_relocate, {NewTy});
1536 };
1537
1538
1539
1540
1542
1543 for (unsigned i = 0; i < LiveVariables.size(); i++) {
1544
1547
1549 if (!TypeToDeclMap.count(Ty))
1550 TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1551 Function *GCRelocateDecl = TypeToDeclMap[Ty];
1552
1553
1555 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1557
1558
1560 }
1561}
1562
1563namespace {
1564
1565
1566
1567class DeferredReplacement {
1570 bool IsDeoptimize = false;
1571
1572 DeferredReplacement() = default;
1573
1574public:
1576 assert(Old != New && Old && New &&
1577 "Cannot RAUW equal values or to / from null!");
1578
1579 DeferredReplacement D;
1580 D.Old = Old;
1582 return D;
1583 }
1584
1585 static DeferredReplacement createDelete(Instruction *ToErase) {
1586 DeferredReplacement D;
1587 D.Old = ToErase;
1588 return D;
1589 }
1590
1591 static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {
1592#ifndef NDEBUG
1593 auto *F = cast(Old)->getCalledFunction();
1594 assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1595 "Only way to construct a deoptimize deferred replacement");
1596#endif
1597 DeferredReplacement D;
1598 D.Old = Old;
1599 D.IsDeoptimize = true;
1600 return D;
1601 }
1602
1603
1604 void doReplacement() {
1607
1608 assert(OldI != NewI && "Disallowed at construction?!");
1609 assert((!IsDeoptimize || !New) &&
1610 "Deoptimize intrinsics are not replaced!");
1611
1612 Old = nullptr;
1613 New = nullptr;
1614
1615 if (NewI)
1617
1618 if (IsDeoptimize) {
1619
1620
1621 auto *RI = cast(OldI->getParent()->getTerminator());
1622 new UnreachableInst(RI->getContext(), RI->getIterator());
1623 RI->eraseFromParent();
1624 }
1625
1627 }
1628};
1629
1630}
1631
1633 const char *DeoptLowering = "deopt-lowering";
1634 if (Call->hasFnAttr(DeoptLowering)) {
1635
1636
1637 const AttributeList &CSAS = Call->getAttributes();
1638 if (CSAS.hasFnAttr(DeoptLowering))
1640 Function *F = Call->getCalledFunction();
1641 assert(F && F->hasFnAttribute(DeoptLowering));
1642 return F->getFnAttribute(DeoptLowering).getValueAsString();
1643 }
1644 return "live-through";
1645}
1646
1647static void
1651 PartiallyConstructedSafepointRecord &Result,
1652 std::vector &Replacements,
1653 const PointerToBaseTy &PointerToBase,
1656
1657
1658
1659
1660
1662
1667
1669 std::optional<ArrayRef> DeoptArgs;
1671 DeoptArgs = Bundle->Inputs;
1672 std::optional<ArrayRef> TransitionArgs;
1674 TransitionArgs = Bundle->Inputs;
1675
1677 }
1678
1679
1680
1681
1682 bool IsDeoptimize = false;
1683 bool IsMemIntrinsic = false;
1684
1691
1692
1694 if (DeoptLowering == "live-in")
1696 else {
1697 assert(DeoptLowering == "live-through" && "Unsupported value!");
1698 }
1699
1700 FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());
1702 auto IID = F->getIntrinsicID();
1703 if (IID == Intrinsic::experimental_deoptimize) {
1704
1705
1706
1707
1709 for (Value *Arg : CallArgs)
1710 DomainTy.push_back(Arg->getType());
1712 false);
1713
1714
1715
1716
1717
1718 CallTarget = F->getParent()
1719 ->getOrInsertFunction("__llvm_deoptimize", FTy);
1720
1721 IsDeoptimize = true;
1722 } else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1723 IID == Intrinsic::memmove_element_unordered_atomic) {
1724 IsMemIntrinsic = true;
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742 auto &Context = Call->getContext();
1743 auto &DL = Call->getDataLayout();
1744 auto GetBaseAndOffset = [&](Value *Derived) {
1746
1747
1748
1749
1750 if (isa(Derived))
1753 else {
1754 assert(PointerToBase.count(Derived));
1755 Base = PointerToBase.find(Derived)->second;
1756 }
1757 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1758 unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
1763 return std::make_pair(Base, Builder.CreateSub(Derived_int, Base_int));
1764 };
1765
1766 auto *Dest = CallArgs[0];
1767 Value *DestBase, *DestOffset;
1768 std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1769
1770 auto *Source = CallArgs[1];
1771 Value *SourceBase, *SourceOffset;
1772 std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);
1773
1774 auto *LengthInBytes = CallArgs[2];
1775 auto *ElementSizeCI = cast(CallArgs[3]);
1776
1777 CallArgs.clear();
1781 CallArgs.push_back(SourceOffset);
1782 CallArgs.push_back(LengthInBytes);
1783
1785 for (Value *Arg : CallArgs)
1786 DomainTy.push_back(Arg->getType());
1788 false);
1789
1791 uint64_t ElementSize = ElementSizeCI->getZExtValue();
1792 if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1793 switch (ElementSize) {
1794 case 1:
1795 return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1796 case 2:
1797 return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1798 case 4:
1799 return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1800 case 8:
1801 return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1802 case 16:
1803 return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1804 default:
1806 }
1807 }
1808 assert(IID == Intrinsic::memmove_element_unordered_atomic);
1809 switch (ElementSize) {
1810 case 1:
1811 return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1812 case 2:
1813 return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1814 case 4:
1815 return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1816 case 8:
1817 return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1818 case 16:
1819 return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1820 default:
1822 }
1823 };
1824
1825 CallTarget =
1826 F->getParent()
1827 ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);
1828 }
1829 }
1830
1831
1833 if (auto *CI = dyn_cast(Call)) {
1835 StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1836 TransitionArgs, DeoptArgs, GCLive, "safepoint_token");
1837
1840
1841
1842
1845
1846 Token = cast(SPCall);
1847
1848
1849
1850 assert(CI->getNextNode() && "Not a terminator, must have next!");
1853 } else {
1854 auto *II = cast(Call);
1855
1856
1857
1858
1860 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1861 II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,
1862 GCLive, "statepoint_token");
1863
1865
1866
1867
1870
1871 Token = cast(SPInvoke);
1872
1873
1874 BasicBlock *UnwindBlock = II->getUnwindDest();
1875 assert(!isa(UnwindBlock->begin()) &&
1877 "can't safely insert in this block!");
1878
1881
1882
1884 Result.UnwindToken = ExceptionalToken;
1885
1887
1888
1889 BasicBlock *NormalDest = II->getNormalDest();
1890 assert(!isa(NormalDest->begin()) &&
1892 "can't safely insert in this block!");
1893
1895
1896
1897
1898 }
1899 assert(Token && "Should be set in one of the above branches!");
1900
1901 if (IsDeoptimize) {
1902
1903
1904
1905 Replacements.push_back(
1906 DeferredReplacement::createDeoptimizeReplacement(Call));
1907 } else {
1908 Token->setName("statepoint_token");
1909 if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1910 StringRef Name = Call->hasName() ? Call->getName() : "";
1914 Call->getAttributes().getRetAttrs()));
1915
1916
1917
1918
1919
1920
1921
1922 Replacements.emplace_back(
1923 DeferredReplacement::createRAUW(Call, GCResult));
1924 } else {
1925 Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1926 }
1927 }
1928
1929 Result.StatepointToken = Token;
1930
1931
1933}
1934
1935
1936
1937
1938
1939
1940static void
1942 PartiallyConstructedSafepointRecord &Result,
1943 std::vector &Replacements,
1944 const PointerToBaseTy &PointerToBase, GCStrategy *GC) {
1945 const auto &LiveSet = Result.LiveSet;
1946
1947
1949 LiveVec.reserve(LiveSet.size());
1950 BaseVec.reserve(LiveSet.size());
1951 for (Value *L : LiveSet) {
1953 assert(PointerToBase.count(L));
1954 Value *Base = PointerToBase.find(L)->second;
1956 }
1958
1959
1961 PointerToBase, GC);
1962}
1963
1964
1965
1966
1967
1968
1969
1970static void
1974 for (User *U : GCRelocs) {
1975 GCRelocateInst *Relocate = dyn_cast(U);
1976 if (!Relocate)
1977 continue;
1978
1981 Value *Alloca = AllocaMap[OriginalValue];
1982
1983
1985 "Should always have one since it's not a terminator");
1987
1988#ifndef NDEBUG
1989 VisitedLiveValues.insert(OriginalValue);
1990#endif
1991 }
1992}
1993
1994
1995
1997 const RematerializedValueMapTy &RematerializedValues,
2000 for (auto RematerializedValuePair: RematerializedValues) {
2001 Instruction *RematerializedValue = RematerializedValuePair.first;
2002 Value *OriginalValue = RematerializedValuePair.second;
2003
2004 assert(AllocaMap.count(OriginalValue) &&
2005 "Can not find alloca for rematerialized value");
2006 Value *Alloca = AllocaMap[OriginalValue];
2007
2008 new StoreInst(RematerializedValue, Alloca,
2009 std::next(RematerializedValue->getIterator()));
2010
2011#ifndef NDEBUG
2012 VisitedLiveValues.insert(OriginalValue);
2013#endif
2014 }
2015}
2016
2017
2021#ifndef NDEBUG
2022
2023
2024 int InitialAllocaNum = 0;
2026 if (isa(I))
2027 InitialAllocaNum++;
2028#endif
2029
2030
2033
2034 std::size_t NumRematerializedValues = 0;
2036
2037
2038
2040 auto emitAllocaFor = [&](Value *LiveValue) {
2042 new AllocaInst(LiveValue->getType(), DL.getAllocaAddrSpace(), "",
2043 F.getEntryBlock().getFirstNonPHIIt());
2044 AllocaMap[LiveValue] = Alloca;
2045 PromotableAllocas.push_back(Alloca);
2046 };
2047
2048
2050 emitAllocaFor(V);
2051
2052
2053 for (const auto &Info : Records)
2054 for (auto RematerializedValuePair : Info.RematerializedValues) {
2055 Value *OriginalValue = RematerializedValuePair.second;
2056 if (AllocaMap.contains(OriginalValue))
2057 continue;
2058
2059 emitAllocaFor(OriginalValue);
2060 ++NumRematerializedValues;
2061 }
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072 for (const auto &Info : Records) {
2073 Value *Statepoint = Info.StatepointToken;
2074
2075
2077
2078
2080
2081
2082
2083 if (isa(Statepoint)) {
2085 VisitedLiveValues);
2086 }
2087
2088
2090 VisitedLiveValues);
2091
2093
2094
2095
2096
2097
2099 for (auto Pair : AllocaMap) {
2100 Value *Def = Pair.first;
2102
2103
2104 if (VisitedLiveValues.count(Def)) {
2105 continue;
2106 }
2108 }
2109
2111 for (auto *AI : ToClobber) {
2112 auto AT = AI->getAllocatedType();
2114 if (AT->isVectorTy())
2116 else
2119 }
2120 };
2121
2122
2123
2124 if (auto II = dyn_cast(Statepoint)) {
2125 InsertClobbersAt(II->getNormalDest()->getFirstInsertionPt());
2126 InsertClobbersAt(II->getUnwindDest()->getFirstInsertionPt());
2127 } else {
2128 InsertClobbersAt(
2129 std::next(cast(Statepoint)->getIterator()));
2130 }
2131 }
2132 }
2133
2134
2135 for (auto Pair : AllocaMap) {
2136 Value *Def = Pair.first;
2138
2139
2140
2141
2143
2144 Uses.reserve(Def->getNumUses());
2145 for (User *U : Def->users()) {
2146 if (!isa(U)) {
2147
2148
2149
2150
2151
2152 Uses.push_back(cast(U));
2153 }
2154 }
2155
2159
2161 if (isa(Use)) {
2163 for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
2164 if (Def == Phi->getIncomingValue(i)) {
2167 Phi->getIncomingBlock(i)->getTerminator()->getIterator());
2168 Phi->setIncomingValue(i, Load);
2169 }
2170 }
2171 } else {
2173 Use->getIterator());
2174 Use->replaceUsesOfWith(Def, Load);
2175 }
2176 }
2177
2178
2179
2180
2182 DL.getABITypeAlign(Def->getType()));
2183 if (Instruction *Inst = dyn_cast(Def)) {
2184 if (InvokeInst *Invoke = dyn_cast(Inst)) {
2185
2186
2187 BasicBlock *NormalDest = Invoke->getNormalDest();
2189 } else {
2190 assert(!Inst->isTerminator() &&
2191 "The only terminator that can produce a value is "
2192 "InvokeInst which is handled above.");
2193 Store->insertAfter(Inst);
2194 }
2195 } else {
2196 assert(isa(Def));
2197 Store->insertAfter(cast(Alloca));
2198 }
2199 }
2200
2201 assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
2202 "we must have the same allocas with lives");
2203 (void) NumRematerializedValues;
2204 if (!PromotableAllocas.empty()) {
2205
2207 }
2208
2209#ifndef NDEBUG
2210 for (auto &I : F.getEntryBlock())
2211 if (isa(I))
2212 InitialAllocaNum--;
2213 assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
2214#endif
2215}
2216
2217
2218
2219
2222 erase_if(Vec, [&](const T &V) { return !Seen.insert(V).second; });
2223}
2224
2225
2226
2229 if (Values.empty())
2230
2231 return;
2232
2233 Module *M = Call->getModule();
2234
2237 if (isa(Call)) {
2238
2240 CallInst::Create(Func, Values, "", std::next(Call->getIterator())));
2241 return;
2242 }
2243
2244
2245 auto *II = cast(Call);
2247 Func, Values, "", II->getNormalDest()->getFirstInsertionPt()));
2249 Func, Values, "", II->getUnwindDest()->getFirstInsertionPt()));
2250}
2251
2256 GCPtrLivenessData OriginalLivenessData;
2258 for (size_t i = 0; i < records.size(); i++) {
2259 struct PartiallyConstructedSafepointRecord &info = records[i];
2261 }
2262}
2263
2264
2265
2266
2267
2268
2269
2272 Value *CurrentValue) {
2276 GEP->getPointerOperand());
2277 }
2278
2279 if (CastInst *CI = dyn_cast(CurrentValue)) {
2280 if (!CI->isNoopCast(CI->getDataLayout()))
2281 return CI;
2282
2285 CI->getOperand(0));
2286 }
2287
2288
2289
2290 return CurrentValue;
2291}
2292
2293
2294
2299
2301 if (CastInst *CI = dyn_cast(Instr)) {
2302 assert(CI->isNoopCast(CI->getDataLayout()) &&
2303 "non noop cast is found during rematerialization");
2304
2305 Type *SrcTy = CI->getOperand(0)->getType();
2309
2311
2312 Type *ValTy = GEP->getSourceElementType();
2314
2315
2316
2317
2318 if (->hasAllConstantIndices())
2320
2321 } else {
2322 llvm_unreachable("unsupported instruction type during rematerialization");
2323 }
2324 }
2325
2326 return Cost;
2327}
2328
2333 return false;
2334
2335
2337 for (unsigned i = 0; i < PhiNum; i++)
2340
2341
2342
2343 for (unsigned i = 0; i < PhiNum; i++) {
2344 auto CIVI =
2346 if (CIVI == CurrentIncomingValues.end())
2347 return false;
2348 BasicBlock *CurrentIncomingBB = CIVI->second;
2349 if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
2350 return false;
2351 }
2352 return true;
2353}
2354
2355
2356
2357static void
2359 RematCandTy &RematerizationCandidates,
2361 const unsigned int ChainLengthThreshold = 10;
2362
2363 for (auto P2B : PointerToBase) {
2364 auto *Derived = P2B.first;
2365 auto *Base = P2B.second;
2366
2367 if (Derived == Base)
2368 continue;
2369
2370
2372 Value *RootOfChain =
2374
2375
2376 if ( ChainToBase.size() == 0 ||
2377 ChainToBase.size() > ChainLengthThreshold)
2378 continue;
2379
2380
2381
2382 if (RootOfChain != PointerToBase[Derived]) {
2383 PHINode *OrigRootPhi = dyn_cast(RootOfChain);
2384 PHINode *AlternateRootPhi = dyn_cast(PointerToBase[Derived]);
2385 if (!OrigRootPhi || !AlternateRootPhi)
2386 continue;
2387
2388
2389
2390
2391
2392
2393
2394
2395
2397 continue;
2398 }
2399
2401
2402
2403
2404
2405
2406
2407 RematerizlizationCandidateRecord Record;
2408 Record.ChainToBase = ChainToBase;
2409 Record.RootOfChain = RootOfChain;
2411 RematerizationCandidates.insert({ Derived, Record });
2412 }
2413}
2414
2415
2416
2417
2418
2420 RematCandTy &RematerizationCandidates,
2422 PointerToBaseTy &PointerToBase) {
2424 return;
2425
2427
2428 LLVM_DEBUG(dbgs() << "Rematerialize derived pointers at uses, "
2429 << "Num statepoints: " << Records.size() << '\n');
2430
2431 for (auto &It : RematerizationCandidates) {
2432 Instruction *Cand = cast(It.first);
2433 auto &Record = It.second;
2434
2436 continue;
2437
2439 continue;
2440
2443 if (U->getParent() == Cand->getParent())
2444 continue;
2445
2446
2448 [](const auto *U) { return isa(U); }))
2449 continue;
2450
2451 LLVM_DEBUG(dbgs() << "Trying cand " << *Cand << " ... ");
2452
2453
2454
2455
2456
2457
2458
2460 Records, [Cand](const auto &R) { return R.LiveSet.contains(Cand); });
2461 unsigned NumUses = Cand->getNumUses();
2462
2463 LLVM_DEBUG(dbgs() << "Num uses: " << NumUses << " Num live statepoints: "
2464 << NumLiveStatepoints << " ");
2465
2466 if (NumLiveStatepoints < NumUses) {
2468 continue;
2469 }
2470
2471
2472
2473
2474 if (NumLiveStatepoints == NumUses && Record.Cost > 0) {
2476 continue;
2477 }
2478
2480
2481
2482
2483
2484
2485
2486 if (Record.ChainToBase.size() > 1) {
2487 Record.ChainToBase.clear();
2489 }
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2503 Record.ChainToBase, UserI, Record.RootOfChain, PointerToBase[Cand]);
2505 PointerToBase[RematChain] = PointerToBase[Cand];
2506 }
2507 LiveValuesToBeDeleted.push_back(Cand);
2508 }
2509
2510 LLVM_DEBUG(dbgs() << "Rematerialized " << LiveValuesToBeDeleted.size()
2511 << " derived pointers\n");
2512 for (auto *Cand : LiveValuesToBeDeleted) {
2513 assert(Cand->use_empty() && "Unexpected user remain");
2514 RematerizationCandidates.erase(Cand);
2515 for (auto &R : Records) {
2516 assert(!R.LiveSet.contains(Cand) ||
2517 R.LiveSet.contains(PointerToBase[Cand]));
2518 R.LiveSet.remove(Cand);
2519 }
2520 }
2521
2522
2523
2524 if (!LiveValuesToBeDeleted.empty()) {
2525 for (auto &P : RematerizationCandidates) {
2526 auto &R = P.second;
2527 if (R.ChainToBase.size() > 1) {
2528 R.ChainToBase.clear();
2530 }
2531 }
2532 }
2533}
2534
2535
2536
2537
2538
2540 PartiallyConstructedSafepointRecord &Info,
2541 PointerToBaseTy &PointerToBase,
2542 RematCandTy &RematerizationCandidates,
2544
2545
2547
2548 for (Value *LiveValue : Info.LiveSet) {
2549 auto It = RematerizationCandidates.find(LiveValue);
2550 if (It == RematerizationCandidates.end())
2551 continue;
2552
2553 RematerizlizationCandidateRecord &Record = It->second;
2554
2556
2557
2558 if (isa(Call))
2560
2561
2563 continue;
2564
2565
2566 LiveValuesToBeDeleted.push_back(LiveValue);
2567
2568
2569
2570
2571
2572 if (isa(Call)) {
2573 Instruction *InsertBefore = Call->getNextNode();
2574 assert(InsertBefore);
2577 Record.RootOfChain, PointerToBase[LiveValue]);
2578 Info.RematerializedValues[RematerializedValue] = LiveValue;
2579 } else {
2580 auto *Invoke = cast(Call);
2581
2583 &*Invoke->getNormalDest()->getFirstInsertionPt();
2585 &*Invoke->getUnwindDest()->getFirstInsertionPt();
2586
2587 Instruction *NormalRematerializedValue =
2589 Record.RootOfChain, PointerToBase[LiveValue]);
2590 Instruction *UnwindRematerializedValue =
2592 Record.RootOfChain, PointerToBase[LiveValue]);
2593
2594 Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2595 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2596 }
2597 }
2598
2599
2600 for (auto *LiveValue: LiveValuesToBeDeleted) {
2601 Info.LiveSet.remove(LiveValue);
2602 }
2603}
2604
2607 DefiningValueMapTy &DVCache,
2608 IsKnownBaseMapTy &KnownBases) {
2609 auto &Context = F.getContext();
2610 auto &DL = F.getDataLayout();
2611 bool Changed = false;
2612
2613 for (auto *Callsite : Intrinsics)
2614 switch (Callsite->getIntrinsicID()) {
2615 case Intrinsic::experimental_gc_get_pointer_base: {
2616 Changed = true;
2618 findBasePointer(Callsite->getOperand(0), DVCache, KnownBases);
2619 assert(!DVCache.count(Callsite));
2620 Callsite->replaceAllUsesWith(Base);
2621 if (->hasName())
2622 Base->takeName(Callsite);
2623 Callsite->eraseFromParent();
2624 break;
2625 }
2626 case Intrinsic::experimental_gc_get_pointer_offset: {
2627 Changed = true;
2628 Value *Derived = Callsite->getOperand(0);
2630 assert(!DVCache.count(Callsite));
2632 unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
2634 Value *BaseInt =
2637 Value *DerivedInt =
2642 Offset->takeName(Callsite);
2643 Callsite->eraseFromParent();
2644 break;
2645 }
2646 default:
2648 }
2649
2650 return Changed;
2651}
2652
2656 DefiningValueMapTy &DVCache,
2657 IsKnownBaseMapTy &KnownBases) {
2659
2660#ifndef NDEBUG
2661
2662 std::set<CallBase *> Uniqued;
2663 Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
2664 assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
2665
2666 for (CallBase *Call : ToUpdate)
2667 assert(Call->getFunction() == &F);
2668#endif
2669
2670
2671
2672
2673
2674 for (CallBase *Call : ToUpdate) {
2675 auto *II = dyn_cast(Call);
2676 if ()
2677 continue;
2680 }
2681
2682
2683
2685
2686
2687
2688
2689
2690 for (CallBase *Call : ToUpdate) {
2692
2695 "support for FCA unimplemented");
2698 }
2699
2701 }
2702
2704
2705
2706
2708
2709
2710 PointerToBaseTy PointerToBase;
2711
2712
2713 for (size_t i = 0; i < Records.size(); i++) {
2714 PartiallyConstructedSafepointRecord &info = Records[i];
2715 findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases);
2716 }
2718 errs() << "Base Pairs (w/o Relocation):\n";
2719 for (auto &Pair : PointerToBase) {
2720 errs() << " derived ";
2721 Pair.first->printAsOperand(errs(), false);
2722 errs() << " base ";
2723 Pair.second->printAsOperand(errs(), false);
2724 errs() << "\n";
2725 ;
2726 }
2727 }
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742 Holders.reserve(Holders.size() + Records.size());
2743 for (size_t i = 0; i < Records.size(); i++) {
2744 PartiallyConstructedSafepointRecord &Info = Records[i];
2745
2747 for (auto *Derived : Info.LiveSet) {
2748 assert(PointerToBase.count(Derived) && "Missed base for derived pointer");
2749 Bases.push_back(PointerToBase[Derived]);
2750 }
2751
2753 }
2754
2755
2756
2757
2759
2761 errs() << "Base Pairs: (w/Relocation)\n";
2762 for (auto Pair : PointerToBase) {
2763 errs() << " derived ";
2764 Pair.first->printAsOperand(errs(), false);
2765 errs() << " base ";
2766 Pair.second->printAsOperand(errs(), false);
2767 errs() << "\n";
2768 }
2769 }
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779 for (auto &Info : Records) {
2780 Info.LiveSet.remove_if([&](Value *LiveV) {
2781 assert(PointerToBase.count(LiveV) && "Missed base for derived pointer");
2782 return isa(PointerToBase[LiveV]);
2783 });
2784 }
2785
2786 for (CallInst *CI : Holders)
2787 CI->eraseFromParent();
2788
2789 Holders.clear();
2790
2791
2792 RematCandTy RematerizationCandidates;
2794
2795
2796
2797
2798
2800 PointerToBase);
2801 for (size_t i = 0; i < Records.size(); i++)
2803 RematerizationCandidates, TTI);
2804
2805
2806
2807
2808 std::vector Replacements;
2809
2810
2811
2812
2813
2814
2815
2816 for (size_t i = 0; i < Records.size(); i++)
2818 PointerToBase, GC.get());
2819
2820 ToUpdate.clear();
2821
2822 for (auto &PR : Replacements)
2823 PR.doReplacement();
2824
2825 Replacements.clear();
2826
2827 for (auto &Info : Records) {
2828
2829
2830
2831
2832
2833
2834
2835
2836 Info.LiveSet.clear();
2837 }
2838 PointerToBase.clear();
2839
2840
2842 for (const PartiallyConstructedSafepointRecord &Info : Records) {
2843
2844
2845
2846
2847
2849#ifndef NDEBUG
2850
2851
2852
2853
2855 "statepoint must be reachable or liveness is meaningless");
2856 for (Value *V : Info.StatepointToken->gc_live()) {
2857 if (!isa(V))
2858
2859 continue;
2860 auto *LiveInst = cast(V);
2862 "unreachable values should never be live");
2864 "basic SSA liveness expectation violated by liveness analysis");
2865 }
2866#endif
2867 }
2869
2870#ifndef NDEBUG
2871
2874 "must be a gc pointer type");
2875#endif
2876
2878 return !Records.empty();
2879}
2880
2881
2882
2883
2886 R.addAttribute(Attribute::Dereferenceable);
2887 R.addAttribute(Attribute::DereferenceableOrNull);
2888 R.addAttribute(Attribute::ReadNone);
2889 R.addAttribute(Attribute::ReadOnly);
2890 R.addAttribute(Attribute::WriteOnly);
2891 R.addAttribute(Attribute::NoAlias);
2892 R.addAttribute(Attribute::NoFree);
2893 return R;
2894}
2895
2898
2899
2900
2901
2902
2903
2906 return;
2907 }
2908
2911 if (isa(A.getType()))
2912 F.removeParamAttrs(A.getArgNo(), R);
2913
2914 if (isa(F.getReturnType()))
2915 F.removeRetAttrs(R);
2916
2918 F.removeFnAttr(Attr);
2919}
2920
2921
2922
2923
2926 return;
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2941 LLVMContext::MD_range,
2942 LLVMContext::MD_alias_scope,
2943 LLVMContext::MD_nontemporal,
2944 LLVMContext::MD_nonnull,
2945 LLVMContext::MD_align,
2946 LLVMContext::MD_type};
2947
2948
2949 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2950}
2951
2953 if (F.empty())
2954 return;
2955
2958
2959
2960
2962
2964
2965
2966
2967
2968
2969
2970 if (auto *II = dyn_cast(&I))
2971 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2972 InvariantStartInstructions.push_back(II);
2973 continue;
2974 }
2975
2976 if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {
2978 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2979 }
2980
2982
2984 if (auto *Call = dyn_cast(&I)) {
2985 for (int i = 0, e = Call->arg_size(); i != e; i++)
2986 if (isa(Call->getArgOperand(i)->getType()))
2987 Call->removeParamAttrs(i, R);
2988 if (isa(Call->getType()))
2989 Call->removeRetAttrs(R);
2990 }
2991 }
2992
2993
2994 for (auto *II : InvariantStartInstructions) {
2996 II->eraseFromParent();
2997 }
2998}
2999
3000
3001
3003 if (.hasGC())
3004 return nullptr;
3005
3007}
3008
3009
3010
3012 if (.hasGC())
3013 return false;
3014
3015 std::unique_ptr Strategy = findGCStrategy(F);
3016
3017 assert(Strategy && "GC strategy is required by function, but was not found");
3018
3019 return Strategy->useRS4GC();
3020}
3021
3023#ifndef NDEBUG
3025#endif
3026
3029
3032}
3033
3037 assert(.isDeclaration() &&
.empty() &&
3038 "need function body to rewrite statepoints in");
3040
3041 auto NeedsRewrite = [&TLI](Instruction &I) {
3042 if (const auto *Call = dyn_cast(&I)) {
3043 if (isa(Call))
3044 return false;
3046 return false;
3047
3048
3049
3050
3051
3052
3053
3054
3056 assert((isa(Call) || isa(Call)) &&
3057 "Don't expect any other calls here!");
3058 return false;
3059 }
3060 return true;
3061 }
3062 return false;
3063 };
3064
3065
3066
3067
3068 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
3070
3072
3073
3074
3075
3079
3080 if (NeedsRewrite(I)) {
3081
3082
3083
3084
3086 "no unreachable blocks expected");
3087 ParsePointNeeded.push_back(cast(&I));
3088 }
3089 if (auto *CI = dyn_cast(&I))
3090 if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
3091 CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
3093 }
3094
3095
3096 if (ParsePointNeeded.empty() && Intrinsics.empty())
3097 return MadeChange;
3098
3099
3100
3101
3102
3104 if (BB.getUniquePredecessor())
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3121 if (auto *BI = dyn_cast(TI))
3122 if (BI->isConditional())
3123 return dyn_cast(BI->getCondition());
3124
3125 return nullptr;
3126 };
3129 if (auto *Cond = getConditionInst(TI))
3130
3131
3132 if (isa(Cond) && Cond->hasOneUse()) {
3133 MadeChange = true;
3134 Cond->moveBefore(TI);
3135 }
3136 }
3137
3138
3139
3140
3141
3142
3144 if (!isa(I))
3145 continue;
3146
3147 unsigned VF = 0;
3148 for (unsigned i = 0; i < I.getNumOperands(); i++)
3149 if (auto *OpndVTy = dyn_cast(I.getOperand(i)->getType())) {
3151 VF == cast(OpndVTy)->getNumElements());
3152 VF = cast(OpndVTy)->getNumElements();
3153 }
3154
3155
3156
3157 if (.getOperand(0)->getType()->isVectorTy() && VF != 0) {
3159 auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));
3161 MadeChange = true;
3162 }
3163 }
3164
3165
3166
3167
3168
3169 DefiningValueMapTy DVCache;
3170
3171
3172
3173 IsKnownBaseMapTy KnownBases;
3174
3175 if (!Intrinsics.empty())
3176
3177
3179
3180 if (!ParsePointNeeded.empty())
3181 MadeChange |=
3183
3184 return MadeChange;
3185}
3186
3187
3188
3189
3190
3191
3192
3193
3194
3199
3201
3202
3203
3204 if (isa(I))
3205 continue;
3206
3207
3208 for (Value *V : I.operands()) {
3210 "support for FCA unimplemented");
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3223 }
3224 }
3225 }
3226}
3227
3231 for (auto &I : *Succ) {
3232 PHINode *PN = dyn_cast(&I);
3233 if (!PN)
3234 break;
3235
3238 "support for FCA unimplemented");
3241 }
3242 }
3243}
3244
3250 return KillSet;
3251}
3252
3253#ifndef NDEBUG
3254
3255
3257 Instruction *TI, bool TermOkay = false) {
3259 if (auto *I = dyn_cast(V)) {
3260
3261
3262
3263 if (TermOkay && TI == I)
3264 continue;
3266 "basic SSA liveness expectation violated by liveness analysis");
3267 }
3268 }
3269}
3270
3271
3272
3273
3279}
3280#endif
3281
3285
3286
3289 Data.LiveSet[&BB].clear();
3291
3292#ifndef NDEBUG
3293 for (Value *Kill : Data.KillSet[&BB])
3294 assert(.LiveSet[&BB].count(Kill) && "live set contains kill");
3295#endif
3296
3299 Data.LiveIn[&BB] = Data.LiveSet[&BB];
3300 Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]);
3301 Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]);
3302 if (.LiveIn[&BB].empty())
3304 }
3305
3306
3307 while (!Worklist.empty()) {
3309
3310
3311
3313 const auto OldLiveOutSize = LiveOut.size();
3317 }
3318
3319 if (OldLiveOutSize == LiveOut.size()) {
3320
3321
3322
3323 continue;
3324 }
3325 Data.LiveOut[BB] = LiveOut;
3326
3327
3331
3334
3335 if (OldLiveIn.size() != LiveTmp.size()) {
3336 Data.LiveIn[BB] = LiveTmp;
3338 }
3339 }
3340
3341#ifndef NDEBUG
3342
3343
3346#endif
3347}
3348
3350 StatepointLiveSetTy &Out, GCStrategy *GC) {
3352
3353
3356
3357
3358
3359
3360
3362 GC);
3363 LiveOut.remove(Inst);
3364 Out.insert(LiveOut.begin(), LiveOut.end());
3365}
3366
3369 PartiallyConstructedSafepointRecord &Info,
3370 PointerToBaseTy &PointerToBase,
3372 StatepointLiveSetTy Updated;
3374
3375
3376
3377 for (auto *V : Updated)
3378 PointerToBase.insert({ V, V });
3379
3380 Info.LiveSet = Updated;
3381}
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Expand Atomic instructions
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Analysis containing CSE Info
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Checks Use for liveness in LiveValues If Use is not live
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
std::optional< std::vector< StOtherPiece > > Other
Module.h This file contains the declarations for the Module class.
This file implements a map that provides insertion order iteration.
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
const SmallVectorImpl< MachineOperand > & Cond
Remove Loads Into Fake Uses
static void makeStatepointExplicitImpl(CallBase *Call, const SmallVectorImpl< Value * > &BasePtrs, const SmallVectorImpl< Value * > &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)
static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
static std::unique_ptr< GCStrategy > findGCStrategy(Function &F)
Looks up the GC strategy for a given function, returning null if the function doesn't have a GC tag.
static Instruction * rematerializeChain(ArrayRef< Instruction * > ChainToBase, Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase)
static void unique_unsorted(SmallVectorImpl< T > &Vec)
Implement a unique function which doesn't require we sort the input vector.
static void stripNonValidDataFromBody(Function &F)
static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases)
Returns true if V is a known base.
static Value * findBasePointer(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
For a given value or instruction, figure out what base ptr its derived from.
static cl::opt< bool, true > ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden)
static void insertRelocationStores(iterator_range< Value::user_iterator > GCRelocs, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT)
static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result, GCStrategy *GC)
static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value * > &LiveTmp, GCStrategy *GC)
static void relocationViaAlloca(Function &F, DominatorTree &DT, ArrayRef< Value * > Live, ArrayRef< PartiallyConstructedSafepointRecord > Records)
Do all the relocation update via allocas and mem2reg.
static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)
static cl::opt< unsigned > RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6))
static Value * findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base pointer for this value if known.
static Value * findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Returns the base defining value for this value.
static void insertUseHolderAfter(CallBase *Call, const ArrayRef< Value * > Values, SmallVectorImpl< CallInst * > &Holders)
Insert holders so that each Value is obviously live through the entire lifetime of the call.
static AttributeList legalizeCallAttributes(CallBase *Call, bool IsMemIntrinsic, AttributeList StatepointAL)
static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl< CallBase * > &ToUpdate, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static bool shouldRewriteStatepointsIn(Function &F)
Returns true if this function should be rewritten by this pass.
static cl::opt< bool > RematDerivedAtUses("rs4gc-remat-derived-at-uses", cl::Hidden, cl::init(true))
static ArrayRef< Use > GetDeoptBundleOperands(const CallBase *Call)
static void stripNonValidAttributesFromPrototype(Function &F)
static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, StatepointLiveSetTy &out, GCStrategy *GC)
Given results from the dataflow liveness computation, find the set of live Values at a particular ins...
static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data, GCStrategy *GC)
Compute the live-in set for every basic block in the function.
static void stripInvalidMetadataFromInstruction(Instruction &I)
Certain metadata on instructions are invalid after running RS4GC.
static constexpr Attribute::AttrKind FnAttrsToStrip[]
static bool areBothVectorOrScalar(Value *First, Value *Second)
static void rematerializeLiveValuesAtUses(RematCandTy &RematerizationCandidates, MutableArrayRef< PartiallyConstructedSafepointRecord > Records, PointerToBaseTy &PointerToBase)
static bool isHandledGCPointerType(Type *T, GCStrategy *GC)
static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction * > &ChainToBase, Value *CurrentValue)
static cl::opt< bool > PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false))
static Value * findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base defining value for the 'Index' element of the given vector instruction 'I'.
static void stripNonValidData(Module &M)
The IR fed into RewriteStatepointsForGC may have had attributes and metadata implying dereferenceabil...
static InstructionCost chainToBasePointerCost(SmallVectorImpl< Instruction * > &Chain, TargetTransformInfo &TTI)
static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC)
static SetVector< Value * > computeKillSet(BasicBlock *BB, GCStrategy *GC)
static bool ClobberNonLive
static cl::opt< bool > PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false))
static bool isOriginalBaseResult(Value *V)
This value is a base pointer that is not generated by RS4GC, i.e.
static cl::opt< bool > PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false))
static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases)
Caches the IsKnownBase flag for a value and asserts that it wasn't present in the cache before.
static cl::opt< bool > AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true))
static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)
static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName)
static void CreateGCRelocates(ArrayRef< Value * > LiveVariables, ArrayRef< Value * > BasePtrs, Instruction *StatepointToken, IRBuilder<> &Builder, GCStrategy *GC)
Helper function to place all gc relocates necessary for the given statepoint.
static void checkBasicSSA(DominatorTree &DT, SetVector< Value * > &Live, Instruction *TI, bool TermOkay=false)
Check that the items in 'Live' dominate 'TI'.
static StringRef getDeoptLowering(CallBase *Call)
static void findLiveReferences(Function &F, DominatorTree &DT, ArrayRef< CallBase * > toUpdate, MutableArrayRef< struct PartiallyConstructedSafepointRecord > records, GCStrategy *GC)
static AttributeMask getParamAndReturnAttributesToRemove()
static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl< CallInst * > &Intrinsics, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static Value * findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Helper function for findBasePointer - Will return a value which either a) defines the base pointer fo...
static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase, GCStrategy *GC)
Given an updated version of the dataflow liveness results, update the liveset and base pointer maps f...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static unsigned getNumElements(Type *Ty)
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
static bool containsGCPtrType(Type *Ty)
Provides some synthesis utilities to produce sequences of values.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
This file defines the SmallVector class.
This pass exposes codegen information to IR-level passes.
an instruction to allocate memory on the stack
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents an incoming formal argument to a Function.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
reverse_iterator rend() const
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
reverse_iterator rbegin() const
Value handle that asserts if the Value is deleted.
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
AttributeSet getFnAttrs() const
The function attributes are returned.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute > > Attrs)
Create an AttributeList with the specified parameters in it.
bool isEmpty() const
Return true if there are no attributes.
AttributeList addFnAttributes(LLVMContext &C, const AttrBuilder &B) const
Add function attribute to the list.
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if the attribute exists for the function.
Attribute getFnAttr(Attribute::AttrKind Kind) const
Return the attribute object that exists for the function.
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
AttributeList addParamAttributes(LLVMContext &C, unsigned ArgNo, const AttrBuilder &B) const
Add an argument attribute to the list.
StringRef getValueAsString() const
Return the attribute's value as a string.
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
reverse_iterator rbegin()
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
InstListType::reverse_iterator reverse_iterator
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This class represents a no-op cast from one type to another.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setCallingConv(CallingConv::ID CC)
void setAttributes(AttributeList A)
Set the attributes for this call.
AttributeList getAttributes() const
Return the attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
void setTailCallKind(TailCallKind TCK)
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
This is the base class for all instructions that perform data casts.
static ConstantAggregateZero * get(Type *Ty)
This is the shared class of boolean and integer constants.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
A handy container for a FunctionType+Callee-pointer pair, which can be passed around as a single enti...
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Represents calls to the gc.relocate intrinsic.
Value * getDerivedPtr() const
Represents a gc.statepoint intrinsic call.
GCStrategy describes a garbage collector algorithm's code generation requirements,...
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
CallInst * CreateGCStatepointCall(uint64_t ID, uint32_t NumPatchBytes, FunctionCallee ActualCallee, ArrayRef< Value * > CallArgs, std::optional< ArrayRef< Value * > > DeoptArgs, ArrayRef< Value * > GCArgs, const Twine &Name="")
Create a call to the experimental.gc.statepoint intrinsic to start a new statepoint sequence.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args={}, const Twine &Name="", MDNode *FPMathTag=nullptr)
CallInst * CreateGCResult(Instruction *Statepoint, Type *ResultType, const Twine &Name="")
Create a call to the experimental.gc.result intrinsic to extract the result from a call wrapped in a ...
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
InvokeInst * CreateGCStatepointInvoke(uint64_t ID, uint32_t NumPatchBytes, FunctionCallee ActualInvokee, BasicBlock *NormalDest, BasicBlock *UnwindDest, ArrayRef< Value * > InvokeArgs, std::optional< ArrayRef< Value * > > DeoptArgs, ArrayRef< Value * > GCArgs, const Twine &Name="")
Create an invoke to the experimental.gc.statepoint intrinsic to start a new statepoint sequence.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
MDNode * createMutableTBAAAccessTag(MDNode *Tag)
Return mutable version of the given mutable or immutable TBAA access tag.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
static 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 all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
This class represents the LLVM 'select' instruction.
A vector that has set insertion semantics.
bool remove(const value_type &X)
Remove an item from the set vector.
size_type size() const
Determine the number of elements in the SetVector.
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
iterator end()
Get an iterator to the end of the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
iterator begin()
Get an iterator to the beginning of the SetVector.
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
Class to represent struct types.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
static CastContextHint getCastContextHint(const Instruction *I)
Calculates a CastContextHint from I.
InstructionCost getAddressComputationCost(Type *Ty, ScalarEvolution *SE=nullptr, const SCEV *Ptr=nullptr) const
InstructionCost getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src, TTI::CastContextHint CCH, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
@ TCK_SizeAndLatency
The weighted sum of size and latency.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
static Type * getVoidTy(LLVMContext &C)
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
iterator_range< value_op_iterator > operand_values()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
User * getUniqueUndroppableUser()
Return true if there is exactly one unique user of this value that cannot be dropped (that user can h...
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getNumUses() const
This method computes the number of uses of this Value.
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.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Cold
Attempts to make code in the caller as efficient as possible under the assumption that the call is no...
Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
AttributeList getAttributes(LLVMContext &C, ID id)
Return the attributes for an intrinsic.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void PromoteMemToReg(ArrayRef< AllocaInst * > Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)
Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...
auto pred_end(const MachineBasicBlock *BB)
auto successors(const MachineBasicBlock *BB)
bool operator!=(uint64_t V1, const APInt &V2)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
auto unique(Range &&R, Predicate P)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeList AS)
Parse out statepoint directives from the function attributes present in AS.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
@ GCTransition
Indicates that this statepoint is a transition from GC-aware code to code that is not GC-aware.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
auto pred_begin(const MachineBasicBlock *BB)
std::unique_ptr< GCStrategy > getGCStrategy(const StringRef Name)
Lookup the GCStrategy object associated with the given gc name.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
bool isStatepointDirectiveAttr(Attribute Attr)
Return true if the Attr is an attribute that is a statepoint directive.
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, const TargetLibraryInfo &)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Call sites that get wrapped by a gc.statepoint (currently only in RewriteStatepointsForGC and potenti...
std::optional< uint32_t > NumPatchBytes
std::optional< uint64_t > StatepointID
static const uint64_t DefaultStatepointID