--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile	Sat Feb 16 17:48:51 2008 +0900
@@ -0,0 +1,29 @@
+TARGET1 = final-thesis
+
+TARGETS = $(TARGET1).pdf
+SOURCES = $(TARGET1).tex
+
+.SUFFIXES: .tex .dvi .pdf
+
+all: $(TARGETS)
+
+.dvi.pdf:
+	dvipdfmx $^
+.tex.dvi:
+	platex $^
+
+two: $(TARGET1).dvi
+	rm -f *.{dvi,pdf}
+	make
+
+clean:
+	#rm -rf .bak
+	#mkdir -p .bak
+	#mv $(SOURCES) $(TARGETS) .bak/
+	rm -f *.{aux,log,nav,out,snm}
+	#mv .bak/* ./
+	#rmdir .bak
+
+distclean: clean
+	rm -f $(TARGETS) *.{dvi}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/final-thesis.tex	Sat Feb 16 17:48:51 2008 +0900
@@ -0,0 +1,1011 @@
+%        File: final.tex
+%     Created: 火  2 05 02:00 PM 2008 J
+% Last Change: 火  2 16 14:13 PM 2008 J
+%
+\documentclass[a4j,10pt]{jreport}
+\usepackage{graphicx}
+\usepackage{verbatim}
+\title{Continuation based CコンパイラのGCC-4.2による実装}
+\author{琉球大学 工学部 情報工学科\\045760E  与儀健人\\指導教官  河野真治}
+\date{\today}
+
+\begin{document}
+\maketitle
+\tableofcontents
+\break
+
+\chapter{序論}\label{chp:joron}
+\section{研究の背景と目的}
+当研究室ではContinuation based C(以下CbC)という言語を使用している。
+このCbCはCと同じ様な構文であるが、よりアセンブリに近い形で実現されている。
+そのため、C言語より細かく、アセンブリよりは高級なプログラミングを可能にする。
+
+これまで当研究室ではCbCのコンパイルに、
+太田昌孝氏のMicro-Cをベースにした独自のコンパイラを使用していた。
+このコンパイラはi386, ppc, mips, spuなどのアーキテクチャに対応おり、
+出力されるCのコードもGCCのものと比較して、速度に大きな差は見られない。
+
+しかし UNIX環境に置けるコンパイラの標準はGCCである事は明らかであり、
+またGCCには最適化という機能が存在し、その機能をonにすればGCCの出力コードの
+性能は(ソースやアーキテクチャにもよるが)格段に上昇する。
+さらに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:hyouka}章]この実装によってどの程度の性能向上ができたかを評価する。
+  \item[第\ref{chp:kadai}章]実装によって明らかになった問題点、また今後の課題を論じる。
+\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とは}
+\section{Micro-CベースのCbCコンパイラ}
+\subsection{現状}
+\subsection{問題点}
+
+
+
+\chapter{GNU Compiler Collection}\label{chp:GCC}
+\section{GCCの基本構造}
+GCCはコンパイラという名称を持っているが
+コンパイル、アセンブル、リンクまで、
+ソースコードを実行可能にするまでの変換を全て受け持っている。
+しかしCbCの拡張にはコンパイル以外は関わらないので、
+ここではCのコンパイル処理を扱うcc1というプログラムについて説明する。
+(以下、GCCはcc1と同じ意味で使用する)
+
+GCCはpassと呼ばれる一連の処理の中でソースコードをアセンブリに変換する。
+以下ではそのpassの中でも重要なものをその実行順に説明する。
+\begin{enumerate}
+  \item parsing. 一般的なコンパイラと同じく、GCCもまずはパーサによって
+	ソースコードを解析し、解析した結果はGeneric Treeと呼ばれる
+	tree構造の構造体に格納される(Generic Treeに関しては\ref{}で説明)。
+	Cのパーサは c\_parse\_* という関数名で統一されている。
+  \item gimplification. この段階ではGeneric Treeをもとにこれを
+	GIMPLEに変換していく(GIMPLEは\ref{}で説明)。
+  \item GIMPLE optimization. 前段階で変換したGIMPLEに対して最適化を行う。
+	この最適化には``Dead store elimination''やif文等の条件判定を最適化する
+	``Lower control flow''などが含まれる。
+  \item RTL generation. ここで、GIMPLEをもとにRTLを生成する(\ref{}で説明)。
+	この段階でほぼ言語依存性がなくなる。
+	GIMPLEを解析してRTLを生成する関数はexpand\_* という名前で統一されている。
+  \item RTL optimization. 前段階で生成されたRTLに対して最適化を行う。
+	この最適化には必要のないコードを除去する``Cleanup control flow graph''や
+	無駄に複数回行われる演算を減らす``Common subexpression elimination''
+	などがある。
+  \item Output assembly. 
+	最後にRTLをもとにターゲットマシンのアセンブリに変換する。
+\end{enumerate}
+これらの処理は図\ref{fig:GCC-pass}のように表される。
+\begin{figure}[htbp]
+  \begin{center}
+	%\psfig{figure=kkkk}
+	%\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で
+行われているので割愛した。
+
+
+\subsection{Generic Tree}\label{Generic}
+この節ではGCCにおいて最も重要なデータ構造であるtreeについて
+簡単に説明する。なお詳しくはFree Software FoundationのGCCのWebページにある
+GCC Internals Manual\cite{gcc1}を参照していただきたい。
+
+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:FUNXTION_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}
+\begin{verbatim}
+ <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{verbatim}
+\end{comment}
+
+
+\subsubsection{CALL\_EXPR}
+次にCALL\_EXPRの詳細を見てみよう。
+\verb|int test01(int a, double b){...}|
+という関数に対して、
+\verb|test01(c+d, 2.0);|
+のように呼び出したときのその文を表すtreeは次の図\ref{}のようになる。
+\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の演算結果が格納されている。これについては次節で述べる。
+
+あとで解説するTail call eliminationはこのCALL\_EXPRに対して行われる。
+\begin{comment}
+  \begin{verbatim}
+ <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{verbatim}
+\end{comment}
+
+
+\subsection{GIMPLE}
+GIMPLEとはGCC内部でのみ使われる造語で、
+``Generic TreeのSimpleなもの''という意味で、縮めてGIMPLEとなっている。
+
+GCCのgimplificationによってGeneric TreeがGIMPLEに変換されるが、
+データ構造としてはGenericもGIMPLEも同じtree共用体を使っており、差はない。
+しかしGIMPLEではtreeの様々な要素を制限しており、
+次の最適化passを行いやすくしている。
+
+具体的なgimplificationの動作としては、複雑な式を3番地コード(3-address form)
+と呼ばれる簡単な形式に変換するものがある。
+これはどんな演算でも、\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{figure}[htpb]
+  \small
+  \begin{center}
+	\begin{minipage}[b]{.45\textwidth}
+	  \begin{verbatim}
+int test(int a, int b){
+    int i,sum=0;
+    i = a;
+    while ( i <= b ) {
+        sum += i;
+        i++;
+    }
+    return sum - a*b;
+}
+	  \end{verbatim}
+	  \caption{元の関数test}\label{code:gimplify-before}
+	\end{minipage}
+	\hfill
+	\begin{minipage}[b]{.45\textwidth}
+	  \begin{verbatim}
+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{verbatim}
+	  \caption{gimplification後の関数test}\label{code:gimplify-after}
+	\end{minipage}
+  \end{center}
+\end{figure}
+
+
+\subsection{RTL}
+\subsection{最適化機構}
+GCCにおいて、最適化はとても重要な要素である。
+ソースコードの大半は最適化のために存在し、先に述べたGIMPLEやRTLも
+最適化のために最適なデータ構造を成している。
+また、新しい最適化を追加する環境も整備されており、
+\verb|struct tree_opt_pass|型の\verb|all_passes|という変数に
+独自の関数を登録するだけでその関数による最適化が行われる。
+
+最適化は本研究においてはほとんど関係しないが、
+``Tail call elimination''に関しては例外である。
+この最適化については次節で詳しく説明する。
+
+
+\section{Tail call}
+``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.8\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{figure}[htpb]
+  \small
+  \begin{center}
+	\begin{minipage}[tb]{.7\textwidth}
+	\begin{verbatim}
+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{verbatim}
+	\end{minipage}
+  \end{center}
+  \caption{関数main, A, Bの例}
+  \label{code:main A B}
+\end{figure}
+これを通常通り、``Tail call elimination''を使用せずにコンパイルすると
+次の図\ref{code:compiled main A}のようなコードが出力される。
+(ただし関数Bは最適化に関係しないのでここでは省いた。)
+\begin{figure}[htpb]
+  \begin{center}
+    \begin{minipage}[b]{.45\textwidth}
+      \begin{verbatim}
+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{verbatim}
+    \end{minipage}
+    \hfill
+    \begin{minipage}[b]{.45\textwidth}
+      \begin{verbatim}
+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{verbatim}
+    \end{minipage}
+  \end{center}
+  \caption{関数main, Aのコンパイル結果(Tail callなし)}
+  \label{code:compiled main A}
+\end{figure}
+
+\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{figure}[htpb]
+  \begin{center}
+    \begin{verbatim}
+A:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    20(%ebp), %eax
+    addl    %eax, 16(%ebp)
+    popl    %ebp
+    jmp     B
+    .size   A, .-A
+    \end{verbatim}
+  \end{center}
+  \caption{Tail call eliminationの行われた関数A}
+  \label{code:tailcalled A}
+\end{figure}
+\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を元に戻す。
+\end{description}
+(a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
+普通の関数では(b)と(c)の間にいくつかの処理があると思われるが、
+ここでは省略した。
+通常は関数呼び出しの際はAのスタックフレームの上に新たに作るはずである。
+しかし、関数AのTail call elimination後のコードを見ても分かる通り、
+無駄な処理が少なくなっている事が分かる。
+これがTail call eliminationにおける最適化の主な効果である。
+
+\subsection{Tail callの条件}
+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を定義してもスタックは一定に保たれる。
+これに関しては\ref{}節で詳しく説明する。
+
+実装の流れとしては次のようになる。
+\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{verbatim}
+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{verbatim}
+ここで``\_\_code''を定義する事で、Tokenizerから
+それを予約語として認識できるようになる。
+
+もう一つ必要なものが、\_\_code型である事を示すidである。
+これはGCCが関数や変数の宣言を表すtreeを生成するまでの間に
+データを保持する \verb|c_declapecs|構造体で使用される。
+void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。
+これは gcc/c-tree.h にて定義されており次のようになる。
+\begin{small}
+\begin{verbatim}
+enum c_typespec_keyword {
+    :
+  cts_int,
+  cts_float,
+  cts_double,
+  cts_CbC_code,
+  cts_dfloat32,
+    :
+}; 
+\end{verbatim}
+\end{small}
+以上により、\_\_codeをパースする準備ができた。
+実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
+\verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
+\verb|declspecs_add_type()|関数に統一されている。
+この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。
+以下のようになる。
+\begin{verbatim}
+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{verbatim}
+これは実際には\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{verbatim}
+  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{verbatim}
+これで\_\_codeによる型がvoid型にマップされた。
+
+
+\section{code segment の tree 表現}
+次に、関数と同じようにパースされるcode segmentのtreeを
+後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。
+この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。
+具体的には以下の様な関数になる。
+\begin{verbatim}
+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{verbatim}
+\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|を使用すべき関数、
+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{verbatim}
+  if ( declspecs->typespec_word &=&  cts_CbC_code )
+    {
+      type = build_code_segment_type (type, arg_types);
+    }
+  else
+    {
+      type = build_function_type (type, arg_types);
+    }
+\end{verbatim}
+これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。
+code segmentかをチェックする時はtree typeに対して
+\verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。
+
+
+\section{goto のパース}
+つづいてgoto文のパースが必要になる。
+goto文は通常のCの構文にも存在するが、
+
+
+
+
+\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{verbatim}
+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{verbatim}
+この処理で一つ一つの引数に付いて、与えられた式を計算し、レジスタか
+もしくはスタックに格納しておく。
+\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{}節でも説明したように、2つ以上の引数のもとのアドレスと
+格納先アドレスが相互に重なる場合、一時的な変数に格納する必要がある。
+\verb|expand_cbc_goto|ではこの処理を\verb|push_overlaps|関数に任せている。
+それほど大きな関数ではないので以下にコードを示す。
+\begin{small}
+\begin{verbatim}
+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{verbatim}
+\end{small}
+重要なのは\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{verbatim}
+  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{verbatim}
+
+\subsection{CALL\_INSN}
+最後にCALL\_INSNを発行する処理が来る。
+\begin{verbatim}
+  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{verbatim}
+この\verb|rtx_for_function_call|関数により、funexp変数にcallee関数の
+アドレスを示したrtxが格納され、
+それを引数に\verb|emit_call_1|関数を呼び出している。
+ここで、変数\verb|flags|は
+\verb|flags & ECF_SIBCALL != 0|を満たしている必要がある。
+これがこのCALL\_INSNがtail callであることを示すフラグとなる。
+
+
+\section{parallel assignment}
+
+\begin{comment}
+memo....
+\begin{itemize}
+  \item RID\_CbC\_CODE, cts\_CbC\_codeの追加
+  \item \_\_code のパース
+  \item ただし、実際にtreeを生成する段階でvoid型にマッピングする
+  \item treeがcode segmentであることを示すフラグ
+
+
+  \item goto cs();のパース
+  \item この関数呼び出しがCbCの継続である事を示すフラグ
+  \item 該当関数がcbcgotoのステートメントを持っている事を示すフラグ
+  \item CALL\_EXPR\_TAILCALL()
+
+  \item expand\_call()の説明
+  \item expand\_cbc\_goto()の説明
+
+  \item parallel assignment
+
+
+  \item 関数からのgoto
+\end{itemize}
+\end{comment}
+
+
+\chapter{評価}
+今回実装できたGCCによるCbCコンパイラを評価してみる。
+評価の手法としてはあるCbCプログラムをMicro-CとGCCでコンパイルして、
+その出力されたコードの実行速度を測れば良いだろう。
+
+今回測定に使用したプログラムはこれまでもMicro-Cの測定に使われていた
+テストルーチンで、普通のCのソースをCbCに機械的に変換したものである。
+引数に1を入れるとその変換されたCbCのコード、
+引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
+また、評価はia32アーキテクチャのFedora上で行った。
+実行結果は表\ref{tab:mc,gcc,compare}に示される。
+\begin{table}[htpb]
+  \centering
+  \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 (+fastcall) & 3.44 & 1.76 & 2.34 \\ \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,
+最後に元にフレームポインタにpopという動作をなるべくなくすようになる。
+ここでは引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、
+やはり少し速度は勝てない。
+これは様々な理由が考えられるが、最大の理由は
+Micro-Cではfastcallが使われている事だと思われる。
+Micro-Cのコードでは関数呼び出しの際、スタックに全ての引数をつめるのではなく、
+できる限り開いているレジスタを使うようになっている。これがfastcallである。
+
+GCCはfastcallをサポートしているので、これも試してみた。
+fastcallを有効にするには関数定義の際に
+\verb|int __attribute__ ((fastcall)) test(){|
+として、型と関数名の間に挿入する。
+ここでは上記の-fomit-frame-pointerも有効にした。
+その測定結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。 
+ここまで最適化を行って、Micro-Cの速度を超える事ができた。
+
+
+\chapter{今後の課題}
+
+\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}
+
+
+\begin{thebibliography}{9}
+  \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''.
+	日本ソフトウェア科学会第19回大会論文集, Sep, 2002.
+  \bibitem{kono2} 河野真治. ``継続を持つCの下位言語によるシステム記述''.
+	日本ソフトウェア科学会第17回大会論文集, Sep, 2000.
+  \bibitem{gcc1} GNU Project - Free Software Foundation, GCC internal manual.
+	``http://gcc.gnu.org/onlinedocs/gccint/''.
+\end{thebibliography}
+
+\end{document}
+
+