\chapter{GCCにおける実装・改善}
\label{chp:impl}

この章では、GCCにおけるCbCコンパイラの実装方法の説明と、 \ref{chp:cbc}
章で洗い出したGCCでの問題点の改善を行う。

実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。
このcc1はCからアセンブラへ変換を行う純粋なコンパイラとして実行されるプ
ログラムである。このcc1をCbCの構文解析に対応させる。

過去の研究においてはGCCのバージョン4.2.3が用いられた。現在はGCCのリリ
ースに並ぶ形で4.4.2（2010年1月時）を用いている。

\section{過去の研究における実装部分}
今回の改善においての予備知識として、過去の研究での実装部分であるコード
セグメントと軽量継続がどのように実装されたかを簡単に説明する。

\subsection{コードセグメントの実装}

コードセグメント内部の実装は実際は単なる関数で良い。
変更の必要があったのは関数の返り値に当たる部分である。コードセグメント
では返り値が存在しないのでここは``code''キーワードを入力できるようにす
る。このcodeは内部でvoid型に変換する。

GCC（及び一般的なコンパイラ）ではコンパイルに必要な全ての要素、変数や式
、関数、構文などをすべて GIMPLEと呼ばれる構文木に保持している。コードセ
グメントの構文木も関数とほぼ同じものを作成すれば良い。コード
\ref{code:build-code-segment}はその構文木を作成している部分である。

\lstinputlisting
  [caption=構文木生成(gcc/c-typeck.c),label=code:build-code-segment]
  {sources/build-code-segment.cbc}

\verb|build_code_segment_type|関数においてコードセグメントの構文木を作
成している。内部の処理は\verb|build_function_type|とほぼ同じだが、関数
のテーブルに登録せず、軽量継続の際にそれがコードセグメントであることを
示すためのフラグをセットしている。



\subsection{軽量継続の実装} \label{sec:impl-goto}

軽量継続はGCCの末尾呼び出し最適化の機構を用いて実装する。

\subsubsection{末尾呼び出し最適化}
プログラム中、関数を呼び出すときには通常はスタックを積み上げ、現在の環
境を保持した上で呼び出し先の処理を行う。これは元の関数に復帰して残りの
処理を続行する必要があるためである。しかし関数の最後、リターン直前に呼
び出しを行う場合は環境を保持する必要がない（図\ref{fig:tailcall}参照）
。そのためスタックの状態を変更することなく呼び出すことができる。この最
適化は末尾呼び出し最適化(tailcall)と呼ばれている。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.6\textwidth]{figures/tailcall.eps}
  \end{center}
  \caption{末尾呼び出し最適化が可能な関数funcYの例}
  \label{fig:tailcall}
\end{figure}

Scheme処理系では仕様上この最適化が必須となっているが、Cはそうではない。
しかしGCCはこの最適化をデフォルトで行っている。

\subsubsection{軽量継続への摘要}
tailcallをコードセグメントの呼び出しに適用することで軽量継続が実装でき
る。具体的にはソースコード上にコード\ref{code:goto}のような式があった
場合に、これをコード\ref{code:ret-call}と同じように解釈する。
つまり、``goto''が前置する関数呼び出しは、必ず後ろに\verb|return;|がつ
くと解釈するのである。これでtailcallの条件ほぼ満たされる。

この構文解析はGCCのgcc/c-parser.c内で行う。

\begin{minipage}[t]{.45\textwidth}
  \lstinputlisting[caption=goto文の例,label=code:goto]
    {sources/goto-expression.cbc}
\end{minipage}
\hfill
\begin{minipage}[t]{.45\textwidth}
  \lstinputlisting[caption=構文木での解釈,label=code:ret-call]
    {sources/ret-call.cbc}
\end{minipage}

しかし構文木の変更だけではtailcallが行われるとは限らない。特にスタック
の状態や変数の数、順番によっても最適化はカットされる場合がある。
そのため最適化を判断する条件式を修正、また構文木から中間コードRTLを生
成する部分でも修正が必要になる。

\paragraph{expand-call}関数は関数を表す構文木からRTLを生成する処理であ
る。この関数内では呼び出される関数のアドレスを取得するコードの生成、ス
タックへの引数をプッシュするコードの生成、引数のプッシュの度に
tailcallが可能かのチェックなどが行われている。

