Warum wird eine einfache Schleife optimiert, wenn das Limit 959, aber nicht 960 beträgt?

131

Betrachten Sie diese einfache Schleife:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Wenn Sie mit gcc 7 (Snapshot) oder clang (Trunk) kompilieren, erhalten -march=core-avx2 -OfastSie etwas sehr Ähnliches.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Mit anderen Worten, die Antwort wird ohne Schleife auf 960 gesetzt.

Wenn Sie den Code jedoch ändern in:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

Die produzierte Baugruppe führt tatsächlich die Schleifensumme aus? Zum Beispiel gibt clang:

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Warum ist das so und warum ist es für clang und gcc genau das gleiche?

Die Grenze für die gleiche Schleife , wenn Sie ersetzen floatmit doubleist 479. Dies ist das gleiche wieder für gcc und Klirren ist.

Update 1

Es stellt sich heraus, dass sich gcc 7 (Schnappschuss) und clang (Trunk) sehr unterschiedlich verhalten. clang optimiert die Loops für alle Limits unter 960, soweit ich das beurteilen kann. gcc hingegen reagiert empfindlich auf den genauen Wert und hat keine Obergrenze. Zum Beispiel es nicht optimiert die Schleife, wenn die Grenze 200 (wie auch viele andere Werte), aber es tut , wenn die Grenze 202 und 20002 (sowie viele andere Werte) ist.

c gcc optimization clang eleanora
quelle
3
Was Sulthan wahrscheinlich bedeutet, ist, dass 1) der Compiler die Schleife abrollt und 2) nach dem Abrollen sieht, dass die Summenoperationen zu einer zusammengefasst werden können. Wenn die Schleife nicht abgewickelt wird, können die Vorgänge nicht gruppiert werden.
Jean-François Fabre
3
Eine ungerade Anzahl von Schleifen erschwert das Abrollen. Die letzten Iterationen müssen speziell durchgeführt werden. Dies könnte ausreichen, um den Optimierer in einen Modus zu versetzen, in dem er die Verknüpfung nicht mehr erkennen kann. Es ist ziemlich wahrscheinlich, dass zuerst der Code für den Sonderfall hinzugefügt und dann erneut entfernt werden muss. Die Verwendung des Optimierers zwischen den Ohren ist immer am besten :)
Hans Passant
3
@ HansPassant Es ist auch für jede Zahl kleiner als 959 optimiert.
eleanora
6
Würde dies normalerweise nicht mit der Eliminierung von Induktionsvariablen geschehen, anstatt eine verrückte Menge abzuwickeln? Das Abrollen um den Faktor 959 ist verrückt.
Harold
4
@eleanora Ich habe mit diesem Compiler-Explorer gespielt und das Folgende scheint zu gelten (wenn es nur um den gcc-Snapshot geht): Wenn die Anzahl der Schleifen ein Vielfaches von 4 und mindestens 72 ist, wird die Schleife nicht abgewickelt (oder vielmehr von a abgewickelt Faktor 4); Andernfalls wird die gesamte Schleife durch eine Konstante ersetzt - auch wenn die Anzahl der Schleifen 2000000001 beträgt. Mein Verdacht: vorzeitige Optimierung (wie in einem vorzeitigen "Hey, ein Vielfaches von 4, das ist gut zum Abrollen", das die weitere Optimierung im Vergleich zu a blockiert gründlicher "Was ist mit dieser Schleife überhaupt los?")
Hagen von Eitzen

Antworten:

88

TL; DR

Standardmäßig verhält sich der aktuelle Snapshot GCC 7 inkonsistent, während frühere Versionen aufgrund von PARAM_MAX_COMPLETELY_PEEL_TIMES16 ein Standardlimit haben. Es kann über die Befehlszeile überschrieben werden.

Das Grundprinzip des Limits besteht darin, ein zu aggressives Abrollen der Schleife zu verhindern, das ein zweischneidiges Schwert sein kann .

GCC-Version <= 6.3.0

Die relevante Optimierungsoption für GCC ist -fpeel-loops, die indirekt zusammen mit dem Flag aktiviert wird -Ofast(Schwerpunkt liegt bei mir):

Schält Schleifen, für die genügend Informationen vorhanden sind, die nicht viel rollen (aufgrund von Profilfeedback oder statischer Analyse ). Es wird auch das vollständige Schälen der Schleife aktiviert (dh das vollständige Entfernen von Schleifen mit einer kleinen konstanten Anzahl von Iterationen ).

Aktiviert mit -O3und / oder -fprofile-use.

Weitere Details erhalten Sie durch Hinzufügen von -fdump-tree-cunroll:

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

Die Nachricht stammt von /gcc/tree-ssa-loop-ivcanon.c:

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

daher try_peel_loopkehrt die Funktion zurück false.

Eine ausführlichere Ausgabe kann erreicht werden mit -fdump-tree-cunroll-details:

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

Es ist möglich, die Grenzen durch Plaing mit max-completely-peeled-insns=nund max-completely-peel-times=nparams zu optimieren :

max-completely-peeled-insns

Die maximale Anzahl von Insns einer vollständig geschälten Schleife. 

max-completely-peel-times

Die maximale Anzahl von Iterationen einer Schleife, die für ein vollständiges Schälen geeignet sind.

Weitere Informationen zu Insns finden Sie im GCC Internals Manual .

Zum Beispiel, wenn Sie mit folgenden Optionen kompilieren:

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

dann verwandelt sich Code in:

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Clang

Ich bin nicht sicher, was Clang tatsächlich tut und wie man seine Grenzen ändert, aber wie ich beobachtet habe, könnten Sie es zwingen, den Endwert zu bewerten, indem Sie die Schleife mit einem Abroll-Pragma markieren , und es wird sie vollständig entfernen:

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

