\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{picins}
\usepackage{float}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{figures/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.2による実装}
\author{045760E 与儀健人 \hspace{2cm} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy}

\section{はじめに}
当研究室ではContinuation based C(以下CbC)という言語を提案している。
これまでCbCのコンパイルにはMicro-Cをベースとした当研究室独自のコンパイラを
使用していた。

また、河野氏による以前の論文\cite{kono1}にて、Tail call optimizationを用いることで
GCC上でも実装可能である事が示されている。

この様な背景から、CbCをGCCでコンパイルしたいという要望がでてきた。
本研究ではこの言語をGCCへ移植することを目的とする。
それによりGCCの最適化機構によるCbCのコード性能の向上、
また複数のアーキテクチャへの対応を目指す。


\section{Continuation based Cについて}
Continuation based C (以下CbC) は当研究室が提案するアセンブラよりも上
位でC よりも下位な記述言語である\cite{kono2}。
Cの仕様からループ制御や関数コールを取り除き、
継続(goto) や code segmentを導入している。
これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
ソースコードレベルで行うことができる。
図\ref{fig:continuation}にこの様子を表す。
\begin{figure}[H]
  \begin{center}
    \includegraphics[width=.45\textwidth]{figures/continuation.eps}
  \end{center}
  \caption{code segment間の``継続''}
  \label{fig:continuation}
\end{figure}%


\section{The GNU Compiler Collection}
\subsection{GCCの基本構成}
GCCは主に次のような手順でソースコードをコンパイルする。
\begin{description}
  \item[parsing] 一般的なコンパイラと同じく、GCCもまずはパーサによって
	ソースコードを解析し、解析した結果はGeneric Treeと呼ばれる
	tree構造の構造体に格納される
  \item[gimplification] この段階ではGeneric Treeをもとにこれを
	GIMPLEに変換していく。
  \item[GIMPLE optimization] 前段階で変換したGIMPLEに対して最適化を行う。
  \item[RTL generation] ここで、GIMPLEをもとにRTLを生成する。
	この段階でほぼ言語依存性がなくなる。
  \item[RTL optimization] 前段階で生成されたRTLに対して最適化を行う。
  \item[Output assembly]
    最後にRTLをもとにターゲットマシンのアセンブリに変換する。
\end{description}
これらの様子を図\ref{fig:GCC-pass}に示す。
\begin{figure}[H]
  \begin{center}
    \includegraphics[width=.45\textwidth]{figures/GCC-pass.eps}
  \end{center}
  \caption{GCCのpass}
  \label{fig:GCC-pass}
\end{figure}

\subsection{Tail call elimination}
GCCの最適化には``Tail call elimination''と呼ばれる、関数呼び出しを
最適化するものがある。
``Tail call elimination''は通常call命令を使用すべき
関数呼び出しで、jump命令に変更するというものである。
この最適化の概要を図\ref{fig:Tail call}にしめす。
\begin{figure}[H]
  \begin{center}
    \includegraphics[width=.4\textwidth]{figures/GCC-TailCall.eps}
  \end{center}
  \caption{Tail call eliminationの例}
  \label{fig:Tail call}
\end{figure}

\section{GCCへの実装}
河野氏の論文``継続を基本とした言語CbCのgcc上の実装''\cite{kono1}
にて、Tail call optimizationをもちいてCbCのgotoが実装できる事が
示されている。

実装の流れとしては次のようになる。
\begin{enumerate}
  \item \_\_code トークンの追加(Tokenizerで読み込めるようにする)
  \item code segmentのパース及びtree生成
  \item CbCのgoto ステートメントのパース及びtree生成
  \item gotoステートメントtreeのRTLへの変換
  \item その他エラーメッセージ処理やコード改良
\end{enumerate}

最も重要なところがRTL生成である。
ここではtail call可能なフラグのついた関数コールをRTLに変換することになる。
これは通常は\verb|expand_call|という巨大な関数にて生成されている。
\verb|expand_call|ではtail callが可能かを詳しくチェックして、可能であれば
tialcall用のCALL\_INSN RTL. 不可と判定されれば通常のCALL\_INSN RTLを生成している。

しかし、goto先がcode segmentであれば
強制的にtailcall用のCALL\_INSNを生成する必要がある。
そこで実装の際には\verb|expand_cbc_goto|という新たな関数を作り、
CbCのgoto処理はそこで全て行うようにした。



\section{評価}
本研究によって、GCCによるCbCのコンパイルが可能になった。
その評価としては両コンパイラによってコンパイルされたコードの
実行速度を測れば良いだろう。
評価にはこれまでもMicro-Cの評価に用いてきたconv1という簡単な
プログラムを用いた。

測定結果は表\ref{tab:mc,gcc,compare}に示される。
\begin{table}[H]
  \centering
  \begin{tabular}{|l|r|r|r|r|} \hline
    & conv1 0 & conv1 1 & conv1 2 &  conv1 3 \\ \hline
    Micro-C         & 5.25 & 8.97 & 2.19 & 2.73 \\ \hline \hline
    GCC             & 3.69 & 4.87 & 3.08 & 3.65 \\ \hline
    GCC (+omit)     & 2.74 & 4.20 & 2.25 & 2.76 \\ \hline
    GCC (+fastcall) & 2.70 & 3.44 & 1.76 & 2.34 \\ \hline \hline
    TCC             & 4.15 &122.28& 84.91&102.59\\ \hline
  \end{tabular}
  \caption{Micro-C, GCCの実行速度比較 (単位 秒)}
  \label{tab:mc,gcc,compare}
\end{table}
この評価から本研究における目的の一つ、``CbCコードの高速化''を
達成できたことが分かった。

\section{今後の課題}
本研究において、CbCを使う分にはほぼ問題はなくなったが、
まだ対応していない構文や、バグが以下の通り見つかっている。
\begin{description}
  \item[environment]
    CbCにはもう一つ、environment付きの継続という構文が存在する。
    これは関数からcode segmentにgotoした場合に関数の呼び出し元に戻る
    ことを可能にするものだが、今回この実装は間に合わなかった。
  \item[code segmentポインタの計算] 今の実装では\verb|goto cs->next(a, b);|
    のように呼び出し先code segmentを計算することができない。
  \item[-O2オプションの強制] CbCは-O2オプションをつけないとコンパイルできない。
    なのでファイル名が.cbcの場合はこれを強制させる必要がある。
  \item[fastcall] code segmentではfastcallを強制させることで高速化が期待できる。
\end{description}
この中から特に重要なのがenvironmentとcode segmentポインタの計算
への対応だと考えている。
この二つができればとりあえずCbCの現在の仕様を満たす。

これらに加えて、GCCにはすでにC++やObjective-Cのコンパイルが可能である。
これを活かし、CbC++, もしくはObjective-CbCといった既存の言語と
CbCを組み合わせた言語に付いても考えてみる価値があるだろう。


\begin{thebibliography}{9}
  \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''.
	日本ソフトウェア科学会第19回大会論文集, Sep, 2002.
  \bibitem{kono2} 河野真治. ``継続を持つCの下位言語によるシステム記述''.
	日本ソフトウェア科学会第17回大会論文集, Sep, 2000.
  \bibitem{gcc1} GNU Project - Free Software Foundation, GCC internal manual.
	``http://gcc.gnu.org/onlinedocs/gccint/''.
\end{thebibliography}

\end{document}