8.1 SSA最適化
静的単一代入形式(以下、SSA形式と略す)は、変数の定義が字面上唯一になるように添字をつけた新しい中間表現形式であり、
コンパイラにおけるデータフロー解析や最適化を見通しよく行うのに適している。
COINSには以下のSSA最適化モジュールが組み込まれている。
- SSA形式への変換
SSA形式への効率良い変換を行う。
- SSA形式からの逆変換
SSA形式から実行効率の良い通常形式への変換を行う。
- SSA形式上のデータフロー解析と基本的最適化および高度最適化
SSA形式上でデータフロー解析を行い、機能・性能に優れた最適化を行う。基本的な最適化をほぼ網羅しており、
いくつかの高度な最適化も実現している。
- SSA形式上の最適化のために有用な変換
SSA形式上の最適化のために有用な様々の変換を行う。
以下、SSA最適化部について、設計思想や採用の経緯を示しつつやや詳しく述べる。また、SSA最適化部の評価、
教育・研究への適用、共通インフラストラクチャとしての統合などについて述べる。
8.1.1 SSA形式最適化部
8.1.1.1 SSA最適化部の流れ
SSA最適化部の全体構成を図8.1-1に示す。
SSA最適化部は、COINS基盤部から低水準中間表現(LIR)を受け取り、それをまずSSA形式に変換する。
ついで、SSA形式上で種々の変換やデータフロー解析および最適化を行う。
最後にSSA形式をふたたび通常形式に戻し(SSA逆変換)、基盤部へ渡す。基盤部は、そこから目的コードを生成する。

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

図8.1-2 SSA変換の変換時間の比較
8.1.1.3 SSA形式からの逆変換
SSA形式から通常形式への逆変換についての主なアルゴリズムにはBriggsらの方法とSreedharらの方法がある。
それらを詳細に比較検討したところ、SSA逆変換の際に挿入されるコピー文の数などからSreedharらの方法に
優位性があると認められた [小濱ほか2002]。
そこで、既存のコンパイラでは採用が稀であったが、Sreedharらの方法を採用した。
その後、東京工業大学の研究室で別途Briggsらの方法を実装し、さらにBriggsらの方法の改善案も提案し、
Sreedharらの方法との比較を実測評価した [伊藤ほか2005]。
その結果、当初の選択が正しいことが実証された。
それぞれの方法を用いて逆変換した後の目的コードの実行時間の比較の一部を図8.1-3に示す。
Sreedharらの逆変換法を用いた目的コードの実行時間が少ないことが見てとれる。ちなみにその後、
大学院生が実装したBriggsらの方法によるSSA逆変換もCOINSに組み込んだ。
Sreedharらの逆変換法には、3つのヴァリエーション Method 1、 2、 3がある。
アルゴリズムの比較評価のためにこれらのヴァリエーションをすべて実装し、オプションで指定できるようにした。
また、SSA逆変換後のコピー文を減らす目的で、2種類の合併 (coalescing) を実装し、これらもオプションで指定できるようにした。

