Pourquoi cette boucle produit-elle «avertissement: l'itération 3u appelle un comportement indéfini» et produit plus de 4 lignes?

Compiler ceci:

#include <iostream>

int main()
{
    for (int i = 0; i < 4; ++i)
        std::cout << i*1000000000 << std::endl;
}

et gccproduit l'avertissement suivant:

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

Je comprends qu'il y a un débordement d'entier signé.

Ce que je ne peux pas obtenir, c'est pourquoi la ivaleur est cassée par cette opération de débordement?

J'ai lu les réponses à Pourquoi un débordement d'entier sur x86 avec GCC provoque-t-il une boucle infinie? , mais je ne sais toujours pas pourquoi cela se produit - j'obtiens que «indéfini» signifie «tout peut arriver», mais quelle est la cause sous-jacente de ce comportement spécifique ?

En ligne: http://ideone.com/dMrRKR

Compilateur: gcc (4.8)

Un débordement d'entier signé (à proprement parler, il n'y a pas de "débordement d'entier non signé") signifie un comportement indéfini . Et cela signifie que tout peut arriver, et discuter de pourquoi cela se produit selon les règles de C ++ n'a pas de sens.

Projet C ++ 11 N3337: §5.4: ¹

Si lors de l'évaluation d'une expression, le résultat n'est pas défini mathématiquement ou n'est pas dans la plage de valeurs représentables de son type, le comportement est indéfini. [Remarque: la plupart des implémentations existantes de C ++ ignorent les débordements d'entiers. Le traitement de la division par zéro, formant un reste en utilisant un diviseur nul, et toutes les exceptions de point flottant varient selon les machines et est généralement ajustable par une fonction de bibliothèque. —End note]

Votre code compilé avec g++ -O3émet un avertissement (même sans -Wall)

a.cpp: In function 'int main()':
a.cpp:11:18: warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^
a.cpp:9:2: note: containing loop
  for (int i = 0; i < 4; ++i)
  ^

La seule façon d'analyser ce que fait le programme est de lire le code d'assemblage généré.

Voici la liste complète de l'assemblage:

    .file   "a.cpp"
    .section    .text$_ZNKSt5ctypeIcE8do_widenEc,"x"
    .linkonce discard
    .align 2
LCOLDB0:
LHOTB0:
    .align 2
    .p2align 4,,15
    .globl  __ZNKSt5ctypeIcE8do_widenEc
    .def    __ZNKSt5ctypeIcE8do_widenEc;    .scl    2;  .type   32; .endef
__ZNKSt5ctypeIcE8do_widenEc:
LFB860:
    .cfi_startproc
    movzbl  4(%esp), %eax
    ret $4
    .cfi_endproc
LFE860:
LCOLDE0:
LHOTE0:
    .section    .text.unlikely,"x"
LCOLDB1:
    .text
LHOTB1:
    .p2align 4,,15
    .def    ___tcf_0;   .scl    3;  .type   32; .endef
___tcf_0:
LFB1091:
    .cfi_startproc
    movl    $__ZStL8__ioinit, %ecx
    jmp __ZNSt8ios_base4InitD1Ev
    .cfi_endproc
LFE1091:
    .section    .text.unlikely,"x"
LCOLDE1:
    .text
LHOTE1:
    .def    ___main;    .scl    2;  .type   32; .endef
    .section    .text.unlikely,"x"
LCOLDB2:
    .section    .text.startup,"x"
LHOTB2:
    .p2align 4,,15
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
LFB1084:
    .cfi_startproc
    leal    4(%esp), %ecx
    .cfi_def_cfa 1, 0
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    .cfi_escape 0x10,0x5,0x2,0x75,0
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    pushl   %ecx
    .cfi_escape 0xf,0x3,0x75,0x70,0x6
    .cfi_escape 0x10,0x7,0x2,0x75,0x7c
    .cfi_escape 0x10,0x6,0x2,0x75,0x78
    .cfi_escape 0x10,0x3,0x2,0x75,0x74
    xorl    %edi, %edi
    subl    $24, %esp
    call    ___main
L4:
    movl    %edi, (%esp)
    movl    $__ZSt4cout, %ecx
    call    __ZNSolsEi
    movl    %eax, %esi
    movl    (%eax), %eax
    subl    $4, %esp
    movl    -12(%eax), %eax
    movl    124(%esi,%eax), %ebx
    testl   %ebx, %ebx
    je  L15
    cmpb    $0, 28(%ebx)
    je  L5
    movsbl  39(%ebx), %eax
L6:
    movl    %esi, %ecx
    movl    %eax, (%esp)
    addl    $1000000000, %edi
    call    __ZNSo3putEc
    subl    $4, %esp
    movl    %eax, %ecx
    call    __ZNSo5flushEv
    jmp L4
    .p2align 4,,10
L5:
    movl    %ebx, %ecx
    call    __ZNKSt5ctypeIcE13_M_widen_initEv
    movl    (%ebx), %eax
    movl    24(%eax), %edx
    movl    $10, %eax
    cmpl    $__ZNKSt5ctypeIcE8do_widenEc, %edx
    je  L6
    movl    $10, (%esp)
    movl    %ebx, %ecx
    call    *%edx
    movsbl  %al, %eax
    pushl   %edx
    jmp L6
L15:
    call    __ZSt16__throw_bad_castv
    .cfi_endproc
LFE1084:
    .section    .text.unlikely,"x"
LCOLDE2:
    .section    .text.startup,"x"
LHOTE2:
    .section    .text.unlikely,"x"
LCOLDB3:
    .section    .text.startup,"x"
LHOTB3:
    .p2align 4,,15
    .def    __GLOBAL__sub_I_main;   .scl    3;  .type   32; .endef
__GLOBAL__sub_I_main:
LFB1092:
    .cfi_startproc
    subl    $28, %esp
    .cfi_def_cfa_offset 32
    movl    $__ZStL8__ioinit, %ecx
    call    __ZNSt8ios_base4InitC1Ev
    movl    $___tcf_0, (%esp)
    call    _atexit
    addl    $28, %esp
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc
LFE1092:
    .section    .text.unlikely,"x"
LCOLDE3:
    .section    .text.startup,"x"
LHOTE3:
    .section    .ctors,"w"
    .align 4
    .long   __GLOBAL__sub_I_main
.lcomm __ZStL8__ioinit,1,1
    .ident  "GCC: (i686-posix-dwarf-rev1, Built by MinGW-W64 project) 4.9.0"
    .def    __ZNSt8ios_base4InitD1Ev;   .scl    2;  .type   32; .endef
    .def    __ZNSolsEi; .scl    2;  .type   32; .endef
    .def    __ZNSo3putEc;   .scl    2;  .type   32; .endef
    .def    __ZNSo5flushEv; .scl    2;  .type   32; .endef
    .def    __ZNKSt5ctypeIcE13_M_widen_initEv;  .scl    2;  .type   32; .endef
    .def    __ZSt16__throw_bad_castv;   .scl    2;  .type   32; .endef
    .def    __ZNSt8ios_base4InitC1Ev;   .scl    2;  .type   32; .endef
    .def    _atexit;    .scl    2;  .type   32; .endef

Je peux à peine lire l'assemblage, mais même je peux voir la addl $1000000000, %ediligne. Le code résultant ressemble plus à

for(int i = 0; /* nothing, that is - infinite loop */; i += 1000000000)
    std::cout << i << std::endl;

Ce commentaire de @TC:

Je soupçonne que c'est quelque chose comme: (1) parce que chaque itération avec iune valeur supérieure à 2 a un comportement non défini -> (2) nous pouvons supposer qu'à i <= 2des fins d'optimisation -> (3) la condition de boucle est toujours vraie -> (4 ) il est optimisé dans une boucle infinie.

m'a donné l'idée de comparer le code d'assemblage du code de l'OP au code d'assemblage du code suivant, sans comportement indéfini.

#include <iostream>

int main()
{
    // changed the termination condition
    for (int i = 0; i < 3; ++i)
        std::cout << i*1000000000 << std::endl;
}

Et, en fait, le code correct a une condition de terminaison.

    ; ...snip...
L6:
    mov ecx, edi
    mov DWORD PTR [esp], eax
    add esi, 1000000000
    call    __ZNSo3putEc
    sub esp, 4
    mov ecx, eax
    call    __ZNSo5flushEv
    cmp esi, -1294967296 // here it is
    jne L7
    lea esp, [ebp-16]
    xor eax, eax
    pop ecx
    ; ...snip...

OMG, ce n'est pas du tout évident! Ce n'est pas juste! J'exige un procès par le feu!

Traitez-le, vous avez écrit le code du buggy et vous devriez vous sentir mal. Supportez les conséquences.

... ou, alternativement, utilisez correctement de meilleurs diagnostics et de meilleurs outils de débogage - c'est à cela qu'ils servent:

• activer tous les avertissements

  • -Wallest l'option gcc qui active tous les avertissements utiles sans faux positifs. C'est un strict minimum que vous devez toujours utiliser.
  • gcc a de nombreuses autres options d'avertissement , cependant, elles ne sont pas activées -Wallcar elles peuvent avertir des faux positifs
  • Visual C ++ est malheureusement à la traîne avec la possibilité de donner des avertissements utiles. Au moins l'EDI en permet certains par défaut.

• utiliser des indicateurs de débogage pour le débogage

  • pour le débordement d'entier -ftrapvintercepte le programme en cas de débordement,
  • Compilateur Clang est excellent pour cela: -fcatch-undefined-behaviorattrape beaucoup de cas de comportement non défini (note: "a lot of" != "all of them")

J'ai un désordre spaghetti d'un programme non écrit par moi qui doit être expédié demain! AIDE !!!!!! 111oneone

Utilisez gcc -fwrapv

Cette option demande au compilateur de supposer que le débordement arithmétique signé d'addition, de soustraction et de multiplication s'enroule en utilisant la représentation à complément à deux.

¹ - cette règle ne s'applique pas au "débordement d'entier non signé", comme le §3.9.1.4 dit que

Les entiers non signés, déclarés non signés, doivent obéir aux lois de l'arithmétique modulo 2 ⁿ où n est le nombre de bits dans la représentation de valeur de cette taille particulière d'entier.

et par exemple le résultat de UINT_MAX + 1est défini mathématiquement - par les règles de l'arithmétique modulo 2 ⁿ

Réponse courte, a gccspécifiquement documenté ce problème, nous pouvons voir que dans les notes de publication de gcc 4.8 qui dit ( je souligne à l'avenir ):

GCC utilise maintenant une analyse plus agressive pour dériver une limite supérieure du nombre d'itérations de boucles en utilisant des contraintes imposées par les standards du langage . Cela peut empêcher les programmes non conformes de fonctionner comme prévu, tels que SPEC CPU 2006 464.h264ref et 416.gamess. Une nouvelle option, -fno-aggressive-loop-optimisations, a été ajoutée pour désactiver cette analyse agressive. Dans certaines boucles qui ont connu un nombre constant d'itérations, mais un comportement indéfini est connu pour se produire dans la boucle avant d'atteindre ou pendant la dernière itération, GCC avertira du comportement indéfini dans la boucle au lieu de dériver la limite supérieure inférieure du nombre d'itérations pour la boucle. L'avertissement peut être désactivé avec -Wno-aggressif-loop-optimisations.

et en effet si nous utilisons -fno-aggressive-loop-optimizationsla boucle infinie, le comportement devrait cesser et c'est le cas dans tous les cas que j'ai testés.

La réponse longue commence par savoir que le débordement d' entier signé est un comportement indéfini en regardant le projet de section standard C ++ 5 Expressions paragraphe 4 qui dit:

Si lors de l'évaluation d'une expression, le résultat n'est pas défini mathématiquement ou n'est pas dans la plage de valeurs représentables pour son type, le comportement n'est pas défini . [Remarque: la plupart des implémentations existantes de C ++ ignorent les débordements d'entiers. Le traitement de la division par zéro, formant un reste à l'aide d'un diviseur nul, et toutes les exceptions en virgule flottante varient selon les machines et est généralement ajustable par une fonction de bibliothèque. —End note

Nous savons que la norme dit qu'un comportement non défini est imprévisible d'après la note fournie avec la définition qui dit:

[Note: Un comportement non défini peut être attendu lorsque la présente Norme internationale omet toute définition explicite du comportement ou lorsqu'un programme utilise une construction erronée ou des données erronées. Le comportement indéfini autorisé va de l'ignorance totale de la situation avec des résultats imprévisibles , au comportement pendant la traduction ou l'exécution du programme d'une manière documentée caractéristique de l'environnement (avec ou sans l'émission d'un message de diagnostic), à la fin d'une traduction ou d'une exécution (avec l'émission d'un message de diagnostic). De nombreuses constructions de programme erronées n'engendrent pas de comportement indéfini; ils doivent être diagnostiqués. —End note]

Mais que diable peut faire l' gccoptimiseur pour transformer cela en une boucle infinie? Cela semble complètement farfelu. Mais heureusement, gccnous donne un indice pour le comprendre dans l'avertissement:

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

L'indice est le Waggressive-loop-optimizations, qu'est-ce que cela signifie? Heureusement pour nous, ce n'est pas la première fois que cette optimisation a cassé le code de cette manière et nous avons de la chance car John Regehr a documenté un cas dans l'article GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks qui montre le code suivant:

int d[16];

int SATD (void)
{
  int satd = 0, dd, k;
  for (dd=d[k=0]; k<16; dd=d[++k]) {
    satd += (dd < 0 ? -dd : dd);
  }
  return satd;
}

l'article dit:

Le comportement non défini accède à d [16] juste avant de quitter la boucle. Dans C99, il est légal de créer un pointeur vers un élément une position après la fin du tableau, mais ce pointeur ne doit pas être déréférencé.

et plus tard dit:

En détail, voici ce qui se passe. Le compilateur AC, en voyant d [++ k], est autorisé à supposer que la valeur incrémentée de k se trouve dans les limites du tableau, car autrement un comportement indéfini se produit. Pour le code ici, GCC peut déduire que k est compris entre 0 et 15. Un peu plus tard, quand GCC voit k <16, il se dit: "Aha - cette expression est toujours vraie, donc nous avons une boucle infinie." La situation ici, où le compilateur utilise l'hypothèse d'une bonne définition pour déduire un fait utile de flux de données,

Donc, ce que le compilateur doit faire dans certains cas, c'est supposer que le débordement d'entier signé est un comportement indéfini, alors idoit toujours être inférieur à 4et donc nous avons une boucle infinie.

Il explique que cela est très similaire à la tristement célèbre suppression de la vérification du pointeur nul du noyau Linux où en voyant ce code:

struct foo *s = ...;
int x = s->f;
if (!s) return ERROR;

gccdéduit que puisque a sété déférencé dans s->f;et puisque le déréférencement d'un pointeur nul est un comportement indéfini, alors sne doit pas être nul et donc optimise la if (!s)vérification sur la ligne suivante.

La leçon ici est que les optimiseurs modernes sont très agressifs pour exploiter un comportement non défini et ne seront probablement que plus agressifs. Clairement, avec juste quelques exemples, nous pouvons voir que l'optimiseur fait des choses qui semblent complètement déraisonnables pour un programmeur, mais rétrospectivement du point de vue des optimiseurs, cela a du sens.

tl; dr Le code génère un test que entier + entier positif == entier négatif . Habituellement, l'optimiseur n'optimise pas cela, mais dans le cas spécifique d' std::endlêtre utilisé ensuite, le compilateur optimise ce test. Je n'ai pas encore compris ce qui est spécial endl.

À partir du code d'assemblage à -O1 et aux niveaux supérieurs, il est clair que gcc refactorise la boucle en:

i = 0;
do {
    cout << i << endl;
    i += NUMBER;
} 
while (i != NUMBER * 4)

La plus grande valeur qui fonctionne correctement est 715827882, ie floor ( INT_MAX/3). L'extrait d'assembly à -O1est:

L4:
movsbl  %al, %eax
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
addl    $715827882, %esi
cmpl    $-1431655768, %esi
jne L6
    // fallthrough to "return" code

Notez que le -1431655768est 4 * 715827882en complément de 2.

Frapper -O2optimise cela comme suit:

L4:
movsbl  %al, %eax
addl    $715827882, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655768, %esi
jne L6
leal    -8(%ebp), %esp
jne L6 
   // fallthrough to "return" code

Ainsi, l'optimisation qui a été faite est simplement que le a addlété déplacé plus haut.

Si nous recompilons avec à la 715827883place, la version -O1 est identique à l'exception du nombre et de la valeur de test modifiés. Cependant, -O2 fait alors un changement:

L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2

Là où il y avait cmpl $-1431655764, %esià -O1, cette ligne a été supprimé car -O2. L'optimiseur doit avoir décidé que l'ajout 715827883à %esine peut jamais égaler -1431655764.

C'est assez déroutant. Ajoutant que pour INT_MIN+1 ne générer le résultat attendu, de sorte que l'optimiseur doit avoir décidé que %esine peut jamais être INT_MIN+1et je ne sais pas pourquoi il déciderait que.

Dans l'exemple de travail, il semble qu'il serait également valable de conclure que l'ajout 715827882à un nombre ne peut pas égaler INT_MIN + 715827882 - 2! (cela n'est possible que si le bouclage se produit réellement), mais cela n'optimise pas la sortie de ligne dans cet exemple.

Le code que j'utilisais est:

#include <iostream>
#include <cstdio>

int main()
{
    for (int i = 0; i < 4; ++i)
    {
        //volatile int j = i*715827883;
        volatile int j = i*715827882;
        printf("%d\n", j);

        std::endl(std::cout);
    }
}

Si le std::endl(std::cout)est supprimé, l'optimisation ne se produit plus. En fait, le remplacer par std::cout.put('\n'); std::flush(std::cout);empêche également l'optimisation, même si elle std::endlest intégrée.

L'inlining de std::endlsemble affecter la partie antérieure de la structure de la boucle (ce que je ne comprends pas très bien ce qu'elle fait mais je la posterai ici au cas où quelqu'un d'autre le ferait):