ここでは以下の処理を追加することでtailcallカットの条件判断をパスしている。
\begin{itemize}
  \item スタックのサイズをごまかす

    tailcallは呼び出し元の全引数サイズが呼び出し先のそれより小さい場合
    には実行できない。そのため呼び出し元のコードセグメント全ての引数に
    もちいるスタックサイズを大きな値でごまかす。
  \item 並列代入

    \ref{sec:cbc-problem}で説明したような並列代入の必要な関数呼び出し
    を行った場合はtailcallは実行されない。そのためここで並列代入が必要
    になる。
\end{itemize}

上記処理の追加により軽量継続が実装された。
継続の際にコードセグメントに渡す引数は関数と同じようにスタック上に格納
されるが、このスタックは拡張することはなく、図
\ref{fig:gotostack}のように連続した継続の中でスタックポインタは常
に同じアドレスを指し示す。（比較のため、図\ref{fig:funcstack}には関数
呼び出しの際のスタックの状態を例示した）
\begin{figure}[htpb]
  \begin{center}
    \subfloat[][関数呼び出し]{\label{fig:funcstack}
      \includegraphics[width=.6\textwidth]{figures/functionstack.eps}}
    \subfloat[][軽量継続]{\label{fig:gotostack}
      \includegraphics[width=.6\textwidth]{figures/interfacestack.eps}}
  \end{center}
  \caption{継続制御と関数呼び出しでのスタックの違い}
\end{figure}

しかし並列代入の処理は構造体のようにオーバラップする引数に対しては対応
しておらず、プログラムによっては引数がちゃんと渡されないなどのバグが生
じていた。


\section{問題点の改善}
ここから\ref{sec:cbc-problem}節で紹介した問題点について、本研究での改
善点を説明する。


\subsection{並列代入}\label{sec:impl-parallel}

\ref{sec:gcc-problems}節で説明した様に、コードセグメントの受け取
った引数と継続の際に渡す引数の順序が変わる場合等に並列代入が必要になる。
過去の実装ではこの並列代入を、\verb|expand_call|という構文木から RTLを
生成する処理の部分で行っていた。

しかし実際にはGCCは元より並列代入を実装しているため、独自の実装は必要
としない。また、この独自の実装にも問題があった。
そのため独自の実装は廃止し、GCCの機能を利用することにする。

コード\ref{code:parallel-example2}は並列代入の必要な軽量継続の例である。
\lstinputlisting
  [caption=並列代入の必要な軽量継続の例,label=code:parallel-example2]
  {sources/parallel-example.cbc}

継続の引数は現在の引数と同じメモリに格納されるため、引数\verb|a|は
\verb|b|の位置に、引数\verb|b|は\verb|a|の位置に代入されることになる。
この場合に並列代入を考慮せず、順に代入すると
\begin{verbatim}
  a = b;
  b = a;
\end{verbatim}
となり、両方が同じ値になってしまう。
ただしこの例は極端に簡略化した例であり、この程度であればtailcallに問題
はない。しかしより複雑な並列代入では同じ問題が現れる。特に、引数に含ま
れるコードセグメントポインタへ間接継続する場合には、ほぼ確実に失敗する。

この問題の回避策として単純にコード\ref{code:avoiding-parallel}の様に変
数の値を一時変数に退避することが考えられる。

\lstinputlisting
  [caption=引数の退避,label=code:avoiding-parallel]
  {sources/avoiding-parallel.cbc}

こうすることで引数が一時変数に確保され、その後そこからコピーする形で所
定のメモリ位置に戻されるため問題が回避できる。今回の並列代入の改善では
この手法を用いる。

\subsubsection{問題点と最適化の期待}
この手法でどのように引数を入れ替えても正しく代入可能になる。ただし、一
時変数の使用は処理速度に問題がある。特にレジスタの少ないアーキテクチャ
では一時変数の確保にメモリ上のスタックを用いるため、余計なメモリアクセ
スや冗長な命令が増えてしまう。このため、この手法を実践したコードではそ
うでないコードに比べて若干の速度低下が見込まれる。

その代わり、この速度低下はGCCのもつ最適化機構で回避され得るものである。
GCCでは中間コード生成後、必要のない一時変数へのコピーなどは最適化によ
りカットされる。そのため、最適化を有効にした場合はこの処理速度の低下は
起きないと考えられる。この影響に関しては\ref{chp:eval}章にて検証する。

