[RFC] > WIDE_INT_MAX_PREC support in wide-int

  Hi!

While the _BitInt series isn't committed yet, I had a quick look at
lifting the current lowest limitation on maximum _BitInt precision,
that wide_int can only support wide_int until WIDE_INT_MAX_PRECISION - 1.

Note, other limits if that is lifted are INTEGER_CST currently using 3
unsigned char members and so being able to only hold up to 255 * 64 = 16320
bit numbers and then TYPE_PRECISION being 16-bit, so limiting us to 65535
bits.  The INTEGER_CST limit could be dealt with by dropping the
int_length.offset "cache" and making int_length.extended and
int_length.unextended members unsinged short rather than unsigned char.

The following so far just compile tested patch changes wide_int_storage
to be a union, for precisions up to WIDE_INT_MAX_PRECISION inclusive it
will work as before (just being no longer trivially copyable type and
having an inline destructor), while larger precision instead use a pointer
to heap allocated array.
For wide_int this is fairly easy (of course, I'd need to see what the
patch does to gcc code size and compile time performance, some
growth/slowdown is certain), but I'd like to brainstorm on
widest_int/widest2_int.

Currently it is a constant precision storage with WIDE_INT_MAX_PRECISION
precision (widest2_int twice that), so memory layout-wide on at least 64-bit
hosts identical to wide_int, just it doesn't have precision member and so
32 bits smaller on 32-bit hosts.  It is used in lots of places.

I think the most common is what is done e.g. in tree_int_cst* comparisons
and similarly, using wi::to_widest () to just compare INTEGER_CSTs.
That case actually doesn't even use wide_int but widest_extended_tree
as storage, unless stored into widest_int in between (that happens in
various spots as well).  For comparisons, it would be fine if
widest_int_storage/widest_extended_tree storages had a dynamic precision,
WIDE_INT_MAX_PRECISION for most of the cases (if only
precision < WIDE_INT_MAX_PRECISION is involved), otherwise the needed
precision (e.g. for binary ops) which would be what we say have in
INTEGER_CST or some type, rounded up to whole multiples of HOST_WIDE_INTs
and if unsigned with multiple of HOST_WIDE_INT precision, have another
HWI to make it always sign-extended.

Another common case is how e.g. tree-ssa-ccp.cc uses them, that is mostly
for bitwise ops and so I think the above would be just fine for that case.

Another case is how tree-ssa-loop-niter.cc uses it, I think for such a usage
it really wants something widest, perhaps we could just try to punt for
_BitInt(N) for N >= WIDE_INT_MAX_PRECISION in there, so that we never care
about bits beyond that limit?

Some passes only use widest_int after the bitint lowering spot, we don't
really need to care about those.

I think another possibility could be to make widest_int_storage etc. always
pretend it has 65536 bit precision or something similarly large and make the
decision on whether inline array or pointer is used in the storage be done
using len.  Unfortunately, set_len method is usually called after filling
the array, not before it (it even sign-extends some cases, so it has to be
done that late).

Or for e.g. binary ops compute widest_int precision based on the 2 (for
binary) or 1 (for unary) operand's .len involved?

Thoughts on this?

Note, the wide-int.cc change is just to show it does something, it would be
a waste to put that into self-test when _BitInt can support such sizes.

2023-08-28  Jakub Jelinek  <jakub@redhat.com>

	* wide-int.h (wide_int_storage): Replace val member with a union of
	val and valp.  Declare destructor.
	(wide_int_storage::wide_int_storage): Initialize precision to 0
	in default ctor.  Allocate u.valp if needed in copy ctor.
	(wide_int_storage::~wide_int_storage): New.
	(wide_int_storage::operator =): Delete and/or allocate u.valp if
	needed.
	(wide_int_storage::get_val, wide_int_storage::write_val): Return
	u.valp for precision > WIDE_INT_MAX_PRECISION, otherwise u.val.
	(wide_int_storage::set_len): Use write_val instead of accessing
	val directly.
	(wide_int_storage::create): Allocate u.valp if needed.
	* value-range.h (irange::maybe_resize): Use a loop instead of
	memcpy.
	* wide-int.cc (wide_int_cc_tests): Add a test for 4096 bit wide_int
	addition.


	Jakub
  

On Mon, 28 Aug 2023, Jakub Jelinek wrote:

