コンパイラーの最適化に関する質問

Question

1. コンパイラが繰り返し部分式の再計算を排除する方法にはどのようなものがありますか？部分式をどのように追跡しますか？そして、繰り返したものをどのように識別しますか？
2. ビットごとの演算子の使用に加えて、一般的なコンパイラが使用する強度低減技術にはどのようなものがありますか？

Answer 1

1. 私は、多くのコンパイラがSSAPRE（静的単一割り当て部分冗長性排除）を使用して、繰り返し式を排除すると考えています。これには、 SSAフォームのコードが必要です。これにより、さらに多くの最適化が可能になります。

2. これについてはよくわかりませんが、このLLVMパスのリストを見てください。 LLVM はコンパイラー向けの最適化IRであり、GCCよりも高速です。各パスの簡単な説明があります。さらに情報が必要な場合は、これらのパスのLLVMソースをご覧ください。 C ++で記述されていますが、非常に簡潔で理解しやすいものです。

編集：ところで、コンパイラを開発している場合、LLVMを強くお勧めします。LLVMは非常に使いやすく、高度に最適化されたコードを生成します。

Answer 2

1の場合、探している最適化の名前は共通部分式除去（CSE）です。表現に応じて、これはかなり簡単です。通常、コンパイラーは、操作が可能な限り分解され、線形化されるプログラムの中間表現を持ちます。たとえば、式 c = a * b + a * b は、次のように分類できます。

v1 = a * b
v2 = a * b
c = v1 + v2

したがって、同じ演算子とオペランドを持つ操作を探すことで、非常に低いレベルでCSEを実行できます。重複（この場合はv2）が発生すると、そのすべてのインスタンスを元のインスタンスに置き換えます。したがって、上記のコードを次のように単純化できます。

v1 = a * b
c = v1 + v1

これは通常、各変数を1回だけ割り当てることを想定しています（単一の静的割り当てフォーム）が、そのような制限なしでこのようなものを実装できます。ブランチ間でこの最適化を実行しようとすると、これはより複雑になります。 Zifreが言及しているように、部分的な冗長性の排除を検討してください。

いずれにせよ、いくつかの基本的な改善があり、追跡する必要があるのは基本的な表現だけです。これをさらに一歩進めて、算術恒等式を探すことができます。たとえば、 a * b は b * a と同じです。また、 x *（y + z）= x * y + x * z 。これにより、最適化がより複雑になり、パフォーマンスが大幅に向上するかどうかは明らかではありません。逸話的に、CSE最適化の利点のほとんどは、配列アクセスのようなアドレス計算から得られ、上記のような複雑なIDは必要ありません。

2の場合、どの強度の低減が有用かは、実際にコンパイルするアーキテクチャによって異なります。通常、これには乗算と除算をシフト、加算、減算に変換するだけです。

Answer 3

これらのテーマに関する2つの参考文献を強くお勧めします：

1. 高度なコンパイラ設計＆amp;実装 by Steven S. Muchnick
2. 最適化コンパイラの構築 Robert Morgan

Muchnickの本は正式な側面にありますが、非常に読みやすく、重要な最適化手法のすべての良い説明があります。モーガンの本は、はるかに実践的な感覚を持ち、最適化手法に焦点を当てたコンパイラプロジェクトの優れた基盤となります。どちらの本も字句解析や構文解析について多くのことを述べていません。これらの主題の知識が想定されています。

Answer 4

推奨事項のリストにもう1冊の本を追加するには、＆quot; Hacker's Delight＆quotをチェックしてください。 ; by Henry S. Warren。これは、整数除算を乗算に変換するなど、一般的な操作を最適化するための手法の大要です。

Answer 5

部分冗長除去（PRE）を探しています。 CSE（他の回答から）とループ不変コードの動きの両方がPREに含まれています。 （PREのバリエーションはLazy Code Motionで、これが最適だと思います）。

キースクーパーの講義ノートをご覧ください。テクニックを非常によく説明しているようです。

SSAPREを使用しないしない。知る限り、これにはHSSAと呼ばれる特定の形式のSSAが必要です。これにはいくつかの欠点があります。

• かなり複雑です
• グローバルな値の番号付けが必要です（したがって、SSAPREは既に存在すると予想される値の番号付けを提供しません）。
• 言語がスタック変数へのポインタをサポートしていない場合は何も提供しません（サポートしている場合は、独自の分析の記述を停止してLLVMまたはgccを使用します）。
• gccはしばらくHSSAを使用していましたが、HSSAから遠ざかりました。
• LLVMはそれを実験しましたが、知る限りではもう使用していません。

編集：

Muchnickの本には詳細な説明があり、別の回答にリンクされています。