patch to fix constant math - 4th patch - the wide-int class - patch ping for the next stage 1

This patch contains a large number of the changes requested by Richi.   
It does not contain any of the changes that he requested to abstract the 
storage layer.   That suggestion appears to be quite unworkable.

I believe that the wide-int class addresses the needs of gcc for 
performing math on any size integer irregardless of the platform that 
hosts the compiler.  The interface is admittedly large, but it is large 
for a reason:  these are the operations that are commonly performed by 
the client optimizations in the compiler.

I would like to get this patch preapproved for the next stage 1.

kenny
2013-2-26  Kenneth Zadeck <zadeck@naturalbridge.com>

	* Makefile.in (wide-int.c, wide-int.h): New files.
	* wide-int.c: New file containing implementation of wide_int class.
	* wide-int.h: New file containing public spec for wide_int class.

On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
<zadeck@naturalbridge.com> wrote:
> This patch contains a large number of the changes requested by Richi.   It
> does not contain any of the changes that he requested to abstract the
> storage layer.   That suggestion appears to be quite unworkable.
>
> I believe that the wide-int class addresses the needs of gcc for performing
> math on any size integer irregardless of the platform that hosts the
> compiler.  The interface is admittedly large, but it is large for a reason:
> these are the operations that are commonly performed by the client
> optimizations in the compiler.
>
> I would like to get this patch preapproved for the next stage 1.

Please clean from dead code like

+// using wide_int::;

and

+#ifdef DEBUG_WIDE_INT
+  if (dump_file)
+    debug_wh ("wide_int::from_shwi %s " HOST_WIDE_INT_PRINT_HEX ")\n",
+             result, op0);
+#endif

and

+#ifdef NEW_REP_FOR_INT_CST
+  /* This is the code once the tree level is converted.  */
+  wide_int result;
+  int i;
+
+  tree type = TREE_TYPE (tcst);
+
+  result.bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
+  result.precision = TYPE_PRECISION (type);
+  result.len = TREE_INT_CST_LEN (tcst);
+  for (i = 0; i < result.len; i++)
+    result.val[i] = TREE_INT_CST_ELT (tcst, i);
+
+  return result;
+#else

this also shows the main reason I was asking for storage abstraction.
The initialization from tree is way too expensive.

+/* Convert a integer cst into a wide int expanded to BITSIZE and
+   PRECISION.  This call is used by tree passes like vrp that expect
+   that the math is done in an infinite precision style.  BITSIZE and
+   PRECISION are generally determined to be twice the largest type
+   seen in the function.  */
+
+wide_int
+wide_int::from_tree_as_infinite_precision (const_tree tcst,
+                                          unsigned int bitsize,
+                                          unsigned int precision)
+{

I know you have converted everything, but to make this patch reviewable
I'd like you to strip the initial wide_int down to a bare minimum.

Only then people will have a reasonable chance to play with interface
changes (such as providing a storage abstraction).

+/* Check the upper HOST_WIDE_INTs of src to see if the length can be
+   shortened.  An upper HOST_WIDE_INT is unnecessary if it is all ones
+   or zeros and the top bit of the next lower word matches.
+
+   This function may change the representation of THIS, but does not
+   change the value that THIS represents.  It does not sign extend in
+   the case that the size of the mode is less than
+   HOST_BITS_PER_WIDE_INT.  */
+
+void
+wide_int::canonize ()

this shouldn't be necessary - it's an optimization - and due to value
semantics (yes - I know you have a weird mix of value semantics
and modify-in-place in wide_int) the new length should be computed
transparently when creating a new value.

Well.  Leaving wide-int.c for now.

+class wide_int {
+  /* Internal representation.  */
+
+  /* VAL is set to a size that is capable of computing a full
+     multiplication on the largest mode that is represented on the
+     target.  The full multiplication is use by tree-vrp.  tree-vpn
+     currently does a 2x largest mode by 2x largest mode yielding a 4x
+     largest mode result.  If operations are added that require larger
+     buffers, then VAL needs to be changed.  */
+  HOST_WIDE_INT val[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT];

as you conver partial int modes in MAX_BITSIZE_MODE_ANY_INT the
above may come too short.  Please properly round up.

+  unsigned short len;
+  unsigned int bitsize;
+  unsigned int precision;

I see we didn't get away with this mix of bitsize and precision.  I'm probably
going to try revisit the past discussions - but can you point me to a single
place in the RTL conversion where they make a difference?  Bits beyond
precision are either undefined or properly zero-/sign-extended.  Implicit
extension beyond len val members should then provide in "valid" bits
up to bitsize (if anyone cares).  That's how double-ints work on tree
INTGER_CSTs
which only care for precision, even with partial integer mode types
(ok, I never came along one of these beasts - testcase / target?).

[abstraction possibility - have both wide_ints with actual mode and
wide_ints with arbitrary bitsize/precision]

+  enum ShiftOp {
+    NONE,
+    /* There are two uses for the wide-int shifting functions.  The
+       first use is as an emulation of the target hardware.  The
+       second use is as service routines for other optimizations.  The
+       first case needs to be identified by passing TRUNC as the value
+       of ShiftOp so that shift amount is properly handled according to the
+       SHIFT_COUNT_TRUNCATED flag.  For the second case, the shift
+       amount is always truncated by the bytesize of the mode of
+       THIS.  */
+    TRUNC
+  };

I think I have expressed my opinion on this.  (and SHIFT_COUNT_TRUNCATED
should vanish - certainly wide-int shouldn't care, so doesn't double-int)

+  enum SignOp {
+    /* Many of the math functions produce different results depending
+       on if they are SIGNED or UNSIGNED.  In general, there are two
+       different functions, whose names are prefixed with an 'S" and
+       or an 'U'.  However, for some math functions there is also a
+       routine that does not have the prefix and takes an SignOp
+       parameter of SIGNED or UNSIGNED.  */
+    SIGNED,
+    UNSIGNED
+  };

See above.  GCC standard practice is a 'unsigned uns' parameter.

+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type);
+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type,
+                                  bool *overflow);
+  inline static wide_int from_shwi (HOST_WIDE_INT op0, enum machine_mode mode);
+  inline static wide_int from_shwi (HOST_WIDE_INT op0, enum machine_mode mode,
+                                   bool *overflow);
+  inline static wide_int from_uhwi (unsigned HOST_WIDE_INT op0,
+                                   enum machine_mode mode);
+  inline static wide_int from_uhwi (unsigned HOST_WIDE_INT op0,
+                                   enum machine_mode mode,
+                                   bool *overflow);

way too many overloads.  Besides the "raw" ones I only expect wide-ints
to be constructed from a tree INTEGER_CST or a rtx DOUBLE_INT.

+  inline static wide_int minus_one (unsigned int bitsize, unsigned int prec);
+  inline static wide_int minus_one (const_tree type);
+  inline static wide_int minus_one (enum machine_mode mode);
+  inline static wide_int minus_one (const wide_int &op1);

wide-ints representation should be properly sign-extended, thus all of the
possible -1 variants have the same representation.  If it were not for
providing precision and bitsize for which you have the four overloads.
Just have one.  Providing precision (or bitsize).

I see that for example in wide_int::add bitsize and precision are arbitrarily
copied from the first operand.  With the present way of dealing with them
it would sound more logical to assert that they are the same for both
operands (do both need to match?).  I'd rather see wide-int being
"arbitrary" precision/bitsize up to its supported storage size (as
double-int is).
I suppose we've been there and discussed this to death already though ;)
As you have some fused operation plus sign-/zero-extend ops already
the alternative is to always provide a precision for the result and treat the
operands as "arbitrary" precision (that way wide_int::minus_one can
simply return a sign-extended precision 1 -1).

Btw, wide_int::add does not look at bitsize at all, so it clearly is redundant
information.  Grepping for uses of bitsize shows up only maintaining and
copying around this information as well.  please remove bitsize.

Ok, enough for today.

Thanks,
Richard.

> kenny
>

On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
<zadeck@naturalbridge.com> wrote:
> This patch contains a large number of the changes requested by Richi.   It
> does not contain any of the changes that he requested to abstract the
> storage layer.   That suggestion appears to be quite unworkable.

I of course took this claim as a challenge ... with the following result.  It is
of course quite workable ;)

The attached patch implements the core wide-int class and three storage
models (fixed size for things like plain HWI and double-int, variable size
similar to how your wide-int works and an adaptor for the double-int as
contained in trees).  With that you can now do

HOST_WIDE_INT
wi_test (tree x)
{
  // template argument deduction doesn't do the magic we want it to do
  // to make this kind of implicit conversions work
  // overload resolution considers this kind of conversions so we
  // need some magic that combines both ... but seeding the overload
  // set with some instantiations doesn't seem to be possible :/
  // wide_int<> w = x + 1;
  wide_int<> w;
  w += x;
  w += 1;
  // template argument deduction doesn't deduce the return value type,
  // not considering the template default argument either ...
  // w = wi (x) + 1;
  // we could support this by providing rvalue-to-lvalue promotion
  // via a traits class?
  // otoh it would lead to sub-optimal code anyway so we should
  // make the result available as reference parameter and only support
  // wide_int <> res; add (res, x, 1); ?
  w = wi (x).operator+<wide_int<> >(1);
  wide_int<>::add(w, x, 1);
  return w.to_hwi ();
}

we are somewhat limited with C++ unless we want to get really fancy.
Eventually providing operator+ just doesn't make much sense for
generic wide-int combinations (though then the issue is its operands
are no longer commutative which I think is the case with your wide-int
or double-int as well - they don't suport "1 + wide_int" for obvious reasons).

So there are implementation design choices left undecided.

Oh, and the operation implementations are crap (they compute nonsense).

But you should get the idea.

Richard.

Yes, I agree that you win the challenge that it can be done.    What you 
have always failed to address is why anyone would want to do this.  Or 
how this would at all be desirable.    But I completely agree that from 
a purely abstract point of view you can add a storage model.

Now here is why we REALLY do not want to go down this road:

1)  The following comment from your earlier mail is completely wrong

> +#ifdef NEW_REP_FOR_INT_CST
> +  /* This is the code once the tree level is converted.  */
> +  wide_int result;
> +  int i;
> +
> +  tree type = TREE_TYPE (tcst);
> +
> +  result.bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
> +  result.precision = TYPE_PRECISION (type);
> +  result.len = TREE_INT_CST_LEN (tcst);
> +  for (i = 0; i < result.len; i++)
> +    result.val[i] = TREE_INT_CST_ELT (tcst, i);
> +
> +  return result;
> +#else

> this also shows the main reason I was asking for storage abstraction.
> The initialization from tree is way too expensive.

In almost all cases, constants will fit in a single HWI.  Thus, the only 
thing that you are copying is the length and a single HWI. So you are 
dragging in a lot of machinery just to save these two copies?   
Certainly there has to be more to it than that.

2)  You present this as if the implementor actually should care about 
the implementation and you give 3 alternatives:  the double_int, the 
current one, and HWI.     We have tried to make it so that the client 
should not care.   Certainly in my experience here, I have not found a 
place to care.

In my opinion double_int needs to go away.  That is the main thrust of 
my patches.   There is no place in a compiler for an abi that depends on 
constants fitting into 2 two words whose size is defined by the host.    
This is not a beauty contest argument, we have public ports are 
beginning to use modes that are larger than two x86-64 HWIs and i have a 
private port that has such modes and it is my experience that any pass 
that uses this interface has one of three behaviors: it silently gets 
the wrong answer, it ices, or it fails to do the transformation.  If we 
leave double_int as an available option, then any use of it potentially 
will have one of these three behaviors.  And so one of my strong 
objections to this direction is that i do not want to fight this kind of 
bug for the rest of my life.    Having a single storage model that just 
always works is in my opinion a highly desirable option.  What you have 
never answered in a concrete manner is, if we decide to provide this 
generality, what it would be used for.    There is no place in a 
portable compiler where the right answer for every target is two HOST 
wide integers.

However, i will admit that the HWI option has some merits.   We try to 
address this in our implementation by dividing what is done inline in 
wide-int.h to the cases that fit in an HWI and then only drop into the 
heavy code in wide-int.c if mode is larger (which it rarely will be).   
However, a case could be made that for certain kinds of things like 
string lengths and such, we could use another interface or as you argue, 
a different storage model with the same interface.   I just do not see 
that the cost of the conversion code is really going to show up on 
anyone's radar.

3) your trick will work at the tree level, but not at the rtl level.   
The wide-int code cannot share storage with the CONST_INTs.    We tried 
this, and there are a million bugs that would have to be fixed to make 
it work.    It could have worked if CONST_INTs had carried a mode 
around, but since they do not, you end up with the same CONST_INT 
sharing the rep for several different types and that just did not work 
unless you are willing to do substantial cleanups.

On 04/02/2013 11:04 AM, Richard Biener wrote:
> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
> <zadeck@naturalbridge.com> wrote:
>> This patch contains a large number of the changes requested by Richi.   It
>> does not contain any of the changes that he requested to abstract the
>> storage layer.   That suggestion appears to be quite unworkable.
> I of course took this claim as a challenge ... with the following result.  It is
> of course quite workable ;)
>
> The attached patch implements the core wide-int class and three storage
> models (fixed size for things like plain HWI and double-int, variable size
> similar to how your wide-int works and an adaptor for the double-int as
> contained in trees).  With that you can now do
>
> HOST_WIDE_INT
> wi_test (tree x)
> {
>    // template argument deduction doesn't do the magic we want it to do
>    // to make this kind of implicit conversions work
>    // overload resolution considers this kind of conversions so we
>    // need some magic that combines both ... but seeding the overload
>    // set with some instantiations doesn't seem to be possible :/
>    // wide_int<> w = x + 1;
>    wide_int<> w;
>    w += x;
>    w += 1;
>    // template argument deduction doesn't deduce the return value type,
>    // not considering the template default argument either ...
>    // w = wi (x) + 1;
>    // we could support this by providing rvalue-to-lvalue promotion
>    // via a traits class?
>    // otoh it would lead to sub-optimal code anyway so we should
>    // make the result available as reference parameter and only support
>    // wide_int <> res; add (res, x, 1); ?
>    w = wi (x).operator+<wide_int<> >(1);
>    wide_int<>::add(w, x, 1);
>    return w.to_hwi ();
> }
>
> we are somewhat limited with C++ unless we want to get really fancy.
> Eventually providing operator+ just doesn't make much sense for
> generic wide-int combinations (though then the issue is its operands
> are no longer commutative which I think is the case with your wide-int
> or double-int as well - they don't suport "1 + wide_int" for obvious reasons).
>
> So there are implementation design choices left undecided.
>
> Oh, and the operation implementations are crap (they compute nonsense).
>
> But you should get the idea.
>
> Richard.

On Tue, Apr 2, 2013 at 7:35 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Yes, I agree that you win the challenge that it can be done.    What you
> have always failed to address is why anyone would want to do this.  Or how
> this would at all be desirable.    But I completely agree that from a purely
> abstract point of view you can add a storage model.
>
> Now here is why we REALLY do not want to go down this road:
>
> 1)  The following comment from your earlier mail is completely wrong
>
>
>> +#ifdef NEW_REP_FOR_INT_CST
>> +  /* This is the code once the tree level is converted.  */
>> +  wide_int result;
>> +  int i;
>> +
>> +  tree type = TREE_TYPE (tcst);
>> +
>> +  result.bitsize = GET_MODE_BITSIZE (TYPE_MODE (type));
>> +  result.precision = TYPE_PRECISION (type);
>> +  result.len = TREE_INT_CST_LEN (tcst);
>> +  for (i = 0; i < result.len; i++)
>> +    result.val[i] = TREE_INT_CST_ELT (tcst, i);
>> +
>> +  return result;
>> +#else
>
>
>> this also shows the main reason I was asking for storage abstraction.
>> The initialization from tree is way too expensive.
>
>
> In almost all cases, constants will fit in a single HWI.  Thus, the only
> thing that you are copying is the length and a single HWI. So you are
> dragging in a lot of machinery just to save these two copies?   Certainly
> there has to be more to it than that.

In the end you will have a variable-size storage in TREE_INT_CST thus
you will have at least to emit _code_ copying over meta-data and data
from the tree representation to the wide-int (similar for RTX CONST_DOUBLE/INT).
I'm objecting to the amount of code you emit and agree that the runtime
cost is copying the meta-data (hopefully optimizable via CSE / SRA)
and in most cases one (or two) iterations of the loop copying the data
(not optimizable).

> 2)  You present this as if the implementor actually should care about the
> implementation and you give 3 alternatives:  the double_int, the current
> one, and HWI.     We have tried to make it so that the client should not
> care.   Certainly in my experience here, I have not found a place to care.

Well, similar as for the copying overhead for tree your approach requires
overloading operations for HOST_WIDE_INT operands to be able to
say wi + 1 (which is certainly desirable), or the overhead of using
wide_int_one ().

> In my opinion double_int needs to go away.  That is the main thrust of my
> patches.   There is no place in a compiler for an abi that depends on
> constants fitting into 2 two words whose size is defined by the host.

That's true.  I'm not arguing to preserve "double-int" - I'm arguing to
preserve a way to ask for an integer type on the host with (at least)
N bits.  Almost all double-int users really ask for an integer type on the
host that has at least as many bits as the pointer representation (or
word_mode) on
the target (we do have HOST_WIDEST_INT == 32bits for 64bit pointer
targets).  No double-int user specifically wants 2 * HOST_WIDE_INT
precision - that is just what happens to be there.  Thus I am providing
a way to say get me a host integer with at least N bits (VRP asks for
this, for example).

What I was asking for is that whatever can provide the above should share
the functional interface with wide-int (or the othert way around).  And I
was claiming that wide-int is too fat, because current users of double-int
eventually store double-ints permanently.

> This is not a beauty contest argument, we have public ports are beginning to
> use modes that are larger than two x86-64 HWIs and i have a private port
> that has such modes and it is my experience that any pass that uses this
> interface has one of three behaviors: it silently gets the wrong answer, it
> ices, or it fails to do the transformation.  If we leave double_int as an
> available option, then any use of it potentially will have one of these
> three behaviors.  And so one of my strong objections to this direction is
> that i do not want to fight this kind of bug for the rest of my life.
> Having a single storage model that just always works is in my opinion a
> highly desirable option.  What you have never answered in a concrete manner
> is, if we decide to provide this generality, what it would be used for.
> There is no place in a portable compiler where the right answer for every
> target is two HOST wide integers.
>
> However, i will admit that the HWI option has some merits.   We try to
> address this in our implementation by dividing what is done inline in
> wide-int.h to the cases that fit in an HWI and then only drop into the heavy
> code in wide-int.c if mode is larger (which it rarely will be).   However, a
> case could be made that for certain kinds of things like string lengths and
> such, we could use another interface or as you argue, a different storage
> model with the same interface.   I just do not see that the cost of the
> conversion code is really going to show up on anyone's radar.

What's the issue with abstracting away the model so a fixed-size 'len'
is possible?  (let away the argument that this would easily allow an
adaptor to tree)

> 3) your trick will work at the tree level, but not at the rtl level.   The
> wide-int code cannot share storage with the CONST_INTs.    We tried this,
> and there are a million bugs that would have to be fixed to make it work.
> It could have worked if CONST_INTs had carried a mode around, but since they
> do not, you end up with the same CONST_INT sharing the rep for several
> different types and that just did not work unless you are willing to do
> substantial cleanups.

I don't believe you.  I am only asking for the adaptors to tree and RTL to
work in an RVALUE-ish way (no modification, as obviously RTL and tree
constants may be shared).  I think your claim is because you have that
precision and bitsize members in your wide-int which I believe is a
design red herring.  I suppose we should concentrate on addressing that
one first.  Thus, let me repeat a few questions on your design to eventually
let you understand my concerns:

Given two wide-ints, a and b, what precision will the result of
     a + b
have?  Consider a having precision 32 and b having precision 64
on a 32-bit HWI host.

You define wide-int to have no sign information:

+   The representation does not contain any information about
+   signedness of the represented value, so it can be used to represent
+   both signed and unsigned numbers.  For operations where the results
+   depend on signedness (division, comparisons), the signedness must
+   be specified separately.  For operations where the signness
+   matters, one of the operands to the operation specifies either
+   wide_int::SIGNED or wide_int::UNSIGNED.

but the result of operations on mixed precision operands _does_ depend
on the sign, nevertheless most operations do not get a signedness argument.
Nor would that help, because it depends on the signedness of the individual
operands!

double-int get's around this by having a common "precision" to which
all smaller precision constants have to be sign-/zero-extended.  So
does CONST_INT and CONST_DOUBLE.

Note that even with same precision you have introduced the same problem
with the variable len.

My proposal is simple - all wide-ints are signed!  wide-int is basically
an arbitrary precision signed integer format.  The sign is encoded in
the most significant bit of the last active HWI of the representation
(val[len - 1] & (1 << HOST_BITS_PER_WIDE_INT - 1)).  All values
with less precision than len * HOST_BITS_PER_WIDE_INT are
properly sign-/zero-extended to precision len * HOST_BITS_PER_WIDE_INT.

This let's you define mixed len operations by implicitely sign-/zero-extending
the operands to whatever len is required for the operation.

