Mercurial > hg > Papers > 2010 > kent-master

comparison probation-slide/final-slide.html @ 13:12cb508ee15d after-organizing

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add slides for probation.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 14:48:06 +0900
parents
children
comparison
equal deleted inserted replaced
12:0f9a0ecc6afb 13:12cb508ee15d
1 <?xml version="1.0" encoding="utf-8"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja">
5 <head>
6 <title>Continuation based C</title>
7 <meta name="copyright" content="Copyright &#169; 2009 KSL: Yogi KENT" />
8 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9 <meta name="font-size-adjustment" content="1" />
10 <link rel="stylesheet" href="slidy.css"
11 type="text/css" media="screen, projection, print" />
12 <link rel="stylesheet" href="final-slide.css"
13 type="text/css" media="screen" />
14 <!--link rel="stylesheet" href="../Slidy/w3c-blue2.css"
15 type="text/css" media="screen, projection, print" /-->
16 <style type="text/css">
17 .right {
18 float: right;
19 width: 40%;
20 }
21 .left {
22 float: left;
23 width: 40%;
24 }
25 div.slide {
26 vertical-align: middle;
27 }
28 div.top h1 {
29 width: 70%;
30 padding: 0 1em 0;
31 text-align: center;
32 }
33 #frame {
34 position: fixed;
35 left: -1px;
36 top: -1px;
37 width: 800px;
38 height: 600px;
39 border: solid 1px red;
40 visibility: visible;
41 }
42 .speak {
43
44 visibility: hidden;
45
46 font-size: 80%;
47 line-height: 1.0;
48 position: fixed;
49 right: 0.5em;
50 bottom: 1.5em;
51 max-width: 60%;
52 background-color: green;
53 opacity: 0.90;
54 color: black;
55 -moz-border-radius: 8px;
56 -webkit-border-radius: 8px;
57 }
58 ul.narrow li {
59 margin-right: 0;
60 }
61 table {
62 border-collapse: collapse;
63 border: solid 1px black;
64 }
65 table td {
66 border: solid 1px black;
67 }
68 table th {
69 text-align: center;
70 border: solid 1px black;
71 }
72 </style>
73 <script src="slidy.js"
74 charset="utf-8" type="text/javascript">
75 </script>
76 <script type="text/javascript">
77 sizes = new Array("14pt", "15pt", "16pt", "17pt", "18pt", "19pt", "20pt", "21pt", "22pt","23pt", "24pt", "26pt", "28pt", "30pt", "32pt");
78 sizeIndex = 1;
79 mouseClickEnabled = false;
80 </script>
81 </head>
82 <body>
83 <!-- this defines the slide background -->
84 <div id="frame"></div>
85
86 <div class="background">
87 <div class="header">
88 <!-- sized and colored via CSS -->
89 </div>
90
91 <!--img id="head-icon" alt="graphic with four colored squares"
92 src="../Slidy/icon-blue.png" /-->
93
94 <div class="footer">
95 <object id="w3c-logo" data="kent-logo2.svg" type="image/svg+xml" title="KENT logo">
96 <a href="http://www.w3.org/">
97 <img alt="W3C logo" id="w3c-logo-fallback" src="kent-logo2.png" />
98 </a>
99 </object>
100
101 <!-- modify the following text as appropriate -->
102 組み込み向け言語CbCのGCC上の実装 <span style="font-size:70%;">http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html</span><br />
103 <!--Event, Location, Month Year-->
104 </div>
105 </div>
106
107 <div class="slide top">
108 <h1>組み込み向け言語Continuation based CのGCC上の実装</h1>
109 <p>
110 与儀健人 (並列信頼研究室)
111 &lt;<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>&gt;
112 </p>
113 <!--img src="../Slidy/keys.jpg" class="cover"
114 alt="W3C as letters on 3 plastic buttons from a keyboard" /-->
115 <!--h2>ゼミ, 河野研, Sep, 2009</h2-->
116 </div>
117
118 <div class="slide">
119 <h1>研究の背景</h1>
120 <ul>
121 <li>ソフトウェアは今も大規模・複雑化が続いている</li>
122 <li>しかし、ソフトウェアのバグを発見するのは難しい</li>
123 <li style="marker:none;"/>
124 <li>組込みやReal-time処理の需要も増大してる</li>
125 <li>高速な応答が要求される組込み処理にはハードウェアに近い言語が適している</li>
126 </ul>
127 <p class="subtitle">なにが問題を複雑にしているのか？</p>
128 <ul>
129 <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
130 <li>現存する記述言語は状態遷移の記述に向いていない</li>
131 <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
132 </ul>
133 </div>
134
135 <div class="slide" style="font-size:95%">
136 <h1>研究目的</h1>
137 <p class="subtitle">
138 状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する
139 </p>
140 <ul>
141 <li>組込み、通信プロトコル、Real-time処理などの記述に向いている</li>
142 <li>状態遷移を直接記述するため、タブロー法での検証に有利</li>
143 <li>関数より細かく、ステートメントより大きい処理単位</li>
144 <li>細かい単位でソースコードレベルの最適化を可能にする</li>
145 </ul>
146 <p class="subtitle">条件</p>
147 <ul>
148 <li>既存のソフトウェアは膨大であり、無駄にはできない</li>
149 <li>互換性が必須条件</li>
150 <li>Cからの変換、Cへの変換ができる事が望ましい</li>
151 </ul>
152 </div>
153
154 <div class="slide">
155 <h1>Continuation based Cの提案</h1>
156 <p class="subtitle">継続を基本とする記述言語CbC</p>
157 <ul>
158 <li>環境を保持しない継続、<dfn>軽量継続</dfn>を導入</li>
159 <li>軽量継続で<em class="weak">状態遷移が明確</em>になる</li>
160 <li>関数の代わりとなる処理単位<dfn>コードセグメント</dfn></li>
161 <li>関数 &gt; コードセグメント &gt; ステートメント</li>
162 <li>for, whileなどのループも軽量継続で実現できる</li>
163 <li>Cとの相互利用のための構文<dfn>環境付き継続</dfn>
164 <ul>
165 <li>このCとの相互利用可能なCbCは<em>C with Continuation</em>と呼ばれる</li>
166 </ul>
167 </li>
168 </ul>
169 <p class="subtitle"></p>
170 </div>
171
172 <div class="slide">
173 <h1>継続とはなんなのか？</h1>
174 <p class="subtitle">継続</p>
175 <ul>
176 <li>現在の処理を続行するための情報
177 <ul>
178 <li>Cならば続く命令のアドレスや</li>
179 <li>命令に必要な値、</li>
180 <li>スタックなど、その環境全てを含む</li>
181 </ul>
182 </li>
183 </ul>
184 <p class="subtitle">CbCでの軽量継続</p>
185 <ul>
186 <li>継続からスタックに関する情報を落とす</li>
187 <li>続く命令とデータのみのシンプルな継続</li>
188 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
189 </ul>
190 </div>
191
192 <div class="slide" style="font-size:95%;">
193 <h1>コードセグメントと軽量継続の記述</h1>
194 <pre style="float:right; width-max:45%">
195 <code>typedef code (*NEXT)(int);
196 int main(int argc, char **argv) {
197 int i;
198 i = atoi(argv[1]);
199 goto factor(i, print_fact);
200 }
201 <em>code factor(int x, NEXT next)</em> {
202 goto factor0(1, x, next);
203 }
204 code factor0(int prod,int x,NEXT next) {
205 if (x &gt;= 1) {
206 goto factor0(prod*x, x-1, next);
207 } else {
208 <em>goto (*next)(prod);</em>
209 }
210 }
211 code print_fact(int value) {
212 printf("factorial = %d\n", value);
213 exit(0);
214 } </code></pre>
215 <p class="subtitle">実際のプログラム記述は？</p>
216 <ul>
217 <li>コードセグメント定義
218 <ul>
219 <li><code>codeキーワードで宣言</code></li>
220 <li>書式は関数と同じ</li>
221 </ul>
222 </li>
223 <li>軽量継続制御
224 <ul>
225 <li><code>goto</code>キーワードと引数</li>
226 <li>コードセグメントの最初に飛ぶ</li>
227 <li>コードセグメントポインタによる間接継続も可能</li>
228 </ul>
229 </li>
230 </ul>
231 </div>
232
233 <div class="slide">
234 <h1>これまでのCbC</h1>
235 <p class="subtitle"></p>
236 <dl>
237 <dt>2000</dt>
238 <dd>micro-cをベースとしたコンパイラの完成<br/>
239 x86, PowerPC, ARM, MIPS.
240 </dd>
241 <dt>2002</dt>
242 <dd>CbCを用いた分散計算</dd>
243 <dt>2005</dt>
244 <dd>CbCを用いたプログラム分割手法</dd>
245 <dt>2006</dt>
246 <dd>CbCによるSPUマシンのシミュレータ</dd>
247 <dt>2007</dt>
248 <dd>時相論理をベースとしたCbCプログラムの検証</dd>
249 <dt>2008</dt>
250 <dd>GCCをベースとしたコンパイラが開発される</dd>
251 <dt>2010</dt>
252 <dd>GCCベースコンパイラを実用レベルに拡張</dd>
253 </dl>
254 </div>
255
256 <div class="slide">
257 <h1>本研究での取り組み</h1>
258 <p class="subtitle">取り組み</p>
259 <dl>
260 <dt>First</dt>
261 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
262 <ul>
263 <li>軽量継続の実装、これまでの制限の除去</li>
264 <li>x86アーキテクチャにて高速化を行った</li>
265 </ul>
266 </dd>
267 <dt>Second</dt>
268 <dd>C言語との相互利用を可能にした</dd>
269 <dt>Third</dt>
270 <dd>ソースコードメンテナンス性の向上</dd>
271 </dl>
272 </div>
273
274
275
276 <div class="slide">
277 <h1>GNU コンパイラコレクション (GCC)</h1>
278 <div style="width:50%;float:right;">
279 <p class="subtitle">GCCでのコンパイルの流れ</p>
280 <ul style="padding-left:3em">
281 <li>フロントエンド</li>
282 <li>ミドルエンド</li>
283 <li>バックエンド</li>
284 </ul>
285 </div>
286 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
287 </div>
288
289 <div class="slide">
290 <h1>GNU コンパイラコレクション (GCC)</h1>
291 <div style="width:50%;float:right;">
292 <p class="subtitle">GCCでのコンパイルの流れ</p>
293 <ul style="padding-left:3em">
294 <li>フロントエンド</li>
295 <li>ミドルエンド</li>
296 <li>バックエンド</li>
297 </ul>
298 </div>
299 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
300 </div>
301
302
303 <div class="slide">
304 <h1>GCC フロントエンド</h1>
305 <p class="subtitle">GCCにおける構文解析部</p>
306 <ul class="outline">
307 <li>C,Java,Adaなど、言語毎に違う</li>
308 <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li>
309 <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li>
310 <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li>
311 <li>GIMPLEの内部表現例
312 <pre><code>
313 &lt;call_expr 0xb7bc7850
314 type &lt;void_type 0xb7cc9270 void VOID
315 align 8 symtab 0 alias set -1 canonical type 0xb7cc9270
316 pointer_to_this &lt;pointer_type 0xb7cc92d8&gt;&gt;
317 side-effects addressable tree_5
318 fn &lt;var_decl 0xb7d65370 D.2156
319 type &lt;pointer_type 0xb7da74e0 type &lt;function_type 0xb7da7478&gt;
320 unsigned SI
321 size &lt;integer_cst 0xb7cb36ac constant 32&gt;
322 unit size &lt;integer_cst 0xb7cb3498 constant 4&gt;
323 align 32 symtab 0 alias set -1 structural equality&gt;
324 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
325 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
326 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
327 (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32])
328 chain &lt;var_decl 0xb7d653c8 D.2157 type &lt;pointer_type 0xb7cc92d8&gt;
329 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
330 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
331 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
332 (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain &lt;var_decl 0xb7d65420 D.2158&gt;&gt;&gt; arg 0 &lt;var_decl 0xb7d653c8 D.2157&gt;
333 arg 1 &lt;var_decl 0xb7d65420 D.2158
334 type &lt;pointer_type 0xb7da7270 stack type &lt;void_type 0xb7cc9270 void&gt;
335 sizes-gimplified unsigned SI size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
336 align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8
337 pointer_to_this &lt;pointer_type 0xb7bb7000&gt;&gt;
338 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
339 align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
340 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
341 (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])&gt;
342 quicksort/quicksort_cbc.cbc:29:7&gt;
343 </code></pre>
344 <p class="subtitle">全ての構文はこのGIMPLEで表される</p>
345 </li>
346 </ul>
347 <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p>
348 </div>
349
350 <div class="slide" style="font-size:95%">
351 <h1>GCC ミドルエンド</h1>
352 <p class="subtitle">GIMPLEからRTLへの変換と最適化</p>
353 <ul class="outline">
354 <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li>
355 <li>登録されたpassを一つ一つ実行する</li>
356 <li>最初にGIMPLEの最適化がたくさんある</li>
357 <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li>
358 <li>最後にRTLの最適化がまた大量にある
359 <pre style="font-size:80%"><code>
360 p = &amp;all_lowering_passes;
361 NEXT_PASS (pass_remove_useless_stmts);
362 NEXT_PASS (pass_mudflap_1);
363 NEXT_PASS (pass_lower_omp);
364 NEXT_PASS (pass_lower_cf);
365 NEXT_PASS (pass_refactor_eh);
366 NEXT_PASS (pass_lower_eh);
367 NEXT_PASS (pass_build_cfg);
368 NEXT_PASS (pass_lower_complex_O0);
369 NEXT_PASS (pass_lower_vector);
370 #ifndef noCbC
371 //NEXT_PASS (pass_warn_function_return);
372 #else
373 NEXT_PASS (pass_warn_function_return);
374 #endif
375 NEXT_PASS (pass_build_cgraph_edges);
376 NEXT_PASS (pass_inline_parameters);
377 *p = NULL;
378
379 /* Interprocedural optimization passes. */
380 p = &amp;all_ipa_passes;
381 NEXT_PASS (pass_ipa_function_and_variable_visibility);
382 NEXT_PASS (pass_ipa_early_inline);
383 {
384 struct opt_pass **p = &amp;pass_ipa_early_inline.pass.sub;
385 NEXT_PASS (pass_early_inline);
386 NEXT_PASS (pass_inline_parameters);
387 NEXT_PASS (pass_rebuild_cgraph_edges);
388 }
389 NEXT_PASS (pass_early_local_passes);
390 {
391 struct opt_pass **p = &amp;pass_early_local_passes.pass.sub;
392 NEXT_PASS (pass_tree_profile);
393 NEXT_PASS (pass_cleanup_cfg);
394 NEXT_PASS (pass_init_datastructures);
395 NEXT_PASS (pass_expand_omp);
396
397 NEXT_PASS (pass_referenced_vars);
398 NEXT_PASS (pass_reset_cc_flags);
399 NEXT_PASS (pass_build_ssa);
400 NEXT_PASS (pass_early_warn_uninitialized);
401 NEXT_PASS (pass_all_early_optimizations);
402 {
403 struct opt_pass **p = &amp;pass_all_early_optimizations.pass.sub;
404 NEXT_PASS (pass_rebuild_cgraph_edges);
405 NEXT_PASS (pass_early_inline);
406 NEXT_PASS (pass_rename_ssa_copies);
407 NEXT_PASS (pass_ccp);
408 NEXT_PASS (pass_forwprop);
409 NEXT_PASS (pass_update_address_taken);
410 NEXT_PASS (pass_sra_early);
411 NEXT_PASS (pass_copy_prop);
412 NEXT_PASS (pass_merge_phi);
413 NEXT_PASS (pass_cd_dce);
414 NEXT_PASS (pass_simple_dse);
415 NEXT_PASS (pass_tail_recursion);
416 NEXT_PASS (pass_convert_switch);
417 NEXT_PASS (pass_profile);
418 }
419 NEXT_PASS (pass_release_ssa_names);
420 NEXT_PASS (pass_rebuild_cgraph_edges);
421 NEXT_PASS (pass_inline_parameters);
422 }
423 NEXT_PASS (pass_ipa_increase_alignment);
424 NEXT_PASS (pass_ipa_matrix_reorg);
425 NEXT_PASS (pass_ipa_cp);
426 NEXT_PASS (pass_ipa_inline);
427 NEXT_PASS (pass_ipa_reference);
428 NEXT_PASS (pass_ipa_pure_const);
429 NEXT_PASS (pass_ipa_type_escape);
430 NEXT_PASS (pass_ipa_pta);
431 NEXT_PASS (pass_ipa_struct_reorg);
432 *p = NULL;
433
434 /* These passes are run after IPA passes on every function that is being
435 output to the assembler file. */
436 p = &amp;all_passes;
437 NEXT_PASS (pass_all_optimizations);
438 {
439 struct opt_pass **p = &amp;pass_all_optimizations.pass.sub;
440 /* Initial scalar cleanups before alias computation.
441 They ensure memory accesses are not indirect wherever possible. */
442 NEXT_PASS (pass_strip_predict_hints);
443 NEXT_PASS (pass_update_address_taken);
444 NEXT_PASS (pass_rename_ssa_copies);
445 NEXT_PASS (pass_complete_unrolli);
446 NEXT_PASS (pass_ccp);
447 NEXT_PASS (pass_forwprop);
448 /* Ideally the function call conditional
449 dead code elimination phase can be delayed
450 till later where potentially more opportunities
451 can be found. Due to lack of good ways to
452 update VDEFs associated with the shrink-wrapped
453 calls, it is better to do the transformation
454 here where memory SSA is not built yet. */
455 NEXT_PASS (pass_call_cdce);
456 /* pass_build_alias is a dummy pass that ensures that we
457 execute TODO_rebuild_alias at this point. Re-building
458 alias information also rewrites no longer addressed
459 locals into SSA form if possible. */
460 NEXT_PASS (pass_build_alias);
461 NEXT_PASS (pass_return_slot);
462 NEXT_PASS (pass_phiprop);
463 NEXT_PASS (pass_fre);
464 NEXT_PASS (pass_copy_prop);
465 NEXT_PASS (pass_merge_phi);
466 NEXT_PASS (pass_vrp);
467 NEXT_PASS (pass_dce);
468 NEXT_PASS (pass_cselim);
469 NEXT_PASS (pass_tree_ifcombine);
470 NEXT_PASS (pass_phiopt);
471 NEXT_PASS (pass_tail_recursion);
472 NEXT_PASS (pass_ch);
473 NEXT_PASS (pass_stdarg);
474 NEXT_PASS (pass_lower_complex);
475 NEXT_PASS (pass_sra);
476 NEXT_PASS (pass_rename_ssa_copies);
477 NEXT_PASS (pass_dominator);
478 /* The only const/copy propagation opportunities left after
479 DOM should be due to degenerate PHI nodes. So rather than
480 run the full propagators, run a specialized pass which
481 only examines PHIs to discover const/copy propagation
482 opportunities. */
483 NEXT_PASS (pass_phi_only_cprop);
484 NEXT_PASS (pass_dse);
485 NEXT_PASS (pass_reassoc);
486 NEXT_PASS (pass_dce);
487 NEXT_PASS (pass_forwprop);
488 NEXT_PASS (pass_phiopt);
489 NEXT_PASS (pass_object_sizes);
490 NEXT_PASS (pass_ccp);
491 NEXT_PASS (pass_copy_prop);
492 NEXT_PASS (pass_fold_builtins);
493 NEXT_PASS (pass_cse_sincos);
494 NEXT_PASS (pass_split_crit_edges);
495 NEXT_PASS (pass_pre);
496 NEXT_PASS (pass_sink_code);
497 NEXT_PASS (pass_tree_loop);
498 {
499 struct opt_pass **p = &amp;pass_tree_loop.pass.sub;
500 NEXT_PASS (pass_tree_loop_init);
501 NEXT_PASS (pass_copy_prop);
502 NEXT_PASS (pass_dce_loop);
503 NEXT_PASS (pass_lim);
504 NEXT_PASS (pass_predcom);
505 NEXT_PASS (pass_tree_unswitch);
506 NEXT_PASS (pass_scev_cprop);
507 NEXT_PASS (pass_empty_loop);
508 NEXT_PASS (pass_record_bounds);
509 NEXT_PASS (pass_check_data_deps);
510 NEXT_PASS (pass_loop_distribution);
511 NEXT_PASS (pass_linear_transform);
512 NEXT_PASS (pass_graphite_transforms);
513 NEXT_PASS (pass_iv_canon);
514 NEXT_PASS (pass_if_conversion);
515 NEXT_PASS (pass_vectorize);
516 {
517 struct opt_pass **p = &amp;pass_vectorize.pass.sub;
518 NEXT_PASS (pass_lower_vector_ssa);
519 NEXT_PASS (pass_dce_loop);
520 }
521 NEXT_PASS (pass_complete_unroll);
522 NEXT_PASS (pass_parallelize_loops);
523 NEXT_PASS (pass_loop_prefetch);
524 NEXT_PASS (pass_iv_optimize);
525 NEXT_PASS (pass_tree_loop_done);
526 }
527 NEXT_PASS (pass_cse_reciprocals);
528 NEXT_PASS (pass_convert_to_rsqrt);
529 NEXT_PASS (pass_reassoc);
530 NEXT_PASS (pass_vrp);
531 NEXT_PASS (pass_dominator);
532 /* The only const/copy propagation opportunities left after
533 DOM should be due to degenerate PHI nodes. So rather than
534 run the full propagators, run a specialized pass which
535 only examines PHIs to discover const/copy propagation
536 opportunities. */
537 NEXT_PASS (pass_phi_only_cprop);
538 NEXT_PASS (pass_cd_dce);
539 NEXT_PASS (pass_tracer);
540
541 /* FIXME: If DCE is not run before checking for uninitialized uses,
542 we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
543 However, this also causes us to misdiagnose cases that should be
544 real warnings (e.g., testsuite/gcc.dg/pr18501.c).
545
546 To fix the false positives in uninit-5.c, we would have to
547 account for the predicates protecting the set and the use of each
548 variable. Using a representation like Gated Single Assignment
549 may help. */
550 NEXT_PASS (pass_late_warn_uninitialized);
551 NEXT_PASS (pass_dse);
552 NEXT_PASS (pass_forwprop);
553 NEXT_PASS (pass_phiopt);
554 NEXT_PASS (pass_tail_calls);
555 NEXT_PASS (pass_rename_ssa_copies);
556 NEXT_PASS (pass_uncprop);
557 }
558 NEXT_PASS (pass_del_ssa);
559 NEXT_PASS (pass_nrv);
560 NEXT_PASS (pass_mark_used_blocks);
561 NEXT_PASS (pass_cleanup_cfg_post_optimizing);
562
563 NEXT_PASS (pass_warn_function_noreturn);
564 NEXT_PASS (pass_free_datastructures);
565 NEXT_PASS (pass_mudflap_2);
566
567 NEXT_PASS (pass_free_cfg_annotations);
568 <em>NEXT_PASS (pass_expand);</em>
569 NEXT_PASS (pass_rest_of_compilation);
570 {
571 struct opt_pass **p = &amp;pass_rest_of_compilation.pass.sub;
572 NEXT_PASS (pass_init_function);
573 NEXT_PASS (pass_jump);
574 NEXT_PASS (pass_rtl_eh);
575 NEXT_PASS (pass_initial_value_sets);
576 NEXT_PASS (pass_unshare_all_rtl);
577 NEXT_PASS (pass_instantiate_virtual_regs);
578 NEXT_PASS (pass_into_cfg_layout_mode);
579 NEXT_PASS (pass_jump2);
580 NEXT_PASS (pass_lower_subreg);
581 NEXT_PASS (pass_df_initialize_opt);
582 NEXT_PASS (pass_cse);
583 NEXT_PASS (pass_rtl_fwprop);
584 NEXT_PASS (pass_gcse);
585 NEXT_PASS (pass_rtl_ifcvt);
586 /* Perform loop optimizations. It might be better to do them a bit
587 sooner, but we want the profile feedback to work more
588 efficiently. */
589 NEXT_PASS (pass_loop2);
590 {
591 struct opt_pass **p = &amp;pass_loop2.pass.sub;
592 NEXT_PASS (pass_rtl_loop_init);
593 NEXT_PASS (pass_rtl_move_loop_invariants);
594 NEXT_PASS (pass_rtl_unswitch);
595 NEXT_PASS (pass_rtl_unroll_and_peel_loops);
596 NEXT_PASS (pass_rtl_doloop);
597 NEXT_PASS (pass_rtl_loop_done);
598 *p = NULL;
599 }
600 NEXT_PASS (pass_web);
601 NEXT_PASS (pass_jump_bypass);
602 NEXT_PASS (pass_cse2);
603 NEXT_PASS (pass_rtl_dse1);
604 NEXT_PASS (pass_rtl_fwprop_addr);
605 NEXT_PASS (pass_reginfo_init);
606 NEXT_PASS (pass_inc_dec);
607 NEXT_PASS (pass_initialize_regs);
608 NEXT_PASS (pass_outof_cfg_layout_mode);
609 NEXT_PASS (pass_ud_rtl_dce);
610 NEXT_PASS (pass_combine);
611 NEXT_PASS (pass_if_after_combine);
612 NEXT_PASS (pass_partition_blocks);
613 NEXT_PASS (pass_regmove);
614 NEXT_PASS (pass_split_all_insns);
615 NEXT_PASS (pass_lower_subreg2);
616 NEXT_PASS (pass_df_initialize_no_opt);
617 NEXT_PASS (pass_stack_ptr_mod);
618 NEXT_PASS (pass_mode_switching);
619 NEXT_PASS (pass_see);
620 NEXT_PASS (pass_match_asm_constraints);
621 NEXT_PASS (pass_sms);
622 NEXT_PASS (pass_sched);
623 NEXT_PASS (pass_subregs_of_mode_init);
624 NEXT_PASS (pass_ira);
625 NEXT_PASS (pass_subregs_of_mode_finish);
626 NEXT_PASS (pass_postreload);
627 {
628 struct opt_pass **p = &amp;pass_postreload.pass.sub;
629 NEXT_PASS (pass_postreload_cse);
630 NEXT_PASS (pass_gcse2);
631 NEXT_PASS (pass_split_after_reload);
632 NEXT_PASS (pass_branch_target_load_optimize1);
633 NEXT_PASS (pass_thread_prologue_and_epilogue);
634 NEXT_PASS (pass_rtl_dse2);
635 NEXT_PASS (pass_rtl_seqabstr);
636 NEXT_PASS (pass_stack_adjustments);
637 NEXT_PASS (pass_peephole2);
638 NEXT_PASS (pass_if_after_reload);
639 NEXT_PASS (pass_regrename);
640 NEXT_PASS (pass_cprop_hardreg);
641 NEXT_PASS (pass_fast_rtl_dce);
642 NEXT_PASS (pass_reorder_blocks);
643 NEXT_PASS (pass_branch_target_load_optimize2);
644 NEXT_PASS (pass_leaf_regs);
645 NEXT_PASS (pass_split_before_sched2);
646 NEXT_PASS (pass_sched2);
647 NEXT_PASS (pass_stack_regs);
648 {
649 struct opt_pass **p = &amp;pass_stack_regs.pass.sub;
650 NEXT_PASS (pass_split_before_regstack);
651 NEXT_PASS (pass_stack_regs_run);
652 }
653 NEXT_PASS (pass_compute_alignments);
654 NEXT_PASS (pass_duplicate_computed_gotos);
655 NEXT_PASS (pass_variable_tracking);
656 NEXT_PASS (pass_free_cfg);
657 NEXT_PASS (pass_machine_reorg);
658 NEXT_PASS (pass_cleanup_barriers);
659 NEXT_PASS (pass_delay_slots);
660 NEXT_PASS (pass_split_for_shorten_branches);
661 NEXT_PASS (pass_convert_to_eh_region_ranges);
662 NEXT_PASS (pass_shorten_branches);
663 NEXT_PASS (pass_set_nothrow_function_flags);
664 NEXT_PASS (pass_final);
665 }
666 NEXT_PASS (pass_df_finish);
667 }
668 NEXT_PASS (pass_clean_state);
669 *p = NULL;
670 </code></pre>
671 </li>
672 </ul>
673 <p class="subtitle">RTL</p>
674 <ul class="outline">
675 <li>一般的には中間コードとも呼ばれる</li>
676 <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li>
677 <li>RTLの例
678 <pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [
679 (set (reg/f:SI 7 sp)
680 (plus:SI (reg/f:SI 7 sp)
681 (const_int -1024 [0xfffffc00])))
682 (clobber (reg:CC 17 flags))
683 ]) -1 (nil))
684 </code></pre>
685 </li>
686 </ul>
687 </div>
688
689 <div class="slide">
690 <h1>バックエンド</h1>
691 <p class="subtitle">RTLからアセンブラに変換する処理</p>
692 <ul class="outline">
693 <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li>
694 <li>アーキテクチャ毎にこのmdが必要になる</li>
695 <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li>
696 <li>mdの例
697 <pre><code>
698 (define_insn "cmpdi_ccno_1_rex64"
699 [(set (reg FLAGS_REG)
700 (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr")
701 (match_operand:DI 1 "const0_operand" "")))]
702 "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCNOmode)"
703 "@
704 test{q}\t%0, %0
705 cmp{q}\t{%1, %0|%0, %1}"
706 [(set_attr "type" "test,icmp")
707 (set_attr "length_immediate" "0,1")
708 (set_attr "mode" "DI")])
709
710 (define_insn "*cmpdi_minus_1_rex64"
711 [(set (reg FLAGS_REG)
712 (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r")
713 (match_operand:DI 1 "x86_64_general_operand" "re,mr"))
714 (const_int 0)))]
715 "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCGOCmode)"
716 "cmp{q}\t{%1, %0|%0, %1}"
717 [(set_attr "type" "icmp")
718 (set_attr "mode" "DI")])
719 </code></pre></li>
720 </ul>
721 </div>
722
723 <div class="slide">
724 <h1>本研究での取り組み</h1>
725 <p class="subtitle">取り組み</p>
726 <dl>
727 <dt>First</dt>
728 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
729 <ul>
730 <li>軽量継続の実装、これまでの制限の除去</li>
731 <li>x86アーキテクチャにて高速化を行った</li>
732 </ul>
733 </dd>
734 <dt>Second</dt>
735 <dd>C言語との互換性の向上</dd>
736 <dt>Third</dt>
737 <dd>ソースコードメンテナンス性の向上</dd>
738 </dl>
739 </div>
740
741
742
743 <div class="slide">
744 <h1>First: 軽量継続の実装</h1>
745 <p class="subtitle">軽量継続を実装するには？</p>
746 <ul>
747 <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
748 <li>GCCでは<em class="weak">あくまで関数</em>がベース</li>
749 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
750 <li>関数コール(call命令)ではもちろんダメ</li>
751 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
752 <li>スタックを拡張するのもダメ</li>
753 </ul>
754 <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
755 </div>
756
757 <div class="slide">
758 <h1>First: 軽量継続の実装</h1>
759 <p class="subtitle">末尾呼出ってなに？</p>
760 <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
761 <ul>
762 <li>リターンの直前の関数呼び出しのこと</li>
763 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
764 <li>元の関数に戻らないため少し高速に</li>
765 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
766 </ul>
767 </div>
768
769 <div class="slide">
770 <h1>First: 軽量継続の実装</h1>
771 <p class="subtitle">末尾呼出ってなに？</p>
772 <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
773 <ul>
774 <li>リターンの直前の関数呼び出しのこと</li>
775 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
776 <li>元の関数に戻らないため少し高速に</li>
777 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
778 </ul>
779 <p class="subtitle incremental">軽量継続ではこの末尾呼出(TCE)を強制する！</p>
780 </div>
781
782 <div class="slide">
783 <h1>First: 軽量継続の実装</h1>
784 <p class="subtitle">末尾呼出による軽量継続の実装</p>
785 <ul>
786 <li>全ての軽量継続は末尾呼出と解釈する</li>
787 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
788 <li><code>goto cs(20, 30);</code></li>
789 <li><code>cs(20, 30); return;</code></li>
790 </ul>
791 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
792 <ol>
793 <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li>
794 <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li>
795 </ol>
796 </div>
797 <div class="slide">
798 <h1>First: 軽量継続の実装</h1>
799 <p class="subtitle">末尾呼出による軽量継続の実装</p>
800 <ul>
801 <li>全ての軽量継続は末尾呼出と解釈する</li>
802 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
803 <li><code>goto cs(20, 30);</code></li>
804 <li><code>cs(20, 30); return;</code></li>
805 </ul>
806 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
807 <ol>
808 <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
809 <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
810 </ol>
811 </div>
812
813
814 <div class="slide">
815 <h1>First: 軽量継続の実装</h1>
816 <p class="subtitle">引数順序の問題の解決</p>
817 <ul>
818 <li>問題となる例
819 <pre><code>code somesegment(int a, int b, int c) {
820 /∗ do something ∗/
821 goto nextsegment(b, c, a);
822 }
823 </code></pre>
824 </li>
825 <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
826 <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
827 <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
828 </ul>
829
830 </div>
831
832 <div class="slide">
833 <h1>First: 軽量継続の実装</h1>
834 <p class="subtitle">全ての引数を一時変数に退避</p>
835 <ul>
836 <li>次の様に構文木を変更する
837 <pre><code>code somesegment(int a, int b, int c) {
838 int a1, b1, c1;
839 /∗ do something ∗/
840 a1=a; b1=b; c1=c;
841 goto nextsegment(b1, c1, a1);
842 }
843 </code></pre>
844 </li>
845 <li>これにより、引数順序を考える必要はなくなる</li>
846 <li>代わりに、メモリアクセスが大量に発生</li>
847 <li>しかし、これはGCCの最適化で除去される</li>
848 </ul>
849
850 <p class="subtitle">これで軽量継続が実装された</p>
851 </div>
852
853
854 <div class="slide">
855 <h1>First: x86における高速化</h1>
856 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
857 <ul>
858 <li>特にx86アーキテクチャ</li>
859 <li><em class="weak">あくまで関数がベース</em>なので</li>
860 <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
861 <li>これをレジスタにすれば高速化が可能</li>
862 </ul>
863 <p class="subtitle">fastcallの導入</p>
864 <ul>
865 <li>GCCの独自拡張機能</li>
866 <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
867 </ul>
868 </div>
869
870 <div class="slide">
871 <h1>First: x86における高速化</h1>
872 <p class="subtitle">fastcallの強制</p>
873 <ul>
874 <li>通常は以下の様に定義される
875 <pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
876 </code></pre></li>
877 <li>しかしこれを毎回ユーザが書くのは変</li>
878 <li>やはりフロントエンドにて、強制するべき</li>
879 <li>型の構文木を生成した際にfastcall属性を付加</li>
880 </ul>
881 <p class="subtitle">実際の出力はどうなる？</p>
882 <div style="width:70%;margin:1em auto 0;">
883 <pre><code>__code current(int a, int b, int c) {
884 goto next(10, 20, 30);
885 }
886 </code></pre>
887 </div>
888 </div>
889
890 <div class="slide" style="font-size:95%;">
891 <h1>First: x86における高速化</h1>
892 <p class="subtitle">実際の出力アセンブラ</p>
893 <div style="width:50%;float:left;margin-left:auto;">
894 <p style="margin:0;text-align:center">fastcallにした場合</p>
895 <pre><code>current:
896 subl $12, %esp
897 movl $30, 16(%esp)
898 movl $20, %edx
899 movl $10, %ecx
900 addl $12, %esp
901 jmp next
902 </code></pre>
903 </div>
904 <div style="width:50%;float:right;margin-right:auto;">
905 <p style="margin:0;text-align:center">normalcallの場合</p>
906 <pre><code>current:
907 pushl %ebp
908 movl %esp, %ebp
909 movl $30, 16(%ebp)
910 movl $20, 12(%ebp)
911 movl $10, 8(%ebp)
912 leave
913 jmp next
914 </code></pre>
915 </div>
916 <br clear="all" />
917 <ul>
918 <li>命令数ではほとんど変化はない</li>
919 <li>引数2つがレジスタecxとedxに格納されるようになった</li>
920 <li>そのためメモリアクセスが減る</li>
921 <li>これで高速化されるはず</li>
922 </ul>
923 </div>
924
925
926 <div class="slide">
927 <h1>First: CbCコンパイラ実装の評価</h1>
928 <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
929 <ul>
930 <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
931 <li>コンパイラの出力した実行ファイルを比較</li>
932 <li>CbCでのquicksort例題を用意</li>
933 <li>実行速度、ファイルサイズ</li>
934 <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
935 </ul>
936 <p class="subtitle">実行環境</p>
937 <ul>
938 <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
939 <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
940 <li>OSはLinuxとOS Xを使用する</li>
941 </ul>
942 </div>
943
944 <div class="slide">
945 <h1>First: 性能評価（速度比較） vs.旧ver</h1>
946 <p class="subtitle">速度測定結果(単位:秒)</p>
947 <table>
948 <tr>
949 <th></th>
950 <th colspan="2">新CbCGCC</th>
951 <th colspan="2">旧CbCGCC</th>
952 </tr>
953 <tr>
954 <td></td>
955 <th>最適化無し</th>
956 <th>最適化有り</th>
957 <th>最適化無し</th>
958 <th>最適化有り</th>
959 </tr>
960 <tr>
961 <td>x86/OS X</td>
962 <td>5.907</td>
963 <td>2.434</td>
964 <td>4.668</td>
965 <td>3.048</td>
966 </tr>
967 <tr>
968 <td>x86/Linux</td>
969 <td>5.715</td>
970 <td>2.401</td>
971 <td>4.525</td>
972 <td>2.851</td>
973 </tr>
974 </table>
975 <p class="subtitle">評価</p>
976 <ul>
977 <li>最適化無の場合は遅くなった </li>
978 <li>一時変数への確保があるのでこれは予想通り</li>
979 <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
980 <li>fastcallの効果が十分に出ている</li>
981 </ul>
982 </div>
983
984
985 <div class="slide">
986 <h1>First: 性能評価（速度比較）</h1>
987 <p class="subtitle">速度測定結果(単位:秒)</p>
988 <table>
989 <tr>
990 <td></td>
991 <td>最適化なしのGCC</td>
992 <td>最適化付きのGCC</td>
993 <td>micro-c</td>
994 </tr>
995 <tr>
996 <td>x86/OS X</td>
997 <td>5.901</td>
998 <td>2.434</td>
999 <td>2.857</td>
1000 </tr>
1001 <tr>
1002 <td>x86/Linux</td>
1003 <td>5.732</td>
1004 <td>2.401</td>
1005 <td>2.254</td>
1006 </tr>
1007 <tr>
1008 <td>ppc/OS X</td>
1009 <td>14.875</td>
1010 <td>2.146</td>
1011 <td>4.811</td>
1012 </tr>
1013 <tr>
1014 <td>ppc/Linux</td>
1015 <td>19.793</td>
1016 <td>3.955</td>
1017 <td>6.454</td>
1018 </tr>
1019 <tr>
1020 <td>ppc/PS3</td>
1021 <td>39.176</td>
1022 <td>5.874</td>
1023 <td>11.121</td>
1024 </tr>
1025 </table>
1026 <p class="subtitle">結果(micro-cとの比較)</p>
1027 <ul>
1028 <li>x86では速度にあまり差が出なかった</li>
1029 <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
1030 <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
1031 </ul>
1032 </div>
1033
1034 <div class="slide">
1035 <h1>First: 性能評価（速度比較）</h1>
1036 <p class="subtitle">結果(micro-cとの比較)</p>
1037 <ul>
1038 <li>x86では速度にあまり差が出なかった</li>
1039 <li>PowerPCではCbCGCCが2倍ほど早い</li>
1040 </ul>
1041 <p class="subtitle">この違いはどこから？</p>
1042 <ul style="font-size:95%;">
1043 <li>実際にアセンブラを出力して比較、その結果</li>
1044 <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
1045 <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
1046 <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
1047 <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
1048 </ul>
1049 </div>
1050
1051 <div class="slide">
1052 <h1>First: 性能評価（サイズ比較）</h1>
1053 <p class="subtitle">ファイルサイズの比較</p>
1054 <ul>
1055 <li>組み込み系ではメモリ使用量が肝心</li>
1056 <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
1057 <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
1058 </ul>
1059 <p class="subtitle">結果</p>
1060 <table>
1061 <tr>
1062 <td></td>
1063 <th>CbCGCC<br/>速度最適化</th>
1064 <th>CbCGCC<br/>サイズ最適化</th>
1065 <th>micro-c</th>
1066 </tr>
1067 <tr>
1068 <td>x86/OS X</td>
1069 <td>9176</td>
1070 <td>9176</td>
1071 <td>9172</td>
1072 </tr>
1073 <tr>
1074 <td>x86/Linux</td>
1075 <td>5752</td>
1076 <td>5752</td>
1077 <td>5796</td>
1078 </tr>
1079 <tr>
1080 <td>ppc/OS X</td>
1081 <td>8576</td>
1082 <td>8576</td>
1083 <td>12664</td>
1084 </tr>
1085 <tr>
1086 <td>ppc/Linux</td>
1087 <td>10068</td>
1088 <td>10068</td>
1089 <td>9876</td>
1090 </tr>
1091 <tr>
1092 <td>ppc/PS3</td>
1093 <td>6960</td>
1094 <td>6728</td>
1095 <td>8636</td>
1096 </tr>
1097 </table>
1098 <p class="subtitle">結果考察</p>
1099 <ul>
1100 <li>x86ではファイルサイズの差がない</li>
1101 <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
1102 <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
1103 </ul>
1104 </div>
1105
1106
1107 <div class="slide">
1108 <h1>Second: Cとの相互利用</h1>
1109 <p class="subtitle">なぜそれが必要か</p>
1110 <ul>
1111 <li>C &lt;=&gt; CbC の変換が可能なので互換性はある</li>
1112 <li>しかし、ソースコード上での互換性もある事が望ましい</li>
1113 <li>CbCからCの関数を呼び出すのは問題ない</li>
1114 <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
1115 </ul>
1116 <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
1117 <ul>
1118 <li>軽量継続に、スタックの情報を加える</li>
1119 <li>つまり通常の「継続」と同じ</li>
1120 <li>関数からのみ使用可能</li>
1121 </ul>
1122 </div>
1123
1124 <div class="slide" style="font-size:95%;">
1125 <h1>Second: Cとの相互利用</h1>
1126 <pre style="float:right; width-max:45%">
1127 <code>typedef code (*NEXT)(int);
1128 int main(int argc, char **argv) {
1129 int i,a;
1130 i = atoi(argv[1]);
1131 <em>a = factor(i);</em>
1132 printf("%d! = %d\n", a);
1133 }
1134 int factor(int x) {
1135 NEXT ret = <em>__return</em>;
1136 goto factor0(1, x, ret);
1137 }
1138 code
1139 factor0(int prod,int x,NEXT next) {
1140 if (x &gt;= 1) {
1141 goto factor0(prod*x, x-1, next);
1142 } else {
1143 <em>goto (*next)(prod);</em>
1144 }
1145 }
1146 </code></pre>
1147 <p class="subtitle">環境付き継続の使用例</p>
1148 <ul>
1149 <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li>
1150 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
1151 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
1152 </ul>
1153 </div>
1154
1155 <div class="slide">
1156 <h1>Second: Cとの相互利用</h1>
1157 <p class="subtitle">どのように実装する？</p>
1158 <ol>
1159 <li>setjmp()/longjmp()を使って実装可能
1160 <ul>
1161 <li>Cの標準ライブラリの関数</li>
1162 <li>しかし余計な環境も保持するためオーバヘッドが大きい</li>
1163 <li>継続の際に渡す引数が一つ増えてしまう</li>
1164 </ul></li>
1165 <li>内部関数
1166 <ul>
1167 <li>GCCの独自拡張</li>
1168 <li>関数内に関数を定義可能</li>
1169 <li><em>内部関数から外の関数のラベルにgotoできる</em></li>
1170 </ul></li>
1171 </ol>
1172 <p class="subtitle">内部関数が使いやすい</p>
1173 </div>
1174
1175 <div class="slide" style="font-size:95%;">
1176 <h1>Second: Cとの相互利用</h1>
1177 <p class="subtitle">具体的には</p>
1178 <ul>
1179 <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
1180 <li>内部関数の中からは外の関数にgotoして脱出</li>
1181 </ul>
1182 <pre><code>int factor(int x) {
1183 int retval;
1184
1185 <em class="weak">code __return(int val) {
1186 retval = val;
1187 goto label;
1188 }
1189 if (0) {
1190 label:
1191 return retval;
1192 }</em>
1193
1194 NEXT ret = <em>__return</em>;
1195 goto factor0(1, x, ret);
1196 } </code></pre>
1197 </div>
1198
1199 <div class="slide" style="font-size:95%;">
1200 <h1>Second: Cとの相互利用・評価</h1>
1201 <p class="subtitle">この取り組みにより</p>
1202 <ul>
1203 <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li>
1204 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
1205 </ul>
1206 </div>
1207
1208 <div class="slide">
1209 <h1>Third: メンテナンス性の向上</h1>
1210 <p class="subtitle">GCCのアップデートリリースは早い</p>
1211 <ul>
1212 <li>リリースだけで年に5回のペース</li>
1213 <li>その度にバグの修正やコードの改善が入る</li>
1214 <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li>
1215 </ul>
1216 <p class="subtitle">このリリースに追従して差分をアップデートしたい</p>
1217 <ul>
1218 <li>GCC本家にマージしてもらうのが一番良いが難しい</li>
1219 <li></li>
1220 </ul>
1221 </div>
1222
1223 <div class="slide">
1224 <h1>Third: メンテナンス性の向上</h1>
1225 <img style="width:60%;float:right;" src="figures/gcc-repository.png" />
1226 <p class="subtitle">二つのリポジトリ管理</p>
1227 <ul>
1228 <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li>
1229 <li>CbCの修正が加えられたリポジトリ CbCGCC</li>
1230 <li>Mercurialによる分散リポジトリ管理</li>
1231 <li>CbCGCC は GCC_copyをクローン（ブランチ）して作成する</li>
1232 </ul>
1233 <p class="subtitle"></p>
1234 </div>
1235
1236
1237 <div class="slide">
1238 <h1>Third: メンテナンス性の向上</h1>
1239 <p class="subtitle">アップデート手順</p>
1240 <ul>
1241 <li>GCC-copyリポジトリにて
1242 <ol>
1243 <li>GCC-copyリポジトリのファイルをすべて消す</li>
1244 <li>GCCの最新バージョンをリポジトリ内に展開</li>
1245 <li>追加ファイル、削除ファイルを確認</li>
1246 <li>コミット、タグ付け</li>
1247 </ol> </li>
1248 <li>CbCGCCリポジトリにて
1249 <ol>
1250 <li>GCC-copyからpull.</li>
1251 <li>hg mergeでマージ実行</li>
1252 <li>衝突があればソースコードをを修正</li>
1253 <li>ビルドテスト</li>
1254 <li>コミット、タグ付け</li>
1255 </ol></li>
1256 </ul>
1257 </div>
1258
1259 <div class="slide">
1260 <h1>Third: メンテナンス性の向上・比較</h1>
1261 <p class="subtitle">これまでのアップデートは</p>
1262 <ul>
1263 <li>GCCの新旧の差分、CbCの差分</li>
1264 <li>複雑なdiffをとる必要がある</li>
1265 </ul>
1266 <p class="subtitle">新しい管理方法により</p>
1267 <ul>
1268 <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li>
1269 <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li>
1270 <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li>
1271 </ul>
1272 </div>
1273
1274 <div class="slide">
1275 <h1>まとめ</h1>
1276 <p class="subtitle">本研究での取り組み</p>
1277 <dl>
1278 <dt>First</dt>
1279 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
1280 <ul>
1281 <li>軽量継続における引数順序の制限を取り除いた</li>
1282 <li>PowerPCでの間接継続の制限を取り除いた</li>
1283 <li>x86アーキテクチャにて高速化を行った</li>
1284 </ul>
1285 </dd>
1286 <dt>Second</dt>
1287 <dd>Cとの相互利用性の向上</dd>
1288 <dt>Third</dt>
1289 <dd>ソースコードメンテナンス性の向上</dd>
1290 </dl>
1291 </div>
1292
1293 <div class="slide" style="font-size:95%;">
1294 <h1>まとめ</h1>
1295 <p class="subtitle">本研究での成果</p>
1296 <dl>
1297 <dt>成果1</dt>
1298 <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
1299 <dt>成果2</dt>
1300 <dd>CbCが多数のアーキテクチャに対応
1301 <ul>
1302 <li>20以上のアーキテクチャ</li>
1303 <li>特に64bitのx86, SPUがうれしい</li>
1304 </ul> </dd>
1305 <dt>成果3</dt>
1306 <dd>CbCの高速化
1307 <ul>
1308 <li>x86においてもmicro-cと互角の速度を達成</li>
1309 <li>PowerPCでは2倍の速度</li>
1310 </ul></dd>
1311 <dt>成果4</dt>
1312 <dd>メンテナンス性が向上</dd>
1313 </dl>
1314 </div>
1315
1316 <div class="slide">
1317 <h1>今後の課題</h1>
1318 <p class="subtitle"></p>
1319 <ul>
1320 <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li>
1321 <li>タブロー方を用いた検証</li>
1322 <li>TaskManagerのCbC実装</li>
1323 </ul>
1324 <p class="subtitle">CbC言語の今後</p>
1325 <ul>
1326 <li>オブジェクティブなCbCの設計</li>
1327 <li>データセグメントの導入</li>
1328 <li>スケジューラのためのリフレクション</li>
1329 </ul>
1330 </div>
1331
1332
1333 <div class="slide">
1334 <h1>おわり</h1>
1335 <p class="subtitle">ありがとうございました</p>
1336 </div>
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357 <div class="slide">
1358 <h1>Continuation based C</h1>
1359 <ul>
1360 <li>言語仕様</li>
1361 <li>return-callから軽量継続へ</li>
1362 <li>コードセグメント</li>
1363 <li>状態遷移に適した言語</li>
1364 <li>Cとの互換性</li>
1365 </ul>
1366 </div>
1367
1368
1369 <div class="slide">
1370 <h1></h1>
1371 <p class="subtitle"></p>
1372 <ul>
1373 <li></li>
1374 <li></li>
1375 </ul>
1376 </div>
1377 <div class="slide">
1378 <h1></h1>
1379 <p class="subtitle"></p>
1380 <ul>
1381 <li></li>
1382 <li></li>
1383 </ul>
1384 </div>
1385
1386 <div class="slide">
1387 <h1></h1>
1388 <p class="subtitle"></p>
1389 <ul>
1390 <li></li>
1391 <li></li>
1392 </ul>
1393 </div>
1394
1395
1396 <div class="slide">
1397 <h1>First: PowerPCでの間接継続</h1>
1398 <p class="subtitle"></p>
1399 <ul>
1400 <li></li>
1401 </ul>
1402 <p class="subtitle"></p>
1403 <div style="width:70%;margin:1em auto 0;">
1404 <pre><code>
1405 </code></pre>
1406 </div>
1407 </div>
1408
1409 <div class="slide">
1410 <h1>継続制御での並列代入</h1>
1411 <p class="subtitle" style="margin:0 1em 0.1em;">
1412 本当に最適化で余分なコードが消えるのか？
1413 </p>
1414 <div style="width:45%;float:left;margin-left:1em;">
1415 最適化しない場合
1416 <pre style="margin-top:0"><code> _test:
1417 stwu r1,-64(r1)
1418 mr r30,r1
1419 stw r3,88(r30)
1420 stw r4,92(r30)
1421 stw r5,96(r30)
1422 lwz r0,92(r30)
1423 stw r0,32(r30)
1424 lwz r0,96(r30)
1425 addic r0,r0,1
1426 stw r0,28(r30)
1427 lwz r0,88(r30)
1428 stw r0,24(r30)
1429 lwz r3,32(r30)
1430 lwz r4,28(r30)
1431 lwz r5,24(r30)
1432 addi r1,r30,64
1433 lwz r30,-8(r1)
1434 lwz r31,-4(r1)
1435 b L_next$stub
1436 </code></pre>
1437 </div>
1438 <div style="width:45%;float:right;margin-right:1em;">
1439 最適化した場合
1440 <pre><code>
1441 _test:
1442 mr r0,r3
1443 mr r3,r4
1444 mr r4,r5
1445 mr r5,r0
1446 b L_next$stub
1447 </code></pre>
1448 </div>
1449 <div style="width:50%;float:right">
1450 <ul>
1451 <li>r3:=a, r4:=b, r5:=c</li>
1452 <li>最適化しないとload, storeが満載</li>
1453 <li>最適化すると無駄なload, store命令が消えている</li>
1454 <li>実際はr0を使って4命令で入れ替えられる!</li>
1455 </ul>
1456 </div>
1457 </div>
1458
1459 <div class="slide">
1460 <h1>Cとの比較について</h1>
1461 <p class="subtitle">quicksort例題をCと比較すると</p>
1462 <ul>
1463 <li>現在のところ、遅くなる</li>
1464 <li>問題はquicksortという例題では必ずスタックが必要だということ</li>
1465 <li>例題ではスタックを自前の構造体で用意している</li>
1466 <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li>
1467 <li>状態遷移ベースの例題を作りたい</li>
1468 </ul>
1469 </div>
1470
1471
1472 <div class="slide">
1473 <h1>TODO</h1>
1474 <p class="subtitle"></p>
1475 <ul>
1476 <li>並列代入</li>
1477 <li>PowerPC間接継続</li>
1478 <li>評価結果・表</li>
1479 <li>バックエンド</li>
1480 <li></li>
1481 </ul>
1482 </div>
1483
1484
1485 </body>
1486 </html>
1487