Continuation based C

- +

階乗を求めるCbCのプログラム

@@ -227,12 +225,95 @@

GCC によるコンパイル

GCC

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

GCCでは次の4つの内部表現が扱われる。

Generic Tree
GIMPLE
Tree SSA
RTL

+ +

GCC

Generic Tree:ソースコードを構文木の形に直したもの

GIMPLE: Generic Treeの命令を簡単にした構文木

Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木

RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。

+ +

GCC

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

+ +

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

+ +

GCC:Generic Tree

Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。

+ + + + + + + + + +

値の代入:MODIFY_EXPR	関数呼び出し:CALL_EXPR
+ +	+ +

Generic Treeでの表現

+ +

GCC:Generic Tree

それぞれの命令はSTATEMENT_LISTでまとめて保持される。

+ + + + + + + + + +

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

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

+ +

CbCの実装

@@ -281,8 +362,8 @@ -

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

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

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

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

@@ -319,7 +400,7 @@

CbCの実装:引数渡し

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

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

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

@@ -399,23 +480,27 @@

次の条件を満たしていないとtry_tail_callフラグを落とす。

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

+ +

CbCの実装:TCE

フラグを落とされない為にコードセグメントは次の条件で作成する。

void型で統一。

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

+ +

これでコードセグメントへの処理はjmp命令で移ることになる。

@@ -466,18 +551,19 @@

 goto c1(__return, __environment);
 
-goto c1(
-	({
+goto c1(({
 	  __label__ _cbc_exit0;
 	  static int retval;
-	  void _cbc_internal_return(int retval_, void *_envp){
+	  void _cbc_internal_return(int retval_, void *_envp) {
 	    retval = retval_;
-	    goto _cbc_exit0; }
-	  if (0) { _cbc_exit0:
-	    return retval; }
+	    goto _cbc_exit0; 
+          }
+	  if (0) { 
+            _cbc_exit0:
+	    return retval; 
+          }
 	  _cbc_internal_return;
-	}), 
-	__environment);
+	}), __environment);

retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。

@@ -629,7 +715,7 @@

__rectype の実装

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

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

@@ -651,7 +737,7 @@

__rectype の実装

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

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

 __code factorial(int n, int result, __rectype *print) {
@@ -662,7 +748,7 @@

CbCの機能の拡張

CbCの機能の拡張:selftype

selftypeの実装

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

@@ -682,7 +768,7 @@

Micro-Cとの比較

以下はMicro-C,GCC-4.4とGCC-4.6それぞれのCbCコンパイラでコンパイルしたプログラムの実行結果

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

diff -r 1bc732d13326 -r 1399414ea3f6 presen/omni/STATEMENT_LIST_1.graffle --- a/presen/omni/STATEMENT_LIST_1.graffle Thu Dec 29 01:53:43 2011 +0900 +++ b/presen/omni/STATEMENT_LIST_1.graffle Thu Dec 29 16:01:24 2011 +0900 @@ -14,7 +14,7 @@ BackgroundGraphic Bounds - {{0, 0}, {1118, 783}} + {{0, 0}, {559, 783}} Class SolidGraphic ID @@ -51,125 +51,6 @@ Bounds - {{486, 187}, {120, 22}} - Class - ShapedGraphic - ID - 73 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 _cbc_internal_return\ -(address)} - VerticalPad - 0 - - - - Bounds - {{401.5, 239}, {81, 22}} - Class - ShapedGraphic - ID - 72 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 if(0) \{..\}} - VerticalPad - 0 - - - - Bounds {{253, 241}, {120, 22}} Class ShapedGraphic @@ -348,400 +229,6 @@ Class LineGraphic - Head - - ID - 68 - - ID - 69 - Points - - {428, 187} - {428, 215} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - TailArrow - 0 - TailScale - 0.5 - - - Tail - - ID - 62 - - - - Bounds - {{378, 215}, {100, 26}} - Class - ShapedGraphic - ID - 68 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 COND_EXPR} - VerticalPad - 0 - - - - Class - LineGraphic - ID - 67 - Points - - {548.5, 129} - {548.5, 157} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - TailArrow - 0 - TailScale - 0.5 - - - - - Bounds - {{496, 157}, {100, 26}} - Class - ShapedGraphic - ID - 66 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 ADDR_EXPR} - VerticalPad - 0 - - - - Bounds - {{519.5, 88}, {53, 41}} - Class - ShapedGraphic - ID - 65 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 next\ -prev\ -stmt} - VerticalPad - 0 - - - - Class - LineGraphic - ID - 64 - Points - - {454.5, 112} - {519.5, 112} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - TailArrow - 0 - TailScale - 0.5 - - - - - Class - LineGraphic - Head - - ID - 62 - - ID - 63 - Points - - {428, 129} - {428, 161} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - TailArrow - 0 - TailScale - 0.5 - - - Tail - - ID - 61 - - - - Bounds - {{378, 161}, {100, 26}} - Class - ShapedGraphic - ID - 62 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 BIND_EXPR} - VerticalPad - 0 - - - - Bounds - {{401.5, 88}, {53, 41}} - Class - ShapedGraphic - ID - 61 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006299} - {0.50711799, -0.224086} - {0.50711799, 0.26717901} - {-0.27430999, -0.47402799} - {0.27978, -0.47847801} - {0.29393801, 0.54304397} - {-0.28623199, 0.55380398} - - Shape - Rectangle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 next\ -prev\ -stmt} - VerticalPad - 0 - - - - Class - LineGraphic - ID - 60 - Points - - {336.5, 112} - {401.5, 112} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - TailArrow - 0 - TailScale - 0.5 - - - - - Class - LineGraphic ID 59 Points @@ -912,7 +399,7 @@ {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc -\f0\fs24 \cf0 DECL_EXPR} +\f0\fs24 \cf0 RETURN_EXPR} VerticalPad 0 @@ -1222,7 +709,7 @@ {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc -\f0\fs24 \cf0 DECL_EXPR} +\f0\fs24 \cf0 MODIFY_EXPR} VerticalPad 0 @@ -1271,7 +758,7 @@ {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc -\f0\fs24 \cf0 DECL_EXPR} +\f0\fs24 \cf0 MODIFY_EXPR} VerticalPad 0 @@ -1497,7 +984,7 @@ GuidesVisible YES HPages - 2 + 1 ImageCounter 1 KeepToScale @@ -1537,7 +1024,7 @@ MasterSheets ModificationDate - 2011-12-28 09:22:13 +0000 + 2011-12-29 06:52:40 +0000 Modifier Nobuyasu Oshiro NotesVisible @@ -1632,7 +1119,7 @@ SidebarWidth 120 VisibleRegion - {{126, 0}, {558, 783}} + {{0, 0}, {558, 783}} Zoom 1 ZoomValues