\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{url}
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{listings}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Continuation based C コンパイラのGCC-4.6における実装}
\author{学籍番号:085711E 氏名:大城信康 {}{} 指導教員 : 河野真治}
%\date{H23 11/18 fri}
\maketitle
\thispagestyle{fancy}

\section{研究背景と目的}
当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.

GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.

%\subsection{研究内容}
%今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った.

%現在の GCC ベースの CbC (以下CbC-GCC) コンパイラには幾つかのバグが見られる.
%特に Code Segmtne への処理移動が jmp でなく call で行われる部分あげられる.
%現在 CbC を実装した GCC コンパイラのバージョンは,初めに実装が行われた GCC-4.2 よりバージョンを上げた GCC-4.5 となる.
%本研究では,CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする.
%また,GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う.
\section{Continuation basede C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

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

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

%また,コードセグメント間の移動は軽量継続によって行われる.
%プログラムの末尾に次のコードセグメントを記述し処理を続けていく.
%コードセグメントの記述の仕方は C の関数の記述と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
%コードセグメントへの処理の移りは call ではなく jmp で行われ,その為 C の関数の様に呼び出し元への復帰がない.
%構文では“\_\_code”で関数を宣言することでコードセグメントとして扱うようにしている.

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

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


%だが,返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ.

\section{GCC-4.6 への実装}
% \subsection{軽量継続の実装}
GCCでの計量継続を Tail Call Ellimination (末尾除去)を強制することで実装する.
これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
コードセグメント自体には戻値はない.

%「caller側とcallee側の返り値の型が同じ」といった,幾つかのの条件下において行われる最適化になる.
図\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}

\subsection{expand\_call 関数}
GCCでは, ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で以下の条件で判断される.

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

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

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

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


%\subsubsection{try_tail_call フラグ}
%Tail Call Elimination が可能である場合,try_tail_call フラグが立てられる.
%コードセグメントへの jmp は Tail Call Elimination を受けることで実装される.
%軽量継続において重要なのは上記でも述べた Tail Call Elimination に必要な幾つかの条件をクリアすることであった.
%最初に開発された CbC-GCC ではコードセグメントの場合は上記の『ある特定の条件』をクリアするよう実装されていた.
%しかし,CbC のコードをアセンブラに出力してみると幾つか call で呼び出されていることが分かった.
%この問題を解決し,全てのコードセグメントは jmp によって呼びされるようにする必要がある.


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


%\subsubsection{typedefrec の実装方法}
%typedefrec 

%GCC における C の構文解析では,関数名はハッシュテーブルによって管理される.
%ここで問題となるのが,関数の宣言を全て読んだ後にハッシュテーブルに追加されるということである.
%その為,関数の引数に自身の関数名がでるとそのような関数はないとエラーにされてしまう.
%そこで typedefrec の付いた関数は先行して宣言を行うことにする.
%すると,宣言中でもハッシュテーブルから関数の情報をとることができるようになる.

%\subsection{\_\_return 変数}
\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
これを環境付き継続という.
これらは, 以下の二種類の CbC で定義した特殊変数である.
\_\_environment は, 環境を表す情報である.
\_\_return は,  これを環境付き継続の行き先であり, 関数の戻値と \_\_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; // should be thread local                                                                                                                                                   
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 を用いた実装方法もある.


\section{現状と今後の課題}
%アセンブラ出力を見ることができ,gdb を使ってのデバッグが可能になったことである.
%CbC-GCC により CbC のプログラム開発が行いやすくなった.
%CbC-GCC は GCC に合わせてアップデートされてきた.
%しかし,アップデートに伴い幾つか実装を見直す必要がでてきた.
%同時に,現時点で見つかっている問題以外にもバグが無いかを調べていく.
今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく.
また, 実装後は, 32ビット, 64ビットそれぞれでコンパイルしたプログラムの比較,
 それと Micro-C による実装との性能比較も行う予定である.

時間があれば, LLVM での実装, コードセグメントの宣言に便利な \verb+typedefrec+ の実装,
 あるいは, Google go 言語での実装などの研究も行う予定である.


%今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある.
%また,CbC を GCC だけでなく LLVM での実装や,C 言語以外の言語への変更も検討していく.

\thispagestyle{fancy}
\begin{thebibliography}{3}

\bibitem{1}{河野真治}:
“継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002

\bibitem{2}{与儀健人,河野真治}:
“Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008

\bibitem{3}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}
\end{document}