%        File: slide.tex
%     Created: 火  6 24 12:51 PM 2008 J
% Last Change: 火  7  3 11:58 AM 2008 J
%
\documentclass[mathserif]{beamer}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{ulem}
%\usepackage{beamerthemesplit}
%manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf

\title[CbC on GCC]{組み込み向け低レベル言語 CbC の GCC による実装}
\author{与儀健人 \and 河野真治}
\institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻}
\date{\today}

\usetheme{Boadilla}
%\usetheme{default}
%\useoutertheme[subsection=false]{smoothbars}
%\useoutertheme{infolines}
\renewcommand{\kanjifamilydefault}{gt}

%
%
%  研究内容
%  CbC例
%  GCC
%  Tailcall
%  評価
%  環境付きgoto
%  今後の研究内容( 検証? REP マージャーの検証、タブロー法等 )
%
%

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{背景}
\begin{frame}
  \frametitle{研究背景}
  \begin{exampleblock}{Background}
    \begin{itemize}
      \item 近年、情報技術の発展により、ソフトウェアは大規模
	かつ複雑化する傾向にある。
      \item また、日常にあふれる様々な家電にもコンピュータが使われるようになり、
	組み込みソフトウェアの需要が拡大している。
      % 近年、情報技術の発展により、
      % ソフトウェアは大規模かつ複雑化する傾向にあります。
      % おなじ理由で、市場に出回る家電には冷蔵庫や洗濯機、電子ジャーやコーヒーメーカーに
      % いたるまで組み込み系のソフトおよびOSが使われるようになりました。
    \end{itemize}
  \end{exampleblock}
  %\begin{exampleblock}{Problem}
  \begin{Problem}
    \begin{itemize}
      \item 複雑化したソフトウェアの正当性(Validity)を保証できるか?
      \item 組み込みソフトやOSの記述に最適な言語とは?
      % 
      %
      %
    \end{itemize}
  \end{Problem}
  %\end{exampleblock}
\end{frame}

\begin{frame}
  \frametitle{研究内容}
  \begin{exampleblock}{Continuation based C (CbC)}
    \begin{itemize}
      \item Cよりも下位、アセンブラより上位の言語
      \item 入力、出力インターフェイスの組み合わせから、検証を自身で表現できる
      \item OS、デバイスドライバ、ハードウェアの記述が可能
    \end{itemize}
  \end{exampleblock}
  \begin{exampleblock}{Recent works}
    \begin{itemize}
      \item Micro-Cによる実装 (i386,PPC,mips,spu,arm)
      \item タブロー法によるCbCプログラムの検証
	%タブロー法を用いたContinuation based Cプログラムの検証, 下地 篤樹, 河野 真治(琉球大学) 日本ソフトウェア科学会第23回大会論文集, Sep, 2006
      \item CbCによるハードウェア記述の可能性
	%検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用 , 河野 真治 (琉球大学), 電子情報通信学会VLSI設計技術研究会, March, 2008
      \item 組み込みソフトウェアへの適用法
	%継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
    \end{itemize}
  \end{exampleblock}
\end{frame}

\begin{frame}
  \frametitle{GCCによるCbCコンパイラの実装}
  \begin{exampleblock}{Why is it needed?}
    \begin{itemize}
      \item 十数種のアーキテクチャへの対応が可能
      \item 構文木、RTLレベルでの高度な最適化
      \item ポータビリティー
    \end{itemize}
  \end{exampleblock}
  %Tailcallを使った実装方法が示されている
\end{frame}

\begin{comment}
  \frametitle{目標}
  \begin{exampleblock}{Purposes}
    \begin{itemize}
      \item アセンブラとC言語の中間にあたる
      \item 組み込み、OS、デバイスドライバの記述に適した、
      \item 検証を自身で表現できる
    \end{itemize}
  \end{exampleblock}
  \begin{exampleblock}{past Research}
    \begin{itemize}
      \item Micro-Cによる Continuation based C の開発 [Sep,2000]
      \item C言語からContinuation based Cへの変換 [Jul,2001]
      \item タブロー法を用いたContinuation based Cプログラムの検証 [Sep,2006]
    \end{itemize}
  \end{exampleblock}
\end{comment}

\begin{comment}
  \frametitle{CbCの現状}
  \begin{exampleblock}{Recent work}
    \begin{itemize}
      \item Micro-Cによる実装 (i386,PPC,mips,spu,arm)
      \item タブロー法によるCbCプログラムの検証
	%タブロー法を用いたContinuation based Cプログラムの検証, 下地 篤樹, 河野 真治(琉球大学) 日本ソフトウェア科学会第23回大会論文集, Sep, 2006
      \item CbCによるハードウェア記述
	%検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用 , 河野 真治 (琉球大学), 電子情報通信学会VLSI設計技術研究会, March, 2008
      \item 組み込みソフトウェアへの適用
	%継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
    \end{itemize}
  \end{exampleblock}
