
用いる方法を採用した [中谷ほか2001]。
SSA変換の2種類の方法の変換時間の比較の一例を図8.1-2に示す。この図から、通常のプログラムでは、
支配辺境を用いる方法(Cytronらによる方法)による変換時間がDJグラフを用いる方法による変換時間
(Sreedharらによる方法)よりもやや少なく良好であることが見てとれる。ちなみに、2つの方法の変換結果に差はない。
この評価結果に基づき、支配辺境を用いる方法を採用した。具体的には、LIR上の制御フローグラフの上で変換を行う。
なお、SSA変換の際に同時にコピー畳み込みを行うこともできる。
SSA形式には、最小 (minimal) SSA、半ば刈り込んだ (semi-pruned) SSA 、刈り込んだ (pruned) SSA の3つの形式
がヴァリエーションとして提案されている。アルゴリズムの比較評価ができるようにこれらのヴァリエーションをすべて実装し、
オプションで指定できるようにした。


for (i=0; i<M; i=i+1) {
for (j=1; j<N; j=j+1) {
a[j+1]=a[j-1]+b[i];
}
c[i]=a[N];
}
の内側のループでは、
a[2]=a[0]+b[i]; a[3]=a[1]+b[i]; a[4]=a[2]+b[i]; a[5]=a[3]+b[i]; a[6]=a[4]+b[i]; ....のように実行が進む。もしレジスタに余裕があって、r0, r1, r2, r3 が使えるとすると、上記のループを
r0=b[i]; r1=a[0]+r0; a[2]=r1; r2=a[1]+r0; a[3]=r2; r3=r1+r0; a[4]=r3; r1=r2+r0; a[5]=r1; r2=r3+r0; a[6]=r2; ....のように実行されるようにすれば、右辺の配列aと配列bの参照を レジスタ参照に置き換えることができる。
for(i=0; i<M;i=i+1) {
j=0; v1=1; v3=2;
for(; j<N-v1; j=j+v3) {
a[j+1]=a[j-1]+b[i]
a[j+2]=a[j]+b[i];
}
for(; j<N; j=j+1) {
a[j+1]=a[j-1]+b[i];
}
c[i]=a[N];
}
のように展開され、これに対してループの繰り返しをまたいだスカラ置換
が行われる。そのときのオプション指定は、例えば
-coins:ssa-opt=<SSA形式最適化列>/<通常形式最適化列>/<SSA形式最適化列>
(また、-coins:ssa-opt=... の代わりに、-coins:lir-opt=... を使用することも可能である。 ただし、lir-opt と ssa-opt の両方が記述されている場合、lir-opt で指定したもののみが有効である。)
ここで、<SSA形式最適化列>は,xxx/yyy/.../zzzのようなオプション名列であり, 最初の"xxx"はSSA形式への変換の仕方を指定するものであり、次のいずれかである。
-coins:ssa-opt=divex2/esplt/pdeqp/prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/dce/srd3どのような最適化を、どのような順番で行うのが良いかは、簡単には決められない。 あるソースプログラムには効果のある順番が、他のプログラムに対して同じような効果が あるとは限らないからである。
-coins:ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3それで、次節の評価では、このオプション指定を使っている。その後、
-coins:ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/dce/srd3はわずかではあるがさらに良い効果を示した。coins.driver.Driverでは、以前は "-O2"オプションを指定すると、ssa-optとしては前者の指定をしたことにしてい たが、最新のバージョンでは後者を指定したことにしている。
最適化オプション ddpde と glia を指定する場合の一例を次に示す。
-coins:ssa-opt=divex2/esplt/pdeqp/ddpde/expde/prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/glia/dce/srd3
x3 = φ(x1, x2)のようなφ関数が作られる。SSAからLIRに逆変換する時は、単純に考えれば、先行ブロックに
x3 = x1 や x3 = x2というコピー文を置いて、φ関数を消去すればよい。しかし、 それでは無駄なコピー文になったり、SSA最適化の変換をした後では正しいプログラムが 得られないことがあるので、逆変換の方法がいろいろ提案されている。
-coins:ssa-with-chaitin-coalescingはそれを行うことを指定するオプションである。これは、どの逆変換の方法を選んだときにも使うことが出来る。
-coins:ssa-no-sreedhar-coalescingもある。
その他に、SSA最適化の際にデフォールトで行っているいくつかの処理について、それをしないように指定する以下のようなオプションがある。
-coins:ssa-no-change-loopSSA最適化に先立って、同じヘッダをもったループを合併(merge)したり、whileループを if-do-whileの形に変換しているのを止めるオプションである。
-coins:ssa-no-copy-foldingSSA形式への変換の際に、コピー伝播を行っているのを止めるオプションである。
-coins:ssa-no-redundant-phi-eliminationSSA形式への変換後に、冗長なφ関数削除を行っているのを止めるオプションである。
-coins:ssa-no-memory-analysisSSA最適化のcseやpreqpを行う際は、簡単なalias解析をしている。それは、メモリ全体を 一つの変数のように扱うものである。その解析を止めるオプションである。
-coins:ssa-no-aggregate-exp逆変換の直前には、ある基本ブロックの中で1回使われるだけの変数をその変数の値を定義する式で置き換える処理を行っているが、 それを止めるオプションである。
coins-1.5 以降の版では「大域値番号付けに基づく要求駆動型部分冗長除去による
スカラ置換」が指定できる。そのためのオプション指定の例としては、次のものをあげる。
hirOpt=presrhir,
ssa-opt=prun/divex3/esplt/cstp/presr/cse/cstp/hli/osr/hli/cstp/eqp/dce/srd3
ここで、要求駆動型部分冗長除去によるスカラ置換のために設けられたSSAオプションは、先に述べたように、次のとおりである。
divex3 式の3アドレス形式変換(スカラ置換むけ)
eqp コピー伝播を伴わない要求駆動型部分冗長除去(レジスタ要求低減型)
presr 要求駆動型部分冗長除去によるスカラ置換
以上はあらましであり、詳しくは、英語のドキュメントの
8. SSA Optimization for LIR、
および
SSA最適化外部仕様書(pdf)を見られたい。
表8.1-1 SPECベンチマークによるSSA最適化器の評価 (目的コードの実行時間)
SUN Fire V440 (UltraSPARC III, 1GHz*4, メモリ8 GB)での結果.入力はtest
-------------------------------------------------------------------------------
CINT (excluding C++ source code)
-------------------------------------------------------------------------------
coins-noopt coins-ssa gcc-O2
(sec) (sec) (sec)
-------------------------------------------------------------------------------
164.gzip 4.32 3.97 2.74
175.vpr 8.12 5.88 3.57
181.mcf 0.743 0.736 0.741
197.parser 6.73 6.72 5.12
254.gap 2.63 2.45 2.07
255.vortex 13.9 12.8 9.84
256.bzip2 28.2 26.3 9.99
300.twolf 0.671 0.623 0.489
-------------------------------------------------------------------------------
CFP (excluding F90 source code)
-------------------------------------------------------------------------------
coins-noopt coins-ssa gcc-O2
(sec) (sec) (sec)
-------------------------------------------------------------------------------
171.swim 9.11 2.50 2.67
172.mgrid 851 107 78.2
173.applu 10.1 1.21 0.687
177.mesa 5.30 5.46 4.83
179.art 18.2 16.2 12.4
183.equake 4.17 3.34 3.00
188.ammp 29.6 23.4 18.5
-------------------------------------------------------------------------------
coins-noopt:
coins基盤部最適化なし
coins-ssa:
-coins:ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3で指定されるSSA最適化を行ったもの
gcc-O2:
gcc -O2 または g77 -O2

