# HG changeset patch
# User Nobuyasu Oshiro  <dimolto@cr.ie.u-ryukyu.ac.jp>
# Date 1321786592 -32400
# Node ID 7de00dc2a9975e05e699108e0e67fa15a81c50e9
# Parent  4533a7f9f594eb53504d96bece5d99645a7ce040
modify

diff -r 4533a7f9f594 -r 7de00dc2a997 Paper/nobu-prosym.tex
--- a/Paper/nobu-prosym.tex	Sun Nov 20 19:38:17 2011 +0900
+++ b/Paper/nobu-prosym.tex	Sun Nov 20 19:56:32 2011 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
\usepackage{jtygm}


% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の GCC 4.6 上の実装について]%
	{Continuation based C の GCC 4.6 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on GCC 4.6}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{大城 信康\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{大城 信康\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: dimolto@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
GCC-4.6 をベースとした CbC コンパイラの実装を行った.
CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
本論文では GCC-4.6 への CbC の具体的な実装について述べる。


%当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
%また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
%お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.


\end{abstract}


% 英文概要
\begin{eabstract}
We implemented Continuation based C Compiler on GCC-4.6.
CbC Compiler on GCC-4.2 was developed on 2008.
Since then we kept to update it.
In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

%Continuation based C is programming language. It is developing our laboratory.

\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

% 本文はここから始まる
\section{歴史的経緯}
%当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
%CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.

CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
2010年には GCC-4.4 へとアップデートが行われた.
GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
%以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
%今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
%本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.


%}{

\section{Continuation based C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

%Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
%構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
%また,コードセグメント単位で処理を記述するという特徴がある.
%図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.


\subsection{継続(goto)}
コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる.
コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

%コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
%コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
%この goto によるコードセグメント間の移動を継続と言う.
%継続の実態は jmp による関数の移動となる.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}

\subsection{コードセグメント(code segment)}
コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.

軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}
\lstinputlisting[language=c]{source/factorial.cbc}
\caption{階上を計算する CbC プログラムの例}
\label{fig:factorial}
\end{figure}

%CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
%コードセグメントの記述の仕方は C の関数と同じだが, 型に ``\_\_code''を使って宣言を行うところだけが違う.
%関数と同じように引数を持たせて継続させることもできる.
%しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.

%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.

GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.

CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsection{GIMPLE}
Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.


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


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
  \end{center}
  \caption{\_\_code のパース}
  \label{fig:code-parse}
\end{figure}


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-id.eps}}
  \end{center}
  \caption{cts\_CbC\_code の定義}
  \label{fig:code-id}
\end{figure}

後は\verb+c_declspecs+ 構造体にこの id を登録する.
 id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-id.eps}}
  \end{center}
  \caption{id の登録(declspecs\_add\_type 関数)}
  \label{fig:regi-id}
\end{figure}

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

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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
  \end{center}
  \caption{declspecs\_add\_type 関数}
  \label{fig:regi-node}
\end{figure}


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/rid-goto.eps}}
  \end{center}
  \caption{goto へのシンタックスの追加}
  \label{fig:rid-goto}
\end{figure}

%具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した.
具体的には
void 型の tree を元にコードセグメントと判定するフラグ と Tail Call のフラグ
を付けた関数として tree の作成を行なっている.

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

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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻値を funcB ではなく funcA へと返すことになる.

\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
\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 goto の直後に retrun を置く．
  \item スタックサイズは関数宣言時に決まったサイズにする．
  \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
%\end{itemize}
\end{enumerate}

1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
2, 3 と 4 については以下で詳しく説明を行う.

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

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
__code factorial0(int prod, int x)
{
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
    return;
  }else{
    goto print_factorial(prod);
    return;
  }
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}
CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
図\ref{fig:rid-goto}の\verb+c_finish_return+ 関数がそれにあたる.

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

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

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

%GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも
%Tail Call Elimination にかからないコードセグメントがある.
%この点を改善する必要がある.

%\subsection{引数の一時変数への避難}
%\subsection{スタック書き換えの問題}
\subsubsection{引数の並びの上書きコピー}
CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
例えばlistlising\ref{code:cs_prog}のような継続である.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
__code cs_a(int a, int b) {
        goto cs_b(b, a)
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}


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

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

図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる.
%\begin{figure}
%\lstinputlisting[language=c]{source/cbc_replace_arguments.c}
%\caption{引数の一時変数へのコピー}
%\label{fig:cbc_replace}
%\end{figure}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cbc_replace.eps}}
  \end{center}
  \caption{引数の一時変数へのコピー}
  \label{fig:cbc_replace}
\end{figure}


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

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

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

\begin{verbatim}
__code c1(__code ret(int,void *),void *env) {
    goto ret(1,env);
}

int main() {
    goto c1(__return, __environment);
}
\end{verbatim}

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

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
__label__ _cbc_exit0;
static int retval;
   void _cbc_internal_return(int retval_,
                            void *_envp){
  retval = retval_;
  goto _cbc_exit0;
}
if (0) {
 _cbc_exit0:
  return retval;
 }
_cbc_internal_return;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

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


