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

5 files changed, 73 insertions, 6 deletions

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 86652f5673..3f7a4c7d89 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 <typename MapA, typename MapB>
 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 7e6bec639c..730b729dba 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<SlotIndex, unsigned, 4> RangeMap;
-  typedef RangeMap::Allocator Allocator;
 
+public:
+  typedef IntervalMap<SlotIndex, unsigned, 4> 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 079468a4f0..7ebe96f066 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<LiveIntervalUnion::Map, MachineLoopRange::Map>
+    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 d8dcbda8d3..ff23cf61a3 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 9af49b04ab..9ee6c5bd12 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() << ')';
 }