Binary file 2014_sigos.pdf has changed

--- a/2014_sigos.tex	Mon Apr 21 19:45:57 2014 +0900
+++ b/2014_sigos.tex	Mon Apr 21 19:52:14 2014 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
%\usepackage{jtygm}
%\usepackage{mediabb}
\usepackage{float}
\lstset{
  language={C},
  basicstyle={\footnotesize\ttfamily},
  identifierstyle={\footnotesize},
  commentstyle={\footnotesize\itshape},
  keywordstyle={\footnotesize\bfseries},
  ndkeywordstyle={\footnotesize},
  stringstyle={\footnotesize\ttfamily},
  frame={tb},
  breaklines=true,
  columns=[l]{fullflexible},
  numbers=left,
  xrightmargin=0zw,
  xleftmargin=3zw,
  numberstyle={\scriptsize},
  stepnumber=1,
  numbersep=1zw,
  lineskip=-0.5ex
}

% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の LLVM/clang 3.5 上の実装について]%
	{Continuation based C の LLVM/clang 3.5 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on LLVM/clang 3.5}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{徳森 海斗\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Kaito Tokumori\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{徳森 海斗\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: kaito@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment を用いるプログラミング手法を提案している. この手法を用いるプログラミング言語として CbC の開発を行っており, これは C の下位の言語になる. 本研究では, LLVM/clang-3.5 をベースとした CbC コンパイラの実装を行い, LLVM/clang-3.5 への CbC の具体的な実装について述べる.
\end{abstract}


% 英文概要
\begin{eabstract}
We suggest a programming paradigm which use data segments and code segments. We develop CbC which is a lower language of C and uses that programming paradigm. In this study, we implement CbC compiler on LLVM/clang and introduce implemented Continuation based C Compiler on LLVM/clang-3.5.
\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

\section{研究目的}
当研究室では, プログラムを code segment, data segment という単位を用いて書くという手法を提案している. この手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) というプログラミング言語を開発しており, これは C の下位の言語にあたる. CbC においてコードセグメント間の処理の移動は goto 文を用いた軽量継続によって行われ, これは Tail Call Elimination というコンパイラの持つ最適化の強制によって実現される. CbC では継続前の code segment に戻ることはなく, 状態遷移ベースのプログラミングを行うのに適しており, これは OpenCL, CUDA, そして Cerium といった並列開発環境を用いたプログラムの記述に向いている. この他にも meta code segment, meta data segment といったメタレベルの単位を用意することで柔軟なメタプログラミングを可能にする, データと処理を分離し並列度を高めるといった目的を持つ.\\
　これまでに開発された CbC のコンパイラは Micro-C をベースにしたものと GCC をベースにしたものの二種がある.
　GCC 上に CbC コンパイラを実装した理由の一つに, 実装時の UNIX 環境における コンパイラの標準が GCC であったからというものがあった. しかし, Mac OS X の最新版である Mavericks では GCC の代わりに LLVM/clang が用いられるようになり, 環境が変わりつつあることがわかる. 
このれらのことから, LLVM/clang を用いて CbC をコンパイルできるのが良いという考えが生じた. 本研究では LLVM/clang 上に CbC コンパイラの実装を行う.
 
\section{Continuation based C (CbC)}
CbC では C の関数の代わりに code segment を用いて処理を記述し,  code segment 間の移動に goto を用いる. 
構文は C と同じであるが, 関数呼び出しは goto を用いた継続に, ループ制御は再帰的な継続に置き換えられる.

code segment の記述は C の関数の構文と同じで, 型に \_\_code を使うことで宣言でき, code segment 間の移動は goto の後に code segment 名と引数を並べて記述することで行える. 
この goto による処理の遷移を継続と呼ぶ. 
%図\ref{fig:cs}は code segment 間の処理の流れを表している. 



code segment は C の関数と異なり戻り値を持たず, 必要な値は継続の際に次の code segment へ引数として渡す.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. 
しかし, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無く, スタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. \\
　以下の図\ref{fig:factorial}に示されたプログラムは与えられた数値の階乗を算出する CbC プログラムであり, 図\ref{fig:cs}はこのときの code segment 間の処理の流れを表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/factorial.pdf}}
  \end{center}
  \caption{階乗を計算する CbC プログラムの例}
  \label{fig:factorial}
\end{figure}

\begin{figure}[h]
  \begin{center}
\scalebox{0.53}{\includegraphics{figure/fact_codesegment.pdf}}
  \end{center}
  \caption{goto による code segment 間の継続}
  \label{fig:cs}
\end{figure}

%\section{LLVM/clang の概要}
%LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
%　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
\section{LLVM/clang}
LLVM はコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
　LLVM, clang はコンパイル対象コードを Abstract Syntax Tree (AST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブリコードに変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブリコードを出力するまでの流れを表した図である. clang はソースコードを与えられると, パーサーで構文解析を行い, AST を生成する. そしてその AST を CodeGen を用いて LLVM IR に変換する. LLVM IR をアセンブリコードに変換するまでの処理は LLVM が用いられる. LLVM IR はまず, SelectionDAGISel によって Machine Code に変換される. この時, 直接変換されるのではなく SelectionDAG という内部表現に一度変換され, 最適化された後に変換される. Machine Code は Machine code に対する最適化をかけられた後, Code Emission を通じてアセンブリコードに変換される. またこれらの内部表現の他に, clang が型を表現するのに用いる QualType というクラスについても説明する.

\begin{figure}[ht]
  \begin{center}
\scalebox{0.25}{\includegraphics{figure/clang_llvm_structure.pdf}}
  \end{center}
  \caption{clang, LLVM によるコンパイルの一連の流れ}
  \label{fig:llvmFlow}
\end{figure}

\subsection{QualType}
\label{sec:QualType}
QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (参照) 等の型情報を持つ Type オブジェクトへのポインタを持つ. QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる. また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ, それを通してポインタの指す型を知ることが可能である. 配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する. 修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる.\\
　ここで, 以下に一つの例として ``const int *'' 型に対応する QualType を表した図を示す.\\
\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.45}{\includegraphics{figure/qualType.pdf}}
 \end{center}
 \caption{const int * に対応する QualType}
 \label{fig:qual}
\end{figure}

 図\ref{fig:qual}の QualType A が const int * 型の変数, もしくは関数の持つ QualType である. これの持つ getTypePtr 関数を呼び出すことで, PointerType を得ることができる. この PointerType がどの型に対するポインタかを知るには前述したとおり getPointeeType を呼び出せば良い. そうして呼び出されたのが QualType B である. この例の QualType は const int * 型に対応するものであるので, ここで取得できた QualType B のgetTypePtr 関数を呼び出すと, 当然 IntegerType が得られる. また, この時 int には const がかかっているので, QualType B の isConstQualified 関数を呼ぶと true が返る. \\
　このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる.

\subsection{Abstract Syntax Tree (AST)}
AST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 
出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. CbC コンパイラの実装ではパーサーがこの AST を生成する部分に手を加えている.
%% それぞれの簡単な説明を以下に記す.
%% \begin{description}
%%   \item[Decl]\mbox{}\\
%%     宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
%%   \item[Stmt]\mbox{}\\
%%     一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する. 
%%   \item[Expr]\mbox{}\\
%%     一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
%% \end{description}

\subsection{LLVM IR}
LLVM IR はLLVM BitCode とも呼ばれ, リファレンスが公開されている\cite{LLVMIR}. この言語で記述したプログラムを LLVM 上で実行することも可能である. 各変数が一度のみ代入される Static Single Assignment (SSA) ベースの言語であり, LLVM 内部で扱うためのメモリ上での形式, 人が理解しやすいアセンブリ言語形式, JIT 上で実行するための bitcode 形式の三種類の形を持ち, いずれも相互変換が可能で同等なものである. ループ構文は存在せず, 一つのファイルが一つのモジュールという単位で扱われる. CbC コンパイラの実装では特に変更を行っていない.

\subsection{SelectionDAG}
SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は illegal SelectionDAG, legal SelectionDAG の順に変換されていき, その都度最適化が行われる. CbC コンパイラの実装では, ここで行われる最適化のうちの一つである Tail Call Elimination を code segment に対して強制するように変更を加えている.