Furthermore it allows you to get rid of the precision member (and
bitsize anyway).
Conversion from tree / RTL requires information on the signedness of the
input (trivial for tree, for RTL all constants are signed - well,
sign-extended).
Whenever you want to transfer the wide-int to tree / RTL you have to
sign-/zero-extend according to the desired precision.  If you need sth else
than arbitrary precision arithmetic you have to explicitely truncate / extend
at suitable places - with overflow checking being trivial here.  For
optimization
purposes selected operations may benefit from a combined implementation
receiving a target precision and signedness.  Whatever extra meta-data
RTL requires does not belong in wide-int but in the RTX.  Trivially
a mode comes to my mind (on tree we have a type), and trivially
each RTX has a mode.  And each mode has a precision and bitsize.
It lacks a sign, so all RTL integer constants are sign-extended for
encoding efficiency purposes.  mixed-mode operations will not
occur (mixed len operations will), mixed-mode ops are exclusively
sign-/zero-extensions and truncations.

Representation of (unsigned HOST_WIDE_INT)-1 would necessarily
be { 0, (unsigned HOST_WIDE_INT)-1 }, representation of -1 in any
precision would be { -1 }.

That was my proposal.  Now, can you please properly specify yours?

Thanks,
Richard.

>
> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>
>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>> <zadeck@naturalbridge.com> wrote:
>>>
>>> This patch contains a large number of the changes requested by Richi.
>>> It
>>> does not contain any of the changes that he requested to abstract the
>>> storage layer.   That suggestion appears to be quite unworkable.
>>
>> I of course took this claim as a challenge ... with the following result.
>> It is
>> of course quite workable ;)
>>
>> The attached patch implements the core wide-int class and three storage
>> models (fixed size for things like plain HWI and double-int, variable size
>> similar to how your wide-int works and an adaptor for the double-int as
>> contained in trees).  With that you can now do
>>
>> HOST_WIDE_INT
>> wi_test (tree x)
>> {
>>    // template argument deduction doesn't do the magic we want it to do
>>    // to make this kind of implicit conversions work
>>    // overload resolution considers this kind of conversions so we
>>    // need some magic that combines both ... but seeding the overload
>>    // set with some instantiations doesn't seem to be possible :/
>>    // wide_int<> w = x + 1;
>>    wide_int<> w;
>>    w += x;
>>    w += 1;
>>    // template argument deduction doesn't deduce the return value type,
>>    // not considering the template default argument either ...
>>    // w = wi (x) + 1;
>>    // we could support this by providing rvalue-to-lvalue promotion
>>    // via a traits class?
>>    // otoh it would lead to sub-optimal code anyway so we should
>>    // make the result available as reference parameter and only support
>>    // wide_int <> res; add (res, x, 1); ?
>>    w = wi (x).operator+<wide_int<> >(1);
>>    wide_int<>::add(w, x, 1);
>>    return w.to_hwi ();
>> }
>>
>> we are somewhat limited with C++ unless we want to get really fancy.
>> Eventually providing operator+ just doesn't make much sense for
>> generic wide-int combinations (though then the issue is its operands
>> are no longer commutative which I think is the case with your wide-int
>> or double-int as well - they don't suport "1 + wide_int" for obvious
>> reasons).
>>
>> So there are implementation design choices left undecided.
>>
>> Oh, and the operation implementations are crap (they compute nonsense).
>>
>> But you should get the idea.
>>
>> Richard.
>
>

On 04/03/2013 05:17 AM, Richard Biener wrote:

> In the end you will have a variable-size storage in TREE_INT_CST thus
> you will have at least to emit _code_ copying over meta-data and data
> from the tree representation to the wide-int (similar for RTX CONST_DOUBLE/INT).
> I'm objecting to the amount of code you emit and agree that the runtime
> cost is copying the meta-data (hopefully optimizable via CSE / SRA)
> and in most cases one (or two) iterations of the loop copying the data
> (not optimizable).
i did get rid of the bitsize in the wide-int patch so at this point the 
meta data is the precision and the len.
not really a lot here.   As usual we pay a high price in gcc for not 
pushing the tree rep down into the rtl level, then it would have been 
acceptable to have the tree type bleed into the wide-int code.


>> 2)  You present this as if the implementor actually should care about the
>> implementation and you give 3 alternatives:  the double_int, the current
>> one, and HWI.     We have tried to make it so that the client should not
>> care.   Certainly in my experience here, I have not found a place to care.
> Well, similar as for the copying overhead for tree your approach requires
> overloading operations for HOST_WIDE_INT operands to be able to
> say wi + 1 (which is certainly desirable), or the overhead of using
> wide_int_one ().
>
>> In my opinion double_int needs to go away.  That is the main thrust of my
>> patches.   There is no place in a compiler for an abi that depends on
>> constants fitting into 2 two words whose size is defined by the host.
> That's true.  I'm not arguing to preserve "double-int" - I'm arguing to
> preserve a way to ask for an integer type on the host with (at least)
> N bits.  Almost all double-int users really ask for an integer type on the
> host that has at least as many bits as the pointer representation (or
> word_mode) on
> the target (we do have HOST_WIDEST_INT == 32bits for 64bit pointer
> targets).  No double-int user specifically wants 2 * HOST_WIDE_INT
> precision - that is just what happens to be there.  Thus I am providing
> a way to say get me a host integer with at least N bits (VRP asks for
> this, for example).
>
> What I was asking for is that whatever can provide the above should share
> the functional interface with wide-int (or the othert way around).  And I
> was claiming that wide-int is too fat, because current users of double-int
> eventually store double-ints permanently.
The problem is that, in truth, double int is too fat. 99.something% of 
all constants fit in 1 hwi and that is likely to be true forever (i 
understand that tree vpn may need some thought here).  The rtl level, 
which has, for as long as i have known it, had 2 reps for integer 
constants. So it was relatively easy to slide the CONST_WIDE_INT in.  It 
seems like the right trickery here rather than adding a storage model 
for wide-ints might be a way to use the c++ to invisibly support several 
(and by "several" i really mean 2) classes of TREE_CSTs.

>
>> This is not a beauty contest argument, we have public ports are beginning to
>> use modes that are larger than two x86-64 HWIs and i have a private port
>> that has such modes and it is my experience that any pass that uses this
>> interface has one of three behaviors: it silently gets the wrong answer, it
>> ices, or it fails to do the transformation.  If we leave double_int as an
>> available option, then any use of it potentially will have one of these
>> three behaviors.  And so one of my strong objections to this direction is
>> that i do not want to fight this kind of bug for the rest of my life.
>> Having a single storage model that just always works is in my opinion a
>> highly desirable option.  What you have never answered in a concrete manner
>> is, if we decide to provide this generality, what it would be used for.
>> There is no place in a portable compiler where the right answer for every
>> target is two HOST wide integers.
>>
>> However, i will admit that the HWI option has some merits.   We try to
>> address this in our implementation by dividing what is done inline in
>> wide-int.h to the cases that fit in an HWI and then only drop into the heavy
>> code in wide-int.c if mode is larger (which it rarely will be).   However, a
>> case could be made that for certain kinds of things like string lengths and
>> such, we could use another interface or as you argue, a different storage
>> model with the same interface.   I just do not see that the cost of the
>> conversion code is really going to show up on anyone's radar.
> What's the issue with abstracting away the model so a fixed-size 'len'
> is possible?  (let away the argument that this would easily allow an
> adaptor to tree)
I have a particularly pessimistic perspective because i have already 
written most of this patch.   It is not that i do not want to change 
that code, it is that i have seen a certain set of mistakes that were 
made and i do not want to fix them more than once.   At the rtl level 
you can see the transition from only supporting 32 bit ints to 
supporting 64 bit its to finally supporting two HWIs and that transition 
code is not pretty.  My rtl patch fixes the places where an optimization 
was only made if the data type was 32 bits or smaller as well as the 
places where the optimization was made only if the data type is smaller 
than 64 bits (in addition to fixing all of the places where the code 
ices or simply gets the wrong answer if it is larger than TImode.)  The 
tree level is only modestly better, I believe only because it is newer. 
I have not seen any 32 bit only code, but it is littered with 
transformations that only work for 64 bits.   What is that 64 bit only 
code going to look like in 5 years?

I want to make it easier to write the general code than to write the 
code that only solves the problem for the size port that the implementor 
is currently working on.   So I perceive the storage model as a way to 
keep having to fight this battle forever because it will allow the 
implementor to make a decision that the optimization only needs to be 
done for a particular sized integer.

However, i get the fact that from your perspective, what you really want 
is a solution to the data structure problem in tree-vrp.  My patch for 
tree vrp scans the entire function to find the largest type used in the 
function and then does all of the math at 2x that size.  But i have to 
admit that i thought it was weird that you use tree cst as your long 
term storage.   If this were my pass, i would have allocated a 2d array 
of some type that was as large as the function in 1d and twice as large 
as the largest int used in the other dimension and not overloaded 
tree-cst and then had a set of friend functions in double int to get in 
and out. Of course you do not need friends in double int because the rep 
is exposed, but in wide-int that is now hidden since it now is purely 
functional.

I just have to believe that there is a better way to do tree-vrp than 
messing up wide-int for the rest of the compiler.

>> 3) your trick will work at the tree level, but not at the rtl level.   The
>> wide-int code cannot share storage with the CONST_INTs.    We tried this,
>> and there are a million bugs that would have to be fixed to make it work.
>> It could have worked if CONST_INTs had carried a mode around, but since they
>> do not, you end up with the same CONST_INT sharing the rep for several
>> different types and that just did not work unless you are willing to do
>> substantial cleanups.
> I don't believe you.  I am only asking for the adaptors to tree and RTL to
> work in an RVALUE-ish way (no modification, as obviously RTL and tree
> constants may be shared).  I think your claim is because you have that
> precision and bitsize members in your wide-int which I believe is a
> design red herring.  I suppose we should concentrate on addressing that
> one first.  Thus, let me repeat a few questions on your design to eventually
> let you understand my concerns:
>
> Given two wide-ints, a and b, what precision will the result of
>       a + b
> have?  Consider a having precision 32 and b having precision 64
> on a 32-bit HWI host.
>
> You define wide-int to have no sign information:
>
> +   The representation does not contain any information about
> +   signedness of the represented value, so it can be used to represent
> +   both signed and unsigned numbers.  For operations where the results
> +   depend on signedness (division, comparisons), the signedness must
> +   be specified separately.  For operations where the signness
> +   matters, one of the operands to the operation specifies either
> +   wide_int::SIGNED or wide_int::UNSIGNED.
>
> but the result of operations on mixed precision operands _does_ depend
> on the sign, nevertheless most operations do not get a signedness argument.
> Nor would that help, because it depends on the signedness of the individual
> operands!
>
> double-int get's around this by having a common "precision" to which
> all smaller precision constants have to be sign-/zero-extended.  So
> does CONST_INT and CONST_DOUBLE.
>
> Note that even with same precision you have introduced the same problem
> with the variable len.
>
> My proposal is simple - all wide-ints are signed!  wide-int is basically
> an arbitrary precision signed integer format.  The sign is encoded in
> the most significant bit of the last active HWI of the representation
> (val[len - 1] & (1 << HOST_BITS_PER_WIDE_INT - 1)).  All values
> with less precision than len * HOST_BITS_PER_WIDE_INT are
> properly sign-/zero-extended to precision len * HOST_BITS_PER_WIDE_INT.
>
> This let's you define mixed len operations by implicitely sign-/zero-extending
> the operands to whatever len is required for the operation.
>
> Furthermore it allows you to get rid of the precision member (and
> bitsize anyway).
> Conversion from tree / RTL requires information on the signedness of the
> input (trivial for tree, for RTL all constants are signed - well,
> sign-extended).
> Whenever you want to transfer the wide-int to tree / RTL you have to
> sign-/zero-extend according to the desired precision.  If you need sth else
> than arbitrary precision arithmetic you have to explicitely truncate / extend
> at suitable places - with overflow checking being trivial here.  For
> optimization
> purposes selected operations may benefit from a combined implementation
> receiving a target precision and signedness.  Whatever extra meta-data
> RTL requires does not belong in wide-int but in the RTX.  Trivially
> a mode comes to my mind (on tree we have a type), and trivially
> each RTX has a mode.  And each mode has a precision and bitsize.
> It lacks a sign, so all RTL integer constants are sign-extended for
> encoding efficiency purposes.  mixed-mode operations will not
> occur (mixed len operations will), mixed-mode ops are exclusively
> sign-/zero-extensions and truncations.
>
> Representation of (unsigned HOST_WIDE_INT)-1 would necessarily
> be { 0, (unsigned HOST_WIDE_INT)-1 }, representation of -1 in any
> precision would be { -1 }.
>
> That was my proposal.  Now, can you please properly specify yours?
>
> Thanks,
> Richard.
>
>> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>>> <zadeck@naturalbridge.com> wrote:
>>>> This patch contains a large number of the changes requested by Richi.
>>>> It
>>>> does not contain any of the changes that he requested to abstract the
>>>> storage layer.   That suggestion appears to be quite unworkable.
>>> I of course took this claim as a challenge ... with the following result.
>>> It is
>>> of course quite workable ;)
>>>
>>> The attached patch implements the core wide-int class and three storage
>>> models (fixed size for things like plain HWI and double-int, variable size
>>> similar to how your wide-int works and an adaptor for the double-int as
>>> contained in trees).  With that you can now do
>>>
>>> HOST_WIDE_INT
>>> wi_test (tree x)
>>> {
>>>     // template argument deduction doesn't do the magic we want it to do
>>>     // to make this kind of implicit conversions work
>>>     // overload resolution considers this kind of conversions so we
>>>     // need some magic that combines both ... but seeding the overload
>>>     // set with some instantiations doesn't seem to be possible :/
>>>     // wide_int<> w = x + 1;
>>>     wide_int<> w;
>>>     w += x;
>>>     w += 1;
>>>     // template argument deduction doesn't deduce the return value type,
>>>     // not considering the template default argument either ...
>>>     // w = wi (x) + 1;
>>>     // we could support this by providing rvalue-to-lvalue promotion
>>>     // via a traits class?
>>>     // otoh it would lead to sub-optimal code anyway so we should
>>>     // make the result available as reference parameter and only support
>>>     // wide_int <> res; add (res, x, 1); ?
>>>     w = wi (x).operator+<wide_int<> >(1);
>>>     wide_int<>::add(w, x, 1);
>>>     return w.to_hwi ();
>>> }
>>>
>>> we are somewhat limited with C++ unless we want to get really fancy.
>>> Eventually providing operator+ just doesn't make much sense for
>>> generic wide-int combinations (though then the issue is its operands
>>> are no longer commutative which I think is the case with your wide-int
>>> or double-int as well - they don't suport "1 + wide_int" for obvious
>>> reasons).
>>>
>>> So there are implementation design choices left undecided.
>>>
>>> Oh, and the operation implementations are crap (they compute nonsense).
>>>
>>> But you should get the idea.
>>>
>>> Richard.
>>

On Wed, Apr 3, 2013 at 2:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
> On 04/03/2013 05:17 AM, Richard Biener wrote:
>
>> In the end you will have a variable-size storage in TREE_INT_CST thus
>> you will have at least to emit _code_ copying over meta-data and data
>> from the tree representation to the wide-int (similar for RTX
>> CONST_DOUBLE/INT).
>> I'm objecting to the amount of code you emit and agree that the runtime
>> cost is copying the meta-data (hopefully optimizable via CSE / SRA)
>> and in most cases one (or two) iterations of the loop copying the data
>> (not optimizable).
>
> i did get rid of the bitsize in the wide-int patch so at this point the meta
> data is the precision and the len.
> not really a lot here.   As usual we pay a high price in gcc for not pushing
> the tree rep down into the rtl level, then it would have been acceptable to
> have the tree type bleed into the wide-int code.
>
>
>
>>> 2)  You present this as if the implementor actually should care about the
>>> implementation and you give 3 alternatives:  the double_int, the current
>>> one, and HWI.     We have tried to make it so that the client should not
>>> care.   Certainly in my experience here, I have not found a place to
>>> care.
>>
>> Well, similar as for the copying overhead for tree your approach requires
>> overloading operations for HOST_WIDE_INT operands to be able to
>> say wi + 1 (which is certainly desirable), or the overhead of using
>> wide_int_one ().
>>
>>> In my opinion double_int needs to go away.  That is the main thrust of my
>>> patches.   There is no place in a compiler for an abi that depends on
>>> constants fitting into 2 two words whose size is defined by the host.
>>
>> That's true.  I'm not arguing to preserve "double-int" - I'm arguing to
>> preserve a way to ask for an integer type on the host with (at least)
>> N bits.  Almost all double-int users really ask for an integer type on the
>> host that has at least as many bits as the pointer representation (or
>> word_mode) on
>> the target (we do have HOST_WIDEST_INT == 32bits for 64bit pointer
>> targets).  No double-int user specifically wants 2 * HOST_WIDE_INT
>> precision - that is just what happens to be there.  Thus I am providing
>> a way to say get me a host integer with at least N bits (VRP asks for
>> this, for example).
>>
>> What I was asking for is that whatever can provide the above should share
>> the functional interface with wide-int (or the othert way around).  And I
>> was claiming that wide-int is too fat, because current users of double-int
>> eventually store double-ints permanently.
>
> The problem is that, in truth, double int is too fat. 99.something% of all
> constants fit in 1 hwi and that is likely to be true forever (i understand
> that tree vpn may need some thought here).  The rtl level, which has, for as
> long as i have known it, had 2 reps for integer constants. So it was
> relatively easy to slide the CONST_WIDE_INT in.  It seems like the right
> trickery here rather than adding a storage model for wide-ints might be a
> way to use the c++ to invisibly support several (and by "several" i really
> mean 2) classes of TREE_CSTs.

