Mercurial > hg > Papers > 2011 > nobu-prosym

view presen/index.html @ 86:a6135031ce35 default tip

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 Sat, 07 Jan 2012 17:43:09 +0900
parents 7ed352ddae10
children
line wrap: on
line source

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<style type="text/css">
tr.srctr {
font-size:28px;
}
td.srctd {
height:17em;
}
pre.srcbox {
height: 100%;
overflow: scroll;
}
.src{
overflow: scroll;
width: 90%;
height: 60%;
}
.center {
margin-left: auto;
margin-right: auto;
text-align: center;
}
.textcenter {
text-align: center;
}
.taninaritop {
   margin: auto;
   width: 95%;
   font-weight: bold;
}
</style>
<title>2012/ 1/ 7</title>
<!-- metadata -->
    <meta name="generator" content="S5" />
    <meta name="version" content="S5 1.1" />
    <meta name="presdate" content="20120107" />
    <meta name="author" content="Nobuyasu Oshiro" />
    <meta name="company" content="University of the Ryukyu" />
<!-- meta temporary -->
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<!-- configuration extensions -->
<meta name="tranSitions" content="true" />
<meta name="fadeDuration" content="500" />
<meta name="incrDuration" content="250" />
<!-- configuration autoplay extension -->
<meta name="autoMatic" content="false" />
<meta name="playLoop" content="true" />
<meta name="playDelay" content="10" />
<!-- configuration audio extension -->
<meta name="audioSupport" content="false" />
<meta name="audioVolume" content="100" />
<meta name="audioError" content="false" />
<!-- configuration audio debug -->
<meta name="audioDebug" content="false" />
<!-- style sheet links -->
<link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" />
<link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" />
<link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" />
<link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" />
<!-- embedded styles -->
<style type="text/css" media="all">
.imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;}
#anim {width: 33%; height: 320px; position: relative;}
#anim img {position: absolute; top: 0px; left: 0px;}
</style>
<!-- S5 JS -->
<script src="ui/default_utf/slides.js" type="text/javascript"></script>
</head>
<body>

<div class="layout">
<div id="controls"><!-- DO NOT EDIT --></div>
<div id="currentSlide"><!-- DO NOT EDIT --></div>
<div id="header"></div>
<div id="footer">
<h1>プログラミングシンポジウム: 2012/ 1/ 7</h1>
<h2>並列信頼研</h2>
</div>
</div>

<div class="presentation">

      <div class="slide">
        <h1>Continuation based Cの GCC 4.6 上の実装について</li>
        <h3></h3>
	<li>大城 信康</li>
        <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4>
        <div class="handout"></div>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>目的と背景(1)</h1>
	<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。</li>
	<li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
	<li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
      </div>
      <!-- PAGE -->
      <div class="slide">
 	<h1>目的と背景(2)</h1>
	<li>CbCのコンパイラは2001年に Micro-C版、2008年にはGCC-4.2をベースとしたコンパイラが開発された。</li>
	<li>GCC上のCbCコンパイラは、GCCで修正・追加されていく最適化の機能を使用する為に、アップデートに合わせ変更する必要がある。</li>
	<li>本研究ではCbCコンパイラをGCC-4.6へとアップデートを行った。 </li>
      </div>
      <!-- PAGE -->
<!--
      <div class="">
	<h1>先行研究</h1>
	<li>Continuation based c コン パイラの gcc-4.2 による実装</li>
	<li></li>
      </div>
