Mercurial > hg > Papers > 2011 > nobu-prosym

--- a/presen/.#test.c	Wed Jan 04 17:16:44 2012 +0900
+++ b/presen/.#test.c	Wed Jan 04 23:41:05 2012 +0900
@@ -1,1 +1,1 @@
-aotokage@dimolto.cr.ie.u-ryukyu.ac.jp.37188
\ No newline at end of file
+aotokage@Nobuyasus-MacBook-Pro.local.88737
\ No newline at end of file
--- a/presen/index.html	Wed Jan 04 17:16:44 2012 +0900
+++ b/presen/index.html	Wed Jan 04 23:41:05 2012 +0900
@@ -107,9 +107,9 @@
       <!-- PAGE -->
       <div class="slide">
  	<h1>目的と背景(2)</h1>
-	<li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
-	<li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
-	<li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
+	<li>CbCのコンパイラは2001年に Micro-C版、2008年にはGCC-4.2をベースとしたコンパイラが開発された。</li>
+	<li>GCC上のCbCコンパイラは、GCCで修正・追加されていく最適化の機能を使用する為に、アップデートに合わせ変更する必要がある。</li>
+	<li>本研究ではCbCコンパイラをGCC-4.6へとアップデートを行った。 </li>
       </div>
       <!-- PAGE -->
       <div class="slide">
@@ -131,9 +131,9 @@
 	<ul>
 	<li>コードセグメント:CbCにおけるプログラムの基本単位</li>
 	<ul>
+	  <li>Cから関数コールとループ制御が取り除かれた形</li>
 	  <li>C の関数よりも細かい単位になる。</li>
 	  <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
-	  <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
 	  </ul>
 	<p class="center">
 	  <img src="./pix/codesegment.png"  style="height:6em;">
@@ -225,16 +225,19 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC</h1>
+	<li>GCC:Gnu Compiler Collection</li>
 	  <ul>
-	    <li>本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。</li>
-	    <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
+	    <li><small>GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。</small></li>
+	    <li><small>cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</small></li>
 	  <ul>
 	    <li>Generic Tree</li>
 	    <li>GIMPLE</li>
 	    <li>Tree SSA</li>
 	    <li>RTL</li>
 	  </ul>
+<!--
 	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
+-->
 	<li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
 	  </ul>
       </div>
@@ -270,7 +273,7 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC:Generic Tree</h1>
-	<li><small>CALL_EXPRE、MODIFY_EXPR等といった表現で扱われる。</small></li>
+	<li><small>CALL_EXPRE、MODIFY_EXPR、RETURN_EXPR等といった表現で扱われる。</small></li>
 	<table width=100% border=1>
 	  <tr>
 	    <td class="center"><small>ソースコード</small></td>
@@ -311,12 +314,12 @@
 	<h1>CbCの実装</h1>
 	<ul>
 	  <li>シンタックスの追加</li>
+	  <li>継続処理の実装</li>
+<!--
 	  <li>末尾除去:Tail Call Elimination(TCE)</li>
+-->
 	  <li>レジスタによる引数渡し(fastcall属性の付与)</li>
      	  <li>環境付き継続</li>
-<!--
-	  <li>__rectype の実装</li>
--->
 	</ul>
       </div>
       <!-- PAGE -->
@@ -326,52 +329,72 @@
 	  <li>__code キーワードでのコードセグメントの宣言</li>
 	  <ul>
 	    <li>__code 用idとkeywordを作成。</li>
-	    <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
+	    <li>通常の関数作成と基本同じだが、コードセグメント判定用のフラグを立てる。</li>
 	  </ul>
 	</ul>
 	  <table width=100% border=1>
 	    <tr class="srctr">
 	      <td>
