# Date 1266382855 -32400 # Node ID d9b85f0419081298596d06e988ccd7ea5c757b77 # Parent 67544736317e059c81980a2baccf1fff6edf5c81 up recital diff -r 67544736317e -r d9b85f041908 recital-slide/slide.html --- 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 @@

継続とはなんなのか？

継続

現在の処理を続行するための情報 +
- Cならば続く命令のアドレスや
- 命令に必要な値、
- スタックなど、その環境全てを含む
+

CbCでの軽量継続

継続からスタックに関する情報を落とす
続く命令とデータのみのシンプルな継続
命令はコードセグメント、引数はインタフェイスと呼ばれる

コードセグメントと軽量継続の記述

@@ -285,14 +305,14 @@
   First: 軽量継続の実装
   軽量継続を実装するには？
   
-    河野先生の作ったmicro-cは元より軽量継続を考慮して良く設計されている
+    micro-cは元より軽量継続を考慮して良く設計されている
     micro-Cと同じ命令列を出力させるのは難しい
     関数コール(call命令)ではもちろんダメ
     必ずjmp命令を出力しないといけない
     スタックを拡張してはいけない
-    しかしGCCでは関数をベースにしなければならない
+    加えて、GCCでは関数をベースにしなければならない
   
-  末尾呼出をGCCに強制させる必要がある
+  そこで、末尾呼出をGCCに強制させる必要がある

@@ -321,6 +341,11 @@

First: 軽量継続の実装

プログラム実行時のスタックの変化

+ +

First: x86における高速化

軽量継続は実装されたが、やはりmicro-cに比べると遅い

環境付き継続の使用例

__retunrで表される特殊なコードセグメント
__returnで表される特殊なコードセグメント
コードセグメントからは通常のコードセグメントポインタに見える
この__returnに継続すると、元の関数の環境にリターン

Second: Cとの相互利用・評価

この取り組みにより

これにより、C with Continuation の仕様を満たした
これにより、Continuation based C の全仕様を満たした
ソースコードレベルで、Cと相互に利用することが可能になった

@@ -557,7 +582,7 @@

First

CbCGCCにて実用レベルのCbCプログラムが動作可能となった

軽量継続における引数順序の制限を取り除いた
軽量継続における引数順序の制限を取り除いた
PowerPCでの間接継続の制限を取り除いた
x86アーキテクチャにて高速化を行った

@@ -619,6 +644,1179 @@ +

継続とはなんなのか？

継続

現在の処理を続行するための情報 +
- Cならば続く命令のアドレスや
- 命令に必要な値、
- スタックなど、その環境全てを含む
+

CbCでの軽量継続

継続からスタックに関する情報を落とす
続く命令とデータのみのシンプルな継続
命令はコードセグメント、引数はインタフェイスと呼ばれる

+ +

コードセグメントと軽量継続の記述

+typedef code (*NEXT)(int);
+int main(int argc, char **argv) {
+  int i;
+  i = atoi(argv[1]);
+  goto factor(i, print_fact);
+}
+code factor(int x, NEXT next) {
+  goto factor0(1, x, next);
+}
+code factor0(int prod,int x,NEXT next) {
+  if (x >= 1) {
+    goto factor0(prod*x, x-1, next);
+  } else {
+    goto (*next)(prod);
+  }
+}
+code print_fact(int value) {
+  printf("factorial = %d\n", value);
+  exit(0);
+}

実際のプログラム記述は？

コードセグメント定義 +
- codeキーワードで宣言
- 書式は関数と同じ
+
軽量継続制御 +
- gotoキーワードと引数
- コードセグメントの最初に飛ぶ
- コードセグメントポインタによる間接継続も可能
+

+ +

これまでのCbC

2000: micro-cをベースとしたコンパイラの完成
+ x86, PowerPC, ARM, MIPS. +
2002: CbCを用いた分散計算
2005: CbCを用いたプログラム分割手法
2006: CbCによるSPUマシンのシミュレータ
2007: 時相論理をベースとしたCbCプログラムの検証
2008: GCCをベースとしたコンパイラが開発される
2010: GCCベースコンパイラを実用レベルに拡張

+ +

本研究での取り組み

取り組み

First

GCCにて実用レベルのCbCプログラムを動作可能にする +

軽量継続の実装、これまでの制限の除去
x86アーキテクチャにて高速化を行った

