Re: Ada front-end depends on signed overflow

[Michael Veksler <VEKSLER at il dot ibm dot com>]

Paul Schlie <schlie@comcast.net> wrote on 08/06/2005 21:16:46:

> > From: Michael Veksler <VEKSLER@il.ibm.com>
> >> Paul Schlie wrote on 08/06/2005 17:53:04:
> >> - I would have if someone could provide a concrete example of an
> >>   undefined behavior which produces a reliably useful/predictable
result.
> >>
> > Well this is a simple hackery quiz, which is irrelevant to GCC.
> >
> >       1: int a, b;
> >       2: int f() {   return b++; }
> >       3: int main(int argc)
> >       4: {
> >       5:   b= argc;
> >       6:   a= b + f();  /* a==b*2  or  a==b*2+1 */
> >       7:   a= a/2;      /* a=b */
> >       8:   return a;
> >       9: }
> >
> > If one would claim that a is totally unconstrained at line 6, then this
> > example will be invalid. In that case, I can give a more restricted
> > example, where 'a' is computed speculatively and is discarded
> > in exactly the same cases when it is undefined.
>
> - unless I misunderstand, it actually is undefined if the value of argc
>   may be as large as the largest representable positive int value, if
>   both signed int overflows and evaluation order are
undefined/unspecified.
>

It is undefined due to evaluation order.
Is it:
      tmp= b;     // b is fetched first.
      a= tmp + b++; // then f() is called and added
or is it:
      tmp= b++;   // f() is called first.
      a= b + tmp; // then b is fetched and added

Please note that this has nothing to do with overflow.
I argue that although 'a' is undefined due to
evaluation order, it may still be used as long as
its undefined-ness is constrained (which the std may
or may not guarantee).
Anyway, as I said, it is more of a quiz than a practical
question and example. You may come up with a bizarre
example where it makes some sense.


>   (although confess to missing your point, as it's not clear how an
>   undefined behavior is productively contributing to the observation that
>   a == argc if agc++ doesn't overflow or evaluated l-r; as opposed to
>   observing that if the evaluation order were fixed l-r and not
undefined,
>   then the optimization may be derived?)
>

Now it is me who missed the above point. What is 1-r ?

> > Oh, well here it is.
> >       1: int a, b, c;
> >       2: int f() {  return a ? b++ : b; }
> >       3: int main()
> >       4: {
> >       5:   scanf("%d %d", &a, &b);
> >       6:   c= b + f();   /* C is undefined if a != 0*/
> >       7:   if (a)  c = b;
> >       8:   return c;
> >       9: }
> >
> > This example is predictable. I argue that it may be also
> > useful performance-wise to do speculative computations.
>
> - I believe it's subject to the same problem?
>
No, here also the result is undefined due to evaluation
order. My point in this example is that you may operate
on 'c' which is defined for some inputs and undefined
for others, and still get an observably consistent results.
If you know that the result may be undefined only when you
do not intend to use it, then you don't care about it
(if guaranteed not to get SIGBUS).

As other have noted, the effects of constraining the
compiler to "platform defined" behavior, you lose
performance.
For example:
      double a, b;
      int f();
      int main()
      {
        int i;
        for (i=0 ; i < 1000000 ; ++i)
           b += (double)f() + sin(a);
        return foo(b);
      }
Let's assume that on a given platform the FPU
can calculate sin(a) in parallel to f().

The compiler cannot prove that f() does not
modify a, because f() is not given here or
because it is intractable.

If, calls to f() and sin(a) take 10 ns each, then
calculating them in parallel will save 50% of the
total run-time. To do that, the compiler will have
to change the order of function calls.

You may argue that even a x100 speed up is not worth
an undefined behavior. I will argue that in this case
most programmers will avoid modifying 'a' inside f()
anyway (due to maintainability) and will avoid the
undefined result.

I think that normative code should be penalized for
the possibility of bizarre code. This bizarre code
should be fixed anyway to avoid maintenance
nightmares.