1 files changed, 34 insertions, 18 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index ce9845ee1673a..9b8b91c9b80e2 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -27,6 +27,7 @@
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <climits>
+#include <set>
 
 namespace llvm {
   class CoalescerPair;
@@ -194,6 +195,12 @@ namespace llvm {
     Segments segments;   // the liveness segments
     VNInfoList valnos;   // value#'s
 
+    // The segment set is used temporarily to accelerate initial computation
+    // of live ranges of physical registers in computeRegUnitRange.
+    // After that the set is flushed to the segment vector and deleted.
+    typedef std::set<Segment> SegmentSet;
+    std::unique_ptr<SegmentSet> segmentSet;
+
     typedef Segments::iterator iterator;
     iterator begin() { return segments.begin(); }
     iterator end()   { return segments.end(); }
@@ -211,12 +218,16 @@ namespace llvm {
     const_vni_iterator vni_end() const   { return valnos.end(); }
 
     /// Constructs a new LiveRange object.
-    LiveRange() {
-    }
+    LiveRange(bool UseSegmentSet = false)
+        : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>()
+                                   : nullptr) {}
 
     /// Constructs a new LiveRange object by copying segments and valnos from
     /// another LiveRange.
     LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) {
+      assert(Other.segmentSet == nullptr &&
+             "Copying of LiveRanges with active SegmentSets is not supported");
+
       // Duplicate valnos.
       for (const VNInfo *VNI : Other.valnos) {
         createValueCopy(VNI, Allocator);
@@ -437,14 +448,12 @@ namespace llvm {
     /// Add the specified Segment to this range, merging segments as
     /// appropriate.  This returns an iterator to the inserted segment (which
     /// may have grown since it was inserted).
-    iterator addSegment(Segment S) {
-      return addSegmentFrom(S, segments.begin());
-    }
+    iterator addSegment(Segment S);
 
-    /// extendInBlock - If this range is live before Kill in the basic block
-    /// that starts at StartIdx, extend it to be live up to Kill, and return
-    /// the value. If there is no segment before Kill, return NULL.
-    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill);
+    /// If this range is live before @p Use in the basic block that starts at
+    /// @p StartIdx, extend it to be live up to @p Use, and return the value. If
+    /// there is no segment before @p Use, return nullptr.
+    VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use);
 
     /// join - Join two live ranges (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS ranges as specified.  If
@@ -540,6 +549,12 @@ namespace llvm {
       return thisIndex < otherIndex;
     }
 
+    /// Flush segment set into the regular segment vector.
+    /// The method is to be called after the live range
+    /// has been created, if use of the segment set was
+    /// activated in the constructor of the live range.
+    void flushSegmentSet();
+
     void print(raw_ostream &OS) const;
     void dump() const;
 
@@ -557,10 +572,8 @@ namespace llvm {
     void append(const LiveRange::Segment S);
 
   private:
-
-    iterator addSegmentFrom(Segment S, iterator From);
-    void extendSegmentEndTo(iterator I, SlotIndex NewEnd);
-    iterator extendSegmentStartTo(iterator I, SlotIndex NewStr);
+    friend class LiveRangeUpdater;
+    void addSegmentToSet(Segment S);
     void markValNoForDeletion(VNInfo *V);
 
   };
@@ -606,6 +619,10 @@ namespace llvm {
     LiveInterval(unsigned Reg, float Weight)
       : SubRanges(nullptr), reg(Reg), weight(Weight) {}
 
+    ~LiveInterval() {
+      clearSubRanges();
+    }
+
     template<typename T>
     class SingleLinkedListIterator {
       T *P;
@@ -681,9 +698,7 @@ namespace llvm {
     }
 
     /// Removes all subregister liveness information.
-    void clearSubRanges() {
-      SubRanges = nullptr;
-    }
+    void clearSubRanges();
 
     /// Removes all subranges without any segments (subranges without segments
     /// are not considered valid and should only exist temporarily).
@@ -726,13 +741,14 @@ namespace llvm {
 #endif
 
   private:
-    LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION;
-
     /// Appends @p Range to SubRanges list.
     void appendSubRange(SubRange *Range) {
       Range->Next = SubRanges;
       SubRanges = Range;
     }
+
+    /// Free memory held by SubRange.
+    void freeSubRange(SubRange *S);
   };
 
   inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) {