Comment puis-je empêcher l'optimiseur gcc de produire des opérations binaires incorrectes ?

Question

Considérons le programme suivant.

#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);
}

Lorsqu'il est compilé sans les optimisations du compilateur, il produit les résultats attendus.

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

Lorsqu'il est compilé avec les optimisations du compilateur, il produit la sortie incorrecte suivante.

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

Je suis en train de courir gcc version 5.4.0 .

Puis-je modifier le code source pour empêcher le compilateur de produire ce comportement ? -O3 ?

Answer 1

1. -2147483648 ne fait pas ce que vous pensez qu'il fait. C n'a pas de constantes négatives. Inclure limits.h et utiliser INT_MIN à la place (à peu près tous les INT_MIN La définition des machines à complément à deux est la suivante (-INT_MAX - 1) pour une bonne raison).

2. A = ~A + 1; invoque un comportement non défini parce que ~A + 1 provoque un dépassement d'entier.

Ce n'est pas le compilateur, c'est votre code.

Answer 2

Le compilateur remplace votre A = ~A + 1; avec un seul neg instruction, c'est-à-dire ce code :

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

sera compilé en :

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

Mais le compilateur est aussi assez intelligent pour réaliser que, si A & 0x80000000 était non nulle avant la négation, elle doit être nul après négation, à moins que vous ne comptiez sur un comportement indéfini .

Cela signifie que le deuxième printf("negative(A) = %d\n", negative(A)); peut être optimisé de manière "sûre" :

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

J'utilise l'outil en ligne explorateur de compilateur godbolt pour vérifier l'assemblage pour diverses optimisations du compilateur.

Answer 3

Pour expliquer en détail ce qui se passe ici :

• Dans cette réponse, je suppose que long est de 32 bits et long long est de 64 bits. C'est le cas le plus courant, mais ce n'est pas garanti.

• Le C n'a pas de contants entiers signés. -2147483648 est en fait de type long long sur lequel on applique l'opérateur unaire moins.

  Le compilateur choisit le type de la constante entière après avoir vérifié si 2147483648 peut s'adapter :

  • A l'intérieur d'un int ? Non, c'est impossible.
  • A l'intérieur d'un long ? Non, c'est impossible.
  • A l'intérieur d'un long long ? Oui, c'est possible. Le type de la constante entière sera donc long long . Ensuite, on applique un moins unaire sur ce long long .

• Ensuite, vous essayez de montrer ce négatif long long à une fonction qui attend un int . Un bon compilateur pourrait avertir ici. Vous forcez une conversion implicite vers un type plus petit ("lvalue conversion").
  Cependant, en supposant le complément à 2, la valeur -2147483648 peut tenir dans un int Ainsi, aucun comportement défini par l'implémentation n'est nécessaire pour la conversion, ce qui aurait été le cas autrement.

• La prochaine partie délicate est la fonction negative où vous utilisez 0x80000000 . Il ne s'agit pas d'un int non plus, et ce n'est pas un long long mais un unsigned int ( voir ceci pour une explication).

  Lorsque vous comparez vos résultats int avec un unsigned int les "conversions arithmétiques habituelles" ( voir ceci ) forcent une conversion implicite vers le format int à unsigned int . Cela n'affecte pas le résultat dans ce cas précis, mais voici pourquoi gcc -Wconversion les utilisateurs reçoivent un bel avertissement ici.

  (Conseil : activez -Wconversion déjà ! Il est bon pour attraper des bugs subtils, mais ne fait pas partie de -Wall ou -Wextra .)

• Ensuite, vous faites ~A un inverse bit à bit de la représentation binaire de la valeur, ce qui donne la valeur suivante 0x7FFFFFFF . Il s'agit, en fait, de la même valeur que INT_MAX sur votre système 32 ou 64 bits. Ainsi, 0x7FFFFFFF + 1 donne un dépassement d'entier signé qui conduit à un comportement non défini. C'est la raison pour laquelle le programme se comporte mal.

  De manière insolente, nous pourrions changer le code en A = ~A + 1u; et soudain tout fonctionne comme prévu, à nouveau à cause de la promotion implicite des entiers.

---

Les leçons apprises :

En C, les constantes entières, ainsi que les promotions entières implicites, sont très dangereuses et peu intuitives. Elles peuvent subtilement changer complètement la signification du programme et introduire des bogues. À chaque opération en C, vous devez tenir compte des types réels des opérandes concernés.

Jouer avec C11 _Generic pourrait être un bon moyen de voir les types réels. Exemple :

#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

Une bonne mesure de sécurité pour se protéger de ce genre de bogues est de toujours utiliser stdint.h et d'utiliser MISRA-C.

Answer 4

Vous vous fiez à un comportement non défini. 0x7fffffff + 1 pour les entiers signés 32 bits entraîne un dépassement de capacité des entiers signés, ce qui est un comportement non défini selon la norme, donc tout est permis.

Dans gcc, vous pouvez forcer le comportement enveloppant en passant le paramètre -fwrapv mais si vous n'avez pas de contrôle sur les drapeaux - et plus généralement, si vous voulez un programme plus portable - vous devriez faire toutes ces astuces sur unsigned qui doivent être enveloppés par la norme (et ont une sémantique bien définie pour les opérations binaires, contrairement aux entiers signés).

Convertissez d'abord le int à unsigned (bien défini selon la norme, donne le résultat attendu), faites votre travail, reconvertissez en int - défini par l'implémentation (≠ non défini) pour des valeurs supérieures à la plage de int mais en fait défini par chaque compilateur travaillant en complément à 2 pour faire la "bonne chose".

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;
}

Votre version (à -O3) :

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

Ma version (à -O3) :

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