\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) を開発している。
また CbC の開発と共に CbC のコンパイラの開発も行なってきた。
2008年には GCC-4.2 をベースとした CbC のコンパイラ (以下 CbC-GCC) が開発され、GCC の最適化やデバッグ、他アーキテクチャへの対応と言った恩恵を受けられるようになった。
以降、GCC のアップデートに合わせて CbC-GCC のアップデートも行ってきた。

本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行う。

%\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)}
Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である。
CbC のプログラムはコードセグメント毎に記述され、コード間を軽量継続により処理を移るという特徴を持つ。
構文は C と同じであるが、ループ制御や関数コールが取り除かれる。

\subsection{コードセグメント}
CbC においてのプログラムの基本単位としてコードセグメントという概念がある。
記述の仕方は 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 の関数と違って返り値を持たず、処理が終われば次のコードセグメントへと処理を移る。
このコードセグメント間の継続制御を軽量継続(light-weight continuation) と呼ぶ。
C おいて関数呼び出しを繰り返し行う場合、呼び出された関数の引数の数だけスタックに値が積まれていく。
だが、返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く、最小限のスタックの使用ですむ。

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


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

\section{GCC-4.6 への実装}
\subsection{軽量継続の実装}
CbC はコードセグメント間の処理の移りを軽量継続で行う。
その実態は、アセンブラでの関数の呼び出しを call ではなく jmp で行うようにするというものである。


\subsubsection{Tail Call Elimination}
GCC には最適化の1つに Tail Call Elimination (末尾除去) がある。
Tail Call Elimination は関数の呼び出しを 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}

CbC における軽量継続の実装はこの Tail Call Elimination を用いて行われている。
コードセグメントは全てこの Tail Call Elimination にかからなければならない。

\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.

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

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

\begin{itemize}
  \item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.
  \item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.
  \item スタックサイズは決め打ちで行う.
\end{itemize}

だが、 CbC-GCC-4.5 において Tail Call Elimination にかからないコードセグメントがあることを確認できた。
この点は GCC-4.6 へのアップデートに合わせ改善する。


%\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 の関数からコードセグメントに継続する際、
元の C の関数に処理を戻すことがように環境付き継続を実装してある。
環境付き継続は \_\_return, \_\_environment という CbC で定義した変数を参照することで用いることができる。
この2つの変数は参照されると、参照した関数のアドレスを覚えておく。
具体的には変数を参照した関数にコード\ref{code:_ret_val}の生成を行なっている。
コードセグメントから戻るときには関数内で定義された \_cbc\_internal\_return 関数に飛び、
リターンを行うのである。
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
__label__ _cbc_exit0;
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{環境付き継続の問題}
しかし現在環境付き継続はスレッドセーフな実装でない。
その為,マルチスレッドで環境付き継続を扱うと、元の関数に戻る前に別スレッド
が記憶したアドレスの値を書き換えられる可能性があるからである。
そこで、環境付き継続をスレッドセーフで実装する必要がある。


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


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

\thispagestyle{fancy}
\begin{thebibliography}{9}

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

\bibitem{2}{河野真治}:
“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

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

\bibitem{4}{与儀健人,河野真治}:
“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010

\bibitem{5}{下地篤樹,河野真治}:
“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008

\bibitem{6}{楊挺,河野真治}:
“Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002

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


\end{thebibliography}
\end{document}