changeset 71:64d22e65489c

modify TCE
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 02 Jan 2012 05:34:11 +0900
parents 79894ca66a9a
children 48de60dd51d1
files presen/index.html
diffstat 1 files changed, 85 insertions(+), 40 deletions(-) [+]
line wrap: on
line diff
--- a/presen/index.html	Sat Dec 31 11:55:47 2011 +0900
+++ b/presen/index.html	Mon Jan 02 05:34:11 2012 +0900
@@ -4,15 +4,16 @@
 <html xmlns="http://www.w3.org/1999/xhtml">
 
 <head>
-<style>
-td.box {
-height: 80%;
-overflow: scroll;
+<style type="text/css">
+tr.srctr {
+font-size:28px;
+}
+td.srctd {
+height:20em;
 }
 pre.srcbox {
-height: 80%;
+height: 100%;
 overflow: scroll;
-font-size: 25px;
 }
 .src{
 overflow: scroll;
@@ -194,8 +195,8 @@
 	<h1>Continuation based C </h1>
 	<small>
 <table width=100% border=1>
-<tr>
 <caption>階乗を求めるCbCのプログラム</caption>
+<tr class="srctr">
 <td width=50%>
 	  <pre class="srcbox">
 __code print_factorial(int prod) {
@@ -269,10 +270,9 @@
 	    <td>Generic(ソースコード)</td>
 	    <td>GIMPLE</td>
 	  </tr>
-	  <tr>
+	  <tr class="srctr">
 	    <td>
-	      <small>
-		<pre class="srcbox" style="height:20em; font-size:25px;">
+               <pre class="srcbox">
 void factorial(int x)
 {
   int prod,i;
@@ -282,11 +282,9 @@
   print_factorial(prod);
 }
 	      </pre>
-	      </small>
 	    </td>
-	    <td>
-	      <small>
-		<pre class="srcbox" style="height:20em; font-size:25px;">
+	    <td width=50%>
+		<pre class="srcbox">
 factorial (int x)
 {
   int prod;
@@ -305,22 +303,20 @@
 }
 	      </pre>
 	    </td>
-	      </small>
 	    </tr>
 	</table>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC</h1>
-	<table width=100% border=1>
+	<table border=1 width=100% height=100%>
 	  <tr>
 	    <td width=50%>SSA</td>
 	    <td width=50%>RTL</td>
 	  </tr>
-	  <tr>
-	    <td>
-	      <small>
-		<pre class="srcbox" style="height:20em; font-size:25px;">
+	  <tr class="srctr">
+	    <td class="srctd">
+		<pre class="srcbox">
 factorial (int x)
 {
   int i;
@@ -349,15 +345,13 @@
 }
 
 		</pre>
-	      </small>
 	    </td>
-	    <td>
-		<pre class="srcbox" style="font-size:25px; height:20em; width:25em;">
+	    <td class="srctd">
+		<pre class="srcbox" style="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>
@@ -591,16 +585,17 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE</h1>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
 	<h2>Tail Call Elimination(TCE):末尾除去</h2>
 	<ul>
 	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
 	</ul>
 	<li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li>
+	<br>
 	<table width=100%>
-	  <td>
-	<small>
-	<pre>
+	  <tr class="srctr">
+	  <td width=50%>
+	<pre class="srcbox">
 int main() {
   int num = a(2);
   printf("main:num=%d\n",num);
@@ -613,18 +608,17 @@
   printf("b:a = %d\n",num);
   return num+3;
 }	  
-	</small>
 	</pre>
 	  </td>
 	  <td class="center">
-	    <img src="./pix/continuation.png" style="height: 8em;">
+	    <img src="./pix/continuation.png" style="height:100%;">
 	    </td>
 	    </tr>
 	</table>
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCEの動作</h1>
+	<h1>CbCの実装:TCE(末尾除去)の動作</h1>
 	<li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
 	<table width=100% border=1>
 	  <td>
@@ -644,7 +638,7 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE</h1>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
 	<li>TCEにかかる条件</li>
 	<ol>
 	  <li>caller側とcallee側の戻値の型の一致している。</li>
@@ -655,7 +649,7 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE</h1>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
 	<li>条件を回避する為以下の実装にする。</li>
 	<ol>
 	  <li>型はvoid型で統一する。</li>
@@ -667,7 +661,7 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE</h1>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
 	<li>TCEの条件はexpand_call関数で調べられる。</li>
 	<ul>
 	  <li>Treeで表された関数からRTLを生成する関数</li>
@@ -692,8 +686,54 @@
 -->
       <!-- PAGE -->
       <div class="slide">
-	<h1>CbCの実装:TCE</h1>
-	<li></li>
+	<h1>CbCの実装:TCE(末尾除去)</h1>
+	<li>try_tail_callフラグが落とされるif文</li>
+	<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;
+	</pre>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<li>try_tail_callフラグが落とされる部分</li>
+	<table>
+	  <tr class="srctr">
+	    <td class="srctd">
+	<pre class="srcbox">
+  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;
+	</pre>
+	    </td>
+	    </tr>
+	  </table>
+
       </div>
       <!-- PAGE -->
 <!--
@@ -725,8 +765,10 @@
 	<li>__returnキーワードを引数に渡すことで使うことができる。</li>
 	</ul>
 	<li>以下の使い方の場合は1を返す。</li>
+	<table border=1 width=100%>
+	    <td>
 	<small>
-	<pre>
+	    <pre class="srcbox">
 __code c1(__code ret(int,void *),void *env) {
  goto ret(1,env);
 }
@@ -734,15 +776,18 @@
  goto c1(__return, __environment);
 }
 	</pre>
-	</small>
-	<p><small>__environmentキーワードは関数の環境を保存している。</small></p>
+	    </small>
+	</td>
+	    </table>
+	<p><small>__environmentキーワードは関数の環境を保持する。</small></p>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:環境付き継続</h1>
 	<h2>実際には以下のコードを生成している。</h2>
 	<small>
-	  <pre>
+	  <pre class="srcbox">
+
 goto c1(__return, __environment);
 
 goto c1(({