Mercurial > hg > Papers > 2010 > kent-master
diff gcc.tex @ 8:4b2af58b0302 probation_version
the version for probation.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 16 Feb 2010 14:04:40 +0900 |
parents | 8ef81ff8cb52 |
children |
line wrap: on
line diff
--- a/gcc.tex Fri Feb 12 13:10:57 2010 +0900 +++ b/gcc.tex Tue Feb 16 14:04:40 2010 +0900 @@ -10,17 +10,17 @@ たる予備知識としてGCCのプログラム構成について簡単に説明する。 -\section{ソースコードからアセンブラへ} +\section{コンパイル、アセンブル、リンク} GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで 行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に はそれらを統括しているだけである。 -言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ +言語に関する処理はcc1だけである。以降はこのプログラムcc1がどのようにソ ースコードをアセンブラに変換するかを説明する。 -\subsection{cc1} +\section{cc1} GCCではプログラムソースコードをアセンブラに変換する過程で Generic, GIMPLE, RTL という3つの内部表現を用いている。 @@ -69,20 +69,25 @@ をコンパイラが理解し、それぞれのブロック毎にアセンブラへの変換が可能に なる。 +\subsubsection{GimplifyとGIMPLE(SSA)} + フロントエンドではGenericを生成した後、ミドルエンドにデータを渡す前に -GenericをGIMPLEと呼ばれるデータ構造に変換する。GIMPLEはデータ構造とし -ては Genericと同じであるが、一つの枝に4つ以上の子がついてはいけないな -どの制限が付加されている。この制限はミドルエンド以降での解析を容易にし -、また種々の最適化はこのGIMPLEを対象として行われている。 +GenericをGIMPLEと呼ばれるデータ構造に変換する。この処理がGimplifyであ +る。GIMPLEはデータ構造としては Genericと同じであるが、一つの枝に4つ以 +上の子がついてはいけないなどの制限が付加されている。 + +この制限されたデータ構造は一般的には静的単一代入(Static Single +Assignment)と呼ばれており、様々な最適化を簡略化する事を目的として導入 +されている。 \subsection{ミドルエンドとRTL} -GCCは構文木GIMPLEの生成後、このGIMPLEを解析しながらRTLと呼ばれる中間コ -ードを生成する。RTLはアセンブラとほぼ同等の命令列を表現可能であり、ど -のアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存はな -いため、ミドルエンドは言語にもアーキテクチャにも依存しない、全ての GCC -コンパイラに共通のルーチンとなっている。 +GCCはフロントエンドにて構文木GIMPLEの生成後、このGIMPLEを解析しながら +RTLと呼ばれる中間コードを生成する。RTLはアセンブラとほぼ同等の命令列を +表現可能であり、どのアーキテクチャでも同じように扱われる。また、GIMPLE +にも言語の依存はないため、ミドルエンドは言語にもアーキテクチャにも依存 +しない、全ての GCC コンパイラに共通のルーチンとなっている。 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ @@ -107,6 +112,32 @@ ミドルエンドでは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} @@ -157,29 +188,27 @@ "mul%?\\t%0, %2, %1") \end{lstlisting} - -\subsection{最適化パス} -最適化はGCCの中でももっとも重要な機能の一つといえる。 -様々な最適化の手法がGCCにおいて実装され、実用化されている。 +\subsubsection{mdからソースコードへの変換} -GCCでは最適化は2つフェーズに分類される。 -一つはGIMPLEを対象とした最適化である。 -GIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どのコン -パイラにおいてもこの最適化を適用することができる。 -この最適化はミドルエンドで行われる。 +mdの記述は上記の様に単なる生成規則でしかない。そのため通常のプログラム +であれば実行時にmdデータを読み込みその通りに解釈する方法を取るが、コン +パイラの様な大規模なソフトウェアではそれでは処理に時間がかかりすぎる。 -もう一つはRTLを対象とした最適化である。 -RTLのデータ構造自体は言語にもアーキテクチャにも依存はないが、最適化に -はレジスタの数やスタックの操作法などに依存する事が多いため、この最適化 -ではいくつかの制限が入る。 -こちらはバックエンドでの実装である。 +そのためGCCではこのmdを直接プログラムに変換する手法を取っている。 +例として、\verb|i386.md|(x86アーキテクチャの生成規則である)は +\verb|insn-emit.c|や\verb|insn-output.c|などの、C言語ソースファイルに +変換され、バックエンドやその他のソースファイルと一緒にコンパイルされ、 +cc1プログラムの一部となる。この様子を図\ref{fig:insns}に表した。 -次章で説明するが、本研究では軽量継続の実装にGIMPLE対象の最適化である末 -尾呼び出し最適化を利用している。そのため、CbCの言語実装であるがミドル -エンドの修正も行っている。 +\begin{figure}[htpb] + \begin{center} + \includegraphics[width=.9\textwidth]{figures/insns.eps} + \end{center} + \caption{mdからソースコードを生成、さらにcc1をコンパイルする様子} + \label{fig:insns} +\end{figure} - -\subsection{GCC} +\section{GCC} 以上のようにGCCはフロントエンド、ミドルエンド、バックエンドがそれぞれ の役割を持ち、全体を通して最終的にアセンブラの生成を行う。