-	      <pre>
+	      <pre class="srcbox" style="height:13em">
+tree
+build_code_segment_type (tree value_type, tree arg_types)
+{
+  tree t;
+  hashval_t hashcode = 0;
+
+  gcc_assert (TREE_CODE (value_type) == VOID_TYPE);
+
+  /* Make a node of the sort we want.  */
+  t = make_node (FUNCTION_TYPE);
+  TREE_TYPE (t) = value_type;
+  TYPE_ARG_TYPES (t) = arg_types;
+
+  CbC_IS_CODE_SEGMENT (t) = 1;
+
+  if (!COMPLETE_TYPE_P (t))
+    layout_type (t);
+  return t;
+}
+	      </pre>
+	      </td>
+	    </tr>
+	    </table>
+	  <li><small>コードセグメントはGCC内部では関数として扱われる。</small></li>
+      </div>
+
+      <!-- SOURCE -->
+<!--
 const struct c_common_resword c_common_reswords[] =
 {
  { "_Bool",            RID_BOOL,      D_CONLY },
      :
  { "__code",         RID_CbC_CODE,   0 },
-	      </pre>
-	      </td>
-	    </tr>
-	    <tr class="srctr">
-	      <td>
-		<pre>
+...
+
 case RID_CbC_CODE:
       :
  specs->typespec_word = cts_CbC_code;
-                 </pre>
-	      </td>
-	    </tr>
-	    <tr class="srctr">
-	      <td>
-		<pre>
+...
+
 case cts_CbC_code:
        :
      specs->type = void_type_node;
      break;
-                </pre>
-	      </td>
-	    </tr>
-	    </table>
-      </div>
-      <!-- PAGE -->
+-->
+      <!--PAGE-->
       <div class="slide">
 	<h1>CbCの実装:gotoシンタックスの追加</h1>
 	  <li>goto によるコードセグメントへの継続</li>
 	  <ul>
-	    <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
+	    <li>通常の goto の構文にコードセグメントへ継続する処理を追加。</li>
+<!--
 	    <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
+-->
 	  </ul>
-	<li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li>
-	  <pre class="srcbox" style="font-size:25px; height:16em;">
+	<table width=100% border=1>
+	  <tr>
+	    <td>
+	  <pre class="srcbox" style="font-size:25px; height:20em;" >
  case RID_GOTO:
    c_parser_consume_token (parser);
    if ( c_parser_next_token_is (parser, CPP_NAME)
@@ -390,19 +413,35 @@
        mark_exp_read (val);
        stmt = c_finish_goto_ptr (loc, val);
      }
+#ifndef noCbC
    else
-     expr = c_parser_expr_no_commas (parser, NULL);
-   if (TREE_CODE(expr.value) == CALL_EXPR )
      {
-       location_t loc = c_parser_peek_token (parser)->location;
-       cbc_replace_arguments (loc, expr.value);
-       TREE_TYPE(expr.value) = void_type_node;
-       CbC_IS_CbC_GOTO (expr.value) = 1;
-       CALL_EXPR_TAILCALL (expr.value) = 1;
-       add_stmt(expr.value);
-       stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
+       if (c_parser_next_token_is (parser, CPP_NAME))
+	 {
+	   tree id = c_parser_peek_token (parser)->value;
+	   location_t loc = c_parser_peek_token (parser)->location;
+	   /** build_external_ref (id,RID_CbC_CODE , loc); **/
+	   build_external_ref (loc, id, RID_CbC_CODE, &expr.original_type);
+	 }
+       expr = c_parser_expr_no_commas (parser, NULL);
+       if (TREE_CODE(expr.value) == CALL_EXPR )
+	 {
+	   location_t loc = c_parser_peek_token (parser)->location;
+	   cbc_replace_arguments (loc, expr.value);
+	   TREE_TYPE(expr.value) = void_type_node;
+	   CbC_IS_CbC_GOTO (expr.value) = 1;
+	   CALL_EXPR_TAILCALL (expr.value) = 1;
+	   add_stmt(expr.value);
+	   stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
+	 }
+       else
+	 c_parser_error (parser, "expected code segment jump or %<*%>");
      }
+#else
 	</pre>
+	  </td>
+	    </tr>
+	  </table>
       </div>
       <!-- PAGE -->
       <div class="slide">
@@ -445,14 +484,18 @@
 	  </tr>
 	</table>
 	<ul>
+	  <li><small>これで__codeによるコードセグメントの宣言と、gotoによる関数呼び出しが行われるようになった。</small></li>
+	  <li class="incremental"><small>次に、コードセグメントへの関数呼び出しは軽量継続で行わせる処理がいる。</small></li>
+<!--
 	  <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
 	  <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
+-->
 	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
-	<h2>末尾除去:Tail Call Elimination(TCE)</h2>
+	<h1>CbCの実装:軽量継続(末尾除去)</h1>
+	<h2>軽量継続は<font color=red>末尾除去(Tail Call elimination)</font>によって実装される。</h2>
 	<ul>
 	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
 	</ul>
@@ -497,16 +540,16 @@
 	  </pre>
 	  </td>
 	  <td class="center">
-	    <img src="./pix/continuation.png" style="height:100%;">
+	    <img src="./pix/continuation.png" style="height:90%;">
 	    </td>
 	    </tr>
 	</table>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<h1>CbCの実装:軽量継続(末尾除去)</h1>
 	<ul>
-	<li>TCEにかかる条件</li>
+	<li>末尾除去にかかる条件</li>
 	<ul>
 	  <li>caller側とcallee側の戻値の型の一致している。</li>
 	  <li>関数呼び出しがリターン直前に行われている。</li>
@@ -515,7 +558,7 @@
 	</ul>
 	<li class="incremental">条件を回避する為以下の実装にする。</li>
 	<ul class="incremental">
-	  <li>型はvoid型で統一する。</li>
+	  <li>コードセグメントの型はvoid型で統一する。</li>
 	  <li>gotoの直後にreturnを置く。</li>
 	  <li>スタックサイズは固定にする。</li>
 	  <li>引数は一旦、一時変数にコピーする。</li>
@@ -524,14 +567,14 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
-	<li>TCEの条件はexpand_call関数で調べられる。</li>
+	<h1>CbCの実装:軽量継続(末尾除去)</h1>
+	<li>末尾除去の条件はexpand_call関数で調べられる。</li>
 	<ul>
 	  <li>expand_call関数</li>
 	<ul>
 	  <li>Treeで表された関数からRTLを生成する関数</li>
 	  <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
-	  <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
+	  <li>try_taill_call(変数名)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。</li>
 	</ul>
 	<li class="incremental">具体的な実装内容</li>
 	<ul>
@@ -543,7 +586,7 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<h1>CbCの実装:軽量継続(末尾除去)</h1>
 	<li>try_tail_callフラグが落とされる部分</li>
 	<table width=100%>
 	  <tr class="srctr">
@@ -629,7 +672,7 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<h1>CbCの実装:軽量継続(末尾除去)</h1>
 	<li>try_tail_callフラグ矯正付与のソースコード</li>
 	<table width=100%>
 	  <tr class="srctr">
@@ -652,13 +695,12 @@
 	  </tr>
 	  </table>
 	<ul>
-	  <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
-	    <br><small>(最適化の矯正付与)</small></li>
+	  <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。<small>(最適化の矯正付与)</small></li>
 	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)の実装について</h1>
+	<h1>CbCの実装:軽量継続(末尾除去)の実装について</h1>
 	<ul>
 	  <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
 	  <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
@@ -668,32 +710,6 @@
       <!-- PAGE -->
 <!--
       <div class="slide">
-	<h1>CbCの実装</h1>
-	<li>CbCの基本機能を実現する為の実装は以上の2つになる。</li>
-	<ul>
-	  <li>シンタックスの追加</li>
-	  <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
-	</ul>
-	<li class="incremental">ここからはCbCの機能の拡張になる。</li>
-      </div>
--->
-      <!-- PAGE -->
-<!--
-      <div class="slide">
-	<h1>CbCの実装:環境付き継続</h1>
-	<li>CbCにおけるCとの互換性を保つための機能。</li>
-	<li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
-	<li>論文における訂正</li>
-	<li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
-	<ul>
-	  <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li>
-	  <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li>
-	</ul>
-      </div>
--->
-      <!-- PAGE -->
-<!--
-      <div class="slide">
 	<h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
 	<p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
 	    とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
@@ -789,7 +805,7 @@
 	<table border=1 width=100%>
 	  <tr>
 	    <td><small>生成しているコード</small></td>
