# HG changeset patch # User Kaito Tokumori # Date 1383650643 -32400 # Node ID 35c91ea40640043bec71e4cf089fe052330abfe1 # Parent da013b704b5a5ed0ebf34648aa8e6e3bd6cf4bcc finished to write objective diff -r da013b704b5a -r 35c91ea40640 2013_mid.tex --- a/2013_mid.tex Tue Nov 05 18:24:31 2013 +0900 +++ b/2013_mid.tex Tue Nov 05 20:24:03 2013 +0900 @@ -23,20 +23,21 @@ \begin{document} \title{Continuation based C コンパイラの LLVM 3.4 上での実装} \author{105711B 氏名 徳森 海斗 指導教員 : 河野 真治} -%\date{2013年11月3日} +%\date{} \maketitle \thispagestyle{fancy} -\section{背景及び研究目的} -現代社会においてプログラムは様々な場所で用いられ,その用途に応じて求められる要素も様々である.例えば Real-time な制御が重要視される場合には速度,組込みシステムなどのメモリが制限される環境では軽量なプログラムが求められる.軽量で高速であるという条件に最も適しているのはアセンブリ言語であるが,低レベル過ぎてわかりづらい上に,アーキテクチャへの依存性が高いため汎用的でない.当研究室ではそういった要求に応える言語として Continuation based C (以下 CbC) を提案している. -CbC のコンパイラは2001年に micro-c をベースとしたものが開発され,続いて2008年の研究により GCC ベースのものが開発された.これにより GCC の持つ最適化の恩恵を受けることに成功している.しかし、 Mac OS X の最新版である Mavericks が C コンパイラとして GCC ではなく clang を用いるようになったことや, LLVM にも GCC 同様に強力な最適化機能が存在し,さらにエラーメッセージが GCC に比べ丁寧であるという特徴を持つことから, GCC から clang に移り変わる人々も少なくない.そこで本研究では, micro-c , GCC に続く LLVM/clang ベースのコンパイラの開発を行う. +\section{研究目的} +当研究室では、プログラムをコードセグメント、データセグメントという単位を用いて書くという手法を提案している。その手法を用いてプログラミングを行うのに最適な言語として Continuation based C (以下CbC) を開発しており、これは C の下位の言語になる。CbC においてコードセグメント間の移動は goto 文を用いた軽量継続によって行われ、Tail Call Elimination という最適化の強制によってこれが実現される。 +本研究では, CbC のコンパイラ開発を LLVM/clang をベースに行う。 + \section{Continuation based C (CbC)} -CbC のでは処理をコードセグメントという単位で記述し,コード間の移動に goto (軽量継続)を用いる. +CbC のでは C の関数の代わりにコードセグメントを用いて処理を記述し,コードセグメント間の移動に goto (軽量継続)を用いる. 構文は C と同じであるが, ループ制御や関数コールが取り除かれる. \subsection{継続 (goto)} コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる. -コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える. +コードセグメントへの移動には二種存在する。直接コードセグメントに移動する場合は ``goto'' の後にコードセグメント名と引数を並べて記述し、(もういっこの。)記述する. この goto による処理の遷移を継続と呼ぶ. 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. @@ -65,23 +66,14 @@ %\end{itemize} \subsection{``\_\_code"のパース} -予約語は clang/include/clang/Basic/TokenKinds.def で登録する.登録する予約語がC,あるいはC++のどの規格で使用されるものかもここで記述し,これによりclangのパーサーが``\_\_code"をkw\_\_\_codeとして認識するようになる. +予約語は clang/include/clang/Basic/TokenKinds.def で登録する.登録する予約語が C ,あるいは C++ のどの規格で使用されるものかもここで記述し,これにより clang のパーサーが``\_\_code"をkw\_\_\_codeとして認識するようになる. \subsection{goto シンタックスの追加} 通常, goto のシンタックスは ``goto ラベル名;" となっている.CbC ではこれに加え,``goto codeSegment();"の形でコードセグメントを呼び出すシンタックスを追加する必要がある. \subsection{軽量継続の実装} -軽量継続の実装は Tail Call Elimination (末尾除去)の強制によって実現する. これによりコードセグメント間の移動に call ではなく jmp 命令が用いられるようになる.図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. -funcB は jmp 命令で funcC を呼び出す. -funcC は, 戻り値を funcB ではなく funcA へと返すことになる. +軽量継続の実装は Tail Call Elimination (末尾除去) の強制によって実現する. Tail Call Elimination が行われると関数を呼び出す際に call ではなく jmp 命令を用いて移動するようになる。Tail Call Elimination は関数呼び出しの直後に処理が残っていない場合に行われる。 -\begin{figure}[htpb] - \begin{center} -\scalebox{0.25}{\includegraphics{figure/continuation.pdf}} - \end{center} - \caption{Tail Call Elimination} - \label{fig:continue} -\end{figure} \subsection{Tail Call Elimination の強制} LLVM で Tail Call Elimination を行う場合,対象となる関数の isTailCall というフラグを true にした上で, アーキテクチャ によって異なるいくつかの条件を満たす必要がある.現在は x86/x86-64 と PowerPC がこの最適化を利用できる.これらのアーキテクチャでの条件を以下に示す.