Mercurial > hg > Papers > 2008 > kent-graduation

changeset 2:2ec81b844da2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
*** empty log message ***
author kent
date Mon, 18 Feb 2008 11:53:00 +0900
parents b74e68c4e7da
children a4f00b195d35
files Makefile final-thesis.tex
diffstat 2 files changed, 51 insertions(+), 30 deletions(-) [+]
line wrap: on
line diff
--- a/Makefile	Sat Feb 16 17:48:51 2008 +0900
+++ b/Makefile	Mon Feb 18 11:53:00 2008 +0900
@@ -12,17 +12,13 @@
 .tex.dvi:
 	platex $^
 
-two: $(TARGET1).dvi
-	rm -f *.{dvi,pdf}
-	make
+
+twice: distclean $(TARGET1).dvi 
+	rm -f $(TARGET1).dvi
+	make all
 
 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}
--- a/final-thesis.tex	Sat Feb 16 17:48:51 2008 +0900
+++ b/final-thesis.tex	Mon Feb 18 11:53:00 2008 +0900
@@ -43,8 +43,8 @@
   \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}章]実装によって明らかになった問題点、また今後の課題を論じる。
+  \item[第\ref{chp:appraising}章]この実装によってどの程度の性能向上ができたかを評価する。
+  \item[第\ref{chp:problem}章]実装によって明らかになった問題点、また今後の課題を論じる。
 \end{description}
 また、本研究ではGCCのversion-4.2.2
 \footnote{実装を始めた当初は4.2.1. 2008/02/01には4.2.3がリリースされている。}
@@ -63,7 +63,7 @@
 
 
 
-\chapter{GNU Compiler Collection}\label{chp:GCC}
+\chapter{The GNU Compiler Collection}\label{chp:GCC}
 \section{GCCの基本構造}
 GCCはコンパイラという名称を持っているが
 コンパイル、アセンブル、リンクまで、
@@ -98,7 +98,7 @@
 \begin{figure}[htbp]
   \begin{center}
 	%\psfig{figure=kkkk}
-	%\includegraphics[width=0.8\textwidth]{figures/GCC-pass.eps}
+	\includegraphics[width=0.8\textwidth]{figures/GCC-pass.eps}
   \end{center}
   \caption{GCCのpass}
   \label{fig:GCC-pass}
@@ -141,7 +141,7 @@
 図の角丸の長方形はtree、矢印はtreeへのポインタを表している。
 \begin{figure}[htpb]
   \begin{center}
-	%\includegraphics[width=0.8\textwidth]{figures/FUNCTION_TYPE.eps}
+	\includegraphics[width=0.8\textwidth]{figures/FUNCTION_TYPE.eps}
   \end{center}
   \caption{int test(int *, double)関数の型 FUNCTION\_TYPE}
   \label{fig:FUNCTION_TYPE}
@@ -164,7 +164,6 @@
 これは引数の最後を明示的に指定しており、
 これがない場合は、GCCでは可変長引数を持つ関数として扱う事になっている。
 \begin{comment}
-\begin{verbatim}
  <function_type 0x12bda20
     type <void_type 0x42d14960 void VOID
         align 8 symtab 0 alias set 2
@@ -181,19 +180,18 @@
             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{}のようになる。
+のように呼び出したときのその文を表すtreeは次の図\ref{fig:CALL_EXPR}
+のようになる。
 \begin{figure}[htpb]
   \begin{center}
-	%\includegraphics[width=0.8\textwidth]{figures/CALL_EXPR.eps}
+	\includegraphics[width=0.8\textwidth]{figures/CALL_EXPR.eps}
   \end{center}
   \caption{test01(c+d, 2.0); の構文木 CALL\_EXPR}
   \label{fig:CALL_EXPR}
@@ -210,7 +208,6 @@
 
 あとで解説する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>
@@ -237,7 +234,6 @@
                 value <addr_expr 0x42daf4c0 type <pointer_type 0x42d14d20>
                     invariant arg 0 <var_decl 0x42dae180 c>>>>>
     test04.c:10>
-  \end{verbatim}
 \end{comment}
 
 
