\chapter{GCC, The Gnu Compiler Collection}
\section{GCC とは}


\subsection{cc1}
GCC はコンパイルだけではなく, アセンブルとリンクも行う.


\section{GCC の内部表現}
GCC-4.6 への実装の前に, GCC で扱われる内部表現について触れておく.

GCC は内部で Generic Tree, GIMPLE Tree, Tree SSA, RTL という4つの内部表現を扱う(GIMPLE と SSA は一緒に考えられることもある).
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE Tree, Tree SSA, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=100mm]{figure/ir.pdf}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.

CbC の実装ではパースの部分からこの Generic Tree 生成の部分に手が加わっている.

\subsection{GIMPLE Tree}
Generic Tree で表現されたデータは GIMPLE Tree に変換される.
GIMPLE Tree は Generic Tree より制約がかかった状態で作成された構文木となる.
制約は「1つの枝につく子が3つ以下になるように分解」等といったもので,
GIMPLE Tree へと変換されたデータは Generic Tree より簡単な命令で表されることになる.
CbC の実装では特に修正は加えていない.



\subsection{SSA}
Tree SSA (Static Single Assignment) は, プログラムの中で
変数が一度しか代入されないように変換させた構文木になる.
SSA に変換することで, 様々な最適化が行いやすくなる.
こちらも GIMPLE 同様 CbC の実装では特に修正は加えていない.



\subsection{RTL}
Tree SSA は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現であり, アセンブラとほぼ同じ命令の表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.