Mercurial > hg > Papers > 2010 > kent-master
diff probation-slide/final-slide.html @ 13:12cb508ee15d after-organizing
add slides for probation.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 16 Feb 2010 14:48:06 +0900 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/probation-slide/final-slide.html Tue Feb 16 14:48:06 2010 +0900 @@ -0,0 +1,1487 @@ +<?xml version="1.0" encoding="utf-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja"> +<head> + <title>Continuation based C</title> + <meta name="copyright" content="Copyright © 2009 KSL: Yogi KENT" /> + <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> + <meta name="font-size-adjustment" content="1" /> + <link rel="stylesheet" href="slidy.css" + type="text/css" media="screen, projection, print" /> + <link rel="stylesheet" href="final-slide.css" + type="text/css" media="screen" /> + <!--link rel="stylesheet" href="../Slidy/w3c-blue2.css" + type="text/css" media="screen, projection, print" /--> + <style type="text/css"> + .right { + float: right; + width: 40%; + } + .left { + float: left; + width: 40%; + } + div.slide { + vertical-align: middle; + } + div.top h1 { + width: 70%; + padding: 0 1em 0; + text-align: center; + } + #frame { + position: fixed; + left: -1px; + top: -1px; + width: 800px; + height: 600px; + border: solid 1px red; + visibility: visible; + } + .speak { + + visibility: hidden; + + font-size: 80%; + line-height: 1.0; + position: fixed; + right: 0.5em; + bottom: 1.5em; + max-width: 60%; + background-color: green; + opacity: 0.90; + color: black; + -moz-border-radius: 8px; + -webkit-border-radius: 8px; + } + ul.narrow li { + margin-right: 0; + } + table { + border-collapse: collapse; + border: solid 1px black; + } + table td { + border: solid 1px black; + } + table th { + text-align: center; + border: solid 1px black; + } + </style> + <script src="slidy.js" + charset="utf-8" type="text/javascript"> + </script> + <script type="text/javascript"> + sizes = new Array("14pt", "15pt", "16pt", "17pt", "18pt", "19pt", "20pt", "21pt", "22pt","23pt", "24pt", "26pt", "28pt", "30pt", "32pt"); + sizeIndex = 1; + mouseClickEnabled = false; + </script> +</head> +<body> +<!-- this defines the slide background --> +<div id="frame"></div> + +<div class="background"> + <div class="header"> + <!-- sized and colored via CSS --> + </div> + + <!--img id="head-icon" alt="graphic with four colored squares" + src="../Slidy/icon-blue.png" /--> + + <div class="footer"> + <object id="w3c-logo" data="kent-logo2.svg" type="image/svg+xml" title="KENT logo"> + <a href="http://www.w3.org/"> + <img alt="W3C logo" id="w3c-logo-fallback" src="kent-logo2.png" /> + </a> + </object> + + <!-- modify the following text as appropriate --> + 組み込み向け言語CbCのGCC上の実装 <span style="font-size:70%;">http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html</span><br /> + <!--Event, Location, Month Year--> + </div> +</div> + +<div class="slide top"> + <h1>組み込み向け言語Continuation based CのGCC上の実装</h1> + <p> + 与儀健人 (並列信頼研究室) + <<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>> + </p> + <!--img src="../Slidy/keys.jpg" class="cover" + alt="W3C as letters on 3 plastic buttons from a keyboard" /--> + <!--h2>ゼミ, 河野研, Sep, 2009</h2--> +</div> + +<div class="slide"> + <h1>研究の背景</h1> + <ul> + <li>ソフトウェアは今も大規模・複雑化が続いている</li> + <li>しかし、ソフトウェアのバグを発見するのは難しい</li> + <li style="marker:none;"/> + <li>組込みやReal-time処理の需要も増大してる</li> + <li>高速な応答が要求される組込み処理にはハードウェアに近い言語が適している</li> + </ul> + <p class="subtitle">なにが問題を複雑にしているのか?</p> + <ul> + <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li> + <li>現存する記述言語は状態遷移の記述に向いていない</li> + <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li> + </ul> +</div> + +<div class="slide" style="font-size:95%"> + <h1>研究目的</h1> + <p class="subtitle"> + 状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する + </p> + <ul> + <li>組込み、通信プロトコル、Real-time処理などの記述に向いている</li> + <li>状態遷移を直接記述するため、タブロー法での検証に有利</li> + <li>関数より細かく、ステートメントより大きい処理単位</li> + <li>細かい単位でソースコードレベルの最適化を可能にする</li> + </ul> + <p class="subtitle">条件</p> + <ul> + <li>既存のソフトウェアは膨大であり、無駄にはできない</li> + <li>互換性が必須条件</li> + <li>Cからの変換、Cへの変換ができる事が望ましい</li> + </ul> +</div> + +<div class="slide"> + <h1>Continuation based Cの提案</h1> + <p class="subtitle">継続を基本とする記述言語CbC</p> + <ul> + <li>環境を保持しない継続、<dfn>軽量継続</dfn>を導入</li> + <li>軽量継続で<em class="weak">状態遷移が明確</em>になる</li> + <li>関数の代わりとなる処理単位<dfn>コードセグメント</dfn></li> + <li>関数 > コードセグメント > ステートメント</li> + <li>for, whileなどのループも軽量継続で実現できる</li> + <li>Cとの相互利用のための構文<dfn>環境付き継続</dfn> + <ul> + <li>このCとの相互利用可能なCbCは<em>C with Continuation</em>と呼ばれる</li> + </ul> + </li> + </ul> + <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%"> +<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> + + + + + + + + + + + + + + + + + + + + +<div class="slide"> + <h1>Continuation based C</h1> + <ul> + <li>言語仕様</li> + <li>return-callから軽量継続へ</li> + <li>コードセグメント</li> + <li>状態遷移に適した言語</li> + <li>Cとの互換性</li> + </ul> +</div> + + +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> + +<div class="slide"> + <h1></h1> + <p class="subtitle"></p> + <ul> + <li></li> + <li></li> + </ul> +</div> + + +<div class="slide"> + <h1>First: PowerPCでの間接継続</h1> + <p class="subtitle"></p> + <ul> + <li></li> + </ul> + <p class="subtitle"></p> + <div style="width:70%;margin:1em auto 0;"> +<pre><code> +</code></pre> + </div> +</div> + +<div class="slide"> + <h1>継続制御での並列代入</h1> + <p class="subtitle" style="margin:0 1em 0.1em;"> + 本当に最適化で余分なコードが消えるのか? + </p> + <div style="width:45%;float:left;margin-left:1em;"> + 最適化しない場合 +<pre style="margin-top:0"><code> _test: + stwu r1,-64(r1) + mr r30,r1 + stw r3,88(r30) + stw r4,92(r30) + stw r5,96(r30) + lwz r0,92(r30) + stw r0,32(r30) + lwz r0,96(r30) + addic r0,r0,1 + stw r0,28(r30) + lwz r0,88(r30) + stw r0,24(r30) + lwz r3,32(r30) + lwz r4,28(r30) + lwz r5,24(r30) + addi r1,r30,64 + lwz r30,-8(r1) + lwz r31,-4(r1) + b L_next$stub +</code></pre> + </div> + <div style="width:45%;float:right;margin-right:1em;"> + 最適化した場合 +<pre><code> +_test: + mr r0,r3 + mr r3,r4 + mr r4,r5 + mr r5,r0 + b L_next$stub +</code></pre> + </div> + <div style="width:50%;float:right"> + <ul> + <li>r3:=a, r4:=b, r5:=c</li> + <li>最適化しないとload, storeが満載</li> + <li>最適化すると無駄なload, store命令が消えている</li> + <li>実際はr0を使って4命令で入れ替えられる!</li> + </ul> + </div> +</div> + +<div class="slide"> + <h1>Cとの比較について</h1> + <p class="subtitle">quicksort例題をCと比較すると</p> + <ul> + <li>現在のところ、遅くなる</li> + <li>問題はquicksortという例題では必ずスタックが必要だということ</li> + <li>例題ではスタックを自前の構造体で用意している</li> + <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li> + <li>状態遷移ベースの例題を作りたい</li> + </ul> +</div> + + +<div class="slide"> + <h1>TODO</h1> + <p class="subtitle"></p> + <ul> + <li>並列代入</li> + <li>PowerPC間接継続</li> + <li>評価結果・表</li> + <li>バックエンド</li> + <li></li> + </ul> +</div> + + +</body> +</html> +