Continuation based C の <br> GCC 4.6による実装
=========

---

研究目的
---------

.notes:

<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>
- 本研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。
- CbC のコンパイラは Micro-C 版 と GCC 版(以下 CbC-GCC) が開発されている。
- しかし, CbC-GCC はいくつかのバグがあり機能に修正の余地があった。
- また、GCC の最新の機能を利用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。

<h2>本研究では CbC-GCC のアップデートを行い、より良いコードを生成する CbC の処理系を開発した。</h2>

---

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

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

<table width=100%  border=1>
  <tr>
    <td style="margin-left:auto; margin-right: auto; text-align: center; width:50%" >
      <img src="./pix/codesegment.png" style="width:100%">
    </td>
    <td>
      <pre style="margin-left:5%">
__code cs_a(int num) {
   :
   :
   goto cs_b();
}
      </pre>
    </td>
  </tr>
</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 width=50%>
<pre style="margin-left:5%">
\_\_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>

---


Gnu Compiler Collection (GCC)
========
<li>GCC: オープンソースのコンパイラ群</li>
<li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li>
<li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li>
<table width=100%>
  <caption>GCC のアセンブラ言語出力までの流れ</caption>
  <td style="margin:auto; text-align:center;">
    <img src="./pix/ir.png" style="height:15em">
  </td>
</table>
<li>ソースコードはアセンブラに変換される間に 4 つのデータ構造に変換される。</li>
<li>この中でも CbC の実装では Parser と RTL の生成部分に手が加えられている。</li>

---


CbC の実装 : 軽量継続
========
<li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Elimination(末尾除去)</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 の実装: 末尾除去の強制
========
末尾除去の条件をチェックする関数
---------
- 関数が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。
- その関数を元に、『コードセグメントは末尾除去』にかける専用の関数を用意していた。
- しかしこの方法は、元になった関数が修正に合わせて専用の関数も修正を行う必要があった。

実装の修正とその利点
---------
- しかし, 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更。
- 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。
- また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。


---




GCC-4.5, GCC-4.6 の性能比較
========
<li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li>
<li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li>
<li>conv1: 加算と継続を交互に繰り返すプログラム</li>

<table width=100% border=1>
  <caption>各コンパイラにより生成されたプログラムの速度比較</caption>
  <tr>
  <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>
  </tr>
  <tr>
    <td style="text-align:center;">x86/Linux</td>
    <td style="text-align:center;">x86/OS X (10.7)</td>
  </tr>
</table>
<li>Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。</li>
<li>引数 2、3 は手動で最適化をかけている。</li>
<li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li>


---



GCC-4.6 の最適化
========
- GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。

インライン展開
---------
- 関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化

<table width=100% border=1>
<caption><h3>インライン展開の例</h3></caption>
<tr>
<td width=50%>
<pre style="margin-left:5%">
void func_b(){
  A;
  B;
}

void func_a() {
  func_b();
  func_b();
}
</pre>
</td>
<td>
<pre style="margin-left:5%">
void func_a() {
  A;
  B;
  A;
  B;
}
</pre>
</td>
</tr>
</table>
<li>func_b の呼び出しがなくなっている。</li>


---

<h1>最適化の比較</h1>
<table width=100% border=1>
  <caption><h3>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</h3></caption>
  <tr>
    <td width=30%>最適化なし</td>
    <td width=30%>GCC-4.5の最適化(-O2)</td>
    <td width=30%>GCC-4.6の最適化(-O2)</td>
  </tr>
  <tr>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_noopt.png" style="width:65%;"> 
    </td>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_45.png"  style="width:65%;"> 
    </td>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_46.png"  style="width:65%;"> 
    </td>
  </tr>
</table>

- 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。
- GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。


---

最新バージョンに合わせる有用性
========

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

---



まとめ
========
- 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
- アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。
- また、最適化の強制付与といった実装の修正も行えた。
- 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。


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

---


CbC
========
<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>
<li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
<li>現存する記述言語は状態遷移の記述に向いていない</li>
<li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
<li>以上の問題を解決する言語として CbC は提案されている。</li>

具体的な CbC の利用予定
---------
- モデル検査
- Cerium の実装

---

Tail Call Elimination
========
関数が Tail Call Elimination にかかる条件
---------
<ul>
  <li>関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。</li>
  <li>関数呼び出しがリターン直前に行われている。</li>
  <li>呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。</li>
  <li>引数の並びのコピーに上書きがない。</li>
</ul>

条件回避の為の CbC の実装内容
---------
<ul>
  <li>コードセグメントの型はvoid型で統一する。</li>
  <li>gotoの直後に自動で return を置く。</li>
  <li>スタックサイズは固定にする。</li>
  <li>引数は一旦、一時変数にコピーする。</li>
</ul>

---





jmp と call
========
<table width=100%>
<caption>インライン展開無しの conv1 プログラム実行結果</caption>
<td style="text-align:center;">
<img src="./pix/fno_inline.png">
</td>
</table>

---

conv1 プログラム
========
<li>性能評価で用いた conv1 プログラムの C 版</li>
<pre style="width:5%;" border=1>
f0(int i) {
    int k,j;
    k = 3+i;
    j = g0(i+3);
    return k+4+j;
}
g0(int i) {
    return h0(i+4)+i;
}
h0(int i) {
    return i+4;
}</pre>
<li>性能評価はこのプログラムを CbC へと書き換えて行なっている。</li>

---


CbC-GCC のアップデート手法
========

<ol>
<li>GCC のソースを入れるリポジトリを用意する。</li>
<li>GCC のリポジトリの中身を全て消し、新しい GCC を入れて新しいファイルは追加、消えたファイルは削除する。</li>
<li>コミット</li>
</ol>


CbC-GCC のリポジトリ
---------
<ol>
<li>GCC のソースから pull</li>
<li>merge を行う</li>
<li>衝突のあったファイルを手動でマージする</li>
<li>コミット</li>
</ol>

---





構文の追加
========
リカーシブタイプの宣言に使う"__rectype"
---------
- 関数宣言時、以下のように引数に自分自身を指す型を入れたい。
<pre>
\_\_code func(int, func*);
<pre>
- 上記の宣言ではエラーがでる。その為、以下のような宣言になる。
<pre>
\_\_code func(int, \_\_code (*)());
</pre>
- しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。
<pre>
\_\_code func(int, \_\_code (*)(int, \_\_code(*)(int, \_\_code(*)(int, ...))))
</pre>
- だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。
- そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。
<pre>
\_\_code func(int, rectype*);
</pre>


---


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>


---



引数の並びに上書きコピー
========
<li>以下の呼び出しを行うと、スタックの書き換えがおこる</li>
<pre>
void funcA(int a, int b) {
  funcB(b, a);
}
</pre>

<table width=100%>
<tr>
<td style="margin:auto; text-align:center;">
<img src="./pix/cs_prog.png">
</td>
</tr>
</table>


---

最適化の比較
========

<table width=100% border=1>
  <caption>各コンパイラにより生成されたコードの速度比較</caption>
  <tr>
  <td style="margin:auto; text-align:center;">
    <img src="./pix/O3_conv1_linux.png" style="height:15em"> 
  </td>
  <td>
    <img src="./pix/O3_conv1_mac.png" style="height:15em"> 
  </td>
  </tr>
  <tr>
    <td style="text-align:center;">x86/Linux</td>
    <td style="text-align:center;">x86/OS X (10.7)</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>
-->

---