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

comparison Paper/nobu-prosym.tex @ 19:e89540b527cf

modify

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Sun, 20 Nov 2011 08:03:08 +0900
parents	8ea8be1671d0
children	9e904a731cf4

comparison

equal deleted inserted replaced

-:085054e84bc5
+:e89540b527cf
 \subsubsection{expand\_call}
 ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
 \verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
-\begin{itemize}
+%\begin{itemize}
+\begin{enumerate}
 \item caller 側と callee 側の戻値の型が一致している.
 \item 関数呼び出しがリターンの直前に行われている.
 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
 \item 引数の並びのコピーに上書きがない.
-\end{itemize}
+\end{enumerate}
+%\end{itemize}
 CbC の実装では上記の条件を,以下の様にして解決させている.
-\begin{itemize}
+\begin{enumerate}
+%\begin{itemize}
 \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない.
 \item goto の直後に retrun を置く．
 \item スタックサイズは関数宣言時に決まったサイズにする．
 \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
-\end{itemize}
+%\end{itemize}
+\end{enumerate}
-スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
+1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
+2, 3 と 4 については以下で詳しく説明を行う.
+\subsubsection{継続の直後に return の配置}
+この処理は Generic Tree の生成時に組み込んである為, ユーザは return を記述する必要はない.
+例をあげると, 図\ref{fig:factorial}の factorial0 は,
+プログラム内部では図\ref{code:return}の様に処理されることになる.
+\begin{figure}[h]
+\begin{minipage}[b]{.45\textwidth}
+\begin{lstlisting}[caption=継続の直後に return を置く,label=code:return]
+__code factorial0(int prod, int x)
+{
+if ( x >= 1) {
+goto factorial0(prod*x, x-1);
+return;
+}else{
+goto print_factorial(prod);
+return;
+}
+}
+\end{lstlisting}
+\end{minipage}
+\hfill
+\end{figure}
+%goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う.
+\subsubsection{スタックサイズの固定化}
+CbC では継続によりスタックに値が積まれていくということはない為サイズを固定することができる.
+また, サイズが固定な為, スタックポインタを変えずにスタックを扱うことができる.
 これも CbC の1つの特徴である.
 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.
 \begin{figure}[htpb]
 \begin{center}
 \end{figure}
 %GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも
 %Tail Call Elimination にかからないコードセグメントがある.
 %この点を改善する必要がある.
 %\subsection{引数の一時変数への避難}
 %\subsection{スタック書き換えの問題}
 \subsection{引数の並びの上書きコピー}
 CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
 例えばlistlising\ref{code:cs_prog}のような継続である.
 \begin{figure}[h]
 \begin{minipage}[b]{.45\textwidth}
-\begin{lstlisting}[caption=,label=code:cs_prog]
+\begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
 __code cs_a(int a, int b) {
 goto cs_b(b, a)
 }
 \end{lstlisting}
 \end{minipage}
 \hfill
 \end{figure}
-この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる.
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.33}{\includegraphics{figure/cs_prog.eps}}
 \end{center}
 \caption{スタック書き換えの問題}
 \label{fig:cs_prog}
 \end{figure}
+この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる.
 数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している.
 CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している.
 \subsubsection{一時変数へのコピー}
 一時変数へのコピーは, goto が行われた時の, コードセグメントの Generic Tree 生成時に行われる.
 \item 引数と同じ型の一時変数を作成
 \item 一時変数に引数の値を代入
 \item 関数に渡す引数のポインタを一時変数に変更
 \end{itemize}
-tree call は継続を行うコードセグメントになる.
+tree call は継続を行うコードセグメントを指す.
 コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
 ところへ一時変数を入れている.
 \subsection{環境付き継続}
 CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメント間を継続することで, 速度の向上を図る.
 \subsubsection{fastcall}
 C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う.
-だが, コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
+だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない.
 そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う.
 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているコードである.
 %\lstinputlisting[language=c]{source/fastcall.c}

Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 19:e89540b527cf