mf_ = &fn;
tm_ = &fn.getTarget();
mri_ = tm_->getRegisterInfo();
+ tii_ = tm_->getInstrInfo();
lv_ = &getAnalysis<LiveVariables>();
allocatableRegs_ = mri_->getAllocatableSet(fn);
r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg());
+ // If this function has any live ins, insert a dummy instruction at the
+ // beginning of the function that we will pretend "defines" the values. This
+ // is to make the interval analysis simpler by providing a number.
+ if (fn.livein_begin() != fn.livein_end()) {
+ unsigned FirstLiveIn = fn.livein_begin()->first;
+
+ // Find a reg class that contains this live in.
+ const TargetRegisterClass *RC = 0;
+ for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(),
+ E = mri_->regclass_end(); RCI != E; ++RCI)
+ if ((*RCI)->contains(FirstLiveIn)) {
+ RC = *RCI;
+ break;
+ }
+
+ MachineInstr *OldFirstMI = fn.begin()->begin();
+ mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(),
+ FirstLiveIn, FirstLiveIn, RC);
+ assert(OldFirstMI != fn.begin()->begin() &&
+ "copyRetToReg didn't insert anything!");
+ }
+
// number MachineInstrs
unsigned miIndex = 0;
for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end();
miIndex += InstrSlots::NUM;
}
+ // Note intervals due to live-in values.
+ if (fn.livein_begin() != fn.livein_end()) {
+ MachineBasicBlock *Entry = fn.begin();
+ for (MachineFunction::livein_iterator I = fn.livein_begin(),
+ E = fn.livein_end(); I != E; ++I) {
+ handlePhysicalRegisterDef(Entry, Entry->begin(),
+ getOrCreateInterval(I->first), 0, 0);
+ for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS)
+ handlePhysicalRegisterDef(Entry, Entry->begin(),
+ getOrCreateInterval(*AS), 0, 0);
+ }
+ }
+
computeIntervals();
numIntervals += getNumIntervals();
// perform a final pass over the instructions and compute spill
// weights, coalesce virtual registers and remove identity moves
const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
- const TargetInstrInfo& tii = *tm_->getInstrInfo();
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
mbbi != mbbe; ++mbbi) {
mii != mie; ) {
// if the move will be an identity move delete it
unsigned srcReg, dstReg, RegRep;
- if (tii.isMoveInstr(*mii, srcReg, dstReg) &&
+ if (tii_->isMoveInstr(*mii, srcReg, dstReg) &&
(RegRep = rep(srcReg)) == rep(dstReg)) {
// remove from def list
LiveInterval &interval = getOrCreateInterval(RegRep);
LiveInterval &RegInt = getInterval(reg);
RegInt.weight +=
- (mop.isUse() + mop.isDef()) * pow(10.0F, loopDepth);
+ (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth);
}
}
++mii;
}
/// print - Implement the dump method.
-void LiveIntervals::print(std::ostream &O) const {
+void LiveIntervals::print(std::ostream &O, const Module* ) const {
O << "********** INTERVALS **********\n";
for (const_iterator I = begin(), E = end(); I != E; ++I)
- O << I->second << "\n";
+ O << " " << I->second << "\n";
O << "********** MACHINEINSTRS **********\n";
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
}
}
-
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
// since this is called after the analysis is done we don't know if
if (MachineInstr* fmi = mri_->foldMemoryOperand(mi, i, slot)) {
if (lv_)
lv_->instructionChanged(mi, fmi);
- vrm.virtFolded(li.reg, mi, fmi);
+ vrm.virtFolded(li.reg, mi, i, fmi);
mi2iMap_.erase(mi);
i2miMap_[index/InstrSlots::NUM] = fmi;
mi2iMap_[fmi] = index;
// the spill weight is now infinity as it
// cannot be spilled again
- nI.weight = HUGE_VAL;
+ nI.weight = float(HUGE_VAL);
LiveRange LR(start, end, nI.getNextValue());
DEBUG(std::cerr << " +" << LR);
nI.addRange(LR);
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
- LiveInterval& interval)
+ LiveInterval& interval,
+ unsigned SrcReg, unsigned DestReg)
{
// A physical register cannot be live across basic block, so its
// lifetime must end somewhere in its defining basic block.
exit:
assert(start < end && "did not find end of interval?");
+
+ // Finally, if this is defining a new range for the physical register, and if
+ // that physreg is just a copy from a vreg, and if THAT vreg was a copy from
+ // the physreg, then the new fragment has the same value as the one copied
+ // into the vreg.
+ if (interval.reg == DestReg && !interval.empty() &&
+ MRegisterInfo::isVirtualRegister(SrcReg)) {
+
+ // Get the live interval for the vreg, see if it is defined by a copy.
+ LiveInterval &SrcInterval = getOrCreateInterval(SrcReg);
+
+ if (SrcInterval.containsOneValue()) {
+ assert(!SrcInterval.empty() && "Can't contain a value and be empty!");
+
+ // Get the first index of the first range. Though the interval may have
+ // multiple liveranges in it, we only check the first.
+ unsigned StartIdx = SrcInterval.begin()->start;
+ MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx);
+
+ // Check to see if the vreg was defined by a copy instruction, and that
+ // the source was this physreg.
+ unsigned VRegSrcSrc, VRegSrcDest;
+ if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) &&
+ SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) {
+ // Okay, now we know that the vreg was defined by a copy from this
+ // physreg. Find the value number being copied and use it as the value
+ // for this range.
+ const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1);
+ if (DefRange) {
+ LiveRange LR(start, end, DefRange->ValId);
+ interval.addRange(LR);
+ DEBUG(std::cerr << " +" << LR << '\n');
+ return;
+ }
+ }
+ }
+ }
+
+
LiveRange LR(start, end, interval.getNextValue());
interval.addRange(LR);
DEBUG(std::cerr << " +" << LR << '\n');
if (MRegisterInfo::isVirtualRegister(reg))
handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg));
else if (allocatableRegs_[reg]) {
- handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg));
+ unsigned SrcReg = 0, DestReg = 0;
+ bool IsMove = tii_->isMoveInstr(*MI, SrcReg, DestReg);
+
+ handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg),
+ SrcReg, DestReg);
for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS)
- handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS));
+ handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS),
+ SrcReg, DestReg);
}
}
DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n");
DEBUG(std::cerr << "********** Function: "
<< ((Value*)mf_->getFunction())->getName() << '\n');
+ bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end();
for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
I != E; ++I) {
MachineBasicBlock* mbb = I;
DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n");
- for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
- mi != miEnd; ++mi) {
+ MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
+ if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; }
+ for (; mi != miEnd; ++mi) {
const TargetInstrDescriptor& tid =
tm_->getInstrInfo()->get(mi->getOpcode());
DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi);
void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) {
DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
- const TargetInstrInfo &TII = *tm_->getInstrInfo();
for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end();
mi != mie; ++mi) {
// physical registers since we do not have liveness information
// on not allocatable physical registers
unsigned regA, regB;
- if (TII.isMoveInstr(*mi, regA, regB) &&
+ if (tii_->isMoveInstr(*mi, regA, regB) &&
(MRegisterInfo::isVirtualRegister(regA) || allocatableRegs_[regA]) &&
(MRegisterInfo::isVirtualRegister(regB) || allocatableRegs_[regB])) {
/// classes. The registers may be either phys or virt regs.
bool LiveIntervals::differingRegisterClasses(unsigned RegA,
unsigned RegB) const {
- const TargetRegisterClass *RegClass;
// Get the register classes for the first reg.
- if (MRegisterInfo::isVirtualRegister(RegA))
- RegClass = mf_->getSSARegMap()->getRegClass(RegA);
- else
- RegClass = mri_->getRegClass(RegA);
+ if (MRegisterInfo::isPhysicalRegister(RegA)) {
+ assert(MRegisterInfo::isVirtualRegister(RegB) &&
+ "Shouldn't consider two physregs!");
+ return !mf_->getSSARegMap()->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);
else
}
LiveInterval LiveIntervals::createInterval(unsigned reg) {
- float Weight = MRegisterInfo::isPhysicalRegister(reg) ? HUGE_VAL :0.0F;
+ float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
+ (float)HUGE_VAL :0.0F;
return LiveInterval(reg, Weight);
}