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