2005年06月16日

MinCaml読解ノート: 定数畳み込み

定数畳み込みは次のような結果がわかっている式をコンパイル時に計算した値に置き換えてしまう処理である。

let x = 1 in
let y = 2 in
x + y

MinCamlでは、演算のオペランドの両方の値が定数である場合にその計算結果で置き換えることだけを実装している。だから

let x = 3 in
let y = 7 in
let x + a + y

のような場合を10+aにはできない。

まず、小さな関数から見ていく。

memi, memf, memtは変数xと環境envを受け取り、xが登録されていて値が即値のInt/Float/タプルであれば真、それ以外の場合は偽を返す。

findi, findf, findtxの値が即値のInt/Float/タプルであれば値を返す。xが見付からないか型が合わない場合はエラーとする。

次に定数畳み込みの本体ConstFold.gである。

ソースコードと順番が前後するが、letではまず代入する式を定数畳み込みし、変数とその式を環境に追加する。

変数の評価はそのまま即値に置き換える。ただしIntの場合のみで、FloatTupleの場合はコメントアウトされている。これらは整数と異なり最終的にメモリ上に置かれるデータとなるため重複を嫌ったものであろうか。代償として畳み込みの効率は少し落ち、(let x=1.0 in x) +. (let y=2.0 in y)のような式を一回では3.0と計算できず、最適化フェーズを2回通る必要がある。重複した浮動小数点数は後の仮想マシンコード生成にて省かれるので、ここでFloatの処理を避ける必要はないように思えるのだが。

整数の演算、浮動小数の演算は、全ての項が定数なら計算した即値で置換。

比較による条件分岐では、比較が即値同士なら真偽が確定するので生きる方の式だけを残す。

LetTupleではタプルの中身がわかっている場合はタプルを分解し、要素の数だけLetを並べた形に変換する。同時にletの場合と同様変数と式を環境に追加する。

例えば、t=(a,b,c)とわかっているとき let (x,y,z)=t in elet x=a in let y=b in let z=c in e となる。

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/4390731
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。