Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 68:1399414ea3f6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of Generic Tree
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 29 Dec 2011 16:01:24 +0900
parents 26a3713b2989
children 9dc6013b0559
comparison
equal deleted inserted replaced
67:1bc732d13326 68:1399414ea3f6
164 <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> --> 164 <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> -->
165 <!-- <li>スタックポインタの位置を変えずにすむ。</li> --> 165 <!-- <li>スタックポインタの位置を変えずにすむ。</li> -->
166 <p style=" margin-right:auto; margin-left:auto;"> 166 <p style=" margin-right:auto; margin-left:auto;">
167 <table width=90% class="center" border=1> 167 <table width=90% class="center" border=1>
168 <tr> 168 <tr>
169 <small> 169 <td><small>Cの関数呼び出し</small></td>
170 <td>Cの関数呼び出し</td> 170 <td><small>CbCの継続</></small></td>
171 <td>CbCの継続</td>
172 </small>
173 </tr> 171 </tr>
174 <tr> 172 <tr>
175 <td> 173 <td>
176 <img class="scale" src="./pix/func_call.png" style="height: 6em;"> 174 <img class="scale" src="./pix/func_call.png" style="height: 6em;">
177 </td> 175 </td>
184 </div> 182 </div>
185 <!-- PAGE --> 183 <!-- PAGE -->
186 <div class="slide"> 184 <div class="slide">
187 <h1>Continuation based C </h1> 185 <h1>Continuation based C </h1>
188 <small> 186 <small>
189 <table width=100% > 187 <table width=100% border=1>
190 <tr> 188 <tr>
191 <caption>階乗を求めるCbCのプログラム</caption> 189 <caption>階乗を求めるCbCのプログラム</caption>
192 <td width=50%> 190 <td width=50%>
193 <pre> 191 <pre>
194 __code print_factorial(int prod) { 192 __code print_factorial(int prod) {
225 <li>__code キーワードによるコードセグメントの宣言</li> 223 <li>__code キーワードによるコードセグメントの宣言</li>
226 <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li> 224 <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li>
227 </div> 225 </div>
228 <!-- PAGE --> 226 <!-- PAGE -->
229 <div class="slide"> 227 <div class="slide">
230 <h1>GCC によるコンパイル</h1> 228 <h1>GCC</h1>
229 <li>本来はGnu Compiler Collectionのことを指すが、
230 <br>ここで扱うのはGnu C Compilerになる。</li>
231 <li>GCCでは次の4つの内部表現が扱われる。</li>
232 <ol>
233 <li>Generic Tree</li>
234 <li>GIMPLE</li>
235 <li>Tree SSA</li>
236 <li>RTL</li>
237 </ol>
238 </div>
239 <!-- PAGE -->
240 <div class="slide">
241 <h1>GCC</h1>
242 <li>Generic Tree:ソースコードを構文木の形に直したもの</li>
243 <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li>
244 <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li>
245 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
246 </div>
247 <!-- PAGE -->
248 <div class="slide">
249 <h1>GCC</h1>
250 <li>CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
251 <p class="center">
252 <img src="./pix/ir.png" style="height: 6em;">
253 </p>
254 <li class="incremental">Generic Tree生成部分について触れてみる。</li>
255 </div>
256 <!-- PAGE -->
257 <div class="slide">
258 <h1>GCC:Generic Tree</h1>
259 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
260 <table class="center" width=100% border=1>
261 <tr>
262 <td><small>値の代入:MODIFY_EXPR</small></td>
263 <td><small>関数呼び出し:CALL_EXPR</small></td>
264 </t>
265 <tr>
266 <td>
267 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
268 </td>
269 <td>
270 <img src="./pix/CALL_EXPR.png" style="height: 7em;">
271 </td>
272 </tr>
273 </table>
274 <p class="center"><small>Generic Treeでの表現</small></p>
275 </div>
276 <!-- PAGE -->
277 <div class="slide">
278 <h1>GCC:Generic Tree</h1>
279 <li>それぞれの命令はSTATEMENT_LISTでまとめて保持される。</li>
280 <table width=100% border=1>
281 <tr>
282 <td class="center"><small>ソースコード</small></td>
283 <td class="center"><small>Generic Treeでの表現</small></td>
284 </tr>
285 <tr>
286 <td>
287 <small>
288 <pre>
289 int main() {
290 int a, b;
291 a = 3;
292 b = func(a, 10);
293 return b;
294 }
295 </pre>
296 </small>
297 </td>
298 <td>
299 <p class="center">
300 <img src="./pix/STATEMENT_LIST.png" style="height: 6em;">
301 </p>
302 </td>
303 </tr>
304 </table>
305 <li>CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
306 </div>
307 <!-- PAGE -->
308 <!--
309 <div class="slide">
310 <h1>GCC</h1>
231 <li>GCC についての簡単な説明を行う...</li> 311 <li>GCC についての簡単な説明を行う...</li>
232 <li>TODO: NEXT_PASS() の把握</li> 312 <li>TODO: NEXT_PASS() の把握</li>
233 <img src="./pix/ir.png" style="height: 6em;"> 313 <img src="./pix/ir.png" style="height: 6em;">
234 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li> 314 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li>
235 </div> 315 </div>
316 -->
236 <!-- PAGE --> 317 <!-- PAGE -->
237 <div class="slide"> 318 <div class="slide">
238 <h1>CbCの実装</h1> 319 <h1>CbCの実装</h1>
239 <ul> 320 <ul>
240 <li>シンタックスの追加</li> 321 <li>シンタックスの追加</li>
279 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); 360 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
280 } 361 }
281 </pre> 362 </pre>
282 </small> 363 </small>
283 <small> 364 <small>
284 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li>
285 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> 365 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
366 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
286 <li>最後にc_finish_return関数によりreturn文を生成している。</li> 367 <li>最後にc_finish_return関数によりreturn文を生成している。</li>
287 </small> 368 </small>
288 </div> 369 </div>
289 <!-- PAGE --> 370 <!-- PAGE -->
290 <div class="slide"> 371 <div class="slide">
317 <!-- PAGE --> 398 <!-- PAGE -->
318 <div class="slide"> 399 <div class="slide">
319 <h1>CbCの実装:引数渡し</h1> 400 <h1>CbCの実装:引数渡し</h1>
320 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> 401 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
321 <ul> 402 <ul>
322 <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> 403 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
323 </ul> 404 </ul>
324 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li> 405 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
325 </div> 406 </div>
326 <!-- PAGE --> 407 <!-- PAGE -->
327 <div class="slide"> 408 <div class="slide">
397 <ul> 478 <ul>
398 <li>Treeで表された関数からRTLを生成する関数</li> 479 <li>Treeで表された関数からRTLを生成する関数</li>
399 </ul> 480 </ul>
400 </ul> 481 </ul>
401 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li> 482 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li>
402 <ul> 483 <small>
484 <ol>
403 <li>caller側とcallee側の戻値の型の一致している。</li> 485 <li>caller側とcallee側の戻値の型の一致している。</li>
404 <li>関数呼び出しがリターン直前に行われている。</li> 486 <li>関数呼び出しがリターン直前に行われている。</li>
405 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> 487 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
406 <li>引数の並びのコピーに上書きがない。</li> 488 <li>引数の並びのコピーに上書きがない。</li>
407 </ul> 489 </ol>
490 </small>
408 </div> 491 </div>
409 <!-- PAGE --> 492 <!-- PAGE -->
410 <div class="slide"> 493 <div class="slide">
411 <h1>CbCの実装:TCE</h1> 494 <h1>CbCの実装:TCE</h1>
412 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li> 495 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li>
413 <ul> 496 <small>
414 <li>void型で統一。</li> 497 <ol>
498 <li>型はvoid型で統一。</li>
415 <li>gotoの直後にreturnを置く。</li> 499 <li>gotoの直後にreturnを置く。</li>
416 <li>スタックサイズは固定。</li> 500 <li>スタックサイズは固定。</li>
417 <li>引数は一旦、一時変数にコピーする。</li> 501 <li>引数は一旦、一時変数にコピーする。</li>
418 </ul> 502 </ol>
503 </small>
419 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li> 504 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li>
420 </div> 505 </div>
421 <!-- PAGE --> 506 <!-- PAGE -->
422 <!-- 507 <!--
423 <div class="slide"> 508 <div class="slide">
464 <h2>実際には以下のコードを生成している。</h2> 549 <h2>実際には以下のコードを生成している。</h2>
465 <small> 550 <small>
466 <pre> 551 <pre>
467 goto c1(__return, __environment); 552 goto c1(__return, __environment);
468 553
469 goto c1( 554 goto c1(({
470 ({
471 __label__ _cbc_exit0; 555 __label__ _cbc_exit0;
472 static int retval; 556 static int retval;
473 void _cbc_internal_return(int retval_, void *_envp){ 557 void _cbc_internal_return(int retval_, void *_envp) {
474 retval = retval_; 558 retval = retval_;
475 goto _cbc_exit0; } 559 goto _cbc_exit0;
476 if (0) { _cbc_exit0: 560 }
477 return retval; } 561 if (0) {
562 _cbc_exit0:
563 return retval;
564 }
478 _cbc_internal_return; 565 _cbc_internal_return;
479 }), 566 }), __environment);
480 __environment);
481 </pre> 567 </pre>
482 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> 568 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p>
483 </small> 569 </small>
484 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> 570 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li>
485 </div> 571 </div>
627 </ul> 713 </ul>
628 </ul> 714 </ul>
629 </div> 715 </div>
630 <!-- PAGE --> 716 <!-- PAGE -->
631 <div class="slide"> 717 <div class="slide">
632 <h1>__rectype の実装</h1> 718 <h1>CbCの機能の拡張:__rectype の実装</h1>
633 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> 719 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
634 <small> 720 <small>
635 <pre> 721 <pre>
636 void factorial(int n, int result, void(*print)()){ 722 void factorial(int n, int result, void(*print)()){
637 : 723 :
649 </pre> 735 </pre>
650 </small> 736 </small>
651 </div> 737 </div>
652 <!-- PAGE --> 738 <!-- PAGE -->
653 <div class="slide"> 739 <div class="slide">
654 <h1>__rectype の実装</h1> 740 <h1>CbCの機能の拡張:__rectype の実装</h1>
655 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> 741 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
656 <pre> 742 <pre>
657 __code factorial(int n, int result, __rectype *print) { 743 __code factorial(int n, int result, __rectype *print) {
658 : 744 :
659 (*print)(n,result,print,exit1, envp); 745 (*print)(n,result,print,exit1, envp);
660 } 746 }
661 </pre> 747 </pre>
662 </div> 748 </div>
663 <!-- PAGE --> 749 <!-- PAGE -->
664 <div class="slide"> 750 <div class="slide">
665 <h1>CbCの機能の拡張</h1> 751 <h1>CbCの機能の拡張:selftype</h1>
666 <h2>selftypeの実装</h2> 752 <h2>selftypeの実装</h2>
667 <li>以下の宣言が行えるようにしたい。</li> 753 <li>以下の宣言が行えるようにしたい。</li>
668 <small> 754 <small>
669 <pre> 755 <pre>
670 typedef sturct node { 756 typedef sturct node {
680 </ul> 766 </ul>
681 </div> 767 </div>
682 <!-- PAGE --> 768 <!-- PAGE -->
683 <div class="slide"> 769 <div class="slide">
684 <h1>Micro-Cとの比較</h1> 770 <h1>Micro-Cとの比較</h1>
685 <li>以下はMicro-C,GCC-4.4とGCC-4.6それぞれのCbCコンパイラでコンパイルしたプログラムの実行結果</li> 771 <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
686 <table width=100% class="center"> 772 <table width=100% class="center">
687 <td> 773 <td>
688 <img src="./pix/mac_conv.png"> 774 <img src="./pix/mac_conv.png">
689 </td> 775 </td>
690 <td> 776 <td>