0
|
1 % File: main.tex
|
|
2 % Created: 日 6 01 18:00 PM 2008 J
|
|
3 % Last Change: 火 6 03 13:19 PM 2008 J
|
|
4 %
|
|
5 %\documentclass[a4j,twocolumn,9pt]{dsw-style/compsoft-dsw08}
|
|
6 \documentclass[ronbun,epsfig]{compsoft-dsw08}
|
|
7 %see /usr/local/ptetex3/share/texmf/ptex/platex209/jarticle.sty
|
|
8 \usepackage[dvipdfm]{graphicx}
|
|
9 \usepackage{verbatim}
|
|
10 \usepackage{nonDefaultPackage/listings}
|
|
11 \usepackage{url}
|
|
12
|
|
13 \title{組み込み向け低レベル言語 CbC の GCC による実装}
|
|
14 \author{与儀 健人 \and 河野 真治}
|
|
15
|
|
16 \renewcommand{\paragraph}[1]{ {\par\vspace{1em}\normalsize\bf #1} }
|
|
17 %\renewcommand{\thepage}{--- \arabic{page} ---}
|
|
18 %\renewcommand{\labelenumi}{\roman{enumi})}
|
|
19 \def\theenumi{\roman{enumi}}
|
|
20 \def\labelenumi{\theenumi)}
|
|
21 %\def\p@enumi{i)}
|
|
22 \renewcommand{\lstlistingname}{リスト}
|
|
23 \lstset{
|
|
24 language=C,%
|
|
25 stringstyle=\ttfamily,%
|
|
26 basicstyle=\small\ttfamily,%
|
|
27 commentstyle=\itshape,%
|
|
28 classoffset=1,%
|
|
29 keywordstyle=\bfseries,%
|
|
30 framesep=5pt,%
|
|
31 showstringspaces=false,%
|
|
32 %frame=tRBl,
|
|
33 %numbers=left,stepnumber=1,numberstyle=\footnotesize%
|
|
34 }%
|
|
35 \def\lstlistingname{リスト}
|
|
36 \def\lstlistlistingname{プログラムコード目次}
|
|
37
|
|
38
|
|
39
|
|
40
|
|
41 \begin{document}
|
|
42 %\twocolumn[\maketitle]{}
|
|
43 \maketitle
|
|
44
|
2
|
45 \section{概要}
|
|
46 当研究室ではContinuation based C(以下CbC)という言語を提案しており、
|
|
47 そのコンパイルにはこれまでMicro-Cをベースにした独自のコンパイラを使用していた。
|
|
48 また、以前の論文で
|
|
49 GCCのTail call optimizationを用いてGCC上に実装が可能である事を示した。
|
|
50 ここではGCC上に実際にCbC言語の実装し、その評価を行った。
|
|
51 この実装はアーキテクチャに依存しないので、GCCが対応する全てのアーキテクチャ上でCbCが動く事になるはずであるが、若干の問題があり、その点に付いても考察を行う。
|
|
52
|
|
53
|
0
|
54 \section{CbCについて}\label{sec:CbC}
|
2
|
55 Continuation based Cは当研究室が提案するアセンブラよりも上位で
|
0
|
56 Cよりも下位な記述言語である\cite{kono2}。
|
|
57 Cの仕様からループ制御や関数コールを取り除き、
|
|
58 継続(goto) や コードセグメントを導入している。
|
|
59 これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
|
|
60 ソースコードレベルで行うことができる。
|
|
61
|
|
62 図\ref{fig:continuation}はコードセグメント同士の関係を表したものである。
|
|
63 \begin{figure}[htpb]
|
|
64 \begin{center}
|
|
65 \includegraphics[width=.45\textwidth,bb=0 0 351 202]{figures/continuation.pdf}
|
|
66 \end{center}
|
|
67 \caption{コードセグメント間の``継続''}
|
|
68 \label{fig:continuation}
|
|
69 \end{figure}%
|
|
70 コードセグメント\verb|start|は実行を終えるとgotoによって
|
|
71 別のコードセグメント \verb|A|もしくは\verb|B|に実行を継続する。
|
|
72 また、\verb|A|から\verb|B|,再び\verb|A|の用に継続を繰り返すことも可能だ。
|
|
73 このように、コードセグメントからgotoを用いて別のコードセグメントへ飛ぶ
|
|
74 構成はオートマトンと似た構造になっていることがわかる。
|
|
75
|
|
76 これらの特徴から、CbCは自身でスケジューラの記述ができ、
|
|
77 それにより並列処理や逐次処理をスムースに繋げることが出来る。
|
|
78 また、OperatingSystemの記述やハードウェアの記述に向いている。
|
|
79
|
|
80 以下では実装に必要なCbCの構文、
|
|
81 コードセグメントの定義と継続(goto)について説明する。
|
|
82 \paragraph{コードセグメント}
|
|
83 はCbCにおける最も基本的な処理単位である。
|
|
84 コードセグメントを定義する構文は通常の関数と同じであるが、型は``\_\_code''となる。
|
|
85 ただし、コードセグメントは関数のようにリターンすることはないので、
|
|
86 これはコードセグメントであることを示すフラグの様なものである。
|
|
87
|
|
88 コードセグメントの処理内容も通常の関数と同じように定義されるが、
|
|
89 Cと違いコードセグメントではforやwhile, returnなどの構文は存在しない。
|
|
90 ループ等の制御は自分自身への再帰的な継続によって実現されることになる。
|
|
91
|
|
92 \paragraph{継続 (goto)}
|
|
93 はコードセグメント間の移動を表す。
|
|
94 構文としてはgotoをつかっているがCにおけるlabelへのgotoとは違い、
|
|
95 gotoの後ろに関数呼び出しの様な形をとる。
|
|
96 例として、あるコードセグメント \verb|cs|への継続は
|
|
97 \verb|goto cs(10, "test");|となる。
|
|
98 これにより、csに対して引数\verb|10|と\verb|"test"|を渡すことができる。
|
|
99 ただし関数コールとは違い、継続ではコールスタックの拡張を行わない。
|
|
100 代わりにgotoを発行したコードセグメントの持つスタック自体に次のコードセグメント
|
|
101 の引数を書き込むことになる。また、returnアドレスのpushなども行わない。
|
|
102
|
2
|
103 \subsection{CbCの例文}
|
|
104 以上の2つの構文を使った例題をリスト\ref{code:cbc_example}に示す。
|
|
105 \begin{lstlisting}[caption=CbC 例,label=code:cbc_example]
|
|
106 __code while_cond(int total, int count){
|
|
107 if ( count <= 100 ){
|
|
108 goto while_process(total,count);
|
|
109 }else{
|
|
110 goto while_end(total);
|
|
111 }
|
|
112 }
|
|
113 __code while_process(int total,
|
|
114 int count){
|
|
115 /* some processes */
|
|
116 goto while_cond(total, count);
|
|
117 }
|
|
118 __code while_end(int total){
|
|
119 goto cs_exit(0);
|
|
120 }
|
|
121 \end{lstlisting}
|
|
122 これは単純なループ構造である。
|
|
123 まず\verb|while_cond|が実行されると、そこでは条件判定により
|
|
124 \verb|while_process|か\verb|while_end|に継続する。
|
|
125 \verb|while_process|では処理が終了すると再び\verb|while_cond|に
|
|
126 継続することでループが形成される。
|
|
127 このようにCbCではforやwhileを使用せずコードセグメントから
|
|
128 同じコードセグメントへ継続する形でループが表現される。
|
|
129
|
0
|
130
|
|
131 \section{GCCの構成}
|
|
132 今回の実装ではGCCのソースコードを修正することになる。
|
|
133 また、GCCの最適化処理の一つであるTail callがその実装に深く関わってくる\cite{kono1}。
|
|
134 この章ではGCCの基本的な動作について簡単に説明する。
|
|
135 \subsection{GCCの基本構造}
|
|
136 GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
|
|
137 以下ではそのpassの中でも重要なものをその実行順に説明する。
|
|
138 \begin{description}
|
|
139 \item[parsing] パーサによってソースコードを解析する。
|
|
140 解析した結果はGeneric Treeと呼ばれるtree構造の構造体に格納される。
|
|
141 \item[gimplification] Generic TreeをもとにこれをGIMPLEに変換する。
|
|
142 \item[GIMPLE optimization] GIMPLEに対して最適化を行う。
|
|
143 \item[RTL generation] GIMPLEをもとにRTLを生成する。
|
|
144 \item[RTL optimization] RTLに対して最適化を行う。
|
|
145 \item[Output assembly] RTLをもとにターゲットマシンのアセンブリに変換する。
|
|
146 \end{description}
|
|
147 これらの処理は図\ref{fig:GCC-pass}のように表される。
|
|
148 \begin{figure}[htbp]
|
|
149 \begin{center}
|
|
150 \includegraphics[width=.45\textwidth,bb=0 0 371 214]{figures/GCC-pass.pdf}
|
|
151 \end{center}
|
|
152 \caption{GCCのpass}
|
|
153 \label{fig:GCC-pass}
|
|
154 \end{figure}
|
|
155 各passは通常は各々の関数毎に行われるものだが、
|
|
156 inline関数の処理や、関数間での最適化を行う場合には
|
|
157 一つのソースファイル毎に行われる。
|
|
158
|
|
159 \subsection{Tail call elimination}\label{sec:tailcall}
|
|
160 最適化のひとつである``Tail call elimination''
|
|
161 \footnote{Tail call Optimizationと呼ばれたり、
|
|
162 単にTail callと呼ばれたり、呼称はさまざまである。}
|
|
163 は、
|
|
164 ``関数のreturnの前に別の関数呼び出しがある場合はcall命令でなくjump命令が
|
|
165 使える''というアイデアを元に設計されている。
|
|
166 この最適化は本研究におけるCbCコンパイラの実装に深く関わってくるので、
|
|
167 以下で詳しく説明する。
|
|
168
|
|
169 \subsubsection{Tail callの概要}\label{ssec:tailcall}
|
|
170 まずmain関数から関数Aを呼び出していて、
|
|
171 関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える
|
|
172 (図\ref{fig:Tail call}参照)。
|
|
173 このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
|
|
174 そこで再びret命令をつかってmainに戻ることになる。
|
|
175 ``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
|
|
176 この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
|
|
177 \begin{figure}[htpb]
|
|
178 \begin{center}
|
|
179 \includegraphics[width=.45\textwidth,bb=0 0 382 263]{figures/GCC-TailCall.pdf}
|
|
180 \end{center}
|
|
181 \caption{Tail call eliminationの例}
|
|
182 \label{fig:Tail call}
|
|
183 \end{figure}
|
|
184
|
|
185 次に``Tail call elimination''によって、
|
|
186 アセンブリレベルでどのようにコードが変わるのか、
|
|
187 スタックの変化も交えて見てみる。
|
|
188 この例では最も一般的に使われているi386形式のアセンブラを使用している。
|
|
189
|
|
190 図\ref{fig:Tail call}と同じように呼び出される関数main, A, Bを
|
|
191 リスト\ref{code:main A B}の様に定義する。
|
|
192 \begin{lstlisting}[caption=関数main\, A\, Bの例,label=code:main A B]
|
|
193 void B(int A, int A, int C){
|
|
194 /* what do you do? */
|
|
195 return ;
|
|
196 }
|
|
197 void A(int a, int b, int c, int d){
|
|
198 /* some processes.. */
|
|
199 return B(a, b, c+d);
|
|
200 }
|
|
201 int main(int argc, char **argv){
|
|
202 A(10, 20, 30, 40);
|
|
203 return 0;
|
|
204 }
|
|
205 \end{lstlisting}
|
|
206 これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
|
|
207 次のリスト\ref{code:compiled A}のようなコードが出力される。
|
|
208 ここではTailcall最適化が影響をあたえる関数Aのみをしめした。
|
|
209 また、出力アーキテクチャはi386である。
|
|
210 \begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A]
|
|
211 A:
|
|
212 pushl %ebp
|
|
213 movl %esp, %ebp
|
|
214 subl $24, %esp
|
|
215 movl 20(%ebp), %eax
|
|
216 addl 16(%ebp), %eax
|
|
217 movl %eax, 8(%esp)
|
|
218 movl 12(%ebp), %eax
|
|
219 movl %eax, 4(%esp)
|
|
220 movl 8(%ebp), %eax
|
|
221 movl %eax, (%esp)
|
|
222 call B
|
|
223 leave
|
|
224 ret
|
|
225 .size A, .-A
|
|
226 \end{lstlisting}
|
|
227 これを見ても分かる通り、
|
|
228 Tail callをしない場合はAのスタック領域の上にBのスタック領域が確保され、
|
|
229 Bが終了するとそれが破棄される形になる。
|
|
230
|
|
231 次にTail call eliminationが行われた場合の
|
|
232 コンパイル結果をリスト\ref{code:tailcalled A}に示す。
|
|
233 \begin{center}
|
|
234 \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A]
|
|
235 A:
|
|
236 pushl %ebp
|
|
237 movl %esp, %ebp
|
|
238 movl 20(%ebp), %eax
|
|
239 addl %eax, 16(%ebp)
|
|
240 popl %ebp
|
|
241 jmp B
|
|
242 .size A, .-A
|
|
243 \end{lstlisting}
|
|
244 \end{center}
|
|
245 \verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。
|
|
246 ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に
|
|
247 Bのための引数を上書きしていることが分かる。
|
|
248 ただし、変数aとbは書き込む位置も値も変わらないので触れられていない。
|
|
249 また、call命令を使わずにjmpでBに飛んでいる
|
|
250 (そのためリターンアドレスも確保してない)。
|
|
251 これにより、B側ではret命令を発効するとAに戻らず、Aの呼び出し側に直接戻ることになる。
|
|
252
|
|
253 \subsubsection{Tail call時のスタック}
|
|
254 このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
|
|
255 \begin{figure}[htpb]
|
|
256 \begin{center}
|
|
257 \includegraphics[width=.45\textwidth,bb=0 0 528 272]{figures/stack-tailcall.pdf}
|
|
258 \end{center}
|
|
259 \caption{関数AからBを呼び出す時のスタックの様子}
|
|
260 \label{fig:stack-tailcall}
|
|
261 \end{figure}
|
|
262 図\ref{fig:stack-tailcall}の各ステップは次のような状態を表している。
|
|
263 \begin{description}
|
|
264 \item[(a)] mainからAが呼ばれた直後の状態。espは引数のトップをさしてるが、
|
|
265 ebpはmainの引数をさしたまま
|
|
266 \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
|
|
267 \item[(c)] A自身のスタックフレームにB用の引数をつめる。
|
|
268 \item[(d)] ebpを元に戻す。その後関数Bにjump。
|
|
269 \end{description}
|
|
270 (a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
|
|
271 通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
|
|
272 しかし、関数AのTail call elimination後のコードを見ても分かる通り、
|
|
273 無駄な処理が少なくなっていることが分かる。
|
|
274 これがTail call eliminationにおける最適化の主な効果である。
|
|
275 最大の効果が得られるのは、caller関数が持っている引数を
|
|
276 callee関数に直接渡す場合である。
|
|
277 この時はスタック操作は全く必要なく、単にjump命令のみになる。
|
|
278
|
|
279 \subsection{Tail callの条件}\label{ssec:tailcallcond}
|
|
280 Tail callが可能かどうかの条件についてここで考察する。
|
|
281
|
|
282 まず最初の条件として、
|
|
283 ``関数コールがreturnの直前にある''ということは自明だろう。
|
|
284 また、これに関連して``関数の返す型がcallerとcalleeで一致している''
|
|
285 ことが必要となる。
|
|
286
|
|
287 図\ref{fig:stack-tailcall}の(c)にてcallee関数Bのための引数をスタックに上書きしているが、
|
|
288 この領域はAのためのスタックフレームであることは説明した。
|
|
289 ここでもしBの引数が5つ以上あったらどうなるだろうか?
|
|
290 図を見て分かる通り、mainのスタックまで書きつぶすことになってしまう。
|
|
291 このことから``caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい''
|
|
292 という条件が必要だと分かる。
|
|
293
|
|
294 最後にcallee用の引数を格納する順番が問題になる。
|
|
295 通常、引数は関数定義の右から順にスタックにつめられる。
|
|
296 例えば図\ref{code:main A B}のコードにおいて、AからBの呼び出しが
|
|
297 \verb|B(c, b, c+d)|となっていたらどうだろうか?
|
|
298 最初に\verb|c+d|の書き込みによって変数cは上書きされてしまう。
|
|
299 そのため、最後に書き込む引数cは上書きされたc+dが使われ、
|
|
300 実行結果はまったく違うものになってしまうだろう。
|
|
301 よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
|
|
302 という条件も必要となる。
|
|
303
|
|
304 他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
|
|
305 \begin{enumerate}
|
|
306 \item 関数コールがreturnの直前にある \label{i}
|
|
307 \item 関数の返す型がcallerとcalleeで一致している \label{ii}
|
|
308 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい \label{iii}
|
|
309 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない \label{iv}
|
|
310 \end{enumerate}
|
|
311
|
|
312 CbCコンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。
|
|
313
|
|
314
|
|
315
|
|
316 \section{実装}
|
|
317 次に、実際の実装方法を簡単に説明する。
|
2
|
318 今回実装したソースコードはSourceForge上の以下のURLにて公開されている。\\
|
0
|
319 \url{http://sourceforge.jp/projects/cbc/}
|
|
320
|
|
321 実装に置ける最大の問題はgoto文でのコードセグメントへのjump
|
|
322 の際にスタックフレームをどう扱うかということである。
|
|
323 \ref{sec:CbC}章にて説明した通り、CbCではコードセグメントへジャンプした後は
|
|
324 元のコードセグメントには戻らない。
|
|
325 ゆえに通常の関数コールと違い、スッタクを積む必要が無い。
|
|
326 この特性が\ref{ssec:tailcall}で説明したTail callの性質と似ていることを利用し、
|
|
327 ``コードセグメントへのgotoはすべてTail callに置き換える''という実装を行う。
|
|
328
|
|
329
|
|
330 \subsection{Tail call条件のパス}
|
|
331 上記のような実装を行う上で、\ref{ssec:tailcallcond}で説明したように、
|
|
332 Tail callの条件を満足させる必要がある。
|
|
333
|
|
334 条件の\ref{i}は簡単に実装できる。
|
|
335 例えば次のような継続文を考える。
|
|
336 \begin{verbatim}
|
|
337 goto cs(10, "test");
|
|
338 \end{verbatim}
|
|
339 この文を構文解析する際に次のような形に置き換えることになる。
|
|
340 \begin{verbatim}
|
|
341 cs(10, "test");
|
|
342 return;
|
|
343 \end{verbatim}
|
|
344 これによりGeneric Treeの段階では単純な関数呼び出しとなるが、
|
|
345 Tail callのフラグをたてることにより、RTL生成時には
|
|
346 jump命令に置き換えられる。
|
|
347
|
|
348 次に条件の\ref{ii}だが、これは``\_\_code''を型に持つものは
|
|
349 すべてvoid型に置き換えることで対応できる。
|
|
350 すなわちコードセグメントの継続はvoid型関数へのTail callとなる。
|
|
351
|
|
352 条件\ref{iii}が最大の問題となる。
|
|
353 もしより大きい引数サイズのコードセグメントにTail callすると、
|
|
354 直前の呼び出した関数スタックを書きつぶしてしまう。最悪Segmentation faultとなる。
|
|
355 今回はこの解決方法として、すべてのコードセグメントでは引数スタックを
|
|
356 一定量とした。
|
|
357 ゆえにこのサイズ以上の引数を持つことはできないが、
|
|
358 これは通常のプログラミングでは問題にならない程度に大きい値にしている。
|
|
359 また、継続の際にはスタック拡張を行わないので、この一定量が大きくなっても
|
|
360 とくに実行速度等に影響はない。
|
|
361
|
|
362 最後に条件\ref{iv}だが、
|
|
363 これは上書きされうる引数がある場合には直前にそれを計算し一時変数に代入するように
|
|
364 修正した。
|
|
365
|
|
366 以上の内容に基づいて修正したソースコードの大半は
|
|
367 RTLを生成部となる。
|
|
368
|
|
369
|
|
370 \begin{comment}
|
|
371 GCCへのCbCのコンパイル機能の実装を行う。
|
|
372 実装における最大の問題はgoto文でのコードセグメントへのjump
|
|
373 の際のスタックフレームの状態をどう扱うかである。
|
|
374 先に述べたようにコードセグメントへ飛ぶ時は Tail call を使用するのだが、
|
|
375 その条件としてcaller関数の引数サイズはcallee関数と同じか
|
|
376 より大きくなければならない。
|
|
377
|
|
378 これを解決するために、この実装ではコードセグメントの
|
|
379 引数サイズを一定にすることにした。
|
|
380 どのようなコードセグメントを定義してもスタックは一定に保たれる。
|
|
381
|
|
382 以下の節ではそれぞれの行程について簡単に説明する。
|
|
383
|
|
384 \subsection{\_\_code基本型の追加とパース}
|
|
385 まず最初に必要となるのが``\_\_code''という予約語を定義することである。
|
|
386 Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されており、
|
|
387 ここに``\_\_code''を定義することで、Tokenizerから
|
|
388 それを予約語として認識できるようになる。
|
|
389
|
|
390 もう一つ必要なものが、\_\_code型であることを示すidである。
|
|
391 これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
|
|
392 データを保持する \verb|c_declapecs|構造体で使用される。
|
|
393 void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
|
|
394 これは gcc/c-tree.h にて定義されており、ここに\verb|cts_CbC_code|を追加する。
|
|
395
|
|
396 以上により、\_\_codeをパースする準備ができた。
|
|
397 実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
|
|
398 \verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
|
|
399 \verb|declspecs_add_type()|関数に統一されている。
|
|
400 この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
|
|
401 以下のようになる。
|
|
402 \begin{lstlisting}[caption=declspecs\_add\_type関数,label=code:declspecs_add_type]
|
|
403 case RID_CbC_CODE:
|
|
404 if (specs->long_p)
|
|
405 error ("both %<long%> and %<void ..)
|
|
406 else if (specs->signed_p)
|
|
407 error ("both %<signed%> and %<vo ..)
|
|
408 :
|
|
409 else
|
|
410 specs->typespec_word = cts_CbC_code;
|
|
411 return specs;
|
|
412 \end{lstlisting}
|
|
413 これは実際には\verb|case RID_VOID|とほぼ同じである。
|
|
414 違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。
|
|
415 同様にコードセグメントの型はほぼ、void型と同じように扱うことになる。
|
|
416
|
|
417 gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
|
|
418 パースされた型を決定し、その分のちいさなtreeを生成する関数である。
|
|
419 treeにする際はコードセグメントは全てvoidと見なされるようにすることになっている。
|
|
420 よってここで生成するtreeはvoidにしなければならない。
|
|
421 \begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs]
|
|
422 case cts_void:
|
|
423 case cts_CbC_code:
|
|
424 specs->type = void_type_node;
|
|
425 break;
|
|
426 \end{lstlisting}
|
|
427 これで\_\_codeによる型がvoid型にマップされた。
|
|
428
|
|
429
|
|
430 \subsection{コードセグメント のtree表現}
|
|
431 次に、関数と同じようにパースされるコードセグメントのtreeを
|
|
432 後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
|
|
433 この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
|
|
434 具体的には以下の様な関数になる。
|
|
435 \begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment]
|
|
436 tree
|
|
437 build_code_segment_type(value_type ..)
|
|
438 {
|
|
439 tree t;
|
|
440 t = make_node (FUNCTION_TYPE);
|
|
441 TREE_TYPE (t) = value_type;
|
|
442 TYPE_ARG_TYPES (t) = arg_types;
|
|
443
|
|
444 CbC_IS_CODE_SEGMENT (t) = 1;
|
|
445 if (!COMPLETE_TYPE_P (t))
|
|
446 layout_type (t);
|
|
447 return t;
|
|
448 }
|
|
449 \end{lstlisting}
|
|
450 \verb|CbC_IS_CODE_SEGMENT|というマクロがコードセグメントを示すフラグである。
|
|
451 この関数は通常のFUNCTION\_TYPEを作る \verb|build_function_type|と
|
|
452 ほぼ同じ構造になっているが、
|
|
453 このtreeをハッシュ表に登録しないところだけが違っている。
|
|
454
|
|
455 つづいてこの\verb|build_code_segment_type|を使用すべき関数、
|
|
456 \verb|grokdeclarator|を修正する。
|
|
457 この関数は今までパースしてきた情報の入った構造体、
|
|
458 \verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを
|
|
459 gcc/tree.c の関数を使って生成している。
|
|
460
|
|
461 この関数で\verb|build_function_type|関数を使用している箇所
|
|
462 3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。
|
|
463 これを、コードセグメントの場合には\verb|build_code_segment_type|を使うようにする。
|
|
464 \begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator]
|
|
465 if(typespec_word==cts_CbC_code)
|
|
466 type =build_code_segment_type(..);
|
|
467 else
|
|
468 type =build_function_type(..);
|
|
469 \end{lstlisting}
|
|
470 これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
|
|
471 コードセグメントかをチェックする時はtree typeに対して
|
|
472 \verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。
|
|
473
|
|
474
|
|
475 \subsection{goto のパース}
|
|
476 つづいてgoto文のパースが必要になる。
|
|
477 goto文は通常のCの構文にも存在するが、CbCではgotoトークンの後に
|
|
478 関数呼び出しと同じ構文がくる。
|
|
479
|
|
480 Cの関数定義をパースしているのは
|
|
481 \verb|c_parser_statement_after_labels|という関数である。
|
|
482 この関数内の巨大な switch文における\verb|case RID_GOTO:|
|
|
483 を修正することになる。
|
|
484 具体的な修正は以下のようになった。
|
|
485 \begin{lstlisting}[caption=goto文の構文解析,label=code:goto_parse]
|
|
486 c_parser_consume_token (parser);
|
|
487 if (c_parser_next_token_is(parser,..)
|
|
488 && _parser_peek_2nd_token(pars..))
|
|
489 {
|
|
490 stmt = c_finish_goto_label(..);
|
|
491 c_parser_consume_token (parser);
|
|
492 } else {
|
|
493 struct c_expr expr;
|
|
494 expr=c_parser_postfix_expression(..);
|
|
495 if(TREE_CODE(expr)==CALL_EXPR){
|
|
496 CbC_IS_CbC_GOTO(expr) = 1;
|
|
497 CALL_EXPR_TAILCALL(expr) = 1;
|
|
498 stmt = c_finish_return(expr);
|
|
499 } else
|
|
500 c_parser_error (parser, ..);
|
|
501 }
|
|
502 \end{lstlisting}
|
|
503 gotoトークンを読み込むと、次のトークンが識別子で、その次がセミコロンであれば
|
|
504 通常のCにおけるgotoと判定できる。
|
|
505 そうでなければCbCの継続である。
|
|
506
|
|
507 \subsection{expand\_callの分割}
|
|
508 ここではパーサによって生成されたtreeを元に、
|
|
509 RTLを生成する段階について説明する。
|
|
510
|
|
511 とはいうものの、実際にRTLをいじる必要があるのは
|
|
512 コードセグメントへのjumpのみである。
|
|
513 これはtree上ではTail callと認識されているので、
|
|
514 そのtreeからRTLに変換する関数\verb|expand_call|を修正することになる。
|
|
515
|
|
516 関数\verb|expand_call|は CALL\_EXPR treeをもとに
|
|
517 関数呼び出しの際のスタック領域確保、引数の格納、
|
|
518 関数へのcall命令の発行などを行うRTLを生成している。
|
|
519 しかしこの\verb|expand_call|は約1200行も存在し、
|
|
520 その大半はTail callが可能かの判定をしているにすぎない。
|
|
521 そこでこの実装ではCbCのgotoのためのRTLを生成する関数\verb|expand_cbc_goto|
|
|
522 を新たに作成した。
|
|
523
|
|
524 \subsection{expand\_cbc\_goto}
|
|
525 簡単に説明すると、\verb|expand_cbc_goto|は\verb|expand_call|での
|
|
526 Tail callの処理を可否判定無しで行うものとなる。
|
|
527 大まかな処理内容は以下の通り
|
|
528 \begin{enumerate}
|
|
529 \item スタックフレームのベースアドレスRTLを取得
|
|
530 \item 各引数の格納されるアドレスRTLを取得
|
|
531 \item 各引数の式を計算 (一時的にレジスタに格納)
|
|
532 \item オーバーラップする引数を一時に変数に格納\label{overlap}
|
|
533 \item 引数のスタックへの格納
|
|
534 \item call\_insn RTLの生成
|
|
535 \end{enumerate}
|
|
536
|
|
537 これらの処理はほぼ\verb|expand_call|の内容をそのまま利用できる。
|
|
538 ただし、\ref{overlap}のオーバーラップする引数がある場合のみ問題になる。
|
|
539 gotoの実装には\ref{sec:tailcall}節で説明したTail callを用いているため
|
|
540 引数の書き込み領域と読み込み領域が重なる場合がある。
|
|
541 本来この場合はTail call不能として通常の関数呼出が用いられるところであるが、
|
|
542 CbCではこれを強制しなければならない。
|
|
543 そのため、このように重なる場合は変数の内容を一時退避する必要がある。
|
|
544 次のリスト\ref{code:push_overlaps}がこの処理を書く引数に対して行っている。
|
|
545 \begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
|
|
546 push_overlaps(struct arg_data *args, int num_actuals){
|
|
547 int i;
|
|
548 for (i=0; i<num_actuals; i++)
|
|
549 {
|
|
550 int dst_offset;
|
|
551 int src_offset;
|
|
552 rtx temp;
|
|
553 if (/*args[i].stackはスタック外*/) continue;
|
|
554 if (/*args[i].valueはスタック外*/) continue;
|
|
555 temp =assign_temp(args[i].tree_value..);
|
|
556 if ( args[i].mode==BLKmode )
|
|
557 emit_block_move(temp,args[i].value..);
|
|
558 else
|
|
559 emit_move_insn(temp,args[i].value);
|
|
560 args[i].value = temp;
|
|
561 }
|
|
562 \end{lstlisting}
|
|
563
|
|
564 \end{comment}
|
|
565
|
2
|
566 \section{環境付き継続に関する考察}\label{sec:env}
|
0
|
567 また前説までにその実装方法を説明した。
|
|
568 しかしまだ実装されていない構文があるので、その実装方法に関して
|
|
569 ここで考察する。
|
|
570
|
|
571 \subsection{環境付き継続の概念}
|
|
572 環境付き継続は以下に示すように、継続文の後ろに``環境''の値を
|
|
573 明示したものである。
|
|
574 \begin{verbatim}
|
|
575 goto cs(10, 20), env;
|
|
576 \end{verbatim}
|
|
577 この構文を使用することでスタックフレームを別の(環境envが示す)
|
|
578 領域に切り替えたうえで継続を行うことができる。
|
|
579 例としてリスト\ref{code:envSwitch}の様なコードセグメントが考えられる。
|
|
580 \begin{lstlisting}[caption=環境付き継続 例,label=code:envSwitch]
|
|
581 __code envSwitch(int a, int b, double c)
|
|
582 {
|
|
583 void *stack;
|
|
584 if ((stack=malloc(STACKSIZE))==NULL)
|
|
585 goto error(no);
|
|
586
|
|
587 goto envCheck(10, 20), stack+OFFSET;
|
|
588 }
|
|
589 \end{lstlisting}
|
|
590 このコードセグメントenvSwitchではスタック領域をmallocで取得した領域に切り替えた
|
|
591 上でenvCheckに継続する
|
|
592 \footnote{この構文を使用し、複数のスタックを交互に切り替える等の
|
|
593 処理を行うことでタブロー法などの検証を行うのがCbCの目的でもある。}。
|
|
594
|
|
595 また、この構文を使ってコードセグメントを呼び出した関数に戻ることも可能となる。
|
|
596 それにはこの関数側でも若干の修正が必要で、\verb|__return, __environment|
|
|
597 という二つの定義済み変数を使用する。
|
|
598 これらはそれぞれコードセグメントから関数への戻り先とその時のスタックフレームの
|
|
599 位置を表している。
|
|
600 これらをリスト\ref{code:ret2func}の様に用いることで
|
|
601 \verb|env_func|を呼び出した関数まで戻ることができる。
|
|
602 また、\verb|env_code|環境付きgotoで与えている引数は\verb|env_func|の戻り値と
|
|
603 して扱われる。
|
|
604 \begin{lstlisting}[caption=呼び出し元の関数へのgoto例,label=code:ret2func]
|
|
605 __code env_code(int a, int b,
|
|
606 void *env, void *_ret)
|
|
607 {
|
|
608 __code (*ret)(int, int, int);
|
|
609 ret = _ret;
|
|
610 goto ret(20), env;
|
|
611 }
|
|
612 int env_func(int a, int b, double c)
|
|
613 {
|
|
614 goto env_code(20, 30,
|
|
615 __environment, __return);
|
|
616 /* unreachable */
|
|
617 }
|
|
618 \end{lstlisting}
|
|
619
|
|
620
|
|
621 \subsection{実装方法に関する考察}
|
|
622 環境付き継続の実装方法について考察を行う。
|
|
623 環境付き継続では通常の関数コールや継続と違い、スタックフレームを変更するため、
|
|
624 現在のスタックフレームの位置をさすレジスタを変更しなければならない。
|
|
625 理想的なリスト\ref{code:envSwitch}のコンパイル結果は以下のようになる。
|
|
626 \begin{lstlisting}[caption=環境付き継続 出力例,label=code:envSwitch_out]
|
|
627 movl $env, $eax
|
|
628 movl $10, 8(%eax)
|
|
629 movl $20, 12(%eax)
|
|
630 movl %eax, %ebp
|
|
631 jmp envCheck
|
|
632 \end{lstlisting}
|
|
633 この結果なら新たなスタックフレームenvの先に引数を格納し、
|
|
634 かつ\verb|%ebp|レジスタを置き換えた上でコードセグメントに継続している。
|
|
635
|
|
636 しかし、現在のTail callを用いた仕様ではいくつかの問題点がある。
|
|
637 一つは``Tail callはjmp命令の直前に必ず\verb|%ebp|を変更する''ということである。
|
|
638 さらに``環境''の値から引数を格納する位置までのオフセットを計算する必要がある。
|
|
639 これはGCCではRTLとして\verb|virtual_incoming_args_rtx|や\verb|hard_frame_pointer_rtx|
|
|
640 などの固定レジスタ値が用意されてるので、これを用いて計算できるだろう。
|
|
641 最後に、関数の呼び出し側に戻る時の\verb|__return|変数の定義が必要となる。
|
|
642 この変数はただ値をつくるだけでなく、この変数が使われている場合には
|
|
643 特殊なコードを生成する必要がある。
|
|
644
|
|
645
|
|
646
|
|
647 \section{評価}
|
|
648 今回、環境付き継続は実装には至らなかったが、
|
|
649 残りの部分は実装完了した。そこでベンチマークテストを行い、
|
|
650 Micro-Cとの比較を行った。
|
|
651
|
|
652 今回ベンチマークに使用したプログラムはこれまでもMicro-Cの測定に使われていた
|
|
653 テストルーチンで、普通のCのソースをプログラムでCbCに変換したものである。
|
|
654 引数に1を入れるとそれが変換されたCbCのコード、
|
|
655 引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
|
|
656 また、評価はia32アーキテクチャのFedora上で行った。
|
|
657 一番結果の良い引数2の場合のコードセグメントをリスト\ref{code:bench}に示す。
|
|
658 \begin{lstlisting}[caption=bench,label=code:bench]
|
|
659 __code f2(int i,char *sp) {
|
|
660 int k,j;
|
|
661 k = 3+i;
|
|
662 goto g2(i,k,i+3,sp);
|
|
663 }
|
|
664 __code g2(int i,int k,int j,char *sp){
|
|
665 j = j+4;
|
|
666 goto h2(i,k+4+j,sp);
|
|
667 }
|
|
668 __code h2_1(int i,int k,int j,char *sp){
|
|
669 goto main_return2(i+j,sp);
|
|
670 }
|
|
671 __code h2(int i,int k,char *sp) {
|
|
672 goto h2_1(i,k,i+4,sp);
|
|
673 }
|
|
674 \end{lstlisting}
|
|
675 このベンチマークではCbCの継続と計算を交互に行っている。
|
|
676 測定結果は表\ref{tab:mc,gcc,compare}に示される。
|
|
677 \begin{table}[htpb]
|
|
678 \centering
|
|
679 \small
|
|
680 \begin{tabular}{|l|r|r|r|} \hline
|
|
681 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
|
|
682 Micro-C & 8.97 & 2.19 & 2.73 \\ \hline \hline
|
|
683 GCC & 4.87 & 3.08 & 3.65 \\ \hline
|
|
684 GCC (+omit) & 4.20 & 2.25 & 2.76 \\ \hline
|
|
685 GCC (+fast) & 3.44 & 1.76 & 2.34 \\ \hline \hline
|
|
686 \end{tabular}
|
|
687 \caption{Micro-C, GCCの実行速度比較 (単位 秒)}
|
|
688 \label{tab:mc,gcc,compare}
|
|
689 \end{table}
|
|
690
|
|
691 通常のTail call eliminationのみを有効にした場合の結果が2行目、
|
|
692 その他は次節で説明するオプションを付加したものである。
|
|
693 見てのとおり、手動で最適化された引数2,3の場合はオプションを加えなければ
|
|
694 Micro-Cの速度に及ばなかった。次節ではこの点について考察する。
|
|
695
|
|
696 \subsection{出力コード}
|
|
697 先ほどのリスト\ref{code:bench}のコードセグメント g2のみをMicro-Cでコンパイルした結果
|
|
698 をリスト\ref{code:bench_mc},
|
|
699 GCCのオプション無しによるコンパイル結果をリスト\ref{code:bench_gcc}に示す。
|
|
700 \begin{lstlisting}[caption=Micro-Cによる出力コード,label=code:bench_mc]
|
|
701 f2:
|
|
702 lea -_44(%ebp),%esp
|
|
703 movl $3,%eax
|
|
704 addl %esi,%eax
|
|
705 movl %eax,-28(%ebp)
|
|
706 movl %edi,-32(%ebp)
|
|
707 movl -28(%ebp),%edi
|
|
708 movl %esi,%eax
|
|
709 addl $3,%eax
|
|
710 movl %eax,-28(%ebp)
|
|
711 jmp g2
|
|
712 \end{lstlisting}
|
|
713 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc]
|
|
714 f2:
|
|
715 pushl %ebp
|
|
716 movl %esp, %ebp
|
|
717 movl 8(%ebp), %eax
|
|
718 movl 12(%ebp), %ecx
|
|
719 leal 3(%eax), %edx
|
|
720 movl %edx, 12(%ebp)
|
|
721 movl %edx, 16(%ebp)
|
|
722 movl %ecx, 20(%ebp)
|
|
723 popl %ebp
|
|
724 jmp g2
|
|
725 \end{lstlisting}
|
|
726 このとおり出力コードは10命令と、行数にはあまり差が無い。(他のsegmentも同様である)
|
|
727 しかしGCCの出力においては無駄なコードが混じっていることがわかるだろう。
|
|
728 \verb|pushl%ebp|と\verb|popl %ebp|である。
|
|
729 すべてのコードセグメントにおいてこれと同じ命令が出てしまっているが、
|
|
730 これはTailcallを無理矢理適用したために出てきたコードである。
|
|
731
|
|
732 このような関数の最初と最後にある無駄なフレームポインタのpushを抑制するオプションが
|
|
733 -fomit-frame-pointerである。このオプションを付加するとリスト\ref{code:bench_gcc_omit}
|
|
734 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_omit]
|
|
735 f2:
|
|
736 movl 4(%esp), %eax
|
|
737 movl 8(%esp), %ecx
|
|
738 leal 3(%eax), %edx
|
|
739 movl %edx, 8(%esp)
|
|
740 movl %edx, 12(%esp)
|
|
741 movl %ecx, 16(%esp)
|
|
742 jmp g2
|
|
743 \end{lstlisting}
|
|
744 これによって一気に3命令減った。ベンチマークは表\ref{tab:mc,gcc,compare}の3行目、``GCC (+omit)''である。
|
|
745 しかし、(コードセグメントにもよるが)3/10命令減ったにもかかわらずMicro-Cとの速度差が
|
|
746 ほとんど無い。
|
|
747
|
3
|
748 リスト\ref{code:bench_mc}をみるとMicro-Cでは引数の格納にレジスタ\%edi と
|
0
|
749 \%esi を用いる分、高速なコードを生成出来ていることが分かる。
|
|
750 この違いが命令数の差を埋めている。
|
|
751 GCCでも引数をレジスタに詰めることができるfastcall属性がある。
|
|
752 -fomit-frame-pointerに加えてfastcallを付加した結果をリスト\ref{code:bench_gcc_fast}
|
|
753 に示す。
|
|
754 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_fast]
|
|
755 f2:
|
|
756 movl %edx, %eax
|
|
757 leal 3(%ecx), %edx
|
|
758 movl %edx, 4(%esp)
|
|
759 movl %eax, 8(%esp)
|
|
760 jmp g2
|
|
761 \end{lstlisting}
|
|
762 命令数はさらに2命令減り、またメモリへのアクセスが減ったため
|
|
763 ベンチマーク結果(表\ref{tab:mc,gcc,compare}GCC (+fast))も大幅に改善した。
|
|
764
|
|
765 この評価結果から、GCCの最適化オプションを用いることで
|
|
766 CbCコードのさらなる高速化が可能であることが示された。
|
|
767 また、使用したベンチマークプログラムはCのコードをプログラムで
|
|
768 CbCに変換したものだが、これをCのままコンパイルすると
|
|
769 最適化をかけても約3.3秒かかる。
|
|
770 このように不要なスタック操作を減らすことによって、
|
|
771 C言語のみでは不可能な手動による最適化がCbCの利点としてあげられる。
|
|
772
|
|
773
|
|
774
|
|
775
|
|
776
|
|
777 \section{まとめ}
|
|
778 本研究の実装により、GCCを使ってCbCのソースコードを
|
|
779 コンパイルすることができるようになった。
|
|
780 その結果、これまでのMicro-Cベースのコンパイラではできなかった
|
|
781 最適化をGCC上で実行できるようになり、CbCプログラムをより高速化することに成功した。
|
|
782 また、環境付き継続の実装方法に関して考察を行いその問題点を洗い出した。
|
|
783
|
2
|
784 今後は\ref{sec:env}で説明した様に環境付き継続の
|
0
|
785 実装が課題となる。
|
|
786 また、SPUアーキテクチャにGCCが対応してないという問題もある。
|
|
787 今回の実装の目的の一つとしてPS3上でCbCを動かしたいということがあったので、
|
|
788 この問題についてはPS3SDKとのマージも一つの手法として考えている。
|
|
789 これらに加えて、GCCはすでにC++やObjective-C のコンパイルが可能である。
|
|
790 これを活かし、CbC++, もしくはObjective-CbC といった
|
|
791 既存の言語とCbC を組み合わせた言語に付いても今後実装していく。
|
|
792
|
|
793
|
|
794 \begin{thebibliography}{9}
|
|
795 \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''.
|
|
796 日本ソフトウェア科学会第19回大会論文集, Sep, 2002.
|
|
797 \bibitem{kono2} 河野真治. ``継続を持つCの下位言語によるシステム記述''.
|
|
798 日本ソフトウェア科学会第17回大会論文集, Sep, 2000.
|
|
799 \bibitem{c--} Simon Peyton Jones, Thomas Nordin, and Dino Oliva, ``C--: a portable assembly language''. Implementing Functional Languages, 1997.
|
|
800 \bibitem{gcc1} GNU Project - Free Software Foundation, GCC internal manual.
|
|
801 \url{http://gcc.gnu.org/onlinedocs/gccint/}.
|
|
802 \end{thebibliography}
|
|
803
|
|
804 \end{document}
|
|
805
|