Continuation based Cの GCC 4.6 上の実装について

琉球大学 並列信頼研究室

目的と背景(1)

目的と背景(2)

発表内容

1. CbC の紹介
2. GCC でのコンパイルの流れ
3. CbC の実装
4. Micro-C との性能比較
5. mercurial を用いたアップデートの方法
6. まとめ

Continuation based C

コードセグメント単位での記述と継続を基本としたプログラミング言語。

• C の関数よりも細かい単位。
• コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。

Continuation Based C

継続:現在の処理を実行していく為の情報

• 続く命令のアドレス
• 命令に必要なデータ
• スタックに積まれている値(環境)

• Cの継続から環境を除外
• 続く命令とその命令に必要なデータのみ

Continuation Based C (軽量継続)

Continuation based C

__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;
}

Continuation Based C

GCC によるコンパイル

CbC の実装

• シンタックスの追加
• fastcall属性の付与
• Tail Call Elimination
• 環境付き継続

シンタックスの追加

• __code でコードセグメントの宣言
• goto にコードセグメントへの継続処理を追加

シンタックスの追加

__code でコードセグメントの宣言

• __code 用idとkeywordを作成。
• 戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。

シンタックスの追加

goto シンタックスの追加

• 通常の goto に加え、コードセグメントを呼び出す処理を追加。
• コードセグメントへのgoto後は、 return の処理を自動で追加。

goto factorial0(1, x); 
	    

factorial0(1, x); 
return;
	    

引数渡し

• Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていたため。

引数渡し(fastcall属性の付与)

if(!TARGET_64BIT) {
  attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 
  declspecs_add_attrs(specs, attrs);
 }	  
	

Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。

typedef struct node {
 selftype *right;
 selftype *left;
}*NODE	  
	

環境付き継続とは

環境付き継続:クロージャでの実装について

• GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。
• GCC 4.6 と Lion でのクロージャは特に問題はない。

環境付き継続:クロージャでの実装の問題点

環境付き継続: 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 での実装の問題

• 構造体等ポインタの場合使えない。

__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 の実装

__code factorial(int n, int result, __rectype *print) {
   :
   (*print)(n,result,print,exit1, envp);
}