# HG changeset patch # User kent # Date 1208890746 -32400 # Node ID 0cca1c3a062d7e0e3a52b7068fc7f2e65f45f020 # Parent f8cf4a3ac7a8db76bc368379623cd5ab5a8bd98f slide $B40@.(B? diff -r f8cf4a3ac7a8 -r 0cca1c3a062d Makefile --- a/Makefile Tue Apr 22 14:13:29 2008 +0900 +++ b/Makefile Wed Apr 23 03:59:06 2008 +0900 @@ -28,10 +28,11 @@ $(SLIDE1).ps: $(SLIDE1).dvi $(DVIPS) $^ - if [ -x $(BKMK2UNI) ]; then\ - mv $@ $@.tmp;\ - $(BKMK2UNI) -e < $@.tmp > $@;\ - fi + + #if [ -x $(BKMK2UNI) ]; then\ + #mv $@ $@.tmp;\ + #$(BKMK2UNI) -e < $@.tmp > $@;\ + #fi clean: rm -f *.{aux,log,nav,out,snm} diff -r f8cf4a3ac7a8 -r 0cca1c3a062d slide.tex --- a/slide.tex Tue Apr 22 14:13:29 2008 +0900 +++ b/slide.tex Wed Apr 23 03:59:06 2008 +0900 @@ -1,53 +1,76 @@ % File: slide.tex % Created: 月 4 21 08:00 PM 2008 J -% Last Change: 月 4 21 08:00 PM 2008 J +% Last Change: 月 4 22 17:18 PM 2008 J % \documentclass[mathserif]{beamer} \usepackage{graphicx} \usepackage{verbatim} -\usepackage{beamerthemesplit} +%\usepackage{beamerthemesplit} %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf -\title{Continuation based CコンパイラのGCC-4.2による実装} -\author{与儀 健人} +\title[CbC on GCC]{Continuation based CコンパイラのGCC-4.2による実装} +\author{与儀 健人 \and 河野真治} +\institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻} \date{\today} \usetheme{Boadilla} +%\usetheme{default} +%\useoutertheme[subsection=false]{smoothbars} +%\useoutertheme{infolines} +\renewcommand{\kanjifamilydefault}{gt} \begin{document} +\begin{frame} + \titlepage +\end{frame} + \section{背景} \begin{frame} \frametitle{研究背景} \begin{itemize} \item Continuation based C (CbC) \item Micro-CによるCbCコンパイラの実装 - \item 以前の論文により、GCCでコンパイラを実装する方法が示された + \item GCCでCbCコンパイラを実装する方法が分かっている \end{itemize} \end{frame} \begin{comment} 私たちの研究室ではCbCという言語を提案しています。 - CbCはCから関数の概念を取り払って、代わりに継続という概念を追加したもので、.. + CbCはCから関数の概念を取り払って、 + 代わりにコードセグメントという処理単位を追加したものです。詳しくは CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの つかってコンパイルしていました。 - このMicro-CによるコンパイラもGCCとくらべて遜色ないほど、良いコードをはくのですが\ldots - 細かな最適化などを比べると及ばない。 - 対応アーキテクチャ + このMicro-CもGCCとくらべて遜色ないほど、良いコードをはくのですが + はやり、UNIXの標準的なコンパイラであるGCCでコンパイルしたい - そこでGCCに移植する - 以前の論文によりGCCへの実装方法がしめされた。 - そこで、本研究ではGCCへの実装を行いました。 + また、以前の論文によりTail callを使ったGCCへの実装方法がしめされた。 + そこで、本研究ではCbCのGCCへの実装を行いましたので、 + その評価と合わせて報告したいと思います \end{comment} \section{CbC} \begin{frame} \frametitle{Continuation based Cについて} - \begin{itemize} - \item - \end{itemize} + \begin{exampleblock}{What is it?} + \begin{itemize} + \item 琉球大学 並列信頼研究室で開発 + \item 構文はC言語とほぼ同じ + \item 関数の除去、コードセグメントの追加 + \item コードセグメントを繋ぐ``継続''を導入 + \end{itemize} + \end{exampleblock} \end{frame} +\begin{comment} + まずは、本研究室が提案しているCbCについて少し説明します + 構文はC言語とほぼ同じです + ただし Cから関数や、while,forなどのloopを除去し + code segmentという処理の単位を追加しています + また、code segmentどうしの移動(これを継続と呼びます) + をgotoを使って表します + ...聴いても分かりにくいと思うので、コード例をみましょう +\end{comment} \begin{frame}[fragile] \frametitle{CbCコード例} @@ -77,15 +100,31 @@ \includegraphics[width=\textwidth]{figures/CbC-loop.eps} \end{columns} \end{frame} +\begin{comment} + 見にくい？ + これはCのwhile文をcode segmentにしたものです + みての通り、_ _codeという関数の様なものが三つあります + この一つずつがコードセグメントです + 最初に while_condが実行されます これは条件判定ですね + .. . + 簡単でしたが、少し分かっていただけたでしょうか？ +\end{comment} \begin{frame}[fragile] \frametitle{実装に必要な構文} \begin{itemize} \large - \item コードセグメント宣言 \hfill\verb|__ code cs(int a, char *b)| - \item 継続 \hfill\verb|goto cs(10, "abc");| + \item \verb|__code cs(int a, char *b)| + \item \verb|goto cs(10, "abc");| \end{itemize} \end{frame} +\begin{comment} + 実装に必要な構文を説明します + まずはcode segmentの定義です コード例にもあったように、 + コードセグメントの定義や宣言、コードセグメントポインタの宣言などをこの構文で行えます + つぎにgoto. + この二つを実装することでCbCを動作させることができます +\end{comment} \section{GCC} \begin{frame} @@ -98,6 +137,11 @@ \item コンパイルだけでなくas, ldなどの統合環境 \end{itemize} \end{frame} +\begin{comment} + GNU Compiler Collection + .. . ですが、皆さん良くご存知だと思いますので、 + ここではGCCの内部構造について簡単に説明します +\end{comment} \begin{frame} \frametitle{GCCコンパイルパス} @@ -113,16 +157,24 @@ \end{columns} \end{frame} \begin{comment} + 図は GCCがどのようにコンパイルを進めるかを表したものです パーサによってGenericに変換 一般的にいう構文木、言語の構造をそのままツリーにしている - Static Single Assignment であるGIMPLEに変換 - ここで、ほとんど言語の違いがなくなる + 次にGEnericはGimplifyというpassによってGIMPLEに変換されます + Static Single Assignment + データ構造自体はGenericとかわりまりませんが、いろいろ制約が加わります RTLに変換 アーキテクチャに依存しないアセンブラ - 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる + * 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる + 今回の実装でどの部分を変更したのか + コードセグメントや継続のパースのためにParserを修正 + それらの構文を表すGeneric Treeを作る + そのTreeをRTLに変換するRTLGenerator を修正 + + そこで、Tailcalleliminationについて説明します \end{comment} @@ -131,6 +183,24 @@ \frametitle{Tail call elimination} \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps} \end{frame} +\begin{comment} + このTail call EliminationはGCCの最適化の一つで、 + 「関数の最後に別の関数を呼び出してる場合は、 + callじゃなくてjmpでいいじゃないか」 + というアイデアをもとに設計されてます + + 図を見ていただくと分かるとおり、ここでは関数main, A, B + を定義しています + そして関数Aでは最後に関数Bを呼び出しています + この場合、mainからAをよび、AからBをよび、 + Bが終わるとAに戻り、すぐにret命令でmainにもどるという処理になります + + ですが、明らかにAに戻るのは無駄でしょう + この無駄はAからBを呼ぶ際にcallでなくjmpを使うことで回避できます + これが単純なTail callの例です + + ですが、たった1命令で最適化と言えるのか? +\end{comment} \begin{frame}[fragile] \begin{columns}[t] @@ -172,10 +242,8 @@ \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない \end{enumerate} -\end{frame} - -\begin{frame} - \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps} + \center + \visible<2>{引数をすべて固定数とすることで対応} \end{frame} \section{実装} @@ -183,31 +251,44 @@ \frametitle{実装} \begin{itemize} \item \_\_code トークンの追加 - \item code segmentのパース - \item gotoのパース - \item \alert<2>{tree/RTL変換 (expand\_call)} + \item code segmentのパース \hfill Parser \hspace{5em} + \item gotoのパース \hfill Parser \hspace{5em} + \item code segment/goto を表すGeneric Tree + \item \alert<2>{tree/RTL変換 (expand\_call)} \hfill RTL Generator \hspace{5em} \item その他(エラー検出など) \end{itemize} \end{frame} +\begin{comment} + トークン + パーサ recursive Decent + expand_call + expand_cbc_goto +\end{comment} \begin{frame} \frametitle{expand\_call} - \begin{itemize} - \item 関数呼び出しのtreeからRTLへ変換する - \item Tail callが可能ならその最適化を行う - \item この関数のみで1200行もある - \item そのほとんどがTail call可否の判定 - \item そして読みづらい - \end{itemize} + \begin{exampleblock}{What is the function?} + \begin{itemize} + \item 関数呼び出しのtreeからRTLへ変換する + \item Tail callが可能ならその最適化を行う + \item この関数のみで1200行もある + \item そのほとんどがTail call可否の判定 + \item そして読みづらい + \end{itemize} + \end{exampleblock} \end{frame} \begin{frame} \frametitle{expand\_cbc\_goto} - \begin{itemize} - \item code segmentへのgotoを表したtreeを受け取る - \item 確実にTail callでcode segmentにgoto - \item 無駄なTail call可否判定を削除 - \end{itemize} + \begin{exampleblock}{What is it doing?} + \begin{itemize} + \item code segmentへのgotoを表したtreeをRTLに変換 + \item 無駄なTail call可否判定を削除 + \item Tail callの条件を強制 + \item 確実にTail callを適用 + \item 500行程度 + \end{itemize} + \end{exampleblock} \end{frame} @@ -234,19 +315,32 @@ \end{frame} \begin{frame} + \frametitle{考察} +\end{frame} + +\begin{frame} \frametitle{まとめ} - \begin{itemize} - \item GCCにCbCコンパイラを実装 - \item そのベンチマーク - \end{itemize} - + \begin{block}{まとめ} + \begin{itemize} + \item GCCにCbCコンパイラを実装 + \item そのベンチマーク + \item 性能向上を確認 + \end{itemize} + \end{block} - \begin{itemize} - \item environment - \item PPCのRTL変換不能 - \item オプションの強制 - \item SPU対応とGCCのversion - \end{itemize} + \begin{block}{TO DO} + \begin{itemize} + \item environment + \item PPCのRTL変換不能 + \item オプションの強制 + \item SPU対応とGCCのversion + \end{itemize} + \end{block} +\end{frame} + +\appendix +\begin{frame} + \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps} \end{frame} \end{document}