Mercurial > hg > Papers > 2011 > nobu-prosym
comparison 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 |
comparison
equal
deleted
inserted
replaced
70:79894ca66a9a | 71:64d22e65489c |
---|---|
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> | 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> |
3 | 3 |
4 <html xmlns="http://www.w3.org/1999/xhtml"> | 4 <html xmlns="http://www.w3.org/1999/xhtml"> |
5 | 5 |
6 <head> | 6 <head> |
7 <style> | 7 <style type="text/css"> |
8 td.box { | 8 tr.srctr { |
9 height: 80%; | 9 font-size:28px; |
10 } | |
11 td.srctd { | |
12 height:20em; | |
13 } | |
14 pre.srcbox { | |
15 height: 100%; | |
10 overflow: scroll; | 16 overflow: scroll; |
11 } | |
12 pre.srcbox { | |
13 height: 80%; | |
14 overflow: scroll; | |
15 font-size: 25px; | |
16 } | 17 } |
17 .src{ | 18 .src{ |
18 overflow: scroll; | 19 overflow: scroll; |
19 width: 90%; | 20 width: 90%; |
20 height: 60%; | 21 height: 60%; |
192 <!-- PAGE --> | 193 <!-- PAGE --> |
193 <div class="slide"> | 194 <div class="slide"> |
194 <h1>Continuation based C </h1> | 195 <h1>Continuation based C </h1> |
195 <small> | 196 <small> |
196 <table width=100% border=1> | 197 <table width=100% border=1> |
197 <tr> | |
198 <caption>階乗を求めるCbCのプログラム</caption> | 198 <caption>階乗を求めるCbCのプログラム</caption> |
199 <tr class="srctr"> | |
199 <td width=50%> | 200 <td width=50%> |
200 <pre class="srcbox"> | 201 <pre class="srcbox"> |
201 __code print_factorial(int prod) { | 202 __code print_factorial(int prod) { |
202 printf("factorial = %d\n",prod); | 203 printf("factorial = %d\n",prod); |
203 exit(0); | 204 exit(0); |
267 <table width=100% border=1> | 268 <table width=100% border=1> |
268 <tr> | 269 <tr> |
269 <td>Generic(ソースコード)</td> | 270 <td>Generic(ソースコード)</td> |
270 <td>GIMPLE</td> | 271 <td>GIMPLE</td> |
271 </tr> | 272 </tr> |
272 <tr> | 273 <tr class="srctr"> |
273 <td> | 274 <td> |
274 <small> | 275 <pre class="srcbox"> |
275 <pre class="srcbox" style="height:20em; font-size:25px;"> | |
276 void factorial(int x) | 276 void factorial(int x) |
277 { | 277 { |
278 int prod,i; | 278 int prod,i; |
279 for(i=1,prod=1; i <= x; i++){ | 279 for(i=1,prod=1; i <= x; i++){ |
280 prod = prod*i; | 280 prod = prod*i; |
281 } | 281 } |
282 print_factorial(prod); | 282 print_factorial(prod); |
283 } | 283 } |
284 </pre> | 284 </pre> |
285 </small> | |
286 </td> | 285 </td> |
287 <td> | 286 <td width=50%> |
288 <small> | 287 <pre class="srcbox"> |
289 <pre class="srcbox" style="height:20em; font-size:25px;"> | |
290 factorial (int x) | 288 factorial (int x) |
291 { | 289 { |
292 int prod; | 290 int prod; |
293 int i; | 291 int i; |
294 | 292 |
303 <D.2847>: | 301 <D.2847>: |
304 print_factorial (prod); | 302 print_factorial (prod); |
305 } | 303 } |
306 </pre> | 304 </pre> |
307 </td> | 305 </td> |
308 </small> | |
309 </tr> | 306 </tr> |
310 </table> | 307 </table> |
311 </div> | 308 </div> |
312 <!-- PAGE --> | 309 <!-- PAGE --> |
313 <div class="slide"> | 310 <div class="slide"> |
314 <h1>GCC</h1> | 311 <h1>GCC</h1> |
315 <table width=100% border=1> | 312 <table border=1 width=100% height=100%> |
316 <tr> | 313 <tr> |
317 <td width=50%>SSA</td> | 314 <td width=50%>SSA</td> |
318 <td width=50%>RTL</td> | 315 <td width=50%>RTL</td> |
319 </tr> | 316 </tr> |
320 <tr> | 317 <tr class="srctr"> |
321 <td> | 318 <td class="srctd"> |
322 <small> | 319 <pre class="srcbox"> |
323 <pre class="srcbox" style="height:20em; font-size:25px;"> | |
324 factorial (int x) | 320 factorial (int x) |
325 { | 321 { |
326 int i; | 322 int i; |
327 int prod; | 323 int prod; |
328 | 324 |
347 print_factorial (prod_1); | 343 print_factorial (prod_1); |
348 return; | 344 return; |
349 } | 345 } |
350 | 346 |
351 </pre> | 347 </pre> |
352 </small> | |
353 </td> | 348 </td> |
354 <td> | 349 <td class="srctd"> |
355 <pre class="srcbox" style="font-size:25px; height:20em; width:25em;"> | 350 <pre class="srcbox" style="width:25em;"> |
356 (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403] <function_decl 0x146f6b200 print_factorial>) [0 S1 A8]) | 351 (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403] <function_decl 0x146f6b200 print_factorial>) [0 S1 A8]) |
357 (const_int 0 [0])) | 352 (const_int 0 [0])) |
358 </pre> | 353 </pre> |
359 </td> | 354 </td> |
360 | |
361 </tr> | 355 </tr> |
362 </table> | 356 </table> |
363 </div> | 357 </div> |
364 <!-- PAGE --> | 358 <!-- PAGE --> |
365 <div class="slide"> | 359 <div class="slide"> |
589 </tr> | 583 </tr> |
590 </table> | 584 </table> |
591 </div> | 585 </div> |
592 <!-- PAGE --> | 586 <!-- PAGE --> |
593 <div class="slide"> | 587 <div class="slide"> |
594 <h1>CbCの実装:TCE</h1> | 588 <h1>CbCの実装:TCE(末尾除去)</h1> |
595 <h2>Tail Call Elimination(TCE):末尾除去</h2> | 589 <h2>Tail Call Elimination(TCE):末尾除去</h2> |
596 <ul> | 590 <ul> |
597 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li> | 591 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li> |
598 </ul> | 592 </ul> |
599 <li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li> | 593 <li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li> |
594 <br> | |
600 <table width=100%> | 595 <table width=100%> |
601 <td> | 596 <tr class="srctr"> |
602 <small> | 597 <td width=50%> |
603 <pre> | 598 <pre class="srcbox"> |
604 int main() { | 599 int main() { |
605 int num = a(2); | 600 int num = a(2); |
606 printf("main:num=%d\n",num); | 601 printf("main:num=%d\n",num); |
607 return 0; | 602 return 0; |
608 } | 603 } |
611 } | 606 } |
612 int b(int num) { | 607 int b(int num) { |
613 printf("b:a = %d\n",num); | 608 printf("b:a = %d\n",num); |
614 return num+3; | 609 return num+3; |
615 } | 610 } |
616 </small> | |
617 </pre> | 611 </pre> |
618 </td> | 612 </td> |
619 <td class="center"> | 613 <td class="center"> |
620 <img src="./pix/continuation.png" style="height: 8em;"> | 614 <img src="./pix/continuation.png" style="height:100%;"> |
621 </td> | 615 </td> |
622 </tr> | 616 </tr> |
623 </table> | 617 </table> |
624 </div> | 618 </div> |
625 <!-- PAGE --> | 619 <!-- PAGE --> |
626 <div class="slide"> | 620 <div class="slide"> |
627 <h1>CbCの実装:TCEの動作</h1> | 621 <h1>CbCの実装:TCE(末尾除去)の動作</h1> |
628 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li> | 622 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li> |
629 <table width=100% border=1> | 623 <table width=100% border=1> |
630 <td> | 624 <td> |
631 <p class="center"> | 625 <p class="center"> |
632 <img src="./pix/tce.png" style="height: 6em;"> | 626 <img src="./pix/tce.png" style="height: 6em;"> |
642 <li class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> | 636 <li class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> |
643 <li class="incremental">TCEにかかるには条件が幾つかある。</li> | 637 <li class="incremental">TCEにかかるには条件が幾つかある。</li> |
644 </div> | 638 </div> |
645 <!-- PAGE --> | 639 <!-- PAGE --> |
646 <div class="slide"> | 640 <div class="slide"> |
647 <h1>CbCの実装:TCE</h1> | 641 <h1>CbCの実装:TCE(末尾除去)</h1> |
648 <li>TCEにかかる条件</li> | 642 <li>TCEにかかる条件</li> |
649 <ol> | 643 <ol> |
650 <li>caller側とcallee側の戻値の型の一致している。</li> | 644 <li>caller側とcallee側の戻値の型の一致している。</li> |
651 <li>関数呼び出しがリターン直前に行われている。</li> | 645 <li>関数呼び出しがリターン直前に行われている。</li> |
652 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> | 646 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> |
653 <li>引数の並びのコピーに上書きがない。</li> | 647 <li>引数の並びのコピーに上書きがない。</li> |
654 </ol> | 648 </ol> |
655 </div> | 649 </div> |
656 <!-- PAGE --> | 650 <!-- PAGE --> |
657 <div class="slide"> | 651 <div class="slide"> |
658 <h1>CbCの実装:TCE</h1> | 652 <h1>CbCの実装:TCE(末尾除去)</h1> |
659 <li>条件を回避する為以下の実装にする。</li> | 653 <li>条件を回避する為以下の実装にする。</li> |
660 <ol> | 654 <ol> |
661 <li>型はvoid型で統一する。</li> | 655 <li>型はvoid型で統一する。</li> |
662 <li>gotoの直後にreturnを置く。</li> | 656 <li>gotoの直後にreturnを置く。</li> |
663 <li>スタックサイズは固定する。</li> | 657 <li>スタックサイズは固定する。</li> |
665 </ol> | 659 </ol> |
666 </small> | 660 </small> |
667 </div> | 661 </div> |
668 <!-- PAGE --> | 662 <!-- PAGE --> |
669 <div class="slide"> | 663 <div class="slide"> |
670 <h1>CbCの実装:TCE</h1> | 664 <h1>CbCの実装:TCE(末尾除去)</h1> |
671 <li>TCEの条件はexpand_call関数で調べられる。</li> | 665 <li>TCEの条件はexpand_call関数で調べられる。</li> |
672 <ul> | 666 <ul> |
673 <li>Treeで表された関数からRTLを生成する関数</li> | 667 <li>Treeで表された関数からRTLを生成する関数</li> |
674 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> | 668 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> |
675 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li> | 669 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li> |
690 <li></li> | 684 <li></li> |
691 </div> | 685 </div> |
692 --> | 686 --> |
693 <!-- PAGE --> | 687 <!-- PAGE --> |
694 <div class="slide"> | 688 <div class="slide"> |
695 <h1>CbCの実装:TCE</h1> | 689 <h1>CbCの実装:TCE(末尾除去)</h1> |
696 <li></li> | 690 <li>try_tail_callフラグが落とされるif文</li> |
691 <pre class="srcbox"> | |
692 if (currently_expanding_call++ != 0 | |
693 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) | |
694 && !flag_optimize_sibling_calls) | |
695 || args_size.var | |
696 || dbg_cnt (tail_call) == false) | |
697 try_tail_call = 0; | |
698 </pre> | |
699 </div> | |
700 <!-- PAGE --> | |
701 <div class="slide"> | |
702 <li>try_tail_callフラグが落とされる部分</li> | |
703 <table> | |
704 <tr class="srctr"> | |
705 <td class="srctd"> | |
706 <pre class="srcbox"> | |
707 if ( | |
708 #ifdef HAVE_sibcall_epilogue | |
709 !HAVE_sibcall_epilogue | |
710 #else | |
711 1 | |
712 #endif | |
713 || !try_tail_call | |
714 || structure_value_addr != NULL_RTX | |
715 #ifdef REG_PARM_STACK_SPACE | |
716 || (OUTGOING_REG_PARM_STACK_SPACE (funtype) | |
717 != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))) | |
718 || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl)) | |
719 #endif | |
720 || !targetm.function_ok_for_sibcall (fndecl, exp) | |
721 || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) | |
722 || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))) | |
723 || (fndecl && decl_function_context (fndecl) == current_function_decl) | |
724 || args_size.constant > (crtl->args.size | |
725 - crtl->args.pretend_args_size) | |
726 || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) | |
727 != targetm.calls.return_pops_args (current_function_decl, | |
728 TREE_TYPE (current_function_decl), | |
729 crtl->args.size)) | |
730 || !lang_hooks.decls.ok_for_sibcall (fndecl)) | |
731 try_tail_call = 0; | |
732 </pre> | |
733 </td> | |
734 </tr> | |
735 </table> | |
736 | |
697 </div> | 737 </div> |
698 <!-- PAGE --> | 738 <!-- PAGE --> |
699 <!-- | 739 <!-- |
700 <div class="slide"> | 740 <div class="slide"> |
701 <h1>CbCの実装:環境付き継続</h1> | 741 <h1>CbCの実装:環境付き継続</h1> |
723 <ul> | 763 <ul> |
724 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> | 764 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> |
725 <li>__returnキーワードを引数に渡すことで使うことができる。</li> | 765 <li>__returnキーワードを引数に渡すことで使うことができる。</li> |
726 </ul> | 766 </ul> |
727 <li>以下の使い方の場合は1を返す。</li> | 767 <li>以下の使い方の場合は1を返す。</li> |
768 <table border=1 width=100%> | |
769 <td> | |
728 <small> | 770 <small> |
729 <pre> | 771 <pre class="srcbox"> |
730 __code c1(__code ret(int,void *),void *env) { | 772 __code c1(__code ret(int,void *),void *env) { |
731 goto ret(1,env); | 773 goto ret(1,env); |
732 } | 774 } |
733 int main() { | 775 int main() { |
734 goto c1(__return, __environment); | 776 goto c1(__return, __environment); |
735 } | 777 } |
736 </pre> | 778 </pre> |
737 </small> | 779 </small> |
738 <p><small>__environmentキーワードは関数の環境を保存している。</small></p> | 780 </td> |
781 </table> | |
782 <p><small>__environmentキーワードは関数の環境を保持する。</small></p> | |
739 </div> | 783 </div> |
740 <!-- PAGE --> | 784 <!-- PAGE --> |
741 <div class="slide"> | 785 <div class="slide"> |
742 <h1>CbCの実装:環境付き継続</h1> | 786 <h1>CbCの実装:環境付き継続</h1> |
743 <h2>実際には以下のコードを生成している。</h2> | 787 <h2>実際には以下のコードを生成している。</h2> |
744 <small> | 788 <small> |
745 <pre> | 789 <pre class="srcbox"> |
790 | |
746 goto c1(__return, __environment); | 791 goto c1(__return, __environment); |
747 | 792 |
748 goto c1(({ | 793 goto c1(({ |
749 __label__ _cbc_exit0; | 794 __label__ _cbc_exit0; |
750 static int retval; | 795 static int retval; |