5 ms·

The most impressive example I've ever seen of this kind of compiler cleverness is the following function from the "convoluted isEven" competition: bool isE

by ufo 5y ago

The most impressive example I've ever seen of this kind of compiler cleverness is the following function from the "convoluted isEven" competition: bool isEven(int n) { return n == 0 || !isEven(n + 1); } Clang somehow optimizes it to a constant-time implementation, even if we use "unsigned"! https://gcc.godbolt.org/z/nGbn1T https://gcc.godbolt.org/z/nGbn1T

whimsicalism 5y ago
Is this code not relying on UB? Seems like it could/should be optimized to `return true`
- carnitine 5y ago
  What’s the UB?
  - deleted 5y ago
    [deleted]
  - whimsicalism 5y ago
    Calling it on any positive int causes signed integer overflow, which is UB.
  - nawgz 5y ago
    signed integer overflow for positive N
- edflsafoiewq 5y ago
  It's only UB for positive n. For negative n, it is an is-even test, so it can't be optimized to return true.
  - whimsicalism 5y ago
    Oh yeah - negative numbers exist, doh!
- poizan42 5y ago
  It's UB for positive integers, so the compiler can assume it never happens. It's correct for negative integers, so the compiler just optimizes it for negative integers and ignores the positive ones - in this case with the end result that it works for positive integers as well. If the argument is changed to unsigned int then it seems to be correct and portable because the C standard[1] requires UINT_MAX to be of the form 2^n - 1 (which makes it wrap from odd to even when overflowing). So the one with signed argument is UB for positive integers but happens to work by accident (but the nasal demons may still lurk just around the corner, e.g. the compiler may also assume that it's never called with a positive argument which may affect the compilation of callers). The one with unsigned argument is correct because unsigned overflow is well-defined to wrap around to zero, combined with the restrictions on max unsigned int. [1]: From C17 6.2.6.2: For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2*(N-1), so that objects of that type shall be capable of representing values from 0 to 2*(N-1) using a pure binary representation; this shall be known as the value representation.
joosters 5y ago
Isn't the unsigned version the correct one? Presumably the int version will hit the same problem as in the original article, in that the C spec says that ints are not treated as overflowing? (i.e. the compiler cannot assume that adding one will eventually turn negative and then later on reach 0)
- DSMan195276 5y ago
  Yes that's right - unsigned is defined to wrap, but ints have undefined behavior if you add to the max value (or do other silly things with them). Thus the int version given could be optimized to do whatever when a positive integer is passed, since it only doesn't have UB when negatives or zero are passed.
- BeeOnRope 5y ago
  Well the int version returns the correct answer for "empty()" unlike unsigned. The size of a list of 2^32-1 elements should not be reported as zero, nor as "empty". In this case, the compiler has to enforce wrap semantics for unsigned, which is an applicaton-level level bug if it occurs, and doesn't need to enforce it for int, which happens to lead to the right answer for empty (i.e., it checks if it has at least one element, which continues to return the correct "not empty" answer for 2^32-1 or 2^31-1 elements). Both get the wrong answer for size() (over different domains), if you allow lists that large: they can't even represent very large lists.
- TheCoelacanth 5y ago
  > the compiler cannot assume that adding one will eventually turn negative and then later on reach 0 Signed overflow is undefined behavior, so it is allowed to assume that. It's also allowed to assume anything else that it wants to. Once you cause a signed overflow, all guarantees are out the window and the compiler can do anything it wants to.
spatulon 5y ago
Is the LLVM optimisation pass that does this hyper-specialised for this one particular trick, and, if so, is it valuable in practice? Here's an example where (I think) the two functions are equivalent, so I'm a little disappointed it couldn't make the same optimisation on the second one. (At least it still optimised the tail call to a jump.) https://godbolt.org/z/K9rMajsjK https://godbolt.org/z/K9rMajsjK
- Someone 5y ago
  No, it is very generic. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo..., https://blog.matthieud.me/2020/exploring-clang-llvm-optimization-on-programming-horror/ https://blog.matthieud.me/2020/exploring-clang-llvm-optimiza... (discussed at https://news.ycombinator.com/item?id=28207207 https://news.ycombinator.com/item?id=28207207) (I remember reading a page with more examples, but cannot find it)

by ufo 5y ago

whimsicalism 5y ago

Is this code not relying on UB? Seems like it could/should be optimized to `return true`

carnitine 5y ago
What’s the UB?
- deleted 5y ago
  [deleted]
- whimsicalism 5y ago
  Calling it on any positive int causes signed integer overflow, which is UB.
- nawgz 5y ago
  signed integer overflow for positive N
edflsafoiewq 5y ago
It's only UB for positive n. For negative n, it is an is-even test, so it can't be optimized to return true.
- whimsicalism 5y ago
  Oh yeah - negative numbers exist, doh!
poizan42 5y ago
It's UB for positive integers, so the compiler can assume it never happens. It's correct for negative integers, so the compiler just optimizes it for negative integers and ignores the positive ones - in this case with the end result that it works for positive integers as well. If the argument is changed to unsigned int then it seems to be correct and portable because the C standard[1] requires UINT_MAX to be of the form 2^n - 1 (which makes it wrap from odd to even when overflowing). So the one with signed argument is UB for positive integers but happens to work by accident (but the nasal demons may still lurk just around the corner, e.g. the compiler may also assume that it's never called with a positive argument which may affect the compilation of callers). The one with unsigned argument is correct because unsigned overflow is well-defined to wrap around to zero, combined with the restrictions on max unsigned int. [1]: From C17 6.2.6.2: For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2*(N-1), so that objects of that type shall be capable of representing values from 0 to 2*(N-1) using a pure binary representation; this shall be known as the value representation.

joosters 5y ago

Isn't the unsigned version the correct one? Presumably the int version will hit the same problem as in the original article, in that the C spec says that ints are not treated as overflowing? (i.e. the compiler cannot assume that adding one will eventually turn negative and then later on reach 0)

DSMan195276 5y ago
Yes that's right - unsigned is defined to wrap, but ints have undefined behavior if you add to the max value (or do other silly things with them). Thus the int version given could be optimized to do whatever when a positive integer is passed, since it only doesn't have UB when negatives or zero are passed.
BeeOnRope 5y ago
Well the int version returns the correct answer for "empty()" unlike unsigned. The size of a list of 2^32-1 elements should not be reported as zero, nor as "empty". In this case, the compiler has to enforce wrap semantics for unsigned, which is an applicaton-level level bug if it occurs, and doesn't need to enforce it for int, which happens to lead to the right answer for empty (i.e., it checks if it has at least one element, which continues to return the correct "not empty" answer for 2^32-1 or 2^31-1 elements). Both get the wrong answer for size() (over different domains), if you allow lists that large: they can't even represent very large lists.
TheCoelacanth 5y ago
> the compiler cannot assume that adding one will eventually turn negative and then later on reach 0 Signed overflow is undefined behavior, so it is allowed to assume that. It's also allowed to assume anything else that it wants to. Once you cause a signed overflow, all guarantees are out the window and the compiler can do anything it wants to.

spatulon 5y ago

Is the LLVM optimisation pass that does this hyper-specialised for this one particular trick, and, if so, is it valuable in practice? Here's an example where (I think) the two functions are equivalent, so I'm a little disappointed it couldn't make the same optimisation on the second one. (At least it still optimised the tail call to a jump.) https://godbolt.org/z/K9rMajsjK https://godbolt.org/z/K9rMajsjK

Someone 5y ago
No, it is very generic. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo..., https://blog.matthieud.me/2020/exploring-clang-llvm-optimization-on-programming-horror/ https://blog.matthieud.me/2020/exploring-clang-llvm-optimiza... (discussed at https://news.ycombinator.com/item?id=28207207 https://news.ycombinator.com/item?id=28207207) (I remember reading a page with more examples, but cannot find it)