-	    <td><small>生成されるTree</small></td>
+	    <td><small>生成するコード(GCC内部)</small></td>
 	  </tr>
 	  <tr class="srctr">
 	    <td width=50% class="srctd">
@@ -811,28 +827,6 @@
 	}), __environment);
 	  </pre>
 	    </td>
-	    <td width=50% class="srctd">
-	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
-	    </td>
-	  </tr>
-	  </table>
-	  <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
-<!--
-	<li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
--->
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>CbCの実装:環境付き継続</h1>
-	<table border=1 width=100%>
-	  <tr>
-	    <td width=50%><small>生成されるTree</small></td>
-	    <td width=50%><small>生成する為のコード</small></td>
-	  </tr>
-	  <tr class="srctr">
-	    <td class="srctd">
-	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
-	    </td>
 	    <td class="srctd">
 	      <pre class="srcbox" style="width:25em;">

@@ -883,25 +877,31 @@
 }
 			 </pre>
 	    </td>
+	    </td>
+	  </tr>
+	  </table>
+	  <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
+<!--
+	<li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
+-->
+      </div>
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
+	<table border=1 width=100%>
+	  <tr>
+	    <td width=50%><small>生成されるTree</small></td>
+	    <td width=50%><small>生成する為のコード</small></td>
+	  </tr>
+	  <tr class="srctr">
+	    <td class="srctd">
+	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
+	    </td>
 	  </tr>
 	</table>
-<!--
-	<small>
-	  <pre>
-	({
-	  __label__ _cbc_exit0;
-	  static int retval;
-	  void _cbc_internal_return(int retval_, void *_envp){
-	    retval = retval_;
-	    goto _cbc_exit0; }
-	  if (0) { _cbc_exit0:
-	    return retval; }
-	  _cbc_internal_return;
-	}),
-	  </pre>
-	  </small>
+      </div>
 -->
-      </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>環境付き継続:実装の問題</h1>
@@ -913,9 +913,11 @@
 	<ul>
 	  <li>クロージャでの確保</li>
 	  <li>staticでの確保</li>
+	  <li>static thread local storage(tls)を用いての確保</li>
+<!--
 	  <li>setjmpを用いての実装</li>
-	  <li>static thread local storage(tls)を用いての確保</li>
 	  <li>戻り値を入れるレジスタを明示的に指定</li>
+-->
 	</ul>
       </div>
       <!-- PAGE -->
@@ -935,24 +937,35 @@
 	    <li >マルチスレッドのプログラムに対応できない。</li>
 	    <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
 	  </ul>
-
-	  <li>setjmpでの実装</li>
+	<li class="incremental">static tlsでの実装</li>
+	<!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
+	<ul class="incremental">
+	<li>現在はこの方法で実装を行なっている。</li>
+	<li>しかし、最適化にかけると正しい値が返ってこない。
+	  <br>(最適化によりコードが削除されている...?)</li>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>クロージャの動作について</h1>
+	<li>予稿における訂正</li>
+	<li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
+	<ul>
+	  <li>CbCの末尾除去矯正付与のせいでクロージャが破壊されていたことが判明。</li>
+	  <li>GCC 4.6 と Lion でのクロージャは特に問題はなかった。</li>
+	</ul>
+      </div>
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>環境付き継続:実装の問題</h1>
+	<ul>
+	  <li>setjmpでの実装の問題点:</li>
 	  <ul>
 	    <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
 	    <li>int型の戻値しか得られない。</li>
 	  </ul>
-	</ul>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>環境付き継続:実装の問題</h1>
-	<ul>
-	<li>static tlsでの実装</li>
-	<!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
-	<ul>
-	<li>現在はこの方法で実装を行なっている。</li>
-	<li>しかし、最適化にかけると正しい値が返ってこない。
-	  <br>(最適化によりコードが削除されている...?)</li>
+
 	</ul>
 	<li>戻値を入れるレジスタを明示的に指定する。</li>
 	<ul>
@@ -960,30 +973,31 @@
 	</ul>
 	</ul>
       </div>
+-->
       <!-- PAGE -->
       <div class="slide">
 	<h1>Micro-Cとの比較</h1>
-	<li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
 	<table width=100% class="center">
+	<caption><small>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</small></caption>
 	  <td>
-	    <img src="./pix/mac_conv.png">
+	    <img src="./pix/mac_conv.png" style="height:10em">
 	  </td>
 	  <td>
-	    <img src="./pix/linux_conv.png">
+	    <img src="./pix/linux_conv.png" style="height:10em">
 	  </td>
 	  </table>
-	  <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
-	    その為に明らかに遅くなっていることが分かる。</li>
-	  <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li>
+	  <li><small>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
+	    その為に明らかに遅くなっていることが分かる。</small></li>
+	  <li><small>だがGCCの最適化有りの場合はMicro-C版よりも早い。</small></li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>まとめ</h1>
 	  <ul>
 	    <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
-	    <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。
-	      <br>おかげで、以前より楽な管理ができる実装にすることができた。</li>
-	    <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li>
+	    <li>末尾除去にかかる判定の部分の実装の修正を行った。
+	      <br>それにより、以前より楽な管理ができる実装にすることができた。</li>
+	    <li>後は環境付き継続の最適化の問題の修正とselftypeといった新しい実装を行う。</li>
 	    <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
 	    </ul>
 	</div>
@@ -1002,7 +1016,26 @@
 	</div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)の動作</h1>
+	<h1>CbCの引数渡し</h1>
+	<table border=1 width=100%>
+	  <caption><small>fastcall属性有・無の実行速度</small></caption>
+	  <tr class="center">
+	    <td width=50%><small>fastcall有り</small></td>
+	    <td width=50%><small>fastcall無し</small></td>
+	  </tr>
+	  <tr class="center">
+	    <td>
+	      <img src="./pix/linux_conv_fastcall.png">
+	    </td>
+	    <td>
+	      <img src="./pix/linux_conv_nofastcall.png">
+	    </td>
+	  </tr>
+	    </table>
+	</div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:軽量継続(末尾除去)の動作</h1>
 	<li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
 	<table width=100% border=1>
 	  <td>
