Pourquoi cette boucle produit « AVERTISSEMENT : itération 3u invoque un comportement indéfini » et plus de 4 lignes de sortie ?

Question

La compilation de ce:

#include <iostream>

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

et gcc produit le message d'avertissement suivant:

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

Je comprends, il y est un nombre entier signé de débordement.

Ce que je ne peux pas obtenir est pourquoi, i de la valeur est cassé par le débordement de l'opération?

J'ai lu les réponses à Pourquoi débordement d'entier sur x86 avec GCC provoquer une boucle infinie?, mais je ne suis pas encore au clair sur pourquoi cela se produit - je obtenir que "undefined" signifie "tout peut arriver", mais quelle est la cause sous-jacente de ce comportement particulier?

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

Compilateur: gcc (4.8)

Answer 1

Signé débordement d'entier (comme strictement parlant, il n'y a pas une telle chose comme "unsigned integer overflow") signifie un comportement indéterminé. Et cela signifie que tout peut arriver, et de discuter de pourquoi faut-il se produire dans les règles de C++ n'a pas de sens.

C++11 projet de N3337: §5.4:¹

Si, lors de l'évaluation d'une expression, le résultat n'est pas mathématiquement définie ou non dans la gamme de représentable valeurs pour son type, le comportement est indéfini. [ Note: la plupart des implémentations existantes de C++ ignorer les débordements d'entiers. Traitement de division par zéro, formant un reste à l'aide d'un diviseur de zéro, et tous les virgule flottante exceptions varient entre machines, et est généralement réglable par une fonction de la bibliothèque. -la note de fin ]

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 que nous pouvons analyser ce que le programme est en train de faire, c'est de lire le code assembleur généré.

Voici l'assemblage complet d'inscription:

    .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 même assemblée, mais même moi, je peux voir l' addl $1000000000, %ediligne de. 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 @T. C.:

Je soupçonne que c'est quelque chose comme: (1) parce qu'à chaque itération avec i de la valeur de plus de 2 a un comportement indéfini -> (2), on peut supposer qu' i <= 2 pour des raisons d'optimisation -> (3) la condition de la boucle est toujours vrai -> (4) il est optimisé à l'écart dans une boucle infinie.

m'a donné l'idée de comparer l'assemblée du code de l'OP du code de l'assemblée de code de le code suivant, avec aucun 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 condition de résiliation.

    ; ...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, c'est pas du tout évident! Ce n'est pas juste! Je demande à l'épreuve du feu!

Traiter avec elle, vous avez écrit le code bogué et vous devriez vous sentir mal. En supporter les conséquences.

...ou, sinon, de faire bon usage de l'amélioration des diagnostics et des meilleurs outils de débogage - c'est ce qu'ils sont pour:

• permettre à tous les avertissements

  • -Wall est la gcc avec l'option qui permet à tous les avertissements utiles sans faux positifs. C'est un strict minimum que vous devez toujours utiliser.
  • gcc a beaucoup d'autres options d'alerte, cependant, ils ne sont pas activés avec -Wall car ils peuvent avertir sur les faux positifs
  • Visual C++, malheureusement, est à la traîne avec la capacité de donner des avertissements utiles. Au moins l'IDE permet à certains par défaut.

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

  • pour de dépassement d'entier, -ftrapv pièges du programme sur le dépassement,
  • Compilateur Clang est excellent pour cela: -fcatch-undefined-behavior des captures un grand nombre de cas de comportement indéfini (note: "a lot of" != "all of them")

J'ai un spaghetti désordre d'un programme n'est pas écrit par moi qui doit être livré demain! AIDER!!!!!!111oneone

L'utilisation de gcc -fwrapv

Cette option indique au compilateur de supposer que signée de dépassement de capacité arithmétique d'addition, de soustraction et de multiplication s'enroule autour de l'aide de deux-complément de la représentation.

¹ - cette règle ne s'applique pas aux "unsigned integer overflow", §3.9.1.4 dit que

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

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

Answer 2

Réponse courte, gcc spécifiquement a documenté ce problème, nous pouvons voir que dans le gcc 4.8 notes de version qui est dit (c'est moi qui souligne à l'avenir):