\subsection{Machine Code}
Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ SSA 形式と物理レジスタを持つ non-SSA 形式がある. LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている. CbC コンパイラの実装では特に変更を行っていない.

\subsection{MC Layer}
MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. CbC コンパイラの実装では特に変更を行っていない.
% MC Layer が扱うデータ構造は複数あるが, ここでは MCInst と MCStreamer について説明する.\\
%　MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令は次に説明する MCInst と組み合わせて出力する.\\
%　MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.


\section{LLVM/clang 3.5 での CbC コンパイラの実装}
以下の節では LLVM と clang に CbC コンパイラを実装する工程について詳しく説明する. \\
　また, 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.
\subsection{clang への \_\_code 型の追加}
\label{sec:add__code}
まず最初に関数が code segment であることを示す \_\_code 型の追加を行う. そのためには \_\_code を予約語として定義する必要がある. clang では, 予約語は全て \$(CLANG)/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 図\ref{fig:TokenKinds}のように変更を加えて \_\_code を追加した. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示す. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を設定した.
%KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. また, 同時に定義されている \_\_return, \_\_environment は環境付き継続のための予約語である. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/tokenKinds.pdf}}
  \end{center}
  \caption{TokenKinds.def}
  \label{fig:TokenKinds}
\end{figure}

予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. したがって, 次に clang に \_\_code 型を認識させる必要がある.\\
　clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを図\ref{fig:Specifiers}のように編集した.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/Specifiers.pdf}}
  \end{center}
  \caption{Specifiers.h}
  \label{fig:Specifiers}
\end{figure}

これに加えてさらに\ref{sec:QualType} 節で説明した QualType が用いる Type を作らなければならない. この定義は \$(CLANG)/include/clang/AST/BuiltinTypes.def で行われているので, これを図\ref{fig:BuiltinTypes}のように編集した. ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. \_\_code 型は符号無し,有りといった性質を保つ必要はなく, また void 型が BUILTIN\_TYPE を利用していることから \_\_code 型も BUILTIN\_TYPE を使うべきだと判断した.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/BuiltinTypes.pdf}}
  \end{center}
  \caption{BuiltinTypes.def}
  \label{fig:BuiltinTypes}
\end{figure}
\\　これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. よって次に \_\_code 型を解析できるよう clang に変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われており, これが持つ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下の図\ref{fig:parse__code}ように記述を加えた. ここで重要なのは SetTypeSpecType 関数であり, これによって \_\_code 型が DeclSpec に登録される. DeclSpec は型の識別子を持つためのクラスで, 後に QualType に変換される. 
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/parse__code.pdf}}
  \end{center}
  \caption{\_\_code の parse}
  \label{fig:parse__code}
\end{figure}
\\　その他の処理について, 最初にある LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, tailcallopt を有効化するためである. LangOptions が管理するオプションは \$(CLANG)/include/clang/Basic/LangOptions.def で定義される. ここに以下の図 \ref{fig:langOpt} のような変更を加え, HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/langOpt.pdf}}
  \end{center}
  \caption{オプションの追加}
  \label{fig:langOpt}
\end{figure}

\subsection{LLVM 側での \_\_code 型の追加}
LLVM でも clang と同様に \_\_code 型の追加を行う. 型の追加を行うと言っても LLVM IR の持つ type の拡張を行うわけではなく, コンパイル時に内部で code segment であることを知るためだけに型の定義を行い, LLVM IR として出力した場合には 型は void となる. LLVM では型の情報は Type というクラスで管理しており, Type の定義は \$(LLVM)/lib/IR/LLVMContextImpl.h で行う. これに加えて TypeID の登録も行う必要があり, これは \$(LLVM)/include/llvm/IR/Type.h で定義されている. それぞれ, 以下の図\ref{fig:llvm__code}, \ref{fig:llvmType}ように編集した. \\
　さらに, \_\_CodeTy は VoidTy としても扱いたいため, 型判別に用いられる isVoidTy 関数の編集も行った. この関数は Type が VoidTy の場合に真を返す関数である. この関数を Type が \_\_CodeTy の場合にも真を返すようにした. ここで変更を行ったのは if 文の条件文のみなので, ソースコードの記載はしない.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/llvm__code.pdf}}
  \end{center}
  \caption{LLVM での \_\_code の追加}
  \label{fig:llvm__code}
\end{figure}
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/llvmType.pdf}}
  \end{center}
  \caption{LLVM での Type ID の追加}
  \label{fig:llvmType}
\end{figure}

\subsection{継続のための goto syntax の構文解析}
続いて, 継続のための新しい goto syntax の構文解析を行えるようにする. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下の図\ref{fig:ParseGoto}ように変更した. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/parseGoto.pdf}}
  \end{center}
  \caption{継続を行う goto syntax の構文解析}
  \label{fig:ParseGoto}
\end{figure}

ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下の図\ref{fig:ParseCbCGotoStmt} に示す.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/ParseGotoStmt.pdf}}
  \end{center}
  \caption{ParseGotoStmt 関数}
  \label{fig:ParseCbCGotoStmt}
\end{figure}
\\　この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する. 

\subsection{clang/LLVM 間の \_\_code 型の変換}
前述したように, clang と LLVM は別々のクラスを用いて型を管理する. そのため clang の型クラスが LLVM のものに置き換えられる箇所で \_\_code も正しく置き換えられるようにしなければならない. \$(CLANG)/lib/CodeGen/CGCall.cpp の GetFunctionType 関数が clang での関数の型を LLVM のものに変換する関数であるのでここを編集すれば良い. 具体的には以下の図\ref{fig:type} のように編集した. 図のコード中の ABIArgInfo は clang が関数にどのように引数を渡すかの情報を保持するクラスである. void 型ではこれが必ず Ignore になり, 同じことが \_\_code 型にも言える. したがって switch 文内のこの箇所だけで型のチェックを行い, \_\_code 型の時のみ LLVM 側でも \_\_code として扱えば良い.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/type.pdf}}
  \end{center}
  \caption{clang/LLVM 間の型変換}
  \label{fig:type}
\end{figure}
\subsection{Tail call eliminationの強制}
前述したように, CbC の継続の実装には Tail call elimination を用いる. Tail call elimination は最適化の一つで, これにより code segment 間の移動を call でなく jmp 命令で行うようになる. 図\ref{fig:tce}は Tail call elimination が行われた際のプログラムの処理を表している. caller は funcB を call でなく jmp で呼び出し, funcB は caller でなく main に戻る.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.30}{\includegraphics{figure/TCE.pdf}}
  \end{center}
  \caption{Tail call elimination}
  \label{fig:tce}
\end{figure}

code segment にこれを強制するためにコンパイラ側では以下の条件を満たす必要がある.
\begin{enumerate}
  \item tail フラグを立てる tail call eliminatoin pass の追加.
  \item 呼び出し元と呼び出す関数の呼び出し規約が fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかである.
%  \item 対象となる関数呼び出しが tail call である.
  \item 最適化のオプションである tailcallopt が有効になっている. 
%  \item 対象関数が可変長引数を持たない.
\end{enumerate}
　まず tail call elimination pass 追加の処理について述べる. clang は最適化の pass の追加を \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数内で行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるが, その pass の追加はこの関数から呼び出される populateModulePassManager 関数で行われる. この関数は LLVM が用意した最適化に用いられる主要な pass を追加するものである. この関数を以下の図\ref{fig:PassManager}のように変更し, 最適化レベルに関わらず追加するようにした. MPM はpass を管理するクラスのインスタンスで, add 関数によってpass の追加が可能になる. また, createTailCallEliminationPass 関数に対して引数を受け取れるように変更を加え, これによって最適化レベルが低い時に code segment 以外の関数に対して tail call elimination しないようにしている. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/PassManager.pdf}}
  \end{center}
  \caption{pass の追加}
  \label{fig:PassManager}
\end{figure}

