1

私はコンパイラーを書いています、そして私は最適化に関するリソースを探しています。私はマシンコードにコンパイルしているので、実行時に何でも問題外です。

私が最近探していたのは、コードの最適化を減らし、セマンティック/高レベルの最適化を増やすことです。例えば：

free(malloc(400)); // should be completely optimized away

これらの関数が完全にインライン化されていても、最終的にはインライン化できないOSメモリ関数を呼び出す可能性があります。特別な場合のルールをコンパイラーに組み込むことなく、そのステートメントを完全に排除できるようにしたいと思います（結局のところ、これmallocは単なる別の関数です）。

もう一つの例：

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

bこの状況では、の容量をに初期化できるようにしたいと思いますstr.Length + 2（メモリを無駄にすることなく、結果を正確に保持するのに十分です）。

正直なところ、どこから始めればいいのかわからないので、どこかで始めたいと思っていました。同様の分野で行われた作業はありますか？一般的な意味でこのようなものを実装しているコンパイラはありますか？

4

2 に答える 2

2

2 つ以上の操作にわたって最適化を行うには、これら 2 つの操作の代数関係を理解する必要があります。問題領域で操作を表示すると、多くの場合、そのような関係があります。

ストレージ割り当てドメインでは free と malloc が逆であるため、 free(malloc(400)) が可能です。多くの操作には逆があり、それらが逆であることをコンパイラーに教え、一方のデータフローの結果が無条件に他方に流れることを実証することが必要です。逆数が実際に逆数であり、どこかに驚きがないことを確認する必要があります。a/x*x は値 a のように見えますが、x がゼロの場合はトラップが発生します。トラップを気にしない場合、それは逆です。トラップを気にする場合、最適化はより複雑になります: (if (x==0) then trap() else a) 除算が高価であると思われる場合でも、これは適切な最適化です。

他の「代数的」関係も可能です。たとえば、冪等の操作があります。変数をゼロにする (何かを同じ値に繰り返し設定する) などです。1 つのオペランドが恒等要素のように機能する操作があります。X+0 ==> X for any 0. X と 0 が行列の場合でも、これは真であり、時間を大幅に節約できます。

コードが何を行っているかについて抽象的に推論できる場合、他の最適化が発生する可能性があります。「抽象的解釈」は、結果をさまざまな興味深いビン (たとえば、この整数は不明、ゼロ、負、または正) に分類することによって、値について推論するための一連の手法です。これを行うには、どのビンが役立つかを判断し、各ポイントで抽象値を計算する必要があります。これは、カテゴリに対するテストがある場合 (たとえば、「if (x<0) { ... 」) で、x が 0 未満であることを抽象的に知っている場合に便利です。条件を最適化して取り除くことができます。

もう 1 つの方法は、計算が何を行っているかを記号的に定義し、計算をシミュレートして結果を確認することです。これが、必要なバッファーの有効サイズを計算する方法です。ループが開始する前にバッファ サイズをシンボリックに計算し、すべての反復でループを実行した場合の効果をシミュレートしました。このためには、プログラムのプロパティを表す記号式を作成し、そのような式を構成し、そのような式が使用できないほど複雑になったときに単純化できる必要があります (一種の抽象解釈スキームへのフェード)。また、そのようなシンボリック計算では、上で説明した代数的特性を考慮に入れる必要があります。これをうまく行うツールは数式の構築に優れており、プログラム変換システムは多くの場合、このための優れた基盤です。DMS ソフトウェア リエンジニアリング ツールキット.

難しいのは、どの最適化を実行する価値があるかを判断することです。なぜなら、膨大な量のものを追跡し続けることができず、それが報われない可能性があるからです。コンピューター サイクルは安くなってきているため、コンパイラでコードのより多くのプロパティを追跡することは理にかなっています。

于 2009-08-27T23:57:11.007 に答える
1

ブロードウェイのフレームワークは、あなたが探しているものと同じかもしれません。「ソースからソースへの変換」に関する論文もおそらく啓発的でしょう。

于 2009-08-27T19:14:26.770 に答える