Mercurial > hg > CbC > old > device

comparison mc-switch.c @ 297:0f79c95df73a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
switch index no compile error
author kono
date Sun, 06 Jun 2004 20:19:36 +0900
parents
children 4ccacae1d2e6
comparison
equal deleted inserted replaced
296:284aa4eaab0d 297:0f79c95df73a
1 /* Micro-C Switch Code generation Part */
2 /* $Id$ */
3
4 #define EXTERN extern
5 #include "mc.h"
6 #include "mc-code.h"
7 #include "mc-codegen.h"
8
9 #if CASE_CODE
10
11 extern void genswitch(int cslist,int cslabel,int dlabel);
12
13 /*
14 value label pair
15 cslist = list3(value,next,label) label==0 means skip
16 continuous cslist
17 chunks: list4(cslist,next,delta,list3(count,min,max))
18 mergeable chunks count list
19 merge: list4(continuous number of chunk,next,delta,case_count);
20 index list
21 index: list4(label,next,max,min);
22 */
23
24 #define chunk_max(chunks) caddr(cadddr(chunks))
25 #define chunk_min(chunks) cadr(cadddr(chunks))
26 #define index_max(index) caddr(index)
27 #define index_min(index) cadddr(index)
28
29 /*
30 group continous case value
31 */
32
33 static int
34 make_chunk(int cslist)
35 {
36 int delta,delta1,list,p,count;
37 // cslist is already sorted
38 delta = 0;
39 list = list4(cslist,0,1,list3(0,car(cslist) /* min */,0));
40 count=1;
41 for(p=0;cadr(cslist);cslist = cadr(cslist),count++) {
42 // compute new delta
43 delta1 = car(cadr(cslist))-car(cslist);
44 // empty case
45 if (!caddr(cslist)) count--;
46 if (delta==0) {
47 // 2nd element
48 caddr(list) = delta = delta1;
49 if (p) cadr(p)=0; // terminate previous chunk
50 } else if (delta1!=delta) {
51 // not contiguous, start new list
52 caddr(cadddr(list)) = car(cslist); // max
53 car(cadddr(list)) = count; count=0;
54 delta = 0;
55 list = list4(cadr(cslist),list,1,list3(0,0,0));
56 cadr(cadddr(list)) = car(cadr(cslist)); // min
57 // prepare terminate point for next turn
58 p=cslist;
59 }
60 }
61 if (p) cadr(p)=0; // terminate previous chunk
62 car(cadddr(list)) = count;
63 caddr(cadddr(list)) = car(cslist); // max
64 return list;
65 }
66
67 #define CASE_MERGE_RATE 70
68
69 static int gcd(int i,int j)
70 {
71 int k;
72 if (i<j) { k=i; i=j; j=k;}
73 for(;;) {
74 if ((k=i%j)==0) return j;
75 i = j; j = k;
76 }
77 }
78
79 /*
80 check two chunks are mergeable or not.
81 */
82
83 static int
84 merge_chunk_p(int *delta,int max,int min,int *count,int delta1,int count1)
85 {
86 int range = max-min;
87 int g;
88 // compute possible merge delta
89 g = gcd(*delta,delta1);
90 g = gcd(g,range);
91 range /= g;
92 *count = count1 = count1+*count;
93 *delta = g;
94 #if 1
95 if (count1*128>(range*128*CASE_MERGE_RATE/100)) {
96 printf("# min %d, max %d, count %d, delta %d, rate %g t=%d\n",
97 min,max,count1,g,
98 ((double)count1)*100.0/range,
99 count1*128>(range*128*CASE_MERGE_RATE/100)
100 );
101 }
102 #endif
103 // count/((max-min)/delta) > 0.8
104 return count1*128>(range*128*CASE_MERGE_RATE/100);
105 }
106
107
108 static int
109 merge_chunk(int chunks)
110 {
111 int list = chunks;
112 int tail,last,max,min,i;
113 int count,c_count,p,widest,delta=1;
114 int merge = 0;
115 while(cadr(list)) {
116 p = cadddr(list);
117 c_count = count = car(p); max=caddr(p);
118 widest = 1; last = list;
119 delta = caddr(list);
120 // check possible merge against the end of the chunks
121 for(i=1,tail=cadr(list);cadr(tail); tail=cadr(tail),i++) {
122 p = cadddr(tail);
123 min = cadr(p);
124 if (merge_chunk_p(&delta,max,min,&count,caddr(tail),car(p))) {
125 // It is mergeable.
126 widest = i+1; last = tail; c_count=count;
127 }
128 }
129 merge = list4(widest,merge,delta,c_count);
130 // skip merged chunks
131 list = cadr(last);
132 }
133 // last one can remain.
134 if (list) merge = list4(1,merge,caddr(list),car(cadddr(list)));
135 return merge;
136 }
137
138 static int
139 table_jump(int count,int delta,int cslist)
140 {
141 int list;
142 for(;count-->0;cslist=cadr(cslist)) {
143 list = car(cslist);
144 printf("# table cases delta=%d count=%d min=%d max=%d\n",
145 caddr(cslist),car(cadddr(cslist)),
146 cadr(cadddr(cslist)),caddr(cadddr(cslist))
147 );
148 for(;list; list=cadr(list)) {
149 if (caddr(list))
150 cmpdimm(car(list),csvalue1,caddr(list),0);
151 }
152 }
153 return cslist;
154 }
155
156 static int
157 cascade_compare(int count,int cslist)
158 {
159 int list;
160 for(;count-->0;cslist=cadr(cslist)) {
161 list = car(cslist);
162 printf("# cascade cases delta=%d count=%d min=%d max=%d\n",
163 caddr(cslist),car(cadddr(cslist)),
164 cadr(cadddr(cslist)),caddr(cadddr(cslist))
165 );
166 for(;list; list=cadr(list)) {
167 if (caddr(list))
168 cmpdimm(car(list),csvalue1,caddr(list),0);
169 // value register label mode
170 }
171 }
172 return cslist;
173 }
174
175 #define CASE_TABLE_COUNT 10
176 #define CASE_INDEX_COUNT 10
177
178
179 /*
180 generate index jmp
181 */
182
183 static void
184 switch_index_jmp(int index,int label)
185 {
186 int value = car(car(caddr(caddr(index))));
187 cmpdimm(value,csvalue1,label,LT);
188 // value register label mode
189 }
190
191 /*
192 generate leaf index branch
193 */
194
195 static int
196 switch_make_index_leaf(int count,int index)
197 {
198 for(;count-- !=0 && cadr(index);index=cadr(index)) {
199 switch_index_jmp(
200 cadr(index), /* next max */
201 car(caddr(index)) /*label*/ );
202 }
203 if (!cadr(index)) {
204 // don't check max boundary
205 jmp(car(caddr(index)));
206 return 0;
207 }
208 if (count!=0) error(-1);
209 return index;
210 }
211
212 /*
213 generate index switch branch (no table).
214 if necessary generate higher index.
215 */
216
217 static void
218 switch_make_index(int index0,int count,int cslabel)
219 {
220 int index=0;
221 int icount=0;
222 int l,min,max;
223 while (index0 && count > CASE_INDEX_COUNT) {
224 l = backdef();
225 min = index_min(index0);
226 index0=switch_make_index_leaf(CASE_INDEX_COUNT,index0);
227 max = index_min(index0);
228 index = list4(l,index,max,min);
229 count-=CASE_INDEX_COUNT;
230 icount++;
231 }
232 if (index) {
233 switch_make_index(reverse0(index),icount,cslabel);
234 if (dlabel) jmp(dlabel);
235 } else {
236 fwddef(cslabel);
237 switch_make_index_leaf(-1,index0);
238 if (dlabel) jmp(dlabel);
239 }
240 }
241
242 /*
243 generate leaf switch branch or table jump
244 */
245
246 static int
247 switch_leaf(int count,int merge,int cslist)
248 {
249 for(;count-- !=0 && merge;merge=cadr(merge)) {
250 printf("# merge count %d delta %d c_count %d\n",
251 car(merge),caddr(merge),cadddr(merge));
252 if (cadddr(merge)>CASE_TABLE_COUNT)
253 cslist = table_jump(car(merge),caddr(merge),cslist);
254 else
255 cslist = cascade_compare(car(merge),cslist);
256 }
257 return cslist;
258 }
259
260 /*
261 make index if necessary or
262 generate case branch or table jump
263 */
264
265 static void
266 switch_index(int merge,int chunks,int cslabel,int dlabel,int gmax)
267 {
268 int m,l,max,min;
269 int chnkcnt = 0;
270 int icount = 0;
271 int count = 0;
272 int index = 0;
273 for(m=merge;m;m=cadr(m)) {
274 chnkcnt++;
275 count += cadddr(m);
276 if (count > CASE_INDEX_COUNT || (index && !cadr(m))) {
277 icount++;
278 min = car(car(chunks));
279 l = backdef();
280 chunks= switch_leaf(chnkcnt,merge,chunks);
281 max = chunks?car(car(chunks)):gmax;
282 index = list4(l,index,max,min);
283 merge = cadr(m); count = 0; chnkcnt = 0;
284 if (dlabel) jmp(dlabel);
285 }
286 }
287 if (index) {
288 index = reverse0(index);
289 // check lower bound
290 switch_index_jmp(index,dlabel?dlabel:blabel);
291 switch_make_index(index,icount,cslabel);
292 if (dlabel) jmp(dlabel);
293 } else {
294 fwddef(cslabel);
295 switch_leaf(-1,merge,chunks);
296 if (dlabel) jmp(dlabel);
297 }
298 }
299
300 /* generate switch table, index, cascading branch */
301
302
303 void
304 genswitch(int cslist,int cslabel,int dlabel)
305 {
306 int chunks,merge,gmax;
307 int i,j;
308 #if 0
309 for(i=cslist;i;i=cadr(i)) {
310 printf("# case %d L_%d\n",car(i),caddr(i));
311 }
312 #endif
313 /* find stepwise chunks */
314 chunks=make_chunk(cslist);
315 #if 1
316 chunks = 0;
317 for(i=cslist;i;i=cadr(i)) {
318 chunks++;
319 }
320 j = chunks;
321 #endif
322 /* possible merge of loose stepwise chunks */
323 merge = merge_chunk(chunks);
324 #if 0
325 // chunks: list3(widest,next,delta);
326 printf("# chunks %d = sum ",j);
327 j = 0;
328 for(i=merge;i;i=cadr(i)) {
329 printf(" %d/%d",car(i),caddr(i));
330 j+=car(i);
331 }
332 printf(" sum = %d\n",j);
333 #endif
334 /* make index branch or table jump */
335 gmax = chunk_max(chunks);
336 chunks = reverse0(chunks);
337 switch_index(merge,chunks,cslabel,dlabel,gmax);
338 }
339
340 #endif
341
342
343
344 /* end */