5 ms·
Hmm you're right that there's definitely more to the first function than coincidence. I dug a bit deeper and surprisingly when n is unsigned the function is sti
by davemp 5y ago
Hmm you're right that there's definitely more to the first function than coincidence. I dug a bit deeper and surprisingly when n is unsigned the function is still well defined and correct. [0] AFAIK clang will usually just treat a signed overflow as an unsigned overflow when optimizing as it simplifies things. So my bet would be that clang is just casting n to unsigned and performing some inductive reasoning similar to the proof I wrote below. Pretty impressive on the behalf of clang. [1]
[0]: I did the proof below for anyone interested:
int isEven(unsigned int n) {
return n == 0 || !isEven(n + 1);
}
# assumptions
MAX + 1 --> 0 # from the C standard
MAX is odd # true for most machines
# base case
isEven(0) --> True # trivial short circuit
# base case
isEven(MAX):
==> return MAX == 0 || !isEven(MAX+1) # MAX is not zero
==> return False || !isEven(MAX+1) # MAX + 1 rolls over
==> return False || !isEven(0)
==> return False || !True
==> return False || False
==> return False
==> isEven(MAX) --> False
# recursive steps
isEven(n) where 0 < n < MAX
==> return n == 0 || !isEven(n + 1) # n cannot be zero
==> return False || !isEven(n + 1) # False || anything is tautological
==> return !isEven(n + 1)
which will turn into an inverter chain of length MAX - n until you reach isEven(MAX)
- an odd length inverter chain is the same as a single inversion
- an even length inverter chain is the identity
(can be proven by induction trivially)
isEven(n) where 0 < n < MAX and n is even
==> return !isEven(n + 1) # MAX - n is odd, when n is even; replace with single inversion before isEven(MAX)
==> return !isEven(MAX)
==> !(False) --> True
isEven(n) where 0 < n < MAX and n is odd
==> return !isEven(n + 1) # MAX - n is even, when n is odd; replace with identity of isEven(MAX)
==> return isEven(MAX)
==> False --> False
All cases of n are accounted for so the function is correct (and equivalent to return n & 1 == 0).
[1]: Yup clang just recognizes this optimization: https://gcc.godbolt.org/z/Tc1MTa6nj https://gcc.godbolt.org/z/Tc1MTa6nj
- aw1621107 5y ago> AFAIK clang will usually just treat a signed overflow as an unsigned overflow when optimizing as it simplifies things. This was a bit of a surprise to me; I thought that Clang could use the presence of signed overflow to infer bounds, like when it "breaks" naïve overflow checks. I didn't know about the treat-signed-as-unsigned behavior you described. If that's what clang is doing, that's pretty neat! Quite a bit of reasoning to work through there. Thanks for taking the time to explain!
- int_19h 5y agoTreat-signed-as-unsigned is what you get "by default" with a two's complement representation of integers, if you just use ADD/SUB opcodes regardless of the type (i.e. the cheapest/fastest way to do it).
- aw1621107 5y agoRight, but I had thought that clang would have done something involving deducing the bounds of n, which could be used to avoid overflow in later optimizations. Now that I think about it, though, they key there is "could" - overflow could be avoided by deducing bounds, but if said deduction can't occur then what you describe sounds like the most natural action to take as long as there aren't other issues.
- int_19h 5y agomax(unsigned int) being odd is also required by the C standard; C17 6.2.6.2/1: "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."