%        File: main.tex
%     Created: 日  3 23 18:00 PM 2008 J
% Last Change: 火  3 25 02:40 PM 2008 J
%
\documentclass[a4j,twocolumn,9pt]{jarticle}
\usepackage{main}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{nonDefaultPackage/listings}


\jtitle{Continuation based CコンパイラのGCC-4.2による実装}
\etitle{The implementation of Continuation based C Compiler on GCC} 
\jaffiliation{琉球大学理工学研究科情報工学専攻}
\eaffiliation{Information Engineering, University Of the Ryukyus}
\jauthor{与儀 健人 \hspace{2cm} 河野 真治}
\eauthor{KENT yogi \hspace{2cm} Shinji KONO}
\year{平成19年度}
\thesis{OS研究会}
%\logo{%\includegraphics[width=15em]{figures/u-ryukyu-Mark.eps}}

\jabstract{
当研究室ではContinuation based Cという言語を提案しており、
そのコンパイルにはこれまでMicro-Cをベースにした独自のコンパイラを使用していた。
また、GCCのTail call optimizationを用いた実装が可能である事を以前の論文で示した。
ここではGCC上に実際にCbC言語の実装し、その評価を行った。
この実装はアーキテクチャに依存しないので、
GCCが対応する全てのアーキテクチャ上でCbCが動く事になるはずであるが、
若干の問題があり、その点に付いても考察を行う。
}
\eabstract{
We are approach Continuation based C Language, 
and have used Micro-C based Compiler that is developed by us to compile it.
This research, We are implement a compiler for CbC into GCC and 
appraising it.
This implementation is supposed
to run on all archtectures that is supported by GCC,
but few problems are founded.
}


\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{プログラムコード目次}



\renewcommand{\thepage}{--- \arabic{page} ---}
\begin{document}
\twocolumn[\maketitle]{}

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

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

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

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

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

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


\section{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=.5\textwidth]{figures/GCC-pass.eps}
  \end{center}
  \caption{GCCのpass}
  \label{fig:GCC-pass}
\end{figure}
各passは通常は各々の関数毎に行われるものだが、
inline関数の処理や、関数間での最適化を行う場合には
一つのソースファイル毎に行われる。

\subsection{Tail call elimination}\label{sec:tailcall}
最適化のひとつである``Tail call elimination''は、
本研究におけるCbCコンパイラの実装に深く関わってくる。
本節ではこの最適化機構について詳しく説明する。

\subsubsection{Tail callの概要}
具体的に説明する。
まずmain関数から関数Aを呼び出していて、
関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える。
このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
そこで再びret命令をつかってmainに戻ることになる。
``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=0.5\textwidth]{figures/GCC-TailCall.eps}
  \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){
    return ;
}
void A(int a, int b, int c, int d){
    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のみをしめした)
\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は書き込む位置も値も変わらないので触れられていない。

\subsubsection{Tail call時のスタック}
このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.5\textwidth]{figures/stack-tailcall.eps}
  \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の条件}
Tail callが可能かどうかの条件についてここで考察する。
必要に応じて前節の図\ref{fig:stack-tailcall}と、リスト\ref{code:main A B}
を説明に用いるので参考にしていただきたい。

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

図の(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{itemize}
  \item 関数コールがreturnの直前にある
  \item 関数の返す型がcallerとcalleeで一致している
  \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
  \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
\end{itemize}

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



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

これを解決するために、この実装ではcode segmentの
引数サイズを一定にすることにした。
どのようなcode segmentを定義してもスタックは一定に保たれる。

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

\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|のみとなる。
同様にcode segmentの型はほぼ、void型と同じように扱うことになる。

gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
パースされた型を決定し、その分のちいさなtreeを生成する関数である。
treeにする際はcode segmentは全て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{code segment のtree表現}
次に、関数と同じようにパースされるcode segmentの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|というマクロが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:|の部分である。
これを、code segmentの場合には\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にフラグが付くようになった。
code segmentかをチェックする時は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をいじる必要があるのは
code segmentへの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}

\section{評価}
今回実装できたGCCによるCbCコンパイラでベンチマークを行い、
Micro-Cとの比較を行った。

今回ベンチマークに使用したプログラムはこれまでもMicro-Cの測定に使われていた
テストルーチンで、普通のCのソースをプログラムでCbCに変換したものである。
引数に1を入れるとそれが変換されたCbCのコード、
引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
また、評価はia32アーキテクチャのFedora上で行った。
一番結果の良い引数2の場合のcode segmentをリスト\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}のcode segment 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|である。
すべてのcode segmentにおいてこれと同じ命令が出てしまっているが、
これは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)''である。
しかし、(code segmentにもよるが)3/10命令減ったにもかかわらずMicro-Cとの速度差が
ほとんど無い。

リスト11をみると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上で実行できるようになった。

しかしまだいくつかの問題が残っているので、
今後の課題と併せて、以下に簡単に説明する。
\begin{description}
  \item[environment]
    CbCにはもう一つ、environment付きの継続という構文が存在する。
    これは関数からcode segmentにgotoした場合に関数の呼び出し元に戻る
    ことを可能にするものだが、今回この実装は間に合わなかった。
  \item[PPCのRTL変換不能] PowerPCアーキテクチャにおいて、code segment
    のポインタ参照へgotoすることができない。
    これはRTLレベルで対応されてないことが原因と思われる。
  \item[オプションの強制] -O2オプションや、code segmentへのfasecall属性の付加
    などを強制させる必要がある。
  \item[SPU対応とGCCのversion] 実装できたversionは4.2.3である。
    しかし現在SPUに対応したGCCは4.1までしかでていないうえに、
    GCCのversion間の差異によって移植が難しくなっている。
\end{description}
ここで、二つ目のPowerPCへの対応が大きな問題となっている。
本来、このコンパイラはアーキテクチャに依存しない形で
実装したのが、実装後、PowerPCはTailcall eliminationにたいして一部対応してない
ことがわかった。
これはMachineDescriptionとよばれるRTLからアセンブラへの対応を表す
ファイルを記述することで対応させることができるはずだが、今回その実装には至らなかった。

またこれらに加えて、GCCはすでにC++や
Objective-C のコンパイルが可能である。これを活かし、
CbC++, もしくはObjective-CbC といった
既存の言語とCbC を組み合わせた言語に付いても今後実装していく。
%考えてみる価値があるだろう。


\small
\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.
	``http://gcc.gnu.org/onlinedocs/gccint/''.
\end{thebibliography}

\renewcommand{\thepage}{--- \arabic{page} ---E}
\end{document}