The truth is that _now_ TREE_INT_CSTs use double-ints and we have
CONST_INT and CONST_DOUBLE.  What I (and you) propose would
get us to use variable-size storage for both, allowing to just use a single
HOST_WIDE_INT in the majority of cases.  In my view the constant
length of the variable-size storage for TREE_INT_CSTs is determined
by its type (thus, it doesn't have "optimized" variable-size storage
but "unoptimized" fixed-size storage based on the maximum storage
requirement for the type).  Similar for RTX CONST_INT which would
have fixed-size storage based on the mode-size of the constant.
Using optimized space (thus using the encoding properties) requires you
to fit the 'short len' somewhere which possibly will not pay off in the end
(for tree we do have that storage available, so we could go with optimized
storage for it, not sure with RTL, I don't see available space there).

>>> This is not a beauty contest argument, we have public ports are beginning
>>> to
>>> use modes that are larger than two x86-64 HWIs and i have a private port
>>> that has such modes and it is my experience that any pass that uses this
>>> interface has one of three behaviors: it silently gets the wrong answer,
>>> it
>>> ices, or it fails to do the transformation.  If we leave double_int as an
>>> available option, then any use of it potentially will have one of these
>>> three behaviors.  And so one of my strong objections to this direction is
>>> that i do not want to fight this kind of bug for the rest of my life.
>>> Having a single storage model that just always works is in my opinion a
>>> highly desirable option.  What you have never answered in a concrete
>>> manner
>>> is, if we decide to provide this generality, what it would be used for.
>>> There is no place in a portable compiler where the right answer for every
>>> target is two HOST wide integers.
>>>
>>> However, i will admit that the HWI option has some merits.   We try to
>>> address this in our implementation by dividing what is done inline in
>>> wide-int.h to the cases that fit in an HWI and then only drop into the
>>> heavy
>>> code in wide-int.c if mode is larger (which it rarely will be).
>>> However, a
>>> case could be made that for certain kinds of things like string lengths
>>> and
>>> such, we could use another interface or as you argue, a different storage
>>> model with the same interface.   I just do not see that the cost of the
>>> conversion code is really going to show up on anyone's radar.
>>
>> What's the issue with abstracting away the model so a fixed-size 'len'
>> is possible?  (let away the argument that this would easily allow an
>> adaptor to tree)
>
> I have a particularly pessimistic perspective because i have already written
> most of this patch.   It is not that i do not want to change that code, it
> is that i have seen a certain set of mistakes that were made and i do not
> want to fix them more than once.   At the rtl level you can see the
> transition from only supporting 32 bit ints to supporting 64 bit its to
> finally supporting two HWIs and that transition code is not pretty.  My rtl
> patch fixes the places where an optimization was only made if the data type
> was 32 bits or smaller as well as the places where the optimization was made
> only if the data type is smaller than 64 bits (in addition to fixing all of
> the places where the code ices or simply gets the wrong answer if it is
> larger than TImode.)  The tree level is only modestly better, I believe only
> because it is newer. I have not seen any 32 bit only code, but it is
> littered with transformations that only work for 64 bits.   What is that 64
> bit only code going to look like in 5 years?

The user interface of wide-int does not depend on whether a storage model
is abstracted or not.  If you take advantage of the storage model by
making its interface leaner then it will.  But I guess converting everything
before settling on the wide-int interface may not have been the wisest
choice in the end (providing a wide-int that can literally replace double-int
would have got you testing coverage without any change besides
double-int.[ch] and wide-int.[ch]).

> I want to make it easier to write the general code than to write the code
> that only solves the problem for the size port that the implementor is
> currently working on.   So I perceive the storage model as a way to keep
> having to fight this battle forever because it will allow the implementor to
> make a decision that the optimization only needs to be done for a particular
> sized integer.
>
> However, i get the fact that from your perspective, what you really want is
> a solution to the data structure problem in tree-vrp.

No, that's just a convenient example.  What I really want is a wide-int
that is less visibly a replacement for CONST_DOUBLE.

>  My patch for tree vrp
> scans the entire function to find the largest type used in the function and
> then does all of the math at 2x that size.  But i have to admit that i
> thought it was weird that you use tree cst as your long term storage.   If
> this were my pass, i would have allocated a 2d array of some type that was
> as large as the function in 1d and twice as large as the largest int used in
> the other dimension and not overloaded tree-cst and then had a set of friend
> functions in double int to get in and out. Of course you do not need friends
> in double int because the rep is exposed, but in wide-int that is now hidden
> since it now is purely functional.
>
> I just have to believe that there is a better way to do tree-vrp than
> messing up wide-int for the rest of the compiler.

It's not "messing up", it's making wide-int a generally useful thing and
not tying it so closely to RTL.

>>> 3) your trick will work at the tree level, but not at the rtl level.
>>> The
>>> wide-int code cannot share storage with the CONST_INTs.    We tried this,
>>> and there are a million bugs that would have to be fixed to make it work.
>>> It could have worked if CONST_INTs had carried a mode around, but since
>>> they
>>> do not, you end up with the same CONST_INT sharing the rep for several
>>> different types and that just did not work unless you are willing to do
>>> substantial cleanups.
>>
>> I don't believe you.  I am only asking for the adaptors to tree and RTL to
>> work in an RVALUE-ish way (no modification, as obviously RTL and tree
>> constants may be shared).  I think your claim is because you have that
>> precision and bitsize members in your wide-int which I believe is a
>> design red herring.  I suppose we should concentrate on addressing that
>> one first.  Thus, let me repeat a few questions on your design to
>> eventually
>> let you understand my concerns:
>>
>> Given two wide-ints, a and b, what precision will the result of
>>       a + b
>> have?  Consider a having precision 32 and b having precision 64
>> on a 32-bit HWI host.
>>
>> You define wide-int to have no sign information:
>>
>> +   The representation does not contain any information about
>> +   signedness of the represented value, so it can be used to represent
>> +   both signed and unsigned numbers.  For operations where the results
>> +   depend on signedness (division, comparisons), the signedness must
>> +   be specified separately.  For operations where the signness
>> +   matters, one of the operands to the operation specifies either
>> +   wide_int::SIGNED or wide_int::UNSIGNED.
>>
>> but the result of operations on mixed precision operands _does_ depend
>> on the sign, nevertheless most operations do not get a signedness
>> argument.
>> Nor would that help, because it depends on the signedness of the
>> individual
>> operands!
>>
>> double-int get's around this by having a common "precision" to which
>> all smaller precision constants have to be sign-/zero-extended.  So
>> does CONST_INT and CONST_DOUBLE.
>>
>> Note that even with same precision you have introduced the same problem
>> with the variable len.
>>
>> My proposal is simple - all wide-ints are signed!  wide-int is basically
>> an arbitrary precision signed integer format.  The sign is encoded in
>> the most significant bit of the last active HWI of the representation
>> (val[len - 1] & (1 << HOST_BITS_PER_WIDE_INT - 1)).  All values
>> with less precision than len * HOST_BITS_PER_WIDE_INT are
>> properly sign-/zero-extended to precision len * HOST_BITS_PER_WIDE_INT.
>>
>> This let's you define mixed len operations by implicitely
>> sign-/zero-extending
>> the operands to whatever len is required for the operation.
>>
>> Furthermore it allows you to get rid of the precision member (and
>> bitsize anyway).
>> Conversion from tree / RTL requires information on the signedness of the
>> input (trivial for tree, for RTL all constants are signed - well,
>> sign-extended).
>> Whenever you want to transfer the wide-int to tree / RTL you have to
>> sign-/zero-extend according to the desired precision.  If you need sth
>> else
>> than arbitrary precision arithmetic you have to explicitely truncate /
>> extend
>> at suitable places - with overflow checking being trivial here.  For
>> optimization
>> purposes selected operations may benefit from a combined implementation
>> receiving a target precision and signedness.  Whatever extra meta-data
>> RTL requires does not belong in wide-int but in the RTX.  Trivially
>> a mode comes to my mind (on tree we have a type), and trivially
>> each RTX has a mode.  And each mode has a precision and bitsize.
>> It lacks a sign, so all RTL integer constants are sign-extended for
>> encoding efficiency purposes.  mixed-mode operations will not
>> occur (mixed len operations will), mixed-mode ops are exclusively
>> sign-/zero-extensions and truncations.
>>
>> Representation of (unsigned HOST_WIDE_INT)-1 would necessarily
>> be { 0, (unsigned HOST_WIDE_INT)-1 }, representation of -1 in any
>> precision would be { -1 }.
>>
>> That was my proposal.  Now, can you please properly specify yours?

And you chose to not answer that fundamental question of how your
wide-int is _supposed_ to work?  Ok, maybe I shouldn't have distracted
you with the bits before this.

Richard.

>> Thanks,
>> Richard.
>>
>>> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>>>
>>>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>>>> <zadeck@naturalbridge.com> wrote:
>>>>>
>>>>> This patch contains a large number of the changes requested by Richi.
>>>>> It
>>>>> does not contain any of the changes that he requested to abstract the
>>>>> storage layer.   That suggestion appears to be quite unworkable.
>>>>
>>>> I of course took this claim as a challenge ... with the following
>>>> result.
>>>> It is
>>>> of course quite workable ;)
>>>>
>>>> The attached patch implements the core wide-int class and three storage
>>>> models (fixed size for things like plain HWI and double-int, variable
>>>> size
>>>> similar to how your wide-int works and an adaptor for the double-int as
>>>> contained in trees).  With that you can now do
>>>>
>>>> HOST_WIDE_INT
>>>> wi_test (tree x)
>>>> {
>>>>     // template argument deduction doesn't do the magic we want it to do
>>>>     // to make this kind of implicit conversions work
>>>>     // overload resolution considers this kind of conversions so we
>>>>     // need some magic that combines both ... but seeding the overload
>>>>     // set with some instantiations doesn't seem to be possible :/
>>>>     // wide_int<> w = x + 1;
>>>>     wide_int<> w;
>>>>     w += x;
>>>>     w += 1;
>>>>     // template argument deduction doesn't deduce the return value type,
>>>>     // not considering the template default argument either ...
>>>>     // w = wi (x) + 1;
>>>>     // we could support this by providing rvalue-to-lvalue promotion
>>>>     // via a traits class?
>>>>     // otoh it would lead to sub-optimal code anyway so we should
>>>>     // make the result available as reference parameter and only support
>>>>     // wide_int <> res; add (res, x, 1); ?
>>>>     w = wi (x).operator+<wide_int<> >(1);
>>>>     wide_int<>::add(w, x, 1);
>>>>     return w.to_hwi ();
>>>> }
>>>>
>>>> we are somewhat limited with C++ unless we want to get really fancy.
>>>> Eventually providing operator+ just doesn't make much sense for
>>>> generic wide-int combinations (though then the issue is its operands
>>>> are no longer commutative which I think is the case with your wide-int
>>>> or double-int as well - they don't suport "1 + wide_int" for obvious
>>>> reasons).
>>>>
>>>> So there are implementation design choices left undecided.
>>>>
>>>> Oh, and the operation implementations are crap (they compute nonsense).
>>>>
>>>> But you should get the idea.
>>>>
>>>> Richard.
>>>
>>>
>

On 04/03/2013 09:53 AM, Richard Biener wrote:
> On Wed, Apr 3, 2013 at 2:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>> On 04/03/2013 05:17 AM, Richard Biener wrote:
>>
>>> In the end you will have a variable-size storage in TREE_INT_CST thus
>>> you will have at least to emit _code_ copying over meta-data and data
>>> from the tree representation to the wide-int (similar for RTX
>>> CONST_DOUBLE/INT).
>>> I'm objecting to the amount of code you emit and agree that the runtime
>>> cost is copying the meta-data (hopefully optimizable via CSE / SRA)
>>> and in most cases one (or two) iterations of the loop copying the data
>>> (not optimizable).
>> i did get rid of the bitsize in the wide-int patch so at this point the meta
>> data is the precision and the len.
>> not really a lot here.   As usual we pay a high price in gcc for not pushing
>> the tree rep down into the rtl level, then it would have been acceptable to
>> have the tree type bleed into the wide-int code.
>>
>>
>>
>>>> 2)  You present this as if the implementor actually should care about the
>>>> implementation and you give 3 alternatives:  the double_int, the current
>>>> one, and HWI.     We have tried to make it so that the client should not
>>>> care.   Certainly in my experience here, I have not found a place to
>>>> care.
>>> Well, similar as for the copying overhead for tree your approach requires
>>> overloading operations for HOST_WIDE_INT operands to be able to
>>> say wi + 1 (which is certainly desirable), or the overhead of using
>>> wide_int_one ().
>>>
>>>> In my opinion double_int needs to go away.  That is the main thrust of my
>>>> patches.   There is no place in a compiler for an abi that depends on
>>>> constants fitting into 2 two words whose size is defined by the host.
>>> That's true.  I'm not arguing to preserve "double-int" - I'm arguing to
>>> preserve a way to ask for an integer type on the host with (at least)
>>> N bits.  Almost all double-int users really ask for an integer type on the
>>> host that has at least as many bits as the pointer representation (or
>>> word_mode) on
>>> the target (we do have HOST_WIDEST_INT == 32bits for 64bit pointer
>>> targets).  No double-int user specifically wants 2 * HOST_WIDE_INT
>>> precision - that is just what happens to be there.  Thus I am providing
>>> a way to say get me a host integer with at least N bits (VRP asks for
>>> this, for example).
>>>
>>> What I was asking for is that whatever can provide the above should share
>>> the functional interface with wide-int (or the othert way around).  And I
>>> was claiming that wide-int is too fat, because current users of double-int
>>> eventually store double-ints permanently.
>> The problem is that, in truth, double int is too fat. 99.something% of all
>> constants fit in 1 hwi and that is likely to be true forever (i understand
>> that tree vpn may need some thought here).  The rtl level, which has, for as
>> long as i have known it, had 2 reps for integer constants. So it was
>> relatively easy to slide the CONST_WIDE_INT in.  It seems like the right
>> trickery here rather than adding a storage model for wide-ints might be a
>> way to use the c++ to invisibly support several (and by "several" i really
>> mean 2) classes of TREE_CSTs.
> The truth is that _now_ TREE_INT_CSTs use double-ints and we have
> CONST_INT and CONST_DOUBLE.  What I (and you) propose would
> get us to use variable-size storage for both, allowing to just use a single
> HOST_WIDE_INT in the majority of cases.  In my view the constant
> length of the variable-size storage for TREE_INT_CSTs is determined
> by its type (thus, it doesn't have "optimized" variable-size storage
> but "unoptimized" fixed-size storage based on the maximum storage
> requirement for the type).  Similar for RTX CONST_INT which would
> have fixed-size storage based on the mode-size of the constant.
> Using optimized space (thus using the encoding properties) requires you
> to fit the 'short len' somewhere which possibly will not pay off in the end
> (for tree we do have that storage available, so we could go with optimized
> storage for it, not sure with RTL, I don't see available space there).
There are two questions here:   one is the fact that you object to the 
fact that we represent small constants efficiently and the second is 
that we take advantage of the fact that fixed size stack allocation is 
effectively free for short lived objects like wide-ints (as i use them).

At the rtl level your idea does not work.   rtl constants do not have a 
mode or type.    So if you do not compress, how are you going to 
determine how many words you need for the constant 1.   I would love to 
have a rep that had the mode in it.    But it is a huge change that 
requires a lot of hacking to every port.

I understand that this makes me vulnerable to the argument that we 
should not let the rtl level ever dictate anything about the tree level, 
but the truth is that a variable len rep is almost always used for big 
integers.   In our code, most constants of large types are small 
numbers.   (Remember i got into this because the tree constant prop 
thinks that left shifting any number by anything greater than 128 is 
always 0 and discovered that that was just the tip of the iceberg.) But 
mostly i support the decision to canonize numbers to the smallest number 
of HWIs because most of the algorithms to do the math can be short 
circuited.    I admit that if i had to effectively unpack most numbers 
to do the math, that the canonization would be a waste.   However, this 
is not really relevant to this conversation.   Yes, you could get rid of 
the len, but this such a small part of picture.

Furthermore, I am constrained at the rtl level because it is just too 
dirty to share the storage.   We tried that and the amount of whack a 
mole we were playing was killing us.

I am comfortable making big changes at the portable level because i can 
easily test them, but changes to fundamental data structures inside 
every port is more than i am willing to do.   If you are going to do 
that, then you are going to have start giving rtl constants modes and 
that is a huge change (that while desirable i cannot do).

At the tree level you could share the storage, I admit that that is 
easy, i just do not think that it is desirable.  The stack allocation 
inside the wide-int is very cheap and the fact that the number that 
comes out is almost always one hwi makes this very efficient.   Even if 
I was starting from scratch this would be a strong contender to be the 
right representation.

Fundamentally, i do not believe that the amount of copying that i am 
proposing at the tree level will be significant.  Yes, if you force me 
to use an uncompressed format you can make what i propose expensive.

>>>> This is not a beauty contest argument, we have public ports are beginning
>>>> to
>>>> use modes that are larger than two x86-64 HWIs and i have a private port
>>>> that has such modes and it is my experience that any pass that uses this
>>>> interface has one of three behaviors: it silently gets the wrong answer,
>>>> it
>>>> ices, or it fails to do the transformation.  If we leave double_int as an
>>>> available option, then any use of it potentially will have one of these
>>>> three behaviors.  And so one of my strong objections to this direction is
>>>> that i do not want to fight this kind of bug for the rest of my life.
>>>> Having a single storage model that just always works is in my opinion a
>>>> highly desirable option.  What you have never answered in a concrete
>>>> manner
>>>> is, if we decide to provide this generality, what it would be used for.
>>>> There is no place in a portable compiler where the right answer for every
>>>> target is two HOST wide integers.
>>>>
>>>> However, i will admit that the HWI option has some merits.   We try to
>>>> address this in our implementation by dividing what is done inline in
>>>> wide-int.h to the cases that fit in an HWI and then only drop into the
>>>> heavy
>>>> code in wide-int.c if mode is larger (which it rarely will be).
>>>> However, a
>>>> case could be made that for certain kinds of things like string lengths
>>>> and
>>>> such, we could use another interface or as you argue, a different storage
>>>> model with the same interface.   I just do not see that the cost of the
>>>> conversion code is really going to show up on anyone's radar.
>>> What's the issue with abstracting away the model so a fixed-size 'len'
>>> is possible?  (let away the argument that this would easily allow an
>>> adaptor to tree)
>> I have a particularly pessimistic perspective because i have already written
>> most of this patch.   It is not that i do not want to change that code, it
>> is that i have seen a certain set of mistakes that were made and i do not
>> want to fix them more than once.   At the rtl level you can see the
>> transition from only supporting 32 bit ints to supporting 64 bit its to
>> finally supporting two HWIs and that transition code is not pretty.  My rtl
>> patch fixes the places where an optimization was only made if the data type
>> was 32 bits or smaller as well as the places where the optimization was made
>> only if the data type is smaller than 64 bits (in addition to fixing all of
>> the places where the code ices or simply gets the wrong answer if it is
>> larger than TImode.)  The tree level is only modestly better, I believe only
>> because it is newer. I have not seen any 32 bit only code, but it is
>> littered with transformations that only work for 64 bits.   What is that 64
>> bit only code going to look like in 5 years?
> The user interface of wide-int does not depend on whether a storage model
> is abstracted or not.  If you take advantage of the storage model by
> making its interface leaner then it will.  But I guess converting everything
> before settling on the wide-int interface may not have been the wisest
> choice in the end (providing a wide-int that can literally replace double-int
> would have got you testing coverage without any change besides
> double-int.[ch] and wide-int.[ch]).
I think that it was exactly the correct decision.   We have made 
significant changes to the structure as we have gone along.   I have 
basically done most of what you have suggested, (the interface is 
completely functional, i got rid of the bitsize...)   What you are 
running into is that mike stump, richard sandiford and myself actually 
believe that the storage model is a fundamentally bad idea.

>> I want to make it easier to write the general code than to write the code
>> that only solves the problem for the size port that the implementor is
>> currently working on.   So I perceive the storage model as a way to keep
>> having to fight this battle forever because it will allow the implementor to
>> make a decision that the optimization only needs to be done for a particular
>> sized integer.
>>
>> However, i get the fact that from your perspective, what you really want is
>> a solution to the data structure problem in tree-vrp.
> No, that's just a convenient example.  What I really want is a wide-int
> that is less visibly a replacement for CONST_DOUBLE.
I think that that is unfair.   Variable length reps are the standard 
technique for doing wide math.  I am just proposing using data 
structures that are common best practices in the rest of the world and 
adapting them so that they match the gcc world better than just hacking 
in a gmp interface.
>
>>   My patch for tree vrp
>> scans the entire function to find the largest type used in the function and
>> then does all of the math at 2x that size.  But i have to admit that i
>> thought it was weird that you use tree cst as your long term storage.   If
>> this were my pass, i would have allocated a 2d array of some type that was
>> as large as the function in 1d and twice as large as the largest int used in
>> the other dimension and not overloaded tree-cst and then had a set of friend
>> functions in double int to get in and out. Of course you do not need friends
>> in double int because the rep is exposed, but in wide-int that is now hidden
>> since it now is purely functional.
>>
>> I just have to believe that there is a better way to do tree-vrp than
>> messing up wide-int for the rest of the compiler.
> It's not "messing up", it's making wide-int a generally useful thing and
> not tying it so closely to RTL.
Again, this is unfair.
>
>>>> 3) your trick will work at the tree level, but not at the rtl level.
>>>> The
>>>> wide-int code cannot share storage with the CONST_INTs.    We tried this,
>>>> and there are a million bugs that would have to be fixed to make it work.
>>>> It could have worked if CONST_INTs had carried a mode around, but since
>>>> they
>>>> do not, you end up with the same CONST_INT sharing the rep for several
>>>> different types and that just did not work unless you are willing to do
>>>> substantial cleanups.
>>> I don't believe you.  I am only asking for the adaptors to tree and RTL to
>>> work in an RVALUE-ish way (no modification, as obviously RTL and tree
>>> constants may be shared).  I think your claim is because you have that
>>> precision and bitsize members in your wide-int which I believe is a
>>> design red herring.  I suppose we should concentrate on addressing that
>>> one first.  Thus, let me repeat a few questions on your design to
>>> eventually
>>> let you understand my concerns:
>>>
>>> Given two wide-ints, a and b, what precision will the result of
>>>        a + b
>>> have?  Consider a having precision 32 and b having precision 64
>>> on a 32-bit HWI host.
>>>
>>> You define wide-int to have no sign information:
>>>
>>> +   The representation does not contain any information about
>>> +   signedness of the represented value, so it can be used to represent
>>> +   both signed and unsigned numbers.  For operations where the results
>>> +   depend on signedness (division, comparisons), the signedness must
>>> +   be specified separately.  For operations where the signness
>>> +   matters, one of the operands to the operation specifies either
>>> +   wide_int::SIGNED or wide_int::UNSIGNED.
>>>
>>> but the result of operations on mixed precision operands _does_ depend
>>> on the sign, nevertheless most operations do not get a signedness
>>> argument.
>>> Nor would that help, because it depends on the signedness of the
>>> individual
>>> operands!
>>>
>>> double-int get's around this by having a common "precision" to which
>>> all smaller precision constants have to be sign-/zero-extended.  So
>>> does CONST_INT and CONST_DOUBLE.
>>>
>>> Note that even with same precision you have introduced the same problem
>>> with the variable len.
>>>
>>> My proposal is simple - all wide-ints are signed!  wide-int is basically
>>> an arbitrary precision signed integer format.  The sign is encoded in
>>> the most significant bit of the last active HWI of the representation
>>> (val[len - 1] & (1 << HOST_BITS_PER_WIDE_INT - 1)).  All values
>>> with less precision than len * HOST_BITS_PER_WIDE_INT are
>>> properly sign-/zero-extended to precision len * HOST_BITS_PER_WIDE_INT.
>>>
>>> This let's you define mixed len operations by implicitely
>>> sign-/zero-extending
>>> the operands to whatever len is required for the operation.
>>>
>>> Furthermore it allows you to get rid of the precision member (and
>>> bitsize anyway).
>>> Conversion from tree / RTL requires information on the signedness of the
>>> input (trivial for tree, for RTL all constants are signed - well,
>>> sign-extended).
>>> Whenever you want to transfer the wide-int to tree / RTL you have to
>>> sign-/zero-extend according to the desired precision.  If you need sth
>>> else
>>> than arbitrary precision arithmetic you have to explicitely truncate /
>>> extend
>>> at suitable places - with overflow checking being trivial here.  For
>>> optimization
>>> purposes selected operations may benefit from a combined implementation
>>> receiving a target precision and signedness.  Whatever extra meta-data
>>> RTL requires does not belong in wide-int but in the RTX.  Trivially
>>> a mode comes to my mind (on tree we have a type), and trivially
>>> each RTX has a mode.  And each mode has a precision and bitsize.
>>> It lacks a sign, so all RTL integer constants are sign-extended for
>>> encoding efficiency purposes.  mixed-mode operations will not
>>> occur (mixed len operations will), mixed-mode ops are exclusively
>>> sign-/zero-extensions and truncations.
>>>
>>> Representation of (unsigned HOST_WIDE_INT)-1 would necessarily
>>> be { 0, (unsigned HOST_WIDE_INT)-1 }, representation of -1 in any
>>> precision would be { -1 }.
>>>
>>> That was my proposal.  Now, can you please properly specify yours?
> And you chose to not answer that fundamental question of how your
> wide-int is _supposed_ to work?  Ok, maybe I shouldn't have distracted
> you with the bits before this.
sorry, i missed this question by accident.

