Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 63:3cc4a8603489

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 Wed, 28 Dec 2011 04:53:23 +0900
parents 7087484574b0
children 743afe406e56
comparison
equal deleted inserted replaced
62:7087484574b0 63:3cc4a8603489
85 <!-- PAGE --> 85 <!-- PAGE -->
86 <div class="slide"> 86 <div class="slide">
87 <h1>目的と背景(1)</h1> 87 <h1>目的と背景(1)</h1>
88 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li> 88 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li>
89 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li> 89 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
90 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考える。</li> 90 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
91 </div> 91 </div>
92 <!-- PAGE --> 92 <!-- PAGE -->
93 <div class="slide"> 93 <div class="slide">
94 <h1>目的と背景(2)</h1> 94 <h1>目的と背景(2)</h1>
95 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.4 をベースとしたコンパイラが開発された。</li> 95 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。</li>
96 <li>GCC をベースとした CbC コンパイラは、修正・追加された最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li> 96 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
97 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li> 97 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
98 </div> 98 </div>
99 <!-- PAGE --> 99 <!-- PAGE -->
100 <div class="slide"> 100 <div class="slide">
101 <h1>発表内容</h1> 101 <h1>発表内容</h1>
119 </div> 119 </div>
120 <!-- PAGE --> 120 <!-- PAGE -->
121 <div class="slide"> 121 <div class="slide">
122 <h1>Continuation based C </h1> 122 <h1>Continuation based C </h1>
123 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2> 123 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
124 <ul>
124 <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li> 125 <li>プログラムの記述は C の構文と同じだが、ループ制御や関数コールが取り除かれる。</li>
125 <li>コードセグメント</li> 126 </ul>
127 <br>
128 <h2>コードセグメント</h2>
126 <ul> 129 <ul>
127 <li>C の関数よりも細かい単位。</li> 130 <li>C の関数よりも細かい単位。</li>
128 <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li> 131 <li>コードセグメントの処理は最後に別のコードセグメントへ継続(goto)することで続いていく。</li>
129 </ul> 132 </ul>
130 </div> 133 </div>
228 <li>__code 用idとkeywordを作成。</li> 231 <li>__code 用idとkeywordを作成。</li>
229 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li> 232 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
230 </ul> 233 </ul>
231 <li>goto によるコードセグメントへの継続</li> 234 <li>goto によるコードセグメントへの継続</li>
232 <ul> 235 <ul>
233 <li>通常の goto に加え、コードセグメントを呼び出す処理を追加。</li> 236 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
234 <li>コードセグメントへのgoto後は、 return の処理を自動で追加。</li> 237 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
235 </ul> 238 </ul>
236 </ul> 239 </ul>
237 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li> 240 <li class="incremental">追加したgotoシンタックスの実際のソースは次のようになる。</li>
238 </div> 241 </div>
239 <!-- PAGE --> 242 <!-- PAGE -->
245 expr = c_parser_expr_no_commas (parser, NULL); 248 expr = c_parser_expr_no_commas (parser, NULL);
246 if (TREE_CODE(expr.value) == CALL_EXPR ) 249 if (TREE_CODE(expr.value) == CALL_EXPR )
247 { 250 {
248 location_t loc = c_parser_peek_token (parser)->location; 251 location_t loc = c_parser_peek_token (parser)->location;
249 cbc_replace_arguments (loc, expr.value); 252 cbc_replace_arguments (loc, expr.value);
250
251 TREE_TYPE(expr.value) = void_type_node; 253 TREE_TYPE(expr.value) = void_type_node;
252 /*tree env = NULL_TREE;**/
253 CbC_IS_CbC_GOTO (expr.value) = 1; 254 CbC_IS_CbC_GOTO (expr.value) = 1;
254 CALL_EXPR_TAILCALL (expr.value) = 1; 255 CALL_EXPR_TAILCALL (expr.value) = 1;
255 add_stmt(expr.value); 256 add_stmt(expr.value);
256 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE); /* stmt = c_finish_return (0); */ 257 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
257 } 258 }
258 </pre> 259 </pre>
259 </small> 260 </small>
260 <li>CALL_EXPR_TAILCALLマクロにより tail call フラグを立てている。</li> 261 <small>
261 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へと代入させる関数</li> 262 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立て。</li>
263 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
262 <li>最後にc_finish_return関数によりreturn文を生成している。</li> 264 <li>最後にc_finish_return関数によりreturn文を生成している。</li>
265 </small>
263 </div> 266 </div>
264 <!-- PAGE --> 267 <!-- PAGE -->
265 <div class="slide"> 268 <div class="slide">
266 <h1>CbCの実装:シンタックスの追加</h1> 269 <h1>CbCの実装:シンタックスの追加</h1>
267 <h2>gotoシンタックスの追加</h2> 270 <h2>gotoシンタックスの追加</h2>
268 <li>最後にリターン文を生成することにより、次へと制御を映させず。また末尾最適化がかかるようになる。</li> 271 <li>最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。</li>
269 <table border=1 width=100%> 272 <table border=1 width=100%>
270 <tr class="center"> 273 <tr class="center">
271 <small> 274 <small>
272 <td>実際のコード </td> 275 <td>実際のコード </td>
273 <td>GCC 内で処理されるコード</td> 276 <td>GCC 内で処理されるコード</td>
290 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li> 293 <li>末尾最適化(末尾除去)については後ほど詳しく説明する。</li>
291 </div> 294 </div>
292 <!-- PAGE --> 295 <!-- PAGE -->
293 <div class="slide"> 296 <div class="slide">
294 <h1>CbCの実装:引数渡し</h1> 297 <h1>CbCの実装:引数渡し</h1>
295 <li>当初、GCCを使ってコンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li> 298 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
296 <ul> 299 <ul>
297 <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていたため。</li> 300 <li>Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
298 </ul> 301 </ul>
299 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに</li> 302 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
300 </div> 303 </div>
301 <!-- PAGE --> 304 <!-- PAGE -->
302 <div class="slide"> 305 <div class="slide">
303 <h1>CbCの実装:引数渡し(fastcall)</h1> 306 <h1>CbCの実装:引数渡し(fastcall)</h1>
304 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li> 307 <h2>fastcall</h2>
305 <li>__code で宣言された関数は自動でfastcall属性が付与される。</li> 308 <ul>
309 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
310 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
311 </ul>
312 <li>__code で宣言された関数は自動でfastcall属性が付与されるように。</li>
306 <small> 313 <small>
307 <pre> 314 <pre>
308 if(!TARGET_64BIT) { 315 if(!TARGET_64BIT) {
309 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 316 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
310 declspecs_add_attrs(specs, attrs); 317 declspecs_add_attrs(specs, attrs);
313 </small> 320 </small>
314 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p> 321 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
315 </div> 322 </div>
316 <!-- PAGE --> 323 <!-- PAGE -->
317 <div class="slide"> 324 <div class="slide">
325 <h1>CbCの実装:引数渡し</h1>
326 <table width=100% border=1 class="center">
327 <caption>引数渡しに使われるレジスタの数(gcc)</caption>
328 <tr>
329 <td>arch</td>
330 <td>int(整数型)</td>
331 <td>float(浮動小数点型)</td>
332 <td>double(浮動小数点型)</td>
333 </tr>
334 <tr>
335 <td>i386</td>
336 <td>2</td>
337 <td>0<br>(stackを使用)</td>
338 <td>0<br>(stackを使用)</td>
339 </tr>
340 <tr>
341 <td>x86_64</td>
342 <td>6</td>
343 <td>8</td>
344 <td>8</td>
345 </tr>
346 </table>
347 </div>
348 <!-- PAGE -->
349 <div class="slide">
318 <h1>CbCの実装:TCE</h1> 350 <h1>CbCの実装:TCE</h1>
319 <h2>Tail Call Elimination(TCE):末尾除去</h2> 351 <h2>Tail Call Elimination(TCE):末尾除去</h2>
320 <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li> 352 <li>関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。</li>
321 <img src="./pix/continuation.png" style="height: 7em;"> 353 <img src="./pix/continuation.png" style="height: 7em;">
322 <li>CbCにおけるコードセグメントへの継続はこのTCEにより実装されている。</li> 354 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
323 </div> 355 </div>
324 <!-- PAGE --> 356 <!-- PAGE -->
325 <div class="slide"> 357 <div class="slide">
326 <h1>CbCの実装:TCE</h1> 358 <h1>CbCの実装:TCE</h1>
327 <li></li> 359 <li>TCEにより関数へjmp命令で処理を移すことを利用。</li>
328 </div> 360 <li>TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。</li>
329 <!-- PAGE --> 361 <br>
330 <div class="slide"> 362 <h2>具体的な実装内容</h2>
331 <h1>環境付き継続</h1> 363 <ul>
364 <li class="incremental">try_tail_call(変数名)フラグを立てる。</li>
365 <li class="incremental">try_tail_callフラグを落とさせない。</li>
366 </ul>
367 <li class="incremental">TCEにかかるにはtry_tail_callフラグ次第</li>
368 </div>
369 <!-- PAGE -->
370 <div class="slide">
371 <h1>CbCの実装:TCE</h1>
372 <li>try_tail_callフラグはexpand_call関数で落とされる。</li>
373 <ul>
374 <li>expand_call関数</li>
375 <ul>
376 <li>Treeで表された関数からRTLを生成する関数</li>
377 </ul>
378 </ul>
379 <li>次の条件を満たしていないとtry_tail_callフラグを落とす。</li>
380 <ul>
381 <li>caller側とcallee側の戻値の型の一致している。</li>
382 <li>関数呼び出しがリターン直前に行われている。</li>
383 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
384 <li>引数の並びのコピーに上書きがない。</li>
385 </ul>
386 </div>
387 <!-- PAGE -->
388 <div class="slide">
389 <h1>CbCの実装:TCE</h1>
390 <li>フラグを落とされない為にコードセグメントは次の条件で作成する。</li>
391 <ul>
392 <li>void型で統一。</li>
393 <li>gotoの直後にreturnを置く。</li>
394 <li>スタックサイズは固定。</li>
395 <li>引数は一旦、一時変数にコピーする。</li>
396 </ul>
397 <li class="incremental">これでコードセグメントへの処理はjmp命令で移ることになる。</li>
398 </div>
399 <!-- PAGE -->
400 <div class="slide">
401 <h1>CbCの実装:環境付き継続</h1>
332 <li>CbCにおけるCとの互換性を保つための機能。</li> 402 <li>CbCにおけるCとの互換性を保つための機能。</li>
333 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li> 403 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
334 <li></li> 404 <li></li>
335 </div> 405 </div>
336 <!-- PAGE --> 406 <!-- PAGE -->