\chapter{LLVM, clang}
\label{chapter:LLVM/clang}
LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる. LLVM を利用する各コンパイラフロントエンドはターゲットとなるプログラミング言語を LLVM IR に変換することで LLVM の持つ最適化機構を利用する. 

clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
GCC と比較すると丁寧でわかりやすいエラーメッセージを出力する, コンパイル時間が短いといった特徴を持つ.


\section{clang の基本構造}
\label{sec:clang}
clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている. 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.35}{\includegraphics{fig/clangProcess.pdf}}
 \end{center}
 \caption{clang の 処理過程}
 \label{fig:clangProcess}
\end{figure}

AST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 例えばリスト\ref{ASTSampleCode}コンパイル時にオプション ``-Xclang -ast-dump'' を付与した場合は出力結果としてリスト\ref{AST}が得られる. 出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. それぞれの簡単な説明を以下に記す.

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

AST の他に本研究において重要な clang のクラスに 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.4}{\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 を辿ることで完全な型を知ることができる.


\section{LLVM の基本構造}
\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.35}{\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.50}{\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 のリストとなっている.

Machine Code の一例を以下のリスト \ref{MachineCodeSSA}, \ref{MachineCodeNonSSA}に示す. リスト \ref{MachineCodeSSA} が SSA 形式, リスト \ref{MachineCodeNonSSA} が non-SSA 形式であり, 元となるコードはリスト \ref{IRtestC} である. \%varg1, \%varg2 といったものが仮想レジスタであり, リスト \ref{MachineCodeSSA} に多く存在することが確認できる. しかし, リスト \ref{MachineCodeNonSSA} には1行目を除いてそれが存在しない. 1行目はこの関数の引数に対応する物理レジスタと仮想レジスタを並べて表記しているだけなので, ここに仮想レジスタが残っていることについて問題はなく, non-SSA 形式の Machine Code では仮想レジスタが取り除かれていることがわかる.
\begin{lstlisting}[frame=lrbt, label=MachineCodeSSA, caption={Machine Code (SSA)}]
Function Live Ins: %EDI in %vreg4, %ESI in %vreg5

BB#0: derived from LLVM BB %entry
    Live Ins: %EDI %ESI
%vreg5<def> = COPY %ESI
%vreg4<def> = COPY %EDI
%vreg6<def> = MOV32r0 %EFLAGS<imp-def,dead>
    Successors according to CFG: BB#1

BB#1: derived from LLVM BB %while.cond
    Predecessors according to CFG: BB#0 BB#2
%vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#2>
%vreg1<def> = PHI %vreg6, <BB#0>, %vreg2, <BB#2>
%vreg7<def,tied1> = SUB32rr %vreg0<tied0>, %vreg5, %EFLAGS<imp-def>
JG_4 <BB#3>, %EFLAGS<imp-use>
JMP_4 <BB#2>
    Successors according to CFG: BB#2(124) BB#3(4)

BB#2: derived from LLVM BB %while.body
    Predecessors according to CFG: BB#1
%vreg2<def,tied1> = ADD32rr %vreg1<tied0>, %vreg0, %EFLAGS<imp-def,dead>
%vreg3<def,tied1> = INC64_32r %vreg0<tied0>, %EFLAGS<imp-def,dead>
JMP_4 <BB#1>
    Successors according to CFG: BB#1

BB#3: derived from LLVM BB %while.end
    Predecessors according to CFG: BB#1
%vreg8<def,tied1> = IMUL32rr %vreg4<tied0>, %vreg5, %EFLAGS<imp-def,dead>
%vreg9<def,tied1> = SUB32rr %vreg1<tied0>, %vreg8<kill>, %EFLAGS<imp-def,dead>
%EAX<def> = COPY %vreg9
RET %EAX
\end{lstlisting}

\begin{lstlisting}[frame=lrbt, label=MachineCodeNonSSA, caption={Machine Code (non-SSA)}]
Function Live Ins: %EDI in %vreg4, %ESI in %vreg5

0B    BB#0: derived from LLVM BB %entry
        Live Ins: %EDI %ESI
48B        %EAX<def> = MOV32r0 %EFLAGS<imp-def,dead>
64B        %ECX<def> = COPY %EDI
        Successors according to CFG: BB#1

96B    BB#1: derived from LLVM BB %while.cond
        Live Ins: %ESI %EDI %ECX %EAX
        Predecessors according to CFG: BB#0 BB#2
144B        CMP32rr %ECX, %ESI, %EFLAGS<imp-def>
160B        JG_4 <BB#3>, %EFLAGS<imp-use,kill>
176B        JMP_4 <BB#2>
        Successors according to CFG: BB#2(124) BB#3(4)

192B    BB#2: derived from LLVM BB %while.body
        Live Ins: %ESI %EDI %ECX %EAX
        Predecessors according to CFG: BB#1
224B        %EAX<def,tied1> = ADD32rr %EAX<kill,tied0>, %ECX, %EFLAGS<imp-def,dead>
256B        %ECX<def,tied1> = INC64_32r %ECX<kill,tied0>, %EFLAGS<imp-def,dead>
304B        JMP_4 <BB#1>
        Successors according to CFG: BB#1

320B    BB#3: derived from LLVM BB %while.end
        Live Ins: %ESI %EDI %EAX
        Predecessors according to CFG: BB#1
352B        %EDI<def,tied1> = IMUL32rr %EDI<kill,tied0>, %ESI<kill>, %EFLAGS<imp-def,dead>
384B        %EAX<def,tied1> = SUB32rr %EAX<kill,tied0>, %EDI<kill>, %EFLAGS<imp-def,dead>
416B        RET %EAX
\end{lstlisting}

MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. MC Layer が扱うデータ構造は複数あるが, ここでは MCInst, MCStreamer, MCOperand について説明する.

MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令を出力するには MCInst クラスを用いる.

MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.

MCOperand はオペランドに対応し, MCInst はこのクラスを用いる.

MC Layer で用いられる各クラスも ``-mllvm -asm-show-inst'' オプションを用いることで他の中間表現のように確認することが出来る. MCInst はアセンブリの各命令に対応しているので, アセンブリファイルにコメントとして出力される. リスト \ref{MCInst} は\ref{IRtestC} をコンパイルして得られるアセンブリコードの一部である. 各命令の隣にコメントで記されているのが MCInst, 下に記されているのが MCOperand である. 

\begin{lstlisting}[frame=lrbt, label=MCInst, caption={アセンブリコードと MCInst}]
  _add:                                   ## @add
      .cfi_startproc
  ## BB#0:                                ## %entry
      pushq   %rbp                    ## <MCInst #2300 PUSH64r
  ##  <MCOperand Reg:36>>
  Ltmp0:
      .cfi_def_cfa_offset 16
  Ltmp1:
      .cfi_offset %rbp, -16
      movq    %rsp, %rbp              ## <MCInst #1684 MOV64rr
  ##  <MCOperand Reg:36>
  ##  <MCOperand Reg:44>>
  Ltmp2:
      .cfi_def_cfa_register %rbp
      addl    %esi, %edi              ## <MCInst #97 ADD32rr
  ##  <MCOperand Reg:23>
  ##  <MCOperand Reg:23>
  ##  <MCOperand Reg:29>>
      movl    %edi, %eax              ## <MCInst #1665 MOV32rr
  ##  <MCOperand Reg:19>
  ##  <MCOperand Reg:23>>
      popq    %rbp                    ## <MCInst #2178 POP64r
  ##  <MCOperand Reg:36>>
      retq                            ## <MCInst #2460 RETQ>
\end{lstlisting}

\section{Tail call elimination}
前述した通り, LLVM の処理は最適化を含め全て pass によって行われるため, pass を選択することで任意の最適化をかけることができる. 独自の pass を作ることも可能であり, pass 作成のチュートリアルは LLVM のドキュメント\cite{LLVM}にも記されている. また, pass の雛形となるクラスも用意されており, 独自の pass を作成する環境は整っていると言える.

最適化機構は本研究においてはほとんど関係しないが, 継続の実装に関わる Tail Call Elimination, 関数呼び出し時のフレームポインタ操作の最適化を行う omit leaf frame pointer だけは別である. 

%%Tail Call Elimination は, 通常 call 命令を使用するべき関数呼び出しで jmp 命令を用いるという最適化である. code segment は call でなく jmp で遷移する必要が有るため, CbC コンパイラでは code segment に対してこの最適化がかかるよう強制しなければならない.

Tail call elimination の説明の前にまず, tail call について簡単に説明する. tail call は, ある関数の持つ処理の一番最後に位置し, 呼び出し元が戻り値を返す場合は呼び出された関数の戻り値がそのまま呼び出し元の戻り値として返されるような関数呼び出しのことを指す. 具体的には以下のリスト \ref{tailCall} の 関数B, 関数C の呼び出しがそれに当たる. Tail call elimination はこの末尾にある関数呼び出しの最適化を行う. 通常, 関数呼び出しはアセンブルされると call 命令に置き換わるが, tail call elimination ではその代わりに jmp 命令を用いる. その様子を関数Bの呼び出しに注目し, 関数 caller が main 関数から呼ばれるとして図示したものが以下の図\ref{fig:TCE}である. 通常の関数呼び出しの場合, 関数 caller に呼び出された関数 B はその処理を終えると ret 命令により一度関数 caller に戻る. そして再び ret 命令を用いることで main 関数に戻る. Tail call elimination ではこの関数 B から関数 caller に戻る無駄な処理を低減する. 図\ref{fig:TCE}より, 関数 caller が関数 B を呼び出す時の命令が call から jmp にかわり, 関数 B は処理を終えると直接 main 関数に戻っていることがわかる.
\begin{lstlisting}[frame=lrbt, label=tailCall, caption={Tail call の例}]
void caller(){
  A();
  if ( condition )
    B();
    return;
  else
    C();
    return;
}
\end{lstlisting}
\begin{figure}[htpb]
    \begin{center}
      \scalebox{0.4}{\includegraphics{fig/TCE.pdf}}
    \end{center}
    \caption{Tail call elimination}
    \label{fig:TCE}
\end{figure}


では次に, Tail call elimination によって実際にアセンブリコードがどのように変化するかを確認する. この例では x64 形式のアセンブリ命令セットを使用する. リスト\ref{tailCall}のコードでは分かり辛いので, 図\ref{fig:TCE}の関数をそれぞれリスト\ref{tailCall2}のように再定義する.
\begin{lstlisting}[frame=lrbt, label=tailCall2, caption={caller, B, main 関数の定義}]
void B(int a, int b, int c, int d){
  return;
}

void caller(int a, int b, int c){
  B(a, b, c, 40);
  return;
}

int main(){
  caller(10, 20, 30);
  return 0;
}
\end{lstlisting}

これを tail call elimination を行わずにコンパイルしたものが以下のリスト \ref{asmCaller}, tail call elimination を行いコンパイルしたものがリスト \ref{asmCallerTCE} である. なお, tail call elimination の影響を受けるのは関数 caller のみなのでその部分のみ記載する.

\begin{minipage}[t]{0.5\textwidth}
  \begin{lstlisting}[frame=lrbt, label=asmCaller, caption={関数 caller (tail call elimination 無し)}]
_caller:                                ## @caller
	.cfi_startproc
## BB#0:                                ## %entry
	pushq	%rbp
Ltmp7:
	.cfi_def_cfa_offset 16
Ltmp8:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
Ltmp9:
	.cfi_def_cfa_register %rbp
	movl	$40, %ecx
	callq	_B
	popq	%rbp
	ret
	.cfi_endproc
  \end{lstlisting}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
  \begin{lstlisting}[frame=lrbt, label=asmCallerTCE, caption={関数 caller (tail call elimination 有り)}]
_caller:                                ## @caller
	.cfi_startproc
## BB#0:                                ## %entry
	pushq	%rbp
Ltmp7:
	.cfi_def_cfa_offset 16
Ltmp8:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
Ltmp9:
	.cfi_def_cfa_register %rbp
	movl	$40, %ecx
	popq	%rbp
	jmp	_B                      ## TAILCALL
	.cfi_endproc
  \end{lstlisting}
\end{minipage}

二つのアセンブリを比較すると, tail call elimination を行った方では call 命令を用いずに jmp 命令で 関数 B に移動していることがわかる. 移動の前に popq を \%rbp に対して行っているのはベースポインタの値を戻しておき, 関数 B から直接 main 関数に戻れるようにするためである. 尚, GCC では tail call elimination を行っていない場合には関数呼び出し前にスタックの値を操作する処理が入っていたが, LLVM ではそれが行われていない. これについて, LLVM では tail call elimination を行っていない場合でも関数呼び出しが末尾にある場合には, その関数に戻ることがないことが自明であることから, 現在のスタックに割り当てられたスタックフレームをそのまま使用するようにしているのだろう. 

\section{Tail call elimination の要件}
\label{sec:TCE}
Tail call elimination は 全ての tail call に対して行えるわけではなく, 行うためにはいくつかの条件を満たさなければならない. この条件は LLVM Document\cite{LLVM}に記されている. 現在 LLVM では x86/x86-64, PowerPC を tail call elimination のサポート対象としている. 今回の実装では x86/x86-64 を対象としたので, そちらの条件について考える. x86/x86-64 での tail call elimination の要件は以下のようになっている.

\begin{enumerate}
  \item 呼び出し元と呼び出す関数の呼び出し規約が fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかである.
  \item 対象となる関数呼び出しが tail call である.
  \item 最適化のオプションである tailcallopt が有効になっている. 
  \item 対象関数が可変長引数を持たない.
  \item GOT (Global Offset Table) / PIC (Position Independent Code) を生成する場合, visibility が hidden か protect でなければならない.
\end{enumerate}

これらの条件のうち, コンパイラ側でサポートする必要のある条件について考える. 3つめの条件にある tailcallopt は有効化することで tail call elimination を行うようになるオプションである. しかし tail call elimination を行うためには 関数呼び出しに対して tail フラグを立てる必要がある. これは Tail Call Elimination pass によって付与されるので, CbC コンパイラではこのパスをオプションに関わらず無条件で追加しなければならない. 4つめの条件にある可変長引数について, CbC では可変長引数の機能は data segment を用いてサポートすることになるだろう. data segment は現在 CbC には未実装なので今の段階では可変長引数を持つ code segment を作ることは出来ない. 5つめの条件について, LLVM を用いて PIC を生成する場合には -fPIC というオプションを付加する必要がある. 本論文の主旨から大きく離れるため詳しくは説明しないが, PIC は主に共有ライブラリなどに用いられる, 絶対アドレスにかかわらず正しく実行できるコードの形式, GOT は PIC がアクセスする全グローバル変数のアドレスを格納しているテーブルである. この条件の達成はユーザーに委ねられる. 

これらのことから, code segment に対して tail call elimination を行うために達成しなければならない条件は以下のようになることがわかる.
\begin{itemize}
  \item 呼び出し規約を fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかに指定.
  \item code segment を tail call にする.
  \item tailcallopt の有効化.
  \item 最適化レベルに関わらず Tail call elimination pass を追加.
\end{itemize}

\section{omit leaf frame pointer}

omit leaf frame pointer は関数呼び出しの際に行われるフレームポインタ操作に関わる最適化である. 通常関数呼び出しを行う際にはフレームポインタの値をスタックに積み, return 直前に戻すという作業を行う. omit leaf frame pointer はこの操作を leaf function を呼び出す際に行わないようにする最適化である.

leaf function とはコールツリーの終端の位置する関数のことを指し, この関数が関数を呼び出さないことを意味する.


以下のリスト \ref{loptno}, \ref{lopt} はどちらもアセンブリコードから leaf function の部分を抜き出したものであり, 前者が omit leaf frame pointer 無し, 後者が omit leaf frame pointer ありのコードである. push, pop 命令によるフレームポインタの操作がリスト \ref{lopt} ではなくなっていることがわかる.

\begin{minipage}[t]{0.5\textwidth}
  \begin{lstlisting}[frame=lrbt, label=loptno, caption={関数 caller (omit leaf frame pointer 無し)}]
_caller:                                ## @caller
  .cfi_startproc
## BB#0:
  pushq»  %rbp
Ltmp0:
  .cfi_def_cfa_offset 16
Ltmp1:
  .cfi_offset %rbp, -16
  movq»   %rsp, %rbp
Ltmp2:
  .cfi_def_cfa_register %rbp
  movl»   %edi, -4(%rbp)
  movl»   %esi, -8(%rbp)
  movl»   -4(%rbp), %esi
  addl»   -8(%rbp), %esi
  movl»   %esi, %eax
  popq»   %rbp
  retq
  .cfi_endproc
  \end{lstlisting}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
  \begin{lstlisting}[frame=lrbt, label=lopt, caption={関数 caller (omit leaf frame pointer 有り)}]
_caller:                                ## @caller
  .cfi_startproc
## BB#0:
  movl»   %edi, -4(%rbp)
  movl»   %esi, -8(%rbp)
  movl»   -4(%rbp), %esi
  addl»   -8(%rbp), %esi
  movl»   %esi, %eax
  retq
  .cfi_endproc
  \end{lstlisting}
\end{minipage}

CbC の code segment は関数呼び出しでなく継続によって処理の遷移を行っていくため, 全ての code segment が leaf function ということになる. したがって CbC はこの最適化と非常に相性が良く, 本研究ではこの最適化の強制も行った.