\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{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}
      \huge
    \item \verb|__code cs(int a, char *b)|
    \item \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}


\section{Tail call}

\begin{frame}
  \frametitle{Tail call elimination}
  \begin{exampleblock}{Waht is it?}
    \begin{itemize}
      \item 関数呼び出しに関する最適化
      \item call命令じゃなく、jmp命令を使用する (i386)
      \item スタックを拡張せず、現在のスタックフレームを書き潰す
    \end{itemize}
  \end{exampleblock}
  GCCへの実装ではこの最適化を利用して行う
\end{frame}

\begin{frame}
  \frametitle{Tail call elimination}
  \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps}
\end{frame}

\begin{comment}[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{comment}

\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 tree/RTL変換 (expand\_call) \hfill RTL Generator \hspace{5em}
    \item その他(エラー検出など) 
  \end{itemize}
\end{frame}

\begin{comment}
  \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{comment}

\begin{comment}
  \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{comment}

\section{評価}

\begin{frame}
  \frametitle{評価(ベンチマーク)}
  GCCとMicro-Cの間でベンチマーク測定をする
  \begin{itemize}
    \item 環境 i386 fedora core
    \item 使用したプログラム conv1
    \item 関数コールと演算の交互実行
  \end{itemize}
  引数の値によって同じ内容の別のソースを実行する
  \begin{description}
    \item[0] Cの関数を用いた演算
    \item[1] 上を機械的にコードセグメントに変換したもの
    \item[2] さらに手動で最適化したもの
    \item[3] 別の手法で最適化したもの
  \end{description}
\end{frame}

\begin{frame}[fragile]
  \frametitle{評価(ベンチマーク)}
  \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{exampleblock}{Result}
    \begin{itemize}
      \item GCCの最適化を使うことで、Micro-Cより早く動作する
      \item 単にCからCbCに機械的に変換しただけでは若干遅くなる が、
      \item そのコードを修正することで、C より高速化できる
    \end{itemize}
  \end{exampleblock}
\end{frame}

\renewcommand<>{\sout}[1]{\temporal#2{#1}{\beameroriginal{\sout}{#1}}{#1}}
\section{環境付き継続に関する考察}
\begin{frame}[fragile]
  \frametitle{環境付き継続}
  %\sout<2>{未実装の構文}\\
  未実装の構文
  %\uncover<2>{新たに実装された構文}
  \begin{verbatim}
  env = malloc(STACKSIZE);
  goto cs( 10 ), env;
  \end{verbatim}
  \begin{itemize}
    \item envは現在とは別のスタック空間を表す
      \begin{itemize}
	\item mallocで取得
	\item 中断した別スレッドのスッタクフレーム
	\item 関数から継続した場合の元のスタックフレーム
      \end{itemize}
    \item そのenvで表される環境(スタック)へスタックフレームを変更したあと継続する \\
      具体的には\verb|%ebp|を変更
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{環境付き継続}
  Micro-CでのCbCでは以下の使い方が主となっている
  \begin{verbatim}
  int func(void){
      /* something */
      goto cs( __environment, __return );
  }
  __code cs(void *env, void *ret){
      /* something */
      goto ret(20), env;
  }
  \end{verbatim}
  このように、\verb|__environment,__return|を使用して、呼び出し元関数の環境へ戻れる。\\
  この使用方法に限れば、GCCでも実装完了。
\end{frame}

\begin{frame}[fragile]
  \frametitle{実装方法}
  \begin{exampleblock}{``環境''を表すのに必要な物}
    \begin{itemize}
      \item スタックフレーム (\%ebp)
      \item 継続の引数を格納する位置
    \end{itemize}
  \end{exampleblock}
  この二つをメンバに持つ構造体を\verb|__environment|として渡す。

  この構造体のスペースはどこからとる?
  \begin{itemize}
    \item malloc? --- freeの問題がある
    \item static変数でも問題ない? --- スレッド、再帰関数の場合に問題が
    \item Thread-Local strage?
  \end{itemize}

  setjmpとの違いは?
\end{frame}

\section{まとめ}
\begin{frame}
  \frametitle{まとめ}
  \begin{exampleblock}{Conclusion}
    \begin{itemize}
      \item GCCにCbCコンパイラを実装
      \item そのベンチマークによる性能向上の確認
      \item 環境付き継続を一部実装
      \item 環境付き継続の実装及び問題点の考察
    \end{itemize}
  \end{exampleblock}

  \begin{exampleblock}{TO DO}
    \begin{itemize}
      \item 環境付き継続を完全にする
      \item PPCのindirect tailcall
      \item オプションの強制 
    \end{itemize}
  \end{exampleblock}
\end{frame}


%\begin{thebibliography}
  %\item[CbC]{} 河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
%\end{thebibliography}
%継続を持つCの下位言語によるシステム記述
%河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
%継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003

%\appendix
%\begin{frame}
  %\includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
%\end{frame}

\end{document}