递归函数如何在 MIPS 中工作? [英] How a recursive function works in MIPS?

问题描述

我是 MIPS 的新手(当我开始为我的大学学习 MIPS 汇编时)，我在理解 MIPS 中递归函数的工作原理方面遇到了问题.

I'm a newbie in MIPS (as I started learning MIPS assembly for my college) and I've got a problem in understanding how a recursive function works in MIPS.

例如，我有这个程序(用 C 语言)用 MIPS 编写:

For example, I've got this program (in C) to write it in MIPS:

int fact (int n)
{
   if (n < 1) return 0;
   else return n * fact(n - 1);
}

有人可以用这个或另一个递归函数的例子帮助我并解释它是如何工作的吗?

Can someone help me, with this or another example of a recursive function and explain me how it works?

推荐答案

我想分享的第一件事是，将其转换为 MIPS 的复杂性来自于单纯的函数调用，而不是因为涉及递归——fact 是递归的，恕我直言，这是一条红鲱鱼. 为此，我将说明一个非递归函数，它具有您所说的递归函数的每一点复杂性:

The first thing I'd like to share is that the complexity in translating this into MIPS comes from the presence of mere function calling, rather than because recursion is involved — that fact is recursive is IMHO a red herring.  To this end, I'll illustrate a non-recursive function that has every bit the complexity of the recursive function you've stated:

int fact (int n)
{
   if (n < 1) return 0;
   else return n * other(n - 1);    // I've changed the call to "fact" to function "other"
}

我的修改不再是递归的！ 但是，此版本的 MIPS 代码看起来与您的 fact 的 MIPS 代码相同(当然，jal fact 会改变 jal other). 这是为了说明翻译 this 的复杂性是由于函数内的调用造成的，与被调用的人无关. (虽然 YMMV 带有优化技术.)

My alteration is no longer recursive!  However the MIPS code for this version will look identical to the MIPS code for your fact (with the exception, of course, that the jal fact which changes jal other).  This is meant to illustrate that the complexity in translating this is due to the call within the function, and has nothing to do with who is being called.  (Though YMMV with optimization techniques.)

要了解函数调用，您需要了解:

To understand function calling, you need to understand:

• 程序计数器:程序如何与程序计数器交互，尤其是在函数调用的上下文中..
• 参数传递
• 一般注册约定

在 C 中，我们有显式参数. 当然，这些显式参数也出现在汇编/机器语言中——但也有一些在机器代码中传递的参数在 C 代码中不可见.这些示例包括返回地址值和堆栈指针.

In C, we have explicit parameters.  These explicit parameter, of course, also appear in assembly/machine language — but there are also parameters passed in machine code that are not visible in C code.  Examples of these are the return address value, and the stack pointer.

这里需要的是对函数的分析(独立于递归):

What is needed here is an analysis of the function (independent of recursion):

参数 n 将在函数入口的 $a0 中. n 的值在函数调用之后是必需的(到 other)，因为在该函数调用返回 *.

The parameter n will be in $a0 on function entry.  The value of n is required after the function call (to other), because we cannot multiply until that function call returns the right hand operand of *.

因此，n(* 的左手操作数)必须在other 的函数调用中存活下来，并且在$a0 它不会——因为我们自己的代码将重新利用 $a0 以调用 other(n-1)，作为 n-1 必须进入 $a0 .

Therefore, n (the left hand operand to *) must survive the function call to other, and in $a0 it will not — since our own code will repurpose $a0 in order to call other(n-1), as n-1 must go into $a0 for that.

此外，(在 C 中，隐式)参数$ra 保存返回给我们的调用者所需的返回地址值. 类似地，对 other 的调用将重新调整 $ra 寄存器的用途，清除其先前的值.

Also, the (in C, implicit) parameter$ra holds the return address value needed to return to our caller.  The call to other will, similarly, repurpose the $ra register, wiping out its previous value.

因此，此函数(您的或我的)需要两个值才能在其主体内的函数调用(例如对other 的调用)中存活下来.

Therefore, this function (yours or mine) needs two values to survive the function call that is within its body (e.g. the call to other).

解决方案很简单:我们需要的值(存在于寄存器中，这些值被我们正在做的事情或被调用者可能做的事情重新利用或删除)需要移动或复制到其他地方:某个地方可以在函数中幸存下来打电话.

The solution is simple: values we need (that are living in registers that are repurposed or wiped out by something we're doing, or the callee potentially does) need to be moved or copied elsewhere: somewhere that will survive the function call.

内存可用于此目的，并且我们可以使用堆栈为这些目的获取一些内存.

Memory can be used for this, and, we can obtain some memory for these purposes using the stack.

基于此，我们需要创建一个堆栈帧，在调用 other 后为我们需要的两个东西提供空间(否则会被清除). 条目 $ra 必须保存(然后重新加载)，以便我们使用它返回；此外，需要保存初始 n 值，以便我们可以将其用于乘法. (堆栈帧通常在函数序言中创建，并在函数尾声中删除.)

Based on this, we need to make a stack frame that has space for the two things we need (and would otherwise get wiped out) after calling other.  The entry $ra must be saved (and later reloaded) in order for us to use it to return; also, the initial n value needs to be saved so we can use it for the multiply.  (Stack frames are typically created in function prologue, and removed in function epilogue.)

在机器代码(甚至一般的编程)中经常出现这种情况，但也有其他处理方式，尽管要点是相同的. (这是一件好事，优化编译器通常会根据特定情况寻找最佳方法.)

As is often the case in machine code (or even programming in general) there are also other ways of handling things, though the gist is the same.  (This is a good thing, and an optimizing compiler will generally seek the best way given the particular circumstances.)

递归的存在与否不会改变我们将其翻译成汇编/机器语言所需的基本分析. 递归极大地增加了堆栈溢出的可能性，但不会改变这种分析.

Presence or absence of recursion does not change the fundamental analysis we need to translate this into assembly/machine language.  Recursion dramatically increases the potential for stack overflow, but otherwise does not change this analysis.

需要明确的是，递归要求使用可动态扩展的调用堆栈——尽管所有现代计算机系统都提供了这样的调用堆栈，因此这一要求很容易被今天的系统遗忘或掩盖.

To be clear, recursion imposes the requirement to use a dynamically expandable call stack — though all modern computer systems provide such a stack for calling, so this requirement is easy to forget or gloss over on today's systems.

对于没有递归的程序，调用栈不是必需的——局部变量可以分配给函数私有的全局变量(包括返回地址)，这在某些较旧的系统上完成，如 PDP-8，它没有不为调用堆栈提供特定的硬件支持.

For programs without recursion, a call stack is not a requirement — local variables can be allocated to function-private global variables (including the return address), and this was done on certain older systems like the PDP-8, which did not offer specific hardware support for a call stack.

使用堆栈内存来传递参数和/或寄存器不足的系统可能不需要本答案中描述的分析，因为变量已经存储在内存中，可以在嵌套函数调用中幸存下来.

Systems that use stack memory for passing parameters and/or are register poor may not require the analysis described in this answer, since variables are already being stored in memory that survives nested function calls.

现代寄存器丰富的机器上的寄存器分区产生了上述分析的要求. 这些寄存器丰富的机器在 CPU 寄存器中传递参数和返回值(大部分)，这很有效，但有时需要进行复制，因为寄存器从一个函数被重新用于另一个函数.

It is the partitioning of registers on modern register-rich machines that creates the requirement for the above analysis.  These register-rich machines pass parameters and return values (mostly) in CPU registers, which is efficient but imposes the need to sometimes make copies as registers are repurposed from one function to another.

这篇关于递归函数如何在 MIPS 中工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！