# HG changeset patch # User kent # Date 1265399255 -32400 # Node ID d2999e94b97d6017030a30b9c83035e9e64fe996 # Parent 50e23a4b2f4053ece0f21665ae9aab149cd2928e add gcc. diff -r 50e23a4b2f40 -r d2999e94b97d cbc.tex --- a/cbc.tex Fri Feb 05 10:00:05 2010 +0900 +++ b/cbc.tex Sat Feb 06 04:47:35 2010 +0900 @@ -1,7 +1,9 @@ \chapter{Continuation based C (CbC)} \label{chp:cbc} -Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも上位でCよりも下位な記述言語である。 -我々は様々な視点からこのCbCを使った研究を行っている。本章ではそのCbCの + +Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも +上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを使った +研究を行っている。本章ではそのCbCの 仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。 \section{CbCの要求仕様} @@ -179,9 +181,9 @@ この環境付き継続を導入した言語はC with Continuation(CwC)と呼ばれ、Cと CbCの両方の機能をもつ言語となる。また、 C、CbCはCwCのサブセットと考え られるので（図 \ref{fig:cwc}）、CwCのコンパイラをCbCに使用する事ができ -る。これまでに実装されてきたCbCのコンパイラは1章で説明したmicro-c、gcc -共に実際にはCwCのコンパイラとして実装されている。すなわち、Cの関数や -forなどを使うことができ、mcでは環境付き継続も実装されている。 +る。 +これまでに実装されてきたCbCのコンパイラは実際にはCwCのコンパイラとして +実装されている。 \begin{figure}[htpb] \begin{center} @@ -195,11 +197,13 @@ \subsection{環境付き継続}\label{ssec:gotowithenv} 環境付き継続を用いる場合、Cの関数からコードセグメントへ継続する際に \_\_returnという名前で表される特殊なコードセグメントポインタを渡す。コ -ード\ref{code:cbcreturn}参照。 +ード\ref{code:cbcreturn}では関数\verb|funcB|からコードセグメント +\verb|cs|に継続する際に\verb|__return|を渡している。 継続先のコードセグメントでは渡されたコードセグメントポインタへ継続する 事で元のCの環境に復帰することが可能となる。 -ただし復帰先は\_\_returnを参照した関数が終了する位置である。 -図\ref{fig:cbcreturn}にこの様子を表した。 +ただし復帰先は\_\_returnを参照した関数が終了する位置である。このプログ +ラムの例では、関数\verb|funcA|からは\verb|funcB|が正常に終了したように +見える。図\ref{fig:cbcreturn}にこの様子を表した。 \lstinputlisting [caption=\_\_returnの例, label=code:cbcreturn, @@ -262,14 +266,23 @@ -\section{gccベースコンパイラの現時点の問題点} +\section{CbCコンパイラの現状と問題点} \label{sec:cbc-problem} -当初CbCのコンパイラはmicro-cをベースとしたものが使われていた。しかしよ -り多くのアーキテクチャや最適化機能などの要望により、 2008年の研究をも -って\bibref{kent-2008}GCCによる実装が行われた。この研究によりコードセグメント、継 -続制御構造などは実装され、一通りのCbCプログラムのコンパイルが可能とな -った。 +\subsection{micro-cとGCC} + +CbCのコンパイラには二つの実装が用意されている。 +一つは2000年に当研究室の河野らにより開発された、micro-cというCのコンパ +イラをベースとしたものである。こちらは現在安定して動作しており、アーキ +テクチャは PowerPC, x86, MIPS, ARMなどに対応している。 +もう一つは2008年に開発された、GCCをベースとしたコンパイラである。 +micro-cはバグも少なく安定しているのだが、GCCは元より豊富な最適化機構や +多数のアーキテクチャをサポートしており、その要望により開発された。 + +\subsection{GCCベースコンパイラの問題点} + +この時の実装でコードセグメント、継続制御構造などは実装され、一通りの +CbCプログラムのコンパイルが可能となった。 しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制 御構造の実装方法の影響により、いくつかの問題が発生している。 @@ -322,10 +335,10 @@ \item x86での継続制御のオーバヘッド - mc実装ではx86アーキテクチャでのコードセグメント継続の際には引数を - レジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォルト - では全ての引数をメモリに格納する。コードセグメントは関数をベースに - 作られているため、このABIに引きずられ実効速度に影響をもたらす。 + micro-c実装ではx86アーキテクチャでのコードセグメント継続の際には引 + 数をレジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォ + ルトでは全ての引数をメモリに格納する。コードセグメントは関数をベー + スに作られているため、このABIに引きずられ実効速度に影響をもたらす。 \end{itemize} @@ -333,7 +346,7 @@ これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ ていた。 %特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。 -次章ではこれらの問題の解決を行う。 +\ref{chp:impl}章ではこれらの問題の解決手法を説明する。 diff -r 50e23a4b2f40 -r d2999e94b97d implementation.tex --- a/implementation.tex Fri Feb 05 10:00:05 2010 +0900 +++ b/implementation.tex Sat Feb 06 04:47:35 2010 +0900 @@ -2,14 +2,18 @@ \chapter{GCCにおける実装・改善} \label{chp:impl} -前章で洗い出したGCCでの問題点の改善を行う。 +この章では、GCCにおけるCbCコンパイラの実装方法と、 \ref{chp:cbc}章で洗 +い出したGCCでの問題点の改善を行う。 実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。 +このcc1はCからアセンブラへ変換を行う純粋なコンパイラとして実行されるプ +ログラムである。このcc1をCbCの構文解析に対応させる。 + 過去の研究においてはGCCのバージョン4.2.3が用いられた。現在はGCCのリリ ースに並ぶ形で4.4.2（2010年1月時）を用いている。 \section{過去の研究における実装部分} -今回の実装においての予備知識として、過去の研究での実装部分であるコード +今回の改善においての予備知識として、過去の研究での実装部分であるコード セグメントと軽量継続がどのように実装されたかを簡単に説明する。 \subsection{コードセグメントの実装} @@ -36,8 +40,7 @@ -\subsection{軽量継続の実装} -\label{ssec:impl-goto} +\subsection{軽量継続の実装} \label{sec:impl-goto} % return somesegment(); % expand_call() @@ -226,12 +229,11 @@ という擬似変数を使う。この変数の値を継続先のコードセグメントに渡すこと で、そのコードセグメントから関数の環境へ復帰することを可能にする。 渡された\verb|__return|の値は、コードセグメント側からは他のコードセグ -メントと識別できる必要はない。 +メントと区別する必要はない。 この環境付き継続にもちいる\verb|_ _return|擬似変数の実装には様々な方法 が考えられるが、今回の実装には内部関数をもちいることにした。内部関数は -GCCによるCの拡張機能である -\cite{bib:nestedfunc}。 +GCCによるCの拡張機能である\cite{bib:nestedfunc}。 \subsubsection{GCCにより追加されるコード} 環境付き継続で使う\verb|__return|変数は特殊なコードセグメントへのポイ @@ -292,12 +294,12 @@ \subsubsection{関数からの継続} -ここで関数内から継続を行ったときの弊害がでてくる。 -\ref{ssec:impl-goto}節の実装では関数からの継続は考慮していない。通常の +ここで軽量継続の実装にtailcallを用いたことの弊害がでてくる。 +\ref{sec:impl-goto}節の実装では関数からの継続は考慮していない。通常の 継続の際は現コードセグメントのもつ引数は保持しないため、直接継続しよう とすると、その関数やその関数を呼び出した関数の持つ環境（スタック）を破 -壊してしまう（\pageref{fig:interfacestack} -ページ、図\ref{fig:interfacestack}）。 +壊してしまう（\pageref{fig:gotostack} +ページ、図\ref{fig:gotostack}）。 この問題を回避するため、関数からの継続に限り、スタックを拡張し関数の環 境を保持する手法をとった。 @@ -315,6 +317,11 @@ れない。このためこれまでPowerPCでの間接継続はコンパイルエラーで実行で きなかった。 +間接呼び出しのtailcallは専用のRTL表現がある。 +PowerPCで問題となるのは、このRTLからアセンブラへの変換が定義されていな +いことである。この問題に対処するため、PowerPCアーキテクチャにおけるmc +を記述する。 + \subsubsection{RTLとMachine Description} GCCは構文木からRTLと呼ばれる中間コードを生成する。この中間コードは一部 を除いてアーキテクチャ依存性はなく、どのアーキテクチャでもほぼ同じにな @@ -328,12 +335,12 @@ ースコードがコンパイルされてGCCの一部となる。 RTLの例としてこの問題となっている間接継続を表すS式をコード -\ref{code:rtl-example}に示す。 +\ref{code:rtl-indirecttailcall}に示す。 \lstinputlisting [caption=PowerPCにおける間接継続のRTL, - label=code:rtl-example, + label=code:rtl-indirecttailcall, language=Lisp] - {sources/rtl-example.rtl} + {sources/rtl-indirecttailcall.rtl} % TODO: RTLの説明も入れるか？ @@ -350,10 +357,14 @@ 同じくmdの例として、この問題となったRTL用の変換規則を定義したものをコ ード\ref{code:md-example}に示す。 \lstinputlisting - [caption=\ref{code:rtl-example}の変換規則, - label=code:md-example, + [caption=\ref{code:rtl-for-indirect}の変換規則, + label=code:md-for-indirect, language=Lisp] - {sources/md-example.md} + {sources/md-for-indirect.md} +このコードの2番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似 +ていることがわかる。これは変換対象としてこの型に合うものに制限するため +である。 + ここでは出力するアセンブラとして\verb|b%T0|が使われている。 \verb|%T0|はレジスタ名に置き換えられる部分である。このアセンブラは最終 的には\verb|bctr|と置き換えられてPowerPCのアセンブラとして出力される。 diff -r 50e23a4b2f40 -r d2999e94b97d introduction.tex --- a/introduction.tex Fri Feb 05 10:00:05 2010 +0900 +++ b/introduction.tex Sat Feb 06 04:47:35 2010 +0900 @@ -38,10 +38,10 @@ 試みられているが、完全な排除は難しい。数学的なアプローチから無矛盾を証 明する技術の研究も進んでいるが、現在のスタックベースのプログラミングは 状態数が膨大になり、実用化された例は少ない。しかしマルチコアの台頭によ -り並列プログラミングの必要性も高まっており、これからより検証の必要性が -増すと考えられる。 +り並列プログラミングの必要性も高まっており、今後より検証の必要性が増す +と考えられる。 -ハードウェアの進化、数学的検証にソフトウェアが対応するためにはこれまで +ハードウェアの進化や数学的検証にソフトウェアが対応するためにはこれまで とは違う新たな視点を持ったプログラミング言語が望ましい。 しかし既存のソフトウェアやシステムは膨大な数に上り、これらを新しい言語 に書き換えるのは無理がある。新しい言語は古い言語との互換性が必須である。 diff -r 50e23a4b2f40 -r d2999e94b97d master_paper.tex --- a/master_paper.tex Fri Feb 05 10:00:05 2010 +0900 +++ b/master_paper.tex Sat Feb 06 04:47:35 2010 +0900 @@ -10,8 +10,8 @@ \usepackage{caption} % TODO: -% captionパッケージはtouch ragged2e.sty everysel.sty -% をしておかないとフォントが破滅する +% captionパッケージは空のファイル ragged2e.sty everysel.sty +% を作っておかないとフォントが破滅する \usepackage{subfig} % なかでcaptionを呼び出してる @@ -40,6 +40,8 @@ showstringspaces=false,% frameround=ftft,% frame=trBL, + framextopmargin=2pt, + framexbottommargin=3pt, emphstyle=\underbar, %frame=tRBl, %numbers=left,stepnumber=1,numberstyle=\footnotesize% diff -r 50e23a4b2f40 -r d2999e94b97d sources/cbcreturn.cbc --- a/sources/cbcreturn.cbc Fri Feb 05 10:00:05 2010 +0900 +++ b/sources/cbcreturn.cbc Sat Feb 06 04:47:35 2010 +0900 @@ -1,4 +1,4 @@ -__code cs(RET_FUNC ret) +code cs(RET_FUNC ret) { goto ret(2); } diff -r 50e23a4b2f40 -r d2999e94b97d sources/rtl-example.rtl --- a/sources/rtl-example.rtl Fri Feb 05 10:00:05 2010 +0900 +++ b/sources/rtl-example.rtl Sat Feb 06 04:47:35 2010 +0900 @@ -1,13 +1,2 @@ -(call_insn/j 25 24 0 (parallel [ - (call (mem:SI (reg/f:SI 129) [0 S4 A8]) - (const_int 256 [0x100])) - (use (const_int 0 [0x0])) - (use (reg:SI 130)) - (return) - ]) -1 (nil) - (nil) - (expr_list:REG_DEP_TRUE (use (reg:SI 6 r6)) - (expr_list:REG_DEP_TRUE (use (reg:SI 5 r5)) - (expr_list:REG_DEP_TRUE (use (reg:SI 4 r4)) - (expr_list:REG_DEP_TRUE (use (reg:SI 3 r3)) - (nil)))))) +(mult:SI (reg:SI 58) + (const_int 20 [0x14]))