X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=7c512ed368a8669d088ceb64c8daa984987caf96;hb=420cdebbcb95f3881ab3518fd3bb670837669e43;hp=03e416b26064a05cc8d7ce5f074d56d89852f7b1;hpb=343013538f72f2202338f57161c0bd92344ca407;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 03e416b2606..7c512ed368a 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -13,17 +13,17 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regcoalescing" -#include "llvm/CodeGen/SimpleRegisterCoalescing.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "SimpleRegisterCoalescing.h" #include "VirtRegMap.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/Value.h" -#include "llvm/Analysis/LoopInfo.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/SSARegMap.h" -#include "llvm/Target/MRegisterInfo.h" +#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Support/CommandLine.h" @@ -36,6 +36,8 @@ using namespace llvm; STATISTIC(numJoins , "Number of interval joins performed"); +STATISTIC(numCommutes , "Number of instruction commuting performed"); +STATISTIC(numExtends , "Number of copies extended"); STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); STATISTIC(numAborts , "Number of times interval joining aborted"); @@ -46,20 +48,33 @@ namespace { cl::desc("Coalesce copies (default=true)"), cl::init(true)); + static cl::opt + NewHeuristic("new-coalescer-heuristic", + cl::desc("Use new coalescer heuristic"), + cl::init(false)); + + static cl::opt + CommuteDef("coalescer-commute-instrs", + cl::init(false), cl::Hidden); + RegisterPass X("simple-register-coalescing", "Simple Register Coalescing"); + + // Declare that we implement the RegisterCoalescer interface + RegisterAnalysisGroup V(X); } const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo(); void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { - //AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(MachineDominatorsID); AU.addPreservedID(PHIEliminationID); AU.addPreservedID(TwoAddressInstructionPassID); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -78,8 +93,9 @@ void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { /// /// This returns true if an interval was modified. /// -bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, - MachineInstr *CopyMI) { +bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, + LiveInterval &IntB, + MachineInstr *CopyMI) { unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); // BValNo is a value number in B that is defined by a copy from A. 'B3' in @@ -90,25 +106,23 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // 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->reg) return false; - assert(BValNo->def == CopyIdx && - "Copy doesn't define the value?"); + if (!BValNo->copy) return false; + assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); - // AValNo is the value number in A that defines the copy, A0 in the example. - LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1); - VNInfo *AValNo = AValLR->valno; - - // If AValNo is defined as a copy from IntB, we can potentially process this. + // AValNo is the value number in A that defines the copy, A3 in the example. + LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); + VNInfo *AValNo = ALR->valno; + // If AValNo is defined as a copy from IntB, we can potentially process this. // Get the instruction that defines this value number. - unsigned SrcReg = AValNo->reg; + unsigned SrcReg = li_->getVNInfoSourceReg(AValNo); if (!SrcReg) return false; // Not defined by a copy. // If the value number is not defined by a copy instruction, ignore it. - + // If the source register comes from an interval other than IntB, we can't // handle this. - if (rep(SrcReg) != IntB.reg) return false; + if (SrcReg != IntB.reg) return false; // Get the LiveRange in IntB that this value number starts with. LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1); @@ -127,24 +141,24 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // 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 (MRegisterInfo::isPhysicalRegister(IntB.reg) && - *mri_->getSubRegisters(IntB.reg)) { - for (const unsigned* SR = mri_->getSubRegisters(IntB.reg); *SR; ++SR) + if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) && + *tri_->getSubRegisters(IntB.reg)) { + for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) { DOUT << "Interfere with sub-register "; - DEBUG(li_->getInterval(*SR).print(DOUT, mri_)); + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); return false; } } - DOUT << "\nExtending: "; IntB.print(DOUT, mri_); + DOUT << "\nExtending: "; IntB.print(DOUT, tri_); unsigned FillerStart = ValLR->end, FillerEnd = BLR->start; // We are about to delete CopyMI, so need to remove it as the 'instruction // that defines this value #'. Update the the valnum with the new defining // instruction #. - BValNo->def = FillerStart; - BValNo->reg = 0; + BValNo->def = FillerStart; + BValNo->copy = NULL; // Okay, we can merge them. We need to insert a new liverange: // [ValLR.end, BLR.begin) of either value number, then we merge the @@ -153,89 +167,430 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // If the IntB live range is assigned to a physical register, and if that // physreg has aliases, - if (MRegisterInfo::isPhysicalRegister(IntB.reg)) { + if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { // Update the liveintervals of sub-registers. - for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) { + for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) { LiveInterval &AliasLI = li_->getInterval(*AS); AliasLI.addRange(LiveRange(FillerStart, FillerEnd, - AliasLI.getNextValue(FillerStart, 0))); + AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator()))); } } // Okay, merge "B1" into the same value number as "B0". if (BValNo != ValLR->valno) IntB.MergeValueNumberInto(BValNo, ValLR->valno); - DOUT << " result = "; IntB.print(DOUT, mri_); + 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) - ValLREndInst->getOperand(UIdx).unsetIsKill(); + ValLREndInst->getOperand(UIdx).setIsKill(false); + + ++numExtends; + return true; +} + +/// HasOtherReachingDefs - Return true if there are definitions of IntB +/// other than BValNo val# that can reach uses of AValno val# of IntA. +bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA, + LiveInterval &IntB, + VNInfo *AValNo, + VNInfo *BValNo) { + for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); + AI != AE; ++AI) { + if (AI->valno != AValNo) continue; + LiveInterval::Ranges::iterator BI = + std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); + if (BI != IntB.ranges.begin()) + --BI; + for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { + if (BI->valno == BValNo) + continue; + if (BI->start <= AI->start && BI->end > AI->start) + return true; + if (BI->start > AI->start && BI->start < AI->end) + return true; + } + } + return false; +} + +/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA +/// being the source and IntB being the dest, thus this defines a value number +/// in IntB. If the source value number (in IntA) is defined by a commutable +/// instruction and its other operand is coalesced to the copy dest register, +/// see if we can transform the copy into a noop by commuting the definition. For +/// example, +/// +/// A3 = op A2 B0 +/// ... +/// B1 = A3 <- this copy +/// ... +/// = op A3 <- more uses +/// +/// ==> +/// +/// B2 = op B0 A2 +/// ... +/// B1 = B2 <- now an identify copy +/// ... +/// = op B2 <- more uses +/// +/// This returns true if an interval was modified. +/// +bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, + LiveInterval &IntB, + MachineInstr *CopyMI) { + if (!CommuteDef) return false; + + unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); + + // FIXME: For now, only eliminate the copy by commuting its def when the + // source register is a virtual register. We want to guard against cases + // where the copy is a back edge copy and commuting the def lengthen the + // live interval of the source register to the entire loop. + if (TargetRegisterInfo::isPhysicalRegister(IntA.reg)) + return false; + + // 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); + VNInfo *BValNo = BLR->valno; + + // 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; + assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); - // Finally, delete the copy instruction. - li_->RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); - ++numPeep; + // AValNo is the value number in A that defines the copy, A3 in the example. + LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1); + 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) + return false; + MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def); + const TargetInstrDesc &TID = DefMI->getDesc(); + unsigned NewDstIdx; + if (!TID.isCommutable() || + !tii_->CommuteChangesDestination(DefMI, NewDstIdx)) + return false; + + MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); + unsigned NewReg = NewDstMO.getReg(); + if (NewReg != IntB.reg || !NewDstMO.isKill()) + return false; + + // Make sure there are no other definitions of IntB that would reach the + // uses which the new definition can reach. + if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) + return false; + + // At this point we have decided that it is legal to do this + // transformation. Start by commuting the instruction. + MachineBasicBlock *MBB = DefMI->getParent(); + MachineInstr *NewMI = tii_->commuteInstruction(DefMI); + if (!NewMI) + return false; + if (NewMI != DefMI) { + li_->ReplaceMachineInstrInMaps(DefMI, NewMI); + MBB->insert(DefMI, NewMI); + MBB->erase(DefMI); + } + unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg); + NewMI->getOperand(OpIdx).setIsKill(); + + // Update uses of IntA of the specific Val# with IntB. + bool BHasPHIKill = BValNo->hasPHIKill; + SmallVector BDeadValNos; + SmallVector BKills; + std::map BExtend; + for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), + UE = mri_->use_end(); UI != UE;) { + MachineOperand &UseMO = UI.getOperand(); + MachineInstr *UseMI = &*UI; + ++UI; + if (JoinedCopies.count(UseMI)) + continue; + unsigned UseIdx = li_->getInstructionIndex(UseMI); + LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); + if (ULR->valno != AValNo) + continue; + UseMO.setReg(NewReg); + if (UseMI == CopyMI) + continue; + if (UseMO.isKill()) + BKills.push_back(li_->getUseIndex(UseIdx)+1); + unsigned SrcReg, DstReg; + if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) + continue; + if (DstReg == IntB.reg) { + // This copy will become a noop. If it's defining a new val#, + // remove that val# as well. However this live range is being + // extended to the end of the existing live range defined by the copy. + unsigned DefIdx = li_->getDefIndex(UseIdx); + LiveInterval::iterator DLR = IntB.FindLiveRangeContaining(DefIdx); + BHasPHIKill |= DLR->valno->hasPHIKill; + assert(DLR->valno->def == DefIdx); + BDeadValNos.push_back(DLR->valno); + BExtend[DLR->start] = DLR->end; + JoinedCopies.insert(UseMI); + // If this is a kill but it's going to be removed, the last use + // of the same val# is the new kill. + if (UseMO.isKill()) { + BKills.pop_back(); + } + } + } + + // We need to insert a new liverange: [ALR.start, LastUse). It may be we can + // 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) + IntB.removeValNo(BDeadValNos[i]); + VNInfo *ValNo = IntB.getNextValue(ALR->start, 0, li_->getVNInfoAllocator()); + for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); + AI != AE; ++AI) { + if (AI->valno != AValNo) continue; + unsigned End = AI->end; + std::map::iterator EI = BExtend.find(End); + if (EI != BExtend.end()) + End = EI->second; + IntB.addRange(LiveRange(AI->start, End, ValNo)); + } + IntB.addKills(ValNo, BKills); + ValNo->hasPHIKill = BHasPHIKill; + + DOUT << " result = "; IntB.print(DOUT, tri_); + DOUT << "\n"; + + DOUT << "\nShortening: "; IntA.print(DOUT, tri_); + IntA.removeValNo(AValNo); + DOUT << " result = "; IntA.print(DOUT, tri_); + DOUT << "\n"; + + ++numCommutes; return true; } +/// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate +/// due to live range lengthening as the result of coalescing. +void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, + LiveInterval &LI) { + 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; + LiveInterval::const_iterator UI = LI.FindLiveRangeContaining(UseIdx); + assert(UI != LI.end()); + if (!LI.isKill(UI->valno, UseIdx+1)) + UseMO.setIsKill(false); + } + } +} + +/// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. +/// +bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, + unsigned DstReg) { + MachineBasicBlock *MBB = CopyMI->getParent(); + const MachineLoop *L = loopInfo->getLoopFor(MBB); + if (!L) + return false; + if (MBB != L->getLoopLatch()) + return false; + + LiveInterval &LI = li_->getInterval(DstReg); + unsigned DefIdx = li_->getInstructionIndex(CopyMI); + LiveInterval::const_iterator DstLR = + LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx)); + if (DstLR == LI.end()) + return false; + unsigned KillIdx = li_->getInstructionIndex(&MBB->back()) + InstrSlots::NUM; + if (DstLR->valno->kills.size() == 1 && + DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill) + return true; + return false; +} + +/// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and +/// update the subregister number if it is not zero. If DstReg is a +/// physical register and the existing subregister number of the def / use +/// being updated is not zero, make sure to set it to the correct physical +/// subregister. +void +SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, + unsigned SubIdx) { + bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); + if (DstIsPhys && SubIdx) { + // Figure out the real physical register we are updating with. + DstReg = tri_->getSubReg(DstReg, SubIdx); + SubIdx = 0; + } + + for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg), + E = mri_->reg_end(); I != E; ) { + MachineOperand &O = I.getOperand(); + ++I; + if (DstIsPhys) { + unsigned UseSubIdx = O.getSubReg(); + unsigned UseDstReg = DstReg; + if (UseSubIdx) + UseDstReg = tri_->getSubReg(DstReg, UseSubIdx); + O.setReg(UseDstReg); + O.setSubReg(0); + } else { + unsigned OldSubIdx = O.getSubReg(); + assert((!SubIdx || !OldSubIdx) && "Conflicting sub-register index!"); + if (SubIdx) + O.setSubReg(SubIdx); + O.setReg(DstReg); + } + } +} + /// 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, or if it is never possible -/// to coalesce this copy, due to register constraints. It returns -/// false if it is not currently possible to coalesce this interval, but -/// it may be possible if other things get coalesced. -bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, - unsigned SrcReg, unsigned DstReg, bool PhysOnly) { +/// if the copy was successfully coalesced away. If it is not currently +/// possible to coalesce this interval, but it may be possible if other +/// things get coalesced, then it returns true by reference in 'Again'. +bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { + MachineInstr *CopyMI = TheCopy.MI; + + Again = false; + if (JoinedCopies.count(CopyMI)) + return false; // Already done. + DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI; - // Get representative registers. - unsigned repSrcReg = rep(SrcReg); - unsigned repDstReg = rep(DstReg); - + unsigned SrcReg; + unsigned DstReg; + bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; + unsigned SubIdx = 0; + if (isExtSubReg) { + DstReg = CopyMI->getOperand(0).getReg(); + SrcReg = CopyMI->getOperand(1).getReg(); + } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) { + assert(0 && "Unrecognized copy instruction!"); + return false; + } + // If they are already joined we continue. - if (repSrcReg == repDstReg) { + if (SrcReg == DstReg) { DOUT << "\tCopy already coalesced.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } - bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); - bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg); - if (PhysOnly && !SrcIsPhys && !DstIsPhys) - // Only joining physical registers with virtual registers in this round. - return true; + bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); + bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); // If they are both physical registers, we cannot join them. if (SrcIsPhys && DstIsPhys) { DOUT << "\tCan not coalesce physregs.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } // We only join virtual registers with allocatable physical registers. - if (SrcIsPhys && !allocatableRegs_[repSrcReg]) { + if (SrcIsPhys && !allocatableRegs_[SrcReg]) { DOUT << "\tSrc reg is unallocatable physreg.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } - if (DstIsPhys && !allocatableRegs_[repDstReg]) { + if (DstIsPhys && !allocatableRegs_[DstReg]) { DOUT << "\tDst reg is unallocatable physreg.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } - - // If they are not of the same register class, we cannot join them. - if (differingRegisterClasses(repSrcReg, repDstReg)) { + + unsigned RealDstReg = 0; + if (isExtSubReg) { + SubIdx = CopyMI->getOperand(2).getImm(); + if (SrcIsPhys) { + // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be + // coalesced with AX. + SrcReg = tri_->getSubReg(SrcReg, SubIdx); + SubIdx = 0; + } else if (DstIsPhys) { + // 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. + const TargetRegisterClass *RC = mri_->getRegClass(SrcReg); + for (const unsigned *SRs = tri_->getSuperRegisters(DstReg); + unsigned SR = *SRs; ++SRs) { + if (DstReg == tri_->getSubReg(SR, SubIdx) && + RC->contains(SR)) { + RealDstReg = SR; + break; + } + } + assert(RealDstReg && "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. + 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 + } + SubIdx = 0; + } else { + unsigned SrcSize= li_->getInterval(SrcReg).getSize() / InstrSlots::NUM; + unsigned DstSize= li_->getInterval(DstReg).getSize() / InstrSlots::NUM; + const TargetRegisterClass *RC = mri_->getRegClass(DstReg); + 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 (DstSize > Threshold || SrcSize > Threshold) { + LiveVariables::VarInfo &svi = lv_->getVarInfo(SrcReg); + LiveVariables::VarInfo &dvi = lv_->getVarInfo(DstReg); + if ((float)dvi.NumUses / DstSize < (float)svi.NumUses / SrcSize) { + 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 + // 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"; - return true; // Not coalescable. + // 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; } - LiveInterval &SrcInt = li_->getInterval(repSrcReg); - LiveInterval &DstInt = li_->getInterval(repDstReg); - assert(SrcInt.reg == repSrcReg && DstInt.reg == repDstReg && + LiveInterval &SrcInt = li_->getInterval(SrcReg); + LiveInterval &DstInt = li_->getInterval(DstReg); + assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg && "Register mapping is horribly broken!"); - DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_); - DOUT << " and "; DstInt.print(DOUT, mri_); + DOUT << "\t\tInspecting "; SrcInt.print(DOUT, tri_); + DOUT << " and "; DstInt.print(DOUT, tri_); DOUT << ": "; // Check if it is necessary to propagate "isDead" property before intervals @@ -257,19 +612,20 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (SrcEnd > li_->getDefIndex(CopyIdx)) { isDead = false; } else { - MachineOperand *MOU; - MachineInstr *LastUse= lastRegisterUse(SrcStart, CopyIdx, repSrcReg, MOU); + unsigned LastUseIdx; + MachineOperand *LastUse = + lastRegisterUse(SrcStart, CopyIdx, SrcReg, LastUseIdx); if (LastUse) { // Shorten the liveinterval to the end of last use. - MOU->setIsKill(); + LastUse->setIsKill(); isDead = false; isShorten = true; - RemoveStart = li_->getDefIndex(li_->getInstructionIndex(LastUse)); - RemoveEnd = SrcEnd; + RemoveStart = li_->getDefIndex(LastUseIdx); + RemoveEnd = SrcEnd; } else { MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart); if (SrcMI) { - MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); + MachineOperand *mops = findDefOperand(SrcMI, SrcReg); if (mops) // A dead def should have a single cycle interval. ++RemoveStart; @@ -282,14 +638,16 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // virtual register. Once the coalescing is done, it cannot be broken and // these are not spillable! If the destination interval uses are far away, // think twice about coalescing them! - if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) { + if (!mopd->isDead() && (SrcIsPhys || DstIsPhys) && !isExtSubReg) { LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; - unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg; - unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg; - const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg); - unsigned Threshold = allocatableRCRegs_[RC].count(); - - // If the virtual register live interval is long has it has low use desity, + 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 = JoinVInt.getSize() / InstrSlots::NUM; @@ -299,6 +657,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, JoinVInt.preference = JoinPReg; ++numAborts; DOUT << "\tMay tie down a physical register, abort!\n"; + Again = true; // May be possible to coalesce later. return false; } } @@ -312,15 +671,15 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (isDead) { // Result of the copy is dead. Propagate this property. if (SrcStart == 0) { - assert(MRegisterInfo::isPhysicalRegister(repSrcReg) && + assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) && "Live-in must be a physical register!"); // Live-in to the function but dead. Remove it from entry live-in set. // JoinIntervals may end up swapping the two intervals. - mf_->begin()->removeLiveIn(repSrcReg); + mf_->begin()->removeLiveIn(SrcReg); } else { MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart); if (SrcMI) { - MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); + MachineOperand *mops = findDefOperand(SrcMI, SrcReg); if (mops) mops->setIsDead(); } @@ -330,67 +689,125 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (isShorten || isDead) { // Shorten the destination live interval. if (Swapped) - SrcInt.removeRange(RemoveStart, RemoveEnd); + SrcInt.removeRange(RemoveStart, RemoveEnd, true); } } else { // Coalescing failed. // If we can eliminate the copy without merging the live ranges, do so now. - if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI)) + if (!isExtSubReg && + (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) || + RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) { + JoinedCopies.insert(CopyMI); return true; - + } + // Otherwise, we are unable to join the intervals. DOUT << "Interference!\n"; + Again = true; // May be possible to coalesce later. return false; } LiveInterval *ResSrcInt = &SrcInt; LiveInterval *ResDstInt = &DstInt; if (Swapped) { - std::swap(repSrcReg, repDstReg); + std::swap(SrcReg, DstReg); std::swap(ResSrcInt, ResDstInt); } - assert(MRegisterInfo::isVirtualRegister(repSrcReg) && + assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && "LiveInterval::join didn't work right!"); // If we're about to merge live ranges into a physical register live range, // we have to update any aliased register's live ranges to indicate that they // have clobbered values for this range. - if (MRegisterInfo::isPhysicalRegister(repDstReg)) { + if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { // Unset unnecessary kills. if (!ResDstInt->containsOneValue()) { for (LiveInterval::Ranges::const_iterator I = ResSrcInt->begin(), E = ResSrcInt->end(); I != E; ++I) - unsetRegisterKills(I->start, I->end, repDstReg); + unsetRegisterKills(I->start, I->end, DstReg); + } + + // 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. + if (RealDstReg) { + LiveInterval &RealDstInt = li_->getOrCreateInterval(RealDstReg); + SmallSet CopiedValNos; + for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(), + E = ResSrcInt->ranges.end(); I != E; ++I) { + LiveInterval::const_iterator DstLR = + ResDstInt->FindLiveRangeContaining(I->start); + assert(DstLR != ResDstInt->end() && "Invalid joined interval!"); + const VNInfo *DstValNo = DstLR->valno; + if (CopiedValNos.insert(DstValNo)) { + VNInfo *ValNo = RealDstInt.getNextValue(DstValNo->def, DstValNo->copy, + li_->getVNInfoAllocator()); + ValNo->hasPHIKill = DstValNo->hasPHIKill; + RealDstInt.addKills(ValNo, DstValNo->kills); + RealDstInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo); + } + } + DstReg = RealDstReg; } // Update the liveintervals of sub-registers. - for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS) - li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt); + for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS) + li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt, + li_->getVNInfoAllocator()); } else { // Merge use info if the destination is a virtual register. - LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); - LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg); + LiveVariables::VarInfo& dVI = lv_->getVarInfo(DstReg); + LiveVariables::VarInfo& sVI = lv_->getVarInfo(SrcReg); dVI.NumUses += sVI.NumUses; } - DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_); + // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the + // larger super-register. + if (isExtSubReg && !SrcIsPhys && !DstIsPhys) { + if (!Swapped) { + ResSrcInt->Copy(*ResDstInt, li_->getVNInfoAllocator()); + std::swap(SrcReg, DstReg); + std::swap(ResSrcInt, ResDstInt); + } + } + + 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) + continue; + MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); + unsigned NewSrcReg, NewDstReg; + if (CopyMI && + JoinedCopies.count(CopyMI) == 0 && + tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg)) { + unsigned LoopDepth = loopInfo->getLoopDepth(CopyMI->getParent()); + JoinQueue->push(CopyRec(CopyMI, LoopDepth, + isBackEdgeCopy(CopyMI, DstReg))); + } + } + } + + DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, tri_); DOUT << "\n"; - // Remember these liveintervals have been joined. - JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister); - if (MRegisterInfo::isVirtualRegister(repDstReg)) - JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister); + // Remember to delete the copy instruction. + JoinedCopies.insert(CopyMI); + + // Some live range has been lengthened due to colaescing, eliminate the + // unnecessary kills. + RemoveUnnecessaryKills(SrcReg, *ResDstInt); + if (TargetRegisterInfo::isVirtualRegister(DstReg)) + RemoveUnnecessaryKills(DstReg, *ResDstInt); - // repSrcReg is guarateed to be the register whose live interval that is + // SrcReg is guarateed to be the register whose live interval that is // being merged. - li_->removeInterval(repSrcReg); - r2rMap_[repSrcReg] = repDstReg; + li_->removeInterval(SrcReg); + UpdateRegDefsUses(SrcReg, DstReg, SubIdx); - // Finally, delete the copy instruction. - li_->RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); - ++numPeep; ++numJoins; return true; } @@ -455,7 +872,7 @@ static bool InVector(VNInfo *Val, const SmallVector &V) { /// value number and that the RHS is not defined by a copy from this /// interval. This returns false if the intervals are not joinable, or it /// joins them and returns true. -bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) { +bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ assert(RHS.containsOneValue()); // Some number (potentially more than one) value numbers in the current @@ -493,8 +910,8 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // If we haven't already recorded that this value # is safe, check it. if (!InVector(LHSIt->valno, EliminatedLHSVals)) { // Copy from the RHS? - unsigned SrcReg = LHSIt->valno->reg; - if (rep(SrcReg) != RHS.reg) + unsigned SrcReg = li_->getVNInfoSourceReg(LHSIt->valno); + if (SrcReg != RHS.reg) return false; // Nope, bail out. EliminatedLHSVals.push_back(LHSIt->valno); @@ -521,7 +938,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) } else { // Otherwise, if this is a copy from the RHS, mark it as being merged // in. - if (rep(LHSIt->valno->reg) == RHS.reg) { + if (li_->getVNInfoSourceReg(LHSIt->valno) == RHS.reg) { EliminatedLHSVals.push_back(LHSIt->valno); // We know this entire LHS live range is okay, so skip it now. @@ -564,13 +981,14 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // Okay, now that there is a single LHS value number that we're merging the // RHS into, update the value number info for the LHS to indicate that the // value number is defined where the RHS value number was. - const VNInfo *VNI = RHS.getFirstValNumInfo(); - LHSValNo->def = VNI->def; - LHSValNo->reg = VNI->reg; + const VNInfo *VNI = RHS.getValNumInfo(0); + LHSValNo->def = VNI->def; + LHSValNo->copy = VNI->copy; // Okay, the final step is to loop over the RHS live intervals, adding them to // the LHS. - LHS.addKills(*LHSValNo, VNI->kills); + LHSValNo->hasPHIKill |= VNI->hasPHIKill; + LHS.addKills(LHSValNo, VNI->kills); LHS.MergeRangesInAsValue(RHS, LHSValNo); LHS.weight += RHS.weight; if (RHS.preference && !LHS.preference) @@ -597,20 +1015,20 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, // 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 (MRegisterInfo::isPhysicalRegister(LHS.reg) && - *mri_->getSubRegisters(LHS.reg)) { - for (const unsigned* SR = mri_->getSubRegisters(LHS.reg); *SR; ++SR) + 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, mri_)); + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); return false; } - } else if (MRegisterInfo::isPhysicalRegister(RHS.reg) && - *mri_->getSubRegisters(RHS.reg)) { - for (const unsigned* SR = mri_->getSubRegisters(RHS.reg); *SR; ++SR) + } 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, mri_)); + DEBUG(li_->getInterval(*SR).print(DOUT, tri_)); return false; } } @@ -625,13 +1043,13 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, int RHSVal0DefinedFromLHS = -1; int RHSValID = -1; VNInfo *RHSValNoInfo = NULL; - VNInfo *RHSValNoInfo0 = RHS.getFirstValNumInfo(); - unsigned RHSSrcReg = RHSValNoInfo0->reg; - if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { + VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0); + unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0); + 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. - if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) { + if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { return SimpleJoin(LHS, RHS); } else { RHSValNoInfo = RHSValNoInfo0; @@ -653,8 +1071,8 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, i != e; ++i) { VNInfo *VNI = *i; unsigned VN = VNI->id; - if (unsigned LHSSrcReg = VNI->reg) { - if (rep(LHSSrcReg) != RHS.reg) { + if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) { + if (LHSSrcReg != RHS.reg) { // If this is not a copy from the RHS, its value number will be // unmodified by the coalescing. NewVNInfo[VN] = VNI; @@ -692,17 +1110,16 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); i != e; ++i) { VNInfo *VNI = *i; - unsigned ValSrcReg = VNI->reg; - if (ValSrcReg == 0) // Src not defined by a copy? + if (VNI->def == ~1U || VNI->copy == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the LHS interval. If the src is // from the RHS interval, we can use its value #. - if (rep(ValSrcReg) != RHS.reg) + if (li_->getVNInfoSourceReg(VNI) != RHS.reg) continue; // Figure out the value # from the RHS. - LHSValsDefinedFromRHS[VNI] = RHS.getLiveRangeContaining(VNI->def-1)->valno; + LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno; } // Loop over the value numbers of the RHS, seeing if any are defined from @@ -710,17 +1127,16 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); i != e; ++i) { VNInfo *VNI = *i; - unsigned ValSrcReg = VNI->reg; - if (ValSrcReg == 0) // Src not defined by a copy? + if (VNI->def == ~1U || VNI->copy == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the RHS interval. If the src is // from the LHS interval, we can use its value #. - if (rep(ValSrcReg) != LHS.reg) + if (li_->getVNInfoSourceReg(VNI) != LHS.reg) continue; // Figure out the value # from the LHS. - RHSValsDefinedFromLHS[VNI]= LHS.getLiveRangeContaining(VNI->def-1)->valno; + RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); @@ -799,32 +1215,34 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, } } + // Update kill info. Some live ranges are extended due to copy coalescing. + for (DenseMap::iterator I = LHSValsDefinedFromRHS.begin(), + E = LHSValsDefinedFromRHS.end(); I != E; ++I) { + VNInfo *VNI = I->first; + unsigned LHSValID = LHSValNoAssignments[VNI->id]; + LiveInterval::removeKill(NewVNInfo[LHSValID], VNI->def); + NewVNInfo[LHSValID]->hasPHIKill |= VNI->hasPHIKill; + RHS.addKills(NewVNInfo[LHSValID], VNI->kills); + } + + // Update kill info. Some live ranges are extended due to copy coalescing. + for (DenseMap::iterator I = RHSValsDefinedFromLHS.begin(), + E = RHSValsDefinedFromLHS.end(); I != E; ++I) { + VNInfo *VNI = I->first; + unsigned RHSValID = RHSValNoAssignments[VNI->id]; + LiveInterval::removeKill(NewVNInfo[RHSValID], VNI->def); + NewVNInfo[RHSValID]->hasPHIKill |= VNI->hasPHIKill; + LHS.addKills(NewVNInfo[RHSValID], VNI->kills); + } + // If we get here, we know that we can coalesce the live ranges. Ask the // intervals to coalesce themselves now. if ((RHS.ranges.size() > LHS.ranges.size() && - MRegisterInfo::isVirtualRegister(LHS.reg)) || - MRegisterInfo::isPhysicalRegister(RHS.reg)) { - // Update kill info. Some live ranges are extended due to copy coalescing. - for (DenseMap::iterator I = LHSValsDefinedFromRHS.begin(), - E = LHSValsDefinedFromRHS.end(); I != E; ++I) { - VNInfo *VNI = I->first; - unsigned LHSValID = LHSValNoAssignments[VNI->id]; - LiveInterval::removeKill(*NewVNInfo[LHSValID], VNI->def); - RHS.addKills(*NewVNInfo[LHSValID], VNI->kills); - } - + TargetRegisterInfo::isVirtualRegister(LHS.reg)) || + TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo); Swapped = true; } else { - // Update kill info. Some live ranges are extended due to copy coalescing. - for (DenseMap::iterator I = RHSValsDefinedFromLHS.begin(), - E = RHSValsDefinedFromLHS.end(); I != E; ++I) { - VNInfo *VNI = I->first; - unsigned RHSValID = RHSValNoAssignments[VNI->id]; - LiveInterval::removeKill(*NewVNInfo[RHSValID], VNI->def); - LHS.addKills(*NewVNInfo[RHSValID], VNI->kills); - } - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo); Swapped = false; } @@ -844,36 +1262,88 @@ namespace { }; } +/// getRepIntervalSize - Returns the size of the interval that represents the +/// specified register. +template +unsigned JoinPriorityQueue::getRepIntervalSize(unsigned Reg) { + return Rc->getRepIntervalSize(Reg); +} + +/// CopyRecSort::operator - Join priority queue sorting function. +/// +bool CopyRecSort::operator()(CopyRec left, CopyRec right) const { + // Inner loops first. + if (left.LoopDepth > right.LoopDepth) + return false; + else if (left.LoopDepth == right.LoopDepth) + if (left.isBackEdge && !right.isBackEdge) + return false; + return true; +} + void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, - std::vector *TryAgain, bool PhysOnly) { + std::vector &TryAgain) { DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; - + + std::vector VirtCopies; + std::vector PhysCopies; + unsigned LoopDepth = loopInfo->getLoopDepth(MBB); for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); MII != E;) { MachineInstr *Inst = MII++; - // If this isn't a copy, we can't join intervals. + // If this isn't a copy nor a extract_subreg, we can't join intervals. unsigned SrcReg, DstReg; - if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue; - - if (TryAgain && !JoinCopy(Inst, SrcReg, DstReg, PhysOnly)) - TryAgain->push_back(getCopyRec(Inst, SrcReg, DstReg)); + if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { + DstReg = Inst->getOperand(0).getReg(); + SrcReg = Inst->getOperand(1).getReg(); + } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) + continue; + + bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); + bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); + if (NewHeuristic) { + JoinQueue->push(CopyRec(Inst, LoopDepth, isBackEdgeCopy(Inst, DstReg))); + } else { + if (SrcIsPhys || DstIsPhys) + PhysCopies.push_back(CopyRec(Inst, 0, false)); + else + VirtCopies.push_back(CopyRec(Inst, 0, false)); + } + } + + if (NewHeuristic) + return; + + // Try coalescing physical register + virtual register first. + for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { + CopyRec &TheCopy = PhysCopies[i]; + bool Again = false; + if (!JoinCopy(TheCopy, Again)) + if (Again) + TryAgain.push_back(TheCopy); + } + for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { + CopyRec &TheCopy = VirtCopies[i]; + bool Again = false; + if (!JoinCopy(TheCopy, Again)) + if (Again) + TryAgain.push_back(TheCopy); } } void SimpleRegisterCoalescing::joinIntervals() { DOUT << "********** JOINING INTERVALS ***********\n"; - JoinedLIs.resize(li_->getNumIntervals()); - JoinedLIs.reset(); + if (NewHeuristic) + JoinQueue = new JoinPriorityQueue(this); std::vector TryAgainList; - const LoopInfo &LI = getAnalysis(); - if (LI.begin() == LI.end()) { + if (loopInfo->begin() == loopInfo->end()) { // 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) - CopyCoalesceInMBB(I, &TryAgainList); + CopyCoalesceInMBB(I, TryAgainList); } else { // Otherwise, join intervals in inner loops before other intervals. // Unfortunately we can't just iterate over loop hierarchy here because @@ -882,91 +1352,107 @@ void SimpleRegisterCoalescing::joinIntervals() { // Join intervals in the function prolog first. We want to join physical // registers with virtual registers before the intervals got too long. std::vector > MBBs; - for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E;++I) - MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); + for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){ + MachineBasicBlock *MBB = I; + MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I)); + } // Sort by loop depth. std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); // Finally, join intervals in loop nest order. for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - CopyCoalesceInMBB(MBBs[i].second, NULL, true); - for (unsigned i = 0, e = MBBs.size(); i != e; ++i) - CopyCoalesceInMBB(MBBs[i].second, &TryAgainList, false); + CopyCoalesceInMBB(MBBs[i].second, TryAgainList); } // Joining intervals can allow other intervals to be joined. Iteratively join // until we make no progress. - bool ProgressMade = true; - while (ProgressMade) { - ProgressMade = false; - - for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { - CopyRec &TheCopy = TryAgainList[i]; - if (TheCopy.MI && - JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) { - TheCopy.MI = 0; // Mark this one as done. - ProgressMade = true; + if (NewHeuristic) { + SmallVector TryAgain; + bool ProgressMade = true; + while (ProgressMade) { + ProgressMade = false; + while (!JoinQueue->empty()) { + CopyRec R = JoinQueue->pop(); + bool Again = false; + bool Success = JoinCopy(R, Again); + if (Success) + ProgressMade = true; + else if (Again) + TryAgain.push_back(R); } - } - } - // Some live range has been lengthened due to colaescing, eliminate the - // unnecessary kills. - int RegNum = JoinedLIs.find_first(); - while (RegNum != -1) { - unsigned Reg = RegNum + MRegisterInfo::FirstVirtualRegister; - unsigned repReg = rep(Reg); - LiveInterval &LI = li_->getInterval(repReg); - LiveVariables::VarInfo& svi = lv_->getVarInfo(Reg); - for (unsigned i = 0, e = svi.Kills.size(); i != e; ++i) { - MachineInstr *Kill = svi.Kills[i]; - // Suppose vr1 = op vr2, x - // and vr1 and vr2 are coalesced. vr2 should still be marked kill - // unless it is a two-address operand. - if (li_->isRemoved(Kill) || hasRegisterDef(Kill, repReg)) - continue; - if (LI.liveAt(li_->getInstructionIndex(Kill) + InstrSlots::NUM)) - unsetRegisterKill(Kill, repReg); + if (ProgressMade) { + while (!TryAgain.empty()) { + JoinQueue->push(TryAgain.back()); + TryAgain.pop_back(); + } + } } - RegNum = JoinedLIs.find_next(RegNum); - } - - DOUT << "*** Register mapping ***\n"; - for (int i = 0, e = r2rMap_.size(); i != e; ++i) - if (r2rMap_[i]) { - DOUT << " reg " << i << " -> "; - DEBUG(printRegName(r2rMap_[i])); - DOUT << "\n"; + } else { + bool ProgressMade = true; + while (ProgressMade) { + ProgressMade = false; + + for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { + CopyRec &TheCopy = TryAgainList[i]; + if (TheCopy.MI) { + bool Again = false; + bool Success = JoinCopy(TheCopy, Again); + if (Success || !Again) { + TheCopy.MI = 0; // Mark this one as done. + ProgressMade = true; + } + } + } } + } + + if (NewHeuristic) + delete JoinQueue; } /// 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 { + unsigned RegB) const { // Get the register classes for the first reg. - if (MRegisterInfo::isPhysicalRegister(RegA)) { - assert(MRegisterInfo::isVirtualRegister(RegB) && + if (TargetRegisterInfo::isPhysicalRegister(RegA)) { + assert(TargetRegisterInfo::isVirtualRegister(RegB) && "Shouldn't consider two physregs!"); - return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); + return !mri_->getRegClass(RegB)->contains(RegA); } // Compare against the regclass for the second reg. - const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); - if (MRegisterInfo::isVirtualRegister(RegB)) - return RegClass != mf_->getSSARegMap()->getRegClass(RegB); + const TargetRegisterClass *RegClass = mri_->getRegClass(RegA); + if (TargetRegisterInfo::isVirtualRegister(RegB)) + return RegClass != mri_->getRegClass(RegB); else return !RegClass->contains(RegB); } /// lastRegisterUse - Returns the last use of the specific register between -/// cycles Start and End. It also returns the use operand by reference. It -/// returns NULL if there are no uses. -MachineInstr * -SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, - MachineOperand *&MOU) { +/// cycles Start and End or NULL if there are no uses. +MachineOperand * +SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, + unsigned Reg, unsigned &UseIdx) const{ + UseIdx = 0; + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + MachineOperand *LastUse = NULL; + for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg), + E = mri_->use_end(); I != E; ++I) { + MachineOperand &Use = I.getOperand(); + MachineInstr *UseMI = Use.getParent(); + unsigned Idx = li_->getInstructionIndex(UseMI); + if (Idx >= Start && Idx < End && Idx >= UseIdx) { + LastUse = &Use; + UseIdx = Idx; + } + } + return LastUse; + } + int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; int s = Start; while (e >= s) { @@ -980,11 +1466,11 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, unsigned return NULL; for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isUse() && MO.getReg() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) { - MOU = &MO; - return MI; + MachineOperand &Use = MI->getOperand(i); + if (Use.isRegister() && Use.isUse() && Use.getReg() && + tri_->regsOverlap(Use.getReg(), Reg)) { + UseIdx = e; + return &Use; } } @@ -997,31 +1483,21 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End, unsigned /// findDefOperand - Returns the MachineOperand that is a def of the specific /// register. It returns NULL if the def is not found. -MachineOperand *SimpleRegisterCoalescing::findDefOperand(MachineInstr *MI, unsigned Reg) { +MachineOperand *SimpleRegisterCoalescing::findDefOperand(MachineInstr *MI, + unsigned Reg) const { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) + if (MO.isRegister() && MO.isDef() && + tri_->regsOverlap(MO.getReg(), Reg)) return &MO; } return NULL; } -/// unsetRegisterKill - Unset IsKill property of all uses of specific register -/// of the specific instruction. -void SimpleRegisterCoalescing::unsetRegisterKill(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isKill() && MO.getReg() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) - MO.unsetIsKill(); - } -} - /// unsetRegisterKills - Unset IsKill property of all uses of specific register /// between cycles Start and End. void SimpleRegisterCoalescing::unsetRegisterKills(unsigned Start, unsigned End, - unsigned Reg) { + unsigned Reg) { int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; int s = Start; while (e >= s) { @@ -1036,9 +1512,9 @@ void SimpleRegisterCoalescing::unsetRegisterKills(unsigned Start, unsigned End, for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isKill() && MO.getReg() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) { - MO.unsetIsKill(); + if (MO.isRegister() && MO.isKill() && MO.getReg() && + tri_->regsOverlap(MO.getReg(), Reg)) { + MO.setIsKill(false); } } @@ -1046,28 +1522,15 @@ void SimpleRegisterCoalescing::unsetRegisterKills(unsigned Start, unsigned End, } } -/// hasRegisterDef - True if the instruction defines the specific register. -/// -bool SimpleRegisterCoalescing::hasRegisterDef(MachineInstr *MI, unsigned Reg) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isReg() && MO.isDef() && - mri_->regsOverlap(rep(MO.getReg()), Reg)) - return true; - } - return false; -} - void SimpleRegisterCoalescing::printRegName(unsigned reg) const { - if (MRegisterInfo::isPhysicalRegister(reg)) - cerr << mri_->getName(reg); + if (TargetRegisterInfo::isPhysicalRegister(reg)) + cerr << tri_->getName(reg); else cerr << "%reg" << reg; } void SimpleRegisterCoalescing::releaseMemory() { - r2rMap_.clear(); - JoinedLIs.clear(); + JoinedCopies.clear(); } static bool isZeroLengthInterval(LiveInterval *li) { @@ -1080,59 +1543,65 @@ static bool isZeroLengthInterval(LiveInterval *li) { bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; + mri_ = &fn.getRegInfo(); tm_ = &fn.getTarget(); - mri_ = tm_->getRegisterInfo(); + tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); li_ = &getAnalysis(); lv_ = &getAnalysis(); + loopInfo = &getAnalysis(); DOUT << "********** SIMPLE REGISTER COALESCING **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'; - allocatableRegs_ = mri_->getAllocatableSet(fn); - for (MRegisterInfo::regclass_iterator I = mri_->regclass_begin(), - E = mri_->regclass_end(); I != E; ++I) - allocatableRCRegs_.insert(std::make_pair(*I,mri_->getAllocatableSet(fn, *I))); - - r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); + allocatableRegs_ = tri_->getAllocatableSet(fn); + for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(), + E = tri_->regclass_end(); I != E; ++I) + allocatableRCRegs_.insert(std::make_pair(*I, + tri_->getAllocatableSet(fn, *I))); // 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, mri_); + 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, coalesce virtual registers and remove identity moves. - const LoopInfo &loopInfo = getAnalysis(); + // Delete all coalesced copies. + for (SmallPtrSet::iterator I = JoinedCopies.begin(), + E = JoinedCopies.end(); I != E; ++I) { + li_->RemoveMachineInstrFromMaps(*I); + (*I)->eraseFromParent(); + ++numPeep; + } + } + // Perform a final pass over the instructions and compute spill weights + // and remove identity moves. for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { MachineBasicBlock* mbb = mbbi; - unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); + unsigned loopDepth = loopInfo->getLoopDepth(mbb); for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); mii != mie; ) { // if the move will be an identity move delete it - unsigned srcReg, dstReg, RegRep; - if (tii_->isMoveInstr(*mii, srcReg, dstReg) && - (RegRep = rep(srcReg)) == rep(dstReg)) { + unsigned srcReg, dstReg; + if (tii_->isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) { // remove from def list - LiveInterval &RegInt = li_->getOrCreateInterval(RegRep); + LiveInterval &RegInt = li_->getOrCreateInterval(srcReg); MachineOperand *MO = mii->findRegisterDefOperand(dstReg); // If def of this move instruction is dead, remove its live range from // the dstination register's live interval. if (MO->isDead()) { unsigned MoveIdx = li_->getDefIndex(li_->getInstructionIndex(mii)); LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx); - RegInt.removeRange(MLR->start, MoveIdx+1); + RegInt.removeRange(MLR->start, MoveIdx+1, true); if (RegInt.empty()) - li_->removeInterval(RegRep); + li_->removeInterval(srcReg); } li_->RemoveMachineInstrFromMaps(mii); mii = mbbi->erase(mii); @@ -1142,18 +1611,15 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { const MachineOperand &mop = mii->getOperand(i); if (mop.isRegister() && mop.getReg() && - MRegisterInfo::isVirtualRegister(mop.getReg())) { - // replace register with representative register - unsigned reg = rep(mop.getReg()); - mii->getOperand(i).setReg(reg); - + TargetRegisterInfo::isVirtualRegister(mop.getReg())) { + unsigned reg = mop.getReg(); // Multiple uses of reg by the same instruction. It should not // contribute to spill weight again. if (UniqueUses.count(reg) != 0) continue; LiveInterval &RegInt = li_->getInterval(reg); - float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth); - RegInt.weight += w; + RegInt.weight += + li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth); UniqueUses.insert(reg); } } @@ -1164,12 +1630,26 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) { LiveInterval &LI = I->second; - if (MRegisterInfo::isVirtualRegister(LI.reg)) { + 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 // it and hope it will be easier to allocate for this li. if (isZeroLengthInterval(&LI)) LI.weight = HUGE_VALF; + else { + bool isLoad = false; + if (li_->isReMaterializable(LI, 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. + // FIXME: this gets much more complicated once we support non-trivial + // re-materialization. + if (isLoad) + LI.weight *= 0.9F; + else + LI.weight *= 0.5F; + } + } // Slightly prefer live interval that has been assigned a preferred reg. if (LI.preference) @@ -1190,3 +1670,10 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { void SimpleRegisterCoalescing::print(std::ostream &O, const Module* m) const { li_->print(O, m); } + +RegisterCoalescer* llvm::createSimpleRegisterCoalescer() { + return new SimpleRegisterCoalescing(); +} + +// Make sure that anything that uses RegisterCoalescer pulls in this file... +DEFINING_FILE_FOR(SimpleRegisterCoalescing)