Upcoming removal of legacy ranges and conversion to wide_ints.

Upcoming removal of legacy ranges and conversion to wide_ints.

[Aldy Hernandez]

After GCC 13 is released we will remove legacy range support from the
compiler, and convert irange's to wide_ints.  I want to give everyone
a heads up, to help understand what's involved and what the end result is.

Legacy ranges are basically the value_range type (int_range<1>) where
the internal representation has anti-ranges and allows symbolics, etc.
It is a holdout from the old VRP, and was left in place because it was
pervasive and too risky remove late in the GCC 13 cycle.

There will be lots of patches (about 30), mostly because legacy
touches a lot, and also because it was necessary to rip out things in
order to double check the work.  Furthermore, having small pieces
makes it easier to bisect any possible regressions.

I will give a bird's eye view of what follows with details in the
patches themselves.

First the good news.  VRP improves by 13.22%, jump threading by 11.6%
and overall compilation improves by 1.5%.  Andrew has some
improvements to the cache that should provide significant additional
speedups.

Here are the main parts of the work:

1. Converting users of the old API to the new irange API.

    There are a few holdouts, most notably the middle end warnings,
    some of which have strong dependencies on VR_ANTI_RANGE and the old
    API.  I have provided a transitional function (get_legacy_range)
    which translates an irange to whatever min/max/kind concoction they
    rely on.  I have no plans for converting these passes, as I don't
    understand the code well enough to fix it.  Naive attempts broke
    the tests, even though conceptually the changes were correct.  At
    least the damage will be limited to users of one function:
    get_legacy_range().

    The IPA passes also use the old API, but I have plans (and patches)
    for revamping all of the IPA ranges.  Details below.

2. Repurposing int_range<1> to its obvious meaning (a range with two
    endpoints).  This will reduce the memory footprint for small
    ranges.

3. Overhauling the vrange storage mechanism used for global ranges
    (SSA_NAME_RANGE_INFO) so it can be shared with the ranger cache.

    The reason for this is because the ranger cache used a tree range
    allocator, which didn't exactly scale to the eventual conversion to
    wide ints.  It also allows us to use one lean and efficient
    allocator for everything instead of two incomplete implementations.

    The storage remains slim (no trees, plus a trailing_wide_int like
    implementation).  The storage is also quite fast, since without
    legacy or trees, we can copy host integers arrays back and forth
    between the storage and the wide_ints.

4. Conversion of trees to wide ints in irange.

5. Various performance optimizations now possible because we have
    moved away from both legacy and trees.

A few notes.

The value_range typedef has been renamed to int_range<2>, since
int_range<1> now means two endpoints which can't represent the inverse
of a range (say not-zero) for anything but a handful of ranges.  The
(future) plan is to mechanically convert the definitions to
int_range<2> and finally rename Value_Range (the type agnostic range
class) to value_range for use in passes that must work in a variety of
different types (floats, integers, etc).

IPA has been rolling their own ranges forever.  They use a combination
of the legacy API along with handcrafted pairs of wide_ints (ipa_vr).
The passes must be divorced of its legacy dependency, and cleaned up a
bit.  IPA is also very tied to integers and pointers, and I see no
reason why we can't keep track of float arguments, etc.

I am sitting on a lot of additional patches to do 90% of the
conversion, but need to consult with the IPA experts on various issues
before proceeding (for instance, the lifetime of various structures).
Among these patches are generic vrange LTO streaming functions and
vrange hashing.  I think it's time we make vrange a first class
citizen for LTO/hashing and a few other things folks were doing in an
ad-hoc manner.  This should alleviate the maintenance burden on the
IPA maintainers going forward.  Note, that the IPA work is a
follow-up, and only after careful consultation with the relevant
maintainers.

In addition to the IPA/LTO work described above, future work this
cycle will include converting irange to the value/mask mechanism we
use elsewhere in the compiler (CCP, etc).  With wide ints in place, this 
should be relatively straightforward, plus it will give us additional
optimization opportunities in the ranger ecosystem.

Comments welcome.

Aldy and Andrew

Re: Upcoming removal of legacy ranges and conversion to wide_ints.

[Martin Jambor]

Hi,

On Tue, Apr 25 2023, Aldy Hernandez via Gcc wrote:
> After GCC 13 is released we will remove legacy range support from the
> compiler, and convert irange's to wide_ints.  I want to give everyone
> a heads up, to help understand what's involved and what the end result is.
>

[...]

>
> 1. Converting users of the old API to the new irange API.
>

[...]

>
>     The IPA passes also use the old API, but I have plans (and patches)
>     for revamping all of the IPA ranges.  Details below.

Thanks a lot for taking care of this.

[..]

> IPA has been rolling their own ranges forever.  They use a combination
> of the legacy API along with handcrafted pairs of wide_ints (ipa_vr).
> The passes must be divorced of its legacy dependency, and cleaned up a
> bit.  IPA is also very tied to integers and pointers, and I see no
> reason why we can't keep track of float arguments, etc.

Agreed.

>
> I am sitting on a lot of additional patches to do 90% of the
> conversion, but need to consult with the IPA experts on various issues
> before proceeding (for instance, the lifetime of various structures).
> Among these patches are generic vrange LTO streaming functions and
> vrange hashing.  I think it's time we make vrange a first class
> citizen for LTO/hashing and a few other things folks were doing in an
> ad-hoc manner.  This should alleviate the maintenance burden on the
> IPA maintainers going forward.  Note, that the IPA work is a
> follow-up, and only after careful consultation with the relevant
> maintainers.

I need to get up to speed when it comes to the new representation and
new API but I'll be happy to help.

Martin