changeset 10:5c0fdc79df25

add LLVM/clang description and compile flow.
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Sun, 20 Apr 2014 21:28:42 +0900
parents a9621a0894d5
children 1663ff2891f3
files 2014_sigos.bib 2014_sigos.pdf 2014_sigos.tex
diffstat 3 files changed, 1 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/2014_sigos.bib	Sun Apr 20 18:11:58 2014 +0900
+++ b/2014_sigos.bib	Sun Apr 20 21:28:42 2014 +0900
@@ -30,14 +30,6 @@
 	year = 2008
 }
                   
-@article{yogi:2008b,
-	author = "与儀健人 and 河野真治",
-	title = "Continuation based C の GCC 上の実装",
-	journal = "琉球大学 情報工学科 学位論文(修士)",
-	month = "Feb",
-	year = 2008
-}
-                  
 @manual{LLVMIR,
 author = "{LLVM Language Reference Manual}",
 title = "{\\http://llvm.org/docs/LangRef.html}",
Binary file 2014_sigos.pdf has changed
--- a/2014_sigos.tex	Sun Apr 20 18:11:58 2014 +0900
+++ b/2014_sigos.tex	Sun Apr 20 21:28:42 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{研究目的}
当研究室では, プログラムをコードセグメント, データセグメントという単位を用いて書くという手法を提案している. この手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) というプログラミング言語を開発しており, これは C の下位の言語にあたる. CbC においてコードセグメント間の処理の移動は goto 文を用いた軽量継続によって行われ, これは Tail Call Elimination というコンパイラの持つ最適化の強制によって実現される. CbC では継続前の code segment に戻ることはなく, 状態遷移ベースのプログラミングを行うのに適しており, これは OpenCL, CUDA, そして Cerium といった並列開発環境を用いたプログラムの記述に向いている. \\
 これまでに開発された CbC のコンパイラは Micro-C をベースにしたものと GCC をベースにしたものの二種がある.
 GCC 上に CbC コンパイラを実装した理由の一つに, 当時の UNIX 環境における コンパイラの標準が GCC であったからというものがあった. しかし, Mac OS X の最新版である Mavericks では GCC の代わりに LLVM/clang が用いられるようになり, 環境が変わりつつあることがわかる. 
このような背景から, LLVM/clang を用いて CbC をコンパイルできるのが良いという考えが生じた. 本研究では LLVM/clang 上に CbC コンパイラの実装を行う.
%\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}
%\bibliographystyle{junsrt}
%\bibliography{cbc.bib}
 
\section{Continuation based C (CbC)}
CbC では C の関数の代わりに code segment を用いて処理を記述し,  code segment 間の移動に goto を用いる. 
構文は C と同じであるが, ループ制御や関数コールが取り除かれる. 

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

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


code segment は C の関数と異なり戻り値を持たず, 処理が終われば次の code segment へと処理を移る. 
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. 
しかし, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無く, スタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. \\
 以下の図\ref{fig:factorial}に示されたプログラムは与えられた数値の階乗を算出する CbC プログラムである. %このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/factorial.pdf}}
  \end{center}
  \caption{階乗を計算する CbC プログラムの例}
  \label{fig:factorial}
\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 で扱われる内部表現}
CbC コンパイラの実装の前に, LLVM 及び clang で扱われる内部表現について触れる. LLVM, clang はコンパイル対象コードを Abstract Syntax Tree (AST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブリ言語へと変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブリ言語を出力するまでの流れを表した図である. またこれらの内部表現の他に, 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 での実装}
以下の節では 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.60}{\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{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 という特殊変数を用いる. GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文である内部関数を用いていたが, clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. 環境付き継続は, \_\_return, \_\_environment が使用された時に自動的にあるコードを生成することで実現される. 具体的には, 図\ref{fig:autoCodeGenB} のようなコードを, 内部で図\ref{fig:autoCodeGenA} のように解釈することで実現される.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/autoCodeGenB.pdf}}
  \end{center}
  \caption{環境付き継続の使用例}
  \label{fig:autoCodeGenB}
\end{figure}
\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 プログラムをコンパイルさせ, 出力されたアセンブリコードを確認することで行う. コンパイルは x86-64 アーキテクチャの Mac OS X 上で行った. 以下の図 \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 上で実装できたことがわかる. \\

\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 の待ち合わせ制御に依存される, といった要件を満たすように設計されるべきであると考えている.

\nocite{yogi:2008b, nobu:2011a, LLVMIR, LLVM, clang, clangAPI}
\bibliographystyle{junsrt}
\bibliography{2014_sigos.bib}
\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{研究目的}
当研究室では, プログラムをコードセグメント, データセグメントという単位を用いて書くという手法を提案している. この手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) というプログラミング言語を開発しており, これは C の下位の言語にあたる. CbC においてコードセグメント間の処理の移動は goto 文を用いた軽量継続によって行われ, これは Tail Call Elimination というコンパイラの持つ最適化の強制によって実現される. CbC では継続前の code segment に戻ることはなく, 状態遷移ベースのプログラミングを行うのに適しており, これは OpenCL, CUDA, そして Cerium といった並列開発環境を用いたプログラムの記述に向いている. \\
 これまでに開発された 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 と同じであるが, ループ制御や関数コールが取り除かれる. 

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

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


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

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/factorial.pdf}}
  \end{center}
  \caption{階乗を計算する CbC プログラムの例}
  \label{fig:factorial}
\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 での実装}
以下の節では 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.60}{\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{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 という特殊変数を用いる. GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文で nested function を用いていた\cite{yogi:2008a}が, clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. 環境付き継続は, \_\_return, \_\_environment が使用された時に自動的にあるコードを生成することで実現される. 具体的には, 図\ref{fig:autoCodeGenB} のようなコードを, 内部で図\ref{fig:autoCodeGenA} のように解釈することで実現される.

\begin{figure}[htpb]
  \begin{center}
    \scalebox{0.50}{\includegraphics{figure/autoCodeGenB.pdf}}
  \end{center}
  \caption{環境付き継続の使用例}
  \label{fig:autoCodeGenB}
\end{figure}
\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 プログラムをコンパイルさせ, 出力されたアセンブリコードを確認することで行う. コンパイルは x86-64 アーキテクチャの Mac OS X 上で行った. 以下の図 \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 上で実装できたことがわかる. \\

\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 の待ち合わせ制御に依存される, といった要件を満たすように設計されるべきであると考えている.

\nocite{yogi:2008a, nobu:2011a, LLVMIR, LLVM, clang, clangAPI}
\bibliographystyle{junsrt}
\bibliography{2014_sigos.bib}
\end{document}
\ No newline at end of file