# HG changeset patch # User Nobuyasu Oshiro # Date 1329392542 -32400 # Node ID 124612a0f170f2d2163c662e39db7576a5bb8de2 # Parent eadfb06324728fa0d062125a42b3a54e7e5c79ce modify tex diff -r eadfb0632472 -r 124612a0f170 paper/chapter1.tex --- a/paper/chapter1.tex Tue Feb 07 19:16:31 2012 +0900 +++ b/paper/chapter1.tex Thu Feb 16 20:42:22 2012 +0900 @@ -1,10 +1,36 @@ \chapter{Continuation based C (CbC)} +CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る. +構文は C と同じであるが, ループ制御や関数コールが取り除かれる. -\section{CbC とは} +%\section{CbC とは} \subsection{コードセグメント} + \subsection{継続(goto)} +コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる. +コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える. +図\ref{fig:cs}はコードセグメント間の処理の流れを表している. + +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=100mm]{figure/codesegment.pdf} + \end{center} + \caption{コードセグメント間の継続(goto)} + \label{fig:cs} +\end{figure} + + \subsection{CbC のプログラム例} +コードセグメントは C の関数と違って戻値を持たず, 処理が終われば次のコードセグメントへと処理を移る. +C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. +だが, 戻値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない. +軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. + +ソースコード\ref{fig:factorial}は CbC で書いたプログラムの例である. +与えられた数 x の階上を計算して出力するプログラムとなっている. + +\lstinputlisting[label=src:factorial, caption=階乗を計算する CbC プログラムの例]{src/factorial.cbc} + diff -r eadfb0632472 -r 124612a0f170 paper/chapter2.tex --- a/paper/chapter2.tex Tue Feb 07 19:16:31 2012 +0900 +++ b/paper/chapter2.tex Thu Feb 16 20:42:22 2012 +0900 @@ -5,7 +5,50 @@ \subsection{cc1} \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} + \includegraphics[width=100mm]{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{SSA} +Tree SSA (Static Single Assignment) は, プログラムの中で +変数が一度しか代入されないように変換させた構文木になる. +SSA に変換することで, 様々な最適化が行いやすくなる. +こちらも GIMPLE 同様 CbC の実装では特に修正は加えていない. + + + \subsection{RTL} +Tree SSA は解析が行われた後 RTL へと変換される. +RTL はレジスタの割り当てといった低レベルの表現であり, アセンブラとほぼ同じ命令の表現を行うことができる. +プログラム内部では RTL も木構造で表される. + +CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる. diff -r eadfb0632472 -r 124612a0f170 paper/chapter3.tex --- a/paper/chapter3.tex Tue Feb 07 19:16:31 2012 +0900 +++ b/paper/chapter3.tex Thu Feb 16 20:42:22 2012 +0900 @@ -1,14 +1,289 @@ \chapter{CbC の実装} +前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. +ここからは GCC-4.6 への実装について述べていく. \section{構文の追加} -\subsection{"\_\_code"のパース} + + +\subsection{``\_\_code''のパース} +C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている. +ここに, ソースコード\ref{src:code-parse}のように \verb+__code+ 型の追加を行う. + + +\begin{lstlisting}[label=src:code-parse, caption=\_\_codeの予約後登録] +const struct c_common_resword c_common_reswords[] = + { + { "_Bool", RID_BOOL, D_CONLY }, + { "_Complex", RID_COMPLEX, 0 }, + : + /* CbC project */ + { "__code", RID_CbC_CODE, 0 }, + : +\end{lstlisting} + +\begin{lstlisting}[label=src:code-id, caption=cts\_CbC\_code の定義] +enum c_typespec_keyword { cts_none, +cts_void, +: +cts_CbC_code, +\end{lstlisting} + +\begin{lstlisting}[label=src:regi-id, caption=id の登録] +case RID_CbC_CODE: if (specs->long_p) +: +else +specs->typespec_word = cts_CbC_code; return specs; +\end{lstlisting} + + + +これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる. +次に, id を用意する. + Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される. +そこに登録するコードセグメント判定用 id ``\verb+cts_CbC_code+'' を用意する. +これは gcc/c-tree.h で定義される(ソースコード\ref{src:code-id}). +後は\verb+c_declspecs+ 構造体にこの id を登録する. + id の登録は \verb+declspecs_add_type+ 関数の中で行われる(ソースコード\ref{src:regi-id}). + +ソースコード\ref{src:regi-id} のプログラムは void 型の id 登録を元に作られている. +違うところは \verb+cts_CbC_code+ を登録するところだけである. + +読み込まれたコードは, 最後に \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする. +コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと +して登録している(ソースコード\ref{src:regi-node}). + + + +\lstinputlisting[label=src:regi-node, caption=declspecs\_add\_type 関数]{src/regi-id.c} + \subsection{gotoシンタックスの追加} + +通常 goto のシンタックスは ``goto ラベル名;'' となる. +CbC では通常の goto に加え ``goto cs(arg,...);'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある. +ソースコード\ref{src:rid-goto}は, 追加した goto のシンタックスである +(通常のシンタックスは省いてある). + + +\lstinputlisting[label=src:rid-goto, caption=goto シンタックスへの追加]{src/rid-goto.c} + +具体的にはvoid 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ +を付けた関数の Tree となっている. + +\verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については + CbC においても重要になるので後に説明する. + + \section{Tail Call elimination} +CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する. +これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する. +図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. + +funcB は jmp 命令で funcC を呼び出す. +funcC は, 戻値を funcB ではなく funcA へと返すことになる. + + + +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=70mm]{figure/continuation.pdf} + \end{center} + \caption{Tail Call Elimination} + \label{fig:continue} +\end{figure} + + + \subsection{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 については以下で詳しく説明を行う. + + \subsection{末尾最適化の矯正付与} +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{src:tail_call}:2行目). + + + + +\lstinputlisting[label=src:tail_call, caption=コードセグメントの末尾最適化の付与]{src/tail_call_flag.c} + +\verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+ + 変数があり, コードセグメントはこのフラグには初め 1 がセットされている. +コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った. +また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った. +これにより末尾最適化の強制付与がなされた. + \subsection{gotoの後にreturnの配置} +コードセグメントは GCC 内部では関数として扱われる. +Tail Call Elimination は関数呼び出しの直後に return がある場合にかかる. +その為, goto の直後に return を置く必要がある. +CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している. +ソースコード\ref{src:rid-goto}の \verb+c_finish_return+ 関数がそれにあたる. +これにより, コンパイラではソースコード\ref{src:factorial}のコードセグメント factorial0 がソースコード\ref{src:return} +として処理される. + +%ソースコード\ref{src:factorial}のコードセグメント factorial0 をソースコード\ref{src:return}の様に, goto の直後に return を +%置く必要がある.だがそれをプログラマが記述することは実用的でない. + + +\lstinputlisting[label=src:return, caption=goto の直後に return を置く]{src/return.c} + +%goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う. + + \subsection{スタックサイズの固定化} +CbC の継続では, C の関数呼び出しとは違いスタックに値が積まれていくことはない. +その為スタックサイズを固定にすることができる. +また, スタックサイズが固定な為, スタックポインタを変えずにスタックを扱うことができる. +これも CbC の1つの特徴である. +図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している. + + +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=90mm]{figure/cs_stack.pdf} + \end{center} + \caption{継続による引数のスタック格納の様子} + \label{fig:cs_stack} +\end{figure} + + + \subsection{引数の並びの上書きコピー} -\section{fastcall} +CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる. +例えばソースコード\ref{src:cs_prog_code}のような継続である. + +\begin{lstlisting}[label=src:cs_prog_code, caption=スタックの上書きが起こる継続] +__code cs_a(int a, int b) { + goto cs_b(b, a) +} +\end{lstlisting} + + +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=80mm]{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{src:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる. + + +\lstinputlisting[label=src:cbc_replace, caption=引数の一時変数へのコピー]{src/cbc_replace_arguments.c} + + +具体的には, 内部で以下の事が行われている. +\begin{itemize} +\item 引数と同じ型の一時変数を作成 +\item 一時変数に引数の値を代入 +\item 関数に渡す引数のポインタを一時変数に変更 +\end{itemize} + +Tree call は継続を行うコードセグメントを指す. +コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である. + \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた +ところへ一時変数を入れている. + + + \section{環境付き継続} +CbC には通常の C の関数からコードセグメントに継続する際, + その関数から値を戻す処理への継続を得ることができる. +これを環境付き継続という. +これらは, 以下の二種類の CbC で定義した特殊変数である. +\verb+__environment+ は, 環境を表す情報である. +\verb+__return+ は, これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ +コードセグメントである. 例えば, 図\ref{fig:env_code}のように使うと, \verb+main()+ は 1 を返す. + + +\begin{lstlisting}[label=fig:env_code, caption=\_\_return\, \_\_environment 変数の使用例] +__code c1(__code ret(int,void *),void *env) { goto ret(1,env); +} +int main() { +goto c1(__return, __environment); +} +\end{lstlisting} + +GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. +戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(ソースコード\ref{src:ret_val_code}). + + + +\lstinputlisting[label=src:ret_val_code, caption=環境付き継続を行うコード]{src/ret_val.c} + + + +\subsubsection{環境付き継続の問題} +現在環境付き継続は +このコードを GCC 内部で生成することで実現している. これは正しく動作しているが, + \verb+retval+に static を指定してしまうと, + スレッドセーフな実装でなくなる. +Thread local 変数を用いると, やはり closure が出力されてしまう. +スタックに値を確保する closure は, スタックを破棄していく CbC には向いていない. +戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず, +浮動小数点や構造体自体である可能性があり複雑である. +一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある. + + + +\section{引数の渡し方} +通常 ia32 のコードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される. +だが GCC には ia32 の引数渡しにレジスタを用いらせる機能として fastcall がある. +使えるレジスタは 2つまでだが, 継続を繰り返して行う CbC においては fastcall を使うことで速度向上が望めるはずである. + + +\subsubsection{fastcall} +C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う. +だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない. +そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う. +ソースコード\ref{src:fastcall}はコードセグメントの生成を行なっているコードである. + +\lstinputlisting[label=src:fastcall, caption=コードセグメントへのfastcall属性付与]{src/fastcall.c} + +13, 14 行目が fastcall 属性を付与している部分になる. +if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて, + warning を出すからである. + + \section{新しい構文の実装} diff -r eadfb0632472 -r 124612a0f170 paper/thesis.tex --- a/paper/thesis.tex Tue Feb 07 19:16:31 2012 +0900 +++ b/paper/thesis.tex Thu Feb 16 20:42:22 2012 +0900 @@ -4,6 +4,7 @@ \usepackage[dvipdfm]{graphicx} \usepackage{comment} \usepackage{listings,jlisting} +\usepackage{url} \input{dummy.tex} %% font \jtitle{Continuation based C コンパイラの GCC 4.6 上の実装について} @@ -11,7 +12,7 @@ \year{平成23年度} \affiliation{\center% \includegraphics[clip,keepaspectratio,width=.15\textwidth] - {images/u-ryukyu-Mark.eps}\\ + {figure/u-ryukyu-Mark.eps}\\ \vskip10mm 琉球大学工学部 \ 情報工学科} @@ -19,7 +20,7 @@ \marklefthead{% 左上に挿入 \begin{minipage}[b]{.4\textwidth} - \includegraphics[height=1zw,clip,keepaspectratio]{images/emblem-bitmap.eps} + \includegraphics[height=1zw,clip,keepaspectratio]{figure/emblem-bitmap.eps} 琉球大学卒業論文 \end{minipage}} \markleftfoot{% 左下に挿入