# HG changeset patch # User Kaito Tokumori # Date 1383724527 -32400 # Node ID fdf2da6ac28620fe487f562a50d0cb1564482f2c # Parent 35c91ea40640043bec71e4cf089fe052330abfe1 check diff -r 35c91ea40640 -r fdf2da6ac286 2013_mid.tex --- a/2013_mid.tex Tue Nov 05 20:24:03 2013 +0900 +++ b/2013_mid.tex Wed Nov 06 16:55:27 2013 +0900 @@ -28,16 +28,16 @@ \thispagestyle{fancy} \section{研究目的} -当研究室では、プログラムをコードセグメント、データセグメントという単位を用いて書くという手法を提案している。その手法を用いてプログラミングを行うのに最適な言語として Continuation based C (以下CbC) を開発しており、これは C の下位の言語になる。CbC においてコードセグメント間の移動は goto 文を用いた軽量継続によって行われ、Tail Call Elimination という最適化の強制によってこれが実現される。 -本研究では, CbC のコンパイラ開発を LLVM/clang をベースに行う。 +当研究室では,プログラムをコードセグメント,データセグメントという単位を用いて書くという手法を提案している.その手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) を開発しており,これは C の下位の言語になる.CbC においてコードセグメント間の移動は goto 文を用いた軽量継続によって行われ,Tail Call Elimination という最適化の強制によってこれが実現される. +本研究では, CbC のコンパイラ開発を LLVM/clang をベースに行う. \section{Continuation based C (CbC)} -CbC のでは C の関数の代わりにコードセグメントを用いて処理を記述し,コードセグメント間の移動に goto (軽量継続)を用いる. +CbC のプログラムでは C の関数の代わりにコードセグメントを用いて処理を記述し,コードセグメント間の移動に goto (軽量継続) を用いる. 構文は C と同じであるが, ループ制御や関数コールが取り除かれる. \subsection{継続 (goto)} -コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる. -コードセグメントへの移動には二種存在する。直接コードセグメントに移動する場合は ``goto'' の後にコードセグメント名と引数を並べて記述し、(もういっこの。)記述する. +コードセグメントの記述は C の関数の構文と同じで, 型に ``\_\_code'' を使うことで宣言できる. +コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える. この goto による処理の遷移を継続と呼ぶ. 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. @@ -55,77 +55,78 @@ しかし, 戻り値を持たないコードセグメントではスタックに値を積んでいく必要が無く, スタックは変更されない. このようなスタックに値を積まない継続,つまり呼び出し元の環境を持たない継続を軽量継続と呼び,軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. +\subsection{データセグメント (data segment)} +コードセグメントが処理の単位であるのに対し,データセグメントは処理に用いるデータを表す. + +%CbC においてデータセグメントは未実装であり,どのように記述するかも考案されていない.過去に開発された GCC 版の CbC コンパイラでも未実装の機能であり,今後実装する必要があるものの一つである. + \section{LLVM/clang 3.4 上での実装} ここではLLVM/clang 3.4 上でどのように CbC コンパイラを実装するかについて述べる. %CbC コンパイラを実現するには以下の機能を実装する必要がある. %\begin{itemize} -%\item ``\_\_code"のパース +%\item ``\_\_code''のパース %\item goto シンタックスの追加 %\item 軽量継続の実装 %\item 環境付き継続の実装 %\end{itemize} -\subsection{``\_\_code"のパース} -予約語は clang/include/clang/Basic/TokenKinds.def で登録する.登録する予約語が C ,あるいは C++ のどの規格で使用されるものかもここで記述し,これにより clang のパーサーが``\_\_code"をkw\_\_\_codeとして認識するようになる. +\subsection{``\_\_code''のパース} +``\_\_code''型をコンパイラに認識させるために,予約語に登録する必要がある.予約語は clang/include/clang/Basic/TokenKinds.def で登録する.登録する予約語が C ,あるいは C++ のどの規格で使用されるものかもここで記述し,これにより clang のパーサーが``\_\_code''を``kw\_\_\_code''として認識するようになる. \subsection{goto シンタックスの追加} -通常, goto のシンタックスは ``goto ラベル名;" となっている.CbC ではこれに加え,``goto codeSegment();"の形でコードセグメントを呼び出すシンタックスを追加する必要がある. +%通常, goto のシンタックスは``goto ラベル名;''となっている.CbC ではこれに加え,``goto codeSegment();''の形でコードセグメントへ移動するシンタックスを追加する必要がある.``goto''が読み込まれた時の処理は clang/lib/Parse/ParseStmt.cpp で行われるのでここを書き換えた. +通常の goto シンタックスに加え, CbC ではコードセグメントへ移動するためのシンタックスが必要である.``goto''が読み込まれた時の処理は clang/lib/Parse/ParseStmt.cpp で行われるのでここを書き換えた. +%後述する Tail Call Elimination の条件の一つである関数直後に return 文があるという条件も、ここで自動的に return 文を挿入することによって満たしている。 \subsection{軽量継続の実装} -軽量継続の実装は Tail Call Elimination (末尾除去) の強制によって実現する. Tail Call Elimination が行われると関数を呼び出す際に call ではなく jmp 命令を用いて移動するようになる。Tail Call Elimination は関数呼び出しの直後に処理が残っていない場合に行われる。 - +軽量継続の実装は Tail Call Elimination (末尾除去) の強制によって実現する. Tail Call Elimination が行われると関数を呼び出す際に call ではなく jmp 命令を用いて移動するようになる.Tail Call Elimination が行われるのは関数呼び出しの直後に処理が残っていない場合であり,その関数に戻る必要がないので jmp 命令を用いて移動することが可能なのである. \subsection{Tail Call Elimination の強制} -LLVM で Tail Call Elimination を行う場合,対象となる関数の isTailCall というフラグを true にした上で, アーキテクチャ によって異なるいくつかの条件を満たす必要がある.現在は x86/x86-64 と PowerPC がこの最適化を利用できる.これらのアーキテクチャでの条件を以下に示す. -%isTailCall を true にする処理は TailCallElim という Pass によって行われる.通常この Pass は Optimize level が 2 以上の場合にのみ有効化されるが, コード内に``\_\_code"が含まれる場合にはこの Pass を有効化し,コードセグメントに対してのみ処理を行うように改変した. -\begin{itemize} -\setlength{\itemsep}{0mm} -\item caller と callee の calling convention が fastcc, cc10, cc11 のいずれかである. -\item 関数呼び出しが return の直前に行われており, void 型である. -\item 可変長引数リストを使用していない. -\item tailcallopt が有効になっている. -\item byval parameter を使用していない. -\item PIC/GOT を用いる場合,visibility が hidden か protected である必要がある. -\end{itemize} +LLVM で Tail Call Elimination を行うためには,関数に Tail Call Flag を set したうえで複数の条件をクリアしなければならない.本研究では以下の実装を行うことで Tail Call Elimination の強制を実装した. +\subsubsection{Tail Call Flag} +Tail Call Elimination を行うにはまず Tail Call Flag を set する必要がある.これを set する処理は TailCallElim という Pass によって行われる.通常この Pass は optimize level が 2 以上の場合にのみ有効化されるが, コード内に``\_\_code''が含まれる場合にはこの Pass を有効化し,コードセグメントに対してのみ処理を行うように改変した. +\subsubsection{関数の型と呼び出し直後の return} +Tail Call Elimination 対象の関数は呼び出し直後に return 文があり、さらに void 型である必要がある。これらの条件をコードセグメントが呼び出されたときに、直後に return 文を挿入する処理の追加と、コードセグメントを``void''型として扱うことによって満たした。 + +\subsubsection{tailcallopt の有効化と calling convention} +tailcallopt オプションの有効化も Tail Call Elimination を行うために必要である. tailcallopt オプションは LLVM 内部では GuaranteedTailCallOpt という変数で管理されており,通常コンパイルオプションで指定することで有効化されるが,コード内に``\_\_code''が含まれる場合にはこれを有効化するように改変した.また,GuaranteedTailCallOpt が true の場合,calling convention がチェックされ,指定されたものでない場合には Tail Call Elimination が行われない.そこで,コードセグメントの calling convention を全て FastCC に変更するよう改変することで解決した. +\subsubsection{可変長引数リスト} +可変長引数リストを持つ関数には Tail Call Elimination を行えないという制限がある.CbC では可変長引数リストの機能を利用したい場合,データセグメントを用いることになる予定である.したがってコードセグメントは可変長引数リストを用いる必要はない.可変長引数リストを持つコードセグメントがあった場合はそれを通常の関数呼び出しに変更する. + +%対象となる関数に Tail Call Eliminaition を行うフラグの set を行うだけでなく,アーキテクチャ によって異なるいくつかの条件を満たす必要がある.現在は x86/x86-64 と PowerPC がこの最適化を利用できる.これらのアーキテクチャでの条件を以下に示す. + +%\begin{itemize} +%\setlength{\itemsep}{0mm} +%\item caller と callee の calling convention が fastcc, cc10, cc11 のいずれかである. +%\item 関数呼び出しが return の直前に行われており, void 型である. +%\item 可変長引数リストを使用していない. +%\item tailcallopt が有効になっている. +%\item byval parameter を使用していない. +%\item PIC/GOT を用いる場合,visibility が hidden か protected である必要がある. +%\end{itemize} %また,X86/X86-64 の場合には Sibling call optimization というものがあり,いくつかの条件を満たすことで Tail Call Elimination と同様の最適化を受けることができるが, 別アーキテクチャのサポートも考え, Tail Call Elimination を用い, Sibling call optimization は使用しない. + \subsection{環境付き継続} -CbC には通常の C の関数からコードセグメントに継続する際, - その関数から値を返す処理への継続を得ることができる. -これを環境付き継続といい,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 版の CbC コンパイラでは内部関数を用いることで環境付き継続を実現している.この他には setjmp , longjmp を用いた実装案, Exception を用いた実装案,LLVM IRを用いた実装案がある. - -%GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. -%戻り値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(図\ref{fig:ret_val_code}). +CbC と C との違いは環境を持つか持たないかである.C から CbC に移る際には環境を破棄するだけで良いが,環境を破棄した CbC から C に移ることは不可能である.これを可能にする機能が環境付き継続である.環境付き継続は C との互換性をもたせるのに必須であるが,LLVM 版のコンパイラでは未実装の機能である. \section{現状及び今後の課題} -今後は本稿でも述べたとおり、LLVM/clang 上での CbC コンパイラの実装を行っていく.実装後はGCC版とLLVM版のCbCコンパイラそれぞれでコンパイルしたプログラムの性能比較を行う予定である. -%また,LLVM版とGCC版でCbCコンパイラを実現するために変更を加えた箇所を比較し,どちらが実装を容易に行えるかも判別する. +%現在までに行った実装は,LLVM IR に手を加えていない. +今後は本稿で述べたとおり,未実装である環境付き継続の実装を行う. +環境付き継続の実装案には複数あり, 例えばGCC 版の CbC コンパイラでは内部関数を用いることで環境付き継続を実現している.この他には setjmp , longjmp を用いた実装案,Exception を用いた実装案,LLVM IRを用いた実装案がある. +また,データセグメント部分のシンタックスの考案,コンパイラへの実装も行う予定である. \begin{thebibliography}{9} -\bibitem{1}与儀 健人. ``組み込み向け言語Continuation based C の GCC 上の実装". 琉球大学 情報工学科 学位論文(修士), 2008 +\bibitem{1}与儀 健人. ``組み込み向け言語Continuation based C の GCC 上の実装''. 琉球大学 情報工学科 学位論文(修士), 2008 \vspace{-3mm} -\bibitem{2}大城 信康,河野 真治. ``Continuation based C の GCC 4.6 上の実装について". 第53回プログラミング・シンポジウム, 2011 +\bibitem{2}大城 信康,河野 真治. ``Continuation based C の GCC 4.6 上の実装について''. 第53回プログラミング・シンポジウム, 2011 \vspace{-3mm} -\bibitem{3}LLVM 3.4 documentation.\\ ``http://llvm.org/docs/index.html" +\bibitem{3}LLVM 3.4 documentation.\\ ``http://llvm.org/docs/index.html'' \vspace{-3mm} -\bibitem{4}``Clang" CFE Internals Manual - Clang 3.4 documentation.\\ ``http://clang.llvm.org/docs/InternalsManual.html" +\bibitem{4}``Clang'' CFE Internals Manual - Clang 3.4 documentation.\\ ``http://clang.llvm.org/docs/InternalsManual.html'' \vspace{-3mm} -\bibitem{5}LLVM API Documentation.\\ ``http://llvm.org/docs/doxygen/html/index.html" +\bibitem{5}LLVM API Documentation.\\ ``http://llvm.org/docs/doxygen/html/index.html'' \vspace{-3mm} -\bibitem{6}Clang API Documentation.\\ ``http://clang.llvm.org/doxygen/" +\bibitem{6}Clang API Documentation.\\ ``http://clang.llvm.org/doxygen/'' \vspace{-3mm} \end{thebibliography} \end{document}