Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 69:9dc6013b0559

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of tce
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 29 Dec 2011 18:19:44 +0900
parents 1399414ea3f6
children 79894ca66a9a
comparison
equal deleted inserted replaced
68:1399414ea3f6 69:9dc6013b0559
245 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li> 245 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
246 </div> 246 </div>
247 <!-- PAGE --> 247 <!-- PAGE -->
248 <div class="slide"> 248 <div class="slide">
249 <h1>GCC</h1> 249 <h1>GCC</h1>
250 <li>CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
251 <p class="center"> 250 <p class="center">
252 <img src="./pix/ir.png" style="height: 6em;"> 251 <img src="./pix/ir.png" style="height: 6em;">
253 </p> 252 </p>
254 <li class="incremental">Generic Tree生成部分について触れてみる。</li> 253 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。</li>
254 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
255 </div> 255 </div>
256 <!-- PAGE --> 256 <!-- PAGE -->
257 <div class="slide"> 257 <div class="slide">
258 <h1>GCC:Generic Tree</h1> 258 <h1>GCC:Generic Tree</h1>
259 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li> 259 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
260 <table class="center" width=100% border=1> 260 <table class="center" width=100% border=1>
261 <tr> 261 <tr>
262 <td></td>
262 <td><small>値の代入:MODIFY_EXPR</small></td> 263 <td><small>値の代入:MODIFY_EXPR</small></td>
263 <td><small>関数呼び出し:CALL_EXPR</small></td> 264 <td><small>関数呼び出し:CALL_EXPR</small></td>
264 </t> 265 </t>
265 <tr> 266 <tr>
267 <td>命令</td>
268 <td>b = a * 10</td>
269 <td>func(a,10)</td>
270 </t>
271 <tr>
272 <td><small>Generic<br>Tree</small></td>
266 <td> 273 <td>
267 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;"> 274 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
268 </td> 275 </td>
269 <td> 276 <td>
270 <img src="./pix/CALL_EXPR.png" style="height: 7em;"> 277 <img src="./pix/CALL_EXPR.png" style="height: 7em;">
300 <img src="./pix/STATEMENT_LIST.png" style="height: 6em;"> 307 <img src="./pix/STATEMENT_LIST.png" style="height: 6em;">
301 </p> 308 </p>
302 </td> 309 </td>
303 </tr> 310 </tr>
304 </table> 311 </table>
305 <li>CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li> 312 <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
306 </div> 313 </div>
307 <!-- PAGE --> 314 <!-- PAGE -->
308 <!-- 315 <!--
309 <div class="slide"> 316 <div class="slide">
310 <h1>GCC</h1> 317 <h1>GCC</h1>
362 </pre> 369 </pre>
363 </small> 370 </small>
364 <small> 371 <small>
365 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> 372 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
366 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li> 373 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
367 <li>最後にc_finish_return関数によりreturn文を生成している。</li> 374 <li class="incremental">最後にc_finish_return関数によりreturn文を生成している。</li>
368 </small> 375 </small>
369 </div> 376 </div>
370 <!-- PAGE --> 377 <!-- PAGE -->
371 <div class="slide"> 378 <div class="slide">
372 <h1>CbCの実装:シンタックスの追加</h1> 379 <h1>CbCの実装:シンタックスの追加</h1>
410 <h2>fastcall</h2> 417 <h2>fastcall</h2>
411 <ul> 418 <ul>
412 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> 419 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
413 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li> 420 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
414 </ul> 421 </ul>
415 <li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li> 422 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを挿入。</li>
416 <small> 423 <small>
417 <pre> 424 <pre>
418 if(!TARGET_64BIT) { 425 if(!TARGET_64BIT) {
419 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 426 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
420 declspecs_add_attrs(specs, attrs); 427 declspecs_add_attrs(specs, attrs);
450 </div> 457 </div>
451 <!-- PAGE --> 458 <!-- PAGE -->
452 <div class="slide"> 459 <div class="slide">
453 <h1>CbCの実装:TCE</h1> 460 <h1>CbCの実装:TCE</h1>
454 <h2>Tail Call Elimination(TCE):末尾除去</h2> 461 <h2>Tail Call Elimination(TCE):末尾除去</h2>
455 <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li> 462 <ul>
456 <img src="./pix/continuation.png" style="height: 7em;"> 463 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
464 </ul>
465 <li><small>以下のソースの場合 関数a から関数b へjmp命令で処理が移る。</small></li>
466 <table width=100%>
467 <td>
468 <small>
469 <pre>
470 int main() {
471 int a = f(2);
472 printf("main:num=%d\n",num);
473 return 0;
474 }
475 int a(int num) {
476 return g(num+5);
477 }
478 int b(int num) {
479 printf("g:a = %d\n",num);
480 return num+3;
481 }
482 </small>
483 </pre>
484 </td>
485 <td class="center">
486 <img src="./pix/continuation.png" style="height: 8em;">
487 </td>
488 </tr>
489 </table>
490 </div>
491 <!-- PAGE -->
492 <div class="slide">
493 <h1>CbCの実装:TCEの動作</h1>
457 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> 494 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
495 <ul>
496 <li>jmp命令により呼び出し元関数と同じ範囲のスタックを使うことになる。</li>
497 </ul>
498 <p class="center">
499 <img src="./pix/tce.png" style="height: 6em;">
500 </p>
501 <li class="incremental">TCEにかかるには条件が幾つかある。</li>
458 </div> 502 </div>
459 <!-- PAGE --> 503 <!-- PAGE -->
460 <div class="slide"> 504 <div class="slide">
461 <h1>CbCの実装:TCE</h1> 505 <h1>CbCの実装:TCE</h1>
462 <li>TCEにより関数へjmp命令で処理を移すことを利用。</li> 506 <li>TCEにかかる条件</li>
507 <ol>
508 <li>caller側とcallee側の戻値の型の一致している。</li>
509 <li>関数呼び出しがリターン直前に行われている。</li>
510 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
511 <li>引数の並びのコピーに上書きがない。</li>
512 </ol>
513 </div>
514 <!-- PAGE -->
515 <div class="slide">
516 <h1>CbCの実装:TCE</h1>
517 <li>条件を回避する為以下の実装にする。</li>
518 <ol>
519 <li>型はvoid型で統一。</li>
520 <li>gotoの直後にreturnを置く。</li>
521 <li>スタックサイズは固定。</li>
522 <li>引数は一旦、一時変数にコピーする。</li>
523 </ol>
524 </small>
525 </div>
526 <!-- PAGE -->
527 <div class="slide">
528 <h1>CbCの実装:TCE</h1>
529 <li>コードセグメントの継続 -> TCEにより吐かれるjmp命令を利用。</li>
530 <!--
463 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li> 531 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li>
532 -->
464 <br> 533 <br>
465 <h2>具体的な実装内容</h2> 534 <h2>具体的な実装内容</h2>
466 <ul> 535 <ul>
467 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li> 536 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li>
468 <li class="incremental">try_tail_callフラグを落とさせない。</li> 537 <li class="incremental">try_tail_callフラグを落とさせない。</li>