MIPS: 栈指针（$sp）和栈的相关用途

Question

我正在准备计算机组成原理的期中考试，尝试完全理解栈指针和栈。 我知道以下与概念相关的事实：

• It follows the first in last out principle

• And adding something to the stack takes a two step process:

  addi $sp, $sp, -4
  sw $s0, 0($sp)
  

我认为阻碍我完全理解的原因是我无法想到一个相关的、自明的情况，在这种情况下我需要和/或想要使用栈指针来跟踪数据。

有人能够详细说明整个概念并给我一些有用的代码示例吗？

- Connor Black

---

你应该使用无符号加/减来处理地址，否则如果发生溢出（跨越0x7FFFFFFF和0x80000000之间的边界），就会冒着异常/陷阱的风险。 - Alexey Frunze

实际上是这样，但出于测试目的，我认为他并不要求我们理解那种微妙之处。 - Connor Black

Answer 1

一个栈的重要用途是嵌套子程序调用。

每个子程序可以有一组本地变量。这些变量可以方便地存储在一个“栈帧”中。一些调用惯例也将参数传递到堆栈上。

使用子程序还意味着您必须跟踪调用者，即返回地址。 一些体系结构专门为此目的设计了一个堆栈，而其他体系结构隐式使用“正常”堆栈。 MIPS默认仅使用寄存器，但在非叶函数（即调用其他函数的函数）中，返回地址被覆盖。因此，您必须保存原始值，通常保存在本地变量之间的堆栈上。调用惯例也可以声明一些寄存器值必须在函数调用中保留，您可以类似地使用堆栈保存和恢复它们。

假设您有这个C片段：

extern void foo();
extern int bar();
int baz()
{
    int x = bar();
    foo();
    return x;
}

MIPS汇编代码可能如下所示：

addiu $sp, $sp, -8  # allocate 2 words on the stack
sw $ra, 4($sp)      # save $ra in the upper one
jal bar             # this overwrites $ra
sw $v0, ($sp)       # save returned value (x)
jal foo             # this overwrites $ra and possibly $v0
lw $v0, ($sp)       # reload x so we can return it
lw $ra, 4($sp)      # reload $ra so we can return to caller
addiu $sp, $sp, 8   # restore $sp, freeing the allocated space
jr $ra              # return

- Jester

---

这可能是我读过的最清晰的关于这个主题的解释。非常感谢！ - Aleksandr Hovhannisyan

Answer 2

MIPS调用约定要求前四个函数参数在寄存器a0到a3中，如果还有更多的参数，则放在堆栈中。此外，它还要求函数调用者为前四个参数在堆栈上分配四个插槽，尽管这些参数已经传递给了寄存器。

因此，如果您想访问第五个（及更多）参数，需要使用sp。如果该函数反过来调用其他函数并在调用后使用其参数，则需要将a0到a3存储在堆栈上的这四个插槽中，以避免它们丢失/被覆盖。同样，您可以使用sp将这些寄存器写入堆栈。

如果您的函数具有局部变量，并且无法将所有变量都保留在寄存器中（例如，当它调用其他函数时无法保留a0到a3时），则必须使用on-stack空间来存储这些局部变量，这再次需要使用sp。

例如，如果您有以下内容：

int tst5(int x1, int x2, int x3, int x4, int x5)
{
  return x1 + x2 + x3 + x4 + x5;
}

它的反汇编大概会是这样：

tst5:
        lw      $2,16($sp) # r2 = x5; 4 slots are skipped
        addu    $4,$4,$5   # x1 += x2
        addu    $4,$4,$6   # x1 += x3
        addu    $4,$4,$7   # x1 += x4
        j       $31        # return
        addu    $2,$4,$2   # r2 += x1

注意，sp用于访问x5。

如果您有以下代码：

int binary(int a, int b)
{
  return a + b;
}

void stk(void)
{
  binary(binary(binary(1, 2), binary(3, 4)), binary(binary(5, 6), binary(7, 8)));
}

这是编译后的反汇编结果：

binary:
        j       $31                     # return
        addu    $2,$4,$5                # r2 = a + b

stk:
        subu    $sp,$sp,32              # allocate space for local vars & 4 slots
        li      $4,0x00000001           # 1
        li      $5,0x00000002           # 2
        sw      $31,24($sp)             # store return address on stack
        sw      $17,20($sp)             # preserve r17 on stack
        jal     binary                  # call binary(1,2)
        sw      $16,16($sp)             # preserve r16 on stack

        li      $4,0x00000003           # 3
        li      $5,0x00000004           # 4
        jal     binary                  # call binary(3,4)
        move    $16,$2                  # r16 = binary(1,2)

        move    $4,$16                  # r4 = binary(1,2)
        jal     binary                  # call binary(binary(1,2), binary(3,4))
        move    $5,$2                   # r5 = binary(3,4)

        li      $4,0x00000005           # 5
        li      $5,0x00000006           # 6
        jal     binary                  # call binary(5,6)
        move    $17,$2                  # r17 = binary(binary(1,2), binary(3,4))

        li      $4,0x00000007           # 7
        li      $5,0x00000008           # 8
        jal     binary                  # call binary(7,8)
        move    $16,$2                  # r16 = binary(5,6)

        move    $4,$16                  # r4 = binary(5,6)
        jal     binary                  # call binary(binary(5,6), binary(7,8))
        move    $5,$2                   # r5 = binary(7,8)

        move    $4,$17                  # r4 = binary(binary(1,2), binary(3,4))
        jal     binary                  # call binary(binary(binary(1,2), binary(3,4)), binary(binary(5,6), binary(7,8)))
        move    $5,$2                   # r5 = binary(binary(5,6), binary(7,8))

        lw      $31,24($sp)             # restore return address from stack
        lw      $17,20($sp)             # restore r17 from stack
        lw      $16,16($sp)             # restore r16 from stack
        addu    $sp,$sp,32              # remove local vars and 4 slots
        j       $31                     # return
        nop

我希望我已经在不出错的情况下对代码进行了注释。

请注意，编译器选择在函数中使用r16和r17，但将它们保留在堆栈上。由于该函数调用另一个函数，因此还需要将其返回地址保存在堆栈中，而不是只将其保留在r31中。

PS 请记住，在MIPS上，所有分支/跳转指令在实际传输控制到新位置之前有效地执行紧随其后的指令。这可能会让人感到困惑。

- Alexey Frunze