Delete the top-down "Latency" scheduler. Top-down scheduling doesn't handle

[oota-llvm.git] / include / llvm / ADT / IntervalMap.h

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index ae79e845088d3e0d1f6d944b34c789a36374863f..1230e8f5fb43641d8e0f6f77fba0dba35e0ee2df 100644 (file)
--- 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:
@@ -1326,9 +1328,16 @@ public:
   /// const_iterator - Create an iterator that isn't pointing anywhere.
   const_iterator() : map(0) {}
 
+  /// setMap - Change the map iterated over. This call must be followed by a
+  /// call to goToBegin(), goToEnd(), or find()
+  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
+
   /// valid - Return true if the current position is valid, false for end().
   bool valid() const { return path.valid(); }
 
+  /// atBegin - Return true if the current position is the first map entry.
+  bool atBegin() const { return path.atBegin(); }
+
   /// start - Return the beginning of the current interval.
   const KeyT &start() const { return unsafeStart(); }
 
@@ -1409,6 +1418,8 @@ public:
   /// The search is started from the current position, and no earlier positions
   /// can be found. This is much faster than find() for small moves.
   void advanceTo(KeyT x) {
+    if (!valid())
+      return;
     if (branched())
       treeAdvanceTo(x);
     else
@@ -2025,6 +2036,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;
@@ -2033,14 +2045,31 @@ class IntervalMapOverlaps {
   /// either meets end.
   /// Don't move the iterators if they are already overlapping.
   void advance() {
+    if (!valid())
+      return;
+
+    if (Traits::stopLess(posA.stop(), posB.start())) {
+      // A ends before B begins. Catch up.
+      posA.advanceTo(posB.start());
+      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
+        return;
+    } else if (Traits::stopLess(posB.stop(), posA.start())) {
+      // B ends before A begins. Catch up.
+      posB.advanceTo(posA.start());
+      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
+        return;
+    } else
+      // Already overlapping.
+      return;
+
     for (;;) {
       // Make a.end > b.start.
       posA.advanceTo(posB.start());
-      if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start()))
+      if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
         return;
       // Make b.end > a.start.
       posB.advanceTo(posA.start());
-      if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
+      if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
         return;
     }
   }
@@ -2049,10 +2078,7 @@ public:
   /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
   IntervalMapOverlaps(const MapA &a, const MapB &b)
     : posA(b.empty() ? a.end() : a.find(b.start())),
-      posB(posA.valid() ? b.find(posA.start()) : b.end()) {
-    if (valid())
-      advance();
-  }
+      posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }
 
   /// valid - Return true if iterator is at an overlap.
   bool valid() const {
@@ -2065,37 +2091,55 @@ 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 overlapping 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;
-    if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start()))
-      return;
-    // Second half-loop of advance().
-    posB.advanceTo(posA.start());
-    if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
-      return ;
     advance();
   }
 
   /// skipB - Move to the next overlap that doesn't involve b().
   void skipB() {
     ++posB;
-    if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
-        return;
     advance();
   }
 
   /// Preincrement - Move to the next overlap.
   IntervalMapOverlaps &operator++() {
     // Bump the iterator that ends first. The other one may have more overlaps.
-    if (Traits::startLess(posB.end(), posA.end()))
+    if (Traits::startLess(posB.stop(), posA.stop()))
       skipB();
     else
       skipA();
     return *this;
   }
-};
 
+  /// advanceTo - Move to the first overlapping interval with
+  /// stopLess(x, stop()).
+  void advanceTo(KeyType x) {
+    if (!valid())
+      return;
+    // Make sure advanceTo sees monotonic keys.
+    if (Traits::stopLess(posA.stop(), x))
+      posA.advanceTo(x);
+    if (Traits::stopLess(posB.stop(), x))
+      posB.advanceTo(x);
+    advance();
+  }
+};
 
 } // namespace llvm