Continuation based C

- +

階乗を計算する CbC プログラム
-__code print_factorial(int prod) -{ - printf("factorial = %d\n",prod); - exit(0); + __code code1(int n,__code(exit_code)(int,void ),void exit_env){ + printf("code1 : code entry1\n"); + goto exit_code(n,exit_env); +} + +int caller(){ + printf("caller : main1 entry\n"); + __code (__ret)(int, void ) = __return; + struct __CbC_env __env = __environment; + goto code1(1, __ret, __env); + return 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); -} +int main(){ + int n; + n = caller(); + printf("return = %d\n",n); + return 0; +}	code segment は型に __code を使うことで宣言できる. @@ -184,7 +188,7 @@ LLVM はコンパイラ, ツールチェーン技術などを開発するプロジェクトの名称. 単に LLVM といった場合には LLVM Core を指し, これはコンパイラの基板となるライブラリの集合. - LLVM IR, LLVM BitCode と呼ばれる独自の言語を持つ. + LLVM IR と呼ばれる独自の言語を持つ. clang はバックエンドに LLVM を利用する C/C++/Objective-C コンパイラ. @@ -238,6 +242,7 @@

階乗を計算する CbC プログラム

CbC プログラムの例

-__code print_factorial(int prod)
-{
-  printf("factorial = %d\n",prod);
-  exit(0);
+__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
+  printf("code1 : code entry1\n");
+  goto exit_code(n,exit_env);
+}
+
+int caller(){
+  printf("caller : main1 entry\n");
+  __code (*__ret)(int, void *) = __return;
+  struct __CbC_env *__env = __environment;
+  goto code1(1, __ret, __env);
+  return 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);
-}

+int main(){ + int n; + n = caller(); + printf("return = %d\n",n); + return 0; +}

code segment は型に __code を使うことで宣言できる. @@ -184,7 +188,7 @@
- LLVM はコンパイラ, ツールチェーン技術などを開発するプロジェクトの名称.
- 単に LLVM といった場合には LLVM Core を指し, これはコンパイラの基板となるライブラリの集合. -
- LLVM IR, LLVM BitCode と呼ばれる独自の言語を持つ. +
- LLVM IR と呼ばれる独自の言語を持つ.
- clang はバックエンドに LLVM を利用する C/C++/Objective-C コンパイラ.
@@ -238,6 +242,7 @@

内部表現には手を加えていない.

CbC コンパイラの実装に深く関わる内部表現である AST についてさらに触れる.

CbC の文に対してこの木が正しく生成されるようにソースコードに手を加えていく.

CbC コンパイラの実装

clang/LLVM 上での CbC コンパイラの実装

__code 型の追加

goto syntax の追加 @@ -321,7 +325,7 @@

goto を用いて継続を行う構文に対応させる.
ここでは関数呼び出しを生成しておき, 後で Tail Call Elimination によって継続に直す. -
以下は goto をパースする箇所. C の goto 出ない場合に継続の構文と判断する. +
以下は goto をパースする箇所. C の goto でない場合に継続の構文と判断する.

@@ -351,7 +355,7 @@

実際のコード -

clnag内部で扱われるコード +

clnag内部扱う AST に対応するコード

@@ -446,41 +450,42 @@
       
 	環境付き継続
 	
-	  
-	  
+	  

 	
 	  __return, __environment という二つのキーワードを利用して実現.
 	  
C の関数から code segment に継続した後, C 元の関数を呼び出した関数に戻るための機能.
-	  
以下のコードの場合, A から継続した B は環境付き継続を用いて A の呼び出し元である main に戻る.
+	  
以下のコードの場合, caller から継続した code1 は環境付き継続を用いて caller の呼び出し元である main に戻る.
+	  
GCC 上に実装した CbC コンパイラは nested function を使用していたが clang はこの構文を受け付けない.
+	  
setjmp/longjmp を用いて実装.
 	
-	

 	    
-	      -__code B(int retval,__code(*ret)(int,void *),void *env){
-  goto ret(n, env);
+	      __code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
+  printf("code1 : code entry1\n");
+  goto exit_code(n,exit_env);
 }
 
-int A(){
-  goto B(1, __return, __environment);
+int caller(){
+  printf("caller : main1 entry\n");
+  __code (*__ret)(int, void *) = __return;
+  struct __CbC_env *__env = __environment;
+  goto code1(1, __ret, __env);
   return 0;
 }
 
 int main(){
-  int retval;
-  retval = A(); // retval should be 1.
-}	      
+  int n;
+  n = caller();
+  printf("return = %d\n",n);
+  return 0;
+}	      
 	  
 	
-	
-	  GCC 上に実装した CbC コンパイラは nested function を使用していたが clang はこの構文を受け付けない.
-	  
setjmp/longjmp を用いて実装.
-	
       
 
       
 	環境付き継続
-	自動生成されたコード
-	
+	自動生成する AST に対応する擬似コード
+	

 	  
 	    
 	      @@ -494,50 +499,58 @@
   goto ret(n, env);
 }
 
