# HG changeset patch # User Nobuyasu Oshiro # Date 1339430607 -32400 # Node ID bcacfe595c2a2c50416081a5c73515d1f38c187d # Parent 635448a197ac672e7055c95776a3dc80d31a25b4 add memo.txt diff -r 635448a197ac -r bcacfe595c2a paper/aplas2012.tex --- a/paper/aplas2012.tex Mon Jun 11 14:29:35 2012 +0900 +++ b/paper/aplas2012.tex Tue Jun 12 01:03:27 2012 +0900 @@ -46,6 +46,28 @@ \section{Continuation based C} \section{recursive type syntax} +We implemeted \verb+__rectype+ syntax on GCC. +\verb+__rectype+ syntax is declare a recursive type. + +\subsection{What is recursive type} +Recursive type is + + + +\begin{lstlisting} +__code csA( __code (*p)( __code (*)( __code (*)( __code )))) { + goto p(csB); +} +\end{lstlisting} + + +This example is rectype syntax: + +\begin{lstlisting} +__code csA( __rectype *p) { + goto p(csB); +} +\end{lstlisting} \begin{figure}[htpb] @@ -65,31 +87,8 @@ \end{minipage} \end{figure} -\begin{table}[htpb] -\centering -\small -\begin{tabular}{|l|r|r|r|} \hline -(unit: s) & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline -Micro-C(32bit) & 9.93 & 6.31 & 7.18 \\ \hline -Micro-C(64bit) & 5.03 & 5.12 & 5.00 \\ \hline \hline -GCC -O3(32bit) & 2.52 & 2.34 & 1.53 \\ \hline -GCC -O3(64bit) & 1.80 & 1.20 & 1.44 \\ \hline -\end{tabular} -\caption{Micro-C, GCC bench mark (in sec)} -\label{tab:mc,gcc,compare} -\end{table} -\begin{lstlisting} -__code fibonacci( __code (*p)( __code (*)( __code (*)( __code )))) { - goto p(fibonacci2); -\end{lstlisting} - - -\begin{lstlisting} -__code fibonacci(__rectype *p, int num, int count, int result, int prev) { -\end{lstlisting} - \begin{lstlisting} struct interface { @@ -110,6 +109,37 @@ + + +\begin{lstlisting} +__code fibonacci(__rectype *p, int num, int count, int result, int prev) { +\end{lstlisting} + + + + + + +\begin{table}[htpb] +\centering +\small +\begin{tabular}{|l|r|r|r|} \hline +(unit: s) & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline +Micro-C(32bit) & 9.93 & 6.31 & 7.18 \\ \hline +Micro-C(64bit) & 5.03 & 5.12 & 5.00 \\ \hline \hline +GCC -O3(32bit) & 2.52 & 2.34 & 1.53 \\ \hline +GCC -O3(64bit) & 1.80 & 1.20 & 1.44 \\ \hline +\end{tabular} +\caption{Micro-C, GCC bench mark (in sec)} +\label{tab:mc,gcc,compare} +\end{table} + + + + + + + \bibliographystyle{junsrt} \bibliography{cbc} \nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals} diff -r 635448a197ac -r bcacfe595c2a paper/memo.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/memo.txt Tue Jun 12 01:03:27 2012 +0900 @@ -0,0 +1,261 @@ +We have implemented Continuation based C (CbC).CbC is an extension of C, which has parameterized goto statement. +It is useful for finite state automaton or many core tasks. +Goto statement is a way to force tail call elimination. +The destination of goto statement is called Code Segment, which is actually a normal function of C. +To represent recursive function call, the type system of C is not enough, because +it has no recursive types. +We introduce __rectype keyword for recursive type, and it is implemented in GCC-4.6.0. +We will compare the conventional methods, __rectype keyword and a method using C structure. +Also we show usage of CbC and it's benchmark. + + + + + + +・__rectype と GCC-4.6.0 における実装の説明 +・普通に宣言した場合と __rectype , 構造体を使用した場合に比較 +・それと CbC のベンチマークをみせる。 + + + + +・Continuation based C + +・・CbC によるプログラミング +(なぜrectypeが必要になったのかを書く。1.引数の型チェックを行いたかった 2.Cの構文で宣言するとソースが長い、) +CbC では継続を基本としている。継続は goto の後にコードセグメントと引数をかくことで行われる。 +CbC においてはループ処理もこの goto による継続を用いて行われる。以下に loop の例を示す。 + + + + + +今回我々は__rectype 構文を新たに実装した。 +__rectype はリカーシブタイプを宣言するものである。 +__rectype は引数に使われる型で、宣言中の引数の型と同じ型を持つ関数ポインタであることを示す。 + +//ここでいうリカーシブタイプとは、同じ引数の型を持つタイプのことである。 +//C においては、以下のようなリカーシブタイプを宣言することはできない。 + + + +void func( func *p ) + +関数ポインタを引数にもつ関数がある時、以下のように宣言される。 + +__code csA( void (*p)() ) + +しかし、この宣言では p を使用する場合、p の引数の型チェックが行われない。 +p の引数の型チェックを行いたい時は以下の様に宣言しなければならない。 + +__code csA( __code (*p)(void *) ) { + goto p(csB); +} + + +これで p の引数の型チェックは行われるようになる。 +だが、これでもまだ正しくはない。なぜなら、p が引数として受け取った関数も引数を持つからである。 +引数で受け取る関数ポインタがそれぞれ引数で関数ポインタを持つ場合、以下のような宣言になる。 + +__code csA( __code (*p)(__code (*)(__code (*)( __code (*)( __code (*)(,,) ))))) + +(,, の部分には同じような宣言が続いていく。) +C において引数で再帰的な関数ポインタを受け取る場合は上記のような宣言になり。宣言しきることができない。 +(再帰的な関数ポインタ…?) + + +そこで、__rectype 構文により以下のような宣言を行えるようにした。 + +__code csA( __rectype *p ) + + +この時、*p は csA のポインタを表している。 + + + +・__rectype の実装方法 +__rectype の実装は、Generic Tree を書き換えることで行なっている。 +GCC では~のプログラムは次のようにGeneric Treeが作成される。 +void func(void (*)() ); + +fig1. + +TREE_LIST には引数の情報が入っている。第一引数にはFUNCTION_TYPEへのポインタがさされているのがわかる。(第二引数にVOID_TYPEがあるのは固定長引数の為) +この第一引数が指すFUNCTION_TYPEを自分自身へと書き換えることで __rectype は実装されている。 + +GCC 内部に実際に書き込んであるコードは以下になる。 +gcc/c-decl.c + + cbc_return_f = NULL_TREE; + cbc_env = NULL_TREE; + if ( declspecs->typespec_word == cts_CbC_code ) + { + cbc_set_codesegment(decl1); + /* implementation of rectype */ + tree func_tree = TREE_TYPE(decl1); + // parm is PARM_DECL + tree parm = declarator->u.arg_info->parms; + while (parm) { + tree tmptype = parm; + if (!IS_RECTYPE(TREE_TYPE(tmptype))) { + parm = TREE_CHAIN(parm); + continue; + } + tree t = TREE_TYPE(tmptype); + while (TREE_CODE(t) == POINTER_TYPE) { + tmptype = t; + t= TREE_TYPE(tmptype); + } + TREE_TYPE(tmptype) = func_tree; + parm = TREE_CHAIN(parm); + } + } + + +decl1 は宣言中の自分自身にあたる変数である。 + + + +・__rectype 実装による問題 +warning チェックによる無限再帰。 +__rectype を上記の方法で実装を行った所、以下の呼び出しをおこうとした場合 compile 中に segmen tation fault が発生した。 + +__code csA(__rectype *p) { + goto p(3); +} + +これは GCC においては以下の構文と同じである。 +void func(void (*p)(void*)) { + p(3); +} + +上記の場合、GCC の内部では宣言された p の正しい引数の型を調べるためにポインタが辿られていく。 +その後、int の 3 が void の pointer へと convert(cast) される。 +しかし、__rectype の実装では pointer の先は csA となる。その csA の第一引数が関数ポインタだった場合その引数の型もみるのだが、この場合それが csA である。csA の引数の型をみにいき続けてしまい無限再帰となってしまっていた。 +この問題を解決するために、現在の実装では __rectype で宣言されたモノの型を辿らないようにしている。 +以下はその実装の部分である。 +gcc/c-family/c-pretty-print.c + +static void +pp_c_abstract_declarator (c_pretty_printer *pp, tree t) +{ + if (TREE_CODE (t) == POINTER_TYPE) + { + if (TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE + || TREE_CODE (TREE_TYPE (t)) == FUNCTION_TYPE) + pp_c_right_paren (pp); +#ifndef noCbC + if(IS_RECTYPE(t)) return; +#endif + t = TREE_TYPE (t); + } + + pp_direct_abstract_declarator (pp, t); +} + + +上記のコードの変数 t には引数の情報が入っている。 +~行目の t = TREE_TYPE (t); におり、 t が pointer タイプだった場合そのタイプを辿るようになっているのが分かる。 +ここで、もし t が __rectype で宣言されたのならただ return を行うという処理を追加した。 +この実装により warning チェックの際の無限再帰を抑えることができた。 + + + + +・構造体を使用してのリカーシブタイプ +リカーシブタイプの問題は引数を構造体にすることでも解決できる。 +以下はその例である。 + +struct interface { + __code (*next)(struct interface); +}; + +__code csA(struct interface p) { + : + goto p.next(ds); +} + +int main() { + struct interface ds = { print }; + goto csA(ds); + return 0; +} + +構造体で包むことで先に上げた関数ポインタの引数の型チェックの問題はクリアされる。 + + + +・GCC 版 CbC コンパイラのベンチマーク： +最後に、GCC 版 CbC コンパイラのベンチマークをMicro-C版 CbC と比較しながら以下に示す。 +使用したプログラムは conv1 プログラムで、内部では加算と継続を交互に行なっている。 + + + + + + + + + + + +実装の確認と問題： +・関数ポインタ中の引数の型に__rectype +__code csA(__code (*p)(__rectype*)) { + goto p(csA); +} + +特に問題なく実行できる。 + + +・typedef の問題 +//typedef __code (*csPtr)(__rectype); +typedef __code (*csPtr)(__rectype*); // error + +上記の場合、宣言自体失敗する。 +修正が必要。 + +・struct 内部での __rectype +struct interface { + __rectype *next; +}; + +__code csA(struct interface p) { + struct interface ds = { csA }; + goto p.next(ds); +} + +void main1() { + struct interface ds = { print }; + goto csA(ds); +} + +この時、errorがでる…が、一応 struct の宣言自体は通っている。 +struct の宣言時に __rectype がきたらエラーが出るようにすべき… + + + + + + + + + + + + + + + + + + + + + + + + + +