|
5
|
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
|
