19

目前我正在为我的计算机组织期中学习,我正在尝试完全理解堆栈指针和堆栈。我知道围绕这个概念的以下事实:

  • 它遵循先进后出的原则
  • 向堆栈中添加一些东西需要两个步骤:

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

我认为阻止我完全理解的是,我无法提出一个相关的、不言自明的情况,我需要和/或想要使用堆栈指针跟踪数据。

有人可以详细说明这个概念并给我一些有用的代码示例吗?

4

2 回答 2

37

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

每个子程序可能有一组该子程序的局部变量。这些变量可以方便地存储在堆栈帧中的堆栈中。一些调用约定也会在堆栈上传递参数。

使用子例程还意味着您必须跟踪调用者,即返回地址。一些架构为此目的有一个专用堆栈,而其他架构则隐式使用“普通”堆栈。默认情况下,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
于 2013-02-26T23:11:03.870 回答
8

MIPS 调用约定要求前四个函数参数在寄存器中a0a3其余的(如果有更多的话)在堆栈中。更重要的是,它还要求函数调用者在堆栈上为前四个参数分配四个插槽,尽管这些参数是在寄存器中传递的。

因此,如果要访问参数 5(以及更多参数),则需要使用sp. 如果该函数依次调用其他函数并在调用后使用其参数,则需要在堆栈上的这四个槽中进行存储a0a3以避免它们丢失/覆盖。同样,您使用sp将这些寄存器写入堆栈。

如果您的函数具有局部变量并且不能将它们全部保存在寄存器中(例如当它调用其他函数时无法保持a0通过a3),它将不得不为这些局部变量使用堆栈空间,这再次需要的使用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

我希望我已经对代码进行了注释而不会出错。

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

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

于 2013-02-26T23:21:47.980 回答