Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 70:79894ca66a9a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of GCC
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 31 Dec 2011 11:55:47 +0900
parents 9dc6013b0559
children 64d22e65489c
comparison
equal deleted inserted replaced
69:9dc6013b0559 70:79894ca66a9a
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>
8 td.box {
9 height: 80%;
10 overflow: scroll;
11 }
12 pre.srcbox {
13 height: 80%;
14 overflow: scroll;
15 font-size: 25px;
16 }
8 .src{ 17 .src{
9 overflow: scroll; 18 overflow: scroll;
10 width: 90%; 19 width: 90%;
11 height: 60%; 20 height: 60%;
12 } 21 }
186 <small> 195 <small>
187 <table width=100% border=1> 196 <table width=100% border=1>
188 <tr> 197 <tr>
189 <caption>階乗を求めるCbCのプログラム</caption> 198 <caption>階乗を求めるCbCのプログラム</caption>
190 <td width=50%> 199 <td width=50%>
191 <pre> 200 <pre class="srcbox">
192 __code print_factorial(int prod) { 201 __code print_factorial(int prod) {
193 printf("factorial = %d\n",prod); 202 printf("factorial = %d\n",prod);
194 exit(0); 203 exit(0);
195 } 204 }
196 205
202 } 211 }
203 } 212 }
204 </pre> 213 </pre>
205 </td> 214 </td>
206 <td> 215 <td>
207 <pre> 216 <pre class="srcbox">
208 __code factorial(int x) { 217 __code factorial(int x) {
209 goto factorial0(1, x); 218 goto factorial0(1, x);
210 } 219 }
211 220
212 int main(int argc, char **argv) { 221 int main(int argc, char **argv) {
225 </div> 234 </div>
226 <!-- PAGE --> 235 <!-- PAGE -->
227 <div class="slide"> 236 <div class="slide">
228 <h1>GCC</h1> 237 <h1>GCC</h1>
229 <li>本来はGnu Compiler Collectionのことを指すが、 238 <li>本来はGnu Compiler Collectionのことを指すが、
230 <br>ここで扱うのはGnu C Compilerになる。</li> 239 <br>ここで扱うのはGnu C Compiler(cc1)になる。</li>
231 <li>GCCでは次の4つの内部表現が扱われる。</li> 240 <ul>
241 <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコード次の4つの内部表現へと変換される。</li>
242 </ul>
243 <!--
244 <li>GCCでは、アセンブラのコードを出力するまでに次の4つの内部表現が扱われる。</li>
232 <ol> 245 <ol>
233 <li>Generic Tree</li> 246 <li>Generic Tree</li>
234 <li>GIMPLE</li> 247 <li>GIMPLE</li>
235 <li>Tree SSA</li> 248 <li>Tree SSA</li>
236 <li>RTL</li> 249 <li>RTL</li>
237 </ol> 250 </ol>
251 -->
238 </div> 252 </div>
239 <!-- PAGE --> 253 <!-- PAGE -->
240 <div class="slide"> 254 <div class="slide">
241 <h1>GCC</h1> 255 <h1>GCC</h1>
242 <li>Generic Tree:ソースコードを構文木の形に直したもの</li> 256 <ol>
243 <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li> 257 <li>Generic Tree:ソースコードを構文木の形に直したもの</li>
244 <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li> 258 <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li>
245 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li> 259 <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li>
246 </div> 260 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
247 <!-- PAGE --> 261 </ol>
262 <li class="incremental">それぞれは次のようなデータを構文木にして持っている。</li>
263 </div>
264 <!-- PAGE -->
265 <div class="slide">
266 <h1>GCC</h1>
267 <table width=100% border=1>
268 <tr>
269 <td>Generic(ソースコード)</td>
270 <td>GIMPLE</td>
271 </tr>
272 <tr>
273 <td>
274 <small>
275 <pre class="srcbox" style="height:20em; font-size:25px;">
276 void factorial(int x)
277 {
278 int prod,i;
279 for(i=1,prod=1; i <= x; i++){
280 prod = prod*i;
281 }
282 print_factorial(prod);
283 }
284 </pre>
285 </small>
286 </td>
287 <td>
288 <small>
289 <pre class="srcbox" style="height:20em; font-size:25px;">
290 factorial (int x)
291 {
292 int prod;
293 int i;
294
295 i = 1;
296 prod = 1;
297 goto &lt;D.2846&gt;;
298 &lt;D.2845&gt;:
299 prod = prod * i;
300 i = i + 1;
301 &lt;D.2846&gt;:
302 if (i &lt;= x) goto &lt;D.2845&gt;; else goto &lt;D.2847&gt;;
303 &lt;D.2847&gt;:
304 print_factorial (prod);
305 }
306 </pre>
307 </td>
308 </small>
309 </tr>
310 </table>
311 </div>
312 <!-- PAGE -->
313 <div class="slide">
314 <h1>GCC</h1>
315 <table width=100% border=1>
316 <tr>
317 <td width=50%>SSA</td>
318 <td width=50%>RTL</td>
319 </tr>
320 <tr>
321 <td>
322 <small>
323 <pre class="srcbox" style="height:20em; font-size:25px;">
324 factorial (int x)
325 {
326 int i;
327 int prod;
328
329 &lt;bb 2&gt;:
330 i_3 = 1;
331 prod_4 = 1;
332 goto &lt;bb 4&gt;;
333
334 &lt;bb 3&gt;:
335 prod_6 = prod_1 * i_2;
336 i_7 = i_2 + 1;
337
338 &lt;bb 4&gt;:
339 # prod_1 = PHI &lt;prod_4(2), prod_6(3)&gt;
340 # i_2 = PHI &lt;i_3(2), i_7(3)&gt;
341 if (i_2 &lt;= x_5(D))
342 goto &lt;bb 3&gt;;
343 else
344 goto &lt;bb 5&gt;;
345
346 &lt;bb 5&gt;:
347 print_factorial (prod_1);
348 return;
349 }
350
351 </pre>
352 </small>
353 </td>
354 <td>
355 <pre class="srcbox" style="font-size:25px; height:20em; width:25em;">
356 (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403] &lt;function_decl 0x146f6b200 print_factorial&gt;) [0 S1 A8])
357 (const_int 0 [0]))
358 </pre>
359 </td>
360
361 </tr>
362 </table>
363 </div>
364 <!-- PAGE -->
248 <div class="slide"> 365 <div class="slide">
249 <h1>GCC</h1> 366 <h1>GCC</h1>
250 <p class="center"> 367 <p class="center">
251 <img src="./pix/ir.png" style="height: 6em;"> 368 <img src="./pix/ir.png" style="height: 6em;">
252 </p> 369 </p>
351 </div> 468 </div>
352 <!-- PAGE --> 469 <!-- PAGE -->
353 <div class="slide"> 470 <div class="slide">
354 <h1>CbCの実装:シンタックスの追加</h1> 471 <h1>CbCの実装:シンタックスの追加</h1>
355 <h2>gotoシンタックスの追加</h2> 472 <h2>gotoシンタックスの追加</h2>
356 <small> 473 <pre class="srcbox" style="font-size:25px; height:20em;">
357 <pre> 474 case RID_GOTO:
358 expr = c_parser_expr_no_commas (parser, NULL); 475 c_parser_consume_token (parser);
359 if (TREE_CODE(expr.value) == CALL_EXPR ) 476 if ( c_parser_next_token_is (parser, CPP_NAME)
360 { 477 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
361 location_t loc = c_parser_peek_token (parser)->location; 478 {
362 cbc_replace_arguments (loc, expr.value); 479 stmt = c_finish_goto_label (loc,
363 TREE_TYPE(expr.value) = void_type_node; 480 c_parser_peek_token (parser)->value);
364 CbC_IS_CbC_GOTO (expr.value) = 1; 481 c_parser_consume_token (parser);
365 CALL_EXPR_TAILCALL (expr.value) = 1; 482 }
366 add_stmt(expr.value); 483 else if (c_parser_next_token_is (parser, CPP_MULT))
367 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); 484 {
368 } 485 tree val;
486
487 c_parser_consume_token (parser);
488 val = c_parser_expression (parser).value;
489 mark_exp_read (val);
490 stmt = c_finish_goto_ptr (loc, val);
491 }
492 else
493 expr = c_parser_expr_no_commas (parser, NULL);
494 if (TREE_CODE(expr.value) == CALL_EXPR )
495 {
496 location_t loc = c_parser_peek_token (parser)->location;
497 cbc_replace_arguments (loc, expr.value);
498 TREE_TYPE(expr.value) = void_type_node;
499 CbC_IS_CbC_GOTO (expr.value) = 1;
500 CALL_EXPR_TAILCALL (expr.value) = 1;
501 add_stmt(expr.value);
502 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
503 }
369 </pre> 504 </pre>
370 </small>
371 <small> 505 <small>
372 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> 506 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
373 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> 507 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
374 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li> 508 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li>
375 </small> 509 </small>
376 </div> 510 </div>
377 <!-- PAGE --> 511 <!-- PAGE -->
378 <div class="slide"> 512 <div class="slide">
379 <h1>CbCの実装:シンタックスの追加</h1> 513 <h1>CbCの実装:シンタックスの追加</h1>
380 <h2>gotoシンタックスの追加</h2> 514 <h2>gotoシンタックスの追加</h2>
381 <li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li> 515 <li>最後にリターン文を生成することにより、次へと制御を移させず、末尾最適化がかかるようになる。</li>
382 <table border=1 width=100%> 516 <table border=1 width=100%>
383 <tr class="center"> 517 <tr class="center">
384 <small> 518 <small>
385 <td>実際のコード </td> 519 <td>実際のコード </td>
386 <td>GCC 内で処理されるコード</td> 520 <td>GCC 内で処理されるコード</td>
417 <h2>fastcall</h2> 551 <h2>fastcall</h2>
418 <ul> 552 <ul>
419 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> 553 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
420 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li> 554 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
421 </ul> 555 </ul>
422 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを挿入。</li> 556 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
423 <small> 557 <small>
424 <pre> 558 <pre>
425 if(!TARGET_64BIT) { 559 if(!TARGET_64BIT) {
426 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 560 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
427 declspecs_add_attrs(specs, attrs); 561 declspecs_add_attrs(specs, attrs);
466 <table width=100%> 600 <table width=100%>
467 <td> 601 <td>
468 <small> 602 <small>
469 <pre> 603 <pre>
470 int main() { 604 int main() {
471 int a = f(2); 605 int num = a(2);
472 printf("main:num=%d\n",num); 606 printf("main:num=%d\n",num);
473 return 0; 607 return 0;
474 } 608 }
475 int a(int num) { 609 int a(int num) {
476 return g(num+5); 610 return b(num+5);
477 } 611 }
478 int b(int num) { 612 int b(int num) {
479 printf("g:a = %d\n",num); 613 printf("b:a = %d\n",num);
480 return num+3; 614 return num+3;
481 } 615 }
482 </small> 616 </small>
483 </pre> 617 </pre>
484 </td> 618 </td>
489 </table> 623 </table>
490 </div> 624 </div>
491 <!-- PAGE --> 625 <!-- PAGE -->
492 <div class="slide"> 626 <div class="slide">
493 <h1>CbCの実装:TCEの動作</h1> 627 <h1>CbCの実装:TCEの動作</h1>
494 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> 628 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
495 <ul> 629 <table width=100% border=1>
496 <li>jmp命令により呼び出し元関数と同じ範囲のスタックを使うことになる。</li> 630 <td>
497 </ul>
498 <p class="center"> 631 <p class="center">
499 <img src="./pix/tce.png" style="height: 6em;"> 632 <img src="./pix/tce.png" style="height: 6em;">
500 </p> 633 </p>
634 </td>
635 <td>
636 <ul>
637 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
638 <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
639 </ul>
640 </td>
641 </table>
642 <li class="incremental">CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
501 <li class="incremental">TCEにかかるには条件が幾つかある。</li> 643 <li class="incremental">TCEにかかるには条件が幾つかある。</li>
502 </div> 644 </div>
503 <!-- PAGE --> 645 <!-- PAGE -->
504 <div class="slide"> 646 <div class="slide">
505 <h1>CbCの実装:TCE</h1> 647 <h1>CbCの実装:TCE</h1>
514 <!-- PAGE --> 656 <!-- PAGE -->
515 <div class="slide"> 657 <div class="slide">
516 <h1>CbCの実装:TCE</h1> 658 <h1>CbCの実装:TCE</h1>
517 <li>条件を回避する為以下の実装にする。</li> 659 <li>条件を回避する為以下の実装にする。</li>
518 <ol> 660 <ol>
519 <li>型はvoid型で統一。</li> 661 <li>型はvoid型で統一する。</li>
520 <li>gotoの直後にreturnを置く。</li> 662 <li>gotoの直後にreturnを置く。</li>
521 <li>スタックサイズは固定。</li> 663 <li>スタックサイズは固定する。</li>
522 <li>引数は一旦、一時変数にコピーする。</li> 664 <li>引数は一旦、一時変数にコピーする。</li>
523 </ol> 665 </ol>
524 </small> 666 </small>
525 </div> 667 </div>
526 <!-- PAGE --> 668 <!-- PAGE -->
527 <div class="slide"> 669 <div class="slide">
528 <h1>CbCの実装:TCE</h1> 670 <h1>CbCの実装:TCE</h1>
529 <li>コードセグメントの継続 -> TCEにより吐かれるjmp命令を利用。</li> 671 <li>TCEの条件はexpand_call関数で調べられる。</li>
672 <ul>
673 <li>Treeで表された関数からRTLを生成する関数</li>
674 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
675 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
676 </ul>
677 <li>具体的な実装</li>
678 <ul>
679 <li>try_tail_callフラグを落とさせない処理が追加されている。</li>
680 </ul>
681 </div>
682 <!-- PAGE -->
530 <!-- 683 <!--
531 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li> 684 <div class="slide">
685 <h1>CbCの実装:TCE</h1>
686 <li>TCEにかかる条件</li>
687 <ul>
688 <li>try_tail_callフラグを落とさせない。</li>
689 </ul>
690 <li></li>
691 </div>
532 --> 692 -->
533 <br>
534 <h2>具体的な実装内容</h2>
535 <ul>
536 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li>
537 <li class="incremental">try_tail_callフラグを落とさせない。</li>
538 </ul>
539 <li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li>
540 </div>
541 <!-- PAGE --> 693 <!-- PAGE -->
542 <div class="slide"> 694 <div class="slide">
543 <h1>CbCの実装:TCE</h1> 695 <h1>CbCの実装:TCE</h1>
544 <li>try_tail_callフラグはexpand_call関数で落とされる。</li> 696 <li></li>
545 <ul>
546 <li>expand_call関数</li>
547 <ul>
548 <li>Treeで表された関数からRTLを生成する関数</li>
549 </ul>
550 </ul>
551 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li>
552 <small>
553 <ol>
554 <li>caller側とcallee側の戻値の型の一致している。</li>
555 <li>関数呼び出しがリターン直前に行われている。</li>
556 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
557 <li>引数の並びのコピーに上書きがない。</li>
558 </ol>
559 </small>
560 </div>
561 <!-- PAGE -->
562 <div class="slide">
563 <h1>CbCの実装:TCE</h1>
564 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li>
565 <small>
566 <ol>
567 <li>型はvoid型で統一。</li>
568 <li>gotoの直後にreturnを置く。</li>
569 <li>スタックサイズは固定。</li>
570 <li>引数は一旦、一時変数にコピーする。</li>
571 </ol>
572 </small>
573 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li>
574 </div> 697 </div>
575 <!-- PAGE --> 698 <!-- PAGE -->
576 <!-- 699 <!--
577 <div class="slide"> 700 <div class="slide">
578 <h1>CbCの実装:環境付き継続</h1> 701 <h1>CbCの実装:環境付き継続</h1>
595 </div> 718 </div>
596 --> 719 -->
597 <!-- PAGE --> 720 <!-- PAGE -->
598 <div class="slide"> 721 <div class="slide">
599 <h1>CbCの実装:環境付き継続</h1> 722 <h1>CbCの実装:環境付き継続</h1>
723 <ul>
600 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> 724 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
601 <li>__returnキーワードを引数に渡すことで使うことができる。</li> 725 <li>__returnキーワードを引数に渡すことで使うことができる。</li>
726 </ul>
602 <li>以下の使い方の場合は1を返す。</li> 727 <li>以下の使い方の場合は1を返す。</li>
603 <small> 728 <small>
604 <pre> 729 <pre>
605 __code c1(__code ret(int,void *),void *env) { 730 __code c1(__code ret(int,void *),void *env) {
606 goto ret(1,env); 731 goto ret(1,env);
637 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> 762 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p>
638 </small> 763 </small>
639 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> 764 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li>
640 </div> 765 </div>
641 <!-- PAGE --> 766 <!-- PAGE -->
767 <!--
642 <div class="slide"> 768 <div class="slide">
643 <h1>CbCの実装:環境付き継続</l> 769 <h1>CbCの実装:環境付き継続</l>
644 <h2>環境付き継続の生成部分:</h2> 770 <h2>環境付き継続の生成部分:</h2>
645 <div class="src"> 771 <div class="src">
646 <small> 772 <small>
691 } 817 }
692 </pre> 818 </pre>
693 </small> 819 </small>
694 </div> 820 </div>
695 </div> 821 </div>
822 -->
696 <!-- PAGE --> 823 <!-- PAGE -->
697 <div class="slide"> 824 <div class="slide">
698 <h1>CbCの実装:環境付き継続</h1> 825 <h1>CbCの実装:環境付き継続</h1>
699 <h2>作成されるTree</h2> 826 <h2>作成されるTree</h2>
700 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;"> 827 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
792 : 919 :
793 (*print)(n,result,print,exit1, envp); 920 (*print)(n,result,print,exit1, envp);
794 } 921 }
795 </pre> 922 </pre>
796 </small> 923 </small>
797 <li>以下の様に扱えるようにしたい。</li> 924 <li>以下の様に引数に()をつけて受けてることをやめたい。</li>
798 <small> 925 <small>
799 <pre> 926 <pre>
800 void factorial(int n, int result, void *print){ 927 void factorial(int n, int result, void *print){
801 : 928 :
802 (*print)(n,result,print,exit1, envp); 929 void(*print)(n,result,print,exit1, envp);
803 } 930 }
804 </pre> 931 </pre>
805 </small> 932 </small>
806 </div> 933 </div>
807 <!-- PAGE --> 934 <!-- PAGE -->
809 <h1>CbCの機能の拡張:__rectype の実装</h1> 936 <h1>CbCの機能の拡張:__rectype の実装</h1>
810 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> 937 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
811 <pre> 938 <pre>
812 __code factorial(int n, int result, __rectype *print) { 939 __code factorial(int n, int result, __rectype *print) {
813 : 940 :
814 (*print)(n,result,print,exit1, envp); 941 goto (*print)(n,result,print,exit1, envp);
815 } 942 }
816 </pre> 943 </pre>
817 </div> 944 </div>
818 <!-- PAGE --> 945 <!-- PAGE -->
819 <div class="slide"> 946 <div class="slide">