Continuation based Cの GCC 4.6 上の実装について
大城 信康
目的と背景(1)
当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。
コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。
Many Core での並列実行を高い性能と高い信頼性で実現することができると考える。
目的と背景(2)
CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.4 をベースとしたコンパイラが開発された。
GCC をベースとした CbC コンパイラは、修正・追加された最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。
本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。
発表内容
- CbC の紹介
- GCC でのコンパイルの流れ
- CbC の実装
- Micro-C との性能比較
- mercurial を用いたアップデートの方法
- まとめ
Continuation based C
コードセグメント単位での記述と継続を基本としたプログラミング言語。
プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。
コードセグメント
- C の関数よりも細かい単位。
- コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。
Continuation Based C
継続:現在の処理を実行していく為の情報
Cにおいての継続
- 続く命令のアドレス
- 命令に必要なデータ
- スタックに積まれている値(環境)
Continuation Based C (軽量継続)
CbCの継続(軽量継続)
関数コールが無い -> 呼び出し元への復帰がない
- Cの継続から環境を除外
- 続く命令とその命令に必要なデータのみ
Continuation based C
階乗を求めるCbCのプログラム
__code print_factorial(int prod) {
printf("factorial = %d\n",prod);
exit(0);
}
__code factorial0(int prod, int x) {
if ( x >= 1) {
goto factorial0(prod*x, x-1);
}else{
goto print_factorial(prod);
}
}
|
__code factorial(int x) {
goto factorial0(1, x);
}
int main(int argc, char **argv) {
int i;
i = atoi(argv[1]);
goto factorial(i);
return 0;
}
|
__code キーワードによるコードセグメントの宣言
goto によるコードセグメントへの継続(Cの関数呼び出しと同等)
GCC によるコンパイル
GCC についての簡単な説明を行う...
TODO: NEXT_PASS() の把握
CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。
CbCの実装
- シンタックスの追加
- レジスタによる引数渡し(fastcall属性の付与)
- Tail Call Elimination
- 環境付き継続
- __rectype の実装
CbCの実装:シンタックスの追加
- __code キーワードでのコードセグメントの宣言
- __code 用idとkeywordを作成。
- 戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。
- goto によるコードセグメントへの継続
- 通常の goto に加え、コードセグメントを呼び出す処理を追加。
- コードセグメントへのgoto後は、 return の処理を自動で追加。
追加したgotoシンタックスの実際のソースは次のようになる。
CbCの実装:シンタックスの追加
gotoシンタックスの追加
expr = c_parser_expr_no_commas (parser, NULL);
if (TREE_CODE(expr.value) == CALL_EXPR )
{
location_t loc = c_parser_peek_token (parser)->location;
cbc_replace_arguments (loc, expr.value);
TREE_TYPE(expr.value) = void_type_node;
/*tree env = NULL_TREE;**/
CbC_IS_CbC_GOTO (expr.value) = 1;
CALL_EXPR_TAILCALL (expr.value) = 1;
add_stmt(expr.value);
stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); /* stmt = c_finish_return (0); */
}
CALL_EXPR_TAILCALLマクロにより tail call フラグを立てている。
cbc_replace_arguments関数は引数のデータを一時的な変数へと代入させる関数
最後にc_finish_return関数によりreturn文を生成している。
CbCの実装:シンタックスの追加
gotoシンタックスの追加
最後にリターン文を生成することにより、次へと制御を映させず。また末尾最適化がかかるようになる。
実際のコード |
GCC 内で処理されるコード |
goto factorial0(1, x);
|
factorial0(1, x);
return;
|
末尾最適化(末尾除去)については後ほど詳しく説明する。
CbCの実装:引数渡し
当初、GCCを使ってコンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。
- Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていたため。
そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに
CbCの実装:引数渡し(fastcall)
i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。
__code で宣言された関数は自動でfastcall属性が付与される。
if(!TARGET_64BIT) {
attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
declspecs_add_attrs(specs, attrs);
}
Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。
CbCの実装:TCE
Tail Call Elimination(TCE):末尾除去
関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。
CbCにおけるコードセグメントへの継続はこのTCEにより実装されている。
CbCの実装:TCE
環境付き継続
CbCにおけるCとの互換性を保つための機能。
コードセグメントを呼び出したCの関数に戻ることができる。
環境付き継続:クロージャでの実装について
『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』
間違い
訂正
- GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。
- GCC 4.6 と Lion でのクロージャは特に問題はない。
環境付き継続:クロージャでの実装の問題点
環境付き継続: setjmp での実装
setjmp での実装
({
int a = setjmp(env);
int retval;
void _cbc_internal_return(int retval_, jmp_buf _envp){
retval = retval_;
longjmp(_envp, retval);
}
if (a) {
return retval;
}
_cbc_internal_return;
})
環境付き継続: setjmp での実装の問題
GCC 内で setjmp を生成する関数を作る必要がある。
戻値の型が int
setjmp での実装はあまり実用的ではない。
__rectype の実装
通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。
void factorial(int n, int result, void(*print)()){
:
(*print)(n,result,print,exit1, envp);
}
以下の様に扱えるようにしたい。
void factorial(int n, int result, void *print){
:
(*print)(n,result,print,exit1, envp);
}
__rectype の実装
そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。
__code factorial(int n, int result, __rectype *print) {
:
(*print)(n,result,print,exit1, envp);
}