185 votes

Pourquoi GCC génère telle Assemblée radicalement différente pour presque le même code C ?

Lors de l'écriture d'un optimisée ftol de la fonction, j'ai trouvé quelques très étrange comportement en GCC 4.6.1. Permettez-moi de vous montrer le premier code (pour plus de clarté, j'ai marqué les différences):

fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two, C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

Semble que le même droit? Bien GCC n'est pas d'accord. Après la compilation avec gcc -O3 -S -Wall -o test.s test.c c'est l'assemblée de sortie:

fast_trunc_one, généré:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two, généré:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

C'est une extrême différence. En fait, cela s'affiche sur le profil de trop, fast_trunc_one à environ 30% plus rapide que l' fast_trunc_two. Maintenant, ma question: quelle en est la cause?

258voto

Mysticial Points 180300

Mise à jour pour la synchronisation avec l'OP modifier

Par bricoler avec le code, j'ai réussi à voir comment GCC optimise le premier cas.

Avant de comprendre pourquoi ils sont si différents, nous devons d'abord comprendre comment GCC optimise fast_trunc_one().

Croyez le ou non, fast_trunc_one() est optimisé:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

Ce produit exactement de la même assemblée que l'original, fast_trunc_one() - enregistrer des noms et tout et tout.

Notez qu'il n'existe pas de xors dans l'assemblée pour fast_trunc_one(). C'est ce qu'il a donné suite pour moi.


Comment alors?


Étape 1: sign = -sign

Tout d'abord, jetons un coup d'oeil à l' sign variable. Depuis sign = i & 0x80000000;, il y a seulement deux valeurs possibles qu' sign prendre:

  • sign = 0
  • sign = 0x80000000

Maintenant reconnaître que, dans les deux cas, sign == -sign. Donc, quand j'ai changer le code d'origine:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

Il produit exactement de la même assemblée que l'original, fast_trunc_one(). Je vais vous épargner l'assemblée, mais il est identique - enregistrer les noms et tous les.


Étape 2: Mathématiques réduction: x + (y ^ x) = y

sign ne peut prendre que deux valeurs, 0 ou 0x80000000.

  • Lors de l' x = 0, alors x + (y ^ x) = y alors trivial détient.
  • L'ajout et la xoring en 0x80000000 est le même. Il retourne le bit de signe. Par conséquent, x + (y ^ x) = y détient également lors de l' x = 0x80000000.

Par conséquent, x + (y ^ x) réduit de y. Et le code simplifie à ceci:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

Encore une fois, cette compile à la même assemblée - enregistrer les noms et tous les.


Cette version ci-dessus, finalement réduit à ceci:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

qui est à peu près exactement ce que GCC génère dans l'assemblée.


Alors pourquoi ne pas le compilateur d'optimiser fast_trunc_two() à la même chose?

La partie clé en fast_trunc_one() est le x + (y ^ x) = y d'optimisation. En fast_trunc_two() le x + (y ^ x) expression est divisé sein de la direction générale.

Je soupçonne que cela peut être suffisant pour confondre GCC pour ne pas faire de cette optimisation. (Il aurait besoin de hisser l' ^ -sign de la branche et de le fusionner dans l' r + sign à la fin.)

Par exemple, ce produit de la même assemblée que fast_trunc_one():

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}

63voto

dwelch Points 27195

C'est la nature de compilateurs. En supposant qu'ils vont prendre le plus rapide ou le meilleur chemin, c'est tout à fait faux. Toute personne qui implique que vous n'avez pas besoin de faire quelque chose pour votre code afin d'optimiser parce que "les compilateurs modernes" remplir le vide, faire le meilleur travail, faire de la manière la plus rapide de code, etc. En fait j'ai vu gcc s'aggraver à partir de 3.x à 4.x sur les bras, au moins. 4.x pourrait avoir pris jusqu'à 3.x en ce moment, mais dès le début, on produit plus lent code. Avec la pratique, vous pouvez apprendre comment écrire votre code de sorte que le compilateur n'a pas à travailler aussi dur et comme un résultat produit de plus en plus cohérentes et les résultats attendus.

Le bug ici sont vos attentes de ce qui sera produit, pas ce qui était réellement produit. Si vous souhaitez que le compilateur pour générer la même sortie, de le nourrir à la même entrée. Pas mathmatically le même, pas un peu la même chose, mais en fait la même, pas de chemins différents, pas de partage ou de distribuer des opérations à partir d'une version à l'autre. C'est un bon exercice de compréhension de la façon d'écrire votre code et de voir ce que les compilateurs faire avec elle. Ne faites pas l'erreur de croire que parce qu'une version de gcc pour un processeur cible, un jour, a produit un certain résultat, c'est la règle pour tous les compilateurs et l'ensemble du code. Vous devez utiliser beaucoup de compilateurs et de nombreux objectifs pour avoir une idée de ce qui se passe.

gcc est assez méchant, je vous invite à regarder derrière le rideau, regarder les entrailles de la gcc, essayez d'ajouter une cible ou de modifier de quelque chose de vous-même. Il est à peine maintenus ensemble par un ruban et fil de puisage. Un supplément de ligne de code ajoutée ou supprimée dans des endroits critiques et il vient de s'écrouler. Le fait qu'il a produit utilisable code est quelque chose pour être heureux à ce sujet, au lieu de se demander pourquoi il na pas de répondre à d'autres attentes.

