Binary file main.pdf has changed

--- a/main.tex	Tue Mar 25 03:44:16 2008 +0900
+++ b/main.tex	Tue Mar 25 11:48:42 2008 +0900
@@ -57,6 +57,7 @@
 
 
 
+\renewcommand{\thepage}{--- \arabic{page} ---}
 \begin{document}
 \twocolumn[\maketitle]{}
 
@@ -134,7 +135,7 @@
 inline関数の処理や、関数間での最適化を行う場合には
 一つのソースファイル毎に行われる。
 
-\subsection{Tail call elimination}
+\subsection{Tail call elimination}\ref{sec:tailcall}
 最適化のひとつである``Tail call elimination''は、
 本研究におけるCbCコンパイラの実装に深く関わってくる。
 本節ではこの最適化機構について詳しく説明する。
@@ -297,38 +298,16 @@
 
 \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から
+Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されており、
+ここに``\_\_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}
+これは gcc/c-tree.h にて定義されており、ここに\verb|cts_CbC_code|を追加する。
+
 以上により、\_\_codeをパースする準備ができた。
 実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、
 \verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは
@@ -465,100 +444,66 @@
   \item スタックフレームのベースアドレスRTLを取得
   \item 各引数の格納されるアドレスRTLを取得
   \item 各引数の式を計算 (一時的にレジスタに格納)
-  \item オーバーラップする引数を一時に変数に格納
+  \item オーバーラップする引数を一時に変数に格納\label{overlap}
   \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に値する。
-
-\paragraph{各引数の格納場所}
-次にそれぞれの引数を格納するためのアドレスを表すRTLを生成する。
-これと、先ほど生成した\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] ..);
-\end{lstlisting}
-この処理で一つ一つの引数に付いて、与えられた式を計算し、レジスタか
-もしくはスタックに格納しておく。
-\verb|preexpand_argument_expr|関数はgcc/calls.c
-にある\verb|store_one_arg|を元に作った関数で、
-一つだけ引数の情報を受け取り、計算して\verb|args[i].value|
-に計算の結果の格納されているrtxをおく。
-よって、あとは\verb|args[i].value|から\verb|args[i].stack|
-にデータを移動する命令を出力するだけでよい。
-
-\paragraph{オーバーラップ}
-2つ以上の引数のもとのアドレスと格納先アドレスが相互に重なる場合、
-一時的な変数に格納する必要がある。
-\verb|expand_cbc_goto|ではこの処理を\verb|push_overlaps|関数に任せている。
+これらの処理はほぼ\verb|expand_call|の内容をそのまま利用できる。
+ただし、\ref{overlap}のオーバーラップする引数がある場合のみ問題になる。
+gotoの実装には\ref{sec:tailcall}節で説明したTail callを用いているため
+引数の書き込み領域と読み込み領域が重なる場合がある。
+本来この場合はTail call不能として通常の関数呼出が用いられるところであるが、
+CbCではこれを強制しなければならない。
+そのため、このように重なる場合は変数の内容を一時退避する必要がある。
+次のリスト\ref{code:push_overlaps}がこの処理を書く引数に対して行っている。
 \begin{lstlisting}[caption=push\_overlaps関数,label=code:push_overlaps]
-if(args[i].mode==BLKmode)
-  emit_block_move(temp, args[i].value..)
-else
-  emit_move_insn(temp, args[i].value);
+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 (/*args[i].stackはスタック外*/) continue;
+    if (/*args[i].valueはスタック外*/) continue;
+    temp =assign_temp(args[i].tree_value..);
+    if ( args[i].mode==BLKmode )
+      emit_block_move(temp,args[i].value..);
+    else
+      emit_move_insn(temp,args[i].value);
+    args[i].value = temp;
+  }
 \end{lstlisting}
-この関数は引数の読み込み元と書き込み先が重なる場合に、
-一部の引数を別の場所に退避する役割を持つ。
-この処理がリスト\ref{code:push_overlaps}である。
-\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 ..);
-\end{lstlisting}
-
-\paragraph{CALL\_INSN}
-最後にCALL\_INSNを発行する処理が来る。
-\begin{lstlisting}[caption=CALL\_INSNの発行,label=emit CALL_INSN]
-funexp=rtx_for_function_call(fndecl..);
-   :
-emit_call_1(funexp,exp,fndecl,fun ..);
-\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に機械的に変換したものである。
+テストルーチンで、普通のCのソースをプログラムでCbCに変換したものである。
 引数に1を入れるとそれが変換されたCbCのコード、
 引数2,3では変換されたコードを手動でMicro-C用に最適化したコードが実行される。
 また、評価はia32アーキテクチャのFedora上で行った。
+一番結果の良い引数2の場合のcode segmentをリスト\ref{code:bench}に示す。
+\begin{lstlisting}[caption=bench,label=code:bench]
+__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);
+}
+\end{lstlisting}
+このベンチマークではCbCの継続と計算を交互に行っている。
 測定結果は表\ref{tab:mc,gcc,compare}に示される。
 \begin{table}[htpb]
   \centering
@@ -569,28 +514,93 @@
     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に特化したコードでは速度が負けている。
