#define DEBUG_TYPE "liveintervals"
#include "LiveIntervals.h"
+#include "llvm/Value.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Support/CFG.h"
#include "Support/CommandLine.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
#include "VirtRegMap.h"
#include <cmath>
#include <iostream>
-#include <limits>
using namespace llvm;
unsigned miIndex = 0;
for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end();
mbb != mbbEnd; ++mbb) {
- const std::pair<MachineBasicBlock*, unsigned>& entry =
- lv_->getMachineBasicBlockInfo(mbb);
- bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second,
- entry.first)).second;
+ unsigned mbbIdx = lv_->getMachineBasicBlockIndex(mbb);
+ bool inserted = mbbi2mbbMap_.insert(std::make_pair(mbbIdx,
+ mbb)).second;
assert(inserted && "multiple index -> MachineBasicBlock");
for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
mii != mie; ) {
- for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
- const MachineOperand& mop = mii->getOperand(i);
- if (mop.isRegister() && mop.getReg()) {
- // replace register with representative register
- unsigned reg = rep(mop.getReg());
- mii->SetMachineOperandReg(i, reg);
-
- if (MRegisterInfo::isVirtualRegister(reg)) {
- Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
- assert(r2iit != r2iMap_.end());
- r2iit->second->weight += pow(10.0F, loopDepth);
- }
- }
- }
-
- // if the move is now an identity move delete it
+ // if the move will be an identity move delete it
unsigned srcReg, dstReg;
- if (tii.isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) {
+ if (tii.isMoveInstr(*mii, srcReg, dstReg) &&
+ rep(srcReg) == rep(dstReg)) {
+ // remove from def list
+ Interval& interval = getOrCreateInterval(rep(dstReg));
// remove index -> MachineInstr and
// MachineInstr -> index mappings
Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii);
mii = mbbi->erase(mii);
++numPeep;
}
- else
+ else {
+ for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
+ const MachineOperand& mop = mii->getOperand(i);
+ if (mop.isRegister() && mop.getReg() &&
+ MRegisterInfo::isVirtualRegister(mop.getReg())) {
+ // replace register with representative register
+ unsigned reg = rep(mop.getReg());
+ mii->SetMachineOperandReg(i, reg);
+
+ Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
+ assert(r2iit != r2iMap_.end());
+ r2iit->second->weight +=
+ (mop.isUse() + mop.isDef()) * pow(10.0F, loopDepth);
+ }
+ }
++mii;
+ }
}
}
- intervals_.sort(StartPointComp());
+ intervals_.sort();
DEBUG(std::cerr << "********** INTERVALS **********\n");
DEBUG(std::copy(intervals_.begin(), intervals_.end(),
std::ostream_iterator<Interval>(std::cerr, "\n")));
DEBUG(
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
mbbi != mbbe; ++mbbi) {
- std::cerr << mbbi->getBasicBlock()->getName() << ":\n";
+ std::cerr << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
for (MachineBasicBlock::iterator mii = mbbi->begin(),
mie = mbbi->end(); mii != mie; ++mii) {
std::cerr << getInstructionIndex(mii) << '\t';
return true;
}
-void LiveIntervals::updateSpilledInterval(Interval& li,
- VirtRegMap& vrm,
- int slot)
+std::vector<Interval*> LiveIntervals::addIntervalsForSpills(const Interval& li,
+ VirtRegMap& vrm,
+ int slot)
{
- assert(li.weight != std::numeric_limits<float>::infinity() &&
+ std::vector<Interval*> added;
+
+ assert(li.weight != HUGE_VAL &&
"attempt to spill already spilled interval!");
- Interval::Ranges oldRanges;
- swap(oldRanges, li.ranges);
- DEBUG(std::cerr << "\t\t\t\tupdating interval: " << li);
+ DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: "
+ << li << '\n');
- for (Interval::Ranges::iterator i = oldRanges.begin(), e = oldRanges.end();
- i != e; ++i) {
+ const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
+
+ for (Interval::Ranges::const_iterator
+ i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
unsigned index = getBaseIndex(i->first);
unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM;
for (; index < end; index += InstrSlots::NUM) {
unsigned end = 1 + (mop.isDef() ?
getUseIndex(index+InstrSlots::NUM) :
getUseIndex(index));
- li.addRange(start, end);
+
+ // create a new register for this spill
+ unsigned nReg =
+ mf_->getSSARegMap()->createVirtualRegister(rc);
+ mi->SetMachineOperandReg(i, nReg);
+ vrm.grow();
+ vrm.assignVirt2StackSlot(nReg, slot);
+ Interval& nI = getOrCreateInterval(nReg);
+ assert(nI.empty());
+ // the spill weight is now infinity as it
+ // cannot be spilled again
+ nI.weight = HUGE_VAL;
+ nI.addRange(start, end);
+ added.push_back(&nI);
+ // update live variables
+ lv_->addVirtualRegisterKilled(nReg, mi->getParent(),mi);
+ DEBUG(std::cerr << "\t\t\t\tadded new interval: "
+ << nI << '\n');
}
}
}
}
}
- // the new spill weight is now infinity as it cannot be spilled again
- li.weight = std::numeric_limits<float>::infinity();
- DEBUG(std::cerr << '\n');
- DEBUG(std::cerr << "\t\t\t\tupdated interval: " << li << '\n');
+
+ return added;
}
void LiveIntervals::printRegName(unsigned reg) const
void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- unsigned reg)
+ Interval& interval)
{
- DEBUG(std::cerr << "\t\tregister: "; printRegName(reg));
- LiveVariables::VarInfo& vi = lv_->getVarInfo(reg);
+ DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg));
+ LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
- Interval* interval = 0;
- Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg);
- if (r2iit == r2iMap_.end() || r2iit->first != reg) {
- // add new interval
- intervals_.push_back(Interval(reg));
- // update interval index for this register
- r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end()));
- interval = &intervals_.back();
-
- // iterate over all of the blocks that the variable is
- // completely live in, adding them to the live
- // interval. obviously we only need to do this once.
+ // iterate over all of the blocks that the variable is completely
+ // live in, adding them to the live interval. obviously we only
+ // need to do this once.
+ if (interval.empty()) {
for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
if (vi.AliveBlocks[i]) {
MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i);
if (!mbb->empty()) {
- interval->addRange(
+ interval.addRange(
getInstructionIndex(&mbb->front()),
getInstructionIndex(&mbb->back()) + InstrSlots::NUM);
}
}
}
}
- else {
- interval = &*r2iit->second;
- }
unsigned baseIndex = getInstructionIndex(mi);
// PHI elimination)
if (start < end) {
killedInDefiningBasicBlock |= mbb == killerBlock;
- interval->addRange(start, end);
+ interval.addRange(start, end);
}
}
if (!killedInDefiningBasicBlock) {
unsigned end = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
- interval->addRange(getDefIndex(baseIndex), end);
+ interval.addRange(getDefIndex(baseIndex), end);
}
DEBUG(std::cerr << '\n');
}
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb,
MachineBasicBlock::iterator mi,
- unsigned reg)
+ Interval& interval)
{
- DEBUG(std::cerr << "\t\tregister: "; printRegName(reg));
+ DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg));
typedef LiveVariables::killed_iterator KillIter;
MachineBasicBlock::iterator e = mbb->end();
// a variable can be dead by the instruction defining it
for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi);
ki != ke; ++ki) {
- if (reg == ki->second) {
+ if (interval.reg == ki->second) {
DEBUG(std::cerr << " dead");
end = getDefIndex(start) + 1;
goto exit;
baseIndex += InstrSlots::NUM;
for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi);
ki != ke; ++ki) {
- if (reg == ki->second) {
+ if (interval.reg == ki->second) {
DEBUG(std::cerr << " killed");
end = getUseIndex(baseIndex) + 1;
goto exit;
exit:
assert(start < end && "did not find end of interval?");
-
- Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg);
- if (r2iit != r2iMap_.end() && r2iit->first == reg) {
- r2iit->second->addRange(start, end);
- }
- else {
- intervals_.push_back(Interval(reg));
- // update interval index for this register
- r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end()));
- intervals_.back().addRange(start, end);
- }
+ interval.addRange(start, end);
DEBUG(std::cerr << '\n');
}
{
if (MRegisterInfo::isPhysicalRegister(reg)) {
if (lv_->getAllocatablePhysicalRegisters()[reg]) {
- handlePhysicalRegisterDef(mbb, mi, reg);
+ handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(reg));
for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
- handlePhysicalRegisterDef(mbb, mi, *as);
+ handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(*as));
}
}
- else {
- handleVirtualRegisterDef(mbb, mi, reg);
- }
+ else
+ handleVirtualRegisterDef(mbb, mi, getOrCreateInterval(reg));
}
unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const
{
DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n");
DEBUG(std::cerr << "********** Function: "
- << mf_->getFunction()->getName() << '\n');
+ << ((Value*)mf_->getFunction())->getName() << '\n');
for (MbbIndex2MbbMap::iterator
it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
it != itEnd; ++it) {
MachineBasicBlock* mbb = it->second;
- DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n");
+ DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n");
for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
mi != miEnd; ++mi) {
for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
mbbi != mbbe; ++mbbi) {
MachineBasicBlock* mbb = mbbi;
- DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n");
+ DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n");
for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end();
mi != mie; ++mi) {
"A must be physical and B must be virtual");
if (!intA->overlaps(*intB) &&
- !overlapsAliases(*intA, *intB)) {
+ !overlapsAliases(*intA, *intB)) {
intA->join(*intB);
r2iB->second = r2iA->second;
r2rMap_.insert(std::make_pair(intB->reg, intA->reg));
return false;
}
-LiveIntervals::Interval::Interval(unsigned r)
- : reg(r),
- weight((MRegisterInfo::isPhysicalRegister(r) ?
- std::numeric_limits<float>::infinity() : 0.0F))
+Interval& LiveIntervals::getOrCreateInterval(unsigned reg)
{
+ Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg);
+ if (r2iit == r2iMap_.end() || r2iit->first != reg) {
+ intervals_.push_back(Interval(reg));
+ r2iit = r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end()));
+ }
+ return *r2iit->second;
}
-bool LiveIntervals::Interval::spilled() const
+Interval::Interval(unsigned r)
+ : reg(r),
+ weight((MRegisterInfo::isPhysicalRegister(r) ? HUGE_VAL : 0.0F))
{
- return (weight == std::numeric_limits<float>::infinity() &&
+}
+
+bool Interval::spilled() const
+{
+ return (weight == HUGE_VAL &&
MRegisterInfo::isVirtualRegister(reg));
}
// definition of the variable it represents. This is because slot 1 is
// used (def slot) and spans up to slot 3 (store slot).
//
-bool LiveIntervals::Interval::liveAt(unsigned index) const
+bool Interval::liveAt(unsigned index) const
{
Range dummy(index, index+1);
Ranges::const_iterator r = std::upper_bound(ranges.begin(),
//
// A->overlaps(C) should return false since we want to be able to join
// A and C.
-bool LiveIntervals::Interval::overlaps(const Interval& other) const
+bool Interval::overlaps(const Interval& other) const
{
Ranges::const_iterator i = ranges.begin();
Ranges::const_iterator ie = ranges.end();
return false;
}
-void LiveIntervals::Interval::addRange(unsigned start, unsigned end)
+void Interval::addRange(unsigned start, unsigned end)
{
assert(start < end && "Invalid range to add!");
DEBUG(std::cerr << " +[" << start << ',' << end << ")");
it = mergeRangesBackward(it);
}
-void LiveIntervals::Interval::join(const LiveIntervals::Interval& other)
+void Interval::join(const Interval& other)
{
DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other << '\n');
Ranges::iterator cur = ranges.begin();
++numJoins;
}
-LiveIntervals::Interval::Ranges::iterator
-LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it)
+Interval::Ranges::iterator Interval::mergeRangesForward(Ranges::iterator it)
{
Ranges::iterator n;
while ((n = next(it)) != ranges.end()) {
return it;
}
-LiveIntervals::Interval::Ranges::iterator
-LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it)
+Interval::Ranges::iterator Interval::mergeRangesBackward(Ranges::iterator it)
{
while (it != ranges.begin()) {
Ranges::iterator p = prior(it);
return it;
}
-std::ostream& llvm::operator<<(std::ostream& os,
- const LiveIntervals::Interval& li)
+std::ostream& llvm::operator<<(std::ostream& os, const Interval& li)
{
- os << "%reg" << li.reg << ',' << li.weight << " = ";
+ os << "%reg" << li.reg << ',' << li.weight;
if (li.empty())
return os << "EMPTY";
- for (LiveIntervals::Interval::Ranges::const_iterator
+
+ os << " = ";
+ for (Interval::Ranges::const_iterator
i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
os << "[" << i->first << "," << i->second << ")";
}
projects / oota-llvm.git / blobdiff