|
6
|
1 % File: slide.tex
|
|
|
2 % Created: 月 4 21 08:00 PM 2008 J
|
|
8
|
3 % Last Change: 月 4 22 17:18 PM 2008 J
|
|
6
|
4 %
|
|
|
5 \documentclass[mathserif]{beamer}
|
|
|
6 \usepackage{graphicx}
|
|
7
|
7 \usepackage{verbatim}
|
|
8
|
8 %\usepackage{beamerthemesplit}
|
|
6
|
9 %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf
|
|
|
10
|
|
8
|
11 \title[CbC on GCC]{Continuation based CコンパイラのGCC-4.2による実装}
|
|
|
12 \author{与儀 健人 \and 河野真治}
|
|
|
13 \institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻}
|
|
6
|
14 \date{\today}
|
|
|
15
|
|
7
|
16 \usetheme{Boadilla}
|
|
8
|
17 %\usetheme{default}
|
|
|
18 %\useoutertheme[subsection=false]{smoothbars}
|
|
|
19 %\useoutertheme{infolines}
|
|
|
20 \renewcommand{\kanjifamilydefault}{gt}
|
|
7
|
21
|
|
6
|
22 \begin{document}
|
|
|
23
|
|
8
|
24 \begin{frame}
|
|
|
25 \titlepage
|
|
|
26 \end{frame}
|
|
|
27
|
|
7
|
28 \section{背景}
|
|
|
29 \begin{frame}
|
|
|
30 \frametitle{研究背景}
|
|
|
31 \begin{itemize}
|
|
|
32 \item Continuation based C (CbC)
|
|
|
33 \item Micro-CによるCbCコンパイラの実装
|
|
8
|
34 \item GCCでCbCコンパイラを実装する方法が分かっている
|
|
7
|
35 \end{itemize}
|
|
|
36 \end{frame}
|
|
|
37 \begin{comment}
|
|
|
38 私たちの研究室ではCbCという言語を提案しています。
|
|
8
|
39 CbCはCから関数の概念を取り払って、
|
|
|
40 代わりにコードセグメントという処理単位を追加したものです。詳しくは
|
|
7
|
41
|
|
|
42 CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの
|
|
|
43 つかってコンパイルしていました。
|
|
8
|
44 このMicro-CもGCCとくらべて遜色ないほど、良いコードをはくのですが
|
|
|
45 はやり、UNIXの標準的なコンパイラであるGCCでコンパイルしたい
|
|
7
|
46
|
|
8
|
47 また、以前の論文によりTail callを使ったGCCへの実装方法がしめされた。
|
|
|
48 そこで、本研究ではCbCのGCCへの実装を行いましたので、
|
|
|
49 その評価と合わせて報告したいと思います
|
|
7
|
50 \end{comment}
|
|
|
51
|
|
|
52
|
|
|
53 \section{CbC}
|
|
6
|
54 \begin{frame}
|
|
|
55 \frametitle{Continuation based Cについて}
|
|
8
|
56 \begin{exampleblock}{What is it?}
|
|
|
57 \begin{itemize}
|
|
|
58 \item 琉球大学 並列信頼研究室で開発
|
|
|
59 \item 構文はC言語とほぼ同じ
|
|
|
60 \item 関数の除去、コードセグメントの追加
|
|
|
61 \item コードセグメントを繋ぐ``継続''を導入
|
|
|
62 \end{itemize}
|
|
|
63 \end{exampleblock}
|
|
6
|
64 \end{frame}
|
|
8
|
65 \begin{comment}
|
|
|
66 まずは、本研究室が提案しているCbCについて少し説明します
|
|
|
67 構文はC言語とほぼ同じです
|
|
|
68 ただし Cから関数や、while,forなどのloopを除去し
|
|
|
69 code segmentという処理の単位を追加しています
|
|
|
70 また、code segmentどうしの移動(これを継続と呼びます)
|
|
|
71 をgotoを使って表します
|
|
|
72 ...聴いても分かりにくいと思うので、コード例をみましょう
|
|
|
73 \end{comment}
|
|
6
|
74
|
|
|
75 \begin{frame}[fragile]
|
|
|
76 \frametitle{CbCコード例}
|
|
|
77 \begin{columns}
|
|
|
78 \column{.4\textwidth}
|
|
7
|
79 \flushleft \small
|
|
6
|
80 \begin{verbatim}
|
|
7
|
81 __code while_process(int total,int count){
|
|
6
|
82 total += count;
|
|
|
83 count++;
|
|
|
84 goto while_cond(total, count);
|
|
|
85 }
|
|
|
86 __code while_cond(int total, int count){
|
|
|
87 if ( count <= 100 ){
|
|
|
88 goto while_process(total, count);
|
|
|
89 }else{
|
|
|
90 goto while_end(total);
|
|
|
91 }
|
|
|
92 }
|
|
|
93 __code while_end(int total){
|
|
|
94 goto cs_exit(0);
|
|
|
95 }
|
|
|
96 \end{verbatim}
|
|
7
|
97 \column{.1\textwidth}
|
|
6
|
98 \column{.3\textwidth}
|
|
7
|
99 \flushright
|
|
|
100 \includegraphics[width=\textwidth]{figures/CbC-loop.eps}
|
|
6
|
101 \end{columns}
|
|
|
102 \end{frame}
|
|
8
|
103 \begin{comment}
|
|
|
104 見にくい？
|
|
|
105 これはCのwhile文をcode segmentにしたものです
|
|
|
106 みての通り、_ _codeという関数の様なものが三つあります
|
|
|
107 この一つずつがコードセグメントです
|
|
|
108 最初に while_condが実行されます これは条件判定ですね
|
|
|
109 .. .
|
|
|
110 簡単でしたが、少し分かっていただけたでしょうか？
|
|
|
111 \end{comment}
|
|
6
|
112
|
|
|
113 \begin{frame}[fragile]
|
|
|
114 \frametitle{実装に必要な構文}
|
|
|
115 \begin{itemize}
|
|
7
|
116 \large
|
|
8
|
117 \item \verb|__code cs(int a, char *b)|
|
|
|
118 \item \verb|goto cs(10, "abc");|
|
|
7
|
119 \end{itemize}
|
|
|
120 \end{frame}
|
|
8
|
121 \begin{comment}
|
|
|
122 実装に必要な構文を説明します
|
|
|
123 まずはcode segmentの定義です コード例にもあったように、
|
|
|
124 コードセグメントの定義や宣言、コードセグメントポインタの宣言などをこの構文で行えます
|
|
|
125 つぎにgoto.
|
|
|
126 この二つを実装することでCbCを動作させることができます
|
|
|
127 \end{comment}
|
|
7
|
128
|
|
|
129 \section{GCC}
|
|
|
130 \begin{frame}
|
|
|
131 \frametitle{GNU Compiler Collection}
|
|
|
132 \begin{itemize}
|
|
|
133 \item UNIXにおける標準的なコンパイラ
|
|
|
134 \item C, C++, java, FORTRAN, Ada ..
|
|
|
135 \item i386, PowerPC, MIPS, SPARC ..
|
|
|
136 \item 強力な最適化機構
|
|
|
137 \item コンパイルだけでなくas, ldなどの統合環境
|
|
6
|
138 \end{itemize}
|
|
|
139 \end{frame}
|
|
8
|
140 \begin{comment}
|
|
|
141 GNU Compiler Collection
|
|
|
142 .. . ですが、皆さん良くご存知だと思いますので、
|
|
|
143 ここではGCCの内部構造について簡単に説明します
|
|
|
144 \end{comment}
|
|
6
|
145
|
|
|
146 \begin{frame}
|
|
7
|
147 \frametitle{GCCコンパイルパス}
|
|
6
|
148 \begin{columns}
|
|
|
149 \column{.5\textwidth}
|
|
|
150 \includegraphics[width=\textwidth]{figures/GCC-pass-slide.eps}
|
|
7
|
151 \column{.4\textwidth}
|
|
|
152 \begin{description}
|
|
|
153 \item[Generic Tree] 構文木
|
|
|
154 \item[GIMPLE] SSA
|
|
|
155 \item[RTL] 中間コード
|
|
|
156 \end{description}
|
|
|
157 \end{columns}
|
|
|
158 \end{frame}
|
|
|
159 \begin{comment}
|
|
8
|
160 図は GCCがどのようにコンパイルを進めるかを表したものです
|
|
7
|
161 パーサによってGenericに変換
|
|
|
162 一般的にいう構文木、言語の構造をそのままツリーにしている
|
|
|
163
|
|
8
|
164 次にGEnericはGimplifyというpassによってGIMPLEに変換されます
|
|
|
165 Static Single Assignment
|
|
|
166 データ構造自体はGenericとかわりまりませんが、いろいろ制約が加わります
|
|
7
|
167
|
|
|
168 RTLに変換
|
|
|
169 アーキテクチャに依存しないアセンブラ
|
|
|
170
|
|
8
|
171 * 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる
|
|
|
172 今回の実装でどの部分を変更したのか
|
|
|
173 コードセグメントや継続のパースのためにParserを修正
|
|
|
174 それらの構文を表すGeneric Treeを作る
|
|
|
175 そのTreeをRTLに変換するRTLGenerator を修正
|
|
|
176
|
|
|
177 そこで、Tailcalleliminationについて説明します
|
|
7
|
178 \end{comment}
|
|
|
179
|
|
|
180
|
|
|
181 \section{Tail call}
|
|
|
182 \begin{frame}
|
|
|
183 \frametitle{Tail call elimination}
|
|
|
184 \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps}
|
|
|
185 \end{frame}
|
|
8
|
186 \begin{comment}
|
|
|
187 このTail call EliminationはGCCの最適化の一つで、
|
|
|
188 「関数の最後に別の関数を呼び出してる場合は、
|
|
|
189 callじゃなくてjmpでいいじゃないか」
|
|
|
190 というアイデアをもとに設計されてます
|
|
|
191
|
|
|
192 図を見ていただくと分かるとおり、ここでは関数main, A, B
|
|
|
193 を定義しています
|
|
|
194 そして関数Aでは最後に関数Bを呼び出しています
|
|
|
195 この場合、mainからAをよび、AからBをよび、
|
|
|
196 Bが終わるとAに戻り、すぐにret命令でmainにもどるという処理になります
|
|
|
197
|
|
|
198 ですが、明らかにAに戻るのは無駄でしょう
|
|
|
199 この無駄はAからBを呼ぶ際にcallでなくjmpを使うことで回避できます
|
|
|
200 これが単純なTail callの例です
|
|
|
201
|
|
|
202 ですが、たった1命令で最適化と言えるのか?
|
|
|
203 \end{comment}
|
|
7
|
204
|
|
|
205 \begin{frame}[fragile]
|
|
|
206 \begin{columns}[t]
|
|
|
207 \column{.5\textwidth}
|
|
|
208 \begin{verbatim}
|
|
|
209 A:
|
|
|
210 pushl %ebp
|
|
|
211 movl %esp, %ebp
|
|
|
212 subl $24, %esp
|
|
|
213 movl 20(%ebp), %eax
|
|
|
214 addl 16(%ebp), %eax
|
|
|
215 movl %eax, 8(%esp)
|
|
|
216 movl 12(%ebp), %eax
|
|
|
217 movl %eax, 4(%esp)
|
|
|
218 movl 8(%ebp), %eax
|
|
|
219 movl %eax, (%esp)
|
|
|
220 call B
|
|
|
221 leave
|
|
|
222 ret
|
|
|
223 \end{verbatim}
|
|
|
224 \column{.5\textwidth}
|
|
|
225 \begin{verbatim}
|
|
|
226 A:
|
|
|
227 pushl %ebp
|
|
|
228 movl %esp, %ebp
|
|
|
229 movl 20(%ebp), %eax
|
|
|
230 addl %eax, 16(%ebp)
|
|
|
231 popl %ebp
|
|
|
232 jmp B
|
|
|
233 \end{verbatim}
|
|
6
|
234 \end{columns}
|
|
|
235 \end{frame}
|
|
|
236
|
|
|
237 \begin{frame}
|
|
7
|
238 \frametitle{Tail callの条件}
|
|
|
239 \begin{enumerate}
|
|
|
240 \item 関数コールがreturnの直前にある
|
|
|
241 \item 関数の返す型がcallerとcalleeで一致している
|
|
|
242 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
|
|
|
243 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
|
|
|
244 \end{enumerate}
|
|
8
|
245 \center
|
|
|
246 \visible<2>{引数をすべて固定数とすることで対応}
|
|
7
|
247 \end{frame}
|
|
|
248
|
|
|
249 \section{実装}
|
|
|
250 \begin{frame}
|
|
6
|
251 \frametitle{実装}
|
|
7
|
252 \begin{itemize}
|
|
6
|
253 \item \_\_code トークンの追加
|
|
8
|
254 \item code segmentのパース \hfill Parser \hspace{5em}
|
|
|
255 \item gotoのパース \hfill Parser \hspace{5em}
|
|
|
256 \item code segment/goto を表すGeneric Tree
|
|
|
257 \item \alert<2>{tree/RTL変換 (expand\_call)} \hfill RTL Generator \hspace{5em}
|
|
6
|
258 \item その他(エラー検出など)
|
|
7
|
259 \end{itemize}
|
|
6
|
260 \end{frame}
|
|
8
|
261 \begin{comment}
|
|
|
262 トークン
|
|
|
263 パーサ recursive Decent
|
|
|
264 expand_call
|
|
|
265 expand_cbc_goto
|
|
|
266 \end{comment}
|
|
6
|
267
|
|
|
268 \begin{frame}
|
|
|
269 \frametitle{expand\_call}
|
|
8
|
270 \begin{exampleblock}{What is the function?}
|
|
|
271 \begin{itemize}
|
|
|
272 \item 関数呼び出しのtreeからRTLへ変換する
|
|
|
273 \item Tail callが可能ならその最適化を行う
|
|
|
274 \item この関数のみで1200行もある
|
|
|
275 \item そのほとんどがTail call可否の判定
|
|
|
276 \item そして読みづらい
|
|
|
277 \end{itemize}
|
|
|
278 \end{exampleblock}
|
|
6
|
279 \end{frame}
|
|
|
280
|
|
|
281 \begin{frame}
|
|
|
282 \frametitle{expand\_cbc\_goto}
|
|
8
|
283 \begin{exampleblock}{What is it doing?}
|
|
|
284 \begin{itemize}
|
|
|
285 \item code segmentへのgotoを表したtreeをRTLに変換
|
|
|
286 \item 無駄なTail call可否判定を削除
|
|
|
287 \item Tail callの条件を強制
|
|
|
288 \item 確実にTail callを適用
|
|
|
289 \item 500行程度
|
|
|
290 \end{itemize}
|
|
|
291 \end{exampleblock}
|
|
6
|
292 \end{frame}
|
|
|
293
|
|
|
294
|
|
7
|
295 \section{評価}
|
|
6
|
296 \begin{frame}[fragile]
|
|
|
297 \frametitle{評価(ベンチマーク)}
|
|
|
298 \begin{itemize}
|
|
|
299 \item 環境 i386 fedora core
|
|
|
300 \item 使用したプログラム conv1
|
|
7
|
301 \end{itemize}
|
|
6
|
302 \centering
|
|
|
303 \begin{tabular}{|l|r|r|r|r|} \hline
|
|
|
304 & ./conv1 0 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
|
|
|
305 Micro-C & 5.25 & 8.97 & 2.19 & 2.73 \\ \hline \hline
|
|
|
306 GCC & 3.69 & 4.87 & 3.08 & 3.65 \\ \hline
|
|
|
307 GCC (+omit) & 2.74 & 4.20 & 2.25 & 2.76 \\ \hline
|
|
|
308 GCC (+fastcall) & 2.70 & 3.44 & 1.76 & 2.34 \\ \hline \hline
|
|
|
309 TCC & 4.15 &122.28& 84.91&102.59\\ \hline
|
|
|
310 \end{tabular}
|
|
|
311 \begin{description}
|
|
|
312 \item[+omit] -fomit-frame-pointerオプションを付加
|
|
|
313 \item[+fastcall] \verb|__attribute__ ((fastcall))|を付加
|
|
|
314 \end{description}
|
|
|
315 \end{frame}
|
|
|
316
|
|
9
|
317 %\begin{frame}
|
|
|
318 %\frametitle{考察}
|
|
|
319 %\end{frame}
|
|
8
|
320
|
|
|
321 \begin{frame}
|
|
6
|
322 \frametitle{まとめ}
|
|
8
|
323 \begin{block}{まとめ}
|
|
|
324 \begin{itemize}
|
|
|
325 \item GCCにCbCコンパイラを実装
|
|
|
326 \item そのベンチマーク
|
|
|
327 \item 性能向上を確認
|
|
|
328 \end{itemize}
|
|
|
329 \end{block}
|
|
6
|
330
|
|
8
|
331 \begin{block}{TO DO}
|
|
|
332 \begin{itemize}
|
|
|
333 \item environment
|
|
|
334 \item PPCのRTL変換不能
|
|
|
335 \item オプションの強制
|
|
|
336 \item SPU対応とGCCのversion
|
|
|
337 \end{itemize}
|
|
|
338 \end{block}
|
|
|
339 \end{frame}
|
|
|
340
|
|
|
341 \appendix
|
|
|
342 \begin{frame}
|
|
|
343 \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
|
|
6
|
344 \end{frame}
|
|
|
345
|
|
|
346 \end{document}
|
|
|
347
|
|
|
348
|
|
|
349
|
|
|
350
|
