Mercurial > hg > Papers > 2010 > kent-master
annotate implementation.tex @ 7:8ef81ff8cb52
emended.
| author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 13:10:57 +0900 |
| parents | dfb89e32eea1 |
| children | 4b2af58b0302 |
| rev | line source |
|---|---|
| 2 | 1 \chapter{GCCにおける実装・改善} |
| 2 \label{chp:impl} | |
| 3 | |
| 7 | 4 この章では、GCCにおけるCbCコンパイラの実装方法の説明と、 \ref{chp:cbc} |
| 5 章で洗い出したGCCでの問題点の改善を行う。 | |
| 2 | 6 |
| 7 実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。 | |
| 3 | 8 このcc1はCからアセンブラへ変換を行う純粋なコンパイラとして実行されるプ |
| 9 ログラムである。このcc1をCbCの構文解析に対応させる。 | |
| 10 | |
| 2 | 11 過去の研究においてはGCCのバージョン4.2.3が用いられた。現在はGCCのリリ |
| 12 ースに並ぶ形で4.4.2（2010年1月時）を用いている。 | |
| 13 | |
| 14 \section{過去の研究における実装部分} | |
| 3 | 15 今回の改善においての予備知識として、過去の研究での実装部分であるコード |
| 2 | 16 セグメントと軽量継続がどのように実装されたかを簡単に説明する。 |
| 17 | |
| 18 \subsection{コードセグメントの実装} | |
| 19 | |
| 20 コードセグメント内部の実装は実際は単なる関数で良い。 | |
| 21 変更の必要があったのは関数の返り値に当たる部分である。コードセグメント | |
| 22 では返り値が存在しないのでここは``code''キーワードを入力できるようにす | |
| 23 る。このcodeは内部でvoid型に変換する。 | |
| 24 | |
| 25 GCC（及び一般的なコンパイラ）ではコンパイルに必要な全ての要素、変数や式 | |
| 4 | 26 、関数、構文などをすべて GIMPLEと呼ばれる構文木に保持している。コードセ |
| 27 グメントの構文木も関数とほぼ同じものを作成すれば良い。コード | |
| 28 \ref{code:build-code-segment}はその構文木を作成している部分である。 | |
| 2 | 29 |
| 30 \lstinputlisting | |
| 31 [caption=構文木生成(gcc/c-typeck.c),label=code:build-code-segment] | |
| 32 {sources/build-code-segment.cbc} | |
| 33 | |
| 34 \verb|build_code_segment_type|関数においてコードセグメントの構文木を作 | |
| 35 成している。内部の処理は\verb|build_function_type|とほぼ同じだが、関数 | |
| 36 のテーブルに登録せず、軽量継続の際にそれがコードセグメントであることを | |
| 37 示すためのフラグをセットしている。 | |
| 38 | |
| 39 | |
| 40 | |
| 3 | 41 \subsection{軽量継続の実装} \label{sec:impl-goto} |
| 2 | 42 |
| 43 軽量継続はGCCの末尾呼び出し最適化の機構を用いて実装する。 | |
| 44 | |
| 45 \subsubsection{末尾呼び出し最適化} | |
| 46 プログラム中、関数を呼び出すときには通常はスタックを積み上げ、現在の環 | |
| 47 境を保持した上で呼び出し先の処理を行う。これは元の関数に復帰して残りの | |
| 48 処理を続行する必要があるためである。しかし関数の最後、リターン直前に呼 | |
| 49 び出しを行う場合は環境を保持する必要がない（図\ref{fig:tailcall}参照） | |
| 50 。そのためスタックの状態を変更することなく呼び出すことができる。この最 | |
| 51 適化は末尾呼び出し最適化(tailcall)と呼ばれている。 | |
| 52 \begin{figure}[htpb] | |
| 53 \begin{center} | |
| 54 \includegraphics[width=.6\textwidth]{figures/tailcall.eps} | |
| 55 \end{center} | |
| 7 | 56 \caption{末尾呼び出し最適化が可能な関数funcYの例} |
| 2 | 57 \label{fig:tailcall} |
| 58 \end{figure} | |
| 59 | |
| 60 Scheme処理系では仕様上この最適化が必須となっているが、Cはそうではない。 | |
| 61 しかしGCCはこの最適化をデフォルトで行っている。 | |
| 62 | |
| 63 \subsubsection{軽量継続への摘要} | |
| 64 tailcallをコードセグメントの呼び出しに適用することで軽量継続が実装でき | |
| 65 る。具体的にはソースコード上にコード\ref{code:goto}のような式があった | |
| 7 | 66 場合に、これをコード\ref{code:ret-call}と同じように解釈する。 |
| 67 つまり、``goto''が前置する関数呼び出しは、必ず後ろに\verb|return;|がつ | |
| 68 くと解釈するのである。これでtailcallの条件ほぼ満たされる。 | |
| 69 | |
| 2 | 70 この構文解析はGCCのgcc/c-parser.c内で行う。 |
| 71 | |
| 72 \begin{minipage}[t]{.45\textwidth} | |
| 73 \lstinputlisting[caption=goto文の例,label=code:goto] | |
| 74 {sources/goto-expression.cbc} | |
| 75 \end{minipage} | |
| 76 \hfill | |
| 77 \begin{minipage}[t]{.45\textwidth} | |
| 78 \lstinputlisting[caption=構文木での解釈,label=code:ret-call] | |
| 79 {sources/ret-call.cbc} | |
| 80 \end{minipage} | |
| 81 | |
| 7 | 82 しかし構文木の変更だけではtailcallが行われるとは限らない。特にスタック |
| 83 の状態や変数の数、順番によっても最適化はカットされる場合がある。 | |
| 84 そのため最適化を判断する条件式を修正、また構文木から中間コードRTLを生 | |
| 2 | 85 成する部分でも修正が必要になる。 |
| 86 | |
| 7 | 87 \paragraph{expand-call}関数は関数を表す構文木からRTLを生成する処理であ |
| 88 る。この関数内では呼び出される関数のアドレスを取得するコードの生成、ス | |
| 89 タックへの引数をプッシュするコードの生成、引数のプッシュの度に | |
| 2 | 90 tailcallが可能かのチェックなどが行われている。 |
| 91 | |
| 92 ここでは以下の処理を追加することでtailcallカットの条件判断をパスしている。 | |
| 93 \begin{itemize} | |
| 94 \item スタックのサイズをごまかす | |
| 95 | |
| 96 tailcallは呼び出し元の全引数サイズが呼び出し先のそれより小さい場合 | |
| 4 | 97 には実行できない。そのため呼び出し元のコードセグメント全ての引数に |
| 98 もちいるスタックサイズを大きな値でごまかす。 | |
| 2 | 99 \item 並列代入 |
| 100 | |
| 101 \ref{sec:cbc-problem}で説明したような並列代入の必要な関数呼び出し | |
| 102 を行った場合はtailcallは実行されない。そのためここで並列代入が必要 | |
| 103 になる。 | |
| 104 \end{itemize} | |
| 105 | |
| 106 上記処理の追加により軽量継続が実装された。 | |
| 107 継続の際にコードセグメントに渡す引数は関数と同じようにスタック上に格納 | |
| 108 されるが、このスタックは拡張することはなく、図 | |
| 109 \ref{fig:gotostack}のように連続した継続の中でスタックポインタは常 | |
| 110 に同じアドレスを指し示す。（比較のため、図\ref{fig:funcstack}には関数 | |
| 111 呼び出しの際のスタックの状態を例示した） | |
| 112 \begin{figure}[htpb] | |
| 113 \begin{center} | |
| 114 \subfloat[][関数呼び出し]{\label{fig:funcstack} | |
| 115 \includegraphics[width=.6\textwidth]{figures/functionstack.eps}} | |
| 116 \subfloat[][軽量継続]{\label{fig:gotostack} | |
| 117 \includegraphics[width=.6\textwidth]{figures/interfacestack.eps}} | |
| 118 \end{center} | |
| 119 \caption{継続制御と関数呼び出しでのスタックの違い} | |
| 120 \end{figure} | |
| 121 | |
| 122 しかし並列代入の処理は構造体のようにオーバラップする引数に対しては対応 | |
| 123 しておらず、プログラムによっては引数がちゃんと渡されないなどのバグが生 | |
| 124 じていた。 | |
| 125 | |
| 126 | |
| 127 \section{問題点の改善} | |
| 128 ここから\ref{sec:cbc-problem}節で紹介した問題点について、本研究での改 | |
| 129 善点を説明する。 | |
| 130 | |
| 131 | |
| 132 \subsection{並列代入}\label{sec:impl-parallel} | |
| 133 | |
| 4 | 134 \ref{sec:gcc-problems}節で説明した様に、コードセグメントの受け取 |
| 2 | 135 った引数と継続の際に渡す引数の順序が変わる場合等に並列代入が必要になる。 |
| 7 | 136 過去の実装ではこの並列代入を、\verb|expand_call|という構文木から RTLを |
| 137 生成する処理の部分で行っていた。 | |
| 2 | 138 |
| 139 しかし実際にはGCCは元より並列代入を実装しているため、独自の実装は必要 | |
| 140 としない。また、この独自の実装にも問題があった。 | |
| 141 そのため独自の実装は廃止し、GCCの機能を利用することにする。 | |
| 142 | |
| 143 コード\ref{code:parallel-example2}は並列代入の必要な軽量継続の例である。 | |
| 144 \lstinputlisting | |
| 145 [caption=並列代入の必要な軽量継続の例,label=code:parallel-example2] | |
| 146 {sources/parallel-example.cbc} | |
| 147 | |
| 148 継続の引数は現在の引数と同じメモリに格納されるため、引数\verb|a|は | |
| 149 \verb|b|の位置に、引数\verb|b|は\verb|a|の位置に代入されることになる。 | |
| 150 この場合に並列代入を考慮せず、順に代入すると | |
| 151 \begin{verbatim} | |
| 152 a = b; | |
| 153 b = a; | |
| 154 \end{verbatim} | |
| 155 となり、両方が同じ値になってしまう。 | |
| 156 ただしこの例は極端に簡略化した例であり、この程度であればtailcallに問題 | |
| 157 はない。しかしより複雑な並列代入では同じ問題が現れる。特に、引数に含ま | |
| 158 れるコードセグメントポインタへ間接継続する場合には、ほぼ確実に失敗する。 | |
| 159 | |
| 160 この問題の回避策として単純にコード\ref{code:avoiding-parallel}の様に変 | |
| 161 数の値を一時変数に退避することが考えられる。 | |
| 162 | |
| 163 \lstinputlisting | |
| 164 [caption=引数の退避,label=code:avoiding-parallel] | |
| 165 {sources/avoiding-parallel.cbc} | |
| 166 | |
| 167 こうすることで引数が一時変数に確保され、その後そこからコピーする形で所 | |
| 168 定のメモリ位置に戻されるため問題が回避できる。今回の並列代入の改善では | |
| 169 この手法を用いる。 | |
| 170 | |
| 171 \subsubsection{問題点と最適化の期待} | |
| 172 この手法でどのように引数を入れ替えても正しく代入可能になる。ただし、一 | |
| 173 時変数の使用は処理速度に問題がある。特にレジスタの少ないアーキテクチャ | |
| 7 | 174 では一時変数の確保にメモリ上のスタックを用いるため、余計なメモリアクセ |
| 175 スや冗長な命令が増えてしまう。このため、この手法を実践したコードではそ | |
| 176 うでないコードに比べて若干の速度低下が見込まれる。 | |
| 2 | 177 |
| 178 その代わり、この速度低下はGCCのもつ最適化機構で回避され得るものである。 | |
| 179 GCCでは中間コード生成後、必要のない一時変数へのコピーなどは最適化によ | |
| 180 りカットされる。そのため、最適化を有効にした場合はこの処理速度の低下は | |
| 7 | 181 起きないと考えられる。この影響に関しては\ref{chp:eval}章にて検証する。 |
| 2 | 182 |
| 183 \subsubsection{一時変数への退避の実装} | |
| 184 | |
| 185 この手法の実装は、中間コード生成時ではなく構文木生成で可能である。 | |
| 186 tailcallの関数呼び出しを表す構文木の生成時に以下の処理を追加する。 | |
| 187 \begin{enumerate} | |
| 188 \item 関数呼び出しを表す構文木\verb|a|の取得 | |
| 189 \item \verb|a|から引数を表す構文木を取得、それぞれについて | |
| 190 \begin{enumerate} | |
| 191 \item 同じ型の名前なし一時変数を作成 | |
| 192 \item 引数の値を一時変数に代入 | |
| 193 \item 関数に渡す引数を一時変数に変更 | |
| 194 \end{enumerate} | |
| 195 \item 呼び出す関数がポインタだった場合 | |
| 7 | 196 \begin{enumerate} |
| 197 \item 関数と同じ型（関数ポインタ）の一時変数を作成 | |
| 198 \item 関数アドレスを一時変数に代入 | |
| 199 \item 呼び出す関数を一時変数に変更 | |
| 200 \end{enumerate} | |
| 2 | 201 \end{enumerate} |
| 202 | |
| 203 ここでは関数ポインタも引数と同じように扱い、一時変数に退避する。 | |
| 204 実際のプログラムはコード\ref{code:replace-args}の様になる。 | |
| 205 この関数\verb|cbc_replace_arguments|は関数呼び出し構文木を引数として受 | |
| 7 | 206 け取り、上記の処理を行う。引数として渡される\verb|tree call|がその構文 |
| 207 木である。 \verb|build_decl|は名無し一時変数の宣言、 | |
| 208 \verb|build_modify_expr|は一時変数への代入を行う構文木の生成をしている | |
| 209 。 | |
| 2 | 210 |
| 211 \lstinputlisting | |
| 212 [caption=上記の処理を行う関数,label=code:replace-args] | |
| 213 {sources/replace-args.c} | |
| 214 | |
| 7 | 215 ソースコードの構文解析時、軽量継続をパースしてその構文木を生成した際に |
| 216 、この関数\verb|cbc_replace_arguments|を実行することで、この軽量継続は | |
| 217 並列代入に対応できるようになった。 | |
| 2 | 218 |
| 219 | |
| 220 \subsection{環境付き継続} | |
| 221 | |
| 222 環境付き継続は過去の研究では実装されていなかった。 | |
| 223 これはCとの互換性のために必要な制御構造である。 | |
| 224 | |
| 225 環境付き継続には\ref{ssec:gotowithenv}で述べたように、\verb|__return| | |
| 226 という擬似変数を使う。この変数の値を継続先のコードセグメントに渡すこと | |
| 227 で、そのコードセグメントから関数の環境へ復帰することを可能にする。 | |
| 228 渡された\verb|__return|の値は、コードセグメント側からは他のコードセグ | |
| 3 | 229 メントと区別する必要はない。 |
| 2 | 230 |
| 4 | 231 この環境付き継続にもちいる\verb|__return|擬似変数の実装には様々な方法 |
| 2 | 232 が考えられるが、今回の実装には内部関数をもちいることにした。内部関数は |
| 3 | 233 GCCによるCの拡張機能である\cite{bib:nestedfunc}。 |
| 2 | 234 |
| 235 \subsubsection{GCCにより追加されるコード} | |
| 236 環境付き継続で使う\verb|__return|変数は特殊なコードセグメントへのポイ | |
| 237 ンタとなる必要がある。このコードセグメントはユーザでは定義せず、その変 | |
| 238 数を参照した関数の返り値型を基にコンパイラが自動で生成する事が望ましい。 | |
| 239 | |
| 7 | 240 具体的には、コード\ref{code:cbcreturn2}の関数funcB（ |
| 241 \pageref{code:cbcreturn}ページのコード\ref{code:cbcreturn}と同じ）をコ | |
| 242 ンパイラは次のコード\ref{code:nestedcode}の様に解釈し、内部コードセグ | |
| 243 メントを自動生成する。 | |
| 244 | |
| 245 \begin{minipage}[t]{.33\textwidth} | |
| 246 \lstinputlisting | |
| 247 [caption=\_\_returnの例, | |
| 248 label=code:cbcreturn2, | |
| 249 basicstyle=\footnotesize\ttfamily, | |
| 250 emph=\_\_return] | |
| 251 {sources/cbcreturn2.cbc} | |
| 252 \end{minipage} | |
| 253 \hfill | |
| 254 \begin{minipage}[t]{.55\textwidth} | |
| 255 \lstinputlisting | |
| 256 [caption=コード\ref{code:cbcreturn}のfuncBに追加される処理, | |
| 257 label=code:nestedcode,numbers=left] | |
| 258 {sources/nestedcode.cbc} | |
| 259 \end{minipage} | |
| 2 | 260 |
| 261 | |
| 262 5--14行がGCCにより追加される処理である。内部コードセグメント | |
| 7 | 263 \verb|_segment|は受け取った引数を関数の返り値として保持し、ラベ |
| 264 ル\verb|_label|にjumpする。この時点で内部コードセグメントを抜 | |
| 2 | 265 けて元の関数funcBの環境に復帰する。 |
| 266 | |
| 267 さらにjump先もGCCにより自動で追加される。しかしこのjump先は | |
| 7 | 268 \verb|_segment|以外からは実行してはならない。そのため条件式が真に |
| 2 | 269 ならないif文で囲み、実行を回避している。 |
| 7 | 270 jump先での処理は、\verb|_segment|内で代入された値を持ってリター |
| 2 | 271 ンするのみである。 |
| 272 | |
| 273 | |
| 274 \subsubsection{内部コードセグメント自動生成の実装方法} | |
| 275 | |
| 7 | 276 GCCは変数や関数、また文字列や数値などのリテラルに関する処理を \\ |
| 277 \verb|c_parser_postfix_expression|で行っている。この関数では変数や数 | |
| 278 値、文字列などの判定に500行にわたるswitch文を使っているが、ここに | |
| 2 | 279 \verb|__return|の判定も追加する。 |
| 280 | |
| 281 必要な処理は以下の様になる。 | |
| 282 \begin{itemize} | |
| 7 | 283 \item ラベル\verb|_label|の宣言 |
| 2 | 284 \item 返り値を保持しておく変数の宣言 |
| 285 \item 内部関数の定義 | |
| 286 \item 条件分岐制御の構文木生成 | |
| 287 \item 条件分岐内でのラベルの定義 | |
| 288 \item 条件分岐内での復帰構文の構文木生成 | |
| 289 \end{itemize} | |
| 7 | 290 参考のため付録\ref{apx:postfix-expression}にこの処理のコードを掲載す |
| 291 る。 | |
| 2 | 292 |
| 293 %コード\ref{code:nestedcode}にその処理を示す。 | |
| 294 %\lstinputlisting | |
| 295 % [caption=c\_parser\_postfix\_expressionでの処理, | |
| 296 % label=code:nestedcode] | |
| 297 % {sources/c_parser_postfix_expression.c} | |
| 298 %ここで使われている関数\verb|cbc_define_nested_code|, | |
| 299 %\verb|cbc_define_if_closed_goto |もこの処理のために作成したものである | |
| 300 %が割愛する。処理内容は GCCが通常行う関数やif文の構文木生成とほぼ同じで | |
| 301 %ある。 | |
| 302 | |
| 303 以上でコード\ref{code:nestedcode}に示すような処理がコンパイル時に自動 | |
| 304 で追加され、環境付き継続の使用が可能になった。 | |
| 305 | |
| 306 \subsubsection{関数からの継続} | |
| 307 | |
| 3 | 308 ここで軽量継続の実装にtailcallを用いたことの弊害がでてくる。 |
| 309 \ref{sec:impl-goto}節の実装では関数からの継続は考慮していない。通常の | |
| 2 | 310 継続の際は現コードセグメントのもつ引数は保持しないため、直接継続しよう |
| 311 とすると、その関数やその関数を呼び出した関数の持つ環境（スタック）を破 | |
| 3 | 312 壊してしまう（\pageref{fig:gotostack} |
| 313 ページ、図\ref{fig:gotostack}）。 | |
| 2 | 314 |
| 315 この問題を回避するため、関数からの継続に限り、スタックを拡張し関数の環 | |
| 316 境を保持する手法をとった。 | |
| 317 この動作は本来の軽量継続の概念とは相容れないものだが、Cとの互換性維持 | |
| 318 のために必要である。また、CbC部分での軽量継続ではいずれもスタックは定 | |
| 319 常なので、CbC の目的である検証、状態遷移記述などの問題にはならない。 | |
| 320 | |
| 321 | |
| 322 | |
| 323 \subsection{PowerPCにおける間接継続}\label{sec:impl-indirect} | |
| 324 | |
| 4 | 325 軽量継続の実装にtailcallを用いたことは\ref{sec:impl-goto}で説明した。 |
| 326 しかし、実際にはtailcallが行われないアーキテクチャがいくつか存在する。 | |
| 327 PowerPCもその一つで、このアーキテクチャでは間接呼び出しの場合は | |
| 328 tailcallが行われない。このためこれまでPowerPCでの間接継続はコンパイル | |
| 329 エラーで実行できなかった。 | |
| 2 | 330 |
| 3 | 331 間接呼び出しのtailcallは専用のRTL表現がある。 |
| 332 PowerPCで問題となるのは、このRTLからアセンブラへの変換が定義されていな | |
| 4 | 333 いことである。この問題に対処するため、PowerPCアーキテクチャにおけるmd |
| 3 | 334 を記述する。 |
| 335 | |
| 4 | 336 \subsubsection{間接tailcallのRTLとMachine Description} |
| 2 | 337 |
| 4 | 338 GCCでは関数呼び出しは全て一つのRTLに置き換えられる。 |
| 339 これはtailcallが行われた場合も、呼び出し関数がポインタである場合も同様 | |
| 340 である。しかしtailcallかポインタかによってRTLの形が異なるため、 | |
| 341 PowerPCではこの両方の場合（つまり間接呼び出しのtailcall）のRTLの形が | |
| 342 mdで定義されていない。そのため、これはエラーになる。 | |
| 2 | 343 |
| 4 | 344 この問題となっているRTLを次のコード\ref{code:rtl-indirecttailcall}に |
| 345 示す。 | |
| 2 | 346 \lstinputlisting |
| 347 [caption=PowerPCにおける間接継続のRTL, | |
| 3 | 348 label=code:rtl-indirecttailcall, |
| 2 | 349 language=Lisp] |
| 3 | 350 {sources/rtl-indirecttailcall.rtl} |
| 7 | 351 |
| 4 | 352 このRTL内の\verb|(mem:SI (reg/f:SI 129)|が関数のポインタを示すレジスタ |
| 353 である。間接呼び出しでない場合はこれが | |
| 354 \verb|(mem:SI (symbol_ref:SI (``cs0'')|となり、コードセグメントの関数 | |
| 355 を直接表している。 | |
| 2 | 356 |
| 357 \subsubsection{間接継続のmd} | |
| 358 | |
| 4 | 359 PowerPCにおいて間接継続を実装するには、上記のRTLを変換するmdを記述すれ |
| 360 ば良い。このRTLに近い形が間接でないtailcallのmdとして使われているはず | |
| 361 なのでそれを使用する。 次のコード\ref{code:md-example}が新しく記述され | |
| 362 たmdである。 | |
| 363 | |
| 2 | 364 \lstinputlisting |
| 4 | 365 [caption=\ref{code:rtl-indirecttailcall}の変換規則, |
| 3 | 366 label=code:md-for-indirect, |
| 2 | 367 language=Lisp] |
| 3 | 368 {sources/md-for-indirect.md} |
| 7 | 369 このコードの3番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似 |
| 3 | 370 ていることがわかる。これは変換対象としてこの型に合うものに制限するため |
| 371 である。 | |
| 372 | |
| 2 | 373 ここでは出力するアセンブラとして\verb|b%T0|が使われている。 |
| 374 \verb|%T0|はレジスタ名に置き換えられる部分である。このアセンブラは最終 | |
| 4 | 375 的には\verb|bctr|と置き換えられてPowerPCのアセンブラとして出力されるこ |
| 376 とになる。 | |
| 377 %間接でない、通常の継続ではこれが\verb|b%T0l|となっているので対照的であ | |
| 2 | 378 %る。コード\ref{code:md-example}は実際に通常の継続用のmd修正して作られ |
| 379 %た。 | |
| 380 | |
| 381 | |
| 382 | |
| 383 | |
| 384 \subsection{x86における引数渡し}\label{sec:impl-fastcall} | |
| 385 | |
| 386 コードセグメントの間の軽量継続は、Cの関数呼び出しと同じように引数を渡 | |
| 387 すことができる。関数呼び出しでのこの引数の渡し型はほとんどの場合アーキ | |
| 388 テクチャやオペレーティングシステム、また各プログラミング言語毎に違った | |
| 389 規約があり、これは一般に呼出規約(Calling convention)と呼ばれている。 | |
| 390 | |
| 7 | 391 CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は異なる。 |
| 392 mc の軽量継続では、なるべく多くの引数をレジスタに格納するようになって | |
| 393 おり、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少な | |
| 394 い x86でも2つだけだが、やはりレジスタを使用している。 | |
| 2 | 395 |
| 396 GCCベースコンパイラでは継続制御の引数渡しに関数の呼出規約と同じ方法を | |
| 397 使っている。そのため、x86では引数渡しに全てスタックを用いることになり | |
| 398 、mcに比べて速度低下がみられた。 | |
| 399 | |
| 400 引数渡しにレジスタを使用できるようにすることでこの問題を解決したい。 | |
| 401 | |
| 402 \subsubsection{fastcall} | |
| 403 そもそも引数渡しがスタックだけだということは、CbCだけでなくCにおいても | |
| 404 速度面で問題をはらんでいる。そのためGCCではもとより、x86でのレジスタ渡 | |
| 405 しを可能にする拡張機能を実装している。それがfastcallである。 | |
| 406 | |
| 407 このfastcallも使用するレジスタ数は2つだけではあるが、継続制御でもこれ | |
| 408 を使うことにより高速化が図れるはずである。 | |
| 409 | |
| 410 \subsubsection{コードセグメントを全てfastcallに} | |
| 411 | |
| 412 通常、GCCの拡張機能を用いて関数をfastcallにするにはコード | |
| 413 \ref{code:fastcall-example}の様に ``attribute''キーワードを関数宣言の | |
| 414 後ろに記述する。 | |
| 415 | |
| 416 \lstinputlisting | |
| 7 | 417 [caption=fastcallな関数fastfuncを宣言する例,label=code:fastcall-example] |
| 2 | 418 {sources/fastcall-example.c} |
| 419 | |
| 420 しかし全てのコードセグメントに対してこの属性を宣言するのは現実的でなく | |
| 421 、mcとのソースコードレベルの整合性もとれない。そこでGCCではコードセグ | |
| 422 メントの解析時に全てfastcall属性を付加することにする。 | |
| 423 | |
| 424 具体的には「型」の構文解析の際、キーワード``code''で関数の型が宣言され | |
| 425 ている場合に、属性値を表す構文木を付加する。 | |
| 426 \verb|c_parser_declspecs|関数が「型」に関する構文解析部である。 | |
| 427 この関数内の型名キーワードを処理するswitch文内で、``code''のみ | |
| 428 fastcall属性を付加する。 | |
| 429 | |
| 430 コード\ref{code:declspecs}がその処理である。このコードの12--14行目が | |
| 431 fastcall属性付加の処理になる。それ以外の行は voidやintなど他の型の処理 | |
| 432 と変わらない。 | |
| 433 | |
| 434 \lstinputlisting | |
| 435 [caption=c\_parser\_declspecsにおけるキーワード``code''の処理, | |
| 436 label=code:declspecs] | |
| 437 {sources/declspecs.c} | |
| 438 | |
| 439 この処理で全てのコードセグメントがfastcall対応となり、軽量継続の際には | |
| 440 レジスタ\verb|ecx,edx|に引数をのせることが可能となる。 | |
| 441 | |
| 442 | |
| 4 | 443 \subsection{プロトタイプ自動生成} \label{sec:prototype} |
|
5
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
444 Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。しかしCbC |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
445 のコードセグメントには返り値は存在しない。また状態遷移記述という性質上 |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
446 、プログラムを記述する際は上から下に実行順にコードセグメントを並べるこ |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
447 とが多いため、プロトタイプ宣言をするとそれが膨大な数になる。 |
| 2 | 448 |
| 449 また、mcベースコンパイラの方ではプロトタイプ宣言を減らすため、一種の簡 | |
| 450 単な型推論を実装している。そのためこれまでに作られたCbCのプログラムで | |
| 451 は特殊な場合を除いてプロトタイプ宣言がほとんどなく、GCCでコンパイルす | |
| 452 る際に問題となる。 | |
| 453 | |
|
5
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
454 これらの問題に暫定的に対処するため、Pythonを用いてプロトタイプの自動生 |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
455 成を行うスクリプトを作成した。このスクリプトでは関数の定義部を正規表現 |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
456 で検索し、マッチする部分を変換して関数宣言として出力する。 |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
457 全コードは付録\ref{apx:make-prototype}に掲載する。 |
| 2 | 458 |
|
5
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
459 このプトロタイプ自動生成により、これまでに作られたCbCのプログラムとの |
|
dfb89e32eea1
added gcc.tex, conclusion.tex
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
460 互換性が確保できた。 |
| 2 | 461 |
| 462 |