Mercurial > hg > Papers > 2008 > kent-sigos
view slide.tex @ 7:f8cf4a3ac7a8
$B$R$H$^$:(Bslide.tex$B40@.(B
author | kent |
---|---|
date | Tue, 22 Apr 2008 14:13:29 +0900 |
parents | bfb290984b07 |
children | 0cca1c3a062d |
line wrap: on
line source
% File: slide.tex % Created: 月 4 21 08:00 PM 2008 J % Last Change: 月 4 21 08:00 PM 2008 J % \documentclass[mathserif]{beamer} \usepackage{graphicx} \usepackage{verbatim} \usepackage{beamerthemesplit} %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf \title{Continuation based CコンパイラのGCC-4.2による実装} \author{与儀 健人} \date{\today} \usetheme{Boadilla} \begin{document} \section{背景} \begin{frame} \frametitle{研究背景} \begin{itemize} \item Continuation based C (CbC) \item Micro-CによるCbCコンパイラの実装 \item 以前の論文により、GCCでコンパイラを実装する方法が示された \end{itemize} \end{frame} \begin{comment} 私たちの研究室ではCbCという言語を提案しています。 CbCはCから関数の概念を取り払って、代わりに継続という概念を追加したもので、.. CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの つかってコンパイルしていました。 このMicro-CによるコンパイラもGCCとくらべて遜色ないほど、良いコードをはくのですが\ldots 細かな最適化などを比べると及ばない。 対応アーキテクチャ そこでGCCに移植する 以前の論文によりGCCへの実装方法がしめされた。 そこで、本研究ではGCCへの実装を行いました。 \end{comment} \section{CbC} \begin{frame} \frametitle{Continuation based Cについて} \begin{itemize} \item \end{itemize} \end{frame} \begin{frame}[fragile] \frametitle{CbCコード例} \begin{columns} \column{.4\textwidth} \flushleft \small \begin{verbatim} __code while_process(int total,int count){ total += count; count++; goto while_cond(total, count); } __code while_cond(int total, int count){ if ( count <= 100 ){ goto while_process(total, count); }else{ goto while_end(total); } } __code while_end(int total){ goto cs_exit(0); } \end{verbatim} \column{.1\textwidth} \column{.3\textwidth} \flushright \includegraphics[width=\textwidth]{figures/CbC-loop.eps} \end{columns} \end{frame} \begin{frame}[fragile] \frametitle{実装に必要な構文} \begin{itemize} \large \item コードセグメント宣言 \hfill\verb|__ code cs(int a, char *b)| \item 継続 \hfill\verb|goto cs(10, "abc");| \end{itemize} \end{frame} \section{GCC} \begin{frame} \frametitle{GNU Compiler Collection} \begin{itemize} \item UNIXにおける標準的なコンパイラ \item C, C++, java, FORTRAN, Ada .. \item i386, PowerPC, MIPS, SPARC .. \item 強力な最適化機構 \item コンパイルだけでなくas, ldなどの統合環境 \end{itemize} \end{frame} \begin{frame} \frametitle{GCCコンパイルパス} \begin{columns} \column{.5\textwidth} \includegraphics[width=\textwidth]{figures/GCC-pass-slide.eps} \column{.4\textwidth} \begin{description} \item[Generic Tree] 構文木 \item[GIMPLE] SSA \item[RTL] 中間コード \end{description} \end{columns} \end{frame} \begin{comment} パーサによってGenericに変換 一般的にいう構文木、言語の構造をそのままツリーにしている Static Single Assignment であるGIMPLEに変換 ここで、ほとんど言語の違いがなくなる RTLに変換 アーキテクチャに依存しないアセンブラ 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる \end{comment} \section{Tail call} \begin{frame} \frametitle{Tail call elimination} \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps} \end{frame} \begin{frame}[fragile] \begin{columns}[t] \column{.5\textwidth} \begin{verbatim} A: pushl %ebp movl %esp, %ebp subl $24, %esp movl 20(%ebp), %eax addl 16(%ebp), %eax movl %eax, 8(%esp) movl 12(%ebp), %eax movl %eax, 4(%esp) movl 8(%ebp), %eax movl %eax, (%esp) call B leave ret \end{verbatim} \column{.5\textwidth} \begin{verbatim} A: pushl %ebp movl %esp, %ebp movl 20(%ebp), %eax addl %eax, 16(%ebp) popl %ebp jmp B \end{verbatim} \end{columns} \end{frame} \begin{frame} \frametitle{Tail callの条件} \begin{enumerate} \item 関数コールがreturnの直前にある \item 関数の返す型がcallerとcalleeで一致している \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない \end{enumerate} \end{frame} \begin{frame} \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps} \end{frame} \section{実装} \begin{frame} \frametitle{実装} \begin{itemize} \item \_\_code トークンの追加 \item code segmentのパース \item gotoのパース \item \alert<2>{tree/RTL変換 (expand\_call)} \item その他(エラー検出など) \end{itemize} \end{frame} \begin{frame} \frametitle{expand\_call} \begin{itemize} \item 関数呼び出しのtreeからRTLへ変換する \item Tail callが可能ならその最適化を行う \item この関数のみで1200行もある \item そのほとんどがTail call可否の判定 \item そして読みづらい \end{itemize} \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} \end{frame} \section{評価} \begin{frame}[fragile] \frametitle{評価(ベンチマーク)} \begin{itemize} \item 環境 i386 fedora core \item 使用したプログラム conv1 \end{itemize} \centering \begin{tabular}{|l|r|r|r|r|} \hline & ./conv1 0 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline Micro-C & 5.25 & 8.97 & 2.19 & 2.73 \\ \hline \hline GCC & 3.69 & 4.87 & 3.08 & 3.65 \\ \hline GCC (+omit) & 2.74 & 4.20 & 2.25 & 2.76 \\ \hline GCC (+fastcall) & 2.70 & 3.44 & 1.76 & 2.34 \\ \hline \hline TCC & 4.15 &122.28& 84.91&102.59\\ \hline \end{tabular} \begin{description} \item[+omit] -fomit-frame-pointerオプションを付加 \item[+fastcall] \verb|__attribute__ ((fastcall))|を付加 \end{description} \end{frame} \begin{frame} \frametitle{まとめ} \begin{itemize} \item GCCにCbCコンパイラを実装 \item そのベンチマーク \end{itemize} \begin{itemize} \item environment \item PPCのRTL変換不能 \item オプションの強制 \item SPU対応とGCCのversion \end{itemize} \end{frame} \end{document}