ranger: Optimise irange_union
authorRichard Sandiford <richard.sandiford@arm.com>
Mon, 6 Dec 2021 18:29:30 +0000 (18:29 +0000)
committerRichard Sandiford <richard.sandiford@arm.com>
Mon, 6 Dec 2021 18:29:30 +0000 (18:29 +0000)
commitd27b7e69872b34890077e3dff291b4bcbc52e4cd
tree702b9a2a1b93e6efa6a83ebe07dc9e7c9d3526f9
parent14dc5b71d7e845be4ac21b16e849d6689df81b67
ranger: Optimise irange_union

When compiling an optabs.ii at -O2 with a release-checking build,
the hottest function in the profile was irange_union.  This patch
tries to optimise it a bit.  The specific changes are:

- Use quick_push rather than safe_push, since the final number
  of entries is known in advance.

- Avoid assigning wi::to_wide & co. to a temporary wide_int,
  such as in:

    wide_int val_j = wi::to_wide (res[j]);

  wi::to_wide returns a wide_int "view" of the in-place INTEGER_CST
  storage.  Assigning the result to wide_int forces an unnecessary
  copy to temporary storage.

  This is one area where "auto" helps a lot.  In the end though,
  it seemed more readable to inline the wi::to_*s rather than
  use auto.

- Use to_widest_int rather than to_wide_int.  Both are functionally
  correct, but to_widest_int is more efficient, for three reasons:

  - to_wide returns a wide-int representation in which the most
    significant element might not be canonically sign-extended.
    This is because we want to allow the storage of an INTEGER_CST
    like 0x1U << 31 to be accessed directly with both a wide_int view
    (where only 32 bits matter) and a widest_int view (where many more
    bits matter, and where the 32 bits are zero-extended to match the
    unsigned type).  However, operating on uncanonicalised wide_int
    forms is less efficient than operating on canonicalised forms.

  - to_widest_int has a constant rather than variable precision and
    there are never any redundant upper bits to worry about.

  - Using widest_int avoids the need for an overflow check, since
    there is enough precision to add 1 to any IL constant without
    wrap-around.

This gives a ~2% compile-time speed up with the test above.

I also tried adding a path for two single-pair ranges, but it
wasn't a win.

gcc/
* value-range.cc (irange::irange_union): Use quick_push rather
than safe_push.  Use widest_int rather than wide_int.  Avoid
assigning wi::to_* results to wide*_int temporaries.
gcc/value-range.cc