we did not do infinite precision by design.   We looked at the set of 
programming languages that gcc either compiles or might compile and we 
looked at the set of machines that gcc targets and neither of these two 
sets of entities define their operations in terms of infinite precision 
math.   They always do math within a particular precision.    Scripting 
languages do use infinite precision but gcc does not compile any of 
them.   So unless you are going to restrict your set of operations to 
those that satisfy the properties of a ring, it is generally not 
strictly safe to do your math in infinite precision.

we do all of the math in the precision defined by the types or modes 
that are passed in.

constants are defined to be the size of the precision unless they can be 
compressed.   The len field tells how many words are actually needed to 
exactly represent the constant if (len-1)*HOST_WIDE_BITS_PER_WIDE_INT is 
less than the precision. The decompression process is to add a number of 
words to the high order side of the number.   These words must contain a 
zero if the highest represented bit is 0 and -1 if the highest 
represented bit is 1.

i.e. this looks a lot like sign extension, but the numbers them selves 
are not inherently signed or unsigned as in your representation.    It 
is up to the operators to imply the signess. So the unsigned multiply 
operation is different than the signed multiply operation.    But these 
are applied to the bits without an interpretation of their sign.

> Richard.
>
>>> Thanks,
>>> Richard.
>>>
>>>> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>>>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>>>>> <zadeck@naturalbridge.com> wrote:
>>>>>> This patch contains a large number of the changes requested by Richi.
>>>>>> It
>>>>>> does not contain any of the changes that he requested to abstract the
>>>>>> storage layer.   That suggestion appears to be quite unworkable.
>>>>> I of course took this claim as a challenge ... with the following
>>>>> result.
>>>>> It is
>>>>> of course quite workable ;)
>>>>>
>>>>> The attached patch implements the core wide-int class and three storage
>>>>> models (fixed size for things like plain HWI and double-int, variable
>>>>> size
>>>>> similar to how your wide-int works and an adaptor for the double-int as
>>>>> contained in trees).  With that you can now do
>>>>>
>>>>> HOST_WIDE_INT
>>>>> wi_test (tree x)
>>>>> {
>>>>>      // template argument deduction doesn't do the magic we want it to do
>>>>>      // to make this kind of implicit conversions work
>>>>>      // overload resolution considers this kind of conversions so we
>>>>>      // need some magic that combines both ... but seeding the overload
>>>>>      // set with some instantiations doesn't seem to be possible :/
>>>>>      // wide_int<> w = x + 1;
>>>>>      wide_int<> w;
>>>>>      w += x;
>>>>>      w += 1;
>>>>>      // template argument deduction doesn't deduce the return value type,
>>>>>      // not considering the template default argument either ...
>>>>>      // w = wi (x) + 1;
>>>>>      // we could support this by providing rvalue-to-lvalue promotion
>>>>>      // via a traits class?
>>>>>      // otoh it would lead to sub-optimal code anyway so we should
>>>>>      // make the result available as reference parameter and only support
>>>>>      // wide_int <> res; add (res, x, 1); ?
>>>>>      w = wi (x).operator+<wide_int<> >(1);
>>>>>      wide_int<>::add(w, x, 1);
>>>>>      return w.to_hwi ();
>>>>> }
>>>>>
>>>>> we are somewhat limited with C++ unless we want to get really fancy.
>>>>> Eventually providing operator+ just doesn't make much sense for
>>>>> generic wide-int combinations (though then the issue is its operands
>>>>> are no longer commutative which I think is the case with your wide-int
>>>>> or double-int as well - they don't suport "1 + wide_int" for obvious
>>>>> reasons).
>>>>>
>>>>> So there are implementation design choices left undecided.
>>>>>
>>>>> Oh, and the operation implementations are crap (they compute nonsense).
>>>>>
>>>>> But you should get the idea.
>>>>>
>>>>> Richard.
>>>>

