a21_opt02 のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_opt02 へ行く。
- 1 (2021-10-08 (金) 08:42:55)
- 2 (2021-10-08 (金) 14:09:32)
- 3 (2021-10-08 (金) 22:10:48)
- 4 (2021-10-10 (日) 16:43:12)

プログラミング言語における最適化について #2

(by K, 2021.10.08)

↑

(0)

この記事は、以下の2つの話からの派生記事です。
- 「10日くらいでできる！プログラミング言語自作入門」 → a21_txt01
- HLX-002 → a21_hlx002

↑

(1-1)

「プログラミング言語における最適化について」（a21_opt）では、(3-1)として、
- コンパイル時に答えが確定しているものは、定数に置き換えてしまう。
という最適化を紹介しました。これの話の続きです。

上記では以下のアルゴリズムを紹介しました。

この最適化を実現するアルゴリズムは簡単です。
プログラムを上から順番に見ていくことにします。
もし変数に定数が代入されたら、この変数の値は〇〇である、とテーブルに登録しておきます。
もし定数ではない値が代入されたら、もう変数の値は不定なので、もしテーブルにその変数が登録されていればそれを消しますし、登録されていなければ何もしません。
テーブルに登録された変数を参照された場合は、それを全部定数に置換してしまいます。
ラベル定義文やforやwhileの先頭は繰り返しやcontiuneで合流が発生する可能性があるところです。そうなると合流の際に変数の値がどうなっているかわかったものではないので、テーブルはクリアしてしまいます。forやwhileの直後の文もbreakなどで飛んでくるので、テーブルのクリアが必要です。そんな感じで、合流の可能性があるところでは全部テーブルクリアです。
置換の結果（もしくは置換する前から）式の一部または全部が定数だけで構成されていたら、そこは計算してしまって計算値と置換します。
こうして最後までプログラムをチェックし終わったら、それでおしまいです。
ちなみにプログラム内で一度でもポインタを取得した変数（p = &i; としたときのiのこと）は、そのポインタを使って中身を書き換えたり読んだりする可能性があります。それはいつ起こるか簡単にはわかりません。だからそういう変数に対しては、たとえ定数の代入があってもその後も定数のままでいると仮定することなく、変数扱いにします。
ここも頑張ればもっと最適化がうまくなるのですが、それをやると大変なので、面倒なら無理せずに変数扱いにしてしまいましょう。それでも多くのケースで十分に最適化はできます。

しかしこのアルゴリズムでは、たとえば関数の冒頭で一度だけ定数で初期化されて、それ以降一度も上書きされない変数があっても、最初の合流ポイントでテーブルクリアされてしまい、せっかくの定数が生かされません。これをどうにかしてやりたいと思いました。・・・もちろんできるだけ難しくないアルゴリズムで。

↑

(1-2)

（今考えているアルゴリズム）
基本的な考え方は、上記に似ています。違うのは、合流可能性のあるところに来ても、完全にはクリアしないということです。「定数かもしれない」に切り替えます。ただし、それだと定数ではないものまで定数扱いする恐れがあるので、最初のターンでは定数だろうと思われても、定数への置換はやりません（保留する）。合流地点よりあとで定数が代入されたものについては、定数に違いないので、それはすぐに定数に置換していきます。
もし途中で条件分岐などでほかの合流地点に行くときは、その時のテーブルの状態をその合流地点に関連付けて記録しておきます。その際に、もしある地点からの合流では「a=1」という定数で、別の地点からの合流で「a=2」という定数であれば、それは定数なんかではなく変数だとわかります。
```
if (...) { a = 1; } else { a = 2; }
// ここは上記のifに対する合流地点。 ここでは a=1 という定数情報と a=2 という定数情報がぶつかることになる。
```
このように各合流地点に情報がたまってくるので、それを各合流地点ごとに集計して全部重ねて、それでも残った定数情報は本当に定数だということです。・・・最初のうちは定数だと思っていたけど実は定数ではなかった、みたいなことが起きたら、それはそのコード片からの分岐先に渡した情報も修正されなければいけないので、それも直します。・・・これを繰り返して、もう新しい変化は起きなくなったら、それで情報は確定するので、「定数かもしれない」を「定数」に直して、この最適化を完了します。

↑

(2-1)

「プログラミング言語における最適化について」（a21_opt）では、(3-2)として、
- 結果が利用されない命令は消す。
という最適化を紹介しました。これの話の続きです。

（つづく）

↑

こめんと欄

コメント	お名前	NameLink