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

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是正常弹出，只是丢弃从堆栈顶部n条目，但POP_KEEP n是让他们变体“地方”（在辅助堆栈不直接到应用程序访问，但只有到虚拟机本身的机械如 - 存储有这样的性格有时被称为讨论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"

有没有必要POP或堆栈上推什么，只是重新分配。结果 显然，这可以进一步优化，通过将退出条件第二，使我们能够跳过跳跃，从而导致更少的操作。

 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;
}