Re: [wide-int] int_traits <tree>

[Richard Sandiford <rsandifo at linux dot vnet dot ibm dot com>]

Richard Biener <rguenther@suse.de> writes:
>> The new tree representation can have a length greater than max_len
>> for an unsigned tree constant that occupies a whole number of HWIs.
>> The tree representation of an unsigned 0x8000 is 0x00 0x80 0x00.
>> When extended to max_wide_int the representation is the same.
>> But a 2-HWI addr_wide_int would be 0x80 0x00, without the leading zero.
>> The MIN trims the length from 3 to 2 in the last case.
>
> Oh, so it was the tree rep that changed?  _Why_ was it changed?
> We still cannot use it directly from wide-int and the extra
> word is redundant because we have access to TYPE_UNSIGNED (TREE_TYPE ()).

It means that we can now use the tree's HWI array directly, without any
copying, for addr_wide_int and max_wide_int.  The only part of decompose ()
that does a copy is the small_prec case, which is trivially compiled out
for addr_wide_int and max_wide_int.

>> > > the case actually comes up on the ppc because they do a lot of 128 bit 
>> >> > math.    I think i got thru the x86-64 without noticing this.
>> >> 
>> >> Well, it'd be suspicious if we're directly using 128-bit numbers
>> >> in addr_wide_int.  The justification for the assertion was that we
>> >> should explicitly truncate to addr_wide_int when deliberately
>> >> ignoring upper bits, beyond bit or byte address width.  128 bits
>> >> definitely falls into that category on powerpc.
>> >
>> > My question is whether with 8-bit HWI 0x00 0xff 0xff is a valid
>> > wide-int value if it has precision 16.
>> 
>> No, for a 16-bit wide_int it should be 0xff.  0x00 0xff 0xff is correct
>> for any wide_int wider than 16 bits though.
>> 
>> > AFAIK that is what the code produces,
>> 
>> In which case?  This is:
>> 
>>    precision == 16
>>    xprecision == 16
>>    len == 3
>>    max_len == 2
>> 
>> The MIN trims the len to 2 and then the loop Kenny added trims it
>> again to 1, so the "0x00 0xff 0xff" becomes "0xff".  The "0x00 0xff"
>> is still there in the array, but not used.
>> 
>> > but now Kenny says this is only for some kind
>> > of wide-ints but not all?  That is, why is
>> >
>> > inline wi::storage_ref
>> > wi::int_traits <const_tree>::decompose (HOST_WIDE_INT *scratch,
>> >                                         unsigned int precision, const_tree 
>> > x)
>> > {
>> >   unsigned int len = TREE_INT_CST_NUNITS (x);
>> >   const HOST_WIDE_INT *val = (const HOST_WIDE_INT *) &TREE_INT_CST_ELT (x, 
>> > 0);
>> >   return wi::storage_ref (val, len, precision);
>> > }
>> >
>> > not a valid implementation together with making sure that the
>> > INTEGER_CST tree rep has that extra word of zeros if required?
>> 
>> The fundamental problem here is that we're trying to support two cases:
>> 
>> (a) doing N-bit arithemtic in cases where the inputs have N bits
>> (b) doing N-bit arithmetic in cases where the inputs have fewer than N bits
>>     and are extended according to TYPE_SIGN.
>> 
>> Let's assume 32-bit HWIs.  The 16-bit (4-hex-digit) constant 0x8000 is
>> 0x8000 regardless of whether the type is signed or unsigned.  But if it's
>> extended to 32-bits you get two different numbers 0xffff8000 and 0x00008000,
>> depending on the sign.
>> 
>> So for one value of the "precision" parameter (i.e. xprecision), signed
>> and unsigned constants produce the same number.  But for another value
>> of the "precision" parameter (those greater than xprecision), signed and
>> unsigned constants produce different numbers.  Yet at the moment the tree
>> constant has a single representation.
>
> But a correctly extended one, up to its len!  (as opposed to RTL)

But extending the precision can change the right value of "len".
Take the same example with 16-bit HWIs.  In wide_int terms, and with
the original tree representation, the constant is a single HWI:

    0x8000

with len 1.  And in case (a) -- where we're asking for a 16-bit wide_int --
this single HWI is all we want.  The signed and unsigned constants give
the same wide_int.

But the same constant extended to 32 bits and left "uncompressed" would be
two HWIs:

    0x0000 0x8000 for unsigned constants
    0xffff 0x8000 for signed constants

Compressed according to the sign scheme they are:

    0x0000 0x8000 (len == 2) for unsigned constants
           0x8000 (len == 1) for signed constants

which is also the new tree representation.

So the unsigned case is different for (a) and (b).

>> So I think the possibilities are:
>> 
>> (1) Use the representation of an N-bit wide_int to store N-bit tree constants.
>>     Do work when extending them to wider wide_ints.
>> 
>> (2) Use the representation of max_wide_int to store N-bit tree constants.
>>     Do work when creating an N-bit wide_int.
>> 
>> (3) Store both representations in the tree constant.
>> 
>> (4) Require all tree arithmetic to be done in the same way as rtl arithmetic,
>>     with explicit extensions.  This gets rid of case (b).
>> 
>> (5) Require all tree arithemtic to be done in wider wide_ints than the inputs,
>>     which I think is what you preferred.  This gets rid of case (a).
>> 
>> (6) Allow the same wide_int constant to have several different
>> representations.
>>     Remember that this is to some extent what Kenny's original implementation
>>     did, since partial HWIs were filled with don't-cares.  You and I are the
>>     ones who argued that each wide_int should have a single representation.
>
> As far as I can see when we need to extend the tree rep to a bigger
> precision (extend according to its sign) the only thing we have to
> do to make the wide-int rep canonical is sign-extend the tree rep
> at the desired precision.

That's what the new representation does.  It sign-extends from
TYPE_PRECISION to any value greater than TYPE_PRECISION.

> And as we never truncate this sign-extension
> is a no-op for signed tree constants, is a no-op for unsigned
> tree constants when precision > xprecision but not for unsigned tree
> constants and precision == xprecision when the MSB is set.

Are you talking about addr_wide_int and max_wide_int only,
or wide_int too?  The above is right for addr_wide_int and max_wide_int,
and is also all that decompose does for those cases.  The small_prec case
is compiled out because the "precision" parameter is constant and
known at compile time to be a HWI multiple.

But the small_prec case is needed for wide_ints whenever len == max_len.
That includes the precision == xprecision case, but also something like:

     precision == 13, xprecision == 12

Which is unlikely to occur in practice, but given that the code is
still needed for precision == xprecision == 12, there's not much
point forbidding it.

Thanks,
Richard