Summation on HP 42S

[ijabbott]

(09-29-2018 06:15 PM)Thomas Okken Wrote:  

(09-29-2018 04:06 PM)ijabbott Wrote:  Not my example, but consider this C program:

That "example" tests the behavior of code on integer overflow, which is undefined in C, so both the unoptimized and the optimized versions fall into the category of Not Even Wrong.

If you operate under the assumption that integer overflow should behave like the underlying CPU does, then your unoptimized version behaves like you would expect on a CPU with 32-bit signed integers, and the optimized version is wrong. Your assertion that there is no bug there doesn't make it so;

Just to clarify, I am asserting that there is no bug in the optimizer in this case because the problem does indeed lie in the program source code itself as you stated. However, this same compiler at the same optimization level will happily add a signed integer variable to another integer of the same sign without checking for overflow, producing a result of opposite sign by 2's complement rule when it does in fact overflow, so the programmer might be forgiven for thinking the compiler would do the same thing for the loop in the code I posted.

There are plenty of real life examples of code that assumes that signed integer values will wrap around and change sign on overflow, and in most cases they get away with it until an updated compiler with a slightly more aggressive optimizer throws a spanner in the works. One old real-life example of such code is the implementation of the mktime() function from version 2.5 of the GNU C Library (long since fixed). It performed some signed integer addition and checked the resulting values for overflow afterwards. (EDIT: An optimizing compiler could legitimately deem those checks to be unnecessary and remove them, stymying the efforts of the programmer to perform error detection.) See CERT's Dangerous Optimizations and the Loss of Causality for that and other examples.

Quote:if a shift left is supposed to behave like on the metal, then the optimizer needs to consider the possibility that a positive signed integer might turn negative or become zero when shifted left, and the optimizer in your example obviously doesn't do that.

In practice, I assume the gcc maintainers would not consider it a bug, again, because the C standard specifically states that behavior on integer overflow is undefined.

Curiously, replacing `i += i;` with `i <<= 1` in the code I posted doesn't make the GCC optimizer (at least for GCC 7 and 8) generate an infinite loop like the original version. In fact it doesn't generate a loop or any variables at all for function `f`; it just returns the value 31. I don't know why it ends up behaving differently for this minor variant of the code, since both versions exhibit undefined behaviour, but technically it can do whatever it likes here and it wouldn't be considered an optimizer bug.