+/// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
+/// Return true if live interval is removed.
+bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
+ MachineInstr *CopyMI) {
+ unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
+ LiveInterval::iterator MLR =
+ li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
+ if (MLR == li.end())
+ return false; // Already removed by ShortenDeadCopySrcLiveRange.
+ unsigned RemoveStart = MLR->start;
+ unsigned RemoveEnd = MLR->end;
+ // Remove the liverange that's defined by this.
+ if (RemoveEnd == li_->getDefIndex(CopyIdx)+1) {
+ removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
+ return removeIntervalIfEmpty(li, li_, tri_);
+ }
+ return false;
+}
+
+/// PropagateDeadness - Propagate the dead marker to the instruction which
+/// defines the val#.
+static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
+ unsigned &LRStart, LiveIntervals *li_,
+ const TargetRegisterInfo* tri_) {
+ MachineInstr *DefMI =
+ li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
+ if (DefMI && DefMI != CopyMI) {
+ int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false, tri_);
+ if (DeadIdx != -1) {
+ DefMI->getOperand(DeadIdx).setIsDead();
+ // A dead def should have a single cycle interval.
+ ++LRStart;
+ }
+ }
+}
+
+/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
+/// fallthoughs to SuccMBB.
+static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
+ MachineBasicBlock *SuccMBB,
+ const TargetInstrInfo *tii_) {
+ if (MBB == SuccMBB)
+ return true;
+ MachineBasicBlock *TBB = 0, *FBB = 0;
+ std::vector<MachineOperand> Cond;
+ return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
+ MBB->isSuccessor(SuccMBB);
+}
+
+/// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
+/// extended by a dead copy. Mark the last use (if any) of the val# as kill as
+/// ends the live range there. If there isn't another use, then this live range
+/// is dead. Return true if live interval is removed.
+bool
+SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
+ MachineInstr *CopyMI) {
+ unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
+ if (CopyIdx == 0) {
+ // FIXME: special case: function live in. It can be a general case if the
+ // first instruction index starts at > 0 value.
+ assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
+ // Live-in to the function but dead. Remove it from entry live-in set.
+ if (mf_->begin()->isLiveIn(li.reg))
+ mf_->begin()->removeLiveIn(li.reg);
+ const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
+ removeRange(li, LR->start, LR->end, li_, tri_);
+ return removeIntervalIfEmpty(li, li_, tri_);
+ }
+
+ LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1);
+ if (LR == li.end())
+ // Livein but defined by a phi.
+ return false;
+
+ unsigned RemoveStart = LR->start;
+ unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1;
+ if (LR->end > RemoveEnd)
+ // More uses past this copy? Nothing to do.
+ return false;
+
+ MachineBasicBlock *CopyMBB = CopyMI->getParent();
+ unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
+ unsigned LastUseIdx;
+ MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
+ LastUseIdx);
+ if (LastUse) {
+ MachineInstr *LastUseMI = LastUse->getParent();
+ if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
+ // r1024 = op
+ // ...
+ // BB1:
+ // = r1024
+ //
+ // BB2:
+ // r1025<dead> = r1024<kill>
+ if (MBBStart < LR->end)
+ removeRange(li, MBBStart, LR->end, li_, tri_);
+ return false;
+ }
+
+ // There are uses before the copy, just shorten the live range to the end
+ // of last use.
+ LastUse->setIsKill();
+ removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
+ unsigned SrcReg, DstReg;
+ if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg) &&
+ DstReg == li.reg) {
+ // Last use is itself an identity code.
+ int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
+ LastUseMI->getOperand(DeadIdx).setIsDead();
+ }
+ return false;
+ }
+
+ // Is it livein?
+ if (LR->start <= MBBStart && LR->end > MBBStart) {
+ if (LR->start == 0) {
+ assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
+ // Live-in to the function but dead. Remove it from entry live-in set.
+ mf_->begin()->removeLiveIn(li.reg);
+ }
+ // FIXME: Shorten intervals in BBs that reaches this BB.
+ }
+
+ if (LR->valno->def == RemoveStart)
+ // If the def MI defines the val#, propagate the dead marker.
+ PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
+
+ removeRange(li, RemoveStart, LR->end, li_, tri_);
+ return removeIntervalIfEmpty(li, li_, tri_);
+}
+
+/// CanCoalesceWithImpDef - Returns true if the specified copy instruction
+/// from an implicit def to another register can be coalesced away.
+bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI,
+ LiveInterval &li,
+ LiveInterval &ImpLi) const{
+ if (!CopyMI->killsRegister(ImpLi.reg))
+ return false;
+ unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
+ LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx);
+ if (LR == li.end())
+ return false;
+ if (LR->valno->hasPHIKill)
+ return false;
+ if (LR->valno->def != CopyIdx)
+ return false;
+ // Make sure all of val# uses are copies.
+ for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(li.reg),
+ UE = mri_->use_end(); UI != UE;) {
+ MachineInstr *UseMI = &*UI;
+ ++UI;
+ if (JoinedCopies.count(UseMI))
+ continue;
+ unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
+ LiveInterval::iterator ULR = li.FindLiveRangeContaining(UseIdx);
+ if (ULR == li.end() || ULR->valno != LR->valno)
+ continue;
+ // If the use is not a use, then it's not safe to coalesce the move.
+ unsigned SrcReg, DstReg;
+ if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) {
+ if (UseMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG &&
+ UseMI->getOperand(1).getReg() == li.reg)
+ continue;
+ return false;
+ }
+ }
+ return true;
+}
+
+
+/// RemoveCopiesFromValNo - The specified value# is defined by an implicit
+/// def and it is being removed. Turn all copies from this value# into
+/// identity copies so they will be removed.
+void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
+ VNInfo *VNI) {
+ SmallVector<MachineInstr*, 4> ImpDefs;
+ MachineOperand *LastUse = NULL;
+ unsigned LastUseIdx = li_->getUseIndex(VNI->def);
+ for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg),
+ RE = mri_->reg_end(); RI != RE;) {
+ MachineOperand *MO = &RI.getOperand();
+ MachineInstr *MI = &*RI;
+ ++RI;
+ if (MO->isDef()) {
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ ImpDefs.push_back(MI);
+ }
+ continue;
+ }
+ if (JoinedCopies.count(MI))
+ continue;
+ unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(MI));
+ LiveInterval::iterator ULR = li.FindLiveRangeContaining(UseIdx);
+ if (ULR == li.end() || ULR->valno != VNI)
+ continue;
+ // If the use is a copy, turn it into an identity copy.
+ unsigned SrcReg, DstReg;
+ if (tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == li.reg) {
+ // Each use MI may have multiple uses of this register. Change them all.
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (MO.isReg() && MO.getReg() == li.reg)
+ MO.setReg(DstReg);
+ }
+ JoinedCopies.insert(MI);
+ } else if (UseIdx > LastUseIdx) {
+ LastUseIdx = UseIdx;
+ LastUse = MO;
+ }
+ }
+ if (LastUse)
+ LastUse->setIsKill();
+ else {
+ // Remove dead implicit_def's.
+ while (!ImpDefs.empty()) {
+ MachineInstr *ImpDef = ImpDefs.back();
+ ImpDefs.pop_back();
+ li_->RemoveMachineInstrFromMaps(ImpDef);
+ ImpDef->eraseFromParent();
+ }
+ }
+}
+
+static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx,
+ const TargetRegisterClass *RC,
+ const TargetRegisterInfo* TRI) {
+ for (const unsigned *SRs = TRI->getSuperRegisters(Reg);
+ unsigned SR = *SRs; ++SRs)
+ if (Reg == TRI->getSubReg(SR, SubIdx) && RC->contains(SR))
+ return SR;
+ return 0;
+}
+
+/// isProfitableToCoalesceToSubRC - Given that register class of DstReg is
+/// a subset of the register class of SrcReg, return true if it's profitable
+/// to coalesce the two registers.
+bool
+SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg,
+ unsigned DstReg,
+ MachineBasicBlock *MBB){
+ if (!CrossClassJoin)
+ return false;
+
+ // First let's make sure all uses are in the same MBB.
+ for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(SrcReg),
+ RE = mri_->reg_end(); RI != RE; ++RI) {
+ MachineInstr &MI = *RI;
+ if (MI.getParent() != MBB)
+ return false;
+ }
+ for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(DstReg),
+ RE = mri_->reg_end(); RI != RE; ++RI) {
+ MachineInstr &MI = *RI;
+ if (MI.getParent() != MBB)
+ return false;
+ }
+
+ // Then make sure the intervals are *short*.
+ LiveInterval &SrcInt = li_->getInterval(SrcReg);
+ LiveInterval &DstInt = li_->getInterval(DstReg);
+ unsigned SrcSize = SrcInt.getSize() / InstrSlots::NUM;
+ unsigned DstSize = DstInt.getSize() / InstrSlots::NUM;
+ const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
+ unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
+ return (SrcSize + DstSize) <= Threshold;
+}
+
+