如何在Risc-V中使用递归?将c转换为Risc-V

我们有一个任务要将以下C代码转换为汇编：

#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
int ret;
while (a != b){
if (a > b){
ret = gcd(a - b, b);
return ret;
}
else{
ret = gcd(a , b - a);
return ret;
}
}
return a;
}
void main(void)
{
int a;
int b;
int c;

printf("a & b? ");
scanf(" %d %d",&a,&b );

c = gcd(a, b);
printf("result = %d",c);
}

求一个整数的最大公约数。我们必须把它翻译成汇编

.data
str1:    .ascii "result = "
str2:    .ascii "n"
.text
.global main
main:
addi sp,sp,-32 
sw  ra,28(sp)
sw  s0,24(sp)
addi s0,sp,32
call read_int
mv s0,a0    
call read_int
mv s1,a0    
mv a0,s0    #a0 = a
mv a1,s1    #a1 = b
call gcd
mv s1,a0
la a0,str1
call print_string
mv a0,s1
call print_int
la a0,str2
call print_string
lw  ra,28(sp)
lw  s0,24(sp)
addi    sp,sp,32
call show_pc
call exit
ret
gcd:
addi sp,sp,-8   # Increase stack w/ space for 1 int
sw s3,4(sp)     # push S0 to stack
sw s4,4(sp)
L1: beq a0,a1,L2    # if (a0==a1) go to L2
slt s4,a0,a1    # if (a<b) s1=1, else s4=0
beq s4,zero,L3  # if s4==0 go to L3
sub s3,a0,a1    # varRet(s3) = a-b
call gcd        # recursion
L3: sub s3,a1,a0    # varRet(s3) = b-a
call gcd        # recursion
beq zero,zero,L1 # jump to L1
L2: lw s3,4(sp)     # restore old s0
lw s4,4(sp)
addi sp,sp,4    # decrease stack
jr ra           # jump to ra

但是我在gcd函数的代码中遇到了一个数据保存错误。可能是因为我如何使用变量或结束函数。

如果您能理解如何做到这一点，我们将不胜感激。

Erik的回答解释了代码的错误。存在许多错误。我列出几个：

