assembly RISC-V在递归调用中使用堆栈

shyt4zoc  于 2022-11-13  发布在  其他
关注(0)|答案(1)|浏览(172)

有没有人能解释一下a0指针为什么不能返回到原来的值?下面的代码使用DC指令创建字符串并将其反转。Trecrev被递归调用,并使用堆栈存储值。我能理解为什么保存ra。如果我们不保存它,我们将丢失返回到main的返回地址。但为什么我们需要保存a0和a1呢?此外,如果我们把a0重新加载到a0中,为什么我们不能把字符串恢复到正常状态呢?

STR:    DC  "Hadoukan\0"

main:
    addi    a0, x0, STR
    jal ra, strlen
    addi    a1, a0, -1
    addi    a0, x0, STR
    jal ra, trecrev
    addi    x5, x0, STR
    ecall   x0, x5, 4
    ebreak  x0,x0, 0

trecrev:
    bge x0, a1, trecrevbase
    addi    sp, sp, -24
    sd  ra, 0(sp)
    sd  a0, 8(sp)
    sd  a1, 16(sp)
    add a1, a1, a0
    jal ra, excharr
    ld  ra, 0(sp)
    ld  a0, 8(sp)
    ld  a1, 16(sp)
    addi    sp, sp, 24
    addi    a0, a0, 1
    addi    a1, a1, -2
    jal x0, trecrev

trecrevbase:
    jalr    x0, 0(ra)

;;; EXCHARR
;;; expects two arguments (pointers to characters) and
;;; exchanges the two characters
excharr:
    lb  t0, 0(a0)
    lb  t1, 0(a1)
    sb  t1, 0(a0)
    sb  t0, 0(a1)
    jalr    x0, 0(ra)

;;; STRLEN
;;; expacts one argument pointer to char and returns the length of the
;;; string.
;;; t0  -> counter
;;; t1  -> temp to read the char in.
strlen:
    addi    t0, x0, 0
strlenloop:
    lb  t1, 0(a0)
    beq t1, x0, strlenend
    addi    t0, t0, 1
    addi    a0, a0, 1
    jal x0, strlenloop
strlenend:
    addi    a0, t0, 0
    jalr    x0, 0(ra)

我猜我对字符指针以及它们如何存储在堆栈上的理解是缺乏的。

kupeojn6

kupeojn61#

首先,让我们注意到这里没有递归:这是一种迭代算法。

trecrev:
    bge x0, a1, trecrevbase

    addi sp, sp, -24   # this is written so as to look like function prologue
                       # but it isn't -- it occurs inside the loop
    sd ra, 0(sp)       # silly to save the same, unchanging ra each iteration...
    sd a0, 8(sp)       # saving a0, since the upcoming call will overwrite a0
                       # and we need this variable for the next iteration
    sd a1, 16(sp)      # saving a1, since the upcoming call will overwrite a1
                       # and we need this variable for the next iteration

    add a1, a1, a0     # passing (array, array+index) as a0, a1
    jal ra, excharr

    ld ra, 0(sp)       # this is written so as to look like function epilogue,
                       # but it isn't -- it occurs inside the loop
    ld a0, 8(sp)       #
    ld a1, 16(sp)      #
    addi sp, sp, 24    #

    addi a0, a0, 1
    addi a1, a1, -2

    jal x0, trecrev    # this may look like a call, but it is not.
                       # this is a simple backward branch, 
                       #   effectively forming a loop

trecrevbase:
    jalr x0, 0(ra)

堆栈正被用作变量存储,它将在对ecxharr的调用后继续存在。
这种方法是可行的,尽管可以说是有缺陷的,因为它在每次迭代时都推送和弹出,这是不必要的,也是误导性的。误导性的是,它在每次迭代时都推送整个堆栈帧,这是不必要的。
这可以通过将堆栈帧创建移到循环之外来解决,如下面的转换所示。
(By定义函数序言出现在函数体之前,并且只运行一次;函数尾声发生在函数体之后,并且只运行一次。)

trecrev:
    addi  sp, sp, -24   # this is function prologue
                        # creating room for saved ra + 2 more slots
    sd ra, 0(sp)        # saving ra (just once!)

loop1:
    bge x0, a1, loop1End

    sd a0, 8(sp)        # saving a0, since the upcoming call will overwrite a0
    sd a1, 16(sp)       # saving a1, since the upcoming call will overwrite a1

    add a1, a1, a0      # passing (array, array+index) as a0, a1
    jal ra, excharr

    ld a0, 8(sp)        # restore the a0 and a1 variables from the stack
    ld a1, 16(sp)

    addi a0, a0, 1
    addi a1, a1, -2

    jal x0, loop1       # loop

loop1End:
    ld ra, 0(sp)        # this is function epilogue
    addi sp, sp, 24     #
    jalr x0, 0(ra)

不过,对于这种情况,最好也是最合适的方法是使用s寄存器,而不是内存来存储那些需要在调用excharr后仍然存在的变量。

trecrev:
    addi  sp, sp, -24   # this is function prologue
                        # creating room for saved ra + 2 more slots
    sd ra, 0(sp)        # saving ra (just once!)
    sd s0, 8(sp)        # preserving s0 so we can use s0
    sd s1, 16(sp)       # preserving s1 so we can use s1

    move s0, a0         # transfer parameter variables to s regs
    move s1, a1

loop1:
    bge x0, s1, loop1End

    move a0, s0
    add a1, a1, a0      # passing array, array + len as a0, a1
    jal ra, excharr

    addi s0, s0, 1
    addi s1, s1, -2

    jal x0, loop1       # loop

loop1End:
    ld ra, 0(sp)        # this is function epilogue
    ld s0, 8(sp)
    ld s1, 16(sp)
    addi sp, sp, 24
    jalr x0, 0(ra)

使用s寄存器代替堆栈存储器,从每次迭代有2次加载和2次存储变为仅一次有2次加载和2次存储。
这个函数的大部分工作都在循环中进行,现在循环大大缩短了。
(使用s寄存器而不是内存会使函数仅在使用索引0调用时开销更大;当以索引1调用时,它是偶数,而当以索引〉1调用时,它是赢。)

相关问题