gcc Schleifenentrollen Kuriosität

Question

Im Zuge eines „Ungleich-Scan“ für Boolesche Arrays zu schreiben, beendet ich diese Schleife bis zu schreiben:

// Heckman recursive doubling 
#ifdef STRENGTHREDUCTION // Haswell/gcc does not like the multiply 
    for(s=1; s<BITSINWORD; s=s*2) { 
#else // STRENGTHREDUCTION 
    for(s=1; s<BITSINWORD; s=s+s) { 
#endif // STRENGTHREDUCTION 
     w = w XOR (w >> s); 
    } 

Was ich beobachtet, dass gcc die s = s entrollen WÜRDE * 2 Schleife, , aber nicht die s = s + s Schleife. Dies ist etwas nicht intuitiv, wie die Schleife-Count-Analyse für die Zugabe sollte IMO einfacher sein als für multiplizieren. Ich vermute, dass gcc kennt die s = s + s Schleife zählen, und ist nur verschämt.

Weiß jemand, ob es einen guten Grund für dieses Verhalten auf gcc's Seite gibt? ich diese aus Neugier bin fragen ...

[Die abgerollt Version lief BTW, ein gutes Stück langsamer als die Schleife.]

Danke, Robert

Answer 1

Das ist interessant.

erste Vermutung

Meine erste Vermutung wäre, dass Schleife entrollen Analyse des gcc erwartet die Zugabe Fall weniger von Schleifenentrollen profitieren, weil s langsamer wächst.

I Experiment auf dem folgenden Code:

#include <stdio.h> 
int main(int argc, char **args) { 
    int s; 
    int w = 255; 
    for (s = 1; s < 32; s = s * 2) 
    { 
     w = w^(w >> s); 
    } 
    printf("%d", w); // To prevent everything from being optimized away 
    return 0; 
} 

Und eine andere Version, die die gleiche, außer die Schleife s = s + s hat, ist. Ich finde, dass gcc 4.9.2 die Schleife in der multiplikativen Version entrollt, aber nicht die additive. Dies wird die Erstellung mit

gcc -S -O3 test.c 

Meine erste Vermutung ist, dass gcc die additive Version annimmt, wenn abgerollt, in mehr Bytes Code führen würde, die in der icache passen und daher nicht optimiert ist. Die Änderung der Schleifenbedingung von s < 32 zu s < 4 in der additiven Version führt jedoch immer noch nicht zu einer Optimierung, obwohl es scheint, dass gcc leicht erkennen sollte, dass es nur sehr wenige Iterationen der Schleife gibt.

Mein nächster Versuch (zurück zum s < 32 als Bedingung zu gehen) ist explizit gcc zu sagen, Schleifen bis zu 100 mal entrollen:

gcc -S -O3 -fverbose-asm --param max-unroll-times=100 test.c 

Diese noch eine Schleife in der Baugruppe erzeugt. Der Versuch, in nicht abgerollten Schleifen mehr Anweisungen mit --param max-entrollt-insns zuzulassen, behält die Schleife ebenfalls bei. Aus diesem Grund können wir die Möglichkeit, dass gcc denkt, dass es ineffizient ist, es zu entrollen, weitgehend eliminieren.

Interessanterweise rollt der Versuch, mit clang bei -O3 zu kompilieren sofort die Schleife aus. clang ist known to unroll more aggressively, aber das scheint keine befriedigende Antwort zu sein.

Ich kann gcc die additive Schleife entrollen, indem es eine Konstante und nicht s sich selbst hinzufügen, das heißt, ich mache s = s + 2. Dann rollt sich die Schleife ab.

Zweite Vermutung

Das ist für mich führt theoretisieren, dass gcc nicht in der Lage ist, zu verstehen, wie viele Iterationen der Schleife für laufen (notwendig zum Abrollen), wenn der Wert erhöhen, hängt der Schleife auf den Wert des Zählers mehr als einmal. Ich wechsle die Schleife wie folgt:

for (s = 2; s < 32; s = s*s) 

Und es spielt entrollen nicht mit gcc, während Klirren es entrollt. Also meine beste Schlussfolgerung ist, dass gcc die Anzahl der Iterationen nicht berechnet, wenn die increment-Anweisung der Schleife die Form s = s (op) s hat.

Answer 2

Compiler routinemäßig Stärke Verringerung, so würde ich erwarten, dass gcc würde es hier verwenden, ersetzen s * 2 durch s + s, zu welchem ​​Zeitpunkt die Formen der beiden Quellcodeausdrücke übereinstimmen würde.

Wenn das nicht der Fall ist, dann denke ich, es ist ein Fehler in gcc. Die Analyse zur Berechnung der Schleife Anzahl mit s + s ist (marginal) einfacher als die mit s * 2, so würde ich erwarten, dass gcc wäre (marginal) eher die s + s Fall zu entrollen.