使用 RISC-V 编程：如何为 Collatz 猜想编写更干净、不那么难看的代码？

Question

我想用 RISC-V 编写一个程序，在严格正整数上计算以下函数：

f(n) = f(n/2) if n is even
        f(3n+1) if n!=1 is odd
        1 if n=1

我们假设一个严格的正整数最初存储在寄存器

a0

中，作为程序的输入。

我想出了以下代码：

 li t1 1
 li t2 2
 li t3 3

test:
 andi t0 a0 1 
 beqz t0, iseven

isodd:
 beq a0, t1, exit
 mul a0, a0, t3
 add a0, a0, t1
 j test

iseven:
 div a0 a0 t2
 j test

exit:

也许这是正确的，但确实看起来很尴尬。我怀疑有一种更优雅的方式来编写它。例如，一开始的三个立即加载看起来很难看。而且条件分支看起来很丑。

如何改进上面的代码？我绝对是 RISC-V 的初学者。

Answer 1

这是一个用于测试 https://en.wikipedia.org/wiki/Collatz_conjecture 的函数 - 该函数未经证实，但没有人发现在重复应用这些步骤时最终不会收敛到

1

的数字。

---

您不需要

div

，只需右移 1。（相关：为什么用于测试 Collatz 猜想的 C++ 代码比手写汇编运行得更快？ 对于 x86）。 除法很慢，通常非常慢。 位移位速度很快，并且可以使用移位计数作为立即数操作数。 （正如我在问答中提到的，优化的编译器输出 (Godbolt) 对于查看足够简单的函数很有用。GCC 和 clang 都只设置一个常量

1

。该函数返回一个迭代计数； （或者如果一个数字没有收敛，将永远循环）。以减少不同陈述的工作混合在一起。）同样，你也不需要

需要

乘法；编译器通常会将

-O1

视为 -Og，因此使用 3 条指令而不是 2 条，但没有

3*n + 1

，并且仍然只有 2 个 ALU 操作的关键路径延迟（因为存在指令级并行性。）根据微架构，

 (n+1) + (n<<1)

可能相当便宜；与除法不同，部分乘积相加有很多固有的并行性，因此在问题上投入大量晶体管可以快速完成它。 但至少在高主频的CPU上，通常会有超过2个周期的延迟。 3 在现代 x86 中很常见。这样就摆脱了

mul

和

mul

常量，您可以像使用

2

一样使用

3

。不过，您确实需要在寄存器中使用

addi

作为循环退出条件，以检测序列何时收敛到

andi

。 RISC-V 比较和分支指令在相对位移上使用其所有位，没有用于立即比较的位。

底部有一个无条件的

1

；如果您以不同的方式安排循环，则可以将循环退出条件放在那里，这样您就不需要循环内的另一个分支。 （

为什么循环总是被编译成“do...while”风格（尾跳）？

） 1 所以这是一个

j

循环。  它有两个返回循环顶部的分支，就像循环尾部重复优化一样，但在其中一个分支中，我优化了 

.global collatz_test
collatz_test:            # function entry point
 li   t1, 1
 beq  a0, t1, exit       # or  j to the loop entry-point.
                         # or just fall into the loop and let it do 3*1 + 1 = 4
                          # then reach 1 with 2 more iterations.

testloop:              # do {
 andi   t0, a0, 1 
 beqz   t0, iseven

isodd:
 slli   t2, a0, 1        # x*2
 addi   a0, a0, 1        # x+1
 add    a0, a0, t2       # x*2 + x+1 = x*3 + 1
      # mul  a0, a0, t3
      # add  a0, a0, t1
 j testloop              # this can't produce a result of 1
                         # even if the x*=3 overflows, it can't clear the lowest set bit since 3 is odd.
                         # so non-zero x already has x*3 != 0

iseven:            # this *can* produce a 1 we need to check for
 slri   a0, a0, 1
 bne    a0, t1, testloop # }while(x != 1)

exit:
# ret   # if this was a function, not a whole program

循环条件，因此它只是一个

do{}while(x != 1)

。 否则我就不得不这么做x != 1