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
