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*>;
162 bool ShrinkMainRange =
false;
166 bool JoinGlobalCopies =
false;
170 bool JoinSplitEdges =
false;
202 void coalesceLocals();
205 void joinAllIntervals();
220 void lateLiveIntervalUpdate();
225 bool copyValueUndefInPredecessors(
LiveRange &S,
290 std::pair<bool,bool> removeCopyByCommutingDef(
const CoalescerPair &CP,
361 MI->eraseFromParent();
397char RegisterCoalescer::ID = 0;
402 "Simple Register Coalescing",
false,
false)
415 Dst =
MI->getOperand(0).getReg();
416 DstSub =
MI->getOperand(0).getSubReg();
417 Src =
MI->getOperand(1).getReg();
418 SrcSub =
MI->getOperand(1).getSubReg();
419 }
else if (
MI->isSubregToReg()) {
420 Dst =
MI->getOperand(0).getReg();
421 DstSub = tri.composeSubRegIndices(
MI->getOperand(0).getSubReg(),
422 MI->getOperand(3).getImm());
423 Src =
MI->getOperand(2).getReg();
424 SrcSub =
MI->getOperand(2).getSubReg();
439 for (
const auto &
MI : *
MBB) {
440 if (!
MI.isCopyLike() && !
MI.isUnconditionalBranch())
450 Flipped = CrossClass =
false;
453 unsigned SrcSub = 0, DstSub = 0;
456 Partial = SrcSub || DstSub;
459 if (Src.isPhysical()) {
460 if (Dst.isPhysical())
469 if (Dst.isPhysical()) {
472 Dst =
TRI.getSubReg(Dst, DstSub);
473 if (!Dst)
return false;
479 Dst =
TRI.getMatchingSuperReg(Dst, SrcSub,
MRI.getRegClass(Src));
480 if (!Dst)
return false;
481 }
else if (!
MRI.getRegClass(Src)->contains(Dst)) {
490 if (SrcSub && DstSub) {
492 if (Src == Dst && SrcSub != DstSub)
495 NewRC =
TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub,
502 NewRC =
TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
506 NewRC =
TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
509 NewRC =
TRI.getCommonSubClass(DstRC, SrcRC);
518 if (DstIdx && !SrcIdx) {
524 CrossClass = NewRC != DstRC || NewRC != SrcRC;
527 assert(Src.isVirtual() &&
"Src must be virtual");
528 assert(!(Dst.isPhysical() && DstSub) &&
"Cannot have a physical SubIdx");
547 unsigned SrcSub = 0, DstSub = 0;
555 }
else if (Src != SrcReg) {
561 if (!Dst.isPhysical())
563 assert(!DstIdx && !SrcIdx &&
"Inconsistent CoalescerPair state.");
566 Dst =
TRI.getSubReg(Dst, DstSub);
569 return DstReg == Dst;
571 return Register(
TRI.getSubReg(DstReg, SrcSub)) == Dst;
577 return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
578 TRI.composeSubRegIndices(DstIdx, DstSub);
582void RegisterCoalescer::getAnalysisUsage(
AnalysisUsage &AU)
const {
594void RegisterCoalescer::eliminateDeadDefs(
LiveRangeEdit *Edit) {
604void RegisterCoalescer::LRE_WillEraseInstruction(
MachineInstr *
MI) {
609bool RegisterCoalescer::adjustCopiesBackFrom(
const CoalescerPair &CP,
611 assert(!
CP.isPartial() &&
"This doesn't work for partial copies.");
612 assert(!
CP.isPhys() &&
"This doesn't work for physreg copies.");
637 if (BS == IntB.
end())
return false;
638 VNInfo *BValNo = BS->valno;
643 if (BValNo->
def != CopyIdx)
return false;
649 if (AS == IntA.
end())
return false;
650 VNInfo *AValNo = AS->valno;
656 if (!
CP.isCoalescable(ACopyMI) || !ACopyMI->
isFullCopy())
662 if (ValS == IntB.
end())
675 if (ValS+1 != BS)
return false;
679 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
683 BValNo->
def = FillerStart;
691 if (BValNo != ValS->valno)
700 S.removeSegment(*SS,
true);
704 if (!S.getVNInfoAt(FillerStart)) {
707 S.extendInBlock(BBStart, FillerStart);
709 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
712 if (SubBValNo != SubValSNo)
713 S.MergeValueNumberInto(SubBValNo, SubValSNo);
729 bool RecomputeLiveRange = AS->end == CopyIdx;
730 if (!RecomputeLiveRange) {
733 if (SS != S.end() &&
SS->end == CopyIdx) {
734 RecomputeLiveRange =
true;
739 if (RecomputeLiveRange)
746bool RegisterCoalescer::hasOtherReachingDefs(
LiveInterval &IntA,
756 if (ASeg.
valno != AValNo)
continue;
758 if (BI != IntB.
begin())
760 for (; BI != IntB.
end() && ASeg.
end >= BI->start; ++BI) {
761 if (BI->valno == BValNo)
763 if (BI->start <= ASeg.
start && BI->end > ASeg.
start)
765 if (BI->start > ASeg.
start && BI->start < ASeg.
end)
774static std::pair<bool,bool>
777 bool Changed =
false;
778 bool MergedWithDead =
false;
780 if (S.
valno != SrcValNo)
791 MergedWithDead =
true;
794 return std::make_pair(Changed, MergedWithDead);
798RegisterCoalescer::removeCopyByCommutingDef(
const CoalescerPair &CP,
831 assert(BValNo !=
nullptr && BValNo->
def == CopyIdx);
837 return {
false,
false };
840 return {
false,
false };
842 return {
false,
false };
849 return {
false,
false };
862 return {
false,
false };
867 return {
false,
false };
871 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
872 return {
false,
false };
881 if (US == IntA.
end() || US->valno != AValNo)
885 return {
false,
false };
897 return {
false,
false };
899 !
MRI->constrainRegClass(IntB.
reg(),
MRI->getRegClass(IntA.
reg())))
900 return {
false,
false };
901 if (NewMI !=
DefMI) {
926 UseMO.setReg(NewReg);
931 assert(US != IntA.
end() &&
"Use must be live");
932 if (US->valno != AValNo)
935 UseMO.setIsKill(
false);
937 UseMO.substPhysReg(NewReg, *
TRI);
939 UseMO.setReg(NewReg);
958 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
961 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
963 S.MergeValueNumberInto(SubDVNI, SubBValNo);
971 bool ShrinkB =
false;
985 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
994 MaskA |= SA.LaneMask;
997 Allocator, SA.LaneMask,
998 [&Allocator, &SA, CopyIdx, ASubValNo,
1000 VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
1001 : SR.getVNInfoAt(CopyIdx);
1002 assert(BSubValNo != nullptr);
1003 auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
1004 ShrinkB |= P.second;
1006 BSubValNo->def = ASubValNo->def;
1014 if ((SB.LaneMask & MaskA).any())
1018 SB.removeSegment(*S,
true);
1022 BValNo->
def = AValNo->
def;
1024 ShrinkB |=
P.second;
1031 return {
true, ShrinkB };
1081bool RegisterCoalescer::removePartialRedundancy(
const CoalescerPair &CP,
1114 bool FoundReverseCopy =
false;
1133 bool ValB_Changed =
false;
1134 for (
auto *VNI : IntB.
valnos) {
1135 if (VNI->isUnused())
1138 ValB_Changed =
true;
1146 FoundReverseCopy =
true;
1150 if (!FoundReverseCopy)
1160 if (CopyLeftBB && CopyLeftBB->
succ_size() > 1)
1171 if (InsPos != CopyLeftBB->
end()) {
1177 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Move the copy to "
1182 TII->get(TargetOpcode::COPY), IntB.
reg())
1193 ErasedInstrs.
erase(NewCopyMI);
1195 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Remove the copy from "
1204 deleteInstr(&CopyMI);
1218 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1219 assert(BValNo &&
"All sublanes should be live");
1228 for (
unsigned I = 0;
I != EndPoints.
size(); ) {
1230 EndPoints[
I] = EndPoints.
back();
1252 assert(!Reg.isPhysical() &&
"This code cannot handle physreg aliasing");
1255 if (Op.getReg() != Reg)
1259 if (Op.getSubReg() == 0 || Op.isUndef())
1265bool RegisterCoalescer::reMaterializeTrivialDef(
const CoalescerPair &CP,
1269 Register SrcReg =
CP.isFlipped() ?
CP.getDstReg() :
CP.getSrcReg();
1270 unsigned SrcIdx =
CP.isFlipped() ?
CP.getDstIdx() :
CP.getSrcIdx();
1271 Register DstReg =
CP.isFlipped() ?
CP.getSrcReg() :
CP.getDstReg();
1272 unsigned DstIdx =
CP.isFlipped() ?
CP.getSrcIdx() :
CP.getDstIdx();
1294 LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS,
nullptr,
this);
1300 bool SawStore =
false;
1317 if (SrcIdx && DstIdx)
1325 unsigned NewDstIdx =
TRI->composeSubRegIndices(
CP.getSrcIdx(),
1328 NewDstReg =
TRI->getSubReg(DstReg, NewDstIdx);
1338 "Only expect to deal with virtual or physical registers");
1364 assert(SrcIdx == 0 &&
CP.isFlipped()
1365 &&
"Shouldn't have SrcIdx+DstIdx at this point");
1368 TRI->getCommonSubClass(DefRC, DstRC);
1369 if (CommonRC !=
nullptr) {
1377 if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1398 assert(MO.
isImplicit() &&
"No explicit operands after implicit operands.");
1406 ErasedInstrs.
insert(CopyMI);
1425 if (DefRC !=
nullptr) {
1427 NewRC =
TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1429 NewRC =
TRI->getCommonSubClass(NewRC, DefRC);
1430 assert(NewRC &&
"subreg chosen for remat incompatible with instruction");
1435 SR.LaneMask =
TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1437 MRI->setRegClass(DstReg, NewRC);
1440 updateRegDefsUses(DstReg, DstReg, DstIdx);
1468 if (!SR.liveAt(DefIndex))
1469 SR.createDeadDef(DefIndex,
Alloc);
1470 MaxMask &= ~SR.LaneMask;
1472 if (MaxMask.
any()) {
1490 bool UpdatedSubRanges =
false;
1495 if ((SR.
LaneMask & DstMask).none()) {
1497 <<
"Removing undefined SubRange "
1502 UpdatedSubRanges =
true;
1514 if (UpdatedSubRanges)
1521 "Only expect virtual or physical registers in remat");
1524 CopyDstReg,
true ,
true ,
false ));
1556 for (
unsigned i = 0, e = NewMIImplDefs.
size(); i != e; ++i) {
1568 if (
MRI->use_nodbg_empty(SrcReg)) {
1574 UseMO.substPhysReg(DstReg, *
TRI);
1576 UseMO.setReg(DstReg);
1585 if (ToBeUpdated.
count(SrcReg))
1588 unsigned NumCopyUses = 0;
1590 if (UseMO.getParent()->isCopyLike())
1596 if (!DeadDefs.
empty())
1597 eliminateDeadDefs(&Edit);
1599 ToBeUpdated.
insert(SrcReg);
1617 unsigned SrcSubIdx = 0, DstSubIdx = 0;
1618 if(!
isMoveInstr(*
TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1627 if ((SR.
LaneMask & SrcMask).none())
1640 assert(Seg !=
nullptr &&
"No segment for defining instruction");
1645 if (((V &&
V->isPHIDef()) || (!V && !DstLI.
liveAt(
Idx)))) {
1646 CopyMI->
setDesc(
TII->get(TargetOpcode::IMPLICIT_DEF));
1668 if ((SR.
LaneMask & DstMask).none())
1690 if ((SR.
LaneMask & UseMask).none())
1698 isLive = DstLI.
liveAt(UseIdx);
1711 if (MO.
getReg() == DstReg)
1723 bool IsUndef =
true;
1725 if ((S.LaneMask & Mask).none())
1727 if (S.liveAt(UseIdx)) {
1740 ShrinkMainRange =
true;
1749 if (DstInt && DstInt->
hasSubRanges() && DstReg != SrcReg) {
1755 if (
MI.isDebugInstr())
1758 addUndefFlag(*DstInt, UseIdx, MO,
SubReg);
1764 I =
MRI->reg_instr_begin(SrcReg),
E =
MRI->reg_instr_end();
1773 if (SrcReg == DstReg && !Visited.
insert(
UseMI).second)
1786 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1792 if (SubIdx && MO.
isDef())
1797 if (MO.
isUse() && !DstIsPhys) {
1798 unsigned SubUseIdx =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
1799 if (SubUseIdx != 0 &&
MRI->shouldTrackSubRegLiveness(DstReg)) {
1816 addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);
1827 dbgs() <<
"\t\tupdated: ";
1835bool RegisterCoalescer::canJoinPhys(
const CoalescerPair &CP) {
1839 if (!
MRI->isReserved(
CP.getDstReg())) {
1840 LLVM_DEBUG(
dbgs() <<
"\tCan only merge into reserved registers.\n");
1849 dbgs() <<
"\tCannot join complex intervals into reserved register.\n");
1853bool RegisterCoalescer::copyValueUndefInPredecessors(
1867void RegisterCoalescer::setUndefOnPrunedSubRegUses(
LiveInterval &LI,
1874 if (SubRegIdx == 0 || MO.
isUndef())
1880 if (!S.
liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {
1896bool RegisterCoalescer::joinCopy(
MachineInstr *CopyMI,
bool &Again) {
1901 if (!
CP.setRegisters(CopyMI)) {
1906 if (
CP.getNewRC()) {
1907 auto SrcRC =
MRI->getRegClass(
CP.getSrcReg());
1908 auto DstRC =
MRI->getRegClass(
CP.getDstReg());
1909 unsigned SrcIdx =
CP.getSrcIdx();
1910 unsigned DstIdx =
CP.getDstIdx();
1911 if (
CP.isFlipped()) {
1915 if (!
TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1916 CP.getNewRC(), *LIS)) {
1928 eliminateDeadDefs();
1935 if (
MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
1936 if (UndefMI->isImplicitDef())
1938 deleteInstr(CopyMI);
1946 if (
CP.getSrcReg() ==
CP.getDstReg()) {
1948 LLVM_DEBUG(
dbgs() <<
"\tCopy already coalesced: " << LI <<
'\n');
1953 assert(ReadVNI &&
"No value before copy and no <undef> flag.");
1954 assert(ReadVNI != DefVNI &&
"Cannot read and define the same value.");
1969 if (copyValueUndefInPredecessors(S,
MBB, SLRQ)) {
1970 LLVM_DEBUG(
dbgs() <<
"Incoming sublane value is undef at copy\n");
1971 PrunedLanes |= S.LaneMask;
1978 if (PrunedLanes.
any()) {
1980 << PrunedLanes <<
'\n');
1981 setUndefOnPrunedSubRegUses(LI,
CP.getSrcReg(), PrunedLanes);
1986 deleteInstr(CopyMI);
1995 if (!canJoinPhys(CP)) {
1998 bool IsDefCopy =
false;
1999 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2012 dbgs() <<
"\tConsidering merging to "
2013 <<
TRI->getRegClassName(
CP.getNewRC()) <<
" with ";
2014 if (
CP.getDstIdx() &&
CP.getSrcIdx())
2016 <<
TRI->getSubRegIndexName(
CP.getDstIdx()) <<
" and "
2018 <<
TRI->getSubRegIndexName(
CP.getSrcIdx()) <<
'\n';
2026 ShrinkMainRange =
false;
2032 if (!joinIntervals(CP)) {
2037 bool IsDefCopy =
false;
2038 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2043 if (!
CP.isPartial() && !
CP.isPhys()) {
2044 bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2045 bool Shrink =
false;
2047 std::tie(Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2049 deleteInstr(CopyMI);
2051 Register DstReg =
CP.isFlipped() ?
CP.getSrcReg() :
CP.getDstReg();
2063 if (!
CP.isPartial() && !
CP.isPhys())
2064 if (removePartialRedundancy(CP, *CopyMI))
2075 if (
CP.isCrossClass()) {
2077 MRI->setRegClass(
CP.getDstReg(),
CP.getNewRC());
2088 ErasedInstrs.
erase(CopyMI);
2093 updateRegDefsUses(
CP.getDstReg(),
CP.getDstReg(),
CP.getDstIdx());
2094 updateRegDefsUses(
CP.getSrcReg(),
CP.getDstReg(),
CP.getSrcIdx());
2097 if (ShrinkMask.
any()) {
2100 if ((S.LaneMask & ShrinkMask).none())
2105 ShrinkMainRange =
true;
2113 if (ToBeUpdated.
count(
CP.getSrcReg()))
2114 ShrinkMainRange =
true;
2116 if (ShrinkMainRange) {
2126 TRI->updateRegAllocHint(
CP.getSrcReg(),
CP.getDstReg(), *MF);
2131 dbgs() <<
"\tResult = ";
2143bool RegisterCoalescer::joinReservedPhysReg(
CoalescerPair &CP) {
2146 assert(
CP.isPhys() &&
"Must be a physreg copy");
2147 assert(
MRI->isReserved(DstReg) &&
"Not a reserved register");
2151 assert(
RHS.containsOneValue() &&
"Invalid join with reserved register");
2160 if (!
MRI->isConstantPhysReg(DstReg)) {
2164 if (!
MRI->isReserved(*RI))
2177 !RegMaskUsable.
test(DstReg)) {
2190 if (
CP.isFlipped()) {
2198 CopyMI =
MRI->getVRegDef(SrcReg);
2199 deleteInstr(CopyMI);
2208 if (!
MRI->hasOneNonDBGUse(SrcReg)) {
2219 CopyMI = &*
MRI->use_instr_nodbg_begin(SrcReg);
2223 if (!
MRI->isConstantPhysReg(DstReg)) {
2231 if (
MI->readsRegister(DstReg,
TRI)) {
2241 <<
printReg(DstReg,
TRI) <<
" at " << CopyRegIdx <<
"\n");
2244 deleteInstr(CopyMI);
2254 MRI->clearKillFlags(
CP.getSrcReg());
2339 const unsigned SubIdx;
2347 const bool SubRangeJoin;
2350 const bool TrackSubRegLiveness;
2366 enum ConflictResolution {
2398 ConflictResolution Resolution = CR_Keep;
2408 VNInfo *RedefVNI =
nullptr;
2411 VNInfo *OtherVNI =
nullptr;
2424 bool ErasableImplicitDef =
false;
2428 bool Pruned =
false;
2431 bool PrunedComputed =
false;
2438 bool Identical =
false;
2442 bool isAnalyzed()
const {
return WriteLanes.
any(); }
2454 std::pair<const VNInfo *, Register> followCopyChain(
const VNInfo *VNI)
const;
2456 bool valuesIdentical(
VNInfo *Value0,
VNInfo *Value1,
const JoinVals &
Other)
const;
2465 ConflictResolution analyzeValue(
unsigned ValNo, JoinVals &
Other);
2470 void computeAssignment(
unsigned ValNo, JoinVals &
Other);
2501 bool isPrunedValue(
unsigned ValNo, JoinVals &
Other);
2507 bool TrackSubRegLiveness)
2508 : LR(LR),
Reg(
Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2509 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2510 NewVNInfo(newVNInfo),
CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2511 TRI(
TRI), Assignments(LR.getNumValNums(), -1),
2512 Vals(LR.getNumValNums()) {}
2516 bool mapValues(JoinVals &
Other);
2520 bool resolveConflicts(JoinVals &
Other);
2540 void pruneMainSegments(
LiveInterval &LI,
bool &ShrinkMainRange);
2551 void removeImplicitDefs();
2554 const int *getAssignments()
const {
return Assignments.
data(); }
2557 ConflictResolution getResolution(
unsigned Num)
const {
2558 return Vals[Num].Resolution;
2570 L |=
TRI->getSubRegIndexLaneMask(
2578std::pair<const VNInfo *, Register>
2579JoinVals::followCopyChain(
const VNInfo *VNI)
const {
2585 assert(
MI &&
"No defining instruction");
2586 if (!
MI->isFullCopy())
2587 return std::make_pair(VNI, TrackReg);
2588 Register SrcReg =
MI->getOperand(1).getReg();
2590 return std::make_pair(VNI, TrackReg);
2604 LaneBitmask SMask =
TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2605 if ((SMask & LaneMask).
none())
2613 return std::make_pair(VNI, TrackReg);
2616 if (ValueIn ==
nullptr) {
2623 return std::make_pair(
nullptr, SrcReg);
2628 return std::make_pair(VNI, TrackReg);
2631bool JoinVals::valuesIdentical(
VNInfo *Value0,
VNInfo *Value1,
2632 const JoinVals &
Other)
const {
2635 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2636 if (Orig0 == Value1 && Reg0 ==
Other.Reg)
2641 std::tie(Orig1, Reg1) =
Other.followCopyChain(Value1);
2645 if (Orig0 ==
nullptr || Orig1 ==
nullptr)
2646 return Orig0 == Orig1 && Reg0 == Reg1;
2652 return Orig0->
def == Orig1->
def && Reg0 == Reg1;
2655JoinVals::ConflictResolution
2656JoinVals::analyzeValue(
unsigned ValNo, JoinVals &
Other) {
2657 Val &
V = Vals[ValNo];
2658 assert(!
V.isAnalyzed() &&
"Value has already been analyzed!");
2670 :
TRI->getSubRegIndexLaneMask(SubIdx);
2671 V.ValidLanes =
V.WriteLanes = Lanes;
2680 V.ErasableImplicitDef =
true;
2684 V.ValidLanes =
V.WriteLanes = computeWriteLanes(
DefMI, Redef);
2703 assert((TrackSubRegLiveness ||
V.RedefVNI) &&
2704 "Instruction is reading nonexistent value");
2705 if (
V.RedefVNI !=
nullptr) {
2706 computeAssignment(
V.RedefVNI->id,
Other);
2707 V.ValidLanes |= Vals[
V.RedefVNI->id].ValidLanes;
2719 V.ErasableImplicitDef =
true;
2736 if (OtherVNI->def < VNI->
def)
2737 Other.computeAssignment(OtherVNI->id, *
this);
2738 else if (VNI->
def < OtherVNI->def && OtherLRQ.
valueIn()) {
2742 return CR_Impossible;
2744 V.OtherVNI = OtherVNI;
2745 Val &OtherV =
Other.Vals[OtherVNI->id];
2749 if (!OtherV.isAnalyzed() ||
Other.Assignments[OtherVNI->id] == -1)
2756 if ((
V.ValidLanes & OtherV.ValidLanes).any())
2758 return CR_Impossible;
2773 Other.computeAssignment(
V.OtherVNI->id, *
this);
2774 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
2776 if (OtherV.ErasableImplicitDef) {
2789 <<
", keeping it.\n");
2790 OtherV.ErasableImplicitDef =
false;
2797 dbgs() <<
"IMPLICIT_DEF defined at " <<
V.OtherVNI->def
2798 <<
" may be live into EH pad successors, keeping it.\n");
2799 OtherV.ErasableImplicitDef =
false;
2802 OtherV.ValidLanes &= ~OtherV.WriteLanes;
2817 if (
CP.isCoalescable(
DefMI)) {
2820 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2835 valuesIdentical(VNI,
V.OtherVNI,
Other)) {
2858 if ((
V.WriteLanes & OtherV.ValidLanes).none())
2871 "Only early clobber defs can overlap a kill");
2872 return CR_Impossible;
2879 if ((
TRI->getSubRegIndexLaneMask(
Other.SubIdx) & ~
V.WriteLanes).none())
2880 return CR_Impossible;
2882 if (TrackSubRegLiveness) {
2887 if (!OtherLI.hasSubRanges()) {
2889 return (OtherMask &
V.WriteLanes).none() ? CR_Replace : CR_Impossible;
2897 TRI->composeSubRegIndexLaneMask(
Other.SubIdx, OtherSR.LaneMask);
2898 if ((OtherMask &
V.WriteLanes).none())
2901 auto OtherSRQ = OtherSR.Query(VNI->
def);
2902 if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->
def) {
2904 return CR_Impossible;
2917 return CR_Impossible;
2926 return CR_Unresolved;
2929void JoinVals::computeAssignment(
unsigned ValNo, JoinVals &
Other) {
2930 Val &
V = Vals[ValNo];
2931 if (
V.isAnalyzed()) {
2934 assert(Assignments[ValNo] != -1 &&
"Bad recursion?");
2937 switch ((
V.Resolution = analyzeValue(ValNo,
Other))) {
2941 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't merge.");
2942 assert(
Other.Vals[
V.OtherVNI->id].isAnalyzed() &&
"Missing recursion");
2943 Assignments[ValNo] =
Other.Assignments[
V.OtherVNI->id];
2947 <<
V.OtherVNI->def <<
" --> @"
2948 << NewVNInfo[Assignments[ValNo]]->def <<
'\n');
2951 case CR_Unresolved: {
2953 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't prune");
2954 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
2957 if (OtherV.ErasableImplicitDef &&
2958 TrackSubRegLiveness &&
2959 (OtherV.WriteLanes & ~
V.ValidLanes).any()) {
2960 LLVM_DEBUG(
dbgs() <<
"Cannot erase implicit_def with missing values\n");
2962 OtherV.ErasableImplicitDef =
false;
2969 OtherV.Pruned =
true;
2974 Assignments[ValNo] = NewVNInfo.
size();
2980bool JoinVals::mapValues(JoinVals &
Other) {
2982 computeAssignment(i,
Other);
2983 if (Vals[i].Resolution == CR_Impossible) {
3001 assert(OtherI !=
Other.LR.end() &&
"No conflict?");
3006 if (
End >= MBBEnd) {
3008 << OtherI->valno->id <<
'@' << OtherI->start <<
'\n');
3012 << OtherI->valno->id <<
'@' << OtherI->start <<
" to "
3017 TaintExtent.push_back(std::make_pair(
End, TaintedLanes));
3020 if (++OtherI ==
Other.LR.end() || OtherI->start >= MBBEnd)
3024 const Val &OV =
Other.Vals[OtherI->valno->id];
3025 TaintedLanes &= ~OV.WriteLanes;
3028 }
while (TaintedLanes.
any());
3034 if (
MI.isDebugOrPseudoInstr())
3041 unsigned S =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
3042 if ((Lanes &
TRI->getSubRegIndexLaneMask(S)).any())
3048bool JoinVals::resolveConflicts(JoinVals &
Other) {
3051 assert(
V.Resolution != CR_Impossible &&
"Unresolvable conflict");
3052 if (
V.Resolution != CR_Unresolved)
3061 assert(
V.OtherVNI &&
"Inconsistent conflict resolution.");
3063 const Val &OtherV =
Other.Vals[
V.OtherVNI->id];
3068 LaneBitmask TaintedLanes =
V.WriteLanes & OtherV.ValidLanes;
3070 if (!taintExtent(i, TaintedLanes,
Other, TaintExtent))
3074 assert(!TaintExtent.
empty() &&
"There should be at least one conflict.");
3087 "Interference ends on VNI->def. Should have been handled earlier");
3090 assert(LastMI &&
"Range must end at a proper instruction");
3091 unsigned TaintNum = 0;
3094 if (usesLanes(*
MI,
Other.Reg,
Other.SubIdx, TaintedLanes)) {
3099 if (&*
MI == LastMI) {
3100 if (++TaintNum == TaintExtent.
size())
3103 assert(LastMI &&
"Range must end at a proper instruction");
3104 TaintedLanes = TaintExtent[TaintNum].second;
3110 V.Resolution = CR_Replace;
3116bool JoinVals::isPrunedValue(
unsigned ValNo, JoinVals &
Other) {
3117 Val &
V = Vals[ValNo];
3118 if (
V.Pruned ||
V.PrunedComputed)
3121 if (
V.Resolution != CR_Erase &&
V.Resolution != CR_Merge)
3126 V.PrunedComputed =
true;
3127 V.Pruned =
Other.isPrunedValue(
V.OtherVNI->id, *
this);
3131void JoinVals::pruneValues(JoinVals &
Other,
3133 bool changeInstrs) {
3136 switch (Vals[i].Resolution) {
3146 Val &OtherV =
Other.Vals[Vals[i].OtherVNI->id];
3147 bool EraseImpDef = OtherV.ErasableImplicitDef &&
3148 OtherV.Resolution == CR_Keep;
3149 if (!
Def.isBlock()) {
3169 <<
": " <<
Other.LR <<
'\n');
3174 if (isPrunedValue(i,
Other)) {
3181 << Def <<
": " << LR <<
'\n');
3239 bool DidPrune =
false;
3244 if (
V.Resolution != CR_Erase &&
3245 (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned))
3252 OtherDef =
V.OtherVNI->def;
3255 LLVM_DEBUG(
dbgs() <<
"\t\tExpecting instruction removal at " << Def
3263 if (ValueOut !=
nullptr && (Q.
valueIn() ==
nullptr ||
3264 (
V.Identical &&
V.Resolution == CR_Erase &&
3265 ValueOut->
def == Def))) {
3267 <<
" at " << Def <<
"\n");
3274 if (
V.Identical && S.Query(OtherDef).valueOutOrDead()) {
3284 ShrinkMask |= S.LaneMask;
3298 ShrinkMask |= S.LaneMask;
3310 if (VNI->
def == Def)
3316void JoinVals::pruneMainSegments(
LiveInterval &LI,
bool &ShrinkMainRange) {
3320 if (Vals[i].Resolution != CR_Keep)
3325 Vals[i].Pruned =
true;
3326 ShrinkMainRange =
true;
3330void JoinVals::removeImplicitDefs() {
3333 if (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned)
3349 switch (Vals[i].Resolution) {
3354 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3366 if (LI !=
nullptr) {
3391 ED = ED.
isValid() ? std::min(ED,
I->start) :
I->start;
3393 LE =
LE.isValid() ? std::max(LE,
I->end) :
I->
end;
3396 NewEnd = std::min(NewEnd, LE);
3398 NewEnd = std::min(NewEnd, ED);
3404 if (S != LR.
begin())
3405 std::prev(S)->end = NewEnd;
3409 dbgs() <<
"\t\tremoved " << i <<
'@' <<
Def <<
": " << LR <<
'\n';
3411 dbgs() <<
"\t\t LHS = " << *LI <<
'\n';
3418 assert(
MI &&
"No instruction to erase");
3421 if (
Reg.isVirtual() && Reg !=
CP.getSrcReg() && Reg !=
CP.getDstReg())
3427 MI->eraseFromParent();
3440 JoinVals RHSVals(RRange,
CP.getSrcReg(),
CP.getSrcIdx(), LaneMask,
3441 NewVNInfo, CP, LIS,
TRI,
true,
true);
3442 JoinVals LHSVals(LRange,
CP.getDstReg(),
CP.getDstIdx(), LaneMask,
3443 NewVNInfo, CP, LIS,
TRI,
true,
true);
3450 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
3455 if (!LHSVals.resolveConflicts(RHSVals) ||
3456 !RHSVals.resolveConflicts(LHSVals)) {
3467 LHSVals.pruneValues(RHSVals, EndPoints,
false);
3468 RHSVals.pruneValues(LHSVals, EndPoints,
false);
3470 LHSVals.removeImplicitDefs();
3471 RHSVals.removeImplicitDefs();
3477 LRange.
join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
3481 <<
' ' << LRange <<
"\n");
3482 if (EndPoints.
empty())
3488 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3489 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3490 dbgs() << EndPoints[i];
3494 dbgs() <<
": " << LRange <<
'\n';
3499void RegisterCoalescer::mergeSubRangeInto(
LiveInterval &LI,
3503 unsigned ComposeSubRegIdx) {
3506 Allocator, LaneMask,
3509 SR.assign(ToMerge, Allocator);
3512 LiveRange RangeCopy(ToMerge, Allocator);
3513 joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
3519bool RegisterCoalescer::isHighCostLiveInterval(
LiveInterval &LI) {
3522 auto &Counter = LargeLIVisitCounter[LI.
reg()];
3534 bool TrackSubRegLiveness =
MRI->shouldTrackSubRegLiveness(*
CP.getNewRC());
3536 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3538 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3540 LLVM_DEBUG(
dbgs() <<
"\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS <<
'\n');
3542 if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))
3547 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3551 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3555 if (
RHS.hasSubRanges() ||
LHS.hasSubRanges()) {
3560 unsigned DstIdx =
CP.getDstIdx();
3561 if (!
LHS.hasSubRanges()) {
3563 :
TRI->getSubRegIndexLaneMask(DstIdx);
3566 LHS.createSubRangeFrom(Allocator, Mask, LHS);
3567 }
else if (DstIdx != 0) {
3578 unsigned SrcIdx =
CP.getSrcIdx();
3579 if (!
RHS.hasSubRanges()) {
3581 :
TRI->getSubRegIndexLaneMask(SrcIdx);
3582 mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);
3587 mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);
3594 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3596 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3597 RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3605 LHSVals.pruneValues(RHSVals, EndPoints,
true);
3606 RHSVals.pruneValues(LHSVals, EndPoints,
true);
3611 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3612 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3613 while (!ShrinkRegs.
empty())
3617 checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
3621 auto RegIt = RegToPHIIdx.
find(
CP.getSrcReg());
3622 if (RegIt != RegToPHIIdx.
end()) {
3624 for (
unsigned InstID : RegIt->second) {
3625 auto PHIIt = PHIValToPos.
find(InstID);
3630 auto LII =
RHS.find(SI);
3631 if (LII ==
RHS.end() || LII->start > SI)
3646 if (
CP.getSrcIdx() != 0 ||
CP.getDstIdx() != 0)
3649 if (PHIIt->second.SubReg && PHIIt->second.SubReg !=
CP.getSrcIdx())
3653 PHIIt->second.Reg =
CP.getDstReg();
3657 if (
CP.getSrcIdx() != 0)
3658 PHIIt->second.SubReg =
CP.getSrcIdx();
3664 auto InstrNums = RegIt->second;
3665 RegToPHIIdx.
erase(RegIt);
3669 RegIt = RegToPHIIdx.
find(
CP.getDstReg());
3670 if (RegIt != RegToPHIIdx.
end())
3671 RegIt->second.insert(RegIt->second.end(), InstrNums.begin(),
3674 RegToPHIIdx.
insert({
CP.getDstReg(), InstrNums});
3678 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3683 MRI->clearKillFlags(
LHS.reg());
3684 MRI->clearKillFlags(
RHS.reg());
3686 if (!EndPoints.
empty()) {
3690 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3691 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3692 dbgs() << EndPoints[i];
3696 dbgs() <<
": " <<
LHS <<
'\n';
3705 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(
CP);
3716 for (
auto *
X : ToInsert) {
3717 for (
const auto &Op :
X->debug_operands()) {
3718 if (
Op.isReg() &&
Op.getReg().isVirtual())
3729 for (
auto &
MBB : MF) {
3732 for (
auto &
MI :
MBB) {
3733 if (
MI.isDebugValue()) {
3735 return MO.isReg() && MO.getReg().isVirtual();
3737 ToInsert.push_back(&
MI);
3738 }
else if (!
MI.isDebugOrPseudoInstr()) {
3740 CloseNewDVRange(CurrentSlot);
3749 for (
auto &Pair : DbgVRegToValues)
3753void RegisterCoalescer::checkMergingChangesDbgValues(
CoalescerPair &CP,
3757 JoinVals &RHSVals) {
3759 checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
3763 checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
3767 ScanForSrcReg(
CP.getSrcReg());
3768 ScanForDstReg(
CP.getDstReg());
3771void RegisterCoalescer::checkMergingChangesDbgValuesImpl(
Register Reg,
3774 JoinVals &RegVals) {
3776 auto VRegMapIt = DbgVRegToValues.
find(Reg);
3777 if (VRegMapIt == DbgVRegToValues.
end())
3780 auto &DbgValueSet = VRegMapIt->second;
3781 auto DbgValueSetIt = DbgValueSet.begin();
3782 auto SegmentIt = OtherLR.
begin();
3784 bool LastUndefResult =
false;
3789 auto ShouldUndef = [&RegVals, &
RegLR, &LastUndefResult,
3794 if (LastUndefIdx ==
Idx)
3795 return LastUndefResult;
3802 if (OtherIt ==
RegLR.end())
3811 auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3812 LastUndefResult = Resolution != JoinVals::CR_Keep &&
3813 Resolution != JoinVals::CR_Erase;
3815 return LastUndefResult;
3821 while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.
end()) {
3822 if (DbgValueSetIt->first < SegmentIt->end) {
3825 if (DbgValueSetIt->first >= SegmentIt->start) {
3826 bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3827 bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3828 if (HasReg && ShouldUndefReg) {
3830 DbgValueSetIt->second->setDebugValueUndef();
3844struct MBBPriorityInfo {
3850 :
MBB(mbb),
Depth(depth), IsSplit(issplit) {}
3860 const MBBPriorityInfo *RHS) {
3862 if (
LHS->Depth !=
RHS->Depth)
3863 return LHS->Depth >
RHS->Depth ? -1 : 1;
3866 if (
LHS->IsSplit !=
RHS->IsSplit)
3867 return LHS->IsSplit ? -1 : 1;
3871 unsigned cl =
LHS->MBB->pred_size() +
LHS->MBB->succ_size();
3872 unsigned cr =
RHS->MBB->pred_size() +
RHS->MBB->succ_size();
3874 return cl > cr ? -1 : 1;
3877 return LHS->MBB->getNumber() <
RHS->MBB->getNumber() ? -1 : 1;
3882 if (!Copy->isCopy())
3885 if (Copy->getOperand(1).isUndef())
3888 Register SrcReg = Copy->getOperand(1).getReg();
3889 Register DstReg = Copy->getOperand(0).getReg();
3897void RegisterCoalescer::lateLiveIntervalUpdate() {
3903 if (!DeadDefs.
empty())
3904 eliminateDeadDefs();
3906 ToBeUpdated.clear();
3909bool RegisterCoalescer::
3911 bool Progress =
false;
3934 assert(Copy.isCopyLike());
3937 if (&
MI != &Copy &&
MI.isCopyLike())
3942bool RegisterCoalescer::applyTerminalRule(
const MachineInstr &Copy)
const {
3947 unsigned SrcSubReg = 0, DstSubReg = 0;
3948 if (!
isMoveInstr(*
TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
3969 if (&
MI == &Copy || !
MI.isCopyLike() ||
MI.getParent() != OrigBB)
3972 unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
3973 if (!
isMoveInstr(*
TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
3976 if (OtherReg == SrcReg)
3977 OtherReg = OtherSrcReg;
3997 const unsigned PrevSize = WorkList.
size();
3998 if (JoinGlobalCopies) {
4006 if (!
MI.isCopyLike())
4008 bool ApplyTerminalRule = applyTerminalRule(
MI);
4010 if (ApplyTerminalRule)
4015 if (ApplyTerminalRule)
4022 LocalWorkList.
append(LocalTerminals.
begin(), LocalTerminals.
end());
4028 if (MII.isCopyLike()) {
4029 if (applyTerminalRule(MII))
4041 CurrList(WorkList.
begin() + PrevSize, WorkList.
end());
4042 if (copyCoalesceWorkList(CurrList))
4043 WorkList.
erase(std::remove(WorkList.
begin() + PrevSize, WorkList.
end(),
4044 nullptr), WorkList.
end());
4047void RegisterCoalescer::coalesceLocals() {
4048 copyCoalesceWorkList(LocalWorkList);
4049 for (
unsigned j = 0, je = LocalWorkList.
size(); j != je; ++j) {
4050 if (LocalWorkList[j])
4053 LocalWorkList.
clear();
4056void RegisterCoalescer::joinAllIntervals() {
4057 LLVM_DEBUG(
dbgs() <<
"********** JOINING INTERVALS ***********\n");
4058 assert(WorkList.
empty() && LocalWorkList.
empty() &&
"Old data still around.");
4060 std::vector<MBBPriorityInfo> MBBs;
4061 MBBs.reserve(MF->size());
4063 MBBs.push_back(MBBPriorityInfo(&
MBB,
Loops->getLoopDepth(&
MBB),
4069 unsigned CurrDepth = std::numeric_limits<unsigned>::max();
4070 for (MBBPriorityInfo &
MBB : MBBs) {
4072 if (JoinGlobalCopies &&
MBB.Depth < CurrDepth) {
4074 CurrDepth =
MBB.Depth;
4076 copyCoalesceInMBB(
MBB.MBB);
4078 lateLiveIntervalUpdate();
4083 while (copyCoalesceWorkList(WorkList))
4085 lateLiveIntervalUpdate();
4088void RegisterCoalescer::releaseMemory() {
4089 ErasedInstrs.
clear();
4092 InflateRegs.
clear();
4093 LargeLIVisitCounter.
clear();
4097 LLVM_DEBUG(
dbgs() <<
"********** SIMPLE REGISTER COALESCING **********\n"
4098 <<
"********** Function: " << fn.
getName() <<
'\n');
4110 dbgs() <<
"* Skipped as it exposes functions that returns twice.\n");
4119 LIS = &getAnalysis<LiveIntervals>();
4120 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4121 Loops = &getAnalysis<MachineLoopInfo>();
4130 for (
const auto &DebugPHI : MF->DebugPHIPositions) {
4133 unsigned SubReg = DebugPHI.second.SubReg;
4136 PHIValToPos.
insert(std::make_pair(DebugPHI.first,
P));
4137 RegToPHIIdx[
Reg].push_back(DebugPHI.first);
4146 MF->verify(
this,
"Before register coalescing");
4148 DbgVRegToValues.
clear();
4161 InflateRegs.
erase(std::unique(InflateRegs.
begin(), InflateRegs.
end()),
4165 for (
unsigned i = 0, e = InflateRegs.
size(); i != e; ++i) {
4167 if (
MRI->reg_nodbg_empty(Reg))
4169 if (
MRI->recomputeRegClass(Reg)) {
4171 <<
TRI->getRegClassName(
MRI->getRegClass(Reg)) <<
'\n');
4178 if (!
MRI->shouldTrackSubRegLiveness(Reg)) {
4186 assert((S.LaneMask & ~MaxMask).none());
4196 for (
auto &p : MF->DebugPHIPositions) {
4197 auto it = PHIValToPos.
find(
p.first);
4199 p.second.Reg = it->second.Reg;
4200 p.second.SubReg = it->second.SubReg;
4203 PHIValToPos.
clear();
4204 RegToPHIIdx.
clear();
4208 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
SmallVector< uint32_t, 0 > Writes
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 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(256))
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< 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 DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness)
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)
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 hasEHPadSuccessor() 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
iterator_range< filtered_mop_iterator > all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
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.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
bool isValid() const
Returns true if this is a valid index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the 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...