如何在自定义虚拟机中实现尾调用

Question

如何在自定义虚拟机中实现尾调用？

我知道我需要弹出原始函数的本地堆栈，然后弹出它的参数，然后推送新参数。但是，如果我弹出函数的本地堆栈，我该如何推送新参数呢？它们刚刚从堆栈中弹出。

Answer 1

我想当然地认为我们在这里讨论的是传统的“基于堆栈”的虚拟机。

您弹出当前函数的本地堆栈在非堆栈“寄存器”中保留仍然相关的部分（其中“相关部分”显然是即将进行的递归尾调用的参数），然后（一旦清除了函数的所有本地堆栈和参数），您就可以推送递归调用的参数。例如，假设您正在优化的函数类似于：

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

如果没有优化，它可能会产生类似于符号的字节码：

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

CALL_FUN2 表示“调用带有两个参数的函数”。通过优化，它有时可能会变成这样：

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

当然，我正在编写符号字节码，但我希望意图很明确：POP_DISCARD n 是正常的弹出，只是丢弃堆栈中的 top n 条目，但 POP_KEEP n 是一种变体，将它们保留在“某处”（例如，在应用程序无法直接访问的辅助堆栈中，而只能由 VM 访问）自己的机器——在讨论 VM 实现时，具有此类字符的存储有时称为“寄存器”）和匹配的 PUSH_KEPT n ，它将“寄存器”清空回 VM 的正常堆栈。

Answer 2

我认为你看待这个问题的方式是错误的。不要将旧变量从堆栈中弹出，然后推送新变量，只需重新分配已经存在的变量（小心地）即可。如果您将代码重写为等效的迭代算法，这与会发生的优化大致相同。

对于此代码：

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

将不需要

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

在堆栈上弹出或压入任何内容，只需重新分配即可。
显然，这可以进一步优化，将退出条件放在第二位，允许我们跳过跳转，从而减少操作。

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

再看一遍，这个“程序集”更好地反映了这个C++，它显然避免了递归调用

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}