# HG changeset patch # User Nobuyasu Oshiro # Date 1330275817 -32400 # Node ID 45369b0cbcd1b7fcd8b30b9b5ce5f1dad8ee3242 # Parent 6b5277a9bc0fbdc6a7acf1180adcbca019c2e139 add some files diff -r 6b5277a9bc0f -r 45369b0cbcd1 presen/presen.css --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/presen.css Mon Feb 27 02:03:37 2012 +0900 @@ -0,0 +1,3 @@ +.incremental { + +} \ No newline at end of file diff -r 6b5277a9bc0f -r 45369b0cbcd1 presen/presentation.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/presentation.html Mon Feb 27 02:03:37 2012 +0900 @@ -0,0 +1,1042 @@ + + + + + + + Continuation based Cの <br> GCC 4.6による実装 + + + + + + + + + + + + + + + + + + + +
+
+
+
+
+
+ + +
+
+
+ +

Continuation based Cの
GCC 4.6による実装

+ + +
+
+

Presenter Notes

+
+ +
+
+
+ + + + +
+
+
+ + +
+
+
+ +

はじめに

+ + +

plop

+
    +
  • 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。
    • +
  • コードセグメントは C の関数よりも細かな単位で、状態を表すことができる。
    • +
  • その為 CbC では状態遷移記述を行うことが出来、状態探索といったモデル検査等に使えると考えている。
    • +
+ +
+
+

Presenter Notes

+
+ +
+
+
+ + + + +
+
+
+ + +
+
+
+ +

研究の目的

+ + +
    +
  • CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。
    • +
  • しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。
    • +
  • また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。
    • +
  • 本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に実装の修正を行った。
    • +
+ +
+
+

Presenter Notes

+
+ +
+
+
+ + + + +
+
+
+ + +
+
+
+ +

発表内容

+ + +
    +
  • Continuation based C
    • +
  • CbC の実装(修正点)
    • +
      +
    1. Tail Call Elimination の強制付与
      2. +
    +
  • 性能評価
    • +
  • まとめ
    • +
+ +
+
+

Presenter Notes

+
+ +
+
+
+ + + + +
+
+
+ + +
+
+
+ +

Continuation based C

+ + +

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

+
  • コーセグメント:CbC におけるプログラムの基本単位
    • + +
      +
    • C の関数よりも細かな単位
      • +
    • C から関数コールとループ制御が取り除かれた形
      • +
    • コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。
      • +
    + + + +
    + +
    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    Continuation based C

    + + +

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

    +

    + + + + + + + + + + + + +

    Cの継続

    CbCの継続(軽量継続)

    +
      +
    • 続く命令のアドレス
      • +
    • 命令に必要なデータ
      • +
    • スタックに積まれている値(環境)
      • +
    +     		+
      +
    • Cの継続から環境を除外
      • +
    • 続く命令とその命令に必要なデータのみ
      • +
    +
    + + + +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    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(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 によるコードセグメントの宣言
    • +
  • goto によるコードセグメントへの継続
    • +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    CbC の実装

    + + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    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;
+  }
+
    +     		+ +
    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    CbC の実装: Tail Call Elimination

    + + +

    Tail Call Elimination の条件

    +

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

    +

    条件回避の為の実装

    +

      +
    • コードセグメントの型はvoid型で統一する。
      • +
    • gotoの直後に自動で return を置く。
      • +
    • スタックサイズは固定にする。
      • +
    • 引数は一旦、一時変数にコピーする。
      • +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    CbC の実装

    + + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    性能評価

    + + +
  • conv1:演算と継続を交互に繰り返すプログラム
    • + + + + + +
    各コンパイラにより生成されたコードの速度比較
    + + + +
    + +
  • 引数 2,3 の結果はほぼ同じだが, 引数 1 の結果には差がでている.
    • + +

    引数 1 の時のプログラム

    +

  • 引数が 1 の時は, 関数ポインタとして構造体に保存していたコードセグメントへと継続を行なっている

    • + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    最適化の比較

    + + +

    + + + + + + + + + + + + + + + + +
    それぞれの最適化にかかったプログラムの挙動
    最適化状態遷移
    最適化無し + +
    GCC-4.5
    の最適化    		 + +
    GCC-4.6
    の最適化    		 + +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    最適化の比較

    + + +

    + + + + +

    +

    + + + +

    +

    それぞれの最適化により吐かれたアセンブラコード
    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
+
    +
    +

  • 関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる
    • +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    GCC の最適化について

    + + +
      +
    • インライン展開の最適化がより良くなっていることができた.
      • +
    • また, GCC では新たな最適化もアップデートが行われていく.
      • +
    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    まとめ

    + + +
      +
    • 今回 CbC-GCC を GCC-4.6 へとアップデートを行った.
      • +
    • アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った.
      • +
    • アップデートにかけたことで, より良い最適化がかかることを確認できた.
      • +
    • GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる.
      • +
    +

    今後の課題

    +
      +
    • LLVM ベースの CbC コンパイラの開発
      • +
    • google Go 言語への実装の検討
      • +
    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    CbC 引数渡し

    + + +

  • CbC では引数渡しにできるだけレジスタを用いるようにしている.
    • + + + + + + + + + + + + + +
    fastcall属性有・無の実行速度
    fastcall無し
    + +
    fastcall有り
    + +

    + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + +

    GCC でのコンパイルの仕組み

    + + +
    + +
    + +
    + +
  • CbC の実装では Parser と RTL の生成部分に手が加えられている。
    • + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + + + +
    +
    +
    + + +
    +
    +
    + + +
    +
    +

    Presenter Notes

    +
    + +
    +
    +
    + + +
    +
    +
    + +
    +
    + + + + + + + \ No newline at end of file