diff options
-rw-r--r-- | include/llvm/Target/TargetRegisterInfo.h | 6 | ||||
-rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.cpp | 209 | ||||
-rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.h | 23 |
3 files changed, 129 insertions, 109 deletions
diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h index c7b8290..54fc00d 100644 --- a/include/llvm/Target/TargetRegisterInfo.h +++ b/include/llvm/Target/TargetRegisterInfo.h @@ -164,6 +164,12 @@ public: while (*I != NULL) ++I; return I; } + + /// isASubClass - return true if this TargetRegisterClass is a sub-class of at + /// least one other TargetRegisterClass. + bool isASubClass() const { + return SuperClasses[0] != 0; + } /// allocation_order_begin/end - These methods define a range of registers /// which specify the registers in this class that are valid to register diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index 637d74b..f0b0d58 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -36,7 +36,7 @@ using namespace llvm; STATISTIC(numJoins , "Number of interval joins performed"); -STATISTIC(numSubJoins , "Number of subclass joins performed"); +STATISTIC(numCrossRCs , "Number of cross class joins performed"); STATISTIC(numCommutes , "Number of instruction commuting performed"); STATISTIC(numExtends , "Number of copies extended"); STATISTIC(NumReMats , "Number of instructions re-materialized"); @@ -55,8 +55,8 @@ NewHeuristic("new-coalescer-heuristic", cl::init(false), cl::Hidden); static cl::opt<bool> -CrossClassJoin("join-subclass-copies", - cl::desc("Coalesce copies to sub- register class"), +CrossClassJoin("join-cross-class-copies", + cl::desc("Coalesce cross register class copies"), cl::init(false), cl::Hidden); static RegisterPass<SimpleRegisterCoalescing> @@ -953,38 +953,24 @@ static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx, return 0; } -/// isProfitableToCoalesceToSubRC - Given that register class of DstReg is -/// a subset of the register class of SrcReg, return true if it's profitable -/// to coalesce the two registers. +/// isWinToJoinCrossClass - Return true if it's profitable to coalesce +/// two virtual registers from different register classes. bool -SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg, - unsigned DstReg, - MachineBasicBlock *MBB){ - if (!CrossClassJoin) - return false; - - // First let's make sure all uses are in the same MBB. - for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(SrcReg), - RE = mri_->reg_end(); RI != RE; ++RI) { - MachineInstr &MI = *RI; - if (MI.getParent() != MBB) - return false; - } - for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(DstReg), - RE = mri_->reg_end(); RI != RE; ++RI) { - MachineInstr &MI = *RI; - if (MI.getParent() != MBB) - return false; - } - +SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg, + unsigned SmallReg, + unsigned Threshold) { // Then make sure the intervals are *short*. - LiveInterval &SrcInt = li_->getInterval(SrcReg); - LiveInterval &DstInt = li_->getInterval(DstReg); - unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt); - unsigned DstSize = li_->getApproximateInstructionCount(DstInt); - const TargetRegisterClass *RC = mri_->getRegClass(DstReg); - unsigned Threshold = allocatableRCRegs_[RC].count() * 2; - return (SrcSize + DstSize) <= Threshold; + LiveInterval &LargeInt = li_->getInterval(LargeReg); + LiveInterval &SmallInt = li_->getInterval(SmallReg); + unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt); + unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt); + if (SmallSize > Threshold || LargeSize > Threshold) + if ((float)std::distance(mri_->use_begin(SmallReg), + mri_->use_end()) / SmallSize < + (float)std::distance(mri_->use_begin(LargeReg), + mri_->use_end()) / LargeSize) + return false; + return true; } /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual @@ -1047,15 +1033,9 @@ SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, /// an extract_subreg where dst is a physical register, e.g. /// cl = EXTRACT_SUBREG reg1024, 1 bool -SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(MachineInstr *CopyMI, - unsigned DstReg, unsigned SrcReg, - unsigned SubIdx, unsigned &RealDstReg) { - if (CopyMI->getOperand(1).getSubReg()) { - DOUT << "\tSrc of extract_subreg already coalesced with reg" - << " of a super-class.\n"; - return false; // Not coalescable. - } - +SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg, + unsigned SrcReg, unsigned SubIdx, + unsigned &RealDstReg) { const TargetRegisterClass *RC = mri_->getRegClass(SrcReg); RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_); assert(RealDstReg && "Invalid extract_subreg instruction!"); @@ -1083,14 +1063,9 @@ SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(MachineInstr *CopyMI, /// an insert_subreg where src is a physical register, e.g. /// reg1024 = INSERT_SUBREG reg1024, c1, 0 bool -SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(MachineInstr *CopyMI, - unsigned DstReg, unsigned SrcReg, - unsigned SubIdx, unsigned &RealSrcReg) { - if (CopyMI->getOperand(1).getSubReg()) { - DOUT << "\tSrc of insert_subreg already coalesced with reg" - << " of a super-class.\n"; - return false; // Not coalescable. - } +SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg, + unsigned SrcReg, unsigned SubIdx, + unsigned &RealSrcReg) { const TargetRegisterClass *RC = mri_->getRegClass(DstReg); RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_); assert(RealSrcReg && "Invalid extract_subreg instruction!"); @@ -1111,7 +1086,6 @@ SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(MachineInstr *CopyMI, return true; } - /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, /// which are the src/dst of the copy instruction CopyMI. This returns true /// if the copy was successfully coalesced away. If it is not currently @@ -1172,7 +1146,8 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { } // Should be non-null only when coalescing to a sub-register class. - const TargetRegisterClass *SubRC = NULL; + bool CrossRC = false; + const TargetRegisterClass *NewRC = NULL; MachineBasicBlock *CopyMBB = CopyMI->getParent(); unsigned RealDstReg = 0; unsigned RealSrcReg = 0; @@ -1206,13 +1181,17 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { DstReg = tri_->getSubReg(DstReg, SubIdx); SubIdx = 0; } else if ((DstIsPhys && isExtSubReg) || (SrcIsPhys && isInsSubReg)) { + if (CopyMI->getOperand(1).getSubReg()) { + DOUT << "\tSrc of extract_subreg already coalesced with reg" + << " of a super-class.\n"; + return false; // Not coalescable. + } + if (isExtSubReg) { - if (!CanJoinExtractSubRegToPhysReg(CopyMI, DstReg, SrcReg, SubIdx, - RealDstReg)) + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg)) return false; // Not coalescable } else { - if (!CanJoinInsertSubRegToPhysReg(CopyMI, DstReg, SrcReg, SubIdx, - RealSrcReg)) + if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) return false; // Not coalescable } SubIdx = 0; @@ -1220,8 +1199,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg() : CopyMI->getOperand(2).getSubReg(); if (OldSubIdx) { - if (OldSubIdx == SubIdx && - !differingRegisterClasses(SrcReg, DstReg, SubRC)) + if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg)) // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been // coalesced to a larger register so the subreg indices cancel out. // Also check if the other larger register is of the same register @@ -1235,41 +1213,90 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { if (SubIdx) { unsigned LargeReg = isExtSubReg ? SrcReg : DstReg; unsigned SmallReg = isExtSubReg ? DstReg : SrcReg; - unsigned LargeRegSize = - li_->getApproximateInstructionCount(li_->getInterval(LargeReg)); - unsigned SmallRegSize = - li_->getApproximateInstructionCount(li_->getInterval(SmallReg)); - const TargetRegisterClass *RC = mri_->getRegClass(SmallReg); - unsigned Threshold = allocatableRCRegs_[RC].count(); - // Be conservative. If both sides are virtual registers, do not coalesce - // if this will cause a high use density interval to target a smaller - // set of registers. - if (SmallRegSize > Threshold || LargeRegSize > Threshold) { - if ((float)std::distance(mri_->use_begin(SmallReg), - mri_->use_end()) / SmallRegSize < - (float)std::distance(mri_->use_begin(LargeReg), - mri_->use_end()) / LargeRegSize) { - Again = true; // May be possible to coalesce later. - return false; - } + unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count(); + if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { + Again = true; // May be possible to coalesce later. + return false; } } } - } else if (differingRegisterClasses(SrcReg, DstReg, SubRC)) { - // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced + } else if (differingRegisterClasses(SrcReg, DstReg)) { + if (!CrossClassJoin) + return false; + CrossRC = true; + + // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced // with another? If it's the resulting destination register, then // the subidx must be propagated to uses (but only those defined // by the EXTRACT_SUBREG). If it's being coalesced into another // register, it should be safe because register is assumed to have // the register class of the super-register. - if (!SubRC || !isProfitableToCoalesceToSubRC(SrcReg, DstReg, CopyMBB)) { - // If they are not of the same register class, we cannot join them. + // Process moves where one of the registers have a sub-register index. + MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg); + if (DstMO->getSubReg()) + // FIXME: Can we handle this? + return false; + MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg); + SubIdx = SrcMO->getSubReg(); + if (SubIdx) { + // This is not a extract_subreg but it looks like one. + // e.g. %cl = MOV16rr %reg1024:2 + isExtSubReg = true; + if (DstIsPhys) { + if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg)) + return false; // Not coalescable + SubIdx = 0; + } + } + + const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg); + const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg); + unsigned LargeReg = SrcReg; + unsigned SmallReg = DstReg; + unsigned Limit = 0; + + // Now determine the register class of the joined register. + if (isExtSubReg) { + if (SubIdx && DstRC && DstRC->isASubClass()) { + // This is a move to a sub-register class. However, the source is a + // sub-register of a larger register class. We don't know what should + // the register class be. FIXME. + Again = true; + return false; + } + Limit = allocatableRCRegs_[DstRC].count(); + } else if (!SrcIsPhys && !SrcIsPhys) { + unsigned SrcSize = SrcRC->getSize(); + unsigned DstSize = DstRC->getSize(); + if (SrcSize < DstSize) + // For example X86::MOVSD2PDrr copies from FR64 to VR128. + NewRC = DstRC; + else if (DstSize > SrcSize) { + NewRC = SrcRC; + std::swap(LargeReg, SmallReg); + } else { + unsigned SrcNumRegs = SrcRC->getNumRegs(); + unsigned DstNumRegs = DstRC->getNumRegs(); + if (DstNumRegs < SrcNumRegs) + // Sub-register class? + NewRC = DstRC; + else if (SrcNumRegs < DstNumRegs) { + NewRC = SrcRC; + std::swap(LargeReg, SmallReg); + } else + // No idea what's the right register class to use. + return false; + } + } + + if (!SrcIsPhys && !DstIsPhys && + !isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { DOUT << "\tSrc/Dest are different register classes.\n"; // Allow the coalescer to try again in case either side gets coalesced to // a physical register that's compatible with the other side. e.g. // r1024 = MOV32to32_ r1025 - // but later r1024 is assigned EAX then r1025 may be coalesced with EAX. + // But later r1024 is assigned EAX then r1025 may be coalesced with EAX. Again = true; // May be possible to coalesce later. return false; } @@ -1417,9 +1444,10 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { // Coalescing to a virtual register that is of a sub-register class of the // other. Make sure the resulting register is set to the right register class. - if (SubRC) { - mri_->setRegClass(DstReg, SubRC); - ++numSubJoins; + if (CrossRC) { + ++numCrossRCs; + if (NewRC) + mri_->setRegClass(DstReg, NewRC); } if (NewHeuristic) { @@ -2208,14 +2236,10 @@ void SimpleRegisterCoalescing::joinIntervals() { } /// Return true if the two specified registers belong to different register -/// classes. The registers may be either phys or virt regs. In the -/// case where both registers are virtual registers, it would also returns -/// true by reference the RegB register class in SubRC if it is a subset of -/// RegA's register class. +/// classes. The registers may be either phys or virt regs. bool -SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB, - const TargetRegisterClass *&SubRC) const { - +SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, + unsigned RegB) const { // Get the register classes for the first reg. if (TargetRegisterInfo::isPhysicalRegister(RegA)) { assert(TargetRegisterInfo::isVirtualRegister(RegB) && @@ -2227,10 +2251,7 @@ SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB, const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA); if (TargetRegisterInfo::isVirtualRegister(RegB)) { const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB); - if (RegClassA == RegClassB) - return false; - SubRC = (RegClassA->hasSubClass(RegClassB)) ? RegClassB : NULL; - return true; + return RegClassA != RegClassB; } return !RegClassA->contains(RegB); } diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h index a4f0fa3..cce5ceb 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.h +++ b/lib/CodeGen/SimpleRegisterCoalescing.h @@ -173,12 +173,8 @@ namespace llvm { bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS); /// Return true if the two specified registers belong to different register - /// classes. The registers may be either phys or virt regs. In the - /// case where both registers are virtual registers, it would also returns - /// true by reference the RegB register class in SubRC if it is a subset of - /// RegA's register class. - bool differingRegisterClasses(unsigned RegA, unsigned RegB, - const TargetRegisterClass *&SubRC) const; + /// classes. The registers may be either phys or virt regs. + bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If @@ -219,11 +215,10 @@ namespace llvm { /// identity copies so they will be removed. void RemoveCopiesFromValNo(LiveInterval &li, VNInfo *VNI); - /// isProfitableToCoalesceToSubRC - Given that register class of DstReg is - /// a subset of the register class of SrcReg, return true if it's profitable - /// to coalesce the two registers. - bool isProfitableToCoalesceToSubRC(unsigned SrcReg, unsigned DstReg, - MachineBasicBlock *MBB); + /// isWinToJoinCrossClass - Return true if it's profitable to coalesce + /// two virtual registers from different register classes. + bool isWinToJoinCrossClass(unsigned LargeReg, unsigned SmallReg, + unsigned Threshold); /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual /// register with a physical register, check if any of the virtual register @@ -235,15 +230,13 @@ namespace llvm { /// CanJoinExtractSubRegToPhysReg - Return true if it's possible to coalesce /// an extract_subreg where dst is a physical register, e.g. /// cl = EXTRACT_SUBREG reg1024, 1 - bool CanJoinExtractSubRegToPhysReg(MachineInstr *CopyMI, - unsigned DstReg, unsigned SrcReg, + bool CanJoinExtractSubRegToPhysReg(unsigned DstReg, unsigned SrcReg, unsigned SubIdx, unsigned &RealDstReg); /// CanJoinInsertSubRegToPhysReg - Return true if it's possible to coalesce /// an insert_subreg where src is a physical register, e.g. /// reg1024 = INSERT_SUBREG reg1024, c1, 0 - bool CanJoinInsertSubRegToPhysReg(MachineInstr *CopyMI, - unsigned DstReg, unsigned SrcReg, + bool CanJoinInsertSubRegToPhysReg(unsigned DstReg, unsigned SrcReg, unsigned SubIdx, unsigned &RealDstReg); /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of |