#define DEBUG_TYPE "liveintervals"
#include "LiveIntervalAnalysis.h"
+#include "VirtRegMap.h"
#include "llvm/Value.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "Support/CommandLine.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
-#include "Support/STLExtras.h"
-#include "VirtRegMap.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
#include <cmath>
-
using namespace llvm;
namespace {
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;
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;
}
}
- DEBUG(std::cerr << "********** INTERVALS **********\n");
- DEBUG (for (iterator I = begin(), E = end(); I != E; ++I)
- std::cerr << I->second << "\n");
- DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
- DEBUG(
- for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
- mbbi != mbbe; ++mbbi) {
- std::cerr << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
- for (MachineBasicBlock::iterator mii = mbbi->begin(),
- mie = mbbi->end(); mii != mie; ++mii) {
- std::cerr << getInstructionIndex(mii) << '\t';
- mii->print(std::cerr, tm_);
- }
- });
-
+ DEBUG(dump());
return true;
}
-std::vector<LiveInterval*> LiveIntervals::addIntervalsForSpills(
- const LiveInterval& li,
- VirtRegMap& vrm,
- int slot)
-{
+/// 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";
+
+ O << "********** MACHINEINSTRS **********\n";
+ for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
+ mbbi != mbbe; ++mbbi) {
+ O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
+ for (MachineBasicBlock::iterator mii = mbbi->begin(),
+ mie = mbbi->end(); mii != mie; ++mii) {
+ O << getInstructionIndex(mii) << '\t' << *mii;
+ }
+ }
+}
+
+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
+ // LiveVariables is available
+ lv_ = getAnalysisToUpdate<LiveVariables>();
+
std::vector<LiveInterval*> added;
assert(li.weight != HUGE_VAL &&
for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
MachineOperand& mop = mi->getOperand(i);
if (mop.isRegister() && mop.getReg() == li.reg) {
- if (MachineInstr* fmi =
- mri_->foldMemoryOperand(mi, i, slot)) {
- lv_->instructionChanged(mi, fmi);
- vrm.virtFolded(li.reg, mi, fmi);
+ // 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 (lv_)
+ lv_->instructionChanged(mi, fmi);
+ vrm.virtFolded(li.reg, mi, i, fmi);
mi2iMap_.erase(mi);
i2miMap_[index/InstrSlots::NUM] = fmi;
mi2iMap_[fmi] = index;
- MachineBasicBlock& mbb = *mi->getParent();
- mi = mbb.insert(mbb.erase(mi), fmi);
+ MachineBasicBlock &MBB = *mi->getParent();
+ mi = MBB.insert(MBB.erase(mi), fmi);
++numFolded;
+
+ // Folding the load/store can completely change the instruction in
+ // unpredictable ways, rescan it from the beginning.
goto for_operand;
- }
- else {
- // This is tricky. We need to add information in
- // the interval about the spill code so we have to
- // use our extra load/store slots.
+ } else {
+ // This is tricky. We need to add information in the interval about
+ // the spill code so we have to use our extra load/store slots.
//
- // If we have a use we are going to have a load so
- // we start the interval from the load slot
- // onwards. Otherwise we start from the def slot.
+ // If we have a use we are going to have a load so we start the
+ // interval from the load slot onwards. Otherwise we start from the
+ // def slot.
unsigned start = (mop.isUse() ?
getLoadIndex(index) :
getDefIndex(index));
- // If we have a def we are going to have a store
- // right after it so we end the interval after the
- // use of the next instruction. Otherwise we end
- // after the use of this instruction.
+ // If we have a def we are going to have a store right after it so
+ // we end the interval after the use of the next
+ // instruction. Otherwise we end after the use of this instruction.
unsigned end = 1 + (mop.isDef() ?
getStoreIndex(index) :
getUseIndex(index));
// create a new register for this spill
- unsigned nReg =
- mf_->getSSARegMap()->createVirtualRegister(rc);
+ unsigned nReg = mf_->getSSARegMap()->createVirtualRegister(rc);
mi->SetMachineOperandReg(i, nReg);
vrm.grow();
vrm.assignVirt2StackSlot(nReg, slot);
LiveInterval& nI = getOrCreateInterval(nReg);
assert(nI.empty());
+
// 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);
added.push_back(&nI);
- // update live variables
- lv_->addVirtualRegisterKilled(nReg, mi);
- DEBUG(std::cerr << "\t\t\t\tadded new interval: "
- << nI << '\n');
+
+ // update live variables if it is available
+ if (lv_)
+ lv_->addVirtualRegisterKilled(nReg, mi);
+ DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n');
}
}
}
DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg));
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
- // Virtual registers may be defined multiple times (due to phi
- // elimination and 2-addr elimination). Much of what we do only has to be
- // done once for the vreg. We use an empty interval to detect the first
+ // Virtual registers may be defined multiple times (due to phi
+ // elimination and 2-addr elimination). Much of what we do only has to be
+ // done once for the vreg. We use an empty interval to detect the first
// time we see a vreg.
if (interval.empty()) {
// Get the Idx of the defining instructions.
// If the kill happens after the definition, we have an intra-block
// live range.
if (killIdx > defIndex) {
- assert(vi.AliveBlocks.empty() &&
+ assert(vi.AliveBlocks.empty() &&
"Shouldn't be alive across any blocks!");
LiveRange LR(defIndex, killIdx, ValNum);
interval.addRange(LR);
// of the defining block, potentially live across some blocks, then is
// live into some number of blocks, but gets killed. Start by adding a
// range that goes from this definition to the end of the defining block.
- LiveRange NewLR(defIndex, getInstructionIndex(&mbb->back()) +
- InstrSlots::NUM, ValNum);
+ LiveRange NewLR(defIndex,
+ getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
+ ValNum);
DEBUG(std::cerr << " +" << NewLR);
interval.addRange(NewLR);
MachineBasicBlock* mbb = mf_->getBlockNumbered(i);
if (!mbb->empty()) {
LiveRange LR(getInstructionIndex(&mbb->front()),
- getInstructionIndex(&mbb->back())+InstrSlots::NUM,
+ getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
ValNum);
interval.addRange(LR);
DEBUG(std::cerr << " +" << LR);
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
LiveRange LR(getInstructionIndex(Kill->getParent()->begin()),
- getUseIndex(getInstructionIndex(Kill))+1, ValNum);
+ getUseIndex(getInstructionIndex(Kill))+1,
+ ValNum);
interval.addRange(LR);
DEBUG(std::cerr << " +" << LR);
}
// must be due to phi elimination or two addr elimination. If this is
// the result of two address elimination, then the vreg is the first
// operand, and is a def-and-use.
- if (mi->getOperand(0).isRegister() &&
+ if (mi->getOperand(0).isRegister() &&
mi->getOperand(0).getReg() == interval.reg &&
mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) {
// If this is a two-address definition, then we have already processed
// Delete the initial value, which should be short and continuous,
// becuase the 2-addr copy must be in the same MBB as the redef.
interval.removeRange(DefIndex, RedefIndex);
-
+
LiveRange LR(DefIndex, RedefIndex, interval.getNextValue());
DEBUG(std::cerr << " replace range with " << LR);
interval.addRange(LR);
// live until the end of the block. We've already taken care of the
// rest of the live range.
unsigned defIndex = getDefIndex(getInstructionIndex(mi));
- LiveRange LR(defIndex,
+ LiveRange LR(defIndex,
getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
interval.getNextValue());
interval.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');
unsigned reg) {
if (MRegisterInfo::isVirtualRegister(reg))
handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg));
- else if (lv_->getAllocatablePhysicalRegisters()[reg]) {
- handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg));
+ else if (allocatableRegs_[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();
+ 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->print(std::cerr, tm_));
+ DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi);
// handle implicit defs
for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
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) &&
- (MRegisterInfo::isVirtualRegister(regA) ||
- lv_->getAllocatablePhysicalRegisters()[regA]) &&
- (MRegisterInfo::isVirtualRegister(regB) ||
- lv_->getAllocatablePhysicalRegisters()[regB])) {
-
+ if (tii_->isMoveInstr(*mi, regA, regB) &&
+ (MRegisterInfo::isVirtualRegister(regA) || allocatableRegs_[regA]) &&
+ (MRegisterInfo::isVirtualRegister(regB) || allocatableRegs_[regB])) {
+
// Get representative registers.
regA = rep(regA);
regB = rep(regB);
-
+
// If they are already joined we continue.
if (regA == regB)
continue;
-
+
// If they are both physical registers, we cannot join them.
- if (MRegisterInfo::isPhysicalRegister(regA) &&
+ if (MRegisterInfo::isPhysicalRegister(regA) &&
MRegisterInfo::isPhysicalRegister(regB))
continue;
typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
if (LHS.first > RHS.first) return true; // Deeper loops first
- return LHS.first == RHS.first &&
+ return LHS.first == RHS.first &&
LHS.second->getNumber() < RHS.second->getNumber();
}
};
// Sort by loop depth.
std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
- // Finally, join intervals in loop nest order.
+ // Finally, join intervals in loop nest order.
for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
joinIntervalsInMachineBB(MBBs[i].second);
}
DEBUG(std::cerr << "*** Register mapping ***\n");
- DEBUG(for (std::map<unsigned, unsigned>::iterator I = r2rMap_.begin(),
- E = r2rMap_.end(); I != E; ++I)
- std::cerr << " reg " << I->first << " -> reg " << I->second << "\n";);
+ DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i)
+ if (r2rMap_[i])
+ std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n");
}
/// Return true if the two specified registers belong to different register
/// 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
- return RegClass != mri_->getRegClass(RegB);
+ return !RegClass->contains(RegB);
}
bool LiveIntervals::overlapsAliases(const LiveInterval *LHS,
}
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);
}
-
projects / oota-llvm.git / blobdiff