Warum wird eine einfache Schleife optimiert, wenn das Limit 959, aber nicht 960 ist?

Betrachten Sie diese einfache Schleife:

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

Kompiliert man mit gcc 7 (snapshot) oder clang (trunk) mit -march=core-avx2 -Ofast Sie erhalten 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, es setzt die Antwort ohne Schleife einfach auf 960.

Wenn Sie jedoch den Code ä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 durch? clang gibt zum Beispiel:

.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 gleich?

Das Limit für die gleiche Schleife, wenn Sie ersetzen float mit double ist 479. Dies gilt wieder für gcc und clang.

Aktualisierung 1

Es stellt sich heraus, dass sich gcc 7 (snapshot) und clang (trunk) sehr unterschiedlich verhalten. Clang optimiert die Loops für alle Limits unter 960, soweit ich das beurteilen kann. gcc hingegen ist empfindlich gegenüber dem genauen Wert und hat keine Obergrenze. Zum Beispiel es nicht Optimieren Sie die Schleife, wenn das Limit 200 (sowie viele andere Werte) ist, aber es tut wenn die Grenze 202 und 20002 (sowie viele andere Werte) ist.

TL;DR

Standardmäßig verhält sich der aktuelle Snapshot GCC 7 inkonsistent, während frühere Versionen aufgrund von Standardlimits eingeschränkt sind PARAM_MAX_COMPLETELY_PEEL_TIMESdas ist 16. Es kann von der Befehlszeile aus überschrieben werden.

Der Grund für die Begrenzung besteht darin, ein zu aggressives Abrollen der Schleife zu verhindern, was ein zweischneidiges Schwert sein kann.

GCC-Version <= 6.3.0

Die relevante Optimierungsoption für GCC ist -fpeel-loopsdas indirekt zusammen mit flag aktiviert wird -Ofast (Hervorhebung von mir):

Schält Loops, für die genügend Informationen vorliegen, dass sie nicht viel rollen (aus Profil-Feedback bzw statische Analyse). Es schaltet auch das vollständige Schleifen-Peeling ein (dh vollständige Entfernung von Schleifen mit kleiner konstanter Anzahl von Iterationen).

Aktiviert mit -O3 und/oder -fprofile-use.

Weitere Details erhalten Sie durch Hinzufügen -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 ist 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;
    }

somit try_peel_loop Funktion zurück false.

Eine ausführlichere Ausgabe kann mit erreicht werden -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 zu optimieren, indem Sie mit klicken max-completely-peeled-insns=n und max-completely-peel-times=n Parameter:

max-completely-peeled-insns

Die maximale Anzahl von Insns einer vollständig abgezogenen Schleife.

max-completely-peel-times

Die maximale Anzahl von Iterationen einer Schleife, die für ein vollständiges Peeling geeignet ist.

Um mehr über insns zu erfahren, können Sie auf verweisen GCC Internes Handbuch.

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

Klirren

Ich bin mir nicht sicher, was Clang tatsächlich tut und wie man seine Grenzen optimiert, aber wie ich beobachtet habe, könnten Sie es zwingen, den endgültigen Wert auszuwerten, indem Sie die Schleife mit markieren Pragma ausrollenund es wird es vollständig entfernen:

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

ergibt sich zu:

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

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

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

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

Wenn die Schleife aus irgendeinem Grund nicht ausgerollt wird (hier: es würde zu viele Anweisungen mit generieren 1000), können die Vorgänge nicht gruppiert werden.

Der Compiler könnte Beachten Sie, dass das Aufrollen von 1000 Anweisungen auf eine einzelne Addition hinausläuft, aber die oben beschriebenen Schritte 1 und 2 sind zwei separate Optimierungen, sodass Sie nicht das “Risiko” des Aufrollens eingehen können, ohne zu wissen, ob die Operationen gruppiert werden können (Beispiel: ein Funktionsaufruf kann nicht gruppiert werden).

Hinweis: Dies ist ein Sonderfall: Wer verwendet eine Schleife, um dasselbe noch einmal hinzuzufügen? Verlassen Sie sich in diesem Fall nicht auf das mögliche Entrollen/Optimieren des Compilers; Schreiben Sie die richtige Operation direkt in eine Anweisung.

Sehr gute Frage!

Sie scheinen eine Grenze für die Anzahl der Iterationen oder Operationen erreicht zu haben, die der Compiler beim Vereinfachen des Codes einzubetten versucht. Wie von Grzegorz Szpetkowski dokumentiert, gibt es Compiler-spezifische Möglichkeiten, diese Grenzen mit Pragmas oder Befehlszeilenoptionen zu optimieren.

Sie können auch mit spielen Godbolts Compiler Explorer um zu vergleichen, wie sich verschiedene Compiler und Optionen auf den generierten Code auswirken: gcc 6.2 und icc 17 immer noch den Code für 960 inline, während clang 3.9 nicht (mit der standardmäßigen Godbolt-Konfiguration stoppt das Inlining tatsächlich bei 73).