Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 2:4c5a29c7bb47

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify nobu-prosym.tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 18 Nov 2011 06:33:48 +0900
parents 878e70793abe
children 5dfa978ee319
comparison
equal deleted inserted replaced
1:878e70793abe 2:4c5a29c7bb47
96 % }{ 96 % }{
97 97
98 % 本文はここから始まる 98 % 本文はここから始まる
99 \section{歴史的経緯} 99 \section{歴史的経緯}
100 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. 100 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
101 CbC の構文は C と同じであるが,継続によりループ制御や関数コールを取り除かれる. 101 CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
102 102
103 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発された. 103 CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
104 以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. 104 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
105 お陰で,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. 105 2010年には GCC-4.4 へとアップデートが行われた.
106 106 GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
107 しかし,未だに GCC ベースのコンパイラには幾つかのバグがある. 107 %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
108 今回,GCC-4.6 への実装も兼ねながら問題の部分の改善を行った. 108
109 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を具体的に述べる. 109 今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
110 110 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
111 111
112 % }{ 112 % }{
113 113
114 \section{Continuation based C (CbC)} 114 \section{Continuation based C (CbC)}
115 Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 115 Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
117 また,コードセグメント単位で処理を記述するという特徴がある. 117 また,コードセグメント単位で処理を記述するという特徴がある.
118 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. 118 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.
119 119
120 \begin{figure}[htpb] 120 \begin{figure}[htpb]
121 \begin{center} 121 \begin{center}
122 \scalebox{0.50}{\includegraphics{figure/codesegment.eps}} 122 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
123 \end{center} 123 \end{center}
124 \caption{コードセグメント間の継続(goto)} 124 \caption{コードセグメント間の継続(goto)}
125 \label{fig:cs} 125 \label{fig:cs}
126 \end{figure} 126 \end{figure}
127 127
128 128
129 \subsection{継続(goto)} 129 \subsection{継続(goto)}
130 コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. 130 コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
131 コードセグメントは自身の処理が終われば goto により次のコードセグメントでの処理に移る. 131 コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
132 goto によるコードセグメント間の移動を継続と言う. 132 この goto によるコードセグメント間の移動を継続と言う.
133
134 継続の実態は jmp による関数の移動となる.
133 135
134 136
135 \subsection{コードセグメント(code segment)} 137 \subsection{コードセグメント(code segment)}
136 CbC におけるプログラムの基本単位としてコードセグメントという概念がある. 138 CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
137 コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 139 コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
140 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 142 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
141 与えられた数 x の階上を計算して出力するプログラムとなっている. 143 与えられた数 x の階上を計算して出力するプログラムとなっている.
142 144
143 \begin{figure}[htpb] 145 \begin{figure}[htpb]
144 \begin{center} 146 \begin{center}
145 \scalebox{0.50}{\includegraphics{figure/factorial.eps}} 147 \scalebox{0.40}{\includegraphics{figure/factorial.eps}}
146 \end{center} 148 \end{center}
147 \caption{CbC のプログラム例} 149 \caption{階上を計算する CbC プログラムの例}
148 \label{fig:factorial} 150 \label{fig:factorial}
149 \end{figure} 151 \end{figure}
150 152
151 153
152 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. 154 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
153 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. 155 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
154 156
155 157
156 158 \section{GCCの3つの内部表現}
157 \section{Gnu Compiler Collection} 159 GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.
158 GCC-4.6 への実装の前に,GCC によるコンパイルの一連の流れについて触れておく. 160
159 161
160 \subsection{3つの中間言語} 162 \subsection{3つの内部表現}
161 GCC は内部で Generic Tree, GIMPLE, RTL の3つの中間言語を扱われる. 163 GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
164 それぞれが
165 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
166 最後にアセンブラ言語へと出力される.
167 図\ref{fig:ir}は
168
169
170 \begin{figure}[htpb]
171 \begin{center}
172 \scalebox{0.35}{\includegraphics{figure/ir.eps}}
173 \end{center}
174 \caption{GCC によるコンパイルの一連の流れ}
175 \label{fig:ir}
176 \end{figure}
177
162 178
163 \subsubsection{Generic Tree} 179 \subsubsection{Generic Tree}
164 まず,GCC で読み込まれたソースコードは Generic Tree 呼ばれる構文木のデータ構造で表される. 180 ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
165 図...に Generic Tree で表現された例を示す. 181 関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
182 CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.
183
166 184
167 \subsubsection{GIMPLE} 185 \subsubsection{GIMPLE}
168 Generic Tree により表現されたデータは次に GIMPLE という構文木へと変換される. 186 Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
169 GIMPLE は Generic Tree より制約がかかった状態で作成される. 187 GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
170 制約は「1つの枝に4つ以上の子を持たせない」といったもので, 188 制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
171 GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになる. 189 GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
172 190 CbC の実装では特に修正は加えていない.
173 191
174 \subsubsection{RTL} 192
175 193 \subsubsection{Register Transfer Language (RTL)}
176 194 構文木 GIMPLE は解析が行われた後 RTL へと変換される.
177 195 RTL での表現は低レベルで,アセンブラとほぼ同じ表現を行うことができる.
178 Gneric Tree から GIMPLE, そして RTL へとデータは変換され最後にアセンブリ言語で出力される. 196
179 197
198 CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる.
180 199
181 200
182 \section{GCC-4.6 への実装} 201 \section{GCC-4.6 への実装}
202 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
203 ここからは GCC-4.6 への実装について述べていく.
204
205
206 \subsection{“__code” のパース}
207
183 208
184 209
185 \subsection{Tail Call Elimination} 210 \subsection{Tail Call Elimination}
186 CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. 211 CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
187 Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, 212 Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
188 call ではなく jmp を用いて大元の関数へ戻るようにする最適化のことである. 213 call ではなく jmp を用いることができるという最適化である.
189 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. 214 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
190 215
191 216
192 \begin{figure}[htpb] 217 \begin{figure}[htpb]
193 \begin{center} 218 \begin{center}
194 \scalebox{0.50}{\includegraphics{figure/continuation.eps}} 219 \scalebox{0.50}{\includegraphics{figure/continuation.eps}}
195 \end{center} 220 \end{center}
196 \caption{Tail Call Elimination} 221 \caption{Tail Call Elimination}
197 \label{fig:continue} 222 \label{fig:continue}
198 \end{figure} 223 \end{figure}
199 224 funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.
200 225
201 226
202 \subsubsection{expand\_call} 227 \subsubsection{expand\_call}
228 ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数によって判断される.
229 Tail call Elimination が行える場合 try\_tail_call
230 expand\_call 関数の中で try_tail_call というフラグ
203 231
204 232
205 233
206 \subsection{引数渡し} 234 \subsection{引数渡し}
207 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される. 235 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される.