Mercurial > hg > Papers > 2010 > kent-master
diff recital-slide/slide.html @ 16:d9b85f041908
up recital
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 17 Feb 2010 14:00:55 +0900 |
parents | 67544736317e |
children | 7c25b2856f27 |
line wrap: on
line diff
--- a/recital-slide/slide.html Tue Feb 16 17:25:21 2010 +0900 +++ b/recital-slide/slide.html Wed Feb 17 14:00:55 2010 +0900 @@ -169,6 +169,26 @@ <p class="subtitle"></p> </div> +<div class="slide"> + <h1>継続とはなんなのか?</h1> + <p class="subtitle">継続</p> + <ul> + <li>現在の処理を続行するための情報 + <ul> + <li>Cならば続く命令のアドレスや</li> + <li>命令に必要な値、</li> + <li>スタックなど、その環境全てを含む</li> + </ul> + </li> + </ul> + <p class="subtitle">CbCでの軽量継続</p> + <ul> + <li>継続からスタックに関する情報を落とす</li> + <li>続く命令とデータのみのシンプルな継続</li> + <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li> + </ul> +</div> + <div class="slide" style="font-size:95%;"> <h1>コードセグメントと軽量継続の記述</h1> <pre style="float:right; width-max:45%"> @@ -285,14 +305,14 @@ <h1>First: 軽量継続の実装</h1> <p class="subtitle">軽量継続を実装するには?</p> <ul> - <li>河野先生の作ったmicro-cは元より軽量継続を考慮して良く設計されている</li> + <li>micro-cは元より軽量継続を考慮して良く設計されている</li> <li>micro-Cと同じ命令列を出力させるのは難しい</li> <li>関数コール(call命令)ではもちろんダメ</li> <li>必ず<em>jmp命令</em>を出力しないといけない</li> <li>スタックを拡張してはいけない</li> - <li>しかしGCCでは<em>関数をベース</em>にしなければならない</li> + <li>加えて、GCCでは<em>関数をベース</em>にしなければならない</li> </ul> - <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p> + <p class="subtitle">そこで、<dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p> </div> <div class="slide"> @@ -321,6 +341,11 @@ </div> <div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">プログラム実行時のスタックの変化</p> +</div> + +<div class="slide"> <h1>First: x86における高速化</h1> <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p> <ul> @@ -508,7 +533,7 @@ </code></pre> <p class="subtitle">環境付き継続の使用例</p> <ul> - <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li> + <li><code><em>__return</em></code>で表される特殊なコードセグメント</li> <li>コードセグメントからは通常のコードセグメントポインタに見える</li> <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li> </ul> @@ -543,7 +568,7 @@ <h1>Second: Cとの相互利用・評価</h1> <p class="subtitle">この取り組みにより</p> <ul> - <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li> + <li>これにより、<dfn>Continuation based C</dfn> の全仕様を満たした</li> <li>ソースコードレベルで、Cと相互に利用することが可能になった</li> </ul> </div> @@ -557,7 +582,7 @@ <dt>First</dt> <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった <ul> - <li><em>軽量継続における引数順序の制限を取り除いた</em></li> + <li>軽量継続における引数順序の制限を取り除いた</li> <li>PowerPCでの間接継続の制限を取り除いた</li> <li><em>x86アーキテクチャにて高速化を行った</em></li> </ul> @@ -619,6 +644,1179 @@ +<div class="slide"> + <h1>継続とはなんなのか?</h1> + <p class="subtitle">継続</p> + <ul> + <li>現在の処理を続行するための情報 + <ul> + <li>Cならば続く命令のアドレスや</li> + <li>命令に必要な値、</li> + <li>スタックなど、その環境全てを含む</li> + </ul> + </li> + </ul> + <p class="subtitle">CbCでの軽量継続</p> + <ul> + <li>継続からスタックに関する情報を落とす</li> + <li>続く命令とデータのみのシンプルな継続</li> + <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li> + </ul> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>コードセグメントと軽量継続の記述</h1> + <pre style="float:right; width-max:45%"> +<code>typedef code (*NEXT)(int); +int main(int argc, char **argv) { + int i; + i = atoi(argv[1]); + goto factor(i, print_fact); +} +<em>code factor(int x, NEXT next)</em> { + goto factor0(1, x, next); +} +code factor0(int prod,int x,NEXT next) { + if (x >= 1) { + goto factor0(prod*x, x-1, next); + } else { + <em>goto (*next)(prod);</em> + } +} +code print_fact(int value) { + printf("factorial = %d\n", value); + exit(0); +} </code></pre> + <p class="subtitle">実際のプログラム記述は?</p> + <ul> + <li>コードセグメント定義 + <ul> + <li><code>codeキーワードで宣言</code></li> + <li>書式は関数と同じ</li> + </ul> + </li> + <li>軽量継続制御 + <ul> + <li><code>goto</code>キーワードと引数</li> + <li>コードセグメントの最初に飛ぶ</li> + <li>コードセグメントポインタによる間接継続も可能</li> + </ul> + </li> + </ul> +</div> + +<div class="slide"> + <h1>これまでのCbC</h1> + <p class="subtitle"></p> + <dl> + <dt>2000</dt> + <dd>micro-cをベースとしたコンパイラの完成<br/> + x86, PowerPC, ARM, MIPS. + </dd> + <dt>2002</dt> + <dd>CbCを用いた分散計算</dd> + <dt>2005</dt> + <dd>CbCを用いたプログラム分割手法</dd> + <dt>2006</dt> + <dd>CbCによるSPUマシンのシミュレータ</dd> + <dt>2007</dt> + <dd>時相論理をベースとしたCbCプログラムの検証</dd> + <dt>2008</dt> + <dd>GCCをベースとしたコンパイラが開発される</dd> + <dt>2010</dt> + <dd>GCCベースコンパイラを実用レベルに拡張</dd> + </dl> +</div> + +<div class="slide"> + <h1>本研究での取り組み</h1> + <p class="subtitle">取り組み</p> + <dl> + <dt>First</dt> + <dd>GCCにて実用レベルのCbCプログラムを動作可能にする + <ul> + <li>軽量継続の実装、これまでの制限の除去</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>C言語との相互利用を可能にした</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + + + +<div class="slide"> + <h1>GNU コンパイラコレクション (GCC)</h1> + <div style="width:50%;float:right;"> + <p class="subtitle">GCCでのコンパイルの流れ</p> + <ul style="padding-left:3em"> + <li>フロントエンド</li> + <li>ミドルエンド</li> + <li>バックエンド</li> + </ul> + </div> + <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" /> +</div> + +<div class="slide"> + <h1>GNU コンパイラコレクション (GCC)</h1> + <div style="width:50%;float:right;"> + <p class="subtitle">GCCでのコンパイルの流れ</p> + <ul style="padding-left:3em"> + <li>フロントエンド</li> + <li>ミドルエンド</li> + <li>バックエンド</li> + </ul> + </div> + <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" /> +</div> + + +<div class="slide"> + <h1>GCC フロントエンド</h1> + <p class="subtitle">GCCにおける構文解析部</p> + <ul class="outline"> + <li>C,Java,Adaなど、言語毎に違う</li> + <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li> + <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li> + <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li> + <li>GIMPLEの内部表現例 + <pre><code> + <call_expr 0xb7bc7850 + type <void_type 0xb7cc9270 void VOID + align 8 symtab 0 alias set -1 canonical type 0xb7cc9270 + pointer_to_this <pointer_type 0xb7cc92d8>> + side-effects addressable tree_5 + fn <var_decl 0xb7d65370 D.2156 + type <pointer_type 0xb7da74e0 type <function_type 0xb7da7478> + unsigned SI + size <integer_cst 0xb7cb36ac constant 32> + unit size <integer_cst 0xb7cb3498 constant 4> + align 32 symtab 0 alias set -1 structural equality> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32]) + chain <var_decl 0xb7d653c8 D.2157 type <pointer_type 0xb7cc92d8> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain <var_decl 0xb7d65420 D.2158>>> arg 0 <var_decl 0xb7d653c8 D.2157> + arg 1 <var_decl 0xb7d65420 D.2158 + type <pointer_type 0xb7da7270 stack type <void_type 0xb7cc9270 void> + sizes-gimplified unsigned SI size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8 + pointer_to_this <pointer_type 0xb7bb7000>> + used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4> + align 32 context <function_decl 0xb7da2c80 returner> + (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars) + (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])> + quicksort/quicksort_cbc.cbc:29:7> + </code></pre> + <p class="subtitle">全ての構文はこのGIMPLEで表される</p> + </li> + </ul> + <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p> +</div> + +<div class="slide" style="font-size:95%"> + <h1>GCC ミドルエンド</h1> + <p class="subtitle">GIMPLEからRTLへの変換と最適化</p> + <ul class="outline"> + <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li> + <li>登録されたpassを一つ一つ実行する</li> + <li>最初にGIMPLEの最適化がたくさんある</li> + <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li> + <li>最後にRTLの最適化がまた大量にある + <pre style="font-size:80%"><code> + p = &all_lowering_passes; + NEXT_PASS (pass_remove_useless_stmts); + NEXT_PASS (pass_mudflap_1); + NEXT_PASS (pass_lower_omp); + NEXT_PASS (pass_lower_cf); + NEXT_PASS (pass_refactor_eh); + NEXT_PASS (pass_lower_eh); + NEXT_PASS (pass_build_cfg); + NEXT_PASS (pass_lower_complex_O0); + NEXT_PASS (pass_lower_vector); +#ifndef noCbC + //NEXT_PASS (pass_warn_function_return); +#else + NEXT_PASS (pass_warn_function_return); +#endif + NEXT_PASS (pass_build_cgraph_edges); + NEXT_PASS (pass_inline_parameters); + *p = NULL; + + /* Interprocedural optimization passes. */ + p = &all_ipa_passes; + NEXT_PASS (pass_ipa_function_and_variable_visibility); + NEXT_PASS (pass_ipa_early_inline); + { + struct opt_pass **p = &pass_ipa_early_inline.pass.sub; + NEXT_PASS (pass_early_inline); + NEXT_PASS (pass_inline_parameters); + NEXT_PASS (pass_rebuild_cgraph_edges); + } + NEXT_PASS (pass_early_local_passes); + { + struct opt_pass **p = &pass_early_local_passes.pass.sub; + NEXT_PASS (pass_tree_profile); + NEXT_PASS (pass_cleanup_cfg); + NEXT_PASS (pass_init_datastructures); + NEXT_PASS (pass_expand_omp); + + NEXT_PASS (pass_referenced_vars); + NEXT_PASS (pass_reset_cc_flags); + NEXT_PASS (pass_build_ssa); + NEXT_PASS (pass_early_warn_uninitialized); + NEXT_PASS (pass_all_early_optimizations); + { + struct opt_pass **p = &pass_all_early_optimizations.pass.sub; + NEXT_PASS (pass_rebuild_cgraph_edges); + NEXT_PASS (pass_early_inline); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_update_address_taken); + NEXT_PASS (pass_sra_early); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_merge_phi); + NEXT_PASS (pass_cd_dce); + NEXT_PASS (pass_simple_dse); + NEXT_PASS (pass_tail_recursion); + NEXT_PASS (pass_convert_switch); + NEXT_PASS (pass_profile); + } + NEXT_PASS (pass_release_ssa_names); + NEXT_PASS (pass_rebuild_cgraph_edges); + NEXT_PASS (pass_inline_parameters); + } + NEXT_PASS (pass_ipa_increase_alignment); + NEXT_PASS (pass_ipa_matrix_reorg); + NEXT_PASS (pass_ipa_cp); + NEXT_PASS (pass_ipa_inline); + NEXT_PASS (pass_ipa_reference); + NEXT_PASS (pass_ipa_pure_const); + NEXT_PASS (pass_ipa_type_escape); + NEXT_PASS (pass_ipa_pta); + NEXT_PASS (pass_ipa_struct_reorg); + *p = NULL; + + /* These passes are run after IPA passes on every function that is being + output to the assembler file. */ + p = &all_passes; + NEXT_PASS (pass_all_optimizations); + { + struct opt_pass **p = &pass_all_optimizations.pass.sub; + /* Initial scalar cleanups before alias computation. + They ensure memory accesses are not indirect wherever possible. */ + NEXT_PASS (pass_strip_predict_hints); + NEXT_PASS (pass_update_address_taken); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_complete_unrolli); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_forwprop); + /* Ideally the function call conditional + dead code elimination phase can be delayed + till later where potentially more opportunities + can be found. Due to lack of good ways to + update VDEFs associated with the shrink-wrapped + calls, it is better to do the transformation + here where memory SSA is not built yet. */ + NEXT_PASS (pass_call_cdce); + /* pass_build_alias is a dummy pass that ensures that we + execute TODO_rebuild_alias at this point. Re-building + alias information also rewrites no longer addressed + locals into SSA form if possible. */ + NEXT_PASS (pass_build_alias); + NEXT_PASS (pass_return_slot); + NEXT_PASS (pass_phiprop); + NEXT_PASS (pass_fre); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_merge_phi); + NEXT_PASS (pass_vrp); + NEXT_PASS (pass_dce); + NEXT_PASS (pass_cselim); + NEXT_PASS (pass_tree_ifcombine); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_tail_recursion); + NEXT_PASS (pass_ch); + NEXT_PASS (pass_stdarg); + NEXT_PASS (pass_lower_complex); + NEXT_PASS (pass_sra); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_dominator); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); + NEXT_PASS (pass_dse); + NEXT_PASS (pass_reassoc); + NEXT_PASS (pass_dce); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_object_sizes); + NEXT_PASS (pass_ccp); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_fold_builtins); + NEXT_PASS (pass_cse_sincos); + NEXT_PASS (pass_split_crit_edges); + NEXT_PASS (pass_pre); + NEXT_PASS (pass_sink_code); + NEXT_PASS (pass_tree_loop); + { + struct opt_pass **p = &pass_tree_loop.pass.sub; + NEXT_PASS (pass_tree_loop_init); + NEXT_PASS (pass_copy_prop); + NEXT_PASS (pass_dce_loop); + NEXT_PASS (pass_lim); + NEXT_PASS (pass_predcom); + NEXT_PASS (pass_tree_unswitch); + NEXT_PASS (pass_scev_cprop); + NEXT_PASS (pass_empty_loop); + NEXT_PASS (pass_record_bounds); + NEXT_PASS (pass_check_data_deps); + NEXT_PASS (pass_loop_distribution); + NEXT_PASS (pass_linear_transform); + NEXT_PASS (pass_graphite_transforms); + NEXT_PASS (pass_iv_canon); + NEXT_PASS (pass_if_conversion); + NEXT_PASS (pass_vectorize); + { + struct opt_pass **p = &pass_vectorize.pass.sub; + NEXT_PASS (pass_lower_vector_ssa); + NEXT_PASS (pass_dce_loop); + } + NEXT_PASS (pass_complete_unroll); + NEXT_PASS (pass_parallelize_loops); + NEXT_PASS (pass_loop_prefetch); + NEXT_PASS (pass_iv_optimize); + NEXT_PASS (pass_tree_loop_done); + } + NEXT_PASS (pass_cse_reciprocals); + NEXT_PASS (pass_convert_to_rsqrt); + NEXT_PASS (pass_reassoc); + NEXT_PASS (pass_vrp); + NEXT_PASS (pass_dominator); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); + NEXT_PASS (pass_cd_dce); + NEXT_PASS (pass_tracer); + + /* FIXME: If DCE is not run before checking for uninitialized uses, + we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c). + However, this also causes us to misdiagnose cases that should be + real warnings (e.g., testsuite/gcc.dg/pr18501.c). + + To fix the false positives in uninit-5.c, we would have to + account for the predicates protecting the set and the use of each + variable. Using a representation like Gated Single Assignment + may help. */ + NEXT_PASS (pass_late_warn_uninitialized); + NEXT_PASS (pass_dse); + NEXT_PASS (pass_forwprop); + NEXT_PASS (pass_phiopt); + NEXT_PASS (pass_tail_calls); + NEXT_PASS (pass_rename_ssa_copies); + NEXT_PASS (pass_uncprop); + } + NEXT_PASS (pass_del_ssa); + NEXT_PASS (pass_nrv); + NEXT_PASS (pass_mark_used_blocks); + NEXT_PASS (pass_cleanup_cfg_post_optimizing); + + NEXT_PASS (pass_warn_function_noreturn); + NEXT_PASS (pass_free_datastructures); + NEXT_PASS (pass_mudflap_2); + + NEXT_PASS (pass_free_cfg_annotations); + <em>NEXT_PASS (pass_expand);</em> + NEXT_PASS (pass_rest_of_compilation); + { + struct opt_pass **p = &pass_rest_of_compilation.pass.sub; + NEXT_PASS (pass_init_function); + NEXT_PASS (pass_jump); + NEXT_PASS (pass_rtl_eh); + NEXT_PASS (pass_initial_value_sets); + NEXT_PASS (pass_unshare_all_rtl); + NEXT_PASS (pass_instantiate_virtual_regs); + NEXT_PASS (pass_into_cfg_layout_mode); + NEXT_PASS (pass_jump2); + NEXT_PASS (pass_lower_subreg); + NEXT_PASS (pass_df_initialize_opt); + NEXT_PASS (pass_cse); + NEXT_PASS (pass_rtl_fwprop); + NEXT_PASS (pass_gcse); + NEXT_PASS (pass_rtl_ifcvt); + /* Perform loop optimizations. It might be better to do them a bit + sooner, but we want the profile feedback to work more + efficiently. */ + NEXT_PASS (pass_loop2); + { + struct opt_pass **p = &pass_loop2.pass.sub; + NEXT_PASS (pass_rtl_loop_init); + NEXT_PASS (pass_rtl_move_loop_invariants); + NEXT_PASS (pass_rtl_unswitch); + NEXT_PASS (pass_rtl_unroll_and_peel_loops); + NEXT_PASS (pass_rtl_doloop); + NEXT_PASS (pass_rtl_loop_done); + *p = NULL; + } + NEXT_PASS (pass_web); + NEXT_PASS (pass_jump_bypass); + NEXT_PASS (pass_cse2); + NEXT_PASS (pass_rtl_dse1); + NEXT_PASS (pass_rtl_fwprop_addr); + NEXT_PASS (pass_reginfo_init); + NEXT_PASS (pass_inc_dec); + NEXT_PASS (pass_initialize_regs); + NEXT_PASS (pass_outof_cfg_layout_mode); + NEXT_PASS (pass_ud_rtl_dce); + NEXT_PASS (pass_combine); + NEXT_PASS (pass_if_after_combine); + NEXT_PASS (pass_partition_blocks); + NEXT_PASS (pass_regmove); + NEXT_PASS (pass_split_all_insns); + NEXT_PASS (pass_lower_subreg2); + NEXT_PASS (pass_df_initialize_no_opt); + NEXT_PASS (pass_stack_ptr_mod); + NEXT_PASS (pass_mode_switching); + NEXT_PASS (pass_see); + NEXT_PASS (pass_match_asm_constraints); + NEXT_PASS (pass_sms); + NEXT_PASS (pass_sched); + NEXT_PASS (pass_subregs_of_mode_init); + NEXT_PASS (pass_ira); + NEXT_PASS (pass_subregs_of_mode_finish); + NEXT_PASS (pass_postreload); + { + struct opt_pass **p = &pass_postreload.pass.sub; + NEXT_PASS (pass_postreload_cse); + NEXT_PASS (pass_gcse2); + NEXT_PASS (pass_split_after_reload); + NEXT_PASS (pass_branch_target_load_optimize1); + NEXT_PASS (pass_thread_prologue_and_epilogue); + NEXT_PASS (pass_rtl_dse2); + NEXT_PASS (pass_rtl_seqabstr); + NEXT_PASS (pass_stack_adjustments); + NEXT_PASS (pass_peephole2); + NEXT_PASS (pass_if_after_reload); + NEXT_PASS (pass_regrename); + NEXT_PASS (pass_cprop_hardreg); + NEXT_PASS (pass_fast_rtl_dce); + NEXT_PASS (pass_reorder_blocks); + NEXT_PASS (pass_branch_target_load_optimize2); + NEXT_PASS (pass_leaf_regs); + NEXT_PASS (pass_split_before_sched2); + NEXT_PASS (pass_sched2); + NEXT_PASS (pass_stack_regs); + { + struct opt_pass **p = &pass_stack_regs.pass.sub; + NEXT_PASS (pass_split_before_regstack); + NEXT_PASS (pass_stack_regs_run); + } + NEXT_PASS (pass_compute_alignments); + NEXT_PASS (pass_duplicate_computed_gotos); + NEXT_PASS (pass_variable_tracking); + NEXT_PASS (pass_free_cfg); + NEXT_PASS (pass_machine_reorg); + NEXT_PASS (pass_cleanup_barriers); + NEXT_PASS (pass_delay_slots); + NEXT_PASS (pass_split_for_shorten_branches); + NEXT_PASS (pass_convert_to_eh_region_ranges); + NEXT_PASS (pass_shorten_branches); + NEXT_PASS (pass_set_nothrow_function_flags); + NEXT_PASS (pass_final); + } + NEXT_PASS (pass_df_finish); + } + NEXT_PASS (pass_clean_state); + *p = NULL; + </code></pre> + </li> + </ul> + <p class="subtitle">RTL</p> + <ul class="outline"> + <li>一般的には中間コードとも呼ばれる</li> + <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li> + <li>RTLの例 +<pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [ + (set (reg/f:SI 7 sp) + (plus:SI (reg/f:SI 7 sp) + (const_int -1024 [0xfffffc00]))) + (clobber (reg:CC 17 flags)) + ]) -1 (nil)) +</code></pre> + </li> + </ul> +</div> + +<div class="slide"> + <h1>バックエンド</h1> + <p class="subtitle">RTLからアセンブラに変換する処理</p> + <ul class="outline"> + <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li> + <li>アーキテクチャ毎にこのmdが必要になる</li> + <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li> + <li>mdの例 + <pre><code> +(define_insn "cmpdi_ccno_1_rex64" + [(set (reg FLAGS_REG) + (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr") + (match_operand:DI 1 "const0_operand" "")))] + "TARGET_64BIT && ix86_match_ccmode (insn, CCNOmode)" + "@ + test{q}\t%0, %0 + cmp{q}\t{%1, %0|%0, %1}" + [(set_attr "type" "test,icmp") + (set_attr "length_immediate" "0,1") + (set_attr "mode" "DI")]) + +(define_insn "*cmpdi_minus_1_rex64" + [(set (reg FLAGS_REG) + (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r") + (match_operand:DI 1 "x86_64_general_operand" "re,mr")) + (const_int 0)))] + "TARGET_64BIT && ix86_match_ccmode (insn, CCGOCmode)" + "cmp{q}\t{%1, %0|%0, %1}" + [(set_attr "type" "icmp") + (set_attr "mode" "DI")]) + </code></pre></li> + </ul> +</div> + +<div class="slide"> + <h1>本研究での取り組み</h1> + <p class="subtitle">取り組み</p> + <dl> + <dt>First</dt> + <dd>GCCにて実用レベルのCbCプログラムを動作可能にする + <ul> + <li>軽量継続の実装、これまでの制限の除去</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>C言語との互換性の向上</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + + + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">軽量継続を実装するには?</p> + <ul> + <li>micro-cは元より軽量継続を考慮して良く設計されている</li> + <li>GCCでは<em class="weak">あくまで関数</em>がベース</li> + <li>micro-Cと同じ命令列を出力させるのは難しい</li> + <li>関数コール(call命令)ではもちろんダメ</li> + <li>必ず<em>jmp命令</em>を出力しないといけない</li> + <li>スタックを拡張するのもダメ</li> + </ul> + <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出ってなに?</p> + <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" /> + <ul> + <li>リターンの直前の関数呼び出しのこと</li> + <li>GCCが最適化してくれる (<em>TCE</em>)</li> + <li>元の関数に戻らないため少し高速に</li> + <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出ってなに?</p> + <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" /> + <ul> + <li>リターンの直前の関数呼び出しのこと</li> + <li>GCCが最適化してくれる (<em>TCE</em>)</li> + <li>元の関数に戻らないため少し高速に</li> + <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li> + </ul> + <p class="subtitle incremental">軽量継続ではこの末尾呼出(TCE)を強制する!</p> +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出による軽量継続の実装</p> + <ul> + <li>全ての軽量継続は末尾呼出と解釈する</li> + <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li> + <li><code>goto cs(20, 30);</code></li> + <li><code>cs(20, 30); return;</code></li> + </ul> + <p class="subtitle">ある条件で末尾呼出が行われなくなる</p> + <ol> + <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li> + <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li> + </ol> +</div> +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">末尾呼出による軽量継続の実装</p> + <ul> + <li>全ての軽量継続は末尾呼出と解釈する</li> + <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li> + <li><code>goto cs(20, 30);</code></li> + <li><code>cs(20, 30); return;</code></li> + </ul> + <p class="subtitle">ある条件で末尾呼出が行われなくなる</p> + <ol> + <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li> + <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li> + </ol> +</div> + + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">引数順序の問題の解決</p> + <ul> + <li>問題となる例 +<pre><code>code somesegment(int a, int b, int c) { + /∗ do something ∗/ + goto nextsegment(b, c, a); +} +</code></pre> + </li> + <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li> + <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li> + <li>必ず一つ(1ワード)以上の一時変数が必要になる</li> + </ul> + +</div> + +<div class="slide"> + <h1>First: 軽量継続の実装</h1> + <p class="subtitle">全ての引数を一時変数に退避</p> + <ul> + <li>次の様に構文木を変更する +<pre><code>code somesegment(int a, int b, int c) { + int a1, b1, c1; + /∗ do something ∗/ + a1=a; b1=b; c1=c; + goto nextsegment(b1, c1, a1); +} +</code></pre> + </li> + <li>これにより、引数順序を考える必要はなくなる</li> + <li>代わりに、メモリアクセスが大量に発生</li> + <li>しかし、これはGCCの最適化で除去される</li> + </ul> + + <p class="subtitle">これで軽量継続が実装された</p> +</div> + + +<div class="slide"> + <h1>First: x86における高速化</h1> + <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p> + <ul> + <li>特にx86アーキテクチャ</li> + <li><em class="weak">あくまで関数がベース</em>なので</li> + <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li> + <li>これをレジスタにすれば高速化が可能</li> + </ul> + <p class="subtitle">fastcallの導入</p> + <ul> + <li>GCCの独自拡張機能</li> + <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li> + </ul> +</div> + +<div class="slide"> + <h1>First: x86における高速化</h1> + <p class="subtitle">fastcallの強制</p> + <ul> + <li>通常は以下の様に定義される +<pre><code>__code current(int a, int b, int c) __attribute__((fastcall)); +</code></pre></li> + <li>しかしこれを毎回ユーザが書くのは変</li> + <li>やはりフロントエンドにて、強制するべき</li> + <li>型の構文木を生成した際にfastcall属性を付加</li> + </ul> + <p class="subtitle">実際の出力はどうなる?</p> + <div style="width:70%;margin:1em auto 0;"> +<pre><code>__code current(int a, int b, int c) { + goto next(10, 20, 30); +} +</code></pre> + </div> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>First: x86における高速化</h1> + <p class="subtitle">実際の出力アセンブラ</p> + <div style="width:50%;float:left;margin-left:auto;"> + <p style="margin:0;text-align:center">fastcallにした場合</p> +<pre><code>current: + subl $12, %esp + movl $30, 16(%esp) + movl $20, %edx + movl $10, %ecx + addl $12, %esp + jmp next +</code></pre> + </div> + <div style="width:50%;float:right;margin-right:auto;"> + <p style="margin:0;text-align:center">normalcallの場合</p> +<pre><code>current: + pushl %ebp + movl %esp, %ebp + movl $30, 16(%ebp) + movl $20, 12(%ebp) + movl $10, 8(%ebp) + leave + jmp next +</code></pre> + </div> + <br clear="all" /> + <ul> + <li>命令数ではほとんど変化はない</li> + <li>引数2つがレジスタecxとedxに格納されるようになった</li> + <li>そのためメモリアクセスが減る</li> + <li>これで高速化されるはず</li> + </ul> +</div> + + +<div class="slide"> + <h1>First: CbCコンパイラ実装の評価</h1> + <p class="subtitle">CbCGCCとmicro-cで性能の比較</p> + <ul> + <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li> + <li>コンパイラの出力した実行ファイルを比較</li> + <li>CbCでのquicksort例題を用意</li> + <li>実行速度、ファイルサイズ</li> + <li>比較対象はまずは旧CbCGCC、それとmicro-c</li> + </ul> + <p class="subtitle">実行環境</p> + <ul> + <li>CbCGCC、micro-cでともに実行可能な環境を選択</li> + <li>アーキテクチャは x86, PowerPC(Cell含む)</li> + <li>OSはLinuxとOS Xを使用する</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価(速度比較) vs.旧ver</h1> + <p class="subtitle">速度測定結果(単位:秒)</p> + <table> + <tr> + <th></th> + <th colspan="2">新CbCGCC</th> + <th colspan="2">旧CbCGCC</th> + </tr> + <tr> + <td></td> + <th>最適化無し</th> + <th>最適化有り</th> + <th>最適化無し</th> + <th>最適化有り</th> + </tr> + <tr> + <td>x86/OS X</td> + <td>5.907</td> + <td>2.434</td> + <td>4.668</td> + <td>3.048</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5.715</td> + <td>2.401</td> + <td>4.525</td> + <td>2.851</td> + </tr> + </table> + <p class="subtitle">評価</p> + <ul> + <li>最適化無の場合は遅くなった </li> + <li>一時変数への確保があるのでこれは予想通り</li> + <li>最適化を行うと、<em>約20%の高速化に成功</em></li> + <li>fastcallの効果が十分に出ている</li> + </ul> +</div> + + +<div class="slide"> + <h1>First: 性能評価(速度比較)</h1> + <p class="subtitle">速度測定結果(単位:秒)</p> + <table> + <tr> + <td></td> + <td>最適化なしのGCC</td> + <td>最適化付きのGCC</td> + <td>micro-c</td> + </tr> + <tr> + <td>x86/OS X</td> + <td>5.901</td> + <td>2.434</td> + <td>2.857</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5.732</td> + <td>2.401</td> + <td>2.254</td> + </tr> + <tr> + <td>ppc/OS X</td> + <td>14.875</td> + <td>2.146</td> + <td>4.811</td> + </tr> + <tr> + <td>ppc/Linux</td> + <td>19.793</td> + <td>3.955</td> + <td>6.454</td> + </tr> + <tr> + <td>ppc/PS3</td> + <td>39.176</td> + <td>5.874</td> + <td>11.121</td> + </tr> + </table> + <p class="subtitle">結果(micro-cとの比較)</p> + <ul> + <li>x86では速度にあまり差が出なかった</li> + <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li> + <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価(速度比較)</h1> + <p class="subtitle">結果(micro-cとの比較)</p> + <ul> + <li>x86では速度にあまり差が出なかった</li> + <li>PowerPCではCbCGCCが2倍ほど早い</li> + </ul> + <p class="subtitle">この違いはどこから?</p> + <ul style="font-size:95%;"> + <li>実際にアセンブラを出力して比較、その結果</li> + <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li> + <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li> + <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li> + <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li> + </ul> +</div> + +<div class="slide"> + <h1>First: 性能評価(サイズ比較)</h1> + <p class="subtitle">ファイルサイズの比較</p> + <ul> + <li>組み込み系ではメモリ使用量が肝心</li> + <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li> + <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li> + </ul> + <p class="subtitle">結果</p> + <table> + <tr> + <td></td> + <th>CbCGCC<br/>速度最適化</th> + <th>CbCGCC<br/>サイズ最適化</th> + <th>micro-c</th> + </tr> + <tr> + <td>x86/OS X</td> + <td>9176</td> + <td>9176</td> + <td>9172</td> + </tr> + <tr> + <td>x86/Linux</td> + <td>5752</td> + <td>5752</td> + <td>5796</td> + </tr> + <tr> + <td>ppc/OS X</td> + <td>8576</td> + <td>8576</td> + <td>12664</td> + </tr> + <tr> + <td>ppc/Linux</td> + <td>10068</td> + <td>10068</td> + <td>9876</td> + </tr> + <tr> + <td>ppc/PS3</td> + <td>6960</td> + <td>6728</td> + <td>8636</td> + </tr> + </table> + <p class="subtitle">結果考察</p> + <ul> + <li>x86ではファイルサイズの差がない</li> + <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li> + <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li> + </ul> +</div> + + +<div class="slide"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">なぜそれが必要か</p> + <ul> + <li>C <=> CbC の変換が可能なので互換性はある</li> + <li>しかし、ソースコード上での互換性もある事が望ましい</li> + <li>CbCからCの関数を呼び出すのは問題ない</li> + <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li> + </ul> + <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p> + <ul> + <li>軽量継続に、スタックの情報を加える</li> + <li>つまり通常の「継続」と同じ</li> + <li>関数からのみ使用可能</li> + </ul> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用</h1> + <pre style="float:right; width-max:45%"> +<code>typedef code (*NEXT)(int); +int main(int argc, char **argv) { + int i,a; + i = atoi(argv[1]); + <em>a = factor(i);</em> + printf("%d! = %d\n", a); +} +int factor(int x) { + NEXT ret = <em>__return</em>; + goto factor0(1, x, ret); +} +code +factor0(int prod,int x,NEXT next) { + if (x >= 1) { + goto factor0(prod*x, x-1, next); + } else { + <em>goto (*next)(prod);</em> + } +} +</code></pre> + <p class="subtitle">環境付き継続の使用例</p> + <ul> + <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li> + <li>コードセグメントからは通常のコードセグメントポインタに見える</li> + <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li> + </ul> +</div> + +<div class="slide"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">どのように実装する?</p> + <ol> + <li>setjmp()/longjmp()を使って実装可能 + <ul> + <li>Cの標準ライブラリの関数</li> + <li>しかし余計な環境も保持するためオーバヘッドが大きい</li> + <li>継続の際に渡す引数が一つ増えてしまう</li> + </ul></li> + <li>内部関数 + <ul> + <li>GCCの独自拡張</li> + <li>関数内に関数を定義可能</li> + <li><em>内部関数から外の関数のラベルにgotoできる</em></li> + </ul></li> + </ol> + <p class="subtitle">内部関数が使いやすい</p> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用</h1> + <p class="subtitle">具体的には</p> + <ul> + <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li> + <li>内部関数の中からは外の関数にgotoして脱出</li> + </ul> + <pre><code>int factor(int x) { + int retval; + + <em class="weak">code __return(int val) { + retval = val; + goto label; + } + if (0) { + label: + return retval; + }</em> + + NEXT ret = <em>__return</em>; + goto factor0(1, x, ret); +} </code></pre> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>Second: Cとの相互利用・評価</h1> + <p class="subtitle">この取り組みにより</p> + <ul> + <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li> + <li>ソースコードレベルで、Cと相互に利用することが可能になった</li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <p class="subtitle">GCCのアップデートリリースは早い</p> + <ul> + <li>リリースだけで年に5回のペース</li> + <li>その度にバグの修正やコードの改善が入る</li> + <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li> + </ul> + <p class="subtitle">このリリースに追従して差分をアップデートしたい</p> + <ul> + <li>GCC本家にマージしてもらうのが一番良いが難しい</li> + <li></li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <img style="width:60%;float:right;" src="figures/gcc-repository.png" /> + <p class="subtitle">二つのリポジトリ管理</p> + <ul> + <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li> + <li>CbCの修正が加えられたリポジトリ CbCGCC</li> + <li>Mercurialによる分散リポジトリ管理</li> + <li>CbCGCC は GCC_copyをクローン(ブランチ)して作成する</li> + </ul> + <p class="subtitle"></p> +</div> + + +<div class="slide"> + <h1>Third: メンテナンス性の向上</h1> + <p class="subtitle">アップデート手順</p> + <ul> + <li>GCC-copyリポジトリにて + <ol> + <li>GCC-copyリポジトリのファイルをすべて消す</li> + <li>GCCの最新バージョンをリポジトリ内に展開</li> + <li>追加ファイル、削除ファイルを確認</li> + <li>コミット、タグ付け</li> + </ol> </li> + <li>CbCGCCリポジトリにて + <ol> + <li>GCC-copyからpull.</li> + <li>hg mergeでマージ実行</li> + <li>衝突があればソースコードをを修正</li> + <li>ビルドテスト</li> + <li>コミット、タグ付け</li> + </ol></li> + </ul> +</div> + +<div class="slide"> + <h1>Third: メンテナンス性の向上・比較</h1> + <p class="subtitle">これまでのアップデートは</p> + <ul> + <li>GCCの新旧の差分、CbCの差分</li> + <li>複雑なdiffをとる必要がある</li> + </ul> + <p class="subtitle">新しい管理方法により</p> + <ul> + <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li> + <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li> + <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li> + </ul> +</div> + +<div class="slide"> + <h1>まとめ</h1> + <p class="subtitle">本研究での取り組み</p> + <dl> + <dt>First</dt> + <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった + <ul> + <li>軽量継続における引数順序の制限を取り除いた</li> + <li>PowerPCでの間接継続の制限を取り除いた</li> + <li>x86アーキテクチャにて高速化を行った</li> + </ul> + </dd> + <dt>Second</dt> + <dd>Cとの相互利用性の向上</dd> + <dt>Third</dt> + <dd>ソースコードメンテナンス性の向上</dd> + </dl> +</div> + +<div class="slide" style="font-size:95%;"> + <h1>まとめ</h1> + <p class="subtitle">本研究での成果</p> + <dl> + <dt>成果1</dt> + <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった + <dt>成果2</dt> + <dd>CbCが多数のアーキテクチャに対応 + <ul> + <li>20以上のアーキテクチャ</li> + <li>特に64bitのx86, SPUがうれしい</li> + </ul> </dd> + <dt>成果3</dt> + <dd>CbCの高速化 + <ul> + <li>x86においてもmicro-cと互角の速度を達成</li> + <li>PowerPCでは2倍の速度</li> + </ul></dd> + <dt>成果4</dt> + <dd>メンテナンス性が向上</dd> + </dl> +</div> + +<div class="slide"> + <h1>今後の課題</h1> + <p class="subtitle"></p> + <ul> + <li>Real-time、組込み向けに実用的なCbCプログラムの例題</li> + <li>タブロー方を用いた検証</li> + <li>TaskManagerのCbC実装</li> + </ul> + <p class="subtitle">CbC言語の今後</p> + <ul> + <li>オブジェクティブなCbCの設計</li> + <li>データセグメントの導入</li> + <li>スケジューラのためのリフレクション</li> + </ul> +</div> + + +<div class="slide"> + <h1>おわり</h1> + <p class="subtitle">ありがとうございました</p> +</div> + + + + + + + + @@ -733,203 +1931,27 @@ </div> </div> - -<div class="slide"> - <h1>継続とはなんなのか?</h1> - <p class="subtitle">継続</p> - <ul> - <li>現在の処理を続行するための情報 - <ul> - <li>Cならば続く命令のアドレスや</li> - <li>命令に必要な値、</li> - <li>スタックなど、その環境全てを含む</li> - </ul> - </li> - </ul> - <p class="subtitle">CbCでの軽量継続</p> - <ul> - <li>継続からスタックに関する情報を落とす</li> - <li>続く命令とデータのみのシンプルな継続</li> - <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li> - </ul> -</div> - -<div class="slide" style="font-size:95%;"> - <h1>コードセグメントと軽量継続の記述</h1> - <pre style="float:right; width-max:45%"> -<code>typedef code (*NEXT)(int); -int main(int argc, char **argv) { - int i; - i = atoi(argv[1]); - goto factor(i, print_fact); -} -<em>code factor(int x, NEXT next)</em> { - goto factor0(1, x, next); -} -code factor0(int prod,int x,NEXT next) { - if (x >= 1) { - goto factor0(prod*x, x-1, next); - } else { - <em>goto (*next)(prod);</em> - } -} -code print_fact(int value) { - printf("factorial = %d\n", value); - exit(0); -} </code></pre> - <p class="subtitle">実際のプログラム記述は?</p> - <ul> - <li>コードセグメント定義 - <ul> - <li><code>codeキーワードで宣言</code></li> - <li>書式は関数と同じ</li> - </ul> - </li> - <li>軽量継続制御 - <ul> - <li><code>goto</code>キーワードと引数</li> - <li>コードセグメントの最初に飛ぶ</li> - <li>コードセグメントポインタによる間接継続も可能</li> - </ul> - </li> - </ul> -</div> - <div class="slide"> <h1>Cとの比較について</h1> - <p class="subtitle">quicksort例題をCと比較すると</p> + <p class="subtitle">CbCとCの比較に関して</p> <ul> - <li>現在のところ、遅くなる</li> - <li>問題はquicksortという例題では必ずスタックが必要だということ</li> - <li>例題ではスタックを自前の構造体で用意している</li> - <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li> - <li>状態遷移ベースの例題を作りたい</li> + <li>まだ例題を用意していない</li> + <li>quicksortはスタックが必要となるため、Cに有利</li> + <li>この例題ではプログラム上自前でスタックを用意している</li> + <li>このメモリへのアクセスはスタックより重い</li> + <li>Cとの比較には状態遷移ベースの例題があった方が良い</li> </ul> </div> -<div class="slide" style="font-size:95%;"> - <h1>fastcall</h1> - <p class="subtitle">実際の出力アセンブラ</p> - <div style="width:50%;float:left;margin-left:auto;"> - <p style="margin:0;text-align:center">fastcallにした場合</p> -<pre><code>current: - subl $12, %esp - movl $30, 16(%esp) - movl $20, %edx - movl $10, %ecx - addl $12, %esp - jmp next -</code></pre> - </div> - <div style="width:50%;float:right;margin-right:auto;"> - <p style="margin:0;text-align:center">normalcallの場合</p> -<pre><code>current: - pushl %ebp - movl %esp, %ebp - movl $30, 16(%ebp) - movl $20, 12(%ebp) - movl $10, 8(%ebp) - leave - jmp next -</code></pre> - </div> - <br clear="all" /> - <ul> - <li>命令数ではほとんど変化はない</li> - <li>引数2つがレジスタecxとedxに格納されるようになった</li> - <li>そのためメモリアクセスが減る</li> - <li>これで高速化されるはず</li> - </ul> -</div> + + + -<div class="slide"> - <h1>First: 性能評価(サイズ比較)</h1> - <p class="subtitle">ファイルサイズの比較</p> - <ul> - <li>組み込み系ではメモリ使用量が肝心</li> - <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li> - <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li> - </ul> - <p class="subtitle">結果</p> - <table> - <tr> - <td></td> - <th>CbCGCC<br/>速度最適化</th> - <th>CbCGCC<br/>サイズ最適化</th> - <th>micro-c</th> - </tr> - <tr> - <td>x86/OS X</td> - <td>9176</td> - <td>9176</td> - <td>9172</td> - </tr> - <tr> - <td>x86/Linux</td> - <td>5752</td> - <td>5752</td> - <td>5796</td> - </tr> - <tr> - <td>ppc/OS X</td> - <td>8576</td> - <td>8576</td> - <td>12664</td> - </tr> - <tr> - <td>ppc/Linux</td> - <td>10068</td> - <td>10068</td> - <td>9876</td> - </tr> - <tr> - <td>ppc/PS3</td> - <td>6960</td> - <td>6728</td> - <td>8636</td> - </tr> - </table> - <p class="subtitle">結果考察</p> - <ul> - <li>x86ではファイルサイズの差がない</li> - <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li> - <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li> - </ul> -</div> + -<div class="slide"> - <h1>並列代入</h1> - <p class="subtitle">ある条件で末尾呼出が行われなくなる</p> - <ol> - <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li> - <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li> - </ol> - <p class="subtitle">問題となる例</p> -<pre><code>code somesegment(int a, int b, int c) { - /∗ do something ∗/ - goto nextsegment(b, c, a); -} -</code></pre> - <ul> - <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li> - <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li> - <li>必ず一つ(1ワード)以上の一時変数が必要になる</li> - </ul> - <p class="subtitle">次の様に構文木を変更する</p> -<pre><code>code somesegment(int a, int b, int c) { - int a1, b1, c1; - /∗ do something ∗/ - a1=a; b1=b; c1=c; - goto nextsegment(b1, c1, a1); -} -</code></pre> - <ul> - <li>これにより、引数順序を考える必要はなくなる</li> - <li>代わりに、メモリアクセスが大量に発生</li> - <li>しかし、これはGCCの最適化で除去される</li> - </ul> -</div> + +