Mercurial > hg > Papers > 2010 > kent-master
view gcc.tex @ 5:dfb89e32eea1
added gcc.tex, conclusion.tex
and some sources.
writed abstraction.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 08 Feb 2010 00:35:58 +0900 |
parents | |
children | 8ef81ff8cb52 |
line wrap: on
line source
\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ではこのようにアセンブラを出力した後、アセンブル、リンクまでを行う。 しかしそれらは本研究では関連しないので説明は割愛する。