RISC-V 实现无分支的离散函数

Question

考虑在集合 {-3, -2, -1, 0, 1, 2, 3} 中的整数上定义的离散值函数 f。定义：

f(-3) = 6
f(-2) = 61
f(-1) = 17
f(0) = -38
f(1) = 19
f(2) = 42
f(3) = 5

我正在尝试在 RISC V 中实现一个函数“f”，它不使用分支也不使用跳转来评估函数。 a0 将是 f 中要计算的值，[本质上是： f(a0) ]，而 a1 将指向输出数组的地址（参见下面的代码）。

到目前为止我的代码：

.globl f

.data
neg3:   .asciiz "f(-3) should be 6, and it is: "
neg2:   .asciiz "f(-2) should be 61, and it is: "
neg1:   .asciiz "f(-1) should be 17, and it is: "
zero:   .asciiz "f(0) should be -38, and it is: "
pos1:   .asciiz "f(1) should be 19, and it is: "
pos2:   .asciiz "f(2) should be 42, and it is: "
pos3:   .asciiz "f(3) should be 5, and it is: "

output: .word   6, 61, 17, -38, 19, 42, 5
.text
main:
    la a0, neg3
    jal print_str
    li a0, -3
    la a1, output
    jal f               # evaluate f(-3); should be 6
    jal print_int
    jal print_newline

    la a0, neg2
    jal print_str
    li a0, -2
    la a1, output
    jal f               # evaluate f(-2); should be 61
    jal print_int
    jal print_newline

    la a0, neg1
    jal print_str
    li a0, -1
    la a1, output
    jal f               # evaluate f(-1); should be 17
    jal print_int
    jal print_newline

    la a0, zero
    jal print_str
    li a0, 0
    la a1, output
    jal f               # evaluate f(0); should be -38
    jal print_int
    jal print_newline

    la a0, pos1
    jal print_str
    li a0, 1
    la a1, output
    jal f               # evaluate f(1); should be 19
    jal print_int
    jal print_newline

    la a0, pos2
    jal print_str
    li a0, 2
    la a1, output
    jal f               # evaluate f(2); should be 42
    jal print_int
    jal print_newline

    la a0, pos3
    jal print_str
    li a0, 3
    la a1, output
    jal f               # evaluate f(3); should be 5
    jal print_int
    jal print_newline

    li a0, 10
    ecall

# f takes in two arguments:
# a0 is the value we want to evaluate f at
# a1 is the address of the "output" array (defined above).
# 
f:
    
    #store the value of a0 in temp register
    add t0, a0, x0
    
    #store numerical value to get correct output index
    addi t1, x0, 3
    
    #add the numerical value 3 to the argument value 
    #to get the correct output array index value
    add t2, t1, t0
    
    #store size of int
    addi t3, x0, 4
    
    #index the output array
    mul t4, t2, t3
    add t4, t4, t2
    
    lw ra, 0(t4)
    

    jr ra            

print_int:
    mv a1, a0
    li a0, 1
    ecall
    jr    ra

print_str:
    mv a1, a0
    li a0, 4
    ecall
    jr    ra

print_newline:
    li a1, '\n'
    li a0, 11
    ecall
    jr    ra

很明显，将值 3 添加到传入的参数 a0 将正确索引到输出数组。我不确定我在代码中是否正确执行了此操作，并且需要一些建议。

Answer 1

我可以在您的实现中发现两个错误

:

```
add t4, t4, t2
```
：在这里，您将数组
```
t4 = (a0 + 3) * 4
```
中的地址偏移量添加到数组中的索引（
```
t2 = a0 + 3
```
），而您想要添加偏移量和数组指针（
```
a1
```
）：
```
add t4, t4, a1
```
。
```
lw ra, 0(t4)
```
：这里将数组中的值加载到return a地址寄存器
```
ra
```
，该寄存器保存调用函数中要跳回（返回）的指令的地址，并且是由
```
jr ra
```
使用。
相反，您希望将值加载到
```
a0
```
，这是规范的返回值寄存器：
```
lw a0, 0(t4)
```
。

