0

我在课堂上，我们已经/正在介绍汇编语言中的递归。我觉得我理解了递归，但是越多人试图向我解释它，我就越觉得离它越远。

无论如何，我们的最后一张幻灯片有一个函数（用 C 语言？），老师说他会在课堂上介绍它，但呼吁我们学生在黑板上展示课堂的其余部分。我觉得他一直在看着我，我害怕看起来很愚蠢。

你们能帮我用 MIPS 编写这段代码并帮助我理解吗？IDK 如果这太难了

用 MIPS 汇编语言编写找到 fix(i,x)，其中 fix(i, x) 递归定义为：

int fix(int i, int x) // assume i > 0, x > 0
{
    if (x>0)
        return fix(i,x-1);
    else if (i>0)
        return fix(i-1, i-1)+1;
    else
        return 0;
}

谢谢你们，我明天就要上课了，我还是希望他不要来找我；但我想真正了解这种材料。

注意：这将是一个附有 0 学分的课堂练习。我觉得班上的每个人都已经知道如何做到这一点。

4

3 回答 3

2

汇编语言与递归无关，由于 C 语言以及调用约定和实现，它恰好可以工作。只需在汇编程序中实现 C 而不关心递归。我想我在一个宠物项目http://github.com/dwelch67/lsasim上谈到了这一点，除非我把它改掉，最后一课是手动将 C 中的递归转换为汇编程序。它不是 mips，所以不用担心这是一个家庭作业问题。

无论如何，开始的关键是简单地在汇编中实现 C。

例如，您有一个带有输入参数的函数。

int fix(int i, int x)

您将需要声明自己的调用约定或使用现有的约定，要实现 C，这意味着您需要一些输入参数的位置，将它们压入堆栈或将它们放入寄存器中。假设没有优化，您将在整个函数中保留这些变量并在最后进行清理。因此，如果您需要在代码中的任何位置调用 ANY 函数（递归，调用相同的函数，是 ANY 的一个非常小的子集，但属于该类别并且不是特殊的），您需要保留这些变量。如果调用约定将它们带入堆栈，那么您已经完成，如果调用约定将它们带入寄存器，那么您需要在调用之前保留它们并在调用之后恢复

push i
push x
implement call to function
pop x
pop i

并继续执行该功能。

就是这样，其余的将自行处理。

如果您碰巧注意到您作为示例创建的函数，在调用此函数中的函数后没有需要保留输入变量的路径。并且输入变量被修改并用作下一次调用的输入。因此，对 C 代码实现的优化是不用担心保留这些变量。只需修改它们并传递它们。在调用约定中使用寄存器将是为此特定函数执行此操作的最简单方法。这是编译器在优化时无论如何都会做的事情（如果使用基于寄存器的调用约定，则不保留）。

如果这就是所谓的，您也可以进行尾部优化。通常在调用函数时，您使用指令通常执行的任何操作来执行“调用”，这与简单的跳转或分支不同，因为在某处保存了返回值。并且有某种返回函数可以撤消此操作并在调用后返回到指令。嵌套调用意味着嵌套返回值，跟踪所有的返回值。尽管在这种情况下以及在其他情况下，您对函数的执行路径所做的最后一件事是调用另一个函数，但您可以（取决于指令集）分支到该函数，而不必嵌套另一组返回值。以 arm 指令集为例：

一些代码调用第一个函数：

bl firstfun:

在 arm bl 表示分支链接。寄存器 14 将填入返回值，程序计数器将填入函数 firstfun 的地址。

通常，如果您需要从函数调用函数，则需要保存 r14 以便可以从该函数返回，而无需进行尾部优化：

firstfun:
 ...
 push {r14}
 bl secondfun
 pop {r14}
 bx r14
 ...
secondfun:
  bx r14

bx lr 只是表示分支到 r14 中的内容，在这种情况下是返回。优化看起来像这样，重要的是要注意，在第一个函数中，对第二个函数的调用是您在从第一个函数返回之前所做的最后一件事。这是此优化的关键。

firstfun:
 ...
 b secondfun
 ...
secondfun:
  bx r14

b 仅表示分支，而不是分支链接仅修改 pc 并且不修改 r14 或任何其他寄存器或堆栈。两个实现的执行在功能上是相同的，外部函数调用 firstfun 并且在正确的执行路径中有一个返回 (bx r14)。

其他人指出，由于您将原始调用者返回为零，因此该代码可能会完全优化自身。

fix:
  return 0
于 2012-01-26T04:32:47.350 回答
1

虽然我反对只给出作业问题的答案，但这里是 find 的等效函数，fix(i, x)并带有示例调用（此版本比 C 版本更有效）：

fix:
        bgtz RetI
        xor $v0, $v0, $v0
        jr $ra
RetI:
        move $v0, $a0
        jr $ra

# example of calling fix
main:
        la $a0, 42
        la $a1, 21
        jal fix

让这成为你在尝试编写函数之前学习函数的一个教训:)

于 2012-01-26T00:39:33.303 回答
1

就像上面的 C 一样，把它分成 3 块。通过寄存器传递值 i 和 x 并在运行 if 检查和修改寄存器后调用自己。以上不应该超过 30 行汇编程序来完成。如果我是一个更好的 MIPS 编码器，我会为你做。它看起来像（是伪汇编程序）


fix:
  compare r0, 0
  branch greater than x_positive
  subtract r1,r1,1
  call fix
  return;
//  or just jump fix instead

x_positive:
  compare r1, 0
  branch greater than i_positive
  subtract r0, r0, 1
  subtract r1, r1, 1
  call fix
  return
// or just  jmp fix

i_positive:
  move return register, 0
  return

有趣的是，这将始终返回 0，如用 C 编写的 :)


  fix:
    move return_register, 0
    return
于 2012-01-26T00:44:16.650 回答