Re: [wide-int] int_traits <tree>

[Richard Biener <rguenther at suse dot de>]

On Thu, 17 Oct 2013, Kenneth Zadeck wrote:

> On 10/17/2013 09:48 AM, Richard Biener wrote:
> > On Thu, 17 Oct 2013, Richard Sandiford wrote:
> > 
> > > Richard Biener <rguenther@suse.de> writes:
> > > > On Thu, 17 Oct 2013, Richard Sandiford wrote:
> > > > 
> > > > > 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.
> > > > "     2) addr_wide_int.  This is a fixed size representation that is
> > > >       guaranteed to be large enough to compute any bit or byte sized
> > > >       address calculation on the target.  Currently the value is 64 + 4
> > > >       bits rounded up to the next number even multiple of
> > > >       HOST_BITS_PER_WIDE_INT (but this can be changed when the first
> > > >       port needs more than 64 bits for the size of a pointer).
> > > > 
> > > >       This flavor can be used for all address math on the target.  In
> > > >       this representation, the values are sign or zero extended based
> > > >       on their input types to the internal precision.  All math is done
> > > >       in this precision and then the values are truncated to fit in the
> > > >       result type.  Unlike most gimple or rtl intermediate code, it is
> > > >       not useful to perform the address arithmetic at the same
> > > >       precision in which the operands are represented because there has
> > > >       been no effort by the front ends to convert most addressing
> > > >       arithmetic to canonical types.
> > > > 
> > > >       In the addr_wide_int, all numbers are represented as signed
> > > >       numbers.  There are enough bits in the internal representation so
> > > >       that no infomation is lost by representing them this way."
> > > > 
> > > > so I guess from that that addr_wide_int.get_precision is always
> > > > that "64 + 4 rounded up".  Thus decompose gets that constant precision
> > > > input and the extra zeros make the necessary extension always a no-op.
> > > > Aha.
> > > > 
> > > > For max_wide_int the same rules apply, just its size is larger.
> > > > 
> > > > Ok.  So the reps are only canonical wide-int because we only
> > > > ever use them with precision > xprecision (maybe we should assert
> > > > that).
> > > No, we allow precision == xprecision for addr_wide_int and max_wide_int
> > > too.
> > > But all we do in that case is trim the length.
> > > 
> > > Requiring precision > xprecision was option (5) from my message.
> > > 
> > > > Btw, we are not using them directly, but every time we actually
> > > > build a addr_wide_int / max_wide_int we copy them anyway:
> > > > 
> > > > /* Initialize the storage from integer X, in precision N.  */
> > > > template <int N>
> > > > template <typename T>
> > > > inline fixed_wide_int_storage <N>::fixed_wide_int_storage (const T &x)
> > > > {
> > > >    /* Check for type compatibility.  We don't want to initialize a
> > > >       fixed-width integer from something like a wide_int.  */
> > > >    WI_BINARY_RESULT (T, FIXED_WIDE_INT (N)) *assertion ATTRIBUTE_UNUSED;
> > > >    wide_int_ref xi (x, N);
> > > >    len = xi.len;
> > > >    for (unsigned int i = 0; i < len; ++i)
> > > >      val[i] = xi.val[i];
> > > > }
> > > Are you saying that:
> > > 
> > >       max_wide_int x = (tree) y;
> > > 
> > > should just copy a pointer?  Then what about:
> > No, it should do a copy.  But only one - which it does now with
> > the append-extra-zeros-in-tree-rep, I was just thinking how to
> > avoid it when not doing that which means adjusting the rep in
> > the copy we need to do anyway.  If fixed_wide_int_storage is
> > really the only reason to enlarge the tree rep.
> >   
> > >       max_wide_int z = x;
> > > 
> > > Should that just copy a pointer too, or is it OK for the second
> > > constructor
> > > to do a copy?
> > > 
> > > In most cases we only use the fixed_wide_int to store the result of the
> > > computation.  We don't use the above constructor for things like:
> > > 
> > >       max_wide_int x = wi::add ((tree) y, (int) z);
> > > 
> > > wi::add uses y and z without going through max_wide_int.
> > Yes, I am aware of that.
> > 
> > > > What's the reason again to not use my original proposed encoding
> > > > of the MSB being the sign bit?  RTL constants simply are all signed
> > > > then.  Just you have to also sign-extend in functions like lts_p
> > > > as not all constants are sign-extended.  But we can use both tree
> > > > (with the now appended zero) and RTL constants representation
> > > > unchanged.
> > > The answer's the same as always.  RTL constants don't have a sign.
> > > Any time we extend an RTL constant, we need to say whether the extension
> > > should be sign extension or zero extension.  So the natural model for
> > > RTL is that an SImode addition is done to SImode width, not some
> > > arbitrary wider width.
> > RTL constants are sign-extended (whether you call them then "signed"
> > is up to you).  They have a precision.  This is how they are
> > valid reps for wide-ints, and that doesn't change.
> > 
> > I was saying that if we make not _all_ wide-ints sign-extended
> > then we can use the tree rep as-is.  We'd then have the wide-int
> > rep being either zero or sign extended but not arbitrary random
> > bits outside of the precision (same as the tree rep).
> > 
> > As nearly 100% of all compile-time constant math is done on
> > the tree level pessimizing that just because we can invent sth
> > that only fits RTX and not tree looks wrong.  At least if we
> > can invent sth that fits _both_, which I think we can (see above).
> This would be a disaster.   the wide int rep is the same as the double-int
> rep.    both do not have an explicit bit that says that this came from a
> signed or unsigned value.    Once you go down that road then you have to start
> saying what you mean for every binary operation if the signedness does not
> match.   And you have to say for every comparison what it means to compare
> unsigned numbers in a signed way......

Signedness only matters for operations where we already specify it.
A plus or a minus doesn't care about the upper bits (twos complement
to the rescue), so the only question is how do you extend the result?
Obvious: the wide-int way (sign-extend).

But I suppose you are right.  The only way to make it work reasonably
efficient would be for infinite precision wide-ints.

Bah.

Now I'm thinking of having the storage rep say if it is reliably
sign-extended,

  static const bool is_sign_extended = ...;

which would be true for wide-int and RTX but not for tree.  In
'signed' function variants you then can no longer rely on all
values being sign-extended but you have to do sth like

  if (!x::is_sign_extended)
    sext (x);

which should be decidable at compile-time.  Note that all this
dances are to avoid ::decompose of trees of making a copy and
thus introducing possibly escaped local (large) storage.

That said, even the _large workers can just get this flag as
input and do the sign-extension on-the-fly?

Richard.