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 6465e96ba272
children efe2e6806c26
comparison
equal deleted inserted replaced
79:d53237223e13 80:923dd8de7be2
105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li> 105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
106 </div> 106 </div>
107 <!-- PAGE --> 107 <!-- PAGE -->
108 <div class="slide"> 108 <div class="slide">
109 <h1>目的と背景(2)</h1> 109 <h1>目的と背景(2)</h1>
110 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li> 110 <li>CbCのコンパイラは2001年に Micro-C版、2008年にはGCC-4.2をベースとしたコンパイラが開発された。</li>
111 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> 111 <li>GCC上のCbCコンパイラは、GCCで修正・追加されていく最適化の機能を使用する為に、アップデートに合わせ変更する必要がある。</li>
112 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> 112 <li>本研究ではCbCコンパイラをGCC-4.6へとアップデートを行った。 </li>
113 </div> 113 </div>
114 <!-- PAGE --> 114 <!-- PAGE -->
115 <div class="slide"> 115 <div class="slide">
116 <h1>発表内容</h1> 116 <h1>発表内容</h1>
117 <ol> 117 <ol>
129 <h1>Continuation based C </h1> 129 <h1>Continuation based C </h1>
130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> 130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
131 <ul> 131 <ul>
132 <li>コードセグメント:CbCにおけるプログラムの基本単位</li> 132 <li>コードセグメント:CbCにおけるプログラムの基本単位</li>
133 <ul> 133 <ul>
134 <li>Cから関数コールとループ制御が取り除かれた形</li>
134 <li>C の関数よりも細かい単位になる。</li> 135 <li>C の関数よりも細かい単位になる。</li>
135 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li> 136 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
136 <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
137 </ul> 137 </ul>
138 <p class="center"> 138 <p class="center">
139 <img src="./pix/codesegment.png" style="height:6em;"> 139 <img src="./pix/codesegment.png" style="height:6em;">
140 </p> 140 </p>
141 </ul> 141 </ul>
223 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li> 223 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
224 </div> 224 </div>
225 <!-- PAGE --> 225 <!-- PAGE -->
226 <div class="slide"> 226 <div class="slide">
227 <h1>GCC</h1> 227 <h1>GCC</h1>
228 <li>GCC:Gnu Compiler Collection</li>
228 <ul> 229 <ul>
229 <li>本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。</li> 230 <li><small>GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。</small></li>
230 <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li> 231 <li><small>cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</small></li>
231 <ul> 232 <ul>
232 <li>Generic Tree</li> 233 <li>Generic Tree</li>
233 <li>GIMPLE</li> 234 <li>GIMPLE</li>
234 <li>Tree SSA</li> 235 <li>Tree SSA</li>
235 <li>RTL</li> 236 <li>RTL</li>
236 </ul> 237 </ul>
238 <!--
237 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li> 239 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
240 -->
238 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li> 241 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
239 </ul> 242 </ul>
240 </div> 243 </div>
241 <!-- PAGE --> 244 <!-- PAGE -->
242 <!-- 245 <!--
268 </div> 271 </div>
269 --> 272 -->
270 <!-- PAGE --> 273 <!-- PAGE -->
271 <div class="slide"> 274 <div class="slide">
272 <h1>GCC:Generic Tree</h1> 275 <h1>GCC:Generic Tree</h1>
273 <li><small>CALL_EXPRE、MODIFY_EXPR等といった表現で扱われる。</small></li> 276 <li><small>CALL_EXPRE、MODIFY_EXPR、RETURN_EXPR等といった表現で扱われる。</small></li>
274 <table width=100% border=1> 277 <table width=100% border=1>
275 <tr> 278 <tr>
276 <td class="center"><small>ソースコード</small></td> 279 <td class="center"><small>ソースコード</small></td>
277 <td class="center"><small>Generic Treeでの表現</small></td> 280 <td class="center"><small>Generic Treeでの表現</small></td>
278 </tr> 281 </tr>
309 <!-- PAGE --> 312 <!-- PAGE -->
310 <div class="slide"> 313 <div class="slide">
311 <h1>CbCの実装</h1> 314 <h1>CbCの実装</h1>
312 <ul> 315 <ul>
313 <li>シンタックスの追加</li> 316 <li>シンタックスの追加</li>
317 <li>継続処理の実装</li>
318 <!--
314 <li>末尾除去:Tail Call Elimination(TCE)</li> 319 <li>末尾除去:Tail Call Elimination(TCE)</li>
320 -->
315 <li>レジスタによる引数渡し(fastcall属性の付与)</li> 321 <li>レジスタによる引数渡し(fastcall属性の付与)</li>
316 <li>環境付き継続</li> 322 <li>環境付き継続</li>
317 <!--
318 <li>__rectype の実装</li>
319 -->
320 </ul> 323 </ul>
321 </div> 324 </div>
322 <!-- PAGE --> 325 <!-- PAGE -->
323 <div class="slide"> 326 <div class="slide">
324 <h1>CbCの実装:__codeシンタックスの追加</h1> 327 <h1>CbCの実装:__codeシンタックスの追加</h1>
325 <ul> 328 <ul>
326 <li>__code キーワードでのコードセグメントの宣言</li> 329 <li>__code キーワードでのコードセグメントの宣言</li>
327 <ul> 330 <ul>
328 <li>__code 用idとkeywordを作成。</li> 331 <li>__code 用idとkeywordを作成。</li>
329 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> 332 <li>通常の関数作成と基本同じだが、コードセグメント判定用のフラグを立てる。</li>
330 </ul> 333 </ul>
331 </ul> 334 </ul>
332 <table width=100% border=1> 335 <table width=100% border=1>
333 <tr class="srctr"> 336 <tr class="srctr">
334 <td> 337 <td>
335 <pre> 338 <pre class="srcbox" style="height:13em">
339 tree
340 build_code_segment_type (tree value_type, tree arg_types)
341 {
342 tree t;
343 hashval_t hashcode = 0;
344
345 gcc_assert (TREE_CODE (value_type) == VOID_TYPE);
346
347 /* Make a node of the sort we want. */
348 t = make_node (FUNCTION_TYPE);
349 TREE_TYPE (t) = value_type;
350 TYPE_ARG_TYPES (t) = arg_types;
351
352 CbC_IS_CODE_SEGMENT (t) = 1;
353
354 if (!COMPLETE_TYPE_P (t))
355 layout_type (t);
356 return t;
357 }
358 </pre>
359 </td>
360 </tr>
361 </table>
362 <li><small>コードセグメントはGCC内部では関数として扱われる。</small></li>
363 </div>
364
365 <!-- SOURCE -->
366 <!--
336 const struct c_common_resword c_common_reswords[] = 367 const struct c_common_resword c_common_reswords[] =
337 { 368 {
338 { "_Bool", RID_BOOL, D_CONLY }, 369 { "_Bool", RID_BOOL, D_CONLY },
339 : 370 :
340 { "__code", RID_CbC_CODE, 0 }, 371 { "__code", RID_CbC_CODE, 0 },
341 </pre> 372 ...
342 </td> 373
343 </tr>
344 <tr class="srctr">
345 <td>
346 <pre>
347 case RID_CbC_CODE: 374 case RID_CbC_CODE:
348 : 375 :
349 specs->typespec_word = cts_CbC_code; 376 specs->typespec_word = cts_CbC_code;
350 </pre> 377 ...
351 </td> 378
352 </tr>
353 <tr class="srctr">
354 <td>
355 <pre>
356 case cts_CbC_code: 379 case cts_CbC_code:
357 : 380 :
358 specs->type = void_type_node; 381 specs->type = void_type_node;
359 break; 382 break;
360 </pre> 383 -->
361 </td> 384 <!--PAGE-->
362 </tr>
363 </table>
364 </div>
365 <!-- PAGE -->
366 <div class="slide"> 385 <div class="slide">
367 <h1>CbCの実装:gotoシンタックスの追加</h1> 386 <h1>CbCの実装:gotoシンタックスの追加</h1>
368 <li>goto によるコードセグメントへの継続</li> 387 <li>goto によるコードセグメントへの継続</li>
369 <ul> 388 <ul>
370 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> 389 <li>通常の goto の構文にコードセグメントへ継続する処理を追加。</li>
390 <!--
371 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> 391 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
392 -->
372 </ul> 393 </ul>
373 <li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li> 394 <table width=100% border=1>
374 <pre class="srcbox" style="font-size:25px; height:16em;"> 395 <tr>
396 <td>
397 <pre class="srcbox" style="font-size:25px; height:20em;" >
375 case RID_GOTO: 398 case RID_GOTO:
376 c_parser_consume_token (parser); 399 c_parser_consume_token (parser);
377 if ( c_parser_next_token_is (parser, CPP_NAME) 400 if ( c_parser_next_token_is (parser, CPP_NAME)
378 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) 401 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
379 { 402 {
388 c_parser_consume_token (parser); 411 c_parser_consume_token (parser);
389 val = c_parser_expression (parser).value; 412 val = c_parser_expression (parser).value;
390 mark_exp_read (val); 413 mark_exp_read (val);
391 stmt = c_finish_goto_ptr (loc, val); 414 stmt = c_finish_goto_ptr (loc, val);
392 } 415 }
416 #ifndef noCbC
393 else 417 else
394 expr = c_parser_expr_no_commas (parser, NULL);
395 if (TREE_CODE(expr.value) == CALL_EXPR )
396 { 418 {
397 location_t loc = c_parser_peek_token (parser)->location; 419 if (c_parser_next_token_is (parser, CPP_NAME))
398 cbc_replace_arguments (loc, expr.value); 420 {
399 TREE_TYPE(expr.value) = void_type_node; 421 tree id = c_parser_peek_token (parser)->value;
400 CbC_IS_CbC_GOTO (expr.value) = 1; 422 location_t loc = c_parser_peek_token (parser)->location;
401 CALL_EXPR_TAILCALL (expr.value) = 1; 423 /** build_external_ref (id,RID_CbC_CODE , loc); **/
402 add_stmt(expr.value); 424 build_external_ref (loc, id, RID_CbC_CODE, &expr.original_type);
403 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); 425 }
426 expr = c_parser_expr_no_commas (parser, NULL);
427 if (TREE_CODE(expr.value) == CALL_EXPR )
428 {
429 location_t loc = c_parser_peek_token (parser)->location;
430 cbc_replace_arguments (loc, expr.value);
431 TREE_TYPE(expr.value) = void_type_node;
432 CbC_IS_CbC_GOTO (expr.value) = 1;
433 CALL_EXPR_TAILCALL (expr.value) = 1;
434 add_stmt(expr.value);
435 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
436 }
437 else
438 c_parser_error (parser, "expected code segment jump or %<*%>");
404 } 439 }
440 #else
405 </pre> 441 </pre>
442 </td>
443 </tr>
444 </table>
406 </div> 445 </div>
407 <!-- PAGE --> 446 <!-- PAGE -->
408 <div class="slide"> 447 <div class="slide">
409 <h1>CbCの実装:gotoシンタックスの追加</h1> 448 <h1>CbCの実装:gotoシンタックスの追加</h1>
410 <ul> 449 <ul>
443 </pre> 482 </pre>
444 </td> 483 </td>
445 </tr> 484 </tr>
446 </table> 485 </table>
447 <ul> 486 <ul>
487 <li><small>これで__codeによるコードセグメントの宣言と、gotoによる関数呼び出しが行われるようになった。</small></li>
488 <li class="incremental"><small>次に、コードセグメントへの関数呼び出しは軽量継続で行わせる処理がいる。</small></li>
489 <!--
448 <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li> 490 <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
449 <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li> 491 <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
450 </ul> 492 -->
451 </div> 493 </ul>
452 <!-- PAGE --> 494 </div>
453 <div class="slide"> 495 <!-- PAGE -->
454 <h1>CbCの実装:TCE(末尾除去)</h1> 496 <div class="slide">
455 <h2>末尾除去:Tail Call Elimination(TCE)</h2> 497 <h1>CbCの実装:軽量継続(末尾除去)</h1>
498 <h2>軽量継続は<font color=red>末尾除去(Tail Call elimination)</font>によって実装される。</h2>
456 <ul> 499 <ul>
457 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li> 500 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
458 </ul> 501 </ul>
459 <li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li> 502 <li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
460 <br> 503 <br>
495 } 538 }
496 539
497 </pre> 540 </pre>
498 </td> 541 </td>
499 <td class="center"> 542 <td class="center">
500 <img src="./pix/continuation.png" style="height:100%;"> 543 <img src="./pix/continuation.png" style="height:90%;">
501 </td> 544 </td>
502 </tr> 545 </tr>
503 </table> 546 </table>
504 </div> 547 </div>
505 <!-- PAGE --> 548 <!-- PAGE -->
506 <div class="slide"> 549 <div class="slide">
507 <h1>CbCの実装:TCE(末尾除去)</h1> 550 <h1>CbCの実装:軽量継続(末尾除去)</h1>
508 <ul> 551 <ul>
509 <li>TCEにかかる条件</li> 552 <li>末尾除去にかかる条件</li>
510 <ul> 553 <ul>
511 <li>caller側とcallee側の戻値の型の一致している。</li> 554 <li>caller側とcallee側の戻値の型の一致している。</li>
512 <li>関数呼び出しがリターン直前に行われている。</li> 555 <li>関数呼び出しがリターン直前に行われている。</li>
513 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> 556 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
514 <li>引数の並びのコピーに上書きがない。</li> 557 <li>引数の並びのコピーに上書きがない。</li>
515 </ul> 558 </ul>
516 <li class="incremental">条件を回避する為以下の実装にする。</li> 559 <li class="incremental">条件を回避する為以下の実装にする。</li>
517 <ul class="incremental"> 560 <ul class="incremental">
518 <li>型はvoid型で統一する。</li> 561 <li>コードセグメントの型はvoid型で統一する。</li>
519 <li>gotoの直後にreturnを置く。</li> 562 <li>gotoの直後にreturnを置く。</li>
520 <li>スタックサイズは固定にする。</li> 563 <li>スタックサイズは固定にする。</li>
521 <li>引数は一旦、一時変数にコピーする。</li> 564 <li>引数は一旦、一時変数にコピーする。</li>
522 </ul> 565 </ul>
523 </ul> 566 </ul>
524 </div> 567 </div>
525 <!-- PAGE --> 568 <!-- PAGE -->
526 <div class="slide"> 569 <div class="slide">
527 <h1>CbCの実装:TCE(末尾除去)</h1> 570 <h1>CbCの実装:軽量継続(末尾除去)</h1>
528 <li>TCEの条件はexpand_call関数で調べられる。</li> 571 <li>末尾除去の条件はexpand_call関数で調べられる。</li>
529 <ul> 572 <ul>
530 <li>expand_call関数</li> 573 <li>expand_call関数</li>
531 <ul> 574 <ul>
532 <li>Treeで表された関数からRTLを生成する関数</li> 575 <li>Treeで表された関数からRTLを生成する関数</li>
533 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> 576 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
534 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li> 577 <li>try_taill_call(変数名)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。</li>
535 </ul> 578 </ul>
536 <li class="incremental">具体的な実装内容</li> 579 <li class="incremental">具体的な実装内容</li>
537 <ul> 580 <ul>
538 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li> 581 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
539 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li> 582 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
541 <ul> 584 <ul>
542 585
543 </div> 586 </div>
544 <!-- PAGE --> 587 <!-- PAGE -->
545 <div class="slide"> 588 <div class="slide">
546 <h1>CbCの実装:TCE(末尾除去)</h1> 589 <h1>CbCの実装:軽量継続(末尾除去)</h1>
547 <li>try_tail_callフラグが落とされる部分</li> 590 <li>try_tail_callフラグが落とされる部分</li>
548 <table width=100%> 591 <table width=100%>
549 <tr class="srctr"> 592 <tr class="srctr">
550 <td class="srctd"> 593 <td class="srctd">
551 <pre class="srcbox"> 594 <pre class="srcbox">
627 </table> 670 </table>
628 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li> 671 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
629 </div> 672 </div>
630 <!-- PAGE --> 673 <!-- PAGE -->
631 <div class="slide"> 674 <div class="slide">
632 <h1>CbCの実装:TCE(末尾除去)</h1> 675 <h1>CbCの実装:軽量継続(末尾除去)</h1>
633 <li>try_tail_callフラグ矯正付与のソースコード</li> 676 <li>try_tail_callフラグ矯正付与のソースコード</li>
634 <table width=100%> 677 <table width=100%>
635 <tr class="srctr"> 678 <tr class="srctr">
636 <td> 679 <td>
637 <pre class="srcbox"> 680 <pre class="srcbox">
650 </pre> 693 </pre>
651 </td> 694 </td>
652 </tr> 695 </tr>
653 </table> 696 </table>
654 <ul> 697 <ul>
655 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。 698 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。<small>(最適化の矯正付与)</small></li>
656 <br><small>(最適化の矯正付与)</small></li> 699 </ul>
657 </ul> 700 </div>
658 </div> 701 <!-- PAGE -->
659 <!-- PAGE --> 702 <div class="slide">
660 <div class="slide"> 703 <h1>CbCの実装:軽量継続(末尾除去)の実装について</h1>
661 <h1>CbCの実装:TCE(末尾除去)の実装について</h1>
662 <ul> 704 <ul>
663 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li> 705 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
664 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li> 706 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
665 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li> 707 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
666 </ul> 708 </ul>
667 </div> 709 </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 --> 710 <!-- PAGE -->
695 <!-- 711 <!--
696 <div class="slide"> 712 <div class="slide">
697 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1> 713 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
698 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br> 714 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
787 <li><small>生成しているコードと生成する為のコード</small></li> 803 <li><small>生成しているコードと生成する為のコード</small></li>
788 --> 804 -->
789 <table border=1 width=100%> 805 <table border=1 width=100%>
790 <tr> 806 <tr>
791 <td><small>生成しているコード</small></td> 807 <td><small>生成しているコード</small></td>
792 <td><small>生成されるTree</small></td> 808 <td><small>生成するコード(GCC内部)</small></td>
793 </tr> 809 </tr>
794 <tr class="srctr"> 810 <tr class="srctr">
795 <td width=50% class="srctd"> 811 <td width=50% class="srctd">
796 <pre class="srcbox" style="width:25em;"> 812 <pre class="srcbox" style="width:25em;">
797 813
809 } 825 }
810 _cbc_internal_return; 826 _cbc_internal_return;
811 }), __environment); 827 }), __environment);
812 </pre> 828 </pre>
813 </td> 829 </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"> 830 <td class="srctd">
837 <pre class="srcbox" style="width:25em;"> 831 <pre class="srcbox" style="width:25em;">
838 832
839 case RID_CbC_RET: 833 case RID_CbC_RET:
840 { 834 {
881 expr.value = c_finish_stmt_expr (location, stmt); 875 expr.value = c_finish_stmt_expr (location, stmt);
882 expr.original_code = ERROR_MARK; 876 expr.original_code = ERROR_MARK;
883 } 877 }
884 </pre> 878 </pre>
885 </td> 879 </td>
880 </td>
881 </tr>
882 </table>
883 <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
884 <!--
885 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
886 -->
887 </div>
888 <!-- PAGE -->
889 <!--
890 <div class="slide">
891 <h1>CbCの実装:環境付き継続</h1>
892 <table border=1 width=100%>
893 <tr>
894 <td width=50%><small>生成されるTree</small></td>
895 <td width=50%><small>生成する為のコード</small></td>
896 </tr>
897 <tr class="srctr">
898 <td class="srctd">
899 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
900 </td>
886 </tr> 901 </tr>
887 </table> 902 </table>
888 <!-- 903 </div>
889 <small> 904 -->
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>
902 </small>
903 -->
904 </div>
905 <!-- PAGE --> 905 <!-- PAGE -->
906 <div class="slide"> 906 <div class="slide">
907 <h1>環境付き継続:実装の問題</h1> 907 <h1>環境付き継続:実装の問題</h1>
908 <li>重要な部分</li> 908 <li>重要な部分</li>
909 <ul> 909 <ul>
911 </ul> 911 </ul>
912 <li>次の方法が考えられる。</li> 912 <li>次の方法が考えられる。</li>
913 <ul> 913 <ul>
914 <li>クロージャでの確保</li> 914 <li>クロージャでの確保</li>
915 <li>staticでの確保</li> 915 <li>staticでの確保</li>
916 <li>static thread local storage(tls)を用いての確保</li>
917 <!--
916 <li>setjmpを用いての実装</li> 918 <li>setjmpを用いての実装</li>
917 <li>static thread local storage(tls)を用いての確保</li>
918 <li>戻り値を入れるレジスタを明示的に指定</li> 919 <li>戻り値を入れるレジスタを明示的に指定</li>
920 -->
919 </ul> 921 </ul>
920 </div> 922 </div>
921 <!-- PAGE --> 923 <!-- PAGE -->
922 <div class="slide"> 924 <div class="slide">
923 <h1>環境付き継続:実装の問題</h1> 925 <h1>環境付き継続:実装の問題</h1>
933 <!-- <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> --> 935 <!-- <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
934 <ul> 936 <ul>
935 <li >マルチスレッドのプログラムに対応できない。</li> 937 <li >マルチスレッドのプログラムに対応できない。</li>
936 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> 938 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
937 </ul> 939 </ul>
938 940 <li class="incremental">static tlsでの実装</li>
939 <li>setjmpでの実装</li> 941 <!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
942 <ul class="incremental">
943 <li>現在はこの方法で実装を行なっている。</li>
944 <li>しかし、最適化にかけると正しい値が返ってこない。
945 <br>(最適化によりコードが削除されている...?)</li>
946 </ul>
947 </div>
948 <!-- PAGE -->
949 <div class="slide">
950 <h1>クロージャの動作について</h1>
951 <li>予稿における訂正</li>
952 <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
953 <ul>
954 <li>CbCの末尾除去矯正付与のせいでクロージャが破壊されていたことが判明。</li>
955 <li>GCC 4.6 と Lion でのクロージャは特に問題はなかった。</li>
956 </ul>
957 </div>
958 <!-- PAGE -->
959 <!--
960 <div class="slide">
961 <h1>環境付き継続:実装の問題</h1>
962 <ul>
963 <li>setjmpでの実装の問題点:</li>
940 <ul> 964 <ul>
941 <li>setjmpを行うTreeを生成するのが少し手間になる。</li> 965 <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
942 <li>int型の戻値しか得られない。</li> 966 <li>int型の戻値しか得られない。</li>
943 </ul> 967 </ul>
944 </ul> 968
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> 969 </ul>
957 <li>戻値を入れるレジスタを明示的に指定する。</li> 970 <li>戻値を入れるレジスタを明示的に指定する。</li>
958 <ul> 971 <ul>
959 <li>まだ実装を試していない。</li> 972 <li>まだ実装を試していない。</li>
960 </ul> 973 </ul>
961 </ul> 974 </ul>
962 </div> 975 </div>
976 -->
963 <!-- PAGE --> 977 <!-- PAGE -->
964 <div class="slide"> 978 <div class="slide">
965 <h1>Micro-Cとの比較</h1> 979 <h1>Micro-Cとの比較</h1>
966 <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
967 <table width=100% class="center"> 980 <table width=100% class="center">
981 <caption><small>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</small></caption>
968 <td> 982 <td>
969 <img src="./pix/mac_conv.png"> 983 <img src="./pix/mac_conv.png" style="height:10em">
970 </td> 984 </td>
971 <td> 985 <td>
972 <img src="./pix/linux_conv.png"> 986 <img src="./pix/linux_conv.png" style="height:10em">
973 </td> 987 </td>
974 </table> 988 </table>
975 <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 989 <li><small>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
976 その為に明らかに遅くなっていることが分かる。</li> 990 その為に明らかに遅くなっていることが分かる。</small></li>
977 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li> 991 <li><small>だがGCCの最適化有りの場合はMicro-C版よりも早い。</small></li>
978 </div> 992 </div>
979 <!-- PAGE --> 993 <!-- PAGE -->
980 <div class="slide"> 994 <div class="slide">
981 <h1>まとめ</h1> 995 <h1>まとめ</h1>
982 <ul> 996 <ul>
983 <li>今回GCC版CbCコンパイラのアップデートを行った。</li> 997 <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
984 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。 998 <li>末尾除去にかかる判定の部分の実装の修正を行った。
985 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li> 999 <br>それにより、以前より楽な管理ができる実装にすることができた。</li>
986 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li> 1000 <li>後は環境付き継続の最適化の問題の修正とselftypeといった新しい実装を行う。</li>
987 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> 1001 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
988 </ul> 1002 </ul>
989 </div> 1003 </div>
990 <!-- PAGE --> 1004 <!-- PAGE -->
991 <div class="slide"> 1005 <div class="slide">
1000 <br> 1014 <br>
1001 <h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2> 1015 <h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
1002 </div> 1016 </div>
1003 <!-- PAGE --> 1017 <!-- PAGE -->
1004 <div class="slide"> 1018 <div class="slide">
1005 <h1>CbCの実装:TCE(末尾除去)の動作</h1> 1019 <h1>CbCの引数渡し</h1>
1020 <table border=1 width=100%>
1021 <caption><small>fastcall属性有・無の実行速度</small></caption>
1022 <tr class="center">
1023 <td width=50%><small>fastcall有り</small></td>
1024 <td width=50%><small>fastcall無し</small></td>
1025 </tr>
1026 <tr class="center">
1027 <td>
1028 <img src="./pix/linux_conv_fastcall.png">
1029 </td>
1030 <td>
1031 <img src="./pix/linux_conv_nofastcall.png">
1032 </td>
1033 </tr>
1034 </table>
1035 </div>
1036 <!-- PAGE -->
1037 <div class="slide">
1038 <h1>CbCの実装:軽量継続(末尾除去)の動作</h1>
1006 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li> 1039 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
1007 <table width=100% border=1> 1040 <table width=100% border=1>
1008 <td> 1041 <td>
1009 <p class="center"> 1042 <p class="center">
1010 <img src="./pix/tce.png" style="height: 6em;"> 1043 <img src="./pix/tce.png" style="height: 6em;">