これで code segment の呼び出しに対して tail フラグが付与されるようになった. しかし実際にはこれだけでは不十分でさらに二つの pass を追加する必要がある. 追加する pass は SROA pass と codeGenPrepare pass である. 一つ目の SROA pass は メモリ参照を減らすスカラー置換を行う pass でこれにより LLVM IR の alloca 命令を可能な限り除去できる. tail call elimination の条件に直接記されてはいないが, tail call elimination pass を用いて tail フラグを付与する場合には 呼び出し元の関数に alloca がないことが求められるのである. 二つ目の codeGenPrepare pass は名前の通りコード生成の準備を行う pass で, これを通さないと if 文を用いた時に call の直後に配置した return 文が消えてしまう. これらの pass 追加されるように変更する必要がある. SROA pass は tail call elimination と同じようにして追加される pass なので同様にして追加することができる. codeGenPrepare pass はこれら二つとは異なり, addPassesToEmitFile という関数を とおして LLVM によって追加される. この時の追加されるかどうか条件が最適化レベルに依存するものであったため, code segment を持つ場合には最適化レベルに関わらず追加するように変更した.\\
　次に, 呼び出し規約の問題を解消する. 条件を満たす呼び出し規約は fastcc, cc 10, cc 11 の三種類があるが, LLVM のドキュメントに cc 10 と cc 11 積極的に利用するのは好ましくないとあった. よって本実験では fastcc を使用する. fastcc を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. 加えて可変引数の使用が不可になり, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要があるという要件を持つ. fastcc の追加は clang が関数情報の設定処理を行っている箇所で行った. 関数情報は CGFunctionInfo というクラスを用いて管理される. 関数情報の設定は \$(CLANG)/lib/CodeGen /CGCall.cpp 内の arrangeLLVMFunctionInfo という関数で行われる. この関数に図\ref{fig:CC} に示されるコードを加えた. 変数 CC への代入文が fastcc を設定している箇所である. \\
%関数が \_\_code型の場合で, かつ可変長引数を持たない場合に呼び出し規約を fastcc に設定する. 可変長引数に関する条件を加えているのは, 可変長引数が使用されている場合には呼び出し規約を変えず tail call elimination を行わないことで通常の関数呼び出しを生成するためである.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.45}{\includegraphics{figure/CC.pdf}}
  \end{center}
  \caption{fastcc の付与}
  \label{fig:CC}
\end{figure}

最後に, tailcallopt を有効化を行う. clang と LLVM は指定されたオプションを管理するクラスを別々に持っており, clang はユーザーに指定されたオプションを LLVM に引き継ぐ処理を持つ. その処理が行われているのが \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数である. この関数のオプションの引き継ぎを行っている箇所を以下の図\ref{fig:option}のように変更する. tailcallopt は内部では GuaranteedTailCallOpt となっており, code segment を持つ場合にこれを有効化する.また, LLVM 側でも HasCodeSegment というオプションを追加している. これは先ほど述べた codeGenPrepare pass を追加する際に利用する. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.45}{\includegraphics{figure/option.pdf}}
  \end{center}
  \caption{tailcallopt の有効化}
  \label{fig:option}
\end{figure}

LLVM でのオプションの追加方法についてもここで述べておく. LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. TargetOptions クラスの中で変数を宣言するだけで追加できるので, コードは省略する.

\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメント継続する際, その関数から値を戻す処理への継続を得ることでき, これを環境付き継続と言う. こには は\_\_return, \_\_environment という特殊変数を用い. る図\ref{fig:autoCodeGenB} は環境付き継続の使用例で, この場合 caller が func を呼び出した結果得られる値 0は でなく 1 となる. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/autoCodeGenB.pdf}}
  \end{center}
  \caption{環境付き継続の使用例}
  \label{fig:autoCodeGenB}
\end{figure}

GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文で nested function を用いていた\cite{yogi:2008a}が, LLVM/clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. \_\_return, \_\_environment が宣言されると, 環境付き継続を用いる関数内での継続前に setjmp の構文が追加され, 環境を保持して継続を行うようになる. このとき, \_\_return には元の環境に戻るための code segment へのアドレスが, \_\_environment には元の環境が保持され, \_\_return の指す code segment に \_\_environment を渡して継続することで元の環境に戻ることができる. \_\_return へ継続することで元の環境に戻ることができるのは \_\_return の指す code segment が longjmp を呼び出すためである. また, 環境付き継続を行う際には戻り値を返すために継続元の関数の型をコピーしなければならないという問題があるが, clang では \ref{sec:QualType}節で述べた QualType をコピーするだけで解決する.
%% 図\ref{fig:autoCodeGenB} のコードの場合内部では図\ref{fig:autoCodeGenA} のように解釈される.

%% \begin{figure}[htpb]
%%   \begin{center}
%%     \scalebox{0.50}{\includegraphics{figure/autoCodeGenA.pdf}}
%%   \end{center}
%%   \caption{内部での解釈}
%%   \label{fig:autoCodeGenA}
%% \end{figure}

%% 追加された処理は, setjmp ヘッダのインクルード, 環境と戻り値を保持する構造体 CbC\_env の定義, 元の環境に戻るための特殊 code segment return1 の定義, これに加えて \_\_return, \_\_environment が環境付き継続の前準備を行う処理に変更される. \_\_return は内部では元の環境に戻るための code segment へのポインタの宣言文と, アドレスの代入を行う文に変換され, \_\_environment は内部では環境を保持する構造体, setjmp, longjmp が用いる jmp\_buf, 関数の戻り値となる retval の宣言文, 構造体のメンバの値の設定を行う代入文, そして特殊 code segment return1 の戻り先となる setjmp を用いた構文に変換される. また, \_\_return, \_\_environment に置き換わる処理は Statement Exprs を利用しており, これによって変数への代入も可能となっている.
%追加された処理の大まかな流れを説明すると, 環境付き継続を用いる関数は継続前に setjmp を用いて戻り先の環境を保存し, 継続を行う. このとき, 引数として渡される \_\_return には特殊 code segment return1 のアドレス, \_\_environment の持つメンバには戻り値として返される値を持つ変数のアドレスと, setjmp により保存された継続前の環境が保持されている. 元の環境に戻るための code segment は自動生成されるので, 継続先の code segment は返す戻り値と \_\_environemnt を引数として \_\_return の指す code segment を呼び出すだけで元の環境に戻れる. return1 は 構造体の持つ戻り値へのポインタを利用して戻り値を更新した後, longjmp を用いて元の環境に戻る. longjmp によって再度 setjmp の呼び出しに戻るが今回は if文内に入り, 戻り値を返す.

\section{評価と考察}
今回の実装を行った LLVM/clang 上での CbC コンパイラの評価を試みる. 評価は, コンパイルして出力されたアセンブリコードの確認と, CbC プログラムを Micro-C, GCC, LLVM/clang でコンパイルして得られたプログラムの実行速度を計測により行う. コンパイル, 計測は x86-64 アーキテクチャの Mac OS X 上で行った. なお, このときの GCC のバージョンは 4.9.0 である.
\subsection{アセンブリコードの評価}
以下の図 \ref{fig:evalCbC},\ref{fig:evalAsm} はそれぞれコンパイル前の CbC の code segment とコンパイル後, それに対応するアセンブリコードを示している. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/evalCbC.pdf}}
  \end{center}
  \caption{コンパイル前の code segment}
  \label{fig:evalCbC}
\end{figure}
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/evalAsm.pdf}}
  \end{center}
  \caption{対応するコード}
  \label{fig:evalAsm}
\end{figure}

コンパイル前のコードが持つ factorial0 への継続はコンパイル後, call ではなく jmp 命令により実装されており, このことから tail call elimination が正しく行われていることがわかる. これより, CbC コンパイラを LLVM/clang 上で実装できたことがわかる. \\

\subsection{実行速度の評価}
今回測定に使用したプログラムは conv1 と呼ばれるもので, これは Micro-C での測定や, GCC 上に CbC コンパイラを実装した際の評価にも使用されたものである.\footnote{conv1 のソースコードは付録 A に掲載する.} conv1 の行う処理は CbC の継続と計算を交互に行うもので, 引数 1 の時には CbC の継続を使用, 引数 2, 3 の時には Micro-C のための最適化が手動で施されたコードを使用するようになっている. 測定結果は表 \ref{result} に示される. 尚, GCC の最適化無しコードは, 末尾最適化の強制が原因で segmentation fault を起こすために除外している. 
\begin{table}[htpb]
  \centering
  \begin{tabular}{|l|r|r|r|} \hline
    & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
    Micro-C  & 6.875 & 2.4562 & 3.105 \\ \hline
    GCC -O2 & 2.9438 & 0.955 & 1.265  \\ \hline
    LLVM/clang -O0 & 5.835 & 4.1887 & 5.0625 \\ \hline
    LLVM/clang -O2 & 3.3875 & 2.29 & 2.5087 \\ \hline
  \end{tabular}
  \caption{Micro-C, GCC, LLVM/clang の実行速度比較 (単位 : 秒)}
  \label{result}