SSA最適化部に関連するユーティリティとして、LIR実行命令カウント機能、LIRへの文番号付加機能があり、 これらの機能は、ssa-opt(lir-opt でも同様)で指定できる。 ただし、ここで述べる機能が使えるのは、coins-1.4.4.4 より後のバージョンである。 (詳細に関しては、 SSA最適化の外部仕様書の9章,11章を参照のこと。)
本機能は、COINS コンパイル時の SSA オプション内に cntbb が記述されている場合に、 その cntbb の処理の直前に作成された LIR コードの各基本ブロックの LIR 命令数をあらかじめ COINS コンパイル時に数え(計数)ておき、 その基本ブロックが実行されたときにその計数を加算してファイル(計数結果ファイルという)に実行したLIR命令数を加えこむことにより、 各基本ブロックの LIR 実行命令数の総数を測定するものである。
ただし、LIR 実行命令カウントのために、同じソースファイルにたいし2回のコンパイルをおこない、その結果作成された実行ファイルを実行することによって、情報を収集する。 すなわち、1回目の COINS コンパイルで関数名等を収集し、作業用ファイル file_list.dat に書き込み、2回目の COINS コンパイルで LIR 実行命令の計数命令とプリント関数の呼び出しを埋め込む。 実行によって得られたカウント結果は、ソースファイルの関数ごとに、''<ファイル名>.<関数名>.cnt''というファイルを作成し、 ''<基本ブロック番号>:<LIR実行命令数><改行>''の形式で書き出される。 ここで、作業用ファイルとカウント結果のファイルは、作業用ディレクトリ(デフォールトでは /tmp だが、COINS オプション tmpdir を用いて設定することもできる)に書き出される。
また、カウント数の表示、作業用ファイル等の削除をおこなうクラス(ProApp)も用意した。
本機能は、つぎのオプションを指定することにより、有効となる。
-coins:lir-opt=.../cntbb/...
コンパイル時に、cntbb の直前に生成されている LIR 命令がカウントの対象となる。 したがって、
-coins:lir-opt=prun/divex/cse/cntbb/srd3
であれば、共通部分式除去を終了したあとの LIR 実行命令数がカウントされる。
また、つぎのように、tmpdir をもちいて、作業用ディレクトリを指定することもできる。
-coins:tmpdir='d:\cygwin\tmp',lir-opt=.../cntbb/...
tmpdir が指定されていなければ、デフォールトとして '/tmp' が使用される。
この指定は、Windows 環境において有効に用いられることと思う。
ProApp を用いて、つぎのコマンドを実行することにより、カウント結果が表示される。
java -cp ./classes coins.ssa.ProApp -t xxxx
ここで、-t オプションにより、xxxx を作業用ディレクトリを指定しているが、-t オプションがなければ、/tmp を作業用ディレクトリとして処理する。
同じ ProApp を用いて、つぎのコマンドにより、作業用ディレクトリ内の file_lis.dat、カウント結果を削除できる。
java -cp ./classes coins.ssa.ProApp -t xxxx -n
ここで、-t オプションについては、表示の場合と同様である。
LIR文に文番号を付加する。 COINS には、もともとソースプログラムでの行番号(ソース行番号)を取り込む仕組みが存在し、coins オプション debuginfo が設定されていれば、HIR から LIR への変換の際に、行番号が (LINE <行番号>)という LIR 式(LINE 文ともいう)として、各基本ブロックの先頭に挿入される。 しかしこの行番号は、 HIR を通って LIR になるまでに、行の改変、挿入がおこなわれ、すべての LIR 式に行番号が 対応しているわけではないので、COINS の SSA 最適化をデバッグするとき、かならずしも適切な指標ではない。 本機能で扱う文番号は、いま述べた行番号とは異なり、SSA最適化において各関数毎に1から始まる番号を LIR 文に ふった番号である。 (もともとあった行番号と区別するために文番号とし負の整数で表示している。) また、ソース行番号を表す LINE 文にも文番号がふられるので、ソース行番号と LIR 文番号を対として情報を利用することも 可能である。 本機能は、lir-opt もしくは ssa-opt につぎのオプションを設定することにより、使用することができる。