GCC utilise maintenant une plus agressif de l'analyse afin d'obtenir une limite supérieure pour les le nombre d'itérations des boucles à l'aide de contraintes imposées par les normes linguistiques. Cela peut entraîner la non-conformité des programmes de comme prévu, tels que SPEC CPU 2006 464.h264ref et 416.gamess. Une nouvelle option, l'option-fno-agressif-boucle-optimisations, a été ajouté pour désactiver cette agressifs analyse. Dans certaines boucles qui ont connu constante nombre d'itérations, mais un comportement indéfini est connu de se produire dans la boucle avant d'atteindre ou au cours de la dernière itération, GCC avertir sur le comportement non défini dans la boucle au lieu de tirer inférieure à la limite supérieure du nombre d'itérations de la boucle. L' l'avertissement peut être désactivé avec l'-Wno-agressif-boucle-optimisations.

et en effet, si nous utilisons -fno-aggressive-loop-optimizations la boucle infinie comportement doit cesser et il le fait dans tous les cas, j'ai testé.

La réponse commence par savoir qui a signé integer overflow est un comportement indéfini en regardant le projet de norme C++ section 5 Expressions paragraphe 4 qui dit:

Si, lors de l'évaluation d'une expression, le résultat n'est pas mathématiquement définie ou non dans la gamme de représentable valeurs pour son type, le comportement est indéfini. [ Note: la plupart des les implémentations de C++ ignorer les débordements d'entiers. Le traitement de la division par zéro, formant un reste à l'aide d'un diviseur de zéro, et toutes les point exceptions varient entre machines, et est généralement réglable par un fonction de la bibliothèque. -la note de fin de

Nous savons que la norme ne dit pas défini le comportement est imprévisible à partir de la note qui viennent avec la définition qui dit:

