aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/RegAllocGreedy.cpp
diff options
context:
space:
mode:
authorJakob Stoklund Olesen <stoklund@2pi.dk>2011-02-09 01:14:03 +0000
committerJakob Stoklund Olesen <stoklund@2pi.dk>2011-02-09 01:14:03 +0000
commit2710638db2eb84cd7eefb8bb9a1b7e5c49413d45 (patch)
tree94eb0449093393b76f1a8f12079c8640c8456f97 /lib/CodeGen/RegAllocGreedy.cpp
parentc3dca3f9d4a049102fa985aedbc65e53f4cf6c0d (diff)
downloadexternal_llvm-2710638db2eb84cd7eefb8bb9a1b7e5c49413d45.tar.gz
external_llvm-2710638db2eb84cd7eefb8bb9a1b7e5c49413d45.tar.bz2
external_llvm-2710638db2eb84cd7eefb8bb9a1b7e5c49413d45.zip
Evict a lighter single interference before attempting to split a live range.
Registers are not allocated strictly in spill weight order when live range splitting and spilling has created new shorter intervals with higher spill weights. When one of the new heavy intervals conflicts with a single lighter interval, simply evict the old interval instead of trying to split the heavy one. The lighter interval is a better candidate for splitting, it has a smaller use density. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125151 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/RegAllocGreedy.cpp')
-rw-r--r--lib/CodeGen/RegAllocGreedy.cpp70
1 files changed, 41 insertions, 29 deletions
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");