Débordement signé en C ++ et comportement indéfini (UB)

Je m'interroge sur l'utilisation de code comme le suivant

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Si la boucle est itérée au fil du ntemps, elle factorest multipliée par 10exactement le ntemps. Cependant, il factorn'est utilisé qu'après avoir été multiplié par 10un total de n-1fois. Si nous supposons que factorjamais ne déborde, sauf sur la dernière itération de la boucle, mais peut déborder sur la dernière itération de la boucle, alors un tel code devrait-il être acceptable? Dans ce cas, la valeur de factorne sera probablement jamais utilisée après le dépassement de capacité.

J'ai un débat sur la question de savoir si un code comme celui-ci devrait être accepté. Il serait possible de mettre la multiplication dans une instruction if et de ne pas faire la multiplication à la dernière itération de la boucle lorsqu'elle peut déborder. L'inconvénient est qu'il encombre le code et ajoute une branche inutile qui devrait vérifier toutes les itérations de boucle précédentes. Je pourrais également répéter la boucle une fois de plus et répliquer le corps de la boucle une fois après la boucle, encore une fois, cela complique le code.

Le code en question est utilisé dans une boucle interne serrée qui consomme une grande partie du temps CPU total dans une application graphique en temps réel.

Les compilateurs supposent qu'un programme C ++ valide ne contient pas UB. Considérez par exemple:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Si x == nullptralors le déréférencement et l'attribution d'une valeur est UB. Par conséquent, la seule façon dont cela pourrait se terminer dans un programme valide est quand x == nullptrne donnera jamais la valeur true et que le compilateur peut supposer sous la règle comme si, ce qui précède est équivalent à:

*x = 5;

Maintenant dans votre code

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

La dernière multiplication de factorne peut pas se produire dans un programme valide (le débordement signé n'est pas défini). Par conséquent, l'affectation à resultne peut pas se produire. Comme il n'y a aucun moyen de créer une branche avant la dernière itération, l'itération précédente ne peut pas se produire. Finalement, la partie du code qui est correcte (c'est-à-dire qu'aucun comportement indéfini ne se produit jamais) est:

// nothing :(

Le comportement du intdébordement n'est pas défini.

Peu importe si vous lisez en factordehors du corps de la boucle; s'il a débordé d'ici là, alors le comportement de votre code sur, après et quelque peu paradoxalement avant que le débordement ne soit indéfini.

Un problème qui pourrait survenir en conservant ce code est que les compilateurs deviennent de plus en plus agressifs en matière d'optimisation. En particulier, ils développent une habitude où ils supposent qu'un comportement indéfini ne se produit jamais. Pour que ce soit le cas, ils peuvent supprimer forcomplètement la boucle.

Ne pouvez-vous pas utiliser un unsignedtype pour factorbien que vous deviez alors vous soucier de la conversion indésirable de inten unsigneddans des expressions contenant les deux?

Il peut être judicieux de considérer des optimiseurs du monde réel. Le déroulement des boucles est une technique connue. L'idée de base du déroulement de la boucle op est que

for (int i = 0; i != 3; ++i)
    foo()

pourrait être mieux mis en œuvre dans les coulisses comme

 foo()
 foo()
 foo()

C'est le cas facile, avec une limite fixe. Mais les compilateurs modernes peuvent également le faire pour des limites variables:

for (int i = 0; i != N; ++i)
   foo();

devient

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Évidemment, cela ne fonctionne que si le compilateur sait que N <= 3. Et c'est là que nous revenons à la question d'origine. Comme le compilateur sait qu'aucun débordement signé ne se produit , il sait que la boucle peut s'exécuter au maximum 9 fois sur des architectures 32 bits. 10^10 > 2^32. Il peut donc dérouler une boucle à 9 itérations. Mais le maximum prévu était de 10 itérations! .

Ce qui pourrait arriver, c'est que vous obtenez un saut relatif vers une instruction d'assemblage (9-N) avec N = 10, donc un décalage de -1, qui est l'instruction de saut elle-même. Oops. Il s'agit d'une optimisation de boucle parfaitement valide pour un C ++ bien défini, mais l'exemple donné se transforme en une boucle infinie serrée.

Tout débordement d'entier signé entraîne un comportement indéfini, que la valeur de débordement soit ou non lue ou non.

Peut-être que dans votre cas d'utilisation, vous pouvez sortir la première itération de la boucle,

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

dans ce

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Avec l'optimisation activée, le compilateur peut dérouler la deuxième boucle ci-dessus en un seul saut conditionnel.

C'est UB; en termes ISO C ++, le comportement entier de l'ensemble du programme est complètement non spécifié pour une exécution qui finit par atteindre UB. L'exemple classique est en ce qui concerne la norme C ++, il peut faire sortir les démons de votre nez. (Je déconseille d'utiliser une implémentation où les démons nasaux sont une réelle possibilité). Voir les autres réponses pour plus de détails.

