Why does clang produces wrong results for my c code compiled with -O1 but not with -O0?

Question

For input 0xffffffff, the following c code works fine with no optimization, but produces wrong results when compiled with -O1. Other compilation options are -g -m32 -Wall. The code is tested with clang-900.0.39.2 in macOS 10.13.2.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    if (argc < 2) return 1;

    char *endp;
    int x = (int)strtoll(argv[1], &endp, 0);

    int mask1 = 0x55555555;
    int mask2 = 0x33333333;
    int count = (x & mask1) + ((x >> 1) & mask1);

    int v1 = count >> 2;
    printf("v1 = %#010x\n", v1);

    int v2 = v1 & mask2;
    printf("v2 = %#010x\n", v2);

    return 0;
}

Input: 0xffffffff

Outputs with -O0: (expected)

v1 = 0xeaaaaaaa

v2 = 0x22222222

Outputs with -O1: (wrong)

v1 = 0x2aaaaaaa

v2 = 0x02222222

Below are disassembled instructions for the line "int v1 = count >> 2;" with -O0 and -O1.

With -O0:

sarl $0x2, %esi

With -O1:

shrl $0x2, %esi

Below are disassembled instructions for the line "int v2 = v1 & mask2;" with -O0 and -O1.

With -O0:

andl -0x24(%ebp), %esi //-0x24(%ebp) stores 0x33333333

With -O1:

andl $0x13333333, %esi //why does the optimization changes 0x33333333 to 0x13333333?

In addition, if x is set to 0xffffffff locally instead of getting its value from arguments, the code will work as expected even with -O1.

P.S: The code is an experimental piece based on my solution to the Data Lab from the CS:APP course @ CMU. The lab asks the student to implement a function that counts the number of 1 bit of an int variable without using any type other than int.

Answer 1

As several commenters have pointed out, right-shifting signed values is not well defined.

I changed the declaration and initialization of x to

unsigned int x = (unsigned int)strtoll(argv[1], &endp, 0);

and got consistent results under -O0 and -O1. (But before making that change, I was able to reproduce your result under clang under MacOS.)

Answer 2

As you have discovered, you raise Implementation-defined Behavior in your attempt to store 0xffffffff (4294967295) in int x (where INT_MAX is 7fffffff, or 2147483647). C11 Standard §6.3.1.3 (draft n1570) - Signed and unsigned integers Whenever using strtoll (or strtoull) (both versions with 1-l would be fine) and attempting to store the value as an int, you must check the result against INT_MAX before making the assignment with a cast. (or if using exact width types, against INT32_MAX, or UINT32_MAX for unsigned)

Further, in circumstance such as this where bit operations are involved, you can remove uncertainty and insure portability by using the exact width types provided in stdint.h and the associated format specifiers provided in inttypes.h. Here, there is no need for use of a signed int. It would make more sense to handle all values as unsigned (or uint32_t).

For example, the following provides a default value for the input to avoid the Undefined Behavior invoked if your code is executed without argument (you can also simply test argc), replaces the use of strtoll with strtoul, validates the input fits within the associated variable before assignment handling the error if it does not, and then makes use of the unambiguous exact types, e.g.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

int main (int argc, char *argv[]) {

    uint64_t tmp = argc > 1 ? strtoul (argv[1], NULL, 0) : 0xffffffff;

    if (tmp > UINT32_MAX) {
        fprintf (stderr, "input exceeds UINT32_MAX.\n");
        return 1;
    }

    uint32_t x = (uint32_t)tmp,
        mask1 = 0x55555555,
        mask2 = 0x33333333,
        count = (x & mask1) + ((x >> 1) & mask1),
        v1 = count >> 2,
        v2 = v1 & mask2;

    printf("v1 = 0x%" PRIx32 "\n", v1);

    printf("v2 = 0x%" PRIx32 "\n", v2);

    return 0;
}

Example Use/Output

$ ./bin/masktst
v1 = 0x2aaaaaaa
v2 = 0x22222222

Compiled with

$ gcc -Wall -Wextra -pedantic -std=gnu11 -Ofast -o bin/masktst masktst.c

Look things over and let me know if you have further questions.

Answer 3

this statement:

int x = (int)strtoll(argv[1], &endp, 0);

results in a signed overflow, which is undefined behavior.

(on my system, the result is: -1431655766

The resulting values tend to go downhill from there:

The variable: v1 receives: -357913942

The variable: v2 receives: 572662306

the %x format specifier only works correctly with unsigned variables