code Algebraische Reduktion von Ganzzahlausdrücken mit Vorzeichen in C/C++



gcc optimization flags (2)

  1. Nein, die Multiplikation ist in Ganzzahlen mit Vorzeichen nicht assoziativ. Betrachte (0 * x) * x vs. 0 * (x * x) - Letzteres hat potenziell undefiniertes Verhalten, während ersteres immer definiert ist.

  2. Das Potenzial für undefiniertes Verhalten führt immer nur zu neuen Optimierungsmöglichkeiten, das klassische Beispiel ist das Optimieren von x + 1 > x zu true für signiertes x , eine Optimierung, die für unsignierte Ganzzahlen nicht verfügbar ist.

Ich glaube nicht, dass Sie annehmen können, dass gcc, wenn es nicht gelingt, a - (b - c) in (a + c) - b zu ändern, eine verpasste Optimierungsmöglichkeit darstellt; Die beiden Berechnungen kompilieren zu denselben zwei Anweisungen auf x86-64 ( leal und subl ), nur in einer anderen Reihenfolge.

Tatsächlich kann die Implementierung annehmen, dass Arithmetik assoziativ ist, und diese für Optimierungen verwenden, 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 weiteres Beispiel wird try (a + a) - a - gcc dies für a für a als auch für unsigned optimieren.

Ich wollte sehen, ob GCC a - (b - c) zu (a + c) - b mit vorzeichenbehafteten und vorzeichenlosen Ganzzahlen reduzieren würde, also habe ich zwei Tests erstellt

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

Ich kompilierte zuerst mit gcc -O3 test1.c test2.c -S und schaute auf die Baugruppe. Für beide Tests waren fooau identisch, fooas jedoch nicht.

Soweit ich verstehe, kann vorzeichenlose Arithmetik aus der folgenden Formel abgeleitet werden

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

mit dem angezeigt werden kann, dass vorzeichenlose Arithmetik assoziativ ist. Aber da der vorzeichenbehaftete Überlauf ein undefiniertes Verhalten ist, gilt diese Gleichheit nicht unbedingt für eine vorzeichenbehaftete Addition (dh die vorzeichenbehaftete Addition ist nicht assoziativ), was erklärt, warum GCC a - (b - c) auf (a + c) - b für vorzeichenbehaftete ganze Zahlen reduziert hat. Aber wir können dem GCC mitteilen, diese Formel mit -fwrapv . 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, also denke ich, dass es mit der obigen Formel gezeigt werden kann

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

was ich denke, kann auch zeigen, dass vorzeichenlose modulare Multiplikation auch assoziativ ist. Da GCC jedoch nur drei Multiplikationen für foomu zeigt dies, dass GCC annimmt, dass die Ganzzahl-Multiplikation mit Vorzeichen assoziativ ist.

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

Zwei Fragen:

  1. Stimmt es, dass Addition nicht mit Ganzzahlen mit Vorzeichen assoziativ ist, aber Multiplikation in C / C ++?

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


Answer #1

Die algebraische Reduktion vorzeichenbehafteter Integerausdrücke kann durchgeführt werden, vorausgesetzt, sie hat für jeden definierten Satz von Eingaben das gleiche Ergebnis. Also wenn der Ausdruck

a * a * a * a * a * a

ist definiert - das heißt, a ist klein genug, dass während der Berechnung kein vorzeichenbehafteter Überlauf auftritt - dann erzeugt jede Neugruppierung der Multiplikationen den gleichen Wert, da kein Produkt mit weniger als sechs a s überlaufen kann.

Das Gleiche gilt für a + a + a + a + a + a .

Dinge ändern sich, wenn die multiplizierten (oder addierten) Variablen 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.

Nimm zum Beispiel den Ausdruck

a - (b - c)

Algebraisch ist das gleichbedeutend mit

(a + c) - b

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

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





integer