54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 <html xmlns="http://www.w3.org/1999/xhtml">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 <head>
|
80
|
7 <style type="text/css">
|
|
8 tr.srctr {
|
|
9 font-size:28px;
|
|
10 }
|
|
11 td.srctd {
|
|
12 height:17em;
|
|
13 }
|
|
14 pre.srcbox {
|
|
15 height: 100%;
|
|
16 overflow: scroll;
|
|
17 }
|
|
18 .src{
|
|
19 overflow: scroll;
|
|
20 width: 90%;
|
|
21 height: 60%;
|
|
22 }
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 .center {
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 margin-left: auto;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25 margin-right: auto;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 text-align: center;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 }
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 .textcenter {
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 text-align: center;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 }
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 .taninaritop {
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 margin: auto;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 width: 95%;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 font-weight: bold;
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 }
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 </style>
|
80
|
37 <title>2012/ 1/ 7</title>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 <!-- metadata -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 <meta name="generator" content="S5" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 <meta name="version" content="S5 1.1" />
|
80
|
41 <meta name="presdate" content="20120107" />
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 <meta name="author" content="Nobuyasu Oshiro" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 <meta name="company" content="University of the Ryukyu" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 <!-- meta temporary -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 <meta http-equiv="content-type" content="text/html; charset=utf-8" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 <meta http-equiv="Content-Script-Type" content="text/javascript" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 <meta http-equiv="Content-Style-Type" content="text/css" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 <!-- configuration parameters -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 <meta name="defaultView" content="slideshow" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 <meta name="controlVis" content="hidden" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 <!-- configuration extensions -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 <meta name="tranSitions" content="true" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 <meta name="fadeDuration" content="500" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 <meta name="incrDuration" content="250" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 <!-- configuration autoplay extension -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 <meta name="autoMatic" content="false" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 <meta name="playLoop" content="true" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 <meta name="playDelay" content="10" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 <!-- configuration audio extension -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 <meta name="audioSupport" content="false" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 <meta name="audioVolume" content="100" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 <meta name="audioError" content="false" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 <!-- configuration audio debug -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 <meta name="audioDebug" content="false" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 <!-- style sheet links -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 <link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 <link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 <link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 <link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" />
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 <!-- embedded styles -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 <style type="text/css" media="all">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 .imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;}
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 #anim {width: 33%; height: 320px; position: relative;}
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 #anim img {position: absolute; top: 0px; left: 0px;}
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 </style>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 <!-- S5 JS -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 <script src="ui/default_utf/slides.js" type="text/javascript"></script>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 </head>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 <body>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 <div class="layout">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 <div id="controls"><!-- DO NOT EDIT --></div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 <div id="currentSlide"><!-- DO NOT EDIT --></div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 <div id="header"></div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 <div id="footer">
|
80
|
86 <h1>プログラミングシンポジウム: 2012/ 1/ 7</h1>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 <h2>並列信頼研</h2>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 <div class="presentation">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 <div class="slide">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 <h1>Continuation based Cの GCC 4.6 上の実装について</li>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 <h3></h3>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 <li>大城 信康</li>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 <div class="handout"></div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 <div class="slide">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 <h1>目的と背景(1)</h1>
|
80
|
103 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)を開発している。</li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 <li>コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。</li>
|
80
|
105 <li>Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。</li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 <div class="slide">
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 <h1>目的と背景(2)</h1>
|
80
|
110 <li>CbC のコンパイラは2001年に Micro-C 版、2008年には GCC-4.2 をベースとしたコンパイラが開発された。</li>
|
|
111 <li>GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。</li>
|
|
112 <li>本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。 </li>
|
|
113 </div>
|
|
114 <!-- PAGE -->
|
|
115 <div class="slide">
|
|
116 <h1>発表内容</h1>
|
|
117 <ol>
|
|
118 <li>CbC の紹介</li>
|
|
119 <li>GCC でのコンパイルの流れ</li>
|
|
120 <font color="red">
|
|
121 <li>CbC の実装</li>
|
|
122 </font>
|
|
123 <li>Micro-C との性能比較</li>
|
|
124 <li>まとめ</li>
|
|
125 <ol>
|
|
126 </div>
|
|
127 <!-- PAGE -->
|
|
128 <div class="slide">
|
|
129 <h1>Continuation based C </h1>
|
|
130 <h2>コードセグメント単位での記述と継続を基本としたプログラミング言語。</h2>
|
|
131 <ul>
|
|
132 <li>コードセグメント:CbCにおけるプログラムの基本単位</li>
|
|
133 <ul>
|
|
134 <li>C の関数よりも細かい単位になる。</li>
|
|
135 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することでCbCのプログラムは続いていく。</li>
|
|
136 <li>Cから関数コールとループ制御が取り除かれた形となる。</li>
|
|
137 </ul>
|
|
138 <p class="center">
|
|
139 <img src="./pix/codesegment.png" style="height:6em;">
|
|
140 </p>
|
|
141 </ul>
|
|
142 </div>
|
|
143 <!-- PAGE -->
|
|
144 <div class="slide">
|
|
145 <h1>Continuation based C </h1>
|
|
146 <h2>継続:現在の処理を実行していく為の情報</h2>
|
|
147
|
|
148 <table width=100% border=1>
|
|
149 <tr>
|
|
150 <td><small>Cの継続</small></td>
|
|
151 <td><small>CbCの継続(軽量継続)</small></td>
|
|
152 </tr>
|
|
153 <tr style="font-size:30px">
|
|
154 <td>
|
|
155 <ul>
|
|
156 <li>続く命令のアドレス</li>
|
|
157 <li>命令に必要なデータ</li>
|
|
158 <li>スタックに積まれている値(環境)</li>
|
|
159 </ul>
|
|
160 </td>
|
|
161 <td>
|
|
162 <ul>
|
|
163 <li>Cの継続から環境を除外</li>
|
|
164 <li>続く命令とその命令に必要なデータのみ</li>
|
|
165 </ul>
|
|
166 </td>
|
|
167 </tr>
|
|
168 <tr>
|
|
169 <td style="margin-left:auto; margin-right: auto; text-align: center;">
|
|
170 <img class="scale" src="./pix/func_call.png" style="height: 6em;">
|
|
171 </td>
|
|
172 <td style="margin-left:auto; margin-right: auto; text-align: center;">
|
|
173 <img class="scale" src="./pix/cs_stack.png" style="height: 6em;">
|
|
174 </td>
|
|
175 </tr>
|
|
176 </table>
|
|
177 <li>コードセグメントへの継続はcallではなくjmp命令で行われる</li>
|
|
178 </div>
|
|
179 <!-- PAGE -->
|
|
180 <div class="slide">
|
|
181 <h1>Continuation based C </h1>
|
|
182 <table width=100% border=1>
|
|
183 <caption><small>階乗を求めるCbCのプログラム</small></caption>
|
|
184 <tr class="srctr">
|
|
185 <td width=50%>
|
|
186 <pre class="srcbox">
|
|
187
|
|
188 __code print_factorial(int prod) {
|
|
189 printf("factorial = %d\n",prod);
|
|
190 exit(0);
|
|
191 }
|
|
192
|
|
193 __code factorial0(int prod, int x) {
|
|
194 if ( x >= 1) {
|
|
195 goto factorial0(prod*x, x-1);
|
|
196 }else{
|
|
197 goto print_factorial(prod);
|
|
198 }
|
|
199 }
|
|
200 </pre>
|
|
201 </td>
|
|
202 <td>
|
|
203 <pre class="srcbox">
|
|
204
|
|
205 __code factorial(int x) {
|
|
206 goto factorial0(1, x);
|
|
207 }
|
|
208
|
|
209 int main(int argc, char **argv) {
|
|
210 int i;
|
|
211 i = atoi(argv[1]);
|
|
212 goto factorial(i);
|
|
213 return 0;
|
|
214 }
|
|
215 </pre>
|
|
216 </td>
|
|
217 </tr>
|
|
218 </table>
|
|
219 <ul>
|
|
220 <li><small>__code キーワードによるコードセグメントの宣言</small></li>
|
|
221 <li><small>goto によるコードセグメントへの継続(Cの関数呼び出しと同等)</small></li>
|
|
222 </ul>
|
|
223 <li class="incremental"><small>以上がCbCについての紹介となる。</small></li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
225 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
226 <div class="slide">
|
80
|
227 <h1>GCC</h1>
|
|
228 <ul>
|
|
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>
|
|
236 </ul>
|
|
237 <li class="incremental">CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられている。</li>
|
|
238 <li class="incremental">Generic Tree生成部分について詳しく触れてみる。</li>
|
|
239 </ul>
|
|
240 </div>
|
|
241 <!-- PAGE -->
|
|
242 <!--
|
|
243 <div class="slide">
|
|
244 <h1>GCC:Generic Tree</h1>
|
|
245 <li>Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。</li>
|
|
246 <table class="center" width=100% border=1>
|
|
247 <tr>
|
|
248 <td></td>
|
|
249 <td><small>値の代入:MODIFY_EXPR</small></td>
|
|
250 <td><small>関数呼び出し:CALL_EXPR</small></td>
|
|
251 </t>
|
|
252 <tr>
|
|
253 <td>命令</td>
|
|
254 <td>b = a * 10</td>
|
|
255 <td>func(a,10)</td>
|
|
256 </t>
|
|
257 <tr>
|
|
258 <td><small>Generic<br>Tree</small></td>
|
|
259 <td>
|
|
260 <img src="./pix/MODIFY_EXPR.png" style="height: 6em;">
|
|
261 </td>
|
|
262 <td>
|
|
263 <img src="./pix/CALL_EXPR.png" style="height: 7em;">
|
|
264 </td>
|
|
265 </tr>
|
|
266 </table>
|
|
267 <p class="center"><small>Generic Treeでの表現</small></p>
|
|
268 </div>
|
|
269 -->
|
|
270 <!-- PAGE -->
|
|
271 <div class="slide">
|
|
272 <h1>GCC:Generic Tree</h1>
|
|
273 <li><small>CALL_EXPRE、MODIFY_EXPR等といった表現で扱われる。</small></li>
|
|
274 <table width=100% border=1>
|
|
275 <tr>
|
|
276 <td class="center"><small>ソースコード</small></td>
|
|
277 <td class="center"><small>Generic Treeでの表現</small></td>
|
|
278 </tr>
|
|
279 <tr>
|
|
280 <td>
|
|
281 <small>
|
|
282 <pre>
|
|
283 int main() {
|
|
284 int a, b;
|
|
285 a = 3;
|
|
286 b = func(a, 10);
|
|
287 return b;
|
|
288 }
|
|
289 </pre>
|
|
290 </small>
|
|
291 </td>
|
|
292 <td style="margin-left:auto; margin-right:auto; text-align: center;">
|
|
293 <img src="./pix/STATEMENT_LIST.png" style="height: 7em;">
|
|
294 </td>
|
|
295 </tr>
|
|
296 </table>
|
|
297 <li class="incremental">CbCの実装においてこのGeneric Treeの生成を意識していくことになる。</li>
|
|
298 </div>
|
|
299 <!-- PAGE -->
|
|
300 <!--
|
|
301 <div class="slide">
|
|
302 <h1>GCC</h1>
|
|
303 <li>GCC についての簡単な説明を行う...</li>
|
|
304 <li>TODO: NEXT_PASS() の把握</li>
|
|
305 <img src="./pix/ir.png" style="height: 6em;">
|
|
306 <li>CbCの実装は主に Parser の部分と RTL を生成する部分に行われる。</li>
|
|
307 </div>
|
|
308 -->
|
|
309 <!-- PAGE -->
|
|
310 <div class="slide">
|
|
311 <h1>CbCの実装</h1>
|
|
312 <ul>
|
|
313 <li>シンタックスの追加</li>
|
|
314 <li>末尾除去:Tail Call Elimination(TCE)</li>
|
|
315 <li>レジスタによる引数渡し(fastcall属性の付与)</li>
|
|
316 <li>環境付き継続</li>
|
|
317 <!--
|
|
318 <li>__rectype の実装</li>
|
|
319 -->
|
|
320 </ul>
|
|
321 </div>
|
|
322 <!-- PAGE -->
|
|
323 <div class="slide">
|
|
324 <h1>CbCの実装:__codeシンタックスの追加</h1>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
325 <ul>
|
80
|
326 <li>__code キーワードでのコードセグメントの宣言</li>
|
|
327 <ul>
|
|
328 <li>__code 用idとkeywordを作成。</li>
|
|
329 <li>戻り値が無い為、コードセグメントは void 型の関数で作成される木と同じ木が作られる。</li>
|
|
330 </ul>
|
|
331 </ul>
|
|
332 <table width=100% border=1>
|
|
333 <tr class="srctr">
|
|
334 <td>
|
|
335 <pre>
|
|
336 const struct c_common_resword c_common_reswords[] =
|
|
337 {
|
|
338 { "_Bool", RID_BOOL, D_CONLY },
|
|
339 :
|
|
340 { "__code", RID_CbC_CODE, 0 },
|
|
341 </pre>
|
|
342 </td>
|
|
343 </tr>
|
|
344 <tr class="srctr">
|
|
345 <td>
|
|
346 <pre>
|
|
347 case RID_CbC_CODE:
|
|
348 :
|
|
349 specs->typespec_word = cts_CbC_code;
|
|
350 </pre>
|
|
351 </td>
|
|
352 </tr>
|
|
353 <tr class="srctr">
|
|
354 <td>
|
|
355 <pre>
|
|
356 case cts_CbC_code:
|
|
357 :
|
|
358 specs->type = void_type_node;
|
|
359 break;
|
|
360 </pre>
|
|
361 </td>
|
|
362 </tr>
|
|
363 </table>
|
|
364 </div>
|
|
365 <!-- PAGE -->
|
|
366 <div class="slide">
|
|
367 <h1>CbCの実装:gotoシンタックスの追加</h1>
|
|
368 <li>goto によるコードセグメントへの継続</li>
|
|
369 <ul>
|
|
370 <li>通常の goto に加え、コードセグメントへ継続する処理を追加。</li>
|
|
371 <li>コードセグメントへのgotoの後に、returnの処理を自動で追加。</li>
|
|
372 </ul>
|
|
373 <li><small>追加したgotoシンタックスの実際のソースは次のようになる。</small></li>
|
|
374 <pre class="srcbox" style="font-size:25px; height:16em;">
|
|
375 case RID_GOTO:
|
|
376 c_parser_consume_token (parser);
|
|
377 if ( c_parser_next_token_is (parser, CPP_NAME)
|
|
378 && c_parser_peek_2nd_token (parser)->type == CPP_SEMICOLON )
|
|
379 {
|
|
380 stmt = c_finish_goto_label (loc,
|
|
381 c_parser_peek_token (parser)->value);
|
|
382 c_parser_consume_token (parser);
|
|
383 }
|
|
384 else if (c_parser_next_token_is (parser, CPP_MULT))
|
|
385 {
|
|
386 tree val;
|
|
387
|
|
388 c_parser_consume_token (parser);
|
|
389 val = c_parser_expression (parser).value;
|
|
390 mark_exp_read (val);
|
|
391 stmt = c_finish_goto_ptr (loc, val);
|
|
392 }
|
|
393 else
|
|
394 expr = c_parser_expr_no_commas (parser, NULL);
|
|
395 if (TREE_CODE(expr.value) == CALL_EXPR )
|
|
396 {
|
|
397 location_t loc = c_parser_peek_token (parser)->location;
|
|
398 cbc_replace_arguments (loc, expr.value);
|
|
399 TREE_TYPE(expr.value) = void_type_node;
|
|
400 CbC_IS_CbC_GOTO (expr.value) = 1;
|
|
401 CALL_EXPR_TAILCALL (expr.value) = 1;
|
|
402 add_stmt(expr.value);
|
|
403 stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
|
|
404 }
|
|
405 </pre>
|
|
406 </div>
|
|
407 <!-- PAGE -->
|
|
408 <div class="slide">
|
|
409 <h1>CbCの実装:gotoシンタックスの追加</h1>
|
|
410 <ul>
|
|
411 <small>
|
|
412 <li>cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。</li>
|
|
413 <li>CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。</li>
|
|
414 <li>最後にc_finish_return関数によりreturn文を生成している。</li>
|
|
415 </small>
|
|
416 </ul>
|
|
417 <table border=1 width=100%>
|
|
418 <!--
|
|
419 <caption><small>return 自動生成</small></caption>
|
|
420 -->
|
|
421 <tr class="center">
|
|
422 <td><small>実際のコード</small></td>
|
|
423 <td><small>GCC内で処理されるコード</small></td>
|
|
424 </tr>
|
|
425 <tr class="srctr">
|
|
426 <td>
|
|
427 <pre>
|
|
428
|
|
429 __code test() {
|
|
430 :
|
|
431 goto factorial0(1, x);
|
|
432 }
|
|
433 </pre>
|
|
434 </td>
|
|
435 <td>
|
|
436 <pre>
|
|
437
|
|
438 void test() {
|
|
439 :
|
|
440 factorial0(1, x);
|
|
441 return;
|
|
442 }
|
|
443 </pre>
|
|
444 </td>
|
|
445 </tr>
|
|
446 </table>
|
|
447 <ul>
|
|
448 <li><small>tail callフラグを立てることで、関数呼び出しに末尾除去(末尾最適化)をかけることができる。</small></li>
|
|
449 <li><small>最後のリターン文生成も、末尾除去にかける為に必要な処理。</small></li>
|
|
450 </ul>
|
|
451 </div>
|
|
452 <!-- PAGE -->
|
|
453 <div class="slide">
|
|
454 <h1>CbCの実装:TCE(末尾除去)</h1>
|
|
455 <h2>末尾除去:Tail Call Elimination(TCE)</h2>
|
|
456 <ul>
|
|
457 <li>関数呼び出しをcallではなくjmp命令で行う最適化。</li>
|
|
458 </ul>
|
|
459 <li><small>以下のソースの場合 関数g から関数f へjmp命令で処理が移る。</small></li>
|
|
460 <br>
|
|
461 <table width=100%>
|
|
462 <tr class="srctr">
|
|
463 <td width=50%>
|
|
464 <!--
|
|
465 <pre class="srcbox">
|
|
466 int main() {
|
|
467 int num = a(2);
|
|
468 printf("main:num=%d\n",num);
|
|
469 return 0;
|
|
470 }
|
|
471 int a(int num) {
|
|
472 return b(num+5);
|
|
473 }
|
|
474 int b(int num) {
|
|
475 printf("b:a = %d\n",num);
|
|
476 return num+3;
|
|
477 }
|
|
478 </pre>
|
|
479 -->
|
|
480 <pre class="srcbox">
|
|
481
|
|
482 void f(int a, int b) {
|
|
483 printf("f: a=%d b=%d\n",a,b);
|
|
484 return ;
|
|
485 }
|
|
486 void g(int a, int b){
|
|
487 printf("g: a=%d b=%d\n",a,b);
|
|
488 f(a,b);
|
|
489 return;
|
|
490 }
|
|
491
|
|
492 int main() {
|
|
493 g(3,4);
|
|
494 return 0;
|
|
495 }
|
|
496
|
|
497 </pre>
|
|
498 </td>
|
|
499 <td class="center">
|
|
500 <img src="./pix/continuation.png" style="height:100%;">
|
|
501 </td>
|
|
502 </tr>
|
|
503 </table>
|
|
504 </div>
|
|
505 <!-- PAGE -->
|
|
506 <div class="slide">
|
|
507 <h1>CbCの実装:TCE(末尾除去)</h1>
|
|
508 <ul>
|
|
509 <li>TCEにかかる条件</li>
|
|
510 <ul>
|
|
511 <li>caller側とcallee側の戻値の型の一致している。</li>
|
|
512 <li>関数呼び出しがリターン直前に行われている。</li>
|
|
513 <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
|
|
514 <li>引数の並びのコピーに上書きがない。</li>
|
|
515 </ul>
|
|
516 <li class="incremental">条件を回避する為以下の実装にする。</li>
|
|
517 <ul class="incremental">
|
|
518 <li>型はvoid型で統一する。</li>
|
|
519 <li>gotoの直後にreturnを置く。</li>
|
|
520 <li>スタックサイズは固定にする。</li>
|
|
521 <li>引数は一旦、一時変数にコピーする。</li>
|
|
522 </ul>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
523 </ul>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
524 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
525 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526 <div class="slide">
|
80
|
527 <h1>CbCの実装:TCE(末尾除去)</h1>
|
|
528 <li>TCEの条件はexpand_call関数で調べられる。</li>
|
|
529 <ul>
|
|
530 <li>expand_call関数</li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
531 <ul>
|
80
|
532 <li>Treeで表された関数からRTLを生成する関数</li>
|
|
533 <li>スタックの領域確保、引数の格納、関数へのcall命令の発行が行わる。</li>
|
|
534 <li>try_taill_call(変数名)フラグがあり、TCEの条件に合わなければこのフラグが落とされる。</li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
535 </ul>
|
80
|
536 <li class="incremental">具体的な実装内容</li>
|
|
537 <ul>
|
|
538 <li class="incremental">try_tail_callフラグを落とすif文の条件をかわすようにする。</li>
|
|
539 <li class="incremental">try_tail_callフラグを立たせる処理の追加。</li>
|
|
540 </ul>
|
|
541 <ul>
|
|
542
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545 <div class="slide">
|
80
|
546 <h1>CbCの実装:TCE(末尾除去)</h1>
|
|
547 <li>try_tail_callフラグが落とされる部分</li>
|
|
548 <table width=100%>
|
|
549 <tr class="srctr">
|
|
550 <td class="srctd">
|
|
551 <pre class="srcbox">
|
|
552
|
|
553 if (currently_expanding_call++ != 0
|
|
554 || ((!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)))
|
|
555 && !flag_optimize_sibling_calls)
|
|
556 || args_size.var
|
|
557 || dbg_cnt (tail_call) == false)
|
|
558 try_tail_call = 0;
|
|
559
|
|
560 :
|
|
561
|
|
562 if (
|
|
563 #ifdef HAVE_sibcall_epilogue
|
|
564 !HAVE_sibcall_epilogue
|
|
565 #else
|
|
566 1
|
|
567 #endif
|
|
568 || !try_tail_call
|
|
569 || structure_value_addr != NULL_RTX
|
|
570 #ifdef REG_PARM_STACK_SPACE
|
|
571 || (OUTGOING_REG_PARM_STACK_SPACE (funtype)
|
|
572 != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)))
|
|
573 || (reg_parm_stack_space != REG_PARM_STACK_SPACE (fndecl))
|
|
574 #endif
|
|
575 || !targetm.function_ok_for_sibcall (fndecl, exp)
|
|
576 || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN))
|
|
577 || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))
|
|
578 || (fndecl && decl_function_context (fndecl) == current_function_decl)
|
|
579 || args_size.constant > (crtl->args.size
|
|
580 - crtl->args.pretend_args_size)
|
|
581 || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant)
|
|
582 != targetm.calls.return_pops_args (current_function_decl,
|
|
583 TREE_TYPE (current_function_decl),
|
|
584 crtl->args.size))
|
|
585 || !lang_hooks.decls.ok_for_sibcall (fndecl))
|
|
586 try_tail_call = 0;
|
|
587
|
|
588 :
|
|
589
|
|
590 /* Check if caller and callee disagree in promotion of function
|
|
591 return value. */
|
|
592 #ifndef noCbC
|
|
593 if (try_tail_call && (!fndecl || !CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))))
|
|
594 #else
|
|
595 if (try_tail_call)
|
|
596 #endif
|
|
597 {
|
|
598 enum machine_mode caller_mode, caller_promoted_mode;
|
|
599 enum machine_mode callee_mode, callee_promoted_mode;
|
|
600 int caller_unsignedp, callee_unsignedp;
|
|
601 tree caller_res = DECL_RESULT (current_function_decl);
|
|
602
|
|
603 caller_unsignedp = TYPE_UNSIGNED (TREE_TYPE (caller_res));
|
|
604 caller_mode = DECL_MODE (caller_res);
|
|
605 callee_unsignedp = TYPE_UNSIGNED (TREE_TYPE (funtype));
|
|
606 callee_mode = TYPE_MODE (TREE_TYPE (funtype));
|
|
607 caller_promoted_mode
|
|
608 = promote_function_mode (TREE_TYPE (caller_res), caller_mode,
|
|
609 &caller_unsignedp,
|
|
610 TREE_TYPE (current_function_decl), 1);
|
|
611 callee_promoted_mode
|
|
612 = promote_function_mode (TREE_TYPE (funtype), callee_mode,
|
|
613 &callee_unsignedp,
|
|
614 funtype, 1);
|
|
615 if (caller_mode != VOIDmode
|
|
616 && (caller_promoted_mode != callee_promoted_mode
|
|
617 || ((caller_mode != caller_promoted_mode
|
|
618 || callee_mode != callee_promoted_mode)
|
|
619 && (caller_unsignedp != callee_unsignedp
|
|
620 || GET_MODE_BITSIZE (caller_mode)
|
|
621 < GET_MODE_BITSIZE (callee_mode)))))
|
|
622 try_tail_call = 0;
|
|
623 }
|
|
624 </pre>
|
|
625 </td>
|
|
626 </tr>
|
|
627 </table>
|
|
628 <li><string>!CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl)により条件を回避</string></li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
631 <div class="slide">
|
80
|
632 <h1>CbCの実装:TCE(末尾除去)</h1>
|
|
633 <li>try_tail_callフラグ矯正付与のソースコード</li>
|
|
634 <table width=100%>
|
|
635 <tr class="srctr">
|
|
636 <td>
|
|
637 <pre class="srcbox">
|
|
638 #ifndef noCbC
|
|
639 if (fndecl && CbC_IS_CODE_SEGMENT (TREE_TYPE (fndecl))
|
|
640 && CbC_IS_CODE_SEGMENT (TREE_TYPE (current_function_decl))
|
|
641 && try_tail_call == 0)
|
|
642 {
|
|
643 location_t loc = EXPR_LOCATION (exp);
|
|
644 char *name_callee = IDENTIFIER_POINTER(DECL_NAME(fndecl));
|
|
645 warning_at (loc, 0, "transition to code segment \"%s\" with CbC goto, but tail call optimization was cut.",
|
|
646 name_callee);
|
|
647 try_tail_call = 1;
|
|
648 }
|
|
649 #endif
|
|
650 </pre>
|
|
651 </td>
|
|
652 </tr>
|
|
653 </table>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
654 <ul>
|
80
|
655 <li>try_tail_callフラグが落とされた場合warningを出してフラグを立たせる。
|
|
656 <br><small>(最適化の矯正付与)</small></li>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
657 </ul>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
658 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
659 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
660 <div class="slide">
|
80
|
661 <h1>CbCの実装:TCE(末尾除去)の実装について</h1>
|
|
662 <ul>
|
|
663 <li>以前はexpand_call関数を元にしたexpand_cbc_goto関数を作り条件を回避させていた。</li>
|
|
664 <li>だがその方法だとexpand_call関数の修正にも合わせていく必要もあり管理も面倒であった。</li>
|
|
665 <li>しかしtry_tail_callフラグを落とさせない方法にすることでexpand_cbc_goto関数はいらなくなり、管理が容易くなった。</li>
|
|
666 </ul>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
667 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
668 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
669 <!--
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
670 <div class="slide">
|
80
|
671 <h1>CbCの実装</h1>
|
|
672 <li>CbCの基本機能を実現する為の実装は以上の2つになる。</li>
|
|
673 <ul>
|
|
674 <li>シンタックスの追加</li>
|
|
675 <li>末尾除去によるコードセグメントへjmp命令での処理の移り</li>
|
|
676 </ul>
|
|
677 <li class="incremental">ここからはCbCの機能の拡張になる。</li>
|
|
678 </div>
|
|
679 -->
|
|
680 <!-- PAGE -->
|
|
681 <!--
|
|
682 <div class="slide">
|
|
683 <h1>CbCの実装:環境付き継続</h1>
|
|
684 <li>CbCにおけるCとの互換性を保つための機能。</li>
|
|
685 <li>コードセグメントを呼び出したCの関数に戻ることができる。</li>
|
|
686 <li>論文における訂正</li>
|
|
687 <li>『GCC 4.6 と Lion の組合せでは Closure は正しく動作していないことが分かった.』</li>
|
|
688 <ul>
|
|
689 <li>GCC 4.6 への CbC の実装のせいでクロージャがうまくできていなかったことが判明。</li>
|
|
690 <li>GCC 4.6 と Lion でのクロージャは特に問題はない。</li>
|
|
691 </ul>
|
|
692 </div>
|
|
693 -->
|
|
694 <!-- PAGE -->
|
|
695 <!--
|
|
696 <div class="slide">
|
|
697 <h1>環境付き継続:論文におけるクロージャの問題の訂正</h1>
|
|
698 <p><small>『GCC 4.6とLionの組み合わせではclosureは正しく動作してないことが分かった。』<br>
|
|
699 とあるが、これはCbCの実装でTCEを強制的に立てることが原因であったことを訂正させて頂きます。</small></p>
|
|
700 </div>
|
|
701 -->
|
|
702 <!-- PAGE -->
|
|
703 <div class="slide">
|
|
704 <h1>CbCの実装:引数渡し</h1>
|
|
705 <li>GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。</li>
|
|
706 <ul>
|
|
707 <li class="incremental">Micro-Cでは関数呼び出しの際にできるだけレジスタを使うようにしていた。</li>
|
|
708 </ul>
|
|
709 <li class="incremental">そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。</li>
|
|
710 </div>
|
|
711 <!-- PAGE -->
|
|
712 <div class="slide">
|
|
713 <h1>CbCの実装:引数渡し(fastcall)</h1>
|
|
714 <h2>fastcall</h2>
|
|
715 <ul>
|
|
716 <li>i386 において関数呼び出しの際、引数渡しをできるだけレジスタを用いるGCCの拡張機能。</li>
|
|
717 <li>関数に『__attribute__ ((fastcall))』をつけることで使えるようになる。</li>
|
|
718 </ul>
|
|
719 <li>__codeで宣言された関数は自動でfastcall属性が付与されるように以下のコードを追加。</li>
|
|
720 <small>
|
|
721 <pre>
|
|
722 if(!TARGET_64BIT) {
|
|
723 attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE);
|
|
724 declspecs_add_attrs(specs, attrs);
|
|
725 }
|
|
726 </pre>
|
|
727 </small>
|
|
728 <p><small>Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。</small></p>
|
|
729 </div>
|
|
730 <!-- PAGE -->
|
|
731 <div class="slide">
|
|
732 <h1>CbCの実装:引数渡し</h1>
|
|
733 <ul>
|
|
734 <li>fastcall属性の付与によりMicro-C版に速度で勝るようになった。</li>
|
|
735 </ul>
|
|
736 <br>
|
|
737 <table width=100% border=1 class="center">
|
|
738 <caption><small>引数渡しに使われるレジスタの数(gcc)</small></caption>
|
|
739 <tr>
|
|
740 <td>arch</td>
|
|
741 <td>int(整数型)</td>
|
|
742 <td>float(浮動小数点型)</td>
|
|
743 <td>double(浮動小数点型)</td>
|
|
744 </tr>
|
|
745 <tr>
|
|
746 <td>i386</td>
|
|
747 <td>2</td>
|
|
748 <td>0<br>(stackを使用)</td>
|
|
749 <td>0<br>(stackを使用)</td>
|
|
750 </tr>
|
|
751 <tr>
|
|
752 <td>x64</td>
|
|
753 <td>6</td>
|
|
754 <td>8</td>
|
|
755 <td>8</td>
|
|
756 </tr>
|
|
757 </table>
|
|
758 </div>
|
|
759 <!-- PAGE -->
|
|
760 <div class="slide">
|
|
761 <h1>CbCの実装:環境付き継続</h1>
|
|
762 <ul>
|
|
763 <li>CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。</li>
|
|
764 <li>__returnキーワードを引数に渡すことで使うことができる。</li>
|
|
765 </ul>
|
|
766 <li>以下の使い方の場合は1を返す。</li>
|
|
767 <table border=1 width=100%>
|
|
768 <td>
|
|
769 <small>
|
|
770 <pre class="srcbox">
|
|
771 __code c1(__code ret(int,void *),void *env) {
|
|
772 goto ret(1,env);
|
|
773 }
|
|
774 int main() {
|
|
775 goto c1(__return, __environment);
|
|
776 }
|
|
777 </pre>
|
|
778 </small>
|
|
779 </td>
|
|
780 </table>
|
|
781 <p><small>__environmentキーワードは関数の環境を保持する(Micro-Cの場合)。</small></p>
|
|
782 </div>
|
|
783 <!-- PAGE -->
|
|
784 <div class="slide">
|
|
785 <h1>CbCの実装:環境付き継続</h1>
|
|
786 <!--
|
|
787 <li><small>生成しているコードと生成する為のコード</small></li>
|
|
788 -->
|
|
789 <table border=1 width=100%>
|
|
790 <tr>
|
|
791 <td><small>生成しているコード</small></td>
|
|
792 <td><small>生成されるTree</small></td>
|
|
793 </tr>
|
|
794 <tr class="srctr">
|
|
795 <td width=50% class="srctd">
|
|
796 <pre class="srcbox" style="width:25em;">
|
|
797
|
|
798 //goto c1(__return, __environment);
|
|
799 goto c1(({
|
|
800 __label__ _cbc_exit0;
|
|
801 static int retval;
|
|
802 void _cbc_internal_return(int retval_, void *_envp) {
|
|
803 retval = retval_;
|
|
804 goto _cbc_exit0;
|
|
805 }
|
|
806 if (0) {
|
|
807 _cbc_exit0:
|
|
808 return retval;
|
|
809 }
|
|
810 _cbc_internal_return;
|
|
811 }), __environment);
|
|
812 </pre>
|
|
813 </td>
|
|
814 <td width=50% class="srctd">
|
|
815 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
|
|
816 </td>
|
|
817 </tr>
|
|
818 </table>
|
|
819 <li><small>retval変数の型は継続を行った関数と同じ戻値の型となる。</small></li>
|
|
820 <!--
|
|
821 <li class="incremental">上記のコードをGCC内で生成すると次のようなTreeができる。</li>
|
|
822 -->
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
824 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
825 <div class="slide">
|
80
|
826 <h1>CbCの実装:環境付き継続</h1>
|
|
827 <table border=1 width=100%>
|
|
828 <tr>
|
|
829 <td width=50%><small>生成されるTree</small></td>
|
|
830 <td width=50%><small>生成する為のコード</small></td>
|
|
831 </tr>
|
|
832 <tr class="srctr">
|
|
833 <td class="srctd">
|
|
834 <img src="./pix/STATEMENT_LIST_1.png" style="height: 10em;">
|
|
835 </td>
|
|
836 <td class="srctd">
|
|
837 <pre class="srcbox" style="width:25em;">
|
|
838
|
|
839 case RID_CbC_RET:
|
|
840 {
|
|
841 tree value, stmt, label, tlab, decl;
|
|
842 c_parser_consume_token (parser);
|
|
843
|
|
844 stmt = c_begin_stmt_expr ();
|
|
845 cbc_return_f = c_parser_peek_token (parser)->value;
|
|
846 location_t location = c_parser_peek_token (parser)->location;
|
|
847
|
|
848 /* create label. (__label__ _cbc_exit0;) */
|
|
849 label = get_identifier ("_cbc_exit0");
|
|
850 tlab = declare_label (label);
|
|
851 C_DECLARED_LABEL_FLAG (tlab) = 1;
|
|
852 add_stmt (build_stmt (location, DECL_EXPR, tlab));
|
|
853
|
|
854 /* declare retval. (int retval;) */
|
|
855 tree decl_cond =
|
|
856 build_decl (location, VAR_DECL, get_identifier ("retval"),
|
|
857 TREE_TYPE (TREE_TYPE (current_function_decl)));
|
|
858 TREE_STATIC (decl_cond) = 1;
|
|
859 TREE_USED (decl_cond) = 1;
|
|
860
|
|
861 /* Use thread-local */
|
|
862 DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
|
|
863 DECL_NONLOCAL (decl_cond) = 1;
|
|
864 add_stmt (build_stmt(location, DECL_EXPR, pushdecl (decl_cond)));
|
|
865
|
|
866 /* define nested function. */
|
|
867 decl =
|
|
868 cbc_finish_nested_function (location, label, decl_cond);
|
|
869 TREE_USED(decl) = 1;
|
|
870
|
|
871 /* define if-ed goto label and return statement. */
|
|
872 cbc_finish_labeled_goto (location, label, decl_cond);
|
|
873
|
|
874 /* get pointer to nested function. */
|
|
875 value = build_addr (decl , current_function_decl);
|
|
876 TREE_USED (current_function_decl) = 1;
|
|
877 SET_EXPR_LOCATION (value, location);
|
|
878 add_stmt (value);
|
|
879
|
|
880 TREE_SIDE_EFFECTS (stmt) = 1;
|
|
881 expr.value = c_finish_stmt_expr (location, stmt);
|
|
882 expr.original_code = ERROR_MARK;
|
|
883 }
|
|
884 </pre>
|
|
885 </td>
|
|
886 </tr>
|
|
887 </table>
|
|
888 <!--
|
|
889 <small>
|
|
890 <pre>
|
|
891 ({
|
|
892 __label__ _cbc_exit0;
|
|
893 static int retval;
|
|
894 void _cbc_internal_return(int retval_, void *_envp){
|
|
895 retval = retval_;
|
|
896 goto _cbc_exit0; }
|
|
897 if (0) { _cbc_exit0:
|
|
898 return retval; }
|
|
899 _cbc_internal_return;
|
|
900 }),
|
|
901 </pre>
|
|
902 </small>
|
|
903 -->
|
|
904 </div>
|
|
905 <!-- PAGE -->
|
|
906 <div class="slide">
|
|
907 <h1>環境付き継続:実装の問題</h1>
|
|
908 <li>重要な部分</li>
|
|
909 <ul>
|
|
910 <li>リターンするretval変数のメモリ確保</li>
|
|
911 </ul>
|
|
912 <li>次の方法が考えられる。</li>
|
|
913 <ul>
|
|
914 <li>クロージャでの確保</li>
|
|
915 <li>staticでの確保</li>
|
|
916 <li>setjmpを用いての実装</li>
|
|
917 <li>static thread local storage(tls)を用いての確保</li>
|
|
918 <li>戻り値を入れるレジスタを明示的に指定</li>
|
|
919 </ul>
|
|
920 </div>
|
|
921 <!-- PAGE -->
|
|
922 <div class="slide">
|
|
923 <h1>環境付き継続:実装の問題</h1>
|
|
924 <ul>
|
|
925 <li>クロージャでの実装の問題点:</li>
|
|
926 <!-- <ul><li>クロージャにしてスタックに値を確保する。</li></ul> -->
|
|
927 <ul>
|
|
928 <li >CbCでは継続によりスタックの値は破棄されていく。</li>
|
|
929 <li >クロージャにしたコードが破棄される可能性がある。</li>
|
|
930 </ul>
|
|
931
|
|
932 <li>staticでの実装の問題点:</li>
|
|
933 <!-- <ul><li>静的に値を確保することでスタック破棄の影響を受けない。</li></ul> -->
|
|
934 <ul>
|
|
935 <li >マルチスレッドのプログラムに対応できない。</li>
|
|
936 <li >値を返し切る前に別スレッドによって値が書き換えられる可能性がある。</li>
|
|
937 </ul>
|
|
938
|
|
939 <li>setjmpでの実装</li>
|
|
940 <ul>
|
|
941 <li>setjmpを行うTreeを生成するのが少し手間になる。</li>
|
|
942 <li>int型の戻値しか得られない。</li>
|
|
943 </ul>
|
|
944 </ul>
|
|
945 </div>
|
|
946 <!-- PAGE -->
|
|
947 <div class="slide">
|
|
948 <h1>環境付き継続:実装の問題</h1>
|
|
949 <ul>
|
|
950 <li>static tlsでの実装</li>
|
|
951 <!-- <ul> <li>スレッド毎に静的に値を確保する。</li></ul>-->
|
|
952 <ul>
|
|
953 <li>現在はこの方法で実装を行なっている。</li>
|
|
954 <li>しかし、最適化にかけると正しい値が返ってこない。
|
|
955 <br>(最適化によりコードが削除されている...?)</li>
|
|
956 </ul>
|
|
957 <li>戻値を入れるレジスタを明示的に指定する。</li>
|
|
958 <ul>
|
|
959 <li>まだ実装を試していない。</li>
|
|
960 </ul>
|
|
961 </ul>
|
|
962 </div>
|
|
963 <!-- PAGE -->
|
|
964 <div class="slide">
|
|
965 <h1>Micro-Cとの比較</h1>
|
|
966 <li>Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度</li>
|
|
967 <table width=100% class="center">
|
|
968 <td>
|
|
969 <img src="./pix/mac_conv.png">
|
|
970 </td>
|
|
971 <td>
|
|
972 <img src="./pix/linux_conv.png">
|
|
973 </td>
|
|
974 </table>
|
|
975 <li>GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。
|
|
976 その為に明らかに遅くなっていることが分かる。</li>
|
|
977 <li>だがGCCの最適化有りの場合はMicro-C版よりも早い。</li>
|
|
978 </div>
|
|
979 <!-- PAGE -->
|
|
980 <div class="slide">
|
|
981 <h1>まとめ</h1>
|
|
982 <ul>
|
|
983 <li>今回GCC版CbCコンパイラのアップデートを行った。</li>
|
|
984 <li>TCEにかかる判定の部分と環境付き継続の実装の修正を行った。
|
|
985 <br>おかげで、以前より楽な管理ができる実装にすることができた。</li>
|
|
986 <li>後は環境付き継続の最適化の問題の修正とselftypeの実装を行う。</li>
|
|
987 <li>全ての実装を終えたらGCC版CbCコンパイラの実装はアップデートを行なっていくだけとなる。</li>
|
|
988 </ul>
|
|
989 </div>
|
|
990 <!-- PAGE -->
|
|
991 <div class="slide">
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
992 <h1>今後の予定</h1>
|
80
|
993 <ul>
|
|
994 <li>CbCを用いたプログラムの作成</li>
|
|
995 <ul>
|
|
996 <li>CbCによるタスクマネージャの作成</li>
|
|
997 </ul>
|
|
998 <li>llvmへのCbCの実装</li>
|
|
999 </ul>
|
|
1000 <br>
|
|
1001 <h2 class="incremental" style="font-weight: bold;">ご清聴ありがとうございました。</h2>
|
|
1002 </div>
|
|
1003 <!-- PAGE -->
|
|
1004 <div class="slide">
|
|
1005 <h1>CbCの実装:TCE(末尾除去)の動作</h1>
|
|
1006 <li>スタック:呼び出し元関数と同じ範囲を使うことになる。</li>
|
|
1007 <table width=100% border=1>
|
|
1008 <td>
|
|
1009 <p class="center">
|
|
1010 <img src="./pix/tce.png" style="height: 6em;">
|
|
1011 </p>
|
|
1012 </td>
|
|
1013 <td>
|
|
1014 <ul>
|
|
1015 <li><small>func_bの引数はfunc_aのスタックに上書する</small></li>
|
|
1016 <li><small>func_bの為にスタックポインタは伸ばされない</small></li>
|
|
1017 </ul>
|
|
1018 </td>
|
|
1019 </table>
|
|
1020 <li>CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。</li>
|
|
1021 </div>
|
|
1022 <!-- PAGE -->
|
|
1023 <div class="slide">
|
|
1024 <h1>CbCの機能の拡張:__rectype の実装</h1>
|
|
1025 <ul>
|
|
1026 <li>通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。</li>
|
|
1027 <pre style="font-size:28px;">
|
|
1028 void factorial(int n, int result, void(*print)()){
|
|
1029 :
|
|
1030 (*print)(n,result,print,exit1, envp);
|
|
1031 }
|
|
1032 </pre>
|
|
1033 <li>そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。</li>
|
|
1034 <pre style="font-size:28px;">
|
|
1035 __code factorial(int n, int result, __rectype *print) {
|
|
1036 :
|
|
1037 goto (*print)(n,result,print,exit1, envp);
|
|
1038 }
|
|
1039 </pre>
|
|
1040 </ul>
|
|
1041 </div>
|
|
1042 <!-- PAGE -->
|
|
1043 <div class="slide">
|
|
1044 <h1>CbCの機能の拡張:selftype</h1>
|
|
1045 <h2>selftypeの実装</h2>
|
|
1046 <li>以下の宣言が行えるようにしたい。</li>
|
|
1047 <small>
|
|
1048 <pre>
|
|
1049 typedef sturct node {
|
|
1050 selftype *left;
|
|
1051 selftype *right;
|
|
1052 int num;
|
|
1053 }*NODE
|
|
1054 </pre>
|
|
1055 <p>selftype は struct node を指す。</p>
|
|
1056 </small>
|
|
1057 <ul>
|
|
1058 <li>上記の構文は実装を行う予定である。</li>
|
|
1059 </ul>
|
54
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1060 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1061 <!-- PAGE -->
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1062 </div>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1063 </body>
|
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1064 </html>
|