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

• GCCではアセンブラ言語を出力するまでに読み込まれたソースコード次の4つの内部表現へと変換される。

GCC

1. Generic Tree:ソースコードを構文木の形に直したもの
2. GIMPLE: Generic Treeの命令を簡単にした構文木
3. Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木
4. RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。

GCC

void factorial(int x)
{
  int prod,i;
  for(i=1,prod=1; i <= x; i++){
    prod = prod*i;
  }
  print_factorial(prod);
}
	      

factorial (int x)
{
  int prod;
  int i;

  i = 1;
  prod = 1;
  goto <D.2846>;
  <D.2845>:
  prod = prod * i;
  i = i + 1;
  <D.2846>:
  if (i <= x) goto <D.2845>; else goto <D.2847>;
  <D.2847>:
  print_factorial (prod);
}
	      

GCC

factorial (int x)
{
  int i;
  int prod;

<bb 2>:
  i_3 = 1;
  prod_4 = 1;
  goto <bb 4>;

<bb 3>:
  prod_6 = prod_1 * i_2;
  i_7 = i_2 + 1;

<bb 4>:
  # prod_1 = PHI <prod_4(2), prod_6(3)>
  # i_2 = PHI <i_3(2), i_7(3)>
  if (i_2 <= x_5(D))
    goto <bb 3>;
  else
    goto <bb 5>;

<bb 5>:
  print_factorial (prod_1);
  return;
}

		

(call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403]  <function_decl 0x146f6b200 print_factorial>) [0 S1 A8])
        (const_int 0 [0]))
              

GCC

GCC:Generic Tree

	値の代入:MODIFY_EXPR	関数呼び出し:CALL_EXPR
命令	b = a * 10	func(a,10)
Generic Tree

Generic Treeでの表現

GCC:Generic Tree

int main() {
  int a, b;
  a = 3;
  b = func(a, 10);
  return b;
}
	

CbCの実装

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

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

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

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

gotoシンタックスの追加

 case RID_GOTO:
   c_parser_consume_token (parser);
   if ( c_parser_next_token_is (parser, CPP_NAME)
	&& c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
     {
       stmt = c_finish_goto_label (loc,
				   c_parser_peek_token (parser)->value);
       c_parser_consume_token (parser);
     }
   else if (c_parser_next_token_is (parser, CPP_MULT))
     {
       tree val;

       c_parser_consume_token (parser);
       val = c_parser_expression (parser).value;
       mark_exp_read (val);
       stmt = c_finish_goto_ptr (loc, val);
     }
   else
     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):末尾除去

• 関数呼び出しをcallではなくjmp命令で行う最適化。

int main() { int num = a(2); printf("main:num=%d\n",num); return 0; } int a(int num) { return b(num+5); } int b(int num) { printf("b:a = %d\n",num); return num+3; }

CbCの実装:TCE(末尾除去)の動作

CbCの実装:TCE(末尾除去)

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

CbCの実装:TCE(末尾除去)

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

CbCの実装:TCE(末尾除去)

• Treeで表された関数からRTLを生成する関数
• スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。
• try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。

• try_tail_callフラグを落とさせない処理が追加されている。

CbCの実装:TCE(末尾除去)

  if (currently_expanding_call++ != 0
      || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) 
         && !flag_optimize_sibling_calls)
      || args_size.var
      || dbg_cnt (tail_call) == false)
    try_tail_call = 0;
	

CbCの実装:環境付き継続

• CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。
• __returnキーワードを引数に渡すことで使うことができる。

__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

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

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

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

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

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

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

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

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

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

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

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

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

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

CbCの機能の拡張:__rectype の実装

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

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

CbCの機能の拡張:__rectype の実装

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

CbCの機能の拡張:selftype

selftypeの実装

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

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

Micro-Cとの比較

まとめ

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

今後の予定

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