On Wed, Apr 3, 2013 at 6:16 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> On 04/03/2013 09:53 AM, Richard Biener wrote:
>>
>> On Wed, Apr 3, 2013 at 2:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com>
>> wrote:
>>>
>>> On 04/03/2013 05:17 AM, Richard Biener wrote:
>>>
>>>> In the end you will have a variable-size storage in TREE_INT_CST thus
>>>> you will have at least to emit _code_ copying over meta-data and data
>>>> from the tree representation to the wide-int (similar for RTX
>>>> CONST_DOUBLE/INT).
>>>> I'm objecting to the amount of code you emit and agree that the runtime
>>>> cost is copying the meta-data (hopefully optimizable via CSE / SRA)
>>>> and in most cases one (or two) iterations of the loop copying the data
>>>> (not optimizable).
>>>
>>> i did get rid of the bitsize in the wide-int patch so at this point the
>>> meta
>>> data is the precision and the len.
>>> not really a lot here.   As usual we pay a high price in gcc for not
>>> pushing
>>> the tree rep down into the rtl level, then it would have been acceptable
>>> to
>>> have the tree type bleed into the wide-int code.
>>>
>>>
>>>
>>>>> 2)  You present this as if the implementor actually should care about
>>>>> the
>>>>> implementation and you give 3 alternatives:  the double_int, the
>>>>> current
>>>>> one, and HWI.     We have tried to make it so that the client should
>>>>> not
>>>>> care.   Certainly in my experience here, I have not found a place to
>>>>> care.
>>>>
>>>> Well, similar as for the copying overhead for tree your approach
>>>> requires
>>>> overloading operations for HOST_WIDE_INT operands to be able to
>>>> say wi + 1 (which is certainly desirable), or the overhead of using
>>>> wide_int_one ().
>>>>
>>>>> In my opinion double_int needs to go away.  That is the main thrust of
>>>>> my
>>>>> patches.   There is no place in a compiler for an abi that depends on
>>>>> constants fitting into 2 two words whose size is defined by the host.
>>>>
>>>> That's true.  I'm not arguing to preserve "double-int" - I'm arguing to
>>>> preserve a way to ask for an integer type on the host with (at least)
>>>> N bits.  Almost all double-int users really ask for an integer type on
>>>> the
>>>> host that has at least as many bits as the pointer representation (or
>>>> word_mode) on
>>>> the target (we do have HOST_WIDEST_INT == 32bits for 64bit pointer
>>>> targets).  No double-int user specifically wants 2 * HOST_WIDE_INT
>>>> precision - that is just what happens to be there.  Thus I am providing
>>>> a way to say get me a host integer with at least N bits (VRP asks for
>>>> this, for example).
>>>>
>>>> What I was asking for is that whatever can provide the above should
>>>> share
>>>> the functional interface with wide-int (or the othert way around).  And
>>>> I
>>>> was claiming that wide-int is too fat, because current users of
>>>> double-int
>>>> eventually store double-ints permanently.
>>>
>>> The problem is that, in truth, double int is too fat. 99.something% of
>>> all
>>> constants fit in 1 hwi and that is likely to be true forever (i
>>> understand
>>> that tree vpn may need some thought here).  The rtl level, which has, for
>>> as
>>> long as i have known it, had 2 reps for integer constants. So it was
>>> relatively easy to slide the CONST_WIDE_INT in.  It seems like the right
>>> trickery here rather than adding a storage model for wide-ints might be a
>>> way to use the c++ to invisibly support several (and by "several" i
>>> really
>>> mean 2) classes of TREE_CSTs.
>>
>> The truth is that _now_ TREE_INT_CSTs use double-ints and we have
>> CONST_INT and CONST_DOUBLE.  What I (and you) propose would
>> get us to use variable-size storage for both, allowing to just use a
>> single
>> HOST_WIDE_INT in the majority of cases.  In my view the constant
>> length of the variable-size storage for TREE_INT_CSTs is determined
>> by its type (thus, it doesn't have "optimized" variable-size storage
>> but "unoptimized" fixed-size storage based on the maximum storage
>> requirement for the type).  Similar for RTX CONST_INT which would
>> have fixed-size storage based on the mode-size of the constant.
>> Using optimized space (thus using the encoding properties) requires you
>> to fit the 'short len' somewhere which possibly will not pay off in the
>> end
>> (for tree we do have that storage available, so we could go with optimized
>> storage for it, not sure with RTL, I don't see available space there).
>
> There are two questions here:   one is the fact that you object to the fact
> that we represent small constants efficiently

Huh?  Where do I object to that?  I question that for the storage in tree
and RTX the encoding trick pays off if you need another HWI-aligned
word to store the len.  But see below.

> and the second is that we take
> advantage of the fact that fixed size stack allocation is effectively free
> for short lived objects like wide-ints (as i use them).

I don't question that and I am not asking you to change that.  As part of
what I ask for a more optimal (smaller) stack allocation would be _possible_
(but not required).

> At the rtl level your idea does not work.   rtl constants do not have a mode
> or type.    So if you do not compress, how are you going to determine how
> many words you need for the constant 1.   I would love to have a rep that
> had the mode in it.    But it is a huge change that requires a lot of
> hacking to every port.

Quoting from your RTL parts patch:

+struct GTY((variable_size)) hwivec_def {
+  int num_elem;                /* number of elements */
+  HOST_WIDE_INT elem[1];
+};
+
+#define HWI_GET_NUM_ELEM(HWIVEC)       ((HWIVEC)->num_elem)
+#define HWI_PUT_NUM_ELEM(HWIVEC, NUM)  ((HWIVEC)->num_elem = (NUM))
+
 /* RTL expression ("rtx").  */

 struct GTY((chain_next ("RTX_NEXT (&%h)"),
@@ -343,6 +352,7 @@ struct GTY((chain_next ("RTX_NEXT (&%h)"),
     struct block_symbol block_sym;
     struct real_value rv;
     struct fixed_value fv;
+    struct hwivec_def hwiv;
   } GTY ((special ("rtx_def"), desc ("GET_CODE (&%0)"))) u;
 };

that 'wastes' one HOST_WIDE_INT.  So the most efficient encoding
of 0 will require two HOST_WIDE_INT size storage.  Same as for
double-int currently.  99.9% of all constants will fit into two
HOST_WIDE_INTs, thus having the variable size encoding for
the storage in RTX (as opposed to having num_elem == GET_MODE_BITSIZE
/ HOST_BITS_PER_WIDE_INT) is a waste of time.  num_elem
for a non-optimized encoding is available from the mode stored in
the integer constant RTX...

You say

> At the rtl level your idea does not work.   rtl constants do not have a mode
> or type.

Which is not true and does not matter.  I tell you why.  Quote:

+#if TARGET_SUPPORTS_WIDE_INT
+
+/* Match CONST_*s that can represent compile-time constant integers.  */
+#define CASE_CONST_SCALAR_INT \
+   case CONST_INT: \
+   case CONST_WIDE_INT

which means you are only replacing CONST_DOUBLE with wide-int.
And _all_ CONST_DOUBLE have a mode.  Otherwise you'd have no
way of creating the wide-int in the first place.  Which means any
future transition of CONST_INT to the wide-int code (which is desirable!)
will need to fix the fact that CONST_INTs do not have a mode.
Or even simpler - just retain CONST_INT behavior!  CONST_INTs
need a single HWI storage (moving that to wide-int with a len field
regresses here) and CONST_INTs are always sign-extended.
Preserve that!  Make VOIDmode integer constants have a single
HWI as storage, sign-extended.

> I understand that this makes me vulnerable to the argument that we should
> not let the rtl level ever dictate anything about the tree level, but the
> truth is that a variable len rep is almost always used for big integers.
> In our code, most constants of large types are small numbers.   (Remember i
> got into this because the tree constant prop thinks that left shifting any
> number by anything greater than 128 is always 0 and discovered that that was
> just the tip of the iceberg.) But mostly i support the decision to canonize
> numbers to the smallest number of HWIs because most of the algorithms to do
> the math can be short circuited.    I admit that if i had to effectively
> unpack most numbers to do the math, that the canonization would be a waste.
> However, this is not really relevant to this conversation.   Yes, you could
> get rid of the len, but this such a small part of picture.

Getting rid of 'len' in the RTX storage was only a question of whether it
is an efficient way to go forward.  And with considering to unify
CONST_INTs and CONST_WIDE_INTs it is not.  And even for CONST_WIDE_INTs
(which most of the time would be 2 HWI storage, as otherwise you'd use
a CONST_INT) it would be an improvement.

> Furthermore, I am constrained at the rtl level because it is just too dirty
> to share the storage.   We tried that and the amount of whack a mole we were
> playing was killing us.

The above argument (not encode len explicitely in the RTX) is unrelated
to "sharing the storage" (whatever you exactly refer to here).

> I am comfortable making big changes at the portable level because i can
> easily test them, but changes to fundamental data structures inside every
> port is more than i am willing to do.   If you are going to do that, then
> you are going to have start giving rtl constants modes and that is a huge
> change (that while desirable i cannot do).

All CONST_DOUBLEs have modes.  You do not touch CONST_INTs.
VOIDmode CONST_WIDE_INTs seem perfectly possible to me (see above).
So nothing to fix, even if that is desirable as you say and as I agree.

> At the tree level you could share the storage, I admit that that is easy, i
> just do not think that it is desirable.  The stack allocation inside the
> wide-int is very cheap and the fact that the number that comes out is almost
> always one hwi makes this very efficient.   Even if I was starting from
> scratch this would be a strong contender to be the right representation.
>
> Fundamentally, i do not believe that the amount of copying that i am
> proposing at the tree level will be significant.  Yes, if you force me to
> use an uncompressed format you can make what i propose expensive.

An uncompressed format at tree / RTX will in 99.9% of all cases be
one or two HWIs.  Realize that all my arguments and requests are
really independent (even though I make them together).

As we now have the power of C++ and templates I see no good reason
to not do the optimization of eliding the copying from the RTX / tree
representation.  It can be done as a followup I guess (with the disadvantage
of leaving the possibility to "optimize" existing converted client code).

Btw, is the current state of the patches accessible as a branch somewhere?

>>>>> This is not a beauty contest argument, we have public ports are
>>>>> beginning
>>>>> to
>>>>> use modes that are larger than two x86-64 HWIs and i have a private
>>>>> port
>>>>> that has such modes and it is my experience that any pass that uses
>>>>> this
>>>>> interface has one of three behaviors: it silently gets the wrong
>>>>> answer,
>>>>> it
>>>>> ices, or it fails to do the transformation.  If we leave double_int as
>>>>> an
>>>>> available option, then any use of it potentially will have one of these
>>>>> three behaviors.  And so one of my strong objections to this direction
>>>>> is
>>>>> that i do not want to fight this kind of bug for the rest of my life.
>>>>> Having a single storage model that just always works is in my opinion a
>>>>> highly desirable option.  What you have never answered in a concrete
>>>>> manner
>>>>> is, if we decide to provide this generality, what it would be used for.
>>>>> There is no place in a portable compiler where the right answer for
>>>>> every
>>>>> target is two HOST wide integers.
>>>>>
>>>>> However, i will admit that the HWI option has some merits.   We try to
>>>>> address this in our implementation by dividing what is done inline in
>>>>> wide-int.h to the cases that fit in an HWI and then only drop into the
>>>>> heavy
>>>>> code in wide-int.c if mode is larger (which it rarely will be).
>>>>> However, a
>>>>> case could be made that for certain kinds of things like string lengths
>>>>> and
>>>>> such, we could use another interface or as you argue, a different
>>>>> storage
>>>>> model with the same interface.   I just do not see that the cost of the
>>>>> conversion code is really going to show up on anyone's radar.
>>>>
>>>> What's the issue with abstracting away the model so a fixed-size 'len'
>>>> is possible?  (let away the argument that this would easily allow an
>>>> adaptor to tree)
>>>
>>> I have a particularly pessimistic perspective because i have already
>>> written
>>> most of this patch.   It is not that i do not want to change that code,
>>> it
>>> is that i have seen a certain set of mistakes that were made and i do not
>>> want to fix them more than once.   At the rtl level you can see the
>>> transition from only supporting 32 bit ints to supporting 64 bit its to
>>> finally supporting two HWIs and that transition code is not pretty.  My
>>> rtl
>>> patch fixes the places where an optimization was only made if the data
>>> type
>>> was 32 bits or smaller as well as the places where the optimization was
>>> made
>>> only if the data type is smaller than 64 bits (in addition to fixing all
>>> of
>>> the places where the code ices or simply gets the wrong answer if it is
>>> larger than TImode.)  The tree level is only modestly better, I believe
>>> only
>>> because it is newer. I have not seen any 32 bit only code, but it is
>>> littered with transformations that only work for 64 bits.   What is that
>>> 64
>>> bit only code going to look like in 5 years?
>>
>> The user interface of wide-int does not depend on whether a storage model
>> is abstracted or not.  If you take advantage of the storage model by
>> making its interface leaner then it will.  But I guess converting
>> everything
>> before settling on the wide-int interface may not have been the wisest
>> choice in the end (providing a wide-int that can literally replace
>> double-int
>> would have got you testing coverage without any change besides
>> double-int.[ch] and wide-int.[ch]).
>
> I think that it was exactly the correct decision.   We have made significant
> changes to the structure as we have gone along.   I have basically done most
> of what you have suggested, (the interface is completely functional, i got
> rid of the bitsize...)   What you are running into is that mike stump,
> richard sandiford and myself actually believe that the storage model is a
> fundamentally bad idea.

Well, that must be because of C++ ignorance.  Let's keep that issue
aside for now.  Be sure I'll come back to it.

>>> I want to make it easier to write the general code than to write the code
>>> that only solves the problem for the size port that the implementor is
>>> currently working on.   So I perceive the storage model as a way to keep
>>> having to fight this battle forever because it will allow the implementor
>>> to
>>> make a decision that the optimization only needs to be done for a
>>> particular
>>> sized integer.
>>>
>>> However, i get the fact that from your perspective, what you really want
>>> is
>>> a solution to the data structure problem in tree-vrp.
>>
>> No, that's just a convenient example.  What I really want is a wide-int
>> that is less visibly a replacement for CONST_DOUBLE.
>
> I think that that is unfair.   Variable length reps are the standard
> technique for doing wide math.  I am just proposing using data structures
> that are common best practices in the rest of the world and adapting them so
> that they match the gcc world better than just hacking in a gmp interface.

I don't object to variable-length reps.  I question the need of 'bitsize'
(gone! yay!) and now 'precision' in class wide_int.  I question the need
and efficiency of encoding 'len' in RTX CONST_WIDE_INT.

>>>   My patch for tree vrp
>>> scans the entire function to find the largest type used in the function
>>> and
>>> then does all of the math at 2x that size.  But i have to admit that i
>>> thought it was weird that you use tree cst as your long term storage.
>>> If
>>> this were my pass, i would have allocated a 2d array of some type that
>>> was
>>> as large as the function in 1d and twice as large as the largest int used
>>> in
>>> the other dimension and not overloaded tree-cst and then had a set of
>>> friend
>>> functions in double int to get in and out. Of course you do not need
>>> friends
>>> in double int because the rep is exposed, but in wide-int that is now
>>> hidden
>>> since it now is purely functional.
>>>
>>> I just have to believe that there is a better way to do tree-vrp than
>>> messing up wide-int for the rest of the compiler.
>>
>> It's not "messing up", it's making wide-int a generally useful thing and
>> not tying it so closely to RTL.
>
> Again, this is unfair.
>
>>
>>>>> 3) your trick will work at the tree level, but not at the rtl level.
>>>>> The
>>>>> wide-int code cannot share storage with the CONST_INTs.    We tried
>>>>> this,
>>>>> and there are a million bugs that would have to be fixed to make it
>>>>> work.
>>>>> It could have worked if CONST_INTs had carried a mode around, but since
>>>>> they
>>>>> do not, you end up with the same CONST_INT sharing the rep for several
>>>>> different types and that just did not work unless you are willing to do
>>>>> substantial cleanups.
>>>>
>>>> I don't believe you.  I am only asking for the adaptors to tree and RTL
>>>> to
>>>> work in an RVALUE-ish way (no modification, as obviously RTL and tree
>>>> constants may be shared).  I think your claim is because you have that
>>>> precision and bitsize members in your wide-int which I believe is a
>>>> design red herring.  I suppose we should concentrate on addressing that
>>>> one first.  Thus, let me repeat a few questions on your design to
>>>> eventually
>>>> let you understand my concerns:
>>>>
>>>> Given two wide-ints, a and b, what precision will the result of
>>>>        a + b
>>>> have?  Consider a having precision 32 and b having precision 64
>>>> on a 32-bit HWI host.
>>>>
>>>> You define wide-int to have no sign information:
>>>>
>>>> +   The representation does not contain any information about
>>>> +   signedness of the represented value, so it can be used to represent
>>>> +   both signed and unsigned numbers.  For operations where the results
>>>> +   depend on signedness (division, comparisons), the signedness must
>>>> +   be specified separately.  For operations where the signness
>>>> +   matters, one of the operands to the operation specifies either
>>>> +   wide_int::SIGNED or wide_int::UNSIGNED.
>>>>
>>>> but the result of operations on mixed precision operands _does_ depend
>>>> on the sign, nevertheless most operations do not get a signedness
>>>> argument.
>>>> Nor would that help, because it depends on the signedness of the
>>>> individual
>>>> operands!
>>>>
>>>> double-int get's around this by having a common "precision" to which
>>>> all smaller precision constants have to be sign-/zero-extended.  So
>>>> does CONST_INT and CONST_DOUBLE.
>>>>
>>>> Note that even with same precision you have introduced the same problem
>>>> with the variable len.
>>>>
>>>> My proposal is simple - all wide-ints are signed!  wide-int is basically
>>>> an arbitrary precision signed integer format.  The sign is encoded in
>>>> the most significant bit of the last active HWI of the representation
>>>> (val[len - 1] & (1 << HOST_BITS_PER_WIDE_INT - 1)).  All values
>>>> with less precision than len * HOST_BITS_PER_WIDE_INT are
>>>> properly sign-/zero-extended to precision len * HOST_BITS_PER_WIDE_INT.
>>>>
>>>> This let's you define mixed len operations by implicitely
>>>> sign-/zero-extending
>>>> the operands to whatever len is required for the operation.
>>>>
>>>> Furthermore it allows you to get rid of the precision member (and
>>>> bitsize anyway).
>>>> Conversion from tree / RTL requires information on the signedness of the
>>>> input (trivial for tree, for RTL all constants are signed - well,
>>>> sign-extended).
>>>> Whenever you want to transfer the wide-int to tree / RTL you have to
>>>> sign-/zero-extend according to the desired precision.  If you need sth
>>>> else
>>>> than arbitrary precision arithmetic you have to explicitely truncate /
>>>> extend
>>>> at suitable places - with overflow checking being trivial here.  For
>>>> optimization
>>>> purposes selected operations may benefit from a combined implementation
>>>> receiving a target precision and signedness.  Whatever extra meta-data
>>>> RTL requires does not belong in wide-int but in the RTX.  Trivially
>>>> a mode comes to my mind (on tree we have a type), and trivially
>>>> each RTX has a mode.  And each mode has a precision and bitsize.
>>>> It lacks a sign, so all RTL integer constants are sign-extended for
>>>> encoding efficiency purposes.  mixed-mode operations will not
>>>> occur (mixed len operations will), mixed-mode ops are exclusively
>>>> sign-/zero-extensions and truncations.
>>>>
>>>> Representation of (unsigned HOST_WIDE_INT)-1 would necessarily
>>>> be { 0, (unsigned HOST_WIDE_INT)-1 }, representation of -1 in any
>>>> precision would be { -1 }.
>>>>
>>>> That was my proposal.  Now, can you please properly specify yours?
>>
>> And you chose to not answer that fundamental question of how your
>> wide-int is _supposed_ to work?  Ok, maybe I shouldn't have distracted
>> you with the bits before this.
>
> sorry, i missed this question by accident.
>
> we did not do infinite precision by design.   We looked at the set of
> programming languages that gcc either compiles or might compile and we
> looked at the set of machines that gcc targets and neither of these two sets
> of entities define their operations in terms of infinite precision math.
> They always do math within a particular precision.    Scripting languages do
> use infinite precision but gcc does not compile any of them.   So unless you
> are going to restrict your set of operations to those that satisfy the
> properties of a ring, it is generally not strictly safe to do your math in
> infinite precision.
>
> we do all of the math in the precision defined by the types or modes that
> are passed in.
>
> constants are defined to be the size of the precision unless they can be
> compressed.   The len field tells how many words are actually needed to
> exactly represent the constant if (len-1)*HOST_WIDE_BITS_PER_WIDE_INT is
> less than the precision. The decompression process is to add a number of
> words to the high order side of the number.   These words must contain a
> zero if the highest represented bit is 0 and -1 if the highest represented
> bit is 1.

So the compressed representation is signed.  Please document that.

> i.e. this looks a lot like sign extension, but the numbers them selves are
> not inherently signed or unsigned as in your representation.    It is up to
> the operators to imply the signess. So the unsigned multiply operation is
> different than the signed multiply operation.    But these are applied to
> the bits without an interpretation of their sign.

Which means that the inconsistency of ops getting a precision argument
vs. arbitrarily taking the precision of the first operand is a design bug.
Note that with your encoding scheme as far as I understand the "sign"
of { -1 } depends on the precision.  If the precision is less than that of HWI
then { -1 } is signed, if it is exactly the precision of HWI the sign is
unspecified, it could be -1U or -1 (as far as I understand it is not an
invalid encoding of -1U?), if it has bigger precision than that of HWI
then the sign is unspecified (it could be -1U or -1 in larger precision)?

"Unspecified sign" means that you cannot combine two operands with
different 'len' / 'precision' without knowing the sign of the operands you
need to extend.  Note that knowing the sign of the operation is not enough.

So I believe that for correctness you need to assert at least
gcc_assert that operands have the same precision - as you assume
here for example:

+wide_int
+wide_int::operator + (const wide_int &op1) const
+{
+  wide_int result;
+
+  if (precision <= HOST_BITS_PER_WIDE_INT)
+    {
+      result.len = 1;
+      result.bitsize = bitsize;
+      result.precision = precision;
+      result.val[0] = val[0] + op1.val[0];
+      if (precision < HOST_BITS_PER_WIDE_INT)
+       result.val[0] = sext_hwi (result.val[0], precision);
+    }

which is clearly wrong if op1.precision != precision.  It also explains
why wide_int::one needs a precision ... (I hope you got rid of the
overloads)

I'm not sure to what extent you got rid of the precision/bitsize taking
functions like

+  inline wide_int lshift (unsigned int y, ShiftOp z, unsigned int bitsize,
+                         unsigned int precision) const;
+  wide_int popcount (unsigned int bitsize, unsigned int prec) const;

already.  They don't make sense as *this already has a precision.

Btw, my proposal would be to get rid of 'precision', as 'precision' is
not needed to interpret the encoding as I would define it (the MSB
would _always_ be a sign-bit) and as you say the operation
has a sign.  Truncating to a desired target precision can be done
after the fact or as part of the operation.  You already have to
deal with extension as even with equal precision operands can
have a different len.

I'd like to see the current state of wide-int somewhere btw., given
you've done significant changes since the last post.

Thanks,
Richard.

>
>> Richard.
>>
>>>> Thanks,
>>>> Richard.
>>>>
>>>>> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>>>>>
>>>>>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>>>>>> <zadeck@naturalbridge.com> wrote:
>>>>>>>
>>>>>>> This patch contains a large number of the changes requested by Richi.
>>>>>>> It
>>>>>>> does not contain any of the changes that he requested to abstract the
>>>>>>> storage layer.   That suggestion appears to be quite unworkable.
>>>>>>
>>>>>> I of course took this claim as a challenge ... with the following
>>>>>> result.
>>>>>> It is
>>>>>> of course quite workable ;)
>>>>>>
>>>>>> The attached patch implements the core wide-int class and three
>>>>>> storage
>>>>>> models (fixed size for things like plain HWI and double-int, variable
>>>>>> size
>>>>>> similar to how your wide-int works and an adaptor for the double-int
>>>>>> as
>>>>>> contained in trees).  With that you can now do
>>>>>>
>>>>>> HOST_WIDE_INT
>>>>>> wi_test (tree x)
>>>>>> {
>>>>>>      // template argument deduction doesn't do the magic we want it to
>>>>>> do
>>>>>>      // to make this kind of implicit conversions work
>>>>>>      // overload resolution considers this kind of conversions so we
>>>>>>      // need some magic that combines both ... but seeding the
>>>>>> overload
>>>>>>      // set with some instantiations doesn't seem to be possible :/
>>>>>>      // wide_int<> w = x + 1;
>>>>>>      wide_int<> w;
>>>>>>      w += x;
>>>>>>      w += 1;
>>>>>>      // template argument deduction doesn't deduce the return value
>>>>>> type,
>>>>>>      // not considering the template default argument either ...
>>>>>>      // w = wi (x) + 1;
>>>>>>      // we could support this by providing rvalue-to-lvalue promotion
>>>>>>      // via a traits class?
>>>>>>      // otoh it would lead to sub-optimal code anyway so we should
>>>>>>      // make the result available as reference parameter and only
>>>>>> support
>>>>>>      // wide_int <> res; add (res, x, 1); ?
>>>>>>      w = wi (x).operator+<wide_int<> >(1);
>>>>>>      wide_int<>::add(w, x, 1);
>>>>>>      return w.to_hwi ();
>>>>>> }
>>>>>>
>>>>>> we are somewhat limited with C++ unless we want to get really fancy.
>>>>>> Eventually providing operator+ just doesn't make much sense for
>>>>>> generic wide-int combinations (though then the issue is its operands
>>>>>> are no longer commutative which I think is the case with your wide-int
>>>>>> or double-int as well - they don't suport "1 + wide_int" for obvious
>>>>>> reasons).
>>>>>>
>>>>>> So there are implementation design choices left undecided.
>>>>>>
>>>>>> Oh, and the operation implementations are crap (they compute
>>>>>> nonsense).
>>>>>>
>>>>>> But you should get the idea.
>>>>>>
>>>>>> Richard.
>>>>>
>>>>>
>

Richard,

There has been something that has bothered me about you proposal for the 
storage manager and i think i can now characterize that problem.  Say i 
want to compute the expression

(a + b) / c

converting from tree values, using wide-int as the engine and then 
storing the result in a tree.   (A very common operation for the various 
simplifiers in gcc.)

in my version of wide-int where there is only the stack allocated fix 
size allocation for the data, the compiler arranges for 6 instances of 
wide-int that are "statically" allocated on the stack when the function 
is entered.    There would be 3 copies of the precision and data to get 
things started and one allocation variable sized object at the end when 
the INT_CST is built and one copy to put it back.   As i have argued, 
these copies are of negligible size.

In your world, to get things started, you would do 3 pointer copies to 
get the values out of the tree to set the expression leaves but then you 
will call the allocator 3 times to get space to hold the intermediate 
nodes before you get to pointer copy the result back into the result cst 
which still needs an allocation to build it. I am assuming that we can 
play the same game at the tree level that we do at the rtl level where 
we do 1 variable sized allocation to get the entire INT_CST rather than 
doing 1 fixed sized allocation and 1 variable sized one.

even if we take the simpler example of a + b, you still loose.   The 
cost of the extra allocation and it's subsequent recovery is more than 
my copies.   In fact, even in the simplest case of someone going from a 
HWI thru wide_int into tree, you have 2 allocations vs my 1.

I just do not see the cost savings and if there are no cost savings, you 
certainly cannot say that having these templates is simpler than not 
having the templates.

Kenny

On 04/02/2013 11:04 AM, Richard Biener wrote:
> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
> <zadeck@naturalbridge.com> wrote:
>> This patch contains a large number of the changes requested by Richi.   It
>> does not contain any of the changes that he requested to abstract the
>> storage layer.   That suggestion appears to be quite unworkable.
> I of course took this claim as a challenge ... with the following result.  It is
> of course quite workable ;)
>
> The attached patch implements the core wide-int class and three storage
> models (fixed size for things like plain HWI and double-int, variable size
> similar to how your wide-int works and an adaptor for the double-int as
> contained in trees).  With that you can now do
>
> HOST_WIDE_INT
> wi_test (tree x)
> {
>    // template argument deduction doesn't do the magic we want it to do
>    // to make this kind of implicit conversions work
>    // overload resolution considers this kind of conversions so we
>    // need some magic that combines both ... but seeding the overload
>    // set with some instantiations doesn't seem to be possible :/
>    // wide_int<> w = x + 1;
>    wide_int<> w;
>    w += x;
>    w += 1;
>    // template argument deduction doesn't deduce the return value type,
>    // not considering the template default argument either ...
>    // w = wi (x) + 1;
>    // we could support this by providing rvalue-to-lvalue promotion
>    // via a traits class?
>    // otoh it would lead to sub-optimal code anyway so we should
>    // make the result available as reference parameter and only support
>    // wide_int <> res; add (res, x, 1); ?
>    w = wi (x).operator+<wide_int<> >(1);
>    wide_int<>::add(w, x, 1);
>    return w.to_hwi ();
> }
>
> we are somewhat limited with C++ unless we want to get really fancy.
> Eventually providing operator+ just doesn't make much sense for
> generic wide-int combinations (though then the issue is its operands
> are no longer commutative which I think is the case with your wide-int
> or double-int as well - they don't suport "1 + wide_int" for obvious reasons).
>
> So there are implementation design choices left undecided.
>
> Oh, and the operation implementations are crap (they compute nonsense).
>
> But you should get the idea.
>
> Richard.

Richard,

You advocate that I should be using an infinite precision
representation and I advocate a finite precision representation where
the precision is taken from the context.  I would like to make the
case for my position here, in a separate thread, because the other
thread is just getting too messy.

At both the tree level and the rtl level you have a type (mode is just
bad rep for types) and both of those explicitly have precisions. The
semantics of the programming languages that we implement define, or at
least recommend, that most operations be done in a precision that is
implementation dependent (or like java a particular machine
independent precision).  Each hardware platform specifies exactly how
every operation is done.  I will admit that infinite precision is more
esthetically pleasing than what i have done, but exact precision
matches the needs of these clients.  The problem is that the results
from infinite precision arithmetic differ in many significant ways
from finite precision math.  And the number of places where you have
to inject a precision to get the expected answer, ultimately makes the
infinite precision representation unattractive.

As I said on Thursday, whenever you do operations that do not satisfy
the requirements of a mathematical ring (add sub and mul are in a
ring, divide, shift and comparisons are not) you run the risk of
getting a result that is not what would have been obtained with either
a strict interpretation of the semantics or the machine. Intuitively
any operation that looks at the bits above the precision does not
qualify as an operation that works in a ring.

The poster child for operations that do not belong to a ring is division.
For my example, I am using 4 bit integers because it makes the
examples easy, but similar examples exist for any fixed precision.

Consider 8 * 10 / 4

in an infinite precision world the result is 20, but in a 4 bit
precision world the answer is 0.

another example is to ask if

-10 * 10 is less than 0?

again you get a different answer with infinite precision.   I would argue
that if i declare a variable of type uint32 and scale my examples i have
the right to expect the compiler to produce the same result as the
machine would.

While C and C++ may have enough wiggle room in their standards so that
this is just an unexpected, but legal, result as opposed to being wrong,
everyone will hate you (us) if we do this.  Furthermore, Java explicitly 
does
not allow this (not that anyone actually uses gcj).  I do not know
enough about go, ada and fortran to say how it would effect them.

In looking at the double-int class, the only operation that does not
fit in a ring that is done properly is shifting.  There we explicitly
pass in the precision.

The reason that we rarely see this kind of problem even though
double-int implements 128 bit infinite precision is that currently
very little of the compiler actually uses infinite precision in a
robust way.   In a large number of places, the code looks like:

if (TYPE_PRECISION (TREE_TYPE (...)) < HOST_BITS_PER_WIDE_INT)
    do something using inline operators.
else
    either do not do something or use const-double,

such code clears out most of these issues before the two passes that
embrace infinite precision get a chance to do much damage.  However,
my patch at the rtl level gets rid of most of this kind of code and
replaces it with calls to wide-int that currently uses only operations
within the precision.  I assume that if i went down the infinite
precision road at the tree level, that all of this would come to the
surface very quickly.  I prefer to not change my rep and not have to
deal with this later.

Add, subtract, multiply and the logicals are all safe.  But divide,
remainder, and all of the comparisons need explicit precisions.  In
addition operations like clz, ctl and clrsb need precisions.  In total
about half of the functions would need a precision passed in.  My
point is that once you have to start passing in the precision in for all
of those operations, it seems to be cleaner to get the precision from
the leaves of the tree as I currently do.

Once you buy into the math in a particular precision world, a lot of
the other issues that you raise are just settled.  Asking how to extend
a value beyond it's precision is like asking what the universe was like 
before
the big bang.  It is just something you do not need to know.

I understand that you would like to have functions like x + 1 work,
and so do I. I just could not figure out how to make them have
unsurprising semantics.  In particular, g++ did not seem to be happy
with me defining two plus operators, one for each of signed and
unsigned HWIs.  It seems like if someone explicitly added a wide_int
and an unsigned HWI that they had a right to have the unsigned hwi not
be sign extended.  But if you can show me how to do this, i am happy
to go down that road.

Kenny

On 04/07/2013 07:16 PM, Kenneth Zadeck wrote:
> The poster child for operations that do not belong to a ring is division.
> For my example, I am using 4 bit integers because it makes the
> examples easy, but similar examples exist for any fixed precision.
>
> Consider 8 * 10 / 4
>
> in an infinite precision world the result is 20, but in a 4 bit
> precision world the answer is 0.

I think you mean "4" instead of "20".

> another example is to ask if
>
> -10 * 10 is less than 0?
>
> again you get a different answer with infinite precision.

Actually, for C/C++ ,you don't—because of undefined signed overflow
(at least with default compiler flags).  But similar examples with 
unsigned types exist, so this point isn't too relevant.

> I would argue
> that if i declare a variable of type uint32 and scale my examples i have
> the right to expect the compiler to produce the same result as the
> machine would.

In my very, very limited experience, the signed/unsigned mismatch is 
more confusing.  With infinite precision, this confusion would not arise 
(but adjustment would be needed to get limited-precision results, as you 
write).  With finite precision, you either need separate types for 
signed/unsigned, or separate operations.

> While C and C++ may have enough wiggle room in their standards so that
> this is just an unexpected, but legal, result as opposed to being wrong,
> everyone will hate you (us) if we do this.  Furthermore, Java explicitly
> does
> not allow this (not that anyone actually uses gcj).  I do not know
> enough about go,

Go specified two's-complement signed arithmetic and does not 
automatically promote to int (i.e., it performs arithmetic in the type, 
and mixed arguments are not supported).

Go constant arithmetic is infinite precision.

 > ada and fortran to say how it would effect them.

Ada requires trapping arithmetic for signed integers.  Currently, this 
is implemented in the front end.  Arithmetic happens in the base range 
of a type (which is symmetric around zero and chosen to correspond to a 
machine type).  Ada allows omitting intermediate overflow checks as long 
as you produce the infinite precision result (or raise an overflow 
exception).

I think this applies to Ada constant arithmetic as well.

(GNAT has a mode where comparisons are computed with infinite precision, 
which is extremely useful for writing bounds checking code.)

Considering the range of different arithmetic operations we need to 
support, I'm not convinced that the ring model is appropriate.

On Fri, Apr 5, 2013 at 2:34 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Richard,
>
> There has been something that has bothered me about you proposal for the
> storage manager and i think i can now characterize that problem.  Say i want
> to compute the expression
>
> (a + b) / c
>
> converting from tree values, using wide-int as the engine and then storing
> the result in a tree.   (A very common operation for the various simplifiers
> in gcc.)
>
> in my version of wide-int where there is only the stack allocated fix size
> allocation for the data, the compiler arranges for 6 instances of wide-int
> that are "statically" allocated on the stack when the function is entered.
> There would be 3 copies of the precision and data to get things started and
> one allocation variable sized object at the end when the INT_CST is built
> and one copy to put it back.   As i have argued, these copies are of
> negligible size.
>
> In your world, to get things started, you would do 3 pointer copies to get
> the values out of the tree to set the expression leaves but then you will
> call the allocator 3 times to get space to hold the intermediate nodes
> before you get to pointer copy the result back into the result cst which
> still needs an allocation to build it. I am assuming that we can play the
> same game at the tree level that we do at the rtl level where we do 1
> variable sized allocation to get the entire INT_CST rather than doing 1
> fixed sized allocation and 1 variable sized one.
>
> even if we take the simpler example of a + b, you still loose.   The cost of
> the extra allocation and it's subsequent recovery is more than my copies.
> In fact, even in the simplest case of someone going from a HWI thru wide_int
> into tree, you have 2 allocations vs my 1.

Just to clarify, my code wouldn't handle

  tree a, b, c;
  tree res = (a + b) / c;

transparently.  The most "complex" form of the above that I think would
be reasonable to handle would be

  tree a, b, c;
  wide_int wires = (wi (a) + b) / c;
  tree res = build_int_cst (TREE_TYPE (a), wires);

and the code as posted would even require you to specify the
return type of operator+ and operator/ explicitely like

 wide_int<> wires = (wi (a).operator+<wi_embed_var>
(b)).operator/<wi_embed_var> (c);

but as I said I just didn't bother to "decide" that the return type is
always of wide_int <variable-len-storage> kind.

Now, the only real allocation that happens is done by build_int_cst.
There is one wide_int on the stack to hold the a + b result and one
separate wide_int to hold wires (it's literally written in the code).
There are no "pointer copies" involved in the end - the result from
converting a tree to a wide_int<tree-storage> is the original 'tree'
pointer itself, thus a register.

> I just do not see the cost savings and if there are no cost savings, you
> certainly cannot say that having these templates is simpler than not having
> the templates.

I think you are missing the point - by abstracting away the storage
you don't necessarily need to add the templates.  But you open up
a very easy route for doing so and you make the operations _trivially_
work on the tree / RTL storage with no overhead in generated code
and minimal overhead in the amount of code in GCC itself.  In my
prototype the overhead of adding 'tree' support is to place

class wi_tree_int_cst
{
  tree cst;
public:
  void construct (tree c) { cst = c; }
  const HOST_WIDE_INT *storage() const { return reinterpret_cast
<HOST_WIDE_INT *>(&TREE_INT_CST (cst)); }
  unsigned len() const { return 2; }
};

template <>
class wi_traits <tree>
{
public:
    typedef wide_int <wi_tree_int_cst> wi_t;
    wi_traits(tree t)
  {
    wi_tree_int_cst ws;
    ws.construct (t);
    w.construct (ws);
  }
    wi_t* operator->() { return &w; }
private:
    wi_t w;
};

into tree.h.

Richard.

> Kenny
>
>
> On 04/02/2013 11:04 AM, Richard Biener wrote:
>>
>> On Wed, Feb 27, 2013 at 2:59 AM, Kenneth Zadeck
>> <zadeck@naturalbridge.com> wrote:
>>>
>>> This patch contains a large number of the changes requested by Richi.
>>> It
>>> does not contain any of the changes that he requested to abstract the
>>> storage layer.   That suggestion appears to be quite unworkable.
>>
>> I of course took this claim as a challenge ... with the following result.
>> It is
>> of course quite workable ;)
>>
>> The attached patch implements the core wide-int class and three storage
>> models (fixed size for things like plain HWI and double-int, variable size
>> similar to how your wide-int works and an adaptor for the double-int as
>> contained in trees).  With that you can now do
>>
>> HOST_WIDE_INT
>> wi_test (tree x)
>> {
>>    // template argument deduction doesn't do the magic we want it to do
>>    // to make this kind of implicit conversions work
>>    // overload resolution considers this kind of conversions so we
>>    // need some magic that combines both ... but seeding the overload
>>    // set with some instantiations doesn't seem to be possible :/
>>    // wide_int<> w = x + 1;
>>    wide_int<> w;
>>    w += x;
>>    w += 1;
>>    // template argument deduction doesn't deduce the return value type,
>>    // not considering the template default argument either ...
>>    // w = wi (x) + 1;
>>    // we could support this by providing rvalue-to-lvalue promotion
>>    // via a traits class?
>>    // otoh it would lead to sub-optimal code anyway so we should
>>    // make the result available as reference parameter and only support
>>    // wide_int <> res; add (res, x, 1); ?
>>    w = wi (x).operator+<wide_int<> >(1);
>>    wide_int<>::add(w, x, 1);
>>    return w.to_hwi ();
>> }
>>
>> we are somewhat limited with C++ unless we want to get really fancy.
>> Eventually providing operator+ just doesn't make much sense for
>> generic wide-int combinations (though then the issue is its operands
>> are no longer commutative which I think is the case with your wide-int
>> or double-int as well - they don't suport "1 + wide_int" for obvious
>> reasons).
>>
>> So there are implementation design choices left undecided.
>>
>> Oh, and the operation implementations are crap (they compute nonsense).
>>
>> But you should get the idea.
>>
>> Richard.
>
>

On Sun, Apr 7, 2013 at 7:16 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Richard,
>
> You advocate that I should be using an infinite precision
> representation and I advocate a finite precision representation where
> the precision is taken from the context.  I would like to make the
> case for my position here, in a separate thread, because the other
> thread is just getting too messy.
>
> At both the tree level and the rtl level you have a type (mode is just
> bad rep for types) and both of those explicitly have precisions. The
> semantics of the programming languages that we implement define, or at
> least recommend, that most operations be done in a precision that is
> implementation dependent (or like java a particular machine
> independent precision).  Each hardware platform specifies exactly how
> every operation is done.  I will admit that infinite precision is more
> esthetically pleasing than what i have done, but exact precision
> matches the needs of these clients.  The problem is that the results
> from infinite precision arithmetic differ in many significant ways
> from finite precision math.  And the number of places where you have
> to inject a precision to get the expected answer, ultimately makes the
> infinite precision representation unattractive.
>
> As I said on Thursday, whenever you do operations that do not satisfy
> the requirements of a mathematical ring (add sub and mul are in a
> ring, divide, shift and comparisons are not) you run the risk of
> getting a result that is not what would have been obtained with either
> a strict interpretation of the semantics or the machine. Intuitively
> any operation that looks at the bits above the precision does not
> qualify as an operation that works in a ring.
>
> The poster child for operations that do not belong to a ring is division.
> For my example, I am using 4 bit integers because it makes the
> examples easy, but similar examples exist for any fixed precision.
>
> Consider 8 * 10 / 4
>
> in an infinite precision world the result is 20, but in a 4 bit
> precision world the answer is 0.
>
> another example is to ask if
>
> -10 * 10 is less than 0?
>
> again you get a different answer with infinite precision.   I would argue
> that if i declare a variable of type uint32 and scale my examples i have
> the right to expect the compiler to produce the same result as the
> machine would.
>
> While C and C++ may have enough wiggle room in their standards so that
> this is just an unexpected, but legal, result as opposed to being wrong,
> everyone will hate you (us) if we do this.  Furthermore, Java explicitly
> does
> not allow this (not that anyone actually uses gcj).  I do not know
> enough about go, ada and fortran to say how it would effect them.
>
> In looking at the double-int class, the only operation that does not
> fit in a ring that is done properly is shifting.  There we explicitly
> pass in the precision.
>
> The reason that we rarely see this kind of problem even though
> double-int implements 128 bit infinite precision is that currently
> very little of the compiler actually uses infinite precision in a
> robust way.   In a large number of places, the code looks like:
>
> if (TYPE_PRECISION (TREE_TYPE (...)) < HOST_BITS_PER_WIDE_INT)
>    do something using inline operators.
> else
>    either do not do something or use const-double,
>
> such code clears out most of these issues before the two passes that
> embrace infinite precision get a chance to do much damage.  However,
> my patch at the rtl level gets rid of most of this kind of code and
> replaces it with calls to wide-int that currently uses only operations
> within the precision.  I assume that if i went down the infinite
> precision road at the tree level, that all of this would come to the
> surface very quickly.  I prefer to not change my rep and not have to
> deal with this later.
>
> Add, subtract, multiply and the logicals are all safe.  But divide,
> remainder, and all of the comparisons need explicit precisions.  In
> addition operations like clz, ctl and clrsb need precisions.  In total
> about half of the functions would need a precision passed in.  My
> point is that once you have to start passing in the precision in for all
> of those operations, it seems to be cleaner to get the precision from
> the leaves of the tree as I currently do.
>
> Once you buy into the math in a particular precision world, a lot of
> the other issues that you raise are just settled.  Asking how to extend
> a value beyond it's precision is like asking what the universe was like
> before
> the big bang.  It is just something you do not need to know.
>
> I understand that you would like to have functions like x + 1 work,
> and so do I. I just could not figure out how to make them have
> unsurprising semantics.  In particular, g++ did not seem to be happy
> with me defining two plus operators, one for each of signed and
> unsigned HWIs.  It seems like if someone explicitly added a wide_int
> and an unsigned HWI that they had a right to have the unsigned hwi not
> be sign extended.  But if you can show me how to do this, i am happy
> to go down that road.

I advocate the infinite precision signed representation as one solution
to avoid the issues that come up with your implementation (as I currently
have access to) which has a representation with N bits of precision
encoded with M <= N bits and no sign information.  That obviously
leaves operations on numbers of that representation with differing
N undefined.  You define it by having coded the operations which as far
as I can see simply assume N is equal for any two operands and
the effective sign for extending the M-bits encoding to the common
N-bits precision is "available".  A thorough specification of both
the encoding scheme and the operation semantics is missing.
I can side-step both of these issues nicely by simply using
a infinite precision signed representation and requiring the client to
explicitely truncate / extend to a specific precision when required.
I also leave open the possibility to have the _encoding_ be always
the same as an infinite precision signed representation but to always
require an explicitely specified target precision for each operation
(which rules out the use of operator overloading).

Citing your example:

  8 * 10 / 4

and transforming it slightly into a commonly used pattern:

  (byte-size * 8 + bit-size) / 8

then I argue that what people want here is this carried out in
_infinite_ precision!  Even if byte-size happens to come from
a sizetype TREE_INT_CST with 64bit precision.  So either
choice - having a fixed-precision representation or an
infinite-precision representation - can and will lead to errors
done by the programmer.  And as you can easily build a
finite precision wrapper around an infinite precision implementation
but not the other way around it's obvious to me what the
implementation should provide.

Richard.

> Kenny

On 04/08/2013 06:46 AM, Richard Biener wrote:
> On Sun, Apr 7, 2013 at 7:16 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>> Richard,
>>
>> You advocate that I should be using an infinite precision
>> representation and I advocate a finite precision representation where
>> the precision is taken from the context.  I would like to make the
>> case for my position here, in a separate thread, because the other
>> thread is just getting too messy.
>>
>> At both the tree level and the rtl level you have a type (mode is just
>> bad rep for types) and both of those explicitly have precisions. The
>> semantics of the programming languages that we implement define, or at
>> least recommend, that most operations be done in a precision that is
>> implementation dependent (or like java a particular machine
>> independent precision).  Each hardware platform specifies exactly how
>> every operation is done.  I will admit that infinite precision is more
>> esthetically pleasing than what i have done, but exact precision
>> matches the needs of these clients.  The problem is that the results
>> from infinite precision arithmetic differ in many significant ways
>> from finite precision math.  And the number of places where you have
>> to inject a precision to get the expected answer, ultimately makes the
>> infinite precision representation unattractive.
>>
>> As I said on Thursday, whenever you do operations that do not satisfy
>> the requirements of a mathematical ring (add sub and mul are in a
>> ring, divide, shift and comparisons are not) you run the risk of
>> getting a result that is not what would have been obtained with either
>> a strict interpretation of the semantics or the machine. Intuitively
>> any operation that looks at the bits above the precision does not
>> qualify as an operation that works in a ring.
>>
>> The poster child for operations that do not belong to a ring is division.
>> For my example, I am using 4 bit integers because it makes the
>> examples easy, but similar examples exist for any fixed precision.
>>
>> Consider 8 * 10 / 4
>>
>> in an infinite precision world the result is 20, but in a 4 bit
>> precision world the answer is 0.
>>
>> another example is to ask if
>>
>> -10 * 10 is less than 0?
>>
>> again you get a different answer with infinite precision.   I would argue
>> that if i declare a variable of type uint32 and scale my examples i have
>> the right to expect the compiler to produce the same result as the
>> machine would.
>>
>> While C and C++ may have enough wiggle room in their standards so that
>> this is just an unexpected, but legal, result as opposed to being wrong,
>> everyone will hate you (us) if we do this.  Furthermore, Java explicitly
>> does
>> not allow this (not that anyone actually uses gcj).  I do not know
>> enough about go, ada and fortran to say how it would effect them.
>>
>> In looking at the double-int class, the only operation that does not
>> fit in a ring that is done properly is shifting.  There we explicitly
>> pass in the precision.
>>
>> The reason that we rarely see this kind of problem even though
>> double-int implements 128 bit infinite precision is that currently
>> very little of the compiler actually uses infinite precision in a
>> robust way.   In a large number of places, the code looks like:
>>
>> if (TYPE_PRECISION (TREE_TYPE (...)) < HOST_BITS_PER_WIDE_INT)
>>     do something using inline operators.
>> else
>>     either do not do something or use const-double,
>>
>> such code clears out most of these issues before the two passes that
>> embrace infinite precision get a chance to do much damage.  However,
>> my patch at the rtl level gets rid of most of this kind of code and
>> replaces it with calls to wide-int that currently uses only operations
>> within the precision.  I assume that if i went down the infinite
>> precision road at the tree level, that all of this would come to the
>> surface very quickly.  I prefer to not change my rep and not have to
>> deal with this later.
>>
>> Add, subtract, multiply and the logicals are all safe.  But divide,
>> remainder, and all of the comparisons need explicit precisions.  In
>> addition operations like clz, ctl and clrsb need precisions.  In total
>> about half of the functions would need a precision passed in.  My
>> point is that once you have to start passing in the precision in for all
>> of those operations, it seems to be cleaner to get the precision from
>> the leaves of the tree as I currently do.
>>
>> Once you buy into the math in a particular precision world, a lot of
>> the other issues that you raise are just settled.  Asking how to extend
>> a value beyond it's precision is like asking what the universe was like
>> before
>> the big bang.  It is just something you do not need to know.
>>
>> I understand that you would like to have functions like x + 1 work,
>> and so do I. I just could not figure out how to make them have
>> unsurprising semantics.  In particular, g++ did not seem to be happy
>> with me defining two plus operators, one for each of signed and
>> unsigned HWIs.  It seems like if someone explicitly added a wide_int
>> and an unsigned HWI that they had a right to have the unsigned hwi not
>> be sign extended.  But if you can show me how to do this, i am happy
>> to go down that road.
> I advocate the infinite precision signed representation as one solution
> to avoid the issues that come up with your implementation (as I currently
> have access to) which has a representation with N bits of precision
> encoded with M <= N bits and no sign information.  That obviously
> leaves operations on numbers of that representation with differing
> N undefined.  You define it by having coded the operations which as far
> as I can see simply assume N is equal for any two operands and
> the effective sign for extending the M-bits encoding to the common
> N-bits precision is "available".  A thorough specification of both
> the encoding scheme and the operation semantics is missing.
This is a perfectly reasonable request.
> I can side-step both of these issues nicely by simply using
> a infinite precision signed representation and requiring the client to
> explicitely truncate / extend to a specific precision when required.
> I also leave open the possibility to have the _encoding_ be always
> the same as an infinite precision signed representation but to always
> require an explicitely specified target precision for each operation
> (which rules out the use of operator overloading).
>
> Citing your example:
>
>    8 * 10 / 4
>
> and transforming it slightly into a commonly used pattern:
>
>    (byte-size * 8 + bit-size) / 8
Patterns like this are generally not encoded in either double int or 
wide-int.   I do not think that anyone has taken the position that all 
math be done in a wide math, only the math on the variables that appear 
in the programs.


> then I argue that what people want here is this carried out in
> _infinite_ precision!  Even if byte-size happens to come from
> a sizetype TREE_INT_CST with 64bit precision.  So either
> choice - having a fixed-precision representation or an
> infinite-precision representation - can and will lead to errors
> done by the programmer.  And as you can easily build a
> finite precision wrapper around an infinite precision implementation
> but not the other way around it's obvious to me what the
> implementation should provide.
>
> Richard.
Infinite precision does get rid of the issue that you have to specify 
the precision at the leaves.    However, for the vast majority 
expression trees that get built, the leaves already have their precision 
in the type or the mode.   On the other hand to keep the math sane, the 
infinite precision requires either external truncation (ugly) or 
specification of the precision and many interior nodes of the expression 
tree (just as ugly as my putting it at the constant leaves).

The other problem, which i invite you to use the full power of your c++ 
sorcery on, is the one where defining an operator so that wide-int + 
unsigned hwi is either rejected or properly zero extended.    If you can 
do this, I will go along with your suggestion that the internal rep 
should be sign extended.  Saying that constants are always sign extended 
seems ok, but there are a huge number of places where we convert 
unsigned hwis as the second operand and i do not want that to be a 
trap.  I went thru a round of this, where i did not post the patch 
because i could not make this work.   And the number of places where you 
want to use an hwi as the second operand dwarfs the number of places 
where you want to use a small integer constant.
>> Kenny

It may be interesting to look at what we have done in
Ada with regard to overflow in intermediate expressions.
Briefly we allow specification of three modes

all intermediate arithmetic is done in the base type,
with overflow signalled if an intermediate value is
outside this range.

all intermediate arithmetic is done in the widest
integer type, with overflow signalled if an intermediate
value is outside this range.

all intermediate arithmetic uses an infinite precision
arithmetic package built for this purpose.

In the second and third cases we do range analysis that
allows smaller intermediate precision if we know it's
safe.

We also allow separate specification of the mode inside
and outside assertions (e.g. preconditions and postconditions)
since in the latter you often want to regard integers as
mathematical, not subject to intermediate overflow.

On 04/08/2013 04:56 AM, Florian Weimer wrote:
> On 04/07/2013 07:16 PM, Kenneth Zadeck wrote:
>> The poster child for operations that do not belong to a ring is 
>> division.
>> For my example, I am using 4 bit integers because it makes the
>> examples easy, but similar examples exist for any fixed precision.
>>
>> Consider 8 * 10 / 4
>>
>> in an infinite precision world the result is 20, but in a 4 bit
>> precision world the answer is 0.
>
> I think you mean "4" instead of "20".
>
oops
>> another example is to ask if
>>
>> -10 * 10 is less than 0?
>>
>> again you get a different answer with infinite precision.
>
> Actually, for C/C++ ,you don't—because of undefined signed overflow
> (at least with default compiler flags).  But similar examples with 
> unsigned types exist, so this point isn't too relevant.
>
>> I would argue
>> that if i declare a variable of type uint32 and scale my examples i have
>> the right to expect the compiler to produce the same result as the
>> machine would.
>
> In my very, very limited experience, the signed/unsigned mismatch is 
> more confusing.  With infinite precision, this confusion would not 
> arise (but adjustment would be needed to get limited-precision 
> results, as you write).  With finite precision, you either need 
> separate types for signed/unsigned, or separate operations.
>
I come from a world where people write code where they expect full 
control of the horizon and vertical when they program.   Hank Warren, 
the author of Hacker Delight is in my group and a huge number of those 
tricks require understanding what is going on in the machine.  If the 
compiler decides that it wants to do things differently, you are dead.
>> While C and C++ may have enough wiggle room in their standards so that
>> this is just an unexpected, but legal, result as opposed to being wrong,
>> everyone will hate you (us) if we do this.  Furthermore, Java explicitly
>> does
>> not allow this (not that anyone actually uses gcj).  I do not know
>> enough about go,
>
> Go specified two's-complement signed arithmetic and does not 
> automatically promote to int (i.e., it performs arithmetic in the 
> type, and mixed arguments are not supported).
>
> Go constant arithmetic is infinite precision.
>
> > ada and fortran to say how it would effect them.
>
> Ada requires trapping arithmetic for signed integers.  Currently, this 
> is implemented in the front end.  Arithmetic happens in the base range 
> of a type (which is symmetric around zero and chosen to correspond to 
> a machine type).  Ada allows omitting intermediate overflow checks as 
> long as you produce the infinite precision result (or raise an 
> overflow exception).
>
> I think this applies to Ada constant arithmetic as well.
>
> (GNAT has a mode where comparisons are computed with infinite 
> precision, which is extremely useful for writing bounds checking code.)
>
> Considering the range of different arithmetic operations we need to 
> support, I'm not convinced that the ring model is appropriate.
>
I will answer this in Robert's email.

On 4/8/2013 9:15 AM, Kenneth Zadeck wrote:

>> I think this applies to Ada constant arithmetic as well.

Ada constant arithmetic (at compile time) is always infinite
precision (for float as well as for integer).

On 04/08/2013 09:19 AM, Robert Dewar wrote:
> On 4/8/2013 9:15 AM, Kenneth Zadeck wrote:
>
>>> I think this applies to Ada constant arithmetic as well.
>
> Ada constant arithmetic (at compile time) is always infinite
> precision (for float as well as for integer).
>
What do you mean when you say "constant arithmetic"?    Do you mean 
places where there is an explicit 8 * 6 in the source or do you mean any 
arithmetic that a compiler, using the full power of interprocedural 
constant propagation can discover?

On 04/08/2013 09:03 AM, Robert Dewar wrote:
> It may be interesting to look at what we have done in
> Ada with regard to overflow in intermediate expressions.
> Briefly we allow specification of three modes
>
> all intermediate arithmetic is done in the base type,
> with overflow signalled if an intermediate value is
> outside this range.
>
> all intermediate arithmetic is done in the widest
> integer type, with overflow signalled if an intermediate
> value is outside this range.
>
> all intermediate arithmetic uses an infinite precision
> arithmetic package built for this purpose.
>
> In the second and third cases we do range analysis that
> allows smaller intermediate precision if we know it's
> safe.
>
> We also allow separate specification of the mode inside
> and outside assertions (e.g. preconditions and postconditions)
> since in the latter you often want to regard integers as
> mathematical, not subject to intermediate overflow.
So then how does a language like ada work in gcc?   My assumption is 
that most of what you describe here is done in the front end and by the 
time you get to the middle end of the compiler, you have chosen types 
for which you are comfortable to have any remaining math done in along 
with explicit checks for overflow where the programmer asked for them.

Otherwise, how could ada have ever worked with gcc?

kenny

On 4/8/2013 9:24 AM, Kenneth Zadeck wrote:

> So then how does a language like ada work in gcc?   My assumption is
> that most of what you describe here is done in the front end and by the
> time you get to the middle end of the compiler, you have chosen types
> for which you are comfortable to have any remaining math done in along
> with explicit checks for overflow where the programmer asked for them.

That's right, the front end does all the promotion of types
>
> Otherwise, how could ada have ever worked with gcc?

Sometimes we do have to make changes to gcc to accomodate Ada
specific requirements, but this was not one of those cases. Of
course the back end would do a better job of the range analysis
to remove some unnecessary use of infinite precision, but the
front end in practice does a good enough job.

On 4/8/2013 9:23 AM, Kenneth Zadeck wrote:
> On 04/08/2013 09:19 AM, Robert Dewar wrote:
>> On 4/8/2013 9:15 AM, Kenneth Zadeck wrote:
>>
>>>> I think this applies to Ada constant arithmetic as well.
>>
>> Ada constant arithmetic (at compile time) is always infinite
>> precision (for float as well as for integer).
>>
> What do you mean when you say "constant arithmetic"?    Do you mean
> places where there is an explicit 8 * 6 in the source or do you mean any
> arithmetic that a compiler, using the full power of interprocedural
> constant propagation can discover?

Somewhere between the two. Ada has a very well defined notion of
what is and what is not a "static expression", it definitely does not
include everything the compiler can discover, but it goes beyond just
explicit literal arithmetic, e.g. declared constants

    X : Integer := 75;

are considered static. It is static expressions that must be computed
with full precision at compile time. For expressions the compiler can
tell are constant even though not officially static, it is fine to
compute at compile time for integer, but NOT for float, since you want
to use target precision for all non-static float-operations.
>

On 04/08/2013 09:52 AM, Robert Dewar wrote:
> On 4/8/2013 9:23 AM, Kenneth Zadeck wrote:
>> On 04/08/2013 09:19 AM, Robert Dewar wrote:
>>> On 4/8/2013 9:15 AM, Kenneth Zadeck wrote:
>>>
>>>>> I think this applies to Ada constant arithmetic as well.
>>>
>>> Ada constant arithmetic (at compile time) is always infinite
>>> precision (for float as well as for integer).
>>>
>> What do you mean when you say "constant arithmetic"?    Do you mean
>> places where there is an explicit 8 * 6 in the source or do you mean any
>> arithmetic that a compiler, using the full power of interprocedural
>> constant propagation can discover?
>
> Somewhere between the two. Ada has a very well defined notion of
> what is and what is not a "static expression", it definitely does not
> include everything the compiler can discover, but it goes beyond just
> explicit literal arithmetic, e.g. declared constants
>
>    X : Integer := 75;
>
I actually guessed that it was something like this but i did not want to 
spend the time trying to figure this bit of ada syntax out.
> are considered static. It is static expressions that must be computed
> with full precision at compile time. For expressions the compiler can
> tell are constant even though not officially static, it is fine to
> compute at compile time for integer, but NOT for float, since you want
> to use target precision for all non-static float-operations.
>>
>
yes but the relevant question for the not officially static integer 
constants is "in what precision are those operations to be performed 
in?    I assume that you choose gcc types for these operations and you 
expect the math to be done within that type, i.e. exactly the way you 
expect the machine to perform.

On 4/8/2013 9:58 AM, Kenneth Zadeck wrote:

> yes but the relevant question for the not officially static integer
> constants is "in what precision are those operations to be performed
> in?    I assume that you choose gcc types for these operations and you
> expect the math to be done within that type, i.e. exactly the way you
> expect the machine to perform.

As I explained in an earlier message, *within* a single expression, we
are free to use higher precision, and we provide modes that allow this
up to and including the usea of infinite precision. That applies not
just to constant expressions but to all expressions.
>

On 04/08/2013 10:12 AM, Robert Dewar wrote:
> On 4/8/2013 9:58 AM, Kenneth Zadeck wrote:
>
>> yes but the relevant question for the not officially static integer
>> constants is "in what precision are those operations to be performed
>> in?    I assume that you choose gcc types for these operations and you
>> expect the math to be done within that type, i.e. exactly the way you
>> expect the machine to perform.
>
> As I explained in an earlier message, *within* a single expression, we
> are free to use higher precision, and we provide modes that allow this
> up to and including the usea of infinite precision. That applies not
> just to constant expressions but to all expressions.
>>
>
My confusion is what you mean by "we"?   Do you mean "we" the writer of 
the program, "we" the person invoking the compiler by the use command 
line options or "we", your company's implementation of ada?

My interpretation of your first email was that it was possible for the 
programmer to do something equivalent to adding attributes surrounding a 
block in the program to control the precision and overflow detection of 
the expressions in the block.   And if this is so, then by the time the 
expression is seen by the middle end of gcc, those attributes will have 
been converted into tree code will evaluate the code in a well defined 
way by both the optimization passes and the target machine.

Kenny

On Mon, Apr 8, 2013 at 2:43 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
> On 04/08/2013 06:46 AM, Richard Biener wrote:
>>
>> On Sun, Apr 7, 2013 at 7:16 PM, Kenneth Zadeck <zadeck@naturalbridge.com>
>> wrote:
>>>
>>> Richard,
>>>
>>> You advocate that I should be using an infinite precision
>>> representation and I advocate a finite precision representation where
>>> the precision is taken from the context.  I would like to make the
>>> case for my position here, in a separate thread, because the other
>>> thread is just getting too messy.
>>>
>>> At both the tree level and the rtl level you have a type (mode is just
>>> bad rep for types) and both of those explicitly have precisions. The
>>> semantics of the programming languages that we implement define, or at
>>> least recommend, that most operations be done in a precision that is
>>> implementation dependent (or like java a particular machine
>>> independent precision).  Each hardware platform specifies exactly how
>>> every operation is done.  I will admit that infinite precision is more
>>> esthetically pleasing than what i have done, but exact precision
>>> matches the needs of these clients.  The problem is that the results
>>> from infinite precision arithmetic differ in many significant ways
>>> from finite precision math.  And the number of places where you have
>>> to inject a precision to get the expected answer, ultimately makes the
>>> infinite precision representation unattractive.
>>>
>>> As I said on Thursday, whenever you do operations that do not satisfy
>>> the requirements of a mathematical ring (add sub and mul are in a
>>> ring, divide, shift and comparisons are not) you run the risk of
>>> getting a result that is not what would have been obtained with either
>>> a strict interpretation of the semantics or the machine. Intuitively
>>> any operation that looks at the bits above the precision does not
>>> qualify as an operation that works in a ring.
>>>
>>> The poster child for operations that do not belong to a ring is division.
>>> For my example, I am using 4 bit integers because it makes the
>>> examples easy, but similar examples exist for any fixed precision.
>>>
>>> Consider 8 * 10 / 4
>>>
>>> in an infinite precision world the result is 20, but in a 4 bit
>>> precision world the answer is 0.
>>>
>>> another example is to ask if
>>>
>>> -10 * 10 is less than 0?
>>>
>>> again you get a different answer with infinite precision.   I would argue
>>> that if i declare a variable of type uint32 and scale my examples i have
>>> the right to expect the compiler to produce the same result as the
>>> machine would.
>>>
>>> While C and C++ may have enough wiggle room in their standards so that
>>> this is just an unexpected, but legal, result as opposed to being wrong,
>>> everyone will hate you (us) if we do this.  Furthermore, Java explicitly
>>> does
>>> not allow this (not that anyone actually uses gcj).  I do not know
>>> enough about go, ada and fortran to say how it would effect them.
>>>
>>> In looking at the double-int class, the only operation that does not
>>> fit in a ring that is done properly is shifting.  There we explicitly
>>> pass in the precision.
>>>
>>> The reason that we rarely see this kind of problem even though
>>> double-int implements 128 bit infinite precision is that currently
>>> very little of the compiler actually uses infinite precision in a
>>> robust way.   In a large number of places, the code looks like:
>>>
>>> if (TYPE_PRECISION (TREE_TYPE (...)) < HOST_BITS_PER_WIDE_INT)
>>>     do something using inline operators.
>>> else
>>>     either do not do something or use const-double,
>>>
>>> such code clears out most of these issues before the two passes that
>>> embrace infinite precision get a chance to do much damage.  However,
>>> my patch at the rtl level gets rid of most of this kind of code and
>>> replaces it with calls to wide-int that currently uses only operations
>>> within the precision.  I assume that if i went down the infinite
>>> precision road at the tree level, that all of this would come to the
>>> surface very quickly.  I prefer to not change my rep and not have to
>>> deal with this later.
>>>
>>> Add, subtract, multiply and the logicals are all safe.  But divide,
>>> remainder, and all of the comparisons need explicit precisions.  In
>>> addition operations like clz, ctl and clrsb need precisions.  In total
>>> about half of the functions would need a precision passed in.  My
>>> point is that once you have to start passing in the precision in for all
>>> of those operations, it seems to be cleaner to get the precision from
>>> the leaves of the tree as I currently do.
>>>
>>> Once you buy into the math in a particular precision world, a lot of
>>> the other issues that you raise are just settled.  Asking how to extend
>>> a value beyond it's precision is like asking what the universe was like
>>> before
>>> the big bang.  It is just something you do not need to know.
>>>
>>> I understand that you would like to have functions like x + 1 work,
>>> and so do I. I just could not figure out how to make them have
>>> unsurprising semantics.  In particular, g++ did not seem to be happy
>>> with me defining two plus operators, one for each of signed and
>>> unsigned HWIs.  It seems like if someone explicitly added a wide_int
>>> and an unsigned HWI that they had a right to have the unsigned hwi not
>>> be sign extended.  But if you can show me how to do this, i am happy
>>> to go down that road.
>>
>> I advocate the infinite precision signed representation as one solution
>> to avoid the issues that come up with your implementation (as I currently
>> have access to) which has a representation with N bits of precision
>> encoded with M <= N bits and no sign information.  That obviously
>> leaves operations on numbers of that representation with differing
>> N undefined.  You define it by having coded the operations which as far
>> as I can see simply assume N is equal for any two operands and
>> the effective sign for extending the M-bits encoding to the common
>> N-bits precision is "available".  A thorough specification of both
>> the encoding scheme and the operation semantics is missing.
>
> This is a perfectly reasonable request.
>
>> I can side-step both of these issues nicely by simply using
>> a infinite precision signed representation and requiring the client to
>> explicitely truncate / extend to a specific precision when required.
>> I also leave open the possibility to have the _encoding_ be always
>> the same as an infinite precision signed representation but to always
>> require an explicitely specified target precision for each operation
>> (which rules out the use of operator overloading).
>>
>> Citing your example:
>>
>>    8 * 10 / 4
>>
>> and transforming it slightly into a commonly used pattern:
>>
>>    (byte-size * 8 + bit-size) / 8
>
> Patterns like this are generally not encoded in either double int or
> wide-int.   I do not think that anyone has taken the position that all math
> be done in a wide math, only the math on the variables that appear in the
> programs.

Especially sizetype arithmetic - which appears in programs - is generally
done in double_int _exactly_ to cater for the above issue.  And that
assumes (usually without checking) that a double-int can encode
sizeof(size_t) * 8 + 3 bits in precision.  Which would not be true for
a 32bit HWI host and a 64bit target (which is why we have need_hwint64).

>> then I argue that what people want here is this carried out in
>> _infinite_ precision!  Even if byte-size happens to come from
>> a sizetype TREE_INT_CST with 64bit precision.  So either
>> choice - having a fixed-precision representation or an
>> infinite-precision representation - can and will lead to errors
>> done by the programmer.  And as you can easily build a
>> finite precision wrapper around an infinite precision implementation
>> but not the other way around it's obvious to me what the
>> implementation should provide.
>>
>> Richard.
>
> Infinite precision does get rid of the issue that you have to specify the
> precision at the leaves.    However, for the vast majority expression trees
> that get built, the leaves already have their precision in the type or the
> mode.   On the other hand to keep the math sane, the infinite precision
> requires either external truncation (ugly) or specification of the precision
> and many interior nodes of the expression tree (just as ugly as my putting
> it at the constant leaves).

Indeed the only "pretty" operation is with fully infinite precision computes.
But as you most of the time have a single operation per stmt performing
one truncation/extension for the result isn't that bad.  And only supporting
explicit truncation/extension is the 2nd most "pretty" option.  Certainly
the need to provide a precision when constructing wide_int::one () isn't
pretty either ...

> The other problem, which i invite you to use the full power of your c++
> sorcery on, is the one where defining an operator so that wide-int +
> unsigned hwi is either rejected or properly zero extended.    If you can do
> this, I will go along with your suggestion that the internal rep should be
> sign extended.

That's very easy with template specialization (not with overloading as
you might have figured out).

typdef signed long HOST_WIDE_INT;
template <typename T>
struct to_shwi
{
  void to_shwi (HOST_WIDE_INT *s, HOST_WIDE_INT x)
    { s[0] = x; }
};

template <>
struct to_shwi<unsigned HOST_WIDE_INT>
{
  void to_shwi (HOST_WIDE_INT *s, unsigned HOST_WIDE_INT x)
    { s[0] = x; s[1] = 0; }
};

gives a method to properly initialize the sign-extended HWI representation
from any integer type.  Needs additional specializations if init from
long long is suported and long long is bigger than HOST_WIDE_INT.

That is, I suppose your issue was stuff like

   wide_int operator+(unsigned HOST_WIDE_INT);
   wide_int operator+(HOST_WIDE_INT);

then you'd write that as

   template <class T>
   wide_int operator+(T);

and in the implementation use the to_swhi class (or a class providing
exactly what you need) that is specialized for the unsigned HOST_WIDE_INT
case (smaller operands automatically are promoted in the right way to
signed HOST_WIDE_INT).

>  Saying that constants are always sign extended seems ok, but
> there are a huge number of places where we convert unsigned hwis as the
> second operand and i do not want that to be a trap.  I went thru a round of
> this, where i did not post the patch because i could not make this work.
> And the number of places where you want to use an hwi as the second operand
> dwarfs the number of places where you want to use a small integer constant.

See above - this isn't an issue if you use templates for the "overloads".

Richard.

>>>
>>> Kenny
>
>

On 4/8/2013 10:26 AM, Kenneth Zadeck wrote:

> My confusion is what you mean by "we"?   Do you mean "we" the writer of
> the program, "we" the person invoking the compiler by the use command
> line options or "we", your company's implementation of ada?

Sorry, bad usage, The gcc implementation of Ada allows the user to
specify by pragmas how intermediate overflow is handled.
>
> My interpretation of your first email was that it was possible for the
> programmer to do something equivalent to adding attributes surrounding a
> block in the program to control the precision and overflow detection of
> the expressions in the block.   And if this is so, then by the time the
> expression is seen by the middle end of gcc, those attributes will have
> been converted into tree code will evaluate the code in a well defined
> way by both the optimization passes and the target machine.

Yes, that's a correct understanding
>
> Kenny
>

On 4/8/13, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> The other problem, which i invite you to use the full power of
> your c++ sorcery on, is the one where defining an operator so
> that wide-int + unsigned hwi is either rejected or properly
> zero extended.  If you can do this, I will go along with
> your suggestion that the internal rep should be sign extended.
> Saying that constants are always sign extended seems ok, but there
> are a huge number of places where we convert unsigned hwis as
> the second operand and i do not want that to be a trap.  I went
> thru a round of this, where i did not post the patch because i
> could not make this work.  And the number of places where you
> want to use an hwi as the second operand dwarfs the number of
> places where you want to use a small integer constant.

You can use overloading, as in the following, which actually ignores
handling the sign in the representation.

class number {
        unsigned int rep1;
        int representation;
public:
        number(int arg) : representation(arg) {}
        number(unsigned int arg) : representation(arg) {}
        friend number operator+(number, int);
        friend number operator+(number, unsigned int);
        friend number operator+(int, number);
        friend number operator+(unsigned int, number);
};

number operator+(number n, int si) {
    return n.representation + si;
}

number operator+(number n, unsigned int ui) {
    return n.representation + ui;
}

number operator+(int si, number n) {
    return n.representation + si;
}

number operator+(unsigned int ui, number n) {
    return n.representation + ui;
}

If the argument type is of a template type parameter, then
you can test the template type via

    if (std::is_signed<T>::value)
      .... // sign extend
    else
      .... // zero extend

See http://www.cplusplus.com/reference/type_traits/is_signed/.

If you want to handle non-builtin types that are asigne dor unsigned,
then you need to add a specialization for is_signed.

On 4/8/13, Richard Biener <richard.guenther@gmail.com> wrote:
> I advocate the infinite precision signed representation as one
> solution to avoid the issues that come up with your implementation
> (as I currently have access to) which has a representation
> with N bits of precision encoded with M <= N bits and no sign
> information.  That obviously leaves operations on numbers of
> that representation with differing N undefined.  You define it
> by having coded the operations which as far as I can see simply
> assume N is equal for any two operands and the effective sign for
> extending the M-bits encoding to the common N-bits precision is
> "available".  A thorough specification of both the encoding scheme
> and the operation semantics is missing.  I can side-step both of
> these issues nicely by simply using a infinite precision signed
> representation and requiring the client to explicitely truncate /
> extend to a specific precision when required.  I also leave open
> the possibility to have the _encoding_ be always the same as an
> infinite precision signed representation but to always require
> an explicitely specified target precision for each operation
> (which rules out the use of operator overloading).

For efficiency, the machine representation of an infinite precision
number should allow for a compact one-word representation.

  class infinite
  {
    int length;
    union representation
    {
         int inside_word;
         int *outside_words;
    } field;
  public:
    int mod_one_word()
    {
      if (length == 1)
        return field.inside_word;
      else
        return field.outside_word[0];
    }
  };

Also for efficiency, you want to know the modulus at the time you
do the last normal operation on it, not as a subsequent operation.

> Citing your example:
>
>   8 * 10 / 4
>
> and transforming it slightly into a commonly used pattern:
>
>   (byte-size * 8 + bit-size) / 8
>
> then I argue that what people want here is this carried out in
> _infinite_ precision!

But what people want isn't really relevant, what is relevant is
what the language and/or compatiblity requires.  Ideally, gcc
should accurately represent languages with both finite size and
infinite size.

> Even if byte-size happens to come from
> a sizetype TREE_INT_CST with 64bit precision.  So either
> choice - having a fixed-precision representation or an
> infinite-precision representation - can and will lead to errors
> done by the programmer.  And as you can easily build a
> finite precision wrapper around an infinite precision implementation
> but not the other way around it's obvious to me what the
> implementation should provide.

IIUC, the issue here is not the logical chain of implementation, but
the interface that is most helpful to the programmers in getting to
performant, correct code.  I expect we need the infinite precision
forms, but also that having more concise coding for fixed-precision
would be helpful.

For mixed operations, all the languages that I know of promote
smaller operands to larger operands, so I think a reasonable
definition is possible here.

On 4/8/13, Robert Dewar <dewar@adacore.com> wrote:
> On 4/8/2013 10:26 AM, Kenneth Zadeck wrote:
> > On 04/08/2013 10:12 AM, Robert Dewar wrote:
> > > On 4/8/2013 9:58 AM, Kenneth Zadeck wrote:
> > > > yes but the relevant question for the not officially
> > > > static integer constants is "in what precision are those
> > > > operations to be performed in?  I assume that you choose
> > > > gcc types for these operations and you expect the math to
> > > > be done within that type, i.e. exactly the way you expect
> > > > the machine to perform.
> > >
> > > As I explained in an earlier message, *within* a single
> > > expression, we are free to use higher precision, and we provide
> > > modes that allow this up to and including the usea of infinite
> > > precision. That applies not just to constant expressions but
> > > to all expressions.
> >
> > My confusion is what you mean by "we"?  Do you mean "we" the
> > writer of the program, "we" the person invoking the compiler
> > by the use command line options or "we", your company's
> > implementation of ada?
>
> Sorry, bad usage, The gcc implementation of Ada allows the user
> to specify by pragmas how intermediate overflow is handled.

Correct me if I'm wrong, but the Ada standard doesn't require any
particular maximum evaluation precision, but only that you get an
exception if the values exceed the chosen maximum.

> > My interpretation of your first email was that it was possible
> > for the programmer to do something equivalent to adding
> > attributes surrounding a block in the program to control the
> > precision and overflow detection of the expressions in the block.
> > And if this is so, then by the time the expression is seen by
> > the middle end of gcc, those attributes will have been converted
> > into tree code will evaluate the code in a well defined way by
> > both the optimization passes and the target machine.
>
> Yes, that's a correct understanding

In essence, you have moved some of the optimization from the back
end to the front end.  Correct?

On 4/8/2013 5:12 PM, Lawrence Crowl wrote:

(BTW, you *really* don't need to quote entire messages, I find
it rather redundant for the entire thread to be in every message,
we all have thread following mail readers!)

> Correct me if I'm wrong, but the Ada standard doesn't require any
> particular maximum evaluation precision, but only that you get an
> exception if the values exceed the chosen maximum.

Right, that's at run-time, at compile-time for static expressions,
infinite precision is required.

But at run-time, all three of the modes we provide are
standard conforming.

> In essence, you have moved some of the optimization from the back
> end to the front end.  Correct?

Sorry, I don't quite understand that. If you are syaing that the
back end could handle this widening for intermediate values, sure
it could, this is the kind of thing that can be done at various
different places.
>

In some sense you have to think in terms of three worlds:
1) what you call "compile-time static expressions" is one world which in 
gcc is almost always done by the front ends.
2) the second world is what the optimizers can do.   This is not 
compile-time static expressions because that is what the front end has 
already done.
3) there is run time.

