\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}

% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の GCC 4.6 上の実装について]%
	{Continuation based C の GCC 4.6 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on GCC 4.6}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{大城 信康\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{大城 信康\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: dimolto@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
GCC-4.6 をベースとした CbC コンパイラの実装を行った.
CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
今回は GCC-4.6 への実装を行った.
本論文では GCC-4.6 への CbC の具体的な実装について述べる。


%当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
%また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
%お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.


\end{abstract}


% 英文概要
\begin{eabstract}
We implemented Continuation based C Compiler on GCC-4.6.
CbC Compiler on GCC-4.2 was developed on 2008.
Since then we kept to update it.
In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

%Continuation based C is programming language. It is developing our laboratory.

\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

% 本文はここから始まる
\section{歴史的経緯}
当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
CbC の構文は C と同じであるが,継続によりループ制御や関数コールを取り除かれる.

2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発された.
以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
お陰で,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.

しかし,未だに GCC ベースのコンパイラには幾つかのバグがある.
今回,GCC-4.6 への実装も兼ねながら問題の部分の改善を行った.
本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を具体的に述べる.


%}{

\section{Continuation based C (CbC)}
Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
また,コードセグメント単位で処理を記述するという特徴がある.
図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.

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


\subsection{継続(goto)}
コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
コードセグメントは自身の処理が終われば goto により次のコードセグメントでの処理に移る.
goto によるコードセグメント間の移動を継続と言う.


\subsection{コードセグメント(code segment)}
CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
関数と同じように引数を持たせて継続させることもできる.
しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.50}{\includegraphics{figure/factorial.eps}}
  \end{center}
  \caption{CbC のプログラム例}
  \label{fig:factorial}
\end{figure}


%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.



\section{Gnu Compiler Collection}
GCC-4.6 への実装の前に,GCC によるコンパイルの一連の流れについて触れておく.

\subsection{3つの中間言語}
GCC は内部で Generic Tree, GIMPLE, RTL の3つの中間言語を扱われる.

\subsubsection{Generic Tree}
まず,GCC で読み込まれたソースコードは Generic Tree 呼ばれる構文木のデータ構造で表される.
図...に Generic Tree で表現された例を示す.

\subsubsection{GIMPLE}
Generic Tree により表現されたデータは次に GIMPLE という構文木へと変換される.
GIMPLE は Generic Tree より制約がかかった状態で作成される.
制約は「1つの枝に4つ以上の子を持たせない」といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになる.


\subsubsection{RTL}



Gneric Tree から GIMPLE, そして RTL へとデータは変換され最後にアセンブリ言語で出力される.



\section{GCC-4.6 への実装}


\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
call ではなく jmp を用いて大元の関数へ戻るようにする最適化のことである.
図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.50}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}



\subsubsection{expand\_call}



\subsection{引数渡し}
通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される.
GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る.

\subsubsection{fastcall}
コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{fastcall属性付与}
  \label{fig:fastcall}
\end{figure}

if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である.


\begin{thebibliography}{10}

\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}