# HG changeset patch # User Nobuyasu Oshiro # Date 1321578449 -32400 # Node ID 5dfa978ee319e02cd520722a161d0c759fb8025d # Parent 4c5a29c7bb47c92cba3d48e35ce5c479ef4aaf97 modify tex diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/figure/fastcall.graffle --- a/Paper/figure/fastcall.graffle Fri Nov 18 06:33:48 2011 +0900 +++ b/Paper/figure/fastcall.graffle Fri Nov 18 10:07:29 2011 +0900 @@ -105,24 +105,24 @@ \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720 \f0\fs24 \cf0 \ - 1 | case RID_CbC_CODE:\ - 2 | if (!typespec_ok)\ - 3 | goto out; \ - 4 | attrs_ok = true; \ - 5 | seen_type = true; \ - 6 | if (c_dialect_objc ())\ - 7 | parser->objc_need_raw_identifier = true; \ - 8 | t.kind = ctsk_resword; \ - 9 | t.spec = c_parser_peek_token (parser)->value; \ - 10 | declspecs_add_type (loc, specs, t); \ - 11 |\ - 12 | if(!TARGET_64BIT) \{\ - 13 | attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); \ - 14 | declspecs_add_attrs(specs, attrs); \ - 15 | \}\ - 16 |\ - 17 | c_parser_consume_token (parser); \ - 18 | break; } + case RID_CbC_CODE:\ + if (!typespec_ok)\ + goto out; \ + attrs_ok = true; \ + seen_type = true; \ + if (c_dialect_objc ())\ + parser->objc_need_raw_identifier = true; \ + t.kind = ctsk_resword; \ + t.spec = c_parser_peek_token (parser)->value; \ + declspecs_add_type (loc, specs, t); \ + \ + if(!TARGET_64BIT) \{\ + attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); \ + declspecs_add_attrs(specs, attrs); \ + \}\ + \ + c_parser_consume_token (parser); \ + break; } VerticalPad 0 @@ -177,7 +177,7 @@ MasterSheets ModificationDate - 2011-11-17 02:02:00 +0000 + 2011-11-18 00:01:57 +0000 Modifier Nobuyasu Oshiro NotesVisible diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.aux --- a/Paper/nobu-prosym.aux Fri Nov 18 06:33:48 2011 +0900 +++ b/Paper/nobu-prosym.aux Fri Nov 18 10:07:29 2011 +0900 @@ -1,8 +1,8 @@ \relax \newlabel{fig:cs}{{1}{1}} -\newlabel{fig:factorial}{{2}{2}} -\newlabel{fig:ir}{{3}{2}} -\newlabel{fig:continue}{{4}{2}} +\@writefile{lol}{\contentsline {lstlisting}{source/factorial.cbc}{1}} +\newlabel{fig:ir}{{2}{2}} +\newlabel{fig:continue}{{3}{2}} \bibcite{1}{1} \bibcite{2}{2} \bibcite{3}{3} @@ -10,4 +10,6 @@ \bibcite{5}{5} \bibcite{6}{6} \bibcite{7}{7} -\newlabel{fig:fastcall}{{5}{3}} +\newlabel{fig:fastcall}{{4}{3}} +\newlabel{tab:speed-mc-vs-gcc-nonopt}{{1}{3}} +\newlabel{tab:speed-mc-vs-gcc-opt}{{2}{3}} diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.dvi Binary file Paper/nobu-prosym.dvi has changed diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.log --- a/Paper/nobu-prosym.log Fri Nov 18 06:33:48 2011 +0900 +++ b/Paper/nobu-prosym.log Fri Nov 18 10:07:29 2011 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10) 18 NOV 2011 05:31 +This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10) 18 NOV 2011 10:06 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -110,91 +110,164 @@ (/usr/local/texlive/2011/texmf-dist/tex/latex/url/url.sty \Urlmuskip=\muskip10 Package: url 2006/04/12 ver 3.3 Verb mode for urls, etc. -) (./nobu-prosym.aux) +) +(/usr/local/texlive/2011/texmf-dist/tex/latex/multirow/multirow.sty +\bigstrutjot=\dimen141 +) +(./slashbox.sty +slashbox style by K.Yasuoka, May 1993. +\@slashboxa=\box51 +\@slashboxb=\box52 +\@slashboxc=\box53 +\@slashboxwd=\count102 +\@slashboxht=\count103 +\@slashsepl=\dimen142 +\@slashsepr=\dimen143 +) (/usr/local/texlive/2011/texmf-dist/tex/latex/listings/listings.sty +\lst@mode=\count104 +\lst@gtempboxa=\box54 +\lst@token=\toks16 +\lst@length=\count105 +\lst@currlwidth=\dimen144 +\lst@column=\count106 +\lst@pos=\count107 +\lst@lostspace=\dimen145 +\lst@width=\dimen146 +\lst@newlines=\count108 +\lst@lineno=\count109 +\abovecaptionskip=\skip43 +\belowcaptionskip=\skip44 +\lst@maxwidth=\dimen147 + +(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstmisc.sty +File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz) +\c@lstnumber=\count110 +\lst@skipnumbers=\count111 +\lst@framebox=\box55 +) +(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/listings.cfg +File: listings.cfg 2007/02/22 1.4 listings configuration +)) +Package: listings 2007/02/22 1.4 (Carsten Heinz) + +(./nobu-prosym.aux) \openout1 = `nobu-prosym.aux'. -LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for JY1/mc/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. -LaTeX Font Info: Checking defaults for JT1/mc/m/n on input line 38. -LaTeX Font Info: ... okay on input line 38. +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for JY1/mc/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +LaTeX Font Info: Checking defaults for JT1/mc/m/n on input line 42. +LaTeX Font Info: ... okay on input line 42. +\c@lstlisting=\count112 LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <14.4> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 93. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 97. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <14.4> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 93. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 97. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <10.95> on input line 93. +(Font) <10.95> on input line 97. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <8> on input line 93. +(Font) <8> on input line 97. LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <12> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 93. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 97. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <12> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 93. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 97. Class ipsjpapers Warning: \etitle is too wide. Break line(s) by \\ on input lin -e 93. +e 97. LaTeX Font Warning: Font shape `JT1/mc/m/sc' undefined -(Font) using `JT1/mc/m/n' instead on input line 93. +(Font) using `JT1/mc/m/n' instead on input line 97. LaTeX Font Warning: Font shape `JY1/mc/m/sc' undefined -(Font) using `JY1/mc/m/n' instead on input line 93. +(Font) using `JY1/mc/m/n' instead on input line 97. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <7> on input line 93. +(Font) <7> on input line 97. File: figure/codesegment.eps Graphic file (type eps)
-Overfull \hbox (2.42252pt too wide) in paragraph at lines 121--122 +Overfull \hbox (2.42252pt too wide) in paragraph at lines 126--127 [] [] LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 123. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 128. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 123. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 128. LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 128. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 133. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 128. -File: figure/factorial.eps Graphic file (type eps) -
[1 +(Font) Font shape `JY1/gt/m/n' tried instead on input line 133. + +LaTeX Warning: Reference `fig:factorial' on page 1 undefined on input line 146. + + +(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstlang1.sty +File: lstlang1.sty 2004/09/05 1.3 listings language file +) +(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstmisc.sty +File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz) +) +(./source/factorial.cbc [1 ] +LaTeX Font Info: Try loading font information for OMS+cmr on input line 2. + +(/usr/local/texlive/2011/texmf-dist/tex/latex/base/omscmr.fd +File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions +) +LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <9> not available +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 2. +LaTeX Font Info: Try loading font information for OML+cmr on input line 8. + +(/usr/local/texlive/2011/texmf-dist/tex/latex/base/omlcmr.fd +File: omlcmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions +) +LaTeX Font Info: Font shape `OML/cmr/m/n' in size <9> not available +(Font) Font shape `OML/cmm/m/it' tried instead on input line 8. +) File: figure/ir.eps Graphic file (type eps)
-Overfull \hbox (19.2858pt too wide) in paragraph at lines 171--172 +Overfull \hbox (19.2858pt too wide) in paragraph at lines 173--174 [] [] -LaTeX Warning: Reference `continue' on page 2 undefined on input line 210. +LaTeX Warning: Reference `continue' on page 2 undefined on input line 215. File: figure/continuation.eps Graphic file (type eps)
[2] File: figure/fastcall.eps Graphic file (type eps)
-Overfull \hbox (25.60954pt too wide) in paragraph at lines 241--242 +Overfull \hbox (12.43753pt too wide) in paragraph at lines 264--265 [] [] -[3 + +Overfull \hbox (10.40831pt too wide) in paragraph at lines 297--303 + [][] + [] + -] (./nobu-prosym.aux) +Overfull \hbox (10.40831pt too wide) in paragraph at lines 311--317 + [][] + [] + +[3] (./nobu-prosym.aux) LaTeX Font Warning: Some font shapes were not available, defaults substituted. @@ -203,12 +276,12 @@ ) Here is how much of TeX's memory you used: - 1178 strings out of 494163 - 14028 string characters out of 3160585 - 70551 words of memory out of 3000000 - 4599 multiletter control sequences out of 15000+200000 + 2579 strings out of 494163 + 34809 string characters out of 3160585 + 119661 words of memory out of 3000000 + 5965 multiletter control sequences out of 15000+200000 17620 words of font info for 68 fonts, out of 3000000 for 9000 745 hyphenation exceptions out of 8191 - 30i,10n,22p,207b,303s stack positions out of 5000i,500n,10000p,200000b,50000s + 30i,10n,52p,207b,1530s stack positions out of 5000i,500n,10000p,200000b,50000s -Output written on nobu-prosym.dvi (3 pages, 13808 bytes). +Output written on nobu-prosym.dvi (3 pages, 19520 bytes). diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.pdf Binary file Paper/nobu-prosym.pdf has changed diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.tex --- a/Paper/nobu-prosym.tex Fri Nov 18 06:33:48 2011 +0900 +++ b/Paper/nobu-prosym.tex Fri Nov 18 10:07:29 2011 +0900 @@ -1,1 +1,1 @@ -\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} \def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 今回は GCC-4.6 への実装を行った. 本論文では GCC-4.6 への CbC の具体的な実装について述べる。 %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる. CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. 今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. % }{ \section{Continuation based C (CbC)} Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. また,コードセグメント単位で処理を記述するという特徴がある. 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/codesegment.eps}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{継続(goto)} コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. この goto によるコードセグメント間の移動を継続と言う. 継続の実態は jmp による関数の移動となる. \subsection{コードセグメント(code segment)} CbC におけるプログラムの基本単位としてコードセグメントという概念がある. コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 関数と同じように引数を持たせて継続させることもできる. しかし,関数とは違ってリターンを行わない為返り値を取得することはできない. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \begin{figure}[htpb] \begin{center} \scalebox{0.40}{\includegraphics{figure/factorial.eps}} \end{center} \caption{階上を計算する CbC プログラムの例} \label{fig:factorial} \end{figure} %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. \section{GCCの3つの内部表現} GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく. \subsection{3つの内部表現} GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う. それぞれが 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図\ref{fig:ir}は \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/ir.eps}} \end{center} \caption{GCC によるコンパイルの一連の流れ} \label{fig:ir} \end{figure} \subsubsection{Generic Tree} ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる. 関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される. CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている. \subsubsection{GIMPLE} Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される. GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる. 制約は「1つの枝に4つ以上の子を持たせない」等といったもので, GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる. CbC の実装では特に修正は加えていない. \subsubsection{Register Transfer Language (RTL)} 構文木 GIMPLE は解析が行われた後 RTL へと変換される. RTL での表現は低レベルで,アセンブラとほぼ同じ表現を行うことができる. CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる. \section{GCC-4.6 への実装} 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく. \subsection{“__code” のパース} \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, call ではなく jmp を用いることができるという最適化である. 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/continuation.eps}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す. \subsubsection{expand\_call} ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数によって判断される. Tail call Elimination が行える場合 try\_tail_call expand\_call 関数の中で try_tail_call というフラグ \subsection{引数渡し} 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される. GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある. fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る. \subsubsection{fastcall} コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする. C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う. だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない. そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/fastcall.eps}} \end{center} \caption{fastcall属性付与} \label{fig:fastcall} \end{figure} if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である. \begin{thebibliography}{10} \bibitem{1}{河野真治}: “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 \bibitem{2}{河野真治}: “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000 \bibitem{3}{与儀健人,河野真治}: “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008 \bibitem{4}{与儀健人,河野真治}: “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010 \bibitem{5}{下地篤樹,河野真治}: “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008 \bibitem{6}{楊挺,河野真治}: “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002 \bibitem{7}{GNU Compiler Collection (GCC) Internals}: “http://gcc.gnu.org/onlinedocs/gccint/” \end{thebibliography} \end{document} \ No newline at end of file +\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} \usepackage{multirow} %% tabularの上下の結合 \usepackage{slashbox} %% tabularでの斜め線 \usepackage{listings} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} \def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 今回は GCC-4.6 への実装を行った. 本論文では GCC-4.6 への CbC の具体的な実装について述べる。 %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる. CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. 今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. % }{ \section{Continuation based C (CbC)} Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. また,コードセグメント単位で処理を記述するという特徴がある. 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/codesegment.eps}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{継続(goto)} コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. この goto によるコードセグメント間の移動を継続と言う. 継続の実態は jmp による関数の移動となる. \subsection{コードセグメント(code segment)} CbC におけるプログラムの基本単位としてコードセグメントという概念がある. コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 関数と同じように引数を持たせて継続させることもできる. しかし,関数とは違ってリターンを行わない為返り値を取得することはできない. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \lstinputlisting[language=c]{source/factorial.cbc} %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. \section{GCCの3つの内部表現} GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく. \subsection{3つの内部表現} GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う. それぞれが 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図\ref{fig:ir}は \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/ir.eps}} \end{center} \caption{GCC によるコンパイルの一連の流れ} \label{fig:ir} \end{figure} \subsubsection{Generic Tree} ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる. 関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される. CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている. \subsubsection{GIMPLE} Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される. GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる. 制約は「1つの枝に4つ以上の子を持たせない」等といったもので, GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる. CbC の実装では特に修正は加えていない. \subsubsection{Register Transfer Language (RTL)} 構文木 GIMPLE は解析が行われた後 RTL へと変換される. RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる. プログラム内部では RTL も木構造で表される. CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる. \section{GCC-4.6 への実装} 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく. \subsection{“\_\_code” のパース} \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, call ではなく jmp を用いることができるという最適化である. 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/continuation.eps}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す. \subsubsection{expand\_call} ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される. Tail Call Elimination が行える条件は以下のようになる. \begin{description} \item[caller側とcallee側の型の一致] \item[] \item[] \end{description} %expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている. %Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる. expand\_call 関数の中で try\_tail\_call フラグ \subsection{引数渡し} 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される. GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある. fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る. \subsubsection{fastcall} コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする. C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う. だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない. そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである. %\lstinputlisting[language=c]{source/fastcall.c} \begin{figure}[htpb] \begin{center} \scalebox{0.33}{\includegraphics{figure/fastcall.eps}} \end{center} \caption{コードセグメントへのfastcall属性付与} \label{fig:fastcall} \end{figure} if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行れ, fastcall 属性を付けると warning を出すからである. \section{評価} 今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース, Micro-C コンパイラとそれぞれ比較を行った. 比較を行うのはクイックソートのプログラムである. クイックソートは再帰的にプログラムされる為 CbC に向いている プログラムだと言える. 比較を行うのは以下のアーキテクチャと OS になる. \begin{description} \item[x86/Linux] \item[x86/OS] \item[x86/OS X(64bit 動作)] \end{description} また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと, 速度最適化(-O2 -fomit-frame-pointer)を行うものの2つを用意する. 表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し, 表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる. \begin{table}[htpb] \centering \small \begin{tabular}{|c|c|c|c|} \hline CPU/OS &GCC-4.4& GCC-4.6 &Micro-C \\ \hline x86/Linux & 7.378 & 0.829 & 2.890 \\ \hline x86\_64(m32)/OS X& 3.890 & 0.382 & 2.288 \\ \hline x86\_64/OS X & 4.078 & 0.450 & \\ \hline \end{tabular} \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(最適化無し)} \label{tab:speed-mc-vs-gcc-nonopt} \end{table} \begin{table}[htpb] \centering \small \begin{tabular}{|c|c|c|c|} \hline CPU/OS &GCC-4.4& GCC-4.6 &Micro-C \\ \hline x86/Linux & 3.252 & 1.768 & 2.890 \\ \hline x86\_64(m32)/OS X& 1.827 & 0.934 & 2.288 \\ \hline x86\_64/OS X & 1.101 & 2.896 & \\ \hline \end{tabular} \caption{アーキテクチャ毎のGCCとmicro-cの速度比較（単位: 秒)(速度最適化)} \label{tab:speed-mc-vs-gcc-opt} \end{table} \begin{thebibliography}{10} \bibitem{1}{河野真治}: “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 \bibitem{2}{河野真治}: “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000 \bibitem{3}{与儀健人,河野真治}: “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008 \bibitem{4}{与儀健人,河野真治}: “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010 \bibitem{5}{下地篤樹,河野真治}: “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008 \bibitem{6}{楊挺,河野真治}: “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002 \bibitem{7}{GNU Compiler Collection (GCC) Internals}: “http://gcc.gnu.org/onlinedocs/gccint/” \end{thebibliography} \end{document} \ No newline at end of file diff -r 4c5a29c7bb47 -r 5dfa978ee319 Paper/nobu-prosym.tex~ --- a/Paper/nobu-prosym.tex~ Fri Nov 18 06:33:48 2011 +0900 +++ b/Paper/nobu-prosym.tex~ Fri Nov 18 10:07:29 2011 +0900 @@ -1,1 +1,1 @@ -\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} \def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 今回は GCC-4.6 への実装を行った. 本論文では GCC-4.6 への CbC の具体的な実装について述べる。 %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. CbC の構文は C と同じであるが,継続によりループ制御や関数コールを取り除かれる. 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発された. 以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. お陰で,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. しかし,未だに GCC ベースのコンパイラには幾つかのバグがある. 今回,GCC-4.6 への実装も兼ねながら問題の部分の改善を行った. 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を具体的に述べる. % }{ \section{Continuation based C (CbC)} Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. また,コードセグメント単位で処理を記述するという特徴がある. 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/codesegment.eps}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{継続(goto)} コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. コードセグメントは自身の処理が終われば goto により次のコードセグメントでの処理に移る. goto によるコードセグメント間の移動を継続と言う. \subsection{コードセグメント(code segment)} CbC におけるプログラムの基本単位としてコードセグメントという概念がある. コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 関数と同じように引数を持たせて継続させることもできる. しかし,関数とは違ってリターンを行わない為返り値を取得することはできない. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/factorial.eps}} \end{center} \caption{CbC のプログラム例} \label{fig:factorial} \end{figure} %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. \section{Gnu Compiler Collection} GCC-4.6 への実装の前に,GCC によるコンパイルの一連の流れについて触れておく. \subsection{3つの中間言語} GCC は内部で Generic Tree, GIMPLE, RTL の3つの中間言語を扱われる. \subsubsection{Generic Tree} まず,GCC で読み込まれたソースコードは Generic Tree 呼ばれる構文木のデータ構造で表される. 図...に Generic Tree で表現された例を示す. \subsubsection{GIMPLE} Generic Tree により表現されたデータは次に GIMPLE という構文木へと変換される. GIMPLE は Generic Tree より制約がかかった状態で作成される. 制約は「1つの枝に4つ以上の子を持たせない」といったもので, GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになる. \subsubsection{RTL} Gneric Tree から GIMPLE, そして RTL へとデータは変換され最後にアセンブリ言語で出力される. \section{GCC-4.6 への実装} \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, call ではなく jmp を用いて大元の関数へ戻るようにする最適化のことである. 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/continuation.eps}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} \subsubsection{expand\_call} \subsection{引数渡し} 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される. GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある. fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る. \subsubsection{fastcall} コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする. C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う. だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない. そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/fastcall.eps}} \end{center} \caption{fastcall属性付与} \label{fig:fastcall} \end{figure} if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である. \begin{thebibliography}{10} \bibitem{1}{河野真治}: “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 \bibitem{2}{河野真治}: “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000 \bibitem{3}{与儀健人,河野真治}: “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008 \bibitem{4}{与儀健人,河野真治}: “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010 \bibitem{5}{下地篤樹,河野真治}: “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008 \bibitem{6}{楊挺,河野真治}: “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002 \bibitem{7}{GNU Compiler Collection (GCC) Internals}: “http://gcc.gnu.org/onlinedocs/gccint/” \end{thebibliography} \end{document} \ No newline at end of file +\documentclass[private]{ipsjpapers} %\documentstyle{ipsjpapers} \usepackage[dvipdfmx]{graphicx} \usepackage{url} % 巻数，号数などの設定 %\setcounter{巻数}{41} %\setcounter{号数}{6} %\setcounter{volpageoffset}{1234} %\受付{12}{2}{4} %\採録{12}{5}{11} \pagestyle{empty} % ユーザが定義したマクロなど． \makeatletter \let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY} \def\<{\(\langle\)} \def\>{\(\rangle\)} \def\|{\verb|} \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} \def\LATEX{\iLATEX\Large} \def\LATEx{\iLATEX\normalsize} \def\LATex{\iLATEX\small} \def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} \def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} \def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} \def\Quote{\list{}{}\item[]} \let\endQuote\endlist \def\TT{\if@LaTeX@e\tt\fi} \def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else $\backslash$#1\fi} %\checklines % 行送りを確認する時に使用 \begin{document}%{ % 和文表題 \title[Continuation based C の GCC 4.6 上の実装について]% {Continuation based C の GCC 4.6 上の実装について} % 英文表題 \etitle{The implementation of Continuation based C Compiler on GCC 4.6} % 所属ラベルの定義 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu} % 和文著者名 \author{大城 信康\affiref{URYUKYU}\nomember\and 河野 真治\affiref{URYUKYU}\member{19841765}} % 英文著者名 \eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and Shinji Kono\affiref{URYUKYU}} % 連絡先（投稿時に必要．製版用では無視される．） \contact{大城 信康\\ 〒903-0213 沖縄県中頭郡西原町字千原1番地\\ 琉球大学 情報工学科\\ TEL: (098)895-8723\qquad FAX: (098)895-8727\\ email: dimolto@cr.ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 今回は GCC-4.6 への実装を行った. 本論文では GCC-4.6 への CbC の具体的な実装について述べる。 %当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している. %また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている. %お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった. \end{abstract} % 英文概要 \begin{eabstract} We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6. %Continuation based C is programming language. It is developing our laboratory. \end{eabstract} % 表題などの出力 \maketitle \thispagestyle{empty} % }{ % 本文はここから始まる \section{歴史的経緯} 当研究室では,継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している. CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる. CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった. %以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている. 今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる. % }{ \section{Continuation based C (CbC)} Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である. 構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている. また,コードセグメント単位で処理を記述するという特徴がある. 図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/codesegment.eps}} \end{center} \caption{コードセグメント間の継続(goto)} \label{fig:cs} \end{figure} \subsection{継続(goto)} コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. この goto によるコードセグメント間の移動を継続と言う. 継続の実態は jmp による関数の移動となる. \subsection{コードセグメント(code segment)} CbC におけるプログラムの基本単位としてコードセグメントという概念がある. コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 関数と同じように引数を持たせて継続させることもできる. しかし,関数とは違ってリターンを行わない為返り値を取得することはできない. 図\ref{fig:factorial}は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている. \begin{figure}[htpb] \begin{center} \scalebox{0.40}{\includegraphics{figure/factorial.eps}} \end{center} \caption{階上を計算する CbC プログラムの例} \label{fig:factorial} \end{figure} %コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる. %コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる. \section{GCCの3つの内部表現} GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく. \subsection{3つの内部表現} GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う. それぞれが 読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図\ref{fig:ir}は \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/ir.eps}} \end{center} \caption{GCC によるコンパイルの一連の流れ} \label{fig:ir} \end{figure} \subsubsection{Generic Tree} ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる. 関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される. CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている. \subsubsection{GIMPLE} Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される. GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる. 制約は「1つの枝に4つ以上の子を持たせない」等といったもので, GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる. CbC の実装では特に修正は加えていない. \subsubsection{Register Transfer Language (RTL)} 構文木 GIMPLE は解析が行われた後 RTL へと変換される. RTL での表現は低レベルで,アセンブラとほぼ同じ表現を行うことができる. CbC における継続は,この RTL で行われる最適化の1つ Tail Call Elimination が重要となってくる. \section{GCC-4.6 への実装} 前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく. \subsection{“__code” のパース} \subsection{Tail Call Elimination} CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる. Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, call ではなく jmp を用いることができるという最適化である. 図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している. \begin{figure}[htpb] \begin{center} \scalebox{0.50}{\includegraphics{figure/continuation.eps}} \end{center} \caption{Tail Call Elimination} \label{fig:continue} \end{figure} funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す. \subsubsection{expand\_call} ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数によって判断される. Tail call Elimination が行える場合 try\_tail_call expand\_call 関数の中で try_tail_call というフラグ \subsection{引数渡し} 通常コードセグメントの継続において,引数は C の関数と同じスタックを用いて渡される. GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある. fastcall を用いてコードセグメントを宣言することで,レジスタを用いた速度の向上を図る. \subsubsection{fastcall} コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする. C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う. だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない. そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う. 図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである. \begin{figure}[htpb] \begin{center} \scalebox{0.35}{\includegraphics{figure/fastcall.eps}} \end{center} \caption{fastcall属性付与} \label{fig:fastcall} \end{figure} if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である. \begin{thebibliography}{10} \bibitem{1}{河野真治}: “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 \bibitem{2}{河野真治}: “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000 \bibitem{3}{与儀健人,河野真治}: “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008 \bibitem{4}{与儀健人,河野真治}: “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010 \bibitem{5}{下地篤樹,河野真治}: “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008 \bibitem{6}{楊挺,河野真治}: “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002 \bibitem{7}{GNU Compiler Collection (GCC) Internals}: “http://gcc.gnu.org/onlinedocs/gccint/” \end{thebibliography} \end{document} \ No newline at end of file