# HG changeset patch
# User kent
# Date 1214898699 -32400
# Node ID 448fb638bfa008aff9f4e7ee1ffbda12f43d4e1f
# Parent  e35e566b9983452350daf31fb01ae981052c43f5
add tex for slide.

diff -r e35e566b9983 -r 448fb638bfa0 Makefile
--- a/Makefile	Wed Jun 18 12:55:12 2008 +0900
+++ b/Makefile	Tue Jul 01 16:51:39 2008 +0900
@@ -1,48 +1,46 @@
 DVIPDF = dvipdfmx
-#DVIPDF_OPT = -f ptex-hiragino.map -f otf-hiragino.map
+DVIPDF_OPT = -f ptex-hiragino.map -f otf-hiragino.map
 LATEX  = platex
-PS2PDF = ps2pdf14
+PS2PDF = ps2pdf
 DVIPS  = dvips
-BKMK2UNI = ~/src/bkmk2uni
 
-TARGET1 = main
-#TARGET2 = resume
-#TARGET3 = resume2
-SLIDE1 = slide
+TEXS = main
+SLIDES = slide
 
-PDFs = $(TARGET1).pdf
-DVIs = $(TARGET1).dvi
-TEXs = $(TARGET1).tex
-
+.PHONY: all clean distclean
 .SUFFIXES: .tex .dvi .pdf
 
-all: $(PDFs)
+all: $(addsuffix .pdf,$(TEXS)) $(addsuffix .pdf,$(SLIDES))
 
-.dvi.pdf:
+
+$(addsuffix .pdf,$(TEXS)): %.pdf: %.dvi
 	$(DVIPDF) $(DVIPDF_OPT) $^
-.tex.dvi:
-	$(LATEX) $^
 
-$(SLIDE1).pdf: $(SLIDE1).ps
+$(addsuffix .pdf,$(SLIDES)): %.pdf: %.ps
 	$(PS2PDF) $^
 
-$(SLIDE1).ps: $(SLIDE1).dvi
+$(addsuffix .ps,$(SLIDES)): %.ps: %.dvi
 	$(DVIPS) $^
 
-	#if [ -x $(BKMK2UNI) ]; then\
-	  #mv $@ $@.tmp;\
-	  #$(BKMK2UNI) -e < $@.tmp > $@;\
-	#fi
+$(addsuffix .dvi,$(TEXS) $(SLIDES)): %.dvi: %.tex
+	$(LATEX) $^
 
-clean:
-	rm -f *.{aux,log,nav,out,snm}
-
-distclean: clean
-	rm -f $(DVIs) $(PDFs) *.{dvi}
 
 
-twice: distclean $(DVIs) .rmdvi $(PDFs)
-.rmdvi:
-	rm -f $(DVIs)
+cleansuffix = aux log nav out snm vrb toc ps dvi
+comma:= ,
+empty:=
+space:= $(empty) $(empty)
+clean:
+	rm -f {$(subst $(space),$(comma),$(SLIDES)),$(subst $(space),$(comma),$(TEXS))}.{$(subst $(space),$(comma),$(cleansuffix))}
+distclean: clean
+	rm -f $(addsuffix .pdf,$(TEXS)) $(addsuffix .pdf,$(SLIDES)) \
+	      $(addsuffix .dvi,$(TEXS)) $(addsuffix .dvi,$(SLIDES))
 
 
+twice: all
+#twice: distclean $(DVIs) .rmdvi $(PDFs)
+#.rmdvi:
+	#rm -f $(DVIs)
+
+
diff -r e35e566b9983 -r 448fb638bfa0 slide.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/slide.tex	Tue Jul 01 16:51:39 2008 +0900
@@ -0,0 +1,389 @@
+%        File: slide.tex
+%     Created: 火  6 24 12:51 PM 2008 J
+% Last Change: 火  6 24 12:51 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]{組み込み向け低レベル言語 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 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{frame}
+
+\begin{frame}
+  \frametitle{GCCによるCbCコンパイラの実装}
+  \begin{exampleblock}{Why is it needed?}
+    \begin{itemize}
+      \item 十数種のアーキテクチャへの対応が可能
+      \item 構文木、RTLレベルでの高度な最適化
+      \item
+      \item Tailcallを使った実装方法が示されている
+    \end{itemize}
+  \end{exampleblock}
+\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
+    a%\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}
+    a%\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}
+  a%\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}
+  \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{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{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}
+  \frametitle{実装における問題}
+\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}{Conclusion}
+    \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}
+
+
+%\begin{thebibliography}
+  %\item[CbC]{} 河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
+%\end{thebibliography}
+%継続を持つCの下位言語によるシステム記述
+%河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
+%継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
+
+\appendix
+\begin{frame}
+  a%\includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
+\end{frame}
+
+\end{document}
+
+
+
+