@@ -131,9 +131,9 @@

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

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

@@ -225,16 +225,19 @@

GCC

GCC:Gnu Compiler Collection

本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。
GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。
GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。
cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。

Generic Tree
GIMPLE
Tree SSA
RTL

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

GCC:Generic Tree

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

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

@@ -311,12 +314,12 @@

CbCの実装

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

@@ -326,52 +329,72 @@

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

__code 用idとkeywordを作成。
戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。
通常の関数作成と基本同じだが、コードセグメント判定用のフラグを立てる。

ソースコード

+ +

+	      +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 に加え、コードセグメントへ継続する処理を追加。
通常の goto の構文にコードセグメントへ継続する処理を追加。

追加したgotoシンタックスの実際のソースは次のようになる。

+	
+	  
+	    
+	    
+	  
+	    case RID_GOTO:
    c_parser_consume_token (parser);
    if ( c_parser_next_token_is (parser, CPP_NAME)
@@ -390,19 +413,35 @@
        mark_exp_read (val);
        stmt = c_finish_goto_ptr (loc, val);
      }
+#ifndef noCbC
    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);
+       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
 	
+

@@ -445,14 +484,18 @@

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

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

末尾除去:Tail Call Elimination(TCE)

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

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

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

@@ -497,16 +540,16 @@ -

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

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

TCEにかかる条件
末尾除去にかかる条件

caller側とcallee側の戻値の型の一致している。
関数呼び出しがリターン直前に行われている。

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

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

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

TCEの条件はexpand_call関数で調べられる。

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

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

expand_call関数

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

具体的な実装内容

@@ -543,7 +586,7 @@

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

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

try_tail_callフラグが落とされる部分

@@ -629,7 +672,7 @@

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

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

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

@@ -652,13 +695,12 @@

try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。 -
(最適化の矯正付与)
try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。(最適化の矯正付与)

CbCの実装:TCE(末尾除去)の実装について

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

以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。
だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。

CbCの実装:環境付き継続

- - - - - - - + + +

生成されるTree	生成する為のコード
- -	@@ -883,25 +877,31 @@ }

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

+ +

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

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

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

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

diff -r d53237223e13 -r 923dd8de7be2 presen/index.html~ --- a/presen/index.html~ Wed Jan 04 17:16:44 2012 +0900 +++ b/presen/index.html~ Wed Jan 04 23:41:05 2012 +0900 @@ -4,7 +4,22 @@ - -2011/12/20 +2012/ 1/ 7 - + @@ -68,7 +83,7 @@

@@ -85,141 +100,963 @@

目的と背景(1)

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

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

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

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

目的と背景(2)

CbC のコンパイラは2008年に GCC をベースとしたコンパイラが開発された。

GCC をベースとした CbC コンパイラは、GCC のアップデートに合わせ変更する必要がある。

本研究ではGCC-4.5 をベースとしていた CbC コンパイラを GCC-4.6 へのアップデートを行い、Intel64 への対応するとともに CbC の拡張を行う。

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

+ +

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

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

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

今週の作業内容

環境付き継続について

GCC

本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。
GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。

Generic Tree
GIMPLE
Tree SSA
RTL

CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。
Generic Tree生成部分について詳しく触れてみる。

+ + + +

GCC:Generic Tree

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

+ + + + + + + + + +

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

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

+ + + +

CbCの実装

シンタックスの追加
末尾除去:Tail Call Elimination(TCE)
レジスタによる引数渡し(fastcall属性の付与)
環境付き継続

+ +

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

変数 retval を static スレッドローカル(TLS)での実装
__code キーワードでのコードセグメントの宣言

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

+ + + + + + + + + + +