Les compilateurs peuvent "causer des problèmes" au moment de la compilation pour les chemins d'exécution qu'ils peuvent voir, conduisant à une UB visible au moment de la compilation, par exemple en supposant que ces blocs de base ne sont jamais atteints.

Voir aussi Ce que tout programmeur C doit savoir sur le comportement non défini (blog LLVM). Comme expliqué ici, UB avec débordement signé permet aux compilateurs de prouver que les for(... i <= n ...)boucles ne sont pas des boucles infinies, même pour des inconnues n. Il leur permet également de "promouvoir" les compteurs de boucles int en largeur de pointeur au lieu de refaire l'extension de signe. (La conséquence de l'UB dans ce cas pourrait donc être d'accéder en dehors des éléments 64k ou 4G bas d'un tableau, si vous vous attendiez à un emballage signé de idans sa plage de valeurs.)

Dans certains cas, les compilateurs émettront une instruction illégale comme x86 ud2pour un bloc qui provoque vraisemblablement UB s'il est exécuté. (Notez qu'une fonction peut ne jamais être appelée, donc les compilateurs ne peuvent généralement pas se déchaîner et casser d'autres fonctions, ou même des chemins possibles à travers une fonction qui n'atteint pas UB. toutes les entrées qui ne mènent pas à UB.)

La solution la plus efficace est probablement de décoller manuellement la dernière itération afin d' factor*=10éviter les inutiles .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Ou si le corps de la boucle est volumineux, envisagez simplement d'utiliser un type non signé pour factor. Ensuite, vous pouvez laisser le débordement multiplier non signé et il fera juste un habillage bien défini à une puissance de 2 (le nombre de bits de valeur dans le type non signé).

C'est très bien même si vous l'utilisez avec des types signés, surtout si votre conversion non signée> signée ne déborde jamais.

La conversion entre le signe non signé et le complément à 2 signé est gratuite (même motif binaire pour toutes les valeurs); l'encapsulage modulo pour int -> unsigned spécifié par la norme C ++ simplifie simplement l'utilisation du même motif binaire, contrairement à son complément ou à son signe / amplitude.

Et unsigned-> signed est tout aussi trivial, bien qu'il soit défini par l'implémentation pour des valeurs supérieures à INT_MAX. Si vous n'utilisez pas l'énorme résultat non signé de la dernière itération, vous n'avez rien à craindre. Mais si vous l'êtes, voir La conversion de non signé en signé n'est-elle pas définie? . Le cas value-does-fit est défini par l'implémentation , ce qui signifie qu'une implémentation doit choisir un comportement; les plus sensés tronquent (si nécessaire) le modèle de bits non signé et l'utilisent comme signé, car cela fonctionne pour les valeurs dans la plage de la même manière sans travail supplémentaire. Et ce n'est certainement pas UB. Les grandes valeurs non signées peuvent donc devenir des entiers signés négatifs. par exemple, après int x = u; gcc et clang ne pas optimiser loinx>=0comme toujours vrai, même sans -fwrapv, car ils définissaient le comportement.

Si vous pouvez tolérer quelques instructions d'assemblage supplémentaires dans la boucle, au lieu de

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

tu peux écrire:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

pour éviter la dernière multiplication. !factorn'introduira pas de branche:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Ce code

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

se traduit également par un assemblage sans branche après optimisation:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Compilé avec GCC 8.3.0 -O3)

