%        File: final.tex
%     Created: 火  2 05 02:00 PM 2008 J
% Last Change: 火  2 22 13:35 PM 2008 J
%
\documentclass[a4j]{jreport}
\usepackage{graduate_paper}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{multicol}
\usepackage{nonDefaultPackage/listings}
%\usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,bookmarkstype=toc]{hyperref}


\jtitle{Continuation based CコンパイラのGCC-4.2による実装}
\etitle{The implementation of Continuation based C Compiler on GCC} 
\year{平成19年度}
\thesis{卒業論文}
\logo{\includegraphics[width=15em]{figures/u-ryukyu-Mark.eps}}
\affiliation{琉球大学 工学部 情報工学科}
\author{045760E 与儀 健人\\ 指導教官 河野 真治}


\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}
\maketitle
\tableofcontents
\break
\listoffigures
\lstlistoflistings
%\listoftables

\chapter{序論}\label{chp:joron}
\section{研究の背景と目的}
当研究室ではContinuation based C(以下CbC)という言語を提案している。
このCbCはCと同じ様な構文であるが、よりアセンブリに近い形で実現されている。
そのため、C言語より細かく、アセンブリよりは高級なプログラミングを可能にする。

これまで当研究室ではCbCのコンパイルに、
太田昌孝氏のMicro-Cをベースにした独自のコンパイラを使用していた。
このコンパイラはi386, ppc, mips, spuなどのアーキテクチャに対応おり、
出力されるアセンブリもGCCのものと比較して、速度に大きな差は見られない。

しかし UNIX環境に置けるコンパイラの標準はGCCであることは明らかであり、
またGCCには最適化という機能が存在し、その機能をonにすればGCCの出力コードの
性能は格段に上昇する
\footnote{もちろんこれはアーキテクチャにも依存する。
i386アーキテクチャでの実行速度の測定結果は第\ref{chp:appraising}章を参照の事。}。
さらにGCCの対応しているアーキテクチャは数十種類に及ぶ。

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



\section{論文構成}
本論文は以下の様な構成になっている。
\begin{description}
  \item[第\ref{chp:CbC}章]CbCの概要について述べる。
  \item[第\ref{chp:GCC}章]CbCコンパイル機能の実装に関わるGCCの内部構造を述べる。
  \item[第\ref{chp:impl}章]本論文の主旨であるCbCコンパイル機能のGCCへの実装について説明する。
  \item[第\ref{chp:appraising}章]この実装によってどの程度の性能向上ができたかを評価する。
  \item[第\ref{chp:problems}章]実装によって明らかになった問題点、また今後の課題、改良点を論じる。
\end{description}
また、本研究ではGCCのversion-4.2.2
\footnote{実装を始めた当初は4.2.1. 2008/02/01には4.2.3がリリースされている。}
を使用した。
GCCのソースコードはFree Software FoundationのGCCページ
(http://www.gnu.org/software/gcc/mirrors.html)からダウンロード可能である。
論文内で示されるCのソースファイルはこのソースコードを展開したディレクトリを
カレントディレクトリとする相対パスで示されている。


\chapter{Continuation based C}\label{chp:CbC}
\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, 矢印は継続による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)について説明する。
\subsection{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)とよばれる。}。
ループ等の制御は自分自身への再帰的な継続によって実現されることになる。

