汇编中的冗余值复制？
Redundant value copying in assembly?
我正在从 Programming Ground Up 书中学习 x86 汇编。在介绍函数时，作者给出了一个函数的例子，该函数将给定的 4 字节整数提高到大于 0 的幂。函数的定义如下（这是我写的版本，但代码几乎相同）：
1. .type find_pow, @function
2. find_pow:
3. pushl %ebp # Save current base pointer
4. movl %esp, %ebp # Copy stack pointer to base pointer
5. movl , %eax # %eax will hold the result, set it to 1
6.
7. subl , %esp
8. movl 8(%ebp), %ebx
10. movl 12(%ebp), %ecx
11.
12. movl %ebx, -4(%ebp)
13.
14. loop_find_pow: # Start loop
15. cmpl , %ecx # If 2nd parameter equals 0
16. je exit_find_now # Exit loop
17. movl -4(%ebp), %eax # Move current result to %eax
18. imull %ebx, %eax # Multiply to current value of %eax
19. movl %eax, -4(%ebp) # Store current result
20. decl %ecx # Decrease %ecx
21. jmp loop_find_pow # Jump to loop top
22.
23. exit_find_now:
24. movl -4(%ebp), %eax
25. movl %ebp, %esp
26. popl %ebp
27. ret
我完全理解代码，但对作者为什么要在第 17...19 行做他正在做的事情有点困惑。首先，局部变量的值从栈中复制到%eax。然后使用 %eax 完成计算（我想这是出于性能原因？），然后将计算出的值存储回分配给唯一局部变量的 space。我不明白为什么需要所有这些复制。无论如何，调用者通过检查 %eax 寄存器获得 return 值。完全消除局部变量的使用（地址 -4(%ebp)?
没有意义吗？
编辑：如果有人想看书中的原始代码，请浏览到第 67 页。
Doesn't it make sense to completely eliminate use of the local variable (at address -4(%ebp)?
是的。
因为 eax 是一个 volatile 寄存器（由 ABI 定义），函数不需要保留其原始值。
这种简单的算法可以将其所有状态保存在寄存器中，而不必将它们溢出到堆栈中。
但是，这是一个简单的示例，旨在进行教学；它演示的一件事是当你没有足够的寄存器时如何使用堆栈变量。
您的版本破坏了调用者的 ebx 值。该寄存器在 i386 System V ABI（Linux 使用）中被调用保留。选择不同的 tmp reg，例如 EDX。
EAX、ECX 和 EDX 在所有标准的 32 位调用约定中都被调用破坏，因此这些是您可以在没有 saving/restoring.[=52= 的情况下临时使用 space 的寄存器]
Then the computation is done using %eax (I suppose this is for performance reasons?
不，这是因为 imul 没有内存目标编码，只有 r/m 源。
如果您关心性能，就不会将 store/reload 延迟引入您正在计算的产品的依赖链中。即使将循环计数器保留在内存中也会更好（至少对于大量计数），因为 dec 延迟比 imul 延迟短。
在您的循环中，每次迭代的一个输入来自上一次迭代。 store/load/imul / store/load/imul / ... 的总延迟是乱序执行 CPU 循环的瓶颈（所有当前的 x86 CPU 都是这样).存储转发使 store/reload 只有大约 5 个周期，但这仍然比大多数 CPU 上的 imul 延迟长。
如果您 运行 寄存器不足并希望将其中一个变量保留在内存中，通常更喜欢溢出一个只在循环内读取而不写入的变量。多次重新读取相同的内存位置是可以的。
在 compiler/optimization 术语中，"spilling" 来自寄存器的变量是指当您无法将其保存在寄存器中而不是将其存储到内存中时。
例如imul 8(%ebp), %eax 作为你的循环体。
- 你不需要 tmp reg 来加载+操作内存中的值，你只需要一个计数器 + 累加器。
- 循环携带的依赖链只有 imul -> imul -> imul ... 关键路径。
您也不需要复制到 -4(%ebp)，您可以只修改 8(%ebp) 内存中已有此变量的位置。
根据调用约定，您 "own" 您的堆栈参数并且可以修改您的变量副本。所以即使你确实想修改内存中的值，你仍然不需要复制它。
你的循环结构也很低效，尽管 imul 的 3 周期延迟（或更早一些更旧的 CPUs）很容易隐藏 运行ning all 的开销这些额外的指令与循环底部的简单 dec %ecx / jnz loop_find_pow 相比。
查看函数的 C 版本的优化编译器输出！
(更新：这可以进一步简化 因为我们保证 n>0。所以我们可以直接使用 do{}while(--n); 循环结构。我最初在问题中遗漏了这一点，并将简化作为 reader 的练习。）
unsigned find_pow(unsigned x, unsigned n) {
unsigned tot = x; // or should this be 1? Possible off-by-1 error
for(; n ; n--) { // gcc fails to convert i=0 ; i<n ; i++ into a down-count
tot *= x;
}
return tot;
}
海湾合作委员会 9.1 -O3 -m32 -fno-tree-vectorize -march=skylake on Godbolt
find_pow:
movl 4(%esp), %ecx
movl 8(%esp), %eax
movl %ecx, %edx
testl %eax, %eax # if(n==0) return
je .L1
.L3: # do{
imull %ecx, %edx
decl %eax
jne .L3 # }while(--n);
.L1:
movl %edx, %eax # silly compiler, should have used tot=EAX in the first place
ret
clang 展开（除非您使用 -fno-unroll-loops）。但它没有为产品使用多个累加器来隐藏 imul 延迟 /facepalm。 imul 是流水线，比现代 x86 CPUs 上的延迟具有更好的吞吐量，通常为 3 周期延迟/1 周期吞吐量。参见 https://agner.org/optimize/。
但是 clang 只是在它的主循环中重复了 imul %ecx, %eax 8 次，这基本上是没有用的。并行乘以 %edx 和 %eax，然后在最后乘以它们，将使 imul 运行 的两个链并行。至少使用 3 个寄存器以获得较大 n 的最佳性能。但是 n 的实际值相对较小（即使 2**32 也会溢出 32 位整数），因此大 n 优化只有在您想使用它来获得(x**n) % (2**32).
的低位
我认为即使在 2^32 处环绕也是安全的优化。如果可用 (-march=skylake)，GCC 使用 AVX2 vpmulld 自动矢量化，如果整数乘法不是关联的，这将是不安全的。
当使用 -ffast-math 优化 FP 循环时，Clang 确实会展开多个累加器（使其将 FP add/mul 视为关联），所以很糟糕，它没有用整数数学来做。如果编译器没有意识到 n 可能通常很小，则按 8 展开才有意义，因此如果 clang 要针对大 n 进行优化，请正确执行并隐藏 imul 延迟.
当使用 AVX2 进行自动矢量化时，clang 确实做到了这一点，并并行使用了 4 个总计矢量。但是 vpmulld 在 Haswell/Skylake 上有 10 个周期延迟并且 clang 展开 32，而不仅仅是 4。似乎太多了。
我正在从 Programming Ground Up 书中学习 x86 汇编。在介绍函数时，作者给出了一个函数的例子，该函数将给定的 4 字节整数提高到大于 0 的幂。函数的定义如下（这是我写的版本，但代码几乎相同）：
1. .type find_pow, @function
2. find_pow:
3. pushl %ebp # Save current base pointer
4. movl %esp, %ebp # Copy stack pointer to base pointer
5. movl , %eax # %eax will hold the result, set it to 1
6.
7. subl , %esp
8. movl 8(%ebp), %ebx
10. movl 12(%ebp), %ecx
11.
12. movl %ebx, -4(%ebp)
13.
14. loop_find_pow: # Start loop
15. cmpl , %ecx # If 2nd parameter equals 0
16. je exit_find_now # Exit loop
17. movl -4(%ebp), %eax # Move current result to %eax
18. imull %ebx, %eax # Multiply to current value of %eax
19. movl %eax, -4(%ebp) # Store current result
20. decl %ecx # Decrease %ecx
21. jmp loop_find_pow # Jump to loop top
22.
23. exit_find_now:
24. movl -4(%ebp), %eax
25. movl %ebp, %esp
26. popl %ebp
27. ret
我完全理解代码，但对作者为什么要在第 17...19 行做他正在做的事情有点困惑。首先，局部变量的值从栈中复制到%eax。然后使用 %eax 完成计算（我想这是出于性能原因？），然后将计算出的值存储回分配给唯一局部变量的 space。我不明白为什么需要所有这些复制。无论如何，调用者通过检查 %eax 寄存器获得 return 值。完全消除局部变量的使用（地址 -4(%ebp)?
编辑：如果有人想看书中的原始代码，请浏览到第 67 页。
Doesn't it make sense to completely eliminate use of the local variable (at address -4(%ebp)?
是的。
因为 eax 是一个 volatile 寄存器（由 ABI 定义），函数不需要保留其原始值。
这种简单的算法可以将其所有状态保存在寄存器中，而不必将它们溢出到堆栈中。
但是，这是一个简单的示例，旨在进行教学；它演示的一件事是当你没有足够的寄存器时如何使用堆栈变量。
您的版本破坏了调用者的 ebx 值。该寄存器在 i386 System V ABI（Linux 使用）中被调用保留。选择不同的 tmp reg，例如 EDX。
EAX、ECX 和 EDX 在所有标准的 32 位调用约定中都被调用破坏，因此这些是您可以在没有 saving/restoring.[=52= 的情况下临时使用 space 的寄存器]
Then the computation is done using
%eax(I suppose this is for performance reasons?
不，这是因为 imul 没有内存目标编码，只有 r/m 源。
如果您关心性能，就不会将 store/reload 延迟引入您正在计算的产品的依赖链中。即使将循环计数器保留在内存中也会更好（至少对于大量计数），因为 dec 延迟比 imul 延迟短。
在您的循环中，每次迭代的一个输入来自上一次迭代。 store/load/imul / store/load/imul / ... 的总延迟是乱序执行 CPU 循环的瓶颈（所有当前的 x86 CPU 都是这样).存储转发使 store/reload 只有大约 5 个周期，但这仍然比大多数 CPU 上的 imul 延迟长。
如果您 运行 寄存器不足并希望将其中一个变量保留在内存中，通常更喜欢溢出一个只在循环内读取而不写入的变量。多次重新读取相同的内存位置是可以的。
在 compiler/optimization 术语中，"spilling" 来自寄存器的变量是指当您无法将其保存在寄存器中而不是将其存储到内存中时。
例如imul 8(%ebp), %eax 作为你的循环体。
- 你不需要 tmp reg 来加载+操作内存中的值，你只需要一个计数器 + 累加器。
- 循环携带的依赖链只有 imul -> imul -> imul ... 关键路径。
您也不需要复制到 -4(%ebp)，您可以只修改 8(%ebp) 内存中已有此变量的位置。
根据调用约定，您 "own" 您的堆栈参数并且可以修改您的变量副本。所以即使你确实想修改内存中的值，你仍然不需要复制它。
你的循环结构也很低效，尽管 imul 的 3 周期延迟（或更早一些更旧的 CPUs）很容易隐藏 运行ning all 的开销这些额外的指令与循环底部的简单 dec %ecx / jnz loop_find_pow 相比。
查看函数的 C 版本的优化编译器输出！
(更新：这可以进一步简化 因为我们保证 n>0。所以我们可以直接使用 do{}while(--n); 循环结构。我最初在问题中遗漏了这一点，并将简化作为 reader 的练习。）
unsigned find_pow(unsigned x, unsigned n) {
unsigned tot = x; // or should this be 1? Possible off-by-1 error
for(; n ; n--) { // gcc fails to convert i=0 ; i<n ; i++ into a down-count
tot *= x;
}
return tot;
}
海湾合作委员会 9.1 -O3 -m32 -fno-tree-vectorize -march=skylake on Godbolt
find_pow:
movl 4(%esp), %ecx
movl 8(%esp), %eax
movl %ecx, %edx
testl %eax, %eax # if(n==0) return
je .L1
.L3: # do{
imull %ecx, %edx
decl %eax
jne .L3 # }while(--n);
.L1:
movl %edx, %eax # silly compiler, should have used tot=EAX in the first place
ret
clang 展开（除非您使用 -fno-unroll-loops）。但它没有为产品使用多个累加器来隐藏 imul 延迟 /facepalm。 imul 是流水线，比现代 x86 CPUs 上的延迟具有更好的吞吐量，通常为 3 周期延迟/1 周期吞吐量。参见 https://agner.org/optimize/。
但是 clang 只是在它的主循环中重复了 imul %ecx, %eax 8 次，这基本上是没有用的。并行乘以 %edx 和 %eax，然后在最后乘以它们，将使 imul 运行 的两个链并行。至少使用 3 个寄存器以获得较大 n 的最佳性能。但是 n 的实际值相对较小（即使 2**32 也会溢出 32 位整数），因此大 n 优化只有在您想使用它来获得(x**n) % (2**32).
我认为即使在 2^32 处环绕也是安全的优化。如果可用 (-march=skylake)，GCC 使用 AVX2 vpmulld 自动矢量化，如果整数乘法不是关联的，这将是不安全的。
当使用 -ffast-math 优化 FP 循环时，Clang 确实会展开多个累加器（使其将 FP add/mul 视为关联），所以很糟糕，它没有用整数数学来做。如果编译器没有意识到 n 可能通常很小，则按 8 展开才有意义，因此如果 clang 要针对大 n 进行优化，请正确执行并隐藏 imul 延迟.
当使用 AVX2 进行自动矢量化时，clang 确实做到了这一点，并并行使用了 4 个总计矢量。但是 vpmulld 在 Haswell/Skylake 上有 10 个周期延迟并且 clang 展开 32，而不仅仅是 4。似乎太多了。