Quando il comportamento non definito in C supera la barriera di causalità

8

Alcuni compilatori C ultramoderni dedurranno che se un programma invoca il comportamento non definito quando vengono dati determinati input, tali input non verranno mai ricevuti. Di conseguenza, qualsiasi codice che sarebbe irrilevante a meno che tali input siano ricevuti può essere eliminato.

Come esempio semplice, dato:

void foo(uint32_t);

uint32_t rotateleft(uint_t value, uint32_t amount)
{
  return (value << amount) | (value >> (32-amount));
}

uint32_t blah(uint32_t x, uint32_t y)
{
  if (y != 0) foo(y);
  return rotateleft(x,y);
}

un compilatore può dedurre che poiché la valutazione di value >> (32-amount) darà un comportamento non definito quando amount è zero, la funzione blah non sarà mai chiamata con y uguale a zero; la chiamata a foo può quindi essere resa incondizionata.

Da quello che posso dire, questa filosofia sembra essersi impadronita intorno al 2010. La prima prova che ho visto delle sue radici risale al 2009, ed è stata sancita nello standard C11 che afferma esplicitamente che se il comportamento non definito si verifica in qualsiasi punto dell'esecuzione di un programma, il comportamento dell'intero programma diventa retroattivamente indefinito.

L'idea che i compilatori dovessero tentare di utilizzare il comportamento non definito per giustificare le ottimizzazioni causali inverse (ovvero il comportamento non definito nella funzione rotateleft dovrebbe far assumere al compilatore che blah deve essere stato chiamato con un valore diverso da zero y , indipendentemente dal fatto che qualcosa potrebbe mai causare y per mantenere un valore diverso da zero) seriamente difeso prima del 2009? Quando mai una cosa del genere è stata proposta seriamente come tecnica di ottimizzazione?

[Addendum]

Alcuni compilatori hanno incluso, anche nel ventesimo secolo, opzioni per abilitare determinati tipi di inferenze sui loop e sui valori calcolati al loro interno. Ad esempio, dato

int i; int total=0;
for (i=n; i>=0; i--)
{
  doSomething();
  total += i*1000;
}

un compilatore, anche senza le inferenze facoltative, potrebbe riscriverlo come:

int i; int total=0; int x1000;
for (i=n, x1000=n*1000; i>0; i--, x1000-=1000)
{
  doSomething();
  total += x1000;
}

poiché il comportamento di quel codice corrisponderebbe esattamente all'originale, anche se il compilatore specificava che i valori di int si sovrappongono sempre in mod-65536 moda a complemento a due . L'opzione di inferenza aggiuntiva consentirebbe al compilatore di riconoscere che dal momento che i e x1000 devono attraversare lo zero allo stesso tempo, la variabile precedente può essere eliminata:

int total=0; int x1000;
for (x1000=n*1000; x1000 > 0; x1000-=1000)
{
  doSomething();
  total += x1000;
}

In un sistema in cui int ha eseguito il wrapping del mod 65536, un tentativo di eseguire uno dei primi due loop con n uguale a 33 risulterebbe in doSomething() invocato 33 volte. L'ultimo ciclo, al contrario, non invocerebbe affatto doSomething() , anche se la prima chiamata di doSomething() avrebbe preceduto qualsiasi overflow aritmetico. Un simile comportamento potrebbe essere considerato "non causale", ma gli effetti sono ragionevolmente ben vincolati e ci sono molti casi in cui il comportamento sarebbe inequivocabilmente innocuo (nei casi in cui è richiesta una funzione per produrre un certo valore quando viene data qualsiasi input, ma il valore può essere arbitrario se l'input non è valido, avendo la fine del ciclo più veloce quando viene dato un valore non valido di n sarebbe effettivamente vantaggioso). Inoltre, la documentazione del compilatore tendeva a scusarsi per il fatto che avrebbe cambiato il comportamento di qualsiasi programma, anche quelli che erano impegnati in UB.

Sono interessato a quando gli atteggiamenti degli scrittori di compilatori si sono allontanati dall'idea che le piattaforme dovrebbero quando sono pratici documentare alcuni limiti comportamentali utilizzabili anche nei casi non imposti dallo Standard, all'idea che qualsiasi costrutto che si baserebbe su qualsiasi comportamento non mandato dallo Standard dovrebbe essere marchiato illegittimo anche se sulla maggior parte dei compilatori esistenti funzionerebbe bene o meglio di qualsiasi codice rigorosamente conforme che soddisfi gli stessi requisiti (spesso consentendo ottimizzazioni che non sarebbero possibili in un codice rigorosamente conforme).

    
posta supercat 01.08.2015 - 21:25
fonte

4 risposte

4

Il comportamento non definito viene utilizzato in situazioni in cui non è fattibile per le specifiche per specificare il comportamento, ed è sempre stato scritto per consentire assolutamente qualsiasi comportamento possibile.

Le regole estremamente loose per UB sono utili quando si pensa a cosa deve fare un compilatore conforme alle specifiche. Potresti avere una potenza di compilazione sufficiente per emettere un errore quando fai un brutto UB in un caso, ma aggiungi alcuni livelli di ricorsione e ora il meglio che puoi fare è un avvertimento. Le specifiche non hanno alcun concetto di "avvertenze", quindi se le specifiche hanno dato un comportamento, dovrebbe essere "un errore".

