util.c

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