# HG changeset patch # User Nobuyasu Oshiro # Date 1330275776 -32400 # Node ID 6b5277a9bc0fbdc6a7acf1180adcbca019c2e139 # Parent 9aab71420606f0367847fa1b9bc7108bea3f9fa8 add cbc.md diff -r 9aab71420606 -r 6b5277a9bc0f presen/cbc.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/cbc.md Mon Feb 27 02:02:56 2012 +0900 @@ -0,0 +1,430 @@ +Continuation based Cの
GCC 4.6による実装 +========= + +--- + +はじめに +--------- + +.notes: plop + +- 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。 +- コードセグメントは C の関数よりも細かな単位で、状態を表すことができる。 +- その為 CbC では状態遷移記述を行うことが出来、状態探索といったモデル検査等に使えると考えている。 + +--- + +研究の目的 +--------- + +- CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。 +- しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。 +- また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。 +- 本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に実装の修正を行った。 + +--- + +発表内容 +======== + +.fx: foo bar + + + + +--- + + +Continuation based C +======== +コードセグメント単位での記述と継続を基本としたプログラミング言語 +--------- + +
  • コーセグメント:CbC におけるプログラムの基本単位
    • + + + + +
    + +
    + + +--- + +Continuation based C +======== + +継続:現在の処理を実行していく為の情報 +--------- + + + + + + + + + + + + + +

    Cの継続

    CbCの継続(軽量継続)

    +
      +
    • 続く命令のアドレス
      • +
    • 命令に必要なデータ
      • +
    • スタックに積まれている値(環境)
      • +
    +     		+
      +
    • Cの継続から環境を除外
      • +
    • 続く命令とその命令に必要なデータのみ
      • +
    +
    + + + +
    + + + +--- + +Continuation based C +======== + + + + +
    階乗を求める CbC のプログラム
    +
    +    \_\_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 によるコードセグメントへの継続
    • +
    + +--- + + +CbC の実装 +======== + +--- + + +CbC の実装 : Tail Call Elimination +======== +
  • CbC-GCC の軽量継続は最適化の1つ, Tail Call Celimination(末尾除去)により実装されている.
    • + +Tail Call Elimination +--------- +
  • 関数呼び出しを call ではなく jmp 命令で行う最適化
    • +
  • 例えば, 如何の場合関数 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;
+  }
+
    +     		+ +
    + + +--- + + +CbC の実装: Tail Call Elimination +======== +Tail Call Elimination の条件 +--------- + + +条件回避の為の実装 +--------- + + +--- + + +CbC の実装: Tail Call Elimination +======== +Tail Call Elimination の条件をチェックする expand_call関数 +--------- +- 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。 +- この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく +必要があった。 +- しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。 +- 専用関数がなくなったことでより今後より楽なアップデートを行なっていくことができるようになった。 + + +--- + + + + + +性能評価 +======== + +
  • conv1:演算と継続を交互に繰り返すプログラム
    • + + + + + +
    各コンパイラにより生成されたコードの速度比較
    + + + +
    + +
  • 引数 2,3 の結果はほぼ同じだが, 引数 1 の結果には差がでている.
    • + +引数 1 の時のプログラム +--------- +
  • 引数が 1 の時は, 関数ポインタとして構造体に保存していたコードセグメントへと継続を行なっている
    • + + +--- + + + +最適化の比較 +======== + + + + + + + + + + + + + + + + + +
    それぞれの最適化にかかったプログラムの挙動
    最適化状態遷移
    最適化無し + +
    GCC-4.5
    の最適化    		 + +
    GCC-4.6
    の最適化    		 + +
    + +--- + +最適化の比較 +======== + + + + + + + + + + + + + +
    それぞれの最適化により吐かれたアセンブラコード
    CbC-GCC-4.5CbC-GCC-4.6
    + 
    +main:
+	call    f
+	:
+	jmp     f_g0
+	:
+	movq    $f_g1, -24(%rdx)
+	addl    $10, %edi
+	movq    $g_h1, -48(%rdx)
+	jmp     g_h1
+	:
+	movq    24(%rsi), %rdx
+	movq    %rax, %rsi
+	:
+	jmp     *%rdx
+	:
+	movq    24(%rsi), %rdx
+	:
+	jmp     *%rdx
+
    +     		+ 
    +main:
+	movq    $f_g1, main_stack+2000(%rip)
+	:
+	call    g_h1
+	:
+	movq    24(%rax), %rdx
+	:
+	jmp     *%rdx
+	:
+	movq    24(%rax), %rdx
+	:
+	jmp     *%rdx
+
    +
    +
  • 関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる
    • + + +--- + + + +GCC の最適化について +======== +- インライン展開の最適化がより良くなっていることができた. +- また, GCC では新たな最適化もアップデートが行われていく. + + +--- + + + + +まとめ +======== +- 今回 CbC-GCC を GCC-4.6 へとアップデートを行った. +- アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った. +- アップデートにかけたことで, より良い最適化がかかることを確認できた. +- GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる. + + +今後の課題 +--------- +- LLVM ベースの CbC コンパイラの開発 +- google Go 言語への実装の検討 + +--- + + +CbC 引数渡し +======== +
  • CbC では引数渡しにできるだけレジスタを用いるようにしている.
    • + + + + + + + + + + + + + +
    fastcall属性有・無の実行速度
    fastcall無し
    + +
    fastcall有り
    + +
    + + +--- + + +GCC でのコンパイルの仕組み +======== + + + +
    + +
    + +
  • CbC の実装では Parser と RTL の生成部分に手が加えられている。
    • + +--- + + + + + + + + + + + + +