\end{table} 

結果についてまず LLVM/clang の最適化の有無で比較すると, 最適化を有効化した方が最適化を用いない場合より全てのケースで二倍以上速い. これは LLVM の最適化の恩恵を受けていることを示していると考えられる. Micro-C と LLVM/clang との実行速度を比較すると, 最適化なしでは LLVM/clang が遅い場合もあるが最適化を有効化すると全ての場合で LLVM/clang が速く, 最適化が大きな効果をもたらしていることがわかる. GCC と比較した場合には速度面では劣るが, LLVM/clang は最適化を無効化しても正常にプログラムが動くという点では優位である.
\section{まとめと今後の課題}
今回の実装により, LLVM/clang を CbC のコンパイルに利用できるようになった. また, 環境付き継続を GCC の拡張構文である nested function でなく, setjmp/longjmp を用いて実装することに成功した. これより, 今後 nested function をサポートしないコンパイル上に CbC コンパイラを実装する必要がでてきた場合でもこの方法により問題なく実装可能であることがわかったと言える. 

今後の課題としてまず, data segment の設計及び実装がある. code segment が処理を表す単位であるのに対し, data segment は処理に必要なデータに対応する. 我々は code segment と data segment の組みがひとつの task に相当すると考えており, data segment は, 内部表現と外部表現を持つ, priority を持ち処理順序の切り替えが可能, task の待ち合わせ制御に依存される, といった要件を満たすように設計されるべきであると考えている.\\
　二つ目の課題として, 環境付き継続の実装をアセンブリコードを用いて行うというものがある. 今回の実装では setjmp/longjmp を用いたが, インラインアセンブリを用いてアセンブリコードを直接書き出すことで速度の向上が見込めるのではないかと考えている. GCC, LLVM はそれぞれ nested function, setjmp/longjmp と言った機能を利用して環境付き継続を実装しているが, Micro-C では直接対応するアセンブリコードを出力する. Micro-Cでは環境付き継続を用いると元の環境のアドレスをベースポインタに代入する mov 命令, ベースポインタの値をスタックポインタに代入する mov 命令, そして元の環境に帰るための jmp 命令の三つで済む. この方法だと各アーキテクチャ毎に対応しなければならないという欠点はあるが, 他の実装方法よりも楽に実装でき, 速度も勝るだろうと考えている.
%以下の図\ref{MicroCAsm} の様なアセンブリコードを出力するのでこれを出力することで GCC, LLVM でも Micro-C と同等の環境付き継続が行えるようにしたい.

\nocite{yogi:2008a, nobu:2011a, LLVMIR, LLVM, clang, clangAPI}
\bibliographystyle{junsrt}
\bibliography{2014_sigos.bib}

\appendix
\section{conv1.c}
\begin{lstlisting}[frame=lrbt,label=conv1,caption={}]
#include <stdio.h>
#include <stdlib.h>
static int loop;

#if 1 // def __micro_c__
#define CC_ONLY 0
#else
#define CC_ONLY 1
#endif

#ifdef CLANG // for clang/LLVM
#define _CbC_return __return
#define _CbC_environment __environment
#endif

typedef char *stack;
#include "conv1.h"

/* classical function call case (0) */
int f0(int i) {
  int k,j;
  k = 3+i;
  j = g0(i+3);
  return k+4+j;
}

int g0(int i) {
  return h0(i+4)+i;
}

int h0(int i) {
  return i+4;
}

#if !CC_ONLY

/* straight conversion case (1) */


struct cont_interface { // General Return Continuation
  __code (*ret)(int,stack);
};

__code f(int i,stack sp) {
  int k,j;
  k = 3+i;
  goto f_g0(i,k,sp);
}

struct f_g0_interface {  // Specialized Return Continuation
  __code (*ret)(int,stack);
  int i_,k_,j_;
};

__code f_g1(int j,stack sp);

__code f_g0(int i,int k,stack sp) { // Caller
  struct f_g0_interface *c = 
    (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

  c->ret = f_g1;
  c->k_ = k;
  c->i_ = i;

  goto g(i+3,sp);
}

__code f_g1(int j,stack sp) {  // Continuation 
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  int k = c->k_;
  sp+=sizeof(struct f_g0_interface);
  c = (struct f_g0_interface *)sp;
  goto (c->ret)(k+4+j,sp);
}

__code g_h1(int j,stack sp);

__code g(int i,stack sp) { // Caller
  struct f_g0_interface *c = 
    (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

  c->ret = g_h1;
  c->i_ = i;

  goto h(i+3,sp);
}

__code g_h1(int j,stack sp) {  // Continuation 
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  int i = c->i_;
  sp+=sizeof(struct f_g0_interface);
  c = (struct f_g0_interface *)sp;
  goto (c->ret)(j+i,sp);
}

__code h(int i,stack sp) {
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  goto (c->ret)(i+4,sp);
}

struct main_continuation { // General Return Continuation
  __code (*ret)(int,stack);
  __code (*main_ret)(int,void*);
  void *env;
};

__code main_return(int i,stack sp) {
  if (loop-->0)
    goto f(233,sp);
  printf("#0103:%d\n",i);
  goto (( (struct main_continuation *)sp)->main_ret)(0,
  ((struct main_continuation *)sp)->env);
}

/* little optimzation without stack continuation (2) */

__code f2(int i,char *sp) {
  int k,j;
  k = 3+i;
  goto g2(i,k,i+3,sp);
}

__code g2(int i,int k,int j,char *sp) {
  j = j+4;
  goto h2(i,k+4+j,sp);
}

__code h2_1(int i,int k,int j,char *sp) {
  goto main_return2(i+j,sp);
}

__code h2(int i,int k,char *sp) {
  goto h2_1(i,k,i+4,sp);
}

__code main_return2(int i,stack sp) {
  if (loop-->0)
    goto f2(233,sp);
  printf("#0132:%d\n",i);
  goto (( (struct main_continuation *)sp)->main_ret)(0,
       ((struct main_continuation *)sp)->env);
}

/* little optimizaed case (3) */

__code f2_1(int i,char *sp) {
  int k,j;
  k = 3+i;
  goto g2_1(k,i+3,sp);
}

__code g2_1(int k,int i,char *sp) {
  goto h2_11(k,i+4,sp);
}

__code f2_0_1(int k,int j,char *sp);
__code h2_1_1(int i,int k,int j,char *sp) {
  goto f2_0_1(k,i+j,sp);
}

__code h2_11(int i,int k,char *sp) {
  goto h2_1_1(i,k,i+4,sp);
}

__code f2_0_1(int k,int j,char *sp) {
  goto (( (struct cont_interface *)sp)->ret)(k+4+j,sp);
}

__code main_return2_1(int i,stack sp) {
  if (loop-->0)
    goto f2_1(233,sp);
  printf("#0165:%d\n",i);
  exit(0);
  //goto (( (struct main_continuation *)sp)->main_ret)(0,
  //((struct main_continuation *)sp)->env);
}

#define STACK_SIZE 2048
char main_stack[STACK_SIZE];
#define stack_last (main_stack+STACK_SIZE)

#endif

#define LOOP_COUNT 500000000
int
main(int ac,char *av[])
{
#if !CC_ONLY
  struct main_continuation *cont;
  stack sp = stack_last;
#endif
  int sw;
  int j;
  if (ac==2) sw = atoi(av[1]);
  else sw=3;

  if (sw==0) {
    for(loop=0;loop<LOOP_COUNT;loop++) {
      j = f0(loop);
    }
    printf("#0193:%d\n",j);
#if !CC_ONLY
  } else if (sw==1) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f(loop,sp);
  } else if (sw==2) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return2;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f2(loop,sp);
  } else if (sw==3) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return2_1;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f2_1(loop,sp);
#endif
  }
  return 0;
}

/* end */
\end{lstlisting}

