Mercurial > hg > Papers > 2012 > aplas
annotate paper/rectype.ind @ 21:88899c193e6d
modify
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 15 Jun 2012 15:59:00 +0900 |
parents | 203699cf5384 |
children | f1839aae06dc |
rev | line source |
---|---|
11 | 1 -title: Recursive type syntax in Continuation based C |
2 | |
3 \newcommand{\rectype}{{\tt \_\_rectype}} | |
16
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
4 \newcommand{\code}{{\tt \_\_code}} |
11 | 5 |
6 --author: Shinji Kono, Nobuyasu Oshiro | |
7 | |
8 --abstract: | |
9 We have implemented Continuation based C (CbC). | |
10 CbC is an extension of C, which has parameterized goto statement. | |
11 It is useful for finite state automaton or many core tasks. | |
12 Goto statement is a way to force tail call elimination. | |
13 The destination of goto statement is called Code Segment, which is actually a normal function of C. | |
14 To represent recursive function call, the type system of C is not enough, because | |
15 it has no recursive types. | |
16 We introduce \rectype keyword for recursive type, and it is implemented in GCC-4.6.0. | |
17 We will compare the conventional methods, \rectype keyword and a method using C structure. | |
18 Also we show usage of CbC and it's benchmark. | |
19 | |
20 | |
21 --Continuation based C | |
22 | |
23 CbC's basic programming unit is a code segment. It is not a subroutine, but it | |
24 looks like a function, because it has input and output. We can use C struct | |
25 as input and output interfaces. | |
26 | |
27 struct interface1 { int i; }; | |
28 struct interface2 { int o; }; | |
29 | |
30 __code f(struct interface1 a) { | |
31 struct interface2 b; b.o=a.i; | |
32 goto g(b); | |
33 } | |
34 | |
35 In this example, a code segment | |
36 \verb+f+ has \verb+input a+ and sends \verb+output b+ to a code segment \verb+g+. | |
37 There is no return from code segment \verb+b+, \verb+b+ should call another | |
38 continuation using \verb+goto+. Any control structure in C is allowed in CwC | |
39 language, but in case of CbC, we restrict ourselves to use \verb+if+ statement | |
40 only, because it is sufficient to implement C to CbC translation. In this case, | |
41 code segment has one input interface and several output interfaces (fig.\ref{code}). | |
42 | |
43 \includegraphics[width=6cm]{ | |
44 \begin{figure}[htb] | |
45 \begin{center} | |
46 \includegraphics[width=6cm]{figure/code.pdf} | |
47 \caption{code} | |
48 \end{center} | |
49 \label{code} | |
50 \end{figure} | |
51 | |
52 | |
53 | |
54 \verb+__code+ and parameterized global goto statement is an extension of | |
55 Continuation based C. Unlike \verb+C--+ \cite{cminusminus}'s parameterized goto, | |
56 we cannot goto into normal C function. | |
57 | |
58 --Intermix with C | |
59 | |
60 In CwC, we can go to a code segment from a C function and we can call C functions | |
61 in a code segment. So we don't have to shift completely from C to CbC. The later | |
62 one is straight forward, but the former one needs further extensions. | |
63 | |
64 void *env; | |
65 __code (*exit)(int); | |
66 | |
67 __code h(char *s) { | |
68 printf(s); | |
69 goto (*exit)(0),env; | |
70 } | |
71 | |
72 int main() { | |
73 env = __environment; | |
74 exit = __return; | |
75 goto h("hello World\n"); | |
76 } | |
77 | |
78 In this hello world example, the environment of \verb+main()+ | |
79 and its continuation is kept in global variables. The environment | |
80 and the continuation can be get using \verb+__environment+, | |
81 and \verb+__return+. Arbitrary mixture of code segments and functions | |
82 are allowed (in CwC). The continuation of \verb+goto+ statement | |
83 never returns to original function, but it goes to caller of original | |
84 function. In this case, it returns result 0 to the operating system. | |
85 | |
86 | |
87 --What's good? | |
88 | |
89 CbC is a kind of high level assembler language. It can do several | |
90 original C language cannot do. For examples, | |
91 | |
92 {\small | |
93 \begin{verbatim} | |
94 Thread Scheduler | |
95 Context Switch | |
96 Synchronization Primitives | |
97 I/O wait semantics | |
98 | |
99 \end{verbatim} | |
100 } | |
101 | |
102 are impossible to write in C. Usually it requires some help of | |
103 assembler language such as \verb+__asm+ statement extension which is | |
104 of course not portable. | |
105 | |
106 --Scheduler example | |
107 | |
108 We can easily write these things in CbC, because | |
109 CbC has no hidden information behind the stack frame of C. | |
110 A thread simply go to the scheduler, | |
111 | |
112 goto scheduler(self, task_list); | |
113 | |
114 | |
115 and the scheduler simply pass the control to the next | |
116 thread in the task queue. | |
117 | |
118 code scheduler(Thread self,TaskPtr list) | |
119 { | |
120 TaskPtr t = list; | |
121 TaskPtr e; | |
122 list = list->next; | |
123 goto list->thread->next(list->thread,list); | |
124 } | |
125 | |
126 Of course it is a simulator, but it is an implementation | |
127 also. If we have a CPU resource API, we can write real multi | |
128 CPU scheduler in CbC. | |
129 | |
130 This is impossible in C, because we cannot access the hidden | |
131 stack which is necessary to switch in the scheduler. In CbC, | |
132 everything is visible, so we can switch threads very easily. | |
133 | |
134 This means we can use CbC as an executable specification | |
135 language of OS API. | |
136 | |
137 --Self Verification | |
138 | |
139 Since we can write a scheduler in CbC, we can also enumerate | |
140 all possible interleaving of a concurrent program. We have | |
141 implement a model checker in CwC. CbC can be a self verifiable | |
142 language\cite{kono08a}. | |
143 | |
144 SPIN\cite{holzmann97model} is a very reliable model checker, but it have to | |
145 use special specification language PROMELA. We cannot directly | |
146 use PROMELA as an implementation language, and it is slightly | |
147 difficult to study its concurrent execution semantics including | |
148 communication ports. | |
149 | |
150 There are another kind of model checker for real programming | |
151 language, such as Java PathFinder\cite{havelund98model}. Java PathFinder use | |
152 Java Virtual Machine (JVM) for state space enumeration which | |
153 is very expensive some time. | |
154 | |
155 In CbC, state enumerator itself is written in CbC, and its concurrency | |
156 semantics is written in CbC itself. Besides it is very close | |
157 to the implementation. Actually we can use CbC as an implementation | |
158 language. Since enumerator is written in the application itself, we | |
159 can perform abstraction or approximation in the application specific | |
160 way, which is a little difficult in Java PathFinder. It is possible | |
161 to handle JVM API for the purpose, although. | |
162 | |
163 We can use CPS transformed CbC source code for verification, but | |
164 we don't have to transform all of the source code, because CwC | |
165 supports all C constructs. (But not in C++... Theoretically it is | |
166 possible with using cfront converter, it should be difficult). | |
167 | |
168 | |
169 --As a target language | |
170 | |
171 Now we have GCC implementation of CbC, it runs very fast. Many | |
172 popular languages are implemented on top of C. Some of them | |
173 uses very large switch statement for the byte code interpreter. | |
174 We don't have to use these hacks, when we use CbC as an implementation | |
175 language. | |
176 | |
177 CbC is naturally similar to the state charts. It means it is very | |
178 close to UML diagrams. Although CbC does not have Object Oriented | |
179 feature such as message passing nor inheritance, which is not | |
180 crucial in UML. | |
181 | |
182 | |
14 | 183 --Recursive type syntax |
184 | |
185 CbC's program pass next pointer of code segment on argument. | |
186 It is passed as follows. | |
187 | |
188 __code csA( __code (*p)() ) { | |
189 goto p(csB); | |
190 } | |
191 | |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
192 p is next pointer of codesegment. |
14 | 193 But, This declarationd is not right. |
194 Because p have arguments. | |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
195 We wanted to the same type of p's arguments as type of csA's arguments. |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
196 Right declaration is as follows. |
14 | 197 |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
198 __code csA( __code (*p)( __code (*)( __code (*)( __code *)))) { |
14 | 199 goto p(csB); |
200 } | |
201 | |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
202 The syntax of C Must be declared recursively. |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
203 The following declaration if it may be that the type checking of p. |
11 | 204 |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
205 __code csA( __code (*p)( __code )) { |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
206 goto p(csB); |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
207 } |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
208 |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
209 However this declaration is long. |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
210 Therefore we implemented \rectype syntax in CbC on GCC. |
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
211 |
11 | 212 \rectype syntax is declare a recursive type. |
15
68d2c32f74cf
modify explanation of rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
213 This example is using \rectype syntax. |
11 | 214 |
215 __code csA( __rectype *p) { | |
216 goto p(csB); | |
217 } | |
218 | |
219 *p represent pointer of csA at \ref{code:rectype} . | |
220 p's argument type is same csA that function pointer. | |
221 | |
222 | |
21 | 223 --Problems with implementation of \rectype. |
224 Segmentation fault has occurred in the following program on compile. | |
225 | |
226 __code csA(__rectype *p) { | |
227 goto p(3); | |
228 } | |
229 | |
230 The above code is the wrong argument of p. | |
231 The argument convert the above code is carried out in the GCC. | |
232 3 of type int that to a pointer type conversions are made of code segment. | |
233 | |
234 | |
235 | |
236 | |
237 | |
16
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
238 --How to implement \rectype |
17
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
239 \rectype syntx is implemented overriding AST. |
16
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
240 First, \rectype syntax make Tree same \code(\ref{fig:tree1}). |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
241 Second, tree was created to be rectype flag. |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
242 Thrid, to override AST(\ref{fig:tree2}). |
16
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
243 |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
244 \begin{figure}[htpb] |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
245 \begin{minipage}{0.5\hsize} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
246 \begin{center} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
247 \scalebox{0.35}{\includegraphics{figure/tree1.pdf}} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
248 \end{center} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
249 \caption{AST of function pointer} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
250 \label{fig:tree1} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
251 \end{minipage} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
252 \begin{minipage}{0.2\hsize} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
253 \begin{center} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
254 \scalebox{0.35}{\includegraphics{figure/tree2.pdf}} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
255 \end{center} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
256 \caption{AST of \rectype} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
257 \label{fig:tree2} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
258 \end{minipage} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
259 \end{figure} |
b5bef0479ef5
modify how to implement rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
260 |
17
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
261 Above AST(\ref{fig:tree2}) is made by syntax of \verb+__code csA(__rectype *p)+ . |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
262 TREE_LIST have infomation of argument. |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
263 First TREE_LIST represent that argument is function pointer(\verb+__code (*p)()+) . |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
264 Second TREE_LIST represent that csA is Fixed-length argument. |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
265 First TREE_LIST is connected with POINTER_TYPE. |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
266 POINTER_TYPE have pointer of function(FUNCTION_TYPE). |
02bd9a41010f
modify How to implement rectype syntax
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
267 We have to override it in the pointer of csA. |
11 | 268 |
269 | |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
270 -- |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
271 |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
272 |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
273 |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
274 |
11 | 275 --Method other than \rectype |
276 | |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
277 The recursively program of C's syntax can be solved using struct syntax. |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
278 For example, if we write |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
279 |
11 | 280 struct interface { |
281 __code (*next)(struct interface); | |
282 }; | |
283 | |
284 __code csA(struct interface p) { | |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
285 struct interface ds; |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
286 ds.next = csB; |
11 | 287 goto p.next(ds); |
288 } | |
289 | |
290 int main() { | |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
291 struct interface ds; |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
292 ds = print; |
11 | 293 goto csA(ds); |
294 return 0; | |
295 } | |
296 | |
18
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
297 there is no need to write recursively. |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
298 Because the struct syntax wrapped in a function pointer. |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
299 Code segment does not receive function pointer in arguments. |
33b7a54edaa9
method other rectype
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
300 Recursively program does not occur. |
11 | 301 |
302 | |
303 | |
304 \section{Comparision} | |
305 | |
19
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
306 Here is our bench mark program. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
307 {\small |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
308 f0(int i) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
309 int k,j; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
310 k = 3+i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
311 j = g0(i+3); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
312 return k+4+j; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
313 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
314 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
315 g0(int i) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
316 return h0(i+4)+i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
317 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
318 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
319 h0(int i) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
320 return i+4; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
321 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
322 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
323 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
324 It is written in C, we perform CPS transformation in several |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
325 steps by hands. There are several optimization is possible. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
326 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
327 {\small |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
328 /* straight conversion case (1) */ |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
329 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
330 typedef char *stack; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
331 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
332 struct cont_interface { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
333 // General Return Continuation |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
334 __code (*ret)(); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
335 }; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
336 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
337 __code f(int i,stack sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
338 int k,j; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
339 k = 3+i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
340 goto f_g0(i,k,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
341 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
342 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
343 struct f_g0_interface { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
344 // Specialized Return Continuation |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
345 __code (*ret)(); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
346 int i_,k_,j_; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
347 }; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
348 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
349 __code f_g1(int j,stack sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
350 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
351 __code f_g0(int i,int k,stack sp) { // Caller |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
352 struct f_g0_interface *c = |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
353 (struct f_g0_interface *)( |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
354 sp -= sizeof(struct f_g0_interface)); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
355 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
356 c->ret = f_g1; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
357 c->k_ = k; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
358 c->i_ = i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
359 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
360 goto g(i+3,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
361 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
362 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
363 __code f_g1(int j,stack sp) { // Continuation |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
364 struct f_g0_interface *c = |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
365 (struct f_g0_interface *)sp; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
366 int k = c->k_; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
367 sp+=sizeof(struct f_g0_interface); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
368 c = (struct f_g0_interface *)sp; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
369 goto (c->ret)(k+4+j,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
370 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
371 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
372 __code g_h1(int j,stack sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
373 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
374 __code g(int i,stack sp) { // Caller |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
375 struct f_g0_interface *c = |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
376 (struct f_g0_interface *)( |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
377 sp -= sizeof(struct f_g0_interface)); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
378 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
379 c->ret = g_h1; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
380 c->i_ = i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
381 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
382 goto h(i+3,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
383 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
384 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
385 __code g_h1(int j,stack sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
386 // Continuation |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
387 struct f_g0_interface *c = |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
388 (struct f_g0_interface *)sp; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
389 int i = c->i_; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
390 sp+=sizeof(struct f_g0_interface); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
391 c = (struct f_g0_interface *)sp; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
392 goto (c->ret)(j+i,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
393 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
394 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
395 __code h(int i,stack sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
396 struct f_g0_interface *c = |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
397 (struct f_g0_interface *)sp; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
398 goto (c->ret)(i+4,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
399 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
400 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
401 struct main_continuation { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
402 // General Return Continuation |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
403 __code (*ret)(); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
404 __code (*main_ret)(); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
405 void *env; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
406 }; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
407 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
408 __code main_return(int i,stack sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
409 if (loop-->0) |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
410 goto f(233,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
411 printf("#0103:%d\n",i); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
412 goto (( (struct main_continuation *)sp)->main_ret)(0), |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
413 ((struct main_continuation *)sp)->env; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
414 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
415 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
416 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
417 This is awfully long, but it is straight forward. Several forward |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
418 prototyping is necessary, and we find strict prototyping is |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
419 painful in CbC, because we have to use many code segments to |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
420 perform simple thing. CbC is not a language for human, but for |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
421 automatic generation, verification or IDE directed programming. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
422 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
423 We can shorten the result in this way. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
424 {\small |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
425 /* little optimized case (3) */ |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
426 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
427 __code f2_1(int i,char *sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
428 int k,j; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
429 k = 3+i; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
430 goto g2_1(k,i+3,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
431 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
432 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
433 __code g2_1(int k,int i,char *sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
434 goto h2_11(k,i+4,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
435 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
436 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
437 __code f2_0_1(int k,int j,char *sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
438 __code h2_1_1(int i,int k,int j,char *sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
439 goto f2_0_1(k,i+j,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
440 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
441 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
442 __code h2_11(int i,int k,char *sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
443 goto h2_1_1(i,k,i+4,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
444 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
445 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
446 __code f2_0_1(int k,int j,char *sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
447 goto (( (struct cont_interface *) |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
448 sp)->ret)(k+4+j,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
449 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
450 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
451 __code main_return2_1(int i,stack sp) { |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
452 if (loop-->0) |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
453 goto f2_1(233,sp); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
454 printf("#0165:%d\n",i); |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
455 goto (( (struct main_continuation *)sp)->main_ret)(0), |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
456 ((struct main_continuation *)sp)->env; |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
457 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
458 } |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
459 |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
460 In this example, CPS transformed source is faster than |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
461 original function call form. There are not so much area for the |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
462 optimization in function call form, because function call API |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
463 have to be strict. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
464 CbC does not need standard call API other than interface which |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
465 is simply a struct and there are no need for register save. (This |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
466 bench mark is designed to require the register save). |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
467 |
20
203699cf5384
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
468 Here is the result in x86_64 architecture (Table.\ref{tab:gcc,compare}). |
19
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
469 is function call. \verb+conv1 2+, \verb+conv1 3+ is optimized CPS transformed |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
470 source. |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
471 |
11 | 472 \begin{table}[htpb] |
473 \centering | |
474 \small | |
475 \begin{tabular}{|l|r|r|r|} \hline | |
476 (unit: s) & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline | |
477 GCC -O3(32bit) & 2.52 & 2.34 & 1.53 \\ \hline | |
478 GCC -O3(64bit) & 1.80 & 1.20 & 1.44 \\ \hline | |
479 \end{tabular} | |
480 \caption{Micro-C, GCC bench mark (in sec)} | |
20
203699cf5384
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
481 \label{tab:gcc,compare} |
11 | 482 \end{table} |
483 | |
484 | |
485 | |
19
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
486 --Conclusion |
dc62dc1fe059
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
18
diff
changeset
|
487 |
20
203699cf5384
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
488 |
203699cf5384
modify compression
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
19
diff
changeset
|
489 |
21 | 490 |