STATISTIC(NumGlobalSplits, "Number of split global live ranges");
STATISTIC(NumLocalSplits, "Number of split local live ranges");
-STATISTIC(NumReassigned, "Number of interferences reassigned");
STATISTIC(NumEvicted, "Number of interferences evicted");
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
private:
void LRE_WillEraseInstruction(MachineInstr*);
-
- bool checkUncachedInterference(LiveInterval&, unsigned);
- LiveInterval *getSingleInterference(LiveInterval&, unsigned);
- bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
+ bool LRE_CanEraseVirtReg(unsigned);
+ void LRE_WillShrinkVirtReg(unsigned);
void mapGlobalInterference(unsigned, SmallVectorImpl<IndexPair>&);
float calcSplitConstraints(const SmallVectorImpl<IndexPair>&);
unsigned nextSplitPoint(unsigned);
bool canEvictInterference(LiveInterval&, unsigned, float&);
- unsigned tryReassign(LiveInterval&, AllocationOrder&,
- SmallVectorImpl<LiveInterval*>&);
unsigned tryEvict(LiveInterval&, AllocationOrder&,
SmallVectorImpl<LiveInterval*>&);
unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
VRM->RemoveMachineInstrFromMaps(MI);
}
+bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
+ if (unsigned PhysReg = VRM->getPhys(VirtReg)) {
+ unassign(LIS->getInterval(VirtReg), PhysReg);
+ return true;
+ }
+ // Unassigned virtreg is probably in the priority queue.
+ // RegAllocBase will erase it after dequeueing.
+ return false;
+}
+
+void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
+ unsigned PhysReg = VRM->getPhys(VirtReg);
+ if (!PhysReg)
+ return;
+
+ // Register is assigned, put it back on the queue for reassignment.
+ LiveInterval &LI = LIS->getInterval(VirtReg);
+ unassign(LI, PhysReg);
+ enqueue(&LI);
+}
void RAGreedy::releaseMemory() {
SpillerInstance.reset(0);
unsigned Prio;
LRStage.grow(Reg);
- if (LRStage[Reg] == RS_Original)
- // 1st generation ranges are handled first, long -> short.
+ if (LRStage[Reg] == RS_Second)
+ // Unsplit ranges that couldn't be allocated immediately are deferred until
+ // everything else has been allocated. Long ranges are allocated last so
+ // they are split against realistic interference.
+ Prio = (1u << 31) - Size;
+ else {
+ // Everything else is allocated in long->short order. Long ranges that don't
+ // fit should be spilled ASAP so they don't create interference.
Prio = (1u << 31) + Size;
- else
- // Repeat offenders are handled second, short -> long
- Prio = (1u << 30) - Size;
- // Boost ranges that have a physical register hint.
- const unsigned Hint = VRM->getRegAllocPref(Reg);
- if (TargetRegisterInfo::isPhysicalRegister(Hint))
- Prio |= (1u << 30);
+ // Boost ranges that have a physical register hint.
+ if (TargetRegisterInfo::isPhysicalRegister(VRM->getRegAllocPref(Reg)))
+ Prio |= (1u << 30);
+ }
Queue.push(std::make_pair(Prio, Reg));
}
return LI;
}
-//===----------------------------------------------------------------------===//
-// Register Reassignment
-//===----------------------------------------------------------------------===//
-
-// Check interference without using the cache.
-bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
- unsigned PhysReg) {
- for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
- LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
- if (subQ.checkInterference())
- return true;
- }
- return false;
-}
-
-/// getSingleInterference - Return the single interfering virtual register
-/// assigned to PhysReg. Return 0 if more than one virtual register is
-/// interfering.
-LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
- unsigned PhysReg) {
- // Check physreg and aliases.
- LiveInterval *Interference = 0;
- for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
- LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
- if (Q.checkInterference()) {
- if (Interference)
- return 0;
- if (Q.collectInterferingVRegs(2) > 1)
- return 0;
- Interference = Q.interferingVRegs().front();
- }
- }
- return Interference;
-}
-
-// Attempt to reassign this virtual register to a different physical register.
-//
-// FIXME: we are not yet caching these "second-level" interferences discovered
-// in the sub-queries. These interferences can change with each call to
-// selectOrSplit. However, we could implement a "may-interfere" cache that
-// could be conservatively dirtied when we reassign or split.
-//
-// FIXME: This may result in a lot of alias queries. We could summarize alias
-// live intervals in their parent register's live union, but it's messy.
-bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
- unsigned WantedPhysReg) {
- assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
- "Can only reassign virtual registers");
- assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
- "inconsistent phys reg assigment");
-
- AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
- while (unsigned PhysReg = Order.next()) {
- // Don't reassign to a WantedPhysReg alias.
- if (TRI->regsOverlap(PhysReg, WantedPhysReg))
- continue;
-
- if (checkUncachedInterference(InterferingVReg, PhysReg))
- continue;
-
- // Reassign the interfering virtual reg to this physical reg.
- unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
- DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
- TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
- unassign(InterferingVReg, OldAssign);
- assign(InterferingVReg, PhysReg);
- ++NumReassigned;
- return true;
- }
- return false;
-}
-
-/// tryReassign - Try to reassign a single interference to a different physreg.
-/// @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,
- SmallVectorImpl<LiveInterval*> &NewVRegs){
- NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
-
- Order.rewind();
- 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;
- }
- return 0;
-}
-
-
//===----------------------------------------------------------------------===//
// Interference eviction
//===----------------------------------------------------------------------===//
IndexPair &IP = InterferenceRanges[i];
DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
<< Bundles->getBundle(BI.MBB->getNumber(), 1)
- << " intf [" << IP.first << ';' << IP.second << ')');
+ << " [" << BI.Start << ';' << BI.LastSplitPoint << '-'
+ << BI.Stop << ") intf [" << IP.first << ';' << IP.second
+ << ')');
// The interference interval should either be invalid or overlap MBB.
assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference");
IndexPair &IP = InterferenceRanges[i];
DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
- << " -> BB#" << BI.MBB->getNumber());
+ << " -> BB#" << BI.MBB->getNumber() << " [" << BI.Start << ';'
+ << BI.LastSplitPoint << '-' << BI.Stop << ')');
// Check interference entering the block.
if (!IP.first.isValid()) {
SE->finish();
++NumGlobalSplits;
- if (VerifyEnabled) {
+ if (VerifyEnabled)
MF->verify(this, "After splitting live range around region");
-
-#ifndef NDEBUG
- // Make sure that at least one of the new intervals can allocate to PhysReg.
- // That was the whole point of splitting the live range.
- bool found = false;
- for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
- ++I)
- if (!checkUncachedInterference(**I, PhysReg)) {
- found = true;
- break;
- }
- assert(found && "No allocatable intervals after pointless splitting");
-#endif
- }
}
unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
SmallVectorImpl<LiveInterval*> &NewVRegs) {
- LiveRangeStage Stage = getStage(VirtReg);
- if (Stage == RS_Original)
- LRStage[VirtReg.reg] = RS_Second;
-
// First try assigning a free register.
AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
while (unsigned PhysReg = Order.next()) {
return PhysReg;
}
- if (unsigned PhysReg = tryReassign(VirtReg, Order, NewVRegs))
- return PhysReg;
-
if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
return PhysReg;
// The first time we see a live range, don't try to split or spill.
// Wait until the second time, when all smaller ranges have been allocated.
// This gives a better picture of the interference to split around.
+ LiveRangeStage Stage = getStage(VirtReg);
if (Stage == RS_Original) {
+ LRStage[VirtReg.reg] = RS_Second;
+ DEBUG(dbgs() << "wait for second round\n");
NewVRegs.push_back(&VirtReg);
return 0;
}
// Finally spill VirtReg itself.
NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
- spiller().spill(&VirtReg, NewVRegs, 0);
+ LiveRangeEdit LRE(VirtReg, NewVRegs, this);
+ spiller().spill(LRE);
+
+ if (VerifyEnabled)
+ MF->verify(this, "After spilling");
// The live virtual register requesting allocation was spilled, so tell
// the caller not to allocate anything during this round.
projects / oota-llvm.git / blobdiff