-->
      <!-- PAGE -->
      <div class="slide">
	<h1>発表内容</h1>
	<ol>
	  <li>CbC の紹介</li>
	  <li>GCC でのコンパイルの流れ</li>
	  <font color="red">
	    <li>CbC の実装</li>
	  </font>
	  <li>Micro-C との性能比較</li>
	  <li>まとめ</li>
	<ol>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>Continuation based C </h1>
	<h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
	<ul>
	<li>コードセグメント:CbCにおけるプログラムの基本単位</li>
	<ul>
	  <li>Cから関数コールとループ制御が取り除かれた形</li>
	  <li>C の関数よりも細かい単位になる。</li>
	  <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
	  </ul>
	<p class="center">
	  <img src="./pix/codesegment.png"  style="height:6em;">
	  </p>
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>Continuation based C </h1>	
	<h2>継続:現在の処理を実行していく為の情報</h2>

	<table width=100% border=1>
	  <tr>
	    <td><small>Cの継続</small></td>
	    <td><small>CbCの継続(軽量継続)</small></td>
	  </tr>
	  <tr style="font-size:30px">
	    <td>
	      <ul>
		<li>続く命令のアドレス</li>
		<li>命令に必要なデータ</li>
		<li>スタックに積まれている値(環境)</li>
	      </ul>
	    </td>
	    <td>
	      <ul>
		<li>Cの継続から環境を除外</li>
		<li>続く命令とその命令に必要なデータのみ</li>
	      </ul>
	    </td>
	  </tr>
	    <tr>
	    <td style="margin-left:auto; margin-right: auto; text-align: center;">
	      <img class="scale" src="./pix/func_call.png" style="height: 6em;">
	      </td>
	    <td style="margin-left:auto; margin-right: auto; text-align: center;">
		<img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
	      </td>
	    </tr>
	</table>
	  <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>Continuation based C </h1>
<table width=100% border=1>
<caption><small>階乗を求めるCbCのプログラム</small></caption>
<tr class="srctr">
<td width=50%>
	  <pre class="srcbox">

__code print_factorial(int prod) {
  printf("factorial = %d\n",prod);
  exit(0); 
}

__code factorial0(int prod, int x) {
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
  }else{
    goto print_factorial(prod);
  } 
}
	  </pre>
</td>
<td>
<pre class="srcbox">

__code factorial(int x) {
  goto factorial0(1, x); 
}

int main(int argc, char **argv) {
  int i;
  i = atoi(argv[1]);
  goto factorial(i); 
  return 0;
}
</pre>
</td>
</tr>
</table>
	<ul>
	  <li><small>__code キーワードによるコードセグメントの宣言</small></li>
	  <li><small>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</small></li>
	</ul>
	<li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>GCC</h1>
	<li>GCC:Gnu Compiler Collection</li>
	  <ul>
	    <li><small>GCCの中でも変更を加えた部分はソースコードをアセンブラに変換するcc1になる。</small></li>
	    <li><small>cc1ではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</small></li>
	  <ul>
	    <li>Generic Tree</li>
	    <li>GIMPLE</li>
	    <li>Tree SSA</li>
	    <li>RTL</li>
	  </ul>
<!--
	<li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
-->
	<li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
	  </ul>
      </div>
      <!-- PAGE -->
<!--
      <div class="slide">
	<h1>GCC:Generic Tree</h1>
	<li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
	<table class="center" width=100%  border=1>
	  <tr>
	    <td></td>
	    <td><small>値の代入:MODIFY_EXPR</small></td>
	    <td><small>関数呼び出し:CALL_EXPR</small></td>
	  </t>
	  <tr>
	    <td>命令</td>
	    <td>b = a * 10</td>
	    <td>func(a,10)</td>
	  </t>
	  <tr>
	    <td><small>Generic<br>Tree</small></td>
	  <td>
	    <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
	  </td>
	  <td>
	    <img src="./pix/CALL_EXPR.png" style="height: 7em;">
	  </td>
	  </tr>
	</table>
	  <p class="center"><small>Generic Treeでの表現</small></p>
      </div>
-->
      <!-- PAGE -->
      <div class="slide">
	<h1>GCC:Generic Tree</h1>
	<li><small>CALL_EXPRE、MODIFY_EXPR、RETURN_EXPR等といった表現で扱われる。</small></li>
	<table width=100% border=1>
	  <tr>
	    <td class="center"><small>ソースコード</small></td>
	    <td class="center"><small>Generic Treeでの表現</small></td>
	  </tr>
	  <tr>
	    <td>
	<small>
	<pre>
