# HG changeset patch # User kent # Date 1265947857 -32400 # Node ID 8ef81ff8cb52b5a7e871f3a9369a0f22afe71c85 # Parent b59d31966d7d3aaa6a25a2b25186ece8abbf9595 emended. diff -r b59d31966d7d -r 8ef81ff8cb52 Makefile --- a/Makefile Mon Feb 08 03:50:27 2010 +0900 +++ b/Makefile Fri Feb 12 13:10:57 2010 +0900 @@ -12,24 +12,27 @@ PS_SUFFIX=.ps PDF_SUFFIX=.pdf -.SUFFIXES: .tex .dvi .pdf +.SUFFIXES: .tex .dvi .pdf .toc default: $(TARGET).pdf .dvi.pdf: - $(DVI2PDF) $(DVIPDF_OPT) $^ + $(DVI2PDF) $(DVI2PDF_OPT) $^ .tex.dvi: - $(LATEX) $^ + $(LATEX) $< bib: dvi @echo "========== MAKE Bib file ($(MAIN_TARGET).dvi) ==========" $(BIBTEX) $(MAIN_TARGET) + +$(TARGET).dvi: abstract.tex introduction.tex cbc.tex gcc.tex implementation.tex evaluations.tex conclusion.tex thanx.tex bibliography.tex presentations.tex appendix.tex + clean: - @echo "remove $(TARGET)*{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out}" - $(RM) $(TARGET)*{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out} + @echo "remove $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out}" + $(RM) $(TARGET).{aux,log,toc,lof,lot,blg,bbl,ilg,idx,ind,dvi,ps,pdf,out} veryclean: clean find ./ -name \*~ -exec rm -f {} \; diff -r b59d31966d7d -r 8ef81ff8cb52 abstract.tex --- a/abstract.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/abstract.tex Fri Feb 12 13:10:57 2010 +0900 @@ -1,27 +1,22 @@ %% 要旨 \begin{abstract} -%%TODO - 本研究室では継続を基本としたプログラミング言語Continuation based C(CbC)を開発している。この言語はCから関数やforループ制御などを除き、同 様の動作は全て継続を用いて実現する事で、Cよりも細かい動作を可能にして いる。 - +これまでCbCのコンパイラにはmicro-cをベースとしたコンパイラを用いてきた +。また2008年の研究ではGCCにて継続制御を実装し、GCCによるCbCのコンパイ +ルが可能となった。 -これまでCbCのコンパイラにはmicro-cをベースとしたコンパイラを用いてきた -。また、2008年の研究ではGCCでのCbCコンパイルも可能となった。しかし、 -GCCは当初の期待ほどの性能は出ず、未実装の機能もあり、また実装方法の問 -題からバグの存在も明らかになった。 +本研究ではGCCベースのコンパイラに、残るCbCの機能の実装を行った。 -そこで本研究ではその問題点の洗い出しと、未実装であった機能の実装を含む -その問題点の改善を行った。 - -この改善により、GCCコンパイラはCbCの機能を完全にサポートし、さらに以前 -のバージョンよりも高速化に成功した。またこれまでmicro-cでは対応してい -なかった多数のアーキテクチャへの対応が可能となった。実測評価においては -micro-cベースのコンパイラと比較し、良好な結果を得られた。 +この改善により、GCCベースコンパイラはCbCの機能を完全にサポートし、さら +に以前のバージョンよりも高速化に成功した。加えてGCCベースにしたことに +より、これまでmicro-cでは対応していなかった多数のアーキテクチャへの対 +応が可能となった。実測評価においては micro-cベースのコンパイラと比較し +、良好な結果を得ることができた。 %%%%% diff -r b59d31966d7d -r 8ef81ff8cb52 appendix.tex --- a/appendix.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/appendix.tex Fri Feb 12 13:10:57 2010 +0900 @@ -1,5 +1,48 @@ \chapter{付録} +\section{測定環境}\label{sec:machine-specs} +\ref{chp:eval}章の性能評価ではCPUアーキテクチャとオペレーティングシス +テムの5つの組み合わせで測定を行った。ここでその5つの環境を一覧する。 + +\begin{itemize} + \item x86/OS X + \begin{description} + \item[機種] Mac mini + \item[CPU] 2.26GHz Intel Core 2 Duo + \item[メモリ] 2GB 1067MHz DDR3 + \item[OS] Mac OS X 10.6.2 + \end{description} + \item x86/Linux + \begin{description} + \item[機種] 自作 + \item[CPU] 2.4GHz Intel Core 2 Quad Q6600 + \item[メモリ] 4GB 800MHz DDR2 + \item[OS] Gentoo Linux + \end{description} + \item PPC/OS X + \begin{description} + \item[機種] Power Mac G5 + \item[CPU] 2GHz PowerPC G5 + \item[メモリ] 2GB DDR + \item[OS] Mac OS X 10.5.8 + \end{description} + \item PPC/Linux + \begin{description} + \item[機種] PowerBook 17" -1.67GHz + \item[CPU] 1.66GHz PowerPC G4 7447A + \item[メモリ] 1.5MB DDR + \item[OS] Gentoo Linux + \end{description} + \item PPC/PS3 + \begin{description} + \item[機種] PlayStation3 モデルCECHB00 + \item[CPU] Cell Broadband Engine 3.2GHz + \item[メモリ] 210MB + \item[OS] Fedora release 10 + \end{description} +\end{itemize} + + \section{\texttt{\_\_return}擬似変数の実装}\label{apx:postfix-expression} % 環境付き継続の実装、内部関数の自動追加処理 @@ -52,5 +95,3 @@ {quicksort/quicksort_test.cbc} -\section{測定環境} -% TODO diff -r b59d31966d7d -r 8ef81ff8cb52 bibliography.tex --- a/bibliography.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/bibliography.tex Fri Feb 12 13:10:57 2010 +0900 @@ -6,6 +6,18 @@ 河野真治. ``検証を自身で表現できるハードウェア、ソフトウェア記述言 語 Continuation based C と、そのCell への応用''. 電子情報通信学会VLSI設計技術研究会, March, 2008 + \bibitem{bib:kono-2006} + 河野真治, 渕田良彦, 宮國渡. + ``継続を基本とする言語 CbC による分散プログラミング''. + 日本ソフトウェア科学会第23回大会論文集, Sep, 2006 + \bibitem{bib:kono-2000} + 河野真治, 島袋仁. + ``C with Continuation と、そのPlayStationへの応用''. + 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS), May, 2000 + \bibitem{bib:kono-1998} + 河野真治, 池村正之. + ``状態集合の分割による時相論理検証の並列化''. + 電気学会・電子情報通信学会合同講演会, Dec, 1998 \bibitem{bib:kinjo-master-2005} 金城拓実. ``軽量継続を用いたゲームプログラムの分割と再構成の考察''. 琉球大学理工学研究科情報工学専攻 平成17年度学位論文, 2006. @@ -22,10 +34,6 @@ 神里晃 宮國渡, 杉山千秋, 河野真治. ``CからCellアーキテクチャを利用したCbCへの変換'' 電子情報通信学会VLSI設計技術研究会, March, 2008 - \bibitem{bib:kono-2006} - 河野真治, 渕田良彦, 宮國渡. - ``継続を基本とする言語 CbC による分散プログラミング''. - 日本ソフトウェア科学会第23回大会論文集, Sep, 2006 \bibitem{bib:kinjo-2005} 金城拓実, 河野真治. ``ゲームプログラムからの一部の仕様の抽出に関する考察''. diff -r b59d31966d7d -r 8ef81ff8cb52 cbc.tex --- a/cbc.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/cbc.tex Fri Feb 12 13:10:57 2010 +0900 @@ -2,9 +2,9 @@ \label{chp:cbc} Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも -上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを使った -研究を行っている。本章ではそのCbCの -仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。 +上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを用いた +研究を行っている。本章ではそのCbCの仕様と現在の状況について説明し、ま +たCbCを用いた研究例についても紹介する。 \section{CbCの要求仕様} 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ @@ -14,34 +14,41 @@ 、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ ベルな言語による記述に比べて、余分な条件判断（Method search, Meta level での実行） を増やしてしまい、コンパクトで高速な応答を期待される -Real-time 処理や組み込み用途には適さない。 +Real-time 処理や組み込み用途には適さない。この用途にはハードウェアに近 +い記述が要求される。 +%ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記 +%述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー +%ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル +%チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため +%に既存の言語に対するコンパイラをその都度設計し直すことが必要になってき +%ている。 ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記 -述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー -ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル -チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため -に既存の言語に対するコンパイラを一々設計し直すことが必要になってきてい -る。 +述はあまりにも低レベルであり、依存性が強く汎用的ではない。さらに使用可 +能なゲート数が増えるにつれ、RISC 的な対称性の高い少数の命令よりも、複 +雑なSIMD命令やソフトウェアパイプライン命令を持つCPU が増えてきている。 +そのために既存の言語に対するコンパイラをその都度設計し直すことが必要に +なってきている。 VHDL, Verilog などのハードウェア記述言語は有限状態遷移の中に閉じており 、オブジェクト指向などの抽象化とはまったく別なものとなってしまっている。 -このように3 つは全く異なる方向を向いている。コンパイラの自動生成などが -重要な研究テーマとなると考えられるが、ハードウェア記述言語、アセンブラ -、プログラミング言語の3 つが全く独立したものであれば困難なものになると -考えられる。 +このようにハードウェア記述言語、アセンブラ、プログラミング言語の3つは +全く異なる方向を向いている。コンパイラの自動生成などが重要な研究テーマ +となると考えられるが、この3つが全く独立したものであれば困難なものにな +ると考えられる。 そこでCbC はこの3 つを埋めるべく以下のような要求仕様に従って設計された。 \begin{itemize} \item ハードウェアとスタックマシンの中間言語 - インタプリタ記述やコンパイラターゲットとして優れること。アーキテク - チャ依存性が少ないこと、また、アーキテクチャ依存性をモデル化できる。 + インタプリタ記述やコンパイラターゲットとして優れる。アーキテクチャ + 依存性が少ない。また、アーキテクチャ依存性をモデル化できる。 \item C 言語よりも下位の言語 - アセンブラよりも汎用性と記述性に優れC と互換であること。C をCbC に - コンパイルでき、ハンドコンパイルの結果を同値なコードに変換できる。 + アセンブラよりも汎用性と記述性に優れC と互換である。C をCbC にコン + パイルでき、ハンドコンパイルの結果を同値なコードに変換できる。 \item 明確な実行モデル @@ -55,20 +62,25 @@ \item Thread を実行モデルに内蔵できる - 並列処理記述法ではなく状態遷移として表現できる。 + %並列処理記述法ではなく状態遷移として表現できる。 + 状態遷移記述とCbC上のスケジューラ実装によりスレッドを実現可能にす + る。 \item クリティカルパスの最適化 - 全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出 - して最適化できる。 + 全体を散漫に最適化するのではなく、実行ルーチンから重要な箇所を抜き + 出し、アセンブラに近い最適化をソースコードレベルで実現する。 + + %全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出 + %して最適化できる。 \end{itemize} これらの仕様はハードウェア記述とソフトウェア記述の両方を同時に行いつつ 、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ -グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移 -記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に -適した言語を作ることを考え、スタックマシンを避けてContinuation（継続） -が導入されている。 +グラム変換やコンパイラターゲットとしての使用を意識している。状態遷移記 +述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に適 +した言語を作ることを考え、スタックマシンを避けてContinuation（継続）が +導入されている。 \section{コードセグメントと継続} @@ -102,6 +114,31 @@ \label{fig:continuation} \end{figure} +\subsection{Schemeにおける継続制御} +継続とは一般的には「現在の処理を続行するための情報」と解釈されている。 +継続制御はその情報をプログラム記述で操作するための構文である。 +例としてSchemeでの継続の使用をコード\ref{code:scheme-cont}に挙げる。 + +%\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/ +\lstinputlisting + [caption=Schemeでの継続制御の例, + label=code:scheme-cont, + language=Lisp, + morekeywords={cont,cont-test}, + emph={gosh}, + emphstyle=\bfseries\underbar] + {sources/scheme-cont-out.scmout} + +この例では関数\verb|cont-test|内にて\verb|call/cc|を呼ぶことで、現在の +計算処理の``継続''を関数として変数\verb|cont|に保持している。 + +その後、\verb|(cont)|という命令でその関数を実行すると、contが代入され +た位置に処理が復帰する。そのため、直前の``before''は出力されずに +``after''が出力されていることが分かる。\verb|cont|では関数の継続処理だ +けでなく、引数などの環境も一緒に保持しているので、この\verb|cont|は呼 +ばれる度に \verb|i|カウントアップし、その値を返すことになる。 + + CbCはこの継続制御を基本として設計されており、その実現のためにコードセ グメントと軽量継続という概念を用いている。 以下ではその二つについて説明する。 @@ -220,7 +257,27 @@ \label{fig:cbcreturn} \end{figure}% +環境付きは実際にはCにおける\verb|setjmp()/longjmp()|とほぼ同じ処理であ +る。この二つの関数はCで継続を実現するために用いられる。例としてコード +\ref{code:setjmp}を挙げる。このコードでは\verb|setfunc|内で +\verb|setjmp|を使用している。\verb|setjmp|は通常は0を返すため、if文の +内部は実行されないが、その後\verb|longjmp|が実行されると、関連する +\verb|setjmp|が呼び出された環境に``継続''し、非零を返すためif文の中が +実行されることになる。この時、\verb|longjmp|の呼出側（この例では +\verb|jmpfunc|）の環境は失われる。 +環境付き継続もこの動作によく似ており、if文内でreturnのみを記述すること +に相当する。 + +\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/ +\lstinputlisting + [caption=setjmp/longjmpの例, + basicstyle=\footnotesize\ttfamily,% + commentstyle=\footnotesize\itshape\rmfamily,% + label=code:setjmp, + emph={setjmp,longjmp}] + {sources/setjmp.c} +\lstset{morecomment=[s]{/*}{*/}} % /*元に戻す*/ @@ -264,10 +321,10 @@ %う方法、SOAPやMPIなどのライブラリ、Telescripに見られる言語仕様への埋め %込みなどがあった。これらは通信に関する複雑なセマンティクスを実現する手 %段といえる。 -% TODO +% TODO 分散プログラミング -\section{CbCコンパイラの現状と問題点} +\section{CbCコンパイラの現状と本研究における目標} \label{sec:cbc-problem} \subsection{micro-cとGCC} @@ -282,74 +339,73 @@ いる。これらをCbCでも活用したいという要望からコンパイラ環境の移植が行 われた。 -\subsection{GCCベースコンパイラの問題点}\label{sec:gcc-problems} +\subsection{本研究における目標}\label{sec:gcc-problems} この時の実装でコードセグメント、継続制御構造などは実装され、一通りの CbCプログラムのコンパイルが可能となった。 -しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制 -御構造の実装方法の影響により、いくつかの問題が発生している。 -以下にその問題点を列記する。 -%この問題に対せる解決を \ref{chp:impl}章にて説明する。 +本研究ではこのGCCベースのコンパイラをより実用的なCbCコンパイラとすべく +以下の項目を目標とする。 \begin{itemize} \item 環境付き継続 - これは未実装の機能である。 - 仕様に若干変更があったので新しい仕様に対応したい。 + Cとの互換性のための制御構造である環境付き継続を実装する。 \item 並列代入 - CbCでは現在のコードセグメントのインタフェイスと次に継続するコード - セグメントの引数は同じメモリスペース（もしくはレジスタ）に格納して - いる。そのためコード\ref{code:parallel-example}のように変数の値を - 入れ替えるような処理では並列代入が行われることになる。 - 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる - 複雑な並列代入ではバグが見つかっている。 - \lstinputlisting - [caption=並列代入の例, - label=code:parallel-example] - {sources/parallel-example.cbc} + これまでGCCベースのコンパイラでは、実装方法の影響から継続制御に一 + 部制限が存在した。これは実行中のコードセグメントの引数と継続制御に + 渡す引数の順序が入れ替わる場合等に継続が行えないという制限である。 + + 並列代入を行うことで引数順序の影響はなくなり、この制限を排除できる。 \item PowerPCにおける間接継続(indirect goto) - CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し - (indirect call)の様にコードセグメントポインタを用いた間接継続が可 - 能である。 + Cでの関数ポインタを用いた間接呼び出し(indirect call)の様に、CbCで + 用いる継続制御においても、コードセグメントポインタを用いたメモリ参 + 照による間接的な継続が可能である。これを間接継続と呼んでいる。 + コード\ref{code:indirect-example}のcodepointerへの継続が間接継続に + 当たる。 \lstinputlisting[ caption=間接継続の例（2つめのgoto文）, label=code:indirect-example] {sources/indirect-example.cbc} - しかしPowerPCアーキテクチャでは最適化の問題でこの機能が働かないこ - とが分かっている。 + しかしPowerPCアーキテクチャでは最適化の問題からこの間接継続がこれ + まで制限されていた。 間接継続はCbCでのプログラミングには必須であり、また本研究室の主要 - プロジェクトであるCeriumはPS3をメインターゲットとしているため、こ - の対応は必須のものである。 + プロジェクトであるCeriumはPS3（PowerPCをもつ）をメインターゲットと + しているため、この対応は必須のものである。 - \item プロトタイプ宣言 + \item プロトタイプ宣言の自動化 - Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。 - しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記 - 述という性質上、プログラムを記述する際は上から下に実行順にコードセ - グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大 - な数になる。 - これはプログラミングにおける障害とも言える。 + Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っているが、 + CbCでは返り値が存在しないなど、あまり重要な意味をなさない。 + また、micro-cではこれを極力排除するよう設計されているため、ソース + コードの互換性が薄れてしまう。 + + プロトタイプを自動生成することにより、この互換性を向上させる。 + + \item x86での継続制御の最適化 - \item x86での継続制御のオーバヘッド + x86では、Cの関数呼び出し全ての引数をメモリに格納する。コードセグメ + ントは関数をベースに作られているため、このABIに引きずられ実効速度 + に影響をもたらしている。引数の一部をレジスタに格納することで、x86 + における継続処理の高速化を行う。 - micro-c実装ではx86アーキテクチャでのコードセグメント継続の際には引 - 数をレジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォ - ルトでは全ての引数をメモリに格納する。コードセグメントは関数をベー - スに作られているため、このABIに引きずられ実効速度に影響をもたらす。 + \item メンテナンス性の向上 + GCCのソースコードは200万行にものぼる。CbCコンパイラで修正するソー + スコードはそのごく一部であるが、GCCのアップデートによる修正はCbC用 + のソースコードにも大きな影響をもたらす。 + GCCの最新リリースに追従するためには、アップデートも考慮し、洗練さ + れたメンテナンス方法が必要になる。 \end{itemize} -これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ -ていた。 %特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。 -\ref{chp:impl}章ではこれらの問題の解決手法を説明する。 +\ref{chp:impl}章ではこれらの項目の実装を行う。 diff -r b59d31966d7d -r 8ef81ff8cb52 conclusion.tex --- a/conclusion.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/conclusion.tex Fri Feb 12 13:10:57 2010 +0900 @@ -16,7 +16,7 @@ \ref{chp:impl}章ではこれらの問題に対処するため、GCCベースコンパイラの 改善を行った。ここでは最初にGCCに移植した際の実装方法を再確認し、その -上で問題点の解決方法の提案、実装を行った。 +上で問題点の解決方法の提案し、実装した。 \ref{chp:eval}章では、\ref{chp:impl}章における改善点の評価とともに、実 用的なプログラムが動作可能になったことで、以前のコンパイラとGCCベース @@ -37,22 +37,18 @@ \section{今後の課題} -作業中 - -% TODO: 実用的なCbCプログラムが実行可能になった事で、CbCを用いた研究もこれまで にない応用が可能になる。 -特に、本研究室の提案するCeriumはこれまではC++を用いて実装されていたが -、現在はCbCへの移植作業が進行中である。 +本研究室の提案するCeriumはこれまではC++を用いて実装されていたが、現在 +はCbCへの移植作業が進行中である。その他、CbCを用いた検証や分散プログラ +ミングなどの研究もこれからの研究課題となる。 -% オブジェクティブCbC -% C2CbC +また、CbC言語自体の仕様拡張も検討されている。 +特にオブジェクト指向は現在のプログラミングの主流であり、CbCでもその実 +装を行いたい。しかし\ref{chp:intro}章でも述べたようにCbCの開発動機には +オブジェクト指向の問題点も含まれる。オブジェクティブなCbCの導入には、 +CbCという言語の特徴を活かしつつ、この問題を回避していく必要がある。 -今後はCbCを用いた検証手法の確立、またプログラム分割のためのCからCbCへ -の変換プログラムの実装などが必要になる。 - - - diff -r b59d31966d7d -r 8ef81ff8cb52 evaluations.tex --- a/evaluations.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/evaluations.tex Fri Feb 12 13:10:57 2010 +0900 @@ -3,18 +3,47 @@ 本章では本研究の評価を行う。 + +\section{本研究での改善による成果} +本研究では、2008年に実装されたGCCベースコンパイラの改善を行った。 +まずはその改善による成果をここで述べる。 + +\begin{description} + \item [並列代入] \hfill \\ + 並列代入の改善により、これまで存在した軽量継続の際のバグが取り除か + れた。特に引数で渡されたコードセグメントポインタへ継続する際に出て + いたバグに対する影響が大きい。 + \item [環境付き継続の実装] \hfill \\ + この実装により、Cとの互換性が確保できた。これにより名実ともにCwC + コンパイラとして完成したと言える。 + \item [PowerPCでの間接軽量継続] \hfill \\ + これまで実質的にはPowerPCでは使用不能であった。 + + 本研究室ではPS3を用いた研究も行っており、その研究ではPowerPCアーキ + テクチャが必要となる。この問題の解決により、当研究室の提案する + CeriumはCbCベースへの移行が可能になる。 + \item [プトロタイプ宣言の自動生成] \hfill \\ + GCCとmicro-cの間にある、コードセグメントの宣言に関する差異が、この + 自動生成によって改善された。これにより、これまでmicro-c用に作成さ + れていたプログラムはほとんど修正することなく動く。 + \item [x86でのfastcall] \hfill \\ + 未だに主流であるx86アーキテクチャ（x86\_64への移行は進みつつあるが + ）において、若干の速度低下が見られていたものを改善した。この測定に + ついては\ref{sec:evaluation}節で行う。 +\end{description} + \section{GCCを使うことの利点・欠点} \label{sec:merit} -これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくGCCが +これまでCbCのコンパイルに使用してきたmicro-cに対し、新しくGCCが CwCのフルセットとして使用可能となった。ここでGCCを用いることの利点と欠 点について考察する。 \subsection*{アーキテクチャ} -mcにおいてはPPC,x86,MIPS,ARM,SPUなど、多数のCPUアーキテクチャをサポー -トしてきた。しかしあるCPUに新しく対応するには多大な時間、労力が必要と -なる。 +micro-cにおいてはPPC, x86, MIPS, ARM, SPUなど、多数のCPUアーキテクチャ +をサポートしてきた。しかし他のCPUに新しく対応するには多大な時間、労力 +が必要となる。 GCCは現在、既に20を越えるCPUに対応しており、またOS毎のABIの差異も吸収 可能である。これはGCCをコンパイラとすることに最大の利点である。 @@ -33,7 +62,7 @@ とくに、プログラムにおいては類似した形の式(expression)を扱うことがよく あるため、共通式除去は非常に効果が高い。同様の効果は同じ式を保持する変 数を用意することでも実現できるがソースコードの修正が必要になる。 -mcにはこの最適化は含まれていないため、複雑な計算式を含むプログラムにお +micro-cにはこの最適化は含まれていないため、複雑な計算式を含むプログラムにお いてはGCCの方が良いコンパイル結果を示すものと考えられる。 %\ref{sec:}の性能評価では最適化の効果についても測定する。 @@ -54,36 +83,31 @@ 本研究による軽量継続制御の実装には\ref{chp:impl}章で説明したように関数 の末尾最適化を利用した。それゆえコードセグメントのアセンブラ出力の命令 -列には一部関数呼び出し時のスタック処理が残ってしまうことが分かっている。 +列には関数呼び出し時のスタック処理が一部残ってしまうことが分かっている。 特にレジスタの少ないアーキテクチャ、x86などではそれが顕著に現れる。 -mcではコードセグメントと関数は完全に別物として取り扱っており、この様な +micro-cではコードセグメントと関数は完全に別物として取り扱っており、この様な スタック操作はコードセグメントには現れないため、このオーバヘッドがGCC では不利な点である。 \subsection*{互換性、ABI} -%これは最後の考察に入れよう -ソースコードレベルでの互換性の問題がある。 -また、継続制御のパラメタを - % 関数宣言 - % 型推定 - % ABI、特にppc - +また、同じく関数呼び出しの名残りから、GCCではmicro-cとのバイナリレベル +での互換性がない。つまりGCCでコンパイルしたコードセグメントからmicro-c +でコンパイルしたコードセグメントに継続することはできない。 -% 最適化 -% SPUでのベクトル演算 -% gdb -% architecture +これはmicro-cでの軽量継続のABIが関数とはまったく違うものだからである。 +今回はtailcallを実装に用いたため、関数としての制限があり、micro-cの +ABIに合わせることはできなかった。 -% 関数呼び出しのオーバヘッド -% 互換性,ソースコード、ABI +この問題はGCCの欠点というわけではないが、CbCベースの共有ライブラリを生 +成・使用する場合には注意が必要となる。 - -\section{性能評価} +\section{性能評価}\label{sec:evaluation} +次にコンパイラの性能評価を行う。 \subsection{評価項目、比較対象} コンパイラの出力した実行ファイルを複数回実行し、その実効速度を測定する @@ -94,13 +118,12 @@ る。一般的なプログラムではファイルサイズを気にすることは少ないが、CbC の用途には組み込みなども考えられているため、ファイルサイズの影響は大き い。比較する際はstripコマンドを用いてデバグ情報等を取り除いている。 -%SPUはm.. 実効速度、ファイルサイズの比較対象として2つ用意した。 一つは過去の研究でのGCCベースコンパイラ、つまり今回の改善を含めてない ものである。こちらはGCCのバージョン4.2.3をベースとしている。 -もう一つの比較対象にはmicro-cベースのコンパイラ（以下mc）を用いる。 +もう一つの比較対象にはmicro-cベースのコンパイラを用いる。 さらにGCCでは最適化による効果も評価するため、 \begin{inparaenum}[\itshape 1)\ttfamily] \item 最適化なし ``-O0'' @@ -118,7 +141,8 @@ した。このプログラムは付録\ref{apx:quicksort}に添付する。 測定環境は両コンパイラが対応しているアーキテクチャ、OSから以下の5つの -組み合わせ[CPUアーキテクチャ/OS種別]を選択した。 +組み合わせ[CPUアーキテクチャ/OS種別]を選択した。（ppcはPowerPCの意であ +る） \begin{itemize} \item ppc/OS X \item ppc/linux @@ -126,9 +150,9 @@ \item x86/OS X \item x86/linux \end{itemize} -なお、mcはmips,armにも対応しているが、現在その処理系が用意できなかった -ので割愛している。また、GCC-4.2.3ベースコンパイラはppcでは実行不能であ -ったためx86のみとなる。 +なお、micro-cはMIPS, ARMにも対応しているが、現在その処理系が用意できな +かったので割愛している。また、GCC-4.2.3ベースコンパイラはppcでは実行不 +能であったためx86のみとなる。 各評価マシンの詳細は付録\ref{sec:machine-specs}に掲載する。 @@ -144,7 +168,7 @@ \centering \begin{tabular}{|c|c|c|c|c|} \hline \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ} } - & \multicolumn{3}{c|}{GCC} & \multirow{2}{*}{mc} \\ \cline{2-4} + & \multicolumn{3}{c|}{GCC} & \multirow{2}{*}{micro-c} \\ \cline{2-4} &最適化なし&速度最適化&サイズ最適化& \\ \hline x86/OS X & 5.901 & 2.434 & 2.785 & 2.857 \\ \hline x86/Linux & 5.732 & 2.401 & 2.876 & 2.254 \\ \hline @@ -152,20 +176,20 @@ ppc/Linux &19.793 & 3.955 & 4.013 & 6.454 \\ \hline ppc/PS3 &39.176 & 5.874 & 6.111 &11.121 \\ \hline \end{tabular} - \caption{アーキテクチャ毎のGCCとmcの速度比較（単位: 秒）} + \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒）} \label{tab:speed-mc-vs-gcc} \end{table} -次に実行ファイルのstrip前のファイルサイズを表\ref{tab:eval-nostrip} +実行ファイルのstrip前のファイルサイズを表\ref{tab:eval-nostrip} に、strip後のファイルサイズを表\ref{tab:eval-strip}に示す。 \begin{table}[htpb] \centering \begin{tabular}{|c|c|c|c|c|c|} \hline \multirow{3}{*}{ \backslashbox{CPU/OS}{コンパイラ} } - & \multicolumn{4}{c|}{GCC} & \multirow{3}{*}{mc} \\ \cline{2-5} + & \multicolumn{4}{c|}{GCC} & \multirow{3}{*}{micro-c} \\ \cline{2-5} & \multicolumn{2}{c|}{デバグ情報(-g)付き} & \multicolumn{2}{c|}{デバグ情報なし} & \\ \cline{2-5} - & -O2 & -Os & -O2 & -Os & \\ \hline + & 速度最適化 & サイズ最適化 & 速度最適化 & サイズ最適化 & \\ \hline x86/OS X & 11100 & 11100 & 9804 & 9804 & 11136 \\ \hline x86/Linux & 18444 & 17310 & 8216 & 8214 & 9844 \\ \hline ppc/OS X & 10392 & 10392 & 9172 & 9172 & 14396 \\ \hline @@ -179,8 +203,8 @@ \centering \begin{tabular}{|c|c|c|c|} \hline \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ} } - & \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{mc} \\ \cline{2-3} - & -O2 & -Os & \\ \hline + & \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{micro-c} \\ \cline{2-3} + & 速度最適化 & サイズ最適化 & \\ \hline x86/OS X & 9176 & 9176 & 9172 \\ \hline x86/Linux & 5752 & 5752 & 5796 \\ \hline ppc/OS X & 8576 & 8576 & 12664 \\ \hline @@ -191,7 +215,7 @@ \label{tab:eval-strip} \end{table} -最後に、本研究での実装GCC-4.4.2と以前のバージョンGCC-4.2.3との比較を表 +本研究での実装GCC-4.4.2と以前のバージョンGCC-4.2.3との比較を表 \ref{tab:speed-old-vs-new}に示す。こちらはx86のみ、最適化も-Osは対応し ていない。 \begin{table}[htpb] @@ -200,7 +224,7 @@ \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ} } & \multicolumn{2}{c|}{CbC on GCC-4.4.2} & \multicolumn{2}{c|}{CbC on GCC-4.2.3} \\ \hline - & -O0 & -O2 & -O0 & -O2 \\ \hline + & 最適化なし & 速度最適化 & 最適化なし & 速度最適化 \\ \hline x86/OS X & 5.907 & 2.434 & 4.668 & 3.048 \\ \hline x86/Linux & 5.715 & 2.401 & 4.525 & 2.851 \\ \hline \end{tabular} @@ -212,8 +236,6 @@ \subsection{評価結果考察} % stripするとx86はサイズに変化がない \subsubsection{速度面} -まずは速度面からこの測定結果を考察する。 - まずどのアーキテクチャにおいても、GCCの最適化が大きな速度差を生み出し ている事が分かる。最適化なしと速度最適化を比較すると、x86では2.4倍、 ppcでは5〜7倍もの差が生じている。 @@ -223,51 +245,26 @@ れる。しかしながら最適化を有効にすることでそのメモリへの一時変数の確保 も解消されるということが分かった。 -x86はOS XとLinuxの環境で測定を行った。速度最適化のGCCとmcを比べると、 -OS Xではmcに比べて20\%ほど早くなった事が分かる。しかし逆にLinux環境で -は6\%の速度低下が示された。どちらにしてもppcほどの良い結果ではない。こ -れは自由に使えるレジスタが極めて少ないというx86の特殊なアーキテクチャ -が要因だと考えられる。そのためGCCの最適化が十分に機能できなかった可能 -性がある。この6\%の差は実用レベルでは問題なく、プログラムの構成によっ -ては結果は逆転する事も十分にある。 +x86はOS XとLinuxの環境で測定を行った。速度最適化のGCCとmicro-cを比べる +と、 OS Xではmicro-cに比べて20\%ほど早くなった事が分かる。しかし逆に +Linux環境では6\%の速度低下が示された。どちらにしてもppcほどの良い結果 +ではない。これは自由に使えるレジスタが極めて少ないというx86の特殊なア +ーキテクチャが要因だと考えられる。そのためGCCの最適化が十分に機能でき +なかった可能性がある。この6\%の差は実用レベルでは問題なく、プログラム +の構成によっては結果は逆転する事も十分にある。 ppcにおいてはどのオペレーティングシステムでも、速度最適化を使ったGCCは -mcに比べて早い事が分かる。いずれも約2倍、もしくはそれ以上に速度が向上 -している。これはGCCの最適化機構が十分に働いている要因が大きい。 +micro-cに比べて早い事が分かる。いずれも約2倍、もしくはそれ以上に速度が +向上している。これはGCCの最適化機構が十分に働いている要因が大きい。 \subsubsection{アセンブラ比較} 実際に出力されたアセンブラから速度向上の要因を確かめるため、quicksort プログラムで使用されているコードセグメントを一つ例に挙げる。CbCのプロ グラムソースがコード \ref{code:divider-e}である。このコードセグメント -の速度最適化を使ったGCCによる出力がコード\ref{code:divider-e-gcc}、mc -による出力がコード \ref{code:divider-e-mc}である。 -どちらもアーキテクチャはppcである。 - -%まずどのアーキテクチャにおいてもgccの最適化の効果が大きいことが分かる -%。 x86では約2.5倍、ppcでは4~7倍もの差が生じている。ppcの方で異様に効果 -%が高いように見えるのは、関数やコードセグメントの引数渡しがレジスタベー -%スのため、最適化なしの場合には無駄なメモリアクセスが生じているためであ -%る。 +の速度最適化を使ったGCCによる出力がコード\ref{code:divider-e-gcc}、 +micro-c による出力がコード \ref{code:divider-e-mc}である。どちらもアー +キテクチャはppcである。 -%x86はOS XとLinuxの環境で測定を行った。OS Xではmcに比べて20\%ほど早くな -%ったことが分かる。しかし逆にLinux環境では6\%の速度低下が示された。 -%どちらにおいてもppcほどの良い結果ではない。これは自由に使えるレジスタ -%が極めて少ないというx86の特殊なアーキテクチャが要因だと考えられる。そ -%のためにgccの最適化が十分に働かなかった可能性がある。逆に言うとmcが高 -%いレベルでx86のアセンブラ命令を実行しているともとれる。この6\%の差は実 -%用レベルでは問題なく、プログラムの構成によっては結果は逆転する事も十分 -%にある。 - -%ppcではどのオペレーティングシステムでもmcに比べてgccが早いことが分かる -%。いずれも約2倍近くあるいはそれ以上に速度が向上している。これはgccの最 -%適化機構が十分に働いている要因が大きい。 - -%\subsubsection{アセンブラ比較} -%比較のため、quicksortプログラムで使われているコードセグメントを一つ例 -%にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン -%トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー -%ド \ref{code:divider_s_mc} である。 -% \lstinputlisting[ caption=quicksortプログラムで使われているコードセグメント, label=code:divider-e] @@ -281,21 +278,21 @@ \hfill \begin{minipage}[t]{.45\textwidth} \lstinputlisting[ - caption=divider\_eのmcによる出力(ppc), + caption=divider\_eのmicro-cによる出力(ppc), label=code:divider-e-mc] {sources/divider-e-mc.asm} \end{minipage} -もっとも比較しやすい箇所は\verb|e-1|の処理である。 -コード\ref{code:divider-e-gcc}のGCCではこれを1命令の\verb|addi 5,5,-1| -で行っている。 mcではこれが\verb|mr, addi, mr|という3命令になっている +もっとも比較しやすい箇所は\verb|e-1|の処理である。コード +\ref{code:divider-e-gcc}のGCCではこれを1命令の\verb|addi 5,5,-1| で行 +っている。 micro-cではこれが\verb|mr, addi, mr|という3命令になっている 。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で ある。この様な細かい命令の展開が速度に差が出る要因である。 またこのppcのアセンブラからも、x86での速度差が少ないことが頷ける。引数 のほとんどをメモリに格納するx86では、計算のために一度レジスタに格納し ないといけないことから、この命令は結局3命令になるはずであり、実際にx86 -ではGCC,mc共にそのようなコードが出力されていた。 +ではGCC, micro-c共にそのようなコードが出力されていた。 この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度 の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が @@ -313,9 +310,10 @@ OSも存在しないため仮想記憶の概念がない。そのためメモリに乗り切らないプ ログラムはそもそも実行不能である。 -まず、評価の主な特徴として、strip後のファイルサイズ\ref{tab:eval-strip} -をみると、x86ではmcとGCCでほとんど差がない事が分かる。この環境では速度 -面でも大きな差はなく、mcの精度の良さがわかる。 +まず、評価の主な特徴として、strip後のファイルサイズ +\ref{tab:eval-strip} をみると、x86ではmicro-cとGCCでほとんど差がない事 +が分かる。この環境では速度面でも大きな差はなく、micro-cの精度の良さが +わかる。 デバグ情報のあり／なし／strip後との比較で大きな差が出ているのは全て Linux（PS3含む）である。Linuxでは実行ファイルのファイル形式にELFを用い @@ -325,11 +323,12 @@ Linuxは組み込み用途に多く用いられているため、極端にメモリの制限された 環境ではデバグが困難になることが考えられる。 -また興味深い特徴として、-O2と-Osの差がppc/PS3以外は全くないことも分か -った。 -Osは-O2の最適化機能から、ファイルサイズが大きくなるものを除外 -したものである。評価結果には-Osによるファイルサイズの減少はほとんどな -く、しかし速度は少々遅くなっている。このことからCbCによるプログラムで -は-Osを用いる必要はなく、-O2で十分であることが分かった。 +また興味深い特徴として、速度最適化とサイズ最適化の差がppc/PS3以外は全 +くないことも分かった。 サイズ最適化は速度最適化の最適化機能から、ファ +イルサイズが大きくなるものを除外したものである。評価結果にはサイズ最適 +化によるファイルサイズの減少はほとんどなく、しかし速度は少々遅くなって +いる。このことからCbCによるプログラムではサイズ最適化を用いる必要はな +く、速度最適化で十分であることが分かった。 % ELF, Mach-O @@ -367,9 +366,6 @@ -%\section{CbCでのプログラミング} -% TODO: - \section{メンテナンス性の向上に関する取り組み}\label{sec:mentainance} @@ -380,7 +376,7 @@ トではバグの除去や最適化の改善などが行われている。 そのためCbCコンパイラでもそのリリースに沿ってアップデートすることが望 ましく、実際に今回の改善の際にも2010年1月現在での最新リリースである -4.4.2をベースとしている。 +4.4.2をベースとして行い、本稿執筆中に4.4.3へのアップデートが行われた。 しかしアップデートの度に新しいソースコードを書き換えるのは無理があり、 現実的ではない。最良の方法はGCCの正式な機能として開発リポジトリにマー @@ -404,7 +400,7 @@ \begin{figure}[htpb] \begin{center} - \includegraphics[width=.4\textwidth]{figures/gcc-repository.eps} + \includegraphics[width=.7\textwidth]{figures/gcc-repository.eps} \end{center} \caption{CbCコンパイラ開発でのリポジトリ管理（左が本家のリリースタイ ムライン、中央がGCC-copy、右がCbCの開発用リポジトリのタイムライン）} @@ -418,10 +414,10 @@ \begin{enumerate} \item GCC-copyリポジトリ中のファイル全てを消す（バージョン管理情 報以外） - \item gcc-core-4.4.3.tar.gzを展開し、全ファイルをGCC-copyに追加 + \item gcc-core-{\tt\it version}.tar.gzを展開し、全ファイルをGCC-copyに追加 \item \verb|hg status|で追加ファイル、削除ファイルを確認 \item コミット - \item gcc-4.4.3タグの追加 + \item gcc-{\tt\it version}タグの追加 \end{enumerate} \item CbConGCCリポジトリにて \begin{enumerate} @@ -430,7 +426,7 @@ \item 衝突のあったファイルを修正 \item 実際にビルドしてテストファイルが動くことを確認 \item コミット - \item cbc-4.4.3タグの追加 + \item cbc-{\tt\it version}タグの追加 \end{enumerate} \end{itemize} @@ -438,9 +434,9 @@ \subsection{このリポジトリ管理方法の評価} -実際にこのリポジトリ管理方法を用いてアップデートを行った。この作業では +実際にこのリポジトリ管理方法を用いてアップデートを行った。この評価では バージョン 4.4.0から4.4.2へのアップデートと、4.4.2から4.4.3へのアップ -デートである。 +デートを行った。 アップデートの際に何らかの問題が生じるのはCbConGCCリポジトリでの衝突フ ァイルの修正だけである。4.4.3へのアップデートでは特になにも衝突するこ diff -r b59d31966d7d -r 8ef81ff8cb52 figures/gcc-repository.dia Binary file figures/gcc-repository.dia has changed diff -r b59d31966d7d -r 8ef81ff8cb52 figures/gcc-repository.eps --- a/figures/gcc-repository.eps Mon Feb 08 03:50:27 2010 +0900 +++ b/figures/gcc-repository.eps Fri Feb 12 13:10:57 2010 +0900 @@ -1,11 +1,11 @@ %!PS-Adobe-2.0 EPSF-2.0 %%Title: /home/kent/WorkSpace/Mercurial/master-paper/figures/gcc-repository.dia %%Creator: Dia v0.97 -%%CreationDate: Sun Feb 7 16:42:35 2010 +%%CreationDate: Tue Feb 9 01:43:06 2010 %%For: kent %%Orientation: Portrait %%Magnification: 1.0000 -%%BoundingBox: 0 0 545 678 +%%BoundingBox: 0 0 772 678 %%BeginSetup %%EndSetup %%EndComments @@ -118,7 +118,7 @@ /start_ol { gsave 1.1 dpi_x div dup scale} bind def /end_ol { closepath fill grestore } bind def 28.346000 -28.346000 scale -9.000000 -24.075000 translate +13.000000 -24.075000 translate %%EndProlog @@ -127,7 +127,7 @@ [] 0 sd 0 slc 0.000000 0.000000 0.000000 srgb -n -6.000000 2.000000 m -6.000000 20.000000 l s +n -10.000000 2.000000 m -10.000000 20.000000 l s 0.150000 slw [] 0 sd [] 0 sd @@ -137,8 +137,8 @@ [] 0 sd [] 0 sd 0 slc -n 6.000000 6.000000 m 6.000000 22.000000 l s -gsave -7.335000 0.833469 translate 0.035278 -0.035278 scale +n 10.000000 6.000000 m 10.000000 22.000000 l s +gsave -11.335000 0.843750 translate 0.035278 -0.035278 scale start_ol 2019 2836 moveto 277 2836 lineto @@ -168,7 +168,7 @@ 102 496 lineto 1381 1625 2019 2836 conicto end_ol grestore -gsave -6.695601 0.833469 translate 0.035278 -0.035278 scale +gsave -10.695601 0.843750 translate 0.035278 -0.035278 scale start_ol 1736 15 moveto 2257 -10 2369 -10 conicto @@ -222,7 +222,7 @@ 4144 2612 lineto 4144 3366 lineto end_ol grestore -gsave -6.056203 0.833469 translate 0.035278 -0.035278 scale +gsave -10.056203 0.843750 translate 0.035278 -0.035278 scale start_ol 2816 504 moveto 2816 1472 lineto @@ -248,7 +248,7 @@ 2276 320 2469 365 conicto 2662 410 2816 504 conicto end_ol grestore -gsave -5.561672 0.833469 translate 0.035278 -0.035278 scale +gsave -9.561672 0.843750 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -270,7 +270,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave -5.114592 0.833469 translate 0.035278 -0.035278 scale +gsave -9.114592 0.843750 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -292,7 +292,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave -8.240000 1.633469 translate 0.035278 -0.035278 scale +gsave -12.240000 1.643750 translate 0.035278 -0.035278 scale start_ol 2724 1469 moveto 2126 1469 lineto @@ -364,7 +364,7 @@ 1882 2792 lineto 739 2792 lineto end_ol grestore -gsave -7.600601 1.633469 translate 0.035278 -0.035278 scale +gsave -11.600601 1.643750 translate 0.035278 -0.035278 scale start_ol 1571 1887 moveto 1065 1887 lineto @@ -439,7 +439,7 @@ 2014 2758 1270 2203 conicto 3594 2203 lineto end_ol grestore -gsave -6.961203 1.633469 translate 0.035278 -0.035278 scale +gsave -10.961203 1.643750 translate 0.035278 -0.035278 scale start_ol 778 1600 moveto 1800 1600 lineto @@ -490,7 +490,7 @@ 2889 2257 lineto 3123 1508 3517 973 conicto end_ol grestore -gsave -6.321804 1.633469 translate 0.035278 -0.035278 scale +gsave -10.321804 1.643750 translate 0.035278 -0.035278 scale start_ol 3502 3604 moveto 3901 3604 lineto @@ -507,7 +507,7 @@ 1352 1464 lineto 963 1464 lineto end_ol grestore -gsave -5.682405 1.633469 translate 0.035278 -0.035278 scale +gsave -9.682405 1.643750 translate 0.035278 -0.035278 scale start_ol 3502 3604 moveto 3901 3604 lineto @@ -524,7 +524,7 @@ 1352 1464 lineto 963 1464 lineto end_ol grestore -gsave -5.043007 1.633469 translate 0.035278 -0.035278 scale +gsave -9.043007 1.643750 translate 0.035278 -0.035278 scale start_ol 452 1659 moveto 452 2033 lineto @@ -532,7 +532,7 @@ 4412 1659 lineto 452 1659 lineto end_ol grestore -gsave -4.403608 1.633469 translate 0.035278 -0.035278 scale +gsave -8.403608 1.643750 translate 0.035278 -0.035278 scale start_ol 924 3478 moveto 3940 3478 lineto @@ -713,7 +713,7 @@ 2688 2688 lineto 1542 -238 lineto end_ol grestore -gsave 5.348750 2.821250 translate 0.035278 -0.035278 scale +gsave 9.348750 2.821250 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -735,7 +735,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave 5.795830 2.821250 translate 0.035278 -0.035278 scale +gsave 9.795830 2.821250 translate 0.035278 -0.035278 scale start_ol 2368 1344 moveto 2368 1823 2171 2095 conicto @@ -761,7 +761,7 @@ 896 3712 lineto 896 2304 lineto end_ol grestore -gsave 6.202949 2.821250 translate 0.035278 -0.035278 scale +gsave 10.202949 2.821250 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -783,7 +783,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave 4.805000 3.621250 translate 0.035278 -0.035278 scale +gsave 8.805000 3.621250 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -804,7 +804,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave 5.197129 3.621250 translate 0.035278 -0.035278 scale +gsave 9.197129 3.621250 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto @@ -824,10 +824,10 @@ 2217 2752 2452 2471 conicto 2688 2191 2688 1646 conicto end_ol grestore -gsave 5.601743 3.621250 translate 0.035278 -0.035278 scale +gsave 9.601743 3.621250 translate 0.035278 -0.035278 scale start_ol end_ol grestore -gsave 5.804050 3.621250 translate 0.035278 -0.035278 scale +gsave 9.804050 3.621250 translate 0.035278 -0.035278 scale start_ol 2816 504 moveto 2816 1472 lineto @@ -853,7 +853,7 @@ 2276 320 2469 365 conicto 2662 410 2816 504 conicto end_ol grestore -gsave 6.298581 3.621250 translate 0.035278 -0.035278 scale +gsave 10.298581 3.621250 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -875,7 +875,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave 6.745661 3.621250 translate 0.035278 -0.035278 scale +gsave 10.745661 3.621250 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -901,23 +901,23 @@ [] 0 sd [] 0 sd 0 slc -n -6.000000 11.000000 m -0.535321 11.910780 l s +n -10.000000 11.000000 m -0.540012 11.945999 l s [] 0 sd 0 slj 0 slc -n -0.165423 11.972429 m -0.699720 12.136828 l -0.535321 11.910780 l -0.617521 11.643631 l ef -n -0.165423 11.972429 m -0.699720 12.136828 l -0.535321 11.910780 l -0.617521 11.643631 l cp s +n -0.166873 11.983313 m -0.689267 12.182320 l -0.540012 11.945999 l -0.639515 11.684802 l ef +n -0.166873 11.983313 m -0.689267 12.182320 l -0.540012 11.945999 l -0.639515 11.684802 l cp s 0.150000 slw [] 0 sd [] 0 sd 0 slc -n 0.000000 13.000000 m 5.464679 13.910780 l s +n 0.000000 13.000000 m 9.459988 13.945999 l s [] 0 sd 0 slj 0 slc -n 5.834577 13.972429 m 5.300280 14.136828 l 5.464679 13.910780 l 5.382479 13.643631 l ef -n 5.834577 13.972429 m 5.300280 14.136828 l 5.464679 13.910780 l 5.382479 13.643631 l cp s -gsave -9.000000 11.000000 translate 0.035278 -0.035278 scale +n 9.833127 13.983313 m 9.310733 14.182320 l 9.459988 13.945999 l 9.360485 13.684802 l ef +n 9.833127 13.983313 m 9.310733 14.182320 l 9.459988 13.945999 l 9.360485 13.684802 l cp s +gsave -13.000000 11.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -938,7 +938,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.680301 11.000000 translate 0.035278 -0.035278 scale +gsave -12.680301 11.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -946,7 +946,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -8.360601 11.000000 translate 0.035278 -0.035278 scale +gsave -12.360601 11.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -967,7 +967,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.040902 11.000000 translate 0.035278 -0.035278 scale +gsave -12.040902 11.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -975,7 +975,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -7.721203 11.000000 translate 0.035278 -0.035278 scale +gsave -11.721203 11.000000 translate 0.035278 -0.035278 scale start_ol 1605 3191 moveto 1605 3201 lineto @@ -1000,7 +1000,7 @@ 730 2077 lineto 1605 3191 lineto end_ol grestore -gsave -9.000000 11.800000 translate 0.035278 -0.035278 scale +gsave -13.000000 11.800000 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -1018,7 +1018,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave -8.752739 11.800000 translate 0.035278 -0.035278 scale +gsave -12.752739 11.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1043,7 +1043,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -8.358113 11.800000 translate 0.035278 -0.035278 scale +gsave -12.358113 11.800000 translate 0.035278 -0.035278 scale start_ol 448 3712 moveto 896 3712 lineto @@ -1051,7 +1051,7 @@ 448 0 lineto 448 3712 lineto end_ol grestore -gsave -8.180784 11.800000 translate 0.035278 -0.035278 scale +gsave -12.180784 11.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1076,7 +1076,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -7.786158 11.800000 translate 0.035278 -0.035278 scale +gsave -11.786158 11.800000 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -1109,7 +1109,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave -7.394029 11.800000 translate 0.035278 -0.035278 scale +gsave -11.394029 11.800000 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -1141,7 +1141,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave -7.061844 11.800000 translate 0.035278 -0.035278 scale +gsave -11.061844 11.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1170,23 +1170,23 @@ [] 0 sd [] 0 sd 0 slc -n -6.000000 16.000000 m -0.535321 16.910780 l s +n -10.000000 16.000000 m -0.540012 16.945999 l s [] 0 sd 0 slj 0 slc -n -0.165423 16.972429 m -0.699720 17.136828 l -0.535321 16.910780 l -0.617521 16.643631 l ef -n -0.165423 16.972429 m -0.699720 17.136828 l -0.535321 16.910780 l -0.617521 16.643631 l cp s +n -0.166873 16.983313 m -0.689267 17.182320 l -0.540012 16.945999 l -0.639515 16.684802 l ef +n -0.166873 16.983313 m -0.689267 17.182320 l -0.540012 16.945999 l -0.639515 16.684802 l cp s 0.150000 slw [] 0 sd [] 0 sd 0 slc -n 0.000000 18.000000 m 5.464679 18.910780 l s +n 0.000000 18.000000 m 9.459988 18.945999 l s [] 0 sd 0 slj 0 slc -n 5.834577 18.972429 m 5.300280 19.136828 l 5.464679 18.910780 l 5.382479 18.643631 l ef -n 5.834577 18.972429 m 5.300280 19.136828 l 5.464679 18.910780 l 5.382479 18.643631 l cp s -gsave -9.000000 16.000000 translate 0.035278 -0.035278 scale +n 9.833127 18.983313 m 9.310733 19.182320 l 9.459988 18.945999 l 9.360485 18.684802 l ef +n 9.833127 18.983313 m 9.310733 19.182320 l 9.459988 18.945999 l 9.360485 18.684802 l cp s +gsave -13.000000 16.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -1207,7 +1207,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.680301 16.000000 translate 0.035278 -0.035278 scale +gsave -12.680301 16.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -1215,7 +1215,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -8.360601 16.000000 translate 0.035278 -0.035278 scale +gsave -12.360601 16.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -1236,7 +1236,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.040902 16.000000 translate 0.035278 -0.035278 scale +gsave -12.040902 16.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -1244,7 +1244,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -7.721203 16.000000 translate 0.035278 -0.035278 scale +gsave -11.721203 16.000000 translate 0.035278 -0.035278 scale start_ol 876 2092 moveto 885 2092 lineto @@ -1265,7 +1265,7 @@ 910 3201 lineto 876 2092 lineto end_ol grestore -gsave -9.000000 16.800000 translate 0.035278 -0.035278 scale +gsave -13.000000 16.800000 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -1283,7 +1283,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave -8.752739 16.800000 translate 0.035278 -0.035278 scale +gsave -12.752739 16.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1308,7 +1308,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -8.358113 16.800000 translate 0.035278 -0.035278 scale +gsave -12.358113 16.800000 translate 0.035278 -0.035278 scale start_ol 448 3712 moveto 896 3712 lineto @@ -1316,7 +1316,7 @@ 448 0 lineto 448 3712 lineto end_ol grestore -gsave -8.180784 16.800000 translate 0.035278 -0.035278 scale +gsave -12.180784 16.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1341,7 +1341,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -7.786158 16.800000 translate 0.035278 -0.035278 scale +gsave -11.786158 16.800000 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -1374,7 +1374,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave -7.394029 16.800000 translate 0.035278 -0.035278 scale +gsave -11.394029 16.800000 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -1406,7 +1406,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave -7.061844 16.800000 translate 0.035278 -0.035278 scale +gsave -11.061844 16.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1435,13 +1435,13 @@ [] 0 sd [] 0 sd 0 slc -n -6.000000 3.000000 m -0.535321 3.910780 l s +n -10.000000 3.000000 m -0.540012 3.945999 l s [] 0 sd 0 slj 0 slc -n -0.165423 3.972429 m -0.699720 4.136828 l -0.535321 3.910780 l -0.617521 3.643631 l ef -n -0.165423 3.972429 m -0.699720 4.136828 l -0.535321 3.910780 l -0.617521 3.643631 l cp s -gsave -9.000000 3.000000 translate 0.035278 -0.035278 scale +n -0.166873 3.983313 m -0.689267 4.182320 l -0.540012 3.945999 l -0.639515 3.684802 l ef +n -0.166873 3.983313 m -0.689267 4.182320 l -0.540012 3.945999 l -0.639515 3.684802 l cp s +gsave -13.000000 3.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -1462,7 +1462,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.680301 3.000000 translate 0.035278 -0.035278 scale +gsave -12.680301 3.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -1470,7 +1470,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -8.360601 3.000000 translate 0.035278 -0.035278 scale +gsave -12.360601 3.000000 translate 0.035278 -0.035278 scale start_ol 1425 2870 moveto 1415 2870 lineto @@ -1491,7 +1491,7 @@ 1425 0 lineto 1425 851 lineto end_ol grestore -gsave -8.040902 3.000000 translate 0.035278 -0.035278 scale +gsave -12.040902 3.000000 translate 0.035278 -0.035278 scale start_ol 900 0 moveto 900 730 lineto @@ -1499,7 +1499,7 @@ 1532 0 lineto 900 0 lineto end_ol grestore -gsave -7.721203 3.000000 translate 0.035278 -0.035278 scale +gsave -11.721203 3.000000 translate 0.035278 -0.035278 scale start_ol 851 360 moveto 851 350 lineto @@ -1518,7 +1518,7 @@ 2019 2194 1756 1663 conicto 1493 1133 851 360 conicto end_ol grestore -gsave -9.000000 3.800000 translate 0.035278 -0.035278 scale +gsave -13.000000 3.800000 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -1536,7 +1536,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave -8.752739 3.800000 translate 0.035278 -0.035278 scale +gsave -12.752739 3.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1561,7 +1561,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -8.358113 3.800000 translate 0.035278 -0.035278 scale +gsave -12.358113 3.800000 translate 0.035278 -0.035278 scale start_ol 448 3712 moveto 896 3712 lineto @@ -1569,7 +1569,7 @@ 448 0 lineto 448 3712 lineto end_ol grestore -gsave -8.180784 3.800000 translate 0.035278 -0.035278 scale +gsave -12.180784 3.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1594,7 +1594,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -7.786158 3.800000 translate 0.035278 -0.035278 scale +gsave -11.786158 3.800000 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -1627,7 +1627,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave -7.394029 3.800000 translate 0.035278 -0.035278 scale +gsave -11.394029 3.800000 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -1659,7 +1659,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave -7.061844 3.800000 translate 0.035278 -0.035278 scale +gsave -11.061844 3.800000 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1684,7 +1684,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -4.016250 4.221250 translate 0.035278 -0.035278 scale +gsave -6.016250 4.221250 translate 0.035278 -0.035278 scale start_ol 2368 2560 moveto 2368 2176 lineto @@ -1706,7 +1706,7 @@ 1801 2752 1994 2704 conicto 2187 2656 2368 2560 conicto end_ol grestore -gsave -3.664081 4.221250 translate 0.035278 -0.035278 scale +gsave -5.664081 4.221250 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -1724,7 +1724,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave -3.416820 4.221250 translate 0.035278 -0.035278 scale +gsave -5.416820 4.221250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1749,7 +1749,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -3.022194 4.221250 translate 0.035278 -0.035278 scale +gsave -5.022194 4.221250 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -1782,7 +1782,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave -2.630065 4.221250 translate 0.035278 -0.035278 scale +gsave -4.630065 4.221250 translate 0.035278 -0.035278 scale start_ol 896 3456 moveto 896 2688 lineto @@ -1804,7 +1804,7 @@ 448 3456 lineto 896 3456 lineto end_ol grestore -gsave -2.380298 4.221250 translate 0.035278 -0.035278 scale +gsave -4.380298 4.221250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1833,13 +1833,13 @@ [] 0 sd [] 0 sd 0 slc -n 0.000000 5.000000 m 5.464679 5.910780 l s +n 0.000000 5.000000 m 9.459988 5.945999 l s [] 0 sd 0 slj 0 slc -n 5.834577 5.972429 m 5.300280 6.136828 l 5.464679 5.910780 l 5.382479 5.643631 l ef -n 5.834577 5.972429 m 5.300280 6.136828 l 5.464679 5.910780 l 5.382479 5.643631 l cp s -gsave 7.000000 8.650000 translate 0.035278 -0.035278 scale +n 9.833127 5.983313 m 9.310733 6.182320 l 9.459988 5.945999 l 9.360485 5.684802 l ef +n 9.833127 5.983313 m 9.310733 6.182320 l 9.459988 5.945999 l 9.360485 5.684802 l cp s +gsave 11.000000 8.650000 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -1861,7 +1861,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave 7.447080 8.650000 translate 0.035278 -0.035278 scale +gsave 11.447080 8.650000 translate 0.035278 -0.035278 scale start_ol 2368 1344 moveto 2368 1823 2171 2095 conicto @@ -1887,7 +1887,7 @@ 896 3712 lineto 896 2304 lineto end_ol grestore -gsave 7.854199 8.650000 translate 0.035278 -0.035278 scale +gsave 11.854199 8.650000 translate 0.035278 -0.035278 scale start_ol 3136 3264 moveto 3136 2752 lineto @@ -1909,7 +1909,7 @@ 2320 3584 2603 3504 conicto 2887 3424 3136 3264 conicto end_ol grestore -gsave 7.000000 9.450000 translate 0.035278 -0.035278 scale +gsave 11.000000 9.450000 translate 0.035278 -0.035278 scale start_ol 715 3380 moveto 4120 3380 lineto @@ -1921,7 +1921,7 @@ 715 3040 lineto 715 3380 lineto end_ol grestore -gsave 7.639399 9.450000 translate 0.035278 -0.035278 scale +gsave 11.639399 9.450000 translate 0.035278 -0.035278 scale start_ol 890 3536 moveto 1634 3166 2378 2709 conicto @@ -1935,7 +1935,7 @@ 3984 214 880 -58 conicto 832 306 lineto end_ol grestore -gsave 8.278797 9.450000 translate 0.035278 -0.035278 scale +gsave 12.278797 9.450000 translate 0.035278 -0.035278 scale start_ol 4032 -83 moveto 3702 1226 3351 2233 conicto @@ -1966,7 +1966,7 @@ 3361 3906 3623 3906 conicto 3886 3906 4071 3721 conicto end_ol grestore -gsave 8.918196 9.450000 translate 0.035278 -0.035278 scale +gsave 12.918196 9.450000 translate 0.035278 -0.035278 scale start_ol 472 1814 moveto 1522 1960 2514 2451 conicto @@ -1979,7 +1979,7 @@ 1542 1610 530 1464 conicto 472 1814 lineto end_ol grestore -gsave 9.557595 9.450000 translate 0.035278 -0.035278 scale +gsave 13.557595 9.450000 translate 0.035278 -0.035278 scale start_ol 910 3176 moveto 910 3526 lineto @@ -1996,7 +1996,7 @@ 535 1936 lineto 535 2286 lineto end_ol grestore -gsave 7.000000 10.250000 translate 0.035278 -0.035278 scale +gsave 11.000000 10.250000 translate 0.035278 -0.035278 scale start_ol 2899 219 moveto 3483 282 3808 681 conicto @@ -2027,7 +2027,7 @@ 2028 1469 2132 1984 conicto 2237 2500 2310 3166 conicto end_ol grestore -gsave 7.639399 10.250000 translate 0.035278 -0.035278 scale +gsave 11.639399 10.250000 translate 0.035278 -0.035278 scale start_ol 302 983 moveto 302 1299 lineto @@ -2082,7 +2082,7 @@ 2627 3283 lineto 2627 2831 lineto end_ol grestore -gsave 8.278797 10.250000 translate 0.035278 -0.035278 scale +gsave 12.278797 10.250000 translate 0.035278 -0.035278 scale start_ol 4572 3137 moveto 3439 3137 lineto @@ -2151,14 +2151,14 @@ [] 0 sd 0 slj 0 slc -n 6.000000 7.000000 m 7.000000 7.000000 6.000000 9.000000 7.000000 9.000000 c s +n 10.000000 7.000000 m 11.000000 7.000000 10.000000 9.000000 11.000000 9.000000 c s 0.070000 slw [] 0 sd [] 0 sd 0 slj 0 slc -n 7.000000 9.000000 m 6.000000 9.000000 7.000000 11.000000 6.000000 11.000000 c s -gsave 1.983750 6.221250 translate 0.035278 -0.035278 scale +n 11.000000 9.000000 m 10.000000 9.000000 11.000000 11.000000 10.000000 11.000000 c s +gsave 3.983750 6.221250 translate 0.035278 -0.035278 scale start_ol 2368 2560 moveto 2368 2176 lineto @@ -2180,7 +2180,7 @@ 1801 2752 1994 2704 conicto 2187 2656 2368 2560 conicto end_ol grestore -gsave 2.335919 6.221250 translate 0.035278 -0.035278 scale +gsave 4.335919 6.221250 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -2198,7 +2198,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave 2.583180 6.221250 translate 0.035278 -0.035278 scale +gsave 4.583180 6.221250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -2223,7 +2223,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave 2.977806 6.221250 translate 0.035278 -0.035278 scale +gsave 4.977806 6.221250 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -2256,7 +2256,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave 3.369935 6.221250 translate 0.035278 -0.035278 scale +gsave 5.369935 6.221250 translate 0.035278 -0.035278 scale start_ol 896 3456 moveto 896 2688 lineto @@ -2278,7 +2278,7 @@ 448 3456 lineto 896 3456 lineto end_ol grestore -gsave 3.619702 6.221250 translate 0.035278 -0.035278 scale +gsave 5.619702 6.221250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -2303,7 +2303,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave -3.766250 12.211906 translate 0.035278 -0.035278 scale +gsave -5.766250 12.221250 translate 0.035278 -0.035278 scale start_ol 2368 2560 moveto 2368 2176 lineto @@ -2325,7 +2325,7 @@ 1801 2752 1994 2704 conicto 2187 2656 2368 2560 conicto end_ol grestore -gsave -3.414081 12.211906 translate 0.035278 -0.035278 scale +gsave -5.414081 12.221250 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -2346,7 +2346,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave -3.021952 12.211906 translate 0.035278 -0.035278 scale +gsave -5.021952 12.221250 translate 0.035278 -0.035278 scale start_ol 896 384 moveto 896 -1024 lineto @@ -2372,7 +2372,7 @@ 1975 320 2171 592 conicto 2368 865 2368 1344 conicto end_ol grestore -gsave -2.614833 12.211906 translate 0.035278 -0.035278 scale +gsave -4.614833 12.221250 translate 0.035278 -0.035278 scale start_ol 1542 -238 moveto 1360 -726 1187 -875 conicto @@ -2390,7 +2390,7 @@ 2688 2688 lineto 1542 -238 lineto end_ol grestore -gsave 2.225000 14.211906 translate 0.035278 -0.035278 scale +gsave 4.225000 14.221250 translate 0.035278 -0.035278 scale start_ol 896 384 moveto 896 -1024 lineto @@ -2416,7 +2416,7 @@ 1975 320 2171 592 conicto 2368 865 2368 1344 conicto end_ol grestore -gsave 2.632119 14.211906 translate 0.035278 -0.035278 scale +gsave 4.632119 14.221250 translate 0.035278 -0.035278 scale start_ol 448 1040 moveto 448 2688 lineto @@ -2436,7 +2436,7 @@ 923 -64 685 217 conicto 448 499 448 1040 conicto end_ol grestore -gsave 3.036733 14.211906 translate 0.035278 -0.035278 scale +gsave 5.036733 14.221250 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -2468,7 +2468,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave 3.368918 14.211906 translate 0.035278 -0.035278 scale +gsave 5.368918 14.221250 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto @@ -2488,7 +2488,7 @@ 2217 2752 2452 2471 conicto 2688 2191 2688 1646 conicto end_ol grestore -gsave -3.766250 17.221250 translate 0.035278 -0.035278 scale +gsave -5.766250 17.221250 translate 0.035278 -0.035278 scale start_ol 2368 2560 moveto 2368 2176 lineto @@ -2510,7 +2510,7 @@ 1801 2752 1994 2704 conicto 2187 2656 2368 2560 conicto end_ol grestore -gsave -3.414081 17.221250 translate 0.035278 -0.035278 scale +gsave -5.414081 17.221250 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -2531,7 +2531,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave -3.021952 17.221250 translate 0.035278 -0.035278 scale +gsave -5.021952 17.221250 translate 0.035278 -0.035278 scale start_ol 896 384 moveto 896 -1024 lineto @@ -2557,7 +2557,7 @@ 1975 320 2171 592 conicto 2368 865 2368 1344 conicto end_ol grestore -gsave -2.614833 17.221250 translate 0.035278 -0.035278 scale +gsave -4.614833 17.221250 translate 0.035278 -0.035278 scale start_ol 1542 -238 moveto 1360 -726 1187 -875 conicto @@ -2575,7 +2575,7 @@ 2688 2688 lineto 1542 -238 lineto end_ol grestore -gsave 2.225000 19.211906 translate 0.035278 -0.035278 scale +gsave 4.225000 19.221250 translate 0.035278 -0.035278 scale start_ol 896 384 moveto 896 -1024 lineto @@ -2601,7 +2601,7 @@ 1975 320 2171 592 conicto 2368 865 2368 1344 conicto end_ol grestore -gsave 2.632119 19.211906 translate 0.035278 -0.035278 scale +gsave 4.632119 19.221250 translate 0.035278 -0.035278 scale start_ol 448 1040 moveto 448 2688 lineto @@ -2621,7 +2621,7 @@ 923 -64 685 217 conicto 448 499 448 1040 conicto end_ol grestore -gsave 3.036733 19.211906 translate 0.035278 -0.035278 scale +gsave 5.036733 19.221250 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -2653,7 +2653,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave 3.368918 19.211906 translate 0.035278 -0.035278 scale +gsave 5.368918 19.221250 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto @@ -2677,7 +2677,7 @@ [1.000000 0.400000 0.200000 0.400000] 0 sd [0.400000 0.160000 0.080000 0.160000] 0 sd 0 slc -n 6.000000 22.000000 m 6.000000 24.000000 l s +n 10.000000 22.000000 m 10.000000 24.000000 l s 0.150000 slw [0.400000 0.160000 0.080000 0.160000] 0 sd [0.400000 0.160000 0.080000 0.160000] 0 sd @@ -2687,5 +2687,5 @@ [0.400000 0.160000 0.080000 0.160000] 0 sd [0.400000 0.160000 0.080000 0.160000] 0 sd 0 slc -n -6.000000 20.000000 m -6.000000 24.000000 l s +n -10.000000 20.000000 m -10.000000 24.000000 l s showpage diff -r b59d31966d7d -r 8ef81ff8cb52 figures/gcc-repository.pdf Binary file figures/gcc-repository.pdf has changed diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tailcall.dia Binary file figures/tailcall.dia has changed diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tailcall.eps --- a/figures/tailcall.eps Mon Feb 08 03:50:27 2010 +0900 +++ b/figures/tailcall.eps Fri Feb 12 13:10:57 2010 +0900 @@ -1,11 +1,11 @@ %!PS-Adobe-2.0 EPSF-2.0 %%Title: /home/kent/WorkSpace/Mercurial/master-paper/figures/tailcall.dia %%Creator: Dia v0.97 -%%CreationDate: Sun Jan 31 15:22:48 2010 +%%CreationDate: Fri Feb 12 01:40:49 2010 %%For: kent %%Orientation: Portrait %%Magnification: 1.0000 -%%BoundingBox: 0 0 442 289 +%%BoundingBox: 0 0 442 290 %%BeginSetup %%EndSetup %%EndComments @@ -487,19 +487,19 @@ end_ol grestore gsave 1.036185 9.687500 translate 0.035278 -0.035278 scale start_ol -1696 3047 moveto -1042 1280 lineto -2352 1280 lineto -1696 3047 lineto -1424 3520 moveto -1970 3520 lineto -3328 0 lineto -2827 0 lineto -2502 896 lineto -897 896 lineto -572 0 lineto -64 0 lineto -1424 3520 lineto +320 3520 moveto +827 3520 lineto +1694 2211 lineto +2565 3520 lineto +3072 3520 lineto +1951 1830 lineto +3136 0 lineto +2633 0 lineto +1659 1497 lineto +649 0 lineto +128 0 lineto +1406 1879 lineto +320 3520 lineto end_ol grestore gsave 4.700000 9.687500 translate 0.035278 -0.035278 scale start_ol @@ -587,34 +587,16 @@ end_ol grestore gsave 6.086185 9.687500 translate 0.035278 -0.035278 scale start_ol -960 1728 moveto -960 384 lineto -1696 384 lineto -2071 384 2251 550 conicto -2432 716 2432 1057 conicto -2432 1401 2251 1564 conicto -2071 1728 1696 1728 conicto -960 1728 lineto -960 3136 moveto -960 2112 lineto -1639 2112 lineto -1975 2112 2139 2238 conicto -2304 2365 2304 2624 conicto -2304 2881 2139 3008 conicto -1975 3136 1639 3136 conicto -960 3136 lineto -448 3520 moveto -1673 3520 lineto -2222 3520 2519 3300 conicto -2816 3080 2816 2674 conicto -2816 2360 2658 2174 conicto -2500 1989 2193 1943 conicto -2549 1866 2746 1621 conicto -2944 1376 2944 1009 conicto -2944 526 2625 263 conicto -2306 0 1718 0 conicto -448 0 lineto -448 3520 lineto +-64 3520 moveto +466 3520 lineto +1476 2072 lineto +2479 3520 lineto +3008 3520 lineto +1728 1676 lineto +1728 0 lineto +1216 0 lineto +1216 1676 lineto +-64 3520 lineto end_ol grestore gsave 11.550000 9.687500 translate 0.035278 -0.035278 scale start_ol @@ -702,27 +684,19 @@ end_ol grestore gsave 12.936185 9.687500 translate 0.035278 -0.035278 scale start_ol -3136 3264 moveto -3136 2752 lineto -2892 2977 2616 3088 conicto -2340 3200 2030 3200 conicto -1418 3200 1093 2829 conicto -768 2459 768 1759 conicto -768 1061 1093 690 conicto -1418 320 2030 320 conicto -2340 320 2616 431 conicto -2892 543 3136 768 conicto -3136 256 lineto -2882 96 2599 16 conicto -2316 -64 2000 -64 conicto -1189 -64 722 424 conicto -256 913 256 1759 conicto -256 2607 722 3095 conicto -1189 3584 2000 3584 conicto -2320 3584 2603 3504 conicto -2887 3424 3136 3264 conicto +256 3520 moveto +3008 3520 lineto +3008 3155 lineto +793 384 lineto +3072 384 lineto +3072 0 lineto +192 0 lineto +192 365 lineto +2417 3136 lineto +256 3136 lineto +256 3520 lineto end_ol grestore -gsave 6.653750 16.590000 translate 0.035278 -0.035278 scale +gsave 6.653750 16.590050 translate 0.035278 -0.035278 scale start_ol 960 3136 moveto 960 384 lineto @@ -741,7 +715,7 @@ 448 0 lineto 448 3520 lineto end_ol grestore -gsave 7.145784 16.590000 translate 0.035278 -0.035278 scale +gsave 7.145784 16.590050 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -762,10 +736,10 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave 7.537913 16.590000 translate 0.035278 -0.035278 scale +gsave 7.537913 16.590050 translate 0.035278 -0.035278 scale start_ol end_ol grestore -gsave 7.740220 16.590000 translate 0.035278 -0.035278 scale +gsave 7.740220 16.590050 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -786,7 +760,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave 8.132349 16.590000 translate 0.035278 -0.035278 scale +gsave 8.132349 16.590050 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto @@ -806,7 +780,7 @@ 2217 2752 2452 2471 conicto 2688 2191 2688 1646 conicto end_ol grestore -gsave 8.536963 16.590000 translate 0.035278 -0.035278 scale +gsave 8.536963 16.590050 translate 0.035278 -0.035278 scale start_ol 448 3712 moveto 896 3712 lineto @@ -814,7 +788,7 @@ 448 0 lineto 448 3712 lineto end_ol grestore -gsave 8.714292 16.590000 translate 0.035278 -0.035278 scale +gsave 8.714292 16.590050 translate 0.035278 -0.035278 scale start_ol 1542 -238 moveto 1360 -726 1187 -875 conicto @@ -832,10 +806,10 @@ 2688 2688 lineto 1542 -238 lineto end_ol grestore -gsave 6.796250 17.390000 translate 0.035278 -0.035278 scale +gsave 6.796250 17.390050 translate 0.035278 -0.035278 scale start_ol end_ol grestore -gsave 6.998557 17.390000 translate 0.035278 -0.035278 scale +gsave 6.998557 17.390050 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -853,7 +827,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave 7.245818 17.390000 translate 0.035278 -0.035278 scale +gsave 7.245818 17.390050 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -878,7 +852,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave 7.640444 17.390000 translate 0.035278 -0.035278 scale +gsave 7.640444 17.390050 translate 0.035278 -0.035278 scale start_ol 896 3456 moveto 896 2688 lineto @@ -900,7 +874,7 @@ 448 3456 lineto 896 3456 lineto end_ol grestore -gsave 7.890211 17.390000 translate 0.035278 -0.035278 scale +gsave 7.890211 17.390050 translate 0.035278 -0.035278 scale start_ol 448 1040 moveto 448 2688 lineto @@ -920,7 +894,7 @@ 923 -64 685 217 conicto 448 499 448 1040 conicto end_ol grestore -gsave 8.294825 17.390000 translate 0.035278 -0.035278 scale +gsave 8.294825 17.390050 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -938,7 +912,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave 8.547089 17.390000 translate 0.035278 -0.035278 scale +gsave 8.547089 17.390050 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tailcall.pdf Binary file figures/tailcall.pdf has changed diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tree-example.dia Binary file figures/tree-example.dia has changed diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tree-example.eps --- a/figures/tree-example.eps Mon Feb 08 03:50:27 2010 +0900 +++ b/figures/tree-example.eps Fri Feb 12 13:10:57 2010 +0900 @@ -1,7 +1,7 @@ %!PS-Adobe-2.0 EPSF-2.0 %%Title: /home/kent/WorkSpace/Mercurial/master-paper/figures/tree-example.dia %%Creator: Dia v0.97 -%%CreationDate: Fri Feb 5 22:58:16 2010 +%%CreationDate: Fri Feb 12 01:36:35 2010 %%For: kent %%Orientation: Portrait %%Magnification: 1.0000 @@ -139,7 +139,7 @@ 0 slj [] 0 sd n 0.000000 8.000000 1.000000 1.000000 0 360 ellipse cp s -gsave -0.912500 7.811906 translate 0.035278 -0.035278 scale +gsave -0.888750 7.811906 translate 0.035278 -0.035278 scale start_ol 1792 3712 moveto 1792 3328 lineto @@ -161,7 +161,7 @@ 925 3712 1374 3712 conicto 1792 3712 lineto end_ol grestore -gsave -0.687712 7.811906 translate 0.035278 -0.035278 scale +gsave -0.663962 7.811906 translate 0.035278 -0.035278 scale start_ol 448 1040 moveto 448 2688 lineto @@ -181,7 +181,7 @@ 923 -64 685 217 conicto 448 499 448 1040 conicto end_ol grestore -gsave -0.283098 7.811906 translate 0.035278 -0.035278 scale +gsave -0.259348 7.811906 translate 0.035278 -0.035278 scale start_ol 2688 1646 moveto 2688 0 lineto @@ -201,7 +201,7 @@ 2217 2752 2452 2471 conicto 2688 2191 2688 1646 conicto end_ol grestore -gsave 0.121516 7.811906 translate 0.035278 -0.035278 scale +gsave 0.145266 7.811906 translate 0.035278 -0.035278 scale start_ol 2368 2560 moveto 2368 2176 lineto @@ -223,21 +223,17 @@ 1801 2752 1994 2704 conicto 2187 2656 2368 2560 conicto end_ol grestore -gsave 0.473685 7.811906 translate 0.035278 -0.035278 scale +gsave 0.497435 7.811906 translate 0.035278 -0.035278 scale start_ol -1696 3047 moveto -1042 1280 lineto -2352 1280 lineto -1696 3047 lineto -1424 3520 moveto -1970 3520 lineto -3328 0 lineto -2827 0 lineto -2502 896 lineto -897 896 lineto -572 0 lineto -64 0 lineto -1424 3520 lineto +-64 3520 moveto +3008 3520 lineto +3008 3136 lineto +1728 3136 lineto +1728 0 lineto +1216 0 lineto +1216 3136 lineto +-64 3136 lineto +-64 3520 lineto end_ol grestore gsave -0.793750 8.611906 translate 0.035278 -0.035278 scale start_ol @@ -868,7 +864,7 @@ 0 slj [] 0 sd n 10.500000 16.000000 1.000000 1.000000 0 360 ellipse cp s -gsave 5.843750 15.811906 translate 0.035278 -0.035278 scale +gsave 5.843750 15.821250 translate 0.035278 -0.035278 scale start_ol 896 3456 moveto 896 2688 lineto @@ -890,7 +886,7 @@ 448 3456 lineto 896 3456 lineto end_ol grestore -gsave 6.093517 15.811906 translate 0.035278 -0.035278 scale +gsave 6.093517 15.821250 translate 0.035278 -0.035278 scale start_ol 1984 2304 moveto 1912 2337 1828 2352 conicto @@ -908,7 +904,7 @@ 1917 2752 1982 2752 conicto 1984 2304 lineto end_ol grestore -gsave 6.355768 15.811906 translate 0.035278 -0.035278 scale +gsave 6.355768 15.821250 translate 0.035278 -0.035278 scale start_ol 448 1040 moveto 448 2688 lineto @@ -928,7 +924,7 @@ 923 -64 685 217 conicto 448 499 448 1040 conicto end_ol grestore -gsave 6.760382 15.811906 translate 0.035278 -0.035278 scale +gsave 6.760382 15.821250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -953,7 +949,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave 5.706250 16.611906 translate 0.035278 -0.035278 scale +gsave 5.706250 16.621250 translate 0.035278 -0.035278 scale start_ol 2368 1344 moveto 2368 1823 2171 2095 conicto @@ -979,7 +975,7 @@ 896 3712 lineto 896 2304 lineto end_ol grestore -gsave 6.113369 16.611906 translate 0.035278 -0.035278 scale +gsave 6.113369 16.621250 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -1000,7 +996,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave 6.505498 16.611906 translate 0.035278 -0.035278 scale +gsave 6.505498 16.621250 translate 0.035278 -0.035278 scale start_ol 2176 2304 moveto 2176 3712 lineto @@ -1026,7 +1022,7 @@ 1096 2368 900 2095 conicto 704 1823 704 1344 conicto end_ol grestore -gsave 6.912618 16.611906 translate 0.035278 -0.035278 scale +gsave 6.912618 16.621250 translate 0.035278 -0.035278 scale start_ol 1542 -238 moveto 1360 -726 1187 -875 conicto @@ -1044,7 +1040,7 @@ 2688 2688 lineto 1542 -238 lineto end_ol grestore -gsave 9.738750 15.811906 translate 0.035278 -0.035278 scale +gsave 9.738750 15.821250 translate 0.035278 -0.035278 scale start_ol 1792 3712 moveto 1792 3328 lineto @@ -1066,7 +1062,7 @@ 925 3712 1374 3712 conicto 1792 3712 lineto end_ol grestore -gsave 9.963538 15.811906 translate 0.035278 -0.035278 scale +gsave 9.963538 15.821250 translate 0.035278 -0.035278 scale start_ol 1622 1344 moveto 1104 1344 904 1225 conicto @@ -1099,7 +1095,7 @@ 1927 2752 2211 2444 conicto 2496 2137 2496 1513 conicto end_ol grestore -gsave 10.355667 15.811906 translate 0.035278 -0.035278 scale +gsave 10.355667 15.821250 translate 0.035278 -0.035278 scale start_ol 448 3712 moveto 896 3712 lineto @@ -1107,7 +1103,7 @@ 448 0 lineto 448 3712 lineto end_ol grestore -gsave 10.532996 15.811906 translate 0.035278 -0.035278 scale +gsave 10.532996 15.821250 translate 0.035278 -0.035278 scale start_ol 2112 2560 moveto 2112 2176 lineto @@ -1139,7 +1135,7 @@ 1509 2752 1721 2704 conicto 1933 2656 2112 2560 conicto end_ol grestore -gsave 10.865180 15.811906 translate 0.035278 -0.035278 scale +gsave 10.865180 15.821250 translate 0.035278 -0.035278 scale start_ol 2752 1480 moveto 2752 1280 lineto @@ -1164,7 +1160,7 @@ 753 1964 719 1597 conicto 2304 1600 lineto end_ol grestore -gsave 9.706250 16.611906 translate 0.035278 -0.035278 scale +gsave 9.706250 16.621250 translate 0.035278 -0.035278 scale start_ol 2368 1344 moveto 2368 1823 2171 2095 conicto @@ -1190,7 +1186,7 @@ 896 3712 lineto 896 2304 lineto end_ol grestore -gsave 10.113369 16.611906 translate 0.035278 -0.035278 scale +gsave 10.113369 16.621250 translate 0.035278 -0.035278 scale start_ol 1473 2368 moveto 1117 2368 910 2094 conicto @@ -1211,7 +1207,7 @@ 256 2005 579 2378 conicto 902 2752 1472 2752 conicto end_ol grestore -gsave 10.505498 16.611906 translate 0.035278 -0.035278 scale +gsave 10.505498 16.621250 translate 0.035278 -0.035278 scale start_ol 2176 2304 moveto 2176 3712 lineto @@ -1237,7 +1233,7 @@ 1096 2368 900 2095 conicto 704 1823 704 1344 conicto end_ol grestore -gsave 10.912618 16.611906 translate 0.035278 -0.035278 scale +gsave 10.912618 16.621250 translate 0.035278 -0.035278 scale start_ol 1542 -238 moveto 1360 -726 1187 -875 conicto @@ -2314,7 +2310,7 @@ 448 3136 lineto 448 3712 lineto end_ol grestore -gsave -0.820000 13.733469 translate 0.035278 -0.035278 scale +gsave -0.820000 13.743750 translate 0.035278 -0.035278 scale start_ol 1415 2700 moveto 1415 1659 lineto @@ -2330,7 +2326,7 @@ 1017 2700 lineto 1415 2700 lineto end_ol grestore -gsave -0.500301 13.733469 translate 0.035278 -0.035278 scale +gsave -0.500301 13.743750 translate 0.035278 -0.035278 scale start_ol 1415 2700 moveto 1415 1659 lineto diff -r b59d31966d7d -r 8ef81ff8cb52 figures/tree-example.pdf Binary file figures/tree-example.pdf has changed diff -r b59d31966d7d -r 8ef81ff8cb52 gcc.tex --- a/gcc.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/gcc.tex Fri Feb 12 13:10:57 2010 +0900 @@ -15,7 +15,7 @@ GCCはコンパイルだけでなく、出力したアセンブラのアセンブル、リンクまで 行い、最終的に実行ファイルを出力する。このコンパイル、アセンブル、リン クはそれぞれcc1, as, collect2というプログラムが行っており、GCCは実際に -はその統括をしているだけである。 +はそれらを統括しているだけである。 言語に関する処理はcc1だけである。ここではこのプログラムがどのようにソ ースコードをアセンブラに変換するかを説明する。 @@ -31,7 +31,7 @@ \begin{center} \includegraphics[width=.8\textwidth]{figures/gcc-flow.eps} \end{center} - \caption{GCC} + \caption{cc1でのデータフロー(Generic, GIMPLE, RTL)} \label{fig:gcc-flow} \end{figure} @@ -51,7 +51,7 @@ 構文木がプログラムをデータ構造として表す様子を図 \ref{fig:tree-example}に示した。この図はコード\ref{code:tree-example} -の関数\verb|funcA|を解析した結果を構文木で表現している。 +の関数\verb|funcT|を解析した結果を構文木で表現している。 \begin{figure}[htpb] \lstinputlisting @@ -79,21 +79,21 @@ \subsection{ミドルエンドとRTL} GCCは構文木GIMPLEの生成後、このGIMPLEを解析しながらRTLと呼ばれる中間コ -ードを生成する。このRTLはアセンブラとほぼ同等の命令列を表現可能であり -、どのアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存 -はないため、このミドルエンドは言語にもアーキテクチャにも依存しない、全 -てのGCCコンパイラに共通のルーチンとなっている。 +ードを生成する。RTLはアセンブラとほぼ同等の命令列を表現可能であり、ど +のアーキテクチャでも同じように扱われる。また、GIMPLEにも言語の依存はな +いため、ミドルエンドは言語にもアーキテクチャにも依存しない、全ての GCC +コンパイラに共通のルーチンとなっている。 しかしながらアーキテクチャに依存した形にRTLを作ることは可能であり、特 に最適化に関するRTL生成はアーキテクチャ依存であることが多い。ただしそ -の場合はアーキテクチャが対応してるか否かを判別するため、次項に紹介する +の場合はアーキテクチャが対応してるか否かを判別するために次項に紹介する Machine Descriptionが使われるため、共通のミドルエンドが使われることに 変わりはない。 -RTLはプログラム上は構造体として扱われるが、デバグ表示や次のバックエン -ドで使うMachine Descriptionのため、S式を用いた表現が用いられている。 -例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表現 -は以下のようになる。 +RTLはプログラム上はツリー構造として扱われるが、デバッグ表示や次のバッ +クエンドで使うMachine Descriptionのため、S式を用いた表現が用いられてい +る。例として、ある仮想レジスタに直接値20を乗算する命令を表すRTLのS式表 +現は以下のようになる。 \begin{lstlisting}[caption=レジスタに20を乗算する命令のRTL表現例, label=code:rtl-example,language=Lisp] @@ -111,28 +111,29 @@ \subsection{バックエンドとMachine Description} バックエンドでは、ミドルエンドで生成されたRTLを元にアセンブラを出力し -ている。このバックエンドでは必然的にターゲットとするアーキテクチャによ -り処理が異なるため、このバックエンドはアーキテクチャ毎に用意されること -になる。 +ている。この処理は必然的にターゲットとするアーキテクチャにより処理が異 +なるため、バックエンドはアーキテクチャ毎に用意されることになる。 + アーキテクチャ毎に異なるRTLの変換規則を記述したものがMachine Description（以下md）である。 mdはGCCの対応する全てのアーキテクチャに それぞれ用意されており、バックエンドはこれを元にアセンブラを生成する。 -このmdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する -必要がある。 +mdはRTLと同じくS式で表現され、RTLの変換のために次の要素を定義する必要 +がある。 \begin{itemize} \item その変換規則の名前 - GCCのプログラムから関数として呼び出すための名前である + GCCのプログラムから関数として呼び出すための名前である。 \item 変換するRTLの構造（パターンマッチ） - この規則がどのようなRTLを変換できるかを表す + この規則がどのようなRTLを変換できるかを表す。 \item 変換する条件 - 上記のパターンだけでは判別できない時の追加条件をCの構文で記述 + 上記のパターンだけでは判別できない時の追加条件をCの構文で記述する。 \item 出力するアセンブラ - Cの文字列か、もしくは文字列を出力するCの構文 + アセンブラ文字列か、もしくはアセンブラ文字列を出力するCの構文を記 + 述する。 \end{itemize} 例としてARMアーキテクチャにおけるmdを一つ、コード @@ -141,13 +142,13 @@ 力する。 2行目の要素がマッチするRTLのパターンで、コード\ref{code:rtl-example}と 形が似ていることが分かる。 -3行目が条件である。バックエンドプログラムの変数などをチェックしている。 -そして4行目が出力するアセンブラである。ここでは``\verb|%?|''や +5行目が条件である。バックエンドプログラムの変数などをチェックしている。 +そして6行目が出力するアセンブラである。ここでは``\verb|%?|''や ``\verb|%2|''を使い、 printf関数と似たような書式変換を行っている。 \begin{lstlisting}[caption=ARMでのMachine Descriptionの例 （コード\ref{code:rtl-example}をアセンブラに変換）, - label=code:md-example,language=Lisp] + label=code:md-example,language=Lisp,numbers=left] (define_insn "*arm_mulsi3" [(set (match_operand:SI 0 "s_register_operand" "=&r,&r") (mult:SI (match_operand:SI 2 "s_register_operand" "r,r") @@ -161,10 +162,10 @@ 最適化はGCCの中でももっとも重要な機能の一つといえる。 様々な最適化の手法がGCCにおいて実装され、実用化されている。 -GCCではこの最適化は2つフェーズに分類される。 +GCCでは最適化は2つフェーズに分類される。 一つはGIMPLEを対象とした最適化である。 -このGIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どの -コンパイラにおいてもこの最適化を適用することができる。 +GIMPLEは、アーキテクチャはもちろん言語仕様にも依存しないため、どのコン +パイラにおいてもこの最適化を適用することができる。 この最適化はミドルエンドで行われる。 もう一つはRTLを対象とした最適化である。 diff -r b59d31966d7d -r 8ef81ff8cb52 implementation.tex --- 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 - diff -r b59d31966d7d -r 8ef81ff8cb52 introduction.tex --- a/introduction.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/introduction.tex Fri Feb 12 13:10:57 2010 +0900 @@ -15,8 +15,8 @@ 化する傾向にある。また家電製品のデジタル化も進み、組み込みシステムの需 要も増大している。 -それにともないハードウェアはムーアの法則よろしく驚異的な進歩を遂げ、近 -年はCPUのマルチコア化が進み、また新たな段階を築こうとしている。 +それにともないハードウェアは驚異的な進歩を遂げ、近年はCPUのマルチコア +化が進み、また新たな段階を築こうとしている。 ハードウェアの進歩に対し、ソフトウェアの開発に用いられる記述言語は、オ ブジェクト指向プログラミングの発明・導入やデザインパターンに見られる技 @@ -24,54 +24,74 @@ %しかしながら90年代以降、言語その物に対する大きな変化は見られない。 オブジェクト指向を主としたJavaはその有用性が認められ多くのシステム開発 に取り入られている。 -しかしその反面、Cなどの低レベルな言語による記述に比べてこれらの技術は -余分な条件判断やメモリアクセスを増やしてしまう。そのため軽量かつ高速な -応答が要求される Real-time処理や組み込み用途には適さない。 +しかしその反面、Javaではガベージコレクタや実行時コンパイルにより、余分 +な処理が必要となる。そのため軽量かつ高速な応答が要求される Real-time処 +理や組込み用途には適さない。 +%しかしその反面、Cなどの低レベルな言語による記述に比べてこれらの技術は +%余分な条件判断やメモリアクセスを増やしてしまう。そのため軽量かつ高速な +%応答が要求される Real-time処理や組み込み用途には適さない。 -またCellに見られるような複雑なアーキテクチャをもつマシンではプログラミ -ング自体も複雑になる。Cで記述されたプログラムからアーキテクチャに直接 -関わる命令 （DMAやシグナル）を使用するのでは、高級言語の設計思想と矛盾す -るともみられる。 +%またCellに見られるような複雑なアーキテクチャをもつマシンではプログラ +%ミング自体も複雑になる。Cで記述されたプログラムからアーキテクチャに直 +%接関わる命令 （DMAやシグナル）を使用するのでは、高級言語の設計思想と +%矛盾するともみられる。 +またPlayStation3にはCell Broadband Engineという特殊なCPUが採用され注目 +されている。しかしこの様な複雑なアーキテクチャを持つマシンではプログラ +ミング自体も複雑になる。Cで記述されたプログラムからアーキテクチャに直 +接関わる命令 （DMAやシグナル）を使用するのでは、高級言語の設計思想と矛 +盾するともみられる。 + 大規模システムにおけるバグの存在も深刻な問題である。 テストファーストな開発スタイルなどで工学的なアプローチからバグの抑制が 試みられているが、完全な排除は難しい。数学的なアプローチから無矛盾を証 明する技術の研究も進んでいるが、現在のスタックベースのプログラミングは 状態数が膨大になり、実用化された例は少ない。しかしマルチコアの台頭によ -り並列プログラミングの必要性も高まっており、今後より検証の必要性が増す -と考えられる。 +り並列プログラミングの必要性も高まっており、今後はより検証の必要性が増 +すと考えられる。 -ハードウェアの進化や数学的検証にソフトウェアが対応するためにはこれまで -とは違う新たな視点を持ったプログラミング言語が望ましい。 +ハードウェアの進化や数学的検証にソフトウェアが対応するためには、これま +でとは違う新たな視点を持ったプログラミング言語が望ましい。 しかし既存のソフトウェアやシステムは膨大な数に上り、これらを新しい言語 に書き換えるのは無理がある。新しい言語は古い言語との互換性が必須である。 -我々はこれらの問題に取り組むため、Continuation based Cという言語を提案 -している。Continuation based C（以下CbC）はCからサブルーチンやループ構造 -を除いたCの下位言語であり、ハードウェアの記述、また記述したプログラム -の検証などを目的としている。 +我々はこれらの問題に取り組むため、Continuation based C（以下CbC）とい +う言語を提案している。Continuationとはプログラムの次の実行処理を表現す +る制御構造で、継続とも呼ばれている\cite{;}。CbCではCからサブルーチンや +ループ制御を除き、代わりに継続をベースとした実行制御を行う。この特徴か +ら、CbCはCの下位言語と考ることができ、ハードウェアの記述や記述したプロ +グラムの検証などを目的として設計されている。 +%我々はこれらの問題に取り組むため、Continuation based Cという言語を提案 +%している。Continuation based C（以下CbC）はCからサブルーチンやループ構 +%造を除いたCの下位言語であり、ハードウェアの記述、また記述したプログラ +%ムの検証などを目的としている。 -これまでCbCのコンパイルにはmicro-cをベースとしたコンパイラとGNUコンパ -イラコレクション（以下gcc）をベースとしたコンパイラが用いられてきた。 -しかしgccにはバグや当初の期待ほど速度がでないという問題があり、研究段 -階であるCbC言語自体にも仕様の変更などがあった。 +%これまでCbCのコンパイルには、micro-cをベースとしたコンパイラとGNUコン +%パイラコレクション（以下GCC）をベースとしたコンパイラが用いられてきた。 +%しかしGCCにはバグや当初の期待ほど速度がでないという問題があり、研究段 +%階であるCbC言語自体にも仕様の変更などがあった。 +これまでCbCのコンパイルには、micro-cをベースとしたコンパイラが用いられ +てきた。加えて2008年の研究においてGCCをベースとしたCbCコンパイラが開発 +され、継続処理の実装が行われた。 -本論文ではGCCベースのCbCコンパイラの問題の洗い出しとその問題の改善を行 -い、実用レベルのCbCプログラムの動作を目指す。また、CbCを用いたプログラ -ムの例として現在開発中のCbCベースTaskManager の紹介を行う。 -最後に実装したgccベースコンパイラの評価としてmicro-cベースコンパイラと -の速度比較を行い、 同じくTaskManager開発を通してのCbCによるプログラミ -ングの記述性についても評価・考察を行う。 +%TODO: taskmanager +本論文ではGCCベースのコンパイラに残るCbCの機能の実装を行い、実用的な +CbCプログラムの動作を目指す。 +%本論文ではGCCベースのCbCコンパイラの問題の洗い出しとその問題の改善を行 +%い、実用レベルのCbCプログラムの動作を目指す。 +%また、CbCを用いたプログラムの例として現在開発中のCbCベースTaskManager +%の紹介を行う。 +また、実装したGCCベースコンパイラの評価としてmicro-cベースコンパイラと +の速度比較を行い、GCCの開発リリースに合わせるためのメンテナンス手法に +ついても考察する。 \section{論文構成} -%\ref{chp:cbc}にてContinuation based Cの要求仕様と詳細について説明する。 -%\ref{chp:impl}章ではgccへの実装方法を説明する。 次章以降、本論文では本研究での成果を報告する。 diff -r b59d31966d7d -r 8ef81ff8cb52 master_paper.tex --- a/master_paper.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/master_paper.tex Fri Feb 12 13:10:57 2010 +0900 @@ -10,7 +10,6 @@ \usepackage{paralist} %% inlineのenumerate \usepackage{caption} -% TODO: % captionパッケージは空のファイル ragged2e.sty everysel.sty % を作っておかないとフォントが破滅する \usepackage{subfig} % なかでcaptionを呼び出してる @@ -111,6 +110,14 @@ %発表履歴 \input{presentations.tex} + + +\lstset{ + basicstyle=\scriptsize\ttfamily,% + commentstyle=\scriptsize\itshape\rmfamily,% +}% + + %付録 \appendix \input{appendix.tex} diff -r b59d31966d7d -r 8ef81ff8cb52 presentations.tex --- a/presentations.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/presentations.tex Fri Feb 12 13:10:57 2010 +0900 @@ -1,12 +1,14 @@ \chapter*{発表文献} \addcontentsline{toc}{chapter}{発表文献} -Continuation based CコンパイラのGCC-4.2による実装 \\ -与儀健人, 河野真治, ~~ -情報処理学会システムソフトウェアとオペレーティング・システム研究会 -(OS), April, 2008. +\begin{description} + \item [Continuation based CコンパイラのGCC-4.2による実装] \hfill \\ + 与儀健人, 河野真治. \\ + 情報処理学会システムソフトウェアとオペレーティング・システム研究会 + (OS), April, 2008. + \item [組み込み向け低レベル言語 CbC の GCC による実装] \hfill \\ + 与儀健人, 河野真治. \\ + 第6回ディペンダブルシステムワークショップ, July, 2008 +\end{description} -組み込み向け低レベル言語 CbC の GCC による実装 \\ -与儀健人, 河野真治, ~~ -第6回ディペンダブルシステムワークショップ, July, 2008 diff -r b59d31966d7d -r 8ef81ff8cb52 sources/cbcreturn.cbc --- a/sources/cbcreturn.cbc Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/cbcreturn.cbc Fri Feb 12 13:10:57 2010 +0900 @@ -1,12 +1,14 @@ -code cs(RET_FUNC ret) +code cs(code (*ret)(int)) { goto ret(2); } int funcB() { + code (*ret)(int); + ret = __return; /* do something. */ - goto cs(__return); + goto cs(ret); /* never reached. */ return -1; diff -r b59d31966d7d -r 8ef81ff8cb52 sources/cbcreturn2.cbc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/cbcreturn2.cbc Fri Feb 12 13:10:57 2010 +0900 @@ -0,0 +1,10 @@ +int funcB() +{ + code (*ret)(int); + ret = __return; + /* do something. */ + goto cs(ret); + + /* never reached. */ + return -1; +} diff -r b59d31966d7d -r 8ef81ff8cb52 sources/divider-e-gcc.asm --- a/sources/divider-e-gcc.asm Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/divider-e-gcc.asm Fri Feb 12 13:10:57 2010 +0900 @@ -1,4 +1,3 @@ - quicksort_divider_e: lwz 11,0(3) slwi 0,5,2 diff -r b59d31966d7d -r 8ef81ff8cb52 sources/divider-e-mc.asm --- a/sources/divider-e-mc.asm Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/divider-e-mc.asm Fri Feb 12 13:10:57 2010 +0900 @@ -1,4 +1,3 @@ - quicksort_divider_e: la 1,.LC22@l(31) addis 1,1,.LC22@ha diff -r b59d31966d7d -r 8ef81ff8cb52 sources/fastcall-example.c --- a/sources/fastcall-example.c Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/fastcall-example.c Fri Feb 12 13:10:57 2010 +0900 @@ -1,9 +1,9 @@ -int funcB() __attribute__((fastcall)); +int fastfunc() __attribute__((fastcall)); -int funcB(int a, int b) { +int fastfunc(int a, int b) { /* do something. */ } -void funcA() { - funcB(20, 30); +void normalfunc() { + fastfunc(20, 30); } diff -r b59d31966d7d -r 8ef81ff8cb52 sources/indirect-example.cbc --- a/sources/indirect-example.cbc Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/indirect-example.cbc Fri Feb 12 13:10:57 2010 +0900 @@ -1,8 +1,8 @@ code somesegment( . . . ) { - code (*codepoint)(); + code (*codepointer)(); /* do something */ if ( ) goto nextsegment(); else - goto (*segmentpointer)(); + goto (*codepointer)(); } diff -r b59d31966d7d -r 8ef81ff8cb52 sources/nestedcode.cbc --- a/sources/nestedcode.cbc Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/nestedcode.cbc Fri Feb 12 13:10:57 2010 +0900 @@ -1,23 +1,23 @@ int funcB() { - /* do something. */ + code (*ret)(int); - int __retval; - code __unnamed_code(int __retval0){ - __retval = __retval0; - goto __unnamed_label; + int _retval; + code _segment(int _val){ + _retval = _val; + goto _label; } if (0) { - __unnamed_label: - return __retval; + _label: + return _retval; } - __return = __unnamed_code; + __return = _segment; - goto cs(__return); + ret = __return; + /* do something. */ + goto cs(ret); /* never reached. */ return -1; } - - diff -r b59d31966d7d -r 8ef81ff8cb52 sources/scheme-cont-out.scmout --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/scheme-cont-out.scmout Fri Feb 12 13:10:57 2010 +0900 @@ -0,0 +1,24 @@ +gosh> (define (cont-test i) + (print "before") + (call/cc (lambda (k) (set! cont k))) + (print "after") + (set! i (+ 1 i)) + i) +cont-test +gosh> (cont-test 10) +before +after +11 +gosh> (cont) +after +12 +gosh> (cont) +after +13 +gosh> (cont-test 2222) +before +after +2223 +gosh> (cont) +after +2224 diff -r b59d31966d7d -r 8ef81ff8cb52 sources/scheme-cont.scm --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/scheme-cont.scm Fri Feb 12 13:10:57 2010 +0900 @@ -0,0 +1,19 @@ +(define cont #f) + +(define (cont-test i) + (print "before") + (call/cc (lambda (k) (set! cont k))) + (print "after") + (set! i (+ 1 i)) + i) + +(cont-test 1) +;(define (leaf-count/cps tree cont) +; (if (pair? tree) +; (leaf-count/cps (car tree) +; (lambda (n) +; (leaf-count/cps (cdr tree) +; (lambda (m) (cont (+ n m)))))) +; (cont 1))) +; +;(define tree '((a . b) (c . d) . e)) diff -r b59d31966d7d -r 8ef81ff8cb52 sources/setjmp.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sources/setjmp.c Fri Feb 12 13:10:57 2010 +0900 @@ -0,0 +1,42 @@ +/* +#include +#include + +void jmpfunc(jmp_buf env); +int setfunc(); +int flag=0; + +int +main(int argc, char **argv) +{ + int rtn; + flag=1; + rtn = setfunc(); + printf("rtn = %d\n", rtn); + return 0; +} + +*/ +int +setfunc() +{ + int a; + jmp_buf env; + + if (a=setjmp(env)) { + printf("it's continued! with value %d", a); + return a; + } + + jmpfunc(env); + return 0; +} + +void +jmpfunc(jmp_buf env) +{ + if (flag) { + longjmp(env, 2); + } + return; +} diff -r b59d31966d7d -r 8ef81ff8cb52 sources/tree-example.c --- a/sources/tree-example.c Mon Feb 08 03:50:27 2010 +0900 +++ b/sources/tree-example.c Fri Feb 12 13:10:57 2010 +0900 @@ -1,5 +1,5 @@ bool -funcA(char a, char *b, int n) { +funcT(char a, char *b, int n) { int i; for (i=0; i