Mercurial > hg > Papers > 2012 > nobu-thesis
annotate presen/cbc.md @ 42:1d66e06ae2c2 draft
modify
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 28 Feb 2012 22:47:04 +0900 |
| parents | ad0ab1378ae6 |
| children | 8539cd84106e |
| rev | line source |
|---|---|
| 28 | 1 Continuation based C の <br> GCC 4.6による実装 |
| 26 | 2 ========= |
| 3 | |
| 4 --- | |
| 5 | |
| 37 | 6 研究目的 |
| 26 | 7 --------- |
| 8 | |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
9 .notes: |
| 26 | 10 |
| 37 | 11 <li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li> |
| 38 | 12 - 本研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。 |
| 13 - CbC のコンパイラは Micro-C 版 と GCC 版(以下 CbC-GCC) が開発されている。 | |
| 14 - しかし, CbC-GCC はいくつかのバグがあり機能に修正の余地があった。 | |
| 15 - また、GCC の最新の機能を利用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。 | |
|
34
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
16 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
17 <h2>本研究では CbC-GCC のアップデートを行い、より良いコードを生成する CbC の処理系を開発した。</h2> |
| 26 | 18 |
| 19 --- | |
| 20 | |
| 21 Continuation based C | |
| 22 ======== | |
| 23 コードセグメント単位での記述と継続を基本としたプログラミング言語 | |
| 24 --------- | |
| 25 | |
| 26 <li>コーセグメント:CbC におけるプログラムの基本単位</li> | |
| 27 <ul> | |
| 28 <li>C の関数よりも細かな単位</li> | |
| 35 | 29 <li>構文は C と同じだが、C から関数コールとループ制御が取り除かれた形</li> |
| 26 | 30 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li> |
| 31 </ul> | |
| 32 | |
| 37 | 33 <table width=100% border=1> |
| 34 <tr> | |
| 35 <td style="margin-left:auto; margin-right: auto; text-align: center; width:50%" > | |
| 36 <img src="./pix/codesegment.png" style="width:100%"> | |
| 26 | 37 </td> |
| 37 | 38 <td> |
| 39 <pre style="margin-left:5%"> | |
| 40 __code cs_a(int num) { | |
| 41 : | |
| 42 : | |
| 43 goto cs_b(); | |
| 44 } | |
| 45 </pre> | |
| 46 </td> | |
| 47 </tr> | |
| 26 | 48 </table> |
| 49 | |
| 50 | |
| 51 --- | |
| 52 | |
| 53 Continuation based C | |
| 54 ======== | |
| 55 | |
| 56 継続:現在の処理を実行していく為の情報 | |
| 57 --------- | |
| 58 <table width=100% border=1> | |
| 59 <tr> | |
| 60 <td><h2>Cの継続</h2></td> | |
| 61 <td><h2>CbCの継続(軽量継続)</h2></td> | |
| 62 </tr> | |
| 63 <tr> | |
| 64 <td> | |
| 65 <ul> | |
| 66 <li>続く命令のアドレス</li> | |
| 67 <li>命令に必要なデータ</li> | |
| 68 <li>スタックに積まれている値(環境)</li> | |
| 69 </ul> | |
| 70 </td> | |
| 71 <td> | |
| 72 <ul> | |
| 73 <li>Cの継続から環境を除外</li> | |
| 74 <li>続く命令とその命令に必要なデータのみ</li> | |
| 75 </ul> | |
| 76 </td> | |
| 77 </tr> | |
| 78 <t> | |
| 79 <td style="margin-left:auto; margin-right: auto; text-align: center;"> | |
| 80 <img class="scale" src="./pix/func_call.png" style="height: 18em;"> | |
| 81 </td> | |
| 82 <td style="margin-left:auto; margin-right: auto; text-align: center;"> | |
| 83 <img class="scale" src="./pix/cs_stack.png" style="height: 18em;"> | |
| 84 </td> | |
| 85 </tr> | |
| 86 </table> | |
| 87 | |
| 88 | |
| 89 | |
| 90 --- | |
| 91 | |
| 92 Continuation based C | |
| 93 ======== | |
| 94 <table width=100% border=1> | |
| 95 <caption>階乗を求める CbC のプログラム</caption> | |
| 37 | 96 <td width=50%> |
| 97 <pre style="margin-left:5%"> | |
| 98 \_\_code print_factorial(int prod) | |
| 99 { | |
| 100 printf("factorial = %d\n",prod); | |
| 101 exit(0); | |
| 102 } | |
| 103 \_\_code factorial0(int prod, int x) | |
| 104 { | |
| 105 if ( x >= 1) { | |
| 106 goto factorial0(prod\*x, x-1); | |
| 107 }else{ | |
| 108 goto print_factorial(prod); | |
| 109 } | |
| 110 } | |
| 111 \_\_code factorial(int x) | |
| 112 { | |
| 113 goto factorial0(1, x); | |
| 114 } | |
| 115 int main(int argc, char \*\*argv) | |
| 116 { | |
| 117 int i; | |
| 118 i = atoi(argv[1]); | |
| 119 goto factorial(i); | |
| 120 } | |
| 26 | 121 </pre> |
| 122 </td> | |
| 123 <td> | |
| 124 <li>__code によるコードセグメントの宣言</li> | |
| 37 | 125 <li>引数付きの goto でコードセグメントを呼び出すことができる</li> |
| 126 <li>内部では call ではなく jmp 命令でコードセグメントの処理が遷移している</li> | |
| 26 | 127 </td> |
| 128 </table> | |
| 129 | |
| 130 --- | |
| 131 | |
| 132 | |
| 35 | 133 Gnu Compiler Collection (GCC) |
| 134 ======== | |
| 37 | 135 <li>GCC: オープンソースのコンパイラ群</li> |
| 35 | 136 <li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li> |
| 137 <li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li> | |
| 138 <table width=100%> | |
| 139 <caption>GCC のアセンブラ言語出力までの流れ</caption> | |
| 140 <td style="margin:auto; text-align:center;"> | |
| 141 <img src="./pix/ir.png" style="height:15em"> | |
| 142 </td> | |
| 143 </table> | |
| 144 <li>ソースコードはアセンブラに変換される間に 4 つのデータ構造に変換される。</li> | |
| 145 <li>この中でも CbC の実装では Parser と RTL の生成部分に手が加えられている。</li> | |
| 146 | |
| 147 --- | |
| 148 | |
| 149 | |
| 150 CbC の実装 : 軽量継続 | |
| 26 | 151 ======== |
| 37 | 152 <li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Elimination(末尾除去)</font>により実装されている.</li> |
| 26 | 153 |
| 154 Tail Call Elimination | |
| 155 --------- | |
| 156 <li>関数呼び出しを call ではなく jmp 命令で行う最適化</li> | |
| 31 | 157 <li>例えば、以下の場合関数 g は jmp 命令で関数 f へと処理が移る</li> |
| 26 | 158 |
| 31 | 159 <table width=100% border=1> |
| 26 | 160 <tr> |
| 161 <td width=50%> | |
| 162 <pre> | |
| 163 void f(int a, int b) { | |
| 164 printf("f: a=%d b=%d\n",a,b); | |
| 165 return ; | |
| 166 } | |
| 167 | |
| 168 void g(int a, int b){ | |
| 169 printf("g: a=%d b=%d\n",a,b); | |
| 170 f(a,b); | |
| 171 return; | |
| 172 } | |
| 173 | |
| 174 int main() { | |
| 175 g(3,4); | |
| 176 return 0; | |
| 37 | 177 }</pre> |
| 26 | 178 </td> |
| 179 <td> | |
| 180 <img src="./pix/continuation.png" style="height:80%;"> | |
| 181 </td> | |
| 182 </tr> | |
| 183 </table> | |
| 184 | |
| 185 | |
| 186 --- | |
| 187 | |
| 188 | |
| 40 | 189 CbC の実装: 末尾除去の強制 |
| 26 | 190 ======== |
| 40 | 191 末尾除去の条件をチェックする関数 |
| 26 | 192 --------- |
| 40 | 193 - 関数が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。 |
| 194 - その関数を元に、『コードセグメントは末尾除去』にかける専用の関数を用意していた。 | |
| 195 - しかしこの方法は、元になった関数が修正に合わせて専用の関数も修正を行う必要があった。 | |
| 35 | 196 |
| 37 | 197 実装の修正とその利点 |
| 35 | 198 --------- |
| 40 | 199 - しかし, 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更。 |
| 35 | 200 - 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。 |
| 37 | 201 - また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。 |
| 26 | 202 |
| 203 | |
| 204 --- | |
| 205 | |
| 206 | |
| 207 | |
| 35 | 208 |
| 37 | 209 GCC-4.5, GCC-4.6 の性能比較 |
| 26 | 210 ======== |
| 35 | 211 <li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li> |
| 212 <li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li> | |
| 213 <li>conv1: 加算と継続を交互に繰り返すプログラム</li> | |
| 26 | 214 |
| 35 | 215 <table width=100% border=1> |
| 216 <caption>各コンパイラにより生成されたプログラムの速度比較</caption> | |
| 217 <tr> | |
| 26 | 218 <td style="margin:auto; text-align:center;"> |
| 219 <img src="./pix/conv1_for_resume.png" style="height:15em"> | |
| 220 </td> | |
| 221 <td> | |
| 222 <img src="./pix/conv1_mac_for_presen.png" style="height:15em"> | |
| 223 </td> | |
| 35 | 224 </tr> |
| 225 <tr> | |
| 226 <td style="text-align:center;">x86/Linux</td> | |
| 227 <td style="text-align:center;">x86/OS X (10.7)</td> | |
| 228 </tr> | |
| 26 | 229 </table> |
| 35 | 230 <li>Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。</li> |
| 40 | 231 <li>引数 2、3 は手動で最適化をかけている。</li> |
| 31 | 232 <li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li> |
| 26 | 233 |
|
34
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
234 |
| 26 | 235 --- |
| 236 | |
| 237 | |
| 35 | 238 |
| 239 GCC-4.6 の最適化 | |
| 26 | 240 ======== |
| 35 | 241 - GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。 |
| 242 | |
| 243 インライン展開 | |
| 244 --------- | |
| 245 - 関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化 | |
| 246 | |
| 26 | 247 <table width=100% border=1> |
| 35 | 248 <caption><h3>インライン展開の例</h3></caption> |
| 249 <tr> | |
| 250 <td width=50%> | |
| 37 | 251 <pre style="margin-left:5%"> |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
252 void func_b(){ |
| 35 | 253 A; |
| 254 B; | |
| 255 } | |
| 256 | |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
257 void func_a() { |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
258 func_b(); |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
259 func_b(); |
| 35 | 260 } |
| 261 </pre> | |
| 262 </td> | |
| 263 <td> | |
| 37 | 264 <pre style="margin-left:5%"> |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
265 void func_a() { |
| 35 | 266 A; |
| 267 B; | |
| 268 A; | |
| 269 B; | |
| 270 } | |
| 271 </pre> | |
| 272 </td> | |
| 273 </tr> | |
| 274 </table> | |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
275 <li>func_b の呼び出しがなくなっている。</li> |
| 35 | 276 |
| 277 | |
| 278 --- | |
| 279 | |
| 280 <h1>最適化の比較</h1> | |
| 281 <table width=100% border=1> | |
| 282 <caption><h3>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</h3></caption> | |
| 26 | 283 <tr> |
| 35 | 284 <td width=30%>最適化なし</td> |
| 285 <td width=30%>GCC-4.5の最適化(-O2)</td> | |
| 286 <td width=30%>GCC-4.6の最適化(-O2)</td> | |
| 26 | 287 </tr> |
| 288 <tr> | |
| 289 <td style="margin:auto; text-align:center;"> | |
| 35 | 290 <img src="./pix/state_conv1_noopt.png" style="width:65%;"> |
| 291 </td> | |
| 26 | 292 <td style="margin:auto; text-align:center;"> |
| 35 | 293 <img src="./pix/state_conv1_45.png" style="width:65%;"> |
| 294 </td> | |
| 26 | 295 <td style="margin:auto; text-align:center;"> |
| 35 | 296 <img src="./pix/state_conv1_46.png" style="width:65%;"> |
| 26 | 297 </td> |
| 298 </tr> | |
| 299 </table> | |
| 300 | |
| 35 | 301 - 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。 |
| 302 - GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。 | |
| 26 | 303 |
| 304 | |
| 305 --- | |
| 306 | |
| 38 | 307 最新バージョンに合わせる有用性 |
| 35 | 308 ======== |
| 26 | 309 |
| 35 | 310 - 今回の『インライン展開』のように GCC の最適化は日々改良されている。 |
| 29 | 311 - また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。 |
| 312 - それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。 | |
| 313 | |
| 314 --- | |
| 315 | |
| 316 | |
| 26 | 317 |
| 318 まとめ | |
| 319 ======== | |
| 29 | 320 - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。 |
| 35 | 321 - アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。 |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
322 - また、最適化の強制付与といった実装の修正も行えた。 |
| 35 | 323 - 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。 |
| 26 | 324 |
| 325 | |
| 326 今後の課題 | |
| 327 --------- | |
| 328 - LLVM ベースの CbC コンパイラの開発 | |
| 329 - google Go 言語への実装の検討 | |
| 330 | |
| 331 --- | |
| 332 | |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
333 |
| 40 | 334 CbC |
| 335 ======== | |
| 336 <li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li> | |
| 42 | 337 <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li> |
| 338 <li>現存する記述言語は状態遷移の記述に向いていない</li> | |
| 339 <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li> | |
| 340 <li>以上の問題を解決する言語として CbC は提案されている。</li> | |
| 40 | 341 |
| 342 具体的な CbC の利用予定 | |
| 343 --------- | |
| 344 - モデル検査 | |
| 345 - Cerium の実装 | |
| 346 | |
| 347 --- | |
| 348 | |
| 349 Tail Call Elimination | |
| 350 ======== | |
| 351 関数が Tail Call Elimination にかかる条件 | |
| 352 --------- | |
| 353 <ul> | |
| 354 <li>関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。</li> | |
| 355 <li>関数呼び出しがリターン直前に行われている。</li> | |
| 356 <li>呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。</li> | |
| 357 <li>引数の並びのコピーに上書きがない。</li> | |
| 358 </ul> | |
| 359 | |
| 360 条件回避の為の CbC の実装内容 | |
| 361 --------- | |
| 362 <ul> | |
| 363 <li>コードセグメントの型はvoid型で統一する。</li> | |
| 364 <li>gotoの直後に自動で return を置く。</li> | |
| 365 <li>スタックサイズは固定にする。</li> | |
| 366 <li>引数は一旦、一時変数にコピーする。</li> | |
| 367 </ul> | |
| 368 | |
| 369 --- | |
| 370 | |
| 371 | |
| 372 | |
| 373 | |
| 374 | |
|
34
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
375 jmp と call |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
376 ======== |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
377 <table width=100%> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
378 <caption>インライン展開無しの conv1 プログラム実行結果</caption> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
379 <td style="text-align:center;"> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
380 <img src="./pix/fno_inline.png"> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
381 </td> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
382 </table> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
383 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
384 --- |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
385 |
|
39
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
386 conv1 プログラム |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
387 ======== |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
388 <li>性能評価で用いた conv1 プログラムの C 版</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
389 <pre style="width:5%;" border=1> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
390 f0(int i) { |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
391 int k,j; |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
392 k = 3+i; |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
393 j = g0(i+3); |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
394 return k+4+j; |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
395 } |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
396 g0(int i) { |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
397 return h0(i+4)+i; |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
398 } |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
399 h0(int i) { |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
400 return i+4; |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
401 }</pre> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
402 <li>性能評価はこのプログラムを CbC へと書き換えて行なっている。</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
403 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
404 --- |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
405 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
406 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
407 CbC-GCC のアップデート手法 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
408 ======== |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
409 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
410 <ol> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
411 <li>GCC のソースを入れるリポジトリを用意する。</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
412 <li>GCC のリポジトリの中身を全て消し、新しい GCC を入れて新しいファイルは追加、消えたファイルは削除する。</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
413 <li>コミット</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
414 </ol> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
415 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
416 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
417 CbC-GCC のリポジトリ |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
418 --------- |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
419 <ol> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
420 <li>GCC のソースから pull</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
421 <li>merge を行う</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
422 <li>衝突のあったファイルを手動でマージする</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
423 <li>コミット</li> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
424 </ol> |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
425 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
426 --- |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
427 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
428 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
429 |
|
a6540714dda9
modify presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
38
diff
changeset
|
430 |
|
34
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
431 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
432 構文の追加 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
433 ======== |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
434 リカーシブタイプの宣言に使う"__rectype" |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
435 --------- |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
436 - 関数宣言時、以下のように引数に自分自身を指す型を入れたい。 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
437 <pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
438 \_\_code func(int, func*); |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
439 <pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
440 - 上記の宣言ではエラーがでる。その為、以下のような宣言になる。 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
441 <pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
442 \_\_code func(int, \_\_code (*)()); |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
443 </pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
444 - しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
445 <pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
446 \_\_code func(int, \_\_code (*)(int, \_\_code(*)(int, \_\_code(*)(int, ...)))) |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
447 </pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
448 - だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
449 - そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
450 <pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
451 \_\_code func(int, rectype*); |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
452 </pre> |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
453 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
454 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
455 --- |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
456 |
|
3922a95e99a8
commit presen
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
457 |
| 30 | 458 conv1 プログラム |
| 459 ======== | |
| 460 - conv1 プログラムでは計算と継続を交互に繰り返し行なう。 | |
| 461 - しかし状態のいくつかへは関数ポインタとして保存させておき継続を行う。 | |
| 462 <pre> | |
| 32 | 463 \_\_code g(int i,stack sp) { // Caller |
| 30 | 464 struct f_g0_interface *c = |
| 465 (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface)); | |
| 466 c->ret = g_h1; | |
| 467 c->i_ = i; | |
| 468 goto h(i+3,sp); | |
| 469 } | |
| 32 | 470 \_\_code h(int i,stack sp) { |
| 30 | 471 struct f_g0_interface *c = (struct f_g0_interface *)sp; |
| 472 goto (c->ret)(i+4,sp); | |
| 473 } | |
| 474 </pre> | |
| 475 | |
| 476 - 関数ポインタへの継続はインライン展開されない。 | |
| 477 | |
| 478 --- | |
| 479 | |
| 480 | |
| 28 | 481 CbC の実装: 環境付き継続 |
| 482 ======== | |
| 483 - 環境付き継続: C との互換を取るための機能。継続を行った C の関数に戻ることができる。 | |
| 484 - _CbC_return、 _CbC_environment キーワードを使うことで使える。 | |
| 485 - 以下の使い方の場合、戻値 1 を返す。 | |
| 486 <pre> | |
| 487 __code c1(__code ret(int,void *),void *env) { | |
| 488 goto ret(1,env); | |
| 489 } | |
| 490 int main() { | |
| 491 goto c1(__return, __environment); | |
| 492 } | |
| 493 </pre> | |
| 494 | |
| 495 - 今回この環境付き継続をスレッドセーフの実装へと修正した。 | |
| 496 | |
| 497 | |
| 498 --- | |
| 499 | |
| 26 | 500 |
| 501 CbC 引数渡し | |
| 502 ======== | |
| 503 <li>CbC では引数渡しにできるだけレジスタを用いるようにしている.</li> | |
| 504 <table border=1 width=100%> | |
| 505 <caption><small>fastcall属性有・無の実行速度</small></caption> | |
| 506 <tr> | |
| 507 <td width=50% style="text-align:center;">fastcall無し</td> | |
| 508 </tr> | |
| 509 <tr> | |
| 510 <td style="margin:auto; text-align:center;"> | |
| 511 <img src="./pix/linux_conv_nofastcall.png" style="height:15em;"> | |
| 512 </td> | |
| 513 </tr> | |
| 514 <tr> | |
| 515 <td width=50% style="text-align:center;">fastcall有り</td> | |
| 516 <tr> | |
| 517 <td> | |
| 518 <img src="./pix/linux_conv_fastcall.png" style="height:15em;"> | |
| 519 </td> | |
| 520 </tr> | |
| 521 </table> | |
| 522 | |
| 523 | |
| 524 --- | |
| 525 | |
| 526 | |
| 527 | |
| 32 | 528 引数の並びに上書きコピー |
| 529 ======== | |
| 530 <li>以下の呼び出しを行うと、スタックの書き換えがおこる</li> | |
| 531 <pre> | |
| 532 void funcA(int a, int b) { | |
| 533 funcB(b, a); | |
| 534 } | |
| 535 </pre> | |
| 536 | |
| 537 <table width=100%> | |
| 538 <tr> | |
| 539 <td style="margin:auto; text-align:center;"> | |
| 540 <img src="./pix/cs_prog.png"> | |
| 541 </td> | |
| 542 </tr> | |
| 543 </table> | |
| 544 | |
| 545 | |
| 546 --- | |
| 547 | |
| 29 | 548 最適化の比較 |
| 549 ======== | |
| 32 | 550 |
| 29 | 551 <table width=100% border=1> |
| 35 | 552 <caption>各コンパイラにより生成されたコードの速度比較</caption> |
| 553 <tr> | |
| 554 <td style="margin:auto; text-align:center;"> | |
| 555 <img src="./pix/O3_conv1_linux.png" style="height:15em"> | |
| 556 </td> | |
| 557 <td> | |
| 558 <img src="./pix/O3_conv1_mac.png" style="height:15em"> | |
| 559 </td> | |
| 560 </tr> | |
| 561 <tr> | |
| 562 <td style="text-align:center;">x86/Linux</td> | |
| 563 <td style="text-align:center;">x86/OS X (10.7)</td> | |
| 564 </tr> | |
| 565 </table> | |
| 566 | |
| 567 | |
| 568 | |
| 569 --- | |
| 570 | |
| 571 | |
| 572 | |
| 573 最適化の比較 | |
| 574 ======== | |
| 575 | |
| 576 <table width=100% border=1> | |
| 29 | 577 <caption>それぞれの最適化により吐かれたアセンブラコード</caption> |
| 578 <tr> | |
| 579 <td width=50% style="text-align:center;">CbC-GCC-4.5</td> | |
| 580 <td width=50% style="text-align:center;">CbC-GCC-4.6</td> | |
| 581 </tr> | |
| 582 | |
| 583 <tr> | |
| 584 <td> | |
| 585 <pre> | |
| 586 main: | |
| 587 call f | |
| 588 : | |
| 589 jmp f_g0 | |
| 590 : | |
| 591 movq $f_g1, -24(%rdx) | |
| 592 addl $10, %edi | |
| 593 movq $g_h1, -48(%rdx) | |
| 594 jmp g_h1 | |
| 595 : | |
| 596 movq 24(%rsi), %rdx | |
| 597 movq %rax, %rsi | |
| 598 : | |
| 599 jmp *%rdx | |
| 600 : | |
| 601 movq 24(%rsi), %rdx | |
| 602 : | |
| 603 jmp *%rdx | |
| 604 </pre> | |
| 605 </td> | |
| 606 <td> | |
| 607 <pre> | |
| 608 main: | |
| 609 movq $f_g1, main_stack+2000(%rip) | |
| 610 : | |
| 611 call g_h1 | |
| 612 : | |
| 613 movq 24(%rax), %rdx | |
| 614 : | |
| 615 jmp *%rdx | |
| 616 : | |
| 617 movq 24(%rax), %rdx | |
| 618 : | |
| 619 jmp *%rdx | |
| 620 </pre> | |
| 621 </td> | |
| 622 </tr> | |
| 623 <!-- | |
| 624 <tr> | |
| 625 <td></td> | |
| 626 <td></td> | |
| 627 </tr> | |
| 628 --> | |
| 629 | |
| 630 </table> | |
| 631 <li>関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる</li> | |
| 632 <!-- | |
| 633 <li>保存していた関数ポインタへの継続はインライン展開は行われない</li> | |
| 634 --> | |
| 635 | |
| 636 --- | |
| 26 | 637 |
| 638 | |
| 639 | |
| 640 | |
| 641 | |
| 642 | |
| 643 | |
| 644 | |
| 645 | |
| 646 | |
| 647 |