最適化コンパイラへのいざない (3) 定数に関する最適化

記事一覧

1. はじめに
2. マルチパスコンパイラ
3. 定数に関する最適化 (この記事)
4. プログラムの構造

TL;DR

定数畳み込み，定数伝播のお話．

対象読者

• コンパイラの内部構造について興味がある方
• コンパイラに関して精通している方（批評お待ちしております）

手軽な最適化

突然ですが，次のようなプログラムを見たら何を想像するでしょうか．

seconds_in_day = 1 * 60 * 60 * 24

どうやら，1日が何秒なのかを表しているようです．人間にとってはわかりやすいですね．

ですがコンパイラからするとどうでしょうか．仮に上のプログラムを愚直に目的コードへ翻訳すると，実行時に整数に対する掛け算を3回行うことになります．

定数畳み込み

上のプログラムは，下のように書き直すと，計算機にとっては嬉しいものとなります．

seconds_in_day = 86400

このように，定数式（あらかじめ計算しておくことのできる式）を単純化することを 定数畳み込み と言います．
実装するのが比較的簡単な最適化手法ですが，次に紹介する定数伝播と組み合わせると，生成される目的コードがグッと短くなるでしょう．

具体例

プログラムが木で表されているなら，深さ優先で計算していくことで簡単に定数畳み込みを実現することが出来ます．

3番地コードのような形式の場合，次に説明する定数伝播の考え方を知っていないと，欲しい動作が得られません．

t1 = 1 * 60　
t2 = t1 * 60
t3 = t2 * 24

# 定数畳み込み後
t1 = 60
t2 = t1 * 60 # t1 が定数かわからないと t1 * 60 の結果もわからない
t3 = t2 * 24 # t2 が定数かわからないと t2 * 24 の結果もわからない

定数伝播

先ほどの具体例で，t1やt2が定数かわからないと，定数畳み込みできるのかすらわからない場合がありました．

これは，プログラム内で定数（定数畳み込みの結果も含みます）が代入されている変数（その変数への代入は1回のみ行われるとします）を，その定数で置き換えていくことで解決できます．この操作は，どの変数も定数へ置換できなくなるまで，複数回繰り返す必要があります．この一連の操作が 定数伝播 です．

具体例

先ほどの具体例に定数伝播を適用して，どうなるか見てみましょう．

# 最適化前
t1 = 1 * 60　
t2 = t1 * 60
t3 = t2 * 24

# 定数畳み込み
t1 = 60
t2 = t1 * 60
t3 = t2 * 24

# 定数伝搬(t1消去)
t2 = 60 * 60
t3 = t2 * 24

# 定数畳み込み
t2 = 3600
t3 = t2 * 24

# 定数伝搬(t2消去)
t3 = 3600 * 24

# 定数畳み込み
t3 = 86400

いい感じですね．

(迷ったのですが, 疑似コードによる解説は省きました. 疑似コードなどでわかりやすくアルゴリズムを記述してほしいという要望があればお答えします)