diff options
| -rw-r--r-- | lib/CodeGen/RegAllocBase.h | 9 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocBasic.cpp | 21 | ||||
| -rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 70 |
3 files changed, 64 insertions, 36 deletions
diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index a0416d27d8..8c7e5f53b8 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -139,6 +139,15 @@ protected: // exists, return the interfering register, which may be preg or an alias. unsigned checkPhysRegInterference(LiveInterval& VirtReg, unsigned PhysReg); + /// assign - Assign VirtReg to PhysReg. + /// This should not be called from selectOrSplit for the current register. + void assign(LiveInterval &VirtReg, unsigned PhysReg); + + /// unassign - Undo a previous assignment of VirtReg to PhysReg. + /// This can be invoked from selectOrSplit, but be careful to guarantee that + /// allocation is making progress. + void unassign(LiveInterval &VirtReg, unsigned PhysReg); + // Helper for spilling all live virtual registers currently unified under preg // that interfere with the most recently queried lvr. Return true if spilling // was successful, and append any new spilled/split intervals to splitLVRs. diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp index 1175923cd2..7fbb035ed6 100644 --- a/lib/CodeGen/RegAllocBasic.cpp +++ b/lib/CodeGen/RegAllocBasic.cpp @@ -238,6 +238,18 @@ seedLiveVirtRegs(std::priority_queue<std::pair<float, unsigned> > &VirtRegQ) { } } +void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { + assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); + VRM->assignVirt2Phys(VirtReg.reg, PhysReg); + PhysReg2LiveUnion[PhysReg].unify(VirtReg); +} + +void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { + assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); + PhysReg2LiveUnion[PhysReg].extract(VirtReg); + VRM->clearVirt(VirtReg.reg); +} + // Top-level driver to manage the queue of unassigned VirtRegs and call the // selectOrSplit implementation. void RegAllocBase::allocatePhysRegs() { @@ -264,9 +276,7 @@ void RegAllocBase::allocatePhysRegs() { if (AvailablePhysReg) { DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) << " for " << VirtReg << '\n'); - assert(!VRM->hasPhys(VirtReg.reg) && "duplicate vreg in union"); - VRM->assignVirt2Phys(VirtReg.reg, AvailablePhysReg); - PhysReg2LiveUnion[AvailablePhysReg].unify(VirtReg); + assign(VirtReg, AvailablePhysReg); } for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); I != E; ++I) { @@ -308,10 +318,7 @@ void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg, // Deallocate the interfering vreg by removing it from the union. // A LiveInterval instance may not be in a union during modification! - PhysReg2LiveUnion[PhysReg].extract(SpilledVReg); - - // Clear the vreg assignment. - VRM->clearVirt(SpilledVReg.reg); + unassign(SpilledVReg, PhysReg); // Spill the extracted interval. spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills); diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index cfef95e1e8..a0f129aaa8 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -133,7 +133,6 @@ private: bool checkUncachedInterference(LiveInterval&, unsigned); LiveInterval *getSingleInterference(LiveInterval&, unsigned); bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg); - bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg); float calcInterferenceWeight(LiveInterval&, unsigned); void calcLiveBlockInfo(LiveInterval&); float calcInterferenceInfo(LiveInterval&, unsigned); @@ -141,7 +140,8 @@ private: void splitAroundRegion(LiveInterval&, unsigned, const BitVector&, SmallVectorImpl<LiveInterval*>&); - unsigned tryReassign(LiveInterval&, AllocationOrder&); + unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&, + SmallVectorImpl<LiveInterval*>&); unsigned tryRegionSplit(LiveInterval&, AllocationOrder&, SmallVectorImpl<LiveInterval*>&); unsigned trySplit(LiveInterval&, AllocationOrder&, @@ -286,41 +286,54 @@ bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg, unsigned OldAssign = VRM->getPhys(InterferingVReg.reg); DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " << TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n'); - PhysReg2LiveUnion[OldAssign].extract(InterferingVReg); - VRM->clearVirt(InterferingVReg.reg); - VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg); - PhysReg2LiveUnion[PhysReg].unify(InterferingVReg); - + unassign(InterferingVReg, OldAssign); + assign(InterferingVReg, PhysReg); return true; } return false; } -/// reassignInterferences - Reassign all interferences to different physical -/// registers such that Virtreg can be assigned to PhysReg. -/// Currently this only works with a single interference. -/// @param VirtReg Currently unassigned virtual register. -/// @param PhysReg Physical register to be cleared. -/// @return True on success, false if nothing was changed. -bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) { - LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); - if (!InterferingVReg) - return false; - if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) - return false; - return reassignVReg(*InterferingVReg, PhysReg); -} - -/// tryReassign - Try to reassign interferences to different physregs. +/// tryReassignOrEvict - Try to reassign a single interferences to a different +/// physreg, or evict a single interference with a lower spill weight. /// @param VirtReg Currently unassigned virtual register. /// @param Order Physregs to try. /// @return Physreg to assign VirtReg, or 0. -unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) { +unsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg, + AllocationOrder &Order, + SmallVectorImpl<LiveInterval*> &NewVRegs){ NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled); + + // Keep track of the lightest single interference seen so far. + float BestWeight = VirtReg.weight; + LiveInterval *BestVirt = 0; + unsigned BestPhys = 0; + Order.rewind(); - while (unsigned PhysReg = Order.next()) - if (reassignInterferences(VirtReg, PhysReg)) + while (unsigned PhysReg = Order.next()) { + LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg); + if (!InterferingVReg) + continue; + if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg)) + continue; + if (reassignVReg(*InterferingVReg, PhysReg)) return PhysReg; + + // Cannot reassign, is this an eviction candidate? + if (InterferingVReg->weight < BestWeight) { + BestVirt = InterferingVReg; + BestPhys = PhysReg; + BestWeight = InterferingVReg->weight; + } + } + + // Nothing reassigned, can we evict a lighter single interference? + if (BestVirt) { + DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n'); + unassign(*BestVirt, VRM->getPhys(BestVirt->reg)); + NewVRegs.push_back(BestVirt); + return BestPhys; + } + return 0; } @@ -1029,8 +1042,7 @@ unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg, Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end()); for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) { LiveInterval *VReg = Q.interferingVRegs()[i]; - PhysReg2LiveUnion[*AI].extract(*VReg); - VRM->clearVirt(VReg->reg); + unassign(*VReg, *AI); } } @@ -1057,7 +1069,7 @@ unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, } // Try to reassign interferences. - if (unsigned PhysReg = tryReassign(VirtReg, Order)) + if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs)) return PhysReg; assert(NewVRegs.empty() && "Cannot append to existing NewVRegs"); |