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

琉球大学 並列信頼研究室

目的と背景(1)

目的と背景(2)

発表内容

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

Continuation based C

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

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

Continuation based C

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

Cの継続	CbCの継続(軽量継続)
続く命令のアドレス 命令に必要なデータ スタックに積まれている値(環境)	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;
}

• __code キーワードによるコードセグメントの宣言
• goto によるコードセグメントへの継続(Cの関数呼び出しと同等)

GCC

• GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。
• cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。
• Generic Tree
• GIMPLE
• Tree SSA
• RTL
• Generic Tree生成部分について詳しく触れてみる。

GCC:Generic Tree

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

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

CbCの実装: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文を生成している。

__code test() {
   :
  goto factorial0(1, x); 
}
	    

void test() {
   :
  factorial0(1, x); 
  return;
}
	    

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

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

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

• 関数呼び出しをcallではなく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関数
• 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の実装:引数渡し

• 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の実装:引数渡し

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

CbCの実装:環境付き継続

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

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

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

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

    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変数のメモリ確保

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

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

• クロージャでの実装の問題点:
• CbCでは継続によりスタックの値は破棄されていく。
• クロージャにしたコードが破棄される可能性がある。
• staticでの実装の問題点:
• マルチスレッドのプログラムに対応できない。
• 値を返し切る前に別スレッドによって値が書き換えられる可能性がある。
• static tlsでの実装
• 現在はこの方法で実装を行なっている。
• しかし、最適化にかけると正しい値が返ってこない。
  (最適化によりコードが削除されている...?)

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

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

Micro-Cとの比較

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

まとめ

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

今後の課題

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

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

CbCの引数渡し

fastcall属性有・無の実行速度

fastcall有り	fastcall無し

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

call_insn

(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