LiveIntervals: add LiveRange::findIndexesLiveAt function - return a list of SlotIndexes the LiveRange live at.

[vpykhtin]

Summary

Returns an array of indexes the LiveRange is live at.

R is a range of ascending sorted random access iterators to the input SlotIndexes.

Complexity is proportional to O(segments.size * lg(R)) due to a binary search used.

[arsenm]

include/llvm/CodeGen/LiveInterval.h

612–613 ↗

(On Diff #201287)

Probably should use a SmallVectorImpl out argument

616–618 ↗

(On Diff #201287)

Aren't the segment sorted already, so you should be able to restrict the search bounds?

[vpykhtin]

include/llvm/CodeGen/LiveInterval.h

612–613 ↗

(On Diff #201287)

I used std::vector to be able to search again: it can be used for example to search from subranges after a search in the main range. I'm not sure SmallVector has compatible random access iterators with std::upper/lower_bound. I also dislike that every access to SmallVector requires a check whether it is allocated or not.

BTW I just realized that I want resulting array to be ascending sorted for that reason and it is currently so by the implentation.

616–618 ↗

(On Diff #201287)

It is restricted for that reason already: upper bound starts from Lower and next iteration starts from Upper.

[arsenm]

include/llvm/CodeGen/LiveInterval.h

612–613 ↗

(On Diff #201287)

All of the STL iterator functions should work

[vpykhtin]

• replaced output std::vector with template output iterator, return bool on found
• added is_sorted assert
• improved description

[vpykhtin]

this implementation contains bug with upper segment boundary and misses opportunity to search on sorted segments too, fixing.

[vpykhtin]

• fixed bug when an index was considered in-segment at the segment's end in some cases (lower_bound used instead of upper)
• added fast (binary search) skip for non-containing segments
• improved variable naming

[qcolombet]

What is the use case for this?

[vpykhtin]

Hi, this is the parent revision for the https://reviews.llvm.org/D62401.

Briefly AMDGPU backend needs live-in/live-out virtual register sets to calculate register pressure for the beginning/ending of every basic block on scheduling. For the large number of BBs this takes minutes. This patch makes it times faster.

[vpykhtin]

ping

[rampitec]

LGTM

llvm/trunk/include/llvm/CodeGen/LiveInterval.h

public:
     }
 
     /// 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();
 
+    /// Stores indexes from the input index sequence R at which this LiveRange
+    /// is live to the output O iterator.
+    /// R is a range of _ascending sorted_ _random_ access iterators
+    /// to the input indexes. Indexes stored at O are ascending sorted so it
+    /// can be used directly in the subsequent search (for example for
+    /// subranges). Returns true if found at least one index.
+    template <typename Range, typename OutputIt>
+    bool findIndexesLiveAt(Range &&R, OutputIt O) const {
+      assert(std::is_sorted(R.begin(), R.end()));
+      auto Idx = R.begin(), EndIdx = R.end();
+      auto Seg = segments.begin(), EndSeg = segments.end();
+      bool Found = false;
+      while (Idx != EndIdx && Seg != EndSeg) {
+        // if the Seg is lower find first segment that is above Idx using binary
+        // search
+        if (Seg->end <= *Idx) {
+          Seg = std::upper_bound(++Seg, EndSeg, *Idx,
+            [=](typename std::remove_reference<decltype(*Idx)>::type V,
+                const typename std::remove_reference<decltype(*Seg)>::type &S) {
+              return V < S.end;
+            });
+          if (Seg == EndSeg)
+            break;
+        }
+        auto NotLessStart = std::lower_bound(Idx, EndIdx, Seg->start);
+        if (NotLessStart == EndIdx)
+          break;
+        auto NotLessEnd = std::lower_bound(NotLessStart, EndIdx, Seg->end);
+        if (NotLessEnd != NotLessStart) {
+          Found = true;
+          O = std::copy(NotLessStart, NotLessEnd, O);
+        }
+        Idx = NotLessEnd;
+        ++Seg;
+      }
+      return Found;
+    }
+
     void print(raw_ostream &OS) const;
     void dump() const;
 
     /// Walk the range and assert if any invariants fail to hold.
     ///
     /// Note that this is a no-op when asserts are disabled.
 #ifdef NDEBUG
     void verify() const {}