1 #include "gc.h" 2 3 typedef struct Malg Malg; 4 typedef struct Mparam Mparam; 5 6 struct Malg 7 { 8 char vals[10]; 9 }; 10 11 struct Mparam 12 { 13 ulong value; 14 char alg; 15 char neg; 16 char shift; 17 char arg; 18 char off; 19 }; 20 21 static Mparam multab[32]; 22 static int mulptr; 23 24 static Malg malgs[] = 25 { 26 {0, 100}, 27 {-1, 1, 100}, 28 {-9, -5, -3, 3, 5, 9, 100}, 29 {6, 10, 12, 18, 20, 24, 36, 40, 72, 100}, 30 {-8, -4, -2, 2, 4, 8, 100}, 31 }; 32 33 /* 34 * return position of lowest 1 35 */ 36 int 37 lowbit(ulong v) 38 { 39 int s, i; 40 ulong m; 41 42 s = 0; 43 m = 0xFFFFFFFFUL; 44 for(i = 16; i > 0; i >>= 1) { 45 m >>= i; 46 if((v & m) == 0) { 47 v >>= i; 48 s += i; 49 } 50 } 51 return s; 52 } 53 54 void 55 genmuladd(Node *d, Node *s, int m, Node *a) 56 { 57 Node nod; 58 59 nod.op = OINDEX; 60 nod.left = a; 61 nod.right = s; 62 nod.scale = m; 63 nod.type = types[TIND]; 64 nod.xoffset = 0; 65 xcom(&nod); 66 gopcode(OADDR, d->type, &nod, d); 67 } 68 69 void 70 mulparam(ulong m, Mparam *mp) 71 { 72 int c, i, j, n, o, q, s; 73 int bc, bi, bn, bo, bq, bs, bt; 74 char *p; 75 long u; 76 ulong t; 77 78 bc = bq = 10; 79 bi = bn = bo = bs = bt = 0; 80 for(i = 0; i < nelem(malgs); i++) { 81 for(p = malgs[i].vals, j = 0; (o = p[j]) < 100; j++) 82 for(s = 0; s < 2; s++) { 83 c = 10; 84 q = 10; 85 u = m - o; 86 if(u == 0) 87 continue; 88 if(s) { 89 o = -o; 90 if(o > 0) 91 continue; 92 u = -u; 93 } 94 n = lowbit(u); 95 t = (ulong)u >> n; 96 switch(i) { 97 case 0: 98 if(t == 1) { 99 c = s + 1; 100 q = 0; 101 break; 102 } 103 switch(t) { 104 case 3: 105 case 5: 106 case 9: 107 c = s + 1; 108 if(n) 109 c++; 110 q = 0; 111 break; 112 } 113 if(s) 114 break; 115 switch(t) { 116 case 15: 117 case 25: 118 case 27: 119 case 45: 120 case 81: 121 c = 2; 122 if(n) 123 c++; 124 q = 1; 125 break; 126 } 127 break; 128 case 1: 129 if(t == 1) { 130 c = 3; 131 q = 3; 132 break; 133 } 134 switch(t) { 135 case 3: 136 case 5: 137 case 9: 138 c = 3; 139 q = 2; 140 break; 141 } 142 break; 143 case 2: 144 if(t == 1) { 145 c = 3; 146 q = 2; 147 break; 148 } 149 break; 150 case 3: 151 if(s) 152 break; 153 if(t == 1) { 154 c = 3; 155 q = 1; 156 break; 157 } 158 break; 159 case 4: 160 if(t == 1) { 161 c = 3; 162 q = 0; 163 break; 164 } 165 break; 166 } 167 if(c < bc || (c == bc && q > bq)) { 168 bc = c; 169 bi = i; 170 bn = n; 171 bo = o; 172 bq = q; 173 bs = s; 174 bt = t; 175 } 176 } 177 } 178 mp->value = m; 179 if(bc <= 3) { 180 mp->alg = bi; 181 mp->shift = bn; 182 mp->off = bo; 183 mp->neg = bs; 184 mp->arg = bt; 185 } 186 else 187 mp->alg = -1; 188 } 189 190 int 191 m0(int a) 192 { 193 switch(a) { 194 case -2: 195 case 2: 196 return 2; 197 case -3: 198 case 3: 199 return 2; 200 case -4: 201 case 4: 202 return 4; 203 case -5: 204 case 5: 205 return 4; 206 case 6: 207 return 2; 208 case -8: 209 case 8: 210 return 8; 211 case -9: 212 case 9: 213 return 8; 214 case 10: 215 return 4; 216 case 12: 217 return 2; 218 case 15: 219 return 2; 220 case 18: 221 return 8; 222 case 20: 223 return 4; 224 case 24: 225 return 2; 226 case 25: 227 return 4; 228 case 27: 229 return 2; 230 case 36: 231 return 8; 232 case 40: 233 return 4; 234 case 45: 235 return 4; 236 case 72: 237 return 8; 238 case 81: 239 return 8; 240 } 241 diag(Z, "bad m0"); 242 return 0; 243 } 244 245 int 246 m1(int a) 247 { 248 switch(a) { 249 case 15: 250 return 4; 251 case 25: 252 return 4; 253 case 27: 254 return 8; 255 case 45: 256 return 8; 257 case 81: 258 return 8; 259 } 260 diag(Z, "bad m1"); 261 return 0; 262 } 263 264 int 265 m2(int a) 266 { 267 switch(a) { 268 case 6: 269 return 2; 270 case 10: 271 return 2; 272 case 12: 273 return 4; 274 case 18: 275 return 2; 276 case 20: 277 return 4; 278 case 24: 279 return 8; 280 case 36: 281 return 4; 282 case 40: 283 return 8; 284 case 72: 285 return 8; 286 } 287 diag(Z, "bad m2"); 288 return 0; 289 } 290 291 void 292 shiftit(Type *t, Node *s, Node *d) 293 { 294 long c; 295 296 c = (long)s->vconst & 31; 297 switch(c) { 298 case 0: 299 break; 300 case 1: 301 gopcode(OADD, t, d, d); 302 break; 303 default: 304 gopcode(OASHL, t, s, d); 305 } 306 } 307 308 static int 309 mulgen1(ulong v, Node *n) 310 { 311 int i, o; 312 Mparam *p; 313 Node nod, nods; 314 315 for(i = 0; i < nelem(multab); i++) { 316 p = &multab[i]; 317 if(p->value == v) 318 goto found; 319 } 320 321 p = &multab[mulptr]; 322 if(++mulptr == nelem(multab)) 323 mulptr = 0; 324 325 mulparam(v, p); 326 327 found: 328 // print("v=%.lx a=%d n=%d s=%d g=%d o=%d \n", p->value, p->alg, p->neg, p->shift, p->arg, p->off); 329 if(p->alg < 0) 330 return 0; 331 332 nods = *nodconst(p->shift); 333 334 o = OADD; 335 if(p->alg > 0) { 336 regalloc(&nod, n, Z); 337 if(p->off < 0) 338 o = OSUB; 339 } 340 341 switch(p->alg) { 342 case 0: 343 switch(p->arg) { 344 case 1: 345 shiftit(n->type, &nods, n); 346 break; 347 case 15: 348 case 25: 349 case 27: 350 case 45: 351 case 81: 352 genmuladd(n, n, m1(p->arg), n); 353 /* fall thru */ 354 case 3: 355 case 5: 356 case 9: 357 genmuladd(n, n, m0(p->arg), n); 358 shiftit(n->type, &nods, n); 359 break; 360 default: 361 goto bad; 362 } 363 if(p->neg == 1) 364 gins(ANEGL, Z, n); 365 break; 366 case 1: 367 switch(p->arg) { 368 case 1: 369 gmove(n, &nod); 370 shiftit(n->type, &nods, &nod); 371 break; 372 case 3: 373 case 5: 374 case 9: 375 genmuladd(&nod, n, m0(p->arg), n); 376 shiftit(n->type, &nods, &nod); 377 break; 378 default: 379 goto bad; 380 } 381 if(p->neg) 382 gopcode(o, n->type, &nod, n); 383 else { 384 gopcode(o, n->type, n, &nod); 385 gmove(&nod, n); 386 } 387 break; 388 case 2: 389 genmuladd(&nod, n, m0(p->off), n); 390 shiftit(n->type, &nods, n); 391 goto comop; 392 case 3: 393 genmuladd(&nod, n, m0(p->off), n); 394 shiftit(n->type, &nods, n); 395 genmuladd(n, &nod, m2(p->off), n); 396 break; 397 case 4: 398 genmuladd(&nod, n, m0(p->off), nodconst(0)); 399 shiftit(n->type, &nods, n); 400 goto comop; 401 default: 402 diag(Z, "bad mul alg"); 403 break; 404 comop: 405 if(p->neg) { 406 gopcode(o, n->type, n, &nod); 407 gmove(&nod, n); 408 } 409 else 410 gopcode(o, n->type, &nod, n); 411 } 412 413 if(p->alg > 0) 414 regfree(&nod); 415 416 return 1; 417 418 bad: 419 diag(Z, "mulgen botch"); 420 return 1; 421 } 422 423 void 424 mulgen(Type *t, Node *r, Node *n) 425 { 426 if(!mulgen1(r->vconst, n)) 427 gopcode(OMUL, t, r, n); 428 } 429