int main() {
  int a, b;
  a = 3;
  b = func(a, 10);
  return b;
}
	</pre>
	</small>
	</td>
	    <td style="margin-left:auto; margin-right:auto; text-align: center;">
	  <img src="./pix/STATEMENT_LIST.png" style="height: 7em;">
	  </td>
	  </tr>
	    </table>
	  <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
      </div>
      <!-- PAGE -->
<!--
      <div class="slide">
	<h1>GCC</h1>
	<li>GCC についての簡単な説明を行う...</li>
	<li>TODO: NEXT_PASS() の把握</li>
	<img src="./pix/ir.png" style="height: 6em;">
	<li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li>
      </div>
-->
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装</h1>
	<ul>
	  <li>シンタックスの追加</li>
	  <li>継続処理の実装</li>
<!--
	  <li>末尾除去:Tail Call Elimination(TCE)</li>
-->
	  <li>レジスタによる引数渡し(fastcall属性の付与)</li>
     	  <li>環境付き継続</li>
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:__codeシンタックスの追加</h1>
	<ul>
	  <li>__code キーワードでのコードセグメントの宣言</li>
	  <ul>
	    <li>__code 用idとkeywordを作成。</li>
	    <li>通常の関数作成と基本同じだが、コードセグメント判定用のフラグを立てる。</li>
	  </ul>
	</ul>
	  <table width=100% border=1>
	    <tr class="srctr">
	      <td>
	      <pre class="srcbox" style="height:13em">
tree
build_code_segment_type (tree value_type, tree arg_types)
{
  tree t;
  hashval_t hashcode = 0;

  gcc_assert (TREE_CODE (value_type) == VOID_TYPE);

  /* Make a node of the sort we want.  */
  t = make_node (FUNCTION_TYPE);
  TREE_TYPE (t) = value_type;
  TYPE_ARG_TYPES (t) = arg_types;

  CbC_IS_CODE_SEGMENT (t) = 1;

  if (!COMPLETE_TYPE_P (t))
    layout_type (t);
  return t;
}
	      </pre>
	      </td>
	    </tr>
	    </table>
	  <li><small>コードセグメントはGCC内部では関数として扱われる。</small></li>
      </div>

      <!-- SOURCE -->
