Re: patch to fix constant math

[Richard Guenther <richard.guenther@gmail.com>]

On Fri, Oct 5, 2012 at 2:26 PM, Richard Sandiford
<rdsandiford@googlemail.com> wrote:
> Richard Guenther <richard.guenther@gmail.com> writes:
>> On Fri, Oct 5, 2012 at 1:24 PM, Richard Sandiford
>> <rdsandiford@googlemail.com> wrote:
>>> Richard Guenther <richard.guenther@gmail.com> writes:
>>>> The issue is that unlike RTL where we "construct" double-ints from
>>>> CONST_INT/CONST_DOUBLE right now, tree has the double-int
>>>> _embedded_.  That's why I say that the thing we embed in
>>>> a CONST_WIDE_INT or a tree INTEGER_CST needs to be
>>>> "bare metal", and that's what I would call wide-int.
>>>
>>> OK, but that's deliberately not what Kenny's patch calls "wide int".
>>> The whole idea is that the "bare metal" thing we embed in a
>>> CONST_WIDE_INT or tree isn't (and doesn't need to be) the same
>>> as the type that we use to operate on integers.  That bare-metal
>>> thing doesn't even have to have a fixed width.  (CONST_WIDE_INT
>>> doesn't have a fixed width, it's only as big as the integer
>>> needs it to be.)
>>
>> Ok, let's rephrase it this way then: the "bare metal" thing used
>> for the storage should ideally be the same in the tree IL and the RTL
>> IL _and_ the higher-level abstract wide-int.
>
> Hmm, OK, that's a straight disagreement then.
>
>>>> So to me wide-ints provide the higher-level abstraction ontop of
>>>> double-ints (which would remain the storage entity).
>>>>
>>>> Such higher-level abstraction is very useful, also for double-ints and
>>>> also on the tree level.  There is no requirement to provide bigger
>>>> double-int (or wide-int) for this.  Let's call this abstraction
>>>> wide-int (as opposed to my suggested more piecemail double_sint,
>>>> double_uint).  You can perfectly model it ontop of the existing
>>>> double_int storage.
>>>>
>>>> As of providing larger "double-ints" - there is not much code left
>>>> (ok, quite an overstatement ;)) that relies on the implementation
>>>> detail of double-int containing exactly two HOST_WIDE_INTs.
>>>> The exact purpose of double-ints was to _hide_ this (previously
>>>> we only had routines like mul_double_with_sign which take
>>>> two HOST_WIDE_INT components).  Most code dealing with
>>>> the implementation detail is code interfacing with middle-end
>>>> routines that take a HOST_WIDE_INT argument (thus the
>>>> double_int_fits_hwi_p predicates) - even wide_int has to support
>>>> this kind of interfacing.
>>>>
>>>> So, after introducing wide_int that just wraps double_int and
>>>> changing all user code (hopefully all, I guess mostly all), we'd
>>>> tackle the issue that the size of double_int's is host dependent.
>>>> A simple solution is to make it's size dependent on a target macro
>>>> (yes, macro ...), so on a 32bit HWI host targeting a 64bit 'HWI' target
>>>> you'd simply have four HWIs in the 'double-int' storage (and
>>>> arithmetic needs to be generalized to support this).
>>>
>>> I just don't see why this is a good thing.  The constraints
>>> are different when storing integers and when operating on them.
>>> When operating on them, we want something that is easily constructed
>>> on the stack, so we can create temporary structures very cheaply,
>>> and can easily pass and return them.  We happen to know at GCC's
>>> compile time how big the biggest integer will ever be, so it makes
>>> sense for wide_int to be that wide.
>>
>> I'm not arguing against this.  I'm just saying that the internal
>> representation will depend on the host - not the number of total
>> bits, but the number of pieces.
>
> Sure, but Kenny already has a macro to specify how many bits we need
> (MAX_BITSIZE_MODE_ANY_INT).  We can certainly wrap:
>
>   HOST_WIDE_INT val[MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT];
>
> in a typedef if that's what you prefer.

I'd prefer it to be initially double_int, and later "fixed" to double_int
with a member like the above.  Possibly renamed as well.

