Mercurial > hg > Papers > 2011 > nobu-prosym

diff presen/index.html @ 80:923dd8de7be2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Wed, 04 Jan 2012 23:41:05 +0900
parents 6465e96ba272
children efe2e6806c26
line wrap: on
line diff
--- 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>