changeset 70:79894ca66a9a

modify explanation of GCC
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 31 Dec 2011 11:55:47 +0900
parents 9dc6013b0559
children 64d22e65489c
files presen/#test.c# presen/index.html
diffstat 2 files changed, 204 insertions(+), 76 deletions(-) [+]
line wrap: on
line diff
--- a/presen/#test.c#	Thu Dec 29 18:19:44 2011 +0900
+++ b/presen/#test.c#	Sat Dec 31 11:55:47 2011 +0900
@@ -0,0 +1,1 @@
+
--- a/presen/index.html	Thu Dec 29 18:19:44 2011 +0900
+++ b/presen/index.html	Sat Dec 31 11:55:47 2011 +0900
@@ -5,6 +5,15 @@
 
 <head>
 <style>
+td.box {
+height: 80%;
+overflow: scroll;
+}
+pre.srcbox {
+height: 80%;
+overflow: scroll;
+font-size: 25px;
+}
 .src{
 overflow: scroll;
 width: 90%;
@@ -188,7 +197,7 @@
 <tr>
 <caption>階乗を求めるCbCのプログラム</caption>
 <td width=50%>
-	  <pre>
+	  <pre class="srcbox">
 __code print_factorial(int prod) {
   printf("factorial = %d\n",prod);
   exit(0); 
@@ -204,7 +213,7 @@
 	  </pre>
 </td>
 <td>
-<pre>
+<pre class="srcbox">
 __code factorial(int x) {
   goto factorial0(1, x); 
 }
@@ -227,26 +236,134 @@
       <div class="slide">
 	<h1>GCC</h1>
 	<li>本来はGnu Compiler Collectionのことを指すが、
-	  <br>ここで扱うのはGnu C Compilerになる。</li>
-	<li>GCCでは次の4つの内部表現が扱われる。</li>
+	  <br>ここで扱うのはGnu C Compiler(cc1)になる。</li>
+	  <ul>
+	    <li>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">
+	<h1>GCC</h1>
+	<ol>
+	  <li>Generic Tree:ソースコードを構文木の形に直したもの</li>
+	  <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li>
+	  <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li>
+	  <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
+	</ol>
+	<li class="incremental">それぞれは次のようなデータを構文木にして持っている。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC</h1>
-	<li>Generic Tree:ソースコードを構文木の形に直したもの</li>
-	<li>GIMPLE: Generic Treeの命令を簡単にした構文木</li>
-	<li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li>
-	<li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
+	<table width=100% border=1>
+	  <tr>
+	    <td>Generic(ソースコード)</td>
+	    <td>GIMPLE</td>
+	  </tr>
+	  <tr>
+	    <td>
+	      <small>
+		<pre class="srcbox" style="height:20em; font-size:25px;">
+void factorial(int x)
+{
+  int prod,i;
+  for(i=1,prod=1; i <= x; i++){
+    prod = prod*i;
+  }
+  print_factorial(prod);
+}
+	      </pre>
+	      </small>
+	    </td>
+	    <td>
+	      <small>
+		<pre class="srcbox" style="height:20em; font-size:25px;">
+factorial (int x)
+{
+  int prod;
+  int i;
+
+  i = 1;
+  prod = 1;
+  goto &lt;D.2846&gt;;
+  &lt;D.2845&gt;:
+  prod = prod * i;
+  i = i + 1;
+  &lt;D.2846&gt;:
+  if (i &lt;= x) goto &lt;D.2845&gt;; else goto &lt;D.2847&gt;;
+  &lt;D.2847&gt;:
+  print_factorial (prod);
+}
+	      </pre>
+	    </td>
+	      </small>
+	    </tr>
+	</table>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC</h1>
+	<table width=100% border=1>
+	  <tr>
+	    <td width=50%>SSA</td>
+	    <td width=50%>RTL</td>
+	  </tr>
+	  <tr>
+	    <td>
+	      <small>
+		<pre class="srcbox" style="height:20em; font-size:25px;">
+factorial (int x)
+{
+  int i;
+  int prod;
+
+&lt;bb 2&gt;:
+  i_3 = 1;
+  prod_4 = 1;
+  goto &lt;bb 4&gt;;
+
+&lt;bb 3&gt;:
+  prod_6 = prod_1 * i_2;
+  i_7 = i_2 + 1;
+
+&lt;bb 4&gt;:
+  # prod_1 = PHI &lt;prod_4(2), prod_6(3)&gt;
+  # i_2 = PHI &lt;i_3(2), i_7(3)&gt;
+  if (i_2 &lt;= x_5(D))
+    goto &lt;bb 3&gt;;
+  else
+    goto &lt;bb 5&gt;;
+
+&lt;bb 5&gt;:
+  print_factorial (prod_1);
+  return;
+}
+
+		</pre>
+	      </small>
+	    </td>
+	    <td>
+		<pre class="srcbox" style="font-size:25px; height:20em; width:25em;">
+(call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403]  &lt;function_decl 0x146f6b200 print_factorial&gt;) [0 S1 A8])
+        (const_int 0 [0]))
+              </pre>
+	    </td>
+
+	  </tr>
+      </table>
+      </div>
+      <!-- PAGE -->      
+      <div class="slide">
+	<h1>GCC</h1>
 	<p class="center">
 	  <img src="./pix/ir.png" style="height: 6em;">
 	</p>