\subsubsection{一時変数への退避の実装}

この手法の実装は、中間コード生成時ではなく構文木生成で可能である。
tailcallの関数呼び出しを表す構文木の生成時に以下の処理を追加する。
\begin{enumerate}
  \item 関数呼び出しを表す構文木\verb|a|の取得
  \item \verb|a|から引数を表す構文木を取得、それぞれについて
    \begin{enumerate}
      \item 同じ型の名前なし一時変数を作成
      \item 引数の値を一時変数に代入
      \item 関数に渡す引数を一時変数に変更
    \end{enumerate}
  \item 呼び出す関数がポインタだった場合
    \begin{enumerate}
      \item 関数と同じ型（関数ポインタ）の一時変数を作成
      \item 関数アドレスを一時変数に代入
      \item 呼び出す関数を一時変数に変更
    \end{enumerate}
\end{enumerate}

ここでは関数ポインタも引数と同じように扱い、一時変数に退避する。
実際のプログラムはコード\ref{code:replace-args}の様になる。
この関数\verb|cbc_replace_arguments|は関数呼び出し構文木を引数として受
け取り、上記の処理を行う。引数として渡される\verb|tree call|がその構文
木である。 \verb|build_decl|は名無し一時変数の宣言、
\verb|build_modify_expr|は一時変数への代入を行う構文木の生成をしている
。

\lstinputlisting
  [caption=上記の処理を行う関数,label=code:replace-args]
  {sources/replace-args.c}

ソースコードの構文解析時、軽量継続をパースしてその構文木を生成した際に
、この関数\verb|cbc_replace_arguments|を実行することで、この軽量継続は
並列代入に対応できるようになった。


\subsection{環境付き継続}

環境付き継続は過去の研究では実装されていなかった。
これはCとの互換性のために必要な制御構造である。

環境付き継続には\ref{ssec:gotowithenv}で述べたように、\verb|__return|
という擬似変数を使う。この変数の値を継続先のコードセグメントに渡すこと
で、そのコードセグメントから関数の環境へ復帰することを可能にする。
渡された\verb|__return|の値は、コードセグメント側からは他のコードセグ
メントと区別する必要はない。

この環境付き継続にもちいる\verb|__return|擬似変数の実装には様々な方法
が考えられるが、今回の実装には内部関数をもちいることにした。内部関数は
GCCによるCの拡張機能である\cite{bib:nestedfunc}。

\subsubsection{GCCにより追加されるコード}
環境付き継続で使う\verb|__return|変数は特殊なコードセグメントへのポイ
ンタとなる必要がある。このコードセグメントはユーザでは定義せず、その変
数を参照した関数の返り値型を基にコンパイラが自動で生成する事が望ましい。

具体的には、コード\ref{code:cbcreturn2}の関数funcB（
\pageref{code:cbcreturn}ページのコード\ref{code:cbcreturn}と同じ）をコ
ンパイラは次のコード\ref{code:nestedcode}の様に解釈し、内部コードセグ
メントを自動生成する。

\begin{minipage}[t]{.33\textwidth}
  \lstinputlisting
    [caption=\_\_returnの例,
     label=code:cbcreturn2,
     basicstyle=\footnotesize\ttfamily,
     emph=\_\_return]
    {sources/cbcreturn2.cbc}
\end{minipage}
\hfill
\begin{minipage}[t]{.55\textwidth}
  \lstinputlisting
    [caption=コード\ref{code:cbcreturn}のfuncBに追加される処理,
     label=code:nestedcode,numbers=left]
    {sources/nestedcode.cbc}
\end{minipage}


5--14行がGCCにより追加される処理である。内部コードセグメント
\verb|_segment|は受け取った引数を関数の返り値として保持し、ラベ
ル\verb|_label|にjumpする。この時点で内部コードセグメントを抜
けて元の関数funcBの環境に復帰する。

さらにjump先もGCCにより自動で追加される。しかしこのjump先は
\verb|_segment|以外からは実行してはならない。そのため条件式が真に
ならないif文で囲み、実行を回避している。
jump先での処理は、\verb|_segment|内で代入された値を持ってリター
ンするのみである。


\subsubsection{内部コードセグメント自動生成の実装方法}