My view on this is that optimization is just doing what is normally done 
at run time but doing it early.   From that point of view, we are if not 
required, morally obligated to do thing in the same way that the 
hardware would have done them.    This is why i am so against richi on 
wanting to do infinite precision.    By the time the middle or the back 
end sees the representation, all of the things that are allowed to be 
done in infinite precision have already been done.   What we are left 
with is a (mostly) strongly typed language that pretty much says exactly 
what must be done. Anything that we do in the middle end or back ends in 
infinite precision will only surprise the programmer and make them want 
to use llvm.

Kenny

On 04/08/2013 05:36 PM, Robert Dewar wrote:
> On 4/8/2013 5:12 PM, Lawrence Crowl wrote:
>
> (BTW, you *really* don't need to quote entire messages, I find
> it rather redundant for the entire thread to be in every message,
> we all have thread following mail readers!)
>
>> Correct me if I'm wrong, but the Ada standard doesn't require any
>> particular maximum evaluation precision, but only that you get an
>> exception if the values exceed the chosen maximum.
>
> Right, that's at run-time, at compile-time for static expressions,
> infinite precision is required.
>
> But at run-time, all three of the modes we provide are
> standard conforming.
>
>> In essence, you have moved some of the optimization from the back
>> end to the front end.  Correct?
>
> Sorry, I don't quite understand that. If you are syaing that the
> back end could handle this widening for intermediate values, sure
> it could, this is the kind of thing that can be done at various
> different places.
>>
>