[ Note: un comportement Indéfini peut être prévu lors de cette Internationale Standard omet aucune définition explicite de comportement ou lorsqu'un programme utilise une construction erronée ou de données erronées. Admissible undefined le comportement varie d'ignorer la situation complètement avec des résultats imprévisibles, à se comporter lors de la traduction le programme l'exécution dans un documentées de façon caractéristique de l'environnement (avec ou sans émission d'un message de diagnostic), à la terminaison d' une traduction ou l'exécution (avec l'émission d'un diagnostic message). De nombreux erronée programme de constructions de ne pas engendrer undefined comportement; ils sont tenus d'être diagnostiqué. -la note de fin ]

Mais ce qui dans le monde peut l' gcc optimiseur de faire pour transformer cela en une boucle infinie? Il semble complètement farfelu. Mais heureusement, gcc nous donne un indice pour essayer de le comprendre dans l'avertissement:

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

L'indice est l' Waggressive-loop-optimizations, ça veut dire quoi? Heureusement pour nous ce n'est pas la première fois cette optimisation a brisé le code de cette façon et nous sommes chanceux parce que John Regehr a documenté un cas dans l'article de GCC pré-4.8 Pauses Cassé SPEC 2006 Repères 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 sortir de la de la boucle. En C99, il est légal de créer un pointeur sur un élément de l'un position après la fin du tableau, mais le pointeur ne doit pas être déréférencé.

et plus tard dit:

Dans le détail, voici ce qu'il se passe. Un compilateur C, à la vue d[++k], est permis de supposer que la valeur incrémentée de k est à l'intérieur de la les limites du tableau, car sinon comportement imprévisible se produit. Pour le code ici, GCC peut en déduire que k est dans l'intervalle 0..15. Un peu plus tard, quand GCC voit k<16, il est dit de lui-même: "Aha– cette expression est toujours vrai, nous avons donc une boucle infinie." La situation ici, où l' compilateur utilise l'hypothèse de bien-definedness à déduire une utile flux de données de fait,

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

Il explique ce qui est très similaire à l'infâme noyau Linux pointeur null vérifier suppression de où en voyant ce code:

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

gcc déduit que, depuis s a été deferenced en s->f; et depuis le déréférencement d'un pointeur null est un comportement indéfini alors s ne doit pas être null et donc optimise loin l' if (!s) case sur la ligne suivante.

La leçon ici est que les optimiseurs sont très agressifs sur l'exploitation de comportement indéfini et, très probablement, sera de plus en plus agressif. Clairement avec juste quelques exemples, nous pouvons voir l'optimiseur ne des choses qui semblent tout à fait déraisonnable d'un programmeur, mais, rétrospectivement, à partir de la optimiseurs point de vue du sens.

Answer 3

tl;dr Le code génère un test entier + entier positif == entier négatif. Habituellement, l'optimiseur ne pas optimiser, mais dans le cas spécifique de l' std::endl utilisé prochain, le compilateur n'a optimiser ce test. Je n'ai pas compris quelle est la particularité de l' endl encore.

---

De l'assemblée de code à -O1 et des niveaux plus élevés, il est clair que gcc refactors de la boucle:

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

La valeur la plus grande qui fonctionne correctement est - 715827882, c'est à dire étage(INT_MAX/3). L'assemblée extrait à l' -O1 est:

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

Remarque, l' -1431655768 est 4 * 715827882 en complément de 2.

Frapper -O2 optimise qu'à la suivante:

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

Donc l'optimisation qui a été fait est simplement que l' addl a été déplacé plus haut.

Si nous recompiler avec 715827883 au lieu ensuite l'-O1 version est identique à part le changement de nombre et de valeur de test. Cependant, -O2 puis effectue 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

Où il y avait cmpl $-1431655764, %esi à -O1, de cette ligne a été supprimée -O2. L'optimiseur doit avoir décidé que l'ajout d' 715827883 de %esi ne peut jamais égaux -1431655764.

C'est assez déroutant. Ajoutant que d' INT_MIN+1 ne génèrent le résultat attendu, de sorte que l'optimiseur doit avoir décidé qu' %esi ne peut jamais être INT_MIN+1 et je ne sais pas pourquoi il en serait de décider que.

Dans l'exemple, il semble qu'il serait tout aussi valable de conclure que l'ajout d' 715827882 pour un nombre ne peut pas égaler INT_MIN + 715827882 - 2 ! (ceci n'est possible que si enveloppante fait de se produire), mais il n'optimise pas la ligne dans cet exemple.

---

Le code que j'ai été en utilisant:

#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 l' std::endl(std::cout) est supprimé puis l'optimisation ne se produit plus. En fait le remplaçant par std::cout.put('\n'); std::flush(std::cout); provoque également l'optimisation de ne pas se produire, même si std::endl est incorporé.

L'inlining de std::endl semble nuire à la partie antérieure de la structure de boucle (que je ne comprends pas très bien ce qu'il fait mais je vais le poster ici au cas où quelqu'un d'autre):

Avec le 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 mymanual inlining 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, c'est qu' %esi est utilisé dans l'original , et %ebx dans la deuxième version; est-il une différence de sémantique définie entre %esi et %ebx en général? (Je ne sais pas beaucoup sur x86 assemblée).

Answer 4

Ce que je ne peux pas obtenir est pourquoi j'valeur est cassé par le débordement de l'opération?

signed de dépassement d'entier invoque un comportement indéfini. Dans ce cas, rien ne peut être prédit. La boucle peut itérer seulement 4 fois ou il peut aller à l'infini ou quoi que ce soit d'autre!
Le résultat peut varier compilateur de compilateur ou même pour les différentes versions d'un même compilateur.

C11: 1.3.24 comportement indéfini:

le comportement pour lequel la présente Norme Internationale n'impose pas d'exigences
[ Note: un comportement Indéfini peut être prévu lorsque la présente Norme Internationale omet aucune définition explicite de comportement ou lorsqu'un programme utilise une construction erronée ou de données erronées. Admissible comportement indéfini plages d'ignorer la situation complètement avec des résultats imprévisibles, à se comporter lors de la traduction ou de l'exécution du programme dans documenté de façon caractéristique de l'environnement (avec ou sans émission d'un message de diagnostic), à la terminaison d'une traduction ou d'exécution (avec l'émission d'un message de diagnostic). De nombreux erronée programme de constructions de ne pas engendrer un comportement indéfini; ils sont tenus d'être diagnostiqué. -la note de fin ]