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)

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.

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.

> 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.

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

No, it is very generic. See https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo..., https://blog.matthieud.me/2020/exploring-clang-llvm-optimiza... (discussed at https://news.ycombinator.com/item?id=28207207)

(I remember reading a page with more examples, but cannot find it)

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

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.

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.

Oh yeah - negative numbers exist, doh!

What’s the UB?

Calling it on any positive int causes signed integer overflow, which is UB.

signed integer overflow for positive N