Avec code d'origine et -O2:

L2:
movl    %esi, 28(%esp)
movl    28(%esp), %eax
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    __ZSt4cout, %eax
movl    -12(%eax), %eax
movl    __ZSt4cout+124(%eax), %ebx
testl   %ebx, %ebx
je  L10
cmpb    $0, 28(%ebx)
je  L3
movzbl  39(%ebx), %eax
L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2                  // no test

Avec inline mymanual de std::endl, -O2:

L3:
movl    %ebx, 28(%esp)
movl    28(%esp), %eax
addl    $715827883, %ebx
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    $10, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    $__ZSt4cout, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655764, %ebx
jne L3
xorl    %eax, %eax

Une différence entre ces deux est qu'il %esiest utilisé dans l'original et %ebxdans la deuxième version; y a-t-il une différence de sémantique définie entre %esiet %ebxen général? (Je ne sais pas grand chose sur l'assemblage x86).

Un autre exemple de cette erreur signalée dans gcc est lorsque vous avez une boucle qui s'exécute pendant un nombre constant d'itérations, mais que vous utilisez la variable de compteur comme index dans un tableau qui a moins que ce nombre d'éléments, comme:

int a[50], x;

for( i=0; i < 1000; i++) x = a[i];

Le compilateur peut déterminer que cette boucle tentera d'accéder à la mémoire en dehors du tableau «a». Le compilateur s'en plaint avec ce message plutôt cryptique:

l'itération xxu appelle un comportement indéfini [-Werror = aggressives-loop-optimisations]

Ce que je ne peux pas obtenir, c'est pourquoi ma valeur est interrompue par cette opération de débordement?

Il semble qu'un débordement d'entier se produise dans la 4e itération (pour i = 3). signedle dépassement d'entier appelle un comportement indéfini . Dans ce cas, rien ne peut être prédit. La boucle peut itérer seulement des 4fois ou aller à l'infini ou autre chose!
Le résultat peut varier du compilateur au compilateur ou même pour différentes versions du même compilateur.

C11: 1.3.24 comportement non défini:

comportement pour lequel la présente Norme internationale n'impose aucune exigence
[Note: Un comportement indéfini peut être attendu lorsque la présente Norme internationale omet toute définition explicite de comportement ou lorsqu'un programme utilise une construction erronée ou des données erronées. Le comportement indéfini autorisé va de l'ignorance totale de la situation avec des résultats imprévisibles, au comportement pendant la traduction ou l'exécution du programme d'une manière documentée caractéristique de l'environnement (avec ou sans l'émission d'un message de diagnostic), à la fin d'une traduction ou d'une exécution (avec l'émission d'un message de diagnostic) . De nombreuses constructions de programme erronées n'engendrent pas de comportement indéfini; ils doivent être diagnostiqués. —End note]