Mercurial > hg > Papers > 2010 > kent-master

comparison recital-slide/slide.html @ 16:d9b85f041908

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
up recital
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2010 14:00:55 +0900
parents 67544736317e
children 7c25b2856f27
comparison
equal deleted inserted replaced
15:67544736317e 16:d9b85f041908
167 </li> 167 </li>
168 </ul> 168 </ul>
169 <p class="subtitle"></p> 169 <p class="subtitle"></p>
170 </div> 170 </div>
171 171
172 <div class="slide">
173 <h1>継続とはなんなのか？</h1>
174 <p class="subtitle">継続</p>
175 <ul>
176 <li>現在の処理を続行するための情報
177 <ul>
178 <li>Cならば続く命令のアドレスや</li>
179 <li>命令に必要な値、</li>
180 <li>スタックなど、その環境全てを含む</li>
181 </ul>
182 </li>
183 </ul>
184 <p class="subtitle">CbCでの軽量継続</p>
185 <ul>
186 <li>継続からスタックに関する情報を落とす</li>
187 <li>続く命令とデータのみのシンプルな継続</li>
188 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
189 </ul>
190 </div>
191
172 <div class="slide" style="font-size:95%;"> 192 <div class="slide" style="font-size:95%;">
173 <h1>コードセグメントと軽量継続の記述</h1> 193 <h1>コードセグメントと軽量継続の記述</h1>
174 <pre style="float:right; width-max:45%"> 194 <pre style="float:right; width-max:45%">
175 <code>typedef code (*NEXT)(int); 195 <code>typedef code (*NEXT)(int);
176 int main(int argc, char **argv) { 196 int main(int argc, char **argv) {
283 303
284 <div class="slide"> 304 <div class="slide">
285 <h1>First: 軽量継続の実装</h1> 305 <h1>First: 軽量継続の実装</h1>
286 <p class="subtitle">軽量継続を実装するには？</p> 306 <p class="subtitle">軽量継続を実装するには？</p>
287 <ul> 307 <ul>
288 <li>河野先生の作ったmicro-cは元より軽量継続を考慮して良く設計されている</li> 308 <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
289 <li>micro-Cと同じ命令列を出力させるのは難しい</li> 309 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
290 <li>関数コール(call命令)ではもちろんダメ</li> 310 <li>関数コール(call命令)ではもちろんダメ</li>
291 <li>必ず<em>jmp命令</em>を出力しないといけない</li> 311 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
292 <li>スタックを拡張してはいけない</li> 312 <li>スタックを拡張してはいけない</li>
293 <li>しかしGCCでは<em>関数をベース</em>にしなければならない</li> 313 <li>加えて、GCCでは<em>関数をベース</em>にしなければならない</li>
294 </ul> 314 </ul>
295 <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p> 315 <p class="subtitle">そこで、<dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
296 </div> 316 </div>
297 317
298 <div class="slide"> 318 <div class="slide">
299 <h1>First: 軽量継続の実装</h1> 319 <h1>First: 軽量継続の実装</h1>
300 <p class="subtitle">末尾呼出ってなに？</p> 320 <p class="subtitle">末尾呼出ってなに？</p>
316 <li>GCCが最適化してくれる (<em>TCE</em>)</li> 336 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
317 <li>元の関数に戻らないため少し高速に</li> 337 <li>元の関数に戻らないため少し高速に</li>
318 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li> 338 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
319 </ul> 339 </ul>
320 <p class="subtitle incremental">この末尾呼出(TCE)を強制して軽量継続を実装！</p> 340 <p class="subtitle incremental">この末尾呼出(TCE)を強制して軽量継続を実装！</p>
341 </div>
342
343 <div class="slide">
344 <h1>First: 軽量継続の実装</h1>
345 <p class="subtitle">プログラム実行時のスタックの変化</p>
321 </div> 346 </div>
322 347
323 <div class="slide"> 348 <div class="slide">
324 <h1>First: x86における高速化</h1> 349 <h1>First: x86における高速化</h1>
325 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p> 350 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
506 } 531 }
507 } 532 }
508 </code></pre> 533 </code></pre>
509 <p class="subtitle">環境付き継続の使用例</p> 534 <p class="subtitle">環境付き継続の使用例</p>
510 <ul> 535 <ul>
511 <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li> 536 <li><code><em>__return</em></code>で表される特殊なコードセグメント</li>
512 <li>コードセグメントからは通常のコードセグメントポインタに見える</li> 537 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
513 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li> 538 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
514 </ul> 539 </ul>
515 </div> 540 </div>
516 541
541 566
542 <div class="slide" style="font-size:95%;"> 567 <div class="slide" style="font-size:95%;">
543 <h1>Second: Cとの相互利用・評価</h1> 568 <h1>Second: Cとの相互利用・評価</h1>
544 <p class="subtitle">この取り組みにより</p> 569 <p class="subtitle">この取り組みにより</p>
545 <ul> 570 <ul>
546 <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li> 571 <li>これにより、<dfn>Continuation based C</dfn> の全仕様を満たした</li>
547 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li> 572 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
548 </ul> 573 </ul>
549 </div> 574 </div>
550 575
551 576
555 <p class="subtitle">本研究での取り組み</p> 580 <p class="subtitle">本研究での取り組み</p>
556 <dl> 581 <dl>
557 <dt>First</dt> 582 <dt>First</dt>
558 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった 583 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
559 <ul> 584 <ul>
560 <li><em>軽量継続における引数順序の制限を取り除いた</em></li> 585 <li>軽量継続における引数順序の制限を取り除いた</li>
561 <li>PowerPCでの間接継続の制限を取り除いた</li> 586 <li>PowerPCでの間接継続の制限を取り除いた</li>
562 <li><em>x86アーキテクチャにて高速化を行った</em></li> 587 <li><em>x86アーキテクチャにて高速化を行った</em></li>
563 </ul> 588 </ul>
564 </dd> 589 </dd>
565 <dt>Second</dt> 590 <dt>Second</dt>
593 <div class="slide"> 618 <div class="slide">
594 <h1>今後の課題</h1> 619 <h1>今後の課題</h1>
595 <p class="subtitle"></p> 620 <p class="subtitle"></p>
596 <ul> 621 <ul>
597 <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li> 622 <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li>
623 <li>タブロー方を用いた検証</li>
624 <li>TaskManagerのCbC実装</li>
625 </ul>
626 <p class="subtitle">CbC言語の今後</p>
627 <ul>
628 <li>オブジェクティブなCbCの設計</li>
629 <li>データセグメントの導入</li>
630 <li>スケジューラのためのリフレクション</li>
631 </ul>
632 </div>
633
634
635 <div class="slide">
636 <h1>おわり</h1>
637 <p class="subtitle">ありがとうございました</p>
638 </div>
639
640
641
642
643
644
645
646
647 <div class="slide">
648 <h1>継続とはなんなのか？</h1>
649 <p class="subtitle">継続</p>
650 <ul>
651 <li>現在の処理を続行するための情報
652 <ul>
653 <li>Cならば続く命令のアドレスや</li>
654 <li>命令に必要な値、</li>
655 <li>スタックなど、その環境全てを含む</li>
656 </ul>
657 </li>
658 </ul>
659 <p class="subtitle">CbCでの軽量継続</p>
660 <ul>
661 <li>継続からスタックに関する情報を落とす</li>
662 <li>続く命令とデータのみのシンプルな継続</li>
663 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
664 </ul>
665 </div>
666
667 <div class="slide" style="font-size:95%;">
668 <h1>コードセグメントと軽量継続の記述</h1>
669 <pre style="float:right; width-max:45%">
670 <code>typedef code (*NEXT)(int);
671 int main(int argc, char **argv) {
672 int i;
673 i = atoi(argv[1]);
674 goto factor(i, print_fact);
675 }
676 <em>code factor(int x, NEXT next)</em> {
677 goto factor0(1, x, next);
678 }
679 code factor0(int prod,int x,NEXT next) {
680 if (x &gt;= 1) {
681 goto factor0(prod*x, x-1, next);
682 } else {
683 <em>goto (*next)(prod);</em>
684 }
685 }
686 code print_fact(int value) {
687 printf("factorial = %d\n", value);
688 exit(0);
689 } </code></pre>
690 <p class="subtitle">実際のプログラム記述は？</p>
691 <ul>
692 <li>コードセグメント定義
693 <ul>
694 <li><code>codeキーワードで宣言</code></li>
695 <li>書式は関数と同じ</li>
696 </ul>
697 </li>
698 <li>軽量継続制御
699 <ul>
700 <li><code>goto</code>キーワードと引数</li>
701 <li>コードセグメントの最初に飛ぶ</li>
702 <li>コードセグメントポインタによる間接継続も可能</li>
703 </ul>
704 </li>
705 </ul>
706 </div>
707
708 <div class="slide">
709 <h1>これまでのCbC</h1>
710 <p class="subtitle"></p>
711 <dl>
712 <dt>2000</dt>
713 <dd>micro-cをベースとしたコンパイラの完成<br/>
714 x86, PowerPC, ARM, MIPS.
715 </dd>
716 <dt>2002</dt>
717 <dd>CbCを用いた分散計算</dd>
718 <dt>2005</dt>
719 <dd>CbCを用いたプログラム分割手法</dd>
720 <dt>2006</dt>
721 <dd>CbCによるSPUマシンのシミュレータ</dd>
722 <dt>2007</dt>
723 <dd>時相論理をベースとしたCbCプログラムの検証</dd>
724 <dt>2008</dt>
725 <dd>GCCをベースとしたコンパイラが開発される</dd>
726 <dt>2010</dt>
727 <dd>GCCベースコンパイラを実用レベルに拡張</dd>
728 </dl>
729 </div>
730
731 <div class="slide">
732 <h1>本研究での取り組み</h1>
733 <p class="subtitle">取り組み</p>
734 <dl>
735 <dt>First</dt>
736 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
737 <ul>
738 <li>軽量継続の実装、これまでの制限の除去</li>
739 <li>x86アーキテクチャにて高速化を行った</li>
740 </ul>
741 </dd>
742 <dt>Second</dt>
743 <dd>C言語との相互利用を可能にした</dd>
744 <dt>Third</dt>
745 <dd>ソースコードメンテナンス性の向上</dd>
746 </dl>
747 </div>
748
749
750
751 <div class="slide">
752 <h1>GNU コンパイラコレクション (GCC)</h1>
753 <div style="width:50%;float:right;">
754 <p class="subtitle">GCCでのコンパイルの流れ</p>
755 <ul style="padding-left:3em">
756 <li>フロントエンド</li>
757 <li>ミドルエンド</li>
758 <li>バックエンド</li>
759 </ul>
760 </div>
761 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
762 </div>
763
764 <div class="slide">
765 <h1>GNU コンパイラコレクション (GCC)</h1>
766 <div style="width:50%;float:right;">
767 <p class="subtitle">GCCでのコンパイルの流れ</p>
768 <ul style="padding-left:3em">
769 <li>フロントエンド</li>
770 <li>ミドルエンド</li>
771 <li>バックエンド</li>
772 </ul>
773 </div>
774 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
775 </div>
776
777
778 <div class="slide">
779 <h1>GCC フロントエンド</h1>
780 <p class="subtitle">GCCにおける構文解析部</p>
781 <ul class="outline">
782 <li>C,Java,Adaなど、言語毎に違う</li>
783 <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li>
784 <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li>
785 <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li>
786 <li>GIMPLEの内部表現例
787 <pre><code>
788 &lt;call_expr 0xb7bc7850
789 type &lt;void_type 0xb7cc9270 void VOID
790 align 8 symtab 0 alias set -1 canonical type 0xb7cc9270
791 pointer_to_this &lt;pointer_type 0xb7cc92d8&gt;&gt;
792 side-effects addressable tree_5
793 fn &lt;var_decl 0xb7d65370 D.2156
794 type &lt;pointer_type 0xb7da74e0 type &lt;function_type 0xb7da7478&gt;
795 unsigned SI
796 size &lt;integer_cst 0xb7cb36ac constant 32&gt;
797 unit size &lt;integer_cst 0xb7cb3498 constant 4&gt;
798 align 32 symtab 0 alias set -1 structural equality&gt;
799 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
800 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
801 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
802 (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32])
803 chain &lt;var_decl 0xb7d653c8 D.2157 type &lt;pointer_type 0xb7cc92d8&gt;
804 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
805 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
806 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
807 (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain &lt;var_decl 0xb7d65420 D.2158&gt;&gt;&gt; arg 0 &lt;var_decl 0xb7d653c8 D.2157&gt;
808 arg 1 &lt;var_decl 0xb7d65420 D.2158
809 type &lt;pointer_type 0xb7da7270 stack type &lt;void_type 0xb7cc9270 void&gt;
810 sizes-gimplified unsigned SI size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
811 align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8
812 pointer_to_this &lt;pointer_type 0xb7bb7000&gt;&gt;
813 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
814 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
815 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
816 (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])&gt;
817 quicksort/quicksort_cbc.cbc:29:7&gt;
818 </code></pre>
819 <p class="subtitle">全ての構文はこのGIMPLEで表される</p>
820 </li>
821 </ul>
822 <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p>
823 </div>
824
825 <div class="slide" style="font-size:95%">
826 <h1>GCC ミドルエンド</h1>
827 <p class="subtitle">GIMPLEからRTLへの変換と最適化</p>
828 <ul class="outline">
829 <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li>
830 <li>登録されたpassを一つ一つ実行する</li>
831 <li>最初にGIMPLEの最適化がたくさんある</li>
832 <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li>
833 <li>最後にRTLの最適化がまた大量にある
834 <pre style="font-size:80%"><code>
835 p = &amp;all_lowering_passes;
836 NEXT_PASS (pass_remove_useless_stmts);
837 NEXT_PASS (pass_mudflap_1);
838 NEXT_PASS (pass_lower_omp);
839 NEXT_PASS (pass_lower_cf);
840 NEXT_PASS (pass_refactor_eh);
841 NEXT_PASS (pass_lower_eh);
842 NEXT_PASS (pass_build_cfg);
843 NEXT_PASS (pass_lower_complex_O0);
844 NEXT_PASS (pass_lower_vector);
845 #ifndef noCbC
846 //NEXT_PASS (pass_warn_function_return);
847 #else
848 NEXT_PASS (pass_warn_function_return);
849 #endif
850 NEXT_PASS (pass_build_cgraph_edges);
851 NEXT_PASS (pass_inline_parameters);
852 *p = NULL;
853
854 /* Interprocedural optimization passes. */
855 p = &amp;all_ipa_passes;
856 NEXT_PASS (pass_ipa_function_and_variable_visibility);
857 NEXT_PASS (pass_ipa_early_inline);
858 {
859 struct opt_pass **p = &amp;pass_ipa_early_inline.pass.sub;
860 NEXT_PASS (pass_early_inline);
861 NEXT_PASS (pass_inline_parameters);
862 NEXT_PASS (pass_rebuild_cgraph_edges);
863 }
864 NEXT_PASS (pass_early_local_passes);
865 {
866 struct opt_pass **p = &amp;pass_early_local_passes.pass.sub;
867 NEXT_PASS (pass_tree_profile);
868 NEXT_PASS (pass_cleanup_cfg);
869 NEXT_PASS (pass_init_datastructures);
870 NEXT_PASS (pass_expand_omp);
871
872 NEXT_PASS (pass_referenced_vars);
873 NEXT_PASS (pass_reset_cc_flags);
874 NEXT_PASS (pass_build_ssa);
875 NEXT_PASS (pass_early_warn_uninitialized);
876 NEXT_PASS (pass_all_early_optimizations);
877 {
878 struct opt_pass **p = &amp;pass_all_early_optimizations.pass.sub;
879 NEXT_PASS (pass_rebuild_cgraph_edges);
880 NEXT_PASS (pass_early_inline);
881 NEXT_PASS (pass_rename_ssa_copies);
882 NEXT_PASS (pass_ccp);
883 NEXT_PASS (pass_forwprop);
884 NEXT_PASS (pass_update_address_taken);
885 NEXT_PASS (pass_sra_early);
886 NEXT_PASS (pass_copy_prop);
887 NEXT_PASS (pass_merge_phi);
888 NEXT_PASS (pass_cd_dce);
889 NEXT_PASS (pass_simple_dse);
890 NEXT_PASS (pass_tail_recursion);
891 NEXT_PASS (pass_convert_switch);
892 NEXT_PASS (pass_profile);
893 }
894 NEXT_PASS (pass_release_ssa_names);
895 NEXT_PASS (pass_rebuild_cgraph_edges);
896 NEXT_PASS (pass_inline_parameters);
897 }
898 NEXT_PASS (pass_ipa_increase_alignment);
899 NEXT_PASS (pass_ipa_matrix_reorg);
900 NEXT_PASS (pass_ipa_cp);
901 NEXT_PASS (pass_ipa_inline);
902 NEXT_PASS (pass_ipa_reference);
903 NEXT_PASS (pass_ipa_pure_const);
904 NEXT_PASS (pass_ipa_type_escape);
905 NEXT_PASS (pass_ipa_pta);
906 NEXT_PASS (pass_ipa_struct_reorg);
907 *p = NULL;
908
909 /* These passes are run after IPA passes on every function that is being
910 output to the assembler file. */
911 p = &amp;all_passes;
912 NEXT_PASS (pass_all_optimizations);
913 {
914 struct opt_pass **p = &amp;pass_all_optimizations.pass.sub;
915 /* Initial scalar cleanups before alias computation.
916 They ensure memory accesses are not indirect wherever possible. */
917 NEXT_PASS (pass_strip_predict_hints);
918 NEXT_PASS (pass_update_address_taken);
919 NEXT_PASS (pass_rename_ssa_copies);
920 NEXT_PASS (pass_complete_unrolli);
921 NEXT_PASS (pass_ccp);
922 NEXT_PASS (pass_forwprop);
923 /* Ideally the function call conditional
924 dead code elimination phase can be delayed
925 till later where potentially more opportunities
926 can be found. Due to lack of good ways to
927 update VDEFs associated with the shrink-wrapped
928 calls, it is better to do the transformation
929 here where memory SSA is not built yet. */
930 NEXT_PASS (pass_call_cdce);
931 /* pass_build_alias is a dummy pass that ensures that we
932 execute TODO_rebuild_alias at this point. Re-building
933 alias information also rewrites no longer addressed
934 locals into SSA form if possible. */
935 NEXT_PASS (pass_build_alias);
936 NEXT_PASS (pass_return_slot);
937 NEXT_PASS (pass_phiprop);
938 NEXT_PASS (pass_fre);
939 NEXT_PASS (pass_copy_prop);
940 NEXT_PASS (pass_merge_phi);
941 NEXT_PASS (pass_vrp);
942 NEXT_PASS (pass_dce);
943 NEXT_PASS (pass_cselim);
944 NEXT_PASS (pass_tree_ifcombine);
945 NEXT_PASS (pass_phiopt);
946 NEXT_PASS (pass_tail_recursion);
947 NEXT_PASS (pass_ch);
948 NEXT_PASS (pass_stdarg);
949 NEXT_PASS (pass_lower_complex);
950 NEXT_PASS (pass_sra);
951 NEXT_PASS (pass_rename_ssa_copies);
952 NEXT_PASS (pass_dominator);
953 /* The only const/copy propagation opportunities left after
954 DOM should be due to degenerate PHI nodes. So rather than
955 run the full propagators, run a specialized pass which
956 only examines PHIs to discover const/copy propagation
957 opportunities. */
958 NEXT_PASS (pass_phi_only_cprop);
959 NEXT_PASS (pass_dse);
960 NEXT_PASS (pass_reassoc);
961 NEXT_PASS (pass_dce);
962 NEXT_PASS (pass_forwprop);
963 NEXT_PASS (pass_phiopt);
964 NEXT_PASS (pass_object_sizes);
965 NEXT_PASS (pass_ccp);
966 NEXT_PASS (pass_copy_prop);
967 NEXT_PASS (pass_fold_builtins);
968 NEXT_PASS (pass_cse_sincos);
969 NEXT_PASS (pass_split_crit_edges);
970 NEXT_PASS (pass_pre);
971 NEXT_PASS (pass_sink_code);
972 NEXT_PASS (pass_tree_loop);
973 {
974 struct opt_pass **p = &amp;pass_tree_loop.pass.sub;
975 NEXT_PASS (pass_tree_loop_init);
976 NEXT_PASS (pass_copy_prop);
977 NEXT_PASS (pass_dce_loop);
978 NEXT_PASS (pass_lim);
979 NEXT_PASS (pass_predcom);
980 NEXT_PASS (pass_tree_unswitch);
981 NEXT_PASS (pass_scev_cprop);
982 NEXT_PASS (pass_empty_loop);
983 NEXT_PASS (pass_record_bounds);
984 NEXT_PASS (pass_check_data_deps);
985 NEXT_PASS (pass_loop_distribution);
986 NEXT_PASS (pass_linear_transform);
987 NEXT_PASS (pass_graphite_transforms);
988 NEXT_PASS (pass_iv_canon);
989 NEXT_PASS (pass_if_conversion);
990 NEXT_PASS (pass_vectorize);
991 {
992 struct opt_pass **p = &amp;pass_vectorize.pass.sub;
993 NEXT_PASS (pass_lower_vector_ssa);
994 NEXT_PASS (pass_dce_loop);
995 }
996 NEXT_PASS (pass_complete_unroll);
997 NEXT_PASS (pass_parallelize_loops);
998 NEXT_PASS (pass_loop_prefetch);
999 NEXT_PASS (pass_iv_optimize);
1000 NEXT_PASS (pass_tree_loop_done);
1001 }
1002 NEXT_PASS (pass_cse_reciprocals);
1003 NEXT_PASS (pass_convert_to_rsqrt);
1004 NEXT_PASS (pass_reassoc);
1005 NEXT_PASS (pass_vrp);
1006 NEXT_PASS (pass_dominator);
1007 /* The only const/copy propagation opportunities left after
1008 DOM should be due to degenerate PHI nodes. So rather than
1009 run the full propagators, run a specialized pass which
1010 only examines PHIs to discover const/copy propagation
1011 opportunities. */
1012 NEXT_PASS (pass_phi_only_cprop);
1013 NEXT_PASS (pass_cd_dce);
1014 NEXT_PASS (pass_tracer);
1015
1016 /* FIXME: If DCE is not run before checking for uninitialized uses,
1017 we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
1018 However, this also causes us to misdiagnose cases that should be
1019 real warnings (e.g., testsuite/gcc.dg/pr18501.c).
1020
1021 To fix the false positives in uninit-5.c, we would have to
1022 account for the predicates protecting the set and the use of each
1023 variable. Using a representation like Gated Single Assignment
1024 may help. */
1025 NEXT_PASS (pass_late_warn_uninitialized);
1026 NEXT_PASS (pass_dse);
1027 NEXT_PASS (pass_forwprop);
1028 NEXT_PASS (pass_phiopt);
1029 NEXT_PASS (pass_tail_calls);
1030 NEXT_PASS (pass_rename_ssa_copies);
1031 NEXT_PASS (pass_uncprop);
1032 }
1033 NEXT_PASS (pass_del_ssa);
1034 NEXT_PASS (pass_nrv);
1035 NEXT_PASS (pass_mark_used_blocks);
1036 NEXT_PASS (pass_cleanup_cfg_post_optimizing);
1037
1038 NEXT_PASS (pass_warn_function_noreturn);
1039 NEXT_PASS (pass_free_datastructures);
1040 NEXT_PASS (pass_mudflap_2);
1041
1042 NEXT_PASS (pass_free_cfg_annotations);
1043 <em>NEXT_PASS (pass_expand);</em>
1044 NEXT_PASS (pass_rest_of_compilation);
1045 {
1046 struct opt_pass **p = &amp;pass_rest_of_compilation.pass.sub;
1047 NEXT_PASS (pass_init_function);
1048 NEXT_PASS (pass_jump);
1049 NEXT_PASS (pass_rtl_eh);
1050 NEXT_PASS (pass_initial_value_sets);
1051 NEXT_PASS (pass_unshare_all_rtl);
1052 NEXT_PASS (pass_instantiate_virtual_regs);
1053 NEXT_PASS (pass_into_cfg_layout_mode);
1054 NEXT_PASS (pass_jump2);
1055 NEXT_PASS (pass_lower_subreg);
1056 NEXT_PASS (pass_df_initialize_opt);
1057 NEXT_PASS (pass_cse);
1058 NEXT_PASS (pass_rtl_fwprop);
1059 NEXT_PASS (pass_gcse);
1060 NEXT_PASS (pass_rtl_ifcvt);
1061 /* Perform loop optimizations. It might be better to do them a bit
1062 sooner, but we want the profile feedback to work more
1063 efficiently. */
1064 NEXT_PASS (pass_loop2);
1065 {
1066 struct opt_pass **p = &amp;pass_loop2.pass.sub;
1067 NEXT_PASS (pass_rtl_loop_init);
1068 NEXT_PASS (pass_rtl_move_loop_invariants);
1069 NEXT_PASS (pass_rtl_unswitch);
1070 NEXT_PASS (pass_rtl_unroll_and_peel_loops);
1071 NEXT_PASS (pass_rtl_doloop);
1072 NEXT_PASS (pass_rtl_loop_done);
1073 *p = NULL;
1074 }
1075 NEXT_PASS (pass_web);
1076 NEXT_PASS (pass_jump_bypass);
1077 NEXT_PASS (pass_cse2);
1078 NEXT_PASS (pass_rtl_dse1);
1079 NEXT_PASS (pass_rtl_fwprop_addr);
1080 NEXT_PASS (pass_reginfo_init);
1081 NEXT_PASS (pass_inc_dec);
1082 NEXT_PASS (pass_initialize_regs);
1083 NEXT_PASS (pass_outof_cfg_layout_mode);
1084 NEXT_PASS (pass_ud_rtl_dce);
1085 NEXT_PASS (pass_combine);
1086 NEXT_PASS (pass_if_after_combine);
1087 NEXT_PASS (pass_partition_blocks);
1088 NEXT_PASS (pass_regmove);
1089 NEXT_PASS (pass_split_all_insns);
1090 NEXT_PASS (pass_lower_subreg2);
1091 NEXT_PASS (pass_df_initialize_no_opt);
1092 NEXT_PASS (pass_stack_ptr_mod);
1093 NEXT_PASS (pass_mode_switching);
1094 NEXT_PASS (pass_see);
1095 NEXT_PASS (pass_match_asm_constraints);
1096 NEXT_PASS (pass_sms);
1097 NEXT_PASS (pass_sched);
1098 NEXT_PASS (pass_subregs_of_mode_init);
1099 NEXT_PASS (pass_ira);
1100 NEXT_PASS (pass_subregs_of_mode_finish);
1101 NEXT_PASS (pass_postreload);
1102 {
1103 struct opt_pass **p = &amp;pass_postreload.pass.sub;
1104 NEXT_PASS (pass_postreload_cse);
1105 NEXT_PASS (pass_gcse2);
1106 NEXT_PASS (pass_split_after_reload);
1107 NEXT_PASS (pass_branch_target_load_optimize1);
1108 NEXT_PASS (pass_thread_prologue_and_epilogue);
1109 NEXT_PASS (pass_rtl_dse2);
1110 NEXT_PASS (pass_rtl_seqabstr);
1111 NEXT_PASS (pass_stack_adjustments);
1112 NEXT_PASS (pass_peephole2);
1113 NEXT_PASS (pass_if_after_reload);
1114 NEXT_PASS (pass_regrename);
1115 NEXT_PASS (pass_cprop_hardreg);
1116 NEXT_PASS (pass_fast_rtl_dce);
1117 NEXT_PASS (pass_reorder_blocks);
1118 NEXT_PASS (pass_branch_target_load_optimize2);
1119 NEXT_PASS (pass_leaf_regs);
1120 NEXT_PASS (pass_split_before_sched2);
1121 NEXT_PASS (pass_sched2);
1122 NEXT_PASS (pass_stack_regs);
1123 {
1124 struct opt_pass **p = &amp;pass_stack_regs.pass.sub;
1125 NEXT_PASS (pass_split_before_regstack);
1126 NEXT_PASS (pass_stack_regs_run);
1127 }
1128 NEXT_PASS (pass_compute_alignments);
1129 NEXT_PASS (pass_duplicate_computed_gotos);
1130 NEXT_PASS (pass_variable_tracking);
1131 NEXT_PASS (pass_free_cfg);
1132 NEXT_PASS (pass_machine_reorg);
1133 NEXT_PASS (pass_cleanup_barriers);
1134 NEXT_PASS (pass_delay_slots);
1135 NEXT_PASS (pass_split_for_shorten_branches);
1136 NEXT_PASS (pass_convert_to_eh_region_ranges);
1137 NEXT_PASS (pass_shorten_branches);
1138 NEXT_PASS (pass_set_nothrow_function_flags);
1139 NEXT_PASS (pass_final);
1140 }
1141 NEXT_PASS (pass_df_finish);
1142 }
1143 NEXT_PASS (pass_clean_state);
1144 *p = NULL;
1145 </code></pre>
1146 </li>
1147 </ul>
1148 <p class="subtitle">RTL</p>
1149 <ul class="outline">
1150 <li>一般的には中間コードとも呼ばれる</li>
1151 <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li>
1152 <li>RTLの例
1153 <pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [
1154 (set (reg/f:SI 7 sp)
1155 (plus:SI (reg/f:SI 7 sp)
1156 (const_int -1024 [0xfffffc00])))
1157 (clobber (reg:CC 17 flags))
1158 ]) -1 (nil))
1159 </code></pre>
1160 </li>
1161 </ul>
1162 </div>
1163
1164 <div class="slide">
1165 <h1>バックエンド</h1>
1166 <p class="subtitle">RTLからアセンブラに変換する処理</p>
1167 <ul class="outline">
1168 <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li>
1169 <li>アーキテクチャ毎にこのmdが必要になる</li>
1170 <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li>
1171 <li>mdの例
1172 <pre><code>
1173 (define_insn "cmpdi_ccno_1_rex64"
1174 [(set (reg FLAGS_REG)
1175 (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr")
1176 (match_operand:DI 1 "const0_operand" "")))]
1177 "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCNOmode)"
1178 "@
1179 test{q}\t%0, %0
1180 cmp{q}\t{%1, %0|%0, %1}"
1181 [(set_attr "type" "test,icmp")
1182 (set_attr "length_immediate" "0,1")
1183 (set_attr "mode" "DI")])
1184
1185 (define_insn "*cmpdi_minus_1_rex64"
1186 [(set (reg FLAGS_REG)
1187 (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r")
1188 (match_operand:DI 1 "x86_64_general_operand" "re,mr"))
1189 (const_int 0)))]
1190 "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCGOCmode)"
1191 "cmp{q}\t{%1, %0|%0, %1}"
1192 [(set_attr "type" "icmp")
1193 (set_attr "mode" "DI")])
1194 </code></pre></li>
1195 </ul>
1196 </div>
1197
1198 <div class="slide">
1199 <h1>本研究での取り組み</h1>
1200 <p class="subtitle">取り組み</p>
1201 <dl>
1202 <dt>First</dt>
1203 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
1204 <ul>
1205 <li>軽量継続の実装、これまでの制限の除去</li>
1206 <li>x86アーキテクチャにて高速化を行った</li>
1207 </ul>
1208 </dd>
1209 <dt>Second</dt>
1210 <dd>C言語との互換性の向上</dd>
1211 <dt>Third</dt>
1212 <dd>ソースコードメンテナンス性の向上</dd>
1213 </dl>
1214 </div>
1215
1216
1217
1218 <div class="slide">
1219 <h1>First: 軽量継続の実装</h1>
1220 <p class="subtitle">軽量継続を実装するには？</p>
1221 <ul>
1222 <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
1223 <li>GCCでは<em class="weak">あくまで関数</em>がベース</li>
1224 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
1225 <li>関数コール(call命令)ではもちろんダメ</li>
1226 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
1227 <li>スタックを拡張するのもダメ</li>
1228 </ul>
1229 <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
1230 </div>
1231
1232 <div class="slide">
1233 <h1>First: 軽量継続の実装</h1>
1234 <p class="subtitle">末尾呼出ってなに？</p>
1235 <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
1236 <ul>
1237 <li>リターンの直前の関数呼び出しのこと</li>
1238 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
1239 <li>元の関数に戻らないため少し高速に</li>
1240 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
1241 </ul>
1242 </div>
1243
1244 <div class="slide">
1245 <h1>First: 軽量継続の実装</h1>
1246 <p class="subtitle">末尾呼出ってなに？</p>
1247 <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
1248 <ul>
1249 <li>リターンの直前の関数呼び出しのこと</li>
1250 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
1251 <li>元の関数に戻らないため少し高速に</li>
1252 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
1253 </ul>
1254 <p class="subtitle incremental">軽量継続ではこの末尾呼出(TCE)を強制する！</p>
1255 </div>
1256
1257 <div class="slide">
1258 <h1>First: 軽量継続の実装</h1>
1259 <p class="subtitle">末尾呼出による軽量継続の実装</p>
1260 <ul>
1261 <li>全ての軽量継続は末尾呼出と解釈する</li>
1262 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
1263 <li><code>goto cs(20, 30);</code></li>
1264 <li><code>cs(20, 30); return;</code></li>
1265 </ul>
1266 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
1267 <ol>
1268 <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li>
1269 <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li>
1270 </ol>
1271 </div>
1272 <div class="slide">
1273 <h1>First: 軽量継続の実装</h1>
1274 <p class="subtitle">末尾呼出による軽量継続の実装</p>
1275 <ul>
1276 <li>全ての軽量継続は末尾呼出と解釈する</li>
1277 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
1278 <li><code>goto cs(20, 30);</code></li>
1279 <li><code>cs(20, 30); return;</code></li>
1280 </ul>
1281 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
1282 <ol>
1283 <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
1284 <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
1285 </ol>
1286 </div>
1287
1288
1289 <div class="slide">
1290 <h1>First: 軽量継続の実装</h1>
1291 <p class="subtitle">引数順序の問題の解決</p>
1292 <ul>
1293 <li>問題となる例
1294 <pre><code>code somesegment(int a, int b, int c) {
1295 /∗ do something ∗/
1296 goto nextsegment(b, c, a);
1297 }
1298 </code></pre>
1299 </li>
1300 <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
1301 <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
1302 <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
1303 </ul>
1304
1305 </div>
1306
1307 <div class="slide">
1308 <h1>First: 軽量継続の実装</h1>
1309 <p class="subtitle">全ての引数を一時変数に退避</p>
1310 <ul>
1311 <li>次の様に構文木を変更する
1312 <pre><code>code somesegment(int a, int b, int c) {
1313 int a1, b1, c1;
1314 /∗ do something ∗/
1315 a1=a; b1=b; c1=c;
1316 goto nextsegment(b1, c1, a1);
1317 }
1318 </code></pre>
1319 </li>
1320 <li>これにより、引数順序を考える必要はなくなる</li>
1321 <li>代わりに、メモリアクセスが大量に発生</li>
1322 <li>しかし、これはGCCの最適化で除去される</li>
1323 </ul>
1324
1325 <p class="subtitle">これで軽量継続が実装された</p>
1326 </div>
1327
1328
1329 <div class="slide">
1330 <h1>First: x86における高速化</h1>
1331 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
1332 <ul>
1333 <li>特にx86アーキテクチャ</li>
1334 <li><em class="weak">あくまで関数がベース</em>なので</li>
1335 <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
1336 <li>これをレジスタにすれば高速化が可能</li>
1337 </ul>
1338 <p class="subtitle">fastcallの導入</p>
1339 <ul>
1340 <li>GCCの独自拡張機能</li>
1341 <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
1342 </ul>
1343 </div>
1344
1345 <div class="slide">
1346 <h1>First: x86における高速化</h1>
1347 <p class="subtitle">fastcallの強制</p>
1348 <ul>
1349 <li>通常は以下の様に定義される
1350 <pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
1351 </code></pre></li>
1352 <li>しかしこれを毎回ユーザが書くのは変</li>
1353 <li>やはりフロントエンドにて、強制するべき</li>
1354 <li>型の構文木を生成した際にfastcall属性を付加</li>
1355 </ul>
1356 <p class="subtitle">実際の出力はどうなる？</p>
1357 <div style="width:70%;margin:1em auto 0;">
1358 <pre><code>__code current(int a, int b, int c) {
1359 goto next(10, 20, 30);
1360 }
1361 </code></pre>
1362 </div>
1363 </div>
1364
1365 <div class="slide" style="font-size:95%;">
1366 <h1>First: x86における高速化</h1>
1367 <p class="subtitle">実際の出力アセンブラ</p>
1368 <div style="width:50%;float:left;margin-left:auto;">
1369 <p style="margin:0;text-align:center">fastcallにした場合</p>
1370 <pre><code>current:
1371 subl $12, %esp
1372 movl $30, 16(%esp)
1373 movl $20, %edx
1374 movl $10, %ecx
1375 addl $12, %esp
1376 jmp next
1377 </code></pre>
1378 </div>
1379 <div style="width:50%;float:right;margin-right:auto;">
1380 <p style="margin:0;text-align:center">normalcallの場合</p>
1381 <pre><code>current:
1382 pushl %ebp
1383 movl %esp, %ebp
1384 movl $30, 16(%ebp)
1385 movl $20, 12(%ebp)
1386 movl $10, 8(%ebp)
1387 leave
1388 jmp next
1389 </code></pre>
1390 </div>
1391 <br clear="all" />
1392 <ul>
1393 <li>命令数ではほとんど変化はない</li>
1394 <li>引数2つがレジスタecxとedxに格納されるようになった</li>
1395 <li>そのためメモリアクセスが減る</li>
1396 <li>これで高速化されるはず</li>
1397 </ul>
1398 </div>
1399
1400
1401 <div class="slide">
1402 <h1>First: CbCコンパイラ実装の評価</h1>
1403 <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
1404 <ul>
1405 <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
1406 <li>コンパイラの出力した実行ファイルを比較</li>
1407 <li>CbCでのquicksort例題を用意</li>
1408 <li>実行速度、ファイルサイズ</li>
1409 <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
1410 </ul>
1411 <p class="subtitle">実行環境</p>
1412 <ul>
1413 <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
1414 <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
1415 <li>OSはLinuxとOS Xを使用する</li>
1416 </ul>
1417 </div>
1418
1419 <div class="slide">
1420 <h1>First: 性能評価（速度比較） vs.旧ver</h1>
1421 <p class="subtitle">速度測定結果(単位:秒)</p>
1422 <table>
1423 <tr>
1424 <th></th>
1425 <th colspan="2">新CbCGCC</th>
1426 <th colspan="2">旧CbCGCC</th>
1427 </tr>
1428 <tr>
1429 <td></td>
1430 <th>最適化無し</th>
1431 <th>最適化有り</th>
1432 <th>最適化無し</th>
1433 <th>最適化有り</th>
1434 </tr>
1435 <tr>
1436 <td>x86/OS X</td>
1437 <td>5.907</td>
1438 <td>2.434</td>
1439 <td>4.668</td>
1440 <td>3.048</td>
1441 </tr>
1442 <tr>
1443 <td>x86/Linux</td>
1444 <td>5.715</td>
1445 <td>2.401</td>
1446 <td>4.525</td>
1447 <td>2.851</td>
1448 </tr>
1449 </table>
1450 <p class="subtitle">評価</p>
1451 <ul>
1452 <li>最適化無の場合は遅くなった </li>
1453 <li>一時変数への確保があるのでこれは予想通り</li>
1454 <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
1455 <li>fastcallの効果が十分に出ている</li>
1456 </ul>
1457 </div>
1458
1459
1460 <div class="slide">
1461 <h1>First: 性能評価（速度比較）</h1>
1462 <p class="subtitle">速度測定結果(単位:秒)</p>
1463 <table>
1464 <tr>
1465 <td></td>
1466 <td>最適化なしのGCC</td>
1467 <td>最適化付きのGCC</td>
1468 <td>micro-c</td>
1469 </tr>
1470 <tr>
1471 <td>x86/OS X</td>
1472 <td>5.901</td>
1473 <td>2.434</td>
1474 <td>2.857</td>
1475 </tr>
1476 <tr>
1477 <td>x86/Linux</td>
1478 <td>5.732</td>
1479 <td>2.401</td>
1480 <td>2.254</td>
1481 </tr>
1482 <tr>
1483 <td>ppc/OS X</td>
1484 <td>14.875</td>
1485 <td>2.146</td>
1486 <td>4.811</td>
1487 </tr>
1488 <tr>
1489 <td>ppc/Linux</td>
1490 <td>19.793</td>
1491 <td>3.955</td>
1492 <td>6.454</td>
1493 </tr>
1494 <tr>
1495 <td>ppc/PS3</td>
1496 <td>39.176</td>
1497 <td>5.874</td>
1498 <td>11.121</td>
1499 </tr>
1500 </table>
1501 <p class="subtitle">結果(micro-cとの比較)</p>
1502 <ul>
1503 <li>x86では速度にあまり差が出なかった</li>
1504 <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
1505 <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
1506 </ul>
1507 </div>
1508
1509 <div class="slide">
1510 <h1>First: 性能評価（速度比較）</h1>
1511 <p class="subtitle">結果(micro-cとの比較)</p>
1512 <ul>
1513 <li>x86では速度にあまり差が出なかった</li>
1514 <li>PowerPCではCbCGCCが2倍ほど早い</li>
1515 </ul>
1516 <p class="subtitle">この違いはどこから？</p>
1517 <ul style="font-size:95%;">
1518 <li>実際にアセンブラを出力して比較、その結果</li>
1519 <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
1520 <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
1521 <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
1522 <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
1523 </ul>
1524 </div>
1525
1526 <div class="slide">
1527 <h1>First: 性能評価（サイズ比較）</h1>
1528 <p class="subtitle">ファイルサイズの比較</p>
1529 <ul>
1530 <li>組み込み系ではメモリ使用量が肝心</li>
1531 <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
1532 <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
1533 </ul>
1534 <p class="subtitle">結果</p>
1535 <table>
1536 <tr>
1537 <td></td>
1538 <th>CbCGCC<br/>速度最適化</th>
1539 <th>CbCGCC<br/>サイズ最適化</th>
1540 <th>micro-c</th>
1541 </tr>
1542 <tr>
1543 <td>x86/OS X</td>
1544 <td>9176</td>
1545 <td>9176</td>
1546 <td>9172</td>
1547 </tr>
1548 <tr>
1549 <td>x86/Linux</td>
1550 <td>5752</td>
1551 <td>5752</td>
1552 <td>5796</td>
1553 </tr>
1554 <tr>
1555 <td>ppc/OS X</td>
1556 <td>8576</td>
1557 <td>8576</td>
1558 <td>12664</td>
1559 </tr>
1560 <tr>
1561 <td>ppc/Linux</td>
1562 <td>10068</td>
1563 <td>10068</td>
1564 <td>9876</td>
1565 </tr>
1566 <tr>
1567 <td>ppc/PS3</td>
1568 <td>6960</td>
1569 <td>6728</td>
1570 <td>8636</td>
1571 </tr>
1572 </table>
1573 <p class="subtitle">結果考察</p>
1574 <ul>
1575 <li>x86ではファイルサイズの差がない</li>
1576 <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
1577 <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
1578 </ul>
1579 </div>
1580
1581
1582 <div class="slide">
1583 <h1>Second: Cとの相互利用</h1>
1584 <p class="subtitle">なぜそれが必要か</p>
1585 <ul>
1586 <li>C &lt;=&gt; CbC の変換が可能なので互換性はある</li>
1587 <li>しかし、ソースコード上での互換性もある事が望ましい</li>
1588 <li>CbCからCの関数を呼び出すのは問題ない</li>
1589 <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
1590 </ul>
1591 <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
1592 <ul>
1593 <li>軽量継続に、スタックの情報を加える</li>
1594 <li>つまり通常の「継続」と同じ</li>
1595 <li>関数からのみ使用可能</li>
1596 </ul>
1597 </div>
1598
1599 <div class="slide" style="font-size:95%;">
1600 <h1>Second: Cとの相互利用</h1>
1601 <pre style="float:right; width-max:45%">
1602 <code>typedef code (*NEXT)(int);
1603 int main(int argc, char **argv) {
1604 int i,a;
1605 i = atoi(argv[1]);
1606 <em>a = factor(i);</em>
1607 printf("%d! = %d\n", a);
1608 }
1609 int factor(int x) {
1610 NEXT ret = <em>__return</em>;
1611 goto factor0(1, x, ret);
1612 }
1613 code
1614 factor0(int prod,int x,NEXT next) {
1615 if (x &gt;= 1) {
1616 goto factor0(prod*x, x-1, next);
1617 } else {
1618 <em>goto (*next)(prod);</em>
1619 }
1620 }
1621 </code></pre>
1622 <p class="subtitle">環境付き継続の使用例</p>
1623 <ul>
1624 <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li>
1625 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
1626 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
1627 </ul>
1628 </div>
1629
1630 <div class="slide">
1631 <h1>Second: Cとの相互利用</h1>
1632 <p class="subtitle">どのように実装する？</p>
1633 <ol>
1634 <li>setjmp()/longjmp()を使って実装可能
1635 <ul>
1636 <li>Cの標準ライブラリの関数</li>
1637 <li>しかし余計な環境も保持するためオーバヘッドが大きい</li>
1638 <li>継続の際に渡す引数が一つ増えてしまう</li>
1639 </ul></li>
1640 <li>内部関数
1641 <ul>
1642 <li>GCCの独自拡張</li>
1643 <li>関数内に関数を定義可能</li>
1644 <li><em>内部関数から外の関数のラベルにgotoできる</em></li>
1645 </ul></li>
1646 </ol>
1647 <p class="subtitle">内部関数が使いやすい</p>
1648 </div>
1649
1650 <div class="slide" style="font-size:95%;">
1651 <h1>Second: Cとの相互利用</h1>
1652 <p class="subtitle">具体的には</p>
1653 <ul>
1654 <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
1655 <li>内部関数の中からは外の関数にgotoして脱出</li>
1656 </ul>
1657 <pre><code>int factor(int x) {
1658 int retval;
1659
1660 <em class="weak">code __return(int val) {
1661 retval = val;
1662 goto label;
1663 }
1664 if (0) {
1665 label:
1666 return retval;
1667 }</em>
1668
1669 NEXT ret = <em>__return</em>;
1670 goto factor0(1, x, ret);
1671 } </code></pre>
1672 </div>
1673
1674 <div class="slide" style="font-size:95%;">
1675 <h1>Second: Cとの相互利用・評価</h1>
1676 <p class="subtitle">この取り組みにより</p>
1677 <ul>
1678 <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li>
1679 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
1680 </ul>
1681 </div>
1682
1683 <div class="slide">
1684 <h1>Third: メンテナンス性の向上</h1>
1685 <p class="subtitle">GCCのアップデートリリースは早い</p>
1686 <ul>
1687 <li>リリースだけで年に5回のペース</li>
1688 <li>その度にバグの修正やコードの改善が入る</li>
1689 <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li>
1690 </ul>
1691 <p class="subtitle">このリリースに追従して差分をアップデートしたい</p>
1692 <ul>
1693 <li>GCC本家にマージしてもらうのが一番良いが難しい</li>
1694 <li></li>
1695 </ul>
1696 </div>
1697
1698 <div class="slide">
1699 <h1>Third: メンテナンス性の向上</h1>
1700 <img style="width:60%;float:right;" src="figures/gcc-repository.png" />
1701 <p class="subtitle">二つのリポジトリ管理</p>
1702 <ul>
1703 <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li>
1704 <li>CbCの修正が加えられたリポジトリ CbCGCC</li>
1705 <li>Mercurialによる分散リポジトリ管理</li>
1706 <li>CbCGCC は GCC_copyをクローン（ブランチ）して作成する</li>
1707 </ul>
1708 <p class="subtitle"></p>
1709 </div>
1710
1711
1712 <div class="slide">
1713 <h1>Third: メンテナンス性の向上</h1>
1714 <p class="subtitle">アップデート手順</p>
1715 <ul>
1716 <li>GCC-copyリポジトリにて
1717 <ol>
1718 <li>GCC-copyリポジトリのファイルをすべて消す</li>
1719 <li>GCCの最新バージョンをリポジトリ内に展開</li>
1720 <li>追加ファイル、削除ファイルを確認</li>
1721 <li>コミット、タグ付け</li>
1722 </ol> </li>
1723 <li>CbCGCCリポジトリにて
1724 <ol>
1725 <li>GCC-copyからpull.</li>
1726 <li>hg mergeでマージ実行</li>
1727 <li>衝突があればソースコードをを修正</li>
1728 <li>ビルドテスト</li>
1729 <li>コミット、タグ付け</li>
1730 </ol></li>
1731 </ul>
1732 </div>
1733
1734 <div class="slide">
1735 <h1>Third: メンテナンス性の向上・比較</h1>
1736 <p class="subtitle">これまでのアップデートは</p>
1737 <ul>
1738 <li>GCCの新旧の差分、CbCの差分</li>
1739 <li>複雑なdiffをとる必要がある</li>
1740 </ul>
1741 <p class="subtitle">新しい管理方法により</p>
1742 <ul>
1743 <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li>
1744 <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li>
1745 <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li>
1746 </ul>
1747 </div>
1748
1749 <div class="slide">
1750 <h1>まとめ</h1>
1751 <p class="subtitle">本研究での取り組み</p>
1752 <dl>
1753 <dt>First</dt>
1754 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
1755 <ul>
1756 <li>軽量継続における引数順序の制限を取り除いた</li>
1757 <li>PowerPCでの間接継続の制限を取り除いた</li>
1758 <li>x86アーキテクチャにて高速化を行った</li>
1759 </ul>
1760 </dd>
1761 <dt>Second</dt>
1762 <dd>Cとの相互利用性の向上</dd>
1763 <dt>Third</dt>
1764 <dd>ソースコードメンテナンス性の向上</dd>
1765 </dl>
1766 </div>
1767
1768 <div class="slide" style="font-size:95%;">
1769 <h1>まとめ</h1>
1770 <p class="subtitle">本研究での成果</p>
1771 <dl>
1772 <dt>成果1</dt>
1773 <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
1774 <dt>成果2</dt>
1775 <dd>CbCが多数のアーキテクチャに対応
1776 <ul>
1777 <li>20以上のアーキテクチャ</li>
1778 <li>特に64bitのx86, SPUがうれしい</li>
1779 </ul> </dd>
1780 <dt>成果3</dt>
1781 <dd>CbCの高速化
1782 <ul>
1783 <li>x86においてもmicro-cと互角の速度を達成</li>
1784 <li>PowerPCでは2倍の速度</li>
1785 </ul></dd>
1786 <dt>成果4</dt>
1787 <dd>メンテナンス性が向上</dd>
1788 </dl>
1789 </div>
1790
1791 <div class="slide">
1792 <h1>今後の課題</h1>
1793 <p class="subtitle"></p>
1794 <ul>
1795 <li>Real-time、組込み向けに実用的なCbCプログラムの例題</li>
598 <li>タブロー方を用いた検証</li> 1796 <li>タブロー方を用いた検証</li>
599 <li>TaskManagerのCbC実装</li> 1797 <li>TaskManagerのCbC実装</li>
600 </ul> 1798 </ul>
601 <p class="subtitle">CbC言語の今後</p> 1799 <p class="subtitle">CbC言語の今後</p>
602 <ul> 1800 <ul>
731 <li>実際はr0を使って4命令で入れ替えられる!</li> 1929 <li>実際はr0を使って4命令で入れ替えられる!</li>
732 </ul> 1930 </ul>
733 </div> 1931 </div>
734 </div> 1932 </div>
735 1933
736
737 <div class="slide">
738 <h1>継続とはなんなのか？</h1>
739 <p class="subtitle">継続</p>
740 <ul>
741 <li>現在の処理を続行するための情報
742 <ul>
743 <li>Cならば続く命令のアドレスや</li>
744 <li>命令に必要な値、</li>
745 <li>スタックなど、その環境全てを含む</li>
746 </ul>
747 </li>
748 </ul>
749 <p class="subtitle">CbCでの軽量継続</p>
750 <ul>
751 <li>継続からスタックに関する情報を落とす</li>
752 <li>続く命令とデータのみのシンプルな継続</li>
753 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
754 </ul>
755 </div>
756
757 <div class="slide" style="font-size:95%;">
758 <h1>コードセグメントと軽量継続の記述</h1>
759 <pre style="float:right; width-max:45%">
760 <code>typedef code (*NEXT)(int);
761 int main(int argc, char **argv) {
762 int i;
763 i = atoi(argv[1]);
764 goto factor(i, print_fact);
765 }
766 <em>code factor(int x, NEXT next)</em> {
767 goto factor0(1, x, next);
768 }
769 code factor0(int prod,int x,NEXT next) {
770 if (x &gt;= 1) {
771 goto factor0(prod*x, x-1, next);
772 } else {
773 <em>goto (*next)(prod);</em>
774 }
775 }
776 code print_fact(int value) {
777 printf("factorial = %d\n", value);
778 exit(0);
779 } </code></pre>
780 <p class="subtitle">実際のプログラム記述は？</p>
781 <ul>
782 <li>コードセグメント定義
783 <ul>
784 <li><code>codeキーワードで宣言</code></li>
785 <li>書式は関数と同じ</li>
786 </ul>
787 </li>
788 <li>軽量継続制御
789 <ul>
790 <li><code>goto</code>キーワードと引数</li>
791 <li>コードセグメントの最初に飛ぶ</li>
792 <li>コードセグメントポインタによる間接継続も可能</li>
793 </ul>
794 </li>
795 </ul>
796 </div>
797
798 <div class="slide"> 1934 <div class="slide">
799 <h1>Cとの比較について</h1> 1935 <h1>Cとの比較について</h1>
800 <p class="subtitle">quicksort例題をCと比較すると</p> 1936 <p class="subtitle">CbCとCの比較に関して</p>
801 <ul> 1937 <ul>
802 <li>現在のところ、遅くなる</li> 1938 <li>まだ例題を用意していない</li>
803 <li>問題はquicksortという例題では必ずスタックが必要だということ</li> 1939 <li>quicksortはスタックが必要となるため、Cに有利</li>
804 <li>例題ではスタックを自前の構造体で用意している</li> 1940 <li>この例題ではプログラム上自前でスタックを用意している</li>
805 <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li> 1941 <li>このメモリへのアクセスはスタックより重い</li>
806 <li>状態遷移ベースの例題を作りたい</li> 1942 <li>Cとの比較には状態遷移ベースの例題があった方が良い</li>
807 </ul> 1943 </ul>
808 </div> 1944 </div>
809 1945
810 1946
811 <div class="slide" style="font-size:95%;"> 1947
812 <h1>fastcall</h1> 1948
813 <p class="subtitle">実際の出力アセンブラ</p> 1949
814 <div style="width:50%;float:left;margin-left:auto;"> 1950
815 <p style="margin:0;text-align:center">fastcallにした場合</p> 1951
816 <pre><code>current: 1952
817 subl $12, %esp 1953
818 movl $30, 16(%esp) 1954
819 movl $20, %edx
820 movl $10, %ecx
821 addl $12, %esp
822 jmp next
823 </code></pre>
824 </div>
825 <div style="width:50%;float:right;margin-right:auto;">
826 <p style="margin:0;text-align:center">normalcallの場合</p>
827 <pre><code>current:
828 pushl %ebp
829 movl %esp, %ebp
830 movl $30, 16(%ebp)
831 movl $20, 12(%ebp)
832 movl $10, 8(%ebp)
833 leave
834 jmp next
835 </code></pre>
836 </div>
837 <br clear="all" />
838 <ul>
839 <li>命令数ではほとんど変化はない</li>
840 <li>引数2つがレジスタecxとedxに格納されるようになった</li>
841 <li>そのためメモリアクセスが減る</li>
842 <li>これで高速化されるはず</li>
843 </ul>
844 </div>
845
846 <div class="slide">
847 <h1>First: 性能評価（サイズ比較）</h1>
848 <p class="subtitle">ファイルサイズの比較</p>
849 <ul>
850 <li>組み込み系ではメモリ使用量が肝心</li>
851 <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
852 <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
853 </ul>
854 <p class="subtitle">結果</p>
855 <table>
856 <tr>
857 <td></td>
858 <th>CbCGCC<br/>速度最適化</th>
859 <th>CbCGCC<br/>サイズ最適化</th>
860 <th>micro-c</th>
861 </tr>
862 <tr>
863 <td>x86/OS X</td>
864 <td>9176</td>
865 <td>9176</td>
866 <td>9172</td>
867 </tr>
868 <tr>
869 <td>x86/Linux</td>
870 <td>5752</td>
871 <td>5752</td>
872 <td>5796</td>
873 </tr>
874 <tr>
875 <td>ppc/OS X</td>
876 <td>8576</td>
877 <td>8576</td>
878 <td>12664</td>
879 </tr>
880 <tr>
881 <td>ppc/Linux</td>
882 <td>10068</td>
883 <td>10068</td>
884 <td>9876</td>
885 </tr>
886 <tr>
887 <td>ppc/PS3</td>
888 <td>6960</td>
889 <td>6728</td>
890 <td>8636</td>
891 </tr>
892 </table>
893 <p class="subtitle">結果考察</p>
894 <ul>
895 <li>x86ではファイルサイズの差がない</li>
896 <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
897 <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
898 </ul>
899 </div>
900
901 <div class="slide">
902 <h1>並列代入</h1>
903 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
904 <ol>
905 <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
906 <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
907 </ol>
908 <p class="subtitle">問題となる例</p>
909 <pre><code>code somesegment(int a, int b, int c) {
910 /∗ do something ∗/
911 goto nextsegment(b, c, a);
912 }
913 </code></pre>
914 <ul>
915 <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
916 <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
917 <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
918 </ul>
919 <p class="subtitle">次の様に構文木を変更する</p>
920 <pre><code>code somesegment(int a, int b, int c) {
921 int a1, b1, c1;
922 /∗ do something ∗/
923 a1=a; b1=b; c1=c;
924 goto nextsegment(b1, c1, a1);
925 }
926 </code></pre>
927 <ul>
928 <li>これにより、引数順序を考える必要はなくなる</li>
929 <li>代わりに、メモリアクセスが大量に発生</li>
930 <li>しかし、これはGCCの最適化で除去される</li>
931 </ul>
932 </div>
933 1955
934 1956
935 1957
936 </body> 1958 </body>
937 </html> 1959 </html>