\end{document}
\ No newline at end of file
+\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
%\usepackage{jtygm}
%\usepackage{mediabb}
\usepackage{float}
\lstset{
  language={C},
  basicstyle={\footnotesize\ttfamily},
  identifierstyle={\footnotesize},
  commentstyle={\footnotesize\itshape},
  keywordstyle={\footnotesize\bfseries},
  ndkeywordstyle={\footnotesize},
  stringstyle={\footnotesize\ttfamily},
  frame={tb},
  breaklines=true,
  columns=[l]{fullflexible},
  numbers=left,
  xrightmargin=0zw,
  xleftmargin=3zw,
  numberstyle={\scriptsize},
  stepnumber=1,
  numbersep=1zw,
  lineskip=-0.5ex
}

% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の LLVM/clang 3.5 上の実装について]%
	{Continuation based C の LLVM/clang 3.5 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on LLVM/clang 3.5}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{徳森 海斗\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Kaito Tokumori\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{徳森 海斗\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: kaito@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment を用いるプログラミング手法を提案している. この手法を用いるプログラミング言語として CbC の開発を行っており, これは C の下位の言語になる. 本研究では, LLVM/clang-3.5 をベースとした CbC コンパイラの実装を行い, LLVM/clang-3.5 への CbC の具体的な実装について述べる.
\end{abstract}


% 英文概要
\begin{eabstract}
We suggest a programming paradigm which use data segments and code segments. We develop CbC which is a lower language of C and uses that programming paradigm. In this study, we implement CbC compiler on LLVM/clang and introduce implemented Continuation based C Compiler on LLVM/clang-3.5.
\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

\section{研究目的}
当研究室では, プログラムを code segment, data segment という単位を用いて書くという手法を提案している. この手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) というプログラミング言語を開発しており, これは C の下位の言語にあたる. CbC においてコードセグメント間の処理の移動は goto 文を用いた軽量継続によって行われ, これは Tail Call Elimination というコンパイラの持つ最適化の強制によって実現される. CbC では継続前の code segment に戻ることはなく, 状態遷移ベースのプログラミングを行うのに適しており, これは OpenCL, CUDA, そして Cerium といった並列開発環境を用いたプログラムの記述に向いている. この他にも meta code segment, meta data segment といったメタレベルの単位を用意することで柔軟なメタプログラミングを可能にするといった目的を持つ.\\
　これまでに開発された CbC のコンパイラは Micro-C をベースにしたものと GCC をベースにしたものの二種がある.
GCC 上に CbC コンパイラを実装した理由の一つに, 実装時の UNIX 環境におけるコンパイラの標準が GCC であったからというものがあった. しかし, Mac OS X の最新版である Mavericks では GCC の代わりに LLVM/clang が用いられるようになり, 環境が変わりつつあることがわかる. 
このれらのことから, LLVM/clang を用いて CbC をコンパイルできるのが良いという考えが生じた. 本研究では LLVM/clang 上に CbC コンパイラの実装を行う.
 
\section{Continuation based C (CbC)}
CbC では C の関数の代わりに code segment を用いて処理を記述し,  code segment 間の移動に goto を用いる. 
構文は C と同じであるが, 関数呼び出しは goto を用いた継続に, ループ制御は再帰的な継続に置き換えられる.

code segment の記述は C の関数の構文と同じで, 型に \_\_code を使うことで宣言でき, code segment 間の移動は goto の後に code segment 名と引数を並べて記述することで行える. 
この goto による処理の遷移を継続と呼ぶ. 
%図\ref{fig:cs}は code segment 間の処理の流れを表している. 



code segment は C の関数と異なり戻り値を持たず, 必要な値は継続の際に次の code segment へ引数として渡す.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. 
しかし, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無く, スタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. \\
　以下の図\ref{fig:factorial}に示されたプログラムは与えられた数値の階乗を算出する CbC プログラムであり, 図\ref{fig:cs}はこのときの code segment 間の処理の流れを表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/factorial.pdf}}
  \end{center}
  \caption{階乗を計算する CbC プログラムの例}
  \label{fig:factorial}
\end{figure}

\begin{figure}[h]
  \begin{center}
\scalebox{0.53}{\includegraphics{figure/fact_codesegment.pdf}}
  \end{center}
  \caption{goto による code segment 間の継続}
  \label{fig:cs}
\end{figure}

%\section{LLVM/clang の概要}
%LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
%　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
\section{LLVM/clang}
LLVM はコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
　LLVM, clang はコンパイル対象コードを Abstract Syntax Tree (AST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブリコードに変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブリコードを出力するまでの流れを表した図である. clang はソースコードを与えられると, パーサーで構文解析を行い, AST を生成する. そしてその AST を CodeGen を用いて LLVM IR に変換する. LLVM IR をアセンブリコードに変換するまでの処理は LLVM が用いられる. LLVM IR はまず, SelectionDAGISel によって Machine Code に変換される. この時, 直接変換されるのではなく SelectionDAG という内部表現に一度変換され, 最適化された後に変換される. Machine Code は Machine code に対する最適化をかけられた後, Code Emission を通じてアセンブリコードに変換される. またこれらの内部表現の他に, clang が型を表現するのに用いる QualType というクラスについても説明する.

\begin{figure}[ht]
  \begin{center}
\scalebox{0.25}{\includegraphics{figure/clang_llvm_structure.pdf}}
  \end{center}
  \caption{clang, LLVM によるコンパイルの一連の流れ}
  \label{fig:llvmFlow}
\end{figure}

\subsection{QualType}
\label{sec:QualType}
QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (参照) 等の型情報を持つ Type オブジェクトへのポインタを持つ. QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる. また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ, それを通してポインタの指す型を知ることが可能である. 配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する. 修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる.\\
　ここで, 以下に一つの例として ``const int *'' 型に対応する QualType を表した図を示す.\\
\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.45}{\includegraphics{figure/qualType.pdf}}
 \end{center}
 \caption{const int * に対応する QualType}
 \label{fig:qual}
\end{figure}

 図\ref{fig:qual}の QualType A が const int * 型の変数, もしくは関数の持つ QualType である. これの持つ getTypePtr 関数を呼び出すことで, PointerType を得ることができる. この PointerType がどの型に対するポインタかを知るには前述したとおり getPointeeType を呼び出せば良い. そうして呼び出されたのが QualType B である. この例の QualType は const int * 型に対応するものであるので, ここで取得できた QualType B のgetTypePtr 関数を呼び出すと, 当然 IntegerType が得られる. また, この時 int には const がかかっているので, QualType B の isConstQualified 関数を呼ぶと true が返る. \\
　このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる.

\subsection{Abstract Syntax Tree (AST)}
AST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 
出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. CbC コンパイラの実装ではパーサーがこの AST を生成する部分に手を加えている.
%% それぞれの簡単な説明を以下に記す.
%% \begin{description}
%%   \item[Decl]\mbox{}\\
%%     宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
%%   \item[Stmt]\mbox{}\\
%%     一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する. 
%%   \item[Expr]\mbox{}\\
%%     一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
%% \end{description}

\subsection{LLVM IR}
LLVM IR はLLVM BitCode とも呼ばれ, リファレンスが公開されている\cite{LLVMIR}. この言語で記述したプログラムを LLVM 上で実行することも可能である. 各変数が一度のみ代入される Static Single Assignment (SSA) ベースの言語であり, LLVM 内部で扱うためのメモリ上での形式, 人が理解しやすいアセンブリ言語形式, JIT 上で実行するための bitcode 形式の三種類の形を持ち, いずれも相互変換が可能で同等なものである. ループ構文は存在せず, 一つのファイルが一つのモジュールという単位で扱われる. CbC コンパイラの実装では特に変更を行っていない.

\subsection{SelectionDAG}
SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は illegal SelectionDAG, legal SelectionDAG の順に変換されていき, その都度最適化が行われる. CbC コンパイラの実装では, ここで行われる最適化のうちの一つである Tail Call Elimination を code segment に対して強制するように変更を加えている.

\subsection{Machine Code}
Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ SSA 形式と物理レジスタを持つ non-SSA 形式がある. LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている. CbC コンパイラの実装では特に変更を行っていない.

\subsection{MC Layer}
MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. CbC コンパイラの実装では特に変更を行っていない.
% MC Layer が扱うデータ構造は複数あるが, ここでは MCInst と MCStreamer について説明する.\\
%　MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令は次に説明する MCInst と組み合わせて出力する.\\
%　MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.


