¿Es este un error del optimizador de Clang o un comportamiento indefinido en C?

optimization c99

Question

Este código da diferentes resultados para -O1 y -O2:

/*
    Example of a clang optimization bug.
    Mark Adler, August 8, 2015.

    Using -O0 or -O1 takes a little while and gives the correct result:

        47 bits set (4294967296 loops)

    Using -O2 or -O3 optimizes out the loop, returning immediately with:

        0 bits set (4294967296 loops)

    Of course, there weren''t really that many loops.  The number of loops was
    calculated, correctly, by the compiler when optimizing.  But it got the
    number of bits set wrong.

    This is with:

        Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
        Target: x86_64-apple-darwin14.4.0

 */

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = 0;
    uint64_t loops = 0;
    uint32_t x = 0;
    do {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    } while (x);
    printf("%" PRIu64 " bits set (%" PRIu64 " loops)/n", count, loops);
    return 0;
}

Entonces, ¿esto es un error? ¿O hay de alguna manera un comportamiento indefinido allí, que el compilador está dentro de sus derechos para dar diferentes resultados?

Por lo que puedo decir del estándar C99, el bucle do para pasar por todos los valores de uint32_t es válido ya que el incremento del mayor valor entero sin signo está bien definido para dar como resultado cero.

Un cálculo que involucre operandos sin signo nunca puede desbordarse, porque un resultado que no puede ser representado por el tipo entero sin signo resultante se reduce en módulo el número que es uno mayor que el valor más grande que puede ser representado por el tipo resultante.

Answer 1

Es un error en el clang pre-3.6.0 . (La versión "3.6.0svn" es anterior a la versión 3.6.0.) Como ya se ha corregido en la versión 3.6.0 desde hace cinco meses, informé del error a Apple: esta es todavía su distribución más reciente del compilador herramientas.

Answer 2

Estoy razonablemente seguro de que esto es un error en Clang. No veo ningún comportamiento indefinido en el programa (suponiendo que no exceda los límites de capacidad de la implementación), aparte de un pequeño problema en la llamada a printf que printf a continuación (y que ahora se ha abordado en una edición al pregunta). Es posible que me haya perdido algo, pero no lo creo.

Si me he perdido algo, espero que sea señalado en breve. Si esta respuesta no se contradice después de unos días, lo tomaré como un fuerte indicio de que es realmente un error en el sonido.

ACTUALIZACIÓN: Mark Adler, el póster original, informó esto y confirmó que se trata de un error en el clang pre-3.6.0, corregido en versiones posteriores. Robaré descaradamente este enlace al informe de error de su respuesta .

La salida correcta es:

47 bits set (4294967296 loops)

Para abordar algunas de las cosas que se han señalado (o que me he dado cuenta):

static uint64_t vec[1 << 26] = {0};

Este es un objeto grande (2 ²⁹ bytes, o medio gigabyte, asumiendo que CHAR_BIT==8 ), pero aparentemente no excede la capacidad de la implementación. Si lo hiciera, sería rechazado. No estoy 100% seguro de que el estándar lo requiera, pero como el programa funciona correctamente en niveles de optimización más bajos, podemos suponer que el objeto no es demasiado grande.

vec[31415927] = 0xb9fe2f2fedf7ebbd

La constante 0xb9fe2f2fedf7ebbd no es un problema. Su valor está entre 2 ⁶³ y 2 ⁶⁴ , por lo que está dentro del rango de uint64_t . El tipo de constante entero hexadecimal es lo suficientemente amplio como para mantener su valor (a menos que exceda ULLONG_MAX , pero ese no es el caso aquí).

if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))

Pensé brevemente que el cambio a la izquierda podría ser un problema, pero no lo es. El operando izquierdo es de tipo uint64_t , y el operando derecho está en el rango 0 .. 63 . Un desplazamiento a la izquierda de 64 bits tendría un comportamiento indefinido, pero ese no es el caso aquí.

printf("%llu bits set (%llu loops)/n", count, loops);

Lo siguiente ha sido abordado por una actualización de la pregunta. He probado la versión actualizada del código y obtuve los mismos resultados.

%llu requiere un argumento de tipo unsigned long long ; count y loops son de tipo uint64_t . Aquí, dependiendo de la implementación, podríamos tener un comportamiento indefinido (en mi sistema uint64_t es un typedef por unsigned long , y recibo una advertencia). Pero no es probable que cause problemas reales ( unsigned long long y uint64_t típicamente tienen la misma representación, incluso si no son del mismo tipo), y cuando agrego cast para evitar cualquier UB:

printf("%llu bits set (%llu loops)/n",
       (unsigned long long)count,
       (unsigned long long)loops);

Me sale el mismo comportamiento. Los siguientes resultados son para un programa con conversiones agregadas a la llamada a printf .

Al usar gcc 5.2.0 en mi sistema de 64 bits, obtengo la salida correcta con -O0 , -O1 , -O2 y -O3 , con o sin -m32 . El tiempo indica que gcc no elimina el bucle en ningún nivel de optimización.

Al usar Clang 3.4 en el mismo sistema, obtengo la salida correcta con -O0 o -O1 , pero la salida incorrecta ( 0 bits set ) en -O2 o -O2 . El tiempo indica que el bucle se elimina en -O2 y -O2 . Cuando compilo con clang -m32 , la salida es correcta (y el bucle no se elimina) en todos los niveles de optimización.

Cuando cambio la declaración de loops a

volatile uint64_t loops = 0;

Obtengo la salida correcta en todos los niveles de optimización (y el bucle no se elimina).

Otra modificación del programa (que no se muestra aquí) muestra que vec[31415927] realmente está configurado en 0xb9fe2f2fedf7ebbd , incluso cuando la optimización produce un conteo de bits incorrecto.

Answer 3

Se ve como un error en clang. Puedo reproducir esto en mi sistema de 64 bits ejecutando clang3.4-1ubuntu3; como lo menciona la otra respuesta, siempre obtengo una salida correcta con gcc (que nunca optimiza el bucle), pero clang parece optimizar el bucle si usamos -O2 y -O2 .

Esta respuesta no agrega mucho a la respuesta completa y sobresaliente de Keith, pero para futuras referencias quiero mostrar una posible solución (que no sea volatile ).

De hecho, hacer que cualquiera de x , count o loops volatile lo arregle, pero después de algunos experimentos, determiné que el error parece manifestarse solo en do { ... } while; bucles

Si cambia el código para usar un while o un bucle for (y realiza los cambios apropiados para mantener el comportamiento del programa), clang siempre producirá la salida correcta y el bucle no se optimiza (pero aún se ejecuta más rápido con -O3 ) .

Aquí hay un ejemplo:

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = vec[0] & (uint64_t)1;
    uint64_t loops = 1;
    uint32_t x = 1;

    while (x) {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    }

    printf("%" PRIu64 " bits set (%" PRIu64 " loops)/n", count, loops);
    return 0;
}