+const struct c_common_resword c_common_reswords[] =
+{
+ { "_Bool",            RID_BOOL,      D_CONLY },
+     :
+ { "__code",         RID_CbC_CODE,   0 },		
+

+case RID_CbC_CODE:     
+      :
+ specs->typespec_word = cts_CbC_code;		
+

+case cts_CbC_code: 
+       :
+     specs->type = void_type_node; 
+     break;
+

+ +

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

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

通常の goto に加え、コードセグメントへ継続する処理を追加。
コードセグメントへのgotoの後に、returnの処理を自動で追加。

追加した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シンタックスの追加

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

tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。
最後のリターン文生成も、末尾除去にかける為に必要な処理。

+ +

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

末尾除去:Tail Call Elimination(TCE)

関数呼び出しを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の実装:TCE(末尾除去)

TCEにかかる条件

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

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

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

static TLS のGeneric Tree

変数 retval の宣言(VAR_DECL)

static TLS の場合追加される情報は以下の2つ:(Linux)

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

TCEの条件はexpand_call関数で調べられる。

expand_call関数

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

上記の設定で retval を作成しても正しい返り値は得られなかった。
具体的な実装内容

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

環境付き継続の構文木をみる

環境継続において以下の retval 変数は static で作られている.

- -

-({
-  __label__ _cbc_exit0;
-  static __thread int retval;
-  void _cbc_internal_return(int retval_, void *_envp){
-    printf("in _cbc_internal_return\n",retval_);
-    retval = retval_;
-    goto _cbc_exit0;
-  }
-  if (0) {
-  _cbc_exit0:
-    return retval;
-  }
-  _cbc_internal_return;
-})
-

- -

環境付き継続の構文木をみる

BIND_EXPR は{ } の中身を束ねる。

STATEMENT_LIST が1つ1つのプログラムを表す木を持っている。

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

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;
+
+     :
+
+  if (
+#ifdef HAVE_sibcall_epilogue
+      !HAVE_sibcall_epilogue
+#else
+      1
+#endif
+      || !try_tail_call
+      || structure_value_addr != NULL_RTX
+#ifdef REG_PARM_STACK_SPACE
+      || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
+          != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
+      || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl))
+#endif
+      || !targetm.function_ok_for_sibcall (fndecl, exp)
+      || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
+      || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
+      || (fndecl && decl_function_context (fndecl) == current_function_decl)
+      || args_size.constant > (crtl->args.size
+                               - crtl->args.pretend_args_size)
+      || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
+          != targetm.calls.return_pops_args (current_function_decl,
+                                             TREE_TYPE (current_function_decl),
+                                             crtl->args.size))
+      || !lang_hooks.decls.ok_for_sibcall (fndecl))
+    try_tail_call = 0;
+
+      :
+
+  /* Check if caller and callee disagree in promotion of function                                                                                                                      
+     return value.  */
+#ifndef noCbC
+  if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
+#else
+    if (try_tail_call)
+#endif
+    {
+      enum machine_mode caller_mode, caller_promoted_mode;
+      enum machine_mode callee_mode, callee_promoted_mode;
+      int caller_unsignedp, callee_unsignedp;
+      tree caller_res = DECL_RESULT (current_function_decl);
+
+      caller_unsignedp = TYPE_UNSIGNED (TREE_TYPE (caller_res));
+      caller_mode = DECL_MODE (caller_res);
+      callee_unsignedp = TYPE_UNSIGNED (TREE_TYPE (funtype));
+      callee_mode = TYPE_MODE (TREE_TYPE (funtype));
+      caller_promoted_mode
+        = promote_function_mode (TREE_TYPE (caller_res), caller_mode,
+                                 &caller_unsignedp,
+                                 TREE_TYPE (current_function_decl), 1);
+      callee_promoted_mode
+        = promote_function_mode (TREE_TYPE (funtype), callee_mode,
+                                 &callee_unsignedp,
+                                 funtype, 1);
+      if (caller_mode != VOIDmode
+          && (caller_promoted_mode != callee_promoted_mode
+              || ((caller_mode != caller_promoted_mode
+                   || callee_mode != callee_promoted_mode)
+                  && (caller_unsignedp != callee_unsignedp
+                      || GET_MODE_BITSIZE (caller_mode)
+                         < GET_MODE_BITSIZE (callee_mode)))))
+        try_tail_call = 0;
+    }
+

!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避

環境付き継続の構文木をみる

BIND_EXPR は _cbc_internal_return 関数を
- ADDR_EXPR は最後の行の _cbc_internal_return を表す。

- -

環境付き継続の構文木をみる

