diff presen/index.html @ 73:9250ac87c2c7

modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 03 Jan 2012 14:03:13 +0900
parents 48de60dd51d1
children 275073032132
line wrap: on
line diff
--- a/presen/index.html	Mon Jan 02 07:29:15 2012 +0900
+++ b/presen/index.html	Tue Jan 03 14:03:13 2012 +0900
@@ -100,14 +100,14 @@
       <!-- 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 のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li>
+	<li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
 	<li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
 	<li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
       </div>
@@ -139,40 +139,40 @@
 	<h1>Continuation based C </h1>
 	<h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
 	<ul>
-	  <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li>
-	</ul>
-	<br>
-	<h2>コードセグメント</h2>
+	<li>コードセグメント:CbCにおけるプログラムの基本単位</li>
 	<ul>
-	  <li>C の関数よりも細かい単位。</li>
-	  <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li>
+	  <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>
-	<!--
-	<li>Cでは関数呼び出しの後、呼び出し元の環境に復帰する必要がある。</li>
-	-->
-	<li>Cにおいての継続</li>
+	<h1>Continuation based C </h1>	
+	<ul>
+	<li>継続(C言語):現在の処理を実行していく為の情報</li>
 	<ul>
 	  <li>続く命令のアドレス</li>
 	  <li>命令に必要なデータ</li>
 	  <li>スタックに積まれている値(環境)</li>
 	</ul>
+	</ul>
+	<li class="incremental">CbC: 関数コールが無い -> 呼び出し元への復帰がない</li>
+	<ul class="incremental">
+	<li>CbCの継続:軽量継続(light-weight continuation)</li>
+	<ul>
+	  <li>Cの継続から環境を除外</li>
+	  <li>続く命令とその命令に必要なデータのみ</li>
+	</ul>
+	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>Continuation Based C (軽量継続)</h1>
-	<h2>CbCの継続(軽量継続)</h2>
-	<li>関数コールが無い -> 呼び出し元への復帰がない</li>
-	<ul>
-	  <li>Cの継続から環境を除外</li>
-	  <li>続く命令とその命令に必要なデータのみ</li>
-	</ul>
-<!--	<li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> -->
-<!--	<li>スタックポインタの位置を変えずにすむ。</li> -->
 	<p style=" margin-right:auto; margin-left:auto;">
 	  <table width=90% class="center" border=1>
 	    <tr>
@@ -189,16 +189,18 @@
 	    </tr>
 	  </table>
 	</p>
+	  <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
+	<li>スタックに載るデータは1つのコードセグメントの必要なデータのみ。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>Continuation based C </h1>
-	<small>
 <table width=100% border=1>
-<caption>階乗を求めるCbCのプログラム</caption>
+<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); 
@@ -215,6 +217,7 @@
 </td>
 <td>
 <pre class="srcbox">
+
 __code factorial(int x) {
   goto factorial0(1, x); 
 }
@@ -229,9 +232,11 @@
 </td>
 </tr>
 </table>
-	</small>
-	<li>__code キーワードによるコードセグメントの宣言</li>
-	<li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li>
+	<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">
@@ -239,17 +244,8 @@
 	<li>本来はGnu Compiler Collectionのことを指すが、
 	  <br>ここで扱うのはGnu C Compiler(cc1)になる。</li>
 	  <ul>
-	    <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコード次の4つの内部表現へと変換される。</li>
+	    <li class="incremental">GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
 	  </ul>
-<!--
-	<li>GCCでは、アセンブラのコードを出力するまでに次の4つの内部表現が扱われる。</li>
-	<ol>
-	  <li>Generic Tree</li>
-	  <li>GIMPLE</li>
-	  <li>Tree SSA</li>
-	  <li>RTL</li>
-	</ol>
--->
       </div>
       <!-- PAGE -->
       <div class="slide">
@@ -387,7 +383,7 @@
 	<p class="center">
 	  <img src="./pix/ir.png" style="height: 6em;">
 	</p>
-	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
+	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
 	<li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
       </div>
       <!-- PAGE -->
@@ -463,8 +459,8 @@
 	<h1>CbCの実装</h1>
 	<ul>
 	  <li>シンタックスの追加</li>
+	  <li>末尾除去:Tail Call Elimination(TCE)</li>
 	  <li>レジスタによる引数渡し(fastcall属性の付与)</li>
-	  <li>Tail Call Elimination</li>
      	  <li>環境付き継続</li>
 	  <li>__rectype の実装</li>
 	</ul>
@@ -478,19 +474,55 @@
 	    <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の実装:シンタックスの追加</h1>
 	  <li>goto によるコードセグメントへの継続</li>
 	  <ul>
 	    <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
 	    <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
 	  </ul>
-	</ul>
 	<li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:シンタックスの追加</h1>
 	<h2>gotoシンタックスの追加</h2>
