%        File: main.tex
%     Created: 日  6 01 18:00 PM 2008 J
% Last Change: 火  6 03 13:19 PM 2008 J
%
%\documentclass[a4j,twocolumn,9pt]{dsw-style/compsoft-dsw08}
\documentclass[ronbun,epsfig]{compsoft-dsw08}
%see /usr/local/ptetex3/share/texmf/ptex/platex209/jarticle.sty
\usepackage[dvipdfm]{graphicx}
\usepackage{verbatim}
\usepackage{nonDefaultPackage/listings}
\usepackage{url}

\title{組み込み向け低レベル言語 CbC の GCC による実装}
\author{与儀 健人 \and 河野 真治}

\renewcommand{\paragraph}[1]{ {\par\vspace{1em}\normalsize\bf #1} }
%\renewcommand{\thepage}{--- \arabic{page} ---}
%\renewcommand{\labelenumi}{\roman{enumi})}
\def\theenumi{\roman{enumi}}
\def\labelenumi{\theenumi)}
%\def\p@enumi{i)}
\renewcommand{\lstlistingname}{リスト}
\lstset{
  language=C,%
  stringstyle=\ttfamily,%
  basicstyle=\small\ttfamily,%
  commentstyle=\itshape,%
  classoffset=1,%
  keywordstyle=\bfseries,%
  framesep=5pt,%
  showstringspaces=false,%
  %frame=tRBl,
  %numbers=left,stepnumber=1,numberstyle=\footnotesize%
}%
\def\lstlistingname{リスト}
\def\lstlistlistingname{プログラムコード目次}




\begin{document}
%\twocolumn[\maketitle]{}
\maketitle

\section{概要}
当研究室ではContinuation based C(以下CbC)という言語を提案しており、
そのコンパイルにはこれまでMicro-Cをベースにした独自のコンパイラを使用していた。
また、以前の論文で
GCCのTail call optimizationを用いてGCC上に実装が可能である事を示した。
ここではGCC上に実際にCbC言語の実装し、その評価を行った。
この実装はアーキテクチャに依存しないので、GCCが対応する全てのアーキテクチャ上でCbCが動く事になるはずであるが、若干の問題があり、その点に付いても考察を行う。


\section{CbCについて}\label{sec:CbC}
Continuation based Cは当研究室が提案するアセンブラよりも上位で
Cよりも下位な記述言語である\cite{kono2}。
Cの仕様からループ制御や関数コールを取り除き、
継続(goto) や コードセグメントを導入している。
これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
ソースコードレベルで行うことができる。

図\ref{fig:continuation}はコードセグメント同士の関係を表したものである。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.45\textwidth,bb=0 0 351 202]{figures/continuation.pdf}
  \end{center}
  \caption{コードセグメント間の``継続''}
  \label{fig:continuation}
\end{figure}%
コードセグメント\verb|start|は実行を終えるとgotoによって
別のコードセグメント \verb|A|もしくは\verb|B|に実行を継続する。
また、\verb|A|から\verb|B|,再び\verb|A|の用に継続を繰り返すことも可能だ。
このように、コードセグメントからgotoを用いて別のコードセグメントへ飛ぶ
構成はオートマトンと似た構造になっていることがわかる。

これらの特徴から、CbCは自身でスケジューラの記述ができ、
それにより並列処理や逐次処理をスムースに繋げることが出来る。
また、OperatingSystemの記述やハードウェアの記述に向いている。

以下では実装に必要なCbCの構文、
コードセグメントの定義と継続(goto)について説明する。
\paragraph{コードセグメント}
はCbCにおける最も基本的な処理単位である。
コードセグメントを定義する構文は通常の関数と同じであるが、型は``\_\_code''となる。
ただし、コードセグメントは関数のようにリターンすることはないので、
これはコードセグメントであることを示すフラグの様なものである。

コードセグメントの処理内容も通常の関数と同じように定義されるが、
Cと違いコードセグメントではforやwhile, returnなどの構文は存在しない。
ループ等の制御は自分自身への再帰的な継続によって実現されることになる。

