OK, those are horrifying and fascinating, and they basically break my brain.

Is there a explanation somewhere of why the first one "works"? The second one I think is the compiler assuming the default case will never be hit since it'll result in infinite recursion, which is UB under C++, so it's basically assuming 0<=x<=3 and optimizing from there. Is that correct?

The first one I'm less certain about. The only thing I can think of is that the compiler deduces an upper limit of INT_MAX - 1 to avoid signed overflow, and then somehow figuring out the true/false pattern from there? Still a bit of a gap in my understanding there.

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
    ----------
    0b000 | 1
    0b001 | 0
    0b010 | 1
    0b011 | 0
    0b100 | don't care
          .
          .
          .
    MAX   | don't care

The compiler just chooses the most efficient way it knows to get the filled out entries correct which happens to be:

    in    | ~in[0]
    ----------
    0b000 | 1
    0b001 | 0
    0b010 | 1
    0b011 | 0
    0b100 | 1
          .
          .
          .
    MAX   | 1

It would have been just as valid to do:

    in    | in[2] or ~in[0]
    ----------
    0b000 | 1
    0b001 | 0
    0b010 | 1
    0b011 | 0
    0b100 | 1
    0b101 | 1
          .
          .
          .
    MAX   | 1

The first function's table looks like:

    in    | out
    ----------
    0b000 | 1
    0b001 | don't care
    0b010 | don't care
          .
          .
          .
    MAX   | don't care

And the compiler still likes the even check in this case, which makes sense.

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.

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

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

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

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.

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

My guess: since overflowing int is UB, and the only value of n that stops the recursion is zero, the compiler assumes that n must be zero and checks accordingly.

That doesn’t explain why it uses test dil, 1 instead of test dil, dil or cmp 0 or whatever.

The compiler cannot assume that much, because the argument is a signed integer (negative integers will not overflow and do have well-defined behaviour).

The rabbit hole goes deeper than that: https://gcc.godbolt.org/z/Tc1MTa6nj

That is a well defined function. And indeed implements isEven. Because unsigned int has defined overflow semantics.

Essentially, it will eventually overflow and hit the correct base-case for 0.