On 4/8/2013 5:46 PM, Kenneth Zadeck wrote:
> In some sense you have to think in terms of three worlds:
> 1) what you call "compile-time static expressions" is one world which in
> gcc is almost always done by the front ends.
> 2) the second world is what the optimizers can do.   This is not
> compile-time static expressions because that is what the front end has
> already done.
> 3) there is run time.
>
> My view on this is that optimization is just doing what is normally done
> at run time but doing it early.   From that point of view, we are if not
> required, morally obligated to do thing in the same way that the
> hardware would have done them.    This is why i am so against richi on
> wanting to do infinite precision.    By the time the middle or the back
> end sees the representation, all of the things that are allowed to be
> done in infinite precision have already been done.   What we are left
> with is a (mostly) strongly typed language that pretty much says exactly
> what must be done. Anything that we do in the middle end or back ends in
> infinite precision will only surprise the programmer and make them want
> to use llvm.

That may be so in C, in Ada it would be perfectly reasonable to use
infinite precision for intermediate results in some cases, since the
language standard specifically encourages this approach.

On Apr 8, 2013, at 2:48 PM, Robert Dewar <dewar@adacore.com> wrote:
> That may be so in C, in Ada it would be perfectly reasonable to use
> infinite precision for intermediate results in some cases, since the
> language standard specifically encourages this approach.