有一些可能的改进：

    #store the value of a0 in temp register
    add t0, a0, x0

    #store numerical value to get correct output index
    addi t1, x0, 3
    
    #add the numerical value 3 to the argument value 
    #to get the correct output array index value
    add t2, t1, t0

没有理由将
```
a0
```
复制到
```
t0
```
，只需在最后一条指令中直接使用
```
a0
```
即可。
也没有理由将立即值
```
3
```
加载到
```
t1
```
中，只需将最后一条指令变成
```
addi
```
即可。

结合起来，以上三个指令的替代是以下一个指令：

    # add 3 to argument value
    addi t2, a0, 3

还有更多：

    #store size of int
    addi t3, x0, 4
    
    #index the output array
    mul t4, t2, t3
    add t4, t4, a1     # t2 replaced by a1, see above

您可能已经注意到，没有

muli

指令，因此在相乘之前必须将立即数

加载到寄存器

t3

中。
此外，

mul

是M扩展的一部分（并非所有处理器都支持），乘法通常是一个复杂、缓慢的操作。

因此，我建议用左移 2 代替乘以 4，这利用了整数的二进制表示并产生相同的结果 - 至少对于无符号值而言。
计算出的索引应始终为

>= 0

，因此这是安全的。

有一条左移立即指令

slli

，它是所有基本 RISC-V ISA 的一部分，移位通常比乘法更快。
上面的三个指令可以用两个指令代替：

    # index the output array
    # (multiply by 4 / left shift by 2, then add array address)
    slli t4, t2, 2
    add  t4, t4, a1     # t2 replaced by a1, see above

现在结合所有错误修复和改进，整个功能仅需要五个指令而不是八个：

# a0: argument value ; a1: array address
f:
    # add 3 to argument value
    addi t2, a0, 3

    # index the output array
    # (multiply by 4 / left shift by 2, then add array address)
    slli t4, t2, 2
    add  t4, t4, a1     # t2 replaced by a1, see above

    # load value from output array
    lw a0, 0(t4)        # ra replaced by a0, see above

    # return to calling function
    jr ra

现在，让我们最后看看当我们给它提供在 C 中实现的相同函数时，像 clang 11 这样具有优化功能的现代编译器可以产生什么（godbolt.org）：

#include <stdint.h>
int32_t f(int32_t a0, int32_t a1[]) {
    return a1[a0 + 3];
}

这是我添加的一些评论的结果：

f:
    # multiply argument value by 4
    slli a0, a0, 2

    # add array address
    add  a0, a0, a1

    # load array value at three places (= 12 bytes) further
    lw   a0, 12(a0)

    # return to calling function
    ret

这只是四个指令，我们来讨论一下：

```
ret
```
只是
```
jr ra
```
的简写符号，与我们的相同。
寄存器
```
a0
```
被所有指令重复使用。这是完全合法的。
使用
```
a0
```
的好处是该寄存器可由 C 扩展的压缩指令使用。
```
tN
```
寄存器不能。
编译器使用了我建议的相同技巧，将
```
addi
```
和
```
mul
```
替换为
```
slli
```
。
首字母
```
addi t2, a0, 3
```
缺失。
相反，编译器在内部将常量
```
3
```
和
```
4
```
相乘，并使用结果值
```
12
```
作为
```
lw a0, 12(a0)
```
中的立即值。
原来的地址计算是
```
(a0 + 3) * 4 + a1
```
。编译器将其转换为
```
a0 * 4 + a1 + 12
```
，这是等效的。然后将
```
12
```
的加法移至
```
lw
```
指令的地址生成步骤，从而保存
```
addi
```
指令。

RISC-V 实现无分支的离散函数

问题描述投票：0回答：1

1个回答

最新问题

RISC-V 实现无分支的离散函数

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1