<!--
const struct c_common_resword c_common_reswords[] =
{
 { "_Bool",            RID_BOOL,      D_CONLY },
     :
 { "__code",         RID_CbC_CODE,   0 },		
...

case RID_CbC_CODE:     
      :
 specs->typespec_word = cts_CbC_code;		
...

case cts_CbC_code: 
       :
     specs->type = void_type_node; 
     break;
-->
      <!--PAGE-->
      <div class="slide">
	<h1>CbCの実装:gotoシンタックスの追加</h1>
	  <li>goto によるコードセグメントへの継続</li>
	  <ul>
	    <li>通常の goto の構文にコードセグメントへ継続する処理を追加。</li>
<!--
	    <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
-->
	  </ul>
	<table width=100% border=1>
	  <tr>
	    <td>
	  <pre class="srcbox" style="font-size:25px; height:20em;" >
 case RID_GOTO:
   c_parser_consume_token (parser);
   if ( c_parser_next_token_is (parser, CPP_NAME)
	&& c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
     {
          :
     }
#ifndef noCbC
   else
     {
       if (c_parser_next_token_is (parser, CPP_NAME))
	 {
	   tree id = c_parser_peek_token (parser)->value;
	   location_t loc = c_parser_peek_token (parser)->location;
	   /** build_external_ref (id,RID_CbC_CODE , loc); **/
	   build_external_ref (loc, id, RID_CbC_CODE, &expr.original_type);
	 }
       expr = c_parser_expr_no_commas (parser, NULL);
       if (TREE_CODE(expr.value) == CALL_EXPR )
	 {
	   location_t loc = c_parser_peek_token (parser)->location;
	   cbc_replace_arguments (loc, expr.value);
	   TREE_TYPE(expr.value) = void_type_node;
	   CbC_IS_CbC_GOTO (expr.value) = 1;
	   CALL_EXPR_TAILCALL (expr.value) = 1;
	   add_stmt(expr.value);
	   stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
	 }
       else
	 c_parser_error (parser, "expected code segment jump or %<*%>");
     }
#else
	</pre>
	  </td>
	    </tr>
	  </table>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:gotoシンタックスの追加</h1>
	<ul>
	<small>
	    <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
	    <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
	    <li>最後にc_finish_return関数によりreturn文を生成している。</li>
	</small>
	</ul>
	<table border=1 width=100%>
<!--
	  <caption><small>return 自動生成</small></caption>
-->
	  <tr class="center">
	  <td><small>実際のコード</small></td>
	  <td><small>GCC内で処理されるコード</small></td>
	  </tr>
	  <tr class="srctr">
	  <td>
	    <pre>

__code test() {
   :
  goto factorial0(1, x); 
}
	    </pre>
	  </td>
	  <td>
	    <pre>

void test() {
   :
  factorial0(1, x); 
  return;
}
	    </pre>
	  </td>
	  </tr>
	</table>
	<ul>
	  <li><small>これで__codeによるコードセグメントの宣言と、gotoによる関数呼び出しが行われるようになった。</small></li>
	  <li class="incremental"><small>次に、コードセグメントへの関数呼び出しは軽量継続で行わせる処理がいる。</small></li>
<!--
	  <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
	  <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
-->
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:軽量継続(末尾除去)</h1>
	<h2>軽量継続は<font color=red>末尾除去(Tail Call elimination)</font>によって実装される。</h2>
	<ul>
	  <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
	</ul>
	<li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
	<br>
	<table width=100%>
	  <tr class="srctr">
	  <td width=50%>
<!--
	<pre class="srcbox">
int main() {
  int num = a(2);
  printf("main:num=%d\n",num);
  return 0;
}
int a(int num) {
  return b(num+5);
}
int b(int num) {
  printf("b:a = %d\n",num);
  return num+3;
}	  
	</pre>
-->
          <pre class="srcbox">

void f(int a, int b) {
  printf("f: a=%d b=%d\n",a,b);
  return ;
}
void g(int a, int b){
  printf("g: a=%d b=%d\n",a,b);
  f(a,b);
  return;
}

int main() {
  g(3,4);
  return 0;
}
	    
	  </pre>
	  </td>
	  <td class="center">
	    <img src="./pix/continuation.png" style="height:90%;">
	    </td>
	    </tr>
	</table>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:軽量継続(末尾除去)</h1>
	<ul>
	<li>末尾除去にかかる条件</li>
	<ul>
	  <li>caller側とcallee側の戻値の型の一致している。</li>
	  <li>関数呼び出しがリターン直前に行われている。</li>
	  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
	  <li>引数の並びのコピーに上書きがない。</li>
	</ul>
	<li class="incremental">条件を回避する為以下の実装にする。</li>
	<ul class="incremental">
	  <li>コードセグメントの型はvoid型で統一する。</li>
	  <li>gotoの直後にreturnを置く。</li>
	  <li>スタックサイズは固定にする。</li>
	  <li>引数は一旦、一時変数にコピーする。</li>
	</ul>
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:軽量継続(末尾除去)</h1>
	<li>末尾除去の条件はexpand_call関数で調べられる。</li>
	<ul>
	  <li>expand_call関数</li>
	<ul>
	  <li>SSAへの変換を終えたGIMPLEにあるCALL_EXPREのTreeからRTLを生成する関数</li>
	  <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
	  <li>try_taill_call(局所変数)フラグがあり、末尾除去の条件に合わなければこのフラグが落とされる。</li>
	</ul>
	<li class="incremental">具体的な実装内容</li>
	<ul>
	  <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
	  <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
	</ul>
	<ul>

      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:軽量継続(末尾除去)</h1>
	<ul>
	<li><small>try_tail_callフラグを落とさせない。</small></li>
	<pre class="srcbox" style="font-size:28px;">
  if (currently_expanding_call++ != 0
      || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))) 
         && !flag_optimize_sibling_calls)
      || args_size.var
      || dbg_cnt (tail_call) == false)
    try_tail_call = 0;
	</pre>
	<ul>