GCCは変数や関数、また文字列や数値などのリテラルに関する処理を \\
\verb|c_parser_postfix_expression|で行っている。この関数では変数や数
値、文字列などの判定に500行にわたるswitch文を使っているが、ここに
\verb|__return|の判定も追加する。

必要な処理は以下の様になる。
\begin{itemize}
  \item ラベル\verb|_label|の宣言
  \item 返り値を保持しておく変数の宣言
  \item 内部関数の定義
  \item 条件分岐制御の構文木生成
  \item 条件分岐内でのラベルの定義
  \item 条件分岐内での復帰構文の構文木生成
\end{itemize}
参考のため付録\ref{apx:postfix-expression}にこの処理のコードを掲載す
る。

%コード\ref{code:nestedcode}にその処理を示す。
%\lstinputlisting
%  [caption=c\_parser\_postfix\_expressionでの処理,
%   label=code:nestedcode]
%  {sources/c_parser_postfix_expression.c}
%ここで使われている関数\verb|cbc_define_nested_code|,
%\verb|cbc_define_if_closed_goto |もこの処理のために作成したものである
%が割愛する。処理内容は GCCが通常行う関数やif文の構文木生成とほぼ同じで
%ある。

以上でコード\ref{code:nestedcode}に示すような処理がコンパイル時に自動
で追加され、環境付き継続の使用が可能になった。

\subsubsection{関数からの継続}

ここで軽量継続の実装にtailcallを用いたことの弊害がでてくる。
\ref{sec:impl-goto}節の実装では関数からの継続は考慮していない。通常の
継続の際は現コードセグメントのもつ引数は保持しないため、直接継続しよう
とすると、その関数やその関数を呼び出した関数の持つ環境（スタック）を破
壊してしまう（\pageref{fig:gotostack} 
ページ、図\ref{fig:gotostack}）。

この問題を回避するため、関数からの継続に限り、スタックを拡張し関数の環
境を保持する手法をとった。
この動作は本来の軽量継続の概念とは相容れないものだが、Cとの互換性維持
のために必要である。また、CbC部分での軽量継続ではいずれもスタックは定
常なので、CbC の目的である検証、状態遷移記述などの問題にはならない。



\subsection{PowerPCにおける間接継続}\label{sec:impl-indirect}

軽量継続の実装にtailcallを用いたことは\ref{sec:impl-goto}で説明した。
しかし、実際にはtailcallが行われないアーキテクチャがいくつか存在する。
PowerPCもその一つで、このアーキテクチャでは間接呼び出しの場合は
tailcallが行われない。このためこれまでPowerPCでの間接継続はコンパイル
エラーで実行できなかった。

間接呼び出しのtailcallは専用のRTL表現がある。
PowerPCで問題となるのは、このRTLからアセンブラへの変換が定義されていな
いことである。この問題に対処するため、PowerPCアーキテクチャにおけるmd
を記述する。

\subsubsection{間接tailcallのRTLとMachine Description}

GCCでは関数呼び出しは全て一つのRTLに置き換えられる。
これはtailcallが行われた場合も、呼び出し関数がポインタである場合も同様
である。しかしtailcallかポインタかによってRTLの形が異なるため、
PowerPCではこの両方の場合（つまり間接呼び出しのtailcall）のRTLの形が
mdで定義されていない。そのため、これはエラーになる。

この問題となっているRTLを次のコード\ref{code:rtl-indirecttailcall}に
示す。
\lstinputlisting
  [caption=PowerPCにおける間接継続のRTL,
   label=code:rtl-indirecttailcall,
   language=Lisp]
  {sources/rtl-indirecttailcall.rtl}

