Mercurial > hg > Papers > 2011 > nobu-prosym
view presen/index.html @ 63:3cc4a8603489
modify explanation of TCE
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 28 Dec 2011 04:53:23 +0900 |
parents | 7087484574b0 |
children | 743afe406e56 |
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> .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;"> <img class="scale" src="./pix/cs_stack.png" style="height: 7em;"> </p> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation based C </h1> <small> <table width=100% > <tr> <caption>階乗を求めるCbCのプログラム</caption> <td width=50%> <pre> __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> __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>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> <small> <pre> 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> <small> <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li> <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> <li>最後に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>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> <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li> <img src="./pix/continuation.png" style="height: 7em;"> <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE</h1> <li>TCEにより関数へjmp命令で処理を移すことを利用。</li> <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li> <br> <h2>具体的な実装内容</h2> <ul> <li class="incremental">try_tail_call(変数名)フラグを立てる。</li> <li class="incremental">try_tail_callフラグを落とさせない。</li> </ul> <li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE</h1> <li>try_tail_callフラグはexpand_call関数で落とされる。</li> <ul> <li>expand_call関数</li> <ul> <li>Treeで表された関数からRTLを生成する関数</li> </ul> </ul> <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li> <ul> <li>caller側とcallee側の戻値の型の一致している。</li> <li>関数呼び出しがリターン直前に行われている。</li> <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> <li>引数の並びのコピーに上書きがない。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE</h1> <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li> <ul> <li>void型で統一。</li> <li>gotoの直後にreturnを置く。</li> <li>スタックサイズは固定。</li> <li>引数は一旦、一時変数にコピーする。</li> </ul> <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:環境付き継続</h1> <li>CbCにおけるCとの互換性を保つための機能。</li> <li>コードセグメントを呼び出したCの関数に戻ることができる。</li> <li></li> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:クロージャでの実装について</h1> <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』<br>間違い</li> <li>訂正</li> <ul> <li class="incremental">GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li> <li class="incremental">GCC 4.6 と Lion でのクロージャは特に問題はない。</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続:クロージャでの実装の問題点</h1> <li></li> <li></li> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続: setjmp での実装</h1> <li>setjmp での実装</li> <small> <pre> ({ int a = setjmp(env); int retval; void _cbc_internal_return(int retval_, jmp_buf _envp){ retval = retval_; longjmp(_envp, retval); } if (a) { return retval; } _cbc_internal_return; }) </pre> </small> <li></li> </div> <!-- PAGE --> <div class="slide"> <h1>環境付き継続: setjmp での実装の問題</h1> <li>GCC 内で setjmp を生成する関数を作る必要がある。</li> <li>戻値の型が int </li> <ul> <li>構造体等ポインタの場合使えない。</li> </ul> <li class="incremental">setjmp での実装はあまり実用的ではない。</li> </div> <!-- PAGE --> <div class="slide"> <h1>__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){ : (*print)(n,result,print,exit1, envp); } </pre> </small> </div> <!-- PAGE --> <div class="slide"> <h1>__rectype の実装</h1> <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> <pre> __code factorial(int n, int result, __rectype *print) { : (*print)(n,result,print,exit1, envp); } </pre> </div> <!-- PAGE --> <div class="slide"> <h1></h1> <li></li> </div> <!-- PAGE --> </div> </body> </html>