\documentclass[conference]{IEEEtran}

\usepackage[cmex10]{amsmath}
\usepackage{url}
\usepackage{listings}
\usepackage[dvipdfmx]{graphicx}

\lstset{
  frame=single,
  keepspaces=true,
  stringstyle={\ttfamily},
  commentstyle={\ttfamily},
  identifierstyle={\ttfamily},
  keywordstyle={\ttfamily},
  basicstyle={\ttfamily},
  breaklines=true,
  xleftmargin=0zw,
  xrightmargin=0zw,
  framerule=.2pt,
  columns=[l]{fullflexible},
  numbers=left,
  stepnumber=1,
  numberstyle={\scriptsize},
  numbersep=1em,
  language=c,
  tabsize=4,
  lineskip=-0.5zw,
  escapechar={@},
}

\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% Titles are generally capitalized except for words such as a, an, and, as,
% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
% not capitalized unless they are the first or last word of the title.
% Linebreaks \\ can be used within to get better formatting as desired.
% Do not put math or special symbols in the title.
\title{LLVM と Clang を利用した新しい言語の実装}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{
\IEEEauthorblockN{徳森 海斗}
\IEEEauthorblockA{琉球大学 \\ Email: kaito@cr.ie.u-ryukyu.ac.jp}
\and
\IEEEauthorblockN{河野 真治}
\IEEEauthorblockA{琉球大学 \\ Email: kono@ie.u-ryukyu.ac.jp}
}

% make the title area
\maketitle

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



本章では LLVM と Clang を利用した新しいプログラミング言語のコンパイラの実装を行う方法を Continuaton based C(CbC)\cite{CbC2011}
という言語の実装例とともに説明する.
LLVMとClangは、C++ で記述されており、GCCよりも見通し良く書かれている。
LLVMは汎用のコンパイラフレームワークであり、プログラミング言語の構文解析、中間コード生成、機械語生成の各段階で様々なサポートがある。
LLVMで新しい言語を作る方法には様々な方法がある。一つは自作の構文解析器からLLVMの抽象構文木生成のAPI呼び出す方法である。
また、LLVM IRという中間コードを直接生成しても良い。
DSL(ドメイン特化言語)のような場合は、それですむことが多い。
しかし、LLVMの機能を越えたプログラミング言語を作成したい場合は、LLVMの内部に立ち入る必要がある。

CbCは組み込みシステムやOSなどのメタ計算、あるいは言語処理系そのものの実装に的にするように設計された言語である。
コードセグメントという単位と、それを接続する軽量継続(引数付き大域goto文)を持つ。このように関数呼び出しそのものを
独自に持つような言語を実装するにはLLVM自体をLLVMの大域的局所的な最適化に干渉しないように修正する必要がある。

ここではLLVMの内部構造について詳細に説明し、CbCでの修正方法について説明していく。

% また, この実装では LLVM IR に変更を加えることはしない. LLVM IR に変更を加える事は可能であるが, そうした場合最適化を含む LLVM の全てのパスがその変更の影響を受け, 対応させなければならくなる. これは大変難しく現実的でない.

