"静的"ループの最適化

Question

私は楽しいためにコンパイルされた言語を書いています。最近、私の最適化コンパイラを非常に頑強にするための蹴りに乗りました。私はいくつかのものを最適化するためのいくつかの方法を考え出しました。たとえば、2 + 2は常に4なので、（偽）{...}が完全に削除されてもコンパイル時に計算できます。私はループになった。いくつかの研究の後、私がしようとしていることは正確にアンローリングをループすることではないと思うが、それはまだ最適化技術である。私に説明させてください。

次のコードを使用してください。

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

人間として、私はここに座っていると、これは時間の100％だから

output("xxxxx"); 

に等価であることを行っていることを伝えることができ、他の言葉で、このループは「コンパイルすることができます完全に "出る"。ループアンローリングではありませんが、私が「完全に静的」と呼んでいるのは、セグメントの動作を変更する入力がないということです。私の考えは、完全に静的なものは単一の値に解決できるということです。入力に依存するものや、条件付き出力をさらに最適化することはできません。だから、マシンの観点から、私は何を考慮する必要がありますか？ループを「完全に静的にする」とは何ですか？

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

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

Answer 1

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

ビット数を制限しましょう：ループのためだけに番号オーバーフローが発生しないようにしてください（ただし、continueなどを使用する場合を除いて、完全なforループに変換されることもあります）、中断なし、forループ内の制御変数の変更。

for (var i = S; E(i); i = U(i)) ... E（i）とU（i）が象徴的に操作することができる式です

。

U(i) = i + CONSTANT：nサイクル目iの値がS + n * CONSTANT

U(i) = i * CONSTANTです：nサイクル目iの値がS * CONSTANT^n

U(i) = i/CONSTANTです：n番目比較的容易であるいくつかのクラスがあります。 iの値は、S * CONSTANT^-n

です。 0：nサイクル目iの値が(S + n * CONSTANT) % M

およびいくつかの他の非常に簡単な組み合わせ（およびいくつかの非常に困難なもの）である

ループが終了するかどうかの判定は、E(i(n))が偽である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の時代から来て、あまりにも困難ではありません。説明されているもの（またはバリアント）が最も一般的なタイプのプラクティスですが、シナリオを解決することはさらに困難であり、不可能です。