\documentclass[twocolumn,twoside,9.5pt]{jarticle}
%\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{url}

\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{figure/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}
%\date{平成23 年11 月18 日}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下 CbC) を提案している.
%コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
% Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.
コードセグメントは C の関数よりも細かな単位で, 状態を表すことができる.
その為 CbC では状態遷移記述を行うことができ, 状態探索といったモデル検査が行えると考えられている.

%GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
%当研究室には 2008 年に開発されて以来アップデートがGCC-4.5 をベースとした CbC コンパイラがある.
CbC のコンパイラとしては Micro-C 版と GCC ベースのコンパイラ(以下 CbC-GCC) が開発されている.
しかし, CbC-GCC はいくつかバグがあり機能の修正の余地があった.
また, GCC の最新の機能を使用する為にも CbC-GCC は GCC のアップデートに合わせていく必要がある.
本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートとすると共に機能の修正
を行う.
%本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.

\section{Continuation basede C (CbC)}
Continuation based C (以下 CbC) は C を基本としたプログラミング言語である.
構文は C と同じであるが, 継続(goto) やコードセグメントの導入によりループ制御や関数コールが取り除かれる.
CbC のプログラムはコードセグメントの末尾から次のコードセグメントへの継続を記述することで作られる.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

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


\section{GCC-4.6 への実装}
CbC 環境を保持しない継続は軽量継続と呼ばれる.
GCC における軽量継続は Tail Call Ellimination (末尾除去)を強制することで実装する.
これにより, コードセグメント間の移動を, call ではなく jmp 命令で行う.
この為コードセグメントからのは戻値は無くなる.
図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す.
\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/continuation.pdf}}
  \end{center}
  \caption{Tail Call Elimination の例}
  \label{fig:continue}
\end{figure}

\subsection{Tail Call Elimination の矯正付与}
関数が Tail Call Elimination にかかる為には, ``呼び出し先関数と呼び出し元関数の方が一致している''
等といった幾つかの条件をクリアしなければならない.
これまでの実装ではコードセグメントに条件をクリアさせる為, 専用の関数を用意していた.
しかし今回の実装ではその関数を廃止し, 末尾除去にかかるフラグを落とさせない
コードを追加することで Tail Call Elimination の条件をクリアさせるようになった.
これにより GCC のアップデート時に伴う専用関数の修正が不要となり, 楽な管理が行えるようになった.

\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
これを環境付き継続という.
環境付き継続は, \verb+_CbC_environment+ と \verb+_CbC_return+ キーワードを
引数に渡しコードセグメントとして扱うことで使用できる.
%\verb+environment+ は 環境を表す情報を持つ.
%\verb+__return+ は環境付き継続の行き先であり, 関数の戻り値と\verb+__environment+ の二つの引数を
%持つコードセグメントになる.
%GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
%戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:retval}) .
%実際には \verb+__return+ キーワードにより GCC 内部でlisting\ref{code:retval}のコードが生成されている.
実際には \verb+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
%    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:retval]
    \begin{verbatim}
({
__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{verbatim}
  \end{minipage}
  \hfill
\end{figure}

\subsubsection{環境付き継続の問題と改良}
環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである.
元々の実装では static で値の確保を行なっていた.
しかしこれではスレッドセーフではない.
そこで retval 変数の値を static thread local で確保することでこの問題の解決を行った.

\subsection{構文の追加}

\subsubsection{``\_\_rectype'', ``selftype'' 構文}
%\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる.
通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない.
そこで, \verb+__rectype+を使うことでlisting\ref{code:rectype}の用な宣言が行うことができる.
また, 構造体の宣言時に宣言中の構造体を指す``selftype'' 構文の追加も行った.
以下の様な宣言が行えるようになった.
この時\verb+__rectype+は funcPtr を指し, selftype は struct node を指す.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{verbatim}
typedef __code (*funcPtr)(int,__rectype*);
struct node {
 int num;
 selftype child;
}
    \end{verbatim}
  \end{minipage}
\end{figure}
%    \begin{lstlisting}[caption=\_\_rectype\, selftype 構文の使用例,label=code:rectype]
%    \end{lstlisting}
\section{評価}
今回実装を行った GCC-4.6 ベース と安定版である GCC-4.5 ベース,
 それと Micro-C の CbC コンパイラでベンチマークを行った.
プログラムは Micro-C のベンチマークにも使用されるものである.
このプログラムは演算と継続を交互に行う.
引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる.
引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである.
また評価は \verb+x86_64+ 上の CentOS 5.7 で行った.
%また評価は \verb+x86_64+ 上の OS X(10.7) で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った.
%結果を図\ref{fig:conv1}の様になった(斜線は segmentation fault を示す).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/conv1_linux.pdf}}
  \end{center}
  \caption{各種コンパイラにより生成されたコードの速度比較}
  \label{fig:conv1}
\end{figure}

\subsection{評価の考察}
まず, Micro-C 版より GCC 版コンパイラの方が結果が良いことが確認できる.
次に GCC-4.5 と GCC-4.6 を比較してみる.
手動で最適化を行なっている引数 2 と 3 の時は余り差は無い.
だが, 引数 1 の時は GCC-4.6 版が GCC-4.5 に比べて 1.67 倍程早い.
アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて
必要最小限の継続だけを行なっていた.
アセンブラとこの結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた.

\section{今後の課題}
今回, CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い実装の修正と Intel64 bit への対応を行った.
また, CbC の記述に便利な新たな構文の追加も行うことができた.

GCC 版 CbC コンパイラは細かい実装の除けば, 以後 GCC のアップデートに合わせていくだけとなる.
CbC コンパイラの今後としては LLVM への実装, もしくは 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}