diff --git a/llvm/include/llvm/CodeGen/LiveIntervalUnion.h b/llvm/include/llvm/CodeGen/LiveIntervalUnion.h --- a/llvm/include/llvm/CodeGen/LiveIntervalUnion.h +++ b/llvm/include/llvm/CodeGen/LiveIntervalUnion.h @@ -114,30 +114,30 @@ const LiveRange *LR = nullptr; LiveRange::const_iterator LRI; ///< current position in LR ConstSegmentIter LiveUnionI; ///< current position in LiveUnion - SmallVector InterferingVRegs; + Optional> InterferingVRegs; bool CheckedFirstInterference = false; bool SeenAllInterferences = false; unsigned Tag = 0; unsigned UserTag = 0; + public: + Query() = default; + Query(const LiveRange &LR, const LiveIntervalUnion &LIU) + : LiveUnion(&LIU), LR(&LR) {} + Query(const Query &) = delete; + Query &operator=(const Query &) = delete; + void reset(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion) { LiveUnion = &NewLiveUnion; LR = &NewLR; - InterferingVRegs.clear(); + InterferingVRegs = None; CheckedFirstInterference = false; SeenAllInterferences = false; Tag = NewLiveUnion.getTag(); UserTag = NewUserTag; } - public: - Query() = default; - Query(const LiveRange &LR, const LiveIntervalUnion &LIU): - LiveUnion(&LIU), LR(&LR) {} - Query(const Query &) = delete; - Query &operator=(const Query &) = delete; - void init(unsigned NewUserTag, const LiveRange &NewLR, const LiveIntervalUnion &NewLiveUnion) { if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion && @@ -164,7 +164,7 @@ // Vector generated by collectInterferingVRegs. const SmallVectorImpl &interferingVRegs() const { - return InterferingVRegs; + return *InterferingVRegs; } }; diff --git a/llvm/lib/CodeGen/LiveIntervalUnion.cpp b/llvm/lib/CodeGen/LiveIntervalUnion.cpp --- a/llvm/lib/CodeGen/LiveIntervalUnion.cpp +++ b/llvm/lib/CodeGen/LiveIntervalUnion.cpp @@ -112,7 +112,7 @@ // Scan the vector of interfering virtual registers in this union. Assume it's // quite small. bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { - return is_contained(InterferingVRegs, VirtReg); + return is_contained(*InterferingVRegs, VirtReg); } // Collect virtual registers in this union that interfere with this @@ -126,9 +126,12 @@ // unsigned LiveIntervalUnion::Query:: collectInterferingVRegs(unsigned MaxInterferingRegs) { + if (!InterferingVRegs) + InterferingVRegs.emplace(); + // Fast path return if we already have the desired information. - if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) - return InterferingVRegs.size(); + if (SeenAllInterferences || InterferingVRegs->size() >= MaxInterferingRegs) + return InterferingVRegs->size(); // Set up iterators on the first call. if (!CheckedFirstInterference) { @@ -157,14 +160,14 @@ LiveInterval *VReg = LiveUnionI.value(); if (VReg != RecentReg && !isSeenInterference(VReg)) { RecentReg = VReg; - InterferingVRegs.push_back(VReg); - if (InterferingVRegs.size() >= MaxInterferingRegs) - return InterferingVRegs.size(); + InterferingVRegs->push_back(VReg); + if (InterferingVRegs->size() >= MaxInterferingRegs) + return InterferingVRegs->size(); } // This LiveUnion segment is no longer interesting. if (!(++LiveUnionI).valid()) { SeenAllInterferences = true; - return InterferingVRegs.size(); + return InterferingVRegs->size(); } } @@ -185,7 +188,7 @@ LiveUnionI.advanceTo(LRI->start); } SeenAllInterferences = true; - return InterferingVRegs.size(); + return InterferingVRegs->size(); } void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, diff --git a/llvm/lib/CodeGen/LiveRegMatrix.cpp b/llvm/lib/CodeGen/LiveRegMatrix.cpp --- a/llvm/lib/CodeGen/LiveRegMatrix.cpp +++ b/llvm/lib/CodeGen/LiveRegMatrix.cpp @@ -216,7 +216,21 @@ // Check for interference with that segment for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { - if (query(LR, *Units).checkInterference()) + // LR is stack-allocated. LiveRegMatrix caches queries by a key that + // includes the address of the live range. If (for the same reg unit) this + // checkInterference overload is called twice, without any other query() + // calls in between (on heap-allocated LiveRanges) - which would invalidate + // the cached query - the LR address seen the second time may well be the + // same as that seen the first time, while the Start/End/valno may not - yet + // the same cached result would be fetched. To avoid that, we don't cache + // this query. + // + // FIXME: the usability of the Query API needs to be improved to avoid + // subtle bugs due to query identity. Avoiding caching, for example, would + // greatly simplify things. + LiveIntervalUnion::Query Q; + Q.reset(UserTag, LR, Matrix[*Units]); + if (Q.checkInterference()) return true; } return false; diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp --- a/llvm/lib/CodeGen/RegAllocGreedy.cpp +++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp @@ -471,12 +471,13 @@ bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const; bool canEvictInterference(LiveInterval &, MCRegister, bool, EvictionCost &, const SmallVirtRegSet &) const; - bool canEvictInterferenceInRange(LiveInterval &VirtReg, MCRegister PhysReg, - SlotIndex Start, SlotIndex End, - EvictionCost &MaxCost) const; + bool canEvictInterferenceInRange(const LiveInterval &VirtReg, + MCRegister PhysReg, SlotIndex Start, + SlotIndex End, EvictionCost &MaxCost) const; MCRegister getCheapestEvicteeWeight(const AllocationOrder &Order, - LiveInterval &VirtReg, SlotIndex Start, - SlotIndex End, float *BestEvictWeight); + const LiveInterval &VirtReg, + SlotIndex Start, SlotIndex End, + float *BestEvictWeight) const; void evictInterference(LiveInterval &, MCRegister, SmallVectorImpl &); bool mayRecolorAllInterferences(MCRegister PhysReg, LiveInterval &VirtReg, @@ -979,7 +980,7 @@ /// \param MaxCost Only look for cheaper candidates and update with new cost /// when returning true. /// \return True when interference can be evicted cheaper than MaxCost. -bool RAGreedy::canEvictInterferenceInRange(LiveInterval &VirtReg, +bool RAGreedy::canEvictInterferenceInRange(const LiveInterval &VirtReg, MCRegister PhysReg, SlotIndex Start, SlotIndex End, EvictionCost &MaxCost) const { @@ -987,6 +988,7 @@ for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); + Q.collectInterferingVRegs(); // Check if any interfering live range is heavier than MaxWeight. for (const LiveInterval *Intf : reverse(Q.interferingVRegs())) { @@ -1031,9 +1033,9 @@ /// \return The PhysReg which is the best candidate for eviction and the /// eviction cost in BestEvictweight MCRegister RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order, - LiveInterval &VirtReg, + const LiveInterval &VirtReg, SlotIndex Start, SlotIndex End, - float *BestEvictweight) { + float *BestEvictweight) const { EvictionCost BestEvictCost; BestEvictCost.setMax(); BestEvictCost.MaxWeight = VirtReg.weight(); @@ -1058,7 +1060,7 @@ /// returned true. void RAGreedy::evictInterference(LiveInterval &VirtReg, MCRegister PhysReg, SmallVectorImpl &NewVRegs) { - // Make sure that VirtReg has a cascade number, and assign that cascade + // Make sure th5at 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; @@ -1556,25 +1558,9 @@ return false; } - // Check if the local interval will evict a cheaper interval. - float CheapestEvictWeight = 0; - MCRegister FutureEvictedPhysReg = getCheapestEvicteeWeight( - Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(), - Cand.Intf.last(), &CheapestEvictWeight); - - // Have we found an interval that can be evicted? - if (FutureEvictedPhysReg) { - float splitArtifactWeight = - VRAI->futureWeight(LIS->getInterval(VirtRegToSplit), - Cand.Intf.first().getPrevIndex(), Cand.Intf.last()); - // Will the weight of the local interval be higher than the cheapest evictee - // weight? If so it will evict it and will not cause a spill. - if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight) - return false; - } - - // The local interval is not able to find non interferencing assignment and - // not able to evict a less worthy interval, therfore, it can cause a spill. + // The local interval is not able to find non interferencing assignment + // and not able to evict a less worthy interval, therfore, it can cause a + // spill. return true; } diff --git a/llvm/lib/Target/X86/X86Subtarget.h b/llvm/lib/Target/X86/X86Subtarget.h --- a/llvm/lib/Target/X86/X86Subtarget.h +++ b/llvm/lib/Target/X86/X86Subtarget.h @@ -941,7 +941,7 @@ return TargetSubtargetInfo::ANTIDEP_CRITICAL; } - bool enableAdvancedRASplitCost() const override { return true; } + bool enableAdvancedRASplitCost() const override { return false; } }; } // end namespace llvm diff --git a/llvm/test/CodeGen/X86/bug26810.ll b/llvm/test/CodeGen/X86/bug26810.ll --- a/llvm/test/CodeGen/X86/bug26810.ll +++ b/llvm/test/CodeGen/X86/bug26810.ll @@ -1,4 +1,4 @@ -; RUN: llc < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s +; RUN: llc -consider-local-interval-cost < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s ; Make sure bad eviction sequence doesnt occur ; Fix for bugzilla 26810. diff --git a/llvm/test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll b/llvm/test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll --- a/llvm/test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll +++ b/llvm/test/CodeGen/X86/greedy_regalloc_bad_eviction_sequence.ll @@ -1,4 +1,4 @@ -; RUN: llc < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s +; RUN: llc -consider-local-interval-cost < %s -march=x86 -regalloc=greedy -stop-after=greedy | FileCheck %s ; Make sure bad eviction sequence doesnt occur ; Part of the fix for bugzilla 26810. diff --git a/llvm/test/CodeGen/X86/i128-mul.ll b/llvm/test/CodeGen/X86/i128-mul.ll --- a/llvm/test/CodeGen/X86/i128-mul.ll +++ b/llvm/test/CodeGen/X86/i128-mul.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py -; RUN: llc < %s -mtriple=i686-unknown-unknown | FileCheck %s --check-prefix=X86-NOBMI +; RUN: llc -consider-local-interval-cost < %s -mtriple=i686-unknown-unknown | FileCheck %s --check-prefix=X86-NOBMI ; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=+bmi2 | FileCheck %s --check-prefix=X86-BMI ; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s --check-prefix=X64-NOBMI ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi2 | FileCheck %s --check-prefix=X64-BMI diff --git a/llvm/test/CodeGen/X86/mmx-arith.ll b/llvm/test/CodeGen/X86/mmx-arith.ll --- a/llvm/test/CodeGen/X86/mmx-arith.ll +++ b/llvm/test/CodeGen/X86/mmx-arith.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py -; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=+mmx,+sse2 | FileCheck -check-prefix=X32 %s +; RUN: llc -consider-local-interval-cost < %s -mtriple=i686-unknown-unknown -mattr=+mmx,+sse2 | FileCheck -check-prefix=X32 %s ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+mmx,+sse2 | FileCheck -check-prefix=X64 %s ;; A basic sanity check to make sure that MMX arithmetic actually compiles. diff --git a/llvm/test/CodeGen/X86/optimize-max-0.ll b/llvm/test/CodeGen/X86/optimize-max-0.ll --- a/llvm/test/CodeGen/X86/optimize-max-0.ll +++ b/llvm/test/CodeGen/X86/optimize-max-0.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py -; RUN: llc < %s | FileCheck %s +; RUN: llc -consider-local-interval-cost < %s | FileCheck %s ; LSR should be able to eliminate the max computations by ; making the loops use slt/ult comparisons instead of ne comparisons.