diff options
-rw-r--r-- | include/llvm/CodeGen/LiveIntervalAnalysis.h | 10 | ||||
-rw-r--r-- | include/llvm/CodeGen/LiveStackAnalysis.h | 59 | ||||
-rw-r--r-- | include/llvm/Target/TargetInstrInfo.h | 2 | ||||
-rw-r--r-- | include/llvm/Target/TargetRegisterInfo.h | 12 | ||||
-rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 58 | ||||
-rw-r--r-- | lib/CodeGen/LiveStackAnalysis.cpp | 12 | ||||
-rw-r--r-- | lib/CodeGen/PreAllocSplitting.cpp | 7 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 52 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 16 | ||||
-rw-r--r-- | lib/CodeGen/StackSlotColoring.cpp | 335 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 36 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.h | 55 |
12 files changed, 479 insertions, 175 deletions
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index b54cf64..01ea609 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -356,15 +356,13 @@ namespace llvm { std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, SmallVectorImpl<LiveInterval*> &SpillIs, - const MachineLoopInfo *loopInfo, VirtRegMap& vrm, - float &SSWeight); + const MachineLoopInfo *loopInfo, VirtRegMap& vrm); /// addIntervalsForSpillsFast - Quickly create new intervals for spilled /// defs / uses without remat or splitting. std::vector<LiveInterval*> addIntervalsForSpillsFast(const LiveInterval &li, - const MachineLoopInfo *loopInfo, - VirtRegMap &vrm, float& SSWeight); + const MachineLoopInfo *loopInfo, VirtRegMap &vrm); /// spillPhysRegAroundRegDefsUses - Spill the specified physical register /// around all defs and uses of the specified interval. Return true if it @@ -512,7 +510,7 @@ namespace llvm { SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs, float &SSWeight); + std::vector<LiveInterval*> &NewLIs); void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, @@ -524,7 +522,7 @@ namespace llvm { BitVector &RestoreMBBs, DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes, DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs, float &SSWeight); + std::vector<LiveInterval*> &NewLIs); static LiveInterval* createInterval(unsigned Reg); diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h index 7cb4151..a2a2f93 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -18,6 +18,7 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/Allocator.h" #include <map> @@ -28,44 +29,66 @@ namespace llvm { /// BumpPtrAllocator VNInfoAllocator; - /// s2iMap - Stack slot indices to live interval mapping. + /// S2IMap - Stack slot indices to live interval mapping. /// typedef std::map<int, LiveInterval> SS2IntervalMap; - SS2IntervalMap s2iMap; + SS2IntervalMap S2IMap; + /// S2RCMap - Stack slot indices to register class mapping. + std::map<int, const TargetRegisterClass*> S2RCMap; + public: static char ID; // Pass identification, replacement for typeid LiveStacks() : MachineFunctionPass(&ID) {} typedef SS2IntervalMap::iterator iterator; typedef SS2IntervalMap::const_iterator const_iterator; - const_iterator begin() const { return s2iMap.begin(); } - const_iterator end() const { return s2iMap.end(); } - iterator begin() { return s2iMap.begin(); } - iterator end() { return s2iMap.end(); } - unsigned getNumIntervals() const { return (unsigned)s2iMap.size(); } - - LiveInterval &getOrCreateInterval(int Slot) { - SS2IntervalMap::iterator I = s2iMap.find(Slot); - if (I == s2iMap.end()) - I = s2iMap.insert(I,std::make_pair(Slot,LiveInterval(Slot,0.0F,true))); + const_iterator begin() const { return S2IMap.begin(); } + const_iterator end() const { return S2IMap.end(); } + iterator begin() { return S2IMap.begin(); } + iterator end() { return S2IMap.end(); } + + unsigned getNumIntervals() const { return (unsigned)S2IMap.size(); } + + LiveInterval &getOrCreateInterval(int Slot, const TargetRegisterClass *RC) { + assert(Slot >= 0 && "Spill slot indice must be >= 0"); + SS2IntervalMap::iterator I = S2IMap.find(Slot); + if (I == S2IMap.end()) { + I = S2IMap.insert(I,std::make_pair(Slot, LiveInterval(Slot,0.0F,true))); + S2RCMap.insert(std::make_pair(Slot, RC)); + } else { + // Use the largest common subclass register class. + const TargetRegisterClass *OldRC = S2RCMap[Slot]; + S2RCMap[Slot] = getCommonSubClass(OldRC, RC); + } return I->second; } LiveInterval &getInterval(int Slot) { - SS2IntervalMap::iterator I = s2iMap.find(Slot); - assert(I != s2iMap.end() && "Interval does not exist for stack slot"); + assert(Slot >= 0 && "Spill slot indice must be >= 0"); + SS2IntervalMap::iterator I = S2IMap.find(Slot); + assert(I != S2IMap.end() && "Interval does not exist for stack slot"); return I->second; } const LiveInterval &getInterval(int Slot) const { - SS2IntervalMap::const_iterator I = s2iMap.find(Slot); - assert(I != s2iMap.end() && "Interval does not exist for stack slot"); + assert(Slot >= 0 && "Spill slot indice must be >= 0"); + SS2IntervalMap::const_iterator I = S2IMap.find(Slot); + assert(I != S2IMap.end() && "Interval does not exist for stack slot"); return I->second; } - bool hasInterval(unsigned Slot) const { - return s2iMap.count(Slot); + bool hasInterval(int Slot) const { + return S2IMap.count(Slot); + } + + const TargetRegisterClass *getIntervalRegClass(int Slot) const { + assert(Slot >= 0 && "Spill slot indice must be >= 0"); + std::map<int, const TargetRegisterClass*>::const_iterator + I = S2RCMap.find(Slot); + assert(I != S2RCMap.end() && + "Register class info does not exist for stack slot"); + return I->second; } BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } diff --git a/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h index c6b8987..ec5ab44 100644 --- a/include/llvm/Target/TargetInstrInfo.h +++ b/include/llvm/Target/TargetInstrInfo.h @@ -391,7 +391,7 @@ public: /// possible, returns true as well as the new instructions by reference. virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr *MI, unsigned Reg, bool UnfoldLoad, bool UnfoldStore, - SmallVectorImpl<MachineInstr*> &NewMIs) const{ + SmallVectorImpl<MachineInstr*> &NewMIs) const{ return false; } diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h index fbb8ffe..6cd664e 100644 --- a/include/llvm/Target/TargetRegisterInfo.h +++ b/include/llvm/Target/TargetRegisterInfo.h @@ -238,8 +238,6 @@ public: return end(); } - - /// getSize - Return the size of the register in bytes, which is also the size /// of a stack slot allocated to hold a spilled copy of this register. unsigned getSize() const { return RegSize; } @@ -254,10 +252,6 @@ public: int getCopyCost() const { return CopyCost; } }; -/// getCommonSubClass - find the largest common subclass of A and B. Return NULL -/// if there is no common subclass. -const TargetRegisterClass *getCommonSubClass(const TargetRegisterClass *A, - const TargetRegisterClass *B); /// TargetRegisterInfo base class - We assume that the target defines a static /// array of TargetRegisterDesc objects that represent all of the machine @@ -644,6 +638,7 @@ public: virtual void getInitialFrameState(std::vector<MachineMove> &Moves) const; }; + // This is useful when building IndexedMaps keyed on virtual registers struct VirtReg2IndexFunctor : std::unary_function<unsigned, unsigned> { unsigned operator()(unsigned Reg) const { @@ -651,6 +646,11 @@ struct VirtReg2IndexFunctor : std::unary_function<unsigned, unsigned> { } }; +/// getCommonSubClass - find the largest common subclass of A and B. Return NULL +/// if there is no common subclass. +const TargetRegisterClass *getCommonSubClass(const TargetRegisterClass *A, + const TargetRegisterClass *B); + } // End llvm namespace #endif diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index d2927ed..612b9ac 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1229,9 +1229,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, const MachineLoopInfo *loopInfo, unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs, float &SSWeight) { - MachineBasicBlock *MBB = MI->getParent(); - unsigned loopDepth = loopInfo->getLoopDepth(MBB); + std::vector<LiveInterval*> &NewLIs) { bool CanFold = false; RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { @@ -1312,11 +1310,6 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, // the INSERT_SUBREG and both target registers that would overlap. HasUse = false; - // Update stack slot spill weight if we are splitting. - float Weight = getSpillWeight(HasDef, HasUse, loopDepth); - if (!TrySplit) - SSWeight += Weight; - // Create a new virtual register for the spill interval. // Create the new register now so we can map the fold instruction // to the new register so when it is unfolded we get the correct @@ -1348,10 +1341,8 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, HasUse = false; HasDef = false; CanFold = false; - if (isNotInMIMap(MI)) { - SSWeight -= Weight; + if (isNotInMIMap(MI)) break; - } goto RestartInstruction; } } else { @@ -1486,7 +1477,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, BitVector &RestoreMBBs, DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, DenseMap<unsigned,unsigned> &MBBVRegsMap, - std::vector<LiveInterval*> &NewLIs, float &SSWeight) { + std::vector<LiveInterval*> &NewLIs) { bool AllCanFold = true; unsigned NewVReg = 0; unsigned start = getBaseIndex(I->start); @@ -1588,7 +1579,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, index, end, MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, - ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); + ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); if (!HasDef && !HasUse) continue; @@ -1747,7 +1738,7 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, std::vector<LiveInterval*> LiveIntervals:: addIntervalsForSpillsFast(const LiveInterval &li, const MachineLoopInfo *loopInfo, - VirtRegMap &vrm, float& SSWeight) { + VirtRegMap &vrm) { unsigned slot = vrm.assignVirt2StackSlot(li.reg); std::vector<LiveInterval*> added; @@ -1761,8 +1752,6 @@ addIntervalsForSpillsFast(const LiveInterval &li, const TargetRegisterClass* rc = mri_->getRegClass(li.reg); - SSWeight = 0.0f; - MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); while (RI != mri_->reg_end()) { MachineInstr* MI = &*RI; @@ -1825,15 +1814,6 @@ addIntervalsForSpillsFast(const LiveInterval &li, DOUT << "\t\t\t\tadded new interval: "; DEBUG(nI.dump()); DOUT << '\n'; - - unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); - if (HasUse) { - if (HasDef) - SSWeight += getSpillWeight(true, true, loopDepth); - else - SSWeight += getSpillWeight(false, true, loopDepth); - } else - SSWeight += getSpillWeight(true, false, loopDepth); } @@ -1846,11 +1826,10 @@ addIntervalsForSpillsFast(const LiveInterval &li, std::vector<LiveInterval*> LiveIntervals:: addIntervalsForSpills(const LiveInterval &li, SmallVectorImpl<LiveInterval*> &SpillIs, - const MachineLoopInfo *loopInfo, VirtRegMap &vrm, - float &SSWeight) { + const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { if (EnableFastSpilling) - return addIntervalsForSpillsFast(li, loopInfo, vrm, SSWeight); + return addIntervalsForSpillsFast(li, loopInfo, vrm); assert(li.weight != HUGE_VALF && "attempt to spill already spilled interval!"); @@ -1859,9 +1838,6 @@ addIntervalsForSpills(const LiveInterval &li, li.print(DOUT, tri_); DOUT << '\n'; - // Spill slot weight. - SSWeight = 0.0f; - // Each bit specify whether a spill is required in the MBB. BitVector SpillMBBs(mf_->getNumBlockIDs()); DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; @@ -1916,18 +1892,17 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs, SSWeight); + MBBVRegsMap, NewLIs); } else { rewriteInstructionsForSpills(li, false, I, NULL, 0, Slot, 0, false, false, false, false, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs, SSWeight); + MBBVRegsMap, NewLIs); } IsFirstRange = false; } - SSWeight = 0.0f; // Already accounted for when split. handleSpilledImpDefs(li, vrm, rc, NewLIs); return NewLIs; } @@ -2001,7 +1976,7 @@ addIntervalsForSpills(const LiveInterval &li, Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, rc, ReMatIds, loopInfo, SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, - MBBVRegsMap, NewLIs, SSWeight); + MBBVRegsMap, NewLIs); } // Insert spills / restores if we are splitting. @@ -2015,8 +1990,6 @@ addIntervalsForSpills(const LiveInterval &li, if (NeedStackSlot) { int Id = SpillMBBs.find_first(); while (Id != -1) { - MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); - unsigned loopDepth = loopInfo->getLoopDepth(MBB); std::vector<SRInfo> &spills = SpillIdxes[Id]; for (unsigned i = 0, e = spills.size(); i != e; ++i) { int index = spills[i].index; @@ -2073,10 +2046,6 @@ addIntervalsForSpills(const LiveInterval &li, if (isKill) AddedKill.insert(&nI); } - - // Update spill slot weight. - if (!isReMat) - SSWeight += getSpillWeight(true, false, loopDepth); } Id = SpillMBBs.find_next(Id); } @@ -2084,9 +2053,6 @@ addIntervalsForSpills(const LiveInterval &li, int Id = RestoreMBBs.find_first(); while (Id != -1) { - MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); - unsigned loopDepth = loopInfo->getLoopDepth(MBB); - std::vector<SRInfo> &restores = RestoreIdxes[Id]; for (unsigned i = 0, e = restores.size(); i != e; ++i) { int index = restores[i].index; @@ -2148,10 +2114,6 @@ addIntervalsForSpills(const LiveInterval &li, nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); else vrm.addRestorePoint(VReg, MI); - - // Update spill slot weight. - if (!isReMat) - SSWeight += getSpillWeight(false, true, loopDepth); } Id = RestoreMBBs.find_next(Id); } diff --git a/lib/CodeGen/LiveStackAnalysis.cpp b/lib/CodeGen/LiveStackAnalysis.cpp index 2baf699..c68a2d9 100644 --- a/lib/CodeGen/LiveStackAnalysis.cpp +++ b/lib/CodeGen/LiveStackAnalysis.cpp @@ -32,7 +32,8 @@ void LiveStacks::getAnalysisUsage(AnalysisUsage &AU) const { void LiveStacks::releaseMemory() { // Release VNInfo memroy regions after all VNInfo objects are dtor'd. VNInfoAllocator.Reset(); - s2iMap.clear(); + S2IMap.clear(); + S2RCMap.clear(); } bool LiveStacks::runOnMachineFunction(MachineFunction &) { @@ -42,10 +43,15 @@ bool LiveStacks::runOnMachineFunction(MachineFunction &) { } /// print - Implement the dump method. -void LiveStacks::print(std::ostream &O, const Module* ) const { +void LiveStacks::print(std::ostream &O, const Module*) const { O << "********** INTERVALS **********\n"; for (const_iterator I = begin(), E = end(); I != E; ++I) { I->second.print(O); - O << "\n"; + int Slot = I->first; + const TargetRegisterClass *RC = getIntervalRegClass(Slot); + if (RC) + O << " [" << RC->getName() << "]\n"; + else + O << " [Unknown]\n"; } } diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp index c4bda48..97d4728 100644 --- a/lib/CodeGen/PreAllocSplitting.cpp +++ b/lib/CodeGen/PreAllocSplitting.cpp @@ -339,7 +339,7 @@ int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg, } // Create live interval for stack slot. - CurrSLI = &LSs->getOrCreateInterval(SS); + CurrSLI = &LSs->getOrCreateInterval(SS, RC); if (CurrSLI->hasAtLeastOneValue()) CurrSValNo = CurrSLI->getValNumInfo(0); else @@ -926,8 +926,7 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, if (I != IntervalSSMap.end()) { SS = I->second; } else { - SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); - + SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); } MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), @@ -939,7 +938,7 @@ MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, ++NumFolds; IntervalSSMap[vreg] = SS; - CurrSLI = &LSs->getOrCreateInterval(SS); + CurrSLI = &LSs->getOrCreateInterval(SS, RC); if (CurrSLI->hasAtLeastOneValue()) CurrSValNo = CurrSLI->getValNumInfo(0); else diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index 83c1cbb..b5f581c 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -216,6 +216,18 @@ namespace { } void finalizeRegUses() { +#ifndef NDEBUG + // Verify all the registers are "freed". + 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"; + Error = true; + } + } + if (Error) + abort(); +#endif regUse_.clear(); regUseBackUp_.clear(); } @@ -514,6 +526,13 @@ void RALinScan::linearScan() } DOUT << *vrm_; + + // Look for physical registers that end up not being allocated even though + // register allocator had to spill other registers in its register class. + if (ls_->getNumIntervals() == 0) + return; + if (!vrm_->FindUnusedRegisters(tri_, li_)) + return; } /// processActiveIntervals - expire old intervals and move non-overlapping ones @@ -630,9 +649,9 @@ void RALinScan::updateSpillWeights(std::vector<float> &Weights, // bl should get the same spill weight otherwise it will be choosen // as a spill candidate since spilling bh doesn't make ebx available. for (unsigned i = 0, e = Supers.size(); i != e; ++i) { - for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr) - if (!Processed.count(*sr)) - Weights[*sr] += weight; + for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr) + if (!Processed.count(*sr)) + Weights[*sr] += weight; } } @@ -658,13 +677,14 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ /// addStackInterval - Create a LiveInterval for stack if the specified live /// interval has been spilled. static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, - LiveIntervals *li_, float &Weight, - VirtRegMap &vrm_) { + LiveIntervals *li_, + MachineRegisterInfo* mri_, VirtRegMap &vrm_) { int SS = vrm_.getStackSlot(cur->reg); if (SS == VirtRegMap::NO_STACK_SLOT) return; - LiveInterval &SI = ls_->getOrCreateInterval(SS); - SI.weight += Weight; + + const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); + LiveInterval &SI = ls_->getOrCreateInterval(SS, RC); VNInfo *VNI; if (SI.hasAtLeastOneValue()) @@ -679,10 +699,10 @@ static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, /// getConflictWeight - Return the number of conflicts between cur /// live interval and defs and uses of Reg weighted by loop depthes. -static float getConflictWeight(LiveInterval *cur, unsigned Reg, - LiveIntervals *li_, - MachineRegisterInfo *mri_, - const MachineLoopInfo *loopInfo) { +static +float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_, + MachineRegisterInfo *mri_, + const MachineLoopInfo *loopInfo) { float Conflicts = 0; for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), E = mri_->reg_end(); I != E; ++I) { @@ -1072,12 +1092,11 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // linearscan. if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { DOUT << "\t\t\tspilling(c): " << *cur << '\n'; - float SSWeight; SmallVector<LiveInterval*, 8> spillIs; std::vector<LiveInterval*> added = - li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight); + li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); std::sort(added.begin(), added.end(), LISorter()); - addStackInterval(cur, ls_, li_, SSWeight, *vrm_); + addStackInterval(cur, ls_, li_, mri_, *vrm_); if (added.empty()) return; // Early exit if all spills were folded. @@ -1149,10 +1168,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) spillIs.pop_back(); DOUT << "\t\t\tspilling(a): " << *sli << '\n'; earliestStart = std::min(earliestStart, sli->beginNumber()); - float SSWeight; std::vector<LiveInterval*> newIs = - li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight); - addStackInterval(sli, ls_, li_, SSWeight, *vrm_); + li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_); + addStackInterval(sli, ls_, li_, mri_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(sli->reg); } diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index 748fae4..8cdf4fa 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -165,7 +165,7 @@ namespace { //! \brief Adds a stack interval if the given live interval has been //! spilled. Used to support stack slot coloring. - void addStackInterval(const LiveInterval *spilled, float &weight); + void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); //! \brief Given a solved PBQP problem maps this solution back to a register //! assignment. @@ -637,14 +637,15 @@ pbqp* PBQPRegAlloc::constructPBQPProblem() { return solver; } -void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) { +void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, + MachineRegisterInfo* mri) { int stackSlot = vrm->getStackSlot(spilled->reg); if (stackSlot == VirtRegMap::NO_STACK_SLOT) return; - LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot); - stackInterval.weight += weight; + const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); + LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); VNInfo *vni; if (stackInterval.getNumValNums() != 0) @@ -688,16 +689,13 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { // of allocation vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); - float ssWeight; - // Insert spill ranges for this live range const LiveInterval *spillInterval = node2LI[node]; double oldSpillWeight = spillInterval->weight; SmallVector<LiveInterval*, 8> spillIs; std::vector<LiveInterval*> newSpills = - lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm, - ssWeight); - addStackInterval(spillInterval, ssWeight); + lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); + addStackInterval(spillInterval, mri); DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " << oldSpillWeight << ", New vregs: "; diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index 4fedc1a..139d12b 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -12,9 +12,13 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "stackcoloring" +#include "VirtRegMap.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" @@ -32,21 +36,34 @@ DisableSharing("no-stack-slot-sharing", cl::init(false), cl::Hidden, cl::desc("Suppress slot sharing during stack coloring")); +static cl::opt<bool> +ColorWithRegs("-color-ss-with-regs", + cl::init(false), cl::Hidden, + cl::desc("Color stack slots with free registers")); + + static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); -STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); -STATISTIC(NumDeadAccesses, - "Number of trivially dead stack accesses eliminated"); +STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); +STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); +STATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs"); namespace { class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { LiveStacks* LS; + VirtRegMap* VRM; MachineFrameInfo *MFI; + MachineRegisterInfo *MRI; const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + const MachineLoopInfo *loopInfo; // SSIntervals - Spill slot intervals. std::vector<LiveInterval*> SSIntervals; + // SSRefs - Keep a list of frame index references for each spill slot. + SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; + // OrigAlignments - Alignments of stack objects before coloring. SmallVector<unsigned, 16> OrigAlignments; @@ -66,7 +83,7 @@ namespace { BitVector UsedColors; // Assignments - Color to intervals mapping. - SmallVector<SmallVector<LiveInterval*,4>,16> Assignments; + SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; public: static char ID; // Pass identification @@ -74,8 +91,10 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<LiveStacks>(); - - AU.addPreservedID(MachineLoopInfoID); + AU.addRequired<VirtRegMap>(); + AU.addPreserved<VirtRegMap>(); + AU.addRequired<MachineLoopInfo>(); + AU.addPreserved<MachineLoopInfo>(); AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -86,11 +105,20 @@ namespace { } private: - bool InitializeSlots(); + void InitializeSlots(); + void ScanForSpillSlotRefs(MachineFunction &MF); bool OverlapWithAssignments(LiveInterval *li, int Color) const; int ColorSlot(LiveInterval *li); bool ColorSlots(MachineFunction &MF); - bool removeDeadStores(MachineBasicBlock* MBB); + bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, + SmallVector<SmallVector<int, 4>, 16> &RevMap, + BitVector &SlotIsReg); + void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, + MachineFunction &MF); + void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, + unsigned Reg, MachineFunction &MF); + bool AllMemRefsCanBeUnfolded(int SS); + bool RemoveDeadStores(MachineBasicBlock* MBB); }; } // end anonymous namespace @@ -113,12 +141,39 @@ namespace { }; } +/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot +/// references and update spill slot weights. +void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { + SSRefs.resize(MFI->getObjectIndexEnd()); + + // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. + for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = &*MBBI; + unsigned loopDepth = loopInfo->getLoopDepth(MBB); + for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); + MII != EE; ++MII) { + MachineInstr *MI = &*MII; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isFI()) + continue; + int FI = MO.getIndex(); + if (FI < 0) + continue; + if (!LS->hasInterval(FI)) + continue; + LiveInterval &li = LS->getInterval(FI); + li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); + SSRefs[FI].push_back(MI); + } + } + } +} + /// InitializeSlots - Process all spill stack slot liveintervals and add them /// to a sorted (by weight) list. -bool StackSlotColoring::InitializeSlots() { - if (LS->getNumIntervals() < 2) - return false; - +void StackSlotColoring::InitializeSlots() { int LastFI = MFI->getObjectIndexEnd(); OrigAlignments.resize(LastFI); OrigSizes.resize(LastFI); @@ -127,8 +182,10 @@ bool StackSlotColoring::InitializeSlots() { Assignments.resize(LastFI); // Gather all spill slots into a list. + DOUT << "Spill slot intervals:\n"; for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { LiveInterval &li = i->second; + DEBUG(li.dump()); int FI = li.getStackSlotIndex(); if (MFI->isDeadObjectIndex(FI)) continue; @@ -137,13 +194,13 @@ bool StackSlotColoring::InitializeSlots() { OrigSizes[FI] = MFI->getObjectSize(FI); AllColors.set(FI); } + DOUT << '\n'; // Sort them by weight. std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); // Get first "color". NextColor = AllColors.find_first(); - return true; } /// OverlapWithAssignments - Return true if LiveInterval overlaps with any @@ -159,6 +216,83 @@ StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { return false; } +/// ColorSlotsWithFreeRegs - If there are any free registers available, try +/// replacing spill slots references with registers instead. +bool +StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, + SmallVector<SmallVector<int, 4>, 16> &RevMap, + BitVector &SlotIsReg) { + if (!ColorWithRegs || !VRM->HasUnusedRegisters()) + return false; + + bool Changed = false; + DOUT << "Assigning unused registers to spill slots:\n"; + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { + LiveInterval *li = SSIntervals[i]; + int SS = li->getStackSlotIndex(); + if (!UsedColors[SS]) + continue; + // Get the largest common sub- register class of all the stack slots that + // are colored to this stack slot. + const TargetRegisterClass *RC = 0; + for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { + int RSS = RevMap[SS][j]; + const TargetRegisterClass *RRC = LS->getIntervalRegClass(RSS); + if (!RC) + RC = RRC; + else + RC = getCommonSubClass(RC, RRC); + } + + // If it's not colored to another stack slot, try coloring it + // to a "free" register. + if (!RC) + continue; + unsigned Reg = VRM->getFirstUnusedRegister(RC); + if (!Reg) + continue; + bool IsSafe = true; + for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { + int RSS = RevMap[SS][j]; + if (!AllMemRefsCanBeUnfolded(RSS)) { + IsSafe = false; + break; + } + } + if (!IsSafe) + // Try color the next spill slot. + continue; + + DOUT << "Assigning fi#" << SS << " to " << TRI->getName(Reg) + << ", which in turn means...\n"; + // Register and its sub-registers are no longer free. + VRM->setRegisterUsed(Reg); + // If reg is a callee-saved register, it will have to be spilled in + // the prologue. + MRI->setPhysRegUsed(Reg); + for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { + VRM->setRegisterUsed(*AS); + MRI->setPhysRegUsed(*AS); + } + // This spill slot is dead after the rewrites + MFI->RemoveStackObject(SS); + + // Remember all these FI references will have to be unfolded. + for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { + int RSS = RevMap[SS][j]; + DOUT << " Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n'; + SlotMapping[RSS] = Reg; + SlotIsReg.set(RSS); + } + + ++NumEliminated; + Changed = true; + } + DOUT << '\n'; + + return Changed; +} + /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. /// int StackSlotColoring::ColorSlot(LiveInterval *li) { @@ -207,56 +341,61 @@ int StackSlotColoring::ColorSlot(LiveInterval *li) { /// operands in the function. bool StackSlotColoring::ColorSlots(MachineFunction &MF) { unsigned NumObjs = MFI->getObjectIndexEnd(); - std::vector<int> SlotMapping(NumObjs, -1); + SmallVector<int, 16> SlotMapping(NumObjs, -1); + SmallVector<float, 16> SlotWeights(NumObjs, 0.0); + SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); + BitVector SlotIsReg(NumObjs); + BitVector UsedColors(NumObjs); + DOUT << "Color spill slot intervals:\n"; bool Changed = false; for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { LiveInterval *li = SSIntervals[i]; int SS = li->getStackSlotIndex(); int NewSS = ColorSlot(li); + assert(NewSS >= 0 && "Stack coloring failed?"); SlotMapping[SS] = NewSS; + RevMap[NewSS].push_back(SS); + SlotWeights[NewSS] += li->weight; + UsedColors.set(NewSS); Changed |= (SS != NewSS); } + DOUT << "\nSpill slots after coloring:\n"; + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { + LiveInterval *li = SSIntervals[i]; + int SS = li->getStackSlotIndex(); + li->weight = SlotWeights[SS]; + } + // Sort them by new weight. + std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); + +#ifndef NDEBUG + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) + DEBUG(SSIntervals[i]->dump()); + DOUT << '\n'; +#endif + + // Can we "color" a stack slot with a unused register? + Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); + if (!Changed) return false; // Rewrite all MO_FrameIndex operands. - // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. - for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); - MBB != E; ++MBB) { - for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); - MII != EE; ++MII) { - MachineInstr &MI = *MII; - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isFI()) - continue; - int FI = MO.getIndex(); - if (FI < 0) - continue; - int NewFI = SlotMapping[FI]; - if (NewFI == -1) - continue; - MO.setIndex(NewFI); - - // Update the MachineMemOperand for the new memory location. - // FIXME: We need a better method of managing these too. - SmallVector<MachineMemOperand, 2> MMOs(MI.memoperands_begin(), - MI.memoperands_end()); - MI.clearMemOperands(MF); - const Value *OldSV = PseudoSourceValue::getFixedStack(FI); - for (unsigned i = 0, e = MMOs.size(); i != e; ++i) { - if (MMOs[i].getValue() == OldSV) { - MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), - MMOs[i].getFlags(), MMOs[i].getOffset(), - MMOs[i].getSize(), MMOs[i].getAlignment()); - MI.addMemOperand(MF, MMO); - } else - MI.addMemOperand(MF, MMOs[i]); - } - } - } + for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { + bool isReg = SlotIsReg[SS]; + int NewFI = SlotMapping[SS]; + if (NewFI == -1 || (NewFI == (int)SS && !isReg)) + continue; + + SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; + for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) + if (isReg) + // Rewrite to use a register instead. + UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, MF); + else + RewriteInstruction(RefMIs[i], SS, NewFI, MF); } // Delete unused stack slots. @@ -269,12 +408,77 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { return true; } -/// removeDeadStores - Scan through a basic block and look for loads followed +/// AllMemRefsCanBeUnfolded - Return true if all references of the specified +/// spill slot index can be unfolded. +bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { + SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; + for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { + MachineInstr *MI = RefMIs[i]; + if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) + return false; + for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { + MachineOperand &MO = MI->getOperand(j); + if (MO.isFI() && MO.getIndex() != SS) + // If it uses another frameindex, we can, currently* unfold it. + return false; + } + } + return true; +} + +/// RewriteInstruction - Rewrite specified instruction by replacing references +/// to old frame index with new one. +void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, + int NewFI, MachineFunction &MF) { + for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isFI()) + continue; + int FI = MO.getIndex(); + if (FI != OldFI) + continue; + MO.setIndex(NewFI); + } + + // Update the MachineMemOperand for the new memory location. + // FIXME: We need a better method of managing these too. + SmallVector<MachineMemOperand, 2> MMOs(MI->memoperands_begin(), + MI->memoperands_end()); + MI->clearMemOperands(MF); + const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); + for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) { + if (MMOs[i].getValue() != OldSV) + MI->addMemOperand(MF, MMOs[i]); + else { + MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), + MMOs[i].getFlags(), MMOs[i].getOffset(), + MMOs[i].getSize(), MMOs[i].getAlignment()); + MI->addMemOperand(MF, MMO); + } + } +} + +/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding +/// folded memory references and replacing those references with register +/// references instead. +void StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, + unsigned Reg, + MachineFunction &MF) { + MachineBasicBlock *MBB = MI->getParent(); + SmallVector<MachineInstr*, 4> NewMIs; + bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); + assert(Success && "Failed to unfold!"); + MBB->insert(MI, NewMIs[0]); + MBB->erase(MI); + ++NumRegRepl; +} + +/// RemoveDeadStores - Scan through a basic block and look for loads followed /// by stores. If they're both using the same stack slot, then the store is /// definitely dead. This could obviously be much more aggressive (consider /// pairs with instructions between them), but such extensions might have a /// considerable compile time impact. -bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) { +bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { // FIXME: This could be much more aggressive, but we need to investigate // the compile time impact of doing so. bool changed = false; @@ -283,7 +487,7 @@ bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) { for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { - if (DCELimit != -1 && (int)NumDeadAccesses >= DCELimit) + if (DCELimit != -1 && (int)NumDead >= DCELimit) break; MachineBasicBlock::iterator NextMI = next(I); @@ -296,11 +500,11 @@ bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) { if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; - ++NumDeadAccesses; + ++NumDead; changed = true; if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { - ++NumDeadAccesses; + ++NumDead; toErase.push_back(I); } @@ -320,15 +524,32 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { DOUT << "********** Stack Slot Coloring **********\n"; MFI = MF.getFrameInfo(); + MRI = &MF.getRegInfo(); TII = MF.getTarget().getInstrInfo(); + TRI = MF.getTarget().getRegisterInfo(); LS = &getAnalysis<LiveStacks>(); + VRM = &getAnalysis<VirtRegMap>(); + loopInfo = &getAnalysis<MachineLoopInfo>(); bool Changed = false; - if (InitializeSlots()) - Changed = ColorSlots(MF); + + unsigned NumSlots = LS->getNumIntervals(); + if (NumSlots < 2) { + if (NumSlots == 0 || !VRM->HasUnusedRegisters()) + // Nothing to do! + return false; + } + + // Gather spill slot references + ScanForSpillSlotRefs(MF); + InitializeSlots(); + Changed = ColorSlots(MF); NextColor = -1; SSIntervals.clear(); + for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) + SSRefs[i].clear(); + SSRefs.clear(); OrigAlignments.clear(); OrigSizes.clear(); AllColors.clear(); @@ -339,7 +560,7 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { if (Changed) { for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - Changed |= removeDeadStores(I); + Changed |= RemoveDeadStores(I); } return Changed; diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index cb0f764..f2f6ab0 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -19,6 +19,7 @@ #define DEBUG_TYPE "virtregmap" #include "VirtRegMap.h" #include "llvm/Function.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -201,6 +202,41 @@ void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) { EmergencySpillMap.erase(MI); } +/// FindUnusedRegisters - Gather a list of allocatable registers that +/// have not been allocated to any virtual register. +bool VirtRegMap::FindUnusedRegisters(const TargetRegisterInfo *TRI, + LiveIntervals* LIs) { + unsigned NumRegs = TRI->getNumRegs(); + UnusedRegs.reset(); + UnusedRegs.resize(NumRegs); + + BitVector Used(NumRegs); + for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, + e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) + if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) + Used.set(Virt2PhysMap[i]); + + BitVector Allocatable = TRI->getAllocatableSet(*MF); + bool AnyUnused = false; + for (unsigned Reg = 1; Reg < NumRegs; ++Reg) { + if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) { + bool ReallyUnused = true; + for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { + if (Used[*AS] || LIs->hasInterval(*AS)) { + ReallyUnused = false; + break; + } + } + if (ReallyUnused) { + AnyUnused = true; + UnusedRegs.set(Reg); + } + } + } + + return AnyUnused; +} + void VirtRegMap::print(std::ostream &OS, const Module* M) const { const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index 2e9c899..91c8322 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -20,6 +20,7 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" @@ -27,6 +28,7 @@ #include <map> namespace llvm { + class LiveIntervals; class MachineInstr; class MachineFunction; class TargetInstrInfo; @@ -122,6 +124,9 @@ namespace llvm { /// the register is implicitly defined. BitVector ImplicitDefed; + /// UnusedRegs - A list of physical registers that have not been used. + BitVector UnusedRegs; + VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT void operator=(const VirtRegMap&); // DO NOT IMPLEMENT @@ -277,8 +282,10 @@ namespace llvm { /// @brief records the specified MachineInstr as a spill point for virtReg. void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) { - if (SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end()) - SpillPt2VirtMap[Pt].push_back(std::make_pair(virtReg, isKill)); + std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator + I = SpillPt2VirtMap.find(Pt); + if (I != SpillPt2VirtMap.end()) + I->second.push_back(std::make_pair(virtReg, isKill)); else { std::vector<std::pair<unsigned,bool> > Virts; Virts.push_back(std::make_pair(virtReg, isKill)); @@ -289,7 +296,7 @@ namespace llvm { /// @brief - transfer spill point information from one instruction to /// another. void transferSpillPts(MachineInstr *Old, MachineInstr *New) { - std::map<MachineInstr*,std::vector<std::pair<unsigned,bool> > >::iterator + std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator I = SpillPt2VirtMap.find(Old); if (I == SpillPt2VirtMap.end()) return; @@ -315,8 +322,10 @@ namespace llvm { /// @brief records the specified MachineInstr as a restore point for virtReg. void addRestorePoint(unsigned virtReg, MachineInstr *Pt) { - if (RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end()) - RestorePt2VirtMap[Pt].push_back(virtReg); + std::map<MachineInstr*, std::vector<unsigned> >::iterator I = + RestorePt2VirtMap.find(Pt); + if (I != RestorePt2VirtMap.end()) + I->second.push_back(virtReg); else { std::vector<unsigned> Virts; Virts.push_back(virtReg); @@ -327,7 +336,7 @@ namespace llvm { /// @brief - transfer restore point information from one instruction to /// another. void transferRestorePts(MachineInstr *Old, MachineInstr *New) { - std::map<MachineInstr*,std::vector<unsigned> >::iterator I = + std::map<MachineInstr*, std::vector<unsigned> >::iterator I = RestorePt2VirtMap.find(Old); if (I == RestorePt2VirtMap.end()) return; @@ -430,6 +439,40 @@ namespace llvm { /// the folded instruction map and spill point map. void RemoveMachineInstrFromMaps(MachineInstr *MI); + /// FindUnusedRegisters - Gather a list of allocatable registers that + /// have not been allocated to any virtual register. + bool FindUnusedRegisters(const TargetRegisterInfo *TRI, + LiveIntervals* LIs); + + /// HasUnusedRegisters - Return true if there are any allocatable registers + /// that have not been allocated to any virtual register. + bool HasUnusedRegisters() const { + return !UnusedRegs.none(); + } + + /// setRegisterUsed - Remember the physical register is now used. + void setRegisterUsed(unsigned Reg) { + UnusedRegs.reset(Reg); + } + + /// isRegisterUnused - Return true if the physical register has not been + /// used. + bool isRegisterUnused(unsigned Reg) const { + return UnusedRegs[Reg]; + } + + /// getFirstUnusedRegister - Return the first physical register that has not + /// been used. + unsigned getFirstUnusedRegister(const TargetRegisterClass *RC) { + int Reg = UnusedRegs.find_first(); + while (Reg != -1) { + if (RC->contains(Reg)) + return (unsigned)Reg; + Reg = UnusedRegs.find_next(Reg); + } + return 0; + } + void print(std::ostream &OS, const Module* M = 0) const; void print(std::ostream *OS) const { if (OS) print(*OS); } void dump() const; |