//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "liveintervals"
-#include "LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "VirtRegMap.h"
#include "llvm/Value.h"
#include "llvm/Analysis/LoopInfo.h"
EnableJoining("join-liveintervals",
cl::desc("Join compatible live intervals"),
cl::init(true));
- cl::opt<bool>
- DisableHack("disable-hack");
};
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
{
- AU.addPreserved<LiveVariables>();
AU.addRequired<LiveVariables>();
AU.addPreservedID(PHIEliminationID);
AU.addRequiredID(PHIEliminationID);
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, true);
+ for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS)
+ handlePhysicalRegisterDef(Entry, Entry->begin(),
+ getOrCreateInterval(*AS), 0, 0, true);
+ }
+ }
+
computeIntervals();
numIntervals += getNumIntervals();
-#if 1
- DEBUG(std::cerr << "********** INTERVALS **********\n");
- DEBUG(for (iterator I = begin(), E = end(); I != E; ++I)
- std::cerr << I->second << "\n");
-#endif
+ DEBUG(std::cerr << "********** INTERVALS **********\n";
+ for (iterator I = begin(), E = end(); I != E; ++I) {
+ I->second.print(std::cerr, mri_);
+ std::cerr << "\n";
+ });
// join intervals if requested
if (EnableJoining) joinIntervals();
/// print - Implement the dump method.
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";
+ for (const_iterator I = begin(), E = end(); I != E; ++I) {
+ I->second.print(std::cerr, mri_);
+ std::cerr << "\n";
+ }
O << "********** MACHINEINSTRS **********\n";
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
MachineBasicBlock::iterator mi = getInstructionFromIndex(index);
+ // NewRegLiveIn - This instruction might have multiple uses of the spilled
+ // register. In this case, for the first use, keep track of the new vreg
+ // that we reload it into. If we see a second use, reuse this vreg
+ // instead of creating live ranges for two reloads.
+ unsigned NewRegLiveIn = 0;
+
for_operand:
for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
MachineOperand& mop = mi->getOperand(i);
if (mop.isRegister() && mop.getReg() == li.reg) {
- // First thing, attempt to fold the memory reference into the
- // instruction. If we can do this, we don't need to insert spill
- // code.
- if (MachineInstr* fmi = mri_->foldMemoryOperand(mi, i, slot)) {
+ if (NewRegLiveIn && mop.isUse()) {
+ // We already emitted a reload of this value, reuse it for
+ // subsequent operands.
+ mi->SetMachineOperandReg(i, NewRegLiveIn);
+ DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn
+ << " for operand #" << i << '\n');
+ } else if (MachineInstr* fmi = mri_->foldMemoryOperand(mi, i, slot)) {
+ // Attempt to fold the memory reference into the instruction. If we
+ // can do this, we don't need to insert spill code.
if (lv_)
lv_->instructionChanged(mi, fmi);
vrm.virtFolded(li.reg, mi, i, fmi);
getUseIndex(index));
// create a new register for this spill
- unsigned nReg = mf_->getSSARegMap()->createVirtualRegister(rc);
- mi->SetMachineOperandReg(i, nReg);
+ NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc);
+ mi->SetMachineOperandReg(i, NewRegLiveIn);
vrm.grow();
- vrm.assignVirt2StackSlot(nReg, slot);
- LiveInterval& nI = getOrCreateInterval(nReg);
+ vrm.assignVirt2StackSlot(NewRegLiveIn, slot);
+ LiveInterval& nI = getOrCreateInterval(NewRegLiveIn);
assert(nI.empty());
// the spill weight is now infinity as it
// update live variables if it is available
if (lv_)
- lv_->addVirtualRegisterKilled(nReg, mi);
+ lv_->addVirtualRegisterKilled(NewRegLiveIn, mi);
+
+ // If this is a live in, reuse it for subsequent live-ins. If it's
+ // a def, we can't do this.
+ if (!mop.isUse()) NewRegLiveIn = 0;
+
DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n');
}
}
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
- for (LiveVariables::killed_iterator KI = lv_->dead_begin(mi),
- E = lv_->dead_end(mi); KI != E; ++KI)
- if (KI->second == interval.reg) {
- interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
- break;
- }
+ if (lv_->RegisterDefIsDead(mi, interval.reg))
+ interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
DEBUG(std::cerr << "RESULT: " << interval);
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
LiveInterval& interval,
- unsigned SrcReg, unsigned DestReg)
+ unsigned SrcReg, unsigned DestReg,
+ bool isLiveIn)
{
// A physical register cannot be live across basic block, so its
// lifetime must end somewhere in its defining basic block.
// If it is not used after definition, it is considered dead at
// the instruction defining it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
- for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi);
- ki != ke; ++ki) {
- if (interval.reg == ki->second) {
- DEBUG(std::cerr << " dead");
- end = getDefIndex(start) + 1;
- goto exit;
- }
+ if (lv_->RegisterDefIsDead(mi, interval.reg)) {
+ DEBUG(std::cerr << " dead");
+ end = getDefIndex(start) + 1;
+ goto exit;
}
// If it is not dead on definition, it must be killed by a
// subsequent instruction. Hence its interval is:
// [defSlot(def), useSlot(kill)+1)
- while (true) {
- ++mi;
- assert(mi != MBB->end() && "physreg was not killed in defining block!");
+ while (++mi != MBB->end()) {
baseIndex += InstrSlots::NUM;
- for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi);
- ki != ke; ++ki) {
- if (interval.reg == ki->second) {
- DEBUG(std::cerr << " killed");
- end = getUseIndex(baseIndex) + 1;
- goto exit;
- }
+ if (lv_->KillsRegister(mi, interval.reg)) {
+ DEBUG(std::cerr << " killed");
+ end = getUseIndex(baseIndex) + 1;
+ goto exit;
}
}
+
+ // The only case we should have a dead physreg here without a killing or
+ // instruction where we know it's dead is if it is live-in to the function
+ // and never used.
+ assert(isLiveIn && "physreg was not killed in defining block!");
+ end = getDefIndex(start) + 1; // It's dead.
exit:
assert(start < end && "did not find end of interval?");
// 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) && !DisableHack) {
+ MRegisterInfo::isVirtualRegister(SrcReg)) {
// Get the live interval for the vreg, see if it is defined by a copy.
LiveInterval &SrcInterval = getOrCreateInterval(SrcReg);
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);
if ((TriviallyJoinable || IntB.joinable(IntA, MIDefIdx)) &&
!overlapsAliases(&IntA, &IntB)) {
IntB.join(IntA, MIDefIdx);
+ DEBUG(std::cerr << "Joined. Result = " << IntB << "\n");
if (!MRegisterInfo::isPhysicalRegister(regA)) {
r2iMap_.erase(regA);
IntA.swap(IntB);
r2iMap_.erase(regB);
}
- DEBUG(std::cerr << "Joined. Result = " << IntB << "\n");
++numJoins;
} else {
DEBUG(std::cerr << "Interference!\n");
// Get the register classes for the first reg.
if (MRegisterInfo::isPhysicalRegister(RegA)) {
- assert(MRegisterInfo::isVirtualRegister(RegB) &&
+ assert(MRegisterInfo::isVirtualRegister(RegB) &&
"Shouldn't consider two physregs!");
return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA);
}
}
LiveInterval LiveIntervals::createInterval(unsigned reg) {
- float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
+ float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
(float)HUGE_VAL :0.0F;
return LiveInterval(reg, Weight);
}
projects / oota-llvm.git / blobdiff