\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 と同じであるが, ループ制御や関数コールが取り除かれる. 


コードセグメントの記述は 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}


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

\section{LLVM/clang 3. 4 上での実装}
ここではLLVM/clang 3. 4 上でどのように CbC コンパイラを実装するかについて述べる. 

\subsection{LLVM, clang について}
実装方法の前に, LLVM と clang について簡潔に記す. LLVM はコンパイラフレームワークであり, コンパイラが行う処理のうちバックエンド部分を提供する. LLVM BitCode という中間言語を持ち, それをターゲットマシンの機械語や実行可能なファイルに変換する.  


clang は C, C++, Objective-C, Objective-C++ のコンパイラのフロントエンドであり, LLVM をバックエンドとして利用する. つまりLLVM と clang を組み合わせることで, C, C++, Objective-C, Objective-C++ のコンパイラが実現される.

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

\subsection{goto シンタックスの追加}
通常の goto シンタックスに加え, CbC ではコードセグメントへ移動するためのシンタックスが必要である. ``goto''が読み込まれた時の処理は clang/lib/Parse/ParseStmt.cpp で行われるのでここを書き換えた. 

\subsection{軽量継続の実装}
軽量継続の実装は Tail Call Elimination (以下TCE) の強制によって実現する. TCE が行われると関数を呼び出す際に call ではなく jmp 命令を用いて移動するようになる. TCE が行われるのは関数呼び出しの直後に処理が残っていない場合であり, その場合, 呼び出し元の関数に戻る必要がないので jmp 命令を用いて移動することが可能なのである. 

\subsection{Tail Call Elimination (TCE) の強制}
LLVM で TCE を行うためには, 関数に Tail Call Flag を set したうえで複数の条件をクリアしなければならない. 
まず, Tail Call Flag を set する処理であるが, これは TailCallElim という Pass によって行われる. 通常この Pass は optimize level が 2 以上の場合にのみ有効化されるが, コード内に``\_\_code''が含まれる場合にはこの Pass を有効化し, コードセグメントに対してのみ処理を行うように改変した. 


次に条件をクリアする方法を述べる. TCE 対象の関数は呼び出し直後に return 文があり, さらに void 型でなければならないという条件がある. これらの条件を満たすために, まずコードセグメントの型を``void''で統一した. さらに, コードセグメントが呼び出された場合, 直後に return 文を挿入する処理の追加を行った.


tailcallopt オプションの有効化も TCE を行うために必要である. tailcallopt オプションは LLVM 内部では GuaranteedTailCallOpt という変数で管理されており, 通常コンパイルオプションで指定することで有効化される. これを, コード内に``\_\_code''が含まれる場合には自動的に有効化するように改変した. また, GuaranteedTailCallOpt が true の場合, calling convention がチェックされ, 指定されたものでない場合には TCE が行われない. そこでコードセグメントの calling convention を全て指定 calling convention の一つである FastCC に変更する処理を加えることで解決した. 


TCE は可変長引数リストを持つ関数に対して行えないという制限がある. CbC では可変長引数リストの機能を利用したい場合, データセグメントを用いることになる予定である. したがってコードセグメントは可変長引数リストを用いる必要はない. 可変長引数リストを持つコードセグメントがあった場合はそれを通常の関数呼び出しに変更する. 
\subsection{環境付き継続}
CbC の軽量継続と C 関数呼び出しとの違いは環境を持つか持たないかである. C の関数からコードセグメントに移る際には環境を破棄するだけで良いが, 環境を破棄したコードセグメントから環境を必要とする C に移ることは通常不可能である. これを可能にする機能が環境付き継続である. 環境付き継続は C との互換性をもたせるのに必須であるが, LLVM 版のコンパイラでは未実装の機能である. 

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

\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}