|
15
|
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="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
|
|
16
|
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
|
|
15
|
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 <li>PowerPCアーキテクチャでの間接継続の追加</li>
|
|
|
266 </ul>
|
|
|
267 </dd>
|
|
|
268 <dt>Second</dt>
|
|
|
269 <dd>C言語との相互利用を可能にした</dd>
|
|
|
270 <dt>Third</dt>
|
|
|
271 <dd>ソースコードメンテナンス性の向上</dd>
|
|
|
272 </dl>
|
|
|
273 </div>
|
|
|
274
|
|
|
275
|
|
|
276
|
|
|
277 <div class="slide">
|
|
|
278 <h1>GNU コンパイラコレクション (GCC)</h1>
|
|
|
279 <div style="width:50%;float:right;">
|
|
|
280 <p class="subtitle">GCCでのコンパイルの流れ</p>
|
|
|
281 <ul style="padding-left:3em">
|
|
|
282 <li>フロントエンド</li>
|
|
|
283 <li>ミドルエンド</li>
|
|
|
284 <li>バックエンド</li>
|
|
|
285 </ul>
|
|
|
286 </div>
|
|
|
287 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
|
|
|
288 </div>
|
|
|
289
|
|
|
290 <div class="slide">
|
|
|
291 <h1>GNU コンパイラコレクション (GCC)</h1>
|
|
|
292 <div style="width:50%;float:right;">
|
|
|
293 <p class="subtitle">GCCでのコンパイルの流れ</p>
|
|
|
294 <ul style="padding-left:3em">
|
|
|
295 <li>フロントエンド</li>
|
|
|
296 <li>ミドルエンド</li>
|
|
|
297 <li>バックエンド</li>
|
|
|
298 </ul>
|
|
|
299 </div>
|
|
|
300 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
|
|
|
301 </div>
|
|
|
302
|
|
|
303
|
|
|
304 <div class="slide">
|
|
|
305 <h1>First: 軽量継続の実装</h1>
|
|
|
306 <p class="subtitle">軽量継続を実装するには？</p>
|
|
|
307 <ul>
|
|
16
|
308 <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
|
|
15
|
309 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
|
|
|
310 <li>関数コール(call命令)ではもちろんダメ</li>
|
|
|
311 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
|
|
|
312 <li>スタックを拡張してはいけない</li>
|
|
16
|
313 <li>加えて、GCCでは<em>関数をベース</em>にしなければならない</li>
|
|
15
|
314 </ul>
|
|
16
|
315 <p class="subtitle">そこで、<dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
|
|
15
|
316 </div>
|
|
|
317
|
|
|
318 <div class="slide">
|
|
|
319 <h1>First: 軽量継続の実装</h1>
|
|
|
320 <p class="subtitle">末尾呼出ってなに？</p>
|
|
|
321 <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
|
|
|
322 <ul>
|
|
|
323 <li>リターンの直前の関数呼び出しのこと</li>
|
|
|
324 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
|
|
|
325 <li>元の関数に戻らないため少し高速に</li>
|
|
|
326 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
|
|
|
327 </ul>
|
|
|
328 </div>
|
|
|
329
|
|
|
330 <div class="slide">
|
|
|
331 <h1>First: 軽量継続の実装</h1>
|
|
|
332 <p class="subtitle">末尾呼出ってなに？</p>
|
|
|
333 <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
|
|
|
334 <ul>
|
|
|
335 <li>リターンの直前の関数呼び出しのこと</li>
|
|
|
336 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
|
|
|
337 <li>元の関数に戻らないため少し高速に</li>
|
|
|
338 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
|
|
|
339 </ul>
|
|
|
340 <p class="subtitle incremental">この末尾呼出(TCE)を強制して軽量継続を実装！</p>
|
|
|
341 </div>
|
|
|
342
|
|
|
343 <div class="slide">
|
|
16
|
344 <h1>First: 軽量継続の実装</h1>
|
|
|
345 <p class="subtitle">プログラム実行時のスタックの変化</p>
|
|
17
|
346 <img style="float:right; width:50%; margin:1em; " src="figures/interfacestack.png" />
|
|
|
347 <ul>
|
|
|
348 <li>スタックの拡張はしなくなる</li>
|
|
|
349 <li>継続されるデータはインタフェイスのみ</li>
|
|
|
350 <li>継続の際に古いデータは上書きされる</li>
|
|
|
351 </ul>
|
|
16
|
352 </div>
|
|
|
353
|
|
|
354 <div class="slide">
|
|
15
|
355 <h1>First: x86における高速化</h1>
|
|
|
356 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
|
|
|
357 <ul>
|
|
|
358 <li>特にx86アーキテクチャ</li>
|
|
|
359 <li><em class="weak">あくまで関数がベース</em>なので</li>
|
|
|
360 <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
|
|
|
361 <li>これをレジスタにすれば高速化が可能</li>
|
|
|
362 </ul>
|
|
|
363 <p class="subtitle">fastcallの導入</p>
|
|
|
364 <ul>
|
|
|
365 <li>GCCの独自拡張機能</li>
|
|
|
366 <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
|
|
|
367 </ul>
|
|
|
368 </div>
|
|
|
369
|
|
|
370 <div class="slide">
|
|
|
371 <h1>First: x86における高速化</h1>
|
|
|
372 <p class="subtitle">fastcallの強制</p>
|
|
|
373 <ul>
|
|
|
374 <li>通常は以下の様に定義される
|
|
|
375 <pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
|
|
|
376 </code></pre></li>
|
|
|
377 <li>しかしこれを毎回ユーザが書くのは変</li>
|
|
|
378 <li>やはりフロントエンドにて、強制するべき</li>
|
|
|
379 <li>型の構文木を生成した際にfastcall属性を付加</li>
|
|
|
380 </ul>
|
|
|
381 <p class="subtitle incremental">これで軽量継続制御が高速化される！</p>
|
|
|
382 </div>
|
|
|
383
|
|
|
384 <div class="slide">
|
|
|
385 <h1>First: CbCコンパイラ実装の評価</h1>
|
|
|
386 <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
|
|
|
387 <ul>
|
|
|
388 <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
|
|
|
389 <li>コンパイラの出力した実行ファイルを比較</li>
|
|
|
390 <li>CbCでのquicksort例題を用意</li>
|
|
|
391 <li>実行速度、ファイルサイズ</li>
|
|
|
392 <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
|
|
|
393 </ul>
|
|
|
394 <p class="subtitle">実行環境</p>
|
|
|
395 <ul>
|
|
|
396 <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
|
|
|
397 <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
|
|
|
398 <li>OSはLinuxとOS Xを使用する</li>
|
|
|
399 </ul>
|
|
|
400 </div>
|
|
|
401
|
|
|
402 <div class="slide">
|
|
|
403 <h1>First: 性能評価（速度比較） vs.旧ver</h1>
|
|
|
404 <p class="subtitle">速度測定結果(単位:秒)</p>
|
|
|
405 <table>
|
|
|
406 <tr>
|
|
|
407 <th></th>
|
|
|
408 <th colspan="2">新CbCGCC</th>
|
|
|
409 <th colspan="2">旧CbCGCC</th>
|
|
|
410 </tr>
|
|
|
411 <tr>
|
|
|
412 <td></td>
|
|
|
413 <th>最適化無し</th>
|
|
|
414 <th>最適化有り</th>
|
|
|
415 <th>最適化無し</th>
|
|
|
416 <th>最適化有り</th>
|
|
|
417 </tr>
|
|
|
418 <tr>
|
|
|
419 <td>x86/OS X</td>
|
|
|
420 <td>5.907</td>
|
|
|
421 <td>2.434</td>
|
|
|
422 <td>4.668</td>
|
|
|
423 <td>3.048</td>
|
|
|
424 </tr>
|
|
|
425 <tr>
|
|
|
426 <td>x86/Linux</td>
|
|
|
427 <td>5.715</td>
|
|
|
428 <td>2.401</td>
|
|
|
429 <td>4.525</td>
|
|
|
430 <td>2.851</td>
|
|
|
431 </tr>
|
|
|
432 </table>
|
|
|
433 <p class="subtitle">評価</p>
|
|
|
434 <ul>
|
|
|
435 <li>最適化無の場合は遅くなった </li>
|
|
|
436 <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
|
|
|
437 <li>fastcallの効果が十分に出ている</li>
|
|
|
438 </ul>
|
|
|
439 </div>
|
|
|
440
|
|
|
441
|
|
|
442 <div class="slide">
|
|
|
443 <h1>First: 性能評価（速度比較）</h1>
|
|
|
444 <p class="subtitle">速度測定結果(単位:秒)</p>
|
|
|
445 <table>
|
|
|
446 <tr>
|
|
|
447 <td></td>
|
|
|
448 <td>最適化なしのGCC</td>
|
|
|
449 <td>最適化付きのGCC</td>
|
|
|
450 <td>micro-c</td>
|
|
|
451 </tr>
|
|
|
452 <tr>
|
|
|
453 <td>x86/OS X</td>
|
|
|
454 <td>5.901</td>
|
|
|
455 <td>2.434</td>
|
|
|
456 <td>2.857</td>
|
|
|
457 </tr>
|
|
|
458 <tr>
|
|
|
459 <td>x86/Linux</td>
|
|
|
460 <td>5.732</td>
|
|
|
461 <td>2.401</td>
|
|
|
462 <td>2.254</td>
|
|
|
463 </tr>
|
|
|
464 <tr>
|
|
|
465 <td>ppc/OS X</td>
|
|
|
466 <td>14.875</td>
|
|
|
467 <td>2.146</td>
|
|
|
468 <td>4.811</td>
|
|
|
469 </tr>
|
|
|
470 <tr>
|
|
|
471 <td>ppc/Linux</td>
|
|
|
472 <td>19.793</td>
|
|
|
473 <td>3.955</td>
|
|
|
474 <td>6.454</td>
|
|
|
475 </tr>
|
|
|
476 <tr>
|
|
|
477 <td>ppc/PS3</td>
|
|
|
478 <td>39.176</td>
|
|
|
479 <td>5.874</td>
|
|
|
480 <td>11.121</td>
|
|
|
481 </tr>
|
|
|
482 </table>
|
|
|
483 <p class="subtitle">結果(micro-cとの比較)</p>
|
|
|
484 <ul>
|
|
|
485 <li>x86では速度にあまり差が出なかった</li>
|
|
|
486 <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
|
|
|
487 <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
|
|
|
488 </ul>
|
|
|
489 <p class="subtitle">この違いはどこから？</p>
|
|
|
490 <ul style="font-size:95%;">
|
|
|
491 <li>実際にアセンブラを出力して比較、その結果</li>
|
|
|
492 <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
|
|
|
493 <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
|
|
|
494 <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
|
|
|
495 <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
|
|
|
496 </ul>
|
|
|
497 </div>
|
|
|
498
|
|
|
499
|
|
|
500 <div class="slide">
|
|
|
501 <h1>Second: Cとの相互利用</h1>
|
|
|
502 <p class="subtitle">なぜそれが必要か</p>
|
|
|
503 <ul>
|
|
|
504 <li>既存のソフトウェアを無駄にはできない</li>
|
|
|
505 <li>ソースコード上での互換性がある事が望ましい</li>
|
|
|
506 <li>CbCからCの関数を呼び出すのは問題ない</li>
|
|
|
507 <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
|
|
|
508 </ul>
|
|
|
509 <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
|
|
|
510 <ul>
|
|
|
511 <li>軽量継続に、スタックの情報を加える</li>
|
|
|
512 <li>関数からのみ使用可能</li>
|
|
|
513 </ul>
|
|
|
514 </div>
|
|
|
515
|
|
|
516 <div class="slide" style="font-size:95%;">
|
|
|
517 <h1>Second: Cとの相互利用</h1>
|
|
|
518 <pre style="float:right; width-max:45%">
|
|
|
519 <code>typedef code (*NEXT)(int);
|
|
|
520 int main(int argc, char **argv) {
|
|
|
521 int i,a;
|
|
|
522 i = atoi(argv[1]);
|
|
|
523 <em>a = factor(i);</em>
|
|
|
524 printf("%d! = %d\n", a);
|
|
|
525 }
|
|
|
526 int factor(int x) {
|
|
|
527 NEXT ret = <em>__return</em>;
|
|
|
528 goto factor0(1, x, ret);
|
|
|
529 }
|
|
|
530 code
|
|
|
531 factor0(int prod,int x,NEXT next) {
|
|
|
532 if (x >= 1) {
|
|
|
533 goto factor0(prod*x, x-1, next);
|
|
|
534 } else {
|
|
|
535 <em>goto (*next)(prod);</em>
|
|
|
536 }
|
|
|
537 }
|
|
|
538 </code></pre>
|
|
|
539 <p class="subtitle">環境付き継続の使用例</p>
|
|
|
540 <ul>
|
|
16
|
541 <li><code><em>__return</em></code>で表される特殊なコードセグメント</li>
|
|
15
|
542 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
|
|
|
543 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
|
|
|
544 </ul>
|
|
|
545 </div>
|
|
|
546
|
|
|
547 <div class="slide" style="font-size:95%;">
|
|
|
548 <h1>Second: Cとの相互利用</h1>
|
|
|
549 <p class="subtitle">内部関数を用いた実装</p>
|
|
|
550 <ul>
|
|
|
551 <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
|
|
|
552 <li>内部関数の中からは外の関数にgotoして脱出</li>
|
|
|
553 </ul>
|
|
|
554 <pre><code>int factor(int x) {
|
|
|
555 int retval;
|
|
|
556
|
|
|
557 <em class="weak">code __return(int val) {
|
|
|
558 retval = val;
|
|
|
559 goto label;
|
|
|
560 }
|
|
|
561 if (0) {
|
|
|
562 label:
|
|
|
563 return retval;
|
|
|
564 }</em>
|
|
|
565
|
|
|
566 NEXT ret = <em>__return</em>;
|
|
|
567 goto factor0(1, x, ret);
|
|
|
568 } </code></pre>
|
|
|
569 </div>
|
|
|
570
|
|
|
571
|
|
|
572 <div class="slide" style="font-size:95%;">
|
|
|
573 <h1>Second: Cとの相互利用・評価</h1>
|
|
|
574 <p class="subtitle">この取り組みにより</p>
|
|
|
575 <ul>
|
|
16
|
576 <li>これにより、<dfn>Continuation based C</dfn> の全仕様を満たした</li>
|
|
15
|
577 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
|
|
|
578 </ul>
|
|
|
579 </div>
|
|
|
580
|
|
|
581
|
|
|
582
|
|
|
583 <div class="slide">
|
|
|
584 <h1>まとめ</h1>
|
|
|
585 <p class="subtitle">本研究での取り組み</p>
|
|
|
586 <dl>
|
|
|
587 <dt>First</dt>
|
|
17
|
588 <dd><em>CbCGCCにて実用レベルのCbCプログラムが動作可能となった</em>
|
|
15
|
589 <ul>
|
|
16
|
590 <li>軽量継続における引数順序の制限を取り除いた</li>
|
|
15
|
591 <li>PowerPCでの間接継続の制限を取り除いた</li>
|
|
|
592 <li><em>x86アーキテクチャにて高速化を行った</em></li>
|
|
|
593 </ul>
|
|
|
594 </dd>
|
|
|
595 <dt>Second</dt>
|
|
|
596 <dd><em>Cとの相互利用性の向上</em></dd>
|
|
|
597 <dt>Third</dt>
|
|
|
598 <dd>ソースコードメンテナンス性の向上</dd>
|
|
|
599 </dl>
|
|
|
600 </div>
|
|
|
601
|
|
|
602 <div class="slide" style="font-size:95%;">
|
|
|
603 <h1>まとめ</h1>
|
|
|
604 <p class="subtitle">本研究での成果</p>
|
|
|
605 <dl>
|
|
|
606 <dt>成果1</dt>
|
|
|
607 <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
|
|
|
608 <dt>成果2</dt>
|
|
|
609 <dd>CbCが多数のアーキテクチャに対応
|
|
|
610 <ul>
|
|
|
611 <li>20以上のアーキテクチャ</li>
|
|
|
612 <li>特に64bitのx86, SPUがうれしい</li>
|
|
|
613 </ul> </dd>
|
|
|
614 <dt>成果3</dt>
|
|
|
615 <dd>CbCの高速化
|
|
|
616 <ul>
|
|
|
617 <li>x86においてmicro-cと互角の速度を達成</li>
|
|
|
618 <li>PowerPCでは2倍の速度</li>
|
|
|
619 </ul></dd>
|
|
|
620 </dl>
|
|
|
621 </div>
|
|
|
622
|
|
|
623 <div class="slide">
|
|
|
624 <h1>今後の課題</h1>
|
|
|
625 <p class="subtitle"></p>
|
|
|
626 <ul>
|
|
|
627 <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li>
|
|
|
628 <li>タブロー方を用いた検証</li>
|
|
|
629 <li>TaskManagerのCbC実装</li>
|
|
|
630 </ul>
|
|
|
631 <p class="subtitle">CbC言語の今後</p>
|
|
|
632 <ul>
|
|
|
633 <li>オブジェクティブなCbCの設計</li>
|
|
|
634 <li>データセグメントの導入</li>
|
|
|
635 <li>スケジューラのためのリフレクション</li>
|
|
|
636 </ul>
|
|
|
637 </div>
|
|
|
638
|
|
|
639
|
|
|
640 <div class="slide">
|
|
|
641 <h1>おわり</h1>
|
|
|
642 <p class="subtitle">ありがとうございました</p>
|
|
|
643 </div>
|
|
|
644
|
|
|
645
|
|
|
646
|
|
|
647
|
|
|
648
|
|
|
649
|
|
|
650
|
|
|
651
|
|
16
|
652 <div class="slide">
|
|
|
653 <h1>継続とはなんなのか？</h1>
|
|
|
654 <p class="subtitle">継続</p>
|
|
|
655 <ul>
|
|
|
656 <li>現在の処理を続行するための情報
|
|
|
657 <ul>
|
|
|
658 <li>Cならば続く命令のアドレスや</li>
|
|
|
659 <li>命令に必要な値、</li>
|
|
|
660 <li>スタックなど、その環境全てを含む</li>
|
|
|
661 </ul>
|
|
|
662 </li>
|
|
|
663 </ul>
|
|
|
664 <p class="subtitle">CbCでの軽量継続</p>
|
|
|
665 <ul>
|
|
|
666 <li>継続からスタックに関する情報を落とす</li>
|
|
|
667 <li>続く命令とデータのみのシンプルな継続</li>
|
|
|
668 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
|
|
|
669 </ul>
|
|
|
670 </div>
|
|
|
671
|
|
|
672 <div class="slide" style="font-size:95%;">
|
|
|
673 <h1>コードセグメントと軽量継続の記述</h1>
|
|
|
674 <pre style="float:right; width-max:45%">
|
|
|
675 <code>typedef code (*NEXT)(int);
|
|
|
676 int main(int argc, char **argv) {
|
|
|
677 int i;
|
|
|
678 i = atoi(argv[1]);
|
|
|
679 goto factor(i, print_fact);
|
|
|
680 }
|
|
|
681 <em>code factor(int x, NEXT next)</em> {
|
|
|
682 goto factor0(1, x, next);
|
|
|
683 }
|
|
|
684 code factor0(int prod,int x,NEXT next) {
|
|
|
685 if (x >= 1) {
|
|
|
686 goto factor0(prod*x, x-1, next);
|
|
|
687 } else {
|
|
|
688 <em>goto (*next)(prod);</em>
|
|
|
689 }
|
|
|
690 }
|
|
|
691 code print_fact(int value) {
|
|
|
692 printf("factorial = %d\n", value);
|
|
|
693 exit(0);
|
|
|
694 } </code></pre>
|
|
|
695 <p class="subtitle">実際のプログラム記述は？</p>
|
|
|
696 <ul>
|
|
|
697 <li>コードセグメント定義
|
|
|
698 <ul>
|
|
|
699 <li><code>codeキーワードで宣言</code></li>
|
|
|
700 <li>書式は関数と同じ</li>
|
|
|
701 </ul>
|
|
|
702 </li>
|
|
|
703 <li>軽量継続制御
|
|
|
704 <ul>
|
|
|
705 <li><code>goto</code>キーワードと引数</li>
|
|
|
706 <li>コードセグメントの最初に飛ぶ</li>
|
|
|
707 <li>コードセグメントポインタによる間接継続も可能</li>
|
|
|
708 </ul>
|
|
|
709 </li>
|
|
|
710 </ul>
|
|
|
711 </div>
|
|
|
712
|
|
|
713 <div class="slide">
|
|
|
714 <h1>これまでのCbC</h1>
|
|
|
715 <p class="subtitle"></p>
|
|
|
716 <dl>
|
|
|
717 <dt>2000</dt>
|
|
|
718 <dd>micro-cをベースとしたコンパイラの完成<br/>
|
|
|
719 x86, PowerPC, ARM, MIPS.
|
|
|
720 </dd>
|
|
|
721 <dt>2002</dt>
|
|
|
722 <dd>CbCを用いた分散計算</dd>
|
|
|
723 <dt>2005</dt>
|
|
|
724 <dd>CbCを用いたプログラム分割手法</dd>
|
|
|
725 <dt>2006</dt>
|
|
|
726 <dd>CbCによるSPUマシンのシミュレータ</dd>
|
|
|
727 <dt>2007</dt>
|
|
|
728 <dd>時相論理をベースとしたCbCプログラムの検証</dd>
|
|
|
729 <dt>2008</dt>
|
|
|
730 <dd>GCCをベースとしたコンパイラが開発される</dd>
|
|
|
731 <dt>2010</dt>
|
|
|
732 <dd>GCCベースコンパイラを実用レベルに拡張</dd>
|
|
|
733 </dl>
|
|
|
734 </div>
|
|
|
735
|
|
|
736 <div class="slide">
|
|
|
737 <h1>本研究での取り組み</h1>
|
|
|
738 <p class="subtitle">取り組み</p>
|
|
|
739 <dl>
|
|
|
740 <dt>First</dt>
|
|
|
741 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
|
|
|
742 <ul>
|
|
|
743 <li>軽量継続の実装、これまでの制限の除去</li>
|
|
|
744 <li>x86アーキテクチャにて高速化を行った</li>
|
|
|
745 </ul>
|
|
|
746 </dd>
|
|
|
747 <dt>Second</dt>
|
|
|
748 <dd>C言語との相互利用を可能にした</dd>
|
|
|
749 <dt>Third</dt>
|
|
|
750 <dd>ソースコードメンテナンス性の向上</dd>
|
|
|
751 </dl>
|
|
|
752 </div>
|
|
|
753
|
|
|
754
|
|
|
755
|
|
|
756 <div class="slide">
|
|
|
757 <h1>GNU コンパイラコレクション (GCC)</h1>
|
|
|
758 <div style="width:50%;float:right;">
|
|
|
759 <p class="subtitle">GCCでのコンパイルの流れ</p>
|
|
|
760 <ul style="padding-left:3em">
|
|
|
761 <li>フロントエンド</li>
|
|
|
762 <li>ミドルエンド</li>
|
|
|
763 <li>バックエンド</li>
|
|
|
764 </ul>
|
|
|
765 </div>
|
|
|
766 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
|
|
|
767 </div>
|
|
|
768
|
|
|
769 <div class="slide">
|
|
|
770 <h1>GNU コンパイラコレクション (GCC)</h1>
|
|
|
771 <div style="width:50%;float:right;">
|
|
|
772 <p class="subtitle">GCCでのコンパイルの流れ</p>
|
|
|
773 <ul style="padding-left:3em">
|
|
|
774 <li>フロントエンド</li>
|
|
|
775 <li>ミドルエンド</li>
|
|
|
776 <li>バックエンド</li>
|
|
|
777 </ul>
|
|
|
778 </div>
|
|
|
779 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
|
|
|
780 </div>
|
|
|
781
|
|
|
782
|
|
|
783 <div class="slide">
|
|
|
784 <h1>GCC フロントエンド</h1>
|
|
|
785 <p class="subtitle">GCCにおける構文解析部</p>
|
|
|
786 <ul class="outline">
|
|
|
787 <li>C,Java,Adaなど、言語毎に違う</li>
|
|
|
788 <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li>
|
|
|
789 <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li>
|
|
|
790 <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li>
|
|
|
791 <li>GIMPLEの内部表現例
|
|
|
792 <pre><code>
|
|
|
793 <call_expr 0xb7bc7850
|
|
|
794 type <void_type 0xb7cc9270 void VOID
|
|
|
795 align 8 symtab 0 alias set -1 canonical type 0xb7cc9270
|
|
|
796 pointer_to_this <pointer_type 0xb7cc92d8>>
|
|
|
797 side-effects addressable tree_5
|
|
|
798 fn <var_decl 0xb7d65370 D.2156
|
|
|
799 type <pointer_type 0xb7da74e0 type <function_type 0xb7da7478>
|
|
|
800 unsigned SI
|
|
|
801 size <integer_cst 0xb7cb36ac constant 32>
|
|
|
802 unit size <integer_cst 0xb7cb3498 constant 4>
|
|
|
803 align 32 symtab 0 alias set -1 structural equality>
|
|
|
804 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
|
805 align 32 context <function_decl 0xb7da2c80 returner>
|
|
|
806 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
|
|
|
807 (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32])
|
|
|
808 chain <var_decl 0xb7d653c8 D.2157 type <pointer_type 0xb7cc92d8>
|
|
|
809 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
|
810 align 32 context <function_decl 0xb7da2c80 returner>
|
|
|
811 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
|
|
|
812 (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain <var_decl 0xb7d65420 D.2158>>> arg 0 <var_decl 0xb7d653c8 D.2157>
|
|
|
813 arg 1 <var_decl 0xb7d65420 D.2158
|
|
|
814 type <pointer_type 0xb7da7270 stack type <void_type 0xb7cc9270 void>
|
|
|
815 sizes-gimplified unsigned SI size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
|
816 align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8
|
|
|
817 pointer_to_this <pointer_type 0xb7bb7000>>
|
|
|
818 used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size <integer_cst 0xb7cb36ac 32> unit size <integer_cst 0xb7cb3498 4>
|
|
|
819 align 32 context <function_decl 0xb7da2c80 returner>
|
|
|
820 (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
|
|
|
821 (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])>
|
|
|
822 quicksort/quicksort_cbc.cbc:29:7>
|
|
|
823 </code></pre>
|
|
|
824 <p class="subtitle">全ての構文はこのGIMPLEで表される</p>
|
|
|
825 </li>
|
|
|
826 </ul>
|
|
|
827 <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p>
|
|
|
828 </div>
|
|
|
829
|
|
|
830 <div class="slide" style="font-size:95%">
|
|
|
831 <h1>GCC ミドルエンド</h1>
|
|
|
832 <p class="subtitle">GIMPLEからRTLへの変換と最適化</p>
|
|
|
833 <ul class="outline">
|
|
|
834 <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li>
|
|
|
835 <li>登録されたpassを一つ一つ実行する</li>
|
|
|
836 <li>最初にGIMPLEの最適化がたくさんある</li>
|
|
|
837 <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li>
|
|
|
838 <li>最後にRTLの最適化がまた大量にある
|
|
|
839 <pre style="font-size:80%"><code>
|
|
|
840 p = &all_lowering_passes;
|
|
|
841 NEXT_PASS (pass_remove_useless_stmts);
|
|
|
842 NEXT_PASS (pass_mudflap_1);
|
|
|
843 NEXT_PASS (pass_lower_omp);
|
|
|
844 NEXT_PASS (pass_lower_cf);
|
|
|
845 NEXT_PASS (pass_refactor_eh);
|
|
|
846 NEXT_PASS (pass_lower_eh);
|
|
|
847 NEXT_PASS (pass_build_cfg);
|
|
|
848 NEXT_PASS (pass_lower_complex_O0);
|
|
|
849 NEXT_PASS (pass_lower_vector);
|
|
|
850 #ifndef noCbC
|
|
|
851 //NEXT_PASS (pass_warn_function_return);
|
|
|
852 #else
|
|
|
853 NEXT_PASS (pass_warn_function_return);
|
|
|
854 #endif
|
|
|
855 NEXT_PASS (pass_build_cgraph_edges);
|
|
|
856 NEXT_PASS (pass_inline_parameters);
|
|
|
857 *p = NULL;
|
|
|
858
|
|
|
859 /* Interprocedural optimization passes. */
|
|
|
860 p = &all_ipa_passes;
|
|
|
861 NEXT_PASS (pass_ipa_function_and_variable_visibility);
|
|
|
862 NEXT_PASS (pass_ipa_early_inline);
|
|
|
863 {
|
|
|
864 struct opt_pass **p = &pass_ipa_early_inline.pass.sub;
|
|
|
865 NEXT_PASS (pass_early_inline);
|
|
|
866 NEXT_PASS (pass_inline_parameters);
|
|
|
867 NEXT_PASS (pass_rebuild_cgraph_edges);
|
|
|
868 }
|
|
|
869 NEXT_PASS (pass_early_local_passes);
|
|
|
870 {
|
|
|
871 struct opt_pass **p = &pass_early_local_passes.pass.sub;
|
|
|
872 NEXT_PASS (pass_tree_profile);
|
|
|
873 NEXT_PASS (pass_cleanup_cfg);
|
|
|
874 NEXT_PASS (pass_init_datastructures);
|
|
|
875 NEXT_PASS (pass_expand_omp);
|
|
|
876
|
|
|
877 NEXT_PASS (pass_referenced_vars);
|
|
|
878 NEXT_PASS (pass_reset_cc_flags);
|
|
|
879 NEXT_PASS (pass_build_ssa);
|
|
|
880 NEXT_PASS (pass_early_warn_uninitialized);
|
|
|
881 NEXT_PASS (pass_all_early_optimizations);
|
|
|
882 {
|
|
|
883 struct opt_pass **p = &pass_all_early_optimizations.pass.sub;
|
|
|
884 NEXT_PASS (pass_rebuild_cgraph_edges);
|
|
|
885 NEXT_PASS (pass_early_inline);
|
|
|
886 NEXT_PASS (pass_rename_ssa_copies);
|
|
|
887 NEXT_PASS (pass_ccp);
|
|
|
888 NEXT_PASS (pass_forwprop);
|
|
|
889 NEXT_PASS (pass_update_address_taken);
|
|
|
890 NEXT_PASS (pass_sra_early);
|
|
|
891 NEXT_PASS (pass_copy_prop);
|
|
|
892 NEXT_PASS (pass_merge_phi);
|
|
|
893 NEXT_PASS (pass_cd_dce);
|
|
|
894 NEXT_PASS (pass_simple_dse);
|
|
|
895 NEXT_PASS (pass_tail_recursion);
|
|
|
896 NEXT_PASS (pass_convert_switch);
|
|
|
897 NEXT_PASS (pass_profile);
|
|
|
898 }
|
|
|
899 NEXT_PASS (pass_release_ssa_names);
|
|
|
900 NEXT_PASS (pass_rebuild_cgraph_edges);
|
|
|
901 NEXT_PASS (pass_inline_parameters);
|
|
|
902 }
|
|
|
903 NEXT_PASS (pass_ipa_increase_alignment);
|
|
|
904 NEXT_PASS (pass_ipa_matrix_reorg);
|
|
|
905 NEXT_PASS (pass_ipa_cp);
|
|
|
906 NEXT_PASS (pass_ipa_inline);
|
|
|
907 NEXT_PASS (pass_ipa_reference);
|
|
|
908 NEXT_PASS (pass_ipa_pure_const);
|
|
|
909 NEXT_PASS (pass_ipa_type_escape);
|
|
|
910 NEXT_PASS (pass_ipa_pta);
|
|
|
911 NEXT_PASS (pass_ipa_struct_reorg);
|
|
|
912 *p = NULL;
|
|
|
913
|
|
|
914 /* These passes are run after IPA passes on every function that is being
|
|
|
915 output to the assembler file. */
|
|
|
916 p = &all_passes;
|
|
|
917 NEXT_PASS (pass_all_optimizations);
|
|
|
918 {
|
|
|
919 struct opt_pass **p = &pass_all_optimizations.pass.sub;
|
|
|
920 /* Initial scalar cleanups before alias computation.
|
|
|
921 They ensure memory accesses are not indirect wherever possible. */
|
|
|
922 NEXT_PASS (pass_strip_predict_hints);
|
|
|
923 NEXT_PASS (pass_update_address_taken);
|
|
|
924 NEXT_PASS (pass_rename_ssa_copies);
|
|
|
925 NEXT_PASS (pass_complete_unrolli);
|
|
|
926 NEXT_PASS (pass_ccp);
|
|
|
927 NEXT_PASS (pass_forwprop);
|
|
|
928 /* Ideally the function call conditional
|
|
|
929 dead code elimination phase can be delayed
|
|
|
930 till later where potentially more opportunities
|
|
|
931 can be found. Due to lack of good ways to
|
|
|
932 update VDEFs associated with the shrink-wrapped
|
|
|
933 calls, it is better to do the transformation
|
|
|
934 here where memory SSA is not built yet. */
|
|
|
935 NEXT_PASS (pass_call_cdce);
|
|
|
936 /* pass_build_alias is a dummy pass that ensures that we
|
|
|
937 execute TODO_rebuild_alias at this point. Re-building
|
|
|
938 alias information also rewrites no longer addressed
|
|
|
939 locals into SSA form if possible. */
|
|
|
940 NEXT_PASS (pass_build_alias);
|
|
|
941 NEXT_PASS (pass_return_slot);
|
|
|
942 NEXT_PASS (pass_phiprop);
|
|
|
943 NEXT_PASS (pass_fre);
|
|
|
944 NEXT_PASS (pass_copy_prop);
|
|
|
945 NEXT_PASS (pass_merge_phi);
|
|
|
946 NEXT_PASS (pass_vrp);
|
|
|
947 NEXT_PASS (pass_dce);
|
|
|
948 NEXT_PASS (pass_cselim);
|
|
|
949 NEXT_PASS (pass_tree_ifcombine);
|
|
|
950 NEXT_PASS (pass_phiopt);
|
|
|
951 NEXT_PASS (pass_tail_recursion);
|
|
|
952 NEXT_PASS (pass_ch);
|
|
|
953 NEXT_PASS (pass_stdarg);
|
|
|
954 NEXT_PASS (pass_lower_complex);
|
|
|
955 NEXT_PASS (pass_sra);
|
|
|
956 NEXT_PASS (pass_rename_ssa_copies);
|
|
|
957 NEXT_PASS (pass_dominator);
|
|
|
958 /* The only const/copy propagation opportunities left after
|
|
|
959 DOM should be due to degenerate PHI nodes. So rather than
|
|
|
960 run the full propagators, run a specialized pass which
|
|
|
961 only examines PHIs to discover const/copy propagation
|
|
|
962 opportunities. */
|
|
|
963 NEXT_PASS (pass_phi_only_cprop);
|
|
|
964 NEXT_PASS (pass_dse);
|
|
|
965 NEXT_PASS (pass_reassoc);
|
|
|
966 NEXT_PASS (pass_dce);
|
|
|
967 NEXT_PASS (pass_forwprop);
|
|
|
968 NEXT_PASS (pass_phiopt);
|
|
|
969 NEXT_PASS (pass_object_sizes);
|
|
|
970 NEXT_PASS (pass_ccp);
|
|
|
971 NEXT_PASS (pass_copy_prop);
|
|
|
972 NEXT_PASS (pass_fold_builtins);
|
|
|
973 NEXT_PASS (pass_cse_sincos);
|
|
|
974 NEXT_PASS (pass_split_crit_edges);
|
|
|
975 NEXT_PASS (pass_pre);
|
|
|
976 NEXT_PASS (pass_sink_code);
|
|
|
977 NEXT_PASS (pass_tree_loop);
|
|
|
978 {
|
|
|
979 struct opt_pass **p = &pass_tree_loop.pass.sub;
|
|
|
980 NEXT_PASS (pass_tree_loop_init);
|
|
|
981 NEXT_PASS (pass_copy_prop);
|
|
|
982 NEXT_PASS (pass_dce_loop);
|
|
|
983 NEXT_PASS (pass_lim);
|
|
|
984 NEXT_PASS (pass_predcom);
|
|
|
985 NEXT_PASS (pass_tree_unswitch);
|
|
|
986 NEXT_PASS (pass_scev_cprop);
|
|
|
987 NEXT_PASS (pass_empty_loop);
|
|
|
988 NEXT_PASS (pass_record_bounds);
|
|
|
989 NEXT_PASS (pass_check_data_deps);
|
|
|
990 NEXT_PASS (pass_loop_distribution);
|
|
|
991 NEXT_PASS (pass_linear_transform);
|
|
|
992 NEXT_PASS (pass_graphite_transforms);
|
|
|
993 NEXT_PASS (pass_iv_canon);
|
|
|
994 NEXT_PASS (pass_if_conversion);
|
|
|
995 NEXT_PASS (pass_vectorize);
|
|
|
996 {
|
|
|
997 struct opt_pass **p = &pass_vectorize.pass.sub;
|
|
|
998 NEXT_PASS (pass_lower_vector_ssa);
|
|
|
999 NEXT_PASS (pass_dce_loop);
|
|
|
1000 }
|
|
|
1001 NEXT_PASS (pass_complete_unroll);
|
|
|
1002 NEXT_PASS (pass_parallelize_loops);
|
|
|
1003 NEXT_PASS (pass_loop_prefetch);
|
|
|
1004 NEXT_PASS (pass_iv_optimize);
|
|
|
1005 NEXT_PASS (pass_tree_loop_done);
|
|
|
1006 }
|
|
|
1007 NEXT_PASS (pass_cse_reciprocals);
|
|
|
1008 NEXT_PASS (pass_convert_to_rsqrt);
|
|
|
1009 NEXT_PASS (pass_reassoc);
|
|
|
1010 NEXT_PASS (pass_vrp);
|
|
|
1011 NEXT_PASS (pass_dominator);
|
|
|
1012 /* The only const/copy propagation opportunities left after
|
|
|
1013 DOM should be due to degenerate PHI nodes. So rather than
|
|
|
1014 run the full propagators, run a specialized pass which
|
|
|
1015 only examines PHIs to discover const/copy propagation
|
|
|
1016 opportunities. */
|
|
|
1017 NEXT_PASS (pass_phi_only_cprop);
|
|
|
1018 NEXT_PASS (pass_cd_dce);
|
|
|
1019 NEXT_PASS (pass_tracer);
|
|
|
1020
|
|
|
1021 /* FIXME: If DCE is not run before checking for uninitialized uses,
|
|
|
1022 we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
|
|
|
1023 However, this also causes us to misdiagnose cases that should be
|
|
|
1024 real warnings (e.g., testsuite/gcc.dg/pr18501.c).
|
|
|
1025
|
|
|
1026 To fix the false positives in uninit-5.c, we would have to
|
|
|
1027 account for the predicates protecting the set and the use of each
|
|
|
1028 variable. Using a representation like Gated Single Assignment
|
|
|
1029 may help. */
|
|
|
1030 NEXT_PASS (pass_late_warn_uninitialized);
|
|
|
1031 NEXT_PASS (pass_dse);
|
|
|
1032 NEXT_PASS (pass_forwprop);
|
|
|
1033 NEXT_PASS (pass_phiopt);
|
|
|
1034 NEXT_PASS (pass_tail_calls);
|
|
|
1035 NEXT_PASS (pass_rename_ssa_copies);
|
|
|
1036 NEXT_PASS (pass_uncprop);
|
|
|
1037 }
|
|
|
1038 NEXT_PASS (pass_del_ssa);
|
|
|
1039 NEXT_PASS (pass_nrv);
|
|
|
1040 NEXT_PASS (pass_mark_used_blocks);
|
|
|
1041 NEXT_PASS (pass_cleanup_cfg_post_optimizing);
|
|
|
1042
|
|
|
1043 NEXT_PASS (pass_warn_function_noreturn);
|
|
|
1044 NEXT_PASS (pass_free_datastructures);
|
|
|
1045 NEXT_PASS (pass_mudflap_2);
|
|
|
1046
|
|
|
1047 NEXT_PASS (pass_free_cfg_annotations);
|
|
|
1048 <em>NEXT_PASS (pass_expand);</em>
|
|
|
1049 NEXT_PASS (pass_rest_of_compilation);
|
|
|
1050 {
|
|
|
1051 struct opt_pass **p = &pass_rest_of_compilation.pass.sub;
|
|
|
1052 NEXT_PASS (pass_init_function);
|
|
|
1053 NEXT_PASS (pass_jump);
|
|
|
1054 NEXT_PASS (pass_rtl_eh);
|
|
|
1055 NEXT_PASS (pass_initial_value_sets);
|
|
|
1056 NEXT_PASS (pass_unshare_all_rtl);
|
|
|
1057 NEXT_PASS (pass_instantiate_virtual_regs);
|
|
|
1058 NEXT_PASS (pass_into_cfg_layout_mode);
|
|
|
1059 NEXT_PASS (pass_jump2);
|
|
|
1060 NEXT_PASS (pass_lower_subreg);
|
|
|
1061 NEXT_PASS (pass_df_initialize_opt);
|
|
|
1062 NEXT_PASS (pass_cse);
|
|
|
1063 NEXT_PASS (pass_rtl_fwprop);
|
|
|
1064 NEXT_PASS (pass_gcse);
|
|
|
1065 NEXT_PASS (pass_rtl_ifcvt);
|
|
|
1066 /* Perform loop optimizations. It might be better to do them a bit
|
|
|
1067 sooner, but we want the profile feedback to work more
|
|
|
1068 efficiently. */
|
|
|
1069 NEXT_PASS (pass_loop2);
|
|
|
1070 {
|
|
|
1071 struct opt_pass **p = &pass_loop2.pass.sub;
|
|
|
1072 NEXT_PASS (pass_rtl_loop_init);
|
|
|
1073 NEXT_PASS (pass_rtl_move_loop_invariants);
|
|
|
1074 NEXT_PASS (pass_rtl_unswitch);
|
|
|
1075 NEXT_PASS (pass_rtl_unroll_and_peel_loops);
|
|
|
1076 NEXT_PASS (pass_rtl_doloop);
|
|
|
1077 NEXT_PASS (pass_rtl_loop_done);
|
|
|
1078 *p = NULL;
|
|
|
1079 }
|
|
|
1080 NEXT_PASS (pass_web);
|
|
|
1081 NEXT_PASS (pass_jump_bypass);
|
|
|
1082 NEXT_PASS (pass_cse2);
|
|
|
1083 NEXT_PASS (pass_rtl_dse1);
|
|
|
1084 NEXT_PASS (pass_rtl_fwprop_addr);
|
|
|
1085 NEXT_PASS (pass_reginfo_init);
|
|
|
1086 NEXT_PASS (pass_inc_dec);
|
|
|
1087 NEXT_PASS (pass_initialize_regs);
|
|
|
1088 NEXT_PASS (pass_outof_cfg_layout_mode);
|
|
|
1089 NEXT_PASS (pass_ud_rtl_dce);
|
|
|
1090 NEXT_PASS (pass_combine);
|
|
|
1091 NEXT_PASS (pass_if_after_combine);
|
|
|
1092 NEXT_PASS (pass_partition_blocks);
|
|
|
1093 NEXT_PASS (pass_regmove);
|
|
|
1094 NEXT_PASS (pass_split_all_insns);
|
|
|
1095 NEXT_PASS (pass_lower_subreg2);
|
|
|
1096 NEXT_PASS (pass_df_initialize_no_opt);
|
|
|
1097 NEXT_PASS (pass_stack_ptr_mod);
|
|
|
1098 NEXT_PASS (pass_mode_switching);
|
|
|
1099 NEXT_PASS (pass_see);
|
|
|
1100 NEXT_PASS (pass_match_asm_constraints);
|
|
|
1101 NEXT_PASS (pass_sms);
|
|
|
1102 NEXT_PASS (pass_sched);
|
|
|
1103 NEXT_PASS (pass_subregs_of_mode_init);
|
|
|
1104 NEXT_PASS (pass_ira);
|
|
|
1105 NEXT_PASS (pass_subregs_of_mode_finish);
|
|
|
1106 NEXT_PASS (pass_postreload);
|
|
|
1107 {
|
|
|
1108 struct opt_pass **p = &pass_postreload.pass.sub;
|
|
|
1109 NEXT_PASS (pass_postreload_cse);
|
|
|
1110 NEXT_PASS (pass_gcse2);
|
|
|
1111 NEXT_PASS (pass_split_after_reload);
|
|
|
1112 NEXT_PASS (pass_branch_target_load_optimize1);
|
|
|
1113 NEXT_PASS (pass_thread_prologue_and_epilogue);
|
|
|
1114 NEXT_PASS (pass_rtl_dse2);
|
|
|
1115 NEXT_PASS (pass_rtl_seqabstr);
|
|
|
1116 NEXT_PASS (pass_stack_adjustments);
|
|
|
1117 NEXT_PASS (pass_peephole2);
|
|
|
1118 NEXT_PASS (pass_if_after_reload);
|
|
|
1119 NEXT_PASS (pass_regrename);
|
|
|
1120 NEXT_PASS (pass_cprop_hardreg);
|
|
|
1121 NEXT_PASS (pass_fast_rtl_dce);
|
|
|
1122 NEXT_PASS (pass_reorder_blocks);
|
|
|
1123 NEXT_PASS (pass_branch_target_load_optimize2);
|
|
|
1124 NEXT_PASS (pass_leaf_regs);
|
|
|
1125 NEXT_PASS (pass_split_before_sched2);
|
|
|
1126 NEXT_PASS (pass_sched2);
|
|
|
1127 NEXT_PASS (pass_stack_regs);
|
|
|
1128 {
|
|
|
1129 struct opt_pass **p = &pass_stack_regs.pass.sub;
|
|
|
1130 NEXT_PASS (pass_split_before_regstack);
|
|
|
1131 NEXT_PASS (pass_stack_regs_run);
|
|
|
1132 }
|
|
|
1133 NEXT_PASS (pass_compute_alignments);
|
|
|
1134 NEXT_PASS (pass_duplicate_computed_gotos);
|
|
|
1135 NEXT_PASS (pass_variable_tracking);
|
|
|
1136 NEXT_PASS (pass_free_cfg);
|
|
|
1137 NEXT_PASS (pass_machine_reorg);
|
|
|
1138 NEXT_PASS (pass_cleanup_barriers);
|
|
|
1139 NEXT_PASS (pass_delay_slots);
|
|
|
1140 NEXT_PASS (pass_split_for_shorten_branches);
|
|
|
1141 NEXT_PASS (pass_convert_to_eh_region_ranges);
|
|
|
1142 NEXT_PASS (pass_shorten_branches);
|
|
|
1143 NEXT_PASS (pass_set_nothrow_function_flags);
|
|
|
1144 NEXT_PASS (pass_final);
|
|
|
1145 }
|
|
|
1146 NEXT_PASS (pass_df_finish);
|
|
|
1147 }
|
|
|
1148 NEXT_PASS (pass_clean_state);
|
|
|
1149 *p = NULL;
|
|
|
1150 </code></pre>
|
|
|
1151 </li>
|
|
|
1152 </ul>
|
|
|
1153 <p class="subtitle">RTL</p>
|
|
|
1154 <ul class="outline">
|
|
|
1155 <li>一般的には中間コードとも呼ばれる</li>
|
|
|
1156 <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li>
|
|
|
1157 <li>RTLの例
|
|
|
1158 <pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [
|
|
|
1159 (set (reg/f:SI 7 sp)
|
|
|
1160 (plus:SI (reg/f:SI 7 sp)
|
|
|
1161 (const_int -1024 [0xfffffc00])))
|
|
|
1162 (clobber (reg:CC 17 flags))
|
|
|
1163 ]) -1 (nil))
|
|
|
1164 </code></pre>
|
|
|
1165 </li>
|
|
|
1166 </ul>
|
|
|
1167 </div>
|
|
|
1168
|
|
|
1169 <div class="slide">
|
|
|
1170 <h1>バックエンド</h1>
|
|
|
1171 <p class="subtitle">RTLからアセンブラに変換する処理</p>
|
|
|
1172 <ul class="outline">
|
|
|
1173 <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li>
|
|
|
1174 <li>アーキテクチャ毎にこのmdが必要になる</li>
|
|
|
1175 <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li>
|
|
|
1176 <li>mdの例
|
|
|
1177 <pre><code>
|
|
|
1178 (define_insn "cmpdi_ccno_1_rex64"
|
|
|
1179 [(set (reg FLAGS_REG)
|
|
|
1180 (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr")
|
|
|
1181 (match_operand:DI 1 "const0_operand" "")))]
|
|
|
1182 "TARGET_64BIT && ix86_match_ccmode (insn, CCNOmode)"
|
|
|
1183 "@
|
|
|
1184 test{q}\t%0, %0
|
|
|
1185 cmp{q}\t{%1, %0|%0, %1}"
|
|
|
1186 [(set_attr "type" "test,icmp")
|
|
|
1187 (set_attr "length_immediate" "0,1")
|
|
|
1188 (set_attr "mode" "DI")])
|
|
|
1189
|
|
|
1190 (define_insn "*cmpdi_minus_1_rex64"
|
|
|
1191 [(set (reg FLAGS_REG)
|
|
|
1192 (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r")
|
|
|
1193 (match_operand:DI 1 "x86_64_general_operand" "re,mr"))
|
|
|
1194 (const_int 0)))]
|
|
|
1195 "TARGET_64BIT && ix86_match_ccmode (insn, CCGOCmode)"
|
|
|
1196 "cmp{q}\t{%1, %0|%0, %1}"
|
|
|
1197 [(set_attr "type" "icmp")
|
|
|
1198 (set_attr "mode" "DI")])
|
|
|
1199 </code></pre></li>
|
|
|
1200 </ul>
|
|
|
1201 </div>
|
|
|
1202
|
|
|
1203 <div class="slide">
|
|
|
1204 <h1>本研究での取り組み</h1>
|
|
|
1205 <p class="subtitle">取り組み</p>
|
|
|
1206 <dl>
|
|
|
1207 <dt>First</dt>
|
|
|
1208 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
|
|
|
1209 <ul>
|
|
|
1210 <li>軽量継続の実装、これまでの制限の除去</li>
|
|
|
1211 <li>x86アーキテクチャにて高速化を行った</li>
|
|
|
1212 </ul>
|
|
|
1213 </dd>
|
|
|
1214 <dt>Second</dt>
|
|
|
1215 <dd>C言語との互換性の向上</dd>
|
|
|
1216 <dt>Third</dt>
|
|
|
1217 <dd>ソースコードメンテナンス性の向上</dd>
|
|
|
1218 </dl>
|
|
|
1219 </div>
|
|
|
1220
|
|
|
1221
|
|
|
1222
|
|
|
1223 <div class="slide">
|
|
|
1224 <h1>First: 軽量継続の実装</h1>
|
|
|
1225 <p class="subtitle">軽量継続を実装するには？</p>
|
|
|
1226 <ul>
|
|
|
1227 <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
|
|
|
1228 <li>GCCでは<em class="weak">あくまで関数</em>がベース</li>
|
|
|
1229 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
|
|
|
1230 <li>関数コール(call命令)ではもちろんダメ</li>
|
|
|
1231 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
|
|
|
1232 <li>スタックを拡張するのもダメ</li>
|
|
|
1233 </ul>
|
|
|
1234 <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
|
|
|
1235 </div>
|
|
|
1236
|
|
|
1237 <div class="slide">
|
|
|
1238 <h1>First: 軽量継続の実装</h1>
|
|
|
1239 <p class="subtitle">末尾呼出ってなに？</p>
|
|
|
1240 <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
|
|
|
1241 <ul>
|
|
|
1242 <li>リターンの直前の関数呼び出しのこと</li>
|
|
|
1243 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
|
|
|
1244 <li>元の関数に戻らないため少し高速に</li>
|
|
|
1245 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
|
|
|
1246 </ul>
|
|
|
1247 </div>
|
|
|
1248
|
|
|
1249 <div class="slide">
|
|
|
1250 <h1>First: 軽量継続の実装</h1>
|
|
|
1251 <p class="subtitle">末尾呼出ってなに？</p>
|
|
|
1252 <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
|
|
|
1253 <ul>
|
|
|
1254 <li>リターンの直前の関数呼び出しのこと</li>
|
|
|
1255 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
|
|
|
1256 <li>元の関数に戻らないため少し高速に</li>
|
|
|
1257 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
|
|
|
1258 </ul>
|
|
|
1259 <p class="subtitle incremental">軽量継続ではこの末尾呼出(TCE)を強制する！</p>
|
|
|
1260 </div>
|
|
|
1261
|
|
|
1262 <div class="slide">
|
|
|
1263 <h1>First: 軽量継続の実装</h1>
|
|
|
1264 <p class="subtitle">末尾呼出による軽量継続の実装</p>
|
|
|
1265 <ul>
|
|
|
1266 <li>全ての軽量継続は末尾呼出と解釈する</li>
|
|
|
1267 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
|
|
|
1268 <li><code>goto cs(20, 30);</code></li>
|
|
|
1269 <li><code>cs(20, 30); return;</code></li>
|
|
|
1270 </ul>
|
|
|
1271 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
|
|
|
1272 <ol>
|
|
|
1273 <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li>
|
|
|
1274 <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li>
|
|
|
1275 </ol>
|
|
|
1276 </div>
|
|
|
1277 <div class="slide">
|
|
|
1278 <h1>First: 軽量継続の実装</h1>
|
|
|
1279 <p class="subtitle">末尾呼出による軽量継続の実装</p>
|
|
|
1280 <ul>
|
|
|
1281 <li>全ての軽量継続は末尾呼出と解釈する</li>
|
|
|
1282 <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
|
|
|
1283 <li><code>goto cs(20, 30);</code></li>
|
|
|
1284 <li><code>cs(20, 30); return;</code></li>
|
|
|
1285 </ul>
|
|
|
1286 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
|
|
|
1287 <ol>
|
|
|
1288 <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
|
|
|
1289 <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
|
|
|
1290 </ol>
|
|
|
1291 </div>
|
|
|
1292
|
|
|
1293
|
|
|
1294 <div class="slide">
|
|
|
1295 <h1>First: 軽量継続の実装</h1>
|
|
|
1296 <p class="subtitle">引数順序の問題の解決</p>
|
|
|
1297 <ul>
|
|
|
1298 <li>問題となる例
|
|
|
1299 <pre><code>code somesegment(int a, int b, int c) {
|
|
|
1300 /∗ do something ∗/
|
|
|
1301 goto nextsegment(b, c, a);
|
|
|
1302 }
|
|
|
1303 </code></pre>
|
|
|
1304 </li>
|
|
|
1305 <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
|
|
|
1306 <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
|
|
|
1307 <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
|
|
|
1308 </ul>
|
|
|
1309
|
|
|
1310 </div>
|
|
|
1311
|
|
|
1312 <div class="slide">
|
|
|
1313 <h1>First: 軽量継続の実装</h1>
|
|
|
1314 <p class="subtitle">全ての引数を一時変数に退避</p>
|
|
|
1315 <ul>
|
|
|
1316 <li>次の様に構文木を変更する
|
|
|
1317 <pre><code>code somesegment(int a, int b, int c) {
|
|
|
1318 int a1, b1, c1;
|
|
|
1319 /∗ do something ∗/
|
|
|
1320 a1=a; b1=b; c1=c;
|
|
|
1321 goto nextsegment(b1, c1, a1);
|
|
|
1322 }
|
|
|
1323 </code></pre>
|
|
|
1324 </li>
|
|
|
1325 <li>これにより、引数順序を考える必要はなくなる</li>
|
|
|
1326 <li>代わりに、メモリアクセスが大量に発生</li>
|
|
|
1327 <li>しかし、これはGCCの最適化で除去される</li>
|
|
|
1328 </ul>
|
|
|
1329
|
|
|
1330 <p class="subtitle">これで軽量継続が実装された</p>
|
|
|
1331 </div>
|
|
|
1332
|
|
|
1333
|
|
|
1334 <div class="slide">
|
|
|
1335 <h1>First: x86における高速化</h1>
|
|
|
1336 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
|
|
|
1337 <ul>
|
|
|
1338 <li>特にx86アーキテクチャ</li>
|
|
|
1339 <li><em class="weak">あくまで関数がベース</em>なので</li>
|
|
|
1340 <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
|
|
|
1341 <li>これをレジスタにすれば高速化が可能</li>
|
|
|
1342 </ul>
|
|
|
1343 <p class="subtitle">fastcallの導入</p>
|
|
|
1344 <ul>
|
|
|
1345 <li>GCCの独自拡張機能</li>
|
|
|
1346 <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
|
|
|
1347 </ul>
|
|
|
1348 </div>
|
|
|
1349
|
|
|
1350 <div class="slide">
|
|
|
1351 <h1>First: x86における高速化</h1>
|
|
|
1352 <p class="subtitle">fastcallの強制</p>
|
|
|
1353 <ul>
|
|
|
1354 <li>通常は以下の様に定義される
|
|
|
1355 <pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
|
|
|
1356 </code></pre></li>
|
|
|
1357 <li>しかしこれを毎回ユーザが書くのは変</li>
|
|
|
1358 <li>やはりフロントエンドにて、強制するべき</li>
|
|
|
1359 <li>型の構文木を生成した際にfastcall属性を付加</li>
|
|
|
1360 </ul>
|
|
|
1361 <p class="subtitle">実際の出力はどうなる？</p>
|
|
|
1362 <div style="width:70%;margin:1em auto 0;">
|
|
|
1363 <pre><code>__code current(int a, int b, int c) {
|
|
|
1364 goto next(10, 20, 30);
|
|
|
1365 }
|
|
|
1366 </code></pre>
|
|
|
1367 </div>
|
|
|
1368 </div>
|
|
|
1369
|
|
|
1370 <div class="slide" style="font-size:95%;">
|
|
|
1371 <h1>First: x86における高速化</h1>
|
|
|
1372 <p class="subtitle">実際の出力アセンブラ</p>
|
|
|
1373 <div style="width:50%;float:left;margin-left:auto;">
|
|
|
1374 <p style="margin:0;text-align:center">fastcallにした場合</p>
|
|
|
1375 <pre><code>current:
|
|
|
1376 subl $12, %esp
|
|
|
1377 movl $30, 16(%esp)
|
|
|
1378 movl $20, %edx
|
|
|
1379 movl $10, %ecx
|
|
|
1380 addl $12, %esp
|
|
|
1381 jmp next
|
|
|
1382 </code></pre>
|
|
|
1383 </div>
|
|
|
1384 <div style="width:50%;float:right;margin-right:auto;">
|
|
|
1385 <p style="margin:0;text-align:center">normalcallの場合</p>
|
|
|
1386 <pre><code>current:
|
|
|
1387 pushl %ebp
|
|
|
1388 movl %esp, %ebp
|
|
|
1389 movl $30, 16(%ebp)
|
|
|
1390 movl $20, 12(%ebp)
|
|
|
1391 movl $10, 8(%ebp)
|
|
|
1392 leave
|
|
|
1393 jmp next
|
|
|
1394 </code></pre>
|
|
|
1395 </div>
|
|
|
1396 <br clear="all" />
|
|
|
1397 <ul>
|
|
|
1398 <li>命令数ではほとんど変化はない</li>
|
|
|
1399 <li>引数2つがレジスタecxとedxに格納されるようになった</li>
|
|
|
1400 <li>そのためメモリアクセスが減る</li>
|
|
|
1401 <li>これで高速化されるはず</li>
|
|
|
1402 </ul>
|
|
|
1403 </div>
|
|
|
1404
|
|
|
1405
|
|
|
1406 <div class="slide">
|
|
|
1407 <h1>First: CbCコンパイラ実装の評価</h1>
|
|
|
1408 <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
|
|
|
1409 <ul>
|
|
|
1410 <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
|
|
|
1411 <li>コンパイラの出力した実行ファイルを比較</li>
|
|
|
1412 <li>CbCでのquicksort例題を用意</li>
|
|
|
1413 <li>実行速度、ファイルサイズ</li>
|
|
|
1414 <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
|
|
|
1415 </ul>
|
|
|
1416 <p class="subtitle">実行環境</p>
|
|
|
1417 <ul>
|
|
|
1418 <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
|
|
|
1419 <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
|
|
|
1420 <li>OSはLinuxとOS Xを使用する</li>
|
|
|
1421 </ul>
|
|
|
1422 </div>
|
|
|
1423
|
|
|
1424 <div class="slide">
|
|
|
1425 <h1>First: 性能評価（速度比較） vs.旧ver</h1>
|
|
|
1426 <p class="subtitle">速度測定結果(単位:秒)</p>
|
|
|
1427 <table>
|
|
|
1428 <tr>
|
|
|
1429 <th></th>
|
|
|
1430 <th colspan="2">新CbCGCC</th>
|
|
|
1431 <th colspan="2">旧CbCGCC</th>
|
|
|
1432 </tr>
|
|
|
1433 <tr>
|
|
|
1434 <td></td>
|
|
|
1435 <th>最適化無し</th>
|
|
|
1436 <th>最適化有り</th>
|
|
|
1437 <th>最適化無し</th>
|
|
|
1438 <th>最適化有り</th>
|
|
|
1439 </tr>
|
|
|
1440 <tr>
|
|
|
1441 <td>x86/OS X</td>
|
|
|
1442 <td>5.907</td>
|
|
|
1443 <td>2.434</td>
|
|
|
1444 <td>4.668</td>
|
|
|
1445 <td>3.048</td>
|
|
|
1446 </tr>
|
|
|
1447 <tr>
|
|
|
1448 <td>x86/Linux</td>
|
|
|
1449 <td>5.715</td>
|
|
|
1450 <td>2.401</td>
|
|
|
1451 <td>4.525</td>
|
|
|
1452 <td>2.851</td>
|
|
|
1453 </tr>
|
|
|
1454 </table>
|
|
|
1455 <p class="subtitle">評価</p>
|
|
|
1456 <ul>
|
|
|
1457 <li>最適化無の場合は遅くなった </li>
|
|
|
1458 <li>一時変数への確保があるのでこれは予想通り</li>
|
|
|
1459 <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
|
|
|
1460 <li>fastcallの効果が十分に出ている</li>
|
|
|
1461 </ul>
|
|
|
1462 </div>
|
|
|
1463
|
|
|
1464
|
|
|
1465 <div class="slide">
|
|
|
1466 <h1>First: 性能評価（速度比較）</h1>
|
|
|
1467 <p class="subtitle">速度測定結果(単位:秒)</p>
|
|
|
1468 <table>
|
|
|
1469 <tr>
|
|
|
1470 <td></td>
|
|
|
1471 <td>最適化なしのGCC</td>
|
|
|
1472 <td>最適化付きのGCC</td>
|
|
|
1473 <td>micro-c</td>
|
|
|
1474 </tr>
|
|
|
1475 <tr>
|
|
|
1476 <td>x86/OS X</td>
|
|
|
1477 <td>5.901</td>
|
|
|
1478 <td>2.434</td>
|
|
|
1479 <td>2.857</td>
|
|
|
1480 </tr>
|
|
|
1481 <tr>
|
|
|
1482 <td>x86/Linux</td>
|
|
|
1483 <td>5.732</td>
|
|
|
1484 <td>2.401</td>
|
|
|
1485 <td>2.254</td>
|
|
|
1486 </tr>
|
|
|
1487 <tr>
|
|
|
1488 <td>ppc/OS X</td>
|
|
|
1489 <td>14.875</td>
|
|
|
1490 <td>2.146</td>
|
|
|
1491 <td>4.811</td>
|
|
|
1492 </tr>
|
|
|
1493 <tr>
|
|
|
1494 <td>ppc/Linux</td>
|
|
|
1495 <td>19.793</td>
|
|
|
1496 <td>3.955</td>
|
|
|
1497 <td>6.454</td>
|
|
|
1498 </tr>
|
|
|
1499 <tr>
|
|
|
1500 <td>ppc/PS3</td>
|
|
|
1501 <td>39.176</td>
|
|
|
1502 <td>5.874</td>
|
|
|
1503 <td>11.121</td>
|
|
|
1504 </tr>
|
|
|
1505 </table>
|
|
|
1506 <p class="subtitle">結果(micro-cとの比較)</p>
|
|
|
1507 <ul>
|
|
|
1508 <li>x86では速度にあまり差が出なかった</li>
|
|
|
1509 <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
|
|
|
1510 <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
|
|
|
1511 </ul>
|
|
|
1512 </div>
|
|
|
1513
|
|
|
1514 <div class="slide">
|
|
|
1515 <h1>First: 性能評価（速度比較）</h1>
|
|
|
1516 <p class="subtitle">結果(micro-cとの比較)</p>
|
|
|
1517 <ul>
|
|
|
1518 <li>x86では速度にあまり差が出なかった</li>
|
|
|
1519 <li>PowerPCではCbCGCCが2倍ほど早い</li>
|
|
|
1520 </ul>
|
|
|
1521 <p class="subtitle">この違いはどこから？</p>
|
|
|
1522 <ul style="font-size:95%;">
|
|
|
1523 <li>実際にアセンブラを出力して比較、その結果</li>
|
|
|
1524 <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
|
|
|
1525 <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
|
|
|
1526 <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
|
|
|
1527 <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
|
|
|
1528 </ul>
|
|
|
1529 </div>
|
|
|
1530
|
|
|
1531 <div class="slide">
|
|
|
1532 <h1>First: 性能評価（サイズ比較）</h1>
|
|
|
1533 <p class="subtitle">ファイルサイズの比較</p>
|
|
|
1534 <ul>
|
|
|
1535 <li>組み込み系ではメモリ使用量が肝心</li>
|
|
|
1536 <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
|
|
|
1537 <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
|
|
|
1538 </ul>
|
|
|
1539 <p class="subtitle">結果</p>
|
|
|
1540 <table>
|
|
|
1541 <tr>
|
|
|
1542 <td></td>
|
|
|
1543 <th>CbCGCC<br/>速度最適化</th>
|
|
|
1544 <th>CbCGCC<br/>サイズ最適化</th>
|
|
|
1545 <th>micro-c</th>
|
|
|
1546 </tr>
|
|
|
1547 <tr>
|
|
|
1548 <td>x86/OS X</td>
|
|
|
1549 <td>9176</td>
|
|
|
1550 <td>9176</td>
|
|
|
1551 <td>9172</td>
|
|
|
1552 </tr>
|
|
|
1553 <tr>
|
|
|
1554 <td>x86/Linux</td>
|
|
|
1555 <td>5752</td>
|
|
|
1556 <td>5752</td>
|
|
|
1557 <td>5796</td>
|
|
|
1558 </tr>
|
|
|
1559 <tr>
|
|
|
1560 <td>ppc/OS X</td>
|
|
|
1561 <td>8576</td>
|
|
|
1562 <td>8576</td>
|
|
|
1563 <td>12664</td>
|
|
|
1564 </tr>
|
|
|
1565 <tr>
|
|
|
1566 <td>ppc/Linux</td>
|
|
|
1567 <td>10068</td>
|
|
|
1568 <td>10068</td>
|
|
|
1569 <td>9876</td>
|
|
|
1570 </tr>
|
|
|
1571 <tr>
|
|
|
1572 <td>ppc/PS3</td>
|
|
|
1573 <td>6960</td>
|
|
|
1574 <td>6728</td>
|
|
|
1575 <td>8636</td>
|
|
|
1576 </tr>
|
|
|
1577 </table>
|
|
|
1578 <p class="subtitle">結果考察</p>
|
|
|
1579 <ul>
|
|
|
1580 <li>x86ではファイルサイズの差がない</li>
|
|
|
1581 <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
|
|
|
1582 <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
|
|
|
1583 </ul>
|
|
|
1584 </div>
|
|
|
1585
|
|
|
1586
|
|
|
1587 <div class="slide">
|
|
|
1588 <h1>Second: Cとの相互利用</h1>
|
|
|
1589 <p class="subtitle">なぜそれが必要か</p>
|
|
|
1590 <ul>
|
|
|
1591 <li>C <=> CbC の変換が可能なので互換性はある</li>
|
|
|
1592 <li>しかし、ソースコード上での互換性もある事が望ましい</li>
|
|
|
1593 <li>CbCからCの関数を呼び出すのは問題ない</li>
|
|
|
1594 <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
|
|
|
1595 </ul>
|
|
|
1596 <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
|
|
|
1597 <ul>
|
|
|
1598 <li>軽量継続に、スタックの情報を加える</li>
|
|
|
1599 <li>つまり通常の「継続」と同じ</li>
|
|
|
1600 <li>関数からのみ使用可能</li>
|
|
|
1601 </ul>
|
|
|
1602 </div>
|
|
|
1603
|
|
|
1604 <div class="slide" style="font-size:95%;">
|
|
|
1605 <h1>Second: Cとの相互利用</h1>
|
|
|
1606 <pre style="float:right; width-max:45%">
|
|
|
1607 <code>typedef code (*NEXT)(int);
|
|
|
1608 int main(int argc, char **argv) {
|
|
|
1609 int i,a;
|
|
|
1610 i = atoi(argv[1]);
|
|
|
1611 <em>a = factor(i);</em>
|
|
|
1612 printf("%d! = %d\n", a);
|
|
|
1613 }
|
|
|
1614 int factor(int x) {
|
|
|
1615 NEXT ret = <em>__return</em>;
|
|
|
1616 goto factor0(1, x, ret);
|
|
|
1617 }
|
|
|
1618 code
|
|
|
1619 factor0(int prod,int x,NEXT next) {
|
|
|
1620 if (x >= 1) {
|
|
|
1621 goto factor0(prod*x, x-1, next);
|
|
|
1622 } else {
|
|
|
1623 <em>goto (*next)(prod);</em>
|
|
|
1624 }
|
|
|
1625 }
|
|
|
1626 </code></pre>
|
|
|
1627 <p class="subtitle">環境付き継続の使用例</p>
|
|
|
1628 <ul>
|
|
|
1629 <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li>
|
|
|
1630 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
|
|
|
1631 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
|
|
|
1632 </ul>
|
|
|
1633 </div>
|
|
|
1634
|
|
|
1635 <div class="slide">
|
|
|
1636 <h1>Second: Cとの相互利用</h1>
|
|
|
1637 <p class="subtitle">どのように実装する？</p>
|
|
|
1638 <ol>
|
|
|
1639 <li>setjmp()/longjmp()を使って実装可能
|
|
|
1640 <ul>
|
|
|
1641 <li>Cの標準ライブラリの関数</li>
|
|
|
1642 <li>しかし余計な環境も保持するためオーバヘッドが大きい</li>
|
|
|
1643 <li>継続の際に渡す引数が一つ増えてしまう</li>
|
|
|
1644 </ul></li>
|
|
|
1645 <li>内部関数
|
|
|
1646 <ul>
|
|
|
1647 <li>GCCの独自拡張</li>
|
|
|
1648 <li>関数内に関数を定義可能</li>
|
|
|
1649 <li><em>内部関数から外の関数のラベルにgotoできる</em></li>
|
|
|
1650 </ul></li>
|
|
|
1651 </ol>
|
|
|
1652 <p class="subtitle">内部関数が使いやすい</p>
|
|
|
1653 </div>
|
|
|
1654
|
|
|
1655 <div class="slide" style="font-size:95%;">
|
|
|
1656 <h1>Second: Cとの相互利用</h1>
|
|
|
1657 <p class="subtitle">具体的には</p>
|
|
|
1658 <ul>
|
|
|
1659 <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
|
|
|
1660 <li>内部関数の中からは外の関数にgotoして脱出</li>
|
|
|
1661 </ul>
|
|
|
1662 <pre><code>int factor(int x) {
|
|
|
1663 int retval;
|
|
|
1664
|
|
|
1665 <em class="weak">code __return(int val) {
|
|
|
1666 retval = val;
|
|
|
1667 goto label;
|
|
|
1668 }
|
|
|
1669 if (0) {
|
|
|
1670 label:
|
|
|
1671 return retval;
|
|
|
1672 }</em>
|
|
|
1673
|
|
|
1674 NEXT ret = <em>__return</em>;
|
|
|
1675 goto factor0(1, x, ret);
|
|
|
1676 } </code></pre>
|
|
|
1677 </div>
|
|
|
1678
|
|
|
1679 <div class="slide" style="font-size:95%;">
|
|
|
1680 <h1>Second: Cとの相互利用・評価</h1>
|
|
|
1681 <p class="subtitle">この取り組みにより</p>
|
|
|
1682 <ul>
|
|
|
1683 <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li>
|
|
|
1684 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
|
|
|
1685 </ul>
|
|
|
1686 </div>
|
|
|
1687
|
|
|
1688 <div class="slide">
|
|
|
1689 <h1>Third: メンテナンス性の向上</h1>
|
|
|
1690 <p class="subtitle">GCCのアップデートリリースは早い</p>
|
|
|
1691 <ul>
|
|
|
1692 <li>リリースだけで年に5回のペース</li>
|
|
|
1693 <li>その度にバグの修正やコードの改善が入る</li>
|
|
|
1694 <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li>
|
|
|
1695 </ul>
|
|
|
1696 <p class="subtitle">このリリースに追従して差分をアップデートしたい</p>
|
|
|
1697 <ul>
|
|
|
1698 <li>GCC本家にマージしてもらうのが一番良いが難しい</li>
|
|
|
1699 <li></li>
|
|
|
1700 </ul>
|
|
|
1701 </div>
|
|
|
1702
|
|
|
1703 <div class="slide">
|
|
|
1704 <h1>Third: メンテナンス性の向上</h1>
|
|
|
1705 <img style="width:60%;float:right;" src="figures/gcc-repository.png" />
|
|
|
1706 <p class="subtitle">二つのリポジトリ管理</p>
|
|
|
1707 <ul>
|
|
|
1708 <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li>
|
|
|
1709 <li>CbCの修正が加えられたリポジトリ CbCGCC</li>
|
|
|
1710 <li>Mercurialによる分散リポジトリ管理</li>
|
|
|
1711 <li>CbCGCC は GCC_copyをクローン（ブランチ）して作成する</li>
|
|
|
1712 </ul>
|
|
|
1713 <p class="subtitle"></p>
|
|
|
1714 </div>
|
|
|
1715
|
|
|
1716
|
|
|
1717 <div class="slide">
|
|
|
1718 <h1>Third: メンテナンス性の向上</h1>
|
|
|
1719 <p class="subtitle">アップデート手順</p>
|
|
|
1720 <ul>
|
|
|
1721 <li>GCC-copyリポジトリにて
|
|
|
1722 <ol>
|
|
|
1723 <li>GCC-copyリポジトリのファイルをすべて消す</li>
|
|
|
1724 <li>GCCの最新バージョンをリポジトリ内に展開</li>
|
|
|
1725 <li>追加ファイル、削除ファイルを確認</li>
|
|
|
1726 <li>コミット、タグ付け</li>
|
|
|
1727 </ol> </li>
|
|
|
1728 <li>CbCGCCリポジトリにて
|
|
|
1729 <ol>
|
|
|
1730 <li>GCC-copyからpull.</li>
|
|
|
1731 <li>hg mergeでマージ実行</li>
|
|
|
1732 <li>衝突があればソースコードをを修正</li>
|
|
|
1733 <li>ビルドテスト</li>
|
|
|
1734 <li>コミット、タグ付け</li>
|
|
|
1735 </ol></li>
|
|
|
1736 </ul>
|
|
|
1737 </div>
|
|
|
1738
|
|
|
1739 <div class="slide">
|
|
|
1740 <h1>Third: メンテナンス性の向上・比較</h1>
|
|
|
1741 <p class="subtitle">これまでのアップデートは</p>
|
|
|
1742 <ul>
|
|
|
1743 <li>GCCの新旧の差分、CbCの差分</li>
|
|
|
1744 <li>複雑なdiffをとる必要がある</li>
|
|
|
1745 </ul>
|
|
|
1746 <p class="subtitle">新しい管理方法により</p>
|
|
|
1747 <ul>
|
|
|
1748 <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li>
|
|
|
1749 <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li>
|
|
|
1750 <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li>
|
|
|
1751 </ul>
|
|
|
1752 </div>
|
|
|
1753
|
|
|
1754 <div class="slide">
|
|
|
1755 <h1>まとめ</h1>
|
|
|
1756 <p class="subtitle">本研究での取り組み</p>
|
|
|
1757 <dl>
|
|
|
1758 <dt>First</dt>
|
|
|
1759 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
|
|
|
1760 <ul>
|
|
|
1761 <li>軽量継続における引数順序の制限を取り除いた</li>
|
|
|
1762 <li>PowerPCでの間接継続の制限を取り除いた</li>
|
|
|
1763 <li>x86アーキテクチャにて高速化を行った</li>
|
|
|
1764 </ul>
|
|
|
1765 </dd>
|
|
|
1766 <dt>Second</dt>
|
|
|
1767 <dd>Cとの相互利用性の向上</dd>
|
|
|
1768 <dt>Third</dt>
|
|
|
1769 <dd>ソースコードメンテナンス性の向上</dd>
|
|
|
1770 </dl>
|
|
|
1771 </div>
|
|
|
1772
|
|
|
1773 <div class="slide" style="font-size:95%;">
|
|
|
1774 <h1>まとめ</h1>
|
|
|
1775 <p class="subtitle">本研究での成果</p>
|
|
|
1776 <dl>
|
|
|
1777 <dt>成果1</dt>
|
|
|
1778 <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
|
|
|
1779 <dt>成果2</dt>
|
|
|
1780 <dd>CbCが多数のアーキテクチャに対応
|
|
|
1781 <ul>
|
|
|
1782 <li>20以上のアーキテクチャ</li>
|
|
|
1783 <li>特に64bitのx86, SPUがうれしい</li>
|
|
|
1784 </ul> </dd>
|
|
|
1785 <dt>成果3</dt>
|
|
|
1786 <dd>CbCの高速化
|
|
|
1787 <ul>
|
|
|
1788 <li>x86においてもmicro-cと互角の速度を達成</li>
|
|
|
1789 <li>PowerPCでは2倍の速度</li>
|
|
|
1790 </ul></dd>
|
|
|
1791 <dt>成果4</dt>
|
|
|
1792 <dd>メンテナンス性が向上</dd>
|
|
|
1793 </dl>
|
|
|
1794 </div>
|
|
|
1795
|
|
|
1796 <div class="slide">
|
|
|
1797 <h1>今後の課題</h1>
|
|
|
1798 <p class="subtitle"></p>
|
|
|
1799 <ul>
|
|
|
1800 <li>Real-time、組込み向けに実用的なCbCプログラムの例題</li>
|
|
|
1801 <li>タブロー方を用いた検証</li>
|
|
|
1802 <li>TaskManagerのCbC実装</li>
|
|
|
1803 </ul>
|
|
|
1804 <p class="subtitle">CbC言語の今後</p>
|
|
|
1805 <ul>
|
|
|
1806 <li>オブジェクティブなCbCの設計</li>
|
|
|
1807 <li>データセグメントの導入</li>
|
|
|
1808 <li>スケジューラのためのリフレクション</li>
|
|
|
1809 </ul>
|
|
|
1810 </div>
|
|
|
1811
|
|
|
1812
|
|
|
1813 <div class="slide">
|
|
|
1814 <h1>おわり</h1>
|
|
|
1815 <p class="subtitle">ありがとうございました</p>
|
|
|
1816 </div>
|
|
|
1817
|
|
|
1818
|
|
|
1819
|
|
|
1820
|
|
|
1821
|
|
|
1822
|
|
|
1823
|
|
|
1824
|
|
15
|
1825
|
|
|
1826
|
|
|
1827
|
|
|
1828
|
|
|
1829
|
|
|
1830
|
|
|
1831
|
|
|
1832
|
|
|
1833
|
|
|
1834
|
|
|
1835
|
|
|
1836
|
|
|
1837 <div class="slide">
|
|
|
1838 <h1>Continuation based C</h1>
|
|
|
1839 <ul>
|
|
|
1840 <li>言語仕様</li>
|
|
|
1841 <li>return-callから軽量継続へ</li>
|
|
|
1842 <li>コードセグメント</li>
|
|
|
1843 <li>状態遷移に適した言語</li>
|
|
|
1844 <li>Cとの互換性</li>
|
|
|
1845 </ul>
|
|
|
1846 </div>
|
|
|
1847
|
|
|
1848
|
|
|
1849 <div class="slide">
|
|
|
1850 <h1></h1>
|
|
|
1851 <p class="subtitle"></p>
|
|
|
1852 <ul>
|
|
|
1853 <li></li>
|
|
|
1854 <li></li>
|
|
|
1855 </ul>
|
|
|
1856 </div>
|
|
|
1857 <div class="slide">
|
|
|
1858 <h1></h1>
|
|
|
1859 <p class="subtitle"></p>
|
|
|
1860 <ul>
|
|
|
1861 <li></li>
|
|
|
1862 <li></li>
|
|
|
1863 </ul>
|
|
|
1864 </div>
|
|
|
1865
|
|
|
1866 <div class="slide">
|
|
|
1867 <h1></h1>
|
|
|
1868 <p class="subtitle"></p>
|
|
|
1869 <ul>
|
|
|
1870 <li></li>
|
|
|
1871 <li></li>
|
|
|
1872 </ul>
|
|
|
1873 </div>
|
|
|
1874
|
|
|
1875
|
|
|
1876 <div class="slide">
|
|
|
1877 <h1>First: PowerPCでの間接継続</h1>
|
|
|
1878 <p class="subtitle"></p>
|
|
|
1879 <ul>
|
|
|
1880 <li></li>
|
|
|
1881 </ul>
|
|
|
1882 <p class="subtitle"></p>
|
|
|
1883 <div style="width:70%;margin:1em auto 0;">
|
|
|
1884 <pre><code>
|
|
|
1885 </code></pre>
|
|
|
1886 </div>
|
|
|
1887 </div>
|
|
|
1888
|
|
|
1889 <div class="slide">
|
|
|
1890 <h1>継続制御での並列代入</h1>
|
|
|
1891 <p class="subtitle" style="margin:0 1em 0.1em;">
|
|
|
1892 本当に最適化で余分なコードが消えるのか？
|
|
|
1893 </p>
|
|
|
1894 <div style="width:45%;float:left;margin-left:1em;">
|
|
|
1895 最適化しない場合
|
|
|
1896 <pre style="margin-top:0"><code> _test:
|
|
|
1897 stwu r1,-64(r1)
|
|
|
1898 mr r30,r1
|
|
|
1899 stw r3,88(r30)
|
|
|
1900 stw r4,92(r30)
|
|
|
1901 stw r5,96(r30)
|
|
|
1902 lwz r0,92(r30)
|
|
|
1903 stw r0,32(r30)
|
|
|
1904 lwz r0,96(r30)
|
|
|
1905 addic r0,r0,1
|
|
|
1906 stw r0,28(r30)
|
|
|
1907 lwz r0,88(r30)
|
|
|
1908 stw r0,24(r30)
|
|
|
1909 lwz r3,32(r30)
|
|
|
1910 lwz r4,28(r30)
|
|
|
1911 lwz r5,24(r30)
|
|
|
1912 addi r1,r30,64
|
|
|
1913 lwz r30,-8(r1)
|
|
|
1914 lwz r31,-4(r1)
|
|
|
1915 b L_next$stub
|
|
|
1916 </code></pre>
|
|
|
1917 </div>
|
|
|
1918 <div style="width:45%;float:right;margin-right:1em;">
|
|
|
1919 最適化した場合
|
|
|
1920 <pre><code>
|
|
|
1921 _test:
|
|
|
1922 mr r0,r3
|
|
|
1923 mr r3,r4
|
|
|
1924 mr r4,r5
|
|
|
1925 mr r5,r0
|
|
|
1926 b L_next$stub
|
|
|
1927 </code></pre>
|
|
|
1928 </div>
|
|
|
1929 <div style="width:50%;float:right">
|
|
|
1930 <ul>
|
|
|
1931 <li>r3:=a, r4:=b, r5:=c</li>
|
|
|
1932 <li>最適化しないとload, storeが満載</li>
|
|
|
1933 <li>最適化すると無駄なload, store命令が消えている</li>
|
|
|
1934 <li>実際はr0を使って4命令で入れ替えられる!</li>
|
|
|
1935 </ul>
|
|
|
1936 </div>
|
|
|
1937 </div>
|
|
|
1938
|
|
|
1939 <div class="slide">
|
|
|
1940 <h1>Cとの比較について</h1>
|
|
16
|
1941 <p class="subtitle">CbCとCの比較に関して</p>
|
|
15
|
1942 <ul>
|
|
16
|
1943 <li>まだ例題を用意していない</li>
|
|
|
1944 <li>quicksortはスタックが必要となるため、Cに有利</li>
|
|
|
1945 <li>この例題ではプログラム上自前でスタックを用意している</li>
|
|
|
1946 <li>このメモリへのアクセスはスタックより重い</li>
|
|
|
1947 <li>Cとの比較には状態遷移ベースの例題があった方が良い</li>
|
|
15
|
1948 </ul>
|
|
|
1949 </div>
|
|
|
1950
|
|
|
1951
|
|
16
|
1952
|
|
|
1953
|
|
|
1954
|
|
15
|
1955
|
|
16
|
1956
|
|
15
|
1957
|
|
16
|
1958
|
|
|
1959
|
|
15
|
1960
|
|
|
1961
|
|
|
1962
|
|
|
1963 </body>
|
|
|
1964 </html>
|
|
|
1965
|
