There is no 'printf'

Post by davemp » Fri, Oct 22, 2021, 1:29 AM UTC

notriddle wrote: post #42

davemp wrote: post #40

Earlier quoted context omitted.

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…

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.

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

Post by ikerdanzel » Fri, Oct 22, 2021, 1:33 AM UTC

_kst_ wrote: post #65

kazinator wrote: post #53

> But what if you're not using C99 or newer? If you're using C90, but under an implementation that supports C99, that implementation should obey all the new rules in all areas where there is no conflict between C90 and C99. The ISO C90 standard is obsolescent, so the fact that dropping off the end of main with no return value is an unspecified termination status is an obsolescent requirement (or non-requirement). It…

Regardless of how you think a modern compiler in C99 mode should behave, the fact is that "gcc -std=c90" generates code that returns an arbitrary value from main if no return or exit is executed. clang doesn't do this as far as I can tell -- though it's difficult to be sure, since returning a status of 0 is valid C90 behavior.

Post by davemp » Fri, Oct 22, 2021, 1:42 AM UTC

eMSF wrote: post #67

barsonme wrote: post #38

Earlier quoted context omitted.

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

Post by QuestingElf » Fri, Oct 22, 2021, 1:55 AM UTC

moffkalast wrote: post #37

rrauenza wrote: post #15

Quick Summary: The C compiler optimizer replaces printf("Hello World!\n") with puts("Hello World!\n") and the implicit return from main() changes from 13 (the return value of printf) to 10 (the return value of puts)

Calls on puts you say?

Post by anonymfus » Fri, Oct 22, 2021, 1:56 AM UTC

kazinator wrote: post #53

> But what if you're not using C99 or newer? If you're using C90, but under an implementation that supports C99, that implementation should obey all the new rules in all areas where there is no conflict between C90 and C99. The ISO C90 standard is obsolescent, so the fact that dropping off the end of main with no return value is an unspecified termination status is an obsolescent requirement (or non-requirement). It…