<!--
	  <li>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</li>
-->
	</ul>
	<li><small>try_tail_callフラグ矯正付与のソースコード</small></li>
	  <pre class="srcbox" style="font-size:28px;">
  if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
      && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
      && try_tail_call == 0)
    {
      location_t loc = EXPR_LOCATION (exp);
      char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
      warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
                        name_callee);
      try_tail_call = 1;
    }
	</pre>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:軽量継続(末尾除去)の実装について</h1>
	<ul>
	  <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
	  <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
	  <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
	</ul>
      </div>
      <!-- PAGE -->
<!--
      <div class="slide">
	<h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
	<p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
	    とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
      </div>
-->
       <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:引数渡し</h1>
	<li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
	<ul>
	  <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
	</ul>
	<li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:引数渡し(fastcall)</h1>
	<h2>fastcall</h2>
	<ul>
	  <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
	  <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
	</ul>
	<li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
	<small>
	<pre>
if(!TARGET_64BIT) {
  attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 
  declspecs_add_attrs(specs, attrs);
 }	  
	</pre>
	</small>
	<p><small>Intel64 ではレジスタが増えていてfastcallの機能は標準でつくようになっている。</small></p>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:引数渡し</h1>
	<ul>
	  <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
	</ul>
	<br>
	  <br>
	<table width=100% border=1 class="center">
	  <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
	  <tr>
	    <td>arch</td>
	    <td>int(整数型)</td>
	    <td>float(浮動小数点型)</td>
	    <td>double(浮動小数点型)</td>
	  </tr>
	  <tr>
	    <td>i386</td>
	    <td>2</td>
	    <td>0<br>(stackを使用)</td>
	    <td>0<br>(stackを使用)</td>
	  </tr>
	  <tr>
	    <td>x64</td>
	    <td>6</td>
	    <td>8</td>
	    <td>8</td>
	  </tr>
	</table>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:環境付き継続</h1>
	<ul>
	<li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
	<li>__returnキーワードを引数に渡すことで使うことができる。</li>
	</ul>
	<li>以下の使い方の場合は1を返す。</li>
	<table border=1 width=100%>
	    <td>
	<small>
	    <pre class="srcbox">
__code c1(__code ret(int,void *),void *env) {
 goto ret(1,env);
}
int main() {
 goto c1(__return, __environment);
}
	</pre>
	    </small>
	</td>
	    </table>
	<p><small>__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。</small></p>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの実装:環境付き継続</h1>
<!--
	<li><small>生成しているコードと生成する為のコード</small></li>
-->
	<table border=1 width=100%>
	  <tr>
	    <td><small>生成しているコード</small></td>
	    <td><small>生成するコード(GCC内部)</small></td>
	  </tr>
	  <tr class="srctr">
	    <td width=50% class="srctd">
	  <pre class="srcbox" style="width:25em;">