Vous n'avez pas montré ce qu'il y a entre parenthèses de la fordéclaration, mais je vais supposer que c'est quelque chose comme ceci:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Vous pouvez simplement déplacer l'incrémentation du compteur et la vérification de la fin de la boucle dans le corps:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Le nombre d'instructions d'assemblage dans la boucle restera le même.

Inspiré par la présentation d'Andrei Alexandrescu "La vitesse se trouve dans l'esprit des gens".

Considérez la fonction:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

D' après la publication Raison d'être , les auteurs de la norme aurait prévu que si cette fonction a été invoquée sur (par exemple) un lieu commun ordinateur 32 bits avec des arguments de 0xC000 et 0xC000, la promotion des opérandes de *la signed intcauserait le calcul pour obtenir -0x10000000 , qui une fois converti en unsigneddonnerait 0x90000000u- la même réponse que s'ils avaient fait la unsigned shortpromotion de unsigned. Néanmoins, gcc optimisera parfois cette fonction de manière à se comporter de manière absurde en cas de débordement. Tout code où une combinaison d'entrées pourrait provoquer un débordement doit être traité avec -fwrapvoption à moins qu'il ne soit acceptable de permettre aux créateurs d'entrées délibérément malformées d'exécuter du code arbitraire de leur choix.

Pourquoi pas ça:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Il existe de nombreux visages différents du comportement indéfini, et ce qui est acceptable dépend de l'utilisation.

boucle interne serrée qui consomme une grande partie du temps CPU total dans une application graphique en temps réel

En soi, c'est un peu inhabituel, mais quoi qu'il en soit ... si c'est effectivement le cas, l'UB est probablement dans le domaine "admissible, acceptable" . La programmation graphique est connue pour les hacks et les trucs laids. Tant qu'il "fonctionne" et qu'il ne faut pas plus de 16,6 ms pour produire un cadre, généralement, personne ne s'en soucie. Mais tout de même, sachez ce que signifie invoquer UB.

Tout d'abord, il y a la norme. De ce point de vue, il n'y a rien à discuter et aucun moyen à justifier, votre code est tout simplement invalide. Il n'y a ni si ni quand, ce n'est tout simplement pas un code valide. Vous pourriez aussi bien dire que c'est du milieu de la main de votre point de vue, et 95-99% du temps, vous serez bon de toute façon.

Ensuite, il y a le côté matériel. Il existe des architectures inhabituelles et étranges où cela pose problème. Je dis "peu commun, bizarre" parce que sur la seule architecture qui représente 80% de tous les ordinateurs (ou les deux architectures qui représentent ensemble 95% de tous les ordinateurs), le débordement est un "ouais, peu importe, peu importe" chose au niveau du matériel. Vous obtenez certainement un résultat poubelle (bien que toujours prévisible), mais rien de mal ne se produit.
Ce n'est pasle cas sur chaque architecture, vous pourriez très bien avoir un piège sur le débordement (bien qu'en voyant comment vous parlez d'une application graphique, les chances d'être sur une architecture aussi étrange soient plutôt petites). La portabilité est-elle un problème? Si c'est le cas, vous voudrez peut-être vous abstenir.

Enfin, il y a le côté compilateur / optimiseur. Une raison pour laquelle le débordement n'est pas défini est que le laisser simplement à ce qui était le plus facile à gérer avec le matériel était une fois. Mais une autre raison est que, par exemple, il x+1est garanti d'être toujours plus grand que x, et le compilateur / optimiseur peut exploiter cette connaissance. Maintenant, dans le cas mentionné précédemment, les compilateurs sont en effet connus pour agir de cette façon et simplement supprimer les blocs complets (il existait il y a quelques années un exploit Linux qui était basé sur le compilateur ayant supprimé le code de validation à cause de cela exactement).
Pour votre cas, je doute sérieusement que le compilateur fasse des optimisations spéciales et étranges. Cependant, que savez-vous, que sais-je. En cas de doute, essayez-le. Si cela fonctionne, vous êtes prêt à partir.

(Et enfin, il y a bien sûr l'audit du code, vous pourriez avoir à perdre votre temps à en discuter avec un auditeur si vous n'avez pas de chance.)