Mercurial > hg > Papers > 2010 > kent-master
diff 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 |
line wrap: on
line diff
--- a/implementation.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/implementation.tex Fri Feb 12 13:10:57 2010 +0900 @@ -1,8 +1,8 @@ \chapter{GCCにおける実装・改善} \label{chp:impl} -この章では、GCCにおけるCbCコンパイラの実装方法と、 \ref{chp:cbc}章で洗 -い出したGCCでの問題点の改善を行う。 +この章では、GCCにおけるCbCコンパイラの実装方法の説明と、 \ref{chp:cbc} +章で洗い出したGCCでの問題点の改善を行う。 実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。 このcc1はCからアセンブラへ変換を行う純粋なコンパイラとして実行されるプ @@ -53,7 +53,7 @@ \begin{center} \includegraphics[width=.6\textwidth]{figures/tailcall.eps} \end{center} - \caption{末尾呼び出し最適化が可能な関数funcBの例} + \caption{末尾呼び出し最適化が可能な関数funcYの例} \label{fig:tailcall} \end{figure} @@ -63,7 +63,10 @@ \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} @@ -76,14 +79,14 @@ {sources/ret-call.cbc} \end{minipage} -しかし構文木の変更だけでは最適化が行われるとは限らない。特にスタックの -状態や変数の数、順番によっても最適化はカットされる場合がある。 -そのため最適化を判断する条件式を修正、また構文木から中間コードを生 +しかし構文木の変更だけではtailcallが行われるとは限らない。特にスタック +の状態や変数の数、順番によっても最適化はカットされる場合がある。 +そのため最適化を判断する条件式を修正、また構文木から中間コードRTLを生 成する部分でも修正が必要になる。 -\paragraph{expand-call}関数は関数を表す構文木から中間コードを生成する -処理である。この関数内では呼び出される関数のアドレスを取得するコードの -生成、スタックへの引数をプッシュするコードの生成、引数のプッシュの度に +\paragraph{expand-call}関数は関数を表す構文木からRTLを生成する処理であ +る。この関数内では呼び出される関数のアドレスを取得するコードの生成、ス +タックへの引数をプッシュするコードの生成、引数のプッシュの度に tailcallが可能かのチェックなどが行われている。 ここでは以下の処理を追加することでtailcallカットの条件判断をパスしている。 @@ -127,14 +130,11 @@ \subsection{並列代入}\label{sec:impl-parallel} -% 一時変数を取得する例を示す -% 最適化の期待 -% おい、replace_arguments関数、あんまり意味ないぞ \ref{sec:gcc-problems}節で説明した様に、コードセグメントの受け取 った引数と継続の際に渡す引数の順序が変わる場合等に並列代入が必要になる。 -過去の実装ではこの並列代入を、\verb|expand_call|という構文木から中間コ -ードを生成する処理の部分で行っていた。 +過去の実装ではこの並列代入を、\verb|expand_call|という構文木から RTLを +生成する処理の部分で行っていた。 しかし実際にはGCCは元より並列代入を実装しているため、独自の実装は必要 としない。また、この独自の実装にも問題があった。 @@ -171,14 +171,14 @@ \subsubsection{問題点と最適化の期待} この手法でどのように引数を入れ替えても正しく代入可能になる。ただし、一 時変数の使用は処理速度に問題がある。特にレジスタの少ないアーキテクチャ -では一時変数の確保にはメモリ上のスタックを用いるため、余計なメモリアク -セスや冗長な命令が増えてしまう。このため、この手法を実践したコードでは -そうでないコードに比べて若干の速度低下が見込まれる。 +では一時変数の確保にメモリ上のスタックを用いるため、余計なメモリアクセ +スや冗長な命令が増えてしまう。このため、この手法を実践したコードではそ +うでないコードに比べて若干の速度低下が見込まれる。 その代わり、この速度低下はGCCのもつ最適化機構で回避され得るものである。 GCCでは中間コード生成後、必要のない一時変数へのコピーなどは最適化によ りカットされる。そのため、最適化を有効にした場合はこの処理速度の低下は -起きないはずである。この影響に関しては\ref{chp:eval}章にて評価を行う。 +起きないと考えられる。この影響に関しては\ref{chp:eval}章にて検証する。 \subsubsection{一時変数への退避の実装} @@ -193,25 +193,28 @@ \item 関数に渡す引数を一時変数に変更 \end{enumerate} \item 呼び出す関数がポインタだった場合 - \item 関数と同じ型(関数ポインタ)の一時変数を作成 - \item 関数アドレスを一時変数に代入 - \item 呼び出す関数を一時変数に変更 + \begin{enumerate} + \item 関数と同じ型(関数ポインタ)の一時変数を作成 + \item 関数アドレスを一時変数に代入 + \item 呼び出す関数を一時変数に変更 + \end{enumerate} \end{enumerate} ここでは関数ポインタも引数と同じように扱い、一時変数に退避する。 実際のプログラムはコード\ref{code:replace-args}の様になる。 この関数\verb|cbc_replace_arguments|は関数呼び出し構文木を引数として受 -け取り、上記の処理を行う。tree callがその構文木である。 -\verb|build_decl|は名無し一時変数の宣言、 \verb|build_modify_expr|は一 -時変数への代入を行う構文木の生成をしている。 +け取り、上記の処理を行う。引数として渡される\verb|tree call|がその構文 +木である。 \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{環境付き継続} @@ -234,44 +237,58 @@ ンタとなる必要がある。このコードセグメントはユーザでは定義せず、その変 数を参照した関数の返り値型を基にコンパイラが自動で生成する事が望ましい。 -具体的には、コード\ref{code:cbcreturn}の関数funcBをコンパイラは次のコ -ード\ref{code:nestedcode}の様に解釈し、内部コードセグメントを自動生成 -する。 -\lstinputlisting - [caption=コード\ref{code:cbcreturn}のfuncBに追加される処理, - label=code:nestedcode,numbers=left] - {sources/nestedcode.cbc} +具体的には、コード\ref{code:cbcreturn2}の関数funcB( +\pageref{code:cbcreturn}ページのコード\ref{code:cbcreturn}と同じ)をコ +ンパイラは次のコード\ref{code:nestedcode}の様に解釈し、内部コードセグ +メントを自動生成する。 + +\begin{minipage}[t]{.33\textwidth} + \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|__unnamed_label|にjumpする。この時点で内部コードセグメントを抜 +\verb|_segment|は受け取った引数を関数の返り値として保持し、ラベ +ル\verb|_label|にjumpする。この時点で内部コードセグメントを抜 けて元の関数funcBの環境に復帰する。 さらにjump先もGCCにより自動で追加される。しかしこのjump先は -\verb|__unnamd_code|以外からは実行してはならない。そのため条件式が真に +\verb|_segment|以外からは実行してはならない。そのため条件式が真に ならないif文で囲み、実行を回避している。 -jump先での処理は、\verb|__unnamed_code|内で代入された値を持ってリター +jump先での処理は、\verb|_segment|内で代入された値を持ってリター ンするのみである。 \subsubsection{内部コードセグメント自動生成の実装方法} -GCCは変数や関数、また文字列や数値などのリテラルに関する処理を -\verb|c_parser_postfix_expression|で行っている。この関数では変数や数値 -、文字列などの判定に500行にわたるswitch文を使っているが、ここに +GCCは変数や関数、また文字列や数値などのリテラルに関する処理を \\ +\verb|c_parser_postfix_expression|で行っている。この関数では変数や数 +値、文字列などの判定に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 @@ -331,6 +348,7 @@ 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'')|となり、コードセグメントの関数 @@ -348,7 +366,7 @@ label=code:md-for-indirect, language=Lisp] {sources/md-for-indirect.md} -このコードの2番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似 +このコードの3番目の要素はコード\ref{code:rtl-indirecttailcall}とよく似 ていることがわかる。これは変換対象としてこの型に合うものに制限するため である。 @@ -370,10 +388,10 @@ テクチャやオペレーティングシステム、また各プログラミング言語毎に違った 規約があり、これは一般に呼出規約(Calling convention)と呼ばれている。 -CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は違う。mc -の軽量継続では、なるべく多くの引数をレジスタに格納するようになっており -、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少ない -x86でも2つだけだがやはりレジスタを使用している。 +CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は異なる。 +mc の軽量継続では、なるべく多くの引数をレジスタに格納するようになって +おり、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少な +い x86でも2つだけだが、やはりレジスタを使用している。 GCCベースコンパイラでは継続制御の引数渡しに関数の呼出規約と同じ方法を 使っている。そのため、x86では引数渡しに全てスタックを用いることになり @@ -395,11 +413,9 @@ \ref{code:fastcall-example}の様に ``attribute''キーワードを関数宣言の 後ろに記述する。 -\begin{minipage}[t]{.7\textwidth} \lstinputlisting - [caption=fastcallな関数funcBを呼び出す例,label=code:fastcall-example] + [caption=fastcallな関数fastfuncを宣言する例,label=code:fastcall-example] {sources/fastcall-example.c} -\end{minipage} しかし全てのコードセグメントに対してこの属性を宣言するのは現実的でなく 、mcとのソースコードレベルの整合性もとれない。そこでGCCではコードセグ @@ -443,6 +459,4 @@ このプトロタイプ自動生成により、これまでに作られたCbCのプログラムとの 互換性が確保できた。 -% TODO: prototype declaration -