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

az31mfrm  于 2022-11-13  发布在  其他
关注(0)|答案(2)|浏览(215)

我们有一个任务要把下面的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 = \0"
str2:    .ascii "\n\0"

.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函数的代码中得到了一个数据保存错误。可能是因为我使用变量或结束函数的方式。
任何帮助理解如何做到这一点将不胜感激。

368yc8dk

368yc8dk1#

Erik的回答解释了代码中的错误。代码中有很多错误。下面我列出几个:
1.寄存器保存/恢复代码错误。从4(sp)进行存储/加载,因此一个寄存器被乱码
1.恢复代码中的addi错误--它与保存代码不匹配
1.没有保存/恢复返回地址(例如ra)。实际上,这是 * 唯一 * 需要保存/恢复的寄存器。

  1. a0/a1(即ab)在递归调用中从不更改
    1.通常,返回值的格式是v0,这只是惯例,所以没什么大不了的。
    1.我们只需要一个额外的寄存器来获取slt结果。按照惯例,这可以是一个t*寄存器[不需要保存/恢复]。
    请注意,在下面的代码中,我测试了修改后的C函数,但没有测试asm。
    当我想编写汇编程序时,我重写C代码,只使用ifgoto,以便更接近地模拟[建议的]汇编程序。
    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 %d\n", a, b);

        int c1 = gcd(a, b);
        printf("gcd1 = %d\n", c1);

        int c3 = gcd3(a, b);
        printf("gcd3 = %d\n", c3);
        if (c3 != c1) {
            printf("MISMATCH\n");
            code = 1;
        }

        int c4 = gcd4(a, b);
        printf("gcd4 = %d\n", c4);
        if (c4 != c1) {
            printf("MISMATCH\n");
            code = 1;
        }

        if (code)
            break;
    }

    return code;
}
rdlzhqv9

rdlzhqv92#

递归有点red herring。只要运行时体系结构支持(递归)调用栈- RISC V环境是这样做的-那么支持或执行递归就归结为一个函数A调用另一个函数B。(在递归的情况下,A和B是同一个函数。)重点是,你所要做的就是遵循 * 函数调用 * 的规则,递归就会简单地工作。
(通过偏离标准调用规则,可以优化函数调用,但这通常不是教师在这里要做的。)
我想谈以下几点:

  • 使用寄存器s3s4,这两个寄存器对于此函数是不必要的。(如果使用它们,需要修复prologue和epilog,因为s3s4都保存到相同的存储器位置,所以最后保存的将获得存储器位置。)
  • 对于ret,应使用call-crobbered寄存器,即a0是一个很好的选择。
  • 考虑使用t0作为涉及关系测试的临时变量,但这是MIPS风格的编程:与MIPS不同,RISC V在条件分支中具有关系的全部补充,因此不需要slt
  • 必须正确地将(a-bb)作为参数传递给递归调用,第一个参数在a0中,第二个参数在a1中。在第二个调用中传递(ab-a)时也是如此。
  • 应该分配堆栈空间并保留ra,因为它将自动重新用于后续调用,并且您将需要原始ra值以返回到正确的调用方。
  • 程序集的控制流与C代码不匹配。尽管C代码是使用while循环编写的,但它实际上不包含循环。循环体中的每个路径都有一个return语句,因此,“循环”要么从不运行,要么只运行一次-最好写成if。程序集代码试图创建一个实际的循环,在循环中的所有代码路径上缺少return语句的点。return构造需要执行函数epilog(并返回给调用者),而不是落入碰巧是下一个代码的某个随机部分。

相关问题