Change addRange and join to be a little bit smarter. In particular, we don't

want to insert a new range into the middle of the vector, then delete ranges
one at a time next to the inserted one as they are merged.

Instead, if the inserted interval overlaps, just start merging.  The only time
we insert into the middle of the vector is when we don't overlap at all.  Also
delete blocks of live ranges if we overlap with many of them.

This patch speeds up joining by .7 seconds on a large testcase, but more
importantly gets all of the range adding code into addRangeFrom.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15141 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 9 insertions, 3 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 7d4c23b2c8..8f6a3487ac 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -97,7 +97,12 @@ namespace llvm {
 
     bool overlaps(const LiveInterval& other) const;
 
-    void addRange(LiveRange R);
+    /// addRange - Add the specified LiveRange to this interval, merging
+    /// intervals as appropriate.  This returns an iterator to the inserted live
+    /// range (which may have grown since it was inserted.
+    void addRange(LiveRange LR) {
+      addRangeFrom(LR, ranges.begin());
+    }
 
     void join(const LiveInterval& other);
 
@@ -110,8 +115,9 @@ namespace llvm {
     }
 
   private:
-    Ranges::iterator mergeRangesForward(Ranges::iterator it);
-    Ranges::iterator mergeRangesBackward(Ranges::iterator it);
+    Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
+    void extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd);
+    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, unsigned NewStr);
   };
 
   std::ostream& operator<<(std::ostream& os, const LiveInterval& li);