メインコンテンツまでスキップ

WebAssembly 尾部呼び出し

· 約11分
Thibaud Michaud, Thomas Lively

V8 v11.2でWebAssemblyの尾部呼び出しをリリースします！この記事では、この提案の概要を簡単に説明し、EmscriptenでのC++コルーチンの興味深い使用例を示し、V8が尾部呼び出しを内部でどのように処理するかを紹介します。

尾部呼び出し最適化とは？​

ある呼び出しが現在の関数から戻る前に実行される最後の命令である場合、それは尾部位置にあると言われます。コンパイラは、そのような呼び出しを最適化して、呼び出し元のフレームを破棄し、呼び出しをジャンプに置き換えることができます。

これは特に再帰関数にとって有用です。例えば、次のC関数はリンクリストの要素の合計を計算します：

int sum(List* list, int acc) {
  if (list == nullptr) return acc;
  return sum(list->next, acc + list->val);
}

通常の呼び出しでは、これは𝒪(n)のスタック空間を消費します：リストの各要素が呼び出しスタックに新しいフレームを追加します。リストが十分に長い場合、スタックが非常に速くオーバーフローする可能性があります。呼び出しをジャンプに置き換えることにより、尾部呼び出し最適化はこの再帰関数を本質的に𝒪(1)スタック空間を使用するループに変換します：

int sum(List* list, int acc) {
  while (list != nullptr) {
    acc = acc + list->val;
    list = list->next;
  }
  return acc;
}

この最適化は特に関数型言語にとって重要です。それらは再帰関数に大いに依存しており、Haskellのような純粋な関数型言語はループ制御構造さえ提供していません。任意の種類のカスタム反復は、何らかの方法で通常再帰を使用します。尾部呼び出し最適化がなければ、非自明なプログラムではスタックオーバーフローが非常に速く発生するでしょう。

WebAssemblyの尾部呼び出し提案​

Wasm MVPには関数を呼び出す方法が2つあります：callとcall_indirectです。WebAssemblyの尾部呼び出し提案はそれらに対する尾部呼び出しカウンターパートであるreturn_callとreturn_call_indirectを追加します。これは、ツールチェーンが実際に尾部呼び出し最適化を行って適切な呼び出し種別を出力する責任を負い、パフォーマンスとスタック空間の使用に対してさらに制御できることを意味します。

再帰的なフィボナッチ関数を見てみましょう。Wasmバイトコードは完全性のためにテキスト形式でここに含められていますが、次のセクションでC++で見つけることができます：

(func $fib_rec (param $n i32) (param $a i32) (param $b i32) (result i32)
  (if (i32.eqz (local.get $n))
    (then (return (local.get $a)))
    (else
      (return_call $fib_rec
        (i32.sub (local.get $n) (i32.const 1))
        (local.get $b)
        (i32.add (local.get $a) (local.get $b))
      )
    )
  )
)

(func $fib (param $n i32) (result i32)
  (call $fib_rec (local.get $n) (i32.const 0) (i32.const 1))
)

任意の時点でfib_recフレームは1つしかなく、それは次の再帰呼び出しを実行する前に自分自身を解除します。基本ケースに到達すると、fib_recは結果aを直接fibに返します。

尾部呼び出しの一つの観測可能な結果は（スタックオーバーフローのリスクが減少することを除いて）、尾部呼び出し元がスタックトレースに現れないことです。それらは捕捉された例外のスタックプロパティにも、DevToolsスタックトレースにも現れません。例外がスローされたり、実行が一時停止されたりした時点では、尾部呼び出し元フレームは消えており、V8がそれらを復元する方法はありません。

Emscriptenで尾部呼び出しを使用する​

関数型言語はしばしば尾部呼び出しに依存しますが、CまたはC++プログラマーとしてそれを使用することも可能です。Emscripten（およびEmscriptenが使用するClang）は、呼び出しを尾部呼び出しにコンパイルする必要があることをコンパイラに伝えるmusttail属性をサポートしています。例として、フィボナッチ数列の第n項目（整数が大きすぎるため2^32でmod）を計算するこの再帰的な実装を考えてみましょう：

#include <stdio.h>

unsigned fib_rec(unsigned n, unsigned a, unsigned b) {
  if (n == 0) {
    return a;
  }
  return fib_rec(n - 1, b, a + b);
}

unsigned fib(unsigned n) {
  return fib_rec(n, 0, 1);
}

int main() {
  for (unsigned i = 0; i < 10; i++) {
    printf("fib(%d): %d\n", i, fib(i));
  }

  printf("fib(1000000): %d\n", fib(1000000));
}

emcc test.c -o test.jsでコンパイルした後、Node.jsでこのプログラムを実行するとスタックオーバーフローエラーが発生します。これを修正するには、fib_recのリターンに__attribute__((__musttail__))を追加し、コンパイル引数に-mtail-callを追加します。これで生成されたWasmモジュールには新しい尾部呼び出し命令が含まれるため、Node.jsに--experimental-wasm-return_callを渡す必要がありますが、スタックはもはやオーバーフローしません。

相互再帰を使用する例も次の通りです：

#include <stdio.h>
#include <stdbool.h>

bool is_odd(unsigned n);
bool is_even(unsigned n);

