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

大城信康

琉球大学並列信頼研究室

目的と背景(1)

当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。

コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。

Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。

目的と背景(2)

CbCのコンパイラは2001年に Micro-C版、2008年にはGCC-4.2をベースとしたコンパイラが開発された。

GCC上のCbCコンパイラは、GCCで修正・追加されていく最適化の機能を使用する為に、アップデートに合わせ変更する必要がある。

本研究ではCbCコンパイラをGCC-4.6へとアップデートを行った。

発表内容

CbC の紹介
GCC でのコンパイルの流れ

CbC の実装

Micro-C との性能比較
まとめ

Continuation based C

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

コードセグメント:CbCにおけるプログラムの基本単位

Cから関数コールとループ制御が取り除かれた形
C の関数よりも細かい単位になる。
コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。

Continuation based C

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

Cの継続	CbCの継続(軽量継続)
続く命令のアドレス命令に必要なデータスタックに積まれている値(環境)	Cの継続から環境を除外続く命令とその命令に必要なデータのみ

コードセグメントへの継続はcallではなくjmp命令で行われる

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

階乗を求める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の関数呼び出しと同等)

以上がCbCについての紹介となる。

GCC

GCC:Gnu Compiler Collection

GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。
cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。

Generic Tree
GIMPLE
Tree SSA
RTL

Generic Tree生成部分について詳しく触れてみる。

GCC:Generic Tree

CALL_EXPRE、MODIFY_EXPR、RETURN_EXPR等といった表現で扱われる。

ソースコード	Generic Treeでの表現
int main() { int a, b; a = 3; b = func(a, 10); return b; }

CbCの実装においてこのGeneric Treeの生成を意識していくことになる。

CbCの実装

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

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

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

__code 用idとkeywordを作成。
通常の関数作成と基本同じだが、コードセグメント判定用のフラグを立てる。

tree
build_code_segment_type (tree value_type, tree arg_types)
{
  tree t;
  hashval_t hashcode = 0;

  gcc_assert (TREE_CODE (value_type) == VOID_TYPE);

  /* Make a node of the sort we want.  */
  t = make_node (FUNCTION_TYPE);
  TREE_TYPE (t) = value_type;
  TYPE_ARG_TYPES (t) = arg_types;

  CbC_IS_CODE_SEGMENT (t) = 1;

  if (!COMPLETE_TYPE_P (t))
    layout_type (t);
  return t;
}

コードセグメントはGCC内部では関数として扱われる。

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

goto によるコードセグメントへの継続

通常の 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 )
     {
          :
     }
#ifndef noCbC
   else
     {
       if (c_parser_next_token_is (parser, CPP_NAME))
	 {
	   tree id = c_parser_peek_token (parser)->value;
	   location_t loc = c_parser_peek_token (parser)->location;
	   /** build_external_ref (id,RID_CbC_CODE , loc); **/
	   build_external_ref (loc, id, RID_CbC_CODE, &expr.original_type);
	 }
       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);
	 }
       else
	 c_parser_error (parser, "expected code segment jump or %<*%>");
     }
#else

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

cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。

CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。

最後にc_finish_return関数によりreturn文を生成している。

実際のコード	GCC内で処理されるコード
__code test() { : goto factorial0(1, x); }	void test() { : factorial0(1, x); return; }

これで__codeによるコードセグメントの宣言と、gotoによる関数呼び出しが行われるようになった。
次に、コードセグメントへの関数呼び出しは軽量継続で行わせる処理がいる。

CbCの実装:軽量継続(末尾除去)

軽量継続は末尾除去(Tail Call elimination)によって実装される。

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

以下のソースの場合関数g から関数f へjmp命令で処理が移る。


void f(int a, int b) {
  printf("f: a=%d b=%d\n",a,b);
  return ;
}
void g(int a, int b){
  printf("g: a=%d b=%d\n",a,b);
  f(a,b);
  return;
}

int main() {
  g(3,4);
  return 0;
}

CbCの実装:軽量継続(末尾除去)

末尾除去にかかる条件

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

条件を回避する為以下の実装にする。

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

CbCの実装:軽量継続(末尾除去)

末尾除去の条件はexpand_call関数で調べられる。

expand_call関数

SSAへの変換を終えたGIMPLEからとり出されたCALL_EXPREのTreeからRTLを生成する関数
スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。
try_taill_call(局所変数)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。

具体的な実装内容

try_tail_callフラグを落とすif文の条件をかわすようにする。
try_tail_callフラグを立たせる処理の追加。

CbCの実装:軽量継続(末尾除去)

