Mercurial > hg > Papers > 2010 > kent-master

comparison gcc.tex @ 7:8ef81ff8cb52

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
emended.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 13:10:57 +0900
parents dfb89e32eea1
children 4b2af58b0302
comparison
equal deleted inserted replaced
6:b59d31966d7d 7:8ef81ff8cb52
13 \section{ソースコードからアセンブラへ} 13 \section{ソースコードからアセンブラへ}
14 14
15 GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで 15 GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで
16 行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン 16 行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン
17 クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に 17 クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に
18 はその統括をしているだけである。 18 はそれらを統括しているだけである。
19 19
20 言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ 20 言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ
21 ースコードをアセンブラに変換するかを説明する。 21 ースコードをアセンブラに変換するかを説明する。
22 22
23 \subsection{cc1} 23 \subsection{cc1}
29 を示す。 29 を示す。
30 \begin{figure}[htpb] 30 \begin{figure}[htpb]
31 \begin{center} 31 \begin{center}
32 \includegraphics[width=.8\textwidth]{figures/gcc-flow.eps} 32 \includegraphics[width=.8\textwidth]{figures/gcc-flow.eps}
33 \end{center} 33 \end{center}
34 \caption{GCC} 34 \caption{cc1でのデータフロー(Generic, GIMPLE, RTL)}
35 \label{fig:gcc-flow} 35 \label{fig:gcc-flow}
36 \end{figure} 36 \end{figure}
37 37
38 38
39 \subsection{フロントエンドとGeneric, GIMPLE} 39 \subsection{フロントエンドとGeneric, GIMPLE}
49 この構文木は言語に依存しないため、言語設計者は通常はミドルエンド以降に 49 この構文木は言語に依存しないため、言語設計者は通常はミドルエンド以降に
50 ついては考慮する必要はない。 50 ついては考慮する必要はない。
51 51
52 構文木がプログラムをデータ構造として表す様子を図 52 構文木がプログラムをデータ構造として表す様子を図
53 \ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example} 53 \ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example}
54 の関数\verb|funcA|を解析した結果を構文木で表現している。 54 の関数\verb|funcT|を解析した結果を構文木で表現している。
55 55
56 \begin{figure}[htpb] 56 \begin{figure}[htpb]
57 \lstinputlisting 57 \lstinputlisting
58 [caption=C言語の解析例（解析結果は図\ref{fig:tree-example}）, 58 [caption=C言語の解析例（解析結果は図\ref{fig:tree-example}）,
59 label=code:tree-example] 59 label=code:tree-example]
77 77
78 78
79 \subsection{ミドルエンドとRTL} 79 \subsection{ミドルエンドとRTL}
80 80
81 GCCは構文木GIMPLEの生成後、このGIMPLEを解析しながらRTLと呼ばれる中間コ 81 GCCは構文木GIMPLEの生成後、このGIMPLEを解析しながらRTLと呼ばれる中間コ
82 ードを生成する。このRTLはアセンブラとほぼ同等の命令列を表現可能であり 82 ードを生成する。RTLはアセンブラとほぼ同等の命令列を表現可能であり、ど
83 、どのアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存 83 のアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存はな
84 はないため、このミドルエンドは言語にもアーキテクチャにも依存しない、全 84 いため、ミドルエンドは言語にもアーキテクチャにも依存しない、全ての GCC
85 てのGCCコンパイラに共通のルーチンとなっている。 85 コンパイラに共通のルーチンとなっている。
86 86
87 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特 87 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特
88 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ 88 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ
89 の場合はアーキテクチャが対応してるか否かを判別するため、次項に紹介する 89 の場合はアーキテクチャが対応してるか否かを判別するために次項に紹介する
90 Machine Descriptionが使われるため、共通のミドルエンドが使われることに 90 Machine Descriptionが使われるため、共通のミドルエンドが使われることに
91 変わりはない。 91 変わりはない。
92 92
93 RTLはプログラム上は構造体として扱われるが、デバグ表示や次のバックエン 93 RTLはプログラム上はツリー構造として扱われるが、デバッグ表示や次のバッ
94 ドで使うMachine Descriptionのため、S式を用いた表現が用いられている。 94 クエンドで使うMachine Descriptionのため、S式を用いた表現が用いられてい
95 例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表現 95 る。例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表
96 は以下のようになる。 96 現は以下のようになる。
97 97
98 \begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例, 98 \begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例,
99 label=code:rtl-example,language=Lisp] 99 label=code:rtl-example,language=Lisp]
100 (set (reg/f:SI 54 virtual-stack-vars) 100 (set (reg/f:SI 54 virtual-stack-vars)
101 (mult:SI (reg:SI 58) 101 (mult:SI (reg:SI 58)
109 109
110 110
111 \subsection{バックエンドとMachine Description} 111 \subsection{バックエンドとMachine Description}
112 112
113 バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し 113 バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し
114 ている。このバックエンドでは必然的にターゲットとするアーキテクチャによ 114 ている。この処理は必然的にターゲットとするアーキテクチャにより処理が異
115 り処理が異なるため、このバックエンドはアーキテクチャ毎に用意されること 115 なるため、バックエンドはアーキテクチャ毎に用意されることになる。
116 になる。 116
117 アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine 117 アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine
118 Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに 118 Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに
119 それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。 119 それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。
120 120
121 このmdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する 121 mdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する必要
122 必要がある。 122 がある。
123 \begin{itemize} 123 \begin{itemize}
124 \item その変換規則の名前 124 \item その変換規則の名前
125 125
126 GCCのプログラムから関数として呼び出すための名前である 126 GCCのプログラムから関数として呼び出すための名前である。
127 \item 変換するRTLの構造（パターンマッチ） 127 \item 変換するRTLの構造（パターンマッチ）
128 128
129 この規則がどのようなRTLを変換できるかを表す 129 この規則がどのようなRTLを変換できるかを表す。
130 \item 変換する条件 130 \item 変換する条件
131 131
132 上記のパターンだけでは判別できない時の追加条件をCの構文で記述 132 上記のパターンだけでは判別できない時の追加条件をCの構文で記述する。
133 \item 出力するアセンブラ 133 \item 出力するアセンブラ
134 134
135 Cの文字列か、もしくは文字列を出力するCの構文 135 アセンブラ文字列か、もしくはアセンブラ文字列を出力するCの構文を記
136 述する。
136 \end{itemize} 137 \end{itemize}
137 138
138 例としてARMアーキテクチャにおけるmdを一つ、コード 139 例としてARMアーキテクチャにおけるmdを一つ、コード
139 \ref{code:md-example}に示す。このmdはコード\ref{code:rtl-example}で紹 140 \ref{code:md-example}に示す。このmdはコード\ref{code:rtl-example}で紹
140 介した乗算命令のRTLにマッチし、アセンブラ``\verb|mul r0 r2 r1|'' を出 141 介した乗算命令のRTLにマッチし、アセンブラ``\verb|mul r0 r2 r1|'' を出
141 力する。 142 力する。
142 2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と 143 2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と
143 形が似ていることが分かる。 144 形が似ていることが分かる。
144 3行目が条件である。バックエンドプログラムの変数などをチェックしている。 145 5行目が条件である。バックエンドプログラムの変数などをチェックしている。
145 そして4行目が出力するアセンブラである。ここでは``\verb|%?|''や 146 そして6行目が出力するアセンブラである。ここでは``\verb|%?|''や
146 ``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。 147 ``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。
147 148
148 \begin{lstlisting}[caption=ARMでのMachine Descriptionの例 149 \begin{lstlisting}[caption=ARMでのMachine Descriptionの例
149 （コード\ref{code:rtl-example}をアセンブラに変換）, 150 （コード\ref{code:rtl-example}をアセンブラに変換）,
150 label=code:md-example,language=Lisp] 151 label=code:md-example,language=Lisp,numbers=left]
151 (define_insn "*arm_mulsi3" 152 (define_insn "*arm_mulsi3"
152 [(set (match_operand:SI 0 "s_register_operand" "=&r,&r") 153 [(set (match_operand:SI 0 "s_register_operand" "=&r,&r")
153 (mult:SI (match_operand:SI 2 "s_register_operand" "r,r") 154 (mult:SI (match_operand:SI 2 "s_register_operand" "r,r")
154 (match_operand:SI 1 "s_register_operand" "%?r,0")))] 155 (match_operand:SI 1 "s_register_operand" "%?r,0")))]
155 "TARGET_32BIT && !arm_arch6" 156 "TARGET_32BIT && !arm_arch6"
159 160
160 \subsection{最適化パス} 161 \subsection{最適化パス}
161 最適化はGCCの中でももっとも重要な機能の一つといえる。 162 最適化はGCCの中でももっとも重要な機能の一つといえる。
162 様々な最適化の手法がGCCにおいて実装され、実用化されている。 163 様々な最適化の手法がGCCにおいて実装され、実用化されている。
163 164
164 GCCではこの最適化は2つフェーズに分類される。 165 GCCでは最適化は2つフェーズに分類される。
165 一つはGIMPLEを対象とした最適化である。 166 一つはGIMPLEを対象とした最適化である。
166 このGIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どの 167 GIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どのコン
167 コンパイラにおいてもこの最適化を適用することができる。 168 パイラにおいてもこの最適化を適用することができる。
168 この最適化はミドルエンドで行われる。 169 この最適化はミドルエンドで行われる。
169 170
170 もう一つはRTLを対象とした最適化である。 171 もう一つはRTLを対象とした最適化である。
171 RTLのデータ構造自体は言語にもアーキテクチャにも依存はないが、最適化に 172 RTLのデータ構造自体は言語にもアーキテクチャにも依存はないが、最適化に
172 はレジスタの数やスタックの操作法などに依存する事が多いため、この最適化 173 はレジスタの数やスタックの操作法などに依存する事が多いため、この最適化