--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc.tex	Mon Feb 08 00:35:58 2010 +0900
@@ -0,0 +1,189 @@
+\chapter{GNU コンパイラ コレクション}
+\label{chp:gcc}
+
+GNU コンパイラ コレクション（以下GCC）はフリーソフトウェア財団によって
+管理されているオープンソースのコンパイラ群である。
+C, C++, Java, FORTRANなどの様々な言語に対応しており、UNIX系OSの標準的
+なコンパイラとして用いられている。
+
+本研究におけるCbCコンパイラの実装対象もこのGCCとなる。本章では実装に当
+たる予備知識としてGCCのプログラム構成について簡単に説明する。
+
+
+\section{ソースコードからアセンブラへ}
+
+GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで
+行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン
+クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に
+はその統括をしているだけである。
+
+言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ
+ースコードをアセンブラに変換するかを説明する。
+
+\subsection{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{GCC}
+  \label{fig:gcc-flow}
+\end{figure}
+
+
+\subsection{フロントエンドとGeneric, GIMPLE}
+
+フロントエンドはコンパイラ中で直接ソースコードを解析するルーチンのこと
+である。ソースコードの解析はコンパイルする言語毎に異なるため、フロント
+エンドの実装もC, C++, Javaなどで様々である。言語によって異なるソースコ
+ードを解析し、その結果をGenericという構文木（プログラムの構造を表すデー
+タ構造）に変換するのがフロントエンドの役割となる。
+
+構文木Genericは関数の宣言や繰返し制御構造、条件分岐、リターン文など、
+プログラムの構造を全てツリー構造で表現することができる。
+この構文木は言語に依存しないため、言語設計者は通常はミドルエンド以降に
+ついては考慮する必要はない。
+
+構文木がプログラムをデータ構造として表す様子を図
+\ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example}
+の関数\verb|funcA|を解析した結果を構文木で表現している。
+
+\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|などのディレクティブ
+を除くソースコードの全てを構文木で表現する。これによりプログラムの文脈
+をコンパイラが理解し、それぞれのブロック毎にアセンブラへの変換が可能に
+なる。
+
+フロントエンドではGenericを生成した後、ミドルエンドにデータを渡す前に
+GenericをGIMPLEと呼ばれるデータ構造に変換する。GIMPLEはデータ構造とし
+ては Genericと同じであるが、一つの枝に4つ以上の子がついてはいけないな
+どの制限が付加されている。この制限はミドルエンド以降での解析を容易にし
+、また種々の最適化はこのGIMPLEを対象として行われている。
+
+
+\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の命令列を作成し、バックエンド
+に処理を引き渡している。
+
+
+\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の文字列か、もしくは文字列を出力する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}と
+形が似ていることが分かる。
+3行目が条件である。バックエンドプログラムの変数などをチェックしている。
+そして4行目が出力するアセンブラである。ここでは``\verb|%?|''や
+``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。
+
+\begin{lstlisting}[caption=ARMでのMachine Descriptionの例
+                   （コード\ref{code:rtl-example}をアセンブラに変換）,
+                   label=code:md-example,language=Lisp]
+(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}
+
+
+\subsection{最適化パス}
+最適化はGCCの中でももっとも重要な機能の一つといえる。
+様々な最適化の手法がGCCにおいて実装され、実用化されている。
+
+GCCではこの最適化は2つフェーズに分類される。
+一つはGIMPLEを対象とした最適化である。
+このGIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どの
+コンパイラにおいてもこの最適化を適用することができる。
+この最適化はミドルエンドで行われる。
+
+もう一つはRTLを対象とした最適化である。
+RTLのデータ構造自体は言語にもアーキテクチャにも依存はないが、最適化に
+はレジスタの数やスタックの操作法などに依存する事が多いため、この最適化
+ではいくつかの制限が入る。
+こちらはバックエンドでの実装である。
+
+次章で説明するが、本研究では軽量継続の実装にGIMPLE対象の最適化である末
+尾呼び出し最適化を利用している。そのため、CbCの言語実装であるがミドル
+エンドの修正も行っている。
+
+
+\subsection{GCC}
+
+以上のようにGCCはフロントエンド、ミドルエンド、バックエンドがそれぞれ
+の役割を持ち、全体を通して最終的にアセンブラの生成を行う。
+
+GCCではこのようにアセンブラを出力した後、アセンブル、リンクまでを行う。
+しかしそれらは本研究では関連しないので説明は割愛する。
+
+