Second

C言語との相互利用を可能にした

Third

ソースコードメンテナンス性の向上

+ + + +

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

フロントエンド
ミドルエンド
バックエンド

+ +

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

フロントエンド
ミドルエンド
バックエンド

+ + +

GCC フロントエンド

GCCにおける構文解析部

C,Java,Adaなど、言語毎に違う
解析した構文はGenericという構文木に構築
さらに静的単一代入と呼ばれる手法でGIMPLEという構文木に変換
最終的にこのGIMPLE構文木をミドルエンドに渡す

GIMPLEの内部表現例 +


+ <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>
+

全ての構文はこのGIMPLEで表される

つまり、主に修正すべきはこのフロントエンドとなる

+ +

GCC ミドルエンド

GIMPLEからRTLへの変換と最適化

passと呼ばれる様々な処理の集合体
登録されたpassを一つ一つ実行する
最初にGIMPLEの最適化がたくさんある
そしてもっとも重要なGIMPLEからRTLへの変換

最後にRTLの最適化がまた大量にある +


+  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);
+  NEXT_PASS (pass_expand);
+  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;
+

RTL

一般的には中間コードとも呼ばれる
アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現

RTLの例 +

(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))
+

+ +

バックエンド

RTLからアセンブラに変換する処理

Machine Description(md)と呼ばれる変換規則を用いる
アーキテクチャ毎にこのmdが必要になる
新しいアーキテクチャの対応はこのバックエンドを修正することになる

mdの例 +


+(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")])
+

+ +

本研究での取り組み

取り組み

First

GCCにて実用レベルのCbCプログラムを動作可能にする +

軽量継続の実装、これまでの制限の除去
x86アーキテクチャにて高速化を行った

Second

C言語との互換性の向上

Third

ソースコードメンテナンス性の向上

+ + + +

First: 軽量継続の実装

軽量継続を実装するには？

micro-cは元より軽量継続を考慮して良く設計されている
GCCではあくまで関数がベース
micro-Cと同じ命令列を出力させるのは難しい
関数コール(call命令)ではもちろんダメ
必ずjmp命令を出力しないといけない
スタックを拡張するのもダメ

末尾呼出をGCCに強制させる必要がある

+ +

First: 軽量継続の実装

末尾呼出ってなに？

リターンの直前の関数呼び出しのこと
GCCが最適化してくれる (TCE)
元の関数に戻らないため少し高速に
スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減

+ +

First: 軽量継続の実装

末尾呼出ってなに？

リターンの直前の関数呼び出しのこと
GCCが最適化してくれる (TCE)
元の関数に戻らないため少し高速に
スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減

軽量継続ではこの末尾呼出(TCE)を強制する！

+ +

First: 軽量継続の実装

末尾呼出による軽量継続の実装

全ての軽量継続は末尾呼出と解釈する
変更箇所はGCCのフロントエンドでの構文解析
goto cs(20, 30);
cs(20, 30); return;

ある条件で末尾呼出が行われなくなる

呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合
引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合

First: 軽量継続の実装

末尾呼出による軽量継続の実装

全ての軽量継続は末尾呼出と解釈する
変更箇所はGCCのフロントエンドでの構文解析
goto cs(20, 30);
cs(20, 30); return;

ある条件で末尾呼出が行われなくなる

~~呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合~~ 解決済み
引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合

+ + +

First: 軽量継続の実装

引数順序の問題の解決

問題となる例 +

code somesegment(int a, int b, int c) {
+  /∗ do something ∗/
+  goto nextsegment(b, c, a);
+}
+

(a,b,c) = (b,c,a)と本質的に同じ。これが並列代入
a=b,b=c,c=aではだめ。aの値が失われる
必ず一つ(1ワード)以上の一時変数が必要になる

+ +

First: 軽量継続の実装

全ての引数を一時変数に退避

次の様に構文木を変更する +

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);
+}
+

これにより、引数順序を考える必要はなくなる
代わりに、メモリアクセスが大量に発生
しかし、これはGCCの最適化で除去される

+ +

これで軽量継続が実装された

+ + +

First: x86における高速化

軽量継続は実装されたが、やはりmicro-cに比べると遅い

特にx86アーキテクチャ
あくまで関数がベースなので
関数呼出規約に従い全ての引数をスタックに格納してしまう
これをレジスタにすれば高速化が可能