avez-vous regardé ce que les différentes versions de gcc produire? 3.x et 4.x en particulier 4.5 vs vs 4.6 4.7, etc? et pour les différents processeurs cibles, x86, arm, mips, etc ou différentes saveurs de x86 si c'est le compilateur natif que vous utilisez, 32 bits vs 64 bits, etc? Et puis llvm (clang) pour des cibles différentes?

Mystique a fait un excellent travail dans le processus de pensée nécessaires pour résoudre le problème de l'analyse et de l'optimisation du code, en attente d'un compilateur à venir avec de de qui est, ainsi, ne s'attend pas du tout "moderne compilateur".

Sans entrer dans le calcul des propriétés, le code de ce formulaire

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

est va conduire le compilateur à: mettre en œuvre sous cette forme, réaliser le si-alors-sinon convergent ensuite vers le code commun pour finir et en revenir. ou B: enregistrer une branche puisque c'est la fin de la queue de la fonction. Aussi de ne pas s'embêter avec l'aide ou de l'enregistrement de la r.

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

Ensuite, vous pouvez obtenir en tant que Mystique, a souligné le signe de la variable disparaît tous ensemble pour le code écrit. Je ne reviendrai pas attendre le compilateur de voir le signe de la variable aller loin si vous devez avez fait vous-même et pas forcé le compilateur pour essayer de le comprendre.

Ce est une occasion parfaite pour creuser dans le code source de gcc. Il semble que vous avez trouvé un cas où l'optimiseur a vu une chose dans un cas, puis une autre chose dans un autre cas. Puis prendre la prochaine étape et de voir si vous arrivez à gcc de voir cette affaire. Chaque optimisation est là parce qu'un individu ou d'un groupe reconnu l'optimisation et intentionnellement mis là. Pour cette optimisation d'être là et de travail à chaque fois que quelqu'un l'a mis là (et puis le tester, et le maintenir dans le futur).

Certainement ne pas supposer que moins de code est plus rapide et plus code est plus lent, il est très facile de créer et de trouver des exemples de ce n'est pas vrai. Il serait peut-être plus souvent que de ne pas être le cas de moins de code étant plus rapide que plus de code. Comme je l'ai démontré depuis le début si vous pouvez créer plus d'un code à enregistrer de ramification dans ce cas, ou en boucle, etc et avoir le résultat net serait plus rapide de code.

La ligne de fond est que vous nourrissiez d'un compilateur source différente et d'attendre les mêmes résultats. Le problème n'est pas la sortie du compilateur, mais les attentes de l'utilisateur. Il est assez facile à démontrer pour un compilateur et d'un processeur, l'ajout d'une ligne de code qui fait toute la fonction considérablement plus lent. Par exemple, pourquoi le fait de passer a = b + 2; a = b + c + 2; cause _fill_in_the_blank_compiler_name_ générer radicalement différent et plus lent code? La réponse étant bien sûr le compilateur a été nourri différents code de l'entrée et il est parfaitement valable pour le compilateur pour générer de sortie différents. (encore mieux, lorsque vous permutez deux indépendants des lignes de code et la cause de la sortie à changer de façon spectaculaire) Il n'y a pas de relation attendue entre la complexité et de la taille de l'entrée de la complexité et de la taille de la sortie. Nourrir quelque chose comme cela dans clang:

for(ra=0;ra<20;ra++) dummy(ra);

Il produit quelque part entre 60 à 100 lignes d'assembleur. Il déroulé la boucle. Je n'ai pas compter les lignes, si vous pensez cela, il a à ajouter, copier le résultat à l'entrée à l'appel de la fonction, de faire l'appel de fonction, trois opérations minimum. donc, en fonction de la cible, qui est probablement 60 instructions d'au moins 80 si quatre par boucle, 100 si cinq par boucle, etc.

23voto

Maristic Points 533

Mysticial a déjà donné une bonne explication, mais je pensais que je voudrais ajouter, FWIW, qu'il n'y a vraiment rien de fondamental sur les raisons d'un compilateur pourrait faire de l'optimisation pour l'un et pas l'autre.

De LLVM clang compilateur, par exemple, donne le même code pour les deux fonctions (sauf pour le nom de la fonction):

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

Ce code n'est pas aussi courte que la première version de gcc à partir de l'OP, mais pas aussi longue que la seconde.

Le Code d'un autre compilateur (dont je tairai le nom), la compilation pour x86_64, produit de la ce pour les deux fonctions:

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret                         

ce qui est fascinant en ce qu'il calcule des deux côtés de l' if , puis utilise un conditionnel de se déplacer à la fin de choisir le bon.

Le Open64 compilateur produit est le suivant:

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538                  

et similaires, mais pas identiques, code fast_trunc_two.

De toute façon, quand il s'agit de l'optimisation, c'est une loterie, c'est ce que c'est... Il n'est pas toujours facile de savoir pourquoi vous code sera compilé une manière particulière.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X