\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 の関数の構文と同じで, 型に ``\verb+__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 において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
しかし, 戻り値を持たないコードセグメントではスタックに値を積んでいく必要が無く, スタックは変更されない.
このようなスタックに値を積まない継続,つまり呼び出し元の環境を持たない継続を軽量継続と呼び,軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

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

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

\subsection{goto シンタックスの追加}
通常, goto のシンタックスは ``goto ラベル名;" となっている.CbC ではこれに加え,``goto codeSegment();"の形でコードセグメントを呼び出すシンタックスを追加する必要がある.

\subsection{軽量継続の実装}
軽量継続の実装は Tail Call Elimination (末尾除去) の強制によって実現する. Tail Call Elimination が行われると関数を呼び出す際に call ではなく jmp 命令を用いて移動するようになる。Tail Call Elimination は関数呼び出しの直後に処理が残っていない場合に行われる。


\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}
%また,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}).

\section{現状及び今後の課題}
今後は本稿でも述べたとおり、LLVM/clang 上での CbC コンパイラの実装を行っていく.実装後はGCC版とLLVM版のCbCコンパイラそれぞれでコンパイルしたプログラムの性能比較を行う予定である.
%また,LLVM版とGCC版でCbCコンパイラを実現するために変更を加えた箇所を比較し,どちらが実装を容易に行えるかも判別する.

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