LLVM: lib/CodeGen/RegisterCoalescer.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
56#include
57#include
58#include
59#include
60#include
61#include
62#include
63
64using namespace llvm;
65
66#define DEBUG_TYPE "regalloc"
67
68STATISTIC(numJoins, "Number of interval joins performed");
69STATISTIC(numCrossRCs, "Number of cross class joins performed");
70STATISTIC(numCommutes, "Number of instruction commuting performed");
71STATISTIC(numExtends, "Number of copies extended");
72STATISTIC(NumReMats, "Number of instructions re-materialized");
73STATISTIC(NumInflated, "Number of register classes inflated");
74STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");
75STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved");
76STATISTIC(NumShrinkToUses, "Number of shrinkToUses called");
77
79 cl::desc("Coalesce copies (default=true)"),
81
83 cl::desc("Apply the terminal rule"),
85
86
88 "join-splitedges",
89 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);
90
91
93 "join-globalcopies",
94 cl::desc("Coalesce copies that span blocks (default=subtarget)"),
96
98 "verify-coalescing",
99 cl::desc("Verify machine instrs before and after register coalescing"),
101
103 "late-remat-update-threshold", cl::Hidden,
104 cl::desc("During rematerialization for a copy, if the def instruction has "
105 "many other copy uses to be rematerialized, delay the multiple "
106 "separate live interval update work and do them all at once after "
107 "all those rematerialization are done. It will save a lot of "
108 "repeated work. "),
110
112 "large-interval-size-threshold", cl::Hidden,
113 cl::desc("If the valnos size of an interval is larger than the threshold, "
114 "it is regarded as a large interval. "),
116
118 "large-interval-freq-threshold", cl::Hidden,
119 cl::desc("For a large interval, if it is coalesced with other live "
120 "intervals many times more than the threshold, stop its "
121 "coalescing to control the compile time. "),
123
124namespace {
125
126class JoinVals;
127
137
138
139 struct PHIValPos {
142 unsigned SubReg;
143 };
144
145
146 DenseMap<unsigned, PHIValPos> PHIValToPos;
147
148
149
150 DenseMap<Register, SmallVector<unsigned, 2>> RegToPHIIdx;
151
152
153
154
155 using DbgValueLoc = std::pair<SlotIndex, MachineInstr *>;
156 DenseMap<Register, std::vector> DbgVRegToValues;
157
158
159
160 LaneBitmask ShrinkMask;
161
162
163
164 bool ShrinkMainRange = false;
165
166
167
168 bool JoinGlobalCopies = false;
169
170
171
172 bool JoinSplitEdges = false;
173
174
175 SmallVector<MachineInstr *, 8> WorkList;
176 SmallVector<MachineInstr *, 8> LocalWorkList;
177
178
179
180 SmallPtrSet<MachineInstr *, 8> ErasedInstrs;
181
182
183 SmallVector<MachineInstr *, 8> DeadDefs;
184
185
187
188
189
190
191 DenseSet ToBeUpdated;
192
193
194
195 DenseMap<Register, unsigned long> LargeLIVisitCounter;
196
197
198 void eliminateDeadDefs(LiveRangeEdit *Edit = nullptr);
199
200
201 void LRE_WillEraseInstruction(MachineInstr *MI) override;
202
203
204 void coalesceLocals();
205
206
207 void joinAllIntervals();
208
209
210
211 void copyCoalesceInMBB(MachineBasicBlock *MBB);
212
213
214
216
217
218
219
220
221
222 void lateLiveIntervalUpdate();
223
224
225
226
227 bool copyValueUndefInPredecessors(LiveRange &S, const MachineBasicBlock *MBB,
228 LiveQueryResult SLRQ);
229
230
231
232 void setUndefOnPrunedSubRegUses(LiveInterval &LI, Register Reg,
233 LaneBitmask PrunedLanes);
234
235
236
237
238
239
240 bool joinCopy(MachineInstr *CopyMI, bool &Again,
241 SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);
242
243
244
245
246 bool joinIntervals(CoalescerPair &CP);
247
248
249 bool joinVirtRegs(CoalescerPair &CP);
250
251
252
253
254 bool isHighCostLiveInterval(LiveInterval &LI);
255
256
257 bool joinReservedPhysReg(CoalescerPair &CP);
258
259
260
261
262
263
264 void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
265 LaneBitmask LaneMask, CoalescerPair &CP,
266 unsigned DstIdx);
267
268
269
271 LaneBitmask LaneMask, const CoalescerPair &CP);
272
273
274
275
276
277 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
278
279
280
281 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
282 VNInfo *AValNo, VNInfo *BValNo);
283
284
285
286
287
288
289
290
291
292 std::pair<bool, bool> removeCopyByCommutingDef(const CoalescerPair &CP,
293 MachineInstr *CopyMI);
294
295
296 bool removePartialRedundancy(const CoalescerPair &CP, MachineInstr &CopyMI);
297
298
299
300 bool reMaterializeDef(const CoalescerPair &CP, MachineInstr *CopyMI,
301 bool &IsDefCopy);
302
303
304 bool canJoinPhys(const CoalescerPair &CP);
305
306
307
308
309
310 void updateRegDefsUses(Register SrcReg, Register DstReg, unsigned SubIdx);
311
312
313
314
315
316
317
318
319 void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
320 MachineOperand &MO, unsigned SubRegIdx);
321
322
323
324
325
326 MachineInstr *eliminateUndefCopy(MachineInstr *CopyMI);
327
328
329
330
331
332
333
334
335
336
337
338
339
340 bool applyTerminalRule(const MachineInstr &Copy) const;
341
342
343
344
346 SmallVectorImpl<MachineInstr *> *Dead = nullptr) {
347 NumShrinkToUses++;
348 if (LIS->shrinkToUses(LI, Dead)) {
349
350
352 LIS->splitSeparateComponents(*LI, SplitLIs);
353 }
354 }
355
356
357
358
359
360 void deleteInstr(MachineInstr *MI) {
361 ErasedInstrs.insert(MI);
362 LIS->RemoveMachineInstrFromMaps(*MI);
363 MI->eraseFromParent();
364 }
365
366
368
369
370
371
372 void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,
374 JoinVals &RHSVals);
375
377 LiveRange &RegRange, JoinVals &Vals2);
378
379public:
380
381 RegisterCoalescer() = default;
382 RegisterCoalescer &operator=(RegisterCoalescer &&Other) = default;
383
384 RegisterCoalescer(LiveIntervals *LIS, SlotIndexes *SI,
385 const MachineLoopInfo *Loops)
386 : LIS(LIS), SI(SI), Loops(Loops) {}
387
388 bool run(MachineFunction &MF);
389};
390
392public:
393 static char ID;
394
395 RegisterCoalescerLegacy() : MachineFunctionPass(ID) {
397 }
398
399 void getAnalysisUsage(AnalysisUsage &AU) const override;
400
401 MachineFunctionProperties getClearedProperties() const override {
402 return MachineFunctionProperties().setIsSSA();
403 }
404
405
406 bool runOnMachineFunction(MachineFunction &) override;
407};
408
409}
410
411char RegisterCoalescerLegacy::ID = 0;
412
414
416 "Register Coalescer", false, false)
422
425 Register &Dst, unsigned &SrcSub,
426 unsigned &DstSub) {
427 if (MI->isCopy()) {
428 Dst = MI->getOperand(0).getReg();
429 DstSub = MI->getOperand(0).getSubReg();
430 Src = MI->getOperand(1).getReg();
431 SrcSub = MI->getOperand(1).getSubReg();
432 } else if (MI->isSubregToReg()) {
433 Dst = MI->getOperand(0).getReg();
434 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
435 MI->getOperand(3).getImm());
436 Src = MI->getOperand(2).getReg();
437 SrcSub = MI->getOperand(2).getSubReg();
438 } else
439 return false;
440 return true;
441}
442
443
444
445
446
447
449 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
450 return false;
451
452 for (const auto &MI : *MBB) {
453 if (.isCopyLike() &&
.isUnconditionalBranch())
454 return false;
455 }
456 return true;
457}
458
460 SrcReg = DstReg = Register();
461 SrcIdx = DstIdx = 0;
462 NewRC = nullptr;
463 Flipped = CrossClass = false;
464
466 unsigned SrcSub = 0, DstSub = 0;
467 if ((TRI, MI, Src, Dst, SrcSub, DstSub))
468 return false;
469 Partial = SrcSub || DstSub;
470
471
472 if (Src.isPhysical()) {
473 if (Dst.isPhysical())
474 return false;
477 Flipped = true;
478 }
479
482
483 if (Dst.isPhysical()) {
484
485 if (DstSub) {
486 Dst = TRI.getSubReg(Dst, DstSub);
487 if (!Dst)
488 return false;
489 DstSub = 0;
490 }
491
492
493 if (SrcSub) {
494 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, SrcRC);
495 if (!Dst)
496 return false;
497 } else if (!SrcRC->contains(Dst)) {
498 return false;
499 }
500 } else {
501
503
504
505 if (SrcSub && DstSub) {
506
507 if (Src == Dst && SrcSub != DstSub)
508 return false;
509
510 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, SrcIdx,
511 DstIdx);
512 if (!NewRC)
513 return false;
514 } else if (DstSub) {
515
516 SrcIdx = DstSub;
517 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
518 } else if (SrcSub) {
519
520 DstIdx = SrcSub;
521 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
522 } else {
523
524 NewRC = TRI.getCommonSubClass(DstRC, SrcRC);
525 }
526
527
528 if (!NewRC)
529 return false;
530
531
532
533 if (DstIdx && !SrcIdx) {
536 Flipped = !Flipped;
537 }
538
539 CrossClass = NewRC != DstRC || NewRC != SrcRC;
540 }
541
542 assert(Src.isVirtual() && "Src must be virtual");
543 assert(!(Dst.isPhysical() && DstSub) && "Cannot have a physical SubIdx");
544 SrcReg = Src;
545 DstReg = Dst;
546 return true;
547}
548
550 if (DstReg.isPhysical())
551 return false;
554 Flipped = !Flipped;
555 return true;
556}
557
559 if ()
560 return false;
562 unsigned SrcSub = 0, DstSub = 0;
563 if ((TRI, MI, Src, Dst, SrcSub, DstSub))
564 return false;
565
566
567 if (Dst == SrcReg) {
570 } else if (Src != SrcReg) {
571 return false;
572 }
573
574
575 if (DstReg.isPhysical()) {
576 if (!Dst.isPhysical())
577 return false;
578 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.");
579
580 if (DstSub)
581 Dst = TRI.getSubReg(Dst, DstSub);
582
583 if (!SrcSub)
584 return DstReg == Dst;
585
586 return Register(TRI.getSubReg(DstReg, SrcSub)) == Dst;
587 }
588
589
590 if (DstReg != Dst)
591 return false;
592
593 return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
594 TRI.composeSubRegIndices(DstIdx, DstSub);
595}
596
597void RegisterCoalescerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
607}
608
609void RegisterCoalescer::eliminateDeadDefs(LiveRangeEdit *Edit) {
610 if (Edit) {
612 return;
613 }
615 LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, nullptr, this)
617}
618
619void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
620
622}
623
624bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
626 assert(.isPartial() && "This doesn't work for partial copies.");
627 assert(.isPhys() && "This doesn't work for physreg copies.");
628
630 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
632 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
652 if (BS == IntB.end())
653 return false;
654 VNInfo *BValNo = BS->valno;
655
656
657
658
659 if (BValNo->def != CopyIdx)
660 return false;
661
662
665
666 if (AS == IntA.end())
667 return false;
668 VNInfo *AValNo = AS->valno;
669
670
671
673
674 if (.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
675 return false;
676
677
680 if (ValS == IntB.end())
681 return false;
682
683
684
688 return false;
689
690
691
692
693 if (ValS + 1 != BS)
694 return false;
695
697
698 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
699
700
701
702 BValNo->def = FillerStart;
703
704
705
706
708
709
710 if (BValNo != ValS->valno)
712
713
715
716
719 S.removeSegment(*SS, true);
720 continue;
721 }
722
723 if (!S.getVNInfoAt(FillerStart)) {
726 S.extendInBlock(BBStart, FillerStart);
727 }
728 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
731 if (SubBValNo != SubValSNo)
732 S.MergeValueNumberInto(SubBValNo, SubValSNo);
733 }
734
736
737
738
739 int UIdx =
741 if (UIdx != -1) {
743 }
744
745
747
748
749 bool RecomputeLiveRange = AS->end == CopyIdx;
750 if (!RecomputeLiveRange) {
753 if (SS != S.end() && SS->end == CopyIdx) {
754 RecomputeLiveRange = true;
755 break;
756 }
757 }
758 }
759 if (RecomputeLiveRange)
761
762 ++numExtends;
763 return true;
764}
765
766bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
769
770
772 return true;
773
775 if (ASeg.valno != AValNo)
776 continue;
778 if (BI != IntB.begin())
779 --BI;
780 for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
781 if (BI->valno == BValNo)
782 continue;
783 if (BI->start <= ASeg.start && BI->end > ASeg.start)
784 return true;
785 if (BI->start > ASeg.start && BI->start < ASeg.end)
786 return true;
787 }
788 }
789 return false;
790}
791
792
793
797 const VNInfo *SrcValNo) {
799 bool MergedWithDead = false;
801 if (S.valno != SrcValNo)
802 continue;
803
804
805
806
807
808
812 MergedWithDead = true;
814 }
815 return std::make_pair(Changed, MergedWithDead);
816}
817
818std::pair<bool, bool>
819RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
822
824 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
826 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
852 assert(BValNo != nullptr && BValNo->def == CopyIdx);
853
854
856 assert(AValNo && !AValNo->isUnused() && "COPY source not live");
858 return {false, false};
861 return {false, false};
863 return {false, false};
864
865
867 assert(DefIdx != -1);
868 unsigned UseOpIdx;
870 return {false, false};
871
872
873
874
875
876
877
878
879
880
883 return {false, false};
884
888 return {false, false};
889
890
891
892 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
893 return {false, false};
894
895
896
902 if (US == IntA.end() || US->valno != AValNo)
903 continue;
904
906 return {false, false};
907 }
908
909 LLVM_DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'
911
912
913
917 if (!NewMI)
918 return {false, false};
920 ->constrainRegClass(IntB.reg(), MRI->getRegClass(IntA.reg())))
921 return {false, false};
922 if (NewMI != DefMI) {
927 }
928
929
930
931
932
933
934
935
936
937
938
941 if (UseMO.isUndef())
942 continue;
945
946
947 UseMO.setReg(NewReg);
948 continue;
949 }
952 assert(US != IntA.end() && "Use must be live");
953 if (US->valno != AValNo)
954 continue;
955
956 UseMO.setIsKill(false);
958 UseMO.substPhysReg(NewReg, *TRI);
959 else
960 UseMO.setReg(NewReg);
961 if (UseMI == CopyMI)
962 continue;
964 continue;
967 continue;
968
969
970
973 if (!DVNI)
974 continue;
979 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
980 if (!SubDVNI)
981 continue;
982 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
983 assert(SubBValNo->def == CopyIdx);
984 S.MergeValueNumberInto(SubDVNI, SubBValNo);
985 }
986
987 deleteInstr(UseMI);
988 }
989
990
991
992 bool ShrinkB = false;
1001 }
1006 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
1007
1008
1009
1010
1011
1012
1013 if (!ASubValNo)
1014 continue;
1015 MaskA |= SA.LaneMask;
1016
1019 [&Allocator, &SA, CopyIdx, ASubValNo,
1021 VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
1022 : SR.getVNInfoAt(CopyIdx);
1023 assert(BSubValNo != nullptr);
1024 auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
1025 ShrinkB |= P.second;
1026 if (P.first)
1027 BSubValNo->def = ASubValNo->def;
1028 },
1029 Indexes, *TRI);
1030 }
1031
1032
1033
1035 if ((SB.LaneMask & MaskA).any())
1036 continue;
1038 if (S->start.getBaseIndex() == CopyIdx.getBaseIndex())
1039 SB.removeSegment(*S, true);
1040 }
1041 }
1042
1043 BValNo->def = AValNo->def;
1045 ShrinkB |= P.second;
1046 LLVM_DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
1047
1049
1050 LLVM_DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n');
1051 ++numCommutes;
1052 return {true, ShrinkB};
1053}
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
1106 return false;
1107
1109
1110
1112 return false;
1113
1115 return false;
1116
1118 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
1120 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
1121
1122
1125 assert(AValNo && !AValNo->isUnused() && "COPY source not live");
1127 return false;
1128
1129
1131 return false;
1132
1133
1134
1135 bool FoundReverseCopy = false;
1141 CopyLeftBB = Pred;
1142 continue;
1143 }
1144
1148 CopyLeftBB = Pred;
1149 continue;
1150 }
1151
1152
1153
1154 bool ValB_Changed = false;
1155 for (auto *VNI : IntB.valnos) {
1156 if (VNI->isUnused())
1157 continue;
1158 if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(Pred)) {
1159 ValB_Changed = true;
1160 break;
1161 }
1162 }
1163 if (ValB_Changed) {
1164 CopyLeftBB = Pred;
1165 continue;
1166 }
1167 FoundReverseCopy = true;
1168 }
1169
1170
1171 if (!FoundReverseCopy)
1172 return false;
1173
1174
1175
1176
1177
1178
1179
1180
1181 if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
1182 return false;
1183
1184
1185 if (CopyLeftBB) {
1186
1188
1189
1190
1191
1192 if (InsPos != CopyLeftBB->end()) {
1195 return false;
1196 }
1197
1198 LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
1200
1201
1203 TII->get(TargetOpcode::COPY), IntB.reg())
1210
1211
1212
1213
1214 ErasedInstrs.erase(NewCopyMI);
1215 } else {
1216 LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "
1218 }
1219
1221
1222
1223
1224
1225
1226
1227 deleteInstr(&CopyMI);
1228
1229
1233 &EndPoints);
1235
1236 if (IsUndefCopy) {
1237
1238
1239
1243 if (!IntB.liveAt(UseIdx))
1244 MO.setIsUndef(true);
1245 }
1246 }
1247
1248
1250
1251
1253 EndPoints.clear();
1254 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1255 assert(BValNo && "All sublanes should be live");
1258
1259
1260
1261
1262
1263
1264 for (unsigned I = 0; I != EndPoints.size();) {
1266 EndPoints[I] = EndPoints.back();
1268 continue;
1269 }
1270 ++I;
1271 }
1276 }
1277
1279
1280
1282 return true;
1283}
1284
1285
1286
1288 assert(.isPhysical() && "This code cannot handle physreg aliasing");
1289
1292 continue;
1293
1294
1295 if (Op.getSubReg() == 0 || Op.isUndef())
1296 return true;
1297 }
1298 return false;
1299}
1300
1301bool RegisterCoalescer::reMaterializeDef(const CoalescerPair &CP,
1303 bool &IsDefCopy) {
1304 IsDefCopy = false;
1305 Register SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1306 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1307 Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1308 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1310 return false;
1311
1315 if (!ValNo)
1316 return false;
1318 return false;
1321 return false;
1323 IsDefCopy = true;
1324 return false;
1325 }
1327 return false;
1328
1330 return false;
1331
1333 return false;
1334 bool SawStore = false;
1336 return false;
1338 if (MCID.getNumDefs() != 1)
1339 return false;
1340
1341
1342
1343
1344
1345
1346 if (SrcIdx && DstIdx)
1347 return false;
1348
1349
1353 return false;
1354
1355
1356
1357
1358
1359
1360
1361 if (CopyDstReg.isPhysical() && CP.isPartial()) {
1362 for (MCRegUnit Unit : TRI->regunits(DstReg)) {
1363
1365 continue;
1366
1367
1368
1370 if (LR.liveAt(CopyIdx))
1371 return false;
1372 }
1373 }
1374
1379 Register NewDstReg = DstReg;
1380
1381 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), DefSubIdx);
1382 if (NewDstIdx)
1383 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1384
1385
1386
1387 if (!DefRC->contains(NewDstReg))
1388 return false;
1389 } else {
1390
1391
1393 "Only expect to deal with virtual or physical registers");
1394 }
1395 }
1396
1398 return false;
1399
1407 LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS, nullptr, this);
1411
1412
1413
1414
1415
1416
1418 if (DstIdx != 0) {
1420 if (DefMO.getSubReg() == DstIdx) {
1421 assert(SrcIdx == 0 && CP.isFlipped() &&
1422 "Shouldn't have SrcIdx+DstIdx at this point");
1425 TRI->getCommonSubClass(DefRC, DstRC);
1426 if (CommonRC != nullptr) {
1427 NewRC = CommonRC;
1428
1429
1430
1431
1432
1434 if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1435 MO.setSubReg(0);
1436 }
1437 }
1438
1439 DstIdx = 0;
1440 DefMO.setIsUndef(false);
1441 }
1442 }
1443 }
1444
1445
1446
1454 if (MO.isReg()) {
1456 "No explicit operands after implicit operands.");
1459 "unexpected implicit virtual register def");
1461 }
1462 }
1463
1465 ErasedInstrs.insert(CopyMI);
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1481 i != e; ++i) {
1488 (DefSubIdx &&
1489 ((TRI->getSubReg(MO.getReg(), DefSubIdx) ==
1494 } else {
1496
1497
1498
1499
1500
1501
1502 assert(->shouldTrackSubRegLiveness(DstReg) &&
1503 "subrange update for implicit-def of super register may not be "
1504 "properly handled");
1505 }
1506 }
1507 }
1508
1511
1512 if (DefRC != nullptr) {
1513 if (NewIdx)
1514 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1515 else
1516 NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1517 assert(NewRC && "subreg chosen for remat incompatible with instruction");
1518 }
1519
1520
1523 SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1524 }
1525 MRI->setRegClass(DstReg, NewRC);
1526
1527
1528 updateRegDefsUses(DstReg, DstReg, DstIdx);
1530
1531
1532
1533 if (NewIdx == 0)
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1547 MRI->shouldTrackSubRegLiveness(DstReg)) {
1548 LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstReg);
1549 LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(NewIdx);
1550 LaneBitmask UnusedLanes = FullMask & ~UsedLanes;
1554 }
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1574 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1577 if (!SR.liveAt(DefIndex))
1578 SR.createDeadDef(DefIndex, Alloc);
1579 MaxMask &= ~SR.LaneMask;
1580 }
1581 if (MaxMask.any()) {
1584 }
1585 }
1586
1587
1588
1589
1590
1591
1592
1593
1594
1596
1598 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1599 bool UpdatedSubRanges = false;
1603
1604
1605
1609
1610
1611
1612
1613
1614 if (!SR.liveAt(DefIndex))
1616 },
1618
1620 if ((SR.LaneMask & DstMask).none()) {
1622 << "Removing undefined SubRange "
1624
1626
1627
1629 }
1630
1631
1632
1633
1634
1635 UpdatedSubRanges = true;
1636 }
1637 }
1638 if (UpdatedSubRanges)
1640 }
1642
1643
1645 "Only expect virtual or physical registers in remat");
1646
1647
1648
1649
1650
1652
1653 bool HasDefMatchingCopy = false;
1654 for (auto [OpIndex, Reg] : NewMIImplDefs) {
1655 if (Reg != DstReg)
1656 continue;
1657
1658
1659
1660 if (DstReg != CopyDstReg)
1662 else
1663 HasDefMatchingCopy = true;
1664 }
1665
1666
1667 if (!HasDefMatchingCopy)
1669 CopyDstReg, true , true , false ));
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1691 }
1692
1694
1695
1698
1701 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
1704 }
1705
1707 ++NumReMats;
1708
1709
1710
1711 if (MRI->use_nodbg_empty(SrcReg)) {
1717 UseMO.substPhysReg(DstReg, *TRI);
1718 else
1719 UseMO.setReg(DstReg);
1720
1721
1724 }
1725 }
1726 }
1727
1728 if (ToBeUpdated.count(SrcReg))
1729 return true;
1730
1731 unsigned NumCopyUses = 0;
1733 if (UseMO.getParent()->isCopyLike())
1734 NumCopyUses++;
1735 }
1737
1739 if (!DeadDefs.empty())
1740 eliminateDeadDefs(&Edit);
1741 } else {
1742 ToBeUpdated.insert(SrcReg);
1743 }
1744 return true;
1745}
1746
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1760 unsigned SrcSubIdx = 0, DstSubIdx = 0;
1761 if ((*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1762 return nullptr;
1763
1766
1767 if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1768 LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1770 if ((SR.LaneMask & SrcMask).none())
1771 continue;
1773 return nullptr;
1774 }
1775 } else if (SrcLI.liveAt(Idx))
1776 return nullptr;
1777
1778
1779
1783 assert(Seg != nullptr && "No segment for defining instruction");
1785
1786
1787
1788 if (((V && V->isPHIDef()) || (!V && !DstLI.liveAt(Idx)))) {
1789 for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
1791 if (MO.isReg()) {
1794 } else {
1796 CopyMI->getOpcode() == TargetOpcode::SUBREG_TO_REG);
1798 }
1799 }
1800
1801 CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1802 LLVM_DEBUG(dbgs() << "\tReplaced copy of value with an "
1803 "implicit def\n");
1804 return CopyMI;
1805 }
1806
1807
1808 LLVM_DEBUG(dbgs() << "\tEliminating copy of value\n");
1809
1810
1814
1815
1816 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1818 if ((SR.LaneMask & DstMask).none())
1819 continue;
1820
1824 }
1826 } else
1828
1829
1831 if (MO.isDef() )
1832 continue;
1836 bool isLive;
1837 if (!UseMask.all() && DstLI.hasSubRanges()) {
1838 isLive = false;
1840 if ((SR.LaneMask & UseMask).none())
1841 continue;
1842 if (SR.liveAt(UseIdx)) {
1843 isLive = true;
1844 break;
1845 }
1846 }
1847 } else
1848 isLive = DstLI.liveAt(UseIdx);
1849 if (isLive)
1850 continue;
1852 LLVM_DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
1853 }
1854
1855
1856
1857
1858
1859
1861 if (MO.getReg() == DstReg)
1864
1865 return CopyMI;
1866}
1867
1872 Mask = ~Mask;
1873 bool IsUndef = true;
1875 if ((S.LaneMask & Mask).none())
1876 continue;
1877 if (S.liveAt(UseIdx)) {
1878 IsUndef = false;
1879 break;
1880 }
1881 }
1882 if (IsUndef) {
1884
1885
1886
1887
1889 if (Q.valueOut() == nullptr)
1890 ShrinkMainRange = true;
1891 }
1892}
1893
1894void RegisterCoalescer::updateRegDefsUses(Register SrcReg, Register DstReg,
1895 unsigned SubIdx) {
1896 bool DstIsPhys = DstReg.isPhysical();
1898
1899 if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1902 continue;
1905 continue;
1906
1908 if (MI.isDebugInstr())
1909 continue;
1911 addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1912 }
1913 }
1914
1917 E = MRI->reg_instr_end();
1920
1921
1922
1923
1924
1925
1926 if (SrcReg == DstReg && !Visited.insert(UseMI).second)
1927 continue;
1928
1930 bool Reads, Writes;
1932
1933
1934
1937
1938
1939 for (unsigned Op : Ops) {
1941
1942
1943
1944
1945 if (SubIdx && MO.isDef())
1947
1948
1949
1950 if (MO.isUse() && !MO.isUndef() && !DstIsPhys) {
1951 unsigned SubUseIdx = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
1952 if (SubUseIdx != 0 && MRI->shouldTrackSubRegLiveness(DstReg)) {
1955 LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstInt->reg());
1956 LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);
1957 LaneBitmask UnusedLanes = FullMask & ~UsedLanes;
1959
1960
1961
1962
1964 }
1969 addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);
1970 }
1971 }
1972
1973 if (DstIsPhys)
1975 else
1977 }
1978
1980 dbgs() << "\t\tupdated: ";
1984 });
1985 }
1986}
1987
1988bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1989
1990
1991
1992 if (->isReserved(CP.getDstReg())) {
1993 LLVM_DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
1994 return false;
1995 }
1996
1999 return true;
2000
2002 dbgs() << "\tCannot join complex intervals into reserved register.\n");
2003 return false;
2004}
2005
2006bool RegisterCoalescer::copyValueUndefInPredecessors(
2011
2013 return false;
2014 }
2015 }
2016
2017 return true;
2018}
2019
2020void RegisterCoalescer::setUndefOnPrunedSubRegUses(LiveInterval &LI,
2023
2024
2026 unsigned SubRegIdx = MO.getSubReg();
2027 if (SubRegIdx == 0 || MO.isUndef())
2028 continue;
2029
2030 LaneBitmask SubRegMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
2033 if (!S.liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {
2035 break;
2036 }
2037 }
2038 }
2039
2041
2042
2043
2044
2045
2047}
2048
2049bool RegisterCoalescer::joinCopy(
2052 Again = false;
2054
2056 if (.setRegisters(CopyMI)) {
2058 return false;
2059 }
2060
2061 if (CP.getNewRC()) {
2064 << "are available for allocation\n");
2065 return false;
2066 }
2067
2068 auto SrcRC = MRI->getRegClass(CP.getSrcReg());
2069 auto DstRC = MRI->getRegClass(CP.getDstReg());
2070 unsigned SrcIdx = CP.getSrcIdx();
2071 unsigned DstIdx = CP.getDstIdx();
2072 if (CP.isFlipped()) {
2075 }
2076 if (->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
2077 CP.getNewRC(), *LIS)) {
2078 LLVM_DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");
2079 return false;
2080 }
2081 }
2082
2083
2084
2085
2089 eliminateDeadDefs();
2090 return true;
2091 }
2092
2093
2094 if (.isPhys()) {
2095
2096 if (MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
2097 if (UndefMI->isImplicitDef())
2098 return false;
2099 deleteInstr(CopyMI);
2100 return false;
2101 }
2102 }
2103
2104
2105
2106
2107 if (CP.getSrcReg() == CP.getDstReg()) {
2109 LLVM_DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
2114 assert(ReadVNI && "No value before copy and no flag.");
2115 assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
2116
2117
2120
2121
2127
2128
2129
2130 if (copyValueUndefInPredecessors(S, MBB, SLRQ)) {
2131 LLVM_DEBUG(dbgs() << "Incoming sublane value is undef at copy\n");
2132 PrunedLanes |= S.LaneMask;
2134 }
2135 }
2136 }
2137
2139 if (PrunedLanes.any()) {
2140 LLVM_DEBUG(dbgs() << "Pruning undef incoming lanes: " << PrunedLanes
2141 << '\n');
2142 setUndefOnPrunedSubRegUses(LI, CP.getSrcReg(), PrunedLanes);
2143 }
2144
2145 LLVM_DEBUG(dbgs() << "\tMerged values: " << LI << '\n');
2146 }
2147 deleteInstr(CopyMI);
2148 return true;
2149 }
2150
2151
2152 if (CP.isPhys()) {
2155 << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n');
2156 if (!canJoinPhys(CP)) {
2157
2158
2159 bool IsDefCopy = false;
2160 if (reMaterializeDef(CP, CopyMI, IsDefCopy))
2161 return true;
2162 if (IsDefCopy)
2163 Again = true;
2164 return false;
2165 }
2166 } else {
2167
2170 CP.flip();
2171
2173 dbgs() << "\tConsidering merging to "
2174 << TRI->getRegClassName(CP.getNewRC()) << " with ";
2175 if (CP.getDstIdx() && CP.getSrcIdx())
2177 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
2178 << printReg(CP.getSrcReg()) << " in "
2179 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
2180 else
2182 << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
2183 });
2184 }
2185
2187 ShrinkMainRange = false;
2188
2189
2190
2191
2192
2193 if (!joinIntervals(CP)) {
2194
2195
2196
2197 bool IsDefCopy = false;
2198 if (reMaterializeDef(CP, CopyMI, IsDefCopy))
2199 return true;
2200
2201
2202
2203 if (.isPartial() &&
.isPhys()) {
2204 bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2205 bool Shrink = false;
2207 std::tie(Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2209 deleteInstr(CopyMI);
2210 if (Shrink) {
2211 Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
2214 LLVM_DEBUG(dbgs() << "\t\tshrunk: " << DstLI << '\n');
2215 }
2217 return true;
2218 }
2219 }
2220
2221
2222
2223 if (.isPartial() &&
.isPhys())
2224 if (removePartialRedundancy(CP, *CopyMI))
2225 return true;
2226
2227
2229 Again = true;
2230 return false;
2231 }
2232
2233
2234
2235 if (CP.isCrossClass()) {
2236 ++numCrossRCs;
2237 MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
2238 }
2239
2240
2241
2244
2245
2246
2247
2248 if (ErasedInstrs.erase(CopyMI))
2249
2250 CurrentErasedInstrs.insert(CopyMI);
2251
2252
2253
2254 if (CP.getDstIdx())
2255 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
2256 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
2257
2258
2259 if (ShrinkMask.any()) {
2262 if ((S.LaneMask & ShrinkMask).none())
2263 continue;
2265 << ")\n");
2267 ShrinkMainRange = true;
2268 }
2270 }
2271
2272
2273
2274
2275 if (ToBeUpdated.count(CP.getSrcReg()))
2276 ShrinkMainRange = true;
2277
2278 if (ShrinkMainRange) {
2281 }
2282
2283
2284
2286
2287
2288 TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
2289
2291 dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
2292 << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
2293 dbgs() << "\tResult = ";
2294 if (CP.isPhys())
2296 else
2298 dbgs() << '\n';
2299 });
2300
2301 ++numJoins;
2302 return true;
2303}
2304
2305bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
2308 assert(CP.isPhys() && "Must be a physreg copy");
2309 assert(MRI->isReserved(DstReg) && "Not a reserved register");
2312
2313 assert(RHS.containsOneValue() && "Invalid join with reserved register");
2314
2315
2316
2317
2318
2319
2320
2321
2322 if (->isConstantPhysReg(DstReg)) {
2323 for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2324
2326 if (->isReserved(*RI))
2327 return false;
2328 }
2331 << '\n');
2332 return false;
2333 }
2334 }
2335
2336
2339 !RegMaskUsable.test(DstReg.id())) {
2341 return false;
2342 }
2343 }
2344
2345
2346
2347
2348
2349
2350
2352 if (CP.isFlipped()) {
2353
2354
2355
2356
2357
2358
2359
2360 CopyMI = MRI->getVRegDef(SrcReg);
2361 deleteInstr(CopyMI);
2362 } else {
2363
2364
2365
2366
2367
2368
2369
2370 if (->hasOneNonDBGUse(SrcReg)) {
2372 return false;
2373 }
2374
2376 LLVM_DEBUG(dbgs() << "\t\tComplex control flow!\n");
2377 return false;
2378 }
2379
2381 CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
2384
2385 if (->isConstantPhysReg(DstReg)) {
2386
2387
2388
2393 if (MI->readsRegister(DstReg, TRI)) {
2395 return false;
2396 }
2397 }
2398 }
2399
2400
2401
2402 LLVM_DEBUG(dbgs() << "\t\tRemoving phys reg def of "
2403 << printReg(DstReg, TRI) << " at " << CopyRegIdx << "\n");
2404
2406 deleteInstr(CopyMI);
2407
2408
2409 for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2412 }
2413 }
2414
2415
2416 MRI->clearKillFlags(CP.getSrcReg());
2417
2418 return true;
2419}
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485namespace {
2486
2487
2488
2489
2490
2491class JoinVals {
2492
2494
2495
2497
2498
2499
2500
2501 const unsigned SubIdx;
2502
2503
2504
2505 const LaneBitmask LaneMask;
2506
2507
2508
2509 const bool SubRangeJoin;
2510
2511
2512 const bool TrackSubRegLiveness;
2513
2514
2515 SmallVectorImpl<VNInfo *> &NewVNInfo;
2516
2517 const CoalescerPair &CP;
2518 LiveIntervals *LIS;
2519 SlotIndexes *Indexes;
2520 const TargetRegisterInfo *TRI;
2521
2522
2523
2524 SmallVector<int, 8> Assignments;
2525
2526public:
2527
2528 enum ConflictResolution {
2529
2530 CR_Keep,
2531
2532
2533
2534
2535 CR_Erase,
2536
2537
2538
2539
2540 CR_Merge,
2541
2542
2543
2544
2545
2546 CR_Replace,
2547
2548
2549 CR_Unresolved,
2550
2551
2552 CR_Impossible
2553 };
2554
2555private:
2556
2557
2558
2559 struct Val {
2560 ConflictResolution Resolution = CR_Keep;
2561
2562
2563 LaneBitmask WriteLanes;
2564
2565
2566
2567 LaneBitmask ValidLanes;
2568
2569
2570 VNInfo *RedefVNI = nullptr;
2571
2572
2573 VNInfo *OtherVNI = nullptr;
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586 bool ErasableImplicitDef = false;
2587
2588
2589
2590 bool Pruned = false;
2591
2592
2593 bool PrunedComputed = false;
2594
2595
2596
2597
2598
2599
2600 bool Identical = false;
2601
2602 Val() = default;
2603
2604 bool isAnalyzed() const { return WriteLanes.any(); }
2605
2606
2607
2608 void mustKeepImplicitDef(const TargetRegisterInfo &TRI,
2609 const MachineInstr &ImpDef) {
2611 ErasableImplicitDef = false;
2613 }
2614 };
2615
2616
2618
2619
2620
2621
2622 LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2623
2624
2625 std::pair<const VNInfo *, Register> followCopyChain(const VNInfo *VNI) const;
2626
2627 bool valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2628 const JoinVals &Other) const;
2629
2630
2631
2632
2633
2634
2635
2636
2637 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2638
2639
2640
2641
2642 void computeAssignment(unsigned ValNo, JoinVals &Other);
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659 bool
2660 taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2661 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2662
2663
2664
2665 bool usesLanes(const MachineInstr &MI, Register, unsigned, LaneBitmask) const;
2666
2667
2668
2669
2670
2671
2672
2673 bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2674
2675public:
2676 JoinVals(LiveRange &LR, Register Reg, unsigned SubIdx, LaneBitmask LaneMask,
2677 SmallVectorImpl<VNInfo *> &newVNInfo, const CoalescerPair &cp,
2678 LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2679 bool TrackSubRegLiveness)
2680 : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2681 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2682 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2683 TRI(TRI), Assignments(LR.getNumValNums(), -1),
2684 Vals(LR.getNumValNums()) {}
2685
2686
2687
2688 bool mapValues(JoinVals &Other);
2689
2690
2691
2692 bool resolveConflicts(JoinVals &Other);
2693
2694
2695
2696
2697 void pruneValues(JoinVals &Other, SmallVectorImpl &EndPoints,
2698 bool changeInstrs);
2699
2700
2701
2702
2703 void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2704
2705
2706
2707
2708
2709
2710
2711
2712 void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2713
2714
2715
2716
2717
2718 void eraseInstrs(SmallPtrSetImpl<MachineInstr *> &ErasedInstrs,
2719 SmallVectorImpl &ShrinkRegs,
2720 LiveInterval *LI = nullptr);
2721
2722
2723 void removeImplicitDefs();
2724
2725
2726 const int *getAssignments() const { return Assignments.data(); }
2727
2728
2729 ConflictResolution getResolution(unsigned Num) const {
2730 return Vals[Num].Resolution;
2731 }
2732};
2733
2734}
2735
2737 bool &Redef) const {
2741 continue;
2742 L |= TRI->getSubRegIndexLaneMask(
2743 TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2745 Redef = true;
2746 }
2747 return L;
2748}
2749
2750std::pair<const VNInfo *, Register>
2751JoinVals::followCopyChain(const VNInfo *VNI) const {
2753
2757 assert(MI && "No defining instruction");
2758 if (->isFullCopy())
2759 return std::make_pair(VNI, TrackReg);
2760 Register SrcReg = MI->getOperand(1).getReg();
2762 return std::make_pair(VNI, TrackReg);
2763
2765 const VNInfo *ValueIn;
2766
2769 ValueIn = LRQ.valueIn();
2770 } else {
2771
2772
2773 ValueIn = nullptr;
2775
2776 LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2777 if ((SMask & LaneMask).none())
2778 continue;
2780 if (!ValueIn) {
2781 ValueIn = LRQ.valueIn();
2782 continue;
2783 }
2785 return std::make_pair(VNI, TrackReg);
2786 }
2787 }
2788 if (ValueIn == nullptr) {
2789
2790
2791
2792
2793
2794
2795 return std::make_pair(nullptr, SrcReg);
2796 }
2797 VNI = ValueIn;
2798 TrackReg = SrcReg;
2799 }
2800 return std::make_pair(VNI, TrackReg);
2801}
2802
2803bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2804 const JoinVals &Other) const {
2805 const VNInfo *Orig0;
2807 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2808 if (Orig0 == Value1 && Reg0 == Other.Reg)
2809 return true;
2810
2811 const VNInfo *Orig1;
2813 std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
2814
2815
2816
2817 if (Orig0 == nullptr || Orig1 == nullptr)
2818 return Orig0 == Orig1 && Reg0 == Reg1;
2819
2820
2821
2822
2823
2824 return Orig0->def == Orig1->def && Reg0 == Reg1;
2825}
2826
2827JoinVals::ConflictResolution JoinVals::analyzeValue(unsigned ValNo,
2828 JoinVals &Other) {
2829 Val &V = Vals[ValNo];
2830 assert(.isAnalyzed() && "Value has already been analyzed!");
2834 return CR_Keep;
2835 }
2836
2837
2840
2842 : TRI->getSubRegIndexLaneMask(SubIdx);
2843 V.ValidLanes = V.WriteLanes = Lanes;
2844 } else {
2847 if (SubRangeJoin) {
2848
2852 V.ErasableImplicitDef = true;
2853 }
2854 } else {
2855 bool Redef = false;
2856 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873 if (Redef) {
2875 assert((TrackSubRegLiveness || V.RedefVNI) &&
2876 "Instruction is reading nonexistent value");
2877 if (V.RedefVNI != nullptr) {
2878 computeAssignment(V.RedefVNI->id, Other);
2879 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2880 }
2881 }
2882
2883
2885
2886
2887
2888
2889
2890
2891 V.ErasableImplicitDef = true;
2892 }
2893 }
2894 }
2895
2896
2898
2899
2900
2901
2902
2905
2906
2907
2908 if (OtherVNI->def < VNI->def)
2909 Other.computeAssignment(OtherVNI->id, *this);
2910 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2911
2912
2913 V.OtherVNI = OtherLRQ.valueIn();
2914 return CR_Impossible;
2915 }
2916 V.OtherVNI = OtherVNI;
2917 Val &OtherV = Other.Vals[OtherVNI->id];
2918
2919
2920
2921 if (!OtherV.isAnalyzed() || Other.Assignments[OtherVNI->id] == -1)
2922 return CR_Keep;
2923
2924
2925
2927 return CR_Merge;
2928 if ((V.ValidLanes & OtherV.ValidLanes).any())
2929
2930 return CR_Impossible;
2931 return CR_Merge;
2932 }
2933
2934
2935 V.OtherVNI = OtherLRQ.valueIn();
2936 if (.OtherVNI)
2937
2938 return CR_Keep;
2939
2941
2942
2943
2944 Other.computeAssignment(V.OtherVNI->id, *this);
2945 Val &OtherV = Other.Vals[V.OtherVNI->id];
2946
2947 if (OtherV.ErasableImplicitDef) {
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2964 LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2965 << " extends into "
2967 << ", keeping it.\n");
2968 OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);
2970
2971
2972
2973
2975 dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2976 << " may be live into EH pad successors, keeping it.\n");
2977 OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);
2978 } else {
2979
2980 OtherV.ValidLanes &= ~OtherV.WriteLanes;
2981 }
2982 }
2983
2984
2985
2987 return CR_Replace;
2988
2989
2991 return CR_Erase;
2992
2993
2994
2995 if (CP.isCoalescable(DefMI)) {
2996
2997
2998 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2999 return CR_Erase;
3000 }
3001
3002
3003
3005 return CR_Keep;
3006
3007
3008
3009
3010
3011
3013 valuesIdentical(VNI, V.OtherVNI, Other)) {
3014 V.Identical = true;
3015 return CR_Erase;
3016 }
3017
3018
3019
3020
3021 if (SubRangeJoin)
3022 return CR_Replace;
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036 if ((V.WriteLanes & OtherV.ValidLanes).none())
3037 return CR_Replace;
3038
3039
3040
3041
3042
3043
3044
3045
3046 if (OtherLRQ.isKill()) {
3047
3049 "Only early clobber defs can overlap a kill");
3050 return CR_Impossible;
3051 }
3052
3053
3054
3055
3056
3057 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
3058 return CR_Impossible;
3059
3060 if (TrackSubRegLiveness) {
3062
3063
3064
3065 if (!OtherLI.hasSubRanges()) {
3067 return (OtherMask & V.WriteLanes).none() ? CR_Replace : CR_Impossible;
3068 }
3069
3070
3071
3072
3075 TRI->composeSubRegIndexLaneMask(Other.SubIdx, OtherSR.LaneMask);
3076 if ((OtherMask & V.WriteLanes).none())
3077 continue;
3078
3079 auto OtherSRQ = OtherSR.Query(VNI->def);
3080 if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->def) {
3081
3082 return CR_Impossible;
3083 }
3084 }
3085
3086
3087 return CR_Replace;
3088 }
3089
3090
3091
3092
3095 return CR_Impossible;
3096
3097
3098
3099
3100
3101
3102
3103
3104 return CR_Unresolved;
3105}
3106
3107void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
3108 Val &V = Vals[ValNo];
3109 if (V.isAnalyzed()) {
3110
3111
3112 assert(Assignments[ValNo] != -1 && "Bad recursion?");
3113 return;
3114 }
3115 switch ((V.Resolution = analyzeValue(ValNo, Other))) {
3116 case CR_Erase:
3117 case CR_Merge:
3118
3119 assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
3120 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
3121 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
3124 << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
3125 << V.OtherVNI->def << " --> @"
3126 << NewVNInfo[Assignments[ValNo]]->def << '\n');
3127 break;
3128 case CR_Replace:
3129 case CR_Unresolved: {
3130
3131 assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
3132 Val &OtherV = Other.Vals[V.OtherVNI->id];
3133 OtherV.Pruned = true;
3134 [[fallthrough]];
3135 }
3136 default:
3137
3138 Assignments[ValNo] = NewVNInfo.size();
3140 break;
3141 }
3142}
3143
3144bool JoinVals::mapValues(JoinVals &Other) {
3145 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3146 computeAssignment(i, Other);
3147 if (Vals[i].Resolution == CR_Impossible) {
3150 return false;
3151 }
3152 }
3153 return true;
3154}
3155
3156bool JoinVals::taintExtent(
3158 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
3162
3163
3165 assert(OtherI != Other.LR.end() && "No conflict?");
3166 do {
3167
3168
3170 if (End >= MBBEnd) {
3172 << OtherI->valno->id << '@' << OtherI->start << '\n');
3173 return false;
3174 }
3176 << OtherI->valno->id << '@' << OtherI->start << " to "
3177 << End << '\n');
3178
3180 break;
3181 TaintExtent.push_back(std::make_pair(End, TaintedLanes));
3182
3183
3184 if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
3185 break;
3186
3187
3188 const Val &OV = Other.Vals[OtherI->valno->id];
3189 TaintedLanes &= ~OV.WriteLanes;
3190 if (!OV.RedefVNI)
3191 break;
3192 } while (TaintedLanes.any());
3193 return true;
3194}
3195
3198 if (MI.isDebugOrPseudoInstr())
3199 return false;
3202 continue;
3204 continue;
3205 unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
3206 if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
3207 return true;
3208 }
3209 return false;
3210}
3211
3212bool JoinVals::resolveConflicts(JoinVals &Other) {
3213 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3214 Val &V = Vals[i];
3215 assert(V.Resolution != CR_Impossible && "Unresolvable conflict");
3216 if (V.Resolution != CR_Unresolved)
3217 continue;
3221 if (SubRangeJoin)
3222 return false;
3223
3224 ++NumLaneConflicts;
3225 assert(V.OtherVNI && "Inconsistent conflict resolution.");
3227 const Val &OtherV = Other.Vals[V.OtherVNI->id];
3228
3229
3230
3231
3232 LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
3234 if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
3235
3236 return false;
3237
3238 assert(!TaintExtent.empty() && "There should be at least one conflict.");
3239
3240
3246
3247 ++MI;
3248 }
3249 }
3251 "Interference ends on VNI->def. Should have been handled earlier");
3254 assert(LastMI && "Range must end at a proper instruction");
3255 unsigned TaintNum = 0;
3256 while (true) {
3258 if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
3260 return false;
3261 }
3262
3263 if (&*MI == LastMI) {
3264 if (++TaintNum == TaintExtent.size())
3265 break;
3267 assert(LastMI && "Range must end at a proper instruction");
3268 TaintedLanes = TaintExtent[TaintNum].second;
3269 }
3270 ++MI;
3271 }
3272
3273
3274 V.Resolution = CR_Replace;
3275 ++NumLaneResolves;
3276 }
3277 return true;
3278}
3279
3280bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
3281 Val &V = Vals[ValNo];
3282 if (V.Pruned || V.PrunedComputed)
3283 return V.Pruned;
3284
3285 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
3286 return V.Pruned;
3287
3288
3289
3290 V.PrunedComputed = true;
3291 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
3292 return V.Pruned;
3293}
3294
3295void JoinVals::pruneValues(JoinVals &Other,
3297 bool changeInstrs) {
3298 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3300 switch (Vals[i].Resolution) {
3301 case CR_Keep:
3302 break;
3303 case CR_Replace: {
3304
3306
3307
3308
3309
3310 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
3311 bool EraseImpDef =
3312 OtherV.ErasableImplicitDef && OtherV.Resolution == CR_Keep;
3313 if (.isBlock()) {
3314 if (changeInstrs) {
3315
3316
3317
3324 }
3325 }
3326 }
3327
3328
3329 if (!EraseImpDef)
3331 }
3333 << ": " << Other.LR << '\n');
3334 break;
3335 }
3336 case CR_Erase:
3337 case CR_Merge:
3338 if (isPrunedValue(i, Other)) {
3339
3340
3341
3342
3343 LIS->pruneValue(LR, Def, &EndPoints);
3345 << Def << ": " << LR << '\n');
3346 }
3347 break;
3348 case CR_Unresolved:
3349 case CR_Impossible:
3351 }
3352 }
3353}
3354
3355
3356
3357
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3402
3403 bool DidPrune = false;
3404 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3405 Val &V = Vals[i];
3406
3407
3408 if (V.Resolution != CR_Erase &&
3409 (V.Resolution != CR_Keep || .ErasableImplicitDef ||
.Pruned))
3410 continue;
3411
3412
3415 if (V.Identical)
3416 OtherDef = V.OtherVNI->def;
3417
3418
3419 LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def
3420 << '\n');
3423
3424
3425
3427 if (ValueOut != nullptr &&
3428 (Q.valueIn() == nullptr ||
3429 (V.Identical && V.Resolution == CR_Erase && ValueOut->def == Def))) {
3431 << " at " << Def << "\n");
3433 LIS->pruneValue(S, Def, &EndPoints);
3434 DidPrune = true;
3435
3437
3438 if (V.Identical && S.Query(OtherDef).valueOutOrDead()) {
3439
3440
3441
3443 }
3444
3445
3446
3448 ShrinkMask |= S.LaneMask;
3449 continue;
3450 }
3451
3452
3453
3454
3455
3456
3457 if ((Q.valueIn() != nullptr && Q.valueOut() == nullptr) ||
3461 << "\n");
3462 ShrinkMask |= S.LaneMask;
3463 }
3464 }
3465 }
3466 if (DidPrune)
3468}
3469
3470
3474 if (VNI->def == Def)
3475 return true;
3476 }
3477 return false;
3478}
3479
3480void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
3482
3483 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3484 if (Vals[i].Resolution != CR_Keep)
3485 continue;
3488 continue;
3489 Vals[i].Pruned = true;
3490 ShrinkMainRange = true;
3491 }
3492}
3493
3494void JoinVals::removeImplicitDefs() {
3495 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3496 Val &V = Vals[i];
3497 if (V.Resolution != CR_Keep || .ErasableImplicitDef ||
.Pruned)
3498 continue;
3499
3503 }
3504}
3505
3509 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3510
3513 switch (Vals[i].Resolution) {
3514 case CR_Keep: {
3515
3516
3517
3518 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3519 break;
3520
3521
3522
3523
3524
3525
3526
3527
3528
3530 if (LI != nullptr) {
3533
3534
3535
3536 NewEnd = I->end;
3537 }
3538
3540
3541
3543
3546
3547
3548
3553 continue;
3554 if (I->start > Def)
3555 ED = ED.isValid() ? std::min(ED, I->start) : I->start;
3556 else
3557 LE = LE.isValid() ? std::max(LE, I->end) : I->end;
3558 }
3559 if (LE.isValid())
3560 NewEnd = std::min(NewEnd, LE);
3562 NewEnd = std::min(NewEnd, ED);
3563
3564
3565
3566 if (LE.isValid()) {
3568 if (S != LR.begin())
3569 std::prev(S)->end = NewEnd;
3570 }
3571 }
3573 dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';
3574 if (LI != nullptr)
3575 dbgs() << "\t\t LHS = " << *LI << '\n';
3576 });
3577 [[fallthrough]];
3578 }
3579
3580 case CR_Erase: {
3582 assert(MI && "No instruction to erase");
3583 if (MI->isCopy()) {
3587 }
3589 LLVM_DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
3591 MI->eraseFromParent();
3592 break;
3593 }
3594 default:
3595 break;
3596 }
3597 }
3598}
3599
3600void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
3604 JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask, NewVNInfo,
3605 CP, LIS, TRI, true, true);
3606 JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask, NewVNInfo,
3607 CP, LIS, TRI, true, true);
3608
3609
3610
3611
3612
3613
3614 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
3615
3616
3618 }
3619 if (!LHSVals.resolveConflicts(RHSVals) ||
3620 !RHSVals.resolveConflicts(LHSVals)) {
3621
3622
3624 }
3625
3626
3627
3628
3629
3631 LHSVals.pruneValues(RHSVals, EndPoints, false);
3632 RHSVals.pruneValues(LHSVals, EndPoints, false);
3633
3634 LHSVals.removeImplicitDefs();
3635 RHSVals.removeImplicitDefs();
3636
3638
3639
3640 LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
3641 NewVNInfo);
3642
3644 << LRange << "\n");
3645 if (EndPoints.empty())
3646 return;
3647
3648
3649
3651 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3652 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3653 dbgs() << EndPoints[i];
3654 if (i != n - 1)
3655 dbgs() << ',';
3656 }
3657 dbgs() << ": " << LRange << '\n';
3658 });
3660}
3661
3662void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
3666 unsigned ComposeSubRegIdx) {
3671 if (SR.empty()) {
3673 } else {
3674
3676 joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
3677 }
3678 },
3680}
3681
3682bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {
3684 return false;
3685 auto &Counter = LargeLIVisitCounter[LI.reg()];
3687 Counter++;
3688 return false;
3689 }
3690 return true;
3691}
3692
3693bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
3697 bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
3699 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3701 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3702
3704
3705 if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))
3706 return false;
3707
3708
3709
3710 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3711 return false;
3712
3713
3714 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3715 return false;
3716
3717
3718 if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3720
3721
3722
3723 unsigned DstIdx = CP.getDstIdx();
3724 if (.hasSubRanges()) {
3726 : TRI->getSubRegIndexLaneMask(DstIdx);
3727
3730 } else if (DstIdx != 0) {
3731
3735 }
3736 }
3738 << '\n');
3739
3740
3741 unsigned SrcIdx = CP.getSrcIdx();
3742 if (.hasSubRanges()) {
3744 : TRI->getSubRegIndexLaneMask(SrcIdx);
3745 mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);
3746 } else {
3747
3750 mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);
3751 }
3752 }
3754
3755
3756
3757 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3758
3759 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3760 RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3761 } else if (TrackSubRegLiveness && .getDstIdx() && CP.getSrcIdx()) {
3763 CP.getNewRC()->getLaneMask(), LHS);
3764 mergeSubRangeInto(LHS, RHS, TRI->getSubRegIndexLaneMask(CP.getSrcIdx()), CP,
3765 CP.getDstIdx());
3766 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3767 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3768 }
3769
3770
3771
3772
3773
3775 LHSVals.pruneValues(RHSVals, EndPoints, true);
3776 RHSVals.pruneValues(LHSVals, EndPoints, true);
3777
3778
3779
3781 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3782 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3783 while (!ShrinkRegs.empty())
3785
3786
3787 checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
3788
3789
3790
3791 auto RegIt = RegToPHIIdx.find(CP.getSrcReg());
3792 if (RegIt != RegToPHIIdx.end()) {
3793
3794 for (unsigned InstID : RegIt->second) {
3795 auto PHIIt = PHIValToPos.find(InstID);
3796 assert(PHIIt != PHIValToPos.end());
3798
3799
3801 if (LII == RHS.end() || LII->start > SI)
3802 continue;
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816 if (CP.getSrcIdx() != 0 || CP.getDstIdx() != 0)
3817
3818
3819 if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.getSrcIdx())
3820 continue;
3821
3822
3823 PHIIt->second.Reg = CP.getDstReg();
3824
3825
3826
3827 if (CP.getSrcIdx() != 0)
3828 PHIIt->second.SubReg = CP.getSrcIdx();
3829 }
3830
3831
3832
3833
3834 auto InstrNums = RegIt->second;
3835 RegToPHIIdx.erase(RegIt);
3836
3837
3838
3839 RegIt = RegToPHIIdx.find(CP.getDstReg());
3840 if (RegIt != RegToPHIIdx.end())
3842 else
3843 RegToPHIIdx.insert({CP.getDstReg(), InstrNums});
3844 }
3845
3846
3847 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3848
3849
3850
3851
3852 MRI->clearKillFlags(LHS.reg());
3853 MRI->clearKillFlags(RHS.reg());
3854
3855 if (!EndPoints.empty()) {
3856
3857
3859 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3860 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3861 dbgs() << EndPoints[i];
3862 if (i != n - 1)
3863 dbgs() << ',';
3864 }
3865 dbgs() << ": " << LHS << '\n';
3866 });
3868 }
3869
3870 return true;
3871}
3872
3873bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3874 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3875}
3876
3877void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF) {
3880
3881
3882
3883 auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {
3884 for (auto *X : ToInsert) {
3885 for (const auto &Op : X->debug_operands()) {
3886 if (Op.isReg() && Op.getReg().isVirtual())
3887 DbgVRegToValues[Op.getReg()].push_back({Slot, X});
3888 }
3889 }
3890
3891 ToInsert.clear();
3892 };
3893
3894
3895
3896
3897 for (auto &MBB : MF) {
3899
3901 if (MI.isDebugValue()) {
3903 return MO.isReg() && MO.getReg().isVirtual();
3904 }))
3905 ToInsert.push_back(&MI);
3906 } else if (.isDebugOrPseudoInstr()) {
3908 CloseNewDVRange(CurrentSlot);
3909 }
3910 }
3911
3912
3914 }
3915
3916
3917 for (auto &Pair : DbgVRegToValues)
3919}
3920
3921void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,
3923 JoinVals &LHSVals,
3925 JoinVals &RHSVals) {
3926 auto ScanForDstReg = [&](Register Reg) {
3927 checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
3928 };
3929
3930 auto ScanForSrcReg = [&](Register Reg) {
3931 checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
3932 };
3933
3934
3935 ScanForSrcReg(CP.getSrcReg());
3936 ScanForDstReg(CP.getDstReg());
3937}
3938
3939void RegisterCoalescer::checkMergingChangesDbgValuesImpl(Register Reg,
3942 JoinVals &RegVals) {
3943
3944 auto VRegMapIt = DbgVRegToValues.find(Reg);
3945 if (VRegMapIt == DbgVRegToValues.end())
3946 return;
3947
3948 auto &DbgValueSet = VRegMapIt->second;
3949 auto DbgValueSetIt = DbgValueSet.begin();
3950 auto SegmentIt = OtherLR.begin();
3951
3952 bool LastUndefResult = false;
3954
3955
3956
3957 auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,
3958 &LastUndefIdx](SlotIndex Idx) -> bool {
3959
3960
3961
3962 if (LastUndefIdx == Idx)
3963 return LastUndefResult;
3964
3965
3966
3967
3968
3969 auto OtherIt = RegLR.find(Idx);
3970 if (OtherIt == RegLR.end())
3971 return true;
3972
3973
3974
3975
3976
3977
3978
3979 auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3980 LastUndefResult =
3981 Resolution != JoinVals::CR_Keep && Resolution != JoinVals::CR_Erase;
3982 LastUndefIdx = Idx;
3983 return LastUndefResult;
3984 };
3985
3986
3987
3988
3989 while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {
3990 if (DbgValueSetIt->first < SegmentIt->end) {
3991
3992
3993 if (DbgValueSetIt->first >= SegmentIt->start) {
3994 bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3995 bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3996 if (HasReg && ShouldUndefReg) {
3997
3998 DbgValueSetIt->second->setDebugValueUndef();
3999 continue;
4000 }
4001 }
4002 ++DbgValueSetIt;
4003 } else {
4004 ++SegmentIt;
4005 }
4006 }
4007}
4008
4009namespace {
4010
4011
4012struct MBBPriorityInfo {
4013 MachineBasicBlock *MBB;
4015 bool IsSplit;
4016
4017 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
4018 : MBB(mbb), Depth(depth), IsSplit(issplit) {}
4019};
4020
4021}
4022
4023
4024
4025
4026
4028 const MBBPriorityInfo *RHS) {
4029
4030 if (LHS->Depth != RHS->Depth)
4031 return LHS->Depth > RHS->Depth ? -1 : 1;
4032
4033
4034 if (LHS->IsSplit != RHS->IsSplit)
4035 return LHS->IsSplit ? -1 : 1;
4036
4037
4038
4039 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
4040 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
4041 if (cl != cr)
4042 return cl > cr ? -1 : 1;
4043
4044
4045 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
4046}
4047
4048
4050 if (!Copy->isCopy())
4051 return false;
4052
4053 if (Copy->getOperand(1).isUndef())
4054 return false;
4055
4056 Register SrcReg = Copy->getOperand(1).getReg();
4057 Register DstReg = Copy->getOperand(0).getReg();
4059 return false;
4060
4063}
4064
4065void RegisterCoalescer::lateLiveIntervalUpdate() {
4066 for (Register reg : ToBeUpdated) {
4068 continue;
4071 if (!DeadDefs.empty())
4072 eliminateDeadDefs();
4073 }
4074 ToBeUpdated.clear();
4075}
4076
4077bool RegisterCoalescer::copyCoalesceWorkList(
4079 bool Progress = false;
4082 if ()
4083 continue;
4084
4085
4086 if (ErasedInstrs.count(MI) || CurrentErasedInstrs.count(MI)) {
4087 MI = nullptr;
4088 continue;
4089 }
4090 bool Again = false;
4091 bool Success = joinCopy(MI, Again, CurrentErasedInstrs);
4094 MI = nullptr;
4095 }
4096
4097 if (!CurrentErasedInstrs.empty()) {
4099 if (MI && CurrentErasedInstrs.count(MI))
4100 MI = nullptr;
4101 }
4103 if (MI && CurrentErasedInstrs.count(MI))
4104 MI = nullptr;
4105 }
4106 }
4107 return Progress;
4108}
4109
4110
4111
4114 assert(Copy.isCopyLike());
4115
4116 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
4117 if (&MI != &Copy && MI.isCopyLike())
4118 return false;
4119 return true;
4120}
4121
4122bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
4125 return false;
4127 unsigned SrcSubReg = 0, DstSubReg = 0;
4128 if ((*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
4129 return false;
4130
4132
4133
4134
4136 return false;
4137
4138
4139
4142 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
4143
4144
4145
4146
4147
4148
4149 if (&MI == &Copy || .isCopyLike() || MI.getParent() != OrigBB)
4150 continue;
4151 Register OtherSrcReg, OtherReg;
4152 unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
4153 if ((*TRI, &MI, OtherSrcReg, OtherReg, OtherSrcSubReg,
4154 OtherSubReg))
4155 return false;
4156 if (OtherReg == SrcReg)
4157 OtherReg = OtherSrcReg;
4158
4160 continue;
4161
4164 << '\n');
4165 return true;
4166 }
4167 }
4168 return false;
4169}
4170
4173
4174
4175
4176 const unsigned PrevSize = WorkList.size();
4177 if (JoinGlobalCopies) {
4180
4181
4183 if (.isCopyLike())
4184 continue;
4185 bool ApplyTerminalRule = applyTerminalRule(MI);
4187 if (ApplyTerminalRule)
4189 else
4191 } else {
4192 if (ApplyTerminalRule)
4194 else
4196 }
4197 }
4198
4199 LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
4200 WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
4201 } else {
4203
4204
4206 if (MII.isCopyLike()) {
4207 if (applyTerminalRule(MII))
4209 else
4211 }
4212
4213 WorkList.append(Terminals.begin(), Terminals.end());
4214 }
4215
4216
4217
4219 WorkList.end());
4220 if (copyCoalesceWorkList(CurrList))
4222 std::remove(WorkList.begin() + PrevSize, WorkList.end(), nullptr),
4223 WorkList.end());
4224}
4225
4226void RegisterCoalescer::coalesceLocals() {
4227 copyCoalesceWorkList(LocalWorkList);
4229 if (MI)
4231 }
4232 LocalWorkList.clear();
4233}
4234
4235void RegisterCoalescer::joinAllIntervals() {
4236 LLVM_DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
4237 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.");
4238
4239 std::vector MBBs;
4240 MBBs.reserve(MF->size());
4242 MBBs.push_back(MBBPriorityInfo(&MBB, Loops->getLoopDepth(&MBB),
4244 }
4246
4247
4248 unsigned CurrDepth = std::numeric_limits::max();
4249 for (MBBPriorityInfo &MBB : MBBs) {
4250
4251 if (JoinGlobalCopies && MBB.Depth < CurrDepth) {
4252 coalesceLocals();
4253 CurrDepth = MBB.Depth;
4254 }
4255 copyCoalesceInMBB(MBB.MBB);
4256 }
4257 lateLiveIntervalUpdate();
4258 coalesceLocals();
4259
4260
4261
4262 while (copyCoalesceWorkList(WorkList))
4263 ;
4264 lateLiveIntervalUpdate();
4265}
4266
4274 RegisterCoalescer Impl(&LIS, SI, &Loops);
4275 if (!Impl.run(MF))
4283 return PA;
4284}
4285
4286bool RegisterCoalescerLegacy::runOnMachineFunction(MachineFunction &MF) {
4287 auto *LIS = &getAnalysis().getLIS();
4288 auto *Loops = &getAnalysis().getLI();
4289 auto *SIWrapper = getAnalysisIfAvailable();
4290 SlotIndexes *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;
4291 RegisterCoalescer Impl(LIS, SI, Loops);
4292 return Impl.run(MF);
4293}
4294
4296 LLVM_DEBUG(dbgs() << "********** REGISTER COALESCER **********\n"
4297 << "********** Function: " << fn.getName() << '\n');
4298
4299
4300
4301
4302
4303
4304
4305
4306
4309 dbgs() << "* Skipped as it exposes functions that returns twice.\n");
4310 return false;
4311 }
4312
4313 MF = &fn;
4320 else
4322
4323
4324
4329 unsigned SubReg = DebugPHI.second.SubReg;
4332 PHIValToPos.insert(std::make_pair(DebugPHI.first, P));
4333 RegToPHIIdx[Reg].push_back(DebugPHI.first);
4334 }
4335
4336
4337
4338
4340
4342 MF->verify(LIS, SI, "Before register coalescing", &errs());
4343
4344 DbgVRegToValues.clear();
4346
4348
4349
4351 joinAllIntervals();
4352
4353
4354
4355
4359 << " regs.\n");
4361 if (MRI->reg_nodbg_empty(Reg))
4362 continue;
4363 if (MRI->recomputeRegClass(Reg)) {
4365 << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
4366 ++NumInflated;
4367
4370
4371
4372 if (->shouldTrackSubRegLiveness(Reg)) {
4374 } else {
4375#ifndef NDEBUG
4377
4378
4380 assert((S.LaneMask & ~MaxMask).none());
4381 }
4382#endif
4383 }
4384 }
4385 }
4386 }
4387
4388
4389
4391 auto it = PHIValToPos.find(p.first);
4392 assert(it != PHIValToPos.end());
4393 p.second.Reg = it->second.Reg;
4394 p.second.SubReg = it->second.SubReg;
4395 }
4396
4397 PHIValToPos.clear();
4398 RegToPHIIdx.clear();
4399
4401
4403 MF->verify(LIS, SI, "After register coalescing", &errs());
4404 return true;
4405}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const TargetInstrInfo & TII
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseSet and SmallDenseSet classes.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
A common definition of LaneBitmask for use in TableGen and CodeGen.
Register const TargetRegisterInfo * TRI
Promote Memory to Register
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static cl::opt< bool > UseTerminalRule("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(true), cl::Hidden)
static cl::opt< cl::boolOrDefault > EnableGlobalCopies("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), cl::init(cl::BOU_UNSET), cl::Hidden)
Temporary flag to test global copy optimization.
static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS)
Definition RegisterCoalescer.cpp:4049
static bool isSplitEdge(const MachineBasicBlock *MBB)
Return true if this block should be vacated by the coalescer to eliminate branches.
Definition RegisterCoalescer.cpp:448
static int compareMBBPriority(const MBBPriorityInfo *LHS, const MBBPriorityInfo *RHS)
C-style comparator that sorts first based on the loop depth of the basic block (the unsigned),...
Definition RegisterCoalescer.cpp:4027
static cl::opt< unsigned > LargeIntervalSizeThreshold("large-interval-size-threshold", cl::Hidden, cl::desc("If the valnos size of an interval is larger than the threshold, " "it is regarded as a large interval. "), cl::init(100))
static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def)
Check if any of the subranges of LI contain a definition at Def.
Definition RegisterCoalescer.cpp:3471
static std::pair< bool, bool > addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src, const VNInfo *SrcValNo)
Copy segments with value number SrcValNo from liverange Src to live range @Dst and use value number D...
Definition RegisterCoalescer.cpp:794
static bool isLiveThrough(const LiveQueryResult Q)
Definition RegisterCoalescer.cpp:3358
static bool isTerminalReg(Register DstReg, const MachineInstr &Copy, const MachineRegisterInfo *MRI)
Check if DstReg is a terminal node.
Definition RegisterCoalescer.cpp:4112
static cl::opt< bool > VerifyCoalescing("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden)
register Register static false bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, Register &Src, Register &Dst, unsigned &SrcSub, unsigned &DstSub)
Definition RegisterCoalescer.cpp:423
static cl::opt< bool > EnableJoinSplits("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden)
Temporary flag to test critical edge unsplitting.
static cl::opt< bool > EnableJoining("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true), cl::Hidden)
static cl::opt< unsigned > LargeIntervalFreqThreshold("large-interval-freq-threshold", cl::Hidden, cl::desc("For a large interval, if it is coalesced with other live " "intervals many times more than the threshold, stop its " "coalescing to control the compile time. "), cl::init(256))
static bool definesFullReg(const MachineInstr &MI, Register Reg)
Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister.
Definition RegisterCoalescer.cpp:1287
static cl::opt< unsigned > LateRematUpdateThreshold("late-remat-update-threshold", cl::Hidden, cl::desc("During rematerialization for a copy, if the def instruction has " "many other copy uses to be rematerialized, delay the multiple " "separate live interval update work and do them all at once after " "all those rematerialization are done. It will save a lot of " "repeated work. "), cl::init(100))
SI Optimize VGPR LiveRange
This file defines the SmallPtrSet class.
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)
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness)
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
bool test(unsigned Idx) const
Represents analyses that only rely on functions' control flow.
A helper class for register coalescers.
bool flip()
Swap SrcReg and DstReg.
Definition RegisterCoalescer.cpp:549
bool isCoalescable(const MachineInstr *) const
Return true if MI is a copy instruction that will become an identity copy after coalescing.
Definition RegisterCoalescer.cpp:558
bool setRegisters(const MachineInstr *)
Set registers to match the copy instruction MI.
Definition RegisterCoalescer.cpp:459
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
bool hasSubRanges() const
Returns true if subregister liveness information is available.
SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...
iterator_range< subrange_iterator > subranges()
LLVM_ABI void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
LLVM_ABI void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
LLVM_ABI void clearSubRanges()
Removes all subregister liveness information.
bool hasInterval(Register Reg) const
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
LLVM_ABI bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
LLVM_ABI bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
VNInfo::Allocator & getVNInfoAllocator()
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
LiveInterval & getInterval(Register Reg)
LLVM_ABI void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
void removeInterval(Register Reg)
Interval removal.
LiveRange & getRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit.
LLVM_ABI MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
LiveRange * getCachedRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LLVM_ABI void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LLVM_ABI bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
LLVM_ABI void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
LLVM_ABI void dump() const
LLVM_ABI void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
Result of a LiveRange query.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
bool isKill() const
Return true if the live-in value is killed by this instruction.
Callback methods for LiveRangeEdit owners.
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr)
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled={})
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
This class represents the liveness of a register, stack slot, etc.
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::iterator iterator
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
LLVM_ABI void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
bool liveAt(SlotIndex index) const
LLVM_ABI VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
LLVM_ABI void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...
bool verify() const
Walk the range and assert if any invariants fail to hold.
LLVM_ABI VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
unsigned getNumValNums() const
bool containsOneValue() const
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
LLVM_ABI iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
Wrapper class representing physical registers. Should be passed by value.
An RAII based helper class to modify MachineFunctionProperties when running pass.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
LLVM_ABI bool hasEHPadSuccessor() const
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, raw_ostream *OS=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
LLVM_ABI void setRegisterDefReadUndef(Register Reg, bool IsUndef=true)
Mark all subregister defs of register Reg with the undef flag.
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
filtered_mop_range all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
LLVM_ABI std::pair< bool, bool > readsWritesVirtualRegister(Register Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const
Return a pair of bools (reads, writes) indicating if this instruction reads or writes Reg.
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
LLVM_ABI bool isSafeToMove(bool &SawStore) const
Return true if it is safe to move this instruction.
bool isDebugInstr() const
unsigned getNumOperands() const
Retuns the total number of operands.
LLVM_ABI void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx=nullptr) const
Given the index of a register def operand, check if the register def is tied to a source operand,...
LLVM_ABI int findRegisterUseOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isKill=false) const
Returns the operand index that is a use of the specific register or -1 if it is not found.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
bool isCommutable(QueryType Type=IgnoreBundle) const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
LLVM_ABI void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
LLVM_ABI void substituteRegister(Register FromReg, Register ToReg, unsigned SubIdx, const TargetRegisterInfo &RegInfo)
Replace all occurrences of FromReg with ToReg:SubIdx, properly composing subreg indices where necessa...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
LLVM_ABI void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
LLVM_ABI void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
LLVM_ABI bool allDefsAreDead() const
Return true if all the defs of this instruction are dead.
Analysis pass that exposes the MachineLoopInfo for a machine function.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
LLVM_ABI void substVirtReg(Register Reg, unsigned SubIdx, const TargetRegisterInfo &)
substVirtReg - Substitute the current register with the virtual subregister Reg:SubReg.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsDead(bool Val=true)
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
LLVM_ABI void substPhysReg(MCRegister Reg, const TargetRegisterInfo &)
substPhysReg - Substitute the current register with the physical register Reg, taking any existing Su...
void setIsUndef(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
defusechain_instr_iterator< true, true, false, true > reg_instr_iterator
reg_instr_iterator/reg_instr_begin/reg_instr_end - Walk all defs and uses of the specified register,...
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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.
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
LLVM_ABI void runOnMachineFunction(const MachineFunction &MF, bool Rev=false)
runOnFunction - Prepare to answer questions about MF.
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
Definition RegisterCoalescer.cpp:4268
Wrapper class representing virtual and physical registers.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr unsigned id() const
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
bool isValid() const
Returns true if this is a valid index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the index past the last valid index in the given basic block.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
SlotIndex getIndexBefore(const MachineInstr &MI) const
getIndexBefore - Returns the index of the last indexed instruction before MI, or the start index of i...
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
pointer data()
Return a pointer to the vector's buffer, even if empty().
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum) const
Given a machine instruction descriptor, returns the register class constraint for OpNum,...
bool isReMaterializable(const MachineInstr &MI) const
Return true if the instruction would be materializable at a point in the containing function where al...
virtual bool findCommutedOpIndices(const MachineInstr &MI, unsigned &SrcOpIdx1, unsigned &SrcOpIdx2) const
Returns true iff the routine could find two commutable operands in the given machine instruction.
virtual bool isAsCheapAsAMove(const MachineInstr &MI) const
Return true if the instruction is as cheap as a move instruction.
MachineInstr * commuteInstruction(MachineInstr &MI, bool NewMI=false, unsigned OpIdx1=CommuteAnyOperandIndex, unsigned OpIdx2=CommuteAnyOperandIndex) const
This method commutes the operands of the given machine instruction MI.
static const unsigned CommuteAnyOperandIndex
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual bool enableJoinGlobalCopies() const
True if the subtarget should enable joining global copies.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
VNInfo - Value Number Information.
void markUnused()
Mark this value as unused.
BumpPtrAllocator Allocator
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
static bool allUsesAvailableAt(const MachineInstr *MI, SlotIndex UseIdx, const LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII)
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.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
This namespace contains all of the command line option processing machinery.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
LLVM_ABI char & RegisterCoalescerID
RegisterCoalescer - This pass merges live ranges to eliminate copies.
Definition RegisterCoalescer.cpp:413
LLVM_ABI char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
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...
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
auto unique(Range &&R, Predicate P)
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
LLVM_ABI void initializeRegisterCoalescerLegacyPass(PassRegistry &)
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
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)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
@ Success
The lock was released successfully.
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DWARFExpression::Operation Op
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI void eraseInstrs(ArrayRef< MachineInstr * > DeadInstrs, MachineRegisterInfo &MRI, LostDebugLocObserver *LocObserver=nullptr)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static constexpr LaneBitmask getLane(unsigned Lane)
static constexpr LaneBitmask getAll()
constexpr bool any() const
static constexpr LaneBitmask getNone()
Remat - Information needed to rematerialize at a specific location.
This represents a simple continuous liveness interval for a value.