\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvips]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{mediabb}
\usepackage{float}

\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{246mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Continuation based C コンパイラの LLVM 3.4 上での実装}
\author{105711B 氏名 徳森 海斗 指導教員 : 河野 真治}
%\date{}
\maketitle
\thispagestyle{fancy}

\section{研究目的}
当研究室では,プログラムをコードセグメント,データセグメントという単位を用いて書くという手法を提案している.その手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) を開発しており,これは C の下位の言語になる.CbC においてコードセグメント間の移動は goto 文を用いた軽量継続によって行われ,Tail Call Elimination という最適化の強制によってこれが実現される.
本研究では, CbC のコンパイラ開発を LLVM/clang をベースに行う.

\section{Continuation based C (CbC)}
CbC のプログラムでは C の関数の代わりにコードセグメントを用いて処理を記述し,コードセグメント間の移動に goto (軽量継続) を用いる.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

\subsection{継続 (goto)}
コードセグメントの記述は C の関数の構文と同じで, 型に ``\_\_code'' を使うことで宣言できる.
コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える.
この goto による処理の遷移を継続と呼ぶ.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/codesegment.pdf}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}

\subsection{コードセグメント (code segment)}
コードセグメントは C の関数と異なり戻り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
しかし, 戻り値を持たないコードセグメントではスタックに値を積んでいく必要が無く, スタックは変更されない.
このようなスタックに値を積まない継続,つまり呼び出し元の環境を持たない継続を軽量継続と呼び,軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

\subsection{データセグメント (data segment)}
コードセグメントが処理の単位であるのに対し,データセグメントは処理に用いるデータを表す.

%CbC においてデータセグメントは未実装であり,どのように記述するかも考案されていない.過去に開発された GCC 版の CbC コンパイラでも未実装の機能であり,今後実装する必要があるものの一つである.

\section{LLVM/clang 3.4 上での実装}
ここではLLVM/clang 3.4 上でどのように CbC コンパイラを実装するかについて述べる.
%CbC コンパイラを実現するには以下の機能を実装する必要がある.
%\begin{itemize}
%\item ``\_\_code''のパース
%\item goto シンタックスの追加
%\item 軽量継続の実装
%\item 環境付き継続の実装
%\end{itemize}

\subsection{``\_\_code''のパース}
``\_\_code''型をコンパイラに認識させるために,予約語に登録する必要がある.予約語は clang/include/clang/Basic/TokenKinds.def で登録する.登録する予約語が C ,あるいは C++ のどの規格で使用されるものかもここで記述し,これにより clang のパーサーが``\_\_code''を``kw\_\_\_code''として認識するようになる.

\subsection{goto シンタックスの追加}
%通常, 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 が行われるのは関数呼び出しの直後に処理が残っていない場合であり,その関数に戻る必要がないので jmp 命令を用いて移動することが可能なのである.

\subsection{Tail Call Elimination の強制}
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 に移る際には環境を破棄するだけで良いが,環境を破棄した CbC から C に移ることは不可能である.これを可能にする機能が環境付き継続である.環境付き継続は C との互換性をもたせるのに必須であるが,LLVM 版のコンパイラでは未実装の機能である.

\section{現状及び今後の課題}
%現在までに行った実装は,LLVM IR に手を加えていない.
今後は本稿で述べたとおり,未実装である環境付き継続の実装を行う.
環境付き継続の実装案には複数あり, 例えばGCC 版の CbC コンパイラでは内部関数を用いることで環境付き継続を実現している.この他には setjmp , longjmp を用いた実装案,Exception を用いた実装案,LLVM IRを用いた実装案がある.
また,データセグメント部分のシンタックスの考案,コンパイラへの実装も行う予定である.

\begin{thebibliography}{9}
\bibitem{1}与儀 健人. ``組み込み向け言語Continuation based C の GCC 上の実装''. 琉球大学 情報工学科 学位論文(修士), 2008
\vspace{-3mm}
\bibitem{2}大城 信康,河野 真治. ``Continuation based C の GCC 4.6 上の実装について''. 第53回プログラミング・シンポジウム, 2011
\vspace{-3mm}
\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''
\vspace{-3mm}
\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/''
\vspace{-3mm}
\end{thebibliography}
\end{document}