aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocGreedy.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/RegAllocGreedy.cpp')
-rw-r--r--lib/CodeGen/RegAllocGreedy.cpp65
1 files changed, 41 insertions, 24 deletions
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 81b21b442437..771fc46415db 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -1,9 +1,8 @@
//===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
@@ -138,7 +137,7 @@ CSRFirstTimeCost("regalloc-csr-first-time-cost",
cl::init(0), cl::Hidden);
static cl::opt<bool> ConsiderLocalIntervalCost(
- "condsider-local-interval-cost", cl::Hidden,
+ "consider-local-interval-cost", cl::Hidden,
cl::desc("Consider the cost of local intervals created by a split "
"candidate when choosing the best split candidate."),
cl::init(false));
@@ -465,7 +464,8 @@ private:
void calcGapWeights(unsigned, SmallVectorImpl<float>&);
unsigned canReassign(LiveInterval &VirtReg, unsigned PrevReg);
bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
- bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
+ bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&,
+ const SmallVirtRegSet&);
bool canEvictInterferenceInRange(LiveInterval &VirtReg, unsigned PhysReg,
SlotIndex Start, SlotIndex End,
EvictionCost &MaxCost);
@@ -479,9 +479,11 @@ private:
const SmallVirtRegSet &FixedRegisters);
unsigned tryAssign(LiveInterval&, AllocationOrder&,
- SmallVectorImpl<unsigned>&);
+ SmallVectorImpl<unsigned>&,
+ const SmallVirtRegSet&);
unsigned tryEvict(LiveInterval&, AllocationOrder&,
- SmallVectorImpl<unsigned>&, unsigned = ~0u);
+ SmallVectorImpl<unsigned>&, unsigned,
+ const SmallVirtRegSet&);
unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
SmallVectorImpl<unsigned>&);
unsigned isSplitBenefitWorthCost(LiveInterval &VirtReg);
@@ -508,7 +510,8 @@ private:
unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
SmallVectorImpl<unsigned>&);
unsigned trySplit(LiveInterval&, AllocationOrder&,
- SmallVectorImpl<unsigned>&);
+ SmallVectorImpl<unsigned>&,
+ const SmallVirtRegSet&);
unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
SmallVectorImpl<unsigned> &,
SmallVirtRegSet &, unsigned);
@@ -758,7 +761,8 @@ LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
/// tryAssign - Try to assign VirtReg to an available register.
unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
AllocationOrder &Order,
- SmallVectorImpl<unsigned> &NewVRegs) {
+ SmallVectorImpl<unsigned> &NewVRegs,
+ const SmallVirtRegSet &FixedRegisters) {
Order.rewind();
unsigned PhysReg;
while ((PhysReg = Order.next()))
@@ -776,7 +780,7 @@ unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
LLVM_DEBUG(dbgs() << "missed hint " << printReg(Hint, TRI) << '\n');
EvictionCost MaxCost;
MaxCost.setBrokenHints(1);
- if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
+ if (canEvictInterference(VirtReg, Hint, true, MaxCost, FixedRegisters)) {
evictInterference(VirtReg, Hint, NewVRegs);
return Hint;
}
@@ -794,7 +798,7 @@ unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is available at cost "
<< Cost << '\n');
- unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
+ unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
return CheapReg ? CheapReg : PhysReg;
}
@@ -866,7 +870,8 @@ bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
/// when returning true.
/// @returns True when interference can be evicted cheaper than MaxCost.
bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
- bool IsHint, EvictionCost &MaxCost) {
+ bool IsHint, EvictionCost &MaxCost,
+ const SmallVirtRegSet &FixedRegisters) {
// It is only possible to evict virtual register interference.
if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
return false;
@@ -896,6 +901,13 @@ bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
LiveInterval *Intf = Q.interferingVRegs()[i - 1];
assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) &&
"Only expecting virtual register interference from query");
+
+ // Do not allow eviction of a virtual register if we are in the middle
+ // of last-chance recoloring and this virtual register is one that we
+ // have scavenged a physical register for.
+ if (FixedRegisters.count(Intf->reg))
+ return false;
+
// Never evict spill products. They cannot split or spill.
if (getStage(*Intf) == RS_Done)
return false;
@@ -1094,7 +1106,8 @@ bool RAGreedy::isUnusedCalleeSavedReg(unsigned PhysReg) const {
unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
AllocationOrder &Order,
SmallVectorImpl<unsigned> &NewVRegs,
- unsigned CostPerUseLimit) {
+ unsigned CostPerUseLimit,
+ const SmallVirtRegSet &FixedRegisters) {
NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
TimePassesIsEnabled);
@@ -1142,7 +1155,8 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
continue;
}
- if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
+ if (!canEvictInterference(VirtReg, PhysReg, false, BestCost,
+ FixedRegisters))
continue;
// Best so far.
@@ -2248,8 +2262,8 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
LLVM_DEBUG(dbgs() << RMS.size() << " regmasks in block:");
// Constrain to VirtReg's live range.
- unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
- Uses.front().getRegSlot()) - RMS.begin();
+ unsigned ri =
+ llvm::lower_bound(RMS, Uses.front().getRegSlot()) - RMS.begin();
unsigned re = RMS.size();
for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
// Look for Uses[i] <= RMS <= Uses[i+1].
@@ -2444,7 +2458,8 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
/// assignable.
/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
- SmallVectorImpl<unsigned>&NewVRegs) {
+ SmallVectorImpl<unsigned>&NewVRegs,
+ const SmallVirtRegSet &FixedRegisters) {
// Ranges must be Split2 or less.
if (getStage(VirtReg) >= RS_Spill)
return 0;
@@ -2472,7 +2487,7 @@ unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
if (SA->didRepairRange()) {
// VirtReg has changed, so all cached queries are invalid.
Matrix->invalidateVirtRegs();
- if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
+ if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs, FixedRegisters))
return PhysReg;
}
@@ -2611,6 +2626,7 @@ unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
DenseMap<unsigned, unsigned> VirtRegToPhysReg;
// Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
// this recoloring "session".
+ assert(!FixedRegisters.count(VirtReg.reg));
FixedRegisters.insert(VirtReg.reg);
SmallVector<unsigned, 4> CurrentNewVRegs;
@@ -2858,14 +2874,14 @@ void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) {
if (!Instr.isFullCopy())
continue;
// Look for the other end of the copy.
- unsigned OtherReg = Instr.getOperand(0).getReg();
+ Register OtherReg = Instr.getOperand(0).getReg();
if (OtherReg == Reg) {
OtherReg = Instr.getOperand(1).getReg();
if (OtherReg == Reg)
continue;
}
// Get the current assignment.
- unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
+ Register OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
? OtherReg
: VRM->getPhys(OtherReg);
// Push the collected information.
@@ -3022,7 +3038,7 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
unsigned CostPerUseLimit = ~0u;
// First try assigning a free register.
AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
- if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
+ if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
// If VirtReg got an assignment, the eviction info is no longre relevant.
LastEvicted.clearEvicteeInfo(VirtReg.reg);
// When NewVRegs is not empty, we may have made decisions such as evicting
@@ -3049,7 +3065,8 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
// get a second chance until they have been split.
if (Stage != RS_Split)
if (unsigned PhysReg =
- tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
+ tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
+ FixedRegisters)) {
unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
// If VirtReg has a hint and that hint is broken record this
// virtual register as a recoloring candidate for broken hint.
@@ -3079,7 +3096,7 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
if (Stage < RS_Spill) {
// Try splitting VirtReg or interferences.
unsigned NewVRegSizeBefore = NewVRegs.size();
- unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
+ unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) {
// If VirtReg got split, the eviction info is no longre relevant.
LastEvicted.clearEvicteeInfo(VirtReg.reg);
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-08 13:36:04 +0000