sys/src/cmd/8c/mul.c

   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         if(v == 0){
 316                 zeroregm(n);
 317                 return 1;
 318         }
 319
 320         for(i = 0; i < nelem(multab); i++) {
 321                 p = &multab[i];
 322                 if(p->value == v)
 323                         goto found;
 324         }
 325
 326         p = &multab[mulptr];
 327         if(++mulptr == nelem(multab))
 328                 mulptr = 0;
 329
 330         mulparam(v, p);
 331
 332 found:
 333 //      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);
 334         if(p->alg < 0)
 335                 return 0;
 336
 337         nods = *nodconst(p->shift);
 338
 339         o = OADD;
 340         if(p->alg > 0) {
 341                 regalloc(&nod, n, Z);
 342                 if(p->off < 0)
 343                         o = OSUB;
 344         }
 345
 346         switch(p->alg) {
 347         case 0:
 348                 switch(p->arg) {
 349                 case 1:
 350                         shiftit(n->type, &nods, n);
 351                         break;
 352                 case 15:
 353                 case 25:
 354                 case 27:
 355                 case 45:
 356                 case 81:
 357                         genmuladd(n, n, m1(p->arg), n);
 358                         /* fall thru */
 359                 case 3:
 360                 case 5:
 361                 case 9:
 362                         genmuladd(n, n, m0(p->arg), n);
 363                         shiftit(n->type, &nods, n);
 364                         break;
 365                 default:
 366                         goto bad;
 367                 }
 368                 if(p->neg == 1)
 369                         gins(ANEGL, Z, n);
 370                 break;
 371         case 1:
 372                 switch(p->arg) {
 373                 case 1:
 374                         gmove(n, &nod);
 375                         shiftit(n->type, &nods, &nod);
 376                         break;
 377                 case 3:
 378                 case 5:
 379                 case 9:
 380                         genmuladd(&nod, n, m0(p->arg), n);
 381                         shiftit(n->type, &nods, &nod);
 382                         break;
 383                 default:
 384                         goto bad;
 385                 }
 386                 if(p->neg)
 387                         gopcode(o, n->type, &nod, n);
 388                 else {
 389                         gopcode(o, n->type, n, &nod);
 390                         gmove(&nod, n);
 391                 }
 392                 break;
 393         case 2:
 394                 genmuladd(&nod, n, m0(p->off), n);
 395                 shiftit(n->type, &nods, n);
 396                 goto comop;
 397         case 3:
 398                 genmuladd(&nod, n, m0(p->off), n);
 399                 shiftit(n->type, &nods, n);
 400                 genmuladd(n, &nod, m2(p->off), n);
 401                 break;
 402         case 4:
 403                 genmuladd(&nod, n, m0(p->off), nodconst(0));
 404                 shiftit(n->type, &nods, n);
 405                 goto comop;
 406         default:
 407                 diag(Z, "bad mul alg");
 408                 break;
 409         comop:
 410                 if(p->neg) {
 411                         gopcode(o, n->type, n, &nod);
 412                         gmove(&nod, n);
 413                 }
 414                 else
 415                         gopcode(o, n->type, &nod, n);
 416         }
 417
 418         if(p->alg > 0)
 419                 regfree(&nod);
 420
 421         return 1;
 422
 423 bad:
 424         diag(Z, "mulgen botch");
 425         return 1;
 426 }
 427
 428 void
 429 mulgen(Type *t, Node *r, Node *n)
 430 {
 431         if(!mulgen1(r->vconst, n))
 432                 gopcode(OMUL, t, r, n);
 433 }