>>> But when storing integers we want something compact.  If your
>>> machine supports 256-bit integers, but the code you're compiling
>>> makes heavy use of 128-bit integers, why would you want to waste
>>> 128 of 256 bits on every stored integer?  Which is why even
>>> CONST_WIDE_INT doesn't have a fixed width.
>>>
>>> You seem to be arguing that the type used to store integers in the IR
>>> has to be same as the one that we use when performing compile-time
>>> arithmetic, but I think it's better to have an abstraction between
>>> the two.
>>
>> Well, you don't want to pay the cost dividing 256bit numbers all
>> the time when most of your numbers are only 128bit.  So we don't
>> really want to perform compile-time arithmetic on the biggest
>> possible precision either.
>
> wide_int doesn't perform them in the biggest possible precision.
> It performs them in the precision of the result.  It just happens
> to have enough storage to cope with all possible precisions (because
> the actual precision of the result is usually only known at GCC's runtime).
>
>>> So if you think a pair of HWIs continues to be a useful way of
>>> storing integers at the tree level, then we can easily continue
>>> to use a pair of HWIs there.
>>
>> How do you store larger ints there then?
>
> You'd need another tree code for wider integers.  I'm not saying that's
> a good idea, I just wasn't sure if it's what you wanted.

Uh, ok.

>> How is CONST_WIDE_INT variable size?
>
> It's just the usual trailing variable-length array thing.

Good.  Do you get rid of CONST_DOUBLE (for integers) at the same time?

>> Why can wide-int not be variable-size?
>
> Because variable-length arrays are usually more expensive
> than (still fairly small) fixed-length arrays when dealing
> with temporaries.

which is why I'd have made it a template (but I admit I didn't fully
investigate all issues).  Something like

template <unsigned bits>  (or bytes?)
struct wide_int {
  unsigned short precision;
  HOST_WIDE_INT val[(bits + HOST_BITS_PER_WIDE_INT - 1) /
HOST_BITS_PER_WIDE_INT];
};

so it would not be variable-size at compile-time but we'd be able
to constrain its maximum size.  That's important for things like
CCP which keep a lattice of ints and maybe do not want to care
about tracking your new 4096-bit integers.

But maybe we don't really care.

>>> Or if you'd prefer every tree integer
>>> to be the same width as a wide_int, we can do that too.  (I don't
>>> know what Kenny's tree patch does.)
>>
>> Keenys patch truncates wide-ints to two HWIs in wide-int-to-tree
>> without any checking (I claimed it's a bug, Kenny says its a feature).
>
> Only because he split the rtl and tree parts up.  By "Kenny's tree patch",
> I meant the patch that he said he was going to send (part 4 as he called it).
>
> Until then, we're not regressing at the tree level, and I think
> the patch is a genuine RTL improvement on its own.
>
>>> Another advantage of abstracting away the storage type is that
>>> we could store things like an overflow flag in the wide_int
>>> (if that ever proves useful) without worrying about the impact
>>> on the tree and RTL footprint.
>>
>> Sure.
>>
>> We seem to be talking in circles.  You don't seem to want (or care)
>> about a common storage for tree, RTL and wide-int.  You seem to
>> care about that operate-on-wide-ints thing.  I am saying if you keep
>> double-ints as-is you create two similar things which should be one thing.
>
> The idea is to get rid of double_ints altogether.  They shouldn't have
> any use once everything has been converted to wide_ints.
>
>> So, make double-int storage only.
>
> The idea was to treat them as legacy and get rid of them as soon
> as we can.
>
>> What I don't see is that the patch just introduces wide-int as type
>> to do compile-time math on in RTL.  It does more (the patch is large
>> and I didn't read it in detail).
>
> Yeah, it introduces things like the CONST_SCALAR_INT_P abstraction.
> But I actually find the patch easier to review like that, because both
> changes are affecting the same kinds of place.
>
>> It doesn't even try to address the same on the tree level.
>
> Because as Kenny's already said, that's a separate patch.
>
>> It doesn't address the fundamental issue of double-int size being host
>> dependent.
>
> Because the plan is to get rid of it :-)
>
> * Trivial, but it has the wrong name.
>
> * It has the wrong interface for general-precision arithmetic because
>   it doesn't say how wide the value stored (or to be stored) in those
>   HOST_WIDE_INTs actually is.  E.g. there's no such thing as an "X-bit
>   add followed by an X-bit division".  You have to a "double_int-wide
>   add", followed by a truncation/extension to X bits, followed by a
>   "double_int-wide division", followed by another truncation/extension
>   to X bits.  Which we don't do in RTL; we just assume or (occasionally)
>   assert that we only use double_int for modes whose precisions are
>   exactly 2 * HOST_BITS_PER_WIDE_INT.
>
> * Using a fixed-length array of HOST_WIDE_INTs is too inflexible
>   for size-conscious IRs, so just bumping its size probably isn't
>   a good idea for them.  But having a fixed-length array does
>   IMO make sense for temporaries.
>
> * If we made it storage-only, it doesn't need all those operations.
>
> Which is why I agree with Kenny that double_int as it exists today
> isn't the right starting point.

Ok, I see where you are going.  Let me look at the patch again.

Richard.

> Richard