--- a/presen/index.html~	Wed Jan 04 17:16:44 2012 +0900
+++ b/presen/index.html~	Wed Jan 04 23:41:05 2012 +0900
@@ -4,7 +4,22 @@
 <html xmlns="http://www.w3.org/1999/xhtml">

 <head>
-<style>
+<style type="text/css">
+tr.srctr {
+font-size:28px;
+}
+td.srctd {
+height:17em;
+}
+pre.srcbox {
+height: 100%;
+overflow: scroll;
+}
+.src{
+overflow: scroll;
+width: 90%;
+height: 60%;
+}
 .center {
 margin-left: auto;
 margin-right: auto;
@@ -19,11 +34,11 @@
    font-weight: bold;
 }
 </style>
-<title>2011/12/20</title>
+<title>2012/ 1/ 7</title>
 <!-- metadata -->
     <meta name="generator" content="S5" />
     <meta name="version" content="S5 1.1" />
-    <meta name="presdate" content="20111220" />
+    <meta name="presdate" content="20120107" />
     <meta name="author" content="Nobuyasu Oshiro" />
     <meta name="company" content="University of the Ryukyu" />
 <!-- meta temporary -->
@@ -68,7 +83,7 @@
 <div id="currentSlide"><!-- DO NOT EDIT --></div>
 <div id="header"></div>
 <div id="footer">
-<h1>セミナー: 2011/ 12/ 20</h1>
+<h1>プログラミングシンポジウム: 2012/ 1/ 7</h1>
 <h2>並列信頼研</h2>
 </div>
 </div>
@@ -85,141 +100,963 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>目的と背景(1)</h1>
-	<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li>
+	<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。</li>
 	<li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
+	<li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
  	<h1>目的と背景(2)</h1>
-	<li>CbC のコンパイラは2008年に GCC をベースとしたコンパイラが開発された。</li>
-	<li>GCC をベースとした CbC コンパイラは、GCC のアップデートに合わせ変更する必要がある。</li>
-	<li>本研究ではGCC-4.5 をベースとしていた CbC コンパイラを GCC-4.6 へのアップデートを行い、Intel64 への対応するとともに CbC の拡張を行う。 </li>
+	<li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
+	<li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
+	<li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>発表内容</h1>
+	<ol>
+	  <li>CbC の紹介</li>
+	  <li>GCC でのコンパイルの流れ</li>
+	  <font color="red">
+	    <li>CbC の実装</li>
+	  </font>
+	  <li>Micro-C との性能比較</li>
+	  <li>まとめ</li>
+	<ol>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>Continuation based C </h1>
+	<h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
+	<ul>
+	<li>コードセグメント:CbCにおけるプログラムの基本単位</li>
+	<ul>
+	  <li>C の関数よりも細かい単位になる。</li>
+	  <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
+	  <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
+	  </ul>
+	<p class="center">
+	  <img src="./pix/codesegment.png"  style="height:6em;">
+	  </p>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>Continuation based C </h1>
+	<h2>継続:現在の処理を実行していく為の情報</h2>
+
+	<table width=100% border=1>
+	  <tr>
+	    <td><small>Cの継続</small></td>
+	    <td><small>CbCの継続(軽量継続)</small></td>
+	  </tr>
+	  <tr style="font-size:30px">
+	    <td>
+	      <ul>
+		<li>続く命令のアドレス</li>
+		<li>命令に必要なデータ</li>
+		<li>スタックに積まれている値(環境)</li>
+	      </ul>
+	    </td>
+	    <td>
+	      <ul>
+		<li>Cの継続から環境を除外</li>
+		<li>続く命令とその命令に必要なデータのみ</li>
+	      </ul>
+	    </td>
+	  </tr>
+	    <tr>
+	    <td style="margin-left:auto; margin-right: auto; text-align: center;">
+	      <img class="scale" src="./pix/func_call.png" style="height: 6em;">
+	      </td>
+	    <td style="margin-left:auto; margin-right: auto; text-align: center;">
+		<img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
+	      </td>
+	    </tr>
+	</table>
+	  <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>Continuation based C </h1>
+<table width=100% border=1>
+<caption><small>階乗を求めるCbCのプログラム</small></caption>
+<tr class="srctr">
+<td width=50%>
+	  <pre class="srcbox">
+
+__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);
+  }
+}
+	  </pre>
+</td>
+<td>
+<pre class="srcbox">
+
+__code factorial(int x) {
+  goto factorial0(1, x);
+}
+
+int main(int argc, char **argv) {
+  int i;
+  i = atoi(argv[1]);
+  goto factorial(i);
+  return 0;
+}
+</pre>
+</td>
+</tr>
+</table>
+	<ul>
+	  <li><small>__code キーワードによるコードセグメントの宣言</small></li>
+	  <li><small>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</small></li>
+	</ul>
+	<li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>今週の作業内容</h1>
-	<li></li>
-	<li>環境付き継続について</li>
+	<h1>GCC</h1>
+	  <ul>
+	    <li>本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。</li>
+	    <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
+	  <ul>
+	    <li>Generic Tree</li>
+	    <li>GIMPLE</li>
+	    <li>Tree SSA</li>
+	    <li>RTL</li>
+	  </ul>
+	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
+	<li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
+	  </ul>
+      </div>
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>GCC:Generic Tree</h1>
+	<li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
+	<table class="center" width=100%  border=1>
+	  <tr>
+	    <td></td>
+	    <td><small>値の代入:MODIFY_EXPR</small></td>
+	    <td><small>関数呼び出し:CALL_EXPR</small></td>
+	  </t>
+	  <tr>
+	    <td>命令</td>
+	    <td>b = a * 10</td>
+	    <td>func(a,10)</td>
+	  </t>
+	  <tr>
+	    <td><small>Generic<br>Tree</small></td>
+	  <td>
+	    <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
+	  </td>
+	  <td>
+	    <img src="./pix/CALL_EXPR.png" style="height: 7em;">
+	  </td>
+	  </tr>
+	</table>
+	  <p class="center"><small>Generic Treeでの表現</small></p>
+      </div>
+-->
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>GCC:Generic Tree</h1>
+	<li><small>CALL_EXPRE、MODIFY_EXPR等といった表現で扱われる。</small></li>
+	<table width=100% border=1>
+	  <tr>
+	    <td class="center"><small>ソースコード</small></td>
+	    <td class="center"><small>Generic Treeでの表現</small></td>
+	  </tr>
+	  <tr>
+	    <td>
+	<small>
+	<pre>
+int main() {
+  int a, b;
+  a = 3;
+  b = func(a, 10);
+  return b;
+}
+	</pre>
+	</small>
+	</td>
+	    <td style="margin-left:auto; margin-right:auto; text-align: center;">
+	  <img src="./pix/STATEMENT_LIST.png" style="height: 7em;">
+	  </td>
+	  </tr>
+	    </table>
+	  <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
+      </div>
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>GCC</h1>
+	<li>GCC についての簡単な説明を行う...</li>
+	<li>TODO: NEXT_PASS() の把握</li>
+	<img src="./pix/ir.png" style="height: 6em;">
+	<li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li>
+      </div>
+-->
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装</h1>
+	<ul>
+	  <li>シンタックスの追加</li>
+	  <li>末尾除去:Tail Call Elimination(TCE)</li>
+	  <li>レジスタによる引数渡し(fastcall属性の付与)</li>
+     	  <li>環境付き継続</li>
+<!--
+	  <li>__rectype の実装</li>
+-->
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:__codeシンタックスの追加</h1>
 	<ul>
