Perché la divisione intera di -1 (quella negativa) risulta in FPE?

Ho l’incarico di espiare alcuni comportamenti apparentemente strani del codice C (in esecuzione su x86). Posso completare facilmente tutto il resto ma questo mi ha davvero confuso.

-2147483648 codice 1 output -2147483648

 int a = 0x80000000; int b = a / -1; printf("%d\n", b); 

Lo snippet di codice 2 non restituisce nulla e restituisce Floating point exception a Floating point exception

 int a = 0x80000000; int b = -1; int c = a / b; printf("%d\n", c); 

Conosco bene il motivo del risultato di Code Snippet 1 ( 1 + ~INT_MIN == INT_MIN ), ma non riesco a capire come possa la divisione intera di -1 generare FPE, né posso riprodurlo sul mio telefono Android (AArch64 , GCC 7.2.0). Il codice 2 viene prodotto come il codice 1 senza eccezioni. È una caratteristica di bug nascosta del processore x86?

Il compito non ha detto nient’altro (inclusa l’architettura della CPU), ma poiché l’intero corso è basato su una distro Linux desktop, si può tranquillamente pensare che sia un x86 moderno.


Edit : ho contattato il mio amico e ha testato il codice su Ubuntu 16.04 (Intel Kaby Lake, GCC 6.3.0). Il risultato è stato coerente con qualunque sia stato l’incarico dichiarato (il codice 1 emette la suddetta cosa e il codice 2 si blocca con FPE).

Ci sono quattro cose che succedono qui:

  • gcc -O0 comportamento di gcc -O0 spiega la differenza tra le tue due versioni. (Mentre clang -O0 capita di compilarli entrambi con idiv ). E perché lo ottieni anche con operandi costanti in fase di compilazione.
  • x86 idiv comportamento idiv rispetto al comportamento dell’istruzione di divisione su ARM
  • Se la matematica intera genera un segnale in uscita, POSIX richiede che sia SIGFPE: Su quali piattaforms il dividendo intero per zero triggers un’eccezione a virgola mobile? Ma POSIX non richiede il trapping per nessuna particolare operazione di intero. (Questo è il motivo per cui è consentito che x86 e ARM siano diversi).

    La specifica Single Unix definisce SIGFPE come “Operazione aritmetica errata”. È chiamato in modo confuso dopo il punto mobile, ma in un normale sistema con FPU nel suo stato predefinito, solo la matematica intera lo solleverà. Su x86, solo divisione intera. Su MIPS, un compilatore potrebbe utilizzare add anziché addu per la matematica con addu , in modo da ottenere trap su overflow di aggiunta firmato. ( gcc usa addu anche per firmati , ma un rivelatore di comportamento non definito potrebbe usare add .)

  • C Regole di comportamento non definite (overflow con segno e divisione specifica) che consentono a gcc di emettere un codice che può intercettare in quel caso.

gcc senza opzioni è uguale a gcc -O0 .

-O0 Riduci i tempi di compilazione e fai il debug producendo i risultati attesi . Questo è l’impostazione predefinita.

Questo spiega la differenza tra le tue due versioni:

gcc -O0 non gcc -O0 non tenta di ottimizzare, ma de-ottimizza triggersmente per rendere ASM che implementa indipendentemente ogni istruzione C all’interno di una funzione. Ciò consente al comando di jump gdb di funzionare in modo sicuro, permettendoti di saltare a una linea diversa all’interno della funzione e di comportarti come se fossi davvero a saltare nella sorgente C.

Inoltre non può assumere nulla sui valori delle variabili tra le istruzioni, perché è ansible modificare le variabili con set b = 4 . Ovviamente questo è catastroficamente negativo per le prestazioni, motivo per -O0 codice -O0 viene eseguito più volte rispetto al codice normale, e perché l’ ottimizzazione di -O0 specifico è una totale assurdità . Rende anche l’output di -O0 asm davvero rumoroso e difficile da leggere per un umano , a causa di tutto lo stoccaggio / ricarico e la mancanza anche delle ottimizzazioni più ovvie.

 int a = 0x80000000; int b = -1; // debugger can stop here on a breakpoint and modify b. int c = a / b; // a and b have to be treated as runtime variables, not constants. printf("%d\n", c); 

