\chapter{CbC の実装}
前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
ここからは GCC-4.6 への実装について述べていく.

\section{構文の追加}


\subsection{``\_\_code''のパース}
C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている.
ここに, ソースコード\ref{src:code-parse}のように \verb+__code+ 型の追加を行う.


\begin{lstlisting}[label=src:code-parse, caption=\_\_codeの予約後登録]
const struct c_common_resword c_common_reswords[] =
  {
    { "_Bool",            RID_BOOL,      D_CONLY },
    { "_Complex",         RID_COMPLEX,    0 },
    :
    /* CbC project */
    { "__code",         RID_CbC_CODE,   0 },
    :
\end{lstlisting}

\begin{lstlisting}[label=src:code-id, caption=cts\_CbC\_code の定義]
enum c_typespec_keyword { cts_none,
cts_void,
: 
cts_CbC_code,
\end{lstlisting}

\begin{lstlisting}[label=src:regi-id, caption=id の登録]
case RID_CbC_CODE: if (specs->long_p)
: 
else
specs->typespec_word = cts_CbC_code; return specs;
\end{lstlisting}



これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる.
次に, id を用意する.
 Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される.
そこに登録するコードセグメント判定用 id  ``\verb+cts_CbC_code+'' を用意する.
これは gcc/c-tree.h で定義される(ソースコード\ref{src:code-id}).
後は\verb+c_declspecs+ 構造体にこの id を登録する.
 id の登録は \verb+declspecs_add_type+ 関数の中で行われる(ソースコード\ref{src:regi-id}).

ソースコード\ref{src:regi-id} のプログラムは void 型の id 登録を元に作られている.
違うところは \verb+cts_CbC_code+ を登録するところだけである.

読み込まれたコードは, 最後に \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする.
コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと
して登録している(ソースコード\ref{src:regi-node}).



\lstinputlisting[label=src:regi-node, caption=declspecs\_add\_type 関数]{src/regi-id.c}

\subsection{gotoシンタックスの追加}

通常 goto のシンタックスは ``goto ラベル名;'' となる.
CbC では通常の goto に加え ``goto cs(arg,...);'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある.
ソースコード\ref{src:rid-goto}は, 追加した goto のシンタックスである
(通常のシンタックスは省いてある).


\lstinputlisting[label=src:rid-goto, caption=goto シンタックスへの追加]{src/rid-goto.c}

具体的にはvoid 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ
を付けた関数の Tree となっている.

\verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については
 CbC においても重要になるので後に説明する.


\section{Tail Call elimination}
CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する.
これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.

funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻値を funcB ではなく funcA へと返すことになる.



\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=70mm]{figure/continuation.pdf}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}



\subsection{expand\_call}
\verb+expand_call+ 関数は, 関数を表す Tree から RTL を生成する関数である.
 Tail Call Elimination を行えるかどうかもこの関数で判断される.
内部でチェックされる Tail Call Elimination の条件は以下になる.
%\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.

%\begin{itemize}
\begin{enumerate}
  \item caller 側と callee 側の戻値の型が一致している.
  \item 関数呼び出しがリターンの直前に行われている.
  \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
  \item 引数の並びのコピーに上書きがない.
\end{enumerate}
%\end{itemize}

CbC の実装では上記の条件を,以下の様にして解決させている.

\begin{enumerate}
%\begin{itemize}
%  \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない.
  \item コードセグメントは void 型で統一する. 最適化(-O2)の強制付与.
  \item goto の直後に retrun を置く．
  \item スタックサイズは関数宣言時に決まったサイズにする．
  \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
%\end{itemize}
\end{enumerate}

%1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
%2, 3 と 4 については以下で詳しく説明を行う.
戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう.
最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う.


\subsection{末尾最適化の矯正付与}
Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる.
以前の CbC-GCC の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_goto+ という関数を作成して,
 条件をクリアするようにしていた.
しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_goto+ 関数にも
変更を加える必要があり, 手間となっていた.
そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_goto+ 関数を取り除くことに
成功した(ソースコード\ref{src:tail_call}:2行目).




\lstinputlisting[label=src:tail_call, caption=コードセグメントの末尾最適化の付与]{src/tail_call_flag.c}

\verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+
 変数があり, コードセグメントはこのフラグには初め 1 がセットされている.
コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った.
また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った.
これにより末尾最適化の強制付与がなされた.

