Papers/2010/kent-master: implementation.tex comparison

comparison implementation.tex @ 7:8ef81ff8cb52

emended.

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 13:10:57 +0900
parents	dfb89e32eea1
children	4b2af58b0302

comparison

equal deleted inserted replaced

-:b59d31966d7d
+:8ef81ff8cb52
 \chapter{GCCにおける実装・改善}
 \label{chp:impl}
-この章では、GCCにおけるCbCコンパイラの実装方法と、 \ref{chp:cbc}章で洗
+この章では、GCCにおけるCbCコンパイラの実装方法の説明と、 \ref{chp:cbc}
-い出したGCCでの問題点の改善を行う。
+章で洗い出したGCCでの問題点の改善を行う。
 実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。
 このcc1はCからアセンブラへ変換を行う純粋なコンパイラとして実行されるプ
 ログラムである。このcc1をCbCの構文解析に対応させる。
 適化は末尾呼び出し最適化(tailcall)と呼ばれている。
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[width=.6\textwidth]{figures/tailcall.eps}
 \end{center}
-\caption{末尾呼び出し最適化が可能な関数funcBの例}
+\caption{末尾呼び出し最適化が可能な関数funcYの例}
 \label{fig:tailcall}
 \end{figure}
 Scheme処理系では仕様上この最適化が必須となっているが、Cはそうではない。
 しかしGCCはこの最適化をデフォルトで行っている。
 \subsubsection{軽量継続への摘要}
 tailcallをコードセグメントの呼び出しに適用することで軽量継続が実装でき
 る。具体的にはソースコード上にコード\ref{code:goto}のような式があった
-場合に、これをコード\ref{code:ret-call}と同じように解釈すれば良い。
+場合に、これをコード\ref{code:ret-call}と同じように解釈する。
+つまり、``goto''が前置する関数呼び出しは、必ず後ろに\verb|return;|がつ
+くと解釈するのである。これでtailcallの条件ほぼ満たされる。
 この構文解析はGCCのgcc/c-parser.c内で行う。
 \begin{minipage}[t]{.45\textwidth}
 \lstinputlisting[caption=goto文の例,label=code:goto]
 {sources/goto-expression.cbc}
 \begin{minipage}[t]{.45\textwidth}
 \lstinputlisting[caption=構文木での解釈,label=code:ret-call]
 {sources/ret-call.cbc}
 \end{minipage}
-しかし構文木の変更だけでは最適化が行われるとは限らない。特にスタックの
+しかし構文木の変更だけではtailcallが行われるとは限らない。特にスタック
-状態や変数の数、順番によっても最適化はカットされる場合がある。
+の状態や変数の数、順番によっても最適化はカットされる場合がある。
-そのため最適化を判断する条件式を修正、また構文木から中間コードを生
+そのため最適化を判断する条件式を修正、また構文木から中間コードRTLを生
 成する部分でも修正が必要になる。
-\paragraph{expand-call}関数は関数を表す構文木から中間コードを生成する
+\paragraph{expand-call}関数は関数を表す構文木からRTLを生成する処理であ
-処理である。この関数内では呼び出される関数のアドレスを取得するコードの
+る。この関数内では呼び出される関数のアドレスを取得するコードの生成、ス
-生成、スタックへの引数をプッシュするコードの生成、引数のプッシュの度に
+タックへの引数をプッシュするコードの生成、引数のプッシュの度に
 tailcallが可能かのチェックなどが行われている。
 ここでは以下の処理を追加することでtailcallカットの条件判断をパスしている。
 \begin{itemize}
 \item スタックのサイズをごまかす
 ここから\ref{sec:cbc-problem}節で紹介した問題点について、本研究での改
 善点を説明する。
 \subsection{並列代入}\label{sec:impl-parallel}
-% 一時変数を取得する例を示す
-% 最適化の期待
-% おい、replace_arguments関数、あんまり意味ないぞ
 \ref{sec:gcc-problems}節で説明した様に、コードセグメントの受け取
 った引数と継続の際に渡す引数の順序が変わる場合等に並列代入が必要になる。
-過去の実装ではこの並列代入を、\verb|expand_call|という構文木から中間コ
+過去の実装ではこの並列代入を、\verb|expand_call|という構文木から RTLを
-ードを生成する処理の部分で行っていた。
+生成する処理の部分で行っていた。
 しかし実際にはGCCは元より並列代入を実装しているため、独自の実装は必要
 としない。また、この独自の実装にも問題があった。
 そのため独自の実装は廃止し、GCCの機能を利用することにする。
 この手法を用いる。
 \subsubsection{問題点と最適化の期待}
 この手法でどのように引数を入れ替えても正しく代入可能になる。ただし、一
 時変数の使用は処理速度に問題がある。特にレジスタの少ないアーキテクチャ
