【译文】在计算机里还没有堆(heap)和栈(stacks)的古世界里的子程序调用

堆栈| 2024-04-05

如今，我们认为堆(heap)和栈(stacks)是理所当然的，但在计算机发展的早期，计算机的运行是没有堆栈和堆的。

告诉一个刚毕业的大学生这些，你还不如告诉他，曾经有一段时间，你无法即时访问数以百万计的 cat 视频。

要想象没有动态内存分配的计算环境并不难。你只需使用固定大小的内存缓冲区来处理所有事情。如果你必须对可变大小的数据进行操作，你就会预留一个固定大小的缓冲区，其容量足以容纳你要合理处理的任何数据，如果有人要求更多，你就会以致命错误退出程序。如果你真的很好，你会提供一个编译时配置，这样你的客户就可以根据他们的数据集调整最大容量。如果你真的很花哨，你还会编写一个自定义分配器，在固定大小的缓冲区上运行，这样人们就可以从缓冲区中 “分配 “和 “释放 “内存了。

但在没有堆栈的情况下如何操作？如果没有堆栈来存放返回地址或局部变量，又如何调用函数呢？

事情是这样的。

首先，编译器为每个入站函数参数定义了一个秘密全局变量，并为每个函数定义了另一个秘密全局变量来保存返回地址。编译器还为每个函数的局部变量定义了一个秘密全局变量。

为了生成函数调用，编译器将参数值分配给相应的秘密全局变量，将返回地址分配给函数的秘密 “返回地址变量”，然后跳转到函数的起始位置。

函数从其秘密全局变量中读取参数，并使用与其逻辑局部变量相对应的预定义秘密全局变量。函数完成后，跳转到函数的秘密 “返回地址变量 “中的地址。

例如，假设你有这样一段代码，是用类似 C 语言编写的：

int add_two_values(int a, int b)
{
    int c = a + b;
    return c;
}

void sample()
{
    int x = add_two_values(31415, 2718);
}

编译器会将其转换成类似这样的内容：

int a2v_a;
int a2v_b;
int a2v_c;
void* a2v_retaddr;

int add_two_values()
{
    a2v_c = a2v_a + a2v_b;

    return_value_register = a2v_c;
    goto a2v_retaddr;
}

int sample_x;
void sample()
{
    a2v_a = 31415;
    a2v_b = 2718;
    a2v_retaddr = &resume;
    goto add_two_values;
resume:
    sample_x = return_value_register;
}

来看看：我们在没有堆栈的情况下进行了函数调用和返回！

现在，你可以通过在寄存器而不是全局中传递其中一些值来优化 ABI。例如，大多数处理器都有一个特殊的 ““link “寄存器和一条特殊指令 “branch with link”，该指令会自动将链接寄存器设置为 “branch with link “指令之后的指令地址，也许你优化了调用规则，将前两个参数用寄存器传递，结果就是这样：

int a2v_a;
int a2v_b;
int a2v_c;
void* a2v_retaddr;

int add_two_values()
{
    a2v_a = argument_register_1;
    a2v_b = argument_register_2;
    a2v_retaddr = link_register;

    a2v_c = a2v_a + a2v_b;

    return_value_register = a2v_c;
    goto a2v_retaddr;
}

int sample_x;
void sample()
{
    argument_register_1 = 31415;
    argument_register_2 = 2718;
    branch_with_link add_two_values;
    sample_x = return_value_register;
}

只有一个问题：你不能进行递归。

递归不起作用是因为递归调用会用递归调用的返回地址覆盖返回地址变量，当外部调用完成时，就会跳转到错误的地方。

当时的编程语言解决这个问题的方法就是简单地宣布递归调用非法：它们不支持递归。

作者：Raymond Chen

额外的聊天：有些编译器甚至更狡猾，使用了自修改代码：特殊的返回地址变量实际上是函数末尾跳转指令的地址！

有时，这与其说是一种偷偷摸摸的技巧，不如说是一种实际需要：处理器可能也不支持间接跳转！

在认识到子程序的实用价值后，许多处理器增加了子程序调用指令，将返回地址存储在子程序的第一个 word 上，并从子程序的第二个 word 开始执行。要从子程序返回，需要通过子程序起始标签执行间接跳转。(我记得，有些处理器将返回地址存储在子程序第一条指令之前的字段）。下面是用汇编语言编写的程序：

add_two_values:
    nop                     ; return address goes here
    add   r1 = r1, r2       ; actual subroutine begins here
    jmp   @add_two_values   ; indirect jump to return address

sample:
    mov   r1 = 31415        ; first parameter
    mov   r2 = 2718         ; second parameter
    bsr   add_two_values    ; call subroutine
    st    sample_x = r1     ; save return value

当 CPU 执行 bsr 分支到子程序指令时，它会将返回地址存储到 add_twoo_values 的第一个字中（覆盖牺牲的 nop），然后开始执行下面的指令，即 add r1 = r1, r2。

¹ FORTRAN 最初甚至不支持子程序！子程序是在 1958 年加入的。直到 1991 年，FORTRAN 才将支持递归作为标准配置，即便如此，你也必须明确地将子程序声明为递归（RECURSIVE）。

本文文字及图片出自 Subroutine calls in the ancient world, before computers had stacks or heaps