c++ - ¿Cuán indefinidos están__builtin_ctz(0) o__builtin_clz(0)?

undefined-behavior constexpr

Question

Fondo

Durante mucho tiempo, gcc ha proporcionado una serie de funciones integradas de twiddling de bits, en particular el número de 0 bits finales y finales (también para long unsigned y long long unsigned , que tienen los sufijos l ll ):

- Función incorporada: int __builtin_clz (unsigned int x)

Devuelve el número de 0 bits iniciales en x , comenzando en la posición de bit más significativa. Si x es 0, el resultado no está definido.

- Función incorporada: int __builtin_ctz (unsigned int x)

Devuelve el número de 0 bits finales en x , comenzando en la posición de bit menos significativa. Si x es 0, el resultado no está definido.

En cada compilador en línea (descargo de responsabilidad: solo x64) que probé, sin embargo, el resultado ha sido que tanto clz(0) como ctz(0) devuelven el número de bits del tipo incorporado subyacente, por ejemplo

#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);    
}

Ejemplo vivo .

Intento de solución

El último troncal Clang SVN en modo std=c++1y ha hecho que todas estas funciones se relajen en C ++ 14 constexpr , lo que las convierte en candidatas para usar en una expresión SFINAE para una plantilla de función de envoltura alrededor de los 3 ctz / clz incorporados para unsigned , unsigned long y 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; }

El beneficio de este truco es que las plataformas que dan el resultado requerido para ctz(0) pueden omitir un condicional adicional para probar x==0 (lo que puede parecer una microoptimización, pero cuando ya está al nivel de builtin funciones de cambio de bits, puede hacer una gran diferencia)

Preguntas

¿Cuán indefinida está la familia de funciones incorporadas clz(0) y ctz(0) ?

• ¿Pueden lanzar una excepción std::invalid_argument ?
• para x64, ¿devolverán el tamaño del tipo de underyling para la distribución gcc actual?
• ¿Las plataformas ARM / x86 son diferentes (no tengo acceso a eso para probarlas)?
• ¿Es el truco anterior de SFINAE una forma bien definida de separar tales plataformas?

Answer 1

Desafortunadamente, incluso las implementaciones x86-64 pueden diferir, de la referencia del conjunto de instrucciones de Intel, BSF y BSR , con un valor de operando de origen de (0) , deja el destino sin definir y establece el ZF (indicador cero). Por lo tanto, es posible que el comportamiento no sea consistente entre las microarquitecturas o, digamos, AMD e Intel. (Creo que AMD no modifica el destino).

Las nuevas instrucciones de LZCNT y TZCNT no son ubicuas. Ambos están presentes solo a partir de la arquitectura Haswell (para Intel).

Answer 2

La razón por la que el valor no está definido es que le permite al compilador utilizar instrucciones del procesador para las cuales el resultado no está definido, cuando esas instrucciones son la forma más rápida de obtener una respuesta.

Pero es importante entender que no solo los resultados no están definidos; Son indeterministas. Es válido, dada la referencia de instrucciones de Intel, para que la instrucción devuelva los 7 bits bajos de la hora actual, por ejemplo.

Y aquí es donde se vuelve interesante / peligroso: el escritor del compilador puede aprovechar esta situación para producir un código más pequeño. Considera esta versión de tu código sin especialización en plantillas:

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;
}

Esto funciona bien en un procesador / compilador que ha decidido devolver #bits para ctznz (0). Pero un procesador / compilador que decide devolver valores pseudoaleatorios, el compilador puede decidir "Se me permite devolver lo que quiera para ctznz (0), y el código es más pequeño si devuelvo #bits, así que lo haré" . Entonces el código termina llamando a ctznz todo el tiempo, aunque produce la respuesta incorrecta.

Para decirlo de otra manera: no se garantiza que los resultados indefinidos del compilador queden indefinidos de la misma manera que lo son los resultados indefinidos del programa en ejecución.

Realmente no hay forma de evitar esto. Si debe usar __builtin_clz, con un operando de origen que podría ser cero, debe agregar el cheque, todo el tiempo.