try_tail_callフラグを落とさせない。

  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;

try_tail_callフラグ矯正付与のソースコード

  if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
      && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
      && try_tail_call == 0)
    {
      location_t loc = EXPR_LOCATION (exp);
      char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
      warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
                        name_callee);
      try_tail_call = 1;
    }

CbCの実装:軽量継続(末尾除去)の実装について

以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。
だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。
しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。

CbCの実装:引数渡し

GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。

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

そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。

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

fastcall

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

__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。

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

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

CbCの実装:引数渡し

fastcall属性の付与によりMicro-C版に速度で勝るようになった。

引数渡しに使われるレジスタの数(gcc)
arch	int(整数型)	float(浮動小数点型)	double(浮動小数点型)
i386	2	0 (stackを使用)	0 (stackを使用)
x64	6	8	8

CbCの実装:環境付き継続

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

以下の使い方の場合は1を返す。

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

__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。

CbCの実装:環境付き継続

生成しているコード

生成するコード(GCC内部)


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


    case RID_CbC_RET:
{
  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;
}

retval変数の型は継続を行った関数と同じ戻値の型となる。

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

重要な部分

リターンするretval変数のメモリ確保

次の方法が考えられる。

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

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

クロージャでの実装の問題点:

CbCでは継続によりスタックの値は破棄されていく。
クロージャにしたコードが破棄される可能性がある。

staticでの実装の問題点:

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

static tlsでの実装

現在はこの方法で実装を行なっている。
しかし、最適化にかけると正しい値が返ってこない。
(最適化によりコードが削除されている...?)

クロージャの動作について

予稿における訂正

『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』

CbCの末尾除去矯正付与のせいでクロージャが破壊されていたことが判明。
GCC 4.6 と Lion でのクロージャは特に問題はなかった。

Micro-Cとの比較

Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度

最適化無しだと、引数を全て一時変数に代入するGCCは遅い。だが、最適化にかければ不要な代入は減りMicro-C版より早くなる。

まとめ

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

今後の課題

CbCを用いたプログラムの作成

CbCによるタスクマネージャの作成

llvmへのCbCの実装

ご清聴ありがとうございました。

CbCの引数渡し

fastcall属性有・無の実行速度
fastcall有り	fastcall無し

軽量継続(末尾除去)の動作

スタック:呼び出し元関数と同じ範囲を使うことになる。

func_bの引数はfunc_aのスタックに上書する
func_bの為にスタックポインタは伸ばされない

call_insn

expand_callより作成されたRTLのTreeは以下のS式となる。


(call_insn/j 18 17 19 3 (call (mem:QI (symbol_ref:DI ("factorial") [flags 0x403]  <function_decl 0x1443b4400 factorial>) [0 S1 A8])
        (const_int 1024 [0x400])) factorial.cbc:30 -1
     (expr_list:REG_EH_REGION (const_int 0 [0])
        (nil))
    (expr_list:REG_DEP_TRUE (use (reg:SI 5 di))
        (nil)))

__rectype の実装

通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。

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

そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。

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

selftype

selftypeの実装

以下の宣言が行えるようにしたい。

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

selftype は struct node を指す。

環境付き継続

生成する為のコード

生成されるTree


    case RID_CbC_RET:
{
  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;
}

環境付き継続

生成しているコード

生成されるTree


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

引数の並びの上書きにコピーが無い。

__code cs_a(int a, int b) {
  goto cs_b(b,a);
}

プログラミングシンポジウム: 2012/ 1/ 7

並列信頼研

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

琉球大学 並列信頼研究室

目的と背景(1)

目的と背景(2)

発表内容

Continuation based C

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

Continuation based C

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

Continuation based C

GCC

GCC:Generic Tree

CbCの実装

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

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

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

CbCの実装:軽量継続(末尾除去)

軽量継続は末尾除去(Tail Call elimination)によって実装される。

CbCの実装:軽量継続(末尾除去)

CbCの実装:軽量継続(末尾除去)

CbCの実装:軽量継続(末尾除去)

CbCの実装:軽量継続(末尾除去)の実装について

CbCの実装:引数渡し

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

fastcall

CbCの実装:引数渡し

CbCの実装:環境付き継続

CbCの実装:環境付き継続

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

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

クロージャの動作について

Micro-Cとの比較

まとめ

今後の課題

ご清聴ありがとうございました。

CbCの引数渡し

軽量継続(末尾除去)の動作

call_insn

__rectype の実装

selftype

selftypeの実装

環境付き継続

環境付き継続

琉球大学並列信頼研究室