8

私は趣味でコンパイル済み言語を書いていますが、最近、最適化コンパイラを非常に堅牢にすることに熱中しています。たとえば、2 + 2 は常に 4 であるため、コンパイル時にその計算を行うことができ、if(false){ ... } を完全に削除することができます。ループになってしまいました。いくつかの調査の後、私がやろうとしていることは正確にはループ展開ではないと思いますが、それでも最適化手法です。説明させてください。

次のコードを取ります。

String s = "";
for(int i = 0; i < 5; i++){
    s += "x";
}
output(s);

人間として、私はここに座って、これが 100% の確率で

output("xxxxx");

つまり、このループは完全に「コンパイル」することができます。これはループ展開ではありませんが、私が「完全に静的」と呼んでいるもの、つまり、セグメントの動作を変更する入力はありません。私の考えでは、完全に静的なものはすべて単一の値に解決でき、入力に依存するものや条件付き出力を作成するものはもちろん、それ以上最適化することはできません。では、マシンの観点からは、何を考慮する必要があるでしょうか? ループを「完全に静的」にするのは何ですか?

分類方法を理解する必要がある 3 種類のループを考え出しました。入力に関係なく、毎回の実行後に常に同じマシン状態で終了するループ、決して完了しないループ、およびどちらか一方を理解できないループ。私がそれを理解できない場合（動的入力に基づいて実行回数が条件付きで変更されます）、最適化について心配することはありません。無限のループは、プログラマーが特に抑制しない限り、コンパイル エラー/警告になります。毎回同じループは、ループせずに、マシンを適切な状態にするために直接スキップする必要があります。

もちろん、最適化する主なケースは、内部のすべての関数呼び出しも静的である静的ループの反復です。ループに動的コンポーネントがあるかどうかを判断するのは簡単です。動的でない場合は、静的でなければならないと思います。私が理解できないのは、それが無限になるかどうかを検出する方法です。誰もこれについて何か考えがありますか？これが停止問題のサブセットであることはわかっていますが、解決可能だと感じています。停止の問題は、プログラムの一部のサブセットについては、それが永久に実行される可能性があるかどうかを判断できないという事実による問題です。どこで停止するか、どこで停止しないかですが、最初に 3 つの状態を区別する必要があります。

4

1 に答える 1

2

これは、いくつかのクラスに対して定義できる一種のシンボリック ソルバーのように見えますが、一般的にはそうではありません。

要件を少し制限してみましょう: 数値オーバーフローなし、for ループのみ (while は、continue などを使用する場合を除いて完全な for ループに変換される場合があります)、ブレークなし、for ループ内の制御変数の変更なし。

for (var i = S; E(i); i = U(i))...

ここで、E(i) と U(i) は記号的に操作できる式です。比較的簡単なクラスがいくつかあります。

U(i) = i + CONSTANT: n-th サイクルの値iはS + n * CONSTANT

U(i) = i * CONSTANT: n-th サイクルの値iはS * CONSTANT^n

U(i) = i / CONSTANT: n-th サイクルの値iはS * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n-th サイクルの値iは(S + n * CONSTANT) % M

他のいくつかの非常に簡単な組み合わせ (およびいくつかの非常に難しい組み合わせ)

ループが終了するかどうかを判断することは、falseのn場所を検索することです。E(i(n))これは、多くの場合、シンボリック操作によって実行できますが、ソルバーの作成には多くの作業が必要です。

例えば

  • for(int i = 0; i < 5; i++)、
  • i(n) = 0 + n * 1 = n、E(i(n))=> not(n < 5)=>
  • n >= 5=>停止n = 5
  • for(int i = 0; i < 5; i--)、
  • i(n) = 0 + n * -1 = -n、E(i(n))=> not(-n < 5)=> -n >= 5=>
  • n < -5-nは非負の整数であるため、これが真になることはありません - 停止することはありません
  • for(int i = 0; i < 5; i = (i + 1) % 3)、
  • E(i(n))=> not(n % 3 < 5)=> n % 3 >= 5=> これは決して真実ではありません => 止まらない
  • for(int i = 10; i + 10 < 500; i = i + 2 * i)=>
  • for(int i = 10; i < 480; i = 3 * i)、
  • i(n) = 10 * 3^n、
  • E(i(n))=> not(10 * 3^n < 480)=> 10 * 3^n >= 480=> 3^n >= 48=> n >= log3(48)=> n >= 3.5...=>
  • n は全体なので => 停止しますn = 4

他のケースについては、すでに解決できるケースに変換できればよいのですが...

記号操作の多くのトリックは Lisp 時代から来ており、それほど難しくありません。説明されているもの (またはバリアント) は最も一般的な型のプラクティスですが、解決が困難または不可能なシナリオが多数あります。

于 2012-05-02T17:23:37.283 に答える