-	  <li>変数 retval を static スレッドローカル(TLS)での実装</li>
+	  <li>__code キーワードでのコードセグメントの宣言</li>
+	  <ul>
+	    <li>__code 用idとkeywordを作成。</li>
+	    <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
+	  </ul>
+	</ul>
+	  <table width=100% border=1>
+	    <tr class="srctr">
+	      <td>
+	      <pre>
+const struct c_common_resword c_common_reswords[] =
+{
+ { "_Bool",            RID_BOOL,      D_CONLY },
+     :
+ { "__code",         RID_CbC_CODE,   0 },
+	      </pre>
+	      </td>
+	    </tr>
+	    <tr class="srctr">
+	      <td>
+		<pre>
+case RID_CbC_CODE:
+      :
+ specs->typespec_word = cts_CbC_code;
+                 </pre>
+	      </td>
+	    </tr>
+	    <tr class="srctr">
+	      <td>
+		<pre>
+case cts_CbC_code:
+       :
+     specs->type = void_type_node;
+     break;
+                </pre>
+	      </td>
+	    </tr>
+	    </table>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:gotoシンタックスの追加</h1>
+	  <li>goto によるコードセグメントへの継続</li>
+	  <ul>
+	    <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
+	    <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
+	  </ul>
+	<li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li>
+	  <pre class="srcbox" style="font-size:25px; height:16em;">
+ case RID_GOTO:
+   c_parser_consume_token (parser);
+   if ( c_parser_next_token_is (parser, CPP_NAME)
+	&& c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
+     {
+       stmt = c_finish_goto_label (loc,
+				   c_parser_peek_token (parser)->value);
+       c_parser_consume_token (parser);
+     }
+   else if (c_parser_next_token_is (parser, CPP_MULT))
+     {
+       tree val;
+
+       c_parser_consume_token (parser);
+       val = c_parser_expression (parser).value;
+       mark_exp_read (val);
+       stmt = c_finish_goto_ptr (loc, val);
+     }
+   else
+     expr = c_parser_expr_no_commas (parser, NULL);
+   if (TREE_CODE(expr.value) == CALL_EXPR )
+     {
+       location_t loc = c_parser_peek_token (parser)->location;
+       cbc_replace_arguments (loc, expr.value);
+       TREE_TYPE(expr.value) = void_type_node;
+       CbC_IS_CbC_GOTO (expr.value) = 1;
+       CALL_EXPR_TAILCALL (expr.value) = 1;
+       add_stmt(expr.value);
+       stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
+     }
+	</pre>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:gotoシンタックスの追加</h1>
+	<ul>
+	<small>
+	    <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
+	    <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
+	    <li>最後にc_finish_return関数によりreturn文を生成している。</li>
+	</small>
+	</ul>
+	<table border=1 width=100%>
+<!--
+	  <caption><small>return 自動生成</small></caption>
+-->
+	  <tr class="center">
+	  <td><small>実際のコード</small></td>
+	  <td><small>GCC内で処理されるコード</small></td>
+	  </tr>
+	  <tr class="srctr">
+	  <td>
+	    <pre>
+
+__code test() {
+   :
+  goto factorial0(1, x);
+}
+	    </pre>
+	  </td>
+	  <td>
+	    <pre>
+
+void test() {
+   :
+  factorial0(1, x);
+  return;
+}
+	    </pre>
+	  </td>
+	  </tr>
+	</table>
+	<ul>
+	  <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
+	  <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<h2>末尾除去:Tail Call Elimination(TCE)</h2>
+	<ul>
+	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
+	</ul>
+	<li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
+	<br>
+	<table width=100%>
+	  <tr class="srctr">
+	  <td width=50%>
+<!--
+	<pre class="srcbox">
+int main() {
+  int num = a(2);
+  printf("main:num=%d\n",num);
+  return 0;
+}
+int a(int num) {
+  return b(num+5);
+}
+int b(int num) {
+  printf("b:a = %d\n",num);
+  return num+3;
+}
+	</pre>
+-->
+          <pre class="srcbox">
+
+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 class="center">
+	    <img src="./pix/continuation.png" style="height:100%;">
+	    </td>
+	    </tr>
+	</table>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<ul>
+	<li>TCEにかかる条件</li>
+	<ul>
+	  <li>caller側とcallee側の戻値の型の一致している。</li>
+	  <li>関数呼び出しがリターン直前に行われている。</li>
+	  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+	  <li>引数の並びのコピーに上書きがない。</li>
+	</ul>
+	<li class="incremental">条件を回避する為以下の実装にする。</li>
+	<ul class="incremental">
+	  <li>型はvoid型で統一する。</li>
+	  <li>gotoの直後にreturnを置く。</li>
+	  <li>スタックサイズは固定にする。</li>
+	  <li>引数は一旦、一時変数にコピーする。</li>
+	</ul>
 	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>static TLS のGeneric Tree</h1>
-	<li>変数 retval の宣言(VAR_DECL)</li>
-	<li>static TLS の場合追加される情報は以下の2つ:(Linux)</li>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<li>TCEの条件はexpand_call関数で調べられる。</li>
+	<ul>
+	  <li>expand_call関数</li>
 	<ul>
-	  <li>TLS のモデル: TLS_MODEL_LOCAL_EXEC</li>
-	  <li>static フラグ 1</li>
+	  <li>Treeで表された関数からRTLを生成する関数</li>
+	  <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
+	  <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
 	</ul>
-	<li class="incremental">上記の設定で retval を作成しても正しい返り値は得られなかった。</li>
+	<li class="incremental">具体的な実装内容</li>
+	<ul>
+	  <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
+	  <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
+	</ul>
+	<ul>
+
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>環境付き継続の構文木をみる</h1>
-	<li>環境継続において以下の retval 変数は static で作られている.</li>
-<small>
-<pre>
-({
-  __label__ _cbc_exit0;
-  static __thread int retval;
-  void _cbc_internal_return(int retval_, void *_envp){
-    printf("in _cbc_internal_return\n",retval_);
-    retval = retval_;
-    goto _cbc_exit0;
-  }
-  if (0) {
-  _cbc_exit0:
-    return retval;
-  }
-  _cbc_internal_return;
-})
-</pre>
-</small>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>環境付き継続の構文木をみる</h1>
-	<img src="./pix/BIND_EXPR.png">
-	<li>BIND_EXPR は{ } の中身を束ねる。</li>
-	<li>STATEMENT_LIST が1つ1つのプログラムを表す木を持っている。</li>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<li>try_tail_callフラグが落とされる部分</li>
+	<table width=100%>
+	  <tr class="srctr">
+	    <td class="srctd">
+	<pre class="srcbox">
+
+  if (currently_expanding_call++ != 0
+      || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))
+         && !flag_optimize_sibling_calls)
+      || args_size.var
+      || dbg_cnt (tail_call) == false)
+    try_tail_call = 0;
+
+     :
+
+  if (
+#ifdef HAVE_sibcall_epilogue
+      !HAVE_sibcall_epilogue
+#else
+      1
+#endif
+      || !try_tail_call
+      || structure_value_addr != NULL_RTX
+#ifdef REG_PARM_STACK_SPACE
+      || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
+          != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
+      || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl))
+#endif
+      || !targetm.function_ok_for_sibcall (fndecl, exp)
+      || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
+      || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
+      || (fndecl && decl_function_context (fndecl) == current_function_decl)
+      || args_size.constant > (crtl->args.size
+                               - crtl->args.pretend_args_size)
+      || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
+          != targetm.calls.return_pops_args (current_function_decl,
+                                             TREE_TYPE (current_function_decl),
+                                             crtl->args.size))
+      || !lang_hooks.decls.ok_for_sibcall (fndecl))
+    try_tail_call = 0;
+
+      :
+
+  /* Check if caller and callee disagree in promotion of function
+     return value.  */
+#ifndef noCbC
+  if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
+#else
+    if (try_tail_call)
+#endif
+    {
+      enum machine_mode caller_mode, caller_promoted_mode;
+      enum machine_mode callee_mode, callee_promoted_mode;
+      int caller_unsignedp, callee_unsignedp;
+      tree caller_res = DECL_RESULT (current_function_decl);
+
+      caller_unsignedp = TYPE_UNSIGNED (TREE_TYPE (caller_res));
+      caller_mode = DECL_MODE (caller_res);
+      callee_unsignedp = TYPE_UNSIGNED (TREE_TYPE (funtype));
+      callee_mode = TYPE_MODE (TREE_TYPE (funtype));
+      caller_promoted_mode
+        = promote_function_mode (TREE_TYPE (caller_res), caller_mode,
+                                 &caller_unsignedp,
+                                 TREE_TYPE (current_function_decl), 1);
+      callee_promoted_mode
+        = promote_function_mode (TREE_TYPE (funtype), callee_mode,
+                                 &callee_unsignedp,
+                                 funtype, 1);
+      if (caller_mode != VOIDmode
+          && (caller_promoted_mode != callee_promoted_mode
+              || ((caller_mode != caller_promoted_mode
+                   || callee_mode != callee_promoted_mode)
+                  && (caller_unsignedp != callee_unsignedp
+                      || GET_MODE_BITSIZE (caller_mode)
+                         < GET_MODE_BITSIZE (callee_mode)))))
+        try_tail_call = 0;
+    }
+	</pre>
+	    </td>
+	  </tr>
+	</table>
+	<li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>環境付き継続の構文木をみる</h1>
-	<img src="./pix/STATEMENT_LIST_1.png">
-	<li>BIND_EXPR は _cbc_internal_return 関数を<br>
-	ADDR_EXPR は最後の行の _cbc_internal_return を表す。</li>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>環境付き継続の構文木をみる</h1>
-	<li>_CbC_return の実装より作られる構文木を見てみる。</li>
-	<scale>
-	<img src="./pix/STATEMENT_LIST_2.png">
-	</scale>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>環境付き継続の構文木をみる</h1>
-	<li>出来上がる構文木が違う。</li>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<li>try_tail_callフラグ矯正付与のソースコード</li>
+	<table width=100%>
+	  <tr class="srctr">
+	    <td>
+	  <pre class="srcbox">
+#ifndef noCbC
+  if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
+      && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
+      && try_tail_call == 0)
+    {
+      location_t loc = EXPR_LOCATION (exp);
+      char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
+      warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
+                        name_callee);
+      try_tail_call = 1;
+    }
+#endif
+	</pre>
+	  </td>
+	  </tr>
+	  </table>
 	<ul>
