C言語における末尾呼び出し最適化は比較的新しい
Tail-call optimization in C is relatively recent (lwn.net)
要約
C言語における末尾呼び出し最適化(TCO)は、長らく標準的な呼び出し規約ではサポートされていませんでしたが、2001年のGCCでの実装試行を経て、最近のGCCやClangコンパイラで特定の形式の末尾呼び出しがサポートされるようになりました。この進歩は、Gforthやインタプリタ開発など、コード効率が重要な分野での応用が期待されています。
全文翻訳
Tail-call optimization in C is relatively recent
Posted Aug 21, 2025 22:11 UTC (Thu) by anton (subscriber, #25547)
Parent article: Python, tail calls, and performance
Actually tail calls in C have not been around forever. The C calling convention has been that the callee does not remove any stuff the caller has put on the stack. The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m≤n parameters. That would not always work if the callee removed the arguments.
So the caller had to remove the arguments between the call and the following return, turning the call into a non-tail call.
When I looked in 1994 at the C compilers of the day, they did not perform tail-call optimization for the kind of usage shown in the article. In 2001 Mark Probst implemented tail-call optimization in GCC with a separate calling convention; he lists the limitations of the then-existing tail-call optimization in GCC in section 6.4, among them: "It cannot handle indirect calls" (which would have been used in tail calls for interpreter dispatch).
I have not looked at the issue since then (GCC's goto * was good enough (well, mostly)), and I had not much reason for assuming that something had changed wrt to GCC support for tail-calls (although one release note mentioned sibcalls, and I remember thinking that I should be checking that out.
Anyway, last year I read the paper on "Copy-and-Patch Compilation" by Xu and Kjolstad, and they use tail-call optimization. In any case, after reading that paper, I made some tests if gcc and clang can do tail-call optimization for the kind of tail calls shown in the article. And it works. And Xu and Kjolstad report that they use 100,000 code snippets, whereas we limit ourselves in Gforth to <2000 (for VM instructions, stack caching variations thereof, static superinstructions etc.). Being able to do 100,000 would allow us to use techniques that need too many different code snippets to be usable in a goto *-based system.
We have not gotten around to putting this into Gforth yet, so congratulations to the Python community for being there first.
末尾呼び出し最適化は比較的最近のもの
投稿日 2025年8月21日 22:11 UTC (木) by anton (subscriber, #25547)
親記事: Python、末尾呼び出し、およびパフォーマンス
実際、C言語における末尾呼び出しは、永遠に存在していたわけではありません。C言語の呼び出し規約では、呼び出し元がスタックに積んだものを呼び出し先が削除しないことになっていました。呼び出し元は int f(); という宣言を見ることができましたが、実際の呼び出しには n>0 個の引数が含まれる可能性があり、実際の関数は m≤n 個のパラメータを持つことができました。呼び出し先が引数を削除した場合、これは常にうまくいくとは限りませんでした。
そのため、呼び出し元は呼び出しとその後のリターンとの間で引数を削除する必要があり、呼び出しを末尾呼び出しではないものに変えていました。
1994年に当時のCコンパイラを調べたとき、記事で示されているような用途に対する末尾呼び出し最適化は行われていませんでした。2001年にMark ProbstはGCCで末尾呼び出し最適化を実装しました。彼は、セクション6.4で当時のGCCにおける末尾呼び出し最適化の制限を挙げており、その中には「間接呼び出しを処理できない」(これはインタプリタのディスパッチにおける末尾呼び出しに使われるだろう)というものがありました。
それ以降、この問題は調べていません(GCCの goto * は十分でした(まあ、ほとんどの場合))、GCCの末尾呼び出しサポートに関して何かが変わったと仮定する理由はあまりありませんでした(リリースノートでsibcallsに言及しているものがあり、それを確認すべきだと考えていたことを覚えています)。
いずれにせよ、昨年、XuとKjolstadによる「Copy-and-Patch Compilation」という論文を読み、彼らが末尾呼び出し最適化を使用していることを知りました。いずれにしても、その論文を読んだ後、gccとclangが記事で示されているような末尾呼び出しを最適化できるかどうかをテストしました。そして、それは機能します。XuとKjolstadは10万個のコードスニペットを使用していると報告していますが、私たちはGforthでは2000個未満(VM命令、スタックキャッシュのバリエーション、静的スーパーインストラクションなど)に制限しています。10万個を扱えるようになれば、goto * ベースのシステムでは使用するにはコードスニペットが多すぎる技術を使用できるようになります。
まだGforthにこれを組み込むまでには至っていませんが、Pythonコミュニティが先行したことに祝意を表します。