diff options
| -rw-r--r-- | include/llvm/CodeGen/LiveIntervalAnalysis.h | 34 | ||||
| -rw-r--r-- | include/llvm/CodeGen/LiveIntervals.h | 34 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 160 | ||||
| -rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.h | 34 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 232 |
5 files changed, 324 insertions, 170 deletions
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 5aea679b57..3769f07de7 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -44,6 +44,8 @@ namespace llvm { bool empty() const { return ranges.empty(); } + bool spilled() const; + unsigned start() const { assert(!empty() && "empty interval for register"); return ranges.front().first; @@ -112,6 +114,33 @@ namespace llvm { Intervals intervals_; public: + struct InstrSlots + { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4, + }; + }; + + static unsigned getBaseIndex(unsigned index) { + return index - (index % 4); + } + static unsigned getLoadIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::LOAD; + } + static unsigned getUseIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::USE; + } + static unsigned getDefIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::DEF; + } + static unsigned getStoreIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::STORE; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); @@ -123,13 +152,16 @@ namespace llvm { return *r2iMap_.find(reg)->second; } + /// getInstructionIndex - returns the base index of instr unsigned getInstructionIndex(MachineInstr* instr) const; + /// getInstructionFromIndex - given an index in any slot of an + /// instruction return a pointer the instruction MachineInstr* getInstructionFromIndex(unsigned index) const; Intervals& getIntervals() { return intervals_; } - void updateSpilledInterval(Interval& i); + void updateSpilledInterval(Interval& i, int slot); private: /// computeIntervals - compute live intervals diff --git a/include/llvm/CodeGen/LiveIntervals.h b/include/llvm/CodeGen/LiveIntervals.h index 5aea679b57..3769f07de7 100644 --- a/include/llvm/CodeGen/LiveIntervals.h +++ b/include/llvm/CodeGen/LiveIntervals.h @@ -44,6 +44,8 @@ namespace llvm { bool empty() const { return ranges.empty(); } + bool spilled() const; + unsigned start() const { assert(!empty() && "empty interval for register"); return ranges.front().first; @@ -112,6 +114,33 @@ namespace llvm { Intervals intervals_; public: + struct InstrSlots + { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4, + }; + }; + + static unsigned getBaseIndex(unsigned index) { + return index - (index % 4); + } + static unsigned getLoadIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::LOAD; + } + static unsigned getUseIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::USE; + } + static unsigned getDefIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::DEF; + } + static unsigned getStoreIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::STORE; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); @@ -123,13 +152,16 @@ namespace llvm { return *r2iMap_.find(reg)->second; } + /// getInstructionIndex - returns the base index of instr unsigned getInstructionIndex(MachineInstr* instr) const; + /// getInstructionFromIndex - given an index in any slot of an + /// instruction return a pointer the instruction MachineInstr* getInstructionFromIndex(unsigned index) const; Intervals& getIntervals() { return intervals_; } - void updateSpilledInterval(Interval& i); + void updateSpilledInterval(Interval& i, int slot); private: /// computeIntervals - compute live intervals diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 91de847e07..55c0370ad2 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -45,7 +45,8 @@ namespace { Statistic<> numJoined ("liveintervals", "Number of joined intervals"); Statistic<> numPeep ("liveintervals", "Number of identity moves " "eliminated after coalescing"); - + Statistic<> numFolded ("liveintervals", "Number of register operands " + "folded"); cl::opt<bool> join("join-liveintervals", cl::desc("Join compatible live intervals"), @@ -77,7 +78,6 @@ void LiveIntervals::releaseMemory() /// runOnMachineFunction - Register allocate the whole function /// bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { - DEBUG(std::cerr << "MACHINE FUNCTION: "; fn.print(std::cerr)); mf_ = &fn; tm_ = &fn.getTarget(); mri_ = tm_->getRegisterInfo(); @@ -98,7 +98,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; assert(inserted && "multiple MachineInstr -> index mappings"); i2miMap_.push_back(mi); - miIndex += 2; + miIndex += InstrSlots::NUM; } } @@ -143,7 +143,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { // MachineInstr -> index mappings Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); if (mi2i != mi2iMap_.end()) { - i2miMap_[mi2i->second/2] = 0; + i2miMap_[mi2i->second/InstrSlots::NUM] = 0; mi2iMap_.erase(mi2i); } mii = mbbi->erase(mii); @@ -155,14 +155,14 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { } intervals_.sort(StartPointComp()); - DEBUG(std::cerr << "*** INTERVALS ***\n"); + DEBUG(std::cerr << "********** INTERVALS **********\n"); DEBUG(std::copy(intervals_.begin(), intervals_.end(), std::ostream_iterator<Interval>(std::cerr, "\n"))); - DEBUG(std::cerr << "*** MACHINEINSTRS ***\n"); + DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); DEBUG( for (unsigned i = 0; i != i2miMap_.size(); ++i) { if (const MachineInstr* mi = i2miMap_[i]) { - std:: cerr << i*2 << '\t'; + std:: cerr << i * InstrSlots::NUM << '\t'; mi->print(std::cerr, *tm_); } }); @@ -170,37 +170,52 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { return true; } -void LiveIntervals::updateSpilledInterval(Interval& li) +void LiveIntervals::updateSpilledInterval(Interval& li, int slot) { assert(li.weight != std::numeric_limits<float>::infinity() && "attempt to spill already spilled interval!"); Interval::Ranges oldRanges; swap(oldRanges, li.ranges); + DEBUG(std::cerr << "\t\t\t\tupdating interval: " << li); + for (Interval::Ranges::iterator i = oldRanges.begin(), e = oldRanges.end(); i != e; ++i) { - unsigned index = i->first & ~1; - unsigned end = i->second; - - for (; index < end; index += 2) { + unsigned index = getBaseIndex(i->first); + unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM; + for (; index < end; index += InstrSlots::NUM) { // skip deleted instructions - while (!getInstructionFromIndex(index)) index += 2; - MachineInstr* mi = getInstructionFromIndex(index); + while (!getInstructionFromIndex(index)) index += InstrSlots::NUM; + MachineBasicBlock::iterator mi = getInstructionFromIndex(index); + for (unsigned i = 0; i < mi->getNumOperands(); ++i) { MachineOperand& mop = mi->getOperand(i); - if (mop.isRegister()) { - unsigned reg = mop.getReg(); - if (rep(reg) == li.reg) { - unsigned start = mop.isUse() ? index : index+1; - unsigned end = mop.isDef() ? index+2 : index+1; - li.addRange(start, end); - } + 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); } } } } // the new spill weight is now infinity as it cannot be spilled again li.weight = std::numeric_limits<float>::infinity(); + DEBUG(std::cerr << '\n'); } void LiveIntervals::printRegName(unsigned reg) const @@ -208,15 +223,14 @@ void LiveIntervals::printRegName(unsigned reg) const if (MRegisterInfo::isPhysicalRegister(reg)) std::cerr << mri_->getName(reg); else - std::cerr << '%' << reg; + std::cerr << "%reg" << reg; } void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, MachineBasicBlock::iterator mi, unsigned reg) { - DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); - + DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); Interval* interval = 0; @@ -235,8 +249,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, if (vi.AliveBlocks[i]) { MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); if (!mbb->empty()) { - interval->addRange(getInstructionIndex(&mbb->front()), - getInstructionIndex(&mbb->back()) + 1); + interval->addRange( + getInstructionIndex(&mbb->front()), + getInstructionIndex(&mbb->back()) + InstrSlots::NUM); } } } @@ -245,20 +260,20 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, interval = &*r2iit->second; } - // we consider defs to happen at the second time slot of the - // instruction - unsigned instrIndex = getInstructionIndex(mi) + 1; + unsigned baseIndex = getInstructionIndex(mi); bool killedInDefiningBasicBlock = false; for (int i = 0, e = vi.Kills.size(); i != e; ++i) { MachineBasicBlock* killerBlock = vi.Kills[i].first; MachineInstr* killerInstr = vi.Kills[i].second; unsigned start = (mbb == killerBlock ? - instrIndex : + getDefIndex(baseIndex) : getInstructionIndex(&killerBlock->front())); unsigned end = (killerInstr == mi ? - instrIndex + 1 : // dead - getInstructionIndex(killerInstr) + 1); // killed + // dead + start + 1 : + // killed + getUseIndex(getInstructionIndex(killerInstr))+1); // we do not want to add invalid ranges. these can happen when // a variable has its latest use and is redefined later on in // the same basic block (common with variables introduced by @@ -270,31 +285,30 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, } if (!killedInDefiningBasicBlock) { - unsigned end = getInstructionIndex(&mbb->back()) + 1; - interval->addRange(instrIndex, end); + unsigned end = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; + interval->addRange(getDefIndex(baseIndex), end); } + DEBUG(std::cerr << '\n'); } void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, MachineBasicBlock::iterator mi, unsigned reg) { - typedef LiveVariables::killed_iterator KillIter; - DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); + typedef LiveVariables::killed_iterator KillIter; MachineBasicBlock::iterator e = mbb->end(); - // we consider defs to happen at the second time slot of the - // instruction - unsigned start, end; - start = end = getInstructionIndex(mi) + 1; + unsigned baseIndex = getInstructionIndex(mi); + unsigned start = getDefIndex(baseIndex); + unsigned end = start; // 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) { - DEBUG(std::cerr << " dead\n"); - ++end; + DEBUG(std::cerr << " dead"); + end = getDefIndex(start) + 1; goto exit; } } @@ -302,11 +316,12 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, // a variable can only be killed by subsequent instructions do { ++mi; - end += 2; + baseIndex += InstrSlots::NUM; for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); ki != ke; ++ki) { if (reg == ki->second) { - DEBUG(std::cerr << " killed\n"); + DEBUG(std::cerr << " killed"); + end = getUseIndex(baseIndex) + 1; goto exit; } } @@ -325,6 +340,7 @@ exit: r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); intervals_.back().addRange(start, end); } + DEBUG(std::cerr << '\n'); } void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, @@ -346,12 +362,14 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const { Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); - return it == mi2iMap_.end() ? std::numeric_limits<unsigned>::max() : it->second; + return (it == mi2iMap_.end() ? + std::numeric_limits<unsigned>::max() : + it->second); } MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const { - index /= 2; // convert index to vector index + index /= InstrSlots::NUM; // convert index to vector index assert(index < i2miMap_.size() && "index does not correspond to an instruction"); return i2miMap_[index]; @@ -363,7 +381,9 @@ MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const /// which a variable is live void LiveIntervals::computeIntervals() { - DEBUG(std::cerr << "*** COMPUTING LIVE INTERVALS ***\n"); + DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_->getFunction()->getName() << '\n'); for (MbbIndex2MbbMap::iterator it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); @@ -375,8 +395,8 @@ void LiveIntervals::computeIntervals() 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->print(std::cerr, *tm_)); // handle implicit defs for (const unsigned* id = tid.ImplicitDefs; *id; ++id) @@ -403,7 +423,7 @@ unsigned LiveIntervals::rep(unsigned reg) void LiveIntervals::joinIntervals() { - DEBUG(std::cerr << "** JOINING INTERVALS ***\n"); + DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); const TargetInstrInfo& tii = tm_->getInstrInfo(); @@ -416,7 +436,7 @@ void LiveIntervals::joinIntervals() mi != mie; ++mi) { const TargetInstrDescriptor& tid = tm_->getInstrInfo().get(mi->getOpcode()); - DEBUG(std::cerr << "[" << getInstructionIndex(mi) << "]\t"; + DEBUG(std::cerr << getInstructionIndex(mi) << '\t'; mi->print(std::cerr, *tm_);); // we only join virtual registers with allocatable @@ -513,17 +533,19 @@ LiveIntervals::Interval::Interval(unsigned r) } +bool LiveIntervals::Interval::spilled() const +{ + return (weight == std::numeric_limits<float>::infinity() && + MRegisterInfo::isVirtualRegister(reg)); +} + // An example for liveAt(): // -// this = [1,2), liveAt(0) will return false. The instruction defining -// this spans slots [0,1]. Since it is a definition we say that it is -// live in the second slot onwards. By ending the lifetime of this -// interval at 2 it means that it is not used at all. liveAt(1) -// returns true which means that this clobbers a register at -// instruction at 0. +// this = [1,4), liveAt(0) will return false. The instruction defining +// this spans slots [0,3]. The interval belongs to an spilled +// definition of the variable it represents. This is because slot 1 is +// used (def slot) and spans up to slot 3 (store slot). // -// this = [1,4), liveAt(0) will return false and liveAt(2) will return -// true. The variable is defined at instruction 0 and last used at 2. bool LiveIntervals::Interval::liveAt(unsigned index) const { Range dummy(index, index+1); @@ -540,14 +562,14 @@ bool LiveIntervals::Interval::liveAt(unsigned index) const // An example for overlaps(): // // 0: A = ... -// 2: B = ... -// 4: C = A + B ;; last use of A +// 4: B = ... +// 8: C = A + B ;; last use of A // // The live intervals should look like: // -// A = [1, 5) -// B = [3, x) -// C = [5, y) +// A = [3, 11) +// B = [7, x) +// C = [11, y) // // A->overlaps(C) should return false since we want to be able to join // A and C. @@ -592,7 +614,7 @@ bool LiveIntervals::Interval::overlaps(const Interval& other) const void LiveIntervals::Interval::addRange(unsigned start, unsigned end) { assert(start < end && "Invalid range to add!"); - DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); + DEBUG(std::cerr << " +[" << start << ',' << end << ")"); //assert(start < end && "invalid range?"); Range range = std::make_pair(start, end); Ranges::iterator it = @@ -601,13 +623,11 @@ void LiveIntervals::Interval::addRange(unsigned start, unsigned end) it = mergeRangesForward(it); it = mergeRangesBackward(it); - DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); } void LiveIntervals::Interval::join(const LiveIntervals::Interval& other) { - DEBUG(std::cerr << "\t\t\t\tjoining intervals: " - << other << " and " << *this << '\n'); + DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other << '\n'); Ranges::iterator cur = ranges.begin(); for (Ranges::const_iterator i = other.ranges.begin(), @@ -618,8 +638,6 @@ void LiveIntervals::Interval::join(const LiveIntervals::Interval& other) } if (MRegisterInfo::isVirtualRegister(reg)) weight += other.weight; - - DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); } LiveIntervals::Interval::Ranges::iterator @@ -652,6 +670,8 @@ std::ostream& llvm::operator<<(std::ostream& os, const LiveIntervals::Interval& li) { os << "%reg" << li.reg << ',' << li.weight << " = "; + if (li.empty()) + return os << "EMPTY"; for (LiveIntervals::Interval::Ranges::const_iterator i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { os << "[" << i->first << "," << i->second << ")"; diff --git a/lib/CodeGen/LiveIntervalAnalysis.h b/lib/CodeGen/LiveIntervalAnalysis.h index 5aea679b57..3769f07de7 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.h +++ b/lib/CodeGen/LiveIntervalAnalysis.h @@ -44,6 +44,8 @@ namespace llvm { bool empty() const { return ranges.empty(); } + bool spilled() const; + unsigned start() const { assert(!empty() && "empty interval for register"); return ranges.front().first; @@ -112,6 +114,33 @@ namespace llvm { Intervals intervals_; public: + struct InstrSlots + { + enum { + LOAD = 0, + USE = 1, + DEF = 2, + STORE = 3, + NUM = 4, + }; + }; + + static unsigned getBaseIndex(unsigned index) { + return index - (index % 4); + } + static unsigned getLoadIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::LOAD; + } + static unsigned getUseIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::USE; + } + static unsigned getDefIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::DEF; + } + static unsigned getStoreIndex(unsigned index) { + return getBaseIndex(index) + InstrSlots::STORE; + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); @@ -123,13 +152,16 @@ namespace llvm { return *r2iMap_.find(reg)->second; } + /// getInstructionIndex - returns the base index of instr unsigned getInstructionIndex(MachineInstr* instr) const; + /// getInstructionFromIndex - given an index in any slot of an + /// instruction return a pointer the instruction MachineInstr* getInstructionFromIndex(unsigned index) const; Intervals& getIntervals() { return intervals_; } - void updateSpilledInterval(Interval& i); + void updateSpilledInterval(Interval& i, int slot); private: /// computeIntervals - compute live intervals diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 67adeb5e7e..ab40e6fdae 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -85,6 +85,7 @@ namespace { private: MachineFunction* mf_; const TargetMachine* tm_; + const TargetInstrInfo* tii_; const MRegisterInfo* mri_; LiveIntervals* li_; typedef std::list<LiveIntervals::Interval*> IntervalPtrs; @@ -182,12 +183,12 @@ namespace { for (Virt2PhysMap::const_iterator i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) { assert(i->second != 0); - std::cerr << '[' << i->first << ',' + std::cerr << "[reg" << i->first << " -> " << mri_->getName(i->second) << "]\n"; } for (Virt2StackSlotMap::const_iterator i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) { - std::cerr << '[' << i->first << ",ss#" << i->second << "]\n"; + std::cerr << '[' << i->first << " -> ss#" << i->second << "]\n"; } std::cerr << '\n'; } @@ -197,7 +198,7 @@ namespace { RA::IntervalPtrs::const_iterator e) const { if (str) std::cerr << str << " intervals:\n"; for (; i != e; ++i) { - std::cerr << "\t\t" << **i << " -> "; + std::cerr << "\t" << **i << " -> "; unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg)) { Virt2PhysMap::const_iterator it = v2pMap_.find(reg); @@ -240,6 +241,7 @@ void RA::releaseMemory() bool RA::runOnMachineFunction(MachineFunction &fn) { mf_ = &fn; tm_ = &fn.getTarget(); + tii_ = &tm_->getInstrInfo(); mri_ = tm_->getRegisterInfo(); li_ = &getAnalysis<LiveIntervals>(); prt_ = PhysRegTracker(mf_); @@ -247,12 +249,14 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { initIntervalSets(li_->getIntervals()); // linear scan algorithm - DEBUG(std::cerr << "Machine Function\n"); + DEBUG(std::cerr << "********** LINEAR SCAN **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_->getFunction()->getName() << '\n'); - DEBUG(printIntervals("\tunhandled", unhandled_.begin(), unhandled_.end())); - DEBUG(printIntervals("\tfixed", fixed_.begin(), fixed_.end())); - DEBUG(printIntervals("\tactive", active_.begin(), active_.end())); - DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end())); + DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end())); + DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); + DEBUG(printIntervals("active", active_.begin(), active_.end())); + DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); while (!unhandled_.empty() || !fixed_.empty()) { // pick the interval with the earliest start point @@ -274,7 +278,7 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { fixed_.pop_front(); } - DEBUG(std::cerr << *cur << '\n'); + DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n'); processActiveIntervals(cur); processInactiveIntervals(cur); @@ -292,13 +296,15 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { assignRegOrStackSlotAtInterval(cur); } - DEBUG(printIntervals("\tactive", active_.begin(), active_.end())); - DEBUG(printIntervals("\tinactive", inactive_.begin(), inactive_.end())); } + DEBUG(printIntervals("active", active_.begin(), active_.end())); + DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); + // DEBUG(verifyAssignment()); + } // expire any remaining active intervals for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { unsigned reg = (*i)->reg; - DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); + DEBUG(std::cerr << "\tinterval " << **i << " expired\n"); if (MRegisterInfo::isVirtualRegister(reg)) { reg = v2pMap_[reg]; } @@ -306,25 +312,30 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { } DEBUG(printVirtRegAssignment()); - DEBUG(std::cerr << "finished register allocation\n"); - // this is a slow operations do not uncomment - // DEBUG(verifyAssignment()); - const TargetInstrInfo& tii = tm_->getInstrInfo(); + DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); + DEBUG(std::cerr << "********** Function: " + << mf_->getFunction()->getName() << '\n'); - DEBUG(std::cerr << "Rewrite machine code:\n"); for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { instrAdded_ = 0; for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end(); mii != mie; ++mii) { - DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_)); + DEBUG( + std::cerr << '['; + unsigned index = li_->getInstructionIndex(mii); + if (index == std::numeric_limits<unsigned>::max()) + std::cerr << '*'; + else + std::cerr << index; + std::cerr << "]\t"; + mii->print(std::cerr, *tm_)); // use our current mapping and actually replace every // virtual register with its allocated physical registers - DEBUG(std::cerr << "\t\treplacing virtual registers with mapped " - "physical registers:\n"); + DEBUG(std::cerr << "\t"); for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { MachineOperand& op = mii->getOperand(i); @@ -336,14 +347,30 @@ bool RA::runOnMachineFunction(MachineFunction &fn) { "all virtual registers must be allocated"); unsigned physReg = it->second; assert(MRegisterInfo::isPhysicalRegister(physReg)); - DEBUG(std::cerr << "\t\t\t%reg" << virtReg - << " -> " << mri_->getName(physReg) << '\n'); + DEBUG(std::cerr << "\t[reg" << virtReg + << " -> " << mri_->getName(physReg) << ']'); mii->SetMachineOperandReg(i, physReg); } } + DEBUG(std::cerr << '\n'); } } + DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); + DEBUG( + for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); + mbbi != mbbe; ++mbbi) { + for (MachineBasicBlock::iterator mii = mbbi->begin(), + mie = mbbi->end(); mii != mie; ++mii) { + unsigned index = li_->getInstructionIndex(mii); + if (index == std::numeric_limits<unsigned>::max()) + std::cerr << "*\t"; + else + std::cerr << index << '\t'; + mii->print(std::cerr, *tm_); + } + }); + return true; } @@ -379,7 +406,7 @@ void RA::processActiveIntervals(IntervalPtrs::value_type cur) } // move inactive intervals to inactive list else if (!(*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " inactive\n"); + DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n"); if (MRegisterInfo::isVirtualRegister(reg)) { reg = v2pMap_[reg]; } @@ -403,13 +430,13 @@ void RA::processInactiveIntervals(IntervalPtrs::value_type cur) // remove expired intervals if ((*i)->expiredAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " expired\n"); + DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n"); // remove from inactive i = inactive_.erase(i); } // move re-activated intervals in active list else if ((*i)->liveAt(cur->start())) { - DEBUG(std::cerr << "\t\t\tinterval " << **i << " active\n"); + DEBUG(std::cerr << "\t\tinterval " << **i << " active\n"); if (MRegisterInfo::isVirtualRegister(reg)) { reg = v2pMap_[reg]; } @@ -434,7 +461,7 @@ void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight) void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) { - DEBUG(std::cerr << "\tallocating current interval:\n"); + DEBUG(std::cerr << "\tallocating current interval: "); PhysRegTracker backupPrt = prt_; @@ -480,16 +507,15 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) // the free physical register and add this interval to the active // list. if (physReg) { + DEBUG(std::cerr << mri_->getName(physReg) << '\n'); assignVirt2PhysReg(cur->reg, physReg); active_.push_back(cur); handled_.push_back(cur); return; } + DEBUG(std::cerr << "no free registers\n"); - DEBUG(std::cerr << "\t\tassigning stack slot at interval "<< *cur << ":\n"); - // push the current interval back to unhandled since we are going - // to re-run at least this iteration - unhandled_.push_front(cur); + DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n"); float minWeight = std::numeric_limits<float>::infinity(); unsigned minReg = 0; @@ -502,21 +528,36 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) minReg = reg; } } - DEBUG(std::cerr << "\t\t\tregister with min weight: " + DEBUG(std::cerr << "\t\tregister with min weight: " << mri_->getName(minReg) << " (" << minWeight << ")\n"); // if the current has the minimum weight, we need to modify it, // push it back in unhandled and let the linear scan algorithm run // again - if (cur->weight < minWeight) { - DEBUG(std::cerr << "\t\t\t\tspilling(c): " << *cur;); + if (cur->weight <= minWeight) { + DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';); int slot = assignVirt2StackSlot(cur->reg); - li_->updateSpilledInterval(*cur); - addSpillCode(cur, slot); - DEBUG(std::cerr << "[ " << *cur << " ]\n"); + li_->updateSpilledInterval(*cur, slot); + + // if we didn't eliminate the interval find where to add it + // back to unhandled. We need to scan since unhandled are + // sorted on earliest start point and we may have changed our + // start point. + if (!cur->empty()) { + addSpillCode(cur, slot); + IntervalPtrs::iterator it = unhandled_.begin(); + while (it != unhandled_.end() && (*it)->start() < cur->start()) + ++it; + unhandled_.insert(it, cur); + } return; } + // push the current interval back to unhandled since we are going + // to re-run at least this iteration. Since we didn't modify it it + // should go back right in the front of the list + unhandled_.push_front(cur); + // otherwise we spill all intervals aliasing the register with // minimum weight, rollback to the interval with the earliest // start point and let the linear scan algorithm run again @@ -526,18 +567,16 @@ void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur) toSpill[*as] = true; unsigned earliestStart = cur->start(); - for (IntervalPtrs::iterator i = active_.begin(); - i != active_.end(); ++i) { + for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { unsigned reg = (*i)->reg; if (MRegisterInfo::isVirtualRegister(reg) && toSpill[v2pMap_[reg]] && cur->overlaps(**i)) { - DEBUG( |