Mercurial > hg > Papers > 2012 > nobu-thesis

changeset 26:6b5277a9bc0f draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add cbc.md
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 27 Feb 2012 02:02:56 +0900
parents 9aab71420606
children 45369b0cbcd1
files presen/cbc.md
diffstat 1 files changed, 430 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /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の <br> 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
+
+<ul>
+<li>Continuation based C</li>
+<li>CbC の実装(修正点)</li>
+<ol>
+<li>Tail Call Elimination の強制付与</li>
+</ol>
+<li>性能評価</li>
+<li>まとめ</li>
+</ul>
+
+
+---
+
+
+Continuation based C
+========
+コードセグメント単位での記述と継続を基本としたプログラミング言語
+---------
+
+<li>コーセグメント:CbC におけるプログラムの基本単位</li>
+<ul>
+<li>C の関数よりも細かな単位</li>
+<li>C から関数コールとループ制御が取り除かれた形</li>
+<li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li>
+</ul>
+
+<table width=100% >
+    <td style="margin-left:auto; margin-right: auto; text-align: center;">
+      <img src="./pix/codesegment.png" style="height:14em;">
+    </td>
+</table>
+
+
+---
+
+Continuation based C
+========
+
+継続:現在の処理を実行していく為の情報
+---------
+<table width=100% border=1>
+  <tr>
+    <td><h2>Cの継続</h2></td>
+    <td><h2>CbCの継続(軽量継続)</h2></td>
+  </tr>
+  <tr>
+    <td>
+      <ul>
+	<li>続く命令のアドレス</li>
+	<li>命令に必要なデータ</li>
+	<li>スタックに積まれている値(環境)</li>
+      </ul>
+    </td>
+    <td>
+      <ul>
+	<li>Cの継続から環境を除外</li>
+	<li>続く命令とその命令に必要なデータのみ</li>
+      </ul>
+    </td>
+  </tr>
+  <t>
+    <td style="margin-left:auto; margin-right: auto; text-align: center;">
+      <img class="scale" src="./pix/func_call.png" style="height: 18em;">
+    </td>
+    <td style="margin-left:auto; margin-right: auto; text-align: center;">
+      <img class="scale" src="./pix/cs_stack.png" style="height: 18em;">
+    </td>
+  </tr>
+</table>
+
+
+
+---
+
+Continuation based C
+========
+<table width=100% border=1>
+<caption>階乗を求める CbC のプログラム</caption>
+<td>
+<pre>
+    \_\_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);
+    }
+</pre>
+</td>
+<td>
+<li>__code によるコードセグメントの宣言</li>
+<li>goto によるコードセグメントへの継続</li>
+</td>
+</table>
+
+---
+
+
+CbC の実装
+========
+
+---
+
+
+CbC の実装 : Tail Call Elimination
+========
+<li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li>
+
+Tail Call Elimination
+---------
+<li>関数呼び出しを call ではなく jmp 命令で行う最適化</li>
+<li>例えば, 如何の場合関数 f は jmp 命令で処理が移る</li>
+
+<table width=100%>
+  <tr>
+    <td width=50%>
+<pre>
+  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;
+  }
+      </pre>
+    </td>
+    <td>
+      <img src="./pix/continuation.png" style="height:80%;">
+    </td>
+  </tr>
+</table>
+
+
+---
+
+
+CbC の実装: Tail Call Elimination
+========
+Tail Call Elimination の条件
+---------
+<ul>
+  <li>caller側とcallee側の戻値の型の一致している。</li>
+  <li>関数呼び出しがリターン直前に行われている。</li>
+  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+  <li>引数の並びのコピーに上書きがない。</li>
+</ul>
+
+条件回避の為の実装
+---------
+<ul>
+  <li>コードセグメントの型はvoid型で統一する。</li>
+  <li>gotoの直後に自動で return を置く。</li>
+  <li>スタックサイズは固定にする。</li>
+  <li>引数は一旦、一時変数にコピーする。</li>
+</ul>
+
+---
+
+
+CbC の実装: Tail Call Elimination
+========
+Tail Call Elimination の条件をチェックする expand_call関数
+---------
+- 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。
+- この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
+必要があった。
+- しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。
+- 専用関数がなくなったことでより今後より楽なアップデートを行なっていくことができるようになった。
+
+
+---
+
+
+
+
+
+性能評価
+========
+
+<li>conv1:演算と継続を交互に繰り返すプログラム</li>
+
+<table width=100%>
+  <caption>各コンパイラにより生成されたコードの速度比較</caption>
+  <td style="margin:auto; text-align:center;">
+    <img src="./pix/conv1_for_resume.png" style="height:15em"> 
+  </td>
+  <td>
+    <img src="./pix/conv1_mac_for_presen.png" style="height:15em"> 
+  </td>
+</table>
+
+<li>引数 2,3 の結果はほぼ同じだが, 引数 1 の結果には差がでている.</li>
+
+引数 1 の時のプログラム
+---------
+<li>引数が 1 の時は, 関数ポインタとして構造体に保存していたコードセグメントへと継続を行なっている</li>
+
+
+---
+
+
+
+最適化の比較
+========
+<table width=100% border=1>
+  <caption>それぞれの最適化にかかったプログラムの挙動</caption>
+  <tr>
+    <td>最適化</td>
+    <td style="text-align:center;">状態遷移</td>
+  </tr>
+  <tr>
+    <td>最適化無し</td>
+    <td style="margin:auto; text-align:center;">
+      <img src="./pix/state_conv1_noopt.png"> 
+  </td>
+  <tr>
+    <td>GCC-4.5<br>の最適化</td>
+    <td style="margin:auto; text-align:center;">
+    <img src="./pix/state_conv1_45.png"> 
+  </td>
+  </tr>
+  <tr>
+    <td>GCC-4.6<br>の最適化</td>
+    <td style="margin:auto; text-align:center;">
+      <img src="./pix/state_conv1_46.png"> 
+    </td>
+  </tr>
+</table>
+
+---
+
+最適化の比較
+========
+<table width=100% border=1>
+  <caption>それぞれの最適化により吐かれたアセンブラコード</caption>
+  <tr>
+    <td width=50% style="text-align:center;">CbC-GCC-4.5</td>
+    <td width=50% style="text-align:center;">CbC-GCC-4.6</td>
+  </tr>
+
+  <tr>
+    <td>
+      <pre>
+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
+      </pre>
+    </td>
+    <td>
+      <pre>
+main:
+	movq    $f_g1, main_stack+2000(%rip)
+	:
+	call    g_h1
+	:
+	movq    24(%rax), %rdx
+	:
+	jmp     *%rdx
+	:
+	movq    24(%rax), %rdx
+	:
+	jmp     *%rdx
+      </pre>
+    </td>
+  </tr>
+<!--
+  <tr> 
+    <td></td>  
+    <td></td>  
+  </tr>
+-->
+
+</table>
+<li>関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる</li>
+<!--
+<li>保存していた関数ポインタへの継続はインライン展開は行われない</li>
+-->
+
+---
+
+
+
+GCC の最適化について
+========
+- インライン展開の最適化がより良くなっていることができた.
+- また, GCC では新たな最適化もアップデートが行われていく.
+
+
+---
+
+
+
+
+まとめ
+========
+- 今回 CbC-GCC を GCC-4.6 へとアップデートを行った.
+- アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った.
+- アップデートにかけたことで, より良い最適化がかかることを確認できた.
+- GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる.
+
+
+今後の課題
+---------
+- LLVM ベースの CbC コンパイラの開発
+- google Go 言語への実装の検討
+
+---
+
+
+CbC 引数渡し
+========
+<li>CbC では引数渡しにできるだけレジスタを用いるようにしている.</li>
+<table border=1 width=100%>
+  <caption><small>fastcall属性有・無の実行速度</small></caption>
+  <tr>
+    <td width=50% style="text-align:center;">fastcall無し</td>
+  </tr>
+  <tr>
+  <td style="margin:auto; text-align:center;">
+      <img src="./pix/linux_conv_nofastcall.png" style="height:15em;">
+    </td>
+  </tr>
+  <tr>
+    <td width=50% style="text-align:center;">fastcall有り</td>
+  <tr>
+    <td>
+      <img src="./pix/linux_conv_fastcall.png" style="height:15em;">
+    </td>
+  </tr>
+</table>
+
+
+---
+
+
+GCC でのコンパイルの仕組み
+========
+
+<table width=100%>
+  <td style="margin:auto; text-align:center;">
+    <img src="./pix/ir.png" style="height:15em">
+  </td>
+</table>
+
+<li>CbC の実装では Parser と RTL の生成部分に手が加えられている。</li>
+
+---
+
+
+
+
+
+
+
+
+
+
+
+
+