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