5 ms·

Optimizers have to keep the same input/output pairs unless there is undefined behavior. In the second function the truth table looks like: in | out

• notriddle 5y ago
  The first function (the `n == 0 || !isEven(n+1)` recursive function) has defined behavior for negative numbers. That's probably why it compiled to an even number check.
  • 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 ago
        Treat-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 ago
          Right, 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 ago
      max(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."