\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+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \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+を使うことで以下の様な宣言が行うことができる.
また, 構造体の宣言時に宣言中の構造体を指す``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}
\section{評価}
今回実装を行った GCC-4.6 と GCC-4.5 ベース,
 それと Micro-C の CbC コンパイラでベンチマークを行った.
プログラムは Micro-C のベンチマークにも使用されるものである.
このプログラムは演算と継続を交互に行う.
引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる.
引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである.
また評価は \verb+x86_64+ 上の Linux で行った.
%また評価は \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_for_resume.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 版が 32 bit, 64 bit 共に GCC-4.5 に比べて 1.5 倍以上早い.
アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて
必要最小限の継続だけを行なうプログラムとなっていた.
この結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた.

\section{今後の課題}
今回, CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い実装の修正を行い, また 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}