Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 1:878e70793abe

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