> Hi!
> 
> While the _BitInt series isn't committed yet, I had a quick look at
> lifting the current lowest limitation on maximum _BitInt precision,
> that wide_int can only support wide_int until WIDE_INT_MAX_PRECISION - 1.
> 
> Note, other limits if that is lifted are INTEGER_CST currently using 3
> unsigned char members and so being able to only hold up to 255 * 64 = 16320
> bit numbers and then TYPE_PRECISION being 16-bit, so limiting us to 65535
> bits.  The INTEGER_CST limit could be dealt with by dropping the
> int_length.offset "cache" and making int_length.extended and
> int_length.unextended members unsinged short rather than unsigned char.
> 
> The following so far just compile tested patch changes wide_int_storage
> to be a union, for precisions up to WIDE_INT_MAX_PRECISION inclusive it
> will work as before (just being no longer trivially copyable type and
> having an inline destructor), while larger precision instead use a pointer
> to heap allocated array.
> For wide_int this is fairly easy (of course, I'd need to see what the
> patch does to gcc code size and compile time performance, some
> growth/slowdown is certain), but I'd like to brainstorm on
> widest_int/widest2_int.
> 
> Currently it is a constant precision storage with WIDE_INT_MAX_PRECISION
> precision (widest2_int twice that), so memory layout-wide on at least 64-bit
> hosts identical to wide_int, just it doesn't have precision member and so
> 32 bits smaller on 32-bit hosts.  It is used in lots of places.
> 
> I think the most common is what is done e.g. in tree_int_cst* comparisons
> and similarly, using wi::to_widest () to just compare INTEGER_CSTs.
> That case actually doesn't even use wide_int but widest_extended_tree
> as storage, unless stored into widest_int in between (that happens in
> various spots as well).  For comparisons, it would be fine if
> widest_int_storage/widest_extended_tree storages had a dynamic precision,
> WIDE_INT_MAX_PRECISION for most of the cases (if only
> precision < WIDE_INT_MAX_PRECISION is involved), otherwise the needed
> precision (e.g. for binary ops) which would be what we say have in
> INTEGER_CST or some type, rounded up to whole multiples of HOST_WIDE_INTs
> and if unsigned with multiple of HOST_WIDE_INT precision, have another
> HWI to make it always sign-extended.
> 
> Another common case is how e.g. tree-ssa-ccp.cc uses them, that is mostly
> for bitwise ops and so I think the above would be just fine for that case.
> 
> Another case is how tree-ssa-loop-niter.cc uses it, I think for such a usage
> it really wants something widest, perhaps we could just try to punt for
> _BitInt(N) for N >= WIDE_INT_MAX_PRECISION in there, so that we never care
> about bits beyond that limit?

I'll note tree-ssa-loop-niter.cc also uses GMP in some cases, widest_int
is really trying to be poor-mans GMP by limiting the maximum precision.

> Some passes only use widest_int after the bitint lowering spot, we don't
> really need to care about those.
> 
> I think another possibility could be to make widest_int_storage etc. always
> pretend it has 65536 bit precision or something similarly large and make the
> decision on whether inline array or pointer is used in the storage be done
> using len.  Unfortunately, set_len method is usually called after filling
> the array, not before it (it even sign-extends some cases, so it has to be
> done that late).
> 
> Or for e.g. binary ops compute widest_int precision based on the 2 (for
> binary) or 1 (for unary) operand's .len involved?
> 
> Thoughts on this?

The simplest way would probably to keep widest_int at 
WIDE_INT_MAX_PRECISION like we have now and assert that this is
enough at ::to_widest time (we probably do already).  And then
declare uses with more precision need to use GMP.

Not sure if that's not also a viable way for wide_int - we're
only losing optimization here, no?

Richard.