\paragraph{継続 (goto)}
はコードセグメント間の移動を表す。
構文としてはgotoをつかっているがCにおけるlabelへのgotoとは違い、
gotoの後ろに関数呼び出しの様な形をとる。
例として、あるコードセグメント \verb|cs|への継続は
\verb|goto cs(10, "test");|となる。
これにより、csに対して引数\verb|10|と\verb|"test"|を渡すことができる。
ただし関数コールとは違い、継続ではコールスタックの拡張を行わない。
代わりにgotoを発行したコードセグメントの持つスタック自体に次のコードセグメント
の引数を書き込むことになる。また、returnアドレスのpushなども行わない。

\subsection{CbCの例文}
以上の2つの構文を使った例題をリスト\ref{code:cbc_example}に示す。
\begin{lstlisting}[caption=CbC 例,label=code:cbc_example]
__code while_cond(int total, int count){
    if ( count <= 100 ){
        goto while_process(total,count);
    }else{
        goto while_end(total);
    }
}
__code while_process(int total,
                     int count){
    /* some processes */
    goto while_cond(total, count);
}
__code while_end(int total){
    goto cs_exit(0);
}
\end{lstlisting}
これは単純なループ構造である。
まず\verb|while_cond|が実行されると、そこでは条件判定により
\verb|while_process|か\verb|while_end|に継続する。
\verb|while_process|では処理が終了すると再び\verb|while_cond|に
継続することでループが形成される。
このようにCbCではforやwhileを使用せずコードセグメントから
同じコードセグメントへ継続する形でループが表現される。


\section{GCCの構成}
今回の実装ではGCCのソースコードを修正することになる。
また、GCCの最適化処理の一つであるTail callがその実装に深く関わってくる\cite{kono1}。
この章ではGCCの基本的な動作について簡単に説明する。
\subsection{GCCの基本構造}
GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
以下ではそのpassの中でも重要なものをその実行順に説明する。
\begin{description}
  \item[parsing] パーサによってソースコードを解析する。
        解析した結果はGeneric Treeと呼ばれるtree構造の構造体に格納される。
  \item[gimplification] Generic TreeをもとにこれをGIMPLEに変換する。
  \item[GIMPLE optimization] GIMPLEに対して最適化を行う。
  \item[RTL generation] GIMPLEをもとにRTLを生成する。
  \item[RTL optimization] RTLに対して最適化を行う。
  \item[Output assembly] RTLをもとにターゲットマシンのアセンブリに変換する。
\end{description}
これらの処理は図\ref{fig:GCC-pass}のように表される。
\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=.45\textwidth,bb=0 0 371 214]{figures/GCC-pass.pdf}
  \end{center}
  \caption{GCCのpass}
  \label{fig:GCC-pass}
\end{figure}
各passは通常は各々の関数毎に行われるものだが、
inline関数の処理や、関数間での最適化を行う場合には
一つのソースファイル毎に行われる。

\subsection{Tail call elimination}\label{sec:tailcall}
最適化のひとつである``Tail call elimination''
\footnote{Tail call Optimizationと呼ばれたり、
単にTail callと呼ばれたり、呼称はさまざまである。}
は、
``関数のreturnの前に別の関数呼び出しがある場合はcall命令でなくjump命令が
使える''というアイデアを元に設計されている。
この最適化は本研究におけるCbCコンパイラの実装に深く関わってくるので、
以下で詳しく説明する。

\subsubsection{Tail callの概要}\label{ssec:tailcall}
まずmain関数から関数Aを呼び出していて、
関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える
(図\ref{fig:Tail call}参照)。
このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
そこで再びret命令をつかってmainに戻ることになる。
``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.45\textwidth,bb=0 0 382 263]{figures/GCC-TailCall.pdf}
  \end{center}
  \caption{Tail call eliminationの例}
  \label{fig:Tail call}
\end{figure}

次に``Tail call elimination''によって、
アセンブリレベルでどのようにコードが変わるのか、
スタックの変化も交えて見てみる。
この例では最も一般的に使われているi386形式のアセンブラを使用している。

