Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 73:9250ac87c2c7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 03 Jan 2012 14:03:13 +0900
parents 48de60dd51d1
children 275073032132
comparison
equal deleted inserted replaced
72:48de60dd51d1 73:9250ac87c2c7
98 <div class="handout"></div> 98 <div class="handout"></div>
99 </div> 99 </div>
100 <!-- PAGE --> 100 <!-- PAGE -->
101 <div class="slide"> 101 <div class="slide">
102 <h1>目的と背景(1)</h1> 102 <h1>目的と背景(1)</h1>
103 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> 103 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。</li>
104 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> 104 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li> 105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
106 </div> 106 </div>
107 <!-- PAGE --> 107 <!-- PAGE -->
108 <div class="slide"> 108 <div class="slide">
109 <h1>目的と背景(2)</h1> 109 <h1>目的と背景(2)</h1>
110 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li> 110 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
111 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> 111 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
112 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> 112 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
113 </div> 113 </div>
114 <!-- PAGE --> 114 <!-- PAGE -->
115 <div class="slide"> 115 <div class="slide">
137 <!-- PAGE --> 137 <!-- PAGE -->
138 <div class="slide"> 138 <div class="slide">
139 <h1>Continuation based C </h1> 139 <h1>Continuation based C </h1>
140 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> 140 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
141 <ul> 141 <ul>
142 <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li> 142 <li>コードセグメント:CbCにおけるプログラムの基本単位</li>
143 </ul> 143 <ul>
144 <br> 144 <li>C の関数よりも細かい単位になる。</li>
145 <h2>コードセグメント</h2> 145 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
146 <ul> 146 <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
147 <li>C の関数よりも細かい単位。</li> 147 </ul>
148 <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li> 148 <p class="center">
149 </ul> 149 <img src="./pix/codesegment.png" style="height:6em;">
150 </div> 150 </p>
151 <!-- PAGE --> 151 </ul>
152 <div class="slide"> 152 </div>
153 <h1>Continuation Based C</h1> 153 <!-- PAGE -->
154 <h2>継続:現在の処理を実行していく為の情報</h2> 154 <div class="slide">
155 <!-- 155 <h1>Continuation based C </h1>
156 <li>Cでは関数呼び出しの後、呼び出し元の環境に復帰する必要がある。</li> 156 <ul>
157 --> 157 <li>継続(C言語):現在の処理を実行していく為の情報</li>
158 <li>Cにおいての継続</li>
159 <ul> 158 <ul>
160 <li>続く命令のアドレス</li> 159 <li>続く命令のアドレス</li>
161 <li>命令に必要なデータ</li> 160 <li>命令に必要なデータ</li>
162 <li>スタックに積まれている値(環境)</li> 161 <li>スタックに積まれている値(環境)</li>
163 </ul> 162 </ul>
164 </div> 163 </ul>
165 <!-- PAGE --> 164 <li class="incremental">CbC: 関数コールが無い -> 呼び出し元への復帰がない</li>
166 <div class="slide"> 165 <ul class="incremental">
167 <h1>Continuation Based C (軽量継続)</h1> 166 <li>CbCの継続:軽量継続(light-weight continuation)</li>
168 <h2>CbCの継続(軽量継続)</h2>
169 <li>関数コールが無い -> 呼び出し元への復帰がない</li>
170 <ul> 167 <ul>
171 <li>Cの継続から環境を除外</li> 168 <li>Cの継続から環境を除外</li>
172 <li>続く命令とその命令に必要なデータのみ</li> 169 <li>続く命令とその命令に必要なデータのみ</li>
173 </ul> 170 </ul>
174 <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> --> 171 </ul>
175 <!-- <li>スタックポインタの位置を変えずにすむ。</li> --> 172 </div>
173 <!-- PAGE -->
174 <div class="slide">
175 <h1>Continuation Based C (軽量継続)</h1>
176 <p style=" margin-right:auto; margin-left:auto;"> 176 <p style=" margin-right:auto; margin-left:auto;">
177 <table width=90% class="center" border=1> 177 <table width=90% class="center" border=1>
178 <tr> 178 <tr>
179 <td><small>Cの関数呼び出し</small></td> 179 <td><small>Cの関数呼び出し</small></td>
180 <td><small>CbCの継続</></small></td> 180 <td><small>CbCの継続</></small></td>
187 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;"> 187 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
188 </td> 188 </td>
189 </tr> 189 </tr>
190 </table> 190 </table>
191 </p> 191 </p>
192 <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
193 <li>スタックに載るデータは1つのコードセグメントの必要なデータのみ。</li>
192 </div> 194 </div>
193 <!-- PAGE --> 195 <!-- PAGE -->
194 <div class="slide"> 196 <div class="slide">
195 <h1>Continuation based C </h1> 197 <h1>Continuation based C </h1>
196 <small>
197 <table width=100% border=1> 198 <table width=100% border=1>
198 <caption>階乗を求めるCbCのプログラム</caption> 199 <caption><small>階乗を求めるCbCのプログラム</small></caption>
199 <tr class="srctr"> 200 <tr class="srctr">
200 <td width=50%> 201 <td width=50%>
201 <pre class="srcbox"> 202 <pre class="srcbox">
203
202 __code print_factorial(int prod) { 204 __code print_factorial(int prod) {
203 printf("factorial = %d\n",prod); 205 printf("factorial = %d\n",prod);
204 exit(0); 206 exit(0);
205 } 207 }
206 208
213 } 215 }
214 </pre> 216 </pre>
215 </td> 217 </td>
216 <td> 218 <td>
217 <pre class="srcbox"> 219 <pre class="srcbox">
220
218 __code factorial(int x) { 221 __code factorial(int x) {
219 goto factorial0(1, x); 222 goto factorial0(1, x);
220 } 223 }
221 224
222 int main(int argc, char **argv) { 225 int main(int argc, char **argv) {
227 } 230 }
228 </pre> 231 </pre>
229 </td> 232 </td>
230 </tr> 233 </tr>
231 </table> 234 </table>
232 </small> 235 <ul>
233 <li>__code キーワードによるコードセグメントの宣言</li> 236 <li><small>__code キーワードによるコードセグメントの宣言</small></li>
234 <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li> 237 <li><small>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</small></li>
238 </ul>
239 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
235 </div> 240 </div>
236 <!-- PAGE --> 241 <!-- PAGE -->
237 <div class="slide"> 242 <div class="slide">
238 <h1>GCC</h1> 243 <h1>GCC</h1>
239 <li>本来はGnu Compiler Collectionのことを指すが、 244 <li>本来はGnu Compiler Collectionのことを指すが、
240 <br>ここで扱うのはGnu C Compiler(cc1)になる。</li> 245 <br>ここで扱うのはGnu C Compiler(cc1)になる。</li>
241 <ul> 246 <ul>
242 <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコード次の4つの内部表現へと変換される。</li> 247 <li class="incremental">GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
243 </ul> 248 </ul>
244 <!--
245 <li>GCCでは、アセンブラのコードを出力するまでに次の4つの内部表現が扱われる。</li>
246 <ol>
247 <li>Generic Tree</li>
248 <li>GIMPLE</li>
249 <li>Tree SSA</li>
250 <li>RTL</li>
251 </ol>
252 -->
253 </div> 249 </div>
254 <!-- PAGE --> 250 <!-- PAGE -->
255 <div class="slide"> 251 <div class="slide">
256 <h1>GCC</h1> 252 <h1>GCC</h1>
257 <ol> 253 <ol>
385 <div class="slide"> 381 <div class="slide">
386 <h1>GCC</h1> 382 <h1>GCC</h1>
387 <p class="center"> 383 <p class="center">
388 <img src="./pix/ir.png" style="height: 6em;"> 384 <img src="./pix/ir.png" style="height: 6em;">
389 </p> 385 </p>
390 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li> 386 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
391 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li> 387 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
392 </div> 388 </div>
393 <!-- PAGE --> 389 <!-- PAGE -->
394 <div class="slide"> 390 <div class="slide">
395 <h1>GCC:Generic Tree</h1> 391 <h1>GCC:Generic Tree</h1>
461 <!-- PAGE --> 457 <!-- PAGE -->
462 <div class="slide"> 458 <div class="slide">
463 <h1>CbCの実装</h1> 459 <h1>CbCの実装</h1>
464 <ul> 460 <ul>
465 <li>シンタックスの追加</li> 461 <li>シンタックスの追加</li>
462 <li>末尾除去:Tail Call Elimination(TCE)</li>
466 <li>レジスタによる引数渡し(fastcall属性の付与)</li> 463 <li>レジスタによる引数渡し(fastcall属性の付与)</li>
467 <li>Tail Call Elimination</li>
468 <li>環境付き継続</li> 464 <li>環境付き継続</li>
469 <li>__rectype の実装</li> 465 <li>__rectype の実装</li>
470 </ul> 466 </ul>
471 </div> 467 </div>
472 <!-- PAGE --> 468 <!-- PAGE -->
476 <li>__code キーワードでのコードセグメントの宣言</li> 472 <li>__code キーワードでのコードセグメントの宣言</li>
477 <ul> 473 <ul>
478 <li>__code 用idとkeywordを作成。</li> 474 <li>__code 用idとkeywordを作成。</li>
479 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> 475 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
480 </ul> 476 </ul>
477 </ul>
478 <table width=100% border=1>
479 <tr class="srctr">
480 <td>
481 <pre>
482 const struct c_common_resword c_common_reswords[] =
483 {
484 { "_Bool", RID_BOOL, D_CONLY },
485 :
486 { "__code", RID_CbC_CODE, 0 },
487 </pre>
488 </td>
489 </tr>
490 <tr class="srctr">
491 <td>
492 <pre>
493 case RID_CbC_CODE:
494 :
495 specs->typespec_word = cts_CbC_code;
496 </pre>
497 </td>
498 </tr>
499 <tr class="srctr">
500 <td>
501 <pre>
502 case cts_CbC_code:
503 :
504 specs->type = void_type_node;
505 break;
506 </pre>
507 </td>
508 </tr>
509 </table>
510 </div>
511 <!-- PAGE -->
512 <div class="slide">
513 <h1>CbCの実装:シンタックスの追加</h1>
481 <li>goto によるコードセグメントへの継続</li> 514 <li>goto によるコードセグメントへの継続</li>
482 <ul> 515 <ul>
483 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> 516 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
484 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> 517 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
485 </ul> 518 </ul>
486 </ul>
487 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> 519 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li>
488 </div> 520 </div>
489 <!-- PAGE --> 521 <!-- PAGE -->
490 <div class="slide"> 522 <div class="slide">
491 <h1>CbCの実装:シンタックスの追加</h1> 523 <h1>CbCの実装:シンタックスの追加</h1>
492 <h2>gotoシンタックスの追加</h2> 524 <h2>gotoシンタックスの追加</h2>
493 <pre class="srcbox" style="font-size:25px; height:20em;"> 525 <pre class="srcbox" style="font-size:25px; height:17em;">
494 case RID_GOTO: 526 case RID_GOTO:
495 c_parser_consume_token (parser); 527 c_parser_consume_token (parser);
496 if ( c_parser_next_token_is (parser, CPP_NAME) 528 if ( c_parser_next_token_is (parser, CPP_NAME)
497 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON ) 529 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
498 { 530 {
522 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); 554 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
523 } 555 }
524 </pre> 556 </pre>
525 <small> 557 <small>
526 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> 558 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
527 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> 559 <li class="incremental">CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
528 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li> 560 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li>
529 </small> 561 </small>
530 </div> 562 </div>
531 <!-- PAGE --> 563 <!-- PAGE -->
532 <div class="slide"> 564 <div class="slide">
533 <h1>CbCの実装:シンタックスの追加</h1> 565 <h1>CbCの実装:シンタックスの追加</h1>
534 <h2>gotoシンタックスの追加</h2> 566 <h2>gotoシンタックスの追加</h2>
535 <li>最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。</li> 567 <ul>
568 <li>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</li>
569 <li>最後のリターン文生成も、末尾除去にかける為に必要な処理。</li>
570 </ul>
536 <table border=1 width=100%> 571 <table border=1 width=100%>
572 <!--
573 <caption><small>return 自動生成</small></caption>
574 -->
537 <tr class="center"> 575 <tr class="center">
538 <small> 576 <small>
539 <td>実際のコード </td> 577 <td>実際のコード </td>
540 <td>GCC 内で処理されるコード</td> 578 <td>GCC 内で処理されるコード</td>
541 </small> 579 </small>
542 </tr> 580 </tr>
543 <tr style="margin-top: auto;"> 581 <tr class="srctr">
544 <td> 582 <td>
545 <pre> 583 <pre>
546 goto factorial0(1, x); 584
585 __code test() {
586 :
587 goto factorial0(1, x);
588 }
547 </pre> 589 </pre>
548 </td> 590 </td>
549 <td> 591 <td>
550 <pre> 592 <pre>
551 factorial0(1, x); 593
552 return; 594 void test() {
595 :
596 factorial0(1, x);
597 return;
598 }
553 </pre> 599 </pre>
554 </td> 600 </td>
555 </tr> 601 </tr>
556 </table> 602 </table>
603 <!--
557 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> 604 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li>
558 </div> 605 -->
559 <!-- PAGE -->
560 <div class="slide">
561 <h1>CbCの実装:引数渡し</h1>
562 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
563 <ul>
564 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
565 </ul>
566 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
567 </div>
568 <!-- PAGE -->
569 <div class="slide">
570 <h1>CbCの実装:引数渡し(fastcall)</h1>
571 <h2>fastcall</h2>
572 <ul>
573 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
574 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
575 </ul>
576 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
577 <small>
578 <pre>
579 if(!TARGET_64BIT) {
580 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
581 declspecs_add_attrs(specs, attrs);
582 }
583 </pre>
584 </small>
585 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
586 </div>
587 <!-- PAGE -->
588 <div class="slide">
589 <h1>CbCの実装:引数渡し</h1>
590 <table width=100% border=1 class="center">
591 <caption>引数渡しに使われるレジスタの数(gcc)</caption>
592 <tr>
593 <td>arch</td>
594 <td>int(整数型)</td>
595 <td>float(浮動小数点型)</td>
596 <td>double(浮動小数点型)</td>
597 </tr>
598 <tr>
599 <td>i386</td>
600 <td>2</td>
601 <td>0<br>(stackを使用)</td>
602 <td>0<br>(stackを使用)</td>
603 </tr>
604 <tr>
605 <td>x86_64</td>
606 <td>6</td>
607 <td>8</td>
608 <td>8</td>
609 </tr>
610 </table>
611 </div> 606 </div>
612 <!-- PAGE --> 607 <!-- PAGE -->
613 <div class="slide"> 608 <div class="slide">
614 <h1>CbCの実装:TCE(末尾除去)</h1> 609 <h1>CbCの実装:TCE(末尾除去)</h1>
615 <h2>Tail Call Elimination(TCE):末尾除去</h2> 610 <h2>末尾除去:Tail Call Elimination(TCE)</h2>
616 <ul> 611 <ul>
617 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li> 612 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
618 </ul> 613 </ul>
619 <li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li> 614 <li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
620 <br> 615 <br>
621 <table width=100%> 616 <table width=100%>
622 <tr class="srctr"> 617 <tr class="srctr">
623 <td width=50%> 618 <td width=50%>
619 <!--
624 <pre class="srcbox"> 620 <pre class="srcbox">
625 int main() { 621 int main() {
626 int num = a(2); 622 int num = a(2);
627 printf("main:num=%d\n",num); 623 printf("main:num=%d\n",num);
628 return 0; 624 return 0;
633 int b(int num) { 629 int b(int num) {
634 printf("b:a = %d\n",num); 630 printf("b:a = %d\n",num);
635 return num+3; 631 return num+3;
636 } 632 }
637 </pre> 633 </pre>
634 -->
635 <pre class="srcbox">
636
637 void f(int a, int b) {
638 printf("f: a=%d b=%d\n",a,b);
639 return ;
640 }
641 void g(int a, int b){
642 printf("g: a=%d b=%d\n",a,b);
643 f(a,b);
644 return;
645 }
646
647 int main() {
648 g(3,4);
649 return 0;
650 }
651
652 </pre>
638 </td> 653 </td>
639 <td class="center"> 654 <td class="center">
640 <img src="./pix/continuation.png" style="height:100%;"> 655 <img src="./pix/continuation.png" style="height:100%;">
641 </td> 656 </td>
642 </tr> 657 </tr>
678 <h1>CbCの実装:TCE(末尾除去)</h1> 693 <h1>CbCの実装:TCE(末尾除去)</h1>
679 <li>条件を回避する為以下の実装にする。</li> 694 <li>条件を回避する為以下の実装にする。</li>
680 <ol> 695 <ol>
681 <li>型はvoid型で統一する。</li> 696 <li>型はvoid型で統一する。</li>
682 <li>gotoの直後にreturnを置く。</li> 697 <li>gotoの直後にreturnを置く。</li>
683 <li>スタックサイズは固定する。</li> 698 <li>スタックサイズは固定にする。</li>
684 <li>引数は一旦、一時変数にコピーする。</li> 699 <li>引数は一旦、一時変数にコピーする。</li>
685 </ol> 700 </ol>
686 </small>
687 </div> 701 </div>
688 <!-- PAGE --> 702 <!-- PAGE -->
689 <div class="slide"> 703 <div class="slide">
690 <h1>CbCの実装:TCE(末尾除去)</h1> 704 <h1>CbCの実装:TCE(末尾除去)</h1>
691 <li>TCEの条件はexpand_call関数で調べられる。</li> 705 <li>TCEの条件はexpand_call関数で調べられる。</li>
706 <ul>
707 <li>expand_call関数</li>
692 <ul> 708 <ul>
693 <li>Treeで表された関数からRTLを生成する関数</li> 709 <li>Treeで表された関数からRTLを生成する関数</li>
694 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li> 710 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
695 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li> 711 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
696 </ul> 712 </ul>
697 <li>具体的な実装</li> 713 <li class="incremental">具体的な実装内容</li>
698 <ul> 714 <ul>
699 <li>try_tail_callフラグを落とすif文の条件をかわす。</li> 715 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
700 </ul> 716 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
717 </ul>
718 <ul>
719
701 </div> 720 </div>
702 <!-- PAGE --> 721 <!-- PAGE -->
703 <!-- 722 <!--
704 <div class="slide"> 723 <div class="slide">
705 <h1>CbCの実装:TCE</h1> 724 <h1>CbCの実装:TCE</h1>
822 <h1>CbCの実装:TCE(末尾除去)</h1> 841 <h1>CbCの実装:TCE(末尾除去)</h1>
823 <li>try_tail_callフラグ矯正付与のソースコード</li> 842 <li>try_tail_callフラグ矯正付与のソースコード</li>
824 <table width=100%> 843 <table width=100%>
825 <tr class="srctr"> 844 <tr class="srctr">
826 <td> 845 <td>
827 <pre> 846 <pre class="srcbox">
828 #ifndef noCbC 847 #ifndef noCbC
829 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)) 848 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
830 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl)) 849 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
831 && try_tail_call == 0) 850 && try_tail_call == 0)
832 { 851 {
839 #endif 858 #endif
840 </pre> 859 </pre>
841 </td> 860 </td>
842 </tr> 861 </tr>
843 </table> 862 </table>
844 </div> 863 <ul>
845 <!-- PAGE --> 864 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
846 <div class="slide"> 865 <br><small>(最適化の矯正付与)</small></li>
847 <h1>CbCの実装:TCE(末尾除去)</h1> 866 </ul>
867 </div>
868 <!-- PAGE -->
869 <div class="slide">
870 <h1>CbCの実装:TCE(末尾除去)の実装について</h1>
848 <ul> 871 <ul>
849 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作って条件を回避させていた。</li> 872 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作って条件を回避させていた。</li>
850 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li> 873 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
851 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li> 874 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
852 </ul> 875 </ul>
876 </div>
877 <!-- PAGE -->
878 <div class="slide">
879 <h1>CbCの実装</h1>
880 <ul>
881 <li>シンタックスの追加</li>
882 <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
883 </ul>
884 <li>この2つがGCCにおけるCbC実装の基本の部分となる。</li>
885 <li class="incremental">ここからはCbCの機能の拡張になる。</li>
853 </div> 886 </div>
854 <!-- PAGE --> 887 <!-- PAGE -->
855 <!-- 888 <!--
856 <div class="slide"> 889 <div class="slide">
857 <h1>CbCの実装:環境付き継続</h1> 890 <h1>CbCの実装:環境付き継続</h1>
872 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br> 905 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
873 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p> 906 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
874 </div> 907 </div>
875 --> 908 -->
876 <!-- PAGE --> 909 <!-- PAGE -->
910 <div class="slide">
911 <h1>CbCの実装:引数渡し</h1>
912 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
913 <ul>
914 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
915 </ul>
916 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
917 </div>
918 <!-- PAGE -->
919 <div class="slide">
920 <h1>CbCの実装:引数渡し(fastcall)</h1>
921 <h2>fastcall</h2>
922 <ul>
923 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
924 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
925 </ul>
926 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
927 <small>
928 <pre>
929 if(!TARGET_64BIT) {
930 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
931 declspecs_add_attrs(specs, attrs);
932 }
933 </pre>
934 </small>
935 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
936 </div>
937 <!-- PAGE -->
938 <div class="slide">
939 <h1>CbCの実装:引数渡し</h1>
940 <ul>
941 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
942 <li></li>
943 </ul>
944
945 <table width=100% border=1 class="center">
946 <caption>引数渡しに使われるレジスタの数(gcc)</caption>
947 <tr>
948 <td>arch</td>
949 <td>int(整数型)</td>
950 <td>float(浮動小数点型)</td>
951 <td>double(浮動小数点型)</td>
952 </tr>
953 <tr>
954 <td>i386</td>
955 <td>2</td>
956 <td>0<br>(stackを使用)</td>
957 <td>0<br>(stackを使用)</td>
958 </tr>
959 <tr>
960 <td>x86_64</td>
961 <td>6</td>
962 <td>8</td>
963 <td>8</td>
964 </tr>
965 </table>
966 </div>
967 <!-- PAGE -->
877 <div class="slide"> 968 <div class="slide">
878 <h1>CbCの実装:環境付き継続</h1> 969 <h1>CbCの実装:環境付き継続</h1>
879 <ul> 970 <ul>
880 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> 971 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
881 <li>__returnキーワードを引数に渡すことで使うことができる。</li> 972 <li>__returnキーワードを引数に渡すことで使うことができる。</li>
898 <p><small>__environmentキーワードは関数の環境を保持する。</small></p> 989 <p><small>__environmentキーワードは関数の環境を保持する。</small></p>
899 </div> 990 </div>
900 <!-- PAGE --> 991 <!-- PAGE -->
901 <div class="slide"> 992 <div class="slide">
902 <h1>CbCの実装:環境付き継続</h1> 993 <h1>CbCの実装:環境付き継続</h1>
903 <h2>実際には以下のコードを生成している。</h2> 994 <li><small>生成しているコードと生成する為のコード</small></li>
904 <small> 995 <table border=1 width=100%>
905 <pre class="srcbox"> 996 <tr>
906 997 <td><small>生成しているコード</small></td>
998 <td><small>生成する為のコード</small></td>
999 </tr>
1000 <tr class="srctr">
1001 <td width=50% class="srctd">
1002 <pre class="srcbox" style="width:25em;">
907 goto c1(__return, __environment); 1003 goto c1(__return, __environment);
908 1004
909 goto c1(({ 1005 goto c1(({
910 __label__ _cbc_exit0; 1006 __label__ _cbc_exit0;
911 static int retval; 1007 static int retval;
918 return retval; 1014 return retval;
919 } 1015 }
920 _cbc_internal_return; 1016 _cbc_internal_return;
921 }), __environment); 1017 }), __environment);
922 </pre> 1018 </pre>
923 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> 1019 </td>
924 </small> 1020 <td width=50% class="srctd">
925 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> 1021 <pre class="srcbox" style="width:25em;">
926 </div> 1022 case RID_CbC_RET:
927 <!-- PAGE -->
928 <!--
929 <div class="slide">
930 <h1>CbCの実装:環境付き継続</l>
931 <h2>環境付き継続の生成部分:</h2>
932 <div class="src">
933 <small>
934 <pre>
935 { 1023 {
936 tree value, stmt, label, tlab, decl; 1024 tree value, stmt, label, tlab, decl;
937 c_parser_consume_token (parser); 1025 c_parser_consume_token (parser);
938 1026
939 stmt = c_begin_stmt_expr (); 1027 stmt = c_begin_stmt_expr ();
974 1062
975 TREE_SIDE_EFFECTS (stmt) = 1; 1063 TREE_SIDE_EFFECTS (stmt) = 1;
976 expr.value = c_finish_stmt_expr (location, stmt); 1064 expr.value = c_finish_stmt_expr (location, stmt);
977 expr.original_code = ERROR_MARK; 1065 expr.original_code = ERROR_MARK;
978 } 1066 }
979 </pre> 1067 </td>
980 </small> 1068 </tr>
981 </div> 1069 </table>
982 </div> 1070 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p>
983 --> 1071 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
1072 </div>
984 <!-- PAGE --> 1073 <!-- PAGE -->
985 <div class="slide"> 1074 <div class="slide">
986 <h1>CbCの実装:環境付き継続</h1> 1075 <h1>CbCの実装:環境付き継続</h1>
987 <h2>作成されるTree</h2> 1076 <h2>作成されるTree</h2>
988 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;"> 1077 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">