X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=7c512ed368a8669d088ceb64c8daa984987caf96;hb=420cdebbcb95f3881ab3518fd3bb670837669e43;hp=e71b9d4c0f810a14fef17831c6bdba1e36fcf017;hpb=ccb36a4f1bcafdf0de8514e396a5d2acf29d3947;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index e71b9d4c0f8..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,42 +93,39 @@ 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 // the example above. LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); - unsigned BValNo = BLR->ValId; + 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. - unsigned BValNoDefIdx = IntB.getDefForValNum(BValNo); - if (!IntB.getSrcRegForValNum(BValNo)) return false; - assert(BValNoDefIdx == 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); - unsigned AValNo = AValLR->ValId; - - // 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 = IntA.getSrcRegForValNum(AValNo); + 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. - unsigned AValNoInstIdx = IntA.getDefForValNum(AValNo); - LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1); + LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1); // Make sure that the end of the live range is inside the same block as // CopyMI. @@ -125,15 +137,28 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte // live-range starts. If there are no intervening live ranges between them in // IntB, we can merge them. if (ValLR+1 != BLR) return false; + + // If a live interval is a physical register, conservatively check if any + // of its sub-registers is overlapping the live interval of the virtual + // register. If so, do not coalesce. + if (TargetRegisterInfo::isPhysicalRegister(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, 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 #. - IntB.setDefForValNum(BValNo, FillerStart); - IntB.setSrcRegForValNum(BValNo, 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 @@ -142,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->ValId) - IntB.MergeValueNumberInto(BValNo, ValLR->ValId); - DOUT << " result = "; IntB.print(DOUT, mri_); + if (BValNo != ValLR->valno) + IntB.MergeValueNumberInto(BValNo, ValLR->valno); + DOUT << " result = "; IntB.print(DOUT, tri_); DOUT << "\n"; // If the source instruction was killing the source register before the // merge, unset the isKill marker given the live range has been extended. int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); if (UIdx != -1) - 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 @@ -246,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; @@ -271,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; @@ -288,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; } } @@ -296,19 +666,20 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // Otherwise, if one of the intervals being joined is a physreg, this method // always canonicalizes DstInt to be it. The output "SrcInt" will not have // been modified, so we can use this information below to update aliases. - if (JoinIntervals(DstInt, SrcInt)) { + bool Swapped = false; + if (JoinIntervals(DstInt, SrcInt, Swapped)) { 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(); } @@ -317,69 +688,126 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, if (isShorten || isDead) { // Shorten the destination live interval. - if (repSrcReg == DstInt.reg) - DstInt.removeRange(RemoveStart, RemoveEnd); + if (Swapped) + 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; } - bool Swapped = repSrcReg == DstInt.reg; - if (Swapped) - std::swap(repSrcReg, repDstReg); - assert(MRegisterInfo::isVirtualRegister(repSrcReg) && + LiveInterval *ResSrcInt = &SrcInt; + LiveInterval *ResDstInt = &DstInt; + if (Swapped) { + std::swap(SrcReg, DstReg); + std::swap(ResSrcInt, ResDstInt); + } + 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 (!DstInt.containsOneValue()) { - for (LiveInterval::Ranges::const_iterator I = SrcInt.begin(), - E = SrcInt.end(); I != E; ++I) - unsetRegisterKills(I->start, I->end, repDstReg); + if (!ResDstInt->containsOneValue()) { + for (LiveInterval::Ranges::const_iterator I = ResSrcInt->begin(), + E = ResSrcInt->end(); I != E; ++I) + 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(SrcInt); + 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 = "; DstInt.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); - // If the intervals were swapped by Join, swap them back so that the register - // mapping (in the r2i map) is correct. - if (Swapped) SrcInt.swap(DstInt); + // 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; } @@ -399,43 +827,43 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, /// ThisFromOther[x] - If x is defined as a copy from the other interval, this /// contains the value number the copy is from. /// -static unsigned ComputeUltimateVN(unsigned VN, - SmallVector &ValueNumberInfo, - SmallVector &ThisFromOther, - SmallVector &OtherFromThis, +static unsigned ComputeUltimateVN(VNInfo *VNI, + SmallVector &NewVNInfo, + DenseMap &ThisFromOther, + DenseMap &OtherFromThis, SmallVector &ThisValNoAssignments, - SmallVector &OtherValNoAssignments, - LiveInterval &ThisLI, LiveInterval &OtherLI) { + SmallVector &OtherValNoAssignments) { + unsigned VN = VNI->id; + // If the VN has already been computed, just return it. if (ThisValNoAssignments[VN] >= 0) return ThisValNoAssignments[VN]; // assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); - + // If this val is not a copy from the other val, then it must be a new value // number in the destination. - int OtherValNo = ThisFromOther[VN]; - if (OtherValNo == -1) { - ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); - return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; + DenseMap::iterator I = ThisFromOther.find(VNI); + if (I == ThisFromOther.end()) { + NewVNInfo.push_back(VNI); + return ThisValNoAssignments[VN] = NewVNInfo.size()-1; } + VNInfo *OtherValNo = I->second; // Otherwise, this *is* a copy from the RHS. If the other side has already // been computed, return it. - if (OtherValNoAssignments[OtherValNo] >= 0) - return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo]; + if (OtherValNoAssignments[OtherValNo->id] >= 0) + return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; // Mark this value number as currently being computed, then ask what the // ultimate value # of the other value is. ThisValNoAssignments[VN] = -2; unsigned UltimateVN = - ComputeUltimateVN(OtherValNo, ValueNumberInfo, - OtherFromThis, ThisFromOther, - OtherValNoAssignments, ThisValNoAssignments, - OtherLI, ThisLI); + ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, + OtherValNoAssignments, ThisValNoAssignments); return ThisValNoAssignments[VN] = UltimateVN; } -static bool InVector(unsigned Val, const SmallVector &V) { +static bool InVector(VNInfo *Val, const SmallVector &V) { return std::find(V.begin(), V.end(), Val) != V.end(); } @@ -444,7 +872,7 @@ static bool InVector(unsigned 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 @@ -464,7 +892,7 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) if (RHSIt != RHS.begin()) --RHSIt; } - SmallVector EliminatedLHSVals; + SmallVector EliminatedLHSVals; while (1) { // Determine if these live intervals overlap. @@ -480,13 +908,13 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // coalesce these live ranges and we bail out. if (Overlaps) { // If we haven't already recorded that this value # is safe, check it. - if (!InVector(LHSIt->ValId, EliminatedLHSVals)) { + if (!InVector(LHSIt->valno, EliminatedLHSVals)) { // Copy from the RHS? - unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId); - if (rep(SrcReg) != RHS.reg) + unsigned SrcReg = li_->getVNInfoSourceReg(LHSIt->valno); + if (SrcReg != RHS.reg) return false; // Nope, bail out. - EliminatedLHSVals.push_back(LHSIt->ValId); + EliminatedLHSVals.push_back(LHSIt->valno); } // We know this entire LHS live range is okay, so skip it now. @@ -503,15 +931,15 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // want to notice this copy (so that it gets coalesced away) even though // the live ranges don't actually overlap. if (LHSIt->start == RHSIt->end) { - if (InVector(LHSIt->ValId, EliminatedLHSVals)) { + if (InVector(LHSIt->valno, EliminatedLHSVals)) { // We already know that this value number is going to be merged in // if coalescing succeeds. Just skip the liverange. if (++LHSIt == LHSEnd) break; } else { // Otherwise, if this is a copy from the RHS, mark it as being merged // in. - if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) { - EliminatedLHSVals.push_back(LHSIt->ValId); + 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. if (++LHSIt == LHSEnd) break; @@ -529,13 +957,13 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) // optimize for it: if there is more than one value, we merge them all into // the lowest numbered one, then handle the interval as if we were merging // with one value number. - unsigned LHSValNo; + VNInfo *LHSValNo; if (EliminatedLHSVals.size() > 1) { // Loop through all the equal value numbers merging them into the smallest // one. - unsigned Smallest = EliminatedLHSVals[0]; + VNInfo *Smallest = EliminatedLHSVals[0]; for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { - if (EliminatedLHSVals[i] < Smallest) { + if (EliminatedLHSVals[i]->id < Smallest->id) { // Merge the current notion of the smallest into the smaller one. LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); Smallest = EliminatedLHSVals[i]; @@ -553,14 +981,15 @@ 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 LiveInterval::VNInfo VNI = RHS.getValNumInfo(0); - LHS.setDefForValNum(LHSValNo, VNI.def); - LHS.setSrcRegForValNum(LHSValNo, 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. + LHSValNo->hasPHIKill |= VNI->hasPHIKill; + LHS.addKills(LHSValNo, VNI->kills); LHS.MergeRangesInAsValue(RHS, LHSValNo); - LHS.addKillsForValNum(LHSValNo, VNI.kills); LHS.weight += RHS.weight; if (RHS.preference && !LHS.preference) LHS.preference = RHS.preference; @@ -573,32 +1002,33 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) /// physreg, this method always canonicalizes LHS to be it. The output /// "RHS" will not have been modified, so we can use this information /// below to update aliases. -bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { +bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, + LiveInterval &RHS, bool &Swapped) { // Compute the final value assignment, assuming that the live ranges can be // coalesced. SmallVector LHSValNoAssignments; SmallVector RHSValNoAssignments; - SmallVector LHSValsDefinedFromRHS; - SmallVector RHSValsDefinedFromLHS; - SmallVector ValueNumberInfo; + DenseMap LHSValsDefinedFromRHS; + DenseMap RHSValsDefinedFromLHS; + SmallVector NewVNInfo; // If a live interval is a physical register, conservatively check if any // of its sub-registers is overlapping the live interval of the virtual // register. If so, do not coalesce. - if (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; } } @@ -612,56 +1042,57 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH // Find out if the RHS is defined as a copy from some value in the LHS. int RHSVal0DefinedFromLHS = -1; int RHSValID = -1; - LiveInterval::VNInfo RHSValNoInfo; - unsigned RHSSrcReg = RHS.getSrcRegForValNum(0); - if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { + VNInfo *RHSValNoInfo = NULL; + 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 = RHS.getValNumInfo(0); + RHSValNoInfo = RHSValNoInfo0; } } else { // It was defined as a copy from the LHS, find out what value # it is. - unsigned ValInst = RHS.getDefForValNum(0); - RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId; - RHSValNoInfo = LHS.getValNumInfo(RHSValID); + RHSValNoInfo = LHS.getLiveRangeContaining(RHSValNoInfo0->def-1)->valno; + RHSValID = RHSValNoInfo->id; RHSVal0DefinedFromLHS = RHSValID; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.resize(LHS.getNumValNums()); + NewVNInfo.resize(LHS.getNumValNums(), NULL); // Okay, *all* of the values in LHS that are defined as a copy from RHS // should now get updated. - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) { - if (rep(LHSSrcReg) != RHS.reg) { + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + 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. - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); + NewVNInfo[VN] = VNI; LHSValNoAssignments[VN] = VN; } else if (RHSValID == -1) { // Otherwise, it is a copy from the RHS, and we don't already have a // value# for it. Keep the current value number, but remember it. LHSValNoAssignments[VN] = RHSValID = VN; - ValueNumberInfo[VN] = RHSValNoInfo; - RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN)); + NewVNInfo[VN] = RHSValNoInfo; + LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; } else { // Otherwise, use the specified value #. LHSValNoAssignments[VN] = RHSValID; - if (VN != (unsigned)RHSValID) - ValueNumberInfo[VN].def = ~1U; // Now this val# is dead. - else { - ValueNumberInfo[VN] = RHSValNoInfo; - RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN)); + if (VN == (unsigned)RHSValID) { // Else this val# is dead. + NewVNInfo[VN] = RHSValNoInfo; + LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; } } } else { - ValueNumberInfo[VN] = LHS.getValNumInfo(VN); + NewVNInfo[VN] = VNI; LHSValNoAssignments[VN] = VN; } } @@ -669,70 +1100,75 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH assert(RHSValID != -1 && "Didn't find value #?"); RHSValNoAssignments[0] = RHSValID; if (RHSVal0DefinedFromLHS != -1) { - int LHSValId = LHSValNoAssignments[RHSVal0DefinedFromLHS]; - LHS.addKills(ValueNumberInfo[LHSValId], RHS.getKillsForValNum(0)); + // This path doesn't go through ComputeUltimateVN so just set + // it to anything. + RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1; } } else { // Loop over the value numbers of the LHS, seeing if any are defined from // the RHS. - LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = LHS.getSrcRegForValNum(VN); - if (ValSrcReg == 0) // Src not defined by a copy? + 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? 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. - unsigned ValInst = LHS.getDefForValNum(VN); - LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; + LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno; } // Loop over the value numbers of the RHS, seeing if any are defined from // the LHS. - RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - unsigned ValSrcReg = RHS.getSrcRegForValNum(VN); - if (ValSrcReg == 0) // Src not defined by a copy? + 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? 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. - unsigned ValInst = RHS.getDefForValNum(VN); - RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; + RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno; } LHSValNoAssignments.resize(LHS.getNumValNums(), -1); RHSValNoAssignments.resize(RHS.getNumValNums(), -1); - ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); + NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); - for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { - if (LHSValNoAssignments[VN] >= 0 || LHS.getDefForValNum(VN) == ~1U) + for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (LHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) continue; - ComputeUltimateVN(VN, ValueNumberInfo, + ComputeUltimateVN(VNI, NewVNInfo, LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, - LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); + LHSValNoAssignments, RHSValNoAssignments); } - for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { - if (RHSValNoAssignments[VN] >= 0 || RHS.getDefForValNum(VN) == ~1U) + for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); + i != e; ++i) { + VNInfo *VNI = *i; + unsigned VN = VNI->id; + if (RHSValNoAssignments[VN] >= 0 || VNI->def == ~1U) continue; // If this value number isn't a copy from the LHS, it's a new number. - if (RHSValsDefinedFromLHS[VN] == -1) { - ValueNumberInfo.push_back(RHS.getValNumInfo(VN)); - RHSValNoAssignments[VN] = ValueNumberInfo.size()-1; + if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { + NewVNInfo.push_back(VNI); + RHSValNoAssignments[VN] = NewVNInfo.size()-1; continue; } - ComputeUltimateVN(VN, ValueNumberInfo, + ComputeUltimateVN(VNI, NewVNInfo, RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, - RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); + RHSValNoAssignments, LHSValNoAssignments); } } @@ -765,7 +1201,8 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH if (Overlaps) { // If the live range overlap will map to the same value number in the // result liverange, we can still coalesce them. If not, we can't. - if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) + if (LHSValNoAssignments[I->valno->id] != + RHSValNoAssignments[J->valno->id]) return false; } @@ -779,25 +1216,36 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH } // Update kill info. Some live ranges are extended due to copy coalescing. - for (unsigned i = 0, e = RHSValsDefinedFromLHS.size(); i != e; ++i) { - int LHSValId = RHSValsDefinedFromLHS[i]; - if (LHSValId == -1) - continue; - unsigned RHSValId = RHSValNoAssignments[i]; - LHS.addKills(ValueNumberInfo[RHSValId], RHS.getKillsForValNum(i)); + 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); } - for (unsigned i = 0, e = LHSValsDefinedFromRHS.size(); i != e; ++i) { - int RHSValId = LHSValsDefinedFromRHS[i]; - if (RHSValId == -1) - continue; - unsigned LHSValId = LHSValNoAssignments[i]; - RHS.addKills(ValueNumberInfo[LHSValId], LHS.getKillsForValNum(i)); + + // 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. - LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], - ValueNumberInfo); + if ((RHS.ranges.size() > LHS.ranges.size() && + TargetRegisterInfo::isVirtualRegister(LHS.reg)) || + TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { + RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo); + Swapped = true; + } else { + LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo); + Swapped = false; + } return true; } @@ -814,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 @@ -852,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) { @@ -950,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; } } @@ -967,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) { @@ -1006,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); } } @@ -1016,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) { @@ -1050,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); @@ -1112,24 +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); - // If the definition instruction is re-materializable, its spill - // weight is half of what it would have been normally unless it's - // a load from fixed stack slot. - int Dummy; - if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy)) - w /= 2; - RegInt.weight += w; + RegInt.weight += + li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth); UniqueUses.insert(reg); } } @@ -1140,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) @@ -1166,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)