Mercurial > hg > Papers > 2010 > kent-master
view implementation.tex @ 2:50e23a4b2f40
add many files.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 05 Feb 2010 10:00:05 +0900 |
parents | |
children | d2999e94b97d |
line wrap: on
line source
\chapter{GCCにおける実装・改善} \label{chp:impl} 前章で洗い出したGCCでの問題点の改善を行う。 実装にはGCCのフロントエンドであるcc1というプログラムを直接変更する。 過去の研究においてはGCCのバージョン4.2.3が用いられた。現在はGCCのリリ ースに並ぶ形で4.4.2(2010年1月時)を用いている。 \section{過去の研究における実装部分} 今回の実装においての予備知識として、過去の研究での実装部分であるコード セグメントと軽量継続がどのように実装されたかを簡単に説明する。 \subsection{コードセグメントの実装} コードセグメント内部の実装は実際は単なる関数で良い。 変更の必要があったのは関数の返り値に当たる部分である。コードセグメント では返り値が存在しないのでここは``code''キーワードを入力できるようにす る。このcodeは内部でvoid型に変換する。 GCC(及び一般的なコンパイラ)ではコンパイルに必要な全ての要素、変数や式 、関数、構文などをすべて treeと呼ばれる構文木に保持している。コードセ グメントの構文木も関数とほ ぼ同じものを作成すれば良い。コード\ref{code:build-code-segment}はその 構文木を作成している部分である。 \lstinputlisting [caption=構文木生成(gcc/c-typeck.c),label=code:build-code-segment] {sources/build-code-segment.cbc} \verb|build_code_segment_type|関数においてコードセグメントの構文木を作 成している。内部の処理は\verb|build_function_type|とほぼ同じだが、関数 のテーブルに登録せず、軽量継続の際にそれがコードセグメントであることを 示すためのフラグをセットしている。 \subsection{軽量継続の実装} \label{ssec:impl-goto} % return somesegment(); % expand_call() 軽量継続はGCCの末尾呼び出し最適化の機構を用いて実装する。 \subsubsection{末尾呼び出し最適化} プログラム中、関数を呼び出すときには通常はスタックを積み上げ、現在の環 境を保持した上で呼び出し先の処理を行う。これは元の関数に復帰して残りの 処理を続行する必要があるためである。しかし関数の最後、リターン直前に呼 び出しを行う場合は環境を保持する必要がない(図\ref{fig:tailcall}参照) 。そのためスタックの状態を変更することなく呼び出すことができる。この最 適化は末尾呼び出し最適化(tailcall)と呼ばれている。 \begin{figure}[htpb] \begin{center} \includegraphics[width=.6\textwidth]{figures/tailcall.eps} \end{center} \caption{末尾呼び出し最適化が可能な関数funcBの例} \label{fig:tailcall} \end{figure} Scheme処理系では仕様上この最適化が必須となっているが、Cはそうではない。 しかしGCCはこの最適化をデフォルトで行っている。 \subsubsection{軽量継続への摘要} tailcallをコードセグメントの呼び出しに適用することで軽量継続が実装でき る。具体的にはソースコード上にコード\ref{code:goto}のような式があった 場合に、これをコード\ref{code:ret-call}と同じように解釈すれば良い。 この構文解析はGCCのgcc/c-parser.c内で行う。 \begin{minipage}[t]{.45\textwidth} \lstinputlisting[caption=goto文の例,label=code:goto] {sources/goto-expression.cbc} \end{minipage} \hfill \begin{minipage}[t]{.45\textwidth} \lstinputlisting[caption=構文木での解釈,label=code:ret-call] {sources/ret-call.cbc} \end{minipage} しかし構文木の変更だけでは最適化が行われるとは限らない。特にスタックの 状態や変数の数、順番によっても最適化はカットされる場合がある。 そのため最適化を判断する条件式を修正、また構文木から中間コードを生 成する部分でも修正が必要になる。 \paragraph{expand-call}関数は関数を表す構文木から中間コードを生成する 処理である。この関数内では呼び出される関数のアドレスを取得するコードの 生成、スタックへの引数をプッシュするコードの生成、引数のプッシュの度に tailcallが可能かのチェックなどが行われている。 ここでは以下の処理を追加することでtailcallカットの条件判断をパスしている。 \begin{itemize} \item スタックのサイズをごまかす tailcallは呼び出し元の全引数サイズが呼び出し先のそれより小さい場合 には実行できない。そのため呼び出し元、この場合コードセグメント全て の引数にもちいるスタックサイズを大きな値でごまかす。 \item 並列代入 \ref{sec:cbc-problem}で説明したような並列代入の必要な関数呼び出し を行った場合はtailcallは実行されない。そのためここで並列代入が必要 になる。 \end{itemize} 上記処理の追加により軽量継続が実装された。 継続の際にコードセグメントに渡す引数は関数と同じようにスタック上に格納 されるが、このスタックは拡張することはなく、図 \ref{fig:gotostack}のように連続した継続の中でスタックポインタは常 に同じアドレスを指し示す。(比較のため、図\ref{fig:funcstack}には関数 呼び出しの際のスタックの状態を例示した) \begin{figure}[htpb] \begin{center} \subfloat[][関数呼び出し]{\label{fig:funcstack} \includegraphics[width=.6\textwidth]{figures/functionstack.eps}} \subfloat[][軽量継続]{\label{fig:gotostack} \includegraphics[width=.6\textwidth]{figures/interfacestack.eps}} \end{center} \caption{継続制御と関数呼び出しでのスタックの違い} \end{figure} しかし並列代入の処理は構造体のようにオーバラップする引数に対しては対応 しておらず、プログラムによっては引数がちゃんと渡されないなどのバグが生 じていた。 \section{問題点の改善} ここから\ref{sec:cbc-problem}節で紹介した問題点について、本研究での改 善点を説明する。 \subsection{並列代入}\label{sec:impl-parallel} % 一時変数を取得する例を示す % 最適化の期待 % おい、replace_arguments関数、あんまり意味ないぞ \ref{sec:}のコード\ref{code:}で説明した様に、コードセグメントの受け取 った引数と継続の際に渡す引数の順序が変わる場合等に並列代入が必要になる。 過去の実装ではこの並列代入を、\verb|expand_call|という構文木から中間コ ードを生成する処理の部分で行っていた。 しかし実際にはGCCは元より並列代入を実装しているため、独自の実装は必要 としない。また、この独自の実装にも問題があった。 そのため独自の実装は廃止し、GCCの機能を利用することにする。 コード\ref{code:parallel-example2}は並列代入の必要な軽量継続の例である。 \lstinputlisting [caption=並列代入の必要な軽量継続の例,label=code:parallel-example2] {sources/parallel-example.cbc} 継続の引数は現在の引数と同じメモリに格納されるため、引数\verb|a|は \verb|b|の位置に、引数\verb|b|は\verb|a|の位置に代入されることになる。 この場合に並列代入を考慮せず、順に代入すると \begin{verbatim} a = b; b = a; \end{verbatim} となり、両方が同じ値になってしまう。 ただしこの例は極端に簡略化した例であり、この程度であればtailcallに問題 はない。しかしより複雑な並列代入では同じ問題が現れる。特に、引数に含ま れるコードセグメントポインタへ間接継続する場合には、ほぼ確実に失敗する。 この問題の回避策として単純にコード\ref{code:avoiding-parallel}の様に変 数の値を一時変数に退避することが考えられる。 \lstinputlisting [caption=引数の退避,label=code:avoiding-parallel] {sources/avoiding-parallel.cbc} こうすることで引数が一時変数に確保され、その後そこからコピーする形で所 定のメモリ位置に戻されるため問題が回避できる。今回の並列代入の改善では この手法を用いる。 \subsubsection{問題点と最適化の期待} この手法でどのように引数を入れ替えても正しく代入可能になる。ただし、一 時変数の使用は処理速度に問題がある。特にレジスタの少ないアーキテクチャ では一時変数の確保にはメモリ上のスタックを用いるため、余計なメモリアク セスや冗長な命令が増えてしまう。このため、この手法を実践したコードでは そうでないコードに比べて若干の速度低下が見込まれる。 その代わり、この速度低下はGCCのもつ最適化機構で回避され得るものである。 GCCでは中間コード生成後、必要のない一時変数へのコピーなどは最適化によ りカットされる。そのため、最適化を有効にした場合はこの処理速度の低下は 起きないはずである。この影響に関しては\ref{chp:eval}章にて評価を行う。 \subsubsection{一時変数への退避の実装} この手法の実装は、中間コード生成時ではなく構文木生成で可能である。 tailcallの関数呼び出しを表す構文木の生成時に以下の処理を追加する。 \begin{enumerate} \item 関数呼び出しを表す構文木\verb|a|の取得 \item \verb|a|から引数を表す構文木を取得、それぞれについて \begin{enumerate} \item 同じ型の名前なし一時変数を作成 \item 引数の値を一時変数に代入 \item 関数に渡す引数を一時変数に変更 \end{enumerate} \item 呼び出す関数がポインタだった場合 \item 関数と同じ型(関数ポインタ)の一時変数を作成 \item 関数アドレスを一時変数に代入 \item 呼び出す関数を一時変数に変更 \end{enumerate} ここでは関数ポインタも引数と同じように扱い、一時変数に退避する。 実際のプログラムはコード\ref{code:replace-args}の様になる。 この関数\verb|cbc_replace_arguments|は関数呼び出し構文木を引数として受 け取り、上記の処理を行う。tree callがその構文木である。 \verb|build_decl|は名無し一時変数の宣言、 \verb|build_modify_expr|は一 時変数への代入を行う構文木の生成をしている。 \lstinputlisting [caption=上記の処理を行う関数,label=code:replace-args] {sources/replace-args.c} これによりソースコードの構文解析時、軽量継続をパースしてその構文木を生 成した際にこの関数\verb|cbc_replace_arguments|を実行することで、この軽 量継続は並列代入に対応できるようになった。 この影響による速度変化の評価は\ref{sec:compare2old}節で行う。 \subsection{環境付き継続} 環境付き継続は過去の研究では実装されていなかった。 これはCとの互換性のために必要な制御構造である。 環境付き継続には\ref{ssec:gotowithenv}で述べたように、\verb|__return| という擬似変数を使う。この変数の値を継続先のコードセグメントに渡すこと で、そのコードセグメントから関数の環境へ復帰することを可能にする。 渡された\verb|__return|の値は、コードセグメント側からは他のコードセグ メントと識別できる必要はない。 この環境付き継続にもちいる\verb|_ _return|擬似変数の実装には様々な方法 が考えられるが、今回の実装には内部関数をもちいることにした。内部関数は GCCによるCの拡張機能である \cite{bib:nestedfunc}。 \subsubsection{GCCにより追加されるコード} 環境付き継続で使う\verb|__return|変数は特殊なコードセグメントへのポイ ンタとなる必要がある。このコードセグメントはユーザでは定義せず、その変 数を参照した関数の返り値型を基にコンパイラが自動で生成する事が望ましい。 具体的には、コード\ref{code:cbcreturn}の関数funcBをコンパイラは次のコ ード\ref{code:nestedcode}の様に解釈し、内部コードセグメントを自動生成 する。 \lstinputlisting [caption=コード\ref{code:cbcreturn}のfuncBに追加される処理, label=code:nestedcode,numbers=left] {sources/nestedcode.cbc} 5--14行がGCCにより追加される処理である。内部コードセグメント \verb|__unnamed_code|は受け取った引数を関数の返り値として保持し、ラベ ル\verb|__unnamed_label|にjumpする。この時点で内部コードセグメントを抜 けて元の関数funcBの環境に復帰する。 さらにjump先もGCCにより自動で追加される。しかしこのjump先は \verb|__unnamd_code|以外からは実行してはならない。そのため条件式が真に ならないif文で囲み、実行を回避している。 jump先での処理は、\verb|__unnamed_code|内で代入された値を持ってリター ンするのみである。 \subsubsection{内部コードセグメント自動生成の実装方法} GCCは変数や関数、また文字列や数値などのリテラルに関する処理を \verb|c_parser_postfix_expression|で行っている。この関数では変数や数値 、文字列などの判定に500行にわたるswitch文を使っているが、ここに \verb|__return|の判定も追加する。 必要な処理は以下の様になる。 \begin{itemize} \item ラベル\verb|_ _unnamed_label|の宣言 \item 返り値を保持しておく変数の宣言 \item 内部関数の定義 \item 条件分岐制御の構文木生成 \item 条件分岐内でのラベルの定義 \item 条件分岐内での復帰構文の構文木生成 \end{itemize} 参考のため付録にコード\ref{code:nestedcode}を用意した。 %コード\ref{code:nestedcode}にその処理を示す。 %\lstinputlisting % [caption=c\_parser\_postfix\_expressionでの処理, % label=code:nestedcode] % {sources/c_parser_postfix_expression.c} %ここで使われている関数\verb|cbc_define_nested_code|, %\verb|cbc_define_if_closed_goto |もこの処理のために作成したものである %が割愛する。処理内容は GCCが通常行う関数やif文の構文木生成とほぼ同じで %ある。 以上でコード\ref{code:nestedcode}に示すような処理がコンパイル時に自動 で追加され、環境付き継続の使用が可能になった。 \subsubsection{関数からの継続} ここで関数内から継続を行ったときの弊害がでてくる。 \ref{ssec:impl-goto}節の実装では関数からの継続は考慮していない。通常の 継続の際は現コードセグメントのもつ引数は保持しないため、直接継続しよう とすると、その関数やその関数を呼び出した関数の持つ環境(スタック)を破 壊してしまう(\pageref{fig:interfacestack} ページ、図\ref{fig:interfacestack})。 この問題を回避するため、関数からの継続に限り、スタックを拡張し関数の環 境を保持する手法をとった。 この動作は本来の軽量継続の概念とは相容れないものだが、Cとの互換性維持 のために必要である。また、CbC部分での軽量継続ではいずれもスタックは定 常なので、CbC の目的である検証、状態遷移記述などの問題にはならない。 \subsection{PowerPCにおける間接継続}\label{sec:impl-indirect} 軽量継続の実装にtailcallを用いたことは\ref{sec:}で説明した。しかし、実 際にはtailcallが行われないアーキテクチャがいくつか存在する。 PowerPCも その一つで、このアーキテクチャでは間接呼び出しの場合は tailcallが行わ れない。このためこれまでPowerPCでの間接継続はコンパイルエラーで実行で きなかった。 \subsubsection{RTLとMachine Description} GCCは構文木からRTLと呼ばれる中間コードを生成する。この中間コードは一部 を除いてアーキテクチャ依存性はなく、どのアーキテクチャでもほぼ同じにな る。さらに、最終的にこのRTLはアーキテクチャ毎に異なる規則でアセンブラ に変換される。この規則を定義するのがMachine Description(以下md)であ る。 RTL、およびmdはどちらもS式で表現されている。 GCCは自身のビルドの際、S式をパースするプログラムを作成し、そのプログラ ムはmdを基にアーキテクチャ毎に異なるCのソースコードを出力する。このソ ースコードがコンパイルされてGCCの一部となる。 RTLの例としてこの問題となっている間接継続を表すS式をコード \ref{code:rtl-example}に示す。 \lstinputlisting [caption=PowerPCにおける間接継続のRTL, label=code:rtl-example, language=Lisp] {sources/rtl-example.rtl} % TODO: RTLの説明も入れるか? \subsubsection{間接継続のmd} mdにはこのRTLをアセンブラに変換するための情報を定義する。 定義すべき情報は以下の4つである。 \begin{itemize} \item 規則の名前 \item 変換するRTL \item 変換する条件 \item 出力するアセンブラを返すCの構文 \end{itemize} 同じくmdの例として、この問題となったRTL用の変換規則を定義したものをコ ード\ref{code:md-example}に示す。 \lstinputlisting [caption=\ref{code:rtl-example}の変換規則, label=code:md-example, language=Lisp] {sources/md-example.md} ここでは出力するアセンブラとして\verb|b%T0|が使われている。 \verb|%T0|はレジスタ名に置き換えられる部分である。このアセンブラは最終 的には\verb|bctr|と置き換えられてPowerPCのアセンブラとして出力される。 %間接でない、通常の継続ではこれが\verb|bl%T0|となっているので対照的であ %る。コード\ref{code:md-example}は実際に通常の継続用のmd修正して作られ %た。 \subsection{x86における引数渡し}\label{sec:impl-fastcall} コードセグメントの間の軽量継続は、Cの関数呼び出しと同じように引数を渡 すことができる。関数呼び出しでのこの引数の渡し型はほとんどの場合アーキ テクチャやオペレーティングシステム、また各プログラミング言語毎に違った 規約があり、これは一般に呼出規約(Calling convention)と呼ばれている。 CbCでは同じアーキテクチャでもコンパイラによってこの呼出規約は違う。mc の軽量継続では、なるべく多くの引数をレジスタに格納するようになっており 、 PowerPCでは最大11個のint型をレジスタに格納する。レジスタの少ない x86でも2つだけだがやはりレジスタを使用している。 GCCベースコンパイラでは継続制御の引数渡しに関数の呼出規約と同じ方法を 使っている。そのため、x86では引数渡しに全てスタックを用いることになり 、mcに比べて速度低下がみられた。 引数渡しにレジスタを使用できるようにすることでこの問題を解決したい。 \subsubsection{fastcall} そもそも引数渡しがスタックだけだということは、CbCだけでなくCにおいても 速度面で問題をはらんでいる。そのためGCCではもとより、x86でのレジスタ渡 しを可能にする拡張機能を実装している。それがfastcallである。 このfastcallも使用するレジスタ数は2つだけではあるが、継続制御でもこれ を使うことにより高速化が図れるはずである。 \subsubsection{コードセグメントを全てfastcallに} 通常、GCCの拡張機能を用いて関数をfastcallにするにはコード \ref{code:fastcall-example}の様に ``attribute''キーワードを関数宣言の 後ろに記述する。 \begin{minipage}[t]{.7\textwidth} \lstinputlisting [caption=fastcallな関数funcBを呼び出す例,label=code:fastcall-example] {sources/fastcall-example.c} \end{minipage} しかし全てのコードセグメントに対してこの属性を宣言するのは現実的でなく 、mcとのソースコードレベルの整合性もとれない。そこでGCCではコードセグ メントの解析時に全てfastcall属性を付加することにする。 具体的には「型」の構文解析の際、キーワード``code''で関数の型が宣言され ている場合に、属性値を表す構文木を付加する。 \verb|c_parser_declspecs|関数が「型」に関する構文解析部である。 この関数内の型名キーワードを処理するswitch文内で、``code''のみ fastcall属性を付加する。 コード\ref{code:declspecs}がその処理である。このコードの12--14行目が fastcall属性付加の処理になる。それ以外の行は voidやintなど他の型の処理 と変わらない。 \lstinputlisting [caption=c\_parser\_declspecsにおけるキーワード``code''の処理, label=code:declspecs] {sources/declspecs.c} この処理で全てのコードセグメントがfastcall対応となり、軽量継続の際には レジスタ\verb|ecx,edx|に引数をのせることが可能となる。 \subsection{プロトタイプ自動生成} Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。 しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記 述という性質上、プログラムを記述する際は上から下に実行順にコードセ グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大 な数になる。 また、mcベースコンパイラの方ではプロトタイプ宣言を減らすため、一種の簡 単な型推論を実装している。そのためこれまでに作られたCbCのプログラムで は特殊な場合を除いてプロトタイプ宣言がほとんどなく、GCCでコンパイルす る際に問題となる。 この問題に暫定的に対処するため、Pythonを用いてプロトタイプの自動生成を 行うスクリプトを作成した。このスクリプトでは関数の定義部を正規表現で検 索し、マッチする部分を変換して関数宣言として出力する。 全コードは付録\ref{apx:}に掲載する。 % TODO: prototype declaration