Mercurial > hg > Papers > 2011 > nobu-prosym

comparison presen/index.html @ 75:454ddda8d306

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify explanation of CbC
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 03 Jan 2012 21:13:11 +0900
parents 275073032132
children a4d16779fd1e
comparison
equal deleted inserted replaced
74:275073032132 75:454ddda8d306
118 <li>CbC の紹介</li> 118 <li>CbC の紹介</li>
119 <li>GCC でのコンパイルの流れ</li> 119 <li>GCC でのコンパイルの流れ</li>
120 <font color="red"> 120 <font color="red">
121 <li>CbC の実装</li> 121 <li>CbC の実装</li>
122 </font> 122 </font>
123 <!--
124 <ul>
125 <li>Tail Call Elimination</li>
126 <li>goto シンタックスの追加</li>
127 <li>環境付き継続</li>
128 </ul>
129 -->
130 <li>Micro-C との性能比較</li> 123 <li>Micro-C との性能比較</li>
131 <!--
132 <li>mercurial を用いたアップデートの方法</li>
133 -->
134 <li>まとめ</li> 124 <li>まとめ</li>
135 <ol> 125 <ol>
136 </div> 126 </div>
137 <!-- PAGE --> 127 <!-- PAGE -->
138 <div class="slide"> 128 <div class="slide">
151 </ul> 141 </ul>
152 </div> 142 </div>
153 <!-- PAGE --> 143 <!-- PAGE -->
154 <div class="slide"> 144 <div class="slide">
155 <h1>Continuation based C </h1> 145 <h1>Continuation based C </h1>
156 <ul> 146 <h2>継続:現在の処理を実行していく為の情報</h2>
157 <li>継続(C言語):現在の処理を実行していく為の情報</li> 147
158 <ul> 148 <table width=100% border=1>
159 <li>続く命令のアドレス</li> 149 <tr>
160 <li>命令に必要なデータ</li> 150 <td><small>Cの継続</small></td>
161 <li>スタックに積まれている値(環境)</li> 151 <td><small>CbCの継続(軽量継続)</small></td>
162 </ul> 152 </tr>
163 </ul> 153 <tr style="font-size:30px">
164 <li class="incremental">CbC: 関数コールが無い -> 呼び出し元への復帰がない</li> 154 <td>
165 <ul class="incremental"> 155 <ul>
166 <li>CbCの継続:軽量継続(light-weight continuation)</li> 156 <li>続く命令のアドレス</li>
167 <ul> 157 <li>命令に必要なデータ</li>
168 <li>Cの継続から環境を除外</li> 158 <li>スタックに積まれている値(環境)</li>
169 <li>続く命令とその命令に必要なデータのみ</li> 159 </ul>
170 </ul> 160 </td>
171 </ul> 161 <td>
172 </div> 162 <ul>
173 <!-- PAGE --> 163 <li>Cの継続から環境を除外</li>
174 <div class="slide"> 164 <li>続く命令とその命令に必要なデータのみ</li>
175 <h1>Continuation Based C (軽量継続)</h1> 165 </ul>
176 <p style=" margin-right:auto; margin-left:auto;"> 166 </td>
177 <table width=90% class="center" border=1> 167 </tr>
178 <tr> 168 <tr>
179 <td><small>Cの関数呼び出し</small></td> 169 <td style="margin-left:auto; margin-right: auto; text-align: center;">
180 <td><small>CbCの継続</></small></td>
181 </tr>
182 <tr>
183 <td>
184 <img class="scale" src="./pix/func_call.png" style="height: 6em;"> 170 <img class="scale" src="./pix/func_call.png" style="height: 6em;">
185 </td> 171 </td>
186 <td> 172 <td style="margin-left:auto; margin-right: auto; text-align: center;">
187 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;"> 173 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
188 </td> 174 </td>
189 </tr> 175 </tr>
190 </table> 176 </table>
191 </p>
192 <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li> 177 <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
193 <li>スタックに載るデータは1つのコードセグメントの必要なデータのみ。</li>
194 </div> 178 </div>
195 <!-- PAGE --> 179 <!-- PAGE -->
196 <div class="slide"> 180 <div class="slide">
197 <h1>Continuation based C </h1> 181 <h1>Continuation based C </h1>
198 <table width=100% border=1> 182 <table width=100% border=1>
239 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li> 223 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
240 </div> 224 </div>
241 <!-- PAGE --> 225 <!-- PAGE -->
242 <div class="slide"> 226 <div class="slide">
243 <h1>GCC</h1> 227 <h1>GCC</h1>
244 <li>本来はGnu Compiler Collectionのことを指すが、
245 <br>ここで扱うのはGnu C Compiler(cc1)になる。</li>
246 <ul> 228 <ul>
247 <li class="incremental">GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li> 229 <li>本来はGnu Compiler Collectionのことを指すが、ここで扱うのはGnu C Compiler(cc1)になる。</li>
230 <li>GCCではアセンブラ言語を出力するまでに読み込まれたソースコードは次の4つの中間言語へと変換される。</li>
231 <ul>
232 <li>Generic Tree</li>
233 <li>GIMPLE</li>
234 <li>Tree SSA</li>
235 <li>RTL</li>
248 </ul> 236 </ul>
249 </div>
250 <!-- PAGE -->
251 <div class="slide">
252 <h1>GCC</h1>
253 <ol>
254 <li>Generic Tree:ソースコードを構文木の形に直したもの</li>
255 <li>GIMPLE: Generic Treeの命令を簡単にした構文木</li>
256 <li>Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木</li>
257 <li>RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。</li>
258 </ol>
259 <li class="incremental">それぞれは次のようなデータを構文木にして持っている。</li>
260 </div>
261 <!-- PAGE -->
262 <div class="slide">
263 <h1>GCC</h1>
264 <table width=100% border=1>
265 <tr>
266 <td>Generic(ソースコード)</td>
267 <td>GIMPLE</td>
268 </tr>
269 <tr class="srctr">
270 <td>
271 <pre class="srcbox">
272 void factorial(int x)
273 {
274 int prod,i;
275 for(i=1,prod=1; i <= x; i++){
276 prod = prod*i;
277 }
278 print_factorial(prod);
279 }
280 </pre>
281 </td>
282 <td width=50%>
283 <pre class="srcbox">
284 factorial (int x)
285 {
286 int prod;
287 int i;
288
289 i = 1;
290 prod = 1;
291 goto &lt;D.2846&gt;;
292 &lt;D.2845&gt;:
293 prod = prod * i;
294 i = i + 1;
295 &lt;D.2846&gt;:
296 if (i &lt;= x) goto &lt;D.2845&gt;; else goto &lt;D.2847&gt;;
297 &lt;D.2847&gt;:
298 print_factorial (prod);
299 }
300 </pre>
301 </td>
302 </tr>
303 </table>
304 </div>
305 <!-- PAGE -->
306 <div class="slide">
307 <h1>GCC</h1>
308 <table border=1 width=100% height=100%>
309 <tr>
310 <td width=50%>SSA</td>
311 <td width=50%>RTL(一部)</td>
312 </tr>
313 <tr class="srctr">
314 <td class="srctd">
315 <pre class="srcbox">
316 factorial (int x)
317 {
318 int i;
319 int prod;
320
321 &lt;bb 2&gt;:
322 i_3 = 1;
323 prod_4 = 1;
324 goto &lt;bb 4&gt;;
325
326 &lt;bb 3&gt;:
327 prod_6 = prod_1 * i_2;
328 i_7 = i_2 + 1;
329
330 &lt;bb 4&gt;:
331 # prod_1 = PHI &lt;prod_4(2), prod_6(3)&gt;
332 # i_2 = PHI &lt;i_3(2), i_7(3)&gt;
333 if (i_2 &lt;= x_5(D))
334 goto &lt;bb 3&gt;;
335 else
336 goto &lt;bb 5&gt;;
337
338 &lt;bb 5&gt;:
339 print_factorial (prod_1);
340 return;
341 }
342
343 </pre>
344 </td>
345 <td class="srctd">
346 <pre class="srcbox" style="width:25em;">
347 (jump_insn 20 19 21 5 (set (pc)
348 (if_then_else (le (reg:CCGC 17 flags)
349 (const_int 0 [0]))
350 (label_ref 17)
351 (pc))) factorial.c:12 -1
352 (nil)
353 -> 17)
354
355 (note 21 20 22 6 [bb 6] NOTE_INSN_BASIC_BLOCK)
356
357 (insn 22 21 23 6 (set (reg:SI 62)
358 (mem/c/i:SI (plus:DI (reg/f:DI 54 virtual-stack-vars)
359 (const_int -4 [0xfffffffffffffffc])) [0 prod+0 S4 A32])) factorial.c:15 -1
360 (nil))
361
362 (insn 23 22 24 6 (set (reg:SI 5 di)
363 (reg:SI 62)) factorial.c:15 -1
364 (nil))
365
366 (call_insn 24 23 25 6 (call (mem:QI (symbol_ref:DI ("print_factorial") [flags 0x403] <function_decl 0x146f6b200 print_factorial>) [0 S1 A8])
367 (const_int 0 [0])) factorial.c:15 -1
368 (nil)
369 (expr_list:REG_DEP_TRUE (use (reg:SI 5 di))
370 (nil)))
371
372 (code_label 25 24 26 7 2 "" [0 uses])
373
374 (note 26 25 0 7 [bb 7] NOTE_INSN_BASIC_BLOCK)
375 </pre>
376 </td>
377 </tr>
378 </table>
379 </div>
380 <!-- PAGE -->
381 <div class="slide">
382 <h1>GCC</h1>
383 <p class="center">
384 <img src="./pix/ir.png" style="height: 6em;">
385 </p>
386 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li> 237 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
387 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li> 238 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
239 </ul>
388 </div> 240 </div>
389 <!-- PAGE --> 241 <!-- PAGE -->
390 <div class="slide"> 242 <div class="slide">
391 <h1>GCC:Generic Tree</h1> 243 <h1>GCC:Generic Tree</h1>
392 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li> 244 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>