5 ms·
> Granted, there are cases where a compiler can take proper advantage of such optimizations, but it's emphatically not the case that the only alternative to the
by pcwalton 11y ago
> Granted, there are cases where a compiler can take proper advantage of such optimizations, but it's emphatically not the case that the only alternative to the current "nasal daemon" approach is disabling all loop optimizations. Simply changing "undefined" to "implementation defined" would satisfy a majority of the objections.
No. Since a huge number of loop optimizations are dependent on trip count detection, this is not in fact the case. Loop trip count detection is ruined by making signed overflow implementation defined.
See this thread from just last week explaining this: https://news.ycombinator.com/item?id=11653940 https://news.ycombinator.com/item?id=11653940
Additionally, there's less of a difference between "undefined" and "implementation defined" than you might think. Consider the example in the original post:
if (x + y < x) {
return 0; /* Overflow */
}
length = x + y;
With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow, and comparisons on undefined values are themselves undefined. If you want the compiler to do anything else, then you're proposing a drastic overhaul of (for example) LLVM's notion of "undef" [1], one that would have massive consequences for optimization.
[1]: http://llvm.org/docs/LangRef.html#undefined-values http://llvm.org/docs/LangRef.html#undefined-values
- nkurz 11y agoSince a huge number of loop optimizations are dependent on trip count detection, this is not in fact the case. Loop trip count detection is ruined by making signed overflow implementation defined. Could you offer a good example of a loop where performance of a human written lop would suffer if the loop counter was changed from int64_t to uint64_t? I'm sure they exist, but I wonder if I'm underestimating the severity. With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow Well, no, at least the way I'm viewing "implementation defined". If the signed addition is implementation defined, I'd think that by definition "x + y" never becomes an undefined value. As I'm sure you realize (but others might not), x64 doesn't have separate add-signed-32-bit and add-unsigned-32-bit instructions. So on x64, I'd hope that a sane implementation would simply define signed addition as "ask the processor to add x to y and interpret the result as signed". I don't think this would require any overhaul of the notion of "undef"?
- pcwalton 11y ago> Well, no, at least the way I'm viewing "implementation defined". If the signed addition is implementation defined, I'd think that by definition "x + y" never becomes an undefined value. See my other reply. A compiler can legally rewrite the expression into "(uint64_t)x + (uint64_t)y > UINT_MAX ? undef : true" per your rule.
- efaref 11y agoAm I the only one who thinks that writing if (x + y < x) is utterly insane? It completely breaks the abstraction of algebra that's being used in the language. Much better would be: if (ADDITION_WOULD_OVERFLOW_INT(x, y)) { ... } This is (a) far easier to read, and (b) more likely to be more correctly implemented as something like: #define ADDITION_WOULD_OVERFLOW_INT(a, b) \ (((a) > 0 && (b) > 0 && (b) > INT_MAX - (a)) || \ ((a) < 0 && (b) < 0 && (b) < INT_MIN - (a))) For bonus points you could write this as part of the compiler support library to derive the types and limits automatically, or even define it as part of the compiler. Why do GCC/clang not have: __builtin_addition_would_overflow(a, b) ?
- Kristine1975 11y ago>Why do GCC/clang not have: __builtin_addition_would_overflow(a, b) But they do: https://news.ycombinator.com/item?id=11711608 https://news.ycombinator.com/item?id=11711608 :-)
- efaref 11y agoThe API for those is equally insane (they replace the arithmetic operation). See my sibling comment for a more reasonable proposal.
- kevinnk 11y ago> Why do GCC/clang not have: __builtin_addition_would_overflow(a, b) Both GCC and Clang have __builtin_add_overflow, which as far as I can tell do exactly what you're proposing.
- efaref 11y agoA comment below reminded me of these: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins..., which are close, but have an insane API as they replace your arithmetic operations with ugliness. I think they can be fixed with sensible macros, though: #define ADDITION_WOULD_OVERFLOW(a, b) \ ({ typeof((a) + (b)) __r; __builtin_add_overflow((a), (b), &__r); }) Hopefully the compiler would optimise: if (ADDITION_WOULD_OVERFLOW(a, b)) { return 0; } return a + b; to only do the addition once.
- tomp 11y ago> Additionally, there's less of a difference between "undefined" and "implementation defined" than you might think. No. If `x + y < x` is "implementation defined", then an "undef" value would never even come into existence!
- pcwalton 11y agoA compiler can legally rewrite the expression into "(uint64_t)x + (uint64_t)y > UINT_MAX ? undef : true" per the rule suggested by nkurz. This makes the undef value show up.