riduzioni algebrica delle espressioni intere firmati in C/C++

Question

ho voluto vedere se GCC ridurrebbe a - (b - c)-(a + c) - b con numeri interi con e senza segno così ho creato due test

//test1.c 
unsigned fooau(unsigned a, unsigned b, unsigned c) { return a - (b - c); } 
signed fooas(signed a, signed b, signed c) { return a - (b - c); } 
signed fooms(signed a) { return a*a*a*a*a*a; } 
unsigned foomu(unsigned a) { return a*a*a*a*a*a; } 

//test2.c 
unsigned fooau(unsigned a, unsigned b, unsigned c) { return (a + c) - b; } 
signed fooas(signed a, signed b, signed c) { return (a + c) - b; } 
signed fooms(signed a) { return (a*a*a)*(a*a*a); } 
unsigned foomu(unsigned a) { return (a*a*a)*(a*a*a); } 

ho compilato prima con gcc -O3 test1.c test2.c -S e guardarono la montaggio. Per entrambi i test fooau erano identici, tuttavia non lo era lo fooas.

Per quanto comprendo aritmetica senza segno può essere derivato da the following formula

(a%n + b%n)%n = (a+b)%n 

che può essere usato per mostrare che l'aritmetica senza segno è associativa. Ma dal signed overflow is undefined behavior questa uguaglianza non è necessariamente valida per l'aggiunta firmata (cioè l'aggiunta firmata non è associativa) il che spiega perché GCC non ha ridotto a - (b - c) a (a + c) - b per gli interi con segno. Ma possiamo dire a GCC di usare questa formula usando -fwrapv. L'utilizzo di questa opzione fooas per entrambi i test è identico.

Ma che dire della moltiplicazione? Per entrambi i test, fooms e foomu sono stati semplificati in tre moltiplicazioni (a*a*a*a*a*a to (a*a*a)*(a*a*a)). Ma moltiplicazione può essere scritto come addizione ripetuta in modo da utilizzare la suddetta formula Credo si possa dimostrare che

((a%n)*(b%n))%n = (a*b)%n 

che ritengo possono anche mostrare che la moltiplicazione modulare senza segno è associativo pure. Ma dal momento che GCC ha utilizzato solo tre moltiplicazioni per foomu, ciò dimostra che GCC presuppone che la moltiplicazione dell'intero con segno sia associativa.

Questa mi sembra una contraddizione. Per l'aggiunta l'aritmetica firmata non era associativa ma per la sua moltiplicazione.

due domande:

1. E 'vero che l'aggiunta non è associativo con interi con segno, ma la moltiplicazione è in C/C++?

2. Se l'overflow con segno viene utilizzato per l'ottimizzazione, non è il fatto che GCC non riduce l'espressione algebrica e non ottimizza l'ottimizzazione? Non sarebbe meglio per l'ottimizzazione usare -fwrapv (ho capito che a - (b - c) a (a + c) - b non è molto ridotto ma sono preoccupato per casi più complicati)? Questo significa che l'ottimizzazione a volte utilizzando -fwrapv è più efficiente e talvolta non lo è?

Answer 1

1. No, la moltiplicazione non è associativa in interi con segno. Si consideri (0 * x) * x rispetto a 0 * (x * x) - quest'ultimo ha un comportamento potenzialmente indefinito mentre il primo è sempre definito.

2. Il potenziale di comportamento non definito introduce sempre e solo nuove opportunità di ottimizzazione, l'esempio classico è l'ottimizzazione x + 1 > x per true per firmato x, un'ottimizzazione che non è disponibile per gli interi senza segno.

Non credo che si può assumere che gcc non riuscendo a cambiare a - (b - c)-(a + c) - b rappresenta un'occasione mancata ottimizzazione; i due calcoli compilano le stesse due istruzioni su x86-64 (leal e subl), solo in un ordine diverso.

In effetti, l'implementazione ha il diritto di presumere che l'aritmetica è associativa, e l'uso che per le ottimizzazioni, dal momento che tutto può succedere su UB tra cui l'aritmetica modulo o infinita gamma aritmetica. Tuttavia, è in quanto il programmatore non è autorizzato ad assumere associatività a meno che non si possa garantire che non si verifichi un overflow di risultati intermedi.

Come altro esempio, prova (a + a) - a - gcc lo ottimizzerà su a per il a firmato come non firmato.

Answer 2

La riduzione algebrica delle espressioni con numero intero con segno può essere eseguita purché abbia lo stesso risultato per qualsiasi serie di ingressi definita. Quindi, se l'espressione

a * a * a * a * a * a 

è definito - vale a dire, a è abbastanza piccolo che nessuno di overflow firmato si verifica durante il calcolo - allora qualsiasi raggruppamento delle moltiplicazioni produrrà lo stesso valore, perché nessun prodotto inferiore a sei a s possono overflow.

Lo stesso vale per a + a + a + a + a + a.

Le cose cambiano se le variabili moltiplicate (o aggiunte) non sono tutte uguali, o se le aggiunte sono mescolate con le sottrazioni. In questi casi, il raggruppamento e la riorganizzazione del calcolo potrebbero portare a un overflow firmato che non si è verificato nel calcolo canonico.

Ad esempio, prendere l'espressione

a - (b - c) 

Algebricamente, che è equivalente a

(a + c) - b 

Ma il compilatore non può farlo riarrangiamento perché è possibile che il valore intermedio a+c traboccherà di ingressi che non causerebbe un trabocco nell'originale. Supponiamo di avere a=INT_MAX-1; b=1; c=2; quindi a+c risultati in overflow, ma a - (b - c) è calcolato come a - (-1), che è INT_MAX, senza overflow.

Se il compilatore può presupporre che l'overflow con segno non trapoli ma invece è calcolato modulo INT_MAX+1, è possibile che tali riarrangiamenti siano possibili. Le opzioni -fwrapv consentono a gcc di fare questa ipotesi.