% \section{Continuation based C}
% 今回例として用いる Continuation based C \cite{CbC2011}(以下 CbC) は code segment という処理単位を持つ.
% code segment の宣言は \_\_code という型を用いて行うとする. リスト \ref{code_simple} は最も基本的な CbC のコードの一例で, 図 \ref {fig:code_simple}はそれを図示したものである. 
% 
% 現在の code segment から次の code segment への処理の移動は goto のあとに code segment 名と引数を並べて記述することで次の code segment へと処理を移す (これを軽量継続と呼ぶ) .
% 軽量継続では Secheme の call/cc 等の継続と異なり呼び出し元の環境を持たない. 
% 
% \begin{lstlisting}[float=*,frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
% __code cs0(int a, int b){
%   goto cs1(a+b);
% }
% 
% __code cs1(int c){
%   goto cs2(c);
% }
% \end{lstlisting}
% 
% \begin{figure}[htp]
%  \begin{center}
%   \scalebox{0.55}{\includegraphics{fig/codesegment.pdf}}
%  \end{center}
%  \caption{code segment の軽量継続}
%  \label{fig:code_simple}
% \end{figure}
% 

\section{LLVM clang}
LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本稿でも, 単に LLVM といった場合は LLVM Core を指す. 

LLVMは、 LLVM IR という独自の中間言語を持つ。これはアーキテクチャ依存でない型付きのアセンブラとなっている。人が読める形式のものと
LLVM BitCode というビットストリームにエンコードされたものがある。
LLVMはLLVM IRを実行することのできる仮想機械も持ち、もちろん、. 
 LLVM IR を最適化しながら特定のターゲットの機械語に変換することもできる.

clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたソースコードを解析し, 
抽象構文木(AST)を生成する。そして、そのASTを LLVM IR に変換し、LLVM Coreにより ターゲットマシンの機械語に変換する.
GCC と比較すると丁寧でわかりやすいエラーメッセージを出力する, コンパイル時間が短いといった特徴を持つ.

clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている. 
clang はこれらのライブラリを与えられた引数に応じて呼び出し, コンパイルを行う. 
さらに, 必要な場合は外部のリンカを呼び出してリンクを行い, ソースコードを実行可能な状態まで変換することも可能である. 

ここで, そのライブラリの中でもclangが使用するコンパイルに関連するものについて説明する.

\begin{description}
  \item[libast]\mbox{}\\
    Abstract Syntax Tree (AST) や C の型等をクラスとして利用できるようにしたライブラリ. AST の説明は後述する. % AST は ``-Xclang -ast-dump'' オプションを付加することで表示できる.
  \item[liblex]\mbox{}\\
    字句解析ライブラリ. マクロの展開等の前処理系も担当する.
  \item[libparse]\mbox{}\\
    構文解析ライブラリ. 解析結果を元に後述するlibsemaを使用して AST を生成する.
  \item[libsema]\mbox{}\\
    意味解析ライブラリ. parser (libparse) に AST を生成する機能を提供する.
  \item[libcodegen]\mbox{}\\
    コード生成ライブラリ. 生成された AST を LLVM IR に変換する.
  \item[clang]\mbox{}\\
    ドライバ. 各ライブラリを用いて求められた処理を行う.
\end{description}

これを踏まえて clang が C のコードを LLVM IR に変換する処理について説明する. 尚 LLVM IR が アセンブリ言語にコンパイルされる処理の過程については\ref{sec:llvm}節で LLVM の基本構造とともに説明する.

以下の図\ref{fig:clangProcess}は clang が C のコードを LLVM IR に変換する処理の過程を簡潔に図示したものである. clang は C のソースコードを受け取るとまずその解析を libparser による parser を用いて行い, libsema を用いて 解析結果から AST を構築する. そしてその AST を libcodegen を用いて LLVM IR に変換する.

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.175}{\includegraphics{fig/clangProcess.pdf}}
 \end{center}
 \caption{clang の 処理過程}
 \label{fig:clangProcess}
\end{figure}

