x86-64汇编-3或5的倍数之和

.PHONY: clean

all:    $(RUN).elf
    ./$^

%.elf:  %.o 
    ld $^ -o $@ -lc -e main -dynamic-linker /lib64/ld-linux-x86-64.so.2

%.o:    %.asm
    nasm -f elf64 $^

clean:
    rm -f *.o *.elf

extern printf
global main

section .data
fmt: db "%d", 0x0a, 0

section .text
    
;; main - Calculate the sum of all numbers between [0, 1000) that are divisible
;; by 3 or 5.
;;  sum : R8
main:   
    ; sum = 0
    mov r8, 0   
    ; for i in [0, 1000) {
    mov rcx, 0
for0:   
    ; if i % 3 == 0 or i % 5 == 0 {

    ; i % 3 == 0
    mov rax, rcx
    mov rdx, 0
    mov r9, 3
    div r9
    test rdx, rdx
    jne if01
    ; sum = sum + i
    add r8, rcx
    jmp if0

if01:
    ; i % 5 == 0
    mov rax, rcx
    mov rdx, 0
    mov r9, 5
    div r9
    test rdx, rdx
    jne if0
    ; sum = sum + i
    add r8, rcx
    jmp if0
    ; }
if0:
    inc rcx
    cmp rcx, 1000
    jl  for0
    ; }
    
    ; printf("%d", sum)
    lea rdi, [rel fmt]
    mov rsi, r8
    mov rax, 0
    call printf
    
    ; sys_exit(0)
    mov rdi, 0
    mov rax, 60
    syscall

#1 楼

以下是一些可以帮助您改进代码的事情。另一个评论提出了一些好的观点，但是这里还没有涵盖。
确定是否使用stdlib
Makefile和对printf的调用都表明您正在使用标准C库。 ，这很好，但是程序使用syscall终止，但不是。原因是标准C启动程序在调用main之前先进行设置，然后在main返回后再次将其拆解。此代码通过使用syscall结束程序来跳过删除操作，这不是一个好习惯。有两种选择：要么根本不使用C库（也就是说，编写您自己的打印例程），要么让拆解实际上发生：

xor eax, eax    ; set exit code to 0 to indicate success
ret             ; return to _libc_start_main which called our main

进一步了解启动和拆解的方式在Linux中工作时，请仔细阅读此内容。
小心地管理寄存器
专业的汇编语言程序员（和好的编译器）要做的一件事就是管理寄存器的使用。在这种情况下，总和的最终用途是打印出来，而要打印出来，我们需要rsi寄存器中的值。那么为什么不使用rsi而不是r8作为运行总和呢？正如其他评论所指出的，有更好的方法可以做到这一点，但让我们更深入地了解一下。该代码当前执行此操作：