-__code return1 (int retval, void* env){
-  *(int*)((struct CbC_env *)(env))->ret_p = retcal;
-  longjmp((int*)(((struct CbC_env *)env)->env),1);
+__code caller..ret0 (int retval, void* env){
+  *(int*)((struct CbC_env *)(env))->ret_p = retval;
+  longjmp((int*)(((struct CbC_env *)env)->env),1);
 }
 
+__code code1(int n, __code (*exit_code)(int, void *), void *exit_env) {
+  printf("code1 : code entry1\n");
+  {
+    exit_code(n, exit_env);
+    return;
+  }
+}
 	      
 	    
 	      -int A(){
-   goto B(1,
-       ({
-         __code (*__CbC_return)();
-__CbC_return = return1;
-__CbC_return;
-       }),
-       ({
-         struct CbC_env __CbC_environment;
-         jmp_buf env;
-         int retval;
-         __CbC_environment.ret_p = &retval;
-         __CbC_environment.env = &env;
-         if (setjmp(__CbC_environment.env)){
-  return retval;
-         }
-         &__CbC_environment;
-       })
-     );
+int caller() {
+  printf("caller : main1 entry\n");
+  __code (*__ret)(int, void *) = ({
+    __code (*__CbC_return)(int, void *);
+    __CbC_return = caller..ret0;
+    __CbC_return;
+  });
+
+  struct __CbC_env *__env = ({
+    struct __CbC_env __CbC_environment;
+    int retval;
+    jmp_buf env_buf;
+    __CbC_environment.ret_p = &retval;
+    __CbC_environment.env = env_buf;
+    if (setjmp(__CbC_environment.env)) {
+      return retval;
+    }
+    &__CbC_environment;
+  });
+
+  {
+    code1(1, __ret, __env);
+  }
   return 0;
 }
-	      
+int main() {
+  int n;
+  n = caller();
+  printf("return = %d\n", n);
+  return 0;
+}	      
 	  
 	
       
 
       
-	評価
-	
-	  出力するアセンブリコードの確認
-	  
Micro-C, GCC, LLVM/clang のそれぞれでコンパイルして得られるプログラムの実行速度の比較
-	
-      
-
-      
-	アセンブリコード
+	アセンブリコードの確認
 	
 	  
 	    コンパイル前
@@ -547,15 +560,14 @@
 	    
 	       
-__code factorial(int x)
+__code caller(int x)
 {
-  goto factorial0(1, x);
+  goto code1(1, x);
 }
 	      
 	    
 	      -
-_factorial:                             ## @factorial
+_caller:                             ## @factorial
         .cfi_startproc
 ## BB#0:                                ## %entry
         subq    $24, %rsp
@@ -566,26 +578,36 @@
         movl    %eax, %edi
         movl    20(%rsp), %esi          ## 4-byte Reload
         addq    $24, %rsp
-        jmp     _factorial0             ## TAILCALL
+        jmp     _code1             ## TAILCALL
         .cfi_endproc
 	      
 	  
 	
 	
-	  factorial0 が jmp 命令で呼び出されている.
+	  
code1 が jmp 命令で呼び出されている.
 	  
Tail Call Elimination がきちんと強制されている.
+	  
jmp になっていない場合には警告が出る.
 	
       
 
       
 	実行速度
-	conv1というプログラムを使用した. 引数 1 の時には CbC の継続を使用, 引数 2, 3 の時には Micro-C のための最適化が手動で施されたコードを使用するようになっている.
+	
+	  conv1というプログラムを使用. 
+	    
+	      通常の関数呼び出しを行うコードを継続で実装したプログラム. 
+	    
+	  
引数に応じて純粋に変換した場合とスタックを削り最適化を行った場合のコードどちらを実行するかを選択. 
+	    
+	      引数 1 の時には CbC の継続を使用, 引数 2, 3 の時には Micro-C のための最適化が手動で施されたコードを使用する.
+	    
+	
 	
 	  
 	    
-	    引数 1
-	    引数 2
-	    引数 3
+	    継続への純粋な変換
+	    最適化を行ったコード A
+	    最適化を行ったコード B
 	  
 	  
 	    Micro-C
@@ -623,18 +645,35 @@
       
 	まとめ
 	
-	  clang/LLVM 上で CbC コンパイラを実装した.
-	  
環境付き継続を setjmp/longjmp を用いて実装した. 
+	  
clang/LLVM 上で CbC コンパイラを実装した.
+	  

+	  GCC 上に実装した CbC コンパイラとの違い.
 	    
+	      nested function がないので環境付き継続を setjmp/longjmp を用いて実装した. 
 	      
以後 nested function をサポートしないコンパイラ上に CbC コンパイラを実装する際, 同様にして実装できる.
+	      
GCC 版では最適化レベルが 2 以上でないと Tail Call Elimination を正しく強制できないが, LLVM/clang 版では最適化レベルが 0 でも正しく強制できる.
 	    
 	
-	

+      
+
+      
 	今後の課題
 	
 	  インラインアセンブリを用いた環境付き継続の実装.
+	    
+	      アーキテクチャが限定されるが命令数がかなり少なくなる.
+	      
対応していないアーキテクチャ用に setjmp/longjmp を残す.
+	    
 	  
data segment の設計及び実装.
-	  
CbC による例題の作成.
+	    
+	      code segment の処理対象となるデータの単位.
+	      
並列実行時の待ちの記述が処理と別になる.
+	      
code segment 間のデータのやりとりの記述が容易になる.
+	    
+	  
CbC によるプログラムの作成
+	    
+	      並列プログラミングフレーム Cerium.
+

研究背景

研究目的

Continuation based C

CbC コンパイラの実装

clang/LLVM 上での CbC コンパイラの実装

環境付き継続

環境付き継続

評価

アセンブリコード

アセンブリコードの確認

実行速度

まとめ

今後の課題