技術

4.2. ちょっとした定数の畳み込み

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第4章 万華鏡: JITの追加と最適化のサポート
第2節 ちょっとした定数の畳み込み

第3章における実装はエレガントであり、拡張するのが簡単であった。
しかしそれは不幸にも、素晴らしいコードを生成するものではなかった。
しかしそれでも、IRBuilderで簡単なコードをコンパイルした場合において、明らかに最適化出来る部分は最適化されていた。

ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        ret double %addtmp
}

これは、入力を構文解析した結果構築したASTをそっくりそのままLLVM IRに変換したものとは異なる。
そっくりそのまま変換したら以下のようになるはずである。

ready> def test(x) 1+2+x;
Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 2.000000e+00, 1.000000e+00
        %addtmp1 = fadd double %addtmp, %x
        ret double %addtmp1
}

とりわけ、上記のような定数の畳み込み(Constant folding)は、とても平凡ではあるがとても重要な最適化である。
なので、多くの言語開発者は、ASTの段階において定数畳み込みをサポートしている。

LLVMでは、これをASTで行う必要はない。
LLVM IR生成のための関数呼び出しは、全てLLVM IR Builderに送られるので、それを呼び出したときに定数畳み込みのチャンスがあるかどうかをBuilder自信が確認する。
その場合、Builderは冗長な命令を生成することなく、定数畳み込みを行いその結果を返す。

まぁ、楽勝だね。
実際にこのようなコードを生成する場合は、常にIRBuilderを使うことをおすすめする。
IRBuilderが持つ定数畳み込みの機能を使うのに追加のプログラミングは必要ないし(色んな箇所で定数をチェックしてコンパイラを醜くするべきではない)、いくつかの場合(特に、定数を大量に使用するコードを処理する場合や、プリプロセッサマクロを使用する言語の場合)に、生成されるLLVM IRのコードの量を劇的に削減する。

その一方、そのような定数畳み込みの解析を、構築しようとしているコードと共にインラインで行うという事実によって、IRBuilderは制限される。
以下は、少し複雑な例である。

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double 3.000000e+00, %x
        %addtmp1 = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp1
        ret double %multmp
}

この場合では、掛け算の右側と左側は同じ値である。
本当は、”x+3″を2回計算してから乗算するんじゃなくて、”temp = x+3; result = temp * temp;”のような感じのコードを生成して欲しい。

残念ながら、これはどんなローカル解析(local analysis)をもってしても検出し最適化することはできない。
これを行うには、2つの変革が必要である。
それは、式の再連結(reassociation of expressions)(2つの加算を字句的に同一にし)、そして共通部分式除去(Common Subexpression Elimination, CSE)を用いて冗長な加算命令を削除することである。
幸いにもLLVMは、様々な最適化をパス(passes)の形で提供している。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください