Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 78:6465e96ba272

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of continuation with environment
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Wed, 04 Jan 2012 17:12:52 +0900
parents 2697e09f6ce9
children 923dd8de7be2
comparison
equal deleted inserted replaced
77:2697e09f6ce9 78:6465e96ba272
502 </tr> 502 </tr>
503 </table> 503 </table>
504 </div> 504 </div>
505 <!-- PAGE --> 505 <!-- PAGE -->
506 <div class="slide"> 506 <div class="slide">
507 <h1>CbCの実装:TCE(末尾除去)の動作</h1>
508 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
509 <table width=100% border=1>
510 <td>
511 <p class="center">
512 <img src="./pix/tce.png" style="height: 6em;">
513 </p>
514 </td>
515 <td>
516 <ul>
517 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
518 <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
519 </ul>
520 </td>
521 </table>
522 <li class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
523 <li class="incremental">TCEにかかるには条件が幾つかある。</li>
524 </div>
525 <!-- PAGE -->
526 <div class="slide">
527 <h1>CbCの実装:TCE(末尾除去)</h1> 507 <h1>CbCの実装:TCE(末尾除去)</h1>
508 <ul>
528 <li>TCEにかかる条件</li> 509 <li>TCEにかかる条件</li>
529 <ol> 510 <ul>
530 <li>caller側とcallee側の戻値の型の一致している。</li> 511 <li>caller側とcallee側の戻値の型の一致している。</li>
531 <li>関数呼び出しがリターン直前に行われている。</li> 512 <li>関数呼び出しがリターン直前に行われている。</li>
532 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> 513 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
533 <li>引数の並びのコピーに上書きがない。</li> 514 <li>引数の並びのコピーに上書きがない。</li>
534 </ol> 515 </ul>
535 </div> 516 <li class="incremental">条件を回避する為以下の実装にする。</li>
536 <!-- PAGE --> 517 <ul class="incremental">
537 <div class="slide">
538 <h1>CbCの実装:TCE(末尾除去)</h1>
539 <li>条件を回避する為以下の実装にする。</li>
540 <ol>
541 <li>型はvoid型で統一する。</li> 518 <li>型はvoid型で統一する。</li>
542 <li>gotoの直後にreturnを置く。</li> 519 <li>gotoの直後にreturnを置く。</li>
543 <li>スタックサイズは固定にする。</li> 520 <li>スタックサイズは固定にする。</li>
544 <li>引数は一旦、一時変数にコピーする。</li> 521 <li>引数は一旦、一時変数にコピーする。</li>
545 </ol> 522 </ul>
523 </ul>
546 </div> 524 </div>
547 <!-- PAGE --> 525 <!-- PAGE -->
548 <div class="slide"> 526 <div class="slide">
549 <h1>CbCの実装:TCE(末尾除去)</h1> 527 <h1>CbCの実装:TCE(末尾除去)</h1>
550 <li>TCEの条件はexpand_call関数で調べられる。</li> 528 <li>TCEの条件はexpand_call関数で調べられる。</li>
561 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li> 539 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
562 </ul> 540 </ul>
563 <ul> 541 <ul>
564 542
565 </div> 543 </div>
566 <!-- PAGE -->
567 <!--
568 <div class="slide">
569 <h1>CbCの実装:TCE</h1>
570 <li>TCEにかかる条件</li>
571 <ul>
572 <li>try_tail_callフラグを落とさせない。</li>
573 </ul>
574 <li></li>
575 </div>
576 -->
577 <!-- PAGE --> 544 <!-- PAGE -->
578 <div class="slide"> 545 <div class="slide">
579 <h1>CbCの実装:TCE(末尾除去)</h1> 546 <h1>CbCの実装:TCE(末尾除去)</h1>
580 <li>try_tail_callフラグが落とされる部分</li> 547 <li>try_tail_callフラグが落とされる部分</li>
581 <table width=100%> 548 <table width=100%>
582 <tr class="srctr"> 549 <tr class="srctr">
583 <td> 550 <td class="srctd">
584 <pre class="srcbox"> 551 <pre class="srcbox">
552
585 if (currently_expanding_call++ != 0 553 if (currently_expanding_call++ != 0
586 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) 554 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))
587 && !flag_optimize_sibling_calls) 555 && !flag_optimize_sibling_calls)
588 || args_size.var 556 || args_size.var
589 || dbg_cnt (tail_call) == false) 557 || dbg_cnt (tail_call) == false)
590 try_tail_call = 0; 558 try_tail_call = 0;
591 </pre> 559
592 </td> 560 :
593 </tr> 561
594 </table>
595 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
596 </div>
597 <!-- PAGE -->
598 <div class="slide">
599 <h1>CbCの実装:TCE(末尾除去)</h1>
600 <li>try_tail_callフラグが落とされる部分</li>
601 <table width=100%>
602 <tr class="srctr">
603 <td class="srctd">
604 <pre class="srcbox">
605 if ( 562 if (
606 #ifdef HAVE_sibcall_epilogue 563 #ifdef HAVE_sibcall_epilogue
607 !HAVE_sibcall_epilogue 564 !HAVE_sibcall_epilogue
608 #else 565 #else
609 1 566 1
625 != targetm.calls.return_pops_args (current_function_decl, 582 != targetm.calls.return_pops_args (current_function_decl,
626 TREE_TYPE (current_function_decl), 583 TREE_TYPE (current_function_decl),
627 crtl->args.size)) 584 crtl->args.size))
628 || !lang_hooks.decls.ok_for_sibcall (fndecl)) 585 || !lang_hooks.decls.ok_for_sibcall (fndecl))
629 try_tail_call = 0; 586 try_tail_call = 0;
630 </pre> 587
631 </td> 588 :
632 </tr> 589
633 </table>
634 <li><small>引数のスタックサイズ、関数の型のチェックが行われる。</small></li>
635 </div>
636 <!-- PAGE -->
637 <div class="slide">
638 <h1>CbCの実装:TCE(末尾除去)</h1>
639 <li>try_tail_callフラグが落とされる部分</li>
640 <table width=100% >
641 <tr class="srctr">
642 <td class="srctd">
643 <pre class="srcbox" style="">
644 /* Check if caller and callee disagree in promotion of function 590 /* Check if caller and callee disagree in promotion of function
645 return value. */ 591 return value. */
646 #ifndef noCbC 592 #ifndef noCbC
647 if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))) 593 if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
648 #else 594 #else
674 || GET_MODE_BITSIZE (caller_mode) 620 || GET_MODE_BITSIZE (caller_mode)
675 < GET_MODE_BITSIZE (callee_mode))))) 621 < GET_MODE_BITSIZE (callee_mode)))))
676 try_tail_call = 0; 622 try_tail_call = 0;
677 } 623 }
678 </pre> 624 </pre>
679 </td> 625 </td>
680 </tr> 626 </tr>
681 </table> 627 </table>
682 <li>関数の型のチェックが行われる。</li> 628 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
683 </div> 629 </div>
684 <!-- PAGE --> 630 <!-- PAGE -->
685 <div class="slide"> 631 <div class="slide">
686 <h1>CbCの実装:TCE(末尾除去)</h1> 632 <h1>CbCの実装:TCE(末尾除去)</h1>
687 <li>try_tail_callフラグ矯正付与のソースコード</li> 633 <li>try_tail_callフラグ矯正付与のソースコード</li>
784 <!-- PAGE --> 730 <!-- PAGE -->
785 <div class="slide"> 731 <div class="slide">
786 <h1>CbCの実装:引数渡し</h1> 732 <h1>CbCの実装:引数渡し</h1>
787 <ul> 733 <ul>
788 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li> 734 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
789 <li></li> 735 </ul>
790 </ul> 736 <br>
791 <table width=100% border=1 class="center"> 737 <table width=100% border=1 class="center">
792 <caption>引数渡しに使われるレジスタの数(gcc)</caption> 738 <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
793 <tr> 739 <tr>
794 <td>arch</td> 740 <td>arch</td>
795 <td>int(整数型)</td> 741 <td>int(整数型)</td>
796 <td>float(浮動小数点型)</td> 742 <td>float(浮動小数点型)</td>
797 <td>double(浮動小数点型)</td> 743 <td>double(浮動小数点型)</td>
957 --> 903 -->
958 </div> 904 </div>
959 <!-- PAGE --> 905 <!-- PAGE -->
960 <div class="slide"> 906 <div class="slide">
961 <h1>環境付き継続:実装の問題</h1> 907 <h1>環境付き継続:実装の問題</h1>
962 <ul> 908 <li>重要な部分</li>
963 <li>リターンするretval変数が重要になってくる。</li> 909 <ul>
964 <li>retval変数のデータをどうやって確保するか。</li> 910 <li>リターンするretval変数のメモリ確保</li>
965 </ul> 911 </ul>
966 <li>次の方法が考えられる。</li> 912 <li>次の方法が考えられる。</li>
967 <ul> 913 <ul>
968 <li>クロージャでの確保</li> 914 <li>クロージャでの確保</li>
969 <li>staticでの確保</li> 915 <li>staticでの確保</li>
916 <li>setjmpを用いての実装</li>
970 <li>static thread local storage(tls)を用いての確保</li> 917 <li>static thread local storage(tls)を用いての確保</li>
918 <li>戻り値を入れるレジスタを明示的に指定</li>
971 </ul> 919 </ul>
972 </div> 920 </div>
973 <!-- PAGE --> 921 <!-- PAGE -->
974 <div class="slide"> 922 <div class="slide">
975 <h1>環境付き継続:実装の問題</h1> 923 <h1>環境付き継続:実装の問題</h1>
976 <ul> 924 <ul>
977 <li>クロージャでの実装の問題点:</li> 925 <li>クロージャでの実装の問題点:</li>
978 <!-- 926 <!-- <ul><li>クロージャにしてスタックに値を確保する。</li></ul> -->
979 <ul><li>クロージャにしてスタックに値を確保する。</li></ul> 927 <ul>
980 --> 928 <li >CbCでは継続によりスタックの値は破棄されていく。</li>
981 <ul> 929 <li >クロージャにしたコードが破棄される可能性がある。</li>
982 <li >CbCでは継続によりスタックの値は破棄されていく。</li> 930 </ul>
983 <li >クロージャにしたコードが破棄される可能性がある。</li> 931
984 </ul> 932 <li>staticでの実装の問題点:</li>
985 <br> 933 <!-- <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
986 <li>staticでの実装の問題点:</li> 934 <ul>
987 <!-- 935 <li >マルチスレッドのプログラムに対応できない。</li>
988 <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> 936 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
989 --> 937 </ul>
990 <ul> 938
991 <li >マルチスレッドのプログラムに対応できない。</li>
992 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
993 </ul>
994 </ul>
995 </div>
996 <!-- PAGE -->
997 <div class="slide">
998 <h1>環境付き継続:実装の問題</h1>
999 <li>static tlsでの実装</li>
1000 <ul>
1001 <li>スレッド毎に静的に値を確保する。</li>
1002 </ul>
1003 <li>現在はこの方法で実装を行なっている。</li>
1004 <li>しかし、最適化にかけると正しい値が返ってこない。
1005 <br>(最適化によりコードが削除されている...?)</li>
1006 </div>
1007 <!-- PAGE -->
1008 <div class="slide">
1009 <h1>環境付き継続:その他の実装方法</h1>
1010 <ul>
1011 <li>setjmpでの実装</li> 939 <li>setjmpでの実装</li>
1012 <ul> 940 <ul>
1013 <li>setjmpを行うTreeを生成するのが少し手間になる。</li> 941 <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
1014 <li>int型の戻値しか得られない。</li> 942 <li>int型の戻値しか得られない。</li>
1015 </ul> 943 </ul>
1016 <li>戻値を入れるレジスタを明示的に指定する。</li> 944 </ul>
1017 <ul> 945 </div>
1018 <li>まだ実装を試していない。</li> 946 <!-- PAGE -->
1019 </ul> 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>
1020 </ul> 961 </ul>
1021 </div> 962 </div>
1022 <!-- PAGE --> 963 <!-- PAGE -->
1023 <div class="slide"> 964 <div class="slide">
1024 <h1>Micro-Cとの比較</h1> 965 <h1>Micro-Cとの比較</h1>
1054 <ul> 995 <ul>
1055 <li>CbCによるタスクマネージャの作成</li> 996 <li>CbCによるタスクマネージャの作成</li>
1056 </ul> 997 </ul>
1057 <li>llvmへのCbCの実装</li> 998 <li>llvmへのCbCの実装</li>
1058 </ul> 999 </ul>
1059 <li>ご清聴ありがとうございました。</li> 1000 <br>
1001 <h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
1060 </div> 1002 </div>
1061 <!-- PAGE --> 1003 <!-- PAGE -->
1062 <div class="slide"> 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">
1063 <h1>CbCの機能の拡張:__rectype の実装</h1> 1024 <h1>CbCの機能の拡張:__rectype の実装</h1>
1025 <ul>
1064 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> 1026 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
1065 <small> 1027 <pre style="font-size:28px;">
1066 <pre>
1067 void factorial(int n, int result, void(*print)()){ 1028 void factorial(int n, int result, void(*print)()){
1068 : 1029 :
1069 (*print)(n,result,print,exit1, envp); 1030 (*print)(n,result,print,exit1, envp);
1070 } 1031 }
1071 </pre> 1032 </pre>
1072 </small>
1073 <li>以下の様に引数に()をつけて受けてることをやめたい。</li>
1074 <small>
1075 <pre>
1076 void factorial(int n, int result, void *print){
1077 :
1078 void(*print)(n,result,print,exit1, envp);
1079 }
1080 </pre>
1081 </small>
1082 </div>
1083 <!-- PAGE -->
1084 <div class="slide">
1085 <h1>CbCの機能の拡張:__rectype の実装</h1>
1086 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> 1033 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
1087 <pre> 1034 <pre style="font-size:28px;">
1088 __code factorial(int n, int result, __rectype *print) { 1035 __code factorial(int n, int result, __rectype *print) {
1089 : 1036 :
1090 goto (*print)(n,result,print,exit1, envp); 1037 goto (*print)(n,result,print,exit1, envp);
1091 } 1038 }
1092 </pre> 1039 </pre>
1040 </ul>
1093 </div> 1041 </div>
1094 <!-- PAGE --> 1042 <!-- PAGE -->
1095 <div class="slide"> 1043 <div class="slide">
1096 <h1>CbCの機能の拡張:selftype</h1> 1044 <h1>CbCの機能の拡張:selftype</h1>
1097 <h2>selftypeの実装</h2> 1045 <h2>selftypeの実装</h2>