Pourquoi GCC ne peut-il pas optimiser ce code simple?

Question

Voici deux fonctions qui je demande de faire exactement la même chose:

bool fast(int x)
{
  return x & 4242;
}

bool slow(int x)
{
  return x && (x & 4242);
}

Logiquement, ils font la même chose, et juste pour être sûr à 100%, j'ai écrit un test qui a couru tous les quatre milliards d'entrées possibles par le biais de deux d'entre eux, et qu'ils correspondaient. Mais le code assembleur est une autre histoire:

fast:
    andl    $4242, %edi
    setne   %al
    ret

slow:
    xorl    %eax, %eax
    testl   %edi, %edi
    je      .L3
    andl    $4242, %edi
    setne   %al
.L3:
    rep
    ret

J'ai été surpris de voir que GCC ne pouvait pas faire le saut de la logique pour éliminer le test redondants. J'ai essayé de g++ 4.4.3 et 4.7.2 avec -O2-O3, et-Os, tout ce qui a généré le même code. La plate-forme Linux x86_64.

Quelqu'un peut m'expliquer pourquoi GCC ne devrait pas être assez intelligente pour générer le même code dans les deux cas? Je voudrais aussi savoir si d'autres compilateurs peuvent faire mieux.

Modifier pour ajouter un harnais de test:

#include <cstdlib>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
    // make vector filled with numbers starting from argv[1]
    int seed = atoi(argv[1]);
    vector<int> v(100000);
    for (int j = 0; j < 100000; ++j)
        v[j] = j + seed;

    // count how many times the function returns true
    int result = 0;
    for (int j = 0; j < 100000; ++j)
        for (int i : v)
            result += slow(i); // or fast(i), try both

    return result;
}

J'ai testé le dessus avec clang 5.1 sur Mac OS avec-O3. Il a fallu 2.9 secondes à l'aide d' fast() et 3,8 secondes à l'aide d' slow(). Si j'utilise plutôt un vecteur de tous les zéros, il n'y a pas de différence significative de performance entre les deux fonctions.

Answer 1

Exactement pourquoi devrait - il être en mesure d'optimiser le code? Vous êtes en supposant que toute transformation qui aura beaucoup à faire. Ce n'est pas du tout la façon dont les optimiseurs de travail. Ils ne sont pas des Intelligences Artificielles. Ils travaillent tout simplement par paramétriquement remplacement de modèles connus. E. g. la "Commune de la sous-expression de l'Élimination" scanne une expression commune des sous-expressions, et les déplace vers l'avant, si cela ne change pas d'effets secondaires.

(BTW, le CST montre que les optimiseurs sont déjà tout à fait conscient de ce que le code de mouvement est admis dans la présence éventuelle d'effets secondaires. Ils savent que vous devez être prudent avec &&. Si expr && expr peut être CST-optimisé ou pas ne dépend pas du effets secondaires de l' expr.)

Donc, en résumé: quel modèle avez-vous pense que s'applique ici?

Answer 2

Il est exact que cela semble être une lacune, et, éventuellement, une simple bug, dans l'optimiseur.

Considérer:

bool slow(int x)
{
  return x && (x & 4242);
}

bool slow2(int x)
{
  return (x & 4242) && x;
}

Assemblée émis par GCC 4.8.1 (-O3):

slow:
    xorl    %eax, %eax
    testl   %edi, %edi
    je      .L2
    andl    $4242, %edi
    setne   %al
.L2:
    rep ret

slow2:
    andl    $4242, %edi
    setne   %al
    ret

En d'autres termes, slow2 est mal nommée.

J'ai seulement pu occasionnellement un patch pour GCC, afin de savoir si mon point de vue porte tout le poids est discutable :-). Mais il est certainement étrange, à mon avis, pour GCC pour optimiser un et pas l'autre. Je suggère le dépôt d'un rapport de bogue.

[Mise à jour]

Étonnamment petits changements qui semblent faire une grande différence. Par exemple:

bool slow3(int x)
{
  int y = x & 4242;
  return y && x;
}

...génère "lent" code de nouveau. Je n'ai aucune hypothèse de ce comportement.

Vous pouvez expérimenter avec toutes ces sur plusieurs compilateurs ici.

Answer 3

C'est la façon dont votre code ressemble à BRAS, ce qui devrait faire slow courir plus vite lorsque l'entrée est à 0.

fast(int):
    movw    r3, #4242
    and r3, r0, r3
    adds    r0, r3, #0
    movne   r0, #1
    bx  lr
slow(int):
    cmp r0, #0
    bxeq    lr
    movw    r3, #4242
    and r3, r0, r3
    adds    r0, r3, #0
    movne   r0, #1
    bx  lr

Cependant GCC permettrait d'optimiser très bien quand vous commencez à utiliser un tel trivial fonctions de toute façon.

bool foo() {
    return fast(4242) && slow(42);
}

devient

foo():
    mov r0, #1
    bx  lr

Mon point est parfois le code exige plus de contexte pour être optimisé, donc pourquoi les responsables de l'implémentation des optimiseurs (amendements!) devrait s'en préoccuper?

Un autre exemple:

bool bar(int c) {
  if (fast(c))
    return slow(c);
}

devient

bar(int):
    movw    r3, #4242
    and r3, r0, r3
    cmp r3, #0
    movne   r0, #1
    bxne    lr
    bx  lr

Answer 4

Pour effectuer cette optimisation, on doit étudier l'expression de deux cas distincts: x == 0, en simplifiant à l' false, et x != 0, en simplifiant à l' x & 4242. Et puis être assez intelligent pour voir que la valeur de la seconde expression donne aussi la valeur correcte, même pour x == 0.

Imaginons que le compilateur effectue une étude de cas et trouve des simplifications.

Si x != 0, l'expression se simplifie en x & 4242.

Si x == 0, l'expression se simplifie en false.

Après simplification, on obtient deux complètement sans rapport avec les expressions. Pour les concilier, le compilateur doit demander artificielle questions:

Si x != 0, peut - false être utilisé à la place de x & 4242 de toute façon ? [Non]

Si x == 0, peut - x & 4242 être utilisé à la place de false de toute façon ? [Oui]

Answer 5

Il est légèrement intéressant de noter que cette optimisation n'est pas valable sur toutes les machines. Spécifiquement si vous utilisez une machine qui utilise la représentation des nombres négatifs en complément du complément, alors:

 -0 & 4242 == true
-0 && ( -0 & 4242 ) == false
 

GCC n'a jamais pris en charge de telles représentations, mais elles sont autorisées par la norme C.