; sum = 0
mov r8, 0   
; for i in [0, 1000) {
mov rcx, 0

可以，但是让我们看一下清单文件，以了解NASM将其转换为的内容：列表文件的编号，第二个是地址，第三个是编码指令。因此，我们看到这两个指令使用11个字节。我们可以做得更好！另一则评论正确地提到了mov r8, 0指令，因此让我们尝试一下：

13                                      ; sum = 0
14 00000000 41B800000000                mov r8, 0   
15                                      ; for i in [0, 1000) {
16 00000006 B900000000                  mov rcx, 0

更好，只有六个字节。我们还能做得更好。正如正确注释的注释之一所示，在64位x86机器上，如果您对r8寄存器的下半部分进行xor，则它也会清除上半部分。因此，我们要这样做：

19 00000000 4D31C0                          xor     r8, r8
20 00000003 4831C9                          xor     rcx, rcx

保存了一个字节，但是没有xor寄存器。我们可以通过清除rXX然后将该值复制到e8来做得更好吗？

19 00000000 4D31C0                          xor     r8, r8
20 00000003 31C9                            xor     ecx, ecx

不，我们不能，除非我们也遵循上述建议并使用ecx而不是r8：

14 00000000 31C9                            xor     ecx, ecx
20 00000002 4989C8                          mov     r8, rcx

现在我们减少到4个字节，我们不再需要rsi指令，该指令可以为我们节省另外3个字节，仅用这两项就可以节省10个字节。
如果可行，请避免使用r8
mov rsi, r8指令是x86_64架构上最慢的指令之一，如果尝试除以零，也可能导致异常。由于这两个原因，通常最好避免这样做。在这种情况下，一种避免出现这种情况的方法是，注意它看起来很像div，并保留两个计数器：一个从5开始递减计数，另一个从3开始递减计数。
在可行的地方使用本地标签
很明显，div必须是文件全局符号，但不需要fizzbuzz和main（这两个名字都很差）。在NASM中，我们可以通过在标签前面加上一个句点来指定本地标签，因此可以使用for0代替if01。这样做的好处是我们可以在另一个函数中重用标签，而不必担心冲突。
在可行的情况下避免无条件跳转
x86处理器会尽力找出下一步将执行的指令。它有各种各样的方法可以实现，包括多级缓存和分支预测。这样做是为了使软件运行更快。您可以通过在可行时完全避免分支，特别是通过避免无条件跳转来帮助实现此目的。仔细考虑一下，我们通常可以通过重组代码来做到这一点。这是原始代码：

19 00000000 31C9                            xor     ecx, ecx
20 00000002 31F6                            xor     esi, esi

我们可以这样重写：

        test rdx, rdx
        jne if01
        ; sum = sum + i
        add rsi, rcx
        jmp if0

if01:
        ; i % 5 == 0
        mov rax, rcx
        mov rdx, 0
        mov r9, 5
        div r9
        test rdx, rdx
        jne if0
        ; sum = sum + i
        add rsi, rcx
        jmp if0
        ; }
if0:
        inc rcx
        cmp rcx, 1000
        jl  for0

#2 楼

if01和if0不是最大的名字。

而不是重新加载r9，请使用两个寄存器。让r9始终包含3，而r10始终包含5。


将r8递增到一个位置。 ），而不是向上保留指令（cmp）。


mov rdx, 0编码为7个字节。 xor rdx, rdx的长度要短得多。


所有这些，请考虑

main:
    mov r8, 0   
    mov r9, 3
    mov r10, 5

    ; for i in (1000, 0] 
    mov rcx, 999

for0:   
    mov rax, rcx
    xor rdx, rdx
    div r9
    test rdx, rdx
    jeq accumulate

    mov rax, rcx
    xor rdx, rdx
    div r10
    test rdx, rdx
    jne next

accumulate:
    add r8, rcx
next:
    dec rcx
    jne  for0

PS：我希望您知道这个问题具有非常简单的算术解决方案。 >

#3 楼

关于实现选择以及如何实现的一些简要说明：
当数字仅增加到1000时，div不需要64位操作数大小，这比Intel的div r32慢得多在Ice Lake之前：我在另一份代码审查中解释了详细信息：检查数字在NASM Win64汇编程序中是否为素数。
（通常，对于其他说明，test edx, edx会在此处保存代码大小。即使使用64位数字和64位div，i % 5始终适合32位，因此可以安全地忽略高32位。请参阅
在x86-64中使用32位寄存器/指令的优点-它是x86-64的默认操作数大小，不需要任何机器码前缀。为提高效率，除非确实需要该特定指令的64位操作数大小，并且隐式零扩展为64位将不能满足您的需要，否则请使用它。
Don不会花费额外的指令；通常需要64位操作数大小，例如用于指针增量。）
当然，对于除以编译时常数，div是一个慢速选项，编译器完全避免使用，而是使用定点乘法逆。就像在为什么GCC在实现整数除法中为什么使用乘以奇数的乘法？

此外，如果您使用倒数计数器，当它们达到0（和/或展开）时重置为3或5，则根本不需要除法。来处理3、5模式，例如FizzBu​​zz-请参阅此Stack Overflow答案，其中我编写了有关此类技术的大型教程，在此不再赘述。与FizzBu​​zz不同，即使数字是3和5的倍数，您也只希望计数一次。
您只需将数字展开15（这样模式就可以完全重复）并硬编码类似

.unroll15_loop:
                                    ; lets say ECX=60 for example
    add  eax, ecx                   ; += 60
    lea  eax, [rax + rcx + 3]       ; += 63
    lea  eax, [rax + rcx + 5]       ; += 65
    lea  eax, [rax + rcx + 6]       ; += 66
    ...
    add  ecx, 15
    cmp  ecx, 1000-15
    jbe  .unroll15_loop
   ; handle the last not full group of 15 numbers

或应用一些数学运算，而不是实际查看每个数字，请对15个数字范围内的3和5的倍数之和使用闭式公式，以i * nmuls偏移，其中i是范围的起点，而nmuls是倍数。
例如在[60, 75)范围内，我们有60、63、65、66、69、70、72。所以这是15个数字中的8个。所以就像[0, 15)但+ 8*60一样。手动或循环执行0..14部分，并记住结果。 （欧拉计画与算术一样关乎数学；取决于您想算多少数学还是想要算力多少。）
方便地，8恰好是比例-x86寻址模式支持的因素，因此我们甚至可以做到
（43 + 5 + 6 + ...是一个常量表达式，因此汇编器可以在汇编时为您完成此操作[reg + reg*scale + disp8]寻址模式。不幸的是，三分量LEA在Intel CPU上具有3个周期的延迟，并且循环依赖将成为循环的瓶颈。因此，使用单独的add指令实际上会更有效。 />当然，我们已经将其简化为线性增加的级数的和，并且可以对整个区间范围内的封闭形式应用高斯公式（n * (n+1) / 2），而只需要处理n%15接近n。顺便说一句，clang知道如何将sum += i;转换为闭合形式的简单for循环，将其安排为避免除以2之前的临时溢出（右移）。 Matt Godbolt在CppCon2017上的演讲“最近我的编译器为我做了什么？以解开编译器的盖子为例。另请参阅https://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output

#4 楼

在适当的地方使用条件移动指令
通过@Edward扩展答案中的讨论：如果可以使用条件移动指令，则将进一步减少分支的数量，从而帮助处理器。
如果结合使用建议保持模数3和模数5计数器而不是进行除法，则主循环主体的轮廓可能如下所示（但未经测试）：计数器的初始值为0，则需要将mod3_reg初始化为2，并将mod5_reg初始化为4。另一方面，如果调整为从1开始，则可以将两者都初始化为0，这样会更简单。） br />
还要注意，根据@PeterCordes的一些评论，cmov可能存在问题，从而在循环中创建了足够的额外依赖关系，以至于实际上可能不值得。在这种情况下，如果您非常关心性能，则在目标计算机上运行基准测试很重要。