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 */ 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 */ 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 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