From 40bc309911f0f92ff8b8f64d28cb13a2292695ff Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Tue, 16 Mar 2021 20:41:26 +0100 Subject: [PATCH] Revert "[regalloc] Ensure Query::collectInterferringVregs is called before interval iteration" This reverts commit d40b4911bd9aca0573752e065f29ddd9aff280e1. This causes a large compile-time regression: https://llvm-compile-time-tracker.com/compare.php?from=0aa637b2037d882ddf7861284169abf63f524677&to=d40b4911bd9aca0573752e065f29ddd9aff280e1&stat=instructions --- llvm/include/llvm/CodeGen/LiveIntervalUnion.h | 20 ++++++------- llvm/lib/CodeGen/LiveIntervalUnion.cpp | 19 +++++------- llvm/lib/CodeGen/LiveRegMatrix.cpp | 16 +--------- llvm/lib/CodeGen/RegAllocGreedy.cpp | 42 ++++++++++++++++++--------- 4 files changed, 47 insertions(+), 50 deletions(-) diff --git a/llvm/include/llvm/CodeGen/LiveIntervalUnion.h b/llvm/include/llvm/CodeGen/LiveIntervalUnion.h index 4ebe0f2..ad9e06d 100644 --- a/llvm/include/llvm/CodeGen/LiveIntervalUnion.h +++ b/llvm/include/llvm/CodeGen/LiveIntervalUnion.h @@ -114,30 +114,30 @@ public: const LiveRange *LR = nullptr; LiveRange::const_iterator LRI; ///< current position in LR ConstSegmentIter LiveUnionI; ///< current position in LiveUnion - Optional> InterferingVRegs; + SmallVector 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 = None; + InterferingVRegs.clear(); 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 @@ public: // 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 index dfa523d..7ccb8df 100644 --- a/llvm/lib/CodeGen/LiveIntervalUnion.cpp +++ b/llvm/lib/CodeGen/LiveIntervalUnion.cpp @@ -112,7 +112,7 @@ LiveInterval *LiveIntervalUnion::getOneVReg() const { // 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,12 +126,9 @@ bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { // 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) { @@ -160,14 +157,14 @@ collectInterferingVRegs(unsigned MaxInterferingRegs) { 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(); } } @@ -188,7 +185,7 @@ collectInterferingVRegs(unsigned MaxInterferingRegs) { 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 index 4c0172a..a69aa65 100644 --- a/llvm/lib/CodeGen/LiveRegMatrix.cpp +++ b/llvm/lib/CodeGen/LiveRegMatrix.cpp @@ -216,21 +216,7 @@ bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End, // Check for interference with that segment for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { - // 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()) + if (query(LR, *Units).checkInterference()) return true; } return false; diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp index f56b5ed..d98a3c1 100644 --- a/llvm/lib/CodeGen/RegAllocGreedy.cpp +++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp @@ -471,13 +471,12 @@ private: bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const; bool canEvictInterference(LiveInterval &, MCRegister, bool, EvictionCost &, const SmallVirtRegSet &) const; - bool canEvictInterferenceInRange(const LiveInterval &VirtReg, - MCRegister PhysReg, SlotIndex Start, - SlotIndex End, EvictionCost &MaxCost) const; + bool canEvictInterferenceInRange(LiveInterval &VirtReg, MCRegister PhysReg, + SlotIndex Start, SlotIndex End, + EvictionCost &MaxCost) const; MCRegister getCheapestEvicteeWeight(const AllocationOrder &Order, - const LiveInterval &VirtReg, - SlotIndex Start, SlotIndex End, - float *BestEvictWeight) const; + LiveInterval &VirtReg, SlotIndex Start, + SlotIndex End, float *BestEvictWeight); void evictInterference(LiveInterval &, MCRegister, SmallVectorImpl &); bool mayRecolorAllInterferences(MCRegister PhysReg, LiveInterval &VirtReg, @@ -980,7 +979,7 @@ bool RAGreedy::canEvictInterference( /// \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(const LiveInterval &VirtReg, +bool RAGreedy::canEvictInterferenceInRange(LiveInterval &VirtReg, MCRegister PhysReg, SlotIndex Start, SlotIndex End, EvictionCost &MaxCost) const { @@ -988,7 +987,6 @@ bool RAGreedy::canEvictInterferenceInRange(const LiveInterval &VirtReg, 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())) { @@ -1033,9 +1031,9 @@ bool RAGreedy::canEvictInterferenceInRange(const LiveInterval &VirtReg, /// \return The PhysReg which is the best candidate for eviction and the /// eviction cost in BestEvictweight MCRegister RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order, - const LiveInterval &VirtReg, + LiveInterval &VirtReg, SlotIndex Start, SlotIndex End, - float *BestEvictweight) const { + float *BestEvictweight) { EvictionCost BestEvictCost; BestEvictCost.setMax(); BestEvictCost.MaxWeight = VirtReg.weight(); @@ -1060,7 +1058,7 @@ MCRegister RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order, /// returned true. void RAGreedy::evictInterference(LiveInterval &VirtReg, MCRegister PhysReg, SmallVectorImpl &NewVRegs) { - // Make sure th5at VirtReg has a cascade number, and assign that cascade + // 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; @@ -1558,9 +1556,25 @@ bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit, 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. + // 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. return true; } -- 2.7.4