aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/MachineRegisterInfo.h8
-rw-r--r--lib/CodeGen/LiveIntervalUnion.cpp6
-rw-r--r--lib/CodeGen/LiveIntervalUnion.h3
-rw-r--r--lib/CodeGen/RegAllocGreedy.cpp201
-rw-r--r--lib/CodeGen/VirtRegMap.h5
-rw-r--r--test/CodeGen/ARM/lsr-unfolded-offset.ll11
-rw-r--r--test/CodeGen/X86/2009-12-01-EarlyClobberBug.ll7
-rw-r--r--test/CodeGen/X86/divide-by-constant.ll2
-rw-r--r--test/CodeGen/X86/lsr-reuse-trunc.ll5
-rw-r--r--test/CodeGen/X86/peep-test-3.ll2
-rw-r--r--test/CodeGen/X86/sse3.ll6
11 files changed, 176 insertions, 80 deletions
diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h
index 87541086b2..1079726365 100644
--- a/include/llvm/CodeGen/MachineRegisterInfo.h
+++ b/include/llvm/CodeGen/MachineRegisterInfo.h
@@ -225,6 +225,14 @@ public:
return RegAllocHints[Reg];
}
+ /// getSimpleHint - Return the preferred register allocation hint, or 0 if a
+ /// standard simple hint (Type == 0) is not set.
+ unsigned getSimpleHint(unsigned Reg) const {
+ std::pair<unsigned, unsigned> Hint = getRegAllocationHint(Reg);
+ return Hint.first ? 0 : Hint.second;
+ }
+
+
//===--------------------------------------------------------------------===//
// Physical Register Use Info
//===--------------------------------------------------------------------===//
diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index b67f96667b..70003e7cc8 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -244,7 +244,7 @@ bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
//
// For comments on how to speed it up, see Query::findIntersection().
unsigned LiveIntervalUnion::Query::
-collectInterferingVRegs(unsigned MaxInterferingRegs, float MaxWeight) {
+collectInterferingVRegs(unsigned MaxInterferingRegs) {
InterferenceResult IR = firstInterference();
LiveInterval::iterator VirtRegEnd = VirtReg->end();
LiveInterval *RecentInterferingVReg = NULL;
@@ -287,10 +287,6 @@ collectInterferingVRegs(unsigned MaxInterferingRegs, float MaxWeight) {
RecentInterferingVReg = IR.LiveUnionI.value();
++IR.LiveUnionI;
- // Stop collecting when the max weight is exceeded.
- if (RecentInterferingVReg->weight >= MaxWeight)
- return InterferingVRegs.size();
-
continue;
}
// VirtRegI may have advanced far beyond LiveUnionI,
diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h
index c83578e99c..5e78d5e850 100644
--- a/lib/CodeGen/LiveIntervalUnion.h
+++ b/lib/CodeGen/LiveIntervalUnion.h
@@ -229,8 +229,7 @@ public:
// Count the virtual registers in this union that interfere with this
// query's live virtual register, up to maxInterferingRegs.
- unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX,
- float MaxWeight = HUGE_VALF);
+ unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
// Was this virtual register visited during collectInterferingVRegs?
bool isSeenInterference(LiveInterval *VReg) const;
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 3434a92bf3..d79573c205 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -133,6 +133,20 @@ class RAGreedy : public MachineFunctionPass,
}
}
+ /// Cost of evicting interference.
+ struct EvictionCost {
+ unsigned BrokenHints; ///< Total number of broken hints.
+ float MaxWeight; ///< Maximum spill weight evicted.
+
+ EvictionCost(unsigned B = 0) : BrokenHints(B), MaxWeight(0) {}
+
+ bool operator<(const EvictionCost &O) const {
+ if (BrokenHints != O.BrokenHints)
+ return BrokenHints < O.BrokenHints;
+ return MaxWeight < O.MaxWeight;
+ }
+ };
+
// splitting state.
std::auto_ptr<SplitAnalysis> SA;
std::auto_ptr<SplitEditor> SE;
@@ -197,8 +211,10 @@ private:
void splitAroundRegion(LiveInterval&, GlobalSplitCandidate&,
SmallVectorImpl<LiveInterval*>&);
void calcGapWeights(unsigned, SmallVectorImpl<float>&);
- bool canEvict(LiveInterval &A, LiveInterval &B);
- bool canEvictInterference(LiveInterval&, unsigned, float&);
+ bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
+ bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
+ void evictInterference(LiveInterval&, unsigned,
+ SmallVectorImpl<LiveInterval*>&);
unsigned tryAssign(LiveInterval&, AllocationOrder&,
SmallVectorImpl<LiveInterval*>&);
@@ -382,7 +398,21 @@ unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
if (!PhysReg || Order.isHint(PhysReg))
return PhysReg;
- // PhysReg is available. Try to evict interference from a cheaper alternative.
+ // PhysReg is available, but there may be a better choice.
+
+ // If we missed a simple hint, try to cheaply evict interference from the
+ // preferred register.
+ if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
+ if (Order.isHint(Hint)) {
+ DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
+ EvictionCost MaxCost(1);
+ if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
+ evictInterference(VirtReg, Hint, NewVRegs);
+ return Hint;
+ }
+ }
+
+ // Try to evict interference from a cheaper alternative.
unsigned Cost = TRI->getCostPerUse(PhysReg);
// Most registers have 0 additional cost.
@@ -400,23 +430,42 @@ unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
// Interference eviction
//===----------------------------------------------------------------------===//
-/// canEvict - determine if A can evict the assigned live range B. The eviction
-/// policy defined by this function together with the allocation order defined
-/// by enqueue() decides which registers ultimately end up being split and
-/// spilled.
+/// shouldEvict - determine if A should evict the assigned live range B. The
+/// eviction policy defined by this function together with the allocation order
+/// defined by enqueue() decides which registers ultimately end up being split
+/// and spilled.
///
/// Cascade numbers are used to prevent infinite loops if this function is a
/// cyclic relation.
-bool RAGreedy::canEvict(LiveInterval &A, LiveInterval &B) {
+///
+/// @param A The live range to be assigned.
+/// @param IsHint True when A is about to be assigned to its preferred
+/// register.
+/// @param B The live range to be evicted.
+/// @param BreaksHint True when B is already assigned to its preferred register.
+bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
+ LiveInterval &B, bool BreaksHint) {
+ bool CanSplit = getStage(B) <= RS_Second;
+
+ // Be fairly aggressive about following hints as long as the evictee can be
+ // split.
+ if (CanSplit && IsHint && !BreaksHint)
+ return true;
+
return A.weight > B.weight;
}
-/// canEvict - Return true if all interferences between VirtReg and PhysReg can
-/// be evicted.
-/// Return false if any interference is heavier than MaxWeight.
-/// On return, set MaxWeight to the maximal spill weight of an interference.
+/// canEvictInterference - Return true if all interferences between VirtReg and
+/// PhysReg can be evicted. When OnlyCheap is set, don't do anything
+///
+/// @param VirtReg Live range that is about to be assigned.
+/// @param PhysReg Desired register for assignment.
+/// @prarm IsHint True when PhysReg is VirtReg's preferred register.
+/// @param MaxCost Only look for cheaper candidates and update with new cost
+/// when returning true.
+/// @returns True when interference can be evicted cheaper than MaxCost.
bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
- float &MaxWeight) {
+ bool IsHint, EvictionCost &MaxCost) {
// Find VirtReg's cascade number. This will be unassigned if VirtReg was never
// involved in an eviction before. If a cascade number was assigned, deny
// evicting anything with the same or a newer cascade number. This prevents
@@ -428,11 +477,11 @@ bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
if (!Cascade)
Cascade = NextCascade;
- float Weight = 0;
+ EvictionCost Cost;
for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
// If there is 10 or more interferences, chances are one is heavier.
- if (Q.collectInterferingVRegs(10, MaxWeight) >= 10)
+ if (Q.collectInterferingVRegs(10) >= 10)
return false;
// Check if any interfering live range is heavier than MaxWeight.
@@ -440,19 +489,69 @@ bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
LiveInterval *Intf = Q.interferingVRegs()[i - 1];
if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
return false;
- if (Cascade <= ExtraRegInfo[Intf->reg].Cascade)
+ // Never evict spill products. They cannot split or spill.
+ if (getStage(*Intf) == RS_Spill)
return false;
- if (Intf->weight >= MaxWeight)
+ // Once a live range becomes small enough, it is urgent that we find a
+ // register for it. This is indicated by an infinite spill weight. These
+ // urgent live ranges get to evict almost anything.
+ bool Urgent = !VirtReg.isSpillable() && Intf->isSpillable();
+ // Only evict older cascades or live ranges without a cascade.
+ unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
+ if (Cascade <= IntfCascade) {
+ if (!Urgent)
+ return false;
+ // We permit breaking cascades for urgent evictions. It should be the
+ // last resort, though, so make it really expensive.
+ Cost.BrokenHints += 10;
+ }
+ // Would this break a satisfied hint?
+ bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
+ // Update eviction cost.
+ Cost.BrokenHints += BreaksHint;
+ Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
+ // Abort if this would be too expensive.
+ if (!(Cost < MaxCost))
return false;
- if (!canEvict(VirtReg, *Intf))
+ // Finally, apply the eviction policy for non-urgent evictions.
+ if (!Urgent && !shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
return false;
- Weight = std::max(Weight, Intf->weight);
}
}
- MaxWeight = Weight;
+ MaxCost = Cost;
return true;
}
+/// evictInterference - Evict any interferring registers that prevent VirtReg
+/// from being assigned to Physreg. This assumes that canEvictInterference
+/// returned true.
+void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
+ SmallVectorImpl<LiveInterval*> &NewVRegs) {
+ // Make sure that VirtReg has a cascade number, and assign that cascade
+ // number to every evicted register. These live ranges than then only be
+ // evicted by a newer cascade, preventing infinite loops.
+ unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
+ if (!Cascade)
+ Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
+
+ DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
+ << " interference: Cascade " << Cascade << '\n');
+ for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
+ LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
+ assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
+ for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
+ LiveInterval *Intf = Q.interferingVRegs()[i];
+ unassign(*Intf, VRM->getPhys(Intf->reg));
+ assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
+ VirtReg.isSpillable() < Intf->isSpillable()) &&
+ "Cannot decrease cascade number, illegal eviction");
+ ExtraRegInfo[Intf->reg].Cascade = Cascade;
+ ++NumEvicted;
+ NewVRegs.push_back(Intf);
+ }
+ }
+}
+
/// tryEvict - Try to evict all interferences for a physreg.
/// @param VirtReg Currently unassigned virtual register.
/// @param Order Physregs to try.
@@ -463,31 +562,37 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
unsigned CostPerUseLimit) {
NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
- // Keep track of the lightest single interference seen so far.
- float BestWeight = HUGE_VALF;
+ // Keep track of the cheapest interference seen so far.
+ EvictionCost BestCost(~0u);
unsigned BestPhys = 0;
+ // When we are just looking for a reduced cost per use, don't break any
+ // hints, and only evict smaller spill weights.
+ if (CostPerUseLimit < ~0u) {
+ BestCost.BrokenHints = 0;
+ BestCost.MaxWeight = VirtReg.weight;
+ }
+
Order.rewind();
while (unsigned PhysReg = Order.next()) {
if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
continue;
- // The first use of a register in a function has cost 1.
- if (CostPerUseLimit == 1 && !MRI->isPhysRegUsed(PhysReg))
- continue;
-
- float Weight = BestWeight;
- if (!canEvictInterference(VirtReg, PhysReg, Weight))
- continue;
-
- // This is an eviction candidate.
- DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " interference = "
- << Weight << '\n');
- if (BestPhys && Weight >= BestWeight)
+ // The first use of a callee-saved register in a function has cost 1.
+ // Don't start using a CSR when the CostPerUseLimit is low.
+ if (CostPerUseLimit == 1)
+ if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
+ if (!MRI->isPhysRegUsed(CSR)) {
+ DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
+ << PrintReg(CSR, TRI) << '\n');
+ continue;
+ }
+
+ if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
continue;
// Best so far.
BestPhys = PhysReg;
- BestWeight = Weight;
+
// Stop if the hint can be used.
if (Order.isHint(PhysReg))
break;
@@ -496,29 +601,7 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
if (!BestPhys)
return 0;
- // We will evict interference. Make sure that VirtReg has a cascade number,
- // and assign that cascade number to every evicted register. These live
- // ranges than then only be evicted by a newer cascade, preventing infinite
- // loops.
- unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
- if (!Cascade)
- Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
-
- DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI)
- << " interference: Cascade " << Cascade << '\n');
- for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
- LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
- assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
- for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
- LiveInterval *Intf = Q.interferingVRegs()[i];
- unassign(*Intf, VRM->getPhys(Intf->reg));
- assert(ExtraRegInfo[Intf->reg].Cascade < Cascade &&
- "Cannot decrease cascade number, illegal eviction");
- ExtraRegInfo[Intf->reg].Cascade = Cascade;
- ++NumEvicted;
- NewVRegs.push_back(Intf);
- }
- }
+ evictInterference(VirtReg, BestPhys, NewVRegs);
return BestPhys;
}
@@ -1552,7 +1635,7 @@ unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
// If we couldn't allocate a register from spilling, there is probably some
// invalid inline assembly. The base class wil report it.
- if (Stage >= RS_Spill)
+ if (Stage >= RS_Spill || !VirtReg.isSpillable())
return ~0u;
// Try splitting VirtReg or interferences.
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index ba50f4e423..03abff3569 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -208,6 +208,11 @@ namespace llvm {
/// @brief returns the register allocation preference.
unsigned getRegAllocPref(unsigned virtReg);
+ /// @brief returns true if VirtReg is assigned to its preferred physreg.
+ bool hasPreferredPhys(unsigned VirtReg) {
+ return getPhys(VirtReg) == getRegAllocPref(VirtReg);
+ }
+
/// @brief records virtReg is a split live interval from SReg.
void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
Virt2SplitMap[virtReg] = SReg;
diff --git a/test/CodeGen/ARM/lsr-unfolded-offset.ll b/test/CodeGen/ARM/lsr-unfolded-offset.ll
index e3e6eae31f..61b25bb94a 100644
--- a/test/CodeGen/ARM/lsr-unfolded-offset.ll
+++ b/test/CodeGen/ARM/lsr-unfolded-offset.ll
@@ -4,12 +4,13 @@
; register pressure and therefore spilling. There is more room for improvement
; here.
-; CHECK: sub sp, #{{32|24}}
+; CHECK: sub sp, #{{32|28|24}}
-; CHECK: ldr r{{.*}}, [sp, #4]
-; CHECK-NEXT: ldr r{{.*}}, [sp, #16]
-; CHECK-NEXT: ldr r{{.*}}, [sp, #12]
-; CHECK-NEXT: adds
+; CHECK: %for.inc
+; CHECK: ldr{{(.w)?}} r{{.*}}, [sp, #
+; CHECK: ldr{{(.w)?}} r{{.*}}, [sp, #
+; CHECK: ldr{{(.w)?}} r{{.*}}, [sp, #
+; CHECK: add
target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:32:64-v128:32:128-a0:0:32-n32"
target triple = "thumbv7-apple-macosx10.7.0"
diff --git a/test/CodeGen/X86/2009-12-01-EarlyClobberBug.ll b/test/CodeGen/X86/2009-12-01-EarlyClobberBug.ll
index 1e7a418d1d..07003234a9 100644
--- a/test/CodeGen/X86/2009-12-01-EarlyClobberBug.ll
+++ b/test/CodeGen/X86/2009-12-01-EarlyClobberBug.ll
@@ -22,8 +22,11 @@ return: ; preds = %entry
define void @t2() nounwind ssp {
entry:
; CHECK: t2:
-; CHECK: movl %eax, %ecx
-; CHECK: %ecx = foo (%ecx, %eax)
+; CHECK: movl
+; CHECK: [[D2:%e.x]] = foo
+; CHECK: ([[D2]],
+; CHECK-NOT: [[D2]]
+; CHECK: )
%b = alloca i32 ; <i32*> [#uses=2]
%a = alloca i32 ; <i32*> [#uses=1]
%"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
diff --git a/test/CodeGen/X86/divide-by-constant.ll b/test/CodeGen/X86/divide-by-constant.ll
index 08e3272a37..87c1be51f1 100644
--- a/test/CodeGen/X86/divide-by-constant.ll
+++ b/test/CodeGen/X86/divide-by-constant.ll
@@ -40,7 +40,7 @@ entry:
%div = sdiv i16 %x, 33 ; <i32> [#uses=1]
ret i16 %div
; CHECK: test4:
-; CHECK: imull $1986, %eax, %eax
+; CHECK: imull $1986, %eax, %
}
define i32 @test5(i32 %A) nounwind {
diff --git a/test/CodeGen/X86/lsr-reuse-trunc.ll b/test/CodeGen/X86/lsr-reuse-trunc.ll
index 47705190b0..1f87089f80 100644
--- a/test/CodeGen/X86/lsr-reuse-trunc.ll
+++ b/test/CodeGen/X86/lsr-reuse-trunc.ll
@@ -5,8 +5,9 @@
; stick with indexing here.
; CHECK: movaps (%{{rsi|rdx}},%rax,4), [[X3:%xmm[0-9]+]]
-; CHECK: movaps
-; CHECK: [[X3]], (%{{rdi|rcx}},%rax,4)
+; CHECK: cvtdq2ps
+; CHECK: orps {{%xmm[0-9]+}}, [[X4:%xmm[0-9]+]]
+; CHECK: movaps [[X4]], (%{{rdi|rcx}},%rax,4)
; CHECK: addq $4, %rax
; CHECK: cmpl %eax, (%{{rdx|r8}})
; CHECK-NEXT: jg
diff --git a/test/CodeGen/X86/peep-test-3.ll b/test/CodeGen/X86/peep-test-3.ll
index a34a9784cd..528c4bcc74 100644
--- a/test/CodeGen/X86/peep-test-3.ll
+++ b/test/CodeGen/X86/peep-test-3.ll
@@ -9,7 +9,7 @@ entry:
%0 = ptrtoint float* %A to i32 ; <i32> [#uses=1]
%1 = and i32 %0, 3 ; <i32> [#uses=1]
%2 = xor i32 %IA, 1 ; <i32> [#uses=1]
-; CHECK: orl %ecx, %edx
+; CHECK: orl %e
; CHECK-NEXT: je
%3 = or i32 %2, %1 ; <i32> [#uses=1]
%4 = icmp eq i32 %3, 0 ; <i1> [#uses=1]
diff --git a/test/CodeGen/X86/sse3.ll b/test/CodeGen/X86/sse3.ll
index 8c2e58d503..6658329b92 100644
--- a/test/CodeGen/X86/sse3.ll
+++ b/test/CodeGen/X86/sse3.ll
@@ -169,10 +169,10 @@ define internal void @t10() nounwind {
; X64: t10:
; X64: pextrw $4, [[X0:%xmm[0-9]+]], %eax
; X64: unpcklpd [[X1:%xmm[0-9]+]]
-; X64: pshuflw $8, [[X1]], [[X1]]
-; X64: pinsrw $2, %eax, [[X1]]
+; X64: pshuflw $8, [[X1]], [[X2:%xmm[0-9]+]]
+; X64: pinsrw $2, %eax, [[X2]]
; X64: pextrw $6, [[X0]], %eax
-; X64: pinsrw $3, %eax, [[X1]]
+; X64: pinsrw $3, %eax, [[X2]]
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-24 12:38:29 +0000