@@ -310,6 +306,25 @@
 
 
 \subsection{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も
@@ -339,7 +354,7 @@
 この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。
 \begin{figure}[htpb]
   \begin{center}
-	%\includegraphics[width=0.8\textwidth]{figures/GCC-TailCall.eps}
+	\includegraphics[width=0.6\textwidth]{figures/GCC-TailCall.eps}
   \end{center}
   \caption{Tail call eliminationの例}
   \label{fig:Tail call}
@@ -455,7 +470,7 @@
 \end{figure}
 \begin{figure}[htpb]
   \begin{center}
-    %\includegraphics[width=.8\textwidth]{figures/stack-normal.eps}
+    \includegraphics[width=.8\textwidth]{figures/stack-normal.eps}
   \end{center}
   \caption{関数AからBをcallする時のスタックの様子}
   \label{fig:stack-normal}
@@ -470,7 +485,7 @@
 図\ref{fig:stack-normal2}はBから戻ってきた後のスタックの様子である。
 \begin{figure}[htpb]
   \begin{center}
-    %\includegraphics[width=.7\textwidth]{figures/stack-normal2.eps}
+    \includegraphics[width=.7\textwidth]{figures/stack-normal2.eps}
   \end{center}
   \caption{Bからreturnしたあとmainにもどる時のスタックの様子}
   \label{fig:stack-normal2}
@@ -511,7 +526,7 @@
 このときのスタックの様子を図\ref{fig:stack-tailcall}に表した。
 \begin{figure}[htpb]
   \begin{center}
-    %\includegraphics[width=.8\textwidth]{figures/stack-tailcall.eps}
+    \includegraphics[width=.8\textwidth]{figures/stack-tailcall.eps}
   \end{center}
   \caption{関数AからBを呼び出す時のスタックの様子(Tail call)}
   \label{fig:stack-tailcall}
@@ -522,7 +537,7 @@
     ebpはmainの引数をさしたまま
   \item[(b)] ebpをespに合わせる。通常はebpのオフセットから引数のアドレスを指定する。
   \item[(c)] A自身のスタックフレームにB用の引数をつめる。
-  \item[(d)] ebpを元に戻す。
+  \item[(d)] ebpを元に戻す。その後関数Bにjump。
 \end{description}
 (a),(b)は関数Aの初期化処理、 (c),(d)は関数Bの呼び出し処理である。
 普通の関数では(b)と(c)の間にいくつかの処理があると思われるが、
@@ -531,6 +546,9 @@
 しかし、関数AのTail call elimination後のコードを見ても分かる通り、
 無駄な処理が少なくなっている事が分かる。
 これがTail call eliminationにおける最適化の主な効果である。
+最大の効果が得られるのは、caller関数が持っている引数を
+callee関数に直接渡す場合である。
+この時はスタック操作は全く必要なく、単にjump命令のみになる。
 
 \subsection{Tail callの条件}
 Tail callが可能かどうかの条件についてここで考察する。
@@ -565,7 +583,7 @@
 よって、``書き込んだ引数が、その後書き込む引数を上書きしてはならない''
 という条件も必要となる。
 
-他にも細かな条件はあるが、重要になるのは以下の4つとなる。
+他にも細かな条件はあるが、以上の考察より以下の4つの条件が明らかになった。
 \begin{itemize}
   \item 関数コールがreturnの直前にある
   \item 関数の返す型がcallerとcalleeで一致している
@@ -934,7 +952,7 @@
 \end{comment}
 
 
-\chapter{評価}
+\chapter{評価}\label{appraising}
 今回実装できたGCCによるCbCコンパイラを評価してみる。
 評価の手法としてはあるCbCプログラムをMicro-CとGCCでコンパイルして、
 その出力されたコードの実行速度を測れば良いだろう。
@@ -966,8 +984,9 @@
 次の``GCC (+omit)''では最適化フラグ
 -fomit-frame-pointerを付加してコンパイルした。
 このフラグをたてた場合、関数の最初にフレームポインタをpush,
-最後に元にフレームポインタにpopという動作をなるべくなくすようになる。
-ここでは引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、
+このフラグをたてた場合、フレームポインタのpushやpopがなるべく
+少なくなるようにコンパイルされる。
+この場合では引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、
 やはり少し速度は勝てない。
 これは様々な理由が考えられるが、最大の理由は
 Micro-Cではfastcallが使われている事だと思われる。
@@ -982,8 +1001,14 @@
 その測定結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。 
 ここまで最適化を行って、Micro-Cの速度を超える事ができた。
 
+この評価から本研究における目的の一つ、``CbCコードの高速化''を
+達成できた事が分かった。
+しかし、fastcallというオプションをわざわざつけるというのは無駄が多いだろう。
+GCCと互換性のあるCbCの処理系は他にないので、
+code segmentの場合はfastcallを強制させる事も今後の課題として考えられる。
 
-\chapter{今後の課題}
+
+\chapter{今後の課題}\label{problem}
 
 \begin{itemize}
   \item environment