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

この章では、GCCにおけるCbCコンパイラの実装方法の説明と、\ref{chp:cbc}
章にて示した項目の実装を行う。

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

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

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

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

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

GCC（及び一般的なコンパイラ）ではコンパイルに必要な全ての要素、変数や式
、関数、構文などをすべて Genericと呼ばれる構文木に保持している。よって
Genericを生成するParserのルーチンにおいて、コードセグメントの構文木を
関数の構文木と同じように作成すれば良い。

コード\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を生成する処理であ
る（cc1のミドルエンドに当たる）。この関数内では呼び出される関数のアド
レスを取得するコードの生成、スタックへの引数をプッシュするコードの生成
、引数のプッシュの度に tailcallが可能かのチェックなどが行われている。

問題となるのはtailcallの可否をチェックする部分である。
ここでは主に以下の条件でtailcallが不可能だと判定される。
\begin{itemize}
  \item 呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれよ
    り大きい場合

  \item 引数を順にスタックに格納すると、書き込み前のデータが上書きされ
    てしまう場合
\end{itemize}
そのため、この条件を回避するための処理が必要となる。

スタックサイズの問題に関しては、呼出元関数のスタックサイズをごまかす方
法をとった。全てのコードセグメントは一定の（今回は4096）バイト数のスタ
ックサイズを持つと決めうちすることでこの条件は回避できる。

引数を書き込む順番の問題は、書き込む順序を工夫することで回避した。
書き込んでも次に読み込む引数に影響を与えない引数から順に書き込むように
実行順序を操作する。

この二つの処理はどちらもミドルエンドの\verb|expand_call|関数内で行われ
ている。

上記処理の追加により軽量継続が実装された。
継続の際にコードセグメントに渡す引数は関数と同じようにスタック上に格納
されるが、このスタックは拡張することはなく、図
\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}

前節で説明した様に、コードセグメントへの継続の際の引数書き込みが、別の
引数の読み込みに影響を与えるような場合に正しく引数を渡せないという問題
がある。

前の実装の際には、ミドルエンドの\verb|expand_call|関数という関数呼出の
RTLを生成するルーチンにおいて、引数格納の順序を工夫することでこの問題
を一部回避していた。

しかし完全に、任意の引数の組み合わせでも引数渡しを可能にするにはこの処
理だけでは足りず、``並列代入''を導入する必要がある。

\subsubsection{並列代入とは}

複数の変数に同時に値を代入する事を並列代入(Parallel Assignment)という。
例えばPythonでは\lstinline[language=Python]|a, b = 0, 1|として並列代入
を行える。この場合は単純に二つの代入を順に実行したものと結果は同じだが
、\lstinline[language=Python]|a, b = b, a|という場合には結果は同じには
ならない。順に\lstinline[language=Python]|a=b, b=a|と分割すると元の
\verb|a|の値が失われてしまうからである。処理を正しく行うには、一部の変
数の値を一時変数に保持するなどの処理が必要である。

CbCの継続制御ではコード\ref{code:parallel-example2}の場合などに並列代
入が必要になる。これは継続元の引数の格納場所と継続先のそれが互いに逆の
位置にあるからである。

\lstinputlisting
  [caption=並列代入の必要な軽量継続の例,label=code:parallel-example2]
  {sources/parallel-example.cbc}

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

そのため、このような場合に並列代入を行うことでこの問題が解消できる。し
かし実際にはGCCは元より並列代入を実装しているため、独自の並列代入の実
装は必要としない。余分な一時変数への確保は最適化により省かれるが、この
最適化を利用して、継続制御の引数渡しを並列代入にする。

この実装では一時変数に全ての引数を退避する手法をとった。具体的には、コ
ード \ref{code:avoiding-parallel}の様に、一旦全ての引数を局所変数に代
入し、それらの局所変数を継続の引数とする。

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

この処理はもちろんユーザがソースコードで行うのではなく、GCCが自動で判
定してそのような構文木を生成するべきである。

こうすることで引数が一時変数に確保され、その後そこからコピーする形で所
定のメモリ位置に戻されるため問題が回避できる。


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

その代わり、この余分な一時変数への退避の生成は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|擬似変数の実装には様々な方法が
考えられる。例えば\ref{ssec:gotowithenv}節で紹介した
\verb|setjmp/longjmp|を使った実装も可能である。
しかしこの方法は特に\verb|longjmp|のオーバヘッドが大きく、また実行環境
によっては\verb|setjmp/longjmp|そのものがないことも考えられる。ポータ
ビリティを考えるとGCCの機能で実装することが望ましい。

今回の実装には内部関数をもちいることにした。内部関数は GCCによるCの拡
張機能である\cite{bib:nestedfunc}。

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

具体的には、コード\ref{code:cbcreturn2}の関数funcBをコンパイラは次のコ
ード\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:nest-asm}に示す。

\lstinputlisting
  [caption=\ref{code:nestedcode}のfuncBで出力されるアセンブラ(x86),
   label=code:nest-asm,numbers=left,frame=Ltb,multicols=2]
  {sources/nestedcode.asm}

この出力によると、\verb|funcB|はcsに継続（20行目）する前にいくつかのレ
ジスタをスタック領域に確保している。これは内部関数が呼ばれた際にこの
\verb|funcB|の環境を再現するためのものである。内部関数は
\verb|_segment.1243|として表されており、\verb|jmp *%eax|をもって
\verb|.L3|にジャンプし、最終的に\verb|.L5|のコード内で関数
\verb|funcB|からリターンする。

以上でコード\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が行われない。
これはtailcallを表すRTLをアセンブラに変換するmdが定義されていないため
である。このため、これまで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'')|となり、コードセグメントの関数
を直接表している。また、下に続く\verb|expr_list|は引数の列である。この
RTLの表す継続制御の引数がこのS 式で表されている。

PowerPCをこの間接継続に対応させるにはこのRTLに対応するmdを定義する必要
がある。


\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}のRTLと
よく似ていることがわかる。これは変換対象としてこの型に合うものに制限す
るためである。

ここでは出力するアセンブラとして\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を用いてプロトタイプの自動生
成を行うスクリプトを作成した。このスクリプトでは関数の定義部を正規表現
で検索し、マッチする部分を変換して関数宣言として出力する。この出力例と
して、\pageref{code:factorial}ページにある階乗計算を行うコード
\ref{code:factorial}をスクリプトに通した結果を、コード
\ref{code:factorial-header}に示す。

\lstinputlisting
  [caption=プロトタイプ自動生成スクリプトの出力例,label=code:factorial-header]
  {sources/factorial.h}

このスクリプトの全コードは付録\ref{apx:make-prototype}に掲載する。

このプトロタイプ自動生成により、CbCプログラムのヘッダファイルを自動生
成することができる。プログラムではこのヘッダファイルをインクルードする
ことで、micro-cコンパイラとの互換性を確保することができる。