プログラミング言語における最適化について #2
(0)
(1-1)
- 「プログラミング言語における最適化について」(a21_opt)では、(3-1)として、
- コンパイル時に答えが確定しているものは、定数に置き換えてしまう。
- という最適化を紹介しました。これの話の続きです。
- この最適化を実現するアルゴリズムは簡単です。
- プログラムを上から順番に見ていくことにします。
- もし変数に定数が代入されたら、この変数の値は〇〇である、とテーブルに登録しておきます。
- もし定数ではない値が代入されたら、もう変数の値は不定なので、もしテーブルにその変数が登録されていればそれを消しますし、登録されていなければ何もしません。
- テーブルに登録された変数を参照された場合は、それを全部定数に置換してしまいます。
- ラベル定義文やforやwhileの先頭は繰り返しやcontiuneで合流が発生する可能性があるところです。そうなると合流の際に変数の値がどうなっているかわかったものではないので、テーブルはクリアしてしまいます。forやwhileの直後の文もbreakなどで飛んでくるので、テーブルのクリアが必要です。そんな感じで、合流の可能性があるところでは全部テーブルクリアです。
- 置換の結果(もしくは置換する前から)式の一部または全部が定数だけで構成されていたら、そこは計算してしまって計算値と置換します。
- こうして最後までプログラムをチェックし終わったら、それでおしまいです。
- ちなみにプログラム内で一度でもポインタを取得した変数(p = &i; としたときのiのこと)は、そのポインタを使って中身を書き換えたり読んだりする可能性があります。それはいつ起こるか簡単にはわかりません。だからそういう変数に対しては、たとえ定数の代入があってもその後も定数のままでいると仮定することなく、変数扱いにします。
- ここも頑張ればもっと最適化がうまくなるのですが、それをやると大変なので、面倒なら無理せずに変数扱いにしてしまいましょう。それでも多くのケースで十分に最適化はできます。
- しかしこのアルゴリズムでは、たとえば関数の冒頭で一度だけ定数で初期化されて、それ以降一度も上書きされない変数があっても、最初の合流ポイントでテーブルクリアされてしまい、せっかくの定数が生かされません。これをどうにかしてやりたいと思いました。・・・もちろんできるだけ難しくないアルゴリズムで。
(1-2)
(2-1)
- 「プログラミング言語における最適化について」(a21_opt)では、(3-2)として、
- という最適化を紹介しました。これの話の続きです。
- この最適化を実現するアルゴリズムは簡単です。
- プログラムを上から順番に見ていくことにします(下から順番に見ていってもいい)。
- 何か変数に「代入する命令」があったとき、その直後からその結果を使う命令がどこにあるかを探します(これは上から順番に見る)。つまり二重ループです。
- もし誰からも参照されないまま、新しい別の値を代入する命令にぶつかったら、それは「結果は使われていない」と判断できます。また値を利用する命令にぶつかったときも、「結果は使われている」と判断できます。・・・判断できたら命令を順番に調べていく内側のループからは抜けられます。
- 悩ましいのは分岐命令や条件分岐命令にぶつかったときです。こうなると分岐先でどうなるのかを解析しないと判断できません。でもそれはちょっとめんどくさそうです(たとえ分かれ道がなくて単純そうな無条件分岐であっても、ただそれをたどっていくとかだと、無限ループとかの場合に出られなくなる恐れがある)。・・・ここを頑張れば最適化性能は間違いなく向上しますが、やっぱり面倒なので、分岐命令にぶつかったら、「もうよくわからん、わからんから結果はたぶん使うだろうということにしておこう」って私はやりました。それでも最適化は結構効きます。
- それで、上記の判定で「結果は使われていない」と判断できた場合に限り、その「代入する命令」は消してしまいます。
(2-2)
- (今考えているアルゴリズム)
- 基本的な考え方は、上記に似ています。違うのは、分岐命令に当たった時、解析をあきらめずに継続するところです。
- 解析したことのある部分は覚えておいて、重複がないようにします。
- 必要か不必要化を判定している命令の直後からトレースして、それで重複がないように検査して、可能性のあるどの経路を通ってもその結果を利用されないのであれば、それは捨ててもいい演算だと判断します。
こめんと欄
|