Mercurial > hg > Papers > 2011 > nobu-prosym

changeset 5:c0b91a1c738e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 18 Nov 2011 17:45:21 +0900
parents 9adf0d4a6033
children ea43a580129b
files Paper/nobu-prosym.aux Paper/nobu-prosym.dvi Paper/nobu-prosym.log Paper/nobu-prosym.pdf Paper/nobu-prosym.tex
diffstat 5 files changed, 80 insertions(+), 35 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/nobu-prosym.aux	Fri Nov 18 10:08:31 2011 +0900
+++ b/Paper/nobu-prosym.aux	Fri Nov 18 17:45:21 2011 +0900
@@ -1,15 +1,16 @@
 \relax 
 \newlabel{fig:cs}{{1}{1}}
-\@writefile{lol}{\contentsline {lstlisting}{source/factorial.cbc}{1}}
-\newlabel{fig:ir}{{2}{2}}
-\newlabel{fig:continue}{{3}{2}}
+\@writefile{lol}{\contentsline {lstlisting}{source/factorial.cbc}{2}}
+\newlabel{fig:ir}{{3}{2}}
 \bibcite{1}{1}
+\newlabel{fig:continue}{{4}{3}}
+\newlabel{fig:cs_stack}{{5}{3}}
+\newlabel{fig:fastcall}{{6}{3}}
 \bibcite{2}{2}
 \bibcite{3}{3}
 \bibcite{4}{4}
 \bibcite{5}{5}
 \bibcite{6}{6}
 \bibcite{7}{7}
-\newlabel{fig:fastcall}{{4}{3}}
-\newlabel{tab:speed-mc-vs-gcc-nonopt}{{1}{3}}
-\newlabel{tab:speed-mc-vs-gcc-opt}{{2}{3}}
+\newlabel{tab:speed-mc-vs-gcc-nonopt}{{1}{4}}
+\newlabel{tab:speed-mc-vs-gcc-opt}{{2}{4}}
Binary file Paper/nobu-prosym.dvi has changed
--- a/Paper/nobu-prosym.log	Fri Nov 18 10:08:31 2011 +0900
+++ b/Paper/nobu-prosym.log	Fri Nov 18 17:45:21 2011 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10)  18 NOV 2011 10:06
+This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10)  18 NOV 2011 17:44
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -221,10 +221,7 @@
 (/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstmisc.sty
 File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz)
 )
-(./source/factorial.cbc [1
-
-
-]
+(./source/factorial.cbc
 LaTeX Font Info:    Try loading font information for OMS+cmr on input line 2.
 
 (/usr/local/texlive/2011/texmf-dist/tex/latex/base/omscmr.fd
@@ -239,49 +236,96 @@
 )
 LaTeX Font Info:    Font shape `OML/cmr/m/n' in size <9> not available
 (Font)              Font shape `OML/cmm/m/it' tried instead on input line 8.
-)
+) [1
+
+
+]
 File: figure/ir.eps Graphic file (type eps)
- <figure/ir.eps>
-Overfull \hbox (19.2858pt too wide) in paragraph at lines 173--174
+
+<figure/ir.eps>
+Overfull \hbox (19.2858pt too wide) in paragraph at lines 172--173
+ [] 
+ []
+
+File: figure/continuation.eps Graphic file (type eps)
+<figure/continuation.eps>
+Overfull \hbox (6.55446pt too wide) in paragraph at lines 233--233
+[]
+ []
+
+
+Underfull \hbox (badness 10000) in paragraph at lines 233--233
+
+ []
+
+
+Overfull \hbox (109.73647pt too wide) in paragraph at lines 235--235
+[]
+ []
+
+
+Underfull \hbox (badness 10000) in paragraph at lines 235--235
+
+ []
+
+[2]
+Overfull \hbox (81.8236pt too wide) in paragraph at lines 242--242
+[]
+ []
+
+
+Underfull \hbox (badness 10000) in paragraph at lines 242--242
+
+ []
+
+
+Overfull \hbox (161.4138pt too wide) in paragraph at lines 243--243
+[]
+ []
+
+
+Underfull \hbox (badness 10000) in paragraph at lines 243--243
+
+ []
+
+File: figure/cs_stack.eps Graphic file (type eps)
+<figure/cs_stack.eps>
+File: figure/fastcall.eps Graphic file (type eps)
+ <figure/fastcall.eps>
+Overfull \hbox (12.43753pt too wide) in paragraph at lines 287--288
  [] 
  []
 
 
