%        File: slide.tex
%     Created: 月  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}
%manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf

\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でCbCコンパイラを実装する方法が分かっている
  \end{itemize}
\end{frame}
\begin{comment}
  私たちの研究室ではCbCという言語を提案しています。
  CbCはCから関数の概念を取り払って、
  代わりにコードセグメントという処理単位を追加したものです。詳しくは

  CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの
  つかってコンパイルしていました。
  このMicro-CもGCCとくらべて遜色ないほど、良いコードをはくのですが
  はやり、UNIXの標準的なコンパイラであるGCCでコンパイルしたい

  また、以前の論文によりTail callを使ったGCCへの実装方法がしめされた。
  そこで、本研究ではCbCのGCCへの実装を行いましたので、
  その評価と合わせて報告したいと思います
\end{comment}


\section{CbC}
\begin{frame}
  \frametitle{Continuation based Cについて}
  \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コード例}
  \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{comment}
  見にくい？
  これはCのwhile文をcode segmentにしたものです
  みての通り、_ _codeという関数の様なものが三つあります
  この一つずつがコードセグメントです
  最初に while_condが実行されます これは条件判定ですね
  .. .
  簡単でしたが、少し分かっていただけたでしょうか？
\end{comment}

\begin{frame}[fragile]
  \frametitle{実装に必要な構文}
  \begin{itemize}
      \large
    \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}
  \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{comment}
  GNU Compiler Collection
  .. . ですが、皆さん良くご存知だと思いますので、
  ここではGCCの内部構造について簡単に説明します
\end{comment}

\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}
  図は GCCがどのようにコンパイルを進めるかを表したものです
  パーサによってGenericに変換
  一般的にいう構文木、言語の構造をそのままツリーにしている

  次にGEnericはGimplifyというpassによってGIMPLEに変換されます
  Static Single Assignment
  データ構造自体はGenericとかわりまりませんが、いろいろ制約が加わります

  RTLに変換
  アーキテクチャに依存しないアセンブラ

 * 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる
  今回の実装でどの部分を変更したのか
  コードセグメントや継続のパースのためにParserを修正
  それらの構文を表すGeneric Treeを作る
  そのTreeをRTLに変換するRTLGenerator を修正

  そこで、Tailcalleliminationについて説明します
\end{comment}


\section{Tail call}
\begin{frame}
  \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]
  \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}
  \center
  \visible<2>{引数をすべて固定数とすることで対応}
\end{frame}

\section{実装}
\begin{frame}
  \frametitle{実装}
  \begin{itemize}
    \item \_\_code トークンの追加
    \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{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{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}


\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{考察}
%\end{frame}

\begin{frame}
  \frametitle{まとめ}
  \begin{block}{まとめ}
    \begin{itemize}
      \item GCCにCbCコンパイラを実装
      \item そのベンチマーク
      \item 性能向上を確認
    \end{itemize}
  \end{block}

  \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}