Lines Matching +full:segment +full:- +full:no +full:- +full:remap
1 //===- RegisterCoalescer.cpp - Generic Register Coalescing Interface ------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 //===----------------------------------------------------------------------===//
69 STATISTIC(NumReMats , "Number of instructions re-materialized");
75 static cl::opt<bool> EnableJoining("join-liveintervals",
79 static cl::opt<bool> UseTerminalRule("terminal-rule",
85 EnableJoinSplits("join-splitedges",
90 EnableGlobalCopies("join-globalcopies",
95 VerifyCoalescing("verify-coalescing",
100 "late-remat-update-threshold", cl::Hidden,
109 "large-interval-size-threshold", cl::Hidden,
115 "large-interval-freq-threshold", cl::Hidden,
150 /// Debug variable location tracking -- for each VReg, maintain an
151 /// ordered-by-slot-index set of DBG_VALUEs, to help quick
168 /// True if the coalescer should aggressively coalesce fall-thru
223 /// has no value defined in the predecessors. If the incoming value is the
272 /// We found a non-trivially-coalescable copy. If the source value number is
283 /// We found a non-trivially-coalescable copy.
288 /// - the first element is true if an interval was modified,
289 /// - the second element is true if the destination interval needs
315 /// %0:sub0<def,read-undef> = ...
316 /// %1 = COPY %0 <-- Coalescing COPY reveals undef
317 /// = use %1:sub1 <-- hidden undef use
342 /// This method does the proper fixing of the live-ranges when the afore
347 if (LIS->shrinkToUses(LI, Dead)) {
351 LIS->splitSeparateComponents(*LI, SplitLIs);
361 LIS->RemoveMachineInstrFromMaps(*MI);
362 MI->eraseFromParent();
407 INITIALIZE_PASS_BEGIN(RegisterCoalescer, "register-coalescer",
413 INITIALIZE_PASS_END(RegisterCoalescer, "register-coalescer",
420 if (MI->isCopy()) {
421 Dst = MI->getOperand(0).getReg();
422 DstSub = MI->getOperand(0).getSubReg();
423 Src = MI->getOperand(1).getReg();
424 SrcSub = MI->getOperand(1).getSubReg();
425 } else if (MI->isSubregToReg()) {
426 Dst = MI->getOperand(0).getReg();
427 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
428 MI->getOperand(3).getImm());
429 Src = MI->getOperand(2).getReg();
430 SrcSub = MI->getOperand(2).getSubReg();
439 /// contain non-branches should also be vacated, but this can be handled by an
440 /// earlier pass similar to early if-conversion.
442 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
473 const MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
487 } else if (!MRI.getRegClass(Src)->contains(Dst)) {
497 // Copies between different sub-registers are never coalescable.
506 // SrcReg will be merged with a sub-register of DstReg.
510 // DstReg will be merged with a sub-register of SrcReg.
514 // This is a straight copy without sub-registers.
522 // Prefer SrcReg to be a sub-register of DstReg.
602 Edit->eliminateDeadDefs(DeadDefs);
621 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
623 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
624 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
626 // We have a non-trivially-coalescable copy with IntA being the source and
634 // B1 = A3 <- this copy
644 VNInfo *BValNo = BS->valno;
649 if (BValNo->def != CopyIdx) return false;
654 // The live segment might not exist after fun with physreg coalescing.
656 VNInfo *AValNo = AS->valno;
660 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);
662 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
665 // Get the Segment in IntB that this value number starts with.
667 IntB.FindSegmentContaining(AValNo->def.getPrevSlot());
671 // Make sure that the end of the live segment is inside the same block as
674 LIS->getInstructionFromIndex(ValS->end.getPrevSlot());
675 if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())
679 // live-range starts. If there are no intervening live segments between them
685 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
689 BValNo->def = FillerStart;
694 IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
697 if (BValNo != ValS->valno)
698 IntB.MergeValueNumberInto(BValNo, ValS->valno);
705 if (SS != S.end() && SlotIndex::isSameInstr(SS->start, SS->end)) {
712 LIS->getMBBStartIdx(LIS->getMBBFromIndex(FillerStart));
716 S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
717 VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
727 ValSEndInst->findRegisterUseOperandIdx(IntB.reg(), /*TRI=*/nullptr, true);
728 if (UIdx != -1) {
729 ValSEndInst->getOperand(UIdx).setIsKill(false);
733 CopyMI->substituteRegister(IntA.reg(), IntB.reg(), 0, *TRI);
736 bool RecomputeLiveRange = AS->end == CopyIdx;
740 if (SS != S.end() && SS->end == CopyIdx) {
759 if (LIS->hasPHIKill(IntA, AValNo))
762 for (LiveRange::Segment &ASeg : IntA.segments) {
766 --BI;
767 for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
768 if (BI->valno == BValNo)
770 if (BI->start <= ASeg.start && BI->end > ASeg.start)
772 if (BI->start > ASeg.start && BI->start < ASeg.end)
786 for (const LiveRange::Segment &S : Src.segments) {
789 // This is adding a segment from Src that ends in a copy that is about
790 // to be removed. This segment is going to be merged with a pre-existing
791 // segment in Dst. This works, except in cases when the corresponding
792 // segment in Dst is dead. For example: adding [192r,208r:1) from Src
795 LiveRange::Segment Added = LiveRange::Segment(S.start, S.end, DstValNo);
796 LiveRange::Segment &Merged = *Dst.addSegment(Added);
810 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
812 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
814 // We found a non-trivially-coalescable copy with IntA being the source and
822 // B1 = A3 <- this copy
824 // = op A3 <- more uses
830 // B1 = B2 <- now an identity copy
832 // = op B2 <- more uses
836 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
838 assert(BValNo != nullptr && BValNo->def == CopyIdx);
842 assert(AValNo && !AValNo->isUnused() && "COPY source not live");
843 if (AValNo->isPHIDef())
845 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);
848 if (!DefMI->isCommutable())
850 // If DefMI is a two-address instruction then commuting it will change the
852 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg(), /*TRI=*/nullptr);
853 assert(DefIdx != -1);
855 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
865 // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,
866 // op#2<->op#3) of commute transformation should be considered/tried here.
868 if (!TII->findCommutedOpIndices(*DefMI, UseOpIdx, NewDstIdx))
871 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
873 if (NewReg != IntB.reg() || !IntB.Query(AValNo->def).isKill())
876 // Make sure there are no other definitions of IntB that would reach the
883 for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg())) {
885 unsigned OpNo = &MO - &UseMI->getOperand(0);
886 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI);
888 if (US == IntA.end() || US->valno != AValNo)
891 if (UseMI->isRegTiedToDefOperand(OpNo))
895 LLVM_DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'
900 MachineBasicBlock *MBB = DefMI->getParent();
902 TII->commuteInstruction(*DefMI, false, UseOpIdx, NewDstIdx);
906 !MRI->constrainRegClass(IntB.reg(), MRI->getRegClass(IntA.reg())))
909 LIS->ReplaceMachineInstrInMaps(*DefMI, *NewMI);
911 MBB->insert(Pos, NewMI);
912 MBB->erase(DefMI);
926 llvm::make_early_inc_range(MRI->use_operands(IntA.reg()))) {
930 if (UseMI->isDebugInstr()) {
936 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI).getRegSlot(true);
939 if (US->valno != AValNo)
941 // Kill flags are no longer accurate. They are recomputed after RA.
949 if (!UseMI->isCopy())
951 if (UseMI->getOperand(0).getReg() != IntB.reg() ||
952 UseMI->getOperand(0).getSubReg())
962 assert(DVNI->def == DefIdx);
969 assert(SubBValNo->def == CopyIdx);
979 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
982 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg());
985 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntB.reg());
990 const SlotIndexes &Indexes = *LIS->getSlotIndexes();
1013 BSubValNo->def = ASubValNo->def;
1023 if (LiveRange::Segment *S = SB.getSegmentContaining(CopyIdx))
1024 if (S->start.getBaseIndex() == CopyIdx.getBaseIndex())
1029 BValNo->def = AValNo->def;
1034 LIS->removeVRegDefAt(IntA, AValNo->def);
1068 /// BB0/BB2: ----
1072 /// |-------
1080 /// 2. No B is referenced from the start of BB2 to B = A.
1081 /// 3. No B is defined from A = B to the end of BB0.
1104 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
1106 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
1109 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);
1111 assert(AValNo && !AValNo->isUnused() && "COPY source not live");
1112 if (!AValNo->isPHIDef())
1115 // No B is referenced before CopyMI in MBB.
1116 if (IntB.overlaps(LIS->getMBBStartIdx(&MBB), CopyIdx))
1119 // MBB has two predecessors: one contains A = B so no copy will be inserted
1124 VNInfo *PVal = IntA.getVNInfoBefore(LIS->getMBBEndIdx(Pred));
1125 MachineInstr *DefMI = LIS->getInstructionFromIndex(PVal->def);
1126 if (!DefMI || !DefMI->isFullCopy()) {
1131 if (DefMI->getOperand(0).getReg() != IntA.reg() ||
1132 DefMI->getOperand(1).getReg() != IntB.reg() ||
1133 DefMI->getParent() != Pred) {
1142 if (VNI->isUnused())
1144 if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(Pred)) {
1156 // If no reverse copy is found in predecessors, nothing to do.
1167 if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
1173 auto InsPos = CopyLeftBB->getFirstTerminator();
1178 if (InsPos != CopyLeftBB->end()) {
1179 SlotIndex InsPosIdx = LIS->getInstructionIndex(*InsPos).getRegSlot(true);
1180 if (IntB.overlaps(InsPosIdx, LIS->getMBBEndIdx(CopyLeftBB)))
1189 TII->get(TargetOpcode::COPY), IntB.reg())
1192 LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
1193 IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1195 SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1209 // Note: This is fine to remove the copy before updating the live-ranges.
1210 // While updating the live-ranges, we only look at slot indices and
1218 LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),
1220 BValNo->markUnused();
1226 for (MachineOperand &MO : MRI->use_nodbg_operands(IntB.reg())) {
1228 SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1235 LIS->extendToIndices(IntB, EndPoints);
1242 LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
1243 BValNo->markUnused();
1248 // endpoint; there is no other situation here that there could be a use at
1260 *LIS->getSlotIndexes());
1261 LIS->extendToIndices(SR, EndPoints, Undefs);
1266 // Finally, update the live-range of IntA.
1298 LiveInterval &SrcInt = LIS->getInterval(SrcReg);
1299 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1303 if (ValNo->isPHIDef() || ValNo->isUnused())
1305 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
1308 if (DefMI->isCopyLike()) {
1312 if (!TII->isAsCheapAsAMove(*DefMI))
1323 if (!DefMI->isSafeToMove(AA, SawStore))
1325 const MCInstrDesc &MCID = DefMI->getDesc();
1328 // Only support subregister destinations when the def is read-undef.
1329 MachineOperand &DstOperand = CopyMI->getOperand(0);
1342 const unsigned DefSubIdx = DefMI->getOperand(0).getSubReg();
1343 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
1344 if (!DefMI->isImplicitDef()) {
1348 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), DefSubIdx);
1350 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1354 if (!DefRC->contains(NewDstReg))
1369 DebugLoc DL = CopyMI->getDebugLoc();
1370 MachineBasicBlock *MBB = CopyMI->getParent();
1388 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
1390 TRI->getCommonSubClass(DefRC, DstRC);
1413 ImplicitOps.reserve(CopyMI->getNumOperands() -
1414 CopyMI->getDesc().getNumOperands());
1415 for (unsigned I = CopyMI->getDesc().getNumOperands(),
1416 E = CopyMI->getNumOperands();
1418 MachineOperand &MO = CopyMI->getOperand(I);
1420 assert(MO.isImplicit() && "No explicit operands after implicit operands.");
1428 CopyMI->eraseFromParent();
1435 // We also expect to have tied implicit-defs of super registers originating
1437 // $edi = MOV32r0 implicit-def dead $eflags, implicit-def $rdi
1438 // undef %0.sub_32bit = MOV32r0 implicit-def dead $eflags, implicit-def %0
1440 // The implicit-def of the super register may have been reduced to
1459 ((TRI->getSubReg(MO.getReg(), DefSubIdx) ==
1461 TRI->isSubRegisterEq(NewMI.getOperand(0).getReg(),
1472 assert(!MRI->shouldTrackSubRegLiveness(DstReg) &&
1473 "subrange update for implicit-def of super register may not be "
1484 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1486 NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1489 // Remap subranges to new lanemask and change register class.
1490 LiveInterval &DstInt = LIS->getInterval(DstReg);
1492 SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1494 MRI->setRegClass(DstReg, NewRC);
1511 // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1519 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1522 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1523 VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1531 SR->createDeadDef(DefIndex, Alloc);
1537 // %1:sub1<def,read-undef> = LOAD CONSTANT 1
1540 // %2:sub1<def, read-undef> = LOAD CONSTANT 1
1545 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1546 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1550 VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();
1558 // VNI is in ValNo - remove any segments in this SubRange that have
1582 // The New instruction may be defining a sub-register of what's actually
1593 // Record small dead def live-ranges for all the subregisters
1604 // dead ECX = remat ; implicit-def CL
1607 // no live-ranges would have been created for ECX.
1609 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1610 for (MCRegUnit Unit : TRI->regunits(NewMI.getOperand(0).getReg()))
1611 if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1612 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1621 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1623 for (MCRegUnit Unit : TRI->regunits(Reg))
1624 if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1625 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1633 if (MRI->use_nodbg_empty(SrcReg)) {
1635 llvm::make_early_inc_range(MRI->use_operands(SrcReg))) {
1637 if (UseMI->isDebugInstr()) {
1644 MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);
1654 for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
1655 if (UseMO.getParent()->isCopyLike())
1686 SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);
1687 const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
1690 LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1700 // If the undef copy defines a live-out value (i.e. an input to a PHI def),
1702 LiveInterval &DstLI = LIS->getInterval(DstReg);
1704 LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);
1705 assert(Seg != nullptr && "No segment for defining instruction");
1706 VNInfo *V = DstLI.getVNInfoAt(Seg->end);
1710 if (((V && V->isPHIDef()) || (!V && !DstLI.liveAt(Idx)))) {
1711 for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
1712 MachineOperand &MO = CopyMI->getOperand(i-1);
1715 CopyMI->removeOperand(i - 1);
1718 CopyMI->getOpcode() == TargetOpcode::SUBREG_TO_REG);
1719 CopyMI->removeOperand(i-1);
1723 CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1738 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1744 assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));
1749 LIS->removeVRegDefAt(DstLI, RegIndex);
1752 for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
1756 SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1757 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
1782 for (MachineOperand &MO : CopyMI->all_defs())
1785 LIS->shrinkToUses(&DstLI);
1792 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1809 // use was ending a live segment there.
1819 LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
1821 if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1822 for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
1829 SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
1836 I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
1840 // Each instruction can only be rewritten once because sub-register
1842 // the UseMI operands removes them from the SrcReg use-def chain, but when
1850 std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
1852 // If SrcReg wasn't read, it may still be the case that DstReg is live-in
1853 // because SrcReg is a sub-register.
1854 if (DstInt && !Reads && SubIdx && !UseMI->isDebugInstr())
1855 Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
1859 MachineOperand &MO = UseMI->getOperand(Op);
1861 // Adjust <undef> flags in case of sub-register joins. We don't want to
1862 // turn a full def into a read-modify-write sub-register def and vice
1870 unsigned SubUseIdx = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
1871 if (SubUseIdx != 0 && MRI->shouldTrackSubRegLiveness(DstReg)) {
1872 if (!DstInt->hasSubRanges()) {
1873 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
1874 LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstInt->reg());
1875 LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);
1877 DstInt->createSubRangeFrom(Allocator, UsedLanes, *DstInt);
1878 // The unused lanes are just empty live-ranges at this point.
1882 DstInt->createSubRange(Allocator, UnusedLanes);
1884 SlotIndex MIIdx = UseMI->isDebugInstr()
1885 ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
1886 : LIS->getInstructionIndex(*UseMI);
1900 if (!UseMI->isDebugInstr())
1901 dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
1911 if (!MRI->isReserved(CP.getDstReg())) {
1916 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
1927 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
1928 SlotIndex PredEnd = LIS->getMBBEndIdx(Pred);
1931 if (V->id != SLRQ.valueOutOrDead()->id)
1942 // If we had other instructions in the segment reading the undef sublane
1944 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
1949 LaneBitmask SubRegMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1950 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
1965 LIS->shrinkToUses(&LI);
1972 LLVM_DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);
1981 auto SrcRC = MRI->getRegClass(CP.getSrcReg());
1982 auto DstRC = MRI->getRegClass(CP.getDstReg());
1989 if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1999 if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
2010 if (UndefMI->isImplicitDef())
2021 LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
2023 const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
2027 assert(ReadVNI && "No value before copy and no <undef> flag.");
2032 MachineBasicBlock *MBB = CopyMI->getParent();
2081 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
2082 LIS->getInterval(CP.getDstReg()).size())
2087 << TRI->getRegClassName(CP.getNewRC()) << " with ";
2090 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
2092 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
2126 LiveInterval &DstLI = LIS->getInterval(DstReg);
2147 // Coalescing to a virtual register that is of a sub-register class of the
2151 MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
2154 // Removing sub-register copies can ease the register class constraints.
2174 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
2180 LIS->shrinkToUses(S, LI.reg());
2188 // is not up-to-date, need to update the merged live interval here.
2193 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
2199 LIS->removeInterval(CP.getSrcReg());
2202 TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
2206 << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
2211 dbgs() << LIS->getInterval(CP.getDstReg());
2223 assert(MRI->isReserved(DstReg) && "Not a reserved register");
2224 LiveInterval &RHS = LIS->getInterval(SrcReg);
2232 // - we don't properly track the live range of reserved registers.
2236 if (!MRI->isConstantPhysReg(DstReg)) {
2237 for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2240 if (!MRI->isReserved(*RI))
2243 if (RHS.overlaps(LIS->getRegUnit(Unit))) {
2252 if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
2269 // ... //< no other def of %physreg_x here
2274 CopyMI = MRI->getVRegDef(SrcReg);
2279 // ... //< no other def or use of %physreg_x here
2284 if (!MRI->hasOneNonDBGUse(SrcReg)) {
2289 if (!LIS->intervalIsInOneMBB(RHS)) {
2294 MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
2295 CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
2296 SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
2297 SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
2299 if (!MRI->isConstantPhysReg(DstReg)) {
2300 // We checked above that there are no interfering defs of the physical
2303 SlotIndexes *Indexes = LIS->getSlotIndexes();
2304 for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
2305 SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
2306 MachineInstr *MI = LIS->getInstructionFromIndex(SI);
2307 if (MI->readsRegister(DstReg, TRI)) {
2319 LIS->removePhysRegDefAt(DstReg.asMCReg(), CopyRegIdx);
2323 for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2324 LiveRange &LR = LIS->getRegUnit(Unit);
2325 LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
2330 MRI->clearKillFlags(CP.getSrcReg());
2335 //===----------------------------------------------------------------------===//
2337 //===----------------------------------------------------------------------===//
2340 // there is no interference to consider. It is quite common, though, to have
2344 // The live range of a single SSA value forms a sub-tree of the dominator tree.
2370 // %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext.
2375 // %dst:ssub0<def,read-undef> = FOO
2384 // will have different value numbers for both FOO and BAR, but there is no
2402 /// joined. Objects of this class are always created in pairs - one for each
2443 /// No overlap, simply keep this value.
2470 /// Per-value info for LI. The lane bit masks are all relative to the final
2492 /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2563 /// 1 %dst = VLOAD <-- Define all lanes in %dst
2564 /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
2565 /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
2566 /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2584 /// %src = COPY %dst <-- This value to be pruned.
2585 /// %dst = COPY %src <-- This value is a copy of a pruned value.
2595 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2596 TRI(TRI), Assignments(LR.getNumValNums(), -1),
2615 /// no useful information and can be removed.
2652 for (const MachineOperand &MO : DefMI->all_defs()) {
2655 L |= TRI->getSubRegIndexLaneMask(
2656 TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2667 while (!VNI->isPHIDef()) {
2668 SlotIndex Def = VNI->def;
2669 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2670 assert(MI && "No defining instruction");
2671 if (!MI->isFullCopy())
2673 Register SrcReg = MI->getOperand(1).getReg();
2677 const LiveInterval &LI = LIS->getInterval(SrcReg);
2679 // No subrange involved.
2689 LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2737 return Orig0->def == Orig1->def && Reg0 == Reg1;
2745 if (VNI->isUnused()) {
2752 if (VNI->isPHIDef()) {
2755 : TRI->getSubRegIndexLaneMask(SubIdx);
2758 DefMI = Indexes->getInstructionFromIndex(VNI->def);
2763 if (DefMI->isImplicitDef()) {
2771 // If this is a read-modify-write instruction, there may be more valid
2782 // %src:ssub1<def,read-undef> = FOO %src:ssub2
2784 // The <read-undef> flag on the def operand means that old lane values are
2787 V.RedefVNI = LR.Query(VNI->def).valueIn();
2791 computeAssignment(V.RedefVNI->id, Other);
2792 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2797 if (DefMI->isImplicitDef()) {
2809 // Find the value in Other that overlaps VNI->def, if any.
2810 LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
2817 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
2821 if (OtherVNI->def < VNI->def)
2822 Other.computeAssignment(OtherVNI->id, *this);
2823 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2824 // This is an early-clobber def overlapping a live-in value in the other
2830 Val &OtherV = Other.Vals[OtherVNI->id];
2832 // revisiting OtherVNI->id in JoinVals::computeAssignment() below before it
2834 if (!OtherV.isAnalyzed() || Other.Assignments[OtherVNI->id] == -1)
2839 if (VNI->isPHIDef())
2848 // No simultaneous def. Is Other live at the def?
2851 // No overlap, no conflict.
2854 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");
2858 Other.computeAssignment(V.OtherVNI->id, *this);
2859 Val &OtherV = Other.Vals[V.OtherVNI->id];
2874 Indexes->getInstructionFromIndex(V.OtherVNI->def);
2875 MachineBasicBlock *OtherMBB = OtherImpDef->getParent();
2877 (DefMI->getParent() != OtherMBB || LIS->isLiveInToMBB(LR, OtherMBB))) {
2878 LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2880 << printMBBReference(*DefMI->getParent())
2883 } else if (OtherMBB->hasEHPadSuccessor()) {
2889 dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2900 if (VNI->isPHIDef())
2904 if (DefMI->isImplicitDef())
2907 // Include the non-conflict where DefMI is a coalescable copy that kills
2918 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2924 // %this = COPY %ext <-- Erase this copy
2926 if (DefMI->isFullCopy() && !CP.isPartial() &&
2940 // mapping, though - OtherVNI will map to multiple values:
2942 // 1 %dst:ssub0 = FOO <-- OtherVNI
2943 // 2 %src = BAR <-- VNI
2944 // 3 %dst:ssub1 = COPY killed %src <-- Eliminate this copy.
2956 // %dst<def,early-clobber> = ASM killed %src
2962 assert(VNI->def.isEarlyClobber() &&
2968 // possibility that no instructions actually read the clobbered lanes.
2971 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
2975 auto &OtherLI = LIS->getInterval(Other.Reg);
2980 LaneBitmask OtherMask = TRI->getSubRegIndexLaneMask(Other.SubIdx);
2984 // If we are clobbering some active lanes of OtherVNI at VNI->def, it is
2986 // OtherVNI because of no real conflict.
2989 TRI->composeSubRegIndexLaneMask(Other.SubIdx, OtherSR.LaneMask);
2993 auto OtherSRQ = OtherSR.Query(VNI->def);
2994 if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->def) {
3004 // We need to verify that no instructions are reading the clobbered lanes.
3007 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
3008 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
3016 // that now - the recursive analyzeValue() calls must go upwards in the
3026 assert(Assignments[ValNo] != -1 && "Bad recursion?");
3034 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
3035 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
3037 << LR.getValNumInfo(ValNo)->def << " into "
3038 << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
3039 << V.OtherVNI->def << " --> @"
3040 << NewVNInfo[Assignments[ValNo]]->def << '\n');
3046 Val &OtherV = Other.Vals[V.OtherVNI->id];
3063 << '@' << LR.getValNumInfo(i)->def << '\n');
3074 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
3075 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
3078 LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
3079 assert(OtherI != Other.LR.end() && "No conflict?");
3083 SlotIndex End = OtherI->end;
3086 << OtherI->valno->id << '@' << OtherI->start << '\n');
3090 << OtherI->valno->id << '@' << OtherI->start << " to "
3098 if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
3101 // Lanes written by the new def are no longer tainted.
3102 const Val &OV = Other.Vals[OtherI->valno->id];
3119 unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
3120 if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
3133 << LR.getValNumInfo(i)->def
3141 const Val &OtherV = Other.Vals[V.OtherVNI->id];
3154 // Now look at the instructions from VNI->def to TaintExtent (inclusive).
3155 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
3156 MachineBasicBlock::iterator MI = MBB->begin();
3157 if (!VNI->isPHIDef()) {
3158 MI = Indexes->getInstructionFromIndex(VNI->def);
3159 if (!VNI->def.isEarlyClobber()) {
3160 // No need to check the instruction defining VNI for reads.
3164 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
3165 "Interference ends on VNI->def. Should have been handled earlier");
3167 Indexes->getInstructionFromIndex(TaintExtent.front().first);
3171 assert(MI != MBB->end() && "Bad LastMI");
3180 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
3205 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
3213 SlotIndex Def = LR.getValNumInfo(i)->def;
3219 LIS->pruneValue(Other.LR, Def, &EndPoints);
3221 // instructions are only inserted to provide a live-out value for PHI
3224 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
3229 // Remove <def,read-undef> flags. This def is now a partial redef.
3233 Indexes->getInstructionFromIndex(Def)->operands()) {
3254 // We can no longer trust the value mapping computed by
3257 LIS->pruneValue(LR, Def, &EndPoints);
3269 // Check if the segment consists of a copied live-through value (i.e. the copy
3273 return Q.valueIn() && Q.valueIn()->isPHIDef() && Q.valueIn() == Q.valueOut();
3290 /// | | v0 | v0 <--+
3291 /// 992B ; backedge -> bb.1 | + + |
3294 /// live-out!
3308 /// Since the main-range values %31.v1 and %45.v0 were proved to be
3327 SlotIndex Def = LR.getValNumInfo(i)->def;
3330 OtherDef = V.OtherVNI->def;
3343 ValueOut->def == Def))) {
3347 LIS->pruneValue(S, Def, &EndPoints);
3350 ValueOut->markUnused();
3356 LIS->extendToIndices(S, EndPoints);
3361 if (ValueOut->isPHIDef())
3388 if (VNI->def == Def)
3401 if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))
3415 VNI->markUnused();
3426 SlotIndex Def = VNI->def;
3435 // For intervals with subranges, removing a segment from the main range
3436 // may require extending the previous segment: for each definition of
3438 // That def may fall in the middle of a segment from another subrange.
3442 // The new end point of the main range segment to be extended.
3447 // Do not extend beyond the end of the segment being removed.
3448 // The segment may have been pruned in preparation for joining
3450 NewEnd = I->end;
3456 VNI->markUnused();
3458 if (LI != nullptr && LI->hasSubRanges()) {
3461 // minimum of (earliest def of next segment,
3462 // latest end point of containing segment)
3464 for (LiveInterval::SubRange &SR : LI->subranges()) {
3468 if (I->start > Def)
3469 ED = ED.isValid() ? std::min(ED, I->start) : I->start;
3471 LE = LE.isValid() ? std::max(LE, I->end) : I->end;
3483 std::prev(S)->end = NewEnd;
3495 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
3496 assert(MI && "No instruction to erase");
3497 if (MI->isCopy()) {
3498 Register Reg = MI->getOperand(1).getReg();
3504 LIS->RemoveMachineInstrFromMaps(*MI);
3505 MI->eraseFromParent();
3569 if (i != n-1)
3574 LIS->extendToIndices(LRange, EndPoints);
3582 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3594 *LIS->getSlotIndexes(), *TRI, ComposeSubRegIdx);
3610 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
3611 LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
3612 bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
3634 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3640 LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3641 : TRI->getSubRegIndexLaneMask(DstIdx);
3648 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
3658 LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3659 : TRI->getSubRegIndexLaneMask(SrcIdx);
3664 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
3677 LHS.createSubRangeFrom(LIS->getVNInfoAllocator(),
3678 CP.getNewRC()->getLaneMask(), LHS);
3679 mergeSubRangeInto(LHS, RHS, TRI->getSubRegIndexLaneMask(CP.getSrcIdx()), CP,
3699 shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
3704 // If the RHS covers any PHI locations that were tracked for debug-info, we
3709 for (unsigned InstID : RegIt->second) {
3712 const SlotIndex &SI = PHIIt->second.SI;
3716 if (LII == RHS.end() || LII->start > SI)
3721 // %1:gr16 = some-inst
3722 // ->
3723 // %2:gr32.sub_16bit = some-inst
3726 // %2:gr32.sub_16bit = some-inst
3728 // ->
3729 // %3:gr32.sub_16bit = some-inst
3734 if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.getSrcIdx())
3738 PHIIt->second.Reg = CP.getDstReg();
3740 // If we merge into a sub-register of a larger class (test above),
3743 PHIIt->second.SubReg = CP.getSrcIdx();
3749 auto InstrNums = RegIt->second;
3756 RegIt->second.insert(RegIt->second.end(), InstrNums.begin(),
3768 MRI->clearKillFlags(LHS.reg());
3769 MRI->clearKillFlags(RHS.reg());
3778 if (i != n-1)
3783 LIS->extendToIndices((LiveRange&)LHS, EndPoints);
3795 const SlotIndexes &Slots = *LIS->getSlotIndexes();
3802 for (const auto &Op : X->debug_operands()) {
3812 // Once a non-debug instruction is found, record the slot index of the
3865 auto &DbgValueSet = VRegMapIt->second;
3875 &LastUndefIdx](SlotIndex Idx) -> bool {
3876 // Our worst-case performance typically happens with asan, causing very
3878 // result for this edge-case.
3896 auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3903 // Iterate over both the live-range of the "Other" register, and the set of
3907 if (DbgValueSetIt->first < SegmentIt->end) {
3910 if (DbgValueSetIt->first >= SegmentIt->start) {
3911 bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3912 bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3915 DbgValueSetIt->second->setDebugValueUndef();
3940 /// C-style comparator that sorts first based on the loop depth of the basic
3947 if (LHS->Depth != RHS->Depth)
3948 return LHS->Depth > RHS->Depth ? -1 : 1;
3951 if (LHS->IsSplit != RHS->IsSplit)
3952 return LHS->IsSplit ? -1 : 1;
3956 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3957 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3959 return cl > cr ? -1 : 1;
3962 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3967 if (!Copy->isCopy())
3970 if (Copy->getOperand(1).isUndef())
3973 Register SrcReg = Copy->getOperand(1).getReg();
3974 Register DstReg = Copy->getOperand(0).getReg();
3978 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg))
3979 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
3984 if (!LIS->hasInterval(reg))
3986 LiveInterval &LI = LIS->getInterval(reg);
4033 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
4058 const LiveInterval &DstLI = LIS->getInterval(DstReg);
4059 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
4075 // Check if OtherReg is a non-terminal.
4079 if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
4090 LLVM_DEBUG(dbgs() << MBB->getName() << ":\n");
4092 // Collect all copy-like instructions in MBB. Don't start coalescing anything
4098 // Coalesce copies bottom-up to coalesce local defs before local uses. They
4158 MBBs.reserve(MF->size());
4160 MBBs.push_back(MBBPriorityInfo(&MBB, Loops->getLoopDepth(&MBB),
4179 // until we make no progress.
4224 // If there are PHIs tracked by debug-info, they will need updating during
4226 SlotIndexes *Slots = LIS->getSlotIndexes();
4227 for (const auto &DebugPHI : MF->DebugPHIPositions) {
4231 SlotIndex SI = Slots->getMBBStartIdx(MBB);
4243 MF->verify(this, "Before register coalescing");
4255 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
4262 if (MRI->reg_nodbg_empty(Reg))
4264 if (MRI->recomputeRegClass(Reg)) {
4266 << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
4269 LiveInterval &LI = LIS->getInterval(Reg);
4273 if (!MRI->shouldTrackSubRegLiveness(Reg)) {
4277 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
4289 // After coalescing, update any PHIs that are being tracked by debug-info
4291 for (auto &p : MF->DebugPHIPositions) {
4294 p.second.Reg = it->second.Reg;
4295 p.second.SubReg = it->second.SubReg;
4303 MF->verify(this, "After register coalescing");
4308 LIS->print(O);