Algebraische Reduktionen von Signed Integer Ausdrücke in C/C++

Question

wollte ich sehen, ob GCC a - (b - c)-(a + c) - b mit und ohne Vorzeichen ganzen Zahlen so habe ich zwei Tests

//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); } 

I zusammengestellt zuerst mit gcc -O3 test1.c test2.c -S und sah die reduzieren würde Versammlung. Für beide Tests waren fooau identisch aber fooas war nicht.

Soweit ich unsigned arithmetische verstehen kann von the following formula

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

abgeleitet werden, die verwendet werden können, die unsigned Arithmetik zu zeigen ist assoziativ. Aber da signed overflow is undefined behavior diese Gleichheit nicht unbedingt für die vorzeichenbehaftete Addition gilt (d. H. Die vorzeichenbehaftete Addition ist nicht assoziativ), erklärt dies, warum GCC a - (b - c) nicht auf (a + c) - b für vorzeichenbehaftete Ganzzahlen reduziert hat. Aber wir können dem GCC mitteilen, diese Formel mit -fwrapv zu verwenden. Mit dieser Option ist fooas für beide Tests identisch.

Aber was ist mit Multiplikation? Für beide Tests wurden fooms und foomu auf drei Multiplikationen vereinfacht (a*a*a*a*a*a to (a*a*a)*(a*a*a)). Aber Multiplikation kann als wiederholte Addition geschrieben werden, um unter Verwendung der Formel oben Ich denke, es kann gezeigt werden, dass

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

, die ich denken kann auch zeigen, dass unsigned modulare Multiplikation als auch assoziativ ist. Aber da GCC nur drei Multiplikationen für foomu verwendet, zeigt dies, dass GCC annimmt, dass Vorzeichen Multiplikation ist assoziativ.

Dies scheint wie ein Widerspruch zu mir. Für Addition war arithmetische Vorzeichen nicht assoziativ, sondern für Multiplikation.

Zwei Fragen:

1. Ist es wahr, dass die Zugabe nicht mit unterzeichnet ganzen Zahlen ist assoziativ, aber Multiplikation ist in C/C++?

2. Wenn signed Überlauf für die Optimierung verwendet wird, ist nicht die Tatsache, dass GCC den algebraischen Ausdruck nicht reduziert einen Fehler zu optimieren? Wäre es nicht besser besser für die Optimierung zu verwenden -fwrapv (Ich verstehe, dass a - (b - c) bis (a + c) - b ist nicht viel von einer Reduktion, aber ich mache mir Sorgen über kompliziertere Fälle)? Bedeutet dies für die Optimierung manchmal mit -fwrapv ist effizienter und manchmal ist es nicht?

Answer 1

1. Nein, Multiplikation assoziativ ist nicht in ganzen Zahlen unterzeichnet. Betrachte (0 * x) * x vs. 0 * (x * x) - Letzteres hat möglicherweise undefiniertes Verhalten, während ersteres immer definiert ist.

2. Das Potenzial für undefiniertes Verhalten führt immer nur neue Optimierungsmöglichkeiten, das klassische Beispiel x + 1 > x zu true zur Optimierung unterzeichnete x eine Optimierung, die nicht für ganze Zahlen ohne Vorzeichen zu sein, ist.

Ich glaube nicht, dass gcc a - (b - c)-(a + c) - b stellt eine verpasste Gelegenheit Optimierung andernfalls annehmen kann sich ändern; Die beiden Berechnungen kompilieren zu den gleichen zwei Anweisungen auf x86-64 (leal und subl), nur in einer anderen Reihenfolge. Die Implementierung Implementierung ist in der Tat berechtigt, davon auszugehen, dass Arithmetik assoziativ ist, und verwenden Sie das für Optimierungen, da bei UB alles passieren kann, einschließlich Modulo-Arithmetik oder Arithmetik mit unendlicher Reichweite. Sie als Programmierer sind jedoch nicht berechtigt, Assoziativität anzunehmen, es sei denn, Sie können garantieren, dass kein Zwischenergebnis überläuft.

Als ein anderes Beispiel, versuchen Sie (a + a) - a - gcc wird dies zu a für unterzeichnet a sowie für unsigned optimieren.

Answer 2

Die algebraische Reduktion von vorzeichenbehafteten ganzzahligen Ausdrücken kann durchgeführt werden, vorausgesetzt, sie hat das gleiche Ergebnis für alle definierten definierten Eingänge. Also, wenn der Ausdruck

a * a * a * a * a * a 

definiert ist - das heißt, ist a klein genug, dass kein unterzeichneter Überlauf während der Berechnung erfolgt - dann jede Umgruppierung der Multiplikationen den gleichen Wert produzieren, da kein Produkt von weniger als sechs a s können überlaufen. Das gleiche gilt für a + a + a + a + a + a.

Dinge ändern sich, wenn die Variablen multipliziert (oder addiert) nicht alle gleich sind, oder wenn die Additionen mit Subtraktionen vermischt sind. In diesen Fällen könnte das Neugruppieren und Umordnen der Berechnung zu einem vorzeichenbehafteten Überlauf führen, der bei der kanonischen Berechnung nicht vorkam.

Nehmen wir zum Beispiel den Ausdruck

a - (b - c) 

algebraisch, das ist äquivalent zu

(a + c) - b 

Aber kann der Compiler nicht, dass die Umlagerung tun, weil es möglich ist, dass der Zwischenwert a+c mit Eingaben überläuft das würde keinen Überlauf im Original verursachen. Angenommen, wir hätten a=INT_MAX-1; b=1; c=2; dann a+c führt zu einem Überlauf, aber a - (b - c) wird als , die INT_MAX ist, ohne Überlauf berechnet.

Wenn der Compiler annehmen kann, dass der vorzeichenbehaftete Überlauf nicht abfängt, sondern stattdessen modulo INT_MAX+1 berechnet wird, sind diese Umlagerungen möglich. Mit den Optionen -fwrapv kann gcc diese Annahme treffen.