-	  <li>DECL_EXPR が 1つ足りない</il>
-	  <li>BIND_EXPR の部分が COND_EXPR になっている。</li>
+	  <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
+	    <br><small>(最適化の矯正付与)</small></li>
 	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>DECL_EXPR の問題</h1>
-	<li>なくなっている DECL_EXPR は VAR_DECL の部分。</li>
-	<li>static __thread int retval になる。</li>
-	<li>下記の様にソースを変更</li>
-	<pre>
-//      pushdecl (decl_cond);
-add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));
-	</pre>
-	<li>これで DECL_EXPR が追加された。</li>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>COND_EXPR の問題</h1>
-	<li>BIND_EXPR でなくて COND_EXPR になっていた問題。</li>
-	<li>BIND_EXPR をみると以下の様な構成になっていた。</li>
-	<img src="./pix/COND_EXPR.png">
-	  <li>BIND_EXPR をなぜか COND_EXPR でもう一度包んでいた。</li>
-	  <small>
-	  <p>COND_EXPR には if(0){ } の中身が入る。</p>
-	  </small>
-       </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>ソースの手直し</h1>
-	<li>if(0){ } の構文木が作られる手順を元に<br>
-	cbc_finish_labeled_goto 関数を手直しした。
-	<li>同じ構文木が作られるようになった。</li>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>結果</h1>
-	<li>正常な値が返ってくるようになった。</li>
-	<li class="incremental">しかし、-O2 オプションをつけると返り値の取得が失敗した。</li>
-	<li class="incremental">もっと細かく構文木をみて違いを見つける必要がある。</li>
+	<h1>CbCの実装:TCE(末尾除去)の実装について</h1>
+	<ul>
+	  <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
+	  <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
+	  <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
+	</ul>
       </div>
       <!-- PAGE -->
 <!--
       <div class="slide">
