\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{2013年11月3日}
\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)}
CbC のでは処理をコードセグメントという単位で記述し,コード間の移動に 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 (末尾除去)の強制によって実現する. これによりコードセグメント間の移動に call ではなく jmp 命令が用いられるようになる.図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻り値を funcB ではなく funcA へと返すことになる.

\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 がこの最適化を利用できる.これらのアーキテクチャでの条件を以下に示す.
%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}