Mercurial > hg > Papers > 2011 > nobu-prosym
annotate presen/index.html @ 68:1399414ea3f6
modify explanation of Generic Tree
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 29 Dec 2011 16:01:24 +0900 |
parents | 26a3713b2989 |
children | 9dc6013b0559 |
rev | line source |
---|---|
54 | 1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" |
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> | |
3 | |
4 <html xmlns="http://www.w3.org/1999/xhtml"> | |
5 | |
6 <head> | |
7 <style> | |
64 | 8 .src{ |
9 overflow: scroll; | |
10 width: 90%; | |
11 height: 60%; | |
12 } | |
54 | 13 .center { |
14 margin-left: auto; | |
15 margin-right: auto; | |
16 text-align: center; | |
17 } | |
18 .textcenter { | |
19 text-align: center; | |
20 } | |
21 .taninaritop { | |
22 margin: auto; | |
23 width: 95%; | |
24 font-weight: bold; | |
25 } | |
26 </style> | |
27 <title>2012/ 1/ 7</title> | |
28 <!-- metadata --> | |
29 <meta name="generator" content="S5" /> | |
30 <meta name="version" content="S5 1.1" /> | |
31 <meta name="presdate" content="20120107" /> | |
32 <meta name="author" content="Nobuyasu Oshiro" /> | |
33 <meta name="company" content="University of the Ryukyu" /> | |
34 <!-- meta temporary --> | |
35 <meta http-equiv="content-type" content="text/html; charset=utf-8" /> | |
36 <meta http-equiv="Content-Script-Type" content="text/javascript" /> | |
37 <meta http-equiv="Content-Style-Type" content="text/css" /> | |
38 <!-- configuration parameters --> | |
39 <meta name="defaultView" content="slideshow" /> | |
40 <meta name="controlVis" content="hidden" /> | |
41 <!-- configuration extensions --> | |
42 <meta name="tranSitions" content="true" /> | |
43 <meta name="fadeDuration" content="500" /> | |
44 <meta name="incrDuration" content="250" /> | |
45 <!-- configuration autoplay extension --> | |
46 <meta name="autoMatic" content="false" /> | |
47 <meta name="playLoop" content="true" /> | |
48 <meta name="playDelay" content="10" /> | |
49 <!-- configuration audio extension --> | |
50 <meta name="audioSupport" content="false" /> | |
51 <meta name="audioVolume" content="100" /> | |
52 <meta name="audioError" content="false" /> | |
53 <!-- configuration audio debug --> | |
54 <meta name="audioDebug" content="false" /> | |
55 <!-- style sheet links --> | |
56 <link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" /> | |
57 <link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" /> | |
58 <link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" /> | |
59 <link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" /> | |
60 <!-- embedded styles --> | |
61 <style type="text/css" media="all"> | |
62 .imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;} | |
63 #anim {width: 33%; height: 320px; position: relative;} | |
64 #anim img {position: absolute; top: 0px; left: 0px;} | |
65 </style> | |
66 <!-- S5 JS --> | |
67 <script src="ui/default_utf/slides.js" type="text/javascript"></script> | |
68 </head> | |
69 <body> | |
70 | |
71 <div class="layout"> | |
72 <div id="controls"><!-- DO NOT EDIT --></div> | |
73 <div id="currentSlide"><!-- DO NOT EDIT --></div> | |
74 <div id="header"></div> | |
75 <div id="footer"> | |
76 <h1>プログラミングシンポジウム: 2012/ 1/ 7</h1> | |
77 <h2>並列信頼研</h2> | |
78 </div> | |
79 </div> | |
80 | |
81 <div class="presentation"> | |
82 | |
83 <div class="slide"> | |
84 <h1>Continuation based Cの GCC 4.6 上の実装について</li> | |
85 <h3></h3> | |
86 <li>大城 信康</li> | |
87 <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4> | |
88 <div class="handout"></div> | |
89 </div> | |
90 <!-- PAGE --> | |
91 <div class="slide"> | |
92 <h1>目的と背景(1)</h1> | |
93 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> | |
94 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> | |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
95 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li> |
54 | 96 </div> |
97 <!-- PAGE --> | |
98 <div class="slide"> | |
99 <h1>目的と背景(2)</h1> | |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
100 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
101 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> |
58 | 102 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> |
54 | 103 </div> |
104 <!-- PAGE --> | |
105 <div class="slide"> | |
106 <h1>発表内容</h1> | |
107 <ol> | |
108 <li>CbC の紹介</li> | |
109 <li>GCC でのコンパイルの流れ</li> | |
58 | 110 <font color="red"> |
111 <li>CbC の実装</li> | |
112 </font> | |
54 | 113 <!-- |
114 <ul> | |
115 <li>Tail Call Elimination</li> | |
116 <li>goto シンタックスの追加</li> | |
117 <li>環境付き継続</li> | |
118 </ul> | |
119 --> | |
120 <li>Micro-C との性能比較</li> | |
64 | 121 <!-- |
54 | 122 <li>mercurial を用いたアップデートの方法</li> |
64 | 123 --> |
54 | 124 <li>まとめ</li> |
125 <ol> | |
126 </div> | |
127 <!-- PAGE --> | |
128 <div class="slide"> | |
129 <h1>Continuation based C </h1> | |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
131 <ul> |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
132 <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
133 </ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
134 <br> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
135 <h2>コードセグメント</h2> |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
136 <ul> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
137 <li>C の関数よりも細かい単位。</li> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
138 <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
139 </ul> |
54 | 140 </div> |
141 <!-- PAGE --> | |
142 <div class="slide"> | |
58 | 143 <h1>Continuation Based C</h1> |
144 <h2>継続:現在の処理を実行していく為の情報</h2> | |
145 <!-- | |
146 <li>Cでは関数呼び出しの後、呼び出し元の環境に復帰する必要がある。</li> | |
147 --> | |
148 <li>Cにおいての継続</li> | |
149 <ul> | |
150 <li>続く命令のアドレス</li> | |
151 <li>命令に必要なデータ</li> | |
152 <li>スタックに積まれている値(環境)</li> | |
153 </ul> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
154 </div> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
155 <!-- PAGE --> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
156 <div class="slide"> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
157 <h1>Continuation Based C (軽量継続)</h1> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
158 <h2>CbCの継続(軽量継続)</h2> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
159 <li>関数コールが無い -> 呼び出し元への復帰がない</li> |
58 | 160 <ul> |
59
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
161 <li>Cの継続から環境を除外</li> |
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
162 <li>続く命令とその命令に必要なデータのみ</li> |
58 | 163 </ul> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
164 <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> --> |
59
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
165 <!-- <li>スタックポインタの位置を変えずにすむ。</li> --> |
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
166 <p style=" margin-right:auto; margin-left:auto;"> |
66
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
167 <table width=90% class="center" border=1> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
168 <tr> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
169 <td><small>Cの関数呼び出し</small></td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
170 <td><small>CbCの継続</></small></td> |
66
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
171 </tr> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
172 <tr> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
173 <td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
174 <img class="scale" src="./pix/func_call.png" style="height: 6em;"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
175 </td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
176 <td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
177 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
178 </td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
179 </tr> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
180 </table> |
59
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
181 </p> |
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
182 </div> |
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
183 <!-- PAGE --> |
58 | 184 <div class="slide"> |
54 | 185 <h1>Continuation based C </h1> |
186 <small> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
187 <table width=100% border=1> |
54 | 188 <tr> |
189 <caption>階乗を求めるCbCのプログラム</caption> | |
190 <td width=50%> | |
191 <pre> | |
192 __code print_factorial(int prod) { | |
193 printf("factorial = %d\n",prod); | |
194 exit(0); | |
195 } | |
58 | 196 |
54 | 197 __code factorial0(int prod, int x) { |
198 if ( x >= 1) { | |
199 goto factorial0(prod*x, x-1); | |
200 }else{ | |
201 goto print_factorial(prod); | |
202 } | |
203 } | |
204 </pre> | |
205 </td> | |
206 <td> | |
207 <pre> | |
208 __code factorial(int x) { | |
209 goto factorial0(1, x); | |
210 } | |
58 | 211 |
54 | 212 int main(int argc, char **argv) { |
213 int i; | |
214 i = atoi(argv[1]); | |
215 goto factorial(i); | |
216 return 0; | |
217 } | |
218 </pre> | |
219 </td> | |
220 </tr> | |
221 </table> | |
222 </small> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
223 <li>__code キーワードによるコードセグメントの宣言</li> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
224 <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li> |
54 | 225 </div> |
226 <!-- PAGE --> | |
227 <div class="slide"> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
228 <h1>GCC</h1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
229 <li>本来はGnu Compiler Collectionのことを指すが、 |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
230 <br>ここで扱うのはGnu C Compilerになる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
231 <li>GCCでは次の4つの内部表現が扱われる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
232 <ol> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
233 <li>Generic Tree</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
234 <li>GIMPLE</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
235 <li>Tree SSA</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
236 <li>RTL</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
237 </ol> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
238 </div> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
239 <!-- PAGE --> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
240 <div class="slide"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
241 <h1>GCC</h1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
242 <li>Generic Tree:ソースコードを構文木の形に直したもの</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
243 <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
244 <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
245 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
246 </div> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
247 <!-- PAGE --> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
248 <div class="slide"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
249 <h1>GCC</h1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
250 <li>CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
251 <p class="center"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
252 <img src="./pix/ir.png" style="height: 6em;"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
253 </p> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
254 <li class="incremental">Generic Tree生成部分について触れてみる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
255 </div> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
256 <!-- PAGE --> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
257 <div class="slide"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
258 <h1>GCC:Generic Tree</h1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
259 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
260 <table class="center" width=100% border=1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
261 <tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
262 <td><small>値の代入:MODIFY_EXPR</small></td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
263 <td><small>関数呼び出し:CALL_EXPR</small></td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
264 </t> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
265 <tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
266 <td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
267 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
268 </td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
269 <td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
270 <img src="./pix/CALL_EXPR.png" style="height: 7em;"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
271 </td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
272 </tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
273 </table> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
274 <p class="center"><small>Generic Treeでの表現</small></p> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
275 </div> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
276 <!-- PAGE --> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
277 <div class="slide"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
278 <h1>GCC:Generic Tree</h1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
279 <li>それぞれの命令はSTATEMENT_LISTでまとめて保持される。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
280 <table width=100% border=1> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
281 <tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
282 <td class="center"><small>ソースコード</small></td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
283 <td class="center"><small>Generic Treeでの表現</small></td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
284 </tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
285 <tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
286 <td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
287 <small> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
288 <pre> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
289 int main() { |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
290 int a, b; |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
291 a = 3; |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
292 b = func(a, 10); |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
293 return b; |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
294 } |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
295 </pre> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
296 </small> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
297 </td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
298 <td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
299 <p class="center"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
300 <img src="./pix/STATEMENT_LIST.png" style="height: 6em;"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
301 </p> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
302 </td> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
303 </tr> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
304 </table> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
305 <li>CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
306 </div> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
307 <!-- PAGE --> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
308 <!-- |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
309 <div class="slide"> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
310 <h1>GCC</h1> |
54 | 311 <li>GCC についての簡単な説明を行う...</li> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
312 <li>TODO: NEXT_PASS() の把握</li> |
54 | 313 <img src="./pix/ir.png" style="height: 6em;"> |
314 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li> | |
315 </div> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
316 --> |
54 | 317 <!-- PAGE --> |
318 <div class="slide"> | |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
319 <h1>CbCの実装</h1> |
54 | 320 <ul> |
321 <li>シンタックスの追加</li> | |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
322 <li>レジスタによる引数渡し(fastcall属性の付与)</li> |
54 | 323 <li>Tail Call Elimination</li> |
324 <li>環境付き継続</li> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
325 <li>__rectype の実装</li> |
54 | 326 </ul> |
327 </div> | |
328 <!-- PAGE --> | |
329 <div class="slide"> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
330 <h1>CbCの実装:シンタックスの追加</h1> |
54 | 331 <ul> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
332 <li>__code キーワードでのコードセグメントの宣言</li> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
333 <ul> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
334 <li>__code 用idとkeywordを作成。</li> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
335 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
336 </ul> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
337 <li>goto によるコードセグメントへの継続</li> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
338 <ul> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
339 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
340 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
341 </ul> |
54 | 342 </ul> |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
343 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> |
54 | 344 </div> |
345 <!-- PAGE --> | |
346 <div class="slide"> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
347 <h1>CbCの実装:シンタックスの追加</h1> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
348 <h2>gotoシンタックスの追加</h2> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
349 <small> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
350 <pre> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
351 expr = c_parser_expr_no_commas (parser, NULL); |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
352 if (TREE_CODE(expr.value) == CALL_EXPR ) |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
353 { |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
354 location_t loc = c_parser_peek_token (parser)->location; |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
355 cbc_replace_arguments (loc, expr.value); |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
356 TREE_TYPE(expr.value) = void_type_node; |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
357 CbC_IS_CbC_GOTO (expr.value) = 1; |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
358 CALL_EXPR_TAILCALL (expr.value) = 1; |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
359 add_stmt(expr.value); |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
360 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
361 } |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
362 </pre> |
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
363 </small> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
364 <small> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
365 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
366 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
367 <li>最後にc_finish_return関数によりreturn文を生成している。</li> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
368 </small> |
54 | 369 </div> |
370 <!-- PAGE --> | |
371 <div class="slide"> | |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
372 <h1>CbCの実装:シンタックスの追加</h1> |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
373 <h2>gotoシンタックスの追加</h2> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
374 <li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li> |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
375 <table border=1 width=100%> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
376 <tr class="center"> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
377 <small> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
378 <td>実際のコード </td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
379 <td>GCC 内で処理されるコード</td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
380 </small> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
381 </tr> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
382 <tr style="margin-top: auto;"> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
383 <td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
384 <pre> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
385 goto factorial0(1, x); |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
386 </pre> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
387 </td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
388 <td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
389 <pre> |
58 | 390 factorial0(1, x); |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
391 return; |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
392 </pre> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
393 </td> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
394 </tr> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
395 </table> |
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
396 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> |
54 | 397 </div> |
398 <!-- PAGE --> | |
399 <div class="slide"> | |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
400 <h1>CbCの実装:引数渡し</h1> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
401 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> |
58 | 402 <ul> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
403 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> |
58 | 404 </ul> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
405 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li> |
58 | 406 </div> |
407 <!-- PAGE --> | |
408 <div class="slide"> | |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
409 <h1>CbCの実装:引数渡し(fastcall)</h1> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
410 <h2>fastcall</h2> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
411 <ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
412 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
413 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
414 </ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
415 <li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li> |
58 | 416 <small> |
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
417 <pre> |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
418 if(!TARGET_64BIT) { |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
419 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
420 declspecs_add_attrs(specs, attrs); |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
421 } |
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
422 </pre> |
58 | 423 </small> |
424 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p> | |
425 </div> | |
426 <!-- PAGE --> | |
427 <div class="slide"> | |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
428 <h1>CbCの実装:引数渡し</h1> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
429 <table width=100% border=1 class="center"> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
430 <caption>引数渡しに使われるレジスタの数(gcc)</caption> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
431 <tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
432 <td>arch</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
433 <td>int(整数型)</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
434 <td>float(浮動小数点型)</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
435 <td>double(浮動小数点型)</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
436 </tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
437 <tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
438 <td>i386</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
439 <td>2</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
440 <td>0<br>(stackを使用)</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
441 <td>0<br>(stackを使用)</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
442 </tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
443 <tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
444 <td>x86_64</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
445 <td>6</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
446 <td>8</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
447 <td>8</td> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
448 </tr> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
449 </table> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
450 </div> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
451 <!-- PAGE --> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
452 <div class="slide"> |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
453 <h1>CbCの実装:TCE</h1> |
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
454 <h2>Tail Call Elimination(TCE):末尾除去</h2> |
62 | 455 <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li> |
456 <img src="./pix/continuation.png" style="height: 7em;"> | |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
457 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
458 </div> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
459 <!-- PAGE --> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
460 <div class="slide"> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
461 <h1>CbCの実装:TCE</h1> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
462 <li>TCEにより関数へjmp命令で処理を移すことを利用。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
463 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
464 <br> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
465 <h2>具体的な実装内容</h2> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
466 <ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
467 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
468 <li class="incremental">try_tail_callフラグを落とさせない。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
469 </ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
470 <li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li> |
54 | 471 </div> |
472 <!-- PAGE --> | |
473 <div class="slide"> | |
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
474 <h1>CbCの実装:TCE</h1> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
475 <li>try_tail_callフラグはexpand_call関数で落とされる。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
476 <ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
477 <li>expand_call関数</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
478 <ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
479 <li>Treeで表された関数からRTLを生成する関数</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
480 </ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
481 </ul> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
482 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
483 <small> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
484 <ol> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
485 <li>caller側とcallee側の戻値の型の一致している。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
486 <li>関数呼び出しがリターン直前に行われている。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
487 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
488 <li>引数の並びのコピーに上書きがない。</li> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
489 </ol> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
490 </small> |
54 | 491 </div> |
492 <!-- PAGE --> | |
493 <div class="slide"> | |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
494 <h1>CbCの実装:TCE</h1> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
495 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
496 <small> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
497 <ol> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
498 <li>型はvoid型で統一。</li> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
499 <li>gotoの直後にreturnを置く。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
500 <li>スタックサイズは固定。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
501 <li>引数は一旦、一時変数にコピーする。</li> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
502 </ol> |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
503 </small> |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
504 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
505 </div> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
506 <!-- PAGE --> |
64 | 507 <!-- |
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
508 <div class="slide"> |
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
509 <h1>CbCの実装:環境付き継続</h1> |
62 | 510 <li>CbCにおけるCとの互換性を保つための機能。</li> |
511 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li> | |
64 | 512 <li>論文における訂正</li> |
513 <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li> | |
514 <ul> | |
515 <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li> | |
516 <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li> | |
517 </ul> | |
518 </div> | |
519 --> | |
520 <!-- PAGE --> | |
521 <!-- | |
522 <div class="slide"> | |
523 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1> | |
524 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br> | |
525 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p> | |
526 </div> | |
527 --> | |
528 <!-- PAGE --> | |
529 <div class="slide"> | |
530 <h1>CbCの実装:環境付き継続</h1> | |
531 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> | |
532 <li>__returnキーワードを引数に渡すことで使うことができる。</li> | |
533 <li>以下の使い方の場合は1を返す。</li> | |
534 <small> | |
535 <pre> | |
536 __code c1(__code ret(int,void *),void *env) { | |
537 goto ret(1,env); | |
538 } | |
539 int main() { | |
540 goto c1(__return, __environment); | |
541 } | |
542 </pre> | |
543 </small> | |
544 <p><small>__environmentキーワードは関数の環境を保存している。</small></p> | |
54 | 545 </div> |
546 <!-- PAGE --> | |
547 <div class="slide"> | |
64 | 548 <h1>CbCの実装:環境付き継続</h1> |
549 <h2>実際には以下のコードを生成している。</h2> | |
550 <small> | |
551 <pre> | |
552 goto c1(__return, __environment); | |
553 | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
554 goto c1(({ |
64 | 555 __label__ _cbc_exit0; |
556 static int retval; | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
557 void _cbc_internal_return(int retval_, void *_envp) { |
64 | 558 retval = retval_; |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
559 goto _cbc_exit0; |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
560 } |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
561 if (0) { |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
562 _cbc_exit0: |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
563 return retval; |
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
564 } |
64 | 565 _cbc_internal_return; |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
566 }), __environment); |
64 | 567 </pre> |
568 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> | |
569 </small> | |
570 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> | |
54 | 571 </div> |
572 <!-- PAGE --> | |
573 <div class="slide"> | |
64 | 574 <h1>CbCの実装:環境付き継続</l> |
575 <h2>環境付き継続の生成部分:</h2> | |
576 <div class="src"> | |
577 <small> | |
578 <pre> | |
579 { | |
580 tree value, stmt, label, tlab, decl; | |
581 c_parser_consume_token (parser); | |
582 | |
583 stmt = c_begin_stmt_expr (); | |
584 cbc_return_f = c_parser_peek_token (parser)->value; | |
585 location_t location = c_parser_peek_token (parser)->location; | |
586 | |
587 /* create label. (__label__ _cbc_exit0;) */ | |
588 label = get_identifier ("_cbc_exit0"); | |
589 tlab = declare_label (label); | |
590 C_DECLARED_LABEL_FLAG (tlab) = 1; | |
591 add_stmt (build_stmt (location, DECL_EXPR, tlab)); | |
592 | |
593 /* declare retval. (int retval;) */ | |
594 tree decl_cond = | |
595 build_decl (location, VAR_DECL, get_identifier ("retval"), | |
596 TREE_TYPE (TREE_TYPE (current_function_decl))); | |
597 TREE_STATIC (decl_cond) = 1; | |
598 TREE_USED (decl_cond) = 1; | |
599 | |
600 /* Use thread-local */ | |
601 DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond); | |
602 DECL_NONLOCAL (decl_cond) = 1; | |
603 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond))); | |
604 | |
605 /* define nested function. */ | |
606 decl = | |
607 cbc_finish_nested_function (location, label, decl_cond); | |
608 TREE_USED(decl) = 1; | |
609 | |
610 /* define if-ed goto label and return statement. */ | |
611 cbc_finish_labeled_goto (location, label, decl_cond); | |
612 | |
613 /* get pointer to nested function. */ | |
614 value = build_addr (decl , current_function_decl); | |
615 TREE_USED (current_function_decl) = 1; | |
616 SET_EXPR_LOCATION (value, location); | |
617 add_stmt (value); | |
618 | |
619 TREE_SIDE_EFFECTS (stmt) = 1; | |
620 expr.value = c_finish_stmt_expr (location, stmt); | |
621 expr.original_code = ERROR_MARK; | |
622 } | |
623 </pre> | |
54 | 624 </small> |
64 | 625 </div> |
54 | 626 </div> |
627 <!-- PAGE --> | |
628 <div class="slide"> | |
64 | 629 <h1>CbCの実装:環境付き継続</h1> |
630 <h2>作成されるTree</h2> | |
631 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;"> | |
632 <!-- | |
633 <small> | |
634 <pre> | |
635 ({ | |
636 __label__ _cbc_exit0; | |
637 static int retval; | |
638 void _cbc_internal_return(int retval_, void *_envp){ | |
639 retval = retval_; | |
640 goto _cbc_exit0; } | |
641 if (0) { _cbc_exit0: | |
642 return retval; } | |
643 _cbc_internal_return; | |
644 }), | |
645 </pre> | |
646 </small> | |
647 --> | |
648 </div> | |
649 <!-- PAGE --> | |
650 <div class="slide"> | |
651 <h1>環境付き継続:実装の問題</h1> | |
652 <ul> | |
653 <li>リターンするretval変数が重要になってくる。</li> | |
654 <li>retval変数のデータをどうやって確保するか。</li> | |
655 </ul> | |
656 <li>次の方法が考えられる。</li> | |
657 <ul> | |
658 <li>クロージャでの確保</li> | |
659 <li>staticでの確保</li> | |
660 <li>static thread local storage(tls)を用いての確保</li> | |
661 </ul> | |
662 </div> | |
663 <!-- PAGE --> | |
664 <div class="slide"> | |
665 <h1>環境付き継続:実装の問題</h1> | |
666 <li>クロージャでの実装</li> | |
54 | 667 <ul> |
64 | 668 <li>クロージャにしてスタックに値を確保する。</li> |
669 <li></li> | |
670 </ul> | |
671 <li>問題点</li> | |
672 <ul> | |
673 <li class="incremental">しかしCbCではスタックの値は破棄されていく。</li> | |
674 <li class="incremental">その為スタックに値を確保するのは好ましくない。</li> | |
675 </ul> | |
676 </div> | |
677 <!-- PAGE --> | |
678 <div class="slide"> | |
679 <h1>環境付き継続:実装の問題</h1> | |
680 <li>staticでの実装</li> | |
681 <ul> | |
682 <li>静的に値を確保することでスタック破棄の影響を受けない。</li> | |
683 </ul> | |
684 <li>問題点</li> | |
685 <ul> | |
686 <li class="incremental">マルチスレッドのプログラムに対応できない。</li> | |
687 <li class="incremental">値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> | |
54 | 688 </ul> |
64 | 689 </div> |
690 <!-- PAGE --> | |
691 <div class="slide"> | |
692 <h1>環境付き継続:実装の問題</h1> | |
693 <li>static tlsでの実装</li> | |
694 <ul> | |
695 <li>スレッド毎に静的に値を確保する。</li> | |
696 </ul> | |
697 <li>現在はこの方法で実装を行なっている。</li> | |
698 <li>しかし、最適化にかけると正しい値が返ってこない。 | |
699 <br>(恐らくTreeの生成の部分が間違っている。)</li> | |
700 </div> | |
701 <!-- PAGE --> | |
702 <div class="slide"> | |
703 <h1>環境付き継続:その他の実装方法</h1> | |
704 <ul> | |
705 <li>setjmpでの実装</li> | |
706 <ul> | |
707 <li>setjmpを行うTreeを生成するのが少し手間になる。</li> | |
708 <li>int型の戻値しか得られない。</li> | |
709 </ul> | |
710 <li>戻値を入れるレジスタを明示的に指定する。</li> | |
711 <ul> | |
712 <li>まだ実装を試していない。</li> | |
713 </ul> | |
714 </ul> | |
54 | 715 </div> |
716 <!-- PAGE --> | |
717 <div class="slide"> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
718 <h1>CbCの機能の拡張:__rectype の実装</h1> |
57
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
719 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
720 <small> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
721 <pre> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
722 void factorial(int n, int result, void(*print)()){ |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
723 : |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
724 (*print)(n,result,print,exit1, envp); |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
725 } |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
726 </pre> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
727 </small> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
728 <li>以下の様に扱えるようにしたい。</li> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
729 <small> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
730 <pre> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
731 void factorial(int n, int result, void *print){ |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
732 : |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
733 (*print)(n,result,print,exit1, envp); |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
734 } |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
735 </pre> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
736 </small> |
54 | 737 </div> |
738 <!-- PAGE --> | |
739 <div class="slide"> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
740 <h1>CbCの機能の拡張:__rectype の実装</h1> |
57
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
741 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
742 <pre> |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
743 __code factorial(int n, int result, __rectype *print) { |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
744 : |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
745 (*print)(n,result,print,exit1, envp); |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
746 } |
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
747 </pre> |
54 | 748 </div> |
749 <!-- PAGE --> | |
750 <div class="slide"> | |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
751 <h1>CbCの機能の拡張:selftype</h1> |
64 | 752 <h2>selftypeの実装</h2> |
753 <li>以下の宣言が行えるようにしたい。</li> | |
754 <small> | |
755 <pre> | |
756 typedef sturct node { | |
757 selftype *left; | |
758 selftype *right; | |
759 int num; | |
760 }*NODE | |
761 </pre> | |
762 <p>selftype は struct node を指す。</p> | |
763 </small> | |
764 <ul> | |
765 <li>上記の構文は実装を行う予定である。</li> | |
766 </ul> | |
767 </div> | |
768 <!-- PAGE --> | |
769 <div class="slide"> | |
66
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
770 <h1>Micro-Cとの比較</h1> |
68
1399414ea3f6
modify explanation of Generic Tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
771 <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li> |
66
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
772 <table width=100% class="center"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
773 <td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
774 <img src="./pix/mac_conv.png"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
775 </td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
776 <td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
777 <img src="./pix/linux_conv.png"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
778 </td> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
779 </table> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
780 <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
781 その為に明らかに遅くなっていることが分かる。</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
782 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li> |
54 | 783 </div> |
784 <!-- PAGE --> | |
64 | 785 <div class="slide"> |
786 <h1></h1> | |
787 <li></li> | |
788 </div> | |
789 <!-- PAGE --> | |
790 <div class="slide"> | |
791 <h1>まとめ</h1> | |
66
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
792 <ul> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
793 <li>今回GCC版CbCコンパイラのアップデートを行った。</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
794 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。 |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
795 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
796 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
797 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
798 </ul> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
799 </div> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
800 <!-- PAGE --> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
801 <div class="slide"> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
802 <h1>今後の予定</h1> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
803 <ul> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
804 <li>CbCを用いたプログラムの作成</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
805 <ul> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
806 <li>CbCによるタスクマネージャの作成</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
807 </ul> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
808 <li>llvmへのCbCの実装</li> |
26a3713b2989
modify explanation of CbC
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
64
diff
changeset
|
809 </ul> |
64 | 810 </div> |
811 <!-- PAGE --> | |
54 | 812 </div> |
813 </body> | |
814 </html> |