図\ref{fig:Tail call}と同じように呼び出される関数main, A, Bを
リスト\ref{code:main A B}の様に定義する。
\begin{lstlisting}[caption=関数main\, A\, Bの例,label=code:main A B]
void B(int A, int A, int C){
    /* what do you do?  */
    return ;
}
void A(int a, int b, int c, int d){
    /* some processes..  */
    return B(a, b, c+d);
}
int main(int argc, char **argv){
    A(10, 20, 30, 40);
    return 0;
}
\end{lstlisting}
これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
次のリスト\ref{code:compiled A}のようなコードが出力される。
ここではTailcall最適化が影響をあたえる関数Aのみをしめした。
また、出力アーキテクチャはi386である。
\begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A]
A:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    20(%ebp), %eax
    addl    16(%ebp), %eax
    movl    %eax, 8(%esp)
    movl    12(%ebp), %eax
    movl    %eax, 4(%esp)
    movl    8(%ebp), %eax
    movl    %eax, (%esp)
    call    B
    leave
    ret
    .size   A, .-A
\end{lstlisting}
これを見ても分かる通り、
Tail callをしない場合はAのスタック領域の上にBのスタック領域が確保され、
Bが終了するとそれが破棄される形になる。

次にTail call eliminationが行われた場合の
コンパイル結果をリスト\ref{code:tailcalled A}に示す。
\begin{center}
  \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A]
A:
    pushl   %ebp
    movl    %esp, %ebp
    movl    20(%ebp), %eax
    addl    %eax, 16(%ebp)
    popl    %ebp
    jmp     B
    .size   A, .-A
  \end{lstlisting}
\end{center}
\verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。
ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に
Bのための引数を上書きしていることが分かる。
ただし、変数aとbは書き込む位置も値も変わらないので触れられていない。
また、call命令を使わずにjmpでBに飛んでいる
(そのためリターンアドレスも確保してない)。
これにより、B側ではret命令を発効するとAに戻らず、Aの呼び出し側に直接戻ることになる。

\subsubsection{Tail call時のスタック}
このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.45\textwidth,bb=0 0 528 272]{figures/stack-tailcall.pdf}
  \end{center}
  \caption{関数AからBを呼び出す時のスタックの様子}
  \label{fig:stack-tailcall}
\end{figure}
図\ref{fig:stack-tailcall}の各ステップは次のような状態を表している。
\begin{description}
  \item[(a)] mainからAが呼ばれた直後の状態。espは引数のトップをさしてるが、
    ebpはmainの引数をさしたまま
  \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
  \item[(c)] A自身のスタックフレームにB用の引数をつめる。
  \item[(d)] ebpを元に戻す。その後関数Bにjump。
