63#define DEBUG_TYPE "regalloc"
65STATISTIC(numJoins ,
"Number of interval joins performed");
66STATISTIC(numCrossRCs ,
"Number of cross class joins performed");
67STATISTIC(numCommutes ,
"Number of instruction commuting performed");
69STATISTIC(NumReMats ,
"Number of instructions re-materialized");
70STATISTIC(NumInflated ,
"Number of register classes inflated");
71STATISTIC(NumLaneConflicts,
"Number of dead lane conflicts tested");
72STATISTIC(NumLaneResolves,
"Number of dead lane conflicts resolved");
73STATISTIC(NumShrinkToUses,
"Number of shrinkToUses called");
76 cl::desc(
"Coalesce copies (default=true)"),
91 cl::desc(
"Coalesce copies that span blocks (default=subtarget)"),
96 cl::desc(
"Verify machine instrs before and after register coalescing"),
101 cl::desc(
"During rematerialization for a copy, if the def instruction has "
102 "many other copy uses to be rematerialized, delay the multiple "
103 "separate live interval update work and do them all at once after "
104 "all those rematerialization are done. It will save a lot of "
110 cl::desc(
"If the valnos size of an interval is larger than the threshold, "
111 "it is regarded as a large interval. "),
116 cl::desc(
"For a large interval, if it is coalesed with other live "
117 "intervals many times more than the threshold, stop its "
118 "coalescing to control the compile time. "),
153 using DbgValueLoc = std::pair<SlotIndex, MachineInstr*>;
168 bool ShrinkMainRange =
false;
172 bool JoinGlobalCopies =
false;
176 bool JoinSplitEdges =
false;
208 void coalesceLocals();
211 void joinAllIntervals();
226 void lateLiveIntervalUpdate();
231 bool copyValueUndefInPredecessors(
LiveRange &S,
296 std::pair<bool,bool> removeCopyByCommutingDef(
const CoalescerPair &CP,
367 MI->eraseFromParent();
403char RegisterCoalescer::ID = 0;
408 "Simple Register Coalescing",
false,
false)
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();
445 for (
const auto &
MI : *
MBB) {
446 if (!
MI.isCopyLike() && !
MI.isUnconditionalBranch())
456 Flipped = CrossClass =
false;
459 unsigned SrcSub = 0, DstSub = 0;
462 Partial = SrcSub || DstSub;
465 if (Src.isPhysical()) {
466 if (Dst.isPhysical())
475 if (Dst.isPhysical()) {
478 Dst =
TRI.getSubReg(Dst, DstSub);
479 if (!Dst)
return false;
485 Dst =
TRI.getMatchingSuperReg(Dst, SrcSub,
MRI.getRegClass(Src));
486 if (!Dst)
return false;
487 }
else if (!
MRI.getRegClass(Src)->contains(Dst)) {
496 if (SrcSub && DstSub) {
498 if (Src == Dst && SrcSub != DstSub)
501 NewRC =
TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub,
508 NewRC =
TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
512 NewRC =
TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
515 NewRC =
TRI.getCommonSubClass(DstRC, SrcRC);
524 if (DstIdx && !SrcIdx) {
530 CrossClass = NewRC != DstRC || NewRC != SrcRC;
533 assert(Src.isVirtual() &&
"Src must be virtual");
534 assert(!(Dst.isPhysical() && DstSub) &&
"Cannot have a physical SubIdx");
553 unsigned SrcSub = 0, DstSub = 0;
561 }
else if (Src != SrcReg) {
567 if (!Dst.isPhysical())
569 assert(!DstIdx && !SrcIdx &&
"Inconsistent CoalescerPair state.");
572 Dst =
TRI.getSubReg(Dst, DstSub);
575 return DstReg == Dst;
577 return Register(
TRI.getSubReg(DstReg, SrcSub)) == Dst;
583 return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
584 TRI.composeSubRegIndices(DstIdx, DstSub);
588void RegisterCoalescer::getAnalysisUsage(
AnalysisUsage &AU)
const {
600void RegisterCoalescer::eliminateDeadDefs(
LiveRangeEdit *Edit) {
610void RegisterCoalescer::LRE_WillEraseInstruction(
MachineInstr *
MI) {
615bool RegisterCoalescer::adjustCopiesBackFrom(
const CoalescerPair &CP,
617 assert(!
CP.isPartial() &&
"This doesn't work for partial copies.");
618 assert(!
CP.isPhys() &&
"This doesn't work for physreg copies.");
643 if (BS == IntB.
end())
return false;
644 VNInfo *BValNo = BS->valno;
649 if (BValNo->
def != CopyIdx)
return false;
655 if (AS == IntA.
end())
return false;
656 VNInfo *AValNo = AS->valno;
662 if (!
CP.isCoalescable(ACopyMI) || !ACopyMI->
isFullCopy())
668 if (ValS == IntB.
end())
681 if (ValS+1 != BS)
return false;
685 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
689 BValNo->
def = FillerStart;
697 if (BValNo != ValS->valno)
706 S.removeSegment(*SS,
true);
710 if (!S.getVNInfoAt(FillerStart)) {
713 S.extendInBlock(BBStart, FillerStart);
715 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
718 if (SubBValNo != SubValSNo)
719 S.MergeValueNumberInto(SubBValNo, SubValSNo);
735 bool RecomputeLiveRange = AS->end == CopyIdx;
736 if (!RecomputeLiveRange) {
739 if (SS != S.end() &&
SS->end == CopyIdx) {
740 RecomputeLiveRange =
true;
745 if (RecomputeLiveRange)
752bool RegisterCoalescer::hasOtherReachingDefs(
LiveInterval &IntA,
762 if (ASeg.
valno != AValNo)
continue;
764 if (BI != IntB.
begin())
766 for (; BI != IntB.
end() && ASeg.
end >= BI->start; ++BI) {
767 if (BI->valno == BValNo)
769 if (BI->start <= ASeg.
start && BI->end > ASeg.
start)
771 if (BI->start > ASeg.
start && BI->start < ASeg.
end)
780static std::pair<bool,bool>
783 bool Changed =
false;
784 bool MergedWithDead =
false;
786 if (S.
valno != SrcValNo)
797 MergedWithDead =
true;
800 return std::make_pair(Changed, MergedWithDead);
804RegisterCoalescer::removeCopyByCommutingDef(
const CoalescerPair &CP,
837 assert(BValNo !=
nullptr && BValNo->
def == CopyIdx);
843 return {
false,
false };
846 return {
false,
false };
848 return {
false,
false };
855 return {
false,
false };
868 return {
false,
false };
873 return {
false,
false };
877 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
878 return {
false,
false };
887 if (US == IntA.
end() || US->valno != AValNo)
891 return {
false,
false };
903 return {
false,
false };
905 !
MRI->constrainRegClass(IntB.
reg(),
MRI->getRegClass(IntA.
reg())))
906 return {
false,
false };
907 if (NewMI !=
DefMI) {
932 UseMO.setReg(NewReg);
937 assert(US != IntA.
end() &&
"Use must be live");
938 if (US->valno != AValNo)
941 UseMO.setIsKill(
false);
943 UseMO.substPhysReg(NewReg, *
TRI);
945 UseMO.setReg(NewReg);
964 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
967 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
969 S.MergeValueNumberInto(SubDVNI, SubBValNo);
977 bool ShrinkB =
false;
991 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
1000 MaskA |= SA.LaneMask;
1003 Allocator, SA.LaneMask,
1004 [&Allocator, &SA, CopyIdx, ASubValNo,
1006 VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
1007 : SR.getVNInfoAt(CopyIdx);
1008 assert(BSubValNo != nullptr);
1009 auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
1010 ShrinkB |= P.second;
1012 BSubValNo->def = ASubValNo->def;
1020 if ((SB.LaneMask & MaskA).any())
1024 SB.removeSegment(*S,
true);
1028 BValNo->
def = AValNo->
def;
1030 ShrinkB |=
P.second;
1037 return {
true, ShrinkB };
1087bool RegisterCoalescer::removePartialRedundancy(
const CoalescerPair &CP,
1120 bool FoundReverseCopy =
false;
1139 bool ValB_Changed =
false;
1140 for (
auto *VNI : IntB.
valnos) {
1141 if (VNI->isUnused())
1144 ValB_Changed =
true;
1152 FoundReverseCopy =
true;
1156 if (!FoundReverseCopy)
1166 if (CopyLeftBB && CopyLeftBB->
succ_size() > 1)
1177 if (InsPos != CopyLeftBB->
end()) {
1183 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Move the copy to "
1188 TII->get(TargetOpcode::COPY), IntB.
reg())
1199 ErasedInstrs.
erase(NewCopyMI);
1201 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Remove the copy from "
1210 deleteInstr(&CopyMI);
1224 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1225 assert(BValNo &&
"All sublanes should be live");
1234 for (
unsigned I = 0;
I != EndPoints.
size(); ) {
1236 EndPoints[
I] = EndPoints.
back();
1258 assert(!Reg.isPhysical() &&
"This code cannot handle physreg aliasing");
1261 if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
1265 if (Op.getSubReg() == 0 || Op.isUndef())
1271bool RegisterCoalescer::reMaterializeTrivialDef(
const CoalescerPair &CP,
1275 Register SrcReg =
CP.isFlipped() ?
CP.getDstReg() :
CP.getSrcReg();
1276 unsigned SrcIdx =
CP.isFlipped() ?
CP.getDstIdx() :
CP.getSrcIdx();
1277 Register DstReg =
CP.isFlipped() ?
CP.getSrcReg() :
CP.getDstReg();
1278 unsigned DstIdx =
CP.isFlipped() ?
CP.getSrcIdx() :
CP.getDstIdx();
1300 LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS,
nullptr,
this);
1306 bool SawStore =
false;
1323 if (SrcIdx && DstIdx)
1331 unsigned NewDstIdx =
TRI->composeSubRegIndices(
CP.getSrcIdx(),
1334 NewDstReg =
TRI->getSubReg(DstReg, NewDstIdx);
1344 "Only expect to deal with virtual or physical registers");
1370 assert(SrcIdx == 0 &&
CP.isFlipped()
1371 &&
"Shouldn't have SrcIdx+DstIdx at this point");
1374 TRI->getCommonSubClass(DefRC, DstRC);
1375 if (CommonRC !=
nullptr) {
1383 if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1404 assert(MO.
isImplicit() &&
"No explicit operands after implicit operands.");
1412 ErasedInstrs.
insert(CopyMI);
1431 if (DefRC !=
nullptr) {
1433 NewRC =
TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1435 NewRC =
TRI->getCommonSubClass(NewRC, DefRC);
1436 assert(NewRC &&
"subreg chosen for remat incompatible with instruction");
1441 SR.LaneMask =
TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1443 MRI->setRegClass(DstReg, NewRC);
1446 updateRegDefsUses(DstReg, DstReg, DstIdx);
1474 if (!SR.liveAt(DefIndex))
1475 SR.createDeadDef(DefIndex,
Alloc);
1476 MaxMask &= ~SR.LaneMask;
1478 if (MaxMask.
any()) {
1496 bool UpdatedSubRanges =
false;
1501 if ((SR.
LaneMask & DstMask).none()) {
1503 <<
"Removing undefined SubRange "
1508 UpdatedSubRanges =
true;
1520 if (UpdatedSubRanges)
1527 "Only expect virtual or physical registers in remat");
1530 CopyDstReg,
true ,
true ,
false ));
1562 for (
unsigned i = 0, e = NewMIImplDefs.
size(); i != e; ++i) {
1574 if (
MRI->use_nodbg_empty(SrcReg)) {
1580 UseMO.substPhysReg(DstReg, *
TRI);
1582 UseMO.setReg(DstReg);
1591 if (ToBeUpdated.
count(SrcReg))
1594 unsigned NumCopyUses = 0;
1596 if (UseMO.getParent()->isCopyLike())
1602 if (!DeadDefs.
empty())
1603 eliminateDeadDefs(&Edit);
1605 ToBeUpdated.
insert(SrcReg);
1623 unsigned SrcSubIdx = 0, DstSubIdx = 0;
1624 if(!
isMoveInstr(*
TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1633 if ((SR.
LaneMask & SrcMask).none())
1646 assert(Seg !=
nullptr &&
"No segment for defining instruction");
1651 if (((V &&
V->isPHIDef()) || (!V && !DstLI.
liveAt(
Idx)))) {
1652 CopyMI->
setDesc(
TII->get(TargetOpcode::IMPLICIT_DEF));
1674 if ((SR.
LaneMask & DstMask).none())
1696 if ((SR.
LaneMask & UseMask).none())
1704 isLive = DstLI.
liveAt(UseIdx);
1729 bool IsUndef =
true;
1731 if ((S.LaneMask & Mask).none())
1733 if (S.liveAt(UseIdx)) {
1746 ShrinkMainRange =
true;
1755 if (DstInt && DstInt->
hasSubRanges() && DstReg != SrcReg) {
1761 if (
MI.isDebugInstr())
1764 addUndefFlag(*DstInt, UseIdx, MO,
SubReg);
1770 I =
MRI->reg_instr_begin(SrcReg),
E =
MRI->reg_instr_end();
1779 if (SrcReg == DstReg && !Visited.
insert(
UseMI).second)
1792 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1798 if (SubIdx && MO.
isDef())
1803 if (MO.
isUse() && !DstIsPhys) {
1804 unsigned SubUseIdx =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
1805 if (SubUseIdx != 0 &&
MRI->shouldTrackSubRegLiveness(DstReg)) {
1822 addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);
1833 dbgs() <<
"\t\tupdated: ";
1841bool RegisterCoalescer::canJoinPhys(
const CoalescerPair &CP) {
1845 if (!
MRI->isReserved(
CP.getDstReg())) {
1846 LLVM_DEBUG(
dbgs() <<
"\tCan only merge into reserved registers.\n");
1855 dbgs() <<
"\tCannot join complex intervals into reserved register.\n");
1859bool RegisterCoalescer::copyValueUndefInPredecessors(
1873void RegisterCoalescer::setUndefOnPrunedSubRegUses(
LiveInterval &LI,
1880 if (SubRegIdx == 0 || MO.
isUndef())
1886 if (!S.
liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {
1902bool RegisterCoalescer::joinCopy(
MachineInstr *CopyMI,
bool &Again) {
1907 if (!
CP.setRegisters(CopyMI)) {
1912 if (
CP.getNewRC()) {
1913 auto SrcRC =
MRI->getRegClass(
CP.getSrcReg());
1914 auto DstRC =
MRI->getRegClass(
CP.getDstReg());
1915 unsigned SrcIdx =
CP.getSrcIdx();
1916 unsigned DstIdx =
CP.getDstIdx();
1917 if (
CP.isFlipped()) {
1921 if (!
TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1922 CP.getNewRC(), *LIS)) {
1934 eliminateDeadDefs();
1941 if (
MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
1942 if (UndefMI->isImplicitDef())
1944 deleteInstr(CopyMI);
1952 if (
CP.getSrcReg() ==
CP.getDstReg()) {
1954 LLVM_DEBUG(
dbgs() <<
"\tCopy already coalesced: " << LI <<
'\n');
1959 assert(ReadVNI &&
"No value before copy and no <undef> flag.");
1960 assert(ReadVNI != DefVNI &&
"Cannot read and define the same value.");
1975 if (copyValueUndefInPredecessors(S,
MBB, SLRQ)) {
1976 LLVM_DEBUG(
dbgs() <<
"Incoming sublane value is undef at copy\n");
1977 PrunedLanes |= S.LaneMask;
1984 if (PrunedLanes.
any()) {
1986 << PrunedLanes <<
'\n');
1987 setUndefOnPrunedSubRegUses(LI,
CP.getSrcReg(), PrunedLanes);
1992 deleteInstr(CopyMI);
2001 if (!canJoinPhys(CP)) {
2004 bool IsDefCopy =
false;
2005 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2018 dbgs() <<
"\tConsidering merging to "
2019 <<
TRI->getRegClassName(
CP.getNewRC()) <<
" with ";
2020 if (
CP.getDstIdx() &&
CP.getSrcIdx())
2022 <<
TRI->getSubRegIndexName(
CP.getDstIdx()) <<
" and "
2024 <<
TRI->getSubRegIndexName(
CP.getSrcIdx()) <<
'\n';
2032 ShrinkMainRange =
false;
2038 if (!joinIntervals(CP)) {
2043 bool IsDefCopy =
false;
2044 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2049 if (!
CP.isPartial() && !
CP.isPhys()) {
2050 bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2051 bool Shrink =
false;
2053 std::tie(Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2055 deleteInstr(CopyMI);
2057 Register DstReg =
CP.isFlipped() ?
CP.getSrcReg() :
CP.getDstReg();
2069 if (!
CP.isPartial() && !
CP.isPhys())
2070 if (removePartialRedundancy(CP, *CopyMI))
2081 if (
CP.isCrossClass()) {
2083 MRI->setRegClass(
CP.getDstReg(),
CP.getNewRC());
2094 ErasedInstrs.
erase(CopyMI);
2099 updateRegDefsUses(
CP.getDstReg(),
CP.getDstReg(),
CP.getDstIdx());
2100 updateRegDefsUses(
CP.getSrcReg(),
CP.getDstReg(),
CP.getSrcIdx());
2103 if (ShrinkMask.
any()) {
2106 if ((S.LaneMask & ShrinkMask).none())
2111 ShrinkMainRange =
true;
2119 if (ToBeUpdated.
count(
CP.getSrcReg()))
2120 ShrinkMainRange =
true;
2122 if (ShrinkMainRange) {
2132 TRI->updateRegAllocHint(
CP.getSrcReg(),
CP.getDstReg(), *MF);
2137 dbgs() <<
"\tResult = ";
2149bool RegisterCoalescer::joinReservedPhysReg(
CoalescerPair &CP) {
2152 assert(
CP.isPhys() &&
"Must be a physreg copy");
2153 assert(
MRI->isReserved(DstReg) &&
"Not a reserved register");
2157 assert(
RHS.containsOneValue() &&
"Invalid join with reserved register");
2166 if (!
MRI->isConstantPhysReg(DstReg)) {
2170 if (!
MRI->isReserved(*RI))
2183 !RegMaskUsable.
test(DstReg)) {
2196 if (
CP.isFlipped()) {
2204 CopyMI =
MRI->getVRegDef(SrcReg);
2213 if (!
MRI->hasOneNonDBGUse(SrcReg)) {
2224 CopyMI = &*
MRI->use_instr_nodbg_begin(SrcReg);
2228 if (!
MRI->isConstantPhysReg(DstReg)) {
2236 if (
MI->readsRegister(DstReg,
TRI)) {
2246 <<
printReg(DstReg,
TRI) <<
" at " << CopyRegIdx <<
"\n");
2256 deleteInstr(CopyMI);
2259 MRI->clearKillFlags(
CP.getSrcReg());
2344 const unsigned SubIdx;
2352 const bool SubRangeJoin;
2355 const bool TrackSubRegLiveness;
2371 enum ConflictResolution {
2403 ConflictResolution Resolution = CR_Keep;
2413 VNInfo *RedefVNI =
nullptr;
2416 VNInfo *OtherVNI =
nullptr;
2429 bool ErasableImplicitDef =
false;
2433 bool Pruned =
false;
2436 bool PrunedComputed =
false;
2443 bool Identical =
false;
2447 bool isAnalyzed()
const {
return WriteLanes.
any(); }
2459 std::pair<const VNInfo *, Register> followCopyChain(
const VNInfo *VNI)
const;
2461 bool valuesIdentical(
VNInfo *Value0,
VNInfo *Value1,
const JoinVals &
Other)
const;
2470 ConflictResolution analyzeValue(
unsigned ValNo, JoinVals &
Other);
2475 void computeAssignment(
unsigned ValNo, JoinVals &
Other);
2506 bool isPrunedValue(
unsigned ValNo, JoinVals &
Other);
2512 bool TrackSubRegLiveness)
2513 : LR(LR),
Reg(
Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2514 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2515 NewVNInfo(newVNInfo),
CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2516 TRI(
TRI), Assignments(LR.getNumValNums(), -1),
2517 Vals(LR.getNumValNums()) {}
2521 bool mapValues(JoinVals &
Other);
2525 bool resolveConflicts(JoinVals &
Other);
2545 void pruneMainSegments(
LiveInterval &LI,
bool &ShrinkMainRange);
2556 void removeImplicitDefs();
2559 const int *getAssignments()
const {
return Assignments.
data(); }
2562 ConflictResolution getResolution(
unsigned Num)
const {
2563 return Vals[Num].Resolution;
2575 L |=
TRI->getSubRegIndexLaneMask(
2583std::pair<const VNInfo *, Register>
2584JoinVals::followCopyChain(
const VNInfo *VNI)
const {
2590 assert(
MI &&
"No defining instruction");
2591 if (!
MI->isFullCopy())
2592 return std::make_pair(VNI, TrackReg);
2593 Register SrcReg =
MI->getOperand(1).getReg();
2595 return std::make_pair(VNI, TrackReg);
2609 LaneBitmask SMask =
TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2610 if ((SMask & LaneMask).
none())
2618 return std::make_pair(VNI, TrackReg);
2621 if (ValueIn ==
nullptr) {
2628 return std::make_pair(
nullptr, SrcReg);
2633 return std::make_pair(VNI, TrackReg);
2636bool JoinVals::valuesIdentical(
VNInfo *Value0,
VNInfo *Value1,
2637 const JoinVals &
Other)
const {
2640 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2641 if (Orig0 == Value1 && Reg0 ==
Other.Reg)
2646 std::tie(Orig1, Reg1) =
Other.followCopyChain(Value1);
2650 if (Orig0 ==
nullptr || Orig1 ==
nullptr)
2651 return Orig0 == Orig1 && Reg0 == Reg1;
2657 return Orig0->
def == Orig1->
def && Reg0 == Reg1;
2660JoinVals::ConflictResolution
2661JoinVals::analyzeValue(
unsigned ValNo, JoinVals &
Other) {
2662 Val &
V = Vals[ValNo];
2663 assert(!
V.isAnalyzed() &&
"Value has already been analyzed!");
2675 :
TRI->getSubRegIndexLaneMask(SubIdx);
2676 V.ValidLanes =
V.WriteLanes = Lanes;
2685 V.ErasableImplicitDef =
true;
2689 V.ValidLanes =
V.WriteLanes = computeWriteLanes(
DefMI, Redef);
2708 assert((TrackSubRegLiveness ||
V.RedefVNI) &&
2709 "Instruction is reading nonexistent value");
2710 if (
V.RedefVNI !=
nullptr) {
2711 computeAssignment(
V.RedefVNI->id,
Other);
2712 V.ValidLanes |= Vals[
V.RedefVNI->id].ValidLanes;
2724 V.ErasableImplicitDef =
true;
2741 if (OtherVNI->def < VNI->
def)
2742 Other.computeAssignment(OtherVNI->id, *
this);
2743 else if (VNI->
def < OtherVNI->def && OtherLRQ.
valueIn()) {
2747 return CR_Impossible;
2749 V.OtherVNI = OtherVNI;
2750 Val &OtherV =
Other.Vals[OtherVNI->id];
2754 if (!OtherV.isAnalyzed() ||
Other.Assignments[OtherVNI->id] == -1)
2761 if ((
V.ValidLanes & OtherV.ValidLanes).any())
2763 return CR_Impossible;
2778 Other.computeAssignment(
V.OtherVNI->id, *
this);
2779 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
2781 if (OtherV.ErasableImplicitDef) {
2794 <<
", keeping it.\n");
2795 OtherV.ErasableImplicitDef =
false;
2798 OtherV.ValidLanes &= ~OtherV.WriteLanes;
2813 if (
CP.isCoalescable(
DefMI)) {
2816 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2831 valuesIdentical(VNI,
V.OtherVNI,
Other)) {
2854 if ((
V.WriteLanes & OtherV.ValidLanes).none())
2867 "Only early clobber defs can overlap a kill");
2868 return CR_Impossible;
2875 if ((
TRI->getSubRegIndexLaneMask(
Other.SubIdx) & ~
V.WriteLanes).none())
2876 return CR_Impossible;
2878 if (TrackSubRegLiveness) {
2883 if (!OtherLI.hasSubRanges()) {
2885 return (OtherMask &
V.WriteLanes).none() ? CR_Replace : CR_Impossible;
2893 TRI->composeSubRegIndexLaneMask(
Other.SubIdx, OtherSR.LaneMask);
2894 if ((OtherMask &
V.WriteLanes).none())
2897 auto OtherSRQ = OtherSR.Query(VNI->
def);
2898 if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->
def) {
2900 return CR_Impossible;
2913 return CR_Impossible;
2922 return CR_Unresolved;
2925void JoinVals::computeAssignment(
unsigned ValNo, JoinVals &
Other) {
2926 Val &
V = Vals[ValNo];
2927 if (
V.isAnalyzed()) {
2930 assert(Assignments[ValNo] != -1 &&
"Bad recursion?");
2933 switch ((
V.Resolution = analyzeValue(ValNo,
Other))) {
2937 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't merge.");
2938 assert(
Other.Vals[
V.OtherVNI->id].isAnalyzed() &&
"Missing recursion");
2939 Assignments[ValNo] =
Other.Assignments[
V.OtherVNI->id];
2943 <<
V.OtherVNI->def <<
" --> @"
2944 << NewVNInfo[Assignments[ValNo]]->def <<
'\n');
2947 case CR_Unresolved: {
2949 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't prune");
2950 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
2953 if (OtherV.ErasableImplicitDef &&
2954 TrackSubRegLiveness &&
2955 (OtherV.WriteLanes & ~
V.ValidLanes).any()) {
2956 LLVM_DEBUG(
dbgs() <<
"Cannot erase implicit_def with missing values\n");
2958 OtherV.ErasableImplicitDef =
false;
2965 OtherV.Pruned =
true;
2970 Assignments[ValNo] = NewVNInfo.
size();
2976bool JoinVals::mapValues(JoinVals &
Other) {
2978 computeAssignment(i,
Other);
2979 if (Vals[i].Resolution == CR_Impossible) {
2997 assert(OtherI !=
Other.LR.end() &&
"No conflict?");
3002 if (End >= MBBEnd) {
3004 << OtherI->valno->id <<
'@' << OtherI->start <<
'\n');
3008 << OtherI->valno->id <<
'@' << OtherI->start <<
" to "
3013 TaintExtent.push_back(std::make_pair(End, TaintedLanes));
3016 if (++OtherI ==
Other.LR.end() || OtherI->start >= MBBEnd)
3020 const Val &OV =
Other.Vals[OtherI->valno->id];
3021 TaintedLanes &= ~OV.WriteLanes;
3024 }
while (TaintedLanes.
any());
3030 if (
MI.isDebugOrPseudoInstr())
3037 unsigned S =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
3038 if ((Lanes &
TRI->getSubRegIndexLaneMask(S)).any())
3044bool JoinVals::resolveConflicts(JoinVals &
Other) {
3047 assert(
V.Resolution != CR_Impossible &&
"Unresolvable conflict");
3048 if (
V.Resolution != CR_Unresolved)
3057 assert(
V.OtherVNI &&
"Inconsistent conflict resolution.");
3059 const Val &OtherV =
Other.Vals[
V.OtherVNI->id];
3064 LaneBitmask TaintedLanes =
V.WriteLanes & OtherV.ValidLanes;
3066 if (!taintExtent(i, TaintedLanes,
Other, TaintExtent))
3070 assert(!TaintExtent.
empty() &&
"There should be at least one conflict.");
3083 "Interference ends on VNI->def. Should have been handled earlier");
3086 assert(LastMI &&
"Range must end at a proper instruction");
3087 unsigned TaintNum = 0;
3090 if (usesLanes(*
MI,
Other.Reg,
Other.SubIdx, TaintedLanes)) {
3095 if (&*
MI == LastMI) {
3096 if (++TaintNum == TaintExtent.
size())
3099 assert(LastMI &&
"Range must end at a proper instruction");
3100 TaintedLanes = TaintExtent[TaintNum].second;
3106 V.Resolution = CR_Replace;
3112bool JoinVals::isPrunedValue(
unsigned ValNo, JoinVals &
Other) {
3113 Val &
V = Vals[ValNo];
3114 if (
V.Pruned ||
V.PrunedComputed)
3117 if (
V.Resolution != CR_Erase &&
V.Resolution != CR_Merge)
3122 V.PrunedComputed =
true;
3123 V.Pruned =
Other.isPrunedValue(
V.OtherVNI->id, *
this);
3127void JoinVals::pruneValues(JoinVals &
Other,
3129 bool changeInstrs) {
3132 switch (Vals[i].Resolution) {
3142 Val &OtherV =
Other.Vals[Vals[i].OtherVNI->id];
3143 bool EraseImpDef = OtherV.ErasableImplicitDef &&
3144 OtherV.Resolution == CR_Keep;
3145 if (!
Def.isBlock()) {
3165 <<
": " <<
Other.LR <<
'\n');
3170 if (isPrunedValue(i,
Other)) {
3177 << Def <<
": " << LR <<
'\n');
3235 bool DidPrune =
false;
3240 if (
V.Resolution != CR_Erase &&
3241 (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned))
3248 OtherDef =
V.OtherVNI->def;
3251 LLVM_DEBUG(
dbgs() <<
"\t\tExpecting instruction removal at " << Def
3259 if (ValueOut !=
nullptr && (Q.
valueIn() ==
nullptr ||
3260 (
V.Identical &&
V.Resolution == CR_Erase &&
3261 ValueOut->
def == Def))) {
3263 <<
" at " << Def <<
"\n");
3270 if (
V.Identical && S.Query(OtherDef).valueOutOrDead()) {
3280 ShrinkMask |= S.LaneMask;
3294 ShrinkMask |= S.LaneMask;
3306 if (VNI->
def == Def)
3312void JoinVals::pruneMainSegments(
LiveInterval &LI,
bool &ShrinkMainRange) {
3316 if (Vals[i].Resolution != CR_Keep)
3321 Vals[i].Pruned =
true;
3322 ShrinkMainRange =
true;
3326void JoinVals::removeImplicitDefs() {
3329 if (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned)
3345 switch (Vals[i].Resolution) {
3350 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3362 if (LI !=
nullptr) {
3387 ED = ED.
isValid() ? std::min(ED,
I->start) :
I->start;
3389 LE =
LE.isValid() ? std::max(LE,
I->end) :
I->
end;
3392 NewEnd = std::min(NewEnd, LE);
3394 NewEnd = std::min(NewEnd, ED);
3400 if (S != LR.
begin())
3401 std::prev(S)->end = NewEnd;
3405 dbgs() <<
"\t\tremoved " << i <<
'@' <<
Def <<
": " << LR <<
'\n';
3407 dbgs() <<
"\t\t LHS = " << *LI <<
'\n';
3414 assert(
MI &&
"No instruction to erase");
3417 if (
Reg.isVirtual() && Reg !=
CP.getSrcReg() && Reg !=
CP.getDstReg())
3423 MI->eraseFromParent();
3436 JoinVals RHSVals(RRange,
CP.getSrcReg(),
CP.getSrcIdx(), LaneMask,
3437 NewVNInfo, CP, LIS,
TRI,
true,
true);
3438 JoinVals LHSVals(LRange,
CP.getDstReg(),
CP.getDstIdx(), LaneMask,
3439 NewVNInfo, CP, LIS,
TRI,
true,
true);
3446 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
3451 if (!LHSVals.resolveConflicts(RHSVals) ||
3452 !RHSVals.resolveConflicts(LHSVals)) {
3463 LHSVals.pruneValues(RHSVals, EndPoints,
false);
3464 RHSVals.pruneValues(LHSVals, EndPoints,
false);
3466 LHSVals.removeImplicitDefs();
3467 RHSVals.removeImplicitDefs();
3473 LRange.
join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
3477 <<
' ' << LRange <<
"\n");
3478 if (EndPoints.
empty())
3484 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3485 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3486 dbgs() << EndPoints[i];
3490 dbgs() <<
": " << LRange <<
'\n';
3495void RegisterCoalescer::mergeSubRangeInto(
LiveInterval &LI,
3499 unsigned ComposeSubRegIdx) {
3502 Allocator, LaneMask,
3505 SR.assign(ToMerge, Allocator);
3508 LiveRange RangeCopy(ToMerge, Allocator);
3509 joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
3515bool RegisterCoalescer::isHighCostLiveInterval(
LiveInterval &LI) {
3518 auto &Counter = LargeLIVisitCounter[LI.
reg()];
3530 bool TrackSubRegLiveness =
MRI->shouldTrackSubRegLiveness(*
CP.getNewRC());
3532 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3534 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3536 LLVM_DEBUG(
dbgs() <<
"\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS <<
'\n');
3538 if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))
3543 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3547 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3551 if (
RHS.hasSubRanges() ||
LHS.hasSubRanges()) {
3556 unsigned DstIdx =
CP.getDstIdx();
3557 if (!
LHS.hasSubRanges()) {
3559 :
TRI->getSubRegIndexLaneMask(DstIdx);
3562 LHS.createSubRangeFrom(Allocator, Mask, LHS);
3563 }
else if (DstIdx != 0) {
3574 unsigned SrcIdx =
CP.getSrcIdx();
3575 if (!
RHS.hasSubRanges()) {
3577 :
TRI->getSubRegIndexLaneMask(SrcIdx);
3578 mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);
3583 mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);
3590 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3592 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3593 RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3601 LHSVals.pruneValues(RHSVals, EndPoints,
true);
3602 RHSVals.pruneValues(LHSVals, EndPoints,
true);
3607 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3608 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3609 while (!ShrinkRegs.
empty())
3613 checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
3617 auto RegIt = RegToPHIIdx.
find(
CP.getSrcReg());
3618 if (RegIt != RegToPHIIdx.
end()) {
3620 for (
unsigned InstID : RegIt->second) {
3621 auto PHIIt = PHIValToPos.
find(InstID);
3626 auto LII =
RHS.find(SI);
3627 if (LII ==
RHS.end() || LII->start > SI)
3642 if (
CP.getSrcIdx() != 0 ||
CP.getDstIdx() != 0)
3645 if (PHIIt->second.SubReg && PHIIt->second.SubReg !=
CP.getSrcIdx())
3649 PHIIt->second.Reg =
CP.getDstReg();
3653 if (
CP.getSrcIdx() != 0)
3654 PHIIt->second.SubReg =
CP.getSrcIdx();
3660 auto InstrNums = RegIt->second;
3661 RegToPHIIdx.
erase(RegIt);
3665 RegIt = RegToPHIIdx.
find(
CP.getDstReg());
3666 if (RegIt != RegToPHIIdx.
end())
3667 RegIt->second.insert(RegIt->second.end(), InstrNums.begin(),
3670 RegToPHIIdx.
insert({
CP.getDstReg(), InstrNums});
3674 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3679 MRI->clearKillFlags(
LHS.reg());
3680 MRI->clearKillFlags(
RHS.reg());
3682 if (!EndPoints.
empty()) {
3686 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3687 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3688 dbgs() << EndPoints[i];
3692 dbgs() <<
": " <<
LHS <<
'\n';
3701 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(
CP);
3712 for (
auto *
X : ToInsert) {
3713 for (
const auto &Op :
X->debug_operands()) {
3714 if (
Op.isReg() &&
Op.getReg().isVirtual())
3725 for (
auto &
MBB : MF) {
3728 for (
auto &
MI :
MBB) {
3729 if (
MI.isDebugValue()) {
3731 return MO.isReg() && MO.getReg().isVirtual();
3733 ToInsert.push_back(&
MI);
3734 }
else if (!
MI.isDebugOrPseudoInstr()) {
3736 CloseNewDVRange(CurrentSlot);
3745 for (
auto &Pair : DbgVRegToValues)
3749void RegisterCoalescer::checkMergingChangesDbgValues(
CoalescerPair &CP,
3753 JoinVals &RHSVals) {
3755 checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
3759 checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
3766 if (DbgMergedVRegNums.
count(Reg))
3767 for (
Register X : DbgMergedVRegNums[Reg])
3772 PerformScan(
CP.getSrcReg(), ScanForSrcReg);
3773 PerformScan(
CP.getDstReg(), ScanForDstReg);
3776void RegisterCoalescer::checkMergingChangesDbgValuesImpl(
Register Reg,
3779 JoinVals &RegVals) {
3781 auto VRegMapIt = DbgVRegToValues.
find(Reg);
3782 if (VRegMapIt == DbgVRegToValues.
end())
3785 auto &DbgValueSet = VRegMapIt->second;
3786 auto DbgValueSetIt = DbgValueSet.begin();
3787 auto SegmentIt = OtherLR.
begin();
3789 bool LastUndefResult =
false;
3794 auto ShouldUndef = [&RegVals, &
RegLR, &LastUndefResult,
3799 if (LastUndefIdx ==
Idx)
3800 return LastUndefResult;
3807 if (OtherIt ==
RegLR.end())
3816 auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3817 LastUndefResult = Resolution != JoinVals::CR_Keep &&
3818 Resolution != JoinVals::CR_Erase;
3820 return LastUndefResult;
3826 while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.
end()) {
3827 if (DbgValueSetIt->first < SegmentIt->end) {
3830 if (DbgValueSetIt->first >= SegmentIt->start) {
3831 bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3832 bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3833 if (HasReg && ShouldUndefReg) {
3835 DbgValueSetIt->second->setDebugValueUndef();
3849struct MBBPriorityInfo {
3855 :
MBB(mbb),
Depth(depth), IsSplit(issplit) {}
3865 const MBBPriorityInfo *RHS) {
3867 if (
LHS->Depth !=
RHS->Depth)
3868 return LHS->Depth >
RHS->Depth ? -1 : 1;
3871 if (
LHS->IsSplit !=
RHS->IsSplit)
3872 return LHS->IsSplit ? -1 : 1;
3876 unsigned cl =
LHS->MBB->pred_size() +
LHS->MBB->succ_size();
3877 unsigned cr =
RHS->MBB->pred_size() +
RHS->MBB->succ_size();
3879 return cl > cr ? -1 : 1;
3882 return LHS->MBB->getNumber() <
RHS->MBB->getNumber() ? -1 : 1;
3887 if (!Copy->isCopy())
3890 if (Copy->getOperand(1).isUndef())
3893 Register SrcReg = Copy->getOperand(1).getReg();
3894 Register DstReg = Copy->getOperand(0).getReg();
3902void RegisterCoalescer::lateLiveIntervalUpdate() {
3908 if (!DeadDefs.
empty())
3909 eliminateDeadDefs();
3911 ToBeUpdated.clear();
3914bool RegisterCoalescer::
3916 bool Progress =
false;
3939 assert(Copy.isCopyLike());
3942 if (&
MI != &Copy &&
MI.isCopyLike())
3947bool RegisterCoalescer::applyTerminalRule(
const MachineInstr &Copy)
const {
3952 unsigned SrcSubReg = 0, DstSubReg = 0;
3953 if (!
isMoveInstr(*
TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
3974 if (&
MI == &Copy || !
MI.isCopyLike() ||
MI.getParent() != OrigBB)
3977 unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
3978 if (!
isMoveInstr(*
TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
3981 if (OtherReg == SrcReg)
3982 OtherReg = OtherSrcReg;
4002 const unsigned PrevSize = WorkList.
size();
4003 if (JoinGlobalCopies) {
4011 if (!
MI.isCopyLike())
4013 bool ApplyTerminalRule = applyTerminalRule(
MI);
4015 if (ApplyTerminalRule)
4020 if (ApplyTerminalRule)
4027 LocalWorkList.
append(LocalTerminals.
begin(), LocalTerminals.
end());
4033 if (MII.isCopyLike()) {
4034 if (applyTerminalRule(MII))
4046 CurrList(WorkList.
begin() + PrevSize, WorkList.
end());
4047 if (copyCoalesceWorkList(CurrList))
4048 WorkList.
erase(std::remove(WorkList.
begin() + PrevSize, WorkList.
end(),
4049 nullptr), WorkList.
end());
4052void RegisterCoalescer::coalesceLocals() {
4053 copyCoalesceWorkList(LocalWorkList);
4054 for (
unsigned j = 0, je = LocalWorkList.
size(); j != je; ++j) {
4055 if (LocalWorkList[j])
4058 LocalWorkList.
clear();
4061void RegisterCoalescer::joinAllIntervals() {
4062 LLVM_DEBUG(
dbgs() <<
"********** JOINING INTERVALS ***********\n");
4063 assert(WorkList.
empty() && LocalWorkList.
empty() &&
"Old data still around.");
4065 std::vector<MBBPriorityInfo> MBBs;
4066 MBBs.reserve(MF->size());
4068 MBBs.push_back(MBBPriorityInfo(&
MBB,
Loops->getLoopDepth(&
MBB),
4074 unsigned CurrDepth = std::numeric_limits<unsigned>::max();
4075 for (MBBPriorityInfo &
MBB : MBBs) {
4077 if (JoinGlobalCopies &&
MBB.Depth < CurrDepth) {
4079 CurrDepth =
MBB.Depth;
4081 copyCoalesceInMBB(
MBB.MBB);
4083 lateLiveIntervalUpdate();
4088 while (copyCoalesceWorkList(WorkList))
4090 lateLiveIntervalUpdate();
4093void RegisterCoalescer::releaseMemory() {
4094 ErasedInstrs.
clear();
4097 InflateRegs.
clear();
4098 LargeLIVisitCounter.
clear();
4102 LLVM_DEBUG(
dbgs() <<
"********** SIMPLE REGISTER COALESCING **********\n"
4103 <<
"********** Function: " << fn.
getName() <<
'\n');
4115 dbgs() <<
"* Skipped as it exposes functions that returns twice.\n");
4124 LIS = &getAnalysis<LiveIntervals>();
4125 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4126 Loops = &getAnalysis<MachineLoopInfo>();
4135 for (
const auto &DebugPHI : MF->DebugPHIPositions) {
4138 unsigned SubReg = DebugPHI.second.SubReg;
4141 PHIValToPos.
insert(std::make_pair(DebugPHI.first,
P));
4142 RegToPHIIdx[
Reg].push_back(DebugPHI.first);
4151 MF->verify(
this,
"Before register coalescing");
4153 DbgVRegToValues.
clear();
4154 DbgMergedVRegNums.
clear();
4155 buildVRegToDbgValueMap(fn);
4167 InflateRegs.
erase(std::unique(InflateRegs.
begin(), InflateRegs.
end()),
4171 for (
unsigned i = 0, e = InflateRegs.
size(); i != e; ++i) {
4173 if (
MRI->reg_nodbg_empty(Reg))
4175 if (
MRI->recomputeRegClass(Reg)) {
4177 <<
TRI->getRegClassName(
MRI->getRegClass(Reg)) <<
'\n');
4184 if (!
MRI->shouldTrackSubRegLiveness(Reg)) {
4192 assert((S.LaneMask & ~MaxMask).none());
4202 for (
auto &p : MF->DebugPHIPositions) {
4203 auto it = PHIValToPos.
find(
p.first);
4205 p.second.Reg = it->second.Reg;
4206 p.second.SubReg = it->second.SubReg;
4209 PHIValToPos.
clear();
4210 RegToPHIIdx.
clear();
4214 MF->verify(
this,
"After register coalescing");
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseSet and SmallDenseSet classes.
std::optional< std::vector< StOtherPiece > > Other
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
const HexagonInstrInfo * TII
A common definition of LaneBitmask for use in TableGen and CodeGen.
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
simple register coalescing
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)
simple register Simple Register Coalescing
static bool isSplitEdge(const MachineBasicBlock *MBB)
Return true if this block should be vacated by the coalescer to eliminate branches.
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),...
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))
simple register Simple Register static false bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, Register &Src, Register &Dst, unsigned &SrcSub, unsigned &DstSub)
static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def)
Check if any of the subranges of LI contain a definition at Def.
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...
static bool isLiveThrough(const LiveQueryResult Q)
static bool isTerminalReg(Register DstReg, const MachineInstr &Copy, const MachineRegisterInfo *MRI)
Check if DstReg is a terminal node.
static cl::opt< bool > VerifyCoalescing("verify-coalescing", cl::desc("Verify machine instrs before and after register coalescing"), cl::Hidden)
static cl::opt< unsigned > LargeIntervalFreqThreshold("large-interval-freq-threshold", cl::Hidden, cl::desc("For a large interval, if it is coalesed with other live " "intervals many times more than the threshold, stop its " "coalescing to control the compile time. "), cl::init(100))
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 bool definesFullReg(const MachineInstr &MI, Register Reg)
Returns true if MI defines the full vreg Reg, as opposed to just defining a subregister.
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))
static cl::opt< bool > UseTerminalRule("terminal-rule", cl::desc("Apply the terminal rule"), cl::init(false), cl::Hidden)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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 void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
bool test(unsigned Idx) const
Allocate memory in an ever growing pool, as if by bump-pointer.
A helper class for register coalescers.
bool flip()
Swap SrcReg and DstReg.
bool isCoalescable(const MachineInstr *) const
Return true if MI is a copy instruction that will become an identity copy after coalescing.
bool setRegisters(const MachineInstr *)
Set registers to match the copy instruction MI.
The location of a single variable, composed of an expression and 0 or more DbgValueLocEntries.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
bool isAsCheapAsAMove(const MachineInstr &MI) const override
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
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()
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.
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.
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.
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)
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.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LiveInterval & getInterval(Register Reg)
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.
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
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.
virtual void LRE_WillEraseInstruction(MachineInstr *MI)
Called immediately before erasing a dead machine instruction.
void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled=std::nullopt)
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
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...
bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI)
checkRematerializable - Manually add VNI to the list of rematerializable values if DefMI may be remat...
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx, bool cheapAsAMove)
canRematerializeAt - Determine if ParentVNI can be rematerialized at UseIdx.
This class represents the liveness of a register, stack slot, etc.
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
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
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
void verify() const
Walk the range and assert if any invariants fail to hold.
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 necessarilly including Idx,...
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.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
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.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
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 '...
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
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.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
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.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
int findRegisterUseOperandIdx(Register Reg, bool isKill=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a use of the specific register or -1 if it is not found.
bool isSafeToMove(AAResults *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
int findRegisterDefOperandIdx(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
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.
bool isDebugInstr() const
unsigned getNumOperands() const
Retuns the total number of operands.
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,...
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,...
iterator_range< mop_iterator > operands()
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.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
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
void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
bool allDefsAreDead() const
Return true if all the defs of this instruction are dead.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
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)
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
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)
defusechain_iterator - This class provides iterator support for machine operands in the function that...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
virtual void releaseMemory()
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Wrapper class representing virtual and physical registers.
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
bool isVirtual() const
Return true if the specified register number is in the virtual 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 last index in the given basic block number.
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)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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.
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.