Mercurial > hg > Papers > 2011 > nobu-prosym
diff presen/index.html @ 68:1399414ea3f6
modify explanation of Generic Tree
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 29 Dec 2011 16:01:24 +0900 (2011-12-29) |
parents | 26a3713b2989 |
children | 9dc6013b0559 |
line wrap: on
line diff
--- a/presen/index.html Thu Dec 29 01:53:43 2011 +0900 +++ b/presen/index.html Thu Dec 29 16:01:24 2011 +0900 @@ -166,10 +166,8 @@ <p style=" margin-right:auto; margin-left:auto;"> <table width=90% class="center" border=1> <tr> - <small> - <td>Cの関数呼び出し</td> - <td>CbCの継続</td> - </small> + <td><small>Cの関数呼び出し</small></td> + <td><small>CbCの継続</></small></td> </tr> <tr> <td> @@ -186,7 +184,7 @@ <div class="slide"> <h1>Continuation based C </h1> <small> -<table width=100% > +<table width=100% border=1> <tr> <caption>階乗を求めるCbCのプログラム</caption> <td width=50%> @@ -227,12 +225,95 @@ </div> <!-- PAGE --> <div class="slide"> - <h1>GCC によるコンパイル</h1> + <h1>GCC</h1> + <li>本来はGnu Compiler Collectionのことを指すが、 + <br>ここで扱うのはGnu C Compilerになる。</li> + <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> + <li>Generic Tree:ソースコードを構文木の形に直したもの</li> + <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li> + <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li> + <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li> + </div> + <!-- PAGE --> + <div class="slide"> + <h1>GCC</h1> + <li>CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li> + <p class="center"> + <img src="./pix/ir.png" style="height: 6em;"> + </p> + <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><small>値の代入:MODIFY_EXPR</small></td> + <td><small>関数呼び出し:CALL_EXPR</small></td> + </t> + <tr> + <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>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> @@ -281,8 +362,8 @@ </pre> </small> <small> - <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li> <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> + <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> <li>最後にc_finish_return関数によりreturn文を生成している。</li> </small> </div> @@ -319,7 +400,7 @@ <h1>CbCの実装:引数渡し</h1> <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> <ul> - <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> + <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> </ul> <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li> </div> @@ -399,23 +480,27 @@ </ul> </ul> <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li> - <ul> + <small> + <ol> <li>caller側とcallee側の戻値の型の一致している。</li> <li>関数呼び出しがリターン直前に行われている。</li> <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> <li>引数の並びのコピーに上書きがない。</li> - </ul> + </ol> + </small> </div> <!-- PAGE --> <div class="slide"> <h1>CbCの実装:TCE</h1> <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li> - <ul> - <li>void型で統一。</li> + <small> + <ol> + <li>型はvoid型で統一。</li> <li>gotoの直後にreturnを置く。</li> <li>スタックサイズは固定。</li> <li>引数は一旦、一時変数にコピーする。</li> - </ul> + </ol> + </small> <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li> </div> <!-- PAGE --> @@ -466,18 +551,19 @@ <pre> goto c1(__return, __environment); -goto c1( - ({ +goto c1(({ __label__ _cbc_exit0; static int retval; - void _cbc_internal_return(int retval_, void *_envp){ + void _cbc_internal_return(int retval_, void *_envp) { retval = retval_; - goto _cbc_exit0; } - if (0) { _cbc_exit0: - return retval; } + goto _cbc_exit0; + } + if (0) { + _cbc_exit0: + return retval; + } _cbc_internal_return; - }), - __environment); + }), __environment); </pre> <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> </small> @@ -629,7 +715,7 @@ </div> <!-- PAGE --> <div class="slide"> - <h1>__rectype の実装</h1> + <h1>CbCの機能の拡張:__rectype の実装</h1> <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> <small> <pre> @@ -651,7 +737,7 @@ </div> <!-- PAGE --> <div class="slide"> - <h1>__rectype の実装</h1> + <h1>CbCの機能の拡張:__rectype の実装</h1> <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> <pre> __code factorial(int n, int result, __rectype *print) { @@ -662,7 +748,7 @@ </div> <!-- PAGE --> <div class="slide"> - <h1>CbCの機能の拡張</h1> + <h1>CbCの機能の拡張:selftype</h1> <h2>selftypeの実装</h2> <li>以下の宣言が行えるようにしたい。</li> <small> @@ -682,7 +768,7 @@ <!-- PAGE --> <div class="slide"> <h1>Micro-Cとの比較</h1> - <li>以下はMicro-C,GCC-4.4とGCC-4.6それぞれのCbCコンパイラでコンパイルしたプログラムの実行結果</li> + <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li> <table width=100% class="center"> <td> <img src="./pix/mac_conv.png">