Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 9:de1193768ef9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Nov 2011 18:03:15 +0900
parents 3d1135b3519c
children 3d1f778dc358
comparison
equal deleted inserted replaced
7:3d1135b3519c 9:de1193768ef9
19 % ユーザが定義したマクロなど． 19 % ユーザが定義したマクロなど．
20 \makeatletter 20 \makeatletter
21 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} 21 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
22 \def\<{\(\langle\)} 22 \def\<{\(\langle\)}
23 \def\>{\(\rangle\)} 23 \def\>{\(\rangle\)}
24 \def\|{\verb|} 24 %\def\|{\verb|}
25 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} 25 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
26 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} 26 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
27 \def\LATEX{\iLATEX\Large} 27 \def\LATEX{\iLATEX\Large}
28 \def\LATEx{\iLATEX\normalsize} 28 \def\LATEx{\iLATEX\normalsize}
29 \def\LATex{\iLATEX\small} 29 \def\LATex{\iLATEX\small}
99 99
100 % }{ 100 % }{
101 101
102 % 本文はここから始まる 102 % 本文はここから始まる
103 \section{歴史的経緯} 103 \section{歴史的経緯}
104 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. 104 %当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
105 CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる. 105 %CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
106 当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
107 コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
108 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.
106 109
107 CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 110 CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
108 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 111 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
109 2010年には GCC-4.4 へとアップデートが行われた. 112 2010年には GCC-4.4 へとアップデートが行われた.
110 GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. 113 GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
111 %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. 114 %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
112 115 %今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
113 今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. 116 %本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
114 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. 117 だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
118 本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.
119
115 120
116 % }{ 121 % }{
117 122
118 \section{Continuation based C (CbC)} 123 \section{Continuation based C (CbC)}
119 Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 124 CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
120 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. 125 構文は C と同じであるが, ループ制御や関数コールが取り除かれる.
121 また,コードセグメント単位で処理を記述するという特徴がある. 126
122 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. 127 %Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
128 %構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
129 %また,コードセグメント単位で処理を記述するという特徴がある.
130 %図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.
131
132
133 \subsection{継続(goto)}
134 コードセグメントの記述は C の関数の構文と同じで, 型に“\verb+code+” を使うことで宣言できる.
135 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える.
136 図\ref{fig:cs}はコードセグメント間の処理の流れを表している.
137
138 %コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
139 %コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
140 %この goto によるコードセグメント間の移動を継続と言う.
141 %継続の実態は jmp による関数の移動となる.
123 142
124 \begin{figure}[htpb] 143 \begin{figure}[htpb]
125 \begin{center} 144 \begin{center}
126 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}} 145 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
127 \end{center} 146 \end{center}
128 \caption{コードセグメント間の継続(goto)} 147 \caption{コードセグメント間の継続(goto)}
129 \label{fig:cs} 148 \label{fig:cs}
130 \end{figure} 149 \end{figure}
131 150
132
133 \subsection{継続(goto)}
134 コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
135 コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
136 この goto によるコードセグメント間の移動を継続と言う.
137
138 継続の実態は jmp による関数の移動となる.
139
140
141 \subsection{コードセグメント(code segment)} 151 \subsection{コードセグメント(code segment)}
142 CbC におけるプログラムの基本単位としてコードセグメントという概念がある. 152 コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
143 コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 153 C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
144 関数と同じように引数を持たせて継続させることもできる. 154 だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.
145 しかし,関数とは違ってリターンを行わない為返り値を取得することはできない. 155
156 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.
157
146 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 158 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
147 与えられた数 x の階上を計算して出力するプログラムとなっている. 159 与えられた数 x の階上を計算して出力するプログラムとなっている.
148 160
149 \begin{figure} 161 \begin{figure}
150 \lstinputlisting[language=c]{source/factorial.cbc} 162 \lstinputlisting[language=c]{source/factorial.cbc}
151 \caption{階上を計算する CbC プログラムの例} 163 \caption{階上を計算する CbC プログラムの例}
152 \end{figure} 164 \end{figure}
153 165
166 %CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
167 %コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
168 %関数と同じように引数を持たせて継続させることもできる.
169 %しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
154 170
155 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. 171 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
156 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. 172 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
157
158
159 \section{GCCの3つの内部表現} 173 \section{GCCの3つの内部表現}
160 GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく. 174 GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.
161
162 175
163 \subsection{3つの内部表現} 176 \subsection{3つの内部表現}
164 GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う. 177 GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
165 それぞれが 178 それぞれが
166 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき, 179 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
167 最後にアセンブラ言語へと出力される. 180 最後にアセンブラ言語へと出力される.
168 図\ref{fig:ir}はアセンブラ出力までの流れを表した図である. 181 図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.
169 182
170 \begin{figure}[htpb] 183 \begin{figure}[htpb]
171 \begin{center} 184 \begin{center}
172 \scalebox{0.35}{\includegraphics{figure/ir.eps}} 185 \scalebox{0.35}{\includegraphics{figure/ir.eps}}
173 \end{center} 186 \end{center}
193 \subsubsection{Register Transfer Language (RTL)} 206 \subsubsection{Register Transfer Language (RTL)}
194 構文木 GIMPLE は解析が行われた後 RTL へと変換される. 207 構文木 GIMPLE は解析が行われた後 RTL へと変換される.
195 RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる. 208 RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
196 プログラム内部では RTL も木構造で表される. 209 プログラム内部では RTL も木構造で表される.
197 210
198 CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる. 211 CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.
199 212
200 213
201 \section{GCC-4.6 への実装} 214 \section{GCC-4.6 への実装}
202 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. 215 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
203 ここからは GCC-4.6 への実装について述べていく. 216 ここからは GCC-4.6 への実装について述べていく.
204 217
205 218
206 \subsection{“\_\_code” のパース} 219 %\subsection{“\_\_code” のパース}
207
208 220
209 221
210 \subsection{Tail Call Elimination} 222 \subsection{Tail Call Elimination}
211 CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. 223 CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する.
212 Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, 224 これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
213 call ではなく jmp を用いることができるという最適化である. 225 %Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
226 %call ではなく jmp を用いることができるという最適化である.
214 図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. 227 図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
215 228
216 229 \begin{figure}[htpb]
217 \begin{figure}[htpb] 230 \begin{center}
218 \begin{center} 231 \scalebox{0.35}{\includegraphics{figure/continuation.eps}}
219 \scalebox{0.50}{\includegraphics{figure/continuation.eps}}
220 \end{center} 232 \end{center}
221 \caption{Tail Call Elimination} 233 \caption{Tail Call Elimination}
222 \label{fig:continue} 234 \label{fig:continue}
223 \end{figure} 235 \end{figure}
224 funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す. 236 funcB は jmp 命令で funcC を呼び出す.
225 237 funcC は,返り値を funcB ではなく funcA へと返すことになる.
226 238
227 \subsubsection{expand\_call} 239 \subsubsection{expand\_call}
228 ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される. 240 ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
229 expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる. 241 \verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
230 242
231 \begin{itemize} 243 \begin{itemize}
232 \item caller 側と callee 側の返す値の型が一致している. 244 \item caller 側と callee 側の戻値の型が一致している.
233 \item 関数呼び出しがリターンの直前に行われている. 245 \item 関数呼び出しがリターンの直前に行われている.
234 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない. 246 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
235 \item[] 247 \item 引数の並びのコピーに上書きがない.
236 \end{itemize} 248 \end{itemize}
237
238
239 CbC の実装では上記の条件を,以下の様にして解決させている. 249 CbC の実装では上記の条件を,以下の様にして解決させている.
240 250
241 \begin{itemize} 251 \begin{itemize}
242 \item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない. 252 \item コードセグメントは void 型で統一する
243 \item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる. 253 \item Cの関数からコードセグメントにgotoする場合は返す値の型チェックを行わない.
244 \item スタックサイズは決め打ちで行う. 254 \item goto の直後に retrun を置く．
245 \item[] 255 \item スタックサイズは関数宣言時に決まったサイズにする．
256 \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
246 \end{itemize} 257 \end{itemize}
247 258
248 スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる. 259 スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
249 これも CbC の1つの特徴である. 260 これも CbC の1つの特徴である.
250 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している. 261 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.