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>
<li>call ではなく jmp で処理を移る</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>例えば、以下の場合関数 g は jmp 命令で関数 f へと処理が移る</li>

<table width=100% border=1>
  <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 の結果はほぼ同じ</li>
<li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li>

---


最適化の比較
========
<table width=100% border=1>
  <caption>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</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>

---


GCC の最適化
========
- 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</l>
- これは、最適化の 1 つ『インライン展開』により各コードセグメントの計算がまとめて行われ、
継続する数を減らされている為。
- GCC-4.5 でもインライン展開はされていたが、GCC-4.6 はより良い最適化がかけられている。


---



アップデートに合わせる有用性
========
- 今回の『インライン展開』のように GCC の最適化は日々改良されていく。
- また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。
- それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。



---



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


今後の課題
---------
- LLVM ベースの CbC コンパイラの開発
- google Go 言語への実装の検討

---

conv1 プログラム
========
- conv1 プログラムでは計算と継続を交互に繰り返し行なう。
- しかし状態のいくつかへは関数ポインタとして保存させておき継続を行う。
<pre>
__code g(int i,stack sp) { // Caller
    struct f_g0_interface *c = 
        (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

    c->ret = g_h1;
    c->i_ = i;

    goto h(i+3,sp);
}

__code h(int i,stack sp) {
    struct f_g0_interface *c = (struct f_g0_interface *)sp;
    goto (c->ret)(i+4,sp);
}
</pre>

- 関数ポインタへの継続はインライン展開されない。

---


CbC の実装: 環境付き継続
========
- 環境付き継続: C との互換を取るための機能。継続を行った C の関数に戻ることができる。 
- _CbC_return、 _CbC_environment キーワードを使うことで使える。
- 以下の使い方の場合、戻値 1 を返す。
<pre>
__code c1(__code ret(int,void *),void *env) {
    goto ret(1,env);
}
int main() {
    goto c1(__return, __environment);
}
</pre>

- 今回この環境付き継続をスレッドセーフの実装へと修正した。


---


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>

---


最適化の比較
========
<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>
-->

---