1 /*-
2 * Copyright (c) 1980, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)pccaseop.c 8.1 (Berkeley) 06/06/93";
10 #endif /* not lint */
11
12 #include "whoami.h"
13 #ifdef PC
14 /*
15 * and the rest of the file
16 */
17 #include "0.h"
18 #include "tree.h"
19 #include "objfmt.h"
20 #include <pcc.h>
21 #include "pc.h"
22 #include "tmps.h"
23 #include "tree_ty.h"
24
25 /*
26 * structure for a case:
27 * its constant label, line number (for errors), and location label.
28 */
29 struct ct {
30 long cconst;
31 int cline;
32 int clabel;
33 };
34
35 /*
36 * the PCC_FORCE operator puts its operand into a register.
37 * these to keep from thinking of it as r0 all over.
38 */
39 #if defined(vax) || defined(tahoe)
40 # define FORCENAME "r0"
41 #endif vax || tahoe
42 #ifdef mc68000
43 # define FORCENAME "d0"
44 # define ADDRTEMP "a0"
45 #endif mc68000
46
47 /*
48 * given a tree for a case statement, generate code for it.
49 * this computes the expression into a register,
50 * puts down the code for each of the cases,
51 * and then decides how to do the case switching.
52 * tcase [0] T_CASE
53 * [1] lineof "case"
54 * [2] expression
55 * [3] list of cased statements:
56 * cstat [0] T_CSTAT
57 * [1] lineof ":"
58 * [2] list of constant labels
59 * [3] statement
60 */
pccaseop(tcase)61 pccaseop( tcase )
62 WHI_CAS *tcase;
63 {
64 struct nl *exprtype;
65 struct nl *exprnlp;
66 struct nl *rangetype;
67 long low;
68 long high;
69 long exprctype;
70 char *swlabel;
71 char *endlabel;
72 char *label;
73 int count;
74 struct tnode *cstatlp;
75 struct tnode *cstatp;
76 struct tnode *casep;
77 struct ct *ctab;
78 struct ct *ctp;
79 bool nr;
80 long goc;
81 int casecmp();
82 bool dupcases;
83
84 goc = gocnt;
85 /*
86 * find out the type of the case expression
87 * even if the expression has errors (exprtype == NIL), continue.
88 */
89 line = tcase->line_no;
90 codeoff();
91 exprtype = rvalue( tcase->expr , NLNIL , RREQ );
92 codeon();
93 if ( exprtype != NLNIL ) {
94 if ( isnta( exprtype , "bcsi" ) ) {
95 error("Case selectors cannot be %ss" , nameof( exprtype ) );
96 exprtype = NLNIL;
97 } else {
98 if ( exprtype -> class != RANGE ) {
99 rangetype = exprtype -> type;
100 } else {
101 rangetype = exprtype;
102 }
103 if ( rangetype == NLNIL ) {
104 exprtype = NLNIL;
105 } else {
106 low = rangetype -> range[0];
107 high = rangetype -> range[1];
108 }
109 }
110 }
111 if ( exprtype != NLNIL ) {
112 /*
113 * compute and save the case expression.
114 * also, put expression into a register
115 * save its c-type and jump to the code to do the switch.
116 */
117 exprctype = p2type( exprtype );
118 exprnlp = tmpalloc( (long) (sizeof (long)), nl + T4INT , NOREG );
119 putRV((char *) 0 , cbn , exprnlp -> value[ NL_OFFS ] ,
120 exprnlp -> extra_flags , PCCT_INT );
121 (void) rvalue( tcase->expr , NLNIL , RREQ );
122 sconv((int) exprctype, (int) PCCT_INT);
123 putop( PCC_ASSIGN , PCCT_INT );
124 putop( PCC_FORCE , PCCT_INT );
125 putdot( filename , line );
126 swlabel = getlab();
127 putjbr( (long) swlabel );
128 }
129 /*
130 * count the number of cases
131 * and allocate table for cases, lines, and labels
132 * default case goes in ctab[0].
133 */
134 count = 1;
135 for ( cstatlp = tcase->stmnt_list ; cstatlp != TR_NIL ;
136 cstatlp = cstatlp->list_node.next ) {
137 cstatp = cstatlp->list_node.list;
138 if ( cstatp == TR_NIL ) {
139 continue;
140 }
141 for ( casep = cstatp->c_stmnt.const_list ; casep != TR_NIL ;
142 casep = casep->list_node.next ) {
143 count++;
144 }
145 }
146 /*
147 */
148 ctab = (struct ct *) malloc( count * sizeof( struct ct ) );
149 if ( ctab == (struct ct *) 0 ) {
150 error("Ran out of memory (case)");
151 pexit( DIED );
152 }
153 /*
154 * pick up default label and label for after case statement.
155 */
156 ctab[0].clabel = (int) getlab();
157 endlabel = getlab();
158 /*
159 * generate code for each case
160 * filling in ctab for each.
161 * nr is for error if no case falls out bottom.
162 */
163 nr = TRUE;;
164 count = 0;
165 for ( cstatlp = tcase->stmnt_list ; cstatlp != TR_NIL ;
166 cstatlp = cstatlp->list_node.next ) {
167 cstatp = cstatlp->list_node.list;
168 if ( cstatp == TR_NIL ) {
169 continue;
170 }
171 line = cstatp->c_stmnt.line_no;
172 label = getlab();
173 for ( casep = cstatp->c_stmnt.const_list ; casep != TR_NIL ;
174 casep = casep->list_node.next ) {
175 gconst( casep->list_node.list );
176 if( exprtype == NLNIL || con.ctype == NIL ) {
177 continue;
178 }
179 if ( incompat( con.ctype , exprtype , TR_NIL ) ) {
180 cerror("Case label type clashed with case selector expression type");
181 continue;
182 }
183 if ( con.crval < low || con.crval > high ) {
184 error("Case label out of range");
185 continue;
186 }
187 count++;
188 ctab[ count ].cconst = con.crval;
189 ctab[ count ].cline = line;
190 ctab[ count ].clabel = (int) label;
191 }
192 /*
193 * put out the statement
194 */
195 (void) putlab( label );
196 putcnt();
197 level++;
198 statement( cstatp->c_stmnt.stmnt );
199 nr = (nr && noreach)?TRUE:FALSE;
200 noreach = FALSE;
201 level--;
202 if (gotos[cbn]) {
203 ungoto();
204 }
205 putjbr( (long) endlabel );
206 }
207 noreach = nr;
208 /*
209 * default action is to call error
210 */
211 (void) putlab( (char *) ctab[0].clabel );
212 putleaf( PCC_ICON , 0 , 0 , PCCM_ADDTYPE( PCCTM_FTN | PCCT_INT , PCCTM_PTR ) , "_CASERNG" );
213 putRV((char *) 0 , cbn , exprnlp -> value[ NL_OFFS ] ,
214 exprnlp -> extra_flags , PCCT_INT );
215 putop( PCC_CALL , PCCT_INT );
216 putdot( filename , line );
217 /*
218 * sort the cases
219 */
220 qsort( &ctab[1] , count , sizeof (struct ct) , casecmp );
221 /*
222 * check for duplicates
223 */
224 dupcases = FALSE;
225 for ( ctp = &ctab[1] ; ctp < &ctab[ count ] ; ctp++ ) {
226 if ( ctp[0].cconst == ctp[1].cconst ) {
227 error("Multiply defined label in case, lines %d and %d" ,
228 (char *) ctp[0].cline , (char *) ctp[1].cline );
229 dupcases = TRUE;
230 }
231 }
232 if ( dupcases ) {
233 return;
234 }
235 /*
236 * choose a switch algorithm and implement it:
237 * direct switch >= 1/3 full and >= 4 cases.
238 * binary switch not direct switch and > 8 cases.
239 * ifthenelse not direct or binary switch.
240 */
241 (void) putlab( swlabel );
242 if ( ctab[ count ].cconst - ctab[1].cconst < 3 * count && count >= 4 ) {
243 directsw( ctab , count );
244 } else if ( count > 8 ) {
245 binarysw( ctab , count );
246 } else {
247 itesw( ctab , count );
248 }
249 (void) putlab( endlabel );
250 if ( goc != gocnt ) {
251 putcnt();
252 }
253 }
254
255 /*
256 * direct switch
257 */
258 directsw( ctab , count )
259 struct ct *ctab;
260 int count;
261 {
262 int fromlabel = (int) getlab();
263 long i;
264 long j;
265
266 # ifdef vax
267 if (opt('J')) {
268 /*
269 * We have a table of absolute addresses.
270 *
271 * subl2 to make r0 a 0-origin byte offset.
272 * cmpl check against upper limit.
273 * jlssu error if out of bounds.
274 * ashl to make r0 a 0-origin long offset,
275 * jmp and indirect through it.
276 */
277 putprintf(" subl2 $%d,%s", 0, (int) ctab[1].cconst, (int) FORCENAME);
278 putprintf(" cmpl $%d,%s", 0,
279 (int) (ctab[count].cconst - ctab[1].cconst),
280 (int) FORCENAME);
281 putprintf(" jlssu %s%d", 0, (int) LABELPREFIX, ctab[0].clabel);
282 putprintf(" ashl $2,%s,%s", 0, (int) FORCENAME, (int) FORCENAME);
283 putprintf(" jmp *%s%d(%s)", 0,
284 (int) LABELPREFIX, fromlabel, (int) FORCENAME);
285 } else {
286 /*
287 * We can use the VAX casel instruction with a table
288 * of short relative offsets.
289 */
290 putprintf(" casel %s,$%d,$%d" , 0 , (int) FORCENAME ,
291 (int) ctab[1].cconst ,
292 (int) (ctab[ count ].cconst - ctab[1].cconst ));
293 }
294 # endif vax
295
296 # ifdef tahoe
297 if (opt('J')) {
298 /*
299 * We have a table of absolute addresses.
300 *
301 * subl2 to make r0 a 0-origin byte offset.
302 * cmpl check against upper limit.
303 * jlssu error if out of bounds.
304 * shal to make r0 a 0-origin long offset,
305 * jmp and indirect through it.
306 */
307 putprintf(" subl2 $%d,%s", 0, (int) ctab[1].cconst, (int) FORCENAME);
308 putprintf(" cmpl $%d,%s", 0,
309 (int) (ctab[count].cconst - ctab[1].cconst),
310 (int) FORCENAME);
311 putprintf(" jlssu %s%d", 0, (int) LABELPREFIX, ctab[0].clabel);
312 putprintf(" shal $2,%s,%s", 0, (int) FORCENAME, (int) FORCENAME);
313 putprintf(" jmp *%s%d(%s)", 0,
314 (int) LABELPREFIX, fromlabel, (int) FORCENAME);
315 } else {
316 /*
317 * We can use the TAHOE casel instruction with a table
318 * of short relative offsets.
319 */
320 putprintf(" casel %s,$%d,$%d" , 0 , (int) FORCENAME ,
321 (int) ctab[1].cconst ,
322 (int) (ctab[ count ].cconst - ctab[1].cconst ));
323 putprintf(" .align 1", 0);
324 }
325 # endif tahoe
326
327 # ifdef mc68000
328 /*
329 * subl to make d0 a 0-origin byte offset.
330 * cmpl check against upper limit.
331 * bhi error if out of bounds.
332 */
333 putprintf(" subl #%d,%s", 0, ctab[1].cconst, FORCENAME);
334 putprintf(" cmpl #%d,%s", 0,
335 ctab[count].cconst - ctab[1].cconst, FORCENAME);
336 putprintf(" bhi %s%d", 0, LABELPREFIX, ctab[0].clabel);
337 if (opt('J')) {
338 /*
339 * We have a table of absolute addresses.
340 *
341 * asll to make d0 a 0-origin long offset.
342 * movl pick up a jump-table entry
343 * jmp and indirect through it.
344 */
345 putprintf(" asll #2,%s", 0, FORCENAME, FORCENAME);
346 putprintf(" movl pc@(4,%s:l),%s", 0, FORCENAME, ADDRTEMP);
347 putprintf(" jmp %s@", 0, ADDRTEMP);
348 } else {
349 /*
350 * We have a table of relative addresses.
351 *
352 * addw to make d0 a 0-origin word offset.
353 * movw pick up a jump-table entry
354 * jmp and indirect through it.
355 */
356 putprintf(" addw %s,%s", 0, FORCENAME, FORCENAME);
357 putprintf(" movw pc@(6,%s:w),%s", 0, FORCENAME, FORCENAME);
358 putprintf(" jmp pc@(2,%s:w)", 0, FORCENAME);
359 }
360 # endif mc68000
361 (void) putlab( (char *) fromlabel );
362 i = 1;
363 j = ctab[1].cconst;
364 while ( i <= count ) {
365 if ( j == ctab[ i ].cconst ) {
366 if (opt('J')) {
367 putprintf( " .long " , 1 );
368 putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , ctab[ i ].clabel );
369 } else {
370 putprintf( " .word " , 1 );
371 putprintf( PREFIXFORMAT , 1 , (int) LABELPREFIX , ctab[ i ].clabel );
372 putprintf( "-" , 1 );
373 putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , fromlabel );
374 }
375 i++;
376 } else {
377 if (opt('J')) {
378 putprintf( " .long " , 1 );
379 putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , ctab[ 0 ].clabel );
380 } else {
381 putprintf( " .word " , 1 );
382 putprintf( PREFIXFORMAT , 1 , (int) LABELPREFIX , ctab[ 0 ].clabel );
383 putprintf( "-" , 1 );
384 putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , fromlabel );
385 }
386 }
387 j++;
388 }
389 # if defined(vax) || defined(tahoe)
390 /*
391 * execution continues here if value not in range of case.
392 */
393 if (!opt('J'))
394 putjbr( (long) ctab[0].clabel );
395 # endif vax || tahoe
396 }
397
398 /*
399 * binary switch
400 * special case out default label and start recursion.
401 */
402 binarysw( ctab , count )
403 struct ct *ctab;
404 int count;
405 {
406
407 bsrecur( ctab[0].clabel , &ctab[0] , count );
408 }
409
410 /*
411 * recursive log( count ) search.
412 */
bsrecur(deflabel,ctab,count)413 bsrecur( deflabel , ctab , count )
414 int deflabel;
415 struct ct *ctab;
416 int count;
417 {
418
419 if ( count <= 0 ) {
420 putjbr((long) deflabel);
421 return;
422 } else if ( count == 1 ) {
423 # if defined(vax) || defined(tahoe)
424 putprintf(" cmpl %s,$%d", 0, (int) FORCENAME, (int) ctab[1].cconst);
425 putprintf(" jeql %s%d", 0, (int) LABELPREFIX, ctab[1].clabel);
426 putjbr((long) deflabel);
427 # endif vax || tahoe
428 # ifdef mc68000
429 putprintf(" cmpl #%d,%s", 0, ctab[1].cconst, (int) FORCENAME);
430 putprintf(" jeq L%d", 0, (int) LABELPREFIX, ctab[1].clabel);
431 putjbr((long) deflabel);
432 # endif mc68000
433 return;
434 } else {
435 int half = ( count + 1 ) / 2;
436 int gtrlabel = (int) getlab();
437
438 # if defined(vax) || defined(tahoe)
439 putprintf(" cmpl %s,$%d", 0, (int) FORCENAME, (int) ctab[half].cconst);
440 putprintf(" jgtr %s%d", 0, (int) LABELPREFIX, gtrlabel);
441 putprintf(" jeql %s%d", 0, (int) LABELPREFIX, ctab[half].clabel);
442 # endif vax || tahoe
443 # ifdef mc68000
444 putprintf(" cmpl #%d,%s", 0, (int) ctab[half].cconst, (int) FORCENAME);
445 putprintf(" jgt %s%d", 0, (int) LABELPREFIX, gtrlabel);
446 putprintf(" jeq %s%d", 0, (int) LABELPREFIX, ctab[half].clabel);
447 # endif mc68000
448 bsrecur( deflabel , &ctab[0] , half - 1 );
449 (void) putlab((char *) gtrlabel);
450 bsrecur( deflabel , &ctab[ half ] , count - half );
451 return;
452 }
453 }
454
455 itesw( ctab , count )
456 struct ct *ctab;
457 int count;
458 {
459 int i;
460
461 for ( i = 1 ; i <= count ; i++ ) {
462 # if defined(vax) || defined(tahoe)
463 putprintf(" cmpl %s,$%d", 0, (int) FORCENAME, (int) ctab[i].cconst);
464 putprintf(" jeql %s%d", 0, (int) LABELPREFIX, ctab[i].clabel);
465 # endif vax || tahoe
466 # ifdef mc68000
467 putprintf(" cmpl #%d,%s", 0, (int) ctab[i].cconst, (int) FORCENAME);
468 putprintf(" jeq %s%d", 0, (int) LABELPREFIX, ctab[i].clabel);
469 # endif mc68000
470 }
471 putjbr((long) ctab[0].clabel);
472 return;
473 }
474 int
casecmp(this,that)475 casecmp( this , that )
476 struct ct *this;
477 struct ct *that;
478 {
479 if ( this -> cconst < that -> cconst ) {
480 return -1;
481 } else if ( this -> cconst > that -> cconst ) {
482 return 1;
483 } else {
484 return 0;
485 }
486 }
487 #endif PC
488