\end{description}
(a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
しかし、関数AのTail call elimination後のコードを見ても分かる通り、
無駄な処理が少なくなっていることが分かる。
これがTail call eliminationにおける最適化の主な効果である。
最大の効果が得られるのは、caller関数が持っている引数を
callee関数に直接渡す場合である。
この時はスタック操作は全く必要なく、単にjump命令のみになる。

\subsection{Tail callの条件}\label{ssec:tailcallcond}
Tail callが可能かどうかの条件についてここで考察する。

まず最初の条件として、
``関数コールがreturnの直前にある''ということは自明だろう。
また、これに関連して``関数の返す型がcallerとcalleeで一致している''
ことが必要となる。

図\ref{fig:stack-tailcall}の(c)にてcallee関数Bのための引数をスタックに上書きしているが、
この領域はAのためのスタックフレームであることは説明した。
ここでもしBの引数が5つ以上あったらどうなるだろうか?
図を見て分かる通り、mainのスタックまで書きつぶすことになってしまう。
このことから``caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい''
という条件が必要だと分かる。

最後にcallee用の引数を格納する順番が問題になる。
通常、引数は関数定義の右から順にスタックにつめられる。
例えば図\ref{code:main A B}のコードにおいて、AからBの呼び出しが
\verb|B(c, b, c+d)|となっていたらどうだろうか?
最初に\verb|c+d|の書き込みによって変数cは上書きされてしまう。
そのため、最後に書き込む引数cは上書きされたc+dが使われ、
実行結果はまったく違うものになってしまうだろう。
よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
という条件も必要となる。

他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
\begin{enumerate}
  \item 関数コールがreturnの直前にある \label{i}
  \item 関数の返す型がcallerとcalleeで一致している \label{ii}
  \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい \label{iii}
  \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない \label{iv}
\end{enumerate}

CbCコンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。



\section{実装}
次に、実際の実装方法を簡単に説明する。
今回実装したソースコードはSourceForge上の以下のURLにて公開されている。\\
\url{http://sourceforge.jp/projects/cbc/}

実装に置ける最大の問題はgoto文でのコードセグメントへのjump
の際にスタックフレームをどう扱うかということである。
\ref{sec:CbC}章にて説明した通り、CbCではコードセグメントへジャンプした後は
元のコードセグメントには戻らない。
ゆえに通常の関数コールと違い、スッタクを積む必要が無い。
この特性が\ref{ssec:tailcall}で説明したTail callの性質と似ていることを利用し、
``コードセグメントへのgotoはすべてTail callに置き換える''という実装を行う。


\subsection{Tail call条件のパス}
上記のような実装を行う上で、\ref{ssec:tailcallcond}で説明したように、
Tail callの条件を満足させる必要がある。

条件の\ref{i}は簡単に実装できる。
例えば次のような継続文を考える。
\begin{verbatim}
    goto cs(10, "test");
\end{verbatim}
この文を構文解析する際に次のような形に置き換えることになる。
\begin{verbatim}
    cs(10, "test");
    return;
\end{verbatim}
これによりGeneric Treeの段階では単純な関数呼び出しとなるが、
Tail callのフラグをたてることにより、RTL生成時には
jump命令に置き換えられる。

次に条件の\ref{ii}だが、これは``\_\_code''を型に持つものは
すべてvoid型に置き換えることで対応できる。
すなわちコードセグメントの継続はvoid型関数へのTail callとなる。

条件\ref{iii}が最大の問題となる。
もしより大きい引数サイズのコードセグメントにTail callすると、
直前の呼び出した関数スタックを書きつぶしてしまう。最悪Segmentation faultとなる。
今回はこの解決方法として、すべてのコードセグメントでは引数スタックを
一定量とした。
ゆえにこのサイズ以上の引数を持つことはできないが、
これは通常のプログラミングでは問題にならない程度に大きい値にしている。
また、継続の際にはスタック拡張を行わないので、この一定量が大きくなっても
とくに実行速度等に影響はない。

最後に条件\ref{iv}だが、
これは上書きされうる引数がある場合には直前にそれを計算し一時変数に代入するように
修正した。

以上の内容に基づいて修正したソースコードの大半は
RTLを生成部となる。


\begin{comment}
GCCへのCbCのコンパイル機能の実装を行う。
実装における最大の問題はgoto文でのコードセグメントへのjump
の際のスタックフレームの状態をどう扱うかである。
先に述べたようにコードセグメントへ飛ぶ時は Tail call を使用するのだが、
その条件としてcaller関数の引数サイズはcallee関数と同じか
より大きくなければならない。

これを解決するために、この実装ではコードセグメントの
引数サイズを一定にすることにした。
どのようなコードセグメントを定義してもスタックは一定に保たれる。

以下の節ではそれぞれの行程について簡単に説明する。

\subsection{\_\_code基本型の追加とパース}
まず最初に必要となるのが``\_\_code''という予約語を定義することである。
Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されており、
ここに``\_\_code''を定義することで、Tokenizerから
それを予約語として認識できるようになる。

もう一つ必要なものが、\_\_code型であることを示すidである。
これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
データを保持する \verb|c_declapecs|構造体で使用される。
void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
これは gcc/c-tree.h にて定義されており、ここに\verb|cts_CbC_code|を追加する。

以上により、\_\_codeをパースする準備ができた。
実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
\verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
\verb|declspecs_add_type()|関数に統一されている。
この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
以下のようになる。
\begin{lstlisting}[caption=declspecs\_add\_type関数,label=code:declspecs_add_type]
case RID_CbC_CODE:
if (specs->long_p)
  error ("both %<long%> and %<void ..)
else if (specs->signed_p)
  error ("both %<signed%> and %<vo ..)
      :
else
  specs->typespec_word = cts_CbC_code;
return specs;
\end{lstlisting}
これは実際には\verb|case RID_VOID|とほぼ同じである。
違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。
同様にコードセグメントの型はほぼ、void型と同じように扱うことになる。

gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
パースされた型を決定し、その分のちいさなtreeを生成する関数である。
treeにする際はコードセグメントは全てvoidと見なされるようにすることになっている。
よってここで生成するtreeはvoidにしなければならない。
\begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs]
  case cts_void:
  case cts_CbC_code:
    specs->type = void_type_node;
    break;
\end{lstlisting}
これで\_\_codeによる型がvoid型にマップされた。


\subsection{コードセグメント のtree表現}
次に、関数と同じようにパースされるコードセグメントのtreeを
後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
具体的には以下の様な関数になる。
\begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment]
tree
build_code_segment_type(value_type ..)
{
  tree t;
  t = make_node (FUNCTION_TYPE);
  TREE_TYPE (t) = value_type;
  TYPE_ARG_TYPES (t) = arg_types;

  CbC_IS_CODE_SEGMENT (t) = 1;
  if (!COMPLETE_TYPE_P (t))
    layout_type (t);
  return t;
}
\end{lstlisting}
\verb|CbC_IS_CODE_SEGMENT|というマクロがコードセグメントを示すフラグである。
この関数は通常のFUNCTION\_TYPEを作る \verb|build_function_type|と
ほぼ同じ構造になっているが、
このtreeをハッシュ表に登録しないところだけが違っている。

つづいてこの\verb|build_code_segment_type|を使用すべき関数、
\verb|grokdeclarator|を修正する。
この関数は今までパースしてきた情報の入った構造体、
\verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを
gcc/tree.c の関数を使って生成している。

この関数で\verb|build_function_type|関数を使用している箇所
3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。
これを、コードセグメントの場合には\verb|build_code_segment_type|を使うようにする。
\begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator]
if(typespec_word==cts_CbC_code)
    type =build_code_segment_type(..);
else
    type =build_function_type(..);
\end{lstlisting}
これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
コードセグメントかをチェックする時はtree typeに対して
\verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。


\subsection{goto のパース}
つづいてgoto文のパースが必要になる。
goto文は通常のCの構文にも存在するが、CbCではgotoトークンの後に
関数呼び出しと同じ構文がくる。

Cの関数定義をパースしているのは
\verb|c_parser_statement_after_labels|という関数である。
この関数内の巨大な switch文における\verb|case RID_GOTO:|
を修正することになる。
具体的な修正は以下のようになった。
\begin{lstlisting}[caption=goto文の構文解析,label=code:goto_parse]
c_parser_consume_token (parser);
if (c_parser_next_token_is(parser,..)
     && _parser_peek_2nd_token(pars..))
  {
    stmt = c_finish_goto_label(..);
    c_parser_consume_token (parser);
  } else {
    struct c_expr expr;
    expr=c_parser_postfix_expression(..);
    if(TREE_CODE(expr)==CALL_EXPR){
       CbC_IS_CbC_GOTO(expr) = 1;
      CALL_EXPR_TAILCALL(expr) = 1;
      stmt = c_finish_return(expr);
    } else
      c_parser_error (parser, ..);
  }
\end{lstlisting}
gotoトークンを読み込むと、次のトークンが識別子で、その次がセミコロンであれば
通常のCにおけるgotoと判定できる。
そうでなければCbCの継続である。

\subsection{expand\_callの分割}
ここではパーサによって生成されたtreeを元に、
RTLを生成する段階について説明する。

とはいうものの、実際にRTLをいじる必要があるのは
コードセグメントへのjumpのみである。
これはtree上ではTail callと認識されているので、
そのtreeからRTLに変換する関数\verb|expand_call|を修正することになる。

関数\verb|expand_call|は CALL\_EXPR treeをもとに
関数呼び出しの際のスタック領域確保、引数の格納、
関数へのcall命令の発行などを行うRTLを生成している。
しかしこの\verb|expand_call|は約1200行も存在し、
その大半はTail callが可能かの判定をしているにすぎない。
そこでこの実装ではCbCのgotoのためのRTLを生成する関数\verb|expand_cbc_goto|
を新たに作成した。

\subsection{expand\_cbc\_goto}
簡単に説明すると、\verb|expand_cbc_goto|は\verb|expand_call|での
Tail callの処理を可否判定無しで行うものとなる。
大まかな処理内容は以下の通り
\begin{enumerate}
  \item スタックフレームのベースアドレスRTLを取得
  \item 各引数の格納されるアドレスRTLを取得
  \item 各引数の式を計算 (一時的にレジスタに格納)
  \item オーバーラップする引数を一時に変数に格納\label{overlap}
  \item 引数のスタックへの格納
  \item call\_insn RTLの生成
\end{enumerate}

これらの処理はほぼ\verb|expand_call|の内容をそのまま利用できる。
ただし、\ref{overlap}のオーバーラップする引数がある場合のみ問題になる。
gotoの実装には\ref{sec:tailcall}節で説明したTail callを用いているため
引数の書き込み領域と読み込み領域が重なる場合がある。
本来この場合はTail call不能として通常の関数呼出が用いられるところであるが、
CbCではこれを強制しなければならない。
そのため、このように重なる場合は変数の内容を一時退避する必要がある。
次のリスト\ref{code:push_overlaps}がこの処理を書く引数に対して行っている。
\begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
push_overlaps(struct arg_data *args, int num_actuals){
  int i;
  for (i=0; i<num_actuals; i++)
  {
    int dst_offset;
    int src_offset;
    rtx temp;
    if (/*args[i].stackはスタック外*/) continue;
    if (/*args[i].valueはスタック外*/) continue;
    temp =assign_temp(args[i].tree_value..);
    if ( args[i].mode==BLKmode )
      emit_block_move(temp,args[i].value..);
    else
      emit_move_insn(temp,args[i].value);
    args[i].value = temp;
  }
\end{lstlisting}

\end{comment}

\section{環境付き継続に関する考察}\label{sec:env}
また前説までにその実装方法を説明した。
しかしまだ実装されていない構文があるので、その実装方法に関して
ここで考察する。

\subsection{環境付き継続の概念}
環境付き継続は以下に示すように、継続文の後ろに``環境''の値を
明示したものである。
\begin{verbatim}
  goto cs(10, 20), env;
\end{verbatim}
この構文を使用することでスタックフレームを別の(環境envが示す)
領域に切り替えたうえで継続を行うことができる。
例としてリスト\ref{code:envSwitch}の様なコードセグメントが考えられる。
\begin{lstlisting}[caption=環境付き継続 例,label=code:envSwitch]
__code envSwitch(int a, int b, double c)
{
    void *stack;
    if ((stack=malloc(STACKSIZE))==NULL)
        goto error(no);

    goto envCheck(10, 20), stack+OFFSET;
}
\end{lstlisting}
このコードセグメントenvSwitchではスタック領域をmallocで取得した領域に切り替えた
上でenvCheckに継続する
\footnote{この構文を使用し、複数のスタックを交互に切り替える等の
処理を行うことでタブロー法などの検証を行うのがCbCの目的でもある。}。

また、この構文を使ってコードセグメントを呼び出した関数に戻ることも可能となる。
それにはこの関数側でも若干の修正が必要で、\verb|__return, __environment|
という二つの定義済み変数を使用する。
これらはそれぞれコードセグメントから関数への戻り先とその時のスタックフレームの
位置を表している。
これらをリスト\ref{code:ret2func}の様に用いることで
\verb|env_func|を呼び出した関数まで戻ることができる。
また、\verb|env_code|環境付きgotoで与えている引数は\verb|env_func|の戻り値と
して扱われる。
\begin{lstlisting}[caption=呼び出し元の関数へのgoto例,label=code:ret2func]
__code env_code(int a, int b,
             void *env, void *_ret)
{
    __code (*ret)(int, int, int);
    ret = _ret;
    goto ret(20), env;
}
int env_func(int a, int b, double c)
{
    goto env_code(20, 30,
        __environment, __return);
    /* unreachable */
}
\end{lstlisting}


\subsection{実装方法に関する考察}
環境付き継続の実装方法について考察を行う。
環境付き継続では通常の関数コールや継続と違い、スタックフレームを変更するため、
現在のスタックフレームの位置をさすレジスタを変更しなければならない。
理想的なリスト\ref{code:envSwitch}のコンパイル結果は以下のようになる。
\begin{lstlisting}[caption=環境付き継続 出力例,label=code:envSwitch_out]
    movl    $env, $eax
    movl    $10, 8(%eax)
    movl    $20, 12(%eax)
    movl    %eax, %ebp
    jmp     envCheck
\end{lstlisting}
この結果なら新たなスタックフレームenvの先に引数を格納し、
かつ\verb|%ebp|レジスタを置き換えた上でコードセグメントに継続している。

しかし、現在のTail callを用いた仕様ではいくつかの問題点がある。
一つは``Tail callはjmp命令の直前に必ず\verb|%ebp|を変更する''ということである。
さらに``環境''の値から引数を格納する位置までのオフセットを計算する必要がある。
これはGCCではRTLとして\verb|virtual_incoming_args_rtx|や\verb|hard_frame_pointer_rtx|
などの固定レジスタ値が用意されてるので、これを用いて計算できるだろう。
最後に、関数の呼び出し側に戻る時の\verb|__return|変数の定義が必要となる。
この変数はただ値をつくるだけでなく、この変数が使われている場合には
特殊なコードを生成する必要がある。



\section{評価}
今回、環境付き継続は実装には至らなかったが、
残りの部分は実装完了した。そこでベンチマークテストを行い、
Micro-Cとの比較を行った。

今回ベンチマークに使用したプログラムはこれまでもMicro-Cの測定に使われていた
テストルーチンで、普通のCのソースをプログラムでCbCに変換したものである。
引数に1を入れるとそれが変換されたCbCのコード、
引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
また、評価はia32アーキテクチャのFedora上で行った。
一番結果の良い引数2の場合のコードセグメントをリスト\ref{code:bench}に示す。
\begin{lstlisting}[caption=bench,label=code:bench]
__code  f2(int i,char *sp) {
    int k,j;
    k = 3+i;
    goto g2(i,k,i+3,sp);
}
__code g2(int i,int k,int j,char *sp){
    j = j+4;
    goto h2(i,k+4+j,sp);
}
__code h2_1(int i,int k,int j,char *sp){
    goto main_return2(i+j,sp);
}
__code h2(int i,int k,char *sp) {
    goto h2_1(i,k,i+4,sp);
}
\end{lstlisting}
このベンチマークではCbCの継続と計算を交互に行っている。
測定結果は表\ref{tab:mc,gcc,compare}に示される。
\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|l|r|r|r|} \hline
    & ./conv1 1 & ./conv1 2 &  ./conv1 3 \\ \hline
    Micro-C         & 8.97 & 2.19 & 2.73 \\ \hline \hline
    GCC             & 4.87 & 3.08 & 3.65 \\ \hline
    GCC (+omit)     & 4.20 & 2.25 & 2.76 \\ \hline
    GCC (+fast) & 3.44 & 1.76 & 2.34 \\ \hline \hline
  \end{tabular}
  \caption{Micro-C, GCCの実行速度比較 (単位 秒)}
  \label{tab:mc,gcc,compare}
\end{table}

通常のTail call eliminationのみを有効にした場合の結果が2行目、
その他は次節で説明するオプションを付加したものである。
見てのとおり、手動で最適化された引数2,3の場合はオプションを加えなければ
Micro-Cの速度に及ばなかった。次節ではこの点について考察する。

\subsection{出力コード}
先ほどのリスト\ref{code:bench}のコードセグメント g2のみをMicro-Cでコンパイルした結果
をリスト\ref{code:bench_mc}, 
GCCのオプション無しによるコンパイル結果をリスト\ref{code:bench_gcc}に示す。
\begin{lstlisting}[caption=Micro-Cによる出力コード,label=code:bench_mc]
f2:
    lea -_44(%ebp),%esp
    movl $3,%eax
    addl %esi,%eax
    movl %eax,-28(%ebp)
    movl %edi,-32(%ebp)
    movl -28(%ebp),%edi
    movl %esi,%eax
    addl $3,%eax
    movl %eax,-28(%ebp)
    jmp g2
\end{lstlisting}
\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc]
f2:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %eax
    movl    12(%ebp), %ecx
    leal    3(%eax), %edx
    movl    %edx, 12(%ebp)
    movl    %edx, 16(%ebp)
    movl    %ecx, 20(%ebp)
    popl    %ebp
    jmp     g2