図8.1-3 SSA逆変換におけるBriggs法、その改善案、Sreedhar法による目的コードの実行時間の比較
8.1.1.4 SSA形式上のデータフロー解析と最適化
8.1.1.4.1 SSA形式上の基本最適化
SSA形式上の最適化としては、まず共通インフラストラクチャとして基本的な最適化を含めることとした。
(最適化のためにはまずデータフロー解析を行うのが普通なので、以後はデータフロー解析については逐一言及しない。)
SSA形式による基本的な最適化としては、コピー伝播、条件分岐を考慮した定数伝播、支配関係に基づく共通部分式除去、
無用命令除去、無用φ命令除去、空ブロック除去、ループ不変計算のループ外移動、
ループの帰納変数に関わる演算の強さの軽減と判定の置き換え、を実現した。この他に、前処理として、
ループ構造の変換(while型ループをif-do-while型ループへ変換)も行える。
これらの詳細については、参考ドキュメントを見て欲しい。
8.1.1.4.2 SSA形式上の高度最適化
一方、SSA形式上の高度な最適化もいくつか実装した。また、このSSA最適化部が研究基盤として利用できることの例として、
新たに考案したアルゴリズムによる最適化も含めた。
これらの最適化としては、「大域的再結合(global reassociation)」、「メモリ全体を一つの塊とみなす素朴な別名解析」、
「効率的な質問伝播を用いた大域値番号付けによる部分冗長性除去」を実現した。後者2つは本研究で新たに考案したアルゴリズムである。
メモリ全体を一つの塊とみなす素朴な別名解析とは、COINSでは別名が生じる可能性のある変数については
安全のためメモリに置いたままにしているが、このような変数についても、メモリへの書き込みがない間はこの変数に別名はない、
とみなす解析である。これにより、共通部分式の対象が広がるなどの効果がある。
効率的な質問伝播を用いた大域値番号付けによる部分冗長性除去とは、質問伝播という方法によりSSA形式のφ関数が間に挟まれて
いるような共通部分式も効率よく発見することができ、部分冗長性除去を含む統一的な冗長性除去を行うアルゴリズムである。
詳しくは参考ドキュメント
SSA最適化外部仕様書(pdf)の6.3節 「質問伝播に基づく大域値番号付けと部分冗長除去」
を参照されたい。
さらに、「大域値番号付けに基づく要求駆動型部分冗長除去によるスカラ置換」も実現した。これは、
メモリの参照・設定をレジスタの参照・設定に置き換えるものであり、
ループ内で適用できると、高速実行に大きく貢献することがある(Coins-1.5以降で利用可能)。
例えば、
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の参照を
レジスタ参照に置き換えることができる。
上記の変形が通常の共通式削除や部分冗長性除去と異なる点は、
ループの繰り返しをまたいで値の同じ式を認識することである。
(上記のループでは、j番目の繰り返しにおいて、2回前の繰り返しで
算出したa[j-1]をa[j+1]の計算に使っている。)
「大域値番号付けに基づく要求駆動型部分冗長除去によるスカラ置換」は
上記のような形でメモリアクセスのレジスタ化を行う最適化処理である。
これを効率よく行うため、ループの繰り返しをまたいだ同値配列要素を
認識し、それを含む内側ループを展開するオプション
hirOpt=presrhir
も合わせて指定する。すると上記のループは
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];
}
のように展開され、これに対してループの繰り返しをまたいだスカラ置換
が行われる。そのときのオプション指定は、例えば
hirOpt=presrhir,
ssa-opt=prun/divex3/esplt/cstp/presr/cse/cstp/hli/osr/hli/cstp/eqp/dce/srd3
のようにすればよい。
ここで、要求駆動型部分冗長除去によるスカラ置換のために設けられたSSAオプションは、次のとおりである。
divex3 式の3アドレス形式変換(スカラ置換むけ)
eqp コピー伝播を伴わない要求駆動型部分冗長除去(レジスタ要求低減型)
presr 要求駆動型部分冗長除去によるスカラ置換
8.1.1.4.3 SSA形式最適化のインフラとして有用な様々な変換
制御フローグラフ上の危険辺の除去、などが指定にしたがって行えるよう、インフラを整えた。
これらの詳細については、参考ドキュメントを見て欲しい。
8.1.2 SSA最適化部の評価
8.1.2.1 SSA最適化部の使い方
SSA最適化部を使うには、次のようなオプション指定をすれば良い。
ただし,<通常形式最適化列>が使えるのはcoins-1.4.4.2より後のバージョンである.
-coins:ssa-opt=<SSA形式最適化列>/<通常形式最適化列>/<SSA形式最適化列>
(また、-coins:ssa-opt=... の代わりに、-coins:lir-opt=... を使用することも可能である。
ただし、lir-opt と ssa-opt の両方が記述されている場合、lir-opt で指定したもののみが有効である。)
ここで、<SSA形式最適化列>は,xxx/yyy/.../zzzのようなオプション名列であり,
最初の"xxx"はSSA形式への変換の仕方を指定するものであり、次のいずれかである。
- mini Minimal SSA 形式への変換
- semi Semi-Pruned SSA 形式への変換
- prun Pruned SSA 形式への変換
また、 最後の"zzz"はSSA形式からの逆変換の仕方を指定するものであり、次のいずれかである。
- brig Briggsの方法による逆変換
- srd1 Sreedharの方法Iによる逆変換
- srd2 Sreedharの方法IIによる逆変換
- srd3 Sreedharの方法IIIによる逆変換
中間の"yyy"はSSA形式での最適化の仕方を指定するものであり、次のいずれかである。
それらは、いくつか並べることが出来る。同じものが何回かあっても良い。
それらが並んでいる順番に、順次適用されていく。
- cbb 基本ブロックの連結
- cpyp コピー伝播
- cse 共通部分式削除
- cstp 条件分岐を考慮した定数畳み込みと定数伝播
- dce 無用命令削除
- divex 式を3アドレス方式に変換(代入の右辺の演算子はたかだか1つ)
- ebe 空ブロック削除
- esplt 危険辺の分割
- gra 大域的再結合(Global Reassociation)
- hli ループ不変コードの巻き上げ
- lcm Lazy Code Motion(coins-1.4.4.2より後のバージョンで使える)
- lir2c LIRからCプログラムを生成する
- osr ループの帰納変数に関わる演算の強さの軽減と判定の置き換え
- preqp 質問伝播の方法による大域的番号付けと部分冗長性除去
- rpe 冗長なPhi関数の除去
- ssag SSAグラフの作成
- glia 大域ロード命令集約
(gliaは,同じ配列への参照を,コード移動手法で近づけ合うこと
によって,キャッシュのヒット率を向上させる. これでは
効果を生じないコード移動は避けるので、新たに導入した
一時変数がレジスタに割り付けられやすくする効果ももつ.
ただし,キャッシュやプログラムの特性により,逆効果となる
場合もありえる.)
このうち lcm は、対象プログラムのコンパイルに膨大な時間がかかるので、使用時には注意が必要である。
<通常形式最適化列>は、www/... のような通常形式の最適化オプション名の列である。
ここで、"www" は、通常形式上の最適化オプション名であり、次のいずれかであるが、
pdeqp を使用する場合には前処理として divex2 と esplt とを指定する必要がある。
- pdeqp 要求駆動型無用コード除去
- divex2 式を3アドレス方式に変換(divex と同様だが通常形式プログラムにたいし適用される)
- esplt 危険辺の分割(SSA形式最適化と同じものだが、通常形式プログラムにたいしても適用可能である)
- expde 部分無用コード除去の反復適用
(部分無用コード除去によって新たな無用コードが明らかになる副次的効果
が生ずる可能性があるが,expdeはその処理を反復適用することによって,
部分無用コードを完全に除去する.本オプション を適用するとコンパイル
時間がやや長くなる.)
- ddpde 要求駆動型部分無用コード除去
(ddpdeは部分無用コード除去法を終了点に近い代入文から適用していく
ことによって,従来の部分無用コード除去1回のコストで,ほとんどの
副次的効果を反映させ,多くの部分無用代入を除去できる.)
<SSA形式最適化列>と<通常形式最適化列>は、空列でもよいが、その場合、区切りの'/'は不要である。
とくに<SSA形式最適化列>だけであれば、従来の記述と同じである。
つぎのものは、要求駆動型無用コード除去を行なった後にSSA最適化を行なう記述例である。
ここで、'divex2/esplt/pdeqp'が<通常形式最適化列>であり、'prun' から 'srd3' までが<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
SSA最適化に関係するcoinsオプション
SSA最適化に関係するcoinsオプションがいくつかある。
その一つは合併(coalescing)に関するものである。SSA形式では、制御フローグラフの合流点に
x3 = φ(x1, x2)
のようなφ関数が作られる。SSAからLIRに逆変換する時は、単純に考えれば、先行ブロックに
x3 = x1 や x3 = x2
というコピー文を置いて、φ関数を消去すればよい。しかし、
それでは無駄なコピー文になったり、SSA最適化の変換をした後では正しいプログラムが
得られないことがあるので、逆変換の方法がいろいろ提案されている。
単純なアルゴリズムで上記のようなコピー文が置かれたときは、
たとえばx3とx1を同じ変数として合併すれば、コピー文を減らすことが出来る。
この合併の方法としてはChaitinの提案している方法がある。
これは、逆変換後のLIRに対して行われる。
-coins:ssa-with-chaitin-coalescing
はそれを行うことを指定するオプションである。これは、どの逆変換の方法を選んだときにも使うことが出来る。
ただし、Sreedharの方法IIIはChaitinの提案した合併を包含しているので、
Sreedharの方法IIIで逆変換をしたあとに上記を行っても効果がないと思われる。
逆変換の方法としてSreedharの方法のどれかを選んだ場合は、
逆変換の際にSreedharの提案している別の種類の合併をデフォールトで行っているが、
それをしないように指定するオプション
-coins:ssa-no-sreedhar-coalescing
もある。
その他に、SSA最適化の際にデフォールトで行っているいくつかの処理について、それをしないように指定する以下のようなオプションがある。
-coins:ssa-no-change-loop
SSA最適化に先立って、同じヘッダをもったループを合併(merge)したり、whileループを
if-do-whileの形に変換しているのを止めるオプションである。
-coins:ssa-no-copy-folding
SSA形式への変換の際に、コピー伝播を行っているのを止めるオプションである。
-coins:ssa-no-redundant-phi-elimination
SSA形式への変換後に、冗長なφ関数削除を行っているのを止めるオプションである。
-coins:ssa-no-memory-analysis
SSA最適化の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.2.2 SSA最適化部の評価
SPECベンチマークおよび小規模テストプログラムについて、SSA形式最適化を行った結果の目的コードの性能を実測した。
さまざまなコンパイル時オプションフラグを設けてあるので、その指定を様々に変えて、最適化の評価を行った。この結果、
種々のSSA最適化を適用すればするほど目的コードの性能が上がるという訳ではないこと、スーパースカラーマシンでは
命令キャッシュやパイプライン処理などの計算機アーキテクチャの影響が大きいこと、などが判明した。
SPECベンチマークについての目的コードの実行時間の一部を表8.1-1に示す。これはCOINSの基盤部に対して
他の最適化を適用せずにSSA最適化のみを適用した結果である。
また、COINS基盤部最適化なしを1としたときの目的コードの実行時間の相対比を図8.1-4に示す.
表8.1-1や図8.1-4からわかるように、現時点では、SSA最適化の結果はgccの-O2オプションの結果に一部は優っている
ものの全体としてはまだ及ばない。その原因として、gccの目的コードではレジスタプロモーションや命令スケジューリングが
なされているが、これはSSA最適化だけでは処理できないこと、またSSA形式では配列などスカラーでない変数の扱いが
確立されていないこと、現状のSSA最適化にまだ改良の余地があること、が挙げられる。
そこで、別途レジスタプロモーションや命令スケジューリングを行うモジュールが開発されている。
その結果、1. 概要
の中の「1.6 オブジェクト性能」
に見られるように、いくつかの小さなプログラムではgccの-O2オプションより優れた性能を示している。
表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

