c - C末尾呼び出しの最適化

Question

Cは末尾呼び出しの除去を実行しないとよく言われます。規格では保証されていませんが、とにかくまともな実装で実際に実行されているのではないでしょうか。成熟した、適切に実装されたコンパイラのみを対象とし、あいまいなプラットフォーム用に作成されたプリミティブコンパイラへの絶対的な最大移植性を気にしないと仮定すると、Cで末尾呼び出しの削除に依存するのは合理的ですか？

また、末尾呼び出しの最適化を標準から除外する理由は何でしたか？

Answer 1

「Cは末尾呼び出しの除去を実行しません」のようなステートメントは意味がありません。あなたが正しくあなた自身に気づいたように、このようなことは完全に実装に依存します。そして、はい、適切な実装であれば、末尾再帰を[同等の]サイクルに簡単に変えることができます。もちろん、Cコンパイラは通常、特定の各コードでどの最適化が行われ、どの最適化が行われないかについては保証しません。あなたはそれをコンパイルして自分の目で確かめなければなりません。

Answer 2

最新のコンパイラは、最適化をオンにすると末尾呼び出しの最適化を実行できますが、スタックトレースを取得したり、コードにステップイン/ステップアウトしたりできるように、デバッグビルドはおそらくそれなしで実行されます。この状況では、末尾呼び出しの最適化は望ましくありません。

末尾呼び出しの最適化は必ずしも望ましいとは限らないため、コンパイラの作成者にそれを義務付けることは意味がありません。

Answer 3

末尾呼び出しの最適化は、多くの再帰が予想または必要な場合にのみ保証する必要があると思います。つまり、関数型プログラミングスタイルを奨励または強制する言語です。（これらの種類の言語では、ループが強く推奨されていないか、エレガントでないと認識されているか、おそらく言語に完全に欠けていることがわかる場合がありますfor。そのwhileため、これらすべての理由、およびおそらくそれ以上の理由で再帰に頼ることになります。）

Cプログラミング言語（IMHO）は、関数型プログラミングを念頭に置いて設計されていないことは明らかです。再帰を優先して一般的に使用されるすべての種類のループ構造があります：for、、。このような言語では、動作するプログラムを保証する必要がないため、標準で末尾呼び出しの最適化を規定することはあまり意味がありません。do .. whilewhile

whileこれを、ループのない関数型プログラミング言語ともう一度比較してください。これは、再帰が必要になることを意味します。つまり、言語は、多くの反復でスタックオーバーフローが問題にならないようにする必要があります。したがって、そのような言語の公式標準は、末尾呼び出しの最適化を規定することを選択する可能性があります。

---

PS：末尾呼び出しの最適化に関する私の議論のわずかな欠陥に注意してください。終わりに向かって、私はスタックオーバーフローについて言及します。しかし、関数呼び出しには常にスタックが必要だと誰が言いますか？一部のプラットフォームでは、関数呼び出しがまったく異なる方法で実装される場合があり、スタックオーバーフローが問題になることはありません。これは、標準で末尾呼び出しの最適化を規定することに対するさらに別の議論になります。（しかし、誤解しないでください。スタックがなくても、このような最適化のメリットを確認できます！）

Answer 4

あなたの最後の質問に答えるために：標準は絶対に最適化について何も言明すべきではありません。実装が多かれ少なかれ難しい環境があるかもしれません。

Answer 5

構造による証明が好きな人のために、ここに素晴らしい末尾呼び出しの最適化とインラインを行うgodboltがあります：https ：//godbolt.org/z/DMleUN

ただし、最適化を-O3にクランクすると（または、数年待つか、別のコンパイラを使用する場合は間違いありません）、最適化によってループ/再帰が完全に削除されます。

これは、-O2を使用しても単一の命令に最適化する例です：https ：//godbolt.org/z/CNzWex

Answer 6