@@ -353,21 +470,38 @@
       <div class="slide">
 	<h1>CbCの実装:シンタックスの追加</h1>
 	<h2>gotoシンタックスの追加</h2>
-	<small>
-	<pre>
-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 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)
+	&& 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>
-	</small>
 	<small>
 	<li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
 	<li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
@@ -378,7 +512,7 @@
       <div class="slide">
 	<h1>CbCの実装:シンタックスの追加</h1>
 	<h2>gotoシンタックスの追加</h2>
-	<li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li>
+	<li>最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。</li>
 	<table border=1 width=100%>
 	  <tr class="center">
 	    <small>
@@ -419,7 +553,7 @@
 	  <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
 	  <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
 	</ul>
-	<li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを挿入。</li>
+	<li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
 	<small>
 	<pre>
 if(!TARGET_64BIT) {
@@ -468,15 +602,15 @@
 	<small>
 	<pre>
 int main() {
-  int a = f(2);
+  int num = a(2);
   printf("main:num=%d\n",num);
   return 0;
 }
 int a(int num) {
-  return g(num+5);
+  return b(num+5);
 }
 int b(int num) {
-  printf("g:a = %d\n",num);
+  printf("b:a = %d\n",num);
   return num+3;
 }	  
 	</small>
@@ -491,13 +625,21 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:TCEの動作</h1>
-	<li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
-	<ul>
-	<li>jmp命令により呼び出し元関数と同じ範囲のスタックを使うことになる。</li>
-	</ul>
+	<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 class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
 	    <li class="incremental">TCEにかかるには条件が幾つかある。</li>
       </div>
       <!-- PAGE -->
@@ -516,9 +658,9 @@
 	<h1>CbCの実装:TCE</h1>
 	<li>条件を回避する為以下の実装にする。</li>
 	<ol>
-	  <li>型はvoid型で統一。</li>
+	  <li>型はvoid型で統一する。</li>
 	  <li>gotoの直後にreturnを置く。</li>
-	  <li>スタックサイズは固定。</li>
+	  <li>スタックサイズは固定する。</li>
 	  <li>引数は一旦、一時変数にコピーする。</li>
 	</ol>
 	</small>
@@ -526,51 +668,32 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:TCE</h1>
-	<li>コードセグメントの継続 -> TCEにより吐かれるjmp命令を利用。</li>
+	<li>TCEの条件はexpand_call関数で調べられる。</li>
+	<ul>
+	  <li>Treeで表された関数からRTLを生成する関数</li>
+	  <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
+	  <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
+	</ul>
+	<li>具体的な実装</li>
+	<ul>
+	  <li>try_tail_callフラグを落とさせない処理が追加されている。</li>
+	</ul>
+      </div>
+      <!-- PAGE -->
 <!--
-	<li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li>
+      <div class="slide">
+	<h1>CbCの実装:TCE</h1>
+	<li>TCEにかかる条件</li>
+	<ul>
+	  <li>try_tail_callフラグを落とさせない。</li>
+	</ul>
+	<li></li>
+      </div>
 -->
-	<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>try_tail_callフラグはexpand_call関数で落とされる。</li>
-	<ul>
-	  <li>expand_call関数</li>
-	  <ul>
-	  <li>Treeで表された関数からRTLを生成する関数</li>
-	  </ul>
-	</ul>
-	  <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li>
-	  <small>
-	<ol>
-	  <li>caller側とcallee側の戻値の型の一致している。</li>
-	  <li>関数呼び出しがリターン直前に行われている。</li>
-	  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
-	  <li>引数の並びのコピーに上書きがない。</li>
-	</ol>
-	</small>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
-	<h1>CbCの実装:TCE</h1>
-	<li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li>
-	<small>
-	<ol>
-	  <li>型はvoid型で統一。</li>
-	  <li>gotoの直後にreturnを置く。</li>
-	  <li>スタックサイズは固定。</li>
-	  <li>引数は一旦、一時変数にコピーする。</li>
-	</ol>
-	</small>
-	<li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li>
+	<li></li>
       </div>
       <!-- PAGE -->
 <!--
@@ -597,8 +720,10 @@
        <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>
+	<ul>
 	<li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
 	<li>__returnキーワードを引数に渡すことで使うことができる。</li>
+	</ul>
 	<li>以下の使い方の場合は1を返す。</li>
 	<small>
 	<pre>
@@ -639,6 +764,7 @@
 	<li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li>
       </div>
       <!-- PAGE -->
+<!--
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</l>
 	<h2>環境付き継続の生成部分:</h2>
@@ -693,6 +819,7 @@
 	</small>
 	</div>
       </div>
+-->
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>
@@ -794,12 +921,12 @@
 }
 	</pre>
 	</small>
-	<li>以下の様に扱えるようにしたい。</li>
+	<li>以下の様に引数に()をつけて受けてることをやめたい。</li>
 	<small>
 	<pre>
 void factorial(int n, int result, void *print){
    :
-   (*print)(n,result,print,exit1, envp);
+   void(*print)(n,result,print,exit1, envp);
 }
 	</pre>
 </small>
@@ -811,7 +938,7 @@
 	<pre>
 __code factorial(int n, int result, __rectype *print) {
    :
-   (*print)(n,result,print,exit1, envp);
+   goto (*print)(n,result,print,exit1, envp);
 }
 	</pre>
       </div>