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

\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 での並列実行を高い性能と高い信頼性で実現することができると考えている.

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

\section{Continuation basede C (CbC)}
Continuation based C (以下 CbC) は状態遷移記述をベースとしたプログラミング言語である.
構文は C と同じであるが, 継続(goto) やコードセグメントの導入によりループ制御や関数コールが取り除かれる.
CbC のプログラムはコードセグメントから次のコードセグメントへ jmp 命令(goto)により処理を移っていく.
図\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 への実装}
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{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 にかからないコードセグメントがある.
この点を改善する必要がある.


\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:retval}) .
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:retval]
({
__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{環境付き継続の問題と改良}
環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである.
元々の実装ではListing\ref{code:retval}の様に static で値の確保を行なっていた.
しかしこれではスレッドセーフではない.
そこで retval 変数の値を static thread local で確保することでこの問題の解決を行った.

\section{構文の追加}

\subsection{``\_\_rectype''構文}
%\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる.
通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない.
そこで, \verb+__rectype+を使うことでlisting\ref{code:rectype}の用な宣言が行うことができる.
この時\verb+__rectype+は funcPtr を指す.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=\_\_rectype 構文使用例,label=code:rectype]
typedef (*funcPtr)(int,__rectype*);
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

\subsection{selftype 構文}
selftype 構文は構造体の宣言時に使われる.
listing\ref{code:selftype}な宣言が行える.
この場合, selftype は struct node を指す.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=selftype 構文使用例,label=code:selftype]
struct node {
 int num;
 selftype child;
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

\section{評価}
今回実装を行った GCC-4.6 ベース と安定版である GCC-4.4 ベース,
 それと Micro-C の CbC コンパイラでベンチマークを行った.
プログラムは Micro-C のベンチマークを使用した. 
引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムである.
引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムになる.
Linux 上で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った.
結果を図\ref{fig:linux_conv}に示す.
\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/conv1_linux.pdf}}
  \end{center}
  \caption{それぞれのコンパイラにより生成されたコードの速度比較(Linux)}
  \label{fig:linux_conv}
\end{figure}

\subsection{評価の考察}
まず, Micro-C 版より GCC 版コンパイラの方が結果が良いことが確認できる.
GCC-4.5 と GCC-4.6 版を比較してみると手動で最適化を行なっている引数 2 と 3 の結果に余り差はみられない.
しかし CbC へと変換しただけの引数 1 の場合には GCC-4.6 版が 32bit 版は 2.43倍, 64bit 版は 1.68 倍と優っている.
これは GCC-4.5 に比べ GCC-4.6 の最適化が修正されている為である. 

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