+通常のTail call eliminationのみを有効にした場合の結果が2行目、
+その他は次節で説明するオプションを付加したものである。
+見てのとおり、手動で最適化された引数2,3の場合はオプションを加えなければ
+Micro-Cの速度に及ばなかった。次節ではこの点について考察する。
+
+\subsection{出力コード}
+先ほどのリスト\ref{code:bench}のcode segment g2のみをMicro-Cでコンパイルした結果
+をリスト\ref{code:bench_mc}, 
+GCCのオプション無しによるコンパイル結果をリスト\ref{code:bench_gcc}に示す。
+\begin{lstlisting}[caption=Micro-Cによる出力コード,label=code:bench_mc]
+f2:
+    lea -_44(%ebp),%esp
+    movl $3,%eax
+    addl %esi,%eax
+    movl %eax,-28(%ebp)
+    movl %edi,-32(%ebp)
+    movl -28(%ebp),%edi
+    movl %esi,%eax
+    addl $3,%eax
+    movl %eax,-28(%ebp)
+    jmp g2
+\end{lstlisting}
+\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc]
+f2:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    8(%ebp), %eax
+    movl    12(%ebp), %ecx
+    leal    3(%eax), %edx
+    movl    %edx, 12(%ebp)
+    movl    %edx, 16(%ebp)
+    movl    %ecx, 20(%ebp)
+    popl    %ebp
+    jmp     g2
+\end{lstlisting}
+このとおり出力コードは10命令と、行数にはあまり差が無い。(他のsegmentも同様である)
+しかしGCCの出力においては無駄なコードが混じっていることがわかるだろう。
+\verb|pushl%ebp|と\verb|popl %ebp|である。
+すべてのcode segmentにおいてこれと同じ命令が出てしまっているが、
+これはTailcallを無理矢理適用したために出てきたコードである。
 
-次の``GCC (+omit)''では最適化フラグ
--fomit-frame-pointerを付加してコンパイルしたものである。
-また、``GCC (+fast)''はそれに加えてfastcallを用いたものである。
-その結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。 
-ここまで最適化を行って、Micro-Cの速度を超えることができた。
+このような関数の最初と最後にある無駄なフレームポインタのpushを抑制するオプションが
+-fomit-frame-pointerである。このオプションを付加するとリスト\ref{bench_gcc_omit}
+\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_omit]
+f2:
+    movl    4(%esp), %eax
+    movl    8(%esp), %ecx
+    leal    3(%eax), %edx
+    movl    %edx, 8(%esp)
+    movl    %edx, 12(%esp)
+    movl    %ecx, 16(%esp)
+    jmp     g2
+\end{lstlisting}
+これによって一気に3命令減った。ベンチマークは表\ref{tab:mc,gcc,compare}の3行目、``GCC (+omit)''である。
+しかし、(code segmentにもよるが)3/10命令減ったにもかかわらずMicro-Cとの速度差が
+ほとんど無いことがわかる。
 
-この評価から本研究における目的の一つ、``CbCコードの高速化''を
-達成できたことが分かった。
-しかし、fastcallというオプションをわざわざつけるというのは無駄が多いだろう。
-GCCと互換性のあるCbCの処理系は他にないので、
-code segmentの場合はfastcallを強制させることも今後の課題として考えられる。
+これはリスト\ref{code:bench_mc}をもう一度見てもらえるとわかるが、
+Micro-Cでは引数の格納にレジスタ\%ediと\%esiを用いていることが最大の理由だろう。
+もちろんGCCでは通常関数の引数はスタック、つまりメモリ上に格納される。
+この違いが命令数の差を埋めていると思われる。
+GCCでも引数をレジスタに詰めることができるfastcall属性がある。
+-fomit-frame-pointerに加えてfastcallを付加した結果をリスト\ref{bench_gcc_fast}
+に示す。
+\begin{lstlisting}[caption=GCCによる出力コード,label=code:bench_gcc_fast]
+f2:
+    movl    %edx, %eax
+    leal    3(%ecx), %edx
+    movl    %edx, 4(%esp)
+    movl    %eax, 8(%esp)
+    jmp     g2
+\end{lstlisting}
+命令数はさらに2命令減り、またメモリへのアクセスが減ったため
+ベンチマーク結果(表\ref{tab:mc,gcc,compare}GCC (+fast))も大幅に改善した。
+
+この評価結果から、GCCの最適化オプションを用いることで
+CbCコードのさらなる高速化が可能であることが示された。
+また、使用したベンチマークプログラムはCのコードをプログラムで
+CbCに変換したものだが、これをCのままコンパイルすると、
+最適化をかけても約3.3秒かかる。
+このようにC言語のみでは不可能な手動による最適化がCbCの利点としてあげられる。
+
 
 \section{今後の課題と考察}
 本研究の実装により、GCCを使ってCbCのソースコードを
@@ -637,6 +647,6 @@
 	``http://gcc.gnu.org/onlinedocs/gccint/''.
 \end{thebibliography}
 
-
+\renewcommand{\thepage}{--- \arabic{page} ---E}
 \end{document}