(A + B + C) ≠ (A + C + B) et réordonnancement du compilateur

Question

L'addition de deux entiers de 32 bits peut entraîner un dépassement de capacité :

uint64_t u64_z = u32_x + u32_y;

Ce dépassement peut être évité si l'un des entiers de 32 bits est d'abord converti ou ajouté en un entier de 64 bits.

uint64_t u64_z = u32_x + u64_a + u32_y;

Cependant, si le compilateur décide de réordonner l'addition :

uint64_t u64_z = u32_x + u32_y + u64_a;

le dépassement d'entier peut encore se produire.

Les compilateurs sont-ils autorisés à effectuer une telle réorganisation ou pouvons-nous leur faire confiance pour remarquer l'incohérence du résultat et conserver l'ordre des expressions tel quel ?

Answer 1

Si l'optimiseur effectue un tel réordonnancement, il est toujours lié à la spécification C, de sorte qu'un tel réordonnancement deviendrait :

uint64_t u64_z = (uint64_t)u32_x + (uint64_t)u32_y + u64_a;

Justification :

Nous commençons par

uint64_t u64_z = u32_x + u64_a + u32_y;

L'addition se fait de gauche à droite.

Les règles de promotion des entiers stipulent que lors de la première addition dans l'expression originale, u32_x être promu à uint64_t . Dans le deuxième ajout, u32_y sera également promu à uint64_t .

Ainsi, afin d'être conforme à la spécification C, tout optimiseur doit promouvoir u32_x y u32_y à des valeurs non signées de 64 bits. Cela équivaut à ajouter un cast. (L'optimisation réelle n'est pas faite au niveau du C, mais j'utilise la notation C parce que c'est une notation que nous comprenons).

Answer 2

Un compilateur n'est autorisé à réordonner que dans le cadre de la directive comme si règle. En d'autres termes, si le changement d'ordre donne toujours le même résultat que l'ordre spécifié, il est autorisé. Sinon (comme dans votre exemple), non.

Par exemple, étant donné l'expression suivante

i32big1 - i32big2 + i32small

qui a été soigneusement construit pour soustraire les deux valeurs connues pour être grandes mais similaires, et seulement puis ajouter l'autre petite valeur (évitant ainsi tout débordement), le compilateur peut choisir de réordonner dans :

(i32small - i32big2) + i32big1

et compter sur le fait que la plate-forme cible utilise l'arithmétique à deux compléments avec wrap-round pour éviter les problèmes. (Un tel réordonnancement peut être judicieux si le compilateur est pressé par les registres et qu'il dispose de i32small dans un registre déjà).

Answer 3

Il existe la règle du "as if" en C, C++ et Objective-C : Le compilateur peut faire ce qu'il veut tant qu'aucun programme conforme ne peut faire la différence.

Dans ces langages, a + b + c est défini comme étant la même chose que (a + b) + c. Si vous pouvez faire la différence entre ceci et par exemple a + (b + c), alors le compilateur ne peut pas changer l'ordre. Si vous ne pouvez pas faire la différence, alors le compilateur est libre de changer l'ordre, mais c'est très bien, puisque vous ne pouvez pas faire la différence.

Dans votre exemple, avec b = 64 bits, a et c 32 bits, le compilateur serait autorisé à évaluer (b + a) + c ou même (b + c) + a, car on ne pourrait pas faire la différence, mais pas (a + c) + b car on peut faire la différence.

En d'autres termes, le compilateur n'est pas autorisé à faire quoi que ce soit qui fasse que votre code se comporte différemment de ce qu'il devrait. Il n'est pas obligé de produire le code que vous pensez qu'il produirait, ou que vous pensez qu'il devrait produire, mais le code sera vous donne exactement les résultats escomptés.

Answer 4

Citant le normes :

[ Note : Les opérateurs peuvent être regroupés selon les règles mathématiques habituelles règles mathématiques habituelles que si les opérateurs sont réellement associatifs ou commu commutatifs.7 Par exemple, dans le fragment suivant int a, b ;

/∗ ... ∗/
a = a + 32760 + b + 5;

l'expression se comporte exactement de la même manière que

a = (((a + 32760) + b) + 5);

en raison de l'associativité et de la précédence de ces opérateurs. Ainsi, le résultat de la somme (a + 32760) est ensuite ajouté à b, puis ce résultat est est ensuite ajouté à 5, ce qui donne la valeur attribuée à a. Sur une machine dans laquelle les débordements produisent une exception et dans laquelle la gamme de représentable par un int est [-32768,+32767], l'implémentation ne peut pas réécrire cette ne peut pas réécrire cette expression sous la forme

a = ((a + b) + 32765);

puisque si les valeurs de a et b étaient, respectivement, -32754 et -15, la somme a + b produirait une exception alors que l'expression originale ne le ferait pas ; l'expression ne peut pas non plus être réécrite comme suit

a = ((a + 32765) + b);

ou

a = (a + (b + 32765));

puisque les valeurs de a et b auraient pu être, respectivement, de 4 et -8 ou -17 et 12. Cependant, sur une machine dans laquelle les débordements ne produisent pas exception et sur laquelle les résultats des débordements sont réversibles, l'exa l'expression ci-dessus peut être réécrite par l'implémentation de n'importe quelle manière n'importe laquelle des manières ci-dessus car le même résultat se produira. - note de fin ]

Answer 5

Les compilateurs sont-ils autorisés à effectuer une telle réorganisation ou pouvons-nous leur faire confiance pour remarquer l'incohérence du résultat et conserver l'ordre des expressions tel quel ?

Le compilateur ne peut réordonner que si cela donne le même résultat - ici, comme vous l'avez observé, ce n'est pas le cas.

---

Il est possible d'écrire un modèle de fonction, si vous en voulez un, qui promeut tous les arguments à std::common_type avant d'ajouter - cela serait sûr, et ne dépendrait pas de l'ordre des arguments ou de l'encodage manuel, mais c'est plutôt maladroit.