# HG changeset patch # User Nobuyasu Oshiro # Date 1325908345 -32400 # Node ID 7ed352ddae10e0dce1dd359897511d577ee83153 # Parent fb5994f49abddde5256d638f6cbd3d979633cf13 modify spell miss diff -r fb5994f49abd -r 7ed352ddae10 Paper/figure/rid-goto.pdf Binary file Paper/figure/rid-goto.pdf has changed diff -r fb5994f49abd -r 7ed352ddae10 Paper/nobu-prosym.tex --- a/Paper/nobu-prosym.tex Sat Jan 07 09:16:58 2012 +0900 +++ b/Paper/nobu-prosym.tex Sat Jan 07 12:52:25 2012 +0900 @@ -1,1 +1,1 @@ -\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} \usepackage{multirow} %% tabularの上下の結合 \usepackage{slashbox} %% tabularでの斜め線 \usepackage{listings} %\usepackage{jtygm} \usepackage{mediabb} \usepackage{float} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} %\def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 本論文では GCC-4.6 への CbC の具体的な実装について述べる. %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している. コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより, Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている. CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. %今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. %本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある. %本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. 本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. % }{ \section{Continuation based C (CbC)} CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る. 構文は C と同じであるが, ループ制御や関数コールが取り除かれる. %Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. %構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. %また,コードセグメント単位で処理を記述するという特徴がある. %図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \subsection{継続(goto)} コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる. コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える. 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. %コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. %コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. %この goto によるコードセグメント間の移動を継続と言う. %継続の実態は jmp による関数の移動となる. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/codesegment.pdf}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{コードセグメント(code segment)} コードセグメントは C の関数と違って戻値を持たず, 処理が終われば次のコードセグメントへと処理を移る. C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. だが, 戻値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない. 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/factorial.pdf}} \end{center} \caption{階上を計算する CbC プログラムの例} \label{fig:factorial} \end{figure} %\begin{center} %\begin{small} %\lstinputlisting % [caption=factorial.cbc, % label=code:factorial, % tabsize=4] % {source/factorial.cbc} %\end{small} %\end{center} \section{GCC で扱われる内部表現} GCC-4.6 への実装の前に, GCC で扱われる内部表現について触れておく. GCC は内部で Generic Tree, GIMPLE Tree, Tree SSA, RTL という4つの内部表現を扱う(GIMPLE と SSA は一緒に考えられることもある). それぞれが 読み込んだソースコードは Generic Tree, GIMPLE Tree, Tree SSA, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/ir.pdf}} \end{center} \caption{GCC によるコンパイルの一連の流れ} \label{fig:ir} \end{figure} \subsection{Generic Tree} ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる. 関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される. CbC の実装ではパースの部分からこの Generic Tree 生成の部分に手が加わっている. \subsection{GIMPLE Tree} Generic Tree で表現されたデータは GIMPLE Tree に変換される. GIMPLE Tree は Generic Tree より制約がかかった状態で作成された構文木となる. 制約は「1つの枝につく子が3つ以下になるように分解」等といったもので, GIMPLE Tree へと変換されたデータは Generic Tree より簡単な命令で表されることになる. CbC の実装では特に修正は加えていない. \subsection{Tree SSA} Tree SSA (Static Single Assignment) は, プログラムの中で 変数が一度しか代入されないように変換させた構文木になる. SSA に変換することで, 様々な最適化が行いやすくなる. こちらも GIMPLE 同様 CbC の実装では特に修正は加えていない. \subsection{Register Transfer Language (RTL)} Tree SSA は解析が行われた後 RTL へと変換される. RTL はレジスタの割り当てといった低レベルの表現であり, アセンブラとほぼ同じ命令の表現を行うことができる. プログラム内部では RTL も木構造で表される. CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる. \section{GCC-4.6 への実装} 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく. \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.pdf}} \end{center} \caption{\_\_code のパース} \label{fig:code-parse} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/code-id.pdf}} \end{center} \caption{cts\_CbC\_code の定義} \label{fig:code-id} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/regi-id.pdf}} \end{center} \caption{id の登録} \label{fig:regi-id} \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}). 後は\verb+c_declspecs+ 構造体にこの id を登録する. id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}). 図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている. 違うところは \verb+cts_CbC_code+ を登録するところだけである. 読み込まれたコードは, 最後に \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする. コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと して登録している(図\ref{fig:regi-node}). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/regi-node.pdf}} \end{center} \caption{declspecs\_add\_type 関数} \label{fig:regi-node} \end{figure} \subsection{goto シンタックスの追加} 通常 goto のシンタックスは ``goto ラベル名;'' となる. CbC では通常の goto に加え ``goto cs(arg,...);'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある. 図\ref{fig:rid-goto}は, 追加した goto のシンタックスである (通常のシンタックスは省いてある). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/rid-goto.pdf}} \end{center} \caption{goto へのシンタックスの追加} \label{fig:rid-goto} \end{figure} %具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した. 具体的には void 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ を付けた関数の Tree となっている. %の作成を行なっている. \verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については CbC においても重要になるので後に説明する. \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する. これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する. %Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, %call ではなく jmp を用いることができるという最適化である. 図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. funcB は jmp 命令で funcC を呼び出す. funcC は, 戻値を funcB ではなく funcA へと返すことになる. \begin{figure}[htpb] \begin{center} \scalebox{0.25}{\includegraphics{figure/continuation.pdf}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} \subsubsection{expand\_call} \verb+expand_call+ 関数は, 関数を表す Tree から RTL を生成する関数である. Tail Call Elimination を行えるかどうかもこの関数で判断される. 内部でチェックされる Tail Call Elimination の条件は以下になる. %\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる. %\begin{itemize} \begin{enumerate} \item caller 側と callee 側の戻値の型が一致している. \item 関数呼び出しがリターンの直前に行われている. \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない. \item 引数の並びのコピーに上書きがない. \end{enumerate} %\end{itemize} CbC の実装では上記の条件を,以下の様にして解決させている. \begin{enumerate} %\begin{itemize} % \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない. \item コードセグメントは void 型で統一する. 最適化(-O2)の強制付与. \item goto の直後に retrun を置く． \item スタックサイズは関数宣言時に決まったサイズにする． \item 引数は一旦, 一時変数にコピーして重なりがないようにする． %\end{itemize} \end{enumerate} %1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる. %2, 3 と 4 については以下で詳しく説明を行う. 戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう. 最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う. \subsubsection{末尾最適化の強制付与} Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる. 以前の CbC-GCC の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_goto+ という関数を作成して, 条件をクリアするようにしていた. しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_goto+ 関数にも 変更を加える必要があり, 手間となっていた. そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_goto+ 関数を取り除くことに 成功した(図\ref{fig:tail_call}:2行目). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/tail_call_flag.pdf}} \end{center} \caption{コードセグメントの末尾最適化の付与} \label{fig:tail_call} \end{figure} \verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+ 変数があり, コードセグメントはこのフラグには初め 1 がセットされている. コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った. また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った. これにより末尾最適化の強制付与がなされた. \subsubsection{goto の直後に return の配置} コードセグメントは GCC 内部では関数として扱われる. Tail Call Elimination は関数呼び出しの直後に return がある場合にかかる. その為, goto の直後に return を置く必要がある. CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している. 図\ref{fig:rid-goto}の \verb+c_finish_return+ 関数がそれにあたる. これにより, コンパイラでは図\ref{fig:factorial}のコードセグメント factorial0 が図\ref{fig:return} として処理される. %図\ref{fig:factorial}のコードセグメント factorial0 を図\ref{fig:return}の様に, goto の直後に return を %置く必要がある.だがそれをプログラマが記述することは実用的でない. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/return_factorial.pdf}} \end{center} \caption{goto の直後に return を置く} \label{fig:return} \end{figure} %goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う. \subsubsection{スタックサイズの固定化} CbC の継続では, C の関数呼び出しとは違いスタックに値が積まれていくことはない. その為スタックサイズを固定にすることができる. また, スタックサイズが固定な為, スタックポインタを変えずにスタックを扱うことができる. これも CbC の1つの特徴である. 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.30}{\includegraphics{figure/cs_stack.pdf}} \end{center} \caption{継続による引数のスタック格納の様子} \label{fig:cs_stack} \end{figure} %GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも %Tail Call Elimination にかからないコードセグメントがある. %この点を改善する必要がある. %\subsection{引数の一時変数への避難} %\subsection{スタック書き換えの問題} \subsubsection{引数の並びの上書きコピー} CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる. 例えば図\ref{fig:cs_prog_code}のような継続である. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cs_prog_code.pdf}} \end{center} \caption{スタックの上書きが起こる継続} \label{fig:cs_prog_code} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cs_prog.pdf}} \end{center} \caption{スタック書き換えの問題} \label{fig:cs_prog} \end{figure} この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる. 数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している. CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している. \subsubsection{一時変数へのコピー} 一時変数へのコピーは, goto が行れるコードセグメントの Generic Tree 生成時に行われる. 図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる. %\begin{figure} %\lstinputlisting[language=c]{source/cbc_replace_arguments.c} %\caption{引数の一時変数へのコピー} %\label{fig:cbc_replace} %\end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cbc_replace.pdf}} \end{center} \caption{引数の一時変数へのコピー} \label{fig:cbc_replace} \end{figure} 具体的には, 内部で以下の事が行われている. \begin{itemize} \item 引数と同じ型の一時変数を作成 \item 一時変数に引数の値を代入 \item 関数に渡す引数のポインタを一時変数に変更 \end{itemize} 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+ の二つの引数を持つ コードセグメントである. 例えば, 図\ref{fig:env_code}のように使うと, \verb+main()+ は 1 を返す. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/env_code.pdf}} \end{center} \caption{\_\_return, \_\_environment 変数の使用例} \label{fig:env_code} \end{figure} GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. 戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(図\ref{fig:ret_val_code}). \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/ret_val_code.pdf}} \end{center} \caption{環境付き継続を行うコード} \label{fig:ret_val_code} \end{figure} \subsubsection{環境付き継続の問題} 現在環境付き継続は このコードを GCC 内部で生成することで実現している. これは正しく動作しているが, \verb+retval+に static を指定してしまうと, スレッドセーフな実装でなくなる. これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の 組合せでは closure は正しく動作してないことがわかった. Thread local 変数を用いると, やはり closure が出力されてしまう. 本来, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず, 浮動小数点や構造体自体である可能性があり複雑である. 一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある. \subsection{引数の渡し方} 通常 ia32 のコードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される. だが GCC には ia32 の引数渡しにレジスタを用いらせる機能として fastcall がある. 使えるレジスタは 2つまでだが, 継続を繰り返して行う CbC においては fastcall を使うことで速度向上が望めるはずである. \subsubsection{fastcall} C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う. だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない. そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントの生成を行なっているコードである. %\lstinputlisting[language=c]{source/fastcall.c} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/fastcall.pdf}} \end{center} \caption{コードセグメントへのfastcall属性付与} \label{fig:fastcall} \end{figure} 13, 14 行目が fastcall 属性を付与している部分になる. if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて, warning を出すからである. \subsection{typedefrec, selftype の実装の構想} C では関数や構造体の宣言の時に自分自身を引数にすることができない. そこで ``typedefrec'', ``selftype'' という構文を作り, 図\ref{fig:typedefrec}のような宣言を行えるようにしたい. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/typedefrec.pdf}} \end{center} \caption{typedefrec と selftype の例} \label{fig:typedefrec} \end{figure} typedefrec によりコードセグメントは自分自身に戻る構成ができるようになり, selftype により宣言中の構造体自身を構造体のメンバとして扱えるようになるのである. より柔軟なプログラミングが行えるように typdefrec, selftype の実装を行う予定である. \section{評価} 今回実装を行った GCC-4.6 ベース と安定版である GCC-4.4 ベース, それと Micro-C の CbC コンパイラでベンチマークを行った. プログラムは Micro-C のベンチマークを使用する \footnote{ベンチマークのコードは\ref{chp:conv1}付録に掲載する.} また, テストは通常の C であったプログラムを CbC へと変換して行った. このプログラムは CbC の継続と計算を交互に行うものである. 引数 1 はただ CbC へと変換したプログラム, 引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムになる. 比較を行うのは以下のアーキテクチャと OS になる. %\begin{description} \begin{itemize} \item x86/Linux \item x86/OS X \end{itemize} %\end{description} 32 bit, 64 bit の動作も確認する. また, 最適化無し (-O0) と速度最適化 (-O2 -fomit-frame-pointer ) にかけたコードの比較を行う. 比較の結果を図\ref{fig:linux_conv}, \ref{fig:mac_conv} に示す. ただしGCC-4.6 の最適化無しコードは, コードセグメントに対して末尾最適化を強制したことが 原因で segmentation fault を起こす為除外している. (また Micro-C の 64bit 版は Linux では動かなかった為 OS X だけとなっている.) \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/linux_conv.pdf}} \end{center} \caption{それぞれのコンパイラにより生成されたコードの速度比較(Linux)} \label{fig:linux_conv} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/mac_conv.pdf}} \end{center} \caption{それぞれのコンパイラにより生成されたコードの速度比較(OS X)} \label{fig:mac_conv} \end{figure} \subsection{評価の考察} 最適化無しの結果では Micro-C が早いが, 最適化有りでは GCC バージョンの方がどれも Micro-C に 2.5倍程の差をつけている. 最適化有りの GCC は 64bit の方が 32bit より 2倍程結果が優れているのも確認できる. 4.4, 4.6 での違いは引数が 1 の時である. 4.6 が2倍近く早くなっている. これは, 4.6 の方が 4.4 よりも最適化が進んでいる為だと思われる. \section{CbC のアップデート手法} 最後に, CbC のアップデート手法について述べる. 現在 GCC は年に数回アップデートが行われている. GCC に合わせて CbC のアップデートを行うのが好ましいが, その度新しいソースコードに合わせていくのは負担が大きい. GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが 現時点ではまだそこまで至っていない. そこで Mercurial を使ってアップデート方法を行なっている. \subsection{Mercurial によるアップデート} Mercurial はバージョン管理システムである. 当研究室では CbC のソースコードは Mercurial によって管理されている. Mercurial では本家 GCC のソースコードも管理されており, これら 2 つのリポジトリを使って CbC のアップデートは行われる (図\ref{fig:cbc-repo}に CbC-GCC リポジトリのグラフを示す). 具体的な方法は次の様になる. \begin{figure}[b] \begin{center} %\scalebox{0.31}{\includegraphics{figure/graph.pdf}} %\scalebox{0.30}[0.25]{\includegraphics{figure/graph_gray.pdf}} \includegraphics[scale=0.3]{./figure/graph_gray.pdf} \end{center} \caption{CbC-GCC リポジトリのグラフ(一部)} \label{fig:cbc-repo} \end{figure} \begin{itemize} \item GCC リポジトリ \begin{enumerate} \item GCC リポジトリの中身を削除 (バージョン管理情報以外) \item 新しい GCC のソース入れる \item hg status で追加ファイルと削除ファイルを確認 \item 追加, 削除するファイルに対して hg add, hg remove を行う \item コミット \item gcc version タグを追加 \end{enumerate} \newpage \item CbC リポジトリ \begin{enumerate} \item GCC リポジトリから hg pull を行う \item hg merge でマージを行う \item 衝突が発生したファイルのマージを行う \item ビルドを行い動作確認 \item コミット \item gcc version タグを追加 \end{enumerate} \end{itemize} %\begin{figure}[htpb] % \begin{center} %\scalebox{0.33}{\includegraphics{figure/mercurial_update.pdf}} % \end{center} % \caption{CbConGCC リポジトリの管理(左:本家GCC 中央:独自のGCCリポジトリ 右:CbConGCC リポジトリ)} % \label{fig:mercurial} %\end{figure} %\begin{figure}[htpb] % \begin{center} %\scalebox{0.33}{\includegraphics{figure/gcc-repo.pdf}} % \end{center} % \caption{当研究室で管理している GCC リポジトリのグラフ} % \label{fig:gcc-repo} %\end{figure} \subsection{リポジトリ管理方法の評価} 上記のリポジトリ管理方法を用いて GCC-4.5.0 から GCC-4.6.0 へのアップデートを行った. この手法を用いらない場合は手動で diff を行い差分を探すことになる. だが, 上記の手法ではほとんどの差分の適用を Mercurial が自動で行ってくれた. 手動で差分を直したのは CbC の実装を行ったファイルだけで済んだ. CbC 実装の為のコードが入り, かつ移動されたファイルがあり, それらだけは 2 つのバージョンを並べて手動で diff を行うことになったが, ファイル自体が少ない為 差分の適応はすぐに行えた. %\begin{figure}[h] %\begin{figure}[b] % \begin{center} %\includegraphics[scale=0.3]{./figure/graph_gray.pdf} % \end{center} % \caption{CbC-GCC リポジトリのグラフ(一部)} % \label{fig:cbc-repo} %\end{figure} \section{まとめと今後の課題} 今回 CbC コンパイラを GCC-4.6 へとアップデートを行った. アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った. だが, 環境付き継続等未だ幾つかの問題を残している. typedefrec, selftype といった新たに実装を行いたい機能もでてきた. また, 当研究室ではコードセグメントとデータセグメントを用いた並列・分散プログラミングを提案している. データセグメントは C における構造体のようにデータをまとめて取り扱えるものであり、コードセグメント(タスク)がデータの入出力時に使用する. タスクの並列動作をサポートするためにタスクを管理するエンジンを実装するにあたり、それらも踏まえて CbC-GCC は実装を行っていかなくてはならない. \nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals} \bibliographystyle{junsrt} \bibliography{cbc.bib} %今後はこれらを考えて CbC-GCC の実装を行っていく予定である. %また, 当研究室では CbC を用いてコードセグメントとデータセグメントを組み合わせたプログラミングスタイルを %提案している. %また, CbC を Google Go 言語での実装等の研究も行う予定である. \newpage \section{付録}\label{chp:conv1} 以下はコンパイラのベンチマークで用いたプログラム conv1 である. \subsection{conv1.c} \begin{small} \lstinputlisting [label=code:conv1, tabsize=4, frame=single, breaklines] {source/conv1.c} \end{small} \end{document} \ No newline at end of file +\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} \usepackage{multirow} %% tabularの上下の結合 \usepackage{slashbox} %% tabularでの斜め線 \usepackage{listings} %\usepackage{jtygm} \usepackage{mediabb} \usepackage{float} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} %\def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 本論文では GCC-4.6 への CbC の具体的な実装について述べる. %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している. コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより, Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている. CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. %今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. %本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある. %本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. 本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. % }{ \section{Continuation based C (CbC)} CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る. 構文は C と同じであるが, ループ制御や関数コールが取り除かれる. %Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. %構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. %また,コードセグメント単位で処理を記述するという特徴がある. %図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \subsection{継続(goto)} コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる. コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える. 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. %コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. %コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. %この goto によるコードセグメント間の移動を継続と言う. %継続の実態は jmp による関数の移動となる. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/codesegment.pdf}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{コードセグメント(code segment)} コードセグメントは C の関数と違って戻値を持たず, 処理が終われば次のコードセグメントへと処理を移る. C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. だが, 戻値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない. 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/factorial.pdf}} \end{center} \caption{階乗を計算する CbC プログラムの例} \label{fig:factorial} \end{figure} %\begin{center} %\begin{small} %\lstinputlisting % [caption=factorial.cbc, % label=code:factorial, % tabsize=4] % {source/factorial.cbc} %\end{small} %\end{center} \section{GCC で扱われる内部表現} GCC-4.6 への実装の前に, GCC で扱われる内部表現について触れておく. GCC は内部で Generic Tree, GIMPLE Tree, Tree SSA, RTL という4つの内部表現を扱う(GIMPLE と SSA は一緒に考えられることもある). それぞれが 読み込んだソースコードは Generic Tree, GIMPLE Tree, Tree SSA, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/ir.pdf}} \end{center} \caption{GCC によるコンパイルの一連の流れ} \label{fig:ir} \end{figure} \subsection{Generic Tree} ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる. 関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される. CbC の実装ではパースの部分からこの Generic Tree 生成の部分に手が加わっている. \subsection{GIMPLE Tree} Generic Tree で表現されたデータは GIMPLE Tree に変換される. GIMPLE Tree は Generic Tree より制約がかかった状態で作成された構文木となる. 制約は「1つの枝につく子が3つ以下になるように分解」等といったもので, GIMPLE Tree へと変換されたデータは Generic Tree より簡単な命令で表されることになる. CbC の実装では特に修正は加えていない. \subsection{Tree SSA} Tree SSA (Static Single Assignment) は, プログラムの中で 変数が一度しか代入されないように変換させた構文木になる. SSA に変換することで, 様々な最適化が行いやすくなる. こちらも GIMPLE 同様 CbC の実装では特に修正は加えていない. \subsection{Register Transfer Language (RTL)} Tree SSA は解析が行われた後 RTL へと変換される. RTL はレジスタの割り当てといった低レベルの表現であり, アセンブラとほぼ同じ命令の表現を行うことができる. プログラム内部では RTL も木構造で表される. CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる. \section{GCC-4.6 への実装} 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく. \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.pdf}} \end{center} \caption{\_\_code のパース} \label{fig:code-parse} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/code-id.pdf}} \end{center} \caption{cts\_CbC\_code の定義} \label{fig:code-id} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/regi-id.pdf}} \end{center} \caption{id の登録} \label{fig:regi-id} \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}). 後は\verb+c_declspecs+ 構造体にこの id を登録する. id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}). 図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている. 違うところは \verb+cts_CbC_code+ を登録するところだけである. 読み込まれたコードは, 最後に \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする. コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと して登録している(図\ref{fig:regi-node}). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/regi-node.pdf}} \end{center} \caption{declspecs\_add\_type 関数} \label{fig:regi-node} \end{figure} \subsection{goto シンタックスの追加} 通常 goto のシンタックスは ``goto ラベル名;'' となる. CbC では通常の goto に加え ``goto cs(arg,...);'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある. 図\ref{fig:rid-goto}は, 追加した goto のシンタックスである (通常のシンタックスは省いてある). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/rid-goto.pdf}} \end{center} \caption{goto へのシンタックスの追加} \label{fig:rid-goto} \end{figure} %具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した. 具体的には void 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ を付けた関数の Tree となっている. %の作成を行なっている. \verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については CbC においても重要になるので後に説明する. \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する. これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する. %Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, %call ではなく jmp を用いることができるという最適化である. 図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. funcB は jmp 命令で funcC を呼び出す. funcC は, 戻値を funcB ではなく funcA へと返すことになる. \begin{figure}[htpb] \begin{center} \scalebox{0.25}{\includegraphics{figure/continuation.pdf}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} \subsubsection{expand\_call} \verb+expand_call+ 関数は, 関数を表す Tree から RTL を生成する関数である. Tail Call Elimination を行えるかどうかもこの関数で判断される. 内部でチェックされる Tail Call Elimination の条件は以下になる. %\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる. %\begin{itemize} \begin{enumerate} \item caller 側と callee 側の戻値の型が一致している. \item 関数呼び出しがリターンの直前に行われている. \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない. \item 引数の並びのコピーに上書きがない. \end{enumerate} %\end{itemize} CbC の実装では上記の条件を,以下の様にして解決させている. \begin{enumerate} %\begin{itemize} % \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない. \item コードセグメントは void 型で統一する. 最適化(-O2)の強制付与. \item goto の直後に retrun を置く． \item スタックサイズは関数宣言時に決まったサイズにする． \item 引数は一旦, 一時変数にコピーして重なりがないようにする． %\end{itemize} \end{enumerate} %1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる. %2, 3 と 4 については以下で詳しく説明を行う. 戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう. 最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う. \subsubsection{末尾最適化の強制付与} Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる. 以前の CbC-GCC の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_goto+ という関数を作成して, 条件をクリアするようにしていた. しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_goto+ 関数にも 変更を加える必要があり, 手間となっていた. そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_goto+ 関数を取り除くことに 成功した(図\ref{fig:tail_call}:2行目). \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/tail_call_flag.pdf}} \end{center} \caption{コードセグメントの末尾最適化の付与} \label{fig:tail_call} \end{figure} \verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+ 変数があり, コードセグメントはこのフラグには初め 1 がセットされている. コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った. また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った. これにより末尾最適化の強制付与がなされた. \subsubsection{goto の直後に return の配置} コードセグメントは GCC 内部では関数として扱われる. Tail Call Elimination は関数呼び出しの直後に return がある場合にかかる. その為, goto の直後に return を置く必要がある. CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している. 図\ref{fig:rid-goto}の \verb+c_finish_return+ 関数がそれにあたる. これにより, コンパイラでは図\ref{fig:factorial}のコードセグメント factorial0 が図\ref{fig:return} として処理される. %図\ref{fig:factorial}のコードセグメント factorial0 を図\ref{fig:return}の様に, goto の直後に return を %置く必要がある.だがそれをプログラマが記述することは実用的でない. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/return_factorial.pdf}} \end{center} \caption{goto の直後に return を置く} \label{fig:return} \end{figure} %goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う. \subsubsection{スタックサイズの固定化} CbC の継続では, C の関数呼び出しとは違いスタックに値が積まれていくことはない. その為スタックサイズを固定にすることができる. また, スタックサイズが固定な為, スタックポインタを変えずにスタックを扱うことができる. これも CbC の1つの特徴である. 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.30}{\includegraphics{figure/cs_stack.pdf}} \end{center} \caption{継続による引数のスタック格納の様子} \label{fig:cs_stack} \end{figure} %GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも %Tail Call Elimination にかからないコードセグメントがある. %この点を改善する必要がある. %\subsection{引数の一時変数への避難} %\subsection{スタック書き換えの問題} \subsubsection{引数の並びの上書きコピー} CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる. 例えば図\ref{fig:cs_prog_code}のような継続である. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cs_prog_code.pdf}} \end{center} \caption{スタックの上書きが起こる継続} \label{fig:cs_prog_code} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cs_prog.pdf}} \end{center} \caption{スタック書き換えの問題} \label{fig:cs_prog} \end{figure} この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる. 数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している. CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している. \subsubsection{一時変数へのコピー} 一時変数へのコピーは, goto が行れるコードセグメントの Generic Tree 生成時に行われる. 図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる. %\begin{figure} %\lstinputlisting[language=c]{source/cbc_replace_arguments.c} %\caption{引数の一時変数へのコピー} %\label{fig:cbc_replace} %\end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/cbc_replace.pdf}} \end{center} \caption{引数の一時変数へのコピー} \label{fig:cbc_replace} \end{figure} 具体的には, 内部で以下の事が行われている. \begin{itemize} \item 引数と同じ型の一時変数を作成 \item 一時変数に引数の値を代入 \item 関数に渡す引数のポインタを一時変数に変更 \end{itemize} 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+ の二つの引数を持つ コードセグメントである. 例えば, 図\ref{fig:env_code}のように使うと, \verb+main()+ は 1 を返す. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/env_code.pdf}} \end{center} \caption{\_\_return, \_\_environment 変数の使用例} \label{fig:env_code} \end{figure} GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. 戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(図\ref{fig:ret_val_code}). \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/ret_val_code.pdf}} \end{center} \caption{環境付き継続を行うコード} \label{fig:ret_val_code} \end{figure} \subsubsection{環境付き継続の問題} 現在環境付き継続は このコードを GCC 内部で生成することで実現している. これは正しく動作しているが, \verb+retval+に static を指定してしまうと, スレッドセーフな実装でなくなる. %これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の %組合せでは closure は正しく動作してないことがわかった. Thread local 変数を用いると, やはり closure が出力されてしまう. スタックに値を確保する closure は, スタックを破棄していく CbC には向いていない. 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず, 浮動小数点や構造体自体である可能性があり複雑である. 一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある. \subsection{引数の渡し方} 通常 ia32 のコードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される. だが GCC には ia32 の引数渡しにレジスタを用いらせる機能として fastcall がある. 使えるレジスタは 2つまでだが, 継続を繰り返して行う CbC においては fastcall を使うことで速度向上が望めるはずである. \subsubsection{fastcall} C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う. だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない. そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントの生成を行なっているコードである. %\lstinputlisting[language=c]{source/fastcall.c} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/fastcall.pdf}} \end{center} \caption{コードセグメントへのfastcall属性付与} \label{fig:fastcall} \end{figure} 13, 14 行目が fastcall 属性を付与している部分になる. if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて, warning を出すからである. \subsection{typedefrec, selftype の実装の構想} C では関数や構造体の宣言の時に自分自身を引数にすることができない. そこで ``typedefrec'', ``selftype'' という構文を作り, 図\ref{fig:typedefrec}のような宣言を行えるようにしたい. \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/typedefrec.pdf}} \end{center} \caption{typedefrec と selftype の例} \label{fig:typedefrec} \end{figure} typedefrec によりコードセグメントは自分自身に戻る構成ができるようになり, selftype により宣言中の構造体自身を構造体のメンバとして扱えるようになるのである. より柔軟なプログラミングが行えるように typdefrec, selftype の実装を行う予定である. \section{評価} 今回実装を行った GCC-4.6 ベース と安定版である GCC-4.4 ベース, それと Micro-C の CbC コンパイラでベンチマークを行った. プログラムは Micro-C のベンチマークを使用する \footnote{ベンチマークのコードは\ref{chp:conv1}付録に掲載する.} また, テストは通常の C であったプログラムを CbC へと変換して行った. このプログラムは CbC の継続と計算を交互に行うものである. 引数 1 はただ CbC へと変換したプログラム, 引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムになる. 比較を行うのは以下のアーキテクチャと OS になる. %\begin{description} \begin{itemize} \item x86/Linux \item x86/OS X \end{itemize} %\end{description} 32 bit, 64 bit の動作も確認する. また, 最適化無し (-O0) と速度最適化 (-O2 -fomit-frame-pointer ) にかけたコードの比較を行う. 比較の結果を図\ref{fig:linux_conv}, \ref{fig:mac_conv} に示す. ただしGCC-4.6 の最適化無しコードは, コードセグメントに対して末尾最適化を強制したことが 原因で segmentation fault を起こす為除外している. (また Micro-C の 64bit 版は Linux では動かなかった為 OS X だけとなっている.) \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/linux_conv.pdf}} \end{center} \caption{それぞれのコンパイラにより生成されたコードの速度比較(Linux)} \label{fig:linux_conv} \end{figure} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/mac_conv.pdf}} \end{center} \caption{それぞれのコンパイラにより生成されたコードの速度比較(OS X)} \label{fig:mac_conv} \end{figure} \subsection{評価の考察} 最適化無しの結果では Micro-C が早いが, 最適化有りでは GCC バージョンの方がどれも Micro-C に 2.5倍程の差をつけている. 最適化有りの GCC は 64bit の方が 32bit より 2倍程結果が優れているのも確認できる. 4.4, 4.6 での違いは引数が 1 の時である. 4.6 が2倍近く早くなっている. これは, 4.6 の方が 4.4 よりも最適化が進んでいる為だと思われる. \section{CbC のアップデート手法} 最後に, CbC のアップデート手法について述べる. 現在 GCC は年に数回アップデートが行われている. GCC に合わせて CbC のアップデートを行うのが好ましいが, その度新しいソースコードに合わせていくのは負担が大きい. GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが 現時点ではまだそこまで至っていない. そこで Mercurial を使ってアップデート方法を行なっている. \subsection{Mercurial によるアップデート} Mercurial はバージョン管理システムである. 当研究室では CbC のソースコードは Mercurial によって管理されている. Mercurial では本家 GCC のソースコードも管理されており, これら 2 つのリポジトリを使って CbC のアップデートは行われる (図\ref{fig:cbc-repo}に CbC-GCC リポジトリのグラフを示す). 具体的な方法は次の様になる. \begin{figure}[b] \begin{center} %\scalebox{0.31}{\includegraphics{figure/graph.pdf}} %\scalebox{0.30}[0.25]{\includegraphics{figure/graph_gray.pdf}} \includegraphics[scale=0.3]{./figure/graph_gray.pdf} \end{center} \caption{CbC-GCC リポジトリのグラフ(一部)} \label{fig:cbc-repo} \end{figure} \begin{itemize} \item GCC リポジトリ \begin{enumerate} \item GCC リポジトリの中身を削除 (バージョン管理情報以外) \item 新しい GCC のソース入れる \item hg status で追加ファイルと削除ファイルを確認 \item 追加, 削除するファイルに対して hg add, hg remove を行う \item コミット \item gcc version タグを追加 \end{enumerate} \newpage \item CbC リポジトリ \begin{enumerate} \item GCC リポジトリから hg pull を行う \item hg merge でマージを行う \item 衝突が発生したファイルのマージを行う \item ビルドを行い動作確認 \item コミット \item gcc version タグを追加 \end{enumerate} \end{itemize} %\begin{figure}[htpb] % \begin{center} %\scalebox{0.33}{\includegraphics{figure/mercurial_update.pdf}} % \end{center} % \caption{CbConGCC リポジトリの管理(左:本家GCC 中央:独自のGCCリポジトリ 右:CbConGCC リポジトリ)} % \label{fig:mercurial} %\end{figure} %\begin{figure}[htpb] % \begin{center} %\scalebox{0.33}{\includegraphics{figure/gcc-repo.pdf}} % \end{center} % \caption{当研究室で管理している GCC リポジトリのグラフ} % \label{fig:gcc-repo} %\end{figure} \subsection{リポジトリ管理方法の評価} 上記のリポジトリ管理方法を用いて GCC-4.5.0 から GCC-4.6.0 へのアップデートを行った. この手法を用いらない場合は手動で diff を行い差分を探すことになる. だが, 上記の手法ではほとんどの差分の適用を Mercurial が自動で行ってくれた. 手動で差分を直したのは CbC の実装を行ったファイルだけで済んだ. CbC 実装の為のコードが入り, かつ移動されたファイルがあり, それらだけは 2 つのバージョンを並べて手動で diff を行うことになったが, ファイル自体が少ない為 差分の適応はすぐに行えた. %\begin{figure}[h] %\begin{figure}[b] % \begin{center} %\includegraphics[scale=0.3]{./figure/graph_gray.pdf} % \end{center} % \caption{CbC-GCC リポジトリのグラフ(一部)} % \label{fig:cbc-repo} %\end{figure} \section{まとめと今後の課題} 今回 CbC コンパイラを GCC-4.6 へとアップデートを行った. アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った. だが, 環境付き継続等未だ幾つかの問題を残している. typedefrec, selftype といった新たに実装を行いたい機能もでてきた. また, 当研究室ではコードセグメントとデータセグメントを用いた並列・分散プログラミングを提案している. データセグメントは C における構造体のようにデータをまとめて取り扱えるものであり、コードセグメント(タスク)がデータの入出力時に使用する. タスクの並列動作をサポートするためにタスクを管理するエンジンを実装するにあたり、それらも踏まえて CbC-GCC は実装を行っていかなくてはならない. \nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals} \bibliographystyle{junsrt} \bibliography{cbc.bib} %今後はこれらを考えて CbC-GCC の実装を行っていく予定である. %また, 当研究室では CbC を用いてコードセグメントとデータセグメントを組み合わせたプログラミングスタイルを %提案している. %また, CbC を Google Go 言語での実装等の研究も行う予定である. \newpage \section{付録}\label{chp:conv1} 以下はコンパイラのベンチマークで用いたプログラム conv1 である. \subsection{conv1.c} \begin{small} \lstinputlisting [label=code:conv1, tabsize=4, frame=single, breaklines] {source/conv1.c} \end{small} \end{document} \ No newline at end of file diff -r fb5994f49abd -r 7ed352ddae10 presen/index.html --- a/presen/index.html Sat Jan 07 09:16:58 2012 +0900 +++ b/presen/index.html Sat Jan 07 12:52:25 2012 +0900 @@ -569,7 +569,7 @@