bool is_odd(unsigned n) {
  if (n == 0) {
    return false;
  }
  __attribute__((__musttail__))
  return is_even(n - 1);
}

bool is_even(unsigned n) {
  if (n == 0) {
    return true;
  }
  __attribute__((__musttail__))
  return is_odd(n - 1);
}

int main() {
  printf("is_even(1000000): %d\n", is_even(1000000));
}

これらの例は簡単すぎるので、-O2でコンパイルすれば、コンパイラはスタックを使い切ることなく答えを事前計算することができますが、より複雑なコードではそうではありません。実際のコードでは、musttail属性はこのブログ記事でJosh Habermanによって説明されているように、高性能なインタープリタループを書く際に役立つことがあります。

musttail属性以外にも、C++はもう1つの機能のために末尾呼び出しに依存しています。それは、C++20のコルーチンです。C++20のコルーチンと末尾呼び出しの関係については、Lewis Bakerのこのブログ記事で非常に詳しく説明されていますが、要約すると、ソースコードでは問題があるようには見えないのに、微妙にスタックオーバーフローを引き起こすパターンでコルーチンを使用することが可能です。この問題を解決するために、C++委員会はコンパイラが「対称転送」を実装してスタックオーバーフローを避ける要件を追加しました。これにより実際には内部的に末尾呼び出しを使用することになります。

WebAssemblyの末尾呼び出しが有効になっている場合、Clangは前述のブログ記事で説明されているように対称転送を実装しますが、末尾呼び出しが有効でない場合、Clangは対称転送なしでコードを静かにコンパイルします。この場合、スタックオーバーフローを引き起こす可能性があり、技術的には正しいC++20の実装ではありません！

変化を確認するには、Emscriptenを使用して上記のブログ記事の最後の例をコンパイルし、末尾呼び出しが有効な場合のみスタックが溢れるのを回避できることを観察してください。最近修正されたバグのため、これはEmscripten 3.1.35以降でのみ正しく動作します。

V8での末尾呼び出し​

前述のように、末尾位置での呼び出しを検出するのはエンジンの責任ではありません。これはツールチェーン側で実行されるべきです。そのため、TurboFan（V8の最適化コンパイラ）が残っている唯一のタスクは、呼び出しの種類とターゲット関数の署名に基づいて適切な命令列を生成することです。先ほどのフィボナッチの例では、スタックは以下のようになります。

TurboFanでのシンプルな末尾呼び出し

左側ではfib_rec（緑色）内であり、fib（青色）によって呼び出され、再帰的にfib_recを末尾呼び出ししようとしています。まず、現在のフレームをフレームポインタとスタックポインタをリセットして巻き戻します。フレームポインタは「Caller FP」スロットから読み取ることで以前の値に戻ります。スタックポインタは親フレームのトップまで移動し、さらに潜在的なスタックパラメータおよびスタック戻り値用のスペース分移動します（この場合0、すべてがレジスタによって渡される）。パラメータはfib_recのリンクに従って期待されるレジスタに移動されます（図には表示されていません）。最後に新しいフレームを作成してfib_recを実行します。

fib_recはn == 0になるまでこのように自己を巻き戻し、巻き戻していき、最終的にfibに対してレジスタでaを返します。

これはすべてのパラメータと戻り値がレジスタに収まるシンプルなケースであり、呼び出し元と呼び出し先が同じ署名を持つ場合です。一般的なケースでは、複雑なスタック操作を行う必要があるかもしれません。

  • 古いフレームから送信パラメータを読み取る
  • パラメータを新しいフレームに移動する
  • 呼び出し先のスタックパラメータ数に応じて戻りアドレスを上下に移動させることでフレームサイズを調整する

これらのすべての読み取りと書き込みは互いに競合する可能性があり、同じスタックスペースを再利用しています。これは単純な呼び出しとは大きく異なり、スタックパラメータと戻りアドレスをスタックの上にプッシュするだけです。

TurboFanでの複雑な末尾呼び出し

TurboFanは「ギャップリゾルバ」と呼ばれるコンポーネントを使用して、ソースと宛先間の干渉を解決する適切な移動シーケンスを生成し、セマンティクスを並列に実行するべき移動リストを処理します。競合が非循環的である場合、これは単にすべてのソースを上書きされる前に読み取るよう移動を並べ替える問題にすぎません。循環的競合の場合（例：2つのスタックパラメータを交換する場合）、これは一方のソースを一時レジスタまたは一時スタックスロットに移動して循環を解除することを含む場合があります。

Liftoff（ベースラインコンパイラ）でも末尾呼び出しがサポートされています。実際にはこれがサポートされないとベースラインコードがスタック領域を使い果たす可能性があります。しかし、この段階では最適化されていません。Liftoffは通常の呼び出しのようにパラメータ、戻りアドレス、フレームポインタをプッシュしてフレームを完成させ、その後すべてを下方に移動して呼び出し元のフレームを破棄します。

Liftoffにおける末尾呼び出し

ターゲット関数へジャンプする前に、FPレジスタに呼び出し元のFPをポップしてその以前の値を復元し、ターゲット関数がプロローグで再度 FP をプッシュできるようにします。

この戦略では、不必要な移動に関する競合を解析または解決する必要がないため、コンパイルが高速化されます。生成されるコードは遅くなりますが、最終的に関数が十分にホットであれば TurboFanに昇格します。