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