Dans quelle mesure est-ce que builtin ctz(0) ou builtin clz(0) ne sont pas définis?
arrière-plan
pendant longtemps, gcc a fourni un certain nombre de fonctions de bit-twidling intégrées, en particulier le nombre de 0-bits traînant et menant (également pour long unsigned et long long unsigned , qui ont des suffixes l et ll ):
- fonction intégrée:
int __builtin_clz (unsigned int x)renvoie le nombre de bits de tête en
x, à partir du bit le plus significatif position. Sixest 0, le résultat n'est pas défini.- fonction intégrée:
int __builtin_ctz (unsigned int x)renvoie le nombre de 0 bits de retard dans
x, en commençant par le bit le moins significatif position. Sixest 0, le résultat n'est pas défini.
sur chaque compilateur en ligne (disclaimer: only x64) que j'ai testé, cependant, le résultat a été que les deux clz(0) et ctz(0) renvoient le nombre de bits du type de construction sous-jacent, p.ex.
#include <iostream>
#include <limits>
int main()
{
// prints 32 32 32 on most systems
std::cout << std::numeric_limits<unsigned>::digits << " " << __builtin_ctz(0) << " " << __builtin_clz(0);
}
tentative de contournement
le dernier clang SVN trunk dans le mode std=c++1y a rendu toutes ces fonctions détendues C++14 constexpr , ce qui les rend candidats à utiliser dans une expression SFINAE pour un modèle de fonction d'enveloppe autour les bâtiments de 3 ctz / clz pour unsigned , unsigned long , et unsigned long long
template<class T> // wrapper class specialized for u, ul, ull (not shown)
constexpr int ctznz(T x) { return wrapper_class_around_builtin_ctz<T>()(x); }
// overload for platforms where ctznz returns size of underlying type
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) == std::numeric_limits<T>::digits, int>::type
{ return ctznz(x); }
// overload for platforms where ctznz does something else
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) != std::numeric_limits<T>::digits, int>::type
{ return x ? ctznz(x) : std::numeric_limits<T>::digits; }
le gain de ce hack est que les plates-formes qui donnent le résultat requis pour ctz(0) peuvent omettre une condition supplémentaire pour tester pour x==0 (qui pourrait sembler une micro-optimisation, mais quand vous êtes déjà au niveau du niveau de bit-twiddling fonctions intégrées, il peut faire une grande différence)
Questions
dans quelle mesure la famille de fonctions clz(0) et ctz(0) n'est-elle pas définie ?
- peuvent-ils lancer une exception
std::invalid_argument? - pour x64, est-ce que pour la distribution gcc actuelle retourneront la taille du type sous-jacent?
- les plateformes ARM/x86 sont-elles différentes (Je n'y ai pas accès pour les tester)?
- est l'astuce SFINAE ci-dessus une manière bien définie de séparer tel les plates-formes?
2 réponses
malheureusement, même les implémentations de x86-64 peuvent différer - de " instruction set reference , BSF et BSR D'Intel , avec une valeur d'opérande source de (0) , laisse la destination non définie , et définit le ZF (drapeau zéro). Ainsi, le comportement peut ne pas être cohérent entre les micro-architectures ou, disons, AMD et Intel. (Je crois QU'AMD laisse la destination non modifiée.)
le plus récent Les instructions LZCNT et TZCNT ne sont pas omniprésentes. Les deux ne sont présents qu'à partir de L'architecture Haswell (pour Intel).
la raison pour laquelle la valeur n'est pas définie est qu'elle permet au compilateur d'utiliser des instructions de processeur pour lesquelles le résultat n'est pas défini, lorsque ces instructions sont le moyen le plus rapide d'obtenir une réponse.
mais il est important de comprendre que non seulement les résultats ne sont pas définis, mais ils sont indéterministes. Il est valide, compte tenu de la référence d'instruction D'Intel, pour l'instruction de retourner les 7 bits bas de l'heure actuelle, par exemple.
et c'est là que ça devient intéressant/dangereux: l'auteur du compilateur peut profiter de cette situation, pour produire du code plus petit. Considérez cette version non-modèle-spécialisation de votre code:
using std::numeric_limits;
template<class T>
constexpr auto ctz(T x) {
return ctznz(0) == numeric_limits<T>::digits || x != 0
? ctznz(x) : numeric_limits<T>::digits;
}
cela fonctionne bien sur un processeur/compilateur qui a décidé de retourner #bits pour ctznz(0). Mais si un processeur / compilateur décide de retourner des valeurs pseudo-aléatoires, le compilateur peut décider "je suis autorisé à retourner ce que je veux pour ctznz (0), et le code est plus petit si Je retourne #bits, donc je vais". Puis le code finit par appeler ctsnz tout le temps, même s'il produit la mauvaise réponse.
pour le dire autrement: les résultats non définis du compilateur ne sont pas garantis comme le sont les résultats non définis du programme en cours d'exécution.
Il n'y a vraiment aucun moyen de contourner cela. Si vous devez utiliser __builtin_clozapine, avec un opérande source qui pourrait être de zéro, vous devez ajouter la vérification, tout le temps.