Papers/2011/nobu-prosym: Paper/nobu-prosym.tex comparison

comparison Paper/nobu-prosym.tex @ 5:c0b91a1c738e

modify tex

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Fri, 18 Nov 2011 17:45:21 +0900
parents	5dfa978ee319
children	ea43a580129b

comparison

equal deleted inserted replaced

-:9adf0d4a6033
+:c0b91a1c738e
 関数と同じように引数を持たせて継続させることもできる.
 しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
 与えられた数 x の階上を計算して出力するプログラムとなっている.
+\begin{figure}
 \lstinputlisting[language=c]{source/factorial.cbc}
+\caption{階上を計算する CbC プログラムの例}
+\end{figure}
 %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
 %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
 \subsection{3つの内部表現}
 GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
 それぞれが
 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
 最後にアセンブラ言語へと出力される.
-図\ref{fig:ir}は
+図\ref{fig:ir}はアセンブラ出力までの流れを表した図である.
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.35}{\includegraphics{figure/ir.eps}}
 \end{center}
 \subsection{Tail Call Elimination}
 CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
 Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
 call ではなく jmp を用いることができるという最適化である.
-図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
+図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.50}{\includegraphics{figure/continuation.eps}}
 funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.
 \subsubsection{expand\_call}
 ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
-Tail Call Elimination が行える条件は以下のようになる.
+expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
 \begin{description}
-\item[caller側とcallee側の型の一致]
+\item[caller 側と callee 側の返す値の型が一致している.]
-\item[]
+\item[関数呼び出しがリターンの直前に行われている.]
-\item[]
+\item[呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.]
+\item[]
 \end{description}
+CbC の実装では上記の条件を,以下の様にして解決させている.
+\begin{description}
+\item[呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.]
+\item[コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.]
+\item[スタックサイズは決め打ちで行う.]
+\item[]
+\end{description}
+スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
+これも CbC の1つの特徴である.
+図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.33}{\includegraphics{figure/cs_stack.eps}}
+\end{center}
+\caption{継続による引数のスタック格納の様子}
+\label{fig:cs_stack}
+\end{figure}
 %expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
 %Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.
 プログラムだと言える.
 比較を行うのは以下のアーキテクチャと OS になる.
 \begin{description}
 \item[x86/Linux]
-\item[x86/OS]
+\item[x86/OS X]
-\item[x86/OS X(64bit 動作)]
 \end{description}
 また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
-速度最適化(-O2 -fomit-frame-pointer)を行うものの2つを用意する.
+速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
+それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.
 表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
 表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.
 \begin{table}[htpb]
 \begin{table}[htpb]
 \centering
 \small
 \begin{tabular}{|c|c|c|c|} \hline
 CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
-x86/Linux     & 3.252 & 1.768 & 2.890 \\ \hline
+x86/Linux     & 3.252 & 2.906 & 2.890 \\ \hline
 x86\_64(m32)/OS X& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
 \end{tabular}
 \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)}
 \label{tab:speed-mc-vs-gcc-opt}
 \end{table}
-\begin{thebibliography}{10}
+\begin{thebibliography}{7}
 \bibitem{1}{河野真治}:
 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002

Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 5:c0b91a1c738e