Ho messo il tuo codice all’interno delle funzioni sul explorer del compilatore Godbolt per ottenere l’asm per quelle affermazioni.

Per valutare a/b , gcc -O0 deve emettere il codice per ricaricare a e b dalla memoria e non fare alcuna ipotesi sul loro valore.

Ma con int c = a / -1; , non è ansible modificare il -1 con un debugger , quindi gcc può implementare tale istruzione nello stesso modo in cui implementerebbe int c = -a; , con x86 neg eax o AArch64 neg w0, w0 w0 neg w0, w0 w0 istruzione, circondato da un carico (a) / negozio (c). Su ARM32, è un rsb r3, r3, #0 (reverse-sottrarre: r3 = 0 - r3 ).

Tuttavia, clang5.0 -O0 non esegue questa ottimizzazione. Usa ancora idiv per a / -1 , quindi entrambe le versioni idiv su x86 con clang. Perché gcc “ottimizza” del tutto? Vedi Disabilita tutte le opzioni di ottimizzazione in GCC . gcc si trasforma sempre attraverso una rappresentazione interna e -O0 è solo la quantità minima di lavoro necessaria per produrre un binario. Non ha una modalità “stupida e letterale” che cerca di rendere il più ansible simile alla sorgente.


x86 idiv vs. AArch64 sdiv :

x86-64:

  # int c = a / b from x86_fault() mov eax, DWORD PTR [rbp-4] cdq # dividend sign-extended into edx:eax idiv DWORD PTR [rbp-8] # divisor from memory mov DWORD PTR [rbp-12], eax # store quotient 

A differenza di imul r32,r32 , non esiste un 2-operando idiv che non abbia un input della metà superiore del dividendo. Comunque, non che sia importante; gcc lo sta usando solo con edx = copie del bit di segno in eax , quindi sta facendo davvero un quoziente 32b / 32b => 32b + resto. Come documentato nel manuale di Intel , idiv solleva #DE su:

  • divisore = 0
  • Il risultato firmato (quoziente) è troppo grande per la destinazione.

L’overflow può facilmente accadere se si utilizza l’intera gamma di divisori, ad esempio per int result = long long / int con una singola divisione 64b / 32b => 32b. Ma gcc non può fare quell’ottimizzazione perché non è permesso creare codice che si guasterebbe invece di seguire le regole di promozione integer C e fare una divisione a 64-bit e poi troncare a int . Inoltre non ottimizza anche nei casi in cui il divisore è noto per essere abbastanza grande da non poter essere #DE

Quando si esegue la divisione 32b / 32b (con cdq ), l’unico input che può overflow è INT_MIN / -1 . Il quoziente “corretto” è un intero con segno a 33 bit, ovvero 0x80000000 positivo con un bit di segno zero iniziale che lo rende un intero con segno positivo del complemento a 2. Poiché questo non si adatta a eax , idiv solleva un’eccezione #DE . Il kernel fornisce quindi SIGFPE .

AArch64:

  # int c = a / b from x86_fault() (which doesn't fault on AArch64) ldr w1, [sp, 12] ldr w0, [sp, 8] # 32-bit loads into 32-bit registers sdiv w0, w1, w0 # 32 / 32 => 32 bit signed division str w0, [sp, 4] 

Le istruzioni di divisione hardware AFAICT, ARM non generano eccezioni per la divisione per zero o per INT_MIN / -1. O almeno, alcune CPU ARM non lo fanno. dividere per zero l’eccezione nel processore ARM OMAP3515

La documentazione di AArch64 sdiv non menziona alcuna eccezione.

Tuttavia, le implementazioni software della divisione intera potrebbero generare: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka4061.html . (gcc usa una chiamata di libreria per la divisione su ARM32 per impostazione predefinita, a meno che non si imposti un -mcpu con divisione HW.)