fastcallの導入

GCCの独自拡張機能
引数の最初の2つのみレジスタに保持するようになる

+ +

First: x86における高速化

fastcallの強制

通常は以下の様に定義される +

__code current(int a, int b, int c) __attribute__((fastcall));
+

しかしこれを毎回ユーザが書くのは変
やはりフロントエンドにて、強制するべき
型の構文木を生成した際にfastcall属性を付加

実際の出力はどうなる？

__code current(int a, int b, int c) {
+    goto next(10, 20, 30);
+}
+

+ +

First: x86における高速化

実際の出力アセンブラ

fastcallにした場合

current:
+    subl    $12, %esp
+    movl    $30, 16(%esp)
+    movl    $20, %edx
+    movl    $10, %ecx
+    addl    $12, %esp
+    jmp     next
+

normalcallの場合

current:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    $30, 16(%ebp)
+    movl    $20, 12(%ebp)
+    movl    $10, 8(%ebp)
+    leave
+    jmp     next
+

+
+

命令数ではほとんど変化はない
引数2つがレジスタecxとedxに格納されるようになった
そのためメモリアクセスが減る
これで高速化されるはず

+ + +

First: CbCコンパイラ実装の評価

CbCGCCとmicro-cで性能の比較

CbCGCCが実用的になったことで、micro-cとの比較が可能に
コンパイラの出力した実行ファイルを比較
CbCでのquicksort例題を用意
実行速度、ファイルサイズ
比較対象はまずは旧CbCGCC、それとmicro-c

実行環境

CbCGCC、micro-cでともに実行可能な環境を選択
アーキテクチャは x86, PowerPC(Cell含む)
OSはLinuxとOS Xを使用する

+ +

First: 性能評価（速度比較） vs.旧ver

速度測定結果(単位:秒)

+ + + + + + + + + + + + + + + + + + + + + + + + + + + +

	新CbCGCC		旧CbCGCC
	最適化無し	最適化有り	最適化無し	最適化有り
x86/OS X	5.907	2.434	4.668	3.048
x86/Linux	5.715	2.401	4.525	2.851

評価

最適化無の場合は遅くなった
一時変数への確保があるのでこれは予想通り
最適化を行うと、約20%の高速化に成功
fastcallの効果が十分に出ている

+ + +

First: 性能評価（速度比較）

速度測定結果(単位:秒)

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

	最適化なしのGCC	最適化付きのGCC	micro-c
x86/OS X	5.901	2.434	2.857
x86/Linux	5.732	2.401	2.254
ppc/OS X	14.875	2.146	4.811
ppc/Linux	19.793	3.955	6.454
ppc/PS3	39.176	5.874	11.121

結果(micro-cとの比較)

x86では速度にあまり差が出なかった
x86に特化しているmicro-cと差がないのはとても良い結果
PowerPCではCbCGCCが2倍ほど早い

+ +

First: 性能評価（速度比較）

結果(micro-cとの比較)

x86では速度にあまり差が出なかった
PowerPCではCbCGCCが2倍ほど早い

この違いはどこから？

実際にアセンブラを出力して比較、その結果
x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい
演算の度にメモリ読み込み、演算、書き込みが発生する
レジスタの多いアーキテクチャではCbCGCCが断然有利になる
またCbC言語そのものもレジスタが多いアーキテクチャで有利

+ +

First: 性能評価（サイズ比較）

ファイルサイズの比較

組み込み系ではメモリ使用量が肝心
CbCGCCのサイズ最適化、速度最適化も対象とする
デバグ情報を付加しない、strip後のファイルサイズを比較

結果

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

	CbCGCC 速度最適化	CbCGCC サイズ最適化	micro-c
x86/OS X	9176	9176	9172
x86/Linux	5752	5752	5796
ppc/OS X	8576	8576	12664
ppc/Linux	10068	10068	9876
ppc/PS3	6960	6728	8636

結果考察

x86ではファイルサイズの差がない
ppcではOSによって違うが、OS Xでは3分の2に抑えることができている
サイズ最適化は必要ない、速度最適化で充分

+ + +

Second: Cとの相互利用

なぜそれが必要か

