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