changeset 63:3cc4a8603489

modify explanation of TCE
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Wed, 28 Dec 2011 04:53:23 +0900
parents 7087484574b0
children 743afe406e56
files presen/index.html
diffstat 1 files changed, 90 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/presen/index.html	Mon Dec 26 11:23:23 2011 +0900
+++ b/presen/index.html	Wed Dec 28 04:53:23 2011 +0900
@@ -87,13 +87,13 @@
 	<h1>目的と背景(1)</h1>
 	<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li>
 	<li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
-	<li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考える。</li>
+	<li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
  	<h1>目的と背景(2)</h1>
-	<li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.4 をベースとしたコンパイラが開発された。</li>
-	<li>GCC をベースとした CbC コンパイラは、修正・追加された最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
+	<li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li>
+	<li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
 	<li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
       </div>
       <!-- PAGE -->
@@ -121,8 +121,11 @@
       <div class="slide">
 	<h1>Continuation based C </h1>
 	<h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
+	<ul>
 	  <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li>
-	<li>コードセグメント</li>
+	</ul>
+	<br>
+	<h2>コードセグメント</h2>
 	<ul>
 	  <li>C の関数よりも細かい単位。</li>
 	  <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li>
@@ -230,8 +233,8 @@
 	  </ul>
 	  <li>goto によるコードセグメントへの継続</li>
 	  <ul>
-	    <li>通常の goto に加え、コードセグメントを呼び出す処理を追加。</li>
-	    <li>コードセグメントへのgoto後は、 return の処理を自動で追加。</li>
+	    <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
+	    <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
 	  </ul>
 	</ul>
 	<li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li>
@@ -247,25 +250,25 @@
   {
     location_t loc = c_parser_peek_token (parser)->location;
     cbc_replace_arguments (loc, expr.value);
-
     TREE_TYPE(expr.value) = void_type_node;
-    /*tree env = NULL_TREE;**/
     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); /* stmt = c_finish_return (0); */
+    stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
   }
 	</pre>
 	</small>
-	<li>CALL_EXPR_TAILCALLマクロにより tail call フラグを立てている。</li>
-	<li>cbc_replace_arguments関数は引数のデータを一時的な変数へと代入させる関数</li>
+	<small>
+	<li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li>
+	<li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
 	<li>最後にc_finish_return関数によりreturn文を生成している。</li>
+	</small>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:シンタックスの追加</h1>
 	<h2>gotoシンタックスの追加</h2>
-	<li>最後にリターン文を生成することにより、次へと制御を映させず。また末尾最適化がかかるようになる。</li>
+	<li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li>
 	<table border=1 width=100%>
 	  <tr class="center">
 	    <small>
@@ -292,17 +295,21 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:引数渡し</h1>
-	<li>当初、GCCを使ってコンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
+	<li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
 	<ul>
-	  <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていたため。</li>
+	  <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
 	</ul>
-	<li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに</li>
+	<li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:引数渡し(fastcall)</h1>
-	<li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
-	<li>__code で宣言された関数は自動でfastcall属性が付与される。</li>
+	<h2>fastcall</h2>
+	<ul>
+	  <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
+	  <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
+	</ul>
+	<li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li>
 	<small>
 	<pre>
 if(!TARGET_64BIT) {
@@ -315,20 +322,83 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
+	<h1>CbCの実装:引数渡し</h1>
+	<table width=100% border=1 class="center">
+	  <caption>引数渡しに使われるレジスタの数(gcc)</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>x86_64</td>
+	    <td>6</td>
+	    <td>8</td>
+	    <td>8</td>
+	  </tr>
+	</table>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
 	<h1>CbCの実装:TCE</h1>
 	<h2>Tail Call Elimination(TCE):末尾除去</h2>
 	<li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li>
 	<img src="./pix/continuation.png" style="height: 7em;">
-	<li>CbCにおけるコードセグメントへの継続はこのTCEにより実装されている。</li>
+	<li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE</h1>
+	<li>TCEにより関数へjmp命令で処理を移すことを利用。</li>
+	<li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li>
+	<br>
+	<h2>具体的な実装内容</h2>
+	<ul>
+	  <li class="incremental">try_tail_call(変数名)フラグを立てる。</li>
+	  <li class="incremental">try_tail_callフラグを落とさせない。</li>
+	</ul>
+	<li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:TCE</h1>
-	<li></li>
+	<li>try_tail_callフラグはexpand_call関数で落とされる。</li>
+	<ul>
+	  <li>expand_call関数</li>
+	  <ul>
+	  <li>Treeで表された関数からRTLを生成する関数</li>
+	  </ul>
+	</ul>
+	  <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li>
+	<ul>
+	  <li>caller側とcallee側の戻値の型の一致している。</li>
+	  <li>関数呼び出しがリターン直前に行われている。</li>
+	  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+	  <li>引数の並びのコピーに上書きがない。</li>
+	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>環境付き継続</h1>
+	<h1>CbCの実装:TCE</h1>
+	<li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li>
+	<ul>
+	  <li>void型で統一。</li>
+	  <li>gotoの直後にreturnを置く。</li>
+	  <li>スタックサイズは固定。</li>
+	  <li>引数は一旦、一時変数にコピーする。</li>
+	</ul>
+	<li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:環境付き継続</h1>
 	<li>CbCにおけるCとの互換性を保つための機能。</li>
 	<li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
 	<li></li>