C Comportamento indefinito.

Come spiega PSkocik , INT_MIN / -1 è un comportamento non definito in C, come tutto l’overflow con numero intero firmato. Ciò consente ai compilatori di utilizzare istruzioni di divisione hardware su macchine come x86 senza verificare per quel caso speciale. Se non dovesse essere un errore, gli input sconosciuti richiederebbero confronti a tempo di esecuzione e controlli di ramo, e nessuno vuole che C lo richieda.


Maggiori informazioni sulle conseguenze di UB:

Con l’ottimizzazione abilitata , il compilatore può assumere che a e b mantengano i loro valori impostati quando a/b esecuzione. Può quindi vedere il programma ha un comportamento indefinito, e quindi può fare tutto ciò che vuole. gcc sceglie di produrre INT_MIN come sarebbe da -INT_MIN .

Su un sistema di complementi a 2, il numero più negativo è il suo negativo. Questa è una brutta casella d’angolo per il complemento a 2, perché significa che abs(x) può ancora essere negativo. https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number

 int x86_fault() { int a = 0x80000000; int b = -1; int c = a / b; return c; } 

compilare a questo con gcc6.3 -O3 per x86-64

 x86_fault: mov eax, -2147483648 ret 

ma clang5.0 -O3 compila a (senza preavviso anche con -Wall -Wextra`):

 x86_fault: ret 

Il comportamento indefinito è davvero totalmente indefinito. I compilatori possono fare qualunque cosa vogliano, incluso restituire qualsiasi cosa in cui i rifiuti si eax in entrata nella funzione, o caricare un puntatore NULL e un’istruzione illegale. ad es. con gcc6.3 -O3 per x86-64:

 int *local_address(int a) { return &a; } local_address: xor eax, eax # return 0 ret void foo() { int *p = local_address(4); *p = 2; } foo: mov DWORD PTR ds:0, 0 # store immediate 0 into absolute address 0 ud2 # illegal instruction 

Il tuo caso con -O0 non ha permesso ai compilatori di vedere l’UB in fase di compilazione, quindi hai ottenuto l’output “previsto” asm.

Vedi anche Cosa dovrebbe sapere di ogni programmatore C sul comportamento indefinito (lo stesso post del blog LLVM collegato da Basile).

La divisione int firmata nel complemento a due non è definita se:

  1. il divisore è zero, OR
  2. il dividendo è INT_MIN (== 0x80000000 se int è int32_t ) e il divisore è -1 (in complemento a due, -INT_MIN > INT_MAX , che causa l’overflow integer, che è un comportamento non definito in C)

( https://www.securecoding.cert.org consiglia di avvolgere operazioni intere in funzioni che controllano tali casi limite)

Dato che stai invocando un comportamento indefinito rompendo la regola 2, può succedere di tutto, e come succede, questo particolare qualsiasi cosa sulla tua piattaforma sembra essere un segnale FPE generato dal tuo processore.

Con un comportamento indefinito possono accadere cose molto brutte , ea volte accadono.

La tua domanda non ha senso in C (leggi Lattner su UB ). Ma potresti ottenere il codice assembler (ad esempio prodotto da gcc -O -fverbose-asm -S ) e preoccuparti del comportamento del codice macchina.

Su x86-64 con Linux integer overflow (e anche la divisione intera per zero, IIRC) fornisce un segnale SIGFPE . Vedi segnale (7)

BTW, sulla divisione in intero di PowerPC per zero si dice che dia -1 a livello di macchina (ma alcuni compilatori C generano un codice extra per testare quel caso).

Il codice nella tua domanda è un comportamento non definito in C. Il codice assembler generato ha un comportamento definito (dipende dall’ISA e dal processore).

(il compito è fatto per farti leggere di più su UB, in particolare il blog di Lattner , che dovresti assolutamente leggere)

Su x86 se si divide usando effettivamente l’operazione idiv (che non è realmente necessaria per gli argomenti costanti, nemmeno per le variabili-known-to-be-constant, ma è successo comunque), INT_MIN / -1 è uno dei casi che restituisce #DE (errore di divisione). È davvero un caso particolare che il quoziente sia fuori portata, in generale è ansible perché idiv divide un dividendo extra-wide dal divisore, quindi molte combinazioni causano un overflow – ma INT_MIN / -1 è l’unico caso che non è un div-by-0 che puoi accedere normalmente da linguaggi di livello superiore poiché in genere non espongono le capacità di dividendo extra-wide.

Linux mappa fastosamente il #DE in SIGFPE, che probabilmente ha confuso tutti coloro che lo hanno affrontato la prima volta.

Entrambi i casi sono strani, in quanto il primo consiste nel dividere -2147483648 di -1 e dovrebbe dare 2147483648 e non il risultato che si sta ricevendo.

0x80000000 non è un numero int valido in un’architettura a 32 bit che rappresenta numeri in complemento a due. Se si calcola il suo valore negativo, si otterrà di nuovo ad esso, in quanto non ha alcun numero opposto intorno a zero. Quando si esegue l’aritmetica con numeri interi con segno, funziona bene per l’aggiunta e la sottrazione di interi (sempre con attenzione, dato che è piuttosto facile fare un overflow, quando si aggiunge il valore più grande ad alcuni int) ma non si può tranquillamente usarlo per moltiplicare o dividere. Quindi, in questo caso, stai invocando il comportamento non definito . Si invoca sempre un comportamento non definito (o un comportamento definito dall’implementazione, che è simile, ma non uguale) sull’overflow con numeri interi con segno, poiché le implementazioni variano ampiamente nell’implementazione di ciò.

Cercherò di spiegare cosa può accadere (senza attendibilità), in quanto il compilatore è libero di fare qualsiasi cosa, o nulla del tutto.

Concretamente, 0x80000000 come rappresentato nel complemento a due è

 1000_0000_0000_0000_0000_0000_0000 

se completiamo questo numero, otteniamo (prima completiamo tutti i bit, quindi aggiungiamone uno)

 0111_1111_1111_1111_1111_1111_1111 + 1 => 1000_0000_0000_0000_0000_0000_0000 !!! the same original number. 

sorprendentemente lo stesso numero …. Hai avuto un overflow (non c’è alcun valore positivo di contropartita per questo numero, mentre sorvoliamo quando cambiamo segno) poi estrai il bit del segno, mascherando con

 1000_0000_0000_0000_0000_0000_0000 & 0111_1111_1111_1111_1111_1111_1111 => 0000_0000_0000_0000_0000_0000_0000 

che è il numero che usi come divisore, portando ad una divisione per eccezione zero.

Ma come ho detto prima, questo è ciò che può accadere sul tuo sistema, ma non è sicuro, poiché lo standard dice che questo è un comportamento non definito e, in quanto tale, puoi ottenere qualsiasi comportamento diverso dal tuo computer / compilatore.

NOTA 1

Come il compilatore è interessato, e lo standard non dice nulla sugli intervalli validi di int che devono essere implementati (lo standard non include normalmente 0x8000...000 nelle architetture a complemento di due) il comportamento corretto di 0x800...000 in due complementi architetture dovrebbe essere, in quanto ha il più grande valore assoluto per un intero di quel tipo, per dare un risultato di 0 quando si divide un numero da esso. Ma le implementazioni hardware normalmente non consentono di suddividerle per un numero simile (dato che molti di loro non implementano nemmeno la divisione di interi con segno, ma la simulano dalla divisione senza segno, così tanti semplicemente estraggono i segni e fanno una divisione senza segno). Ciò richiede un controlla prima della divisione, e come dice lo standard Comportamento indefinito , le implementazioni sono autorizzate a evitare liberamente tale controllo e non consentono la divisione per quel numero. Semplicemente seleziona l’intervallo intero per passare da 0x8000...001 a 0xffff...fff , quindi da 0x000..0000 a 0x7fff...ffff , non 0x8000...0000 il valore 0x8000...0000 come non valido.