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

comparison Paper/nobu-prosym.tex @ 29:d80535a49459

modify tex

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Mon, 21 Nov 2011 06:28:32 +0900
parents	9ca3eb4921d6
children	db9735be2bf1

comparison

equal deleted inserted replaced

-:9ca3eb4921d6
+:d80535a49459
 GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
 %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
 %今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
 %本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
 だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
-本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.
+本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.
 %}{
 \section{Continuation based C (CbC)}
 図\ref{fig:factorial}は CbC で書いたプログラムの例である.
 与えられた数 x の階上を計算して出力するプログラムとなっている.
 \begin{figure}
+\begin{footnotesize}
 \lstinputlisting[language=c]{source/factorial.cbc}
 \caption{階上を計算する CbC プログラムの例}
 \label{fig:factorial}
-\end{figure}
+\end{footnotesize}
+\end{figure}
-%CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
-%コードセグメントの記述の仕方は C の関数と同じだが, 型に ``\_\_code''を使って宣言を行うところだけが違う.
-%関数と同じように引数を持たせて継続させることもできる.
-%しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
-%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
-%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
 \section{GCCの3つの内部表現}
 GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.
-GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
+GCC は内部で Generic Tree, GIMPLE Tree, RTL という3つの内部表現を扱う.
 それぞれが
-読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
+読み込んだソースコードは Generic Tree, GIMPLE Tree, RTL の順に変換されていき,
 最後にアセンブラ言語へと出力される.
 図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.
 \begin{figure}[htpb]
 \begin{center}
 関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
 CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.
-\subsection{GIMPLE}
+\subsection{GIMPLE Tree}
-Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
+Generic Tree で表現されたデータは GIMPLE Tree に変換される.
-GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
+GIMPLE Tree は Generic Tree より制約がかかった状態で作成された構文木となる.
 制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
-GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
+GIMPLE Tree へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
 CbC の実装では特に修正は加えていない.
 \subsection{Register Transfer Language (RTL)}
-構文木 GIMPLE は解析が行われた後 RTL へと変換される.
+GIMPLE Tree は解析が行われた後 RTL へと変換される.
 RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
 プログラム内部では RTL も木構造で表される.
 CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.
 ここからは GCC-4.6 への実装について述べていく.
 \subsection{``\_\_code'' のパース}
 C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている.
-ここに,図\ref{fig:code-parse}のように \verb+code+ の登録を行う.
+ここに,図\ref{fig:code-parse}のように \verb+__code+ 型の登録を行う.
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
 \end{center}
 これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる.
 次に, id を用意する.
 Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される.
 そこに登録するコードセグメント判定用 id  ``\verb+cts_CbC_code+'' を用意する.
-これは gcc/c-tree.h で定義される(図\ref{fig:code-id}).
+これは gcc/c-Tree.h で定義される(図\ref{fig:code-id}).
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.35}{\includegraphics{figure/code-id.eps}}
 \end{center}
 \end{figure}
 図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている.
 違うところは \verb+cts_CbC_code+ を登録するところだけである.
-最後に, \verb+finish_declspecs+ 関数にて id 毎に tree タイプの決定をする.
+最後に, \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする.
-コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ をタイプと
+コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと
 して登録している(図\ref{fig:regi-node}).
 \begin{figure}[htpb]
 \begin{center}
 \scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
 \label{fig:rid-goto}
 \end{figure}
 %具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した.
 具体的には
-void 型の tree を元にコードセグメントと判定するフラグ と Tail Call のフラグ
+void 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ
-を付けた関数として tree の作成を行なっている.
+を付けた関数とした Tree となる.
+%の作成を行なっている.
 \verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については
 CbC においても重要になるので後に詳しく説明する.
 \subsection{Tail Call Elimination}
 \end{figure}
 funcB は jmp 命令で funcC を呼び出す.
 funcC は, 戻値を funcB ではなく funcA へと返すことになる.
 \subsubsection{expand\_call}
-ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
+\verb+expand_call+ 関数は, 関数を表す Tree から RTL を生成する関数である.
-\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
+Tail Call Elimination を行えるかどうかもこの関数で判断される.
+内部でチェックされる Tail Call Elimination の条件は以下になる.
+%\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
 %\begin{itemize}
 \begin{enumerate}
 \item caller 側と callee 側の戻値の型が一致している.
 \item 関数呼び出しがリターンの直前に行われている.
 戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう.
 最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う.
 \subsubsection{末尾最適化の強制付与}
 Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる.
-以前の GCC の初期の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_call+ 関数を作成して,
+以前の CbC-GCC の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_call+ 関数を作成して,
 条件をクリアするようにしていた.
 しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_call+ 関数にも
 変更を加える必要があり, 手間となっていた.
-そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_call+ 関数を取り除くことに成功した.
+そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_call+ 関数を取り除くことに
+成功した(図\ref{fig:tail_call}:2行目).
-\verb+expand_call+ 関数内では, Tail Call Eliminatino に書けるためのフラグ, \verb+try_tail_call+
+\begin{figure}[htpb]
+\begin{center}
+\scalebox{0.35}{\includegraphics{figure/tail_call_flag.eps}}
+\end{center}
+\caption{コードセグメントの末尾最適化の付与}
+\label{fig:tail_call}
+\end{figure}
+\verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+
 変数があり, コードセグメントはこのフラグには初め 1 がセットされている.
 コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った.
 また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った.
 これにより末尾最適化の強制付与がなされた.
 \subsubsection{goto の直後に return の配置}
 図\ref{fig:factorial}のコードセグメント factorial0 をlisting\ref{code:return}の様に, goto の直後に return を
 置く必要がある.だがそれをプログラマが記述することは実用的でない.
 \begin{figure}[h]
+\begin{footnotesize}
 \begin{minipage}[b]{.45\textwidth}
 \begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
 __code factorial0(int prod, int x)
 {
 if ( x >= 1) {
 }
 }
 \end{lstlisting}
 \end{minipage}
 \hfill
+\end{footnotesize}
 \end{figure}
 CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
 図\ref{fig:rid-goto}の\verb+c_finish_return+ 関数がそれにあたる.
 %goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う.
 これも CbC の1つの特徴である.
 図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.
 \begin{figure}[htpb]
 \begin{center}
-\scalebox{0.33}{\includegraphics{figure/cs_stack.eps}}
+\scalebox{0.30}{\includegraphics{figure/cs_stack.eps}}
 \end{center}
 \caption{継続による引数のスタック格納の様子}
 \label{fig:cs_stack}
 \end{figure}
 %\subsection{スタック書き換えの問題}
 \subsubsection{引数の並びの上書きコピー}
 CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
 例えばlistlising\ref{code:cs_prog}のような継続である.
 \begin{figure}[h]
+\begin{footnotesize}
 \begin{minipage}[b]{.45\textwidth}
 \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{footnotesize}
 \end{figure}
 \begin{figure}[htpb]
 \begin{center}
 \item 引数と同じ型の一時変数を作成
 \item 一時変数に引数の値を代入
 \item 関数に渡す引数のポインタを一時変数に変更
 \end{itemize}
-tree call は継続を行うコードセグメントを指す.
+Tree call は継続を行うコードセグメントを指す.
 コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
 ところへ一時変数を入れている.
 \subsection{環境付き継続}

Mercurial > hg > Papers > 2011 > nobu-prosym

comparison Paper/nobu-prosym.tex @ 29:d80535a49459