(Read this file in Shift JIS) 　　　　　　　　情報処理学会-道しるべ-COINS連載のSSA部（2006年8月号，9月号） 　　　　　　　　の実行の仕方 　　　　　　　　C言語を使う場合 Copyright 2006-2007 by 佐々政孝 ------------------------------------------------------------------------ １　準備 COINSをインストールする その直下の classes/ と同じレベルに ディレクトリ sassa-ssa-rensai/ をコピーする． すると，COINSのトップでのファイルの状況は次のような感じになる． > ls COPYING build.xml doc-ja/ lang/ suffixes META-INF/ c0front/ examples/ rebuild.bat test/ README.txt classes/ guidance.txt sassa-ssa-rensai/ unbuild.bat build.bat doc/ historyOfRelease.txt sassa-ssa-rensai.tar unbuild.sh build.sh doc-en/ javadoc-ja/ src/ > cd sassa-ssa-rensai > ls README-sassa-ssa-c0-sparc0 Readme-coins-rensai-ssa.txt a.out* addvectosr-addvect-1.lir2c addvectosr-addvect-2.lir2c addvectosr-addvect-3.lir2c addvectosr-addvect-4.lir2c addvectosr-addvect-5.lir2c addvectosr-main-1.lir2c addvectosr-main-2.lir2c addvectosr-main-3.lir2c addvectosr-main-4.lir2c addvectosr-main-5.lir2c addvectosr.c addvectosr.s aliases aliasesc0* appel-main-1.lir2c appel-main-2.lir2c appel-main-3.lir2c appel-main-4.lir2c appel.c appel.s csetest-main-1.lir2c csetest-main-2.lir2c csetest-main-3.lir2c csetest-main-4.lir2c csetest.c csetest.s print.c read.c ssatransback-main-1.lir2c ssatransback-main-2.lir2c ssatransback-main-3.lir2c ssatransback.c ssatransback.s ------------------------------------------------------------------- ２　SSA変換と逆変換の例 ソース > cat ssatransback.c void println(int v); int read(); int main () { int a, b; a = read(); if (a >= 0) { b = a; } else { b = -a; } println(b); } > source aliases ccprunsrd3nocfは alias ccprunsrd3nocf 'java -cp ../classes coins.driver.Driver -coins:assembler= as,ssa-no-copy-folding,ssa-opt=lir2c/prun/lir2c/srd3/lir2c,trace=SSA.1 -S' （１行で） などのようにと定義されている． これらを直接打ってもよい． ccprunsrd3nocfをすると，aliasの定義から， ssa-opt=lir2c/prun/lir2c/srd3/lir2c は，次を順に行う． lir2c:まずSSA変換前のLIRをC言語風に出力し， ssatransback-main-1.lir2を作る prun: pruned SSA形式に変換する． lir2c:SSA変換後のLIRをのLIRをC言語風に出力し， ssatransback-main-2.lir2を作る． srd3: Sreedharの方法3により，SSA逆変換を行う． lir2c:その結果のLIRをC言語風に出力する． ssatransback-main-3.lir2を作る． (言語C0の場合はaliasの代わりにaliasc0を使えば良いように してあるが，動作は未確認である） > ccprunsrd3nocf ssatransback.c Optimization on SSA form 次は最初の，SSA変換前の通常形式LIRをC言語風に出力したもの． > cat ssatransback-main-1.lir2c void main(void) { int a_1_; int b_2_; int returnvalue_3_; _L1: a_1_ = read(); if ((a_1_ >= 0)) { goto _L3;} else { goto _L4;} _L3: b_2_ = ((int)(a_1_)); goto _L5; _L4: b_2_ = ((int)((-(a_1_)))); goto _L5; _L5: println(b_2_); goto _L6; _L6: return; } 次は２つ目の，SSA変換後のLIRをC言語風に出力したもの > cat ssatransback-main-2.lir2c void main(void) { int a_1_; int b_2_; int returnvalue_3_; int a_1__0; int a_1__1; int b_2__0; int b_2__1; int b_2__2; int b_2__3; _L1: a_1__1 = read(); a_1__0 = ((int)( 0)); b_2__0 = ((int)( 0)); if ((a_1__1 >= 0)) { goto _L3;} else { goto _L4;} _L3: b_2__2 = ((int)(a_1__1)); goto _L5; _L4: b_2__1 = ((int)((-(a_1__1)))); goto _L5; _L5: b_2__3 = phi(b_2__2:_L3, b_2__1:_L4); println(b_2__3); goto _L6; _L6: return; } 次は上をSSA逆変換した通常形式LIRをC言語風に出力したもの > cat ssatransback-main-3.lir2c void main(void) { int a_1_; int b_2_; int returnvalue_3_; int a_1__0; int a_1__1; int b_2__0; int b_2__1; int b_2__2; int b_2__3; _L1: a_1__1 = read(); a_1__0 = ((int)( 0)); b_2__0 = ((int)( 0)); if ((a_1__1 >= 0)) { goto _L3;} else { goto _L4;} _L3: b_2__2 = ((int)(a_1__1)); goto _L5; _L4: b_2__2 = ((int)((-(a_1__1)))); goto _L5; _L5: println(b_2__2); goto _L6; _L6: return; } これ以外にも， ssatransback.s というSPARC言語のアセンブリプログラムができている． 確認のため，実行したい場合には， print.c というファイルと read.c というファイルがおいてある． > cat print.c #include void print(int pi) { printf("%d ", pi); } void printInt(int pi) { printf("%d ", pi); } void printStr(char* ps) { printf("%s", ps); } void printEol() { printf("\n"); } void println(int pi) { printf("%d\n", pi); } > cat read.c #include int read() { int i; scanf("%d", &i); return i; } SPARCマシンの上であれば， print.c, read.cとさきほど作った ssatransback.s（SPARC0のアセンブリ形式） を一緒にコンパイルすれば動かすことができる． > gcc ssatransback.s print.c read.c > ./a.out -5 5 > ./a.out 123 123 ssatransback.cは入力の絶対値を返すプログラムであるので， これで実行が確認できた． ---------------------------------------------------------------- 　　　　　　　　　SSA形式最適化の例 ３　共通部分式除去の例 ソースの例 > cat csetest.c void println(int v); int main () { int a; int b; int c; int d; int x; int y; int z; a = 1; b = 2; x = 3; y = a + b; c = x + y; if (a < 10) z = a + b; else z = a + b; d = x + z; println(d); } まず，aliasを読み込む > source aliases この中身は，たとえば alias cccse 'java -cp ../classes coins.driver.Driver -coins:assembler=as,ssa-opt=lir2c/prun/lir2c/cse/lir2c/srd3/lir2c, trace=SSA.1 -S' （実は１行） という定義になっているので， > cccse csetest.c と打つと， Optimization on SSA form が出力される． これは確認のため，オプションの trace=SSA.1 により，SSA最適化が行われたというメッセージが出されたものである． > cccse csetest.c を打つと，aliasの定義から， ssa-opt=lir2c/prun/lir2c/cse/lir2c/srd3/lir2c により，次を順に行う． lir2c:まずSSA変換前のLIRをC言語風に出力し， csetest-main-1.lir2cを作る prun: pruned SSA形式に変換する． lir2c:SSA変換後のLIRをのLIRをC言語風に出力し， csetest-main-2.lir2cを作る． cse: 共通部分式除去を行う． lir2c:その結果のLIRをC言語風に出力する． csetest-main-3.lir2cを作る． srd3: Sreedharの方法３により，SSA逆変換を行う． lir2c:その結果のLIRをC言語風に出力する． csetest-main-4.lir2cを作る． ちなみに，-Sオプションもつけてあるので， csetest.c というアセンブリプログラムも生成される． > cccse csetest.c Optimization on SSA form SSA変換後のLIRをC言語風に出力したのもは次である． > cat csetest-main-2.lir2c void main(void) { int a_1_; int b_2_; int c_3_; int d_4_; int x_5_; int y_6_; int z_7_; int returnvalue_8_; int a_1__0; int a_1__1; int b_2__0; int b_2__1; int x_5__0; int x_5__1; int y_6__0; int y_6__1; int c_3__0; int c_3__1; int z_7__0; int z_7__1; int z_7__2; int z_7__3; int d_4__0; int d_4__1; _L1: a_1__1 = ((int)( 1)); b_2__1 = ((int)( 2)); x_5__1 = ((int)( 3)); y_6__1 = ((int)(((int)(a_1__1 + b_2__1)))); c_3__1 = ((int)(((int)(x_5__1 + y_6__1)))); a_1__0 = ((int)( 0)); b_2__0 = ((int)( 0)); x_5__0 = ((int)( 0)); y_6__0 = ((int)( 0)); c_3__0 = ((int)( 0)); z_7__0 = ((int)( 0)); d_4__0 = ((int)( 0)); if ((a_1__1 < 10)) { goto _L3;} else { goto _L4;} _L3: z_7__2 = ((int)(((int)(a_1__1 + b_2__1)))); goto _L5; _L4: z_7__1 = ((int)(((int)(a_1__1 + b_2__1)))); goto _L5; _L5: z_7__3 = phi(z_7__2:_L3, z_7__1:_L4); d_4__1 = ((int)(((int)(x_5__1 + z_7__3)))); println(d_4__1); goto _L6; _L6: return; } 上に共通部分式除去を施すと次のようになる． > cat csetest-main-3.lir2c void main(void) { int a_1_; int b_2_; int c_3_; int d_4_; int x_5_; int y_6_; int z_7_; int returnvalue_8_; int a_1__0; int a_1__1; int b_2__0; int b_2__1; int x_5__0; int x_5__1; int y_6__0; int y_6__1; int c_3__0; int c_3__1; int z_7__0; int z_7__1; int z_7__2; int z_7__3; int d_4__0; int d_4__1; _L1: a_1__1 = ((int)( 1)); b_2__1 = ((int)( 2)); x_5__1 = ((int)( 3)); y_6__1 = ((int)(((int)(a_1__1 + b_2__1)))); c_3__1 = ((int)(((int)(x_5__1 + y_6__1)))); a_1__0 = ((int)( 0)); b_2__0 = ((int)( 0)); x_5__0 = ((int)( 0)); y_6__0 = ((int)( 0)); c_3__0 = ((int)( 0)); z_7__0 = ((int)( 0)); d_4__0 = ((int)( 0)); if ((a_1__1 < 10)) { goto _L3;} else { goto _L4;} _L3: goto _L5; _L4: goto _L5; _L5: println(c_3__1); goto _L6; _L6: return; } SSA形式で上記の共通部分式除去を行うとともに， SSA形式上の標準的な最適化をすべてかけた結果は次のようになる． これは次のコマンドによって行える． > cccseallopt csetest.c Optimization on SSA form 注意． これをすると， csetest-main-1.lir2c csetest-main-2.lir2c csetest-main-3.lir2c csetest-main-4.lir2c がすべて上書きされる． SSA形式上の標準的な最適化をすべてかけた結果は次である． > cat csetest-main-4.lir2c void main(void) { int a_1_; int b_2_; int c_3_; int d_4_; int x_5_; int y_6_; int z_7_; int returnvalue_8_; //// unknown type (not I,F,A) _preqp_I0; //// unknown type (not I,F,A) _preqp_I0_0; int a_1__0; int a_1__1; int b_2__0; int b_2__1; int x_5__0; int x_5__1; int y_6__0; int y_6__1; int c_3__0; int c_3__1; int z_7__0; int z_7__1; int z_7__2; int z_7__3; int d_4__0; int d_4__1; _L1: println( 6); goto _L6; _L6: return; } ここで， //// unknown type (not I,F,A) _preqp_I0; //// unknown type (not I,F,A) _preqp_I0_0; は，パスpreqpでの宣言情報がまだ不完全であることからくるが， 結果への影響はない． 前述のとおり，-Sオプションもつけてあったので， csetest.c というアセンブリプログラムも生成されている． SPARCマシンの上であれば， print.cとさきほど作った csetest.s（SPARCのアセンブリ形式） を一緒にコンパイルすれば動かすことができる． > gcc csetest.s print.c > ./a.out 6 ---------------------------------------------------------------- ４　条件分岐を考慮した定数伝播 > cat appel.c /* appel_19_4.c */ /* Appel, A.: Modern compiler implementation in Java, 2nd ed., 2002 Fig. 19.4 */ void println(int v); int main () { int i; int j; int k; i = 1; j = 1; k = 0; while (k < 100) { if (j < 20) { j = i; k = k + 1; } else { j = k; k = k + 2; } } println(j); } > source aliases cccstpnochangeloopは次のように定義されている． alias cccstpnochangeloop 'java -cp ../classes coins.driver.Driver -coins:assembler=as,ssa-no-change-loop, ssa-opt=lir2c/prun/lir2c/cstp/lir2c/srd3/lir2c,trace=SSA.1 -S' （実際は１行） そこで， cccstpnochangeloop と打つと，aliasの定義から， ssa-opt=lir2c/prun/lir2c/cstp/lir2c/srd3/lir2c により，次を順に行う． lir2c:まずSSA変換前のLIRをC言語風に出力し， appel-main-1.lir2を作る prun: pruned SSA形式に変換する． lir2c:SSA変換後のLIRをのLIRをC言語風に出力し， appel-main-2.lir2を作る． cstp: 条件分岐を考慮した定数伝播を行う． lir2c:その結果のLIRをC言語風に出力する． appel-main-3.lir2を作る． srd3: Sreedharの方法３により，SSA逆変換を行う． lir2c:その結果のLIRをC言語風に出力する． appel-main-4.lir2を作る． ちなみに，-Sオプションもつけてあるので， appel.c というアセンブリプログラムも生成される． > cccstpnochangeloop appel.c Optimization on SSA form 条件分岐を考慮した定数伝播を行った結果は次である． > cat appel-main-3.lir2c void main(void) { int i_1_; int j_2_; int k_3_; int returnvalue_4_; int i_1__0; int i_1__1; int j_2__0; int j_2__1; int k_3__0; int k_3__1; int k_3__2; int j_2__2; int k_3__3; int k_3__4; _L1: goto _L3; _L3: k_3__2 = phi( 0:_L1, k_3__4:_L5); if ((k_3__2 < 100)) { goto _L4;} else { goto _L8;} _L4: goto _L5; _L5: k_3__4 = ((int)(((int)(k_3__2 + 1)))); goto _L3; _L8: println( 1); goto _L9; _L9: return; } これを通常形式に戻したもののC言語風プログラムは次である． > cat appel-main-4.lir2c void main(void) { int i_1_; int j_2_; int k_3_; int returnvalue_4_; int i_1__0; int i_1__1; int j_2__0; int j_2__1; int k_3__0; int k_3__1; int k_3__2; int j_2__2; int k_3__3; int k_3__4; int _ssaI32; int _ssaI32_0; _L1: _ssaI32_0 = ((int)( 0)); goto _L3; _L3: if ((_ssaI32_0 < 100)) { goto _L4;} else { goto _L8;} _L4: goto _L5; _L5: _ssaI32_0 = ((int)(((int)(_ssaI32_0 + 1)))); goto _L3; _L8: println( 1); goto _L9; _L9: return; } SPARCマシンの上であれば， print.cとさきほど作った appel.s（SPARCのアセンブリ形式） を一緒にコンパイルすれば動かすことができる． > gcc appel.s print.c > ./a.out 1 上のappel-main-4.lirはラベルやgotoが多いが，これは，ふつうのC言語プログラムで書くと，次に相当する． appel-main-4.lir2cをC言語プログラムの見やすい形式で書いたもの： void main(void) { int k; k = 0; while (k < 100)) { k = k + 1; } println( 1); return; } -------------------------------------------------------------------- ５　operator strength reductionの例 これは前述の最適化と同様であるので，説明は簡単に行う． ソースプログラム addvectosr.c > cat addvectosr.c void print(int v); void printEol(); void addvect(int z[], int x[], int y[], int n) { int i; i = 0; while (i < n) { z[i] = x[i] + y[i]; i = i + 1; } } int main() { int x[20], y[20], z[20]; int i; i = 0; while (i < 20) { x[i] = i; y[i] = i; i = i + 1; } addvect(z,x,y,20); i = 0; while (i < 20) { print(z[i]); i = i + 1; } printEol(); return 0; } > source aliases > ccosr addvecosr.c Optimization on SSA form Optimization on SSA form この代わりにaliasesで定義したコマンドを直接打ってもよい． すると．次のファイルができる． addvectosr-addvect-1.lir2c addvectosr-addvect-2.lir2c addvectosr-addvect-3.lir2c addvectosr-addvect-4.lir2c addvectosr-main-1.lir2c addvectosr-main-2.lir2c addvectosr-main-3.lir2c addvectosr-main-4.lir2c addvectosr.s 次は，SSA形式でoperator strength reductionを行った結果である． > cat addvectosr-addvect-3.lir2c void addvect(int z_1__1, int x_2__1, int y_3__1, int n_4__1) { int z_1_; int x_2_; int y_3_; int n_4_; int i_5_; int z_1__0; int x_2__0; int y_3__0; int n_4__0; int i_5__0; int i_5__1; int i_5__2; int i_5__3; int _ssagI32; int _ssagI32_0; int _ssagI32_1; int _ssagI32_2; int _ssagI32_3; int _ssagI32_4; int _ssagI32_5; int _ssagI32_6; int _ssagI32_7; int _ssagI32_8; int _ssagI32_9; int _ssagI32_10; int _ssagI32_11; int _osrI32; int _osrI32_0; int _osrI32_1; int _osrI32_2; int _osrI32_3; int _osrI32_4; int _osrI32_5; int _osrI32_6; int _osrI32_7; int _osrI32_8; int _osrI32_9; int _osrI32_10; int _osrI32_11; int _osrI32_12; _L1: _osrI32_11 = ((int)(((int)(n_4__1 * 4)))); _osrI32_12 = ((int)(((int)(_osrI32_11 + z_1__1)))); i_5__1 = ((int)( 0)); z_1__0 = ((int)( 0)); x_2__0 = ((int)( 0)); y_3__0 = ((int)( 0)); n_4__0 = ((int)( 0)); i_5__0 = ((int)( 0)); _osrI32_4 = ((int)(((int)( 0 + x_2__1)))); _osrI32_7 = ((int)(((int)( 0 + y_3__1)))); _osrI32_10 = ((int)(((int)( 0 + z_1__1)))); goto _L3; _L3: if ((i_5__1 < n_4__1)) { goto _L16;} else { goto _L5;} _L16: goto _L17; _L17: _ssagI32_1 = phi(_osrI32_3:_L15, _osrI32_4:_L16); _ssagI32_4 = phi(_osrI32_6:_L15, _osrI32_7:_L16); _ssagI32_8 = phi(_osrI32_9:_L15, _osrI32_10:_L16); _ssagI32_7 = phi(_osrI32_1:_L15, 0:_L16); i_5__2 = phi(i_5__3:_L15, i_5__1:_L16); goto _L4; _L4: _ssagI32_2 = ((int)(((int)(*((int *)_ssagI32_1))))); _ssagI32_5 = ((int)(((int)(*((int *)_ssagI32_4))))); _ssagI32_6 = ((int)(((int)(_ssagI32_2 + _ssagI32_5)))); ((int)(*((int *)_ssagI32_8))) = ((int)(_ssagI32_6)); i_5__3 = ((int)(((int)(i_5__2 + 1)))); _osrI32_1 = ((int)(((int)(_ssagI32_7 + 4)))); _osrI32_9 = ((int)(((int)(_ssagI32_8 + 4)))); _osrI32_6 = ((int)(((int)(_ssagI32_4 + 4)))); _osrI32_3 = ((int)(((int)(_ssagI32_1 + 4)))); goto _L15; _L15: if ((_osrI32_9 < _osrI32_12)) { goto _L17;} else { goto _L5;} _L5: return; } これはかなり読みにくいが，ループ中の演算の強さの軽減が行われている． さて，ふつうはoperator strength reductionに加えて，さらに他の最適化を 行うものである． その結果は次のようにして得られる． > ccosrallopt addvector.c これをすると， addvectosr-addvect-1.lir2c addvectosr-addvect-2.lir2c addvectosr-addvect-3.lir2c addvectosr-addvect-4.lir2c addvectosr-addvect-5.lir2c addvectosr-main-1.lir2c addvectosr-main-2.lir2c addvectosr-main-3.lir2c addvectosr-main-4.lir2c addvectosr-main-5.lir2c addvectosr.s が書き換えられるので注意する． （実は addvectosr-addvect-1.lir2c addvectosr-addvect-2.lir2c は同じものが作られる） すべての最適化を終えた結果を通常形式に戻したものは次である． > cat addvectosr-addvect-5.lir2c void addvect(int z_1__1, int x_2__1, int y_3__1, int n_4__1) { int z_1_; int x_2_; int y_3_; int n_4_; int i_5_; //// unknown type (not I,F,A) _preqp_I0; //// unknown type (not I,F,A) _preqp_I0_0; int z_1__0; int x_2__0; int y_3__0; int n_4__0; int i_5__0; int i_5__1; int i_5__2; int i_5__3; int _divexI32; int _divexI32_0; int _divexI32_1; int _divexI32_2; int _divexI32_3; int _divexI32_4; int _divexI32_5; int _divexI32_6; int _divexI32_7; int _divexI32_8; int _ssagI32; int _ssagI32_0; int _ssagI32_1; int _ssagI32_2; int _ssagI32_3; int _ssagI32_4; int _ssagI32_5; int _ssagI32_6; int _ssagI32_7; int _ssagI32_8; int _ssagI32_9; int _osrI32; int _osrI32_0; int _osrI32_1; int _osrI32_2; int _osrI32_3; int _osrI32_4; int _osrI32_5; int _osrI32_6; int _osrI32_7; int _osrI32_8; int _osrI32_9; int _osrI32_10; int _osrI32_11; int _osrI32_12; int _divexI32_9; int _divexI32_10; int _preqpI32; int _preqpI32_0; int _preqpI32_1; int _preqpI32_2; int _preqpI32_3; int _preqpI32_4; int _preqpI32_5; int _preqpI32_6; int _preqpI32_7; int _preqpI32_8; int _preqpI32_9; int _preqpI32_10; int _preqpI32_11; int _preqpI32_12; int _preqpI32_13; int _preqpI32_14; _L1: _osrI32_12 = ((int)(((int)(((int)(n_4__1 << 2)) + z_1__1)))); if (( 0 < n_4__1)) { goto _L16;} else { goto _L18;} _L16: goto _L17; _L19: goto _L17; _L17: ((int)(*((int *)z_1__1))) = ((int)(((int)(((int)(*((int *)x_2__1))) + ((int)(*((int *)y_3__1))))))); z_1__1 = ((int)(((int)(z_1__1 + 4)))); y_3__1 = ((int)(((int)(y_3__1 + 4)))); x_2__1 = ((int)(((int)(x_2__1 + 4)))); if ((z_1__1 < _osrI32_12)) { goto _L19;} else { goto _L20;} _L18: goto _L5; _L20: goto _L5; _L5: return; } 最内ループは_L17から始まる5行であって，最適化が行われていることがわかる． 実行例 COINSにより，addvectosr.sにアセンブリの目的プログラムができているので， 次のようにすれば実行できる． > gcc addvectosr.s print.c ;./a.out 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 これは，gccでaddvectosr.cとprint.cをコンパイルして実行した以下のものと 同じ結果を与える． > gcc addvectosr.c print.c ;./a.out 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 （以上） --------------------------------------------------------------------