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