//
// 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.
//
//===----------------------------------------------------------------------===//
//
#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("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);
++numPeep;
return true;
bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
unsigned DstReg) {
MachineBasicBlock *MBB = CopyMI->getParent();
- const BasicBlock *BB = MBB->getBasicBlock();
- const Loop *L = loopInfo->getLoopFor(BB);
+ const MachineLoop *L = loopInfo->getLoopFor(MBB);
if (!L)
return false;
- if (BB != L->getLoopLatch())
+ if (MBB != L->getLoopLatch())
return false;
DstReg = rep(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.
- 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 (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);
}
unsigned SrcReg, DstReg;
if (CopyMI && tii_->isMoveInstr(*CopyMI, SrcReg, DstReg) &&
JoinedCopies.count(CopyMI) == 0) {
- unsigned LoopDepth =
- loopInfo->getLoopDepth(CopyMI->getParent()->getBasicBlock());
+ unsigned LoopDepth = loopInfo->getLoopDepth(CopyMI->getParent());
JoinQueue->push(CopyRec(CopyMI, SrcReg, DstReg, LoopDepth,
isBackEdgeCopy(CopyMI, DstReg)));
}
/// 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);
}
std::vector<CopyRec> VirtCopies;
std::vector<CopyRec> PhysCopies;
- unsigned LoopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock());
+ unsigned LoopDepth = loopInfo->getLoopDepth(MBB);
for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
MII != E;) {
MachineInstr *Inst = MII++;
// 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(loopInfo->
- 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());
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);
}
}
tii_ = tm_->getInstrInfo();
li_ = &getAnalysis<LiveIntervals>();
lv_ = &getAnalysis<LiveVariables>();
- loopInfo = &getAnalysis<LoopInfo>();
+ 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";
}
(*I)->eraseFromParent();
}
- // Transfer sub-registers info to SSARegMap now that coalescing information
- // is complete.
- RegSubIdxMap.grow(mf_->getSSARegMap()->getLastVirtReg()+1);
+ // 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();
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; ) {
// 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