-LaTeX Warning: Reference `continue' on page 2 undefined on input line 215.
-
-File: figure/continuation.eps Graphic file (type eps)
-<figure/continuation.eps> [2]
-File: figure/fastcall.eps Graphic file (type eps)
- <figure/fastcall.eps>
-Overfull \hbox (12.43753pt too wide) in paragraph at lines 264--265
- [] 
- []
-
-
-Overfull \hbox (10.40831pt too wide) in paragraph at lines 297--303
+Overfull \hbox (10.40831pt too wide) in paragraph at lines 320--326
  [][] 
  []
 
 
-Overfull \hbox (10.40831pt too wide) in paragraph at lines 311--317
+Overfull \hbox (10.40831pt too wide) in paragraph at lines 334--340
  [][] 
  []
 
-[3] (./nobu-prosym.aux)
+[3] [4
+
+] (./nobu-prosym.aux)
 
 LaTeX Font Warning: Some font shapes were not available, defaults substituted.
 
 
 LaTeX Warning: There were undefined references.
 
+
+LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
+
  ) 
 Here is how much of TeX's memory you used:
- 2579 strings out of 494163
- 34809 string characters out of 3160585
- 119661 words of memory out of 3000000
- 5965 multiletter control sequences out of 15000+200000
+ 2581 strings out of 494163
+ 34844 string characters out of 3160585
+ 120885 words of memory out of 3000000
+ 5966 multiletter control sequences out of 15000+200000
  17620 words of font info for 68 fonts, out of 3000000 for 9000
  745 hyphenation exceptions out of 8191
- 30i,10n,52p,207b,1530s stack positions out of 5000i,500n,10000p,200000b,50000s
+ 30i,10n,52p,207b,1326s stack positions out of 5000i,500n,10000p,200000b,50000s
 
-Output written on nobu-prosym.dvi (3 pages, 19520 bytes).
+Output written on nobu-prosym.dvi (4 pages, 21344 bytes).
Binary file Paper/nobu-prosym.pdf has changed
--- a/Paper/nobu-prosym.tex	Fri Nov 18 10:08:31 2011 +0900
+++ b/Paper/nobu-prosym.tex	Fri Nov 18 17:45:21 2011 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}


% 巻数，号数などの設定
%\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 と同じであるが,継続によりループ制御や関数コールが取り除かれる.

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

今回,CbC コンパイラを 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.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}


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

継続の実態は jmp による関数の移動となる.


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

\lstinputlisting[language=c]{source/factorial.cbc}



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


\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.


\subsection{3つの内部表現}
GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は




\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsubsection{GIMPLE}
Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsubsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる.


\section{GCC-4.6 への実装}
前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
ここからは GCC-4.6 への実装について述べていく.


\subsection{“\_\_code” のパース}



\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}
funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.


\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
Tail Call Elimination が行える条件は以下のようになる.

\begin{description}
  \item[caller側とcallee側の型の一致]
  \item[] 
  \item[] 
\end{description}


%expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
%Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.


expand\_call 関数の中で try\_tail\_call フラグ



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


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

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}


if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行れ,
fastcall 属性を付けると warning を出すからである.


\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
クイックソートは再帰的にプログラムされる為 CbC に向いている
プログラムだと言える.
比較を行うのは以下のアーキテクチャと OS になる.

\begin{description}
  \item[x86/Linux]
  \item[x86/OS]
  \item[x86/OS X(64bit 動作)] 
\end{description}
また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つを用意する.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.

\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.829 & 2.890 \\ \hline
 x86\_64(m32)/OS X& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.252 & 1.768 & 2.890 \\ \hline
 x86\_64(m32)/OS X& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}


\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}
\ No newline at end of file
+\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}


% 巻数，号数などの設定
%\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 と同じであるが,継続によりループ制御や関数コールが取り除かれる.

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

今回,CbC コンパイラを 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.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}


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

継続の実態は jmp による関数の移動となる.


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

\begin{figure}
\lstinputlisting[language=c]{source/factorial.cbc}
\caption{階上を計算する CbC プログラムの例}
\end{figure}


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


\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.


\subsection{3つの内部表現}
GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}はアセンブラ出力までの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsubsection{GIMPLE}
Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsubsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる.


\section{GCC-4.6 への実装}
前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
ここからは GCC-4.6 への実装について述べていく.


\subsection{“\_\_code” のパース}



\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
call ではなく jmp を用いることができるという最適化である.
図\ref{fig: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}
funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.


\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.

\begin{description}
  \item[caller 側と callee 側の返す値の型が一致している.]
  \item[関数呼び出しがリターンの直前に行われている.] 
  \item[呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.]
  \item[]
\end{description}

CbC の実装では上記の条件を,以下の様にして解決させている.

\begin{description}
  \item[呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.]
  \item[コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.]
  \item[スタックサイズは決め打ちで行う.]
  \item[]
\end{description}

スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
これも CbC の1つの特徴である.
図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cs_stack.eps}}
  \end{center}
  \caption{継続による引数のスタック格納の様子}
  \label{fig:cs_stack}
\end{figure}



%expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
%Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.


expand\_call 関数の中で try\_tail\_call フラグ



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


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

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}


if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行れ,
fastcall 属性を付けると warning を出すからである.


\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
クイックソートは再帰的にプログラムされる為 CbC に向いている
プログラムだと言える.
比較を行うのは以下のアーキテクチャと OS になる.

\begin{description}
  \item[x86/Linux]
  \item[x86/OS X]
\end{description}
また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.

\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.829 & 2.890 \\ \hline
 x86\_64(m32)/OS X& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.252 & 2.906 & 2.890 \\ \hline
 x86\_64(m32)/OS X& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}



\begin{thebibliography}{7}

\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}
\ No newline at end of file