\section{LLVM/clang 3.5 での CbC コンパイラの実装}
以下の節では LLVM と clang に CbC コンパイラを実装する工程について詳しく説明する. \\
　また, 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.
\subsection{clang への \_\_code 型の追加}
\label{sec:add__code}
まず最初に関数が code segment であることを示す \_\_code 型の追加を行う. そのためには \_\_code を予約語として定義する必要がある. clang では, 予約語は全て \$(CLANG)/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 図\ref{fig:TokenKinds}のように変更を加えて \_\_code を追加した. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示す. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を設定した.
%KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. また, 同時に定義されている \_\_return, \_\_environment は環境付き継続のための予約語である. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/tokenKinds.pdf}}
  \end{center}
  \caption{TokenKinds.def}
  \label{fig:TokenKinds}
\end{figure}

予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. したがって, 次に clang に \_\_code 型を認識させる必要がある.\\
　clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを図\ref{fig:Specifiers}のように編集した.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/Specifiers.pdf}}
  \end{center}
  \caption{Specifiers.h}
  \label{fig:Specifiers}
\end{figure}

これに加えてさらに\ref{sec:QualType} 節で説明した QualType が用いる Type を作らなければならない. この定義は \$(CLANG)/include/clang/AST/BuiltinTypes.def で行われているので, これを図\ref{fig:BuiltinTypes}のように編集した. ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. \_\_code 型は符号無し,有りといった性質を保つ必要はなく, また void 型が BUILTIN\_TYPE を利用していることから \_\_code 型も BUILTIN\_TYPE を使うべきだと判断した.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/BuiltinTypes.pdf}}
  \end{center}
  \caption{BuiltinTypes.def}
  \label{fig:BuiltinTypes}
\end{figure}
\\　これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. よって次に \_\_code 型を解析できるよう clang に変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われており, これが持つ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下の図\ref{fig:parse__code}ように記述を加えた. ここで重要なのは SetTypeSpecType 関数であり, これによって \_\_code 型が DeclSpec に登録される. DeclSpec は型の識別子を持つためのクラスで, 後に QualType に変換される. 
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/parse__code.pdf}}
  \end{center}
  \caption{\_\_code の parse}
  \label{fig:parse__code}
\end{figure}
\\　その他の処理について, 最初にある LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, tailcallopt を有効化するためである. LangOptions が管理するオプションは \$(CLANG)/include/clang/Basic/LangOptions.def で定義される. ここに以下の図 \ref{fig:langOpt} のような変更を加え, HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/langOpt.pdf}}
  \end{center}
  \caption{オプションの追加}
  \label{fig:langOpt}
\end{figure}

\subsection{LLVM 側での \_\_code 型の追加}
LLVM でも clang と同様に \_\_code 型の追加を行う. 型の追加を行うと言っても LLVM IR の持つ type の拡張を行うわけではなく, コンパイル時に内部で code segment であることを知るためだけに型の定義を行い, LLVM IR として出力した場合には 型は void となる. LLVM では型の情報は Type というクラスで管理しており, Type の定義は \$(LLVM)/lib/IR/LLVMContextImpl.h で行う. これに加えて TypeID の登録も行う必要があり, これは \$(LLVM)/include/llvm/IR/Type.h で定義されている. それぞれ, 以下の図\ref{fig:llvm__code}, \ref{fig:llvmType}ように編集した. \\
　さらに, \_\_CodeTy は VoidTy としても扱いたいため, 型判別に用いられる isVoidTy 関数の編集も行った. この関数は Type が VoidTy の場合に真を返す関数である. この関数を Type が \_\_CodeTy の場合にも真を返すようにした. ここで変更を行ったのは if 文の条件文のみなので, ソースコードの記載はしない.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/llvm__code.pdf}}
  \end{center}
  \caption{LLVM での \_\_code の追加}
  \label{fig:llvm__code}
\end{figure}
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/llvmType.pdf}}
  \end{center}
  \caption{LLVM での Type ID の追加}
  \label{fig:llvmType}
\end{figure}

\subsection{継続のための goto syntax の構文解析}
続いて, 継続のための新しい goto syntax の構文解析を行えるようにする. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下の図\ref{fig:ParseGoto}ように変更した. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/parseGoto.pdf}}
  \end{center}
  \caption{継続を行う goto syntax の構文解析}
  \label{fig:ParseGoto}
\end{figure}

ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下の図\ref{fig:ParseCbCGotoStmt} に示す.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/ParseGotoStmt.pdf}}
  \end{center}
  \caption{ParseGotoStmt 関数}
  \label{fig:ParseCbCGotoStmt}
\end{figure}
\\　この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する. 

\subsection{clang/LLVM 間の \_\_code 型の変換}
前述したように, clang と LLVM は別々のクラスを用いて型を管理する. そのため clang の型クラスが LLVM のものに置き換えられる箇所で \_\_code も正しく置き換えられるようにしなければならない. \$(CLANG)/lib/CodeGen/CGCall.cpp の GetFunctionType 関数が clang での関数の型を LLVM のものに変換する関数であるのでここを編集すれば良い. 具体的には以下の図\ref{fig:type} のように編集した. 図のコード中の ABIArgInfo は clang が関数にどのように引数を渡すかの情報を保持するクラスである. void 型ではこれが必ず Ignore になり, 同じことが \_\_code 型にも言える. したがって switch 文内のこの箇所だけで型のチェックを行い, \_\_code 型の時のみ LLVM 側でも \_\_code として扱えば良い.
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.55}{\includegraphics{figure/type.pdf}}
  \end{center}
  \caption{clang/LLVM 間の型変換}
  \label{fig:type}
\end{figure}
\subsection{Tail call eliminationの強制}
前述したように, CbC の継続の実装には Tail call elimination を用いる. Tail call elimination は最適化の一つで, これにより code segment 間の移動を call でなく jmp 命令で行うようになる. 図\ref{fig:tce}は Tail call elimination が行われた際のプログラムの処理を表している. caller は funcB を call でなく jmp で呼び出し, funcB は caller でなく main に戻る.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.30}{\includegraphics{figure/TCE.pdf}}
  \end{center}
  \caption{Tail call elimination}
  \label{fig:tce}
\end{figure}

code segment にこれを強制するためにコンパイラ側では以下の条件を満たす必要がある.
\begin{enumerate}
  \item tail フラグを立てる tail call eliminatoin pass の追加.
  \item 呼び出し元と呼び出す関数の呼び出し規約が fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかである.
%  \item 対象となる関数呼び出しが tail call である.
  \item 最適化のオプションである tailcallopt が有効になっている. 
%  \item 対象関数が可変長引数を持たない.
\end{enumerate}
　まず tail call elimination pass 追加の処理について述べる. clang は最適化の pass の追加を \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数内で行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるが, その pass の追加はこの関数から呼び出される populateModulePassManager 関数で行われる. この関数は LLVM が用意した最適化に用いられる主要な pass を追加するものである. この関数を以下の図\ref{fig:PassManager}のように変更し, 最適化レベルに関わらず追加するようにした. MPM はpass を管理するクラスのインスタンスで, add 関数によってpass の追加が可能になる. また, createTailCallEliminationPass 関数に対して引数を受け取れるように変更を加え, これによって最適化レベルが低い時に code segment 以外の関数に対して tail call elimination しないようにしている. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/PassManager.pdf}}
  \end{center}
  \caption{pass の追加}
  \label{fig:PassManager}
\end{figure}

