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

comparison Paper/nobu-prosym.tex~ @ 9:de1193768ef9

modify

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Sat, 19 Nov 2011 18:03:15 +0900
parents	5dfa978ee319
children	3d1f778dc358

comparison

equal deleted inserted replaced

-:3d1135b3519c
+:de1193768ef9
 \documentclass[private]{ipsjpapers}
 %\documentstyle{ipsjpapers}
 \usepackage[dvipdfmx]{graphicx}
 \usepackage{url}
+\usepackage{multirow}  %% tabularの上下の結合
+\usepackage{slashbox}  %% tabularでの斜め線
+\usepackage{listings}
 % 巻数，号数などの設定
 %\setcounter{巻数}{41}
 %\setcounter{号数}{6}
 %\setcounter{volpageoffset}{1234}
 関数と同じように引数を持たせて継続させることもできる.
 しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
 与えられた数 x の階上を計算して出力するプログラムとなっている.
-\begin{figure}[htpb]
+\begin{figure}
-\begin{center}
+\lstinputlisting[language=c]{source/factorial.cbc}
-\scalebox{0.40}{\includegraphics{figure/factorial.eps}}
+\caption{階上を計算する CbC プログラムの例}
-\end{center}
-\caption{階上を計算する CbC プログラムの例}
-\label{fig:factorial}
 \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}
 CbC の実装では特に修正は加えていない.
 \subsubsection{Register Transfer Language (RTL)}
 構文木 GIMPLE は解析が行われた後 RTL へと変換される.
-RTL での表現は低レベルで,アセンブラとほぼ同じ表現を行うことができる.
+RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
+プログラム内部では RTL も木構造で表される.
 CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる.
 \section{GCC-4.6 への実装}
 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
 ここからは GCC-4.6 への実装について述べていく.
-\subsection{“__code” のパース}
+\subsection{“\_\_code” のパース}
 \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}}
 \end{figure}
 funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.
 \subsubsection{expand\_call}
-ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数によって判断される.
+ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
-Tail call Elimination が行える場合 try\_tail_call
+expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
-expand\_call 関数の中で try_tail_call というフラグ
+\begin{itemize}
+\item caller 側と callee 側の返す値の型が一致している.
+\item 関数呼び出しがリターンの直前に行われている.
+\item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
+\item[]
+\end{itemize}
+CbC の実装では上記の条件を,以下の様にして解決させている.
+\begin{itemize}
+\item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.
+\item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.
+\item スタックサイズは決め打ちで行う.
+\item[]
+\end{itemize}
+スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
+これも 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がセットされる.
+expand\_call 関数の中で try\_tail\_call フラグ
 \subsection{引数渡し}
 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る.
 \subsubsection{fastcall}
 コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
 C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
 だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
 そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである.
-\begin{figure}[htpb]
+%\lstinputlisting[language=c]{source/fastcall.c}
-\begin{center}
-\scalebox{0.35}{\includegraphics{figure/fastcall.eps}}
+\begin{figure}[htpb]
-\end{center}
+\begin{center}
-\caption{fastcall属性付与}
+\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
+\end{center}
+\caption{コードセグメントへのfastcall属性付与}
 \label{fig:fastcall}
 \end{figure}
-if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である.
+if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ,
+fastcall 属性を付けると warning を出すからである.
-\begin{thebibliography}{10}
+\section{評価}
+今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
+Micro-C コンパイラとそれぞれ比較を行った.
+比較を行うのはクイックソートのプログラムである.
+クイックソートは再帰的にプログラムされる為 CbC に向いている
+プログラムだと言える.
+比較を行うのは以下のアーキテクチャと OS になる.
+%\begin{description}
+\begin{itemize}
+\item x86/Linux
+\item x86/OS X
+\end{itemize}
+%\end{description}
+また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
+速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
+それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.
+表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
+表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.
+\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     & 7.378 & 0.829 & 2.890 \\ \hline
+x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
+x86\_64/OS X      & 4.078 & 0.450 &        \\ \hline
+\end{tabular}
+\caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)}
+\label{tab:speed-mc-vs-gcc-nonopt}
+\end{table}
+\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 & 2.906 & 2.890 \\ \hline
+x86\_64/OS X(-m32)& 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}{7}
 \bibitem{1}{河野真治}:
 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
 \bibitem{2}{河野真治}:
 “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000
 \bibitem{3}{与儀健人,河野真治}:
 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008

Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex~ @ 9:de1193768ef9