//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "liveintervals"
-#include "llvm/CodeGen/LiveIntervals.h"
+#include "LiveIntervals.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
#include "Support/STLExtras.h"
+#include "VirtRegMap.h"
#include <cmath>
#include <iostream>
#include <limits>
RegisterAnalysis<LiveIntervals> X("liveintervals",
"Live Interval Analysis");
- Statistic<> numIntervals("liveintervals", "Number of intervals");
- Statistic<> numJoined ("liveintervals", "Number of intervals after "
- "coalescing");
- Statistic<> numJoins ("liveintervals", "Number of interval joins "
- "performed");
- Statistic<> numPeep ("liveintervals", "Number of identity moves "
- "eliminated after coalescing");
- Statistic<> numFolded ("liveintervals", "Number of register operands "
- "folded");
+ Statistic<> numIntervals
+ ("liveintervals", "Number of original intervals");
+
+ Statistic<> numIntervalsAfter
+ ("liveintervals", "Number of intervals after coalescing");
+
+ Statistic<> numJoins
+ ("liveintervals", "Number of interval joins performed");
+
+ Statistic<> numPeep
+ ("liveintervals", "Number of identity moves eliminated after coalescing");
+
+ Statistic<> numFolded
+ ("liveintervals", "Number of loads/stores folded into instructions");
+
cl::opt<bool>
join("join-liveintervals",
cl::desc("Join compatible live intervals"),
// join intervals if requested
if (join) joinIntervals();
+ numIntervalsAfter += intervals_.size();
+
// perform a final pass over the instructions and compute spill
// weights, coalesce virtual registers and remove identity moves
const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
mii != mie; ) {
for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
const MachineOperand& mop = mii->getOperand(i);
- if (mop.isRegister()) {
+ if (mop.isRegister() && mop.getReg()) {
// replace register with representative register
unsigned reg = rep(mop.getReg());
mii->SetMachineOperandReg(i, reg);
std::ostream_iterator<Interval>(std::cerr, "\n")));
DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
DEBUG(
- for (unsigned i = 0; i != i2miMap_.size(); ++i) {
- if (const MachineInstr* mi = i2miMap_[i]) {
- std:: cerr << i * InstrSlots::NUM << '\t';
- mi->print(std::cerr, *tm_);
+ for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
+ mbbi != mbbe; ++mbbi) {
+ std::cerr << 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_);
}
});
return true;
}
-void LiveIntervals::updateSpilledInterval(Interval& li, int slot)
+void LiveIntervals::updateSpilledInterval(Interval& li,
+ VirtRegMap& vrm,
+ int slot)
{
assert(li.weight != std::numeric_limits<float>::infinity() &&
"attempt to spill already spilled interval!");
while (!getInstructionFromIndex(index)) index += InstrSlots::NUM;
MachineBasicBlock::iterator mi = getInstructionFromIndex(index);
+ for_operand:
for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
MachineOperand& mop = mi->getOperand(i);
if (mop.isRegister() && mop.getReg() == li.reg) {
- // 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.
- 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.
- unsigned end = 1 + (mop.isDef() ?
- getUseIndex(index+InstrSlots::NUM) :
- getUseIndex(index));
- li.addRange(start, end);
+ MachineInstr* old = mi;
+ if (mri_->foldMemoryOperand(mi, i, slot)) {
+ lv_->instructionChanged(old, mi);
+ vrm.virtFolded(li.reg, old, mi);
+ mi2iMap_.erase(old);
+ i2miMap_[index/InstrSlots::NUM] = mi;
+ mi2iMap_[mi] = index;
+ ++numFolded;
+ 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.
+ //
+ // 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.
+ unsigned end = 1 + (mop.isDef() ?
+ getUseIndex(index+InstrSlots::NUM) :
+ getUseIndex(index));
+ li.addRange(start, end);
+ }
}
}
}
// 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');
}
void LiveIntervals::printRegName(unsigned reg) const
for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
MachineOperand& mop = mi->getOperand(i);
// handle register defs - build intervals
- if (mop.isRegister() && mop.isDef())
+ if (mop.isRegister() && mop.getReg() && mop.isDef())
handleRegisterDef(mbb, mi, mop.getReg());
}
}
r2iB->second = r2iA->second;
r2rMap_.insert(std::make_pair(intB->reg, intA->reg));
intervals_.erase(intB);
- ++numJoined;
}
}
else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^
r2iB->second = r2iA->second;
r2rMap_.insert(std::make_pair(intB->reg, intA->reg));
intervals_.erase(intB);
- ++numJoined;
}
}
}
LiveIntervals::Interval::Ranges::iterator
LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it)
{
- for (Ranges::iterator n = next(it);
- n != ranges.end() && ((it->second & 1) + it->second) >= n->first; ) {
+ Ranges::iterator n;
+ while ((n = next(it)) != ranges.end()) {
+ if (n->first > it->second)
+ break;
it->second = std::max(it->second, n->second);
n = ranges.erase(n);
}
{
while (it != ranges.begin()) {
Ranges::iterator p = prior(it);
- if (it->first > ((p->second & 1) + p->second)) break;
+ if (it->first > p->second)
+ break;
it->first = std::min(it->first, p->first);
it->second = std::max(it->second, p->second);