# HG changeset patch # User Kaito Tokumori # Date 1455489044 -32400 # Node ID 3afb4bfe1100a4606bea18468d1a79ef71cea6a7 # Parent bea98599d11fedc4c363187c15e38c536370018a fix diff -r bea98599d11f -r 3afb4bfe1100 paper/appendix.tex --- a/paper/appendix.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/appendix.tex Mon Feb 15 07:30:44 2016 +0900 @@ -6,153 +6,3 @@ \item {Continuation based C の LLVM/clang 3.5 上の実装について, 徳森海斗, 河野真治, 情報処理学会システムソフトウェアとオペレーティングシステム研究会, May, 2014} \end{itemize} -\chapter{環境付き継続の計測に使用したソースコード} -\begin{lstlisting}[frame=lrbt,label=gotowithenv,caption={}] -#define LOOP 50000000 - -#include - -__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env); - -__code factorial(int n,int result,int orig,__code(*print)(int,int,int,__code(*)(),__code(*)(),void*),__code(*exit1)(int,void *), void *exit1env) -{ - if (n<0) { - printf("#0008:err %d!\n",n); - goto (*exit1)(0,exit1env); - } - if (n==0) - goto (*print)(n,result,orig,print,exit1,exit1env); - else { - result += n; - n--; - goto factorial(n,result,orig,print,exit1,exit1env); - } -} - - -int calc(int n){ - __code (*ret)(int,void *) = __return; - void* env = __environment; - goto factorial(n,1,n,print,ret,env); - return 0; -} - -int main( int ac, char *av[]) -{ - int i; - long ans; - for(i=LOOP,ans=0;i>0;i--){ - ans += calc(10); - } - - printf("%ld\n",ans); -} - -__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env) -{ - goto (*exit1)(result,exit1env); -} -\end{lstlisting} - -\chapter{計算を繰り返すコード (C)} -\begin{lstlisting}[frame=lrbt,label=calc,caption={}] -#define LOOP 500000000 - -#include -#include - -int func4(int a, int b){ - return a+b; -} - -int func3(int a, int b){ - return func4(b,b/a); -} - -int func2(int a, int b){ - return func3(b,a*b); -} - -int func1(int a, int b){ - return func2(b,a+b); -} - -int start_func(int loop){ - int i, a; - a = 0; - for (i=0;i -#include - -__code code4(int a, int b, int loop, int ans){ - goto start_code(ans+a+b, loop-1); -} - -__code code3(int a, int b, int loop, int ans){ - goto code4(b,b/a,loop, ans); -} - -__code code2(int a, int b, int loop, int ans){ - goto code3(b,a*b,loop, ans); -} - -__code code1(int a, int b, int loop, int ans){ - goto code2(b,a+b,loop, ans); -} - -__code start_code(int ans, int loop){ - if (loop>0) - goto code1(1,2,loop, ans); - else - goto print(ans); -} - -int main( int ac, char *av[]){ - goto start_code(0,LOOP); - return 0; -} - -__code print(int a){ - printf("%d\n",a); - exit(0); -} -\end{lstlisting} - -\chapter{計算を繰り返すコード (Scheme)} -\begin{lstlisting}[frame=lrbt,label=calcScheme,caption={}] -(define LOOP 500000000) - -(define (print_ans ans) - (print ans)) - -(define (code4 a b loop ans) - (start_code (+ ans (+ a b)) (- loop 1))) - -(define (code3 a b loop ans) - (code4 b (/ b a) loop ans)) - -(define (code2 a b loop ans) - (code3 b (* a b) loop ans)) - -(define (code1 a b loop ans) - (code2 b (+ a b) loop ans)) - -(define (start_code ans loop) - (if (> loop 0) (code1 1 2 loop ans) (print_ans ans) )) - -(start_code 0 LOOP) -\end{lstlisting} diff -r bea98599d11f -r 3afb4bfe1100 paper/chapter1.tex --- a/paper/chapter1.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/chapter1.tex Mon Feb 15 07:30:44 2016 +0900 @@ -1,26 +1,38 @@ \chapter{Continuation based C (CbC)} \label{chapter:CbC} -CbC の構文は C と同じであるが, for文, while文といったループ制御構文や関数呼び出しを取り除き\footnote{言語仕様としては存在しないが while や for を使用することは可能である. }, code segment と goto による軽量継続を導入している. -以下の図\ref{fig:cs}は code segment 同士の関係を表したものであり, 図中の丸が code segment を, 矢印が goto による継続を表している. +CbC では関数ではなく code segment を処理の単位とする. code segment は入力と出力を持ち, CbC では引数が入出力となっている. code segment は次の code segment への遷移で処理を終え, 引数として出力を与える. CbC は C との行き来に環境付き継続を使用する. + +\section{CbC における Code Segment} +code segment は CbC における最も基本的な処理単位である. リスト \ref{code_simple} は最も基本的な CbC のコードの一例で, 図 \ref {fig:code_simple}はそれを図示したものである. +code segment の宣言は C の関数の構文と同じように行い, 型に \_\_code を用いる. ただし, これは \_\_code 型の戻り値を返すという意味ではない. \_\_code はそれが関数ではなく code segment であることを示すフラグのようなものである. + +現在の code segment から次の code segment への処理の移動は goto の後に code segment 名と引数を並べて記述する リスト \ref{code_simple} の goto cs1(a+b); などがこれにたる. これを軽量継続と呼び, このときの a+b が次のコードセグメントへの出力と成る. + +通常 Secheme の call/cc 等の継続はトップレベルから現在の位置までの位置を環境として保持する. ここで環境は現在のスタックの状態のことを指す. +CbC の軽量継続は呼び出し元の環境を持たない. つまりスタックの情報を破棄して処理を続けていくのである. + +リスト \ref{code_simple} の場合, cs0 は cs1 に継続すると cs0 の環境は破棄されてしまうため, cs0 に戻ることは出来ない. +\begin{lstlisting}[frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}] +__code cs0(int a, int b){ + goto cs1(a+b); +} + +__code cs1(int c){ + goto cs2(c); +} +\end{lstlisting} \begin{figure}[htpb] \begin{center} - \scalebox{0.35}{\includegraphics{fig/codesegment2.pdf}} + \scalebox{0.55}{\includegraphics{fig/codesegment.pdf}} \end{center} - \caption{goto による code segment 間の継続} - \label{fig:cs} + \caption{code segment の軽量継続} + \label{fig:code_simple} \end{figure} -\section{CbC における Code Segment} -CbC では処理の単位として code segment を用いる。code segment は CbC における最も基本的な処理単位であり, C の関数と異なり戻り値を持たない. -code segment の宣言は C の関数の構文と同じように行い, 型に \_\_code を用いる. ただし, これは \_\_code 型の戻り値を返すという意味ではない. 前述した通り, code segment は戻り値を持たないので, \_\_code はそれが関数ではなく code segment であることを示すフラグのようなものである. -code segment の処理内容の定義も C の関数同様に行うが, 前述した通り CbC にはループ制御構文が存在しないので, ループ処理は自分自身への再帰的な継続を行うことで実現する. -現在の code segment から次の code segment への処理の移動は goto の後に code segment 名と引数を並べて記述するという CbC 独自の構文を用いて行う. この goto による処理の遷移を継続と呼ぶ. -C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていくが, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無くスタックは変更されない. -このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. +もう少し複雑な CbC のプログラムの例が以下のリスト \ref{factorial} である. これは与えられた数値の階乗を算出するプログラムである. このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する. -以下に CbC を用いたコードの例として, 与えられた数値の階乗を算出するプログラムを示す. このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する. \begin{lstlisting}[frame=lrbt,label=factorial,caption={\footnotesize 階乗を求める CbC プログラムの例}] __code print_factorial(int prod) { @@ -52,13 +64,19 @@ } \end{lstlisting} +\begin{figure}[htpb] + \begin{center} + \scalebox{0.55}{\includegraphics{fig/factorial.pdf}} + \end{center} + \caption{階乗を求める CbC プログラムの軽量継続図} + \label{fig:factorial} +\end{figure} + \section{環境付き継続} \label{sec:withEnv} 環境付き継続は C との互換性のために必要な機能である. CbC と C の記述を交える際, CbC の code segment から C の関数の呼び出しは問題なく行える. しかし, C の関数から CbC の code segment へと継続する場合, 呼び出し元の環境に戻るための特殊な継続が必要となる. これを環境付き継続と呼ぶ. -この環境付き継続を導入した言語は C with Continuation (CwC) と呼ばれ, C と CbC の両方の機能を持つ言語となる. また, C, CbC は CwC のサブセットと考えられるので, CwC のコンパイラを CbC に使用することができる. これまでに実装されてきた CbC コンパイラは実際には CwC のコンパイラとして実装されている. - -環境付き継続を用いる場合, C の関数から code segment へ継続する際に \_\_return, \_\_environment という変数で表される特殊変数を渡す. \_\_return は環境付き継続先が元の環境に戻る際に利用する code segment, \_\_environment は元の関数の環境を表す. リスト\ref{gotoWithTheEnv}では関数 funcB から code segment cs に継続する際に環境付き継続を利用している. cs は funcB から渡された code segment へ継続することで元の C の環境に復帰することが可能となる. 但し復帰先は \_\_return を渡した関数が終了する位置である. このプログラムの例では, 関数 funcA は戻り値として funcB の終わりにある -1 ではなく, 環境付き継続によって渡される 1 を受け取る. 図\ref{fig:gotoWithTheEnv}にこの様子を表した. +環境付き継続を用いる場合, C の関数から code segment へ継続する際に \_\_return, \_\_environment という変数を渡す. \_\_return は \_\_code (*)(return\_type, void*) 型の変数で環境付き継続先が元の環境に戻る際に利用する code segmentを表す. \_\_environment は void** 型の変数で元の関数の環境を表す. リスト\ref{gotoWithTheEnv}では関数 funcB から code segment cs に継続する際に環境付き継続を利用している. cs は funcB から渡された code segment へ継続することで元の C の環境に復帰することが可能となる. 但し復帰先は \_\_return を渡した関数が終了する位置である. このプログラムの例では, 関数 funcA は戻り値として funcB の終わりにある -1 ではなく, 環境付き継続によって渡される 1 を受け取る. 図\ref{fig:gotoWithTheEnv}にこの様子を表した. \begin{lstlisting}[frame=lrbt,label=gotoWithTheEnv,caption={環境付き継続}] __code cs(__code (*ret)(int, void*), void *env){ @@ -80,6 +98,7 @@ /* A1 */ printf("retval = %d\n", retval); /* retval should not be -1 but be 1. */ + return 0; } \end{lstlisting} @@ -93,11 +112,23 @@ \end{figure} -このような形にすることで, code segment 側では関数から呼ばれたか, code segment からの継続かを考慮する必要がなくなる. また, funcA から見た場合にも, 呼び出した関数の内部で code segment が使われているかどうかが隠蔽され, code segment の有無を考慮しなくて良い. +このように, 環境付き継続を用いることで C, CbC 間の処理の移動が可能になる. \section{Gears OS サポート} \label{sec:Gears} -Gears OS は当研究室で開発している並列フレームワークで, CbC で記述している. Gears では通常の CbC には存在しないメタレベルの処理を表す meta code segment, データの単位である data segment, data segment や code segment 等の情報を管理する context 等がある. これらを現在の CbC の機能のみを用いて記述するとリスト\ref{gears}のようになり, 多くの労力を要する. そのためこの記述を助ける機能が必要であり, 本研究ではこれらを利用するプログラミングをサポートするために以下の機能を提案した. +Gears OS は当研究室で開発している並列フレームワークで, CbC で記述している. Gears では通常の CbC には存在しない meta code segment, data segment, context 等を用いる. meta code segment は meta computation を行う code segment で, メモリの確保やネットワーク管理等が meta computation にあたる. data segment はデータの単位であり, code segment の入出力になる. context は meta data segment に相当し, code segment や data segment を管理している. + +また meta computation を用いる場合, code segment から code segment への軽量継続の間に meta code segment によって meta computation が行われる. これを図示したのが図 \ref{fig:metaCS} である. + +\begin{figure}[htpb] + \begin{center} + \scalebox{0.55}{\includegraphics{fig/metaCS.pdf}} + \end{center} + \caption{meta computation} + \label{fig:metaCS} +\end{figure} + +これらを現在の CbC の機能のみを用いて記述するとリスト\ref{gears}のようになり, 多くの労力を要する. そのためにこの記述を助ける機能を実装する必要があり, 本研究では以下の機能を提案した. \begin{itemize} \item code segment から meta code segment への自動接続 diff -r bea98599d11f -r 3afb4bfe1100 paper/chapter2.tex --- a/paper/chapter2.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/chapter2.tex Mon Feb 15 07:30:44 2016 +0900 @@ -340,20 +340,20 @@ \label{sec:TCE} 前述した通り, LLVM の処理は最適化を含め全て pass によって行われるため, pass を選択することで任意の最適化をかけることができる. 独自の pass を作ることも可能であり, pass 作成のチュートリアルは LLVM のドキュメント\cite{LLVM}にも記されている. また, pass の雛形となるクラスも用意されており, 独自の pass を作成する環境は整っていると言える. -最適化機構は本研究においてはほとんど関係しないが, 継続の実装に関わる Tail Call Elimination, 関数呼び出し時のフレームポインタ操作の最適化を行う omit leaf frame pointer だけは別である. - -%%Tail Call Elimination は, 通常 call 命令を使用するべき関数呼び出しで jmp 命令を用いるという最適化である. code segment は call でなく jmp で遷移する必要が有るため, CbC コンパイラでは code segment に対してこの最適化がかかるよう強制しなければならない. +最適化機構は本研究にはほとんど関係しないが, CbC では継続の実装に Tail Call Elimination という最適化を用いるため, これは別である. Tail call elimination の説明の前にまず, tail call について簡単に説明する. tail call は, ある関数の持つ処理の一番最後に位置し, 呼び出し元が戻り値を返す場合は呼び出された関数の戻り値がそのまま呼び出し元の戻り値として返されるような関数呼び出しのことを指す. 具体的には以下のリスト \ref{tailCall} の 関数B, 関数C の呼び出しがそれに当たる. Tail call elimination はこの末尾にある関数呼び出しの最適化を行う. 通常, 関数呼び出しはアセンブルされると call 命令に置き換わるが, tail call elimination ではその代わりに jmp 命令を用いる. その様子を関数Bの呼び出しに注目し, 関数 caller が main 関数から呼ばれるとして図示したものが以下の図\ref{fig:TCE}である. 通常の関数呼び出しの場合, 関数 caller に呼び出された関数 B はその処理を終えると ret 命令により一度関数 caller に戻る. そして再び ret 命令を用いることで main 関数に戻る. Tail call elimination ではこの関数 B から関数 caller に戻る無駄な処理を低減する. 図\ref{fig:TCE}より, 関数 caller が関数 B を呼び出す時の命令が call から jmp にかわり, 関数 B は処理を終えると直接 main 関数に戻っていることがわかる. \begin{lstlisting}[frame=lrbt, label=tailCall, caption={Tail call の例}] void caller(){ - A(); - if ( condition ) + int a = A(); + if ( a != 10 ){ B(); return; - else + } + else { C(); return; + } } \end{lstlisting} \begin{figure}[htpb] @@ -445,52 +445,3 @@ \item tailcallopt の有効化. \item 最適化レベルに関わらず Tail call elimination pass を追加. \end{itemize} - -\section{omit leaf frame pointer} -\label{sec:olfp} -omit leaf frame pointer は関数呼び出しの際に行われるフレームポインタ操作に関わる最適化である. 通常関数呼び出しを行う際にはフレームポインタの値をスタックに積み, return 直前に戻すという作業を行う. omit leaf frame pointer はこの操作を leaf function を呼び出す際に行わないようにする最適化である. - -leaf function とはコールツリーの終端の位置する関数のことを指し, この関数が関数を呼び出さないことを意味する. - - -以下のリスト \ref{loptno}, \ref{lopt} はどちらもアセンブリコードから leaf function の部分を抜き出したものであり, 前者が omit leaf frame pointer 無し, 後者が omit leaf frame pointer ありのコードである. push, pop 命令によるフレームポインタの操作がリスト \ref{lopt} ではなくなっていることがわかる. - -\begin{minipage}[t]{0.5\textwidth} - \begin{lstlisting}[frame=lrbt, label=loptno, caption={関数 caller (omit leaf frame pointer 無し)}] -_caller: ## @caller - .cfi_startproc -## BB#0: - pushq» %rbp -Ltmp0: - .cfi_def_cfa_offset 16 -Ltmp1: - .cfi_offset %rbp, -16 - movq» %rsp, %rbp -Ltmp2: - .cfi_def_cfa_register %rbp - movl» %edi, -4(%rbp) - movl» %esi, -8(%rbp) - movl» -4(%rbp), %esi - addl» -8(%rbp), %esi - movl» %esi, %eax - popq» %rbp - retq - .cfi_endproc - \end{lstlisting} -\end{minipage} -\begin{minipage}[t]{0.5\textwidth} - \begin{lstlisting}[frame=lrbt, label=lopt, caption={関数 caller (omit leaf frame pointer 有り)}] -_caller: ## @caller - .cfi_startproc -## BB#0: - movl» %edi, -4(%rbp) - movl» %esi, -8(%rbp) - movl» -4(%rbp), %esi - addl» -8(%rbp), %esi - movl» %esi, %eax - retq - .cfi_endproc - \end{lstlisting} -\end{minipage} - -CbC の code segment は関数呼び出しでなく継続によって処理の遷移を行っていくため, 全ての code segment が leaf function ということになる. したがって CbC はこの最適化と非常に相性が良いと言え, 本研究ではこの最適化の強制も行った. diff -r bea98599d11f -r 3afb4bfe1100 paper/chapter3.tex --- a/paper/chapter3.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/chapter3.tex Mon Feb 15 07:30:44 2016 +0900 @@ -1,5 +1,5 @@ \chapter{LLVM clang 上での CbC の実装} -第 \ref{chapter:CbC}, \ref{chapter:LLVM/clang} 章をもとに LLVM, clang への CbC コンパイル機能の実装を行う. コードセグメントの解釈, 軽量継続などいくつかの機能は過去の研究によって実装されたが, 本研究での実装に繋がるので説明する. +第 \ref{chapter:CbC}, \ref{chapter:LLVM/clang} 章をもとに LLVM, clang への CbC コンパイル機能の実装を行う. コードセグメントの解釈, 軽量継続などいくつかの機能は過去の研究によって実装されたが, 本研究での実装に繋がるのでここでも説明する. 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする. \section{code segment} @@ -331,8 +331,51 @@ \end{lstlisting} \section{フレームポインタ操作最適化} -フレームポインタ操作の最適化は omit leaf frame pointer を強制することで行う. この最適化は \ref{sec:olfp} 節でしたとおり leaf function に対して行われるが, 継続を続ける code segment は何もせずとも leaf function の条件を満たしているので内部で有効化するだけで良い. +フレームポインタ操作の最適化は omit leaf frame pointer を強制することで行う. この最適化は関数呼び出しの際に行われるフレームポインタ操作に関わる最適化である. 通常関数呼び出しを行う際にはフレームポインタの値をスタックに積み, return 直前に戻すという作業を行う. omit leaf frame pointer はこの操作を leaf function を呼び出す際に行わないようにする最適化である. +leaf function とはコールツリーの終端の位置する関数のことを指し, この関数が関数を呼び出さないことを意味する. 軽量継続を続ける code segment は何もせずとも leaf function の条件を満たしているので内部で有効化するだけで良い. + +以下のリスト \ref{loptno}, \ref{lopt} はどちらもリスト \ref{leaf} をコンパイルして得られるアセンブリコードから関数 caller の部分を抜き出したものであり, 前者が omit leaf frame pointer 無し, 後者が omit leaf frame pointer ありのコードである. push, pop 命令によるフレームポインタの操作がリスト \ref{lopt} ではなくなっていることがわかる. +\begin{lstlisting}[frame=lrbt, label=leaf, caption={関数 caller}] +void caller(int a, int b, int c){ + B(a, b, c, 40); + return; +} +\end{lstlisting} +\begin{lstlisting}[frame=lrbt, label=loptno, caption={関数 caller (omit leaf frame pointer 無し)}] +_caller: ## @caller + .cfi_startproc +## BB#0: + pushq %rbp +Ltmp0: + .cfi_def_cfa_offset 16 +Ltmp1: + .cfi_offset %rbp, -16 + movq %rsp, %rbp +Ltmp2: + .cfi_def_cfa_register %rbp + movl %edi, -4(%rbp) + movl %esi, -8(%rbp) + movl -4(%rbp), %esi + addl -8(%rbp), %esi + movl %esi, %eax + popq %rbp + retq + .cfi_endproc +\end{lstlisting} +\begin{lstlisting}[frame=lrbt, label=lopt, caption={関数 caller (omit leaf frame pointer 有り)}] +_caller: ## @caller + .cfi_startproc +## BB#0: + movl %edi, -4(%rbp) + movl %esi, -8(%rbp) + movl -4(%rbp), %esi + addl -8(%rbp), %esi + movl %esi, %eax + retq + .cfi_endproc +\end{lstlisting} + omit leaf frame pointer は clang 内部では CodeGenOpts.OmitLeafFramePointer として表現されている. clang は CodeGen で LLVM IR の function を生成する際にこのフラグが立っているかどうかを確認し, 立っている場合には関数の no-frame-pointer-elim という attribute を false にする. それにより最適化が当該関数に作用するようになる. この, LLVM IR function への attribute 設定を行っているのは \$(CLANG)/lib/CodeGen/CGCall.cpp である. ここをリスト \ref{olfp} のように変更した. 通常は OmitLeafFramePointer のみを確認する部分を HasCodeSegment によって code segment の有無も確認するように変更している. これにより, code segment を含むコードのコンパイル, 即ち CbC のコードのコンパイルの際には自動的に omit leaf frame pointer が有効化されるようになった. \begin{lstlisting}[frame=lrbt,label=olfp,caption={omit leaf frame pointer 有効化}] diff -r bea98599d11f -r 3afb4bfe1100 paper/chapter4.tex --- a/paper/chapter4.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/chapter4.tex Mon Feb 15 07:30:44 2016 +0900 @@ -1,23 +1,22 @@ \chapter{Gears OS サポート} \ref{sec:Gears} 節で述べた Gears OS の記述を助ける構文について記す. -Gears OS のための構文のサポートには python スクリプトを用いた. 記述したプログラムをこのスクリプトに読み込ませることで CbC コンパイラでコンパイル可能な構文へと変換される. このようにすることで Gears OS のコード, CbC のコード両方のコンパイルが可能になる. -\section{meta Code Segment の接続} -Gears OS では code segment 間の遷移に meta レベルの meta code segment を挟む. その様子を表したのが図 \ref{fig:meta} である. 通常レベルの code segment は一度 meta code segment へと継続し, その後次の code segment へと継続する. このとき通常レベルの code segment からは meta code segment への継続は隠蔽され, 通常レベルの code segment に直接継続しているように見えるべきである (図 \ref{fig:meta} の破線の継続). しかし既存の CbC では meta code segment への継続はサポートしておらず,これを実現するとリスト \ref{GearsCode} のようになり, meta code segment への継続を隠蔽することは出来ない. これらをスクリプトを用いることで リスト \ref{hideMeta} のように記述できるようになる. code segment から見ると直接次の code segment へ継続しているように見えるが, スクリプトを通すことで リスト \ref{GearsCode} のコードに変換されるので, きちんと meta code segment の処理も行われる. +Gears OS のための構文のサポートには python スクリプトを用いた. 記述したプログラムをこのスクリプトに読み込ませることで CbC コンパイラでコンパイル可能な構文へと変換される. このようにすることで meta code segment, data segment を用いるGears OS のコードのコンパイルが可能になる. -この変換は, meta code segment が通常レベルの code segment に継続する際に enum から成る code segment ID を利用して継続することを利用したものである. +\section{meta Code Segment の接続} +Gears OS では code segment 間の遷移に meta レベルの meta code segment を挟む. その様子を表したのが図 \ref{fig:metaCS} である. 通常レベルの code segment は一度 meta code segment へと継続し, その後次の code segment へと継続する. このとき通常レベルの code segment からは meta code segment への継続は見えず, 通常レベルの code segment に直接継続しているように見えるべきである (リスト \ref{hideMeta}). しかし既存の CbC コンパイラでは meta code segment への継続等は自分で記述する必要がある(リスト \ref{GearsCode}). これをリスト \ref{hideMeta} の形に変換するのが今回作成した python スクリプトである. -また, 同時に context の隠蔽も行っている. context は全ての code segment, data segment を管理しており, これに通常レベルの code segment から触れるのは好ましくないためこのようにした. +もう一つの機能として stub の自動生成がある. Gears OS では code segment は meta code segment に継続し, その後 code segment に継続すると述べたが, 正確には meta code segment から code segment に継続する際に stub という継続を挟む. stub では, code segment が必要とする data segment を context から取り出すという処理を行うもので, リスト \ref{GearsCode}, code1\_stub, code2\_stub がそれにあたる. stub は code segment 毎に生成されるためこの自動生成を行うことで code segment の記述量を約半分にすることができる. \begin{figure}[htpb] \begin{center} - \scalebox{0.45}{\includegraphics{fig/meta.pdf}} + \scalebox{0.55}{\includegraphics{fig/metaCS.pdf}} \end{center} - \caption{Gears OS における code segment の継続} - \label{fig:meta} + \caption{meta computation} + \label{fig:metaCS} \end{figure} -\begin{lstlisting}[frame=lrbt,label=GearsCode,caption={CbC で実現する Gears OS コード例}] +\begin{lstlisting}[frame=lrbt,label=GearsCode,caption={スクリプトにより出力される Gears OS コード}] __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); } @@ -32,7 +31,6 @@ goto meta(context, Code2); } - __code code2(struct Context* context, long* count) { *count = 0; goto meta(context, Code3); @@ -43,36 +41,7 @@ } \end{lstlisting} -\begin{lstlisting}[frame=lrbt,label=hideMeta,caption={meta code segment への継続の隠蔽}] -__code meta(struct Context* context, enum Code next) { - goto (context->code[next])(context); -} - -__code code1_stub(struct Context* context) { - goto code1(context, &context->data[Allocate]->allocate); -} - -__code code1(struct Allocate* allocate) { - allocate->size = sizeof(long); - allocator(); - goto code2(); -} - - -__code code2(long* count) { - *count = 0; - goto code3(); -} - -__code code2_stub(struct Context* context) { - goto code2(context, &context->data[Count]->count); -} -\end{lstlisting} - -\section{stub の自動生成} -もう一つの機能として stub の自動生成がある. 前節で, Gears OS では code segment は meta code segment に継続し, その後 code segment に継続すると述べたが, 正確には meta code segment から code segment に継続する際に stub という継続を挟む. stub では, code segment が必要とする data segment を context から取り出すという処理を行うもので, リスト \ref{GearsCode}, \ref{hideMeta} の code1\_stub, code2\_stub がそれにあたる. stub は code segment 毎に生成されるためこの自動生成を行うことで code segment の記述量を約半分にすることができる. meta code segment への継続, context の隠蔽, stub の生成全てを自動化した最終的なコードがリスト \ref{stubOmit} である. - -\begin{lstlisting}[frame=lrbt,label=stubOmit,caption={機械的な記述を取り除いた Gears OS のコード}] +\begin{lstlisting}[frame=lrbt,label=hideMeta,caption={Gears OS のコード}] __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); } @@ -88,5 +57,3 @@ goto code3(); } \end{lstlisting} - -改めて元のコードであるリスト \ref{GearsCode} と, スクリプトのサポートを受けるコードリスト \ref{stubOmit} を メタへの継続, stub による data segment の取り出しなど機械的な処理を記述する必要がなくなり CbC の記述が楽になっていることがわかる. 機械的な処理の自動化はコードを書く量を減らすだけでなく, 本来記述したい処理部分のプログラミングに集中することができるという利点も齎す. diff -r bea98599d11f -r 3afb4bfe1100 paper/chapter5.tex --- a/paper/chapter5.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/chapter5.tex Mon Feb 15 07:30:44 2016 +0900 @@ -50,10 +50,59 @@ \end{lstlisting} \section{実行速度の評価} -今回測定に使用したプログラムは環境付き継続と計算を繰り返すプログラムである. \footnote{ ソースコードは付録に掲載する. } 測定は x86-84 アーキテクチャの OS X 上で行った. 表 \ref{result}, 図 \ref{fig:result} が測定結果である. +今回測定に使用したプログラムは環境付き継続と計算を繰り返すプログラムである(リスト \ref{gotowithenv}). 測定は x86-84 アーキテクチャの OS X 上で行った. 表 \ref{result} が測定結果である. + +\begin{lstlisting}[frame=lrbt,label=gotowithenv,caption={環境付き継続を繰り返すプログラム}] +#define LOOP 50000000 + +#include + +__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env); + +__code factorial(int n,int result,int orig,__code(*print)(int,int,int,__code(*)(),__code(*)(),void*),__code(*exit1)(int,void *), void *exit1env) +{ + if (n<0) { + printf("#0008:err %d!\n",n); + goto (*exit1)(0,exit1env); + } + if (n==0) + goto (*print)(n,result,orig,print,exit1,exit1env); + else { + result += n; + n--; + goto factorial(n,result,orig,print,exit1,exit1env); + } +} + + +int calc(int n){ + __code (*ret)(int,void *) = __return; + void* env = __environment; + goto factorial(n,1,n,print,ret,env); + return 0; +} + +int main( int ac, char *av[]) +{ + int i; + long ans; + for(i=LOOP,ans=0;i>0;i--){ + ans += calc(10); + } + + printf("%ld\n",ans); +} + +__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env) +{ + goto (*exit1)(result,exit1env); +} +\end{lstlisting} + \begin{table}[htpb] \centering \begin{tabular}{|l|r|} \hline + コンパイラ名 & 実行速度 (s) \\ \hline LLVM/clang & 3.35 \\ \hline LLVM/clang -O2 & 1.30 \\ \hline LLVM/clang (old) & 23.30 \\ \hline @@ -61,49 +110,130 @@ GCC & 14.73 \\ \hline GCC -O2 & 12.96 \\ \hline \end{tabular} - \caption{Mac OS X での Micro-C, GCC, LLVM/clang の実行速度比較 (単位 : 秒)} + \caption{Mac OS X での Micro-C, GCC, LLVM/clang の環境付き継続の速度比較} \label{result} \end{table} -\begin{figure}[htpb] - \begin{center} - \scalebox{0.65}{\includegraphics{fig/env.eps}} - \end{center} - \caption{Mac OS X での Micro-C, GCC, LLVM/clang の実行速度比較グラフ} - \label{fig:result} -\end{figure} - 結果から、改良前の LLVM/clang とくらべて現在のものが最適化込みで 10 倍以上, 最適化を除いても 7 倍近い速度が出ていることがわかる. このことから通常の setjmp, longjmp の処理の重さが伺える. また, GCC のコンパイラの速度を大きく上回っていることから, nested function を用いた実装よりもこちらのほうが速いということがわかる. Micro-C コンパイラは直接アセンブラを生成しているので非常に高速であるが, 最適化を利用することで同等の速度が実現できている. \section{C, Scheme との比較} -CbC と他の言語との比較を行う. 比較対象は構文が殆ど一緒である C, 継続を用いることのできる Scheme とした. Scheme のコンパイラには Chicken を使用した. +CbC と他の言語との比較を行う. 比較対象は C, 継続を用いることのできる Scheme とした. Scheme のコンパイラには Chicken を使用した. -%最初に比較に使用したプログラムはフィボナッチ数を求めるプログラムである. 50000000 番目のフィボナッチ数を再帰を用いて求めるよう記述したところ, C ではスタックオーバーフローにより正しく結果を求めることが出来なかった. - -比較に使用したプログラムは四則演算を何度も繰り返し行うプログラムである. \footnote{ソースコードは付録に掲載する. } C はループにより計算を行い, CbC は goto による軽量継続を用いて計算を行う. +比較に使用したプログラムは C の関数呼び出し, CbC の軽量継続, Scheme の継続 を繰り返し行うものである (リスト \ref{calc}, \ref{calcCbC}, \ref{calcScheme}). 結果は以下のようになった. +\begin{lstlisting}[frame=lrbt,label=calc,caption={Cの計測用コード}] +#define LOOP 500000000 + +#include +#include + +int func4(int a, int b){ + return a+b; +} + +int func3(int a, int b){ + return func4(b,b/a); +} + +int func2(int a, int b){ + return func3(b,a*b); +} + +int func1(int a, int b){ + return func2(b,a+b); +} + +int start_func(int loop){ + int i, a; + a = 0; + for (i=0;i +#include + +__code code4(int a, int b, int loop, int ans){ + goto start_code(ans+a+b, loop-1); +} + +__code code3(int a, int b, int loop, int ans){ + goto code4(b,b/a,loop, ans); +} + +__code code2(int a, int b, int loop, int ans){ + goto code3(b,a*b,loop, ans); +} + +__code code1(int a, int b, int loop, int ans){ + goto code2(b,a+b,loop, ans); +} + +__code start_code(int ans, int loop){ + if (loop>0) + goto code1(1,2,loop, ans); + else + goto print(ans); +} + +int main( int ac, char *av[]){ + goto start_code(0,LOOP); + return 0; +} + +__code print(int a){ + printf("%d\n",a); + exit(0); +} +\end{lstlisting} + +\begin{lstlisting}[frame=lrbt,label=calcScheme,caption={Schemeの測定用コード}] +(define LOOP 500000000) + +(define (print_ans ans) + (print ans)) + +(define (code4 a b loop ans) + (start_code (+ ans (+ a b)) (- loop 1))) + +(define (code3 a b loop ans) + (code4 b (/ b a) loop ans)) + +(define (code2 a b loop ans) + (code3 b (* a b) loop ans)) + +(define (code1 a b loop ans) + (code2 b (+ a b) loop ans)) + +(define (start_code ans loop) + (if (> loop 0) (code1 1 2 loop ans) (print_ans ans) )) + +(start_code 0 LOOP) +\end{lstlisting} + \begin{table}[htpb] \centering \begin{tabular}{|l|r|} \hline + 言語 & 実行速度 (s) \\ \hline C & 4.85 \\ \hline CbC & 3.10 \\ \hline Scheme & 39.24 \\ \hline \end{tabular} - \caption{Mac OS X での C, CbC, Scheme の実行速度比較 (単位 : 秒)} + \caption{Mac OS X での C, CbC, Scheme の実行速度比較} \label{comp} \end{table} -\begin{figure}[htpb] - \begin{center} - \scalebox{0.55}{\includegraphics{fig/comp.eps}} - \end{center} - \caption{Mac OS X での C, CbC, Scheme の実行速度比較グラフ} - \label{fig:comp} -\end{figure} - 結果より, CbC の軽量継続が関数呼び出しよりも高速であることがわかる. このことからも関数呼び出し, return の際に行われるスタック操作の処理の重さがわかるだろう. -%Scheme は書き方が行けない気がする. というか比べるなら環境付き継続とcall/cc？ - diff -r bea98599d11f -r 3afb4bfe1100 paper/conclusion.tex --- a/paper/conclusion.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/conclusion.tex Mon Feb 15 07:30:44 2016 +0900 @@ -5,7 +5,7 @@ LLVM clang ベースの CbC コンパイラは 2014 年の研究によって開発された. 今回の研究では LLVM builtin の setjmp, longjmp を用いることによる環境付き継続の改善, omit leaf frame pointer を強制することによるさらなる最適化の付加, プロトタイプ宣言の自動化を行った. -また, Gears OS をサポートするためのスクリプトも作成し, data segment, meta code segment を利用する CbC の記述量を減らすことが出来た. +また, Gears OS をサポートするためのスクリプトも作成し, data segment, meta code segment を用いる CbC が記述できるようになった. 環境付き継続の速度計測では, 元のものの 7 倍近い速度を出すことに成功し, アセンブリコードを直接生成する高速な Micro-C のものと比較しても殆ど差がなくなった. diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/codesegment.graffle --- a/paper/fig/codesegment.graffle Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/fig/codesegment.graffle Mon Feb 15 07:30:44 2016 +0900 @@ -6,8 +6,8 @@ 0 ApplicationVersion - com.omnigroup.OmniGraffle - 139.18.0.187838 + com.omnigroup.OmniGraffle6 + 169.5.0.253125 AutoAdjust @@ -21,11 +21,6 @@ 2 Style - shadow - - Draws - NO - stroke Draws @@ -46,304 +41,27 @@ Creator Nobuyasu Oshiro DisplayScale - 1 0/72 in = 1.0000 in + 1 in = 1.00000 in GraphDocumentVersion - 8 + 12 GraphicsList Bounds - {{315.5, 89.625}, {45.933593999999999, 18.375}} - Class - ShapedGraphic - ID - 32 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 goto} - VerticalPad - 0 - - - - Bounds - {{315.5, 171}, {45.933593999999999, 18.375}} - Class - ShapedGraphic - ID - 31 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 goto} - VerticalPad - 0 - - - - Bounds - {{190.20312000000001, 167}, {45.933593999999999, 18.375}} + {{366.49999356269836, 106.55999761819839}, {65, 24}} Class ShapedGraphic - ID - 30 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 goto} - VerticalPad - 0 - - - - Bounds - {{405.93358999999998, 125}, {54, 18}} - Class - ShapedGraphic - ID - 29 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle - Style + FitText + YES + Flow + Resize + FontInfo - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - + Size + 11 - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 goto} - VerticalPad - 0 - - - - AllowLabelDrop - - Class - LineGraphic ID - 28 - Points - - {412.93358999999998, 143.02043} - {462.43358999999998, 143} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - Legacy - - TailArrow - 0 - TailScale - 0.5 - - - - - Bounds - {{90, 126}, {54, 18}} - Class - ShapedGraphic - ID - 27 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle + 37 Style fill @@ -365,44 +83,33 @@ Text Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} {\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 -\f0\fs24 \cf0 goto} - VerticalPad - 0 +\f0\fs22 \cf0 goto cs2(c)} + Wrap + NO Bounds - {{252, 134.3125}, {45.933593999999999, 18.375}} + {{209.99999356269836, 106.55999761819839}, {78, 24}} Class ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Size + 11 + ID - 26 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle + 36 Style fill @@ -424,73 +131,47 @@ Text Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} {\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 -\f0\fs24 \cf0 goto} - VerticalPad - 0 - - - - AllowLabelDrop - - Class - LineGraphic - Head - - ID - 3 +\f0\fs22 \cf0 goto cs1(a+b)} - ID - 23 - Points - - {97, 144.03550999999999} - {146.49998746981748, 144.01507110982496} - - Style - - stroke - - HeadArrow - FilledArrow - HeadScale - 1.4285709857940674 - Legacy - - TailArrow - 0 - TailScale - 0.5 - - + Wrap + NO Class LineGraphic - Head + FontInfo - ID - 5 + Font + Helvetica + Size + 12 ID - 11 + 35 Points - {307.08334974209447, 98.992681580751722} - {348.45143717244423, 125.9771788118144} + {323.99999356269836, 144} + {426.68373636901379, 143.8290591686964} Style + shadow + + Draws + NO + stroke HeadArrow FilledArrow Legacy - + LineType 1 TailArrow @@ -500,67 +181,44 @@ Tail ID - 1 + 33 Class LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + Head ID - 5 + 33 ID - 10 + 34 Points - {307.26186035494931, 188.16336416086213} - {348.23813925371286, 161.83663549730926} + {183, 144} + {323.99999356269836, 144} Style + shadow + + Draws + NO + stroke HeadArrow FilledArrow Legacy - - LineType - 1 - TailArrow - 0 - - - Tail - - ID - 4 - - - - Class - LineGraphic - Head - - ID - 4 - - ID - 9 - Points - - {210.7618557053124, 161.83663369834431} - {251.73814196284329, 188.16336833929338} - - Style - - stroke - - HeadArrow - FilledArrow - Legacy - + LineType 1 TailArrow @@ -574,119 +232,12 @@ - Class - LineGraphic - Head - - ID - 1 - - ID - 8 - Points - - {210.57342004857193, 125.99870008392107} - {251.92658045882592, 99.001300352172606} - - Style - - stroke - - HeadArrow - FilledArrow - Legacy - - LineType - 1 - TailArrow - 0 - - - Tail - - ID - 3 - - - - Class - LineGraphic - Head - - ID - 4 - - ID - 7 - Points - - {293.5556962717904, 106.37834049073271} - {315.5, 146} - {294.53436892191536, 180.94271846347439} - - Style - - stroke - - HeadArrow - FilledArrow - Legacy - - LineType - 1 - TailArrow - 0 - - - Tail - - ID - 1 - - - - Class - LineGraphic - Head - - ID - 1 - - ID - 6 - Points - - {263.99039783812128, 181.10804591303423} - {239, 141} - {262.95578717906915, 105.50994491989755} - - Style - - stroke - - HeadArrow - FilledArrow - Legacy - - LineType - 1 - TailArrow - 0 - - - Tail - - ID - 4 - - - Bounds - {{340, 117}, {72, 54}} + {{287.99999356269836, 117}, {72, 54}} Class ShapedGraphic ID - 5 + 33 Shape Circle Style @@ -700,44 +251,14 @@ Text Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} {\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 -\f0\fs24 \cf0 csD} +\f0\fs24 \cf0 cs1} VerticalPad - 0 - - - - Bounds - {{243.5, 179}, {72, 54}} - Class - ShapedGraphic - ID - 4 - Shape - Circle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 csC} - VerticalPad - 0 + 0.0 @@ -760,103 +281,14 @@ Text Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} {\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 -\f0\fs24 \cf0 csA} - VerticalPad - 0 - - - - Bounds - {{243.5, 54}, {72, 54}} - Class - ShapedGraphic - ID - 1 - Shape - Circle - Style - - shadow - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 csB} +\f0\fs24 \cf0 cs0} VerticalPad - 0 - - - - Bounds - {{197.56640999999999, 98.625}, {45.933593999999999, 18.375}} - Class - ShapedGraphic - ID - 25 - Magnets - - {1, 1} - {1, -1} - {-1, -1} - {-1, 1} - {0, 1} - {0, -1} - {1, 0} - {-1, 0} - {-0.5, -0.233518} - {-0.49144199, 0.26006298999999999} - {0.50711799000000002, -0.22408600000000001} - {0.50711799000000002, 0.26717900999999999} - {-0.27430999, -0.47402799000000001} - {0.27977999999999997, -0.47847801000000001} - {0.29393801000000003, 0.54304397000000004} - {-0.28623198999999999, 0.55380397999999997} - - Shape - Rectangle - Style - - fill - - Draws - NO - - shadow - - Draws - NO - - stroke - - Draws - NO - - - Text - - Text - {\rtf1\ansi\ansicpg1252\cocoartf1265 -\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc - -\f0\fs24 \cf0 goto} - VerticalPad - 0 + 0.0 @@ -895,6 +327,8 @@ 0.0 layoutEngine dot + neatoLineLength + 0.20000000298023224 neatoSeparation 0.0 twopiSeparation @@ -907,7 +341,7 @@ MasterSheets ModificationDate - 2014-02-04 06:54:28 +0000 + 2016-02-14 19:41:55 +0000 Modifier utah NotesVisible @@ -942,8 +376,8 @@ NSPrintReverseOrientation - int - 0 + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG NSRightMargin @@ -980,29 +414,22 @@ CurrentSheet 0 - ExpandedCanvases - - - name - Canvas 1 - - + Expanded_Canvases + Frame - {{398, 45}, {693, 938}} - ListView + {{507, -237}, {989, 938}} + ShowInfo - OutlineWidth - 142 - RightSidebar - ShowRuler Sidebar SidebarWidth - 120 + 200 + TopSlabHeight + 250 VisibleRegion - {{0, 0}, {558, 783}} + {{0, 0}, {475, 780}} Zoom 1 ZoomValues diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/codesegment.pdf Binary file paper/fig/codesegment.pdf has changed diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/codesegment.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/codesegment.xbb Mon Feb 15 07:30:44 2016 +0900 @@ -0,0 +1,8 @@ +%%Title: ./fig/codesegment.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 305 85 +%%HiResBoundingBox: 0.000000 0.000000 305.000000 85.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Mon Feb 15 04:43:07 2016 + diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/factorial.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/factorial.graffle Mon Feb 15 07:30:44 2016 +0900 @@ -0,0 +1,706 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle6 + 169.5.0.253125 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559.20001220703125, 782.79998779296875}} + Class + SolidGraphic + ID + 2 + Style + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2011-11-12 11:03:25 +0000 + Creator + Nobuyasu Oshiro + DisplayScale + 1 in = 1.00000 in + GraphDocumentVersion + 12 + GraphicsList + + + Bounds + {{337.67999245226383, 177.89999766647816}, {103, 24}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Size + 11 + + ID + 44 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs22 \cf0 goto print_factorial} + + Wrap + NO + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 42 + + ID + 43 + Points + + {325.49999356269836, 144} + {325.49999356269836, 235.79999533295631} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 33 + + + + Bounds + {{287.99999356269836, 208.79999533295631}, {75, 54}} + Class + ShapedGraphic + ID + 42 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 + +\f0\fs24 \cf0 print_\ +factorial} + VerticalPad + 0.0 + + + + Bounds + {{86.459999710321426, 93}, {75, 24}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Size + 11 + + ID + 41 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs22 \cf0 goto factorial} + + Wrap + NO + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 3 + + ID + 40 + Points + + {48.959999710321426, 144} + {183, 144} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 38 + + + + Bounds + {{12.959999710321426, 117}, {72, 54}} + Class + ShapedGraphic + ID + 38 + Style + + shadow + + Draws + NO + + stroke + + Cap + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 + +\f0\fs24 \cf0 main} + VerticalPad + 0.0 + + + + Bounds + {{284.99999356269836, 45.359998986124992}, {81, 24}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Size + 11 + + ID + 37 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs22 \cf0 goto factorial0} + + Wrap + NO + + + Bounds + {{208.49999356269836, 106.55999761819839}, {81, 24}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Size + 11 + + ID + 36 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs22 \cf0 goto factorial0} + + Wrap + NO + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 33 + + ID + 35 + Points + + {325.49999356269836, 144} + {294.49999356269836, 93.08203125} + {351.578125, 84.4765625} + {325.49999356269836, 144} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 33 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 33 + + ID + 34 + Points + + {183, 144} + {325.49999356269836, 144} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 3 + + + + Bounds + {{287.99999356269836, 117}, {75, 54}} + Class + ShapedGraphic + ID + 33 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 + +\f0\fs24 \cf0 factorial 0} + VerticalPad + 0.0 + + + + Bounds + {{147, 117}, {72, 54}} + Class + ShapedGraphic + ID + 3 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\partightenfactor0 + +\f0\fs24 \cf0 factorial} + VerticalPad + 0.0 + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + Layer 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoLineLength + 0.20000000298023224 + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2016-02-14 19:48:42 +0000 + Modifier + utah + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595.20001220703125, 841.79998779296875} + + NSPrintReverseOrientation + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + Canvas 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + Expanded_Canvases + + Frame + {{87, 100}, {989, 938}} + ShowInfo + + ShowRuler + + Sidebar + + SidebarWidth + 200 + TopSlabHeight + 250 + VisibleRegion + {{0, 0}, {475, 780}} + Zoom + 1 + ZoomValues + + + Canvas 1 + 1 + 1 + + + + + diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/factorial.pdf Binary file paper/fig/factorial.pdf has changed diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/factorial.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/factorial.xbb Mon Feb 15 07:30:44 2016 +0900 @@ -0,0 +1,8 @@ +%%Title: ./fig/factorial.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 449 238 +%%HiResBoundingBox: 0.000000 0.000000 449.000000 238.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Mon Feb 15 04:49:19 2016 + diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/metaCS.pdf Binary file paper/fig/metaCS.pdf has changed diff -r bea98599d11f -r 3afb4bfe1100 paper/fig/metaCS.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/metaCS.xbb Mon Feb 15 07:30:44 2016 +0900 @@ -0,0 +1,8 @@ +%%Title: ./fig/metaCS.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 31 511 515 732 +%%HiResBoundingBox: 30.601520 511.100000 515.413800 732.012800 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Mon Feb 15 05:21:55 2016 + diff -r bea98599d11f -r 3afb4bfe1100 paper/gotoWithEnv.tex --- a/paper/gotoWithEnv.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/gotoWithEnv.tex Mon Feb 15 07:30:44 2016 +0900 @@ -1,16 +1,15 @@ \chapter{環境付き継続の実装} -環境付き継続を行うためには \_\_return, \_\_environment という特殊変数を用い, この実装にはいくつかの方法がある. GCC コンパイラでは nested function を, 以前の LLVM, Clang CbC コンパイラでは setjmp, longjmp を使用して実装を行っていた. これら二つの方法に加えて本研究では LLVM builtin の setjmp, longjmp を利用する実装を行った. 本章ではそれぞれに実装について述べる. +環境付き継続を行うためには \_\_return, \_\_environment という変数を用いる. 環境とはスタックの状態を指す. C の関数の環境を持って軽量継続を行い, 保存した環境に戻すことで, 環境を持たない code segment から関数に戻ることが可能になる. code segment から C の関数に戻るために保存しなければならないのはスタックポインタとフレームポインタのふたつである. 環境付き継続の実装にはいくつかの方法がある. GCC コンパイラでは nested function を, 以前の LLVM Clang CbC コンパイラでは setjmp, longjmp を使用して実装を行っていた. これら二つの方法に加えて本研究では LLVM builtin の setjmp, longjmp を利用する実装を行った. 本章ではそれぞれに実装について述べる. \section{nested function による実装} -GCC 上に実装した CbC コンパイラでは nested function を利用して環境付き継続の実装を行った. 実装の詳細は本論文の趣旨から大きくそれるので, どのようにじつげんしているかについてのみ記す. +GCC 上に実装した CbC コンパイラでは nested function を利用して環境付き継続の実装を行った\cite{gcc}. 実装の詳細は本論文の趣旨から大きくそれるので, どのようにじつげんしているかについてのみ記す. -具体的には, リスト\ref{code:cbcreturn2}の関数funcBをコンパイラは次のコード\ref{code:nestedcode}の様に解釈し, 内部コードセグメントを自動生成する. +具体的には, リスト\ref{code:cbcreturn2}の関数funcBをコンパイラは次のコード\ref{code:nestedcode}の様に解釈し, 内部 code segment を自動生成する. +6 行目から 20 行目が GCC により追加される処理である. 内部 code segment \verb|inner|は受け取った引数を関数の返り値として保持し, ラベル\verb|label|に jumpする. この時点で内部 code segment を抜けて元の関数 int の環境に復帰する. -6 行目から 20 行目が GCC により追加される処理である. 内部コードセグメント\verb|inner|は受け取った引数を関数の返り値として保持し, ラベル\verb|label|に jumpする. この時点で内部コードセグメントを抜けて元の関数 int の環境に復帰する. - -さらに jump 先も GCC により自動で追加される. しかしこの jump 先は\verb|inner|以外からは実行してはならない. そのため条件式が真にならない if 文で囲み、実行を回避している. jump 先での処理は, \verb|inner|内で代入された値を持ってリターンするのみである. +さらに jump 先も GCC により自動で追加される. しかしこの jump 先は\verb|inner|以外からは実行してはならない. そのため条件式が真にならない if 文で囲み, 実行を回避している. jump 先での処理は, \verb|inner|内で代入された値を持って reutnr するのみである. \begin{lstlisting}[frame=lrbt,label=code:cbcreturn2,caption={環境付き継続の例}] __code cs(int retval,__code(*ret)(int,void *),void *env){ @@ -23,7 +22,7 @@ } \end{lstlisting} -\begin{lstlisting}[frame=lrbt,label=code:nestedcode,caption={内部での解釈}] +\begin{lstlisting}[frame=lrbt,label=code:nestedcode,caption={GCC 環境付き継続の内部での解釈}] __code cs(int retval,__code(*ret)(int,void *),void *env){ goto ret(n, env); } @@ -61,7 +60,7 @@ return 0; } \end{lstlisting} -\begin{lstlisting}[frame=lrbt,label=autoCodeGenA,caption={内部での解釈}] +\begin{lstlisting}[frame=lrbt,label=autoCodeGenA,caption={LLVM clang の内部での解釈}] #include struct CbC_env { diff -r bea98599d11f -r 3afb4bfe1100 paper/introduciton.tex --- a/paper/introduciton.tex Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/introduciton.tex Mon Feb 15 07:30:44 2016 +0900 @@ -1,7 +1,30 @@ \chapter{研究目的} -プログラミングに用いられる単位として関数, クラス, オブジェクト等が存在するが, これらは容易に分割, 結合することは出来ない. また, アセンブリ言語は分割, 結合を行うことは容易であるが, これのみでプログラムを記述することは困難である. +プログラムを記述する際, 本来行いたい処理の他にも記述しなけらばならない処理が存在する. malloc 等によるメモリの管理, スレッドの待ち合わせやネットワークの管理, エラーハンドリング等がこれにあたる. +これらの計算は meta computation と呼ばれる. + +meta computation を通常の計算から切り離して記述するためには処理を細かく分割する必要があるが, 関数やクラス等の単位を容易に分割することは出来ない. + +そこで当研究室では meta computation を柔軟に記述するためのプログラミング言語の単位として code segment, data segment という単位を提案している. +code segment, data segment はそれぞれ処理の単位, データの単位である. code segment は関数に比べ細かく分割されているので meta computation をより柔軟に記述することが出来る. +code segment, data segment にはそれぞれメタレベルの単位である meta code segment, meta data segment が存在し, それらを用いて meta computation を実現する. + +これらの単位を用いるものには並列プログラミングフレームワーク Cerium\cite{cerium}, 分散ネットワークフレームワーク Alice\cite{akamine:2011a}, 並列フレームワーク Gears OS\cite{gears}等が存在する. + +プログラミング言語 Continuation based C (CbC)\cite{kono:2000} は処理の単位に code segment を用いるプログラミング言語であり, Gears OS は CbC で記述されている. -これらの問題を解決するべく, 設計された単位が code segment, data segment である. code segment, data segment は分割, 結合を容易に行うことのできる処理, データの単位として設計されたものであり, 並列プログラミングフレームワーク Cerium\cite{cerium}, 分散ネットワークフレームワーク Alice\cite{akamine:2011a}, プログラミング言語 Continuation based C (CbC)\cite{simabukuro:2000} はこれらの単位を用いている. +%また, CbC は C の関数と併せて使用することが出来る. ただし code segment と C の関数の間を自由に行き来するためには環境付き継続という機能を用いる必要がある. + +CbC のコンパイラは Micro-c をベースにしたものと GCC をベースにしたもの\cite{gcc}に加え, 2014年の研究で LLVM, clang をベースにしたもの\cite{cbclang}が存在する. 本研究では, LLVM clang をベースとした CbC コンパイラのさらなる最適化, 機能の追加, Gears OS の記述をサポートする機能の設計を行った. + +また, C の関数と code segment の間を自由に行き来するための機能である環境付き継続の速度を大幅に向上させることにも成功した. + +\section{論文の構成} -CbC のコンパイラは micro-c をベースにしたものと GCC をベースにしたものに加え, 2014年の研究で LLVM, clang をベースにしたものが存在する. 本研究では, LLVM, clang をベースとした CbC コンパイラにさらなる最適化, 機能の追加, Gears OS の記述をサポートする機能の設計を行った. +本論文では, はじめに Continuation based C の概要を CbC のコード例とともに説明する. +第 3 章では LLVM と clang の基本的な構造, 中間表現, 最適化の一つである tail call elimination について説明する. +第 4 章では LLVM と clang 上に CbC コンパイラを実装する方法について述べる. +第 5 章では C の関数と code segment を行き来する環境付き継続の実装について, Micro-C, GCC, LLVM と clang それぞれの方法を紹介する. +第 6 章では Gears OS の記述のための構文について述べる. Gears OS では code segment の他に data segment, meta code segment, meta data segment を用いる. +第 7 章では今回の研究で改良した CbC コンパイラ性能を評価する. 評価は各コンパイラとの環境付き継続の速度の比較と C と Scheme との実行速度の比較にて行う. + \pagenumbering{arabic} diff -r bea98599d11f -r 3afb4bfe1100 paper/master_paper.bib --- a/paper/master_paper.bib Sun Feb 14 20:07:43 2016 +0900 +++ b/paper/master_paper.bib Mon Feb 15 07:30:44 2016 +0900 @@ -16,11 +16,11 @@ year = 2011 } -@article{simabukuro:2000, -author = "河野 真治 and 島袋 仁", -title = "C with Continuation と、そのPlayStationへの応用", -journal = "情報処理学会 システムソフトウェアとオペレーティング・システム研究会(OS)", -month = "May", +@article{kono:2000, +author = "河野 真治", +title = "A Continuation based Programming Language for Embedded Systems", +journal = "IPSJ Computer System Symposium", +month = "November", year = 2000 } @@ -43,3 +43,27 @@ title = "LLVM Language Reference Manual.", url = "http://llvm.org/docs/LangRef.html" } + +@article{gears, +author = "小久保翔平 伊波立樹 河野真治", +title = "Monad に基づくメタ計算を基本とする Gears OS の設", +journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", +month = "May", +year = 2015 +} + +@article{gcc, +author = "与儀健人 河野真治", +title = "Continuation based CコンパイラのGCC-4.2による実装", +journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", +month = "April", +year = 2008 +} + +@article{cbclang, +author = "徳森海斗 河野真治", +title = "Continuation based Cの LLVM/clang 3.5 上の実装について", +journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)", +month = "May", +year = 2014 +} diff -r bea98599d11f -r 3afb4bfe1100 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed