13
|
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 © 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 <<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>>
|
|
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>関数 > コードセグメント > ステートメント</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 >= 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 <call_expr 0xb7bc7850
|
|
314 type <void_type 0xb7cc9270 void VOID
|
|
315 align 8 symtab 0 alias set -1 canonical type 0xb7cc9270
|
|
316 pointer_to_this <pointer_type 0xb7cc92d8>>
|
|
317 side-effects addressable tree_5
|
|
318 fn <var_decl 0xb7d65370 D.2156
|
|
319 type <pointer_type 0xb7da74e0 type <function_type 0xb7da7478>
|
|
320 unsigned SI
|
|
321 size <integer_cst 0xb7cb36ac constant 32>
|
|
322 unit size <integer_cst 0xb7cb3498 constant 4>
|
|
323 align 32 symtab 0 alias set -1 structural equality>
|
|
324 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
325 align 32 context <function_decl 0xb7da2c80 returner>
|
|
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 <var_decl 0xb7d653c8 D.2157 type <pointer_type 0xb7cc92d8>
|
|
329 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
330 align 32 context <function_decl 0xb7da2c80 returner>
|
|
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 <var_decl 0xb7d65420 D.2158>>> arg 0 <var_decl 0xb7d653c8 D.2157>
|
|
333 arg 1 <var_decl 0xb7d65420 D.2158
|
|
334 type <pointer_type 0xb7da7270 stack type <void_type 0xb7cc9270 void>
|
|
335 sizes-gimplified unsigned SI size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
336 align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8
|
|
337 pointer_to_this <pointer_type 0xb7bb7000>>
|
|
338 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
339 align 32 context <function_decl 0xb7da2c80 returner>
|
|
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])>
|
|
342 quicksort/quicksort_cbc.cbc:29:7>
|
|
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 = &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 = &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 = &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 = &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 = &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 = &all_passes;
|
|
437 NEXT_PASS (pass_all_optimizations);
|
|
438 {
|
|
439 struct opt_pass **p = &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 = &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 = &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 = &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 = &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 = &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 = &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 && 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 && 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 <=> 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 >= 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
|