\subsection{gotoの後にreturnの配置}
コードセグメントは GCC 内部では関数として扱われる.
Tail Call Elimination は関数呼び出しの直後に return がある場合にかかる.
その為, goto の直後に return を置く必要がある.
CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
ソースコード\ref{src:rid-goto}の \verb+c_finish_return+ 関数がそれにあたる.
これにより, コンパイラではソースコード\ref{src:factorial}のコードセグメント factorial0 がソースコード\ref{src:return}
として処理される.

%ソースコード\ref{src:factorial}のコードセグメント factorial0 をソースコード\ref{src:return}の様に, goto の直後に return を
%置く必要がある.だがそれをプログラマが記述することは実用的でない.


\lstinputlisting[label=src:return, caption=goto の直後に return を置く]{src/return.c}

%goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う.


\subsection{スタックサイズの固定化}
CbC の継続では, C の関数呼び出しとは違いスタックに値が積まれていくことはない.
その為スタックサイズを固定にすることができる.
また, スタックサイズが固定な為, スタックポインタを変えずにスタックを扱うことができる.
これも CbC の1つの特徴である.
図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=90mm]{figure/cs_stack.pdf}
  \end{center}
  \caption{継続による引数のスタック格納の様子}
  \label{fig:cs_stack}
\end{figure}



\subsection{引数の並びの上書きコピー}
CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
例えばソースコード\ref{src:cs_prog_code}のような継続である.

\begin{lstlisting}[label=src:cs_prog_code, caption=スタックの上書きが起こる継続]
__code cs_a(int a, int b) { 
    goto cs_b(b, a)
}
\end{lstlisting}


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=80mm]{figure/cs_prog.pdf}
  \end{center}
  \caption{スタック書き換えの問題}
  \label{fig:cs_prog}
\end{figure}
この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる.
数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している.
CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している.

\subsubsection{一時変数へのコピー}
一時変数へのコピーは, goto が行れるコードセグメントの Generic Tree 生成時に行われる.

ソースコード\ref{src:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる.


\lstinputlisting[label=src:cbc_replace, caption=引数の一時変数へのコピー]{src/cbc_replace_arguments.c}


具体的には, 内部で以下の事が行われている.
\begin{itemize}
\item 引数と同じ型の一時変数を作成
\item 一時変数に引数の値を代入
\item 関数に渡す引数のポインタを一時変数に変更
\end{itemize}

Tree call は継続を行うコードセグメントを指す.
コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
ところへ一時変数を入れている.



\section{環境付き継続}
CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
これを環境付き継続という.
これらは, 以下の二種類の CbC で定義した特殊変数である.
\verb+__environment+ は, 環境を表す情報である.
\verb+__return+ は,  これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ
コードセグメントである. 例えば, 図\ref{fig:env_code}のように使うと, \verb+main()+ は 1 を返す.


\begin{lstlisting}[label=fig:env_code, caption=\_\_return\, \_\_environment 変数の使用例]
__code c1(__code ret(int,void *),void *env) { goto ret(1,env);
}
int main() {
goto c1(__return, __environment);
}
\end{lstlisting}

GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(ソースコード\ref{src:ret_val_code}).



\lstinputlisting[label=src:ret_val_code, caption=環境付き継続を行うコード]{src/ret_val.c}



\subsubsection{環境付き継続の問題}
現在環境付き継続は
このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
 \verb+retval+に static を指定してしまうと,
 スレッドセーフな実装でなくなる.
Thread local 変数を用いると, やはり closure が出力されてしまう.
スタックに値を確保する closure は, スタックを破棄していく CbC には向いていない.
戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
浮動小数点や構造体自体である可能性があり複雑である. 
一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある.



\section{引数の渡し方}
通常 ia32 のコードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される.
だが GCC には ia32 の引数渡しにレジスタを用いらせる機能として fastcall がある.
使えるレジスタは 2つまでだが, 継続を繰り返して行う CbC においては fastcall を使うことで速度向上が望めるはずである.


\subsubsection{fastcall}
C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う.
だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない.
そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う.
ソースコード\ref{src:fastcall}はコードセグメントの生成を行なっているコードである.

\lstinputlisting[label=src:fastcall, caption=コードセグメントへのfastcall属性付与]{src/fastcall.c}

13, 14 行目が fastcall 属性を付与している部分になる.
if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて,
 warning を出すからである.


\section{新しい構文の実装}