\chapter{LLVM/clang による CbC の実装}
\section{LLVM clang}
LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。
LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。
また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。

clang は LLVM をバックエンドとして利用する C/C++/Ob jective-C のコンパイラである。

\section{LLVM の基本構造}
LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない。
LLVM では、最適化や中間表現の変換を何段階か行う。
この変換を行う処理は全て pass が行う。
多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。
pass には以下のようなものがある。

\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/clang のデバッグ}
LLVM/clang で CbC をコンパイルした際 Code Gear 内 の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。

局所変数でポインタを参照していると clang は生成する LLVM IR にオブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。

ここでリスト\ref{ir_b}のようにオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。

しかし CbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。
そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。

修正後に生成された LLVM IR コード(リスト\ref{ir_a})では tail call の直前に生成された。

\begin{lstlisting}[frame=lrbt,label=ir_a,caption={\footnotesize LLVM IR コード 修正前}]
if.then:                                          ; preds = %entry
  %code_stack = getelementptr inbounds %struct.Context, %struct.Context* %context, i64 0, i32 8
  %4 = load %struct.stack*, %struct.stack** %code_stack, align 8, !tbaa !7
  %next = getelementptr inbounds %struct.Context, %struct.Context* %context, i64 0, i32 0
  %call1 = call i32 (%struct.stack*, i32*, ...) bitcast (i32 (...)* @stack_pop to i32 (%struct.stack*, i32*, ...)*)(%struct.stack* %4, i32* %next) #3
  %5 = load i32, i32* %next, align 8, !tbaa !11
  tail call fastcc void @meta(%struct.Context* nonnull %context, i32 %5) #3
  br label %cleanup

if.end:                                           ; preds = %entry
  %6 = load %struct.stack*, %struct.stack** %node_stack, align 8, !tbaa !24
  %call4 = call i32 (%struct.stack*, %struct.Node**, ...) bitcast (i32 (...)* @stack_push to i32 (%struct.stack*, %struct.Node**, ...)*)(%struct.stack*     %6, %struct.Node** nonnull %parent) #3
  tail call fastcc void @meta(%struct.Context* nonnull %context, i32 18) #3
  br label %cleanup

cleanup:                                          ; preds = %if.end, %if.then
  call void @llvm.lifetime.end(i64 8, i8* %0) #3
  ret void
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=ir_b,caption={\footnotesize LLVM IR コード 修正後}]
if.then:                                          ; preds = %entry
  %code_stack = getelementptr inbounds %struct.Context, %struct.Context* %context, i64 0, i32 8
  %4 = load %struct.stack*, %struct.stack** %code_stack, align 8, !tbaa !7
  %next = getelementptr inbounds %struct.Context, %struct.Context* %context, i64 0, i32 0
  %call1 = call i32 (%struct.stack*, i32*, ...) bitcast (i32 (...)* @stack_pop to i32 (%struct.stack*, i32*, ...)*)    (%struct.stack* %4, i32* %next) #3
  %5 = load i32, i32* %next, align 8, !tbaa !11
  call void @llvm.lifetime.end(i64 8, i8* %0) #3
  tail call fastcc void @meta(%struct.Context* nonnull %context, i32 %5) #3
  br label %cleanup
  
if.end:                                           ; preds = %entry
  %6 = load %struct.stack*, %struct.stack** %node_stack, align 8, !tbaa !24
  %call4 = call i32 (%struct.stack*, %struct.Node**, ...) bitcast (i32 (...)* @stack_push to i32 (%struct.stack*, %    struct.Node**, ...)*)(%struct.stack* %6, %struct.Node** nonnull %parent) #3
  call void @llvm.lifetime.end(i64 8, i8* %0) #3
  tail call fastcc void @meta(%struct.Context* nonnull %context, i32 18) #3
  br label %cleanup
  
cleanup:                                          ; preds = %if.end, %if.then
  ret void
\end{lstlisting}