\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 という言語の実装例とともに説明する.
また, この実装では 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}[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{clangAST について}
LLVM と clang を用いたコンパイラの実装では基本的に clang の中間表現である clangAST を組み立てていくことになる. clangAST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 例えばリスト\ref{ASTSampleCode}コンパイル時にオプション ``-Xclang -ast-dump'' を付与した場合は出力結果としてリスト\ref{AST}が得られる. 出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. それぞれの簡単な説明を以下に記す (各クラスの詳細な実装は 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}

これらを踏まえて, ソースコード\ref{ASTSampleCode}と出力された AST( リスト\ref{AST} ) に注目する.

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

\begin{lstlisting}[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}
\begin{lstlisting}[frame=lrbt, 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{新しい型(\_\_code)を実装するには}
clang で新しい型を扱えるようにするためには, キーワードを登録する, 識別子を登録する, QualType の扱う Type の登録をするといった作業が必要である. これらを順に説明する.

clang では, 予約語は全て \$(CLANG)\footnote{clang のソースコードを展開したディレクトリのパス}/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 次のように変更を加えて \_\_code を追加した. これで \_\_code に対応する token の id が kw\_\_\_code になる. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. 

\begin{lstlisting}[frame=lrbt,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 の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. 

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

\begin{lstlisting}[frame=lrbt,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,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 を解析する準備が整った.
次は \_\_code 型を解析し clangAST に変換できるようにしなければならない. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.

\begin{lstlisting}[frame=lrbt,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 に変換される. 

\section{オプションの追加}
リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.

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


\begin{lstlisting}[frame=lrbt,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 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す. このように, 長い処理を追加する場合には別のファイルを作成し, そこに関数として処理を定義するほうが LLVM, clang のアップデートの際に変更が楽になるため良い.

\begin{lstlisting}[frame=lrbt,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}[frame=lrbt,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}[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,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,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,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}

\section{軽量継続の評価}
今回実装した CbC の軽量継続を評価する. 比較対象は C の関数呼び出しとし, それぞれを大量に行った時の時間の差を確認する. 計測に使用したコードはリスト \ref{calc},\ref{calcCbC} で, 結果は表\ref{comp} である.

結果より, 軽量継続が関数呼び出しよりも高速であることがわかる. 軽量継続では tail call elimination 等によってスタック操作の処理が省かれるのでその影響だろう.

\begin{lstlisting}[frame=lrbt,label=calc,caption={Cの計測用コード}]
#define LOOP 500000000

#include <stdio.h>
#include <stdlib.h>

int func4(int a, int b){
  return a+b;
}

int func3(int a, int b){
  return func4(b,b/a);
}

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

int func1(int a, int b){
  return func2(b,a+b);
}

int start_func(int loop){
  int i, a;
  a = 0;
  for (i=0;i<loop;i++)
    a += func1(1,2);
  return a;
}

int main( int ac, char *av[]){
  printf("%d\n",start_func(LOOP));
  return 0;
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCの計測用コード}]
#define LOOP 500000000

#include <stdio.h>
#include <stdlib.h>

__code code4(int a, int b, int loop, int ans){
  goto start_code(ans+a+b, loop-1);
}

__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);
}

__code code1(int a, int b, int loop, int ans){
  goto code2(b,a+b,loop, ans);
}

__code start_code(int ans, int loop){
  if (loop>0)
    goto code1(1,2,loop, ans);
  else
    goto print(ans);
}

int main( int ac, char *av[]){
  goto start_code(0,LOOP);
  return 0;
}

__code print(int a){
  printf("%d\n",a);
  exit(0);
}
\end{lstlisting}

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