言語標準は、コンパイラの実装方法ではなく、言語の動作を定義します。最適化は常に必要とは限らないため、必須ではありません。コンパイラーは、ユーザーが必要に応じて最適化を有効にし、同様にオフにすることができるように、オプションを提供します。コンパイラの最適化は、コードをデバッグする機能に影響を与える可能性があるため（Cを行ごとにアセンブリに一致させることが難しくなります）、ユーザーの要求があった場合にのみ最適化を実行するのが理にかなっています。

Answer 7

末尾呼び出しの最適化によってABIが破損する可能性がある場合や、少なくともセマンティックを保持する方法で実装することが非常に難しい場合があります。たとえば、共有ライブラリの位置に依存しないコードについて考えてみます。一部のプラットフォームでは、さまざまな異なるアプリケーションがすべて同じ機能に依存している場合に、プログラムがライブラリに対して動的にリンクしてメインメモリを節約できます。このような場合、ライブラリは1回ロードされ、システム上の唯一のアプリケーションであるかのように、プログラムの各仮想メモリにマップされます。UNIXおよびその他のシステムでは、これはライブラリに位置に依存しないコードを使用することで実現されるため、アドレス指定は固定アドレス空間に対して絶対的ではなく、オフセットに対して相対的です。ただし、多くのプラットフォームでは、位置に依存しないコードを末尾呼び出しに最適化してはなりません。関連する問題は、プログラムをナビゲートするためのオフセットをレジスタに保持する必要があることです。Intel 32ビットでは、%ebx呼び出し先が保存したレジスタであるが使用されます。他のプラットフォームはその概念に従います。通常の呼び出しを使用する関数とは異なり、末尾呼び出しを展開する関数は、サブルーチンに分岐する前に、呼び出し先が保存したレジスタを復元する必要があります。通常、これは問題ありません。この時点で、最上位の呼び出し関数はに格納されている値を考慮しません%ebxが、位置に依存しないコードは、ジャンプ、呼び出し、または分岐コマンドごとにこの値に依存します。

その他の問題は、オブジェクト指向言語（C ++）でのクリーンアップが保留されている可能性があります。つまり、関数の最後の呼び出しは実際には最後の呼び出しではありません。クリーンアップはそうです。したがって、これが当てはまる場合、コンパイラは通常最適化を行いません。

またsetjmp、longjmpもちろん問題があります。これは、関数が実際に終了する前に、関数が複数回実行を終了できることを効果的に意味するためです。コンパイル時に最適化するのが難しいか不可能です！

おそらくもっと技術的な理由が考えられます。これらはいくつかの考慮事項です。

Answer 8

コンパイラーは、関数が別の関数を呼び出した後に何もする必要がない状況を認識し、その呼び出しをジャンプに置き換えるのが一般的です。それが安全にできるケースの多くは簡単に認識でき、そのようなケースは「安全なぶら下がっている果物」と見なされます。ただし、このような最適化を実行できるコンパイラーでも、いつ実行する必要があるか、または実行するかが常に明確であるとは限りません。さまざまな要因により、末尾呼び出しのコストが通常の呼び出しのコストよりも高くなる可能性があり、これらの要因は常に予測できるとは限りません。たとえば、関数が。で終わる場合return foo(1,2,3,a,b,c,4,5,6);、a、b、およびcをレジスタにコピーし、スタックをクリーンアップしてから、渡すための引数を準備するのが実用的かもしれませんが、foo(a,b,c,d,e,f,g,h,i);同様に処理するのに十分なレジスタがない場合があります。

言語に特別な「末尾呼び出し」構文があり、可能な限り末尾呼び出しを行うコンパイラーが必要であり、それ以外の場合はコンパイルを拒否する場合、コードはそのような関数が任意の深さでネストできると安全に想定できます。ただし、通常の呼び出し構文を使用する場合、コンパイラーが「通常の」呼び出し構文よりも安価に末尾呼び出しを実行できるかどうかを知る一般的な方法はありません。