Mercurial > hg > Papers > 2008 > kent-graduation
changeset 3:a4f00b195d35
all sections was writen.
| author | kent |
|---|---|
| date | Wed, 20 Feb 2008 19:23:05 +0900 |
| parents | 2ec81b844da2 |
| children | 74884c038ce7 |
| files | final-thesis.tex |
| diffstat | 1 files changed, 341 insertions(+), 143 deletions(-) [+] |
line wrap: on
line diff
--- a/final-thesis.tex Mon Feb 18 11:53:00 2008 +0900 +++ b/final-thesis.tex Wed Feb 20 19:23:05 2008 +0900 @@ -2,17 +2,46 @@ % Created: 火 2 05 02:00 PM 2008 J % Last Change: 火 2 16 14:13 PM 2008 J % -\documentclass[a4j,10pt]{jreport} +\documentclass[a4j]{jreport} +\usepackage{graduate_paper} \usepackage{graphicx} \usepackage{verbatim} -\title{Continuation based CコンパイラのGCC-4.2による実装} -\author{琉球大学 工学部 情報工学科\\045760E 与儀健人\\指導教官 河野真治} -\date{\today} +\usepackage{nonDefaultPackage/listings} + +\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{ソースコード目次} + + +\jtitle{Continuation based CコンパイラのGCC-4.2による実装} +\etitle{The implementation of Continuation based C Compiler on GCC} +\year{平成19年度} +%\affiliation{琉球大学大学院理工学研究科\\ 情報工学専攻} +\author{045760E 与儀 健人\\ 指導教官 河野 真治} +% +%\title{Continuation based CコンパイラのGCC-4.2による実装} +%\author{琉球大学 工学部 情報工学科\\045760E 与儀健人 \and 指導教官 河野真治} +%\date{\today} \begin{document} \maketitle \tableofcontents \break +\listoffigures +\lstlistoflistings +%\listoftables \chapter{序論}\label{chp:joron} \section{研究の背景と目的} @@ -44,7 +73,7 @@ \item[第\ref{chp:GCC}章]CbCコンパイル機能の実装に関わるGCCの内部構造を述べる。 \item[第\ref{chp:impl}章]本論文の主旨であるCbCコンパイル機能のGCCへの実装について説明する。 \item[第\ref{chp:appraising}章]この実装によってどの程度の性能向上ができたかを評価する。 - \item[第\ref{chp:problem}章]実装によって明らかになった問題点、また今後の課題を論じる。 + \item[第\ref{chp:problems}章]実装によって明らかになった問題点、また今後の課題を論じる。 \end{description} また、本研究ではGCCのversion-4.2.2 \footnote{実装を始めた当初は4.2.1. 2008/02/01には4.2.3がリリースされている。} @@ -57,10 +86,122 @@ \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_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_process(int total, int count){ + printf("while_process: do something.\n"); + total += count; + count++; + goto while_cond(total, count); +} + +__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}はこのコードをオートマトンのように表したものだ。 + +\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} @@ -77,14 +218,15 @@ \begin{enumerate} \item parsing. 一般的なコンパイラと同じく、GCCもまずはパーサによって ソースコードを解析し、解析した結果はGeneric Treeと呼ばれる - tree構造の構造体に格納される(Generic Treeに関しては\ref{}で説明)。 + tree構造の構造体に格納される + (Generic Treeに関しては\ref{sec:generic}で説明)。 Cのパーサは c\_parse\_* という関数名で統一されている。 \item gimplification. この段階ではGeneric Treeをもとにこれを - GIMPLEに変換していく(GIMPLEは\ref{}で説明)。 + GIMPLEに変換していく(GIMPLEは\ref{sec:gimple}で説明)。 \item GIMPLE optimization. 前段階で変換したGIMPLEに対して最適化を行う。 この最適化には``Dead store elimination''やif文等の条件判定を最適化する ``Lower control flow''などが含まれる。 - \item RTL generation. ここで、GIMPLEをもとにRTLを生成する(\ref{}で説明)。 + \item RTL generation. ここで、GIMPLEをもとにRTLを生成する(\ref{sec:rtl}で説明)。 この段階でほぼ言語依存性がなくなる。 GIMPLEを解析してRTLを生成する関数はexpand\_* という名前で統一されている。 \item RTL optimization. 前段階で生成されたRTLに対して最適化を行う。 @@ -97,8 +239,7 @@ これらの処理は図\ref{fig:GCC-pass}のように表される。 \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} @@ -111,7 +252,7 @@ 行われているので割愛した。 -\subsection{Generic Tree}\label{Generic} +\subsection{Generic Tree}\label{sec:generic} この節ではGCCにおいて最も重要なデータ構造であるtreeについて 簡単に説明する。なお詳しくはFree Software FoundationのGCCのWebページにある GCC Internals Manual\cite{gcc1}を参照していただきたい。 @@ -136,12 +277,12 @@ 関数の型を表現する為に必要な情報としては関数の返す型、 関数に渡す引数列(parameter)の型の二つが必要だろう。 FUNCTION\_TYPEもこの二つを主な要素に持つ。 -図\ref{fig:FUNXTION_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} + %\includegraphics[width=0.8\textwidth]{figures/FUNCTION_TYPE.eps} \end{center} \caption{int test(int *, double)関数の型 FUNCTION\_TYPE} \label{fig:FUNCTION_TYPE} @@ -191,7 +332,7 @@ のようになる。 \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} @@ -237,7 +378,7 @@ \end{comment} -\subsection{GIMPLE} +\subsection{GIMPLE}\label{sec:gimple} GIMPLEとはGCC内部でのみ使われる造語で、 ``Generic TreeのSimpleなもの''という意味で、縮めてGIMPLEとなっている。 @@ -255,13 +396,11 @@ 3番地コードの例と同じく、関数呼び出しでは全てのargumentは式ではない変数となる。 前節で\verb|c+d|が\verb|D.1563|となっていたのはこのためである。 -一例として、関数をgimplificationした後の状態でどのようになるかを図 +一例として、関数をgimplificationした後の状態でどのようになるかをソースコード \ref{code:gimplify-before}, \ref{code:gimplify-after}に示す。 -\begin{figure}[htpb] - \small - \begin{center} - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} +\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; @@ -271,12 +410,11 @@ } return sum - a*b; } - \end{verbatim} - \caption{元の関数test}\label{code:gimplify-before} - \end{minipage} - \hfill - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} + \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; @@ -298,14 +436,12 @@ D.1556 = sum - D.1557; return D.1556; } - \end{verbatim} - \caption{gimplification後の関数test}\label{code:gimplify-after} - \end{minipage} - \end{center} -\end{figure} + \end{lstlisting} + \end{minipage} +\end{center} -\subsection{RTL} +\subsection{RTL}\label{sec:rtl} RTLはRegister Transfer Languageの略称である。 この言語は一般的に言う中間言語のことで、 アーキテクチャに依存せずにアセンブリ言語を表現する汎用的な言語となっている。 @@ -354,7 +490,7 @@ この様子を図\ref{fig:Tail call}に示したので参考にしていただきたい。 \begin{figure}[htpb] \begin{center} - \includegraphics[width=0.6\textwidth]{figures/GCC-TailCall.eps} + %\includegraphics[width=0.6\textwidth]{figures/GCC-TailCall.eps} \end{center} \caption{Tail call eliminationの例} \label{fig:Tail call} @@ -368,11 +504,9 @@ 図\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} +\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 ; @@ -386,19 +520,15 @@ A(10, 20, 30, 40); return 0; } - \end{verbatim} - \end{minipage} - \end{center} - \caption{関数main, A, Bの例} - \label{code:main A B} -\end{figure} + \end{lstlisting} + \end{minipage} +\end{center} これを通常通り、``Tail call elimination''を使用せずにコンパイルすると -次の図\ref{code:compiled main A}のようなコードが出力される。 +次のソースコード\ref{code:compiled A},\ref{code:compiled main}のようなコードが出力される。 (ただし関数Bは最適化に関係しないのでここでは省いた。) -\begin{figure}[htpb] - \begin{center} - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} +\begin{center} + \begin{minipage}[t]{.45\textwidth} + \begin{lstlisting}[language=,caption=関数Aのコンパイル結果(Tail callなし),label=code:compiled A] A: pushl %ebp movl %esp, %ebp @@ -414,11 +544,11 @@ leave ret .size A, .-A - \end{verbatim} + \end{lstlisting} \end{minipage} \hfill - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} + \begin{minipage}[t]{.45\textwidth} + \begin{lstlisting}[caption=関数mainのコンパイル結果,label=code:compiled main] main: leal 4(%esp), %ecx andl $-16, %esp @@ -439,12 +569,9 @@ 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} + \end{lstlisting} + \end{minipage} +\end{center} \begin{comment} このとき、関数Aが呼ばれて、関数Bを呼ぶまでのスタックの様子を表したものが @@ -454,7 +581,7 @@ \begin{figure}[htpb] \begin{minipage}[tb]{.45\textwidth} \begin{flushright} - \includegraphics[width=1.5\textwidth]{figures/stack-normal.eps} + %\includegraphics[width=1.5\textwidth]{figures/stack-normal.eps} \end{flushright} \caption{関数AからBをcallする時のスタックの様子} \label{fig:stack-normal} @@ -462,7 +589,7 @@ \hfill \begin{minipage}[tb]{.45\textwidth} \begin{flushleft} - \includegraphics[width=1.3\textwidth]{figures/stack-normal2.eps} + %\includegraphics[width=1.3\textwidth]{figures/stack-normal2.eps} \end{flushleft} \caption{Bからreturnしたあとmainにもどる時のスタックの様子} \label{fig:stack-normal} @@ -470,7 +597,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} @@ -485,7 +612,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} @@ -503,9 +630,8 @@ 次にTail call eliminationが行われた場合の コンパイル結果を図\ref{code:tailcalled A}に示す。 -\begin{figure}[htpb] - \begin{center} - \begin{verbatim} +\begin{center} + \begin{lstlisting}[caption=Tail call eliminationの行われた関数A, label=code:tailcalled A] A: pushl %ebp movl %esp, %ebp @@ -514,11 +640,8 @@ popl %ebp jmp B .size A, .-A - \end{verbatim} - \end{center} - \caption{Tail call eliminationの行われた関数A} - \label{code:tailcalled A} -\end{figure} + \end{lstlisting} +\end{center} \verb|20(%ebp)|は変数d、\verb|16(%ebp)|は変数cを表している。 ここではBのためにスタック領域は確保せず、かわりにAのスタック領域に Bのための引数を書き込んでいる事が分かる。 @@ -526,7 +649,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} @@ -550,7 +673,7 @@ callee関数に直接渡す場合である。 この時はスタック操作は全く必要なく、単にjump命令のみになる。 -\subsection{Tail callの条件} +\subsection{Tail callの条件}\label{sec:condition_of_tailcall} Tail callが可能かどうかの条件についてここで考察する。 必要に応じて前節の図\ref{fig:stack-tailcall}と、図\ref{code:main A B} を説明に用いるので参考にしていただきたい。 @@ -606,7 +729,6 @@ これを解決するために、この実装ではcode segmentの 引数サイズを一定にする事にした。 どのようなcode segmentを定義してもスタックは一定に保たれる。 -これに関しては\ref{}節で詳しく説明する。 実装の流れとしては次のようになる。 \begin{enumerate} @@ -622,7 +744,7 @@ まず最初に必要となるのが``\_\_code''という予約語を定義する事である。 Cの予約語は全て gcc/c-parser.c にて\verb|reswords|配列に定義されている。 次のように修正した。 -\begin{verbatim} +\begin{lstlisting}[caption=reswords定義,label=code:reswords] static const struct resword reswords[] = { : @@ -632,7 +754,7 @@ /* CbC project */ { "__code", RID_CbC_CODE, 0 }, : -\end{verbatim} +\end{lstlisting} ここで``\_\_code''を定義する事で、Tokenizerから それを予約語として認識できるようになる。 @@ -641,8 +763,7 @@ データを保持する \verb|c_declapecs|構造体で使用される。 void型なら\verb|cts_void|, int型なら\verb|cts_int|などで表されている。 これは gcc/c-tree.h にて定義されており次のようになる。 -\begin{small} -\begin{verbatim} +\begin{lstlisting}[caption=c\_typespec\_keyword定義 ,label=code:c_typespec_keyword] enum c_typespec_keyword { : cts_int, @@ -652,15 +773,14 @@ cts_dfloat32, : }; -\end{verbatim} -\end{small} +\end{lstlisting} 以上により、\_\_codeをパースする準備ができた。 実際にはパース段階では関数の場合や変数の場合などで違う手続きが踏まれるが、 \verb|c_declspecs|構造体に\verb|cts_CbC_code|を格納する手続きは \verb|declspecs_add_type()|関数に統一されている。 この関数の巨大なswitch文に対して\verb|case RID_CbC_CODE|を追加すれば良い。 以下のようになる。 -\begin{verbatim} +\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 " @@ -680,7 +800,7 @@ else specs->typespec_word = cts_CbC_code; return specs; -\end{verbatim} +\end{lstlisting} これは実際には\verb|case RID_VOID|とほぼ同じである。 違うのは\verb|specs->typespec_word = cts_CbC_code|のみとなる。 同様にcode segmentの型はほぼ、void型と同じように扱うことになる。 @@ -689,7 +809,7 @@ パースされた型を決定し、その分のちいさなtreeを生成する関数である。 treeにする際はcode segmentは全てvoidと見なされるようにする事になっている。 よってここで生成するtreeはvoidにしなければならない。 -\begin{verbatim} +\begin{lstlisting}[caption=finish\_declspecs関数,label=code:finish_declspecs] case cts_void: case cts_CbC_code: gcc_assert (!specs->long_p && !specs->short_p @@ -697,7 +817,7 @@ && !specs->complex_p); specs->type = void_type_node; break; -\end{verbatim} +\end{lstlisting} これで\_\_codeによる型がvoid型にマップされた。 @@ -706,7 +826,7 @@ 後の処理で識別するため、FUNCTION\_TYPE treeにフラグをつける必要がある。 この特殊なFUNCTION\_TYPEを生成する関数を gcc/tree.c に作っておく。 具体的には以下の様な関数になる。 -\begin{verbatim} +\begin{lstlisting}[caption=build\_code\_segment\_type関数,label=code:build_code_segment] tree build_code_segment_type (tree value_type, tree arg_types) { @@ -723,7 +843,7 @@ layout_type (t); return t; } -\end{verbatim} +\end{lstlisting} \verb|CbC_IS_CODE_SEGMENT|というマクロがcode segmentを示すフラグである (これは gcc/cbc-tree.hで定義してある)。 ユーザが定義できるように gcc/tree.h で用意されている @@ -733,7 +853,7 @@ このtreeをハッシュ表に登録しないところだけが違っている。 つづいてこの\verb|build_code_segment_type|を使用すべき関数、 -grokdeclaratorを修正する。 +\verb|grokdeclarator|を修正する。 この関数は今までパースしてきた情報の入った構造体、 \verb|c_declspecs|と\verb|c_declarator|をもとに、その変数や関数を表すtreeを gcc/tree.c の関数を使って生成している。 @@ -741,7 +861,7 @@ この関数で\verb|build_function_type|関数を使用している箇所 3番目の(巨大な)switch文の\verb|case cdk_function:|の部分である。 これを、code segmentの場合には\verb|build_code_segment_type|を使うようにする。 -\begin{verbatim} +\begin{lstlisting}[caption=grokdeclarator関数,label=code:grokdeclarator] if ( declspecs->typespec_word &=& cts_CbC_code ) { type = build_code_segment_type (type, arg_types); @@ -750,7 +870,7 @@ { type = build_function_type (type, arg_types); } -\end{verbatim} +\end{lstlisting} これで、\_\_code型がパースされた時にはFUNCITON\_TYPEにフラグが付くようになった。 code segmentかをチェックする時はtree typeに対して \verb|CbC_IS_CODE_SEGMENT (type)|として真偽値が返される。 @@ -758,9 +878,61 @@ \section{goto のパース} つづいてgoto文のパースが必要になる。 -goto文は通常のCの構文にも存在するが、 +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の分割} @@ -836,7 +1008,7 @@ \subsection{引数の計算} 引数の計算を行う。 -\begin{verbatim} +\begin{lstlisting}[caption=引数の計算,label=code:compute_args] for (i = 0; i < num_actuals; i++) { if (args[i].reg == 0 || args[i].pass_on_stack) @@ -845,7 +1017,7 @@ adjusted_args_size.var != 0); } } -\end{verbatim} +\end{lstlisting} この処理で一つ一つの引数に付いて、与えられた式を計算し、レジスタか もしくはスタックに格納しておく。 \verb|preexpand_argument_expr|関数はgcc/calls.c @@ -858,12 +1030,12 @@ にデータを移動する命令をするだけでよい。 \subsection{オーバーラップ} -\ref{}節でも説明したように、2つ以上の引数のもとのアドレスと -格納先アドレスが相互に重なる場合、一時的な変数に格納する必要がある。 +\ref{sec:condition_of_tailcall}節でも説明したように、 +2つ以上の引数のもとのアドレスと格納先アドレスが相互に重なる場合、 +一時的な変数に格納する必要がある。 \verb|expand_cbc_goto|ではこの処理を\verb|push_overlaps|関数に任せている。 それほど大きな関数ではないので以下にコードを示す。 -\begin{small} -\begin{verbatim} +\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++) @@ -882,8 +1054,7 @@ } return; } -\end{verbatim} -\end{small} +\end{lstlisting} 重要なのは\verb|assign_temp|である。 この関数は指定されたサイズ分のメモリ領域をスタックに確保する。 これにより、オーバラップする可能性のある引数を一時的な領域に格納できる。 @@ -900,23 +1071,23 @@ \verb|args->value|から\verb|args->stack|へデータを移動する RTLを生成する。 具体的には以下の様な関数\verb|emit_push_insn|を使っている。 -\begin{verbatim} +\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{verbatim} +\end{lstlisting} \subsection{CALL\_INSN} 最後にCALL\_INSNを発行する処理が来る。 -\begin{verbatim} +\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{verbatim} +\end{lstlisting} この\verb|rtx_for_function_call|関数により、funexp変数にcallee関数の アドレスを示したrtxが格納され、 それを引数に\verb|emit_call_1|関数を呼び出している。 @@ -925,52 +1096,27 @@ これがこの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{評価}\label{appraising} +\chapter{評価}\label{chp:appraising} 今回実装できたGCCによるCbCコンパイラを評価してみる。 評価の手法としてはあるCbCプログラムをMicro-CとGCCでコンパイルして、 その出力されたコードの実行速度を測れば良いだろう。 今回測定に使用したプログラムはこれまでもMicro-Cの測定に使われていた テストルーチンで、普通のCのソースをCbCに機械的に変換したものである。 -引数に1を入れるとその変換されたCbCのコード、 +引数に0を入れると変換される前の通常の関数のコード、 +引数に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 + \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} @@ -988,14 +1134,14 @@ 少なくなるようにコンパイルされる。 この場合では引数2,3の場合も大幅に改善され、Micro-Cの結果に近づいていが、 やはり少し速度は勝てない。 -これは様々な理由が考えられるが、最大の理由は +この結果には様々な理由が考えられるが、最大の理由は Micro-Cではfastcallが使われている事だと思われる。 Micro-Cのコードでは関数呼び出しの際、スタックに全ての引数をつめるのではなく、 できる限り開いているレジスタを使うようになっている。これがfastcallである。 GCCはfastcallをサポートしているので、これも試してみた。 -fastcallを有効にするには関数定義の際に -\verb|int __attribute__ ((fastcall)) test(){| +fastcallを有効にするにはcode segment定義の際に +\verb|__code __attribute__ ((fastcall)) test(){| として、型と関数名の間に挿入する。 ここでは上記の-fomit-frame-pointerも有効にした。 その測定結果が表\ref{tab:mc,gcc,compare}の``GCC (+fastcall)''の行である。 @@ -1007,9 +1153,54 @@ GCCと互換性のあるCbCの処理系は他にないので、 code segmentの場合はfastcallを強制させる事も今後の課題として考えられる。 +ちなみに、表のTCCとは``Tiny C Compiler''のことである。 +このコンパイラの詳細に付いては割愛するが、Cのソースコードを +アセンブラを介さずに直接オブジェクトファイルに変換することができる。 +本研究の前にTCCにもCbCコンパイル機能の実装を行ったが、 +表の通り満足の行く結果ではなかった +\footnote{しかしこれは実装手段が悪かったと思われる。 +gotoの際に毎回strcpyするようなこと +を改良すれば大幅高速化できるだろう。}。 -\chapter{今後の課題}\label{problem} + +\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変換不能 @@ -1020,7 +1211,7 @@ \item -O2 フラグの強制 \item code segmentは全部 \verb|__attribute__ ((fastcall))|でもいいか \end{itemize} - +\end{comment} \begin{thebibliography}{9} \bibitem{kono1} 河野真治. ``継続を基本とした言語CbCのgcc上の実装''. @@ -1029,8 +1220,15 @@ 日本ソフトウェア科学会第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} +TCCの評価結果 +conv1 0での評価 +conv1のソースコード全体 + +