undefined | Better HN

0 pointscataphract6y ago0 comments

Signed overflow being undefined behavior allows optimizations that wouldn't otherwise be possible

Quoting http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

> This behavior enables certain classes of optimizations that are important for some code. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion. A more important optimization that this allows is for "<=" loops like this:

> for (i = 0; i <= N; ++i) { ... }

> In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.

0 comments

3 comments · 3 top-level

userbinator6y ago

I've always thought that assuming such things should be wrong, because if you were writing the Asm manually, you would certainly think about it and NOT optimise unless you had a very good reason why it won't overflow. Likewise, I think that unless the compiler can prove that it, it should, like the sane human, refrain from making the assumption.

1 more reply

rbultje6y ago

> for (i = 0; i <= N; ++i) { ... }

The worst thing is that people take it as acceptable that this loop is going to operate differently upon overflow (e.g. assume N is TYPE_MAX) depending on whether i or N are signed vs. unsigned.

1 more reply

gwd6y ago

So in a corner case where you have a loop that iterates over all integer values (when does this ever happen?) you can optimize your loop. As a consequence, signed integer arithmetic is very difficult to write while avoiding UB, even for skilled practitioners. Do you think that's a useful trade-off, and do you think anything can be done for those of us who think it's not?

3 more replies

j / k navigate · click thread line to collapse