0

カスタム仮想マシンに末尾呼び出しを実装するにはどうすればよいですか？

元の関数のローカルスタックをポップオフし、次に引数を取得してから、新しい引数をプッシュする必要があることはわかっています。しかし、関数のローカルスタックをポップオフした場合、新しい引数をどのようにプッシュする必要がありますか？それらはスタックからポップされたばかりです。

4

2 に答える 2

4

ここでは、従来の「スタックベース」の仮想マシンについて説明しているのは当然だと思います。

現在の関数のローカルスタックをポップオフして、スタック以外の「レジスタ」にまだ関連する部分を保持します（「関連する部分」は、明らかに、次の再帰的な末尾呼び出しの引数です）、次に（関数のすべてのローカルスタックと引数がクリーンアップされます）再帰呼び出しの引数をプッシュします。たとえば、最適化する関数が次のようなものであるとします。

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は、「2つの引数を持つ関数を呼び出す」ことを意味します。最適化により、次のようになる可能性があります。

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

もちろん、私はシンボリックバイトコードを作成していますが、その意図が明確であることを願っています。これは、スタックから最上位のエントリをPOP_DISCARD n破棄する通常のポップですが、それらを「どこかに」保持するバリアントです（例：アプリケーションには直接アクセスできず、VM自体の機械にのみアクセスできる補助スタック-このような文字を含むストレージは、VMの実装について説明するときに「レジスタ」と呼ばれることもあります）、「レジスタ」を空にしてVMの通常のスタックに戻すマッチング。nPOP_KEEP nPUSH_KEPT n

于 2010-05-13T14:33:00.167 に答える
1

あなたはこれを間違った見方をしていると思います。古い変数をスタックからポップしてから新しい変数をプッシュする代わりに、すでにそこにある変数を（慎重に）再割り当てするだけです。これは、コードを同等の反復アルゴリズムに書き直した場合に発生する最適化とほぼ同じです。

このコードの場合：

 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"

スタックに何かをポップしたりプッシュしたりする必要はなく、単に再割り当てするだけです。
明らかに、これは、終了条件を2番目に配置することでさらに最適化でき、ジャンプをスキップできるため、操作が少なくなります。

 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;
}
于 2013-06-25T23:24:07.693 に答える