Pourquoi le compilateur C++ ne parvient-il pas à optimiser "if (test) - foo" à "foo - = test"?

Question

J'ai une fonction qui trouve la prochaine puissance de deux pour un entier donné. Si l'entier est une puissance de deux, il renvoie le pouvoir.

assez simple:

char nextpow2if(int a) 
{ 
    char foo = char(32 - __builtin_clz(a)); 
    bool ispow2 = !(a & a-1); 
    if (ispow2) --foo; 
    return foo; 
} 

Cependant, après la compilation avec gcc 6 avec -O2, après avoir inspecté l'ensemble généré, je vois que cela est compilé avec l'instruction apparemment inutile cmovne après avoir calculé le foo-1. Pire encore avec gcc5 et plus je reçois une branche réelle jne dans le code.

La façon plus rapide de compiler ce serait comme si je l'avais écrit la fonction suivante:

char nextpow2sub(int a) 
{ 
    char foo = char(32 - __builtin_clz(a)); 
    bool ispow2 = !(a & a-1); 
    return foo - ispow2; 
} 

Ce code est compilé correctement par tous les compilateurs les plus brefs (et plus rapide) l'assemblage possible avec un sete et la soustraction pour le bool.

Pourquoi le compilateur ne parvient-il pas à optimiser le premier? Cela semble être un cas très facile à identifier. Pourquoi gcc 5 et plus compilent ceci à une branche réelle jne? Y a-t-il un cas limite entre les deux versions, que je ne peux pas voir, qui pourrait les amener à se comporter différemment?

PS: Démo en direct here

Edit: Je n'ai pas testé les performances avec gcc 6 mais avec gcc 5 celui-ci est environ deux fois plus rapide (bien sur un test de PerformanSe synthétique, au moins). C'est ce qui m'a amené à poser cette question.

Answer 1

Je crois que la raison de ceci pourrait être que bool est typiquement stocké dans un octet. Par conséquent, le compilateur peut ne pas être en mesure de supposer que la mémoire réelle est exactement égale à 1. La vérification true/false se compare probablement à zéro. La soustraction, cependant, pourrait être une histoire différente avec des effets secondaires.

Voir example code on Ideone:

#include <iostream> 
using namespace std; 

union charBool 
{ 
    unsigned char aChar; 
    bool aBool; 
}; 

int main() 
{ 
    charBool var; 
    charBool* varMemory = &var; 

    var.aBool = 65; 
    std::cout << "a boolean = " << var.aBool << std::endl; 
    std::cout << "a char = " << var.aChar << std::endl; 
    std::cout << "varMemory = " << (*(reinterpret_cast<unsigned char*>(varMemory))) << std::endl; 

    var.aChar = 98; // note: Ideone C++ compiler resolves this to zero, hence bit0 seems to be the only checked 
    std::cout << "a boolean = " << var.aBool << std::endl; 
    std::cout << "a char = " << var.aChar << std::endl; 
    std::cout << "varMemory = " << (*(reinterpret_cast<unsigned char*>(varMemory))) << std::endl; 

    return 0; 
} 

qui se traduit par:

a boolean = 1 
a char = 
varMemory = 
a boolean = 0 
a char = b 
varMemory = b 

(ndlr: deux premiers caractères sont unprintable)

Answer 2

Eh bien, le compilateur pourrait en effet effectuer cette optimisation dans ce spécifique cas sans violer la norme. Mais considérez ce qui suit le cas un peu différent:

char nextpow2sub(int a) 
{ 
    char foo = char(32 - __builtin_clz(a)); 
    bool ispow2 = !(a & a-1); 
    return foo - (5 * ispow2); 
} 

char nextpow2if(int a) 
{ 
    char foo = char(32 - __builtin_clz(a)); 
    bool ispow2 = !(a & a-1); 
    if (ispow2) foo = foo - 5; 
    return foo; 
} 

Le seul changement que je fait ici est que je suis soustrait par 5 plutôt que 1. Si vous compilez à l'aide 6.x gcc et comparez, vous verrez que les Le code binaire généré est de la même taille pour les deux fonctions. Je m'attends aussi à ce qu'ils aient tous deux plus ou moins la même performance. Cela montre que l'algorithme d'optimisation utilisé par le compilateur a été conçu pour gérer le cas général. Cela dit, même pour le cas de la soustraction de 1, j'attends (en utilisant gcc 6.x) qu'il y aura une petite différence de performance sur tout processeur moderne qui supporte le parallélisme au niveau de l'instruction et le changement de registre.

Ce code est compilé correctement par tous les compilateurs à la plus courte (et le plus rapide) l'assemblage possible avec un sete et la soustraction pour la bool.

Comment avez-vous su que c'est le code le plus court et le plus rapide possible? Oui, c'est plus court et plus rapide mais avez-vous la preuve que c'est le plus court et le plus rapide? Aussi, vous ne pouvez pas donner une telle déclaration sans spécifier une architecture particulière et une microarchitecture.