\subsection{引数渡し}
通常コードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメント間を継続することで, 速度の向上を図る.

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

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}

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


\subsection{typedefrecの実装の構想}
C では関数や構造体の宣言の時に自分自身を引数にすることができない。
そこで ``typedefrec'' という構文を作り、図\ref{code:typedefrec}のような宣言を行えるようにしたい。

%C を基本としている CbC には型推論がない.

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=typedefrecの例,label=code:typedefrec]
typedefrec void *funcA(int, funcA);

typedefrec struct {
  NODE left;
  NODE right;
} *NODE;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

typedefrec によりコードセグメントは自分自身に戻る構成ができるようになる.
より柔軟なプログラミングが行えるように typdefrec の実装を行う予定である.

\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
%クイックソートは再帰的にプログラムされる為 CbC に向いている
%プログラムだと言える.
クイックソートは再帰的なプログラムな為スタック操作が行われる.
比較を行うのは以下のアーキテクチャと OS になる.

%\begin{description}
\begin{itemize}
  \item x86/Linux
  \item x86/OS X
\end{itemize}
%\end{description}

また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.829 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.252 & 2.906 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}


\section{CbC のアップデート手法}
最後に, CbC のアップデート手法について述べる.

現在 GCC は年に数回アップデートが行われている.
GCC に合わせて CbC のアップデートを行うのが好ましいが,
 その度新しいソースコードに合わせていくのは負担が大きい.
GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが
現時点ではまだそこまで至っていない.

そこで Mercurial を使ってアップデート方法を行なっている.

\subsection{Mercurial によるアップデート}
Mercurial はバージョン管理システムである.
当研究室では CbC のソースコードは Mercurial によって管理されている.
Mercurial では本家 GCC のソースコードも管理されており,
これら 2 つのリポジトリを使って CbC のアップデートは行われる.
具体的な方法は以下になる.

\begin{itemize}
\item GCC リポジトリ
\begin{enumerate}
\item GCC リポジトリの中身を削除 (バージョン管理情報以外)
\item 新しい GCC のソース入れる
\item hg status で追加ファイルと削除ファイルを確認.
\item 追加, 削除するファイルに対して hg add, hg remove を行う.
\item コミット
\item gcc version タグを追加する.
\end{enumerate}

\item CbC リポジトリ
\begin{enumerate}
\item GCC リポジトリから hg pull を行う
\item hg merge でマージを行う
\item 衝突が発生したファイルを

\end{enumerate}
\end{itemize}


\section{まとめと今後の課題}
今回 CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った.
だが, 環境付き継続等未だ幾つかの問題を残している.
また, typedefrec の様に新たに実装を行いたい機能もでてきている.



\nocite{kono:2002a, kono:2008a, yogi:2008a, gcc_internals}
\bibliographystyle{junsrt}
\bibliography{cbc.bib}

\end{document}
\ No newline at end of file
+\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
\usepackage{jtygm}


% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の GCC 4.6 上の実装について]%
	{Continuation based C の GCC 4.6 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on GCC 4.6}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{大城 信康\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{大城 信康\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: dimolto@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
GCC-4.6 をベースとした CbC コンパイラの実装を行った.
CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
本論文では GCC-4.6 への CbC の具体的な実装について述べる。


%当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
%また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
%お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.


\end{abstract}


% 英文概要
\begin{eabstract}
We implemented Continuation based C Compiler on GCC-4.6.
CbC Compiler on GCC-4.2 was developed on 2008.
Since then we kept to update it.
In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

%Continuation based C is programming language. It is developing our laboratory.

\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

% 本文はここから始まる
\section{歴史的経緯}
%当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
%CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.

CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
2010年には GCC-4.4 へとアップデートが行われた.
GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
%以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
%今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
%本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.


%}{

\section{Continuation based C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

%Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
%構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
%また,コードセグメント単位で処理を記述するという特徴がある.
%図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.


\subsection{継続(goto)}
コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる.
コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

%コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
%コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
%この goto によるコードセグメント間の移動を継続と言う.
%継続の実態は jmp による関数の移動となる.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}

\subsection{コードセグメント(code segment)}
コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.

軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}
\lstinputlisting[language=c]{source/factorial.cbc}
\caption{階上を計算する CbC プログラムの例}
\label{fig:factorial}
\end{figure}

%CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
%コードセグメントの記述の仕方は C の関数と同じだが, 型に ``\_\_code''を使って宣言を行うところだけが違う.
%関数と同じように引数を持たせて継続させることもできる.
%しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.

%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.

GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.

CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsection{GIMPLE}
Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.


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


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
  \end{center}
  \caption{\_\_code のパース}
  \label{fig:code-parse}
\end{figure}


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-id.eps}}
  \end{center}
  \caption{cts\_CbC\_code の定義}
  \label{fig:code-id}
\end{figure}

後は\verb+c_declspecs+ 構造体にこの id を登録する.
 id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-id.eps}}
  \end{center}
  \caption{id の登録(declspecs\_add\_type 関数)}
  \label{fig:regi-id}
\end{figure}

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

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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
  \end{center}
  \caption{declspecs\_add\_type 関数}
  \label{fig:regi-node}
