Mercurial > hg > Papers > 2008 > kent-sigos

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile	Mon Mar 24 02:43:53 2008 +0900
@@ -0,0 +1,46 @@
+DVIPDF = dvipdfmx
+LATEX  = platex
+PS2PDF = ps2pdf14
+DVIPS  = dvips
+BKMK2UNI = ~/src/bkmk2uni
+
+TARGET1 = main
+#TARGET2 = resume
+#TARGET3 = resume2
+#SLIDE1 = slide
+
+PDFs = $(TARGET1).pdf $(TARGET2).pdf $(TARGET3).pdf $(SLIDE1).pdf
+DVIs = $(TARGET1).dvi $(TARGET2).dvi $(TARGET3).dvi $(SLIDE1).dvi
+TEXs = $(TARGET1).tex $(TARGET2).tex $(TARGET3).tex $(SLIDE1).tex
+
+.SUFFIXES: .tex .dvi .pdf
+
+all: $(PDFs)
+
+.dvi.pdf:
+	$(DVIPDF) $^
+.tex.dvi:
+	$(LATEX) $^
+
+$(SLIDE1).pdf: $(SLIDE1).ps
+	$(PS2PDF) $^
+
+$(SLIDE1).ps: $(SLIDE1).dvi
+	$(DVIPS) $^
+	if [ -x $(BKMK2UNI) ]; then\
+	  mv $@ $@.tmp;\
+	  $(BKMK2UNI) -e < $@.tmp > $@;\
+	fi
+
+clean:
+	rm -f *.{aux,log,nav,out,snm}
+
+distclean: clean
+	rm -f $(DVIs) $(PDFs) *.{dvi}
+
+
+twice: distclean $(DVIs) .rmdvi $(PDFs)
+.rmdvi:
+	rm -f $(DVIs)
+
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main.sty	Mon Mar 24 02:43:53 2008 +0900
@@ -0,0 +1,76 @@
+
+%長さ設定
+\setlength{\hoffset}{-1in}
+\setlength{\voffset}{-1in}
+\setlength{\topmargin}{10mm}
+%\setlength{\oddsidemargin}{30mm}
+%\setlength{\evensidemargin}{30mm}
+\setlength{\oddsidemargin}{30mm}
+\setlength{\evensidemargin}{30mm}
+\setlength{\headheight}{10mm}
+\setlength{\headsep}{15mm}
+\setlength{\topskip}{0mm}
+\setlength{\textwidth}{160mm}
+\setlength{\textheight}{232mm} % 297mm - margin - 15mm
+\setlength{\marginparwidth}{3mm}
+\setlength{\marginparsep}{15mm}
+\setlength{\footnotesep}{2mm}
+\setlength{\footskip}{15mm}
+
+%タイトル
+\def\jtitle{}
+\def\jtitle#1{\gdef\@jtitle{#1}}
+%所属
+\def\@jaffiliation{}
+\def\jaffiliation#1{\gdef\@jaffiliation{#1}}
+%著者名
+\def\@jauthor{}
+\def\jauthor#1{\gdef\@jauthor{#1}}
+%抄録
+\def\@jabstract{}
+\def\jabstract#1{\gdef\@jabstract{#1}}
+
+%英タイトル
+\def\@etitle{}
+\def\etitle#1{\gdef\@etitle{#1}}
+%英語所属
+\def\@eaffiliation{}
+\def\eaffiliation#1{\gdef\@eaffiliation{#1}}
+%英著者名
+\def\@eauthor{}
+\def\eauthor#1{\gdef\@eauthor{#1}}
+%抄録
+\def\@eabstract{}
+\def\eabstract#1{\gdef\@eabstract{#1}}
+
+%年度
+\def\@year{}
+\def\year#1{\gdef\@year{#1}}
+%論文
+\def\@thesis{}
+\def\thesis#1{\gdef\@thesis{#1}}
+%ロゴ
+\def\@logo{}
+\def\logo#1{\gdef\@logo{#1}}
+
+
+%%%%表紙
+\renewcommand{\maketitle}{%
+%\newpage\null
+%\thispagestyle{empty}
+\vskip 1cm%
+\begin{center}%
+\let\footnote\thanks
+  {\huge\bfseries\mc\@jtitle \par}%
+  {\Large \@jauthor \par}%
+  {\Large \@jaffiliation \par}%
+  {\@jabstract \par}%
+    \vskip 3.0em%
+  {\huge\textbf{\@etitle}\par}%
+  {\Large \@eauthor \par}%
+  {\Large \@eaffiliation \par}%
+  {\@eabstract \par}%
+    \vskip 5.0em%
+\end{center}}
+
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/main.tex	Mon Mar 24 02:43:53 2008 +0900
@@ -0,0 +1,1750 @@
+%        File: main.tex
+%     Created: 日  3 23 18:00 PM 2008 J
+% Last Change: 日  3 24 03:20 PM 2008 J
+%
+\documentclass[a4j,twocolumn]{jarticle}
+\usepackage{main}
+\usepackage{graphicx}
+\usepackage{verbatim}
+\usepackage{nonDefaultPackage/listings}
+
+
+\jtitle{Continuation based CコンパイラのGCC-4.2による実装}
+\etitle{The implementation of Continuation based C Compiler on GCC}
+\jaffiliation{琉球大学理工学研究科情報工学専攻}
+\eaffiliation{Information Engineering, University Of the Ryukyus}
+\jauthor{与儀 健人 \hspace{2cm} 河野 真治}
+\eauthor{KENT yogi \hspace{2cm} Shinji KONO}
+\year{平成19年度}
+\thesis{OS研究会}
+%\logo{%\includegraphics[width=15em]{figures/u-ryukyu-Mark.eps}}
+
+\jabstract{
+当研究室ではContinuation based Cという言語を提案しており、
+そのコンパイルにはこれまでMicro-Cをベースにした独自のコンパイラを使用していた。
+また、GCCのTail call optimizationを用いた実装が可能である事を以前の論文で示した。
+ここではGCC上に実際にCbC言語の実装し、その評価を行った。
+この実装はアーキテクチャに依存しないので、
+GCCが対応する全てのアーキテクチャ上でCbCが動く事になるはずであるが、
+若干の問題があり、その点に付いても考察を行う。
+}
+\eabstract{
+We are approach Continuation based C Language,
+and have used Micro-C based Compiler that is developed by us to compile it.
+This research, We are implement a compiler for CbC into GCC and
+appraising it.
+This implementation is supposed
+to run on all archtectures that is supported by GCC,
+but few problems are founded.
+}
+
+
+\renewcommand{\lstlistingname}{リスト}
+\lstset{
+  language=C,%
+  stringstyle=\ttfamily,%
+  basicstyle=\small\ttfamily,%
+  commentstyle=\itshape,%
+  classoffset=1,%
+  keywordstyle=\bfseries,%
+  framesep=5pt,%
+  showstringspaces=false,%
+  %frame=tRBl,
+  %numbers=left,stepnumber=1,numberstyle=\footnotesize%
+}%
+\def\lstlistingname{リスト}
+\def\lstlistlistingname{プログラムコード目次}
+
+
+
+\begin{document}
+\twocolumn[\maketitle]{}
+
+\section{CbCについて}
+Continuation based C (以下CbC) は当研究室が提案するアセンブラよりも上
+位でC よりも下位な記述言語である\cite{kono2}。
+Cの仕様からループ制御や関数コールを取り除き、
+継続(goto) や code segmentを導入している。
+これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
+ソースコードレベルで行うことができる。
+
+図\ref{fig:continuation}はcode segment同士の関係を表したものである。
+\begin{figure}[htpb]
+  \begin{center}
+    %%\includegraphics[width=9cm]{figures/continuation.eps}
+  \end{center}
+  \caption{code segment間の``継続''}
+  \label{fig:continuation}
+\end{figure}%
+code segment\verb|start|は実行を終えるとgotoによって
+別のcode segment \verb|A|もしくは\verb|B|に実行を継続する
+また、\verb|A|から\verb|B|,再び\verb|A|の用に継続を繰り返すことも可能だ。
+このように、code segmentからgotoを用いて別のcode segmentへ飛ぶ
+構成はオートマトンと似た構造になっていることがわかる。
+ただしCbCの継続ではinterfaceと呼ばれるcode segmentへの引数が存在し、
+継続して実行されたcode segmntは前のcode segmentからの状態を
+引数によって受け取ることができる。
+
+以下では実装に必要なCbCの構文、
+code segmentの定義と継続(goto)について説明する。
+\paragraph{code segment}
+はCbCにおける最も基本的な処理単位である。
+構文としては通常の関数と同じであるが、型は``\_\_code''となる。
+ただし、code segmentは関数のようにリターンすることはないので、
+これはcode segmentであることを示すフラグの様なものである。
+
+code segmentの処理内容も通常の関数と同じように定義されるが、
+Cと違いcode segmentではforやwhile, returnなどの構文は存在しない。
+ループ等の制御は自分自身への再帰的な継続によって実現されることになる。
+
+\paragraph{継続 (goto)}
+はcode segment間の移動を表す。
+構文としてはgotoをつかっているがCにおけるlabelへのgotoとは違い、
+gotoの後ろに関数呼び出しの様な形をとる。
+例として、あるcode segment \verb|cs|への継続は
+\verb|goto cs(10, "test");|となる。
+これにより、csに対して引数\verb|10|と\verb|"test"|を渡すことができる。
+ただし関数コールとは違い、継続ではコールスタックの拡張を行わない。
+代わりにgotoを発行したcode segmentの持つスタック自体に次のcode segment
+の引数を書き込むことになる。また、returnアドレスのpushなども行わない。
+
+\section{GCCの構成}
+\subsection{GCCの基本構造}
+GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
+以下ではそのpassの中でも重要なものをその実行順に説明する。
+\begin{description}
+  \item[parsing] 一般的なコンパイラと同じく、GCCもまずはパーサによって
+	ソースコードを解析し、解析した結果はGeneric Treeと呼ばれる
+	tree構造の構造体に格納される
+	(Generic Treeに関しては\ref{sec:generic}で説明)。
+	Cのパーサは c\_parse\_* という関数名で統一されている。
+  \item[gimplification] この段階ではGeneric Treeをもとにこれを
+	GIMPLEに変換していく(GIMPLEは\ref{sec:gimple}で説明)。
+  \item[GIMPLE optimization] 前段階で変換したGIMPLEに対して最適化を行う。
+	この最適化には``Dead store elimination''やif文等の条件判定を最適化する
+	``Lower control flow''などが含まれる。
+  \item[RTL generation] ここで、GIMPLEをもとにRTLを生成する(\ref{sec:rtl}で説明)。
+	この段階でほぼ言語依存性がなくなる。
+	GIMPLEを解析してRTLを生成する関数はexpand\_* という名前で統一されている。
+  \item[RTL optimization] 前段階で生成されたRTLに対して最適化を行う。
+	この最適化には必要のないコードを除去する``Cleanup control flow graph''や
+	無駄に複数回行われる演算を減らす``Common subexpression elimination''
+	などがある。
+  \item[Output assembly]
+    最後にRTLをもとにターゲットマシンのアセンブリに変換する。
+\end{description}
+これらの処理は図\ref{fig:GCC-pass}のように表される。
+\begin{figure}[htbp]
+  \begin{center}
+    %\includegraphics[width=.5\textwidth]{figures/GCC-pass.eps}
+  \end{center}
+  \caption{GCCのpass}
+  \label{fig:GCC-pass}
+\end{figure}
+各passは通常は各々の関数毎に行われるものだが、
+inline関数の処理や、関数間での最適化を行う場合には
+一つのソースファイル毎に行われる。
+また、ここでは説明してないがTokenizer(字句解析器)ももちろん存在する。
+しかしこれは一般的なコンパイラと同じくparserの一部として同じpassで
+行われているので割愛した。
+
+\subsection{Tail call elimination}
+最適化のひとつである``Tail call elimination''は、
+通常call命令を使用すべき関数呼び出しにおいて、
+jump命令に変更するというものである。
+この最適化は本研究におけるCbCコンパイラの実装に深く関わってくる。
+本節ではこの最適化機構について詳しく説明する。
+
+\subsubsection{Tail callの概要}
+具体的に説明する。
+まずmain関数から関数Aを呼び出していて、
+関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える。
+このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
+そこで再びret命令をつかってmainに戻ることになる。
+``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
+この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[width=0.5\textwidth]{figures/GCC-TailCall.eps}
+  \end{center}
+  \caption{Tail call eliminationの例}
+  \label{fig:Tail call}
+\end{figure}
+
+次に``Tail call elimination''によって、
+アセンブリレベルでどのようにコードが変わるのか、
+スタックの変化も交えて見てみる。
+この例では最も一般的に使われているi386形式のアセンブラを使用している。
+
+図\ref{fig:Tail call}と同じように呼び出される関数main, A, Bを
+リスト\ref{code:main A B}の様に定義する。
+\begin{center}
+  \begin{minipage}[tb]{.7\textwidth}
+    \begin{lstlisting}[caption=関数main\, A\, Bの例,label=code:main A B]
+void B(int A, int A, int C){
+    //printf("B: a=%d, b=%d, c=%d\n", A, B, C);
+    return ;
+}
+void A(int a, int b, int c, int d){
+    //printf("A: a=%d, b=%d, c=%d, d=%d\n", a, b, c, d);
+    return B(a, b, c+d);
+}
+int main(int argc, char **argv){
+    //printf("main: \n");
+    A(10, 20, 30, 40);
+    return 0;
+}
+    \end{lstlisting}
+  \end{minipage}
+\end{center}
+これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
+次のリスト\ref{code:compiled A}のようなコードが出力される。
+(ここではTailcall最適化が影響をあたえる関数Aのみをしめした)
+\begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A]
+A:
+    pushl   %ebp
+    movl    %esp, %ebp
+    subl    $24, %esp
+    movl    20(%ebp), %eax
+    addl    16(%ebp), %eax
+    movl    %eax, 8(%esp)
+    movl    12(%ebp), %eax
+    movl    %eax, 4(%esp)
+    movl    8(%ebp), %eax
+    movl    %eax, (%esp)
+    call    B
+    leave
+    ret
+    .size   A, .-A
+\end{lstlisting}
+Tail callをしない場合はAのスタック領域の上にBのスタック領域が確保され、
+Bが終了するとそれが破棄される形になる。
+
+次にTail call eliminationが行われた場合の
+コンパイル結果をリスト\ref{code:tailcalled A}に示す。
+\begin{center}
+  \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A]
+A:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    20(%ebp), %eax
+    addl    %eax, 16(%ebp)
+    popl    %ebp
+    jmp     B
+    .size   A, .-A
+  \end{lstlisting}
+\end{center}
+\verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。
+ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に
+Bのための引数を書き込んでいることが分かる。
+ただし、変数aとbは書き込む位置も値も変わらないので触れられていない。
+
+\subsubsection{Tail call時のスタック}
+このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
+\begin{figure}[htpb]
+  \begin{center}
+    %\includegraphics[width=.8\textwidth]{figures/stack-tailcall.eps}
+  \end{center}
+  \caption{関数AからBを呼び出す時のスタックの様子(Tail call)}
+  \label{fig:stack-tailcall}
+\end{figure}
+図\ref{fig:stack-tailcall}の各ステップは次のような状態を表している。
+\begin{description}
+  \item[(a)] mainからAが呼ばれた直後の状態。espは引数のトップをさしてるが、
+    ebpはmainの引数をさしたまま
+  \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
+  \item[(c)] A自身のスタックフレームにB用の引数をつめる。
+  \item[(d)] ebpを元に戻す。その後関数Bにjump。
+\end{description}
+(a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
+普通の関数では(b)と(c)の間にいくつかの処理があると思われるが、
+ここでは省略した。
+通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
+しかし、関数AのTail call elimination後のコードを見ても分かる通り、
+無駄な処理が少なくなっていることが分かる。
+これがTail call eliminationにおける最適化の主な効果である。
+最大の効果が得られるのは、caller関数が持っている引数を
+callee関数に直接渡す場合である。
+この時はスタック操作は全く必要なく、単にjump命令のみになる。
+
+\subsection{Tail callの条件}
+Tail callが可能かどうかの条件についてここで考察する。
+必要に応じて前節の図\ref{fig:stack-tailcall}と、図\ref{code:main A B}
+を説明に用いるので参考にしていただきたい。
+
+まず最初の条件として、
+``関数コールがreturnの直前にある''ということは自明だろう。
+voidでなく何らかの型を返す関数ならreturn文の値自体に関数呼び出しがあることになる。
+これは関数Bが戻る際にAを経由せず、mainに直接戻ることから必ず必要な条件である。
+また、これに関連して``関数の返す型がcallerとcalleeで一致している''
+ことが必要となる。
+
+また、図の(c)にてcallee関数Bのための引数をスタックに上書きしているが、
+この領域はAのためのスタックフレームであることは説明した。
+ここでもしBの引数が5つ以上あったらどうなるだろうか?
+図を見て分かる通り、mainのスタックまで書きつぶすことになってしまう。
+このことから``caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい''
+という条件が必要だと分かる。
+
+最後にcallee用の引数を格納する順番が問題になる。
+通常、引数は関数定義の右から順にスタックにつめられる。
+例えば図\ref{code:main A B}のコードにおいて、AからBの呼び出しが
+\verb|B(c, b, c+d)|となっていたらどうだろうか?
+最初に\verb|c+d|の書き込みによって変数cは上書きされてしまう。
+そのため、最後に書き込む引数cは上書きされたc+dが使われ、
+実行結果はまったく違うものになってしまうだろう。
+よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
+という条件も必要となる。
+
+他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
+\begin{itemize}
+  \item 関数コールがreturnの直前にある
+  \item 関数の返す型がcallerとcalleeで一致している
+  \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
+  \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
+\end{itemize}
+
+CbCコンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。
+
+
+
+\section{実装}
+GCCへのCbCのコンパイル機能の実装を行う。
+実装における最大の問題はgoto文でのcode segmentへのjump
+の際のスタックフレームの状態をどう扱うかである。
+先に述べたようにcode segmentへ飛ぶ時は Tail call を使用するのだが、
+その条件としてcaller関数の引数サイズはcallee関数と同じか
+より大きくなければならない。
+
+これを解決するために、この実装ではcode segmentの
+引数サイズを一定にすることにした。
+どのようなcode segmentを定義してもスタックは一定に保たれる。
+
+以下の節ではそれぞれの行程について簡単に説明する。
+
+\subsection{\_\_code基本型の追加とパース}
+まず最初に必要となるのが``\_\_code''という予約語を定義することである。
+Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されている。
+次のように修正した。
+\begin{lstlisting}[caption=reswords定義,label=code:reswords]
+static const struct resword reswords[] =
+{
+          :
+    { "_Decimal128",      RID_DFLOAT128, D_EXT },
+    { "__alignof",        RID_ALIGNOF,    0 },
+    { "__attribute__",    RID_ATTRIBUTE,  0 },
+    /* CbC project */
+    { "__code",           RID_CbC_CODE,   0 },
+          :
+\end{lstlisting}
+ここで``\_\_code''を定義することで、Tokenizerから
+それを予約語として認識できるようになる。
+
+もう一つ必要なものが、\_\_code型であることを示すidである。
+これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
+データを保持する \verb|c_declapecs|構造体で使用される。
+void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
+これは gcc/c-tree.h にて定義されており次のようになる。
+\begin{lstlisting}[caption=c\_typespec\_keyword定義 ,label=code:c_typespec_keyword]
+enum c_typespec_keyword {
+    :
+  cts_int,
+  cts_float,
+  cts_double,
+  cts_CbC_code,
+  cts_dfloat32,
+    :
+};
+\end{lstlisting}
+以上により、\_\_codeをパースする準備ができた。
+実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
+\verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
+\verb|declspecs_add_type()|関数に統一されている。
+この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
+以下のようになる。
+\begin{lstlisting}[caption=declspecs\_add\_type関数,label=code:declspecs_add_type]
+case RID_CbC_CODE:
+if (specs->long_p)
+  error ("both %<long%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->short_p)
+  error ("both %<short%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->signed_p)
+  error ("both %<signed%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->unsigned_p)
+  error ("both %<unsigned%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->complex_p)
+  error ("both %<complex%> and %<void%> in "
+      "declaration specifiers");
+  else
+  specs->typespec_word = cts_CbC_code;
+  return specs;
+\end{lstlisting}
+これは実際には\verb|case RID_VOID|とほぼ同じである。
+違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。
+同様にcode segmentの型はほぼ、void型と同じように扱うことになる。
+
+gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
+パースされた型を決定し、その分のちいさなtreeを生成する関数である。
+treeにする際はcode segmentは全てvoidと見なされるようにすることになっている。
+よってここで生成するtreeはvoidにしなければならない。
+\begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs]
+  case cts_void:
+  case cts_CbC_code:
+    gcc_assert (!specs->long_p && !specs->short_p
+                && !specs->signed_p && !specs->unsigned_p
+                && !specs->complex_p);
+    specs->type = void_type_node;
+    break;
+\end{lstlisting}
+これで\_\_codeによる型がvoid型にマップされた。
+
+
+\subsection{code segment の tree 表現}
+次に、関数と同じようにパースされるcode segmentのtreeを
+後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
+この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
+具体的には以下の様な関数になる。
+\begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment]
+tree
+build_code_segment_type (tree value_type, tree arg_types)
+{
+    tree t;
+
+    /* Make a node of the sort we want.  */
+    t = make_node (FUNCTION_TYPE);
+    TREE_TYPE (t) = value_type;
+    TYPE_ARG_TYPES (t) = arg_types;
+
+    CbC_IS_CODE_SEGMENT (t) = 1;
+
+    if (!COMPLETE_TYPE_P (t))
+        layout_type (t);
+    return t;
+}
+\end{lstlisting}
+\verb|CbC_IS_CODE_SEGMENT|というマクロがcode segmentを示すフラグである
+(これは gcc/cbc-tree.hで定義してある)。
+ユーザが定義できるように gcc/tree.h で用意されている
+\verb|TYPE_LANG_FLAG_5|を使用した。
+この関数は通常のFUNCTION\_TYPEを作る \verb|build_function_type|と
+ほぼ同じ構造になっているが、
+このtreeをハッシュ表に登録しないところだけが違っている。
+
+つづいてこの\verb|build_code_segment_type|を使用すべき関数、
+\verb|grokdeclarator|を修正する。
+この関数は今までパースしてきた情報の入った構造体、
+\verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを
+gcc/tree.c の関数を使って生成している。
+
+この関数で\verb|build_function_type|関数を使用している箇所
+3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。
+これを、code segmentの場合には\verb|build_code_segment_type|を使うようにする。
+\begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator]
+  if ( declspecs->typespec_word &=&  cts_CbC_code )
+    {
+      type = build_code_segment_type (type, arg_types);
+    }
+  else
+    {
+      type = build_function_type (type, arg_types);
+    }
+\end{lstlisting}
+これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
+code segmentかをチェックする時はtree typeに対して
+\verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。
+
+
+\subsection{goto のパース}
+つづいてgoto文のパースが必要になる。
+goto文は通常のCの構文にも存在するが、CbCではgotoトークンの後に
+関数呼び出しと同じ構文がくる。
+
+Cの関数定義をパースしているのは
+\verb|c_parser_statement_after_labels|という関数である。
+この関数内の巨大な switch文における\verb|case RID_GOTO:|
+を修正することになる。
+具体的な修正は以下のようになった。
+\begin{lstlisting}[caption=goto文の構文解析,label=code:goto_parse]
+case RID_GOTO:
+  c_parser_consume_token (parser);
+  if (c_parser_next_token_is (parser, CPP_NAME))
+    {
+      tree id = c_parser_peek_token (parser)->value;
+      c_parser_consume_token (parser);
+      if ( !c_parser_next_token_is (parser, CPP_OPEN_PAREN) )
+        {
+          stmt = c_finish_goto_label (id);
+        }
+      else //CbC goto statement
+        {
+          struct c_expr expr;
+          tree exprlist;
+          // from c_parser_postfix_expression
+          expr.value = build_external_ref (id, 1, loc);
+          expr.original_code = ERROR_MARK;
+
+          c_parser_consume_token (parser);
+          // from c_parser_postfix_expression_after_primary
+          if (c_parser_next_token_is (parser, CPP_CLOSE_PAREN))
+              exprlist = NULL_TREE;
+          else
+              exprlist = c_parser_expr_list (parser, true);
+          c_parser_skip_until_found (parser, CPP_CLOSE_PAREN,
+                  "expected %<)%>");
+          expr.value = build_function_call (expr.value, exprlist);
+          CbC_IS_CbC_GOTO (expr.value) = 1;
+          CALL_EXPR_TAILCALL (expr.value) = 1;
+          //expr.value->common.lang_flag_5 = 1;
+          expr.original_code = ERROR_MARK;
+          expr = default_function_array_conversion (expr);
+          stmt = c_finish_return (expr.value);
+          CbC_HAVE_CbC_GOTO (current_function_decl) = 1;
+        }
+    }
+\end{lstlisting}
+gotoトークンを読み込むと次のトークンが何かによって処理が分かれる。
+CbCのgotoでは次のトークンはCPP\_NAMEとなるなんらかの変数のはずである。
+この後treeを生成する必要がある。
+ここでは\verb|build_function_call|によってCALL\_EXPRを生成している。
+また、それだけでなく、return文の直前であるために、
+\verb|c_finish_return|によってRETURN\_EXPRも生成している。
+この様な処理は
+\verb|c_parser_postfix_expression_after_primary|関数
+におけるCALL\_EXPRの生成とを参考にした。
+
+
+\subsection{expand\_callの分割}
+前節まではパーサ段階の実装を説明した。
+ここからはパーサによって生成されたtreeを元に、
+RTLを生成する段階について説明する。
+
+とはいうものの、実際にRTLをいじる必要があるのは
+code segmentへのjumpのみである。
+これはtree上ではTail callと認識されているので、
+そのtreeからRTLに変換する関数\verb|expand_call|を修正することになる。
+
+関数\verb|expand_call|は CALL\_EXPR treeをもとに
+関数呼び出しの際のスタック領域確保、引数の格納、
+関数へのcall命令の発行などを行うRTLを生成している。
+しかしこの\verb|expand_call|は約1200行も存在し、
+その大半はTail callが可能かの判定をしているにすぎない。
+そこでこの実装ではCbCのgotoのためのRTLを生成する関数\verb|expand_cbc_goto|
+を新たに作成した。
+
+\verb|expand_call|では、treeがcode segmentへのgotoだった場合にのみ
+\verb|expand_cbc_goto|を呼び出す形になる。
+次節にて関数\verb|expand_cbc_goto|の詳細について説明する。
+
+
+\subsection{expand\_cbc\_goto}
+\verb|expand_cbc_goto|の前にすこし\verb|expand_call|について説明する。
+この関数は大きく2つの処理に分けられる。
+前半はcallすべき関数のアドレスの算出や、与えられた引数を格納する場所を計算、
+またそれらのチェックなどを主に行う。
+後半には巨大なfor文ループが存在し、内部の処理が最大2回実行される。
+最初の1回はTail callをする前提での処理、次はTail callなしの処理である。
+最初の処理では途中でTail call不能と判断されると中断され、
+2回目の処理が優先される。
+
+\verb|expand_cbc_goto|はこの巨大なfor文の直前に呼ばれる。
+簡単に説明するとfor文の最初の処理と同じことをTail call可否のチェックなしで
+実装することになる。
+大まかな処理内容は以下の通り
+\begin{enumerate}
+  \item スタックフレームのベースアドレスRTLを取得
+  \item 各引数の格納されるアドレスRTLを取得
+  \item 各引数の式を計算 (一時的にレジスタに格納)
+  \item オーバーラップする引数を一時に変数に格納
+  \item 引数のスタックへの格納
+  \item call\_insn RTLの生成
+\end{enumerate}
+以下ではこれらの処理に付いてソースコードを交えながら説明する。
+
+
+\paragraph{スタックフレームポインタ}
+引数を格納するスタックフレームのベースアドレスは、以下のコードで取得される。
+\begin{verbatim}
+  argblock = virtual_incoming_args_rtx;
+\end{verbatim}
+この\verb|virtual_incoming_args_rtx|は現在実行中の
+caller側の関数のフレームポインタを表すrtxである。
+ia32アーキテクチャなら\verb|%ebp|レジスタがこのrtxに値する。
+Tail callでない通常のcallでは\verb|virtual_incoming_args_rtx|ではなく
+\verb|virtual_outgoing_args_rtx|が使用される。
+こちらはこの関数が現在使用しているスタックのトップを表すrtxである。
+もちろんTail callの場合にはcallerと同じフレームにcallee関数の
+引数を格納しなければならないので\verb|virtual_incoming_args_rtx|
+が使用されている。
+
+\paragraph{各引数の格納場所}
+次にそれぞれの引数を格納するためのアドレスを表すRTLを生成する。
+それぞれの引数がどのoffsetに格納されるかは\verb|expand_call|
+の中ですでに決定し、\verb|args|変数に入っている。
+これと、先ほど生成した\verb|argblock| rtxを元に計算する関数が
+\verb|compute_argument_addresses|関数である。
+こちらは gcc/calls.c にある関数をそのまま使用した。
+
+\paragraph{引数の計算}
+引数の計算を行う。
+\begin{lstlisting}[caption=引数の計算,label=code:compute_args]
+for (i = 0; i < num_actuals; i++)
+  {
+    if (args[i].reg == 0 || args[i].pass_on_stack)
+      {
+        preexpand_argument_expr (&args[i],
+                adjusted_args_size.var != 0);
+      }
+  }
+\end{lstlisting}
+この処理で一つ一つの引数に付いて、与えられた式を計算し、レジスタか
+もしくはスタックに格納しておく。
+\verb|preexpand_argument_expr|関数はgcc/calls.c
+にある\verb|store_one_arg|を元に作った関数で、
+一つだけ引数の情報を受け取り、計算して\verb|args[i].value|
+に計算の結果の格納されているrtxをおく。
+\verb|args[i].value|には一時的なレジスタや、スタック、
+もしくは変数の場所を示すrtxが格納されることになる。
+よって、あとは\verb|args[i].value|から\verb|args[i].stack|
+にデータを移動する命令をするだけでよい。
+
+\paragraph{オーバーラップ}
+\ref{sec:condition_of_tailcall}節でも説明したように、
+2つ以上の引数のもとのアドレスと格納先アドレスが相互に重なる場合、
+一時的な変数に格納する必要がある。
+\verb|expand_cbc_goto|ではこの処理を\verb|push_overlaps|関数に任せている。
+それほど大きな関数ではないので以下にコードを示す。
+\begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
+push_overlaps(struct arg_data *args, int num_actuals){
+    int i;
+    for (i=0; i<num_actuals; i++)
+    {
+        int dst_offset;
+        int src_offset;
+        rtx temp;
+        if ( (dst_offset=check_frame_offset(args[i].stack)) < 0 ) continue;
+        if ( (src_offset=check_frame_offset(args[i].value)) < 0 ) continue;
+        temp = assign_temp(args[i].tree_value, 1, 0, 0);
+        if ( args[i].mode==BLKmode )
+            emit_block_move ( temp, args[i].value, ARGS_SIZE_RTX(args[i].locate.size), 0 );
+        else
+            emit_move_insn ( temp, args[i].value );
+        args[i].value = temp;
+    }
+    return;
+}
+\end{lstlisting}
+重要なのは\verb|assign_temp|である。
+この関数は指定されたサイズ分のメモリ領域をスタックに確保する。
+これにより、オーバラップする可能性のある引数を一時的な領域に格納できる。
+\verb|emit_block_move|は構造体用の、
+\verb|emit_move_insn|はその他の基本型用のmove RTLを発行する関数である。
+また、ループの初期でこの引数の格納位置、読み込み位置がスタックフレーム内か
+どうかを確認し、両方が真の時のみ実行される。
+
+\paragraph{引数の格納}
+オーバラップの処理が終われば引数の格納である。
+この処理のために、引数の計算と同じく\verb|store_one_arg|
+のコードを参考にした関数\verb|expand_one_arg_push|を作成した。
+この関数では渡された引数の情報を元に、
+\verb|args->value|から\verb|args->stack|へデータを移動する
+RTLを生成する。
+具体的には以下の様な関数\verb|emit_push_insn|を使っている。
+\begin{lstlisting}[caption=引数の格納,label=code:push_args]
+  emit_push_insn (arg->value, arg->mode, TREE_TYPE (pval), size_rtx,
+                  parm_align, partial, reg, excess, argblock,
+                  ARGS_SIZE_RTX (arg->locate.offset), reg_parm_stack_space,
+                  ARGS_SIZE_RTX (arg->locate.alignment_pad));
+\end{lstlisting}
+
+\paragraph{CALL\_INSN}
+最後にCALL\_INSNを発行する処理が来る。
+\begin{lstlisting}[caption=CALL\_INSNの発行,label=emit CALL_INSN]
+  funexp = rtx_for_function_call (fndecl, addr);
+     :
+  emit_call_1 (funexp, exp, fndecl, funtype, unadjusted_args_size,
+               adjusted_args_size.constant, struct_value_size,
+               next_arg_reg, valreg, old_inhibit_defer_pop, call_fusage,
+               flags, & args_so_far);
+\end{lstlisting}
+この\verb|rtx_for_function_call|関数により、funexp変数にcallee関数の
+アドレスを示したrtxが格納され、
+それを引数に\verb|emit_call_1|関数を呼び出している。
+ここで、変数\verb|flags|は
+\verb|flags & ECF_SIBCALL != 0|を満たしている必要がある。
+これがこのCALL\_INSNがtail callであることを示すフラグとなる。
+
+
+
+\section{評価}
+今回実装できたGCCによるCbCコンパイラを評価する。
+ベンチマークを行い、Micro-Cとの比較を行った。
+
+今回ベンチマークに使用したプログラムはこれまでもMicro-Cの測定に使われていた
+テストルーチンで、普通のCのソースをCbCに機械的に変換したものである。
+引数に0を入れると変換される前の通常の関数のコード、
+引数に1を入れるとそれが変換されたCbCのコード、
+引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
+また、評価はia32アーキテクチャのFedora上で行った。
+測定結果は表\ref{tab:mc,gcc,compare}に示される。
+\begin{table}[htpb]
+  \centering
+  \small
+  \begin{tabular}{|l|r|r|r|} \hline
+    & ./conv1 1 & ./conv1 2 &  ./conv1 3 \\ \hline
+    Micro-C         & 8.97 & 2.19 & 2.73 \\ \hline \hline
+    GCC             & 4.87 & 3.08 & 3.65 \\ \hline
+    GCC (+omit)     & 4.20 & 2.25 & 2.76 \\ \hline
+    GCC (+fast) & 3.44 & 1.76 & 2.34 \\ \hline \hline
+    TCC             &122.28& 84.91&102.59\\ \hline
+  \end{tabular}
+  \caption{Micro-C, GCCの実行速度比較 (単位 秒)}
+  \label{tab:mc,gcc,compare}
+\end{table}
+
+通常のTail call eliminationのみを有効にした場合の結果が2行目のデータである。
+この結果では引数に1を入れた場合、すなわちMicro-C用に改良されてない
+コードでは2倍以上の速度になっていることが分かる。
+しかし、Micro-Cに特化したコードでは速度が負けている。
+
+次の``GCC (+omit)''では最適化フラグ
+-fomit-frame-pointerを付加してコンパイルした。
+このフラグをたてた場合、関数の最初にフレームポインタをpush,
+このフラグをたてた場合、フレームポインタのpushやpopがなるべく
+少なくなるようにコンパイルされる。
+この場合では引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、
+やはり少し速度は勝てない。
+この結果には様々な要因が考えられるが、最大の理由は
+Micro-Cではfastcallが使われていることだと思われる。
+Micro-Cのコードでは関数呼び出しの際、スタックに全ての引数をつめるのではなく、
+できる限り開いているレジスタを使うようになっている。これがfastcallである。
+
+GCCはfastcallをサポートしているので、これも試してみた。
+fastcallを有効にするにはcode segment定義の際に
+\verb|__code __attribute__ ((fastcall)) test(){|
+として、型と関数名の間に挿入する。
+ここでは上記の-fomit-frame-pointerも有効にし、測定を行った。
+その結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。
+ここまで最適化を行って、Micro-Cの速度を超えることができた。
+
+この評価から本研究における目的の一つ、``CbCコードの高速化''を
+達成できたことが分かった。
+しかし、fastcallというオプションをわざわざつけるというのは無駄が多いだろう。
+GCCと互換性のあるCbCの処理系は他にないので、
+code segmentの場合はfastcallを強制させることも今後の課題として考えられる。
+
+\section{今後の課題と考察}
+
+
+
+
+
+
+
+
+
+\onecolumn
+
+
+\section{Continuation based C}\label{chp:CbC}
+\subsection{CbCとは}
+Continuation based C (以下CbC) は当研究室が提案するアセンブラよりも上
+位でC よりも下位な記述言語である\cite{kono2}。
+Cの仕様からループ制御や関数コールを取り除き、
+継続(goto) や code segmentを導入している。
+これによりスタックの操作やループ、関数呼び出しなどのより低レベルでの最適化を、
+ソースコードレベルで行うことができる。
+
+図\ref{fig:continuation}はcode segment同士の関係を表したものである。
+\begin{figure}[htpb]
+  \begin{center}
+    %\includegraphics[width=9cm]{figures/continuation.eps}
+  \end{center}
+  \caption{code segment間の``継続''}
+  \label{fig:continuation}
+\end{figure}%
+図中の丸はcode segment, 矢印は継続によるcode segment間の接続を表している。
+code segment\verb|start|は実行を終えるとgotoによって
+別のcode segment \verb|A|もしくは\verb|B|に実行を継続する
+\footnote{どちらにするかはもちろんif文で決定する。}。
+また、\verb|A|から\verb|B|,再び\verb|A|の用に継続を繰り返すことも可能だ。
+このように、code segmentからgotoを用いて別のcode segmentへ飛ぶ
+構成はオートマトンと似た構造になっていることがわかる。
+ただしCbCの継続ではinterfaceと呼ばれるcode segmentへの引数が存在し、
+継続して実行されたcode segmntは前のcode segmentからの状態を
+引数によって受け取ることができる。
+
+以下では実装に必要なCbCの構文、
+code segmentの定義と継続(goto)について説明する。
+\paragraph{code segment}
+code segmentはCbCにおける最も基本的な処理単位である。
+構文としては通常の関数と同じであるが、型は``\_\_code''となる。
+ただし、code segmentは関数のようにリターンすることはないので、
+これはcode segmentであることを示すフラグの様なものである。
+
+code segmentの処理内容も通常の関数と同じように定義されるが、
+Cと違いcode segmentではforやwhile, returnなどの構文は存在しない
+\footnote{言語仕様としては存在しないが、Micro-C versionでは
+whileやforを使用することは可能である。この場合はCbCでなく、
+CwC(Continuation with C)とよばれる。}。
+ループ等の制御は自分自身への再帰的な継続によって実現されることになる。
+
+\paragraph{継続 (goto)}
+code segmentは処理の基本単位となるが、
+そのcode segment間の移動はCbC独自の構文``goto''を使って実現される。
+これを``継続''という。
+このgotoはCにおけるlabelへのgotoとは違い、
+gotoの後ろに関数呼び出しの様な形をとる。
+例として、あるcode segment \verb|cs|への継続は
+\verb|goto cs(10, "test");|となる。
+これにより、csに対して引数\verb|10|と\verb|"test"|を渡すことができる。
+ただし関数コールとは違い、継続ではコールスタックの拡張を行わない。
+代わりにgotoを発行したcode segmentの持つスタック自体に次のcode segment
+の引数を書き込むことになる。また、必要のないreturnアドレスのpushなども行わない。
+
+
+\paragraph{コード例}
+簡単な実例として、code segmentによるloopの実装を以下に示す。
+\begin{figure}[h]
+  \begin{minipage}[b]{.45\textwidth}
+    \begin{lstlisting}[caption=CbCコード例,label=code:CbC-example]
+__code while_process(int total, int count){
+    printf("while_process: do something.\n");
+    total += count;
+    count++;
+    goto while_cond(total, count);
+}
+
+__code while_cond(int total, int count){
+    printf("while_cond: check condition.\n");
+    if ( count <= 100 ){
+        goto while_process(total, count);
+    }else{
+        goto while_end(total);
+    }
+}
+
+__code while_end(int total){
+    printf("while_end: the loop ended.\n");
+    printf("         : total = %d.\n", total);
+    goto cs_exit(0);
+}
+    \end{lstlisting}
+  \end{minipage}
+  \hfill
+  \begin{minipage}[b]{.3\textwidth}
+    %\includegraphics[width=\textwidth]{figures/CbC-loop.eps}
+    \caption{CbCコード例}
+    \label{fig:CbC-loop}
+  \end{minipage}
+\end{figure}
+図\ref{fig:CbC-loop}はこのコードをオートマトンのように表したものだ。
+このコードでは\verb|while_cond|が条件判定し真を得れば\verb|while_process|へ。
+\verb|while_process|は処理が終わると\verb|while_cond|に戻るので、
+ここでループが出来上がる。
+
+\begin{comment}
+
+\subsection{Micro-CベースのCbCコンパイラ}
+第\ref{chp:joron}章でも述べたように、
+現在CbCのソースコードのコンパイルにはMicro-Cをベースとした本研究室
+独自のコンパイラを使用している。
+
+しかし、
+
+\paragraph{現状}
+第\ref{chp:joron}章でも述べたように、
+現在CbCのソースコードのコンパイルにはMicro-Cをベースとした本研究室
+独自のコンパイラを使用している。
+
+\paragraph{問題点}
+
+\begin{itemize}
+  \item アーキテクチャ
+  \item
+\end{itemize}
+
+\end{comment}
+
+
+
+\section{The GNU Compiler Collection}\label{chp:GCC}
+\subsection{GCCの基本構造}
+GCCはコンパイラという名称を持っているが
+コンパイル、アセンブル、リンクまで、
+ソースコードを実行可能にするまでの変換を全て受け持っている。
+しかしCbCの拡張にはコンパイル以外は関わらないので、
+ここではCのコンパイル処理を扱うcc1というプログラムについて説明する。
+(以下、GCCはcc1と同じ意味で使用する)
+
+GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
+以下ではそのpassの中でも重要なものをその実行順に説明する。
+\begin{description}
+  \item[parsing] 一般的なコンパイラと同じく、GCCもまずはパーサによって
+	ソースコードを解析し、解析した結果はGeneric Treeと呼ばれる
+	tree構造の構造体に格納される
+	(Generic Treeに関しては\ref{sec:generic}で説明)。
+	Cのパーサは c\_parse\_* という関数名で統一されている。
+  \item[gimplification] この段階ではGeneric Treeをもとにこれを
+	GIMPLEに変換していく(GIMPLEは\ref{sec:gimple}で説明)。
+  \item[GIMPLE optimization] 前段階で変換したGIMPLEに対して最適化を行う。
+	この最適化には``Dead store elimination''やif文等の条件判定を最適化する
+	``Lower control flow''などが含まれる。
+  \item[RTL generation] ここで、GIMPLEをもとにRTLを生成する(\ref{sec:rtl}で説明)。
+	この段階でほぼ言語依存性がなくなる。
+	GIMPLEを解析してRTLを生成する関数はexpand\_* という名前で統一されている。
+  \item[RTL optimization] 前段階で生成されたRTLに対して最適化を行う。
+	この最適化には必要のないコードを除去する``Cleanup control flow graph''や
+	無駄に複数回行われる演算を減らす``Common subexpression elimination''
+	などがある。
+  \item[Output assembly]
+    最後にRTLをもとにターゲットマシンのアセンブリに変換する。
+\end{description}
+これらの処理は図\ref{fig:GCC-pass}のように表される。
+\begin{figure}[htbp]
+  \begin{center}
+	%\includegraphics[width=0.8\textwidth]{figures/GCC-pass.eps}
+  \end{center}
+  \caption{GCCのpass}
+  \label{fig:GCC-pass}
+\end{figure}
+各passは通常は各々の関数毎に行われるものだが、
+inline関数の処理や、関数間での最適化を行う場合には
+一つのソースファイル毎に行われる。
+また、ここでは説明してないがTokenizer(字句解析器)ももちろん存在する。
+しかしこれは一般的なコンパイラと同じくparserの一部として同じpassで
+行われているので割愛した。
+
+以下の節ではGCCにおいて重要なデータ構造であるGeneri Tree, GIMPLE, RTL
+について簡単に説明する。
+なお、詳しくはFree Software FoundationのGCCのWebページにある
+GCC Internals Manual\cite{gcc1}を参照していただきたい。
+
+\paragraph{Generic Tree}\label{sec:generic}
+この節ではGCCの中でも最も重要なデータ構造であるGeneric treeについて
+簡単に説明する。
+
+Generic Treeはパースしたソースコードの内容を表した
+ツリー構造のデータの集合である。
+例として、treeにはFUNCTION\_TYPEやCALL\_EXPR, INTEGER\_CST, PLUS\_EXPR
+などがあり、それぞれ関数型、関数呼び出し、整数値定数、足し算を表している。
+これらはそれぞれ別の構造体であるが、tree共用体がすべての構造体を
+メンバとして持っているので、treeですべてを表すことができる。
+c\_parse\_* 関数でCのソースをパースし、その部分に合うtreeが生成され、
+最終的に関数全体を表す一つのツリーとしてのtree構造体ができあがる。
+すべてのtreeの種類は gcc/tree.hがincludeする
+gcc/tree.def で定義されており、
+gcc/tree.c にはこのtreeを生成、もしくは操作する様々な関数が定義されている。
+
+具体的な例として、FUNCTION\_TYPEとCALL\_EXPRを次で説明する。
+この二つは本論文の主旨であるGCC拡張にも深く関わってくるtreeである。
+
+\subparagraph{FUNCTION\_TYPE}
+まずは関数の型を表すFUNCTION\_TYPEを見てみる。
+関数の型を表現する為に必要な情報としては関数の返す型、
+関数に渡す引数列(parameter)の型の二つが必要だろう。
+FUNCTION\_TYPEもこの二つを主な要素に持つ。
+図\ref{fig:FUNCTION_TYPE}は関数
+\verb|int test(int *, double)|をパースした際のtreeを表したものである。
+図の角丸の長方形はtree、矢印はtreeへのポインタを表している。
+\begin{figure}[htpb]
+  \begin{center}
+	%\includegraphics[width=0.8\textwidth]{figures/FUNCTION_TYPE.eps}
+  \end{center}
+  \caption{int test(int *, double)関数の型 FUNCTION\_TYPE}
+  \label{fig:FUNCTION_TYPE}
+\end{figure}
+図のFUNCTION\_TYPEから出ている``type''という矢印は関数の返す型である。
+これはint型なので、int型を表すINTEGER\_TYPEへのポインタとなっている。
+ただし、tree構造ではchar型でもINTEGER\_TYPEが使用される。
+この二つの型の違いを表すのはINTEGER\_TYPEのbit数を表す``size''から参照される
+INTEGER\_CSTである。 これは整数値定数を表し、ここでは32となっている。
+char型の場合はこれが8となる。
+実数値を表すREAL\_TYPEでも同じく、doubleなら64, floatなら32で表現される。
+
+このように関数を表すFUNCTION\_TYPEだけでなく、その返却値の型、
+ポインタ、引数、引数のリスト、int型のサイズにいたるまで、
+全てtreeで表現されている。
+図では省略したが、INTEGER\_TYPEではbit sizeに加えて、
+最小値や最大値もINTEGER\_CSTへのポインタが存在する。
+
+興味深いのは最後の引数型がVOID\_TYPEになっていることである。
+これは引数の最後を明示的に指定しており、
+これがない場合は、GCCでは可変長引数を持つ関数として扱うことになっている。
+\begin{comment}
+ <function_type 0x12bda20
+    type <void_type 0x42d14960 void VOID
+        align 8 symtab 0 alias set 2
+        pointer_to_this <pointer_type 0x42d149c0>>
+    type_5 SI
+    size <integer_cst 0x42d0a740 type <integer_type 0x42d140c0 bit_size_type> constant invariant 32>
+    unit size <integer_cst 0x42d0a400 type <integer_type 0x42d14060 long unsigned int> constant invariant 4>
+    align 32 symtab 0 alias set -1
+    arg-types <tree_list 0x12bca40
+        value <integer_type 0x42d14300 int public SI size <integer_cst 0x42d0a740 32> unit size <integer_cst 0x42d0a400 4>
+            align 32 symtab 0 alias set 3 precision 32 min <integer_cst 0x42d0a6e0 -2147483648> max <integer_cst 0x42d0a700 2147483647>
+            pointer_to_this <pointer_type 0x42d14d20>>
+        chain <tree_list 0x12bca20 value <integer_type 0x42d14300 int>
+            chain <tree_list 0x12bca00 value <integer_type 0x42d14300 int>
+                chain <tree_list 0x12bc9e0 value <integer_type 0x42d14300 int>
+                    chain <tree_list 0x42d202a0 value <void_type 0x42d14960 void>>>>>>    pointer_to_this <pointer_type 0x12bf300>>
+\end{comment}
+
+
+\subsection{Tail call elimination}\label{sec:tailcall}
+``Tail call elimination''は通常call命令を使用すべき
+関数呼び出しで、jump命令に変更するというものである。
+この最適化は本研究におけるCbCコンパイラの実装に深く関わってくる。
+本節ではこの最適化機構について詳しく説明する。
+
+\paragraph{Tail callの概要}
+具体的に説明する。
+まずmain関数から関数Aを呼び出していて、
+関数Aの最後の処理(return直前)では次に関数Bを呼び出している状況を考える。
+このあと関数Bの処理が終了すると、ret命令により一旦関数Aに戻ってきて、
+そこで再びret命令をつかってmainに戻ることになる。
+``Tail call elimination''ではこのBからAに戻る無駄な処理を低減する。
+この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
+\begin{figure}[htpb]
+  \begin{center}
+	%\includegraphics[width=0.6\textwidth]{figures/GCC-TailCall.eps}
+  \end{center}
+  \caption{Tail call eliminationの例}
+  \label{fig:Tail call}
+\end{figure}
+
+次に``Tail call elimination''によって、
+アセンブリレベルでどのようにコードが変わるのか、
+スタックの変化も交えて見てみる。
+この例では最も一般的に使われており、またMicro-C versionのCbCも対応している
+i386形式のアセンブラを使用している。
+
+図\ref{fig:Tail call}と同じように呼び出される関数main, A, Bを
+リスト\ref{code:main A B}の様に定義する。
+\begin{center}
+  \begin{minipage}[tb]{.7\textwidth}
+    \begin{lstlisting}[caption=関数main\, A\, Bの例,label=code:main A B]
+void B(int A, int A, int C){
+    //printf("B: a=%d, b=%d, c=%d\n", A, B, C);
+    return ;
+}
+void A(int a, int b, int c, int d){
+    //printf("A: a=%d, b=%d, c=%d, d=%d\n", a, b, c, d);
+    return B(a, b, c+d);
+}
+int main(int argc, char **argv){
+    //printf("main: \n");
+    A(10, 20, 30, 40);
+    return 0;
+}
+    \end{lstlisting}
+  \end{minipage}
+\end{center}
+これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
+次のリスト\ref{code:compiled A},\ref{code:compiled main}のようなコードが出力される。
+(ただし関数Bは最適化に関係しないのでここでは省いた。)
+\begin{center}
+  \begin{minipage}[t]{.45\textwidth}
+      \begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A]
+A:
+    pushl   %ebp
+    movl    %esp, %ebp
+    subl    $24, %esp
+    movl    20(%ebp), %eax
+    addl    16(%ebp), %eax
+    movl    %eax, 8(%esp)
+    movl    12(%ebp), %eax
+    movl    %eax, 4(%esp)
+    movl    8(%ebp), %eax
+    movl    %eax, (%esp)
+    call    B
+    leave
+    ret
+    .size   A, .-A
+      \end{lstlisting}
+    \end{minipage}
+    \hfill
+    \begin{minipage}[t]{.45\textwidth}
+      \begin{lstlisting}[caption=関数mainのコンパイル結果,label=code:compiled main]
+main:
+    leal    4(%esp), %ecx
+    andl    $-16, %esp
+    pushl   -4(%ecx)
+    pushl   %ebp
+    movl    %esp, %ebp
+    pushl   %ecx
+    subl    $20, %esp
+    movl    $40, 12(%esp)
+    movl    $30, 8(%esp)
+    movl    $20, 4(%esp)
+    movl    $10, (%esp)
+    call    A
+    movl    $0, %eax
+    addl    $20, %esp
+    popl    %ecx
+    popl    %ebp
+    leal    -4(%ecx), %esp
+    ret
+    .size   main, .-main
+    \end{lstlisting}
+  \end{minipage}
+\end{center}
+
+\begin{comment}
+このとき、関数Aが呼ばれて、関数Bを呼ぶまでのスタックの様子を表したものが
+図\ref{fig:stack-normal},
+関数Bから戻ってきてmainに戻るまでのスタックの様子を表したものが
+図\ref{fig:stack-normal}である。
+\begin{figure}[htpb]
+  \begin{minipage}[tb]{.45\textwidth}
+    \begin{flushright}
+      %\includegraphics[width=1.5\textwidth]{figures/stack-normal.eps}
+    \end{flushright}
+    \caption{関数AからBをcallする時のスタックの様子}
+    \label{fig:stack-normal}
+  \end{minipage}
+  \hfill
+  \begin{minipage}[tb]{.45\textwidth}
+    \begin{flushleft}
+      %\includegraphics[width=1.3\textwidth]{figures/stack-normal2.eps}
+    \end{flushleft}
+    \caption{Bからreturnしたあとmainにもどる時のスタックの様子}
+    \label{fig:stack-normal}
+  \end{minipage}
+\end{figure}
+\begin{figure}[htpb]
+  \begin{center}
+    %\includegraphics[width=.8\textwidth]{figures/stack-normal.eps}
+  \end{center}
+  \caption{関数AからBをcallする時のスタックの様子}
+  \label{fig:stack-normal}
+\end{figure}
+番号毎に説明する。
+\begin{description}
+  \item[(a)] は最初にmainからAが呼ばれた状態
+  \item[(b)] にて、ebpをこの関数のフレームポインタにセットする
+  \item[(c)] ではBの引数のためのスタック領域を確保
+  \item[(d)] で引数を格納、そのあとBを呼び出す
+\end{description}
+図\ref{fig:stack-normal2}はBから戻ってきた後のスタックの様子である。
+\begin{figure}[htpb]
+  \begin{center}
+    %\includegraphics[width=.7\textwidth]{figures/stack-normal2.eps}
+  \end{center}
+  \caption{Bからreturnしたあとmainにもどる時のスタックの様子}
+  \label{fig:stack-normal2}
+\end{figure}
+(e),(f)はBから戻ってきたときの処理、(g)はmainにreturnするときの処理になる。
+\begin{description}
+  \item[(e)] Bから戻ってきた状態
+  \item[(f)] まずはスッタクポインタを元に戻す
+  \item[(g)] returnのため、ebpをmainの元似合わせる
+\end{description}
+\end{comment}
+
+Tail callをしない場合はAのスタック領域の上にBのスタック領域が確保され、
+Bが終了するとそれが破棄される形になる。
+
+次にTail call eliminationが行われた場合の
+コンパイル結果を図\ref{code:tailcalled A}に示す。
+\begin{center}
+  \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A]
+A:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    20(%ebp), %eax
+    addl    %eax, 16(%ebp)
+    popl    %ebp
+    jmp     B
+    .size   A, .-A
+  \end{lstlisting}
+\end{center}
+\verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。
+ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に
+Bのための引数を書き込んでいることが分かる。
+ただし、変数aとbは書き込む位置も値も変わらないので触れられていない。
+このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
+\begin{figure}[htpb]
+  \begin{center}
+    %\includegraphics[width=.8\textwidth]{figures/stack-tailcall.eps}
+  \end{center}
+  \caption{関数AからBを呼び出す時のスタックの様子(Tail call)}
+  \label{fig:stack-tailcall}
+\end{figure}
+図\ref{fig:stack-tailcall}の各ステップは次のような状態を表している。
+\begin{description}
+  \item[(a)] mainからAが呼ばれた直後の状態。espは引数のトップをさしてるが、
+    ebpはmainの引数をさしたまま
+  \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
+  \item[(c)] A自身のスタックフレームにB用の引数をつめる。
+  \item[(d)] ebpを元に戻す。その後関数Bにjump。
+\end{description}
+(a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
+普通の関数では(b)と(c)の間にいくつかの処理があると思われるが、
+ここでは省略した。
+通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
+しかし、関数AのTail call elimination後のコードを見ても分かる通り、
+無駄な処理が少なくなっていることが分かる。
+これがTail call eliminationにおける最適化の主な効果である。
+最大の効果が得られるのは、caller関数が持っている引数を
+callee関数に直接渡す場合である。
+この時はスタック操作は全く必要なく、単にjump命令のみになる。
+
+\paragraph{Tail callの条件}\label{sec:condition_of_tailcall}
+Tail callが可能かどうかの条件についてここで考察する。
+必要に応じて前節の図\ref{fig:stack-tailcall}と、図\ref{code:main A B}
+を説明に用いるので参考にしていただきたい。
+
+まず最初の条件として、
+``関数コールがreturnの直前にある''ということは自明だろう。
+voidでなく何らかの型を返す関数ならreturn文の値自体に関数呼び出しがあることになる。
+これは関数Bが戻る際にAを経由せず、mainに直接戻ることから必ず必要な条件である。
+また、これに関連して``関数の返す型がcallerとcalleeで一致している''
+ことが必要となる。
+\footnote{int型のBとchar型のAなら自明なキャストが可能かという問題もあるが、
+これは本論文では省略する。なぜならcode segmentは全部void型だからである。}
+
+また、図の(c)にてcallee関数Bのための引数をスタックに上書きしているが、
+この領域はAのためのスタックフレームであることは説明した。
+ここでもしBの引数が5つ以上あったらどうなるだろうか?
+図を見て分かる通り、mainのスタックまで書きつぶすことになってしまう。
+このことから``caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい''
+という条件が必要だと分かる。
+
+最後にcallee用の引数を格納する順番が問題になる。
+通常、引数は関数定義の右から順にスタックにつめられる
+\footnote{アーキテクチャによっては逆のものもあるかもしれないが、
+ここでは順序があるということが重要}。
+例えば図\ref{code:main A B}のコードにおいて、AからBの呼び出しが
+\verb|B(c, b, c+d)|となっていたらどうだろうか?
+最初に\verb|c+d|の書き込みによって変数cは上書きされてしまう。
+そのため、最後に書き込む引数cは上書きされたc+dが使われ、
+実行結果はまったく違うものになってしまうだろう。
+よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
+という条件も必要となる。
+
+他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
+\begin{itemize}
+  \item 関数コールがreturnの直前にある
+  \item 関数の返す型がcallerとcalleeで一致している
+  \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
+  \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
+\end{itemize}
+
+CbCコンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。
+
+
+\section{実装}\label{chp:impl}
+第\ref{chp:CbC}, \ref{chp:GCC}章をもとに、
+GCCへのCbCのコンパイル機能の実装を行う。
+実装における最大の問題はgoto文でのcode segmentへのjump
+の際のスタックフレームの状態をどう扱うかである。
+先に述べたようにcode segmentへ飛ぶ時は Tail call を使用するのだが、
+その条件としてcaller関数の引数サイズはcallee関数と同じか
+より大きくなければならない。
+
+これを解決するために、この実装ではcode segmentの
+引数サイズを一定にすることにした。
+どのようなcode segmentを定義してもスタックは一定に保たれる。
+
+実装の流れとしては次のようになる。
+\begin{enumerate}
+  \item \_\_code tokenの追加(Tokenizerで読み込めるようにする)
+  \item code segmentのパース及びtree生成
+  \item CbCのgoto ステートメントのパース及びtree生成
+  \item gotoステートメントtreeのRTLへの変換
+  \item その他エラーメッセージ処理やコード改良
+\end{enumerate}
+以下の節ではそれぞれの行程について詳しく説明する。
+
+\subsection{\_\_code基本型の追加とパース}
+まず最初に必要となるのが``\_\_code''という予約語を定義することである。
+Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されている。
+次のように修正した。
+\begin{lstlisting}[caption=reswords定義,label=code:reswords]
+static const struct resword reswords[] =
+{
+          :
+    { "_Decimal128",      RID_DFLOAT128, D_EXT },
+    { "__alignof",        RID_ALIGNOF,    0 },
+    { "__attribute__",    RID_ATTRIBUTE,  0 },
+    /* CbC project */
+    { "__code",           RID_CbC_CODE,   0 },
+          :
+\end{lstlisting}
+ここで``\_\_code''を定義することで、Tokenizerから
+それを予約語として認識できるようになる。
+
+もう一つ必要なものが、\_\_code型であることを示すidである。
+これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
+データを保持する \verb|c_declapecs|構造体で使用される。
+void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
+これは gcc/c-tree.h にて定義されており次のようになる。
+\begin{lstlisting}[caption=c\_typespec\_keyword定義 ,label=code:c_typespec_keyword]
+enum c_typespec_keyword {
+    :
+  cts_int,
+  cts_float,
+  cts_double,
+  cts_CbC_code,
+  cts_dfloat32,
+    :
+};
+\end{lstlisting}
+以上により、\_\_codeをパースする準備ができた。
+実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
+\verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
+\verb|declspecs_add_type()|関数に統一されている。
+この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
+以下のようになる。
+\begin{lstlisting}[caption=declspecs\_add\_type関数,label=code:declspecs_add_type]
+case RID_CbC_CODE:
+if (specs->long_p)
+  error ("both %<long%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->short_p)
+  error ("both %<short%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->signed_p)
+  error ("both %<signed%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->unsigned_p)
+  error ("both %<unsigned%> and %<void%> in "
+      "declaration specifiers");
+else if (specs->complex_p)
+  error ("both %<complex%> and %<void%> in "
+      "declaration specifiers");
+  else
+  specs->typespec_word = cts_CbC_code;
+  return specs;
+\end{lstlisting}
+これは実際には\verb|case RID_VOID|とほぼ同じである。
+違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。
+同様にcode segmentの型はほぼ、void型と同じように扱うことになる。
+
+gcc/c\_decl.cにある\verb|finish_declspecs|関数は\verb|c_declspecs|をもとに、
+パースされた型を決定し、その分のちいさなtreeを生成する関数である。
+treeにする際はcode segmentは全てvoidと見なされるようにすることになっている。
+よってここで生成するtreeはvoidにしなければならない。
+\begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs]
+  case cts_void:
+  case cts_CbC_code:
+    gcc_assert (!specs->long_p && !specs->short_p
+                && !specs->signed_p && !specs->unsigned_p
+                && !specs->complex_p);
+    specs->type = void_type_node;
+    break;
+\end{lstlisting}
+これで\_\_codeによる型がvoid型にマップされた。
+
+
+\subsection{code segment の tree 表現}
+次に、関数と同じようにパースされるcode segmentのtreeを
+後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
+この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
+具体的には以下の様な関数になる。
+\begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment]
+tree
+build_code_segment_type (tree value_type, tree arg_types)
+{
+    tree t;
+
+    /* Make a node of the sort we want.  */
+    t = make_node (FUNCTION_TYPE);
+    TREE_TYPE (t) = value_type;
+    TYPE_ARG_TYPES (t) = arg_types;
+
+    CbC_IS_CODE_SEGMENT (t) = 1;
+
+    if (!COMPLETE_TYPE_P (t))
+        layout_type (t);
+    return t;
+}
+\end{lstlisting}
+\verb|CbC_IS_CODE_SEGMENT|というマクロがcode segmentを示すフラグである
+(これは gcc/cbc-tree.hで定義してある)。
+ユーザが定義できるように gcc/tree.h で用意されている
+\verb|TYPE_LANG_FLAG_5|を使用した。
+この関数は通常のFUNCTION\_TYPEを作る \verb|build_function_type|と
+ほぼ同じ構造になっているが、
+このtreeをハッシュ表に登録しないところだけが違っている。
+
+つづいてこの\verb|build_code_segment_type|を使用すべき関数、
+\verb|grokdeclarator|を修正する。
+この関数は今までパースしてきた情報の入った構造体、
+\verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを
+gcc/tree.c の関数を使って生成している。
+
+この関数で\verb|build_function_type|関数を使用している箇所
+3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。
+これを、code segmentの場合には\verb|build_code_segment_type|を使うようにする。
+\begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator]
+  if ( declspecs->typespec_word &=&  cts_CbC_code )
+    {
+      type = build_code_segment_type (type, arg_types);
+    }
+  else
+    {
+      type = build_function_type (type, arg_types);
+    }
+\end{lstlisting}
+これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
+code segmentかをチェックする時はtree typeに対して
+\verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。
+
+
+\subsection{goto のパース}
+つづいてgoto文のパースが必要になる。
+goto文は通常のCの構文にも存在するが、CbCではgotoトークンの後に
+関数呼び出しと同じ構文がくる。
+
+Cの関数定義をパースしているのは
+\verb|c_parser_statement_after_labels|という関数である。
+この関数内の巨大な switch文における\verb|case RID_GOTO:|
+を修正することになる。
+具体的な修正は以下のようになった。
+\begin{lstlisting}[caption=goto文の構文解析,label=code:goto_parse]
+case RID_GOTO:
+  c_parser_consume_token (parser);
+  if (c_parser_next_token_is (parser, CPP_NAME))
+    {
+      tree id = c_parser_peek_token (parser)->value;
+      c_parser_consume_token (parser);
+      if ( !c_parser_next_token_is (parser, CPP_OPEN_PAREN) )
+        {
+          stmt = c_finish_goto_label (id);
+        }
+      else //CbC goto statement
+        {
+          struct c_expr expr;
+          tree exprlist;
+          // from c_parser_postfix_expression
+          expr.value = build_external_ref (id, 1, loc);
+          expr.original_code = ERROR_MARK;
+
+          c_parser_consume_token (parser);
+          // from c_parser_postfix_expression_after_primary
+          if (c_parser_next_token_is (parser, CPP_CLOSE_PAREN))
+              exprlist = NULL_TREE;
+          else
+              exprlist = c_parser_expr_list (parser, true);
+          c_parser_skip_until_found (parser, CPP_CLOSE_PAREN,
+                  "expected %<)%>");
+          expr.value = build_function_call (expr.value, exprlist);
+          CbC_IS_CbC_GOTO (expr.value) = 1;
+          CALL_EXPR_TAILCALL (expr.value) = 1;
+          //expr.value->common.lang_flag_5 = 1;
+          expr.original_code = ERROR_MARK;
+          expr = default_function_array_conversion (expr);
+          stmt = c_finish_return (expr.value);
+          CbC_HAVE_CbC_GOTO (current_function_decl) = 1;
+        }
+    }
+\end{lstlisting}
+gotoトークンを読み込むと次のトークンが何かによって処理が分かれる。
+CbCのgotoでは次のトークンはCPP\_NAMEとなるなんらかの変数のはずである。
+この後treeを生成する必要がある。
+ここでは\verb|build_function_call|によってCALL\_EXPRを生成している。
+また、それだけでなく、return文の直前であるために、
+\verb|c_finish_return|によってRETURN\_EXPRも生成している。
+この様な処理は
+\verb|c_parser_postfix_expression_after_primary|関数
+におけるCALL\_EXPRの生成とを参考にした。
+
+
+\subsection{expand\_callの分割}
+前節まではパーサ段階の実装を説明した。
+ここからはパーサによって生成されたtreeを元に、
+RTLを生成する段階について説明する。
+
+とはいうものの、実際にRTLをいじる必要があるのは
+code segmentへのjumpのみである。
+これはtree上ではTail callと認識されているので、
+そのtreeからRTLに変換する関数\verb|expand_call|を修正することになる。
+
+関数\verb|expand_call|は CALL\_EXPR treeをもとに
+関数呼び出しの際のスタック領域確保、引数の格納、
+関数へのcall命令の発行などを行うRTLを生成している。
+しかしこの\verb|expand_call|は約1200行も存在し、
+その大半はTail callが可能かの判定をしているにすぎない。
+そこでこの実装ではCbCのgotoのためのRTLを生成する関数\verb|expand_cbc_goto|
+を新たに作成した。
+
+\verb|expand_call|では、treeがcode segmentへのgotoだった場合にのみ
+\verb|expand_cbc_goto|を呼び出す形になる。
+次節にて関数\verb|expand_cbc_goto|の詳細について説明する。
+
+
+\subsection{expand\_cbc\_goto}
+\verb|expand_cbc_goto|の前にすこし\verb|expand_call|について説明する。
+この関数は大きく2つの処理に分けられる。
+前半はcallすべき関数のアドレスの算出や、与えられた引数を格納する場所を計算、
+またそれらのチェックなどを主に行う。
+後半には巨大なfor文ループが存在し、内部の処理が最大2回実行される。
+最初の1回はTail callをする前提での処理、次はTail callなしの処理である。
+最初の処理では途中でTail call不能と判断されると中断され、
+2回目の処理が優先される。
+
+\verb|expand_cbc_goto|はこの巨大なfor文の直前に呼ばれる。
+簡単に説明するとfor文の最初の処理と同じことをTail call可否のチェックなしで
+実装することになる。
+大まかな処理内容は以下の通り
+\begin{enumerate}
+  \item スタックフレームのベースアドレスRTLを取得
+  \item 各引数の格納されるアドレスRTLを取得
+  \item 各引数の式を計算 (一時的にレジスタに格納)
+  \item オーバーラップする引数を一時に変数に格納
+  \item 引数のスタックへの格納
+  \item call\_insn RTLの生成
+\end{enumerate}
+以下ではこれらの処理に付いてソースコードを交えながら説明する。
+
+
+\paragraph{スタックフレームポインタ}
+引数を格納するスタックフレームのベースアドレスは、以下のコードで取得される。
+\begin{verbatim}
+  argblock = virtual_incoming_args_rtx;
+\end{verbatim}
+この\verb|virtual_incoming_args_rtx|は現在実行中の
+caller側の関数のフレームポインタを表すrtxである。
+ia32アーキテクチャなら\verb|%ebp|レジスタがこのrtxに値する。
+Tail callでない通常のcallでは\verb|virtual_incoming_args_rtx|ではなく
+\verb|virtual_outgoing_args_rtx|が使用される。
+こちらはこの関数が現在使用しているスタックのトップを表すrtxである。
+もちろんTail callの場合にはcallerと同じフレームにcallee関数の
+引数を格納しなければならないので\verb|virtual_incoming_args_rtx|
+が使用されている。
+
+\paragraph{各引数の格納場所}
+次にそれぞれの引数を格納するためのアドレスを表すRTLを生成する。
+それぞれの引数がどのoffsetに格納されるかは\verb|expand_call|
+の中ですでに決定し、\verb|args|変数に入っている。
+これと、先ほど生成した\verb|argblock| rtxを元に計算する関数が
+\verb|compute_argument_addresses|関数である。
+こちらは gcc/calls.c にある関数をそのまま使用した。
+
+\paragraph{引数の計算}
+引数の計算を行う。
+\begin{lstlisting}[caption=引数の計算,label=code:compute_args]
+for (i = 0; i < num_actuals; i++)
+  {
+    if (args[i].reg == 0 || args[i].pass_on_stack)
+      {
+        preexpand_argument_expr (&args[i],
+                adjusted_args_size.var != 0);
+      }
+  }
+\end{lstlisting}
+この処理で一つ一つの引数に付いて、与えられた式を計算し、レジスタか
+もしくはスタックに格納しておく。
+\verb|preexpand_argument_expr|関数はgcc/calls.c
+にある\verb|store_one_arg|を元に作った関数で、
+一つだけ引数の情報を受け取り、計算して\verb|args[i].value|
+に計算の結果の格納されているrtxをおく。
+\verb|args[i].value|には一時的なレジスタや、スタック、
+もしくは変数の場所を示すrtxが格納されることになる。
+よって、あとは\verb|args[i].value|から\verb|args[i].stack|
+にデータを移動する命令をするだけでよい。
+
+\paragraph{オーバーラップ}
+\ref{sec:condition_of_tailcall}節でも説明したように、
+2つ以上の引数のもとのアドレスと格納先アドレスが相互に重なる場合、
+一時的な変数に格納する必要がある。
+\verb|expand_cbc_goto|ではこの処理を\verb|push_overlaps|関数に任せている。
+それほど大きな関数ではないので以下にコードを示す。
+\begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
+push_overlaps(struct arg_data *args, int num_actuals){
+    int i;
+    for (i=0; i<num_actuals; i++)
+    {
+        int dst_offset;
+        int src_offset;
+        rtx temp;
+        if ( (dst_offset=check_frame_offset(args[i].stack)) < 0 ) continue;
+        if ( (src_offset=check_frame_offset(args[i].value)) < 0 ) continue;
+        temp = assign_temp(args[i].tree_value, 1, 0, 0);
+        if ( args[i].mode==BLKmode )
+            emit_block_move ( temp, args[i].value, ARGS_SIZE_RTX(args[i].locate.size), 0 );
+        else
+            emit_move_insn ( temp, args[i].value );
+        args[i].value = temp;
+    }
+    return;
+}
+\end{lstlisting}
+重要なのは\verb|assign_temp|である。
+この関数は指定されたサイズ分のメモリ領域をスタックに確保する。
+これにより、オーバラップする可能性のある引数を一時的な領域に格納できる。
+\verb|emit_block_move|は構造体用の、
+\verb|emit_move_insn|はその他の基本型用のmove RTLを発行する関数である。
+また、ループの初期でこの引数の格納位置、読み込み位置がスタックフレーム内か
+どうかを確認し、両方が真の時のみ実行される。
+
+\paragraph{引数の格納}
+オーバラップの処理が終われば引数の格納である。
+この処理のために、引数の計算と同じく\verb|store_one_arg|
+のコードを参考にした関数\verb|expand_one_arg_push|を作成した。
+この関数では渡された引数の情報を元に、
+\verb|args->value|から\verb|args->stack|へデータを移動する
+RTLを生成する。
+具体的には以下の様な関数\verb|emit_push_insn|を使っている。
+\begin{lstlisting}[caption=引数の格納,label=code:push_args]
+  emit_push_insn (arg->value, arg->mode, TREE_TYPE (pval), size_rtx,
+                  parm_align, partial, reg, excess, argblock,
+                  ARGS_SIZE_RTX (arg->locate.offset), reg_parm_stack_space,
+                  ARGS_SIZE_RTX (arg->locate.alignment_pad));
+\end{lstlisting}
+
+\paragraph{CALL\_INSN}
+最後にCALL\_INSNを発行する処理が来る。
+\begin{lstlisting}[caption=CALL\_INSNの発行,label=emit CALL_INSN]
+  funexp = rtx_for_function_call (fndecl, addr);
+     :
+  emit_call_1 (funexp, exp, fndecl, funtype, unadjusted_args_size,
+               adjusted_args_size.constant, struct_value_size,
+               next_arg_reg, valreg, old_inhibit_defer_pop, call_fusage,
+               flags, & args_so_far);
+\end{lstlisting}
+この\verb|rtx_for_function_call|関数により、funexp変数にcallee関数の
+アドレスを示したrtxが格納され、
+それを引数に\verb|emit_call_1|関数を呼び出している。
+ここで、変数\verb|flags|は
+\verb|flags & ECF_SIBCALL != 0|を満たしている必要がある。
+これがこのCALL\_INSNがtail callであることを示すフラグとなる。
+
+
+\section{評価}\label{chp:appraising}
+今回実装できたGCCによるCbCコンパイラを評価してみる。
+評価の手法としてはあるCbCプログラムをMicro-CとGCCでコンパイルして、
+その出力されたコードの実行速度を測れば良いだろう。
+
+今回測定に使用したプログラムはこれまでもMicro-Cの測定に使われていた
+テストルーチンで、普通のCのソースをCbCに機械的に変換したものである
+\footnote{ソースコードの全体は付録\ref{chp:conv1}に掲載する。}。
+引数に0を入れると変換される前の通常の関数のコード、
+引数に1を入れるとそれが変換されたCbCのコード、
+引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
+また、評価はia32アーキテクチャのFedora上で行った。
+測定結果は表\ref{tab:mc,gcc,compare}に示される。
+\begin{table}[htpb]
+  \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}
+
+通常のTail call eliminationのみを有効にした場合の結果が2行目のデータである。
+この結果では引数に1を入れた場合、すなわちMicro-C用に改良されてない
+コードでは2倍以上の速度になっていることが分かる。
+しかし、Micro-Cに特化したコードでは速度が負けている。
+
+次の``GCC (+omit)''では最適化フラグ
+-fomit-frame-pointerを付加してコンパイルした。
+このフラグをたてた場合、関数の最初にフレームポインタをpush,
+このフラグをたてた場合、フレームポインタのpushやpopがなるべく
+少なくなるようにコンパイルされる。
+この場合では引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、
+やはり少し速度は勝てない。
+この結果には様々な理由が考えられるが、最大の理由は
+Micro-Cではfastcallが使われていることだと思われる。
+Micro-Cのコードでは関数呼び出しの際、スタックに全ての引数をつめるのではなく、
+できる限り開いているレジスタを使うようになっている。これがfastcallである。
+
+GCCはfastcallをサポートしているので、これも試してみた。
+fastcallを有効にするにはcode segment定義の際に
+\verb|__code __attribute__ ((fastcall)) test(){|
+として、型と関数名の間に挿入する。
+ここでは上記の-fomit-frame-pointerも有効にし、測定を行った。
+その結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。
+ここまで最適化を行って、Micro-Cの速度を超えることができた。
+
+この評価から本研究における目的の一つ、``CbCコードの高速化''を
+達成できたことが分かった。
+しかし、fastcallというオプションをわざわざつけるというのは無駄が多いだろう。
+GCCと互換性のあるCbCの処理系は他にないので、
+code segmentの場合はfastcallを強制させることも今後の課題として考えられる。
+
+ちなみに、表の最後の行にあるTCCとは``Tiny C Compiler''のことである。
+詳細に付いては割愛するが、このコンパイラはCのソースコードを
+アセンブラを介さずに直接オブジェクトファイルに変換することができ、
+コンパイル時間を大幅に短縮している。
+本研究のGCC実装の前に、TCCにもCbCコンパイル機能の実装を行ったが、
+表の通り満足の行く結果ではなかった。
+\footnote{TCCでは実装手段が悪かったと思われる。
+gotoの際に毎回strcpyするようなこと
+を改良すれば大幅な高速化が望めるだろう。}。
+
+
+\section{今後の課題}\label{chp:problems}
+本研究の実装により、GCCを使ってCbCのソースコードを
+コンパイルすることができるようになった。
+また、これまでのMicro-Cベースのコンパイラではできなかった
+最適化をGCC上で実行できるようになった。
+
+しかし、未だに実装されてないCbCの構文がまだ残っている。
+また、一部アーキテクチャではコンパイル不能に陥る現象も発生している。
+これらの問題とその他改良点を今後の課題として以下に簡単に説明する。
+\begin{description}
+  \item[environment] 第\ref{chp:CbC}章では説明を省いたが、
+    CbCにはもう一つ、environment付きの継続という構文が存在する。
+    これは関数からcode segmentにgotoした場合に関数の呼び出し元に戻る
+    ことを可能にするものだが、今回この実装は間に合わなかった。
+  \item[code segmentポインタの計算] 今の実装では\verb|goto cs->next(a, b);|
+    のように呼び出し先code segmentを計算することができない。
+    第\ref{chp:appraising}章のconv1.cでは一旦別の変数に格納することによって回避している。
+  \item[PPCのRTL変換不能] PowerPCアーキテクチャにおいて、code segment
+    のポインタ参照へgotoすることができない。
+    これはRTLレベルで対応されてないことが原因と思われる。
+  \item[push\_overlaps] リスト\ref{code:push_overlaps}において、
+    余計な変数まで一時変数に格納することがある。
+    これは引数をスタックにおく順番を変えることで改良可能だ。
+  \item[-O2オプションの強制] CbCは-O2オプションをつけないとコンパイルできない。
+    なのでファイル名が.cbcの場合はこれを強制させる必要がある。
+  \item[fastcall] 第\ref{chp:appraising}章でも述べたように、
+    code segmentではfastcallを強制させることで高速化が期待できる。
+\end{description}
+この中から特に重要なのがenvironmentとcode segmentポインタの計算
+への対応だと考えている。
+この二つができればとりあえずCbCの現在の仕様を満たす。
+
+これらに加えて、GCCにはすでにC++やObjective-Cのコンパイルが可能である。
+これを活かし、CbC++, もしくはObjective-CbCといった既存の言語と
+CbCを組み合わせた言語に付いても考えてみる価値があるだろう。
+
+
+\begin{comment}
+\begin{itemize}
+  \item environment
+  \item PPCのRTL変換不能
+  \item parallel
+  \item ebpのpop, pushの除去
+  \item \verb|goto (ret)(a, b);|
+  \item -O3以上の対策
+  \item -O2 フラグの強制
+  \item code segmentは全部 \verb|__attribute__ ((fastcall))|でもいいか
+\end{itemize}
+\end{comment}
+
+\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/''.
+  \bibitem{takumi} 金城拓実. ``軽量継続を用いたゲームプログラムの分割と再構成の考察''.
+        琉球大学情報工学科 学位論文, Feb, 2006.
+\end{thebibliography}
+
+\end{document}
+