\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{url}
\usepackage{picins}
\usepackage{fancyhdr}
\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 にかからなければならない。
だが、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 によって呼びされるようにする必要がある。


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.40}{\includegraphics{figure/typedefrec.eps}}
  \end{center}
  \caption{typedefrecの例}
  \label{fig:typedefrec}
\end{figure}

より柔軟なプログラミングが行えるように typdefrec を実装を行いたい。

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

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

%\subsection{\_\_return 変数}
\subsection{環境付き継続}
CbC では通常の C の関数からコードセグメントに継続する際、
元の C の関数に処理を戻すことがように環境付き継続を実装してある。
環境付き継続は \_\_return 変数を参照することで用いることができる。
\_\_return 変数は参照されると、参照した関数のアドレスを覚えておく。
コードセグメントの継続の際に引数に \_\_return 変数を渡すことで、
関数の呼び出し元のアドレスも渡すことができる。
後は引数として渡されたきたアドレスへ飛ぶことでいつでも C の関数に戻ることができる。

\subsubsection{\_\_return 変数の問題}
しかし現在この \_\_return の値は static で実装されている。
これではスレッドセーフであるとは言えない。
マルチスレッドで\_\_returnを扱うと、元の関数に戻る前に \_\_return の値が書き換えられる可能性があるからである。
そこで、\_\_return をスレッドセーフにする必要がある。

\subsection{x86\_64 での fastcall}
GCC では関数の呼び出しの際に引数はスタックに積まれて渡されるが、
レジスタを使って渡すようにする fastcall という拡張機能がある。
CbC-GCC ではコードセグメントとして宣言された場合 fastcall が自動で付くようにしていた。
しかし、x86\_64 においてこの fastcall は標準の機能となっており、コンパイルの際に warning が吐かれた。
そこで、x86\_64 の場合は fastcall を付与させないようにした。

\section{CbC の今後}
現在 CbC は C をベースとして設計されている。
しかし、C ではプロトタイプ宣言や継続の際に型推論が扱えないなど不便な点があることがわかっている。
そこで、Go や D 言語と言った言語へ実装を行いたいという要求がでてきた。

また、LLVM ベースの CbC コンパイラについても検討している。

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

Go 言語や D 言語への CbC の移植,
LLVM ベースの CbC コンパイラについては実装の方法から考えていくことになる。



%今後は本稿で述べた 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{6}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}
\end{document}