--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/gcc.tex	Tue Feb 16 14:35:36 2010 +0900
@@ -0,0 +1,219 @@
+\chapter{GNU コンパイラ コレクション}
+\label{chp:gcc}
+
+GNU コンパイラ コレクション（以下GCC）はフリーソフトウェア財団によって
+管理されているオープンソースのコンパイラ群である。
+C, C++, Java, FORTRANなどの様々な言語に対応しており、UNIX系OSの標準的
+なコンパイラとして用いられている。
+
+本研究におけるCbCコンパイラの実装対象もこのGCCとなる。本章では実装に当
+たる予備知識としてGCCのプログラム構成について簡単に説明する。
+
+
+\section{コンパイル、アセンブル、リンク}
+
+GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで
+行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン
+クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に
+はそれらを統括しているだけである。
+
+言語に関する処理はcc1だけである。以降はこのプログラムcc1がどのようにソ
+ースコードをアセンブラに変換するかを説明する。
+
+\section{cc1}
+
+GCCではプログラムソースコードをアセンブラに変換する過程で Generic,
+GIMPLE, RTL という3つの内部表現を用いている。
+これらの内部表現とソースコード、アセンブラ間の変換はフロントエンド、ミ
+ドルエンド、バックエンドが担当している。図\ref{fig:gcc-flow}にその様子
+を示す。
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[width=.8\textwidth]{figures/gcc-flow.eps}
+  \end{center}
+  \caption{cc1でのデータフロー(Generic, GIMPLE, RTL)}
+  \label{fig:gcc-flow}
+\end{figure}
+
+
+\subsection{フロントエンドとGeneric, GIMPLE}
+
+フロントエンドはコンパイラ中で直接ソースコードを解析するルーチンのこと
+である。ソースコードの解析はコンパイルする言語毎に異なるため、フロント
+エンドの実装もC, C++, Javaなどで様々である。言語によって異なるソースコ
+ードを解析し、その結果をGenericという構文木（プログラムの構造を表すデー
+タ構造）に変換するのがフロントエンドの役割となる。
+
+構文木Genericは関数の宣言や繰返し制御構造、条件分岐、リターン文など、
+プログラムの構造を全てツリー構造で表現することができる。
+この構文木は言語に依存しないため、言語設計者は通常はミドルエンド以降に
+ついては考慮する必要はない。
+
+構文木がプログラムをデータ構造として表す様子を図
+\ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example}
+の関数\verb|funcT|を解析した結果を構文木で表現している。
+
+\begin{figure}[htpb]
+  \lstinputlisting
+    [caption=C言語の解析例（解析結果は図\ref{fig:tree-example}）,
+     label=code:tree-example]
+    {sources/tree-example.c}
+  \begin{center}
+    \includegraphics[width=.8\textwidth]{figures/tree-example.eps}
+  \end{center}
+  \caption{コード\ref{code:tree-example}の構文木の例}
+  \label{fig:tree-example}
+\end{figure}
+図のように、一般的なコンパイラでは\verb|#include|などのディレクティブ
+を除くソースコードの全てを構文木で表現する。これによりプログラムの文脈
+をコンパイラが理解し、それぞれのブロック毎にアセンブラへの変換が可能に
+なる。
+
+\subsubsection{GimplifyとGIMPLE(SSA)}
+
+フロントエンドではGenericを生成した後、ミドルエンドにデータを渡す前に
+GenericをGIMPLEと呼ばれるデータ構造に変換する。この処理がGimplifyであ
+る。GIMPLEはデータ構造としては Genericと同じであるが、一つの枝に4つ以
+上の子がついてはいけないなどの制限が付加されている。
+
+この制限されたデータ構造は一般的には静的単一代入(Static Single
+Assignment)と呼ばれており、様々な最適化を簡略化する事を目的として導入
+されている。
+
+
+\subsection{ミドルエンドとRTL}
+
+GCCはフロントエンドにて構文木GIMPLEの生成後、このGIMPLEを解析しながら
+RTLと呼ばれる中間コードを生成する。RTLはアセンブラとほぼ同等の命令列を
+表現可能であり、どのアーキテクチャでも同じように扱われる。また、GIMPLE
+にも言語の依存はないため、ミドルエンドは言語にもアーキテクチャにも依存
+しない、全ての GCC コンパイラに共通のルーチンとなっている。
+
+しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特
+に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ
+の場合はアーキテクチャが対応してるか否かを判別するために次項に紹介する
+Machine Descriptionが使われるため、共通のミドルエンドが使われることに
+変わりはない。
+
+RTLはプログラム上はツリー構造として扱われるが、デバッグ表示や次のバッ
+クエンドで使うMachine Descriptionのため、S式を用いた表現が用いられてい
+る。例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表
+現は以下のようになる。
+
+\begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例,
+                   label=code:rtl-example,language=Lisp]
+(set (reg/f:SI 54 virtual-stack-vars)
+     (mult:SI (reg:SI 58)
+              (const_int 20 [0x14])))
+\end{lstlisting}
+
+この例では\verb|(reg:SI 58)|で表される仮想レジスタの値と定数20との積を
+、\verb|(reg/f:SI 54)|で表されるレジスタにセットしている。
+ミドルエンドではGIMPLEを元にこの様なRTLの命令列を作成し、バックエンド
+に処理を引き渡している。
+
+\subsubsection{最適化パス}
+最適化はGCCの中でももっとも重要な機能の一つといえる。
+様々な最適化の手法がGCCにおいて実装され、実用化されている。
+
+GCCでは最適化は2つフェーズに分類される。
+
+一つはGIMPLEを対象とした最適化である。 GIMPLEは、アーキテクチャはもち
+ろん言語仕様にも依存しないため、どのコンパイラにおいてもこの最適化を適
+用することができる。
+
+もう一つはRTLを対象とした最適化である。 RTLのデータ構造自体は言語にも
+アーキテクチャにも依存はないが、最適化にはレジスタの数やスタックの操作
+法などに依存する事が多いため、この最適化ではいくつかの制限が入る。
+
+ミドルエンドには``pass''という概念があり、最適化処理やGIMPLEの変換、そ
+の他諸々の処理は、その処理のメインルーチンをpassに登録することでミドル
+エンド上にて実行可能になる。
+
+passの登録順序にも意味があり、passの前半部はGIMPLE対象の最適化など、続
+いてGIMPLEからRTLへの変換処理、後半部にはRTLの最適化処理が登録されてい
+る。
+
+次章で説明するが、本研究では軽量継続の実装にGIMPLE対象の最適化である末
+尾呼び出し最適化を利用している。そのため、CbCの言語実装であるがミドル
+エンドの修正も行っている。
+
+
+\subsection{バックエンドとMachine Description}
+
+バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し
+ている。この処理は必然的にターゲットとするアーキテクチャにより処理が異
+なるため、バックエンドはアーキテクチャ毎に用意されることになる。
+
+アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine
+Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに
+それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。
+
+mdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する必要
+がある。
+\begin{itemize}
+  \item その変換規則の名前
+
+    GCCのプログラムから関数として呼び出すための名前である。
+  \item 変換するRTLの構造（パターンマッチ）
+    
+    この規則がどのようなRTLを変換できるかを表す。
+  \item 変換する条件
+
+    上記のパターンだけでは判別できない時の追加条件をCの構文で記述する。
+  \item 出力するアセンブラ
+
+    アセンブラ文字列か、もしくはアセンブラ文字列を出力するCの構文を記
+    述する。
+\end{itemize}
+
+例としてARMアーキテクチャにおけるmdを一つ、コード
+\ref{code:md-example}に示す。このmdはコード\ref{code:rtl-example}で紹
+介した乗算命令のRTLにマッチし、アセンブラ``\verb|mul r0 r2 r1|'' を出
+力する。
+2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と
+形が似ていることが分かる。
+5行目が条件である。バックエンドプログラムの変数などをチェックしている。
+そして6行目が出力するアセンブラである。ここでは``\verb|%?|''や
+``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。
+
+\begin{lstlisting}[caption=ARMでのMachine Descriptionの例
+                   （コード\ref{code:rtl-example}をアセンブラに変換）,
+                   label=code:md-example,language=Lisp,numbers=left]
+(define_insn "*arm_mulsi3"
+  [(set (match_operand:SI          0 "s_register_operand" "=&r,&r")
+        (mult:SI (match_operand:SI 2 "s_register_operand" "r,r")
+                 (match_operand:SI 1 "s_register_operand" "%?r,0")))]
+  "TARGET_32BIT && !arm_arch6"
+  "mul%?\\t%0, %2, %1")
+\end{lstlisting}
+
+\subsubsection{mdからソースコードへの変換}
+
+mdの記述は上記の様に単なる生成規則でしかない。そのため通常のプログラム
+であれば実行時にmdデータを読み込みその通りに解釈する方法を取るが、コン
+パイラの様な大規模なソフトウェアではそれでは処理に時間がかかりすぎる。
+
+そのためGCCではこのmdを直接プログラムに変換する手法を取っている。
+例として、\verb|i386.md|（x86アーキテクチャの生成規則である）は
+\verb|insn-emit.c|や\verb|insn-output.c|などの、C言語ソースファイルに
+変換され、バックエンドやその他のソースファイルと一緒にコンパイルされ、
+cc1プログラムの一部となる。この様子を図\ref{fig:insns}に表した。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[width=.9\textwidth]{figures/insns.eps}
+  \end{center}
+  \caption{mdからソースコードを生成、さらにcc1をコンパイルする様子}
+  \label{fig:insns}
+\end{figure}
+
+\section{GCC}
+
+以上のようにGCCはフロントエンド、ミドルエンド、バックエンドがそれぞれ
+の役割を持ち、全体を通して最終的にアセンブラの生成を行う。
+
+GCCではこのようにアセンブラを出力した後、アセンブル、リンクまでを行う。
+しかしそれらは本研究では関連しないので説明は割愛する。
+
+