_CbC_return の実装より作られる構文木を見てみる。

- -

環境付き継続の構文木をみる

出来上がる構文木が違う。

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

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

+ + + + +

+#ifndef noCbC
+  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;
+    }
+#endif
+

DECL_EXPR が 1つ足りない -
BIND_EXPR の部分が COND_EXPR になっている。
try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。 +
(最適化の矯正付与)

DECL_EXPR の問題

なくなっている DECL_EXPR は VAR_DECL の部分。

static __thread int retval になる。

下記の様にソースを変更

-//      pushdecl (decl_cond);
-add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));
-

これで DECL_EXPR が追加された。

- -

COND_EXPR の問題

BIND_EXPR でなくて COND_EXPR になっていた問題。

BIND_EXPR をみると以下の様な構成になっていた。

BIND_EXPR をなぜか COND_EXPR でもう一度包んでいた。

- -

COND_EXPR には if(0){ } の中身が入る。

- -

ソースの手直し

if(0){ } の構文木が作られる手順を元に
- cbc_finish_labeled_goto 関数を手直しした。 -

同じ構文木が作られるようになった。

- -

結果

正常な値が返ってくるようになった。

しかし、-O2 オプションをつけると返り値の取得が失敗した。

もっと細かく構文木をみて違いを見つける必要がある。

CbCの実装:TCE(末尾除去)の実装について

以前は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の実装:環境付き継続

+ + + + + + + + + + +

生成しているコード

生成される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);
+

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

CbCの実装:環境付き継続

+ + + + + + + + + +

生成される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;
+}
+

+ +

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

重要な部分

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

次の方法が考えられる。

クロージャでの確保
staticでの確保
setjmpを用いての実装
static thread local storage(tls)を用いての確保
戻り値を入れるレジスタを明示的に指定

+ +

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

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

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

staticでの実装の問題点:

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

setjmpでの実装

setjmpを行うTreeを生成するのが少し手間になる。
int型の戻値しか得られない。

+ +

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

static tlsでの実装

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

戻値を入れるレジスタを明示的に指定する。

まだ実装を試していない。

+ +

Micro-Cとの比較

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

+ + + +

GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 + その為に明らかに遅くなっていることが分かる。

だがGCCの最適化有りの場合はMicro-C版よりも早い。

+ +

まとめ

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

+ +

今後の予定

プロシン用プレゼンの用意

typedefrec, selftype の実装

CbC でタクスマネージャ作成

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

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

llvmへのCbCの実装

+
+

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

+ +

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

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

+ + + +

+ +

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

CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。

+ +

CbCの機能の拡張:__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);
+}
+

+ +

CbCの機能の拡張:selftype

selftypeの実装

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

+ +

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

selftype は struct node を指す。

+ +

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

目的と背景(2)

GCC

GCC:Generic Tree

CbCの実装

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

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

末尾除去:Tail Call Elimination(TCE)

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

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

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

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

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

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

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

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

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

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

CbCの実装:TCE(末尾除去)の実装について

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

CbCの実装:環境付き継続

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

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

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

Micro-Cとの比較

まとめ

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

CbCの引数渡し

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

セミナー: 2011/ 12/ 20

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

並列信頼研

目的と背景(1)

目的と背景(2)

発表内容

Continuation based C

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

Continuation based C

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

Continuation based C

今週の作業内容

GCC

GCC:Generic Tree

CbCの実装

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

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

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

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

末尾除去:Tail Call Elimination(TCE)

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

static TLS のGeneric Tree

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

環境付き継続の構文木をみる

環境付き継続の構文木をみる

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

環境付き継続の構文木をみる

環境付き継続の構文木をみる

環境付き継続の構文木をみる

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

DECL_EXPR の問題

COND_EXPR の問題

ソースの手直し

結果

CbCの実装:TCE(末尾除去)の実装について

CbCの実装:引数渡し

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

fastcall

CbCの実装:引数渡し

CbCの実装:環境付き継続

CbCの実装:環境付き継続

CbCの実装:環境付き継続

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

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

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

Micro-Cとの比較

まとめ

今後の予定

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

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

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

CbCの機能の拡張:selftype