-	  <pre class="srcbox" style="font-size:25px; height:20em;">
+	  <pre class="srcbox" style="font-size:25px; height:17em;">
  case RID_GOTO:
    c_parser_consume_token (parser);
    if ( c_parser_next_token_is (parser, CPP_NAME)
@@ -524,7 +556,7 @@
 	</pre>
 	<small>
 	<li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
-	<li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
+	<li class="incremental">CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
 	<li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li>
 	</small>
       </div>
@@ -532,95 +564,59 @@
       <div class="slide">
 	<h1>CbCの実装:シンタックスの追加</h1>
 	<h2>gotoシンタックスの追加</h2>
-	<li>最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。</li>
+	<ul>
+	  <li>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</li>
+	  <li>最後のリターン文生成も、末尾除去にかける為に必要な処理。</li>
+	</ul>
 	<table border=1 width=100%>
+<!--
+	  <caption><small>return 自動生成</small></caption>
+-->
 	  <tr class="center">
 	    <small>
 	  <td>実際のコード </td>
 	  <td>GCC 内で処理されるコード</td>
 	    </small>
 	  </tr>
-	  <tr style="margin-top: auto;">
+	  <tr class="srctr">
 	  <td>
 	    <pre>
-goto factorial0(1, x); 
+
+__code test() {
+   :
+  goto factorial0(1, x); 
+}
 	    </pre>
 	  </td>
 	  <td>
 	    <pre>
-factorial0(1, x); 
-return;
+
+void test() {
+   :
+  factorial0(1, x); 
+  return;
+}
 	    </pre>
 	  </td>
 	  </tr>
 	</table>
+<!--
 	<li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li>
-      </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>
-	<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>
+	<h2>末尾除去:Tail Call Elimination(TCE)</h2>
 	<ul>
 	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
 	</ul>
-	<li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li>
+	<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);
@@ -635,6 +631,25 @@
   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%;">
@@ -680,24 +695,28 @@
 	<ol>
 	  <li>型はvoid型で統一する。</li>
 	  <li>gotoの直後にreturnを置く。</li>
-	  <li>スタックサイズは固定する。</li>
+	  <li>スタックサイズは固定にする。</li>
 	  <li>引数は一旦、一時変数にコピーする。</li>
 	</ol>
-	</small>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:TCE(末尾除去)</h1>
 	<li>TCEの条件はexpand_call関数で調べられる。</li>
 	<ul>
+	  <li>expand_call関数</li>
+	<ul>
 	  <li>Treeで表された関数からRTLを生成する関数</li>
 	  <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
 	  <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
 	</ul>
-	<li>具体的な実装</li>
+	<li class="incremental">具体的な実装内容</li>
 	<ul>
-	  <li>try_tail_callフラグを落とすif文の条件をかわす。</li>
+	  <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
+	  <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
 	</ul>
+	<ul>
+
       </div>
       <!-- PAGE -->
 <!--
@@ -824,7 +843,7 @@
 	<table width=100%>
 	  <tr class="srctr">
 	    <td>
-	  <pre>
+	  <pre class="srcbox">
 #ifndef noCbC
   if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
       && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
@@ -841,10 +860,14 @@
 	  </td>
 	  </tr>
 	  </table>
+	<ul>
+	  <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
+	    <br><small>(最適化の矯正付与)</small></li>
+	</ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<h1>CbCの実装:TCE(末尾除去)の実装について</h1>
 	<ul>
 	  <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作って条件を回避させていた。</li>
 	  <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
@@ -852,6 +875,16 @@
 	</ul>
       </div>
       <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装</h1>
+	<ul>
+	  <li>シンタックスの追加</li>
+	  <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
+	</ul>
+	<li>この2つがGCCにおけるCbC実装の基本の部分となる。</li>
+	<li class="incremental">ここからはCbCの機能の拡張になる。</li>
+      </div>
+      <!-- PAGE -->
 <!--
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>
@@ -875,6 +908,64 @@
 -->
        <!-- 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>
+	  <li></li>
+	</ul>
+
+	<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の実装:環境付き継続</h1>
 	<ul>
 	<li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
@@ -900,10 +991,15 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>
-	<h2>実際には以下のコードを生成している。</h2>
-	<small>
-	  <pre class="srcbox">
-
+	<li><small>生成しているコードと生成する為のコード</small></li>
+	<table border=1 width=100%>
+	  <tr>
+	    <td><small>生成しているコード</small></td>
+	    <td><small>生成する為のコード</small></td>
+	  </tr>
+	  <tr class="srctr">
+	    <td width=50% class="srctd">
+	  <pre class="srcbox" style="width:25em;">
 goto c1(__return, __environment);
 
 goto c1(({
@@ -920,18 +1016,10 @@
 	  _cbc_internal_return;
 	}), __environment);
 	  </pre>
-	  <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p>
-	</small>
-	<li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li>
-      </div>
-      <!-- PAGE -->
-<!--
-      <div class="slide">
-	<h1>CbCの実装:環境付き継続</l>
-	<h2>環境付き継続の生成部分:</h2>
-	<div class="src">
-	  <small>
-	  <pre>
+	    </td>
+	    <td width=50% class="srctd">
+	      <pre class="srcbox" style="width:25em;">
+    case RID_CbC_RET:
 {
   tree value, stmt, label, tlab, decl;
   c_parser_consume_token (parser);
@@ -976,11 +1064,12 @@
   expr.value = c_finish_stmt_expr (location, stmt);
   expr.original_code = ERROR_MARK;
 }
-	  </pre>
-	</small>
-	</div>
+	    </td>
+	  </tr>
+	  </table>
+	  <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p>
+	<li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
       </div>
--->
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>