Continuation Based C (軽量継続)

- +
継続:現在の処理を実行していく為の情報
+ +
+ + + + + + + + - - - - - - + -
Cの継続 CbCの継続(軽量継続)
+
+
続く命令のアドレス
+
命令に必要なデータ
+
スタックに積まれている値(環境)
+
+ +
+
Cの継続から環境を除外
+
続く命令とその命令に必要なデータのみ
+
+

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

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

スタックに載るデータは1つのコードセグメントの必要なデータのみ。

@@ -241,150 +225,18 @@

GCC

本来はGnu Compiler Collectionのことを指すが、 -
ここで扱うのはGnu C Compiler(cc1)になる。

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

GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。
Generic Tree
GIMPLE
Tree SSA
RTL

- -

GCC

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

それぞれは次のようなデータを構文木にして持っている。

- -

GCC

- - - - - - - - - -

Generic(ソースコード)

GIMPLE

-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

- - - - - - - - - -

SSA

RTL(一部)

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

-(jump_insn 20 19 21 5 (set (pc)
-        (if_then_else (le (reg:CCGC 17 flags)
-                (const_int 0 [0]))
-            (label_ref 17)
-            (pc))) factorial.c:12 -1
-     (nil)
- -> 17)
-
-(note 21 20 22 6 [bb 6] NOTE_INSN_BASIC_BLOCK)
-
-(insn 22 21 23 6 (set (reg:SI 62)
-        (mem/c/i:SI (plus:DI (reg/f:DI 54 virtual-stack-vars)
-                (const_int -4 [0xfffffffffffffffc])) [0 prod+0 S4 A32])) factorial.c:15 -1
-     (nil))
-
-(insn 23 22 24 6 (set (reg:SI 5 di)
-        (reg:SI 62)) factorial.c:15 -1
-     (nil))
-
-(call_insn 24 23 25 6 (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403]  ) [0 S1 A8])
-        (const_int 0 [0])) factorial.c:15 -1
-     (nil)
-    (expr_list:REG_DEP_TRUE (use (reg:SI 5 di))
-        (nil)))
-
-(code_label 25 24 26 7 2 "" [0 uses])
-
-(note 26 25 0 7 [bb 7] NOTE_INSN_BASIC_BLOCK)
-

- -

GCC

- -

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

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

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

Continuation based C

Continuation Based C (軽量継続)

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

GCC

GCC

GCC

GCC

GCC