Mercurial > hg > Papers > 2011 > nobu-prosym

changeset 69:9dc6013b0559

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of tce
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 29 Dec 2011 18:19:44 +0900
parents 1399414ea3f6
children 79894ca66a9a
files presen/index.html presen/omni/func_call.graffle presen/pix/continuation.png
diffstat 3 files changed, 81 insertions(+), 153 deletions(-) [+]
line wrap: on
line diff
--- a/presen/index.html	Thu Dec 29 16:01:24 2011 +0900
+++ b/presen/index.html	Thu Dec 29 18:19:44 2011 +0900
@@ -247,11 +247,11 @@
       <!-- PAGE -->
       <div class="slide">
 	<h1>GCC</h1>
-	<li>CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
 	<p class="center">
-	<img src="./pix/ir.png" style="height: 6em;">
+	  <img src="./pix/ir.png" style="height: 6em;">
 	</p>
-	<li class="incremental">Generic Tree生成部分について触れてみる。</li>
+	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
+	<li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
@@ -259,10 +259,17 @@
 	<li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
 	<table class="center" width=100%  border=1>
 	  <tr>
+	    <td></td>
 	    <td><small>値の代入:MODIFY_EXPR</small></td>
 	    <td><small>関数呼び出し:CALL_EXPR</small></td>
 	  </t>
 	  <tr>
+	    <td>命令</td>
+	    <td>b = a * 10</td>
+	    <td>func(a,10)</td>
+	  </t>
+	  <tr>
+	    <td><small>Generic<br>Tree</small></td>
 	  <td>
 	    <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
 	  </td>
@@ -302,7 +309,7 @@
 	  </td>
 	  </tr>
 	    </table>
-	  <li>CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
+	  <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
       </div>
       <!-- PAGE -->
 <!--
@@ -364,7 +371,7 @@
 	<small>
 	<li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
 	<li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
-	<li>最後にc_finish_return関数によりreturn文を生成している。</li>
+	<li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li>
 	</small>
       </div>
       <!-- PAGE -->
@@ -412,7 +419,7 @@
 	  <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
 	  <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
 	</ul>