-では一時変数の確保にはメモリ上のスタックを用いるため、余計なメモリアク
+では一時変数の確保にメモリ上のスタックを用いるため、余計なメモリアクセ
-セスや冗長な命令が増えてしまう。このため、この手法を実践したコードでは
+スや冗長な命令が増えてしまう。このため、この手法を実践したコードではそ
-そうでないコードに比べて若干の速度低下が見込まれる。
+うでないコードに比べて若干の速度低下が見込まれる。
 その代わり、この速度低下はGCCのもつ最適化機構で回避され得るものである。
 GCCでは中間コード生成後、必要のない一時変数へのコピーなどは最適化によ
 りカットされる。そのため、最適化を有効にした場合はこの処理速度の低下は
-起きないはずである。この影響に関しては\ref{chp:eval}章にて評価を行う。
+起きないと考えられる。この影響に関しては\ref{chp:eval}章にて検証する。
 \subsubsection{一時変数への退避の実装}
 この手法の実装は、中間コード生成時ではなく構文木生成で可能である。
 tailcallの関数呼び出しを表す構文木の生成時に以下の処理を追加する。
 \item 同じ型の名前なし一時変数を作成
 \item 引数の値を一時変数に代入
 \item 関数に渡す引数を一時変数に変更
 \end{enumerate}
 \item 呼び出す関数がポインタだった場合
-\item 関数と同じ型（関数ポインタ）の一時変数を作成
+\begin{enumerate}
-\item 関数アドレスを一時変数に代入
+\item 関数と同じ型（関数ポインタ）の一時変数を作成
-\item 呼び出す関数を一時変数に変更
+\item 関数アドレスを一時変数に代入
+\item 呼び出す関数を一時変数に変更
+\end{enumerate}
 \end{enumerate}
 ここでは関数ポインタも引数と同じように扱い、一時変数に退避する。
 実際のプログラムはコード\ref{code:replace-args}の様になる。
 この関数\verb|cbc_replace_arguments|は関数呼び出し構文木を引数として受
-け取り、上記の処理を行う。tree callがその構文木である。
+け取り、上記の処理を行う。引数として渡される\verb|tree call|がその構文
-\verb|build_decl|は名無し一時変数の宣言、 \verb|build_modify_expr|は一
+木である。 \verb|build_decl|は名無し一時変数の宣言、
-時変数への代入を行う構文木の生成をしている。
+\verb|build_modify_expr|は一時変数への代入を行う構文木の生成をしている
+。
 \lstinputlisting
 [caption=上記の処理を行う関数,label=code:replace-args]
 {sources/replace-args.c}
-これによりソースコードの構文解析時、軽量継続をパースしてその構文木を生
+ソースコードの構文解析時、軽量継続をパースしてその構文木を生成した際に
-成した際にこの関数\verb|cbc_replace_arguments|を実行することで、この軽
+、この関数\verb|cbc_replace_arguments|を実行することで、この軽量継続は
-量継続は並列代入に対応できるようになった。
+並列代入に対応できるようになった。
 \subsection{環境付き継続}
 環境付き継続は過去の研究では実装されていなかった。
 \subsubsection{GCCにより追加されるコード}
 環境付き継続で使う\verb|__return|変数は特殊なコードセグメントへのポイ
 ンタとなる必要がある。このコードセグメントはユーザでは定義せず、その変
 数を参照した関数の返り値型を基にコンパイラが自動で生成する事が望ましい。
-具体的には、コード\ref{code:cbcreturn}の関数funcBをコンパイラは次のコ
+具体的には、コード\ref{code:cbcreturn2}の関数funcB（
-ード\ref{code:nestedcode}の様に解釈し、内部コードセグメントを自動生成
+\pageref{code:cbcreturn}ページのコード\ref{code:cbcreturn}と同じ）をコ
-する。
+ンパイラは次のコード\ref{code:nestedcode}の様に解釈し、内部コードセグ
-\lstinputlisting
+メントを自動生成する。
-[caption=コード\ref{code:cbcreturn}のfuncBに追加される処理,
-label=code:nestedcode,numbers=left]
+\begin{minipage}[t]{.33\textwidth}
-{sources/nestedcode.cbc}
+\lstinputlisting
+[caption=\_\_returnの例,
+label=code:cbcreturn2,
+basicstyle=\footnotesize\ttfamily,
+emph=\_\_return]
+{sources/cbcreturn2.cbc}
+\end{minipage}
+\hfill
+\begin{minipage}[t]{.55\textwidth}
+\lstinputlisting
+[caption=コード\ref{code:cbcreturn}のfuncBに追加される処理,
+label=code:nestedcode,numbers=left]
+{sources/nestedcode.cbc}
+\end{minipage}
 5--14行がGCCにより追加される処理である。内部コードセグメント
-\verb|__unnamed_code|は受け取った引数を関数の返り値として保持し、ラベ
+\verb|_segment|は受け取った引数を関数の返り値として保持し、ラベ
-ル\verb|__unnamed_label|にjumpする。この時点で内部コードセグメントを抜
+ル\verb|_label|にjumpする。この時点で内部コードセグメントを抜
 けて元の関数funcBの環境に復帰する。
 さらにjump先もGCCにより自動で追加される。しかしこのjump先は
