Mercurial > hg > Papers > 2011 > nobu-prosym
annotate presen/index.html @ 64:743afe406e56
modify
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 29 Dec 2011 00:38:32 +0900 |
| parents | 3cc4a8603489 |
| children | 26a3713b2989 |
| rev | line source |
|---|---|
| 54 | 1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" |
| 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> | |
| 3 | |
| 4 <html xmlns="http://www.w3.org/1999/xhtml"> | |
| 5 | |
| 6 <head> | |
| 7 <style> | |
| 64 | 8 .src{ |
| 9 overflow: scroll; | |
| 10 width: 90%; | |
| 11 height: 60%; | |
| 12 } | |
| 54 | 13 .center { |
| 14 margin-left: auto; | |
| 15 margin-right: auto; | |
| 16 text-align: center; | |
| 17 } | |
| 18 .textcenter { | |
| 19 text-align: center; | |
| 20 } | |
| 21 .taninaritop { | |
| 22 margin: auto; | |
| 23 width: 95%; | |
| 24 font-weight: bold; | |
| 25 } | |
| 26 </style> | |
| 27 <title>2012/ 1/ 7</title> | |
| 28 <!-- metadata --> | |
| 29 <meta name="generator" content="S5" /> | |
| 30 <meta name="version" content="S5 1.1" /> | |
| 31 <meta name="presdate" content="20120107" /> | |
| 32 <meta name="author" content="Nobuyasu Oshiro" /> | |
| 33 <meta name="company" content="University of the Ryukyu" /> | |
| 34 <!-- meta temporary --> | |
| 35 <meta http-equiv="content-type" content="text/html; charset=utf-8" /> | |
| 36 <meta http-equiv="Content-Script-Type" content="text/javascript" /> | |
| 37 <meta http-equiv="Content-Style-Type" content="text/css" /> | |
| 38 <!-- configuration parameters --> | |
| 39 <meta name="defaultView" content="slideshow" /> | |
| 40 <meta name="controlVis" content="hidden" /> | |
| 41 <!-- configuration extensions --> | |
| 42 <meta name="tranSitions" content="true" /> | |
| 43 <meta name="fadeDuration" content="500" /> | |
| 44 <meta name="incrDuration" content="250" /> | |
| 45 <!-- configuration autoplay extension --> | |
| 46 <meta name="autoMatic" content="false" /> | |
| 47 <meta name="playLoop" content="true" /> | |
| 48 <meta name="playDelay" content="10" /> | |
| 49 <!-- configuration audio extension --> | |
| 50 <meta name="audioSupport" content="false" /> | |
| 51 <meta name="audioVolume" content="100" /> | |
| 52 <meta name="audioError" content="false" /> | |
| 53 <!-- configuration audio debug --> | |
| 54 <meta name="audioDebug" content="false" /> | |
| 55 <!-- style sheet links --> | |
| 56 <link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" /> | |
| 57 <link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" /> | |
| 58 <link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" /> | |
| 59 <link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" /> | |
| 60 <!-- embedded styles --> | |
| 61 <style type="text/css" media="all"> | |
| 62 .imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;} | |
| 63 #anim {width: 33%; height: 320px; position: relative;} | |
| 64 #anim img {position: absolute; top: 0px; left: 0px;} | |
| 65 </style> | |
| 66 <!-- S5 JS --> | |
| 67 <script src="ui/default_utf/slides.js" type="text/javascript"></script> | |
| 68 </head> | |
| 69 <body> | |
| 70 | |
| 71 <div class="layout"> | |
| 72 <div id="controls"><!-- DO NOT EDIT --></div> | |
| 73 <div id="currentSlide"><!-- DO NOT EDIT --></div> | |
| 74 <div id="header"></div> | |
| 75 <div id="footer"> | |
| 76 <h1>プログラミングシンポジウム: 2012/ 1/ 7</h1> | |
| 77 <h2>並列信頼研</h2> | |
| 78 </div> | |
| 79 </div> | |
| 80 | |
| 81 <div class="presentation"> | |
| 82 | |
| 83 <div class="slide"> | |
| 84 <h1>Continuation based Cの GCC 4.6 上の実装について</li> | |
| 85 <h3></h3> | |
| 86 <li>大城 信康</li> | |
| 87 <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4> | |
| 88 <div class="handout"></div> | |
| 89 </div> | |
| 90 <!-- PAGE --> | |
| 91 <div class="slide"> | |
| 92 <h1>目的と背景(1)</h1> | |
| 93 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> | |
| 94 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> | |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
95 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li> |
| 54 | 96 </div> |
| 97 <!-- PAGE --> | |
| 98 <div class="slide"> | |
| 99 <h1>目的と背景(2)</h1> | |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
100 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
101 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> |
| 58 | 102 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> |
| 54 | 103 </div> |
| 104 <!-- PAGE --> | |
| 105 <div class="slide"> | |
| 106 <h1>発表内容</h1> | |
| 107 <ol> | |
| 108 <li>CbC の紹介</li> | |
| 109 <li>GCC でのコンパイルの流れ</li> | |
| 58 | 110 <font color="red"> |
| 111 <li>CbC の実装</li> | |
| 112 </font> | |
| 54 | 113 <!-- |
| 114 <ul> | |
| 115 <li>Tail Call Elimination</li> | |
| 116 <li>goto シンタックスの追加</li> | |
| 117 <li>環境付き継続</li> | |
| 118 </ul> | |
| 119 --> | |
| 120 <li>Micro-C との性能比較</li> | |
| 64 | 121 <!-- |
| 54 | 122 <li>mercurial を用いたアップデートの方法</li> |
| 64 | 123 --> |
| 54 | 124 <li>まとめ</li> |
| 125 <ol> | |
| 126 </div> | |
| 127 <!-- PAGE --> | |
| 128 <div class="slide"> | |
| 129 <h1>Continuation based C </h1> | |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
131 <ul> |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
132 <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
133 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
134 <br> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
135 <h2>コードセグメント</h2> |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
136 <ul> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
137 <li>C の関数よりも細かい単位。</li> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
138 <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
139 </ul> |
| 54 | 140 </div> |
| 141 <!-- PAGE --> | |
| 142 <div class="slide"> | |
| 58 | 143 <h1>Continuation Based C</h1> |
| 144 <h2>継続:現在の処理を実行していく為の情報</h2> | |
| 145 <!-- | |
| 146 <li>Cでは関数呼び出しの後、呼び出し元の環境に復帰する必要がある。</li> | |
| 147 --> | |
| 148 <li>Cにおいての継続</li> | |
| 149 <ul> | |
| 150 <li>続く命令のアドレス</li> | |
| 151 <li>命令に必要なデータ</li> | |
| 152 <li>スタックに積まれている値(環境)</li> | |
| 153 </ul> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
154 </div> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
155 <!-- PAGE --> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
156 <div class="slide"> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
157 <h1>Continuation Based C (軽量継続)</h1> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
158 <h2>CbCの継続(軽量継続)</h2> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
159 <li>関数コールが無い -> 呼び出し元への復帰がない</li> |
| 58 | 160 <ul> |
|
59
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
161 <li>Cの継続から環境を除外</li> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
162 <li>続く命令とその命令に必要なデータのみ</li> |
| 58 | 163 </ul> |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
164 <!-- <li>継続の際にスタックに載せるデータはコードセグメントへの引数だけとなる。</li> --> |
|
59
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
165 <!-- <li>スタックポインタの位置を変えずにすむ。</li> --> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
166 <p style=" margin-right:auto; margin-left:auto;"> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
167 <img class="scale" src="./pix/cs_stack.png" style="height: 7em;"> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
168 </p> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
169 </div> |
|
6ef99d3e66b2
modify light-weight continuation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
58
diff
changeset
|
170 <!-- PAGE --> |
| 58 | 171 <div class="slide"> |
| 54 | 172 <h1>Continuation based C </h1> |
| 173 <small> | |
| 174 <table width=100% > | |
| 175 <tr> | |
| 176 <caption>階乗を求めるCbCのプログラム</caption> | |
| 177 <td width=50%> | |
| 178 <pre> | |
| 179 __code print_factorial(int prod) { | |
| 180 printf("factorial = %d\n",prod); | |
| 181 exit(0); | |
| 182 } | |
| 58 | 183 |
| 54 | 184 __code factorial0(int prod, int x) { |
| 185 if ( x >= 1) { | |
| 186 goto factorial0(prod*x, x-1); | |
| 187 }else{ | |
| 188 goto print_factorial(prod); | |
| 189 } | |
| 190 } | |
| 191 </pre> | |
| 192 </td> | |
| 193 <td> | |
| 194 <pre> | |
| 195 __code factorial(int x) { | |
| 196 goto factorial0(1, x); | |
| 197 } | |
| 58 | 198 |
| 54 | 199 int main(int argc, char **argv) { |
| 200 int i; | |
| 201 i = atoi(argv[1]); | |
| 202 goto factorial(i); | |
| 203 return 0; | |
| 204 } | |
| 205 </pre> | |
| 206 </td> | |
| 207 </tr> | |
| 208 </table> | |
| 209 </small> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
210 <li>__code キーワードによるコードセグメントの宣言</li> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
211 <li>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</li> |
| 54 | 212 </div> |
| 213 <!-- PAGE --> | |
| 214 <div class="slide"> | |
| 215 <h1>GCC によるコンパイル</h1> | |
| 216 <li>GCC についての簡単な説明を行う...</li> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
217 <li>TODO: NEXT_PASS() の把握</li> |
| 54 | 218 <img src="./pix/ir.png" style="height: 6em;"> |
| 219 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li> | |
| 220 </div> | |
| 221 <!-- PAGE --> | |
| 222 <div class="slide"> | |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
223 <h1>CbCの実装</h1> |
| 54 | 224 <ul> |
| 225 <li>シンタックスの追加</li> | |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
226 <li>レジスタによる引数渡し(fastcall属性の付与)</li> |
| 54 | 227 <li>Tail Call Elimination</li> |
| 228 <li>環境付き継続</li> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
229 <li>__rectype の実装</li> |
| 54 | 230 </ul> |
| 231 </div> | |
| 232 <!-- PAGE --> | |
| 233 <div class="slide"> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
234 <h1>CbCの実装:シンタックスの追加</h1> |
| 54 | 235 <ul> |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
236 <li>__code キーワードでのコードセグメントの宣言</li> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
237 <ul> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
238 <li>__code 用idとkeywordを作成。</li> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
239 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
240 </ul> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
241 <li>goto によるコードセグメントへの継続</li> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
242 <ul> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
243 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
244 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li> |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
245 </ul> |
| 54 | 246 </ul> |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
247 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> |
| 54 | 248 </div> |
| 249 <!-- PAGE --> | |
| 250 <div class="slide"> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
251 <h1>CbCの実装:シンタックスの追加</h1> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
252 <h2>gotoシンタックスの追加</h2> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
253 <small> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
254 <pre> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
255 expr = c_parser_expr_no_commas (parser, NULL); |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
256 if (TREE_CODE(expr.value) == CALL_EXPR ) |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
257 { |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
258 location_t loc = c_parser_peek_token (parser)->location; |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
259 cbc_replace_arguments (loc, expr.value); |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
260 TREE_TYPE(expr.value) = void_type_node; |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
261 CbC_IS_CbC_GOTO (expr.value) = 1; |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
262 CALL_EXPR_TAILCALL (expr.value) = 1; |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
263 add_stmt(expr.value); |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
264 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
265 } |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
266 </pre> |
|
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
267 </small> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
268 <small> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
269 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
270 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li> |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
271 <li>最後にc_finish_return関数によりreturn文を生成している。</li> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
272 </small> |
| 54 | 273 </div> |
| 274 <!-- PAGE --> | |
| 275 <div class="slide"> | |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
276 <h1>CbCの実装:シンタックスの追加</h1> |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
277 <h2>gotoシンタックスの追加</h2> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
278 <li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li> |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
279 <table border=1 width=100%> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
280 <tr class="center"> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
281 <small> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
282 <td>実際のコード </td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
283 <td>GCC 内で処理されるコード</td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
284 </small> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
285 </tr> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
286 <tr style="margin-top: auto;"> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
287 <td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
288 <pre> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
289 goto factorial0(1, x); |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
290 </pre> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
291 </td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
292 <td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
293 <pre> |
| 58 | 294 factorial0(1, x); |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
295 return; |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
296 </pre> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
297 </td> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
298 </tr> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
299 </table> |
|
60
a21d16da431a
modify addition of goto syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
300 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> |
| 54 | 301 </div> |
| 302 <!-- PAGE --> | |
| 303 <div class="slide"> | |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
304 <h1>CbCの実装:引数渡し</h1> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
305 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> |
| 58 | 306 <ul> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
307 <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li> |
| 58 | 308 </ul> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
309 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li> |
| 58 | 310 </div> |
| 311 <!-- PAGE --> | |
| 312 <div class="slide"> | |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
313 <h1>CbCの実装:引数渡し(fastcall)</h1> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
314 <h2>fastcall</h2> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
315 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
316 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
317 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
318 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
319 <li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li> |
| 58 | 320 <small> |
|
55
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
321 <pre> |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
322 if(!TARGET_64BIT) { |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
323 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
324 declspecs_add_attrs(specs, attrs); |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
325 } |
|
06ce8fb8e278
modify presen/index.html
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
54
diff
changeset
|
326 </pre> |
| 58 | 327 </small> |
| 328 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p> | |
| 329 </div> | |
| 330 <!-- PAGE --> | |
| 331 <div class="slide"> | |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
332 <h1>CbCの実装:引数渡し</h1> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
333 <table width=100% border=1 class="center"> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
334 <caption>引数渡しに使われるレジスタの数(gcc)</caption> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
335 <tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
336 <td>arch</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
337 <td>int(整数型)</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
338 <td>float(浮動小数点型)</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
339 <td>double(浮動小数点型)</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
340 </tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
341 <tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
342 <td>i386</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
343 <td>2</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
344 <td>0<br>(stackを使用)</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
345 <td>0<br>(stackを使用)</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
346 </tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
347 <tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
348 <td>x86_64</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
349 <td>6</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
350 <td>8</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
351 <td>8</td> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
352 </tr> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
353 </table> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
354 </div> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
355 <!-- PAGE --> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
356 <div class="slide"> |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
357 <h1>CbCの実装:TCE</h1> |
|
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
358 <h2>Tail Call Elimination(TCE):末尾除去</h2> |
| 62 | 359 <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li> |
| 360 <img src="./pix/continuation.png" style="height: 7em;"> | |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
361 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
362 </div> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
363 <!-- PAGE --> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
364 <div class="slide"> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
365 <h1>CbCの実装:TCE</h1> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
366 <li>TCEにより関数へjmp命令で処理を移すことを利用。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
367 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
368 <br> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
369 <h2>具体的な実装内容</h2> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
370 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
371 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
372 <li class="incremental">try_tail_callフラグを落とさせない。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
373 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
374 <li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li> |
| 54 | 375 </div> |
| 376 <!-- PAGE --> | |
| 377 <div class="slide"> | |
|
61
2c543a47737b
modify explanation of fastcall
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
60
diff
changeset
|
378 <h1>CbCの実装:TCE</h1> |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
379 <li>try_tail_callフラグはexpand_call関数で落とされる。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
380 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
381 <li>expand_call関数</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
382 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
383 <li>Treeで表された関数からRTLを生成する関数</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
384 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
385 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
386 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
387 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
388 <li>caller側とcallee側の戻値の型の一致している。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
389 <li>関数呼び出しがリターン直前に行われている。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
390 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
391 <li>引数の並びのコピーに上書きがない。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
392 </ul> |
| 54 | 393 </div> |
| 394 <!-- PAGE --> | |
| 395 <div class="slide"> | |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
396 <h1>CbCの実装:TCE</h1> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
397 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
398 <ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
399 <li>void型で統一。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
400 <li>gotoの直後にreturnを置く。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
401 <li>スタックサイズは固定。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
402 <li>引数は一旦、一時変数にコピーする。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
403 </ul> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
404 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
405 </div> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
406 <!-- PAGE --> |
| 64 | 407 <!-- |
|
63
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
408 <div class="slide"> |
|
3cc4a8603489
modify explanation of TCE
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
62
diff
changeset
|
409 <h1>CbCの実装:環境付き継続</h1> |
| 62 | 410 <li>CbCにおけるCとの互換性を保つための機能。</li> |
| 411 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li> | |
| 64 | 412 <li>論文における訂正</li> |
| 413 <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li> | |
| 414 <ul> | |
| 415 <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li> | |
| 416 <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li> | |
| 417 </ul> | |
| 418 </div> | |
| 419 --> | |
| 420 <!-- PAGE --> | |
| 421 <!-- | |
| 422 <div class="slide"> | |
| 423 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1> | |
| 424 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br> | |
| 425 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p> | |
| 426 </div> | |
| 427 --> | |
| 428 <!-- PAGE --> | |
| 429 <div class="slide"> | |
| 430 <h1>CbCの実装:環境付き継続</h1> | |
| 431 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li> | |
| 432 <li>__returnキーワードを引数に渡すことで使うことができる。</li> | |
| 433 <li>以下の使い方の場合は1を返す。</li> | |
| 434 <small> | |
| 435 <pre> | |
| 436 __code c1(__code ret(int,void *),void *env) { | |
| 437 goto ret(1,env); | |
| 438 } | |
| 439 int main() { | |
| 440 goto c1(__return, __environment); | |
| 441 } | |
| 442 </pre> | |
| 443 </small> | |
| 444 <p><small>__environmentキーワードは関数の環境を保存している。</small></p> | |
| 54 | 445 </div> |
| 446 <!-- PAGE --> | |
| 447 <div class="slide"> | |
| 64 | 448 <h1>CbCの実装:環境付き継続</h1> |
| 449 <h2>実際には以下のコードを生成している。</h2> | |
| 450 <small> | |
| 451 <pre> | |
| 452 goto c1(__return, __environment); | |
| 453 | |
| 454 goto c1( | |
| 455 ({ | |
| 456 __label__ _cbc_exit0; | |
| 457 static int retval; | |
| 458 void _cbc_internal_return(int retval_, void *_envp){ | |
| 459 retval = retval_; | |
| 460 goto _cbc_exit0; } | |
| 461 if (0) { _cbc_exit0: | |
| 462 return retval; } | |
| 463 _cbc_internal_return; | |
| 464 }), | |
| 465 __environment); | |
| 466 </pre> | |
| 467 <p>retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。</p> | |
| 468 </small> | |
| 469 <li class="incremental">上記のコードをGCC内で生成するのが次のソースとなる。</li> | |
| 54 | 470 </div> |
| 471 <!-- PAGE --> | |
| 472 <div class="slide"> | |
| 64 | 473 <h1>CbCの実装:環境付き継続</l> |
| 474 <h2>環境付き継続の生成部分:</h2> | |
| 475 <div class="src"> | |
| 476 <small> | |
| 477 <pre> | |
| 478 { | |
| 479 tree value, stmt, label, tlab, decl; | |
| 480 c_parser_consume_token (parser); | |
| 481 | |
| 482 stmt = c_begin_stmt_expr (); | |
| 483 cbc_return_f = c_parser_peek_token (parser)->value; | |
| 484 location_t location = c_parser_peek_token (parser)->location; | |
| 485 | |
| 486 /* create label. (__label__ _cbc_exit0;) */ | |
| 487 label = get_identifier ("_cbc_exit0"); | |
| 488 tlab = declare_label (label); | |
| 489 C_DECLARED_LABEL_FLAG (tlab) = 1; | |
| 490 add_stmt (build_stmt (location, DECL_EXPR, tlab)); | |
| 491 | |
| 492 /* declare retval. (int retval;) */ | |
| 493 tree decl_cond = | |
| 494 build_decl (location, VAR_DECL, get_identifier ("retval"), | |
| 495 TREE_TYPE (TREE_TYPE (current_function_decl))); | |
| 496 TREE_STATIC (decl_cond) = 1; | |
| 497 TREE_USED (decl_cond) = 1; | |
| 498 | |
| 499 /* Use thread-local */ | |
| 500 DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond); | |
| 501 DECL_NONLOCAL (decl_cond) = 1; | |
| 502 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond))); | |
| 503 | |
| 504 /* define nested function. */ | |
| 505 decl = | |
| 506 cbc_finish_nested_function (location, label, decl_cond); | |
| 507 TREE_USED(decl) = 1; | |
| 508 | |
| 509 /* define if-ed goto label and return statement. */ | |
| 510 cbc_finish_labeled_goto (location, label, decl_cond); | |
| 511 | |
| 512 /* get pointer to nested function. */ | |
| 513 value = build_addr (decl , current_function_decl); | |
| 514 TREE_USED (current_function_decl) = 1; | |
| 515 SET_EXPR_LOCATION (value, location); | |
| 516 add_stmt (value); | |
| 517 | |
| 518 TREE_SIDE_EFFECTS (stmt) = 1; | |
| 519 expr.value = c_finish_stmt_expr (location, stmt); | |
| 520 expr.original_code = ERROR_MARK; | |
| 521 } | |
| 522 </pre> | |
| 54 | 523 </small> |
| 64 | 524 </div> |
| 54 | 525 </div> |
| 526 <!-- PAGE --> | |
| 527 <div class="slide"> | |
| 64 | 528 <h1>CbCの実装:環境付き継続</h1> |
| 529 <h2>作成されるTree</h2> | |
| 530 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;"> | |
| 531 <!-- | |
| 532 <small> | |
| 533 <pre> | |
| 534 ({ | |
| 535 __label__ _cbc_exit0; | |
| 536 static int retval; | |
| 537 void _cbc_internal_return(int retval_, void *_envp){ | |
| 538 retval = retval_; | |
| 539 goto _cbc_exit0; } | |
| 540 if (0) { _cbc_exit0: | |
| 541 return retval; } | |
| 542 _cbc_internal_return; | |
| 543 }), | |
| 544 </pre> | |
| 545 </small> | |
| 546 --> | |
| 547 </div> | |
| 548 <!-- PAGE --> | |
| 549 <div class="slide"> | |
| 550 <h1>環境付き継続:実装の問題</h1> | |
| 551 <ul> | |
| 552 <li>リターンするretval変数が重要になってくる。</li> | |
| 553 <li>retval変数のデータをどうやって確保するか。</li> | |
| 554 </ul> | |
| 555 <li>次の方法が考えられる。</li> | |
| 556 <ul> | |
| 557 <li>クロージャでの確保</li> | |
| 558 <li>staticでの確保</li> | |
| 559 <li>static thread local storage(tls)を用いての確保</li> | |
| 560 </ul> | |
| 561 </div> | |
| 562 <!-- PAGE --> | |
| 563 <div class="slide"> | |
| 564 <h1>環境付き継続:実装の問題</h1> | |
| 565 <li>クロージャでの実装</li> | |
| 54 | 566 <ul> |
| 64 | 567 <li>クロージャにしてスタックに値を確保する。</li> |
| 568 <li></li> | |
| 569 </ul> | |
| 570 <li>問題点</li> | |
| 571 <ul> | |
| 572 <li class="incremental">しかしCbCではスタックの値は破棄されていく。</li> | |
| 573 <li class="incremental">その為スタックに値を確保するのは好ましくない。</li> | |
| 574 </ul> | |
| 575 </div> | |
| 576 <!-- PAGE --> | |
| 577 <div class="slide"> | |
| 578 <h1>環境付き継続:実装の問題</h1> | |
| 579 <li>staticでの実装</li> | |
| 580 <ul> | |
| 581 <li>静的に値を確保することでスタック破棄の影響を受けない。</li> | |
| 582 </ul> | |
| 583 <li>問題点</li> | |
| 584 <ul> | |
| 585 <li class="incremental">マルチスレッドのプログラムに対応できない。</li> | |
| 586 <li class="incremental">値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li> | |
| 54 | 587 </ul> |
| 64 | 588 </div> |
| 589 <!-- PAGE --> | |
| 590 <div class="slide"> | |
| 591 <h1>環境付き継続:実装の問題</h1> | |
| 592 <li>static tlsでの実装</li> | |
| 593 <ul> | |
| 594 <li>スレッド毎に静的に値を確保する。</li> | |
| 595 </ul> | |
| 596 <li>現在はこの方法で実装を行なっている。</li> | |
| 597 <li>しかし、最適化にかけると正しい値が返ってこない。 | |
| 598 <br>(恐らくTreeの生成の部分が間違っている。)</li> | |
| 599 </div> | |
| 600 <!-- PAGE --> | |
| 601 <div class="slide"> | |
| 602 <h1>環境付き継続:その他の実装方法</h1> | |
| 603 <ul> | |
| 604 <li>setjmpでの実装</li> | |
| 605 <ul> | |
| 606 <li>setjmpを行うTreeを生成するのが少し手間になる。</li> | |
| 607 <li>int型の戻値しか得られない。</li> | |
| 608 </ul> | |
| 609 <li>戻値を入れるレジスタを明示的に指定する。</li> | |
| 610 <ul> | |
| 611 <li>まだ実装を試していない。</li> | |
| 612 </ul> | |
| 613 </ul> | |
| 54 | 614 </div> |
| 615 <!-- PAGE --> | |
| 616 <div class="slide"> | |
|
57
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
617 <h1>__rectype の実装</h1> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
618 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
619 <small> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
620 <pre> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
621 void factorial(int n, int result, void(*print)()){ |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
622 : |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
623 (*print)(n,result,print,exit1, envp); |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
624 } |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
625 </pre> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
626 </small> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
627 <li>以下の様に扱えるようにしたい。</li> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
628 <small> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
629 <pre> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
630 void factorial(int n, int result, void *print){ |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
631 : |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
632 (*print)(n,result,print,exit1, envp); |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
633 } |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
634 </pre> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
635 </small> |
| 54 | 636 </div> |
| 637 <!-- PAGE --> | |
| 638 <div class="slide"> | |
|
57
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
639 <h1>__rectype の実装</h1> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
640 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
641 <pre> |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
642 __code factorial(int n, int result, __rectype *print) { |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
643 : |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
644 (*print)(n,result,print,exit1, envp); |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
645 } |
|
ce844f6c504d
modify __rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
646 </pre> |
| 54 | 647 </div> |
| 648 <!-- PAGE --> | |
| 649 <div class="slide"> | |
| 64 | 650 <h1>CbCの機能の拡張</h1> |
| 651 <h2>selftypeの実装</h2> | |
| 652 <li>以下の宣言が行えるようにしたい。</li> | |
| 653 <small> | |
| 654 <pre> | |
| 655 typedef sturct node { | |
| 656 selftype *left; | |
| 657 selftype *right; | |
| 658 int num; | |
| 659 }*NODE | |
| 660 </pre> | |
| 661 <p>selftype は struct node を指す。</p> | |
| 662 </small> | |
| 663 <ul> | |
| 664 <li>上記の構文は実装を行う予定である。</li> | |
| 665 </ul> | |
| 666 </div> | |
| 667 <!-- PAGE --> | |
| 668 <div class="slide"> | |
| 54 | 669 <h1></h1> |
| 670 <li></li> | |
| 671 </div> | |
| 672 <!-- PAGE --> | |
| 64 | 673 <div class="slide"> |
| 674 <h1></h1> | |
| 675 <li></li> | |
| 676 </div> | |
| 677 <!-- PAGE --> | |
| 678 <div class="slide"> | |
| 679 <h1>まとめ</h1> | |
| 680 <li>今回GCC版CbCコンパイラのアップデートを行った。</li> | |
| 681 <li>アップデートに伴いTCEの条件クリアや環境付き継続といった部分の修正と機能の拡張も行った。</li> | |
| 682 <li></li> | |
| 683 </div> | |
| 684 <!-- PAGE --> | |
| 54 | 685 </div> |
| 686 </body> | |
| 687 </html> |