\end{lstlisting}
このとおり出力コードは10命令と、行数にはあまり差が無い。(他のsegmentも同様である)
しかしGCCの出力においては無駄なコードが混じっていることがわかるだろう。
\verb|pushl%ebp|と\verb|popl %ebp|である。
すべてのコードセグメントにおいてこれと同じ命令が出てしまっているが、
これはTailcallを無理矢理適用したために出てきたコードである。

このような関数の最初と最後にある無駄なフレームポインタのpushを抑制するオプションが
-fomit-frame-pointerである。このオプションを付加するとリスト\ref{code:bench_gcc_omit}
\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_omit]
f2:
    movl    4(%esp), %eax
    movl    8(%esp), %ecx
    leal    3(%eax), %edx
    movl    %edx, 8(%esp)
    movl    %edx, 12(%esp)
    movl    %ecx, 16(%esp)
    jmp     g2
\end{lstlisting}
これによって一気に3命令減った。ベンチマークは表\ref{tab:mc,gcc,compare}の3行目、``GCC (+omit)''である。
しかし、(コードセグメントにもよるが)3/10命令減ったにもかかわらずMicro-Cとの速度差が
ほとんど無い。

リスト\ref{}をみるとMicro-Cでは引数の格納にレジスタ\%edi と
\%esi を用いる分、高速なコードを生成出来ていることが分かる。
この違いが命令数の差を埋めている。
GCCでも引数をレジスタに詰めることができるfastcall属性がある。
-fomit-frame-pointerに加えてfastcallを付加した結果をリスト\ref{code:bench_gcc_fast}
に示す。
\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_fast]
f2:
    movl    %edx, %eax
    leal    3(%ecx), %edx
    movl    %edx, 4(%esp)
    movl    %eax, 8(%esp)
    jmp     g2