これで code segment の呼び出しに対して tail フラグが付与されるようになった. しかし実際にはこれだけでは不十分でさらに二つの pass を追加する必要がある. 追加する pass は SROA pass と codeGenPrepare pass である. 一つ目の SROA pass は メモリ参照を減らすスカラー置換を行う pass でこれにより LLVM IR の alloca 命令を可能な限り除去できる. tail call elimination の条件に直接記されてはいないが, tail call elimination pass を用いて tail フラグを付与する場合には 呼び出し元の関数に alloca がないことが求められるのである. 二つ目の codeGenPrepare pass は名前の通りコード生成の準備を行う pass で, これを通さないと if 文を用いた時に call の直後に配置した return 文が消えてしまう. これらの pass 追加されるように変更する必要がある. SROA pass は tail call elimination と同じようにして追加される pass なので同様にして追加することができる. codeGenPrepare pass はこれら二つとは異なり, addPassesToEmitFile という関数を とおして LLVM によって追加される. この時の追加されるかどうか条件が最適化レベルに依存するものであったため, code segment を持つ場合には最適化レベルに関わらず追加するように変更した.\\
　次に, 呼び出し規約の問題を解消する. 条件を満たす呼び出し規約は fastcc, cc 10, cc 11 の三種類があるが, LLVM のドキュメントに cc 10 と cc 11 積極的に利用するのは好ましくないとあった. よって本実験では fastcc を使用する. fastcc を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. 加えて可変引数の使用が不可になり, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要があるという要件を持つ. fastcc の追加は clang が関数情報の設定処理を行っている箇所で行った. 関数情報は CGFunctionInfo というクラスを用いて管理される. 関数情報の設定は \$(CLANG)/lib/CodeGen /CGCall.cpp 内の arrangeLLVMFunctionInfo という関数で行われる. この関数に図\ref{fig:CC} に示されるコードを加えた. 変数 CC への代入文が fastcc を設定している箇所である. \\
%関数が \_\_code型の場合で, かつ可変長引数を持たない場合に呼び出し規約を fastcc に設定する. 可変長引数に関する条件を加えているのは, 可変長引数が使用されている場合には呼び出し規約を変えず tail call elimination を行わないことで通常の関数呼び出しを生成するためである.\\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.45}{\includegraphics{figure/CC.pdf}}
  \end{center}
  \caption{fastcc の付与}
  \label{fig:CC}
\end{figure}

最後に, tailcallopt を有効化を行う. clang と LLVM は指定されたオプションを管理するクラスを別々に持っており, clang はユーザーに指定されたオプションを LLVM に引き継ぐ処理を持つ. その処理が行われているのが \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数である. この関数のオプションの引き継ぎを行っている箇所を以下の図\ref{fig:option}のように変更する. tailcallopt は内部では GuaranteedTailCallOpt となっており, code segment を持つ場合にこれを有効化する.また, LLVM 側でも HasCodeSegment というオプションを追加している. これは先ほど述べた codeGenPrepare pass を追加する際に利用する. \\

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.45}{\includegraphics{figure/option.pdf}}
  \end{center}
  \caption{tailcallopt の有効化}
  \label{fig:option}
\end{figure}

LLVM でのオプションの追加方法についてもここで述べておく. LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. TargetOptions クラスの中で変数を宣言するだけで追加できるので, コードは省略する.

\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメント継続する際, その関数から値を戻す処理への継続を得ることでき, これを環境付き継続と言う. こには は\_\_return, \_\_environment という特殊変数を用い. る図\ref{fig:autoCodeGenB} は環境付き継続の使用例で, この場合 caller が func を呼び出した結果得られる値 0は でなく 1 となる. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/autoCodeGenB.pdf}}
  \end{center}
  \caption{環境付き継続の使用例}
  \label{fig:autoCodeGenB}
\end{figure}

GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文で nested function を用いていた\cite{yogi:2008a}が, LLVM/clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. \_\_return, \_\_environment が宣言されると, 環境付き継続を用いる関数内での継続前に setjmp の構文が追加され, 環境を保持して継続を行うようになる. このとき, \_\_return には元の環境に戻るための code segment へのアドレスが, \_\_environment には元の環境が保持され, \_\_return の指す code segment に \_\_environment を渡して継続することで元の環境に戻ることができる. \_\_return へ継続することで元の環境に戻ることができるのは \_\_return の指す code segment が longjmp を呼び出すためである. また, 環境付き継続を行う際には戻り値を返すために継続元の関数の型をコピーしなければならないという問題があるが, clang では \ref{sec:QualType}節で述べた QualType をコピーするだけで解決する.
%% 図\ref{fig:autoCodeGenB} のコードの場合内部では図\ref{fig:autoCodeGenA} のように解釈される.

%% \begin{figure}[htpb]
%%   \begin{center}
%%     \scalebox{0.50}{\includegraphics{figure/autoCodeGenA.pdf}}
%%   \end{center}
%%   \caption{内部での解釈}
%%   \label{fig:autoCodeGenA}
%% \end{figure}

%% 追加された処理は, setjmp ヘッダのインクルード, 環境と戻り値を保持する構造体 CbC\_env の定義, 元の環境に戻るための特殊 code segment return1 の定義, これに加えて \_\_return, \_\_environment が環境付き継続の前準備を行う処理に変更される. \_\_return は内部では元の環境に戻るための code segment へのポインタの宣言文と, アドレスの代入を行う文に変換され, \_\_environment は内部では環境を保持する構造体, setjmp, longjmp が用いる jmp\_buf, 関数の戻り値となる retval の宣言文, 構造体のメンバの値の設定を行う代入文, そして特殊 code segment return1 の戻り先となる setjmp を用いた構文に変換される. また, \_\_return, \_\_environment に置き換わる処理は Statement Exprs を利用しており, これによって変数への代入も可能となっている.
%追加された処理の大まかな流れを説明すると, 環境付き継続を用いる関数は継続前に setjmp を用いて戻り先の環境を保存し, 継続を行う. このとき, 引数として渡される \_\_return には特殊 code segment return1 のアドレス, \_\_environment の持つメンバには戻り値として返される値を持つ変数のアドレスと, setjmp により保存された継続前の環境が保持されている. 元の環境に戻るための code segment は自動生成されるので, 継続先の code segment は返す戻り値と \_\_environemnt を引数として \_\_return の指す code segment を呼び出すだけで元の環境に戻れる. return1 は 構造体の持つ戻り値へのポインタを利用して戻り値を更新した後, longjmp を用いて元の環境に戻る. longjmp によって再度 setjmp の呼び出しに戻るが今回は if文内に入り, 戻り値を返す.

\section{評価と考察}
今回の実装を行った LLVM/clang 上での CbC コンパイラの評価を試みる. 評価は, コンパイルして出力されたアセンブリコードの確認と, CbC プログラムを Micro-C, GCC, LLVM/clang でコンパイルして得られたプログラムの実行速度を計測により行う. コンパイル, 計測は x86-64 アーキテクチャの Mac OS X 上で行った. なお, このときの GCC のバージョンは 4.9.0 である.
\subsection{アセンブリコードの評価}
以下の図 \ref{fig:evalCbC},\ref{fig:evalAsm} はそれぞれコンパイル前の CbC の code segment とコンパイル後, それに対応するアセンブリコードを示している. 

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/evalCbC.pdf}}
  \end{center}
  \caption{コンパイル前の code segment}
  \label{fig:evalCbC}
\end{figure}
\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/evalAsm.pdf}}
  \end{center}
  \caption{対応するコード}
  \label{fig:evalAsm}
\end{figure}

コンパイル前のコードが持つ factorial0 への継続はコンパイル後, call ではなく jmp 命令により実装されており, このことから tail call elimination が正しく行われていることがわかる. これより, CbC コンパイラを LLVM/clang 上で実装できたことがわかる. \\

\subsection{実行速度の評価}
今回測定に使用したプログラムは conv1 と呼ばれるもので, これは Micro-C での測定や, GCC 上に CbC コンパイラを実装した際の評価にも使用されたものである.\footnote{conv1 のソースコードは付録 A に掲載する.} conv1 の行う処理は CbC の継続と計算を交互に行うもので, 引数 1 の時には CbC の継続を使用, 引数 2, 3 の時には Micro-C のための最適化が手動で施されたコードを使用するようになっている. 測定結果は表 \ref{result} に示される. 尚, GCC の最適化無しコードは, 末尾最適化の強制が原因で segmentation fault を起こすために除外している. 
\begin{table}[htpb]
  \centering
  \begin{tabular}{|l|r|r|r|} \hline
    & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
    Micro-C  & 6.875 & 2.4562 & 3.105 \\ \hline
    GCC -O2 & 2.9438 & 0.955 & 1.265  \\ \hline
    LLVM/clang -O0 & 5.835 & 4.1887 & 5.0625 \\ \hline
    LLVM/clang -O2 & 3.3875 & 2.29 & 2.5087 \\ \hline
  \end{tabular}
  \caption{Micro-C, GCC, LLVM/clang の実行速度比較 (単位 : 秒)}
  \label{result}
