//
// 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.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//
#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/CodeGen/RegisterCoalescer.h"
-#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
cl::desc("Coalesce copies (default=true)"),
cl::init(true));
+ static cl::opt<bool>
+ NewHeuristic("new-coalescer-heuristic",
+ cl::desc("Use new coalescer heuristic"),
+ cl::init(false));
+
+ static cl::opt<bool>
+ ReMatSpillWeight("tweak-remat-spill-weight",
+ cl::desc("Tweak spill weight of re-materializable intervals"),
+ cl::init(true));
+
RegisterPass<SimpleRegisterCoalescing>
X("simple-register-coalescing", "Simple Register Coalescing");
void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<LiveIntervals>();
+ AU.addPreserved<MachineLoopInfo>();
+ AU.addPreservedID(MachineDominatorsID);
AU.addPreservedID(PHIEliminationID);
AU.addPreservedID(TwoAddressInstructionPassID);
AU.addRequired<LiveVariables>();
AU.addRequired<LiveIntervals>();
- AU.addRequired<LoopInfo>();
+ AU.addRequired<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
///
/// 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
// 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);
- // Finally, delete the copy instruction.
- li_->RemoveMachineInstrFromMaps(CopyMI);
- CopyMI->eraseFromParent();
++numPeep;
return true;
}
}
}
+/// 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;
+
+ 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. 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(MachineInstr *CopyMI,
- unsigned SrcReg, unsigned DstReg,
- bool &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);
- Again = false;
-
// If they are already joined we continue.
if (repSrcReg == repDstReg) {
DOUT << "\tCopy already coalesced.\n";
// 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=mf_->getSSARegMap()->getRegClass(repSrcReg);
+ const TargetRegisterClass *RC=mf_->getRegInfo().getRegClass(repSrcReg);
for (const unsigned *SRs = mri_->getSuperRegisters(repDstReg);
unsigned SR = *SRs; ++SRs) {
if (repDstReg == mri_->getSubReg(SR, SubIdx) &&
} else {
unsigned SrcSize= li_->getInterval(repSrcReg).getSize() / InstrSlots::NUM;
unsigned DstSize= li_->getInterval(repDstReg).getSize() / InstrSlots::NUM;
- const TargetRegisterClass *RC=mf_->getSSARegMap()->getRegClass(repDstReg);
+ const TargetRegisterClass *RC=mf_->getRegInfo().getRegClass(repDstReg);
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
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();
+ const TargetRegisterClass *RC = mf_->getRegInfo().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
// 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";
if (CopiedValNos.insert(DstValNo)) {
VNInfo *ValNo = RealDstInt.getNextValue(DstValNo->def, DstValNo->reg,
li_->getVNInfoAllocator());
+ ValNo->hasPHIKill = DstValNo->hasPHIKill;
RealDstInt.addKills(ValNo, DstValNo->kills);
RealDstInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo);
}
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());
+ JoinQueue->push(CopyRec(CopyMI, SrcReg, DstReg, LoopDepth,
+ isBackEdgeCopy(CopyMI, DstReg)));
+ }
+ }
+ }
+ }
+
DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_);
DOUT << "\n";
r2rRevMap_[repDstReg].push_back(repSrcReg);
// Finally, delete the copy instruction.
- li_->RemoveMachineInstrFromMaps(CopyMI);
- CopyMI->eraseFromParent();
+ JoinedCopies.insert(CopyMI);
++numPeep;
++numJoins;
return true;
/// 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
// 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.weight += RHS.weight;
continue;
// Figure out the value # from the RHS.
- LHSValsDefinedFromRHS[VNI] = RHS.getLiveRangeContaining(VNI->def-1)->valno;
+ LHSValsDefinedFromRHS[VNI]=RHS.getLiveRangeContaining(VNI->def-1)->valno;
}
// Loop over the value numbers of the RHS, seeing if any are defined from
continue;
// Figure out the value # from the LHS.
- RHSValsDefinedFromLHS[VNI]= LHS.getLiveRangeContaining(VNI->def-1)->valno;
+ RHSValsDefinedFromLHS[VNI]=LHS.getLiveRangeContaining(VNI->def-1)->valno;
}
LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
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);
}
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);
}
};
}
+/// getRepIntervalSize - Returns the size of the interval that represents the
+/// specified register.
+template<class SF>
+unsigned JoinPriorityQueue<SF>::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<CopyRec> &TryAgain) {
DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
-
+
std::vector<CopyRec> VirtCopies;
std::vector<CopyRec> PhysCopies;
+ unsigned LoopDepth = loopInfo->getLoopDepth(MBB);
for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
MII != E;) {
MachineInstr *Inst = MII++;
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];
bool Again = false;
- if (!JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg, Again))
+ 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.MI, TheCopy.SrcReg, TheCopy.DstReg, Again))
+ if (!JoinCopy(TheCopy, Again))
if (Again)
TryAgain.push_back(TheCopy);
}
void SimpleRegisterCoalescing::joinIntervals() {
DOUT << "********** JOINING INTERVALS ***********\n";
+ if (NewHeuristic)
+ JoinQueue = new JoinPriorityQueue<CopyRecSort>(this);
+
JoinedLIs.resize(li_->getNumIntervals());
JoinedLIs.reset();
std::vector<CopyRec> TryAgainList;
- const LoopInfo &LI = getAnalysis<LoopInfo>();
- 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)
// Join intervals in the function prolog first. We want to join physical
// registers with virtual registers before the intervals got too long.
std::vector<std::pair<unsigned, MachineBasicBlock*> > 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());
// 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) {
+ if (NewHeuristic) {
+ SmallVector<CopyRec, 16> TryAgain;
+ bool ProgressMade = true;
+ while (ProgressMade) {
+ ProgressMade = false;
+ while (!JoinQueue->empty()) {
+ CopyRec R = JoinQueue->pop();
bool Again = false;
- bool Success = JoinCopy(TheCopy.MI,TheCopy.SrcReg,TheCopy.DstReg,Again);
- if (Success || !Again) {
- TheCopy.MI = 0; // Mark this one as done.
+ 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;
+ }
}
}
}
}
RegNum = JoinedLIs.find_next(RegNum);
}
+
+ if (NewHeuristic)
+ delete JoinQueue;
DOUT << "*** Register mapping ***\n";
for (unsigned i = 0, e = r2rMap_.size(); i != e; ++i)
if (MRegisterInfo::isPhysicalRegister(RegA)) {
assert(MRegisterInfo::isVirtualRegister(RegB) &&
"Shouldn't consider two physregs!");
- return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA);
+ return !mf_->getRegInfo().getRegClass(RegB)->contains(RegA);
}
// Compare against the regclass for the second reg.
- const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA);
+ const TargetRegisterClass *RegClass = mf_->getRegInfo().getRegClass(RegA);
if (MRegisterInfo::isVirtualRegister(RegB))
- return RegClass != mf_->getSSARegMap()->getRegClass(RegB);
+ return RegClass != mf_->getRegInfo().getRegClass(RegB);
else
return !RegClass->contains(RegB);
}
/// 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) {
+SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
+ unsigned Reg, MachineOperand *&MOU) {
int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM;
int s = Start;
while (e >= s) {
/// 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) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isRegister() && MO.isDef() &&
/// unsetRegisterKill - Unset IsKill property of all uses of specific register
/// of the specific instruction.
-void SimpleRegisterCoalescing::unsetRegisterKill(MachineInstr *MI, unsigned Reg) {
+void SimpleRegisterCoalescing::unsetRegisterKill(MachineInstr *MI,
+ unsigned Reg) {
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isRegister() && MO.isKill() && MO.getReg() &&
mri_->regsOverlap(rep(MO.getReg()), Reg))
- MO.unsetIsKill();
+ MO.setIsKill(false);
}
}
/// 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) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isRegister() && MO.isKill() && MO.getReg() &&
mri_->regsOverlap(rep(MO.getReg()), Reg)) {
- MO.unsetIsKill();
+ MO.setIsKill(false);
}
}
r2rMap_.clear();
JoinedLIs.clear();
SubRegIdxes.clear();
+ JoinedCopies.clear();
}
static bool isZeroLengthInterval(LiveInterval *li) {
tii_ = tm_->getInstrInfo();
li_ = &getAnalysis<LiveIntervals>();
lv_ = &getAnalysis<LiveVariables>();
+ loopInfo = &getAnalysis<MachineLoopInfo>();
DOUT << "********** SIMPLE REGISTER COALESCING **********\n"
<< "********** Function: "
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)));
+ allocatableRCRegs_.insert(std::make_pair(*I,
+ mri_->getAllocatableSet(fn, *I)));
- SSARegMap *RegMap = mf_->getSSARegMap();
- r2rMap_.grow(RegMap->getLastVirtReg());
- r2rRevMap_.grow(RegMap->getLastVirtReg());
+ MachineRegisterInfo &RegInfo = mf_->getRegInfo();
+ r2rMap_.grow(RegInfo.getLastVirtReg());
+ r2rRevMap_.grow(RegInfo.getLastVirtReg());
// Join (coalesce) intervals if requested.
+ IndexedMap<unsigned, VirtReg2IndexFunctor> RegSubIdxMap;
if (EnableJoining) {
joinIntervals();
DOUT << "********** INTERVALS POST JOINING **********\n";
- for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) {
+ for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){
I->second.print(DOUT, mri_);
DOUT << "\n";
}
- // Transfer sub-registers info to SSARegMap now that coalescing information
- // is complete.
+ // Delete all coalesced copies.
+ for (SmallPtrSet<MachineInstr*,32>::iterator I = JoinedCopies.begin(),
+ E = JoinedCopies.end(); I != E; ++I) {
+ li_->RemoveMachineInstrFromMaps(*I);
+ (*I)->eraseFromParent();
+ }
+
+ // Transfer sub-registers info to MachineRegisterInfo now that coalescing
+ // information is complete.
+ RegSubIdxMap.grow(RegInfo.getLastVirtReg()+1);
while (!SubRegIdxes.empty()) {
std::pair<unsigned, unsigned> RI = SubRegIdxes.back();
SubRegIdxes.pop_back();
- mf_->getSSARegMap()->setIsSubRegister(RI.first, rep(RI.first), RI.second);
+ RegSubIdxMap[RI.first] = RI.second;
}
}
// perform a final pass over the instructions and compute spill
// weights, coalesce virtual registers and remove identity moves.
- const LoopInfo &loopInfo = getAnalysis<LoopInfo>();
-
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; ) {
// replace register with representative register
unsigned OrigReg = mop.getReg();
unsigned reg = rep(OrigReg);
- // Don't rewrite if it is a sub-register of a virtual register.
- if (!RegMap->isSubRegister(OrigReg))
+ unsigned SubIdx = RegSubIdxMap[OrigReg];
+ if (SubIdx && MRegisterInfo::isPhysicalRegister(reg))
+ mii->getOperand(i).setReg(mri_->getSubReg(reg, SubIdx));
+ else {
mii->getOperand(i).setReg(reg);
- else if (MRegisterInfo::isPhysicalRegister(reg))
- mii->getOperand(i).setReg(mri_->getSubReg(reg,
- RegMap->getSubRegisterIndex(OrigReg)));
+ mii->getOperand(i).setSubReg(SubIdx);
+ }
// Multiple uses of reg by the same instruction. It should not
// contribute to spill weight again.
if (UniqueUses.count(reg) != 0)
continue;
LiveInterval &RegInt = li_->getInterval(reg);
- float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth);
- RegInt.weight += w;
+ RegInt.weight +=
+ li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth);
UniqueUses.insert(reg);
}
}
// it and hope it will be easier to allocate for this li.
if (isZeroLengthInterval(&LI))
LI.weight = HUGE_VALF;
+ else {
+ bool isLoad = false;
+ if (ReMatSpillWeight && 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)
projects / oota-llvm.git / blobdiff