\end{lstlisting}
命令数はさらに2命令減り、またメモリへのアクセスが減ったため
ベンチマーク結果(表\ref{tab:mc,gcc,compare}GCC (+fast))も大幅に改善した。

この評価結果から、GCCの最適化オプションを用いることで
CbCコードのさらなる高速化が可能であることが示された。
また、使用したベンチマークプログラムはCのコードをプログラムで
CbCに変換したものだが、これをCのままコンパイルすると
最適化をかけても約3.3秒かかる。
このように不要なスタック操作を減らすことによって、
C言語のみでは不可能な手動による最適化がCbCの利点としてあげられる。





\section{まとめ}
本研究の実装により、GCCを使ってCbCのソースコードを
コンパイルすることができるようになった。
その結果、これまでのMicro-Cベースのコンパイラではできなかった
最適化をGCC上で実行できるようになり、CbCプログラムをより高速化することに成功した。
また、環境付き継続の実装方法に関して考察を行いその問題点を洗い出した。

今後は\ref{sec:env}で説明した様に環境付き継続の
実装が課題となる。
また、SPUアーキテクチャにGCCが対応してないという問題もある。
今回の実装の目的の一つとしてPS3上でCbCを動かしたいということがあったので、
この問題についてはPS3SDKとのマージも一つの手法として考えている。
これらに加えて、GCCはすでにC++やObjective-C のコンパイルが可能である。
これを活かし、CbC++, もしくはObjective-CbC といった
既存の言語とCbC を組み合わせた言語に付いても今後実装していく。


\begin{thebibliography}{9}
  \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''.
	日本ソフトウェア科学会第19回大会論文集, Sep, 2002.
  \bibitem{kono2} 河野真治. ``継続を持つCの下位言語によるシステム記述''.
	日本ソフトウェア科学会第17回大会論文集, Sep, 2000.
  \bibitem{c--} Simon Peyton Jones, Thomas Nordin, and Dino Oliva, ``C--: a portable assembly language''. Implementing Functional Languages, 1997.
  \bibitem{gcc1} GNU Project - Free Software Foundation, GCC internal manual.
    \url{http://gcc.gnu.org/onlinedocs/gccint/}.
\end{thebibliography}

\end{document}