-	<h1>static TLS のGeneric Tree</h1>
-	<li>変数 retval の宣言(VAR_DECL) が OS X の場合使用する TLS モデルが違った。</li>
-	<li>Linux: TLS_MODEL_LOCAL_EXEC</li>
-	<li>OS X: TLS_MODEL_REAL<br>(TLS_MODEL_GLOBAL_DYNAMIC)</li>
+	<h1>CbCの実装</h1>
+	<li>CbCの基本機能を実現する為の実装は以上の2つになる。</li>
+	<ul>
+	  <li>シンタックスの追加</li>
+	  <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
+	</ul>
+	<li class="incremental">ここからはCbCの機能の拡張になる。</li>
+      </div>
+-->
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
+	<li>CbCにおけるCとの互換性を保つための機能。</li>
+	<li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
+	<li>論文における訂正</li>
+	<li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
+	<ul>
+	  <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li>
+	  <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li>
+	</ul>
+      </div>
+-->
+      <!-- PAGE -->
+<!--
+      <div class="slide">
+	<h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
+	<p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
+	    とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
+      </div>
+-->
+       <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:引数渡し</h1>
+	<li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
+	<ul>
+	  <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
+	</ul>
+	<li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:引数渡し(fastcall)</h1>
+	<h2>fastcall</h2>
+	<ul>
+	  <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
+	  <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
+	</ul>
+	<li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
+	<small>
+	<pre>
+if(!TARGET_64BIT) {
+  attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
+  declspecs_add_attrs(specs, attrs);
+ }
+	</pre>
+	</small>
+	<p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:引数渡し</h1>
+	<ul>
+	  <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
+	</ul>
+	<br>
+	<table width=100% border=1 class="center">
+	  <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
+	  <tr>
+	    <td>arch</td>
+	    <td>int(整数型)</td>
+	    <td>float(浮動小数点型)</td>
+	    <td>double(浮動小数点型)</td>
+	  </tr>
+	  <tr>
+	    <td>i386</td>
+	    <td>2</td>
+	    <td>0<br>(stackを使用)</td>
+	    <td>0<br>(stackを使用)</td>
+	  </tr>
+	  <tr>
+	    <td>x64</td>
+	    <td>6</td>
+	    <td>8</td>
+	    <td>8</td>
+	  </tr>
+	</table>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
+	<ul>
+	<li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
+	<li>__returnキーワードを引数に渡すことで使うことができる。</li>
+	</ul>
+	<li>以下の使い方の場合は1を返す。</li>
+	<table border=1 width=100%>
+	    <td>
+	<small>
+	    <pre class="srcbox">
+__code c1(__code ret(int,void *),void *env) {
+ goto ret(1,env);
+}
+int main() {
+ goto c1(__return, __environment);
+}
+	</pre>
+	    </small>
+	</td>
+	    </table>
+	<p><small>__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。</small></p>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
+<!--
+	<li><small>生成しているコードと生成する為のコード</small></li>
+-->
+	<table border=1 width=100%>
+	  <tr>
+	    <td><small>生成しているコード</small></td>
+	    <td><small>生成されるTree</small></td>
+	  </tr>
+	  <tr class="srctr">
+	    <td width=50% class="srctd">
+	  <pre class="srcbox" style="width:25em;">
+
+//goto c1(__return, __environment);
+goto c1(({
+	  __label__ _cbc_exit0;
+	  static int retval;
+	  void _cbc_internal_return(int retval_, void *_envp) {
+	    retval = retval_;
+	    goto _cbc_exit0;
+          }
+	  if (0) {
+            _cbc_exit0:
+	    return retval;
+          }
+	  _cbc_internal_return;
+	}), __environment);
+	  </pre>
+	    </td>
+	    <td width=50% class="srctd">
+	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
+	    </td>
+	  </tr>
+	  </table>
+	  <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
+<!--
+	<li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
+-->
       </div>
       <!-- PAGE -->
       <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