//goto c1(__return, __environment);
goto c1(({
	  __label__ _cbc_exit0;
	  static int retval;
	  void _cbc_internal_return(int retval_, void *_envp) {
	    retval = retval_;
	    goto _cbc_exit0; 
          }
	  if (0) { 
            _cbc_exit0:
	    return retval; 
          }
	  _cbc_internal_return;
	}), __environment);
	  </pre>
	    </td>
	    <td class="srctd">
	      <pre class="srcbox" style="width:25em;">

    case RID_CbC_RET:
{
  tree value, stmt, label, tlab, decl;
  c_parser_consume_token (parser);

  stmt = c_begin_stmt_expr ();
  cbc_return_f = c_parser_peek_token (parser)->value;
  location_t location = c_parser_peek_token (parser)->location;

  /* create label. (__label__ _cbc_exit0;) */
  label = get_identifier ("_cbc_exit0");
  tlab = declare_label (label);
  C_DECLARED_LABEL_FLAG (tlab) = 1;
  add_stmt (build_stmt (location, DECL_EXPR, tlab));

  /* declare retval.  (int retval;) */
  tree decl_cond =
    build_decl (location, VAR_DECL, get_identifier ("retval"),
		TREE_TYPE (TREE_TYPE (current_function_decl)));
  TREE_STATIC (decl_cond) = 1;
  TREE_USED (decl_cond) = 1;

  /* Use thread-local */
  DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
  DECL_NONLOCAL (decl_cond) = 1;
  add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));

  /* define nested function.  */
  decl =
    cbc_finish_nested_function (location, label, decl_cond);
  TREE_USED(decl) = 1;

  /* define if-ed goto label and return statement. */
  cbc_finish_labeled_goto (location, label, decl_cond);

  /* get pointer to nested function.  */
  value = build_addr (decl , current_function_decl);
  TREE_USED (current_function_decl) = 1;
  SET_EXPR_LOCATION (value, location);
  add_stmt (value);

  TREE_SIDE_EFFECTS (stmt) = 1;
  expr.value = c_finish_stmt_expr (location, stmt);
  expr.original_code = ERROR_MARK;
}
			 </pre>
	    </td>
	    </td>
	  </tr>
	  </table>
	  <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
<!--
	<li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
-->
      </div>
      <!-- PAGE -->
      <!-- PAGE -->
      <div class="slide">
	<h1>環境付き継続:実装の問題</h1>
	<li>重要な部分</li>
	<ul>
	  <li>リターンするretval変数のメモリ確保</li>
	</ul>
	<li>次の方法が考えられる。</li>
	<ul>
	  <li>クロージャでの確保</li>
	  <li>staticでの確保</li>
	  <li>static thread local storage(tls)を用いての確保</li>
<!--
	  <li>setjmpを用いての実装</li>
	  <li>戻り値を入れるレジスタを明示的に指定</li>
-->
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>環境付き継続:実装の問題</h1>
	<ul>
	  <li>クロージャでの実装の問題点:</li>
	  <!--	<ul><li>クロージャにしてスタックに値を確保する。</li></ul>	  -->
          <ul>
	    <li >CbCでは継続によりスタックの値は破棄されていく。</li>
	    <li >クロージャにしたコードが破棄される可能性がある。</li>
	  </ul>

	  <li>staticでの実装の問題点:</li>
	  <!--	<ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
	  <ul>
	    <li >マルチスレッドのプログラムに対応できない。</li>
	    <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
	  </ul>
	<li class="incremental">static tlsでの実装</li>
	<!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
	<ul class="incremental">
	<li>現在はこの方法で実装を行なっている。</li>
	<li>しかし、最適化にかけると正しい値が返ってこない。
	  <br>(最適化によりコードが削除されている...?)</li>
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>クロージャの動作について</h1>
	<li>予稿における訂正</li>
	<li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
	<ul>
	  <li>CbCの末尾除去矯正付与のせいでクロージャが破壊されていたことが判明。</li>
	  <li>GCC 4.6 と Lion でのクロージャは特に問題はなかった。</li>
	</ul>
      </div>
      <!-- PAGE -->