-	<li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li>
+	<li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを挿入。</li>
 	<small>
 	<pre>
 if(!TARGET_64BIT) {
@@ -452,15 +459,77 @@
       <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;">
+	<ul>
+	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
+	</ul>
+	<li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li>
+	<table width=100%>
+	  <td>
+	<small>
+	<pre>
+int main() {
+  int a = f(2);
+  printf("main:num=%d\n",num);
+  return 0;
+}
+int a(int num) {
+  return g(num+5);
+}
+int b(int num) {
+  printf("g:a = %d\n",num);
+  return num+3;
+}	  
+	</small>
+	</pre>
+	  </td>
+	  <td class="center">
+	    <img src="./pix/continuation.png" style="height: 8em;">
+	    </td>
+	    </tr>
+	</table>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCEの動作</h1>
 	<li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
+	<ul>
+	<li>jmp命令により呼び出し元関数と同じ範囲のスタックを使うことになる。</li>
+	</ul>
+	  <p class="center">
+	    <img src="./pix/tce.png" style="height: 6em;">
+	    </p>
+	    <li class="incremental">TCEにかかるには条件が幾つかある。</li>
       </div>
       <!-- PAGE -->
       <div class="slide">
 	<h1>CbCの実装:TCE</h1>
-	<li>TCEにより関数へjmp命令で処理を移すことを利用。</li>
+	<li>TCEにかかる条件</li>
+	<ol>
+	  <li>caller側とcallee側の戻値の型の一致している。</li>
+	  <li>関数呼び出しがリターン直前に行われている。</li>
+	  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+	  <li>引数の並びのコピーに上書きがない。</li>
+	</ol>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE</h1>
+	<li>条件を回避する為以下の実装にする。</li>
+	<ol>
+	  <li>型はvoid型で統一。</li>
+	  <li>gotoの直後にreturnを置く。</li>
+	  <li>スタックサイズは固定。</li>
+	  <li>引数は一旦、一時変数にコピーする。</li>
+	</ol>
+	</small>
+      </div>
+      <!-- PAGE -->
+      <div class="slide">
+	<h1>CbCの実装:TCE</h1>
+	<li>コードセグメントの継続 -> TCEにより吐かれるjmp命令を利用。</li>
+<!--
 	<li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li>
+-->
 	<br>
 	<h2>具体的な実装内容</h2>
 	<ul>
--- a/presen/omni/func_call.graffle	Thu Dec 29 16:01:24 2011 +0900
+++ b/presen/omni/func_call.graffle	Thu Dec 29 18:19:44 2011 +0900
@@ -44,66 +44,12 @@
 	<key>Creator</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>DisplayScale</key>
-	<string>1 0/72 in = 1 0/72 in</string>
+	<string>1 0/72 in = 1.0000 in</string>
 	<key>GraphDocumentVersion</key>
 	<integer>8</integer>
 	<key>GraphicsList</key>
 	<array>
 		<dict>
-			<key>AllowLabelDrop</key>
-			<false/>
-			<key>Class</key>
-			<string>LineGraphic</string>
-			<key>ID</key>
-			<integer>76</integer>
-			<key>Points</key>
-			<array>
-				<string>{302.5, 202.25}</string>
-				<string>{318.5, 202.25}</string>
-			</array>
-			<key>Style</key>
-			<dict>
-				<key>stroke</key>
-				<dict>
-					<key>HeadArrow</key>
-					<string>FilledArrow</string>
-					<key>HeadScale</key>
-					<real>0.82857084274291992</real>
-					<key>TailArrow</key>
-					<string>0</string>
-					<key>TailScale</key>
-					<real>0.5</real>
-				</dict>
-			</dict>
-		</dict>
-		<dict>
-			<key>AllowLabelDrop</key>
-			<false/>
-			<key>Class</key>
-			<string>LineGraphic</string>
-			<key>ID</key>
-			<integer>75</integer>
-			<key>Points</key>
-			<array>
-				<string>{202.75, 228.25}</string>
-				<string>{218.75, 228.25}</string>
-			</array>
-			<key>Style</key>
-			<dict>
-				<key>stroke</key>
-				<dict>
-					<key>HeadArrow</key>
-					<string>FilledArrow</string>
-					<key>HeadScale</key>
-					<real>0.82857084274291992</real>
-					<key>TailArrow</key>
-					<string>0</string>
-					<key>TailScale</key>
-					<real>0.5</real>
-				</dict>
-			</dict>
-		</dict>
-		<dict>
 			<key>Bounds</key>
 			<string>{{148.5, 334.59875}, {58, 22}}</string>
 			<key>Class</key>
@@ -558,93 +504,6 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{40.5, 276.75}, {69, 22}}</string>
-			<key>Class</key>
-			<string>ShapedGraphic</string>
-			<key>ID</key>
-			<integer>50</integer>
-			<key>Magnets</key>
-			<array>
-				<string>{1, 1}</string>
-				<string>{1, -1}</string>
-				<string>{-1, -1}</string>
-				<string>{-1, 1}</string>
-				<string>{0, 1}</string>
-				<string>{0, -1}</string>
-				<string>{1, 0}</string>
-				<string>{-1, 0}</string>
-				<string>{-0.5, -0.233518}</string>
-				<string>{-0.49144199, 0.26006299}</string>
-				<string>{0.50711799, -0.224086}</string>
-				<string>{0.50711799, 0.26717901}</string>
-				<string>{-0.27430999, -0.47402799}</string>
-				<string>{0.27978, -0.47847801}</string>
-				<string>{0.29393801, 0.54304397}</string>
-				<string>{-0.28623199, 0.55380398}</string>
-			</array>
-			<key>Shape</key>
-			<string>Rectangle</string>
-			<key>Style</key>
-			<dict>
-				<key>fill</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-				<key>shadow</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-				<key>stroke</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-			</dict>
-			<key>Text</key>
-			<dict>
-				<key>Text</key>
-				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
-{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;}
-\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
-
-\f0\fs28 \cf0 Stack\
-Pointer}</string>
-				<key>VerticalPad</key>
-				<integer>0</integer>
-			</dict>
-		</dict>
-		<dict>
-			<key>AllowLabelDrop</key>
-			<false/>
-			<key>Class</key>
-			<string>LineGraphic</string>
-			<key>ID</key>
-			<integer>49</integer>
-			<key>Points</key>
-			<array>
-				<string>{102.5, 287.25}</string>
-				<string>{118.5, 287.25}</string>
-			</array>
-			<key>Style</key>
-			<dict>
-				<key>stroke</key>
-				<dict>
-					<key>HeadArrow</key>
-					<string>FilledArrow</string>
-					<key>HeadScale</key>
-					<real>0.82857084274291992</real>
-					<key>TailArrow</key>
-					<string>0</string>
-					<key>TailScale</key>
-					<real>0.5</real>
-				</dict>
-			</dict>
-		</dict>
-		<dict>
-			<key>Bounds</key>
 			<string>{{305.5, 148}, {58, 22}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
@@ -999,7 +858,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2011-12-28 16:28:04 +0000</string>
+	<string>2011-12-29 09:00:29 +0000</string>
 	<key>Modifier</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>NotesVisible</key>
@@ -1080,7 +939,7 @@
 			</dict>
 		</array>
 		<key>Frame</key>
-		<string>{{328, 65}, {693, 938}}</string>
+		<string>{{449, 64}, {693, 938}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
Binary file presen/pix/continuation.png has changed