Mercurial > hg > Papers > 2011 > nobu-prosym

comparison nobu-prosym.tex~ @ 0:9fc7603e8e8b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add nobu-prosym
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 17 Nov 2011 08:38:35 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:9fc7603e8e8b
1 \documentclass[private]{ipsjpapers}
2 %\documentstyle{ipsjpapers}
3 \usepackage[dvipdfmx]{graphicx}
4 \usepackage{url}
5
6 % 巻数，号数などの設定
7 \setcounter{巻数}{41}
8 \setcounter{号数}{6}
9 \setcounter{volpageoffset}{1234}
10 \受付{12}{2}{4}
11 \採録{12}{5}{11}
12
13 % ユーザが定義したマクロなど．
14 \makeatletter
15 \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
16 \def\<{\(\langle\)}
17 \def\>{\(\rangle\)}
18 \def\|{\verb|}
19 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
20 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
21 \def\LATEX{\iLATEX\Large}
22 \def\LATEx{\iLATEX\normalsize}
23 \def\LATex{\iLATEX\small}
24 \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
25 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
26 \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
27 \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
28 \def\Quote{\list{}{}\item[]}
29 \let\endQuote\endlist
30 \def\TT{\if@LaTeX@e\tt\fi}
31 \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
32 $\backslash$#1\fi}
33
34 %\checklines % 行送りを確認する時に使用
35
36 \begin{document}%{
37 % 和文表題
38 \title[Continuation based C の GCC 4.6 上の実装について]%
39 {Continuation based C の GCC 4.6 上の実装について}
40 % 英文表題
41 \etitle{The implementation of Continuation based C Compiler on GCC 4.6}
42
43 % 所属ラベルの定義
44 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}
45
46 % 和文著者名
47 \author{大城 信康\affiref{URYUKYU}\nomember\and
48 河野 真治\affiref{URYUKYU}\member{19841765}}
49
50
51 % 英文著者名
52 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
53 Shinji Kono\affiref{URYUKYU}}
54
55 % 連絡先（投稿時に必要．製版用では無視される．）
56 \contact{大城 信康\\
57 〒903-0213 沖縄県中頭郡西原町字千原1番地\\
58 琉球大学 情報工学科\\
59 TEL: (098)895-8723\qquad FAX: (098)895-8727\\
60 email: dimolto@cr.ie.u-ryukyu.ac.jp}
61
62 % 和文概要
63 \begin{abstract}
64 GCC-4.6 をベースとした CbC コンパイラの実装を行った.
65 CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
66 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
67 今回は GCC-4.6 への実装を行った.
68 本論文では GCC-4.6 への CbC の具体的な実装について述べる。
69
70
71 %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
72 %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
73 %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.
74
75
76 \end{abstract}
77
78
79 % 英文概要
80 \begin{eabstract}
81 We implemented Continuation based C Compiler on GCC-4.6.
82 CbC Compiler on GCC-4.2 was developed on 2008.
83 Since then we kept to update it.
84 In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.
85
86 %Continuation based C is programming language. It is developing our laboratory.
87
88 \end{eabstract}
89
90 % 表題などの出力
91 \maketitle
92
93 % }{
94
95 % 本文はここから始まる
96 \section{歴史的経緯}
97 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
98 CbC の構文は C と同じであるが,継続によりループ制御や関数コールを取り除かれる.
99
100 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発された.
101 以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
102 お陰で,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
103
104 しかし,未だに GCC ベースのコンパイラには幾つかのバグがある.
105 今回,GCC-4.6 への実装も兼ねながら問題の部分の改善を行った.
106 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を具体的に述べる.
107
108
109 % }{
110
111 \section{Continuation based C (CbC)}
112 Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
113 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
114 また,コードセグメント単位で処理を記述するという特徴がある.
115 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.
116
117 \begin{figure}[htpb]
118 \begin{center}
119 \scalebox{0.50}{\includegraphics{figure/codesegment.eps}}
120 \end{center}
121 \caption{コードセグメント間の継続(goto)}
122 \label{fig:cs}
123 \end{figure}
124
125
126 \subsection{継続(goto)}
127 コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
128 コードセグメントは自身の処理が終われば goto により次のコードセグメントでの処理に移る.
129 goto によるコードセグメント間の移動を継続と言う.
130
131
132 \subsection{コードセグメント(code segment)}
133 CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
134 コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
135 関数と同じように引数を持たせて継続させることもできる.
136 しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
137 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
138 与えられた数 x の階上を計算して出力するプログラムとなっている.
139
140 \begin{figure}[htpb]
141 \begin{center}
142 \scalebox{0.50}{\includegraphics{figure/factorial.eps}}
143 \end{center}
144 \caption{CbC のプログラム例}
145 \label{fig:factorial}
146 \end{figure}
147
148
149 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
150 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
151
152
153
154 \section{Gnu Compiler Collection}
155 GCC-4.6 への実装の前に,GCC によるコンパイルの一連の流れについて触れておく.
156
157 \subsection{3つの中間言語}
158 GCC は内部で Generic Tree, GIMPLE, RTL の3つの中間言語を扱われる.
159
160 \subsubsection{Generic Tree}
161 まず,GCC で読み込まれたソースコードは Generic Tree 呼ばれる構文木のデータ構造で表される.
162 図...に Generic Tree で表現された例を示す.
163
164 \subsubsection{GIMPLE}
165 Generic Tree により表現されたデータは次に GIMPLE という構文木へと変換される.
166 GIMPLE は Generic Tree より制約がかかった状態で作成される.
167 制約は「1つの枝に4つ以上の子を持たせない」といったもので,
168 GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになる.
169
170
171 \subsubsection{RTL}
172
173
174
175 Gneric Tree から GIMPLE, そして RTL へとデータは変換され最後にアセンブリ言語で出力される.
176
177
178
179 \section{GCC-4.6 への実装}
180
181
182 \subsection{Tail Call Elimination}
183 CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
184 Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
185 call ではなく jmp を用いて大元の関数へ戻るようにする最適化のことである.
186 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
187
188
189 \begin{figure}[htpb]
190 \begin{center}
191 \scalebox{0.50}{\includegraphics{figure/continuation.eps}}
192 \end{center}
193 \caption{Tail Call Elimination}
194 \label{fig:continue}
195 \end{figure}
196
197
198
199 \subsubsection{expand\_call}
200
201
202
203 \subsection{引数渡し}
204 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される.
205 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
206 fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る.
207
208 \subsubsection{fastcall}
209 コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
210 C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
211 だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
212 そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
213 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである.
214
215 \begin{figure}[htpb]
216 \begin{center}
217 \scalebox{0.35}{\includegraphics{figure/fastcall.eps}}
218 \end{center}
219 \caption{fastcall属性付与}
220 \label{fig:fastcall}
221 \end{figure}
222
223 if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である.
224
225
226 \begin{thebibliography}{10}
227
228 \bibitem{1}{河野真治}:
229 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
230
231 \bibitem{2}{河野真治}:
232 “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000
233
234 \bibitem{3}{与儀健人,河野真治}:
235 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008
236
237 \bibitem{4}{与儀健人,河野真治}:
238 “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010
239
240 \bibitem{5}{下地篤樹,河野真治}:
241 “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008
242
243 \bibitem{6}{楊挺,河野真治}:
244 “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002
245
246 \bibitem{7}{GNU Compiler Collection (GCC) Internals}:
247 “http://gcc.gnu.org/onlinedocs/gccint/”
248
249
250 \end{thebibliography}
251
252
253 \begin{biography}
254 \nomember{大城 信康}
255 1989年生.
256 2008年琉球大学工学部情報工学科入学
257 %
258 \member{河野 真治}
259 1959年生．
260 1989年東京大学大学院情報工学課程修了 (工学博士)
261 同年Sony Computer Science Laboratory, Inc. 入社．
262 1996年より琉球大学工学部准教授
263 工学博士． ACM会員.
264 \end{biography}
265 \end{document}