C <=> CbC の変換が可能なので互換性はある
しかし、ソースコード上での互換性もある事が望ましい
CbCからCの関数を呼び出すのは問題ない
CからCbCのコードセグメントに継続するとスタックが保持されない

環境付き継続の導入

軽量継続に、スタックの情報を加える
つまり通常の「継続」と同じ
関数からのみ使用可能

+ +

Second: Cとの相互利用

+typedef code (*NEXT)(int);
+int main(int argc, char **argv) {
+  int i,a;
+  i = atoi(argv[1]);
+  a = factor(i);
+  printf("%d! = %d\n", a);
+}
+int factor(int x) {
+  NEXT ret = __return;
+  goto factor0(1, x, ret);
+}
+code
+factor0(int prod,int x,NEXT next) {
+  if (x >= 1) {
+    goto factor0(prod*x, x-1, next);
+  } else {
+    goto (*next)(prod);
+  }
+}
+

環境付き継続の使用例

__retunrで表される特殊なコードセグメント
コードセグメントからは通常のコードセグメントポインタに見える
この__returnに継続すると、元の関数の環境にリターン

+ +

Second: Cとの相互利用

どのように実装する？

setjmp()/longjmp()を使って実装可能 +
- Cの標準ライブラリの関数
- しかし余計な環境も保持するためオーバヘッドが大きい
- 継続の際に渡す引数が一つ増えてしまう
内部関数 +
- GCCの独自拡張
- 関数内に関数を定義可能
- 内部関数から外の関数のラベルにgotoできる

内部関数が使いやすい

+ +

Second: Cとの相互利用

具体的には

__returnが参照された場合にGCCが自動で内部関数を定義する
内部関数の中からは外の関数にgotoして脱出

int factor(int x) {
+   int retval;
+
+   code __return(int val) {
+      retval = val;
+      goto label;
+   }
+   if (0) {
+     label:
+      return retval;
+   }
+
+   NEXT ret = __return;
+   goto factor0(1, x, ret);
+}

+ +

Second: Cとの相互利用・評価

この取り組みにより

これにより、C with Continuation の仕様を満たした
ソースコードレベルで、Cと相互に利用することが可能になった

+ +

Third: メンテナンス性の向上

GCCのアップデートリリースは早い

リリースだけで年に5回のペース
その度にバグの修正やコードの改善が入る
問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること

このリリースに追従して差分をアップデートしたい

GCC本家にマージしてもらうのが一番良いが難しい

+ +

Third: メンテナンス性の向上

二つのリポジトリ管理

本家のリリースをそのままコミットするリポジトリ GCC_copy
CbCの修正が加えられたリポジトリ CbCGCC
Mercurialによる分散リポジトリ管理
CbCGCC は GCC_copyをクローン（ブランチ）して作成する

+ + +

Third: メンテナンス性の向上

アップデート手順

GCC-copyリポジトリにて +
1. GCC-copyリポジトリのファイルをすべて消す
2. GCCの最新バージョンをリポジトリ内に展開
3. 追加ファイル、削除ファイルを確認
4. コミット、タグ付け
CbCGCCリポジトリにて +
1. GCC-copyからpull.
2. hg mergeでマージ実行
3. 衝突があればソースコードをを修正
4. ビルドテスト
5. コミット、タグ付け

+ +

Third: メンテナンス性の向上・比較

これまでのアップデートは

GCCの新旧の差分、CbCの差分
複雑なdiffをとる必要がある

新しい管理方法により

「3.衝突があればソースコードを修正」以外は機械的に実行可能
内部の設計が変わったなど、重要な変更点にだけ集中できる
分散管理にしたことで、移行用バージョンを分けることが可能になる

+ +

まとめ

本研究での取り組み

First

CbCGCCにて実用レベルのCbCプログラムが動作可能となった +

軽量継続における引数順序の制限を取り除いた
PowerPCでの間接継続の制限を取り除いた
x86アーキテクチャにて高速化を行った

Second

Cとの相互利用性の向上

Third

ソースコードメンテナンス性の向上

+ +

まとめ

本研究での成果

成果1

CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった +

成果2

CbCが多数のアーキテクチャに対応 +

20以上のアーキテクチャ
特に64bitのx86, SPUがうれしい

成果3

CbCの高速化 +

x86においてもmicro-cと互角の速度を達成
PowerPCでは2倍の速度

成果4

メンテナンス性が向上

