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

Question

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

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

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

Answer 1

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

首先我们来了解一下移动栈指针的意义: 当您在高级语言中使用递归时，它的作用基本上是将当前函数调用的状态“保存”在“堆栈内存”中。 要实现这一目标，您必须:

1. 保存程序的当前状态(所有变量/寄存器 您正在“函数”的范围内使用)，在堆栈内存中；
2. “递归”调用该函数(这可能会修改您正在使用的所有寄存器)；
3. 当函数完成时，您必须恢复之前的状态并“释放”您分配的空间。

但除此之外，我们还必须保存 $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)。并且还存储数组、结构体等。

编辑:

一些注意事项:

• 正确的位置是您的代码调用该函数的位置(分配和保存)，以及在此调用之后(恢复和释放)。
• 了解您的代码以了解哪些变量需要保存(可能会使用)。