Is it a bug in g++?

Question

#include <stdint.h>
#include <iostream>

using namespace std;

uint32_t k[] = {0, 1, 17};

template <typename T>
bool f(T *data, int i) {
    return data[0] < (T)(1 << k[i]);
}

int main() {
    uint8_t v = 0;
    cout << f(&v, 2) << endl;
    cout << (0 < (uint8_t)(1 << 17)) << endl;
    return 0;
}

g++ a.cpp && ./a.out
1
0

Why am I getting these results?

Answer 1

It looks like gcc reverses the shift and applies it to the other side, and I guess this is a bug.

In C (instead of C++) the same thing happens, and C translated to asm is easier to read, so I'm using C here; also I reduced the test cases (dropping templates and the k array). foo() is the original buggy f() function, foo1() is what foo() behaves like with gcc but shouldn't, and bar() shows what foo() should look like apart from the pointer read.

I'm on 64-bit, but 32-bit is the same apart from the parameter handling and finding k.

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

uint32_t k = 17;
char foo(uint8_t *data) {
    return *data < (uint8_t)(1<<k);
/*
with gcc -O3 -S: (gcc version 4.7.2 (Debian 4.7.2-5))
    movzbl  (%rdi), %eax
    movl    k(%rip), %ecx
    shrb    %cl, %al
    testb   %al, %al
    sete    %al
    ret
*/
}
char foo1(uint8_t *data) {
    return (((uint32_t)*data) >> k) < 1;
/*
    movzbl  (%rdi), %eax
    movl    k(%rip), %ecx
    shrl    %cl, %eax
    testl   %eax, %eax
    sete    %al
    ret
*/
}
char bar(uint8_t data) {
    return data < (uint8_t)(1<<k);
/*
    movl    k(%rip), %ecx
    movl    $1, %eax
    sall    %cl, %eax
    cmpb    %al, %dil
    setb    %al
    ret
*/
}

int main() {
    uint8_t v = 0;
    printf("All should be 0: %i %i %i\n", foo(&v), foo1(&v), bar(v));
    return 0;
}

Answer 2

If your int is 16-bit long, you're running into undefined behavior and either result is "OK".

Shifting N-bit integers by N or more bit positions left or right results in undefined behavior.

Since this happens with 32-bit ints, this is a bug in the compiler.

Answer 3

Here are some more data points:

basically, it looks like gcc optimizes (even in when the -O flag is off and -g is on):

    [variable] < (type-cast)(1 << [variable2])

to

    ((type-cast)[variable] >> [variable2]) == 0

and

    [variable] >= (type-cast)(1 << [variable2])

to

    ((type-cast)[variable] >> [variable2]) != 0

where [variable] needs to be an array access.

I guess the advantage here is that it doesn't have to load the literal 1 into a register, which saves 1 register.

So here are the data points:

• changing 1 to a number > 1 forces it to implement the correct version.
• changing any of the variables to a literal forces it to implement the correct version
• changing [variable] to a non array access forces it to implement the correct version
• [variable] > (type-cast)(1 << [variable2]) implements the correct version.

I suspect this is all trying to save a register. When [variable] is an array access, it needs to also keep an index. Someone probably thought this is so clever, until it's wrong.

Using code from the bug report http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56051

    #include <stdio.h>

    int main(void)
    {
        int a, s = 8;
        unsigned char data[1] = {0};

        a = data[0] < (unsigned char) (1 << s);
        printf("%d\n", a);

        return 0;
    }

compiled with gcc -O2 -S

     .globl main
            .type   main, @function
    main:
    leal    4(%esp), %ecx
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %ecx
    subl    $8, %esp
    pushl   $1                ***** seems it already precomputed the result to be 1
    pushl   $.LC0
    pushl   $1
    call    __printf_chk
    xorl    %eax, %eax
    movl    -4(%ebp), %ecx
    leave
    leal    -4(%ecx), %esp
    ret

compile with just gcc -S

    .globl main
            .type   main, @function
    main:
    leal    4(%esp), %ecx
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %ebx
    pushl   %ecx
    subl    $16, %esp
    movl    $8, -12(%ebp)
    movb    $0, -17(%ebp)
    movb    -17(%ebp), %dl
    movl    -12(%ebp), %eax
    movb    %dl, %bl
    movb    %al, %cl
    shrb    %cl, %bl                      ****** (unsigned char)data[0] >> s => %bl
    movb    %bl, %al                              %bl => %al
    testb   %al, %al                              %al = 0?
    sete    %dl
    movl    $0, %eax
    movb    %dl, %al
    movl    %eax, -16(%ebp)
    movl    $.LC0, %eax
    subl    $8, %esp
    pushl   -16(%ebp)
    pushl   %eax
    call    printf
    addl    $16, %esp
    movl    $0, %eax
    leal    -8(%ebp), %esp
    addl    $0, %esp
    popl    %ecx
    popl    %ebx
    popl    %ebp
    leal    -4(%ecx), %esp
    ret

I guess the next step is to dig through gcc's source code.

Answer 4

I'm pretty sure we're talking undefined behaviour here - converting a "large" integer to a smaller, of a value that doesn't fit in the size of the new value, is undefined as far as I know. 131072 definitely doesn't fit in a uint_8.

Although looking at the code generated, I'd say that it's probably not quite right, since it does "sete" rather than "setb"??? That does seem very suspicios to me.

If I turn the expression around:

return (T)(1<<k[i])  >  data[0];

then it uses a "seta" instruction, which is what I'd expect. I'll do a bit more digging - but something seems a bit wrong.