\end{figure}


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/rid-goto.eps}}
  \end{center}
  \caption{goto へのシンタックスの追加}
  \label{fig:rid-goto}
\end{figure}

%具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した.
具体的には
void 型の tree を元にコードセグメントと判定するフラグ と Tail Call のフラグ
を付けた関数として tree の作成を行なっている.

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

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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻値を funcB ではなく funcA へと返すことになる.

\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
\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 goto の直後に retrun を置く．
  \item スタックサイズは関数宣言時に決まったサイズにする．
  \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
%\end{itemize}
\end{enumerate}

1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
2, 3 と 4 については以下で詳しく説明を行う.

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

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
__code factorial0(int prod, int x)
{
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
    return;
  }else{
    goto print_factorial(prod);
    return;
  }
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}
CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
図\ref{fig:rid-goto}の\verb+c_finish_return+ 関数がそれにあたる.

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

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

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

%GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも
%Tail Call Elimination にかからないコードセグメントがある.
%この点を改善する必要がある.

%\subsection{引数の一時変数への避難}
%\subsection{スタック書き換えの問題}
\subsubsection{引数の並びの上書きコピー}
CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
例えばlistlising\ref{code:cs_prog}のような継続である.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
__code cs_a(int a, int b) {
        goto cs_b(b, a)
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}


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

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

図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる.
%\begin{figure}
%\lstinputlisting[language=c]{source/cbc_replace_arguments.c}
%\caption{引数の一時変数へのコピー}
%\label{fig:cbc_replace}
%\end{figure}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cbc_replace.eps}}
  \end{center}
  \caption{引数の一時変数へのコピー}
  \label{fig:cbc_replace}
\end{figure}


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

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

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

\begin{verbatim}
__code c1(__code ret(int,void *),void *env) {
    goto ret(1,env);
}

int main() {
    goto c1(__return, __environment);
}
\end{verbatim}

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

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
__label__ _cbc_exit0;
static int retval;
   void _cbc_internal_return(int retval_,
                            void *_envp){
  retval = retval_;
  goto _cbc_exit0;
}
if (0) {
 _cbc_exit0:
  return retval;
 }
_cbc_internal_return;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

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


\subsection{引数渡し}
通常コードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメント間を継続することで, 速度の向上を図る.

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

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}

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


\subsection{typedefrecの実装の構想}
C では関数や構造体の宣言の時に自分自身を引数にすることができない。
そこで ``typedefrec'' という構文を作り、図\ref{code:typedefrec}のような宣言を行えるようにしたい。

%C を基本としている CbC には型推論がない.

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=typedefrecの例,label=code:typedefrec]
typedefrec void *funcA(int, funcA);

typedefrec struct {
  NODE left;
  NODE right;
} *NODE;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

typedefrec によりコードセグメントは自分自身に戻る構成ができるようになる.
より柔軟なプログラミングが行えるように typdefrec の実装を行う予定である.

\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
%クイックソートは再帰的にプログラムされる為 CbC に向いている
%プログラムだと言える.
クイックソートは再帰的なプログラムな為スタック操作が行われる.
比較を行うのは以下のアーキテクチャと OS になる.

%\begin{description}
\begin{itemize}
  \item x86/Linux
  \item x86/OS X
\end{itemize}
%\end{description}

また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.829 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.252 & 2.906 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}


\section{CbC のアップデート手法}
最後に, CbC のアップデート手法について述べる.

現在 GCC は年に数回アップデートが行われている.
GCC に合わせて CbC のアップデートを行うのが好ましいが,
 その度新しいソースコードに合わせていくのは負担が大きい.
GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが
現時点ではまだそこまで至っていない.

そこで Mercurial を使ってアップデート方法を行なっている.

\subsection{Mercurial によるアップデート}
Mercurial はバージョン管理システムである.
当研究室では CbC のソースコードは Mercurial によって管理されている.
Mercurial では本家 GCC のソースコードも管理されており,
これら 2 つのリポジトリを使って CbC のアップデートは行われる.
具体的な方法は以下になる.

\begin{itemize}
\item GCC リポジトリ
\begin{enumerate}
\item GCC リポジトリの中身を削除 (バージョン管理情報以外)
\item 新しい GCC のソース入れる
\item hg status で追加ファイルと削除ファイルを確認.
\item 追加, 削除するファイルに対して hg add, hg remove を行う.
\item コミット
\item gcc version タグを追加
\end{enumerate}

\item CbC リポジトリ
\begin{enumerate}
\item GCC リポジトリから hg pull を行う
\item hg merge でマージを行う
\item 衝突が発生したファイルのマージを行う
\item ビルドを行い動作確認
\item コミット
\item gcc version タグを追加
\end{enumerate}
\end{itemize}



\section{まとめと今後の課題}
今回 CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った.
だが, 環境付き継続等未だ幾つかの問題を残している.
また, typedefrec の様に新たに実装を行いたい機能もでてきている.



\nocite{kono:2002a, kono:2008a, yogi:2008a, gcc_internals}
\bibliographystyle{junsrt}
\bibliography{cbc.bib}

\end{document}
\ No newline at end of file