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