\subsection{継続 (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なども行わない。


\subsection{コード例}
簡単な実例として、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}

\section{Micro-CベースのCbCコンパイラ}
第\ref{chp:joron}章でも述べたように、
現在CbCのソースコードのコンパイルにはMicro-Cをベースとした本研究室
独自のコンパイラを使用している。

しかし、

\subsection{現状}
第\ref{chp:joron}章でも述べたように、
現在CbCのソースコードのコンパイルにはMicro-Cをベースとした本研究室
独自のコンパイラを使用している。

\subsection{問題点}

\begin{itemize}
  \item アーキテクチャ
  \item 
\end{itemize}

\end{comment}



\chapter{The GNU Compiler Collection}\label{chp:GCC}
\section{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}を参照していただきたい。

\subsection{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である。

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

\subsubsection{CALL\_EXPR}
次にCALL\_EXPRの詳細を見てみよう。
\verb|int test01(int a, double b){...}|
という関数に対して、
\verb|test01(c+d, 2.0);|
のように呼び出したときのその文を表すtreeは次の図\ref{fig:CALL_EXPR}
のようになる。
\begin{figure}[htpb]
  \begin{center}
	\includegraphics[width=0.8\textwidth]{figures/CALL_EXPR.eps}
  \end{center}
  \caption{test01(c+d, 2.0); の構文木 CALL\_EXPR}
  \label{fig:CALL_EXPR}
\end{figure}
CALL\_EXPRからarg 0で参照されているADDR\_EXPRは呼び出す関数のアドレスを表す
treeとなっており、そのtypeからさらに関数の型を参照できる。
また、arg 1から参照されるのは関数呼び出しの際のargumentである。
これはFUNCTION\_TYPEで示されるparameterとは違い、実際に関数に渡す値となる。
これをRTLに落とす際にはFUNCTION\_TYPEから得られるparameterの型と、
argumentの型が一致するか?しなければキャストできるか? などの判定が行われる。
また、最初のargumentがD.1536というVAR\_DECLになっている。
これはGimplification passによって生成されたローカル変数で、
c+dの演算結果が格納されている。これについては次節で述べる。

\ref{sec:tailcall}節で解説するTail call eliminationはこのCALL\_EXPRに対して行われる。
\begin{comment}
 <call_expr 0x42da84e0
    type <integer_type 0x42d14300 int sizes-gimplified public SI
        size <integer_cst 0x42d0a740 constant invariant 32>
        unit size <integer_cst 0x42d0a400 constant invariant 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>>
    arg 0 <addr_expr 0x42daf500
        type <pointer_type 0x42dae3c0 type <function_type 0x42da3c00>
            unsigned SI size <integer_cst 0x42d0a740 32> unit size <integer_cst 0x42d0a400 4>
            align 32 symtab 0 alias set -1>
        constant invariant
        arg 0 <function_decl 0x42da5700 test01 type <function_type 0x42da3c00>
            addressable asm_written used nothrow public static decl_5 SI file test04.c line 2 initial <error_mark 0x42d17120> arguments <parm_decl 0x42da3ae0 a> result <result_decl 0x42da3c60 D.1518>
            (mem:SI (symbol_ref:SI ("test01") [flags 0x403] <function_decl 0x42da5700 test01>) [0 S4 A8]) chain <function_decl 0x42da5780 test>>>
    arg 1 <tree_list 0x42daf540
        value <var_decl 0x42dae660 D.1536 type <integer_type 0x42d14300 int>
            used ignored SI file test04.c line 10 size <integer_cst 0x42d0a740 32> unit size <integer_cst 0x42d0a400 4>
            align 32 context <function_decl 0x42da5780 test>
            (reg:SI 120 [ D.1536 ]) chain <var_decl 0x42dae6c0 D.1537>>
        chain <tree_list 0x42daf560
            value <real_cst 0x42daf460 type <real_type 0x42d14b40 double>
                constant invariant 2.00000000000000004163336342344337026588618755341e-2>
            chain <tree_list 0x42daf580
                value <addr_expr 0x42daf4c0 type <pointer_type 0x42d14d20>
                    invariant arg 0 <var_decl 0x42dae180 c>>>>>
    test04.c:10>
\end{comment}


\subsection{GIMPLE}\label{sec:gimple}
GIMPLEとはGCC内部でのみ使われる造語で、
``Generic TreeのSimpleなもの''という意味で、縮めてGIMPLEとなっている。

GCCのgimplificationによってGeneric TreeがGIMPLEに変換されるが、
データ構造としてはGenericもGIMPLEも同じtree共用体を使っており、差はない。
しかしGIMPLEではtreeの様々な要素を制限しており、
次に行われる最適化passを行いやすくしている。

具体的なgimplificationの動作としては、複雑な式を3番地コード(3-address form)
と呼ばれる簡単な形式に変換するものがある。
この3番地コードとはどんな演算でも、\verb|a = c # b|の形の複数の式に変換して、
最適化を行いやすくするものである。
また、if文以外の制御構文(whileやforなど)をすべてifとgotoの形式に変換する
こともGimplificationの仕事である。
3番地コードの例と同じく、関数呼び出しでは全てのargumentは式ではない変数となる。
前節で\verb|c+d|が\verb|D.1563|となっていたのはこのためである。

一例として、関数をgimplificationした後の状態でどのようになるかをリスト
\ref{code:gimplify-before}, \ref{code:gimplify-after}に示す。
\begin{center}
  \begin{minipage}[t]{.45\textwidth}
      \begin{lstlisting}[caption=元の関数test,label=code:gimplify-before]
int test(int a, int b){
    int i,sum=0;
    i = a;
    while ( i <= b ) {
        sum += i;
        i++;
    }
    return sum - a*b;
}
    \end{lstlisting}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{.45\textwidth}
    \begin{lstlisting}[caption=gimplification後の関数test,label=code:gimplify-after]
test (a, b){
    int D.1556;
    int D.1557;
    int i;
    int sum;
    sum = 0;
    i = a;
    goto <D1554>;
    <D1553>:;
    sum = sum + i;
    i = i + 1;
    <D1554>:;
    if (i <= b) {
        goto <D1553>;
    } else {
        goto <D1555>;
    }  <D1555>:;
    D.1557 = a * b;
    D.1556 = sum - D.1557;
    return D.1556;
}
    \end{lstlisting}
  \end{minipage}
\end{center}


\subsection{RTL}\label{sec:rtl}
RTLはRegister Transfer Languageの略称である。
この言語は一般的に言う中間言語のことで、
アーキテクチャに依存せずにアセンブリ言語を表現する汎用的な言語となっている。
例えば、``PLUS''というRTLは足し算(ia32ならadd命令)、
``CALL''というRTLは関数呼びだし命令など、
アセンブラと1対1の関係で記述することができる。
ただし、アセンブラとの大きな違いとして無数のレジスタを持つことが挙げられる。
これによりコード生成直前の最適化を行いやすくしている。
またアセンブリに近いことから、このRTLで表現されたコードを
実際のアーキテクチャのアセンブリに変換することが容易になることも
その特徴の一つだと言える。

GCCではこのRTL表現するためにrtxという構造体を用いている。
このrtxは命令だけでなくレジスタや数値を表すことができ、
それぞれ``mode''と呼ばれるbitサイズを指定することができる。
RTLを生成する際は命令を表すrtxのオペランドに数値やレジスタを表す
rtxを付加することで一つの命令として確保されることになる。


\subsection{最適化機構}
GCCにおいて、最適化はとても重要な要素である。
ソースコードの大半は最適化のために存在し、先に述べたGIMPLEやRTLも
最適化のために最適なデータ構造を成している。
また、新しい最適化を追加する環境も整備されており、
\verb|struct tree_opt_pass|型の\verb|all_passes|という変数に
独自の関数を登録するだけでその関数による最適化が行われる。

最適化は本研究においてはほとんど関係しないが、
``Tail call elimination''に関しては例外である。
この最適化については次節で詳しく説明する。


\section{Tail call elimination}\label{sec:tailcall}
``Tail call elimination''は通常call命令を使用すべき
関数呼び出しで、jump命令に変更するというものである。
この最適化は本研究におけるCbCコンパイラの実装に深く関わってくる。
本節ではこの最適化機構について詳しく説明する。

\subsection{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命令のみになる。

\subsection{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コンパイル機能の実装の際にはこれらの条件をパスさせる必要がある。


\chapter{実装}\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}
以下の節ではそれぞれの行程について詳しく説明する。

\section{\_\_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型にマップされた。


\section{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)|として真偽値が返される。


\section{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の生成とを参考にした。


\section{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|の詳細について説明する。


\section{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}
以下ではこれらの処理に付いてソースコードを交えながら説明する。


\subsection{スタックフレームポインタ}
引数を格納するスタックフレームのベースアドレスは、以下のコードで取得される。
\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|
が使用されている。

\subsection{各引数の格納場所}
次にそれぞれの引数を格納するためのアドレスを表すRTLを生成する。
それぞれの引数がどのoffsetに格納されるかは\verb|expand_call|
の中ですでに決定し、\verb|args|変数に入っている。
これと、先ほど生成した\verb|argblock| rtxを元に計算する関数が
\verb|compute_argument_addresses|関数である。
こちらは gcc/calls.c にある関数をそのまま使用した。

\subsection{引数の計算}
引数の計算を行う。
\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|
にデータを移動する命令をするだけでよい。

\subsection{オーバーラップ}
\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を発行する関数である。
また、ループの初期でこの引数の格納位置、読み込み位置がスタックフレーム内か
どうかを確認し、両方が真の時のみ実行される。

\subsection{引数の格納}
オーバラップの処理が終われば引数の格納である。
この処理のために、引数の計算と同じく\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}

\subsection{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であることを示すフラグとなる。


\chapter{評価}\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するようなこと
を改良すれば大幅な高速化が望めるだろう。}。


\chapter{今後の課題}\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}

\appendix

\chapter{conv1 プログラム}\label{chp:conv1}
以下は第\ref{chp:appraising}章 評価で使用したプログラムconv1である。
\setlength{\columnsep}{3em}
\setlength{\columnseprule}{0pt}
%\setlength{\columnwidth}{}
\begin{multicols}{2}
\begin{lstlisting}[breaklines=true,numbers=left,stepnumber=1,numberstyle=\footnotesize,framesep=5pt,frame=leftline]
#include <stdio.h>
#include <stdlib.h>

static int loop;
#define CC_ONLY 0

/* classical function call case (0) */
int f0(int);
int g0(int);
int h0(int);

f0(int i) {
    int k,j;
    k = 3+i;
    j = g0(i+3);
    return k+4+j;
}

g0(int i) {
    return h0(i+4)+i;
}

h0(int i) {
    return i+4;
}

#if !CC_ONLY

/* straight conversion case (1) */

typedef char *stack;

struct cont_interface { // General Return Continuation
    __code     (*ret)(int, stack);
};

__code     f_g0(int i,int k,stack sp) ;
__code     f_g1(int j,stack sp);

__code     f(int i,stack sp) {
    int k,j;
    k = 3+i;
    goto f_g0(i,k,sp);
}

struct f_g0_interface {  // Specialized Return Continuation
    __code      (*ret)(int, stack);
    int i_,k_,j_;
};

__code     g(int i,stack sp);
__code     f_g1(int j,stack sp) ;

__code     f_g0(int i,int k,stack sp) { // Caller
    struct f_g0_interface *c = 
        (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

    c->ret = f_g1;
    c->k_ = k;
    c->i_ = i;

    goto g(i+3,sp);
}

__code     f_g1(int j,stack sp) {  // Continuation 
    struct f_g0_interface *c = (void*)sp;
    int k = c->k_;
    __code      (*ret)(int, stack);

    sp+=sizeof(struct f_g0_interface);
    c = (struct f_g0_interface *)sp;
    ret = c->ret;
    goto ret(k+4+j,sp);
}

__code     g_h1(int j,stack sp);
__code     h(int i,stack sp);
__code     g_h1(int j,stack sp);

__code     g(int i,stack sp) { // Caller
    struct f_g0_interface *c = 
        (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

    c->ret = g_h1;
    c->i_ = i;

    goto h(i+3,sp);
}

__code     g_h1(int j,stack sp) {  // Continuation 
    struct f_g0_interface *c = (void*)sp;
    __code     (*ret)(int, stack);
    int i = c->i_;

    sp+=sizeof(struct f_g0_interface);
    c = (struct f_g0_interface *)sp;
    ret = c->ret;
    goto ret(j+i,sp);
}

__code     h(int i,stack sp) {
    struct f_g0_interface *c = (void*)sp;
    __code     (*ret)(int, stack);
    ret = c->ret;
    goto ret(i+4,sp);
}

struct main_continuation { // General Return Continuation
    __code     (*ret)(int, stack);
    __code     (*main_ret)();
    void *env;
};

__code     main_return(int i,stack sp) {
    if (loop-->0)
        goto f(233,sp);
    printf("#0103:%d?n",i);
    exit(0);
}

/* little optimzation without stack continuation (2) */

__code g2(int i,int k,int j,char *sp) ;
__code h2_1(int i,int k,int j,char *sp) ;
__code h2(int i,int k,char *sp) ;
__code main_return2(int i,stack sp) ;
__code f2(int i,char *sp) ;


__code f2(int i,char *sp)
{
    int k,j;
    k = 3+i;
    goto g2(i,k,i+3,sp);
}

__code g2(int i,int k,int j,char *sp) {
    j = j+4;
    goto h2(i,k+4+j,sp);
}

__code h2_1(int i,int k,int j,char *sp) {
    goto main_return2(i+j,sp);
}

__code h2(int i,int k,char *sp) {
    goto h2_1(i,k,i+4,sp);
}

__code main_return2(int i,stack sp) {
    if (loop-->0)
        goto f2(233,sp);
    printf("#0132:%d?n",i);
    exit(0);
}

/* little optimizaed case (3) */
__code g2_1(int k,int i,char *sp) ;
__code f2_0_1(int k,int j,char *sp);
__code h2_1_1(int i,int k,int j,char *sp) ;
__code h2_11(int i,int k,char *sp) ;
__code f2_0_1(int k,int j,char *sp) ;

__code f2_1(int i,char *sp) {
    int k,j;
    k = 3+i;
    goto g2_1(k,i+3,sp);
}

__code g2_1(int k,int i,char *sp) {
    goto h2_11(k,i+4,sp);
}

__code h2_1_1(int i,int k,int j,char *sp) {
    goto f2_0_1(k,i+j,sp);
}

__code h2_11(int i,int k,char *sp) {
    goto h2_1_1(i,k,i+4,sp);
}

__code f2_0_1(int k,int j,char *sp) {
    __code     (*ret)(int, stack);
    ret = ( (struct cont_interface *)sp)->ret;
    goto ret(k+4+j,sp);
}

__code     main_return2_1(int i,stack sp) {
    if (loop-->0)
        goto f2_1(233,sp);
    printf("#0165:%d?n",i);
    exit(0);
}

#define STACK_SIZE 2048
stack main_stack[STACK_SIZE];
#define stack_last (&main_stack[STACK_SIZE])

#endif

#define LOOP_COUNT 0x10000000

void go_codesegment(int sw);
main(int ac,char *av[])
{
    int sw;
    if (ac==2) sw = atoi(av[1]);
    else sw=3;

    go_codesegment(sw);
    return 0;
}

void go_codesegment(int sw)
{
#if !CC_ONLY
    struct main_continuation *cont;
    stack sp = (void*)stack_last;
#endif

    int j=0;
    if (sw==0) {
        for(loop=0;loop<LOOP_COUNT;loop++) {
            j += f0(233+loop);
        }
        printf("#0193:%d?n",j);
#if !CC_ONLY
    } else if (sw==1) {
        loop = LOOP_COUNT;
        sp -= sizeof(*cont);
        cont = (struct main_continuation *)sp;
        cont->ret = main_return;
        //cont->main_ret = return;
        //cont->env = environment;
        goto f(233,sp);
    } else if (sw==2) {
        loop = LOOP_COUNT;
        sp -= sizeof(*cont);
        cont = (struct main_continuation *)sp;
        cont->ret = main_return2;
        //cont->main_ret = return;
        //cont->env = environment;
        goto f2(233,sp);
    } else if (sw==3) {
        loop = LOOP_COUNT;
        sp -= sizeof(*cont);
        cont = (struct main_continuation *)sp;
        cont->ret = main_return2_1;
        //cont->main_ret = return;
        //cont->env = environment;
        goto f2_1(233,sp);
#endif
    }
}

/* end */
\end{lstlisting}
\end{multicols}




\end{document}