Comments on the suggestion to use infinite precision math for wide int.

[Richard Biener]

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