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