|
0
|
1 % File: main.tex
|
|
|
2 % Created: 日 3 23 18:00 PM 2008 J
|
|
2
|
3 % Last Change: 火 3 25 02:40 PM 2008 J
|
|
0
|
4 %
|
|
1
|
5 \documentclass[a4j,twocolumn,9pt]{jarticle}
|
|
0
|
6 \usepackage{main}
|
|
|
7 \usepackage{graphicx}
|
|
|
8 \usepackage{verbatim}
|
|
|
9 \usepackage{nonDefaultPackage/listings}
|
|
|
10
|
|
|
11
|
|
|
12 \jtitle{Continuation based CコンパイラのGCC-4.2による実装}
|
|
|
13 \etitle{The implementation of Continuation based C Compiler on GCC}
|
|
|
14 \jaffiliation{琉球大学理工学研究科情報工学専攻}
|
|
|
15 \eaffiliation{Information Engineering, University Of the Ryukyus}
|
|
|
16 \jauthor{与儀 健人 \hspace{2cm} 河野 真治}
|
|
|
17 \eauthor{KENT yogi \hspace{2cm} Shinji KONO}
|
|
|
18 \year{平成19年度}
|
|
|
19 \thesis{OS研究会}
|
|
|
20 %\logo{%\includegraphics[width=15em]{figures/u-ryukyu-Mark.eps}}
|
|
|
21
|
|
|
22 \jabstract{
|
|
|
23 当研究室ではContinuation based Cという言語を提案しており、
|
|
|
24 そのコンパイルにはこれまでMicro-Cをベースにした独自のコンパイラを使用していた。
|
|
|
25 また、GCCのTail call optimizationを用いた実装が可能である事を以前の論文で示した。
|
|
|
26 ここではGCC上に実際にCbC言語の実装し、その評価を行った。
|
|
|
27 この実装はアーキテクチャに依存しないので、
|
|
|
28 GCCが対応する全てのアーキテクチャ上でCbCが動く事になるはずであるが、
|
|
|
29 若干の問題があり、その点に付いても考察を行う。
|
|
|
30 }
|
|
|
31 \eabstract{
|
|
|
32 We are approach Continuation based C Language,
|
|
|
33 and have used Micro-C based Compiler that is developed by us to compile it.
|
|
|
34 This research, We are implement a compiler for CbC into GCC and
|
|
|
35 appraising it.
|
|
|
36 This implementation is supposed
|
|
|
37 to run on all archtectures that is supported by GCC,
|
|
|
38 but few problems are founded.
|
|
|
39 }
|
|
|
40
|
|
|
41
|
|
|
42 \renewcommand{\lstlistingname}{リスト}
|
|
|
43 \lstset{
|
|
|
44 language=C,%
|
|
|
45 stringstyle=\ttfamily,%
|
|
|
46 basicstyle=\small\ttfamily,%
|
|
|
47 commentstyle=\itshape,%
|
|
|
48 classoffset=1,%
|
|
|
49 keywordstyle=\bfseries,%
|
|
|
50 framesep=5pt,%
|
|
|
51 showstringspaces=false,%
|
|
|
52 %frame=tRBl,
|
|
|
53 %numbers=left,stepnumber=1,numberstyle=\footnotesize%
|
|
|
54 }%
|
|
|
55 \def\lstlistingname{リスト}
|
|
|
56 \def\lstlistlistingname{プログラムコード目次}
|
|
|
57
|
|
|
58
|
|
|
59
|
|
3
|
60 \renewcommand{\thepage}{--- \arabic{page} ---}
|
|
0
|
61 \begin{document}
|
|
|
62 \twocolumn[\maketitle]{}
|
|
|
63
|
|
|
64 \section{CbCについて}
|
|
1
|
65 Continuation based C (以下CbC) は当研究室が提案するアセンブラよりも上位で
|
|
|
66 Cよりも下位な記述言語である\cite{kono2}。
|
|
0
|
67 Cの仕様からループ制御や関数コールを取り除き、
|
|
|
68 継続(goto) や code segmentを導入している。
|
|
|
69 これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
|
|
|
70 ソースコードレベルで行うことができる。
|
|
|
71
|
|
|
72 図\ref{fig:continuation}はcode segment同士の関係を表したものである。
|
|
|
73 \begin{figure}[htpb]
|
|
|
74 \begin{center}
|
|
1
|
75 \includegraphics[width=.5\textwidth]{figures/continuation.eps}
|
|
0
|
76 \end{center}
|
|
|
77 \caption{code segment間の``継続''}
|
|
|
78 \label{fig:continuation}
|
|
|
79 \end{figure}%
|
|
|
80 code segment\verb|start|は実行を終えるとgotoによって
|
|
1
|
81 別のcode segment \verb|A|もしくは\verb|B|に実行を継続する。
|
|
0
|
82 また、\verb|A|から\verb|B|,再び\verb|A|の用に継続を繰り返すことも可能だ。
|
|
|
83 このように、code segmentからgotoを用いて別のcode segmentへ飛ぶ
|
|
|
84 構成はオートマトンと似た構造になっていることがわかる。
|
|
5
|
85
|
|
|
86 これらの特徴から、CbCは自身でスケジューラの記述ができ、
|
|
|
87 それにより並列処理や逐次処理をスムースに繋げることが出来る。
|
|
|
88 また、OperatingSystemの記述やハードウェアの記述が容易になる。
|
|
0
|
89
|
|
|
90 以下では実装に必要なCbCの構文、
|
|
|
91 code segmentの定義と継続(goto)について説明する。
|
|
|
92 \paragraph{code segment}
|
|
|
93 はCbCにおける最も基本的な処理単位である。
|
|
|
94 構文としては通常の関数と同じであるが、型は``\_\_code''となる。
|
|
|
95 ただし、code segmentは関数のようにリターンすることはないので、
|
|
|
96 これはcode segmentであることを示すフラグの様なものである。
|
|
|
97
|
|
|
98 code segmentの処理内容も通常の関数と同じように定義されるが、
|
|
|
99 Cと違いcode segmentではforやwhile, returnなどの構文は存在しない。
|
|
|
100 ループ等の制御は自分自身への再帰的な継続によって実現されることになる。
|
|
|
101
|
|
|
102 \paragraph{継続 (goto)}
|
|
|
103 はcode segment間の移動を表す。
|
|
|
104 構文としてはgotoをつかっているがCにおけるlabelへのgotoとは違い、
|
|
|
105 gotoの後ろに関数呼び出しの様な形をとる。
|
|
|
106 例として、あるcode segment \verb|cs|への継続は
|
|
|
107 \verb|goto cs(10, "test");|となる。
|
|
|
108 これにより、csに対して引数\verb|10|と\verb|"test"|を渡すことができる。
|
|
|
109 ただし関数コールとは違い、継続ではコールスタックの拡張を行わない。
|
|
|
110 代わりにgotoを発行したcode segmentの持つスタック自体に次のcode segment
|
|
|
111 の引数を書き込むことになる。また、returnアドレスのpushなども行わない。
|
|
|
112
|
|
1
|
113
|
|
0
|
114 \section{GCCの構成}
|
|
|
115 \subsection{GCCの基本構造}
|
|
|
116 GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
|
|
|
117 以下ではそのpassの中でも重要なものをその実行順に説明する。
|
|
|
118 \begin{description}
|
|
1
|
119 \item[parsing] パーサによってソースコードを解析する。
|
|
|
120 解析した結果はGeneric Treeと呼ばれるtree構造の構造体に格納される。
|
|
|
121 \item[gimplification] Generic TreeをもとにこれをGIMPLEに変換する。
|
|
|
122 \item[GIMPLE optimization] GIMPLEに対して最適化を行う。
|
|
|
123 \item[RTL generation] GIMPLEをもとにRTLを生成する。
|
|
|
124 \item[RTL optimization] RTLに対して最適化を行う。
|
|
|
125 \item[Output assembly] RTLをもとにターゲットマシンのアセンブリに変換する。
|
|
0
|
126 \end{description}
|
|
|
127 これらの処理は図\ref{fig:GCC-pass}のように表される。
|
|
|
128 \begin{figure}[htbp]
|
|
|
129 \begin{center}
|
|
1
|
130 \includegraphics[width=.5\textwidth]{figures/GCC-pass.eps}
|
|
0
|
131 \end{center}
|
|
|
132 \caption{GCCのpass}
|
|
|
133 \label{fig:GCC-pass}
|
|
|
134 \end{figure}
|
|
|
135 各passは通常は各々の関数毎に行われるものだが、
|
|
|
136 inline関数の処理や、関数間での最適化を行う場合には
|
|
|
137 一つのソースファイル毎に行われる。
|
|
|
138
|
|
5
|
139 \subsection{Tail call elimination}\label{sec:tailcall}
|
|
0
|
140 最適化のひとつである``Tail call elimination''は、
|
|
1
|
141 本研究におけるCbCコンパイラの実装に深く関わってくる。
|
|
0
|
142 本節ではこの最適化機構について詳しく説明する。
|
|
|
143
|
|
|
144 \subsubsection{Tail callの概要}
|
|
|
145 具体的に説明する。
|
|
|
146 まずmain関数から関数Aを呼び出していて、
|
|
|
147 関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える。
|
|
|
148 このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
|
|
|
149 そこで再びret命令をつかってmainに戻ることになる。
|
|
|
150 ``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
|
|
|
151 この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
|
|
|
152 \begin{figure}[htpb]
|
|
|
153 \begin{center}
|
|
|
154 \includegraphics[width=0.5\textwidth]{figures/GCC-TailCall.eps}
|
|
|
155 \end{center}
|
|
|
156 \caption{Tail call eliminationの例}
|
|
|
157 \label{fig:Tail call}
|
|
|
158 \end{figure}
|
|
|
159
|
|
|
160 次に``Tail call elimination''によって、
|
|
|
161 アセンブリレベルでどのようにコードが変わるのか、
|
|
|
162 スタックの変化も交えて見てみる。
|
|
|
163 この例では最も一般的に使われているi386形式のアセンブラを使用している。
|
|
|
164
|
|
|
165 図\ref{fig:Tail call}と同じように呼び出される関数main, A, Bを
|
|
|
166 リスト\ref{code:main A B}の様に定義する。
|
|
1
|
167 \begin{lstlisting}[caption=関数main\, A\, Bの例,label=code:main A B]
|
|
0
|
168 void B(int A, int A, int C){
|
|
|
169 return ;
|
|
|
170 }
|
|
|
171 void A(int a, int b, int c, int d){
|
|
|
172 return B(a, b, c+d);
|
|
|
173 }
|
|
|
174 int main(int argc, char **argv){
|
|
|
175 A(10, 20, 30, 40);
|
|
|
176 return 0;
|
|
|
177 }
|
|
1
|
178 \end{lstlisting}
|
|
0
|
179 これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
|
|
|
180 次のリスト\ref{code:compiled A}のようなコードが出力される。
|
|
|
181 (ここではTailcall最適化が影響をあたえる関数Aのみをしめした)
|
|
|
182 \begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A]
|
|
|
183 A:
|
|
|
184 pushl %ebp
|
|
|
185 movl %esp, %ebp
|
|
|
186 subl $24, %esp
|
|
|
187 movl 20(%ebp), %eax
|
|
|
188 addl 16(%ebp), %eax
|
|
|
189 movl %eax, 8(%esp)
|
|
|
190 movl 12(%ebp), %eax
|
|
|
191 movl %eax, 4(%esp)
|
|
|
192 movl 8(%ebp), %eax
|
|
|
193 movl %eax, (%esp)
|
|
|
194 call B
|
|
|
195 leave
|
|
|
196 ret
|
|
|
197 .size A, .-A
|
|
|
198 \end{lstlisting}
|
|
|
199 Tail callをしない場合はAのスタック領域の上にBのスタック領域が確保され、
|
|
|
200 Bが終了するとそれが破棄される形になる。
|
|
|
201
|
|
|
202 次にTail call eliminationが行われた場合の
|
|
|
203 コンパイル結果をリスト\ref{code:tailcalled A}に示す。
|
|
|
204 \begin{center}
|
|
|
205 \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A]
|
|
|
206 A:
|
|
|
207 pushl %ebp
|
|
|
208 movl %esp, %ebp
|
|
|
209 movl 20(%ebp), %eax
|
|
|
210 addl %eax, 16(%ebp)
|
|
|
211 popl %ebp
|
|
|
212 jmp B
|
|
|
213 .size A, .-A
|
|
|
214 \end{lstlisting}
|
|
|
215 \end{center}
|
|
|
216 \verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。
|
|
|
217 ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に
|
|
|
218 Bのための引数を書き込んでいることが分かる。
|
|
|
219 ただし、変数aとbは書き込む位置も値も変わらないので触れられていない。
|
|
|
220
|
|
|
221 \subsubsection{Tail call時のスタック}
|
|
|
222 このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
|
|
|
223 \begin{figure}[htpb]
|
|
|
224 \begin{center}
|
|
1
|
225 \includegraphics[width=.5\textwidth]{figures/stack-tailcall.eps}
|
|
0
|
226 \end{center}
|
|
1
|
227 \caption{関数AからBを呼び出す時のスタックの様子}
|
|
0
|
228 \label{fig:stack-tailcall}
|
|
|
229 \end{figure}
|
|
|
230 図\ref{fig:stack-tailcall}の各ステップは次のような状態を表している。
|
|
|
231 \begin{description}
|
|
|
232 \item[(a)] mainからAが呼ばれた直後の状態。espは引数のトップをさしてるが、
|
|
|
233 ebpはmainの引数をさしたまま
|
|
|
234 \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
|
|
|
235 \item[(c)] A自身のスタックフレームにB用の引数をつめる。
|
|
|
236 \item[(d)] ebpを元に戻す。その後関数Bにjump。
|
|
|
237 \end{description}
|
|
|
238 (a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
|
|
|
239 通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
|
|
|
240 しかし、関数AのTail call elimination後のコードを見ても分かる通り、
|
|
|
241 無駄な処理が少なくなっていることが分かる。
|
|
|
242 これがTail call eliminationにおける最適化の主な効果である。
|
|
|
243 最大の効果が得られるのは、caller関数が持っている引数を
|
|
|
244 callee関数に直接渡す場合である。
|
|
|
245 この時はスタック操作は全く必要なく、単にjump命令のみになる。
|
|
|
246
|
|
|
247 \subsection{Tail callの条件}
|
|
|
248 Tail callが可能かどうかの条件についてここで考察する。
|
|
1
|
249 必要に応じて前節の図\ref{fig:stack-tailcall}と、リスト\ref{code:main A B}
|
|
0
|
250 を説明に用いるので参考にしていただきたい。
|
|
|
251
|
|
|
252 まず最初の条件として、
|
|
|
253 ``関数コールがreturnの直前にある''ということは自明だろう。
|
|
|
254 また、これに関連して``関数の返す型がcallerとcalleeで一致している''
|
|
|
255 ことが必要となる。
|
|
|
256
|
|
1
|
257 図の(c)にてcallee関数Bのための引数をスタックに上書きしているが、
|
|
0
|
258 この領域はAのためのスタックフレームであることは説明した。
|
|
|
259 ここでもしBの引数が5つ以上あったらどうなるだろうか?
|
|
|
260 図を見て分かる通り、mainのスタックまで書きつぶすことになってしまう。
|
|
|
261 このことから``caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい''
|
|
|
262 という条件が必要だと分かる。
|
|
|
263
|
|
|
264 最後にcallee用の引数を格納する順番が問題になる。
|
|
|
265 通常、引数は関数定義の右から順にスタックにつめられる。
|
|
|
266 例えば図\ref{code:main A B}のコードにおいて、AからBの呼び出しが
|
|
|
267 \verb|B(c, b, c+d)|となっていたらどうだろうか?
|
|
|
268 最初に\verb|c+d|の書き込みによって変数cは上書きされてしまう。
|
|
|
269 そのため、最後に書き込む引数cは上書きされたc+dが使われ、
|
|
|
270 実行結果はまったく違うものになってしまうだろう。
|
|
|
271 よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
|
|
|
272 という条件も必要となる。
|
|
|
273
|
|
|
274 他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
|
|
|
275 \begin{itemize}
|
|
|
276 \item 関数コールがreturnの直前にある
|
|
|
277 \item 関数の返す型がcallerとcalleeで一致している
|
|
|
278 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
|
|
|
279 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
|
|
|
280 \end{itemize}
|
|
|
281
|
|
|
282 CbCコンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。
|
|
|
283
|
|
|
284
|
|
|
285
|
|
|
286 \section{実装}
|
|
|
287 GCCへのCbCのコンパイル機能の実装を行う。
|
|
|
288 実装における最大の問題はgoto文でのcode segmentへのjump
|
|
|
289 の際のスタックフレームの状態をどう扱うかである。
|
|
|
290 先に述べたようにcode segmentへ飛ぶ時は Tail call を使用するのだが、
|
|
|
291 その条件としてcaller関数の引数サイズはcallee関数と同じか
|
|
|
292 より大きくなければならない。
|
|
|
293
|
|
|
294 これを解決するために、この実装ではcode segmentの
|
|
|
295 引数サイズを一定にすることにした。
|
|
|
296 どのようなcode segmentを定義してもスタックは一定に保たれる。
|
|
|
297
|
|
|
298 以下の節ではそれぞれの行程について簡単に説明する。
|
|
|
299
|
|
|
300 \subsection{\_\_code基本型の追加とパース}
|
|
|
301 まず最初に必要となるのが``\_\_code''という予約語を定義することである。
|
|
3
|
302 Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されており、
|
|
|
303 ここに``\_\_code''を定義することで、Tokenizerから
|
|
0
|
304 それを予約語として認識できるようになる。
|
|
|
305
|
|
|
306 もう一つ必要なものが、\_\_code型であることを示すidである。
|
|
|
307 これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
|
|
|
308 データを保持する \verb|c_declapecs|構造体で使用される。
|
|
|
309 void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
|
|
3
|
310 これは gcc/c-tree.h にて定義されており、ここに\verb|cts_CbC_code|を追加する。
|
|
|
311
|
|
0
|
312 以上により、\_\_codeをパースする準備ができた。
|
|
|
313 実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
|
|
|
314 \verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
|
|
|
315 \verb|declspecs_add_type()|関数に統一されている。
|
|
|
316 この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
|
|
|
317 以下のようになる。
|
|
|
318 \begin{lstlisting}[caption=declspecs\_add\_type関数,label=code:declspecs_add_type]
|
|
|
319 case RID_CbC_CODE:
|
|
|
320 if (specs->long_p)
|
|
2
|
321 error ("both %<long%> and %<void ..)
|
|
0
|
322 else if (specs->signed_p)
|
|
2
|
323 error ("both %<signed%> and %<vo ..)
|
|
1
|
324 :
|
|
2
|
325 else
|
|
0
|
326 specs->typespec_word = cts_CbC_code;
|
|
2
|
327 return specs;
|
|
0
|
328 \end{lstlisting}
|
|
|
329 これは実際には\verb|case RID_VOID|とほぼ同じである。
|
|
|
330 違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。
|
|
|
331 同様にcode segmentの型はほぼ、void型と同じように扱うことになる。
|
|
|
332
|
|
|
333 gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
|
|
|
334 パースされた型を決定し、その分のちいさなtreeを生成する関数である。
|
|
|
335 treeにする際はcode segmentは全てvoidと見なされるようにすることになっている。
|
|
|
336 よってここで生成するtreeはvoidにしなければならない。
|
|
|
337 \begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs]
|
|
|
338 case cts_void:
|
|
|
339 case cts_CbC_code:
|
|
|
340 specs->type = void_type_node;
|
|
|
341 break;
|
|
|
342 \end{lstlisting}
|
|
|
343 これで\_\_codeによる型がvoid型にマップされた。
|
|
|
344
|
|
|
345
|
|
1
|
346 \subsection{code segment のtree表現}
|
|
0
|
347 次に、関数と同じようにパースされるcode segmentのtreeを
|
|
|
348 後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
|
|
|
349 この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
|
|
|
350 具体的には以下の様な関数になる。
|
|
|
351 \begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment]
|
|
|
352 tree
|
|
2
|
353 build_code_segment_type(value_type ..)
|
|
0
|
354 {
|
|
1
|
355 tree t;
|
|
|
356 t = make_node (FUNCTION_TYPE);
|
|
|
357 TREE_TYPE (t) = value_type;
|
|
|
358 TYPE_ARG_TYPES (t) = arg_types;
|
|
0
|
359
|
|
1
|
360 CbC_IS_CODE_SEGMENT (t) = 1;
|
|
|
361 if (!COMPLETE_TYPE_P (t))
|
|
|
362 layout_type (t);
|
|
|
363 return t;
|
|
|
364 }
|
|
0
|
365 \end{lstlisting}
|
|
1
|
366 \verb|CbC_IS_CODE_SEGMENT|というマクロがcode segmentを示すフラグである。
|
|
0
|
367 この関数は通常のFUNCTION\_TYPEを作る \verb|build_function_type|と
|
|
|
368 ほぼ同じ構造になっているが、
|
|
|
369 このtreeをハッシュ表に登録しないところだけが違っている。
|
|
|
370
|
|
|
371 つづいてこの\verb|build_code_segment_type|を使用すべき関数、
|
|
|
372 \verb|grokdeclarator|を修正する。
|
|
|
373 この関数は今までパースしてきた情報の入った構造体、
|
|
|
374 \verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを
|
|
|
375 gcc/tree.c の関数を使って生成している。
|
|
|
376
|
|
|
377 この関数で\verb|build_function_type|関数を使用している箇所
|
|
|
378 3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。
|
|
|
379 これを、code segmentの場合には\verb|build_code_segment_type|を使うようにする。
|
|
|
380 \begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator]
|
|
2
|
381 if(typespec_word==cts_CbC_code)
|
|
|
382 type =build_code_segment_type(..);
|
|
1
|
383 else
|
|
2
|
384 type =build_function_type(..);
|
|
0
|
385 \end{lstlisting}
|
|
|
386 これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
|
|
|
387 code segmentかをチェックする時はtree typeに対して
|
|
|
388 \verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。
|
|
|
389
|
|
|
390
|
|
|
391 \subsection{goto のパース}
|
|
|
392 つづいてgoto文のパースが必要になる。
|
|
|
393 goto文は通常のCの構文にも存在するが、CbCではgotoトークンの後に
|
|
|
394 関数呼び出しと同じ構文がくる。
|
|
|
395
|
|
|
396 Cの関数定義をパースしているのは
|
|
|
397 \verb|c_parser_statement_after_labels|という関数である。
|
|
|
398 この関数内の巨大な switch文における\verb|case RID_GOTO:|
|
|
|
399 を修正することになる。
|
|
|
400 具体的な修正は以下のようになった。
|
|
|
401 \begin{lstlisting}[caption=goto文の構文解析,label=code:goto_parse]
|
|
2
|
402 c_parser_consume_token (parser);
|
|
|
403 if (c_parser_next_token_is(parser,..)
|
|
|
404 && _parser_peek_2nd_token(pars..))
|
|
|
405 {
|
|
|
406 stmt = c_finish_goto_label(..);
|
|
|
407 c_parser_consume_token (parser);
|
|
|
408 } else {
|
|
|
409 struct c_expr expr;
|
|
|
410 expr=c_parser_postfix_expression(..);
|
|
|
411 if(TREE_CODE(expr)==CALL_EXPR){
|
|
|
412 CbC_IS_CbC_GOTO(expr) = 1;
|
|
|
413 CALL_EXPR_TAILCALL(expr) = 1;
|
|
|
414 stmt = c_finish_return(expr);
|
|
|
415 } else
|
|
|
416 c_parser_error (parser, ..);
|
|
|
417 }
|
|
0
|
418 \end{lstlisting}
|
|
1
|
419 gotoトークンを読み込むと、次のトークンが識別子で、その次がセミコロンであれば
|
|
|
420 通常のCにおけるgotoと判定できる。
|
|
|
421 そうでなければCbCの継続である。
|
|
0
|
422
|
|
|
423 \subsection{expand\_callの分割}
|
|
1
|
424 ここではパーサによって生成されたtreeを元に、
|
|
0
|
425 RTLを生成する段階について説明する。
|
|
|
426
|
|
|
427 とはいうものの、実際にRTLをいじる必要があるのは
|
|
|
428 code segmentへのjumpのみである。
|
|
|
429 これはtree上ではTail callと認識されているので、
|
|
|
430 そのtreeからRTLに変換する関数\verb|expand_call|を修正することになる。
|
|
|
431
|
|
|
432 関数\verb|expand_call|は CALL\_EXPR treeをもとに
|
|
|
433 関数呼び出しの際のスタック領域確保、引数の格納、
|
|
|
434 関数へのcall命令の発行などを行うRTLを生成している。
|
|
|
435 しかしこの\verb|expand_call|は約1200行も存在し、
|
|
|
436 その大半はTail callが可能かの判定をしているにすぎない。
|
|
|
437 そこでこの実装ではCbCのgotoのためのRTLを生成する関数\verb|expand_cbc_goto|
|
|
|
438 を新たに作成した。
|
|
|
439
|
|
|
440 \subsection{expand\_cbc\_goto}
|
|
2
|
441 簡単に説明すると、\verb|expand_cbc_goto|は\verb|expand_call|での
|
|
|
442 Tail callの処理を可否判定無しで行うものとなる。
|
|
0
|
443 大まかな処理内容は以下の通り
|
|
|
444 \begin{enumerate}
|
|
|
445 \item スタックフレームのベースアドレスRTLを取得
|
|
|
446 \item 各引数の格納されるアドレスRTLを取得
|
|
|
447 \item 各引数の式を計算 (一時的にレジスタに格納)
|
|
3
|
448 \item オーバーラップする引数を一時に変数に格納\label{overlap}
|
|
0
|
449 \item 引数のスタックへの格納
|
|
|
450 \item call\_insn RTLの生成
|
|
|
451 \end{enumerate}
|
|
|
452
|
|
3
|
453 これらの処理はほぼ\verb|expand_call|の内容をそのまま利用できる。
|
|
|
454 ただし、\ref{overlap}のオーバーラップする引数がある場合のみ問題になる。
|
|
|
455 gotoの実装には\ref{sec:tailcall}節で説明したTail callを用いているため
|
|
|
456 引数の書き込み領域と読み込み領域が重なる場合がある。
|
|
|
457 本来この場合はTail call不能として通常の関数呼出が用いられるところであるが、
|
|
|
458 CbCではこれを強制しなければならない。
|
|
|
459 そのため、このように重なる場合は変数の内容を一時退避する必要がある。
|
|
|
460 次のリスト\ref{code:push_overlaps}がこの処理を書く引数に対して行っている。
|
|
0
|
461 \begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
|
|
3
|
462 push_overlaps(struct arg_data *args, int num_actuals){
|
|
|
463 int i;
|
|
|
464 for (i=0; i<num_actuals; i++)
|
|
|
465 {
|
|
|
466 int dst_offset;
|
|
|
467 int src_offset;
|
|
|
468 rtx temp;
|
|
|
469 if (/*args[i].stackはスタック外*/) continue;
|
|
|
470 if (/*args[i].valueはスタック外*/) continue;
|
|
|
471 temp =assign_temp(args[i].tree_value..);
|
|
|
472 if ( args[i].mode==BLKmode )
|
|
|
473 emit_block_move(temp,args[i].value..);
|
|
|
474 else
|
|
|
475 emit_move_insn(temp,args[i].value);
|
|
|
476 args[i].value = temp;
|
|
|
477 }
|
|
0
|
478 \end{lstlisting}
|
|
|
479
|
|
|
480 \section{評価}
|
|
1
|
481 今回実装できたGCCによるCbCコンパイラでベンチマークを行い、
|
|
|
482 Micro-Cとの比較を行った。
|
|
0
|
483
|
|
|
484 今回ベンチマークに使用したプログラムはこれまでもMicro-Cの測定に使われていた
|
|
3
|
485 テストルーチンで、普通のCのソースをプログラムでCbCに変換したものである。
|
|
0
|
486 引数に1を入れるとそれが変換されたCbCのコード、
|
|
|
487 引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
|
|
|
488 また、評価はia32アーキテクチャのFedora上で行った。
|
|
3
|
489 一番結果の良い引数2の場合のcode segmentをリスト\ref{code:bench}に示す。
|
|
|
490 \begin{lstlisting}[caption=bench,label=code:bench]
|
|
|
491 __code f2(int i,char *sp) {
|
|
|
492 int k,j;
|
|
|
493 k = 3+i;
|
|
|
494 goto g2(i,k,i+3,sp);
|
|
|
495 }
|
|
|
496 __code g2(int i,int k,int j,char *sp){
|
|
|
497 j = j+4;
|
|
|
498 goto h2(i,k+4+j,sp);
|
|
|
499 }
|
|
|
500 __code h2_1(int i,int k,int j,char *sp){
|
|
|
501 goto main_return2(i+j,sp);
|
|
|
502 }
|
|
|
503 __code h2(int i,int k,char *sp) {
|
|
|
504 goto h2_1(i,k,i+4,sp);
|
|
|
505 }
|
|
|
506 \end{lstlisting}
|
|
|
507 このベンチマークではCbCの継続と計算を交互に行っている。
|
|
0
|
508 測定結果は表\ref{tab:mc,gcc,compare}に示される。
|
|
|
509 \begin{table}[htpb]
|
|
|
510 \centering
|
|
|
511 \small
|
|
|
512 \begin{tabular}{|l|r|r|r|} \hline
|
|
|
513 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
|
|
|
514 Micro-C & 8.97 & 2.19 & 2.73 \\ \hline \hline
|
|
|
515 GCC & 4.87 & 3.08 & 3.65 \\ \hline
|
|
|
516 GCC (+omit) & 4.20 & 2.25 & 2.76 \\ \hline
|
|
|
517 GCC (+fast) & 3.44 & 1.76 & 2.34 \\ \hline \hline
|
|
|
518 \end{tabular}
|
|
|
519 \caption{Micro-C, GCCの実行速度比較 (単位 秒)}
|
|
|
520 \label{tab:mc,gcc,compare}
|
|
|
521 \end{table}
|
|
|
522
|
|
3
|
523 通常のTail call eliminationのみを有効にした場合の結果が2行目、
|
|
|
524 その他は次節で説明するオプションを付加したものである。
|
|
|
525 見てのとおり、手動で最適化された引数2,3の場合はオプションを加えなければ
|
|
|
526 Micro-Cの速度に及ばなかった。次節ではこの点について考察する。
|
|
|
527
|
|
|
528 \subsection{出力コード}
|
|
|
529 先ほどのリスト\ref{code:bench}のcode segment g2のみをMicro-Cでコンパイルした結果
|
|
|
530 をリスト\ref{code:bench_mc},
|
|
|
531 GCCのオプション無しによるコンパイル結果をリスト\ref{code:bench_gcc}に示す。
|
|
|
532 \begin{lstlisting}[caption=Micro-Cによる出力コード,label=code:bench_mc]
|
|
|
533 f2:
|
|
|
534 lea -_44(%ebp),%esp
|
|
|
535 movl $3,%eax
|
|
|
536 addl %esi,%eax
|
|
|
537 movl %eax,-28(%ebp)
|
|
|
538 movl %edi,-32(%ebp)
|
|
|
539 movl -28(%ebp),%edi
|
|
|
540 movl %esi,%eax
|
|
|
541 addl $3,%eax
|
|
|
542 movl %eax,-28(%ebp)
|
|
|
543 jmp g2
|
|
|
544 \end{lstlisting}
|
|
|
545 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc]
|
|
|
546 f2:
|
|
|
547 pushl %ebp
|
|
|
548 movl %esp, %ebp
|
|
|
549 movl 8(%ebp), %eax
|
|
|
550 movl 12(%ebp), %ecx
|
|
|
551 leal 3(%eax), %edx
|
|
|
552 movl %edx, 12(%ebp)
|
|
|
553 movl %edx, 16(%ebp)
|
|
|
554 movl %ecx, 20(%ebp)
|
|
|
555 popl %ebp
|
|
|
556 jmp g2
|
|
|
557 \end{lstlisting}
|
|
|
558 このとおり出力コードは10命令と、行数にはあまり差が無い。(他のsegmentも同様である)
|
|
|
559 しかしGCCの出力においては無駄なコードが混じっていることがわかるだろう。
|
|
|
560 \verb|pushl%ebp|と\verb|popl %ebp|である。
|
|
|
561 すべてのcode segmentにおいてこれと同じ命令が出てしまっているが、
|
|
|
562 これはTailcallを無理矢理適用したために出てきたコードである。
|
|
0
|
563
|
|
3
|
564 このような関数の最初と最後にある無駄なフレームポインタのpushを抑制するオプションが
|
|
5
|
565 -fomit-frame-pointerである。このオプションを付加するとリスト\ref{code:bench_gcc_omit}
|
|
3
|
566 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_omit]
|
|
|
567 f2:
|
|
|
568 movl 4(%esp), %eax
|
|
|
569 movl 8(%esp), %ecx
|
|
|
570 leal 3(%eax), %edx
|
|
|
571 movl %edx, 8(%esp)
|
|
|
572 movl %edx, 12(%esp)
|
|
|
573 movl %ecx, 16(%esp)
|
|
|
574 jmp g2
|
|
|
575 \end{lstlisting}
|
|
|
576 これによって一気に3命令減った。ベンチマークは表\ref{tab:mc,gcc,compare}の3行目、``GCC (+omit)''である。
|
|
|
577 しかし、(code segmentにもよるが)3/10命令減ったにもかかわらずMicro-Cとの速度差が
|
|
5
|
578 ほとんど無い。
|
|
0
|
579
|
|
5
|
580 リスト11をみるとMicro-Cでは引数の格納にレジスタ\%edi と
|
|
|
581 \%esi を用いる分、高速なコードを生成出来ていることが分かる。
|
|
|
582 この違いが命令数の差を埋めている。
|
|
3
|
583 GCCでも引数をレジスタに詰めることができるfastcall属性がある。
|
|
5
|
584 -fomit-frame-pointerに加えてfastcallを付加した結果をリスト\ref{code:bench_gcc_fast}
|
|
3
|
585 に示す。
|
|
|
586 \begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_fast]
|
|
|
587 f2:
|
|
|
588 movl %edx, %eax
|
|
|
589 leal 3(%ecx), %edx
|
|
|
590 movl %edx, 4(%esp)
|
|
|
591 movl %eax, 8(%esp)
|
|
|
592 jmp g2
|
|
|
593 \end{lstlisting}
|
|
|
594 命令数はさらに2命令減り、またメモリへのアクセスが減ったため
|
|
|
595 ベンチマーク結果(表\ref{tab:mc,gcc,compare}GCC (+fast))も大幅に改善した。
|
|
|
596
|
|
|
597 この評価結果から、GCCの最適化オプションを用いることで
|
|
|
598 CbCコードのさらなる高速化が可能であることが示された。
|
|
|
599 また、使用したベンチマークプログラムはCのコードをプログラムで
|
|
5
|
600 CbCに変換したものだが、これをCのままコンパイルすると
|
|
3
|
601 最適化をかけても約3.3秒かかる。
|
|
5
|
602 このように不要なスタック操作を減らすことによって、
|
|
|
603 C言語のみでは不可能な手動による最適化がCbCの利点としてあげられる。
|
|
3
|
604
|
|
0
|
605
|
|
|
606 \section{今後の課題と考察}
|
|
|
607 本研究の実装により、GCCを使ってCbCのソースコードを
|
|
|
608 コンパイルすることができるようになった。
|
|
|
609 また、これまでのMicro-Cベースのコンパイラではできなかった
|
|
|
610 最適化をGCC上で実行できるようになった。
|
|
|
611
|
|
4
|
612 しかしまだいくつかの問題が残っているので、
|
|
|
613 今後の課題と併せて、以下に簡単に説明する。
|
|
0
|
614 \begin{description}
|
|
2
|
615 \item[environment]
|
|
0
|
616 CbCにはもう一つ、environment付きの継続という構文が存在する。
|
|
|
617 これは関数からcode segmentにgotoした場合に関数の呼び出し元に戻る
|
|
|
618 ことを可能にするものだが、今回この実装は間に合わなかった。
|
|
|
619 \item[PPCのRTL変換不能] PowerPCアーキテクチャにおいて、code segment
|
|
|
620 のポインタ参照へgotoすることができない。
|
|
|
621 これはRTLレベルで対応されてないことが原因と思われる。
|
|
1
|
622 \item[オプションの強制] -O2オプションや、code segmentへのfasecall属性の付加
|
|
|
623 などを強制させる必要がある。
|
|
4
|
624 \item[SPU対応とGCCのversion] 実装できたversionは4.2.3である。
|
|
|
625 しかし現在SPUに対応したGCCは4.1までしかでていないうえに、
|
|
|
626 GCCのversion間の差異によって移植が難しくなっている。
|
|
0
|
627 \end{description}
|
|
4
|
628 ここで、二つ目のPowerPCへの対応が大きな問題となっている。
|
|
1
|
629 本来、このコンパイラはアーキテクチャに依存しない形で
|
|
4
|
630 実装したのが、実装後、PowerPCはTailcall eliminationにたいして一部対応してない
|
|
1
|
631 ことがわかった。
|
|
|
632 これはMachineDescriptionとよばれるRTLからアセンブラへの対応を表す
|
|
4
|
633 ファイルを記述することで対応させることができるはずだが、今回その実装には至らなかった。
|
|
0
|
634
|
|
4
|
635 またこれらに加えて、GCCはすでにC++や
|
|
|
636 Objective-C のコンパイルが可能である。これを活かし、
|
|
|
637 CbC++, もしくはObjective-CbC といった
|
|
5
|
638 既存の言語とCbC を組み合わせた言語に付いても今後実装していく。
|
|
|
639 %考えてみる価値があるだろう。
|
|
0
|
640
|
|
|
641
|
|
4
|
642 \small
|
|
0
|
643 \begin{thebibliography}{9}
|
|
|
644 \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''.
|
|
|
645 日本ソフトウェア科学会第19回大会論文集, Sep, 2002.
|
|
|
646 \bibitem{kono2} 河野真治. ``継続を持つCの下位言語によるシステム記述''.
|
|
|
647 日本ソフトウェア科学会第17回大会論文集, Sep, 2000.
|
|
4
|
648 \bibitem{c--} Simon Peyton Jones, Thomas Nordin, and Dino Oliva, ``C--: a portable assembly language''. Implementing Functional Languages, 1997.
|
|
0
|
649 \bibitem{gcc1} GNU Project - Free Software Foundation, GCC internal manual.
|
|
|
650 ``http://gcc.gnu.org/onlinedocs/gccint/''.
|
|
|
651 \end{thebibliography}
|
|
|
652
|
|
3
|
653 \renewcommand{\thepage}{--- \arabic{page} ---E}
|
|
0
|
654 \end{document}
|
|
|
655
|