寄存器保存/恢复代码错误。两个都从4(sp)存储/加载，因此一个寄存器被破坏
还原代码中的addi错误--与保存代码不匹配
不保存/恢复返回地址(例如ra(。实际上，这是唯一需要保存/恢复的寄存器
对于递归调用，a0/a1(即a和b(从未改变
通常，返回值以v0为单位。这只是惯例，所以没什么大不了的
我们只需要一个额外的寄存器就可以得到slt的结果。按照惯例，这可以是一个t*寄存器[不需要保存/恢复]

请注意，在下面的代码中，我测试了修改后的C函数，但没有测试asm。

当我想写汇编程序时，我重写C代码，只使用if和goto，以更接近地模仿[建议的]汇编程序。

if只能是简单的(例如(if (a > b)和而不是if ((a > b) && (c < d))。后者必须拆分为简单的if(使用更多的goto(

int
gcd3(int a, int b)
{
int ret = a;
if (a == b)
goto done;
if (a > b)
goto a_gt_b;
a_lt_b:
ret = gcd(a, b - a);
goto done;
a_gt_b:
ret = gcd(a - b, b);
goto done;
done:
return ret;
}

以下是重构的asm代码：

gcd:
addi    sp,sp,-4                # Increase stack w/ space for 1 int
sw      ra,0(sp)                # save return address
add     v0,a0,zero              # ret = a
beq     a0,a1,done              # if (a == b) we are done
slt     t0,a0,a1                # is a > b?
beq     t0,zero,a_gt_b          # yes, fly
# a < b
a_lt_b:
sub     a1,a1,a0                # b = b - a
call    gcd                     # recursion
b       done
# a > b
a_gt_b:
sub     a0,a0,a1                # a = a - b
call    gcd                     # recursion
b       done
done:
lw      ra,0(sp)                # restore return address
addi    sp,sp,4                 # decrease stack
jr      ra                      # return

您的原始C代码结合了递归和循环元素。该函数实际上根本不需要是递归的。

这是一个循环版本：

int
gcd4(int a, int b)
{
loop:
if (a == b)
goto done;
if (a > b)
goto a_gt_b;
a_lt_b:
b = b - a;
goto loop;
a_gt_b:
a = a - b;
goto loop;
done:
return a;
}

这是汇编代码：

gcd:
beq     a0,a1,done              # if (a == b) we are done
slt     t0,a0,a1                # is a > b?
beq     t0,zero,a_gt_b          # yes, fly
# a < b
a_lt_b:
sub     a1,a1,a0                # b = b - a
b       gcd
# a > b
a_gt_b:
sub     a0,a0,a1                # a = a - b
b       gcd
done:
add     v0,a0,zero              # ret = a
jr      ra                      # return

这是我使用的完整测试C程序：

#include <stdio.h>
#include <stdlib.h>
int
gcd(int a, int b)
{
int ret;
while (a != b) {
if (a > b) {
ret = gcd(a - b, b);
return ret;
}
else {
ret = gcd(a, b - a);
return ret;
}
}
return a;
}
int
gcd2(int a, int b)
{
int ret = a;
while (a != b) {
if (a > b) {
ret = gcd(a - b, b);
break;
}
else {
ret = gcd(a, b - a);
break;
}
}
return ret;
}
int
gcd3(int a, int b)
{
int ret = a;
if (a == b)
goto done;
if (a > b)
goto a_gt_b;
a_lt_b:
ret = gcd(a, b - a);
goto done;
a_gt_b:
ret = gcd(a - b, b);
goto done;
done:
return ret;
}
int
gcd4(int a, int b)
{
loop:
if (a == b)
goto done;
if (a > b)
goto a_gt_b;
a_lt_b:
b = b - a;
goto loop;
a_gt_b:
a = a - b;
goto loop;
done:
return a;
}
int
main(void)
{
int a;
int b;
int code = 0;
char buf[100];
while (1) {
printf("a & b? ");
fflush(stdout);
if (fgets(buf,sizeof(buf),stdin) == NULL)
break;
if (buf[0] == 'n')
break;
sscanf(buf," %d %d", &a, &b);
printf("%d %dn", a, b);
int c1 = gcd(a, b);
printf("gcd1 = %dn", c1);
int c3 = gcd3(a, b);
printf("gcd3 = %dn", c3);
if (c3 != c1) {
printf("MISMATCHn");
code = 1;
}
int c4 = gcd4(a, b);
printf("gcd4 = %dn", c4);
if (c4 != c1) {
printf("MISMATCHn");
code = 1;
}
if (code)
break;
}
return code;
}

递归有点转移注意力。只要运行时体系结构支持(递归(调用堆栈(RISC V环境支持(，那么支持或执行递归就可以归结为一个函数a调用另一个函数B。(在递归的情况下，a和B是同一个函数。(关键是，你所要做的就是遵循函数调用的规则，递归就可以简单地工作。

(有机会通过偏离标准调用规则来优化函数调用，但这通常不是讲师们想要的。(

我将解决以下问题：

使用寄存器s3&s4，这对于该功能是不必要的。(如果您确实使用了它们，则需要修复prolog和epilog，因为s3和s4都保存到相同的确切内存位置，所以最后保存的将赢得内存位置。(
应该为ret使用调用阻塞寄存器，即a0是一个很好的选择。
考虑对涉及关系测试的temps使用t0，但这是MIPS风格的编程：与MIPS不同，RISC V在条件分支中具有完整的关系补码，因此不需要slt。
必须正确地将(a-b，b(作为参数传递给递归调用，第一个arg在a0中，第二个在a1中。与第二次调用中的传递(a、b-a(相同。
应该分配堆栈空间并保留ra，因为它将自动重新用于后续调用，并且您需要原始的ra值才能返回到正确的调用方。
程序集的控制流与C代码不匹配。尽管C代码是使用while循环编写的，但它实际上不包含循环。循环体内部的每个路径都有一个return语句，因此；循环；从不运行或只运行一次——最好写成if。汇编代码试图进行实际的循环，但在循环中的所有代码路径上都缺少return语句的点。return构造需要执行函数epilog(并返回给调用者(，而不是陷入下一个代码的某个随机部分。

相关内容

最新更新

热门标签：