<!--
      <div class="slide">
	<h1>環境付き継続:実装の問題</h1>
	<ul>
	  <li>setjmpでの実装の問題点:</li>
	  <ul>
	    <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
	    <li>int型の戻値しか得られない。</li>
	  </ul>

	</ul>
	<li>戻値を入れるレジスタを明示的に指定する。</li>
	<ul>
	  <li>まだ実装を試していない。</li>
	</ul>
	</ul>
      </div>
-->
      <!-- PAGE -->
      <div class="slide">
	<h1>Micro-Cとの比較</h1>
	<table width=100% class="center">
	<caption><small>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</small></caption>
	  <td>
	    <img src="./pix/mac_conv.png" style="height:10em">
	  </td>
	  <td>
	    <img src="./pix/linux_conv.png" style="height:10em">
	  </td>
	  </table>
	  <li><small>最適化無しだと、引数を全て一時変数に代入するGCCは遅い。
	      だが、最適化にかければ不要な代入は減りMicro-C版より早くなる。</small></li>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>まとめ</h1>
	  <ul>
	    <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
	    <li>末尾除去にかかる判定の部分の実装の修正を行った。
	      <br>それにより、以前より楽な管理ができる実装にすることができた。</li>
	    <li>後は環境付き継続の最適化の問題の修正とselftypeといった新しい実装を行う。</li>
	    <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
	    </ul>
	</div>
      <!-- PAGE -->
      <div class="slide">
	<h1>今後の課題</h1>
	<ul>
     	  <li>CbCを用いたプログラムの作成</li>
	  <ul>
	    <li>CbCによるタスクマネージャの作成</li>
	  </ul>
	  <li>llvmへのCbCの実装</li>
	</ul>
	<br>
	<h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
	</div>
      <!-- PAGE -->
      <div class="slide">
	<h1>CbCの引数渡し</h1>
	<table border=1 width=100%>
	  <caption><small>fastcall属性有・無の実行速度</small></caption>
	  <tr class="center">
	    <td width=50%><small>fastcall有り</small></td>
	    <td width=50%><small>fastcall無し</small></td>
	  </tr>
	  <tr class="center">
	    <td>
	      <img src="./pix/linux_conv_fastcall.png">
	    </td>
	    <td>
	      <img src="./pix/linux_conv_nofastcall.png">
	    </td>
	  </tr>
	    </table>
	</div>
      <!-- PAGE -->
      <div class="slide">
	<h1>軽量継続(末尾除去)の動作</h1>
	<li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
	<table width=100% border=1>
	  <td>
	  <p class="center">
	    <img src="./pix/tce.png" style="height: 6em;">
	    </p>
	    </td>
	  <td>
	    <ul>
	    <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
	    <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
	    </ul>
	  </td>
	    </table>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>call_insn</h1>
	<li>expand_callより作成されたRTLのTreeは以下のS式となる。</li>
	<pre class="srcbox" style="font-size:28px; width:45em;">

(call_insn/j 18 17 19 3 (call (mem:QI (symbol_ref:DI ("factorial") [flags 0x403]  &lt;function_decl 0x1443b4400 factorial&gt;) [0 S1 A8])
        (const_int 1024 [0x400])) factorial.cbc:30 -1
     (expr_list:REG_EH_REGION (const_int 0 [0])
        (nil))
    (expr_list:REG_DEP_TRUE (use (reg:SI 5 di))
        (nil)))
	</pre>
	<li></li>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>__rectype の実装</h1>
	<ul>
	<li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
	<pre style="font-size:28px;">
void factorial(int n, int result, void(*print)()){
   :
   (*print)(n,result,print,exit1, envp);
}
	</pre>
	<li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
	<pre style="font-size:28px;">
__code factorial(int n, int result, __rectype *print) {
   :
   goto (*print)(n,result,print,exit1, envp);
}
	</pre>
	</ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>selftype</h1>
	<h2>selftypeの実装</h2>
	<li>以下の宣言が行えるようにしたい。</li>
	<small>
	<pre>
