X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=2deece2481eeed67ff6ecd9e0ffdf0d6331222b5;hb=a6b677d209013d82b03fa8da937296b6faae7de0;hp=5f72efc750720ecb3af4c2aba54bb40e10fafb87;hpb=fd246e5f8401df3ef61bf27fec601b4b62905062;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 5f72efc7507..2deece2481e 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -28,6 +28,8 @@ #include "llvm/Target/TargetOptions.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" @@ -36,12 +38,13 @@ using namespace llvm; STATISTIC(numJoins , "Number of interval joins performed"); -STATISTIC(numSubJoins , "Number of subclass 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 @@ -55,8 +58,13 @@ NewHeuristic("new-coalescer-heuristic", cl::init(false), cl::Hidden); static cl::opt -CrossClassJoin("join-subclass-copies", - cl::desc("Coalesce copies to sub- register class"), +DisableCrossClassJoin("disable-cross-class-join", + cl::desc("Avoid coalescing cross register class copies"), + cl::init(false), cl::Hidden); + +static cl::opt +PhysJoinTweak("tweak-phys-join-heuristics", + cl::desc("Tweak heuristics for joining phys reg with vr"), cl::init(false), cl::Hidden); static RegisterPass @@ -68,6 +76,7 @@ static RegisterAnalysisGroup V(X); const PassInfo *const llvm::SimpleRegisterCoalescingID = &X; void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); AU.addRequired(); @@ -110,11 +119,12 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // Get the location that B is defined at. Two options: either this value has // an unknown definition point or it is defined at CopyIdx. If unknown, we // can't process it. - if (!BValNo->copy) return false; + if (!BValNo->getCopy()) return false; assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); // AValNo is the value number in A that defines the copy, A3 in the example. - LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); + unsigned CopyUseIdx = li_->getUseIndex(CopyIdx); + LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 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 @@ -135,7 +145,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // 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) + if (AValNo->hasRedefByEC()) return false; // If AValNo is defined as a copy from IntB, we can potentially process this. @@ -184,7 +194,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, // that defines this value #'. Update the the valnum with the new defining // instruction #. BValNo->def = FillerStart; - BValNo->copy = NULL; + BValNo->setCopy(0); // Okay, we can merge them. We need to insert a new liverange: // [ValLR.end, BLR.begin) of either value number, then we merge the @@ -192,13 +202,13 @@ 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, true, + li_->getVNInfoAllocator()))); } } @@ -218,6 +228,12 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, IntB.removeKill(ValLR->valno, FillerStart); } + // If the copy instruction was killing the destination register before the + // merge, find the last use and trim the live range. That will also add the + // isKill marker. + if (CopyMI->killsRegister(IntA.reg)) + TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR); + ++numExtends; return true; } @@ -291,7 +307,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, // Get the location that B is defined at. Two options: either this value has // an unknown definition point or it is defined at CopyIdx. If unknown, we // can't process it. - if (!BValNo->copy) return false; + if (!BValNo->getCopy()) return false; assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); // AValNo is the value number in A that defines the copy, A3 in the example. @@ -299,14 +315,30 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, 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. - if (AValNo->def == ~0U || AValNo->def == ~1U || AValNo->hasPHIKill) + // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be + // tested? + if (AValNo->isPHIDef() || !AValNo->isDefAccurate() || + AValNo->isUnused() || AValNo->hasPHIKill()) return false; MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def); const TargetInstrDesc &TID = DefMI->getDesc(); - unsigned NewDstIdx; - if (!TID.isCommutable() || - !tii_->CommuteChangesDestination(DefMI, NewDstIdx)) + if (!TID.isCommutable()) + return false; + // If DefMI is a two-address instruction then commuting it will change the + // destination register. + int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); + assert(DefIdx != -1); + unsigned UseOpIdx; + if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) + return false; + unsigned Op1, Op2, NewDstIdx; + if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2)) + return false; + if (Op1 == UseOpIdx) + NewDstIdx = Op2; + else if (Op2 == UseOpIdx) + NewDstIdx = Op1; + else return false; MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); @@ -346,9 +378,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); NewMI->getOperand(OpIdx).setIsKill(); - bool BHasPHIKill = BValNo->hasPHIKill; + bool BHasPHIKill = BValNo->hasPHIKill(); SmallVector BDeadValNos; - SmallVector BKills; + VNInfo::KillSet BKills; std::map BExtend; // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. @@ -366,6 +398,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(); @@ -384,10 +419,10 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, if (Extended) UseMO.setIsKill(false); else - BKills.push_back(li_->getUseIndex(UseIdx)+1); + BKills.push_back(VNInfo::KillInfo(false, 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#, @@ -395,7 +430,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, // extended to the end of the existing live range defined by the copy. unsigned DefIdx = li_->getDefIndex(UseIdx); const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx); - BHasPHIKill |= DLR->valno->hasPHIKill; + BHasPHIKill |= DLR->valno->hasPHIKill(); assert(DLR->valno->def == DefIdx); BDeadValNos.push_back(DLR->valno); BExtend[DLR->start] = DLR->end; @@ -412,18 +447,27 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, DOUT << "\nExtending: "; IntB.print(DOUT, tri_); // Remove val#'s defined by copies that will be coalesced away. - for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) + 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]); + } // 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; + ValNo->setCopy(0); for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) { - unsigned Kill = ValNo->kills[j]; + unsigned Kill = ValNo->kills[j].killIdx; if (Kill != BLR->end) - BKills.push_back(Kill); + BKills.push_back(VNInfo::KillInfo(ValNo->kills[j].isPHIKill, Kill)); } ValNo->kills.clear(); for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); @@ -434,9 +478,18 @@ 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; + ValNo->setHasPHIKill(BHasPHIKill); DOUT << " result = "; IntB.print(DOUT, tri_); DOUT << "\n"; @@ -450,46 +503,175 @@ 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, false); + 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, + unsigned DstSubIdx, 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) + // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be + // tested? + if (ValNo->isPHIDef() || !ValNo->isDefAccurate() || + ValNo->isUnused() || 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; + if (TID.getNumDefs() != 1) + return false; + if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { + // Make sure the copy destination register class fits the instruction + // definition register class. The mismatch can happen as a result of earlier + // extract_subreg, insert_subreg, subreg_to_reg coalescing. + const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_); + if (TargetRegisterInfo::isVirtualRegister(DstReg)) { + if (mri_->getRegClass(DstReg) != RC) + return false; + } else if (!RC->contains(DstReg)) + return false; + } unsigned DefIdx = li_->getDefIndex(CopyIdx); const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx); - DLR->valno->copy = NULL; + DLR->valno->setCopy(0); // 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 (DLR && DLR->valno->getCopy() == CopyMI) + DLR->valno->setCopy(0); } } + // If copy kills the source register, find the last use and propagate + // kill. + bool checkForDeadDef = false; MachineBasicBlock *MBB = CopyMI->getParent(); + if (CopyMI->killsRegister(SrcInt.reg)) + if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) { + checkForDeadDef = true; + } + MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI)); - CopyMI->removeFromParent(); - tii_->reMaterialize(*MBB, MII, DstReg, DefMI); + tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI); MachineInstr *NewMI = prior(MII); + + if (checkForDeadDef) { + // PR4090 fix: Trim interval failed because there was no use of the + // source interval in this MBB. If the def is in this MBB too then we + // should mark it dead: + if (DefMI->getParent() == MBB) { + DefMI->addRegisterDead(SrcInt.reg, tri_); + SrcLR->end = SrcLR->start + 1; + } + } + // 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(), @@ -500,13 +682,13 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, 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; + if (DLR && DLR->valno->getCopy() == CopyMI) + DLR->valno->setCopy(0); } } li_->ReplaceMachineInstrInMaps(CopyMI, NewMI); - MBB->getParent()->DeleteMachineInstr(CopyMI); + CopyMI->eraseFromParent(); ReMatCopies.insert(CopyMI); ReMatDefs.insert(DefMI); ++NumReMats; @@ -530,9 +712,7 @@ bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx)); if (DstLR == LI.end()) return false; - unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1; - if (DstLR->valno->kills.size() == 1 && - DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill) + if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0].isPHIKill) return true; return false; } @@ -563,13 +743,15 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, if (OldSubIdx) UseDstReg = tri_->getSubReg(DstReg, OldSubIdx); - unsigned CopySrcReg, CopyDstReg; - if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) && + 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)) + if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, + CopyDstSubIdx, UseMI)) continue; } @@ -594,51 +776,27 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, // After updating the operand, check if the machine instruction has // become a copy. If so, update its val# information. + if (JoinedCopies.count(UseMI)) + continue; + const TargetInstrDesc &TID = UseMI->getDesc(); - unsigned CopySrcReg, CopyDstReg; + unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 && - tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) && + 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; + if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) { + if (DLR->valno->def == DefIdx) + DLR->valno->setCopy(UseMI); + } } } } -/// RemoveDeadImpDef - Remove implicit_def instructions which are "re-defining" -/// registers due to insert_subreg coalescing. e.g. -/// r1024 = op -/// r1025 = implicit_def -/// r1025 = insert_subreg r1025, r1024 -/// = op r1025 -/// => -/// r1025 = op -/// r1025 = implicit_def -/// r1025 = insert_subreg r1025, r1025 -/// = op r1025 -void -SimpleRegisterCoalescing::RemoveDeadImpDef(unsigned Reg, LiveInterval &LI) { - for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), - E = mri_->reg_end(); I != E; ) { - MachineOperand &O = I.getOperand(); - MachineInstr *DefMI = &*I; - ++I; - if (!O.isDef()) - continue; - if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) - continue; - if (!LI.liveBeforeAndAt(li_->getInstructionIndex(DefMI))) - continue; - li_->RemoveMachineInstrFromMaps(DefMI); - DefMI->eraseFromParent(); - } -} - /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate /// due to live range lengthening as the result of coalescing. void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, @@ -646,37 +804,25 @@ void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), UE = mri_->use_end(); UI != UE; ++UI) { MachineOperand &UseMO = UI.getOperand(); - if (UseMO.isKill()) { - MachineInstr *UseMI = UseMO.getParent(); - unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI)); - if (JoinedCopies.count(UseMI)) - continue; - const LiveRange *UI = LI.getLiveRangeContaining(UseIdx); - if (!UI || !LI.isKill(UI->valno, UseIdx+1)) + if (!UseMO.isKill()) + continue; + MachineInstr *UseMI = UseMO.getParent(); + unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI)); + const LiveRange *LR = LI.getLiveRangeContaining(UseIdx); + if (!LR || !LI.isKill(LR->valno, UseIdx+1)) { + if (LR->valno->def != UseIdx+1) { + // Interesting problem. After coalescing reg1027's def and kill are both + // at the same point: %reg1027,0.000000e+00 = [56,814:0) 0@70-(814) + // + // bb5: + // 60 %reg1027 = t2MOVr %reg1027, 14, %reg0, %reg0 + // 68 %reg1027 = t2LDRi12 %reg1027, 8, 14, %reg0 + // 76 t2CMPzri %reg1038, 0, 14, %reg0, %CPSR + // 84 %reg1027 = t2MOVr %reg1027, 14, %reg0, %reg0 + // 96 t2Bcc mbb, 1, %CPSR + // + // Do not remove the kill marker on t2LDRi12. 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; } } } @@ -713,8 +859,9 @@ bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li, return false; // Already removed by ShortenDeadCopySrcLiveRange. unsigned RemoveStart = MLR->start; unsigned RemoveEnd = MLR->end; + unsigned DefIdx = li_->getDefIndex(CopyIdx); // Remove the liverange that's defined by this. - if (RemoveEnd == li_->getDefIndex(CopyIdx)+1) { + if (RemoveStart == DefIdx && RemoveEnd == DefIdx+1) { removeRange(li, RemoveStart, RemoveEnd, li_, tri_); return removeIntervalIfEmpty(li, li_, tri_); } @@ -741,28 +888,16 @@ static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, MachineInstr *DefMI = li_->getInstructionFromIndex(li_->getDefIndex(LRStart)); if (DefMI && DefMI != CopyMI) { - int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false, tri_); - if (DeadIdx != -1) { + int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false); + if (DeadIdx != -1) DefMI->getOperand(DeadIdx).setIsDead(); - // A dead def should have a single cycle interval. - ++LRStart; - } + else + DefMI->addOperand(MachineOperand::CreateReg(li.reg, + true, true, false, true)); + ++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; - SmallVector 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 @@ -794,55 +929,34 @@ 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; - } + if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR)) + 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(); - } + // There are other kills of the val#. Nothing to do. + if (!li.isOnlyLROfValNo(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); - } - // FIXME: Shorten intervals in BBs that reaches this BB. - } + 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#, propagate the dead marker. + 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. PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); + ++numDeadValNo; - removeRange(li, RemoveStart, LR->end, li_, tri_); + if (li.isKill(LR->valno, RemoveEnd)) + li.removeKill(LR->valno, RemoveEnd); + } + + removeRange(li, RemoveStart, RemoveEnd, li_, tri_); return removeIntervalIfEmpty(li, li_, tri_); } @@ -853,135 +967,148 @@ bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI, 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), + // Make sure this is the only use. + for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(ImpLi.reg), UE = mri_->use_end(); UI != UE;) { MachineInstr *UseMI = &*UI; ++UI; - if (JoinedCopies.count(UseMI)) + if (CopyMI == UseMI || 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 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 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; +/// isWinToJoinVRWithSrcPhysReg - Return true if it's worth while to join a +/// a virtual destination register with physical source register. +bool +SimpleRegisterCoalescing::isWinToJoinVRWithSrcPhysReg(MachineInstr *CopyMI, + MachineBasicBlock *CopyMBB, + LiveInterval &DstInt, + LiveInterval &SrcInt) { + // 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. + const TargetRegisterClass *RC = mri_->getRegClass(DstInt.reg); + unsigned Threshold = allocatableRCRegs_[RC].count() * 2; + unsigned Length = li_->getApproximateInstructionCount(DstInt); + if (Length > Threshold && + (((float)std::distance(mri_->use_begin(DstInt.reg), + mri_->use_end()) / Length) < (1.0 / Threshold))) + return false; + + // If the virtual register live interval extends into a loop, turn down + // aggressiveness. + unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); + const MachineLoop *L = loopInfo->getLoopFor(CopyMBB); + if (!L) { + // Let's see if the virtual register live interval extends into the loop. + LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx); + assert(DLR != DstInt.end() && "Live range not found!"); + DLR = DstInt.FindLiveRangeContaining(DLR->end+1); + if (DLR != DstInt.end()) { + CopyMBB = li_->getMBBFromIndex(DLR->start); + L = loopInfo->getLoopFor(CopyMBB); } } - 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(); + + if (!L || Length <= Threshold) + return true; + + unsigned UseIdx = li_->getUseIndex(CopyIdx); + LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); + MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); + if (loopInfo->getLoopFor(SMBB) != L) { + if (!loopInfo->isLoopHeader(CopyMBB)) + return false; + // If vr's live interval extends pass the loop header, do not join. + for (MachineBasicBlock::succ_iterator SI = CopyMBB->succ_begin(), + SE = CopyMBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SuccMBB = *SI; + if (SuccMBB == CopyMBB) + continue; + if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB), + li_->getMBBEndIdx(SuccMBB)+1)) + return false; } } + return true; } -/// 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) { - 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. +/// isWinToJoinVRWithDstPhysReg - Return true if it's worth while to join a +/// copy from a virtual source register to a physical destination register. bool -SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg, - unsigned DstReg, - MachineBasicBlock *MBB){ - if (!CrossClassJoin) +SimpleRegisterCoalescing::isWinToJoinVRWithDstPhysReg(MachineInstr *CopyMI, + MachineBasicBlock *CopyMBB, + LiveInterval &DstInt, + LiveInterval &SrcInt) { + // 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. + const TargetRegisterClass *RC = mri_->getRegClass(SrcInt.reg); + unsigned Threshold = allocatableRCRegs_[RC].count() * 2; + unsigned Length = li_->getApproximateInstructionCount(SrcInt); + if (Length > Threshold && + (((float)std::distance(mri_->use_begin(SrcInt.reg), + mri_->use_end()) / Length) < (1.0 / Threshold))) 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) + if (SrcInt.empty()) + // Must be implicit_def. + return false; + + // If the virtual register live interval is defined or cross a loop, turn + // down aggressiveness. + unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); + unsigned UseIdx = li_->getUseIndex(CopyIdx); + LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); + assert(SLR != SrcInt.end() && "Live range not found!"); + SLR = SrcInt.FindLiveRangeContaining(SLR->start-1); + if (SLR == SrcInt.end()) + return true; + MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); + const MachineLoop *L = loopInfo->getLoopFor(SMBB); + + if (!L || Length <= Threshold) + return true; + + if (loopInfo->getLoopFor(CopyMBB) != L) { + if (SMBB != L->getLoopLatch()) return false; + // If vr's live interval is extended from before the loop latch, do not + // join. + for (MachineBasicBlock::pred_iterator PI = SMBB->pred_begin(), + PE = SMBB->pred_end(); PI != PE; ++PI) { + MachineBasicBlock *PredMBB = *PI; + if (PredMBB == SMBB) + continue; + if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB), + li_->getMBBEndIdx(PredMBB)+1)) + return false; + } } + return true; +} +/// 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 &SrcInt = li_->getInterval(SrcReg); - LiveInterval &DstInt = li_->getInterval(DstReg); - unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt); - unsigned DstSize = li_->getApproximateInstructionCount(DstInt); - const TargetRegisterClass *RC = mri_->getRegClass(DstReg); - unsigned Threshold = allocatableRCRegs_[RC].count() * 2; - return (SrcSize + DstSize) <= Threshold; + 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 @@ -1016,11 +1143,12 @@ SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, TargetRegisterInfo::isPhysicalRegister(SrcReg) ? tri_->getPhysicalRegisterRegClass(SrcReg) : mri_->getRegClass(SrcReg); - if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_)) + if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) return true; } } - if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { + if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || + MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { SubIdx = MI->getOperand(3).getImm(); if (VirtReg == MI->getOperand(0).getReg()) { if (!tri_->getSubReg(PhysReg, SubIdx)) @@ -1031,7 +1159,7 @@ SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, TargetRegisterInfo::isPhysicalRegister(DstReg) ? tri_->getPhysicalRegisterRegClass(DstReg) : mri_->getRegClass(DstReg); - if (!getMatchingSuperReg(PhysReg, SubIdx, RC, tri_)) + if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) return true; } } @@ -1040,6 +1168,74 @@ SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, } +/// 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 = tri_->getMatchingSuperReg(DstReg, SubIdx, RC); + 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 = tri_->getMatchingSuperReg(SrcReg, SubIdx, RC); + 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; +} + +/// getRegAllocPreference - Return register allocation preference register. +/// +static unsigned getRegAllocPreference(unsigned Reg, MachineFunction &MF, + MachineRegisterInfo *MRI, + const TargetRegisterInfo *TRI) { + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + return 0; + std::pair Hint = MRI->getRegAllocationHint(Reg); + return TRI->ResolveRegAllocHint(Hint.first, Hint.second, MF); +} + /// 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 @@ -1054,25 +1250,30 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI; - unsigned SrcReg; - unsigned DstReg; + unsigned SrcReg, DstReg, SrcSubIdx = 0, DstSubIdx = 0; bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG; + bool isSubRegToReg = CopyMI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG; unsigned SubIdx = 0; if (isExtSubReg) { - DstReg = CopyMI->getOperand(0).getReg(); - SrcReg = CopyMI->getOperand(1).getReg(); - } else if (isInsSubReg) { - if (CopyMI->getOperand(2).getSubReg()) { + DstReg = CopyMI->getOperand(0).getReg(); + DstSubIdx = CopyMI->getOperand(0).getSubReg(); + SrcReg = CopyMI->getOperand(1).getReg(); + SrcSubIdx = CopyMI->getOperand(2).getImm(); + } else if (isInsSubReg || isSubRegToReg) { + DstReg = CopyMI->getOperand(0).getReg(); + DstSubIdx = CopyMI->getOperand(3).getImm(); + SrcReg = CopyMI->getOperand(2).getReg(); + SrcSubIdx = CopyMI->getOperand(2).getSubReg(); + if (SrcSubIdx && SrcSubIdx != DstSubIdx) { + // r1025 = INSERT_SUBREG r1025, r1024<2>, 2 Then r1024 has already been + // coalesced to a larger register so the subreg indices cancel out. DOUT << "\tSource of insert_subreg is already coalesced " << "to another register.\n"; return false; // Not coalescable. } - DstReg = CopyMI->getOperand(0).getReg(); - SrcReg = CopyMI->getOperand(2).getReg(); - } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) { - assert(0 && "Unrecognized copy instruction!"); - return false; + } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){ + llvm_unreachable("Unrecognized copy instruction!"); } // If they are already joined we continue. @@ -1100,12 +1301,50 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { return false; // Not coalescable. } + // Check that a physical source register is compatible with dst regclass + if (SrcIsPhys) { + unsigned SrcSubReg = SrcSubIdx ? + tri_->getSubReg(SrcReg, SrcSubIdx) : SrcReg; + const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); + const TargetRegisterClass *DstSubRC = DstRC; + if (DstSubIdx) + DstSubRC = DstRC->getSubRegisterRegClass(DstSubIdx); + assert(DstSubRC && "Illegal subregister index"); + if (!DstSubRC->contains(SrcSubReg)) { + DEBUG(errs() << "\tIncompatible destination regclass: " + << tri_->getName(SrcSubReg) << " not in " << DstSubRC->getName() + << ".\n"); + return false; // Not coalescable. + } + } + + // Check that a physical dst register is compatible with source regclass + if (DstIsPhys) { + unsigned DstSubReg = DstSubIdx ? + tri_->getSubReg(DstReg, DstSubIdx) : DstReg; + const TargetRegisterClass *SrcRC = mri_->getRegClass(SrcReg); + const TargetRegisterClass *SrcSubRC = SrcRC; + if (SrcSubIdx) + SrcSubRC = SrcRC->getSubRegisterRegClass(SrcSubIdx); + assert(SrcSubRC && "Illegal subregister index"); + if (!SrcSubRC->contains(DstReg)) { + DEBUG(errs() << "\tIncompatible source regclass: " + << tri_->getName(DstSubReg) << " not in " << SrcSubRC->getName() + << ".\n"); + (void)DstSubReg; + return false; // Not coalescable. + } + } + // Should be non-null only when coalescing to a sub-register class. - const TargetRegisterClass *SubRC = NULL; + bool CrossRC = false; + const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg); + const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg); + const TargetRegisterClass *NewRC = NULL; MachineBasicBlock *CopyMBB = CopyMI->getParent(); unsigned RealDstReg = 0; unsigned RealSrcReg = 0; - if (isExtSubReg || isInsSubReg) { + if (isExtSubReg || isInsSubReg || isSubRegToReg) { SubIdx = CopyMI->getOperand(isExtSubReg ? 2 : 3).getImm(); if (SrcIsPhys && isExtSubReg) { // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be @@ -1121,7 +1360,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } else SrcReg = tri_->getSubReg(SrcReg, SubIdx); SubIdx = 0; - } else if (DstIsPhys && isInsSubReg) { + } else if (DstIsPhys && (isInsSubReg || isSubRegToReg)) { // EAX = INSERT_SUBREG EAX, r1024, 0 unsigned SrcSubIdx = CopyMI->getOperand(2).getSubReg(); if (SrcSubIdx) { @@ -1134,51 +1373,27 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } else 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" + } else if ((DstIsPhys && isExtSubReg) || + (SrcIsPhys && (isInsSubReg || isSubRegToReg))) { + if (!isSubRegToReg && CopyMI->getOperand(1).getSubReg()) { + 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 extract_subreg instruction!"); + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg)) + return false; // Not coalescable } else { - RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_); - assert(RealSrcReg && "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. - 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() : CopyMI->getOperand(2).getSubReg(); if (OldSubIdx) { - if (OldSubIdx == SubIdx && - !differingRegisterClasses(SrcReg, DstReg, SubRC)) + if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg)) // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been // coalesced to a larger register so the subreg indices cancel out. // Also check if the other larger register is of the same register @@ -1190,43 +1405,106 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } } if (SubIdx) { + if (!DstIsPhys && !SrcIsPhys) { + if (isInsSubReg || isSubRegToReg) { + NewRC = tri_->getMatchingSuperRegClass(DstRC, SrcRC, SubIdx); + } else // extract_subreg { + NewRC = tri_->getMatchingSuperRegClass(SrcRC, DstRC, SubIdx); + } + if (!NewRC) { + DOUT << "\t Conflicting sub-register indices.\n"; + return false; // Not coalescable + } + unsigned LargeReg = isExtSubReg ? SrcReg : DstReg; unsigned SmallReg = isExtSubReg ? DstReg : SrcReg; - unsigned LargeRegSize = - li_->getApproximateInstructionCount(li_->getInterval(LargeReg)); - unsigned SmallRegSize = - li_->getApproximateInstructionCount(li_->getInterval(SmallReg)); - 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, SubRC)) { - // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced + } else if (differingRegisterClasses(SrcReg, DstReg)) { + if (DisableCrossClassJoin) + 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 (!SubRC || !isProfitableToCoalesceToSubRC(SrcReg, DstReg, CopyMBB)) { - // If they are not of the same register class, we cannot join them. + // Process moves where one of the registers have a sub-register index. + MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg); + MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg); + SubIdx = DstMO->getSubReg(); + if (SubIdx) { + if (SrcMO->getSubReg()) + // FIXME: can we handle this? + return false; + // This is not an insert_subreg but it looks like one. + // e.g. %reg1024:4 = MOV32rr %EAX + isInsSubReg = true; + if (SrcIsPhys) { + if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) + return false; // Not coalescable + SubIdx = 0; + } + } else { + SubIdx = SrcMO->getSubReg(); + if (SubIdx) { + // This is not a extract_subreg but it looks like one. + // e.g. %cl = MOV16rr %reg1024:1 + isExtSubReg = true; + if (DstIsPhys) { + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg)) + return false; // Not coalescable + SubIdx = 0; + } + } + } + + unsigned LargeReg = SrcReg; + unsigned SmallReg = DstReg; + + // 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; + } + if (!DstIsPhys && !SrcIsPhys) + NewRC = SrcRC; + } else if (!SrcIsPhys && !DstIsPhys) { + NewRC = getCommonSubClass(SrcRC, DstRC); + if (!NewRC) { + DEBUG(errs() << "\tDisjoint regclasses: " + << SrcRC->getName() << ", " + << DstRC->getName() << ".\n"); + return false; // Not coalescable. + } + if (DstRC->getSize() > SrcRC->getSize()) + std::swap(LargeReg, SmallReg); + } + + // 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. + // But later r1024 is assigned EAX then r1025 may be coalesced with EAX. Again = true; // May be possible to coalesce later. return false; } @@ -1247,8 +1525,17 @@ 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) { + if (!isExtSubReg && !isInsSubReg && !isSubRegToReg) { MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false); bool isDead = mopd->isDead(); @@ -1257,26 +1544,51 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // these are not spillable! If the destination interval uses are far away, // think twice about coalescing them! if (!isDead && (SrcIsPhys || DstIsPhys)) { - LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; - unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg; - unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg; - const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg); - unsigned Threshold = allocatableRCRegs_[RC].count() * 2; - if (TheCopy.isBackEdge) - Threshold *= 2; // Favors back edge copies. - - // 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 = li_->getApproximateInstructionCount(JoinVInt); - if (Length > 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"; - Again = true; // May be possible to coalesce later. - return false; + // If the copy is in a loop, take care not to coalesce aggressively if the + // src is coming in from outside the loop (or the dst is out of the loop). + // If it's not in a loop, then determine whether to join them base purely + // by the length of the interval. + if (PhysJoinTweak) { + if (SrcIsPhys) { + if (!isWinToJoinVRWithSrcPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { + mri_->setRegAllocationHint(DstInt.reg, 0, SrcReg); + ++numAborts; + DOUT << "\tMay tie down a physical register, abort!\n"; + Again = true; // May be possible to coalesce later. + return false; + } + } else { + if (!isWinToJoinVRWithDstPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { + mri_->setRegAllocationHint(SrcInt.reg, 0, DstReg); + ++numAborts; + DOUT << "\tMay tie down a physical register, abort!\n"; + Again = true; // May be possible to coalesce later. + return false; + } + } + } else { + // 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. + LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; + unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg; + unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg; + const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg); + unsigned Threshold = allocatableRCRegs_[RC].count() * 2; + if (TheCopy.isBackEdge) + Threshold *= 2; // Favors back edge copies. + + unsigned Length = li_->getApproximateInstructionCount(JoinVInt); + float Ratio = 1.0 / Threshold; + if (Length > Threshold && + (((float)std::distance(mri_->use_begin(JoinVReg), + mri_->use_end()) / Length) < Ratio)) { + mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg); + ++numAborts; + DOUT << "\tMay tie down a physical register, abort!\n"; + Again = true; // May be possible to coalesce later. + return false; + } } } } @@ -1301,12 +1613,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // If definition of source is defined by trivial computation, try // rematerializing it. - if (!isExtSubReg && !isInsSubReg && - ReMaterializeTrivialDef(SrcInt, DstInt.reg, CopyMI)) + if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && + ReMaterializeTrivialDef(SrcInt, DstReg, DstSubIdx, CopyMI)) return true; // If we can eliminate the copy without merging the live ranges, do so now. - if (!isExtSubReg && !isInsSubReg && + if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) || RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) { JoinedCopies.insert(CopyMI); @@ -1338,21 +1650,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->getCopy(), + false, // updated at * + li_->getVNInfoAllocator()); + NewValNo->setFlags(ValNo->getFlags()); // * updated here. + RealInt.addKills(NewValNo, ValNo->kills); + RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo); } - + RealInt.weight += SavedLI->weight; DstReg = RealDstReg ? RealDstReg : RealSrcReg; } @@ -1364,9 +1672,11 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the // larger super-register. - if ((isExtSubReg || isInsSubReg) && !SrcIsPhys && !DstIsPhys) { - if ((isExtSubReg && !Swapped) || (isInsSubReg && Swapped)) { - ResSrcInt->Copy(*ResDstInt, li_->getVNInfoAllocator()); + if ((isExtSubReg || isInsSubReg || isSubRegToReg) && + !SrcIsPhys && !DstIsPhys) { + if ((isExtSubReg && !Swapped) || + ((isInsSubReg || isSubRegToReg) && Swapped)) { + ResSrcInt->Copy(*ResDstInt, mri_, li_->getVNInfoAllocator()); std::swap(SrcReg, DstReg); std::swap(ResSrcInt, ResDstInt); } @@ -1374,23 +1684,30 @@ 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 (SubRC) { - mri_->setRegClass(DstReg, SubRC); - ++numSubJoins; - } + if (CrossRC) + ++numCrossRCs; + + // This may happen even if it's cross-rc coalescing. e.g. + // %reg1026 = SUBREG_TO_REG 0, %reg1037, 4 + // reg1026 -> GR64, reg1037 -> GR32_ABCD. The resulting register will have to + // be allocate a register from GR64_ABCD. + 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(), e = ResSrcInt->vni_end(); i != e; ++i) { const VNInfo *vni = *i; - if (!vni->def || vni->def == ~1U || vni->def == ~0U) + // FIXME: Do isPHIDef and isDefAccurate both need to be tested? + if (!vni->def || vni->isUnused() || vni->isPHIDef() || !vni->isDefAccurate()) 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)) { + tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg, + NewSrcSubIdx, NewDstSubIdx)) { unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB); JoinQueue->push(CopyRec(CopyMI, LoopDepth, isBackEdgeCopy(CopyMI, DstReg))); @@ -1407,49 +1724,29 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (TargetRegisterInfo::isVirtualRegister(DstReg)) RemoveUnnecessaryKills(DstReg, *ResDstInt); - if (isInsSubReg) - // Avoid: - // r1024 = op - // r1024 = implicit_def - // ... - // = r1024 - RemoveDeadImpDef(DstReg, *ResDstInt); UpdateRegDefsUses(SrcReg, DstReg, SubIdx); // SrcReg is guarateed to be the register whose live interval that is // being merged. li_->removeInterval(SrcReg); - 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 - // length interval. Remove the val#. - unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); - const LiveRange *LR = ResDstInt->getLiveRangeContaining(CopyIdx); - VNInfo *ImpVal = LR->valno; - assert(ImpVal->def == CopyIdx); - unsigned NextDef = LR->end; - RemoveCopiesFromValNo(*ResDstInt, ImpVal); - ResDstInt->removeValNo(ImpVal); - LR = ResDstInt->FindLiveRangeContaining(NextDef); - if (LR != ResDstInt->end() && LR->valno->def == NextDef) { - // Special case: vr1024 = implicit_def - // vr1024 = insert_subreg vr1024, vr1025, c - // The insert_subreg becomes a "copy" that defines a val# which can itself - // be coalesced away. - MachineInstr *DefMI = li_->getInstructionFromIndex(NextDef); - if (DefMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) - LR->valno->copy = DefMI; - } + // Update regalloc hint. + tri_->UpdateRegAllocHint(SrcReg, DstReg, *mf_); + + // Manually deleted the live interval copy. + if (SavedLI) { + SavedLI->clear(); + delete SavedLI; } // If resulting interval has a preference that no longer fits because of subreg // coalescing, just clear the preference. - if (ResDstInt->preference && (isExtSubReg || isInsSubReg) && + unsigned Preference = getRegAllocPreference(ResDstInt->reg, *mf_, mri_, tri_); + if (Preference && (isExtSubReg || isInsSubReg || isSubRegToReg) && TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) { const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg); - if (!RC->contains(ResDstInt->preference)) - ResDstInt->preference = 0; + if (!RC->contains(Preference)) + mri_->setRegAllocationHint(ResDstInt->reg, 0, 0); } DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, tri_); @@ -1523,18 +1820,20 @@ bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li, unsigned SrcReg = li_->getVNInfoSourceReg(LR->valno); if (SrcReg == Reg) return true; - if (LR->valno->def == ~0U && + // FIXME: Do isPHIDef and isDefAccurate both need to be tested? + if ((LR->valno->isPHIDef() || !LR->valno->isDefAccurate()) && TargetRegisterInfo::isPhysicalRegister(li.reg) && *tri_->getSuperRegisters(li.reg)) { // 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 (DefMI && 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; - LR->valno->copy = DefMI; + LR->valno->setCopy(DefMI); return true; } } @@ -1596,7 +1895,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; @@ -1677,7 +1976,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ *tri_->getSuperRegisters(LHS.reg)) // Imprecise sub-register information. Can't handle it. return false; - assert(0 && "No copies from the RHS?"); + llvm_unreachable("No copies from the RHS?"); } else { LHSValNo = EliminatedLHSVals[0]; } @@ -1687,17 +1986,32 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ // value number is defined where the RHS value number was. const VNInfo *VNI = RHS.getValNumInfo(0); LHSValNo->def = VNI->def; - LHSValNo->copy = VNI->copy; + LHSValNo->setCopy(VNI->getCopy()); // Okay, the final step is to loop over the RHS live intervals, adding them to // the LHS. - LHSValNo->hasPHIKill |= VNI->hasPHIKill; + if (VNI->hasPHIKill()) + LHSValNo->setHasPHIKill(true); LHS.addKills(LHSValNo, VNI->kills); LHS.MergeRangesInAsValue(RHS, LHSValNo); - LHS.weight += RHS.weight; - if (RHS.preference && !LHS.preference) - LHS.preference = RHS.preference; - + + LHS.ComputeJoinedWeight(RHS); + + // Update regalloc hint if both are virtual registers. + if (TargetRegisterInfo::isVirtualRegister(LHS.reg) && + TargetRegisterInfo::isVirtualRegister(RHS.reg)) { + std::pair RHSPref = mri_->getRegAllocationHint(RHS.reg); + std::pair LHSPref = mri_->getRegAllocationHint(LHS.reg); + if (RHSPref != LHSPref) + mri_->setRegAllocationHint(LHS.reg, RHSPref.first, RHSPref.second); + } + + // Update the liveintervals of sub-registers. + if (TargetRegisterInfo::isPhysicalRegister(LHS.reg)) + for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS) + li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS, + li_->getVNInfoAllocator()); + return true; } @@ -1845,7 +2159,7 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); i != e; ++i) { VNInfo *VNI = *i; - if (VNI->def == ~1U || VNI->copy == 0) // Src not defined by a copy? + if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the LHS interval. If the src is @@ -1862,7 +2176,7 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); i != e; ++i) { VNInfo *VNI = *i; - if (VNI->def == ~1U || VNI->copy == 0) // Src not defined by a copy? + if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the RHS interval. If the src is @@ -1882,7 +2196,7 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, i != e; ++i) { VNInfo *VNI = *i; unsigned VN = VNI->id; - if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) + if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) continue; ComputeUltimateVN(VNI, NewVNInfo, LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, @@ -1892,7 +2206,7 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, i != e; ++i) { VNInfo *VNI = *i; unsigned VN = VNI->id; - if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) + if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) continue; // If this value number isn't a copy from the LHS, it's a new number. if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { @@ -1956,7 +2270,8 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, VNInfo *VNI = I->first; unsigned LHSValID = LHSValNoAssignments[VNI->id]; LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def); - NewVNInfo[LHSValID]->hasPHIKill |= VNI->hasPHIKill; + if (VNI->hasPHIKill()) + NewVNInfo[LHSValID]->setHasPHIKill(true); RHS.addKills(NewVNInfo[LHSValID], VNI->kills); } @@ -1966,7 +2281,8 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, VNInfo *VNI = I->first; unsigned RHSValID = RHSValNoAssignments[VNI->id]; LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def); - NewVNInfo[RHSValID]->hasPHIKill |= VNI->hasPHIKill; + if (VNI->hasPHIKill()) + NewVNInfo[RHSValID]->setHasPHIKill(true); LHS.addKills(NewVNInfo[RHSValID], VNI->kills); } @@ -1975,10 +2291,12 @@ SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, if ((RHS.ranges.size() > LHS.ranges.size() && TargetRegisterInfo::isVirtualRegister(LHS.reg)) || TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { - RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo); + RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo, + mri_); Swapped = true; } else { - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo); + LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, + mri_); Swapped = false; } return true; @@ -2018,7 +2336,7 @@ bool CopyRecSort::operator()(CopyRec left, CopyRec right) const { void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, std::vector &TryAgain) { - DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; + DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); std::vector VirtCopies; std::vector PhysCopies; @@ -2029,14 +2347,15 @@ 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) { + } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG || + Inst->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { 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); @@ -2163,14 +2482,10 @@ void SimpleRegisterCoalescing::joinIntervals() { } /// Return true if the two specified registers belong to different register -/// classes. The registers may be either phys or virt regs. In the -/// case where both registers are virtual registers, it would also returns -/// true by reference the RegB register class in SubRC if it is a subset of -/// RegA's register class. +/// classes. The registers may be either phys or virt regs. bool -SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB, - const TargetRegisterClass *&SubRC) const { - +SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, + unsigned RegB) const { // Get the register classes for the first reg. if (TargetRegisterInfo::isPhysicalRegister(RegA)) { assert(TargetRegisterInfo::isVirtualRegister(RegB) && @@ -2182,10 +2497,7 @@ SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB, const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA); if (TargetRegisterInfo::isVirtualRegister(RegB)) { const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB); - if (RegClassA == RegClassB) - return false; - SubRC = (RegClassA->hasSubClass(RegClassB)) ? RegClassB : NULL; - return true; + return RegClassA != RegClassB; } return !RegClassA->contains(RegB); } @@ -2202,14 +2514,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; @@ -2228,13 +2541,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.isReg() && Use.isUse() && Use.getReg() && tri_->regsOverlap(Use.getReg(), Reg)) { - UseIdx = e; + UseIdx = li_->getUseIndex(e); return &Use; } } @@ -2262,49 +2576,11 @@ void SimpleRegisterCoalescing::releaseMemory() { static bool isZeroLengthInterval(LiveInterval *li) { for (LiveInterval::Ranges::const_iterator i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) - if (i->end - i->start > LiveIntervals::InstrSlots::NUM) + if (i->end - i->start > LiveInterval::InstrSlots::NUM) return false; return true; } -/// TurnCopyIntoImpDef - If source of the specified copy is an implicit def, -/// turn the copy into an implicit def. -bool -SimpleRegisterCoalescing::TurnCopyIntoImpDef(MachineBasicBlock::iterator &I, - MachineBasicBlock *MBB, - unsigned DstReg, unsigned SrcReg) { - MachineInstr *CopyMI = &*I; - unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); - if (!li_->hasInterval(SrcReg)) - return false; - LiveInterval &SrcInt = li_->getInterval(SrcReg); - if (!SrcInt.empty()) - return false; - if (!li_->hasInterval(DstReg)) - return false; - LiveInterval &DstInt = li_->getInterval(DstReg); - const LiveRange *DstLR = DstInt.getLiveRangeContaining(CopyIdx); - DstInt.removeValNo(DstLR->valno); - 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_empty(SrcReg); - if (NoUse) { - for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg), - E = mri_->reg_end(); I != E; ) { - assert(I.getOperand().isDef()); - MachineInstr *DefMI = &*I; - ++I; - // The implicit_def source has no other uses, delete it. - assert(DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF); - li_->RemoveMachineInstrFromMaps(DefMI); - DefMI->eraseFromParent(); - } - } - ++I; - return true; -} - bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; @@ -2315,9 +2591,9 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { li_ = &getAnalysis(); loopInfo = &getAnalysis(); - DOUT << "********** SIMPLE REGISTER COALESCING **********\n" - << "********** Function: " - << ((Value*)mf_->getFunction())->getName() << '\n'; + DEBUG(errs() << "********** SIMPLE REGISTER COALESCING **********\n" + << "********** Function: " + << ((Value*)mf_->getFunction())->getName() << '\n'); allocatableRegs_ = tri_->getAllocatableSet(fn); for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(), @@ -2348,12 +2624,13 @@ 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) && + MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || + MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) && "Unrecognized copy instruction"); DstReg = MI->getOperand(0).getReg(); } @@ -2376,6 +2653,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); + if (!Reg) + continue; if (TargetRegisterInfo::isVirtualRegister(Reg)) DeadDefs.push_back(Reg); if (MO.isDead()) @@ -2400,7 +2679,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { } // If the move will be an identity move delete it - bool isMove = tii_->isMoveInstr(*MI, SrcReg, DstReg); + bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); if (isMove && SrcReg == DstReg) { if (li_->hasInterval(SrcReg)) { LiveInterval &RegInt = li_->getInterval(SrcReg); @@ -2414,7 +2693,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { li_->RemoveMachineInstrFromMaps(MI); mii = mbbi->erase(mii); ++numPeep; - } else if (!isMove || !TurnCopyIntoImpDef(mii, mbb, DstReg, SrcReg)) { + } else { SmallSet UniqueUses; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &mop = MI->getOperand(i); @@ -2461,7 +2740,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { } // Slightly prefer live interval that has been assigned a preferred reg. - if (LI.preference) + std::pair Hint = mri_->getRegAllocationHint(LI.reg); + if (Hint.first || Hint.second) LI.weight *= 1.01F; // Divide the weight of the interval by its size. This encourages