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",
createGreedyRegisterAllocator);
namespace {
-class RAGreedy : public MachineFunctionPass, public RegAllocBase {
+class RAGreedy : public MachineFunctionPass,
+ public RegAllocBase,
+ private LiveRangeEdit::Delegate {
+
// context
MachineFunction *MF;
BitVector ReservedRegs;
static char ID;
private:
- bool checkUncachedInterference(LiveInterval&, unsigned);
- LiveInterval *getSingleInterference(LiveInterval&, unsigned);
- bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
+ void LRE_WillEraseInstruction(MachineInstr*);
+ 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&,
MachineFunctionPass::getAnalysisUsage(AU);
}
+
+//===----------------------------------------------------------------------===//
+// LiveRangeEdit delegate methods
+//===----------------------------------------------------------------------===//
+
+void RAGreedy::LRE_WillEraseInstruction(MachineInstr *MI) {
+ // LRE itself will remove from SlotIndexes and parent basic block.
+ 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);
LRStage.clear();
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
//===----------------------------------------------------------------------===//
///
float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
float GlobalCost = 0;
- for (unsigned i = 0, e = SplitConstraints.size(); i != e; ++i) {
+ for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
+ SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
- unsigned Inserts = 0;
- // Broken entry preference?
- Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
- (BC.Entry == SpillPlacement::PrefReg);
- // Broken exit preference?
- Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
- (BC.Exit == SpillPlacement::PrefReg);
- if (Inserts)
- GlobalCost += Inserts * SpillPlacer->getBlockFrequency(BC.Number);
+ bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
+ bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
+ unsigned Ins = 0;
+
+ if (!BI.Uses)
+ Ins += RegIn != RegOut;
+ else {
+ if (BI.LiveIn)
+ Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
+ if (BI.LiveOut)
+ Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
+ }
+ if (Ins)
+ GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
}
- DEBUG({
- dbgs() << "Global cost = " << GlobalCost << " with bundles";
- for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
- dbgs() << " EB#" << i;
- dbgs() << ".\n";
- });
return GlobalCost;
}
SmallVector<IndexPair, 8> InterferenceRanges;
mapGlobalInterference(PhysReg, InterferenceRanges);
- SmallVector<LiveInterval*, 4> SpillRegs;
- LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
+ LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
SE->reset(LREdit);
// Create the main cross-block interval.
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,
mapGlobalInterference(PhysReg, GlobalCand[Cand].Interference);
float Cost = calcSplitConstraints(GlobalCand[Cand].Interference);
- DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " static split cost = " << Cost
- << '\n');
- if (BestReg && Cost >= BestCost)
+ DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
+ if (BestReg && Cost >= BestCost) {
+ DEBUG(dbgs() << " higher.\n");
continue;
+ }
SpillPlacer->placeSpills(SplitConstraints, LiveBundles);
// No live bundles, defer to splitSingleBlocks().
- if (!LiveBundles.any())
+ if (!LiveBundles.any()) {
+ DEBUG(dbgs() << " no bundles.\n");
continue;
+ }
Cost += calcGlobalSplitCost(LiveBundles);
+ DEBUG({
+ dbgs() << ", total = " << Cost << " with bundles";
+ for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
+ dbgs() << " EB#" << i;
+ dbgs() << ".\n";
+ });
if (!BestReg || Cost < BestCost) {
BestReg = PhysReg;
- BestCost = Cost;
+ BestCost = 0.98f * Cost; // Prevent rounding effects.
BestBundles.swap(LiveBundles);
}
}
<< '-' << Uses[BestAfter] << ", " << BestDiff
<< ", " << (BestAfter - BestBefore + 1) << " instrs\n");
- SmallVector<LiveInterval*, 4> SpillRegs;
- LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
+ LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
SE->reset(LREdit);
SE->openIntv();
if (Stage < RS_Block) {
SplitAnalysis::BlockPtrSet Blocks;
if (SA->getMultiUseBlocks(Blocks)) {
- SmallVector<LiveInterval*, 4> SpillRegs;
- LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
+ LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
SE->reset(LREdit);
SE->splitSingleBlocks(Blocks);
setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block);
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);
- SmallVector<LiveInterval*, 1> pendingSpills;
- spiller().spill(&VirtReg, NewVRegs, pendingSpills);
+ 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