+ +

今後の課題

Real-time、組込み向けに実用的なCbCプログラムの例題
タブロー方を用いた検証
TaskManagerのCbC実装

CbC言語の今後

オブジェクティブなCbCの設計
データセグメントの導入
スケジューラのためのリフレクション

+ + +

おわり

ありがとうございました

+ + + + + + + + @@ -733,203 +1931,27 @@ - -

継続とはなんなのか？

継続

現在の処理を続行するための情報 -
- Cならば続く命令のアドレスや
- 命令に必要な値、
- スタックなど、その環境全てを含む
-

CbCでの軽量継続

継続からスタックに関する情報を落とす
続く命令とデータのみのシンプルな継続
命令はコードセグメント、引数はインタフェイスと呼ばれる

- -

コードセグメントと軽量継続の記述

-typedef code (*NEXT)(int);
-int main(int argc, char **argv) {
-  int i;
-  i = atoi(argv[1]);
-  goto factor(i, print_fact);
-}
-code factor(int x, NEXT next) {
-  goto factor0(1, x, next);
-}
-code factor0(int prod,int x,NEXT next) {
-  if (x >= 1) {
-    goto factor0(prod*x, x-1, next);
-  } else {
-    goto (*next)(prod);
-  }
-}
-code print_fact(int value) {
-  printf("factorial = %d\n", value);
-  exit(0);
-}

実際のプログラム記述は？

コードセグメント定義 -
- codeキーワードで宣言
- 書式は関数と同じ
-
軽量継続制御 -
- gotoキーワードと引数
- コードセグメントの最初に飛ぶ
- コードセグメントポインタによる間接継続も可能
-

Cとの比較について

quicksort例題をCと比較すると

CbCとCの比較に関して

現在のところ、遅くなる
問題はquicksortという例題では必ずスタックが必要だということ
例題ではスタックを自前の構造体で用意している
そのため、ハードウェアで考慮されたスタックよりは遅い
状態遷移ベースの例題を作りたい
まだ例題を用意していない
quicksortはスタックが必要となるため、Cに有利
この例題ではプログラム上自前でスタックを用意している
このメモリへのアクセスはスタックより重い
Cとの比較には状態遷移ベースの例題があった方が良い

fastcall

実際の出力アセンブラ

fastcallにした場合

current:
-    subl    $12, %esp
-    movl    $30, 16(%esp)
-    movl    $20, %edx
-    movl    $10, %ecx
-    addl    $12, %esp
-    jmp     next
-

normalcallの場合

current:
-    pushl   %ebp
-    movl    %esp, %ebp
-    movl    $30, 16(%ebp)
-    movl    $20, 12(%ebp)
-    movl    $10, 8(%ebp)
-    leave
-    jmp     next
-

-
-

命令数ではほとんど変化はない
引数2つがレジスタecxとedxに格納されるようになった
そのためメモリアクセスが減る
これで高速化されるはず

+ + + -

First: 性能評価（サイズ比較）

ファイルサイズの比較

組み込み系ではメモリ使用量が肝心
CbCGCCのサイズ最適化、速度最適化も対象とする
デバグ情報を付加しない、strip後のファイルサイズを比較

結果

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

	CbCGCC 速度最適化	CbCGCC サイズ最適化	micro-c
x86/OS X	9176	9176	9172
x86/Linux	5752	5752	5796
ppc/OS X	8576	8576	12664
ppc/Linux	10068	10068	9876
ppc/PS3	6960	6728	8636

結果考察

x86ではファイルサイズの差がない
ppcではOSによって違うが、OS Xでは3分の2に抑えることができている
サイズ最適化は必要ない、速度最適化で充分

+ -

並列代入

ある条件で末尾呼出が行われなくなる

~~呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合~~ 解決済み
引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合

問題となる例

code somesegment(int a, int b, int c) {
-  /∗ do something ∗/
-  goto nextsegment(b, c, a);
-}
-

(a,b,c) = (b,c,a)と本質的に同じ。これが並列代入
a=b,b=c,c=aではだめ。aの値が失われる
必ず一つ(1ワード)以上の一時変数が必要になる

次の様に構文木を変更する

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);
-}
-

これにより、引数順序を考える必要はなくなる
代わりに、メモリアクセスが大量に発生
しかし、これはGCCの最適化で除去される

+ +