このRTL内の\verb|(mem:SI (reg/f:SI 129)|が関数のポインタを示すレジスタ
である。間接呼び出しでない場合はこれが
\verb|(mem:SI (symbol_ref:SI (``cs0'')|となり、コードセグメントの関数
を直接表している。

\subsubsection{間接継続のmd}

PowerPCにおいて間接継続を実装するには、上記のRTLを変換するmdを記述すれ
ば良い。このRTLに近い形が間接でないtailcallのmdとして使われているはず
なのでそれを使用する。 次のコード\ref{code:md-example}が新しく記述され
たmdである。

\lstinputlisting
  [caption=\ref{code:rtl-indirecttailcall}の変換規則,
   label=code:md-for-indirect,
   language=Lisp]
  {sources/md-for-indirect.md}
このコードの3番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似
ていることがわかる。これは変換対象としてこの型に合うものに制限するため
である。

ここでは出力するアセンブラとして\verb|b%T0|が使われている。
\verb|%T0|はレジスタ名に置き換えられる部分である。このアセンブラは最終
的には\verb|bctr|と置き換えられてPowerPCのアセンブラとして出力されるこ
とになる。
%間接でない、通常の継続ではこれが\verb|b%T0l|となっているので対照的であ
%る。コード\ref{code:md-example}は実際に通常の継続用のmd修正して作られ
%た。




\subsection{x86における引数渡し}\label{sec:impl-fastcall}

コードセグメントの間の軽量継続は、Cの関数呼び出しと同じように引数を渡
すことができる。関数呼び出しでのこの引数の渡し型はほとんどの場合アーキ
テクチャやオペレーティングシステム、また各プログラミング言語毎に違った
規約があり、これは一般に呼出規約(Calling convention)と呼ばれている。

CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は異なる。
mc の軽量継続では、なるべく多くの引数をレジスタに格納するようになって
おり、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少な
い x86でも2つだけだが、やはりレジスタを使用している。

GCCベースコンパイラでは継続制御の引数渡しに関数の呼出規約と同じ方法を
使っている。そのため、x86では引数渡しに全てスタックを用いることになり
、mcに比べて速度低下がみられた。

引数渡しにレジスタを使用できるようにすることでこの問題を解決したい。

\subsubsection{fastcall}
そもそも引数渡しがスタックだけだということは、CbCだけでなくCにおいても
速度面で問題をはらんでいる。そのためGCCではもとより、x86でのレジスタ渡
しを可能にする拡張機能を実装している。それがfastcallである。

このfastcallも使用するレジスタ数は2つだけではあるが、継続制御でもこれ
を使うことにより高速化が図れるはずである。

\subsubsection{コードセグメントを全てfastcallに}

通常、GCCの拡張機能を用いて関数をfastcallにするにはコード
\ref{code:fastcall-example}の様に ``attribute''キーワードを関数宣言の
後ろに記述する。

\lstinputlisting
  [caption=fastcallな関数fastfuncを宣言する例,label=code:fastcall-example]
  {sources/fastcall-example.c}

しかし全てのコードセグメントに対してこの属性を宣言するのは現実的でなく
、mcとのソースコードレベルの整合性もとれない。そこでGCCではコードセグ
メントの解析時に全てfastcall属性を付加することにする。

具体的には「型」の構文解析の際、キーワード``code''で関数の型が宣言され
ている場合に、属性値を表す構文木を付加する。
\verb|c_parser_declspecs|関数が「型」に関する構文解析部である。
この関数内の型名キーワードを処理するswitch文内で、``code''のみ
fastcall属性を付加する。

コード\ref{code:declspecs}がその処理である。このコードの12--14行目が
fastcall属性付加の処理になる。それ以外の行は voidやintなど他の型の処理
と変わらない。

\lstinputlisting
  [caption=c\_parser\_declspecsにおけるキーワード``code''の処理,
   label=code:declspecs]
  {sources/declspecs.c}

この処理で全てのコードセグメントがfastcall対応となり、軽量継続の際には
レジスタ\verb|ecx,edx|に引数をのせることが可能となる。


\subsection{プロトタイプ自動生成} \label{sec:prototype}
Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。しかしCbC
のコードセグメントには返り値は存在しない。また状態遷移記述という性質上
、プログラムを記述する際は上から下に実行順にコードセグメントを並べるこ
とが多いため、プロトタイプ宣言をするとそれが膨大な数になる。

また、mcベースコンパイラの方ではプロトタイプ宣言を減らすため、一種の簡
単な型推論を実装している。そのためこれまでに作られたCbCのプログラムで
は特殊な場合を除いてプロトタイプ宣言がほとんどなく、GCCでコンパイルす
る際に問題となる。

これらの問題に暫定的に対処するため、Pythonを用いてプロトタイプの自動生
成を行うスクリプトを作成した。このスクリプトでは関数の定義部を正規表現
で検索し、マッチする部分を変換して関数宣言として出力する。
全コードは付録\ref{apx:make-prototype}に掲載する。

このプトロタイプ自動生成により、これまでに作られたCbCのプログラムとの
互換性が確保できた。