Il motivo per cui vediamo sempre più effetti collaterali di questo è la spinta per l'ottimizzazione. Scrivere un ottimizzatore conforme alle specifiche è difficile. Scrivere un ottimizzatore conforme alle specifiche che capita anche di fare un ottimo lavoro indovinando che cosa intendevi quando sei uscito dalle specifiche è brutale. È molto più semplice con i compilatori se assumono UB significa UB.

Questo è particolarmente vero per gcc, che tenta di supportare molti set di istruzioni con lo stesso compilatore. È molto più facile lasciare che UB produca comportamenti UB piuttosto che provare a cimentarsi con tutti i modi in cui ogni singolo codice UB potrebbe andare storto su ogni piattaforma e inserirlo nelle prime frasi dell'ottimizzatore.

    
risposta data 02.08.2015 - 08:57
fonte
4

"Un comportamento indefinito potrebbe far sì che il compilatore riscriva il codice" è accaduto da molto tempo, in loop optimisations.

Fai un giro (a e b sono puntatori per raddoppiare, per esempio)

for (i = 0; i < n; ++i) a [i] = b [i];

Aumentiamo un int, copiamo un elemento dell'array, lo confrontiamo con un limite. Un compilatore di ottimizzazione rimuove innanzitutto l'indicizzazione:

double* tmp1 = a;
double* tmp2 = b;
for (i = 0; i < n; ++i) *tmp1++ = *tmp2++;

Rimuoviamo il caso n < = 0:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    for (; i < n; ++i) *tmp1++ = *tmp2++;
}

Ora eliminiamo la variabile i:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    double* limit = tmp1 + n;
    for (; tmp1 != limit; tmp1++, tmp2++) *tmp1 = *tmp2;
    i = n;
}

Ora se n = 2 ^ 29 su un sistema a 32 bit o 2 ^ 61 su un sistema a 64 bit, su implementazioni tipiche avremo il limite tmp1 == e non verrà eseguito alcun codice. Ora sostituisci il compito con qualcosa che richiede molto tempo, in modo che il codice originale non possa mai finire nell'inevitabile crash, perché impiega troppo tempo e il compilatore ha cambiato il codice.

    
risposta data 02.08.2015 - 22:06
fonte
3

È sempre stato il caso in C e C ++ che a causa di un comportamento indefinito, può succedere qualsiasi cosa . Pertanto è sempre stato anche il caso che un compilatore possa fare l'ipotesi che il tuo codice non invochi un comportamento indefinito: o non c'è un comportamento indefinito nel tuo codice, quindi l'ipotesi era corretta. Oppure c'è un comportamento indefinito nel tuo codice, quindi qualsiasi cosa accada a causa dell'errata ipotesi è coperta da " qualsiasi cosa può accadere".

Se si osserva la funzione "restrict" in C, l'intero punto della feature è che il compilatore può supporre che non ci sia un comportamento indefinito, così abbiamo raggiunto il punto in cui il compilatore non solo potrebbe ma in realtà dovrebbe presumere che non ci sia un comportamento indefinito.

Nell'esempio che si assegna, le istruzioni assembler generalmente utilizzate su computer x86 per implementare lo spostamento a sinistra oa destra si sposteranno di 0 bit se il numero di shift è 32 per il codice a 32 bit o 64 per il codice a 64 bit. Questo nella maggior parte dei casi pratici porterà a risultati indesiderati (e risultati che non sono gli stessi di ARM o PowerPC, per esempio), quindi il compilatore è del tutto giustificato nell'assumere che questo tipo di comportamento indefinito non avvenga. Puoi cambiare il tuo codice in

uint32_t rotateleft(uint_t value, uint32_t amount)
{
   return amount == 0 ? value : (value << amount) | (value >> (32-amount));
}

e suggerire agli sviluppatori gcc o Clang che sulla maggior parte dei processori il codice "amount == 0" dovrebbe essere rimosso dal compilatore, perché il codice assemblatore generato per il codice turno produrrà lo stesso risultato come valore quando importo == 0.

    
risposta data 02.08.2015 - 11:24
fonte
-1

Questo perché c'è un bug nel tuo codice:

uint32_t blah(uint32_t x, uint32_t y)
{
    if (y != 0) 
    {
        foo(y);
        return x; ////// missing return here //////
    }
    return rotateleft(x, y);
}

In altre parole, salta la barriera di causalità solo se il compilatore vede che, dati determinati input, stai invocando un comportamento indefinito oltre ogni dubbio .

Tornando subito prima dell'invocazione di un comportamento non definito, dici al compilatore che stai evitando consapevolmente quel comportamento non definito dall'esecuzione e il compilatore lo riconosce.

In altre parole, quando si dispone di un compilatore che tenta di applicare le specifiche in modo molto rigoroso, è necessario implementare ogni possibile convalida degli argomenti nel codice. Inoltre, questa convalida deve avvenire prima dell'invocazione di detto comportamento non definito.

Aspetta! E c'è di più!

Ora, con i compilatori che eseguono queste cose super-pazzesche ma super-logiche, è imperativo di dire al compilatore che una funzione non dovrebbe continuare l'esecuzione. Pertanto, la parola chiave noreturn sulla funzione foo() ora diventa obbligatoria .

    
risposta data 02.08.2015 - 01:32
fonte

Leggi altre domande sui tag