Puis-je suggérer l'optimiseur en donnant la plage d'un entier?

Question

Je suis en utilisant un int type pour stocker une valeur. Par la sémantique du programme, la valeur varie toujours dans une très petite plage (0 - 36), et int (pas un char) est utilisé seulement en raison de l'efficacité de l'UC.

Il semble que de nombreux spéciale arithmétique des optimisations peuvent être effectuées sur une petite plage d'entiers. De nombreux appels de fonction sur les entiers pourraient être optimisés dans un petit jeu de "magique" des opérations, et certaines fonctions peuvent même être optimisé dans la table look-up.

Donc, est-il possible de dire au compilateur que c' int est toujours dans ce petit intervalle, et est-il possible pour le compilateur de faire ces optimisations?

Answer 1

Oui, c'est possible. Par exemple, pour gcc vous pouvez utiliser __builtin_unreachable de dire au compilateur conditions impossibles, comme suit:

if (value < 0 || value > 36) __builtin_unreachable();

Nous pouvons conclure que la condition ci-dessus dans une macro:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

Et de l'utiliser comme ceci:

assume(x >= 0 && x <= 10);

Comme vous pouvez le voir, gcc effectue des optimisations basées sur cette information:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Produit:

func(int):
    mov     eax, 17
    ret

Un inconvénient, cependant, que si votre code jamais de pauses, ces hypothèses, vous obtenez un comportement indéfini.

Il n'est pas de vous avertir lorsque cela se produit, même dans les versions de débogage. Debug/test/repérer les bugs, avec des hypothèses plus facilement, vous pouvez utiliser un hybride suppose/macro assert (crédits de @David Z), comme ceci:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

Dans les versions debug (avec NDEBUG non défini), il fonctionne comme un vulgaire assert, message d'erreur d'impression et d' abort'ing programme, et dans les versions release il fait usage d'une hypothèse, la production de code optimisé.

Notez, cependant, que ce n'est pas un substitut pour les réguliers, assert - cond reste dans les versions release, donc vous ne devriez pas faire quelque chose comme assume(VeryExpensiveComputation()).

Answer 2

Il existe un support standard pour cela. Ce que vous devez faire est d’inclure stdint.h ( cstdint ) puis d’utiliser le type uint_fast8_t .

Cela indique au compilateur que vous utilisez uniquement des nombres compris entre 0 et 255, mais que vous pouvez utiliser un type plus grand si le code est plus rapide. De même, le compilateur peut supposer que la variable n'aura jamais une valeur supérieure à 255 et ensuite procéder aux optimisations en conséquence.

Answer 3

La réponse actuelle est bon pour le cas lorsque l'on sait pour sûr que la plage est bien, mais si vous voulez encore le comportement correct lorsque la valeur est hors de la plage, alors il ne fonctionnera pas.

Pour ce cas, j'ai trouvé cette technique peut fonctionner:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

L'idée est un code-données de compromis: vous êtes en mouvement 1 bits de données ( x == c) dans la logique de contrôle.
Cela nous amène à l'optimiseur qu' x est en fait connu une constante c, en l'encourageant à en ligne et optimiser la première invocation de l' foo séparément du reste, peut-être même très fortement.

Assurez-vous de réellement le facteur le code dans un seul sous-routine foo,- ne pas dupliquer le code.

Exemple:

Pour que cette technique fonctionne, vous devez être un peu de chance -- il y a des cas où le compilateur décide de ne pas évaluer les choses, de manière statique, et ils sont un peu arbitraires. Mais quand ça marche, ça fonctionne bien:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

Suffit d'utiliser -O3 et d'avis de la pré-évalués constantes 0x20 et 0x30e dans l'assembleur de sortie.

Answer 4

Je suis juste de tangage pour dire que si vous voudrez peut-être une solution qui est plus standard C++, vous pouvez utiliser l' [[noreturn]] attribut d'écrire votre propre unreachable.

Donc je vais re-but deniss' excellent exemple pour le démontrer:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Qui comme vous pouvez le voir, les résultats de près identiques code:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

L'inconvénient est bien sûr que vous obtenez un message d'avertissement qu'un [[noreturn]] fonction n'est, en effet, de retour.