66#define DEBUG_TYPE "two-address-instruction"
68STATISTIC(NumTwoAddressInstrs,
"Number of two-address instructions");
69STATISTIC(NumCommuted ,
"Number of instructions commuted to coalesce");
70STATISTIC(NumAggrCommuted ,
"Number of instructions aggressively commuted");
71STATISTIC(NumConvertedTo3Addr,
"Number of instructions promoted to 3-address");
72STATISTIC(NumReSchedUps,
"Number of instructions re-scheduled up");
73STATISTIC(NumReSchedDowns,
"Number of instructions re-scheduled down");
77class TwoAddressInstructionImpl {
78 const CodeGenOptions &Opts;
110 bool noUseAfterLastDef(
Register Reg,
unsigned Dist,
unsigned &LastDef);
113 bool &IsSrcPhys,
bool &IsDstPhys)
const;
123 bool &IsDstPhys)
const;
138 unsigned RegBIdx,
unsigned RegCIdx,
unsigned Dist);
155 unsigned SrcIdx,
unsigned DstIdx,
156 unsigned &Dist,
bool shouldOnlyCommute);
171 void processTiedPairs(
MachineInstr *
MI, TiedPairList&,
unsigned &Dist);
173 bool processStatepoint(
MachineInstr *
MI, TiedOperandMap &TiedOperands);
188 TwoAddressInstructionLegacyPass() : MachineFunctionPass(ID) {}
192 TwoAddressInstructionImpl Impl(MF,
this);
196 Impl.setOptLevel(CodeGenOptLevel::None);
200 void getAnalysisUsage(AnalysisUsage &AU)
const override {
218 TwoAddressInstructionImpl Impl(MF, MFAM, LIS);
239char TwoAddressInstructionLegacyPass::ID = 0;
244 "Two-Address instruction pass",
false,
false)
246TwoAddressInstructionImpl::TwoAddressInstructionImpl(
250 TII(Func.getSubtarget().getInstrInfo()),
251 TRI(Func.getSubtarget().getRegisterInfo()),
252 InstrItins(Func.getSubtarget().getInstrItineraryData()),
253 MRI(&Func.getRegInfo()), LIS(LIS),
254 OptLevel(Func.getTarget().getOptLevel()) {}
256TwoAddressInstructionImpl::TwoAddressInstructionImpl(
MachineFunction &Func,
259 TII(
Func.getSubtarget().getInstrInfo()),
260 TRI(
Func.getSubtarget().getRegisterInfo()),
261 InstrItins(
Func.getSubtarget().getInstrItineraryData()),
262 MRI(&
Func.getRegInfo()), OptLevel(
Func.getTarget().getOptLevel()) {
264 LIS = LISWrapper ? &LISWrapper->
getLIS() :
nullptr;
269TwoAddressInstructionImpl::getSingleDef(
Register Reg,
271 MachineInstr *Ret =
nullptr;
273 if (
DefMI.getParent() != BB ||
DefMI.isDebugValue())
277 else if (Ret != &
DefMI)
285 int DefRegIdx =
MI->findRegisterDefOperandIdx(DefReg,
TRI);
288 return MI->isRegTiedToUseOperand(DefRegIdx, &TiedOpIdx);
298bool TwoAddressInstructionImpl::isRevCopyChain(
Register FromReg,
Register ToReg,
301 for (
int i = 0; i < Maxlen; i++) {
302 MachineInstr *
Def = getSingleDef(TmpReg,
MBB);
307 TmpReg =
Def->getOperand(1).getReg();
308 else if (
unsigned TiedOpIdx; Opts.twoaddr_analyze_revcopy_tied &&
310 Register TiedUseReg =
Def->getOperand(TiedOpIdx).getReg();
313 if (TiedUseReg == TmpReg)
329bool TwoAddressInstructionImpl::noUseAfterLastDef(
Register Reg,
unsigned Dist,
332 unsigned LastUse = Dist;
334 MachineInstr *
MI = MO.getParent();
335 if (
MI->getParent() !=
MBB ||
MI->isDebugValue())
337 auto DI = DistanceMap.
find(
MI);
338 if (DI == DistanceMap.
end())
340 if (MO.isUse() && DI->second < LastUse)
341 LastUse = DI->second;
342 if (MO.isDef() && DI->second > LastDef)
343 LastDef = DI->second;
346 return !(LastUse > LastDef && LastUse < Dist);
352bool TwoAddressInstructionImpl::isCopyToReg(MachineInstr &
MI,
Register &SrcReg,
354 bool &IsDstPhys)
const {
357 if (
MI.isCopy() ||
MI.isSubregToReg()) {
358 DstReg =
MI.getOperand(0).getReg();
359 SrcReg =
MI.getOperand(1).getReg();
360 }
else if (
MI.isInsertSubreg()) {
361 DstReg =
MI.getOperand(0).getReg();
362 SrcReg =
MI.getOperand(2).getReg();
372bool TwoAddressInstructionImpl::isPlainlyKilled(
const MachineInstr *
MI,
379 LiveInterval::const_iterator
I = LR.
find(useIdx);
387bool TwoAddressInstructionImpl::isPlainlyKilled(
const MachineInstr *
MI,
402 return isPlainlyKilled(MI, LIS->getRegUnit(U));
406 return MI->killsRegister(
Reg,
nullptr);
411bool TwoAddressInstructionImpl::isPlainlyKilled(
412 const MachineOperand &MO)
const {
433bool TwoAddressInstructionImpl::isKilled(MachineInstr &
MI,
Register Reg,
434 bool allowFalsePositives)
const {
450 bool IsSrcPhys, IsDstPhys;
454 if (!isCopyToReg(*
DefMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
463 for (
unsigned i = 0,
NumOps =
MI.getNumOperands(); i !=
NumOps; ++i) {
468 if (
MI.isRegTiedToDefOperand(i, &ti)) {
469 DstReg =
MI.getOperand(ti).getReg();
478MachineInstr *TwoAddressInstructionImpl::findOnlyInterestingUse(
480 bool &IsDstPhys)
const {
481 MachineOperand *UseOp =
nullptr;
487 if (
MI->getParent() !=
MBB)
489 if (isPlainlyKilled(
MI,
Reg))
498 if (isCopyToReg(
UseMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
507 if (
UseMI.isCommutable()) {
510 if (
TII->findCommutedOpIndices(
UseMI, Src1, Src2)) {
511 MachineOperand &MO =
UseMI.getOperand(Src1);
526 while (
Reg.isVirtual()) {
528 if (
SI == RegMap.
end())
532 if (
Reg.isPhysical())
538bool TwoAddressInstructionImpl::regsAreCompatible(
Register RegA,
544 return TRI->regsOverlap(RegA, RegB);
548void TwoAddressInstructionImpl::removeMapRegEntry(
549 const MachineOperand &MO, DenseMap<Register, Register> &RegMap)
const {
552 "removeMapRegEntry must be called with a register or regmask operand.");
555 for (
auto SI : RegMap) {
562 if (
TRI->regsOverlap(ToReg,
Reg))
568 for (
auto SrcReg : Srcs)
569 RegMap.erase(SrcReg);
580void TwoAddressInstructionImpl::removeClobberedSrcRegMap(MachineInstr *
MI) {
593 if (!Dst || Dst.isVirtual())
597 if (regsAreCompatible(Dst,
getMappedReg(Src, SrcRegMap)))
601 for (
const MachineOperand &MO :
MI->operands()) {
603 removeMapRegEntry(MO, SrcRegMap);
611 removeMapRegEntry(MO, SrcRegMap);
616bool TwoAddressInstructionImpl::regOverlapsSet(
617 const SmallVectorImpl<Register> &Set,
Register Reg)
const {
619 if (
TRI->regsOverlap(R,
Reg))
627bool TwoAddressInstructionImpl::isProfitableToCommute(
Register RegA,
632 if (OptLevel == CodeGenOptLevel::None)
653 if (!isPlainlyKilled(
MI, RegC))
670 bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA);
671 bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA);
677 if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
683 if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
689 unsigned LastDefC = 0;
690 if (!noUseAfterLastDef(RegC, Dist, LastDefC))
695 unsigned LastDefB = 0;
696 if (!noUseAfterLastDef(RegB, Dist, LastDefB))
714 if (isRevCopyChain(RegC, RegA, Opts.twoaddr_dataflow_edge_limit))
717 if (isRevCopyChain(RegB, RegA, Opts.twoaddr_dataflow_edge_limit))
722 if (
TII->hasCommutePreference(*
MI, Commute))
727 return LastDefB && LastDefC && LastDefC > LastDefB;
732bool TwoAddressInstructionImpl::commuteInstruction(MachineInstr *
MI,
737 Register RegC =
MI->getOperand(RegCIdx).getReg();
739 MachineInstr *NewMI =
TII->commuteInstruction(*
MI,
false, RegBIdx, RegCIdx);
741 if (NewMI ==
nullptr) {
748 "TargetInstrInfo::commuteInstruction() should not return a new "
749 "instruction unless it was requested.");
754 Register RegA =
MI->getOperand(DstIdx).getReg();
755 SrcRegMap[RegA] = FromRegC;
763bool TwoAddressInstructionImpl::isProfitableToConv3Addr(
Register RegA,
775 return (ToRegA && !regsAreCompatible(FromRegB, ToRegA));
780bool TwoAddressInstructionImpl::convertInstTo3Addr(
783 MachineInstrSpan MIS(mi,
MBB);
784 MachineInstr *NewMI =
TII->convertToThreeAddress(*mi, LIS);
788 for (MachineInstr &
MI : MIS)
789 DistanceMap.
insert(std::make_pair(&
MI, Dist++));
792 LLVM_DEBUG(
dbgs() <<
"2addr: CONVERTED IN-PLACE TO 3-ADDR: " << *mi);
795 dbgs() <<
"2addr: CONVERTING 2-ADDR: " << *mi;
796 dbgs() <<
"2addr: TO 3-ADDR: " << *NewMI;
800 if (
auto OldInstrNum = mi->peekDebugInstrNum()) {
801 assert(mi->getNumExplicitDefs() == 1);
805 unsigned OldIdx = mi->defs().begin()->getOperandNo();
806 unsigned NewIdx = NewMI->
defs().
begin()->getOperandNo();
811 std::make_pair(NewInstrNum, NewIdx));
822 SrcRegMap.
erase(RegA);
823 DstRegMap.
erase(RegB);
829void TwoAddressInstructionImpl::scanUses(
Register DstReg) {
835 while (MachineInstr *
UseMI =
836 findOnlyInterestingUse(
Reg,
MBB, IsCopy, NewReg, IsDstPhys)) {
837 if (IsCopy && !Processed.insert(
UseMI).second)
841 if (DI != DistanceMap.
end())
849 SrcRegMap[NewReg] =
Reg;
854 if (!VirtRegPairs.
empty()) {
856 while (!VirtRegPairs.
empty()) {
858 bool isNew = DstRegMap.
insert(std::make_pair(FromReg, ToReg)).second;
860 assert(DstRegMap[FromReg] == ToReg &&
"Can't map to two dst registers!");
863 bool isNew = DstRegMap.
insert(std::make_pair(DstReg, ToReg)).second;
865 assert(DstRegMap[DstReg] == ToReg &&
"Can't map to two dst registers!");
881void TwoAddressInstructionImpl::processCopy(MachineInstr *
MI) {
882 if (Processed.count(
MI))
885 bool IsSrcPhys, IsDstPhys;
887 if (!isCopyToReg(*
MI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
890 if (IsDstPhys && !IsSrcPhys) {
891 DstRegMap.
insert(std::make_pair(SrcReg, DstReg));
892 }
else if (!IsDstPhys && IsSrcPhys) {
893 bool isNew = SrcRegMap.
insert(std::make_pair(DstReg, SrcReg)).second;
895 assert(SrcRegMap[DstReg] == SrcReg &&
896 "Can't map to two src physical registers!");
901 Processed.insert(
MI);
907bool TwoAddressInstructionImpl::rescheduleMIBelowKill(
915 MachineInstr *
MI = &*mi;
916 auto DI = DistanceMap.
find(
MI);
917 if (DI == DistanceMap.
end())
922 assert(LI.
end() != LI.
begin() &&
"Reg should not have empty live interval.");
925 LiveInterval::const_iterator
I = LI.
find(MBBEndIdx);
926 if (
I != LI.
end() &&
I->start < MBBEndIdx)
944 bool SeenStore =
true;
945 if (!
MI->isSafeToMove(SeenStore))
955 for (
const MachineOperand &MO :
MI->operands()) {
964 Uses.push_back(MOReg);
965 if (MOReg !=
Reg && isPlainlyKilled(MO))
976 if (
End->isCopy() && regOverlapsSet(Defs,
End->getOperand(1).getReg()))
984 unsigned NumVisited = 0;
989 if (OtherMI.isDebugOrPseudoInstr())
994 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
995 OtherMI.isBranch() || OtherMI.isTerminator())
998 for (
const MachineOperand &MO : OtherMI.operands()) {
1005 if (regOverlapsSet(
Uses, MOReg))
1008 if (!MO.
isDead() && regOverlapsSet(Defs, MOReg))
1014 if (regOverlapsSet(Defs, MOReg))
1016 bool isKill = isPlainlyKilled(MO);
1017 if (MOReg !=
Reg && ((isKill && regOverlapsSet(
Uses, MOReg)) ||
1018 regOverlapsSet(Kills, MOReg)))
1021 if (MOReg ==
Reg && !isKill)
1025 assert((MOReg !=
Reg || &OtherMI == KillMI) &&
1026 "Found multiple kills of a register in a basic block");
1032 while (Begin !=
MBB->
begin() && std::prev(Begin)->isDebugInstr())
1044 if (!CopyMI.isDebugOrPseudoInstr())
1046 InsertPos = &CopyMI;
1053 DistanceMap.
erase(DI);
1064bool TwoAddressInstructionImpl::isDefTooClose(
Register Reg,
unsigned Dist,
1072 if (DDI == DistanceMap.
end())
1074 unsigned DefDist = DDI->second;
1075 assert(Dist > DefDist &&
"Visited def already?");
1085bool TwoAddressInstructionImpl::rescheduleKillAboveMI(
1093 MachineInstr *
MI = &*mi;
1094 auto DI = DistanceMap.
find(
MI);
1095 if (DI == DistanceMap.
end())
1100 assert(LI.
end() != LI.
begin() &&
"Reg should not have empty live interval.");
1103 LiveInterval::const_iterator
I = LI.
find(MBBEndIdx);
1104 if (
I != LI.
end() &&
I->start < MBBEndIdx)
1109 if (!KillMI ||
MI == KillMI)
1117 bool IsCopySrcPhys, IsCopyDstPhys;
1122 if (!isCopyToReg(*KillMI, CopySrcReg, CopyDstReg, IsCopySrcPhys,
1126 if (CopySrcReg !=
Reg || IsCopySrcPhys || !IsCopyDstPhys)
1134 bool SeenStore =
true;
1142 for (
const MachineOperand &MO : KillMI->
operands()) {
1149 if (isDefTooClose(MOReg, DI->second,
MI))
1151 bool isKill = isPlainlyKilled(MO);
1152 if (MOReg ==
Reg && !isKill)
1154 Uses.push_back(MOReg);
1155 if (isKill && MOReg !=
Reg)
1165 unsigned NumVisited = 0;
1166 for (MachineInstr &OtherMI :
1169 if (OtherMI.isDebugOrPseudoInstr())
1171 if (NumVisited > 10)
1174 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1175 OtherMI.isBranch() || OtherMI.isTerminator())
1179 for (
const MachineOperand &MO : OtherMI.operands()) {
1186 if (regOverlapsSet(Defs, MOReg))
1190 if (regOverlapsSet(Kills, MOReg))
1193 if (&OtherMI !=
MI && MOReg ==
Reg && !isPlainlyKilled(MO))
1202 if (regOverlapsSet(
Uses, MOReg))
1204 if (MOReg.
isPhysical() && regOverlapsSet(LiveDefs, MOReg))
1213 while (InsertPos !=
MBB->
begin() && std::prev(InsertPos)->isDebugInstr())
1217 while (std::prev(From)->isDebugInstr())
1221 nmi = std::prev(InsertPos);
1222 DistanceMap.
erase(DI);
1243bool TwoAddressInstructionImpl::tryInstructionCommute(MachineInstr *
MI,
1248 if (!
MI->isCommutable())
1251 bool MadeChange =
false;
1252 Register DstOpReg =
MI->getOperand(DstOpIdx).getReg();
1253 Register BaseOpReg =
MI->getOperand(BaseOpIdx).getReg();
1254 unsigned OpsNum =
MI->getDesc().getNumOperands();
1255 unsigned OtherOpIdx =
MI->getDesc().getNumDefs();
1256 for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1261 if (OtherOpIdx == BaseOpIdx || !
MI->getOperand(OtherOpIdx).isReg() ||
1262 !
TII->findCommutedOpIndices(*
MI, BaseOpIdx, OtherOpIdx))
1265 Register OtherOpReg =
MI->getOperand(OtherOpIdx).getReg();
1266 bool AggressiveCommute =
false;
1270 bool OtherOpKilled = isKilled(*
MI, OtherOpReg,
false);
1271 bool DoCommute = !BaseOpKilled && OtherOpKilled;
1274 isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg,
MI, Dist)) {
1276 AggressiveCommute =
true;
1280 if (DoCommute && commuteInstruction(
MI, DstOpIdx, BaseOpIdx, OtherOpIdx,
1284 if (AggressiveCommute)
1291 BaseOpReg = OtherOpReg;
1292 BaseOpKilled = OtherOpKilled;
1295 OpsNum =
MI->getDesc().getNumOperands();
1308bool TwoAddressInstructionImpl::tryInstructionTransform(
1310 unsigned SrcIdx,
unsigned DstIdx,
unsigned &Dist,
bool shouldOnlyCommute) {
1311 if (OptLevel == CodeGenOptLevel::None)
1314 MachineInstr &
MI = *mi;
1315 Register regA =
MI.getOperand(DstIdx).getReg();
1316 Register regB =
MI.getOperand(SrcIdx).getReg();
1318 assert(regB.
isVirtual() &&
"cannot make instruction into two-address form");
1319 bool regBKilled = isKilled(
MI, regB,
true);
1324 bool Commuted = tryInstructionCommute(&
MI, DstIdx, SrcIdx, regBKilled, Dist);
1337 if (Commuted && !ConvertibleTo3Addr)
1340 if (shouldOnlyCommute)
1345 if (!Commuted && Opts.twoaddr_reschedule &&
1346 rescheduleMIBelowKill(mi, nmi, regB)) {
1354 regB =
MI.getOperand(SrcIdx).getReg();
1355 regBKilled = isKilled(
MI, regB,
true);
1358 if (ConvertibleTo3Addr) {
1361 if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1363 if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1364 ++NumConvertedTo3Addr;
1376 if (Opts.twoaddr_reschedule && rescheduleKillAboveMI(mi, nmi, regB)) {
1389 if (
MI.mayLoad() && !regBKilled) {
1391 unsigned LoadRegIndex;
1393 TII->getOpcodeAfterMemoryUnfold(
MI.getOpcode(),
1398 const MCInstrDesc &UnfoldMCID =
TII->get(NewOpc);
1403 TII->getRegClass(UnfoldMCID, LoadRegIndex));
1405 SmallVector<MachineInstr *, 2> NewMIs;
1406 if (!
TII->unfoldMemoryOperand(*MF,
MI,
Reg,
1413 "Unfolded a load into multiple instructions!");
1415 NewMIs[1]->addRegisterKilled(
Reg,
TRI);
1421 DistanceMap.
insert(std::make_pair(NewMIs[0], Dist++));
1422 DistanceMap.
insert(std::make_pair(NewMIs[1], Dist));
1425 <<
"2addr: NEW INST: " << *NewMIs[1]);
1428 unsigned NewDstIdx =
1429 NewMIs[1]->findRegisterDefOperandIdx(regA,
nullptr);
1430 unsigned NewSrcIdx =
1431 NewMIs[1]->findRegisterUseOperandIdx(regB,
nullptr);
1433 bool TransformResult =
1434 tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist,
true);
1435 (void)TransformResult;
1436 assert(!TransformResult &&
1437 "tryInstructionTransform() should return false.");
1438 if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1443 for (
const MachineOperand &MO :
MI.operands()) {
1451 MI.eraseFromParent();
1475 NewMIs[0]->eraseFromParent();
1476 NewMIs[1]->eraseFromParent();
1477 DistanceMap.
erase(NewMIs[0]);
1478 DistanceMap.
erase(NewMIs[1]);
1491bool TwoAddressInstructionImpl::collectTiedOperands(
1492 MachineInstr *
MI, TiedOperandMap &TiedOperands) {
1493 bool AnyOps =
false;
1494 unsigned NumOps =
MI->getNumOperands();
1496 for (
unsigned SrcIdx = 0; SrcIdx <
NumOps; ++SrcIdx) {
1497 unsigned DstIdx = 0;
1498 if (!
MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1501 MachineOperand &SrcMO =
MI->getOperand(SrcIdx);
1502 MachineOperand &DstMO =
MI->getOperand(DstIdx);
1506 if (SrcReg == DstReg)
1509 assert(SrcReg && SrcMO.
isUse() &&
"two address instruction invalid");
1523 TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1530void TwoAddressInstructionImpl::processTiedPairs(MachineInstr *
MI,
1531 TiedPairList &TiedPairs,
1533 bool IsEarlyClobber =
llvm::any_of(TiedPairs, [
MI](
auto const &TP) {
1534 return MI->getOperand(TP.second).isEarlyClobber();
1537 bool RemovedKillFlag =
false;
1538 bool AllUsesCopied =
true;
1540 SlotIndex LastCopyIdx;
1542 unsigned SubRegB = 0;
1543 for (
auto &TP : TiedPairs) {
1544 unsigned SrcIdx = TP.first;
1545 unsigned DstIdx = TP.second;
1547 const MachineOperand &DstMO =
MI->getOperand(DstIdx);
1552 RegB =
MI->getOperand(SrcIdx).getReg();
1553 SubRegB =
MI->getOperand(SrcIdx).getSubReg();
1559 AllUsesCopied =
false;
1562 LastCopiedReg = RegA;
1564 assert(RegB.
isVirtual() &&
"cannot make instruction into two-address form");
1570 for (
unsigned i = 0; i !=
MI->getNumOperands(); ++i)
1572 !
MI->getOperand(i).isReg() ||
1573 MI->getOperand(i).getReg() != RegA);
1577 MachineInstrBuilder MIB =
BuildMI(*
MI->getParent(),
MI,
MI->getDebugLoc(),
1578 TII->get(TargetOpcode::COPY), RegA);
1581 MIB.
addReg(RegB, {}, SubRegB);
1587 "tied subregister must be a truncation");
1592 &&
"tied subregister must be a truncation");
1599 DistanceMap.
insert(std::make_pair(&*PrevMI, Dist));
1600 DistanceMap[
MI] = ++Dist;
1610 LI.
addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1613 S.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1616 for (MCRegUnit Unit :
TRI->regunits(RegA)) {
1620 LR->
addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1628 MachineOperand &MO =
MI->getOperand(SrcIdx);
1630 "inconsistent operand info for 2-reg pass");
1631 if (isPlainlyKilled(MO)) {
1633 RemovedKillFlag =
true;
1646 if (
MI->isBundle()) {
1650 "tied subregister uses in bundled instructions not supported");
1657 if (AllUsesCopied) {
1660 for (MachineOperand &MO :
MI->all_uses()) {
1661 if (MO.
getReg() == RegB) {
1662 if (MO.
getSubReg() == SubRegB && !IsEarlyClobber) {
1663 if (isPlainlyKilled(MO)) {
1665 RemovedKillFlag =
true;
1667 MO.
setReg(LastCopiedReg);
1670 RemainingUses |=
TRI->getSubRegIndexLaneMask(MO.
getSubReg());
1675 if (RemovedKillFlag && RemainingUses.
none())
1676 SrcRegMap[LastCopiedReg] = RegB;
1681 auto Shrink = [=](
LiveRange &LR, LaneBitmask LaneMask) {
1685 if ((LaneMask & RemainingUses).
any())
1689 S->
end = LastCopyIdx;
1694 bool ShrinkLI =
true;
1696 ShrinkLI &= Shrink(S, S.LaneMask);
1700 }
else if (RemovedKillFlag) {
1705 for (MachineOperand &MO :
MI->all_uses()) {
1706 if (MO.
getReg() == RegB) {
1721bool TwoAddressInstructionImpl::processStatepoint(
1722 MachineInstr *
MI, TiedOperandMap &TiedOperands) {
1724 bool NeedCopy =
false;
1725 for (
auto &TO : TiedOperands) {
1727 if (TO.second.size() != 1) {
1732 unsigned DstIdx = TO.second[0].second;
1734 MachineOperand &DstMO =
MI->getOperand(DstIdx);
1737 assert(RegB ==
MI->getOperand(TO.second[0].first).getReg());
1750 if (DefLI.overlaps(UseLI)) {
1752 <<
" UseLI overlaps with DefLI\n");
1760 <<
" to register class of " <<
printReg(RegA,
TRI, 0)
1772 for (
const VNInfo *VNI :
Other.valnos) {
1776 for (
auto &S :
Other) {
1777 VNInfo *VNI = NewVNIs[S.
valno->
id];
1778 LiveRange::Segment NewSeg(S.
start, S.
end, VNI);
1788bool TwoAddressInstructionImpl::run() {
1789 bool MadeChange =
false;
1791 LLVM_DEBUG(
dbgs() <<
"********** REWRITING TWO-ADDR INSTRS **********\n");
1800 TiedOperandMap TiedOperands;
1801 for (MachineBasicBlock &
MBBI : *MF) {
1804 DistanceMap.
clear();
1812 if (mi->isDebugInstr()) {
1819 if (mi->isRegSequence()) {
1820 eliminateRegSequence(mi);
1824 DistanceMap.
insert(std::make_pair(&*mi, ++Dist));
1830 if (!collectTiedOperands(&*mi, TiedOperands)) {
1831 removeClobberedSrcRegMap(&*mi);
1836 ++NumTwoAddressInstrs;
1843 if (TiedOperands.size() == 1) {
1844 SmallVectorImpl<std::pair<unsigned, unsigned>> &TiedPairs
1845 = TiedOperands.begin()->second;
1846 if (TiedPairs.
size() == 1) {
1847 unsigned SrcIdx = TiedPairs[0].first;
1848 unsigned DstIdx = TiedPairs[0].second;
1849 Register SrcReg = mi->getOperand(SrcIdx).getReg();
1850 Register DstReg = mi->getOperand(DstIdx).getReg();
1851 if (SrcReg != DstReg &&
1852 tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist,
false)) {
1855 TiedOperands.clear();
1856 removeClobberedSrcRegMap(&*mi);
1863 if (mi->getOpcode() == TargetOpcode::STATEPOINT &&
1864 processStatepoint(&*mi, TiedOperands)) {
1865 TiedOperands.clear();
1872 for (
auto &TO : TiedOperands) {
1873 processTiedPairs(&*mi, TO.second, Dist);
1878 if (mi->isInsertSubreg()) {
1881 unsigned SubIdx = mi->getOperand(3).getImm();
1883 LaneBitmask LaneMask =
TRI->getSubRegIndexLaneMask(SubIdx);
1886 bool UndefLanesAreLive =
false;
1896 if (mi->getOperand(1).isUndef()) {
1900 return (S.LaneMask & LaneMask).none() && S.liveAt(Idx);
1905 mi->removeOperand(3);
1906 assert(mi->getOperand(0).getSubReg() == 0 &&
"Unexpected subreg idx");
1907 mi->getOperand(0).setSubReg(SubIdx);
1908 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef() &&
1909 !UndefLanesAreLive);
1910 mi->removeOperand(1);
1911 mi->setDesc(
TII->get(TargetOpcode::COPY));
1914 if (UndefLanesAreLive) {
1915 MachineInstr *ImpDef =
1916 BuildMI(*mi->getParent(), mi, mi->getDebugLoc(),
1917 TII->get(TargetOpcode::IMPLICIT_DEF),
Reg);
1918 DistanceMap.
insert(std::make_pair(ImpDef, Dist));
1919 DistanceMap[&*mi] = ++Dist;
1930 if ((S.LaneMask & LaneMask).none()) {
1931 LiveRange::iterator DefSeg = S.FindSegmentContaining(Idx);
1932 if (mi->getOperand(0).isUndef()) {
1933 S.removeValNo(DefSeg->valno);
1935 LiveRange::iterator UseSeg = std::prev(DefSeg);
1936 S.MergeValueNumberInto(DefSeg->valno, UseSeg->valno);
1955 TiedOperands.clear();
1956 removeClobberedSrcRegMap(&*mi);
1974void TwoAddressInstructionImpl::eliminateRegSequence(
1976 MachineInstr &
MI = *
MBBI;
1980 VNInfo *DefVN =
nullptr;
1983 for (
unsigned i = 1, e =
MI.getNumOperands(); i < e; i += 2)
1996 unsigned SubReg =
Use.getSubReg();
1998 (!LIS ||
Use.getParent()->hasTiedAndOtherReadOf(DstReg, SubReg)))
1999 KeepLanes |=
TRI->getSubRegIndexLaneMask(SubReg);
2003 bool DefEmitted =
false;
2004 for (
unsigned i = 1, e =
MI.getNumOperands(); i < e; i += 2) {
2005 MachineOperand &UseMO =
MI.getOperand(i);
2007 unsigned SubIdx =
MI.getOperand(i+1).getImm();
2010 LaneBitmask LaneMask =
TRI->getSubRegIndexLaneMask(SubIdx);
2011 if ((KeepLanes & LaneMask).
none()) {
2012 UndefLanes |= LaneMask;
2019 bool isKill = UseMO.
isKill();
2021 for (
unsigned j = i + 2;
j <
e;
j += 2)
2022 if (
MI.getOperand(j).getReg() == SrcReg) {
2023 MI.getOperand(j).setIsKill();
2030 MachineInstr *CopyMI =
BuildMI(*
MI.getParent(),
MI,
MI.getDebugLoc(),
2031 TII->get(TargetOpcode::COPY))
2032 .
addReg(DstReg, RegState::Define, SubIdx)
2052 MI.setDesc(
TII->get(TargetOpcode::IMPLICIT_DEF));
2053 for (
int j =
MI.getNumOperands() - 1, ee = 0; j > ee; --j)
2054 MI.removeOperand(j);
2068 if (UseOp.
isUndef() || !SubReg)
2074 LaneBitmask LaneMask =
TRI->getSubRegIndexLaneMask(SubReg);
2075 if ((LaneMask & UndefLanes) == LaneMask)
2084 MI.eraseFromParent();
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator MBBI
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseMap class.
const HexagonInstrInfo * TII
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
Register const TargetRegisterInfo * TRI
Promote Memory to Register
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
MachineRegisterInfo & MRI
Remove Loads Into Fake Uses
SI Optimize VGPR LiveRange
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg)
Return true if the specified MI uses the specified register as a two-address use.
static bool getTiedUse(Register DefReg, MachineInstr *MI, const TargetRegisterInfo *TRI, unsigned &TiedOpIdx)
static MCRegister getMappedReg(Register Reg, DenseMap< Register, Register > &RegMap)
Return the physical register the specified virtual register might be mapped to.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Represents analyses that only rely on functions' control flow.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool hasOptNone() const
Do not optimize this function (-O0).
unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const override
Compute the instruction latency of a given instruction.
Itinerary data supplied by a subtarget to be used by a target.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
iterator_range< subrange_iterator > subranges()
LLVM_ABI void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
LLVM_ABI void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
void removeAllRegUnitsForPhysReg(MCRegister Reg)
Remove associated live ranges for the register units associated with Reg.
bool hasInterval(Register Reg) const
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
LLVM_ABI void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
VNInfo::Allocator & getVNInfoAllocator()
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
LiveInterval & getInterval(Register Reg)
void removeInterval(Register Reg)
Interval removal.
bool isNotInMIMap(const MachineInstr &Instr) const
Returns true if the specified machine instr has been removed or was never entered in the map.
LLVM_ABI bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr, LaneBitmask SubRangeMask=LaneBitmask::getAll())
After removing some uses of a register, shrink its live range to just the remaining uses.
LiveRange * getCachedRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
This class represents the liveness of a register, stack slot, etc.
LLVM_ABI 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.
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
bool hasAtLeastOneValue() const
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
LLVM_ABI iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Wrapper class representing physical registers. Should be passed by value.
An RAII based helper class to modify MachineFunctionProperties when running pass.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
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.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void makeDebugValueSubstitution(DebugInstrOperandPair, DebugInstrOperandPair, unsigned SubReg=0)
Create a substitution between one <instr,operand> value to a different, new value.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineFunctionProperties & getProperties() const
Get the function properties.
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & add(const MachineOperand &MO) const
Representation of each machine instruction.
mop_range defs()
Returns all explicit operands that are register definitions.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
bool isCopyLike() const
Return true if the instruction behaves like a copy.
bool isCall(QueryType Type=AnyInBundle) const
LLVM_ABI bool isSafeToMove(bool &SawStore) const
Return true if it is safe to move this instruction.
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
LLVM_ABI bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
LLVM_ABI unsigned getNumExplicitDefs() const
Returns the number of non-implicit definitions.
LLVM_ABI unsigned getDebugInstrNum()
Fetch the instruction number of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
LLVM_ABI unsigned getOperandNo() const
Returns the index of this operand in the instruction that it belongs to.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
void setIsUndef(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
iterator_range< reg_iterator > reg_operands(Register Reg) const
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
def_iterator def_begin(Register RegNo) const
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
bool hasOneUse(Register RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
defusechain_iterator< false, true, false, true, false > def_iterator
def_iterator/def_begin/def_end - Walk all defs of the specified register.
static def_iterator def_end()
LLVM_ABI const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
iterator_range< use_iterator > use_operands(Register Reg) const
LLVM_ABI void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
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.
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 push_back(const T &Elt)
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
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
BumpPtrAllocator Allocator
unsigned id
The ID number of this value.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
constexpr bool any(E Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< DefNode * > Def
NodeAddr< UseNode * > Use
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
CodeGenOptLevel
Code generation optimization level.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
LLVM_ABI char & TwoAddressInstructionPassID
TwoAddressInstruction - This pass reduces two-address instructions to use two operands.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
static constexpr LaneBitmask getAll()
constexpr bool none() const
constexpr bool any() const
static constexpr LaneBitmask getNone()
bool shouldSkipOptimizationForOptBisect(IRUnitRef IR)