Mercurial > hg > Papers > 2010 > kent-master

comparison gcc.tex @ 5:dfb89e32eea1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
4:30c102343b37 5:dfb89e32eea1
1 \chapter{GNU コンパイラ コレクション}
2 \label{chp:gcc}
3
4 GNU コンパイラ コレクション（以下GCC）はフリーソフトウェア財団によって
5 管理されているオープンソースのコンパイラ群である。
6 C, C++, Java, FORTRANなどの様々な言語に対応しており、UNIX系OSの標準的
7 なコンパイラとして用いられている。
8
9 本研究におけるCbCコンパイラの実装対象もこのGCCとなる。本章では実装に当
10 たる予備知識としてGCCのプログラム構成について簡単に説明する。
11
12
13 \section{ソースコードからアセンブラへ}
14
15 GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで
16 行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン
17 クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に
18 はその統括をしているだけである。
19
20 言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ
21 ースコードをアセンブラに変換するかを説明する。
22
23 \subsection{cc1}
24
25 GCCではプログラムソースコードをアセンブラに変換する過程で Generic,
26 GIMPLE, RTL という3つの内部表現を用いている。
27 これらの内部表現とソースコード、アセンブラ間の変換はフロントエンド、ミ
28 ドルエンド、バックエンドが担当している。図\ref{fig:gcc-flow}にその様子
29 を示す。
30 \begin{figure}[htpb]
31 \begin{center}
32 \includegraphics[width=.8\textwidth]{figures/gcc-flow.eps}
33 \end{center}
34 \caption{GCC}
35 \label{fig:gcc-flow}
36 \end{figure}
37
38
39 \subsection{フロントエンドとGeneric, GIMPLE}
40
41 フロントエンドはコンパイラ中で直接ソースコードを解析するルーチンのこと
42 である。ソースコードの解析はコンパイルする言語毎に異なるため、フロント
43 エンドの実装もC, C++, Javaなどで様々である。言語によって異なるソースコ
44 ードを解析し、その結果をGenericという構文木（プログラムの構造を表すデー
45 タ構造）に変換するのがフロントエンドの役割となる。
46
47 構文木Genericは関数の宣言や繰返し制御構造、条件分岐、リターン文など、
48 プログラムの構造を全てツリー構造で表現することができる。
49 この構文木は言語に依存しないため、言語設計者は通常はミドルエンド以降に
50 ついては考慮する必要はない。
51
52 構文木がプログラムをデータ構造として表す様子を図
53 \ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example}
54 の関数\verb|funcA|を解析した結果を構文木で表現している。
55
56 \begin{figure}[htpb]
57 \lstinputlisting
58 [caption=C言語の解析例（解析結果は図\ref{fig:tree-example}）,
59 label=code:tree-example]
60 {sources/tree-example.c}
61 \begin{center}
62 \includegraphics[width=.8\textwidth]{figures/tree-example.eps}
63 \end{center}
64 \caption{コード\ref{code:tree-example}の構文木の例}
65 \label{fig:tree-example}
66 \end{figure}
67 図のように、一般的なコンパイラでは\verb|#include|などのディレクティブ
68 を除くソースコードの全てを構文木で表現する。これによりプログラムの文脈
69 をコンパイラが理解し、それぞれのブロック毎にアセンブラへの変換が可能に
70 なる。
71
72 フロントエンドではGenericを生成した後、ミドルエンドにデータを渡す前に
73 GenericをGIMPLEと呼ばれるデータ構造に変換する。GIMPLEはデータ構造とし
74 ては Genericと同じであるが、一つの枝に4つ以上の子がついてはいけないな
75 どの制限が付加されている。この制限はミドルエンド以降での解析を容易にし
76 、また種々の最適化はこのGIMPLEを対象として行われている。
77
78
79 \subsection{ミドルエンドとRTL}
80
81 GCCは構文木GIMPLEの生成後、このGIMPLEを解析しながらRTLと呼ばれる中間コ
82 ードを生成する。このRTLはアセンブラとほぼ同等の命令列を表現可能であり
83 、どのアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存
84 はないため、このミドルエンドは言語にもアーキテクチャにも依存しない、全
85 てのGCCコンパイラに共通のルーチンとなっている。
86
87 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特
88 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ
89 の場合はアーキテクチャが対応してるか否かを判別するため、次項に紹介する
90 Machine Descriptionが使われるため、共通のミドルエンドが使われることに
91 変わりはない。
92
93 RTLはプログラム上は構造体として扱われるが、デバグ表示や次のバックエン
94 ドで使うMachine Descriptionのため、S式を用いた表現が用いられている。
95 例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表現
96 は以下のようになる。
97
98 \begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例,
99 label=code:rtl-example,language=Lisp]
100 (set (reg/f:SI 54 virtual-stack-vars)
101 (mult:SI (reg:SI 58)
102 (const_int 20 [0x14])))
103 \end{lstlisting}
104
105 この例では\verb|(reg:SI 58)|で表される仮想レジスタの値と定数20との積を
106 、\verb|(reg/f:SI 54)|で表されるレジスタにセットしている。
107 ミドルエンドではGIMPLEを元にこの様なRTLの命令列を作成し、バックエンド
108 に処理を引き渡している。
109
110
111 \subsection{バックエンドとMachine Description}
112
113 バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し
114 ている。このバックエンドでは必然的にターゲットとするアーキテクチャによ
115 り処理が異なるため、このバックエンドはアーキテクチャ毎に用意されること
116 になる。
117 アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine
118 Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに
119 それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。
120
121 このmdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する
122 必要がある。
123 \begin{itemize}
124 \item その変換規則の名前
125
126 GCCのプログラムから関数として呼び出すための名前である
127 \item 変換するRTLの構造（パターンマッチ）
128
129 この規則がどのようなRTLを変換できるかを表す
130 \item 変換する条件
131
132 上記のパターンだけでは判別できない時の追加条件をCの構文で記述
133 \item 出力するアセンブラ
134
135 Cの文字列か、もしくは文字列を出力するCの構文
136 \end{itemize}
137
138 例としてARMアーキテクチャにおけるmdを一つ、コード
139 \ref{code:md-example}に示す。このmdはコード\ref{code:rtl-example}で紹
140 介した乗算命令のRTLにマッチし、アセンブラ``\verb|mul r0 r2 r1|'' を出
141 力する。
142 2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と
143 形が似ていることが分かる。
144 3行目が条件である。バックエンドプログラムの変数などをチェックしている。
145 そして4行目が出力するアセンブラである。ここでは``\verb|%?|''や
146 ``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。
147
148 \begin{lstlisting}[caption=ARMでのMachine Descriptionの例
149 （コード\ref{code:rtl-example}をアセンブラに変換）,
150 label=code:md-example,language=Lisp]
151 (define_insn "*arm_mulsi3"
152 [(set (match_operand:SI 0 "s_register_operand" "=&r,&r")
153 (mult:SI (match_operand:SI 2 "s_register_operand" "r,r")
154 (match_operand:SI 1 "s_register_operand" "%?r,0")))]
155 "TARGET_32BIT && !arm_arch6"
156 "mul%?\\t%0, %2, %1")
157 \end{lstlisting}
158
159
160 \subsection{最適化パス}
161 最適化はGCCの中でももっとも重要な機能の一つといえる。
162 様々な最適化の手法がGCCにおいて実装され、実用化されている。
163
164 GCCではこの最適化は2つフェーズに分類される。
165 一つはGIMPLEを対象とした最適化である。
166 このGIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どの
167 コンパイラにおいてもこの最適化を適用することができる。
168 この最適化はミドルエンドで行われる。
169
170 もう一つはRTLを対象とした最適化である。
171 RTLのデータ構造自体は言語にもアーキテクチャにも依存はないが、最適化に
172 はレジスタの数やスタックの操作法などに依存する事が多いため、この最適化
173 ではいくつかの制限が入る。
174 こちらはバックエンドでの実装である。
175
176 次章で説明するが、本研究では軽量継続の実装にGIMPLE対象の最適化である末
177 尾呼び出し最適化を利用している。そのため、CbCの言語実装であるがミドル
178 エンドの修正も行っている。
179
180
181 \subsection{GCC}
182
183 以上のようにGCCはフロントエンド、ミドルエンド、バックエンドがそれぞれ
184 の役割を持ち、全体を通して最終的にアセンブラの生成を行う。
185
186 GCCではこのようにアセンブラを出力した後、アセンブル、リンクまでを行う。
187 しかしそれらは本研究では関連しないので説明は割愛する。
188
189