-\verb|__unnamd_code|以外からは実行してはならない。そのため条件式が真に
+\verb|_segment|以外からは実行してはならない。そのため条件式が真に
 ならないif文で囲み、実行を回避している。
-jump先での処理は、\verb|__unnamed_code|内で代入された値を持ってリター
+jump先での処理は、\verb|_segment|内で代入された値を持ってリター
 ンするのみである。
 \subsubsection{内部コードセグメント自動生成の実装方法}
-GCCは変数や関数、また文字列や数値などのリテラルに関する処理を
+GCCは変数や関数、また文字列や数値などのリテラルに関する処理を \\
-\verb|c_parser_postfix_expression|で行っている。この関数では変数や数値
+\verb|c_parser_postfix_expression|で行っている。この関数では変数や数
-、文字列などの判定に500行にわたるswitch文を使っているが、ここに
+値、文字列などの判定に500行にわたるswitch文を使っているが、ここに
 \verb|__return|の判定も追加する。
 必要な処理は以下の様になる。
 \begin{itemize}
-\item ラベル\verb|_ _unnamed_label|の宣言
+\item ラベル\verb|_label|の宣言
 \item 返り値を保持しておく変数の宣言
 \item 内部関数の定義
 \item 条件分岐制御の構文木生成
 \item 条件分岐内でのラベルの定義
 \item 条件分岐内での復帰構文の構文木生成
 \end{itemize}
-参考のため付録にコード\ref{code:nestedcode}を用意した。
+参考のため付録\ref{apx:postfix-expression}にこの処理のコードを掲載す
+る。
 %コード\ref{code:nestedcode}にその処理を示す。
 %\lstinputlisting
 %  [caption=c\_parser\_postfix\_expressionでの処理,
 %   label=code:nestedcode]
 \lstinputlisting
 [caption=PowerPCにおける間接継続のRTL,
 label=code:rtl-indirecttailcall,
 language=Lisp]
 {sources/rtl-indirecttailcall.rtl}
 このRTL内の\verb|(mem:SI (reg/f:SI 129)|が関数のポインタを示すレジスタ
 である。間接呼び出しでない場合はこれが
 \verb|(mem:SI (symbol_ref:SI (``cs0'')|となり、コードセグメントの関数
 を直接表している。
 \lstinputlisting
 [caption=\ref{code:rtl-indirecttailcall}の変換規則,
 label=code:md-for-indirect,
 language=Lisp]
 {sources/md-for-indirect.md}
-このコードの2番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似
+このコードの3番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似
 ていることがわかる。これは変換対象としてこの型に合うものに制限するため
 である。
 ここでは出力するアセンブラとして\verb|b%T0|が使われている。
 \verb|%T0|はレジスタ名に置き換えられる部分である。このアセンブラは最終
 コードセグメントの間の軽量継続は、Cの関数呼び出しと同じように引数を渡
 すことができる。関数呼び出しでのこの引数の渡し型はほとんどの場合アーキ
 テクチャやオペレーティングシステム、また各プログラミング言語毎に違った
 規約があり、これは一般に呼出規約(Calling convention)と呼ばれている。
-CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は違う。mc
+CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は異なる。
-の軽量継続では、なるべく多くの引数をレジスタに格納するようになっており
+mc の軽量継続では、なるべく多くの引数をレジスタに格納するようになって
-、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少ない
+おり、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少な
-x86でも2つだけだがやはりレジスタを使用している。
+い x86でも2つだけだが、やはりレジスタを使用している。
 GCCベースコンパイラでは継続制御の引数渡しに関数の呼出規約と同じ方法を
 使っている。そのため、x86では引数渡しに全てスタックを用いることになり
 、mcに比べて速度低下がみられた。
 通常、GCCの拡張機能を用いて関数をfastcallにするにはコード
 \ref{code:fastcall-example}の様に ``attribute''キーワードを関数宣言の
 後ろに記述する。
-\begin{minipage}[t]{.7\textwidth}
+\lstinputlisting
-\lstinputlisting
+[caption=fastcallな関数fastfuncを宣言する例,label=code:fastcall-example]
-[caption=fastcallな関数funcBを呼び出す例,label=code:fastcall-example]
 {sources/fastcall-example.c}
-\end{minipage}
 しかし全てのコードセグメントに対してこの属性を宣言するのは現実的でなく
 、mcとのソースコードレベルの整合性もとれない。そこでGCCではコードセグ
 メントの解析時に全てfastcall属性を付加することにする。
 全コードは付録\ref{apx:make-prototype}に掲載する。
 このプトロタイプ自動生成により、これまでに作られたCbCのプログラムとの
 互換性が確保できた。
-% TODO: prototype declaration

Mercurial > hg > Papers > 2010 > kent-master

comparison implementation.tex @ 7:8ef81ff8cb52