typedef sturct node {
 selftype *left;
 selftype *right;
 int num;
}*NODE
	</pre>
	<p>selftype は struct node を指す。</p>
	</small>
      </div>
      <!-- PAGE -->
      <div class="slide">
	<h1>環境付き継続</h1>
	<table border=1 width=100%>
	  <tr>
	    <td width=50%><small>生成する為のコード</small></td>
	    <td width=50%><small>生成されるTree</small></td>
	  </tr>
	  <tr class="srctr">
	    <td class="srctd">
	      <pre class="srcbox" style="width:25em;">

    case RID_CbC_RET:
{
  tree value, stmt, label, tlab, decl;
  c_parser_consume_token (parser);

  stmt = c_begin_stmt_expr ();
  cbc_return_f = c_parser_peek_token (parser)->value;
  location_t location = c_parser_peek_token (parser)->location;

  /* create label. (__label__ _cbc_exit0;) */
  label = get_identifier ("_cbc_exit0");
  tlab = declare_label (label);
  C_DECLARED_LABEL_FLAG (tlab) = 1;
  add_stmt (build_stmt (location, DECL_EXPR, tlab));

  /* declare retval.  (int retval;) */
  tree decl_cond =
    build_decl (location, VAR_DECL, get_identifier ("retval"),
		TREE_TYPE (TREE_TYPE (current_function_decl)));
  TREE_STATIC (decl_cond) = 1;
  TREE_USED (decl_cond) = 1;

  /* Use thread-local */
  DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
  DECL_NONLOCAL (decl_cond) = 1;
  add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));

  /* define nested function.  */
  decl =
    cbc_finish_nested_function (location, label, decl_cond);
  TREE_USED(decl) = 1;

  /* define if-ed goto label and return statement. */
  cbc_finish_labeled_goto (location, label, decl_cond);

  /* get pointer to nested function.  */
  value = build_addr (decl , current_function_decl);
  TREE_USED (current_function_decl) = 1;
  SET_EXPR_LOCATION (value, location);
  add_stmt (value);

  TREE_SIDE_EFFECTS (stmt) = 1;
  expr.value = c_finish_stmt_expr (location, stmt);
  expr.original_code = ERROR_MARK;
}
			 </pre>
	    </td>


	    <td class="srctd">
	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
	    </td>

	  </tr>
	</table>
      </div>
	<!--PAGE-->
	<div class="slide">
	  <h1>環境付き継続</h1>
	<table border=1 width=100%>
	  <tr>
	    <td><small>生成しているコード</small></td>
	    <td><small>生成されるTree</small></td>
	  </tr>
	  <tr class="srctr">
	    <td width=50% class="srctd">
	  <pre class="srcbox" style="width:25em;">

//goto c1(__return, __environment);
goto c1(({
	  __label__ _cbc_exit0;
	  static int retval;
	  void _cbc_internal_return(int retval_, void *_envp) {
	    retval = retval_;
	    goto _cbc_exit0; 
          }
	  if (0) { 
            _cbc_exit0:
	    return retval; 
          }
	  _cbc_internal_return;
	}), __environment);
	  </pre>
	    </td>
	    <td class="srctd">
	      <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
	    </td>
	    </tr>
	  </table>
	</div>
	<!--PAGE-->
	<div class="slide">
	  <h1>引数の並びに上書きコピー</h1>
	  <pre style="font-size:28px;">
__code cs_a(int a, int b) {
  goto cs_b(b,a);
}
	  </pre>
	  <img src="./pix/cs_prog.png">
	</div>
	<!--PAGE-->
	<div class="slide">
	  <h1>スタックサイズ固定</h1>
	  <li>expand_call関数にて</li>
	  <pre style="font-size:28px;">
args_size.constant = CbC_PRETENDED_STACK_SIZE;	    
	  </pre>
	</div>
	<!--PAGE-->

</div>
</body>
</html>