c - 循环展开优化，这是如何工作的

Question

考虑这个 C 代码:

int sum=0;
for(int i=0;i<5;i++)
    sum+=i;

这可以在(伪)汇编中以这种方式翻译(没有循环展开):

% pseudo-code assembly
ADDI $R10, #0   % sum
ADDI $R11, #0   % i
LOOP:
ADD $R10, $R11
ADDI $R11, #1
BNE $R11, #5 LOOP

所以我的第一个问题是如何使用循环展开在这两种方式之间转换这段代码:

1)

ADDI $R10, #0
ADDI $R10, #0
ADDI $R10, #1
ADDI $R10, #2
ADDI $R10, #3
ADDI $R10, #4

2)

   ADD $R10, #10

编译器是否能够优化代码并直接知道它必须加 10 而无需执行所有求和？

还有，有没有可能用分支指令阻塞流水线？我必须这样写吗:

% pseudo-code assembly
ADDI $R10, #0   % sum
ADDI $R11, #0   % i
LOOP:
ADD $R10, $R11
ADDI $R11, #1
NOP   % is this necessary to avoid the pipeline blocking?
NOP
NOP
NOP
BNE $R11, #5 LOOP

为了避免 fetch-decode-exe-mem-write back 循环被分支打断？

Answer 1

这更多是为了展示编译器的能力，而不是每个编译器都会做的事情。来源:

#include <stdio.h>

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

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

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

请注意我添加的 printf。如果不使用该变量，编译器将优化整个循环。

使用 -O0 编译(无优化)

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

循环以“愚蠢”的方式发生，-8(%rbp) 是变量 i。

使用 -O1(优化级别 1)编译

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

movl    $10, %edx

循环已被完全删除并替换为等效值。

---

在展开时，编译器查看会发生多少次迭代，并尝试通过执行较少的迭代来展开。例如，循环体可能被复制两次，这将导致分支数减半。 C中的这种情况:

int i = 0, sum = 0;

sum += i;
i++;

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

请注意，必须从循环中提取一次迭代。这是因为 5 是奇数，所以不能简单地通过复制内容来减半工作量。在这种情况下，循环只会进入两次。 -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)

在 C 中完全展开:

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

这次循环实际上只进入了一次。使用 -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