Loop unrolling-Optimierung, wie funktioniert das

Diese ist eher zur demonstration, was ein compiler ist in der Lage, sondern als das, was alle compiler tun würde. Quelle:

#include <stdio.h>

int main(void)
{
    int i, sum = 0;

    for(i=0; i<5; i++) {
        sum+=i;
    }

    printf("%d\n", sum);
    return 0;
}

Hinweis: die printf habe ich Hinzugefügt. Wenn die variable nicht verwendet, kann der compiler optimieren den gesamten loop.

Kompilieren mit -O0 (Keine Optimierung)

gcc -Wall -O0 -S -c lala.c:

.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)
    jle .L3

Der Schleife passiert, die in eine 'dumme' Art und Weise, mit -8(%rbp) variable i.

Kompilieren mit -O1 (Optimierung 1)

gcc -Wall -O1 -S -c lala.c:

movl    $10, %edx

Die Schleife wurde komplett entfernt und ersetzt mit dem entsprechenden Wert.

In abrollen, sucht der compiler um zu sehen, wie viele Iterationen passieren würde, und versucht zu entrollen durch ausführen weniger Iterationen. Zum Beispiel, die Schleife könnte dupliziert werden zweimal dazu führen würde, dass die Zahl der Geschäftsstellen halbiert werden. Solchen Fall in C:

int i = 0, sum = 0;

sum += i;
i++;

for(; i<5;i++) {
    sum+=i;
    i++;
    sum+=i;
}

Beachten Sie, dass eine iteration musste extrahiert werden aus der Schleife. Dies ist, weil 5 eine ungerade Zahl ist, und so kann die Arbeit nicht einfach halbiert werden, die durch das duplizieren des Inhalts. In diesem Fall wird die Schleife nur zweimal eingegeben werden. Der Assembler-code produziert von -O0:

    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    jmp .L2
.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)

Komplett abrollen in C:

for(i=0; i<5;i++) {
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
    i++;
    sum+=i;
}

Dieser Zeit die Schleife wird tatsächlich nur einmal eingegeben. Die Montage produziert mit -O0:

.L3:
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
    movl    -8(%rbp), %eax
    addl    %eax, -4(%rbp)
    addl    $1, -8(%rbp)
.L2:
    cmpl    $4, -8(%rbp)
    jle .L3

In der basic-Ebene, das Konzept der loop-unrolling ist, einfach kopieren den Körper der Schleife mehrfach als angemessen. Der compiler kann nicht, andere Optimierungen (z.B. das einfügen von festen Werten aus einer Berechnung) als gut, aber würde nicht als abrollen der Schleife, aber potenziell ersetzen Sie alle zusammen. Aber das wäre letztlich abhängig von den compiler-flags verwendet.

Dem C-code (ent -) nur wäre mehr wie folgt Aussehen:

int sum = 0;
int i = 0;
for ( ; i < (5 & ~(4-1)); i += 4) /* unrolling 4 iterations */
{
    sum+=(i+0);
    sum+=(i+1);
    sum+=(i+2);
    sum+=(i+3);
}
for ( ; i < 5; i++)
{
    sum+=i;
}

Aber es gibt viele Möglichkeiten für den compiler, um noch weitere Optimierungen hier, dies ist nur ein Schritt.