図8.1-4 SPECベンチマークによるSSA最適化器の評価
(COINS基盤部最適化なしに対する目的コードの実行時間の相対比)
8.1.3 SSA最適化部関連ユーティリティ
SSA最適化部に関連するユーティリティとして、LIR実行命令カウント機能、LIRへの文番号付加機能があり、 これらの機能は、ssa-opt(lir-opt でも同様)で指定できる。
ただし、ここで述べる機能が使えるのは、coins-1.4.4.4 より後のバージョンである。
(詳細に関しては、
SSA最適化の外部仕様書の9章,11章を参照のこと。)
8.1.3.1 LIR 実行命令カウント機能
8.1.3.1.1 LIR 実行命令カウント機能の概要
本機能は、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)も用意した。
8.1.3.1.2 LIR 実行命令カウント機能の使い方
本機能は、つぎのオプションを指定することにより、有効となる。
-coins:lir-opt=.../cntbb/...
コンパイル時に、cntbb の直前に生成されている LIR 命令がカウントの対象となる。 したがって、
-coins:lir-opt=prun/divex/cse/cntbb/srd3
であれば、共通部分式除去を終了したあとの LIR 実行命令数がカウントされる。
- 注意
-
1回目のコンパイルで、file_list.dat に関数名、基本ブロック数などを書き込み、 2回目のコンパイルでそれらを参照して、各基本ブロックにカウントをおこなう LIR 命令を 埋め込む。 そのため、本機能を使用する場合、コンパイルする前には、file_list.dat という ファイルが存在しないことを仮定する。
また、つぎのように、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 オプションについては、表示の場合と同様である。
8.1.3.1.3 使用上の注意
- lir-opt(もしくは ssa-opt)では、cntbb を複数回指定できない
- LIR実行命令数カウントの結果の出力に、fprintf などの関数を使用しているため、x86_64-mac では、本機能を使用できない
- PHI命令、PROLOGUE命令、EPILOGUE命令、およびLIR実行命令数カウントのために埋め込まれたLIR命令は、LIR実行命令数のカウントから除外する
8.1.3.2 LIR への文番号付加機能
LIR文に文番号を付加する。
COINS には、もともとソースプログラムでの行番号(ソース行番号)を取り込む仕組みが存在し、coins オプション
debuginfo が設定されていれば、HIR から LIR への変換の際に、行番号が (LINE <行番号>)という
LIR 式(LINE 文ともいう)として、各基本ブロックの先頭に挿入される。
しかしこの行番号は、 HIR を通って LIR になるまでに、行の改変、挿入がおこなわれ、すべての LIR 式に行番号が
対応しているわけではないので、COINS の SSA 最適化をデバッグするとき、かならずしも適切な指標ではない。
本機能で扱う文番号は、いま述べた行番号とは異なり、SSA最適化において各関数毎に1から始まる番号を LIR 文に
ふった番号である。
(もともとあった行番号と区別するために文番号とし負の整数で表示している。)
また、ソース行番号を表す LINE 文にも文番号がふられるので、ソース行番号と LIR 文番号を対として情報を利用することも
可能である。
本機能は、lir-opt もしくは ssa-opt につぎのオプションを設定することにより、使用することができる。
- stlin : 番号付けをおこなう(各 LIR 文の opt に新に作成された文番号を書き込む)
- inslin : LINE 文を挿入する(PHI命令を除く、各 LIR 文の直前にその LIR 文の opt にある文番号を表す LINE 文が挿入される)
- rmlin : LINE 文を削除する(LINE 文を表す LIR 文が Function から削除される)
- shlin : LINE 文を表示する("LINE xx:" の形で、各 Function に含まれる LIR 文を標準出力に表示する。ここで xx は、負の整数。)
これらのオプションを使って、たとえば、
ssa-opt=stlin/shlin/prun/shlin/cse/shlin/srd3/shlin
のように指定することにより、各SSA最適化でのLIRの異動をある程度表示することができる。
より詳しい説明は、SSA最適化外部仕様書を参照のこと。
- 注意
- これらのオプション stlin/inslin/rmlin/shlin は、ssa-opt の任意の位置に記述できる。
8.1.4 参考ドキュメント
- 中谷俊晴,加藤吉之介,佐々政孝,脇田建:
「コンパイラ・インフラストラクチャにおけるSSA形式最適化プロトタイプシステムの実装」,
函館,日本ソフトウェア科学会大会論文集,第18回,3D-2 (2001年9月).
- 小濱真樹,中谷俊晴,佐々政孝:「静的単一代入形式における正規化アルゴリズムの比較」,
東京,日本ソフトウェア科学会大会論文集,第19回,1C-1 (2002年9月). http://jssstconference.jstage.jst.go.jp/ja/より
- 伊藤陽,小濱真樹,佐々政孝:「静的単一代入形式からの逆変換アルゴリズムの比較と評価」,
情報処理学会プログラミング研究会発表資料,(2005年3月).
- COINSのソース・アーカイブのdoc-en/README.SSA.en.txt(COINSの使い方)
-
SSA最適化の研究(pdf)
-
SSA形式入門(pdf)
-
SSA最適化外部仕様書(pdf)
-
SSA形式最適化の例 (条件付き定数伝播)(pdf)
-
SSA形式最適化の例 (共通部分式除去)(pdf)