Papers/2011/nobu-prosym: Paper/nobu-prosym.tex comparison

comparison Paper/nobu-prosym.tex @ 20:9e904a731cf4

modify

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Sun, 20 Nov 2011 17:55:14 +0900
parents	e89540b527cf
children	f6a58652d10c

comparison

equal deleted inserted replaced

-:e89540b527cf
+:9e904a731cf4
 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
 \section{GCCの3つの内部表現}
 GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.
-\subsection{3つの内部表現}
 GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
 それぞれが
 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
 最後にアセンブラ言語へと出力される.
 図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.
 \caption{GCC によるコンパイルの一連の流れ}
 \label{fig:ir}
 \end{figure}
-\subsubsection{Generic Tree}
+\subsection{Generic Tree}
 ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
 関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
 CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.
-\subsubsection{GIMPLE}
+\subsection{GIMPLE}
 Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
 GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
 制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
 GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
 CbC の実装では特に修正は加えていない.
-\subsubsection{Register Transfer Language (RTL)}
+\subsection{Register Transfer Language (RTL)}
 構文木 GIMPLE は解析が行われた後 RTL へと変換される.
 RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
 プログラム内部では RTL も木構造で表される.
 CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.
 \section{GCC-4.6 への実装}
 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
 ここからは GCC-4.6 への実装について述べていく.
-%\subsection{``\_\_code'' のパース}
+\subsection{``\_\_code'' のパース}
+C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている.
+ここに,図\ref{fig:code-parse}のように \verb+code+ の登録を行う.
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
+\end{center}
+\caption{\_\_code のパース}
+\label{fig:code-parse}
+\end{figure}
+これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる.
+次に, id を用意する.
+Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される.
+そこに登録するコードセグメント判定用 id  ``\verb+cts_CbC_code+'' を用意する.
+これは gcc/c-tree.h で定義される(図\ref{fig:code-id}).
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.35}{\includegraphics{figure/code-id.eps}}
+\end{center}
+\caption{cts\_CbC\_code の定義}
+\label{fig:code-id}
+\end{figure}
+後は\verb+c_declspecs+ 構造体にこの id を登録する.
+id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}).
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.35}{\includegraphics{figure/regi-id.eps}}
+\end{center}
+\caption{id の登録(declspecs\_add\_type 関数)}
+\label{fig:regi-id}
+\end{figure}
+図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている.
+違うところは \verb+cts_CbC_code+ を登録するところだけである.
+最後に, \verb+finish_declspecs+ 関数にて id 毎に tree タイプの決定をする.
+コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ をタイプと
+して登録している(図\ref{fig:regi-node}).
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
+\end{center}
+\caption{declspecs\_add\_type 関数}
+\label{fig:regi-node}
+\end{figure}
 \subsection{Tail Call Elimination}
 CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する.
 これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
 %Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
 %call ではなく jmp を用いることができるという最適化である.
 図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
 \begin{figure}[htpb]
 \begin{center}
-\scalebox{0.35}{\includegraphics{figure/continuation.eps}}
+\scalebox{0.30}{\includegraphics{figure/continuation.eps}}
 \end{center}
 \caption{Tail Call Elimination}
 \label{fig:continue}
 \end{figure}
 funcB は jmp 命令で funcC を呼び出す.
 \end{enumerate}
 1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
 2, 3 と 4 については以下で詳しく説明を行う.
-\subsubsection{継続の直後に return の配置}
+\subsubsection{goto の直後に return の配置}
-この処理は Generic Tree の生成時に組み込んである為, ユーザは return を記述する必要はない.
+図\ref{fig:factoril}の factorial0 関数を図\ref{code:return}の様に, goto の直後に return を
-例をあげると, 図\ref{fig:factorial}の factorial0 は,
+置く必要がある.だがそれをプログラムで記述することは実用的でない.
-プログラム内部では図\ref{code:return}の様に処理されることになる.
+CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
+%, ユーザは return を記述する必要はない.
+%例をあげると, 図\ref{fig:factorial}の factorial0 は,
+% プログラム内部では図\ref{code:return}の様に処理されることになる.
 \begin{figure}[h]
 \begin{minipage}[b]{.45\textwidth}
-\begin{lstlisting}[caption=継続の直後に return を置く,label=code:return]
+\begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
 __code factorial0(int prod, int x)
 {
 if ( x >= 1) {
 goto factorial0(prod*x, x-1);
 return;
 %Tail Call Elimination にかからないコードセグメントがある.
 %この点を改善する必要がある.
 %\subsection{引数の一時変数への避難}
 %\subsection{スタック書き換えの問題}
-\subsection{引数の並びの上書きコピー}
+\subsubsection{引数の並びの上書きコピー}
 CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
 例えばlistlising\ref{code:cs_prog}のような継続である.
 \begin{figure}[h]
 \begin{minipage}[b]{.45\textwidth}
 \begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
 tree call は継続を行うコードセグメントを指す.
 コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
 ところへ一時変数を入れている.
 \subsection{環境付き継続}
 CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
 これを環境付き継続という.
 これらは, 以下の二種類の CbC で定義した特殊変数である.
 \verb+__environment+ は, 環境を表す情報である.
-\verb__return+ は,  これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ
+\verb+__return+ は,  これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ
 コードセグメントである. 例えば, 以下のように使うと, \verb+main()+ は 1 を返す.
 \begin{verbatim}
 __code c1(__code ret(int,void *),void *env) {
 goto ret(1,env);
 \begin{figure}[h]
 \begin{minipage}[b]{.45\textwidth}
 \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
 __label__ _cbc_exit0;
-static int retval; // should be thread local
+static int retval;
-void _cbc_internal_return(int retval_, void *_envp){
+void _cbc_internal_return(int retval_,
+void *_envp){
 retval = retval_;
 goto _cbc_exit0;
 }
 if (0) {
 _cbc_exit0:
 \subsubsection{fastcall}
 C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う.
 だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない.
 そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う.
-図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているコードである.
+図\ref{fig:fastcall}はコードセグメントの生成を行なっているコードである.
 %\lstinputlisting[language=c]{source/fastcall.c}
 \begin{figure}[htpb]
 \begin{center}
 \end{lstlisting}
 \end{minipage}
 \hfill
 \end{figure}
-typedefrec によりコードセグメントは自分自身に戻る構成ができる.
+typedefrec によりコードセグメントは自分自身に戻る構成ができるようになる.
 より柔軟なプログラミングが行えるように typdefrec の実装を行う予定である.
 \section{評価}
 今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
 Micro-C コンパイラとそれぞれ比較を行った.
 比較を行うのはクイックソートのプログラムである.
-クイックソートは再帰的にプログラムされる為 CbC に向いている
+%クイックソートは再帰的にプログラムされる為 CbC に向いている
-プログラムだと言える.
+%プログラムだと言える.
+クイックソートは再帰的なプログラムな為スタック操作が行われる.
 比較を行うのは以下のアーキテクチャと OS になる.
 %\begin{description}
 \begin{itemize}
 \item x86/Linux
 \end{tabular}
 \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
 \label{tab:speed-mc-vs-gcc-opt}
 \end{table}
+\section{まとめと今後の課題}
+今回 CbC コンパイラを GCC-4.6 へとアップデートを行った.
 \nocite{kono:2002a, kono:2008a, yogi:2008a, gcc_internals}
 \bibliographystyle{junsrt}
 \bibliography{cbc.bib}
 \end{document}

Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 20:9e904a731cf4