- \_\_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); - } +

+\_\_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); +}

@@ -180,9 +194,9 @@ Tail Call Elimination の条件 ---------

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

@@ -206,11 +220,11 @@ - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく必要があった。 -実装の修正と修正による利点 +実装の修正とその利点 --------- - しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。 - 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。 -- また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが +- また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。 --- @@ -218,7 +232,7 @@ -性能評価 +GCC-4.5, GCC-4.6 の性能比較 ========

本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。

この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。

@@ -260,7 +274,7 @@

インライン展開の例

+ void func(){
   A;
   B;
@@ -273,7 +287,7 @@

+ int main() {
   A;
   B;
@@ -333,7 +347,7 @@
 ========
 - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
 - アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。
-- また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。
+- また、最適化の強制付与やといった実装の修正も行えた。
 - 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。
 
 
@@ -353,9 +367,6 @@

研究の背景と成果

研究目的

plop

状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する

組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース
現存する記述言語は状態遷移の記述に向いていない
スタックが状態を隠蔽するため、分割しにくい、検証が難しい
当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。
CbC のコンパイラは Micro-C 版と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。
しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。
コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。

- -

+ + + + +

+	+ +__code cs_a(int num) { + : + : + goto cs_b(); +} + +

@@ -229,37 +245,37 @@

-
階乗を求める CbC のプログラム
-
- __code print_factorial(int prod) - { - printf("factorial = %d\n",prod); - exit(0); - } - __code factorial0(int prod, int x) - { - if ( x >= 1) { - goto factorial0(prodx, 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); - } +
+
+__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); +}

__code によるコードセグメントの宣言
-
goto によるコードセグメントへの継続
-
call ではなく jmp で処理を移る
+
引数付きの goto でコードセグメントを呼び出すことができる
+
内部では call ではなく jmp 命令でコードセグメントの処理が遷移している

@@ -291,7 +307,7 @@

Gnu Compiler Collection (GCC)

GCC: オープンソースのコンパイル群

GCC: オープンソースのコンパイラ群

ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。

GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。

@@ -331,7 +347,7 @@

CbC の実装 : 軽量継続

CbC-GCC の軽量継続は最適化の1つ, Tail Call Celimination(末尾除去)により実装されている.

CbC-GCC の軽量継続は最適化の1つ, Tail Call Elimination(末尾除去)により実装されている.

Tail Call Elimination

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

例えば、以下の場合関数 g は jmp 命令で関数 f へと処理が移る

@@ -353,8 +369,7 @@ int main() { g(3,4); return 0; - } - + }

@@ -392,9 +407,9 @@

Tail Call Elimination の条件

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

条件回避の為の実装

@@ -439,11 +454,11 @@

この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく必要があった。

実装の修正と修正による利点

実装の修正とその利点

しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。
専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。
また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが
また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。

@@ -471,7 +486,7 @@

性能評価

GCC-4.5, GCC-4.6 の性能比較

本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。

@@ -538,7 +553,7 @@

インライン展開の例

+ void func(){
   A;
   B;
@@ -551,7 +566,7 @@

+ int main() {
   A;
   B;
@@ -682,7 +697,7 @@
             
 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
 アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。
-また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。
+また、最適化の強制付与やといった実装の修正も行えた。
 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。
 
 今後の課題
@@ -724,10 +739,7 @@

引数 0 は C の関数で書かれたプログラム

- -

引数 3 は引数 0 のプログラムをただ CbC に書き直したもの

@@ -1135,7 +1147,7 @@