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

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

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

%AST はソースコードの解析結果を保持したツリーである。
%AST は “-Xclang -ast-dump” というオプションを付加することで表示することもできる。

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

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