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

Probably should use a SmallVectorImpl out argument

616–618

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

[vpykhtin]

include/llvm/CodeGen/LiveInterval.h

612–613

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

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

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

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();
 
+    /// Returns an array of indexes this LiveRange is live at.
+    /// R is a range of _ascending sorted_ _random_ access iterators
+    /// to the input indexes
+    template <typename Range>
+    std::vector<SlotIndex> findIndexesLiveAt(Range &&R) const {
+      std::vector<SlotIndex> IndexesLiveAt;
+      auto I = R.begin(), E = R.end();
+      for (auto &S : segments) {
+        auto Lower = std::lower_bound(I, E, S.start);
+        if (Lower == E)
+          break;
+        auto Upper = std::upper_bound(Lower, E, S.end);
+        IndexesLiveAt.insert(IndexesLiveAt.end(), Lower, Upper);
+        if (Upper == E)
+          break;
+        I = Upper;
+      }
+      return IndexesLiveAt;
+    }
+
     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 {}