compiler-construction - お気に入りの抽象構文ツリーの最適化

Question

コンパイラを構築する場合、AST レベルでどのような最適化を行うのが最適でしょうか?

Answer 1

プログラムのある部分から別の部分にデータがどのように流れるかについての情報が必要なため、ほとんどの場合、ASTレベルで興味深い最適化を行うことはできません。データフローはASTの意味で暗黙的ですが、ASTだけを検査することによって簡単に決定することはできません。そのため、コンパイラやオプティマイザを構築する人々は、他のプログラム表現（シンボルテーブル、制御フローグラフ、到達定義、データフローを含む）を構築します。およびSSAフォームなど）。

言語のパーサーを持つことは、その言語を分析/操作するための簡単な部分です。あなたは良い仕事をするために他のすべてのものが必要です。

他のすべての表現がある場合は、ASTレベルで最適化を行うことを検討できます。コンパイラを構築するほとんどの人は気にしません。それらはデータフロー表現に変換し、それを単純に最適化します。ただし、変更を加えてソースコードを再現する場合は、ASTが必要です。また、ソースコードを再生成できるようにするためのprettyprinterも必要です。ここまで進んでいくと、ソースからソースへのプログラム変換システムになってしまいます。

DMS Software Reengineering Toolkitは、ASTを変換するシステムであり、これらの他のすべての表現を使用して、変換に必要な分析を可能にします。

Answer 2

AST (CFG などではなく) で実行するのが最も簡単な最適化は、末尾呼び出しの最適化です。次の形式のサブツリーが表示された場合:

RETURN
    CALL f
        ARGS x, y, ...

へのジャンプに置き換えることができますf。f(a, b)末尾呼び出しが表示される関数である場合、置換は次のように簡単です。

a = x; b = y
JUMP to root of tree

そのジャンプを特別な「再起動」ステートメントとして表現するのが最も簡単だと思います。これは、AST->CFG 変換が最初のノードに戻るエッジとして扱います。他の関数へのジャンプは、ローカル変数を設定するだけでなく、実際にどのように引数が渡されるかを前もって考え、下位レベルでこれを変換する準備をする必要があるため、少しトリッキーです。たとえば、AST には、現在のスタック フレームを引数で上書きし、それに応じてジャンプするように後のパスに指示できる特別なノードが必要になる場合があります。

Answer 3

AST で最適化を適用する利点の 1 つは、一部のバックエンド最適化パスの実行時間を短縮できることです。ただし、コードのさらなる最適化を妨げている可能性があるため、これらの最適化は節約して行う必要があると思います。

そうは言っても、ASTレベルまたはIR生成中に適用されるIMOの単純で興味深い最適化の1つは、(1 || 2)または(2 < 3 || A)などの形式のブール式の単純化です。最終結果。単純なのぞき穴の最適化も価値があると思います。