Page MenuHomePhabricator

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

Authored by vpykhtin on May 24 2019, 10:52 AM.



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.

Diff Detail


Event Timeline

vpykhtin created this revision.May 24 2019, 10:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 24 2019, 10:52 AM
arsenm added a subscriber: arsenm.May 24 2019, 10:56 AM
arsenm added inline comments.
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 marked 2 inline comments as done.May 24 2019, 11:22 AM
vpykhtin added inline comments.
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 added inline comments.May 24 2019, 11:28 AM
612–613 ↗(On Diff #201287)

All of the STL iterator functions should work

vpykhtin updated this revision to Diff 201537.May 27 2019, 8:58 AM
  • replaced output std::vector with template output iterator, return bool on found
  • added is_sorted assert
  • improved description

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

vpykhtin updated this revision to Diff 201974.May 29 2019, 10:26 AM
  • 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

What is the use case for this?

Hi, this is the parent revision for the

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.

This revision is now accepted and ready to land.Jun 12 2019, 8:11 AM
This revision was automatically updated to reflect the committed changes.