6.1 HIR最適化の概要
HIR最適化には、オブジェクトコードの性能をあげるための通常の意味での
最適化と、最適化という枠にとらわれないもっと広い意味でのプログラム変換を行う
大域的パタン照合による変換がある。
HIR最適化の内容には、SSA最適化で行っていることと重複するものもあるが、
HIRで最適化した結果を可搬性のあるCプログラムとして生成する場合や、
最適化結果に基づいて並列化しOpenMPプログラムとして生成し並列実行させる
ような場合には、SSA最適化は適用されない。配列要素の表すメモリ領域の解析に
基づく最適化・並列化や、インライン展開、ループ展開などの最適化はLIRよりも
HIRで行う方がやりやすい。たとえば
c = aa[i] + aa[j];
func(c, aa[i] + aa[j]);
という文の列があったとすると、HIR最適化では2つの文のaa[i]+aa[j]の全体を
同じ式と認識して前の文で計算した値を後ろの文で再利用する。一方、LIRでは
aa[i]やaa[j]がそのアドレス計算を含むいくつもの命令列に分解されるため、
分解された命令間の再利用はうまくでき、HIRでは対象としていなかった細かい
レベルの再利用もできるが、aa[i]+aa[j]全体の再利用は、処理が分解され
すぎていて少しむずかしくなる。
1つのコンパイラだけを作るときは重複した機能を実装することはあまり
行わないが、COINSはさまざまな使い方のできるコンパイラ・インフラストラクチャ
とするために、HIR段階とLIR段階の両方に、それぞれの特徴を生かした
基本的な最適化機能を備えている。
HIR 最適化は、HIRの部分木として表現されたプログラムを何らかの観点から
効率がよいと見なす部分木に変換する。それは
-coins:hirOpt=hiroptspec
-coins:hirOpt=hiroptspec/hiroptspec/...
というコンパイラ・コマンドで起動される。ここで、
hiroptspec
は、定数畳みこみを表すcfや、定数伝播を表すcpf、局所的共通部分式削除を表す
cseなどの最適化項目の指定である。
複数の最適化項目を指定するときは、次のように斜線 (`/') で区切って指定する。
-coins:hirOpt=hiroptspec/hiroptspec/...
最適化項目の適用順序は、コマンドで指定した順序とほぼ同じであるが、
場合によって、前処理操作としての項目が自動挿入されたり、他の項目でカバー
されるものが削除されたりする。(順序が入れ替わることはない。)たとえば
java coins.Driver -S -coins:hirOpt=cf/cpf
というコマンドでは、定数畳みこみ(cf)のあとに定数伝播(cpf)がなされる。また、
java coins.Driver -S -coins:hirOpt=pre
と指定すると、部分冗長性削除(pre)の前処理として局所的共通部分式削除(cse)が挿入される。
java coins.Driver -S -coins:hirOpt=pre/cse
というコマンドでは、局所的共通部分式削除は pre でカバーされているとして無視される。
最適化項目には xx.yy のような形で、項目 xx に対する付加情報 yy を指定できるものがある。
たとえば loopexp.4 という指定は、後で個別の項で述べるように、ループ展開を4回まで許すということを表す。
HIR最適化は coins.opt.Opt.java というモジュールで制御されている。
新しい最適化項目を追加するにはこれのサブクラスを定義して、その中に doHir() というメソッドを実現すればよい。
現在のドライバ (coins.driver.Driver.java) では、コンパイル単位内のすべての副プログラムに対する
HIR最適化を行った後にLIRに変換してコード生成を行う。もしも副プログラムごとにHIR最適化と
コード生成を繰り返すコンパイラを作るとすれば、ドライバを修正する(サブクラスを定義する)必要がある。
HIR最適化のうち、大域的パタン照合による変換以外のすべての項目は制御フロー
解析を必要とするが、項目によってはデータフロー解析を必要としない。
データフロー解析は別名解析を必要とする。最適化の処理では、その処理に必要なフロー情報を要求すれば、
このような依存関係は自動的に解消されて、要求された情報が提供される。
HIR最適化には、基本最適化と拡張最適化がある。基本最適化では、制御フロー構造は変えないで、
基本ブロックの中の文の改変、追加、削除を行い、空になった基本ブロックも残す。拡張最適化では制御フロー構造も変更する。
その他に、coins.opt.Opt ではなく、CプログラムからHIRを生成するCフロントで行う最適化もあり、それは
java coins.driver.Driver -coins:hirOpt=fromc
というコマンドで実行される。
大域的パタン照合による変換は、
java coins.driver.Driver -coins:hirOpt=globalReform
というコマンドで起動される。これは入力パタンとそれに対する出力パタンの対応
を与えておき、HIRで表された式や文、あるいは文の列がいずれかの入力パタンに
適合するならば、それを対応する出力パタンに変換する。これによって、ある
限られた形ではあるが、ープ交換や末尾再帰のループ化、SIMDなどの特殊命令向き
の予備変換など、多様な変換を実現できる。
6.2 基本最適化
6.2.1 基本最適化の概要
制御フロー構造を変えない基本最適化の項目としては
noSimplify HIRの単純化変換をしない
cf 定数畳みこみ (constant folding)
cpf 定数伝播とそれに伴う畳みこみ (constant propagation and folding)
cse 局所的共通部分式削除 (local common subexpression elimination)
dce 無用命令削除 (dead code elimination)
gt 大域変数の一時変数化 (global variable temporalization)
が組み込まれている。cf と gt ではデータフロー解析を必要としないが、cpf, cse, dce では必要とする。
noSimplifyは最適化をする指定ではなく、HIR単純化の変換をしないという指定である。この指定がない場合は、HIRをLIRに変換する直前で、参照されないラベルを削除するなどの簡単な単純化変換を行う。これにはelse部のないif文に対して生成されていたelse-labelを削除するなどの効果がある。
6.2.2.1 定数畳み込み (hirOpt=cf)
算術式、比較式、論理式等のオペランドがすべて定数でコンパイル時に演算可能な場合には、その式を演算結果の定数で置き換える。
その置き換えによって新たな定数式置き換えが可能になればさらに置き換えることを繰り返す。
ただし、浮動小数点数の場合は、Javaによる演算と対象機種における演算で誤差が生じる可能性があるので、
hirOpt=evalFloatの指定のある時にのみ、コンパイル時に演算する。
6.2.2.2 定数伝播 (hirOpt=cpf)
定数を代入された変数はその後続文で定数と同様に扱う。ある変数が使われている点
に到達する定義(その変数への値の代入)が唯一で、代入される値が定数扱いとなった
変数は、後続点でも定数として扱う。定数扱いとなった変数の値を代入された変数はまた
定数扱いとなる。この最適化ではhirOpt=cf/cpfと指定する方が定数畳み込みとの
相乗効果を期待できてよい。
6.2.2.3 無用命令削除 (hirOpt=dce)
後続の文で値が利用されない式に対しては、それを演算する文を削除する。次のプログラム
int main ()
{
int a, b, c, d, x;
a = 1;
b = 2;
c = a + b;
d = a + b;
if (a+1 < c-1)
x = a - b;
else
x = a + b;
printf("%d\n",x);
}
に対して、定数畳み込み、定数伝播、無用命令削除の処理を行った結果のHIRは、HIR-to-CによってCで表現すると
int main( )
{
int a;
int b;
int c;
int d;
int x;
a = (int )1;
b = (int )2;
if (((int )2) < ((int )2))
{
x = ((a) - (b));
}
else
{
x = ((a) + (b));
}
(&(printf))( (const char * )((("%d\n"))),x);
}
となる。これを見ると、dの計算は削除され、if (a+1 < c-1) はコンパイル時に演算されて
if (2 < 2) に変換されることがわかる。バックエンドではif (2 < 2) がfalseであることを見て、
次のように、if文のelse部のみを残して他は削除する。
.global main
main:
save %sp,-96,%sp
.L18:
mov 1,%i1
mov 2,%i0
.L20:
add %i1,%i0,%o1
.L21:
sethi %hi(string.17),%o0
or %o0,%lo(string.17),%o0
call printf
nop
.L22:
ret
restore
6.2.2.4 局所的共通部分式削除 (hirOpt=cse)
局所的共通部分式削除では、1つの基本ブロック内に同じ演算があると、前の演算結果を一時変数に記録しておき、
後ろの演算をその一時変数でおきかえる。ただし、演算コストが設定された値より小さいものは、置き換えをせず再計算する。
その設定値は対象機種のMachineParamのメソッドを使って
costOfInstruction(MachineParam.COST_INDEX_TEMP_LOAD) + 3
として与えられる。式の中に式を含む複合された部分式では、最大の共通部分式に対する置き換えを行い、
その中の小さい部分式に対する置き換え処理はしない。
共通部分式としては、算術式などばかりでなく、添字付き変数や構造体要素などの複合変数の参照も対象とし、
その複合変数を構成する要素のいずれにも変更がなければその複合変数の値にも変更がないと見なして置き換えをする。
6.2.2.5 大域変数の一時変数化 (hirOpt=gt)
現在はLIRを対象とした別名解析をしていないので、別名を持つ可能性の高い大域変数はレジスタ化されにくい。
HIRでいくつかの条件に適合する大域変数を一時変数に置き換えると、LIRに変換された時、レジスタ化される可能性が増える。
また、RISCマシンでは大域変数は局所変数よりアクセスに時間がかかることが多い。そこで、
次の条件を満たしている大域変数が基本ブロック内で複数回参照されている場合(副プログラム呼び出しを含む基本ブロック
では呼び出しの前または後で複数回参照されている場合)、それを一時変数に置き換える。
- アドレスをとられていない
- 構造体要素、配列要素でない
- Volatile修飾されていない
これの効果は、多くの場合、1%未満であったが、ループ展開によって基本ブロックが長くなった場合、
約20%の実行時間削減になった例 (Loop/tpfor1.c) もある。
本機能の実装後、LIRに対する最適化として、変数のレジスタ化を促進する
java -coins:regpromote
が追加された。多くの場合にこちらの方が良い結果を出すので、regpromote を指定した
場合は hirOpt=gt は指定しなくてよい。
6.2.3 基本最適化の呼び出し方
基本最適化には、他の最適化の前処理あるいは後処理として呼ぶと効果のあるものがある。そのためには、
その最適化項目に対応するクラスのインスタンスを作り、たとえば
boolean lChanged = new ConstFolding(lResults).doSubp(lSubpFlow);
のようにすればよい。(coins.opt.Opt参照)doSubp メソッドは、その最適化によりHIRが変更されればtrue、
されなければfalseを返す。
6.3 拡張最適化
6.3.1 拡張最適化の概要
拡張最適化はコンパイル単位の副プログラムごとに適用されるもの
であり、次のオプション指定がある。
loopexp ループ展開
loopif ループ不変条件式を持つif文のループ外移動
inline インライン展開
inlinedepth 再帰的インライン展開の深さ指定
pre 部分冗長性削除
globalReform 大域的パタン照合
complexityAllowance プログラムの大きさによる最適化制御
これらのオプションによる最適化処理は、制御フロー構造を変えることがある。loopexp、loopif と inline はデータフロー解析を必要としないが、
pre は必要とする。部分冗長性削除は、大域的共通部分式削除やループ不変式のループ外移動などを行う。
これらの処理は次のコマンドで起動される。
java coins.driver.Driver -S -coins:hirOpt=loopexp
java coins.driver.Driver -S -coins:hirOpt=loopif
java coins.driver.Driver -S -coins:hirOpt=inline
java coins.driver.Driver -S -coins:hirOpt=pre
inlinedepthは、後述するように、inline展開の仕方を制御する。
globalReformについては、6.7節で説明する。
入力プログラムが大きいと、最適化処理に大量のメモリと長い処理時間を
要することがある。そのため、1つの副プログラムがある限度以上に
大きい場合は、それに対して最適化におけるいくつかの処理をバイパス
したり単純化したりすることがある。
complexityAllowanceは
-hirOpt=complexityAllowance.2
...
-hirOpt=complexityAllowance.9
のようにして、この限度を2〜9倍に緩和し、大きいプログラムに
対しても最適化の処理内容をバイパスしないことを指示する。
基本最適化と組み合わせる場合は、拡張最適化を行ったあとに基本最適化を行う方が効果的なことが多い。
6.3.2 拡張最適化の諸項目
6.3.2.1 ループ展開 (hirOpt=loopexp, hirOpt=loopif)
ループ展開では、ループ本体が短い最内側のforループを展開する。
その回数は、対象機種のレジスタ数とループ本体の複雑度によって決める。
その上限は、汎用レジスタ数が16以下なら4まで、それを越えると8までとしているが、
hirOpt=loopexp.2, hirOpt=loopExp.10 のように付加情報を指定すると、2とか10に変更できる。
最内側ループであっても、次のようなループは展開の対象としない。
ループ内で移動しても支障のない文は、同型演算をまとめるために移動する。
そのようにすると、他の最適化との相乗効果が大きくなると予想される。たとえば
for (i = 0; i < 100; i++) {
sum1 = sum1 + i;
sum2 = sum2 + a[i];
}
をループ展開すると
_var5 = 1*7;
_var7 = 1*8;
for (i = 0; i < 100 - _var5; i = i + _var7) {
sum1 = sum1 + i + i + 1 + i + 2 + i + 3 + i + 4 + i + 5
+ i + 6 + i + 7;
sum2 = sum2 + a[i] + a[i+1] + a[i+2] + a[i+3]
+ a[i+4] + a[i+5] + a[i+6] + a[i+7];
}
for (; i < 100; i = i + 1) {
sum1 = sum1 + i;
sum2 = sum2 + a[i];
}
となる。
6.3.2.2 if文のループ外移動 (hirOpt=loopif)
ループの中にループ不変な条件式をもつif 文があるときは、そのif文をループの外に出し、
then部とelse部をそれぞれループ文にする。たとえば
for (i = 0; i < pn; i++) {
lSum = lSum + pa[i];
if (pMode > 0)
lSum = lSum + i;
else
lSum = lSum + i * i;
}
は
if (pMode > 0) {
for (i = 0; i < pn; i++) {
lSum = lSum + pa[i];
lSum = lSum + i;
}
}else {
for (i = 0; i < pn; i++) {
lSum = lSum + pa[i];
lSum = lSum + i * i;
}
}
のように展開される。hirOpt=loopif/loopexp と指定すると、このthen部、
else部のループがさらに展開される。
6.3.2.3 インライン展開 (hirOpt=inline)
副プログラム呼び出しは、レジスタの待避・回復やスタック領域の確保・解放
などを伴う重い処理であり、短い副プログラムではこれらのオーバーヘッドの
比率が高くなる。インライン展開は、小さい副プログラムの本体を、それを
呼び出している (callしている)ところに展開することによって、オーバーヘッド
を減らそうとするものである。展開すると呼び出し元との間で共通部分式が
増えて最適化の機会が増えるという利点もある。オブジェクト指向プログラミング
などでは、小さい副プログラムが多数作られることが多く、これは実行速度向上
に有効である。ただし、展開すると目的コードは大きくなることが多い。
COINSで hirOpt=inline と指定するとインライン展開を行う。
ただし、次のような場合は展開しない。
- 副プログラムが大きい(ノード数が100を越える)。
- callがif文やループ文の条件式の中、あるいはswitch文の選択式の中にある。
ノード数の限界値は、hirOpt=inline.200 とすれば 200 までというように、コマンドで変更できる。
注釈:
hirOpt=inline の指定がなくても、(C言語の場合)プロトタイプ宣言と同列の場所で
#pragma optControl inline sub1 sub2 ...
のように記述すると、副プログラム sub1, sub2, ... を大きさ制限にかかわらず
インライン展開する。 -coins:hirOpt=inline では全ての関数に対してインライン展開
するか否 か調べるが、上記プラグマは指定されたものだけをインライン展開の対象とする。
ただし、大きさ以外の点でインライン展開に適さないと判定されたものは展開しない。
インライン展開では、副プログラムの定義が参照より後ろにある場合も展開する。
直接的または間接的に再帰する副プログラムもある定められた回数(2回)まで展開する。たとえば、
int fact(int p) {
if (p > 0)
return p * fact(p - 1);
else
return 1;
}
は
int fact( int p ) {
int _var1, _var3, _var5, _var7, _var9, _var11;
if (p > 0) {
_var1 = p - 1;
if (_var1 > 0) {
_var5 = _var1 - 1;
if (_var5 > 0) {
_var7 = _var5 - 1;
if (_var7 > 0) {
_var9 = _var7 * fact(_var7 - 1);
goto _lab19;
}else {
_var9 = 1;
goto _lab19;
}
_lab19:;
_var11 = _var5 * _var9;
goto _lab22;
}else {
_var11 = 1;
goto _lab22;
}
_lab22:;
_var3 = _var1 * _var11;
goto _lab12;
}else {
_var3 = 1;
goto _lab12;
}
_lab12:;
return p * _var3;
}
else {
return 1;
}
}
のように展開される。
この展開回数は、
-hirOpt=inlinedepth.3
とすると3回まで、
-hirOpt=inlinedepth.4
とすると4回までというように、変更できる。
6.3.2.4 部分冗長性削除 (hirOpt=pre)
部分冗長性削除は、大域的な共通部分式削除やループ不変式のループ外移動、if文の条件式の真偽によって冗長性が
発現したりしなかったりする場合の効率化を単一の方式で行う強力な最適化方式である
(Morel and Renvoise[1] , Nakata[3]参照 )。
まず部分冗長性削除の原理を簡単に説明する。
a = b + g;
if (a != 0) {
x = a + b;
}else {
x = b + g;
}
printf("%d \n", x);
y = (a + b) * (b + g);
printf("%d \n", y);
というプログラムでは、then部を通るときにはa+bが2度計算されるという
冗長性がある。このように、どの経路を通るかによって冗長性が生ずる
プログラムは、部分冗長性があると言う。部分冗長性を削除する方法を
追求してゆくと、どの経路を通っても冗長となる計算(完全冗長性)も
削除できる。その説明のために、もう少し議論を精密化する。
ある式eの計算は、eのオペランドが計算済みであり、その後オペランドの
値が変更されていない点にならば移動できる。このような点がいくつも
あるならば、制御の流れをできるだけさかのぼったところや、それらの
経路が合流している所に移動すると、同種の移動を少なくできる。
移動可能な点ですでにeが計算ずみとなっていれば、その移動は削除できる。
すなわち、その計算は削除できる。このような移動を試みることによって、
eの計算を完全冗長にすることができるとわかれば、eの計算を以前計算した
値で置き換えることによって、冗長性を削除できる。これが部分冗長性削除の
基本原理である。
その実現方法の詳細は前掲の文献等に譲るとして、ここでは例を使って
説明する。次の例は先の例に基本ブロック番号B1, B2, B3, B4を左端に
付記したものであり、a, b, x, yは局所変数、gは大域変数であるとする。
b+gはB1とB3, B4で計算され、a+bはifの条件式がtrueのときにのみ2回
計算される。式 b+gはB1, B3のいずれで計算しても同じ値となるが、
B4に関数呼び出しがあるので、その後では値が異なるかもしれないと判定する。
B1 a= b+g; b+gの値は B1, B3のいずれで
if (a != 0) { 計算しても同じ.
B2 x= a+b; a+bの値は B2, B3, B4の
} いずれで計算しても同じ.
B3 else { x= b+g;
}
B4 printf("%d \n",x); 大域変数gの値は関数呼び出し
y= (a+b)*(b+g); で変わるかもしれない.
printf("%d \n", y);
a+b は大域変数を含まず関数呼び出しの影響を受けないので、B2, B4のいずれで
計算しても同じ値となる。
hirOpt=preというオプションを指定すると、上記の解析結果に基づいて、
HIRを変換する。ここでは、HIR最適化を適用した結果をわかりやすくするため、
変換後のHIRをhir2cでCプログラムに変換したものを以下に示す。(hir2cによる
変換結果では、暗黙の型変換をすべて明示的に表現し、すべての部分式を括弧で
くくるので少し見づらくなるが、ここでは見やすいように少し整形している。)
これで見ると、最適化前ではifの条件式が真のときはa+bが2度計算されたのに
対し、最適化後では条件式の真偽にかかわらず、1回しか計算されない。
b+gの計算は、then部を通るときは1度再利用しているが、printfでgには
値を設定しないことまではコンパイラで判断していないため、printfの後で
もう一度計算している。
B1 _var1= b+g; b+gを保存し
a= _var1; 置き換え.
if (a != 0) {
B2 _var3= a+b; a+bを保存し
x= _var3; } 置き換え.
B3 else { x= _var1; 保存値を利用.
_var3= a+b; } a+bの計算をB4から移動.
B4 printf("%d \n", x);
y = _var3*(b+g); B2とB3の保存値を利用.
printf("%d \n", y);
次に、ループ不変式の扱いを見るために、次のプログラムをとりあげる。
ここでも左端のB1, B2, ..., B5は基本ブロックの番号である。
B1 for (i = 0;
B2 i < 10;
B4 i++) {
B3 c = c + (a + b);
}
B5 d = a + b;
式a+bの値は B2, B3, B4, B5のいずれで計算しても同じ値となるので、
それらの共通の上流点B1の末尾で計算してもよい。これに対して部分冗長性
削除を行った結果がどうなるかを示すため、変換後のHIRからhir2cでCに変換し
整形したプログラムを以下に示す。a+bの計算は、ループの初期化部分の末尾で
1回行われるだけになっている。
for ( i = 0,_var1 =a + b; i < 10; i = i + 1) {
c = c + _var1;
}
_lab4:;
d = _var1;
では、次に部分冗長性削除の実現方法について述べる。
実装した方法では、DhamdhereのE-pathPRE
のアルゴリズムを採用している。
これは削除可能経路 (E-path) という概念に基づくものである。
式eのE-path bi, bi+1, …, bk-1, bk
は次のように定義される。
- eは基本ブロックbiで局所的に利用可能(locally available)である。
すなわち、bi内でeが計算された後そのオペランドに値が設定されていない。
- eは基本ブロックbkで値が局所的に予測可能(locally anticipable)である。
すなわち、bkで式eが出現しているがその前ではオペランドに値が設定されて
いない。
- 経路 bi+1, … bk-1 には、eもeのオペランドも出現しない。
- 基本ブロック bi, bi+1, …, bk-1 の各々の
出口でeは利用可能(available)であるか値が予測可能(anticipable)である。すなわち、
eは計算済みであるかあるいはそのすべてのオペランドが計算済みである。(eあるいは
そのオペランドが未計算な経路からの流入がない。)
基本ブロックbjが式eのE-pathに含まれているとき、eの一時変数tへの
置き換えは、次のようにして行う。
- bjが開始ブロックでないとき、そのある先行基本ブロック
bhがeのE-pathに含まれていないとする。その場合、bhの
すべての後続ブロックがeのE-pathに含まれていればbhに t := e; を挿入し、
そうでなければbhからbjへの辺に t := e; を挿入する。
- bjが開始ブロックであってeのオペランドへの値設定を含んでいないなら、
eの値をtに設定する。
- bjがeのE-pathにおける先頭基本ブロックであれば、eの最後の出現点に
t := e; を挿入し、eをtで置き換える。
- bjがeのE-pathにおける末尾基本ブロックであれば、最初に出現した
eをtで置き換える。
これによって、ループ内で値の変わらないループ不変式をループの初期化部に
持ってゆくことなどの最適化が可能となる。
もう少し詳しく説明するために、まず各基本ブロックに対して次の記号を定義する。
(e は式を表すものとする。)
locally available: EGen (downward exposed)
After computation, operands are not changed.
available: AvailIn
locally anticipable: AntLoc (upward exposed)
Operands are not set in preceding operations
(before use) in a basic block.
safe: Either anticipable or available.
e-path([b_i ... b_k]) = set of eliminatable computation e included
in b_k, i.e.
{e | e is locally available in b_i and locally anticipable in b_k } &
empty((b_i ... b_k)) & // not computed in intermediate point
e is safe at exit of each node on the path [b_i ... b_k),
ここで b_i, ..., b_k は基本ブロック i, ..., k を表す。
E-path について次の条件を満たす最大のサフィックスをe-path suffix という。
AntIn * (not AvIn) = true for each node in it.
データフロー情報としては次のものを利用する。
Comp_i : e is locally available in b_i
Antloc_i : e is locally anticipable in b_i
Transp_i : b_i does not contain definitions of e's operands
AvIn_i : e is available at entry of b_i
AvOut_i : e is available at exit of b_i
AntIn_i : e is anticipable at entry of b_i
AntOut_i : e is anticipable at exit of b_i
EpsIn_i : entry of b_i is in an e-path suffix
EpsOut_i : exit of b_i is in an e-path suffix
Redund_i : Occurrence of e in b_i is redundant
Insert_i : Insert t_e := e in node b_i
Insert_i_j : Insert t_e := e along edge (b_i, b_j)
SaIn_i : A Save must be inserted above the entry of b_i
SaOut_i : A Save must be inserted above the exit of b_i
Save_i : e should be saved in t_e in node b_i
ここで t_e は式 e の値を保持する一時変数を表す。上記のデータフロー情報は
次のデータフロー方程式を解いて求める。
AvIn_i = PAI_p (AvOut_p)
AvOut_i = AvIn_i * Transp_i + Comp_i
AntIn_i = AntOut_i * Transp_i + Antloc_i
AntOut_i = PAI_s (AntIn_s)
EpsIn_i = SIGMA_p (AvOut_p + EpsOut_p) * AntIn_i * (not AvIn_i)
EpsOut_i = EpsIn_i * (not Antloc_i)
Redund_i = (EpxIn_i + AvIn_i) * Antloc_i
Insert_i = (not AvOut_i) * (not EpsOut_i) * PAI_s(EpsIn_s)
Insert_i_j = (not AvOut_i) * (not EpsOut_i) * (not Insert_i) * EpsIn_j
SaOut_i = SIGMA_s (EpsIn_s + Redund_s + SaIn_s) * AvOut_i
SaIn_i = SaOut_i * (not Comp_i)
Save_i = SaOut_i * Comp_i * (not Redund_i * Transp_i)
ここで _s は後続基本ブロック、 _p は先行基本ブロックを表す添字である。
また、PAI_sは後続基本ブロック全部に対する集合の積、SIGMA_pは先行基本ブロック
全部に対する集合の和、SIGMA_sは後続基本ブロック全部に対する集合の和を表す。
E-path_PRE による最適化は次のアルゴリズムに従って行う。
Save the value of e: computation t_e is inserted before an
occurrence of e and the occurrence of e is replaced by t_e
(as indicated by Save_i).
Insert an evaluation of e: A computation t_e <- e is inserted
(as indicated by Insert_i and Insert_i_j).
Eliminate a redundant evaluation of e: An occurrence of e is
replaced by t_e (as indicated by Redund_i).
部分冗長性削除の準備作業として、生成した文の挿入をやりやすくするため、
危険辺(critical edge)の削除を行う。危険辺とは、2つ以上の後続ブロックを
持つ基本ブロックから2つ以上の先行ブロックを持つ基本ブロックへ行く辺のことである。
たとえば
switch (i) {
case 0:
s = 0;
case 1:
s = s + i;
....
}
は
switch (i) {
case 0:
s = 0;
goto _lab11;
case 1:
{ _lab11:;
s = s + i;
}
......
}
のように変換する。
6.3.3. HIR最適化の効果
HIR最適化をいくつかの例題プログラムに適用したときのSparcにおける実行時間(秒)
を示す。*印は同じ行にならんでいるCOINSの測定値のうち最も速いものを示す。
参考までにSparc gcc -O2 の測定値を最後の列にあげ、COINSよりgccが速いものを
^印で示す。
例題 hirOpt hirOpt ssa no opt gcc -O2
+ ssa etc.
etc.
ISort 474.4 281.0 252.9* 474.5 194.5^
SSort 674.5 396.5 396.2* 561.9 336.9^
heap 115.9 104.6* 111.6 122.0 94.4^
komachi 208.7 163.1* 177.0 206.7 206.6
matmult 12.1 5.7* 7.0 13.0 7.2
prime 507.8 237.0* 243.6 503.0 320.5
queen 176.7 147.3 107.3* 157.7 146.2
shell 160.9 117.1 111.5* 157.2 104.7^
soukan 283.2 183.1* 214.1 388.0 222.8
target=sparc-v8 (UltraSPARC-IIs 450MHz)
hirOpt: hirOpt=inline/loopexp/cs/cpf/pre
ssa etc.: schedule,regpromote,ssa-opt= prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3
COINSの測定値で見ると、HIR最適化だけで十分な効果があるとは言えないし、
逆効果となる例もあるが、他の最適化と組み合わせることによって、効果の上がる
場合が多い。
6.4 Cフロントでの最適化 (hirOpt=fromc)
最適化項目として
java coins.driver.Driver -S -coins:hirOpt=fromc xxx.c
のように fromc を指定すると、CのソースプログラムをHIRに変換する際にいくつかの局所的な最適化を行う。それらは
v + 0 --> v
v * 1 --> v
!(a>b) --> a>=b
のような簡単なものが主であるが、条件式がtrueやfalseに変換される場合は制御構造の変更を伴うこともある。たとえば
if(true ) THEN; else ELSE;
--> { THEN; goto LABEL_END; ELSE; LABEL_END:; }
while(false) BODY;
--> { goto LABEL_BREAK; BODY; LABEL_BREAK:; }
のような変換を行う。この例で制御が到達しないように見えるELSE部やBODY部を残しているのは、
その中にgotoで飛んでくる場合などに対処できるようにするためである。
Cフロントでの最適化の大部分は、後続のHIRでの最適化やLIRでの最適化でカバーされるので、
指定する必要性は少ない。これを指定すると、HIRが少し短くなって後続の処理が少し単純化されるという効果はある。
6.5 フロー解析
6.5.1 フロー解析の概要
フロー解析には制御フロー解析とデータフロー解析があり、各々に幾つかの解析項目がある。
解析項目の間には依存関係による順序づけが要求される場合がある。たとえば項目Cは項目Bの結果を利用し、
項目Bは項目Aの結果を利用する場合、まずAを計算してからBを計算し、それからCを計算する必要がある。
フロー情報を利用するのにこのような順序関係をいちいち考えるのは煩わしいので、
COINSでは必要とするCを要求すれば自動的にそれに必要なA, Bの計算を行う機構が備えてある。
フロー情報には多くの種類がある。そこで、要求された情報とその算出に必要な情報のみを計算するように、項目を自動的に選択するようにしてある。
制御フロー解析は、副プログラムを基本ブロックに分割し、それらの間の接続関係を解析する。
データフロー解析は、変数に対する値の設定とその参照の関係をデータの流れを追う形で解析する。
これらの情報に基づいて、最適化や並列化の処理が行われる。
基本ブロックの中ではプログラムは一直線に走るので、制御フローは基本ブロックを
単位として考えればよい。すなわち、基本ブロックを頂点、その先行、後続関係を表す
矢印を辺とする有向グラフとして制御フローを表現すればよい。これを制御フロー
グラフ(CFG, control flow graph)と言う。HIRでは、制御文(if文、ループ文、
jump文、switch文、return文)とラベルに注目すれば、制御フローグラフを作る
ことができる。
プログラムの解析や変換に当たっては、制御フローグラフをある順序でたどる、
基本ブロックの中の文や式を順次見る、などの操作が必要になる。文の区切りと
基本ブロックの区切りは必ずしも一致しないので、その操作は少し複雑になるが、
COINSはこれらの操作を簡単に行うために、後述するような各種のメソッドを
備えている。
現在、フロー解析には次の2つの版があり、パッケージが分かれている。
coins.flow: HIR最適化のすべての項目で利用されている新しい版
coins.aflow: ループ並列化(LoopPara)と粗粒度並列化(-coins:mdf)
で利用されている古い版
新規に作るモジュールでフロー解析を利用する場合はcoins.flowにある新しい版を利用する方が望ましい。
coins.aflowの版は、1つの副プログラムが500行以上というように大きくなると、
解析に長い時間と大きなメモリを必要とする。
覚え書き:
フロー解析にはさらにもう一つ古い版があったが、それは今は使われていない。
バックエンドにも第1版があり、現在のバックエンドは第2版である。
廃版となったフロー解析は、HIRとLIRに共通の形で作られていて、第1版のバックエンドは
制御フロー解析とデータフロー解析にそれを利用していた。
そのフロー解析では、HIR用とLIR用のコードは
共有部 11891行
HIR固有部 2146行
LIR固有部 1765行
合計 15802行
というように、75%が共有できていた。しかし、フロー情報を要求に応じて計算する
機能はまだ入っていなかったので、それを備えるとともにインタフェースを
改良するためにaflow版のフロー解析部を作ったが、それはHIRには適用できるが
LIRには適用できるようになっていない。第2版のバックエンドのLIRに対しては、
SSA最適化やコード生成などの際にそれぞれの処理に必要なフロー情報を個別に
求めている。LIRに対してもデータフロー解析の情報をHIRに対するのと同様な
形で提供し、個別に作らなくてよいようにするのは今後の課題である。
フロー解析のインタフェースが HIRを引数とするのではなく、HIRとLIRの
上位クラスであるIRを引数とするようにしてあるのは、将来の拡張のためである。
6.5.2 coins.flowパッケージでのフロー解析
6.5.2.1 制御フロー解析
制御フロー解析では指定された副プログラムに対して
- CFG (Control Flow Graph, 制御フローグラフ)
- 基本ブロック(BBlock)間の支配関係
を計算する。
ここで、制御フロー解析とデータフロー解析の説明でよく使う記号について説明しておく。
flowRoot: フロー情報へのリンクの根となるFlowRootクラスの
インスタンス(通常はDriverから渡される)。
subpDefinition: SubpDefinitionのインスタンスで、対応する副プログラム
のHIR部分木などを持つ。
subpFlow: SubpFlowクラスのインスタンスで、対応する副プログラムの
制御フロー情報やデータフロー情報を持つ。
SubpFlowにはHirSubpFlowというサブインタフェースがあり、その実現クラスが
HirSubpFlowImplである。HIRフロー解析では、HirSubpFlowImpl のインスタンスを
対象とする副プログラムに対して1度だけ作る。
その副プログラムに関するすべての制御フロー情報とデータフロー情報は、そのインスタンスからたどるようになっている。
このインスタンスを作り直すと、それまでに計算したすべてのフロー情報はリセットされ、アクセスできなくなる。
SubpFlow のインスタンスを作るには次のようにする。
coins.flow.SubpFlow lSubpFlow = new HirSubpFlowImpl(flowRoot, subpDefinition);
これを実行すると、SubpFlowのインスタンスは lSubpFlowばかりでなく
flowRoot.fSubpFlow
によっても参照できる。
制御フロー解析を行うには、次の文によってその準備を行う。
flowRoot.flow.controlFlowAnal(lSubpFlow);
そうすると、基本ブロックに関する次のようなメソッドが利用可能になり、制御フロー情報の取得とそれに基づく操作ができるようになる。
cfgIterator(), getEntryBBlock(), getBBlockOfIR(ir.getIndex()),
bblockSubtreeIterator(bblock), ...
その他にも多くのメソッドがcoins.flow.SubpFlowインタフェースに用意されている。
また、controlFlowAnal(lSubpFlow)を実行すると、基本ブロックのインタフェースcoins.flow.BBlockにおける
次のようなメソッドも使えるようになる。
getPredList(), getSuccList(),
getImmediateDominator(), getPostDominatedChildren(), ...
制御フロー解析の結果を見ようとするなら
coins.flow.ShowControlFlow lShow = flowRoot.controlFlow.getShowControlFlow();
lShow.showAll();
というようなコーディングをすると、標準出力に結果が表示される。
flowRoot.flow.controlFlowAnal(lSubpFlow);
という文を実行すると、それまでの制御フロー情報は破棄されて、要求される情報を再計算する。
いくつかの最適化項目を連続して行う場合、もし前回計算したときから見て副プログラムのHIRが変化していなければ、
そのような再計算をする必要がない。無用な再計算をしないようにするには、次のようなコーディングを行えばよい。
if (flowRoot.flow.getFlowAnalStateLevel() <
coins.flow.Flow.STATE_CFG_AVAILABLE)
flowRoot.flow.controlFlowAnal(lSubpFlow);
最適化などの処理でHIRを書き換えた場合、あとで述べるようにfinishHir()というメソッドを呼ぶ必要がある。
finishHir() や setIndexNumbetToAllNodes() を呼び出すと、フロー情報の再計算が必要なことを示すために
getGlowAnalStateLevel() < coins.flow.Flow.STATE_CFG_AVAILABLE)
という条件式の値がtrue となるように設定を変更する。
6.5.2.2 データフロー解析
データフロー解析では各々の変数に識別番号をつける。またデータの流れを表現できるよう、
変数への値の設定やその値の参照を行うプログラム点に位置番号をつける。それらの番号は副プログラム内で局所的に割り振られる。
また、式にはその識別と情報表現のために、expression identifier (ExpId) というオブジェクトを対応させる。
ExpIdを導入することにより、HIRのExpとして表される配列要素や構造体要素などの複合変数に対しても、
データフロー解析においてスカラー変数と同様の扱いをすることが可能となる。データフロー解析の対象となる記号を
FlowAnalSymというクラスにまとめる。変数とExpIdはFlowAnalSymのインスタンスであり、
もしレジスタをデータフロー解析の対象とする場合はそれもFlowAnalSymに含める。
データフロー解析では、別名解析も自動的に行われるが、その情報をどのように使うかは
最適化や並列化の処理に任されている。データフロー解析のアクセスメソッドでは、
各文に対して、確実に値が設定される変数と別名等によって値が設定される可能性のある
変数を区別できるようになっている。
6.5.2.3 データフロー情報
データフロー情報は、各基本ブロックにおいて、ある条件を満たす変数や式、
プログラム点としてはどのようなものがあるか、という形で表現する。これは各対象
に対して1ビットで表現できるので、ある条件を満たす変数や式の集合を表す
ビットベクターを基本ブロックごとに用意し、単純変数や複合変数、演算式の
(ExpIdの)インデックスでその情報のビット位置を表す。同様に、ある条件を満たす
プログラム点の集合は、プログラム点を表すビットベクトルによって表現する。
データフロー情報は、まず基本ブロック内だけ見て決めることのできる情報を求め、
ついで隣接基本ブロックにその情報を渡してゆく処理を繰り返すことによって、
制御フローグラフ全体に対する情報を求める。以下、Bは基本ブロックを表し、
変数は単純変数や複合変数を表すとして、それらについて説明する。変数xの定義点
とは、xへ値を設定する点のことである。基本ブロック内だけ見て決めることのできる
情報には次のようなものがある。
Def(B) : Bにおける変数の定義点の集合
Defined(B): Bで値の設定される変数の集合
Exposed(B): Bで値設定をする前に使っている変数の集合
Used(B) : Bで使われている変数の集合
EGen(B) : Bで計算されたあと、Bの中ではそれ以降、
そのオペランドに対する値変更がない式の集合
EKill(B) : Bでオペランドに値設定があるため、以前に
計算された値がBの出口では無効となっている
式の集合
制御フローグラフ全体を見て求める情報としては次のものがある。
Kill(B) : 変数xへの値設定のうち、Bでのxへの値設定
によって無効にされる定義点の集合
Reach(B): 変数の定義点のうち、Bの入り口まで無効に
されずに到達するものの集合(到達定義)
AvailIn(B): 計算された値が無効にされずにBの入り口
まで伝わってきている式の集合
AvailOut(B): 計算された値が無効にされずにBの出口
まで伝わってきている式の集合
LiveIn(B) : 設定された値がBかBの後ろで使われる変数
の集合
LiveOut(B): 設定された値がBの後ろで使われる変数
の集合
DefIn(B): どの経路を通ってもBの入り口で値が設定
済みとなっている変数の集合
DefOut(B): どの経路を通ってもBの出口で値が設定済み
となっている変数の集合
DefUseList(xの定義点): その定義点で設定した値を使う
参照点のリスト
UseDefList(xの参照点): xの参照点まで無効にされずに
伝わるxの定義点のリスト
これらの情報があるとこれまでに述べた最適化の処理が可能になる。これらの用語は
もっと正確に言うと次のようになる。まずデータフロー解析の説明に使う記号を述べる。
x, y, t, u : 演算や代入のオペランドとなる変数
(変数は配列要素や構造体要素などの複合変数でもよい)
op : 演算子
def(x) : x への値の設定(定義)
def(x, y, ...) : x, y, ... への値の設定
use(x) : x の値参照
p(def(x)) : プログラム点 p において x への値の設定がある
p(use(x)) : プログラム点 p において x の参照がある
or_all(z) : z で表されるすべての要素に対する or 演算
and_all(z) : z で表されるすべての要素に対する and 演算
データフロー解析で求める情報は次のとおりである。
Def(B) =
{ p | for some x, p(def(x)) is included in B and after that point
there is no p'(def(x)) in B. }
Kill(B) =
{ p | for some x, p(def(x)) is included in B' (where, B' != B)
and there exists some defining point of x p'(def(x)) in B. }
Reach(B)=
{ p | there is some path from program point p defining x
(that is p(def(x))) to the entry of B such that there is
no p'(def(x)) on that path. }
Reach(B) = or_all( (Def(B') | (Reach(B') - Kill(B')))
for all predecessors B' of B)
Defined(B) =
{ x | x is defined in B. }
Exposed(B) =
{ x | x is used in B and x is not defined in B
before x is used. }
Used(B) =
{x|x is used in B}
EGen(B) =
{ op(x,y) | expression op(x,y) is computed in B and after
that point, neither x nor y are defined in B. }
Thus, the result of op(x,y) is available after B.
EKill(B) =
{ op(x,y) | operand x or y is defined in B and the
expression op(x,y) is not re-evaluated after
that definition in B. }
If t = op(x,y) is killed in B,
then op(t,u) should also be killed in B.
AvailIn(B) =
{ op(x,y) | op(x,y) is computed in every paths to B and
x, y are not defined after the computations
on the paths. }
Thus, the result of op(x,y) can be used without
re-evaluation in B.
AvailOut(B) =
{ op(x,y) | op(x,y) is computed in every paths to the exit of B and
x, y are not defined after the computations
on the paths. }
Thus, op(x,y) can be used without re-evaluation after B.
Following relations hold.
AvailIn(B) = and_all(AvailOut(B') for all predecessors B' of B)
if B is not an entry block;
AvailIn(B) = { } if B is an entry block.
AvailOut(B) = EGen(B) | (AvailIn(B) - EKill(B))
LiveIn(B) =
{ x | x is alive at entry to B, that is, on some path from
entrance point of B to use point of x, x is not defined. }
Thus, x in LiveIn(B) should not be changed until it is used.
LiveOut(B) =
{ x | x is live at exit from B, that is, there is some
path from B to B' where x is in Exposed(B'). }
Following relations hold.
LiveOut(B) = or_all(LiveIn(B') for all successors B' of B
LiveIn(B) = Exposed(B) | (LiveOut(B) - Defined(B))
DefIn(B) =
{ x | x is always defined at entry to B whichever path
may be taken. }
DefIn(B) = and_all(DefOut(B') for all predecessors B' of B)
DefOut(B) =
{ x | x is always defined at exit from B whichever path
may be taken.}
DefOut(B) = Defined(B) | DefIn(B)
Reach(p(use(x))) =
{ p'(def(x)) | there are some paths from p to p' on which
x is not re-defined. }
DefUseList(p(def(x))) =
{ p'(use(x)) | p(def(x)) is included in p'(use(x)). }
UseDefList(p(use(x))) =
{ p'(def(x)) | p'(def(x)) is included in p(use(x)). }
6.5.2.4 データ構造
データフロー情報の内部表現としてはビットベクターやリストなどがある。
新しいデータフロー情報を算出するときは、それに対するデータフロー方程式を解く必要がある。
そのような目的のために、本データフロー・パッケージでは、ビットベクター表現に基づく次のようなメソッドが備えてある。
expVector, pointVector, vectorAnd, vectorOr, ...
BitVectorインタフェースにあるこれらのメソッドを使うことにより、新しいデータフロー
情報の表現とそれを求める手続きを記述することができる。
ビットベクター表現では、フロー情報はIRノードの位置番号と記号の識別番号を直接の
手がかりとしてアクセスするが、記号そのものを引数としてアクセスすることもできる。
BBlockVector は各基本ブロックに対して0/1の情報を対応させる。
このベクターでも他のいずれのビットベクターでも、1はtrue、0はfalseを表す。
DefVector は値を設定する各ノードに対して0/1の情報を対応させる。
PointVector は各IRノードに対して0/1の情報を対応させる。
FlowAnalSymVector は変数やExpIdなどの各記号に対して0/1の情報を対応させる。
ExpVector is はデータを設定、参照する各式に対して0/1の情報を対応させる。
式はそれに対応するExpIdで識別する。
記号の識別番号やIRノードの位置番号は(副プログラムごとに)1, 2, 3, ... と
割り付ける。0という番号は使わないので、ビットベクターの0の位置は使わない。
6.5.2.5 使い方
データフロー情報は要求に応じて算出する。Aという情報が要求されれば、もしそれが算出されていなければ
Aとその計算に必要な情報を計算するだけで、要求されない情報は計算しない。要求された情報が計算済みであればそれを再利用し、計算を省略する。
データフロー解析を行うには、まず
flowRoot.flow.dataFlwoAnal(subpDefinition);
によってその準備を行う。これによってcoins.flow.SubpFlow インタフェースの
getDefinedSyms(), getUsedSyms(), ...
などの多数のメソッドが使えるようになり、coins.flow.BBlockインタフェースのメソッド
getDefIn(), getDefOut(), getRech(), getLiveIn(), getLiveOut(),
getAvailIn(), getAvailOut(), ....
なども使えるようになる。SubpFlow インタフェースのメソッドはそのインスタンス
flowRoot.fSubpFlow
を介して呼び出せる。
上記の dataFlowAnal(subpDefinition) を実行するとそれまでに計算されたデータフロー情報はリセットされ、
次に要求されたときは再計算される。もし処理中の副プログラムのHIRが前回計算したときから変わっていなければ
このような再計算は不要である。無駄な再計算をしないようにするには次のようなコーディングを行えばよい。
if (flowRoot.flow.getFlowAnalStateLevel() <
coins.flow.Flow.STATE_DATA_FLOW_AVAILABLE)
flowRoot.dataFlow = flowRoot.flow.dataFlowAnal(subpDefinition);
制御フロー解析のときと同じように、finishHir() や setIndexNumbetToAllNodes() を呼び出すと、
データフロー情報の再計算が必要なことを示すために
getFlowAnalStateLevel() < coins.flow.Flow.STATE_DATA_FLOW_AVAILABLE
という条件式の値がtrue となるように設定が変更される。
最適化などの結果として副プログラムのHIRの書き変えが終わったとき、HIRにの各ノードに番号をふり直す
とともに不整合がないか調べるなどの操作を行うために、finishHir()というメソッドを呼ぶ必要がある。
これを呼ぶとフロー情報の再計算が要求されるので、最適化によってHIRに変更がなかった場合はfinishHir()を
呼ばないようにすべきである。そのため、最適化のモジュールではHIRの書き変えがなされたか否かを返却値として
返すようにすべきである。(coins.Opt 参照)
HIRの共通部分式は部分木として表現されている。式に対応する部分木にはすでに述べたようにExpIdが対応する。
構造が同じでオペランドも同じ部分木には同じExpIdが対応する。(同じ形の部分木で
あっても左辺値と右辺値では異なるExpIdが対応し、左辺値のExpIdに対する右辺値ExpIdを
求めるメソッドがある。)従って、共通部分式を探すのは単純な作業になるが、
共通部分式削除では、オペランドの値が変更されていないことを確認するとともに、値の不変な最大の部分木を求める必要がある。
HIRの式は一般に多くのオペランドを含み、callを含むこともある。最適化処理ではオペランドの値が変わる可能性の
有無やcallの有無を調べることがしばしば必要になる。そのたびに部分木を走査しなくてよいように、
文扱いの部分木にはSetRefRepr というクラスのオブジェクトを対応させ、文の情報はそこから、
式の情報はExpIdから参照できるようにしてある。
変数の値を設定するのは代入文とcallである。変数を参照するのは、変数をオペランドとする式である。
HIRのデータフロー解析においては、代入文とcall、if文やループ文に現れる条件式、swichのcase選択式、
return文を調べる必要がある。変数の値の設定・参照は、その他のHIR部分木では間接的には行われても直接には行われない。
そこで、次のものに対して SetRefRepr のインスタンスを割り付ける。
AssignStmt
AsmStmt
Conditional expressions in LoopStmt (ExpStmt)
Subprogram call
ReturnStmt
これらはデータフロー解析において、文と同等の扱いをする。SetRefRepr に対しては、次のメソッドが利用できる。
defSym() 値が確実に設定される記号の集合
modSyms() 値が設定される可能性のある記号の集合
useSyms() 値が確実に参照される記号の集合
式に対応させたExpIdに対しては次のメソッドが利用できる。
getOperandSet() オペランドとして使われる変数の集合
getExpInf().hasCall() 式がcallを含めばtrue, 含まなければfalse
SubpFlow インタフェースには、対応する副プログラムに関する情報取得や操作を行う次のメソッドが用意されている。
cfgIterator() 到達可能なすべての基本ブロックをたどるイテレータ
bblockSubtreeItrator(BBlock pBBlock) pBBlockの最上位部分木をたどる
イテレータを求める。最上位部分木とは次のものを表す。
LabeledStmt, AssignStmt, AsmStmt, ExpStmt, ReturnStmt,
IfStmt, LoopStmt, SwitchStmt
Conditional expression in IfStmt and LoopStmt
Case-selection expression in SwitchStmt
Call subtree (irrespective of contained in ExpStmt or Exp)
bblockStmtIterator(BBlock pBBlock)
pBBlockのすべての文をたどるイテレータ
bblockNodeIterator(BBlock pBBlock)
pBBlockのすべてのノードをたどるイテレータ
getSetRefReprOfIR(IR pIr) pIrに対応するSetRefRepr(なければnull)
getExpId(IR pIr) pIrに対応するExpId(なければnull)
getExpOfTemp(Var pTemp) 一時変数 pTemp の表す式
setOfGlobalVariables() 使われている大域的変数の集合
(callで値が設定される可能性がある)
setOfAddressTakenVariables() アドレスをとられている変数の集合
(ポイント先代入とcallで値が設定される可能性がある)
getRecordAlias() 別名情報の参照に使うRecordAlias のインスタンス
DefUseList と UseDefList の算出では、値が確実に設定・参照されているもののリストを作る。
それは、設定・参照の可能性のあるものをすべて含めると、設定・参照リストが長大になるためである。
値の設定参照については、確実なものがわかっていれば、それらに対する別名集合や、大域的変数の集合、
アドレスをとられている変数の集合などから、可能性のあるものの集合を求めることができる。
フロー情報について例で説明するために次のプログラムをとりあげてみる。
int printf(char*, ...);
int func(int pa[10], int pn);
int ga1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main()
{
int a = 1, b = 2, c, d;
int i = 0;
int *ptrc, *ptry;
int sum;
int x[10];
int y[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int z[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int zz[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
ptrc = &c;
ptry = y;
x[i] = a;
*ptrc = x[i] + 1;
sum = c + func(z, 10);
d = zz[2] + zz[3];
printf(" sum=%d ", sum);
for (i = 0; i < 10; i++) {
d = d + (zz[2] + zz[3]);
d = d + z[i] + z[i];
d = d + zz[i] + zz[i];
sum = ga1[i] + ga1[i];
sum = sum + *ptry;
printf(" *ptry=%d d=%d ", *ptry, d);
ptry = ptry + 1;
sum = sum + z[i] + z[i];
sum = sum + zz[i] + zz[i];
d = d + ga1[i] + ga1[i];
}
d = d + ga1[2] + ga1[2];
printf("\n");
d = d + (zz[2] + zz[3]);
d = d + ga1[2] + ga1[2];
printf("%d %d %d \n", sum, c, d);
return 0;
}
これに対するHIR基本ブロックは次のようになる。
BBlock 1: statements from the beginning up to "i=0;" of for-statement
BBlock 2: conditional expression "i < 10"
BBlock 3: from "d=d+(zz[2]+zz[3]);" to "d=d+ga1[i]+ga1[i];"
BBlock 4: "i++"
BBlock 5: rest of statements (from "d=d+ga1[2]+ga1[2];" to "return 0;")
アドレスをとられた変数は次のものである。
setOfAddressTakenVariables() = { c, z, y }
各基本ブロックに対するAvailIn, AvailOutは次の通りである。ここでは複合変数も式として扱っている。
BBlock 1
AvailOut= { zz[2], zz[3], &c, zz[2]+zz[3] }
BBlock 2
AvailIn = { zz[2], zz[3], &c, zz[2]+zz[3] }
AvailOut= { zz[2], zz[3], &c, zz[2]+zz[3], i<10 }
BBlock 3
AvailIn = { zz[2], zz[3], &c, zz[2]+zz[3] }
AvailOut= { zz[2], zz[3], &c, zz[2]+zz[3], i<10, z[i], zz[i], ga1[i] }
BBlock 4
AvailIn = { zz[2], zz[3], &c, zz[2]+zz[3], i<10, z[i], zz[i], ga1[i] }
AvailOut= { zz[2], zz[3], &c, zz[2]+zz[3] }
BBlock 5
AvailIn = { zz[2], zz[3], &c, zz[2]+zz[3], i<10 }
AvailOut= { zz[2], zz[3], &c, zz[2]+zz[3], i<10 }
ポイント先代入文 "*ptrc = x[i] + 1;" ではアドレスをとられた変数は値が変更される可能性があると見なしている。
defSym = { *ptrc }
modSyms= { c, *ptrc, z, ptrc, y }
関数呼び出しを含む式 "sum = c + func(z, 10);", では大域的変数の値が変更される可能性があると見ている。
defSym = { sum }
modSyms= { z, ga1, sum }
注釈:
coins.SourceLanguageクラスのgetFunctionsWithoutSideEffect() で返される集合
に含まれる副プログラムに対しては、大域的変数の値が変更されることはないと判断する。
副作用なし副プログラムの指定は、Cでは大域変数の宣言と同列の場所で
#pragma optControl functionsWithoutSideEffect func1 func2 ...
#pragma optControl functionsWithSideEffect func11 func12 ...
のように記述することにより、コンパイル単位ごとに変更できる。前者の指定は
func1, func2, ... を副作用なしと宣言し、後者の指定は func11, func12, ... を
副作用ありと宣言する。指定のない副プログラムは副作用ありとして扱う。
部分冗長性削除では、これらの情報に基づいて、callのあとで ga1[i]+ga1[i] は再計算するが z[i]+z[i]
は共通部分式と見なして再計算せず、zz[2]+zz[3] はループ不変式と見てループに入る前にその計算結果を一時変数に記録し、
以後はその式を一時変数で置き換える。
次に、上にあげたメソッドを使う例を示す。ここで、flowRoot は FlowRoot のインスタンスであり、
subpDefinition はSubpDefinition のインスタンスである。
SubpFlow lSubpFlow = new HirSubpFlowImpl(flowRoot, subpDefinition);
ControlFlow lControlFlow = flowRoot.flow.controlFlowAnal(lSubpFlow);
DataFlow lDataFlow = flowRoot.flow.dataFlowAnal(lSubpFlow);
RecordAlias lRecordAlias = lSubpFlow.getRecordAlias();
for (Iterator lBBlockIterator = lSubpFlow.cfgIterator();
lBBlockIterator.hasNext(); ) {
BBlock lBBlock = (BBlock)lBBlockIterator.next();
ExpVector lAvailableExp = lBBlock.getAvailIn();
for (BBlockSubtreeIterator lSubtreeIterator
= lSubpFlow.bblockSubtreeIterator(lBBlock);
lSubtreeIterator.hasNext(); ) {
HIR lSubtree = (HIR)lSubtreeIterator.next();
SetRefRepr lSetRefRepr = lSubpFlow.getSetRefReprOfIR(lSubtree);
Set lModSyms = lSetRefRepr.modSyms();
Set lModSymsAlias = fRecordAlias.aliasSymGroup(lModSyms); // Set of
// symbold aliased to some of modified variables.
for (ExpVectorIterator lExpIterator = lAvailableExp.expVectorIterator();
lExpIterator.hasNext(); ) {
ExpId lExpId = nextExpId();
Set lOperands = lExpId.getOperandSet();
if (! lOperands.retailAll(lModSymsAlias).isEmpty()) {
// Treat the expression corresponding to lExpId as unavailable
// because some operand may be changed by the subtree lSubtree.
}
......
}
....
}
....
}
データフロー解析の結果を見るには、
flowRoot.dataFlow.showSummary();
という文を実行すればよい。これは小さい副プログラムで試すのがよい。
何百行もある大きい副プログラムに対しては、標準出力に大量の情報が出力される。
6.5.2.6 フロー解析の拡張方法
何かの最適化処理のために新しいフロー解析情報が必要となった場合、その最適化処理
の中で現在の備え付け機能を使いながらその必要情報を計算するか、あるいはHirSubpFlow
のサブクラスを定義してその中に新しいフロー情報を計算するメソッドを作ればよい。
(HirSubpFlowはSubpFlowのサブクラスである。)たとえば、各基本ブロックに対して、
その中で値が設定もされず無効にもされない(オペランドの値が設定されない)式の集合を求めるとした場合、
次のようなMySubpFlowというサブクラスを作って、その中に getTransparent という名前のメソッドでその情報が得られるようにすればよい。
package coins.flow;
import coins.FlowRoot;
import coins.ir.hir.SubpDefinition;
import java.util.Iterator;
public class
MySubpFlow extends HirSubpFlowImpl implements HirSubpFlow
{
ExpVector fTransparent[];
public MySubpFlow(FlowRoot pFlowRoot, SubpDefinition pSubpDefinition)
{
super(pFlowRoot, pSubpDefinition);
} // MySubpFlow
public void
computeTransparent()
{
ExpVector lEKillAll;
ExpVector lTemp1 = expVector();
ExpVector lTemp2 = expVector();
FlowAnalSymVector lDefined;
int lBBlockNum;
fTransparent = new ExpVector[fBBlockCount + 1]; // Get space
// to record transparent vectors for all basic blocks.
for (Iterator lIterator = cfgIterator();
lIterator.hasNext(); ) { // Repeat for each basic block.
BBlock lBBlock = (BBlock)lIterator.next();
if (lBBlock == null)
continue;
lBBlockNum = lBBlock.getBBlockNumber(); // Get basic block number.
fTransparent[lBBlockNum] = expVector(); // Initiate by zero vector.
lEKillAll = lBBlock.getEKillAll(); // Get the cumulative set of
//expressions killed by some statements in this BBlock.
lEKillAll.vectorNot(lTemp1); // lTemp1 is negation of lEKillAll..
// Get the set of defined variables.
lDefined = (FlowAnalSymVector)lBBlock.getDefined();
lTemp2 = lDefined.flowAnalSymToExpVector(); // Change the set to vector.
lTemp1.vectorSub(lTemp2, fTransparent[lBBlockNum]);
// fTransparent[lBBlockNum] = lTemp1 - lTemp2
if (fDbgLevel > 1) // If trace=Flow.2 or more, print the result.
ioRoot.dbgFlow.print(2, "Transparent B"+lBBlockNum,
fTransparent[lBBlockNum].toStringShort());
}
setComputedFlag(DF_TRSNSPARENT); // Set already-computed flag.
} // computeTransparent
/**
* Get the transparent expression for the basic block pBBlock.
* Expressions are represented by ExpId corresponding to the expression.
* @param pBBlock basic block.
* @return expression vector showing transparent expressions.
*/
public ExpVector
getTransparent( BBlock pBBlock )
{
if (! isComputed(DF_TRSNSPARENT)) // If already computed,
computeTransparent(); // do not re-compute but reuse.
return fTransparent[pBBlock.getBBlockNumber()];
} // getTransparent
} // MySubpFlow
この例では、無用な再計算を避けるために使うフラッグの番号を
public static final int DF_TRANSPARENT = 26;
のように SubpFlow.java に追加する必要がある。このサブクラスを使うには、先の例で
SubpFlow lSubpFlow = new HirSubpFlowImpl(flowRoot, subpDefinition);
とする代わりに
SubpFlow lSubpFlow = new MySubpFlow(flowRoot, subpDefinition);
とすればよい。
6.5.3 coins.aflow パッケージでのフロー解析(旧版)
6.5.3.1 フロー情報
coins.aflow でも制御フロー情報は coins.flow と同じである。データフロー情報の違いは、
「確実な情報」と「可能性のある情報」の両者を計算することである。
その説明に使う記号をまず述べる。
x, y, t, u : 演算や代入のオペランドとなる変数
(変数は配列要素や構造体要素などの複合変数でもよい)
op : 演算子
def(x) : x への値の確実な設定(定義)
mod(x) : x への値の設定の可能性があること
use(x) : x の値参照
p(def(x)) : プログラム点 p において x への値の確実な設定がある
p(mod(x, y, ...)) : プログラム点 p において x, y, ... への
値の設定の可能性がある
p(use(x)) : プログラム点 p にいて x の参照がある
or_all(z) : z で表されるすべての要素に対する or 演算
and_all(z) : z で表されるすべての要素に対する and 演算
データフロー解析では次の情報を要求に応じて算出する。
PDef(B) =
{ p | p(mod(x, y, ...)) is included in B and after that point there is
no p' s.t. p'(def(x)) nor p" s.t. p"(def(y)), ... in B. }
DKill(B) =
{ p | p(def(x)) is not included in B and
p'(def(x)) is included in B. }
PReach(B)=
{ p | there is some path from program point p
that modifies some variables x, y, ... (that is, p(mod(x, y, ...)))
to the entry of B such that there is no p'(def(x)) or no p''(def(y))
or ... on that path. }
PReach(B) = or_all( (PDef(B') | (PReach(B') - DKill(B')))
for all predecessors B' of B)
DDefined(B) =
{ x | x is definitely modified in B. }
PDefined(B) =
{ x | x is posibly modified in B. }
PExposed(B) =
{ x | x is possibly used in B and x is not definitely set in B
before x is used. }
PUsed(B) = {x|x is possibly used in B}
DEGen(B) =
{ op(x,y) | expression op(x,y) is computed in B and after
that point, neither x nor y are possibly set in B. }
Thus, the result of op(x,y) is available after B.
PEKill(B) =
{ op(x,y) | operand x or y is possibly modified in B and the
expression op(x,y) is not re-evaluated after
that definition in B. }
If t = op(x,y) is killed in B,
then op(t,u) should also be killed in B.
DAvailIn(B) =
{ op(x,y) | op(x,y) is computed in every paths to B and
x, y are not modified after the computations
on the paths. }
Thus, the result of op(x,y) can be used without
re-evaluation in B.
DAvailOut(B) =
{ op(x,y) | op(x,y) is computed in every paths to the exit of B and
x, y are not modified after the computations
on the paths. }
Thus, op(x,y) can be used without re-evaluation after B.
Following relations hold.
DAvailIn(B) = and_all(DAvailOut(B') for all predecessors B'
of B) if B is not an entry block;
DAvailIn(B) = { } if B is an entry block.
DAvailOut(B) = DEGen(B) | (DAvailIn(B) - PEKill(B))
PLiveIn(B) =
{ x | x is alive at entry to B, that is, on some path from
entrance point of B to use point of x, x is not definitely set. }
Thus, x in PLiveIn(B) should not be changed until it is used.
PLiveOut(B) =
{ x | x is live at exit from B, that is, there is some
path from B to B' where x is in PExposed(B'). }
Following relations hold.
PLiveOut(B) = or_all(PLiveIn(B') for all successors B' of B
PLiveIn(B) = PExposed(B) | (PLiveOut(B) - DDefined(B))
DDefIn(B) =
{ x | x is always defined at entry to B whichever path
may be taken. }
DDefIn(B) = and_all(DDefOut(B') for all predecessors B' of B)
DDefOut(B) =
{ x | x is always defined at exit from B whichever path
may be taken.}
DDefOut(B) = DDefined(B) | DefIn(B)
6.5.3.2 呼び出し方
最適化や並列化などを行う1つのモジュールでは、coins.aflow か coins.flow のどちらか一方しか使えない。
両方のメソッドを混合して使うことはできない。
フロー情報の参照においては、FlowResultsというクラスが中心的な役割を果たす。
FlowResults はHashMapのサブクラスであり、find(), get(), put(),getRaw() というメソッドを持つ。
(詳しい呼び出し方はcoins.aflow.FlowResults参照)
(1) find
find は、引数で指定された情報がFlowResults に記録されているか否か探し、なければ算出し、記録するための準備をする。
ある情報に対するgetやputをするには、その情報に対するfindがを呼ばれていなければならない。
次の例は基本ブロックlBBlockに対するDef情報の準備をする指示である。findでどんな処理を行うかは、
findの各キイに対する処理を行うクラスを与えるputRegClassesというメソッドを1度だけ呼ぶことによって指定する。
ex. find("Def", lBBlock);
(2) get
引数で指定されたキイに対する情報がFlowResultsに記録されていればそれを返す。記録されていなければ自動的に計算する。
ex. get("Def", lBBlock);
(3) put
引数として与えるキイとその値の組をFlowResultsに記録する。キイには複数のオブジェクトで構成されるものもある。
その実装内容はキイの種類によって異なり、記録されていなければ自動的に計算するものに対してはgetで取り出し、
そうでないものに対してはgetRawで取り出す。次の例は基本ブロックlBBlockのDefベクターの値をlDefVectorとして記録するものである。
ex. put("Def", lBBlock, lDefVector);
(4) getRaw
記録されていない情報を自動的に計算することを行わない場合は、getでなくgetRawを使ってキイに対する値の取り出しを行う。
getRawはMapのgetと同じような使い方である。次の例はlBBlockに対するDefベクターを取り出す指示である。
ex. getRaw("Def", lBBlock)
次の例で、基本ブロックごとのReachベクターを利用するときの処理の概要を示す。
// Establishes the map between the analysis names and the analyzer methods
// that actually do the analysis.
// A key of this map together with the arguments of the associated
// analyzer class methods forms a piece of information that supports the
// automatic analysis mechanism.
// This method will be called only twice during the program life; once
// for HIR and once for LIR.
FlowResults.putRegClasses(new RegisterFlowAnalClasses());
// Instantiate a FlowResults map.
FlowResults lResults = flow.results();
// Instantiate a SubpFlow object, with FlowResults object passed as an
// argument to the factory method.
SubpFlow lSubpFlow = flow.subpFlow(subpDef, lResults);
// Performs control flow analysis.
// Control flow analysis does not support the automatic flow analysis
// mechanism and must be called explicitly.
lSubpFlow.controlFlowAnal();
// Collects some basic information that does not require a complex
// algorithm.
// Some pieces of information obtained here ARE part of the automatic
// analysis picture, but some are not, so I call it explicitly.
lSubpFlow.initiateDataFlow();
// Finds the Reach vector for each of the BBlocks that belong to lSubpFlow.
// There is no need to call lSubpFlow.getExitBBlock().findDef() or
// lSubpFlow.getExitBBlock().findKill() (or lSubpFlow.findReach()) since
// they are called automatically (automatic analysis).
lReach = lResults.get("Reach", lSubpFlow.getExitBBlock());
// OR lReach = lSubpFlow.getExitBBlock().getReach();
...
6.5.3.3 コマンドでの起動
フロー解析の処理は、通常、最適化や並列化のモジュールで呼ぶものであるが、教育などの目的に使う場合は、
フロー解析によってどのような情報が算出されるかを見ることができるとよい。
そのような機能があるとフロー解析のデバッグにも役立つ。次のように、コンパイラ・コマンドでhirAnalを指定すると
フロー解析が行われ、trace=Flow.2を指定するとその結果が標準出力に出される。Flow.4などとすると、
フロー解析の途中情報も見ることができる。
java coins.driver.Driver -S -coins:hirAnal,trace=Flow.2
6.6 別名解析
6.6.1 別名解析の概要
別名解析は、ソースプログラムでは相異なる変数であっても同じ記憶領域を表す可能性を調べるものである。
ある変数に値が設定されたとき、それと別名関係にある変数にも値が設定された可能性があるとみなし、
ある変数の値が参照されたとき、それと別名関係にある変数の値が参照された可能性があるとみなして、
最適化変換などを抑制する等の目的で利用される。
別名解析には、楽観的解析(alias=opt)と悲観的解析(alias=pes)がある。alias=optを指定しなければ悲観的解析を行う。
これらの指定は、coinsオプションの1つとして
-coins:alias=opt
のように指定する。
楽観的解析では、
- 相異なる仮引数は互いに別名関係にない。
- 配列要素の添字値は配列宣言で指定された範囲内にある。
仮引数についても、配列要素の添字値は宣言された範囲内にある。
- ポインタ変数は、(ポイント先の型として)宣言された型に適合しない型のデータを指すことはない。
- 相異なる一時変数(コンパイラの生成した変数)は互いに別名関係にない。
- 一時変数とソースプログラム変数(実行文に出現する変数)とは別名関係にない。
- 局所変数と大域変数とは別名関係にない。
- 配列仮引数と大域的スカラー変数は別名関係にない。
- 副プログラム内static変数は、実引数でもなくアドレスもとられていなければ、仮引数と別名関係にない。
と仮定して解析する。
悲観的解析では、
- 相異なる一時変数は互いに別名関係にない。
- 一時変数とソースプログラム変数とは別名関係にない。
- 局所変数と大域変数とは別名関係にない。
- 副プログラム内static変数は、実引数でもなくアドレスもとられていなければ、仮引数と別名関係にない。
と仮定するが、その他の楽観的仮定は成り立たないことがあると想定して解析する。HIRの最適化では、
別名解析の結果を利用して変換を制限する。
うっかりミスはもう含まれていないとか(変数間で意図的にメモリを重ね合わせる
ような)裏技は用いていないというようなプログラムに対しては楽観的解析でも
よいのであるが、コンパイラではそこまで判断できないので、-coinsのオプション
としてalias=optを指定しなければ、悲観的解析を行う。HIRの最適化では、
別名解析の結果を利用して変換を制限する。ポインタを多用するCのプログラム
は、配列を主たるデータ構造とするFortranのプログラムに比べ、別名解析が
むずかしいので最適化が制限される場合が多い。
注釈:
C言語では配列仮引数の第1添字の範囲を限定しないので、添字値が宣言された範囲を
逸脱していないことを言語的に保証できないが、
#pragma optControl safeArray var1 var2 ...
という形のプラグマを与えると、配列変数 var1, var2, ... の添字がそれらの変数に割り
当てられたメモリ領域を逸脱するような値をとることはないと宣言されたとみなす。
このプラグマは、指定する変数 var1, var2, ... と同じスコープで指定しなければ
ならない。仮引数の場合は対応する副プログラムの中で与える。
別名解析においては、プログラムの流れの解析を行い、ポインタ変数のポイント先
を調べるなどして、各々の変数と別名関係になり得る変数の集合を求める。ある
ポインタ変数pのポイント先が判断できない場合は、使われているすべての変数が
pのポイント先と別名関係にあると見なす。また値のわからない式を添字とする
添字つき変数は、その配列のすべての要素と別名関係にあるとみなす。この
流れ解析は時間がかかるので、副プログラムの複雑度が高い場合(ノード数が
1000以上または使われている変数の数が100以上の場合)、流れ解析は行わず、
静的に判定できる範囲で別名解析を行う。
6.6.2 使い方
別名解析はデータフロー解析のときに自動的に計算され、その結果はRecordAliasのメソッドmayAlias, aliasSyms, and aliasSymGroup
などを使うことによって、次のような形で利用できる。
RecordAlias lRecordAlias = flowRoot.subpFlow.getRecordAlias();
....
if(lRecordAlias.mayAlias(x, y)) {
// Assume y may be changed when x is changed.
....
}
Set lSetOfVariablesAliased = lRecordAlias.aliasSyms(x);
ここで、x, y は変数を表す記号である。RecordAliasの関数の意味は次のとおりである。
mayAlias(x, y): x と y が別名関係にあれば true, なければ false を返す。
aliasSyms(x): x と別名関係にある変数の集合を返す。
aliasSymGroup(s): 変数集合 s のいずれかの変数と別名関係にある変数の集合を返す。
6.7 大域的パタン照合による変換
6.7.1 概要
コンパイルオプションとして
-coins:hirOpt=globalReform
を指定すると、大域的パタン照合による変換が起動される。これは、入力パタン
(in-pattern) と出力パタン (out-pattern) の対応を副プログラムの形で与えると、
入力プログラムにおいて入力パタンに適合する式や文、文の列を検出し、それを
対応する出力パタンに変換するものである。
そのような副プログラムを大域的パタン (global pattern) と呼び、
その名前をパタン名と呼ぶことにする。入力パタンと出力パタンは BNF に
近い形で与えるが、その文法規則には引数をつけることができるので、 BNF では
指定できない入出力の対応関係を指定できる。
この方法で多種多様な変換ができるが、それは与えられた入力パタンに適合する部分が入力プログラム中に見つかった場合に行われるものであり、その適用率はあまり高くはない。
まず簡単な例をあげる。
#pragma globalReform patternSym copy
#pragma globalReform target main
void copy( char *pa, char *pb, int pn, int pi )
{
iPattern:
{
for (pi = 0; pi < pn; pi++)
*pb++ = *pa++;
}
oPattern:
{
memcpy(pb, pa, pn);
}
}
int main()
{
char x[100] = {1, 2, 3, 4, 5, 6, 7, 8}, y[100];
int j;
char *px = x;
char *py = y;
for (j = 0; j < 100; j++)
*py++ = *px++;
printf(" %d %d %d \n", y[0], y[1], y[2]);
return 0;
}
この例では、入力パタンは
for (pi = 0; pi < pn; pi++)
*pb++ = *pa++;
であり、main プログラムの文
for (j = 0; j < 100; j++)
*py++ = *px++;
がこれに適合するものとして、このループ文が関数呼出し
memcpy(py, px, 100);
に変換される。大域的パタンの仮引数 pa, pb, pn, pi の各々は、それぞれ実引数
px, py, 100, j に対応づけられ、出力パタンに含まれる仮引数は、対応する
実引数で置き換えられる。
大域的パタン照合では、globalReform という記号で始まるプラグマを使う。
大域的パタンはそれを定義する前に patternSym というキィワードをもつプラグマ
#pragma globalReform patternSym pattern1 pattern2 ...
でその名前の列挙する。大域的パタンを探索する副プログラムは、その名前を
target というキィワードを持つプラグマ
#pragma globalReform target subpprogram1 subpprogram2 ...
で列挙する。これは対象外のものに対する探索を省略するためである。
大域的パタンの一般形は
void patternSymbol( type1 pParam1, type2 pParam2, ... )
{
iPattern:
{
statement1
statement2
....
}
oPattern:
{
statement4
statement5
....
}
}
である。仮引数 pParam1, pParam2, ... の型 type1, type2, ... は、
対応する実引数がそれに適合しない場合はパタンが合わないと見なす
ためにつけてある。const 修飾詞がついた型の仮引数は、その型に適合する定数
のみを実引数とする。
入力パタンは iPattern というラベルのついたブロック、出力パタンは oPattern
というラベルのついたブロックとして表される。それらのブロックの中の文には
大域的パタンの仮引数が含まれていてもよい。また後述のパタン非終端記号
(pattern nonterminal) が含まれていてもよい。入力プログラムのある部分が
いずれかの入力パタンに適合することがわかると、それは対応する出力パタンに
置き換えられるが、その際、出力パタンに含まれる仮引数は対応する実引数に
おきかえられる。入力パタンを入力プログラムと照合するとき、入力パタンにおける
仮引数の出現位置に対応する位置にある式や文がその仮引数に対応する実引数として
対応づけられる。出力パタンを上記のようにして置き換え用のものに変換する
ことを出力パタンを展開するという。
文を仮引数に対応づける場合は、それが文を表す仮引数であることを stmtParam
というキィワードを持つプラグマ
#pragma globalReform stmtParam param1 param2 ...
によって、大域的パタンの定義の先頭部分で次のように示す。
void patternSymbol( type1 pParam1, type2 pParam2, ... )
{
#pragma globalReform stmtParam param1 param2 ...
iPattern:
{
statement1
statement2
....
}
oPattern:
{
statement1
statement2
....
}
}
文を表す仮引数の型は void* としておく。入力パタンが1つの文ではなく、1つの式
であるときは、それを
iPattern
{
p * 10;
}
のように、式文として表す。それに対応する出力パタンは、
oPattern:
{
p * 8 + p * 2;
}
のように、また式文を表すものでなければならない。
大域的パタンを型紙にたとえるならば、仮引数は型紙の穴であり、型紙を入力
プログラムに重ね合わせたときにその穴の部分に対応する式や文がその仮引数
に対応する実引数である。入力パタンにおいて同じ仮引数が数カ所に現れるならば、
それに対応する位置にある実引数は同じでなければならない。同じでない場合は
その型紙(大域的パタン)は適合しないものと見なされる。
入力パタンは式や文だけでなく、文の列であってもよい。その文の列は
より長い文の列のなかに仕切りなしで埋まっていてもよい。
出力パタンの中に仮引数でない局所変数(大域的パタンを表す副プログラムの
中で定義された変数)があると、展開のとき、その変数はコンパイラの生成する
一時変数で置き換えられる。
上記では、変換結果をCのソースプログラムの形で説明したが、大域的パタン照合
による変換は、実際には HIR から HIR への変換として行われる。すなわち、
変換が起動される以前にパタンを記述した副プログラムを含むプログラムの
全体は HIR に変換されており、本方式による
入力パタンの照合と出力パタンへの変換も HIR で行われる。
HIR はソースプログラムの論理構造を表現でき、Cへの逆変換もできるので、
わかりやすくするため、以下でも C 言語の形で変換仕方を説明する。
6.7.2 パタン非終端記号を含まないパタン記述
例1:絶対値の和
使い方を例を挙げながら説明する。いま、対象機種には SIMD(Single-Instruction
Multiple-Data) 命令があって、その1つとして、8ビットの符号付き整数の絶対値
の和を高速に計算する命令があるとし、次のようなプログラムでそれを利用する
ことを考える。
#pragma globalReform patternSym absAdd
#pragma globalReform target main
#define BSIZE 256
void absAdd( signed char pd[], int pi, int pm, int psum )
{
iPattern:
{
psum = 0;
for (pi = 0; pi < pm; pi = pi + 1 ) {
if (pd[pi] >= 0)
psum = psum + pd[pi];
else
psum = psum - pd[pi];
}
}
oPattern:
{
psum = absAddChar(pd, pm);
}
}
int main()
{
signed char buf[BSIZE], v;
int i, j;
int sum;
for (j = 0; j < BSIZE; j++) {
buf[j] = 128 - j;
}
sum = 0;
for (i = 0; i < BSIZE; i = i + 1) {
if (buf[i] >= 0)
sum = sum + buf[i];
else
sum = sum - buf[i];
}
printf("sum= %d\n", sum);
return 0;
}
これでは、その SIMD 命令を利用する関数 absAddChar を用意し、該当する文の列を
見つけると、その文の列を absAddChar の呼び出し文に置き換えることにする。
上の例では、main の中の
sum = 0;
for (i = 0; i < BSIZE; i = i + 1) {
if (buf[i] >= 0)
sum = sum + buf[i];
else
sum = sum - buf[i];
}
という文の列が入力パタンに適合すると判定し、それを SIMD 命令を使う関数の
呼び出し文に変換する。
例2:asm文との組合せによるSIMD命令の生成
SIMD命令は適用できると効果が大きいが、その処理はC言語で記述すると分岐や
反復を含むものであったりするので、式のパタン照合のような方法では適用
できる部分を検出するのはむずかしい。大域的パタン照合では分岐や反復を
含むコーディングパタンも検出できるので、C言語のインラインアセンブリ機能
であるasm文と組み合わせると、SIMD命令を比較的容易に生成できる。
例として、直交する X, Y, Z 座標系における座標変換をとりあげてみる。
いくつもの頂点で表現される3次元物体の回転と拡大・縮小は、3次の
変換行列で表現できる。それに X, Y, Z 座標に対する移動量の項を
加えた4次の行列をつくると、平行移動と回転、拡大・縮小を統一的に
扱うことができる。そこでは、頂点の座標は (x, y, z, 1) のように、
4次のベクターで表現すればよい。
コンピュータグラフィックスでは、画面表示のために、点の座標値等を
整数で表し、その計算値がある限界値をこえると、その限界値に合わせて
超過部分を切り捨てる「飽和演算」の行われることが多い。
いま、変換行列を
short m[4][4];
で表し、点の座標を
short c[4];
で表すと、座標変換は、一時変数 t, i, j を使って
for (i=0; i< 4; i++) {
t[i]=c[3]*m[i][3]+c[2]*m[i][2]
+c[1]*m[i][1]+c[0]*m[i][0];
}
for(j=0; j< 4; j++) c[j]=t[j];
で表現される。
これはインテルの Pentium に備わっている SIMD 命令である MMX 命令を使うと、
次のように書くことができる。
mov eax,c //edi = &c[0]
mov ebx,m //ebx = &m[0][0]
movq mm0,[eax] //mm0: c[3]: c[2]: c[1]: c[O]
// move quad words to mm0 (64bits)
movq mm1,[ebx] //mm1: m[0][3]:m[0][2]:m[0][1]:m[0][0]
movq mm2,[ebx+8] //mm2: m[1][3]:m[1][2]:m[1][1]:m[1][0]
movq mm3,[ebx+16]//mm3: m[2][3]:m[2][2]:m[2][1]:m[2][0]
movq mm4,[ebx+24]//mm4: m[3][3]:m[3][2]:m[3][1]:m[3][O]
pmaddwd mm1,mm0 //mm1: c[3]*m[0][3]+c[2]*m[0][2]: c[1]*m[0][1]+c[0]*m[0][0]
pmaddwd mm2,mm0 //mm2: c[3]*m[1][3]+c[2]*m[1][2]: c[1]*m[1][1]+c[0]*m[1][0]
pmaddwd mm3,mm0 //mm3: c[3]*m[2][3]+c[2]*m[2][2]: c[1]*m[2][1]+c[0]*m[2][0]
pmaddwd mm4,mm0 //mm4: c[3]*m[3][3]+c[2]*m[3][2]: c[1]*m[3][1]+c[0]*m[3][0]
packssdw mm1,mm2 //mm1: c[3]*m[1][3]+c[2]*m[1][2]: c[1]*m[1][1]+c[0]*m[1][0]
// : c[3]*m[0][3]+c[2]*m[0][2]: c[1]*m[0][1]+c[0]*m[0][0]
// 4 packed words in mm1, mm2 to 4 packed words in mm1
// with saturation operation.
movq [temp1],mm1 // short temp1[4];
packssdw mm3,mm4 //mm3: c[3]*m[3][3]+c[2]*m[3][2]: c[1]*m[3][1]+c[0]*m[3][0]
// : c[3]*m[2][3]+c[2]*m[2][2]: c[1]*m[2][1]+c[0]*m[2][0]
movq[temp2],mm3 // short temp2[4];
emms // empty MMX state so that FPU reg can be used for floating op.
)
c[0]=temp1[0]+temp1[1]; // Move the results from temp1 and temp2.
c[1]=temp1[2]+temp1[3];
c[2]=temp2[0]+temp2[1];
c[3]=temp2[2]+temp2[3];
MMX命令を使ったコーディングでは飽和演算がなされているが、上記の
C コーディングでは飽和演算の処理はまだ表現されていない。
大域的パタン照合では、次のように記述すると、上記のような
C コーディングを検出して、それをMMX命令を使った機械命令列に
変換することができる。
#pragma globalReform patternSym linearTrans
#pragma globalReform target main
int printf(char*, ...);
void linearTrans(short pc[4], short pm[4][4], short pt[4], int pi, int pj)
{
short temp1[4], temp2[4];
iPattern:
{
for (pi=0;pi< 4;pi++) {
pt[pi]=pc[3]*pm[pi][3]+pc[2]*pm[pi][2]+pc[1]*pm[pi][1]+pc[0]*pm[pi][0];
}
for(pj=0;pj< 4;pj++) pc[pj]=pt[pj];
}
oPattern:
{
asm (
"#param %I32,%I32,%I32,%I32\n"
"#clobber %mm0,%mm1,%mm2,%mm3,%mm4\n"
"movq (%1),%mm0\n"
"movq (%2),%mm1\n"
"movq 8(%2),%mm2\n"
"movq 16(%2),%mm3\n"
"movq 24(%2),%mm4\n"
"pmaddwd %mm0,%mm1\n"
"pmaddwd %mm0,%mm2\n"
"pmaddwd %mm0,%mm3\n"
"pmaddwd %mm0,%mm4\n"
"packssdw %mm2,%mm1\n"
"movq %mm1,(%3)\n"
"packssdw %mm4,%mm3\n"
"movq %mm3,(%4)\n"
"emms\n",
pc, pm, temp1, temp2
);
pc[0]=temp1[0]+temp1[1];
pc[1]=temp1[2]+temp1[3];
pc[2]=temp2[0]+temp2[1];
pc[3]=temp2[2]+temp2[3];
}
} // linearTrans
int main()
{
int i;
short tt[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 1}, {0, 0, 1, 0}, {0, 0, 0, 1}};
short xyz[4] = {10, 12, 13, 3};
short tmp[4] = {0};
printf("before %d %d %d %d \n", xyz[0], xyz[1], xyz[2], xyz[3]);
for (i=0;i< 4;i++) {
tmp[i]=xyz[3]*tt[i][3]+xyz[2]*tt[i][2]+xyz[1]*tt[i][1]+xyz[0]*tt[i][0];
}
for(i=0;i< 4;i++) xyz[i]=tmp[i];
printf("linTrans %d %d %d %d \n", xyz[0], xyz[1], xyz[2], xyz[3]);
return 0;
}
この例では、関数定義 linearTrans において、iPattern がラベルとして
ついたブロックで C のコーディングパタンを指定し、oPattern が
ラベルとしてついたブロックでそれの変換形を指定している。
COINSの asm 文は、
asm文の仕様
に記述してあるように、
asm("#param descriptor-list\n"
"#clobber destroyed registers...\n"
"instruction 1\n"
...
"instruction n\n",
input arguments(any expression)...);
という形をしており、そこでの記号は
"descriptor-list" asmへ渡す引数の LIR型(I32等)を指定
"destroyed registers" 内容が保存されないレジスタを列記
"instruction" 生成するアセンブリ言語命令
"input arguments" asm へ渡す引数を列記 (pc, pm 等)
(引数は命令の中で %1, %2, ... のように参照).
ということを表している。この例では、
mainプログラムの中の
for (i=0;i< 4;i++) {
tmp[i]=xyz[3]*tt[i][3]+xyz[2]*tt[i][2]+xyz[1]*tt[i][1]+xyz[0]*tt[i][0];
}
for(i=0;i< 4;i++) xyz[i]=tmp[i];
という文の列がこのパタンに適合すると判定されて、それに対するSIMD 命令
(Pentium では MMX 命令)が生成される。
この座標変換を
インテル Pentium 4 (2.8GHz)
で2000万回繰り返したときの実行時間は、オプション指定
hirOpt=globalReform
の有無によって次のように変った。
globalReformあり globalReformなし
real 8.712s 17.389s
user 8.624s 17.331s
sys 0.015s 0.031s
この例では、大域的パタン照合によるSIMD命令の生成が実行速度向上に
大きい効果があった。
例3:再帰関数のループへの変換
次に、再帰関数のループへの変換を例で説明する。大域的パタンを記述した
副プログラムの中で、その名前であるパタン名を入力パタンや出力パタンで使うと、
それは関数を表す仮引数として扱われる。このことを利用すると、次の例のように、
再帰関数をループに変換することもできる。
#pragma globalReform patternSym recmult
#pragma globalReform target fact
int recmult( int px )
{
iPattern:
{
if (px <= 1)
return 1;
else
return px * recmult(px - 1);
}
oPattern:
{
int lx, i;
lx = 1;
for (i = 1; i <= px; i++) {
lx = lx * i;
}
return lx;
}
}
int fact( int p )
{
if (p <= 1)
return 1;
をelse
return p * fact(p - 1);
}
これでは、fact という関数の中の文が入力パタンと適合すると判定され、recmult
という仮引数が fact という関数を実引数とするよう対応づけられる。
これによって、
出力パタンで示されるように、fact の内容を定義する文がループ文を含む文の
列に変換される。
ただし、これは指定されたパタンに適合したコーディングに対する変換であり、
再帰のループへの変換を一般的な形で行うものではない。
6.7.3 パタン非終端記号を含むパタン記述
これまでの例では、パタンの可変部分は仮引数で表されていたが、可変部分の
範囲を広げるとか、可変部分の構造を指定できるようにするというような目的で、
パタン非終端記号 (pattern nonterminal) と呼ぶ記号を導入し、BNF に近い形で
パタンを記述する方法を示す。
例4:累乗の検出
まず、ごく簡単な例を示す(これは説明用の例であって、実用的な意味は
持たない)。
#pragma globalReform patternSym extractPower
#pragma globalReform nonterminal power
#pragma globalReform target main
int _bnfOr(int p, ...);
double power( double p1 );
double transformPower( double p2 );
void extractPower( double pv1 )
{
iPattern:
{
power(pv1) * pv1;
}
oPattern:
{
transformPower(power(pv1) * pv1);
}
}
double power( double pv2)
{
_bnfOr(2,
pv2 * pv2,
power(pv2) * pv2 );
}
double a = 2.0, b = 3.0, c = 4.0;
int main()
{
double x, y, z;
x = a * a * a;
y = b * b * b * b;
z = a * a * b;
printf(" %f %f %f \n", x, y, z);
return 0;
}
int _bnfOr(int p, ...) {
return p;
}
これは、変数の累乗の式を見つけ出し、それを transformPower という関数の
呼び出しに変える。ここで、
#pragma globalReform nonterminal power
はパタン非終端記号を nonterminal というキィワードの後ろに列挙するプラグマ
である。
関数 _bnfOr は BNF の生成規則に相当するものを選ぶことを表すもので、
_bnfOr(number, expression1, expression2, ... )
は、入力プログラムに合わせて expression1, expression2, ... で表される
生成規則右辺のいずれかを選択することを表す。その選択は左から順番に行われ、
最初に適合したものが選択される。適合するものがなければその非終端記号は
与えられた入力に適合しないと判定される。_bnfOr は
int _bnfOr(int, ...);
をプロトタイプ宣言とする関数で、その第1引数はこれを C の文法に合わせるため
につけた無意味なものである。パタン非終端記号は副プログラムの形で
宣言する。パタン非終端記号は引数を持つことができ、それは大域的パタンの
仮引数に対する実引数を伝播してゆくのに使われる。
double power( double pv2) {
_bnfOr(2, pv2*pv2, power(pv2)*pv2);
}
はパタン非終端記号 power を定義しており、それは
pv2 * pv2
か
power(pv2) * pv2
のいずれの生成規則を選ぶかを表す。いま、入力プログラムに
a * a * a
という式があると、最初の生成規則 v2*pv2 は a*a*a に適合しないので、
2番目の生成規則
power(pv2) * pv2
が選ばれる。その照合過程では、第2項の pv2 を一時的に a と設定し、
power(pv2) と a*a を照合する。それは適合するので、a*a*a は入力パタンに
適合すると判定する。入力として
b * b * b * b
があると、まず pv2 に b を対応させて *b をはぎ取り、power(pv2) と b*b*b が
適合するか否かを調べる。この照合は成功するので、b*b*b*b は 入力パタンに
適合すると判定する。次に、式
a * a * b
に対しては、まず pv2 に b を対応させ、末尾の *b をはぎ取った a*a と
power(pv) の照合を試みるが、pv2 に b が対応しているのでこれは不整合となり、
上記の式の全体は 乳リュ億パタンに適合しないと判定される。
BNF で
power ::= power * var | var
のように書くと、乗算のオペランドが同じ変数であることを表現できず、
1.0*a*a と 1.0*a*b を区別する規則を一般的な形で書くことはできないが、大域的
パタン照合では、パタン記号やパタン非終端記号に引数を付けることによって、
このような区別を可能にしている。
例5:ループ展開
次の例は、ループ展開を行うものである。
#pragma globalReform patternSym loopUnroll
#pragma globalReform nonterminal subsVar expS termS factS iExp
#pragma globalReform target main
#define BSIZE 999
int expS( int pzz[], int pi);
int termS( int pzz[], int pi);
int factS( int pzz[], int pi);
int subsVar( int pzz[], int pi);
int iExp( int px);
int printf(char*, ...);
void loopUnroll( int pzz[], int pi, int pFrom, int pTo)
{
iPattern:
{
for (pi = pFrom; pi < pTo; pi++) {
pzz[iExp(pi)] = expS(pzz, pi);
}
}
oPattern:
{
for (pi = pFrom; pi < pTo-1; pi=pi+2) {
pzz[iExp(pi)] = expS(pzz, pi);
pzz[iExp(pi+1)] = expS(pzz, pi+1);
}
if ((pTo-pFrom) % 2 != 0)
pzz[pTo-1] = expS(pzz, pTo-1);
}
}
int subsVar( int pzz1[], int pi1)
{
pzz1[iExp(pi1)];
}
int expS( int pzz2[], int pi2)
{
#pragma globalReform transparentFitting pc (pzz2, pi2)
int pc;
_bnfOr(1, expS(pzz2,iExp(pi2))+termS(pzz2,iExp(pi2)),
expS(pzz2,iExp(pi2))-termS(pzz2,iExp(pi2)),
expS(pzz2,iExp(pi2))+pc,
expS(pzz2,iExp(pi2))-pc,
expS(pzz2,iExp(pi2)) );
}
int termS( int pzz3[], int pi3 )
{
#pragma globalReform transparentFitting pc2 (pzz3, pi3)
int pc2;
_bnfOr(1, termS(pzz3,iExp(pi3))*factS(pzz3,iExp(pi3)),
termS(pzz3,iExp(pi3))/factS(pzz3,iExp(pi3)),
termS(pzz3,iExp(pi3))*pc2,
termS(pzz3,iExp(pi3))/pc2,
factS(pzz3,iExp(pi3)) );
}
int factS( int pzz4[], int pi4 )
{
#pragma globalReform transparentFitting pc3 (pzz4, pi4)
int pc3;
_bnfOr(2, pc3*subsVar(pzz4,iExp(pi4)),
pc3/subsVar(pzz4,iExp(pi4)),
subsVar(pzz4,iExp(pi4)));
}
int iExp( int px )
{
#pragma globalReform transparentFitting pc4 (px)
int pc4;
_bnfOr(3, px+pc4, px-pc4, px);
}
int main() {
int zz[BSIZE]; int i, n;
n = BSIZE;
for (i = 0; i < n; i++) {
zz[i] = i;
}
for (i = 0; i < n; i++) {
zz[i] = zz[i]*2;
}
printf(" %d %d %d %d %d\n", n, zz[0], zz[1], zz[n-2], zz[n-1]);
return 0;
}
上記の loopUnroll という大域的パタンは、例えば
for (i = 0; i < n; i++) {
zz[i] = zz[i]*2;
}
というループを
for (i = 0; i < n-1; i=i+2) {
zz[i] = zz[i]*2;
zz[i+1] = zz[i+1]*2;
}
if ((n-0) % 2 != 0)
zz[n-1] = zz[n-1]*2;
に変える。
パタン非終端記号
int iExp( int px ) {
#pragma globalReform transparentFitting pc4 (px)
int pc4;
_bnfOr(3, px + pc4, px - pc4, px );
}
は、px+pc4, px-pc4, px のいずれかの形をした式に適合するものであり、ここで
pc4 は px を含まない式を表す。仮引数 px は上位構文から引き継がれた式である。
ここでいう上位構文とは、このパタン非終端記号を参照しているパタン非終端記号、
または大域的パタンと照合中の入力プログラムのことを指す。
プラグマ
#pragma globalReform transparentFitting p (q, r, ..., s)
は、式 p は変数 q, r, ..., s のいずれも含まない(影響し合わない)ものとする
ことを宣言する。
パタン非終端記号
int subsVar( int pzz1[], int pi1) {
pzz1[iExp(pi1)];
}
は、iExpで示された制約を満たす式を添字とする添字つき変数を表す。仮引数
pzz1, pi1 は上記構文から引き継がれる。
上記の例にはその他にパタン非終端記号 expS, termS, factS を定義している。
これらは次の BNF 生成規則と類似性がある。
expS ::= expS "+" termS
| expS "-" termS
| expS "+" pc
| expS "-" pc
| termS
termS ::= termS "*" factS
| termS "/" factS
| termS "*" pc2
| termS "/" pc2
| factS
factS ::= pc3 "*" subsVar
| pc3 "/" subsVar
| subsVar
パタン非終端記号 factS
The pattern nonterminal
int factS( int pzz4[], int pi4 ) {
#pragma globalReform transparentFitting pc3 (pzz4, pi4)
int pc3;
_bnfOr(2,
pc3 * subsVar(pzz4, i(pi4)),
pc3 / subsVar(pzz4, iExp(pi4)),
subsVar(pzz4, iExp(pi4)) );
}
は、上記の subsVar か、あるいは pzz4, pi4 を含まない式と subsVar の乗除算式
と適合する。
パタン非終端記号 termS
int termS( int pzz3[], int pi3 ) {
#pragma globalReform transparentFitting pc2 (pzz3, pi3)
int pc2;
_bnfOr(1,
termS(pzz3, iExp(pi3)) * factS(pzz3, iExp(pi3)),
termS(pzz3, iExp(pi3)) / factS(pzz3, iExp(pi3)),
termS(pzz3, iExp(pi3)) * pc2,
termS(pzz3, iExp(pi3)) / pc2,
factS(pzz3, iExp(pi3)) );
}
は、factS で示される式、または pzz3, pi3 を含まない式か factS を termS に
乗除算した式と適合する。
パタン非終端記号 expS
int expS( int pzz2[], int pi2) {
#pragma globalReform transparentFitting pc (pzz2, pi2)
int pc;
_bnfOr(1,
expS(pzz2, iExp(pi2)) + termS(pzz2, iExp(pi2)),
expS(pzz2, iExp(pi2)) - termS(pzz2, iExp(pi2)),
expS(pzz2, iExp(pi2)) + pc,
expS(pzz2, iExp(pi2)) - pc,
termS(pzz2, iExp(pi2)) );
}
は、termS で示される式、または pzz2, pi2 を含まない式か termS を expS に
加減算した式と適合する。
main プログラムとの照合においては、ループ内の式
zz[i] = zz[i] * 2;
と入力パタン内の式
pzz[iExp(pi)] = expS(pzz, pi);
との照合が行われる。そのとき、まずパタン非終端記号 iExp(pi) は pi を
i と対応づけることによって i と適合し、pzz を zz と対応づけることによって
zz[i] が pzz[iExp(pi)] と適合すると見なされる。右辺の zz[i]*2 は加減演算子を
持たないので expS の生成規則として termS(pzz2,iExp(pi2)) が選ばれる。
termS と zz[i]*2 との照合では、pc2 を 2 と対応づけて、factS[pzz3,iExp(pi3))
と zz[i] の照合、factS では subsVar(pzz4,iExp(pi4)) と zz[i] の照合がなされ、
それらの照合が成功することによって、結局
for (i = 0; i < n; i++) {
zz[i] = zz[i]*2;
}
は入力パタンに適合すると判定される。その結果、上記のループは
for (i = 0; i < n-1; i=i+2) {
zz[i] = zz[i]*2;
zz[i+1] = zz[i+1]*2;
}
に相当するループに変換される。
COINSでは、hirOpt=loopexp というオプションを指定するとループ展開が
行われるが、上記の例はそのループ展開の機能に置き換わるものではない。
hirOpt=loopexp では約2000行のモジュールで一般的なループ展開を行うが、
例5は入力パタンで指定した典型的なコーディングパタンに限定した
ループ展開を100行たらずの記述で行う別の実現方式を示したものである。
6.7.4. 大域的パタン照合の使い方
前節のでは、添字つき変数を含む式というようなパタンを定義し、それを
入力パタンや出力パタンで利用することによって、ループ展開をかなり自由度の
高い形で指定できることを示した。そのほか、各種実行文の
代表的な形式を表すパタン非終端記号を定義しておくならば、それらを参照する
大域的パタンを定義することにより、ループ交換やリダクションなど、
多様な変換を実現できる。
従来、ループ展開や末尾再帰のループ化などは、特定目的ごとに作った
最適化モジュールで行われていた。本方式では、目的に応じて大域的パタンを
定義することにより、それらの変換における代表的な場合を変換できる。
それは網羅的な変換ではなく、代表的なパタンに対する変換なので、
特定目的ごとに作る最適化モジュールを完全に置き換えるものではない。
しかし、大域的パタン照合による変換モジュール1つだけで各種の
代表的なパタンを変換できるので、特定目的用のモジュールをまだ作っていない
最適化項目に対して、広い範囲をカバーするための簡便な
実装方法として利用することができよう。
最適化方式やコンピュータのアーキテクチャの検討段階では、
いくつかの評価用のプログラムに対して、検討中の方式がどれぐらい
効果があるかを実験的に評価することも行われるであろう。そのような
場合に、大域的パタン照合の方法は、評価用プログラムに対する命令生成を
簡易な方法で行う目的にも使うことができるであろう。
このプログラム変換方式は、最適化や並列化の適用を行いやすくする予備的変換
などにも有用である。また、これはコードの最適化に限定されるものではなく、
ソフトウェア工学的な変換や、ある特定のパタンを検出する目的などにも
利用できる。
6.8 参考ドキュメント
-
[1] Morel, Etienne and Renvoise, Claude: Global optimization by suppression
of partial redundancies, CACM, Vol. 22, No. 2, pp.96-103 (Feb. 1979).
-
[2] Muchnick, Steven S.: Advanced Compiler Design and Implementation,
Morgan Kaufmann Publishers (1997).
-
[3] 中田育男: コンパイラの構成と最適化, 朝倉書店
(Nakata, Ikuo: Compiler Construction and Optimization, Asakura Shoten), (1999).
-
[4] Dhamdhere, Dhananjay M.: E-path_PRE - Partial redundancy elimination made
easy, ACM SIGPLAN Notices, Vol. 37, No. 8, pp. 53-65 (Aug. 2002).