util.c

   1 #include "all.h"
   2 #include <stdarg.h>
   3
   4 typedef struct Bitset Bitset;
   5 typedef struct Vec Vec;
   6
   7 struct Vec {
   8         ulong mag;
   9         Pool pool;
  10         size_t esz;
  11         ulong cap;
  12         union {
  13                 long long ll;
  14                 long double ld;
  15                 void *ptr;
  16         } align[];
  17 };
  18
  19 enum {
  20         VMin = 2,
  21         VMag = 0xcabba9e,
  22         NPtr = 256,
  23 };
  24
  25 Typ *typ;
  26 Ins insb[NIns], *curi;
  27
  28 static void *ptr[NPtr];
  29 static void **pool = ptr;
  30 static int nptr = 1;
  31
  32 void
  33 die_(char *file, char *s, ...)
  34 {
  35         va_list ap;
  36
  37         fprintf(stderr, "%s: dying: ", file);
  38         va_start(ap, s);
  39         vfprintf(stderr, s, ap);
  40         va_end(ap);
  41         fputc('\n', stderr);
  42         abort();
  43 }
  44
  45 void *
  46 emalloc(size_t n)
  47 {
  48         void *p;
  49
  50         p = calloc(1, n);
  51         if (!p)
  52                 die("emalloc, out of memory");
  53         return p;
  54 }
  55
  56 void *
  57 alloc(size_t n)
  58 {
  59         void **pp;
  60
  61         if (n == 0)
  62                 return 0;
  63         if (nptr >= NPtr) {
  64                 pp = emalloc(NPtr * sizeof(void *));
  65                 pp[0] = pool;
  66                 pool = pp;
  67                 nptr = 1;
  68         }
  69         return pool[nptr++] = emalloc(n);
  70 }
  71
  72 void
  73 freeall()
  74 {
  75         void **pp;
  76
  77         for (;;) {
  78                 for (pp = &pool[1]; pp < &pool[nptr]; pp++)
  79                         free(*pp);
  80                 pp = pool[0];
  81                 if (!pp)
  82                         break;
  83                 free(pool);
  84                 pool = pp;
  85                 nptr = NPtr;
  86         }
  87         nptr = 1;
  88 }
  89
  90 int
  91 iscmp(int op, int *pk, int *pc)
  92 {
  93         if (Ocmpw <= op && op <= Ocmpw1) {
  94                 *pc = op - Ocmpw;
  95                 *pk = Kw;
  96         }
  97         else if (Ocmpl <= op && op <= Ocmpl1) {
  98                 *pc = op - Ocmpl;
  99                 *pk = Kl;
 100         }
 101         else if (Ocmps <= op && op <= Ocmps1) {
 102                 *pc = NCmpI + op - Ocmps;
 103                 *pk = Ks;
 104         }
 105         else if (Ocmpd <= op && op <= Ocmpd1) {
 106                 *pc = NCmpI + op - Ocmpd;
 107                 *pk = Kd;
 108         }
 109         else
 110                 return 0;
 111         return 1;
 112 }
 113
 114 int
 115 argcls(Ins *i, int n)
 116 {
 117         return optab[i->op].argcls[n][i->cls];
 118 }
 119
 120 void
 121 emit(int op, int k, Ref to, Ref arg0, Ref arg1)
 122 {
 123         if (curi == insb)
 124                 die("emit, too many instructions");
 125         *--curi = (Ins){
 126                 .op = op, .cls = k,
 127                 .to = to, .arg = {arg0, arg1}
 128         };
 129 }
 130
 131 void
 132 emiti(Ins i)
 133 {
 134         emit(i.op, i.cls, i.to, i.arg[0], i.arg[1]);
 135 }
 136
 137 void
 138 idup(Ins **pd, Ins *s, ulong n)
 139 {
 140         *pd = alloc(n * sizeof(Ins));
 141         memcpy(*pd, s, n * sizeof(Ins));
 142 }
 143
 144 Ins *
 145 icpy(Ins *d, Ins *s, ulong n)
 146 {
 147         memcpy(d, s, n * sizeof(Ins));
 148         return d + n;
 149 }
 150
 151 void *
 152 vnew(ulong len, size_t esz, Pool pool)
 153 {
 154         void *(*f)(size_t);
 155         ulong cap;
 156         Vec *v;
 157
 158         for (cap=VMin; cap<len; cap*=2)
 159                 ;
 160         f = pool == Pheap ? emalloc : alloc;
 161         v = f(cap * esz + sizeof(Vec));
 162         v->mag = VMag;
 163         v->cap = cap;
 164         v->esz = esz;
 165         v->pool = pool;
 166         return v + 1;
 167 }
 168
 169 void
 170 vfree(void *p)
 171 {
 172         Vec *v;
 173
 174         v = (Vec *)p - 1;
 175         assert(v->mag == VMag);
 176         if (v->pool == Pheap) {
 177                 v->mag = 0;
 178                 free(v);
 179         }
 180 }
 181
 182 void
 183 vgrow(void *vp, ulong len)
 184 {
 185         Vec *v;
 186         void *v1;
 187
 188         v = *(Vec **)vp - 1;
 189         assert(v+1 && v->mag == VMag);
 190         if (v->cap >= len)
 191                 return;
 192         v1 = vnew(len, v->esz, v->pool);
 193         memcpy(v1, v+1, v->cap * v->esz);
 194         vfree(v+1);
 195         *(Vec **)vp = v1;
 196 }
 197
 198 static int cmptab[][2] ={
 199                      /* negation    swap */
 200         [Ciule]      = {Ciugt,      Ciuge},
 201         [Ciult]      = {Ciuge,      Ciugt},
 202         [Ciugt]      = {Ciule,      Ciult},
 203         [Ciuge]      = {Ciult,      Ciule},
 204         [Cisle]      = {Cisgt,      Cisge},
 205         [Cislt]      = {Cisge,      Cisgt},
 206         [Cisgt]      = {Cisle,      Cislt},
 207         [Cisge]      = {Cislt,      Cisle},
 208         [Cieq]       = {Cine,       Cieq},
 209         [Cine]       = {Cieq,       Cine},
 210         [NCmpI+Cfle] = {NCmpI+Cfgt, NCmpI+Cfge},
 211         [NCmpI+Cflt] = {NCmpI+Cfge, NCmpI+Cfgt},
 212         [NCmpI+Cfgt] = {NCmpI+Cfle, NCmpI+Cflt},
 213         [NCmpI+Cfge] = {NCmpI+Cflt, NCmpI+Cfle},
 214         [NCmpI+Cfeq] = {NCmpI+Cfne, NCmpI+Cfeq},
 215         [NCmpI+Cfne] = {NCmpI+Cfeq, NCmpI+Cfne},
 216         [NCmpI+Cfo]  = {NCmpI+Cfuo, NCmpI+Cfo},
 217         [NCmpI+Cfuo] = {NCmpI+Cfo,  NCmpI+Cfuo},
 218 };
 219
 220 int
 221 cmpneg(int c)
 222 {
 223         assert(0 <= c && c < NCmp);
 224         return cmptab[c][0];
 225 }
 226
 227 int
 228 cmpop(int c)
 229 {
 230         assert(0 <= c && c < NCmp);
 231         return cmptab[c][1];
 232 }
 233
 234 int
 235 clsmerge(short *pk, short k)
 236 {
 237         short k1;
 238
 239         k1 = *pk;
 240         if (k1 == Kx) {
 241                 *pk = k;
 242                 return 0;
 243         }
 244         if ((k1 == Kw && k == Kl) || (k1 == Kl && k == Kw)) {
 245                 *pk = Kw;
 246                 return 0;
 247         }
 248         return k1 != k;
 249 }
 250
 251 int
 252 phicls(int t, Tmp *tmp /*, int c*/)
 253 {
 254         if (tmp[t].phi)
 255                 return tmp[t].phi;
 256         return t;
 257 #if 0
 258         int t1;
 259
 260         t1 = tmp[t].phi;
 261         if (!t1)
 262                 t1 = t;
 263         if (t != t1) {
 264                 t1 = phitmp(t1, tmp, c);
 265                 if (c)
 266                         tmp[t].phi = t1;
 267         }
 268         return t1;
 269 #endif
 270 }
 271
 272 Ref
 273 newtmp(char *prfx, int k,  Fn *fn)
 274 {
 275         static int n;
 276         int t;
 277
 278         t = fn->ntmp++;
 279         vgrow(&fn->tmp, fn->ntmp);
 280         memset(&fn->tmp[t], 0, sizeof(Tmp));
 281         if (prfx)
 282                 sprintf(fn->tmp[t].name, "%s.%d", prfx, ++n);
 283         fn->tmp[t].cls = k;
 284         fn->tmp[t].slot = -1;
 285         fn->tmp[t].nuse = +1;
 286         fn->tmp[t].ndef = +1;
 287         return TMP(t);
 288 }
 289
 290 void
 291 chuse(Ref r, int du, Fn *fn)
 292 {
 293         if (rtype(r) == RTmp)
 294                 fn->tmp[r.val].nuse += du;
 295 }
 296
 297 Ref
 298 getcon(int64_t val, Fn *fn)
 299 {
 300         int c;
 301
 302         for (c=0; c<fn->ncon; c++)
 303                 if (fn->con[c].type == CBits && fn->con[c].bits.i == val)
 304                         return CON(c);
 305         vgrow(&fn->con, ++fn->ncon);
 306         fn->con[c] = (Con){.type = CBits, .bits.i = val};
 307         return CON(c);
 308 }
 309
 310 void
 311 addcon(Con *c0, Con *c1)
 312 {
 313         if (c0->type == CUndef)
 314                 *c0 = *c1;
 315         else {
 316                 if (c1->type == CAddr) {
 317                         assert(c0->type != CAddr && "adding two addresses");
 318                         c0->type = CAddr;
 319                         strcpy(c0->label, c1->label);
 320                 }
 321                 c0->bits.i += c1->bits.i;
 322         }
 323 }
 324
 325 void
 326 blit(Ref rdst, uint doff, Ref rsrc, uint sz, Fn *fn)
 327 {
 328         struct { int st, ld, cls, size; } *p, tbl[] = {
 329                 { Ostorel, Oload,   Kl, 8 },
 330                 { Ostorew, Oload,   Kw, 8 },
 331                 { Ostoreh, Oloaduh, Kw, 2 },
 332                 { Ostoreb, Oloadub, Kw, 1 }
 333         };
 334         Ref r, r1;
 335         uint boff, s;
 336
 337         for (boff=0, p=tbl; sz; p++)
 338                 for (s=p->size; sz>=s; sz-=s, doff+=s, boff+=s) {
 339                         r = newtmp("blt", Kl, fn);
 340                         r1 = newtmp("blt", Kl, fn);
 341                         emit(p->st, 0, R, r, r1);
 342                         emit(Oadd, Kl, r1, rdst, getcon(doff, fn));
 343                         r1 = newtmp("blt", Kl, fn);
 344                         emit(p->ld, p->cls, r, r1, R);
 345                         emit(Oadd, Kl, r1, rsrc, getcon(boff, fn));
 346                 }
 347 }
 348
 349 void
 350 bsinit(BSet *bs, uint n)
 351 {
 352         n = (n + NBit-1) / NBit;
 353         bs->nt = n;
 354         bs->t = alloc(n * sizeof bs->t[0]);
 355 }
 356
 357 MAKESURE(NBit_is_64, NBit == 64);
 358 inline static uint
 359 popcnt(bits b)
 360 {
 361         b = (b & 0x5555555555555555) + ((b>>1) & 0x5555555555555555);
 362         b = (b & 0x3333333333333333) + ((b>>2) & 0x3333333333333333);
 363         b = (b & 0x0f0f0f0f0f0f0f0f) + ((b>>4) & 0x0f0f0f0f0f0f0f0f);
 364         b += (b>>8);
 365         b += (b>>16);
 366         b += (b>>32);
 367         return b & 0xff;
 368 }
 369
 370 inline static int
 371 firstbit(bits b)
 372 {
 373         int n;
 374
 375         n = 0;
 376         if (!(b & 0xffffffff)) {
 377                 n += 32;
 378                 b >>= 32;
 379         }
 380         if (!(b & 0xffff)) {
 381                 n += 16;
 382                 b >>= 16;
 383         }
 384         if (!(b & 0xff)) {
 385                 n += 8;
 386                 b >>= 8;
 387         }
 388         if (!(b & 0xf)) {
 389                 n += 4;
 390                 b >>= 4;
 391         }
 392         n += (char[16]){4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}[b & 0xf];
 393         return n;
 394 }
 395
 396 uint
 397 bscount(BSet *bs)
 398 {
 399         uint i, n;
 400
 401         n = 0;
 402         for (i=0; i<bs->nt; i++)
 403                 n += popcnt(bs->t[i]);
 404         return n;
 405 }
 406
 407 static inline uint
 408 bsmax(BSet *bs)
 409 {
 410         return bs->nt * NBit;
 411 }
 412
 413 void
 414 bsset(BSet *bs, uint elt)
 415 {
 416         assert(elt < bsmax(bs));
 417         bs->t[elt/NBit] |= BIT(elt%NBit);
 418 }
 419
 420 void
 421 bsclr(BSet *bs, uint elt)
 422 {
 423         assert(elt < bsmax(bs));
 424         bs->t[elt/NBit] &= ~BIT(elt%NBit);
 425 }
 426
 427 #define BSOP(f, op)                           \
 428         void                                  \
 429         f(BSet *a, BSet *b)                   \
 430         {                                     \
 431                 uint i;                       \
 432                                               \
 433                 assert(a->nt == b->nt);       \
 434                 for (i=0; i<a->nt; i++)       \
 435                         a->t[i] op b->t[i];   \
 436         }
 437
 438 BSOP(bscopy, =)
 439 BSOP(bsunion, |=)
 440 BSOP(bsinter, &=)
 441 BSOP(bsdiff, &= ~)
 442
 443 int
 444 bsequal(BSet *a, BSet *b)
 445 {
 446         uint i;
 447
 448         assert(a->nt == b->nt);
 449         for (i=0; i<a->nt; i++)
 450                 if (a->t[i] != b->t[i])
 451                         return 0;
 452         return 1;
 453 }
 454
 455 void
 456 bszero(BSet *bs)
 457 {
 458         memset(bs->t, 0, bs->nt * sizeof bs->t[0]);
 459 }
 460
 461 /* iterates on a bitset, use as follows
 462  *
 463  *      for (i=0; bsiter(set, &i); i++)
 464  *              use(i);
 465  *
 466  */
 467 int
 468 bsiter(BSet *bs, int *elt)
 469 {
 470         bits b;
 471         uint t, i;
 472
 473         i = *elt;
 474         t = i/NBit;
 475         if (t >= bs->nt)
 476                 return 0;
 477         b = bs->t[t];
 478         b &= ~(BIT(i%NBit) - 1);
 479         while (!b) {
 480                 ++t;
 481                 if (t >= bs->nt)
 482                         return 0;
 483                 b = bs->t[t];
 484         }
 485         *elt = NBit*t + firstbit(b);
 486         return 1;
 487 }
 488
 489 void
 490 dumpts(BSet *bs, Tmp *tmp, FILE *f)
 491 {
 492         int t;
 493
 494         fprintf(f, "[");
 495         for (t=Tmp0; bsiter(bs, &t); t++)
 496                 fprintf(f, " %s", tmp[t].name);
 497         fprintf(f, " ]\n");
 498 }