\begin{lstlisting}[float=*,basicstyle=\tiny,frame=tb, label=AST, caption={sample.c の AST}]
TranslationUnitDecl 0x102020cd0 <<invalid sloc>>
|-TypedefDecl 0x1020211b0 <<invalid sloc>> __int128_t '__int128'
|-TypedefDecl 0x102021210 <<invalid sloc>> __uint128_t 'unsigned __int128'
|-TypedefDecl 0x102021560 <<invalid sloc>> __builtin_va_list '__va_list_tag [1]'
|-FunctionDecl 0x102021700 <sample.c:1:1, line:3:1> add 'int (int, int)'
| |-ParmVarDecl 0x1020215c0 <line:1:9, col:13> a 'int'
| |-ParmVarDecl 0x102021630 <col:16, col:20> b 'int'
| `-CompoundStmt 0x102021878 <col:22, line:3:1>
|   `-ReturnStmt 0x102021858 <line:2:3, col:14>
|     `-BinaryOperator 0x102021830 <col:10, col:14> 'int' '+'
|       |-ImplicitCastExpr 0x102021800 <col:10> 'int' <LValueToRValue>
|       | `-DeclRefExpr 0x1020217b0 <col:10> 'int' lvalue ParmVar 0x1020215c0 'a' 'int'
|       `-ImplicitCastExpr 0x102021818 <col:14> 'int' <LValueToRValue>
|         `-DeclRefExpr 0x1020217d8 <col:14> 'int' lvalue ParmVar 0x102021630 'b' 'int'
`-FunctionDecl 0x1020218f0 <line:5:1, line:9:1> main 'int ()'
  `-CompoundStmt 0x1020523c0 <line:5:11, line:9:1>
    |-DeclStmt 0x102052210 <line:6:3, col:10>
    | `-VarDecl 0x1020219a0 <col:3, col:7> res 'int'
    |-BinaryOperator 0x102052338 <line:7:3, col:16> 'int' '='
    | |-DeclRefExpr 0x102052228 <col:3> 'int' lvalue Var 0x1020219a0 'res' 'int'
    | `-CallExpr 0x102052300 <col:9, col:16> 'int'
    |   |-ImplicitCastExpr 0x1020522e8 <col:9> 'int (*)(int, int)' <FunctionToPointerDecay>
    |   | `-DeclRefExpr 0x102052250 <col:9> 'int (int, int)' Function 0x102021700 'add' 'int (int, int)'
    |   |-IntegerLiteral 0x102052278 <col:13> 'int' 1
    |   `-IntegerLiteral 0x102052298 <col:15> 'int' 1
    `-ReturnStmt 0x1020523a0 <line:8:3, col:10>
      `-ImplicitCastExpr 0x102052388 <col:10> 'int' <LValueToRValue>
        `-DeclRefExpr 0x102052360 <col:10> 'int' lvalue Var 0x1020219a0 'res' 'int'
\end{lstlisting}


\section{clangAST について}
LLVM と clang を用いたコンパイラの実装では基本的に clang の中間表現である clangAST を組み立てていくことになる. clangAST はソースコードの解析結果を保持したツリーである. 
AST は  \\
\begin{lstlisting}[basicstyle=\tiny,frame=lrbt, caption={ASTを表示するオプション}]
   -Xclang -ast-dump
\end{lstlisting}
というオプションを付加することで表示することもできる.
例えば、簡単なCのソースコード(\ref{ASTSampleCode})は、
リスト\ref{AST}のようになる。

\begin{lstlisting}[basicstyle=\tiny,frame=lrbt, label=ASTSampleCode, caption={sample.c}]
int add(int a, int b){
  return a + b;
}

int main(){
  int res;
  res = add(1,1);
  return res;
}
\end{lstlisting}

出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったC++のクラスを継承したものになっている. 
それぞれの簡単な説明を以下に記す (各クラスの詳細な実装は clang documentation\cite{clang} を参考に).

\begin{description}
  \item[Decl]\mbox{}\\
    宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
  \item[Stmt]\mbox{}\\
    一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する. 
  \item[Expr]\mbox{}\\
    一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
\end{description}



1行目の TranslationUnitDecl が根ノードに当たる. TranslationUnitDecl は翻訳単位を表すクラスであり, この AST が一つのファイルと対応していることがわかる. 実際にソースコードの内容が反映されているのは5行目以降のノードで, 5行目の FunctionDecl がソースコード\ref{ASTSampleCode}の1行目, add 関数の定義部分に当たる. 
対応するソースコードの位置が明らかな場合は\verb+sample.c1:1+などと指定されており、そうでない場合は\verb+<<invalid sloc>>+となっている。
型名や変数名などがASTに格納されていることもわかる。
ソースコード\ref{ASTSampleCode}の7行目の add 関数の呼び出しは, AST ではリスト\ref{AST}の21行目, CallExpr で表されている. 
この CallExpr の下のノードを見ていくと23行目の DeclRefExpr が関数のアドレス0x102021700を持っており, 
これが add 関数のアドレスと一致することから, CallExpr は呼び出す関数への参照を持っていることがわかる. 
これらのノード以外についても return 文は ReturnStmt, 変数宣言は VarDecl というように, 
各ノードがソースコードのいずれかの部分に対応していることが読み取れる.


\section{LLVMでの型の扱い}

clangに新しい機能を付け加えるには新しい型が必要となることがある。
clang で新しい型を扱えるようにするためには, まず型の表す予約後(KEYWORD)を登録する, 
そして、それに対応する識別子を登録する, 
それを QualType (Qaulified type)というC++のオブジェクトの扱う Type として登録をするという手順になる。
ここで新しく作られた型はIRレベルでは基本的な型に展開されてしまうので、LLVMの最適化と衝突することはない。

clang では, 予約語は全て \$(CLANG)\footnote{clang のソースコードを展開したディレクトリのパス}/include/ clang/Basic/TokenKinds.def に定義されている.
ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. 

ここでは CbC のコードセグメントを表す型である\_\_code を追加してみよう。
\_\_code という型は実際には\verb+void *+だが、これを関数の戻り値の型と指定することにより、その関数がコードセグメントであることを表す.

まず、TokenKinds.def のKEYWORDにに\_\_code を追加する.
これで \_\_code に対応する token の id が kw\_\_\_code になる. 
ここで使われている KEYWORD はCのマクロであり、予約語の定義に用いられる.
KEYWORDの第一引数が登録したい予約語, 第二引数のKEYALLはその予約語が利用される範囲を表す. 
KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. 
\verb+noCbC+はCbCでの変更部分を示す条件マクロになっている.

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=token,caption={キーワードの登録}]
       :
KEYWORD(__func__                    , KEYALL)
KEYWORD(__objc_yes                  , KEYALL)
KEYWORD(__objc_no                   , KEYALL)

#ifndef noCbC // CbC Keywords.
KEYWORD(__code                      , KEYALL)
       :
#endif
       :
\end{lstlisting}

予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. 次は clang 内部で使用する識別子を作る.

clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include /clang/Basic/Specifiers.h で行われており, これを以下のように編集した.

\begin{lstlisting}[frame=lrbt,,basicstyle=\tiny,label=TST,caption={TypeSpecTypeの登録}]
enum TypeSpecifierType {
  TST_unspecified,
  TST_void,
       :
#ifndef noCbC
    TST___code,
#endif
       :
\end{lstlisting}
これに加えてさらに QualType が用いる Type を作らなければならない.

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.2}{\includegraphics{fig/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 を辿ることで完全な型を知ることができる.

この Type の定義は \$(CLANG)/include/ clang/AST/BuiltinTypes.def で行われているので, これを編集する(リスト\ref{clangType}).
ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. 
\_\_code 型は符号無し,有りといった性質を保つ必要はないため, 今回は BUILTIN\_TYPE を使うべきである. 

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=clangType,caption={Typeの登録}]
       :
// 'bool' in C++, '_Bool' in C99
UNSIGNED_TYPE(Bool, BoolTy)

// 'char' for targets where it's unsigned
SHARED_SINGLETON_TYPE(UNSIGNED_TYPE(Char_U, CharTy))

// 'unsigned char', explicitly qualified
UNSIGNED_TYPE(UChar, UnsignedCharTy)

#ifndef noCbC
BUILTIN_TYPE(__Code, __CodeTy)
#endif
       :
\end{lstlisting}

ここまでの変更で clang が \_\_code 型を扱えるようになった.
% り, \_\_code 型の関数, 即ち code segment を解析する準備が整った.


次は clang が \_\_code 型を解析し clangAST に変換できるようにしなければならない. 
clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. 
この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 
具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=parse__Code,caption={\_\_code の parse}]
  case tok::kw___code: {
    LangOptions* LOP;
    LOP = const_cast<LangOptions*>(&getLangOpts());
    LOP->HasCodeSegment = 1;
    isInvalid = DS.SetTypeSpecType(
      DeclSpec::TST___code, Loc, PrevSpec, DiagID);
    break;
  }
\end{lstlisting}

重要なのは 5行目である. SetTypeSpecType 関数はその名の通り TypeSpecType を設定する関数であり, ここで \_\_code 型が DeclSpec に登録される. DeclSpec は 型の識別子を持つためのクラスであり, 後に QualType に変換される. 

ここでは型を追加しただけなので、ASTからIRへの変換をいじる必要はない. 実際のCbC言語では軽量継続部分のコード生成を行う必要がある.
それにはLLVM IR生成以降の部分を追う必要がある.

\section{LLVM IRから機械語への変換の流れ}
\label{sec:llvm}
LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない. 中間表現を何度か変え, その度に最適化を行い, そして最終的にターゲットのアセンブリ言語に変換するのである. 
また LLVM では, 最適化や中間表現の変換といったコンパイラを構成する処理は全て pass が行う. 多くの pass は最適化のために存在し, この pass を組み合わせることにより, LLVM の持つ機能の中から任意のものを利用することができる.

LLVM がターゲットのアセンブリ言語を生成するまでの過程を簡潔に記すと以下のようになる.

\begin{description}
  \item[SelectionDAG Instruction Selection (SelectionDAGISel)]\mbox{}\\
    LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し, 最適化を行う. その後 Machine Code を生成する.
  \item[SSA-based Machine Code Optimizations]\mbox{}\\
    SSA-based Machine Code に対する最適化を行う. 各最適化はそれぞれ独立した pass になっている.
  \item[Register Allocation]\mbox{}\\
    仮想レジスタから物理レジスタへの割り当てを行う. ここで PHI 命令が削除され, SSA-based でなくなる.
  \item[Prolog/Epilog Code Insertion]\mbox{}\\
    Prolog/Epilog Code の挿入を行う. どちらも関数呼び出しに関わるものであり, Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理, Epilog は呼び出し元の関数に戻る際に行う処理である.
  \item[Late Machine Code Optimizations]\mbox{}\\
    Machine Code に対してさらに最適化を行う.
  \item[Code Emission]\mbox{}\\
    Machine Code を MC Layer での表現に変換する. その後さらにターゲットのアセンブリ言語へ変換し, その出力を行う.
\end{description}

これらの処理の流れを図示したものが以下の図\ref{fig:llvmProcess}である. 前述した通りこれらの処理は全て pass によって行われる. pass にはいくつかの種類があり, 関数単位で処理を行うもの, ファイル単位で処理を行うもの, ループ単位で処理を行うもの等がある. 

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.175}{\includegraphics{fig/llvmProcess.pdf}}
 \end{center}
 \caption{LLVM の 処理過程}
 \label{fig:llvmProcess}
\end{figure}


\section{LLVM の中間表現}
この節では LLVM の中間表現である LLVM IR, SelectionDAG, Machine Code, MC Layer\footnote{ MC Layer は正確には中間表現ではない. 詳しくは本節で後述する. } と LLVM の最適化について簡単に説明する. なお, 詳しくは LLVM Documantation\cite{LLVM}を参照していただきたい.

LLVM のメインとなる中間表現はフロントエンドの出力, バックエンドの入力に対応する LLVM IR である.

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

LLVM IR の一例として c 言語の関数を clang を用いて LLVM IR に変換したものをリスト \ref{IRtestC}, \ref{IRtestIR} に示す. LLVM IR に変換された後の関数 test を見ると, while文によるループ構文がなくなっていることがわかる. while文は while.cond, while.body という 2つのブロックに分けられており, while.cond が while文の条件文, while.body が while文の中身を表している. while.end は while という名が付いているが, while文と直接は関係しておらず, これは while文によるループ処理が終わった後の処理が置き換わったものである.

\begin{lstlisting}[frame=lrbt, label=IRtestC, caption={c での関数 test}]
int test(int a, int b){
  int i, sum = 0;
  i = a;
  while ( i <= b) {
    sum += i;
    i++;
  }
  return sum - a * b;
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt, label=IRtestIR, caption={LLVM IR での関数 test}]
define i32 @test(i32 %a, i32 %b) #0 {
entry:
  br label %while.cond

while.cond:
  %i.0 = phi i32 [ %a, %entry ], [ %inc, %while.body ]
  %sum.0 = phi i32 [ 0, %entry ], [ %add, %while.body ]
  %cmp = icmp sle i32 %i.0, %b
  br i1 %cmp, label %while.body, label %while.end

while.body:
  %add = add nsw i32 %sum.0, %i.0
  %inc = add nsw i32 %i.0, 1
  br label %while.cond

while.end:
  %mul = mul nsw i32 %a, %b
  %sub = sub nsw i32 %sum.0, %mul
  ret i32 %sub
}
\end{lstlisting}

SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は初め illegal SelectionDAG に変換され, legalization を含む多くの段階を踏んで次の中間表現である Machine Code になる. 

以下に SelectionDAG が Machine Code に変換されるまでに行われる処理の過程を示す. 

\begin{description}
  \item[Build initial DAG]\mbox{}\\
    LLVM IR を illegal SelectionDAG に変換する. 
  \item[Optimize]\mbox{}\\
    illegal SelectionDAG に対して最適化を行う. 
  \item[Legalize SelectionDAG Types]\mbox{}\\
    ターゲットのサポートしていない型を除去し, ターゲットのサポートする型だけで構成された SelectionDAG に変換する.
  \item[Optimize]\mbox{}\\
    最適化. 型変換が行われたことで表面化した冗長性の解消を行う.
  \item[Legalize SelectionDAG Ops]\mbox{}\\
    ターゲットのサポートしていない命令を除去し, ターゲットのサポートする命令だけで構成された SelectionDAG に変換する. これで SelectionDAG の legalization が完了となる.
  \item[Optimize]\mbox{}\\
    最適化. 命令を変更したことによって発生した非効率性を排除する.
  \item[Select instructions from DAG]\mbox{}\\
    SelectionDAG を元に, 現在の命令をターゲットのサポートする命令に置き換えた DAG を生成する.
  \item[SelectionDAG Scheduling and Formation]\mbox{}\\
    命令のスケジューリングを行い, DAG を Machine Code に変換する. 
\end{description}

SelectionDAG を確認したい場合は clang に ``-mllvm -view-***-dags'' オプションを与えることで生成される dot ファイルを見れば良い. *** には legalize などの文字列が入り, どの段階の DAG を出力するか選択することが出来る. 図 \ref{fig:dag} はリスト \ref{IRtestC} の add 関数に対応する legalize 直前の DAG である. この図より, + 演算子に対応する add ノードや return 命令に対応するノードその戻り値を受けるためのレジスタが指定されているのがわかる. 


\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.40}{\includegraphics{fig/dag.pdf}}
 \end{center}
 \caption{add 関数に対応する legalize 直前の SelectionDAG}
 \label{fig:dag}
\end{figure}


Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮想レジスタを持つ Single Static Assignment (SSA) 形式と物理レジスタを持つ non-SSA 形式がある. SSA 形式とは全ての変数が一度のみ代入されるように記述した形式であり. この形式を取ることで LLVM は効率よく最適化を行うことが出来る.

Machine Code は LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている.

IRを安易に変更すると、LLVM内部の最適化と干渉してしまう。IRで許される変更は、新しい型名の追加ぐらいしか許されない.
CbC ではIR以降の変更は、その型名と関数呼び出し時に付けられる汎用のフラグを用いている.



% \section{オプションの追加}
% 
% リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.
% 
% \begin{lstlisting}[float=*,frame=lrbt,label=langOpt,caption={LangOptions の追加}]
%        :
% LANGOPT(ApplePragmaPack, 1, 0, "Apple gcc-compatible #pragma pack handling")
% 
% BENIGN_LANGOPT(RetainCommentsFromSystemHeaders, 1, 0, "retain documentation comments from system headers in the AST")
% 
% #ifndef noCbC
% LANGOPT(HasCodeSegment          , 1, 0, "CbC")
% #endif
%        :
% \end{lstlisting}
% 
% ただしこのオプションは clang 内で有効なもので, LLVM IR の処理以降も有効にしておきたい場合 LLVM 側でもオプションを新設し, 引き継ぐ必要がある.
% 
% clang のオプションの値は \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数(\ref{option})で行われる. 
% 
% \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
%        :
%   Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
%   Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
% #ifndef noCbC
%   Options.HasCodeSegment = LangOpts.HasCodeSegment;
%   Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
% #endif
%        :
% \end{lstlisting}
% 
% LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)\footnote{LLVMのソースコードをインストールしたディレクトリのパス}/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. 
% 
% \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
%   class TargetOptions {
%        :
%     /// Emit target-specific trap instruction for 'unreachable' IR instructions.
%     unsigned TrapUnreachable : 1;
% 
%     /// EmulatedTLS - This flag enables emulated TLS model, using emutls
%     /// function in the runtime library..
%     unsigned EmulatedTLS : 1;
%     #ifndef noCbC
%     unsigned HasCodeSegment : 1;
%     #endif
%        :
% \end{lstlisting}
% 

\section{CbCの構文}
次は新しい構文の追加について. ここでは CbC の軽量継続のための構文を追加する.
CbC で追加される構文は\_\_codeと、それを呼び出すgoto 文だけである.

\begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCのコード}]
__code code3(int a, int b,
             int loop, int ans){
  goto code4(b,b/a,loop, ans);
}

__code code2(int a, int b,
             int loop, int ans){
  goto code3(b,a*b,loop, ans);
}
\end{lstlisting}

コードセグメント\_\_codeはCの関数と同じ形をしているが、return 文は許されず、goto 文で次のコードセグメント
に移行する。この例では\_\_code2 から \_\_code3 へ処理が移行している.

これは以下のCのコードに似ている.

\begin{lstlisting}[frame=lrbt,label=calc,caption={Cのコード}]
int func3(int a, int b){
  return func4(b,b/a);
}

int func2(int a, int b){
  return func3(b,a*b);
}
\end{lstlisting}

Cの関数はcall命令で呼び出され値を返すのに対して、コードセグメントはjmp命令で移動するだけである.
それ以外は同じと言って良い. 引数の計算, 局所変数の扱いなどなどである.
つまり構文的には コードセグメントの定義は関数の定義の構文と同じであり,
軽量継続つまり, goto 文の後のコードセグメントの呼び出しは関数呼び出しの構文と同じで良い.


実際には LLVM 内部で末尾最適化を強制することでこれを実現している.
末尾最適化とは, 関数の一番最後に呼び出される関数は call せすに jmp するだけで良いということである.
LLVM IRレベルでは、call命令にTAIL CALLフラグを付ければ良い.
フラグを付ける以外に
末尾最適化を実現するためのいくつかの条件があり CbC コンパイラでは, それを満たすように
コードセグメントのAST生成部分、あるいは最適化部分に手を入れている.

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


\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,label=ParseStmt,caption={goto 文の構文解析}]
       :
case tok::kw_goto:                // C99 6.8.6.1: goto-statement
#ifndef noCbC
  if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) && // C: 'goto' identifier ';'
    NextToken().isNot(tok::star)) {                                        // C: 'goto' '*' expression ';'
      SemiError = "goto code segment";
      return ParseCbCGotoStatement(Attrs, Stmts);                              // CbC: goto codesegment statement
    }
#endif
  Res = ParseGotoStatement();
  SemiError = "goto";
  break;
       :
\end{lstlisting}

ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, PP.LookAhead(1)でtoken の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. 
C では goto の後はラベルまたは*のついた間接ラベルになる. 
そこで, 識別子とセミコロン、あるいは*がある場合はCのgoto文として扱い, そうでなければ CbC の軽量継続として取り扱う.
ここで軽量継続が呼び出しているのがコードセグメントであることを確認することが望ましいが, この段階では, まだ, 呼び出し側の
型が何かを知ることはできない.
C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. 
ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す. このように, 長い処理を追加する場合には別のファイルを作成し, そこに関数として処理を定義するほうが LLVM, clang のアップデートの際に変更が楽になるため良い.

\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,,label=ParseCbCGotoStmt,caption={ParseCbCGotoStatement}]
StmtResult Parser::ParseCbCGotoStatement(ParsedAttributesWithRange &Attrs,StmtVector &Stmts) {
  assert(Tok.is(tok::kw_goto) && "Not a goto stmt!");
  ParseScope CompoundScope(this, Scope::DeclScope);
  StmtVector CompoundedStmts;

  SourceLocation gotoLoc = ConsumeToken();  // eat the 'goto'.
  StmtResult gotoRes;
  Token TokAfterGoto = Tok;
  Stmtsp = &Stmts;
  
  gotoRes = ParseStatementOrDeclaration(Stmts, false);
  if (gotoRes.get() == NULL)
    return StmtError();
  else if (gotoRes.get()->getStmtClass() != Stmt::CallExprClass) { // if it is not function call
    Diag(TokAfterGoto, diag::err_expected_ident_or_cs);
    return StmtError();
  }
  
  assert((Attrs.empty() || gotoRes.isInvalid() || gotoRes.isUsable()) &&
	 "attributes on empty statement");
  if (!(Attrs.empty() || gotoRes.isInvalid()))
    gotoRes = Actions.ProcessStmtAttributes(gotoRes.get(), Attrs.getList(), Attrs.Range);
  if (gotoRes.isUsable())
    CompoundedStmts.push_back(gotoRes.release());

  // add return; after goto codesegment();
  if (Actions.getCurFunctionDecl()->getResultType().getTypePtr()->is__CodeType()) {
    ExprResult retExpr;
    StmtResult retRes;
    retRes = Actions.ActOnReturnStmt(gotoLoc, retExpr.get(), getCurScope());
    if (retRes.isUsable())
      CompoundedStmts.push_back(retRes.release());
  }
  return Actions.ActOnCompoundStmt(gotoLoc, Tok.getLocation(), CompoundedStmts, false);
}
\end{lstlisting}

この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する.

return statement の生成は ActOnReturnStmt 関数を用いることで楽に行うことが出来る. 具体的には, 引数としてソードコードの位置を示す SourceLocation, Expr, 解析中のスコープを示す scope を与えれば良い. SouceLocation は Token から取得できる. Expr は宣言して生成されたものをすぐに利用して良い. そしてスコープは, getCurScope 関数によって取得できる現在のスコープを与えれば良い.

こうして得られた二つの Stmt を StmtVector に入れ, ActOnCompoundStmt 関数に与えることで適切な Stmt が得られる.

\section{最適化パスの選択}
LLVM では最適化を含めすべての処理がパスによって行われる. 最適化パスを選択することで任意の最適化を利用することが出来る. パスは PassManager によって管理される. 基本的なパスのセットを追加してくれる populateFunctionPassManager, populateModulePassManager 等が存在し, clang でもそれを用いてパスの追加を行っている. なお, functionPassManager は関数単位で働くパスの PassManager で, modulePassManager はモジュール(ファイル)単位で働くパスの PassManager である.

CbC では tail call elimination という最適化を強制する. そのためここでは TailCallElimPass の追加を例として示す.

clang では \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数から populateModulePassManager 関数を呼び出してパスの追加を行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるがこれをレベルにかかわらず追加するように変更した (リスト\ref{PassManager}). 変数 MPM が PassManager で, add 関数を用いて pass の登録を行う. add 関数の引数に createTailCallEliminationPass 関数を指定することで tail call elimination pass が追加される.

\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,label=PassManager,caption={tail call elimnation pass の追加}]
       :
  if (OptLevel == 0) {
       :
#ifndef noCbC
    MPM.add(createTailCallEliminationPass(true));   // Eliminate tail calls
#endif
       :
  }
       :
#ifndef noCbC
  MPM.add(createTailCallEliminationPass(false));   // Eliminate tail calls
#else
  MPM.add(createTailCallEliminationPass());   // Eliminate tail calls
#endif
       :
\end{lstlisting}

\section{calling convention の選択}
LLVM IR には関数呼び出しに様々なフラグをつけることが出来る. そのうちの一つに呼び出し規約がある. LLVM がサポートする呼び出し規約は ccc, fastcc, cc 10, cc 11 等多数存在する. その一部を簡潔にまとめると以下のようになる (詳しくは LLVM IR Language Reference\cite{LLVMIR}).

\begin{description}
  \item[ccc]\mbox{}\\
    特に指定されていない場合にはこれになる. C の呼び出し規約に対応し, 可変長引数をサポートする. プロトタイプ宣言と関数の定義の不一致を許す.
  \item[fastcc]\mbox{}\\
    この規約を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. この呼び出し規約は可変引数をサポートせず, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要がある.
  \item[cc 10]\mbox{}\\
    Glasgow Haskell Compiler のために実装された呼び出し規約. X86 でのみサポートされており, 引数に関するいくつかの制限をもつ. レジスタ内の値を全て渡し, 呼び出された関数はレジスタの値を保存できない. この呼び出し規約は関数型プログラミング言語を実装する際に使用される register pinning という技術の代わりとして特定の状況でしか使用してはならない.
  \item[cc 11]\mbox{}\\
    High-Performance Erlang のために実装された呼び出し規約. 通常の C の呼び出し規約以上に引数を渡すためにレジスタを利用する. X86 でのみサポートされており, cc 10 同様に register pinning を用いる. 
\end{description}

この呼出し規約は LLVM IR 以降で利用されるので clang が clangAST を LLVM IR に変換する前に付加するのが良い. 今回は clang が関数呼び出しの情報を設定する arrangeLLVMFunctionInfo という関数内で行った. この関数は \$(CLANG)/lib/CodeGen /CGCall.cpp にある. この関数に以下のリスト \ref{CC} に示されるコードを加えた. 5 行目が fastcc を設定している箇所である. この CC が後の処理で利用されることで fastcc が設定される. allowsOptionalArgs 関数は可変長引数を持つかどうかを判別するために使用している. 

\begin{lstlisting}[float=*,frame=lrbt,label=CC,caption={fastcc の追加}]
       :
#ifndef noCbC
  if(resultType.getTypePtr()->is__CodeType()){
    if(!required.allowsOptionalArgs())
      CC = llvm::CallingConv::Fast;
  }
#endif
       :
\end{lstlisting}

\section{動作確認}

ここまでの実装で clang を用いて CbC の基本的な構文を解釈できるようになった. おさらいすると以下の機能を実装した.

\begin{itemize}
\item \_\_code 型の登録
\item code segment の構文解析
\item 軽量継続のための構文の実装
\item tail call elimination の強制
\item fastcc 指定
\end{itemize}

正しく実装出来ているか確認するために LLVM IR, アセンブリコードの二種を出力する. LLVM IR はコンパイル時に -S -emit-llvm というオプションをつけることで出力できる. リスト \ref{evalCbC} が元のコード, リスト \ref{evalIR} が LLVM IR, リスト \ref{evalAsm} がアセンブリコードである.

CbC のコードには本来 C には存在しない \_\_code 型, goto による軽量継続の構文が存在するが, 今回の実装によりコンパイルが可能である. 出力された LLVM IR を確認すると, code segment の呼び出し時に tail call であることを示す tail フラグ, fastcc の関数呼び出し規約, 呼び出し直後の return 文が実装したとおりきちんと付加されていることがわかる.

アセンブリコードの方では code segment f\_g0 への遷移が call 命令でなく jmp 命令で行われており, きちんと tail call elimination が強制されていることがわかる. これはオプションの引き継ぎが正しく行われたことを示す.

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalCbC,caption={CbCのコード}]
__code f(int i,stack sp) {
  int k,j;
  k = 3+i;
  goto f_g0(i,k,sp);
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalIR,caption={出力された LLVM IR}]
define fastcc void @f(i32 %i, i8* %sp) #0 {
entry:
%add = add nsw i32 3, %i
tail call fastcc void @f_g0(i32 %i, i32 %add, i8* %sp)
ret void
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalAsm,caption={出力されたアセンブリコード}]
   .cfi_startproc
## BB#0:                                ## %entry
   subq  $24, %rsp
 Ltmp9:
   .cfi_def_cfa_offset 32
   movl  %edi, %eax
   addl  $3, %eax
   movq  %rsi, 16(%rsp)          ## 8-byte Spill
   movl  %eax, %esi
   movq  16(%rsp), %rdx          ## 8-byte Reload
   addq  $24, %rsp
   jmp  _f_g0                   ## TAILCALL
   .cfi_endproc
\end{lstlisting}

Cの関数呼び出しは, スタックの書込を伴うので, かなり重い操作である. 階層化されたライブラリを経由するたびに
関数呼び出しがはさまり, 大きなアプリでは30段になる場合もある.
LLVMを含む最近のコンパイラでは関数は積極的に展開されてしまい, 生成されたコードが大きくなる原因となっている.

CbC は関数呼び出しを排除するので, jmp 命令で高速にコードセグメントを切り替えることができる. 
C の関数呼び出しとし, それぞれを5万回に行った時の時間の差を見ると結果は表\ref{comp}になる.

関数呼び出しを完全に排除したCbCのコードはアセンブラ的であり, 人が書きやすいものとは言えない.
CbC はアーキテクチャに依存しないアセンブラとして使用することができる.
性能が要求されるOSやデータベースなどのシステムソフトウェアなどに向いている.
あるいは,状態遷移を基本としたアプリ, 例えばネットワークアプリケーション, あるいは grep などをにも
向いている. 

\begin{table}[htpb]
  \centering
  \begin{tabular}{|l|r|} \hline
      & 実行速度 (s) \\ \hline
    関数呼び出し  & 4.85 \\ \hline
    軽量継続 & 3.10 \\ \hline
  \end{tabular}
  \caption{関数呼び出しと軽量継続の速度比較}
  \label{comp}
\end{table} 

\section{まとめ}
本章では LLVM と Clang を利用したオリジナルの言語のコンパイラの実装を行った. 新しい型や構文の実装方法, 
% オプションの作り方, 
最適化の追加と強制の方法について説明を行い, 正しくコンパイルできることを確認した. 重要なのは LLVM IR の改変を行わないことで, これによりバックエンドの処理をそのまま利用することが出来る. 今回実装した言語は C ベースな言語であるため clang を利用したが, 必要に応じて他のフロントエンドを利用すること, 一からフロントエンドを書くことを検討するのも良い.

\nocite{CbC2011, LLVMIR, LLVM, clang, repo}
\bibliographystyle{IEEEtran}
\bibliography{IEEEabrv,reference}

% that's all folks
\end{document}