From ff2e9b4225ab55ee049b33158a9cce1ef138c2f7 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Fri, 17 Dec 2010 04:09:47 +0000 Subject: [PATCH] Provide LiveIntervalUnion::Query::checkLoopInterference. This is a three-way interval list intersection between a virtual register, a live interval union, and a loop. It will be used to identify interference-free loops for live range splitting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122034 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/IntervalMap.h | 26 +++++++++++++++++++++++++- include/llvm/CodeGen/MachineLoopRanges.h | 12 +++++++++--- lib/CodeGen/LiveIntervalUnion.cpp | 28 ++++++++++++++++++++++++++++ lib/CodeGen/LiveIntervalUnion.h | 9 +++++++++ lib/CodeGen/MachineLoopRanges.cpp | 4 ++-- 5 files changed, 73 insertions(+), 6 deletions(-) diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 86652f5673a..3f7a4c7d894 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -940,6 +940,8 @@ class IntervalMap { public: typedef typename Sizer::Allocator Allocator; + typedef KeyT KeyType; + typedef ValT ValueType; typedef Traits KeyTraits; private: @@ -2025,6 +2027,7 @@ iterator::overflow(unsigned Level) { /// template class IntervalMapOverlaps { + typedef typename MapA::KeyType KeyType; typedef typename MapA::KeyTraits Traits; typename MapA::const_iterator posA; typename MapB::const_iterator posB; @@ -2065,6 +2068,20 @@ public: /// b - access the right hand side in the overlap. const typename MapB::const_iterator &b() const { return posB; } + /// start - Beginning of the overlapping interval. + KeyType start() const { + KeyType ak = a().start(); + KeyType bk = b().start(); + return Traits::startLess(ak, bk) ? bk : ak; + } + + /// stop - End of the overlaping interval. + KeyType stop() const { + KeyType ak = a().stop(); + KeyType bk = b().stop(); + return Traits::startLess(ak, bk) ? ak : bk; + } + /// skipA - Move to the next overlap that doesn't involve a(). void skipA() { ++posA; @@ -2094,8 +2111,15 @@ public: skipA(); return *this; } -}; + /// advanceTo - Move to the first overlapping interval with + /// stopLess(x, stop()). + void advanceTo(KeyType x) { + posA.advanceTo(x); + posB.advanceTo(x); + advance(); + } +}; } // namespace llvm diff --git a/include/llvm/CodeGen/MachineLoopRanges.h b/include/llvm/CodeGen/MachineLoopRanges.h index 7e6bec639c7..730b729dba7 100644 --- a/include/llvm/CodeGen/MachineLoopRanges.h +++ b/include/llvm/CodeGen/MachineLoopRanges.h @@ -29,15 +29,18 @@ class raw_ostream; /// MachineLoopRange - Range information for a single loop. class MachineLoopRange { friend class MachineLoopRanges; - typedef IntervalMap RangeMap; - typedef RangeMap::Allocator Allocator; +public: + typedef IntervalMap Map; + typedef Map::Allocator Allocator; + +private: /// The mapped loop. const MachineLoop *const Loop; /// Map intervals to a bit mask. /// Bit 0 = inside loop block. - RangeMap Intervals; + Map Intervals; /// Create a MachineLoopRange, only accessible to MachineLoopRanges. MachineLoopRange(const MachineLoop*, Allocator&, SlotIndexes&); @@ -47,6 +50,9 @@ public: /// inteructions. bool overlaps(SlotIndex Start, SlotIndex Stop); + /// getMap - Allow public read-only access for IntervalMapOverlaps. + const Map &getMap() { return Intervals; } + /// print - Print loop ranges on OS. void print(raw_ostream&) const; }; diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp index 079468a4f03..7ebe96f0660 100644 --- a/lib/CodeGen/LiveIntervalUnion.cpp +++ b/lib/CodeGen/LiveIntervalUnion.cpp @@ -16,6 +16,7 @@ #define DEBUG_TYPE "regalloc" #include "LiveIntervalUnion.h" #include "llvm/ADT/SparseBitVector.h" +#include "llvm/CodeGen/MachineLoopRanges.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -284,3 +285,30 @@ collectInterferingVRegs(unsigned MaxInterferingRegs) { SeenAllInterferences = true; return InterferingVRegs.size(); } + +bool LiveIntervalUnion::Query::checkLoopInterference(MachineLoopRange *Loop) { + // VirtReg is likely live throughout the loop, so start by checking LIU-Loop + // overlaps. + IntervalMapOverlaps + Overlaps(LiveUnion->getMap(), Loop->getMap()); + if (!Overlaps.valid()) + return false; + + // The loop is overlapping an LIU assignment. Check VirtReg as well. + LiveInterval::iterator VRI = VirtReg->find(Overlaps.start()); + + for (;;) { + if (VRI == VirtReg->end()) + return false; + if (VRI->start < Overlaps.stop()) + return true; + + Overlaps.advanceTo(VRI->start); + if (!Overlaps.valid()) + return false; + if (Overlaps.start() < VRI->end) + return true; + + VRI = VirtReg->advanceTo(VRI, Overlaps.start()); + } +} diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h index d8dcbda8d34..ff23cf61a33 100644 --- a/lib/CodeGen/LiveIntervalUnion.h +++ b/lib/CodeGen/LiveIntervalUnion.h @@ -24,6 +24,7 @@ namespace llvm { +class MachineLoopRange; class TargetRegisterInfo; #ifndef NDEBUG @@ -76,6 +77,10 @@ public: bool empty() const { return Segments.empty(); } SlotIndex startIndex() const { return Segments.start(); } + // Provide public access to the underlying map to allow overlap iteration. + typedef LiveSegments Map; + const Map &getMap() { return Segments; } + // Add a live virtual register to this union and merge its segments. void unify(LiveInterval &VirtReg); @@ -223,6 +228,10 @@ public: return InterferingVRegs; } + /// checkLoopInterference - Return true if there is interference overlapping + /// Loop. + bool checkLoopInterference(MachineLoopRange*); + void print(raw_ostream &OS, const TargetRegisterInfo *TRI); private: Query(const Query&); // DO NOT IMPLEMENT diff --git a/lib/CodeGen/MachineLoopRanges.cpp b/lib/CodeGen/MachineLoopRanges.cpp index 9af49b04ab0..9ee6c5bd125 100644 --- a/lib/CodeGen/MachineLoopRanges.cpp +++ b/lib/CodeGen/MachineLoopRanges.cpp @@ -69,13 +69,13 @@ MachineLoopRange::MachineLoopRange(const MachineLoop *loop, /// overlaps - Return true if this loop overlaps the given range of machine /// instructions. bool MachineLoopRange::overlaps(SlotIndex Start, SlotIndex Stop) { - RangeMap::const_iterator I = Intervals.find(Start); + Map::const_iterator I = Intervals.find(Start); return I.valid() && Stop > I.start(); } void MachineLoopRange::print(raw_ostream &OS) const { OS << "Loop#" << Loop->getHeader()->getNumber() << " ="; - for (RangeMap::const_iterator I = Intervals.begin(); I.valid(); ++I) + for (Map::const_iterator I = Intervals.begin(); I.valid(); ++I) OS << " [" << I.start() << ';' << I.stop() << ')'; } -- 2.11.0