Mercurial > hg > Papers > 2011 > nobu-prosym
comparison presen/index.html @ 77:2697e09f6ce9
modify
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 03 Jan 2012 22:11:32 +0900 |
parents | a4d16779fd1e |
children | 6465e96ba272 |
comparison
equal
deleted
inserted
replaced
76:a4d16779fd1e | 77:2697e09f6ce9 |
---|---|
319 --> | 319 --> |
320 </ul> | 320 </ul> |
321 </div> | 321 </div> |
322 <!-- PAGE --> | 322 <!-- PAGE --> |
323 <div class="slide"> | 323 <div class="slide"> |
324 <h1>CbCの実装:シンタックスの追加</h1> | 324 <h1>CbCの実装:__codeシンタックスの追加</h1> |
325 <ul> | 325 <ul> |
326 <li>__code キーワードでのコードセグメントの宣言</li> | 326 <li>__code キーワードでのコードセグメントの宣言</li> |
327 <ul> | 327 <ul> |
328 <li>__code 用idとkeywordを作成。</li> | 328 <li>__code 用idとkeywordを作成。</li> |
329 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> | 329 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> |
362 </tr> | 362 </tr> |
363 </table> | 363 </table> |
364 </div> | 364 </div> |
365 <!-- PAGE --> | 365 <!-- PAGE --> |
366 <div class="slide"> | 366 <div class="slide"> |
367 <h1>CbCの実装:シンタックスの追加</h1> | 367 <h1>CbCの実装:gotoシンタックスの追加</h1> |
368 <li>goto によるコードセグメントへの継続</li> | 368 <li>goto によるコードセグメントへの継続</li> |
369 <ul> | 369 <ul> |
370 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> | 370 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> |
371 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> | 371 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> |
372 </ul> | 372 </ul> |
373 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> | 373 <li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li> |
374 </div> | 374 <pre class="srcbox" style="font-size:25px; height:16em;"> |
375 <!-- PAGE --> | |
376 <div class="slide"> | |
377 <h1>CbCの実装:シンタックスの追加</h1> | |
378 <h2>gotoシンタックスの追加</h2> | |
379 <pre class="srcbox" style="font-size:25px; height:17em;"> | |
380 case RID_GOTO: | 375 case RID_GOTO: |
381 c_parser_consume_token (parser); | 376 c_parser_consume_token (parser); |
382 if ( c_parser_next_token_is (parser, CPP_NAME) | 377 if ( c_parser_next_token_is (parser, CPP_NAME) |
383 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) | 378 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) |
384 { | 379 { |
406 CALL_EXPR_TAILCALL (expr.value) = 1; | 401 CALL_EXPR_TAILCALL (expr.value) = 1; |
407 add_stmt(expr.value); | 402 add_stmt(expr.value); |
408 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); | 403 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); |
409 } | 404 } |
410 </pre> | 405 </pre> |
406 </div> | |
407 <!-- PAGE --> | |
408 <div class="slide"> | |
409 <h1>CbCの実装:gotoシンタックスの追加</h1> | |
410 <ul> | |
411 <small> | 411 <small> |
412 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> | 412 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> |
413 <li class="incremental">CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> | 413 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> |
414 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li> | 414 <li>最後にc_finish_return関数によりreturn文を生成している。</li> |
415 </small> | 415 </small> |
416 </div> | |
417 <!-- PAGE --> | |
418 <div class="slide"> | |
419 <h1>CbCの実装:シンタックスの追加</h1> | |
420 <h2>gotoシンタックスの追加</h2> | |
421 <ul> | |
422 <li>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</li> | |
423 <li>最後のリターン文生成も、末尾除去にかける為に必要な処理。</li> | |
424 </ul> | 416 </ul> |
425 <table border=1 width=100%> | 417 <table border=1 width=100%> |
426 <!-- | 418 <!-- |
427 <caption><small>return 自動生成</small></caption> | 419 <caption><small>return 自動生成</small></caption> |
428 --> | 420 --> |
429 <tr class="center"> | 421 <tr class="center"> |
430 <small> | 422 <td><small>実際のコード</small></td> |
431 <td>実際のコード </td> | 423 <td><small>GCC内で処理されるコード</small></td> |
432 <td>GCC 内で処理されるコード</td> | |
433 </small> | |
434 </tr> | 424 </tr> |
435 <tr class="srctr"> | 425 <tr class="srctr"> |
436 <td> | 426 <td> |
437 <pre> | 427 <pre> |
438 | 428 |
452 } | 442 } |
453 </pre> | 443 </pre> |
454 </td> | 444 </td> |
455 </tr> | 445 </tr> |
456 </table> | 446 </table> |
457 <!-- | 447 <ul> |
458 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> | 448 <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li> |
459 --> | 449 <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li> |
450 </ul> | |
460 </div> | 451 </div> |
461 <!-- PAGE --> | 452 <!-- PAGE --> |
462 <div class="slide"> | 453 <div class="slide"> |
463 <h1>CbCの実装:TCE(末尾除去)</h1> | 454 <h1>CbCの実装:TCE(末尾除去)</h1> |
464 <h2>末尾除去:Tail Call Elimination(TCE)</h2> | 455 <h2>末尾除去:Tail Call Elimination(TCE)</h2> |
727 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li> | 718 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li> |
728 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li> | 719 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li> |
729 </ul> | 720 </ul> |
730 </div> | 721 </div> |
731 <!-- PAGE --> | 722 <!-- PAGE --> |
723 <!-- | |
732 <div class="slide"> | 724 <div class="slide"> |
733 <h1>CbCの実装</h1> | 725 <h1>CbCの実装</h1> |
734 <li>CbCの基本機能を実現する為の実装は以上の2つになる。</li> | 726 <li>CbCの基本機能を実現する為の実装は以上の2つになる。</li> |
735 <ul> | 727 <ul> |
736 <li>シンタックスの追加</li> | 728 <li>シンタックスの追加</li> |
737 <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li> | 729 <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li> |
738 </ul> | 730 </ul> |
739 <li class="incremental">ここからはCbCの機能の拡張になる。</li> | 731 <li class="incremental">ここからはCbCの機能の拡張になる。</li> |
740 </div> | 732 </div> |
733 --> | |
741 <!-- PAGE --> | 734 <!-- PAGE --> |
742 <!-- | 735 <!-- |
743 <div class="slide"> | 736 <div class="slide"> |
744 <h1>CbCの実装:環境付き継続</h1> | 737 <h1>CbCの実装:環境付き継続</h1> |
745 <li>CbCにおけるCとの互換性を保つための機能。</li> | 738 <li>CbCにおけるCとの互換性を保つための機能。</li> |
808 <td>2</td> | 801 <td>2</td> |
809 <td>0<br>(stackを使用)</td> | 802 <td>0<br>(stackを使用)</td> |
810 <td>0<br>(stackを使用)</td> | 803 <td>0<br>(stackを使用)</td> |
811 </tr> | 804 </tr> |
812 <tr> | 805 <tr> |
813 <td>x86_64</td> | 806 <td>x64</td> |
814 <td>6</td> | 807 <td>6</td> |
815 <td>8</td> | 808 <td>8</td> |
816 <td>8</td> | 809 <td>8</td> |
817 </tr> | 810 </tr> |
818 </table> | 811 </table> |
837 } | 830 } |
838 </pre> | 831 </pre> |
839 </small> | 832 </small> |
840 </td> | 833 </td> |
841 </table> | 834 </table> |
842 <p><small>__environmentキーワードは関数の環境を保持する。</small></p> | 835 <p><small>__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。</small></p> |
843 </div> | 836 </div> |
844 <!-- PAGE --> | 837 <!-- PAGE --> |
845 <div class="slide"> | 838 <div class="slide"> |
846 <h1>CbCの実装:環境付き継続</h1> | 839 <h1>CbCの実装:環境付き継続</h1> |
847 <!-- | 840 <!-- |
848 <li><small>生成しているコードと生成する為のコード</small></li> | 841 <li><small>生成しているコードと生成する為のコード</small></li> |
849 --> | 842 --> |
850 <table border=1 width=100%> | 843 <table border=1 width=100%> |
851 <tr> | 844 <tr> |
852 <td><small>生成しているコード</small></td> | 845 <td><small>生成しているコード</small></td> |
853 <td><small>生成する為のコード</small></td> | 846 <td><small>生成されるTree</small></td> |
854 </tr> | 847 </tr> |
855 <tr class="srctr"> | 848 <tr class="srctr"> |
856 <td width=50% class="srctd"> | 849 <td width=50% class="srctd"> |
857 <pre class="srcbox" style="width:25em;"> | 850 <pre class="srcbox" style="width:25em;"> |
858 | 851 |
978 </ul> | 971 </ul> |
979 </div> | 972 </div> |
980 <!-- PAGE --> | 973 <!-- PAGE --> |
981 <div class="slide"> | 974 <div class="slide"> |
982 <h1>環境付き継続:実装の問題</h1> | 975 <h1>環境付き継続:実装の問題</h1> |
983 <li>クロージャでの実装</li> | 976 <ul> |
984 <ul> | 977 <li>クロージャでの実装の問題点:</li> |
985 <li>クロージャにしてスタックに値を確保する。</li> | 978 <!-- |
986 <li></li> | 979 <ul><li>クロージャにしてスタックに値を確保する。</li></ul> |
987 </ul> | 980 --> |
988 <li>問題点</li> | 981 <ul> |
989 <ul> | 982 <li >CbCでは継続によりスタックの値は破棄されていく。</li> |
990 <li class="incremental">しかしCbCではスタックの値は破棄されていく。</li> | 983 <li >クロージャにしたコードが破棄される可能性がある。</li> |
991 <li class="incremental">その為スタックに値を確保するのは好ましくない。</li> | 984 </ul> |
992 </ul> | 985 <br> |
993 </div> | 986 <li>staticでの実装の問題点:</li> |
994 <!-- PAGE --> | 987 <!-- |
995 <div class="slide"> | 988 <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> |
996 <h1>環境付き継続:実装の問題</h1> | 989 --> |
997 <li>staticでの実装</li> | 990 <ul> |
998 <ul> | 991 <li >マルチスレッドのプログラムに対応できない。</li> |
999 <li>静的に値を確保することでスタック破棄の影響を受けない。</li> | 992 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> |
1000 </ul> | 993 </ul> |
1001 <li>問題点</li> | |
1002 <ul> | |
1003 <li class="incremental">マルチスレッドのプログラムに対応できない。</li> | |
1004 <li class="incremental">値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> | |
1005 </ul> | 994 </ul> |
1006 </div> | 995 </div> |
1007 <!-- PAGE --> | 996 <!-- PAGE --> |
1008 <div class="slide"> | 997 <div class="slide"> |
1009 <h1>環境付き継続:実装の問題</h1> | 998 <h1>環境付き継続:実装の問題</h1> |
1011 <ul> | 1000 <ul> |
1012 <li>スレッド毎に静的に値を確保する。</li> | 1001 <li>スレッド毎に静的に値を確保する。</li> |
1013 </ul> | 1002 </ul> |
1014 <li>現在はこの方法で実装を行なっている。</li> | 1003 <li>現在はこの方法で実装を行なっている。</li> |
1015 <li>しかし、最適化にかけると正しい値が返ってこない。 | 1004 <li>しかし、最適化にかけると正しい値が返ってこない。 |
1016 <br>(恐らくTreeの生成の部分が間違っている。)</li> | 1005 <br>(最適化によりコードが削除されている...?)</li> |
1017 </div> | 1006 </div> |
1018 <!-- PAGE --> | 1007 <!-- PAGE --> |
1019 <div class="slide"> | 1008 <div class="slide"> |
1020 <h1>環境付き継続:その他の実装方法</h1> | 1009 <h1>環境付き継続:その他の実装方法</h1> |
1021 <ul> | 1010 <ul> |
1047 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li> | 1036 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li> |
1048 </div> | 1037 </div> |
1049 <!-- PAGE --> | 1038 <!-- PAGE --> |
1050 <div class="slide"> | 1039 <div class="slide"> |
1051 <h1>まとめ</h1> | 1040 <h1>まとめ</h1> |
1052 <ul> | 1041 <ul> |
1053 <li>今回GCC版CbCコンパイラのアップデートを行った。</li> | 1042 <li>今回GCC版CbCコンパイラのアップデートを行った。</li> |
1054 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。 | 1043 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。 |
1055 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li> | 1044 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li> |
1056 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li> | 1045 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li> |
1057 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> | 1046 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> |
1058 </ul> | 1047 </ul> |
1059 </div> | 1048 </div> |
1060 <!-- PAGE --> | 1049 <!-- PAGE --> |
1061 <div class="slide"> | 1050 <div class="slide"> |
1062 <h1>今後の予定</h1> | 1051 <h1>今後の予定</h1> |
1063 <ul> | 1052 <ul> |
1064 <li>CbCを用いたプログラムの作成</li> | 1053 <li>CbCを用いたプログラムの作成</li> |
1065 <ul> | 1054 <ul> |
1066 <li>CbCによるタスクマネージャの作成</li> | 1055 <li>CbCによるタスクマネージャの作成</li> |
1067 </ul> | 1056 </ul> |
1068 <li>llvmへのCbCの実装</li> | 1057 <li>llvmへのCbCの実装</li> |
1069 </ul> | 1058 </ul> |
1070 </div> | 1059 <li>ご清聴ありがとうございました。</li> |
1060 </div> | |
1071 <!-- PAGE --> | 1061 <!-- PAGE --> |
1072 <div class="slide"> | 1062 <div class="slide"> |
1073 <h1>CbCの機能の拡張:__rectype の実装</h1> | 1063 <h1>CbCの機能の拡張:__rectype の実装</h1> |
1074 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> | 1064 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> |
1075 <small> | 1065 <small> |