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

Question

我正在尝试学习一些基本的x86程序集，因此我已经开始解决Project问题。我希望对我的代码进行一些批评，希望它包括操作的效率或代码本身的可读性/风格。我将为Linux 64位提供Makefile。

代码的目的是将[0,1000)中所有可被3或5整除的数字相加。

代码可以使用make RUN=euler_1运行。

注：

我知道，大多数编译器使用mov和shr的某种组合来替换已知数字的模块，以避免整数除法。例如，请参见这条线。

Makefile

.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

euler_1.1.asm

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

Answer 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作为运行和呢？

知道如何有效地使寄存器

为零。

显然，如果我们编写mov r8, 0，它具有将值0加载到r8寄存器中的预期效果，正如其他评论所指出的那样，有更好的方法可以做到这一点，但让我们更深入地研究一下。目前的守则是这样做的：

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

这是可行的，但是让我们看看清单文件，看看NASM把它变成了什么：

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

第一列只是列表文件的行号，第二列是地址，第三列是编码指令。所以我们看到这两个指令使用了11个字节。我们可以做得更好！另一篇评论正确地提到了xor指令，所以让我们尝试一下：

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

更好，只有六个字节。我们还能做得更好。正如其中一个注释所正确指出的，在64位x86机器上，如果您xor一个rXX寄存器的下半部分，它也会清除上半部分。所以让我们这样做：

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

它保存了一个字节，但是没有e8寄存器。通过清除ecx，然后将该值复制到r8中，我们能做得更好吗？

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

不，我们不能这样做，除非我们也遵循上面的建议，使用rsi而不是r8：

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

现在我们减少到4个字节，我们不再需要mov rsi, r8指令，它可以节省另外3个字节，这样就可以节省10个字节了。

避免使用div如果实际使用

div指令是x86_64体系结构中最慢的指令之一，如果我们试图将其除以零，也会导致异常。出于这两方面的原因，如果可以的话，最好避免使用指令。在这种情况下，避免这种情况的一种方法是注意到它看起来很像fizzbuzz，并保留了两个计数器:一个从5开始计数，另一个从3计数。

在实际的

中使用本地标签

很明显，main需要成为文件的全局符号，但是for0和if01 (都是糟糕的名称，正如已经注意到的那样)不需要这样做。在NASM中，我们可以通过在这些标签前加上一个句号来指定本地标签，所以我们可以使用.for0代替for0。这样做的好处是我们可以在另一个函数中重用一个标签，而不必担心冲突。

避免在实际的

中无条件跳转

x86处理器尽力找出接下来将执行哪条指令。它有各种各样的事情要实现，包括多级缓存和分支预测。这样做是为了让软件运行得更快。你可以通过在实际情况下避免分支来帮助它，特别是避免无条件的跳跃。仔细考虑一下，我们通常可以通过重构代码来做到这一点。这是原始代码：

        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

我们可以这样改写：

        test rdx, rdx
        je  .accumulate
        ; i % 5 == 0
        mov rax, rcx
        mov rdx, 0
        mov r9, 5
        div r9
        test rdx, rdx
        jne .next
.accumulate:
        ; sum = sum + i
        add rsi, rcx
        ; }
.next:
        inc rcx
        cmp rcx, 1000
        jl  .for0

Answer 2

• if01和if0并不是最伟大的名字。
• 不要重新加载r9，而是使用两个寄存器。让r9总是包含3，而r10总是包含5。
• 在一个地方增加r8。
• 向下运行循环(1000到0)，而不是向上运行，只需要一个指令(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

我希望你知道这个问题有一个非常直截了当的算术解。

Answer 3

关于您的实现选择，以及我如何处理它，请做一些简短的说明：

您不需要64位操作数大小的div，当您的数字只上升到1000，这是明显慢于英特尔在冰湖之前的div r32：我解释了详细的另一个代码审查：在NASM Win64 64程序集中检查数字是否为素数。

(一般情况下，对于其他指令，test edx, edx会将代码大小保存在那里。即使使用64位数字和64位div，i % 5也总是适合32位，所以忽略高32位是安全的。参见在x86-64中使用32位寄存器/指令的优点 -它是x86-64的默认操作数大小，不需要任何机器代码前缀。为了提高效率，除非您实际需要64位操作数大小来执行特定的指令，否则使用它，而对64位的隐式零扩展不能满足您的需要。不过，不要花费额外的指令；通常需要64位操作数大小，例如指针增量。)

当然，对于编译时常量除法而言，div是编译器完全避免的慢速选项，而是使用定点乘法逆。就像GCC为什么用奇数乘法来实现整数除法？ on SO，或者此代码评审。

此外，如果使用向下计数器，当它们按0(和/或展开)处理3，5模式时，这些计数器重置为3或5，如FizzBuzz --请参阅这个堆栈溢出回答，我在这里编写了一篇关于此类技术的大型教程，我将在这里不再重复。与FizzBuzz不同的是，即使数字是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部分，要么使用循环并记住结果。( Euler项目不仅是编程，也是数学；这取决于你想做多少数学，取决于你希望你的程序做多少蛮力。)

方便地说，8恰好是x86寻址模式支持的规模因素之一，所以我们甚至可以这样做。

lea eax, [rax + rcx*8 + 0 + 3 + 5 + 6 + 9 + 10 + 12]

(3+5+6+...是一个常量表达式，因此汇编程序可以在组装时为您完成它，从而生成[reg + reg*scale + disp8]寻址模式。不幸的是，3组件LEA在Intel CPU上有三周期延迟，而循环携带依赖将成为循环的瓶颈。因此，使用单独的add指令实际上更有效。)

当然，我们已经把它简化为线性增长级数的和，可以用高斯公式(n * (n+1) / 2)来表示在整个区间范围内的封闭形式，只需要处理接近n的数的n%15清理。顺便说一下，clang知道如何将执行sum += i;的简单for循环转换为封闭形式，在除以2 (右移位)之前，对其进行排列以避免临时循环溢出。马特·戈德波特的“CppCon2017 talk “我的编译器最近为我做了什么？”打开编译器的盖子“”以此为例。另见https://stackoverflow.com/questions/38552116/how-to-remove-noise-from-gcc-clang-assembly-output