X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=00c820e3df923a0462c7b04b0c0c7aec049d0580;hb=8fc9a1022108e1afa8077e3e0a7b8a70eb3c3bc3;hp=ee2cbbb8ea5b5f07fca915ca48c109274fcf1113;hpb=95f0ab624d96e4ef56dbeccf86cd7ced4e42f519;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index ee2cbbb8ea5..00c820e3df9 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -13,9 +13,9 @@ //===----------------------------------------------------------------------===// #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" @@ -47,6 +47,11 @@ 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)); + RegisterPass X("simple-register-coalescing", "Simple Register Coalescing"); @@ -57,7 +62,6 @@ namespace { const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo(); void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { - //AU.addPreserved(); AU.addPreserved(); AU.addPreservedID(PHIEliminationID); AU.addPreservedID(TwoAddressInstructionPassID); @@ -178,31 +182,70 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte if (UIdx != -1) ValLREndInst->getOperand(UIdx).unsetIsKill(); - // Finally, delete the copy instruction. - li_->RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); ++numPeep; return true; } +/// AddSubRegIdxPairs - Recursively mark all the registers represented by the +/// specified register as sub-registers. The recursion level is expected to be +/// shallow. +void SimpleRegisterCoalescing::AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx) { + std::vector &JoinedRegs = r2rRevMap_[Reg]; + for (unsigned i = 0, e = JoinedRegs.size(); i != e; ++i) { + SubRegIdxes.push_back(std::make_pair(JoinedRegs[i], SubIdx)); + AddSubRegIdxPairs(JoinedRegs[i], SubIdx); + } +} + +/// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. +/// +bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI, + unsigned DstReg) { + MachineBasicBlock *MBB = CopyMI->getParent(); + const BasicBlock *BB = MBB->getBasicBlock(); + const Loop *L = loopInfo->getLoopFor(BB); + if (!L) + return false; + if (BB != L->getLoopLatch()) + return false; + + DstReg = rep(DstReg); + 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-1; + if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0] == KillIdx) + return true; + return false; +} + /// 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) { +/// 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 SrcReg = TheCopy.SrcReg; + unsigned DstReg = TheCopy.DstReg; unsigned repSrcReg = rep(SrcReg); unsigned repDstReg = rep(DstReg); // If they are already joined we continue. if (repSrcReg == repDstReg) { DOUT << "\tCopy already coalesced.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); @@ -211,17 +254,17 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // 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]) { DOUT << "\tSrc reg is unallocatable physreg.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } if (DstIsPhys && !allocatableRegs_[repDstReg]) { DOUT << "\tDst reg is unallocatable physreg.\n"; - return true; // Not coalescable. + return false; // Not coalescable. } bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; @@ -255,19 +298,30 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, RHS.overlaps(li_->getInterval(RealDstReg))) { DOUT << "Interfere with register "; DEBUG(li_->getInterval(RealDstReg).print(DOUT, mri_)); - return true; // Not coalescable + return false; // Not coalescable } for (const unsigned* SR = mri_->getSubRegisters(RealDstReg); *SR; ++SR) if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { DOUT << "Interfere with sub-register "; DEBUG(li_->getInterval(*SR).print(DOUT, mri_)); - return true; // Not coalescable + return false; // Not coalescable } - } else if (li_->getInterval(repDstReg).getSize() > - li_->getInterval(repSrcReg).getSize()) { + } else { + unsigned SrcSize= li_->getInterval(repSrcReg).getSize() / InstrSlots::NUM; + unsigned DstSize= li_->getInterval(repDstReg).getSize() / InstrSlots::NUM; + const TargetRegisterClass *RC=mf_->getSSARegMap()->getRegClass(repDstReg); + unsigned Threshold = allocatableRCRegs_[RC].count(); // Be conservative. If both sides are virtual registers, do not coalesce - // if the sub-register live interval is longer. - return false; + // 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(repSrcReg); + LiveVariables::VarInfo &dvi = lv_->getVarInfo(repDstReg); + if ((float)dvi.NumUses / DstSize < (float)svi.NumUses / SrcSize) { + Again = true; // May be possible to coalesce later. + return false; + } + } } } else if (differingRegisterClasses(repSrcReg, repDstReg)) { // If they are not of the same register class, we cannot join them. @@ -276,6 +330,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // 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; } @@ -338,6 +393,8 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg; const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg); unsigned Threshold = allocatableRCRegs_[RC].count(); + 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 @@ -349,6 +406,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; } } @@ -386,11 +444,14 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // Coalescing failed. // If we can eliminate the copy without merging the live ranges, do so now. - if (!isExtSubReg && AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI)) + if (!isExtSubReg && AdjustCopiesBackFrom(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; } @@ -459,8 +520,27 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, std::swap(repSrcReg, repDstReg); std::swap(ResSrcInt, ResDstInt); } - SubRegIdxes.push_back(std::make_pair(DstReg, - CopyMI->getOperand(2).getImm())); + unsigned SubIdx = CopyMI->getOperand(2).getImm(); + SubRegIdxes.push_back(std::make_pair(repSrcReg, SubIdx)); + AddSubRegIdxPairs(repSrcReg, SubIdx); + } + + if (NewHeuristic) { + 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) { + MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); + unsigned SrcReg, DstReg; + if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg) && + JoinedCopies.count(CopyMI) == 0) { + unsigned LoopDepth = + loopInfo->getLoopDepth(CopyMI->getParent()->getBasicBlock()); + JoinQueue->push(CopyRec(CopyMI, SrcReg, DstReg, LoopDepth, + isBackEdgeCopy(CopyMI, DstReg))); + } + } + } } DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_); @@ -470,10 +550,10 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI, // being merged. li_->removeInterval(repSrcReg); r2rMap_[repSrcReg] = repDstReg; + r2rRevMap_[repDstReg].push_back(repSrcReg); // Finally, delete the copy instruction. - li_->RemoveMachineInstrFromMaps(CopyMI); - CopyMI->eraseFromParent(); + JoinedCopies.insert(CopyMI); ++numPeep; ++numJoins; return true; @@ -777,7 +857,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, i != e; ++i) { VNInfo *VNI = *i; unsigned ValSrcReg = VNI->reg; - if (ValSrcReg == 0) // Src not defined by a copy? + if (VNI->def == ~1U ||ValSrcReg == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the LHS interval. If the src is @@ -795,7 +875,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, i != e; ++i) { VNInfo *VNI = *i; unsigned ValSrcReg = VNI->reg; - if (ValSrcReg == 0) // Src not defined by a copy? + if (VNI->def == ~1U || ValSrcReg == 0) // Src not defined by a copy? continue; // DstReg is known to be a register in the RHS interval. If the src is @@ -928,12 +1008,62 @@ 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; + else if (left.isBackEdge == right.isBackEdge) { + // Join virtuals to physical registers first. + bool LDstIsPhys = MRegisterInfo::isPhysicalRegister(left.DstReg); + bool LSrcIsPhys = MRegisterInfo::isPhysicalRegister(left.SrcReg); + bool LIsPhys = LDstIsPhys || LSrcIsPhys; + bool RDstIsPhys = MRegisterInfo::isPhysicalRegister(right.DstReg); + bool RSrcIsPhys = MRegisterInfo::isPhysicalRegister(right.SrcReg); + bool RIsPhys = RDstIsPhys || RSrcIsPhys; + if (LIsPhys && !RIsPhys) + return false; + else if (LIsPhys == RIsPhys) { + // Join shorter intervals first. + unsigned LSize = 0; + unsigned RSize = 0; + if (LIsPhys) { + LSize = LDstIsPhys ? 0 : JPQ->getRepIntervalSize(left.DstReg); + LSize += LSrcIsPhys ? 0 : JPQ->getRepIntervalSize(left.SrcReg); + RSize = RDstIsPhys ? 0 : JPQ->getRepIntervalSize(right.DstReg); + RSize += RSrcIsPhys ? 0 : JPQ->getRepIntervalSize(right.SrcReg); + } else { + LSize = std::min(JPQ->getRepIntervalSize(left.DstReg), + JPQ->getRepIntervalSize(left.SrcReg)); + RSize = std::min(JPQ->getRepIntervalSize(right.DstReg), + JPQ->getRepIntervalSize(right.SrcReg)); + } + if (LSize < RSize) + return false; + } + } + } + return true; +} + void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, std::vector &TryAgain) { DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; - + std::vector VirtCopies; std::vector PhysCopies; + unsigned LoopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock()); for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); MII != E;) { MachineInstr *Inst = MII++; @@ -950,34 +1080,48 @@ void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, unsigned repDstReg = rep(DstReg); bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg); - if (SrcIsPhys || DstIsPhys) - PhysCopies.push_back(getCopyRec(Inst, SrcReg, DstReg)); - else - VirtCopies.push_back(getCopyRec(Inst, SrcReg, DstReg)); + if (NewHeuristic) { + JoinQueue->push(CopyRec(Inst, SrcReg, DstReg, LoopDepth, + isBackEdgeCopy(Inst, DstReg))); + } else { + if (SrcIsPhys || DstIsPhys) + PhysCopies.push_back(CopyRec(Inst, SrcReg, DstReg, 0, false)); + else + VirtCopies.push_back(CopyRec(Inst, SrcReg, DstReg, 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]; - if (!JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) - TryAgain.push_back(TheCopy); + 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]; - if (!JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) - TryAgain.push_back(TheCopy); + bool Again = false; + if (!JoinCopy(TheCopy, Again)) + if (Again) + TryAgain.push_back(TheCopy); } } void SimpleRegisterCoalescing::joinIntervals() { DOUT << "********** JOINING INTERVALS ***********\n"; + if (NewHeuristic) + JoinQueue = new JoinPriorityQueue(this); + JoinedLIs.resize(li_->getNumIntervals()); JoinedLIs.reset(); 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) @@ -991,7 +1135,8 @@ void SimpleRegisterCoalescing::joinIntervals() { // 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)); + MBBs.push_back(std::make_pair(loopInfo-> + getLoopDepth(I->getBasicBlock()), I)); // Sort by loop depth. std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); @@ -1003,16 +1148,43 @@ void SimpleRegisterCoalescing::joinIntervals() { // 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); + } + + if (ProgressMade) { + while (!TryAgain.empty()) { + JoinQueue->push(TryAgain.back()); + TryAgain.pop_back(); + } + } + } + } 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; + } + } } } } @@ -1037,9 +1209,12 @@ void SimpleRegisterCoalescing::joinIntervals() { } RegNum = JoinedLIs.find_next(RegNum); } + + if (NewHeuristic) + delete JoinQueue; DOUT << "*** Register mapping ***\n"; - for (int i = 0, e = r2rMap_.size(); i != e; ++i) + for (unsigned i = 0, e = r2rMap_.size(); i != e; ++i) if (r2rMap_[i]) { DOUT << " reg " << i << " -> "; DEBUG(printRegName(r2rMap_[i])); @@ -1172,9 +1347,13 @@ void SimpleRegisterCoalescing::printRegName(unsigned reg) const { } void SimpleRegisterCoalescing::releaseMemory() { - r2rMap_.clear(); - JoinedLIs.clear(); - SubRegIdxes.clear(); + for (unsigned i = 0, e = r2rMap_.size(); i != e; ++i) + r2rRevMap_[i].clear(); + r2rRevMap_.clear(); + r2rMap_.clear(); + JoinedLIs.clear(); + SubRegIdxes.clear(); + JoinedCopies.clear(); } static bool isZeroLengthInterval(LiveInterval *li) { @@ -1192,6 +1371,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { tii_ = tm_->getInstrInfo(); li_ = &getAnalysis(); lv_ = &getAnalysis(); + loopInfo = &getAnalysis(); DOUT << "********** SIMPLE REGISTER COALESCING **********\n" << "********** Function: " @@ -1204,6 +1384,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { SSARegMap *RegMap = mf_->getSSARegMap(); r2rMap_.grow(RegMap->getLastVirtReg()); + r2rRevMap_.grow(RegMap->getLastVirtReg()); // Join (coalesce) intervals if requested. if (EnableJoining) { @@ -1214,7 +1395,15 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { DOUT << "\n"; } - // Track coalesced sub-registers. + // Delete all coalesced copies. + for (SmallPtrSet::iterator I = JoinedCopies.begin(), + E = JoinedCopies.end(); I != E; ++I) { + li_->RemoveMachineInstrFromMaps(*I); + (*I)->eraseFromParent(); + } + + // Transfer sub-registers info to SSARegMap now that coalescing information + // is complete. while (!SubRegIdxes.empty()) { std::pair RI = SubRegIdxes.back(); SubRegIdxes.pop_back(); @@ -1224,12 +1413,10 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { // perform a final pass over the instructions and compute spill // weights, coalesce virtual registers and remove identity moves. - const LoopInfo &loopInfo = getAnalysis(); - 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->getBasicBlock()); for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); mii != mie; ) {