+	<table border=1 width=100%>
+	  <tr>
+	    <td width=50%><small>生成されるTree</small></td>
+	    <td width=50%><small>生成する為のコード</small></td>
+	  </tr>
+	  <tr class="srctr">
+	    <td class="srctd">
+	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
+	    </td>
+	    <td class="srctd">
+	      <pre class="srcbox" style="width:25em;">
+
+    case RID_CbC_RET:
+{
+  tree value, stmt, label, tlab, decl;
+  c_parser_consume_token (parser);
+
+  stmt = c_begin_stmt_expr ();
+  cbc_return_f = c_parser_peek_token (parser)->value;
+  location_t location = c_parser_peek_token (parser)->location;
+
+  /* create label. (__label__ _cbc_exit0;) */
+  label = get_identifier ("_cbc_exit0");
+  tlab = declare_label (label);
+  C_DECLARED_LABEL_FLAG (tlab) = 1;
+  add_stmt (build_stmt (location, DECL_EXPR, tlab));
+
+  /* declare retval.  (int retval;) */
+  tree decl_cond =
+    build_decl (location, VAR_DECL, get_identifier ("retval"),
+		TREE_TYPE (TREE_TYPE (current_function_decl)));
+  TREE_STATIC (decl_cond) = 1;
+  TREE_USED (decl_cond) = 1;
+
+  /* Use thread-local */
+  DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
+  DECL_NONLOCAL (decl_cond) = 1;
+  add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));
+
+  /* define nested function.  */
+  decl =
+    cbc_finish_nested_function (location, label, decl_cond);
+  TREE_USED(decl) = 1;
+
+  /* define if-ed goto label and return statement. */
+  cbc_finish_labeled_goto (location, label, decl_cond);
+
+  /* get pointer to nested function.  */
+  value = build_addr (decl , current_function_decl);
+  TREE_USED (current_function_decl) = 1;
+  SET_EXPR_LOCATION (value, location);
+  add_stmt (value);
+
+  TREE_SIDE_EFFECTS (stmt) = 1;
+  expr.value = c_finish_stmt_expr (location, stmt);
+  expr.original_code = ERROR_MARK;
+}
+			 </pre>
+	    </td>
+	  </tr>
+	</table>
+<!--
+	<small>
+	  <pre>
+	({
+	  __label__ _cbc_exit0;
+	  static int retval;
+	  void _cbc_internal_return(int retval_, void *_envp){
+	    retval = retval_;
+	    goto _cbc_exit0; }
+	  if (0) { _cbc_exit0:
+	    return retval; }
+	  _cbc_internal_return;
+	}),
+	  </pre>
+	  </small>
+-->
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>環境付き継続:実装の問題</h1>
+	<li>重要な部分</li>
+	<ul>
+	  <li>リターンするretval変数のメモリ確保</li>
+	</ul>
+	<li>次の方法が考えられる。</li>
+	<ul>
+	  <li>クロージャでの確保</li>
+	  <li>staticでの確保</li>
+	  <li>setjmpを用いての実装</li>
+	  <li>static thread local storage(tls)を用いての確保</li>
+	  <li>戻り値を入れるレジスタを明示的に指定</li>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>環境付き継続:実装の問題</h1>
+	<ul>
+	  <li>クロージャでの実装の問題点:</li>
+	  <!--	<ul><li>クロージャにしてスタックに値を確保する。</li></ul>	  -->
+          <ul>
+	    <li >CbCでは継続によりスタックの値は破棄されていく。</li>
+	    <li >クロージャにしたコードが破棄される可能性がある。</li>
+	  </ul>
+
+	  <li>staticでの実装の問題点:</li>
+	  <!--	<ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
+	  <ul>
+	    <li >マルチスレッドのプログラムに対応できない。</li>
+	    <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
+	  </ul>
+
+	  <li>setjmpでの実装</li>
+	  <ul>
+	    <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
+	    <li>int型の戻値しか得られない。</li>
+	  </ul>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>環境付き継続:実装の問題</h1>
+	<ul>
+	<li>static tlsでの実装</li>
+	<!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
+	<ul>
+	<li>現在はこの方法で実装を行なっている。</li>
+	<li>しかし、最適化にかけると正しい値が返ってこない。
+	  <br>(最適化によりコードが削除されている...?)</li>
+	</ul>
+	<li>戻値を入れるレジスタを明示的に指定する。</li>
+	<ul>
+	  <li>まだ実装を試していない。</li>
+	</ul>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>Micro-Cとの比較</h1>
+	<li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
+	<table width=100% class="center">
+	  <td>
+	    <img src="./pix/mac_conv.png">
+	  </td>
+	  <td>
+	    <img src="./pix/linux_conv.png">
+	  </td>
+	  </table>
+	  <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
+	    その為に明らかに遅くなっていることが分かる。</li>
+	  <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>まとめ</h1>
+	  <ul>
+	    <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
+	    <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。
+	      <br>おかげで、以前より楽な管理ができる実装にすることができた。</li>
+	    <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li>
+	    <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
+	    </ul>
+	</div>
+      <!-- PAGE -->
+      <div class="slide">
 	<h1>今後の予定</h1>
-	<li>プロシン用プレゼンの用意</li>
-	<li>typedefrec, selftype の実装</li>
-	<li>CbC でタクスマネージャ作成</li>
+	<ul>
+     	  <li>CbCを用いたプログラムの作成</li>
+	  <ul>
+	    <li>CbCによるタスクマネージャの作成</li>
+	  </ul>
+	  <li>llvmへのCbCの実装</li>
+	</ul>
+	<br>
+	<h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
+	</div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE(末尾除去)の動作</h1>
+	<li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
+	<table width=100% border=1>
+	  <td>
+	  <p class="center">
+	    <img src="./pix/tce.png" style="height: 6em;">
+	    </p>
+	    </td>
+	  <td>
+	    <ul>
+	    <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
+	    <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
+	    </ul>
+	  </td>
+	    </table>
+	    <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの機能の拡張:__rectype の実装</h1>
+	<ul>
+	<li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
+	<pre style="font-size:28px;">
+void factorial(int n, int result, void(*print)()){
+   :
+   (*print)(n,result,print,exit1, envp);
+}
+	</pre>
+	<li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
+	<pre style="font-size:28px;">
+__code factorial(int n, int result, __rectype *print) {
+   :
+   goto (*print)(n,result,print,exit1, envp);
+}
+	</pre>
+	</ul>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの機能の拡張:selftype</h1>
+	<h2>selftypeの実装</h2>
+	<li>以下の宣言が行えるようにしたい。</li>
+	<small>
+	<pre>
+typedef sturct node {
+ selftype *left;
+ selftype *right;
+ int num;
+}*NODE
+	</pre>
+	<p>selftype は struct node を指す。</p>
+	</small>
+	<ul>
+	  <li>上記の構文は実装を行う予定である。</li>
+	</ul>
       </div>
       <!-- PAGE -->
 </div>