gcc lacks an infinite precision plus operator?!  :-)

On 4/8/2013 6:34 PM, Mike Stump wrote:
> On Apr 8, 2013, at 2:48 PM, Robert Dewar <dewar@adacore.com> wrote:
>> That may be so in C, in Ada it would be perfectly reasonable to use
>> infinite precision for intermediate results in some cases, since the
>> language standard specifically encourages this approach.
>
> gcc lacks an infinite precision plus operator?!  :-)
>
Right, that's why we do everything in the front end in the
case of Ada. But it would be perfectly reasonable for the
back end to do this substitution.

On 04/08/2013 06:45 PM, Robert Dewar wrote:
> On 4/8/2013 6:34 PM, Mike Stump wrote:
>> On Apr 8, 2013, at 2:48 PM, Robert Dewar <dewar@adacore.com> wrote:
>>> That may be so in C, in Ada it would be perfectly reasonable to use
>>> infinite precision for intermediate results in some cases, since the
>>> language standard specifically encourages this approach.
>>
>> gcc lacks an infinite precision plus operator?!  :-)
>>
> Right, that's why we do everything in the front end in the
> case of Ada. But it would be perfectly reasonable for the
> back end to do this substitution.
but there is no way in the current tree language to convey which ones 
you can and which ones you cannot.

On 4/8/2013 7:46 PM, Kenneth Zadeck wrote:
>
> On 04/08/2013 06:45 PM, Robert Dewar wrote:
>> On 4/8/2013 6:34 PM, Mike Stump wrote:
>>> On Apr 8, 2013, at 2:48 PM, Robert Dewar <dewar@adacore.com> wrote:
>>>> That may be so in C, in Ada it would be perfectly reasonable to use
>>>> infinite precision for intermediate results in some cases, since the
>>>> language standard specifically encourages this approach.
>>>
>>> gcc lacks an infinite precision plus operator?!  :-)
>>>
>> Right, that's why we do everything in the front end in the
>> case of Ada. But it would be perfectly reasonable for the
>> back end to do this substitution.
> but there is no way in the current tree language to convey which ones
> you can and which ones you cannot.

Well the back end has all the information to figure this out I think!
But anyway, for Ada, the current situation is just fine, and has
the advantage that the -gnatG expanded code listing clearly shows in
Ada source form, what is going on.
>

On Mon, Apr 8, 2013 at 10:39 PM, Lawrence Crowl <crowl@google.com> wrote:
> On 4/8/13, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>> The other problem, which i invite you to use the full power of
>> your c++ sorcery on, is the one where defining an operator so
>> that wide-int + unsigned hwi is either rejected or properly
>> zero extended.  If you can do this, I will go along with
>> your suggestion that the internal rep should be sign extended.
>> Saying that constants are always sign extended seems ok, but there
>> are a huge number of places where we convert unsigned hwis as
>> the second operand and i do not want that to be a trap.  I went
>> thru a round of this, where i did not post the patch because i
>> could not make this work.  And the number of places where you
>> want to use an hwi as the second operand dwarfs the number of
>> places where you want to use a small integer constant.
>
> You can use overloading, as in the following, which actually ignores
> handling the sign in the representation.
>
> class number {
>         unsigned int rep1;
>         int representation;
> public:
>         number(int arg) : representation(arg) {}
>         number(unsigned int arg) : representation(arg) {}
>         friend number operator+(number, int);
>         friend number operator+(number, unsigned int);
>         friend number operator+(int, number);
>         friend number operator+(unsigned int, number);
> };
>
> number operator+(number n, int si) {
>     return n.representation + si;
> }
>
> number operator+(number n, unsigned int ui) {
>     return n.representation + ui;
> }
>
> number operator+(int si, number n) {
>     return n.representation + si;
> }
>
> number operator+(unsigned int ui, number n) {
>     return n.representation + ui;
> }

That does not work for types larger than int/unsigned int as HOST_WIDE_INT
usually is (it's long / unsigned long).  When you pass an int or unsigned int
to

number operator+(unsigned long ui, number n);
number operator+(long ui, number n)

you get an ambiguity.  You can "fix" that by relying on template argument
deduction and specialization instead of on overloading and integer conversion
rules.

> If the argument type is of a template type parameter, then
> you can test the template type via
>
>     if (std::is_signed<T>::value)
>       .... // sign extend
>     else
>       .... // zero extend
>
> See http://www.cplusplus.com/reference/type_traits/is_signed/.

Yes, if we want to use the standard library.  For what integer types
is std::is_signed required to be implemented in C++98 (long long?)?
Consider non-GCC host compilers.

Richard.

> If you want to handle non-builtin types that are asigne dor unsigned,
> then you need to add a specialization for is_signed.
>
> --
> Lawrence Crowl

On 04/09/2013 01:47 AM, Robert Dewar wrote:
> Well the back end has all the information to figure this out I think!
> But anyway, for Ada, the current situation is just fine, and has
> the advantage that the -gnatG expanded code listing clearly shows in
> Ada source form, what is going on.

Isn't this a bit optimistic, considering that run-time overflow checking 
currently does not use existing hardware support?

On 4/9/2013 5:39 AM, Florian Weimer wrote:
> On 04/09/2013 01:47 AM, Robert Dewar wrote:
>> Well the back end has all the information to figure this out I think!
>> But anyway, for Ada, the current situation is just fine, and has
>> the advantage that the -gnatG expanded code listing clearly shows in
>> Ada source form, what is going on.
>
> Isn't this a bit optimistic, considering that run-time overflow checking
> currently does not use existing hardware support?

Not clear what you mean here, we don't rely on the back end for run-time
overflow checking. What is over-optimistic here?

BTW, existing hardware support can be a dubious thing, you have
to be careful to evaluate costs, for instance you don't want to
use INTO on modern x86 targets!
>

On 04/09/2013 02:41 PM, Robert Dewar wrote:
> On 4/9/2013 5:39 AM, Florian Weimer wrote:
>> On 04/09/2013 01:47 AM, Robert Dewar wrote:
>>> Well the back end has all the information to figure this out I think!
>>> But anyway, for Ada, the current situation is just fine, and has
>>> the advantage that the -gnatG expanded code listing clearly shows in
>>> Ada source form, what is going on.
>>
>> Isn't this a bit optimistic, considering that run-time overflow checking
>> currently does not use existing hardware support?
>
> Not clear what you mean here, we don't rely on the back end for run-time
> overflow checking. What is over-optimistic here?
>
> BTW, existing hardware support can be a dubious thing, you have
> to be careful to evaluate costs, for instance you don't want to
> use INTO on modern x86 targets!

It's not aobut INTO, just access to the overflow flag.

A simple function which adds its two Integer arguments compiles to this 
machine code (with -gnato -O2):

	.cfi_startproc
	movslq	%esi, %rax
	movslq	%edi, %rdx
	addq	%rax, %rdx
	movl	$2147483648, %eax
	addq	%rax, %rdx
	movl	$4294967295, %eax
	cmpq	%rax, %rdx
	ja	.L5
	leal	(%rsi,%rdi), %eax
	ret
.L5:
	pushq	%rax
	.cfi_def_cfa_offset 16
	movl	$3, %esi
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	__gnat_rcheck_10
	.cfi_endproc

While it could be like this:

	.cfi_startproc
	movl    %edi, %eax
	addl    %esi, %eax
	jo	.L5
	ret
.L5:
	pushq	%rax
	.cfi_def_cfa_offset 16
	movl	$3, %esi
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	__gnat_rcheck_10
	.cfi_endproc

Admittedly, I haven't benchmarked it, but at least from the code size 
aspect, it's a significant improvement.

On Tue, Apr 9, 2013 at 5:36 PM, Lawrence Crowl <crowl@google.com> wrote:
>
> On Apr 9, 2013 2:02 AM, "Richard Biener" <richard.guenther@gmail.com> wrote:
>>
>> On Mon, Apr 8, 2013 at 10:39 PM, Lawrence Crowl <crowl@google.com> wrote:
>> > On 4/8/13, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>> >> The other problem, which i invite you to use the full power of
>> >> your c++ sorcery on, is the one where defining an operator so
>> >> that wide-int + unsigned hwi is either rejected or properly
>> >> zero extended.  If you can do this, I will go along with
>> >> your suggestion that the internal rep should be sign extended.
>> >> Saying that constants are always sign extended seems ok, but there
>> >> are a huge number of places where we convert unsigned hwis as
>> >> the second operand and i do not want that to be a trap.  I went
>> >> thru a round of this, where i did not post the patch because i
>> >> could not make this work.  And the number of places where you
>> >> want to use an hwi as the second operand dwarfs the number of
>> >> places where you want to use a small integer constant.
>> >
>> > You can use overloading, as in the following, which actually ignores
>> > handling the sign in the representation.
>> >
>> > class number {
>> >         unsigned int rep1;
>> >         int representation;
>> > public:
>> >         number(int arg) : representation(arg) {}
>> >         number(unsigned int arg) : representation(arg) {}
>> >         friend number operator+(number, int);
>> >         friend number operator+(number, unsigned int);
>> >         friend number operator+(int, number);
>> >         friend number operator+(unsigned int, number);
>> > };
>> >
>> > number operator+(number n, int si) {
>> >     return n.representation + si;
>> > }
>> >
>> > number operator+(number n, unsigned int ui) {
>> >     return n.representation + ui;
>> > }
>> >
>> > number operator+(int si, number n) {
>> >     return n.representation + si;
>> > }
>> >
>> > number operator+(unsigned int ui, number n) {
>> >     return n.representation + ui;
>> > }
>>
>> That does not work for types larger than int/unsigned int as HOST_WIDE_INT
>> usually is (it's long / unsigned long).  When you pass an int or unsigned
>> int
>> to
>>
>> number operator+(unsigned long ui, number n);
>> number operator+(long ui, number n)
>>
>> you get an ambiguity.  You can "fix" that by relying on template argument
>> deduction and specialization instead of on overloading and integer
>> conversion
>> rules.
>
> Ah, I hadn't quite gotten the point. This problem is being fixed in the
> standard, but that won't help GCC anytime soon.
>
>>
>> > If the argument type is of a template type parameter, then
>> > you can test the template type via
>> >
>> >     if (std::is_signed<T>::value)
>> >       .... // sign extend
>> >     else
>> >       .... // zero extend
>> >
>> > See http://www.cplusplus.com/reference/type_traits/is_signed/.
>>
>> Yes, if we want to use the standard library.  For what integer types
>> is std::is_signed required to be implemented in C++98 (long long?)?
>
> It is in C++03/TR1, which is our base requirement. Otherwise, we can test
> ~(T)0<(T)0.

Yeah, I think we want to test ~(T)0<(T)0 here.  Relying on C++03/TR1 is
too obscure if there is an easy workaround.

Richard.

>> Consider non-GCC host compilers.
>>
>> Richard.
>>
>> > If you want to handle non-builtin types that are asigne dor unsigned,
>> > then you need to add a specialization for is_signed.
>> >
>> > --
>> > Lawrence Crowl

On Apr 10, 2013, at 12:38 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> Yeah, I think we want to test ~(T)0<(T)0 here.

Thanks Lawrence, in the next version of the patch, you will discover this at the bottom if you look hard.  :-)

On 04/10/2013 12:02 PM, Mike Stump wrote:
> On Apr 10, 2013, at 12:38 AM, Richard Biener <richard.guenther@gmail.com> wrote:
>> Yeah, I think we want to test ~(T)0<(T)0 here.
> Thanks Lawrence, in the next version of the patch, you will discover this at the bottom if you look hard.  :-)
actually closer to the middle.

Richard Biener <richard.guenther@gmail.com> writes:
>> At the rtl level your idea does not work.   rtl constants do not have a mode
>> or type.
>
> Which is not true and does not matter.  I tell you why.  Quote:

It _is_ true, as long as you read "rtl constants" as "rtl integer constants" :-)

> +#if TARGET_SUPPORTS_WIDE_INT
> +
> +/* Match CONST_*s that can represent compile-time constant integers.  */
> +#define CASE_CONST_SCALAR_INT \
> +   case CONST_INT: \
> +   case CONST_WIDE_INT
>
> which means you are only replacing CONST_DOUBLE with wide-int.
> And _all_ CONST_DOUBLE have a mode.  Otherwise you'd have no
> way of creating the wide-int in the first place.

No, integer CONST_DOUBLEs have VOIDmode, just like CONST_INT.
Only floating-point CONST_DOUBLEs have a "real" mode.

>> I understand that this makes me vulnerable to the argument that we should
>> not let the rtl level ever dictate anything about the tree level, but the
>> truth is that a variable len rep is almost always used for big integers.
>> In our code, most constants of large types are small numbers.   (Remember i
>> got into this because the tree constant prop thinks that left shifting any
>> number by anything greater than 128 is always 0 and discovered that that was
>> just the tip of the iceberg.) But mostly i support the decision to canonize
>> numbers to the smallest number of HWIs because most of the algorithms to do
>> the math can be short circuited.    I admit that if i had to effectively
>> unpack most numbers to do the math, that the canonization would be a waste.
>> However, this is not really relevant to this conversation.   Yes, you could
>> get rid of the len, but this such a small part of picture.
>
> Getting rid of 'len' in the RTX storage was only a question of whether it
> is an efficient way to go forward.  And with considering to unify
> CONST_INTs and CONST_WIDE_INTs it is not.  And even for CONST_WIDE_INTs
> (which most of the time would be 2 HWI storage, as otherwise you'd use
> a CONST_INT) it would be an improvement.

FWIW, I don't really see any advantage in unifying CONST_INT and
CONST_WIDE_INT, for the reasons Kenny has already given.  CONST_INT
can represent a large majority of the integers and it is already a
fairly efficient representation.

It's more important that we don't pick a design that forces one
choice or the other.  And I think Kenny's patch achieves that goal,
because the choice is hidden behind macros and behind the wide_int
interface.

Thanks,
Richard

Richard Sandiford <rdsandiford@googlemail.com> wrote:

>Richard Biener <richard.guenther@gmail.com> writes:
>>> At the rtl level your idea does not work.   rtl constants do not
>have a mode
>>> or type.
>>
>> Which is not true and does not matter.  I tell you why.  Quote:
>
>It _is_ true, as long as you read "rtl constants" as "rtl integer
>constants" :-)
>
>> +#if TARGET_SUPPORTS_WIDE_INT
>> +
>> +/* Match CONST_*s that can represent compile-time constant integers.
> */
>> +#define CASE_CONST_SCALAR_INT \
>> +   case CONST_INT: \
>> +   case CONST_WIDE_INT
>>
>> which means you are only replacing CONST_DOUBLE with wide-int.
>> And _all_ CONST_DOUBLE have a mode.  Otherwise you'd have no
>> way of creating the wide-int in the first place.
>
>No, integer CONST_DOUBLEs have VOIDmode, just like CONST_INT.
>Only floating-point CONST_DOUBLEs have a "real" mode.

I stand corrected. Now that's one more argument for infinite precision constants, as the mode is then certainly provided by the operations similar to the sign. That is, the mode (or size, or precision) of 1 certainly does not matter.

>>> I understand that this makes me vulnerable to the argument that we
>should
>>> not let the rtl level ever dictate anything about the tree level,
>but the
>>> truth is that a variable len rep is almost always used for big
>integers.
>>> In our code, most constants of large types are small numbers.  
>(Remember i
>>> got into this because the tree constant prop thinks that left
>shifting any
>>> number by anything greater than 128 is always 0 and discovered that
>that was
>>> just the tip of the iceberg.) But mostly i support the decision to
>canonize
>>> numbers to the smallest number of HWIs because most of the
>algorithms to do
>>> the math can be short circuited.    I admit that if i had to
>effectively
>>> unpack most numbers to do the math, that the canonization would be a
>waste.
>>> However, this is not really relevant to this conversation.   Yes,
>you could
>>> get rid of the len, but this such a small part of picture.
>>
>> Getting rid of 'len' in the RTX storage was only a question of
>whether it
>> is an efficient way to go forward.  And with considering to unify
>> CONST_INTs and CONST_WIDE_INTs it is not.  And even for
>CONST_WIDE_INTs
>> (which most of the time would be 2 HWI storage, as otherwise you'd
>use
>> a CONST_INT) it would be an improvement.
>
>FWIW, I don't really see any advantage in unifying CONST_INT and
>CONST_WIDE_INT, for the reasons Kenny has already given.  CONST_INT
>can represent a large majority of the integers and it is already a
>fairly efficient representation.
>
>It's more important that we don't pick a design that forces one
>choice or the other.  And I think Kenny's patch achieves that goal,
>because the choice is hidden behind macros and behind the wide_int
>interface.

Not unifying const-int and double-int in the end would be odd.

Richard.

>Thanks,
>Richard

Richard Biener <richard.guenther@gmail.com> writes:
> Richard Sandiford <rdsandiford@googlemail.com> wrote:
>>Richard Biener <richard.guenther@gmail.com> writes:
>>>> At the rtl level your idea does not work.   rtl constants do not
>>have a mode
>>>> or type.
>>>
>>> Which is not true and does not matter.  I tell you why.  Quote:
>>
>>It _is_ true, as long as you read "rtl constants" as "rtl integer
>>constants" :-)
>>
>>> +#if TARGET_SUPPORTS_WIDE_INT
>>> +
>>> +/* Match CONST_*s that can represent compile-time constant integers.
>> */
>>> +#define CASE_CONST_SCALAR_INT \
>>> +   case CONST_INT: \
>>> +   case CONST_WIDE_INT
>>>
>>> which means you are only replacing CONST_DOUBLE with wide-int.
>>> And _all_ CONST_DOUBLE have a mode.  Otherwise you'd have no
>>> way of creating the wide-int in the first place.
>>
>>No, integer CONST_DOUBLEs have VOIDmode, just like CONST_INT.
>>Only floating-point CONST_DOUBLEs have a "real" mode.
>
> I stand corrected. Now that's one more argument for infinite precision
> constants, as the mode is then certainly provided by the operations
> similar to the sign. That is, the mode (or size, or precision) of 1
> certainly does not matter.

I disagree.  Although CONST_INT and CONST_DOUBLE don't _store_ a mode,
they are always interpreted according to a particular mode.  It's just
that that mode has to be specified separately.  That's why so many
rtl functions have (enum machine_mode, rtx) pairs.

Infinite precision seems very alien to rtl, where everything is
interpreted according to a particular mode (whether that mode is
stored in the rtx or not).

For one thing, I don't see how infinite precision could work in an
environment where signedness often isn't defined.  E.g. if you optimise
an addition of two rtl constants, you don't know (and aren't supposed
to know) whether the values involved are "signed" or "unsigned".  With
fixed-precision arithmetic it doesn't matter, because both operands must
have the same precision, and because bits outside the precision are not
significant.  With infinite precision arithmetic, the choice carries
over to the next operation.  E.g., to take a 4-bit example, you don't
know when constructing a wide_int from an rtx whether 0b1000 represents
8 or -8.  But if you have no precision to say how many bits are significant,
you have to pick one.  Which do you choose?  And why should we have to
make a choice at all?  (Note that this is a different question to
whether the internal wide_int representation is sign-extending or not,
which is purely an implementation detail.  The same implementation
principle applies to CONST_INTs: the HWI in a CONST_INT is always
sign-extended from the msb of the represented value, although of course
the CONST_INT itself doesn't tell you which bit the msb is; that has to
be determined separately.)

A particular wide_int isn't, and IMO shouldn't be, inherently signed
or unsigned.  The rtl model is that signedness is a question of
interpretation rather than representation.  I realise trees are
different, because signedness is a property of the type rather
than operations on the type, but I still think fixed precision
works with both tree and rtl whereas infinite precision doesn't
work with rtl.

I also fear there are going to be lots of bugs where we forget to
truncate the result of an N-bit operation from "infinite" precision
to N bits before using it in the next operation (as per Kenny's ring
explanation).  With finite precision, and with all-important asserts
that the operands have consistent precisions, we shouldn't have any
hidden bugs like that.

If there are parts of gcc that really want to do infinite-precision
arithmetic, mpz_t ought to be as good as anything.

Thanks,
Richard