階乗を求めるCbCのプログラム
+ __code print_factorial(int prod) { printf("factorial = %d\n",prod); exit(0); @@ -215,6 +217,7 @@	+ __code factorial(int x) { goto factorial0(1, x); } @@ -229,9 +232,11 @@

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

gotoシンタックスの追加

最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。

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

+ - +

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

+ -

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

- - - - - - - - - - - - - - - - - - - - -

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

+-->

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

Tail Call Elimination(TCE):末尾除去

末尾除去:Tail Call Elimination(TCE)

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

以下のソースの場合関数a から関数b へ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;
+}
+	    
+

@@ -680,24 +695,28 @@

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

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

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

expand_call関数

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

具体的な実装
具体的な実装内容

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

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

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

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

CbCの実装

シンタックスの追加
末尾除去によるコードセグメントへjmp命令での処理の移り

この2つがGCCにおけるCbC実装の基本の部分となる。

ここからはCbCの機能の拡張になる。

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を使用)
x86_64	6	8	8

+ +

CbCの実装:環境付き継続

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

CbCの実装:環境付き継続

実際には以下のコードを生成している。

- -

-
+	生成しているコードと生成する為のコード
+	
+	  
+	    
+	    
+	  
+	  
+	    生成しているコード 生成する為のコード

+	   goto c1(__return, __environment);
 
 goto c1(({
@@ -920,18 +1016,10 @@
 	  _cbc_internal_return;
 	}), __environment);
 	  
-	  retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。
-	
-	上記のコードをGCC内で生成するのが次のソースとなる。
-      
-      
-
       
       
 	CbCの実装:環境付き継続
diff -r 48de60dd51d1 -r 9250ac87c2c7 presen/omni/cs_stack.graffle
--- a/presen/omni/cs_stack.graffle	Mon Jan 02 07:29:15 2012 +0900
+++ b/presen/omni/cs_stack.graffle	Tue Jan 03 14:03:13 2012 +0900
@@ -50,6 +50,93 @@
 	GraphicsList
 	
 		
+			Bounds
+			{{168.3125, 560.00012}, {58, 22}}
+			Class
+			ShapedGraphic
+			ID
+			76
+			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\fs28 \cf0 goto\
+(jmp)}
+				VerticalPad
+				0
+			
+		
+		
+			AllowLabelDrop
+			
+			Class
+			LineGraphic
+			ID
+			75
+			Points
+			
+				{176.4375, 590.00012}
+				{222.4375, 590.00012}
+			
+			Style
+			
+				stroke
+				
+					HeadArrow
+					FilledArrow
+					HeadScale
+					1.4285709857940674
+					TailArrow
+					0
+					TailScale
+					0.5
+				
+			
+		
+		
 			AllowLabelDrop
 			
 			Class
@@ -253,7 +340,7 @@
 		
 		
 			Bounds
-			{{264.5, 567}, {58, 22}}
+			{{265.625, 560}, {58, 22}}
 			Class
 			ShapedGraphic
 			ID
@@ -305,66 +392,8 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs28 \cf0 goto}
-				VerticalPad
-				0
-			
-		
-		
-			Bounds
-			{{167, 567}, {58, 22}}
-			Class
-			ShapedGraphic
-			ID
-			53
-			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\fs28 \cf0 goto}
+\f0\fs28 \cf0 goto\
+(jmp)}
 				VerticalPad
 				0
 			
@@ -661,33 +690,6 @@
 			
 		
 		
-			AllowLabelDrop
-			
-			Class
-			LineGraphic
-			ID
-			44
-			Points
-			
-				{174, 594}
-				{220, 594}
-			
-			Style
-			
-				stroke
-				
-					HeadArrow
-					FilledArrow
-					HeadScale
-					1.4285709857940674
-					TailArrow
-					0
-					TailScale
-					0.5
-				
-			
-		
-		
 			Class
 			LineGraphic
 			ID
@@ -839,7 +841,7 @@
 	MasterSheets
 	
 	ModificationDate
-	2011-12-28 16:28:41 +0000
+	2012-01-02 21:28:56 +0000
 	Modifier
 	Nobuyasu Oshiro
 	NotesVisible
diff -r 48de60dd51d1 -r 9250ac87c2c7 presen/pix/continuation.png
Binary file presen/pix/continuation.png has changed
diff -r 48de60dd51d1 -r 9250ac87c2c7 presen/pix/cs_stack.png
Binary file presen/pix/cs_stack.png has changed

目的と背景(1)

目的と背景(2)

Continuation based C

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

コードセグメント

Continuation Based C

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

Continuation based C

Continuation Based C (軽量継続)

CbCの継続(軽量継続)

Continuation based C

CbCの実装

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

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

gotoシンタックスの追加

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

gotoシンタックスの追加

CbCの実装:引数渡し

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

fastcall

CbCの実装:引数渡し

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

Tail Call Elimination(TCE):末尾除去

末尾除去:Tail Call Elimination(TCE)

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

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

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

CbCの実装

CbCの実装:引数渡し

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

fastcall

CbCの実装:引数渡し

CbCの実装:環境付き継続

CbCの実装:環境付き継続

実際には以下のコードを生成している。

CbCの実装:環境付き継続