> Note, the wide-int.cc change is just to show it does something, it would be
> a waste to put that into self-test when _BitInt can support such sizes.
> 
> 2023-08-28  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* wide-int.h (wide_int_storage): Replace val member with a union of
> 	val and valp.  Declare destructor.
> 	(wide_int_storage::wide_int_storage): Initialize precision to 0
> 	in default ctor.  Allocate u.valp if needed in copy ctor.
> 	(wide_int_storage::~wide_int_storage): New.
> 	(wide_int_storage::operator =): Delete and/or allocate u.valp if
> 	needed.
> 	(wide_int_storage::get_val, wide_int_storage::write_val): Return
> 	u.valp for precision > WIDE_INT_MAX_PRECISION, otherwise u.val.
> 	(wide_int_storage::set_len): Use write_val instead of accessing
> 	val directly.
> 	(wide_int_storage::create): Allocate u.valp if needed.
> 	* value-range.h (irange::maybe_resize): Use a loop instead of
> 	memcpy.
> 	* wide-int.cc (wide_int_cc_tests): Add a test for 4096 bit wide_int
> 	addition.
> 
> --- gcc/wide-int.h.jj	2023-06-07 09:42:14.997126190 +0200
> +++ gcc/wide-int.h	2023-08-28 15:09:06.498448770 +0200
> @@ -1065,7 +1065,11 @@ namespace wi
>  class GTY(()) wide_int_storage
>  {
>  private:
> -  HOST_WIDE_INT val[WIDE_INT_MAX_ELTS];
> +  union
> +  {
> +    HOST_WIDE_INT val[WIDE_INT_MAX_ELTS];
> +    HOST_WIDE_INT *valp;
> +  } GTY((skip)) u;
>    unsigned int len;
>    unsigned int precision;
>  
> @@ -1073,6 +1077,7 @@ public:
>    wide_int_storage ();
>    template <typename T>
>    wide_int_storage (const T &);
> +  ~wide_int_storage ();
>  
>    /* The standard generic_wide_int storage methods.  */
>    unsigned int get_precision () const;
> @@ -1104,7 +1109,7 @@ namespace wi
>    };
>  }
>  
> -inline wide_int_storage::wide_int_storage () {}
> +inline wide_int_storage::wide_int_storage () : precision (0) {}
>  
>  /* Initialize the storage from integer X, in its natural precision.
>     Note that we do not allow integers with host-dependent precision
> @@ -1117,9 +1122,17 @@ inline wide_int_storage::wide_int_storag
>    { STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION); }
>    WIDE_INT_REF_FOR (T) xi (x);
>    precision = xi.precision;
> +  if (UNLIKELY (precision > WIDE_INT_MAX_PRECISION))
> +    u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (precision, HOST_BITS_PER_WIDE_INT));
>    wi::copy (*this, xi);
>  }
>  
> +inline wide_int_storage::~wide_int_storage ()
> +{
> +  if (UNLIKELY (precision > WIDE_INT_MAX_PRECISION))
> +    XDELETEVEC (u.valp);
> +}
> +
>  template <typename T>
>  inline wide_int_storage&
>  wide_int_storage::operator = (const T &x)
> @@ -1127,7 +1140,15 @@ wide_int_storage::operator = (const T &x
>    { STATIC_ASSERT (!wi::int_traits<T>::host_dependent_precision); }
>    { STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION); }
>    WIDE_INT_REF_FOR (T) xi (x);
> -  precision = xi.precision;
> +  if (UNLIKELY (precision != xi.precision))
> +    {
> +      if (UNLIKELY (precision > WIDE_INT_MAX_PRECISION))
> +	XDELETEVEC (u.valp);
> +      precision = xi.precision;
> +      if (UNLIKELY (precision > WIDE_INT_MAX_PRECISION))
> +	u.valp = XNEWVEC (HOST_WIDE_INT,
> +			  CEIL (precision, HOST_BITS_PER_WIDE_INT));
> +    }
>    wi::copy (*this, xi);
>    return *this;
>  }
> @@ -1141,7 +1162,7 @@ wide_int_storage::get_precision () const
>  inline const HOST_WIDE_INT *
>  wide_int_storage::get_val () const
>  {
> -  return val;
> +  return UNLIKELY (precision > WIDE_INT_MAX_PRECISION) ? u.valp : u.val;
>  }
>  
>  inline unsigned int
> @@ -1153,7 +1174,7 @@ wide_int_storage::get_len () const
>  inline HOST_WIDE_INT *
>  wide_int_storage::write_val ()
>  {
> -  return val;
> +  return UNLIKELY (precision > WIDE_INT_MAX_PRECISION) ? u.valp : u.val;
>  }
>  
>  inline void
> @@ -1161,8 +1182,10 @@ wide_int_storage::set_len (unsigned int
>  {
>    len = l;
>    if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > precision)
> -    val[len - 1] = sext_hwi (val[len - 1],
> -			     precision % HOST_BITS_PER_WIDE_INT);
> +    {
> +      HOST_WIDE_INT &v = write_val ()[len - 1];
> +      v = sext_hwi (v, precision % HOST_BITS_PER_WIDE_INT);
> +    }
>  }
>  
>  /* Treat X as having signedness SGN and convert it to a PRECISION-bit
> @@ -1196,6 +1219,9 @@ wide_int_storage::create (unsigned int p
>  {
>    wide_int x;
>    x.precision = precision;
> +  if (UNLIKELY (precision > WIDE_INT_MAX_PRECISION))
> +    x.u.valp = XNEWVEC (HOST_WIDE_INT,
> +			CEIL (precision, HOST_BITS_PER_WIDE_INT));
>    return x;
>  }
>  
> --- gcc/value-range.h.jj	2023-08-08 15:55:09.619120863 +0200
> +++ gcc/value-range.h	2023-08-28 15:08:51.295648228 +0200
> @@ -624,7 +624,9 @@ irange::maybe_resize (int needed)
>      {
>        m_max_ranges = HARD_MAX_RANGES;
>        wide_int *newmem = new wide_int[m_max_ranges * 2];
> -      memcpy (newmem, m_base, sizeof (wide_int) * num_pairs () * 2);
> +      unsigned n = num_pairs () * 2;
> +      for (unsigned i = 0; i < n; ++i)
> +	newmem[i] = m_base[i];
>        m_base = newmem;
>      }
>  }
> --- gcc/wide-int.cc.jj	2023-08-08 15:55:09.621120835 +0200
> +++ gcc/wide-int.cc	2023-08-28 15:29:48.620086813 +0200
> @@ -2617,6 +2617,110 @@ wide_int_cc_tests ()
>  	     wi::shifted_mask (0, 128, false, 128));
>    ASSERT_EQ (wi::mask (128, true, 128),
>  	     wi::shifted_mask (0, 128, true, 128));
> +  const HOST_WIDE_INT a[192] = {
> +    HOST_WIDE_INT_UC (0x0b2b03862d1fbe27), HOST_WIDE_INT_UC (0x444bb6ac06835f26),
> +    HOST_WIDE_INT_UC (0x9d930632270edc17), HOST_WIDE_INT_UC (0xf9f1f7b1a4d298d3),
> +    HOST_WIDE_INT_UC (0x1f87ccdd7b021c38), HOST_WIDE_INT_UC (0xf0366f9e68bbcdb2),
> +    HOST_WIDE_INT_UC (0x2fcbfa32959408aa), HOST_WIDE_INT_UC (0xbdf7d4beb7b3dbe7),
> +    HOST_WIDE_INT_UC (0x4a64ba19bdf3363f), HOST_WIDE_INT_UC (0x145c2ec5ae314c2f),
> +    HOST_WIDE_INT_UC (0x307bf01303ca99d5), HOST_WIDE_INT_UC (0x82cac09501c0df1c),
> +    HOST_WIDE_INT_UC (0x8119188bcf59391d), HOST_WIDE_INT_UC (0xd24ac359b0510387),
> +    HOST_WIDE_INT_UC (0x1b6f9cd3e388da86), HOST_WIDE_INT_UC (0x4e2990a31337004a),
> +    HOST_WIDE_INT_UC (0xd62f16910ab640ae), HOST_WIDE_INT_UC (0xa34a6f3c87668eaa),
> +    HOST_WIDE_INT_UC (0x37e46f52b873eb07), HOST_WIDE_INT_UC (0xa498e8e255eaa65c),
> +    HOST_WIDE_INT_UC (0x2370a16cbbdaa0af), HOST_WIDE_INT_UC (0x4f305e68993df752),
> +    HOST_WIDE_INT_UC (0x074d3e131bd30499), HOST_WIDE_INT_UC (0xf4caf8393dbd01c4),
> +    HOST_WIDE_INT_UC (0xb9e6794f494b3934), HOST_WIDE_INT_UC (0x7d7b2cc51969de8e),
> +    HOST_WIDE_INT_UC (0x87494b790cce95f1), HOST_WIDE_INT_UC (0xeba990c44573c5c8),
> +    HOST_WIDE_INT_UC (0x755007ea9663d2ea), HOST_WIDE_INT_UC (0xe5afe63b489e3d19),
> +    HOST_WIDE_INT_UC (0x82138483f2c2831c), HOST_WIDE_INT_UC (0x5488d7a6d99ce301),
> +    HOST_WIDE_INT_UC (0xd1d713ee75465be7), HOST_WIDE_INT_UC (0x29222cca5699b802),
> +    HOST_WIDE_INT_UC (0x28e6308201df3eff), HOST_WIDE_INT_UC (0x720e2cef5151c53d),
> +    HOST_WIDE_INT_UC (0xac381f111d9e336d), HOST_WIDE_INT_UC (0xfe4ae42ca0336dee),
> +    HOST_WIDE_INT_UC (0xebd720f35a1baebc), HOST_WIDE_INT_UC (0x4fd3dbbf7d4324d6),
> +    HOST_WIDE_INT_UC (0x4d78cb3165e57f22), HOST_WIDE_INT_UC (0x62e39c282e564f40),
> +    HOST_WIDE_INT_UC (0x58a8b34a0882fabb), HOST_WIDE_INT_UC (0xbd6a54b970aa6765),
> +    HOST_WIDE_INT_UC (0x12f7298ae3ec1a4e), HOST_WIDE_INT_UC (0xb3dfe9e1c64aba27),
> +    HOST_WIDE_INT_UC (0xf5ae414ef25fcfb0), HOST_WIDE_INT_UC (0x6bd04f05fc0656ae),
> +    HOST_WIDE_INT_UC (0x61c83d0178ecc390), HOST_WIDE_INT_UC (0xbe5310392ee661d9),
> +    HOST_WIDE_INT_UC (0xb1ef589359431e81), HOST_WIDE_INT_UC (0x187f0dbf9a2cb650),
> +    HOST_WIDE_INT_UC (0xab7b6664a0b0aec2), HOST_WIDE_INT_UC (0x287a358e7bdad628),
> +    HOST_WIDE_INT_UC (0xb6853808e16aeb8b), HOST_WIDE_INT_UC (0x2268d04ba71b1ff7),
> +    HOST_WIDE_INT_UC (0xadd0a43eb925494a), HOST_WIDE_INT_UC (0xaabe8fa96600a548),
> +    HOST_WIDE_INT_UC (0x4f9a6641525c31e3), HOST_WIDE_INT_UC (0x90fd1e86293f4bd4),
> +    HOST_WIDE_INT_UC (0xe2ad2b5c90e9800b), HOST_WIDE_INT_UC (0x914e8dacffa771fc),
> +    HOST_WIDE_INT_UC (0xab104f92f2b7f5f0), HOST_WIDE_INT_UC (0x7ba77c13f62c21c4),
> +
> +    HOST_WIDE_INT_UC (0x004eb118946c8b0a), HOST_WIDE_INT_UC (0xcd10ba90ac387e24),
> +    HOST_WIDE_INT_UC (0x3165a4c40640630e), HOST_WIDE_INT_UC (0x76dbccb2bb28b589),
> +    HOST_WIDE_INT_UC (0x78c7d08d1846ba72), HOST_WIDE_INT_UC (0x088dadabc29b7eee),
> +    HOST_WIDE_INT_UC (0xce09b01b92a09c9f), HOST_WIDE_INT_UC (0x5a3020593ce05c03),
> +    HOST_WIDE_INT_UC (0x2bdc49e21551752d), HOST_WIDE_INT_UC (0x0c68f10ea335eed3),
> +    HOST_WIDE_INT_UC (0xc7eeacac4c89f081), HOST_WIDE_INT_UC (0x1709baf3ff0cbf03),
> +    HOST_WIDE_INT_UC (0x30f6ee76b7390893), HOST_WIDE_INT_UC (0x34837770023b44df),
> +    HOST_WIDE_INT_UC (0x03bb2fa9e55edd44), HOST_WIDE_INT_UC (0xdcde0127dcf651cc),
> +    HOST_WIDE_INT_UC (0xddf5b10f46c14a92), HOST_WIDE_INT_UC (0x5fd6a6333b7fc3d4),
> +    HOST_WIDE_INT_UC (0xf00d6a63a6292f33), HOST_WIDE_INT_UC (0x4c1b946f4bfdf52a),
> +    HOST_WIDE_INT_UC (0x995e31dd31510f3b), HOST_WIDE_INT_UC (0x8d35a772d465d990),
> +    HOST_WIDE_INT_UC (0xdef217407399bfcc), HOST_WIDE_INT_UC (0x0afb0b5823306986),
> +    HOST_WIDE_INT_UC (0xbb3485a144d31f32), HOST_WIDE_INT_UC (0x59f476dbe59fbd66),
> +    HOST_WIDE_INT_UC (0x63ae89916180817f), HOST_WIDE_INT_UC (0xee37dbd94e282511),
> +    HOST_WIDE_INT_UC (0x811c761fe6104d7e), HOST_WIDE_INT_UC (0x1ed873f682f029e2),
> +    HOST_WIDE_INT_UC (0xc23b89782db3f7f0), HOST_WIDE_INT_UC (0x98dee95dea174c4c),
> +    HOST_WIDE_INT_UC (0x5f91f3949dc9992e), HOST_WIDE_INT_UC (0xc36ae182d8aa7d32),
> +    HOST_WIDE_INT_UC (0x61abef3db5f22a7f), HOST_WIDE_INT_UC (0x91ce45bbc50c2eef),
> +    HOST_WIDE_INT_UC (0x5ab513c1350cd605), HOST_WIDE_INT_UC (0xcad14061bf6ec9fb),
> +    HOST_WIDE_INT_UC (0x29557d00db0a03ed), HOST_WIDE_INT_UC (0xd084f8402af7c773),
> +    HOST_WIDE_INT_UC (0x3becec18677ff915), HOST_WIDE_INT_UC (0x12bfce5297ee2e67),
> +    HOST_WIDE_INT_UC (0x49328e0ad6868d03), HOST_WIDE_INT_UC (0xae508be370a5fe87),
> +    HOST_WIDE_INT_UC (0xd04dbe85dd7b93e0), HOST_WIDE_INT_UC (0x2c8c32cb40d820db),
> +    HOST_WIDE_INT_UC (0x17a33407c1a4f783), HOST_WIDE_INT_UC (0x0333bdab351f1a1b),
> +    HOST_WIDE_INT_UC (0x9bf82ce2b590bd0e), HOST_WIDE_INT_UC (0xc28894ae9eb4a655),
> +    HOST_WIDE_INT_UC (0xe5f78919f01d70f0), HOST_WIDE_INT_UC (0x597376afa702626f),
> +    HOST_WIDE_INT_UC (0xb7e652d747bd63da), HOST_WIDE_INT_UC (0xffa518a4ec1620f7),
> +    HOST_WIDE_INT_UC (0xc7e3951a33f99457), HOST_WIDE_INT_UC (0x939c109b56348cb2),
> +    HOST_WIDE_INT_UC (0x0ba1c65a20616b8c), HOST_WIDE_INT_UC (0x230611c1a547fd7b),
> +    HOST_WIDE_INT_UC (0x5c9356e353506379), HOST_WIDE_INT_UC (0x6c32318308ba24f1),
> +    HOST_WIDE_INT_UC (0xd6c4a34b4f7f9a10), HOST_WIDE_INT_UC (0x26d3a3979e9e363c),
> +    HOST_WIDE_INT_UC (0xe8a16f6587bffa80), HOST_WIDE_INT_UC (0xc1ed972017d689a0),
> +
> +    HOST_WIDE_INT_UC (0x0b79b49ec18c4931), HOST_WIDE_INT_UC (0x115c713cb2bbdd4a),
> +    HOST_WIDE_INT_UC (0xcef8aaf62d4f3f26), HOST_WIDE_INT_UC (0x70cdc4645ffb4e5c),
> +    HOST_WIDE_INT_UC (0x984f9d6a9348d6ab), HOST_WIDE_INT_UC (0xf8c41d4a2b574ca0),
> +    HOST_WIDE_INT_UC (0xfdd5aa4e2834a549), HOST_WIDE_INT_UC (0x1827f517f49437ea),
> +    HOST_WIDE_INT_UC (0x764103fbd344ab6d), HOST_WIDE_INT_UC (0x20c51fd451673b02),
> +    HOST_WIDE_INT_UC (0xf86a9cbf50548a56), HOST_WIDE_INT_UC (0x99d47b8900cd9e1f),
> +    HOST_WIDE_INT_UC (0xb2100702869241b0), HOST_WIDE_INT_UC (0x06ce3ac9b28c4866),
> +    HOST_WIDE_INT_UC (0x1f2acc7dc8e7b7cb), HOST_WIDE_INT_UC (0x2b0791caf02d5216),
> +    HOST_WIDE_INT_UC (0xb424c7a051778b41), HOST_WIDE_INT_UC (0x0321156fc2e6527f),
> +    HOST_WIDE_INT_UC (0x27f1d9b65e9d1a3b), HOST_WIDE_INT_UC (0xf0b47d51a1e89b87),
> +    HOST_WIDE_INT_UC (0xbcced349ed2bafea), HOST_WIDE_INT_UC (0xdc6605db6da3d0e2),
> +    HOST_WIDE_INT_UC (0xe63f55538f6cc465), HOST_WIDE_INT_UC (0xffc6039160ed6b4a),
> +    HOST_WIDE_INT_UC (0x751afef08e1e5866), HOST_WIDE_INT_UC (0xd76fa3a0ff099bf5),
> +    HOST_WIDE_INT_UC (0xeaf7d50a6e4f1770), HOST_WIDE_INT_UC (0xd9e16c9d939bead9),
> +    HOST_WIDE_INT_UC (0xf66c7e0a7c742069), HOST_WIDE_INT_UC (0x04885a31cb8e66fb),
> +    HOST_WIDE_INT_UC (0x444f0dfc20767b0d), HOST_WIDE_INT_UC (0xed67c104c3b42f4e),
> +    HOST_WIDE_INT_UC (0x31690783130ff515), HOST_WIDE_INT_UC (0xec8d0e4d2f443535),
> +    HOST_WIDE_INT_UC (0x8a921fbfb7d1697e), HOST_WIDE_INT_UC (0x03dc72ab165df42c),
> +    HOST_WIDE_INT_UC (0x06ed32d252ab0973), HOST_WIDE_INT_UC (0xc91c248e5fa237ea),
> +    HOST_WIDE_INT_UC (0x152c9df43525b2aa), HOST_WIDE_INT_UC (0x2058d3ffa83aec4a),
> +    HOST_WIDE_INT_UC (0x8965b749cd657838), HOST_WIDE_INT_UC (0x75a36a7ac6447da7),
> +    HOST_WIDE_INT_UC (0xa1db4154df0987be), HOST_WIDE_INT_UC (0x6bbae09ce15065ec),
> +    HOST_WIDE_INT_UC (0xe344e810c167ae2f), HOST_WIDE_INT_UC (0xe06c1cad0722db02),
> +    HOST_WIDE_INT_UC (0x0d517556b404c733), HOST_WIDE_INT_UC (0x6f040cb1312570ca),
> +    HOST_WIDE_INT_UC (0xfdc069e42e7d809e), HOST_WIDE_INT_UC (0x80dba4e7cd9b082e),
> +    HOST_WIDE_INT_UC (0x97e6e1ad49608f72), HOST_WIDE_INT_UC (0x71f2846f412f18c0),
> +    HOST_WIDE_INT_UC (0x6361b93be86e129c), HOST_WIDE_INT_UC (0x281f4e3367f0f720),
> +    HOST_WIDE_INT_UC (0x7e68cd2315647fe3), HOST_WIDE_INT_UC (0xb604e0e6fd4facaa),
> +    HOST_WIDE_INT_UC (0xb9726a98d986b4d6), HOST_WIDE_INT_UC (0xcdc4a16b0b48a2c3),
> +    HOST_WIDE_INT_UC (0xac2dbd24a5ac955c), HOST_WIDE_INT_UC (0xfd2f500931f970c5),
> +    HOST_WIDE_INT_UC (0xb971cea7e0691a1b), HOST_WIDE_INT_UC (0xb82231449e45a839),
> +    HOST_WIDE_INT_UC (0x93b1bef87a77f070), HOST_WIDE_INT_UC (0x3d9513340e02ab65)
> +  };
> +  wide_int b = wide_int::from_array (&a[0], 64, 4096);
> +  wide_int c = wide_int::from_array (&a[64], 64, 4096);
> +  wide_int d = wide_int::from_array (&a[128], 64, 4096);
> +  ASSERT_EQ (b + c, d);
>  }
>  
>  } // namespace selftest
> 
> 	Jakub
> 
>
  

Just some off-the-cuff thoughts.  Might think differently when
I've had more time...

Richard Biener <rguenther@suse.de> writes:
> On Mon, 28 Aug 2023, Jakub Jelinek wrote:
>
>> Hi!
>> 
>> While the _BitInt series isn't committed yet, I had a quick look at
>> lifting the current lowest limitation on maximum _BitInt precision,
>> that wide_int can only support wide_int until WIDE_INT_MAX_PRECISION - 1.
>> 
>> Note, other limits if that is lifted are INTEGER_CST currently using 3
>> unsigned char members and so being able to only hold up to 255 * 64 = 16320
>> bit numbers and then TYPE_PRECISION being 16-bit, so limiting us to 65535
>> bits.  The INTEGER_CST limit could be dealt with by dropping the
>> int_length.offset "cache" and making int_length.extended and
>> int_length.unextended members unsinged short rather than unsigned char.
>> 
>> The following so far just compile tested patch changes wide_int_storage
>> to be a union, for precisions up to WIDE_INT_MAX_PRECISION inclusive it
>> will work as before (just being no longer trivially copyable type and
>> having an inline destructor), while larger precision instead use a pointer
>> to heap allocated array.
>> For wide_int this is fairly easy (of course, I'd need to see what the
>> patch does to gcc code size and compile time performance, some
>> growth/slowdown is certain), but I'd like to brainstorm on
>> widest_int/widest2_int.
>> 
>> Currently it is a constant precision storage with WIDE_INT_MAX_PRECISION
>> precision (widest2_int twice that), so memory layout-wide on at least 64-bit
>> hosts identical to wide_int, just it doesn't have precision member and so
>> 32 bits smaller on 32-bit hosts.  It is used in lots of places.
>> 
>> I think the most common is what is done e.g. in tree_int_cst* comparisons
>> and similarly, using wi::to_widest () to just compare INTEGER_CSTs.
>> That case actually doesn't even use wide_int but widest_extended_tree
>> as storage, unless stored into widest_int in between (that happens in
>> various spots as well).  For comparisons, it would be fine if
>> widest_int_storage/widest_extended_tree storages had a dynamic precision,
>> WIDE_INT_MAX_PRECISION for most of the cases (if only
>> precision < WIDE_INT_MAX_PRECISION is involved), otherwise the needed
>> precision (e.g. for binary ops) which would be what we say have in
>> INTEGER_CST or some type, rounded up to whole multiples of HOST_WIDE_INTs
>> and if unsigned with multiple of HOST_WIDE_INT precision, have another
>> HWI to make it always sign-extended.
>> 
>> Another common case is how e.g. tree-ssa-ccp.cc uses them, that is mostly
>> for bitwise ops and so I think the above would be just fine for that case.
>> 
>> Another case is how tree-ssa-loop-niter.cc uses it, I think for such a usage
>> it really wants something widest, perhaps we could just try to punt for
>> _BitInt(N) for N >= WIDE_INT_MAX_PRECISION in there, so that we never care
>> about bits beyond that limit?
>
> I'll note tree-ssa-loop-niter.cc also uses GMP in some cases, widest_int
> is really trying to be poor-mans GMP by limiting the maximum precision.

I'd characterise widest_int as "a wide_int that is big enough to hold
all supported integer types, without losing sign information".  It's
not big enough to do arbitrary arithmetic without losing precision
(in the way that GMP is).

If the new limit on integer sizes is 65535 bits for all targets,
then I think that means that widest_int needs to become a 65536-bit type.
(But not with all bits represented all the time, of course.)

[ And at that point I think widest_int should ideally become a GMP wrapper.
  The wide_int stuff isn't optimised for such large sizes, even accepting
  that large sizes will be a worst case.  That might not be easy to do with
  the current infrastructure though.  Especially not if widest_ints are
  stored in GC-ed structures. ]

That seems like it would stand the biggest chance of preserving
existing semantics.  But we might want to define new typedefs for
narrower limits.  E.g. the current widest_int limit probably still
makes sense for operations on scalar_int_modes.  (But then most
RTL arithmetic should use wide_int rather than widest_int.)

Perhaps some widest_int uses are really restricted to address-like
things and could instead use offset_int.  Until now there hasn't been
much incentive to make the distinction.

And perhaps we could identify other similar cases where the limit is
known (statically) to be the current limit, rather than 65536.

I think one of the worst things we could do is push the requirement
up to users of the API to have one path for _BitInts and one for "normal"
integers.  That's bound to lead to a whack-a-mole effect.

Thanks,
Richard
  

On Tue, Aug 29, 2023 at 09:49:59AM +0000, Richard Biener wrote:
> The simplest way would probably to keep widest_int at 
> WIDE_INT_MAX_PRECISION like we have now and assert that this is
> enough at ::to_widest time (we probably do already).  And then
> declare uses with more precision need to use GMP.
> 
> Not sure if that's not also a viable way for wide_int - we're
> only losing optimization here, no?

No.  In lots of places it is essential (constant evaluation), in other
places very much desirable optimization even or especially on _BitInt (e.g.
value range optimizations, ccp, ...) and then sure, spots where just punting
on larger _BitInt for optimization is something we can live with (and yet
other spots which only happen after the lowering and so will never see that
at all).

I think if we go with allowing _BitInt (N) for N >= WIDE_INT_MAX_PRECISION,
the most important thing is we want to slow down the compiler as little as
possible for the common case, no _BitInt at all or _BitInt smaller than that,
and furthermore from maintainance POV, we want most of the code to work as
is.  Adding assertion that precision is < WIDE_INT_MAX_PRECISION on
widest_int construction from wide_int/INTEGER_CST etc. wouldn't achieve
those goals.  Grepping outside of wide-int.{cc,h} for widest_int, I see
around 450 matches, sure, that doesn't mean 450 places where we'd need to
add some guard to punt for the larger _BitInt (if it is possible to punt at
all), but I'm sure it would be more than hundred of places.  And having
similarly say 50% of those 100-200 spots have a fallback using gmp would be
also a maintainance nightmare, because those spots for larger precisions
would be much less tested than normal code.  Sure, we can add some guards
in some places and the niter stuff could very well be one of them, or simply
also use there wide_int with carefully chosen precision, say
WIDE_INT_MAX_PRECISION if _BitInt isn't involved or at most 128 bits,
and otherwise something wider.  But I'm worried of the maintainance
nightmare etc. if we have to touch hundreds of places and figure out how to
punt or what else to do in each of those spots.

Compared to this, I see only 15 hits for widest2_int, in 2 places,
arith_overflowed_p and operator_mult::wi_fold, that is something that could
very well be done either always using appropriate wider precision wide_int,
or even do it twice, once for < WIDE_INT_MAX_PRECISION input precision and
another time wider.

	Jakub
  

On Tue, Aug 29, 2023 at 11:42:48AM +0100, Richard Sandiford wrote:
> > I'll note tree-ssa-loop-niter.cc also uses GMP in some cases, widest_int
> > is really trying to be poor-mans GMP by limiting the maximum precision.
> 
> I'd characterise widest_int as "a wide_int that is big enough to hold
> all supported integer types, without losing sign information".  It's
> not big enough to do arbitrary arithmetic without losing precision
> (in the way that GMP is).
> 
> If the new limit on integer sizes is 65535 bits for all targets,
> then I think that means that widest_int needs to become a 65536-bit type.
> (But not with all bits represented all the time, of course.)

If the widest_int storage would be dependent on the len rather than
precision for how it is stored, then I think we'd need a new method which
would be called at the start of filling the limbs where we'd tell how many
limbs there would be (i.e. what will set_len be called with later on), and
do nothing for all storages but the new widest_int_storage.

> [ And at that point I think widest_int should ideally become a GMP wrapper.
>   The wide_int stuff isn't optimised for such large sizes, even accepting
>   that large sizes will be a worst case.  That might not be easy to do with
>   the current infrastructure though.  Especially not if widest_ints are
>   stored in GC-ed structures. ]

I strongly hope widest_ints aren't stored in GC-ed structures, we should
be using INTEGER_CSTs or RTXes in GC-ed structures, not wide_int/widest_int
IMNSHO.
nm cc1plus | grep gt_ggc.*widest_int
doesn't show anything,
nm cc1plus | grep gt_ggc.*wide_int
0000000000b2c88d T _Z43gt_ggc_mx_hash_table_const_wide_int_hasher_Pv
0000000000d00b3a T _Z44gt_ggc_mx_generic_wide_int_wide_int_storage_Pv
0000000000d1c8bb W _Z9gt_ggc_mxI16wide_int_storageEvP16generic_wide_intIT_E
0000000000b2eecb W _Z9gt_ggc_mxI21const_wide_int_hasherEvP10hash_tableIT_Lb0E11xcallocatorE
0000000001596e00 T _Z9gt_ggc_mxP16generic_wide_intI22fixed_wide_int_storageILi576EEE
0000000000d00b8e T _Z9gt_ggc_mxR16wide_int_storage
0000000000b2c8e1 T _Z9gt_ggc_mxR21const_wide_int_hasher
From those symbols, only the second has any undefined references to that
(in dwarf2out.o) plus gtype-desc.o defines them and has some references.

In dwarf2out it is dw_val_node's v.wide_int_ptr.  Already the (apparently
incomplete) wide_int patch would need to deal with that, either by making
those say fixed_wide_int_storage <WIDE_INT_MAX_PRECISION> or something
similar, so it would never store anything larger, or run the destructor
when actually freeing it (dunno if that is possible right now in GC).

> That seems like it would stand the biggest chance of preserving
> existing semantics.  But we might want to define new typedefs for
> narrower limits.  E.g. the current widest_int limit probably still
> makes sense for operations on scalar_int_modes.  (But then most
> RTL arithmetic should use wide_int rather than widest_int.)
> 
> Perhaps some widest_int uses are really restricted to address-like
> things and could instead use offset_int.  Until now there hasn't been
> much incentive to make the distinction.

Sure.

> And perhaps we could identify other similar cases where the limit is
> known (statically) to be the current limit, rather than 65536.
> 
> I think one of the worst things we could do is push the requirement
> up to users of the API to have one path for _BitInts and one for "normal"
> integers.  That's bound to lead to a whack-a-mole effect.

Yeah.
As for uses of GMP, I think actually most wide-int.{h,cc} operations aren't
that bad compared to GMP, it is most important to have a fast path for the
most common case and for something rare being say some small constant times
slower than GMP is acceptable (say because GMP will have some assembly
hand-written inner loop while wide-int doesn't).  Something different
is say multiplication/division, perhaps for those in the out of line
wide-int.cc helpers we could check for precision above certain boundary and
in that case convert to mpn, perform multiplication/division/modulo using
that and convert back, because the gmp algorithms for those are much better.

	Jakub