Si tratta di un bug di clang optimizer o di un comportamento non definito in C?

Question

Questo codice dà risultati diversi per -O1 e -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; 
} 

Quindi questo è un bug? O c'è in qualche modo un comportamento indefinito lì dentro, che il compilatore ha i suoi diritti per dare risultati diversi?

Per quanto posso dire dallo standard C99, il ciclo do per passare attraverso tutti i valori uint32_t è valido poiché l'incremento del valore intero senza segno più grande è ben definito per risultare zero.

Un calcolo coinvolge operandi unsigned può mai troppopieno, perché un risultato che non può essere rappresentato dal numero intero senza segno tipo risultante viene ridotta modulo il numero che è maggiore di uno rispetto al massimo valore che può essere rappresentato dal tipo risultante.

Answer 1

Sono ragionevolmente sicuro che si tratti di un bug in clang. Non vedo alcun comportamento non definito nel programma (supponendo che non superi i limiti di capacità dell'implementazione) - diverso da un piccolo problema nella chiamata printf che affronterò di seguito (e che ora è stato indirizzato in una modifica al domanda). È possibile che mi sia sfuggito qualcosa, ma non credo.

Se mi sono perso qualcosa, mi aspetto che venga segnalato a breve. Se questa risposta rimane incontaminata dopo alcuni giorni, la prenderò come una forte indicazione che è davvero un bug in clang.

UPDATE: Mark Adler, il poster originale, ha riferito questo e ha confermato che si tratta di un bug in preambolo 3.6.0, corretto nelle versioni successive. Ruberò spudoratamente this link to the bug report da his answer.

L'output corretto è:

47 bits set (4294967296 loops) 

per affrontare alcune delle cose che sono state sottolineato (o che io stesso ho notato):

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

Si tratta di un oggetto di grandi dimensioni (2 byte o mezzo gigabyte, supponendo CHAR_BIT==8), ma apparentemente non supera la capacità dell'implementazione. Se lo facesse, verrebbe respinto. Non sono sicuro al 100% che lo standard lo richieda, ma poiché il programma funziona correttamente a livelli di ottimizzazione inferiori, possiamo supporre che l'oggetto non sia troppo grande.

vec[31415927] = 0xb9fe2f2fedf7ebbd 

La costante 0xb9fe2f2fedf7ebbd non è un problema. Il suo valore è compreso tra 2 e 2 , quindi è compreso nell'intervallo uint64_t. Il tipo di costante di un intero esadecimale è sufficientemente ampio da contenere il suo valore (a meno che non superi ULLONG_MAX, ma non è questo il caso).

Ho pensato brevemente che lo spostamento a sinistra potrebbe essere un problema, ma non lo è. L'operando sinistro è di tipo uint64_t e l'operando destro è compreso nell'intervallo 0 .. 63. Uno spostamento a sinistra di 64 bit avrebbe un comportamento indefinito, ma non è questo il caso.

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

Quanto segue è stato risolto da un aggiornamento alla domanda. Ho provato la versione aggiornata del codice e ho ottenuto gli stessi risultati.

%llu richiede un argomento di tipo unsigned long long; count e loops sono di tipo uint64_t. Qui, a seconda dell'implementazione, potremmo avere un comportamento non definito (sul mio sistema uint64_t è un typedef per unsigned long e ricevo un avviso). Ma non è probabile che a causare problemi reali ( unsigned long long e uint64_t genere hanno la stessa rappresentazione, anche se non sono dello stesso tipo), e quando aggiungo calchi di evitare qualsiasi UB:

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

ottengo lo stesso comportamento. I seguenti risultati sono per un programma con i cast aggiunti alla chiamata printf.

Utilizzando 5.2.0 gcc sul mio sistema a 64 bit, ottengo l'output corretto con -O0, -O1, -O2, e -O3, con o senza -m32. I tempi indicano che gcc non elimina il ciclo a nessun livello di ottimizzazione.

Uso clangore 3.4 sullo stesso sistema, ottengo l'output corretto con -O0 o -O1, ma non corretto in uscita (0 bits set) a -O2 o -O3. Il tempismo indica che il ciclo viene eliminato a -O2 e -O3. Quando compilo con clang -m32, l'output è corretto (e il ciclo non viene eliminato) a tutti i livelli di ottimizzazione.

Quando cambio la dichiarazione di loops per

volatile uint64_t loops = 0; 

ottengo uscita corretta a tutti i livelli di ottimizzazione (e il ciclo non viene eliminato).

Un'ulteriore modifica al programma (non mostrata qui) mostra che vec[31415927] è impostato su 0xb9fe2f2fedf7ebbd, anche quando l'ottimizzazione produce il conteggio dei bit errato.

Answer 2

Sembra un bug in clang. Posso riprodurlo nel mio sistema a 64-bit eseguendo clang3.4-1ubuntu3; come menziona l'altra risposta, ottengo sempre l'output corretto con gcc (che non ottimizza mai il loop), ma clang sembra ottimizzare il ciclo se usiamo -O2 e -O3.

Questa risposta non aggiunge molto alla risposta completa ed eccezionale di Keith, ma per riferimento futuro desidero mostrare una possibile soluzione alternativa (diversa da volatile).

Infatti, facendo una di x, count o loops volatili sarà risolvere il problema, ma dopo alcuni esperimenti, ho deciso che il bug sembra manifestarsi solo su do { ... } while; loop.

Se si modifica il codice per utilizzare un ciclo while o for (e apportare le modifiche appropriate per mantenere il comportamento del programma), clang produrrà sempre l'output corretto e il ciclo non viene ottimizzato (ma funziona ancora più velocemente con -O3).

Ecco un esempio:

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

Answer 3

È un bug in pre-3.6.0 clang. (La versione "3.6.0svn" precede 3.6.0.) Poiché è già stato risolto nella versione 3.6.0 di cinque mesi fa, ho segnalato il bug ad Apple - questa è ancora la loro distribuzione più recente del compilatore utensili.