Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html~ @ 80:923dd8de7be2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Wed, 04 Jan 2012 23:41:05 +0900
parents a967ee5a0b0f
children 07c5304622ac
comparison
equal deleted inserted replaced
79:d53237223e13 80:923dd8de7be2
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3 3
4 <html xmlns="http://www.w3.org/1999/xhtml"> 4 <html xmlns="http://www.w3.org/1999/xhtml">
5 5
6 <head> 6 <head>
7 <style> 7 <style type="text/css">
8 tr.srctr {
9 font-size:28px;
10 }
11 td.srctd {
12 height:17em;
13 }
14 pre.srcbox {
15 height: 100%;
16 overflow: scroll;
17 }
18 .src{
19 overflow: scroll;
20 width: 90%;
21 height: 60%;
22 }
8 .center { 23 .center {
9 margin-left: auto; 24 margin-left: auto;
10 margin-right: auto; 25 margin-right: auto;
11 text-align: center; 26 text-align: center;
12 } 27 }
17 margin: auto; 32 margin: auto;
18 width: 95%; 33 width: 95%;
19 font-weight: bold; 34 font-weight: bold;
20 } 35 }
21 </style> 36 </style>
22 <title>2011/12/20</title> 37 <title>2012/ 1/ 7</title>
23 <!-- metadata --> 38 <!-- metadata -->
24 <meta name="generator" content="S5" /> 39 <meta name="generator" content="S5" />
25 <meta name="version" content="S5 1.1" /> 40 <meta name="version" content="S5 1.1" />
26 <meta name="presdate" content="20111220" /> 41 <meta name="presdate" content="20120107" />
27 <meta name="author" content="Nobuyasu Oshiro" /> 42 <meta name="author" content="Nobuyasu Oshiro" />
28 <meta name="company" content="University of the Ryukyu" /> 43 <meta name="company" content="University of the Ryukyu" />
29 <!-- meta temporary --> 44 <!-- meta temporary -->
30 <meta http-equiv="content-type" content="text/html; charset=utf-8" /> 45 <meta http-equiv="content-type" content="text/html; charset=utf-8" />
31 <meta http-equiv="Content-Script-Type" content="text/javascript" /> 46 <meta http-equiv="Content-Script-Type" content="text/javascript" />
66 <div class="layout"> 81 <div class="layout">
67 <div id="controls"><!-- DO NOT EDIT --></div> 82 <div id="controls"><!-- DO NOT EDIT --></div>
68 <div id="currentSlide"><!-- DO NOT EDIT --></div> 83 <div id="currentSlide"><!-- DO NOT EDIT --></div>
69 <div id="header"></div> 84 <div id="header"></div>
70 <div id="footer"> 85 <div id="footer">
71 <h1>セミナー: 2011/ 12/ 20</h1> 86 <h1>プログラミングシンポジウム: 2012/ 1/ 7</h1>
72 <h2>並列信頼研</h2> 87 <h2>並列信頼研</h2>
73 </div> 88 </div>
74 </div> 89 </div>
75 90
76 <div class="presentation"> 91 <div class="presentation">
83 <div class="handout"></div> 98 <div class="handout"></div>
84 </div> 99 </div>
85 <!-- PAGE --> 100 <!-- PAGE -->
86 <div class="slide"> 101 <div class="slide">
87 <h1>目的と背景(1)</h1> 102 <h1>目的と背景(1)</h1>
88 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> 103 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。</li>
89 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> 104 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
90 </div> 106 </div>
91 <!-- PAGE --> 107 <!-- PAGE -->
92 <div class="slide"> 108 <div class="slide">
93 <h1>目的と背景(2)</h1> 109 <h1>目的と背景(2)</h1>
94 <li>CbC のコンパイラは2008年に GCC をベースとしたコンパイラが開発された。</li> 110 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
95 <li>GCC をベースとした CbC コンパイラは、GCC のアップデートに合わせ変更する必要がある。</li> 111 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
96 <li>本研究ではGCC-4.5 をベースとしていた CbC コンパイラを GCC-4.6 へのアップデートを行い、Intel64 への対応するとともに CbC の拡張を行う。 </li> 112 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
97 </div> 113 </div>
98 <!-- PAGE --> 114 <!-- PAGE -->
99 <div class="slide"> 115 <div class="slide">
100 <h1>今週の作業内容</h1> 116 <h1>発表内容</h1>
101 <li></li> 117 <ol>
102 <li>環境付き継続について</li> 118 <li>CbC の紹介</li>
103 <ul> 119 <li>GCC でのコンパイルの流れ</li>
104 <li>変数 retval を static スレッドローカル(TLS)での実装</li> 120 <font color="red">
105 </ul> 121 <li>CbC の実装</li>
106 </div> 122 </font>
107 <!-- PAGE --> 123 <li>Micro-C との性能比較</li>
108 <div class="slide"> 124 <li>まとめ</li>
109 <h1>static TLS のGeneric Tree</h1> 125 <ol>
110 <li>変数 retval の宣言(VAR_DECL)</li> 126 </div>
111 <li>static TLS の場合追加される情報は以下の2つ:(Linux)</li> 127 <!-- PAGE -->
112 <ul> 128 <div class="slide">
113 <li>TLS のモデル: TLS_MODEL_LOCAL_EXEC</li> 129 <h1>Continuation based C </h1>
114 <li>static フラグ 1</li> 130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
115 </ul> 131 <ul>
116 <li class="incremental">上記の設定で retval を作成しても正しい返り値は得られなかった。</li> 132 <li>コードセグメント:CbCにおけるプログラムの基本単位</li>
117 </div> 133 <ul>
118 <!-- PAGE --> 134 <li>C の関数よりも細かい単位になる。</li>
119 <div class="slide"> 135 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
120 <h1>環境付き継続の構文木をみる</h1> 136 <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
121 <li>環境継続において以下の retval 変数は static で作られている.</li> 137 </ul>
122 <small> 138 <p class="center">
123 <pre> 139 <img src="./pix/codesegment.png" style="height:6em;">
124 ({ 140 </p>
125 __label__ _cbc_exit0; 141 </ul>
126 static __thread int retval; 142 </div>
127 void _cbc_internal_return(int retval_, void *_envp){ 143 <!-- PAGE -->
128 printf("in _cbc_internal_return\n",retval_); 144 <div class="slide">
129 retval = retval_; 145 <h1>Continuation based C </h1>
130 goto _cbc_exit0; 146 <h2>継続:現在の処理を実行していく為の情報</h2>
131 } 147
132 if (0) { 148 <table width=100% border=1>
133 _cbc_exit0: 149 <tr>
134 return retval; 150 <td><small>Cの継続</small></td>
135 } 151 <td><small>CbCの継続(軽量継続)</small></td>
136 _cbc_internal_return; 152 </tr>
137 }) 153 <tr style="font-size:30px">
154 <td>
155 <ul>
156 <li>続く命令のアドレス</li>
157 <li>命令に必要なデータ</li>
158 <li>スタックに積まれている値(環境)</li>
159 </ul>
160 </td>
161 <td>
162 <ul>
163 <li>Cの継続から環境を除外</li>
164 <li>続く命令とその命令に必要なデータのみ</li>
165 </ul>
166 </td>
167 </tr>
168 <tr>
169 <td style="margin-left:auto; margin-right: auto; text-align: center;">
170 <img class="scale" src="./pix/func_call.png" style="height: 6em;">
171 </td>
172 <td style="margin-left:auto; margin-right: auto; text-align: center;">
173 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
174 </td>
175 </tr>
176 </table>
177 <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
178 </div>
179 <!-- PAGE -->
180 <div class="slide">
181 <h1>Continuation based C </h1>
182 <table width=100% border=1>
183 <caption><small>階乗を求めるCbCのプログラム</small></caption>
184 <tr class="srctr">
185 <td width=50%>
186 <pre class="srcbox">
187
188 __code print_factorial(int prod) {
189 printf("factorial = %d\n",prod);
190 exit(0);
191 }
192
193 __code factorial0(int prod, int x) {
194 if ( x >= 1) {
195 goto factorial0(prod*x, x-1);
196 }else{
197 goto print_factorial(prod);
198 }
199 }
200 </pre>
201 </td>
202 <td>
203 <pre class="srcbox">
204
205 __code factorial(int x) {
206 goto factorial0(1, x);
207 }
208
209 int main(int argc, char **argv) {
210 int i;
211 i = atoi(argv[1]);
212 goto factorial(i);
213 return 0;
214 }
138 </pre> 215 </pre>
139 </small> 216 </td>
140 </div> 217 </tr>
141 <!-- PAGE --> 218 </table>
142 <div class="slide"> 219 <ul>
143 <h1>環境付き継続の構文木をみる</h1> 220 <li><small>__code キーワードによるコードセグメントの宣言</small></li>
144 <img src="./pix/BIND_EXPR.png"> 221 <li><small>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</small></li>
145 <li>BIND_EXPR は{ } の中身を束ねる。</li> 222 </ul>
146 <li>STATEMENT_LIST が1つ1つのプログラムを表す木を持っている。</li> 223 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
147 </div> 224 </div>
148 <!-- PAGE --> 225 <!-- PAGE -->
149 <div class="slide"> 226 <div class="slide">
150 <h1>環境付き継続の構文木をみる</h1> 227 <h1>GCC</h1>
151 <img src="./pix/STATEMENT_LIST_1.png"> 228 <ul>
152 <li>BIND_EXPR は _cbc_internal_return 関数を<br> 229 <li>本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。</li>
153 ADDR_EXPR は最後の行の _cbc_internal_return を表す。</li> 230 <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
154 </div> 231 <ul>
155 <!-- PAGE --> 232 <li>Generic Tree</li>
156 <div class="slide"> 233 <li>GIMPLE</li>
157 <h1>環境付き継続の構文木をみる</h1> 234 <li>Tree SSA</li>
158 <li>_CbC_return の実装より作られる構文木を見てみる。</li> 235 <li>RTL</li>
159 <scale> 236 </ul>
160 <img src="./pix/STATEMENT_LIST_2.png"> 237 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
161 </scale> 238 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
162 </div> 239 </ul>
163 <!-- PAGE --> 240 </div>
164 <div class="slide"> 241 <!-- PAGE -->
165 <h1>環境付き継続の構文木をみる</h1> 242 <!--
166 <li>出来上がる構文木が違う。</li> 243 <div class="slide">
167 <ul> 244 <h1>GCC:Generic Tree</h1>
168 <li>DECL_EXPR が 1つ足りない</il> 245 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
169 <li>BIND_EXPR の部分が COND_EXPR になっている。</li> 246 <table class="center" width=100% border=1>
170 </ul> 247 <tr>
171 </div> 248 <td></td>
172 <!-- PAGE --> 249 <td><small>値の代入:MODIFY_EXPR</small></td>
173 <div class="slide"> 250 <td><small>関数呼び出し:CALL_EXPR</small></td>
174 <h1>DECL_EXPR の問題</h1> 251 </t>
175 <li>なくなっている DECL_EXPR は VAR_DECL の部分。</li> 252 <tr>
176 <li>static __thread int retval になる。</li> 253 <td>命令</td>
177 <li>下記の様にソースを変更</li> 254 <td>b = a * 10</td>
255 <td>func(a,10)</td>
256 </t>
257 <tr>
258 <td><small>Generic<br>Tree</small></td>
259 <td>
260 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
261 </td>
262 <td>
263 <img src="./pix/CALL_EXPR.png" style="height: 7em;">
264 </td>
265 </tr>
266 </table>
267 <p class="center"><small>Generic Treeでの表現</small></p>
268 </div>
269 -->
270 <!-- PAGE -->
271 <div class="slide">
272 <h1>GCC:Generic Tree</h1>
273 <li><small>CALL_EXPRE、MODIFY_EXPR等といった表現で扱われる。</small></li>
274 <table width=100% border=1>
275 <tr>
276 <td class="center"><small>ソースコード</small></td>
277 <td class="center"><small>Generic Treeでの表現</small></td>
278 </tr>
279 <tr>
280 <td>
281 <small>
178 <pre> 282 <pre>
179 // pushdecl (decl_cond); 283 int main() {
180 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond))); 284 int a, b;
285 a = 3;
286 b = func(a, 10);
287 return b;
288 }
181 </pre> 289 </pre>
182 <li>これで DECL_EXPR が追加された。</li> 290 </small>
183 </div> 291 </td>
184 <!-- PAGE --> 292 <td style="margin-left:auto; margin-right:auto; text-align: center;">
185 <div class="slide"> 293 <img src="./pix/STATEMENT_LIST.png" style="height: 7em;">
186 <h1>COND_EXPR の問題</h1> 294 </td>
187 <li>BIND_EXPR でなくて COND_EXPR になっていた問題。</li> 295 </tr>
188 <li>BIND_EXPR をみると以下の様な構成になっていた。</li> 296 </table>
189 <img src="./pix/COND_EXPR.png"> 297 <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
190 <li>BIND_EXPR をなぜか COND_EXPR でもう一度包んでいた。</li> 298 </div>
191 <small> 299 <!-- PAGE -->
192 <p>COND_EXPR には if(0){ } の中身が入る。</p> 300 <!--
301 <div class="slide">
302 <h1>GCC</h1>
303 <li>GCC についての簡単な説明を行う...</li>
304 <li>TODO: NEXT_PASS() の把握</li>
305 <img src="./pix/ir.png" style="height: 6em;">
306 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li>
307 </div>
308 -->
309 <!-- PAGE -->
310 <div class="slide">
311 <h1>CbCの実装</h1>
312 <ul>
313 <li>シンタックスの追加</li>
314 <li>末尾除去:Tail Call Elimination(TCE)</li>
315 <li>レジスタによる引数渡し(fastcall属性の付与)</li>
316 <li>環境付き継続</li>
317 <!--
318 <li>__rectype の実装</li>
319 -->
320 </ul>
321 </div>
322 <!-- PAGE -->
323 <div class="slide">
324 <h1>CbCの実装:__codeシンタックスの追加</h1>
325 <ul>
326 <li>__code キーワードでのコードセグメントの宣言</li>
327 <ul>
328 <li>__code 用idとkeywordを作成。</li>
329 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
330 </ul>
331 </ul>
332 <table width=100% border=1>
333 <tr class="srctr">
334 <td>
335 <pre>
336 const struct c_common_resword c_common_reswords[] =
337 {
338 { "_Bool", RID_BOOL, D_CONLY },
339 :
340 { "__code", RID_CbC_CODE, 0 },
341 </pre>
342 </td>
343 </tr>
344 <tr class="srctr">
345 <td>
346 <pre>
347 case RID_CbC_CODE:
348 :
349 specs->typespec_word = cts_CbC_code;
350 </pre>
351 </td>
352 </tr>
353 <tr class="srctr">
354 <td>
355 <pre>
356 case cts_CbC_code:
357 :
358 specs->type = void_type_node;
359 break;
360 </pre>
361 </td>
362 </tr>
363 </table>
364 </div>
365 <!-- PAGE -->
366 <div class="slide">
367 <h1>CbCの実装:gotoシンタックスの追加</h1>
368 <li>goto によるコードセグメントへの継続</li>
369 <ul>
370 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
371 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
372 </ul>
373 <li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li>
374 <pre class="srcbox" style="font-size:25px; height:16em;">
375 case RID_GOTO:
376 c_parser_consume_token (parser);
377 if ( c_parser_next_token_is (parser, CPP_NAME)
378 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
379 {
380 stmt = c_finish_goto_label (loc,
381 c_parser_peek_token (parser)->value);
382 c_parser_consume_token (parser);
383 }
384 else if (c_parser_next_token_is (parser, CPP_MULT))
385 {
386 tree val;
387
388 c_parser_consume_token (parser);
389 val = c_parser_expression (parser).value;
390 mark_exp_read (val);
391 stmt = c_finish_goto_ptr (loc, val);
392 }
393 else
394 expr = c_parser_expr_no_commas (parser, NULL);
395 if (TREE_CODE(expr.value) == CALL_EXPR )
396 {
397 location_t loc = c_parser_peek_token (parser)->location;
398 cbc_replace_arguments (loc, expr.value);
399 TREE_TYPE(expr.value) = void_type_node;
400 CbC_IS_CbC_GOTO (expr.value) = 1;
401 CALL_EXPR_TAILCALL (expr.value) = 1;
402 add_stmt(expr.value);
403 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
404 }
405 </pre>
406 </div>
407 <!-- PAGE -->
408 <div class="slide">
409 <h1>CbCの実装:gotoシンタックスの追加</h1>
410 <ul>
411 <small>
412 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
413 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
414 <li>最後にc_finish_return関数によりreturn文を生成している。</li>
415 </small>
416 </ul>
417 <table border=1 width=100%>
418 <!--
419 <caption><small>return 自動生成</small></caption>
420 -->
421 <tr class="center">
422 <td><small>実際のコード</small></td>
423 <td><small>GCC内で処理されるコード</small></td>
424 </tr>
425 <tr class="srctr">
426 <td>
427 <pre>
428
429 __code test() {
430 :
431 goto factorial0(1, x);
432 }
433 </pre>
434 </td>
435 <td>
436 <pre>
437
438 void test() {
439 :
440 factorial0(1, x);
441 return;
442 }
443 </pre>
444 </td>
445 </tr>
446 </table>
447 <ul>
448 <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
449 <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
450 </ul>
451 </div>
452 <!-- PAGE -->
453 <div class="slide">
454 <h1>CbCの実装:TCE(末尾除去)</h1>
455 <h2>末尾除去:Tail Call Elimination(TCE)</h2>
456 <ul>
457 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
458 </ul>
459 <li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
460 <br>
461 <table width=100%>
462 <tr class="srctr">
463 <td width=50%>
464 <!--
465 <pre class="srcbox">
466 int main() {
467 int num = a(2);
468 printf("main:num=%d\n",num);
469 return 0;
470 }
471 int a(int num) {
472 return b(num+5);
473 }
474 int b(int num) {
475 printf("b:a = %d\n",num);
476 return num+3;
477 }
478 </pre>
479 -->
480 <pre class="srcbox">
481
482 void f(int a, int b) {
483 printf("f: a=%d b=%d\n",a,b);
484 return ;
485 }
486 void g(int a, int b){
487 printf("g: a=%d b=%d\n",a,b);
488 f(a,b);
489 return;
490 }
491
492 int main() {
493 g(3,4);
494 return 0;
495 }
496
497 </pre>
498 </td>
499 <td class="center">
500 <img src="./pix/continuation.png" style="height:100%;">
501 </td>
502 </tr>
503 </table>
504 </div>
505 <!-- PAGE -->
506 <div class="slide">
507 <h1>CbCの実装:TCE(末尾除去)</h1>
508 <ul>
509 <li>TCEにかかる条件</li>
510 <ul>
511 <li>caller側とcallee側の戻値の型の一致している。</li>
512 <li>関数呼び出しがリターン直前に行われている。</li>
513 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
514 <li>引数の並びのコピーに上書きがない。</li>
515 </ul>
516 <li class="incremental">条件を回避する為以下の実装にする。</li>
517 <ul class="incremental">
518 <li>型はvoid型で統一する。</li>
519 <li>gotoの直後にreturnを置く。</li>
520 <li>スタックサイズは固定にする。</li>
521 <li>引数は一旦、一時変数にコピーする。</li>
522 </ul>
523 </ul>
524 </div>
525 <!-- PAGE -->
526 <div class="slide">
527 <h1>CbCの実装:TCE(末尾除去)</h1>
528 <li>TCEの条件はexpand_call関数で調べられる。</li>
529 <ul>
530 <li>expand_call関数</li>
531 <ul>
532 <li>Treeで表された関数からRTLを生成する関数</li>
533 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
534 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
535 </ul>
536 <li class="incremental">具体的な実装内容</li>
537 <ul>
538 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
539 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
540 </ul>
541 <ul>
542
543 </div>
544 <!-- PAGE -->
545 <div class="slide">
546 <h1>CbCの実装:TCE(末尾除去)</h1>
547 <li>try_tail_callフラグが落とされる部分</li>
548 <table width=100%>
549 <tr class="srctr">
550 <td class="srctd">
551 <pre class="srcbox">
552
553 if (currently_expanding_call++ != 0
554 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))
555 && !flag_optimize_sibling_calls)
556 || args_size.var
557 || dbg_cnt (tail_call) == false)
558 try_tail_call = 0;
559
560 :
561
562 if (
563 #ifdef HAVE_sibcall_epilogue
564 !HAVE_sibcall_epilogue
565 #else
566 1
567 #endif
568 || !try_tail_call
569 || structure_value_addr != NULL_RTX
570 #ifdef REG_PARM_STACK_SPACE
571 || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
572 != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
573 || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl))
574 #endif
575 || !targetm.function_ok_for_sibcall (fndecl, exp)
576 || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
577 || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
578 || (fndecl && decl_function_context (fndecl) == current_function_decl)
579 || args_size.constant > (crtl->args.size
580 - crtl->args.pretend_args_size)
581 || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
582 != targetm.calls.return_pops_args (current_function_decl,
583 TREE_TYPE (current_function_decl),
584 crtl->args.size))
585 || !lang_hooks.decls.ok_for_sibcall (fndecl))
586 try_tail_call = 0;
587
588 :
589
590 /* Check if caller and callee disagree in promotion of function
591 return value. */
592 #ifndef noCbC
593 if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
594 #else
595 if (try_tail_call)
596 #endif
597 {
598 enum machine_mode caller_mode, caller_promoted_mode;
599 enum machine_mode callee_mode, callee_promoted_mode;
600 int caller_unsignedp, callee_unsignedp;
601 tree caller_res = DECL_RESULT (current_function_decl);
602
603 caller_unsignedp = TYPE_UNSIGNED (TREE_TYPE (caller_res));
604 caller_mode = DECL_MODE (caller_res);
605 callee_unsignedp = TYPE_UNSIGNED (TREE_TYPE (funtype));
606 callee_mode = TYPE_MODE (TREE_TYPE (funtype));
607 caller_promoted_mode
608 = promote_function_mode (TREE_TYPE (caller_res), caller_mode,
609 &caller_unsignedp,
610 TREE_TYPE (current_function_decl), 1);
611 callee_promoted_mode
612 = promote_function_mode (TREE_TYPE (funtype), callee_mode,
613 &callee_unsignedp,
614 funtype, 1);
615 if (caller_mode != VOIDmode
616 && (caller_promoted_mode != callee_promoted_mode
617 || ((caller_mode != caller_promoted_mode
618 || callee_mode != callee_promoted_mode)
619 && (caller_unsignedp != callee_unsignedp
620 || GET_MODE_BITSIZE (caller_mode)
621 < GET_MODE_BITSIZE (callee_mode)))))
622 try_tail_call = 0;
623 }
624 </pre>
625 </td>
626 </tr>
627 </table>
628 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
629 </div>
630 <!-- PAGE -->
631 <div class="slide">
632 <h1>CbCの実装:TCE(末尾除去)</h1>
633 <li>try_tail_callフラグ矯正付与のソースコード</li>
634 <table width=100%>
635 <tr class="srctr">
636 <td>
637 <pre class="srcbox">
638 #ifndef noCbC
639 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
640 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
641 && try_tail_call == 0)
642 {
643 location_t loc = EXPR_LOCATION (exp);
644 char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
645 warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
646 name_callee);
647 try_tail_call = 1;
648 }
649 #endif
650 </pre>
651 </td>
652 </tr>
653 </table>
654 <ul>
655 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
656 <br><small>(最適化の矯正付与)</small></li>
657 </ul>
658 </div>
659 <!-- PAGE -->
660 <div class="slide">
661 <h1>CbCの実装:TCE(末尾除去)の実装について</h1>
662 <ul>
663 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
664 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
665 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
666 </ul>
667 </div>
668 <!-- PAGE -->
669 <!--
670 <div class="slide">
671 <h1>CbCの実装</h1>
672 <li>CbCの基本機能を実現する為の実装は以上の2つになる。</li>
673 <ul>
674 <li>シンタックスの追加</li>
675 <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
676 </ul>
677 <li class="incremental">ここからはCbCの機能の拡張になる。</li>
678 </div>
679 -->
680 <!-- PAGE -->
681 <!--
682 <div class="slide">
683 <h1>CbCの実装:環境付き継続</h1>
684 <li>CbCにおけるCとの互換性を保つための機能。</li>
685 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
686 <li>論文における訂正</li>
687 <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
688 <ul>
689 <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li>
690 <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li>
691 </ul>
692 </div>
693 -->
694 <!-- PAGE -->
695 <!--
696 <div class="slide">
697 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
698 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
699 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
700 </div>
701 -->
702 <!-- PAGE -->
703 <div class="slide">
704 <h1>CbCの実装:引数渡し</h1>
705 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
706 <ul>
707 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
708 </ul>
709 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
710 </div>
711 <!-- PAGE -->
712 <div class="slide">
713 <h1>CbCの実装:引数渡し(fastcall)</h1>
714 <h2>fastcall</h2>
715 <ul>
716 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
717 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
718 </ul>
719 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
720 <small>
721 <pre>
722 if(!TARGET_64BIT) {
723 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
724 declspecs_add_attrs(specs, attrs);
725 }
726 </pre>
727 </small>
728 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
729 </div>
730 <!-- PAGE -->
731 <div class="slide">
732 <h1>CbCの実装:引数渡し</h1>
733 <ul>
734 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
735 </ul>
736 <br>
737 <table width=100% border=1 class="center">
738 <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
739 <tr>
740 <td>arch</td>
741 <td>int(整数型)</td>
742 <td>float(浮動小数点型)</td>
743 <td>double(浮動小数点型)</td>
744 </tr>
745 <tr>
746 <td>i386</td>
747 <td>2</td>
748 <td>0<br>(stackを使用)</td>
749 <td>0<br>(stackを使用)</td>
750 </tr>
751 <tr>
752 <td>x64</td>
753 <td>6</td>
754 <td>8</td>
755 <td>8</td>
756 </tr>
757 </table>
758 </div>
759 <!-- PAGE -->
760 <div class="slide">
761 <h1>CbCの実装:環境付き継続</h1>
762 <ul>
763 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
764 <li>__returnキーワードを引数に渡すことで使うことができる。</li>
765 </ul>
766 <li>以下の使い方の場合は1を返す。</li>
767 <table border=1 width=100%>
768 <td>
769 <small>
770 <pre class="srcbox">
771 __code c1(__code ret(int,void *),void *env) {
772 goto ret(1,env);
773 }
774 int main() {
775 goto c1(__return, __environment);
776 }
777 </pre>
778 </small>
779 </td>
780 </table>
781 <p><small>__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。</small></p>
782 </div>
783 <!-- PAGE -->
784 <div class="slide">
785 <h1>CbCの実装:環境付き継続</h1>
786 <!--
787 <li><small>生成しているコードと生成する為のコード</small></li>
788 -->
789 <table border=1 width=100%>
790 <tr>
791 <td><small>生成しているコード</small></td>
792 <td><small>生成されるTree</small></td>
793 </tr>
794 <tr class="srctr">
795 <td width=50% class="srctd">
796 <pre class="srcbox" style="width:25em;">
797
798 //goto c1(__return, __environment);
799 goto c1(({
800 __label__ _cbc_exit0;
801 static int retval;
802 void _cbc_internal_return(int retval_, void *_envp) {
803 retval = retval_;
804 goto _cbc_exit0;
805 }
806 if (0) {
807 _cbc_exit0:
808 return retval;
809 }
810 _cbc_internal_return;
811 }), __environment);
812 </pre>
813 </td>
814 <td width=50% class="srctd">
815 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
816 </td>
817 </tr>
818 </table>
819 <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
820 <!--
821 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
822 -->
823 </div>
824 <!-- PAGE -->
825 <div class="slide">
826 <h1>CbCの実装:環境付き継続</h1>
827 <table border=1 width=100%>
828 <tr>
829 <td width=50%><small>生成されるTree</small></td>
830 <td width=50%><small>生成する為のコード</small></td>
831 </tr>
832 <tr class="srctr">
833 <td class="srctd">
834 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
835 </td>
836 <td class="srctd">
837 <pre class="srcbox" style="width:25em;">
838
839 case RID_CbC_RET:
840 {
841 tree value, stmt, label, tlab, decl;
842 c_parser_consume_token (parser);
843
844 stmt = c_begin_stmt_expr ();
845 cbc_return_f = c_parser_peek_token (parser)->value;
846 location_t location = c_parser_peek_token (parser)->location;
847
848 /* create label. (__label__ _cbc_exit0;) */
849 label = get_identifier ("_cbc_exit0");
850 tlab = declare_label (label);
851 C_DECLARED_LABEL_FLAG (tlab) = 1;
852 add_stmt (build_stmt (location, DECL_EXPR, tlab));
853
854 /* declare retval. (int retval;) */
855 tree decl_cond =
856 build_decl (location, VAR_DECL, get_identifier ("retval"),
857 TREE_TYPE (TREE_TYPE (current_function_decl)));
858 TREE_STATIC (decl_cond) = 1;
859 TREE_USED (decl_cond) = 1;
860
861 /* Use thread-local */
862 DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
863 DECL_NONLOCAL (decl_cond) = 1;
864 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond)));
865
866 /* define nested function. */
867 decl =
868 cbc_finish_nested_function (location, label, decl_cond);
869 TREE_USED(decl) = 1;
870
871 /* define if-ed goto label and return statement. */
872 cbc_finish_labeled_goto (location, label, decl_cond);
873
874 /* get pointer to nested function. */
875 value = build_addr (decl , current_function_decl);
876 TREE_USED (current_function_decl) = 1;
877 SET_EXPR_LOCATION (value, location);
878 add_stmt (value);
879
880 TREE_SIDE_EFFECTS (stmt) = 1;
881 expr.value = c_finish_stmt_expr (location, stmt);
882 expr.original_code = ERROR_MARK;
883 }
884 </pre>
885 </td>
886 </tr>
887 </table>
888 <!--
889 <small>
890 <pre>
891 ({
892 __label__ _cbc_exit0;
893 static int retval;
894 void _cbc_internal_return(int retval_, void *_envp){
895 retval = retval_;
896 goto _cbc_exit0; }
897 if (0) { _cbc_exit0:
898 return retval; }
899 _cbc_internal_return;
900 }),
901 </pre>
193 </small> 902 </small>
194 </div> 903 -->
195 <!-- PAGE --> 904 </div>
196 <div class="slide"> 905 <!-- PAGE -->
197 <h1>ソースの手直し</h1> 906 <div class="slide">
198 <li>if(0){ } の構文木が作られる手順を元に<br> 907 <h1>環境付き継続:実装の問題</h1>
199 cbc_finish_labeled_goto 関数を手直しした。 908 <li>重要な部分</li>
200 <li>同じ構文木が作られるようになった。</li> 909 <ul>
201 </div> 910 <li>リターンするretval変数のメモリ確保</li>
202 <!-- PAGE --> 911 </ul>
203 <div class="slide"> 912 <li>次の方法が考えられる。</li>
204 <h1>結果</h1> 913 <ul>
205 <li>正常な値が返ってくるようになった。</li> 914 <li>クロージャでの確保</li>
206 <li class="incremental">しかし、-O2 オプションをつけると返り値の取得が失敗した。</li> 915 <li>staticでの確保</li>
207 <li class="incremental">もっと細かく構文木をみて違いを見つける必要がある。</li> 916 <li>setjmpを用いての実装</li>
208 </div> 917 <li>static thread local storage(tls)を用いての確保</li>
209 <!-- PAGE --> 918 <li>戻り値を入れるレジスタを明示的に指定</li>
210 <!-- 919 </ul>
211 <div class="slide"> 920 </div>
212 <h1>static TLS のGeneric Tree</h1> 921 <!-- PAGE -->
213 <li>変数 retval の宣言(VAR_DECL) が OS X の場合使用する TLS モデルが違った。</li> 922 <div class="slide">
214 <li>Linux: TLS_MODEL_LOCAL_EXEC</li> 923 <h1>環境付き継続:実装の問題</h1>
215 <li>OS X: TLS_MODEL_REAL<br>(TLS_MODEL_GLOBAL_DYNAMIC)</li> 924 <ul>
216 </div> 925 <li>クロージャでの実装の問題点:</li>
926 <!-- <ul><li>クロージャにしてスタックに値を確保する。</li></ul> -->
927 <ul>
928 <li >CbCでは継続によりスタックの値は破棄されていく。</li>
929 <li >クロージャにしたコードが破棄される可能性がある。</li>
930 </ul>
931
932 <li>staticでの実装の問題点:</li>
933 <!-- <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
934 <ul>
935 <li >マルチスレッドのプログラムに対応できない。</li>
936 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
937 </ul>
938
939 <li>setjmpでの実装</li>
940 <ul>
941 <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
942 <li>int型の戻値しか得られない。</li>
943 </ul>
944 </ul>
945 </div>
946 <!-- PAGE -->
947 <div class="slide">
948 <h1>環境付き継続:実装の問題</h1>
949 <ul>
950 <li>static tlsでの実装</li>
951 <!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
952 <ul>
953 <li>現在はこの方法で実装を行なっている。</li>
954 <li>しかし、最適化にかけると正しい値が返ってこない。
955 <br>(最適化によりコードが削除されている...?)</li>
956 </ul>
957 <li>戻値を入れるレジスタを明示的に指定する。</li>
958 <ul>
959 <li>まだ実装を試していない。</li>
960 </ul>
961 </ul>
962 </div>
963 <!-- PAGE -->
964 <div class="slide">
965 <h1>Micro-Cとの比較</h1>
966 <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
967 <table width=100% class="center">
968 <td>
969 <img src="./pix/mac_conv.png">
970 </td>
971 <td>
972 <img src="./pix/linux_conv.png">
973 </td>
974 </table>
975 <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
976 その為に明らかに遅くなっていることが分かる。</li>
977 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li>
978 </div>
979 <!-- PAGE -->
980 <div class="slide">
981 <h1>まとめ</h1>
982 <ul>
983 <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
984 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。
985 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li>
986 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li>
987 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
988 </ul>
989 </div>
217 <!-- PAGE --> 990 <!-- PAGE -->
218 <div class="slide"> 991 <div class="slide">
219 <h1>今後の予定</h1> 992 <h1>今後の予定</h1>
220 <li>プロシン用プレゼンの用意</li> 993 <ul>
221 <li>typedefrec, selftype の実装</li> 994 <li>CbCを用いたプログラムの作成</li>
222 <li>CbC でタクスマネージャ作成</li> 995 <ul>
996 <li>CbCによるタスクマネージャの作成</li>
997 </ul>
998 <li>llvmへのCbCの実装</li>
999 </ul>
1000 <br>
1001 <h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
1002 </div>
1003 <!-- PAGE -->
1004 <div class="slide">
1005 <h1>CbCの実装:TCE(末尾除去)の動作</h1>
1006 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
1007 <table width=100% border=1>
1008 <td>
1009 <p class="center">
1010 <img src="./pix/tce.png" style="height: 6em;">
1011 </p>
1012 </td>
1013 <td>
1014 <ul>
1015 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
1016 <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
1017 </ul>
1018 </td>
1019 </table>
1020 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
1021 </div>
1022 <!-- PAGE -->
1023 <div class="slide">
1024 <h1>CbCの機能の拡張:__rectype の実装</h1>
1025 <ul>
1026 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
1027 <pre style="font-size:28px;">
1028 void factorial(int n, int result, void(*print)()){
1029 :
1030 (*print)(n,result,print,exit1, envp);
1031 }
1032 </pre>
1033 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
1034 <pre style="font-size:28px;">
1035 __code factorial(int n, int result, __rectype *print) {
1036 :
1037 goto (*print)(n,result,print,exit1, envp);
1038 }
1039 </pre>
1040 </ul>
1041 </div>
1042 <!-- PAGE -->
1043 <div class="slide">
1044 <h1>CbCの機能の拡張:selftype</h1>
1045 <h2>selftypeの実装</h2>
1046 <li>以下の宣言が行えるようにしたい。</li>
1047 <small>
1048 <pre>
1049 typedef sturct node {
1050 selftype *left;
1051 selftype *right;
1052 int num;
1053 }*NODE
1054 </pre>
1055 <p>selftype は struct node を指す。</p>
1056 </small>
1057 <ul>
1058 <li>上記の構文は実装を行う予定である。</li>
1059 </ul>
223 </div> 1060 </div>
224 <!-- PAGE --> 1061 <!-- PAGE -->
225 </div> 1062 </div>
226 </body> 1063 </body>
227 </html> 1064 </html>