a21_opt02 の編集 - essen-wiki

* プログラミング言語における最適化について #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 という定数情報がぶつかることになる。
-このように各合流地点に情報がたまってくるので、それを各合流地点ごとに集計して全部重ねて、それでも残った定数情報は本当に定数だということです。
-最初のうちは定数だと思っていたけど実は定数ではなかった、みたいなことが起きたら、それはそのコード片からの分岐先に渡した情報も修正されなければいけないので、それも直します。
-これを繰り返して、もう新しい変化は起きなくなったら、それで情報は確定するので、「定数かもしれない」を「定数」に直して、この最適化を完了します。

//-要するに、変数の状態が「定数が入っている」「それ以外」の二択だったものを、「定数が入っている」「定数じゃないものが入っている」「変更していない」の三択に分けるのがポイントです。

//-プログラムを上から読んでいくのは同じですが、合流可能性がある場所から（もしくは関数の先頭）、次の合流可能性地点まで（もしくは無条件分岐まで、もしくはreturnまで）を「コード片」と呼ぶことにします。一つの関数は複数のコード片の集まりです。そして分岐命令を追跡すれば、どこからどこへ行く可能性があるのかは簡単に追跡できます。
//-それぞれのコード片について、まず始状態はやはりテーブルクリアから始めます。これはすべての変数に対して、「変更していない」ということを表します。そしてコードを読み進めていくと、いくつかの変数は書き換えられて、定数もしくは非定数が代入されていきます。それらはすべてテーブルに登録されていきます。
//-前回のアルゴリズムでは、変数に定数以外を代入した場合に、テーブルからその項目を消していましたが、今回は消さずに、非定数を代入したと記録します。

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

-上記では以下のアルゴリズムを紹介しました。
----
-この最適化を実現するアルゴリズムは簡単です。
-プログラムを上から順番に見ていくことにします（下から順番に見ていってもいい）。
-何か変数に「代入する命令」があったとき、その直後からその結果を使う命令がどこにあるかを探します（これは上から順番に見る）。つまり二重ループです。
-もし誰からも参照されないまま、新しい別の値を代入する命令にぶつかったら、それは「結果は使われていない」と判断できます。また値を利用する命令にぶつかったときも、「結果は使われている」と判断できます。・・・判断できたら命令を順番に調べていく内側のループからは抜けられます。
-悩ましいのは分岐命令や条件分岐命令にぶつかったときです。こうなると分岐先でどうなるのかを解析しないと判断できません。でもそれはちょっとめんどくさそうです（たとえ分かれ道がなくて単純そうな無条件分岐であっても、ただそれをたどっていくとかだと、無限ループとかの場合に出られなくなる恐れがある）。・・・ここを頑張れば最適化性能は間違いなく向上しますが、やっぱり面倒なので、分岐命令にぶつかったら、「もうよくわからん、わからんから結果はたぶん使うだろうということにしておこう」って私はやりました。それでも最適化は結構効きます。
-それで、上記の判定で「結果は使われていない」と判断できた場合に限り、その「代入する命令」は消してしまいます。
----
-しかしこのアルゴリズムでは、代入文の後に条件分岐などがあるとそれだけであきらめてしまい、以下のような記述を最適化できません。
 a = 1; // この代入は結局利用されないので不要。
 if (b == 0) { c = 1; }
 a = 0;
-これを何とかしたいわけです。

** (2-2)
-（今考えているアルゴリズム）
-基本的な考え方は、上記に似ています。違うのは、分岐命令に当たった時、解析をあきらめずに継続するところです。
-解析したことのある部分は覚えておいて、重複がないようにします。
-必要か不必要化を判定している命令の直後からトレースして、それで重複がないように検査して、可能性のあるどの経路を通ってもその結果を利用されないのであれば、それは捨ててもいい演算だと判断します。

* こめんと欄
#comment

タイムスタンプを変更しない

* プログラミング言語における最適化について #2
-(by [[K]], 2021.10.08)

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

* こめんと欄
#comment

テキスト整形のルールを表示する