Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html~ @ 85:7ed352ddae10

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify spell miss
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 07 Jan 2012 12:52:25 +0900
parents 07c5304622ac
children
comparison
equal deleted inserted replaced
84:fb5994f49abd 85:7ed352ddae10
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 <!--
116 <div class="">
117 <h1>先行研究</h1>
118 <li>Continuation based c コン パイラの gcc-4.2 による実装</li>
119 <li></li>
120 </div>
121 -->
122 <!-- PAGE -->
115 <div class="slide"> 123 <div class="slide">
116 <h1>発表内容</h1> 124 <h1>発表内容</h1>
117 <ol> 125 <ol>
118 <li>CbC の紹介</li> 126 <li>CbC の紹介</li>
119 <li>GCC でのコンパイルの流れ</li> 127 <li>GCC でのコンパイルの流れ</li>
398 case RID_GOTO: 406 case RID_GOTO:
399 c_parser_consume_token (parser); 407 c_parser_consume_token (parser);
400 if ( c_parser_next_token_is (parser, CPP_NAME) 408 if ( c_parser_next_token_is (parser, CPP_NAME)
401 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) 409 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
402 { 410 {
403 stmt = c_finish_goto_label (loc, 411 :
404 c_parser_peek_token (parser)->value);
405 c_parser_consume_token (parser);
406 }
407 else if (c_parser_next_token_is (parser, CPP_MULT))
408 {
409 tree val;
410
411 c_parser_consume_token (parser);
412 val = c_parser_expression (parser).value;
413 mark_exp_read (val);
414 stmt = c_finish_goto_ptr (loc, val);
415 } 412 }
416 #ifndef noCbC 413 #ifndef noCbC
417 else 414 else
418 { 415 {
419 if (c_parser_next_token_is (parser, CPP_NAME)) 416 if (c_parser_next_token_is (parser, CPP_NAME))
570 <h1>CbCの実装:軽量継続(末尾除去)</h1> 567 <h1>CbCの実装:軽量継続(末尾除去)</h1>
571 <li>末尾除去の条件はexpand_call関数で調べられる。</li> 568 <li>末尾除去の条件はexpand_call関数で調べられる。</li>
572 <ul> 569 <ul>
573 <li>expand_call関数</li> 570 <li>expand_call関数</li>
574 <ul> 571 <ul>
575 <li>Treeで表された関数からRTLを生成する関数</li> 572 <li>SSAへの変換を終えたGIMPLEからとり出されたCALL_EXPREのTreeからRTLを生成する関数</li>
576 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> 573 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
577 <li>try_taill_call(変数名)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。</li> 574 <li>try_taill_call(局所変数)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。</li>
578 </ul> 575 </ul>
579 <li class="incremental">具体的な実装内容</li> 576 <li class="incremental">具体的な実装内容</li>
580 <ul> 577 <ul>
581 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li> 578 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
582 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li> 579 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
585 582
586 </div> 583 </div>
587 <!-- PAGE --> 584 <!-- PAGE -->
588 <div class="slide"> 585 <div class="slide">
589 <h1>CbCの実装:軽量継続(末尾除去)</h1> 586 <h1>CbCの実装:軽量継続(末尾除去)</h1>
590 <li>try_tail_callフラグが落とされる部分</li> 587 <ul>
591 <table width=100%> 588 <li><small>try_tail_callフラグを落とさせない。</small></li>
592 <tr class="srctr"> 589 <pre class="srcbox" style="font-size:28px;">
593 <td class="srctd">
594 <pre class="srcbox">
595
596 if (currently_expanding_call++ != 0 590 if (currently_expanding_call++ != 0
597 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) 591 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))
598 && !flag_optimize_sibling_calls) 592 && !flag_optimize_sibling_calls)
599 || args_size.var 593 || args_size.var
600 || dbg_cnt (tail_call) == false) 594 || dbg_cnt (tail_call) == false)
601 try_tail_call = 0; 595 try_tail_call = 0;
602
603 :
604
605 if (
606 #ifdef HAVE_sibcall_epilogue
607 !HAVE_sibcall_epilogue
608 #else
609 1
610 #endif
611 || !try_tail_call
612 || structure_value_addr != NULL_RTX
613 #ifdef REG_PARM_STACK_SPACE
614 || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
615 != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
616 || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl))
617 #endif
618 || !targetm.function_ok_for_sibcall (fndecl, exp)
619 || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
620 || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
621 || (fndecl && decl_function_context (fndecl) == current_function_decl)
622 || args_size.constant > (crtl->args.size
623 - crtl->args.pretend_args_size)
624 || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
625 != targetm.calls.return_pops_args (current_function_decl,
626 TREE_TYPE (current_function_decl),
627 crtl->args.size))
628 || !lang_hooks.decls.ok_for_sibcall (fndecl))
629 try_tail_call = 0;
630
631 :
632
633 /* Check if caller and callee disagree in promotion of function
634 return value. */
635 #ifndef noCbC
636 if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
637 #else
638 if (try_tail_call)
639 #endif
640 {
641 enum machine_mode caller_mode, caller_promoted_mode;
642 enum machine_mode callee_mode, callee_promoted_mode;
643 int caller_unsignedp, callee_unsignedp;
644 tree caller_res = DECL_RESULT (current_function_decl);
645
646 caller_unsignedp = TYPE_UNSIGNED (TREE_TYPE (caller_res));
647 caller_mode = DECL_MODE (caller_res);
648 callee_unsignedp = TYPE_UNSIGNED (TREE_TYPE (funtype));
649 callee_mode = TYPE_MODE (TREE_TYPE (funtype));
650 caller_promoted_mode
651 = promote_function_mode (TREE_TYPE (caller_res), caller_mode,
652 &caller_unsignedp,
653 TREE_TYPE (current_function_decl), 1);
654 callee_promoted_mode
655 = promote_function_mode (TREE_TYPE (funtype), callee_mode,
656 &callee_unsignedp,
657 funtype, 1);
658 if (caller_mode != VOIDmode
659 && (caller_promoted_mode != callee_promoted_mode
660 || ((caller_mode != caller_promoted_mode
661 || callee_mode != callee_promoted_mode)
662 && (caller_unsignedp != callee_unsignedp
663 || GET_MODE_BITSIZE (caller_mode)
664 < GET_MODE_BITSIZE (callee_mode)))))
665 try_tail_call = 0;
666 }
667 </pre> 596 </pre>
668 </td> 597 <ul>
669 </tr> 598 <!--
670 </table> 599 <li>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</li>
671 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li> 600 -->
672 </div> 601 </ul>
673 <!-- PAGE --> 602 <li><small>try_tail_callフラグ矯正付与のソースコード</small></li>
674 <div class="slide"> 603 <pre class="srcbox" style="font-size:28px;">
675 <h1>CbCの実装:軽量継続(末尾除去)</h1>
676 <li>try_tail_callフラグ矯正付与のソースコード</li>
677 <table width=100%>
678 <tr class="srctr">
679 <td>
680 <pre class="srcbox">
681 #ifndef noCbC
682 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)) 604 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
683 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl)) 605 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
684 && try_tail_call == 0) 606 && try_tail_call == 0)
685 { 607 {
686 location_t loc = EXPR_LOCATION (exp); 608 location_t loc = EXPR_LOCATION (exp);
687 char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl)); 609 char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
688 warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.", 610 warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
689 name_callee); 611 name_callee);
690 try_tail_call = 1; 612 try_tail_call = 1;
691 } 613 }
692 #endif
693 </pre> 614 </pre>
694 </td>
695 </tr>
696 </table>
697 <ul>
698 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。<small>(最適化の矯正付与)</small></li>
699 </ul>
700 </div> 615 </div>
701 <!-- PAGE --> 616 <!-- PAGE -->
702 <div class="slide"> 617 <div class="slide">
703 <h1>CbCの実装:軽量継続(末尾除去)の実装について</h1> 618 <h1>CbCの実装:軽量継続(末尾除去)の実装について</h1>
704 <ul> 619 <ul>
739 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 654 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
740 declspecs_add_attrs(specs, attrs); 655 declspecs_add_attrs(specs, attrs);
741 } 656 }
742 </pre> 657 </pre>
743 </small> 658 </small>
744 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p> 659 <p><small>Intel64 ではレジスタが増えていてfastcallの機能は標準でつくようになっている。</small></p>
745 </div> 660 </div>
746 <!-- PAGE --> 661 <!-- PAGE -->
747 <div class="slide"> 662 <div class="slide">
748 <h1>CbCの実装:引数渡し</h1> 663 <h1>CbCの実装:引数渡し</h1>
749 <ul> 664 <ul>
750 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li> 665 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
751 </ul> 666 </ul>
752 <br> 667 <br>
668 <br>
753 <table width=100% border=1 class="center"> 669 <table width=100% border=1 class="center">
754 <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption> 670 <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
755 <tr> 671 <tr>
756 <td>arch</td> 672 <td>arch</td>
757 <td>int(整数型)</td> 673 <td>int(整数型)</td>
884 <!-- 800 <!--
885 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li> 801 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
886 --> 802 -->
887 </div> 803 </div>
888 <!-- PAGE --> 804 <!-- 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>
901 </tr>
902 </table>
903 </div>
904 -->
905 <!-- PAGE --> 805 <!-- PAGE -->
906 <div class="slide"> 806 <div class="slide">
907 <h1>環境付き継続:実装の問題</h1> 807 <h1>環境付き継続:実装の問題</h1>
908 <li>重要な部分</li> 808 <li>重要な部分</li>
909 <ul> 809 <ul>
984 </td> 884 </td>
985 <td> 885 <td>
986 <img src="./pix/linux_conv.png" style="height:10em"> 886 <img src="./pix/linux_conv.png" style="height:10em">
987 </td> 887 </td>
988 </table> 888 </table>
989 <li><small>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 889 <li><small>最適化無しだと、引数を全て一時変数に代入するGCCは遅い。
990 その為に明らかに遅くなっていることが分かる。</small></li> 890 だが、最適化にかければ不要な代入は減りMicro-C版より早くなる。</small></li>
991 <li><small>だがGCCの最適化有りの場合はMicro-C版よりも早い。</small></li>
992 </div> 891 </div>
993 <!-- PAGE --> 892 <!-- PAGE -->
994 <div class="slide"> 893 <div class="slide">
995 <h1>まとめ</h1> 894 <h1>まとめ</h1>
996 <ul> 895 <ul>
1001 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> 900 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
1002 </ul> 901 </ul>
1003 </div> 902 </div>
1004 <!-- PAGE --> 903 <!-- PAGE -->
1005 <div class="slide"> 904 <div class="slide">
1006 <h1>今後の予定</h1> 905 <h1>今後の課題</h1>
1007 <ul> 906 <ul>
1008 <li>CbCを用いたプログラムの作成</li> 907 <li>CbCを用いたプログラムの作成</li>
1009 <ul> 908 <ul>
1010 <li>CbCによるタスクマネージャの作成</li> 909 <li>CbCによるタスクマネージャの作成</li>
1011 </ul> 910 </ul>
1048 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li> 947 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
1049 <li><small>func_bの為にスタックポインタは伸ばされない</small></li> 948 <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
1050 </ul> 949 </ul>
1051 </td> 950 </td>
1052 </table> 951 </table>
952 </div>
953 <!-- PAGE -->
954 <div class="slide">
955 <h1>call_insn</h1>
956 <li>expand_callより作成されたRTLのTreeは以下のS式となる。</li>
957 <pre class="srcbox" style="font-size:28px; width:45em;">
958
959 (call_insn/j 18 17 19 3 (call (mem:QI (symbol_ref:DI ("factorial") [flags 0x403] &lt;function_decl 0x1443b4400 factorial&gt;) [0 S1 A8])
960 (const_int 1024 [0x400])) factorial.cbc:30 -1
961 (expr_list:REG_EH_REGION (const_int 0 [0])
962 (nil))
963 (expr_list:REG_DEP_TRUE (use (reg:SI 5 di))
964 (nil)))
965 </pre>
966 <li></li>
1053 </div> 967 </div>
1054 <!-- PAGE --> 968 <!-- PAGE -->
1055 <div class="slide"> 969 <div class="slide">
1056 <h1>__rectype の実装</h1> 970 <h1>__rectype の実装</h1>
1057 <ul> 971 <ul>
1086 </pre> 1000 </pre>
1087 <p>selftype は struct node を指す。</p> 1001 <p>selftype は struct node を指す。</p>
1088 </small> 1002 </small>
1089 </div> 1003 </div>
1090 <!-- PAGE --> 1004 <!-- PAGE -->
1005 <div class="slide">
1006 <h1>環境付き継続</h1>
1007 <table border=1 width=100%>
1008 <tr>
1009 <td width=50%><small>生成する為のコード</small></td>
1010 <td width=50%><small>生成されるTree</small></td>
1011 </tr>
1012 <tr class="srctr">
1013 <td class="srctd">
1014 <pre class="srcbox" style="width:25em;">
1015
1016 case RID_CbC_RET:
1017 {
1018 tree value, stmt, label, tlab, decl;
1019 c_parser_consume_token (parser);
1020
1021 stmt = c_begin_stmt_expr ();
1022 cbc_return_f = c_parser_peek_token (parser)->value;
1023 location_t location = c_parser_peek_token (parser)->location;
1024
1025 /* create label. (__label__ _cbc_exit0;) */
1026 label = get_identifier ("_cbc_exit0");
1027 tlab = declare_label (label);
1028 C_DECLARED_LABEL_FLAG (tlab) = 1;
1029 add_stmt (build_stmt (location, DECL_EXPR, tlab));
1030
1031 /* declare retval. (int retval;) */
1032 tree decl_cond =
1033 build_decl (location, VAR_DECL, get_identifier ("retval"),
1034 TREE_TYPE (TREE_TYPE (current_function_decl)));
1035 TREE_STATIC (decl_cond) = 1;
1036 TREE_USED (decl_cond) = 1;
1037
1038 /* Use thread-local */
1039 DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
1040 DECL_NONLOCAL (decl_cond) = 1;
1041 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond)));
1042
1043 /* define nested function. */
1044 decl =
1045 cbc_finish_nested_function (location, label, decl_cond);
1046 TREE_USED(decl) = 1;
1047
1048 /* define if-ed goto label and return statement. */
1049 cbc_finish_labeled_goto (location, label, decl_cond);
1050
1051 /* get pointer to nested function. */
1052 value = build_addr (decl , current_function_decl);
1053 TREE_USED (current_function_decl) = 1;
1054 SET_EXPR_LOCATION (value, location);
1055 add_stmt (value);
1056
1057 TREE_SIDE_EFFECTS (stmt) = 1;
1058 expr.value = c_finish_stmt_expr (location, stmt);
1059 expr.original_code = ERROR_MARK;
1060 }
1061 </pre>
1062 </td>
1063
1064
1065 <td class="srctd">
1066 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
1067 </td>
1068
1069 </tr>
1070 </table>
1071 </div>
1072 <!--PAGE-->
1073 <div class="slide">
1074 <h1>環境付き継続</h1>
1075 <table border=1 width=100%>
1076 <tr>
1077 <td><small>生成しているコード</small></td>
1078 <td><small>生成されるTree</small></td>
1079 </tr>
1080 <tr class="srctr">
1081 <td width=50% class="srctd">
1082 <pre class="srcbox" style="width:25em;">
1083
1084 //goto c1(__return, __environment);
1085 goto c1(({
1086 __label__ _cbc_exit0;
1087 static int retval;
1088 void _cbc_internal_return(int retval_, void *_envp) {
1089 retval = retval_;
1090 goto _cbc_exit0;
1091 }
1092 if (0) {
1093 _cbc_exit0:
1094 return retval;
1095 }
1096 _cbc_internal_return;
1097 }), __environment);
1098 </pre>
1099 </td>
1100 <td class="srctd">
1101 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
1102 </td>
1103 </tr>
1104 </table>
1105 </div>
1106 <!--PAGE-->
1107 <div class="slide">
1108 <h1></h1>
1109 <li>引数の並びの上書きにコピーが無い。</li>
1110 <pre style="font-size:28px;">
1111 __code cs_a(int a, int b) {
1112 goto cs_b(b,a);
1113 }
1114 </pre>
1115 <img src="./pix/cs_prog.png">
1116 </div>
1117 <!--PAGE-->
1118
1091 </div> 1119 </div>
1092 </body> 1120 </body>
1093 </html> 1121 </html>