diff options
Diffstat (limited to 'lib/CodeGen/RegAllocLinearScan.cpp')
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 188 |
1 files changed, 101 insertions, 87 deletions
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 904b4cb..5d58ea9 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -33,8 +33,10 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/Support/Debug.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include <algorithm> #include <set> #include <queue> @@ -142,6 +144,7 @@ namespace { } virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); AU.addRequired<LiveIntervals>(); if (StrongPHIElim) AU.addRequiredID(StrongPHIEliminationID); @@ -173,11 +176,11 @@ namespace { /// processActiveIntervals - expire old intervals and move non-overlapping /// ones to the inactive list. - void processActiveIntervals(unsigned CurPoint); + void processActiveIntervals(LiveIndex CurPoint); /// processInactiveIntervals - expire old intervals and move overlapping /// ones to the active list. - void processInactiveIntervals(unsigned CurPoint); + void processInactiveIntervals(LiveIndex CurPoint); /// hasNextReloadInterval - Return the next liveinterval that's being /// defined by a reload from the same SS as the specified one. @@ -230,12 +233,12 @@ namespace { bool Error = false; for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) { if (regUse_[i] != 0) { - cerr << tri_->getName(i) << " is still in use!\n"; + errs() << tri_->getName(i) << " is still in use!\n"; Error = true; } } if (Error) - abort(); + llvm_unreachable(0); #endif regUse_.clear(); regUseBackUp_.clear(); @@ -295,15 +298,20 @@ namespace { template <typename ItTy> void printIntervals(const char* const str, ItTy i, ItTy e) const { - if (str) DOUT << str << " intervals:\n"; - for (; i != e; ++i) { - DOUT << "\t" << *i->first << " -> "; - unsigned reg = i->first->reg; - if (TargetRegisterInfo::isVirtualRegister(reg)) { - reg = vrm_->getPhys(reg); - } - DOUT << tri_->getName(reg) << '\n'; - } + DEBUG({ + if (str) + errs() << str << " intervals:\n"; + + for (; i != e; ++i) { + errs() << "\t" << *i->first << " -> "; + + unsigned reg = i->first->reg; + if (TargetRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + + errs() << tri_->getName(reg) << '\n'; + } + }); } }; char RALinScan::ID = 0; @@ -358,7 +366,8 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { return Reg; VNInfo *vni = cur.begin()->valno; - if (!vni->def || vni->isUnused() || !vni->isDefAccurate()) + if ((vni->def == LiveIndex()) || + vni->isUnused() || !vni->isDefAccurate()) return Reg; MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg; @@ -380,18 +389,18 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { // Try to coalesce. if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) { - DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg) - << '\n'; + DEBUG(errs() << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg) + << '\n'); vrm_->clearVirt(cur.reg); vrm_->assignVirt2Phys(cur.reg, PhysReg); // Remove unnecessary kills since a copy does not clobber the register. if (li_->hasInterval(SrcReg)) { LiveInterval &SrcLI = li_->getInterval(SrcReg); - for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(cur.reg), - E = mri_->reg_end(); I != E; ++I) { + for (MachineRegisterInfo::use_iterator I = mri_->use_begin(cur.reg), + E = mri_->use_end(); I != E; ++I) { MachineOperand &O = I.getOperand(); - if (!O.isUse() || !O.isKill()) + if (!O.isKill()) continue; MachineInstr *MI = &*I; if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI)))) @@ -478,24 +487,25 @@ void RALinScan::initIntervalSets() } } -void RALinScan::linearScan() -{ +void RALinScan::linearScan() { // linear scan algorithm - DOUT << "********** LINEAR SCAN **********\n"; - DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n'; - - DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); + DEBUG({ + errs() << "********** LINEAR SCAN **********\n" + << "********** Function: " + << mf_->getFunction()->getName() << '\n'; + printIntervals("fixed", fixed_.begin(), fixed_.end()); + }); while (!unhandled_.empty()) { // pick the interval with the earliest start point LiveInterval* cur = unhandled_.top(); unhandled_.pop(); ++NumIters; - DOUT << "\n*** CURRENT ***: " << *cur << '\n'; + DEBUG(errs() << "\n*** CURRENT ***: " << *cur << '\n'); if (!cur->empty()) { - processActiveIntervals(cur->beginNumber()); - processInactiveIntervals(cur->beginNumber()); + processActiveIntervals(cur->beginIndex()); + processInactiveIntervals(cur->beginIndex()); assert(TargetRegisterInfo::isVirtualRegister(cur->reg) && "Can only allocate virtual registers!"); @@ -506,15 +516,17 @@ void RALinScan::linearScan() // assign it one. assignRegOrStackSlotAtInterval(cur); - DEBUG(printIntervals("active", active_.begin(), active_.end())); - DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); + DEBUG({ + printIntervals("active", active_.begin(), active_.end()); + printIntervals("inactive", inactive_.begin(), inactive_.end()); + }); } // Expire any remaining active intervals while (!active_.empty()) { IntervalPtr &IP = active_.back(); unsigned reg = IP.first->reg; - DOUT << "\tinterval " << *IP.first << " expired\n"; + DEBUG(errs() << "\tinterval " << *IP.first << " expired\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -523,9 +535,11 @@ void RALinScan::linearScan() } // Expire any remaining inactive intervals - DEBUG(for (IntervalPtrs::reverse_iterator - i = inactive_.rbegin(); i != inactive_.rend(); ++i) - DOUT << "\tinterval " << *i->first << " expired\n"); + DEBUG({ + for (IntervalPtrs::reverse_iterator + i = inactive_.rbegin(); i != inactive_.rend(); ++i) + errs() << "\tinterval " << *i->first << " expired\n"; + }); inactive_.clear(); // Add live-ins to every BB except for entry. Also perform trivial coalescing. @@ -560,7 +574,7 @@ void RALinScan::linearScan() } } - DOUT << *vrm_; + DEBUG(errs() << *vrm_); // Look for physical registers that end up not being allocated even though // register allocator had to spill other registers in its register class. @@ -572,9 +586,9 @@ void RALinScan::linearScan() /// processActiveIntervals - expire old intervals and move non-overlapping ones /// to the inactive list. -void RALinScan::processActiveIntervals(unsigned CurPoint) +void RALinScan::processActiveIntervals(LiveIndex CurPoint) { - DOUT << "\tprocessing active intervals:\n"; + DEBUG(errs() << "\tprocessing active intervals:\n"); for (unsigned i = 0, e = active_.size(); i != e; ++i) { LiveInterval *Interval = active_[i].first; @@ -584,7 +598,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); if (IntervalPos == Interval->end()) { // Remove expired intervals. - DOUT << "\t\tinterval " << *Interval << " expired\n"; + DEBUG(errs() << "\t\tinterval " << *Interval << " expired\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -597,7 +611,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) } else if (IntervalPos->start > CurPoint) { // Move inactive intervals to inactive list. - DOUT << "\t\tinterval " << *Interval << " inactive\n"; + DEBUG(errs() << "\t\tinterval " << *Interval << " inactive\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -618,9 +632,9 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) /// processInactiveIntervals - expire old intervals and move overlapping /// ones to the active list. -void RALinScan::processInactiveIntervals(unsigned CurPoint) +void RALinScan::processInactiveIntervals(LiveIndex CurPoint) { - DOUT << "\tprocessing inactive intervals:\n"; + DEBUG(errs() << "\tprocessing inactive intervals:\n"); for (unsigned i = 0, e = inactive_.size(); i != e; ++i) { LiveInterval *Interval = inactive_[i].first; @@ -630,7 +644,7 @@ void RALinScan::processInactiveIntervals(unsigned CurPoint) IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); if (IntervalPos == Interval->end()) { // remove expired intervals. - DOUT << "\t\tinterval " << *Interval << " expired\n"; + DEBUG(errs() << "\t\tinterval " << *Interval << " expired\n"); // Pop off the end of the list. inactive_[i] = inactive_.back(); @@ -638,7 +652,7 @@ void RALinScan::processInactiveIntervals(unsigned CurPoint) --i; --e; } else if (IntervalPos->start <= CurPoint) { // move re-activated intervals in active list - DOUT << "\t\tinterval " << *Interval << " active\n"; + DEBUG(errs() << "\t\tinterval " << *Interval << " active\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -699,7 +713,7 @@ FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) { return IP.end(); } -static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ +static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, LiveIndex Point){ for (unsigned i = 0, e = V.size(); i != e; ++i) { RALinScan::IntervalPtr &IP = V[i]; LiveInterval::iterator I = std::upper_bound(IP.first->begin(), @@ -725,7 +739,8 @@ static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, if (SI.hasAtLeastOneValue()) VNI = SI.getValNumInfo(0); else - VNI = SI.getNextValue(0, 0, false, ls_->getVNInfoAllocator()); + VNI = SI.getNextValue(LiveIndex(), 0, false, + ls_->getVNInfoAllocator()); LiveInterval &RI = li_->getInterval(cur->reg); // FIXME: This may be overly conservative. @@ -764,10 +779,12 @@ void RALinScan::findIntervalsToSpill(LiveInterval *cur, float Conflicts[3] = { 0.0f, 0.0f, 0.0f }; SmallVector<LiveInterval*, 8> SLIs[3]; - DOUT << "\tConsidering " << NumCands << " candidates: "; - DEBUG(for (unsigned i = 0; i != NumCands; ++i) - DOUT << tri_->getName(Candidates[i].first) << " "; - DOUT << "\n";); + DEBUG({ + errs() << "\tConsidering " << NumCands << " candidates: "; + for (unsigned i = 0; i != NumCands; ++i) + errs() << tri_->getName(Candidates[i].first) << " "; + errs() << "\n"; + }); // Calculate the number of conflicts of each candidate. for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { @@ -865,16 +882,15 @@ void RALinScan::UpgradeRegister(unsigned Reg) { namespace { struct LISorter { bool operator()(LiveInterval* A, LiveInterval* B) { - return A->beginNumber() < B->beginNumber(); + return A->beginIndex() < B->beginIndex(); } }; } /// assignRegOrStackSlotAtInterval - assign a register if one is available, or /// spill. -void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) -{ - DOUT << "\tallocating current interval: "; +void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) { + DEBUG(errs() << "\tallocating current interval: "); // This is an implicitly defined live interval, just assign any register. const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); @@ -882,7 +898,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) unsigned physReg = vrm_->getRegAllocPref(cur->reg); if (!physReg) physReg = *RC->allocation_order_begin(*mf_); - DOUT << tri_->getName(physReg) << '\n'; + DEBUG(errs() << tri_->getName(physReg) << '\n'); // Note the register is not really in use. vrm_->assignVirt2Phys(cur->reg, physReg); return; @@ -891,7 +907,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) backUpRegUses(); std::vector<std::pair<unsigned, float> > SpillWeightsToAdd; - unsigned StartPosition = cur->beginNumber(); + LiveIndex StartPosition = cur->beginIndex(); const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); // If start of this live interval is defined by a move instruction and its @@ -901,7 +917,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // one, e.g. X86::mov32to32_. These move instructions are not coalescable. if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) { VNInfo *vni = cur->begin()->valno; - if (vni->def && !vni->isUnused() && vni->isDefAccurate()) { + if ((vni->def != LiveIndex()) && !vni->isUnused() && + vni->isDefAccurate()) { MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; if (CopyMI && @@ -963,7 +980,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // Okay, this reg is on the fixed list. Check to see if we actually // conflict. LiveInterval *I = IP.first; - if (I->endNumber() > StartPosition) { + if (I->endIndex() > StartPosition) { LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); IP.second = II; if (II != I->begin() && II->start > StartPosition) @@ -988,7 +1005,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg]; if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && - I->endNumber() > StartPosition) { + I->endIndex() > StartPosition) { LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); IP.second = II; if (II != I->begin() && II->start > StartPosition) @@ -1015,7 +1032,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // the free physical register and add this interval to the active // list. if (physReg) { - DOUT << tri_->getName(physReg) << '\n'; + DEBUG(errs() << tri_->getName(physReg) << '\n'); vrm_->assignVirt2Phys(cur->reg, physReg); addRegUse(physReg); active_.push_back(std::make_pair(cur, cur->begin())); @@ -1031,7 +1048,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) } return; } - DOUT << "no free registers\n"; + DEBUG(errs() << "no free registers\n"); // Compile the spill weights into an array that is better for scanning. std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f); @@ -1049,7 +1066,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) updateSpillWeights(SpillWeights, reg, i->first->weight, RC); } - DOUT << "\tassigning stack slot at interval "<< *cur << ":\n"; + DEBUG(errs() << "\tassigning stack slot at interval "<< *cur << ":\n"); // Find a register to spill. float minWeight = HUGE_VALF; @@ -1102,8 +1119,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DowngradedRegs.clear(); assignRegOrStackSlotAtInterval(cur); } else { - cerr << "Ran out of registers during register allocation!\n"; - exit(1); + llvm_report_error("Ran out of registers during register allocation!"); } return; } @@ -1117,16 +1133,19 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) --LastCandidate; } - DOUT << "\t\tregister(s) with min weight(s): "; - DEBUG(for (unsigned i = 0; i != LastCandidate; ++i) - DOUT << tri_->getName(RegsWeights[i].first) - << " (" << RegsWeights[i].second << ")\n"); + DEBUG({ + errs() << "\t\tregister(s) with min weight(s): "; + + for (unsigned i = 0; i != LastCandidate; ++i) + errs() << tri_->getName(RegsWeights[i].first) + << " (" << RegsWeights[i].second << ")\n"; + }); // If the current has the minimum weight, we need to spill it and // add any added intervals back to unhandled, and restart // linearscan. if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { - DOUT << "\t\t\tspilling(c): " << *cur << '\n'; + DEBUG(errs() << "\t\t\tspilling(c): " << *cur << '\n'); SmallVector<LiveInterval*, 8> spillIs; std::vector<LiveInterval*> added; @@ -1154,14 +1173,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) LiveInterval *ReloadLi = added[i]; if (ReloadLi->weight == HUGE_VALF && li_->getApproximateInstructionCount(*ReloadLi) == 0) { - unsigned ReloadIdx = ReloadLi->beginNumber(); + LiveIndex ReloadIdx = ReloadLi->beginIndex(); MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { // Last reload of same SS is in the same MBB. We want to try to // allocate both reloads the same register and make sure the reg // isn't clobbered in between if at all possible. - assert(LastReload->beginNumber() < ReloadIdx); + assert(LastReload->beginIndex() < ReloadIdx); NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); } LastReloadMBB = ReloadMBB; @@ -1206,12 +1225,11 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // mark our rollback point. std::vector<LiveInterval*> added; while (!spillIs.empty()) { - bool epicFail = false; LiveInterval *sli = spillIs.back(); spillIs.pop_back(); - DOUT << "\t\t\tspilling(a): " << *sli << '\n'; + DEBUG(errs() << "\t\t\tspilling(a): " << *sli << '\n'); earliestStartInterval = - (earliestStartInterval->beginNumber() < sli->beginNumber()) ? + (earliestStartInterval->beginIndex() < sli->beginIndex()) ? earliestStartInterval : sli; std::vector<LiveInterval*> newIs; @@ -1223,15 +1241,11 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) addStackInterval(sli, ls_, li_, mri_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(sli->reg); - - if (epicFail) { - //abort(); - } } - unsigned earliestStart = earliestStartInterval->beginNumber(); + LiveIndex earliestStart = earliestStartInterval->beginIndex(); - DOUT << "\t\trolling back to: " << earliestStart << '\n'; + DEBUG(errs() << "\t\trolling back to: " << earliestStart << '\n'); // Scan handled in reverse order up to the earliest start of a // spilled live interval and undo each one, restoring the state of @@ -1239,9 +1253,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) while (!handled_.empty()) { LiveInterval* i = handled_.back(); // If this interval starts before t we are done. - if (i->beginNumber() < earliestStart) + if (i->beginIndex() < earliestStart) break; - DOUT << "\t\t\tundo changes for: " << *i << '\n'; + DEBUG(errs() << "\t\t\tundo changes for: " << *i << '\n'); handled_.pop_back(); // When undoing a live interval allocation we must know if it is active or @@ -1290,8 +1304,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) for (unsigned i = 0, e = handled_.size(); i != e; ++i) { LiveInterval *HI = handled_[i]; if (!HI->expiredAt(earliestStart) && - HI->expiredAt(cur->beginNumber())) { - DOUT << "\t\t\tundo changes for: " << *HI << '\n'; + HI->expiredAt(cur->beginIndex())) { + DEBUG(errs() << "\t\t\tundo changes for: " << *HI << '\n'); active_.push_back(std::make_pair(HI, HI->begin())); assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg)); addRegUse(vrm_->getPhys(HI->reg)); @@ -1310,14 +1324,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) LiveInterval *ReloadLi = added[i]; if (ReloadLi->weight == HUGE_VALF && li_->getApproximateInstructionCount(*ReloadLi) == 0) { - unsigned ReloadIdx = ReloadLi->beginNumber(); + LiveIndex ReloadIdx = ReloadLi->beginIndex(); MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { // Last reload of same SS is in the same MBB. We want to try to // allocate both reloads the same register and make sure the reg // isn't clobbered in between if at all possible. - assert(LastReload->beginNumber() < ReloadIdx); + assert(LastReload->beginIndex() < ReloadIdx); NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); } LastReloadMBB = ReloadMBB; @@ -1420,7 +1434,7 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { // available first. unsigned Preference = vrm_->getRegAllocPref(cur->reg); if (Preference) { - DOUT << "(preferred: " << tri_->getName(Preference) << ") "; + DEBUG(errs() << "(preferred: " << tri_->getName(Preference) << ") "); if (isRegAvail(Preference) && RC->contains(Preference)) return Preference; |