Mercurial > hg > Papers > 2011 > nobu-prosym
view presen/index.html @ 71:64d22e65489c
modify TCE
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 02 Jan 2012 05:34:11 +0900 |
parents | 79894ca66a9a |
children | 48de60dd51d1 |
line wrap: on
line source
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <style type="text/css"> tr.srctr { font-size:28px; } td.srctd { height:20em; } pre.srcbox { height: 100%; overflow: scroll; } .src{ overflow: scroll; width: 90%; height: 60%; } .center { margin-left: auto; margin-right: auto; text-align: center; } .textcenter { text-align: center; } .taninaritop { margin: auto; width: 95%; font-weight: bold; } </style> <title>2012/ 1/ 7</title> <!-- metadata --> <meta name="generator" content="S5" /> <meta name="version" content="S5 1.1" /> <meta name="presdate" content="20120107" /> <meta name="author" content="Nobuyasu Oshiro" /> <meta name="company" content="University of the Ryukyu" /> <!-- meta temporary --> <meta http-equiv="content-type" content="text/html; charset=utf-8" /> <meta http-equiv="Content-Script-Type" content="text/javascript" /> <meta http-equiv="Content-Style-Type" content="text/css" /> <!-- configuration parameters --> <meta name="defaultView" content="slideshow" /> <meta name="controlVis" content="hidden" /> <!-- configuration extensions --> <meta name="tranSitions" content="true" /> <meta name="fadeDuration" content="500" /> <meta name="incrDuration" content="250" /> <!-- configuration autoplay extension --> <meta name="autoMatic" content="false" /> <meta name="playLoop" content="true" /> <meta name="playDelay" content="10" /> <!-- configuration audio extension --> <meta name="audioSupport" content="false" /> <meta name="audioVolume" content="100" /> <meta name="audioError" content="false" /> <!-- configuration audio debug --> <meta name="audioDebug" content="false" /> <!-- style sheet links --> <link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" /> <link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" /> <link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" /> <link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" /> <!-- embedded styles --> <style type="text/css" media="all"> .imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;} #anim {width: 33%; height: 320px; position: relative;} #anim img {position: absolute; top: 0px; left: 0px;} </style> <!-- S5 JS --> <script src="ui/default_utf/slides.js" type="text/javascript"></script> </head> <body> <div class="layout"> <div id="controls"><!-- DO NOT EDIT --></div> <div id="currentSlide"><!-- DO NOT EDIT --></div> <div id="header"></div> <div id="footer"> <h1>プログラミングシンポジウム: 2012/ 1/ 7</h1> <h2>並列信頼研</h2> </div> </div> <div class="presentation"> <div class="slide"> <h1>Continuation based Cの GCC 4.6 上の実装について</li> <h3></h3> <li>大城 信康</li> <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4> <div class="handout"></div> </div> <!-- PAGE --> <div class="slide"> <h1>目的と背景(1)</h1> <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li> </div> <!-- PAGE --> <div class="slide"> <h1>目的と背景(2)</h1> <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li> <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> </div> <!-- PAGE --> <div class="slide"> <h1>発表内容</h1> <ol> <li>CbC の紹介</li> <li>GCC でのコンパイルの流れ</li> <font color="red"> <li>CbC の実装</li> </font> <!-- <ul> <li>Tail Call Elimination</li> <li>goto シンタックスの追加</li> <li>環境付き継続</li> </ul> --> <li>Micro-C との性能比較</li> <!-- <li>mercurial を用いたアップデートの方法</li> --> <li>まとめ</li> <ol> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation based C </h1> <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> <ul> <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li> </ul> <br> <h2>コードセグメント</h2> <ul> <li>C の関数よりも細かい単位。</li> <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation Based C</h1> <h2>継続:現在の処理を実行していく為の情報</h2> <!-- <li>Cでは関数呼び出しの後、呼び出し元の環境に復帰する必要がある。</li> --> <li>Cにおいての継続</li> <ul> <li>続く命令のアドレス</li> <li>命令に必要なデータ</li> <li>スタックに積まれている値(環境)</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation Based C (軽量継続)</h1> <h2>CbCの継続(軽量継続)</h2> <li>関数コールが無い -> 呼び出し元への復帰がない</li> <ul> <li>Cの継続から環境を除外</li> <li>続く命令とその命令に必要なデータのみ</li> </ul> <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> --> <!-- <li>スタックポインタの位置を変えずにすむ。</li> --> <p style=" margin-right:auto; margin-left:auto;"> <table width=90% class="center" border=1> <tr> <td><small>Cの関数呼び出し</small></td> <td><small>CbCの継続</></small></td> </tr> <tr> <td> <img class="scale" src="./pix/func_call.png" style="height: 6em;"> </td> <td> <img class="scale" src="./pix/cs_stack.png" style="height: 6em;"> </td> </tr> </table> </p> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation based C </h1> <small> <table width=100% border=1> <caption>階乗を求めるCbCのプログラム</caption> <tr class="srctr"> <td width=50%> <pre class="srcbox"> __code print_factorial(int prod) { printf("factorial = %d\n",prod); exit(0); } __code factorial0(int prod, int x) { if ( x >= 1) { goto factorial0(prod*x, x-1); }else{ goto print_factorial(prod); } } </pre> </td> <td> <pre class="srcbox"> __code factorial(int x) { goto factorial0(1, x); } int main(int argc, char **argv) { int i; i = atoi(argv[1]); goto factorial(i); return 0; } </pre> </td> </tr> </table> </small> <li>__code キーワードによるコードセグメントの宣言</li> <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li> </div> <!-- PAGE --> <div class="slide"> <h1>GCC</h1> <li>本来はGnu Compiler Collectionのことを指すが、 <br>ここで扱うのはGnu C Compiler(cc1)になる。</li> <ul> <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコード次の4つの内部表現へと変換される。</li> </ul> <!-- <li>GCCでは、アセンブラのコードを出力するまでに次の4つの内部表現が扱われる。</li> <ol> <li>Generic Tree</li> <li>GIMPLE</li> <li>Tree SSA</li> <li>RTL</li> </ol> --> </div> <!-- PAGE --> <div class="slide"> <h1>GCC</h1> <ol> <li>Generic Tree:ソースコードを構文木の形に直したもの</li> <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li> <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li> <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li> </ol> <li class="incremental">それぞれは次のようなデータを構文木にして持っている。</li> </div> <!-- PAGE --> <div class="slide"> <h1>GCC</h1> <table width=100% border=1> <tr> <td>Generic(ソースコード)</td> <td>GIMPLE</td> </tr> <tr class="srctr"> <td> <pre class="srcbox"> void factorial(int x) { int prod,i; for(i=1,prod=1; i <= x; i++){ prod = prod*i; } print_factorial(prod); } </pre> </td> <td width=50%> <pre class="srcbox"> factorial (int x) { int prod; int i; i = 1; prod = 1; goto <D.2846>; <D.2845>: prod = prod * i; i = i + 1; <D.2846>: if (i <= x) goto <D.2845>; else goto <D.2847>; <D.2847>: print_factorial (prod); } </pre> </td> </tr> </table> </div> <!-- PAGE --> <div class="slide"> <h1>GCC</h1> <table border=1 width=100% height=100%> <tr> <td width=50%>SSA</td> <td width=50%>RTL</td> </tr> <tr class="srctr"> <td class="srctd"> <pre class="srcbox"> factorial (int x) { int i; int prod; <bb 2>: i_3 = 1; prod_4 = 1; goto <bb 4>; <bb 3>: prod_6 = prod_1 * i_2; i_7 = i_2 + 1; <bb 4>: # prod_1 = PHI <prod_4(2), prod_6(3)> # i_2 = PHI <i_3(2), i_7(3)> if (i_2 <= x_5(D)) goto <bb 3>; else goto <bb 5>; <bb 5>: print_factorial (prod_1); return; } </pre> </td> <td class="srctd"> <pre class="srcbox" style="width:25em;"> (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403] <function_decl 0x146f6b200 print_factorial>) [0 S1 A8]) (const_int 0 [0])) </pre> </td> </tr> </table> </div> <!-- PAGE --> <div class="slide"> <h1>GCC</h1> <p class="center"> <img src="./pix/ir.png" style="height: 6em;"> </p> <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li> <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li> </div> <!-- PAGE --> <div class="slide"> <h1>GCC:Generic Tree</h1> <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li> <table class="center" width=100% border=1> <tr> <td></td> <td><small>値の代入:MODIFY_EXPR</small></td> <td><small>関数呼び出し:CALL_EXPR</small></td> </t> <tr> <td>命令</td> <td>b = a * 10</td> <td>func(a,10)</td> </t> <tr> <td><small>Generic<br>Tree</small></td> <td> <img src="./pix/MODIFY_EXPR.png" style="height: 6em;"> </td> <td> <img src="./pix/CALL_EXPR.png" style="height: 7em;"> </td> </tr> </table> <p class="center"><small>Generic Treeでの表現</small></p> </div> <!-- PAGE --> <div class="slide"> <h1>GCC:Generic Tree</h1> <li>それぞれの命令はSTATEMENT_LISTでまとめて保持される。</li> <table width=100% border=1> <tr> <td class="center"><small>ソースコード</small></td> <td class="center"><small>Generic Treeでの表現</small></td> </tr> <tr> <td> <small> <pre> int main() { int a, b; a = 3; b = func(a, 10); return b; } </pre> </small> </td> <td> <p class="center"> <img src="./pix/STATEMENT_LIST.png" style="height: 6em;"> </p> </td> </tr> </table> <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li> </div> <!-- PAGE --> <!-- <div class="slide"> <h1>GCC</h1> <li>GCC についての簡単な説明を行う...</li> <li>TODO: NEXT_PASS() の把握</li> <img src="./pix/ir.png" style="height: 6em;"> <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li> </div> --> <!-- PAGE --> <div class="slide"> <h1>CbCの実装</h1> <ul> <li>シンタックスの追加</li> <li>レジスタによる引数渡し(fastcall属性の付与)</li> <li>Tail Call Elimination</li> <li>環境付き継続</li> <li>__rectype の実装</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:シンタックスの追加</h1> <ul> <li>__code キーワードでのコードセグメントの宣言</li> <ul> <li>__code 用idとkeywordを作成。</li> <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> </ul> <li>goto によるコードセグメントへの継続</li> <ul> <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> </ul> </ul> <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:シンタックスの追加</h1> <h2>gotoシンタックスの追加</h2> <pre class="srcbox" style="font-size:25px; height:20em;"> case RID_GOTO: c_parser_consume_token (parser); if ( c_parser_next_token_is (parser, CPP_NAME) && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) { stmt = c_finish_goto_label (loc, c_parser_peek_token (parser)->value); c_parser_consume_token (parser); } else if (c_parser_next_token_is (parser, CPP_MULT)) { tree val; c_parser_consume_token (parser); val = c_parser_expression (parser).value; mark_exp_read (val); stmt = c_finish_goto_ptr (loc, val); } else expr = c_parser_expr_no_commas (parser, NULL); if (TREE_CODE(expr.value) == CALL_EXPR ) { location_t loc = c_parser_peek_token (parser)->location; cbc_replace_arguments (loc, expr.value); TREE_TYPE(expr.value) = void_type_node; CbC_IS_CbC_GOTO (expr.value) = 1; CALL_EXPR_TAILCALL (expr.value) = 1; add_stmt(expr.value); stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); } </pre> <small> <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li> </small> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:シンタックスの追加</h1> <h2>gotoシンタックスの追加</h2> <li>最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。</li> <table border=1 width=100%> <tr class="center"> <small> <td>実際のコード </td> <td>GCC 内で処理されるコード</td> </small> </tr> <tr style="margin-top: auto;"> <td> <pre> goto factorial0(1, x); </pre> </td> <td> <pre> factorial0(1, x); return; </pre> </td> </tr> </table> <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:引数渡し</h1> <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> <ul> <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> </ul> <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:引数渡し(fastcall)</h1> <h2>fastcall</h2> <ul> <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li> </ul> <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li> <small> <pre> if(!TARGET_64BIT) { attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); declspecs_add_attrs(specs, attrs); } </pre> </small> <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:引数渡し</h1> <table width=100% border=1 class="center"> <caption>引数渡しに使われるレジスタの数(gcc)</caption> <tr> <td>arch</td> <td>int(整数型)</td> <td>float(浮動小数点型)</td> <td>double(浮動小数点型)</td> </tr> <tr> <td>i386</td> <td>2</td> <td>0<br>(stackを使用)</td> <td>0<br>(stackを使用)</td> </tr> <tr> <td>x86_64</td> <td>6</td> <td>8</td> <td>8</td> </tr> </table> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)</h1> <h2>Tail Call Elimination(TCE):末尾除去</h2> <ul> <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li> </ul> <li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li> <br> <table width=100%> <tr class="srctr"> <td width=50%> <pre class="srcbox"> int main() { int num = a(2); printf("main:num=%d\n",num); return 0; } int a(int num) { return b(num+5); } int b(int num) { printf("b:a = %d\n",num); return num+3; } </pre> </td> <td class="center"> <img src="./pix/continuation.png" style="height:100%;"> </td> </tr> </table> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)の動作</h1> <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li> <table width=100% border=1> <td> <p class="center"> <img src="./pix/tce.png" style="height: 6em;"> </p> </td> <td> <ul> <li><small>func_bの引数はfunc_aのスタックに上書する</small></li> <li><small>func_bの為にスタックポインタは伸ばされない</small></li> </ul> </td> </table> <li class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> <li class="incremental">TCEにかかるには条件が幾つかある。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)</h1> <li>TCEにかかる条件</li> <ol> <li>caller側とcallee側の戻値の型の一致している。</li> <li>関数呼び出しがリターン直前に行われている。</li> <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> <li>引数の並びのコピーに上書きがない。</li> </ol> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)</h1> <li>条件を回避する為以下の実装にする。</li> <ol> <li>型はvoid型で統一する。</li> <li>gotoの直後にreturnを置く。</li> <li>スタックサイズは固定する。</li> <li>引数は一旦、一時変数にコピーする。</li> </ol> </small> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)</h1> <li>TCEの条件はexpand_call関数で調べられる。</li> <ul> <li>Treeで表された関数からRTLを生成する関数</li> <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li> </ul> <li>具体的な実装</li> <ul> <li>try_tail_callフラグを落とさせない処理が追加されている。</li> </ul> </div> <!-- PAGE --> <!-- <div class="slide"> <h1>CbCの実装:TCE</h1> <li>TCEにかかる条件</li> <ul> <li>try_tail_callフラグを落とさせない。</li> </ul> <li></li> </div> --> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE(末尾除去)</h1> <li>try_tail_callフラグが落とされるif文</li> <pre class="srcbox"> if (currently_expanding_call++ != 0 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) && !flag_optimize_sibling_calls) || args_size.var || dbg_cnt (tail_call) == false) try_tail_call = 0; </pre> </div> <!-- PAGE --> <div class="slide"> <li>try_tail_callフラグが落とされる部分</li> <table> <tr class="srctr"> <td class="srctd"> <pre class="srcbox"> if ( #ifdef HAVE_sibcall_epilogue !HAVE_sibcall_epilogue #else 1 #endif || !try_tail_call || structure_value_addr != NULL_RTX #ifdef REG_PARM_STACK_SPACE || (OUTGOING_REG_PARM_STACK_SPACE (funtype) != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))) || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl)) #endif || !targetm.function_ok_for_sibcall (fndecl, exp) || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))) || (fndecl && decl_function_context (fndecl) == current_function_decl) || args_size.constant > (crtl->args.size - crtl->args.pretend_args_size) || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) != targetm.calls.return_pops_args (current_function_decl, TREE_TYPE (current_function_decl), crtl->args.size)) || !lang_hooks.decls.ok_for_sibcall (fndecl)) try_tail_call = 0; </pre> </td> </tr> </table> </div> <!-- PAGE --> <!-- <div class="slide"> <h1>CbCの実装:環境付き継続</h1> <li>CbCにおけるCとの互換性を保つための機能。</li> <li>コードセグメントを呼び出したCの関数に戻ることができる。</li> <li>論文における訂正</li> <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li> <ul> <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li> <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li> </ul> </div> --> <!-- PAGE --> <!-- <div class="slide"> <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1> <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br> とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p> </div> --> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:環境付き継続</h1> <ul> <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> <li>__returnキーワードを引数に渡すことで使うことができる。</li> </ul> <li>以下の使い方の場合は1を返す。</li> <table border=1 width=100%> <td> <small> <pre class="srcbox"> __code c1(__code ret(int,void *),void *env) { goto ret(1,env); } int main() { goto c1(__return, __environment); } </pre> </small> </td> </table> <p><small>__environmentキーワードは関数の環境を保持する。</small></p> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:環境付き継続</h1> <h2>実際には以下のコードを生成している。</h2> <small> <pre class="srcbox"> goto c1(__return, __environment); goto c1(({ __label__ _cbc_exit0; static int retval; void _cbc_internal_return(int retval_, void *_envp) { retval = retval_; goto _cbc_exit0; } if (0) { _cbc_exit0: return retval; } _cbc_internal_return; }), __environment); </pre> <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> </small> <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> </div> <!-- PAGE --> <!-- <div class="slide"> <h1>CbCの実装:環境付き継続</l> <h2>環境付き継続の生成部分:</h2> <div class="src"> <small> <pre> { tree value, stmt, label, tlab, decl; c_parser_consume_token (parser); stmt = c_begin_stmt_expr (); cbc_return_f = c_parser_peek_token (parser)->value; location_t location = c_parser_peek_token (parser)->location; /* create label. (__label__ _cbc_exit0;) */ label = get_identifier ("_cbc_exit0"); tlab = declare_label (label); C_DECLARED_LABEL_FLAG (tlab) = 1; add_stmt (build_stmt (location, DECL_EXPR, tlab)); /* declare retval. (int retval;) */ tree decl_cond = build_decl (location, VAR_DECL, get_identifier ("retval"), TREE_TYPE (TREE_TYPE (current_function_decl))); TREE_STATIC (decl_cond) = 1; TREE_USED (decl_cond) = 1; /* Use thread-local */ DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond); DECL_NONLOCAL (decl_cond) = 1; add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond))); /* define nested function. */ decl = cbc_finish_nested_function (location, label, decl_cond); TREE_USED(decl) = 1; /* define if-ed goto label and return statement. */ cbc_finish_labeled_goto (location, label, decl_cond); /* get pointer to nested function. */ value = build_addr (decl , current_function_decl); TREE_USED (current_function_decl) = 1; SET_EXPR_LOCATION (value, location); add_stmt (value); TREE_SIDE_EFFECTS (stmt) = 1; expr.value = c_finish_stmt_expr (location, stmt); expr.original_code = ERROR_MARK; } </pre> </small> </div> </div> --> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:環境付き継続</h1> <h2>作成されるTree</h2> <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;"> <!-- <small> <pre> ({ __label__ _cbc_exit0; static int retval; void _cbc_internal_return(int retval_, void *_envp){ retval = retval_; goto _cbc_exit0; } if (0) { _cbc_exit0: return retval; } _cbc_internal_return; }), </pre> </small> --> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:実装の問題</h1> <ul> <li>リターンするretval変数が重要になってくる。</li> <li>retval変数のデータをどうやって確保するか。</li> </ul> <li>次の方法が考えられる。</li> <ul> <li>クロージャでの確保</li> <li>staticでの確保</li> <li>static thread local storage(tls)を用いての確保</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:実装の問題</h1> <li>クロージャでの実装</li> <ul> <li>クロージャにしてスタックに値を確保する。</li> <li></li> </ul> <li>問題点</li> <ul> <li class="incremental">しかしCbCではスタックの値は破棄されていく。</li> <li class="incremental">その為スタックに値を確保するのは好ましくない。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:実装の問題</h1> <li>staticでの実装</li> <ul> <li>静的に値を確保することでスタック破棄の影響を受けない。</li> </ul> <li>問題点</li> <ul> <li class="incremental">マルチスレッドのプログラムに対応できない。</li> <li class="incremental">値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:実装の問題</h1> <li>static tlsでの実装</li> <ul> <li>スレッド毎に静的に値を確保する。</li> </ul> <li>現在はこの方法で実装を行なっている。</li> <li>しかし、最適化にかけると正しい値が返ってこない。 <br>(恐らくTreeの生成の部分が間違っている。)</li> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:その他の実装方法</h1> <ul> <li>setjmpでの実装</li> <ul> <li>setjmpを行うTreeを生成するのが少し手間になる。</li> <li>int型の戻値しか得られない。</li> </ul> <li>戻値を入れるレジスタを明示的に指定する。</li> <ul> <li>まだ実装を試していない。</li> </ul> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの機能の拡張:__rectype の実装</h1> <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> <small> <pre> void factorial(int n, int result, void(*print)()){ : (*print)(n,result,print,exit1, envp); } </pre> </small> <li>以下の様に引数に()をつけて受けてることをやめたい。</li> <small> <pre> void factorial(int n, int result, void *print){ : void(*print)(n,result,print,exit1, envp); } </pre> </small> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの機能の拡張:__rectype の実装</h1> <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> <pre> __code factorial(int n, int result, __rectype *print) { : goto (*print)(n,result,print,exit1, envp); } </pre> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの機能の拡張:selftype</h1> <h2>selftypeの実装</h2> <li>以下の宣言が行えるようにしたい。</li> <small> <pre> typedef sturct node { selftype *left; selftype *right; int num; }*NODE </pre> <p>selftype は struct node を指す。</p> </small> <ul> <li>上記の構文は実装を行う予定である。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>Micro-Cとの比較</h1> <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li> <table width=100% class="center"> <td> <img src="./pix/mac_conv.png"> </td> <td> <img src="./pix/linux_conv.png"> </td> </table> <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 その為に明らかに遅くなっていることが分かる。</li> <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li> </div> <!-- PAGE --> <div class="slide"> <h1></h1> <li></li> </div> <!-- PAGE --> <div class="slide"> <h1>まとめ</h1> <ul> <li>今回GCC版CbCコンパイラのアップデートを行った。</li> <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li> <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li> <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>今後の予定</h1> <ul> <li>CbCを用いたプログラムの作成</li> <ul> <li>CbCによるタスクマネージャの作成</li> </ul> <li>llvmへのCbCの実装</li> </ul> </div> <!-- PAGE --> </div> </body> </html>