\end{table} 

結果についてまず LLVM/clang の最適化の有無で比較すると, 最適化を有効化した方が最適化を用いない場合より全てのケースで二倍以上速い. これは LLVM の最適化の恩恵を受けていることを示していると考えられる. Micro-C と LLVM/clang との実行速度を比較すると, 最適化なしでは LLVM/clang が遅い場合もあるが最適化を有効化すると全ての場合で LLVM/clang が速く, 最適化が大きな効果をもたらしていることがわかる. GCC と比較した場合には速度面では劣るが, LLVM/clang は最適化を無効化しても正常にプログラムが動くという点では優位である.
\section{まとめと今後の課題}
今回の実装により, LLVM/clang を CbC のコンパイルに利用できるようになった. また, 環境付き継続を GCC の拡張構文である nested function でなく, setjmp/longjmp を用いて実装することに成功した. これより, 今後 nested function をサポートしないコンパイル上に CbC コンパイラを実装する必要がでてきた場合でもこの方法により問題なく実装可能であることがわかったと言える. 

今後の課題としてまず, data segment の設計及び実装がある. code segment が処理を表す単位であるのに対し, data segment は処理に必要なデータに対応する. 我々は code segment と data segment の組みがひとつの task に相当すると考えており, data segment は, 内部表現と外部表現を持つ, priority を持ち処理順序の切り替えが可能, task の待ち合わせ制御に依存される, といった要件を満たすように設計されるべきであると考えている.\\
　二つ目の課題として, 環境付き継続の実装をアセンブリコードを用いて行うというものがある. 今回の実装では setjmp/longjmp を用いたが, インラインアセンブリを用いてアセンブリコードを直接書き出すことで速度の向上が見込めるのではないかと考えている. GCC, LLVM はそれぞれ nested function, setjmp/longjmp と言った機能を利用して環境付き継続を実装しているが, Micro-C では直接対応するアセンブリコードを出力する. Micro-Cでは環境付き継続を用いると元の環境のアドレスをベースポインタに代入する mov 命令, ベースポインタの値をスタックポインタに代入する mov 命令, そして元の環境に帰るための jmp 命令の三つで済む. この方法だと各アーキテクチャ毎に対応しなければならないという欠点はあるが, 他の実装方法よりも楽に実装でき, 速度も勝るだろうと考えている.
%以下の図\ref{MicroCAsm} の様なアセンブリコードを出力するのでこれを出力することで GCC, LLVM でも Micro-C と同等の環境付き継続が行えるようにしたい.

\nocite{yogi:2008a, nobu:2011a, LLVMIR, LLVM, clang, clangAPI}
\bibliographystyle{junsrt}
\bibliography{2014_sigos.bib}

\appendix
\section{conv1.c}
\begin{lstlisting}[frame=lrbt,label=conv1,caption={}]
#include <stdio.h>
#include <stdlib.h>
static int loop;

#if 1 // def __micro_c__
#define CC_ONLY 0
#else
#define CC_ONLY 1
#endif

#ifdef CLANG // for clang/LLVM
#define _CbC_return __return
#define _CbC_environment __environment
#endif

typedef char *stack;
#include "conv1.h"

/* classical function call case (0) */
int f0(int i) {
  int k,j;
  k = 3+i;
  j = g0(i+3);
  return k+4+j;
}

int g0(int i) {
  return h0(i+4)+i;
}

int h0(int i) {
  return i+4;
}

#if !CC_ONLY

/* straight conversion case (1) */


struct cont_interface { // General Return Continuation
  __code (*ret)(int,stack);
};

__code f(int i,stack sp) {
  int k,j;
  k = 3+i;
  goto f_g0(i,k,sp);
}

struct f_g0_interface {  // Specialized Return Continuation
  __code (*ret)(int,stack);
  int i_,k_,j_;
};

__code f_g1(int j,stack sp);

__code f_g0(int i,int k,stack sp) { // Caller
  struct f_g0_interface *c = 
    (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

  c->ret = f_g1;
  c->k_ = k;
  c->i_ = i;

  goto g(i+3,sp);
}

__code f_g1(int j,stack sp) {  // Continuation 
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  int k = c->k_;
  sp+=sizeof(struct f_g0_interface);
  c = (struct f_g0_interface *)sp;
  goto (c->ret)(k+4+j,sp);
}

__code g_h1(int j,stack sp);

__code g(int i,stack sp) { // Caller
  struct f_g0_interface *c = 
    (struct f_g0_interface *)(sp -= sizeof(struct f_g0_interface));

  c->ret = g_h1;
  c->i_ = i;

  goto h(i+3,sp);
}

__code g_h1(int j,stack sp) {  // Continuation 
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  int i = c->i_;
  sp+=sizeof(struct f_g0_interface);
  c = (struct f_g0_interface *)sp;
  goto (c->ret)(j+i,sp);
}

__code h(int i,stack sp) {
  struct f_g0_interface *c = (struct f_g0_interface *)sp;
  goto (c->ret)(i+4,sp);
}

struct main_continuation { // General Return Continuation
  __code (*ret)(int,stack);
  __code (*main_ret)(int,void*);
  void *env;
};

__code main_return(int i,stack sp) {
  if (loop-->0)
    goto f(233,sp);
  printf("#0103:%d\n",i);
  goto (( (struct main_continuation *)sp)->main_ret)(0,
  ((struct main_continuation *)sp)->env);
}

/* little optimzation without stack continuation (2) */

__code f2(int i,char *sp) {
  int k,j;
  k = 3+i;
  goto g2(i,k,i+3,sp);
}

__code g2(int i,int k,int j,char *sp) {
  j = j+4;
  goto h2(i,k+4+j,sp);
}

__code h2_1(int i,int k,int j,char *sp) {
  goto main_return2(i+j,sp);
}

__code h2(int i,int k,char *sp) {
  goto h2_1(i,k,i+4,sp);
}

__code main_return2(int i,stack sp) {
  if (loop-->0)
    goto f2(233,sp);
  printf("#0132:%d\n",i);
  goto (( (struct main_continuation *)sp)->main_ret)(0,
       ((struct main_continuation *)sp)->env);
}

/* little optimizaed case (3) */

__code f2_1(int i,char *sp) {
  int k,j;
  k = 3+i;
  goto g2_1(k,i+3,sp);
}

__code g2_1(int k,int i,char *sp) {
  goto h2_11(k,i+4,sp);
}

__code f2_0_1(int k,int j,char *sp);
__code h2_1_1(int i,int k,int j,char *sp) {
  goto f2_0_1(k,i+j,sp);
}

__code h2_11(int i,int k,char *sp) {
  goto h2_1_1(i,k,i+4,sp);
}

__code f2_0_1(int k,int j,char *sp) {
  goto (( (struct cont_interface *)sp)->ret)(k+4+j,sp);
}

__code main_return2_1(int i,stack sp) {
  if (loop-->0)
    goto f2_1(233,sp);
  printf("#0165:%d\n",i);
  exit(0);
  //goto (( (struct main_continuation *)sp)->main_ret)(0,
  //((struct main_continuation *)sp)->env);
}

#define STACK_SIZE 2048
char main_stack[STACK_SIZE];
#define stack_last (main_stack+STACK_SIZE)

#endif

#define LOOP_COUNT 500000000
int
main(int ac,char *av[])
{
#if !CC_ONLY
  struct main_continuation *cont;
  stack sp = stack_last;
#endif
  int sw;
  int j;
  if (ac==2) sw = atoi(av[1]);
  else sw=3;

  if (sw==0) {
    for(loop=0;loop<LOOP_COUNT;loop++) {
      j = f0(loop);
    }
    printf("#0193:%d\n",j);
#if !CC_ONLY
  } else if (sw==1) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f(loop,sp);
  } else if (sw==2) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return2;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f2(loop,sp);
  } else if (sw==3) {
    loop = LOOP_COUNT;
    sp -= sizeof(*cont);
    cont = (struct main_continuation *)sp;
    cont->ret = main_return2_1;
    cont->main_ret = _CbC_return;
    cont->env = _CbC_environment;
    goto f2_1(loop,sp);
#endif
  }
  return 0;
}

/* end */
\end{lstlisting}

\end{document}
\ No newline at end of file