从 C 到 MIPS 的快速排序 - 如何传递参数和维护堆栈帧的变量？

Question

我正在对整数数组创建快速排序算法。我正在使用这个 C 算法并将其转换为 MIPS。然而，MIPS和递归确实非常难。

我不确定如何将参数发送到递归调用 QS。我最近发现我可以通过将堆栈指针移动 4 个字节来更改调用堆栈中每个帧的 $s 寄存器。这将允许我更改每个堆栈帧的 $s 寄存器，这样我就不需要每个 QS 帧的一百万个变量。

我的问题是我不太明白在递归过程中如何以及何时设置和获取这些 $sx 值。

Answer 1

递归是通过移动堆栈指针寄存器($sp)实现的。

首先我们来了解一下移动栈指针的意义：当您在高级语言中使用递归时，它所做的基本上是 "save" "stack memory" 中当前函数调用的状态。为此，您必须：

保存程序的当前状态（所有 variables/registers 你在"function")的范围内使用，在栈内存中；
调用函数"recursively"（这可能会修改您使用的所有寄存器）；
函数完成后，您必须恢复之前的状态和 "free" 您分配的 space。

但除此之外，我们还必须保存 $ra 的值，以跟踪上层函数结束时我们应该去哪里。

下面是一个递归计算阶乘 (n) 的简单程序示例：

.text
main:
  # Calls Fact with Input ($a0) N = 10
  li $a0, 10
  jal fact
  # prints the Output ($v0) Factorial(N)
  move $a0, $v0
  li $v0, 1
  syscall
  # exit
  li $v0, 10
  syscall

# Input: $a0 - N
# Output: $v0 - Factorial(N)
fact:
  # Fact(0) = 1
  beq $a0, 0, r_one
  # Fact(N) = N * Fact(N-1) use recursion
  # allocate 8 bytes in the stack for storing N, and $ra
  addi $sp, $sp, -8
  # stores N in the first, and $ra in the last position
  sw $a0, 4($sp)
  sw $ra, 0($sp)
  # call Fact(N-1)
  addi $a0, $a0, -1
  jal fact
  # Restore the values of N and $ra
  lw $a0, 4($sp)
  lw $ra, 0($sp)
  # Free the 8 bytes used
  addi $sp, $sp, 8
  # Set the return value to be N * Fact(N-1) and return
  mul $v0, $a0, $v0
  jr $ra
  # return 1;
  r_one:
    li $v0, 1
    jr $ra

这基本上是您在实施代码时应该牢记的。只需关注：

堆栈指针递减；
您需要分配多少字节。在这个例子中我使用了 2 个 32 位整数，总共 8 个字节。这将取决于您需要存储多少变量及其大小。
如何使用正确的索引通过 lw 和 sw 访问它们。另外，请注意内存对齐；
这不仅适用于递归。您可以使用堆栈内存来调用另一个使用正在使用的寄存器的函数（与递归基本相同，只是您不需要保存 $ra）。并且还存储一个数组，一个结构等

编辑：

一些注意事项：

执行此操作的正确位置是您的代码调用函数的位置（分配和保存），以及在此调用之后（恢复和释放）。
了解您的代码以了解需要保存哪些变量（可能会被使用）。

从 C 到 MIPS 的快速排序 - 如何传递参数和维护堆栈帧的变量？

Quicksort from C to MIPS - How to pass parameters and maintaining variables for stack frame?

c

parameters

recursion

mips

quicksort