\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{}
%\date{H23 11/18 fri}
%\date{平成23 年11 月18 日}
\maketitle
\thispagestyle{fancy}

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

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

\section{Continuation basede C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

\subsection{コードセグメント}
コードセグメントの記述は C の関数の構文と同じで, 型に``\_\_code'' を使うことで宣言できる.
コードセグメントへの移動は``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}

\subsection{軽量継続(light-weight continuation)}
コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.

%軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.


\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 のアップデート時に伴う専用関数の修正が不要となり, 楽な管理が行えるようになった.


\section{評価}
今回実装を行った CbC-GCC-4.6 と CbC-GCC-4.5 でベンチマークを行った.
結果を図\ref{fig:conv1}に示す.
プログラムは Micro-C のベンチマークにも使用されるものである.
このプログラムは演算と継続を交互に行う処理をループの回数分繰り返すというものである.
引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる。
%自作のスタックを作り, そこに継続先のコードセグメント(以下 cs)と値を確保して
%渡していくプログラムである.
引数 2 と 3 のプログラムは Micro-C 用に手動で最適化を行ったプログラムである.
また評価は \verb+x86_64+ 上の Linux で行った.

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


\subsection{評価の考察}
手動で最適化を行なっている引数 2 と 3 の時は余り差は無い.
寧ろわずかだが GCC-4.6 版の方が遅くなっている.
しかし, 引数 1 の時は GCC-4.6 版 GCC-4.5 版より, 32 bit は 2.45 倍, 64 bit は 1.5 倍以上早いことが確認できる.
これは引数 2 と 3 の処理に比べて引数 1 の処理は最適化にかけにくいことが要因としてあげられる.
GCC-4.6 へとアップデートを行ったことで, より良い最適化にかかることができたと予想する.

%この結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた.
%アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて
%必要最小限の継続だけを行なうプログラムとなっていた.

\subsection{アセンブラコードの比較の結果}
では具体的にはどのようなより良い最適化になっているのかを調べてみる.
結果に差の出た引数 1 の時のアセンブラコードを比較した.
まず, プログラムの大まかな流れを図\ref{fig:conv1_arg0}に示す.
\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/conv1_arg0.pdf}}
  \end{center}
  \caption{conv1プログラムの挙動}
  \label{fig:conv1_arg0}
\end{figure}
\newpage
四角は cs を, 矢印は継続を表している.
また, cs の中の処理は演算の部分は省いて継続に関する部分だけにしてある.
プログラムの処理は cs f から継続が始まり cs g\_h1 まで継続を行いループするという流れになる.
注意点としては, cs f\_g1, cs g\_h1 への継続は cs f\_g0, cs f\_g で自作のスタック(実態は構造体)に
関数ポインタを入れて置き継続している部分である.

まず, CbC-GCC-4.5 のアセンブラをみてみると main 関数から``call f''により継続が行われていた.
cs f へと継続後は図\ref{fig:conv1_arg0}に示す通りの動作を行った.

しかし, CbC-GCC-4.6 の方では main 関数からは``call g\_h1''から継続が行われ, loop check 後も
g\_h1 から継続されていた.
この処理を図\ref{fig:conv1_arg0_2}に示す.
\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/conv1_arg0_2.pdf}}
  \end{center}
  \caption{conv1プログラムの挙動( CbC-GCC-4.6 )}
  \label{fig:conv1_arg0_2}
\end{figure}

cs f から cs h まで継続の処理はインライン展開によりまとめて計算されて定数として出されていた.
cs g\_h1 と cs f\_g1 の処理がインライン展開されないのは, 関数ポインタとして扱っていた為だと思われる.

%CbC-GCC-4.6 では cs g_h1 までの処理はインライン展開されてまとめて計算を行われていたのが確認できた.

\section{今後の課題}
今回, CbC コンパイラを GCC-4.6 へとアップデートを行った.
%アップデートに伴い実装の修正と, 本稿では説明していないが``\verb+__rectype+'' や``selftype''と言った
%構文の追加も行えた.
アップデートに伴いより管理のしやすい実装へと修正を行った.
また, GCC をアップデートしたことで、より協力な最適化がかかることも確認できた.
%アップデートに伴い実装の修正を行い, また 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}