Ergebnisse in:

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret
Grzegorz Szpetkowski
quelle
Vielen Dank für diese sehr schöne Antwort. Wie andere betont haben, scheint gcc empfindlich auf die genaue Grenzgröße zu reagieren. Zum Beispiel kann die Schleife für 912 godbolt.org/g/EQJHvT nicht entfernt werden . Was sagen fdump-tree-cunroll-details in diesem Fall?
Eleanora
In der Tat hat sogar 200 dieses Problem. Dies alles ist in einer Momentaufnahme von gcc 7, die Godbolt bereitstellt. godbolt.org/g/Vg3SVs Dies gilt überhaupt nicht für Klirren .
Eleanora
13
Sie erklären die Mechanik des Peelings, aber nicht, welche Relevanz 960 hat oder warum es überhaupt eine Grenze gibt
MM
1
@MM: Das Peeling-Verhalten ist zwischen GCC 6.3.0 und dem neuesten Snaphost völlig unterschiedlich. Im ersteren Fall vermute ich stark, dass das fest codierte Limit durch PARAM_MAX_COMPLETELY_PEEL_TIMESparam erzwungen wird , das /gcc/params.def:321mit dem Wert 16 definiert ist.
Grzegorz Szpetkowski
14
Vielleicht möchten Sie erwähnen, warum sich GCC auf diese Weise bewusst einschränkt. Insbesondere wenn Sie Ihre Schleifen zu aggressiv abrollen, wird die Binärdatei größer und es ist weniger wahrscheinlich, dass Sie in den L1-Cache passen. Cache-Fehlschläge sind im Vergleich zum Speichern einiger bedingter Sprünge unter der Annahme einer guten Verzweigungsvorhersage (die Sie für eine typische Schleife haben werden) möglicherweise recht teuer .
Kevin
19

Nachdem ich Sulthans Kommentar gelesen habe, denke ich, dass:

  1. Der Compiler rollt die Schleife vollständig ab, wenn der Schleifenzähler konstant (und nicht zu hoch) ist.

  2. Sobald es abgewickelt ist, sieht der Compiler, dass die Summenoperationen zu einer zusammengefasst werden können.

Wenn die Schleife aus irgendeinem Grund nicht abgewickelt wird (hier: es würden zu viele Anweisungen mit generiert 1000), können die Operationen nicht gruppiert werden.

Der Compiler konnte feststellen, dass das Abrollen von 1000 Anweisungen eine einzelne Addition darstellt. Die oben beschriebenen Schritte 1 und 2 sind jedoch zwei separate Optimierungen, sodass er nicht das "Risiko" des Abrollens eingehen kann, ohne zu wissen, ob die Vorgänge gruppiert werden können (Beispiel: Ein Funktionsaufruf kann nicht gruppiert werden.

Hinweis: Dies ist ein Eckfall: Wer verwendet eine Schleife, um dasselbe erneut hinzuzufügen? Verlassen Sie sich in diesem Fall nicht darauf, dass der Compiler möglicherweise abrollt / optimiert. Schreiben Sie direkt die richtige Operation in eine Anweisung.

Jean-François Fabre
quelle
1
Können Sie sich dann auf diesen not too highTeil konzentrieren? Ich meine, warum ist das Risiko bei nicht vorhanden 100? Ich habe etwas erraten ... in meinem Kommentar oben ... kann es der Grund dafür sein?
user2736738
Ich denke, dass der Compiler sich der Gleitkomma-Ungenauigkeit, die er auslösen könnte, nicht bewusst ist. Ich denke, es ist nur eine Größenbeschränkung für Anweisungen. Sie haben max-unrolled-insnsnebenmax-unrolled-times
Jean-François Fabre
Ah, es war eine Art von meinem Gedanken oder meiner Vermutung ... ich möchte eine klarere Begründung erhalten.
user2736738
5
Interessanterweise kann der gcc-Compiler die Schleife unabhängig von der Anzahl der Iterationen aufgrund seiner Optimierungen der Induktionsvariablen ( ) reduzieren, wenn Sie den Wert floatin einen ändern . Aber die scheinen nicht für s zu funktionieren . int-fivoptsfloat
Tavian Barnes
1
@CortAmmon Richtig, und ich erinnere mich, dass ich einige Leute gelesen habe, die überrascht und verärgert waren, dass GCC MPFR verwendet, um sehr große Zahlen präzise zu berechnen, was ziemlich andere Ergebnisse liefert als die äquivalenten Gleitkommaoperationen, die Fehler und Präzisionsverluste akkumuliert hätten. Zeigt, dass viele Menschen Gleitkomma falsch berechnen.
Zan Lynx
12

Sehr gute Frage!

Sie scheinen die Anzahl der Iterationen oder Operationen, die der Compiler bei der Vereinfachung des Codes inline zu setzen versucht, begrenzt zu haben. Wie von Grzegorz Szpetkowski dokumentiert, gibt es compilerspezifische Möglichkeiten, diese Grenzwerte mit Pragmas oder Befehlszeilenoptionen zu optimieren.

Sie können auch mit dem Compiler-Explorer von Godbolt spielen , um zu vergleichen, wie sich verschiedene Compiler und Optionen auf den generierten Code auswirken: gcc 6.2und icc 17den Code für 960 weiterhin einbinden, während clang 3.9dies nicht der Fall ist (bei der Standardkonfiguration von Godbolt wird das Inlining bei 73 tatsächlich beendet).

chqrlie
quelle
Ich habe die Frage bearbeitet, um die von mir verwendeten Versionen von gcc und clang zu verdeutlichen. Siehe godbolt.org/g/FfwWjL . Ich benutze zum Beispiel -Ofast.
Eleanora