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

琉球大学 並列信頼研究室

目的と背景(1)

目的と背景(2)

発表内容

1. CbC の紹介
2. GCC でのコンパイルの流れ
3. CbC の実装
4. Micro-C との性能比較
5. まとめ

Continuation based C

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

• プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。

コードセグメント

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

Continuation Based C

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

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

Continuation Based C (軽量継続)

CbCの継続(軽量継続)

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

Cの関数呼び出し	CbCの継続

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

GCC によるコンパイル

CbCの実装

• シンタックスの追加
• レジスタによる引数渡し(fastcall属性の付与)
• Tail Call Elimination
• 環境付き継続
• __rectype の実装

CbCの実装:シンタックスの追加

• __code キーワードでのコードセグメントの宣言
• __code 用idとkeywordを作成。
• 戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。
• goto によるコードセグメントへの継続
• 通常の goto に加え、コードセグメントへ継続する処理を追加。
• コードセグメントへのgotoの後に、returnの処理を自動で追加。

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

CbCの実装:シンタックスの追加

gotoシンタックスの追加

goto factorial0(1, x); 
	    

factorial0(1, x); 
return;
	    

CbCの実装:引数渡し

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

CbCの実装:引数渡し(fastcall)

fastcall

• i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。
• 関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。

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

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

CbCの実装:引数渡し

CbCの実装:TCE

Tail Call Elimination(TCE):末尾除去

CbCの実装:TCE

具体的な実装内容

• try_tail_call(変数名)フラグを立てる。
• try_tail_callフラグを落とさせない。

CbCの実装:TCE

• expand_call関数
• Treeで表された関数からRTLを生成する関数

• caller側とcallee側の戻値の型の一致している。
• 関数呼び出しがリターン直前に行われている。
• 呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。
• 引数の並びのコピーに上書きがない。

CbCの実装:TCE

• void型で統一。
• gotoの直後にreturnを置く。
• スタックサイズは固定。
• 引数は一旦、一時変数にコピーする。

CbCの実装:環境付き継続

__code c1(__code ret(int,void *),void *env) {
 goto ret(1,env);
}
int main() {
 goto c1(__return, __environment);
}
	

__environmentキーワードは関数の環境を保存している。

CbCの実装:環境付き継続

実際には以下のコードを生成している。

goto c1(__return, __environment);

goto c1(
	({
	  __label__ _cbc_exit0;
	  static int retval;
	  void _cbc_internal_return(int retval_, void *_envp){
	    retval = retval_;
	    goto _cbc_exit0; }
	  if (0) { _cbc_exit0:
	    return retval; }
	  _cbc_internal_return;
	}), 
	__environment);
	  

CbCの実装:環境付き継続

環境付き継続の生成部分:

{
  tree value, stmt, label, tlab, decl;
  c_parser_consume_token (parser);

  stmt = c_begin_stmt_expr ();
  cbc_return_f = c_parser_peek_token (parser)->value;
  location_t location = c_parser_peek_token (parser)->location;

  /* create label. (__label__ _cbc_exit0;) */
  label = get_identifier ("_cbc_exit0");
  tlab = declare_label (label);
  C_DECLARED_LABEL_FLAG (tlab) = 1;
  add_stmt (build_stmt (location, DECL_EXPR, tlab));

  /* declare retval.  (int retval;) */
  tree decl_cond =
    build_decl (location, VAR_DECL, get_identifier ("retval"),
		TREE_TYPE (TREE_TYPE (current_function_decl)));
  TREE_STATIC (decl_cond) = 1;
  TREE_USED (decl_cond) = 1;

  /* Use thread-local */
  DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
  DECL_NONLOCAL (decl_cond) = 1;
  add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));

  /* define nested function.  */
  decl =
    cbc_finish_nested_function (location, label, decl_cond);
  TREE_USED(decl) = 1;

  /* define if-ed goto label and return statement. */
  cbc_finish_labeled_goto (location, label, decl_cond);

  /* get pointer to nested function.  */
  value = build_addr (decl , current_function_decl);
  TREE_USED (current_function_decl) = 1;
  SET_EXPR_LOCATION (value, location);
  add_stmt (value);

  TREE_SIDE_EFFECTS (stmt) = 1;
  expr.value = c_finish_stmt_expr (location, stmt);
  expr.original_code = ERROR_MARK;
}
	  

CbCの実装:環境付き継続

作成されるTree

環境付き継続:実装の問題

• リターンするretval変数が重要になってくる。
• retval変数のデータをどうやって確保するか。

• クロージャでの確保
• staticでの確保
• static thread local storage(tls)を用いての確保

環境付き継続:実装の問題

• クロージャにしてスタックに値を確保する。

• しかしCbCではスタックの値は破棄されていく。
• その為スタックに値を確保するのは好ましくない。

環境付き継続:実装の問題

• 静的に値を確保することでスタック破棄の影響を受けない。

• マルチスレッドのプログラムに対応できない。
• 値を返し切る前に別スレッドによって値が書き換えられる可能性がある。

環境付き継続:実装の問題

• スレッド毎に静的に値を確保する。

環境付き継続:その他の実装方法

• setjmpでの実装
• setjmpを行うTreeを生成するのが少し手間になる。
• int型の戻値しか得られない。
• 戻値を入れるレジスタを明示的に指定する。
• まだ実装を試していない。

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

CbCの機能の拡張

selftypeの実装

typedef sturct node {
 selftype *left;
 selftype *right;
 int num;
}*NODE
	

• 上記の構文は実装を行う予定である。

Micro-Cとの比較

まとめ

• 今回GCC版CbCコンパイラのアップデートを行った。
• TCEにかかる判定の部分と環境付き継続の実装の修正を行った。
  おかげで、以前より楽な管理ができる実装にすることができた。
• 後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。
• 全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。

今後の予定

• CbCを用いたプログラムの作成
• CbCによるタスクマネージャの作成
• llvmへのCbCの実装