operadores - rotacion de bits en c

¿Cómo puedo evitar que el optimizador gcc produzca operaciones de bits incorrectas?

Question

Considere el siguiente programa.

#include <stdio.h>

int negative(int A) {
    return (A & 0x80000000) != 0;
}
int divide(int A, int B) {
    printf("A = %d/n", A);
    printf("negative(A) = %d/n", negative(A));
    if (negative(A)) {
        A = ~A + 1;
        printf("A = %d/n", A);
        printf("negative(A) = %d/n", negative(A));
    }
    if (A < B) return 0;
    return 1;
}
int main(){
    divide(-2147483648, -1);
}

Cuando se compila sin optimizaciones del compilador, produce los resultados esperados.

gcc  -Wall -Werror -g -o TestNegative TestNegative.c
./TestNegative
A = -2147483648
negative(A) = 1
A = -2147483648
negative(A) = 1

Cuando se compila con optimizaciones del compilador, produce el siguiente resultado incorrecto.

gcc -O3 -Wall -Werror -g -o TestNegative TestNegative.c
./TestNegative 
A = -2147483648
negative(A) = 1
A = -2147483648
negative(A) = 0

Estoy ejecutando gcc version 5.4.0 .

¿Hay algún cambio que pueda hacer en el código fuente para evitar que el compilador produzca este comportamiento bajo -O3 ?

Answer 1

1. -2147483648 no hace lo que crees que hace. C no tiene constantes negativas. Incluya limits.h y use INT_MIN en INT_MIN lugar (casi todas INT_MIN definiciones de INT_MIN en las máquinas del complemento de dos lo definen como (-INT_MAX - 1) por una buena razón).

2. A = ~A + 1; invoca un comportamiento indefinido porque ~A + 1 causa un desbordamiento de enteros.

No es el compilador, es tu código.

Answer 2

El compilador reemplaza tu A = ~A + 1; declaración con una sola instrucción neg , es decir, este código:

int just_negate(int A) {
    A = ~A + 1;
    return A;
}

será compilado para:

just_negate(int):
  mov eax, edi
  neg eax         // just negate the input parameter
  ret

Pero el compilador también es lo suficientemente inteligente como para darse cuenta de que, si A & 0x80000000 no era cero antes de la negación, debe ser cero después de la negación, a menos que esté confiando en un comportamiento indefinido .

Esto significa que el segundo printf("negative(A) = %d/n", negative(A)); puede ser "seguro" optimizado para:

mov edi, OFFSET FLAT:.LC0    // .string "negative(A) = %d/n"
xor eax, eax                 // just set eax to zero
call printf

Utilizo el explorador de compiladores de godbolt en línea para verificar el ensamblaje en busca de varias optimizaciones del compilador.

Answer 3

Estás confiando en un comportamiento indefinido. 0x7fffffff + 1 para enteros con signo de 32 bits produce un desbordamiento de entero con signo, que es un comportamiento indefinido según el estándar, por lo que todo vale.

En gcc puedes forzar el -fwrapv envolvente pasando -fwrapv ; aún así, si no tiene control sobre las banderas, y más en general, si desea un programa más portátil, debe hacer todos estos trucos con enteros unsigned , que la norma exige que se ajusten (y tengan una semántica bien definida para operaciones bitwise, a diferencia de los enteros con signo).

Primero convierta el int en unsigned (bien definido de acuerdo con el estándar, produzca el resultado esperado), haga sus cosas, vuelva a convertir int - definido por la implementación (≠ no definido) para valores mayores que el rango de int , pero en realidad definido por cada compilador trabajando en complemento de 2 para hacer lo "correcto".

int divide(int A, int B) {
    printf("A = %d/n", A);
    printf("negative(A) = %d/n", negative(A));
    if (negative(A)) {
        A = ~((unsigned)A) + 1;
        printf("A = %d/n", A);
        printf("negative(A) = %d/n", negative(A));
    }
    if (A < B) return 0;
    return 1;
}

Su versión (en -O3):

A = -2147483648
negative(A) = 1
A = -2147483648
negative(A) = 0

Mi versión (en -O3):

A = -2147483648
negative(A) = 1
A = -2147483648
negative(A) = 1

Answer 4

Para explicar en detalle lo que está pasando aquí:

• En esta respuesta supongo que el long es de 32 bits y el long long es de 64 bits. Este es el caso más común, pero no está garantizado.

• C no tiene contadores enteros con signo. -2147483648 es en realidad de tipo long long , en el que se aplica el operador unario menos.

  El compilador elige el tipo de la constante entera después de verificar si 2147483648 puede caber:

  • Dentro de un int ? No, no puede.
  • Dentro de un long ? No, no puede.
  • Dentro de un long long ? Sí puede. Por lo tanto, el tipo de la constante entera será, por lo tanto, long long . Luego aplique unario menos en ese long long .
• Luego, intenta mostrar este negativo long long a una función que espera un int . Un buen compilador podría avisar aquí. Forzas una conversión implícita a un tipo más pequeño ("lvalue conversion").
  Sin embargo, asumiendo el complemento de 2, el valor -2147483648 puede caber dentro de un int , por lo que no se necesita un comportamiento definido por la implementación para la conversión, que de lo contrario habría sido el caso.

• La siguiente parte difícil es la función negative donde usas 0x80000000 . Esto tampoco es un int , ni es un long long , sino un unsigned int ( vea esto para una explicación).

  Al comparar su int pasado con un unsigned int , "las conversiones aritméticas habituales" ( ver esto ) fuerzan una conversión implícita del int a unsigned int . No afecta el resultado en este caso específico, pero esta es la razón por la que gcc -Wconversion users recibe una advertencia agradable aquí.

  (Sugerencia: habilite -Wconversion ya. Es bueno para detectar errores sutiles, pero no es parte de -Wall o -Wextra ).

• A continuación, haga ~A , una inversa a nivel de bits de la representación binaria del valor, que termina con el valor 0x7FFFFFFF . Esto es, como resulta, el mismo valor que INT_MAX en su sistema de 32 o 64 bits. Por 0x7FFFFFFF + 1 tanto, 0x7FFFFFFF + 1 un desbordamiento de entero con signo que lleva a un comportamiento indefinido. Esta es la razón por la cual el programa se está comportando mal.

  Al parecer, podríamos cambiar el código a A = ~A + 1u; y, de repente, todo funciona como se esperaba, nuevamente debido a la promoción implícita de enteros.

Lecciones aprendidas:

En C, las constantes enteras, así como las promociones enteras implícitas, son muy peligrosas y poco intuitivas. Pueden cambiar sutilmente el significado del programa por completo e introducir errores. En cada una de las operaciones en C, debe considerar los tipos reales de los operandos involucrados.

Jugar con C11 _Generic podría ser una buena manera de ver los tipos reales. Ejemplo:

#define TYPE_SAFE(val, type) _Generic((val), type: val)
...
(void) TYPE_SAFE(-2147483648, int); // won''t compile, type is long or long long
(void) TYPE_SAFE(0x80000000, int);  // won''t compile, type is unsigned int

Buenas medidas de seguridad para protegerse contra errores como estos es usar siempre stdint.h y usar MISRA-C.