Mercurial > hg > Papers > 2010 > kent-master

comparison paper/gcc.tex @ 10:3d9addf62d0b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
organized repository.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 14:35:36 +0900
parents gcc.tex@4b2af58b0302
children
comparison
equal deleted inserted replaced
9:ae0a3666f7f9 10:3d9addf62d0b
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だけである。以降はこのプログラムcc1がどのようにソ
21 ースコードをアセンブラに変換するかを説明する。
22
23 \section{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{cc1でのデータフロー(Generic, GIMPLE, RTL)}
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|funcT|を解析した結果を構文木で表現している。
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 \subsubsection{GimplifyとGIMPLE(SSA)}
73
74 フロントエンドではGenericを生成した後、ミドルエンドにデータを渡す前に
75 GenericをGIMPLEと呼ばれるデータ構造に変換する。この処理がGimplifyであ
76 る。GIMPLEはデータ構造としては Genericと同じであるが、一つの枝に4つ以
77 上の子がついてはいけないなどの制限が付加されている。
78
79 この制限されたデータ構造は一般的には静的単一代入(Static Single
80 Assignment)と呼ばれており、様々な最適化を簡略化する事を目的として導入
81 されている。
82
83
84 \subsection{ミドルエンドとRTL}
85
86 GCCはフロントエンドにて構文木GIMPLEの生成後、このGIMPLEを解析しながら
87 RTLと呼ばれる中間コードを生成する。RTLはアセンブラとほぼ同等の命令列を
88 表現可能であり、どのアーキテクチャでも同じように扱われる。また、GIMPLE
89 にも言語の依存はないため、ミドルエンドは言語にもアーキテクチャにも依存
90 しない、全ての GCC コンパイラに共通のルーチンとなっている。
91
92 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特
93 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ
94 の場合はアーキテクチャが対応してるか否かを判別するために次項に紹介する
95 Machine Descriptionが使われるため、共通のミドルエンドが使われることに
96 変わりはない。
97
98 RTLはプログラム上はツリー構造として扱われるが、デバッグ表示や次のバッ
99 クエンドで使うMachine Descriptionのため、S式を用いた表現が用いられてい
100 る。例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表
101 現は以下のようになる。
102
103 \begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例,
104 label=code:rtl-example,language=Lisp]
105 (set (reg/f:SI 54 virtual-stack-vars)
106 (mult:SI (reg:SI 58)
107 (const_int 20 [0x14])))
108 \end{lstlisting}
109
110 この例では\verb|(reg:SI 58)|で表される仮想レジスタの値と定数20との積を
111 、\verb|(reg/f:SI 54)|で表されるレジスタにセットしている。
112 ミドルエンドではGIMPLEを元にこの様なRTLの命令列を作成し、バックエンド
113 に処理を引き渡している。
114
115 \subsubsection{最適化パス}
116 最適化はGCCの中でももっとも重要な機能の一つといえる。
117 様々な最適化の手法がGCCにおいて実装され、実用化されている。
118
119 GCCでは最適化は2つフェーズに分類される。
120
121 一つはGIMPLEを対象とした最適化である。 GIMPLEは、アーキテクチャはもち
122 ろん言語仕様にも依存しないため、どのコンパイラにおいてもこの最適化を適
123 用することができる。
124
125 もう一つはRTLを対象とした最適化である。 RTLのデータ構造自体は言語にも
126 アーキテクチャにも依存はないが、最適化にはレジスタの数やスタックの操作
127 法などに依存する事が多いため、この最適化ではいくつかの制限が入る。
128
129 ミドルエンドには``pass''という概念があり、最適化処理やGIMPLEの変換、そ
130 の他諸々の処理は、その処理のメインルーチンをpassに登録することでミドル
131 エンド上にて実行可能になる。
132
133 passの登録順序にも意味があり、passの前半部はGIMPLE対象の最適化など、続
134 いてGIMPLEからRTLへの変換処理、後半部にはRTLの最適化処理が登録されてい
135 る。
136
137 次章で説明するが、本研究では軽量継続の実装にGIMPLE対象の最適化である末
138 尾呼び出し最適化を利用している。そのため、CbCの言語実装であるがミドル
139 エンドの修正も行っている。
140
141
142 \subsection{バックエンドとMachine Description}
143
144 バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し
145 ている。この処理は必然的にターゲットとするアーキテクチャにより処理が異
146 なるため、バックエンドはアーキテクチャ毎に用意されることになる。
147
148 アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine
149 Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに
150 それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。
151
152 mdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する必要
153 がある。
154 \begin{itemize}
155 \item その変換規則の名前
156
157 GCCのプログラムから関数として呼び出すための名前である。
158 \item 変換するRTLの構造（パターンマッチ）
159
160 この規則がどのようなRTLを変換できるかを表す。
161 \item 変換する条件
162
163 上記のパターンだけでは判別できない時の追加条件をCの構文で記述する。
164 \item 出力するアセンブラ
165
166 アセンブラ文字列か、もしくはアセンブラ文字列を出力するCの構文を記
167 述する。
168 \end{itemize}
169
170 例としてARMアーキテクチャにおけるmdを一つ、コード
171 \ref{code:md-example}に示す。このmdはコード\ref{code:rtl-example}で紹
172 介した乗算命令のRTLにマッチし、アセンブラ``\verb|mul r0 r2 r1|'' を出
173 力する。
174 2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と
175 形が似ていることが分かる。
176 5行目が条件である。バックエンドプログラムの変数などをチェックしている。
177 そして6行目が出力するアセンブラである。ここでは``\verb|%?|''や
178 ``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。
179
180 \begin{lstlisting}[caption=ARMでのMachine Descriptionの例
181 （コード\ref{code:rtl-example}をアセンブラに変換）,
182 label=code:md-example,language=Lisp,numbers=left]
183 (define_insn "*arm_mulsi3"
184 [(set (match_operand:SI 0 "s_register_operand" "=&r,&r")
185 (mult:SI (match_operand:SI 2 "s_register_operand" "r,r")
186 (match_operand:SI 1 "s_register_operand" "%?r,0")))]
187 "TARGET_32BIT && !arm_arch6"
188 "mul%?\\t%0, %2, %1")
189 \end{lstlisting}
190
191 \subsubsection{mdからソースコードへの変換}
192
193 mdの記述は上記の様に単なる生成規則でしかない。そのため通常のプログラム
194 であれば実行時にmdデータを読み込みその通りに解釈する方法を取るが、コン
195 パイラの様な大規模なソフトウェアではそれでは処理に時間がかかりすぎる。
196
197 そのためGCCではこのmdを直接プログラムに変換する手法を取っている。
198 例として、\verb|i386.md|（x86アーキテクチャの生成規則である）は
199 \verb|insn-emit.c|や\verb|insn-output.c|などの、C言語ソースファイルに
200 変換され、バックエンドやその他のソースファイルと一緒にコンパイルされ、
201 cc1プログラムの一部となる。この様子を図\ref{fig:insns}に表した。
202
203 \begin{figure}[htpb]
204 \begin{center}
205 \includegraphics[width=.9\textwidth]{figures/insns.eps}
206 \end{center}
207 \caption{mdからソースコードを生成、さらにcc1をコンパイルする様子}
208 \label{fig:insns}
209 \end{figure}
210
211 \section{GCC}
212
213 以上のようにGCCはフロントエンド、ミドルエンド、バックエンドがそれぞれ
214 の役割を持ち、全体を通して最終的にアセンブラの生成を行う。
215
216 GCCではこのようにアセンブラを出力した後、アセンブル、リンクまでを行う。
217 しかしそれらは本研究では関連しないので説明は割愛する。
218
219