X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=f60b23a6c5077d84809551239b1c1ffd11b0ece0;hb=e6f350d7558f2db6c39c0a9fc8beafb796d9919a;hp=5cd6dd9da15b1386811058ec46f9e3d6dae68d3e;hpb=dbb8137c112130fabdebfa0fa6c8949707ff17f2;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 5cd6dd9da15..f60b23a6c50 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -25,6 +25,7 @@ #include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/SmallSet.h" @@ -35,10 +36,13 @@ using namespace llvm; STATISTIC(numJoins , "Number of interval joins performed"); +STATISTIC(numCrossRCs , "Number of cross class joins performed"); STATISTIC(numCommutes , "Number of instruction commuting performed"); STATISTIC(numExtends , "Number of copies extended"); +STATISTIC(NumReMats , "Number of instructions re-materialized"); STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); STATISTIC(numAborts , "Number of times interval joining aborted"); +STATISTIC(numDeadValNo, "Number of valno def marked dead"); char SimpleRegisterCoalescing::ID = 0; static cl::opt @@ -48,8 +52,13 @@ EnableJoining("join-liveintervals", static cl::opt NewHeuristic("new-coalescer-heuristic", - cl::desc("Use new coalescer heuristic"), - cl::init(false)); + cl::desc("Use new coalescer heuristic"), + cl::init(false), cl::Hidden); + +static cl::opt +CrossClassJoin("join-cross-class-copies", + cl::desc("Coalesce cross register class copies"), + cl::init(false), cl::Hidden); static RegisterPass X("simple-register-coalescing", "Simple Register Coalescing"); @@ -60,13 +69,16 @@ static RegisterAnalysisGroup V(X); const PassInfo *const llvm::SimpleRegisterCoalescingID = &X; void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); AU.addPreserved(); + AU.addRequired(); AU.addPreserved(); AU.addPreservedID(MachineDominatorsID); - AU.addPreservedID(PHIEliminationID); + if (StrongPHIElim) + AU.addPreservedID(StrongPHIEliminationID); + else + AU.addPreservedID(PHIEliminationID); AU.addPreservedID(TwoAddressInstructionPassID); - AU.addRequired(); - AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -93,8 +105,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // BValNo is a value number in B that is defined by a copy from A. 'B3' in // the example above. LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); - if (BLR == IntB.end()) // Should never happen! - return false; + assert(BLR != IntB.end() && "Live range not found!"); VNInfo *BValNo = BLR->valno; // Get the location that B is defined at. Two options: either this value has @@ -105,9 +116,28 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // AValNo is the value number in A that defines the copy, A3 in the example. LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); - if (ALR == IntA.end()) // Should never happen! - return false; + assert(ALR != IntA.end() && "Live range not found!"); VNInfo *AValNo = ALR->valno; + // If it's re-defined by an early clobber somewhere in the live range, then + // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. + // See PR3149: + // 172 %ECX = MOV32rr %reg1039 + // 180 INLINEASM , 10, %EAX, 14, %ECX, 9, %EAX, + // 36, , 1, %reg0, 0, 9, %ECX, 36, , 1, %reg0, 0 + // 188 %EAX = MOV32rr %EAX + // 196 %ECX = MOV32rr %ECX + // 204 %ECX = MOV32rr %ECX + // 212 %EAX = MOV32rr %EAX + // 220 %EAX = MOV32rr %EAX + // 228 %reg1039 = MOV32rr %ECX + // The early clobber operand ties ECX input to the ECX def. + // + // The live interval of ECX is represented as this: + // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) + // The coalescer has no idea there was a def in the middle of [174,230]. + if (AValNo->redefByEC) + return false; // If AValNo is defined as a copy from IntB, we can potentially process this. // Get the instruction that defines this value number. @@ -122,8 +152,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // Get the LiveRange in IntB that this value number starts with. LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1); - if (ValLR == IntB.end()) // Should never happen! - return false; + assert(ValLR != IntB.end() && "Live range not found!"); // Make sure that the end of the live range is inside the same block as // CopyMI. @@ -164,27 +193,30 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); // If the IntB live range is assigned to a physical register, and if that - // physreg has aliases, + // physreg has sub-registers, update their live intervals as well. if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { - // Update the liveintervals of sub-registers. - for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) { - LiveInterval &AliasLI = li_->getInterval(*AS); - AliasLI.addRange(LiveRange(FillerStart, FillerEnd, - AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator()))); + for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { + LiveInterval &SRLI = li_->getInterval(*SR); + SRLI.addRange(LiveRange(FillerStart, FillerEnd, + SRLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator()))); } } // Okay, merge "B1" into the same value number as "B0". - if (BValNo != ValLR->valno) + if (BValNo != ValLR->valno) { + IntB.addKills(ValLR->valno, BValNo->kills); IntB.MergeValueNumberInto(BValNo, ValLR->valno); + } DOUT << " result = "; IntB.print(DOUT, tri_); DOUT << "\n"; // If the source instruction was killing the source register before the // merge, unset the isKill marker given the live range has been extended. int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); - if (UIdx != -1) + if (UIdx != -1) { ValLREndInst->getOperand(UIdx).setIsKill(false); + IntB.removeKill(ValLR->valno, FillerStart); + } ++numExtends; return true; @@ -253,8 +285,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, // BValNo is a value number in B that is defined by a copy from A. 'B3' in // the example above. LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); - if (BLR == IntB.end()) // Should never happen! - return false; + assert(BLR != IntB.end() && "Live range not found!"); VNInfo *BValNo = BLR->valno; // Get the location that B is defined at. Two options: either this value has @@ -265,8 +296,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, // AValNo is the value number in A that defines the copy, A3 in the example. LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); - if (ALR == IntA.end()) // Should never happen! - return false; + assert(ALR != IntA.end() && "Live range not found!"); VNInfo *AValNo = ALR->valno; // If other defs can reach uses of this def, then it's not safe to perform // the optimization. @@ -336,6 +366,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, BExtend[ALR->end] = BLR->end; // Update uses of IntA of the specific Val# with IntB. + bool BHasSubRegs = false; + if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) + BHasSubRegs = *tri_->getSubRegisters(IntB.reg); for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), UE = mri_->use_end(); UI != UE;) { MachineOperand &UseMO = UI.getOperand(); @@ -356,8 +389,8 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, else BKills.push_back(li_->getUseIndex(UseIdx)+1); } - unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) continue; if (DstReg == IntB.reg) { // This copy will become a noop. If it's defining a new val#, @@ -381,10 +414,30 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, // simply extend BLR if CopyMI doesn't end the range. DOUT << "\nExtending: "; IntB.print(DOUT, tri_); - IntB.removeValNo(BValNo); - for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) + // Remove val#'s defined by copies that will be coalesced away. + for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) { + VNInfo *DeadVNI = BDeadValNos[i]; + if (BHasSubRegs) { + for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { + LiveInterval &SRLI = li_->getInterval(*SR); + const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def); + SRLI.removeValNo(SRLR->valno); + } + } IntB.removeValNo(BDeadValNos[i]); - VNInfo *ValNo = IntB.getNextValue(AValNo->def, 0, li_->getVNInfoAllocator()); + } + + // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition + // is updated. Kills are also updated. + VNInfo *ValNo = BValNo; + ValNo->def = AValNo->def; + ValNo->copy = NULL; + for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) { + unsigned Kill = ValNo->kills[j]; + if (Kill != BLR->end) + BKills.push_back(Kill); + } + ValNo->kills.clear(); for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); AI != AE; ++AI) { if (AI->valno != AValNo) continue; @@ -393,6 +446,15 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, if (EI != BExtend.end()) End = EI->second; IntB.addRange(LiveRange(AI->start, End, ValNo)); + + // If the IntB live range is assigned to a physical register, and if that + // physreg has sub-registers, update their live intervals as well. + if (BHasSubRegs) { + for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { + LiveInterval &SRLI = li_->getInterval(*SR); + SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator()); + } + } } IntB.addKills(ValNo, BKills); ValNo->hasPHIKill = BHasPHIKill; @@ -409,6 +471,169 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, return true; } +/// 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; + SmallVector Cond; + return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB && + MBB->isSuccessor(SuccMBB); +} + +/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range +/// from a physical register live interval as well as from the live intervals +/// of its sub-registers. +static void removeRange(LiveInterval &li, unsigned Start, unsigned End, + LiveIntervals *li_, const TargetRegisterInfo *tri_) { + li.removeRange(Start, End, true); + if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { + for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { + if (!li_->hasInterval(*SR)) + continue; + LiveInterval &sli = li_->getInterval(*SR); + unsigned RemoveEnd = Start; + while (RemoveEnd != End) { + LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start); + if (LR == sli.end()) + break; + RemoveEnd = (LR->end < End) ? LR->end : End; + sli.removeRange(Start, RemoveEnd, true); + Start = RemoveEnd; + } + } + } +} + +/// TrimLiveIntervalToLastUse - If there is a last use in the same basic block +/// as the copy instruction, trim the live interval to the last use and return +/// true. +bool +SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx, + MachineBasicBlock *CopyMBB, + LiveInterval &li, + const LiveRange *LR) { + 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 = r1024 + if (MBBStart < LR->end) + removeRange(li, MBBStart, LR->end, li_, tri_); + return true; + } + + // 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_); + li.addKill(LR->valno, LastUseIdx+1); + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + DstReg == li.reg) { + // Last use is itself an identity code. + int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_); + LastUseMI->getOperand(DeadIdx).setIsDead(); + } + return true; + } + + // 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. + } + + return false; +} + +/// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial +/// computation, replace the copy by rematerialize the definition. +bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, + unsigned DstReg, + MachineInstr *CopyMI) { + unsigned CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI)); + LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); + assert(SrcLR != SrcInt.end() && "Live range not found!"); + VNInfo *ValNo = SrcLR->valno; + // If other defs can reach uses of this def, then it's not safe to perform + // the optimization. + if (ValNo->def == ~0U || ValNo->def == ~1U || ValNo->hasPHIKill) + return false; + MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def); + const TargetInstrDesc &TID = DefMI->getDesc(); + if (!TID.isAsCheapAsAMove()) + return false; + if (!DefMI->getDesc().isRematerializable() || + !tii_->isTriviallyReMaterializable(DefMI)) + return false; + bool SawStore = false; + if (!DefMI->isSafeToMove(tii_, SawStore)) + return false; + + unsigned DefIdx = li_->getDefIndex(CopyIdx); + const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx); + DLR->valno->copy = NULL; + // Don't forget to update sub-register intervals. + if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { + for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) { + if (!li_->hasInterval(*SR)) + continue; + DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx); + if (DLR && DLR->valno->copy == CopyMI) + DLR->valno->copy = NULL; + } + } + + // If copy kills the source register, find the last use and propagate + // kill. + MachineBasicBlock *MBB = CopyMI->getParent(); + if (CopyMI->killsRegister(SrcInt.reg)) + TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR); + + MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI)); + CopyMI->removeFromParent(); + tii_->reMaterialize(*MBB, MII, DstReg, DefMI); + MachineInstr *NewMI = prior(MII); + // CopyMI may have implicit operands, transfer them over to the newly + // rematerialized instruction. And update implicit def interval valnos. + for (unsigned i = CopyMI->getDesc().getNumOperands(), + e = CopyMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = CopyMI->getOperand(i); + if (MO.isReg() && MO.isImplicit()) + NewMI->addOperand(MO); + if (MO.isDef() && li_->hasInterval(MO.getReg())) { + unsigned Reg = MO.getReg(); + DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx); + if (DLR && DLR->valno->copy == CopyMI) + DLR->valno->copy = NULL; + } + } + + li_->ReplaceMachineInstrInMaps(CopyMI, NewMI); + MBB->getParent()->DeleteMachineInstr(CopyMI); + ReMatCopies.insert(CopyMI); + ReMatDefs.insert(DefMI); + ++NumReMats; + return true; +} + /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. /// bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, @@ -426,7 +651,7 @@ bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx)); if (DstLR == LI.end()) return false; - unsigned KillIdx = li_->getInstructionIndex(&MBB->back()) + InstrSlots::NUM; + unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1; if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill) return true; @@ -458,22 +683,52 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned UseDstReg = DstReg; if (OldSubIdx) UseDstReg = tri_->getSubReg(DstReg, OldSubIdx); + + unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; + if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, + CopySrcSubIdx, CopyDstSubIdx) && + CopySrcReg != CopyDstReg && + CopySrcReg == SrcReg && CopyDstReg != UseDstReg) { + // If the use is a copy and it won't be coalesced away, and its source + // is defined by a trivial computation, try to rematerialize it instead. + if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg,UseMI)) + continue; + } + O.setReg(UseDstReg); O.setSubReg(0); - } else { - // Sub-register indexes goes from small to large. e.g. - // RAX: 1 -> AL, 2 -> AX, 3 -> EAX - // EAX: 1 -> AL, 2 -> AX - // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose - // sub-register 2 is also AX. - if (SubIdx && OldSubIdx && SubIdx != OldSubIdx) - assert(OldSubIdx < SubIdx && "Conflicting sub-register index!"); - else if (SubIdx) - O.setSubReg(SubIdx); - // Remove would-be duplicated kill marker. - if (O.isKill() && UseMI->killsRegister(DstReg)) - O.setIsKill(false); - O.setReg(DstReg); + continue; + } + + // Sub-register indexes goes from small to large. e.g. + // RAX: 1 -> AL, 2 -> AX, 3 -> EAX + // EAX: 1 -> AL, 2 -> AX + // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose + // sub-register 2 is also AX. + if (SubIdx && OldSubIdx && SubIdx != OldSubIdx) + assert(OldSubIdx < SubIdx && "Conflicting sub-register index!"); + else if (SubIdx) + O.setSubReg(SubIdx); + // Remove would-be duplicated kill marker. + if (O.isKill() && UseMI->killsRegister(DstReg)) + O.setIsKill(false); + O.setReg(DstReg); + + // After updating the operand, check if the machine instruction has + // become a copy. If so, update its val# information. + const TargetInstrDesc &TID = UseMI->getDesc(); + unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; + if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 && + tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, + CopySrcSubIdx, CopyDstSubIdx) && + CopySrcReg != CopyDstReg && + (TargetRegisterInfo::isVirtualRegister(CopyDstReg) || + allocatableRegs_[CopyDstReg])) { + LiveInterval &LI = li_->getInterval(CopyDstReg); + unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI)); + const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx); + if (DLR->valno->def == DefIdx) + DLR->valno->copy = UseMI; } } } @@ -516,43 +771,16 @@ void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, MachineOperand &UseMO = UI.getOperand(); if (UseMO.isKill()) { MachineInstr *UseMI = UseMO.getParent(); - unsigned SReg, DReg; - if (!tii_->isMoveInstr(*UseMI, SReg, DReg)) - continue; unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI)); if (JoinedCopies.count(UseMI)) continue; const LiveRange *UI = LI.getLiveRangeContaining(UseIdx); - if (!LI.isKill(UI->valno, UseIdx+1)) + if (!UI || !LI.isKill(UI->valno, UseIdx+1)) UseMO.setIsKill(false); } } } -/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range -/// from a physical register live interval as well as from the live intervals -/// of its sub-registers. -static void removeRange(LiveInterval &li, unsigned Start, unsigned End, - LiveIntervals *li_, const TargetRegisterInfo *tri_) { - li.removeRange(Start, End, true); - if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { - for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { - if (!li_->hasInterval(*SR)) - continue; - LiveInterval &sli = li_->getInterval(*SR); - unsigned RemoveEnd = Start; - while (RemoveEnd != End) { - LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start); - if (LR == sli.end()) - break; - RemoveEnd = (LR->end < End) ? LR->end : End; - sli.removeRange(Start, RemoveEnd, true); - Start = RemoveEnd; - } - } - } -} - /// removeIntervalIfEmpty - Check if the live interval of a physical register /// is empty, if so remove it and also remove the empty intervals of its /// sub-registers. Return true if live interval is removed. @@ -592,6 +820,18 @@ bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li, return false; } +/// RemoveDeadDef - If a def of a live interval is now determined dead, remove +/// the val# it defines. If the live interval becomes empty, remove it as well. +bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li, + MachineInstr *DefMI) { + unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI)); + LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); + if (DefIdx != MLR->valno->def) + return false; + li.removeValNo(MLR->valno); + return removeIntervalIfEmpty(li, li_, tri_); +} + /// PropagateDeadness - Propagate the dead marker to the instruction which /// defines the val#. static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, @@ -609,19 +849,6 @@ static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, } } -/// 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 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 @@ -653,55 +880,31 @@ SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li, // More uses past this copy? Nothing to do. return false; + // If there is a last use in the same bb, we can't remove the live range. + // Shorten the live interval and return. 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 = r1024 - 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(); - } + if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR)) 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); + MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart); + if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_)) + // If the live range starts in another mbb and the copy mbb is not a fall + // through mbb, then we can only cut the range from the beginning of the + // copy mbb. + RemoveStart = li_->getMBBStartIdx(CopyMBB) + 1; + + if (LR->valno->def == RemoveStart) { + // If the def MI defines the val# and this copy is the only kill of the + // val#, then propagate the dead marker. + if (li.isOnlyLROfValNo(LR)) { + PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); + ++numDeadValNo; } - // FIXME: Shorten intervals in BBs that reaches this BB. + if (li.isKill(LR->valno, RemoveEnd)) + li.removeKill(LR->valno, RemoveEnd); } - 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_); + removeRange(li, RemoveStart, RemoveEnd, li_, tri_); return removeIntervalIfEmpty(li, li_, tri_); } @@ -732,8 +935,8 @@ bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI, 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)) { + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { if (UseMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG && UseMI->getOperand(1).getReg() == li.reg) continue; @@ -770,8 +973,9 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li, 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) { + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + 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); @@ -784,9 +988,10 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li, LastUse = MO; } } - if (LastUse) + if (LastUse) { LastUse->setIsKill(); - else { + li.addKill(VNI, LastUseIdx+1); + } else { // Remove dead implicit_def's. while (!ImpDefs.empty()) { MachineInstr *ImpDef = ImpDefs.back(); @@ -797,6 +1002,8 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li, } } +/// getMatchingSuperReg - Return a super-register of the specified register +/// Reg so its sub-register of index SubIdx is Reg. static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, const TargetRegisterClass *RC, const TargetRegisterInfo* TRI) { @@ -807,6 +1014,139 @@ static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, return 0; } +/// isWinToJoinCrossClass - Return true if it's profitable to coalesce +/// two virtual registers from different register classes. +bool +SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg, + unsigned SmallReg, + unsigned Threshold) { + // Then make sure the intervals are *short*. + LiveInterval &LargeInt = li_->getInterval(LargeReg); + LiveInterval &SmallInt = li_->getInterval(SmallReg); + unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt); + unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt); + if (SmallSize > Threshold || LargeSize > Threshold) + if ((float)std::distance(mri_->use_begin(SmallReg), + mri_->use_end()) / SmallSize < + (float)std::distance(mri_->use_begin(LargeReg), + mri_->use_end()) / LargeSize) + return false; + return true; +} + +/// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual +/// register with a physical register, check if any of the virtual register +/// operand is a sub-register use or def. If so, make sure it won't result +/// in an illegal extract_subreg or insert_subreg instruction. e.g. +/// vr1024 = extract_subreg vr1025, 1 +/// ... +/// vr1024 = mov8rr AH +/// If vr1024 is coalesced with AH, the extract_subreg is now illegal since +/// AH does not have a super-reg whose sub-register 1 is AH. +bool +SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, + unsigned VirtReg, + unsigned PhysReg) { + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg), + E = mri_->reg_end(); I != E; ++I) { + MachineOperand &O = I.getOperand(); + MachineInstr *MI = &*I; + if (MI == CopyMI || JoinedCopies.count(MI)) + continue; + unsigned SubIdx = O.getSubReg(); + if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx)) + return true; + if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { + SubIdx = MI->getOperand(2).getImm(); + if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx)) + return true; + if (O.isDef()) { + unsigned SrcReg = MI->getOperand(1).getReg(); + const TargetRegisterClass *RC = + TargetRegisterInfo::isPhysicalRegister(SrcReg) + ? tri_->getPhysicalRegisterRegClass(SrcReg) + : mri_->getRegClass(SrcReg); + if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_)) + return true; + } + } + if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { + SubIdx = MI->getOperand(3).getImm(); + if (VirtReg == MI->getOperand(0).getReg()) { + if (!tri_->getSubReg(PhysReg, SubIdx)) + return true; + } else { + unsigned DstReg = MI->getOperand(0).getReg(); + const TargetRegisterClass *RC = + TargetRegisterInfo::isPhysicalRegister(DstReg) + ? tri_->getPhysicalRegisterRegClass(DstReg) + : mri_->getRegClass(DstReg); + if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_)) + return true; + } + } + } + return false; +} + + +/// CanJoinExtractSubRegToPhysReg - Return true if it's possible to coalesce +/// an extract_subreg where dst is a physical register, e.g. +/// cl = EXTRACT_SUBREG reg1024, 1 +bool +SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg, + unsigned SrcReg, unsigned SubIdx, + unsigned &RealDstReg) { + const TargetRegisterClass *RC = mri_->getRegClass(SrcReg); + RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_); + assert(RealDstReg && "Invalid extract_subreg instruction!"); + + // For this type of EXTRACT_SUBREG, conservatively + // check if the live interval of the source register interfere with the + // actual super physical register we are trying to coalesce with. + LiveInterval &RHS = li_->getInterval(SrcReg); + if (li_->hasInterval(RealDstReg) && + RHS.overlaps(li_->getInterval(RealDstReg))) { + DOUT << "Interfere with register "; + DEBUG(li_->getInterval(RealDstReg).print(DOUT, tri_)); + return false; // Not coalescable + } + for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR) + if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { + DOUT << "Interfere with sub-register "; + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + return false; // Not coalescable + } + return true; +} + +/// CanJoinInsertSubRegToPhysReg - Return true if it's possible to coalesce +/// an insert_subreg where src is a physical register, e.g. +/// reg1024 = INSERT_SUBREG reg1024, c1, 0 +bool +SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg, + unsigned SrcReg, unsigned SubIdx, + unsigned &RealSrcReg) { + const TargetRegisterClass *RC = mri_->getRegClass(DstReg); + RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_); + assert(RealSrcReg && "Invalid extract_subreg instruction!"); + + LiveInterval &RHS = li_->getInterval(DstReg); + if (li_->hasInterval(RealSrcReg) && + RHS.overlaps(li_->getInterval(RealSrcReg))) { + DOUT << "Interfere with register "; + DEBUG(li_->getInterval(RealSrcReg).print(DOUT, tri_)); + return false; // Not coalescable + } + for (const unsigned* SR = tri_->getSubRegisters(RealSrcReg); *SR; ++SR) + if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { + DOUT << "Interfere with sub-register "; + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + return false; // Not coalescable + } + return true; +} + /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, /// which are the src/dst of the copy instruction CopyMI. This returns true /// if the copy was successfully coalesced away. If it is not currently @@ -816,13 +1156,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { MachineInstr *CopyMI = TheCopy.MI; Again = false; - if (JoinedCopies.count(CopyMI)) + if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) return false; // Already done. DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI; - unsigned SrcReg; - unsigned DstReg; + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG; unsigned SubIdx = 0; @@ -837,7 +1176,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } DstReg = CopyMI->getOperand(0).getReg(); SrcReg = CopyMI->getOperand(2).getReg(); - } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) { + } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){ assert(0 && "Unrecognized copy instruction!"); return false; } @@ -867,6 +1206,10 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { return false; // Not coalescable. } + // Should be non-null only when coalescing to a sub-register class. + bool CrossRC = false; + const TargetRegisterClass *NewRC = NULL; + MachineBasicBlock *CopyMBB = CopyMI->getParent(); unsigned RealDstReg = 0; unsigned RealSrcReg = 0; if (isExtSubReg || isInsSubReg) { @@ -899,43 +1242,19 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { DstReg = tri_->getSubReg(DstReg, SubIdx); SubIdx = 0; } else if ((DstIsPhys && isExtSubReg) || (SrcIsPhys && isInsSubReg)) { - // If this is a extract_subreg where dst is a physical register, e.g. - // cl = EXTRACT_SUBREG reg1024, 1 - // then create and update the actual physical register allocated to RHS. - // Ditto for - // reg1024 = INSERT_SUBREG r1024, cl, 1 if (CopyMI->getOperand(1).getSubReg()) { - DOUT << "\tSrc of extract_ / insert_subreg already coalesced with reg" + DOUT << "\tSrc of extract_subreg already coalesced with reg" << " of a super-class.\n"; return false; // Not coalescable. } - const TargetRegisterClass *RC = - mri_->getRegClass(isExtSubReg ? SrcReg : DstReg); + if (isExtSubReg) { - RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_); - assert(RealDstReg && "Invalid extra_subreg instruction!"); + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg)) + return false; // Not coalescable } else { - RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_); - assert(RealSrcReg && "Invalid extra_subreg instruction!"); - } - - // For this type of EXTRACT_SUBREG, conservatively - // check if the live interval of the source register interfere with the - // actual super physical register we are trying to coalesce with. - unsigned PhysReg = isExtSubReg ? RealDstReg : RealSrcReg; - LiveInterval &RHS = li_->getInterval(isExtSubReg ? SrcReg : DstReg); - if (li_->hasInterval(PhysReg) && - RHS.overlaps(li_->getInterval(PhysReg))) { - DOUT << "Interfere with register "; - DEBUG(li_->getInterval(PhysReg).print(DOUT, tri_)); - return false; // Not coalescable - } - for (const unsigned* SR = tri_->getSubRegisters(PhysReg); *SR; ++SR) - if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { - DOUT << "Interfere with sub-register "; - DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) return false; // Not coalescable - } + } SubIdx = 0; } else { unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg() @@ -955,43 +1274,105 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (SubIdx) { unsigned LargeReg = isExtSubReg ? SrcReg : DstReg; unsigned SmallReg = isExtSubReg ? DstReg : SrcReg; - unsigned LargeRegSize = - li_->getInterval(LargeReg).getSize() / InstrSlots::NUM; - unsigned SmallRegSize = - li_->getInterval(SmallReg).getSize() / InstrSlots::NUM; - const TargetRegisterClass *RC = mri_->getRegClass(SmallReg); - unsigned Threshold = allocatableRCRegs_[RC].count(); - // Be conservative. If both sides are virtual registers, do not coalesce - // if this will cause a high use density interval to target a smaller - // set of registers. - if (SmallRegSize > Threshold || LargeRegSize > Threshold) { - if ((float)std::distance(mri_->use_begin(SmallReg), - mri_->use_end()) / SmallRegSize < - (float)std::distance(mri_->use_begin(LargeReg), - mri_->use_end()) / LargeRegSize) { - Again = true; // May be possible to coalesce later. - return false; - } + unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count(); + if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { + Again = true; // May be possible to coalesce later. + return false; } } } } else if (differingRegisterClasses(SrcReg, DstReg)) { - // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced + if (!CrossClassJoin) + return false; + CrossRC = true; + + // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced // with another? If it's the resulting destination register, then // the subidx must be propagated to uses (but only those defined // by the EXTRACT_SUBREG). If it's being coalesced into another // register, it should be safe because register is assumed to have // the register class of the super-register. - // If they are not of the same register class, we cannot join them. - DOUT << "\tSrc/Dest are different register classes.\n"; - // Allow the coalescer to try again in case either side gets coalesced to - // a physical register that's compatible with the other side. e.g. - // r1024 = MOV32to32_ r1025 - // but later r1024 is assigned EAX then r1025 may be coalesced with EAX. - Again = true; // May be possible to coalesce later. - return false; + // Process moves where one of the registers have a sub-register index. + MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg); + if (DstMO->getSubReg()) + // FIXME: Can we handle this? + return false; + MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg); + SubIdx = SrcMO->getSubReg(); + if (SubIdx) { + // This is not a extract_subreg but it looks like one. + // e.g. %cl = MOV16rr %reg1024:2 + isExtSubReg = true; + if (DstIsPhys) { + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg)) + return false; // Not coalescable + SubIdx = 0; + } + } + + const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg); + const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg); + unsigned LargeReg = SrcReg; + unsigned SmallReg = DstReg; + unsigned Limit = 0; + + // Now determine the register class of the joined register. + if (isExtSubReg) { + if (SubIdx && DstRC && DstRC->isASubClass()) { + // This is a move to a sub-register class. However, the source is a + // sub-register of a larger register class. We don't know what should + // the register class be. FIXME. + Again = true; + return false; + } + Limit = allocatableRCRegs_[DstRC].count(); + } else if (!SrcIsPhys && !SrcIsPhys) { + unsigned SrcSize = SrcRC->getSize(); + unsigned DstSize = DstRC->getSize(); + if (SrcSize < DstSize) + // For example X86::MOVSD2PDrr copies from FR64 to VR128. + NewRC = DstRC; + else if (DstSize > SrcSize) { + NewRC = SrcRC; + std::swap(LargeReg, SmallReg); + } else { + unsigned SrcNumRegs = SrcRC->getNumRegs(); + unsigned DstNumRegs = DstRC->getNumRegs(); + if (DstNumRegs < SrcNumRegs) + // Sub-register class? + NewRC = DstRC; + else if (SrcNumRegs < DstNumRegs) { + NewRC = SrcRC; + std::swap(LargeReg, SmallReg); + } else + // No idea what's the right register class to use. + return false; + } + } + + // If we are joining two virtual registers and the resulting register + // class is more restrictive (fewer register, smaller size). Check if it's + // worth doing the merge. + if (!SrcIsPhys && !DstIsPhys && + (isExtSubReg || DstRC->isASubClass()) && + !isWinToJoinCrossClass(LargeReg, SmallReg, + allocatableRCRegs_[NewRC].count())) { + DOUT << "\tSrc/Dest are different register classes.\n"; + // Allow the coalescer to try again in case either side gets coalesced to + // a physical register that's compatible with the other side. e.g. + // r1024 = MOV32to32_ r1025 + // But later r1024 is assigned EAX then r1025 may be coalesced with EAX. + Again = true; // May be possible to coalesce later. + return false; + } } + + // Will it create illegal extract_subreg / insert_subreg? + if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg)) + return false; + if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg)) + return false; LiveInterval &SrcInt = li_->getInterval(SrcReg); LiveInterval &DstInt = li_->getInterval(DstReg); @@ -1002,6 +1383,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { DOUT << " and "; DstInt.print(DOUT, tri_); DOUT << ": "; + // Save a copy of the virtual register live interval. We'll manually + // merge this into the "real" physical register live interval this is + // coalesced with. + LiveInterval *SavedLI = 0; + if (RealDstReg) + SavedLI = li_->dupInterval(&SrcInt); + else if (RealSrcReg) + SavedLI = li_->dupInterval(&DstInt); + // Check if it is necessary to propagate "isDead" property. if (!isExtSubReg && !isInsSubReg) { MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false); @@ -1023,10 +1413,10 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // If the virtual register live interval is long but it has low use desity, // do not join them, instead mark the physical register as its allocation // preference. - unsigned Length = JoinVInt.getSize() / InstrSlots::NUM; + unsigned Length = li_->getApproximateInstructionCount(JoinVInt); if (Length > Threshold && - (((float)std::distance(mri_->use_begin(JoinVReg), - mri_->use_end()) / Length) < (1.0 / Threshold))) { + (((float)std::distance(mri_->use_begin(JoinVReg), mri_->use_end()) + / Length) < (1.0 / Threshold))) { JoinVInt.preference = JoinPReg; ++numAborts; DOUT << "\tMay tie down a physical register, abort!\n"; @@ -1053,6 +1443,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) { // Coalescing failed. + + // If definition of source is defined by trivial computation, try + // rematerializing it. + if (!isExtSubReg && !isInsSubReg && + ReMaterializeTrivialDef(SrcInt, DstInt.reg, CopyMI)) + return true; // If we can eliminate the copy without merging the live ranges, do so now. if (!isExtSubReg && !isInsSubReg && @@ -1077,7 +1473,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && "LiveInterval::join didn't work right!"); - // If we're about to merge live ranges into a physical register live range, + // If we're about to merge live ranges into a physical register live interval, // we have to update any aliased register's live ranges to indicate that they // have clobbered values for this range. if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { @@ -1087,21 +1483,17 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (RealDstReg || RealSrcReg) { LiveInterval &RealInt = li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg); - SmallSet CopiedValNos; - for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(), - E = ResSrcInt->ranges.end(); I != E; ++I) { - const LiveRange *DstLR = ResDstInt->getLiveRangeContaining(I->start); - assert(DstLR && "Invalid joined interval!"); - const VNInfo *DstValNo = DstLR->valno; - if (CopiedValNos.insert(DstValNo)) { - VNInfo *ValNo = RealInt.getNextValue(DstValNo->def, DstValNo->copy, - li_->getVNInfoAllocator()); - ValNo->hasPHIKill = DstValNo->hasPHIKill; - RealInt.addKills(ValNo, DstValNo->kills); - RealInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo); - } + for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(), + E = SavedLI->vni_end(); I != E; ++I) { + const VNInfo *ValNo = *I; + VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->copy, + li_->getVNInfoAllocator()); + NewValNo->hasPHIKill = ValNo->hasPHIKill; + NewValNo->redefByEC = ValNo->redefByEC; + RealInt.addKills(NewValNo, ValNo->kills); + RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo); } - + RealInt.weight += SavedLI->weight; DstReg = RealDstReg ? RealDstReg : RealSrcReg; } @@ -1121,6 +1513,14 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } } + // Coalescing to a virtual register that is of a sub-register class of the + // other. Make sure the resulting register is set to the right register class. + if (CrossRC) { + ++numCrossRCs; + if (NewRC) + mri_->setRegClass(DstReg, NewRC); + } + if (NewHeuristic) { // Add all copies that define val# in the source interval into the queue. for (LiveInterval::const_vni_iterator i = ResSrcInt->vni_begin(), @@ -1129,11 +1529,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (!vni->def || vni->def == ~1U || vni->def == ~0U) continue; MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); - unsigned NewSrcReg, NewDstReg; + unsigned NewSrcReg, NewDstReg, NewSrcSubIdx, NewDstSubIdx; if (CopyMI && JoinedCopies.count(CopyMI) == 0 && - tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg)) { - unsigned LoopDepth = loopInfo->getLoopDepth(CopyMI->getParent()); + tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg, + NewSrcSubIdx, NewDstSubIdx)) { + unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB); JoinQueue->push(CopyRec(CopyMI, LoopDepth, isBackEdgeCopy(CopyMI, DstReg))); } @@ -1149,9 +1550,6 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (TargetRegisterInfo::isVirtualRegister(DstReg)) RemoveUnnecessaryKills(DstReg, *ResDstInt); - // SrcReg is guarateed to be the register whose live interval that is - // being merged. - li_->removeInterval(SrcReg); if (isInsSubReg) // Avoid: // r1024 = op @@ -1161,6 +1559,16 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { RemoveDeadImpDef(DstReg, *ResDstInt); UpdateRegDefsUses(SrcReg, DstReg, SubIdx); + // SrcReg is guarateed to be the register whose live interval that is + // being merged. + li_->removeInterval(SrcReg); + + // Manually deleted the live interval copy. + if (SavedLI) { + SavedLI->clear(); + delete SavedLI; + } + if (isEmpty) { // Now the copy is being coalesced away, the val# previously defined // by the copy is being defined by an IMPLICIT_DEF which defines a zero @@ -1184,6 +1592,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } } + // If resulting interval has a preference that no longer fits because of subreg + // coalescing, just clear the preference. + if (ResDstInt->preference && (isExtSubReg || isInsSubReg) && + TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) { + const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg); + if (!RC->contains(ResDstInt->preference)) + ResDstInt->preference = 0; + } + DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, tri_); DOUT << "\n"; @@ -1261,8 +1678,9 @@ bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li, // It's a sub-register live interval, we may not have precise information. // Re-compute it. MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start); - unsigned SrcReg, DstReg; - if (tii_->isMoveInstr(*DefMI, SrcReg, DstReg) && + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (DefMI && + tii_->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && DstReg == li.reg && SrcReg == Reg) { // Cache computed info. LR->valno->def = LR->start; @@ -1328,7 +1746,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ // vr1024 = op // = vr1025 // Even though vr1025 is copied from vr1024, it's not safe to - // coalesced them since live range of vr1025 intersects the + // coalesce them since the live range of vr1025 intersects the // def of vr1024. This happens because vr1025 is assigned the // value of the previous iteration of vr1024. return false; @@ -1388,7 +1806,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ // optimize for it: if there is more than one value, we merge them all into // the lowest numbered one, then handle the interval as if we were merging // with one value number. - VNInfo *LHSValNo; + VNInfo *LHSValNo = NULL; if (EliminatedLHSVals.size() > 1) { // Loop through all the equal value numbers merging them into the smallest // one. @@ -1438,8 +1856,9 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ /// physreg, this method always canonicalizes LHS to be it. The output /// "RHS" will not have been modified, so we can use this information /// below to update aliases. -bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, - LiveInterval &RHS, bool &Swapped) { +bool +SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, + bool &Swapped) { // Compute the final value assignment, assuming that the live ranges can be // coalesced. SmallVector LHSValNoAssignments; @@ -1447,26 +1866,56 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, DenseMap LHSValsDefinedFromRHS; DenseMap RHSValsDefinedFromLHS; SmallVector NewVNInfo; - + // If a live interval is a physical register, conservatively check if any // of its sub-registers is overlapping the live interval of the virtual // register. If so, do not coalesce. if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) && *tri_->getSubRegisters(LHS.reg)) { - for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR) - if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { - DOUT << "Interfere with sub-register "; - DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + // If it's coalescing a virtual register to a physical register, estimate + // its live interval length. This is the *cost* of scanning an entire live + // interval. If the cost is low, we'll do an exhaustive check instead. + + // If this is something like this: + // BB1: + // v1024 = op + // ... + // BB2: + // ... + // RAX = v1024 + // + // That is, the live interval of v1024 crosses a bb. Then we can't rely on + // less conservative check. It's possible a sub-register is defined before + // v1024 (or live in) and live out of BB1. + if (RHS.containsOneValue() && + li_->intervalIsInOneMBB(RHS) && + li_->getApproximateInstructionCount(RHS) <= 10) { + // Perform a more exhaustive check for some common cases. + if (li_->conflictsWithPhysRegRef(RHS, LHS.reg, true, JoinedCopies)) return false; - } + } else { + for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR) + if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { + DOUT << "Interfere with sub-register "; + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + return false; + } + } } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) && *tri_->getSubRegisters(RHS.reg)) { - for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR) - if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) { - DOUT << "Interfere with sub-register "; - DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + if (LHS.containsOneValue() && + li_->getApproximateInstructionCount(LHS) <= 10) { + // Perform a more exhaustive check for some common cases. + if (li_->conflictsWithPhysRegRef(LHS, RHS.reg, false, JoinedCopies)) return false; - } + } else { + for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR) + if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) { + DOUT << "Interfere with sub-register "; + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); + return false; + } + } } // Compute ultimate value numbers for the LHS and RHS values. @@ -1481,7 +1930,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, VNInfo *RHSValNoInfo = NULL; VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0); unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0); - if ((RHSSrcReg == 0 || RHSSrcReg != LHS.reg)) { + if (RHSSrcReg == 0 || RHSSrcReg != LHS.reg) { // If RHS is not defined as a copy from the LHS, we can use simpler and // faster checks to see if the live ranges are coalescable. This joiner // can't swap the LHS/RHS intervals though. @@ -1730,14 +2179,14 @@ void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, MachineInstr *Inst = MII++; // If this isn't a copy nor a extract_subreg, we can't join intervals. - unsigned SrcReg, DstReg; + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { DstReg = Inst->getOperand(0).getReg(); SrcReg = Inst->getOperand(1).getReg(); } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { DstReg = Inst->getOperand(0).getReg(); SrcReg = Inst->getOperand(2).getReg(); - } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) + } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) continue; bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); @@ -1790,7 +2239,7 @@ void SimpleRegisterCoalescing::joinIntervals() { JoinQueue = new JoinPriorityQueue(this); std::vector TryAgainList; - if (loopInfo->begin() == loopInfo->end()) { + if (loopInfo->empty()) { // If there are no loops in the function, join intervals in function order. for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E; ++I) @@ -1865,9 +2314,9 @@ void SimpleRegisterCoalescing::joinIntervals() { /// Return true if the two specified registers belong to different register /// classes. The registers may be either phys or virt regs. -bool SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, - unsigned RegB) const { - +bool +SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, + unsigned RegB) const { // Get the register classes for the first reg. if (TargetRegisterInfo::isPhysicalRegister(RegA)) { assert(TargetRegisterInfo::isVirtualRegister(RegB) && @@ -1876,11 +2325,12 @@ bool SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, } // Compare against the regclass for the second reg. - const TargetRegisterClass *RegClass = mri_->getRegClass(RegA); - if (TargetRegisterInfo::isVirtualRegister(RegB)) - return RegClass != mri_->getRegClass(RegB); - else - return !RegClass->contains(RegB); + const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA); + if (TargetRegisterInfo::isVirtualRegister(RegB)) { + const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB); + return RegClassA != RegClassB; + } + return !RegClassA->contains(RegB); } /// lastRegisterUse - Returns the last use of the specific register between @@ -1895,14 +2345,15 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, E = mri_->use_end(); I != E; ++I) { MachineOperand &Use = I.getOperand(); MachineInstr *UseMI = Use.getParent(); - unsigned SrcReg, DstReg; - if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg) && SrcReg == DstReg) + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + SrcReg == DstReg) // Ignore identity copies. continue; unsigned Idx = li_->getInstructionIndex(UseMI); if (Idx >= Start && Idx < End && Idx >= UseIdx) { LastUse = &Use; - UseIdx = Idx; + UseIdx = li_->getUseIndex(Idx); } } return LastUse; @@ -1921,13 +2372,14 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, return NULL; // Ignore identity copies. - unsigned SrcReg, DstReg; - if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg)) + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && + SrcReg == DstReg)) for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { MachineOperand &Use = MI->getOperand(i); - if (Use.isRegister() && Use.isUse() && Use.getReg() && + if (Use.isReg() && Use.isUse() && Use.getReg() && tri_->regsOverlap(Use.getReg(), Reg)) { - UseIdx = e; + UseIdx = li_->getUseIndex(e); return &Use; } } @@ -1948,6 +2400,8 @@ void SimpleRegisterCoalescing::printRegName(unsigned reg) const { void SimpleRegisterCoalescing::releaseMemory() { JoinedCopies.clear(); + ReMatCopies.clear(); + ReMatDefs.clear(); } static bool isZeroLengthInterval(LiveInterval *li) { @@ -1979,7 +2433,7 @@ SimpleRegisterCoalescing::TurnCopyIntoImpDef(MachineBasicBlock::iterator &I, CopyMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); for (int i = CopyMI->getNumOperands() - 1, e = 0; i > e; --i) CopyMI->RemoveOperand(i); - bool NoUse = mri_->use_begin(SrcReg) == mri_->use_end(); + bool NoUse = mri_->use_empty(SrcReg); if (NoUse) { for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg), E = mri_->reg_end(); I != E; ) { @@ -2019,15 +2473,18 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { // Join (coalesce) intervals if requested. if (EnableJoining) { joinIntervals(); - DOUT << "********** INTERVALS POST JOINING **********\n"; - for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){ - I->second.print(DOUT, tri_); - DOUT << "\n"; - } + DEBUG({ + DOUT << "********** INTERVALS POST JOINING **********\n"; + for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){ + I->second->print(DOUT, tri_); + DOUT << "\n"; + } + }); } // Perform a final pass over the instructions and compute spill weights // and remove identity moves. + SmallVector DeadDefs; for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { MachineBasicBlock* mbb = mbbi; @@ -2036,10 +2493,10 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); mii != mie; ) { MachineInstr *MI = mii; - unsigned SrcReg, DstReg; + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; if (JoinedCopies.count(MI)) { // Delete all coalesced copies. - if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) { + if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) && "Unrecognized copy instruction"); @@ -2056,26 +2513,59 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { continue; } + // Now check if this is a remat'ed def instruction which is now dead. + if (ReMatDefs.count(MI)) { + bool isDead = true; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (!Reg) + continue; + if (TargetRegisterInfo::isVirtualRegister(Reg)) + DeadDefs.push_back(Reg); + if (MO.isDead()) + continue; + if (TargetRegisterInfo::isPhysicalRegister(Reg) || + !mri_->use_empty(Reg)) { + isDead = false; + break; + } + } + if (isDead) { + while (!DeadDefs.empty()) { + unsigned DeadDef = DeadDefs.back(); + DeadDefs.pop_back(); + RemoveDeadDef(li_->getInterval(DeadDef), MI); + } + li_->RemoveMachineInstrFromMaps(mii); + mii = mbbi->erase(mii); + continue; + } else + DeadDefs.clear(); + } + // If the move will be an identity move delete it - bool isMove = tii_->isMoveInstr(*mii, SrcReg, DstReg); + bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); if (isMove && SrcReg == DstReg) { if (li_->hasInterval(SrcReg)) { LiveInterval &RegInt = li_->getInterval(SrcReg); // If def of this move instruction is dead, remove its live range // from the dstination register's live interval. - if (mii->registerDefIsDead(DstReg)) { - if (!ShortenDeadCopySrcLiveRange(RegInt, mii)) - ShortenDeadCopyLiveRange(RegInt, mii); + if (MI->registerDefIsDead(DstReg)) { + if (!ShortenDeadCopySrcLiveRange(RegInt, MI)) + ShortenDeadCopyLiveRange(RegInt, MI); } } - li_->RemoveMachineInstrFromMaps(mii); + li_->RemoveMachineInstrFromMaps(MI); mii = mbbi->erase(mii); ++numPeep; } else if (!isMove || !TurnCopyIntoImpDef(mii, mbb, DstReg, SrcReg)) { SmallSet UniqueUses; - for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { - const MachineOperand &mop = mii->getOperand(i); - if (mop.isRegister() && mop.getReg() && + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &mop = MI->getOperand(i); + if (mop.isReg() && mop.getReg() && TargetRegisterInfo::isVirtualRegister(mop.getReg())) { unsigned reg = mop.getReg(); // Multiple uses of reg by the same instruction. It should not @@ -2094,7 +2584,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { } for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) { - LiveInterval &LI = I->second; + LiveInterval &LI = *I->second; if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { // If the live interval length is essentially zero, i.e. in every live // range the use follows def immediately, it doesn't make sense to spill @@ -2103,7 +2593,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { LI.weight = HUGE_VALF; else { bool isLoad = false; - if (li_->isReMaterializable(LI, isLoad)) { + SmallVector SpillIs; + if (li_->isReMaterializable(LI, SpillIs, isLoad)) { // If all of the definitions of the interval are re-materializable, // it is a preferred candidate for spilling. If non of the defs are // loads, then it's potentially very cheap to re-materialize. @@ -2123,7 +2614,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { // Divide the weight of the interval by its size. This encourages // spilling of intervals that are large and have few uses, and // discourages spilling of small intervals with many uses. - LI.weight /= LI.getSize(); + LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM; } }