RISC-V环境下快速排序递归模块栈指针异常导致死循环问题

问题描述 #

我在做基于RISC-V的快速排序实验，已完成部分代码编写，但递归模块持续异常。推测问题源于栈指针错误，但无法自行修复。

初始参数lo=0、hi=9，每次分区时将lo作为初始pivot并与hi交换。理论上第一次分区后pivot应位于索引2（值为-5），接着递归调用分区（lo=0,hi=1）；分区后pivot位于索引1，再递归调用分区（lo=0,hi=0），此时lo>=hi应返回；随后调用分区（lo=2,hi=1）也返回，之后应回到初始调用并执行分区（lo=3,hi=9），但代码在此处进入死循环。绘制栈图分析发现，第4次递归后栈指针未回到初始的-16位置，而是停留在-32，进而触发死循环。

问题代码 #

.global _start
.data
array1: .word -5 24 -8 45 -15 24 11 7 0 125
hi: .word 9
lo: .word 0
newline: .asciz "\n"
space: .asciz " "

.text
_start:
    la s0,array1        #load address of array1[0] in s0
    lw s4,hi        #last elemnt as pivot, pivot index
    lw s5,lo        #start point(lo)
    lw s2,lo        #pivot(p)
    mv t6,s5
    jal partition
    j end
    #call function that loop partition
    
#s2(p),s4(hi),s5(lo),t5(i),t6(j),s3(array1[p])
partition:
    addi sp,sp,-16
    sw ra,0(sp)
    sw s4,4(sp)
    sw s5,8(sp) #store hi,lo,ra
    jal ra,getVal
    mv s3,t0    #the pivot value
    mv s9,s4
    mv s10,s2
    jal ra swap
    mv t6,s5    #cell going to check(j)
    addi t5,t6,-1   #the last cell that element<pivot(i)
next:   bgt t6,s4,endPartition  #when checking the last cell (pivot), it will swap with the first cell where element>pivot  
    jal ra,getVal
    ble t0,s3,less  #array1[t6]<=pivot
continue:
    addi t6,t6,1
    j next
        
less:   addi t5,t5,1    #swap array1[j] with array1[i+1]
    mv s10,t6
    mv s9,t5
    jal ra,swap
    j continue

swap:       

#swap array1[k1] and array1[k2] which is store in s9,s10,respectively
    slli t0,s9,2    #store address of array1[k1] in t0
    slli t1,s10,2   #store address of array1[k2] in t1
    add t0,s0,t0    #get address of array1[k1]
    add t1,s0,t1    #address of array1[k2]
    lw t2,0(t0) #t2 store arrary1[k1]
    lw t3,0(t1) #t3 store array1[k2]
    sw t2,0(t1)
    sw t3,0(t0)
    jr ra

getVal:         #get value of cell (array1[t6])
    slli t0,t6,2
    add t0,s0,t0
    lw t0,0(t0)
    jr ra
endPartition:   
    addi t5,t5,1
    sw t5,12(sp)    #store pivot after partition
    mv s10,t5
    mv s9,s4
    jal ra,swap
    jal ra,printArr

    lw s4,4(sp)
    lw s5,8(sp)
    blt s5,s4,recursion
    addi sp,sp,16
    jr ra
recursion:
    lw s2,12(sp)
    addi s4,s2,-1
    lw s5,8(sp)
    mv s2,s5
    mv t6,s5
    jal ra,partition    #recursion for left side
    lw s4,4(sp)
    lw s5,8(sp)
    lw s2,12(sp)
    addi s5,s2,1
    mv s2,s5
    mv t6,s5
    jal ra,partition    #resursion for right side
    jr ra

printArr:
    la t0,array1        #address of array1[0]
    li t1,10        #number of element need to print
printloop:              #loop for printing the array
    beqz,t1,printNewline    #print a newline when all element is print
    lw a0,0(t0)     #print the element
    li a7,1
    ecall
    la a0,space     #print a space as delimiter
    li a7,4
    ecall
    addi t0,t0,4        #move to next elemrnt
    addi t1,t1,-1       #need to print--
    j printloop
printNewline:           #print a newline ready for next sequence
    la a0,newline
    li a7,4
    ecall
    jr ra       #jump back to partitioning

end:

问题根源 #

• 栈指针未正确恢复：在recursion分支中，执行完左右两次递归调用后，直接jr ra返回，未将栈指针sp加16恢复到进入partition时的状态。每次递归返回后栈指针都会比预期低16，多次递归后偏移累积，破坏栈结构，引发死循环。
• 分支返回逻辑缺失：当前代码仅在blt s5,s4不成立时才执行栈指针恢复，recursion分支跳过了该步骤，导致栈状态无法正确维护。

修复方案 #

修改recursion段代码，在两次递归调用完成后添加栈指针恢复操作：

recursion:
    lw s2,12(sp)
    addi s4,s2,-1
    lw s5,8(sp)
    mv s2,s5
    mv t6,s5
    jal ra,partition    #recursion for left side
    lw s4,4(sp)
    lw s5,8(sp)
    lw s2,12(sp)
    addi s5,s2,1
    mv s2,s5
    mv t6,s5
    jal ra,partition    #resursion for right side
    addi sp,sp,16       # 新增：恢复栈指针到进入partition时的状态
    jr ra

修改后，recursion分支执行完递归后会正确恢复栈指针，确保所有代码路径都能维护栈的一致性，解决栈指针偏移导致的死循环问题。

内容的提问来源于stack exchange，提问作者Eddison Lam